广义表

1. 广义表的定义

    广义表(Lists，又称列表)是线性表的推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。

    广义表是n(n≥0)个元素a₁，a₂，…，a_i，…，a_n的有限序列。
  其中：
    　①a_i--或者是原子或者是一个广义表。
　    ②广义表通常记作：
              Ls=( a₁，a₂，…，a_i，…，a_n)。
　　 ③Ls是广义表的名字，n为它的长度。
　 　④若a_i是广义表，则称它为Ls的子表。
  注意：
    　①广义表通常用圆括号括起来，用逗号分隔其中的元素。
    　②为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。
    　③若广义表Ls非空(n≥1)，则a_l是LS的表头，其余元素组成的表(a₁，a₂，…，a_n)称为Ls的表。

       ④广义表是递归定义的。

2. 广义表的表示

    （1）广义表常用表示
　　① E=()
     　E是一个空表，其长度为0。
　　② L=(a，b)
     　L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表
　　③ A=(x，L)=(x，(a，b))
     　A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。
　　④ B=(A，y)=((x，(a，b))，y)
　     B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。
　　⑤ C=(A，B)=((x，(a，b))，((x，(a，b))，y))
     　C的长度为2，两个元素都是子表。
　　⑥ D=(a，D)=(a，(a，(a，(…))))
     　D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。

    （2）广义表的深度
　　一个表的"深度"是指表展开后所含括号的层数。
  【例】表L、A、B、C的深度为分别为1、2、3、4，表D的深度为∞。

    （3）带名字的广义表表示
    如果规定任何表都是有名字的，为了既表明每个表的名字，又说明它的组成，则可以在每个表的前面冠以该表的名字，于是上例中的各表又可以写成：
    ①E()
    ②L(a，b)
    ③A(x，L(a，b))
    ④B(A(x，L(a，b))，y)
    ⑤C(A(x，l(a，b))，B(A(x，L(a，b))，y))
    ⑥D(a，D(a，D(…)))

    （4）广义表的图形表示
   　 ①图中的分支结点对应广义表
   　 ②非分支结点一般是原子
    　③但空表对应的也是非分支结点。
　　【例】下图给出了几个广义表的图形表示

图 广义表的图形表示

   

3. 广义表的操作

    广义表的基本操作主要有以下5种：

    （1）GetHead(L)：求广义表的表头操作。如果广义表是空表，返回NULL，否则返回指向表头结点的指针。

    （2）GetTail(L)：求广义表的表尾操作。如果广义表是空表，返回NULL，否则返回指向表尾结点的指针。

    （3）GListLength(L)：返回广义表的长度操作。如果广义表是空表，则返回0，否则返回广义表的长度。

    （4）GListDepth(L)：求广义表的深度操作。深度就是广义表中括号嵌套的层数。空表返回1，否则返回表的深度。

    （5）CopyGList(&T,L)：广义表的复制操作。由广义表L复制得到广义表T。复制成功返回1，否则返回0。

    广义表中的每个元素可以用一个结点表示，表中有两类结点：原子结点和子表结点。广义表可以分解为表头和表尾，一个表头和一个表尾可以确定一个广义表。因此，一个表结点一般由三个域组成：标志域、指向表头的指针域和指向表尾的指针域。一个原子结点一般由两个域组成：标志域和值域。广义表的存储额结构示意图如下所示：

图 广义表存储结构示意图

4. 广义表的运算 

    在此，只讨论广义表的两个特殊的基本运算：取表头head(Ls)和取表尾tail(Ls)。
    　根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。
  【例】
      head(L)=a， tail(L)=(b)
      head(B)=A， tail(B)=(y)
  由于tail(L)是非空表，可继续分解得到：
      head(tail(L))=b， tail(tail(L))=()
  对非空表A和(y)，也可继续分解。
  注意:广义表()和(())不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()。