4-5 广义表

广义表（又称列表Lists）：是n≥0个元素$a_0,a_1,...,a_{n-1}$的有限序列，其中每一个$a_i$或者是原子（基础元素），或者是一个广义表

例：{1,3,5, ,(2,4,6)}

在这个例子中，我们既存储了整型变量，又存储了空值，又存储了另一个广义表

广义表通常记作：$LS=(a_1,a_2,...,a_n)$

其中：LS为表名，n为表的长度，每一个$a_i$为表的元素

习惯上，一般用大写字母表示广义表，小写字母表示原子

表头：若LS非空（n≥1），则其第一个元素$a_1$就是表头

记作$head(LS)=a_1$

注：表头可以是原子，也可以是子表

表尾：除表头之外的其他元素组成的表

记作$tail(LS)=(a_2,...,a_n)$

注：表尾不是最后一个元素，而是一个子表

广义表的性质：

  1. 广义表中的数据元素有相对次序：一个直接前驱和一个直接后继

  2. 广义表的长度定义为最外层所包含元素的个数：

    如：$C=(a,(b,c))$是长度为2的广义表

  3. 广义表的深度定义为该广义表展开后所含括号的重数：

    $A=(b,c)$的深度为1，$B=(A,d)$的深度为2，$C=(f,B,h)$的深度为3

    注意：“原子”的深度为0；“空表”的深度为1

  4. 广义表可以为其他广义表共享：

    如：广义表B就共享表A。在B中不必列出A的值，而是通过名称来引用$B=(A,d)$

  5. 广义表可以是一个递归的表

    如：$F=(a,F)=(a,(a,(a,...)))$

    注意：递归表的深度是无穷值，长度是有限值

  6. 广义表是多层次结构，广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表

广义表与线性表的区别？