稀疏矩阵的三元组表存储实现：从代码到核心知识点

在数据结构中，稀疏矩阵（非零元素占比极低的矩阵）若用普通二维数组存储，会造成大量内存浪费。严蔚敏《数据结构》教材中，三元组表是解决这一问题的经典方案——仅存储非零元素的“行号、列号、值”，再搭配矩阵的总行数、总列数和非零元素总数，实现高效存储。本文结合实例代码，拆解三元组表的核心知识点与时空复杂度，帮你吃透这一基础结构。

一、核心铺垫：为什么需要三元组表？

先明确一个前提：若矩阵维度为 r 行 × c 列，普通二维数组的空间复杂度是 O(r×c)，无论非零元素多少。
而稀疏矩阵（如非零占比<5%）的大部分空间都在存“0”，完全没必要。三元组表的思路是“抓重点”——只存非零元素的关键信息，空间复杂度直接降为 O(n)（n 是非零元素个数），尤其适合大维度稀疏矩阵。

二、核心数据结构：三元组表的定义

严蔚敏教材中，数据结构的定义遵循“基础单元+容器结构”的分层逻辑，代码里的结构体设计完全贴合这一思路：

1. 基础单元：Triple 三元组

存储单个非零元素的“坐标+值”，对应矩阵中的一个“有效点”：

typedef struct {
    int row;    // 行号（1-based，而非数组默认的0-based）
    int col;    // 列号（1-based）
    int value;  // 非零元素的值
} Triple;

关键细节：为什么用1-based索引？
这是严蔚敏教材的典型处理——贴合数学中矩阵的“行/列从1开始”的习惯，后续做矩阵转置、相加等运算时，逻辑更直观，避免频繁转换0-based和1-based的麻烦。

2. 容器结构：SparseMatrix 三元组表

管理整个稀疏矩阵的“元信息”和“所有非零元素”，是对外交互的核心结构：

typedef struct {
    Triple data[100];  // 存储所有非零元素（静态数组，简化版；教材中可扩展动态内存）
    int rows;          // 原矩阵的总行数
    int cols;          // 原矩阵的总列数
    int non_zero_cnt;  // 非零元素的总数（避免遍历data数组找长度）
} SparseMatrix;

设计巧思：non_zero_cnt 是“冗余但高效”的设计——无需遍历 data 数组统计非零元素个数，直接通过该变量获取，降低后续操作的时间成本。

三、代码解析：两种稀疏矩阵的构建与打印

代码实现了“规则稀疏矩阵（三对角矩阵）”和“随机稀疏矩阵”的构建，逻辑完全遵循教材中“先初始化元信息，再提取非零元素”的步骤，清晰易懂。

1. 规则稀疏矩阵：以三对角矩阵为例

三对角矩阵的非零元素仅分布在“主对角线、主对角线左侧、主对角线右侧”（即行i的列j满足 j = i-1, i, i+1），适合演示“按规律提取非零元素”：

void createRegularSparseMatrix(SparseMatrix *sm) {
    // 步骤1：初始化矩阵元信息（4行4列，非零计数从0开始）
    sm->rows = 4;
    sm->cols = 4;
    sm->non_zero_cnt = 0;

    // 步骤2：定义已知的三对角矩阵（0-based数组，后续转换为1-based行号/列号）
    int regularMatrix[4][4] = {
        {5, 8, 0, 0},
        {2, 6, 9, 0},
        {0, 3, 7, 1},
        {0, 0, 4, 8}
    };

    // 步骤3：遍历矩阵，提取非零元素到三元组表
    for (int i = 0; i < sm->rows; i++) {  // i是0-based行下标
        for (int j = 0; j < sm->cols; j++) {  // j是0-based列下标
            if (regularMatrix[i][j] != 0) {
                // 转换为1-based行号/列号，存入data数组
                sm->data[sm->non_zero_cnt].row = i + 1;
                sm->data[sm->non_zero_cnt].col = j + 1;
                sm->data[sm->non_zero_cnt].value = regularMatrix[i][j];
                sm->non_zero_cnt++;  // 非零计数+1
            }
        }
    }
}

