3.3 数组

几乎所有的程序设计语言都把数组作为其数据类型之一。数学中的矩阵在程序设计中一般都采用数组存储。数组可以看成是线性表的扩充。

3.3.1 数组的逻辑结构

数组（Array）是由 n （ n ＞1）个具有相同数据类型的数据元素组成的有序序列，且该序列必须存储在一块地址连续的存储单元中。数组是把有限个类型相同的变量用一个名字命名，然后用编号区分变量的集合，这个名字称为数组名，编号称为下标，组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。

根据数组要表达含义的多少，区分为一维数组、二维数组或n维数组。假设数组名为 A ，则一维数组定义为A[i]，其中，i是该数组的长度，例如，A[4]表示数组的长度为4，数组中有4个元素，分别是A[0]～A[3]。二维数组定义为A[i , j]，其中，i是第一维的长度，j是第二维的长度，例如，A[2,3]表示数组的第一维长度为2，第二维长度为3，总的长度为2 × 3=6，即有6个数组元素，形象地理解记为2行3列。n维数组定义为A[j ₁ , j ₂ , j ₃ , …, j _n ]，其中，j _i （1≤i≤ n ）表示第i维的长度。

3.3.2 数组的存储结构

数组的存储一般采用顺序分配的原则，即在存储器中开辟一块连续的存储空间，依次存放数组的各个元素。线性表是一个一维表，与线性表不同的是，数组可以是多维的。数组可以看成是线性表的扩充，例如，对于二维数组A[2,3]，理解为2行3列共计6个数据元素，也可以理解为具有两个数据元素的线性表，其中的每个数据元素又是一个由3个数据元素组成的线性表。

3.3.3 数组的运算和应用

定义了数组的维数和各维的长度，系统便为它分配存储空间，因此，只要给出一组下标便可求得相应数组元素的存储位置。由于数组的存储空间是顺序分配的，数组一旦被定义，它的长度和维数就不再改变。

删除数组中的一个数据元素后，所有数据元素都要前移一个数据元素所占的存储空间长度。插入一个数据元素需要将被插入后的所有数据元素向后移动一个数据元素所占的长度。如果插入和删除操作不是在数组的尾部，其运算量是相当大的，数据量比较大时更是如此，因此，数组不宜进行插入和删除操作。

数学中的矩阵在程序设计中一般都采用数组存储。例如，对于2 × 3的矩阵，采用数组存储时，如图3-14所示。