特殊矩阵的压缩存储

2026 大纲 三（五）特殊矩阵的压缩存储（地址公式的地基见《多维数组的存储》）。

四类矩阵、八个公式，推法只有一条

一个 $n\times n$ 的矩阵直接存要 $n^2$ 个单元。但如果它有大量重复或恒为常数的元素，这些空间就白花了——压缩存储的目标是只保留有用信息，同时仍能在 $O(1)$ 时间内反算出任一位置的值。后半句同样要紧：如果查一个元素要遍历，压缩就失去意义了。

公式看着有八个，推法其实只有一条：前 $k-1$ 行（列）累加 $+$ 行（列）内偏移。这与《多维数组的存储》那条完全一样，唯一的差别是——"每一行有几个元素"不再是常数 $n$ 了。三角形的行，长度是逐行递减（或递增）的，所以"前 $k-1$ 行的总数"从乘法变成了求和。

矩阵	存哪一半 / 哪些位置	压缩后大小	关键公式（矩阵 1-based，数组 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)$
下三角（行优先）	$i\ge j$	$\frac{n(n+1)}{2}$（三角矩阵再 $+1$）	$\frac{i(i-1)}{2}+(j-1)$
三角矩阵	一半三角 $+$ 1 个常数 $c$	$\frac{n(n+1)}{2}+1$	同对应三角；常数区全部映射到末位 $\frac{n(n+1)}{2}$
三对角矩阵	$|i-j|\le 1$	$3n-2$	$2i+j-3$（含边界行，全体适用）
稀疏矩阵（三元组）	任意稀疏、无规律	$3t+3$（$t$ 个非零）	显式存 $(i,j,v)$，无下标公式
稀疏矩阵（十字链表）	任意稀疏	$\approx 5t+m+n$	链表结点，无下标公式

🔴 查任一元素的三步	① 判断它在不在被存的那个三角；② 不在就先按对称性交换下标；③ 再代公式。跳过前两步直接代，是这一节最容易犯的错
🔴 对称 vs 三角的唯一实质差别	对称：另一半内容重复，查它要交换下标；三角：另一半全是常数 $c$，查它返回末位那一格。区分就看题面说"对称"还是"其余元素均为常数/0"
🔴 三对角公式对边界行也成立	第 1 行的"前缀少 1、行内多 1"正好抵消，不必单独处理
前三类 vs 稀疏矩阵	前三类位置能由 $i,j$ 算出（规律性压缩）；稀疏矩阵无规律，只能把位置显式存下来
压缩的目标	只保留有用信息，同时仍能在 $O(1)$ 时间内反算出任一位置的值。后半句同样重要——查一个元素要遍历，压缩就没意义了
🔴 压缩不是无条件更优	三元组要 $3t+3$ 个单元，非零占比低于约 $1/3$ 才开始省空间；一半元素非零时反而多花约 50%
🔴 邻接矩阵不是压缩结构	它是图的稠密存储，$n\times n$ 一格不省。看到"矩阵"二字就往压缩存储上套是选择题的常见错法

查任一元素，固定三步：① 判断它在不在被存的那个三角；② 不在就先按对称性交换下标；③ 再代公式。跳过前两步直接代公式，是这一节最容易犯的错。

第 ② 步怎么处理，取决于矩阵的类型——对称矩阵与三角矩阵的唯一实质差别就在这里：

• 对称矩阵：另一半的内容是重复的，所以查它要交换下标再代同一个公式；
• 三角矩阵：另一半全是常数 $c$，所以查它直接返回末位那一格，根本不用算。

区分就看题面写的是"对称"，还是"其余元素均为常数 / 均为 0"。

全文约定：矩阵元素下标从 1 开始（$m_{i,j}$），压缩数组下标从 0 开始（C 语言习惯）。 题面若是其他组合，先按本文的约定算出结果，最后一步再 $\pm 1$ 转换，不要临场改公式—— 临场改公式是这一节的主要出错来源。两个 base 互相独立，不要混成一个。

