数据结构课程设计(稀疏矩阵运算器)

实习报告题目：编制一个稀疏矩阵运算器的程序班级：智能科学与技术系姓名：尤雅萍学号：31520082204064完成日期：2009-11-27一•需求分析1.【问题描述】稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。2.【基本要求】以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵，实现两个矩阵相加，相减和相乘的运算，稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。3.【测试数据】（1）10000001000009+00-1=008-10010-300-3（2）1000010009-0-1=010-101-3-23（3）4-30013000-600008042080000100*010=0100000701000000004.【实现提示】（1）首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行，列数对于所要求作的运算是否匹配，可设矩阵的行数和列数均不超过20。（2）程序可以对三元组的输入顺序加以限制，例如，按行优先。（3）在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放。二•概要设计1.设定数组的抽象数据类型定义：ADTSparseMatrix{数据对象：D={m和n分别称为矩阵的行数和列数}数据关系：R={Row，Col}Row={ai,j，ai,j+1|1=i=m，a=j=n-1}Col={ai,j，ai+1,j|1=i=m-1，a=j=n}基本操作：CreateSMatrix(&M);操作结果：创建稀疏矩阵M。DestorySMatrix(&M);初始条件：稀疏矩阵M存在。操作结果：销毁稀疏矩阵M。PrintSMatrix(M)；初始条件：稀疏矩阵M存在。操作结果:输出稀疏矩阵M。CopySMatrix(M,&T)；初始条件：稀疏矩阵M存在。操作结果：由稀疏矩阵M复制得到T。AddSMatrix(M,N,&Q)；初始条件：稀疏矩阵M与N的行数和列数对应相等。操作结果：求稀疏矩阵的和Q=M+N。SubtSMatrix(M,N,&Q);初始条件：稀疏矩阵M与N的行数和列数对应相等。操作结果：求稀疏矩阵的差Q=M-N。MultSMatrix(M,N,&Q);初始条件：稀疏矩阵M的列数等于N的行数。操作结果：求稀疏矩阵乘积Q=M*N。TransposeSMatrix(M,&T);初始条件：稀疏矩阵M存在。操作结果：求稀疏矩阵M的转置矩阵T。}ADTSparseMatrix2．本程序包含的模块（1）voidmain(){初始化；do{接收命令；处理命令；}while(命令！=退出)；}（2）稀疏矩阵模块——实现稀疏矩阵抽象数据类型。（3）稀疏矩阵求值模块——实现稀疏矩阵求值抽象数据类型。稀疏矩阵求值模块包括：矩阵相加模块AddRLSMatrix()；矩阵相减模块SubRLSMatrix()；相乘模块MulTSMatrix()；三•详细设计typedefstruct//稀疏矩阵的三元组顺序表存储表示inti,j;//该非零元的行下标和列下标inte;}Triple;typedefstruct{Tripledata[MAXSIZE+1];//非零元三元组表，data[0]未用intrpos[MAXRC+1];//各行第一个非零元的位置表intmu,nu,tu;//矩阵的行数列数和非零元的个数}RLSMatrix;VoidCreateSMatrix(RLSMatrix*T)//输入创建稀疏矩阵{intk;printf(\n请输入矩阵行数、列数及非零元个数:);scanf(%d%d%d,&T-mu,&T-nu,&T-tu);printf(\n);if(T-tuMAXSIZE||T-mu21){printf(非零个数超出定义范围！出错！);exit(0);}for(k=1;k=T-tu;k++){printf(请输入第%d个非零元素的行数,列数及其值:,k);scanf(%d%d%d,&T-data[k].i,&T-data[k].j,&T-data[k].e);}}voidAddRLSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix*Q)//稀疏矩阵相加{intp,q,k=1;if(M.mu!=N.mu||M.nu!=N.nu){printf(你的输入不满足矩阵相加的条件!\n);exit(1);}Q-mu=M.mu;Q-nu=M.nu;for(p=1,q=1;p=M.tu&&q=N.tu;){if(M.data[p].i==N.data[q].i){if(M.data[p].j==N.data[q].j){Q-data[k].i=M.data[p].i;Q-data[k].j=M.data[p].j;Q-data[k].e=M.data[p].e+N.data[q].e;p++;q++;k++;}elseif(M.data[p].jN.data[q].j){Q-data[k].i=M.data[p].i;Q-data[k].j=M.data[p].j;Q-data[k].e=M.data[p].e;k++;p++;}elseif(M.data[p].jN.data[q].j){Q-data[k].i=N.data[q].i;Q-data[k].j=N.data[q].j;Q-data[k].e=N.data[q].e;k++;p++;}}elseif(M.data[p].iN.data[q].i){Q-data[k].i=M.data[p].i;Q-data[k].j=M.data[p].j;Q-data[k].e=M.data[p].e;k++;p++;}elseif(M.data[p].iN.data[q].i){Q-data[k].i=N.data[q].i;Q-data[k].j=N.data[q].j;Q-data[k].e=N.data[q].e;k++;q++;}}if(p!=M.tu+1)for(;p=M.tu;p++){Q-data[k].i=M.data[p].i;Q-data[k].j=M.data[p].j;Q-data[k].e=M.data[p].e;k++;}if(q!=N.tu+1)for(;q=N.tu;q++){Q-data[k].i=N.data[q].i;Q-data[k].j=N.data[q].j;Q-data[k].e=N.data[q].e;k++;}}voidSubRLSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix*Q)//稀疏矩阵相减{intp,q,k=1;if(M.mu!=N.mu||M.nu!=N.nu){printf(你的输入不满足矩阵相减的条件!\n);exit(1);}Q-mu=M.mu;Q-nu=M.nu;for(p=1,q=1;p=M.tu&&q=N.tu;){if(M.data[p].i==N.data[q].i){if(M.data[p].j==N.data[q].j){Q-data[k].i=M.data[p].i;Q-data[k].j=M.data[p].j;Q-data[k].e=M.data[p].e-N.data[q].e;p++;q++;k++;}elseif(M.data[p].jN.data[q].j){Q-data[k].i=M.data[p].i;Q-data[k].j=M.data[p].j;Q-data[k].e=M.data[p].e;k++;p++;}elseif(M.data[p].jN.data[q].j){Q-data[k].i=N.data[q].i;Q-data[k].j=N.data[q].j;Q-data[k].e=-N.data[q].e;k++;p++;}}elseif(M.data[p].iN.data[q].i){Q-data[k].i=M.data[p].i;Q-data[k].j=M.data[p].j;Q-data[k].e=M.data[p].e;k++;p++;}elseif(M.data[p].iN.data[q].i){Q-data[k].i=N.data[q].i;Q-data[k].j=N.data[q].j;Q-data[k].e=-N.data[q].e;k++;q++;}}if(p!=M.tu+1)for(;p=M.tu;p++){Q-data[k].i=M.data[p].i;Q-data[k].j=M.data[p].j;Q-data[k].e=M.data[p].e;k++;}if(q!=N.tu+1)for(;q=N.tu;q++){Q-data[k].i=N.data[q].i;Q-data[k].j=N.data[q].j;Q-data[k].e=-N.data[q].e;k++;}}intMulTSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix*Q)//稀疏矩阵相乘{intccol=0,tp,brow,t,arow,p,q,i;intctemp[MAXSIZE+1];if(M.nu!=N.mu){printf(你的输入不满足矩阵相乘的条件!\n);return0;}Q-mu=M.mu;Q-nu=N.nu;Q-tu=0;if(M.tu*N.tu!=0){for(arow=1;arow=M.mu;++arow){for(i=1;i=N.nu;i++)ctemp[i]=0;Q-rpos[arow]=Q-tu+1;if(arowM.mu)tp=M.rpos[arow+1];elsetp=M.tu+1;for(p=M.rpos[arow];ptp;++p){brow=M.data[p].j;if(browN.mu)t=N.rpos[brow+1];elset=N.tu+1;for(q=N.rpos[brow];qt;++q){ccol=N.data[q].j;ctemp[ccol]+=M.data[p].e*N.data[q].e;}}for(ccol=1;ccol=Q-nu;++ccol){if(ctemp[ccol]){if(++Q-tuMAXSIZE)return0;Q-data[Q-tu].i=arow;Q-data[Q-tu].j=ccol;Q-data[Q-tu].e=ctemp[ccol];}}}}return1;}voidPrintSMatrix(RLSMatrixQ)//输出稀疏矩阵{intk=1,row,line;printf(\n运算结果:);if(Q.tu==0)printf(0);else{for(row=1;row=Q.mu;row++){for(line=1;line=Q.nu;line++){if(Q.data[k].i==row&&Q.data[k].j==line)printf(%d,Q.data[k++].e);elseprintf(0);}printf(\n\t);}}}voidmain(){RLSMatrixM,N,Q;inti;do{printf(\t\t***************************\n);printf(\t\t稀疏矩阵运算器\n);printf(\t\t***************************\n\n);printf(\t\t1.矩阵相加\n\n);printf(\t\t2.矩阵相减\n\n);printf(\t\t3.矩阵相乘\n\n);printf(\t\t4.退出\n\n);printf(\t\t请选择:);scanf(%d,