数组

未完成

本页面内容有待补充。

定义

1. 数组，是由相同类型的元素的集合所组成的数据结构，
2. 数组可以是多维的，多维数组可以看成是线性表的推广。
3. 数组一旦被定义，维数和维界就不再改变。因此对于一个初始化完成的数组，允许的操作只有存取元素，修改元素和摧毁整个数组。

表示

由于数组的元素个数和关系在初始化后固定，因此使用顺序存储结构。

一维数组的存放毫无疑问，而多维数组存储时就需要将数组“展开”。以二维数组为例，一个$i$行$j$列的二维数组有两种存储方式，其区别为主序的选择。以列序为主序，意味着先存储$n$列上的元素，$a_{00}, a_{10}, a_{20}...$，反之为行序作为主序，即$a_{01}, a_{02}, a_{03}...$。在C语言中，使用的是行序为主序的存储结构。

确定了数组的维数和各个维的长度，就可以分配空间。反之，给出一组下标，就可以得到对应数组元素的存储位置。

因此一个二维数组中的数据元素$a_{ij}$的存储位置如下所示，其中$LOC(0,0)$即基址， $m$是第二维的长度：

$$LOC(i, j) = LOC(0, 0) + (m * i + j) L$$

推广到n维数组：

$$LOC(j_1, j_2, j_3..., j_n) = LOC(0, 0, ..., 0) + \sum_{i=1}^{n} c_ij_i$$

其中$c_i$在数组各维的长度确认后确定不变。数组元素的存储位置是其下标的线性函数。

代码实现：