首页 计算机科学 数据结构 广义表

# 广义表

1. 定义

广义表是 n (n≥0) 个数据元素 a1，a2，…，ai，…，an 的有序序列，一般记作：
LS＝(a1，a2，…，ai，…，an)
其中：
・LS 是广义表的名称，n 是它的长度。
・每个 ai (1≤i≤n) 是 LS 的成员，它可以是单个元素，也可以是一个广义表，分别称为广义表 LS 的原子和子表。习惯上，用大写字母表示广义表的名称，用小写字母表示原子。
・当广义表 LS 非空时，称第一个元素 a1 为 LS 的表头 (head)，称其余元素组成的表 (a2，…，ai，…，an) 为 LS 的表尾 (tail)。

D=() 空表；其长度为零。
A=(a，(b，c)) 表长度为 2 的广义表，其中第一个元素是单个数据 a，第二个元素是一个子表(b，c)。
B=(A，A，D) 长度为 3 的广义表，其前两个元素为表 A，第三个元素为空表 D。
C=(a，C) 长度为 2 递归定义的广义表，C 相当于无穷表 C=(a，(a，度为 2 递归定义的广义表，C 相当于无穷表 C=(a，(a，(a，(…))))。
head( A)= a;表 A 的表头是: a
tail( A)=(( b,c));表 A 的表尾是(( b,c))。
广义表的表尾一定是一个表。

2. 储存结构

由于广义表 GL=(d1 ,d2 ,d3 ,…, dn) 中的数据元素既可以是单个元素，也可以是 子表，因此对于广义表来说，难以用顺序存储结构来表示它，通常用链式存储结构 来表示。

1) 广义表的头尾链表存储结构

typedef enum {ATOM, LIST} ElemTag; /* ATOM＝0，表示原子；LIST＝1，表示子表 */
typedef struct GLNode{
    ElemTag tag; /* 标志位 tag 用来区别原子结点和表结点 */
	union{
        AtomType atom; /* 原子结点的值域 atom*/
		struct {
            struct GLNode * hp, *tp;
        } htp; /* 表结点的指针域 htp，包括表头指针域 hp 和表尾指针域 tp*/
	} atom_htp; /* atom_htp 是原子结点的值域 atom 和表结点的指针域 htp 的联合体域 */
} GLNode，*GList;

A=(a,(b,c)) 例子：

2) 广义表的同层结点链存储结构

typedef enum {ATOM,LIST} ElemTag; /* ATOM＝0，表示原子；LIST＝1，表示子表 */
typedef struct GLNode{
	ElemTag tag;
	union{
		AtomType atom;
		struct GLNode * hp; /* 表头指针域 */
		} atom_hp; /* atom_hp 是原子结点的值域 atom 和表结点的表头指针域 hp 的联合体域 */
	struct GLNode * tp; /* 同层下一个结点的指针域 */
} GLNode，*GList;

3. 运算

广义表有两个重要的基本操作，即取头操作 (GetHead ()) 和取尾操作 (GetTail ())：
・取表头 GetHead (LS)：取出的表头为非空广义表的第一个元素，它可以是一个原子，也可以是一个子表。
・取表尾 GetTail (LS)：取出的表尾为除去表头之外，由其余元素构成的表。即表尾一定是一个广义表。

-->