目录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