交互可视化

顶部切换「对称 / 三角 / 三对角 / 稀疏」，点击网格任意元素查看下标推导； 也可直接输入 $n$、$i$、$j$ 观察前缀累加与行内偏移各占多少。

加载可视化中...

对称矩阵：两个公式的完整推导与手算验证（想会推不想背就展开）

$n\times n$ 矩阵 $M$ 满足 $m_{i,j}=m_{j,i}$。对角线两侧互为镜像，对角线上的元素自身镜像就是自己。 只存上三角（含对角线，$j\ge i$）或只存下三角（$i\ge j$），两种策略都要存 $1+2+\cdots +n=\frac{n(n+1)}{2}$ 个元素，压缩数组记作 $N[0\dots \frac{n(n+1)}{2}-1]$。

上三角 · 行优先。 第 $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 个)

• 前 $i-1$ 行的元素总数：$n+(n-1)+\cdots +(n-i+2)$。 这是首项 $n$、末项 $n-i+2$、共 $i-1$ 项的等差数列，和为

  $$\frac{(i-1)[n+(n-i+2)]}{2}=\frac{(i-1)(2n-i+2)}{2}$$

• 第 $i$ 行内 $m_{i,j}$ 之前：从 $m_{i,i}$ 数到 $m_{i,j-1}$，共 $j-i$ 个。

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

一次演算：$12\times 12$ 对称矩阵，上三角按行优先存入下标从 0 开始的一维数组，求 $m_{6,6}$ 的下标。 $6\ge 6$，已在上三角，无需交换；代入 $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$ 个元素，占 $N[0]\sim N[49]$； 第 6 行的第一个元素正是 $m_{6,6}$，落在 $N[50]$——它是数组中的第 51 个元素， 0-based 下标为 50 ✓。

上三角 · 列优先。 第 $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$ 列的元素总数：$1+2+\cdots +(j-1)={\displaystyle \frac{j(j-1)}{2}}$；
• 第 $j$ 列内 $m_{i,j}$ 之前：从 $m_{1,j}$ 数到 $m_{i-1,j}$，共 $i-1$ 个。

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

一次演算：$10\times 10$ 对称矩阵，上三角按列优先存入下标从 0 开始的一维数组，求 $m_{7,2}$ 的下标。 第一步（关键）：只存 $i\le j$ 的部分，而 $m_{7,2}$ 的行号 $7>$ 列号 $2$， 落在下三角，没有被直接存储，用对称性交换：$m_{7,2}=m_{2,7}$；确认 $2\le 7$ ✓； 代入 $n=10,i=2,j=7$：

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

手算验证：前 6 列共 $1+2+3+4+5+6=21$ 个元素，占 $N[0]\sim N[20]$； 第 7 列依次是 $m_{1,7},m_{2,7},\dots$，分别落在 $N[21],N[22],\dots$， 所以 $m_{2,7}$ 在 $N[22]$ ✓。

漏掉第一步（下标交换）是这类题的典型错法。自查动作：代入公式前， 先把 $i$ 和 $j$ 比一次大小，确认它满足被存三角的条件。

行优先与列优先的对照（题面会明确写出用哪种）：

	行优先（存上三角）	列优先（存上三角）
第 $k$ 行/列的长度	$n-k+1$（递减）	$k$（递增）
前 $k-1$ 行/列总长	$\frac{(i-1)(2n-i+2)}{2}$	$\frac{j(j-1)}{2}$
行内/列内偏移	$j-i$	$i-1$

不必机械记忆两套公式——理解"前 $k-1$ 行（列）总长 $+$ 当前行（列）内偏移"的拆分逻辑， 现场推一遍不到一分钟，而且不会记混。

三角矩阵：公式、常数位，以及与对称矩阵的并排对照（想彻底分清两者就展开）

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

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

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

