5.4　广义表的定义

视频二维码（扫码观看）

广义表（Lists，又称为列表）：是由n（n≥0）个元素组成的有穷序列：LS＝（a₁，a₂，…，a_n），其中a_i或者是原子项，或者是一个广义表。LS是广义表的名字，n为它的长度。若a_i是广义表，则称为LS的子表。

习惯上：原子用小写字母，子表用大写字母。

若广义表LS非空时：

a₁（表中第一个元素）称为表头；

其余元素组成的子表称为表尾（a₂，a₃，…，a_n）；

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

广义表中括号的最大层数称为表深（度）。

广义表的重要结论：

（1）广义表的元素可以是原子，也可以是子表，子表的元素又可以是子表，…。即广义表是一个多层次的结构，可以用图表示，如图5-6所示。图中，圆圈表示列表，方块表示原子。

图5-6　广义表的图形表示

（2）广义表可以被其他广义表所共享，也可以共享其他广义表。广义表共享其他广义表时通过表名引用。

（3）广义表本身可以是一个递归表。

（4）根据对表头、表尾的定义，任何一个非空广义表的表头可以是原子，也可以是子表，而表尾必定是广义表。