408

数据结构

DS-03-03 多维数组的存储（行优先/列优先）

---

一、定位信息

项目	内容
所属圈层	核心层
考点热度	M级（中频常考） — 数组存储地址计算在408选择题中偶有出现，通常2分，主要考查行优先/列优先地址公式的应用
前置知识回顾	需理解"数组"的基本概念（连续存储的线性表），以及基本的地址计算原理（每个元素占 $\text{sizeof(元素类型)}$ 个字节）
知识网络定位	多维数组的存储方式是特殊矩阵压缩存储的基础，理解行优先/列优先的地址映射才能掌握后续的压缩存储下标计算

---

二、知识点讲解

2.1 数组的定义

数组（Array） 是由相同类型的数据元素构成的有限序列，每个元素通过下标唯一标识。

• 一维数组：线性结构，元素按下标线性排列
• 二维数组：可视为"数组的数组"，即每个元素本身是一个一维数组
• $n$ 维数组：递归定义

直观理解：二维数组就是一个表格（矩阵），有行有列。例如 $A_{3 \times 4}$ 是一个3行4列的矩阵，元素 $a_{ij}$ 位于第 $i$ 行第 $j$ 列。

$A_{m \times n} = \begin{pmatrix} a_{00} & a_{01} & \cdots & a_{0,n-1} \\ a_{10} & a_{11} & \cdots & a_{1,n-1} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m-1,0} & a_{m-1,1} & \cdots & a_{m-1,n-1} \end{pmatrix}$

2.2 行优先存储（Row-Major Order）

行优先：将二维数组的元素按行依次存入连续内存。先存第0行，再存第1行，依此类推。

存储顺序：$a_{00}, a_{01}, \ldots, a_{0,n-1}, a_{10}, a_{11}, \ldots, a_{1,n-1}, \ldots$

地址公式（下标从0开始，首地址为 $\text{LOC}(a_{00})$）：

$\text{LOC}(a_{ij}) = \text{LOC}(a_{00}) + (i \times n + j) \times L$

其中 $n$ 为列数，$L$ 为每个元素占用的字节数。

推导：元素 $a_{ij}$ 前面有 $i$ 行完整的元素（每行 $n$ 个），加上当前行中 $j$ 个元素，共 $(i \times n + j)$ 个元素，每个占 $L$ 字节。

示例：$A_{3 \times 4}$（3行4列），$L=4$ 字节，首地址为 100。

• $\text{LOC}(a_{00}) = 100$
• $\text{LOC}(a_{03}) = 100 + (0 \times 4 + 3) \times 4 = 112$
• $\text{LOC}(a_{10}) = 100 + (1 \times 4 + 0) \times 4 = 116$
• $\text{LOC}(a_{23}) = 100 + (2 \times 4 + 3) \times 4 = 144$

2.3 列优先存储（Column-Major Order）

列优先：将二维数组的元素按列依次存入连续内存。先存第0列，再存第1列，依此类推。

存储顺序：$a_{00}, a_{10}, \ldots, a_{m-1,0}, a_{01}, a_{11}, \ldots, a_{m-1,1}, \ldots$

地址公式（下标从0开始）：

$\text{LOC}(a_{ij}) = \text{LOC}(a_{00}) + (j \times m + i) \times L$

其中 $m$ 为行数，$L$ 为每个元素占用的字节数。

推导：元素 $a_{ij}$ 前面有 $j$ 列完整的元素（每列 $m$ 个），加上当前列中 $i$ 个元素，共 $(j \times m + i)$ 个元素。

2.4 下标从1开始的地址公式

若数组下标从1开始（即 $A[1..m][1..n]$），则：

• 行优先：$\text{LOC}(a_{ij}) = \text{LOC}(a_{11}) + [(i-1) \times n + (j-1)] \times L$
• 列优先：$\text{LOC}(a_{ij}) = \text{LOC}(a_{11}) + [(j-1) \times m + (i-1)] \times L$

408考试注意：审题时一定要确认下标是从0还是从1开始，选用对应公式！

2.5 $n$ 维数组的地址计算

设 $n$ 维数组 $A[d_1][d_2] \cdots [d_n]$，每维大小为 $d_1, d_2, \ldots, d_n$，元素 $a_{i_1 i_2 \cdots i_n}$。

行优先（即最后一维变化最快）地址公式：

$\text{LOC}(a_{i_1 i_2 \cdots i_n}) = \text{LOC}(a_{0 \cdots 0}) + \left(\sum_{k=1}^{n-1} i_k \prod_{t=k+1}^{n} d_t + i_n\right) \times L$

此公式在408中很少直接考查高维情况，但理解其推导逻辑有助于应对变式题。

---

三、记忆与理解辅助

技巧1：行优先/列优先口诀

"行优先——行不变列先变，列优先——列不变行先变"

或者：

"行优先按行排，一行存完存下一行；列优先按列排，一列存完存下一列"

技巧2：行优先 vs 列优先对比表

比较项	行优先	列优先
存储顺序	先存完一行，再存下一行	先存完一列，再存下一列
地址公式	$\text{LOC}(a_{00}) + (i \times n + j) \times L$	$\text{LOC}(a_{00}) + (j \times m + i) \times L$
快速访问	按行遍历快（连续存储）	按列遍历快（连续存储）
采用语言	C/C++、Java、Python	Fortran、MATLAB、R
408默认	行优先（C语言风格）	—

技巧3：地址计算通用思路

无论行优先还是列优先，核心思路是：

