前言

致学生

既然你已经开始阅读本书，那么必定对计算机科学感兴趣。你可能也对Python这门编程语言感兴趣，并且已经通过之前的课程或自学有了一些编程经验。不论是何种情况，你肯定都希望学习更多知识。

本书将介绍计算机科学，也会介绍Python。然而，书中的内容并不仅仅局限于这两个方面。学习数据结构与算法对理解计算机科学的本质非常关键。

学习计算机科学与掌握其他高难度学科没什么不同。成功的唯一途径便是循序渐进地学习其中的核心思想。刚开始接触计算机科学的人，需要多多练习来加深理解，从而为学习更复杂的内容做好准备。此外，初学者需要建立起自信心。

本书用作数据结构与算法的入门课的教材。数据结构与算法通常是计算机科学专业的第二门课程，比第一门课程更深入。但是本书的读者对象仍然是初学者，很可能还在第一门课程所教的基本思想和方法中挣扎，但已经准备好进一步探索这一领域并且进一步练习如何解决问题。

如前所述，本书将介绍计算机科学。它既会介绍抽象数据类型及数据结构，也会介绍如何编写算法和解决问题。你会学习一系列的数据结构，并且解决各种经典问题。随着学习的深入，你将反复应用在各章中掌握的工具与技术。

致教师

许多学生在学到这个阶段时会发现，计算机科学除了编程以外还有很多内容。数据结构与算法可以独立于编程来学习和理解。

本书假定学生已经学过计算机科学的入门课程，但入门课程不一定是用Python讲解的。他们理解基本的结构体，比如分支、迭代以及函数定义，也接触过面向对象编程，并且能够创建和使用简单的类。同时，学生也能够理解Python的基础数据结构，比如序列（列表和字符串）以及字典。

本书有三大特点：

❏ 通过简单易读的文字而不引入太多编程语法，重点关注如何解决问题，从而向学生介绍基本的数据结构与算法；

❏ 较早介绍基于大O记法的算法分析，并且通篇运用；

❏ 使用Python讲解，以促使初学者能够使用和掌握数据结构与算法。

学生将首先学习线性数据结构，包括栈、队列、双端队列以及列表。我们用Python列表以及链表实现这些数据结构。然后学习与树有关的非线性数据结构，了解连接节点和引用结构（链表）等一系列技术。最后，学生将通过运用链式结构、链表以及Python字典的实现，学习图的相关知识。对于每一种结构，本书都尽力在使用Python提供的內建数据类型的同时展现众多的实现技巧。这种讲法在向学生揭示各种主要实现方法的同时，也强调Python的易用性。

Python是一门非常适合于讲解算法的语言，语法干净简洁，用户环境直观，基本的数据类型十分强大和易用。其交互性在不需要额外编写驱动函数的情况下为测试数据结构单元提供了直观环境。而且，Python为算法提供了教科书式的表示法，基本上不需要再用伪代码。这一特性有助于通过数据结构与算法来描述众多与之有关、相当有趣的现代问题。

我们相信，对于初学者来说，投入时间学习与算法和数据结构相关的基本思想是非常有益的。我们也相信，Python是一门教授初学者入门的优秀语言。其他许多语言要求学生学习非常高级的编程概念，这会阻碍他们掌握真正需要的基础知识，从而可能导致失败，而这样的失败并不是计算机科学本身造成的，而是由于所使用的语言不当。我们的目标是提供一本教科书，量体裁衣般地聚焦于他们需要掌握的内容，以他们能理解的方式编写，创造和发展一个有助于他们成功的环境。

本书结构

本书紧紧地围绕着运用经典数据结构和技术来解决问题。下面的组织结构图展示了充分利用本书的不同方式。

第1章做一些背景知识的准备，我们来复习一下计算机科学、问题解决、面向对象编程以及Python。基础扎实的学生可以跳过第1章，直接学习第2章。不过，正所谓温故而知新，适当的复习和回顾必然是值得的。

第2章介绍算法分析的内在思想，重点讲解大O记法，还将分析本书一直使用的重要Python数据结构。这可以帮助学生理解如何权衡各种抽象数据类型的不同实现。第2章也包含了在运行时使用的Python原生类型的实验测量例子。

第3～7章全面介绍在经典计算机科学问题中出现的数据结构与算法。尽管在阅读顺序上并无严格要求，但是许多话题之间都存在一定的依赖关系，所以应该按照本书的顺序学习。比如，第3章介绍栈，第4章利用栈解释递归，第5章利用递归实现二分搜索。

第8章是选学内容，包含彼此独立的几节。每一节都与之前的某一章有关。正如前面的组织结构图所示，你既可以在学习完第7章以后再一起学习第8章中的各节内容，也可以把它们与对应的那一章放在一起学习。例如，希望更早介绍数组的教师，可以在讲完第3章以后直接跳到8.2节。

新版改进

❏ 所有的代码都用Python 3.2写成。

❏ 第1章介绍Python的集合以及异常处理。

❏ 不再使用第三方绘图包。新版中的所有图形都通过原生的turtle模块绘制。

❏ 新加的第2章着重讲解算法分析。此外，这一章还包括对全书出现的关键Python数据结构的分析。

❏ 第3章新增了关于链表实现的一节。

❏ 将“动态规划”一节移到了第4章的最后。

❏ 更关注图递归算法，包括递归树绘制以及递归迷宫搜索程序。

❏ 所有的数据结构源代码都被放在一个Python包中，方便学生在完成作业时使用。

❏ 新版包含各章例子的完整源代码，从而避免了从各处复制代码的麻烦。

❏ 第6章改进了二叉搜索树。

❏ 第6章新增了关于平衡二叉树的一节。

❏ 第8章介绍C风格的数组和数组管理。

致谢

在完成本书的过程中，我们得到了众多朋友的帮助。感谢我们的同事Steve Hubbard为本书的第1版提供了大量的反馈，并为新版提供了众多新素材。感谢各地的同事给我们发邮件指出第1版存在的错误，并且为新版内容提供意见。

感谢迪科拉市Java John's咖啡馆的朋友Mary和Bob，以及其他服务员，他们允许我俩在Brad休假期间成为店里的“常驻作者”。David在常驻咖啡馆写书的那几个月中竟然没有成为咖啡爱好者。对了，在一间店名带Java的咖啡馆里写一本Python的书，确实有点讽刺。

感谢Franklin, Beedle & Associates出版公司的各位员工，特别是Jim Leisy和Tom Sumner。与他们的合作非常愉快。最后，还要特别感谢我们两人的妻子Jane Miller和Brenda Ranum。她们的爱与支持使得本书终成现实。

电子书

扫描如下二维码，即可购买本书电子版。

布拉德利·米勒（Bradley N. Miller）

戴维·拉努姆（David L. Ranum）