目录


第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.5迭代器22
第3章线性表25
3.1顺序表25
3.1.1顺序表的概念和操作25
3.1.2Java中的顺序表28
3.2链表28
3.2.1单链表29
3.2.2循环单链表32
3.2.3双链表33
3.2.4静态链表36
★★3.2.5Java中的链表37
3.3顺序表和链表的选择39
小结40
习题40
第4章数组和矩阵42
4.1数组42
4.2特殊矩阵的压缩存储45
4.3小结47
4.4习题47
第5章递归和分治49
5.1用递归进行枚举50
5.1.1案例: N皇后问题(P0230)50
5.1.2案例: 全排列(P0240)52
5.2解决用递归形式定义的问题54
5.2.1案例： 波兰表达式(P0250)55
★★5.2.2案例： 绘制雪花曲线56
5.3用递归进行问题分解58
5.3.1案例: 上台阶(P0260)58
5.3.2案例： 数字三角形(P0265)60
5.3.3案例: 算24(P0270)61
5.4分治63
5.4.1案例: 汉诺塔问题(P0310)63
5.4.2案例： 快速幂64
小结65
习题65
第6章栈和队列67
6.1栈67
6.1.1栈的概念和Java中的栈67
6.1.2案例: 括号配对(P0410)68
6.1.3案例: 后序表达式求值(P0420)69
★6.1.4案例: 四则运算表达式求值(P0440)71
6.1.5案例: 合法出栈序列(P0450)73
★★6.2栈和递归的关系75
6.3队列76
6.3.1基本实现76
6.3.2循环队列77
6.3.3Java中的队列80
★6.3.4案例: 用两个栈模拟一个队列81
★★6.3.5案例: 滑动窗口(P0460)82
6.4用链表实现栈和队列84
小结84
习题85
第7章二叉树87
7.1二叉树的概念87
7.2二叉树的性质89
7.3二叉树的表示91
7.3.1用类表示二叉树91
7.3.2完全二叉树的表示92
7.4二叉树的遍历92
7.4.1二叉树的前序、后序、中序和按层次遍历92
7.4.2案例: 根据二叉树前中序序列建树(P0570)95
★7.4.3案例: 求二叉树的宽度(P0630)97
7.4.4案例： 扩展二叉树 (P0700)99
★7.4.5非递归方式遍历二叉树100
★7.5线索二叉树101
7.6堆104
7.6.1堆的概念104
7.6.2堆的操作105
7.6.3建堆107
7.6.4堆的实现和优先队列107
7.7哈夫曼树110
7.7.1哈夫曼树的概念和构造110
7.7.2案例: 栅栏修补(P0590)111
7.7.3哈夫曼编码113
小结115
习题116
第8章树、森林和并查集119
8.1树的概念119
8.2树的实现120
8.2.1树的直观表示法120
8.2.2案例: 括号嵌套树(P0740)121
8.2.3树的儿子兄弟表示法122
8.2.4案例: 树转儿子兄弟树(P0750)123
8.2.5树的父结点表示法125
8.3森林125
8.4并查集126
8.4.1并查集的概念和用途126
8.4.2案例: The Suspects——疑似病人(P0760)128
小结130
习题130
第9章字符串132
9.1字符串的编码132
9.2字符串的实现133
9.3字符串的匹配算法134
9.3.1暴力匹配算法134
★★9.3.2KMP字符串匹配算法135
小结140
习题140
第10章图的遍历和搜索142
10.1图的定义和术语142
10.2图的表示144
10.2.1邻接矩阵144
10.2.2邻接表145
10.2.3邻接表和邻接矩阵的对比146
10.3图的遍历146
10.3.1深度优先遍历146
10.3.2案例: 输出无向图深度优先遍历序列(P1020)148
10.3.3案例: 城堡的房间(P1030)151
10.3.4案例: 判断无向图是否连通及是否有回路(P1040)153
10.3.5广度优先遍历155
10.4图的搜索157
10.4.1概述157
10.4.2深度优先搜索159
10.4.3案例: 走迷宫之一(P1050)162
10.4.4案例: 走迷宫之二(P1060)164
10.4.5案例: 走迷宫之三(P1070)164
10.4.6广度优先搜索166
10.4.7案例: 抓住那头牛(P1080)166
10.4.8案例: “走迷宫之三”的广搜解法(P1070)168
★★10.4.9案例: 拯救行动(P1100)170
10.5深搜和广搜的选择172
小结172
习题173
第11章图论基础应用算法176
11.1最短路176
11.1.1单源最短路问题的Dijkstra算法176
11.1.2案例: 简单的糖果分配(P1220)178
★11.1.3求每对顶点之间最短路的Floyd算法182
★11.1.4案例: 奶牛比赛(P1230)184
11.2最小生成树185
11.2.1概述185
11.2.2最小生成树的性质187
11.2.3Prim算法189
11.2.4Kruskal算法190
★11.2.5案例: 团结真的就是力量(P1235)192
★★11.2.6案例: 北极网络(P1240)196
11.3拓扑排序197
11.3.1拓扑排序的定义和算法197
11.3.2案例: 火星人家族树(P1250)199
★11.4关键路径200
11.4.1关键路径的定义和算法200
★★11.4.2案例: 火星大工程(P1260)203
小结205
习题206
第12章排序208
12.1插入排序209
12.1.1直接插入排序209
12.1.2折半插入排序211
12.1.3希尔排序212
12.2选择排序213
12.2.1简单选择排序213
12.2.2堆排序215
12.3归并排序217
12.4交换排序220
12.4.1冒泡排序220
12.4.2快速排序222
12.5分配排序226
12.5.1桶排序226
12.5.2计数排序227
12.5.3基数排序228
★12.6外排序231
12.6.1置换选择排序231
12.6.2多路归并和败者树235
小结240
习题240
第13章查找243
13.1线性表查找243
13.1.1顺序查找243
13.1.2二分查找244
13.1.3分块查找250
13.2树表查找251
13.2.1二叉查找树251
★13.2.2平衡二叉树(AVL树)259
★13.2.3红黑树264
★13.2.4外存查找: B树和B+树266
13.2.5Java中的二叉查找树274
13.3散列表278
13.3.1散列函数设计279
13.3.2散列表的插入和冲突消解281
13.3.3散列表的删除和查找283
13.3.4散列表的效率分析284
13.3.5Java中的散列表285
小结288
习题290
参考文献294