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

闽江学院数据结构课程设计报告题目： 稀疏矩阵运算器 院 系： 计算机科学系 专业班级：10计算机科学与技术（网络工程） 学 号： 学生姓名： 指导教师： 王润鸿 2011年12月23 日 目录：1、分析问题和确定解决方案 3 1.1问题描述 3 1.2 输入的形式和输入值的范围 3 1.3 输出的形式 31.4 程序所能达到的功能 31.5 测试数据 31.6 确定解决方案 41.7所有抽象数据类型的定义 42、详细设计 5 2.1稀疏矩阵加法运算思路 5 2.2稀疏矩阵减法运算思路 7 2.3稀疏矩阵乘法运算思路 9 2.4创建稀疏矩阵 113、系统调试与测试 123.1程序的菜单界面 123.2 实现加法运算 123.3 实现减法运算 133.4实现乘法运算 144、结果分析 154.1、算法的时空分析 154.2、经验和体会 155、参考文献 151、分析问题和确定解决方案1.1问题描述 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。用三元组实现稀疏矩阵的相加、相减，相乘；1.2输入的形式和输入值的范围 以三元组的形式输入，首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过20；例如：输入的三元组为：(1,1,10),(2,3,9),(3,1,-1)其对应的稀疏矩阵为： 1.3 输出的形式 运算结果的矩阵以通常的阵列形式输出；1.4程序所能达到的功能 该程序可以实现以三元组形式输入两个矩阵，求出两个矩阵的和、差、积；并可根据输入的矩阵的行列数不同判别是否可以进行相加、减、乘，并重新输入正确的矩阵；1.5测试数据 测试的数据及其结果如下： 矩阵M 矩阵N 矩阵Q加法： + = 减法： - = 乘法： X = 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）比较，因行数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所有抽象数据类型的定义以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方式三元组顺序表。 /* 稀疏矩阵的三元组顺序表存储表示 */#define MAXSIZE 1000 /假设非零元个数的最大值为1000typedef structint i,j; /该非零元的行下标和列下标ElemType e; /该非零元数值 Triple;typedef struct Triple dataMAXSIZE+1; / 非零三元组表，data0未用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此流程表示的是主程序的流程以及各程序模块之间的层次(调用)关系。稀疏矩阵运算器1、矩阵相加输入矩阵2计算结果2、矩阵相乘输入矩阵1输入矩阵2计算结果3,、矩阵相减输入矩阵2计算结果4、退出输入矩阵1输入矩阵12、详细设计 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.datap.i=N.dataq.i)/两个稀疏矩阵的行数相等if(M.datap.j=N.dataq.j) /两个稀疏矩阵的列数相等if(M.datap.e+N.dataq.e!=0) /两个稀疏矩阵相加的结果不为0（三元组表）Q.datak.i=M.datap.i;Q.datak.j=M.datap.j;Q.datak.e=M.datap.e+N.dataq.e;+k;+q;+p;else if(M.datap.jN.dataq.j) /第一个稀疏矩阵列数小于第二个稀疏矩阵列数Q.datak=M.datap; /把M中的所有信息都赋给Q+p;+k;else /第一个稀疏矩阵列数大于第二个稀疏矩阵的列数Q.datak=N.dataq;+q;+k;else if(M.datap.iN.dataq.i) /第一个稀疏矩阵行列数小于第二个稀疏矩阵行数Q.datak=M.datap;+p;+k;else /第一个稀疏矩阵行列数小于第二个稀疏矩阵行数Q.datak=N.dataq;+q;+k;while(p=M.tu) /只有M并且符合条件Q.datak=M.datap;+p;+k;while(q=N.tu) /只有N并且符合条件Q.datak=N.dataq;+q;+k;Q.tu=k-1;printf(tt* * 两个矩阵的加法结果为 * *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.datap.i=N.dataq.i) /两个稀疏矩阵的行数相等if(M.datap.j=N.dataq.j)/两个稀疏矩阵的列数相等if(M.datap.e-N.dataq.e!=0) /两个稀疏矩阵相减的结果不为0Q.datak.i=M.datap.i;Q.datak.j=M.datap.j;Q.datak.e=M.datap.e-N.dataq.e;+k;+q;+p;else if(M.datap.jN.dataq.j)/第一个稀疏矩阵列数大于第二个稀疏矩阵的列Q.datak.i=N.dataq.i;Q.datak.j=N.dataq.j;Q.datak.e=-N.dataq.e; /即0-N.dataq.e+q;+k;else if(M.datap.iN.dataq.i)/第一个稀疏矩阵行列数大于第二个稀疏矩阵行数Q.datak.i=N.dataq.i;Q.datak.j=N.dataq.j;Q.datak.e=-N.dataq.e; /即0-N.dataq.e+q;+k;while(p=M.tu) /只有M并且符合条件Q.datak=M.datap;+p;+k;while(q=N.tu) /只有N并且符合条件Q.datak.i=N.dataq.i;Q.datak.j=N.dataq.j;Q.datak.e=-N.dataq.e;+q;+k;Q.tu=k-1;printf(tt* * 两个矩阵的相减结果为 * *n);return OK;elseprintf(两个矩阵行列数不等，不能相减，请重新输入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.datap(p=1,2,M.tu),找到N中所有满足条件M.datap.j=N.dataq.i的元素N.dataq，求得M.datap.v和N.dataq.v的乘积，又T(i,j)=M(i,k)N(k,j),乘积矩阵T中每个元素的值是个累计和，这个乘积M.datap.vN.dataq.v只是Tij中的一部分。为便于操作，应对每个元素设一累计和的变量，其初值是零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。由于T中元素的行号和M中元素的行号一致，又M中元素排列是以M的行序为主序的，由此可对T进行逐行处理，先求得累计求和的中间结果（T的一行），然后再压缩存储到Q.data中去，其算法如下：Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q)int k1,k2,k3,m;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;if(M.nu=N.mu)/第一个矩阵的列数不等于第二个矩阵的行数才可以相乘for(k1=1;k1=M.tu;k1+)for(k2=1;k2=N.tu;k2+)if(M.datak1.j=N.datak2.i)/第一个矩阵的列数不等于第二个矩阵的行数时相乘m=M.datak1.e*N.datak2.e;if(Q.tu=0)/Q中还未有一个非零元时，赋予第一个非零元 Q.data1.e=m;Q.data1.i=M.datak1.i;Q.data1.j=N.datak2.j;Q.tu+; elsefor(k3=1;k3=Q.tu;k3+)if(Q.datak3.i=M.datak1.i&Q.datak3.j=N.datak2.j)/Q的行等于M的行，Q的列等于N的列时相加Q.datak3.e+=m;/对各个数相加break;if(k3=Q.tu+1) /相加完后成为Q中的三元组Q.datak3.e=m;Q.datak3.i=M.datak1.i; Q.datak3.j=N.datak2.j;Q.tu+;printf(tt* * 两个矩阵相乘结果为 * *n);return OK;elseprintf(第一个矩阵的列数不等于第二个矩阵的行数n);printf(不能相乘，请重新输入n);CreateSMatrix(M);printf(第一个矩阵为:n);PrintSMatrix(M);CreateSMatrix(N);printf(第二个矩阵为:n);printSMatrix(N);printf(n);MultSMatrix(M,N,Q); 2.4创建稀疏矩阵 以三元组表的形式输入创建稀疏矩阵其算法如下：Status CreateSMatrix(TSMatrix &M)printf(tt* * 请输入您的稀疏矩阵 * * nn); doprintf(t* * 请输入矩阵的行数，列数，非零元素个数 * *n);printf( );scanf(%d%d%d,&M.mu,&M.nu,&M.tu); if(M.mu20)|(M.nu20)|(M.tu/(M.mu*M.nu)0.05)|(M.tuM.mu*M.nu)|M.tuMAXSIZE)printf(n 不满足，请重新输入!n); while(M.mu20)|(M.nu20)|(M.tu/(M.mu*M.nu)0.05)|(M.tuM.mu*M.nu)|M.tuMAXSIZE); for(int k=1;k=M.tu;k+)doprintf(t* * 请输入非零元素的行数i，列数j，数值v * *n);printf( );scanf(%d%d%d,&M.datak.i,&M.datak.j,&M.datak.e); if(M.datak.iM.mu)|(M.da