5.2　数组的顺序表示和实现

视频二维码（扫码观看）

数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。

问题：计算机的内存结构是一维（线性）地址结构，对于多维数组，将其存放（映射）到内存时，有个次序约定问题。即必须按某种次序将数组元素排成一维序列，然后将这个线性序列存放到内存中。

二维数组是最简单的多维数组，以二维数组为例说明多维数组存放（映射）到内存一维结构时的次序约定问题。

设有二维数组A＝（a_ij）_m×n，如图5-1所示，若每个元素占用的存储单元数为L（个），LOC（i，j）表示元素a_ij的存储位置。a₀₀是二维数组A的基地址。

图5-1　二维数组的表示形式

图5-2　二维数组顺序存储图例形式

图5-2所示，两种顺序存储方式：

①行优先顺序

将数组元素按行排列，第i＋1个行向量紧接在第i个行向量后面。对二维数组，按行优先顺序存储的线性序列为：

a₀₀，a₀₁，…，a_0，n－1，a₁₀，a₁₁，…，a_1，n－1，…，a_m－1，0，a_m－1，1，…，a_{m－1，n－1}

PASCAL、C是按行优先顺序存储的。

②列优先顺序

将数组元素按列向量排列，第j＋1个列向量紧接在第j个列向量之后，对二维数组，按列优先顺序存储的线性序列为：

a₀₀，a₁₀，…，a_m－1，0，a₀₁，a₁₁，…，a_m－1，1，…，a_n－1，0，a_n－1，1，…，a_{n－1，m－1}

FORTRAN是按列优先顺序存储的。

n维数组的数据元素存储位置的计算公式（n维数组的印象函数）为

其中，c_n＝L，c_i－1＝b_i×c_i，1＜i≤n。