落絮飞雁的个人网站
稀疏矩阵转置之快速转置法
稀疏矩阵转置之快速转置法

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

要你对一个三元表进行步骤最少的转置,你可能会想,如果知道三元表中每一项在转置后的新的三元表中的位置,然后直接放进去,岂不是极大的缩小了时间复杂度?没错!快速转置法正是基于这种思想而设计的。
那么如何知道三元表中某一项的位置呢?在课本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位。

https://www.luoxufeiyan.com/wp-content/uploads/2015/05/150512Matrix.jpg

接下来就轻松多了,转置的时候直接从第一项读起,读取其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 <= a.n; i++)
	{
		for (j = 1; j <= a.m; j++)
		{
			printf("请输入矩阵 %d 行 %d 列 三元组元素的值,回车键结束哦。n", i, j);
			scanf("%d", &tmp);
			if (tmp)
			{
				a.t++;
				a.data[a.t].i = i;
				a.data[a.t].j = j;
				a.data[a.t].e = tmp;
			}
		}
	}
}


void Trans(Matrix a, Matrix &b)
{
	int num[MAXROW + 1] = { 0 }, pos[MAXROW + 1] = { 0 };
	int i, j, p;

	b.n = a.m; b.m = a.n; b.t = a.t;//行列转换

	for (i = 1; i <= a.t; i++) num[a.data[i].j]++;
	for (i = 1; i <= a.m; i++) pos[i] = pos[i - 1] + num[i];
	for (i = a.t; 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 <= a.n; i++)
	{
		for (j = 1; j <= a.m; j++)
		if (i == a.data[u].i && j == a.data[u].j) printf("%d ", a.data[u++].e);
		else printf("0 ");
		printf("n");
	}
	printf("n");
	printf("输出完毕,棒棒哒~nn");
}

int main()
{
	Matrix a, b;
	printf("=====矩阵转置 By:落絮飞雁=====n");
	while (1)
	{
		Inst(a);
		Trans(a, b);
		Out(b);
	}
	return 0;
}

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

原文标题:稀疏矩阵转置之快速转置法|落絮飞雁的个人网站
授权协议:创作共用 署名-非商业性使用 2.5 中国大陆
除注明外,本站文章均为原创;转载时请保留上述链接。

发表评论

textsms
account_circle
email

落絮飞雁的个人网站

稀疏矩阵转置之快速转置法
数据结构作业题目 = = 前情回顾:矩阵转置-简单代码 要你对一个三元表进行步骤最少的转置,你可能会想,如果知道三元表中每一项在转置后的新的三元表中的位置,然后直接放进去,岂不是…
扫描二维码继续阅读
2015-05-12