压缩策略：存所有非常数部分的元素共 ${\displaystyle \frac{n(n+1)}{2}}$ 个，再额外存 1 个常数 $c$ 放在数组末尾， 总空间 ${\displaystyle \frac{n(n+1)}{2}}+1$。

上三角矩阵（非常数部分是 $j\ge i$，按行优先）——与对称矩阵上三角行优先完全相同：

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

常数 $c$ 单独存在末尾位置 $N\left[{\displaystyle \frac{n(n+1)}{2}}\right]$， 即所有 $i>j$ 的元素都映射到这一个下标。

下三角矩阵（非常数部分是 $i\ge j$，按行优先）：第 $i$ 行有 $i$ 个元素（$m_{i,1}\dots m_{i,i}$）， 前 $i-1$ 行共 $1+2+\cdots +(i-1)={\displaystyle \frac{i(i-1)}{2}}$ 个，行内偏移共 $j-1$ 个，故

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

这也是严蔚敏教材给出的经典形式（式 4-14 的下三角情形）。

下三角 · 列优先（对偶推法，供对照）：第 $j$ 列有 $n-j+1$ 个元素， 前 $j-1$ 列共 ${\displaystyle \frac{(j-1)(2n-j+2)}{2}}$ 个，列内偏移 $i-j$，故 $\text{idx}={\displaystyle \frac{(j-1)(2n-j+2)}{2}}+(i-j)$—— 与"上三角行优先"互为对偶，再次说明四个公式只是同一推法的四种代入。

并排对照：同样是 $n=8$、同样问 $m_{2,7}$、同样存下三角按行优先。

三角矩阵（上三角元素全为常数 $c$）：$7>2$，$m_{2,7}$ 落在上三角——那里全是常数 $c$， 不单独存，统一指向数组末尾那一格：$\text{idx}={\displaystyle \frac{n(n+1)}{2}}={\displaystyle \frac{8\times 9}{2}}=36$。 数组总长度 $36+1=37$，其中 $N[0]\sim N[35]$ 存下三角的 36 个元素，$N[36]$ 存常数 $c$ ✓。 另外 $m_{5,3}$：$3\le 5$ 在被存区域，$\text{idx}=\frac{5\times 4}{2}+(3-1)=12$； 验证前 4 行共 $1+2+3+4=10$ 个占 $N[0]\sim N[9]$，第 5 行依次占 $N[10]\sim N[14]$， $m_{5,3}$ 在 $N[12]$ ✓。

对称矩阵：$7>2$，$m_{2,7}$ 在上三角没有被存储，用对称性交换 → $m_{2,7}=m_{7,2}$， 确认 $2\le 7$ ✓，代入下三角行优先公式 $\text{idx}={\displaystyle \frac{7\times 6}{2}}+(2-1)=22$。

对称矩阵答案是 22，三角矩阵答案是 36。区别只在于"另一半是重复内容还是常数"。 三角矩阵的 $m_{2,7}$ 与 $m_{7,2}$ 并不相等（前者是常数 $c$，后者是有效数据）， 对它交换下标会得到完全错误的答案。审题时必须先确定矩阵类型，再决定是交换下标还是指向常数位。

三对角矩阵：一个公式管到底

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

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图4.3 三对角矩阵，p140

每行的非零元素数：第 $1$ 行是 $m_{1,1},m_{1,2}$ 共 2 个（$m_{1,0}$ 不存在）； 第 $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$。

行优先下标公式。 先看中间行（$2\le i\le n-1$）。第 $i$ 行之前一共存了：

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

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

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

这个公式对第 1 行和第 $n$ 行同样成立，不需要单独处理——理由值得说清楚：

