数据结构 Python语言描述 第2版

图书标准信息

• 作者 [美]肯尼思· A.兰伯特（Kenneth A. Lambert）
• 出版社 人民邮电出版社
• 出版时间 2021-07
• 版次 2
• ISBN 9787115551481
• 定价 119.90元
• 装帧 其他
• 开本 其他
• 纸张 胶版纸
• 页数 326页
• 字数 502千字

【内容简介】

本书用 Python 语言来讲解数据结构及实现方法。全书首先概述 Python 编程的功能—这些功能是实际编程和解决问题时所必需的；其次介绍抽象数据类型的规范、实现和应用，多项集类型，以及接口和实现之间的重要差异；随后介绍线性多项集、栈、队列和列表；后介绍树、图等内容。本书附有大量的复习题和编程项目，旨在帮助读者巩固所学知识。
  本书不仅适合高等院校计算机专业师生阅读，也适合对 Python 感兴趣的读者和程序员阅读。

【作者简介】

肯尼思·A. 兰伯特（Kenneth A. Lambert）是一名计算机科学教授，也是美国华盛顿与李大学（Washington and Lee University）计算机科学系的系主任。他教授“程序设计概论”课程已有 30 多年，并且一直是计算机科学教育领域的活跃研究者。Lambert 自行撰写或与他人合著的书多达 28 本，包括一系列 Python 的入门图书、与 Douglas Nance 和 Thomas Naps一起编写的一系列 C  的入门图书、与 Martin Osborne 一起编写的一系列 Java 的入门图书，等等。

【目录】

第 1章 Python编程基础1

1.1 基本程序要素1

1.1.1 程序和模块1

1.1.2 Python的示例程序：猜数字2

1.1.3 编辑、编译并运行Python程序3

1.1.4 程序注释3

1.1.5 词法元素3

1.1.6 拼写和命名惯例4

1.1.7 语法元素4

1.1.8 字面值4

1.1.9 运算符和表达式5

1.1.10 函数调用5

1.1.11 print函数6

1.1.12 input函数6

1.1.13 类型转换函数和混合模式操作6

1.1.14 可选和关键字函数参数6

1.1.15 变量和赋值语句7

1.1.16 Python的数据类型7

1.1.17 import语句7

1.1.18 获取关于程序组件的帮助8

1.2 控制语句8

1.2.1 条件语句9

1.2.2 使用if _name_ == \"_main_\"9

1.2.3 循环语句10

1.3 字符串及其运算11

1.3.1 运算符11

1.3.2 格式化字符串以便输出12

1.3.3 对象和方法调用13

1.4 Python内置的多项集及其操作14

1.4.1 列表14

1.4.2 元组15

1.4.3 遍历整个序列15

1.4.4 字典15

1.4.5 搜索一个值16

1.4.6 通过模式匹配来访问多项集16

1.5 创建新函数17

1.5.1 函数定义17

1.5.2 递归函数18

1.5.3 函数的嵌套定义19

1.5.4 高阶函数20

1.5.5 使用lambda表达式创建匿名函数21

1.6 捕获异常21

1.7 文件及其操作22

1.7.1 文本文件的输出23

1.7.2 将数字写入文本文件23

1.7.3 从文本文件读取文本24

1.7.4 从文件读取数据25

1.7.5 使用pickle读写对象26

1.8 创建新类27

1.9 编程项目29

第 2章 多项集的概述32

2.1 多项集类型32

2.1.1 线性多项集33

2.1.2 分层多项集33

2.1.3 图多项集33

2.1.4 无序多项集33

2.1.5 有序多项集34

2.1.6 多项集类型的分类34

2.2 多项集操作35

2.2.1 所有多项集类型中的基本操作35

2.2.2 类型转换36

2.2.3 克隆和相等性36

2.3 迭代器和高阶函数37

2.4 多项集的实现37

2.5 章节总结38

2.6 复习题39

