数据结构--稀疏矩阵课程设计.doc

安徽理工大学数据结构课程设计说明书题目: 稀疏矩阵的运算 院 系： 计算机科学与工程学院 专业班级： 计算机10-*班 学 号： 201030* 学生姓名： * 指导教师： 2011年 12 月 28 日安徽理工大学课程设计（论文）任务书 计算机科学与工程 学院 学 号201030*学生姓名*专业（班级）计10-*设计题目 稀疏矩阵的运算设计技术参数系统平台：Windows XP开发工具：Microsoft Visual C+ 6.0设计要求(1) 存储结构选择三元组存储方式；(2) 实现一个稀疏矩阵的转置运算；(3) 实现两个稀疏矩阵的加法运算；(4) 实现两个稀疏矩阵的减法运算；(5) 实现两个稀疏矩阵的乘法运算。工作量课程设计报告要求不少于3000字。源程序要求不少于300行工作计划11月9日-11月22日 查找相关资料11月23日-11月26日 DOS菜单界面设计11月27日-12月5日 设计算法12月6日-12月20日 编写代码12月21日-12月28日 撰写实验报告参考资料1秦锋.数据结构（C语言版）.北京:清华大学出版社,20112温秀梅,丁学均.Visual C+面向对象程序设计.北京:清华大学出版社,20093何钦铭,颜晖.C语言程序设计.北京:高等教育出版社,2008指导教师签字教研室主任签字 2011年 11 月 8 日 学生姓名： * 学号： 201030* 专业班级： 计10-* 课程设计题目： 稀疏矩阵的运算 指导教师评语： 成绩： 指导教师： 年 月 日安徽理工大学课程设计（论文）成绩评定表目录1 问题描述12 需求分析13 总体设计23.1 Matrix结构的定义23.2 系统流程图34 详细设计44.1 “菜单”界面44.2 建立矩阵44.3 显示矩阵64.4 矩阵的转置74.5 矩阵的加法运算84.6 矩阵的减法运算94.7 矩阵的乘法运算95 程序运行115.1 输入矩阵115.2 矩阵转置115.3 矩阵加法125.4 矩阵减法125.5 矩阵乘法125.6 退出及错误提示136 总结13参考文献14I1 问题描述(1) 题目内容：设计稀疏矩阵运算系统实现两个稀疏矩阵的加法、减法、乘法以及转置操作。(2) 基本要求：1 存储结构选择三元组存储方式；2 实现一个稀疏矩阵的转置运算；3 实现两个稀疏矩阵的加法运算；4 实现两个稀疏矩阵的减法运算；5 实现两个稀疏矩阵的乘法运算。(3) 设计目的：通过本次课程设计，了解稀疏矩阵的一些基本运算操作，并通过 相关的程序代码实现。2 需求分析 经过本次的课程设计，我认为稀疏矩阵运算系统主要实现的功能如下：(1) 建立矩阵：只有先建立了矩阵，才能够对矩阵进行运算操作，包括建立矩阵A和矩阵B；(2) 转置运算操作：对矩阵A或者矩阵B进行转置运算，输出相应的转置矩阵；(3) 四则运算操作：该步骤由两个矩阵同时参与，对其进行加法运算(A+B)、减法运算(A-B)以及乘法运算(A*B和B*A)；(4) 退出：当做完矩阵的运算操作之后，就可以点击它退出该界面。在这次设计中用到了一些变量和函数，例如：void Display(Matrix M)；int Max(int i,int j)；Matrix Zero(Matrix M)等，下面会做进一步详细的介绍。3 总体设计3.1 Matrix结构的定义struct Matrixint H;/矩阵的行数int L;/矩阵的列数int fly;/矩阵中的非零元个数int zhiMaxsizeMaxsize;/非零元值所在行所在列; 操作集合：(1) Matrix Enter(Matrix M);/建立矩阵M(2) void Display(Matrix M);/显示矩阵M(3) void Transpose(Matrix M);/M矩阵的转置(4) void Add(Matrix M,Matrix N);/求和运算 A+B(5) void Sub(Matrix M,Matrix N);/求差运算 A-B(5) void Multi(Matrix M,Matrix N);/求积运算 A*B(6) int Max(int i,int j);/求最大值(7) Matrix Zero(Matrix M);/矩阵所有元素赋值为03.2 系统流程图 该运算系统的系统流程图如图1所示： 稀疏矩阵运算系统输入矩阵A输入矩阵B矩阵A的转置A + B矩阵B的转置ABA * BB *A退 出图1 系统流程图4 详细设计4.1 “菜单”界面进入稀疏矩阵运算系统后的“菜单”界面如图2所示。图2 “菜单”界面4.2 建立矩阵矩阵在建立之后才能够进行运算操作，建立矩阵A和矩阵B，调用函数Enter(M)，首先根据所输入的矩阵M的行数H和列数L，建立H*L的矩阵M，并且调用函数Zero(M)将其所有元素均赋值为0；其次再根据所输入矩阵M的非零元个数fly做循环控制变量，按提示输入非零元所在的行h和列l以及非零元的值，如果输入的行h或者列l大于矩阵M的行H或列L，则提示输入错误；最后将非零元的值保存在矩阵M中的相应位置。程序如下：Matrix Enter(Matrix M)/建立矩阵coutM.HM.L;coutM.fly;cout(M.H*M.L)cout非零元个数多于矩阵元素总数,请重新输入!endl;coutM.fly;M=Zero(M);int h;int l;for(int n=1;n=M.fly;n+)/输入非零元所在的行、列和值cout请输入第nhl;if(hM.H|lM.L)/行列输入错误提示cout行列输入错误,请重新输入:endl;cout请重新输入第nhl;coutM.zhihl;coutendl;return M;注：该函数中调用的Zero()函数的功能为将矩阵M根据行数H和列数L把所有的元素赋值为0，代码如下：Matrix Zero(Matrix M)/矩阵所有元素赋值为0for(int i=1;i=M.H;i+)for(int j=1;j=M.L;j+)M.zhiij=0;return M;4.3 显示矩阵 建立好矩阵以后，为了验证所建立的矩阵是否成功，以及在后期运算时矩阵的显示，设计该函数，能更直观的看到输入以及输出的矩阵，代码如下：void Display(Matrix M)/显示矩阵int count=0;cout矩阵为:endl;for(int i=1;i=M.H;i+)for(int j=1;j=M.L;j+)printf(%-4d,M.zhiij);count+;if(count=M.L)coutendl;count=0;coutendl;4.4 矩阵的转置该函数实现的是矩阵A或矩阵B的转置操作，通过对矩阵的行和列进行调换，利用for()循环语句实现对矩阵A或矩阵B的转置，其代码如下：void Transpose(Matrix M)/矩阵转置C.H=M.L;C.L=M.H;cout原来的;Display(M);for(int i=1;i=M.L;i+)for(int j=1;j=M.H;j+)C.zhiij=M.zhiji;cout转置后的;Display(C);4.5 矩阵的加法运算 实现两个矩阵之间的加法运算，即A+B，其代码如下：void Add(Matrix M,Matrix N)/A+Bint n1=Max(M.H,N.H);int n2=Max(M.L,N.L);C.H=n1;C.L=n2;C=Zero(C);for(int i=1;i=n1;i+)for(int j=1;j=n2;j+)C.zhiij=M.zhiij+N.zhiij;cout A+B 的运算结果;Display(C);4.6 矩阵的减法运算实现两个矩阵之间的减法运算，即AB，其代码如下：void Sub(Matrix M,Matrix N)/A-Bint n1=Max(M.H,N.H);int n2=Max(M.L,N.L);C.H=n1;C.L=n2;C=Zero(C);for(int i=1;i=n1;i+)for(int j=1;j=n2;j+)C.zhiij=M.zhiij-N.zhiij;cout A-B 的运算结果;Display(C);4.7 矩阵的乘法运算实现两个矩阵之间的乘法运算，即A*B，如果矩阵A的列数和矩阵B的行数不相同,则无法进行乘法运算，系统会提示错误，其代码如下：void Multi(Matrix M,Matrix N)/A*Bif(M.L!=N.H)cout矩阵A的列数和矩阵B的行数不相同,无法进行乘法运算!n;elseif(M.L=N.H)C.H=M.H;C.L=N.L;C=Zero(C);for(int i=1;i=Maxsize;i+)for(int j=1;j=Maxsize;j+)for(int k=1;k=Maxsize;k+)C.zhiij+=M.zhiik*N.zhikj;cout运算结果;Display(C);5 程序运行5.1 输入矩阵 运行该运算系统，进入“菜单”选项以后，输入“1”，选择“输入矩阵A”，运算结果如图3所示；输入“2”，选择“输入矩阵B”，运算结果如图4所示： 图3 输入矩阵A 图4 输入矩阵B 5.2 矩阵转置 输入矩阵A和矩阵B以后，在“菜单”提示下，输入“3”，进行矩阵A的转置，运算结果如图5所示；输入“4”，进行矩阵B的转置，运算结果如图6所示： 图5 矩阵A的转置 图6 矩阵B的转置 5.3 矩阵加法在“菜单”提示下，输入“5”，进行两个矩阵的加法运算，即A+B，运算结果如图7所示：图7 矩阵加法5.4 矩阵减法 在“菜单”提示下，输入“6”，进行两个矩阵的加法运算，即A-B，运算结果如图8所示：图8 矩阵减法5.5 矩阵乘法在“菜单”提示下，输入“7”，进行两个矩阵的第一种乘法运算，即A*B，运算结果如图9所示；输入“8”，进行两个矩阵的第二种乘法运算，即B*A，运算结果如图10所示： 图9 矩阵乘法1(A*B) 图10 矩阵乘法2(B*A) 5.6 退出及错误提示 算法在运行时还有退出及错误提示功能，在“菜单”提示下，输入“0”则退出系统，如图11所示；若输入08以外的数字，则会出现错误提示，如图12所示：图11 退出 图12 错误提示 6 总结 通过对数据结构这门课的学习，我了解到：“数据结构”在计算机科学中是一门综合性的专业基础课。而我们现在所学的数据结构是C语言版的，是建立在C语言基础之上的，若是C语言基础知识不牢固，要想学好数据结构这门课程是有一定的困难的。所以在学习数据结构这门课程的时候，也顺便复习了C语言的相关内容，加深了我对C语言的理解和应用，并且也深深体会到了数据结构这门课程的重要性。在本次课程设计过程中，我体会到自己所学的东西太少了，很多都不知道，也遇到了不少实际问题，使我发现了在学习过程中的不足。这次课程设计，我本来打算做的是MFC可视化的人机友好界面，但是由于在程序设计以及运行时出现了太多目前无法解决的问题，只好退而求其次，应用了DOS界面来完成本次课程设计。在代码设计时，也出现了一些基本的C语言语法错误，如函数的嵌套定义等，在老师和同学的帮助下都一一解决了，这也反映了我C语言基础知识的不扎实，以后应在学习过程中加强这方面的学习。通过本次课程设计，我对数据结构这门课有了进一步的理解。数据结构这门课最主要的内容在于算法思想，而程序编写次之。在编写程序时，如果算法思想是正确的，那么这个程序就已经成功了一多半。算法思想在数据结构中占有重要