数组存储

数组是由相同类型的数据元素构成的有限序列。数组元素大小相同，并且在内存中连续存放，所以可以用起始地址和下标直接计算任意元素的地址。

一维数组

设一维数组 A[0...n-1] 的起始地址为 LOC，每个元素占 sizeof(ElemType) 个字节，则：

$$
LOC(A[i]) = LOC + i \times sizeof(ElemType)
$$

若题目没有特别说明，C 语言数组下标从 0 开始；矩阵题中的行号、列号常从 1 开始。做地址映射题时，先看清下标起点。

二维数组

1000

二维数组本质上仍然存入一维连续内存，关键是确定存储顺序。

设二维数组 b[M][N]，每个元素占 d 个字节，下标从 0 开始。

按行优先存储：

$$
LOC(b[i][j]) = LOC + (i \times N + j) \times d
$$

按列优先存储：

$$
LOC(b[i][j]) = LOC + (j \times M + i) \times d
$$

解题要点

地址计算题的核心是“目标元素前面已经存了多少个元素”。

  • 行优先：先数完整的前 i 行，再数当前行前 j 个元素。
  • 列优先：先数完整的前 j 列，再数当前列前 i 个元素。
  • 若题目用 1 起始下标，先把行列号换成偏移量，或直接使用对应的 1 起始公式。

常见易错点

  • 不要把矩阵的数学下标和 C 数组下标混用。
  • M 是行数，N 是列数；行优先公式中一整行有 N 个元素。
  • “连续存储”意味着随机访问地址可直接计算，但插入、删除整行或整列不一定方便。