Mark Allen Weiss教授撰写的数据结构与算法分析方面的著作曾被评为20世纪最佳的30部计算机著作之一，已经成为公认的经典之作，被全球数百所大学采用为教材，广受好评。

本书反映了Weiss教授在数据结构和算法分析教学实践方面的最新成果。书中从实践需要出发，采用主流的面向对象编程语言，Java，在讲述了基本数据结构和算法之后，先通过几个贴近实际的实例讲授学生如何使用现成的数据结构来解决问题，有利于提高学生抽象思维能力，然后再透彻讲解Java集合类对各种数据结构的实现。既降低了学习难度，又增加了趣味性。

与此同时，本书仍然继承了Weiss著作数学严密、覆盖全面、选材精当。结构安排灵活以及习题丰富的优秀传统，适合读者自学和各种方式的课堂教学。

本书从讲解什么是数据结构开始，延伸至高级数据结构和算法分析，强调数据结构和问题求解技术。本书的目的是从抽象思维和问题求解的观点提供对数据结构的实用介绍，试图包含有关数据结构、算法分析及其Java实现的所有重要的细节。作者采用了独特的方法将数据结构分成说明和实现两部分，并充分利用了已有的数据结构库（Java集合类API）。本书分为四个部分：第一部分讨论适合大多数应用的集合类API的一个子集，并覆盖基本的算法分析技术、递归和排序算法；第二部分包含了一组集合类API的应用实例；第三部分讨论数据结构的实现；第四部分描述了高级的数据结构，如伸展树、偶堆和不相交集数据结构。

本书适合作为本科生数据结构课程或研究生算法分析课程的教材。教师可以灵活地选择本书的内容，选择最适合对应课程的内容授课。

 第一部分 算法和构件块

第1章 算法分析    2

1.1 什么是算法分析    2

1.2 算法运行时间的实例    5

1.3 连续子序列最大和的问题    6

1.3.1 简单的O(N3)算法    7

1.3.2 改进的O(N2)算法    8

1.3.3 线性算法    9

1.4 一般的大O规则    11

1.5 对数    14

1.6 静态查找问题    15

1.6.1 顺序查找    15

1.6.2 二分搜索    16

1.6.3 插值查找    18

1.7 算法分析的检查    18

1.8 大O分析的局限性    19

小结    20

关键概念    20

常见错误    21

网上资源    21

习题    21

参考文献    26

第2章 集合类API    27

2.1 引言    27

2.2 迭代器模式    28

2.2.1 基本的迭代器设计    29

2.2.2 基于继承的迭代器和工厂方法    30

2.3 集合类API：容器和迭代器    32

2.3.1 Collection接口    32

2.3.2 Iterator接口    35

2.4 泛型算法    36

2.4.1 Comparator函数对象    37

2.4.2 Collections类    37

2.4.3 二分搜索    39

2.4.4 排序    40

2.5 List接口    40

2.5.1 ListIterator接口    41

2.5.2 LinkedList类    42

2.6 栈和队列    44

2.6.1 栈    44

2.6.2 栈与计算机语言    45

2.6.3 队列    46

2.6.4 集合类API中的栈和队列    46

2.7 集合    47

2.7.1 TreeSet类    48

2.7.2 HashSet类    48

2.8 映射    52

2.9 优先级队列    55

小结    57

关键概念    57

常见错误    58

网上资源    58

习题    59

参考文献    61

第3章 递归    62

3.1 什么是递归    62

3.2 背景：数学归纳法证明    63

3.3 基本的递归    65

3.3.1 以任何数制打印数    66

3.3.2 为什么可行    67

3.3.3 原理解析    68

3.3.4 太多的递归可能是危险的    69

3.3.5 树的预习    70

3.3.6 其他实例    71

3.4 数值应用    74

3.4.1 模运算    74

3.4.2 模的幂运算    75

3.4.3 最大公因子和乘法逆元素    76

3.4.4 RSA密码系统    78

3.5 分治算法    79

3.5.1 连续子序列最大和的问题    80

3.5.2 对一个基本的分治情况的分析    82

3.5.3 分治算法运行时间的通用上界    84

3.6 动态规划    86

3.7 回溯    89

小结    92

关键概念    92

常见错误    93

网上资源    93

习题    94

参考文献    96

第4章 排序算法    97

4.1 排序为什么重要    97

