《计算机考研稀疏矩阵精选文档.ppt》由会员分享，可在线阅读，更多相关《计算机考研稀疏矩阵精选文档.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机考研稀疏矩阵本讲稿第一页，共二十六页5.3.1 特殊矩阵bb对称矩阵对称矩阵对称矩阵对称矩阵:a aijij=a=ajiji(1=i,j=n)(1=i,j=n)bb下三角矩阵下三角矩阵下三角矩阵下三角矩阵:当当ijij时时,aij=0,(1=i,j=n)aij=0,(1=i,j 1|i-j|1时时,a aijij=0,(1=i,j=n)=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=本讲稿第二页，
2、共二十六页对对 称称 矩矩 阵阵:aij=aji(1=i,j=ji=jbb k=k=k=k=bb j(j-1)/2+i j(j-1)/2+i j(j-1)/2+i j(j-1)/2+i 当当 i ji j本讲稿第三页，共二十六页例5.3 对称矩阵bbn=5,1+2+3+4+5=5*(5+1)/2=15bb一维数组一维数组SA1.15作为数组作为数组A A的存储结构的存储结构:bbSA=(SA=(4 4 5 2 2 3 1 3 3 2 5 2 8 8 1 6 7 9 1 6 7 9 5 5 5 5)bb如:a5,3=a3,5=7bb k=5(5-1)/2+3=13bb故:sa13=7 :sa13
3、=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=本讲稿第四页，共二十六页下下三三角角矩矩阵阵:当ij时,aij=0,(1=i,j=j)i=j)bb 0 (0 (当当 i 1|i-j|1时时,a aij=0,(1=i,j=n)=0,(1=i,j=n)bb a a11111111 a1212 0 0.0 0 0.0bb a2121 a a2222 a23232323 0 .0 0 .0bbAnxn=0 a3232 a a3333 a343434
4、34 .0bb .bb 0 0 0.a 0 0 0.ann-1nn-1 a annnnnnnnbb一一维维数数组组SA1.3*n-2作为数组A下三角元素的存储结构:bbSAk=SAk=a a a a11111111,a,a12121212,a,a21212121,a a a a22222222,a,a23232323,a,a32323232,a a a a33333333,a,a34343434,.,a,.,ann-1nn-1nn-1nn-1,a a a annnnnnnn bb k =1 2 3 4 5 6 7 8 3n-3 3n-2k =1 2 3 4 5 6 7 8 3n-3 3n-2本
5、讲稿第七页，共二十六页bbsaksak和和ai,jai,j的一一对应关系的一一对应关系:bb sak,k=3*(i-1)+j-i+1,sak,k=3*(i-1)+j-i+1,sak,k=3*(i-1)+j-i+1,sak,k=3*(i-1)+j-i+1,bbai,j=ai,j=ai,j=ai,j=当当|i-j|=1|i-j|1|i-j|1本讲稿第八页，共二十六页例5.5 三对角矩阵bb 4 4 3 3 0 0 0 0 0 0 bb 5 2 2 5 2 2 5 2 2 5 2 2 0 0bb A=0 A=0 1 0 4 1 0 4 0 0 bb 0 0 0 0 2 8 72 8 7bb 0 0
6、0 9 5 9 5 9 5 9 5bb一维数组SA1.3*5-2作作为为数数组组A的的存存储储结结构构:SA=(SA=(4 4 4 4 3 5 3 5 2 2 2 2 2 1 0 0 4 2 4 2 8 8 7 9 5 5 5 5)bb如如:a5,4=9bb k=3*(5-1)+4-5+1=12bb故故故故:sa12=9sa12=9本讲稿第九页，共二十六页5.3.2 5.3.2 稀疏矩阵 通常稀疏因子稀疏因子0.05时称为稀疏矩阵.bb例例5.6 5.6 bb 0 12 9 0 0 0 0 0 0-3 0 0 15 0 12 9 0 0 0 0 0 0-3 0 0 15bb 0 0 0 0 0
7、 0 0 12 0 0 0 18 0 0 0 0 0 0 0 0 12 0 0 0 18 0bbM=-3 0 0 0 0 14 0 9 0 0 24 0 0M=-3 0 0 0 0 14 0 9 0 0 24 0 0bb 0 0 24 0 0 0 0 T=0 0 0 0 0-7 0 0 24 0 0 0 0 T=0 0 0 0 0-7bb 0 18 0 0 0 0 0 0 0 0 0 0 0 0 18 0 0 0 0 0 0 0 0 0 0 0bb 15 0 0-7 0 0 0 0 0 14 0 0 0 15 0 0-7 0 0 0 0 0 14 0 0 0bb 0 0 0 0 0 0 0 0
8、 0 0 0 0bbM:mu x nu(6x7)M:mu x nu(6x7)bbT:nu x mu(7x6)T:nu x mu(7x6)bbM M是是T T的转置的转置本讲稿第十页，共二十六页稀疏矩阵的存储结构 一.三元组顺序表bb M:i j e T:i j eM:i j e T:i j eM:i j e T:i j eM:i j e T:i j ebb 1 2 12 1 3 -3 1 2 12 1 3 -3 bb 1 3 9 1 6 15 1 3 9 1 6 15 bb 3 1 -3 2 1 12 3 1 -3 2 1 12 bb 3 6 14 2 5 18 3 6 14 2 5 18 b
9、b 4 3 24 3 1 9 4 3 24 3 1 9 bb 5 2 18 3 4 24 5 2 18 3 4 24 bb 6 1 15 4 6 -7 6 1 15 4 6 -7 bb 6 4 -7 6 3 14 6 4 -7 6 3 14 本讲稿第十一页，共二十六页三元组顺序表结构定义bb#define#define MAXSIZE 12500bbtypedef struct bb int i,j;bb Elemtype e;bbTriple;bbtypedef union bb Triple dataMAXSIZE+1;Triple dataMAXSIZE+1;bb int mu,nu,t
10、u;bbTSMatrix;bbTSMatrix M,T;M.datap .i .j .e012.maxsize本讲稿第十二页，共二十六页求 稀 疏 矩 阵 M的 转 置 矩 阵 TTSMatrix M,T;012345678012345678M.datap .i .j .eT.dataq .i .j .e本讲稿第十三页，共二十六页求稀疏矩阵M的转置矩阵TbbStatus TransposeSMatrix(TSMatrix M,TSMatrix&T)Status TransposeSMatrix(TSMatrix M,TSMatrix&T)bb T.mu=M.nu;T.nu=M.mu;T.tu=
11、M.tu;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;bb if(T.tu)if(T.tu)bb q=1;q=1;bb for(col=1;col=M.nu;+col)for(col=1;col=M.nu;+col)bb for(p=1;p=M.tu;+p)for(p=1;p=M.tu;+p)bb if(M.datap.j=col)if(M.datap.j=col)bb T.dataq.i=M.datap.j;T.dataq.i=M.datap.j;bb T.dataq.j=M.datap.i;T.dataq.j=M.datap.i;bb T.dataq.e=M.datap.e
12、;+q;T.dataq.e=M.datap.e;+q;bb bb bb retrun OK;retrun OK;bb/TransposeSMatrix/TransposeSMatrix本讲稿第十四页，共二十六页求稀疏矩阵转置的算法复杂度算法复杂度bb其算法复杂度是其算法复杂度是 O(nu*tu)O(nu*tu)bb而一般矩阵的转置算法的复杂度是而一般矩阵的转置算法的复杂度是O(mu*nu):O(mu*nu):O(mu*nu):O(mu*nu):bb for(col=1;col=nu;+col)bb for(row=1;row=mu;+row)for(row=1;row=mu;+row)bb T
13、colrow=Mrowcol;Tcolrow=Mrowcol;bb所以所以,当tu=mu*nu tu=mu*nu tu=mu*nu tu=mu*nu 时时,bb 算法复杂度是 O(nu*nu*mu)O(nu*nu*mu)O(nu*nu*mu)O(nu*nu*mu)bb 当tu mu*nu tu mu*nu 时时,才适用才适用本讲稿第十五页，共二十六页求 稀 疏 矩 阵M的 转 置 矩 阵T的快速方法bb为了减少算法复杂度,增加两个向量增加两个向量 num 和和 cpot:cpot:bb numcol:M中第中第 col col 列中非零元素的个数列中非零元素的个数;bbcpotcol:Mcpo
14、tcol:M中第col列列中中的的第第一一个个非非零零元元素素在在T.data中中的位置的位置;bb有:cpot1=1;bb cpotcol=cpotcol-1+numcol-1 cpotcol=cpotcol-1+numcol-1bb 2=col=m.nu 2=col=m.nu本讲稿第十六页，共二十六页bb例例5.6 5.6 bb 0 12 9 0 0 0 0 0 0-3 0 0 15 0 12 9 0 0 0 0 0 0-3 0 0 15bb 0 0 0 0 0 0 0 12 0 0 0 18 0 0 0 0 0 0 0 0 12 0 0 0 18 0bbM=-3 0 0 0 0 14 0
15、 9 0 0 24 0 0M=-3 0 0 0 0 14 0 9 0 0 24 0 0bb 0 0 24 0 0 0 0 T=0 0 0 0 0-7 0 0 24 0 0 0 0 T=0 0 0 0 0-7bb 0 18 0 0 0 0 0 0 0 0 0 0 0 0 18 0 0 0 0 0 0 0 0 0 0 0bb 15 0 0-7 0 0 0 0 0 14 0 0 0 15 0 0-7 0 0 0 0 0 14 0 0 0bb 0 0 0 0 0 0 0 0 0 0 0 0bb例5.65.6的向量 num num 和和 cpot:cpot:bb col 1 2 3 4 5 6 7 co
16、l 1 2 3 4 5 6 7 bb num 2 2 2 1 0 1 0 num 2 2 2 1 0 1 0bb cpot 1 3 5 7 8 8 9本讲稿第十七页，共二十六页bbStatus FastTransposeSMatrix(TSMatrix M,TSMatrix&T)Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)bb T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;bb if(T.tu)if(T.tu)bb for(col=1;col=M.nu;+col)n
17、umcol=0;for(col=1;col=M.nu;+col)numcol=0;bb for(t=1;t=M.tu;+t)+numM.datat.j;for(t=1;t=M.tu;+t)+numM.datat.j;bb cpot1=1;cpot1=1;bb for(col=2;col=M.nu;+col)for(col=2;col=M.nu;+col)bb cpotcol=cpotcol-1+numcol-1;cpotcol=cpotcol-1+numcol-1;bb for(p=1;p=M.tu;+p)for(p=1;p=M.tu;+p)bb col=M.datap.j;q=cpotcol
18、;col=M.datap.j;q=cpotcol;bb T.dataq.i=M.datap.j;T.dataq.i=M.datap.j;bb T.dataq.j=M.datap.i;T.dataq.j=M.datap.i;bb T.dataq.e=M.datap.e;+cpotcol;T.dataq.e=M.datap.e;+cpotcol;bb bb bb retrun OK;retrun OK;bb/FastTransposeSMatrix/FastTransposeSMatrix本讲稿第十八页，共二十六页 col 1 2 3 4 5 6 7 col 1 2 3 4 5 6 7 num 2
19、 2 2 1 0 1 0 num 2 2 2 1 0 1 0 cpot 1 3 5 7 8 8 9 cpot 1 3 5 7 8 8 9012345678M.datap .i .j .e012345678T.dataq .i .j .e本讲稿第十九页，共二十六页求稀疏矩阵转置的快速算法的算法复杂度算法复杂度bb其算法复杂度是其算法复杂度是 O(nu+tu)bb 当tu=mu*nu 时,算法复杂度是算法复杂度是 O(nu*mu)O(nu*mu)bb 当tu mu*nu 时时,时间复杂度将小得多时间复杂度将小得多本讲稿第二十页，共二十六页bb#define MAXRC 100bbtypedef s
20、truct typedef struct bb int i,j;bb Elemtype e;Elemtype e;bbTriple;Triple;bbtypedef struct typedef struct bb Triple dataMAXSIZE+1;bb int rposMAXRC+1;bb int mu,nu,tu;int mu,nu,tu;bbRLSMatrix;二.行 逻 辑 链 接 的 顺 序 表指出每一行的第一个非零元素在三元组中的位置指出每一行的第一个非零元素在三元组中的位置M.datap .i .j .e012.maxsizeM.rposrow本讲稿第二十一页，共二十六页
21、例5.7 矩阵的乘法 Q=M x N Q=M x N Q=M x N Q=M x N M:M:M:M:m1 x n x n1 1 N:N:m m2 2 x n2 当当n n1 1=m=m2 2时时 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 1 2 3Q.r
22、pos 1 2 3row 1 2 3 4N.rpos 1 2 3 5本讲稿第二十二页，共二十六页求两个稀疏矩阵的乘积的算法bbQ初始化初始化;bbif(Mif(M和N均是非零矩阵均是非零矩阵)bb for(arow=1;arow=M.mu;+arow)bb ctemp=0;ctemp=0;bb 计算计算Q Q中第中第arow行的积并存入行的积并存入ctempctemp中中;bb 将ctemp中非零元压缩存储到Q.data;bb bb 本讲稿第二十三页，共二十六页Status MultiSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix&Q)if(M.nu!=N.
23、mu)return ERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;/Q初始化;if(M.tu*N.tu!=0)/Q可能是非零矩阵 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;/
24、for p for(ccol=1;ccol MAXSIZE)return ERROR;Q.dataQ.tu=arow,ccol,ctempccol;/for arow /if return OK;本讲稿第二十四页，共二十六页时间复杂度时间复杂度:ctemp 的时间复杂度是 O(M.mu X N.nu);O(M.mu X N.nu);bb求Q Q所有非零元的时间复杂度是所有非零元的时间复杂度是bb O(M.tu X N.tu/N.mu);O(M.tu X N.tu/N.mu);bb压缩存储的时间复杂度是压缩存储的时间复杂度是O(M.tu X N.tu/N.mu);bb时间复杂度是时间复杂度是:b
25、b O(M.mu X N.nu+M.tu X N.tu/N.mu);O(M.mu X N.nu+M.tu X N.tu/N.mu);bbfor(i=1;i=m1;+i)for(i=1;i=m1;+i)bb for(j=1;j=n2;+j)bb Qij=0;bb for(k=1;k=n1;+k)bb Qij+=Mik*Nkj;bb /算法复杂度是 O(m1*n1*n2)本讲稿第二十五页，共二十六页实验与习题bb理论习题 5.6,5.7,5.8,5.9bb实验题:写一个主程序来写一个主程序来上机验证上机验证求稀疏矩阵求稀疏矩阵M M的转置矩阵的转置矩阵T T的快的快速方法速方法的存储结构；并计算的存储结构；并计算A A的转置 15 0 0 22 15 0 0 22 A=0 -6 0 0 91 0 0 0 91 0 0 0 5.215.21本讲稿第二十六页，共二十六页