算法新解 刘新宇 完整文字版带标签.pdf

算法新解 刘新宇 完整文字版带标签.pdf 个人收集电子书，仅用学习使用，不可用于商业用途，如有版权问题，请联系删除！ 目录： 第一部分　　树 第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