多维数组的存储

2026 大纲 三（四）多维数组的存储（压缩存储见《特殊矩阵的压缩存储》）。

一条方法：先数完整的行，再数行内的

内存是一维的，多维数组必须线性化才能放进去。而无论几维、无论行优先还是列优先，数偏移量的方法只有一条：先数跨过了多少个完整的行（列），再数本行（列）内还差几个。

下面所有公式——包括三维、$n$ 维、以及下一篇《特殊矩阵的压缩存储》里的全部压缩公式——都是这一句话的不同实例。真正需要记的只有这一句。

存储次序	地址公式（0-based，元素大小 $L$）	乘的是谁
一维 A[0..n-1]	$\text{LOC}(A[i])=\text{LOC}(A[0])+i\cdot L$	—
行优先（C / Java）	$\text{LOC}(A[i][j])=\text{LOC}(A[0][0])+(i\cdot n+j)\cdot L$	🔴 列数 $n$
列优先（Fortran / MATLAB）	$\text{LOC}(A[i][j])=\text{LOC}(A[0][0])+(j\cdot m+i)\cdot L$	🔴 行数 $m$
三维行优先 $A[d_1][d_2][d_3]$	偏移 $=i_1(d_2{d}_3)+i_2{d}_3+i_3$	面 $\times$ 行 $\times$ 元素

🔴 为什么行优先乘列数	"跨一整行"跳过的是一行里的元素个数，也就是列数；列优先反之。两个公式完全对偶（$i\leftrightarrow j$、$m\leftrightarrow n$ 同时交换），记一个即可
🔴 1-base 怎么办	不要重新推公式，代入前把下标各减 1：行优先 $\text{LOC}(m_{1,1})+[(i-1)n+(j-1)]L$。转换只发生在"数偏移量"这一步，公式结构不变
base 是题面给的	C 语言代码题一律 0-based；出现 $A[1..n]$ 或 $m_{i,j}(1\le i,j\le n)$ 就是 1-based。把题目的 base 翻译进公式，别把题目改成你习惯的 base
🔴 随机存取的准确含义	不是"可以任意访问"，而是存取任一元素的时间都相同（$O(1)$）——地址是下标的线性函数，与元素位置无关。这与链表"必须从头遍历"形成对照
数组没有插删	维数与各维的界一经定义就不再改变，除初始化与销毁外只有存取和修改两种操作，所以顺序存储是它最合适的存储方式
自查一招	最后一个元素的偏移必须等于元素总数减一，这是检验公式对错最省事的办法
元素大小 $L$	题面给什么用什么，只有明说"每个元素占 1 个存储单元"才是 1

什么时候用哪个公式：

题面特征	用哪个公式
明确写"按行优先" / "按列优先"	直接用对应公式
给的是 C 语言数组 int A[m][n]	行优先（C 的默认存储次序）
出现 Fortran / MATLAB 字样	列优先
完全没说	按行优先处理

行优先（row-major）：一行一行按顺序排。

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）：一列一列按顺序排。

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 个元素 ────┘

交互可视化

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

加载可视化中...

两个公式为什么是对偶的

把上面那句话落到二维上，问题就化成一句：$A[i][j]$ 之前一共排了多少个元素？

按行优先数：跨过的完整行是第 $0$ 行到第 $i-1$ 行共 $i$ 行、每行 $n$ 个元素，本行内排在它前面的还有 $j$ 个，于是偏移 $=i\cdot n+j$。按列优先数则把行列的角色对调：跨过 $j$ 个完整列、每列 $m$ 个元素，本列内还有 $i$ 个，偏移 $=j\cdot m+i$。

🔴 行优先乘的是列数 $n$，不是行数 $m$。 因为"跨过一整行"跳过的是一行里的元素个数，那正是列数。这是本篇最容易写反的地方——而只要每次都老实按"跨过多少个完整的行"去数，就不会错。

两个公式完全对偶：把 $i\leftrightarrow j$、$m\leftrightarrow n$ 同时交换，一个就变成另一个。不要分开记两个公式，记一个加一句"对偶"即可。

