定义
广义表是线性表的推广,线性表中的元素都是原子的单元素,而广义表中的元素可以是原子的单元素,也可以是一个子广义表。广义表的定义是递归的,广义表是线性表的递归数据结构
(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自身,展开后它是一个无限的广义表
(2)广义表的深度
一个表的"深度"是指表展开后所含括号的层数。
【例】表L、A、B、C的深度为分别为1、2、3、4,表D的深度为∞。
广义表的存储结构
广义表中的元素可以是单元素,也可以是广义表,因为具有不同的结构,所以用顺序存储结构实现的难度比较大,因为很难为每个广义表分配固定大小的存储空间,所以通常采用链式存储结构
广义表的类型定义
广义表可以分为两个部分,头部和尾部,头部是广义表的第一个元素,尾部是广义表的除第一个元素的其他子元素,也就是前面的GeneralizedNode.sublist和GeneralizedNode.next
广义表的长度
可以用递归实现,即
1(头部元素)+尾部元素的长度。
广义表的深度
空表或仅由单元素构成,则深度为1,可以用递归实现,即
子表的最大深度+1
查找值为obj的元素
也用递归实现,当当前子元素为广义表时,则递归查找,否则为单元素,直接比较;依次遍历完整个广义表。
广义表的创建
空表用#表示,如(#),广义表的结束用;号表示,例如: (a,(#),b,c,(d,(e)));