数据结构——广义表

标签：元素表头原子 tag 广义子表数据结构

广义表的概念

广义表（又称列表Lists）是n>=0个元素a0，a1，...，an-1的有限序列，其中每一个ai可以是原子，或者是一个广义表。

广义表和线性表的区别：线性表的元素是单一的类型，而广义表的元素可以是不同类型，其元素也可以是一个广义表（子表）。

广义表通常记作:LS=(a1，a2，...，an）其中: LS为表名，n为表的长度，每一个 ai为表的元素。
习惯上，一般用大写字母表示广义表，小写字母表示原子。
表头：若LS非空（n>=1）则其第一个元素a1就是表头。记作head（LS）= a1 注：表头可以是原子，也可以是子表。
表尾：除表头之外的其他元素组成的表。记作tail（LS）= （a2，...，an）。注：表尾不是最后一个元素，而是一个子表。

广义表的性质

（1）广义表中的数据元素有相对次序；一个直接前驱和一个直接后继。

（2）广义表的长度定义为最外层所包含元素的个数；

如：C = （a，（b，c））是长度为2的广义表。

（3）广义表的深度定义为该广义表展开后所包含括号的重数；

注意：“原子”的深度为0，“空表”的深度为1。

（4）广义表可以为其他广义表共享；如：广义表B就共享表A，在B中不必列出A的值，而是通过表名来引用，B = （A）。

（5）广义表可以是一个递归的表，如：F = （a1，F）这种把自身当作元素的广义表

注意：递归表的深度是无穷值，长度是有限值。

（6）广义表是多层次结构，广义表的元素可以是单元素，也可以是子表，而子表还可以是子表，...。可以用图形象地表示。

广义表和线性表的区别

广义表可以看成是线性表的推广，线性表是广义表的特例。
广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。
当二维数组的每行(或每列)作为子表处理时，二维数组即为一个广义表。
另外，树和有向图也可以用广义表来表示。
由于广义表不仅集中了线性表、数组、树和有向图等常见数据结构的特点，而且可有效地利用存储空间，因此在计算机的许多应用领域都有成功使用广义表的实例。

广义表的基本运算

（1）求表头GetHead（L）：非空广义表的第一个元素，可以是一个原子，也可以是一个子表

（2）求表尾GetTail（L）:非空广义表的除去表头元素以外其它元素所构成的表。表尾一定是一个表

广义表的存储结构

1）存储结构一

存储结构一如下示意图所示：表示原子的节点由两部分构成，分别是 tag 标记位和原子的值，表示子表的节点由三部分构成，分别是 tag 标记位、hp 指针和 tp 指针。

（1）tag 标记位用于区分此节点是原子还是子表，通常原子的 tag 值为 0，子表的 tag 值为 1；
（2）子表节点中的 hp 指针用于连接本子表中存储的原子或子表；
（3）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;

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;

广义表的复制

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

实现代码：

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

标签：元素,表头,原子,tag,广义,子表,数据结构
From： https://blog.csdn.net/weixin_74209413/article/details/142523747