特殊矩阵的压缩存储

前置：多维数组的存储。本篇所有压缩公式都建立在那里的"行优先 / 列优先地址公式"地基上——压缩存储的本质就是"砍掉冗余位置"后重新数地址。

一、为什么要压缩

对于 $n\times n$ 的矩阵，朴素存储要 $n^2$ 个单元。当矩阵具有某种规律性（很多元素是 0、很多元素重复对称）时，朴素存储是浪费的：

• $1000\times 1000$ 对称矩阵：朴素要 ${10}^6$ 个单元，但有用信息只有上三角 $\approx 5\times {10}^5$ 个——浪费一半
• $1000\times 1000$ 三对角矩阵：朴素要 ${10}^6$ 个单元，但非零的只有 $\approx 3\times {10}^3$ 个——浪费 99.7%
• $1000\times 1000$ 稀疏矩阵（非零元素 100 个）：朴素要 ${10}^6$ 个单元，浪费 99.99%

压缩存储的目标：只保留有用信息，并能 $O(1)$ 反算出原矩阵任一位置的值。

四类特殊矩阵的压缩思路：

矩阵	规律	压缩思路
对称矩阵	$m_{i,j}=m_{j,i}$	只存一半三角
三角矩阵	一半三角全是常数 $c$（或 0）	存非零三角 + 1 个 $c$
三对角矩阵	非零只在 $|i-j|\le 1$ 的带上	只存三条带
稀疏矩阵	非零元素稀疏分布、无规律	存 (行, 列, 值) 三元组

前三类是规律性压缩（位置可由 $i,j$ 算出），第四类是显式存位置（用三元组）。

二、对称矩阵

2.1 定义

$n\times n$ 矩阵 $M$ 满足 $m_{i,j}=m_{j,i}$（对所有 $1\le i,j\le n$）。 对角线两侧的元素互为镜像，对角线上的元素自身镜像就是自己。

2.2 存储策略

只存上三角（包含对角线，$j\ge i$ 的部分），或者只存下三角（$i\ge j$ 的部分）。两种策略都要存 $\frac{n(n+1)}{2}$ 个元素。

下面以"只存上三角"为例（408 考研最常考的形态），分别推导行优先和列优先的下标公式。

2.3 上三角 · 行优先公式（1-based）

第 $i$ 行存哪些元素？$m_{i,i},m_{i,i+1},\dots ,m_{i,n}$，共 $n-i+1$ 个：

i=1 : m11 m12 m13 ... m1n        (n 个)
i=2 :     m22 m23 ... m2n        (n-1 个)
i=3 :         m33 ... m3n        (n-2 个)
...
i=n :                     mnn    (1 个)

$m_{i,j}$ ($j\ge i$) 的下标推导：

• 前 $i-1$ 行共有 $n+(n-1)+\cdots +(n-i+2)=\frac{(i-1)(2n-i+2)}{2}$ 个元素
• 第 $i$ 行内 $m_{i,j}$ 之前还有 $j-i$ 个元素

0-based 下标（一维数组从 $N[0]$ 起）：

$$\boxed{{\displaystyle \text{idx}(m_{i,j})=\frac{(i-1)(2n-i+2)}{2}+(j-i)}}$$

2.4 真题精讲：2018-03（上三角行优先）

设有一个 $12\times 12$ 的对称矩阵 $M$，将其上三角部分的元素 $m_{i,j}(1\le i\le j\le 12)$ 按行优先存入 C 语言的一维数组 $N$ 中，元素 $m_{6,6}$ 在 $N$ 中的下标是？

第一步：$m_{6,6}$ 满足 $j\ge i$，已经在上三角，无需对称变换。

第二步：代入公式 $n=12,i=6,j=6$：

$$\text{idx}=\frac{5\times (24-6+2)}{2}+(6-6)=\frac{5\times 20}{2}+0=50$$

