数据结构 Python语言描述 第2版(异步图书出品）

输出12
1.3.3对象和方法调用13
1.4Python内置的多项集及其操作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.5in运算符和_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.6ArraySortedBag的运行时性能126
6.1.7Python里类的层次结构的解释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.2CPU的轮询调度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.1AbstractList类的作用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.2Python的集合类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.1AbstractSet类265
11.3.2ArraySet类266
11.4使用字典266
11.5字典的数组实现和链接实现267
11.5.1Entry类268
11.5.2AbstractDict类269
11.5.3ArrayDict类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.1Dijkstra算法307
12.7.2初始化步骤307
12.7.3计算步骤308
12.7.4无穷大的表示和使用309
12.7.5分析309
12.7.6Floyd算法310
12.7.7分析311
12.8开发图多项集311
12.8.1图多项集的用法示例311
12.8.2LinkedDirectedGraph类312
12.8.3LinkedVertex类316
12.8.4LinkedEdge类317
12.9案例研究：测试图算法318
12.9.1案例需求318
12.9.2案例分析318
12.9.3GraphDemoView类和GraphDemoModel类319
12.9.4案例实现（编码）320
12.10章节总结323
12.11复习题324
12.12编程项目325