实现稀疏矩阵(采用三元组表示)的基本运算实验报告(共9页).doc
精选优质文档-倾情为你奉上实现稀疏矩阵（采用三元组表示）的基本运算实验报告一 实验题目: 实现稀疏矩阵（采用三元组表示）的基本运算二 实验要求: （1） 生成如下两个稀疏矩阵的三元组 a 和 b； （上机实验指导 P92 ）（2） 输出 a 转置矩阵的三元组 ；（3） 输出a + b 的三元组；（4） 输出 a * b 的三元组；三 实验内容:3.1 稀疏矩阵的抽象数据类型:ADT SparseMatrix 数据对象:D=aij| i = 1,2,3,.,m; j =1,2,3,n; ai,jElemSet,m和n分别称为矩阵的行数和列数 数据关系 : R= Row , Col Row =<ai,j ,ai,j+1> | 1 im , 1 j n-1 Col =<a i,j , a i+1,j >| 1im-1,1jn基本操作:CreateSMatrix(&M) 操作结果：创建稀疏矩阵 MPrintSMatrix(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*NADT SparseMatrix3.2存储结构的定义#define N 4typedef int ElemType;#define MaxSize 100/矩阵中非零元素最多个数typedef structint r; /行号 int c;/列号 ElemType d; /元素值 TupNode; /三元组定义typedef structint rows; /行数值 int cols; /列数值 int nums; /非零元素个数 TupNode dataMaxSize; TSMatrix; /三元组顺序表定义3.3基本操作实现:void CreatMat(TSMatrix &t,ElemType ANN)int i,j;t.rows=N;t.cols=N;t.nums=0;for (i=0;i<N;i+)for (j=0;j<N;j+)if (Aij!=0)t.datat.nums.r=i;t.datat.nums.c=j;t.datat.nums.d=Aij;t.nums+;void DispMat(TSMatrix t)int i;if (t.nums<=0)return;printf("t%dt%dt%dn",t.rows,t.cols,t.nums);printf("t-n");for (i=0;i<t.nums;i+) printf("t%dt%dt%dn",t.datai.r,t.datai.c,t.datai.d);3.4解题思路： 1. 转置矩阵：只要判定原矩阵有值，那么只要遍历一遍原矩阵，把原来矩阵中非0元素行列变换一下赋值到新的矩阵中即可。2. 矩阵加法：用各种 if 判断，区分出矩阵进行加法时的可能情况，分情况处理即可。3. 矩阵乘法：通过 getvalue（c ， i， j） 函数查找 矩阵c 中i 行j列，所储存的元素的值。然后便是模拟矩阵乘法的过程进行求解。3.5解题过程：实验源代码如下：3.5.1顺序表的各种运算#include <stdio.h>#define N 4typedef int ElemType;#define MaxSize 100/矩阵中非零元素最多个数typedef structint r; /行号 int c;/列号 ElemType d; /元素值 TupNode; /三元组定义typedef structint rows; /行数值 int cols; /列数值 int nums; /非零元素个数 TupNode dataMaxSize; TSMatrix; /三元组顺序表定义void CreatMat(TSMatrix &t,ElemType ANN)int i,j;t.rows=N;t.cols=N;t.nums=0;for (i=0;i<N;i+)for (j=0;j<N;j+)if (Aij!=0)t.datat.nums.r=i;t.datat.nums.c=j;t.datat.nums.d=Aij;t.nums+;void DispMat(TSMatrix t)int i;if (t.nums<=0)return;printf("t%dt%dt%dn",t.rows,t.cols,t.nums);printf("t-n");for (i=0;i<t.nums;i+)printf("t%dt%dt%dn",t.datai.r,t.datai.c,t.datai.d);void TranMat(TSMatrix t,TSMatrix &tb)int p,q=0,v; /q为tb.data的下标tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums;if (t.nums!=0)for (v=0;v<t.cols;v+)/tb.dataq中的记录以c域的次序排列for (p=0;p<t.nums;p+) /p为t.data的下标if (t.datap.c=v)tb.dataq.r=t.datap.c;tb.dataq.c=t.datap.r;tb.dataq.d=t.datap.d;q+;bool MatAdd(TSMatrix a,TSMatrix b,TSMatrix &c)int i=0,j=0,k=0;ElemType v;if (a.rows!=b.rows | a.cols!=b.cols)return false; /行数或列数不等时不能进行相加运算c.rows=a.rows;c.cols=a.cols; /c的行列数与a的相同while (i<a.nums && j<b.nums) /处理a和b中的每个元素if (a.datai.r=b.dataj.r)/行号相等时if(a.datai.c<b.dataj.c) /a元素的列号小于b元素的列号c.datak.r=a.datai.r;/将a元素添加到c中c.datak.c=a.datai.c;c.datak.d=a.datai.d;k+;i+; else if (a.datai.c>b.dataj.c)/a元素的列号大于b元素的列号c.datak.r=b.dataj.r;/将b元素添加到c中 c.datak.c=b.dataj.c; c.datak.d=b.dataj.d; k+;j+; else/a元素的列号等于b元素的列号v=a.datai.d+b.dataj.d;if (v!=0)/只将不为0的结果添加到c中c.datak.r=a.datai.r;c.datak.c=a.datai.c;c.datak.d=v;k+;i+;j+; else if (a.datai.r<b.dataj.r) /a元素的行号小于b元素的行号c.datak.r=a.datai.r; /将a元素添加到c中c.datak.c=a.datai.c;c.datak.d=a.datai.d;k+;i+; else /a元素的行号大于b元素的行号c.datak.r=b.dataj.r; /将b元素添加到c中c.datak.c=b.dataj.c;c.datak.d=b.dataj.d;k+;j+; c.nums=k;return true;int getvalue(TSMatrix c,int i,int j) int k=0; while (k<c.nums && (c.datak.r!=i | c.datak.c!=j)k+; if (k<c.nums)return(c.datak.d); elsereturn(0);bool MatMul(TSMatrix a,TSMatrix b,TSMatrix &c) int i,j,k,p=0;ElemType s;if (a.cols!=b.rows)/a的列数不等于b的行数时不能进行相乘运算return false;for (i=0;i<a.rows;i+)for (j=0;j<b.cols;j+) s=0; for (k=0;k<a.cols;k+)s=s+getvalue(a,i,k)*getvalue(b,k,j); if (s!=0) /产生一个三元组元素 c.datap.r=i; c.datap.c=j; c.datap.d=s; p+; c.rows=a.rows;c.cols=b.cols;c.nums=p;return true;int main()ElemType a1NN= 1,0,3,0, 0,1,0,0, 0,0,1,0, 0,0,1,1;ElemType b1NN= 3,0,0,0, 0,4,0,0, 0,0,1,0, 0,0,0,2;TSMatrix a,b,c;CreatMat(a,a1); CreatMat(b,b1);printf("a的三元组:n");DispMat(a);printf("b的三元组:n");DispMat(b);printf("a转置为cn");TranMat(a,c);printf("c的三元组:n");DispMat(c);printf("c=a+bn");MatAdd(a,b,c);printf("c的三元组:n");DispMat(c);printf("c=a×bn");MatMul(a,b,c);printf("c的三元组:n");DispMat(c);return 0;四 实验结果专心-专注-专业