手算验证：前 5 行的元素数 $12+11+10+9+8=50$，第 6 行的第一个元素就是 $m_{6,6}$，所以它是数组中的第 51 个元素——但 0-based 下标是 50。答案 50。

2.5 上三角 · 列优先公式（1-based）

把行/列角色对调。第 $j$ 列存哪些元素？$m_{1,j},m_{2,j},\dots ,m_{j,j}$，共 $j$ 个：

j=1 : m11                              (1 个)
j=2 : m12 m22                          (2 个)
j=3 : m13 m23 m33                      (3 个)
...
j=n : m1n m2n m3n ... mnn              (n 个)

注意写法上：第 $j$ 列里的元素是按行号 $1,2,\dots ,j$ 顺序排的，但它们的"行下标"出现在第一位、"列下标 $j$" 出现在第二位。

$m_{i,j}$ ($i\le j$) 的下标推导：

• 前 $j-1$ 列共有 $1+2+\cdots +(j-1)=\frac{j(j-1)}{2}$ 个元素
• 第 $j$ 列内 $m_{i,j}$ 之前还有 $i-1$ 个元素

0-based 下标：

$$\boxed{{\displaystyle \text{idx}(m_{i,j})=\frac{j(j-1)}{2}+(i-1)}}$$

2.6 真题精讲：2020-01（上三角列优先 + 对称性）

将一个 $10\times 10$ 对称矩阵 $M$ 的上三角部分的元素 $m_{i,j}$（$1\le i\le j\le 10$），按列优先存入 C 语言的一维数组 $N$ 中，元素 $m_{7,2}$ 在 $N$ 中的下标是？

第一步：用对称性把元素挪到上三角。

题目说"只存 $i\le j$ 的部分"。而 $m_{7,2}$ 的行号 $7>$ 列号 $2$，落在下三角，没有被直接存储。利用 $m_{i,j}=m_{j,i}$：

$$m_{7,2}=m_{2,7}$$

实际查 $m_{2,7}$（$i=2,j=7$）的下标。

第二步：代入列优先公式 $n=10,i=2,j=7$：

$$\text{idx}=\frac{7\times 6}{2}+(2-1)=21+1=22$$

答案 22。

编者注（对称矩阵下三角元素的查询模板）：题目"只存了上三角"+ 你要查的元素在下三角时，三步走：① 用 $m_{i,j}=m_{j,i}$ 交换下标；② 重新核对交换后是否进入上三角（$j\ge i$）；③ 代入公式。漏掉第一步是 2020-01 选错最常见的原因。

2.7 行优先 vs 列优先：什么时候用哪个公式

题面会明确写出"按行优先" / "按列优先"。两种公式的关键区别：

	行优先	列优先
第 $k$ 行/列长度	$n-k+1$（递减）	$k$（递增）
"前部"求和	$\frac{(i-1)(2n-i+2)}{2}$	$\frac{j(j-1)}{2}$
行内偏移	$j-i$	$i-1$

编者注（对称记忆）：行优先和列优先看似"两套公式"，本质是一回事——同一个三角形按两种顺序遍历的不同计数方式。考场上不要硬背两个公式——理解了"前 $k-1$ 行/列总长 + 当前行/列偏移"的拆分逻辑，公式现场推就行。

三、三角矩阵

3.1 定义

上三角矩阵：所有 $i>j$（下三角部分）的元素都等于同一个常数 $c$（多半是 0）。

* * * *
0 * * *      ← 下三角全是常数 c（这里 c=0）
0 0 * *
0 0 0 *

下三角矩阵：所有 $i<j$（上三角部分）的元素都等于同一个常数 $c$。

3.2 压缩策略

• 存所有 $j\ge i$ 的元素（上三角的非常数部分），共 $\frac{n(n+1)}{2}$ 个
• 再额外存 1 个常数 $c$

总空间：$\frac{n(n+1)}{2}+1$。

3.3 下标公式

上三角矩阵：非常数部分（$j\ge i$）按行优先存 0-based 下标——与对称矩阵 2.3 节公式相同：

