5.1.2　数组的顺序表示和实现

通常对数组只作随机访问元素和修改元素值操作，不作插入和删除操作。这样，数组建立后，其数组元素个数和元素间的关系不再发生变动，因此一般采用顺序存储结构表示数组。

对于一个有n个数据元素的一维数组，其任意一个数据元素ai的存储地址为

其中，LOC（a0）是下标为0的数组元素的内存单元地址，也称为基址；h是每个数据元素占用的存储单元数。

对于一个m行n列的二维数组，其数据元素的存储地址与其存储方式有关。由于计算机的内存单元是以一维形式组织的，这样就存在二维如何向一维映射的问题，即数组元素是以行序为主序，还是以列序为主序存放。以行序为主序存放就是指先存放第0行，紧接着存放第1行……最后存放第m－1行。即二维数组的数据元素的排列次序为

以行序为主序存放二维数组元素，其任意一个数据元素aij的存储地址为

其中，LOC（a00）为基址；h是每个数据元素占用的存储单元数。

以列序为主序存放就是指先存放第0列，紧接着存放第1列……最后存放第n－1列。即二维数组的数据元素的排列次序为

以列序为主序存放二维数组元素，其任意一个数据元素aij的存储地址为

其中，LOC（a00）为基址；h是每个数据元素占用的存储单元数。

同理，可推出三维或更高维数组中的元素的存储地址计算公式。

当数组的基址确定以后，其他任意元素的存储地址就可以通过式（5－1）、式（5－2）和式（5－3）计算出来。由于计算数组中每个元素存储位置的时间相等，所以存取数组中任意一个元素的时间也相等，即数组是随机存取的存储结构。

由于C等大多数程序设计语言采用的是以行序为主序的存储方式，因此如果不作特殊声明，本书采用以行序为主序的存储方式。

说明：只要知道以下三要素便可随时求出任一元素的地址（意义：数组中的任一元素可随机存取）：

（1）开始结点的存放地址（即基地址）；

（2）维数和每维的上、下界；

（3）每个数组元素所占用的单元数。