算法新解

内容简介：

本书分4 部分，同时用函数式和传统方法介绍主要的基本算法和数据结构。数据结构部分包括二叉树、红黑树、AVL 树、Trie、Patricia、后缀树、B 树、二叉堆、二项式堆、斐波那契堆、配对堆、队列、序列等；基本算法部分包括各种排序算法、序列搜索算法、字符串匹配算法（KMP 等）、深度优先与广度优先搜索算法、贪心算法以及动态规划。

本书适合软件开发人员、编程和算法爱好者，以及高校学生阅读参考。

作者简介：

刘新宇

1999年和2001年分别获得清华大学自动化系学士和硕士学位，之后长期从事软件研发工作。他关注基本算法和数据结构，尤其是函数式算法，目前就职于亚马逊中国仓储和物流技术团队。

目录：

第一部分树

第1章　二叉搜索树：数据结构中的“hello world”3

1.1 　定义3

1.2 　数据组织5

1.3 　插入6

1.4 　遍历8

1.5 　搜索10

1.5.1 　lookup10

1.5.2 　最小元素和最大元素11

1.5.3 　前驱和后继12

1.6 　删除14

1.7 　随机构建二叉搜索树18

第2章　插入排序的进化19

2.1 　简介19

2.2 　插入20

2.3 　改进一：二分查找20

2.4 　改进二：使用链表22

2.5 　使用二叉搜索树的最终改进26

2.6 　小结27

第3章　并不复杂的红黑树28

3.1 　红黑树的定义32

3.2 　插入33

3.3 　删除36

3.4 　命令式的红黑树算法?*44

3.5 　小结47

第4章　AVL树48

4.1 　AVL树的定义48

4.2 　插入51

4.2.1 　平衡调整53

4.2.2 　模式匹配57

4.3 　删除59

4.4 　AVL树的命令式算法?*59

4.5 　小结63

第5章　基数树：Trie和Patricia65

5.1 　整数Trie65

5.1.1 　整数Trie的定义67

5.1.2 　插入67

5.1.3 　查找69

5.2 　整数Patricia70

5.2.1 　定义71

5.2.2 　插入72

5.2.3 　查找78

5.3 　字符Trie80

5.3.1 　定义80

5.3.2 　插入81

5.3.3 　查找83

5.4 　字符Patricia84

5.4.1 　定义84

5.4.2 　插入85

5.4.3 　查找90

5.5 　Trie和Patricia的应用92

5.5.1 　电子词典和单词自动补齐92

5.5.2 　T9输入法97

5.6 　小结102

第6章　后缀树103

6.1 　后缀Trie104

6.1.1 　节点转移和后缀链接105

6.1.2 　on-line构造107

6.2 　后缀树111

6.3 　后缀树的应用121

6.3.1 　字符串搜索和模式匹配121

6.3.2 　查找最长重复子串123

6.3.3 　查找最长公共子串125

6.3.4 　查找最长回文127

6.3.5 　其他128

6.4 　小结128

第7章　B树129

7.1 　插入131

7.2 　删除139

7.2.1 　删除前预合并139

7.2.2 　先删除再修复139

7.3 　搜索153

7.4 　小结155

第二部分 堆

第8章　二叉堆159

8.1 　用数组实现隐式二叉堆159

8.1.1 　定义159

8.1.2 　Heapify160

8.1.3 　构造堆163

8.1.4 　堆的基本操作164

8.1.5 　堆排序168

8.2 　左偏堆和skew堆:显式的二叉堆169

8.2.1 　定义170

8.2.2 　合并172

8.2.3 　基本堆操作173

8.2.4 　使用左偏堆实现堆排序174

8.2.5 　skew堆174

8.3 　伸展堆177

8.3.1 　定义177

8.3.2 　堆排序183

8.4 　小结183

第9章　从吃葡萄到世界杯：选择排序的进化184

9.1 　查找最小元素186

9.1.1 　标记186

9.1.2 　分组188

