Appearance
数组与特殊矩阵的压缩存储
为什么要压缩存储
一个 n×n 的矩阵直接用二维数组存，空间是 n²。但如果矩阵有大量重复元素或零元素——比如对称矩阵有接近一半的元素是冗余的，稀疏矩阵 90% 以上都是 0——这些空间就白白浪费了。压缩存储的思路很直接：只存有用的那部分，用一个一维数组搞定，再通过映射公式把原来的二维下标 (i, j) 转换成一维下标 k。408 对这块的考法也很直接：给你矩阵类型和下标，算出 k 或者反过来算 i、j。公式不复杂，但下标从 0 还是从 1 开始会直接影响结果，这是最大的坑。
核心思想
- 数组的本质：数组是线性表的推广，n 维数组可以看成"元素为 n-1 维数组"的线性表
- 行优先 vs 列优先：二维数组在内存中是一维连续存放的，区别在于"先存完一行再存下一行"还是"先存完一列再存下一列"
- 压缩存储的核心：利用矩阵的结构特点（对称、三角、带状等），把 n² 个元素压缩到更小的一维数组中，通过映射公式实现下标转换
- 稀疏矩阵：非零元素极少时，用三元组表
(行号, 列号, 值)只存非零元素
操作详解
一、数组的存储——行优先与列优先
设二维数组 a[m][n]，每个元素占 L 个存储单元，起始地址为 LOC(a[0][0])。
下标从 0 开始（a[0..m-1][0..n-1]）：
| 存储方式 | 地址计算公式 |
|---|---|
| 行优先 | LOC(a[i][j]) = LOC(a[0][0]) + (i × n + j) × L |
| 列优先 | LOC(a[i][j]) = LOC(a[0][0]) + (j × m + i) × L |
行优先的直觉：前面有 i 整行（每行 n 个元素），再加上当前行的前 j 个元素。列优先同理，把"行"换成"列"。
下标从 1 开始（a[1..m][1..n]）：
| 存储方式 | 地址计算公式 |
|---|---|
| 行优先 | LOC(a[i][j]) = LOC(a[1][1]) + ((i-1) × n + (j-1)) × L |
| 列优先 | LOC(a[i][j]) = LOC(a[1][1]) + ((j-1) × m + (i-1)) × L |
⚠️ 易错：行优先公式中乘的是列数 n（每行有 n 个元素），列优先公式中乘的是行数 m（每列有 m 个元素）。不少同学会搞反。记忆方法：行优先"跨行"，跨一行跳过 n 个元素；列优先"跨列"，跨一列跳过 m 个元素。
二、对称矩阵的压缩存储
对称矩阵满足 a[i][j] = a[j][i]，上三角和下三角的元素完全相同，只需存其中一半。
策略：只存下三角区域（含对角线），压缩到一维数组 B[0..n(n+1)/2-1]。
一维数组大小：n(n+1)/2
下标从 0 开始（a[0..n-1][0..n-1] → B[0..n(n+1)/2-1]）：
对于元素 a[i][j]，映射到 B[k]：
- 当
i ≥ j（下三角区域）：k = i(i+1)/2 + j - 当
i < j（上三角区域）：利用对称性a[i][j] = a[j][i]，k = j(j+1)/2 + i
下标从 1 开始（a[1..n][1..n] → B[0..n(n+1)/2-1]）：
- 当
i ≥ j：k = i(i-1)/2 + j - 1 - 当
i < j：k = j(j-1)/2 + i - 1
手算示例：5×5 对称矩阵（下标从 0 开始），求 a[3][1] 在压缩数组中的位置。
i = 3, j = 1, 满足 i ≥ j，用下三角公式：
k = i(i+1)/2 + j = 3×4/2 + 1 = 6 + 1 = 7
即 a[3][1] 存储在 B[7]。验证：下三角元素按行存放顺序为 a[0][0], a[1][0], a[1][1], a[2][0], a[2][1], a[2][2], a[3][0], a[3][1], ...，数一下 a[3][1] 确实排在第 8 个位置（下标 7）。
三、三角矩阵的压缩存储
三角矩阵的一个三角区域全是同一个常量 c（通常是 0），只需存另一个三角区域加上这个常量。
一维数组大小：n(n+1)/2 + 1（最后一个位置存常量 c）
下三角矩阵
下三角区域和对角线上有值，上三角全是常量 c。
下标从 0 开始：
- 当
i ≥ j：k = i(i+1)/2 + j（和对称矩阵一样） - 当
i < j：k = n(n+1)/2（指向存放常量 c 的最后一个位置）
上三角矩阵
上三角区域和对角线上有值，下三角全是常量 c。
下标从 0 开始：
上三角按行存放，第 i 行有 n - i 个元素（从 a[i][i] 到 a[i][n-1]）。
- 当
i ≤ j：k = (2n - i + 1) × i / 2 + (j - i) - 当
i > j：k = n(n+1)/2（指向常量 c）
公式拆解：前 i 行一共有 n + (n-1) + ... + (n-i+1) = (2n-i+1)×i/2 个元素，当前行内偏移 j - i。
下标从 1 开始：
- 上三角（
i ≤ j）：k = (2n - i + 2) × (i - 1) / 2 + (j - i) - 下三角（
i > j）：k = n(n+1)/2
四、三对角矩阵（带状矩阵）
三对角矩阵的非零元素集中在主对角线及其相邻的两条对角线上，即 |i - j| ≤ 1 时 a[i][j] 才可能非零。
┌ a00 a01 0 0 0 ┐
│ a10 a11 a12 0 0 │
│ 0 a21 a22 a23 0 │
│ 0 0 a32 a33 a34 │
└ 0 0 0 a43 a44 ┘一维数组大小：3n - 2（第一行和最后一行各 2 个元素，中间每行 3 个）
下标从 0 开始（a[0..n-1][0..n-1] → B[0..3n-3]）：
- 映射：
k = 2i + j - 逆映射（已知 k 求 i, j）：
i = ⌊(k + 1) / 3⌋，j = k - 2i
下标从 1 开始（a[1..n][1..n] → B[0..3n-3]）：
- 映射：
k = 2i + j - 3 - 逆映射：
i = ⌊(k + 2) / 3⌋，j = k - 2i + 3
手算示例：4×4 三对角矩阵（下标从 0 开始），设 LOC(B[0]) = 100，每个元素占 4 字节，求 a[2][3] 的存储地址。
第一步：求 a[2][3] 在一维数组中的下标
k = 2i + j = 2×2 + 3 = 7
第二步：计算地址
LOC(a[2][3]) = LOC(B[0]) + k × L = 100 + 7 × 4 = 128验证：按行列出非零元素顺序为 a[0][0], a[0][1], a[1][0], a[1][1], a[1][2], a[2][1], a[2][2], a[2][3], ...，a[2][3] 排在第 8 个位置（下标 7），地址 = 100 + 28 = 128。
⚠️ 易错：三对角矩阵逆映射公式
i = ⌊(k+1)/3⌋是下标从 0 开始的版本。从 1 开始时变成i = ⌊(k+2)/3⌋。考试如果只记了一个版本，代入验证一下就能避免出错。
五、稀疏矩阵
当矩阵中非零元素的个数远少于总元素个数时（通常非零元素不超过 5%），用常规二维数组存储会浪费大量空间。
三元组表：只存储非零元素，每个非零元素用一个三元组 (i, j, v) 表示（行号、列号、值）。
例如 4×5 矩阵中有 3 个非零元素：
| 行号 i | 列号 j | 值 v |
|---|---|---|
| 0 | 2 | 5 |
| 1 | 4 | 8 |
| 3 | 1 | 3 |
三元组表通常按行优先顺序存放。其他表示方式还有十字链表（适合矩阵运算频繁的场景），408 大纲了解即可。
⚠️ 易错：对称矩阵存的是下三角还是上三角直接决定映射公式。题目说"按行优先压缩存储下三角"和"按行优先压缩存储上三角"对应的公式完全不同。审题时先确认存的是哪个三角。
公式汇总表
| 矩阵类型 | 存储大小 | 映射公式（下标从 0 开始） |
|---|---|---|
| 对称矩阵（存下三角） | n(n+1)/2 | i≥j: k = i(i+1)/2 + j；i<j: k = j(j+1)/2 + i |
| 下三角矩阵 | n(n+1)/2 + 1 | i≥j: k = i(i+1)/2 + j；i<j: k = n(n+1)/2 |
| 上三角矩阵 | n(n+1)/2 + 1 | i≤j: k = (2n-i+1)×i/2 + (j-i)；i>j: k = n(n+1)/2 |
| 三对角矩阵 | 3n - 2 | k = 2i + j |
考研高频考点
- ⭐ 对称矩阵的压缩下标映射公式——选择题/填空题几乎每年都考，给定
(i, j)求 k 或给定 k 反推(i, j) - ⭐ 行优先/列优先的地址计算——填空题高频，直接套公式但注意行数列数别搞反
- ⭐ 三对角矩阵的映射与逆映射——填空题常考，逆映射的取整方向容易出错
- ⭐ 下标从 0 开始 vs 从 1 开始的公式差异——做题第一步先看清题目的下标约定，选错公式满盘皆输
- ⭐ 上三角矩阵与下三角矩阵的公式区别——不能混用，存储的三角区域不同公式就不同
- 稀疏矩阵的三元组表表示——概念题为主，偶尔考三元组表的存储空间计算