算法4~矩阵的转置

《算法4~矩阵的转置》由会员分享，可在线阅读，更多相关《算法4~矩阵的转置（24页珍藏版）》请在金锄头文库上搜索。

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

2、14 4 3 24 5 2 18 6 1 15 6 4 7 和矩阵维数 6 7 唯一确定 6 稀疏矩阵的压缩存储 1 三元组顺序表 defineMAXSIZE12500typedefstruct inti j 该非零元的行标和列标ElemTypee 该非零元的值 Triple 三元组类型 typedefstruct Tripledata MAXSIZE 1 data 0 未用intmu nu tu 矩阵的行数 列数及非零元个数 TSMatrix 稀疏矩阵类型 7 稀疏矩阵的压缩存储 例如 structTSMatrixM M mu 6 M nu 7 M tu 8 M data 4 M data

3、5 M data 6 M data 7 M data 8 M data 0 M data 1 M data 2 M data 3 8 稀疏矩阵的压缩存储 2 行逻辑链接的顺序表 为了便于对矩阵中任意一行非零元素进行操作 对三元组顺序表结构进行修改 增加一个量来记录每一行非零元在三元组表中的位置 这种 带行链接信息 的三元组表称为行逻辑链接的顺序表 typedefstruct Tripledata MAXSIZE 1 intrpos MAXRC 1 各行第一个非零元的位置表intmu nu tu RLSMatrix 行逻辑链接顺序表类型 9 稀疏矩阵的压缩存储 例如 M data 4 M dat

4、a 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 时间复杂度为 行数 列数 11 矩阵的转置 defineMAXSIZE12500typedefstruct inti j 该非零元的行标和列标Ele

5、mTypee 该非零元的值 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 矩阵的转置 i和j相交换实现转置 这样实现是否

6、正确 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中三元组的次序进行转置 并将转置后

7、的三元组置入T中恰当的位置上 15 压缩转置算法 1 压缩转置算法 核心思想 按照T data中三元组的次序依次在M data中找到相应的三元组进行转置 M mu 6 M nu 7 M tu 8 T mu 7 T nu 6 T tu 8 q 1 按照从1到M nu 反复查看M矩阵的三元组表中j值 按照递增的顺序重置入T中 col 1 M data p j col 1 3 3 q 2 1 6 15 q 3 col 2 2 1 12 2 5 18 3 1 9 3 4 24 4 6 7 6 3 14 16 压缩转置算法 StatusTransPoseSMatrix TSMatrixM TSMatri

8、x TranposeSMatrix 算法描述 17 压缩转置算法 压缩转置算法时间复杂度 O nu tu 即与M的列数及非零元的个数的乘积成正比 当非零元数量tu和mu nu同数量级时 算法的时间复杂度就为 O mu nu nu 可见 比不压缩存储的矩阵转置的时间复杂度O mu nu 还要高 虽然 节省了存储空间 但时间复杂度提高了 压缩转置算法仅适于非零元很少 tu mu nu 的情况下 18 压缩快速转置算法 2 压缩快速转置算法 核心思想 按照M data中三元组的次序进行转置 并将转置后的三元组置入T中恰当的位置上 如果不用多次扫描M三元组表 而是在一次扫描中就将每个元素置入T中该元素

9、所应该在的位置上 就可以大大提高时间复杂度了 关键问题在于如何确定每个元素在T中的位置 p 1 M T 2 1 12 p 2 3 1 9 p 3 1 3 3 19 压缩快速转置算法 为了确定这些位置 在转置前 应先求得M的每一列中非零元的个数 进而求得每一列的第一个非零元在T中应在的位置 需要附设两个数组 num col 表示矩阵M中第col列中非零元的个数 cpot col 指示M中第col列的第一个非零元在T data 中的恰当位置 显然两者的关系为 cpot 1 1cpot col cpot col 1 num col 1 20 压缩快速转置算法 for col 1 col M nu c

10、ol num col 0 0 0 0 0 0 0 0 for t 1 t M tu t num M data t j 1 1 1 2 2 2 1 1 cpot 1 1 for col 2 col M nu col cpot col cpot col 1 num col 1 1 3 5 7 8 8 9 21 压缩快速转置算法 M T for p 1 p M tu p col M data p j q cpot col M的p位置数据拷贝到T的q位置上 cpot col p 1 col 2 q 3 2 1 12 1 3 5 7 8 8 9 4 p 2 col 3 q 5 3 9 1 6 p 3 c

11、ol 1 q 1 1 3 3 2 p 4 col 6 q 8 6 3 14 9 p 5 col 3 q 6 3 4 24 22 压缩快速转置算法 StatusFastTransposeSMatrix TSMatrixM TSMatrix FastTransposeSMatrix col M data p j q cpot 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 cpot col 23 压缩快速转置算法 算法的效率分析 时间上 算法中主要的基本操作为 该算法的时间复杂度 2 nu 2 tu O nu tu for col 1 col M nu col 循环次数 nu for i 1 i M tu i 循环次数 tu for col 2 col M nu col 循环次数 nu for p 1 p M tu p 循环次数 tu 最坏的情况 tu nu mu 时间复杂度为O nu mu 24 压缩快速转置算法 算法的效率分析 空间上 算法中增加了两个辅助数组num 和cpot 长度为矩阵的列数nu