C++ 用三元组表示法存储稀疏矩阵

时间:2023-03-08 21:31:08
C++  用三元组表示法存储稀疏矩阵

若有一个矩阵(m*n),其中非0元素个数远少于数值为0的元素个数,若开辟一个m*n大空间,来存储这样一个很多元素值为0的矩阵,浪费空间,于是我们只存储这些非0的元素的下标及数值

用一个结构体——三元组,来表示这些非零元素的行r,列c,数值v的信息

typedef struct //三元组
{
int r; //非零元所在的行
int c; //非零元所在的列
int v; //非零元的值
} node;

一个完整矩阵的包括这些信息需要存储:矩阵的总行m,总列n,非零元的个数N,以及这些非零元的信息,所以再将这些信息用一个结构体来表示出来,其中非零元的相关信息用一个一维数组node a[100]来存储

为什么用一维数组就可以来存储矩阵(二维数组)的信息呢

这就是结构体node的方便之处 —— node将行、列、数值打包成一个整体

typedef struct
{
int m; //稀疏矩阵的行数
int n; //稀疏矩阵的列数
int N; //稀疏矩阵中非零元的个数
node a[]; //存储非零元的数组a
}Matrix;

定义 Matrix M;

查找稀疏矩阵中是否存在值为p的元素

存在,则输出所在的行M.a[i].r,列M.a[i].c,

不存在,输出ERROR

首先用for循环实现,终止条件为i==M.N

如果匹配不成功,输出ERROR。如何表示匹配不成功呢,这里用一个flag来标记,0表示不成功,flag初值为0,

如果匹配成功,后续就不用再继续匹配,flag==1;输出该元素所在的行M.a[i].r,列M.a[i].c     同时用break结束循环

在for循环外判断flag的值  if(flag==0),则表示从i=0到i=M.N-1,都未匹配成功 那么cout<<"ERROR";

void search(Matrix M,int p)  //查找p是否在稀疏矩阵中
{
int i=;
int flag=;
for(i=;i<M.N;i++) //匹配数组a中元素的value和p
{
if(p==M.a[i].v) //相等
{
flag=;
cout<<M.a[i].r<<" "<<M.a[i].c<<endl; //输出所在的行列
break; //跳出for循环
}
}
if(flag==) //若未匹配成功,输出ERROR
cout<<"ERROR"<<endl;
}