数据结构与算法 Python语言实现

本书采用Python语言介绍数据结构和算法，包括其设计、分析和实施。本书源代码简洁、明确，面向对象的观点贯穿始终，通过继承优选限度地提高代码重用，同时彰显不同抽象数据类型和算法之间的异同。

迈克尔·T.古德里奇（Michael T.Goodrich）加州大学欧文分校计算机科学系教授，之前是约翰·霍普金斯大学教授。他是AAAS、ACM和IEEE会士，曾荣获IEEE计算机协会技术成就奖和ACM很好服务奖等。
罗伯托·塔马西亚（Roberto Tamassia）布朗大学计算机科学系教授及系主任，兼任几何计算中心主任。他是AAAS、ACM和IEEE会士，曾荣获IEEE计算机协会技术成就奖。
迈克尔·H.戈德瓦瑟(Michael H.Goldwasser)圣路易斯大学数学系和计算机科学系教授，兼任计算机科学项目主任，之前曾在芝加哥罗耀拉大学任教。

   出版者的话

译者序

前言

致谢

作者简介

第1章Python入门1

1.1Python概述1

1.1.1Python解释器1

1.1.2Python程序预览1

1.2Python对象2

1.2.1标识符、对象和赋值语句2

1.2.2创建和使用对象4

1.2.3Python的内置类4

1.3表达式、运算符和优先级8

1.4控制流程12

1.4.1条件语句12

1.4.2循环语句14

1.5函数16

1.5.1信息传递17

1.5.2Python的内置函数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.9Python的其他便利特点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.4n-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.1Python序列类型119

5.2低层次数组119

5.2.1引用数组121

5.2.2Python中的紧凑数组122

5.3动态数组和摊销124

5.3.1实现动态数组126

5.3.2动态数组的摊销分析127

5.3.3Python列表类130

5.4Python序列类型的效率130

5.4.1Python的列表和元组类130

5.4.2Python的字符串类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.3Pythoncollections模块中的双端队列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

……