本书采用Python语言介绍数据结构和算法，包括其设计、分析和实施。本书源代码简洁、明确，面向对象的观点贯穿始终，通过继承最大限度地提高代码重用，同时彰显不同抽象数据类型和算法之间的异同。
无
高效数据结构的设计与分析，长期以来一直被认为是计算领域的一个重要主题，同时也是计算机科学与计算机工程本科教学中的核心课程。本书介绍数据结构和算法，包括其设计、分析和实现，可在初级数据结构或中级算法导论课程中使用。我们随后会更详细地讨论如何在这些课程中使用本书。
为了提高软件开发的健壮性和可重用性，我们在本书中采取一致的面向对象的视角。面向对象方法的一个主要思想是数据应该被封装，然后提供访问和修改它们的方法。我们不能简单地将数据看作字节和地址的集合，数据对象是抽象数据类型（Abstract Data Type，ADT）的实例，其中包括可在这种类型的数据对象上执行的操作方法的集合。我们强调的是对于一个特定的ADT可能有几种不同的实现策略，并探讨这些选择的优点和缺点。我们几乎为书中的所有数据结构和算法都提供了完整的Python实现，并介绍了将这些实现组织为可重用的组件所需的重要的面向对象设计模式。
通过阅读本书，读者可以：
对常见数据集合的抽象有一定了解（如栈、队列、表、树、图）。
理解生成常用数据结构的高效实现的算法策略。
通过理论方法和实验方法分析算法的性能，并了解竞争策略之间的权衡。
明智地利用编程语言库中已有的数据结构和算法。
拥有大多数基础数据结构和算法的具体实现经验。
应用数据结构和算法来解决复杂的问题。
为了达到最后一个目标，我们在书中提供了数据结构的很多应用实例，包括：文本处理系统，结构化格式（如HTML）的标签匹配，简单的密码技术，文字频率分析，自动几何布局，霍夫曼编码，DNA序列比对，以及搜索引擎索引。
本书特色
本书主要基于由Goodrich和Tamassia所著的《Data Structures and Algorithms in Java》，以及由Goodrich、Tamassia和Mount所著的《Data Structures and Algorithms in C++》编写而成。然而，我们并不是简单地用Python语言实现以上书籍的内容。为了充实内容，我们重新设计了本书：
对全部代码进行了重新设计，以充分利用Python的优势，如使用生成器迭代集合的元素。
在Java和C++版本中，我们提供了很多伪代码，而本书则提供了Python实现的完整代码。
在一般情况下，ADT被定义为与Python内建数据类型和Python的collections模块具有一致的接口。
第5章深入探讨了Python中基于动态数组的内置数据结构，如list、tuple和str类。新增的附录A提供了关于str类功能的进一步讲解。
重新绘制或修改了超过450幅插图。
经过新增和修订，练习的总数达到750个。
在线资源
本书提供一系列丰富的在线资源，可访问以下网站获取：
www.wiley.com/college/goodrich
鼓励学生在学习本书时使用这个网址，以更有效地进行练习并提高对所学知识的认识。也欢迎教师使用本网站来帮助规划、组织和展示他们的课程材料。对于教师和学生而言，网站中包含一系列与本书主题相关的教学资源，由于它们是有附加价值的，所以一些网上资源受密码保护。
对于所有的读者，尤其是学生，我们有以下资源：
书中所有Python程序的源代码。
提供给教师的PDF讲义版PPT（每页四张）。
保存所有练习提示的数据库，以练习的编号为索引。
对于使用本书的教师，我们有以下额外的教学辅助资源：
本书练习的答案。
书中所有图形和插图的彩色版本。
PPT和PDF版本的幻灯片，其中PDF版本为每页一张。
PPT是完全可编辑的，教师可根据自己的课程需求进行修改。在教师使用本书作为教材时，所有的在线资源不收取额外费用。
内容和组织
书中各章节的内容循序渐进，适于教学。从Python编程和面向对象设计的基础开始，然后逐渐增加如算法分析和递归之类的基础技术。在本书的主体部分中，我们展示了基本的数据结构和算法，并且包括对内存管理的讨论（也是数据结构的架构基础）。本书的章节安排如下：
第1章 Python入门
第2章 面向对象编程
第3章 算法分析
第4章 递归
第5章 基于数组的序列
第6章 栈、队列和双端队列
第7章 链表
第8章 树
第9章 优先级队列
第10章 映射、哈希表和跳跃表
第11章 搜索树
第12章 排序与选择
第13章 文本处理
第14章 图算法
第15章 内存管理和B树
附录A Python中的字符串
附录B 有用的数学定理
预备知识
我们假设读者至少接触过一种高级语言，如C、C++、Python或Java，可以理解相关高级语言的主要概念，包括：
变量和表达式。
决策结构（if语句和switch语句）。
迭代结构（for循环和while循环）。
函数（无论是过程式方法还是面向对象方法）。
对于已经熟悉这些概念但还不清楚如何在Python中应用的读者，我们建议将第1章作为Python语言的入门。这本书主要讨论数据结构，而不是讲解Python，因此并没有详尽介绍Python。
直到第2章才开始使用Python中的面向对象编程，这一章对于那些Python新手以及熟悉Python但不熟悉面向对象编程的人都是有用的。
就数学背景而言，我们假定读者多少熟悉些高中数学知识。即便如此，在第3章中，我们先讨论了算法分析的7个最重要的功能。若所涉及的内容超出了这7个功能，则作为可选章节，用星号（*）标记。附录B对其他有用的数学定理做了总结，包括初等概率等。
计算机科学课程的设计
为了帮助教师在IEEE/ACM 2013的框架下设计教学课程，下表描述了本书涵盖的知识要点。
知识要点 相关章节
AL/基本分析 第3章，4.2节，12.2.4节
AL/算法策略 12.2.1节，13.2.1节，13.3节，13.4.2节
AL/基本数据结构与算法 4.1.3节，5.5.2节，9.4.1节，9.3节，10.2节，11.1节，13.2节，第12章，第14章的大部分内容
AL/高级数据结构 5.3节，10.4节，11.2～11.6节，12.3.1节，13.5节，14.5节，15.3节
AR/内存系统组织和架构 第15章
DS/集合、关系和功能 10.5.1节，10.5.2节，9.4节
DS/证明技巧 3.4节，4.2节，5.3.2节，9.3.6节，12.4.1节
DS/基础计数 2.4.2节，6.2.2节，12.2.4节，8.2.2节，附录B
DS/图和树 第8章和第14章的大部分内容
DS/离散概率 1.11节，10.2节，10.4.2节，12.3.1节
PL/面向对象编程 本书的大部分内容，特别是第2章以及7.4节、9.5.1节、10.1.3节和11.2节
PL/函数式编程 1.10节
SDF/算法和设计 2.1节，3.3节，12.2.1节
SDF/基本编程概念 第1章，第4章
SDF/基本数据结构 第6章，第7章，附录A，1.2.1节，5.2节，5.4节，9.1节，10.1节
SDF/开发方法 1.7节，2.2节
SE/软件设计 2.1节，2.1.3节
计算机\数据结构
继C、C++、Java之后，采用Python语言讲解数据结构与算法成为国内外高校的新选择。相比于同类教材，本书并非简单地替换了代码部分，而是根据Python的特点重新规划篇章结构，从而更加符合教学需求。本书要求读者具备一定的高级语言基础，快速入门Python后便进入核心思想——面向对象编程，接着重点讲解栈、队列、表、树和图等内容，同时涵盖文本处理、DNA序列比对和搜索引擎索引等大量实例。
本书特色
·强调面向对象思想，关注抽象数据类型及其算法实现策略，通过理论方法和实验方法分析算法性能，学会比较和权衡不同策略。
·基于Python3标准，对于书中讨论的数据结构均给出了完整的Python实现代码而非伪代码，并提供全部源代码的免费下载。
·包含约500幅精心设计的插图，易于读者理解抽象概念；以及超过750道练习题，便于读者巩固知识、发散思维或开展项目实践。
[美]迈克尔·T. 古德里奇（Michael T. Goodrich） 罗伯托·塔马西亚（Roberto Tamassia） 迈克尔·H.戈德瓦瑟(Michael H. Goldwasser) 著：迈克尔·T. 古德里奇（Michael T. Goodrich） 加州大学欧文分校计算机科学系教授，之前是约翰·霍普金斯大学教授。他是AAAS、ACM和IEEE会士，曾荣获IEEE计算机协会技术成就奖和ACM卓越服务奖等。
罗伯托·塔马西亚（Roberto Tamassia） 布朗大学计算机科学系教授及系主任，兼任几何计算中心主任。他是AAAS、ACM和IEEE会士，曾荣获IEEE计算机协会技术成就奖。
迈克尔·H.戈德瓦瑟(Michael H. Goldwasser) 圣路易斯大学数学系和计算机科学系教授，兼任计算机科学项目主任，之前曾在芝加哥罗耀拉大学任教。
数据结构是计算机科学与技术专业的核心课程，是程序设计、编译原理、数据库等课程的基础。对于从事计算机应用尤其是软件开发的工程技术人员而言，掌握数据结构的相关知识和常用算法，对提高开发效率和编程质量都有着非常重要的作用。国内外有很多优秀的数据结构教材，而且有基于C、C++、Java等多种程序设计语言编写的版本，但是采用Python语言描述的并不多见。
Python是一种面向对象的直译式计算机程序设计语言，语法简洁清晰，类库丰富强大。由于代码的平台无关性以及极简的编程思想，Python近年来成为国内外各大科研院校和IT企业在教学活动、科学研究以及应用软件开发中频繁使用的程序设计语言。例如，卡内基·梅隆大学的编程基础课程、麻省理工学院的计算机科学及编程导论课程就使用Python语言讲授。我们西北工业大学也开设了Python程序设计的选修课，受到学生的热烈欢迎。在实践领域，NumPy、SciPy等是利用Python语言开发的用于科学计算的工具包，著名的计算机视觉库OpenCV、三维可视化库VTK等也是使用Python开发的。在TIOBE编程语言排行榜上，Python排名第五，排在Java、C、C++和C#之后。Python语言也在大数据分析、网络爬虫、量化投资等新兴热点领域广泛使用。
对于计算机专业的学生和计算机应用行业的从业人员而言，从Python开始学习程序设计和数据结构入门门槛低，学习曲线平缓。国内已有大量介绍Python程序设计的书籍，但多局限在Python语法和特定软件包的使用方面。本书是难得的系统讲解如何使用Python语言设计并实现数据结构和基本算法的书籍。
本书作者Goodrich教授、Tamassia教授等人先后撰写了《Data Structures and Algorithms in Java》和《Data Structures and Algorithms in C++》等书籍，对数据结构和常用算法的理解非常透彻。但本书并不是简单地将这些书籍中的代码描述部分替换成Python语言，而是充分利用Python语言的优势，以完整代码的方式实现了各种算法和数据结构。在此基础上，还大量介绍了Python语言内建的数据类型和一些常用基本库及接口的相关知识。
书中介绍的数据结构和算法包括完整的设计、分析和实现过程，非常适合作为初级数据结构课程的教材，同时也可以作为中级算法导论课程的教材，或作为计算机基础知识有限的工程技术人员的参考书。通过学习本书，读者能够更加灵活、高效地运用Python语言编写满足自己需求的程序。
非常荣幸能有机会翻译这样一本优秀的教材。对于书中的专业术语，我们尽量沿用了现有的习惯翻译。不过由于时间和水平所限，难免出现错误和不当之处，恳切希望广大读者不吝批评指正。
最后，感谢作者为我们呈现了一本优秀的教材；感谢出版社的信任，将这项有趣而又有意义的工作交给我们完成；还要感谢所有参与本书翻译和校对工作的教师和研究生，他们是赵晓南、王蕾、赵楠、陈震、卜海龙、柳春懿、孔兰昕、朱顺意等。
张晓
2018年4月
于启真湖畔
出版者的话
译者序
前言
致谢
作者简介
第1章 Python入门 1
1.1 Python概述 1
1.1.1 Python解释器 1
1.1.2 Python程序预览 1
1.2 Python对象 2
1.2.1 标识符、对象和赋值语句 2
1.2.2 创建和使用对象 4
1.2.3 Python的内置类 4
1.3 表达式、运算符和优先级 8
1.4 控制流程 12
1.4.1 条件语句 12
1.4.2 循环语句 14
1.5 函数 16
1.5.1 信息传递 17
1.5.2 Python的内置函数 19
1.6 简单的输入和输出 20
1.6.1 控制台输入和输出 21
1.6.2 文件 21
1.7 异常处理 22
1.7.1 抛出异常 23
1.7.2 捕捉异常 24
1.8 迭代器和生成器 26
1.9 Python的其他便利特点 28
1.9.1 条件表达式 29
1.9.2 解析语法 29
1.9.3 序列类型的打包和解包 30
1.10 作用域和命名空间 31
1.11 模块和import语句 32
1.12 练习 34
扩展阅读 36
第2章 面向对象编程 37
2.1 目标、原则和模式 37
2.1.1 面向对象的设计目标 37
2.1.2 面向对象的设计原则 38
2.1.3 设计模式 39
2.2 软件开发 40
2.2.1 设计 40
2.2.2 伪代码 41
2.2.3 编码风格和文档 42
2.2.4 测试和调试 43
2.3 类定义 44
2.3.1 例子：CreditCard类 45
2.3.2 运算符重载和Python的特殊方法 48
2.3.3 例子：多维向量类 50
2.3.4 迭代器 51
2.3.5 例子：Range类 52
2.4 继承 53
2.4.1 扩展CreditCard类 54
2.4.2 数列的层次图 57
2.4.3 抽象基类 60
2.5 命名空间和面向对象 62
2.5.1 实例和类命名空间 62
2.5.2 名称解析和动态调度 65
2.6 深拷贝和浅拷贝 65
2.7 练习 67
扩展阅读 70
第3章 算法分析 71
3.1 实验研究 71
3.2 本书使用的7种函数 74
3.2.1 常数函数 74
3.2.2 对数函数 74
3.2.3 线性函数 75
3.2.4 n-log-n函数 75
3.2.5 二次函数 76
3.2.6 三次函数和其他多项式 77
3.2.7 指数函数 77
3.2.8 比较增长率 79
3.3 渐近分析 79
3.3.1 大O符号 80
3.3.2 比较分析 82
3.3.3 算法分析示例 84
3.4 简单的证明技术 89
3.4.1 示例 89
3.4.2 反证法 89
3.4.3 归纳和循环不变量 90
3.5 练习 91
扩展阅读 95
第4章 递归 96
4.1 说明性的例子 96
4.1.1 阶乘函数 96
4.1.2 绘制英式标尺 97
4.1.3 二分查找 99
4.1.4 文件系统 101
4.2 分析递归算法 104
4.3 递归算法的不足 106
4.4 递归的其他例子 109
4.4.1 线性递归 109
4.4.2 二路递归 112
4.4.3 多重递归 113
4.5 设计递归算法 114
4.6 消除尾递归 115
4.7 练习 116
扩展阅读 118
第5章 基于数组的序列 119
5.1 Python序列类型 119
5.2 低层次数组 119
5.2.1 引用数组 121
5.2.2 Python中的紧凑数组 122
5.3 动态数组和摊销 124
5.3.1 实现动态数组 126
5.3.2 动态数组的摊销分析 127
5.3.3 Python列表类 130
5.4 Python序列类型的效率 130
5.4.1 Python的列表和元组类 130
5.4.2 Python的字符串类 134
5.5 使用基于数组的序列 136
5.5.1 为游戏存储高分 136
5.5.2 为序列排序 138
5.5.3 简单密码技术 140
5.6 多维数据集 142
5.7 练习 145
扩展阅读 147
第6章 栈、队列和双端队列 148
6.1 栈 148
6.1.1 栈的抽象数据类型 148
6.1.2 简单的基于数组的栈实现 149
6.1.3 使用栈实现数据的逆置 152
6.1.4 括号和HTML标记匹配 152
6.2 队列 155
6.2.1 队列的抽象数据类型 155
6.2.2 基于数组的队列实现 156
6.3 双端队列 160
6.3.1 双端队列的抽象数据类型 160
6.3.2 使用环形数组实现双端队列 161
6.3.3 Python collections模块中的双端队列 162
6.4 练习 163
扩展阅读 165
第7章 链表 166
7.1 单向链表 166
7.1.1 用单向链表实现栈 169
7.1.2 用单向链表实现队列 171
7.2 循环链表 173
7.2.1 轮转调度 173
7.2.2 用循环链表实现队列 174
7.3 双向链表 175
7.3.1 双向链表的基本实现 177
7.3.2 用双向链表实现双端队列 179
7.4 位置列表的抽象数据类型 180
7.4.1 含位置信息的列表抽象数据类型 182
7.4.2 双向链表实现 183
7.5 位置列表的排序 186
7.6 案例研究：维护访问频率 186
7.6.1 使用有序表 187
7.6.2 启发式动态调整列表 188
7.7 基于链接的序列与基于数组的序列 190
7.8 练习 192
扩展阅读 195
第8章 树 196
8.1 树的基本概念 196
8.1.1 树的定义和属性 196
8.1.2 树的抽象数据类型 199
8.1.3 计算深度和高度 201
8.2 二叉树 203
8.2.1 二叉树的抽象数据类型 204
8.2.2 二叉树的属性 206
8.3 树的实现 207
8.3.1 二叉树的链式存储结构 207
8.3.2 基于数组表示的二叉树 212
8.3.3 一般树的链式存储结构 214
8.4 树的遍历算法 214
8.4.1 树的先序和后序遍历 214
8.4.2 树的广度优先遍历 216
8.4.3 二叉树的中序遍历 216
8.4.4 用Python实现树遍历 217
8.4.5 树遍历的应用 220
8.4.6 欧拉图和模板方法模式* 223
8.5 案例研究：表达式树 227
8.6 练习 230
扩展阅读 235
第9章 优先级队列 236
9.1 优先级队列的抽象数据类型 236
9.1.1 优先级 236
9.1.2 优先级队列的抽象数据类型的实现 236
9.2 优先级队列的实现 237
9.2.1 组合设计模式 237
9.2.2 使用未排序列表实现优先级队列 238
9.2.3 使用排序列表实现优先级队列 239
9.3 堆 241
9.3.1 堆的数据结构 241
9.3.2 使用堆实现优先级队列 242
9.3.3 基于数组的完全二叉树表示 244
9.3.4 Python的堆实现 246
9.3.5 基于堆的优先级队列的分析 248
9.3.6 自底向上构建堆* 248
9.3.7 Python的heapq模块 251
9.4 使用优先级队列排序 252
9.4.1 选择排序和插入排序 253
9.4.2 堆排序 254
9.5 适应性优先级队列 255
9.5.1 定位器 256
9.5.2 适应性优先级队列的实现 256
9.6 练习 259
扩展阅读 263
第10章 映射、哈希表和跳跃表 264
10.1 映射和字典 264
10.1.1 映射的抽象数据类型 264
10.1.2 应用：单词频率统计 266
10.1.3 Python的MutableMapping抽象基类 267
10.1.4 我们的MapBase类 267
10.1.5 简单的非有序映射实现 268
10.2 哈希表 269
10.2.1 哈希函数 270
10.2.2 哈希码 271
10.2.3 压缩函数 274
10.2.4 冲突处理方案 274
10.2.5 负载因子、重新哈希和效率 276
10.2.6 Python哈希表的实现 278
10.3 有序映射 281
10.3.1 排序检索表 282
10.3.2 有序映射的两种应用 286
10.4 跳跃表 288
10.4.1 跳跃表中的查找和更新操作 289
10.4.2 跳跃表的概率分析* 292
10.5 集合、多集和多映射 294
10.5.1 集合的抽象数据类型 294
10.5.2 Python的MutableSet抽象基类 295
10.5.3 集合、多集和多映射的实现 297
10.6 练习 298
扩展阅读 302
第11章 搜索树 303
11.1 二叉搜索树 303
11.1.1 遍历二叉搜索树 303
11.1.2 搜索 305
11.1.3 插入和删除 306
11.1.4 Python实现 307
11.1.5 二叉搜索树的性能 311
11.2 平衡搜索树 312
11.3 AVL树 316
11.3.1 更新操作 318
11.3.2 Python实现 320
11.4 伸展树 322
11.4.1 伸展 322
11.4.2 何时进行伸展 323
11.4.3 Python实现 324
11.4.4 伸展树的摊销分析* 325
11.5 （2，4）树 328
11.5.1 多路搜索树 328
11.5.2 （2，4）树的操作 330
11.6 红黑树 334
11.6.1 红黑树的操作 335
11.6.2 Python实现 341
11.7 练习 343
扩展阅读 348
第12章 排序与选择 349
12.1 为什么要学习排序算法 349
12.2 归并排序 349
12.2.1 分治法 349
12.2.2 基于数组的归并排序的实现 351
12.2.3 归并排序的运行时间 353
12.2.4 归并排序与递归方程* 354
12.2.5 归并排序的可选实现 355
12.3 快速排序 357
12.3.1 随机快速排序 361
12.3.2 快速排序的额外优化 362
12.4 再论排序：算法视角 364
12.4.1 排序下界 365
12.4.2 线性时间排序：桶排序和基数排序 366
12.5 排序算法的比较 367
12.6 Python的内置排序函数 369
12.7 选择 370
12.7.1 剪枝搜索 370
12.7.2 随机快速选择 371
12.7.3 随机快速选择分析 371
12.8 练习 372
扩展阅读 376
第13章 文本处理 377
13.1 数字化文本的多样性 377
13.2 模式匹配算法 378
13.2.1 穷举 378
13.2.2 Boyer-Moore算法 379
13.2.3 Knuth-Morris-Pratt算法 382
13.3 动态规划 385
13.3.1 矩阵链乘积 385
13.3.2 DNA和文本序列比对 386
13.4 文本压缩和贪心算法 389
13.4.1 霍夫曼编码算法 390
13.4.2 贪心算法 391
13.5 字典树 391
13.5.1 标准字典树 391
13.5.2 压缩字典树 394
13.5.3 后缀字典树 395
13.5.4 搜索引擎索引 396
13.6 练习 397
拓展阅读 400
第14章 图算法 401
14.1 图 401
14.2 图的数据结构 405
14.2.1 边列表结构 406
14.2.2 邻接列表结构 407
14.2.3 邻接图结构 408
14.2.4 邻接矩阵结构 409
14.2.5 Python实现 409
14.3 图遍历 412
14.3.1 深度优先搜索 413
14.3.2 深度优先搜索的实现和扩展 416
14.3.3 广度优先搜索 419
14.4 传递闭包 421
14.5 有向非循环图 424
14.6 最短路径 426
14.6.1 加权图 427
14.6.2 Dijkstra算法 428
14.7 最小生成树 434
14.7.1 Prim-Jarník算法 435
14.7.2 Kruskal算法 438
14.7.3 不相交分区和联合查找结构 442
14.8 练习 445
扩展阅读 451
第15章 内存管理和B树 452
15.1 内存管理 452
15.1.1 内存分配 452
15.1.2 垃圾回收 453
15.1.3 Python解释器使用的额外内存 455
15.2 存储器层次结构和缓存 456
15.2.1 存储器系统 456
15.2.2 高速缓存策略 456
15.3 外部搜索和B树 460
15.3.1 （a，b）树 460
15.3.2 B树 462
15.4 外部存储器中的排序 462
15.5 练习 464
拓展阅读 465
附录A Python中的字符串 466
附录B 有用的数学定理 469
参考文献 474
