清华大学严蔚敏C++语言算法讲稿：广义表的递归与操作

在清华大学严蔚敏的C++语言算法讲稿中，章节5.4主要讨论了广义表（Generalized List）这一主题。广义表是一种特殊的线性数据结构，它是递归定义的，允许数据元素既可以是原子（单个不可再分的值，如整数或字符串）也可以是其他广义表。这种结构的特点包括： 1. 层次结构：广义表是由原子或子表组成，形成一个多层的线性结构，可以用嵌套的括号来表示，如LS=((1,(2,(((,(n))，代表一个树状结构。 2. 元素顺序与深度：每个元素都有相对的次序，深度由括号的层数决定，原子的深度为0，空表的深度为1。递归表具有无限深度，但长度是有限的。 3. 属性与操作： - 创建与销毁：提供如`InitGList`、`DestroyGList`等函数来初始化和释放广义表。 - 状态查询：通过`GListLength`、`GListDepth`等函数获取表的长度和深度，`GListEmpty`用于判断表是否为空，`GetHead`和`GetTail`用于获取表头和表尾。 - 插入和删除：支持在表头插入元素和删除表头元素的操作，如`InsertFirst_GL`和`DeleteFirst_GL`。 - 遍历：提供了`Traverse_GL`函数，通过`Visit()`函数对广义表进行递归遍历。 5.5节详细介绍了广义表的表示方法，使用头尾指针的链表结构来实现。每个表节点包含一个标记(tag)和两个指针，如果是原子节点，标记为0，数据存储在节点内；如果是非空表，标记为1，表头节点包含表头元素（可能是原子或另一个表），而表尾节点则指向剩余的元素序列。通过分析构造存储结构，我们可以处理空表和非空表的不同情况，如表头为原子时的特殊处理。 理解并熟练掌握广义表在C++中的表示和操作对于算法设计和数据结构实现至关重要，它在递归、树和图等复杂数据结构处理中扮演着核心角色。在实际编程中，合理运用广义表能帮助提高代码的清晰性和效率。