数据结构教学规划(稀疏矩阵运算器).doc

,*大学数据结构课程设计说明书题 目：稀疏矩阵运算器学生姓名：学 号：专 业：班 级：指导教师： 2013 年 7 月 24日稀疏矩阵运算器摘 要 摘要：设计一稀疏矩阵运算器。实现两个矩阵的相加、相减和相乘的功能。用“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算，采用分级的设计方法，分别设计出加、减、乘运算器的子程序，相加运算时只要依次存储、扫描两矩阵的行、列数，若行、列数相等，再取行、列下标相等的元素，相加后存入结果矩阵。相减运算与相加运算相同，同样取行、列下标相等的元素，相减后存入结果矩阵。相乘运算要先判断两矩阵能否相乘。若能相乘，则取行、列号相对应的元素进行相乘及相加，最后将对应元素存入结果矩阵中。通过实验表明本程序能够进行稀疏矩阵的相加，相减，相乘运算。具备矩阵的加、减、乘功能。关键词：相加运算器；相减运算器；相乘运算器 数据结构课程设计任务书针对本课程设计，完成以下课程设计任务：1、 熟悉系统实现工具和上级环境。2、 根据课程设计任务，查阅相关资料。3、 针对所选课题完成以下工作：（1）、需求分析（2）、概要设计（3）、详细设计（4）、编写源程序（5）、静态走查程序和上机调试程序4、书写上述文档和撰写课程设计报告。目 录稀疏矩阵运算器I摘 要II课程设计任务书III课程设计正文第一章 问题描述5第二章 需求分析6第三章 概要设计9第四章 详细设计19 4.1 函数说明10 4.2 算法分析19第五章 调试分析21第六章 测试结果23第七章 课程设计总结24参考文献24附录（程序清单）33第一章 问题描述一、问题描述：稀疏矩阵是指那些多数元素为零的矩阵，利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率，实现一个能进行稀疏矩阵基本运算的运算器。二、基本要求：以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。第二章 需求分析1、运算器程序以用户和计算机的对话方式执行，数组的建立方式为边输入边建立。2、由题目要求可知：首先应输入矩阵的行数、列数和非零个数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。3、程序可以对三元组的输入顺序不加以限制；根据对矩阵的行列，三元组作直接插入排序，从而进行运算时,不会产生错误。4、在用三元组表示稀疏矩阵时，相加、相减和乘积所得结果矩阵应该另生成，为了算法方便，使用二维数组存放。程序在Visual C+ 6.0环境下设计。程序执行的命令为：1.稀疏矩阵加法; 2.稀疏矩阵减法; 3.稀疏矩阵乘法; 第三章 概要设计1、三元组结构定义：typedef struct /三元组结构 int i,j; /矩阵行下标和列下标 int e; /值triple;2、稀疏矩阵结构定义：typedef struct/矩阵结构triple dataMAXSIZE+1; int m,n,t; /矩阵的行数、列数、非零元个数tripletable;3、两个稀疏矩阵相加函数：Add (tripletable M，tripletable T)4、两个稀疏矩阵相减函数：mut (tripletable M，tripletable T)5、两个稀疏矩阵相乘函数：mul (tripletable M，tripletable T)6、主函数：void main( )初始化；switch 接受命令；选择处理命令； 7、本程序有四个模块，调用关系如下：主程序模块矩阵输入模块 矩阵运算模块矩阵输出模块8、本程序的流程图：开始选择要执行的操作作选择3，进行矩阵乘法运算选择1，进行矩阵加法运算 选择2，进行矩阵减法运算输入n个矩阵A的行数、列数、非零元个数输出结果结束第四章 详细设计4.1 函数说明：1、稀疏矩阵的三元组顺序表存储表示：typedef struct /三元组结构 int i,j; /行下标和列下标 int e; /值triple;2、稀疏矩阵存储表示：typedef struct/ /矩阵结构triple dataMAXSIZE+1; int m,n,t; /矩阵的行数、列数、非零元个数tripletable;3、 主要函数：void Add( ) ;void cut ( ); void mul( );int main( );4.2 算法分析：设计一个矩阵类实现矩阵的运算：class tripletable(包含矩阵的各种运算函数)。输入矩阵（以三元组形式输入非零元），输出矩阵（阵列形式）。tripletable M;int m,n,t,i,j,e,k,c,d; int aMAXSIZEMAXSIZE; cout<<"输入稀疏矩阵M的行数，列数和非零元个数："cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k+)cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:"cin>>M.datak.i>>M.datak.j>>M.datak.e;for(k=1;k<=M.t;k+)aM.datak.iM.datak.j=M.datak.e;cout<<"矩阵M的行列形式为:"<<"n"for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<acd<<" "cout<<endl;矩阵的加法：void Add()/矩阵相加tripletable M;tripletable T;int m,n,t,i,j,e,k,c,d; int aMAXSIZEMAXSIZE=0; /将二维数组初始化为零int bMAXSIZEMAXSIZE=0;int fMAXSIZEMAXSIZE=0;cout<<"输入稀疏矩阵M的行数，列数和非零元个数："cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k+)cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:"cin>>M.datak.i>>M.datak.j>>M.datak.e;cout<<"矩阵M的行列形式为:"<<"n"for(k=1;k<=M.t;k+)aM.datak.iM.datak.j=M.datak.e;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<acd<<" "cout<<endl;cout<<"输入稀疏矩阵T的行数，列数和非零元个数："cin>>T.m>>T.n>>T.t;if(M.m!=T.m|M.n!=T.n) /检验两矩阵能否相加cout<<"两矩阵行或列不相等，请重新进入系统输入!"<<"n" return ;for(k=1;k<=T.t;k+)cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:"cin>>T.datak.i>>T.datak.j>>T.datak.e;cout<<"矩阵T的行列形式为:"<<"n"for(k=1;k<=T.t;k+)bT.datak.iT.datak.j=T.datak.e;for(c=1;c<=T.m;c+)for(d=1;d<=T.n;d+)cout<<bcd<<" "cout<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)fcd=acd+bcd; /两矩阵行、列号相等的元素之和为结果矩阵对应元素cout<<"两矩阵相加后的行列形式为："<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<fcd<<" "cout<<endl;以上主要设计思想：此功能由函数Add( )实现，当用户选择该功能时系统即提示用户初始化要进行加法的两个矩阵的信息。然后检测这两个矩阵是否符合矩阵相加的规则，如果符合，进行加法。否则重新进入系统输入数据。最后输出结果。矩阵的减法：void cut()/矩阵相减tripletable M;tripletable T;int m,n,t,i,j,e,k,c,d; int aMAXSIZEMAXSIZE=0;int bMAXSIZEMAXSIZE=0;int fMAXSIZEMAXSIZE=0;cout<<"输入稀疏矩阵M的行数，列数和非零元个数："cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k+)cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:"cin>>M.datak.i>>M.datak.j>>M.datak.e;cout<<"矩阵M的行列形式为:"<<"n"for(k=1;k<=M.t;k+)aM.datak.iM.datak.j=M.datak.e;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<acd<<" "cout<<endl;cout<<"输入稀疏矩阵T的行数，列数和非零元个数："cin>>T.m>>T.n>>T.t;if(M.m!=T.m|M.n!=T.n) /检验两矩阵能否进行减法运算cout<<"两矩阵行或列不相等，请重新进入系统输入!"<<"n"return ;for(k=1;k<=T.t;k+)cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:"cin>>T.datak.i>>T.datak.j>>T.datak.e;cout<<"矩阵T的行列形式为:"<<"n"for(k=1;k<=T.t;k+)bT.datak.iT.datak.j=T.datak.e;for(c=1;c<=T.m;c+)for(d=1;d<=T.n;d+)cout<<bcd<<" "cout<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)fcd=acd-bcd; /两矩阵行、列号相等的元素之差为结果矩阵对应元素cout<<"两矩阵相减后的行列形式为："<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<fcd<<" "cout<<endl;以上主要设计思想：此功能由函数cut( )实现，当用户选择该功能时系统即提示用户初始化要进行减法的两个矩阵的信息。然后检测这两个矩阵是否符合矩阵相减的规则，如果符合，进行减法运算。否则重新进入系统输入数据。最后输出结果。矩阵的乘法：void mul()/矩阵相乘tripletable M;tripletable T;int m,n,t,i,j,e,k,c,d; int aMAXSIZEMAXSIZE=0;int bMAXSIZEMAXSIZE=0;int fMAXSIZEMAXSIZE=0;cout<<"输入稀疏矩阵M的行数，列数和非零元个数："cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k+)cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:"cin>>M.datak.i>>M.datak.j>>M.datak.e;cout<<"矩阵M的行列形式为:"<<"n"for(k=1;k<=M.t;k+)aM.datak.iM.datak.j=M.datak.e;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<acd<<" "cout<<endl;cout<<"输入稀疏矩阵T的行数，列数和非零元个数："cin>>T.m>>T.n>>T.t;if(M.n!=T.m)cout<<"第一个矩阵的行和第二个矩阵的列不相等，请重新进入系统输入!"<<"n"/判断两个矩阵能否进行乘法运算return ;for(k=1;k<=T.t;k+)cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:"cin>>T.datak.i>>T.datak.j>>T.datak.e;cout<<"矩阵T的行列形式为:"<<"n"for(k=1;k<=T.t;k+)bT.datak.iT.datak.j=T.datak.e;for(c=1;c<=T.m;c+)for(d=1;d<=T.n;d+)cout<<bcd<<" "cout<<endl;for(c=1;c<=M.m;c+) /乘法的结果矩阵的元素为两矩阵对应行、列元素依次相乘之和for(d=1;d<=M.n;d+)int g,x;int sum=0; for(g=1;g<=M.n;g+)x=acg*bgd;sum=sum+x;fcd=sum;cout<<"两矩阵相乘后的行列形式为："<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=T.n;d+)cout<<fcd<<" "cout<<endl;以上主要设计思想为：此功能由函数mul( )实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后检测两者是否可以相乘，如果不能，则重新进入系统输入，最后得到结果。第五章 调试分析测试数据：（1）、矩阵的加法：矩阵M的行数、列数、非零个数：3、3、4；非零元素的三元组表示为：111,112,223,234；矩阵T的行数、列数、非零个数：3、3、4；非零元素的三元组表示为：125,216,227,338;两矩阵相加后的矩阵阵列形式为：1 7 0 6 10 4 0 0 8（2）、矩阵的减法：矩阵M的行数、列数、非零个数：3、3、4；非零元素的三元组表示为：111,112,223,234；矩阵T的行数、列数、非零个数：3、3、4；非零元素的三元组表示为：125,216,227,338;两矩阵相加后的矩阵阵列形式为：1 -3 0 -6 -4 4 0 0 -8（3）、矩阵的乘法：矩阵M的行数、列数、非零个数：4、3、4；非零元素的三元组表示为：111,112,223,234；矩阵T的行数、列数、非零个数：3、4、4；非零元素的三元组表示为：125,216,227,338;两矩阵相加后的矩阵阵列形式为：12 19 0 0 18 21 32 0 0 0 0 0 0 0 0 0遇到的问题：二维数组的初始化问题；解决方法：利用int aMAXSIZEMAXSIZE=0;语句，很好的将数组aMAXSIZEMAXSIZE的所有元素都初始化为零。第六章 测试结果（1）、矩阵的加法：矩阵M的行数、列数、非零个数：3、3、4；非零元素的三元组表示为：111,112,223,234；矩阵T的行数、列数、非零个数：3、3、4；非零元素的三元组表示为：125,216,227,338;两矩阵相加后的矩阵阵列形式为：1 7 0 6 10 4 0 0 8（2）、矩阵的减法：矩阵M的行数、列数、非零个数：3、3、4；非零元素的三元组表示为：111,112,223,234；矩阵T的行数、列数、非零个数：3、3、4；非零元素的三元组表示为：125,216,227,338;两矩阵相加后的矩阵阵列形式为：1 -3 0 -6 -4 4 0 0 -8（3）、矩阵的乘法：矩阵M的行数、列数、非零个数：4、3、4；非零元素的三元组表示为：111,112,223,234；矩阵T的行数、列数、非零个数：3、4、4；非零元素的三元组表示为：125,216,227,338;两矩阵相加后的矩阵阵列形式为：12 19 0 0 18 21 32 0 0 0 0 0 0 0 0 0第七章 课程设计总结由于本程序要求实现用三元组的形式对稀疏矩阵进行输入，用阵列的形式对矩阵进行输出，所以，一开始的想法构思存在困难。当发现运用二维数组进行矩阵输出时，对二维数组的赋值又出现了问题，但最终运用数组初始赋值为零的方法解决了这个问题。总的来说，此程序的理解难度并不高，整个程序的算法思想也比较简单，主要还是一些细节性问题需要去克服。通过此次课程设计，使我更加扎实的掌握了有关三元组表示稀疏矩阵方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。 在课程设计过程中，不断发现错误，不断改正，不断领悟，不断获取。最终的检测调试环节，本身就是在践行“过而能改，善莫大焉”的知行观。这次课程设计终于顺利完成了，在设计中遇到了很多问题，最后在一些资料和书本的帮助下，终于游逆而解。参考文献：1谭浩强著.C+程序设计（第二版）M.北京：清华大学出版社，2009.52严蔚敏、吴伟民 主编数据结构 （C语言版）M. 清华大学出版社 2004.11附录（源代码）：#include <iostream>using namespace std;#define MAXSIZE 100typedef struct /三元组结构 int i,j; /矩阵行下标和列下标 int e; /值triple;typedef struct/矩阵结构triple dataMAXSIZE+1; int m,n,t; /矩阵的行数、列数、非零元个数tripletable;void Add()/矩阵相加tripletable M;tripletable T;int m,n,t,i,j,e,k,c,d; int aMAXSIZEMAXSIZE=0;int bMAXSIZEMAXSIZE=0;int fMAXSIZEMAXSIZE=0;cout<<"输入稀疏矩阵M的行数，列数和非零元个数："cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k+)cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:"cin>>M.datak.i>>M.datak.j>>M.datak.e;cout<<"矩阵M的行列形式为:"<<"n"for(k=1;k<=M.t;k+)aM.datak.iM.datak.j=M.datak.e;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<acd<<" "cout<<endl;cout<<"输入稀疏矩阵T的行数，列数和非零元个数："cin>>T.m>>T.n>>T.t;if(M.m!=T.m|M.n!=T.n)cout<<"两矩阵行或列不相等，请重新进入系统输入!"<<"n"return ;for(k=1;k<=T.t;k+)cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:"cin>>T.datak.i>>T.datak.j>>T.datak.e;cout<<"矩阵T的行列形式为:"<<"n"for(k=1;k<=T.t;k+)bT.datak.iT.datak.j=T.datak.e;for(c=1;c<=T.m;c+)for(d=1;d<=T.n;d+)cout<<bcd<<" "cout<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)fcd=acd+bcd;cout<<"两矩阵相加后的行列形式为："<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<fcd<<" "cout<<endl;void cut()/矩阵相减tripletable M;tripletable T;int m,n,t,i,j,e,k,c,d; int aMAXSIZEMAXSIZE=0;int bMAXSIZEMAXSIZE=0;int fMAXSIZEMAXSIZE=0;cout<<"输入稀疏矩阵M的行数，列数和非零元个数："cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k+)cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:"cin>>M.datak.i>>M.datak.j>>M.datak.e;cout<<"矩阵M的行列形式为:"<<"n"for(k=1;k<=M.t;k+)aM.datak.iM.datak.j=M.datak.e;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<acd<<" "cout<<endl;cout<<"输入稀疏矩阵T的行数，列数和非零元个数："cin>>T.m>>T.n>>T.t;if(M.m!=T.m|M.n!=T.n)cout<<"两矩阵行或列不相等，请重新进入系统输入!"<<"n"return ;for(k=1;k<=T.t;k+)cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:"cin>>T.datak.i>>T.datak.j>>T.datak.e;cout<<"矩阵T的行列形式为:"<<"n"for(k=1;k<=T.t;k+)bT.datak.iT.datak.j=T.datak.e;for(c=1;c<=T.m;c+)for(d=1;d<=T.n;d+)cout<<bcd<<" "cout<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)fcd=acd-bcd;cout<<"两矩阵相减后的行列形式为："<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<fcd<<" "cout<<endl;void mul()/矩阵相乘tripletable M;tripletable T;int m,n,t,i,j,e,k,c,d; int aMAXSIZEMAXSIZE=0;int bMAXSIZEMAXSIZE=0;int fMAXSIZEMAXSIZE=0;cout<<"输入稀疏矩阵M的行数，列数和非零元个数："cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k+)cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:"cin>>M.datak.i>>M.datak.j>>M.datak.e;cout<<"矩阵M的行列形式为:"<<"n"for(k=1;k<=M.t;k+)aM.datak.iM.datak.j=M.datak.e;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<acd<<" "cout<<endl;cout<<"输入稀疏矩阵T的行数，列数和非零元个数："cin>>T.m>>T.n>>T.t;if(M.n!=T.m)cout<<"第一个矩阵的行和第二个矩阵的列不相等，请重新进入系统输入!"<<"n"return ;for(k=1;k<=T.t;k+)cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:"cin>>T.datak.i>>T.datak.j>>T.datak.e;cout<<"矩阵T的行列形式为:"<<"n"for(k=1;k<=T.t;k+)bT.datak.iT.datak.j=T.datak.e;for(c=1;c<=T.m;c+)for(d=1;d<=T.n;d+)cout<<bcd<<" "cout<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)int g,x;int sum=0;for(g=1;g<=M.n;g+)x=acg*bgd;sum=sum+x;fcd=sum;cout<<"两矩阵相乘后的行列形式为："<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=T.n;d+)cout<<fcd<<" "cout<<endl;int main()int x;tripletable *M =(tripletable*)malloc(sizeof(tripletable);tripletable *T =(tripletable*)malloc(sizeof(tripletable);cout<<"*"<<endl;cout<<"*稀疏矩阵运算器*"<<endl;cout<<"*选择序号*"<<endl;cout<<"*1.两矩阵相加*"<<endl;cout<<"*2.两矩阵相减*"<<endl;cout<<"*3.两矩阵相乘*"<<endl;cout<<"*"<<endl;cin>>x;switch (x)case 1:Add();break;case 2:cut();break;case 3:mul();break;