《Python 编程》，第 4 版

第 18 章 数据结构数据结构

本作品已使用人工智能进行翻译。欢迎您提供反馈和意见：[e-mail]

"玫瑰是红的，紫罗兰是蓝的；名单是可变的，布景也是可变的"

数据结构是大多数程序的核心主题，尽管 Python 程序员通常并不需要关心。他们的冷漠是有道理的--Python "开箱即用"，内置了丰富的、已经优化过的类型，可以轻松处理结构化数据：列表、字符串、元组、字典、集合等。对于简单的系统，这些类型通常就足够了。例如，字典包含了许多经典的搜索算法，而列表则取代了在低级语言中支持集合所需的大量工作。即便如此，这两种类型都非常容易使用，一般情况下你都不会多想。

但对于高级应用程序，我们可能需要自己添加更复杂的类型来处理额外的需求或特殊情况。在本章中，我们将探索 Python 中一些高级数据结构的实现：集合、栈、图等。 我们将看到，数据结构在 Python 中可以采用新对象类型的形式，并集成到语言的类型模型中。也就是说，我们在 Python 中编码的对象将成为成熟的数据类型，对于使用它们的脚本来说，它们看起来和感觉上就像内置的列表、数字和字典。

尽管本章中的示例说明了高级编程和计算机科学技术，但它们也强调了 Python 对编写可重用软件的支持。 由于对象实现是用类和模块编码的，它们自然而然地成为了通用的有用组件，可以在任何导入它们的程序中使用。实际上，无论我们是否计划好，我们都将建立数据结构工具库。

此外，尽管本章中的大多数示例都是纯 Python 代码（至少对于线性读者来说，有些示例与前面几章的示例相比可能显得相对简单），但它们也为讨论 Python 性能问题提供了一个用例，并暗示了第 20 章的主题的可能性--从最一般的角度来看，新的 Python 对象既可以用 Python 实现，也可以用集成语言（如 C 语言）实现。

不过，最终我们也会发现，Python 的内置支持往往可以在这一领域取代自制的解决方案。尽管自定义数据结构的实现有时是必要的，而且在代码维护和演进方面仍有许多优势，但在 Python 中，它们并不总是像在对程序员不太友好的语言中那样至关重要。

实施堆栈

堆栈是一种常见的、、简单明了的数据结构，在语言处理、图形搜索等各种应用中都有使用。例如，下一章计算器图形用户界面中的表达式求值在很大程度上就是在堆栈中进行的，一般编程语言通常将函数调用作为堆栈操作来实现，以便在调用返回时记住要恢复的操作。堆栈在 XML 解析中也有帮助：在构造任意嵌套的情况下，堆栈是跟踪进度的天然工具。

简而言之，栈是一个后进先出的对象集合--最后一个添加到集合中的项目总是下一个要删除的项目。与我们用于线程通信的队列（在两端添加和删除）不同，栈中的所有活动都发生在顶部。客户端通过以下方式使用堆栈

• 将物品推到顶部

• 从顶部弹出物品

根据客户的要求，还可以使用一些工具来执行以下任务：测试堆栈是否为空、在不弹出堆栈的情况下获取顶层项、遍历堆栈项、测试项的成员资格等。

内置选项

在 Python 中，一个简单的 list 通常就足以实现堆栈：因为我们可以任意地就地更改 list，所以我们可以从开头（左侧）或结尾（右侧）添加和删除项。表 18-1总结了各种内置操作，它们可用来通过 Python 列表和就地更改实现类似堆栈的行为。它们根据堆栈 "顶部 "是列表中的第一个节点还是最后一个节点而有所不同；在本表中，字符串'b' 是堆栈的初始顶部项。

表 18-1.作为列表的堆栈

运行	顶部为列表末尾	顶部为列表前部	顶部为列表前部
新	stack=['a', 'b']	stack=['b', ...