数据结构--稀疏矩阵课程设计
安徽理工大学
数据结构
课程设计说明书题目: 稀疏矩阵的运算
院系：计算机科学与工程学院
专业班级：计算机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语言版）.北京:清华大学出版社,2011
[2]温秀梅,丁学均.Visual C++面向对象程序设计.北京:清华大学出版社,2009
[3]何钦铭,颜晖.C语言程序设计.北京:高等教育出版社,2008
指导教师签字教研室主任签字
2011年 11 月 8 日
安徽理工大学课程设计（论文）成绩评定表
学生姓名：***** 学号：201030**** 专业班级：计10-* 课程设计题目：稀疏矩阵的运算
指导教师评语：
成绩：
指导教师：
年月日
目录
1 问题描述 (1)
2 需求分析 (1)
3 总体设计 (2)
3.1 Matrix结构的定义 (2)
3.2 系统流程图 (3)
4 详细设计 (4)
4.1 “菜单”界面 (4)
4.2 建立矩阵 (4)
4.3 显示矩阵 (6)
4.4 矩阵的转置 (7)
4.5 矩阵的加法运算 (8)
4.6 矩阵的减法运算 (9)
4.7 矩阵的乘法运算 (9)
5 程序运行 (11)
5.1 输入矩阵 (11)
5.2 矩阵转置 (11)
5.3 矩阵加法 (12)
5.4 矩阵减法 (12)
5.5 矩阵乘法 (12)
5.6 退出及错误提示 (13)
6 总结 (13)
参考文献 (14)
1 问题描述
(1)题目内容：设计稀疏矩阵运算系统实现两个稀疏矩阵的加法、减法、乘法以
及转置操作。
(2)基本要求：
①存储结构选择三元组存储方式；
②实现一个稀疏矩阵的转置运算；
③实现两个稀疏矩阵的加法运算；
④实现两个稀疏矩阵的减法运算；
⑤实现两个稀疏矩阵的乘法运算。
(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 Matrix{
int H; //矩阵的行数
int L; //矩阵的列数
int fly; //矩阵中的非零元个数
int zhi[Maxsize][Maxsize];//非零元值[所在行][所在列] };
操作集合：
(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); //矩阵所有元素赋值为0
3.2 系统流程图
该运算系统的系统流程图如图1所示：
图1 系统流程图
稀疏矩阵运算系统
输入矩阵A 输入矩阵B
矩阵A 的转置
A + B
矩阵B 的
转置
A －B
A * B
B *A
退 出
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) //建立矩阵
{
cin>>M.H>>M.L;
cout<<"请输入矩阵的非零元个数:";
cin>>M.fly;
cout< if(M.fly>(M.H*M.L)) { cout<<"非零元个数多于矩阵元素总数,请重新输入!"< cout<<"请重新输入矩阵的非零元个数:"; cin>>M.fly; } M=Zero(M); int h; int l; for(int n=1;n<=M.fly;n++) //输入非零元所在的行、列和值{ cout<<"请输入第"< cin>>h>>l; if(h>M.H||l>M.L) // 行列输入错误提示 { cout<<"行列输入错误,请重新输入:"< cout<<"请重新输入第"< cin>>h>>l; } cin>>M.zhi[h][l]; cout< } return M; } 注：该函数中调用的Zero()函数的功能为将矩阵M根据行数H和列数L 把所有的元素赋值为0，代码如下： Matrix Zero(Matrix M)//矩阵所有元素赋值为0 { for(int i=1;i<=M.H;i++) for(int j=1;j<=M.L;j++) M.zhi[i][j]=0; return M; } 4.3 显示矩阵 建立好矩阵以后，为了验证所建立的矩阵是否成功，以及在后期运算时矩阵的显示，设计该函数，能更直观的看到输入以及输出的矩阵，代码如下：void Display(Matrix M) //显示矩阵 { int count=0; cout<<"矩阵为:"< for(int i=1;i<=M.H;i++) for(int j=1;j<=M.L;j++) { printf("%-4d",M.zhi[i][j]); count++; if(count==M.L) { cout< count=0; } } cout< } 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.zhi[i][j]=M.zhi[j][i]; } cout<<"转置后的"; Display(C); } 4.5 矩阵的加法运算 实现两个矩阵之间的加法运算，即A+B，其代码如下：void Add(Matrix M,Matrix N) //A+B { int 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.zhi[i][j]=M.zhi[i][j]+N.zhi[i][j]; } cout<<" A+B 的运算结果"; Display(C); } 4.6 矩阵的减法运算 实现两个矩阵之间的减法运算，即A－B，其代码如下： void Sub(Matrix M,Matrix N) //A-B { int 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.zhi[i][j]=M.zhi[i][j]-N.zhi[i][j]; } cout<<" A-B 的运算结果"; Display(C); } 4.7 矩阵的乘法运算 实现两个矩阵之间的乘法运算，即A*B，如果矩阵A的列数和矩阵B的行数不相同,则无法进行乘法运算，系统会提示错误，其代码如下： void Multi(Matrix M,Matrix N) //A*B { if(M.L!=N.H) { cout<<"矩阵A的列数和矩阵B的行数不相同,无法进行乘法运算!\n"; } else if(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.zhi[i][j]+=M.zhi[i][k]*N.zhi[k][j]; } 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所示；若输入0－8以外的数字，则会出现错误提示，如图12所示： 图11 退出图12 错误提示 6 总结 通过对数据结构这门课的学习，我了解到：“数据结构”在计算机科学中是一门综合性的专业基础课。而我们现在所学的数据结构是C语言版的，是建立在C 语言基础之上的，若是C语言基础知识不牢固，要想学好数据结构这门课程是有一定的困难的。所以在学习数据结构这门课程的时候，也顺便复习了C语言的相关内容，加深了我对C语言的理解和应用，并且也深深体会到了数据结构这门课程的重要性。 在本次课程设计过程中，我体会到自己所学的东西太少了，很多都不知道，也遇到了不少实际问题，使我发现了在学习过程中的不足。这次课程设计，我本来打算做的是MFC可视化的人机友好界面，但是由于在程序设计以及运行时出现了太多目前无法解决的问题，只好退而求其次，应用了DOS界面来完成本次课程设计。在代码设计时，也出现了一些基本的C语言语法错误，如函数的嵌套定义等，在老师和同学的帮助下都一一解决了，这也反映了我C语言基础知识的不扎实，以后应在学习过程中加强这方面的学习。 通过本次课程设计，我对数据结构这门课有了进一步的理解。数据结构这门课最主要的内容在于算法思想，而程序编写次之。在编写程序时，如果算法思想是正确的，那么这个程序就已经成功了一多半。算法思想在数据结构中占有重要地位，如果说C语言是数据结构这座程序大厦的根基的话，那么算法思想就是构成大厦的一砖一瓦，再好的根基离了砖瓦也构不成大厦。所以，要想学好数据结构这门课程，平时不只要加强程序的编写，更要多思考算法思想，加强对算法思想的锻炼和理解。 本次课程设计得到了老师和很多同学的帮助，在此一并表示感谢。 参考文献 [1]秦锋.数据结构（C语言版）.北京:清华大学出版社,2011 [2]温秀梅,丁学均.Visual C++面向对象程序设计.北京:清华大学出版社,2009 [3]何钦铭,颜晖.C语言程序设计.北京:高等教育出版社,2008 Matrix CreateMatrix() { matrix A; printf("\n\t\t亲输入稀疏矩阵的行数，列数和非零元个数（用逗号隔开）；"); scanf("%d,%d,%d",&A.rows,&A.terms); for(int n=o;n<=A.terms-1;n++) { printf("\n\t\t输入非零元值个数（格式:行号,列号,值）:"); scanf("%d,%d,%d",&A.data[n].i,&A.data[n].j,&A.data[n].v); } return A; }