稀疏矩阵转置

1、稀疏矩阵稀疏矩阵所谓稀疏矩阵,是指矩阵中有大部分的值相同或值为零的元素,且这些元素的分布没有规律.00070015000001800000240001400003000000000009120只需存储非零元,或再用一个单元存储值相同的元素 以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题问题:1) 零值元素占了很大空间零值元素占了很大空间;2) 计算中进行了很多和零值的运算，计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零遇除法，还需判别除数是否为零;1) 尽可能少存或不存零值元素;解决问题的原则解决问题的原则:2) 尽可能减少没有实际意义的运算;3) 操作方便; 即: 能尽

2、可能快地找到 与下标值 (i, j) 对应的元素; 能尽可能快地找到 同一行或同一列的非零值元;随机稀疏矩阵的压缩存储方法随机稀疏矩阵的压缩存储方法:一、三元组顺序表一、三元组顺序表二、行逻辑联接的顺序表二、行逻辑联接的顺序表三、三、 十字链表十字链表 类型定义 矩阵转置 稀疏矩阵转置 快速稀疏矩阵转置一、三元组顺序表一、三元组顺序表 #define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型三元组类型一、三元组顺序表一、三元组顺序表typedef union

3、 Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩阵类型稀疏矩阵类型可以这样存储munutu678ije121213931-3361443245218611564-7行数列数元素数值所在行所在列元素值保持行序如何求转置矩阵？如何求转置矩阵？028003600070500140005280000007143600用“三元组”表示时如何实现？1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为: O(munu)

4、for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;多媒体演示 描述稀疏矩阵转置的过程演示在CD实现三元组表存储的稀疏矩阵的转置运算实现三元组表存储的稀疏矩阵的转置运算munutu678ijv121213931-3361443245218611564-7mu nutu768ijv211231913-3631434242518161546-7mu nutu768ijv13-3161521122518319342446-76314munutu678ijv121213931-3361443245218611564

5、-7算法算法1的转置过程的转置过程mu nutu768ijv13-3161521122518319342446-76314算法分析(M-T) q=0; 以原始矩阵的列K(1-M.nu)开始查询并转换 1)从第一列开始,扫描一切非零的数据总数目为M.tu(p=0M.nu-1) M.datap.j=K的话,则将M.datap-T.dataq转换,其中变换其(I,j,data)(j,I,data),并且p+,q+; 如果M.datap.j!=K时,p+ K+; 2)从第二列开始,扫描一切非零的数据总数目为M.tu(p=0M.nu-1) M.datap.j=K的话,则将M.datap-T.dataq转

6、换,其中变换其(I,j,data)(j,I,data),并且p+,q+; 如果M.datap.j!=K时,p+ 规律：循环执行为O(M.nu*M.tu)算法算法1:按照矩阵A的列序进行转置Status TransposeSMatrix(TSMatrix M,TSMatrix &T)T.mu=M.nu; T.nu=M.mu;T.tu=M.tu;if(T.tu)q:=1;for(col=0 ;col=M.nu;col+)for（ p=1；p=M.tu;p+) if (M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.

7、e=M.datap.e;q+;return OK;/ TransposeSMatrix 首先应该确定转置矩阵中每一行的第一个非零元在三元组中的位置每一行的第一个非零元在三元组中的位置。1 2 151 5 -52 2 -73 1 363 4 28 col12345Numpos12011Cpotcol12445 cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1;Col = M.datap.j;q = cpotcol;T.dataq.i = M.datap.j;T.dataq.j = M.datap.i;T.d

8、ataq.e = M.datap.e;+cpotcol描述快速转置算法 见电子书22-42页参考课件 分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为时间复杂度为: : O(M.nu+M.tu)for (col=1; col=M.nu; +col) for (t=1; t=M.tu; +t) for (col=2; col=M.nu; +col) for (p=1; p=M.tu; +p) Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu = M.nu; T.nu = M.mu; T.tu =

9、M.tu; if (T.tu) for (col=1; col=M.nu; +col) numcol = 0; for (t=1; t=M.tu; +t) +numM.datat.j; cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; for (p=1; p=M.tu; +p) / if return OK; / FastTransposeSMatrix 转置矩阵元素 三元组顺序表又称有序的双下标有序的双下标法法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序便于进行依行顺序处理的矩阵运算

10、处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。二、行逻辑联接的顺序表二、行逻辑联接的顺序表 #define MAXMN 500 typedef struct Triple dataMAXSIZE + 1; int rposMAXMN + 1; int mu, nu, tu; RLSMatrix; / 行逻辑链接顺序表类型 修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos, 其值在稀疏矩阵的初始化函数中确定。例如：给定一组下标，求矩阵的元素值ElemType value(RLSMatrix M, int r, int c) p = M.rposr; while

11、(M.datap.i=r &M.datap.j c) p+; if (M.datap.i=r & M.datap.j=c) return M.datap.e; else return 0; / value矩阵乘法的精典算法矩阵乘法的精典算法: for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; 其时间复杂度为其时间复杂度为: O(m1n2n1) for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij=0; for(k(0-n1

12、-1) Qij+=Mik*Nkj稀疏矩阵相乘的规则对于M,N矩阵求出其Rpos值从M.mu行开始运算（arow) M.datap.j N.data.i= M.datap.j M的第arrow行的所有非零 P:M.rposarrow. M.rposarrow+1-1 M.datap.j 列 N的M.datap.j 行的非零元素乘 与 求出以此列为N的行号的所有非零元素 出. Q初始化; if Q是非零矩阵 / 逐行求积 for (arow=1; arow=M.mu; +arow) / 处理M的每一行 ctemp = 0; / 累加器清零 计算Q中第arow行的积并存入ctemp 中； 将ctem

13、p 中非零元压缩存储到Q.data； / for arow / if 两个稀疏矩阵相乘（两个稀疏矩阵相乘（Q M N） 的过程可大致描述如下：的过程可大致描述如下： Status MultSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix &Q) if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; if (M.tu*N.tu != 0) / Q是非零矩阵 for (arow=1; arow=M.mu; +arow) / 处理M的每一行 / for arow / if

14、 return OK; / MultSMatrix ctemp = 0; / 当前行各元素累加器清零 Q.rposarow = Q.tu+1; for (p=M.rposarow; pM.rposarow+1;+p) /对当前行中每一个非零元 brow=M.datap.j; if (brow N.nu ) t = N.rposbrow+1; else t = N.tu+1 for (q=N.rposbrow; q t; +q) ccol = N.dataq.j; / 乘积元素在Q中列号 ctempccol += M.datap.e * N.dataq.e; / for q / 求得Q中第crow( =arow)行的非零元 for (ccol=1; ccol MAXSIZE) return ERROR; Q.dataQ.tu = arow, ccol, ctempccol; / if处理 的每一行M分析上述算法的时间复杂度分析上述算法的时间复杂度累加器ctemp初始化的时间复杂度为(M.muN.nu)，求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu)，进行压缩存储的时间复杂度为(M.muN.nu)，总的时间复杂度就是总的时间复杂度就是