数据结构课程设计报告稀疏矩阵运算器Word文件下载.docx
《数据结构课程设计报告稀疏矩阵运算器Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告稀疏矩阵运算器Word文件下载.docx（21页珍藏版）》请在冰点文库上搜索。
1.3输出的形式
运算结果的矩阵以通常的阵列形式输出；
1.4程序所能达到的功能
该程序可以实现以三元组形式输入两个矩阵，求出两个矩阵的和、差、积；
并可根据输入的矩阵的行列数不同判别是否可以进行相加、减、乘，并重新输入正确的矩阵；
1.5测试数据
测试的数据及其结果如下：
矩阵M矩阵N矩阵Q
加法：
+
=
减法：
-
乘法：
X
1.6确定解决方案
进入运算器界面后选择要实行的操作，按1实现矩阵相加，调用函数AddSMatrix，若输入的两个矩阵行列数不相等，则提示输入错误，重新输入矩阵进行加法运算；
按2实现矩阵相乘，若输入的第一矩阵的列数不等于第二个矩阵的行数，则提示输入错误，重新输入矩阵进行乘法运算；
按3实现矩阵相减，若输入的两个矩阵行列数不相等，则提示输入错误，重新输入矩阵进行减法运算；
按4退出程序
以加法为例实现运算过程，如下：
（稀疏矩阵的和为Q）
第一个稀疏矩阵M的三元组为（（1,1,10）,（2,3,9）,（3,1,-1））
第二个稀疏矩阵N的三元组为（（2,3,-1）,（3,1,1）,（3,3,-3））
M的第一个三元组（1,1,10）与N的第一个三元组（2,3,-1）比较，因行数1<
2则Q得到第一个三元组（1,1,10）；
M的第二个三元组与N的第一个三元组比较，因对应行列数相等则9+（-1）=8，次行列数就是Q的行列数即得到Q的第二个三元组为（2,3,8）;
M第三个三元组（3,1,-1））与N的第二个三元组进行比较，因对应行列数相等，且1+（-1）=0，则不进行相加；
而此时只有N的第三个三元组（3,3,-3）符合条件，则Q得到第三个三元组（3,3,-3）；
最终结果为
（（1,1,10）,（2,3,8）,（3,3,-3））
1.7所有抽象数据类型的定义
以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方式——三元组顺序表。
/*稀疏矩阵的三元组顺序表存储表示*/
#defineMAXSIZE1000//假设非零元个数的最大值为1000
typedefstruct
{inti,j;
//该非零元的行下标和列下标
ElemTypee;
//该非零元数值
}Triple;
{Tripledata[MAXSIZE+1];
//非零三元组表，data[0]未用
intmu,nu,tu;
//矩阵的行数（<
20）、列数（<
20）和非零元个数
}TSMatrix;
在此，data域中表示非零元得三元组是以行序为主序顺序排列的，这样有利于进行某些矩阵运算。
抽象数据类型稀疏矩阵的定义如下：
ADTSparseMatrix{
数据对象:
D={aij|i=1,2,3,…，m;
j=1,2,…，n;
Aij（-ElemSet,m和n分别称为矩阵的行数和列数}
数据关系：
R={Row,Col}
基本操作：
CreateSMatrix（&
M）;
操作结果：
创建稀疏矩阵M。
PrintSMatrix（M）;
初始条件：
稀疏矩阵M存在。
输出稀疏矩阵M。
AddSMatrix（M,N,&
Q）;
初始条件：
稀疏矩阵M和N的的行数和列数对应相等。
操作结果：
求稀疏矩阵的和Q=Ｍ＋Ｎ。
SubSMatrix（M,N,&
求稀疏矩阵的差Q=M-N。
MultSMatrix（M,N,&
稀疏矩阵M的列数等于N的行数。
求稀疏矩阵的积Q=MXN。
}ADTSpareMatrix
此流程表示的是主程序的流程以及各程序模块之间的层次（调用）关系。
2、详细设计
2.1稀疏矩阵的加法运算思路
比较满足条件（行数及列数都相同的两个矩阵）的两个稀疏矩阵中不为0的元素的行数及列数（即i与j），将i与j都相等的前后两个元素值e相加，保持i,j不变储存在新的三元组中，不等的则分别储存在此新三元组中。
最后得到的这个新三元组表就是两个矩阵的和矩阵的三元组表。
其算法如下：
StatusAddSMatrix（TSMatrixM,TSMatrixN,TSMatrix&
Q）
{
if（M.mu==N.mu&
&
M.nu==N.nu）//行数,列数相等才能相加
{
Q.mu=M.mu;
Q.nu=N.nu;
intp,q,k;
p=1;
q=1;
k=1;
while（p<
=M.tu&
q<
=N.tu）//两个稀疏矩阵存在
{
if（M.data[p].i==N.data[q].i）//两个稀疏矩阵的行数相等
{
if（M.data[p].j==N.data[q].j）//两个稀疏矩阵的列数相等
{
if（M.data[p].e+N.data[q].e!
=0）//两个稀疏矩阵相加的结果不为0（三元组表）
{
Q.data[k].i=M.data[p].i;
Q.data[k].j=M.data[p].j;
Q.data[k].e=M.data[p].e+N.data[q].e;
++k;
}
++q;
++p;
}
elseif（M.data[p].j<
N.data[q].j）
//第一个稀疏矩阵列数小于第二个稀疏矩阵列数
Q.data[k]=M.data[p];
//把M中的所有信息都赋给Q
++k;
else
//第一个稀疏矩阵列数大于第二个稀疏矩阵的列数
Q.data[k]=N.data[q];
}
elseif（M.data[p].i<
N.data[q].i）
//第一个稀疏矩阵行列数小于第二个稀疏矩阵行数
Q.data[k]=M.data[p];
++p;
++k;
else
Q.data[k]=N.data[q];
++q;
}
=M.tu）//只有M并且符合条件
Q.data[k]=M.data[p];
++p;
++k;
while（q<
=N.tu）//只有N并且符合条件
Q.data[k]=N.data[q];
++q;
Q.tu=k-1;
printf（"
\t\t******两个矩阵的加法结果为******\n"
）;
returnOK;
}
else
{
两个矩阵行,列数不等，出错了\n"
CreateSMatrix（M）;
第一个矩阵为:
\n"
PrintSMatrix（M）;
CreateSMatrix（N）;
第二个矩阵为:
PrintSMatrix（N）;
AddSMatrix（M,N,Q）;
}
}
2.2稀疏矩阵相减的算法思路
此思路与稀疏矩阵相加的算法思路相同，其算法如下：
StatusSubtMatrix（TSMatrixM,TSMatrixN,TSMatrix&
if（M.mu==N.mu&
M.nu==N.nu）//行数，列数相等才能相减
{
//M的第p个三元组
//N的第q个三元组
//Q的第k个三元组
{
if（M.data[p].i==N.data[q].i）//两个稀疏矩阵的行数相等
if（M.data[p].j==N.data[q].j）//两个稀疏矩阵的列数相等
if（M.data[p].e-N.data[q].e!
=0）
//两个稀疏矩阵相减的结果不为0
{
Q.data[k].e=M.data[p].e-N.data[q].e;
//第一个稀疏矩阵列数小于第二个稀疏矩阵的列数
{
elseif（M.data[p].j>
N.data[q].j）//第一个稀疏矩阵列数大于第二个稀疏矩阵的列
Q.data[k].i=N.data[q].i;
Q.data[k].j=N.data[q].j;
Q.data[k].e=-N.data[q].e;
//即0-N.data[q].e
N.data[q].i）//第一个稀疏矩阵行列数小于第二个稀疏矩阵行数
//整个三元组进行复制
if（M.data[p].i>
N.data[q].i）//第一个稀疏矩阵行列数大于第二个稀疏矩阵行数
Q.data[k].i=N.data[q].i;
Q.data[k].j=N.data[q].j;
Q.data[k].e=-N.data[q].e;
Q.data[k].i=N.data[q].i;
Q.data[k].j=N.data[q].j;
Q.data[k].e=-N.data[q].e;
\t\t******两个矩阵的相减结果为******\n"
else
{
两个矩阵行列数不等，不能相减，请重新输入\n"
SubtMatrix（M,N,Q）;
2.3稀疏矩阵相乘的算法思路
两个相乘的矩阵为M与N，对M中每个元素M.data[p]（p=1,2,…,M.tu）,找到N中所有满足条件M.data[p].j=N.data[q].i的元素N.data[q]，求得M.data[p].v和N.data[q].v的乘积，又T（i,j）=∑M（i,k）×
N（k,j）,乘积矩阵T中每个元素的值是个累计和，这个乘积M.data[p].v×
N.data[q].v只是T[i][j]中的一部分。
为便于操作，应对每个元素设一累计和的变量，其初值是零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。
由于T中元素的行号和M中元素的行号一致，又M中元素排列是以M的行序为主序的，由此可对T进行逐行处理，先求得累计求和的中间结果（T的一行），然后再压缩存储到Q.data中去，其算法如下：
StatusMultSMatrix（TSMatrixM,TSMatrixN,TSMatrix&
intk1,k2,k3,m;
Q.mu=M.mu;
Q.nu=N.nu;
Q.tu=0;
if（M.nu==N.mu）
//第一个矩阵的列数不等于第二个矩阵的行数才可以相乘
for（k1=1;
k1<
=M.tu;
k1++）
for（k2=1;
k2<
=N.tu;
k2++）
if（M.data[k1].j==N.data[k2].i）
//第一个矩阵的列数不等于第二个矩阵的行数时相乘
m=M.data[k1].e*N.data[k2].e;
if（Q.tu==0）
//Q中还未有一个非零元时，赋予第一个非零元
Q.data[1].e=m;
Q.data[1].i=M.data[k1].i;
Q.data[1].j=N.data[k2].j;
Q.tu++;
else
for（k3=1;
k3<
=Q.tu;
k3++）
{
if（Q.data[k3].i==M.data[k1].i&
Q.data[k3].j==N.data[k2].j）
//Q的行等于M的行，Q的列等于N的列时相加
{
Q.data[k3].e+=m;
//对各个数相加
break;
}
}
if（k3==Q.tu+1）//相加完后成为Q中的三元组
{
Q.data[k3].e=m;
Q.data[k3].i=M.data[k1].i;
Q.data[k3].j=N.data[k2].j;
Q.tu++;
}
printf（"
\t\t******两个矩阵相乘结果为******\n"
returnOK;
第一个矩阵的列数不等于第二个矩阵的行数\n"
不能相乘，请重新输入\n"
printSMatrix（N）;
MultSMatrix（M,N,Q）;
}
2.4创建稀疏矩阵
以三元组表的形式输入创建稀疏矩阵
StatusCreateSMatrix（TSMatrix&
M）
{
printf（"
\t\t******请输入您的稀疏矩阵******\n\n"
do{
\t******请输入矩阵的行数，列数，非零元素个数******\n"
"
scanf（"
%d%d%d"
&
M.mu,&
M.nu,&
M.tu）;
if（（M.mu<
0||M.mu>
20）||（M.nu<
0||M.nu>
20）||（（M.tu/（M.mu*M.nu））>
0.05）||（（M.tu>
M.mu*M.nu）||M.tu>
MAXSIZE））
\n不满足，请重新输入!
!
}while（（M.mu<
MAXSIZE））;
for（intk=1;
k<
k++）
do{
\t******请输入非零元素的行数i，列数j，数值v******\n"
scanf（"
M.data[k].i,&
M.data[k].j,&
M.data[k].e）;
if（（M.data[k].i<
0||M.data[k].i>
M.mu）||（M.data[k].j<
0||M.data[k].j>
M.nu）||（M.data[k].e==0））
printf（"
}while（（M.data[k].i<
M.nu）||（M.data[k].e==0））;
returnOK;
3、系统调试与测试
3.1程序的菜单界面如下：
3.2实现加法运算：
3.3实现减法运算：
3.4实现乘法运算：
当在调试程序过程中遇到有错误的时候，先试着进行调试，找出不应该有得小错误，同时参照课本的算法思路对错误的语句进行分析，也上网找XX查询，以得到无错误的程序，更重要的是与小组成员进行讨论，体现了我们的合作精神。
4、结果分析
4.1时间复杂度的分析
a）加法运算
由于两矩阵行列相等，故时间复杂度为O（行*列）
b）减法运算
c）乘法运算
设M是m1*n1矩阵，N是m2*n2矩阵，则时间复杂度是O（m1*n1*n2）
4.2心得体会
虽然一直以来我不怎么喜欢数据结构这门课，但是它已经是我的一门课程，我就必须学好它，曾经在编程上遇到过很多困难，编了一学期的程序，有时会因为编出作业题目而又高兴几天，有时会因编不出程序而失落几天，总之，我喜欢编程的过程，包括与同学交流，上网XX，从中学到了很多。
此次的课程设计更让我们意识到了数据结构的高深，与小组成员的讨论让我们学到了更多关于数据结构的知识，这是一次团队合作的收获成果。
5、参考文献
1、《数据结构》（c语言描述），严蔚敏编著，清华大学出版社
2、《数据结构题集》，严蔚敏编著，清华大学出版社
升级会员 