408

数据结构

DS-03-04 特殊矩阵的压缩存储（对称/三角/对角/稀疏矩阵）

---

一、定位信息

项目	内容
所属圈层	核心层
考点热度	H级（高频重点） — 特殊矩阵压缩存储是408选择题高频考点，对称矩阵下标映射和稀疏矩阵三元组表几乎每年都会涉及，分值2–4分
前置知识回顾	需掌握"多维数组的存储方式（行优先/列优先）"（DS-03-03），理解地址计算的基本原理
知识网络定位	压缩存储是数组存储的特殊应用，目的是节省空间；稀疏矩阵的三元组表是数据压缩思想的体现，与后续"图的存储（邻接矩阵/邻接表）"有概念上的呼应

---

二、知识点讲解

2.1 为什么要压缩存储？

对于特殊矩阵（如对称矩阵、三角矩阵、对角矩阵），大量元素具有对称性或固定值（如0），若按普通二维数组存储会浪费大量空间。压缩存储将这些冗余信息去除，只存储必要元素。

2.2 对称矩阵

定义：$n$ 阶方阵 $A$ 满足 $a_{ij} = a_{ji}$（$1 \leq i,j \leq n$），即关于主对角线对称。

压缩策略：只存储下三角（含对角线）的元素，共 $n(n+1)/2$ 个。

存储方式：将下三角元素按行优先存入一维数组 $B[0..n(n+1)/2-1]$。

下标映射公式（下标从1开始，行优先）：

对于元素 $a_{ij}$（$i \geq j$，即在下三角区域）： $k = \frac{i(i-1)}{2} + j - 1$

其中 $k$ 为一维数组 $B$ 的下标（从0开始）。

对于上三角元素 $a_{ij}$（$i < j$），利用对称性：$a_{ij} = a_{ji}$，交换 $i$ 和 $j$ 后代入公式： $k = \frac{j(j-1)}{2} + i - 1$

统一公式（不论 $i$ 与 $j$ 的大小关系）：

设 $I = \max(i, j)$，$J = \min(i, j)$，则： $k = \frac{I(I-1)}{2} + J - 1$

推导过程：

• 下三角按行优先存储
• 第1行有1个元素，第2行有2个元素，……，第 $(i-1)$ 行有 $(i-1)$ 个元素
• 到第 $i$ 行前共存储了 $1+2+\cdots+(i-1) = \frac{i(i-1)}{2}$ 个元素
• 第 $i$ 行中 $a_{ij}$ 是第 $j$ 个元素
• 所以 $a_{ij}$ 是整个下三角中的第 $\frac{i(i-1)}{2} + j$ 个元素（从1开始计数）
• 转为数组下标（从0开始）：$k = \frac{i(i-1)}{2} + j - 1$

示例：4阶对称矩阵，$a_{32}$ 的下标： $k = \frac{3 \times 2}{2} + 2 - 1 = 3 + 1 = 4$$B[4]$ 存储的就是 $a_{32}$。

2.3 三角矩阵

上三角矩阵：主对角线以下元素全为常数 $c$（通常为0）。

下三角矩阵：主对角线以上元素全为常数 $c$（通常为0）。

压缩策略：

• 下三角矩阵：存储下三角 $n(n+1)/2$ 个元素 + 1个常数 $c$
• 上三角矩阵：存储上三角 $n(n+1)/2$ 个元素 + 1个常数 $c$

下三角矩阵的下标映射（下标从1开始）：

与对称矩阵的下三角部分完全相同： $k = \frac{i(i-1)}{2} + j - 1 \quad (i \geq j)$

当 $i < j$ 时，$a_{ij} = c$（常数），直接返回常数即可。

上三角矩阵的下标映射（下标从1开始，按行优先存储上三角）：

第1行有 $n$ 个元素，第2行有 $(n-1)$ 个元素，……，第 $(i-1)$ 行有 $(n-i+2)$ 个元素。 $k = \frac{(i-1)(2n-i+2)}{2} + (j-i) \quad (i \leq j)$

2.4 三对角矩阵（带状矩阵）

定义：$n$ 阶三对角矩阵中，只有主对角线及其上下各一条对角线上有非零元素，即 $|i-j| \leq 1$ 时 $a_{ij} \neq 0$。

压缩策略：按行优先将三条对角线上的元素存入一维数组，共 $3n-2$ 个元素。

