2651 - 数据结构/稀疏矩阵/三元组实现
实验原理：稀疏矩阵是指非零元素较少的矩阵，如果采用二维数组存储将会导致很大的存储空间浪费。我们可以使用(行号,列号,非零元素值)的三元组的顺序表来存储矩阵中的非零值，这样就可以不存储大量的零元素。
需要注意的是：为了操作高效，我们需要将非零元素按照行顺序排列，同一行里面按列排列。
实验步骤：
1、实现三元组定义
2、实现稀疏矩阵定义
3、实现稀疏矩阵的元素添加方法
4、实现稀疏矩阵的输出方法
5、实现稀疏矩阵的加法
6、实现稀疏矩阵的减法
7、实现稀疏矩阵的转置
题目输入
每个输入由两个矩阵A和B组成，每个矩阵本身就按三元组的方式输入：每个矩阵的第一行由三个整数组成，n、m和c，表示矩阵的行列数和非零元素数量。
题目输出
输出固定文本：A'
然后输出A的转置
输出固定文本：A+B
然后输出A+B的结果
输入/输出样例
输入格式
3 3 2 0 0 5 1 2 7 3 3 2 0 0 5 2 1 9
输出格式
A' 3 3 2 (0,0)=5 (2,1)=7 A+B 3 3 3 (0,0)=10 (1,2)=7 (2,1)=9
提示
一、三元组实现
struct Triple{
int row,col;
float data;
Triple(){ row=0,col=0,data=0; }
Triple(int r,int c,float d)
{ row=r;col=c;data=d; }
void Show()<br />
{ printf("(%d,%d)=%.0f\n",row,col,data); }
};
二、稀疏矩阵接口和部分实现
#define MAX_SIZE 100 <br />
struct SparseMatrix
{
int rows,cols;
int count;
Triple elems[MAX_SIZE];
SparseMatrix(int r,int c)<br />
{ rows=r; cols=c; count=0; }
void AddElement(Triple &t)<br />
{ elems[count++]=t; }
<br />
void AddElement(int r,int c,float data)
{ elems[count++]=Triple(r,c,data); }
SparseMatrix& Transpose()<br />
{
SparseMatrix* result=new SparseMatrix(cols,rows);
//TODO:实现转置
return *result;<br />
}
SparseMatrix& Add(SparseMatrix &other)<br />
{
SparseMatrix result=new SparseMatrix(rows,cols);
//TODO:完成元素相加result=this+other
return result;
}
void ShowTriple()
{
printf("%d %d %d\n",rows,cols,count);
for (int i=0;i<count;i++)
elems[i].Show();
}
void ShowFull()<br />
{
int index=0;
Triple triple=elems[index++];
for (int r=0;r<rows;r++)
{
for (int c=0;c<cols;c++)
{
if (r==triple.row && c==triple.col)
{
printf("%.2f\t",triple.data);
triple=elems[index++];
}
else
printf("%d\t",triple.data);
}
printf("\n");
}
printf("\n");
}
};
三、主控部分：
int main()<br />
{
int n,m,count;
int r,c,d;
while(scanf("%d%d%d",&n,&m,&count)==3)
{
SparseMatrix A(n,m);
for (int i=0;i<count;i++)
{
scanf("%d%d%d",&r,&c,&d);
A.AddElement(r,c,d);
}
scanf("%d%d%d",&n,&m,&count);
SparseMatrix B(n,m);
for (int i=0;i<count;i++)
{
scanf("%d%d%d",&r,&c,&d);
B.AddElement(r,c,d);
}
printf("A'\n");
A.Transpose().ShowTriple();
printf("A+B\n");
A.Add(B).ShowTriple();
}
return 0;<br />
}