[正版新书]数据结构与算法(Java语言实现) 郭炜 清华大学出版社 数据结构

本书内容全面、细致、通俗易懂，涵盖线性表、栈和队列、树和二叉树、堆、哈夫曼树、并查集、AVL树、红黑树、B树和B+树、串、图、散列表等数据结构，以及枚举、二分、递归、分治、动态规划、贪心、深搜、广搜、最短路、最小生成树、拓扑排序、关键路径、内外排序等算法。

对各类数据结构和算法，不但要掌握理论，还应熟练地编程实现。本书的最大特点是高标准的实践性。除了少数几个特别复杂的数据结构，95%的数据结构和算法都给出了完整可运行的代码，一共130多份，并且这些代码几乎都出现在具体的例题中。

本书的例题和编程习题，都可以在北京大学在线程序评测平台OpenJudge上提交解题程序并自动评判对错。

本书内容和习题按难度做了明确分级，因此不论是高等学校计算机专业还是非计算机专业的师生，都可以从中各取所需用于教学。本书既可以用作高等学校“数据结构与算法”课程的入门教材，又可以作为考研、找工作面试的秘籍，还可以用于程序设计竞赛的基础培训。

数据结构，是各大互联网和软件企业招聘员工时考核的重点。掌握好数据结构，是成为优秀程序员的必由之路。

目前国内许多大学以Java语言作为第一门编程课程的语言，需要以Java语言描述的数据结构教材作为第二门编程课的教材。然而目前多数数据结构教材，以C/C++语言描述，以Java语言描述的较少，因此本书应有较好市场前景。

目前多数数据结构教材，偏重于理论教学，对使用数据结构实际编程解决问题强调不足，数据结构和算法往往用伪代码，而非真实可以运行的代码描述。本书强调高标准的实践性，因此对于95%的各类数据结构和算法，在理论叙述之外，都给出了可运行的、用以解决实际问题的完整代码。本书和北京大学在线程序评测平台OpenJudge紧密结合，所有编程案例和编程习题，都可以在该平台上找到题目并进行提交，平台可以自动判断对错，对提高读者的实际编程能力作用很大。

目录

第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