闽江学院数据结构课程设计报告题目：稀疏矩阵运算器院系：计算机科学系专业班级：10计算机科学与技术（网络工程）学号：学生姓名：指导教师：王润鸿2011年12月23 日目录：1、分析问题和确定解决方案 (3)1.1问题描述 (3)1.2 输入的形式和输入值的范围 (3)1.3 输出的形式 (3)1.4 程序所能达到的功能 (3)1.5 测试数据 (3)1.6 确定解决方案 (4)1.7所有抽象数据类型的定义 (4)2、详细设计 (5)2.1稀疏矩阵加法运算思路 (5)2.2稀疏矩阵减法运算思路 (7)2.3稀疏矩阵乘法运算思路 (9)2.4创建稀疏矩阵 (11)3、系统调试与测试 (12)3.1程序的菜单界面 (12)3.2 实现加法运算 (12)3.3 实现减法运算 (13)3.4实现乘法运算 (14)4、结果分析 (15)4.1、算法的时空分析 (15)4.2、经验和体会 (15)5、参考文献 (15)1、分析问题和确定解决方案1.1问题描述稀疏矩阵是指那些多数元素为零的矩阵。

利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。

实现一个能进行稀疏矩阵基本运算的运算器。

用三元组实现稀疏矩阵的相加、相减，相乘；1.2输入的形式和输入值的范围以三元组的形式输入，首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。

可设矩阵的行数和列数均不超过20；例如：输入的三元组为：((1,1,10),(2,3,9),(3,1,-1))其对应的稀疏矩阵为：⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-0019000010 1.3 输出的形式运算结果的矩阵以通常的阵列形式输出； 1.4程序所能达到的功能该程序可以实现以三元组形式输入两个矩阵，求出两个矩阵的和、差、积；并可根据输入的矩阵的行列数不同判别是否可以进行相加、减、乘，并重新输入正确的矩阵；1.5测试数据测试的数据及其结果如下：矩阵M 矩阵N 矩阵Q加法：⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-0019000010 +⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--301100000 = ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-3008000010 减法：⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-0190010 - ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--311000 = ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-32100010 乘法：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡-70000001000000010034 X ⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡000001010024003 =⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡-000010008060 1.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）比较，因行数1<2则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所有抽象数据类型的定义以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方式——三元组顺序表。

/* 稀疏矩阵的三元组顺序表存储表示 */#define MAXSIZE 1000 //假设非零元个数的最大值为1000 typedef struct{ int i,j; //该非零元的行下标和列下标 ElemType e; //该非零元数值 } Triple;typedef struct{ Triple data[MAXSIZE+1]; // 非零三元组表，data[0]未用int mu,nu,tu; //矩阵的行数(<20)、列数(<20)和非零元个数 } TSMatrix;在此，data 域中表示非零元得三元组是以行序为主序顺序排列的，这样有利于进行某些矩阵运算。

抽象数据类型稀疏矩阵的定义如下： ADT SparseMatrix{数据对象:D={aij|i=1,2,3,…，m;j=1,2,…，n;Aij(-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=M X N。

}ADT SpareMatrix此流程表示的是主程序的流程以及各程序模块之间的层次(调用)关系。

2、详细设计2.1稀疏矩阵的加法运算思路比较满足条件(行数及列数都相同的两个矩阵)的两个稀疏矩阵中不为0的元素的行数及列数（即i与j），将i与j都相等的前后两个元素值e相加，保持i,j不变储存在新的三元组中，不等的则分别储存在此新三元组中。

最后得到的这个新三元组表就是两个矩阵的和矩阵的三元组表。

其算法如下：Status AddSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q){if(M.mu==N.mu&&M.nu==N.nu) //行数,列数相等才能相加{Q.mu=M.mu;Q.nu=N.nu;int p,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;}else if(M.data[p].j<N.data[q].j)//第一个稀疏矩阵列数小于第二个稀疏矩阵列数{Q.data[k]=M.data[p];//把M中的所有信息都赋给Q++p;++k;}else//第一个稀疏矩阵列数大于第二个稀疏矩阵的列数{Q.data[k]=N.data[q];++q;++k;}}else if(M.data[p].i<N.data[q].i)//第一个稀疏矩阵行列数小于第二个稀疏矩阵行数{Q.data[k]=M.data[p];++p;++k;}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");return OK;}else{printf("两个矩阵行,列数不等，出错了\n");CreateSMatrix(M);printf("第一个矩阵为:\n");PrintSMatrix(M);CreateSMatrix(N);printf("第二个矩阵为:\n");PrintSMatrix(N);printf("\n");AddSMatrix(M,N,Q);}}2.2稀疏矩阵相减的算法思路此思路与稀疏矩阵相加的算法思路相同，其算法如下：Status SubtMatrix(TSMatrix M, TSMatrix N,TSMatrix &Q){if(M.mu==N.mu && M.nu==N.nu) //行数，列数相等才能相减{Q.mu=M.mu;Q.nu=N.nu;int p,q,k;p=1; //M的第p个三元组q=1; //N的第q个三元组k=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;}else if(M.data[p].j<N.data[q].j)//第一个稀疏矩阵列数小于第二个稀疏矩阵的列数{Q.data[k]=M.data[p];++p;++k;}else if(M.data[p].j>N.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;}}else if(M.data[p].i<N.data[q].i)//第一个稀疏矩阵行列数小于第二个稀疏矩阵行数{Q.data[k]=M.data[p]; //整个三元组进行复制++p;++k;}if(M.data[p].i>N.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;}}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");return OK;}else{printf("两个矩阵行列数不等，不能相减，请重新输入\n");CreateSMatrix(M);printf("第一个矩阵为:\n");PrintSMatrix(M);CreateSMatrix(N);printf("第二个矩阵为:\n");PrintSMatrix(N);printf("\n");SubtMatrix(M,N,Q);}}2.3稀疏矩阵相乘的算法思路两个相乘的矩阵为M与N，对M中每个元素M.data[p](p=1,2,…,M.tu),找到N中所有满足条件M.data[p].j=N.data[q].i的元素N.data[q]，求得M.data[p].v 和N.data[q].v的乘积，又T(i,j)=∑M(i,k)×N(k,j),乘积矩阵T中每个元素的值是个累计和，这个乘积M.data[p].v×N.data[q].v只是T[i][j]中的一部分。