稀疏矩阵的运算(完美版)

专业课程设计I报告（2011/2012学年第二学期）题目稀疏矩阵的转换专业软件工程学生姓名张鹏宇班级学号09003018指导教师张卫丰指导单位计算机学院软件工程系日期2012年6月18号1指导教师成绩评定表学生姓名班级学号专业评分内容评分标准优秀良好中等差平时成绩认真对待课程设计，遵守实验室规定，上机不迟到早退，不做和设计无关的事设计成果设计的科学、合理性功能丰富、符合题目要求界面友好、外观漂亮、大方程序功能执行的正确性程序算法执行的效能设计报告设计报告正确合理、反映系统设计流程文档内容详实程度文档格式规范、排版美观验收答辩简练、准确阐述设计内容，能准确有条理回答各种问题，系统演示顺利。评分等级指导教师简短评语指导教师签名日期备注评分等级有五种：优秀、良好、中等、及格、不及格2附件：稀疏矩阵的转换一、课题内容和要求1．问题描述设计程序用十字链表实现稀疏矩阵的加、减、乘、转置。2．需求分析（1）设计函数建立稀疏矩阵，初始化值。（2）设计函数输出稀疏矩阵的值。（3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。（4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。（5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。（6）构造函数进行稀疏矩阵的转置，并输出结果。（7）退出系统。二、设计思路分析（1）设计函数建立稀疏矩阵，初始化值。（2）设计函数输出稀疏矩阵的值。（3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。（4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。（5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。（6）构造函数进行稀疏矩阵的转置，并输出结果。（7）退出系统。三、概要设计为了实现以上功能，可以从3个方面着手设计。1．主界面设计为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图所示。32．存储结构设计本系统采用单链表结构存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储。3．系统功能设计本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数itypedefintElemType实现。建立稀疏矩阵用voidCreat()实现，依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。（1）稀疏矩阵的加法：此功能由函数voidXiangjia()实现，当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。（2）稀疏矩阵的乘法：此功能由函数voidXiangcheng()实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后进行相乘，最后得到结果。（3）稀疏矩阵的转置：此功能由函数voidZhuanzhi()实现。当用户选择该功能，系统提示用户初始化一4个矩阵，然后进行转置，最终输出结果。（4）退出：即退出稀疏矩阵的应用系统。由函数5实现，但用户选择此功能时，系统会提示你是否确实想退出，如果是，则退出，否则继续。三、模块设计1.模块设计本程序包含1个模块：主程序模块加各功能实现模块。2．系统子程序及功能设计本系统共设置7个子程序，各子程序的函数名及功能说明如下。（1）typedefintElemType//初始化矩阵(2)voidCreat(TSMatrix&M)//建立矩阵（3）voidPrint_SMatrix(TSMatrixM)//输出矩阵的信息以下编号（4）-（6）是稀疏矩阵的基本操作。依次是：相加，相乘，转置等。（4）voidXiangjia(TSMatrixA,TSMatrixB,TSMatrix&C,intn)//把A和B两个矩阵相加，结果是C（5）voidXiangcheng(TSMatrixA,TSMatrixB,TSMatrix&Q)//把A和B两个矩阵相乘，结果是Q（6）voidZhuanzhi(TSMatrix*a,TSMatrix*b)//把A转置（7）voidmain()//主函数。设定界面的颜色,大小和窗口的标题，调用工作区模块函数四、详细设计#includestdio.h#includemalloc.h#includestdlib.h#defineMAXSIZE40//假设非零元素个数的最大值为40#defineMAXRC20//假设矩阵的最大行数为20typedefintElemType;typedefstruct{inti,j;//非零元的行下标和列下标ElemTypee;//非零元的值}Triple;5typedefstruct{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++;}}voidXiangjia(TSMatrixA,TSMatrixB,TSMatrix&C,intn){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{6temp=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;}intXiangcheng(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++){7ccol=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);}voidZhuanzhi(TSMatrix*a,TSMatrix*b){intq,col,p;8b-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);printf(\t┃***稀疏矩阵的加、减、转、乘***┃\n);printf(\t┣━━━━━━━━━━━━━━━━━━━━━━━━━━━┫\n);printf(\t┃1、稀疏矩阵的加法┃\n);printf(\t┃2、稀疏矩阵的减法┃\n);printf(\t┃3、稀疏矩阵的转置┃\n);printf(\t┃4、稀疏矩阵的乘法9┃\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);Xiangjia(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);Xiangjia(A,B,C,n);Print_SMatrix(C);}elseprintf(错误!行列不一致\n);break;case3:printf(A-B:\n);Zhuanzhi(p,q);Print_SMatrix(B);break;case4:Creat(B);printf(矩阵B