Appearance
数组与特殊矩阵的压缩存储
📖 本文已被拆分为两篇更聚焦的文章，建议按需阅读：
- 多维数组的存储：行优先与列优先地址计算 ——专讲行优先 / 列优先的地址公式推导与 1-base / 0-base 的转换
- 特殊矩阵的压缩存储 ——专讲对称 / 三角 / 三对角 / 稀疏矩阵的映射公式推导与手算示例
本页保留作为合并视图，内容与上述两篇一致。
大纲定位
本页是旧的合并视图，内容已拆分到下列两篇，建议直接阅读拆分后的版本： 《多维数组的存储》对应 2026 大纲 三、栈、队列和数组 →（四）多维数组的存储， 《特殊矩阵的压缩存储》对应 三（五）特殊矩阵的压缩存储。 两篇的推导更完整、边界更清楚，本页不再单独维护。
为什么要压缩存储
一个 n×n 的矩阵直接用二维数组存，空间是 n²。但如果矩阵有大量重复元素或零元素——比如对称矩阵有接近一半的元素是冗余的，稀疏矩阵 90% 以上都是 0——这些空间就白白浪费了。压缩存储的思路很直接：只存有用的那部分，用一个一维数组搞定，再通过映射公式把原来的二维下标 (i, j) 转换成一维下标 k。给定矩阵类型和下标算出 k，或反过来由 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 + 1) / 3⌋ + 1，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+1)/3⌋ + 1（不是把 +1 挪进取整号里写成⌊(k+2)/3⌋，那样k = 0会算出i = 0）。只记了一个版本时，用k = 0代进去自查一下就能避免出错。
五、稀疏矩阵
当矩阵中非零元素的个数远少于总元素个数时（通常非零元素不超过 5%），用常规二维数组存储会浪费大量空间。
三元组表：只存储非零元素，每个非零元素用一个三元组 (i, j, v) 表示（行号、列号、值）。
例如 4×5 矩阵中有 3 个非零元素：
| 行号 i | 列号 j | 值 v |
|---|---|---|
| 0 | 2 | 5 |
| 1 | 4 | 8 |
| 3 | 1 | 3 |
三元组表通常按行优先顺序存放。其他表示方式还有十字链表（适合矩阵运算频繁的场景）。
易错：对称矩阵存的是下三角还是上三角直接决定映射公式。题目说"按行优先压缩存储下三角"和"按行优先压缩存储上三角"对应的公式完全不同。审题时先确认存的是哪个三角。
公式汇总表
| 矩阵类型 | 存储大小 | 映射公式（下标从 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 |
考点速记
这一页是合并视图，本身不单独成题。 它的内容已经拆到下面两篇，考点速记与真题考法也都写在那里，建议直接看拆分后的版本：
- 《多维数组的存储》——行优先 / 列优先的地址计算，含"给两个元素地址反推每行列数"那类题的三步做法；
- 《特殊矩阵的压缩存储》——对称 / 三角 / 三对角 / 稀疏矩阵的下标映射，含三次与真题同型的手算。
留在本页的三条结论：
- 压缩存储的推法只有一条：前
行（列）累加 行（列）内偏移。 - 行优先乘列数、列优先乘行数，两个公式完全对偶。
- 下标从 0 还是从 1 开始会直接改变结果，矩阵下标与数组下标的 base 互相独立，代入前先看清题面。
易错：对称矩阵存的是下三角还是上三角直接决定映射公式。题面写"按行优先压缩存储下三角"和"上三角"，对应的公式完全不同——审题时先确认存的是哪个三角。
相关知识
- 顺序表是数组最直接的应用——一维数组实现的线性表
- 邻接矩阵本质上就是图的二维数组存储，无向图的邻接矩阵恰好是对称矩阵，理论上也可以压缩存储
- 散列表的地址映射思想与矩阵压缩存储的下标映射有相似之处——都是把逻辑位置映射到物理位置