xiangyun61头像
关注

【408数据结构 11】稀疏矩阵：三元组与十字链表，转置算法一次讲清

【408数据结构 11】稀疏矩阵：三元组与十字链表，转置算法一次讲清

专栏导航：本篇是《408数据结构：C++手写实现 + 图解 + 真题》第 11 篇。
上一篇：[【408数据结构 10】数组与特殊矩阵压缩：地址计算一次搞懂]
下一篇：[【408数据结构 12】字符串模式匹配：BF与KMP]

文章目录

先做个自测

下面这道题，你能 30 秒内选出来吗？

稀疏矩阵采用三元组顺序表存储，进行快速转置时，需要预先统计（ ）。
A. 每行的非零元素个数
B. 每列的非零元素个数
C. 每行的零元素个数
D. 每列的零元素个数

如果你靠“感觉”选，或者分不清普通转置和快速转置的区别，那这篇就是为你写的。

稀疏矩阵是 408 数组章节的收尾考点，选择题常考三元组结构和转置算法。
十字链表则偶尔出现在选择题里，考它的结点结构和适用场景。

今天我们把稀疏矩阵一次讲透。

一、408 怎么考稀疏矩阵？先看真题分布

考法出现频率典型问法
稀疏矩阵的定义★★★什么是稀疏矩阵
三元组表示法★★★★★三元组的结点结构、元素个数
三元组转置★★★★普通转置的时间复杂度
快速转置★★★★★快速转置的预处理、时间复杂度
十字链表★★★★十字链表的结点结构、适用场景
稀疏矩阵与特殊矩阵对比★★★两者的区别

重点：三元组表示法、快速转置，这两个必须拿满分。

二、什么是稀疏矩阵

2.1 定义

如果一个矩阵中非零元素个数远小于零元素个数，且非零元素分布没有规律，则称为稀疏矩阵。

例如：

       列0   列1   列2   列3   列4
行0   [  0     0     3     0     0  ]
行1   [  0     0     0     0     0  ]
行2   [  0     4     0     0     6  ]
行3   [  0     0     0     0     0  ]
行4   [  5     0     0     0     0  ]

5 行 5 列，25 个元素，非零元素只有 4 个。

2.2 稀疏矩阵与特殊矩阵的区别

对比项特殊矩阵稀疏矩阵
非零元素分布有规律无规律
压缩方式下标映射公式三元组、十字链表
代表对称、三角、对角随机稀疏
存储重点存一半或一条带只存非零元素

408 常考：

稀疏矩阵压缩存储后，失去了随机访问的能力。
因为非零元素的下标不再有规律，无法通过公式直接计算。

三、三元组表示法

3.1 基本思想

只存非零元素，每个非零元素记录三个信息：

  • 行下标 i
  • 列下标 j
  • 值 v

这就是三元组 (i, j, v)。

3.2 三元组顺序表

把所有三元组按行优先顺序存入一个数组，再记录矩阵的行数、列数、非零元素个数。

结构定义：

#define MAXSIZE 100

typedef int ElemType;

typedef struct {
    int i, j;       // 行下标、列下标
    ElemType v;     // 值
} Triple;

typedef struct {
    Triple data[MAXSIZE + 1];  // data[0] 不用
    int rows, cols, nums;      // 行数、列数、非零元素个数
} TSMatrix;

3.3 图解

原始矩阵：
       列0   列1   列2   列3   列4
行0   [  0     0     3     0     0  ]
行1   [  0     0     0     0     0  ]
行2   [  0     4     0     0     6  ]
行3   [  0     0     0     0     0  ]
行4   [  5     0     0     0     0  ]

三元组顺序表：
下标:  1      2      3      4
      (0,2,3) (2,1,4) (2,4,6) (4,0,5)

rows = 5, cols = 5, nums = 4

3.4 三元组顺序表的优缺点

优点：

  • 存储密度高，只存非零元素。
  • 结构简单，容易实现。

缺点：

  • 失去随机访问，查找某个元素需要遍历。
  • 插入删除不方便，需要移动元素。
  • 非零元素个数动态变化时，数组容量不好确定。

408 常考：

三元组顺序表中，非零元素个数为 t，则存储空间为 O(t)。
三元组顺序表适合非零元素个数固定的场景。

四、三元组转置（普通转置）

4.1 问题描述

给定稀疏矩阵 A 的三元组表示，求其转置矩阵 B 的三元组表示。

转置规则：

B[j][i] = A[i][j]

即把每个三元组 (i, j, v) 变成 (j, i, v)。

4.2 普通转置思路

方法一：按列扫描

  1. 遍历 A 的每一列 col（从 0 到 cols-1）。
  2. 在 A 中找所有列下标为 col 的三元组。
  3. 把它们转置后依次放入 B。

