实现稀疏矩阵(采用三元组表示)的基本运算实验报告
实现稀疏矩阵（采用三元组表示）的基本运算实验报告
一 实验题目: 实现稀疏矩阵（采用三元组表示）的基本运算
二 实验要求:
（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,j∈ElemSet,m和n分别称为矩阵的行数和列数 } 数据关系 : R={ Row , Col }
Row ={ | 1≤ i≤m , 1≤ j≤ n-1} Col ={| 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;i
{
for (j=0;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
return;
printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums);
printf("\t------------------\n");
for (i=0;i
printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d); }
3.4解题思路：
1.转置矩阵：只要判定原矩阵有值，那么只要遍历一遍原矩阵，把原来矩阵中非0元素行列变换一下赋值到新的矩阵中即可。
2.矩阵加法：用各种 if 判断，区分出矩阵进行加法时的可能情况，分情况处理即可。
3.矩阵乘法：通过 getvalue（c ， i， j） 函数查找 矩阵c 中i 行j列，所储存的元素的值。然后便是模拟矩阵乘法的过程进行求解。
3.5解题过程：
实验源代码如下：
3.5.1顺序表的各种运算
#include
#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; //三元组顺序表定义
void CreatMat(TSMatrix &t,ElemType A[N][N]){
int i,j;
t.rows=N;t.cols=N;t.nums=0;
for (i=0;i
{
for (j=0;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
return;
printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums);
printf("\t------------------\n");
for (i=0;i
printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].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
for (p=0;p
{
tb.data[q].r=t.data[p].c;
tb.data[q].c=t.data[p].r;
tb.data[q].d=t.data[p].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
if (a.data[i].r==b.data[j].r) //行号相等时
{
if(a.data[i].c
{
c.data[k].r=a.data[i].r;//将a元素添加到c中
c.data[k].c=a.data[i].c;
c.data[k].d=a.data[i].d;
k++;i++;
}
else if (a.data[i].c>b.data[j].c)//a元素的列号大于b元素的列号
{
c.data[k].r=b.data[j].r; //将b元素添加到c中 c.data[k].c=b.data[j].c;
c.data[k].d=b.data[j].d;
k++;j++;
}
else //a元素的列号等于b元素的列号
{
v=a.data[i].d+b.data[j].d;
if (v!=0) //只将不为0的结果添加到c中 {
c.data[k].r=a.data[i].r;
c.data[k].c=a.data[i].c;
c.data[k].d=v;
k++;
}
i++;j++;
}
}
else if (a.data[i].r
{
c.data[k].r=a.data[i].r; //将a元素添加到c中 c.data[k].c=a.data[i].c;
c.data[k].d=a.data[i].d;
k++;i++;
}
else //a元素的行号大于b元素的行号
{
c.data[k].r=b.data[j].r; //将b元素添加到c中
c.data[k].c=b.data[j].c;
c.data[k].d=b.data[j].d;
k++;j++;
}
c.nums=k;
}
return true;
}
int getvalue(TSMatrix c,int i,int j)
{
int k=0;
while (k
if (k
return(c.data[k].d);
else
return(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
for (j=0;j
{
s=0;
for (k=0;k
s=s+getvalue(a,i,k)*getvalue(b,k,j);
if (s!=0) //产生一个三元组元素
{
c.data[p].r=i;
c.data[p].c=j;
c.data[p].d=s;
p++;
}
}
c.rows=a.rows;
c.cols=b.cols;
c.nums=p;
return true;
}
int main()
{
ElemType a1[N][N]={ {1,0,3,0}, {0,1,0,0}, {0,0,1,0}, {0,0,1,1}}; ElemType b1[N][N]={ {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转置为c\n");
TranMat(a,c);
printf("c的三元组:\n");DispMat(c); printf("c=a+b\n");
MatAdd(a,b,c);
printf("c的三元组:\n");DispMat(c); printf("c=a×b\n");
MatMul(a,b,c);
printf("c的三元组:\n");DispMat(c); return 0;
}
四 实验结果