计算机考研稀疏矩阵精选PPT.ppt
计算机考研稀疏矩阵第1页，此课件共26页哦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页，此课件共26页哦对对 称称 矩矩 阵阵: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第3页，此课件共26页哦例5.3 对称矩阵bbn=5,1+2+3+4+5=5*(5+1)/2=15n=5,1+2+3+4+5=5*(5+1)/2=15bb一维数组SA1.15作为数组A A的存储结构的存储结构:bbSA=(4 4 4 4 5 5 2 2 2 2 3 1 3 3 3 3 2 5 2 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=13 k=5(5-1)/2+3=13bb故:sa13=7 :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=第4页，此课件共26页哦下下三三角角矩矩阵阵:当ij时,aij=0,(1=i,j=j)bb 0 (0 (当 i j)i 1|i-j|1时时,a aijij=0,(1=i,j=n)=0,(1=i,j=n)bb a a11111111 a a1212 0 0.0 0 0.0bb a a21212121 a a a a22222222 a a23232323 0 .0bbAnxn=0 a32323232 a a33333333 a a34343434 .0bb .bb 0 0 0.a 0 0 0.ann-1nn-1nn-1nn-1 a a a annnnnnnnbb一一维维数数组组SA1.3*n-2SA1.3*n-2作作为为数数组组A 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第7页，此课件共26页哦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第8页，此课件共26页哦例5.5 三对角矩阵bb 4 4 4 4 3 3 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 1 0 4 1 0 4 1 0 4 1 0 4 0 0 bb 0 0 0 0 2 8 72 8 72 8 72 8 7bb 0 0 0 0 0 0 9 5 9 5bb一一 维维 数数 组组SA1.3*5-2SA1.3*5-2作作 为为 数数 组组A的存储结构:SA=(SA=(4 4 4 4 3 5 2 2 2 2 2 1 2 1 0 0 0 0 4 2 4 2 8 8 8 8 7 9 7 9 5 5 5 5)bb如如:a5,4=9 a5,4=9bb k=3*(5-1)+4-5+1=12 k=3*(5-1)+4-5+1=12bb故故故故:sa12=9第9页，此课件共26页哦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 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 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的转置的转置第10页，此课件共26页哦稀 疏 矩 阵 的 存 储 结 构 一.三元组顺序表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 bb 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 第11页，此课件共26页哦三元组顺序表结构定义bb#define#define#define#define MAXSIZE 12500MAXSIZE 12500bbtypedef struct typedef struct bb int i,j;int i,j;bb Elemtype e;Elemtype e;bbTriple;Triple;bbtypedef union typedef union bb Triple dataMAXSIZE+1;Triple dataMAXSIZE+1;bb int mu,nu,tu;bbTSMatrix;bbTSMatrix M,T;TSMatrix M,T;M.datap .i .j .e012.maxsize第12页，此课件共26页哦求 稀 疏 矩 阵 M的 转 置 矩 阵 TTSMatrix M,T;012345678012345678M.datap .i .j .eT.dataq .i .j .e第13页，此课件共26页哦求稀疏矩阵M的转置矩阵TbbStatus TransposeSMatrix(TSMatrix M,TSMatrix&T)Status TransposeSMatrix(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 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;+q;T.dataq.e=M.datap.e;+q;bb bb bb retrun OK;retrun OK;bb/TransposeSMatrix/TransposeSMatrix第14页，此课件共26页哦求稀疏矩阵转置的算法复杂度算法复杂度bb其算法复杂度是其算法复杂度是 O(nu*tu)O(nu*tu)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)for(col=1;col=nu;+col)bb for(row=1;row=mu;+row)bb Tcolrow=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 tu mu*nu tu mu*nu 时时,才适用才适用第15页，此课件共26页哦求 稀 疏 矩 阵M的 转 置 矩 阵T的快速方法bb为了减少算法复杂度为了减少算法复杂度,增加两个向量增加两个向量 num num 和和 cpot:cpot:bb numcol:M numcol:M中第中第 col col 列中非零元素的个数列中非零元素的个数;bbcpotcol:Mcpotcol:M中中第第colcol列列中中的的第第一一个个非非零零元元素素在在T.dataT.data中中的位置的位置;bb有有:cpot1=1;:cpot1=1;bb cpotcol=cpotcol-1+numcol-1 cpotcol=cpotcol-1+numcol-1bb 2=col=m.nu第16页，此课件共26页哦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 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 col 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 cpot 1 3 5 7 8 8 9第17页，此课件共26页哦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)numcol=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;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第18页，此课件共26页哦 col 1 2 3 4 5 6 7 col 1 2 3 4 5 6 7 num 2 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第19页，此课件共26页哦求稀疏矩阵转置的快速算法的算法复杂度算法复杂度bb其算法复杂度是其算法复杂度是 O(nu+tu)bb 当tu=mu*nu tu=mu*nu 时,算法复杂度是算法复杂度是 O(nu*mu)O(nu*mu)bb 当当tu mu*nu tu mu*nu 时,时间复杂度将小得多第20页，此课件共26页哦bb#define MAXRC 100#define MAXRC 100bbtypedef struct typedef struct bb int i,j;int i,j;bb Elemtype e;Elemtype e;bbTriple;Triple;bbtypedef struct typedef struct bb Triple dataMAXSIZE+1;Triple dataMAXSIZE+1;bb int rposMAXRC+1;int rposMAXRC+1;bb int mu,nu,tu;int mu,nu,tu;bbRLSMatrix;RLSMatrix;二.行 逻 辑 链 接 的 顺 序 表指出每一行的第一个非零元素在三元组中的位置指出每一行的第一个非零元素在三元组中的位置M.datap .i .j .e012.maxsizeM.rposrow第21页，此课件共26页哦例5.7 矩阵的乘法 Q=M x N Q=M x N M:M:m1 1 x n x n1 1 N:N:m m2 2 x n x n2 2 当当n n1 1=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.rpos 1 2 3row 1 2 3 4N.rpos 1 2 3 5第22页，此课件共26页哦求两个稀疏矩阵的乘积的算法bbQ初始化初始化;bbif(Mif(M和和N N均是非零矩阵均是非零矩阵)bb for(arow=1;arow=M.mu;+arow)bb ctemp=0;bb 计算计算Q中第中第arowarow行的积并存入行的积并存入ctempctemp中;bb 将将ctempctemp中非零元压缩存储到中非零元压缩存储到Q.data;Q.data;bb bb 第23页，此课件共26页哦Status 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可能是非零矩阵 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,ctempccol;/for arow /if return OK;第24页，此课件共26页哦时间复杂度时间复杂度:ctemp ctemp 的时间复杂度是的时间复杂度是 O(M.mu X N.nu);O(M.mu X N.nu);bb求求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时间复杂度是时间复杂度是:bb 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)for(j=1;j=n2;+j)bb Qij=0;Qij=0;bb for(k=1;k=n1;+k)bb Qij+=Mik*Nkj;Qij+=Mik*Nkj;bb /算法复杂度是 O(m1*n1*n2)O(m1*n1*n2)第25页，此课件共26页哦实验与习题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 A=0 -6 0 0 91 0 0 05.21第26页，此课件共26页哦
