数据结构_线性表应用 _稀疏矩阵

[toc]

什么是稀疏矩阵

如果一个矩阵中，0的数量远大于非0的数量（0超过一半以上），这个矩阵就是稀疏矩阵

由于全部都是重复的0，这种无用的重复值的存储会占据很多空间，造成浪费

如何简化系数矩阵的表示

只需要存储非零的数据以及它在矩阵中的位置就可以

比如一个二维矩阵，就可以用一个三元组进行表示，（行，列，数据）

1
2
3
4
5
struct triple
{
    int row,col;
    int data;
}

然后以三元组为基本元素，用顺序表或者链表就可以表示出稀疏矩阵了

十字链表表示法

由于用顺序表或者一般的链表，在表示稀疏矩阵的时候，不便于进行计算的操作

这里采用十字链表来表示

十字链表包括 数据域（data）、同列的下一个结点（down）、同行的下一个结点（right）

img

用来表示稀疏矩阵的时候，data就是三元组

img

如果同列/行中没有了下一个（非零）结点，那down/right就指向NULL

画个图表示一下

img

结束

That’s all, thanks for reading!💐