下标映射公式（下标从1开始）：

$k = 2i + j - 3 \quad (|i-j| \leq 1)$

推导：

• 第1行只有2个元素（$a_{11}, a_{12}$）
• 第2行到第 $(n-1)$ 行每行有3个元素
• 第 $n$ 行只有2个元素（$a_{n,n-1}, a_{nn}$）
• 前 $(i-1)$ 行共存储了 $2 + 3(i-2) = 3i - 4$ 个元素（当 $i \geq 2$）
• 第 $i$ 行中，$a_{ij}$ 是该行的第 $(j-i+2)$ 个元素（当 $j=i-1$ 时为第1个，$j=i$ 时为第2个，$j=i+1$ 时为第3个）
• 所以 $k = (3i-4) + (j-i+2) - 1 = 2i+j-3$（减1因为下标从0开始）

2.5 稀疏矩阵

定义：矩阵中非零元素个数远小于矩阵总元素个数（通常非零元素占比 $< 5\%$）。

压缩存储方式一：三元组表

用三元组 $(i, j, v)$ 表示每个非零元素，其中 $i$ 为行号、$j$ 为列号、$v$ 为元素值。

#define MAXSIZE 1000          // 非零元素最大个数

typedef struct {
    int row;                  // 行号
    int col;                  // 列号
    ElemType value;           // 元素值
} Triple;

typedef struct {
    Triple data[MAXSIZE];     // 三元组数组
    int m, n;                 // 矩阵的行数和列数
    int num;                  // 非零元素个数
} TSMatrix;

示例：矩阵 $\begin{pmatrix} 0 & 0 & 3 & 0 \\ 4 & 0 & 0 & 0 \\ 0 & 5 & 0 & 0 \end{pmatrix}$

三元组表（按行优先排列）：

下标	row	col	value
0	1	3	3
1	2	1	4
2	3	2	5

注意：408中行号和列号通常从1开始。

压缩存储方式二：十字链表

每个非零元素用一个节点表示，节点同时在行链表和列链表中链接。适用于非零元素位置和数量经常变化的场景。

节点结构：[row | col | value | right | down]
- right：指向同行下一个非零元素
- down：指向同列下一个非零元素

2.6 稀疏矩阵的转置

常规转置：将三元组表中每个元素的行号和列号交换，然后按新的行优先顺序重新排列。

快速转置算法（408常考）：

核心思想：预计算原矩阵每一列的非零元素个数，从而确定转置后每一行（即原矩阵每一列）在新三元组表中的起始位置。

// 快速转置：将矩阵M转置为矩阵T
void FastTranspose(TSMatrix M, TSMatrix &T) {
    T.m = M.n;                // 转置后行列互换
    T.n = M.m;
    T.num = M.num;            // 非零元素个数不变

    if (T.num == 0) return;   // 空矩阵无需转置

    int col;                  // 当前列号
    int position[M.n + 1];    // position[col]：第col列在T中的起始位置
    int count[M.n + 1];       // count[col]：第col列的非零元素个数

    // 第一步：统计每一列的非零元素个数
    for (col = 1; col <= M.n; col++)
        count[col] = 0;       // 初始化
    for (int k = 0; k < M.num; k++)
        count[M.data[k].col]++; // 统计每列非零元素数

    // 第二步：计算每一列在T中的起始位置
    position[1] = 0;          // 第1列从下标0开始
    for (col = 2; col <= M.n; col++)
        position[col] = position[col - 1] + count[col - 1];

    // 第三步：将M中的元素按列序依次放入T
    for (int k = 0; k < M.num; k++) {
        col = M.data[k].col;  // 取当前元素的列号
        int t = position[col]; // T中的存放位置
        T.data[t].row = M.data[k].col;   // 行列互换
        T.data[t].col = M.data[k].row;
        T.data[t].value = M.data[k].value;
        position[col]++;      // 该列的下一个位置
    }
}

时间复杂度：$O(n + \text{num})$，其中 $n$ 为列数，$\text{num}$ 为非零元素个数。优于常规转置的 $O(n \times \text{num})$。

---

三、记忆与理解辅助

技巧1：对称矩阵下标映射口诀

"大数定行小定列，行代入 i(i-1)/2，列直接加上去，最后别忘减个1"

