数据结构稀疏矩阵运算器

实习44.1稀疏矩阵运算器实习报告题目：设计一个能实现稀疏矩阵基本运算的运算器。班级：软件工程11-1姓名：张艳艳学号：1101051636完成日期2012-11-23一、需求分析1.本演示程序中，以“带行逻辑的链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的表示以阵列形式列出。首先应输入矩阵的行数和列数，并判断给出的两个矩阵的行和列对于所要求的运算是否相匹配。（矩阵的行数和列数均不超过20）2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入数据中的非法字符）和运算结果显示在其后。3.程序执行的命令包括：（1）构造链表；（2）输入数据；（3）数据处理；（4）结束4.测试数据（1）10000001000009+00-1=008-10010-300-3（2）1000010009-0-1=010-101-3-23300（3）4-30014200-6000080*010=80000100100010000070000000二、概要设计包含的头文件#includestdio.h#includemalloc.h#includestdlib.h定义结构体以实现矩阵的生成typedefstruct{inti,j;//非零元的行下标和列下标ElemTypee;//非零元的值}Triple;typedefstruct{Tripledata[MAXSIZE+1];intrpos[MAXRC+1];//各行第一个非零元在三元组的位置表inths,ls,fls;}TSMatrix,*Matrix;voidCreat(TSMatrix&M)//矩阵的生成算法voidAdd(TSMatrixA,TSMatrixB,TSMatrix&C,intn)//矩阵的相加与相减运算以n=1或-1来调节加或减intMultiplication(TSMatrixA,TSMatrixB,TSMatrix&Q)//实现矩阵的相乘运算voidTurn(TSMatrix*a,TSMatrix*b)//实现矩阵的转置三、详细设计#includestdio.h#includemalloc.h#includestdlib.h#defineMAXSIZE40//假设非零元素个数的最大值为40#defineMAXRC20//假设矩阵的最大行数为20typedefintElemType;typedefstruct{inti,j;//非零元的行下标和列下标ElemTypee;//非零元的值}Triple;typedefstruct{Tripledata[MAXSIZE+1];intrpos[MAXRC+1];//各行第一个非零元在三元组的位置表inths,ls,fls;}TSMatrix,*Matrix;voidCreat(TSMatrix&M)//矩阵的生成算法{inti,k;for(i=1;i=MAXRC+1;i++)M.rpos[i]=0;printf(请输入矩阵的行数、列数和非零元个数(以空格隔开):);scanf(%d%d%d,&M.hs,&M.ls,&M.fls);for(i=1;i=M.fls;i++){printf(请用三元组形式输入矩阵的元素(行列非零元素):);scanf(%d%d%d,&M.data[i].i,&M.data[i].j,&M.data[i].e);}for(i=1,k=1;i=M.hs;i++){M.rpos[i]=k;while(M.data[k].i=i&&k=M.fls)k++;}}voidAdd(TSMatrixA,TSMatrixB,TSMatrix&C,intn)//矩阵的相加与相减运算以n=1或-1来调节加或减{inta,b,temp,l;C.hs=A.hs;C.ls=A.ls;a=b=l=1;while(a=A.fls&&b=B.fls){if(A.data[a].i==B.data[b].i){if(A.data[a].jB.data[b].j)C.data[l++]=A.data[a++];elseif(A.data[a].jB.data[b].j){C.data[l]=B.data[b];C.data[l++].e=n*B.data[b++].e;}else{temp=A.data[a].e+n*B.data[b].e;if(temp){C.data[l]=A.data[a];C.data[l].e=temp;l++;}a++;b++;}}elseif(A.data[a].iB.data[b].i)C.data[l++]=A.data[a++];else{C.data[l]=B.data[b];C.data[l++].e=n*B.data[b++].e;}}while(a=A.fls)C.data[l++]=A.data[a++];while(b=B.fls){C.data[l]=B.data[b];C.data[l++].e=n*B.data[b++].e;}C.fls=l-1;}intMultiplication(TSMatrixA,TSMatrixB,TSMatrix&Q)//实现矩阵的相乘运算{intarow,brow,ccol,tp,p,q,t;intctemp[MAXRC+1];if(A.ls!=B.hs)return0;Q.hs=A.hs;Q.ls=B.ls;Q.fls=0;if(A.fls*B.fls){for(arow=1;arow=A.hs;arow++){for(ccol=1;ccol=Q.ls;ccol++)ctemp[ccol]=0;Q.rpos[arow]=Q.fls+1;if(arowA.hs)tp=A.rpos[arow+1];elsetp=A.fls+1;for(p=A.rpos[arow];ptp;p++){brow=A.data[p].j;if(browB.hs)t=B.rpos[brow+1];elset=B.fls+1;for(q=B.rpos[brow];qt;q++){ccol=B.data[q].j;ctemp[ccol]+=A.data[p].e*B.data[q].e;}}for(ccol=1;ccol=Q.ls;ccol++){if(ctemp[ccol]){if(++Q.flsMAXSIZE)return0;Q.data[Q.fls].i=arow;Q.data[Q.fls].j=ccol;Q.data[Q.fls].e=ctemp[ccol];}}}}return1;}voidPrint_SMatrix(TSMatrixM)//矩阵的输出{intk,l,n;Matrixp;p=&M;for(k=1,n=1;k=p-hs;k++){for(l=1;l=p-ls;l++){if(p-data[n].i==k&&p-data[n].j==l){printf(%5d,p-data[n].e);n++;}elseprintf(%5d,0);}printf(\n);}printf(\n);}voidTurn(TSMatrix*a,TSMatrix*b)//实现矩阵的转置{intq,col,p;b-hs=a-ls;b-ls=a-hs;b-fls=a-fls;if(b-fls){q=1;for(col=1;col=a-ls;col++)for(p=1;p=a-fls;p++)if(a-data[p].j==col){b-data[q].i=a-data[p].j;b-data[q].j=a-data[p].i;b-data[q].e=a-data[p].e;++q;}}}voidDestory_SMatrix(TSMatrix&M){M.hs=M.ls=M.fls=0;}voidmain(){TSMatrixA,B,C;TSMatrix*p=&A,*q=&B;intflag,n;while(1){system(cls);printf(\n\n\n);printf(\t----------------欢迎使用稀疏矩阵运算器--------------------\n\n);printf(\t**********************************************************\n);printf(\t****稀疏矩阵的加、减、转、乘****\n);printf(\t**********************************************************\n);printf(\t*1、稀疏矩阵的加法*\n);printf(\t*2、稀疏矩阵的减法*\n);printf(\t*3、稀疏矩阵的转置*\n);printf(\t*4、稀疏矩阵的乘法*\n);printf(\t*5、退出该应用程序*\n);printf(\t**********************************************************\n);printf(输入要进行的项目的编号:);scanf(%d,&flag);if(flag==5)break;Creat(A);printf(矩阵A:\n);Print_SMatrix(A);switch(flag){case1:Creat(B);n=1;printf(矩阵B:\n);Print_SMatrix(B);if(A.hs==B.hs&&A.ls==B.ls){printf(A+B:\n);Add(A,B,C,n);Print_SMatrix(C);}elseprintf(错误!行列不一致\n);break;case2:Creat(B);n=-1;printf(矩阵B:\n);Print_SMatrix(B);if(A.hs==B.hs&&A.ls==B.ls){printf(A-B:\n);Add(A,B,C,n);Print_SMatrix(C);}elseprintf(错误!行列不一致\n);break;case3:printf(A-B:\n);Turn(p,q);Print_SMatrix(B);break;case4:Creat(B);printf(矩阵B:\n);Print_SMatrix(B);printf(A*B:\n);n=Multiplication(A,B,C);if(!n)printf(错误!行列不匹配\n);elsePrint_SMatrix(C);break;default:printf(输入错误!\n);break;}Destory_SMatrix(A);Destory_SMatrix(B);Destory_SMatrix(C);getchar();getchar();}printf(\n\t\t\t***程序已经退出***\n);getchar();}四、调试分析本程序中主要应用了函数的调用，大大提高了程序的可读性。在编程的过程中，对于转置与相乘，由于原先C语言课本上又源代码，并没有费多大力气。但是对于矩阵的加减，刚开始设置了两个函数，但是效果并不理想，通过借鉴他人的算法，设置一个n值，提高了代码的使用率。五、用户手册1本程序的运行环境为DOS操作系统，执行文件为校园导游.exe。2进入演示程序后即显示文本方式的用户界面：3、根据提示键入命令后会出现其他输入提示，根据提示输入即可。执行完一个命令后按任意键会重新回到上图界面，直至输入5。六、测试结果执行命令1后执行命令2后执行命令3后执行命令4后执行命令5后七、附录该程序在同一个文件，即只在.cpp文件里的以实现。