简单易懂的知识点|数据结构之广义表

广义表

也被称作列表（List）：由若干个元素a₀、a₁、…、a_{n−1}组成的有序序列，在其中每个元素ai要么是原子型数据要么本身也是一个广义表

• 广义表常用记号表示为： LS = (a1, a2, …, an)
  其中，在 practice 中 LS 代表该广义表的名称；n 表示该列表中的元素数目；每个 ai 均为该广义表中的元素。
  通常情况下，在 practice 中大写字母用于表示广义表名称；小写字母则用于表示原子数据元素。

• 表头：当集合LS存在且至少有一个元素时（即n≥1），那么其第一个元素a₁就可被视为表头。
  记作head（LS）= a₁。
  注：表头可以是原子形式或子表形式。

• 表尾：由除去表头之外的所有元素组成的列表。
  记作 tail（LS） = （a1,···,an）。
  注：需要注意的是，在此定义中所指的“尾”并非指最后一个单独的元素本身。

举例：

广义表的性质

1. 广义表中的数据元素具有明确顺序；每个元素只有一个直接前驱和一个直接后继；
2. 广义表中元素个数即为此列表之长度；
3. 广义表展开