广义表
广义表是线性表的推广。
广义表一般记作LS=(a1,a2,....,an),其中,LS是广义表的名称,n是它的长度。
在线性表中,ai只限于单个元素,而在广义表中,ai可以是单个元素,也可以是广义表,分别称为LS的原子和子表。
当广义表LS非空时,称第一个元素a1为LS的表头,称其余元素组成的表为LS的表尾。
广义表的定义是一个递归的定义,因为在描述广义表时又用到了广义表的定义。
广义表的例子:
广义表的结论:
- 列表的元素可以是子表,而子表的元素还可以是子表
- 列表可为其他列表所共享
- 列表可以是一个递归的表,即列表也可以是其本身的一个子表
任何一个非空列表其表头可能是原子,也可能是列表,而其表尾必定是列表。(//表头是一个元素,表尾是很多元素的集合
LS()和LS(())是不同的,前者为空表,长度为0,后者长度为1,可分解得到表头、表尾均为空表()