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

第 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