数据结构章.pptVIP

0　12　 9　 0　 0　 0 0 0　 0　 0　 0 0　 0 0　 －3　 0　 0　 0　 0 14 0　 0　 0 24 0　 0　 0 0 0　18　 0　 0　 0　 0 0 15　 0　 0 －7 0 0　 0 M = 求下列6×7稀疏矩阵M的转置矩阵： 例： M中共有42个元素，而非零元素只有8个。则对应的三元组表和行、列值为： ((1, 2, 12), (1, 3, 9), (3, 1, －3), (3, 6, 14), (4, 3, 24), (5, 2, 18), (6, 1, 15), (6, 4, －7))和(6, 7, 8) 分析： 表中的最后一个元素(6, 7, 8)表示矩阵M为6?7阶的矩阵，且有8个非零元。 转置运算是一种最简单的矩阵运算，且转置后的矩阵仍为稀疏矩阵。即：对于m×n矩阵M，其转置T为n×m矩阵，且T(i, j)=M(j, i),1≤i≤n, 1≤j≤m。 设a和b是TSMatrix型的变量，分别表示M和T。那么，如何由a.data得到b.data呢？(约定0号单元不用) 方法如下： ⅰ) 行列数互换：RowN←→ColN ⅱ) 三元组中的行列标互换：i ←→ j ⅲ) 按行主次序重排三元组之间的次序即可得b.data。 前两条容易做到，关键是如何实现第三条，即：如何使b.data中的三元组按T的行主次序排列？ i j Value 1 2 12 1 3 9 3 1 –3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 –7 i j Value 1 3 –3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 –7 6 3 14 a.data b.data i和j互换并重排b.data 两种方法： 算法思想：按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。为了找到M的每列中的所有非零元素，必须每次对三元组表a.data全部扫描一遍。 a) 经典算法：按矩阵M的列序进行转置。 矩阵的转置算法： P99 Status TransposeSMatrix(TSMatrix M, TSMatrix T) { // 采用三元组表存储表示，求稀疏矩阵M的转置矩阵T。 T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) { q = 1; for (col = 1; col = M.tu; ＋＋col) for (p = 1; p = M.tu; ＋＋p) if (M.data[p].j = = 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; ＋＋q; } // if } // if return OK;} // TransposeSMatrix 算法分析：算法耗费的主要时间在二重for循环中，故其时间复杂度为：T(n)=O(M.nu×M.tu)，简记为O(nu×tu)，即：和M的列数及非零元个数成正比。 一般的矩阵转置算法的时间复杂度为：T(n)=O(mu×nu)。显然，当tu和mu×nu同数量级时，上述算法的时间复杂度为：O(mu×nu2)。因此，上述算法仅适于tu mu×nu。即：非零元个数远远小于零元个数。 算法思想：按a.data中三元组的次序进行转置，并将转置后的三元组直接存放到b.data中恰当的位置。那么，必须预先确定M中每一列(即T中每一行)的第一个非零元在b.data中应有的位置以及M中每一列非零元的个数。 附设两个数组:　 num[M.nu+1]和cpot[M.nu+1] b) 快速转置：求转置矩阵的改进算法。 (约定0号单元不用) 其中：num[col]存放矩阵M中第col列非零元的个数。 cpot[col]存放矩阵M中第col列的第一个非零元在b.data中的恰当位置。显然有： cpot[1]＝1; cpot[col]＝cpot[col–1]+num[col–1] (2≤col≤a.nu) 本例中的矩阵M的num和cpot的值如下表： 9 8 8 7 5