数据结构课程设计(稀疏矩阵运算器)

*****大学数据结构课程设计说明书题目：稀疏矩阵运算器学生姓名：学号：专业：班级：指导教师：2013年7月24日稀疏矩阵运算器摘要摘要：设计一稀疏矩阵运算器。实现两个矩阵的相加、相减和相乘的功能。用“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算，采用分级的设计方法，分别设计出加、减、乘运算器的子程序，相加运算时只要依次存储、扫描两矩阵的行、列数，假设行、列数相等，再取行、列下标相等的元素，相加后存入结果矩阵。相减运算与相加运算相同，同样取行、列下标相等的元素，相减后存入结果矩阵。相乘运算要先判断两矩阵能否相乘。假设能相乘，那么取行、列号相对应的元素进行相乘及相加，最后将对应元素存入结果矩阵中。通过实验说明本程序能够进行稀疏矩阵的相加，相减，相乘运算。具备矩阵的加、减、乘功能。关键词：相加运算器；相减运算器；相乘运算器数据结构课程设计任务书针对本课程设计，完成以下课程设计任务：熟悉系统实现工具和上级环境。根据课程设计任务，查阅相关资料。针对所选课题完成以下工作：〔1〕、需求分析〔2〕、概要设计〔3〕、详细设计〔4〕、编写源程序〔5〕、静态走查程序和上机调试程序4、书写上述文档和撰写课程设计报告。目录16973稀疏矩阵运算器 I31887摘要 II31887课程设计任务书 III31887课程设计正文 Ⅳ11961第一章问题描述 511961第二章需求分析 68345第三章概要设计 928752第四章详细设计 194.1函数说明 104.2算法分析 1911961第五章调试分析 2111961第六章测试结果 2311961第七章课程设计总结 2411961参考文献 24附录〔程序清单〕 33问题描述一、问题描述：稀疏矩阵是指那些多数元素为零的矩阵，利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率，实现一个能进行稀疏矩阵根本运算的运算器。二、根本要求：以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵那么以通常的阵列形式列出。需求分析1、运算器程序以用户和计算机的对话方式执行，数组的建立方式为边输入边建立。2、由题目要求可知：首先应输入矩阵的行数、列数和非零个数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。3、程序可以对三元组的输入顺序不加以限制；根据对矩阵的行列，三元组作直接插入排序，从而进行运算时,不会产生错误。4、在用三元组表示稀疏矩阵时，相加、相减和乘积所得结果矩阵应该另生成，为了算法方便，使用二维数组存放。程序在VisualC++6.0环境下设计。程序执行的命令为：1.稀疏矩阵加法;2.稀疏矩阵减法;3.稀疏矩阵乘法;概要设计1、三元组结构定义：typedefstruct{//三元组结构inti,j;//矩阵行下标和列下标inte;//值}triple;2、稀疏矩阵结构定义：typedefstruct//矩阵结构{tripledata[MAXSIZE+1];intm,n,t;//矩阵的行数、列数、非零元个数}tripletable;3、两个稀疏矩阵相加函数：Add(tripletableM，tripletableT)4、两个稀疏矩阵相减函数：mut(tripletableM，tripletableT)5、两个稀疏矩阵相乘函数：mul(tripletableM，tripletableT)6、主函数：voidmain(){初始化；switch{接受命令；选择处理命令；}}7、本程序有四个模块，调用关系如下：主程序模块主程序模块 矩阵输入模块矩阵输入模块矩阵运算模块矩阵运算模块 矩阵输出模块矩阵输出模块8、本程序的流程图：开始开始选择要执行的操作作选择要执行的操作作选择3，进行矩阵乘法运算选择1，进行矩阵加法运算 选择3，进行矩阵乘法运算选择1，进行矩阵加法运算选择2，进行矩阵减法运算选择2，进行矩阵减法运算输入n个矩阵A的行数、列数、非零元个数输入n个矩阵A的行数、列数、非零元个数输出结果输出结果结束结束详细设计4.1函数说明：1、稀疏矩阵的三元组顺序表存储表示：typedefstruct{//三元组结构inti,j;//行下标和列下标inte;//值}triple;2、稀疏矩阵存储表示：typedefstruct//矩阵结构{tripledata[MAXSIZE+1];intm,n,t;//矩阵的行数、列数、非零元个数}tripletable;主要函数：voidAdd();voidcut();voidmul();intmain();4.2算法分析：设计一个矩阵类实现矩阵的运算：classtripletable(包含矩阵的各种运算函数)。输入矩阵〔以三元组形式输入非零元〕，输出矩阵〔阵列形式〕。{tripletableM;intm,n,t,i,j,e,k,c,d;inta[MAXSIZE][MAXSIZE];cout<<"输入稀疏矩阵M的行数，列数和非零元个数：";cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k++){cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:";cin>>M.data[k].i>>M.data[k].j>>M.data[k].e;}for(k=1;k<=M.t;k++){a[M.data[k].i][M.data[k].j]=M.data[k].e;}cout<<"矩阵M的行列形式为:"<<"\n";for(c=1;c<=M.m;c++){for(d=1;d<=M.n;d++)cout<<a[c][d]<<"";cout<<endl;}矩阵的加法：voidAdd()//矩阵相加{tripletableM;tripletableT;intm,n,t,i,j,e,k,c,d;inta[MAXSIZE][MAXSIZE]={0};//将二维数组初始化为零intb[MAXSIZE][MAXSIZE]={0};intf[MAXSIZE][MAXSIZE]={0};cout<<"输入稀疏矩阵M的行数，列数和非零元个数：";cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k++){cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:";cin>>M.data[k].i>>M.data[k].j>>M.data[k].e;}cout<<"矩阵M的行列形式为:"<<"\n";for(k=1;k<=M.t;k++){a[M.data[k].i][M.data[k].j]=M.data[k].e;}for(c=1;c<=M.m;c++){for(d=1;d<=M.n;d++)cout<<a[c][d]<<"";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.data[k].i>>T.data[k].j>>T.data[k].e;}cout<<"矩阵T的行列形式为:"<<"\n";for(k=1;k<=T.t;k++){b[T.data[k].i][T.data[k].j]=T.data[k].e;}for(c=1;c<=T.m;c++){for(d=1;d<=T.n;d++)cout<<b[c][d]<<"";cout<<endl;}for(c=1;c<=M.m;c++){for(d=1;d<=M.n;d++){f[c][d]=a[c][d]+b[c][d];//两矩阵行、列号相等的元素之和为结果矩阵对应元素}}cout<<"两矩阵相加后的行列形式为："<<endl;for(c=1;c<=M.m;c++){for(d=1;d<=M.n;d++)cout<<f[c][d]<<"";cout<<endl;}}以上主要设计思想：此功能由函数Add()实现，当用户选择该功能时系统即提示用户初始化要进行加法的两个矩阵的信息。然后检测这两个矩阵是否符合矩阵相加的规那么，如果符合，进行加法。否那么重新进入系统输入数据。最后输出结果。矩阵的减法：voidcut()//矩阵相减{tripletableM;tripletableT;intm,n,t,i,j,e,k,c,d;inta[MAXSIZE][MAXSIZE]={0};intb[MAXSIZE][MAXSIZE]={0};intf[MAXSIZE][MAXSIZE]={0};cout<<"输入稀疏矩阵M的行数，列数和非零元个数：";cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k++){cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:";cin>>M.data[k].i>>M.data[k].j>>M.data[k].e;}cout<<"矩阵M的行列形式为:"<<"\n";for(k=1;k<=M.t;k++){a[M.data[k].i][M.data[k].j]=M.data[k].e;}for(c=1;c<=M.m;c++){for(d=1;d<=M.n;d++)cout<<a[c][d]<<"";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.data[k].i>>T.data[k].j>>T.data[k].e;}cout<<"矩阵T的行列形式为:"<<"\n";for(k=1;k<=T.t;k++){b[T.data[k].i][T.data[k].j]=T.data[k].e;}for(c=1;c<=T.m;c++){for(d=1;d<=T.n;d++)cout<<b[c][d]<<"";cout<<endl;}for(c=1;c<=M.m;c++){for(d=1;d<=M.n;d++){f[c][d]=a[c][d]-b[c][d];//两矩阵行、列号相等的元素之差为结果矩阵对应元素}}cout<<"两矩阵相减后的行列形式为："<<endl;for(c=1;c<=M.m;c++){for(d=1;d<=M.n;d++)cout<<f[c][d]<<"";cout<<endl;}}以上主要设计思想：此功能由函数cut()实现，当用户选择该功能时系统即提示用户初始化要进行减法的两个矩阵的信息。然后检测这两个矩阵是否符合矩阵相减的规那么，如果符合，进行减法运算。否那么重新进入系统输入数据。最后输出结果。矩阵的乘法：voidmul()//矩阵相乘{tripletableM;tripletableT;intm,n,t,i,j,e,k,c,d;inta[MAXSIZE][MAXSIZE]={0};intb[MAXSIZE][MAXSIZE]={0};intf[MAXSIZE][MAXSIZE]={0};cout<<"输入稀疏矩阵M的行数，列数和非零元个数：";cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k++){cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:";cin>>M.data[k].i>>M.data[k].j>>M.data[k].e;}cout<<"矩阵M的行列形式为:"<<"\n";for(k=1;k<=M.t;k++){a[M.data[k].i][M.data[k].j]=M.data[k].e;}for(c=1;c<=M.m;c++){for(d=1;d<=M.n;d++)cout<<a[c][d]<<"";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.data[k].i>>T.data[k].j>>T.data[k].e;}cout<<"矩阵T的行列形式为:"<<"\n";for(k=1;k<=T.t;k++){b[T.data[k].i][T.data[k].j]=T.data[k].e;}for(c=1;c<=T.m;c++){for(d=1;d<=T.n;d++)cout<<b[c][d]<<"";cout<<endl;}for(c=1;c<=M.m;c++)//乘法的结果矩阵的元素为两矩阵对应行、列元素依次相乘之和{for(d=1;d<=M.n;d++){intg,x;intsum=0;for(g=1;g<=M.n;g++){x=a[c][g]*b[g][d];sum=sum+x;}f[c][d]=sum;}}cout<<"两矩阵相乘后的行列形式为："<<endl;for(c=1;c<=M.m;c++){for(d=1;d<=T.n;d++)cout<<f[c][d]<<"";cout<<endl;}}以上主要设计思想为：此功能由函数mul()实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后检测两者是否可以相乘，如果不能，那么重新进入系统输入，最后得到结果。调试分析测试数据：〔1〕、矩阵的加法：矩阵M的行数、列数、非零个数：3、3、4；非零元素的三元组表示为：111,112,223,234；矩阵T的行数、列数、非零个数：3、3、4；非零元素的三元组表示为：125,216,227,338;两矩阵相加后的矩阵阵列形式为：1706104008〔2〕、矩阵的减法：矩阵M的行数、列数、非零个数：3、3、4；非零元素的三元组表示为：111,112,223,234；矩阵T的行数、列数、非零个数：3、3、4；非零元素的三元组表示为：125,216,227,338;两矩阵相加后的矩阵阵列形式为：1-30-6-4400-8〔3〕、矩阵的乘法：矩阵M的行数、列数、非零个数：4、3、4；非零元素的三元组表示为：111,112,223,234；矩阵T的行数、列数、非零个数：3、4、4；非零元素的三元组表示为：125,216,227,338;两矩阵相加后的矩阵阵列形式为：121900182132000000000遇到的问题：二维数组的初始化问题；解决方法：利用inta[MAXSIZE][MAXSIZE]={0};语句，很好的将数组a[MAXSIZE][MAXSIZE]的所有元素都初始化为零。测试结果〔1〕、矩阵的加法：矩阵M的行数、列数、非零个数：3、3、4；非零元素的三元组表示为：111,112,223,234；矩阵T的行数、列数、非零个数：3、3、4；非零元素的三元组表示为：125,216,227,338;两矩阵相加后的矩阵阵列形式为：1706104008〔2〕、矩阵的减法：矩阵M的行数、列数、非零个数：3、3、4；非零元素的三元组表示为：111,112,223,234；矩阵T的行数、列数、非零个数：3、3、4；非零元素的三元组表示为：125,216,227,338;两矩阵相加后的矩阵阵列形式为：1-30-6-4400-8〔3〕、矩阵的乘法：矩阵M的行数、列数、非零个数：4、3、4；非零元素的三元组表示为：111,112,223,234；矩阵T的行数、列数、非零个数：3、4、4；非零元素的三元组表示为：125,216,227,338;两矩阵相加后的矩阵阵列形式为：121900182132000000000课程设计总结由于本程序要求实现用三元组的形式对稀疏矩阵进行输入，用阵列的形式对矩阵进行输出，所以，一开始的想法构思存在困难。当发现运用二维数组进行矩阵输出时，对二维数组的赋值又出现了问题，但最终运用数组初始赋值为零的方法解决了这个问题。总的来说，此程序的理解难度并不高，整个程序的算法思想也比拟简单，主要还是一些细节性问题需要去克服。通过此次课程设计，使我更加扎实的掌握了有关三元组表示稀疏矩阵方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验缺乏。

在课程设计过程中，不断发现错误，不断改正，不断领悟，不断获取。最终的检测调试环节，本身就是在践行“过而能改，善莫大焉”的知行观。这次课程设计终于顺利完成了，在设计中遇到了很多问题，最后在一些资料和书本的帮助下，终于游逆而解。参考文献：[1]谭浩强著.C++程序设计〔第二版〕[M].北京：清华大学出版社，2009.5[2]严蔚敏、吴伟民主编《数据结构〔C语言版〕》[M].清华大学出版社2004.11附录〔源代码〕：#include<iostream>usingnamespacestd;#defineMAXSIZE100typedefstruct{//三元组结构inti,j;//矩阵行下标和列下标inte;//值}triple;typedefstruct//矩阵结构{tripledata[MAXSIZE+1];intm,n,t;//矩阵的行数、列数、非零元个数}tripletable;voidAdd()//矩阵相加{tripletableM;tripletableT;intm,n,t,i,j,e,k,c,d;inta[MAXSIZE][MAXSIZE]={0};intb[MAXSIZE][MAXSIZE]={0};intf[MAXSIZE][MAXSIZE]={0};cout<<"输入稀疏矩阵M的行数，列数和非零元个数：";cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k++){cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:";cin>>M.data[k].i>>M.data[k].j>>M.data[k].e;}cout<<"矩阵M的行列形式为:"<<"\n";for(k=1;k<=M.t;k++){a[M.data[k].i][M.data[k].j]=M.data[k].e;}for(c=1;c<=M.m;c++){for(d=1;d<=M.n;d++)cout<<a[c][d]<<"";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.data[k].i>>T.data[k].j>>T.data[k].e;}cout<<"矩阵T的行列形式为:"<<"\n";for(k=1;k<=T.t;k++){b[T.data[k].i][T.data[k].j]=T.data[k].e;}for(c=1;c<=T.m;c++){for(d=1;d<=T.n;d++)cout<<b[c][d]<<"";cout<<endl;}for(c=1;c<=M.m;c++){for(d=1;d<=M.n;d++){f[c][d]=a[c][d]+b[c][d];}}cout<<"两矩阵相加后的行列形式为："<<endl;for(c=1;c<=M.m;c++){for(d=1;d<=M.n;d++)cout<<f[c][d]<<"";cout<<endl;}}voidcut()//矩阵相减{tripletableM;tripletableT;intm,n,t,i,j,e,k,c,d;inta[MAXSIZE][MAXSIZE]={0};intb[MAXSIZE][MAXSIZE]={0};intf[MAXSIZE][MAXSIZE]={0};cout<<"输入稀疏矩阵M的行数，列数和非零元个数：";cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k++){cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:";cin>>M.data[k].i>>M.data[k].j>>M.data[k].e;}cout<<"矩阵M的行列形式为:"<<"\n";for(k=1;k<=M.t;k++){a[M.data[k].i][M.data[k].j]=M.data[k].e;}for(c=1;c<=M.m;c++){for(d=1;d<=M.n;d++)cout<<a[c][d]<<"";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.data[k].i>>T.data[k].j>>T.data[k].e;}cout<<"矩阵T的行列形式为:"<<"\n";for(k=1;k<=T.t;k++){b[T.data[k].i][T.data[k].j]=T.data[k].e;}for(c=1;c<=T.m;c++){for(d=1;d<=T.n;d++)cout<<b[c][d]<<"";cout<<endl;}for(c=1;c<=M.m;c++){for(d=1;d<=M.n;d++){f[c][d]=a[c][d]-b[c][d];}}cout<<"两矩阵相减后的行列形式为："<<endl;for(c=1;c<=M.m;c++){for(d=1;d<=M.n;d++)cout<<f[c][d]<<"";cout<<endl;}}voidmul()//矩阵相乘{tripletableM;tripletableT;intm,n,t,i,j,e,k,c,d;inta[MAXSIZE][MAXSIZE]={0};intb[MAXSIZE][MAXSIZE]={0};intf[MAXSIZE][MAXSIZE]={0};cout<<"输入稀疏矩阵M的行数，列数和非零元个数：";cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k++){cout<<"输入第"<<k<<"个非零元素的行下标，列下标和值:";cin>>M.data[k].i>>M.data[k].j>>M.data[k].e;}cout<<"矩阵M的行列形式为:"<<"\n";for(k=1;k<=M.t;k++){a[M.data[k].i][M.data[k].j]