数据结构 基于三元组表的存储结构实现稀疏矩阵的应用 课程设计 实验报告.doc

数 据 结 构 课 程 设 计设计题目：基于三元组表的存储结构实现稀疏矩阵的应用课题名称基于三元组表的存储结构实现稀疏矩阵的应用院 系年级专业学 号姓 名成 绩课题设计目的与设计意义1、 课题设计目的：（1） 熟练的掌握三元组表的存储结构来实现稀疏矩阵的应用。（2） 让同学们能够很好的将数据结构的思想转化为C语言程序并进行运行生成答案。（3） 提高同学们的编程能力。（4） 使同学们更注重编程的思想而不单单是编程。（5） 同时也为了今后的学习打下基础。2、 课题设计意义：由于矩阵在程序中常使用二维阵列表示，二维阵列的大小与使用的存储器空间成正比，如果多数元素没有数据，则会造成存储器空间的浪费，为此，必须设计稀疏矩阵的阵列储存方式，利用较少的存储器空间储存完整的矩阵数据。由于稀疏矩阵中含有很多的0元素，在计算机中存储会浪费很多的空间，因此我们通常采用压缩存储的方法。其意义是让我们在学习完C、数据结构等课程基础上，掌握多维数组的逻辑结构和存储结构、掌握稀疏矩阵的压缩存储及转置，相加等基本操作，并用不同的方法输出结果，进 一步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。指导教师：年 月 日目 录一、课程设计的目的及意义11.1 目的11.2 意义1二、需求分析12.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值12.2构造函数进行稀疏矩阵的转置并输出结果12.3构造函数进行两稀疏矩阵相加、减及转置并输出结果22.4退出系统22.5 开发环境2三、概要设计23.1 主界面的设计23.2存储结构的设计23.3 模块图33.4 流程图4四、详细设计44.1 设计思路及方案44.2 主调函数44.3 建立矩阵54.4 建立三元组表54.5 矩阵相加64.6 矩阵相减64.7 矩阵转置64.8 退出系统7五、系统的实现与调试以及运行结果75.1 系统的实现75.2系统的调试75.3 系统的运行结果8六、心得体会与总结116.1 心得体会116.2 总结11附录11参考文献19一、课程设计的目的及意义1.1 目的（1）熟练的掌握三元组表的存储结构来实现稀疏矩阵的应用。（2）让同学们能够很好的将数据结构的思想转化为C语言程序并进行运行生成答案。（3）提高同学们的编程能力。（4）使同学们更注重编程的思想而不单单是编程。（5）同时也为了今后的学习打下基础。1.2 意义由于矩阵在程序中常使用二维阵列表示，二维阵列的大小与使用的存储器空间成正比，如果多数元素没有数据，则会造成存储器空间的浪费，为此，必须设计稀疏矩阵的阵列储存方式，利用较少的存储器空间储存完整的矩阵数据。由于稀疏矩阵中含有很多的0元素，在计算机中存储会浪费很多的空间，因此我们通常采用压缩存储的方法。其意义是让我们在学习完C、数据结构等课程基础上，掌握多维数组的逻辑结构和存储结构、掌握稀疏矩阵的压缩存储及转置，相加等基本操作，并用不同的方法输出结果，进 一步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。二、需求分析2.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值本模块要求设计函数建立稀疏矩阵并初始化， 包括在三元组结构下和十字链 表结构下。在创建稀疏矩阵时，需要设计两个不同的函数分别在三元组和十字链 表下创建稀疏矩阵，在输入出现错误时，能够对错误进行判别处理，初始化稀疏 矩阵都为空值。在设计输出稀疏矩阵的值的函数时，也要针对两种不同的情况， 分别编制函数，才能准确的输出稀疏矩阵。在对稀疏矩阵进行初始化时，只输入非零元素的值和它所在的所在行及所在列。在对稀疏矩阵输出时，以矩阵的完整 形式输出。2.2构造函数进行稀疏矩阵的转置并输出结果本模块要求设计函数进行稀疏矩阵的转置并输出转置后的结果。 在编写函数时，要先定义一个相应的结构体变量用于存放转置后的矩阵，最后把此矩阵输出。2.3构造函数进行两稀疏矩阵相加、减及转置并输出结果本模块要求设计相加、减和相乘函数对两个矩阵进行运算，并输出最终的稀 疏矩阵，定义相应的矩阵类型用于存放两个矩阵操作后的结果矩阵，这个结果矩 阵的行、列数需要综合多方面情况来确定。这些函数也是整个程序的难点，需要 灵活运用数组及指针的特点。2.4退出系统本模块要求设置选项能随时结束程序的运行， 本程序中采用 while 循环。 程序在计算机上显示“提示信息”之后，由用户在键盘上输入演示程序中需要的 相关信息及命令。2.5 开发环境 Microsoft visual C+ 6.0三、概要设计3.1 主界面的设计 图1 主界面设计3.2存储结构的设计三元组结构体定义 typedef structint i,j;datatype v;node;typedef structint m,n,t;node datasmax;spmatrix;3.3 模块图稀疏矩阵应用系统创建矩阵创建三元组表矩阵的转置矩阵的加法矩阵的减法3.4 流程图Main()函数Switch()函数创建矩阵矩阵相加矩阵相减矩阵转置创建三元组表矩阵行列是否相等Yxingjia()函数N矩阵行列是否相等xingjian()函数YN四、详细设计4.1 设计思路及方案思路：通过三元组表的存储结构先对稀疏矩阵进行存储，存储过后在三元组表里进行矩阵的基本操作，最后再以三元组表的形式或矩阵形式输出。方案：先建立一个三元组表的存储结构，通过主函数里调用其它函数实现操作，前提是矩阵的相加、相减和转置函数已经完成。4.2 主调函数主调函数是一个C程序必备的函数，它可以对其它函数进行调用以达到便利的效果。具体实现如下：void main()spmatrix *a,*b,*c;int i=1,j; printf(*nn);printf(ttt 欢迎来到稀疏矩阵应用系统!nnn);printf(*n);while(i)printf(tttt1-创建矩阵ntttt2-创建三元组表ntttt3-矩阵相加n);printf(tttt4-矩阵相减ntttt5-矩阵转置ntttt0-退出系统ntt);scanf(%d,&j);switch(j)if(i!=0)printf(nntttt0-退出系统ntttt1-继续操作ntt);scanf(%d,&i);4.3 建立矩阵 要实现稀疏矩阵的应用必须先建立矩阵，所以矩阵的建立是必不可少的，这在本算法中也起到了至关重要的作用。矩阵的建立是在三元组表的基础上实现的，只要创建好了三元组表直接按三元组表输出矩阵即可。体实现如下：a=(spmatrix *)malloc(sizeof(spmatrix);creat(a);printf(tt你创建的矩阵如下:n);printjuzhen(a);break;4.4 建立三元组表所谓稀疏矩阵就是其中非零元素的个数较少，因此会用到三元组表的存储结构，所以建立三元组表也是必要的。建立三元组表就是输入矩阵中非零元素的信息，如行号、列号、非零元素的值。将信息依次输入再以三元组表的形式输出即可得到创建的三元组表。具体实现如下：a=(spmatrix *)malloc(sizeof(spmatrix);creat(a);printf(tt你创建的三元组表如下:n);print(a);break;4.5 矩阵相加 矩阵相加是矩阵中最基本的运算之一，既然能够相加说明这两个矩阵是等行等列的，所以在两个矩阵相加之前必须要先做出判断，判断是否可以相加。矩阵相加就是将矩阵中的元素对应相加组成一个新矩阵，将这个新矩阵输出即可得到相加后矩阵。具体实现如下:a=(spmatrix *)malloc(sizeof(spmatrix); b=(spmatrix *)malloc(sizeof(spmatrix);c=(spmatrix *)malloc(sizeof(spmatrix);printf(tt请输入第一个矩阵的信息n); creat(a); printf(tt请输入第二个矩阵的信息n);creat(b);if(a-m!=b-m|a-n!=b-n)printf(tt对不起! 你输入的矩阵的行列不相等不能相加!n);break;4.6 矩阵相减 矩阵相减也是矩阵中最基本的运算之一，同矩阵相加一样如果要对两个矩阵进行减法运算同样需要判断矩阵的行列是否相等，如果相等才可以进行矩阵相减运算。具体实现如下：a=(spmatrix *)malloc(sizeof(spmatrix); b=(spmatrix *)malloc(sizeof(spmatrix);c=(spmatrix *)malloc(sizeof(spmatrix);printf(tt请输入第一个矩阵的信息n); creat(a);printf(tt请输入第二个矩阵的信息n);creat(b); if(a-m!=b-m|a-n!=b-n)printf(tt对不起! 你输入的矩阵的行列不相等不能相减!n);break;4.7 矩阵转置 众所周知只要是个矩阵它就有它的转置矩阵，转置矩阵也很好求。首先要先建立矩阵，建立之后只要将二维数组中行列的下标对换即可。具体实现如下： a=(spmatrix *)malloc(sizeof(spmatrix);c=(spmatrix *)malloc(sizeof(spmatrix);printf(tt请输入你要转置的矩阵的信息n); creat(a);printf(tt你输入的三元组表的信息如下:n); print(a);printf(tt三元组表对应的矩阵如下:n);printjuzhen(a);printf(tt转置后的三元组表的信息如下:n);c=transmat(a);print(c);printf(tt转置后的三元组表对应的矩阵如下:n);printjuzhen(c);break;4.8 退出系统退出系统其实只是退出循环就可以了，要想退出循环只要结束while（i）即可。因此将0赋给while（i）循环即可。具体实现如下：i=0；break；五、系统的实现与调试以及运行结果5.1 系统的实现系统的实现主要由以下几个函数组成： creat(spmatrix *a)；此函数的功能是创建三元组表，节省内存空间，为矩阵的操作打下基础。 print(spmatrix *a)；此函数的功能是输出三元组表，以便使用者更加直观的看出矩阵的元素信息。 printjuzhen(spmatrix *a)；此函数是做输出矩阵之用，光输出三元组表没有输出矩阵更加直观，输出矩阵也可以和三元组表形成对比，检验输出结果是否出错； spmatrix * xiangjia(spmatrix *a,spmatrix *b)；此函数是用来完成矩阵相加运算的，并且输出相加后的结果，结果以三元组表和矩阵形式输出。 spmatrix * xiangjian(spmatrix *a,spmatrix *b)；此函数是用来完成矩阵相减运算的，并且输出相减后的结果，结果以三元组表和矩阵形式输出。 spmatrix *transmat(spmatrix *a)；此函数是矩阵的转置函数，通过它可以计算出矩阵的转置矩阵，并以三元组表和矩阵形式输出。5.2系统的调试编译链接执行图2 执行界面5.3 系统的运行结果创建矩阵图3 矩阵的创建创建三元组表图4 三元组表的创建矩阵相加图5 矩阵的相加矩阵相减图6 矩阵的相减矩阵转置图7 矩阵的转置六、心得体会与总结6.1 心得体会曾经在编程上遇到过很多困难，编了一学期的程序，有时会因为编出作业题目而又高兴几天，有时会因编不出程序而失落几天，总之，我喜欢 编程的过程，包括与同学交流，上网百度，从中学到了很多。 此次的课程设计更让我们意识到了数据结构的高深， 与小组成员的讨论让我们学到了更多关于数据结构的知识，这是一次团队合作的收获成果。6.2 总结在本次课程设计中，我掌握了稀疏矩阵的存储以及应用的相关知识。我通过程序编写出了矩阵的一些操作，包括矩阵的相加、相减、转置等。并且我知道稀疏矩阵的应用可以很大程度的减少存储空间。从中我也学到很多。不管是讨论交流还是百度搜索我都学到了东西。从而我也知道我们要学的东西还有很多很多。但是我会去慢慢积累！附录源代码：#include#define smax 20typedef int datatype;typedef structint i,j; /矩阵的行号列号datatype v; /矩阵的值node;typedef structint m,n,t; /矩阵的行列及非零元素的个数node datasmax; /非零元素个数为SMAX的数组spmatrix;void creat(spmatrix *a) /创建三元组表int k;printf(tt请输入矩阵的行数、列数、非零元素个数:ntt);scanf(%d%d%d,&a-m,&a-n,&a-t);printf(tt请输入非零元素所在的行号、列号、非零元素的值:n);for(k=0;kt;k+)printf(tt); scanf(%d%d%d,&a-datak.i,&a-datak.j,&a-datak.v);void print(spmatrix *a) /输出三元组表 int k;printf(tt行号t列号t值n);for(k=0;kt;k+)printf(tt%dt%dt%dn,a-datak.i,a-datak.j,a-datak.v);void printjuzhen(spmatrix *a) /输出矩阵int k,p,l;int c1010=0,0,0,0,0,0,0,0,0,0;for(k=0;kt;k+)ca-datak.ia-datak.j=a-datak.v;for(p=0;pm;p+)printf(tt);for(l=0;ln;l+)printf(%dt,cpl);printf(n);spmatrix * xiangjia(spmatrix *a,spmatrix *b) /矩阵相加运算spmatrix *c;int pa=0,pb=0,pc=0,sum=0;c=(spmatrix *)malloc(sizeof(spmatrix);if(a-m=b-m)&(a-n=b-n)c-m=a-m;c-n=a-n;while(pat&pbt)if(a-datapa.i=b-datapb.i)if(a-datapa.j=b-datapb.j)sum=a-datapa.v+b-datapb.v;if(sum)c-datapc.v=sum;c-datapc.i=a-datapa.i;c-datapc.j=a-datapa.j;pc+;pa+;pb+;elseif(a-datapa.jdatapb.j)if(a-datapa.v)c-datapc.v=a-datapa.v;c-datapc.i=a-datapa.i;c-datapc.j=a-datapa.j;pc+;pa+;elseif(b-datapb.v)c-datapc.v=b-datapb.v;c-datapc.i=b-datapb.i;c-datapc.j=b-datapb.j;pc+;pb+;elseif(a-datapa.idatapb.i)if(a-datapa.v)c-datapc.v=a-datapa.v; c-datapc.i=a-datapa.i; c-datapc.j=a-datapa.j; pc+;pa+;elseif(b-datapb.v)c-datapc.v=b-datapb.v; c-datapc.i=b-datapb.i; c-datapc.j=b-datapb.j; pc+;pb+;elsereturn(0);while(pat)c-datapc.v=a-datapa.v; c-datapc.i=a-datapa.i; c-datapc.j=a-datapa.j; pc+;pa+;while(pbt)c-datapc.v=b-datapb.v; c-datapc.i=b-datapb.i;c-datapc.j=b-datapb.j;pc+;pb+;c-t=pc;return(c);spmatrix * xiangjian(spmatrix *a,spmatrix *b) /矩阵相减运算spmatrix *c;int pa=0,pb=0,pc=0,sum=0;c=(spmatrix *)malloc(sizeof(spmatrix);if(a-m=b-m)&(a-n=b-n)c-m=a-m;c-n=a-n;while(pat&pbt)if(a-datapa.i=b-datapb.i)if(a-datapa.j=b-datapb.j)sum=a-datapa.v-b-datapb.v;if(sum)c-datapc.v=sum;c-datapc.i=a-datapa.i;c-datapc.j=a-datapa.j;pc+;pa+;pb+;elseif(a-datapa.jdatapb.j)if(a-datapa.v)c-datapc.v=a-datapa.v;c-datapc.i=a-datapa.i;c-datapc.j=a-datapa.j;pc+;pa+;elseif(b-datapb.v)c-datapc.v=-(b-datapb.v);c-datapc.i=b-datapb.i;c-datapc.j=b-datapb.j;pc+;pb+;elseif(a-datapa.idatapb.i)if(a-datapa.v)c-datapc.v=a-datapa.v; c-datapc.i=a-datapa.i; c-datapc.j=a-datapa.j; pc+;pa+;elseif(b-datapb.v)c-datapc.v=-(b-datapb.v); c-datapc.i=b-datapb.i; c-datapc.j=b-datapb.j; pc+;pb+;elsereturn(0);while(pat)c-datapc.v=a-datapa.v; c-datapc.i=a-datapa.i; c-datapc.j=a-datapa.j; pc+;pa+;while(pbt)c-datapc.v=-(b-datapb.v); c-datapc.i=b-datapb.i;c-datapc.j=b-datapb.j;pc+;pb+;c-t=pc;return(c);spmatrix *transmat(spmatrix *a) /矩阵的转置int pa,pb,col;spmatrix *b;b=(spmatrix *)malloc(sizeof(spmatrix);b-m=a-n;b-n=a-m;b-t=a-t;if(b-t0)pb=0;for(col=0;coln;col+)for(pa=0;pat;pa+)if(a-datapa.j=col)b-datapb.i=a-datapa.j;b-datapb.j=a-datapa.i;b-datapb.v=a-datapa.v;pb+;return(b); void main()spmatrix *a,*b,*c;int i=1,j; printf(*nn);printf(ttt 欢迎来到稀疏矩阵应用系统!nnn);printf(*n);while(i)printf(tttt1-创建矩阵ntttt2-创建三元组表ntttt3-矩阵相加n);printf(tttt4-矩阵相减ntttt5-矩阵转置ntttt0-退出系统ntt);scanf(%d,&j);switch(j)case 0:i=0;break;case 5: a=(spmatrix *)malloc(sizeof(spmatrix);c=(spmatrix *)malloc(sizeof(spmatrix);printf(tt请输入你要转置的矩阵的信息n); creat(a);printf(tt你输入的三元组表的信息如下:n); print(a);printf(tt三元组表对应的矩阵如下:n);printjuzhen(a);printf(tt转置后的三元组表的信息如下:n);c=transmat(a);print(c);printf(tt转置后的三元组表对应的矩阵如下:n);printjuzhen(c);break; case 3: a=(spmatrix *)malloc(sizeof(spmatrix); b=(spmatrix *)malloc(sizeof(spmatrix