稀疏矩阵
稀疏矩阵是指非零元素个数远少于零元素(通常非零元素比例小于 5%)的矩阵。
只存储非零元素的行号、列号和值,用一个三元组表表示:
#define MAXSIZE 100
typedef struct {
int row; // 行号
int col; // 列号
int value; // 元素值
} Triple;
typedef struct {
Triple data[MAXSIZE];
int rows, cols, nums; // 矩阵行数、列数、非零元素个数
} TSMatrix;
优点:极大节省存储空间。缺点:随机访问某个元素需遍历查找,效率低。
用链表存储非零元素,每个非零元素结点同时挂接在”行链表”和”列链表”上,便于矩阵的加法、乘法等运算。
typedef struct OLNode {
int row, col, value;
struct OLNode *right; // 指向同一行的下一个非零元素
struct OLNode *down; // 指向同一列的下一个非零元素
} OLNode, *OLink;
习题 1
稀疏矩阵如何压缩存储?有哪些方法?
解题思路:
本题考查稀疏矩阵的压缩存储方法。答题时先点明稀疏矩阵“只存非零元素及其位置”这一核心思想,再逐条列出三种主流表示法并说明各自的适用特点,最后总结这类压缩存储的共同优点与缺点。
详细步骤:
- 稀疏矩阵中非零元素占比很小,压缩存储的核心是只保存非零元素及其位置,把空间开销从 降到与非零元素个数成正比。
- 三元组表示法:用 (行号, 列号, 值) 的数组存储非零元素,节省空间但随机访问慢。
- 十字链表法:非零元素结点同时挂接行链表和列链表,便于矩阵运算。
- 压缩行/列存储(CSR/CSC):用三个数组分别存值、列号和行偏移,适合大规模稀疏矩阵计算。
- 综合比较:优点是节省存储空间、减少无效运算;缺点是随机访问效率低、算法实现复杂。
最终答案:
稀疏矩阵只存储非零元素及其位置,常用方法有三种:三元组表示法、十字链表法、压缩行/列存储。优点是节省存储空间,减少无效运算;缺点是随机访问效率低,算法实现复杂。
