数据结构：数组和广义表

我们之前讨论的线性结构，比如顺序表、链表、栈、队列和字符串，表中的元素都只能是单个数据元素，而不能是具有某种结构的数据。其实，在众多的数据结构中，还有一类线性结构其数据元素可以是具有某种结构的数据。比如，我们今天要讨论的数组和广义表，它们都可以看成是对线性表的一种扩充。

一、数组

1.1、定义

数组是由类型相同的数据元素构成的有序集合。数组中的每个元素受n（n>=1）个线性关系的约束，每个元素在n个线性关系中的序号$i_1$，$i_2$，…，$i_n$称为该元素的下标，可以通过下标访问该数据元素。

数组可以看成是线性表的推广，其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。例如，一维数组可以看成是一个线性表，二维数组可以看成数据元素是线性表的线性表。如下图所示的二维数组可以看成一个线性表：

其中，每个数据元素$a_i$是一个行向量形式的线性表：

$$a_i=(a_{i0},a_{i1},...,a_{i,n-1}) \quad 0<=i<m-1$$

或者$a_j$是一个列向量形式的线性表：

$$a_j=(a_{0j},a_{1j},...,a_{m-1,j}) \quad 0<=j<n-1$$

在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，

typedef ElemType Array2[m][n];

等价于：

typedef ElemType Array1[n];
typedef Array1 Array2[m];

同理，一个n维数组类型可以定义为其数据元素为n−1维数组类型的一维数组类型。

1.2、存储结构

数组一般不做插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。因此，采用顺序存储结构表示数组比较合适。

由于存储单元是一维的结构，而数组可能是多维的结构，则用一组连续存储单元存放数组的数据元素就有次序约定问题。通常地，对二维数组可有两种存储方式，一种是以行序为主序的存储方式：

另一种是以列序为主序的存储方式：

对于数组，一旦规定了其维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置。下面仅用以行序为主序的存储结构为例予以说明。假设，数组中每个数据元素占L个存储单元，则二维数组A[0… m−1, 0… n−1]（即下标从0开始，共有m行n列）中任一元素$a_{ij}$的存储位置可由下式确定：

$$Loc(i,j)= Loc(0,0) + (n*i+j)*L$$

其中，Loc(i,j)是$a_{ij}$的存储位置；Loc(0,0)是$a_{00}$的存储位置，即二维数组A的起始存储位置，也称为基地址或基址。

1.3、特殊矩阵的压缩存储

矩阵是很多科学与工程计算问题中研究的数学对象，矩阵用二维数组来表示是最自然的方法。但是，在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有很多值相同的元素或者是零元素。有时为了节省存储空间，可以对这类矩阵进行压缩存储。

所谓压缩存储，是指为多个值相同的元只分配一个存储空间，对零元不分配空间。

特殊矩阵，是指矩阵中值相同的元素或者零元素的分布有一定规律。特殊矩阵主要包括对称矩阵、三角矩阵和对角矩阵等，下面我们重点讨论这三种特殊矩阵的压缩存储。

1.3.1、对称矩阵

若n阶矩阵A中的元满足下述性质：

$$a_{ij}=a_{ji} \quad(1<=i,j<=n)$$

则称其为n阶对称矩阵。

对于对称矩阵，可以为每一对对称元分配一个存储空间，则可将$n^2$个元压缩存储到n(n+1)/2个元的空间中，不失一般性，可以行序为主序存储其下三角（包括对角线）中的元。

假设以一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵$a_{ij}$之间存在着一一对应的关系：

$$k = \begin{cases} \frac{i(i-1)}{2}+j-1\quad当i>=j \\ \frac{j(j-1)}{2}+i-1\quad当i<j \end{cases}$$

对于任意给定的一组下标(i,j)，均可在sa中找到矩阵元$a_{ij}$；反之，对所有的k=0，1，2，…，$\frac{n(n+1)}{2}-1$，都能确定sa[k]中的元在矩阵中的位置(i,j)。由此，称sa[n(n+1)/2]为n阶对称矩阵A的压缩存储。

1.3.2、三角矩阵

以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。上三角矩阵是指矩阵下三角（不包括对角线）中的元均为常数c或零的n阶矩阵，下三角矩阵与之相反。对三角矩阵进行压缩存储时，除了和对称矩阵一样，只存储其上（下）三角中的元素之外，再加一个存储常数c的存储空间即可。

在上三角矩阵中，sa[k]和矩阵元$a_{ij}$之间的对应关系为：

$$k = \begin{cases} \frac{(i-1)(2n-i+2)}{2}+j-i\quad当i<=j \\ \frac{n(n+1)}{2}\quad当i>j \end{cases}$$

在下三角矩阵中，sa[k]和矩阵元$a_{ij}$之间的对应关系为：

$$k = \begin{cases} \frac{i(i-1)}{2}+j-1\quad当i>=j \\ \frac{n(n+1)}{2}\quad当i<j \end{cases}$$

1.3.3、多对角线矩阵

在多对角线矩阵中，所有非零元都集中在以主对角线为中心的带状区域中，即除了主对角线上和直接在对角线上、下方若干条对角线上的元之外，所有其他的元皆为零，如下图所示。

二、广义表

广义表，也称列表，它是线性表的推广。线性表的元素仅限于原子项，即每个数据元素只能是一个数或一个记录，如果放松对线性表的这种限制，允许它们自身具有结构，由此就产生了广义表的概念。

广泛地用于人工智能等领域的表处理语言LISP语言，把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。

2.1、定义

