广义表(Lists,又称列表)是一种非线性的
数据结构,是
线性表的一种推广。即广义表中放松对表元素的原子限制,容许它们具有其自身结构。它被广泛的应用于人工智能等领域的表处理语言LISP语言中。在LISP语言中,广义表是一种最基本的数据结构,就连LISP 语言的程序也表示为一系列的广义表。
定义:
广义表是n(n≥0)个元素a1,a2,…,ai,…,其中:
①ai--或者是原子或者是一个广义表。
②广义表通常记作:
Ls=( a1,a2,…,ai,…,an)。
③Ls是广义表的名字,n为它的长度。
④若ai是广义表,则称它为Ls的子表。
注意:
①广义表通常用圆括号括起来,用逗号分隔其中的元素。
②为了区分原子和广义表,书写时用大写字母表示广义表,用小写字母表示原子。
③若广义表Ls非空(n≥1),则a1是Ls的
表头,其余元素组成的表(a2,a3,…,an)称为Ls的表尾。
④广义表是递归定义的an的有限序列。
广义表表示
(1)广义表常用表示
① E=()
E是一个空表,其长度为0。
② L=(a,b)
L是长度为2的广义表,它的两个元素都是原子,因此它是一个线性表
③ A=(x,L)=(x,(a,b))
A是长度为2的广义表,第一个元素是原子x,第二个元素是子表L。
④ B=(A,y)=((x,(a,b)),y)
B是长度为2的广义表,第一个元素是子表A,第二个元素是原子y。
⑤ C=(A,B)=((x,(a,b)),((x,(a,b)),y))
C的长度为2,两个元素都是子表。
⑥ D=(a,D)=(a,(a,(a,(…))))
D的长度为2,第一个元素是原子,第二个元素是D自身,展开后它是一个无限的广义表。