前言

本书用于高等院校的数据结构课程。Python是一门可以作为入门课程的优秀的计算机语言。它相对简单的语法能够让学生更加专注于解决问题，而不用把很多精力放在对具体的编程语言的语法的理解上。Python的内置数据结构和大型标准库还能够让学生比用其他语言更简便地编写一些更有趣的程序。本书假设学生已经学习了Python的基本语法，并且已经接触过类的用法。大多数使用Python的传统编程导论课程都涵盖了这些基础的内容，有些课程甚至可能涵盖了这本书里所涉及的一些主题。

Python的面向对象特性，让它成为一种非常适合用来学习数据结构课程的语言。我们发现，大多数学习完编程导论课程的学生都已经知道了如何使用类，但是他们中的许多人还需要更多的知识和经验，来学习如何设计和编写自己的类。考虑到在编程导论课程里用来学习设计类的时间非常有限，这样的情形并不奇怪。我们可以通过学习本书前几章里包含的一些关于类的设计的例子来解决这个问题。

学生在数据结构课程里学习使用Python语言，可以继续扩展他们的知识和技能，并且能够通过一种更简单、更熟悉的语言来获得设计和编写类的经验。Python语言也使得学习链式结构变得相对更容易，这是因为Python里的每个名称都是一个引用。因此如果要编写链式结构，学生不用再去学习其他的语法。与学习使用更复杂的语言相比，这些优势能够让主题内容的教学速度更快。

把Python用于数据结构课程的一个潜在缺点是：它隐藏了内存管理的复杂性。这个特性在学习第1门课程的时候是一个优势，但我们认为在学习第2门课程时，学生应该需要开始理解Python解释器隐藏的底层级细节了，这也是非常重要的内容。由于我们学习的是Python，因此可以在更短的时间内完成对基本数据结构的相关内容和知识的掌握。也就是说即使在只需要一个学期的数据结构课程里，学生也是有时间去学习第2种编程语言的。在学生不断提高他们的Python编程技能，并同时学习了本书的前几章之后，他们可以相对更容易地去学习第2种面向对象的编程语言。通过使用C++作为第2种编程语言，学生将接触到比较底层的编译语言。C++的语法比Python更复杂，但是好在学生通过Python的学习已经掌握了基本的编程概念，这使得学习C++的语法不会有非常大的障碍。例如，既然他们已经理解了编程的基本概念以及各个语句（如条件语句和循环语句）的语义，那么他们也就只用重点学习一下这些语句在C++中的语法就行了。

一旦学生学习了基本的C++语法，就可以通过在C++里重写链式结构来涵盖动态内存管理的概念。这部分内容会对基本的数据结构概念进行加强，同时也会开始关注内存管理问题。本书无意提供C++语言的完整介绍，只会引入C++语言的一个比较大的子集，从而方便学生理解内存管理的底层细节，并学会在C++里编写面向对象的代码。在介绍了C++语言的基础知识之后，本书还会提供Python实现，让学生用C++来实现它们，从而介绍一些更高级的数据结构。换句话说，Python代码成了用来呈现关键算法和数据结构的可执行的伪代码。

教学过程

由于Python能够让我们比其他语言更快地学习完主题内容，因此数据结构课程中用5个学分就可以学完本书的大部分内容。如果用两个学期来教学整本书，每个学期的课程就只需要3个学分。在这两个学期，每个学期3个学分的数据结构课程安排如下：前7章的内容在8周内完成；然后在剩下的7周里完成前3章关于C++的内容，从而让学生有足够的时间来编写大量的C++代码；之后剩下的5章将在第2个学期的3个学分课程里进行详细的介绍。因此，教师可以在课程开始的时候，先进行一周的复习，用更多的时间来讨论在最后3章里提到的高级算法和数据结构。

根据学生使用面向对象编程的经验，本书前3章的教学进度可以安排得很快，也可以更详细地阐述。第1章介绍算法的渐进运行时分析，从而让我们可以分析所有数据结构实现的运行时间。本书较早地介绍了一个Python的单元测试框架，从而可以方便学生比较正式地测试他们的代码。在完成第4章的链式结构的讨论之后，教师可以比较快地介绍一下堆栈和队列的基本概念，或者也可以通过提供的示例应用程序来继续介绍各个算法，以及加强设计技能的教学。虽然一些编程导论课程已经涵盖了递归，但大多数学生在第一次学习的时候，并不能够完全地理解递归。由于对树的研究需要用到递归的概念，因此本书会在第7章的树的内容之前插入关于递归内容的一章（第6章）。

在关于树的一章之后，本书内容就会切换到C++语言。第8章在基于读者已经了解掌握了Python的情况下，开始对C++进行简单的介绍。第9章介绍在C++里编写和使用类的相关细节。第10章和第11章介绍动态内存以及在C++里如何编写链式结构。我们强烈建议读者按顺序来学习第8章到第11章。第12章介绍使用和编写C++模板代码的基础知识，但并没有完全覆盖模板的所有相关内容。由于其他的章节都不需要理解模板，读者也可以选择跳过第12章。最后3章介绍了一些高级算法和数据结构。虽然这3章之间会有一些相互的参考，但是它们可以任意调换顺序。

致谢

我们要感谢维滕贝格大学（Wittenberg University）的Nancy Saks和Steve Bogaerts对本书C++章节的早期草稿版本的意见。我们还要感谢Franklin, Beedle& Associates出版社，尤其是Jim Leisy和Tom Sumner。我们还要感谢我们的编辑Stephanie Welch，他发现了许多小错误，帮助我们提高了这本书的质量。

David感谢美国Capital大学提供了休假的支持，这让他开始了这本书的编著。David还要感谢那些使用了本书早期草稿版本，并且提出改进建议的学生们。以下这些美国Capital大学的学生因为提出了很多的合理化建议而值得得到特别认可：Kyle Beal、Michael Herold、Jeff Huenemann、John Larison以及Brenton Wolfe。最后，David要感谢他的妻子Sherri在他完成本书所需的无数个小时里给予的支持和理解。

John感谢他在沃特伯格大学（Wartburg College）的部门的同事们，他们一直为他的努力写作提供支持；也要感谢他的学生们，他们帮助John“尝试体验”了一些学习材料。最重要的是，John感谢他的家人，特别是他的妻子Elizabeth Bingham，感谢她的爱、支持和理解，让这个项目成为可能。