目录CONTENTS



第1章绪论1
1.1算法和算法分析1
1.1.1什么是算法1
1.1.2算法的时间复杂度及其表示法3
1.2数据结构6
1.2.1数据的逻辑结构6
1.2.2数据的存储结构7
1.2.3数据结构上的操作8
小结8
习题8
第2章Python语言巩固与提高10
2.1一些Python语言操作的时间复杂度10
2.2函数11
2.2.1lambda表达式11
2.2.2高阶函数和闭包12
2.2.3global变量和nonlocal变量13
2.2.4函数参数的默认值14
★2.2.5生成器(电子文档)14
2.3面向对象程序设计15
2.3.1类和对象15
2.3.2对象的比较18
2.3.3迭代器19
2.3.4类的特殊方法21
习题23
第3章线性表26
3.1顺序表26
3.2链表29
3.2.1单链表29
3.2.2循环单链表33
3.2.3双链表33
3.2.4静态链表37
3.3顺序表和链表的选择37
小结38
习题39
第4章枚举与二分法40
4.1枚举40
4.1.1案例: 八皇后问题(P0070)40
4.1.2案例: 特殊密码锁(P0090)41
4.2二分法43
4.2.1案例: 网线主管(P0120)43
★4.2.2案例: 好斗的牛(P0130)45
小结46
习题46
第5章递归和分治49
5.1用递归进行枚举50
5.1.1案例: N皇后问题(P0230)50
5.1.2案例: 全排列(P0240)52
5.2解决用递归形式定义的问题54
5.2.1案例: 波兰表达式(P0250)54
5.2.2案例: 绘制雪花曲线56
5.3用递归进行问题分解56
5.3.1案例: 上台阶(P0260)56
5.3.2案例: 算24(P0270)57
5.3.3案例: 7的倍数取法有多少种(P0290)58
5.4分治59
5.4.1案例: 求排列的逆序数(P0300)59
5.4.2案例: 汉诺塔问题(P0310)61
5.4.3案例: 快速幂62
小结63
习题63
第6章栈和队列65
6.1栈65
6.1.1案例: 括号配对(P0410)65
6.1.2案例: 后序表达式求值(P0420)66
★6.1.3案例: 四则运算表达式求值(P0440)68
6.1.4案例: 合法出栈序列(P0450)69
★★6.2栈和递归的关系(电子文档)71
6.3队列71
6.3.1队列的基本实现71
6.3.2循环队列72
6.3.3Python语句自带的队列(电子文档)75
★★6.3.4案例: 滑动窗口(P0460)75
6.4用链表实现栈和队列77
小结77
习题78
第7章二叉树80
7.1二叉树的概念80
7.2二叉树的性质82
7.3二叉树的表示84
7.3.1用类表示二叉树84
7.3.2用列表表示二叉树85
7.3.3完全二叉树的表示85
7.4二叉树的遍历86
7.4.1二叉树的前序、后序、中序和按层次遍历86
★7.4.2案例: 文本缩进二叉树(P0560)88
7.4.3案例: 根据二叉树前中序序列建树(P0570)90
★★★7.4.4案例: 根据后序表达式建立表达式树(P0580)(电子文档)91
★7.4.5非递归方式遍历二叉树92
★★7.5线索二叉树93
7.6堆96
7.6.1堆的概念96
7.6.2堆的操作97
7.6.3建堆99
7.6.4堆的实现和优先队列99
7.6.5Python中的堆(电子文档)102
7.7哈夫曼树102
7.7.1哈夫曼树的概念和构造102
7.7.2案例: 栅栏修补(P0590)103
7.7.3哈夫曼编码104
小结107
习题108
第8章树、森林和并查集111
8.1树的概念111
8.2树的实现112
8.2.1树的直观表示法112
8.2.2案例: 括号嵌套树(P0740)113
8.2.3树的儿子兄弟表示法114
8.2.4案例: 树转儿子兄弟树(P0750)115
8.2.5树的父结点表示法117
8.3森林117
8.4并查集118
8.4.1并查集的概念和用途118
8.4.2案例: The Suspects疑似病人(P0760)120
小结122
习题122
第9章字符串匹配124
9.1暴力匹配算法124
★★9.2KMP匹配算法125
小结130
习题130
第10章动态规划132
10.1什么是动态规划132
10.2动态规划解题的一般思路136
10.3案例: 简单背包问题(P0880)138
★★10.4案例: 不简单的出栈序列统计(P0890)140
★10.5案例: 最长上升子序列(P0900)142
★★10.6案例: 最长公共子序列(P0910)(电子文档)143
小结144
习题144
第11章图的遍历和搜索146
11.1图的定义和术语146
11.2图的表示148
11.2.1邻接矩阵148
11.2.2邻接表149
11.2.3邻接表和邻接矩阵的对比150
11.3图的遍历151
11.3.1深度优先遍历151
11.3.2案例: 输出无向图深度优先遍历序列(P1020)152
11.3.3案例: 城堡的房间(P1030)155
11.3.4案例: 判断无向图是否连通及是否有回路(P1040)156
11.3.5广度优先遍历158
11.4图的搜索160
11.4.1概述160
11.4.2深度优先搜索162
11.4.3案例: 走迷宫之一(P1050)166
11.4.4案例: 走迷宫之二(P1060)167
11.4.5案例: 走迷宫之三(P1070)167
11.4.6广度优先搜索168
11.4.7案例: 抓住那头牛(P1080)169
11.4.8案例: “走迷宫之三”的广搜解法(P1070)171
★★11.4.9案例: 拯救行动(P1100)172
11.5深搜和广搜的选择174
小结174
习题175
第12章图论基础应用算法178
12.1最短路178
12.1.1单源最短路问题的Dijkstra算法178
12.1.2案例: 简单的糖果分配 (P1220)181
★12.1.3求每对顶点之间最短路的Floyd算法184
★12.1.4案例: 奶牛比赛 (P1230)186
12.2最小生成树188
12.2.1概述188
★★12.2.2最小生成树的性质189
12.2.3Prim算法190
12.2.4Kruskal算法192
★12.2.5案例: 团结真的就是力量(P1235)193
★★12.2.6案例: 北极网络(P1240)196
12.3拓扑排序198
12.3.1拓扑排序的定义和算法198
12.3.2案例: 火星人家族树 (P1250)199
★12.4关键路径201
12.4.1关键路径的定义和算法201
★★12.4.2案例: 火星大工程(P1260)204
小结206
习题206
第13章排序209
13.1插入排序210
13.1.1直接插入排序210
13.1.2折半插入排序213
13.1.3希尔排序213
13.2选择排序214
13.2.1简单选择排序214
13.2.2堆排序215
13.3归并排序217
13.4交换排序220
13.4.1冒泡排序220
13.4.2快速排序221
13.5分配排序224
13.5.1桶排序224
13.5.2计数排序(电子文档)226
13.5.3基数排序226
★13.6外排序228
13.6.1置换选择排序229
13.6.2多路归并和败者树233
小结236
习题237
第14章查找239
14.1线性表查找239
14.1.1顺序查找239
14.1.2二分查找240
14.1.3Python的二分查找库bisect(电子文档)242
14.1.4分块查找242
14.2树表查找243
14.2.1二叉查找树244
★14.2.2平衡二叉树251
★14.2.3红黑树257
★14.2.4外存查找: B树和B+树258
14.3哈希表268
14.3.1哈希函数设计268
14.3.2哈希表的插入和冲突消解271
14.3.3哈希表的删除和查找274
14.3.4哈希表的效率分析275
★★14.3.5Python中的哈希表(电子文档)276
小结276
习题278
附录A北京大学在线程序评测平台OpenJudge使用说明282
参考文献284