$$\text{idx}(m_{i,j})=\frac{(i-1)(2n-i+2)}{2}+(j-i),j\ge i$$

常数 $c$ 单独存在末尾位置 $N\left[\frac{n(n+1)}{2}\right]$。

下三角矩阵：非常数部分（$i\ge j$）按行优先存。第 $i$ 行有 $i$ 个元素，所以前 $i-1$ 行共 $1+2+\cdots +(i-1)=\frac{i(i-1)}{2}$ 个。

$$\text{idx}(m_{i,j})=\frac{i(i-1)}{2}+(j-1),j\le i$$

编者注（三角矩阵 vs 对称矩阵）：两个考点常常被混淆。对称矩阵存"一半三角"是因为另一半重复，两半内容相同；三角矩阵存"一半三角"是因为另一半全是常数，两半内容不同（一半有值、另一半是 $c$）。考试题里有时会刻意省略这个区分，需要从题面"对称 / 三角 / 主对角线"几个关键词判定。

四、三对角矩阵

4.1 定义

只有满足 $|i-j|\le 1$ 的元素非零，即主对角线 + 上副对角线 + 下副对角线三条带：

n=5 时的非零分布：
* *
* * *
  * * *
    * * *
      * *

4.2 每行非零元素数

• 第 $1$ 行：$m_{1,1},m_{1,2}$ —— 2 个
• 第 $2\sim n-1$ 行：$m_{i,i-1},m_{i,i},m_{i,i+1}$ —— 3 个
• 第 $n$ 行：$m_{n,n-1},m_{n,n}$ —— 2 个

总非零数：$2+3(n-2)+2=3n-2$。

4.3 行优先下标公式（1-based）

设 $2\le i\le n-1$。第 $i$ 行之前共存：

$$\underset{\text{第 1 行}}{\underbrace{2}}+\underset{\text{第 2 至 }i-1\text{ 行}}{\underbrace{3\times (i-2)}}=3i-4$$

第 $i$ 行内三个元素的行内位置（从 0 编号）是 0、1、2，对应 $j=i-1,i,i+1$。所以行内偏移 $=j-i+1$。

0-based 下标（$2\le i\le n-1$，$|i-j|\le 1$）：

$$\boxed{{\displaystyle \text{idx}(m_{i,j})=(3i-4)+(j-i+1)=2i+j-3}}$$

边界行（$i=1$ 或 $i=n$）的下标需要单独算，不要套这个公式。

4.4 真题精讲：2016-04

有一个 100 阶的三对角矩阵 $M$，其元素 $m_{i,j}(1\le i\le 100,1\le j\le 100)$ 按行优先依次压缩存入下标从 0 开始的一维数组 $N$ 中。元素 $m_{30,30}$ 在数组 $N$ 中的下标是？

代入 $i=j=30$（属于 $2\le i\le 99$ 的常规行）：

$$\text{idx}=2\times 30+30-3=87$$

手算验证：第 30 行之前共有 $2+3\times 28=86$ 个元素（占 $N[0]$ 到 $N[85]$）。第 30 行三个元素 $m_{30,29},m_{30,30},m_{30,31}$ 依次占 $N[86],N[87],N[88]$。$m_{30,30}$ 在 $N[87]$。

答案 87。

4.5 三对角矩阵的三个高频坑

1. 第 1 行只有 2 个元素——把所有行都按 3 个算，前缀和会算错（$3\times 29=87$ vs 正确的 $86$）
2. "主对角线 $i=j$" vs "上副对角线 $i=j-1$" 混淆——$m_{30,30}$ 在第 30 行的中间（位置 1），不是第一个（位置 0）
3. 公式 $2i+j-3$ 只对中间行成立——$i=1$ 或 $i=n$ 时单独处理

五、稀疏矩阵

5.1 定义

非零元素个数 $t$ 远小于矩阵总元素数 $m\times n$，且非零元素分布无规律（不像三角、三对角那样有几何规律）。

