数据结构实验(5).doc

计算机系数据结构实验报告（1）姓名： 孟红波 学号： 6100410179 专业班级： 卓越101班 实验目的：深入研究数组的存储表示和实现技术，着重掌握对稀疏矩阵的表示方法及其运算的实现。问题描述：稀疏矩阵是指那些多数元素为零的矩阵。利用稀疏特点进行存储和计算可以大大节省存储空间，提高效率。通过对稀疏矩阵的存储表示，实现矩阵的基本操作。实验要求：文法是一个四元1、要求矩阵的输入形式采用三元组表示，以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵。2、设计矩阵的逆置算法，实现矩阵的逆置。3、实现两个稀疏矩阵的相加、相减和相乘等运算。4、要求运算结果的矩阵则以通常的数组形式出现。 实验内容和过程：实验步骤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=100; const int MAXROW=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 rposMAXROW+1; int mu,nu,tu; RLSMatrix; template bool InPutTSMatrix(P & T,int y) cout输入矩阵的行，列和非零元素个数: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 numMAXROW+1; int cpotMAXROW+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+) col=M.datap.j; q=cpotcol; T.dataq.i=col; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +cpotcol; cout输入矩阵的转置矩阵为endl; OutPutSMatrix(T); return true; bool Count(RLSMatrix &T) int numMAXROW+1; 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; / Q初始化 int ctempMAXROW+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; typedef struct OLNode int i,j; int e; struct OLNode *right,*down; OLNode,*OLink; typedef struct OLink *rhead,*chead; int mu,nu,tu; CrossList; bool CreateSMatrix_OL(CrossList & M) int x,y,m; cout请输入矩阵的行，列，及非零元素个数M.muM.nuM.tu; if(!(M.rhead=(OLink*)malloc(M.mu+1)*sizeof(OLink) exit(0); if(!(M.chead=(OLink*)malloc(M.nu+1)*sizeof(OLink) exit(0); for(x=0;x=M.mu;x+) M.rheadx=NULL; / for(x=0;x=M.nu;x+) M.cheadx=NULL; cout请按三元组的格式输入数组：endl; for(int i=1;ixym; OLink p,q; if(!(p=(OLink)malloc(sizeof(OLNode) exit(0); p-i=x; p-j=y; p-e=m; if(M.rheadx=NULL|M.rheadx-jy) p-right=M.rheadx; M.rheadx=p; else for(q=M.rheadx;(q-right)&(q-right-jright); p-right=q-right; q-right=p; / 完成行插入 if(M.cheady=NULL|M.cheady-ix) p-down=M.cheady; M.cheady=p; else for(q=M.cheady;(q-down)&(q-down-idown); p-down=q-down; q-down=p; / 完成列插入 return true; bool OutPutSMatrix_OL(CrossList T) for(int i=1;i=T.mu;i+) OLink p=T.rheadi; for(int j=1;jj) coutsetw(3)e; p=p-right; else coutsetw(3)0; coutendl; return true; bool AddSMatrix() CrossList M,N; CreateSMatrix_OL(M); CreateSMatrix_OL(N); cout输入的两矩阵的和矩阵为：endl; OLink pa,pb,pre ,hlMAXROW+1; / for(int x=1;x=M.nu;x+) hlx=M.cheadx; for(int k=1;ke=pb-e; p-i=pb-i; p-j=pb-j; if(NULL=pa|pa-jpb-j) if(NULL=pre) M.rheadp-i=p; else pre-right=p; p-right=pa; pre=p; if(NULL=M.cheadp-j) M.cheadp-j=p; p-down=NULL; else p-down=hlp-j-down; hlp-j-down=p; hlp-j=p; pb=pb-right; else if(NULL!=pa)&pa-jj) pre=pa; pa=pa-right; else if(pa-j=pb-j) pa-e += pb-e; if(!pa-e) if(NULL=pre) M.rheadpa-i=pa-right; else pre-right=pa-right; p=pa; pa=pa-right; if(M.cheadp-j=p) M.cheadp-j=hlp-j=p-down; else hlp-j-down=p-down; free(p); pb=pb-right; else pa=pa-right; pb=pb-right; OutPutSMatrix_OL(M); return true; int main() cout.fill( ); / system(color 0C); cout.fill( ); cout请选择要进行的操作：endl; cout1:矩阵的转置endl; cout2:矩阵的加法或减法endl; cout3:矩阵的乘法endl; cout4:退出程序endl; char c=getchar(); if(c=1) TransposeSMatrix( ); else if(c=2) AddSMatrix(); else if(c=3) MultSMatrix (); / else exit(0); /退出 return 0;实验结果：矩阵的逆置矩阵的加减法矩阵的乘法思考题1、 如何提高矩阵转置算法效率？#include void main(void) const int SIZE=11; int gridSIZESIZE; int gridTSIZESIZE; int i,j; for(i=0;iSIZE;i+) for(j=0;jSIZE;j+) coutInput the Value of i , jgridij; for(i=0;iSIZE;i+) for(j=0;jSIZE;j+) gridTij=gridji; c