至于 1-based：不要重新推一套公式，只在代入前把下标各减 1。转换发生在"数偏移量"这一步，公式结构一个字不变。

一维母版、两个公式的逐步推导与 1-base 形式（想把每一步都看清就展开）

一维数组是所有公式的母版。 A[0..n-1]，每个元素占 $L$ 个存储单元：

$$\text{LOC}(A[i])=\text{LOC}(A[0])+i\cdot L$$

这里 $i$ 是 0-based——$A[0]$ 偏移 0 个元素，$A[i]$ 偏移 $i$ 个；若题目用 1-based， 把 $i$ 换成 $i-1$。"地址 $=$ 首地址 $+$ 偏移的元素个数 $\times$ 每元素大小"—— 后面所有公式变的只是"偏移的元素个数"怎么数，这个框架一个字都不会变。

行优先地址公式（0-based）。问题化成一句话：$A[i][j]$ 之前一共排了多少个元素？

• 跨过的完整行：第 $0$ 行到第 $i-1$ 行，共 $i$ 行，每行 $n$ 个元素 → $i\cdot n$ 个；
• 本行内的偏移：第 $i$ 行里排在 $A[i][j]$ 之前的是 $A[i][0]\dots A[i][j-1]$，共 $j$ 个。

$$\boxed{{\displaystyle \text{LOC}(A[i][j])=\text{LOC}(A[0][0])+(i\cdot n+j)\cdot L}}$$

列优先地址公式（0-based）。把行/列的角色对调，推导逐字对应：

• 跨过的完整列：第 $0$ 列到第 $j-1$ 列，共 $j$ 列，每列 $m$ 个元素 → $j\cdot m$ 个；
• 本列内的偏移：第 $j$ 列里排在 $A[i][j]$ 之前的有 $i$ 个。

$$\boxed{{\displaystyle \text{LOC}(A[i][j])=\text{LOC}(A[0][0])+(j\cdot m+i)\cdot L}}$$

1-based 形式：转换在哪一步做。 如果题目用 $m_{i,j}(1\le i\le m,1\le j\le n)$ 这种数学记号，不要重新推一套公式，只需在代入前把下标各减 1：

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

转换发生在"数偏移量"这一步，而不是公式结构上：公式仍然是 "跨过 $(i-1)$ 个完整行 $+$ 本行内 $(j-1)$ 个"，只是"第 $i$ 行"在 1-based 下前面有 $i-1$ 行 （0-based 下有 $i$ 行）。把这个理解清楚，就不需要背两套公式。

不给列数怎么办：用两个基准点反推

有一类题目不直接告诉你 $n$（每行元素个数），而是给出两个元素的地址，要求先反推 $n$，再算第三个元素的地址。这是本篇最值得练熟的一种。

设按行优先存储，已知 $\text{LOC}(A[i_1][j_1])=a_1$、$\text{LOC}(A[i_2][j_2])=a_2$。 把行优先公式代入两次并相减，$\text{LOC}(A[0][0])$ 被消掉：

$$a_2-a_1=[(i_2-i_1)\cdot n+(j_2-j_1)]\cdot L$$

这是关于 $n$ 的一元一次方程，解出即可。关键是方程要写完整—— 行偏移、列偏移、元素大小 $L$ 三项一个都不能丢。

一次完整演算：二维数组 $A$ 按行优先存储，每个元素占 1 个存储单元， $A[0][0]$ 的存储地址是 100，$A[3][3]$ 的存储地址是 220，求 $A[5][5]$ 的存储地址。

第一步，用 $A[3][3]$ 反推每行的元素个数 $n$。$A[3][3]$ 之前跨过 3 个完整行（$3n$ 个元素）， 本行内还有 3 个，所以

$$220=100+(3n+3)\times 1⟹3n+3=120⟹n=39$$

第二步，代入 $A[5][5]$：

$$\text{LOC}(A[5][5])=100+(5\times 39+5)\times 1=100+195+5=300$$

