《转置运算算法基本思想》由会员分享，可在线阅读，更多相关《转置运算算法基本思想（45页珍藏版）》请在金锄头文库上搜索。
1、第五章 数组和广义表5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构在早期的高级语言中，数组是唯一可供使用的数 据类型。由于数组中各元素具有统一的类型，并且数 组元素的下标一般具有固定的上界和下界，因此，数 组的处理比其它复杂的结构更为简单。多维数组是向 量的推广。例如，二维数组： A0=( a0,0a0,1 a1,n-1) A1=(a1,0a1,1 a1,n-1) Am-1=(am-1,0am-1,1 am-1,n-1)A=(A0,A1,Am-1)5.1 数组的定义数组的类型定
2、义数组的类型定义 ADT Array 数据对象数据对象： Daj1,j2, .,ji,jn| ji=0,.,bi-1, i=1,2,.,n 数据关系数据关系： RR1, R2, ., Rn Ri | 0 jk bk-1, 1 k n 且k i, 0 ji bi-2, i=2,.,n ADTArray 基本操作基本操作:二维数组的定义二维数组的定义:数据对象:数据对象: D = aij| 0ib1-1, 0 jb2-1 数据关系:数据关系:R = ROW, COL ROW= | 0ib1-2, 0jb2-1COL= | 0ib1-1, 0 jb2-2基本操作基本操作：InitArray(2) 计
3、算中进行了很多和零值的运算，遇除法，还需判别除数是否为零计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。1) 尽可能少存或不存零值元素；解决问题的原则解决问题的原则:2) 尽可能减少没有实际意义的运算；3) 操作方便。 即： 能尽可能快地找到与 下标值(i，j)对应的元素， 能尽可能快地找到同 一行或同一列的非零值元。1) 特殊矩阵特殊矩阵 非零元在矩阵中的分布有一定规则 例如: 三角矩阵 对角矩阵2) 随机稀疏矩阵随机稀疏矩阵 非零元在矩阵中随机出现有两类稀疏矩阵有两类稀疏矩阵：随机稀疏矩阵的压缩存储方法随机稀疏矩阵的压缩存储方法:一、三元组顺序表二、行逻辑联接的顺序表一、三元组
4、顺序表二、行逻辑联接的顺序表(*)三、 十字链表三、 十字链表(*)#define MAXSIZE 12500 typedef struct int i, j;/该非零元的行下标和列下标 ElemType e;/ 该非零元的值 Triple; / 三元组类型三元组类型一、三元组顺序表一、三元组顺序表typedef union Triple dataMAXSIZE + 1; intmu, nu, tu; TSMatrix; / 稀疏矩阵类型稀疏矩阵类型M=0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 0 14 00 0 24 0 0 0 00 18 0 0 0 0 01
5、5 0 0 -7 0 0 0M=0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 0 14 00 0 24 0 0 0 00 18 0 0 0 0 015 0 0 -7 0 0 0Tripletable M；Tripletable M；M.mu M.nu M.tu6 6 7 7 8 80 1 23 456 7M.datai j ei j e3 6 143 6 14 4 3 244 3 245 2 185 2 181 2 121 2 12 1 3 91 3 9 3 1 -33 1 -36 1 156 1 15 6 4 -76 4 -7如何求转置矩阵？如何求转置矩阵？ 028
6、003600070500140005280000007143600用常规的二维数组表示时的算法其时间复杂度为其时间复杂度为: O(munu)for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;用“三元组”表示时如何实现？1 2 14 1 5 -5 2 2 -7 3 1 36 3 4 282 1 145 1 -52 2 -71 3 364 3 28转置运算算法基本思想对 M.data从头至尾扫描： 第一次扫描时，将M.data中列号为1的三元 组赋值到T.data中 第二次扫描时，将M.data中列号为2的三
7、元 组赋值到T.data中 依此类推，直至将M.data所有三元组赋值到 T.data中TransposeSMatrix(M, T) T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) q=0； / q为当前三元组在T.data 存储位置(下标) for (col=1; col=M.nu; +col) for (p=0; p=M.tu-1; +p) /p为扫描M.data 的“指示器” if (M.datap.j= =col) T.dataq.i =M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +q;
8、 / TransposeSMtrixTransposeSMatrix(M, T) T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) q=0； / q为当前三元组在T.data 存储位置(下标) for (col=1; col=M.nu; +col) for (p=0; p=M.tu-1; +p) /p为扫描M.data 的“指示器” if (M.datap.j= =col) T.dataq.i =M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +q; / TransposeSMtrix转置运算算法分析
9、分析这个算法，主要的工作是在p和col的两个 循环中完成的，故算法的时间复杂度为 O(nu*tu)，即矩阵的列数和非零元的个数的乘 积成正比。而一般传统矩阵的转置算法的时间 复杂度为O(nu*mu)。当非零元素的个数t和 mu*nu同数量级时，算法transmatrix的时间复 杂度为O(mu*nu2)。 三元组顺序表虽然节省了存储空间，但时间复 杂度比一般矩阵转置的算法还要复杂，同时还 有可能增加算法的难度。因此，此算法仅适用 于tm*n的情况。快速转置算法的基本思想下面给出另外一种称之为快速转置的算法，其 算法思想为：对A扫描一次，按A第二列提供的 列号一次确定位置装入B的一个三元组。具体
10、实施如下：一遍扫描先确定三元组的位置 关系，二次扫描由位置关系装入三元组。可见， 位置关系是此种算法的关键。例子0 1 2 3 4 5 6 7 7 7i j v21 1246-713-3342416153196 3142518T.dataT.mu T.nu T.tu6 6 8 80 1 2 3 4 5 6 7i j v3 1 -33 1 -36 1 156 1 151 2 121 2 125 2 185 2 181 3 91 3 94 3 244 3 246 4 -76 4 -73 6 143 6 14M.dataM.mu M.nu M.tu6 6 7 7 8 8各列 第一个 非零元 三元组按
11、 先前求出 的位置， 放至 T.data 中各列后续的非零元三元组，顺序放到对应列元素的后面为先求得M各列第一个非零元三元组在 T.data中的位置。引入两个辅助向量num 、pos 两个辅助向量num 、pos ：numcol：存储第col列非零元个数poscol：存储第col列第一个非零元三 元组在T.data中的位置，poscol的计算：pos1=1poscol=poscol-1+numcol-1 2=col=n例 矩阵M例 矩阵Mcolcol1 2 3 4 5 6 71 2 3 4 5 6 7 numcolnumcol 2 2 2 1 0 1 02 2 2 1 0 1 0 poscol
12、poscol 1 3 5 7 8 8 9i j v1 3 5 7 8 8 9i j v3 1 -33 1 -36 1 156 1 151 2 121 2 125 2 185 2 181 3 91 3 94 3 244 3 246 4 -76 4 -73 6 143 6 14辅助向量快速转置算法主要步骤求M中各列非零元个数num 求M中各列第一个非零元在T.data中的下 标pos ; 对M.data进行一次扫描， 遇到col列的第 一个非零元三元组时，按poscol的位置， 将其放至T.data中，当再次遇到col列的 非零元三元组时，只须顺序放到col列元 素的后面;M.dataM.data
13、求各列 第1个 非零元 在b中位置求各列 第1个 非零元 在b中位置colcol1 2 3 4 5 6 71 2 3 4 5 6 7 numcolnumcol 2 2 2 1 0 1 02 2 2 1 0 1 0 poscolposcoli j vi j v3 1 -33 1 -36 1 156 1 151 2 121 2 125 2 185 2 181 3 91 3 94 3 244 3 246 4 -76 4 -73 6 143 6 14T.dataT.datai j vi j v求各列非零 元个数求各列非零 元个数快速转置算法图示1M.dataM.data扫描M.data实 现扫描M.data实 现M到到T 的转 置的转 置colcol1 2 3 4 5 6 71 2 3 4 5 6 7 numcolnumcol 2 2 2 1 0 1 02 2 2 1 0 1 0 poscolposcol 1 3 5 7 8 8 91 3 5 7 8 8 9i j vi j v3 1 -33 1 -36 1 156
