5.2.2 稀疏矩阵的压缩存储方法

　一、三元组顺序表

算法 5.1
　　void FastTransposeSMatrix(TSMatrix M, TSMatrix &T)
　{
　　// 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵 T
　　T.rows = M.cols;
　　T.cols = M.rows;
　　T.terms = M.terms;
　　if (T.terms) {
　　　for (col=1; col<=M. cols; ++col)
　　　　num[col] = 0;
　　　for (t=1; t<=M. terms; ++t)
　　　　++num[M.data[t].j];　　　　　　// 求 M 中每一列所含非零元的个数
　　　rpos[1] = 1;
　　　for (col=2; col<=M. cols; ++col)
　　　　rpos[col] = rpos[col-1] + num[col-1];
　　　　　　　　　　　　　　// 求T中每一行的第一个非零元在T.data中的序号
　　　for (p=1; p<=M.terms; ++p) { 　// 转置矩阵元素
　　　　col = M.data[p].j; q = rpos[col];
　　　　T.data[q].i =M.data[p].j;
　　　　T.data[q].j =M.data[p].i;
　　　　T.data[q].e =M.data[p].e;
　　　　++rpos[col];
　　　} // for
　　} // if
　} // FastTransposeSMatrix

　　上述算法的时间复杂度为O (M.cols+M.terms)。		  

　

　　算法的控制结构为四个并列的循环，其中两个的循环次数和M矩阵的列数n成正比，另两个的循环次数和非零元的个数t成正比，显然算法的时间复杂度为O(n+t)。

  思考题 当以二维数组表示矩阵时，转置算法的时间复杂度是什么？
　是O(M.rows×M.cols)，对吗？和三元组顺序表表示时的转置算法相比，你将得出什么结论呢？

　　从转置算法可见，这种表示方法便于进行"按行依次存取元素"的矩阵运算，但不便进行"需要随机存取某一行元素"的矩阵运算。