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

专业课程设计I报告（ 2011 / 2012 学年 第 二 学期）题目 稀疏矩阵的转换 专 业 软件工程 学 生 姓 名 张鹏宇 班 级 学 号 09003018 指 导 教 师 张卫丰 指 导 单 位 计算机学院软件工程系 日 期 2012年6月18号 指导教师成绩评定表学生姓名班级学号专业评分内容评分标准优秀良好中等差平时成绩认真对待课程设计，遵守实验室规定，上机不迟到早退，不做和设计无关的事设计成果设计的科学、合理性功能丰富、符合题目要求 界面友好、外观漂亮、大方程序功能执行的正确性程序算法执行的效能设计报告设计报告正确合理、反映系统设计流程文档内容详实程度文档格式规范、排版美观验收答辩简练、准确阐述设计内容，能准确有条理回答各种问题，系统演示顺利。评分等级指导教师简短评语指导教师签名日期备注评分等级有五种：优秀、良好、中等、及格、不及格附件： 稀疏矩阵的转换一、 课题内容和要求1问题描述设计程序用十字链表实现稀疏矩阵的加、减、乘、转置。2需求分析（1）设计函数建立稀疏矩阵，初始化值。（2）设计函数输出稀疏矩阵的值。（3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。（4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。（5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。（6）构造函数进行稀疏矩阵的转置，并输出结果。（7）退出系统。二、设计思路分析（1）设计函数建立稀疏矩阵，初始化值。（2）设计函数输出稀疏矩阵的值。（3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。（4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。（5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。（6）构造函数进行稀疏矩阵的转置，并输出结果。（7）退出系统。三、概要设计 为了实现以上功能，可以从3个方面着手设计。1主界面设计为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图所示。2存储结构设计本系统采用单链表结构存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储。3系统功能设计本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数i typedef int ElemType实现。建立稀疏矩阵用void Creat()实现，依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。（1）稀疏矩阵的加法：此功能由函数void Xiangjia( )实现，当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。（2）稀疏矩阵的乘法：此功能由函数void Xiangcheng( )实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后进行相乘，最后得到结果。（3）稀疏矩阵的转置：此功能由函数void Zhuanzhi( )实现。当用户选择该功能，系统提示用户初始化一个矩阵，然后进行转置，最终输出结果。（4）退出：即退出稀疏矩阵的应用系统。由函数5实现，但用户选择此功能时，系统会提示你是否确实想退出，如果是，则退出，否则继续。三、模块设计1.模块设计本程序包含1个模块：主程序模块加各功能实现模块。2系统子程序及功能设计本系统共设置7个子程序，各子程序的函数名及功能说明如下。（1）typedef int ElemType / 初始化矩阵 ( 2 ) void Creat(TSMatrix &M) /建立矩阵（3）void Print_SMatrix(TSMatrix M) / 输出矩阵的信息以下编号（4）-（6）是稀疏矩阵的基本操作。依次是：相加，相乘，转置等。（4）void Xiangjia(TSMatrix A,TSMatrix B,TSMatrix &C,int n)/把A 和B两个矩阵相加，结果是C（5）void Xiangcheng(TSMatrix A,TSMatrix B,TSMatrix &Q)/把A和B两个矩阵相乘，结果是Q（6）void Zhuanzhi(TSMatrix *a,TSMatrix *b) / 把A转置（7）void main() / 主函数。设定界面的颜色,大小和窗口的标题，调用工作区模块函数 四、详细设计 #include #include #include #define MAXSIZE 40 /假设非零元素个数的最大值为40 #define MAXRC 20/假设矩阵的最大行数为20 typedef int ElemType; typedef struct int i,j; /非零元的行下标和列下标 ElemType e; /非零元的值 Triple; typedef struct Triple dataMAXSIZE+1; int rposMAXRC+1; /各行第一个非零元在三元组的位置表 int hs,ls,fls; TSMatrix,*Matrix; void Creat(TSMatrix &M) int i,k; for(i=1;i=MAXRC+1;i+) M.rposi=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.datai.i,&M.datai.j,&M.datai.e); for(i=1,k=1;i=M.hs;i+) M.rposi=k; while(M.datak.i=i & k=M.fls)k+; void Xiangjia(TSMatrix A,TSMatrix B,TSMatrix &C,int n) int a,b,temp,l; C.hs=A.hs;C.ls=A.ls;a=b=l=1;while(a=A.fls & b=B.fls) if(A.dataa.i=B.datab.i) if(A.dataa.jB.datab.j)C.datal=B.datab; C.datal+.e=n*B.datab+.e;elsetemp=A.dataa.e+n*B.datab.e; if(temp)C.datal=A.dataa; C.datal.e=temp; l+; a+;b+; else if(A.dataa.iB.datab.i)C.datal+=A.dataa+; else C.datal=B.datab; C.datal+.e=n*B.datab+.e; while(a=A.fls)C.datal+=A.dataa+; while(b=B.fls)C.datal=B.datab; C.datal+.e=n*B.datab+.e; C.fls=l-1; int Xiangcheng(TSMatrix A,TSMatrix B,TSMatrix &Q) int arow,brow,ccol,tp,p,q,t; int ctempMAXRC+1; if(A.ls!=B.hs)return 0; 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+) ctempccol=0; Q.rposarow=Q.fls+1; if(arowA.hs)tp=A.rposarow+1;elsetp=A.fls+1;for(p=A.rposarow;ptp;p+)brow=A.datap.j;if(browB.hs)t=B.rposbrow+1;elset=B.fls+1;for(q=B.rposbrow;qt;q+)ccol=B.dataq.j;ctempccol+=A.datap.e*B.dataq.e; for(ccol=1;ccolMAXSIZE)return 0; Q.dataQ.fls.i=arow; Q.dataQ.fls.j=ccol; Q.dataQ.fls.e=ctempccol; return 1; void Print_SMatrix(TSMatrix M) int k,l,n; Matrix p; p=&M; for(k=1,n=1;khs;k+) for(l=1;lls;l+) if(p-datan.i=k & p-datan.j=l) printf(%5d,p-datan.e); n+; else printf(%5d,0); printf(n); printf(n); void Zhuanzhi(TSMatrix *a,TSMatrix *b)int q,col,p;b-hs=a-ls;b-ls=a-hs;b-fls=a-fls;if(b-fls)q=1;for(col=1;colls;col+) for(p=1;pfls;p+)if(a-datap.j=col)b-dataq.i=a-datap.j;b-dataq.j=a-datap.i;b-dataq.e=a-datap.e;+q;void Destory_SMatrix(TSMatrix &M) M.hs=M.ls=M.fls=0; void main() TSMatrix A,B,C; TSMatrix *p=&A,*q=&B;int flag,n; while(1) system(cls);printf(nnn); printf(tn); printf(t * 稀疏矩阵的加、减、转、乘 * n);printf(tn); printf(t 1、稀疏矩阵的加法 n); printf(t 2、稀疏矩阵的减法 n); printf(t 3、稀疏矩阵的转置 n); printf(t 4、稀疏矩阵的乘法 n); printf(t 5、退出该应用程序 n); printf(tn);printf(输入要进行的项目的编号:); scanf(%d,&flag); if(flag=5)break; Creat(A); printf(矩阵A:n); Print_SMatrix(A); switch(flag) case 1: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); else printf(错误!行列不一致n); break; case 2: 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); else printf(错误!行列不一致n); break; case 3: printf(A-B:n); Zhuanzhi(p,q); Print_SMatrix(B);break; case 4:Creat(B); printf(矩阵B:n); Print_SMatrix(B); printf(A*B:n); n=Xiangcheng(A,B,C); if(!n)printf(错误!行列不匹配n); elsePrint_SMatrix(C);break; default:printf(输入错误!n); Destory_SMatrix(A); Destory_SMatrix(B); Destory_SMatrix(C); getchar();getchar();printf(nttt *程序已经退出*n);getchar();五、测试数据及其结果分析六、调试过程中的问题在进行int Xiangcheng(TSMatrix A,TSMatrix B,TSMatrix &Q) 函数调用的时候进行运算的时候出现了一点小差错。七、专业课程设计总结总通过本次实验，在我的学习理解上有很大的促进作用。单单对稀疏矩阵，我了解了由于矩阵在程序中常使用二维阵列表示，二维阵列的大小稀疏矩阵与使用的存储器空间成正比，如果多数的元素没有数据，则会造成存储器空间的浪费，为此，必须设计稀