广义表的一些概念

基本概念

广义表(Lists,又称列表)是线性表的推广。广义表是$n(n\geqslant 0)$个元素$a_1,a_2,a_3,…,a_n$的有限序列,其中$a_i$或者是原子项,或者是一个广义表。

  • 元素:广义表的元素可以是原子,也可以是广义表,也可以为空。
  • 表头:若广义表$LS(n\geqslant 1)$非空,则$a_1$是LS的表头。表头可以是单元素值,也可以是表。空的广义表不能求表头。
  • 表尾:若广义表$LS(n\geqslant 1)$非空,则除去表头后剩下的元素组成的表是LS的表尾。表尾一定是表。空的广义表不能求表尾。

例子

  1. $A=()$——A是一个空表,其长度为零。
  2. $B=(e)$——表B只有一个原子$e$,其长度为1。
  3. $C=(a,(b,c,d))$——表C的长度为2,两个元素分别为原子$a$和子表$(b,c,d)$,其表尾为$((b,c,d))$。
  4. $D=(A,B,C)$——表D的长度为3,三个元素都是广义表。显然,将子表的值代入后,则有$D=((),(e),(a,(b,c,d)))$。
  5. $E=(a,E)$——这是一个递归的表,它的长度为2,E相当于一个无限的广义表$E=(a,(a,(a,(a,…))))$.

考点

  1. 广义表是0个或多个单因素或子表组成的有限序列,广义表可以是自身的子表,广义表的长度$n\geqslant 0$,所以可以为空表。广义表的同级元素(直属于同一个表中的各元素)具有线性关系。
  2. 广义表的表头为空,并不代表该广义表为空表。广义表$()$和$(())$不同。前者是长度为0的空表,对其不能做求表头和表尾的运算;而后者是长度为1的非空表(只不过该表中惟一的一个元素是空表),对其可进行分解,得到的表头和表尾均是空表$()$。
  3. 已知广义表$LS=((a,b,c),(d,e,f))$,运用$head$和$tail$函数取出LS中原子$e$的运算是$head(tail(head(tail(LS)))$。根据表头、表尾的定义可知:任何一个非空广义表的表头是表中第一个元素,它可以是原子,也可以是子表,而其表尾必定是子表。也就是说,广义表的$head$操作,取出的元素是什么,那么结果就是什么。但是$tail$操作取出的元素外必须加一个表——“$()$“。$tail(LS)=((d,e,f))$;$head(tail(LS))=(d,e,f)$;$tail(head(tail(LS)))=(e,f)$;$head(tail(head(tail(LS))))=e$。
  4. 二维以上的数组其实是一种特殊的广义表。
  5. 在(非空)广义表中:1、表头$head$可以是原子或者一个表;2、表尾$tail$一定是一个表;3.广义表难以用顺序存储结构;4.广义表可以是一个多层次的结构。

参考

数据结构:广义表