《数据结构 课程设计》稀疏矩阵实验报告.doc

目 录一、概述1二、 系统分析1三、 概要设计1（1)主界面的设计:2（2）系数矩阵的存储2（3）具体实现流程图：3四、详细设计4(2)稀疏矩阵的相加：5五、 运行与测试8六、 总结与心得8参考文献9源代码9一、概述稀疏矩阵的加法运算，既将稀疏矩阵A和B，他均为m行n列，分别以数组的形式存放在A和B中，实现A+B=C，将所得的结果存放在C数组中。2、 系统分析稀疏矩阵的保存：以一位数组顺序存放非零元素的行号、列号和数值，行号为-1作为结束符。以三个一维数组存放一个系数矩阵中的一个非零元素，为零额元素则不保存。用一个二重循环来实现判断每个系数矩阵的非零元素是否为零，不为零，就将其行列下标和其值存入一维数组中稀疏矩阵的相加：用循环来判断存储A何B稀疏矩阵的两个一维数组中的行列下标是否相等和其大小关系。若相等，则将两个一维数组的第三个元素的值相加存入新的数组C里，行列下标不变的存入进去；若A的列小于B的列，则将A的三个元素直接存入C中；若B的列小于A的列，则将B的三个元素村日C中；若A的行小于B的行，则将A的三个元素存入C中；若A的行大于B的行，则将B存入C中。3、 概要设计（1)主界面的设计:定义两个矩阵a= 0 0 3 0 0 0 0 0 b= 0 2 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 7 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0定义两个数组A和B，用于存储矩阵a和矩阵b的值；定义一个数组C，用于存放数组A和数组B相加后的结果。（2）系数矩阵的存储用一维数组存放系数矩阵A如下：A0=0，A1=2, A2=3, A3=1, A4=6, A5=5, A6=3, A7=4, A8=7, A9=5, A10=1, A11=9, A12=-1。用一维数组存放系数矩阵B如下：B0=0，B1=1,B2=2, B3=1,B4=3, B5=4, B6=2, B7=5, B8=6, B9=3, B10=4, B11=8, B12=4，B13=2，B14=1，B15=-1。（3）具体实现流程图：四、详细设计(1)稀疏矩阵的转存： void CreateMatrix(int Amn,int B50),这是一个将稀疏矩阵转存的函数，类似于顺序存储三元组表。在这个方法中，只要用一个二重循环来判断每个矩阵元素是否为零，若不为零，则将其行、列下标及其值存入到一维数组B中对应的元素。在定义函数的过程中，我们需要定义一个for循环，以完成行和列的转换及存储。在函数的末尾我们定义一个BK=-1，用于结束非零元素的存储。 算法如下：void CreateMatrix(int Amn,int B50)int i,j,k=0;for(i=0;im;i+)for(j=0;jn;j+)if(Aij!=0)Bk=i;k+;Bk=j;k+;Bk=Aij;k+;Bk=-1;(2)稀疏矩阵的相加： void MatrixAdd(int Amax,int Bmax,int Cmax),这个函数用于实现数组A和数组B的相加，并将其相加的结果存入数组C。这个函数讨论了数组在相加的过程中的几种情况：a、 A数组和B数组的行相等且列相等，两者直接相加后存入数组C中。if(Ai=Bj)if(Ai+1=Bj+1)Ck=Ai;Ck+1=Ai+1;Ck+2=Ai+2+Bj+2;k=k+3;i=i+3;j=j+3; b、A的列小于B的列，将A的三个元素直接存入C中if(Ai+1Bj+1)Ck=Bj;Ck+1=Bj+1;Ck+2=Bj+2;k=k+3;j=j+3;d、A的行小于B的行，将A的三个元素直接存入C中if(AiBj) Ck=Bj;Ck+1=Bj+1;Ck+2=Bj+2;k=k+3;j=j+3;f、A结束B还有元素，将B的所有元素直接存入C中if(Ai=-1)while(Bj!=-1)Ck=Bj;Ck+1=Bj+1;Ck+2=Bj+2;k=k+3;j=j+3;g、B结束A还有元素，将A的所有元素直接存入C中if(Bi=-1)while(Ai!=-1)Ck=Ai; Ck+1=Ai+1; Ck+2=Ai+2; k=k+3; i=i+3;最后定义Ck=-1,结束算法。5、 运行与测试 6、 总结与心得在本次试验中，我掌握了稀疏矩阵的存储与转存的相关知识，了解了两个稀疏矩阵的相加后的知识，并实现了稀疏矩阵的加法，明白在计算机中我们对稀疏矩阵的处理，可以很大程度上的节约我们的存储空间，是压缩原理的雏形。参考文献【1】数据结构严蔚敏.清华大学出版社.【2】数据结构课程设计苏仕华.极械工业出版社.【3】程序设计谭浩强 .清华大学出版社.源代码#include #define m 6 #define n 8 #define max 50/ 稀疏矩阵存储在数组中 int i,j,k=0; for(i=0;im;i+) for(j=0;jn;j+) if (Aij!=0) Bk=i; k+; Bk=j; k+; Bk=Aij; k+; Bk=-1;/两个稀疏矩阵存储到两个数组中后相加存储到另一个数组中void matrixadd(int Amax,int Bmax,int Cmax) int i=0,j=0,k=0; while (Ai!=-1&Bj!=-1) if (Ai=Bj) if (Ai+1=Bj+1) Ck=Ai; Ck+1=Ai+1; Ck+2=Ai+2+Bj+2; k=k+3; i=i+3; j=j+3; else if (Ai+1Bj+1) Ck=Ai; Ck+1=Ai+1; Ck+2=Ai+2; k=k+3; i=i+3; else Ck=Bj; Ck+1=Bj+1; Ck+2=Bj+2; k=k+3; j=j+3; else if (AiBj) Ck=Ai; Ck+1=Ai+1; Ck+2=Ai+2+Bj+2; k=k+3; i=i+3; else Ck=Bj; Ck+1=Bj+1; Ck+2=Bj+2; k=k+3; j=j+3; if (Ai=-1) while (Bj!=-1) Ck=Bj; Ck+1=Bj+1; Ck+2=Bj+2; k=k+3;j=j+3; else while(Ai!=-1) Ck=Ai; Ck+1=Ai+1; Ck+2=Ai+2; k=k+3; i=i+3; Ck=-1; /主函数 void main() int Emn,Fmn,Amax,Bmax,Cmax; int i,j,k; printf(输入稀疏矩阵E(%d,%d):n,m,n); for(i=0;im;i+) /输入稀疏矩阵E for(j=0;jn;j+) scanf(%d,&Eij); printf(输入稀疏矩阵F(%d,%d):n,m,n); for(i=0;im;i+)/输入稀疏矩阵F for(j=0;jn;j+) scanf(%d,&Fij); creatematrix(E,A);/ E稀疏矩阵存储在数组A中 creatematrix(F,B);/ F稀疏矩阵存储在数组B中 matrixadd(A,B,C);/相加 i=0;j=0;k=0; printf(A数组内容如下：n); while(Ai!=-1) printf(%5d,%5d,%5dn,Ai,Ai+1,Ai