没有正式的"稀疏度阈值"——一般认为 $t/(m\cdot n)<0.05$ 就算稀疏，但 408 考研里只要题面说"稀疏矩阵"就按稀疏处理，不必纠结临界值。

5.2 三元组表

最简单的稀疏存储：对每个非零元素 $m_{i,j}\ne 0$，存一个三元组 $(i,j,m_{i,j})$。所有三元组连续存放在一个数组里。

辅助信息：

typedef struct {
    int rows;       // M 的行数
    int cols;       // M 的列数
    int nums;       // 非零元素个数
    Triple data[N]; // 三元组数组
} TSMatrix;

5.3 真题精讲：2023-03（三元组必须存什么）

若采用三元组表存储结构存储稀疏矩阵 M，则除三元组外，下列数据中还需要保存的是？

I. M 的行数   II. M 中包含非零元素的行数   III. M 的列数   IV. M 中包含非零元素的列数

正确答案 I 和 III——存矩阵的原始行数和列数。

为什么 II 和 IV 不行？

反例：考虑一个 $5\times 5$ 矩阵只有 $m_{1,1}=1$ 一个非零元素：

1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

• 三元组：$\{(1,1,1)\}$
• 非零行数 II = 1，非零列数 IV = 1
• 如果只存 II + IV，重建出来的矩阵是 $1\times 1$，原矩阵的 4 行 4 列零元素信息全部丢失

所以必须存"原始行列数"（I + III），而不是"非零行列数"（II + IV）。

编者注（三元组的设计原则）：辅助信息要做到 ① 能完整恢复原矩阵形状；② 能完整恢复非零元素。三元组本身负责非零元素，行列数负责形状——两者合起来无冗余、无缺失。多存（D 选项）增加冗余，少存或换错存（B/C 选项）信息不够。

5.4 真题精讲：2017-03（稀疏矩阵的存储结构辨析）

适用于压缩存储稀疏矩阵的两种存储结构是？

A. 三元组表和十字链表   B. 三元组表和邻接矩阵   C. 十字链表和二叉链表   D. 邻接矩阵和十字链表

正确答案 A。

关键辨析：

结构	是否压缩稀疏矩阵	真实用途
三元组表	✓	稀疏矩阵专用
十字链表	✓	稀疏矩阵专用（行/列双向遍历）
邻接矩阵	✗	图的稠密存储，$n\times n$ 全存，0 也占位置
二叉链表	✗	二叉树节点的 lchild / rchild 链接结构

编者注（邻接矩阵的命名陷阱）：邻接矩阵的"矩阵"二字容易让人以为它"和稀疏矩阵相关"。实际上它就是一个普通的 $n\times n$ 二维数组（行列下标对应顶点编号，元素表示边权或邻接关系），完全不压缩，0 元素照常占内存。它自己是稀疏矩阵存储要解决的问题之一——稀疏图的邻接矩阵用三元组或十字链表压缩才高效。

5.5 十字链表

适合频繁修改的稀疏矩阵（增删非零元素）。每个非零元素是一个节点：

typedef struct OLNode {
    int row, col;            // 行、列号
    ElemType value;          // 元素值
    struct OLNode *right;    // 同一行内下一个非零元素
    struct OLNode *down;     // 同一列内下一个非零元素
} OLNode;

每个节点同时挂在所在行链表和列链表两个链表上——所以叫"十字"。一个 $m\times n$ 稀疏矩阵有 $m$ 个行头指针 + $n$ 个列头指针。

优势：

• 行方向遍历某行所有非零元素：沿 right 走一遍，$O(\text{该行非零数})$
• 列方向遍历某列所有非零元素：沿 down 走一遍，$O(\text{该列非零数})$
• 插入新非零元素：找到行链表和列链表中的位置后插入，$O(\text{行长}+\text{列长})$，不需要移动其它元素

劣势：每个节点带 4 个域（2 个指针 + 行号 + 列号 + 值），单元素开销比三元组大。