图解：

A 的三元组：
(0,2,3), (2,1,4), (2,4,6), (4,0,5)

按列扫描：

col = 0：
  找到 (4,0,5)，转置为 (0,4,5)，放入 B

col = 1：
  找到 (2,1,4)，转置为 (1,2,4)，放入 B

col = 2：
  找到 (0,2,3)，转置为 (2,0,3)，放入 B

col = 3：
  没有

col = 4：
  找到 (2,4,6)，转置为 (4,2,6)，放入 B

B 的三元组：
(0,4,5), (1,2,4), (2,0,3), (4,2,6)

4.3 普通转置代码

void TransposeTSMatrix(TSMatrix A, TSMatrix &B) {
    B.rows = A.cols;
    B.cols = A.rows;
    B.nums = A.nums;
    if (B.nums == 0) return;

    int q = 1;  // B 的三元组下标
    for (int col = 0; col < A.cols; col++) {
        for (int p = 1; p <= A.nums; p++) {
            if (A.data[p].j == col) {
                B.data[q].i = A.data[p].j;
                B.data[q].j = A.data[p].i;
                B.data[q].v = A.data[p].v;
                q++;
            }
        }
    }
}

4.4 复杂度分析

  • 时间复杂度：O(cols * nums)，即列数乘以非零元素个数。
  • 空间复杂度：O(1)（不计结果矩阵）。

408 常考：

普通转置的时间复杂度是 O(cols * nums)。

五、快速转置（408 高频）

5.1 为什么需要快速转置

普通转置对每一列都要扫描一遍三元组，效率低。
快速转置通过预处理，把时间复杂度降到 O(nums)。

5.2 核心思想

预先统计：

  1. 每一列的非零元素个数 num[col]。
  2. 每一列第一个非零元素在转置后的起始位置 cpot[col]。

然后遍历一次 A 的三元组，直接放到 B 的正确位置。

5.3 公式

cpot[0] = 1
cpot[col] = cpot[col-1] + num[col-1]   (col >= 1)

5.4 图解

A 的三元组：
下标:  1      2      3      4
      (0,2,3) (2,1,4) (2,4,6) (4,0,5)

统计每列非零元素个数：
col 0: 1个  (来自 (4,0,5))
col 1: 1个  (来自 (2,1,4))
col 2: 1个  (来自 (0,2,3))
col 3: 0个
col 4: 1个  (来自 (2,4,6))

num = [1, 1, 1, 0, 1]

计算 cpot：
cpot[0] = 1
cpot[1] = cpot[0] + num[0] = 1 + 1 = 2
cpot[2] = cpot[1] + num[1] = 2 + 1 = 3
cpot[3] = cpot[2] + num[2] = 3 + 1 = 4
cpot[4] = cpot[3] + num[3] = 4 + 0 = 4

cpot = [1, 2, 3, 4, 4]

遍历 A 的三元组：

(0,2,3)：col = 2，放到 B 的 cpot[2] = 3 位置，cpot[2]++ -> 4
B[3] = (2,0,3)

(2,1,4)：col = 1，放到 B 的 cpot[1] = 2 位置，cpot[1]++ -> 3
B[2] = (1,2,4)

(2,4,6)：col = 4，放到 B 的 cpot[4] = 4 位置，cpot[4]++ -> 5
B[4] = (4,2,6)

(4,0,5)：col = 0，放到 B 的 cpot[0] = 1 位置，cpot[0]++ -> 2
B[1] = (0,4,5)

最终 B：
B[1] = (0,4,5)
B[2] = (1,2,4)
B[3] = (2,0,3)
B[4] = (4,2,6)

5.5 快速转置代码

void FastTransposeTSMatrix(TSMatrix A, TSMatrix &B) {
    B.rows = A.cols;
    B.cols = A.rows;
    B.nums = A.nums;
    if (B.nums == 0) return;

    int num[MAXSIZE] = {0};
    int cpot[MAXSIZE] = {0};

    // 统计每列非零元素个数
    for (int p = 1; p <= A.nums; p++) {
        num[A.data[p].j]++;
    }

    // 计算每列第一个非零元素的起始位置
    cpot[0] = 1;
    for (int col = 1; col < A.cols; col++) {
        cpot[col] = cpot[col - 1] + num[col - 1];
    }

    // 快速转置
    for (int p = 1; p <= A.nums; p++) {
        int col = A.data[p].j;
        int q = cpot[col];
        B.data[q].i = A.data[p].j;
        B.data[q].j = A.data[p].i;
        B.data[q].v = A.data[p].v;
        cpot[col]++;
    }
}

