稀疏矩阵设计说明书

中北大学数据结构课程设计说明书学生姓名:李世阳学号：1021011727学院:软件学院专业:软件工程题目:稀疏矩阵的应运指导教师何志英2011年12月20日11.设计任务概述（包括系统总体框图及功能描述）设计内容：（1）稀疏矩阵的存储（2）稀疏矩阵加法（3）矩阵乘法（4）矩阵转置。设计要求：1.建立十字列表存储结构。2.总体设计要画流程图。3.提供程序测试方案。4.界面友好。总体框图：2.开始用户选择计算类型键入1键入2加法运算转置运算显示结果等待用户键入0继续计算结束运算输入3乘法运算任意键输入42本设计所采用的数据结构（如：链表、栈、树、图等）要实现设计要求，首先矩阵的十字列表存储结构。十字列表是表示元素个数和位置在操作过程中变化较大时，就不宜采用顺序存储来表示三元组的线性表。3.功能模块详细设计b）概要设计：1)能够在一个界面内实现多功能选择，如：printf(\t4.Press1toaddthearray;\n);printf(\t1.Press2totransthearray;\n);printf(\t3.press3tomultiplythetrsmatrixes;\n);printf(\t6.Press4toexitthesystem;\n);从而在这上面能够选择想要实现的功能。2)存储功能：只是简单的应用三元组进行输入，进行存储，再把它存储的内容输出。3)转置功能：运用三元组进行存储，按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当位置。如果能预先确定矩阵M中每一列的第一个非零元在b.data中应有的位置，那么在a.data中的三元组依次作转置时，便可直接放到b.data中恰当的位置。4)乘法功能：对于M中每个元素M.data[p]（1，2，...，M.tu），找到N中所有满足条件M.data[p].j=N.data[q].i的元素N.data[q]，求M.data[p].v和N.data[q].v的乘积。5)矩阵相加：根据提示输入两个矩阵，实现sum=b[m][n]+a[m1][n]，运用二元数组的方法实现与输出它们的和。6)在实现各个内容后想继续实现别的功能，按任意键退出，继续选择功能运算。7)实现完各个内容，按‘4’退出程序。4.c)详细设计：#includestdio.h3#defineMAXSIZE10000typedefintElemType;typedefstruct{introw,col;ElemTypev;}Triple;typedefstruct{Tripledata[MAXSIZE];intm,n,t;}TriTable;/*三元组相加*/voidadd(TriTable*A,TriTable*B,TriTable*C){inti,j,k;if(A-m!=B-m||A-n!=B-n){printf(俩个矩阵不能相加);return;}C-m=A-m;C-n=A-n;C-t=0;if(A-t==0&&B-t==0)return;i=j=k=1;while(i=A-t&&j=B-t){if(A-data[i].rowB-data[j].row){C-data[k]=A-data[i];i++;k++;}else{if(A-data[i].rowB-data[j].row){C-data[k]=B-data[j];j++;k++;}else4{if(A-data[i].colB-data[j].col){C-data[k]=A-data[i];i++;k++;}else{if(A-data[i].colB-data[j].col){C-data[k]=B-data[j];j++;k++;}else{if(A-data[i].v+B-data[j].v!=0){C-data[k].row=A-data[i].row;C-data[k].col=A-data[i].col;C-data[k].v=A-data[i].v+B-data[j].v;k++;}i++;j++;}}}}}while(iA-t){C-data[k]=A-data[i];i++;k++;}while(jB-t){C-data[k]=B-data[j];j++;k++;}5C-t=k;}/*三元组相乘*/voidMultS(TriTable*A,TriTable*B,TriTable*C){intk,p,crow,brow,q,ccol;intnum[MAXSIZE],pos[MAXSIZE],ctemp[MAXSIZE];if(A-n==B-m){for(k=1;k=B-m;k++)num[k]=0;for(k=1;k=B-t;k++)num[B-data[k].row]++;pos[1]=1;for(k=2;k=B-t;k++)pos[k]=pos[k-1]+num[k-1];pos[1+B-t]=pos[B-t]+1;C-m=A-m;C-n=B-n;C-t=0;p=1;while(p=A-t){crow=A-data[p].row;for(k=1;k=C-n;k++)ctemp[k]=0;while(p=A-t&&A-data[p].row==crow){brow=A-data[p].col;for(q=pos[brow];q=pos[brow+1]-1;q++){ccol=B-data[q].col;ctemp[ccol]=ctemp[ccol]+A-data[p].v*B-data[q].v;}p=p+1;}6for(ccol=1;ccol=B-n;ccol++)if(ctemp[ccol]!=0){C-t=C-t+1;C-data[C-t].row=crow;C-data[C-t].col=ccol;C-data[C-t].v=ctemp[ccol];}}}elseprintf(俩个矩阵不能相乘);return;}/*三元组转置*/voidTranspose(TriTable*A,TriTable*B){intcol,i,p,q;intnum[MAXSIZE],position[MAXSIZE];B-t=A-t;B-m=A-n;B-n=A-m;if(B-t){for(col=1;col=A-n;col++)num[col]=0;for(i=1;i=A-t;i++)num[A-data[i].col]++;position[1]=1;for(col=2;col=A-n;col++)position[col]=position[col-1]+num[col-1];for(p=1;p=A-t;p++){col=A-data[p].col;q=position[col];B-data[q].row=A-data[p].col;B-data[q].col=A-data[p].row;B-data[q].v=A-data[p].v;position[col]++;}7}}/*创建三元组*/voidcreatarrey(TriTable*A){inti,j;printf(请输入矩阵的行数:);scanf(%d,&A-m);printf(请输入矩阵的列数:);scanf(%d,&A-n);printf(请输入非零的数:);scanf(%d,&A-t);for(i=1;i=A-t;i++){printf(请输入第%d个非零数（并用，隔开）:,i);scanf(%d,%d,%d,&A-data[i].row,&A-data[i].col,&A-data[i].v);}}/*三元组显示*/voidoutput(TriTable*A){inti,j,t,k=0;t=1;printf(所得到的矩阵为:\n);for(i=1;i=A-m;i++){for(j=1;j=A-n;j++){if(A-data[t].row==i&&A-data[t].col==j){printf(%4d,A-data[t].v);t++;}elseprintf(%4d,k);}printf(\n);}}8voidmain(){inti=0;TriTableA,B,C;while(i4){printf(***************************\n);printf(****\n);printf(**稀疏矩阵运算器**\n);printf(**---------------------**\n);printf(***************************\n);printf(_____________________________________________________________________\n);printf(|请选择|\n);printf(|1.加法2.转置3.乘法4.退出\n);printf(|_____________________________________________________________________|\n\n);printf(请您选择:);scanf(%d,&i);switch(i){case1:creatarrey(&A);output(&A);creatarrey(&B);output(&B);add(&A,&B,&C);output(&C9);break;case2:creatarrey(&A);output(&A);Transpose(&A,&B);output(&B);break;case3:creatarrey(&A);output(&A);creatarrey(&B);output(&B);MultS(&A,&B,&C);output(&C);break;case4:break;}}getch();}3.3程序运行结果（拷屏）1，俩个矩阵的加法102矩阵的转置113，两个矩阵相乘5.课程设计心得、存在问题及解决方法第一次做课程设计，开始自己读题时，思路不是很清晰，后来逐渐明白这个程序就是要结合所学数据结构的思想，用稀疏矩阵那块所用到的一些算法来实现矩阵的存储，加法，乘法，转置这四个基本的功能。在分析好所要实现的功能后，开始编写代码，在代码调试的过成中，并不是一帆风顺的，这也是平常练的不够吧，经过几轮删删改改，终于做的差不多了，基本达到了老师的要求，但是还是有很多不足的地方。通过这次对稀疏矩阵应用的编写与调试，巩固了有关结矩阵算法的知识及其操作，锻炼了实际应用能力。在不断地进行书面设计和上机调试的过程中，认识到掌握设计程序的思路非常重要，要正确处理算法与语法的关系，算法是程序的核心，是灵魂，语法是外壳12是工具。但是光掌握语法也是不够的，应该还要把重点放在解题思路上。…………………………