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

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

[toc]

什么是稀疏矩阵

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

如何简化系数矩阵的表示

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

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

十字链表表示法

由于用顺序表或者一般的链表，在表示稀疏矩阵的时候，不便于进行计算的操作 这里采用十字链表来表示 十字链表包括 数据域（data）、同列的下一个结点（down）、同行的下一个结点（right）

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

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

结束

That’s all, thanks for reading!💐