📐 408 矩阵压缩存储与稀疏矩阵(含稀疏图对比)终极笔记
核心痛点解决
矩阵压缩下标计算极易差 1(下标从 0 还是从 1 开始?行优先还是列优先?),稀疏矩阵与稀疏图的存储结构常在选择题中混考。 本笔记采用 【不背公式现场推导法 + 可折叠手算例子 + 题眼破局 + 避坑指南】,保证考场上算下标、选结构 100% 零失误。
一、 稀疏矩阵的压缩存储(你的真题图片核心考点)
一句话记忆
“稀疏矩阵只存非零元,失去随机存取特性;除三元组外,必须额外存【总行数、总列数、非零元总个数】”。
1. 什么是稀疏矩阵?
矩阵中非零元素的个数 远远小于矩阵元素的总数 (通常认为稠密度 ),且非零元素分布没有规律。
2. 两种存储结构对比(408 选择题必考)
三元组顺序表 vs 十字链表
存储结构 存储方式 核心结构组成 适用场景 随机存取? 三元组表(顺序存储) 把每个非零元存为 (行标 i, 列标 j, 值 v),按行优先排列三元组数组 + 矩阵总行数 、总列数 、非零元个数 矩阵转置、静态查阅 ❌ 丧失随机存取特性(需顺序遍历查找) 十字链表(链式存储) 每个非零元是一个结点,同时处于所在行循环链表和列循环链表中 结点含 5 个域: row, col, val, right, down+ 行/列头指针数组频繁插入、删除非零元(如矩阵加减法 ) ❌ 不能随机存取
408 核心防坑指南(直击你发的图片真题!)
为什么三元组表必须额外保存“矩阵的总行数”和“总列数”?
- 假设一个 的稀疏矩阵,第 9 行和第 10 行全都是 0(没有任何非零元素)。
- 那么在三元组表中,行标
i最大只会出现到8!如果不额外记录“矩阵总行数为 10、总列数为 10”,当你试图把这个三元组还原成原矩阵时,你根本不知道原矩阵到底是 还是 !- 至于“包含非零元素的行数/列数”,直接扫描一遍三元组表就能统计出来,不需要额外保存。
📝 图片原题复盘(点击展开看破局步骤)
题目(你图片中的第 3 题):若采用三元组表存储结构存储稀疏矩阵 ,则除三元组表外,下列数据中还需要保存的是( ): I. 的行数 II. 中包含非零元素的行数 III. 的列数 IV. 中包含非零元素的列数 A. I、III B. I、IV C. II、IV D. I、II、III、IV
🧠 破局思路(题眼 + 步骤):
- 题眼:“三元组表”、“还需要保存”。
- 推导:为了能唯一还原矩阵的维度(防止末尾出现全 0 行或全 0 列导致维度丢失),三元组表的表头(通常存在第 0 行或结构体变量中)必须保存三个元数据:① 矩阵总行数(I)、② 矩阵总列数(III)、③ 非零元素总个数。
- II 和 IV 可由三元组表自身直接统计得出,无需冗余保存。
结论:选 A(I、III)。
二、 特殊矩阵的压缩存储(下标计算必杀技)
考场零失误心法(千万别死背公式!)
408 算一维数组下标
k,永远只用两步**“数人头法”**:
- 算排在
A[i][j]前面的元素一共有多少个(记为Count):
Count= 前面完整行(或列)的元素总数 + 当前行(或列)排在它前面的元素个数。- 看一维数组
B[k]的起始下标:
- 若
B从0开始:k = Count- 若
B从1开始:k = Count + 1
1. 二维数组普通存储( 行 列,设行列下标从 0 开始,B 从 0 开始)
- 行优先:前面有 整行(每行 个),当前行前面有 个 。
- 列优先:前面有 整列(每列 个),当前列前面有 个 。
2. 对称矩阵( 阶,,行列下标从 1 开始)
压缩策略:只存下三角(含主对角线),共 个元素
核心铁律:
- 如果题目默认行优先存下三角():
- 当给你的元素满足 (在下三角):直接算前面有
i-1行(元素数为 ),当前行前面有j-1个元素 。- 当给你的元素是 (在上三角):因为对称矩阵 ,第一步必须先把
i和j互换,折算到下三角再代公式!
📝 小题自测(点击展开看手算与破局)
题目:将 10 阶对称矩阵 (下标从 1 开始)压缩存储到一维数组 中(按行优先存储下三角)。求 在数组 中的下标。
手算步骤:
- 看位置:题目存的是下三角(要求行号 列号),但问的是 (,在上三角)!
- 对称转换:利用 ,转化为求下三角的 (第 6 行第 4 列)。
- 数前面的人头(Count):
- 前面有完整的
1 ~ 5行: 个元素。- 第 6 行中,排在第 4 列前面的有
4 - 1 = 3个元素(即A[6][1], A[6][2], A[6][3])。- 前面总共有 个元素。
- 看 B 的起始下标:题目写明 (从 1 开始),所以 。
结论:存入 。
变体预警(列优先陷阱!)
如果题目改成**“按列优先存储下三角”**(或行优先存储上三角):
- 下三角第 1 列有 个元素,第 2 列有 个……第 列有 个!
- 遇到这种题千万别背公式,直接在草稿纸上画个 的小矩阵,标上第 1 列 个、第 2 列 个,把前 列加起来即可!
3. 三角矩阵(上三角 / 下三角,常量区占最后 1 个位置)
与对称矩阵的唯一区别
- 三角矩阵另一半全都是同一个常数 (比如全为 0)。
- 一维数组长度比对称矩阵多 1 个位置:共 个空间,最后一个位置专门用来存那个常数 !
- 下标计算与对称矩阵完全一致(但在非压缩区直接返回最后一个下标 或 )。
4. 三对角矩阵(带状矩阵,)—— 考察频率:⭐⭐⭐⭐
一句话记忆
“首尾两行各 2 个,中间每行都 3 个;前向公式
2i + j - 3(从 0 起)”。
双向推导公式(设矩阵行列 从 1 开始)
① 已知
A[i][j]求一维下标k(按行优先):
- 前面有
i-1行:第 1 行 2 个,其余i-2行每行 3 个 前i-1行共有 个元素。- 第
i行有A[i][i-1], A[i][i], A[i][i+1],因此A[i][j]前面有j - (i - 1) = j - i + 1个元素。- 前面元素总数 。
- 若
B从 0 开始:- 若
B从 1 开始:② 已知一维下标
k反求矩阵行列(i, j)(选择题秒杀神技):
- 考场最快做法:根本不用记整除取模公式!直接把选项里的
(i, j)代入上面的正向公式2i + j - 3(或-2),算出来等于题目给的k直接秒选!
📝 小题自测(点击展开看秒杀过程)
题目:将 阶三对角矩阵 (行列下标从 1 开始)按行优先压缩存入一维数组 中,则 对应矩阵中的哪个元素? A. B. C. D.
秒杀步骤:
- 数组 从 1 开始,正向公式为 。
- 直接代选项验证哪个等于 26:
- 代入 A ():
- 代入 B ():
- 代入 C ():
- (若题目问 则选 C;若问 ,由于第 9 行第 10 列 代入得 ,可知 必为 !)
三、 稀疏图 vs 稠密图:矩阵与链表存储全对比(联动《图论核心算法》)
为什么要把“稀疏矩阵”和“稀疏图”放在一起看?
当一个图是稀疏图(边数 )时,它的邻接矩阵就是一个典型的稀疏矩阵! 如果直接用二维数组(邻接矩阵)存稀疏图,会浪费海量的
0或∞空间,且遍历一个点的所有邻居需要空扫整行 。因此稀疏图必须改用链式压缩结构(邻接表、十字链表、邻接多重表)!
1. 图的 4 大存储结构全景对比表(408 必背)
| 存储结构 | 适用图类型 | 空间复杂度 | 找某点所有邻居 | 判两点是否有边 | 删边/操作特点 |
|---|---|---|---|---|---|
| 邻接矩阵 | 稠密图(有向/无向均可) | (只与顶点数有关,与边数无关) | (最快) | 无向图的邻接矩阵一定是对称矩阵,可压缩存储! | |
| 邻接表 | 稀疏图(有向/无向均可) | 无向: 有向: | 有向图求入度难(需遍历全表,或建逆邻接表);表示不唯一 | ||
| 十字链表 | 有向稀疏图 | 完美结合邻接表与逆邻接表,求入度、出度都极快(也是稀疏矩阵的链式存储结构!) | |||
| 邻接多重表 | 无向稀疏图 | (一条边只存 1 个结点!) | 解决无向图邻接表中“一条边存两份、删边需找两个结点”的痛点 |
408 极易混淆的两大高频考点
考点 1:邻接矩阵 (矩阵乘法)的图论物理意义!(2012/2021 真题)
- 设图 的邻接矩阵为 (无权图,有边为 1,无边为 0),则矩阵幂 中的元素 的值,等于从顶点 到顶点 长度为 的路径的总条数!
考点 2:拓扑排序 + 邻接矩阵 = 三角矩阵!(2016/2022 真题)
- 若一个有向图(DAG)存在拓扑序列,且顶点的编号恰好按拓扑有序排列(即每条有向边都从小编号指向大编号,),那么该图的邻接矩阵必定是一个上三角矩阵(主对角线及以下全为 0)!
- 反之,若一个有向图的邻接矩阵是三角矩阵(主对角线全为 0 的上三角或下三角),则该图必定没有环(一定存在拓扑序列)!
2. 图论核心算法在【邻接矩阵(稠密图)】vs【邻接表(稀疏图)】下的复杂度对照
背完这张表,408 图论复杂度题一分不丢
算法 / 操作 邻接矩阵(适合稠密图) 邻接表(适合稀疏图) 408 考场核心结论 DFS / BFS 遍历 遍历每个点都要扫描其所有边,矩阵必须扫满整行 拓扑排序 / 关键路径 本质基于 DFS 或 BFS(入度表),复杂度同遍历 Prim(最小生成树) (配合堆) 408 默认考朴素 Prim,时间复杂度 与边数无关,专治稠密图 Kruskal(最小生成树) — 按边排序 + 并查集,时间只与边数 有关,专治稀疏图 Dijkstra(单源最短路) (配合堆) 408 默认考朴素版 ;若求所有点对执行 次则为 Floyd(多源最短路) 不适用(直接用矩阵) 三重循环固定
📝 历年真题精选(实战演练·破局版)
真题 1(特殊矩阵压缩 · 对称矩阵列优先陷阱)
题目:设有一个 12×12 的对称矩阵 ,将其上三角部分的元素 ()按列优先存入 C 语言的一维数组 中,元素 在 中的下标是( )。 A. 15 B. 20 C. 21 D. 22
🧠 破局思路(题眼 + 步骤) 题眼:“上三角()”、“列优先”、“C 语言数组(下标从 0 开始!)”。
- 数前面完整的列:求 (第 6 行第 6 列),前面有完整的
1 ~ 5列。- 在上三角中,第 1 列有 1 个元素(),第 2 列有 2 个元素()……第 5 列有 5 个元素。所以前 5 列共有 个元素。
- 数当前列(第 6 列)前面的元素:在第 6 列中,排在第 6 行前面的有
1 ~ 5行,共 5 个元素。- 总人头数 Count = 个。
- 看起始下标:C 语言一维数组下标从 0 开始,所以 ! 结论:选 B。
真题 2(图的邻接矩阵与三角矩阵 · 2016 年 408 真题)
题目:若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零,则关于该图拓扑序列的结论是( )。 A. 存在,且唯一 B. 存在,且不唯一 C. 存在,可能不唯一 D. 无法确定是否存在
🧠 破局思路(题眼 + 步骤) 题眼:“主对角线以下均为零(上三角矩阵)”。 6. 主对角线及以下均为 0(有向简单图无自环,主对角线本身为 0),说明所有的边
<i, j>都满足i < j(只能从编号小的点指向编号大的点)。 7. 既然边只能往编号大的方向走,就绝对不可能走回头路形成环!因此该图一定是 DAG(有向无环图),必定存在拓扑序列。 8. 但拓扑序列是否唯一?不一定!极端反例:假设矩阵全为 0(一个边都没有的孤立点图),它显然满足“主对角线以下全为 0”,但它的拓扑序列有 种(不唯一);而如果是一条单链 ,拓扑序列又唯一。 结论:一定存在,但可能不唯一,选 C。
真题 3(稀疏矩阵存储结构选择)
题目:对稀疏矩阵进行压缩存储后,失去了( )特性;若需要对稀疏矩阵进行频繁的加法运算(非零元素个数和位置动态变化),最适合采用的存储结构是( )。 A. 随机存取,三元组表 B. 随机存取,十字链表 C. 顺序存取,三元组表 D. 散列存取,邻接多重表
🧠 破局思路 时间内算出任意
(i, j)的存储位置,故失去随机存取特性。 10. 矩阵相加会导致原来为 0 的位置变成非 0(插入),或原来非 0 相加抵消变成 0(删除)。顺序存储的三元组移动元素代价太大,必须用链式存储的十字链表。 结论:选 B。9. 稀疏矩阵非零元素分布无规律,压缩后无法通过简单的多项式公式在