广义表的定义

广义表是线性表的推广，也称列表（Lists）。它是 $n$ 个元素的有限序列，记作：

$$L=({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n)$$

其中 $L$ 是表名，$n$ 是广义表的长度。${\alpha }_i$ 可以是以下几种类型：

• 若 ${\alpha }_i$ 是广义表，则称为子表，通常用大写字母表示
• 若 ${\alpha }_i$ 是单个元素，则称为原子，通常用小写字母表示

广义表的特点

1. 相对次序：广义表中的数据元素有相对次序
2. 长度：广义表的长度定义为最外层包含元素的个数
3. 深度：广义表的深度定义为所含括弧的嵌套层数
   • 原子的深度为 $0$
   • 空表的深度为 $1$
4. 共享：广义表可以共享，不必列出子表的值，而是通过子表的名称来引用
5. 递归：广义表可以是一个递归的表
   • 递归表的深度是无穷值，长度是有限值

链接到

• 上一个知识点：无（本章第一个知识点）
• 下一个知识点：2.2 子表存储