• 第 1 行：3i-4 代入 $i=1$ 得 $-1$，比真实值 0 少 1；而行内偏移 $j-i+1=j$， 比真实的 $j-1$ 多 1。两处偏差正好抵消，结果仍然正确。 验证：$m_{1,1}\to 2+1-3=0$ ✓，$m_{1,2}\to 2+2-3=1$ ✓。
• 第 $n$ 行：3i-4 代入 $i=n$ 得 $3n-4$，正是前 $n-1$ 行的真实总数 $2+3(n-2)=3n-4$ ✓；行内偏移 $j-i+1$ 对 $j=n-1,n$ 分别给出 0、1 ✓，与实际一致。 验证（$n=5$）：$m_{5,4}\to 10+4-3=11$，$m_{5,5}\to 10+5-3=12$， 而总数 $3\times 5-2=13$，下标范围 $0\sim 12$ ✓。

$n=5$ 的完整对照表（可用来复核任何记忆）：

$k$	0	1	2	3	4	5	6	7	8	9	10	11	12
$m_{i,j}$	1,1	1,2	2,1	2,2	2,3	3,2	3,3	3,4	4,3	4,4	4,5	5,4	5,5

逐个代入 $2i+j-3$ 核对，13 个全部吻合。

逆映射：已知 $k$ 求 $(i,j)$。 由 $k=2i+j-3$ 且 $j\in \{i-1,i,i+1\}$ 得 $k\in \{3i-4,3i-3,3i-2\}$，于是 $k+1\in \{3i-3,3i-2,3i-1\}$， 因此 $\lfloor {\displaystyle \frac{k+1}{3}}\rfloor =i-1$。故

$$i=\lfloor \frac{k+1}{3}\rfloor +1,j=k-2i+3$$

验证：$k=87\Rightarrow i=\lfloor 88/3\rfloor +1=29+1=30$， $j=87-60+3=30$，即 $m_{30,30}$； $k=5\Rightarrow i=\lfloor 6/3\rfloor +1=3$，$j=5-6+3=2$，即 $m_{3,2}$ ✓（对照上表）。 记成不带 $+1$ 的版本是常见错法，用 $k=0\to m_{1,1}$ 代一次即可自查。

一次正向演算：100 阶三对角矩阵，$m_{i,j}(1\le i,j\le 100)$ 按行优先压缩存入下标从 0 开始 的一维数组 $N$，$m_{30,30}$ 的下标 $=2\times 30+30-3=87$。 手算验证：第 30 行之前共有 $2+3\times 28=86$ 个元素，占 $N[0]\sim N[85]$； 第 30 行的三个元素 $m_{30,29},m_{30,30},m_{30,31}$ 依次占 $N[86],N[87],N[88]$ ✓。

两个容易算错的地方：① 第 1 行只有 2 个元素，若把所有行都按 3 个算， 前缀和会得到 $3\times 29=87$ 而不是正确的 86，最终答案偏移 1； ② 别把"主对角线 $i=j$"当成行内的第一个——$m_{30,30}$ 在第 30 行的中间（行内位置 1）， 第一个是 $m_{30,29}$。行内偏移 $j-i+1$ 里的那个 $+1$ 就是为此而来。

稀疏矩阵：三元组表、十字链表，以及"什么时候才划算"（要写结构定义或做选型时展开）

非零元素个数 $t$ 远小于 $m\times n$，且非零元素分布无规律。 没有正式的稀疏度阈值——一般认为 $t/(m\cdot n)<0.05$ 就算稀疏， 但题面只要说"稀疏矩阵"就按稀疏处理，不必纠结临界值。

严蔚敏教材在讲完对称、三角、对角三种特殊矩阵后指出： "在实际应用中还经常会遇到另一类矩阵，其非零元较零元少，且分布没有一定规律，称之为稀疏矩阵。 这类矩阵的压缩存储就要比特殊矩阵复杂。"——"无规律"正是它与前三类的分界线。

三元组表：对每个非零元素 $m_{i,j}\ne 0$ 存一个三元组 $(i,j,m_{i,j})$， 所有三元组连续存放，通常按行优先顺序排列。

typedef struct {
    int i, j;        // 非零元素的行号、列号
    int value;       // 元素值
} Triple;