2.7 编程项目40

第3章 搜索、排序以及复杂度分析41

3.1 衡量算法的效率41

3.1.1 衡量算法的运行时42

3.1.2 统计指令数43

3.1.3 衡量算法使用的内存45

3.2 复杂度分析45

3.2.1 复杂度的阶45

3.2.2 大O表示法47

3.2.3 比例常数的作用47

3.3 搜索算法48

3.3.1 最小值搜索48

3.3.2 顺序搜索列表49

3.3.3 最好情况、最坏情况以及平均情况下的性能49

3.3.4 基于有序列表的二分搜索50

3.3.5 比较数据元素51

3.4 基本的排序算法52

3.4.1 选择排序53

3.4.2 冒泡排序53

3.4.3 插入排序55

3.4.4 再论最好情况、最坏情况以及平均情况下的性能56

3.5 更快的排序57

3.5.1 快速排序57

3.5.2 归并排序60

3.6 指数复杂度的算法：递归斐波那契63

3.7 案例研究：算法分析器65

3.7.1 案例需求65

3.7.2 案例分析65

3.7.3 案例设计66

3.7.4 案例实现（编码）67

3.8 章节总结69

3.9 复习题70

3.10 编程项目71

第4章 数组和链接结构73

4.1 数组数据结构73

4.1.1 随机访问和连续内存75

4.1.2 静态内存和动态内存76

4.1.3 物理尺寸和逻辑尺寸76

4.2 数组的操作77

4.2.1 增大数组的尺寸77

4.2.2 减小数组的尺寸78

4.2.3 将元素插入增大的数组78

4.2.4 从数组里删除元素79

4.2.5 复杂度的权衡：时间、空间和数组80

4.3 二维数组（网格）81

4.3.1 使用网格81

4.3.2 创建并初始化网格82

4.3.3 定义Grid类82

4.3.4 参差不齐的网格和多维数组83

4.4 链接结构84

4.4.1 单向链接结构和双向链接结构84

4.4.2 非连续内存和节点85

4.4.3 定义单向链接节点类86

4.4.4 使用单向链接节点类87

4.5 单向链接结构上的操作88

4.5.1 遍历88

4.5.2 搜索89

4.5.3 替换90

4.5.4 在开始处插入90

4.5.5 在结尾处插入91

4.5.6 在开始处删除92

4.5.7 在结尾处删除93

4.5.8 在任意位置处插入94

4.5.9 在任意位置处删除95

4.5.10 复杂度的权衡：时间、空间和单向链接结构96

4.6 链接上的变化97

4.6.1 包含虚拟头节点的环状链接结构97

4.6.2 双向链接结构98

4.7 章节总结100

4.8 复习题101

4.9 编程项目102

第5章 接口、实现和多态104

5.1 开发接口104

5.1.1 设计包接口105

5.1.2 指定参数和返回值106

5.2 构造函数和类的实现107

5.2.1 前置条件、后置条件、异常和文档107

5.2.2 在Python里编写接口108

5.3 开发基于数组的实现110

5.3.1 选择并初始化数据结构110

5.3.2 先完成简单的方法111

5.3.3 完成迭代器112

5.3.4 完成使用迭代器的方法112

5.3.5 in运算符和_contains_方法113

5.3.6 完成remove方法113

5.4 开发基于链接的实现114

5.4.1 初始化数据结构115

5.4.2 完成迭代器115

5.4.3 完成clear和add方法115

5.4.4 完成remove方法116

5.5 两种包实现的运行时性能117

5.6 测试包的两种实现117

5.7 使用UML绘制包资源118

5.8 章节总结119

5.9 复习题120

5.10 编程项目120

第6章 继承与抽象类122

6.1 使用继承定制已经存在的类122

6.1.1 已有类的子类123

6.1.2 修改_init_方法123

6.1.3 添加新的_contains_方法124

6.1.4 修改已有的add方法125

