数据结构--稀疏矩阵课程设计.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语言版)。北京：清华大学出版社，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所示:
稀疏矩阵运算系统
输入矩阵A
输入矩阵B
矩阵A的转置
A + B
矩阵B的转置
A－B
A * B
B *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） //建立矩阵
{
cout<<”请输入矩阵的行数和列数："；
cin>〉M。H>〉M。L；
cout<<”请输入矩阵的非零元个数:”；
cin>>M。fly；
cout〈<endl;
if（M。fly〉（M。H＊M。L）)
{
cout〈<"非零元个数多于矩阵元素总数，请重新输入!"<<endl;
cout<〈”请重新输入矩阵的非零元个数："；
cin>〉M。fly；
｝
M=Zero（M）；
int h；
int l；
for（int n=1;n〈=M.fly;n++） //输入非零元所在的行、列和值
｛
cout〈〈"请输入第"〈<n<〈”个非零元所在的行和列：";
cin〉〉h>〉l;
if（h>M.H|｜l>M。L) // 行列输入错误提示
{
cout〈<”行列输入错误,请重新输入：”<<endl;
cout<〈"请重新输入第"<<n〈〈”个非零元所在的行和列："；
cin〉>h〉>l；
}
cout〈〈"请输入该非零元的值:"；
cin>>M。zhi［h]［l]；
cout<<endl；
｝
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〈〈"矩阵为：”〈<endl；
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〈<endl；
count=0;
}
}
cout<〈endl；
}
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