稀疏矩阵转置之快速转置法

数据结构作业题目 = =
前情回顾:矩阵转置-简单代码

要你对一个三元表进行步骤最少的转置,你可能会想,如果知道三元表中每一项在转置后的新的三元表中的位置,然后直接放进去,岂不是极大的缩小了时间复杂度?没错!快速转置法正是基于这种思想而设计的。
那么如何知道三元表中某一项的位置呢?在课本98页的a.data这个三元表可以看到,j为列号,在转置后即为新的三元表的行号,三元表正是按照行序进行排列的,而j=1有2个、j=2有2个、j=3有2个、j=4有1个、j=6有1个。根据这些数据按照从小到大排列,j=1的项在新的三元表中应占据第1、2位,j=2的项在新的三元表中应占据第3、4位,j=3的项在新的三元表中应占据第5、6位,j=4应占据第7位,j=6应占据第8位。

接下来就轻松多了,转置的时候直接从第一项读起,读取其j值,比如课本中a.data这个三元表的第一项的j值为2,因为j=2占据第3、4位,所以应该从第三位开始放,接下来如果读取的某一项的j值也是2,就放在第4位。因为j=2的项只有两个,所以第5位绝对不会被j=2的项占据,第5、6项本来就是留给j=3的。再比如当读到j=6的那项时,第8位是留给它的,就可以直接放进第8位了。这样,读取每一项,都能在三元表中找到相应的位置,这就是稀疏矩阵快速转置的原理。

代码:

#include

#define MAXROW 250            //最大列数
#define MAXSIZE 12500       //稀疏矩阵中元素的最多个数

typedef int ElemType;       //不清楚要求所以先开int了

typedef struct
{
	int i, j;                //i:行  j:列
	ElemType e;
}Triple;                    //三元组

typedef struct
{
	Triple data[MAXSIZE + 1]; //三元组表示元素信息
	int n, m, t;              //n:行m:列t:元素个数
}Matrix;                  //矩阵


void Inst(Matrix &a)
{
	int i, j;
	ElemType tmp;
	printf("请输入当前矩阵的行列数,以空格分开哦。n");
	scanf("%d%d", &a.n, &a.m);
	a.t = 0;
	for (i = 1; i = 1; i--)
	{
		p = pos[a.data[i].j]--;
		b.data[p].i = a.data[i].j;
		b.data[p].j = a.data[i].i;
		b.data[p].e = a.data[i].e;
	}
}

void Out(Matrix a)//依次输出
{
	int i, j;
	int u = 1;
	printf("矩阵转置的结果为n");
	for (i = 1; i 

参考:
【LB】稀疏矩阵的快速转置原理及其算法

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注