数组

Breeze Shane大约 2 分钟

数组是由 $n(n\geq1)$ 个相同类型的数据元素构成的有限序列，每个数据元素成为一个数组元素，每个元素在 $n$ 个线性关系中的序号称为该元素的下标，下标的取值范围成为数组的维界。

数组与线性表的关系：

提示

数组一旦被定义，其维数和维界就不再改变。因此除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作。

数组的存储结构

逻辑意义上的数组可采用大多数计算机语言所提供的数组类型进行存储，一个数组的所有元素在内存中占用一段连续的存储空间。

以一维数组A[0...n-1]为例，其存储结构关系式为

\mathrm{LOC}(a_i) = \mathrm{LOC}(a_0) + i \times L \quad (0 \leq i < n)

其中， $L$ 是每个数组元素所占的存储单元。

而对于多维数组，有两种映射方法：按行优先和按列优先。

按行优先存储的基本思想是：先行后列，先存储行号较小的元素，行号相等的情况下先存储列号较小的元素。

设二维数组的行下标与列下标的范围分别为 $[0, h_1]$ 与 $[0, h_2]$ ，则存储结构关系式为：

\mathrm{LOC}(a_{i,j}) = \mathrm{LOC}(a_{0,0}) + [i \times (h_2 + 1) + j] \times L

按列优先存储的基本思想是：先列后行，先存储列号较小的元素，列号相等的情况下先存储行号较小的元素。

设二维数组的行下标与列下标的范围分别为 $[0, h_1]$ 与 $[0, h_2]$ ，则存储结构关系式为：

\mathrm{LOC}(a_{i,j}) = \mathrm{LOC}(a_{0,0}) + [j \times (h_1 + 1) + i] \times L