《数据结构第五章 第二节》由会员分享,可在线阅读,更多相关《数据结构第五章 第二节(140页珍藏版)》请在金锄头文库上搜索。
1、行逻辑链接的顺序表,typedef structTriple dataMAXSIZE+1; /非零三元组表int rposMAXRC+1; /各行第一个非零元素的位置表int mu, nu, tu; /矩阵的行数,列数和非零元素个数 RLSMatrix;,行逻辑链接的顺序表,typedef structTriple dataMAXSIZE+1; /非零三元组表int rposMAXRC+1; /各行第一个非零元素的位置表int mu,nu,tu; /矩阵的行数,列数和非零元素个数 RLSMatrix;,特点: 随机存取任意一行的非零元,N.data,1,2,3,5,for(i=1; i=m1;
2、 +i)for(j=1; jn2; +j)Qij=0;for(k=1; kn1; +k) Qij+=Mik*Nkj;,一般矩阵相乘,时间复杂度,稀疏矩阵相乘,M.data,N.data,Q.data,稀疏矩阵相乘基本思路,1,i,m,1,rposk,r,k,xrk,r,k,xrk,k,s1,yks1,k,s2,yks2,rposk,k,s1,yks1,r,s1,s2,zrs1,zrs2,M.data,N.data,Q,相乘,相加,稀疏矩阵相乘,M.data,N.data,第一步:找对应元素,numrow=rposrow+1 rposrow,第二步:累积求和,第三步:压缩存储,Q初始化; if(
3、Q是非零矩阵) /逐项求积for(arow=1; arow=M.mu; +arow) /处理M的每一行ctemp =0; /累加器清零计算Q中第arow行的积并存入ctemp 中;将ctemp 中非零元素压缩存储到Q.data; /for arow /if,稀疏矩阵相乘基本思路,M,N,Q,M.data,N.data,Q.data,M,N,Q,M.data,N.data,Q.data,累加值:0 0,处理第 1 行,M,N,Q,M.data,N.data,Q.data,累加值:0 0,处理第 1 行,M,N,Q,M.data,N.data,Q.data,累加值:0 6,处理第 1 行,M,N,
4、Q,M.data,N.data,Q.data,累加值:0 6,处理第 1 行,M,N,Q,M.data,N.data,Q.data,累加值:0 6,处理第 1 行,M,N,Q,M.data,N.data,Q.data,累加值:0 6,处理第 1 行,M,N,Q,M.data,N.data,Q.data,累加值:0 0,处理第 2 行,M,N,Q,M.data,N.data,Q.data,累加值:0 0,处理第 2 行,M,N,Q,M.data,N.data,Q.data,累加值:-1 0,处理第 2 行,M,N,Q,M.data,N.data,Q.data,累加值:-1 0,处理第 2 行,M
5、,N,Q,M.data,N.data,Q.data,累加值:-1 0,处理第 2 行,M,N,Q,M.data,N.data,Q.data,累加值:-1 0,处理第 2 行,M,N,Q,M.data,N.data,Q.data,累加值:0 0,处理第 2 行,M,N,Q,M.data,N.data,Q.data,累加值:0 0,处理第 2 行,M,N,Q,M.data,N.data,Q.data,累加值:0 0,处理第 2 行,M,N,Q,M.data,N.data,Q.data,累加值:0 3,处理第 2 行,M,N,Q,M.data,N.data,Q.data,累加值:0 3,处理第 2
6、行,M,N,Q,M.data,N.data,累加值:0 0,Q.data,处理第 3 行,M,N,Q,M.data,N.data,累加值:0 0,Q.data,处理第 3 行,M,N,Q,M.data,N.data,累加值:0 4,Q.data,处理第 3 行,M,N,Q,M.data,N.data,累加值:0 4,Q.data,处理第 3 行,M,N,Q,M.data,N.data,累加值:-1 4,Q.data,处理第 3 行,M,N,Q,M.data,N.data,累加值:-1 4,Q.data,处理第 3 行,M,N,Q,M.data,N.data,累加值:-1 1,Q.data,处理
7、第 3 行,M,N,Q,M.data,N.data,累加值:-1 1,Q.data,处理第 3 行,Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix /for q/for p, 求得Q中第crow(=arow)行的非零元,for(ccol=1; ccolMAXSIZE) return ERROR;Q.dataQ.tu= arow, ccol, ctempccol ; /if/for arow,处理M的每一行/if (M.tu*N.tu!=0)return OK; /MultSMatrix,Status MultSMatrix(RLSM
8、atrix M, RLSMatrix N, RLSMatrix /for q/求得Q中第crow(=arow)行的非零元,Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix /for q/求得Q中第crow(=arow)行的非零元,Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix /for q/求得Q中第crow(=arow)行的非零元,Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix /for q/求得Q中第crow
9、(=arow)行的非零元,Ctemp=0, 0, Q.tu=0, Q.rpos1=0, arow=1, brow=0, t=0,Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix /for q/求得Q中第crow(=arow)行的非零元,Ctemp=0, 0, Q.tu=0, Q.rpos1=0, arow=1, brow=0, t=0,Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix /for q/求得Q中第crow(=arow)行的非零元,Ctemp=0, 0, Q.tu=
10、0, Q.rpos1=1, arow=1, brow=0, t=0,Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix /for q/求得Q中第crow(=arow)行的非零元,p,Ctemp=0, 0, Q.tu=0, Q.rpos1=1, arow=1, brow=0, t=0,Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix /for q/求得Q中第crow(=arow)行的非零元,p,Ctemp=0, 0, Q.tu=0, Q.rpos1=1, arow=1, brow
11、=1, t=0,Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix /for q/求得Q中第crow(=arow)行的非零元,p,Ctemp=0, 0, Q.tu=0, Q.rpos1=1, arow=1, brow=1, t=2,Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix /for q/求得Q中第crow(=arow)行的非零元,p,q,Ctemp=0, 0, Q.tu=0, Q.rpos1=1, arow=1, brow=1, t=2,Status MultSMatr
12、ix(RLSMatrix M, RLSMatrix N, RLSMatrix /for q/求得Q中第crow(=arow)行的非零元,p,q,Ctemp=0, 0, Q.tu=0, Q.rpos1=1, arow=1, brow=1, t=2,Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix /for q/求得Q中第crow(=arow)行的非零元,p,q,Ctemp=0, 6, Q.tu=0, Q.rpos1=1, arow=1, brow=1, t=2,Status MultSMatrix(RLSMatrix M, RLSMat
13、rix N, RLSMatrix /for q/求得Q中第crow(=arow)行的非零元,p,q,Ctemp=0, 6, Q.tu=0, Q.rpos1=1, arow=1, brow=1, t=2,Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix /for q/求得Q中第crow(=arow)行的非零元,p,q,Ctemp=0, 6, Q.tu=0, Q.rpos1=1, arow=1, brow=1, t=2,Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix /for
14、q/求得Q中第crow(=arow)行的非零元,p,q,Ctemp=0, 6, Q.tu=0, Q.rpos1=1, arow=1, brow=1, t=2,Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix /for q/求得Q中第crow(=arow)行的非零元,p,q,Ctemp=0, 6, Q.tu=0, Q.rpos1=1, arow=1, brow=4, t=2,Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix /for q/求得Q中第crow(=arow)行的非零元,p,q,Ctemp=0, 6, Q.tu=0, Q.rpos1=1, arow=1, brow=4, t=2,