typedef struct {
    int rows;        // 原矩阵 M 的行数
    int cols;        // 原矩阵 M 的列数
    int nums;        // 非零元素个数
    Triple data[MAXSIZE];
} TSMatrix;

辅助信息为什么必须是"原矩阵的行数和列数"，而不是"包含非零元素的行数/列数"？ 用反例：一个 $5\times 5$ 矩阵只有 $m_{1,1}=1$ 一个非零元素，三元组只有 $(1,1,1)$， 非零行数 $=1$、非零列数 $=1$；若只存这两个数，重建出来的是一个 $1\times 1$ 矩阵， 原矩阵那 4 行 4 列的零元素信息全部丢失——形状错了。

三元组的设计原则：辅助信息要做到两件事——① 能完整恢复原矩阵的形状； ② 能完整恢复所有非零元素。三元组负责第二件，行数与列数负责第一件， 两者合起来无冗余、无缺失。

什么时候才划算：三元组把"1 个值"换成了"3 个值"。设每个整数占 1 个单元， 朴素存储 $m\cdot n$ 个单元，三元组表 $3t+3$ 个单元（3 个辅助量），划算的条件是

$$3t+3<m\cdot n⟺t<\frac{m\cdot n-3}{3}\approx \frac{m\cdot n}{3}$$

非零个数 $t$（$100\times 100$ 矩阵，朴素 10 000 单元）	三元组 $3t+3$	是否划算
100（占 1%）	303	划算，省 97%
1 000（占 10%）	3 003	划算，省 70%
3 333（占 33%）	10 002	持平
5 000（占 50%）	15 003	反而多花 50%

三对角矩阵是一个对照：它的非零个数 $3n-2$ 相对 $n^2$ 极少，但因为位置有规律， 用 $3n-2$ 个单元就够了，连行列号都不用存——有规律时永远比三元组省。

十字链表适合频繁修改（增删非零元素）的稀疏矩阵：

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

每个结点同时挂在所在行链表和列链表上——所以叫"十字"。 一个 $m\times n$ 稀疏矩阵有 $m$ 个行头指针 $+$ $n$ 个列头指针。 遍历某一行沿 right 走一遍、某一列沿 down 走一遍；插入新的非零元素在两条链上各找位置后插入， 不需要移动其他元素。劣势是每个结点有 5 个域，单元素开销明显大于三元组。

	三元组表	十字链表
单个非零元素的开销	小（$i,j,value$ 三个值）	大（再多 2 个指针）
插入 / 删除	慢（数组要移位，$O(t)$）	快（$O(\text{行长}+\text{列长})$）
按行遍历	快（本来就按行序存）	快（沿 right）
按列遍历	慢（要扫全表）	快（沿 down）
适用场景	静态稀疏矩阵	频繁修改的稀疏矩阵

两者都是稀疏矩阵的压缩存储结构，常被拿来与两个"看着像但不是"的结构对比：

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

邻接矩阵的命名容易误导：它的"矩阵"二字让人以为和稀疏矩阵有关。 实际上它就是一个普通的 $n\times n$ 二维数组，完全不压缩。它本身正是"稀疏矩阵压缩" 要解决的对象之一——稀疏图的邻接矩阵用三元组或十字链表存才高效（图那一章的 邻接表 与 十字链表 就是这个思路）。

为什么要压缩：三组量化数字（想看清收益有多大就展开）

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

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

严蔚敏教材对压缩存储的表述是："为多个值相同的元只分配一个存储空间，对零元不分配空间。 假若值相同的元素或者零元素在矩阵中的分布有一定规律，则称此类矩阵为特殊矩阵。"

考点速记

三条会被反复调用的结论：

