| |
| 广义表是5.2节提到的线性表的推广。线性表中的元素仅限于原子项，即不可以再分，而广义表中的元素既可以是原子项，也可以是子表（即另一个线性表）。它是n≥0个元素a1, a2, …，an的有限序列，其中每一个ai或者是原子，或者是一个子表。广义表通常记为LS=（a1, a2, …，an），其中LS为广义表的名字，n为广义表的长度，每一个ai为广义表的元素。但在习惯中，一般用大写字母表示广义表，小写字母表示原子。
|
|
|
|
|
| （1）用LS=（a1， a2, …，an）形式，其中每一个ai为原子或广义表。
|
|
|
|
|
| （2）将广义表中所有子表写到原子形式，并利用圆括号嵌套。
|
|
|
|
|
|
|
| （3）将广义表用树和图来描述，一个广义表的深度指的是该广义表展开后所含括号的层数。例如，A=（b，c）的深度为1，B=（A，d）的深度为2，C=（f，B,h）的深度为3；如下图所示。
|
|
|
|
|
|
|
| 由于广义表的元素类型不一定相同，因此，难以用顺序结构来存储表中的元素，通常采用链接存储方法来存储广义表中元素，并称之为广义链表。广义表需要两种结构的结点，一种是表结点，表示列表；一种是原子节点，表示原子。一个表结点可以由标志域、指示表头的指针域和指示表尾的指针域组成；而原子结点由标志域和值域组成，如下图所示。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
