文章目录

  • 9. 广义表 – 广义表概念，存储结构，深度/长度，复制算法
    • 9.1 广义表的基础概念
    • 9.2 广义表的存储结构
    • 9.3 广义表的深度和长度
      • 9.3.1 广义表的长度
      • 9.3.2 广义表的深度
    • 9.4 广义表的复制

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;
  • 例如，广义表 {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;
  • 例如，广义表 {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));//复制表尾}}}

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