广义表

定义和性质

线性表是由 n 个元素组成的有限序列。其中每个组成元素被限定为单元素。

广义表（Generalized Lists）是 n(n >= 0) 个数据元素的有序序列，一般记作：

ls = (a1, a2, …, an);

其中 ai 可以是单个元素，也可以是一个广义表，分别称为广义表的 ls 的单元素和子表，当广义表为非空时，称第一个元素 a1 为 ls 的表头（head），称其余元素组成的表为 ls 的表尾（Tail）。广义表的定义是递归的。

性质：

例如：

当二维数组的每行（每列）作为子表来处理时，二维数组即为一个广义表。广义表的机构很灵活，它可以兼容线性表、数组、树和有向图等常用的数据结构。

广义表的长度和深度：

广义表长度时广义表中元素的个数。如 lenggh(B) = 1, length(D) = 3。广义表的深度是广义表展开后所含括号的最大层数，如 depth(F) = 3, depth(E) = ∞ 。

广义表的基本运算有：建立、插入、删除、拆开、连接、复制、遍历等。