顾名思义,广义表是线性表的推广,也有人称其为列表,广泛地用于人工智能等领域的表处理语言LISP,把广义表作为基本的数据结构,就连程序也表示为一系列的广义表。其表中的元素可以是另一个广义表,或其自身。
抽象数据类型广义表的定义如下:
ADT GList
{
数据对象:D={ei| i=1,2,...,n;n≥0; ei?AtomSet或ei?GList,
AtomSet为某个数据对象}
数据关系:R1={<ei-1,ei>|ei-1,ei?D,2≤i≤n}
基本操作:
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可以是单个元素也可以是广义表,分别称为广义表的原子和子表。当习惯上,用大写字母表示广义表的名称,用小写字母表示原子。当广义表非空时,称第一个元素a1为LS的表头(Head),称其余元素组成的表是广义表的表尾(Tail)。
显然,广义表是递归定义的线性结构,因为在描述广义表时又用到了广义表的概念。下面列举一些广义表的例子。
A=():A是一个空表,长度为零。
B=(e):列表B只有一个原子e,B的长度为1。
C=(a(b,c,d)):列表C的长度为2,两个元素分别为原子a和子表(b,c,d)。
D=(A,B,C):列表D的长度为3,三个元素都是列表。显然将子表的值代入后,则有D=((), (e), (a(b,c,d)))。
E=(a,E):这是一个递归表,它的长度为2。
从上述定义和例子可推导出列表的3个重要结论:
(1)列表的元素可以是子表,而子表的元素还可以是子表……。由此广义表是一个多层次的线性结构,可以用图形象地表示出来。
(2)列表可以为其他列表所共享。例如,在上述例子中列表A、B、C为D的子表,则在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的表尾)。原子和空表没有表头和表尾。