存储稀疏矩阵方法
① 如何用行逻辑链接顺序表及十字链表存储稀疏矩阵
来自
严蔚敏《数据结构》
稀疏矩阵的压缩方法主要有：
1：三元组顺序表
（行下标，列下标，值）
2：行逻辑链接的顺序表。
3：十字链表。
② 稀疏矩阵定义以及存储格式(COO,CSR,CSC)
网络:在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。 简单来说,稀疏矩阵就是绝大部分都是0的矩阵 ,只包含很少的非零值.
比如,
上述稀疏矩阵非零元素有9个,26个零值.稀疏性是74%.
稀疏矩阵因为绝大部分都是0元素,如果我们仍然按照普通方式存储,无疑会 浪费很多空间 ;同时如果进行运算时,0元素对最终结果也没有帮助, 增加了许多无效计算 . 因此,我们需要设计出新的存储方式,或者说数据结构来存储稀疏矩阵.比较常见的有:
对于稀疏矩阵的存储,为了达到压缩的目的(节省存储空间),只存储非0元素值,但是也要保留非零元素的位置,方便恢复.所以,我们存储时不仅存储非零元素值,同时存储其坐标位置(row,column). 针对这两者的存储,会出现不同的设计方案.这里主要介绍COO,CSR和CSC存储格式.
我们使用三个数组row,column和data分别用来存储非零元素坐标的row_index,col_index,以及数值.比如:
NNO:The number of nonzero.矩阵非零元素个数. 三个数组的长度都是NNO.data[i]在原稀疏矩阵中的坐标为(row[i],col[i]]).
可以发现,这种存储方式中,row数组和column数组中有一定的重复元素.我们是否可以针对这个冗余特性进一步进行压缩?之后出现CSR,CSC,分别是对row数组和column数组进行了压缩.
对COO稀疏矩阵存储格式的三个数组中的row数组进行压缩.其他两个数组保持不变;三个数组分别是row_ptr,columns和data.其中columns和data数组长度均为NNO(矩阵的非零元素个数). 如何对COO的row进行压缩?
row_ptr存储的是每行的第一个非零元素距离稀疏矩阵第一个元素的偏移位置;
由row_ptr我们可以知道每行非零元素在data中的index范围.第i行的非零元素为data[row_ptr[i]:row_ptr[i+1]],对data数组的切片,不包含data[row_ptr[i+1]];同时第i行非零元素的col坐标分别为columns[row_ptr[i]:row_ptr[i+1]];对data和columns的访问相似,index是相同的.
如上图中,第0行非零元素在data中是data[0:2],就是1,7;列坐标为columns[0:2],就是0,1,第1行非零元素为data[2:4],有两个元素2和8,列坐标分别为columns[2:4],1和2.
方便进行行操作.
和CSR类似.只不过对列进行压缩,row和data保持不变.
方便进行列操作.
③ 如何建立一个稀疏矩阵并存储
//创建稀疏矩阵M
Status CreateSMatrix(TSMatrix * M)
{
int i,m,n;
ElemType e;
Status k;
printf("请输入矩阵的行数，列数，非零元素数：");
scanf("%d,%d,%d",&(* M).mu,&(* M).nu,&(* M).tu);
if ((* M).tu > MAX_SIZE)
{
return ERROR;
}
(* M).data[0].i = 0;
for (i=1;i<=(* M).tu; ++i)
{
do
{
printf("请按行序顺序输入第%d个非零元素所在的行（1-%d）,列（1-%d）,元素值：",i,(* M).mu,(* M).nu);
scanf("%d,%d,%d",&m,&n,&e);
k = 0;
if (m<1 || m>(* M).mu || n<1 || n>(* M).nu)//行或列超出范围
{
k = 1;
}
if (m<(* M).data[i-1].i || m==(* M).data[i-1].i && n<=(* M).data[i-1].j)//行或列的顺序有错
{
k = 1;
}
}while (k);
(* M).data[i].i = m;
(* M).data[i].j = n;
(* M).data[i].e = e;
}
return OK;
}
④ 稀疏矩阵一般的压缩存储方法有两种
1.三元数组存储(行,列,值)
2.行指针链表(第一列为数组,用指针链接到本行下一个有意义的位置)
3.十字链表(实在是太复杂了...)
⑤ 稀疏矩阵的压缩存储思想
为了节省存储空间并且加快处理速度，需要对这类矩阵进行压缩存储，压缩存储的原则是：不重复存储相同元素；不存储零值元素。稀疏矩阵，有三元组表示法、带辅助行向量的二元组表示法（也即行逻辑链表的顺序表），十字链表表示法等。算法基本思想：num[col]:第col列的非零元素个数；cpot[col]:第col列第一个非零元在b.data中的恰当位置；在转置过程中，指示该列下一个非零元在b.data中的位置。
⑥ 稀疏矩阵是怎样存储的
/*
稀疏矩阵的三元组顺序表存储表示
*/
# define MAX_SIZE 100//非零元个数的最大值
struct Triple
{
int i,j;//行下标，列下标
ElemType e;//非零元素值
};
struct TSMatrix
{
Triple data[MAX_SIZE+1];//非零元三元组表，data[0]未用
int mu,nu,tu;//矩阵的行数、列数和非零元个数
};
⑦ 稀疏矩阵的三种存储方式
常见的有三元组表示法、带辅助行向量的二元组表示法（也即行逻辑链表的顺序表），十字链表表示法
⑧ 三元组表示稀疏矩阵是什么
三元组表示稀疏矩阵如下：
从方法上讲，所谓的三元组法表示稀疏矩阵是：将非零元素所在的行、列以及它的值构成一个三元组（i、j、v)，然后再按某种规律存储这些三元组，这种方法可以节约存储空间。
对于稀疏矩阵，采用压缩存储方法时，只存储非0元素。必须存储非0元素的行下标值、列下标值、元素值。因此，一个三元组唯一确定稀疏矩阵的一个非零元素。
稀疏矩阵和三元组的特点：
稀疏矩阵的概念是：一个m行n列的矩阵，若它的非零元个数特别少，即可称它为稀疏矩阵。只存储稀疏矩阵的非零元。除了存储非零元的值a以外，还必须记下它的行下标i和列下标j。反之，一个三元组唯一确定矩阵的一个非零元。因此，一个稀疏矩阵可由一个三元组数组和该矩阵的行列数来确定。
⑨ 稀疏矩阵的压缩存储方法有
稀疏矩阵的压缩存储，数据结构提供有 3 种具体实现方式：
三元组顺序表；
行逻辑链接的顺序表；
十字链表；
⑩ 稀疏矩阵的压缩存储只需要存储什么
非零元素。
对于一个用二维数组存储的稀疏矩阵Amn，如果假设存储每个数组元素需要L个字节，那么存储整个矩阵需要m*n*L个字节。但是，这些存储空间的大部分存放的是0元素，从而造成大量的空间浪费。为了节省存储空间，可以只存储其中的非0元素。
(10)存储稀疏矩阵方法扩展阅读
稀疏矩阵算法的最大特点是通过只存储和处理非零元素从而大幅度降低存储空间需求以及计算复杂度，代价则是必须使用专门的稀疏矩阵压缩存储数据结构。稀疏矩阵算法是典型的不规则算法，计算访存比很低，并且计算过程中的访存轨迹与稀疏矩阵的稀疏结构相关。