数据结构矩阵转置

1、1/63矩阵的转置算法 T = 0 0 -3 0 0 1512 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 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 015 0 0 -7 0 0 02/63 int amn,bmn; for ( i =1; i=m; +i ) for (j = 1; j=n; +j ) bji =aij; 在二维数组存储方式下, 矩阵转置的算法算法的时间复杂度为O（

2、m*n)3/63i j e12345678M.dataM.muM.nuM.tu3 1 -36 1 151 2 125 2 181 3 94 3 246 4 -73 6 14678i j e12345678T.dataT.muT.nuT.tu2 1 124 6 -71 3 -33 4 241 6 153 1 96 3 142 5 18768在三元组顺序表存储方式下, 矩阵转置的算法4/631 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7i j vi j v3 1 -32 5 181 3 -36 1 151 6 51 2 122 1 125 2 181

3、 3 93 1 94 3 243 4 246 4 -74 6 -73 6 146 3 14M.dataT.data第一次扫描查找第1列元素第一次扫描结束第二次扫描结束第二次扫描查找第2列元素第三次扫描查找第3列元素第四次扫描查找第4列元素第五次扫描查找第5列元素第六次扫描查找第6列元素 转置运算算法图示5/63Status TranMatrix(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

4、(col=1; col=M.nu; +col) for (p=1;p=M.tu;+p) /p为扫描M.data“指示器” if (M.datap.j= =col) T.dataq.i =M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +q; /if return OK;/ TransposeSMtrix 算法5.16/63时间复杂度分析 转置运算算法1的时间复杂度为O(nutu) 非零元的个数tu和矩阵元素个数munu 同数量级时，转置运算算法的时间复杂度为O( mununu)。算法一般用于tu munu的情况7/63i j e1234

5、5678M.dataM.muM.nuM.tu3 1 -36 1 151 2 125 2 181 3 94 3 246 4 -73 6 14678i j e12345678T.dataT.muT.nuT.tu2 1 124 6 -71 3 -33 4 241 6 153 1 96 3 142 5 18768 矩阵快速转置算法8/63colnumcolcpotcol1 2 3 4 5 6 228110127853 numcol：存储M第col列非零元个数 cposcol：存储M第col列第一个非零元 在T.data中的位置 cposcol的计算方法： cpos1=1 cposcol=cposcol

6、-1+numcol-1 2 col n12345678M.dataM.muM.nuM.tu3 1 -36 1 151 2 125 2 181 3 94 3 246 4 -73 6 14678辅助向量num 、cpos 9/631 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7colnumcolcpotcol1 2 3 4 5 6 228110135278i j vi j vM.dataT.data1 2 122 1 12第2列第一个非零元在b中的位置1 3 9第3列第一个非零元在b中的位置3 1 93 1 -31 3 -33 6 146 3 144

7、3 243 4 245 2 182 5 186 1 151 6 156 4 -74 6 -74第2列第二个非零元在b中的位置65第4列第二个非零元在b中的位置第1列第一个非零元在b中的位置2793第6列第一个非零元在b中的位置扫描M.data实现M到T 的转置810/63Status FastTransSMatrix(TSMatrix M, TSMatrix &T) /采用三元组顺序表存储稀疏矩阵，求M的转置矩阵T T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) for (col=1; col=M.nu; +col) numcol=0; /求M中每一列非零元个数 for (t=1; t=M.tu; +t) +numM.datat.j; /求第 col列中第一个非零元在T.data中的序号 cpot1=1; for(col=2; col=M.nu; +col) cpotcol=cpotcol-1+numcol-1;11/63 for(p=1; pM.tu; +p) col=M.datap.j; q=cpotcol; T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.