9.1.3 　选择排序的性能189

9.2 　细微改进190

9.2.1 　比较方法参数化190

9.2.2 　细微调整191

9.2.3 　鸡尾酒排序192

9.3 　本质改进196

9.3.1 　锦标赛淘汰法196

9.3.2 　使用堆排序进行最后的改进204

9.4 　小结204

第10章　二项式堆、斐波那契堆和配对堆205

10.1 　二项式堆205

10.1.1 　定义205

10.1.2 　基本的堆操作209

10.2 　斐波那契堆220

10.2.1 　定义220

10.2.2 　基本堆操作221

10.2.3 　弹出操作的性能分析230

10.2.4 　减小key232

10.2.5 　“斐波那契堆”名字的由来234

10.3 　配对堆237

10.3.1 　定义237

10.3.2 　基本堆操作238

10.4 　小结244

第三部分 队列和序列

第11章　并不简单的队列247

11.1 　单向链表和循环缓冲区实现的队列247

11.1.1 　单向链表实现247

11.1.2 　循环缓冲区实现251

11.2 　纯函数式实现253

11.2.1 　双列表队列254

11.2.2 　双数组队列：一种对称实现255

11.3 　小改进：平衡队列257

11.4 　进一步改进：实时队列259

11.5 　惰性实时队列266

11.6 　小结269

第12章　序列：最后一块砖271

12.1 　二叉随机访问列表271

12.1.1 　普通数组和列表271

12.1.2 　使用森林表示序列272

12.1.3 　在序列的头部插入273

12.2 　二叉随机访问列表的数值表示279

12.3 　命令式双数组列表285

12.3.1 　定义285

12.3.2 　插入和添加286

12.3.3 　随机访问286

12.3.4 　删除和平衡287

12.4 　可连接列表289

12.5 　手指树293

12.5.1 　定义293

12.5.2 　向序列的头部插入元素295

12.5.3 　从头部删除元素298

12.5.4 　删除时处理不规则的手指树300

12.5.5 　在序列的尾部添加元素304

12.5.6 　从尾部删除元素306

12.5.7 　连接307

12.5.8 　手指树的随机访问312

12.6 　小结325

第四部分 排序和搜索

第13章　分而治之：快速排序和归并排序329

13.1 　快速排序329

13.1.1 　基本形式330

13.1.2 　严格弱序331

13.1.3 　划分331

13.1.4 　函数式划分算法的小改进335

13.2 　快速排序的性能分析337

13.3 　工程实践中的改进340

13.4 　针对最差情况的工程实践348

13.5 　其他工程实践351

13.6 　其他351

13.7 　归并排序352

13.8 　原地归并排序360

13.8.1 　死板原地归并360

13.8.2 　原地工作区362

13.8.3 　原地归并排序与链表归并排序366

13.9 　自然归并排序368

13.10 　自底向上归并排序374

13.11 　并行处理377

13.12 　小结377

第14章　搜索379

14.1 　序列搜索379

14.1.1 　分而治之的搜索379

14.1.2 　信息复用400

14.2 　解的搜索428

14.2.1 　深度优先搜索和广度优先搜索428

14.2.2 　搜索最优解468

14.3 　小结498

附录 列表500

列表的定义500

列表的基本操作502

变换527

提取子列表536

fold543

搜索和匹配549

zip和unzip555

小结558

参考文献559

索引563

文章试读：我和刘新宇认识快10 年了。2007 年的时候我在诺基亚工作，和他所在的公司有技术项目合作，每隔几周都要一起开会，所以渐渐混熟了。那时他的职位是项目经理，虽然做着管理的工作，但是我感觉他的技术水平比大多数工程师都要好。 有一次工作上的原因，我和他一起去匈牙利出差，在飞机上我在看小说，而他拿出一本英文数学书看了一路。他说数学和编程是他的兴趣爱好，每年他都会尝试学习一门编程语言，或者了解一个新的...

(查看全部试读)