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

要你对一个三元表进行步骤最少的转置，你可能会想，如果知道三元表中每一项在转置后的新的三元表中的位置，然后直接放进去，岂不是极大的缩小了时间复杂度？没错！快速转置法正是基于这种思想而设计的。
那么如何知道三元表中某一项的位置呢？在课本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】稀疏矩阵的快速转置原理及其算法
原文标题：稀疏矩阵转置之快速转置法|落絮飞雁的个人网站
原文链接：https://www.luoxufeiyan.com/2015/05/12/trans-matrix-fast/
授权协议：创作共用 署名-非商业性使用 2.5 中国大陆
除注明外，本站文章均为原创；转载时请保留上述链接。