稀疏矩阵压缩详解（C语言实现三元组表法高效存储）

什么是稀疏矩阵？

稀疏矩阵是指非零元素的个数远小于矩阵总元素个数的矩阵。例如一个 1000×1000 的矩阵，如果只有不到 1% 的元素是非零的，那么它就是一个典型的稀疏矩阵。

为什么需要压缩存储？

假设一个 10000×10000 的矩阵，使用 int 类型（4 字节）存储，传统方式需要约 400MB 内存。但如果其中只有 10000 个非零元素，那么实际只需要存储这 10000 个值即可，大大节省内存。这就是矩阵存储优化的核心思想。

三元组表法：最常用的稀疏矩阵压缩方法

三元组表法是实现稀疏矩阵压缩的经典方法。它将每个非零元素用一个三元组 (行号, 列号, 值) 来表示，并将所有三元组按行优先顺序存储在一个结构体数组中。

数据结构定义

#include <stdio.h>#include <stdlib.h>// 定义三元组结构体typedef struct {    int row;   // 行下标    int col;   // 列下标    int value; // 非零元素的值} Triple;// 定义稀疏矩阵结构体typedef struct {    Triple *data;      // 三元组数组    int rows;         // 矩阵行数    int cols;         // 矩阵列数    int nonZeroCount; // 非零元素个数} SparseMatrix;

压缩函数实现

下面是一个将普通二维数组压缩为稀疏矩阵的 C 语言函数：

// 将普通矩阵压缩为稀疏矩阵SparseMatrix* compressMatrix(int **matrix, int rows, int cols) {    // 第一步：统计非零元素个数    int count = 0;    for (int i = 0; i < rows; i++) {        for (int j = 0; j < cols; j++) {            if (matrix[i][j] != 0) {                count++;            }        }    }    // 第二步：分配内存    SparseMatrix *sparse = (SparseMatrix*)malloc(sizeof(SparseMatrix));    sparse->rows = rows;    sparse->cols = cols;    sparse->nonZeroCount = count;    sparse->data = (Triple*)malloc(count * sizeof(Triple));    // 第三步：填充三元组    int index = 0;    for (int i = 0; i < rows; i++) {        for (int j = 0; j < cols; j++) {            if (matrix[i][j] != 0) {                sparse->data[index].row = i;                sparse->data[index].col = j;                sparse->data[index].value = matrix[i][j];                index++;            }        }    }    return sparse;}

完整示例程序

int main() {    // 创建一个 4x5 的稀疏矩阵    int matrix[4][5] = {        {0, 0, 3, 0, 0},        {0, 0, 0, 0, 7},        {0, 9, 0, 0, 0},        {0, 0, 0, 2, 0}    };    // 由于 C 语言不支持直接传递二维数组指针，这里做简单转换    int *ptr[4];    for (int i = 0; i < 4; i++) {        ptr[i] = matrix[i];    }    // 压缩矩阵    SparseMatrix *sparse = compressMatrix(ptr, 4, 5);    // 打印压缩结果    printf("稀疏矩阵信息：\n");    printf("行数：%d，列数：%d，非零元素个数：%d\n",            sparse->rows, sparse->cols, sparse->nonZeroCount);    printf("三元组表：\n");    for (int i = 0; i < sparse->nonZeroCount; i++) {        printf("(%d, %d, %d)\n",                sparse->data[i].row,                sparse->data[i].col,                sparse->data[i].value);    }    // 释放内存    free(sparse->data);    free(sparse);    return 0;}

优势与应用场景

• 内存效率高：只存储非零元素，大幅减少内存占用。
• 适合大规模计算：在有限内存下处理超大矩阵成为可能。
• 算法优化基础：为后续的矩阵运算（如转置、乘法）提供高效数据结构。
• 广泛应用：在有限元分析、网络分析、机器学习等领域都有重要应用。

总结

通过本文的学习，你应该已经掌握了使用C语言稀疏矩阵压缩的基本方法。三元组表法作为最基础的稀疏矩阵压缩技术，不仅概念简单，而且实现容易，是理解更高级压缩方法（如十字链表、CSR格式等）的基础。掌握这种矩阵存储优化技巧，将帮助你在处理大规模数据时更加得心应手。

提示：在实际项目中，还可以考虑使用专业的数学库（如 Intel MKL、Eigen）来处理稀疏矩阵，它们提供了高度优化的实现。