计算机考研稀疏矩阵.ppt

《计算机考研稀疏矩阵.ppt》由会员分享，可在线阅读，更多相关《计算机考研稀疏矩阵.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、5.3 矩阵的压缩存储b矩阵矩阵:二维数组b特殊矩阵特殊矩阵:大量重复元素或大量0元素 b稀疏矩阵稀疏矩阵:大量0元素 b压压缩缩存存储储:重复元素只分配一个存储空间,0元素不分配存储空间5.3.1 特殊矩阵b对称矩阵对称矩阵:aij=aji(1=i,j=n)b下三角矩阵下三角矩阵:当ij时,aij=0,(1=i,j 1时,aij=0,(1=i,j=n)a a1111 a1212 a1313.a1n1n a2121 a a2222 a2323.a2n2n a3131 a3232 a a3333.a3n3n .an1n1 an2n2 an3n3.a annnnAnxn=对对称称矩矩阵阵:aij=

2、aji(1=i,j=jb k=k=b j(j-1)/2+i j(j-1)/2+i 当 i j例5.3 对称矩阵bn=5,1+2+3+4+5=5*(5+1)/2=15b一维数组SA1.15作为数组A的存储结构:bSA=(4 4 5 2 2 3 1 3 3 2 5 2 8 8 1 6 7 9 5 5)b如:a5,3=a3,5=7b k=5(5-1)/2+3=13b故:sa13=7 4 4 5 3 2 15 2 2 1 5 63 1 3 3 2 72 5 2 8 8 91 6 7 9 5 5A=4 4 5 2 2 03 1 3 3 2 5 2 8 8 1 6 7 9 5 5A=下下三三角角矩矩阵阵:

3、当ij时,aij=0,(1=i,j=j)b 0 (0 (当 i 1时,aij=0,(1=i,j=n)b a a1111 a1212 0 0.0b a2121 a a2222 a2323 0 .0bAnxn=0 a3232 a a3333 a3434 .0b .b 0 0 0.annnn-1-1 a annnnb一维数组SA1.3*n-2作为数组A下三角元素的存储结构:bSAk=a a1111,a1212,a2121,a a2222,a2323,a3232,a a3333,a3434,.,annnn-1-1,a annnnb k =1 2 3 4 5 6 7 8 3n-3 3n-2bsak和ai

4、,j的一一对应关系:b sasak,k=3*(i-1)+j-i+1,k,k=3*(i-1)+j-i+1,bai,j=ai,j=当|i-j|1例5.5 三对角矩阵b 4 4 3 3 0 0 0 b 5 2 2 5 2 2 0 0b A=0 1 0 4 1 0 4 0 b 0 0 2 8 72 8 7b 0 0 0 9 5 9 5b一维数组SA1.3*5-2作为数组A的存储结构:SA=(4 4 3 5 2 2 2 1 0 0 4 2 8 8 7 9 5 5)b如如:a5,4=9b k=3*(5-1)+4-5+1=12b故故:sa12=95.3.2 5.3.2 稀疏矩阵 通常稀疏因子稀疏因子0.05

5、时称为稀疏矩阵.b例5.6 b 0 12 9 0 0 0 0 0 0-3 0 0 15b 0 0 0 0 0 0 0 12 0 0 0 18 0bM=-3 0 0 0 0 14 0 9 0 0 24 0 0b 0 0 24 0 0 0 0 T=0 0 0 0 0-7b 0 18 0 0 0 0 0 0 0 0 0 0 0b 15 0 0-7 0 0 0 0 0 14 0 0 0b 0 0 0 0 0 0bM:mu x nu(6x7)bT:nu x mu(7x6)bM是T的转置稀 疏 矩 阵 的 存 储 结 构 一.三元组顺序表b M:i j e T:i j eM:i j e T:i j eb

6、1 2 12 1 3 -3 b 1 3 9 1 6 15 b 3 1 -3 2 1 12 b 3 6 14 2 5 18 b 4 3 24 3 1 9 b 5 2 18 3 4 24 b 6 1 15 4 6 -7 b 6 4 -7 6 3 14 三元组顺序表结构定义b#define define MAXSIZE 12500btypedef struct b int i,j;b Elemtype e;bTriple;btypedef union b Triple dataMAXSIZE+1;b int mu,nu,tu;bTSMatrix;bTSMatrix M,T;M.datap .i .j

7、 .e012.maxsize求 稀 疏 矩 阵 M的 转 置 矩 阵 TTSMatrix M,T;012345678012345678M.datap .i .j .eT.dataq .i .j .e求稀疏矩阵M的转置矩阵TbStatus TransposeSMatrix(TSMatrix M,TSMatrix&T)b T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;b if(T.tu)b q=1;b for(col=1;col=M.nu;+col)b for(p=1;p=M.tu;+p)b if(M.datap.j=col)b T.dataq.i=M.datap.j;b T.dat

8、aq.j=M.datap.i;b T.dataq.e=M.datap.e;+q;b b b retrun OK;b/TransposeSMatrix求稀疏矩阵转置的算法复杂度算法复杂度b其算法复杂度是 O(O(nunu*tutu)b而一般矩阵的转置算法的复杂度是O(O(mumu*nunu):):b for(col=1;col=nu;+col)b for(row=1;row=mu;+row)b Tcolrow=Mrowcol;b所以,当tutu=mu mu*nu nu 时,b 算法复杂度是 O(O(nunu*nunu*mumu)b 当tutu mu mu*nu nu 时,才适用求 稀 疏 矩 阵

9、 M的 转 置 矩 阵 T的快速方法b为了减少算法复杂度,增加两个向量 num 和 cpot:b numcol:M中第 col 列中非零元素的个数;bcpotcol:M中第col列中的第一个非零元素在T.data中的位置;b有:cpot1=1;b cpotcol=cpotcol-1+numcol-1b 2=col=m.nub例5.6 b 0 12 9 0 0 0 0 0 0-3 0 0 15b 0 0 0 0 0 0 0 12 0 0 0 18 0bM=-3 0 0 0 0 14 0 9 0 0 24 0 0b 0 0 24 0 0 0 0 T=0 0 0 0 0-7b 0 18 0 0 0

10、0 0 0 0 0 0 0 0b 15 0 0-7 0 0 0 0 0 14 0 0 0b 0 0 0 0 0 0b例5.6的向量 num 和 cpot:b col 1 2 3 4 5 6 7 b num 2 2 2 1 0 1 0b cpot 1 3 5 7 8 8 9bStatus FastTransposeSMatrix(TSMatrix M,TSMatrix&T)b T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;b if(T.tu)b for(col=1;col=M.nu;+col)numcol=0;b for(t=1;t=M.tu;+t)+numM.datat.j;b

11、cpot1=1;b for(col=2;col=M.nu;+col)b cpotcol=cpotcol-1+numcol-1;b for(p=1;p=M.tu;+p)b col=M.datap.j;q=cpotcol;b T.dataq.i=M.datap.j;b T.dataq.j=M.datap.i;b T.dataq.e=M.datap.e;+cpotcol;b b b retrun OK;b/FastTransposeSMatrix col 1 2 3 4 5 6 7 num 2 2 2 1 0 1 0 cpot 1 3 5 7 8 8 9012345678M.datap .i .j

12、.e012345678T.dataq .i .j .e求稀疏矩阵转置的快速算法的算法复杂度算法复杂度b其算法复杂度是 O(nu+tu)b 当 tu=mu*nu 时,算 法 复 杂 度 是 O(nu*mu)b 当tu mu*nu 时,时间复杂度将小得多b#define MAXRC 100btypedef struct b int i,j;b Elemtype e;bTriple;btypedef struct b Triple dataMAXSIZE+1;b int rposMAXRC+1;b int mu,nu,tu;bRLSMatrix;二.行 逻 辑 链 接 的 顺 序 表指出每一行的第一

13、个非零元素在三元组中的位置M.datap .i .j .e012.maxsizeM.rposrow例5.7 矩阵的乘法 Q=M x N Q=M x N M:M:m1 x n1 N:N:m2 x n2 当n1=m2时 3 0 0 5 0 2 0 6M=0 -1 0 0 N=1 0 Q=-1 0 2 0 0 0 -2 4 0 4 0 0M.data N.data Q.data i j e i j e i j e 1 1 3 1 2 2 1 2 6 1 4 5 2 1 1 2 1 -1 2 2 -1 3 1 -2 3 2 4 3 1 2 3 2 4 row 1 2 3M.rpos 1 3 4 row

14、 1 2 3Q.rpos 1 2 3row 1 2 3 4N.rpos 1 2 3 5求两个稀疏矩阵的乘积的算法bQ初始化;bif(M和N均是非零矩阵)b for(arow=1;arow=M.mu;+arow)b ctemp=0;b 计算Q中第arow行的积并存入ctemp中;b 将ctemp中非零元压缩存储到Q.data;b bStatus MultiSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix&Q)if(M.nu!=N.mu)return ERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;/Q初始化;if(M.tu*N.tu!=0)/Q

15、可能是非零矩阵 for(arow=1;arow=M.mu;+arow)ctemp=0;Q.rposarow=Q.tu +1；for(p=M.rposarow;pM.rposarow+1;+p)brow=M.datap.j;if(brow N.nu/*N.mu?*/)t=N.rposbrow+1;else t=N.tu+1;for(q=N.rposbrow;q t;+q)ccol=N.dataq.j;ctempccol+=M.datap.e*N.dataq.e;/for p for(ccol=1;ccol MAXSIZE)return ERROR;Q.dataQ.tu=arow,ccol,cte

16、mpccol;/for arow /if return OK;时间复杂度时间复杂度:ctemp 的时间复杂度是 O(M.mu X N.nu);b求Q所有非零元的时间复杂度是b O(M.tu X N.tu/N.mu);b压缩存储的时间复杂度是O(M.tu X N.tu/N.mu);b时间复杂度是:b O(M.mu X N.nu+M.tu X N.tu/N.mu);bfor(i=1;i=m1;+i)b for(j=1;j=n2;+j)b Qij=0;b for(k=1;k=n1;+k)b Qij+=Mik*Nkj;b /算法复杂度是 O(m1*n1*n2)实验与习题bb理论习题 5.6,5.7,5.8,5.9b实验题:写一个主程序来上机验证求稀疏矩阵M的转置矩阵T的快速方法的存储结构；并计算A的转置 15 0 0 22 A=0 -6 0 0 91 0 0 05.21