目录



第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数据结构上的操作7
小结8
习题8
第2章Java语言巩固与提高10
2.1接口和多态10
2.2内部类和内部接口12
2.3匿名类、Lambda表达式和函数式接口13
2.4泛型16
2.4.1泛型的概念和作用16
2.4.2泛型类、泛型接口和泛型函数17
2.4.3泛型数组22
★★2.4.4泛型的上下界22
★★2.5迭代器25
第3章线性表27
3.1顺序表27
3.1.1顺序表的概念和操作27
3.1.2Java中的顺序表30
3.2链表30
3.2.1单链表31
3.2.2循环单链表34
3.2.3双链表35
3.2.4静态链表38
★★3.2.5Java中的链表39
3.3顺序表和链表的选择41
小结42
习题42
第4章枚举与二分法44
4.1枚举44
4.1.1案例: 八皇后问题(P0070)44
4.1.2案例: 奥数问题(P0100)45
4.1.3案例: 特殊密码锁(P0090)47
4.1.4案例: 假币问题(P0080)49
4.2二分法51
4.2.1案例: 解方程(P0110)52
4.2.2案例: 网线主管(P0120)53
★4.2.3案例: 好斗的牛(P0130)55
小结56
习题56
第5章递归和分治59
5.1用递归进行枚举59
5.1.1案例: N皇后问题(P0230)59
5.1.2案例: 奥数问题(P0100)的递归解法61
5.1.3案例: 全排列(P0240)63
5.2解决用递归形式定义的问题64
5.2.1案例: 波兰表达式(P0250)65
★★5.2.2案例: 绘制雪花曲线66
5.3用递归进行问题分解69
5.3.1案例: 上台阶(P0260)69
5.3.2案例: 算24(P0270)70
5.3.3案例: 放苹果(P0280)71
5.3.4案例: 7的倍数取法有多少种(P0290)73
5.4分治73
★5.4.1案例: 求排列的逆序数(P0300)74
5.4.2案例: 汉诺塔问题(P0310)76
5.4.3案例: 快速幂77
小结78
习题78
第6章栈和队列80
6.1栈80
6.1.1栈的概念和Java中的栈80
6.1.2案例: 括号配对(P0410)81
6.1.3案例: 后序表达式求值(P0420)82
★6.1.4案例: 中序表达式转后序表达式(P0430)84
★6.1.5案例: 四则运算表达式求值(P0440)86
6.1.6案例: 合法出栈序列(P0450)88
★★6.2栈和递归的关系90
6.3队列92
6.3.1基本实现93
6.3.2循环队列93
6.3.3Java中的队列96
★★6.3.4案例: 滑动窗口(P0460)97
★6.3.5案例: 用两个栈模拟一个队列99
6.4用链表实现栈和队列100
小结101
习题101
第7章二叉树103
7.1二叉树的概念103
7.2二叉树的性质105
7.3二叉树的表示107
7.3.1用类表示二叉树107
7.3.2完全二叉树的表示108
7.4二叉树的遍历108
7.4.1二叉树的前序、后序、中序和按层次遍历108
7.4.2案例: 根据二叉树前中序序列建树(P0570)111
★7.4.3案例: 求二叉树的宽度(P0630)113
★★★7.4.4案例: 根据后序表达式建立表达式树(P0580)115
★★7.4.5案例: 文本缩进二叉树(P0560)116
★7.4.6非递归方式遍历二叉树118
★★7.5线索二叉树120
7.6堆125
7.6.1堆的概念125
7.6.2堆的操作125
7.6.3建堆127
7.6.4堆的实现和优先队列128
7.7哈夫曼树131
7.7.1哈夫曼树的概念和构造131
7.7.2案例: 栅栏修补(P0590)132
7.7.3哈夫曼编码133
小结135
习题136
第8章树、森林和并查集139
8.1树的概念139
8.2树的实现140
8.2.1树的直观表示法140
8.2.2案例: 括号嵌套树(P0740)141
8.2.3树的儿子兄弟表示法142
8.2.4案例: 树转儿子兄弟树(P0750)143
8.2.5树的父结点表示法145
8.3森林145
8.4并查集146
8.4.1并查集的概念和用途146
8.4.2案例: The Suspects疑似病人(P0760)148
小结150
习题150
第9章字符串152
9.1字符串的编码152
9.2字符串的实现153
9.3字符串的匹配算法154
9.3.1暴力匹配算法154
★★9.3.2KMP字符串匹配算法155
小结160
习题160
第10章动态规划162
10.1什么是动态规划162
10.2动态规划解题的一般思路167
10.3案例: 简单背包问题(P0880)169
★★10.4案例: 不简单的出栈序列统计(P0890)171
★10.5案例: 最长上升子序列(P0900)173
★★10.6案例: 最长公共子序列(P0910)174
小结176
习题176
第11章图的遍历和搜索178
11.1图的定义和术语178
11.2图的表示180
11.2.1邻接矩阵180
11.2.2邻接表181
11.2.3邻接表和邻接矩阵的对比182
11.3图的遍历182
11.3.1深度优先遍历182
11.3.2案例: 输出无向图深度优先遍历序列(P1020)184
11.3.3案例: 城堡的房间(P1030)187
11.3.4案例: 判断无向图是否连通及是否有回路(P1040)189
11.3.5广度优先遍历191
11.4图的搜索193
11.4.1概述193
11.4.2深度优先搜索195
11.4.3案例: 走迷宫之一(P1050)198
11.4.4案例: 走迷宫之二(P1060)200
11.4.5案例: 走迷宫之三(P1070)200
11.4.6广度优先搜索202
11.4.7案例: 抓住那头牛(P1080)202
11.4.8案例: “走迷宫之三”的广搜解法(P1070)204
★★11.4.9案例: 拯救行动(P1100)206
11.5深搜和广搜的选择209
小结209
习题210
第12章图论基础应用算法213
12.1最短路213
12.1.1单源最短路问题的Dijkstra算法213
12.1.2案例: 简单的糖果分配(P1220)216
★12.1.3求每对顶点之间最短路的Floyd算法219
★12.1.4案例: 奶牛比赛(P1230)221
12.2最小生成树223
12.2.1概述223
12.2.2最小生成树的性质224
12.2.3Prim算法226
12.2.4Kruskal算法227
★12.2.5案例: 团结真的就是力量(P1235)229
★★12.2.6案例: 北极网络(P1240)233
12.3拓扑排序234
12.3.1拓扑排序的定义和算法234
12.3.2案例: 火星人家族树(P1250)236
★12.4关键路径237
12.4.1关键路径的定义和算法237
★★12.4.2案例: 火星大工程(P1260)240
小结242
习题243
第13章排序245
13.1插入排序246
13.1.1直接插入排序246
13.1.2折半插入排序248
13.1.3希尔排序248
13.2选择排序250
13.2.1简单选择排序250
13.2.2堆排序251
13.3归并排序253
13.4交换排序256
13.4.1冒泡排序256
13.4.2快速排序258
13.5分配排序262
13.5.1桶排序262
13.5.2计数排序263
13.5.3基数排序264
★13.6外排序267
13.6.1置换选择排序267
13.6.2多路归并和败者树271
小结276
习题276
第14章查找279
14.1线性表查找279
14.1.1顺序查找279
14.1.2二分查找280
14.1.3Java的二分查找函数282
14.1.4分块查找283
14.2树表查找284
14.2.1二叉查找树284
★14.2.2平衡二叉树292
★14.2.3红黑树300
★14.2.4外存查找: B树和B+树306
14.2.5Java中的二叉查找树315
14.3散列表319
14.3.1散列函数设计319
14.3.2散列表的插入和冲突消解322
14.3.3散列表的删除和查找324
14.3.4散列表的效率分析325
14.3.5Java中的散列表326
小结329
习题331
第15章贪心算法335
15.1案例: 圣诞老人的礼物(P1370)335
15.2案例: 电影节(P1380)337
小结338
习题339
附录北京大学在线程序评测平台OpenJudge使用说明340
参考文献341