数据结构与课程设计稀疏矩阵

1、实验课程名称 数据结构与课程设计 专 业 班 级 10级计科（2）班 学 生 姓 名 赵 腾 松 学 号 10410902044 指 导 教 师 冯 韵 2012 至 2013学年第 1 学期第 4 至 5 周目录1 概述11 系统分析12.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值12.2造函数并输出最终稀疏矩阵13 概要设计13.1存储结构设计13.2系统功能设计14 详细设计24.1 稀疏矩阵的存储24.2 稀疏矩阵的加法25 程序代码46 运行与测试77 总结与心得78 参考文献71 概述掌握稀疏矩阵的加法运算，稀疏矩阵的存储方法，每一个元素可能有多个直接前驱和多个直接后继。一

2、般情况下都是采用顺序存储方法来表示数组，但有时在实际应用中，一般的顺序存储方法已经不太实用。有时候用普通存储方法就会造成很大的空间浪费。为了节省存储单元，用压缩方法只存储非零元素。2 系统分析2.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值 本模块要求设计函数建立稀疏矩阵并初始化。在创建稀疏矩阵时需要设计稀疏矩阵的加法和存储方法，出现错误时能够对错误进行判别处理初始化稀疏矩阵都为空值。在设计输出稀疏矩阵的值的函数时也要针对两种不同的情况分别编制函数才能准确的输出稀疏矩阵。在对稀疏矩阵进行初始化时只输入非零元素的值和它所在的所在行及所在列。在对稀疏矩阵输出时以矩阵的完整形式输出。 2.2造

3、函数并输出最终稀疏矩阵 本模块要求设计加法函数对两个矩阵进行运算并输出最终的稀疏矩阵，操作后的结果矩阵的行、列数需要综合多方面情况来确定。这些函数也是整个程序的难点需要灵活运用数组及指针的特点。3 概要设计3.1存储结构设计以一维数组顺序存放非零元素的行号、列号和数值，行号-1作为结束标志。稀疏矩阵的存储类似于建立顺序存储稀疏矩阵的三元组表。假设a为一个稀疏矩阵，b为一个存储对应于a矩阵生成的数组。用一个二重循环来判断每个矩阵元素是否为零，若不为零，则将其行、列下标及其值存入到一维数组b中对应的元素中。3.2系统功能设计 设计稀疏矩阵的加法算法，假设两个稀疏矩阵a和b，它们均为m行n列，分别存

4、放在数组a和b中，编写矩阵的加法实现c=a+b的算法，c矩阵存放在数组c中。根据设计要求，首先要将一个稀疏矩阵对应存储到一个一维数组中，然后在进行矩阵加法时依次扫描矩阵a和b的行列值，并以行优先，当行列相同时，将第三个元素值相加的和以及行列号三个元素存入结果数组c中；不相同时，将a或b的三个元素直接存入结果数组中。4 详细设计4.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+;

5、bk=-1; /非零元素存储结束4.2 稀疏矩阵的加法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) /b的列小于a的列，将a的三个元素直接存入c中ck=ai;ck+1=ai+1;ck+2=ai+2;k=k+3;i=i+3;else /b的列小于a的列，将b的三个元素直接存入c中ck=b

6、j;ck+1=bj+1;ck+2=bj+2;k=k+3;j=j+3;else if(aibj) /a的行小于b的行，将a的三个元素直接存入c中ck=ai;ck+1=ai+1;ck+2=ai+2;k=k+3;i=i+3;else /b的行小于a的行，将b的三个元素直接存入c中ck=bj;ck+1=bj+1;ck+2=bj+2;k=k+3;j=j+3; /循环结束if(ai=-1)while(bj!=-1) /a结束b还有元素，将b的所有元素直接存入c中ck=bj;ck+1=bj+1;ck+2=bj+2;k=k+3;j=j+3;elsewhile(ai!=-1) /b结束a还有元素，将a的所有元素

7、直接存入c中ck=ai;ck+1=ai+1;ck+2=ai+2;k=k+3;i=i+3;ck=-1;5 程序代码#include#define m 3 /用户可根据需要定义原始矩阵行数#define n 3 /定义原始矩阵#define max 50void(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; /非零元素存储结束void matrixadd(int amax,int bmax,i

8、nt 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) /b的列小于a的列，将a的三个元素直接存入c中ck=ai;ck+1=ai+1;ck+2=ai+2;k=k+3;i=i+3;else /b的列小于a的列，将b的三个元素直接存入c中ck=bj;ck+1=bj+1;ck+2=bj+2;k=k+3;j=j+3;else if(aibj) /a的行小于b的行，将a的

9、三个元素直接存入c中ck=ai;ck+1=ai+1;ck+2=ai+2;k=k+3;i=i+3;else /b的行小于a的行，将b的三个元素直接存入c中ck=bj;ck+1=bj+1;ck+2=bj+2;k=k+3;j=j+3; /循环结束if(ai=-1)while(bj!=-1) /a结束b还有元素，将b的所有元素直接存入c中ck=bj;ck+1=bj+1;ck+2=bj+2;k=k+3;j=j+3;elsewhile(ai!=-1) /b结束a还有元素，将a的所有元素直接存入c中ck=ai;ck+1=ai+1;ck+2=ai+2;k=k+3;i=i+3;ck=-1;void main()

10、int emn,fmn,amax,bmax,cmax;int i,j,k;for(i=0;im;i+) /输入e矩阵的所有元素for(j=0;jn;j+)scanf(%d,&eij);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); /a,b相加存入c中i=0;j=0;k=0;printf(a数组内容如下：n);while(ai!=-1) /输出a中内容printf(%5d,%5d,%5dn,ai,ai+1,ai+2);i=i+3;printf(b数组内容如下：n);while(bj!=-1) /输出b中内容printf(%5d,%5d,%5dn,bj,bj+1,bj+2);j=j+3;printf(c数组内容如下：n);while(ck!=-1) /输出c中内容printf(%5d,%5d,%5dn,ck,ck+1,ck+2);k=k+3;6 运行与测试7 总结与心得在本次实验中遇到了很多问题，一开始的时候程序有很多错误，花了很多时间才调试成功。慢慢