广义表的表示方法

一、头尾链表存储

广义表结点的分类

1. 表结点：标志域、指示表头的指针域和指示表尾的指针域

2. 原子结点：标志域和值域

一对确定的表头和表尾可唯一确定列表

typedef enum{ATOM, LIST} ElemTag;
typedef struct GLNode {
    ElemTag tag;
    union {
        AtomType atom; // 原子结点的值域
        struct {struct GLNode *hp, *tp;} ptr; // 表结点的指针域
    };
} *GList;

二、扩展线性链表存储

与上述方法的不同点：原子结点也有三个域。

typedef enum{ATOM, LIST} ElemTag;
typedef struct GLNode {
    ElemTag tag;
    union { // 两种结点的联合部分
        AtomType atom; // 原子结点的值域
        struct GLNode *hp; // 表结点的表头指针
    };
    struct GLNode *tp; /// 指向下一个结点的指针
} *GList;

注意：广义表E(a, E)的深度是无穷。因为它自己是自己的一个元素。