目录

第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