数组是 n (n＞1)个相同类型数据元素a0、a1、…、an－1构成的有限序列,且该有限序列存储在一块地址连续的内存单元中。几乎所有的高级程序设计语言都支持数组数据类型。
数组这种数据结构把逻辑上相邻的数据元素存储在物理上相邻的存储单元中，如要保存一个学生所学五门课程的成绩，可以定义一个一维数组A[5]，则该数组一共有A[0]、A[1]、A[2]、A[3]和A[4]五个元素(对于任一元素，用A[i]表示，i称为下标值)，分别保存该学生五门课程的成绩。设第一个元素A[0]在内存的存储起始地址为2000，每个数组元素在内存中占4个存储单元，该数组在内存的存储实现如图5.1所示。由此可见，一个一维数组，一旦第一个元素a[0]的存储地址 LOC(a[0])确定，每个数据元素在内存所占用的存储单元个数 k也确定，则任一数据元素a[i]的存储地址 LOC(a[i])可由以下公式求出：
LOC(a[i])=LOC(a[0])＋i×k （0≤i＜n)

???????
????????????????? ??? 图5.1 一维数组A[5]的存储示意图???
在一维数组的基础上，我们可以引入多维数组。如要保存3个学生每人考4
门功课的成绩，可以定义一个二维数组B[3][4]，则该数组有B[0][0]、B[0][1]、B[0][2]、B[0][3]、B[1][0]、B[1][1]、B[1][2]、B[1][3]、B[2][0]、B[2][1]、B[2][2]、B[2][3]共12个元素，其中B[0][0]保存第1个学生所学第1门课程的成绩，B[0][1]保存第1个学生所学第2门课程的成绩……B[2][3]保存第3个学生所学第4门课程的成绩。由于计算机的存储结构是线性的，用线性的存储结构存放二维数组元素则存在行/列次序排放问题。对二维数组B[3][4]，如果按图5.2所示的方式存储，称为以行序为主序的存储方式，即先存储第0行，再存储第1行……每行中的元素是按列下标由小到大的次序存放；如果按图5.3所示的方式存储，称为以列序为主序的存储方式，即先存储第0列，再存
储第1列……每列中的元素是按行下标由小到大的次序存放。大多数程序设计语言如C、PASCAL、BASIC等采用的都是以行序为主序的存储方式，少数程序设计语言如FORTRAN中采用的是以列序为主序的存储方式。

???????????????? 图5.2以行序为主序存储的二维数组

?? 图5.3以列序为主序存储的二维数组
??? 对于一个以行序为主序方式存储的二维数组a[m]n，若第一个元素a[0][0]的存储地址LOC(a[0][0])确定，每个数据元素在内存所占用的存储单元个数 k也确定。由于在内存中，数组元素a[i][j]前面已存放了i行(第0行至第i-1行)，即已存放了i×n个元素，占用了i×n×k个内存单元；第i行中a[i][j]元素前又已存放了j列，即已存放了j个数据元素(元素a[i][0]至元素a[i][j-1])，占用了j×k个内存单元。该数组是从地址LOC(a[0][0])开始存放的，因此数组元素a[i][j]的存储地址LOC(a[i][j])可由以下公式求出：
LOC(a[i][j])=LOC(a[0][0])＋i×n×k+j×k
而在以列序为主序方式存储的二维数组a[m][n]中的任一数组元素a[i][j]的存储地址 LOC(a[i][j])可由以下公式求出：
LOC(a[i][j])=LOC(a[0][0])＋j×m×k+i×k
由上面分析我们知道，数组中的每个数据元素都和一组惟一的下标值对应，而数组中任一数据元素的存储地址可通过下标值直接计算得到，因此，数组是一种随机存储结构，可通过给定下标值随机存取数组中的任意数据元素，这就给程序设计带来很大方便。
但是，用数组存放数据时，必须事先定义固定的长度(即数组元素的个数)。比如，要保存一个班级的学生某一门课程的成绩，可以采用一维数组，但有的班级有可能有100人，而有的班可能只有30人，如果要用同一个数组先后存放不同班级的学生成绩，则必须定义长度为100的数组。如果事先难以确定一个班的最多人数，则必须把数组定得足够大，以便能存放任何班级的学生数据。显然这将会浪费内存。因此，在有些情况下，要根据需要开辟内存单元来保存数据，链表就是一种可以动态地进行存储分配的数据结构。
转载自：http://public.whut.edu.cn/comptsci/web/data/511.htm