1. 推法只有一条：前 $k-1$ 行（列）累加 $+$ 行（列）内偏移。八个公式都是它在不同形状下的实例。
2. 查元素固定三步：判断在不在被存的三角 → 不在就交换下标（对称）或直接取末位（三角）→ 代公式。
3. 压缩不是无条件更优：三元组要 $3t+3$ 个单元，非零占比低于约 $1/3$ 才开始省空间。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：绝大多数是同一道题的变形——给定矩阵类型、存储方向和一个元素，问它在一维数组中的下标。要注意题面里的四个变量：

• 存的是上三角还是下三角（题面会写 $1\le i\le j\le n$ 之类的范围）；
• 按行优先还是按列优先；
• 待查元素在不在被存的那一半——若不在，先按对称性交换下标。比如 10 阶对称矩阵只存上三角，问 $m_{7,2}$：$7>2$ 不在上三角，先换成 $m_{2,7}$ 再算；
• 数组下标从 0 还是从 1 开始。

三对角矩阵是另一种问法，用 $2i+j-3$ 直接代即可，边界行也适用，不必单独处理。此外还考过两道概念题：适合压缩存储稀疏矩阵的两种结构是三元组表和十字链表；以及三元组表除三元组外还必须存矩阵的行数与列数（不是"含非零元素的行数/列数"——那还原不出原矩阵的形状）。

易错：元素不在被存的三角，却直接代公式。 对称矩阵要先交换下标，三角矩阵要直接取末位常数格。

易错：行优先与列优先的累加对象搞混。 上三角按行存时第 $i$ 行有 $n-i+1$ 个元素；按列存时第 $j$ 列有 $j$ 个元素。累加的是哪个，取决于存储方向。

易错：两个 base 混成一个。 矩阵下标的 base 与数组下标的 base 互相独立，先按熟悉的那套算完，最后一步再 $\pm 1$ 转换，别临场改公式。

易错：看到"矩阵"就往压缩上套。 邻接矩阵是图的稠密存储，$n\times n$ 一格不省，不是压缩结构。

教材出处

• 压缩存储的定义（"为多个值相同的元只分配一个存储空间，对零元不分配空间"）、 特殊矩阵的定义、对称矩阵的压缩存储（存下三角，一维数组 $sa[n(n+1)/2]$， 式 4-14 给出 $sa[k]$ 与 $a_{ij}$ 的一一对应）、三角矩阵的定义与"再加一个存储常数 $c$ 的存储空间"：严蔚敏《数据结构（C 语言版）》（第 3 版）p121「4.4.3 特殊矩阵的压缩存储」
• 上三角矩阵的下标式 4-16、对角矩阵（三对角矩阵） 的定义与图 4.13， 以及稀疏矩阵的定义（"其非零元较零元少，且分布没有一定规律"）：同书 p122
• 行优先 / 列优先的地址公式与 $n$ 维映像函数（本篇一切压缩公式的地基）：同书 p119–p120
• 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图4.3 三对角矩阵，p140

说明：严蔚敏《数据结构（C 语言版）》（第 3 版）在给出稀疏矩阵的定义后即写明 "这类矩阵的压缩存储就要比特殊矩阵复杂，在此不做讨论"， 因此本篇三元组表与十字链表两节没有该书页码可引，其结构定义与优劣对比由本篇自行整理， 不附会页码。

相关知识

多维数组的存储（本篇所有压缩公式的地基，务必先看）｜ 顺序表（压缩存储的落脚点仍是一维顺序存储）｜ 邻接矩阵（图的稠密存储，不是压缩结构）｜ 邻接表、十字链表（同样的"只存存在的边"思想）｜ 数组与特殊矩阵的压缩存储（拆分前的旧合并视图）

相关文章

• 栈和队列基本概念
• 顺序栈
• 共享栈
• 链栈
• 链式队列
• 循环队列
• 双端队列
• 应用：括号匹配
• 应用：表达式求值
• 应用：栈在递归中的应用
• 多维数组的存储

真题练习

相关真题（5题）

2023Q32分2020Q12分2018Q32分2017Q32分2016Q42分