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

实习4、稀疏矩阵运算器一、需求分析1.问题描述稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。2.基本要求以带“行逻辑连接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵的相加、相减和相乘运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。3.实现提示(1)首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否匹配。可设聚矩阵的行数和列数不超过20。(2)程序可以对三元组的输入顺序加以限制，例如，按行优先。注意研究教科书5.3.2节中的算法，以便提高计算效率。(3)在用三元组表示稀疏矩阵时，相加或相减所得的结果矩阵应该另生成，乘积矩阵也可以用二维数组存放。二、概要设计ADTSparseMatrix{数据对象：D={aij|i=1,2,3……m;j=1,2,3……n;ai,j∈intSet,m和n分别称为矩阵的行数和列数}数据关系：R={Row,col}Row={ai,j,ai,j+1|1≤i≤m，1≤j≤n-1}Col={ai,j,ai,j+1|1≤i≤m-1，1≤j≤n}基本操作：CreateSMatrix(*T);操作结果：创建稀疏矩阵T。AddRLSMatrix(M,N,*Q);初始条件：稀疏矩阵M和N的行数列数对应相等。操作结果：求稀疏矩阵的和Q=M+N。SubRLSSMatrix(M,N,*Q);初始条件：稀疏矩阵M和N的行数列数对应相等。操作结果：求稀疏矩阵的差Q=M-N。SMatrixrpos(*T)初始条件：稀疏矩阵T存在。操作结果：求稀疏矩阵的各行第一个非零元的位置表。MulTSMatrix(M,N,*Q);初始条件：稀疏矩阵M的列数与N的行数对应相等。操作结果：求稀疏矩阵的乘积Q=M*N;PrintSMatrix(RLSMatrixQ)初始条件：稀疏矩阵Q存在。操作结果：输出稀疏矩阵Q。DestorySMatrix(T);初始条件：稀疏矩阵T存在。操作结果：销毁稀疏矩阵T。}ADTSparseMatrix三、详细设计（源代码）（使用C语言）#includestdio.h#includestdlib.h#defineMAXSIZE400//矩阵非零元个数的最大值为400#defineMAXRC20//矩阵的行数（列数）的最大值为20typedefstruct{//稀疏矩阵的三元组顺序表存储表示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-mu20||T-nu20){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);}}intAddRLSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix*Q){//稀疏矩阵的加法运算，运算失败返回0intp,q,k=0;if(M.mu!=N.mu||M.nu!=N.nu)//传入的稀疏矩阵不符合加法运算条件return0;Q-mu=M.mu;Q-nu=M.nu;k++;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++;}Q-tu=k;return1;}intSubRLSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix*Q){//稀疏矩阵的减法运算，运算失败返回0if(M.mu!=N.mu||M.nu!=N.nu)//传入的稀疏矩阵不符合加法运算条件return0;inti;for(i=1;i=N.tu;i++)//将稀疏矩阵N的非零元置为其各自的相反数{N.data[i].e=-N.data[i].e;}returnAddRLSMatrix(M,N,Q);//调用稀疏矩阵的加法运算函数}voidSMatrixrpos(RLSMatrix*T){//求稀疏矩阵的各行第一个非零元的位置表intnum[20],col,t;//num[col]为各行非零元的个数for(col=1;col=T-mu;++col)num[col]=0;for(t=1;t=T-tu;++t)//计算各行非零元的个数++num[T-data[t].i];T-rpos[1]=1;for(col=2;col=T-mu;++col)//求各行第一个非零元的位置表T-rpos[col]=T-rpos[col-1]+num[col-1];}intMulTSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix*Q){//稀疏矩阵的乘法运算，采用逻辑连接存储表示，运算失败返回0intccol=0,tp,brow,t,arow,p,q,i;intctemp[MAXSIZE+1];if(M.nu!=N.mu)return0;//求各稀疏矩阵的各行第一个非零元的位置表SMatrixrpos(&M);SMatrixrpos(&N);//Q初始化Q-mu=M.mu;Q-nu=N.nu;Q-tu=0;if(M.tu*N.tu!=0)//Q是非零矩阵{for(arow=1;arow=M.mu;++arow)//处理M的每一行{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){//对当前行中每一个非零元找到对应元在N中的行号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;//乘积元素在Q中的列号ctemp[ccol]+=M.data[p].e*N.data[q].e;}}//求得Q中第arow行的非零元for(ccol=1;ccol=Q-nu;++ccol)//压缩存储该行非零元{if(ctemp[ccol]){Q-tu++;if(Q-tuMAXSIZE)return0;else{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);}}}voidDestroySMatrix(RLSMatrix*T){//销毁稀疏矩阵TT-mu=0;T-nu=0;T-tu=0;}intmain(){//主函数RLSMatrixM,N,Q;charc;//输出菜单printf(*******************************************************\n);printf(**\n);printf(*稀疏矩阵运算器*\n);printf(**\n);printf(*A:输入矩阵M与NB:输出矩阵M与N的和*\n);printf(**\n);printf(*C:输出矩阵M与N的差D:输出矩阵M与N的积*\n);printf(**\n);printf(*E:退出*\n);printf(**\n);printf(*******************************************************\n);do{printf(\n请选择:\n);scanf(%c,&c);if(c=='E'||c=='e')gotoend;else{switch(c){case'A':case'a':{printf(请输入第一个矩阵M:\n);CreateSMatrix(&M);printf(请输入第二个矩阵N:\n);CreateSMatrix(&N);break;}case'B':case'b':{if(AddRLSMatrix(M,N,&Q))PrintSMatrix(Q);elseprintf(您的输入不满足矩阵相加的条件!\n);break;}case'C':case'c':{if(SubRLSMatrix(M,N,&Q))PrintSMatrix(Q);elseprintf(您的输入不满足矩阵相减的条件!\n);break;}case'D':case'd':{if(MulTSMatrix(M,N,&Q))PrintSMatrix