1.2.3　数组和广义表

1.数组的定义

数组应是读者十分熟悉的数据类型，几乎所有的高级程序设计语言都支持数组这种数据类型，在前面讨论的各种线性表结构的顺序存储结构时都是借用一维数组来描述的。数组本身也是一种数据结构，一维数组是一种顺序表结构，多维数组是一种特殊的线性结构，是线性表的推广。基于二维数组的应用十分广泛，像数学中的矩阵、生活中常见的报表都是二维数组，因此，二维数组是我们学习的重点。

数组是由同种类型的数据元素构造而成的。数组中的每个数据元素都对应一组下标，每个数据元素在数组中的相对位置是由其下标来确定的。数组中的数据元素可以是整数、实数等简单类型，也可以是数组等构造类型。

（1）一维数组

一维数组中的每个数据元素只需由一个下标确定。若把一维数组中数据元素的下标顺序看成是线性表中的序号，则一维数组就是一个线性表。

（2）二维数组

二维以上的数组称为多维数组。多维数组实际上是用一维数组实现的。映射后，多维数组每个数组元素所占用的存储大小与相应一维数组中数组元素所占的存储大小相同，多维数组第一个元素对应到相应一维数组的第一个元素位置。只要能计算出多维数组中数组元素在相应一维数组中的位置，就可以直接按此位置存取相应一维数组中的数组元素。

当一个数组中的每个数组元素都含有两个下标时，该数组称为二维数组。如一个m×n阶的矩阵是一个二维数组，如图1-27所示。可把一个二维数组看成是一个线性表，该线性表中的每个数组元素都是一个一维数组。

（3）n维数组

类似于二维数组，当一个数组中的每一个数组元素都含有n个下标时，该数组称为n维数组。同样，可以把一个n维数组看成是一个线性表，该线性表中的每个数组元素都是一个n-1维数组。这样，n维数组可以看作是线性表的推广。

2.数组的顺序存储结构

数组的顺序存储结构方式，就是将数组元素顺序地存放在一片连续的存储单元中。

（1）一维数组

①一维数组的存储：定义一个一维数组为具有相同数据类型n（n≥0）个元素的有限序列，其中的n称为数组长度或数组大小，若n=0则为空数组。各数组元素处于一个线性聚集或线性表中。对于一维数组，数组元素是依照次序顺序存放的。

②一维数组元素地址的计算：对于一维数组a[n]，假设该数组的每一个元素占有一个存储单元。数组的起始地址为L0，则第i（0≤i≤n-1）个元素的存储地址为Loc（a[i]）=L0+i，如图1-28所示。

若数组a[n]中的每一个数据元素占用L个存储单元，那么a[i]的存储地址为Loc（a[i]）=L0+i×L，其中0≤i≤n-1。

③一维数组的特点：除第一个元素外，其他每个元素有且仅有一个直接前驱；除最后一个元素外，其他每一个元素有且仅有一个直接后继。

（2）二维数组

①二维数组的存储：二维数组的顺序存储方式存在两种可能性，一种称为“行优先顺序”，是将数据元素以行为主顺序存放在存储空间中。以行为主顺序存放的例子有高级语言Pascal、C、C++和BASIC等。

具体来说，二维数组以行为主的顺序存储，就是将数组的元素按照行的升序次序，一行接一行地顺序存储到一块连续存储空间中，即先存储第一行数据元素，再存储第二行数据元素，依此类推。每行中的数组元素，从左到右顺序存储。这样得到的数组元素是存于一维数组的一种线性序列：

a[0][0]，a[0][1]，…，a[0][m-1]，a[1][0]，a[1][1]，…，a[1][m-1]，…，a[n-1][0]，a[n-1][1]，…，a[n-1][m-1]

另一种顺序存储方式称为“列优先顺序”，是以列为主把数据元素顺序存放在存储空间中。如FORTRAN高级语言就是以列为主顺序存放的。

二维数组以列为主的顺序存储是将数组中的元素按照列的升序次序，一列一列地顺序存储到一块连续存储空间中，即先存储第一列，再存储第二列，依此类推。每列中的数组元素，从上到下顺序存储。这样得到的数组元素是存于一维数组的另一种线性序列：

