说明

实验原理：稀疏矩阵是指非零元素较少的矩阵，如果采用二维数组存储将会导致很大的存储空间浪费。我们可以使用(行号,列号,非零元素值)的三元组的顺序表来存储矩阵中的非零值，这样就可以不存储大量的零元素。

需要注意的是：为了操作高效，我们需要将非零元素按照行顺序排列，同一行里面按列排列。

 

实验步骤：

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()
 {  printf("(%d,%d)=%.0f\n",row,col,data); }

};

 

二、稀疏矩阵接口和部分实现

#define MAX_SIZE 100 
struct SparseMatrix
{
 int rows,cols;
 int count;
 Triple elems[MAX_SIZE];

 SparseMatrix(int r,int c)
 {  rows=r;  cols=c;  count=0; }

 void AddElement(Triple &t)
 {  elems[count++]=t; }

 void AddElement(int r,int c,float data)
 {  elems[count++]=Triple(r,c,data); }

 

 SparseMatrix& Transpose()
 {
  SparseMatrix* result=new SparseMatrix(cols,rows);
  //TODO:实现转置

  return *result;
 }

 SparseMatrix& Add(SparseMatrix &other)
 {
  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()
 {
  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()
{
 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;
}

 

来源

数据结构-基础数据结构