基本定义

  • 广义表：n(n>=0)个元素组成的有限序列，其中元素可以是原子，也可以是广义表。广义表是线性表的推广，线性表的每个元素可以认为是原子的。
  • 表头：表非空时，表中第一个元素称作表头。
  • 表尾：除去表头其他元素组成的广义表称作表尾。
  • 表长：广义表中元素的个数。
  • 表深：广义表中括号的最大层数。空表的深度为1，原子节点深度为0。

数据结构实现

链式存储实现

typedef struct _glnode{
  int tag;//tag为0代表原子节点，tag为1代表表结点
  union{
    Elemtype value;原子节点的值
    struct _glnode * hp;//表头指针，实际上这里放表尾指针也可，因为原子节点本身就没有表头表尾。但是不能同时放表头表尾，因为union每次只能存一个成员
  };
  struct _glnode * tp;//表尾指针，对于原子节点来说恒为NULL，若表尾为空表也为NULL；
}GLNode;

常见问题

  • 广义表与线性表的区别？
    答：广义表元素可以是原子也可以是广义表，而线性表的元素是原子。广义表是线性表的推广。
  • 广义表的表尾是？
    答：广义表。
  • 空广义表的长度是？深度是？
    答：长度为0，深度为1。原子节点的深度定义为0.
  • 一个递归定义的广义表，例如 E = (a,E) 表长是多少？表深又是多少？
    答：表长为2，表深为无穷。
  • 如何唯一确定一个广义表？
    答：一个确定的表头和一个确定的表尾即可确定广义表。