稀疏矩阵
矩阵是由 m 行和 n 列组成的二维数据对象, 因此总共有 m x n 个值.
如果矩阵的大多数元素都有 0 值, 则称为稀疏矩阵 sparse matrix.
我们可以只存储稀疏矩阵中的非 0 元素, 这样做的好处有:
- 存储空间: 非零元素的数量少于零元素的数量, 因此可以使用较少的内存来存储这些元素
- 计算时间: 通过逻辑设计仅遍历非零元素的数据结构可以节省计算时间
用二维数组表示稀疏矩阵会导致大量内存浪费, 因为矩阵中的零在大多数情况下都是无用的. 因此我们只存储非零元素, 而不是将零与非零元素一起存储. 这意味着用三元组 (行, 列, 值) 存储非零元素.
稀疏矩阵表示可以通过多种方式完成, 以下是两种常见的表示形式:
- 数组表示
- 链表表示
接下来的章节将分别对这两类表示形式展示详细的说明.