数据结构_基于三元组表关于系数矩阵的基本操作_课程设计__实验报告.doc

数 据 结 构 课 程 设 计设计题目：基于三元组表关于稀疏矩阵的基本操作 21课题名称基于三元组表关于系数矩阵的基本操作院 系年级专业学 号姓 名成 绩课题设计目的与设计意义1、课题设计目的：(1)掌握基于三元组表关于稀疏矩阵的基本操作,并通过相关的程序代码实现。(2)培养学生的编程能力、用计算机解决实际问题的能力。(3)了解软件的编制过程。2、课题设计意义：利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。大型稀疏矩阵技术的研究对解决广泛应用于计算科学、工程技术以及人文科学中的大型稀疏矩阵问题,具有重要的理论意义和实用价值。许多科学问题的计算尤其是大量的实际应用问题,通常被归结为稀疏矩阵的计算。因此研究稀疏矩阵的计算具有很重要的意义。指导教师：年 月 日目 录一、基本概念11.1转置矩阵11.2稀疏矩阵11.3三元组表1二、需求分析12.1基本要求12.2设计环境12.3建立矩阵12.4基本运算操作12.5测试12.6退出1三、概要设计13.1程序设计思想13.2主函数模块23.3自定义子程序模块2四、详细设计34.1程序的建立34.2 “菜单”界面34.3各个函数的详细设计34.3.1矩阵转置函数34.3.2矩阵相加函数44.3.3矩阵相减函数74.4退出程序9五、运行与测试105.1矩阵转置105.2矩阵相加115.3矩阵相减12六、总结和心得12七、附程序源代码13八、附 参考文献22一、基本概念1.1转置矩阵若将矩阵A的行换成相应的列，得到的新矩阵称为A的转置矩阵。1.2稀疏矩阵设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数，则称A为稀疏矩阵。1.3三元组表若将表示稀疏矩阵的非零元素三元组按行优先（或者列优先）的顺序排列（跳过零元素），则得到一个其结点均是三元组的线性表。我们将该线性表的顺序存储结构称为三元组表。二、需求分析2.1基本要求（1）要求用C+语言编程，在Visual C+环境下调试完成；（2）要求使用C+的结构体和自定义函数完成设计；（3）在VC+6.0环境中，学会调试程序的方法，及时查究错误，独立调试完成；（4）程序调试通过后，完成程序文档的整理。2.2设计环境（1）WINDOWS 2000/7/XP系统（2）Visual C+集成开发环境2.3建立矩阵首先输入A和B矩阵的行数和列数，只有先建立了矩阵，才能够对矩阵进行运算操作。2.4基本运算操作转置运算先输入一个矩阵，再输出相应的转置矩阵。加减运算操作由两个矩阵同时参与，对其进行加法运算和减法运算。2.5测试输入数据并打印出结果。2.6退出当做完矩阵的运算操作后，根据提示退出该界面。程序存储用三元组表表示，按行优先表示。在三元组表表示稀疏矩阵的运算结果矩阵另生成。三、概要设计3.1程序设计思想（1）输出存储矩阵的算法（2）存储稀疏矩阵用三元组表表示（3）稀疏矩阵的操作算法编写（4）输出稀疏矩阵3.2主函数模块void main() 主要包括对子函数的调用，以及结束程序等。3.3自定义子程序模块输入A矩阵void creata(spmatrix *a)输入B矩阵void creatb(spmatrix *a)输入需要转置的矩阵void creatc(spmatrix *a)输出三元组表void print(spmatrix *a)输出矩阵void printjuzhen(spmatrix *a)转置函数spmatrix *transmat(spmatrix *a)相加函数spmatrix * xiangjia(spmatrix *a,spmatrix *b)相减函数spmatrix * xiangjian(spmatrix *a,spmatrix *b)3.4具体实现流程图开始输入一个矩阵输入A矩阵输入B矩阵函数调用结束输出AB矩阵的和输出AB矩阵的差输出该矩阵的转置矩阵四、详细设计4.1程序的建立定义相关结构类型及其他：#define smax 16typedef int datatype;typedef structint i,j;datatype v;node;typedef structint m,n,t;node datasmax;spmatrix;4.2 “菜单”界面进入稀疏矩阵运算系统后的“菜单”界面如下图1所示 图1 “菜单”界面4.3各个函数的详细设计4.3.1矩阵转置函数函数如下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;cola-n;col+)for(pa=0;paa-t;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); 4.3.2矩阵相加函数函数如下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(paa-tpbb-t)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.jb-datapb.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.ib-datapb.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(paa-t)c-datapc.v=a-datapa.v; c-datapc.i=a-datapa.i; c-datapc.j=a-datapa.j; pc+;pa+;while(pbb-t)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);4.3.3矩阵相减函数函数如下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(paa-tpbb-t)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.jb-datapb.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.ib-datapb.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(paa-t)c-datapc.v=a-datapa.v; c-datapc.i=a-datapa.i; c-datapc.j=a-datapa.j; pc+;pa+;while(pbb-t)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);4.4退出程序printf(tttt继续请按1ntttt退出请按0n); scanf(%d,i);如下图2 图2 退出程序五、运行与测试5.1矩阵转置图2如下 图2矩阵转置5.2矩阵相加图3如下 图3 矩阵相加5.3矩阵相减图4如下 图4 矩阵相减六、总结和心得首先必须了解稀疏矩阵的概念、存储及矩阵的基本运算，三元组表的存储表示，其次对三元组表的输入运算，加法运算的输入算法，必须上网认真了解，认真分析。最后，在对输入程序的运行情况做认真的错误分析，总结出错原因。通过这次实践，自己对软件有更深的了解，对计算机的硬件运行也有一定的认识。七、附程序源代码 #includestdio.h#define smax 16typedef int datatype;typedef structint i,j;datatype v;node;typedef structint m,n,t;node datasmax;spmatrix;void creatt(spmatrix *a)int k;printf(n 请输入一个矩阵的行数、列数、非零元素个数n);scanf(%d%d%d,a-m,a-n,a-t);printf(n 请输入该矩阵非零元素所在的行号、列号、非零元素的值n);for(k=0;ka-t;k+)scanf(%d%d%d,a-datak.i,a-datak.j,a-datak.v);void creata(spmatrix *a)int k;printf(n 请输入A矩阵的行数、列数、非零元素个数n);scanf(%d%d%d,a-m,a-n,a-t);printf(n 请输入该矩阵非零元素所在的行号、列号、非零元素的值n);for(k=0;ka-t;k+)scanf(%d%d%d,a-datak.i,a-datak.j,a-datak.v);void creatb(spmatrix *a)int k;printf(n 请输入B矩阵的行数、列数、非零元素个数n);scanf(%d%d%d,a-m,a-n,a-t);printf(n 请输入该矩阵非零元素所在的行号、列号、非零元素的值n);for(k=0;ka-t;k+)scanf(%d%d%d,a-datak.i,a-datak.j,a-datak.v);void print(spmatrix *a)int k;for(k=0;ka-t;k+)printf(%dt%dt%dn,a-datak.i,a-datak.j,a-datak.v);void printjuzhen(spmatrix *a)int k,p,l;int c55=0,0,0,0,0;for(k=0;ka-t;k+)ca-datak.ia-datak.j=a-datak.v;for(p=0;pa-m;p+)for(l=0;la-n;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(paa-tpbb-t)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.jb-datapb.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.ib-datapb.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(paa-t)c-datapc.v=a-datapa.v; c-datapc.i=a-datapa.i; c-datapc.j=a-datapa.j; pc+;pa+;while(pbb-t)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(paa-tpbb-t)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.jb-datapb.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.ib-datapb.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(paa-t)c-datapc.v=a-datapa.v; c-datapc.i=a-datapa.i; c-datapc.j=a-datapa.j; pc+;pa+;while(pbb-t)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;cola-n;col+)for(pa=0;paa-t;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,j;printf(nttt基于三元组表关于稀疏矩阵的基本操作n);while(i) printf(n#);printf(# ttttttt #); printf(#t矩阵转置请按1t矩阵相加请按2t矩阵相减请按3 #);printf(# ttttttt #); printf(#n);scanf(%d,j);switch(j)case 1: a=(spmatrix *)malloc(sizeof(spmatrix);c=(