5.6 复杂度分析

  • 时间复杂度：O(nums + cols)，通常简写为 O(nums)。
  • 空间复杂度：O(cols)，需要 num 和 cpot 两个辅助数组。

对比：

算法时间复杂度空间复杂度
普通转置O(cols * nums)O(1)
快速转置O(nums + cols)O(cols)

408 常考：

快速转置用空间换时间，时间复杂度从 O(cols * nums) 降到 O(nums + cols)。

六、十字链表

6.1 为什么需要十字链表

三元组顺序表有两个问题：

  1. 插入删除不方便：需要移动元素。
  2. 无法快速访问某行或某列：需要遍历。

十字链表解决了这些问题：它把行链表和列链表交叉在一起。

6.2 结点结构

每个非零元素结点有 5 个域：

+-----+-----+-----+-----+-----+
| row | col | val | down| right|
+-----+-----+-----+-----+-----+
  • row：行下标
  • col：列下标
  • val：值
  • down：指向同列下一个非零元素
  • right：指向同行下一个非零元素

6.3 整体结构

行头指针数组：rhead[0..rows-1]
列头指针数组：chead[0..cols-1]

每个行头结点指向该行第一个非零元素。
每个列头结点指向该列第一个非零元素。

图解：

矩阵：
       列0   列1   列2
行0   [  0     3     0  ]
行1   [  4     0     6  ]
行2   [  0     0     5  ]

十字链表：

rhead[0] --> (0,1,3) --right--> NULL
              |
            down
              |
rhead[1] --> (1,0,4) --right--> (1,2,6) --right--> NULL
              |                    |
            down                 down
              |                    |
rhead[2] --> (2,2,5) --right--> NULL
              ^
              |
chead[0] --> (1,0,4)
chead[1] --> (0,1,3)
chead[2] --> (1,2,6) --down--> (2,2,5)

6.4 结点定义

typedef struct OLNode {
    int i, j;               // 行下标、列下标
    ElemType v;             // 值
    struct OLNode *right;   // 同行下一个
    struct OLNode *down;    // 同列下一个
} OLNode, *OLink;

typedef struct {
    OLink *rhead;  // 行头指针数组
    OLink *chead;  // 列头指针数组
    int rows, cols, nums;
} CrossList;

6.5 十字链表的优缺点

优点：

  • 插入删除方便，不需要移动元素。
  • 可以快速访问某行或某列。
  • 适合非零元素动态变化的场景。

缺点：

  • 结构复杂，指针多，空间开销大。
  • 实现难度高。

408 常考：

十字链表适合非零元素个数动态变化的稀疏矩阵。
三元组顺序表适合非零元素个数固定的稀疏矩阵。

七、完整测试代码

#include <iostream>
using namespace std;

#define MAXSIZE 100
typedef int ElemType;

typedef struct {
    int i, j;
    ElemType v;
} Triple;

typedef struct {
    Triple data[MAXSIZE + 1];
    int rows, cols, nums;
} TSMatrix;

// 创建三元组
void CreateTSMatrix(TSMatrix &A, int rows, int cols) {
    A.rows = rows;
    A.cols = cols;
    A.nums = 0;
}

// 添加非零元素
void AddTriple(TSMatrix &A, int i, int j, ElemType v) {
    if (A.nums >= MAXSIZE) return;
    A.nums++;
    A.data[A.nums].i = i;
    A.data[A.nums].j = j;
    A.data[A.nums].v = v;
}

// 打印三元组
void PrintTSMatrix(TSMatrix A) {
    cout << "rows=" << A.rows << ", cols=" << A.cols
         << ", nums=" << A.nums << endl;
    for (int p = 1; p <= A.nums; p++) {
        cout << "(" << A.data[p].i << ","
             << A.data[p].j << ","
             << A.data[p].v << ")" << endl;
    }
}

// 普通转置
void TransposeTSMatrix(TSMatrix A, TSMatrix &B) {
    B.rows = A.cols;
    B.cols = A.rows;
    B.nums = A.nums;
    if (B.nums == 0) return;
    int q = 1;
    for (int col = 0; col < A.cols; col++) {
        for (int p = 1; p <= A.nums; p++) {
            if (A.data[p].j == col) {
                B.data[q].i = A.data[p].j;
                B.data[q].j = A.data[p].i;
                B.data[q].v = A.data[p].v;
                q++;
            }
        }
    }
}

