;
◆ 其余元素组成的子表称为表尾;(a2,a3,…,an)
◆ 广义表中所包含的元素(包括原子和子表)的个数称为表的长 度。
◆ 广义表中括号的最大层数称为表深 (度) 广义表的元素可以是原子项,也可以是子表,子表的元素又可以是子表, …。即广义表是一个多层次的结构。表5-2中的广义表D的图形表示如图5-12所示。
广义表可以被其它广义表所共享,也可以共享其它广义表。广义表共享其它广义表时不必列出子表的值,而是通过表名引用。如:D=(A,B,C)
广义表本身可以是一个递归表。如:E=(a,E)
根据对表头、表尾的定义,任何一个非空广义表的表头可以是原子,也可以是子表, 而表尾必定是广义表。
广义表的存储结构
由于广义表中的数据元素具有不同的结构,通常用链式存储结构表示,每个数据元素用一个结点表示。因此,广义表中就有两类结点:
◆ 一类是表结点,用来表示广义表项,由标志域,表头指针域,表尾指针域组成;
◆ 另一类是原子结点,用来表示原子项,由标志域,原子的值域组成。如图5-13所示。
只要广义表非空,都是由表头和表尾组成。即一个确定的表头和表尾就唯一确定一个广义表。
相应的数据结构定义如下:
typedef struct GLNode
{ int tag ; /* 标志域,为1:表结点;为0 :原子结点 */
union
{ Atomtype atom; /* 原子结点的值域 */
struct
{ struct GLNode *hp , *tp ;
}ptr ; /* ptr和atom两成员共用 */
}Gdata ;
} GLNode ; /* 广义表结点类型 */