Question

数据结构之广义表

Answer 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自身，展开后它是一个无限的广义表

一个表的"深度"是指表展开后所含括号的层数。

【例】表L、A、B、C的深度为分别为1、2、3、4，表D的深度为∞。

广义表中的元素可以是单元素，也可以是广义表，因为具有不同的结构，所以用顺序存储结构实现的难度比较大，因为很难为每个广义表分配固定大小的存储空间，所以通常采用链式存储结构

广义表可以分为两个部分，头部和尾部，头部是广义表的第一个元素，尾部是广义表的除第一个元素的其他子元素，也就是前面的GeneralizedNode.sublist和GeneralizedNode.next

可以用递归实现，即

空表或仅由单元素构成，则深度为1,可以用递归实现,即

也用递归实现，当当前子元素为广义表时,则递归查找，否则为单元素，直接比较；依次遍历完整个广义表。

空表用#表示，如(#),广义表的结束用;号表示， 例如:       (a,(#),b,c,(d,(e)));