空间数据结构复习（二）

2.广义表的存储结构：

原子：可以是任何在结构上不可分割的元素。

广义表： 简称列表（Lists），是零个或多个有序序列，广义表的元素或者为原子或者为广义表，广义表记为 LS=(x₀,x₁,x₂,···,x_n-1) ,其中，x_i称为表元素。

作为广义表中元素的广义表被称为子表，为了区分原子和子表，有如下书写上的约定：用大写字母表示表或子表，用小写字母表示原子。

一个广义表中所包含的元素（包括原子和子表）个数称为该广义表的长度。长度为0的表是空表。

综上所述，广义表有下列重要的性质：

（1）广义表的元素可以是原子，也可以是子表，而子表的元素还可以是子表······因此广义表是一种多层次的数据结构。当用圆括号表示广义表的时候，一个表的深度是指表中所包含的括号层数。例如一个空表E=(),其深度就是1，A=(x,L)=(x,(a,b))的深度就为2。

（2）广义表可以是递归的表，广义表的定义并没有限制元素的递归，即广义表也可以是自身的子表，例如D=(z, D)这种形式。

（3）广义表可以为其它表所共享，这一点非常的好理解，就是一个表可以是另一个表的子表。

（4）广义表可以看成是线性表的推广，而线性表是广义表的特例。即深度为1的广义表。

（5）如果规定任何表都是有名的表，则为了既标明每个表的名字，又说明它的组成，可以将表的名字写在本表对应的括号前，即可以省略等号，如下：L=(a, b)可以写成L(a,b)。

编者补充：

由于我们是考前抱佛脚，所以解释一下什么是线性表。

线性表是n（n >= 0)个元素 a₀,a₁,···,a_n-1 的有限序列，记为：(a₀,a₁,···,a_n-1)。其中，n 是线性表中元素的个数，即线性表的长度。当n = 0时，为空表。

设 a_i 是表中第 i 个元素， i = 0,1,2,3···,n - 1,我们常称 a_i 是 a_i+1的直接前驱元素 ，a_i+1 是 a_i的直接后驱元素。

一般地，线性表中的元素具有相同的类型，它们可以是简单类型，如整数，也可以是结构类型。

线性表是一种动态数据结构，它的表长可以变化。在线性表上可以执行元素访问和修改运算，也可以在表中任何位置执行和删除元素的运算。

与堆栈和队列相同，线性表有两种典型的存储表达方式：顺序表示和链接表示。

（1）用一维数组存储线性表称为线性表的顺序表示，顺序表示的线性表称为顺序表。

线性表的顺序实现可以用下面C语言结构定义：

 typeof struct list{
    int Size,MaxList;
    T Elements[MaxSize];
 } List;

在上面定义的结构类型List中,Size是线性表的长度，MaxList为表的最大允许长度。一维数组Elements用以存放线性表中的元素，实现线性表的顺序存储。

（2）线性表的链接表示：单链表、双向链表存储线性表称为线性表的链接存储表示。

线性表的链接实现可以用下面C语言结构定义：

    typeof struct node {
        T Elements;
        struct node* Link;
    } Node;
    typeof struct List {
        Node *First;
        int Size;
    } List;

上面定义的结构类型List中，First为指向单链表头结点的指针。特别注意在链接表示下，可以不设线性表的长度限制，只要用于动态存储分配的堆得空间未用完，总可以创建单链表的新结点。

下面要注意一个辅助函数的使用，我们需要知道指向单链表中位置为pos的结点的指针，那么这个函数作用就是返回这个指针：

    Node *set_pos(List lst, int pos) {
        int i;
        Node q = lst.First; /*使指针q指向起始结点*/
        for(i=0;i<pos;i++) q = q -> Link; /*令指针q向后移动pos次，指向位置为pos的结点*/
        return q;
    }

此处编者认为在定义这个函数时不一定要用上述所用到的Node *，其实我们在平时时使用int *来定义这个函数时也不会报错，但是，这里是为了规范，因为这里返回的结果q为Node型指针。

接着回到广义表，广义表的第一个元素称为头部，其余元素组成的表是广义表的尾部。

广义表的存储表示：由于广义表的数据元素可以是原子，也可以是广义表。因此它难以用顺序存储结构表示，通常采用链接存储结构表示。一种做法是将结点分成两类：原子结点和子表结点，每类结点都有三个域，其中有一个标志域Tag,它等于0时表示该结点是原子结点，Tag = 1表示该结点是子表结点，原子结点包括Tag、Atom、Tp域。子表结点包括Tag、Hp、Tp域。Tp域是原子结点和子表结点共有的，它是指向广义表的尾部指针。原子结点的域Atom中存放原子的值，子表结点的域Hp指示子表的头部。