算法与数据结构课程设计--稀疏矩阵.doc

稀疏矩阵 一、问题描述 假若在阶中，有个元素不为零，令称为矩阵的稀疏因子。通常认为0.05时称为稀疏矩阵。稀疏矩阵的研究大大的减少了数据在计算机中存储所需的空间，然而，它们的运算却与普通矩阵有所差异。通过本次实验实现稀疏矩阵的转置、加法和乘法等多种运算。 二、基本要求 1、稀疏矩阵采用三元组表示，建立稀疏矩阵，并能按矩阵和三元组方式输出; 2、编写算法，完成稀疏矩阵的转置操作； 3、编写算法，完成对两个具有相同行列数的稀疏矩阵进行求和操作； 4、编写算法，对前一矩阵行数与后一矩阵列数相等的两个矩阵,完成两个稀疏矩阵的相乘操作。 三、测试数据 1、转置操作的测试数据： 2、相加操作的测试数据： 3、相乘操作的测试数据： 四、算法思想 1、三元组结构类型为Triple，用i表示元素的行，j表示元素的列，e表示元素值。稀疏矩阵的结构类型为TSMatrix，用数组data[]表示三元组，mu表示行数，nu表示列数，tu表示非零元个数。 2、稀疏矩阵转置的算法思想 将需要转置的矩阵a所有元素存储在三元组表a.data中，按照矩阵a的列序来转置。为了找到a的每一列中所有非零元素，需要对其三元组表a.data扫描一遍，由于a.data是以a的行需序为主序来存放每个非零元的，由此得到的就是a的转置矩阵的三元组表，将其储存在b.data中。 3、稀疏矩阵相加的算法思想 比较满足条件(行数及列数都相同的两个矩阵)的两个稀疏矩阵中不为0的元素的行数及列数（即i与j），将i与j都相等的前后两个元素值e相加，保持i,j不变储存在新的三元组中，不等的则分别储存在此新三元组中。最后得到的这个新三元组表就是两个矩阵的和矩阵的三元组表。 4、稀疏矩阵相乘的算法思想 两个相乘的矩阵为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]中的一部分。为便于操作，应对每个元素设一累计和的变量，其初值是零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。由于T中元素的行号和M中元素的行号一致，又M中元素排列是以M的行序为主序的，由此可对T进行逐行处理，先求得累计求和的中间结果（T的一行），然后再压缩存储到Q.data中去。 五、模块划分 1、Status CreateM(TSMatrix *M, int a[],int row, int col)，创立三元组； 2、void PrintM(TSMatrix M)，按数组方式输出； 3、void PrintM3(TSMatrix M)，按三元组方式输出； 4、Status TransposeSMatrix(TSMatrix M, TSMatrix *T)，稀疏矩阵的转置； 5、Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q)，稀疏矩阵加法； 6、Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q)，稀疏矩阵相乘； 7、main(),主函数。 六、数据结构//(ADT) 1、三元组结构类型 typedef struct { int i,j; ElemType e; } Triple; 2、稀疏矩阵 typedef struct { Triple data[MAXSIZE+1]; int mu,nu,tu; } TSMatrix; 七、源程序 #include stdio.h #define OK 1 #define TRUE 1 #define FALSE 0 typedef int Status; typedef int ElemType; /* 三元组顺序表的类型定义 */ #define MAXSIZE 1000 #define MAXRC 1000 typedef struct { int i,j; ElemType e; } Triple; typedef struct { Triple data[MAXSIZE+1]; int mu,nu,tu; } TSMatrix; /* 建立三元组表 */ Status CreateM(TSMatrix *M, int a[],int row, int