算法4-矩阵的转置.ppt

《算法4-矩阵的转置.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、矩阵的转置本节主要内容1.矩阵的转置算法2.改进的快速转置算法2稀疏矩阵的压缩存储对于元素分布都有一定的规律，我们都将其压缩存储到一维数组中，并找到每个矩阵元素在数组中的对应关系。稀疏矩阵：若非零元很少，而且分布没有一定的规律，如何来存储呢？？非零元较零元少，且分布没有一定规律。稀疏因子:假设m行n列的矩阵含t个非零元素，则称通常认为0.05的矩阵为稀疏矩阵。非零元素个数总元素个数稀疏因子3稀疏矩阵的压缩存储1、三元组顺序表2、行逻辑链接的顺序表3、十字链表4稀疏矩阵的压缩存储1、三元组顺序表可由三元组表((1,2,12),(

2、1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))和矩阵维数（6,7）唯一确定5稀疏矩阵的压缩存储1、三元组顺序表#defineMAXSIZE12500typedefstruct{inti,j;//该非零元的行标和列标ElemTypee;//该非零元的值}Triple;//三元组类型typedefstruct{Tripledata[MAXSIZE+1];//data[0]未用intmu,nu,tu;//矩阵的行数、列数及非零元个数}TSMatrix;//稀疏矩

3、阵类型6稀疏矩阵的压缩存储例如：structTSMatrixM;ije121213931-3361443245218611564-7M.mu=6;M.nu=7;M.tu=8;M.data[4]M.data[5]M.data[6]M.data[7]M.data[8]M.data[0]M.data[1]M.data[2]M.data[3]7稀疏矩阵的压缩存储2、行逻辑链接的顺序表为了便于对矩阵中任意一行非零元素进行操作，对三元组顺序表结构进行修改，增加一个量来记录每一行非零元在三元组表中的位置，这种“带行链接信息”的三元组表称为行逻辑

4、链接的顺序表。typedefstruct{Tripledata[MAXSIZE+1];intrpos[MAXRC+1];//各行第一个非零元的位置表intmu,nu,tu;}RLSMatrix;//行逻辑链接顺序表类型8稀疏矩阵的压缩存储例如：ije121213931-3361443245218611564-7M.data[4]M.data[5]M.data[6]M.data[7]M.data[8]M.data[0]M.data[1]M.data[2]M.data[3]structRLSMatrixM;行0123456rpos[]

5、133567M.mu=6;M.nu=7;M.tu=8;9矩阵的转置如何实现？如果矩阵未采用压缩存储方式，采用二维数组作为存储结构：那么，转置算法为：行，列元素相交换。for(col=1;col<=列数;++col)for(row=1;row<=行数;++row)T[col][row]=M[row][col];时间复杂度为：Ο(行数*列数)10矩阵的转置#defineMAXSIZE12500typedefstruct{inti,j;//该非零元的行标和列标ElemTypee;//该非零元的值}Triple;//三元组类型typede

6、fstruct{Tripledata[MAXSIZE+1];//data[0]未用intmu,nu,tu;//矩阵的行数、列数及非零元个数}TSMatrix;//稀疏矩阵类型若矩阵采用压缩存储-----三元组顺序表作为存储结构，如何实现矩阵的转置？？11矩阵的转置ije121213931-3361443245218611564-7M.data[4]M.data[5]M.data[6]M.data[7]M.data[8]M.data[0]M.data[1]M.data[2]M.data[3]M.mu=6;M.nu=7;M.tu=8;

7、structTSMatrixM;12矩阵的转置ije121213931-3361443245218611564-7T.data[8]T.data[7]T.data[5]T.data[6]T.data[4]T.data[0]T.data[1]T.data[2]T.data[3]M.data[8]M.data[7]M.data[5]M.data[6]M.data[4]M.data[0]M.data[1]M.data[2]M.data[3]ije211231913-3631434242518161546-7i和j相交换实现转置，这样实现

8、是否正确？13矩阵的转置为了便于实现矩阵的各类算法，通常采用三元组顺序表对矩阵进行存储时，都将元素按照i值（行值）排列为非递减序列。因此，矩阵的转置（假设矩阵M转置为矩阵T）：1、将矩阵M的行值赋给矩阵T的列值，M的列值赋给T的行值；2、将M的每个