C语言稀疏矩阵详解（从零开始掌握稀疏矩阵的压缩存储与三元组表示法）

为什么需要压缩存储？

假设你有一个1000×1000的矩阵，总共包含100万个元素。如果其中只有1000个是非零的，那么用普通二维数组存储将浪费99.9%的内存！通过C语言数据结构中的压缩技术，我们只需存储非零元素及其位置信息，大幅节省空间。

三元组表示法

最常用的稀疏矩阵压缩方法是三元组表示法。每个非零元素用一个三元组 (行号, 列号, 值) 来表示。所有三元组按照行优先（或列优先）顺序存储在一个结构体数组中。

定义三元组结构

#include <stdio.h>#define MAXSIZE 100  // 最大非零元素个数typedef struct {    int row;   // 行下标    int col;   // 列下标    int value; // 非零值} Triple;typedef struct {    Triple data[MAXSIZE];    int rows;     // 矩阵总行数    int cols;     // 矩阵总列数    int nums;     // 非零元素个数} TSMatrix;  

创建稀疏矩阵示例

下面是一个函数，用于从普通二维数组构建三元组稀疏矩阵：

void createSparseMatrix(int matrix[][5], int rows, int cols, TSMatrix *sparse) {    sparse->rows = rows;    sparse->cols = cols;    sparse->nums = 0;    for (int i = 0; i < rows; i++) {        for (int j = 0; j < cols; j++) {            if (matrix[i][j] != 0) {                sparse->data[sparse->nums].row = i;                sparse->data[sparse->nums].col = j;                sparse->data[sparse->nums].value = matrix[i][j];                sparse->nums++;            }        }    }}  

完整使用示例

int main() {    int mat[4][5] = {        {0, 0, 3, 0, 0},        {0, 0, 0, 0, 7},        {0, 2, 0, 0, 0},        {1, 0, 0, 0, 0}    };    TSMatrix sparse;    createSparseMatrix(mat, 4, 5, &sparse);    printf("稀疏矩阵信息：\n");    printf("行数：%d，列数：%d，非零元素个数：%d\n",            sparse.rows, sparse.cols, sparse.nums);    printf("\n三元组列表：\n");    for (int i = 0; i < sparse.nums; i++) {        printf("(%d, %d, %d)\n",                sparse.data[i].row,                sparse.data[i].col,                sparse.data[i].value);    }    return 0;}  

其他压缩方法简介

除了三元组表示法，还有十字链表、行逻辑链接的顺序表等更高级的压缩方式，适用于需要频繁修改或进行矩阵运算的场景。但对于初学者来说，掌握三元组表示法是理解C语言稀疏矩阵的第一步。

总结

通过本教程，你应该已经了解了什么是稀疏矩阵、为什么要进行压缩存储，以及如何使用三元组表示法在C语言中实现稀疏矩阵的压缩。这种方法不仅节省内存，而且在某些操作（如转置）中还能提高效率。

记住，良好的C语言数据结构设计是编写高效程序的基础。继续练习，尝试实现稀疏矩阵的加法或转置操作，你会对这一概念有更深的理解！