本书结构

本书通过循序渐进的方式推进，并且只有在需要的时候才会引入新概念。

第1章回顾Python编程的相关功能，这是用Python学习计算机科学的第二门课程里的编程和解决问题必需的。如果你有丰富的Python编程经验，那么可以快速地浏览一遍这一章的内容；如果你是Python新手，那么可以通过这部分内容深入了解这门语言。

本书其余部分（第2～12章）涵盖通常会包含在计算机科学的第二门课程里的主要主题，特别是抽象数据类型的规范、实现及应用等内容，并且会把多项集类型作为学习的主要工具和重点。在这些内容里，你将全面了解面向对象的编程技术以及好软件的设计要素。本书还涉及计算机科学的第二门课程里其他一些重要的主题，例如数据的递归处理、搜索和排序算法以及软件开发［复杂度分析或用在设计文档里的图形符号（UML）］里会用到的工具。

第2章介绍抽象数据类型（Abstract Data Type，ADT）的概念，并且对各种多项集中的抽象数据类型进行概览。

第3章和第4章介绍实现大部分多项集的数据结构，并且介绍了一些用来进行复杂度分析的工具。第3章介绍使用大O表示法的复杂度分析。这部分内容包含了很多材料，用搜索和排序算法作为例子，对算法和数据结构的运行时以及内存使用情况进行了简单分析。第4章介绍使用数组和线性链接结构的相关细节，这些数据结构用于实现大部分多项集。你将了解支持数组和链接结构的计算机内存的底层模型，以及使用它们所需要面对的时间/空间的权衡等内容。

第5章和第6章把关注点转移到面向对象设计的原则上。这些原则在后续章节里用于构建多项集类的专家级框架。

第5章讨论接口和实现之间的重要差异。开发包多项集的一个接口和多个实现作为展现这些差异的第一个例子。本章会将重点放在接口包含的通用方法上，允许不同类型的多项集在应用程序里进行协作，比如用来创建迭代器的方法。这个通用方法所创建的迭代器能够通过简单的循环来遍历任何一个多项集。本章还会介绍多态以及信息隐藏，这些主题也会通过接口和实现之间的差异表现出来。

第6章介绍类的层次结构是如何减少面向对象软件系统里的冗余代码的，还会介绍继承、方法调用的动态绑定以及抽象类的相关概念。这些概念会在后续章节里被反复使用。

在掌握这些概念和原则之后，你就可以开始学习第7～12章里其他重要的多项集抽象数据类型了。

第7～9章介绍栈、队列以及列表。我们会先从用户的角度进行介绍，以便你能了解所选实现里提供的接口以及一系列性能特征。我们会通过一个或多个应用程序说明每个多项集的用法，然后开发出这个多项集的若干种实现，并分析它们在性能上的权衡。

第10～12章介绍更高级的数据结构和算法，以便帮助你过渡到计算机科学里更高阶的课程。第10章讨论各种树结构，如二叉查找树、堆和表达式树。第11章通过哈希策略研究无序集合、包、集合和字典的实现。第12章介绍图和图处理算法。

本书的特色在于呈现一个多项集类的专家级框架。你看到的不会是一系列毫不相关的多项集，而是每个多项集在整体框架里的相应位置。这种方法能够让你了解到多项集类型的共同点以及使用不同多项集类型的原因。同时，你会接触到继承和类的层次结构，而这正是面向对象的软件设计的主题，虽然这些主题是这个级别的课程很少讲解和体现的。