两个易错处。其一：把 $220-100=120$ 直接除以 3 得 $n=40$。 这是把 $A[0][0]$ 到 $A[3][3]$ 的全部偏移都算成了行偏移。 但 $A[3][3]$ 不仅在行方向跨了 3 行，列方向也跨了 3 列。 必须写成 $3n+3=120$ 才能解出 $n=39$。

其二：算到第 5 行开头就停了。 $A[5][5]$ 不等于 $A[5][0]$。 第 5 行开头的偏移是 $5\times 39=195$，还要再加 5 个列偏移才到 $A[5][5]$。 算完地址回头核对"跨过的完整行"和"行内偏移"两项都加了，是一个可靠的自查动作。

列优先的同类演算：$A[6][8]$（6 行 8 列）按列优先存储，每个元素占 4 个存储单元， $\text{LOC}(A[0][0])=1000$，求 $\text{LOC}(A[4][5])$。

• 跨过 5 个完整列（第 0 $\sim$ 4 列），每列 $m=6$ 个元素 → $5\times 6=30$ 个；
• 本列内偏移 $i=4$ 个（第 5 列里 $A[0][5]\sim A[3][5]$ 排在它前面）。

$$\text{LOC}(A[4][5])=1000+(30+4)\times 4=1000+136=1136$$

如果同一条件改成行优先：跨过 4 个完整行 $\times$ 8 个 $+$ 行内 5 个 $=37$ 个， 地址为 $1000+37\times 4=1148$。同一个元素、同一块内存，两种次序下地址不同—— 所以题面不写清楚存储次序，题目就是不完整的。

自查：列优先算式里出现的是行数 $m=6$，行优先算式里出现的是列数 $n=8$。 如果你写出来的式子里乘的那个数和"跨过的是行还是列"对不上，一定是记混了。

反推题的列优先版本方法完全一样，只是把公式换成列优先后再相减：

$$a_2-a_1=[(j_2-j_1)\cdot m+(i_2-i_1)]\cdot L$$

这里未知的是行数 $m$，不是列数 $n$——因为列优先跨一整列跳过的是 $m$ 个元素。 看清楚要反推的到底是哪一个维度，是这类题的第一步。

推广到三维与 n 维的映像函数（题目给三维数组时展开）

三维数组 $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$$

推法还是同一句话：跨过 $i_1$ 个完整的"二维面"，每个面有 $d_2\times d_3$ 个元素； 再跨过 $i_2$ 个完整的"行"，每行 $d_3$ 个；最后在行内偏移 $i_3$ 个。

推广到 $n$ 维数组 $A[0..b_1-1][0..b_2-1]\cdots [0..b_n-1]$：

$$\text{offset}(j_1,j_2,\dots ,j_n)=\sum _{k=1}^n{j}_k\cdot \prod _{p=k+1}^n{b}_p$$

严蔚敏教材把它写成 $\text{LOC}(j_1,\dots ,j_n)=\text{LOC}(0,\dots ,0)+\sum _{i=1}^n{c}_i{j}_i$， 其中 $c_n=L$、$c_{i-1}=b_i\times c_i$，并称之为 $n$ 维数组的映像函数。 教材紧接着指出一条重要结论：

"数组元素的存储位置是其下标的线性函数，一旦确定了数组各维的长度，$c_i$ 就是常数。 由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等， 即数组是一种随机存取结构。"

"随机存取"这四个字的准确含义就在这里：不是"可以任意访问"， 而是访问任一元素的时间都相同（$O(1)$），因为地址由下标经一次线性运算算出， 与元素在数组中的位置无关。

三维演算：$A[3][4][5]$ 按行优先存储，每个元素占 2 个存储单元， $\text{LOC}(A[0][0][0])=200$，求 $\text{LOC}(A[2][1][3])$。按"从外层维度向内数"：

• 跨过 $i_1=2$ 个完整的"二维面"，每面 $4\times 5=20$ 个元素 → $2\times 20=40$；
• 在第 2 个面内，跨过 $i_2=1$ 个完整行，每行 $5$ 个 → $1\times 5=5$；
• 在该行内偏移 $i_3=3$ 个。

偏移合计 $40+5+3=48$ 个元素，于是

