第1章 Python编程基础 1
1.1基本程序要素 1
1.1.1程序和模块 1
1.1.2 Python程序示例：猜数字 1
1.1.3编辑、编译并运行Python程序 2
1.1.4程序注释 3
1.1.5词法元素 3
1.1.6拼写和命名惯例 3
1.1.7语法元素 4
1.1.8字面值 4
1.1.9字符串字面值 4
1.1.10运算符和表达式 5
1.1.11函数调用 5
1.1.12 pRInt函数 5
1.1.13 input函数 5
1.1.14类型转换函数和混合模式运算 6
1.1.15 可选的和关键字函数参数 6
1.1.16变量和赋值语句 6
1.1.17 Python数据类型 7
1.1.18 import语句 7
1.1.19获取关于程序组件的帮助 7
1.2控制语句 8
1.2.1条件式语句 8
1.2.2使用if name__==“_main” 9
1.2.3循环语句 10
1.3字符串及其运算 10
1.3.1运算符 10
1.3.2格式化字符串以便输出 11
1.3.3对象和方法调用 13
1.4内建Python集合及其操作 13
1.4.1列表 14
1.4.2元组 14
1.4.3遍历序列 14
1.4.4字典 15
1.4.5搜索一个值 15
1.4.6对集合应用模式匹配 15
1.5编写新的函数 16
1.5.1函数定义 16
1.5.2递归函数 17
1.5.3嵌套的函数定义 19
1.5.4高阶函数 19
1.5.5使用lambda表达式创建匿名函数 20
1.6捕获异常 20
1.7文件及其操作 21
1.7.1文本文件的输出 22
1.7.2将数字写入到一个文本文件 22
1.7.3从文本文件读取文本 23
1.7.4从文件读取数字 24
1.7.5使用pickle读写对象 24
1.8创建新的类 25
1.9编程项目 28
第2章 集合概览 30
2.1集合类型 30
2.1.1线性集合 30
2.1.2层级集合 31
2.1.3图集合 31
2.1.4无序集合 31
2.1.5有序集合 31
2.1.6集合类型的分类 32
2.2集合上的操作 32
2.3集合的实现 34
2.4小结 35
2.5复习题 35
2.6编程项目 36
第3章 搜索、排序和复杂度分析 37
3.1评估算法的性能 37
3.1.1度量算法的运行时间 37
3.1.2统计指令 39
3.1.3度量算法所使用的内存 41
3.1.4练习3.1 41
3.2复杂度分析 41
3.2.1复杂度的阶 41
3.2.2大O表示法 43
3.2.3常量比例的作用 43
3.2.4练习3.2 43
3.3搜索算法 44
3.3.1搜索最小值 44
3.3.2顺序搜索一个列表 44
3.3.3最好情况、最坏情况和平均情况的性能 45
3.3.4有序列表的二叉搜索 45
3.3.5比较数据项 47
3.3.6练习3.3 48
3.4基本排序算法 48
3.4.1选择排序 48
3.4.2冒泡排序 49
3.4.3插入排序 50
3.4.4再谈最好情况、最坏情况和平均情况的性能 52
3.4.5练习3.4 52
3.5更快的排序 53
3.5.1快速排序简介 53
3.5.2合并排序 56
3.5.3练习3.5 59
3.6指数算法：递归式的Fibonacci 59
3.7案例学习：算法探查器 61
3.7.1需求 61
3.7.2分析 61
3.7.3设计 62
3.7.4实现（编写代码） 63
3.8小结 65
3.9复习题 66
3.10编程项目 67
第4章 数组和链表结构 69
4.1数组数据结构 69
4.1.1随机访问和连续内存 71
4.1.2静态内存和动态内存 72
4.1.3物理大小和逻辑大小 72
4.1.4练习4.1 73
4.2数组的操作 73
4.2.1增加数组的大小 73
4.2.2减小数组的大小 74
4.2.3在数组中插入一项 74
4.2.4从数组中删除一项 75
4.2.5复杂度权衡：时间、空间和数组 76
4.2.6练习4.2 76
4.3二维数组 77
4.3.1处理网格 77
4.3.2创建并初始化网格 77
4.3.3定义Grid类 78
4.3.4杂乱的网格和多维数组 79
4.3.5练习4.3 79
4.4链表结构 80
4.4.1单链表结构和双链表结构 80
4.4.2非连续性内存和节点 81
4.4.3定义一个单链表节点类 82
4.4.4使用单链表节点类 82
4.4.5练习4.4 84
4.5单链表结构上的操作 84
4.5.1遍历 84
4.5.2搜索 85
4.5.3替换 86
4.5.4在开始处插入 86
4.5.5在末尾插入 87
4.5.6从开始处删除 87
4.5.7从末尾删除 88
4.5.8在任何位置插入 89
4.5.9从任意位置删除 90
4.5.10复杂度权衡：时间、空间和单链表结构 91
4.5.11练习4.5 92
4.6链表的变体 92
4.6.1带有一个哑头节点的循环链表结构 92
4.6.2双链表结构 93
4.6.3练习4.6 95
4.7小结 95
4.8复习题 96
4.9编程项目 96
第5章 接口、实现和多态 98
5.1开发接口 98
5.1.1定义包接口 98
5.1.2指定参数和返回值 99
5.1.3构造方法和实现类 101
5.1.4先验条件、后验条件、异常和文档 101
5.1.5用Python编写接口 102
5.1.6练习5.1 103
5.2开发一个基于数组的实现 103
5.2.1选择并初始化数据结构 103
5.2.2先完成容易的方法 104
5.2.3完成迭代器 105
5.2.4完成使用迭代器的方法 106
5.2.5 in运算符和contains方法 106
5.2.6完成remove方法 107
5.2.7练习5.2 107
5.3开发一个基于链表的实现 107
5.3.1初始化数据结构 108
5.3.2完成迭代器 109
5.3.3完成clear和add方法 109
5.3.4完成remove方法 109
5.3.5练习5.3 110
5.4两个包实现的运行时性能 110
5.5测试两个包实现 111
5.6用UML图表示包资源 112
5.7小结 113
5.8复习题 113
5.9编程项目 114
第6章 继承和抽象类 115
6.1使用继承定制一个己有的类 115
6.1.1已有类的子类化 115
6.1.2再谈init方法 116
6.1.3添加新的contains方法 117
6.1.4修改已有的add方法 117
6.1.5 ArraySortedBag的运行时间性能 118
6.1.6 Python中的类层级 118
6.1.7练习6.1 119
6.2使用抽象类去除代码冗余性 119
6.2.1设计一个AbstractBag类 119
6.2.2重新编写AbstractBag中的init方法 120
6.2.3修改AbstractBag的子类 120
6.2.4将AbstractBag中的add方法泛化 121
6.3所有集合的一个抽象类 122
6.3.1将AbstractCollection整合到集合层级中 122
6.3.2在__eq__方法中使用两个迭代器 123
6.3.3练习6.2 124
6.4小结 124
6.5复习题 124
6.6编程项目 125
第7章 栈 127
7.1栈概览 127
7.2使用栈 128
7.2.1栈接口 128
7.2.2初始化一个栈 129
7.2.3示例应用程序：匹配括号 129
7.2.4练习7.1 131
7.3栈的3种应用 131
7.3.1计算算术表达式 131
7.3.2计算后缀表达式 132
7.3.3练习7.2 133
7.3.4将中缀表达式转换为后缀表达式 133
7.3.5练习7.3 135
7.3.6回溯算法 135
7.3.7内存管理 137
7.4栈的实现 138
7.4.1测试驱动程序 138
7.4.2将栈添加到集合层级中 139
7.4.3数组实现 140
7.4.4链表实现 141
7.4.5 AbstractStack类的作用 144
7.4.6两种实现的时间和空间分析 144
7.4.7练习7.4 145
7.5案例学习：计算后缀表达式 145
7.5.1要求 145
7.5.2分析 145
7.5.3设计 148
7.5.4实现 150
7.6小结 153
7.7复习题 153
7.8编程项目 154
第8章 队列 156
8.1队列概览 156
8.2队列接口及其应用 157
练习8.1 158
8.3队列的两个应用 159
8.3.1模拟 159
8.3.2轮询CPU调度 161
8.3.3练习8.2 161
8.4队列的实现 161
8.4.1队列的链表实现 161
8.4.2数组实现 163
8.4.3两种实现的时间和空间复杂度分析 164
8.4.4练习8.3 165
8.5案例学习：模拟超市排队结账 165
8.5.1要求 165
8.5.2分析 165
8.5.3用户界面 166
8.5.4类及其作用 166
8.6优先队列 171
练习8.4 175
8.7案例学习：急症室调度 175
8.7.1需求 175
8.7.2分析 175
8.7.3类 176
8.7.4设计和实现 177
8.8小结 179
8.9复习题 179
8.10编程项目 180
第9章 列表 182
9.1概览 182
9.2使用列表 183
9.2.1基于索引的操作 183
9.2.2基于内容的操作 183
9.2.3基于位置的操作 184
9.2.4列表的接口 187
9.2.5练习9.1 188
9.3列表的应用 188
9.3.1堆存储管理 188
9.3.2组织磁盘上的文件 189
9.3.3其他集合的实现 190
9.4列表实现 191
9.4.1 AbstractList类的角色 191
9.4.2基于数组的实现 192
9.4.3链表实现 194
9.4.4两种实现的时间和空间分析 196
9.4.5练习9.2 197
9.5实现列表迭代器 197
9.5.1列表迭代器的角色和作用 197
9.5.2设置和实例化一个列表迭代器类 198
9.5.3列表迭代器中的导航方法 199
9.5.4列表迭代器中的修改器方法 200
9.5.5链表列表的列表迭代器的设计 201
9.5.6列表迭代器实现的时间和空间分析 201
9.6案例学习：开发一个有序的列表 201
9.6.1要求 201
9.6.2分析 202
9.6.3设计 202
9.6.4实现（代码） 204
9.7小结 205
9.8复习题 205
9.9编程项目 206
第10章 树 208
10.1树的概览 208
10.1.1树的术语 208
10.1.2普通的树和二叉树 209
10.1.3树的递归定义 210
10.1.4练习10.1 210
10.2为什么要使用树 210
10.3二叉树的形状 211
练习10.2 213
10.4二叉树的3种常见应用 213
10.4.1堆 213
10.4.2二叉搜索树 214
10.4.3表达式树 215
10.4.4练习10.3 216
10.5二叉树的遍历 216
10.5.1前序遍历 216
10.5.2中序遍历 217
10.5.3后序遍历 217
10.5.4层序遍历 217
10.6开发二叉搜索树 217
10.6.1二叉搜索树接口 218
10.6.2链表实现的数据结构 219
10.6.3二叉搜索树的复杂度分析 223
10.6.4练习10.4 224
10.7递归的后代解析和编程语言 224
10.7.1语法简介 224
10.7.2在语言中识别、解析和解释句子 226
10.7.3词法分析和扫描器 226
10.7.4解析策略 227
10.8案例学习：解析和表达式树 227
10.8.1要求 227
10.8.2分析 228
10.8.3节点类的设计和实现 228
10.8.4解析器类的设计和实现 230
10.9二叉树的数组实现 231
练习10.5 232
10.10实现堆 232
练习10.6 234
10.11小结 234
10.12复习题 235
10.13编程项目 236
第11章 集和字典 238
11.1使用集 238
11.2 Python的set类 239
11.2.1集的一个示例会话 239
11.2.2集的应用 240
11.2.3集和包的关系 240
11.2.4集和字典的关系 240
11.2.5集的实现 240
11.2.6练习11.1 241
11.3集的基于数组和链表的实现 241
11.3.1 AbstractSet类 241
11.3.2 ArraySet类 242
11.4使用字典 243
11.5基于数组和基于链表的字典实现 244
11.5.1 Item类 244
11.5.2 AbstractDict类 245
11.5.3 ArrayDict类 246
11.5.4集和字典的基于数组和列表的实现的复杂度分析 247
11.5.5练习11.2 248
11.6哈希策略 248
11.6.1冲突和密度的关系 249
11.6.2非数字键的哈希 250
11.6.3线性探测 251
11.6.4二次探测 252
11.6.5链化 253
11.6.6复杂度分析 253
11.6.7练习11.3 254
11.7案例学习：探查哈希策略 254
11.7.1需求 255
11.7.2分析 255
11.7.3设计 256
11.8集的哈希实现 258
11.9字典的哈希实现 261
练习11.4 263
11.10有序的集和字典 263
11.11小结 264
11.12复习题 264
11.13编程项目 265
第12章 图 267
12.1图的术语 267
练习12.1 269
12.2为什么使用图 270
12.3图的表示 270
12.3.1相邻矩阵 270
12.3.2 邻接表 271
12.3.3两种表示的分析 272
12.3.4运行时间的进一步考虑 272
12.3.5练习12.2 273
12.4图的遍历 273
12.4.1泛型遍历算法 273
12.4.2广度优先遍历和深度优先遍历 274
12.4.3图区域 275
12.4.4练习12.3 276
12.5图中的树 276
12.5.1生成树和森林 276
12.5.2最小生成树 277
12.5.3最小生成树的算法 277
12.6拓扑排序 279
12.7最短路径问题 279
12.7.1 Dijkstra算法 280
12.7.2初始化步骤 280
12.7.3计算步骤 281
12.7.4无限的表示和用法 282
12.7.5分析 282
12.7.6练习12.4 282
12.7.7 Floyd算法 283
12.7.8分析 283
12.8开发一个图集合 284
12.8.1使用图集合的示例 284
12.8.2 LinkedDirected-Graph类 285
12.8.3 LinkedVertex类 288
12.8.4 LinkedEdge类 289
12.9案例学习：测试图算法 290
12.9.1需求 290
12.9.2分析 290
12.9.3 GraphDemoView类和GraphDemoModel类 291
12.9.4实现（代码） 292
12.10小结 295
12.11复习题 296
12.12编程项目 297
附录 供Python程序员使用的集合框架 299