// 快速转置
void FastTransposeTSMatrix(TSMatrix A, TSMatrix &B) {
    B.rows = A.cols;
    B.cols = A.rows;
    B.nums = A.nums;
    if (B.nums == 0) return;

    int num[MAXSIZE] = {0};
    int cpot[MAXSIZE] = {0};

    for (int p = 1; p <= A.nums; p++) {
        num[A.data[p].j]++;
    }

    cpot[0] = 1;
    for (int col = 1; col < A.cols; col++) {
        cpot[col] = cpot[col - 1] + num[col - 1];
    }

    for (int p = 1; p <= A.nums; p++) {
        int col = A.data[p].j;
        int q = cpot[col];
        B.data[q].i = A.data[p].j;
        B.data[q].j = A.data[p].i;
        B.data[q].v = A.data[p].v;
        cpot[col]++;
    }
}

int main() {
    TSMatrix A, B, C;
    CreateTSMatrix(A, 5, 5);
    AddTriple(A, 0, 2, 3);
    AddTriple(A, 2, 1, 4);
    AddTriple(A, 2, 4, 6);
    AddTriple(A, 4, 0, 5);

    cout << "原始矩阵三元组：" << endl;
    PrintTSMatrix(A);

    cout << "\n普通转置：" << endl;
    TransposeTSMatrix(A, B);
    PrintTSMatrix(B);

    cout << "\n快速转置：" << endl;
    FastTransposeTSMatrix(A, C);
    PrintTSMatrix(C);

    return 0;
}

运行结果：

原始矩阵三元组：
rows=5, cols=5, nums=4
(0,2,3)
(2,1,4)
(2,4,6)
(4,0,5)

普通转置：
rows=5, cols=5, nums=4
(0,4,5)
(1,2,4)
(2,0,3)
(4,2,6)

快速转置：
rows=5, cols=5, nums=4
(0,4,5)
(1,2,4)
(2,0,3)
(4,2,6)

八、真题演练

8.1 稀疏矩阵定义

题目：
下列关于稀疏矩阵的说法中，正确的是（ ）。

A. 稀疏矩阵中非零元素个数远小于零元素个数
B. 稀疏矩阵中非零元素分布有规律
C. 稀疏矩阵压缩后仍支持随机访问
D. 稀疏矩阵只能用三元组存储

答案：A

8.2 三元组存储

题目：
稀疏矩阵采用三元组顺序表存储，非零元素个数为 t，则存储空间为（ ）。

A. O(1)
B. O(t)
C. O(rows * cols)
D. O(rows + cols)

答案：B

8.3 普通转置复杂度

题目：
稀疏矩阵采用三元组顺序表存储，普通转置的时间复杂度是（ ）。

A. O(nums)
B. O(cols)
C. O(cols * nums)
D. O(cols + nums)

答案：C

8.4 快速转置

题目：
稀疏矩阵采用三元组顺序表存储，进行快速转置时，需要预先统计（ ）。

A. 每行的非零元素个数
B. 每列的非零元素个数
C. 每行的零元素个数
D. 每列的零元素个数

答案：B

8.5 十字链表

题目：
十字链表适合存储（ ）。

A. 对称矩阵
B. 三角矩阵
C. 非零元素个数动态变化的稀疏矩阵
D. 三对角矩阵

答案：C

九、一句话记住稀疏矩阵

稀疏矩阵无规律，三元组只存非零。
普通转置按列扫，快速转置先统计。
num 统列数，cpot 算起点，一次遍历放到位。
十字链表指针多，动态变化最合适。

十、总结与下一篇预告

本篇讲了：

  • 稀疏矩阵的定义与特点。
  • 三元组表示法与顺序表存储。
  • 普通转置的思路与代码。
  • 快速转置的预处理与代码。
  • 十字链表的结点结构与适用场景。
  • 408 真题与易错点。

一句话总结：

稀疏矩阵的核心是“只存非零元素”，三元组顺序表适合静态，十字链表适合动态，快速转置用空间换时间。

下一篇进入字符串：

【408数据结构 12】字符串模式匹配：BF与KMP

我会讲字符串的存储结构、BF 算法、KMP 算法的 next 数组求法、nextval 优化，配 408 真题和完整 C++ 代码。

专栏导航

  • 上一篇：[【408数据结构 10】数组与特殊矩阵压缩：地址计算一次搞懂]
  • 下一篇：[【408数据结构 12】字符串模式匹配：BF与KMP]
  • 专栏目录：[《408数据结构：C++手写实现 + 图解 + 真题》]

标签：数据结构、C++、考研408、计算机考研、算法
分类：数据结构与算法

如果这篇对你有帮助，欢迎点赞、收藏、评论。你的支持是我持续更新的动力。

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/xiangyun61/article/details/165999443

文章来源转载

评论

赞0

评论列表

微信小程序
QQ小程序

关于作者

点赞数：0
关注数：0
粉丝：0
文章：0
关注标签：0
加入于：--