数据结构课件：稀疏矩阵的转置.pptx

稀疏矩阵的转置

本讲要点朴素转置算法快速转置算法

1.朴素转置算法转置

1.朴素转置算法转置的基本思想：在A的三元组顺序表中依次找第1列、第2列、…直到最后一列的三元组，并将找到的每个三元组的行、列交换后顺序存储到B的三元组顺序表中。

1.朴素转置算法算法分析：为了在矩阵A的三元组表中依次寻找第1列，第2列，…，第n列的非零元素，需要对三元组表进行n趟重复的扫描。。对于一个m行n列且非零元素个数为t的稀疏矩阵而言，该算法的时间复杂度为O(nt)。最坏情况是，当稀疏矩阵中的非零元素个数t与mn同数量级时，上述算法的时间复杂度就为O(mn2)。显然这种情况下，该朴素算法效率较低。

2.快速转置算法改进着眼点：通过扫描一趟矩阵A的三元组表，将每个非零元素行列互换后直接存入矩阵B的三元组表中的适当位置。如果能预先确定矩阵A的每一列的第一个非零元素在矩阵B的三元组表中的位置，每一列的其他非零元素则应是依次排在该位置的后面，就可以直接对它们在矩阵B的三元组表中进行定位了。顺序取，直接存。即在A中依次取三元组，交换其行号和列号放到B中适当位置。

2.快速转置算法如何确定当前从A中取出的三元组在B中的位置？第2列第1个非零元素第2列有2个非零元素第3列第1个非零元素观察转置后矩阵的三元组顺序表第4列第1个非零元素第5列第1个非零元素第6列第1个非零元素

2.快速转置算法如何确定当前从A中取出的三元组在B中的位置？第2列第1个非零元素第2列有2个非零元素第3列第1个非零元素第4列第1个非零元素第5列第1个非零元素第6列第1个非零元素引入两个数组作为辅助数据结构：cnum[cols]：存储矩阵A中某列的非零元素的个数；cpot[clos]：初值表示矩阵A中某列的第一个非零元素在B中的位置。数据结构设计：cpot[1]=0；cpot[col]=cpot[col-1]+cnum[col-1]；1＜col≤colscnum与cpot存在如下递推关系：

2.快速转置算法将矩阵A中col列元素存放在B中下标为cpot[col]的位置矩阵的行数）6（矩阵的列数）7（非零元个数）cpot[1]cpot[3]cpot[4]cpot[5]cpot[6]212cpot[2]122154265324435453641ij矩阵的行数）7（矩阵的列数）7（非零元个数）ijecpot[7]

2.快速转置算法将矩阵A中col列元素存放在B中下标为cpot[col]的位置矩阵的行数）6（矩阵的列数）7（非零元个数）cpot[1]cpot[2]cpot[3]cpot[4]cpot[5]cpot[6]212122154265324435453641ij矩阵的行数）7（矩阵的列数）7（非零元个数）ijecpot[7]

2.快速转置算法将矩阵A中col列元素存放在B中下标为cpot[col]的位置矩阵的行数）6（矩阵的列数）7（非零元个数）cpot[1]cpot[2]cpot[3]cpot[4]cpot[5]cpot[6]212514122154265324435453641ij矩阵的行数）7（矩阵的列数）7（非零元个