第5章数组和广义表
5.1复习笔记
一、数组
1．数组的基本概念
（1）数组的结构
数组分为逻辑结构和存储结构，在计算机语言中实现数组是采用连续的存储单元集合。从逻辑结构上看，数组是一个二元组（index，value）的集合，对于每个index，都有一个value值与之对应。index称为下标，可以由一个整数、两个整数或多个整数构成，下标含有d（d≥1）个整数称为维数是d。
（2）数组的分类
数组按维数可分为一维数组、二维数组和多维数组。
①一维数组
一维数组A是由n（n＞1）个相同类型的数据元素a1、a2、…、a n构成的有限序列，其逻辑表示为A=（a1，a2，…，a n），其中，A是数组名a i（1≤i≤n）为数组A的第i个元素。
②二维数组
一个二维数组可以看作是每个数据元素都是相同类型的一维数组的一维数组。
③多维数组
任何多维数组都可以看作是一个线性表，这时线性表中的每个数据元素也是一个线性表。多维数组是线性表的推广。一个d维数组中含有b1×b2×…×b d（假设第i维的大小为b i）个数据元素，每个元素受到d个关系的约束，且这d个关系都是线性关系。当d=1时，
d维数组就退化为定长的线性表，当d＞1时，d维数组也可以看成是线性表的推广。例如，图5-1所示的二维数组的逻辑关系用二元组表示如下：
图5-1一个二维数组
其中含有12个元素，这些元素之上有两种关系，r1表示行关系，r2表示列关系，r1和r2均为线性关系。
（3）数组的特点
①数组中的各元素具有统一的类型。
②d（d≥1）维数组中的非边界元素具有d个前趋元素和d个后继元素。
③数组维数确定后，数据元素个数和元素之间的关系不再发生改变，特别适合于顺序存储。
④每组有意义的下标都存在一个与其相对应的数组元素值。抽象数据类型的d维数组的定义如下：
（4）C++中数组的定义方式
①静态数组：在定义数组时指定其大小，如“int a[2][3]；”定义一个2行3列的整型数组。静态数组的空间大小是固定的。
②动态数组：在程序运行时通过new分配其空间，如“int*b；”定义一个指针，在运行时通过“b=new int[10]；”语句分配一个大小为10的整型动态数组b，在不需要时通过“delete[]b；”语句收回其空间。
2．数组的存储结构
数组通常采用顺序存储方式实现。
（1）一维数组的存储结构
一维数组的所有元素依逻辑次序存放在一片连续的内存存储单元中，其起始地址为第一个元素a1的地址，即LOC（a1）。假设每个数据元素占用k个存储单元，则任一数据元素a i的存储地址LOC（a i）可以由以下公式求出：
LOC（a i）=LOC（a1）+（i-1）×k(2≤i≤n)
该式说明一维数组中的任一数据元素的存储地址可直接计算得到，即一维数组中的任一数据元素可直接存取，因此一维数组具有随机存储特性。同样，二维及多维数组也满足随机存储特性。
（2）多维数组的存储结构
对于d（d≥2）维数组，其数据元素的存储必须约定存放次序（即存储方案），这是因为存储单元是一维的（计算机的存储结构是线性的），而数组是d维的。通常，存储方案有以下两种：
①以行序为主序（C／C++、C++、Pascal、Basic等语言采用）。
②以列序为主序（Fortran语言采用）。
（3）二维数组存储结构的分析
下面以二维数组为例进行讨论。对于一个m行n列的二维数组A m×n，有：
①以行序为主序
若采用以行序为主序的存储方式，即先存储第1行，接着存储第2行，…，最后存储第m行。此时，二维数组的线性排列次序为：
如果已知第一个数据元素a1,1的存储地址LOC（a1,1）和每个数据元素所占用的存储单元数k后，则该二维数组中的任一数据元素a1,1的存储地址可由下式确定：
在内存中，数组的a1,1元素前已存放了i-1行，即已存放了（i-1）×n个元素，占用了（i-1）×n×k个内存单元；在第i行中，a1,1前有j-1个元素，即已存放了j-1个数据元素，占用了（j-1）×k个内存单元；并且，该数组是从基地址LOC（a1,1）开始存放的。所以，数组元素a1,1的内存地址为上述三部分之和。
②以列序为主序
若采用以列序为主序的存储方式，即先存储第1列，然后接着存储第2列，…，最后存储第n列。此时，二维数组的线性排列次序为：
同理，可推出在以列序为主序的计算机系统中有：
可以得知：类似于一维数组，一旦二维数组的下标值确定，数据元素类型确定，对应数组元素的存储位置也就可以确定，即二维数组也具有随机存储特性。上述推导公式和结论可推广至三维甚至多维数组中。
③二维数组的存储
在更一般的情况下，假设二维数组的行下界是c1，行上界是d1，列下界是c2，列上界
是d2，即数组，则式
可改写为：
式
可改写为：
对于C++语言中的三维数组A[d1，d2，d3]（即，假设每个元素存储一个存储单元，采用以行序为主序的存储方式，可以看成d1个d2×d3的二维0数组。如果要计算A[i，j，k]的地址，首先确定a[i，0，0]的地址为LOC（A[0，0，0]）+i×d2×d3，因为这个元素之前共有i个二维数组，即有i×d2×d3个存储单元，再根据上述二维数组的定位，求得A[i，j，k]的地址为LOC（A[0，0，0]）+i×d2×d3+k。
对于C++语言中的n（n＞3）维数组A[d1，d2，…，d n]，假设每个元素存储一个存储
单元，计算A[i1，i2，…，i n]的地址。即先求A[i1，0，…，0]的地址为
，再求得A[i1，i2，0，…，0]的地址为
，重复该过程，直到求得A[i1，i2，…，i n]的地址为