6.1.5 修改已有的_add_方法126

6.1.6 ArraySortedBag的运行时性能126

6.1.7 Python里类的层次结构的解释126

6.2 使用抽象类消除冗余代码127

6.2.1 设计AbstractBag类127

6.2.2 重新编写AbstractBag类的_init_方法128

6.2.3 修改AbstractBag的子类129

6.2.4 在AbstractBag里模板化_add_方法129

6.3 所有多项集的抽象类130

6.3.1 把AbstractCollection添加到多项集的层次结构里130

6.3.2 在_eq_方法里使用两个迭代器131

6.4 多项集的专家级框架132

6.5 章节总结134

6.6 复习题134

6.7 编程项目135

第7章 栈137

7.1 栈的概述137

7.2 使用栈138

7.2.1 栈接口138

7.2.2 栈的实例化140

7.2.3 示例应用程序：括号匹配140

7.3 栈的3个应用程序142

7.3.1 算术表达式的求值142

7.3.2 计算后缀表达式143

7.3.3 把中缀表达式转换为后缀表达式144

7.3.4 回溯算法146

7.3.5 内存管理148

7.4 栈的实现150

7.4.1 测试驱动150

7.4.2 将栈添加到多项集的层次结构151

7.4.3 栈的数组实现152

7.4.4 栈的链接实现153

7.4.5 抽象栈类的作用155

7.4.6 两种实现的时间和空间复杂度分析156

7.5 案例研究：计算后缀表达式157

7.5.1 案例需求157

7.5.2 案例分析157

7.5.3 案例设计160

7.5.4 案例实现163

7.6 章节总结165

7.7 复习题165

7.8 编程项目166

第8章 队列168

8.1 队列的概述168

8.2 队列接口及其使用169

8.3 队列的两个应用171

8.3.1 计算机模拟171

8.3.2 CPU的轮询调度173

8.4 队列的实现174

8.4.1 队列的链接实现174

8.4.2 队列的数组实现175

8.4.3 两种实现的时间和空间复杂度分析177

8.5 案例研究：超市收银排队的模拟178

8.5.1 案例需求178

8.5.2 案例分析178

8.5.3 用户交互接口178

8.5.4 类和它们的职责179

8.6 优先队列184

8.7 案例研究：急诊室调度程序188

8.7.1 案例需求188

8.7.2 案例分析188

8.7.3 类189

8.7.4 案例设计与实现189

8.8 章节总结191

8.9 复习题192

8.10 编程项目193

第9章 列表194

9.1 列表的概述194

9.2 使用列表195

9.2.1 基于索引的操作196

9.2.2 基于内容的操作196

9.2.3 基于位置的操作196

9.2.4 列表接口200

9.3 列表的应用201

9.3.1 堆存储管理201

9.3.2 磁盘文件管理202

9.3.3 其他多项集的实现203

9.4 列表的实现204

9.4.1 AbstractList类的作用204

9.4.2 基于数组的实现205

9.4.3 列表的链接实现207

9.4.4 两种实现的时间和空间复杂度分析209

9.5 实现列表迭代器211

9.5.1 列表迭代器的角色和职责211

9.5.2 设置和实例化列表迭代器类211

9.5.3 列表迭代器里的导航方法212

9.5.4 列表迭代器里的变异器方法213

9.5.5 设计链接列表的列表迭代器215

9.5.6 列表迭代器实现的时间和空间复杂度分析215

9.6 案例研究：开发有序列表215

9.6.1 案例需求215

9.6.2 案例分析215

9.6.3 案例设计216

9.6.4 案例实现（编码）218

9.7 递归列表的处理219

9.7.1 类Lisp列表的基本操作220

9.7.2 类Lisp列表的递归遍历221

9.7.3 创建类Lisp列表222

9.7.4 类Lisp列表的内部结构223

9.7.5 使用_repr_在IDLE里输出类Lisp列表224

