数组的稀疏表示：稀疏数组的压缩存储与三元组表示法

咱们平时写代码，数组用得很顺手。但你想过没有——如果数组里大部分元素都是0，你还一个一个存着，是不是有点浪费？

我早年做图像处理时，遇到过一张2000x2000的矩阵，里面只有不到1%的非零元素。要是按普通二维数组存，光内存就得吃掉16MB（按int算）。但实际有效数据才几十KB。嗯，这时候就该稀疏数组出场了。

什么是稀疏数组？

说白了，就是数组中非零元素的数量远少于零元素。一般我们定义：非零元素占比小于5%，就可以认为是稀疏数组。

举个例子：

int matrix[5][5] = {
    {0, 0, 3, 0, 0},
    {0, 0, 0, 0, 0},
    {0, 7, 0, 0, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 9}
};

这个5x5的矩阵，25个元素里只有3个非零值。你想想看，存25个int和存3个int加一点索引信息，哪个划算？

压缩存储的核心思想

压缩存储就一个原则：只存非零元素，不存零。但光存数值不够，你还得知道它原来在哪个位置。所以每个非零元素需要三个信息：

• 行号（row）—— 在哪一行
• 列号（col）—— 在哪一列
• 值（value）—— 具体数值

这三个信息组成一个“三元组”。把所有非零元素的三元组按行优先顺序排成一个线性表，就是三元组表示法。

三元组的数据结构

在C语言里，我们通常这样定义：

// 三元组结构
typedef struct {
    int row;    // 行号
    int col;    // 列号
    int value;  // 非零元素值
} Triple;

// 稀疏矩阵结构
typedef struct {
    Triple data[MAX_TERMS];  // 三元组表
    int rows;               // 总行数
    int cols;               // 总列数
    int nonZeroCount;       // 非零元素个数
} SparseMatrix;

这里有个细节：data数组是按行优先顺序存储的。也就是说，先存第0行的所有非零元素，再存第1行的，以此类推。这样做的好处是——后续做矩阵运算时，遍历顺序和原始矩阵一致，不容易出错。

从普通数组到三元组

转换过程其实很简单。我习惯这么写：

void compressMatrix(int original[][COLS], SparseMatrix *sparse) {
    int i, j, k = 0;

    sparse->rows = ROWS;
    sparse->cols = COLS;
    sparse->nonZeroCount = 0;

    for (i = 0; i < ROWS; i++) {
        for (j = 0; j < COLS; j++) {
            if (original[i][j] != 0) {
                sparse->data[k].row = i;
                sparse->data[k].col = j;
                sparse->data[k].value = original[i][j];
                k++;
                sparse->nonZeroCount++;
            }
        }
    }
}

你看，就是遍历原数组，遇到非零就记下来。时间复杂度O(m×n)，没法再优化了——因为你总得把每个元素看一遍才知道它是不是零。

从三元组还原回普通数组

还原更简单：先创建一个全零数组，然后遍历三元组表，把值填回去。

void restoreMatrix(SparseMatrix *sparse, int result[][sparse->cols]) {
    int i, j;

    // 先全部置零
    for (i = 0; i < sparse->rows; i++) {
        for (j = 0; j < sparse->cols; j++) {
            result[i][j] = 0;
        }
    }

    // 填入非零元素
    for (i = 0; i < sparse->nonZeroCount; i++) {
        int r = sparse->data[i].row;
        int c = sparse->data[i].col;
        result[r][c] = sparse->data[i].value;
    }
}

三元组表示法的优缺点

优点	缺点
存储空间大幅减少（稀疏度高时）	随机访问变慢（需要遍历查找）
结构简单，容易实现	矩阵运算（如乘法）实现较复杂
适合行优先遍历的场景	插入/删除非零元素需要移动数据

为什么会这样？因为三元组表本质上是线性表，不是随机存取结构。你想知道第i行第j列的值，得从头遍历一遍才能找到。所以三元组表示法更适合“一次构建、多次遍历”的场景。

避坑指南

我曾经在做一个稀疏矩阵乘法时，忘了检查三元组表是否按行优先排序。结果两个矩阵的乘法结果完全不对。后来加了个排序步骤才搞定。

所以给你几个建议：

• 始终维护行优先顺序——插入新元素时找到正确位置再插入
• 注意下标从0开始——C语言数组下标从0开始，三元组里的行号列号也要从0开始
• 非零元素个数不要超过MAX_TERMS——否则会数组越界，这是C语言的老大难问题

知识体系图

下面这张图帮你理清稀疏数组压缩存储的核心脉络：

嗯，这张图把整个流程串起来了。你从原始数组出发，压缩成三元组表，需要时再还原回去。记住核心就一句话：只存非零，不存零。

三元组表示法是稀疏数组最基础的存储方式。虽然简单，但很多高级的稀疏矩阵库（比如CSR、CSC格式）都是在这个思想上发展出来的。把三元组搞明白，后面学其他格式就轻松多了。

---

公众号：蓝海资料掘金营，微信 deep3321