运行结果：4行4列的三对角矩阵，非零元素共8个，三元组表会依次存储这些元素的（行号、列号、值）。

2. 随机稀疏矩阵：按概率生成非零元素

更贴近实际场景（如数据采集的稀疏数据），通过“随机概率p”控制非零元素占比，演示“动态提取非零元素”：

void createRandomSparseMatrix(SparseMatrix *sm, int rows, int cols, float p) {
    // 步骤1：初始化元信息（用户指定行数、列数）
    sm->rows = rows;
    sm->cols = cols;
    sm->non_zero_cnt = 0;
    srand((unsigned int)time(NULL));  // 初始化随机种子，确保每次结果不同

    // 步骤2：遍历每个位置，按概率p生成非零元素
    for (int i = 0; i < sm->rows; i++) {
        for (int j = 0; j < sm->cols; j++) {
            // 生成[0,1)的随机浮点数，小于p则为非零元素
            float randomProb = (float)rand() / RAND_MAX;
            if (randomProb < p) {
                sm->data[sm->non_zero_cnt].row = i + 1;
                sm->data[sm->non_zero_cnt].col = j + 1;
                sm->data[sm->non_zero_cnt].value = rand() % 10 + 1;  // 非零值：1~10
                sm->non_zero_cnt++;

                // 边界处理：避免data数组越界（静态数组最大存100个非零元素）
                if (sm->non_zero_cnt >= 100) break;
            }
        }
        if (sm->non_zero_cnt >= 100) break;
    }
}

关键细节：代码中用静态数组 data[100] 限制非零元素个数，教材中会扩展为动态内存分配（malloc），支持任意数量的非零元素，更灵活。

3. 打印函数：直观展示三元组表

打印矩阵元信息和所有非零元素，逻辑简单但实用——遍历 data 数组，按“行号→列号→值”的顺序输出，帮我们验证构建结果：

void printSparseMatrix(SparseMatrix *sm, const char *matrixType) {
    printf("\n=== %s 的三元组表 ===\n", matrixType);
    printf("原矩阵维度：%d行 × %d列\n", sm->rows, sm->cols);
    printf("非零元素总数：%d\n", sm->non_zero_cnt);
    printf("行号\t列号\t值\n");
    for (int i = 0; i < sm->non_zero_cnt; i++) {
        printf("%d\t%d\t%d\n", sm->data[i].row, sm->data[i].col, sm->data[i].value);
    }
}

四、关键分析：时空复杂度（核心考点）

无论是规则还是随机稀疏矩阵，核心操作的时空复杂度可统一分析，这也是面试/考试中常考的点：

1. 时间复杂度

构建矩阵（create函数）：需遍历原矩阵的每一个位置（r 行 × c 列），检查是否为非零元素，因此时间复杂度为 O(r×c)。注意：即使非零元素很少（如n=10），也需遍历所有 r×c 个位置，所以时间复杂度由矩阵维度决定，而非非零元素个数。
打印矩阵（print函数）：仅遍历非零元素（共n个），时间复杂度为 O(n)。

2. 空间复杂度

三元组表（SparseMatrix）：仅存储n个非零元素的三元组，以及3个整数（rows、cols、non_zero_cnt），空间复杂度为 O(n)。
对比普通二维数组：普通数组的空间复杂度是 O(r×c)，当矩阵稀疏时（如r=c=1000，n=100），三元组表的空间优势极其明显（100 vs 1,000,000）。

五、完整代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 三元组结构体：存储单个非零元素的行号、列号、值
typedef struct {
    int row;    // 行号（从1开始）
    int col;    // 列号（从1开始）
    int value;  // 非零元素值
} Triple;

