9. 广义表 - 广义表概念，存储结构，深度/长度，复制算法

9.1 广义表的基础概念

1 ）什么是广义表

• 广义表，又称列表，也是一种线性存储结构，既可以存储不可再分的元素，也可以存储广义表，记作：LS = (a1,a2,…,an)，其中，LS 代表广义表的名称，an 表示广义表存储的数据，广义表中每个 ai 既可以代表单个元素，也可以代表另一个广义表。

2 ）广义表的原子和子表

• 广义表中存储的单个元素称为 "原子"，而存储的广义表称为 "子表"。
  例如 ：广义表 LS = {1,{1,2,3}}，则此广义表的构成 ：广义表 LS 存储了一个原子 1 和子表 {1,2,3}。
• 广义表存储数据的一些常用形式：
  • A = ()：A 表示一个广义表，只不过表是空的。
  • B = (e)：广义表 B 中只有一个原子 e。
  • C = (a,(b,c,d)) ：广义表 C 中有两个元素，原子 a 和子表 (b,c,d)。
  • D = (A,B,C)：广义表 D 中存有 3 个子表，分别是A、B和C。这种表示方式等同于 D = ((),(e),(b,c,d)) 。
  • E = (a,E)：广义表 E 中有两个元素，原子 a 和它本身。这是一个递归广义表，等同于：E = (a,(a,(a,…)))。

3 ） 广义表的表头和表尾

• 当广义表不是空表时，称第一个数据（原子或子表）为"表头"，剩下的数据构成的新广义表为"表尾"。
• 除非广义表为空表，否则广义表一定具有表头和表尾，且广义表的表尾一定是一个广义表。

9.2 广义表的存储结构

1）存储结构一

• 存储结构一如下示意图所示：表示原子的节点由两部分构成，分别是 tag 标记位和原子的值，表示子表的节点由三部分构成，分别是 tag 标记位、hp 指针和 tp 指针。
  • tag 标记位用于区分此节点是原子还是子表，通常原子的 tag 值为 0，子表的 tag 值为 1；
  • 子表节点中的 hp 指针用于连接本子表中存储的原子或子表；
  • tp 指针用于连接广义表中下一个原子或子表。
    
• 广义表中两种节点的表示代码定义如下：
  定义中使用了 union 共用体，因为同一时间此节点不是原子节点就是子表节点，当表示原子节点时，就使用 atom 变量；反之则使用 ptr 结构体。

typedef struct GNode{
    int tag;         // 标志域, 0表示原子, 1表示子表
    union{
        char atom;   //  原子结点的值域
        struct{
            struct GNode * hp, *tp;
        }ptr;   // 子表结点的指针域, hp指向表头, tp指向表尾
    }subNode;
}GLNode, *Glist;
1
2
3
4
5
6
7
8
9

• 例如，广义表 {a,{b,c,d}} 用该存储结构的存储示意图如下 ：
  
  2）存储结构二
• 另一种存储结构的原子的节点也由三部分构成，分别是 ： tag 标记位、原子值和 tp 指针构成；表示子表的节点由三部分构成，分别是 ： tag 标记位、hp 指针和 tp 指针，示意图如下：
  
• 代码定义如下：

typedef struct GNode {
    int tag;                // 标志域, 0表示原子, 1表示子表
    union {
        int atom;          // 原子结点的值域
        struct GNode* hp;  // 子表结点的指针域, hp指向表头
    }subNode;
    struct GNode* tp;     // 这里的tp相当于链表的next指针, 用于指向下一个数据元素
}GLNode, *Glist;
1
2
3
4
5
6
7
8

• 例如，广义表 {a,{b,c,d}} 用该存储结构的存储示意图如下 ：
  

9.3 广义表的深度和长度

9.3.1 广义表的长度

• 广义表的长度，指的是广义表中所包含的数据元素的个数。
• 计算元素个数时，广义表中存储的每个原子算作一个数据，同样每个子表也只算作是一个数据。
  • LS = {a1,a2,…,an} 的长度为 n；
  • 广义表 {a,{b,c,d}} 的长度为 2；
  • 广义表 {{a,b,c}} 的长度为 1；
  • 空表 {} 的长度为 0。
• 求广义表长度时，两种不同的存储方式求解也有所不同，如下示意图所示：
  
  对于图 1a) 来说，只需计算最顶层（红色标注）含有的节点数量，即可求的广义表的长度。同理，对于图 1b) 来说，由于其最顶层（蓝色标注）表示的此广义表，而第二层（红色标注）表示的才是该广义表中包含的数据元素，因此可以通过计算第二层中包含的节点数量，才可求得广义表的长度。

9.3.2 广义表的深度

• 广义表的深度，可以通过观察该表中所包含括号的层数间接得到，如下示例，该广义表的深度为2。
  

9.4 广义表的复制

• 广义表的复制思想 ： 任意一个非空广义表来说，都是由两部分组成：表头和表尾。反之，只要确定的一个广义表的表头和表尾，那么这个广义表就可以唯一确定下来。因此复制一个广义表，也是不断的复制表头和表尾的过程。如果表头或者表尾同样是一个广义表，依旧复制其表头和表尾。
• 复制广义表的过程，其实就是不断的递归复制广义表中表头和表尾的过程，递归的出口有两个：
  • 如果当前遍历的数据元素为空表，则直接返回空表。
  • 如果当前遍历的数据元素为该表的一个原子，那么直接复制，返回即可
• 实现代码：

// 广义表的复制, C为复制目标广义表，*T为指向复制后的广义表
void copyGlist(Glist C, Glist *T){
    // 如果C为空表，那么复制表直接为空表 
    if (!C) {
        *T=NULL;
    }
    else{
        *T=(Glist)malloc(sizeof(GNode)); // C不是空表，给T申请内存空间
        // 申请失败，程序停止
        if (!*T) {
            exit(0);
        }
        (*T)->tag=C->tag; // 复制表C的tag值
        // 判断当前表元素是否为原子，如果是，直接复制
        if (C->tag==0) {
            (*T)->atom=C->atom;
        }else{  //运行到这，说明复制的是子表
            copyGlist(C->ptr.hp, &((*T)->ptr.hp));  //复制表头
            copyGlist(C->ptr.tp, &((*T)->ptr.tp));  //复制表尾
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

感谢阅读 若有错误 敬请见谅！！！