数据结构课程设计报告--稀疏矩阵运算器

1闽江学院数据结构课程设计报告题目：稀疏矩阵运算器院系：计算机科学系专业班级：10计算机科学与技术（网络工程）学号：学生姓名：指导教师：王润鸿2011年12月23日2目录：1、分析问题和确定解决方案…………………………31.1问题描述……………………………31.2输入的形式和输入值的范围……………………31.3输出的形式………………………………31.4程序所能达到的功能……………………………31.5测试数据………………………………31.6确定解决方案………………………………41.7所有抽象数据类型的定义……………………………42、详细设计……………………………52.1稀疏矩阵加法运算思路……………………………52.2稀疏矩阵减法运算思路………………………………72.3稀疏矩阵乘法运算思路………………………………92.4创建稀疏矩阵………………………………113、系统调试与测试……………………………123.1程序的菜单界面………………………………123.2实现加法运算………………………………123.3实现减法运算………………………………133.4实现乘法运算………………………………144、结果分析……………………………………154.1、算法的时空分析………………………………154.2、经验和体会………………………………155、参考文献………………………………1531、分析问题和确定解决方案1.1问题描述稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。用三元组实现稀疏矩阵的相加、相减，相乘；1.2输入的形式和输入值的范围以三元组的形式输入，首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过20；例如：输入的三元组为：((1,1,10),(2,3,9),(3,1,-1))其对应的稀疏矩阵为：00190000101.3输出的形式运算结果的矩阵以通常的阵列形式输出；1.4程序所能达到的功能该程序可以实现以三元组形式输入两个矩阵，求出两个矩阵的和、差、积；并可根据输入的矩阵的行列数不同判别是否可以进行相加、减、乘，并重新输入正确的矩阵；1.5测试数据测试的数据及其结果如下：矩阵M矩阵N矩阵Q加法：0019000010+301100000=3008000010减法：0190010-311000=32100010乘法：4700000001000000010034X000001010024003=0000100080601.6确定解决方案进入运算器界面后选择要实行的操作，按1实现矩阵相加，调用函数AddSMatrix，若输入的两个矩阵行列数不相等，则提示输入错误，重新输入矩阵进行加法运算；按2实现矩阵相乘，若输入的第一矩阵的列数不等于第二个矩阵的行数，则提示输入错误，重新输入矩阵进行乘法运算；按3实现矩阵相减，若输入的两个矩阵行列数不相等，则提示输入错误，重新输入矩阵进行减法运算；按4退出程序以加法为例实现运算过程，如下：(稀疏矩阵的和为Q)第一个稀疏矩阵M的三元组为（（1,1,10）,(2,3,9),(3,1,-1)）第二个稀疏矩阵N的三元组为（（2,3,-1）,（3,1,1）,（3,3,-3））M的第一个三元组（1,1,10）与N的第一个三元组（2,3,-1）比较，因行数12则Q得到第一个三元组（1,1,10）；M的第二个三元组与N的第一个三元组比较，因对应行列数相等则9+（-1）=8，次行列数就是Q的行列数即得到Q的第二个三元组为（2,3,8）;M第三个三元组(3,1,-1)）与N的第二个三元组进行比较，因对应行列数相等，且1+（-1）=0，则不进行相加；而此时只有N的第三个三元组（3,3,-3）符合条件，则Q得到第三个三元组（3,3,-3）；最终结果为(（1,1,10）,(2,3,8）,(3,3,-3）)1.7所有抽象数据类型的定义以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方式——三元组顺序表。/*稀疏矩阵的三元组顺序表存储表示*/#defineMAXSIZE1000//假设非零元个数的最大值为1000typedefstruct{inti,j;//该非零元的行下标和列下标ElemTypee;//该非零元数值}Triple;typedefstruct{Tripledata[MAXSIZE+1];//非零三元组表，data[0]未用intmu,nu,tu;//矩阵的行数(20)、列数(20)和非零元个数}TSMatrix;在此，data域中表示非零元得三元组是以行序为主序顺序排列的，这样有利于进行某些矩阵运算。抽象数据类型稀疏矩阵的定义如下：ADTSparseMatrix{数据对象:D={aij|i=1,2,3,…，m;j=1,2,…，n;5Aij(-ElemSet,m和n分别称为矩阵的行数和列数}数据关系：R={Row,Col}基本操作：CreateSMatrix(&M);操作结果：创建稀疏矩阵M。PrintSMatrix(M);初始条件：稀疏矩阵M存在。操作结果：输出稀疏矩阵M。AddSMatrix(M,N,&Q);初始条件：稀疏矩阵M和N的的行数和列数对应相等。操作结果：求稀疏矩阵的和Q=Ｍ＋Ｎ。SubSMatrix(M,N,&Q);初始条件：稀疏矩阵M和N的的行数和列数对应相等。操作结果：求稀疏矩阵的差Q=M-N。MultSMatrix(M,N,&Q);初始条件：稀疏矩阵M的列数等于N的行数。操作结果：求稀疏矩阵的积Q=MXN。}ADTSpareMatrix此流程表示的是主程序的流程以及各程序模块之间的层次(调用)关系。2、详细设计2.1稀疏矩阵的加法运算思路比较满足条件(行数及列数都相同的两个矩阵)的两个稀疏矩阵中不为0的元素的行数及列数（即i与j），将i与j都相等的前后两个元素值e相加，保持i,j不变储存在新的三元组中，不等的则分别储存在此新三元组中。最后得到的1、矩阵相加输入矩阵2计算结果2、矩阵相乘输入矩阵1输入矩阵2计算结果3,、矩阵相减输入矩阵2计算结果4、退出输入矩阵1输入矩阵1稀疏矩阵运算器6这个新三元组表就是两个矩阵的和矩阵的三元组表。其算法如下：StatusAddSMatrix(TSMatrixM,TSMatrixN,TSMatrix&Q){if(M.mu==N.mu&&M.nu==N.nu)//行数,列数相等才能相加{Q.mu=M.mu;Q.nu=N.nu;intp,q,k;p=1;q=1;k=1;while(p=M.tu&&q=N.tu)//两个稀疏矩阵存在{if(M.data[p].i==N.data[q].i)//两个稀疏矩阵的行数相等{if(M.data[p].j==N.data[q].j)//两个稀疏矩阵的列数相等{if(M.data[p].e+N.data[q].e!=0)//两个稀疏矩阵相加的结果不为0（三元组表）{Q.data[k].i=M.data[p].i;Q.data[k].j=M.data[p].j;Q.data[k].e=M.data[p].e+N.data[q].e;++k;}++q;++p;}elseif(M.data[p].jN.data[q].j)//第一个稀疏矩阵列数小于第二个稀疏矩阵列数{Q.data[k]=M.data[p];//把M中的所有信息都赋给Q++p;++k;}else//第一个稀疏矩阵列数大于第二个稀疏矩阵的列数{Q.data[k]=N.data[q];++q;++k;}}elseif(M.data[p].iN.data[q].i)//第一个稀疏矩阵行列数小于第二个稀疏矩阵行数{Q.data[k]=M.data[p];++p;++k;7}else//第一个稀疏矩阵行列数小于第二个稀疏矩阵行数{Q.data[k]=N.data[q];++q;++k;}}while(p=M.tu)//只有M并且符合条件{Q.data[k]=M.data[p];++p;++k;}while(q=N.tu)//只有N并且符合条件{Q.data[k]=N.data[q];++q;++k;}Q.tu=k-1;printf(\t\t******两个矩阵的加法结果为******\n);returnOK;}else{printf(两个矩阵行,列数不等，出错了\n);CreateSMatrix(M);printf(第一个矩阵为:\n);PrintSMatrix(M);CreateSMatrix(N);printf(第二个矩阵为:\n);PrintSMatrix(N);printf(\n);AddSMatrix(M,N,Q);}}2.2稀疏矩阵相减的算法思路此思路与稀疏矩阵相加的算法思路相同，其算法如下：StatusSubtMatrix(TSMatrixM,TSMatrixN,TSMatrix&Q){if(M.mu==N.mu&&M.nu==N.nu)//行数，列数相等才能相减{Q.mu=M.mu;Q.nu=N.nu;intp,q,k;p=1;//M的第p个三元组q=1;//N的第q个三元组8k=1;//Q的第k个三元组while(p=M.tu&&q=N.tu)//两个稀疏矩阵存在{if(M.data[p].i==N.data[q].i)//两个稀疏矩阵的行数相等{if(M.data[p].j==N.data[q].j)//两个稀疏矩阵的列数相等{if(M.data[p].e-N.data[q].e!=0)//两个稀疏矩阵相减的结果不为0{Q.data[k].i=M.data[p].i;Q.data[k].j=M.data[p].j;Q.data[k].e=M.data[p].e-N.data[q].e;++k;}++q;++p;}elseif(M.data[p].jN.data[q].j)//第一个稀疏矩阵列数小于第二个稀疏矩阵的列数{Q.data[k]=M.data[p];++p;++k;}elseif(M.data[p].jN.data[q].j)//第一个稀疏矩阵列数大于第二个稀疏矩阵的列{Q.data[k].i=N.data[q].i;Q.data[k].j=N.data[q].j;Q.data[k].e=-N.data[q].e;//即0-N.data[q].e++q;++k;}}elseif(M.data[p].iN.data[q].i)//第一个稀疏矩阵行列数小于第二个稀疏矩阵行数{Q.data[k]=M.data[p];//整个三元组进行复制++p;++k;}if(M.data[p].iN.data[q].i)//第一个稀疏矩阵行列数大于第二个稀疏矩阵行数{Q.data[k].i=N.data[q].i;Q.data[k].j=N.data[q].j;Q.data[k].e=-N.data[q].e;//即0-N.data[q].e++q;++k;9}}while(p=M.tu)//只有M并且符合条件{Q.data[k]=M.data[p];++p;++k;}while(q=N.tu)//只有N并且符合条件{Q.data[k].i=N.data[q].i;Q.data[k].j=N.data[q].j;Q.data[k].e=-N.data[q].e;++q;++k;}Q.tu=k-1;printf(\t\t******两个矩阵的相减结果为******\n);returnOK;}else{printf(两个矩阵行列数不等，不能相减，请重新输入\n);CreateSMatrix(M);printf(第一个矩阵为:\n)