4.2 预备知识    98

4.3 插入排序及其他简单排序算法的分析    98

4.4 谢尔排序    101

4.5 归并排序    103

4.5.1 有序数组的线性时间合并    103

4.5.2 归并排序算法    105

4.6 快速排序    106

4.6.1 快速排序算法    107

4.6.2 快速排序的分析    108

4.6.3 挑选中心点    111

4.6.4 一种划分策略    112

4.6.5 键等于中心点    113

4.6.6 三个元素的中值划分    114

4.6.7 小规模数组    114

4.6.8 Java快速排序程序    115

4.7 快速选择    117

4.8 排序的下界    118

小结    119

关键概念    119

常见错误    120

网上资源    120

习题    120

参考文献    123

第5章 随机化    124

5.1 为什么需要随机数    124

5.2 随机数生成器    125

5.3 非均匀分布随机数    129

5.4 产生随机排列    130

5.5 随机化算法    131

5.6 随机化素数检验    133

小结    135

关键概念    135

常见错误    136

网上资源    136

习题    136

参考文献    138

第二部分 应用

第6章 娱乐和游戏    140

6.1 单词搜索迷宫    140

6.1.1 理论    140

6.1.2 Java实现    142

6.2 Tic-Tac-Toe游戏    146

6.2.1 ?-?剪枝    146

6.2.2 置换表    148

6.2.3 计算机象棋    151

小结    152

关键概念    152

常见错误    152

网上资源    152

习题    153

参考文献    154

第7章 栈和编译器    155

7.1 平衡符号检查器    155

7.1.1 基本算法    155

7.1.2 实现    156

7.2 简单计算器    163

7.2.1 后缀机    164

7.2.2 中缀到后缀的转化    165

7.2.3 实现    166

7.2.4 表达式树    172

小结    173

关键概念    173

常见错误    174

网上资源    174

习题    174

参考文献    175

第8章 实用程序    176

8.1 文件压缩    176

8.1.1 前缀编码    177

8.1.2 赫夫曼算法    178

8.1.3 实现    180

8.2 交叉引用生成器    191

8.2.1 基本思想    191

8.2.2 Java实现    191

小结    194

关键概念    194

常见错误    195

网上资源    195

习题    195

参考文献    197

第9章 模拟    198

9.1 约瑟夫问题    198

9.1.1 简单实现方案    199

9.1.2 更高效的算法    200

9.2 事件驱动模拟    202

9.2.1 基本思路    202

9.2.2 实例：调制解调器银行的模拟    203

小结    209

关键概念    209

常见错误    209

网上资源    209

习题    209

第10章 图和路径    211

10.1 图的定义    211

10.2 非加权的最短路径问题    221

10.2.1 理论    221

10.2.2 Java实现    223

10.3 非负权值的最短路径算法    224

10.3.1 理论：Dijkstra算法    224

10.3.2 Java实现    227

10.4 含负权值的最短路径问题    228

10.4.1 理论    228

10.4.2 Java实现    229

10.5 无环图的路径问题    230

10.5.1 拓扑排序    230

10.5.2 无环图最短路径算法的理论    232

10.5.3 Java实现    233

10.5.4 应用：关键路径分析    234

小结    236

关键概念    236

常见错误    237

网上资源    237

习题    238

参考文献    240

第三部分 实现

第11章 内部类和ArrayList的实现    242

11.1 迭代器与嵌套类     242

11.2 迭代器和内部类         244

11.3 AbstractCollection类    246

11.4 StringBuilder    249

11.5 使用迭代器的ArrayList的实现    250

小结    254

关键概念    254

常见错误    254

网上资源    254

习题    255

第12章 栈和队列    257

12.1 动态数组的实现    257

12.1.1 栈    257

12.1.2 队列    260

12.2 链表实现    265

12.2.1 栈    265

12.2.2 队列    267

12.3 两种实现方式的比较    270

12.4 java.util.Stack类    270

12.5 双向队列    271

小结    271

关键概念    272

常见错误    272

网上资源    272

习题    272

第13章 链表    273

13.1 基本思想    273

13.1.1 头结点    274

13.1.2 迭代器类    275

13.2 Java实现    276

13.3 双向链表和循环链表    281

13.4 有序链表    283

13.5 集合类API中LinkedList类的实现    284

小结    292

关键概念    292

常见错误    293

网上资源    293

习题    293