$$\text{LOC}(A[2][1][3])=200+48\times 2=296$$

自查：数组共 $3\times 4\times 5=60$ 个元素，偏移 48 落在 $[0,59]$ 内，合理； 最后一个元素 $A[2][3][4]$ 的偏移应是 $2\times 20+3\times 5+4=59$ ✓，正好是 $60-1$。

为什么"数组"被放在栈、队列这一章（想弄清大纲编排逻辑就展开）

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

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

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

严蔚敏教材对数组的定义是："一个 $n$ 维数组类型可以定义为其数据元素为 $n-1$ 维数组类型的 一维数组类型。"也就是说，数组是线性表的推广：一维数组是元素为原子的线性表， 二维数组是"元素为一维数组"的线性表，以此类推。

数组还有一条与线性表不同的性质：数组一旦定义，维数和各维的界就不再改变， 因此除了初始化和销毁，数组只有存取元素和修改元素值两种操作，没有插入和删除。 正因为不需要插删，顺序存储是数组最合适的存储方式。

考点速记

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

1. 只有一条方法：先数跨过了多少个完整的行（列），再数本行（列）内还差几个。三维、$n$ 维、压缩存储全是它的实例。
2. 行优先乘列数、列优先乘行数，两个公式完全对偶，记一个就够。
3. 1-base 只影响"数偏移量"这一步，代入前把下标各减 1，公式结构不变。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：最典型的一种是给两个元素的地址，求第三个元素的地址——题面故意不给每行的元素个数。三步走：

1. 把两个已知地址代入行优先公式相减，消掉首地址，得到关于 $n$ 的一元一次方程；
2. 解出 $n$；
3. 再代回去算目标元素。

以"每元素占 1 个单元、$A[0][0]$ 在 100、$A[3][3]$ 在 220，求 $A[5][5]$"为例：$3n+3=120$ 解得 $n=39$，于是 $\text{LOC}(A[5][5])=100+(5\times 39+5)=300$。

易错：把地址差直接除以行数。 $120÷3=40$ 是错的——$A[3][3]$ 不仅跨了 3 行，列方向也跨了 3 列，方程必须写成 $3n+3=120$。

易错：算到目标行的开头就停了。 $A[5][5]$ 不是 $A[5][0]$，第 5 行开头之后还要再加 5 个列偏移。

易错：乘错了那个数。 行优先乘列数、列优先乘行数；反推题里也要看清未知的到底是 $n$ 还是 $m$。

易错：元素大小 $L$ 当成 1。 题面写"每个元素占 4 个存储单元"就必须乘 4，只有明说占 1 个单元才是 1。

教材出处

• 数组的定义（$n$ 维数组类型可定义为数据元素为 $n-1$ 维数组类型的一维数组类型）、 ADT Array 的操作集（只有存取与修改，无插删）、以及"数组一旦被定义， 它的维数和维界就不再改变"：严蔚敏《数据结构（C 语言版）》（第 2 版）p99「4.4.1 数组的定义」
• 4.4.2 数组的顺序存储：以行序为主序 / 以列序为主序两种存储方式（图 4.11）、 $n$ 维数组的映像函数式(4-13)（$c_n=L$，$c_{i-1}=b_i\times c_i$）， 以及"数组元素的存储位置是其下标的线性函数……数组是一种随机存取结构"： 同书 p99–p100

相关知识

特殊矩阵的压缩存储（对称、三角、三对角、稀疏四类的下标推导，全部建立在本篇的地址公式之上）｜ 顺序表（一维数组最直接的应用）｜ 邻接矩阵（无向图的邻接矩阵是对称矩阵，理论上可以压缩）｜ 数组与特殊矩阵的压缩存储（拆分前的旧合并视图）

相关文章

• 栈和队列基本概念
• 顺序栈
• 共享栈
• 链栈
• 链式队列
• 循环队列
• 双端队列
• 应用：括号匹配
• 应用：表达式求值
• 应用：栈在递归中的应用
• 特殊矩阵的压缩存储

真题练习

相关真题（4题）

2021Q32分2020Q12分2018Q32分2016Q42分