13.2.2 数组

数组是顺序存储结构的典型代表。它的关键优势是随机访问：只要知道首地址、元素长度和下标，就能直接算出元素地址。

一维数组地址

若一维数组首元素 A[0] 地址为 a，每个元素占 L 个存储单元，则：

$$Loc(A[i])=a+i\times L$$

若下标从 1 开始，首元素 A[1] 地址为 a：

$$Loc(A[i])=a+(i-1)\times L$$

这就是数组读取第 $i$ 个元素为 $O(1)$ 的根本原因。

二维数组：先想“前面已经存了多少元素”

二维数组要转成一维连续空间存储。地址计算的核心不是背公式，而是数清楚目标元素之前已经存了多少个元素。

设数组为 A[m][n]，即 $m$ 行 $n$ 列，每个元素长度为 $L$，首地址为 $a$，下标从 0 开始。

按行优先：

$$Loc(A[i][j])=a+(i\times n+j)\times L$$

解释：前面有 i 整行，每行 n 个元素；当前行前面还有 j 个元素。

按列优先：

$$Loc(A[i][j])=a+(j\times m+i)\times L$$

解释：前面有 j 整列，每列 m 个元素；当前列前面还有 i 个元素。

下标从 1 开始时

若二维数组行列下标均从 1 开始，数组为 $A[1..m][1..n]$：

按行优先：

$$Loc(A[i][j])=a+((i-1)\times n+(j-1))\times L$$

按列优先：

$$Loc(A[i][j])=a+((j-1)\times m+(i-1))\times L$$

考试题经常通过下标起点设坑。看到 A[1..m,1..n] 与 A[0..m-1,0..n-1]，公式里的偏移量不同。

方阵中行优先与列优先的特殊比较

课程用 $n\times n$ 方阵讨论：何时同一个元素在按行和按列存储时偏移量相同？

下标从 1 开始时：

按行偏移元素个数：

$$(i-1)n+(j-1)$$

按列偏移元素个数：

$$(j-1)n+(i-1)$$

令二者相等：

$$(i-1)n+(j-1)=(j-1)n+(i-1)$$

整理可知，当 $i=j$ 时一定相等，也就是主对角线元素在行优先和列优先下偏移相同。题目也可以用特殊值验证，例如 A[1][1] 必然都是第一个元素。

地址计算做题流程

flowchart TD
  A["读题"] --> B["确认下标从 0 还是 1 开始"]
  B --> C["确认数组维度：m 行 n 列"]
  C --> D["确认按行优先还是按列优先"]
  D --> E["计算目标元素前面的元素个数"]
  E --> F["乘以元素长度 L"]
  F --> G["加首地址 a"]

本节例题

单选

二维数组 $A[1..m][1..n]$ 按行优先存储，每个元素长度为 $L$，首地址为 $a$，则 $A[i][j]$ 的地址为：

Aa+(i*n+j)*LBa+((i-1)*n+(j-1))*LCa+((j-1)*m+(i-1))*LDa+(j*m+i)*L

自查清单

1. 能否不背公式，直接数出目标元素前面有多少元素？
2. 能否区分下标从 0 与从 1 开始的公式？
3. 能否解释方阵主对角线元素为什么行优先和列优先偏移相同？