第14章 树    296

14.1 普通的树    296

14.1.1 定义    296

14.1.2 实现    297

14.1.3 应用：文件系统    298

14.2 二叉树    301

14.3 递归和树    306

14.4 树的遍历：迭代器类    307

14.4.1 后序遍历    310

14.4.2 中序遍历    313

14.4.3 前序遍历    314

14.4.4 层次遍历    316

小结    317

关键概念    317

常见错误    318

网上资源    318

习题    318

第15章 二叉查找树    321

15.1 基本思想    321

15.1.1 操作    322

15.1.2 Java实现    323

15.2 顺序统计量    329

15.3 二叉查找树操作的分析    332

15.4 AVL树    335

15.4.1 性质    335

15.4.2 单旋转    337

15.4.3 双旋转    339

15.4.4 AVL插入小结    341

15.5 红黑树    341

15.5.1 自下而上的插入    342

15.5.2 自上而下的红黑树    344

15.5.3 Java实现    345

15.5.4 自上而下的删除    350

15.6 AA树    352

15.6.1 插入    353

15.6.2 删除    354

15.6.3 Java实现    355

15.7 集合类API中TreeSet类和TreeMap类的实现    358

15.8 B树    371

小结    376

关键概念    376

常见错误    377

网上资源    377

习题    378

参考文献    379

第16章 散列表    382

16.1 基本概念    382

16.2 散列函数    383

16.3 线性探测法    385

16.3.1 线性探测法的直观分析    386

16.3.2 实际上所发生的：初始聚类    386

16.3.3 find操作的分析    387

16.4 二次探测法    388

16.4.1 Java实现    392

16.4.2 二次探测法的分析    398

16.5 分别链接散列    399

16.6 散列表与二叉查找树    399

16.7 散列表的应用    400

小结    400

关键概念    400

常见错误    401

网上资源    401

习题    401

参考文献    403

第17章 优先级队列：二叉堆    404

17.1 基本概念    404

17.1.1 结构性    405

17.1.2 堆的有序性    406

17.1.3 允许的操作    406

17.2 基本操作的实现    408

17.2.1 插入    408

17.2.2 deleteMin操作    410

17.3 buildHeap操作：线性时间的堆构造    411

17.4 高级操作：decreaseKey和merge    414

17.5 内排序：堆排序    414

17.6 外排序    416

17.6.1 为什么需要新的算法    417

17.6.2 外排序模型    417

17.6.3 简单算法    417

17.6.4 多路归并    418

17.6.5 多阶段归并    419

17.6.6 置换选择法    420

小结    421

关键概念    422

常见错误    422

网上资源    422

习题    422

参考文献    425

第四部分 高级数据结构

第18章 伸展树    428

18.1 自调整和均摊法的分析    428

18.1.1 均摊法时间限度    429

18.1.2 简单的自调整策略（并不管用）    429

18.2 基本的自底向上的伸展树    430

18.3 基本的伸展树操作    432

18.4 自底向上伸展的分析    432

18.5 自顶向下的伸展树    436

18.6 自顶向下伸展树的实现    439

18.7 伸展树与其他搜索树的比较    442

小结    442

关键概念    443

常见错误    443

网上资源    443

习题    443

参考文献    444

第19章 归并优先级队列    445

19.1 斜堆    445

19.1.1 归并是基本操作    445

19.1.2 满足堆有序性的树的简化归并    446

19.1.3 斜堆：一个简单的修改    446

19.1.4 斜堆的分析    447

19.2 偶堆    448

19.2.1 偶堆操作    449

19.2.2 偶堆的实现    450

19.2.3 应用：Dijkstra最短加权路径算法    455

小结    457

关键概念    457

常见错误    457

网上资源    457

习题    457

参考文献    458

第20章 不相交集类    459

20.1 等价关系    459

20.2 动态等价及应用    459

20.2.1 应用：生成迷宫    460

20.2.2 应用：最小生成树    462

20.2.3 应用：最近的共同祖先问题    463

20.3 快速查找算法    466

20.4 快速并算法    466

20.4.1 智能并算法    468

20.4.2 路径压缩    469

20.5 Java实现    470

20.6 按秩并和路径压缩的最坏情况    471

小结    476

关键概念    477

常见错误    478

网上资源    478

习题    478

参考文献    479

附录A 运算符    481

附录B 位运算符    482