即：$k = \frac{\max(i,j) \times [\max(i,j)-1]}{2} + \min(i,j) - 1$

技巧2：各类特殊矩阵压缩存储对比表

矩阵类型	非零元素个数	压缩后存储量	下标公式（下标从1起）
$n$ 阶对称矩阵	$n^2$	$n(n+1)/2$	$k=\frac{i(i-1)}{2}+j-1$（$i\geq j$）
$n$ 阶下三角矩阵	$\leq n(n+1)/2$	$n(n+1)/2+1$	同对称矩阵下三角
$n$ 阶上三角矩阵	$\leq n(n+1)/2$	$n(n+1)/2+1$	$k=\frac{(i-1)(2n-i+2)}{2}+(j-i)$（$i\leq j$）
$n$ 阶三对角矩阵	$3n-2$	$3n-2$	$k=2i+j-3$
稀疏矩阵	$\ll n^2$	$3 \times \text{num}+1$	三元组表

技巧3：稀疏矩阵两种存储方式对比

比较项	三元组表	十字链表
存储结构	一维数组	链表
空间开销	固定（预分配MAXSIZE）	动态（按需分配）
适用场景	非零元素数量基本不变	非零元素频繁增删
按行/列访问	需遍历	沿 right/down 链快速访问
实现复杂度	简单	较复杂
408考查频率	高	低（了解即可）

技巧4：快速转置的"两遍扫描"逻辑

第一遍：数数（统计每列非零元素个数） 第二遍：定位（计算每列在转置后的起始位置） 第三遍：搬家（按列序依次放入转置矩阵）

---

四、例题与精解

例题1（基础）

题目：设6阶对称矩阵 $A$ 按行优先压缩存储下三角元素到一维数组 $B[0..20]$ 中，已知 $a_{11}$ 存放在 $B[0]$，求 $a_{53}$ 和 $a_{35}$ 分别存放在 $B$ 的哪个下标位置？

命题意图：考查对称矩阵下标映射公式的直接应用，以及对称性的理解。

审题分析：

• 已知：6阶对称矩阵，下标从1开始，$a_{11}$ 在 $B[0]$
• 求解：$a_{53}$ 和 $a_{35}$ 在 $B$ 中的下标

解题思路：

• $a_{53}$：$i=5, j=3$，$i>j$ 在下三角，直接代入公式
• $a_{35}$：$i=3, j=5$，$i<j$ 在上三角，利用对称性 $a_{35}=a_{53}$

完整步骤：

$a_{53}$ 的下标（$i=5 \geq j=3$，在下三角）： $k = \frac{i(i-1)}{2} + j - 1 = \frac{5 \times 4}{2} + 3 - 1 = 10 + 2 = 12$

所以 $a_{53}$ 存放在 $B[12]$。

$a_{35}$ 的下标（$i=3 < j=5$，在上三角）： 利用对称性：$a_{35} = a_{53}$，所以 $a_{35}$ 也存放在 $B[12]$。

验证：

• 第1行：1个元素（$a_{11}$）
• 第2行：2个元素（$a_{21}, a_{22}$）
• 第3行：3个元素（$a_{31}, a_{32}, a_{33}$）
• 第4行：4个元素（$a_{41}, a_{42}, a_{43}, a_{44}$）
• 第5行前4个：$a_{51}, a_{52}, a_{53}, a_{54}$
• $a_{53}$ 是第 $1+2+3+4+2 = 12$ 个元素（从1计数），对应 $B[11]$？

等等，让我重新验证：

• $a_{53}$ 在第5行，是该行的第3个元素
• 前4行共有 $1+2+3+4 = 10$ 个元素
• 所以 $a_{53}$ 是第 $10+3 = 13$ 个元素（从1计数），对应 $B[12]$ ✓

方法反思：

• 对称矩阵的核心：上三角元素可通过交换下标映射到下三角
• 统一公式 $k = \frac{I(I-1)}{2} + J - 1$（$I=\max(i,j), J=\min(i,j)$）可以避免分情况讨论

例题2（中等）

题目：稀疏矩阵 $M$ 为 $4 \times 5$ 矩阵，有6个非零元素，其三元组表如下（下标从1开始）：

下标	row	col	value
0	1	2	3
1	1	4	5
2	2	3	2
3	3	1	7
4	3	4	1
5	4	2	6

