算法4-矩阵的转置.pptxVIP

矩阵的转置

2本节主要内容矩阵的转置算法01改进的快速转置算法02

3稀疏矩阵的压缩存储对于元素分布都有一定的规律，我们都将其压缩存储到一维数组中，并找到每个矩阵元素在数组中的对应关系。稀疏矩阵：若非零元很少，而且分布没有一定的规律，如何来存储呢？？非零元较零元少，且分布没有一定规律。稀疏因子:假设m行n列的矩阵含t个非零元素，则称通常认为??0.05的矩阵为稀疏矩阵。非零元素个数总元素个数稀疏因子

42、行逻辑链接的顺序表三元组顺序表稀疏矩阵的压缩存储十字链表

5稀疏矩阵的压缩存储三元组顺序表可由三元组表((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))和矩阵维数（6,7）唯一确定

61、三元组顺序表稀疏矩阵的压缩存储#2022

7稀疏矩阵的压缩存储例如：structTSMatrixM;M.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]

82、行逻辑链接的顺序表稀疏矩阵的压缩存储#2022

9稀疏矩阵的压缩存储例如：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]structRLSMatrixM;M.mu=6;M.nu=7;M.tu=8;

10矩阵的转何实现？那么，转置算法为：行，列元素相交换。如果矩阵未采用压缩存储方式，采用二维数组作为存储结构：for(col=1;col=列数;++col)for(row=1;row=行数;++row)T[col][row]=M[row][col];05时间复杂度为：Ο(行数*列数)

11矩阵的转置#defineMAXSIZE12500typedefstruct{inti,j;//该非零元的行标和列标ElemTypee;//该非零元的值}Triple;//三元组类型typedefstruct{Tripledata[MAXSIZE+1];//data[0]未用intmu,nu,tu;//矩阵的行数、列数及非零元个数}TSMatrix;//稀疏矩阵类型若矩阵采用压缩存储-----三元组顺序表作为存储结构，如何实现矩阵的转置？？

12矩阵的转置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]M.mu=6;M.nu=7;M.tu=8;structTSMatrixM;

13矩阵的转置T.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]i和j相交换实现转置，这样实现是否正确？

14矩阵的转置为了便于实现矩阵的各类算法，通常采用三元组顺序表对矩阵进行存储时，都将元素按照i值（行值）排列为非递减序列。因此，矩阵的转置（假设矩阵M转置为矩阵T）：1、将矩阵M的行值赋给矩阵T的列值，M的列值赋给T的行值；2、将M的每个元素三元组中的i值给T的每个元素三元组中的j值；M的每个元素三元组中的j值给T的每个元素三元组中的i值。3、应让T的三元组元素按照i值（行值）重新排序。通常有两种方法：1、压缩转置算法：核心思想：按照T.data中三元组的次序依次在M.data中找到相应的三元组进行转置。2、压缩快速转置算法：核心思想：按照M.data中三元组的次序进行转置，并将转置后的三元组置入T中恰当的位置上。

15压缩转置算法1、压缩转置算法：核心思想：按照T.data中三元组的次序依次在M.data中找到相应的三元组进行转置。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]M.mu=6;M.nu=7;M.tu=8T.mu=7;T.nu=6;T.tu=8;T.data[8]T.data[7]T.data[