数据结构chap5.pptVIP

5．2 矩阵的压缩存储 3 转置运算算法 下面以矩阵的转置运算为例，讨论在三元组顺序表存储方式下，如何实现矩阵的运算。本课件介绍两种转置运算算法。 转置运算是一种最简单的矩阵运算。对于一个m行n列的矩阵M，它的转置矩阵T是一个n行m列的矩阵。例如，下图中的矩阵M和T互为转置矩阵。 M = 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 T = 0 0 -3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 5．2 矩阵的压缩存储 M 第一列 第二列 第三列 第四列 第五列 第六列 第七列 T 第一行 第二行 第三行 第四行 第五行 第六行 第七行 5．2 矩阵的压缩存储 i j v 1 2 3 4 5 6 7 8 3 1 -3 6 1 15 1 2 12 5 2 18 1 3 9 4 3 24 6 4 -7 3 6 14 M.data 6 7 8 M.mu M.nu M.tu i j v 1 2 3 4 5 6 7 8 2 1 12 4 6 -7 1 3 -3 3 4 24 1 6 15 3 1 9 6 3 14 2 5 18 T.data 7 6 8 T.mu T.nu T.tu 矩阵M的三元组顺序表 M的转置矩阵T的三元组顺序表 5．2 矩阵的压缩存储 1) 转置运算算法TransposeSMatrix(TSMatrix M, TSMatrix T) 思路：反复扫描M.data中的列序，从小到大依次进行转置。 主要步骤： 对M.data从头至尾扫描： 第一次扫描时，将M.data中列号为1的三元组赋值到T.data中， 第二次扫描时，将M.data中列号为2的三元组赋值到T.data中， ………… 依此类推，直至将M.data所有三元组赋值到T.data中。 5．2 矩阵的压缩存储 转置运算算法 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; // q为当前三元组在T.data[ ]中的下标 for (col=1; col=M.nu; ++col) //col用于控制矩阵M的列数 for (p=1; p=M.tu; ++p) //p为M三元组表中的下标 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; } } return OK; } //TransposeSMatrix 算法5.1 i j v 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 v 3 1 -3 2 5 18 1 3 -3 6 1 15 1 6 15 1 2 12 2 1 12 5 2 18 1 3 9 3 1 9 4 3 24 3 4 24 6 4 -7 4 6 -7 3 6 14 6 3 14 M.data T.data 对M六次扫描完成转置运算