5.6 三元组 vs 十字链表

	三元组表	十字链表
存储开销（单个非零元素）	小（$i,j,value$ 3 个值）	大（再多 2 个指针）
插入 / 删除	慢（数组要移位）	快（链表 $O(\text{行长}+\text{列长})$）
矩阵加法 / 转置	中等	较慢但代码清晰
适用场景	静态稀疏矩阵	频繁修改

408 选择题里两者各有出现，但三元组表的出题频率明显更高。十字链表在题里多半作为"另一个正确选项"出现（如 2017-03）。

六、四类矩阵对比速查表

矩阵	非零分布	压缩后大小	关键公式（0-based 行优先）
对称矩阵（上三角）	$j\ge i$	$\frac{n(n+1)}{2}$	$\frac{(i-1)(2n-i+2)}{2}+(j-i)$
对称矩阵（上三角，列优先）	$j\ge i$	$\frac{n(n+1)}{2}$	$\frac{j(j-1)}{2}+(i-1)$
三角矩阵	一半 + 1 个常数	$\frac{n(n+1)}{2}+1$	同对称矩阵的对应三角
三对角矩阵	$|i-j|\le 1$	$3n-2$	$2i+j-3$（中间行）
稀疏矩阵（三元组）	任意稀疏	$3t+3$（$t$ 个非零）	显式存 $(i,j,v)$，无下标公式
稀疏矩阵（十字链表）	任意稀疏	$\approx 5t+m+n$	链表节点，无下标公式

七、交互可视化：四种矩阵综合演练

打开下方可视化：顶部切换「对称 / 三角 / 三对角 / 稀疏」四种矩阵，点击网格任意元素查看下标推导。带「真题预设」按钮一键加载 2018-03 / 2020-01 / 2016-04 / 2023-03 四道题的初始配置，直接看 ds-visual 跑出正确答案的过程。

加载可视化中...

八、考点速记（考前 30 秒过）

1. 对称矩阵：用对称性 $m_{i,j}=m_{j,i}$ 把元素挪到被存的三角；推公式的两件套是"前几行/列累加 + 行/列内偏移"
2. 三角矩阵：和对称矩阵的下标公式完全一样，只是末尾多存 1 个常数 $c$
3. 三对角矩阵：中间行公式 $2i+j-3$，第 1 行只有 2 个元素是边界陷阱
4. 稀疏矩阵三元组：除了三元组本身，还要存"原矩阵的行数和列数"（不是非零行列数）
5. 邻接矩阵不是稀疏矩阵的压缩结构——它是图的稠密存储，看到"矩阵"二字别误判
6. base 看清：题面 1-based 和 C 数组 0-based 的转换在最后一步做

九、本章真题清单

codebrick 题库中考查 matrix-storage 或 special-matrix 知识点的真题：

年份	题号	考点	难度
2016	04	三对角矩阵 + 行优先下标	★★★
2017	03	稀疏矩阵存储结构辨析（三元组 vs 邻接矩阵）	★★
2018	03	对称矩阵 + 上三角行优先下标	★★★
2020	01	对称矩阵 + 上三角列优先 + 对称性	★★★
2021	03	二维数组 + 行优先地址 + 反推 n	★★
2023	03	稀疏矩阵三元组 + 必存辅助信息	★★

近 10 年 6 次出现，平均 1.7 年 / 次。最近一次 2023 年，2024 和 2025 未考——按命题轨迹规律是中频考点的标准沉寂期，2026 备考需要重点掌握。

编者注（学完之后该做什么）：这一章公式多、易错点密。建议做法：① 把对称矩阵两个公式（行/列优先）至少各推导一遍，不要硬背；② 把上面 6 道真题在 codebrick 题库 (/practice/browse/ds) 顺序刷一遍，每道题做完看错因；③ 三对角矩阵和三角矩阵的下标公式可以放在最后，因为它们和对称矩阵共享同一套推导思路。