广义表：一种扩展的线性表结构

广义表：一种扩展的线性表结构

广义表是一种扩展的线性表结构，在计算机科学的数据结构领域有着重要的应用。它允许表的元素既可以是原子，也可以是另一个广义表，这种特性使得广义表能够表示更复杂的数据结构。本文将详细介绍广义表的基本概念、性质以及相关示例。

广义表的基本定义

广义表是一种扩展的线性表，又称为列表（Lists）。它是由n（n>=0）个元素组成的有限序列，其中每一个元素ai可以是一个原子或另一个广义表。通常用大写字母表示广义表，小写字母表示原子。一个广义表LS可以表示为：

LS=(a1,a2,...,an)

其中，LS为表名，n为表长，ai为表的元素。广义表中的数据元素有相对次序，每个元素都有一个直接前驱和一个直接后继。

表头与表尾

• 表头：若LS非空，则其第一个元素a1就是表头。表头可以是原子，也可以是另一个广义表。记为：head(LS)=a1
• 表尾：除表头之外的其他元素组成的表，表尾是一个字表。记为：tail(LS)=(a2,...,an)

广义表的长度与深度

• 广义表的长度：指最外层所包含元素的个数。
• 广义表的深度：指广义表展开后所包含的括号重数。

共享与递归

广义表可以为其他广义表所共享。例如，广义表B可以通过名称引用共享广义表A：B=(A)。递归表的长度有限，但深度可以是无穷的。

示例说明

下面通过一些具体的例子来帮助理解广义表的概念：

• A=（）：空表，长度为0
• B=（（））：长度为1，表头和表尾都是空表（）
• C=（(a,(b,c)）：长度为1，表头为a，表尾为（(b,c)）
• D=（x，y，z）：长度为3，表头为x，表尾为（y,z）
• E=（（b,c））：长度为1，表头为（b,c），表尾为（）
• F=（a）：长度为1，表头为a，表尾为（）
• 共享广义表E=（C，D）：长度为2，表头为C，表尾为（D）
• 嵌套广义表F=（a，F）/F=(a,(a,(a,...)))：长度为2，表头为a，表尾为（F）

图形化表示

广义表的结构可以通过图形化的方式进行表示，如下图所示：

通过图形化表示，可以更直观地理解广义表的嵌套结构和元素之间的关系。