实现稀疏矩阵采用三元组表示的基本运算实验报告.doc

实现稀疏矩阵（采用三元组表示）的基本运算实验报告 一 实验题目: 实现稀疏矩阵（采用三元组表示）的基本运算 二 实验要求: 生成如下两个稀疏矩阵的三元组 a 和 b； （上机实验指导 P92 ） 输出 a 转置矩阵的三元组 ； 输出a + b 的三元组； 输出 a * b 的三元组； 三 实验内容: 3.1 稀疏矩阵的抽象数据类型: ADT?SparseMatrix?{? 数据对象:D={aij|?i?=??1,2,3,….,m;??j?=1,2,3,……,n;? ai,j∈ElemSet,m和n分别称为矩阵的行数和列数?}? 数据关系?:??R={??Row?,?Col?}? Row?={ai,j?,ai,j+1?|??1≤?i≤m?,?1≤?j≤?n-1}? Col?={a?i,j?,?a?i+1,j?|??1≤i≤m-1,1≤j≤n} 基本操作: CreateSMatrix(M) ?操作结果：创建稀疏矩阵 M PrintSMatrix(M)? 初始条件：稀疏矩阵M已经存在? 操作结果：打印矩阵M? DestroySMatrix(M)? 初始条件：稀疏矩阵M已经存在? 操作结果：销毁矩阵M? CopySMatrix(M,?T) ? 初始条件：稀疏矩阵M已经存在? 操作结果：复制矩阵M到T? ?AddSMatrix(M,?N,?Q)? 初始条件：稀疏矩阵M、N已经存在? 操作结果：求矩阵的和Q=M+N? ?SubSMatrix(M,?N,?Q)? 初始条件：稀疏矩阵M、N已经存在? 操作结果：求矩阵的差Q=M-N? TransposeSMatrix(M,??T)? 初始条件：稀疏矩阵M已经存在? 操作结果：求矩阵M的转置T? MultSMatrix(M,?N,?Q)? 初始条件：稀疏矩阵M已经存在? 操作结果：求矩阵的积Q=M*N }ADT SparseMatrix 3.2存储结构的定义 #define N 4 typedef int ElemType; #define MaxSize 100 //矩阵中非零元素最多个数 typedef struct { int r; //行号 int c; //列号 ElemType d; //元素值 } TupNode; //三元组定义 typedef struct { int rows; //行数值 int cols; //列数值 int nums; //非零元素个数 TupNode data[MaxSize]; } TSMatrix; //三元组顺序表定义 3.3基本操作实现: void CreatMat(TSMatrix t,ElemType A[N][N]) { int i,j; t.rows=N;t.cols=N;t.nums=0; for (i=0;iN;i++) { for (j=0;jN;j++) if (A[i][j]!=0) { t.data[t.nums].r=i;t.data[t.nums].c=j; t.data[t.nums].d=A[i][j];t.nums++; } } } void DispMat(TSMatrix t) { int i; if (t.nums=0) return; printf(\t%d\t%d\t%d\n,t.rows,t.cols,t.nums); printf(\t------------------\n); for (i=0;it.nums;i++) printf(\t%d\t%d\t%d\n,t.data[i].r,t.data[i].c,t.data[i].d); } 3.4解题思路： 转置矩阵：只要判定原矩阵有值，那么只要遍历一遍原矩阵，把原来矩阵中非0元素行列变换一下赋值到新的矩阵中即可。 矩阵加法：用各种 if 判断，区分出矩阵进行加法时的可能情况，分情况处理即可。 矩阵乘法：通过 getvalue（c ， i， j） 函数查找 矩阵c 中i 行j列，所储存的元素的值。然后便是模拟矩阵乘法的过程进行求解。 3.5解题过程： 实验源代码如下： 3.5.1顺序表的各种运算 #include stdio.h #define N 4 typedef int ElemType; #define MaxSiz