// 三元组表结构体：存储稀疏矩阵的元信息和所有非零元素
typedef struct {
    Triple data[100];  // 存储三元组（假设最多100个非零元素）
    int rows;          // 原矩阵的行数
    int cols;          // 原矩阵的列数
    int non_zero_cnt;  // 非零元素的总数
} SparseMatrix;

// 构建普通稀疏矩阵（三对角矩阵）的三元组表
void createRegularSparseMatrix(SparseMatrix *sm) {
    // 1. 初始化矩阵元信息：4行4列的三对角矩阵
    sm->rows = 4;
    sm->cols = 4;
    sm->non_zero_cnt = 0;  // 初始非零元素计数为0

    // 2. 三对角矩阵的非零元素规律：行i的非零列j满足 j = i-1, i, i+1（需在[1,4]范围内）
    int regularMatrix[4][4] = {
        {5, 8, 0, 0},
        {2, 6, 9, 0},
        {0, 3, 7, 1},
        {0, 0, 4, 8}
    };

    // 3. 遍历矩阵，提取非零元素到三元组表
    for (int i = 0; i < sm->rows; i++) {  // 注意：数组下标从0开始，矩阵行号从1开始
        for (int j = 0; j < sm->cols; j++) {
            if (regularMatrix[i][j] != 0) {
                sm->data[sm->non_zero_cnt].row = i + 1;    // 转换为1-based行号
                sm->data[sm->non_zero_cnt].col = j + 1;    // 转换为1-based列号
                sm->data[sm->non_zero_cnt].value = regularMatrix[i][j];
                sm->non_zero_cnt++;  // 非零元素计数+1
            }
        }
    }
}

// 打印三元组表
void printSparseMatrix(SparseMatrix *sm, const char *matrixType) {
    printf("\n=== %s 的三元组表 ===\n", matrixType);
    printf("原矩阵维度：%d行 × %d列\n", sm->rows, sm->cols);
    printf("非零元素总数：%d\n", sm->non_zero_cnt);
    printf("行号\t列号\t值\n");
    for (int i = 0; i < sm->non_zero_cnt; i++) {
        printf("%d\t%d\t%d\n", 
               sm->data[i].row, 
               sm->data[i].col, 
               sm->data[i].value);
    }
}


// 构建随机稀疏矩阵的三元组表（rows行cols列，非零概率p）
void createRandomSparseMatrix(SparseMatrix *sm, int rows, int cols, float p) {
    // 1. 初始化矩阵元信息
    sm->rows = rows;
    sm->cols = cols;
    sm->non_zero_cnt = 0;
    srand((unsigned int)time(NULL));  // 初始化随机种子（确保每次运行结果不同）

    // 2. 随机生成非零元素：每个位置以概率p为非零，1-p为零
    for (int i = 0; i < sm->rows; i++) {
        for (int j = 0; j < sm->cols; j++) {
            // 生成[0,1)的随机浮点数，若小于p则设为非零元素
            float randomProb = (float)rand() / RAND_MAX;
            if (randomProb < p) {
                sm->data[sm->non_zero_cnt].row = i + 1;
                sm->data[sm->non_zero_cnt].col = j + 1;
                sm->data[sm->non_zero_cnt].value = rand() % 10 + 1;  // 非零值：1~10随机
                sm->non_zero_cnt++;
                // 防止三元组表数组越界（此处简化处理，假设非零元素不超过100）
                if (sm->non_zero_cnt >= 100) break;
            }
        }
        if (sm->non_zero_cnt >= 100) break;
    }
}


int main() {
    SparseMatrix regularSM, randomSM;

    // 1. 构建并打印普通稀疏矩阵（三对角矩阵）
    createRegularSparseMatrix(&regularSM);
    printSparseMatrix(&regularSM, "普通稀疏矩阵（三对角）");

    // 2. 构建并打印随机稀疏矩阵（4行4列，非零概率25%）
    createRandomSparseMatrix(&randomSM, 4, 4, 0.25);
    printSparseMatrix(&randomSM, "随机稀疏矩阵");

    return 0;
}

目录CONTENT

稀疏矩阵的三元组表存储实现