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

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

[toc]

什么是稀疏矩阵

如果一个矩阵中，0的数量远大于非0的数量（0超过一半以上），这个矩阵就是稀疏矩阵
由于全部都是重复的0，这种无用的重复值的存储会占据很多空间，造成浪费

如何简化系数矩阵的表示

只需要存储非零的数据以及它在矩阵中的位置就可以
比如一个二维矩阵，就可以用一个三元组进行表示，（行，列，数据）
1
2
3
4
5
struct triple
{
    int row,col;
    int data;
}

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

十字链表表示法

由于用顺序表或者一般的链表，在表示稀疏矩阵的时候，不便于进行计算的操作
这里采用十字链表来表示
十字链表包括数据域（data）、同列的下一个结点（down）、同行的下一个结点（right）
用来表示稀疏矩阵的时候，data就是三元组
如果同列/行中没有了下一个（非零）结点，那down/right就指向NULL
画个图表示一下