第5章 数组和广义表解析.ppt

void TransMatrix（ElementType source［n］［m］, ElementType dest［m］［n］） {/*source和dest分别为被转置的矩阵和转置以后的矩阵（用二维数组表示）*/ int i, j;  for(i=0; im; i++) for (j=0; j n; j++) dest［i］［ j］=source［j］ ［i］ ;  } ① 矩阵source的三元组表A的行、 列互换就可以得到B中的元素， 如图5.13所示。 (i, j, x) ——— (j, i, x) ↑ ↑ A B 图5.13 稀疏矩阵的转置示例 ② 为了保证转置后的矩阵的三元组表B也是以“行序为主序”进行存放，则需要对行、列互换后的三元组表B按B的行下标（即A的列下标）大小重新排序，如图5.14所示。 图5.14 矩阵的转置(用三元组表示矩阵) 方法一： 按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。即以M的列序进行转置。对a.data的三元组进行扫描，由于a.data以M的行序为主序存放，得到的恰是b.data应有的顺序。 图5.15 矩阵的转置 Status TransposeSMatrix ( TSMatrix M, TSMatrix T ){ T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if( T.tu ){ q=1; for( col=1; col=M.nu; ++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; } } return OK; } // TransposeSMatrix 算法的时间耗费主要是在双重循环中，其时间复杂度为O ( mu×tu )。若tu 和mu×nu 同数量级时，前述算法 O ( mu×nu2) 。  方法二： 按照a.data 中三元组的次序进行转置，并将转置后的三元组置入b中的恰当位置。预先确定M中每一列（即T 中每一行）的第一个非零元在b.data中恰当的位置，对a.data 扫描是可直接放入b.data 中恰当的位置。附设两个向量：num和cpot。num[col]表示矩阵M中第col列中非零元的个数，cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置。 为了能将待转置三元组表A中元素一次定位到三元组表B的正确位置上，需要预先计算以下数据：  (1) 待转置矩阵每一列中非零元素的个数（即转置后矩阵每一行中非零元素的个数）。  (2) 待转置矩阵每一列中第一个非零元素在三元组表B中的正确位置（即转置后矩阵每一行中第一个非零元素在三元组B中的正确位置)。 cpot[col］的计算方法：  cpot［1］=1，  cpot［col］=cpot［col-1］+num［col-1］， 其中2 ≤ col≤a.nu。 图5.16 图5.10中矩阵M的num［col］和cpot[col］的值 Status FastTransposeSMatrix( 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++) num[col]=0; for(t=1; t=M.tu;++ t)