多维数组的存储

一、为什么"数组"被放在栈、队列这一章？

408 大纲第二章叫「栈、队列和数组」。一眼看上去三个东西不太搭——栈和队列是操作受限的线性表，数组明明是更基础的数据结构。

大纲把它们绑在一起的真正原因：这一章讲的是"线性表怎么落到内存上"。线性表在第一章给了抽象定义，到了第二章要落地：

栈：限制只能在一端进出，落到内存上是数组或链表
队列：限制只能一端进、另一端出，落到内存上是数组（含循环）或链表
数组：定义本身就规定了「按下标随机访问、元素按某种顺序连续存储」——内存映射规则是整章最底层的一块拼图

理解了这一点你就明白：为什么"数组"这一节的核心不是"什么是数组"（你已经会了），而是 "二维及以上的数组，怎么按线性顺序排进一维内存里"。

二、一维数组：最简单的地址公式

一维数组 A[0..n-1]，每个元素占 $L$ 字节，首地址为 $Addr (A [0])$ 。下标为 $i$ 的元素地址是：

Addr (A [i]) = Addr (A [0]) + i \cdot L

这是后面所有公式的母版。注意两件事：

这里 $i$ 是 0-based —— A[0] 偏移 0，A[1] 偏移 $L$ ，A[i] 偏移 $i \cdot L$
若题目用 1-based（伪代码或老教材常见），把上式中的 $i$ 换成 $i - 1$ 即可

编者注（base 陷阱）：408 大题 C 语言相关的代码一律 0-based；考研题面如果出现 $A [1. . n]$ 或 $m_{i, j} (1 \leq i, j \leq n)$ 这种写法，是在用数学记号 1-based。两个 base 是题面给出的，不是你能选的——你要做的是把题目的 base 翻译到公式里。

三、二维数组：行优先与列优先

二维数组 A[m][n]（ $m$ 行 $n$ 列）需要把一个矩阵塞进一维内存里。两种主流顺序：

行优先（row-major）：一行一行按顺序排，C 语言和 Java 都用这种。

text

A[0][0] A[0][1] ... A[0][n-1]  A[1][0] A[1][1] ... A[1][n-1]  ...  A[m-1][n-1]
└──────── 第 0 行 n 个元素 ────┘└──────── 第 1 行 n 个元素 ────┘

列优先（column-major）：一列一列按顺序排，Fortran 和 MATLAB 默认是这种。

text

A[0][0] A[1][0] ... A[m-1][0]  A[0][1] A[1][1] ... A[m-1][1]  ...  A[m-1][n-1]
└──────── 第 0 列 m 个元素 ────┘└──────── 第 1 列 m 个元素 ────┘

题目不会假定你知道哪种语言用哪种——必须看题面明确告知。

3.1 行优先地址公式（0-based）

$A [i] [j]$ 之前一共有多少个元素？

完整的 $i$ 行： $i \cdot n$ 个（每行 $n$ 个元素，已经过了 $i$ 行）
第 $i$ 行内 $A [i] [j]$ 之前： $j$ 个

加起来 $A [i] [j]$ 的偏移是 $(i \cdot n + j)$ 个元素。所以：

Addr (A [i] [j]) = Addr (A [0] [0]) + (i \cdot n + j) \cdot L

记忆口诀："行 × 列宽 + 列"——行号乘以每行有多少个元素，再加上当前列偏移。

3.2 列优先地址公式（0-based）

把行/列角色对调：

完整的 $j$ 列： $j \cdot m$ 个（每列 $m$ 个元素）
第 $j$ 列内 $A [i] [j]$ 之前： $i$ 个

Addr (A [i] [j]) = Addr (A [0] [0]) + (j \cdot m + i) \cdot L

记忆口诀："列 × 行高 + 行"。

编者注（公式对偶性）：行优先和列优先的公式是完全对偶的——把 $i \leftrightarrow j$ 、 $m \leftrightarrow n$ 同时交换就能从一个变成另一个。不要分开记两个公式，理解了对偶性以后只需要记一个。

3.3 交互可视化：点击元素看下标

打开下方可视化，点击矩阵任意元素 → 一维数组中对应下标会高亮 + 公式实时显示；切换"行优先 / 列优先"立刻能看到同一元素映射到不同位置。

加载可视化中...

3.4 1-based 形式

如果题目用 $m_{i, j} (1 \leq i \leq m, 1 \leq j \leq n)$ 这种数学记号，把上式中的 $i, j$ 替换为 $i - 1, j - 1$ ：

Addr (m_{i, j})_{行优先} = Addr (m_{1, 1}) + [(i - 1) \cdot n + (j - 1)] \cdot L

考场上不要去背 1-based 公式——把 0-based 公式记牢，再根据题目下标起点做平移，比硬记两套要稳。

四、用基准点反推每行列数

考研最爱的题型：题目不直接告诉你 $n$ （每行列数），而是给两个元素的地址，让你先反推 $n$ ，再算第三个元素。

4.1 套路

设题目按行优先存储，给定：

$Addr (A [i_{1}] [j_{1}]) = a_{1}$
$Addr (A [i_{2}] [j_{2}]) = a_{2}$