a[0][0]，a[1][0]，…，a[n-1][0]，a[0][1]，a[1][1]，…，a[n-1][1]，…，a[0][m-1]，a[1][m-1]，…，a[n-1][m-1]

二维数组两种存储方式的图例如图1-29所示。

②二维数组元素地址的计算：假设数组a[m][n]是按行为主顺序存储的，每一个数组元素占有L个存储单元。定义Loc（a11）为第一个元素a11在存储器中的地址，那么数组中任一元素aij，即在第i行、第j列的数组元素所在的存储地址的计算公式为：

Loc（a[i][j]）=Loc（a11）+（（i-1）×n+j-1）×L　（1≤i≤m，1≤j≤n）

如果定义Loc（a00）为第一个元素a00在存储器中的地址，那么上式可改写为：

Loc（a[i][j]）=Loc（a00）+（i×n+j）×L　（0≤m-1，0≤n-1）

③多维数组元素地址的计算：三维数组的元素地址的计算与二维数组类似，即三维数组的元素a[m][n][p]可以看成是一个含有m个n×p的二维数组的数组。这样给定了数组第一个元素的起始地址及每个元素所占用的存储单元数，就不难推出任一元素的存储地址。

多于三维的数组的元素地址的计算，可以从上面的三维数组的元素地址的计算中类似地推算出来。各维元素个数为m1，m2，m3，…，mn，下标为i1，i2，i3，…，in的数组元素的存储地址为：

3.矩阵

矩阵是科学与工程计算问题中常用的数学对象之一。

（1）矩阵的存储

①矩阵的二维数组描述：用高级语言编写程序时，通常用二维数组来描述矩阵，可以对其元素进行随机存取，各种矩阵运算也非常简单。有的程序设计语言中还提供了各种矩阵运算，用户使用时都很方便。

②矩阵的压缩存储：在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，为了节省存储空间，可以对这类矩阵进行压缩存储，即为多个相同的非零元素分配存储空间，而对零元素则不分配空间。

（2）特殊矩阵

所谓特殊矩阵，是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。

①对称矩阵：

a.对称矩阵的定义：在一个n阶方阵A中，若元素满足下述性质

aij=aji　（0≤i，j≤n-1）

则称A为对称矩阵。

【例1-4】图1-30所示即是一个5阶对称矩阵。

b.对称矩阵的压缩存储：对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样能节约近一半的存储空间。

●　按“行优先顺序”存储主对角线（包括对角线）以下的元素：即按a00，a10，a11，…，an−1，0,−an-1，1,…,an-1，n-1次序存放在一个向量中（下三角矩阵中，元素总数为n（n+1）/2）。其中：

●　元素aij的存放位置：aij元素前有i行（从第0行到第i-1行），元素一共有：

1+2+…+i=i×（i+1）/2

在第i行上，aij之前恰有j个元素（即ai0，ail，…，ai，j-1），因此有：

●　aij和sa[k]之间的对应关系为：

若i≥j，则k=i×（i+1）/2+j，0≤k<n（n+1）/2。

若i＜j，则k=j×（j+1）/2+i，0≤k<n（n+1）/2。

令I=max（i，j），J=min（i，j），则k和i，j的对应关系可统一为：

k=I×（I+1）/2+J　0≤k<n（n+1）/2

c.对称矩阵的地址计算公式为：

Loc（aij）=Loc（sa[k]）=Loc（sa[0]）+k×d=Loc（sa[0]）+[i×（i+1）/2+j]×d

通过下标变换公式，能立即找到矩阵元素aij在其压缩存储表示sa中的对应位置k。因此是随机存取结构。

【例1-5】a21和a12均存储在sa[4]中，这是因为：

k=i×（i+1）/2+j=2×（2+1）/2+1=4

②三角矩阵：

a.三角矩阵的划分：以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。

●　上三角矩阵：如图1-31（a）所示，它的下三角（不包括主对角线）中的元素均为常数C或者零。

●　下三角矩阵：与上三角矩阵相反，它的主对角线上方均为常数C或者零，如图1-31（b）所示。

