本文共 1615 字，大约阅读时间需要 5 分钟。

广义表是线性表的推广。

广义表一般记作LS=(α1,α2,...,αn)

n是它的长度αi可以是单个元素也可以说广义表，分别称为广义表LS的原子和子表。

当广义表LS非空时，称第一个元素α1为LS的表头（Head），其余元素组成的表（α2，α3...αn）是LS的表尾（Tail）

下面给出广义表的列子：

1.A=()-空表，长度为0

2.B=(e)-列表B只有一个原子e，B的长度为1.

3.C=(a,(b,c,d))-列表C的长度为2，两个元素分别是原子a和子表（b,c,d）

4.D=(A,B,C)-3个元素都是列表，子表是上面的ABC

5.E=(a,E)-这是一个递归的表，它的长度为2。E相当于一个无线的列表E=(a,(a,(a...)))。

下面给出广义表图D

5.5广义表的存储结构：

下面给出广义表的尾链表存储表示：

结构图如下：

代码如下：

#define  AtomType inttypedef enum{ATOM,LIST}ELemTag;		//ATOM==0:原子,LIST==1:子表typedef struct GLNode{	ELemTag tag;	//公共部分，用于区分原子结点和表结点	union{		AtomType atom;	//atom是原子节点的值域，AtomType由用户定义		struct{			struct GLNode *hp, *tp;//ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾		}ptr;	};}*GList;

enum 为枚举类型，这个的作用是：比如说我们的程序中处理问题时与星期几有关，可能要将星期一转换为数字1，星期二转换为数字2，一直到数字7，在不用enum关键字的情况下，可以使用define来定义，但是大家会觉得很麻烦，因为你要一个一个的定义，星期的还好说，只有7天，如果是月份呢，一年有12个月份，那就要写12个define，非常的不方面，如果利用enum的话就会非常的方便。

下面的union

关于union比较多，大家可以把他直接当成struct，如果想具体了解请点击下面的链接

下面给出的这个图是刚刚上面说的ABCDE5个例子的存储结构：

1.A=()-空表，长度为0

2.B=(e)-列表B只有一个原子e，B的长度为1.

3.C=(a,(b,c,d))-列表C的长度为2，两个元素分别是原子a和子表（b,c,d）

4.D=(A,B,C)-3个元素都是列表，子表是上面的ABC

5.E=(a,E)-这是一个递归的表，它的长度为2。E相当于一个无线的列表E=(a,(a,(a...)))。

下面给出另一种节点结构的链表表示列表，图如下：

下面是代码：

#define  AtomType inttypedef enum{ATOM,LIST}ELemTag;		//ATOM==0:原子,LIST==1:子表typedef struct GLNode{	ELemTag tag;		//公共部分，用于区分原子结点和表结点	union{				//原子结点和表结点的联合		AtomType atom;	//原子结点的值域		struct GLNode *hp;	//表结点的表头指针	};	struct GLNode *tp;	//相当于线性链表的next，指向下一个元素结点}*GList;				//广义表类型GList是一种扩展的线性链表

1.A=()-空表，长度为0

2.B=(e)-列表B只有一个原子e，B的长度为1.

3.C=(a,(b,c,d))-列表C的长度为2，两个元素分别是原子a和子表（b,c,d）

4.D=(A,B,C)-3个元素都是列表，子表是上面的ABC

5.E=(a,E)-这是一个递归的表，它的长度为2。E相当于一个无线的列表E=(a,(a,(a...)))。

转载地址：https://it1995.blog.csdn.net/article/details/54984776 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！