您的位置: 网站首页 > 程序开发 > 数据结构 > 第4章 串、数组和广义表 > 【4.9 广义表的存储表示】

4.9 广义表的存储表示

 

4.9  广义表的存储表示

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

data

link

 

sublist

link

 

tag

sublist/data

link

a)原子节点           b)子表节点                  c)通用节点

4-11  广义表的节点形式

其中,tag域为标志字段,用于区分两类节点。sublistdata域由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域为0link域为空的节点。如图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;                                           /*广义表节点类型定义*/