4.9 广义表的存储表示

4.9  广义表的存储表示

广义表通常用链式存储结构进行存储，链表中的每个节点对应广义表中的一个元素。对于原子元素，节点形式如图4-11（a）所示，其中，data域存放原子值，link是指针域，指向下一个元素。对于子表元素，节点形式如图4-11（b）所示，其中，sublist和link都是指针域，前者为子表，后者指向下一个元素。为了使子表和原子两类节点既能在形式上保持一致，又能进行区别，可采用如图4-11（c）所示的通用节点形式。

（a）原子节点           （b）子表节点                  （c）通用节点

图4-11  广义表的节点形式

其中，tag域为标志字段，用于区分两类节点。sublist或data域由tag决定。若tag=0，表示该节点为原子节点，则第二个域为data，存放相应原子元素的信息；若tag=1，表示该节点为表节点，则第二个域为sublist，存放相应子表第一个元素对应节点的地址。link域存放与本元素同一层的下一个元素所在节点的地址，当本元素是所在层的最后一个元素时，link域为NULL。例如，前面的广义表C的存储结构如图4-12所示，它称为带表头节点的广义表的链式存储结构。

图4-12  广义表C的存储结构

对于上述存储结构，主要分为两种情况。

（1）为广义表时，用头节点的sublist域指向第一个元素，例如，在图4-13中，（a）为空表的情况；（b）为具有n个元素的非空表的情况。

（2）为原子时，不再有头节点，只有一个tag域为0，link域为空的节点。如图4-14是原子'a'。严格地讲，这不能称为广义表，但在特殊情况下会出现这种情况，如求广义表“(a,b)”的表头时，返回的结果就是这种情况。

图4-13  广义表的两种基本情况

图4-14  为原子时的情况

采用C/C++语言描述节点的类型，可用如下定义：

typedef struct lnode

{

    int tag;                                        /*节点类型标识*/

    union

    {  

        ElemType data;

        struct lnode *sublist;

    }val;

    struct lnode *link;                             /*指向下一个元素*/

} GLNode;                                           /*广义表节点类型定义*/