1.数组定义

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

• 一维数组是有序的元素序列，二维数组可以理解为数组元素是一维数组的数组，类推可以得到n维数组是每个元素均为n-1维数组的一维数组
• 多维数组通常用来存储结构比较复杂的相关联数据

数组一旦被定义，其维数和维界就不再改变，因此除了结构体的初始化和销毁外，数组只会进行存取元素和修改元素的操作（最常见的两种操作是查找和修改）。

一个基本的数组的逻辑结构如下

ADT 数组（Array）
Data
    数组的元素类型定义为ElementType，假设数组元素的下标范围为[0, MaxSize-1]
    数组的实际长度定义为Length（表示数组中已存储的元素个数）
Operation
    InitArray(&arr): 初始化一个空数组
    DestroyArray(&arr): 销毁数组，释放相关内存空间
    GetLength(arr): 返回数组的实际长度
    IsEmpty(arr): 判断数组是否为空，若为空则返回1，否则返回0
    ClearArray(&arr): 将数组清空，将长度设置为0
    GetElement(arr, i): 返回数组中第i个元素的值
    SetElement(&arr, i, e): 设置数组中第i个元素的值为e
    InsertElement(&arr, i, e): 在数组的第i个位置插入元素e
    DeleteElement(&arr, i): 删除数组中第i个位置的元素
    Traverse(arr, visit): 遍历数组的所有元素，依次调用visit函数进行访问
endADT

2.多维数组详解

对于k维数组，每个元素都受到k个线性关系的约束，比如m行n列的二维数组

其中每个元素均被两个线性关系约束：

• 第j列上，除第一个结点外aij的直接前驱为ai-1,j，除最后一个结点外aij的直接后继为ai+1,j；
• 第j列上，除第一个结点外aij的直接前驱为ai,j-1，除最后一个结点外aij的直接后继为ai,j+1；

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

由于计算机的内存结构都是一维的，因此在存储多维数组时，需要将数组中的所有元素按某种次序排成一个线性序列，然后将其按顺序存储到内存中。一般来说，数组不执行删除和插入操作，所以通常采用顺序存储方法来存储数组。多维数组通常有两种存储方式：行优先存储和列优先存储。下面将以二维数组(矩阵)为例说明这两种存储方式。

2.1 行优先存储

基本思想是按行存储，即存储完第i行再接着存储第i+1 行。如存储二维数组 Amn，按行优先顺序存储的线性序列为

二维数组以及其按行优先存储的示意图如下

二维数组中任意一个元素aij，其前面共有(i-1)*n+j-1个元素。设a11在内存中的地址为Loc(a11)，每个数组元素占c个存储单元，则aij的地址为

在C++、PASCAL等语言中数组都是按行优先存储。

2.2 列优先存储

基本思想是按列存储，即存储完第j列再接着存储第j+1列。如存储二维数组Amn，按列优先顺序存储的线性序列为

二维数组以及其按列优先存储的示意图如下

对于二维数组中的任意一个元素aij，其前面共有i-1+m*(j-1)个元素。设a11在内存中的地址为Loc(a11)，每个元素占c个存储单元，则aij的地址为

在FORTRAN语言中数组按列优先存储。