广义表

广义表一般记作：LS=（a1,a2,…)

其中ai在线性表中只可以是单个元素，而在广义表中即可以是单个元素，也可以是广义表。如果是单个元素，叫做原子，如果是广义表，叫做子表。当广义表非空时，第一个元素叫做广义表的表头，其余所有元素组成的表叫做广义表的表尾。

例如： A（），空表

B（e) 只有一个原子元素e,长度为1

c（a,(b,c,d)) 长度是2

d( a ( d)) 递归表

• 广义表的储存结构

通常用链式存储结构

每个节点有tag域（标志域），hp，tp三个域，但是原子节点（就是表头节点）只有两个域，标志域和值域

定义：

struct glnnode
{
    int tag;//表示是原子节点还是表结点
    union
    {
        int atom;//原子节点值域
        struct ptr
        {
            glnnode *hp,*tp;
        };
    };
};

除了空表表头指针为空外，其他表表头指针必定指向一个表节点

同一层次的表可以从第一个节点通过尾节点依次往后数，而头结点则指向一个原子节点或者是一个子表。

例如，画出c表的表示

| | | 代表tag， 头结点，尾结点

c-> 1| | | -> 1| | NULL
    |      |  
    ->0|a|   ->1| | |->1| | |->1| |NULL
             |     |     |
             ->0|b|->0|c|->0|c|