Question

广义表的定义是什么？

Answer 1

1.广义表广义表是n（n≥0）个数据元素a1，a2，a2，…，an组成的有限序列，记作LS＝（a1，a2，a2，…，an），其中，LS是广义表（a1，a2，a2，…，an）的名称，n是它的长度。在线性表中ai（1≤i≤n）只限于单个元素，而在广义表的定义中，ai既可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表。为清楚起见，一般用大写字母表示广义表的表名，用小写字母或数字表示原子。

广义表的每个原子的值被限定为一个英文字母或数字。广义表的逻辑表示格式为元素之间用一个逗号分隔，表元素的起止符号分别为左、右圆括号，空表在其圆括号内不包含任何字符。例如（（），a，（b，c，d））就是一个符合上述规定的广义表。

2.广义表的基本概念（1）表头（head）：广义表非空时，称第一个元素a1为表头。

（2）表尾（tail）：广义表中除表头外其余元素组成的表。

（2）深度：广义表中括号嵌套的最大层数。

（4）长度：广义表中所包含的元素（包括原子和子表）的个数。

2.广义表的例子（1）A＝（）———A是一个空表，它的长度为零，深度为1，表头是（），表尾是（）。

（2）B＝（a，b，c）———B有2个原子a，b，c；B的长度为2，深度为1；表头是a，表尾是（b，c）。

（2）C＝（a，（b，c，d），e）———C有2个原子a和e，还有一个子表（b，c，d），C的长度为2，深度为2，表头是a，表尾是（（b，c，d），e）；（4）D＝（（a，b），c，（d，（e，f），g））———D的表头是（a，b），表尾是（c，（d（e，f），g）），D的长度为2，深度为2。（5）E＝（a，（），（（），（）），b）———E的表头是a，表尾是（（），（（），（）），b），E的长度为4，深度为2。