Python广义表详解（手把手教你用Python实现广义表数据结构）

什么是广义表？

广义表的一般形式为：L = (a₁, a₂, ..., aₙ)，其中每个 aᵢ 可以是单个元素（原子），也可以是一个子广义表。

例如：

• () —— 空表
• (1, 2, 3) —— 普通线性表（所有元素都是原子）
• (1, (2, 3), 4) —— 包含子表的广义表
• ((a, b), (c, d)) —— 嵌套结构

为什么用Python实现广义表？

Python 本身支持列表嵌套（如 [1, [2, 3], 4]），但为了深入理解递归数据结构和掌握自定义数据类型的设计方法，我们手动构建一个类来封装广义表的行为。这有助于学习Python数据结构的核心思想。

设计思路

我们将创建一个 GeneralizedList 类，每个节点包含两个属性：

• tag：标记当前节点是原子（0）还是子表（1）
• value：如果是原子，存储实际值；如果是子表，存储指向子表的引用

这种设计模仿了传统 C 语言中广义表的“头尾链表”表示法，但在 Python 中更简洁。

完整代码实现

class GeneralizedList:    def __init__(self, data=None):        """        初始化广义表        :param data: 可以是列表、元组、原子值或 None        """        self.head = None        if data is not None:            self._build_from(data)        def _build_from(self, data):        """从 Python 内置结构构建广义表"""        if isinstance(data, (list, tuple)):            if len(data) == 0:                self.head = None                return            # 创建头节点（子表类型）            self.head = Node(tag=1)            current = self.head            for item in data:                new_node = Node()                if isinstance(item, (list, tuple)):                    # 子表                    new_node.tag = 1                    new_node.value = GeneralizedList(item)                else:                    # 原子                    new_node.tag = 0                    new_node.value = item                current.next = new_node                current = new_node        else:            # 单个原子            self.head = Node(tag=0, value=data)        def display(self):        """返回广义表的字符串表示"""        if self.head is None:            return "()"        if self.head.tag == 0:            return str(self.head.value)                parts = []        current = self.head.next        while current:            if current.tag == 0:                parts.append(str(current.value))            else:                parts.append(current.value.display())            current = current.next        return "(" + ", ".join(parts) + ")"        def __str__(self):        return self.display()class Node:    def __init__(self, tag=None, value=None):        self.tag = tag      # 0: atom, 1: sublist        self.value = value  # actual value or GeneralizedList instance        self.next = None    # pointer to next element

使用示例

# 创建空广义表empty = GeneralizedList([])print(empty)  # 输出: ()# 创建普通列表simple = GeneralizedList([1, 2, 3])print(simple)  # 输出: (1, 2, 3)# 创建嵌套广义表nested = GeneralizedList([1, [2, 3], 4, [5, [6, 7]]])print(nested)  # 输出: (1, (2, 3), 4, (5, (6, 7)))# 单个原子atom = GeneralizedList("hello")print(atom)  # 输出: hello

关键知识点总结

通过本教程，你掌握了以下核心内容：

• 广义表的定义及其与普通列表的区别
• 如何用 Python 类封装递归数据结构
• 节点设计中的 tag 标志位思想
• 从内置结构（如 list）自动构建广义表

结语

广义表虽然在日常开发中不常直接使用，但它是理解复杂数据结构（如 Lisp 的 S-表达式、XML 树等）的重要基础。通过动手实现Python广义表，你不仅加深了对Python数据结构的理解，也提升了抽象建模能力。

希望这篇教程对你有帮助！欢迎尝试扩展功能，比如添加查找、插入、删除等操作。