给出快速转置算法中每一步的执行结果。

命题意图：考查快速转置算法的完整执行过程。

审题分析：

• 已知：$4 \times 5$ 矩阵，6个非零元素
• 求解：快速转置的三步执行过程

解题思路： 按快速转置算法的三步逐一执行。

完整步骤：

第一步：统计每列非零元素个数

原矩阵5列，统计每列非零元素数：

• col=1：1个（$a_{31}$）
• col=2：2个（$a_{12}, a_{42}$）
• col=3：1个（$a_{23}$）
• col=4：2个（$a_{14}, a_{34}$）
• col=5：0个

$\text{count} = [0, 1, 2, 1, 2, 0]$（下标0不用）

第二步：计算每列在转置矩阵T中的起始位置

$\text{position}[1] = 0$$\text{position}[2] = 0 + 1 = 1$$\text{position}[3] = 1 + 2 = 3$$\text{position}[4] = 3 + 1 = 4$$\text{position}[5] = 4 + 2 = 6$

第三步：按列序依次放入T

遍历M的三元组：

原元素	列号	放入T的位置	更新后position
(1,2,3)	2	T[1]=(2,1,3)	position[2]=2
(1,4,5)	4	T[4]=(4,1,5)	position[4]=5
(2,3,2)	3	T[3]=(3,2,2)	position[3]=4
(3,1,7)	1	T[0]=(1,3,7)	position[1]=1
(3,4,1)	4	T[5]=(4,3,1)	position[4]=6
(4,2,6)	2	T[2]=(2,4,6)	position[2]=3

转置后的三元组表T（$5 \times 4$ 矩阵）：

下标	row	col	value
0	1	3	7
1	2	1	3
2	2	4	6
3	3	2	2
4	4	1	5
5	4	3	1

验证：T中元素按行优先排列 ✓，且每个元素的行列号与M中对应元素互换 ✓

方法反思：

• 快速转置的核心是预计算位置，避免了逐个查找的低效
• 理解"position数组"的作用是关键：它记录了每一列（转置后的每一行）下一个元素应存放的位置
• 时间复杂度 $O(n + \text{num})$，其中关键是"计数→定位→搬家"三步

---

五、考情分析

分析维度	内容
考查频次	对称矩阵下标映射近5年出现3次以上，稀疏矩阵三元组表出现2次以上
常见题型	选择题（下标计算、存储量计算、快速转置过程）
分值占比	选择题2分，偶尔作为大题的一部分
命题趋势	对称矩阵下标公式是最稳定的考点，稀疏矩阵快速转置也常作为选择题考查，趋势是与线性代数知识结合

注：以上频次基于大纲权重与通用命题规律推测，待真题分析后校准。

---

六、易错点提醒

易错点1

• 错误表现：对称矩阵下标公式中忘记减1（下标从0开始和从1开始的转换）
• 错误原因：公式推导时"元素序号"和"数组下标"混淆
• 正确做法：牢记公式 $k = \frac{i(i-1)}{2} + j - 1$ 中的 "-1" 是因为一维数组下标从0开始。如果题目说"B的下标从1开始"，则公式变为 $k = \frac{i(i-1)}{2} + j$

易错点2

• 错误表现：上三角矩阵的下标公式记忆错误
• 错误原因：上三角按行优先存储时，每行元素个数递减，推导比下三角复杂
• 正确做法：上三角记住"第 $i$ 行有 $(n-i+1)$ 个元素"，前 $(i-1)$ 行共有 $\sum_{t=1}^{i-1}(n-t+1) = (i-1)(2n-i+2)/2$ 个元素

易错点3

• 错误表现：稀疏矩阵三元组表中行号列号的起始值搞错（从0还是从1）
• 错误原因：不同教材对三元组行列号的约定不同
• 正确做法：408考试中通常从1开始，审题时确认

易错点4

• 错误表现：快速转置中 position 数组的初始化错误
• 错误原因：position[1] 应该从0开始（第一个元素在数组下标0处），但有时误初始化为1
• 正确做法：position[1]=0，然后依次累加。遍历完成后 position 数组的值会自动指向各列下一个可用位置

---

七、来源标注

• 依据2026考研统考大纲（408计算机学科专业基础综合）
• 依据《数据结构（C语言版）》严蔚敏版
• 依据《数据结构》王道考研辅导讲义

---