广义表是由n个元素组成的有限序列，一般记作

$$LS=(a_1,a_n,...,a_n)$$

其中，LS是广义表($a_1$,$a_2$,…,$a_n$)的名称，n是其长度。在线性表的定义中，$a_i$(1<=i<=n)只能是单个元素；而在广义表的定义中，$a_i$可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表。习惯上，用大写字母表示广义表的名称，用小写字母表示原子。

广义表的定义是一个递归的定义，因为在描述广义表时又用到了广义表的概念。下面，列举一些广义表的例子。

• A=()，A是一个空表，其长度为0。
• B=(e)，B只有一个原子e，其长度为1。
• C=(a, (b, c, d))，C的长度为2，两个元素分别为原子a和子表(b, c, d)。
• D=(A, B, C)，D的长度为3，3个元素都是广义表。显然，将子表的值代入后，则有D=((), (e), (a, (b, c, d)))。
• E=(a, E)，E的长度为2，它是一个递归的表，相当于一个无限的广义表E=(a, (a, (a, …)))。

从上述定义和例子可推出广义表的如下3个重要结论。

• 广义表的元素可以是子表，而子表的元素还可以是子表……由此，广义表是一个多层次的结构，可以用图形象地表示。例如，下图表示的是广义表D，图中以圆圈表示广义表，以方块表示原子。

  

• 广义表可为其他广义表所共享。例如在上述例子中，广义表A、B和C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。

• 广义表可以是一个递归的表，即广义表也可以是其本身的一个子表。例如，表E就是一个递归的表。

由于广义表的结构比较复杂，其各种运算的实现也不如线性表简单，其中，最重要的两个运算如下。

• 取表头GetHead(LS)：取出的表头为非空广义表的第一个元素，它可以是一个单原子，也可以是一个子表。
• 取表尾GetTail(LS)：取出的表尾为除去表头之外，由其余元素构成的表。即表尾一定是一个广义表。

例如：

• GetHead(B)=e
• GetTail(B)=()
• GetHead(D)=A
• GetTail(D)=(B, C)

由于(B, C)为非空广义表，则可继续分解得到：

• GetHead(B, C)=B
• GetTail(B, C)=©

这里需要注意的是，广义表( )和(( ))不同。前者为空表，长度n=0；后者长度n=1，可分解得到其表头、表尾均为空表( )。

2.2、存储结构

由于广义表中的数据元素可以有不同的结构（或是原子，或是列表），因此难以用顺序存储结构表示，通常采用链式存储结构。常用的链式存储结构有两种，头尾链表的存储结构和扩展线性链表的存储结构。

2.2.1、头尾链表的存储结构

由于广义表中的数据元素可能为原子或广义表，因此需要两种结构的结点：一种是原子结点，用以表示原子；一种是表结点，用以表示广义表。其中，一个原子结点由2个域组成：标志域和值域；一个表结点由3个域组成：标志域、指示表头的指针域和指示表尾的指针域。它们的结构如下图所示，其中tag是标志域，值为0时表示结点是原子，值为1时表示结点是子表。对于一个非空的广义表来说，它可以被分解成表头和表尾，因此，一对确定的表头和表尾可唯一确定广义表。

在C语言中，广义表的头尾链表存储结构的类型描述如下：

// ATOM==0:原子
// LIST==1:子表
typedef enum{ATOM,LIST} ElemTag;

// 广义表类型
typedef struct GLNode {
    // 公共部分，用于区分原子结点和表结点
    ElemTag tag;
    
    // 原子结点和表结点的联合部分
    union {
        // atom是原子结点的值域，AtomType由用户定义
        AtomType atom;
        // ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾
        struct {
            struct GLNode *hp, *tp;
        }ptr;
    };
}*GList;

前面列举的广义表的例子，它们的头尾链表存储结构是这样的：

说明：

• 除空表的表头指针为空外，对于任何非空广义表来说，其表头指针均指向一个表结点，且该结点中的hp域指示广义表表头（或为原子结点，或为表结点），tp域指向广义表表尾（除非表尾为空，则指针为空，否则必为表结点）。
• 在这种存储结构中，易分清广义表中原子和子表所在层次。比如，在广义表D中，原子a和e在同一层次上，而b、c和d在同一层次且比a和e低一层，B和C是同一层的子表。
• 最高层的表结点个数即为广义表的长度。

2.2.2、扩展线性链表的存储结构

在这种结构中，无论是原子结点还是表结点均由三个域组成，其结点结构如下图所示：

前面列举的广义表的例子，它们的扩展线性链表存储结构是这样的：

三、小结

数组可以看成是线性表的推广，其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。一个n维数组实质上是n个线性表的组合，其每一维都是一个线性表。数组一般采用顺序存储结构，因为物理存储是一维的，故存储多维数组时，应先将其转换为一维结构（按行转换或按列转换）。科学与工程计算中的矩阵通常用二维数组来表示，为了节省存储空间，对于几种常见形式的特殊矩阵，比如对称矩阵、三角矩阵和对角矩阵，在存储时可进行压缩存储，即为多个值相同的元只分配一个存储空间，对零元不分配空间。

广义表是另一种线性表的推广形式，表中的元素可以是称为原子的单个元素，也可以是一个子表。线性表可以看成广义表的特例，表中的元素都是称为原子的单个元素。。广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。广义表的常用操作有取表头和取表尾。广义表通常采用链式存储结构：头尾链表的存储结构和扩展线性链表的存储结构。

四、参考

《数据结构（C语言版 第2版）》

《数据结构 自考02331》