百道网
 您现在的位置:Fun书 > 算法新解
算法新解


算法新解

作  者:刘新宇

出 版 社:人民邮电出版社

丛 书:图灵原创

出版时间:2017年01月

定  价:99.00

I S B N :9787115440358

所属分类: 专业科技  >  计算机/网络  >  程序设计    

标  签:计算机?网络  计算机理论  

[查看微博评论]

分享到:

书评书荐

TOP内容简介

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


TOP作者简介

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


TOP目录

序一 常成博士,4数网主编

序二 姚冬,YY直播架构师 

前言

第一部分 树

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

1.1 定义 3

1.2 数据组织 5

1.3 插入 6

1.4 遍历 8

1.5 搜索 10

1.5.1 lookup 10

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和Patricia 65

5.1 整数Trie 65

5.1.1 整数Trie的定义 67

5.1.2 插入 67

5.1.3 查找 69

5.2 整数Patricia 70

5.2.1 定义 71

5.2.2 插入 72

5.2.3 查找 78

5.3 字符Trie 80

5.3.1 定义 80

5.3.2 插入 81

5.3.3 查找 83

5.4 字符Patricia 84

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 后缀Trie 104

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 Heapify 160

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 减小key 232

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

fold 543

搜索和匹配 549

zip和unzip 555

小结 558

参考文献 559

索引 563


TOP书摘

TOP 其它信息

加载页面用时:86.4131