三元组稀疏矩阵

稀疏矩阵是指矩阵中非零元素远少于零元素，且分布没有规律的矩阵。为了节省存储空间，通常采用三元组表示法（Triple Representation）来存储稀疏矩阵，仅记录非零元素的信息。

三元组定义

每个非零元素用一个三元组表示：

(row, col, value)

• row：该非零元素所在的行号
• col：该非零元素所在的列号
• value：该非零元素的值

数据结构

稀疏矩阵的三元组顺序表通常定义如下：

#define MAXSIZE 1000  // 非零元素最大个数
 
typedef struct {
    int i, j;     // 非零元素的行下标和列下标
    ElemType e;   // 非零元素的值
} Triple;
 
typedef struct {
    Triple data[MAXSIZE + 1];  // 非零元三元组表，data[0] 未使用
    int mu, nu, tu;            // 矩阵的行数、列数、非零元个数
} TSMatrix;

其中 mu 表示原矩阵的行数，nu 表示原矩阵的列数，tu 表示非零元素的个数。

空间效率分析

对于一个 m x n 的矩阵，普通二维数组需要存储 m x n 个元素。而三元组表示法只存储 tu 个非零元素，每个元素需要存储行、列和值三个信息。当 tu 远小于 m x n 时，三元组表示法能显著节省存储空间。通常认为稀疏因子（非零元素比例）小于 0.05 时，采用三元组存储具有明显优势。

特点

• 三元组表中的元素通常按行优先的顺序排列（先按行号递增，同行按列号递增）
• 便于进行矩阵转置、加法、乘法等运算
• 不支持随机访问，访问某个位置的元素需要遍历查找

链接到

• 上一个知识点：无（本章第一个知识点）
• 下一个知识点：3.2 稀疏矩阵转置