稀疏矩阵

稀疏矩阵是指非零元素个数远少于零元素(通常非零元素比例小于 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

稀疏矩阵如何压缩存储?有哪些方法?

稀疏矩阵压缩存储三元组表示法十字链表

解题思路:

本题考查稀疏矩阵的压缩存储方法。答题时先点明稀疏矩阵“只存非零元素及其位置”这一核心思想,再逐条列出三种主流表示法并说明各自的适用特点,最后总结这类压缩存储的共同优点与缺点。

详细步骤:

  1. 稀疏矩阵中非零元素占比很小,压缩存储的核心是只保存非零元素及其位置,把空间开销从 O(n2)O(n^2) 降到与非零元素个数成正比。
  2. 三元组表示法:用 (行号, 列号, 值) 的数组存储非零元素,节省空间但随机访问慢。
  3. 十字链表法:非零元素结点同时挂接行链表和列链表,便于矩阵运算。
  4. 压缩行/列存储(CSR/CSC):用三个数组分别存值、列号和行偏移,适合大规模稀疏矩阵计算。
  5. 综合比较:优点是节省存储空间、减少无效运算;缺点是随机访问效率低、算法实现复杂。

最终答案:

稀疏矩阵只存储非零元素及其位置,常用方法有三种:三元组表示法、十字链表法、压缩行/列存储。优点是节省存储空间,减少无效运算;缺点是随机访问效率低,算法实现复杂。

发现内容有问题?

告诉我们哪里需要改进。