b.三角矩阵的压缩存储：三角矩阵中的重复元素C可共享一个存储空间，其余的元素正好有n×（n+1）/2个，因此，三角矩阵可压缩存储到向量中，其中C存放在向量的最后一个分量中。

●　上三角矩阵中aij和sa[k]之间的对应关系：三角矩阵中，主对角线之上的第p行（0≤p<n）恰有n-p个元素，按行优先顺序存放上三角矩阵中的元素aij时，aij元素前有i行（0行到第i-1行），一共有（n-0）+（n-1）+（n-2）+…+（n-i+1）=i×（2n-i+1）/2个元素。

在第i行上，aij之前恰有j-i个元素（aij，ai，j+l，…，ai，j-1），因此有：

sa[i×（2n-i+1）/2+j-i]=aij

所以：

●　下三角矩阵中aij和sa[k]之间的对应关系为：

注意：三角矩阵的压缩存储结构是随机存取结构。

③对角矩阵：所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零的矩阵为对角矩阵。

【例1-6】图1-32　（a）是对角矩阵的一般情形，图1-32（b）给出了一个三对角矩阵。

其中：非零元素仅出现在主对角线上（aii，0≤i≤n-1），紧邻主对角线上面的那条对角线上（ai，i+1，0≤i≤n-2）和紧邻主对角线下面的那条对角线上（ai+1，i，0≤i≤n-2）。当|i-j|>1时，元素aij=0。

由此可知，一个k对角线矩阵（k为奇数）A是满足下述条件的矩阵：

●　若|i-j|>（k-1）/2，则元素aij=0。

●　对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到

每个非零元素和向量下标的对应关系。

（3）稀疏矩阵

设矩阵Am×n中有S个非零元素，若S远远小于矩阵元素的总数（即S<<m×n），则称A为稀疏矩阵。

①稀疏矩阵的压缩存储：为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。其中每个非零元素所在的行号、列号和值组成一个三元组（i，j，aij），并由此三元组唯一确定。稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储方法。

②三元组表：将表示稀疏矩阵的非零元素的三元组按行优先（或列优先）的顺序排列（跳过零元素），并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表。

注意：以下的讨论中，均假定三元组是按行优先顺序排列的。

a.三元组表的类型说明：为了运算方便，将矩阵的总行数、总列数及非零元素的总数均作为三元组表的属性进行描述。其类型描述为：

b.压缩存储结构上矩阵的转置运算：一个m×n的矩阵A，它的转置矩阵B是一个n×m的矩阵，且：

A[i][j]=B[j][i]　0≤i<m，0≤j<n

即A的行是B的列，A的列是B的行。

●　三元组表表示的矩阵转置的思想方法：

第一步：根据A矩阵的行数、列数和非零元总数确定B矩阵的列数、行数和非零元总数。

第二步：当三元组表非空（A矩阵的非零元素不为0）时，根据A矩阵三元组表的结点空间data（以下简称三元组表），将A的三元组表a->data置换为B的三元组表b->data。

●　三元组表的转置：

方法一：简单地交换a->data中i和j中的内容，得到按列优先顺序存储到b->data；再将b->data重排成按行优先顺序的三元组表。

方法二：由于A的列是B的行，因此按a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先存放的。

按这种方法设计的算法的基本思想是：对A中的每一列col（0≤col≤a->n-1），通过从头至尾扫描三元组表a->data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b->data中，即可得到B的按行优先的压缩存储表示。

●　具体算法如下：

●　算法分析：该算法的时间主要耗费在col和p的二重循环上。

若A的列数为n，非零元素个数为t，则执行时间为O（n×t），即与A的列数和非零元素个数的乘积成正比。通常用二维数组表示矩阵时，其转置算法的执行时间是O（m×n），它正比于行数和列数的乘积。由于非零元素个数一般远远大于行数，因此上述稀疏矩阵转置算法的时间大于通常的转置算法的时间。

③带行表的三元组表：为了方便某些矩阵运算，在按行优先存储的三元组表中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。这就是带行表的三元组表。

a.类型描述如下：

b.带行表的三元组表的操作：

●　对于任意行号i（0≤i≤m-1），能迅速地确定该行的第一个非零元在三元组表中的存储位置为RowTab[i]。

