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

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));  //复制表尾
        }
    }
}

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