数据结构——广义表

介绍

注：广义表的元素既可以是一个元素（原子），也可以又是一个表（子表），（）为原子是空元素，（（））为子表是一个无元素的表

存储结构

对于表节点，需要有个标志域（tag表示他是子表还是原子）、指示表头的指针域（hp指示表内原子的地址）、指示表尾标志域（tp指向表尾，剩下的元素）

对于原子，需要需要有个标志域（tag表示他是子表还是原子）、值（atom）

typedef enum {ATOM, LIST} ElemTag;//ATOM==0：原子；LIST==1：子表
typedef struct GLNode
{ElemTag tag;//公共部分，区分子表和原子union //联合部分，各自特有的{AtomType atom;//原子的值struct{struct GLNode *hp, *tp;}ptr;//ptr是表节点的指针域}
}*GList//整个广义表的头指针

示例

广义表

用上面的存储结构，画出图如下，因为原子没有能力链接下一个元素，所以每个原子都要用一个表节点去指示

但是我们发现这样子很复杂，所以我们可以扩展一下，如下

操作

对于广义表中比较重要的操作：取表头（取表的第一个元素，可以是原子，也可以是子表，输出是元素）、取表尾（除了表头元素剩下的元素组成一个新广义表，输出为广义表）