数据结构实验4.doc

实验目的：深入研究数组的存储表示和实现技术，着重掌握对稀疏矩阵的表示方法及其运算的实现。问题描述：稀疏矩阵是指那些多数元素为零的矩阵。利用稀疏特点进行存储和计算可以大大节省存储空间，提高效率。通过对稀疏矩阵的存储表示，实现矩阵的基本操作。实验要求：1、 要求矩阵的输入形式采用三元组表示，以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵。2、 设计矩阵的逆置算法，实现矩阵的逆置。3、 实现两个稀疏矩阵的相加、相减和相乘等运算。4、 要求运算结果的矩阵则以通常的阵列形式出现。文法是一个四元实验内容和过程：输入数据：2 1 00 0 00 0 32 0 01 0 00 0 3-12 1 00 0 00 0 30 0 00 0 00 0 2+=2 1 00 0 00 0 52 1 00 0 30 00 00 2+=0 00 6程序：#include #include using namespace std; const int MAXSIZE=12500; const int MAXRC=10; typedef struct int i,j; int e; Triple; typedef struct Triple dataMAXSIZE+1; int mu,nu,tu; TSMatrix; typedef struct Triple dataMAXSIZE+2; int rposMAXRC+1; int mu,nu,tu; RLSMatrix; template bool InPutTSMatrix(P & T,int y) cout输入矩阵的行列非零元个数y:T.muT.nuT.tu; cout输入非零元的位置和值:endl; int k=1; for(;kT.datak.iT.datak.jT.datak.e; return true; template bool OutPutSMatrix(P T) int m,n,k=1; for(m=0;mT.mu;m+) for(n=0;nT.nu;n+) if(T.datak.i-1)=m&(T.datak.j-1)=n) cout.width(4); coutT.datak+.e; else cout.width(4); cout0; coutendl; return true; bool TransposeSMatrix( ) TSMatrix M,T; InPutTSMatrix(M, 0);int numMAXRC+1; int cpotMAXRC+1;int q,p,t; T.tu=M.tu; T.mu=M.nu; T.nu=M.mu; if(T.tu) for(int col=1;col=M.nu;col+) numcol=0; for(t=1;t=M.tu;t+) +numM.datat.j; cpot1=1; for(int i=2;i=M.nu;i+) cpoti=cpoti-1+numi-1; for(p=1;p=M.tu;p+) int col=M.datap.j; q=cpotcol; T.dataq.i=col; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +cpotcol; cout输入矩阵的转置矩阵为aendl; OutPutSMatrix(T); return true; bool Count(RLSMatrix &T) int numMAXRC+1; int col;for(int col=1;col=T.mu;col+) numcol=0; for(col=1;col=T.tu;col+) +numT.datacol.i; T.rpos1=1; for(int i=2;i=T.mu;i+) T.rposi=T.rposi-1+numi-1; return true; bool MultSMatrix ( ) RLSMatrix M,N,Q; InPutTSMatrix(M,1); InPutTSMatrix(N,1); Count(M); Count(N); if(M.nu!=N.mu) return false; Q.mu=M.mu; Q.nu=N.nu; Q.tu=0; int ctempMAXRC+1; int arow,tp,p,brow,t,q,ccol; if(M.tu*N.tu) for( arow=1;arow=M.mu;arow+) /memset(ctemp,0,N.nu); for(int x=1;x=N.nu;x+) ctempx=0; Q.rposarow=Q.tu+1; if(arowM.mu) tp=M.rposarow+1; else tp=M.tu+1; for(p=M.rposarow;ptp;p+) brow=M.datap.j; if(browN.mu) t=N.rposbrow+1; else t=N.tu+1; for(q=N.rposbrow;qt;q+) ccol=N.dataq.j; ctempccol += M.datap.e*N.dataq.e; for(ccol=1;ccolMAXSIZE) return false; Q.dataQ.tu.e=ctempccol; Q.dataQ.tu.i=arow; Q.dataQ.tu.j=ccol; OutPutSMatrix(Q); return true; bool AddSMatrix() TSMatrix M,N,Q;InPutTSMatrix(M, 2);InPutTSMatrix(N, 2);if(M.mu=0)|(M.nu=0)|(M.tu=0)|(N.mu=0)|(N.nu=0)|(N.tu=0) return 0; if(M.mu!=N.mu|M.nu!=N.nu) return 0; Q.mu=M.mu; Q.nu=M.nu; Q.tu=0; int x=0,y=0; for(int i=1;i=Q.mu;i+) for(int j=1;j=Q.nu;j+) for(int p=1;p=M.tu;p+) if(i=M.datap.i)&(j=M.datap.j) x=M.datap.e; break; else x=0; /for p for(int q=1;q=N.tu;q+) if(i=N.dataq.i)&(j=N.dataq.j) y=N.dataq.e; break; else y=0; if(x+y)!=0) Q.dataQ.tu+1.i=i; Q.dataQ.tu+1.j=j; Q.dataQ.tu+1.e=x+y; Q.tu+; OutPutSMatrix(Q); return 1;int main() cout请选择要进行的操作endl; cout1:矩阵的转置endl; cout2:矩阵的加法endl; cout3:矩