广义表头尾链表存储结构_C语言：数据结构-广义表的存储结构

广义表相对于线性表﹑数组﹑串等线性结构是较为复杂的结构，其元素可以具有不同的结构(可以是原子，也可以是列表)，通常采用链式结构存储广义表。

(1)表头、表尾链式存储

链式结构中用结点储存列表中的数据元素，用指针的链接体现数据元素间的关系。由于数据元素可能是列表或原子，所以必须设置两类结点。

结点表示，如图5-15所示。

(a)表结点；(b)原子结点

表结点包含3个域：

1.标志域：tag=1，表明该结点是表结点。

2.表头指针域：hp，指向该结点表示的子表的表头。

3.表尾指针域：tp，指向该结点表示的子表的表尾。

原子结点包含2个域 ：

1.标志域：tag=0，表明该结点是表结点。

2.值域：atom，存放原子的值。

其表示方法为：任意广义表都由表头和表尾组成，所以都能用一个表结点表示。表头可能是原子，也可能是广义表。表尾一定是广义表或空表，所以能用一个表结点表示或表明其是空表。

结点的类型定义

typedef struct GLNode{int tag; /*广义表结点的成员,用于区分原子结点、表结点*/union{ atomtype atom; /*atom 是广义表原子结点的成员*/struct {struct GLNode *hp, *tp;}ptr; /*ptr是广义表表结点的成员,它包含两个指向广义 表结点类型的指针hp﹑tp*/}qf ; /*qf是联合体,是广义表结点的成员。当tag=1,其成员 项为ptr, tag=0 成员项为atom*/}* Glist; /*是指向广义表结点类型的指针类型，用于说明广义 表结点类型的指针变量*/}

例5.13 设广义表C=(a,(b,c,d),e)，用表头、表尾存储法画出结构图。

分析：如图5-16所示，广义表C由表头(原子a)和表尾广义表((b,c,d),e))组成；表((b,c,d),e))由表头广义表(b,c,d)和表尾广义表(e)组成；(e)由表头e(原子)和空表组成；(b,c,d)由表头原子b和表尾(c,d)组成；(c,d)由表头c(原子)和表尾(d)组成；(d)由表头d(原子)和空表组成。

(2)同层存储所有兄弟的扩展链式存储

在这种存储方式中，同样设置两类结点：表结点和原子结点。与第一种方式不同的是该种存储方式中的表结点和原子结点都有一个指针指向同一层中下一个元素结点的指针。该指针类似于单向链表中的next指针，把同一层的元素结点链接到一起。

结点表示，如图5-17所示。

(a)表结点；(b)原子结点

表结点包含3个域：

1.标志域：tag=1，表明该结点是表结点。

2.指针域hp：指向该结点表示的子表的表头。

3.指针域tp：指示同层下一个元素结点。

原子结点包含3个域：

1.标志域：tag=0，表明该结点是原子。

2.原子结点的值域：atom。

3.指针域tp：指示同层下一个元素结点。

其表示方法为：表头可能是原子，也可能是表。表结点和原子结点的指针域tp都指示同一层的下一个元素结点。

例5.14 设广义表C=(a,(b,c,d))，用第二种(同层存储所有兄弟的扩展链式)存储结构画出结构图，如图5-18所示。

分析：c是一个列表，其表头为原子a，a同层的下一个元素结点为列表(b,c,d)。列表(b,c,d)的表头为原子b，原子b的同层的元素为原子c和和原子d。

例5.15 设广义表D=( A , B , C ) ，A=( )，B=( e )，C=( a, ( b,c ) )。用第二种存储结构画出结构，如图5-19所示。

分析：D是列表，D的表头是列表A。A的表头是空，列表A的下一个元素结点为列表B。B的表头是原子e，列表B的下一个元素结点为列表C。C的表头是原子a，a的下一个元素结点为列表(b,c)。列表(b,c)的表头是原子b，(b,c)的下一个元素结点为空。原子b的下一个元素结点为原子c，c的下一个元素结点为空。

结点类型定义

typedef struct lnode{ int tag; /*广义表结点的成员,用于取分原子结点﹑表结点 */union{ elemtype data; /*原子结点的值域*/struct lnode *hp; /*指向表结点的表头指针*/}val; /*联合体, tag=0，其成员项为data;tag=1，成员项为表头指针*/struct lnode *link; /*指向同层相邻元素的指针*/}gnode,

(3)算法举例

例5.16 求广义表的长度(以第二种方式存储，同层存储所有兄弟)

int length (gnode *h){ int n=0; gnode *h1;h1=h->val.hp;while (h1 ! = NULL){ n+ +;h1=h1->link ;}return n;}

程序中，h是广义表的头指针，语句h1=h->val.hp;的功能是把广义表的表头指针赋给h1，h1指向表结点的表头，通过循环语句遍历单向链表。n作为计数器，每遍历一个结点加1，直到h1为空。n中是广义表的长度。

如图5-20所示，设有广义表D=( A , B , C, d, f )，A=( )，B=( e )，C=( a, (b,c ) )，以第二种方式同层存储所有元素，运行结果为n=5。