代入行优先公式两次相减，消掉 $Addr (A [0] [0])$ ：

a_{2} - a_{1} = [(i_{2} - i_{1}) \cdot n + (j_{2} - j_{1})] \cdot L

解出 $n$ 。

4.2 真题精讲：2021-03

已知二维数组 A 按行优先方式存储，每个元素占用 1 个存储单元。若元素 A[0][0] 的存储地址是 100，A[3][3] 的存储地址是 220，则元素 A[5][5] 的存储地址是？

第一步：用 A[3][3] 反推每行列数 $n$ 。

220 = 100 + (3 n + 3) \cdot 1

3 n + 3 = 120 \Rightarrow n = 39

第二步：代入 A[5][5]。

Addr (A [5] [5]) = 100 + (5 \times 39 + 5) \times 1 = 100 + 195 + 5 = 300

答案 300。

4.3 这道题的两个致命陷阱

陷阱 1：把 $220 - 100 = 120$ 直接除以 3 得 $n = 40$

这是把 A[0][0] 到 A[3][3] 之间的偏移量"全都算成行偏移"。但 A[3][3] 不仅在行方向跨了 3 行，列方向也跨了 3 列。必须写出完整方程 $3 n + 3 = 120$ 才能解出 $n = 39$ 。

陷阱 2：算到第 5 行的开头就停了

A[5][5] 不等于 A[5][0]。第 5 行开头偏移是 $5 \cdot 39 = 195$ ，还要再加 5 个列偏移才到 A[5][5]。算完地址再回头核对一下"行 × 列宽 + 列"两项都加了，是个稳的习惯。

五、多维数组的通用公式

三维数组 $A [d_{1}] [d_{2}] [d_{3}]$ （按行优先）， $A [i_{1}] [i_{2}] [i_{3}]$ 之前的元素个数是：

i_{1} \cdot (d_{2} \cdot d_{3}) + i_{2} \cdot d_{3} + i_{3}

记忆方法：从外层维度向内乘——第一维要跨过完整的 $(d_{2} \times d_{3})$ 个元素，第二维要跨过 $d_{3}$ 个，第三维只移动 1 个。

推广到 $n$ 维：

offset (i_{1}, i_{2}, \dots, i_{n}) = \sum_{k = 1}^{n} i_{k} \cdot \prod_{p = k + 1}^{n} d_{p}

考研一般不超过三维，但理解了这个递推就明白：行优先就是"最右边的下标变化最快"，列优先反之。

六、行优先 vs 列优先：什么时候考你？

题目特征	怎么判断用哪种
题面明确写 "按行优先" / "按列优先"	直接用对应公式
给的是 C 语言数组 `int A[m][n]`	行优先（C 语言默认）
出现 Fortran / MATLAB 字样（少见）	列优先
完全没说	一般按行优先（408 默认）

考试中如果遇到"列优先"的二维数组题，多半还会叠加对称矩阵 / 三角矩阵 / 三对角矩阵的压缩存储——见下一篇特殊矩阵的压缩存储。

七、易错点汇总（考前 30 秒过一遍）

0-base / 1-base 看清题面，不要默认。C 语言代码题一定是 0-based。
反推每行列数时方程必须完整： $a_{2} - a_{1} = (i_{2} - i_{1}) \cdot n + (j_{2} - j_{1})$ ，两项都不能丢。
行偏移 + 列偏移都要加：算地址不要算到本行开头就停。
行优先和列优先是对偶的：只记一个公式，另一个靠对偶变出来。
元素占字节数 $L$ 题面会告诉你，不要默认是 1。

八、相关真题

codebrick 题库中考查"多维数组存储"知识点（topic = matrix-storage）的真题：

年份	题号	考点	难度
2016	04	三对角矩阵 + 下标	★★★
2018	03	对称矩阵 + 行优先	★★★
2020	01	对称矩阵 + 列优先	★★★
2021	03	行优先地址 + 反推 n	★★

近 10 年高频考点，2024、2025 沉寂未考。下一篇特殊矩阵的压缩存储接着讲对称、三角、三对角和稀疏四种矩阵的下标推导。

编者注（学习路径）：本篇是地基。把行优先 / 列优先地址公式吃透后，再去看下一篇的特殊矩阵压缩——所有压缩公式都是在这个地基上"砍掉对称冗余 / 零元素"的产物，没有新的数学，只有更精细的下标计数。

多维数组的存储 ​

一、为什么"数组"被放在栈、队列这一章？ ​

二、一维数组：最简单的地址公式 ​

三、二维数组：行优先与列优先 ​

3.1 行优先地址公式（0-based） ​

3.2 列优先地址公式（0-based） ​

3.3 交互可视化：点击元素看下标 ​

3.4 1-based 形式 ​

四、用基准点反推每行列数 ​

4.1 套路 ​

4.2 真题精讲：2021-03 ​

4.3 这道题的两个致命陷阱 ​

五、多维数组的通用公式 ​

六、行优先 vs 列优先：什么时候考你？ ​

七、易错点汇总（考前 30 秒过一遍） ​

八、相关真题 ​