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

4.8 广义表的定义

 

4.8  广义表的定义

顾名思义,广义表是线性表的推广,也有人称其为列表,广泛地用于人工智能等领域的表处理语言LISP,把广义表作为基本的数据结构,就连程序也表示为一系列的广义表。其表中的元素可以是另一个广义表,或其自身。

抽象数据类型广义表的定义如下:

ADT GList

{

数据对象:D={ei| i=1,2,...,n;n0; ei?AtomSetei?GList,

AtomSet为某个数据对象}

数据关系:R1={<ei-1,ei>|ei-1,ei?D,2in}

基本操作:

InitGlist(&L)

操作结果:创建空的广义表L

CreateGList(&L,S)

初始条件:S是广义表的书写形式串。

操作结果:由S创建广义表L

DestroyGlist(&L)

初始条件:广义表L存在。

操作结果:销毁广义表L

CopyGlist(&T,L)

初始条件:广义表L存在。

操作结果:由广义表L复制得到广义表T

GListLength(L)

初始条件:广义表L存在。

操作结果:求广义表L的长度,即元素个数。

GListDepth(L)

初始条件:广义表L存在。

操作结果:求广义表L的深度。

GlistEmpty(L)

初始条件:广义表L存在。

操作结果:判断广义表L是否为空。

GetHead(L)

初始条件:广义表L存在。

操作结果:取广义表L的头。

GetTail(L)

初始条件:广义表L存在。

操作结果:取广义表L的尾。

InsertFirst_GL(&L,e)

初始条件:广义表L存在。

操作结果:插入元素e作为广义表L的第一元素。

DeleteFirst_GL(&L,&e)

初始条件:广义表L存在。

操作结果:删除广义表L的第一元素,并用e返回其值。

Traverse_GL(L,Visit())

初始条件:广义表L存在。

操作结果:遍历广义表L,用函数Visit处理每个元素。

}ADT GList

广义表一般记作:

LS=(a1, a2, an)

其中,LS是广义表(a1, a2, an)的名称;n是它的长度;ai可以是单个元素也可以是广义表,分别称为广义表的原子和子表。当习惯上,用大写字母表示广义表的名称,用小写字母表示原子。当广义表非空时,称第一个元素a1LS的表头(Head),称其余元素组成的表是广义表的表尾(Tail)。

显然,广义表是递归定义的线性结构,因为在描述广义表时又用到了广义表的概念。下面列举一些广义表的例子。

A=()A是一个空表,长度为零。

B=(e):列表B只有一个原子eB的长度为1

C=(a(b,c,d)):列表C的长度为2,两个元素分别为原子a和子表(b,c,d)

D=(ABC):列表D的长度为3,三个元素都是列表。显然将子表的值代入后,则有D=((), (e), (a(b,c,d)))

E=(a,E):这是一个递归表,它的长度为2

从上述定义和例子可推导出列表的3个重要结论:

1)列表的元素可以是子表,而子表的元素还可以是子表……。由此广义表是一个多层次的线性结构,可以用图形象地表示出来。

2)列表可以为其他列表所共享。例如,在上述例子中列表ABCD的子表,则在D中可以不必列出子表的值,而是通过子表的名称来引用。

3)列表可以是一个递归的表,即列表可以是其本身的一个子表。

根据前述对表头、表尾的定义可知:任何一个非空列表其表头可能是原子,也可能是列表,而表尾必定为列表。例如:

LS=(A,D )=((),(E,F))=((),((a,(b,c)F)

GetHead(LS)=A                   GetTail(LS)=(D)

GetHead(D)=E                    GetTail(D)=(F)

GetHead(E)=a                    GetTail(E)=((b,c)) 

GetHead(((b,c)))=(b,c)          GetTail(((b,c)))=()

GetHead((b,c))=b                GetTail((b,c))=(c)

GetHead((c))=c                  GetTail((c))=()  

上述表示法称为括号表示法。广义表中所含括号的最大层数称为广义表的深度;广义表中所含元素个数称为广义表的长度;广义表的第一个元素称为广义表的表头(用head(L)表示广义表L的表头),除表头外,其余部分称为广义表的表尾(用tail(L)表示广义表L的表尾)。原子和空表没有表头和表尾。