1. 数前面有多少个元素：按存储顺序，当前元素前面有多少个元素
2. 乘以每个元素的字节数：得到偏移量
3. 加上首地址：得到实际地址

$\text{地址} = \text{首地址} + \text{前面元素个数} \times L$

技巧4：快速验证法

计算完地址后，用特殊位置验证：

• $a_{00}$（或 $a_{11}$）应该等于首地址
• 相邻行同列元素的地址差应为 $n \times L$（行优先）或 $L$（列优先）
• 相邻列同行元素的地址差应为 $L$（行优先）或 $m \times L$（列优先）

---

四、例题与精解

例题1（基础）

题目：已知二维数组 $A[0..5][0..7]$（6行8列）按行优先存储，每个元素占4个字节，首地址为 200。求元素 $A[3][5]$ 的存储地址。

命题意图：考查行优先地址公式的直接应用。

审题分析：

• 已知：下标从0开始，$m=6$，$n=8$，$L=4$，$\text{LOC}(a_{00})=200$
• 求解：$\text{LOC}(a_{35})$

解题思路： 直接代入行优先地址公式。

完整步骤：

$\text{LOC}(a_{35}) = \text{LOC}(a_{00}) + (i \times n + j) \times L$$= 200 + (3 \times 8 + 5) \times 4$$= 200 + 29 \times 4$$= 200 + 116 = 316$

验证：$a_{35}$ 前面有 $3 \times 8 + 5 = 29$ 个元素，每个4字节，偏移116字节，$200+116=316$ ✓

方法反思：代入公式前先确认下标起始值和行列数，避免混淆 $m$ 和 $n$。

例题2（中等）

题目：二维数组 $A[1..10][1..20]$ 按列优先存储，首地址为 1000，每个元素占 8 字节。已知元素 $A[i][j]$ 的地址为 1168，求 $i$ 和 $j$ 的值。

命题意图：考查列优先地址公式的逆向应用（已知地址求下标）。

审题分析：

• 已知：下标从1开始，$m=10$，$n=20$，$L=8$，$\text{LOC}(a_{11})=1000$，$\text{LOC}(a_{ij})=1168$
• 求解：$i$ 和 $j$

解题思路： 列优先、下标从1开始的地址公式为： $\text{LOC}(a_{ij}) = \text{LOC}(a_{11}) + [(j-1) \times m + (i-1)] \times L$

代入已知值，求解方程。

完整步骤：

$1168 = 1000 + [(j-1) \times 10 + (i-1)] \times 8$$168 = [(j-1) \times 10 + (i-1)] \times 8$$(j-1) \times 10 + (i-1) = 168 / 8 = 21$

由于 $1 \leq i \leq 10$，所以 $0 \leq i-1 \leq 9$。

设 $(j-1) \times 10 + (i-1) = 21$，用除法分解：

• $21 \div 10 = 2 \cdots 1$
• 所以 $j-1=2$，$i-1=1$
• 即 $j=3$，$i=2$

验证：$\text{LOC}(a_{23}) = 1000 + [(3-1) \times 10 + (2-1)] \times 8 = 1000 + 21 \times 8 = 1000 + 168 = 1168$ ✓

方法反思：

• 逆向求解的关键是带余除法：总元素序号除以每列元素数得到列偏移，余数为行偏移
• 注意下标从1开始时公式中要减1
• 此类题在408选择题中较常见，建议熟练掌握正向和逆向两个方向的计算

---

五、考情分析

分析维度	内容
考查频次	近5年出现1–2次（选择题为主），属于中低频考点
常见题型	选择题（地址计算、已知地址求下标）
分值占比	通常2分（选择题一道）
命题趋势	单独出题较少，但作为矩阵压缩存储的基础，可能与压缩存储结合考查

注：以上频次基于大纲权重与通用命题规律推测，待真题分析后校准。

---

六、易错点提醒

易错点1

• 错误表现：行优先公式中把 $m$（行数）和 $n$（列数）搞反
• 错误原因：行优先的关键是"一行有多少个元素"即列数 $n$，但容易误用行数 $m$
• 正确做法：行优先公式中的系数是列数 $n$（因为一行有 $n$ 个元素），列优先公式中的系数是行数 $m$（因为一列有 $m$ 个元素）

易错点2

• 错误表现：下标从1开始时忘记减1，直接套用下标从0的公式
• 错误原因：考试中两种下标约定都可能出现，审题不仔细
• 正确做法：看到下标从1开始，公式中必须将 $i$ 替换为 $(i-1)$、$j$ 替换为 $(j-1)$

易错点3

• 错误表现：列优先地址计算时，误将"前面元素个数"算成 $(i \times m + j)$ 而非 $(j \times m + i)$
• 错误原因：与行优先公式混淆
• 正确做法：记住核心原则——"前面有多少个元素"。列优先时，先算前面有多少个完整列（$j$ 列，每列 $m$ 个），再加上当前列中 $i$ 个元素

易错点4

• 错误表现：忽略每个元素占用的字节数 $L$，直接把元素个数当地址偏移
• 错误原因：忘记"地址偏移 = 元素个数 × 每个元素字节数"
• 正确做法：始终区分"元素序号"和"字节偏移"，最终地址 = 首地址 + 元素序号 × $L$

---

七、来源标注

• 依据2026考研统考大纲（408计算机学科专业基础综合）
• 依据《数据结构（C语言版）》严蔚敏版
• 依据《数据结构》王道考研辅导讲义

---