9.7.6 列表和函数式编程225

9.8 章节总结225

9.9 复习题226

9.10 编程项目227

第 10章 树229

10.1 树的概述229

10.1.1 树的术语229

10.1.2 普通树和二叉树230

10.1.3 树的递归定义231

10.2 用树结构的原因232

10.3 二叉树的形状233

10.4 二叉树的遍历235

10.4.1 前序遍历235

10.4.2 中序遍历236

10.4.3 后序遍历236

10.4.4 层次遍历237

10.5 二叉树的3种常见应用237

10.5.1 堆237

10.5.2 二叉查找树238

10.5.3 表达式树239

10.6 开发二叉查找树240

10.6.1 二叉查找树接口240

10.6.2 链接实现的数据结构242

10.6.3 二叉查找树的复杂度分析246

10.7 递归下降解析和编程语言247

10.7.1 语法简介247

10.7.2 识别、解析和解释语言里的句子249

10.7.3 词法分析和扫描器249

10.7.4 解析策略249

10.8 案例研究：解析和表达式树250

10.8.1 案例需求250

10.8.2 案例分析250

10.8.3 节点类的设计与实现251

10.8.4 解析器类的设计与实现253

10.9 二叉树的数组实现254

10.10 堆的实现255

10.11 章节总结258

10.12 复习题258

10.13 编程项目259

第 11章 集合和字典261

11.1 使用集合261

11.2 Python的集合类262

11.2.1 使用集合的交互示例263

11.2.2 集合的应用263

11.2.3 集合和包之间的关系263

11.2.4 集合与字典之间的关系263

11.2.5 集合的实现264

11.3 集合的数组实现和链接实现264

11.3.1 AbstractSet类265

11.3.2 ArraySet类266

11.4 使用字典266

11.5 字典的数组实现和链接实现267

11.5.1 Entry类268

11.5.2 AbstractDict类269

11.5.3 ArrayDict类270

11.5.4 字典的数组实现和链接实现的复杂度分析271

11.6 哈希策略272

11.6.1 冲突与密度的关系272

11.6.2 非数字键的哈希273

11.6.3 线性探测法275

11.6.4 二次探测法276

11.6.5 链式法277

11.6.6 复杂度分析278

11.7 案例研究：分析哈希策略279

11.7.1 案例需求279

11.7.2 案例分析279

11.7.3 案例设计281

11.7.4 案例实现281

11.8 集合的哈希实现283

11.9 字典的哈希实现285

11.10 有序集合和有序字典287

11.11 章节总结288

11.12 复习题289

11.13 编程项目290

第 12章 图292

12.1 使用图的原因292

12.2 图的术语293

12.3 图的存储方式296

12.3.1 邻接矩阵296

12.3.2 邻接表297

12.3.3 两种存储方式的分析298

12.3.4 对运行时的进一步思考299

12.4 图的遍历299

12.4.1 通用遍历算法300

12.4.2 广度优先遍历和深度优先遍历300

12.4.3 图的组件302

12.5 图里的树303

12.5.1 生成树和生成森林303

12.5.2 最小生成树303

12.5.3 最小生成树的算法304

12.6 拓扑排序306

12.7 最短路径问题306

12.7.1 Dijkstra算法307

12.7.2 初始化步骤307

12.7.3 计算步骤308

12.7.4 无穷大的表示和使用309

12.7.5 分析309

12.7.6 Floyd算法310

12.7.7 分析311

12.8 开发图多项集311

12.8.1 图多项集的用法示例311

12.8.2 LinkedDirectedGraph类312

12.8.3 LinkedVertex类316

12.8.4 LinkedEdge类317

12.9 案例研究：测试图算法318

12.9.1 案例需求318

12.9.2 案例分析318

12.9.3 GraphDemoView类和GraphDemoModel类319

12.9.4 案例实现（编码）320

12.10 章节总结323

12.11 复习题324

12.12 编程项目325