●　RowTab[i]（0≤i≤m-1）表示第i行之前的所有行的非零元数。

●　第i行上的非零元数目为RowTab[i+1]-RowTab[i]（0≤i≤m-2）。

●　最后一行（即第m-1行）的非零元数目为t-RowTab[m-1]（t为矩阵的非零元总数）。

注意：若在行表中令RowTab[m]=t（要求MaxRow>m）会更方便些，且t可省略。带行表的三元组表可改进矩阵的转置算法，具体参阅其他参考书。

④稀疏矩阵压缩存储方式分析：

a.三元组表和带行表的三元组表的特点：相应的算法描述较为简单，但这类顺序存储方式对于非零元的位置或个数经常发生变化的矩阵的运算就显得不太适合。

【例1-7】执行将矩阵B相加到矩阵A上的运算时，某位置上的结果可能会由非零元变为零元，但也可能由零元变为非零元，这就会引起在A的三元组表中进行删除和插入操作，从而导致大量结点的移动。对此类运算采用链式存储结构为宜。

b.稀疏矩阵的链式结构：稀疏矩阵的链式结构有十字链表等方法，适用于非零元变化大的场合，比较复杂，可参阅其他参考书。

4.广义表

广义表是线性表的一种推广和扩充，是应用范围十分广泛的数据结构。

（1）广义表的定义

广义表是n（n＞0）个元素的有限序列，记为A=（a1，a2，…，ai，…，an），其中A是表名，n是广义表的长度，即广义表中元素的个数，元素ai是广义表中的数据元素。

（2）广义表中的单元素、子表（表元素）及深度

广义表中的元素ai可以是单元素，也可以是表，称为子表或表元素。为了区别单元素和子表，习惯上用小写字母表示单元素，用大写字母表示子表。广义表中括号嵌套的最大层数称为广义表的深度。

（3）广义表的特点

①广义表是一种递归的数据结构：广义表的定义是递归的，显然在定义广义表时又引用了广义表的概念。

②广义表的存储空间很难确定：由于广义表是一种递归数据结构，因此很难确定它所占用的存储空间的大小，故一般采用链接存储结构对其进行存储。

（4）广义表的一些例子

下面给出广义表的一些例子：

①A=（）：A是空表，长度为0，深度为1，可以写成A（）。

②B=（e）：B的长度为1，只含单元素e，深度为1，可以写成B（e）。

③C=（a，（b，c））：C的长度为2，深度为2，C中有两个元素，分别为单元素a和子表（b，c），可以写成C（a，（b，c））。

④D=（A，B，C）=（（），（e），（a，（b，c）））：D的长度为3，深度为3，每个元素都是一个子表，可以写成D（A，B，C）。

⑤E=（a，E）：E是一个长度为2的递归表，相当于E=（a，（a，（a，（a，…）））的无限表，可以写成E（a，E）。

⑥F=（（a，（b，c），（（a，b），c）））：F是一个长度为1，深度为4的广义表。

（5）广义表的存储结构

①广义表的存储结构方式：一般采用链接存储结构对广义表进行存储。广义表中的元素分单元素和子表两种，因此需要两种结构的结点，分别表示子表和单元素。为此广义表的存储结构，应包括以下部分：

a.一种带标志域tag的结点。在广义表中设立一个标志域tag。当tag=0时，表示该结点为广义表的单元素；当tag=1时，表示该结点为广义表的子表，在结点中的data域存放该子表头结点地址；当tag=-1时，约定是表头结点的标志域。

b.为了方便进行广义表的插入、删除操作，有时在表头增加一个空结点。该表头结点的结构与其他结点相同。为了把表头结点同一般结点区分开，约定表头结点的标志域tag=-1。

设指针first_p指向子表中的第一个结点，指针next_p指向下一个结点，则广义表的结点结构如图1-33所示。

②广义表的图形表示：为把广义表中各元素间的次序和层次表示得更为清晰，可在广义表的图形表示方式中，用横向箭头表示元素之间的次序，用竖向箭头表示元素之间的层次关系，如图1-34所示。图中的例子与上面介绍的“广义表的一些例子”中的①、②、③、⑤一一对应。