【资料简介】
【资料截图】
【资料目录】
初等算法 刘新宇 1 November 17, 2016 1刘新宇 Version: 0.6180339887498949 Email: liuxinyu95@gmail.com
【资料截图】
【资料目录】
I 前言
0.1 算法有用么？
0.2 最小可用ID，算法的威力
0.2.1 改进一
0.2.2 改进二、分而治之
0.2.3 简洁与性能――鱼和熊掌
0.3 丑数――数据结构的威力
0.3.1 暴力解法
0.3.2 改进一、构造性解法
0.3.3 改进二、使用多个队列
0.4 小结
0.5 内容组织
II 树
1 二叉搜索树，数据结构中的`hello world'
1.1 定义
1.2 数据组织
1.3 插入
1.4 遍历
1.5 搜索
1.5.1 lookup
1.5.2 最小元素和最大元素
1.5.3 前驱（Successor）和后继（predecessor）
1.6 删除
1.7 随机构建二叉搜索树
2 插入排序的进化
2.1 简介
2.2 插入
2.3 改进一，二分查找
2.4 改进二，使用链表
2.5 使用二叉搜索树的最终改进
2.6 小结
3 并不复杂的红黑树
3.0.1 如何保证树的平衡
3.0.2 树的旋转
3.1 红黑树的定义
3.2 插入
3.3 删除
3.4 命令式的红黑树算法
3.5 其它
4 AVL树
4.1 AVL树的定义
4.2 插入
4.2.1 平衡调整
4.2.1.1 左－左偏（Left-left lean）的情况
4.2.1.2 右－右偏（Right-right lean）的情况
4.2.1.3 右－左偏（Right-left lean）的情况
4.2.1.4 左－右偏（Left-right lean）的情况
4.2.2 模式匹配
4.2.2.1 验证
4.3 删除
4.4 AVL树的命令式算法
4.5 小结
5 基数树－Trie和Patricia
5.1 简介
5.2 整数Trie
5.2.1 整数Trie的定义
5.2.2 插入
5.2.3 查找
5.3 整数Patricia
5.3.1 定义
5.3.2 插入
5.3.3 查找
5.4 字符Trie
5.4.1 定义
5.4.2 插入
5.4.3 查找
5.5 字符Patricia
5.5.1 定义
5.5.2 插入
5.5.3 查找
5.6 Trie和Patricia的应用
5.6.1 电子词典和单词自动补齐
5.6.2 T9输入法
5.7 小结
6 后缀树
6.1 简介
6.2 后缀Trie
6.2.1 节点转移和后缀链接
6.2.2 On-line构造
6.3 后缀树
6.3.1 on-line构造
6.3.1.1 活动点（active point）和终止点（end point）
6.3.1.2 引用对（Reference pair）
6.3.1.3 归一化引用对
6.3.1.4 Ukkonen算法
6.3.1.5 函数式构造后缀树
6.4 后缀树的应用
6.4.1 字符串搜索和模式匹配
6.4.1.1 子串出现的次数
6.4.2 查找最长重复子串
6.4.3 查找最长公共子串
6.4.4 查找最长回文
6.4.5 其它
6.5 小结
7 B树
7.1 简介
7.2 插入
7.2.1 分拆
7.2.1.1 插入前预分拆
7.2.1.2 先插入再修复
7.3 删除
7.3.1 删除前预合并
7.3.2 先删除再修复
7.4 搜索
7.5 小结
III 堆
8 二叉堆
8.1 简介
8.2 用数组实现隐式二叉堆
8.2.1 定义
8.2.2 Heapify
8.2.3 构造堆
8.2.4 堆的基本操作
8.2.4.1 获取顶部元素
8.2.4.2 弹出堆顶元素
8.2.4.3 寻找top k个元素
8.2.4.4 减小key值
8.2.4.5 插入
8.2.5 堆排序
8.3 左偏堆和skew堆―显式的二叉堆
8.3.1 定义
8.3.1.1 Rank（S-值）
8.3.1.2 左偏性质
8.3.2 合并
8.3.2.1 合并由数组表示的二叉堆
8.3.3 基本堆操作
8.3.3.1 获取顶部元素和弹出操作
8.3.3.2 插入
8.3.4 使用左偏堆实现堆排序
8.3.5 Skew堆
8.3.5.1 Skew堆的定义
8.3.5.2 合并
8.4 伸展堆
8.4.1 定义
8.4.1.1 伸展操作
8.4.1.2 获取和弹出顶部元素
8.4.1.3 合并
8.4.2 堆排序
8.5 小结
9 从吃葡萄到世界杯，选择排序的进化
9.1 简介
9.2 查找最小元素
9.2.1 标记
9.2.2 分组
9.2.3 选择排序的性能
9.3 细微改进
9.3.1 比较方法参数化
9.3.2 细微调整
9.3.3 鸡尾酒排序（Cock-tail sort）
9.4 本质改进
9.4.1 锦标赛淘汰法
9.4.1.1 锦标赛淘汰法的细节改进
9.4.2 使用堆排序进行最后的改进
9.5 小结
10 二项式堆，斐波那契堆和配对堆
10.1 简介
10.2 二项式堆
10.2.1 定义
10.2.1.1 二项式树
10.2.1.2 二项式堆
10.2.1.3 数据布局
10.2.2 基本的堆操作
10.2.2.1 树的链接
10.2.2.2 插入新元素（push）
10.2.2.3 堆合并
10.2.2.4 弹出
10.2.2.5 其他
10.3 斐波那契堆
10.3.1 定义
10.3.2 基本堆操作
10.3.2.1 插入新元素
10.3.2.2 堆合并
10.3.2.3 弹出（删除最小元素）
10.3.3 弹出操作的性能分析
10.3.4 减小key
10.3.5 斐波那契堆名字的由来
10.4 配对堆
10.4.1 定义
10.4.2 基本堆操作
10.4.2.1 合并、插入、和获取顶部元素
10.4.2.2 减小节点的值
10.4.2.3 弹出
10.4.2.4 删除节点
10.5 小结
IV 队列和序列
11 并不简单的队列
11.1 简介
11.2 单向列表和循环缓冲区实现的队列
11.2.1 单向链表实现
11.2.2 循环缓冲区实现
11.3 纯函数式实现
11.3.1 双列表队列
11.3.2 双数组队列——一种对称实现
11.4 小改进：平衡队列
11.5 进一步改进：实时队列
11.5.0.1 逐步反转
11.5.0.2 逐步连接
11.5.0.3 汇总
11.6 惰性实时队列
11.7 小节
12 序列，最后一块砖
12.1 简介
12.2 二叉随机访问列表
12.2.1 普通数组和列表
12.2.2 使用森林表示序列
12.2.3 在序列的头部插入
12.2.3.1 从序列头部删除元素
12.2.3.2 随机访问元素
12.3 二叉随机访问列表的数字表示（Numeric representation）
12.3.1 命令式二叉随机访问列表
12.4 命令式双数组列表（paired-array list）
12.4.1 定义
12.4.2 插入和添加
12.4.3 随机访问
12.4.4 删除和平衡
12.5 可连接列表
12.6 手指树（Finger Tree）
12.6.1 定义
12.6.2 向序列的头部插入元素
12.6.3 从头部删除元素
12.6.4 删除时处理不规则的手指树
12.6.5 在序列的尾部添加元素
12.6.6 从尾部删除元素
12.6.7 连接
12.6.8 手指树的随机访问
12.6.8.1 增加size记录
12.6.8.2 增加size信息后引入的改动
12.6.8.3 在指定位置分割手指树
12.6.8.4 随机访问
12.6.8.5 命令式随机访问
12.6.8.6 命令式分割
12.7 小结
V 排序和搜索
13 分而治之，快速排序和归并排序
13.1 简介
13.2 快速排序
13.2.1 基本形式
13.2.2 严格弱序
13.2.3 划分（partition）
13.2.4 函数式划分算法的小改进
13.2.4.1 累积划分（Accumulated partition）
13.2.4.2 累积式快速排序
13.3 快速排序的性能分析
13.3.1 平均情况的分析
13.4 工程实践中的改进
13.4.1 处理重复元素的工程方法
13.4.1.1 双向划分（2-way partition）
13.4.1.2 三路划分
13.5 针对最差情况的工程实践
13.6 其他工程实践
13.7 其他
13.8 归并排序
13.8.1 基本归并排序
13.8.1.1 归并
13.8.1.2 性能
13.8.1.3 细微改进
13.9 原地归并排序
13.9.1 死板的原地归并
13.9.2 原地工作区
13.9.3 原地归并排序vs.链表归并排序
13.10 自然归并排序
13.11 自底向上归并排序
13.12 并行处理
13.13 小结
14 搜索
14.1 简介
14.2 序列搜索
14.2.1 分而治之的搜索
14.2.1.1 k选择问题
14.2.1.2 二分查找
14.2.1.3 二维搜索
14.2.1.3.1 穷举法二维搜索
14.2.1.3.2 Saddleback搜索
14.2.1.3.3 改进的saddleback搜索
14.2.1.3.4 Saddleback搜索的进一步改进
14.2.2 信息复用
14.2.2.1 Boyer-Moore众数问题
14.2.2.2 最大子序列和
14.2.2.3 KMP
14.2.2.3.1 纯函数式KMP算法
14.2.2.4 Boyer-Moore字符串匹配算法
14.2.2.4.1 不良字符（bad-character）启发条件
14.2.2.4.2 良好后缀启发条件
14.3 解的搜索
14.3.1 深度优先搜索（DFS）和广度优先搜索（BFS）
14.3.1.1 迷宫
14.3.1.2 八皇后问题
14.3.1.3 跳棋趣题
14.3.1.4 深度优先搜索的小结
14.3.1.5 狼、羊、白菜趣题
14.3.1.6 倒水问题
14.3.1.7 华容道
14.3.1.8 广度优先搜索的小结
14.3.2 搜索最优解
14.3.2.1 贪心算法
14.3.2.1.1 Huffman编码
14.3.2.1.2 换零钱问题
14.3.2.1.3 贪心方法的小结
14.3.2.2 动态规划
14.3.2.2.1 动态规划的性质
14.3.2.2.2 最长公共子序列问题
14.3.2.2.3 子集和问题
14.4 小结
VI 附录
A 列表
A.1 简介
A.2 列表的定义
A.2.1 空列表
A.2.2 获取元素和子列表
A.3 列表的基本操作
A.3.1 构建
A.3.2 判空和长度计算
A.3.3 索引
A.3.4 获取最后的元素
A.3.5 反向索引
A.3.6 修改
A.3.6.1 添加（Append）
A.3.6.2 修改指定位置上的元素
A.3.6.3 插入
A.3.6.4 删除
A.3.6.5 连接
A.3.7 和与积
A.3.7.1 递归求和与求积
A.3.7.2 尾递归
A.3.7.3 命令式的求和与求积
A.3.8 最大值和最小值
A.4 变换
A.4.1 映射（map）和for-each
A.4.1.1 映射
A.4.1.2 For each
A.4.1.3 映射的例子
A.4.2 反转
A.5 提取子列表
A.5.1 截取（take）、丢弃（drop）、和分割（split-at）
A.5.1.1 take-while和drop-while
A.5.1.2 split-at
A.5.2 切分和分组
A.5.2.1 切分
A.5.2.2 分组
A.6 Fold
A.6.1 从右侧fold
A.6.2 从左侧fold
A.6.2.1 命令式fold和抽象fold概念
A.6.3 fold的应用
A.6.3.1 连接列表的列表
A.7 搜索和匹配
A.7.1 存在检查
A.7.2 lookup
A.7.3 find和filter
A.7.4 匹配
A.8 zip和unzip
A.9 小结
【资料预览】初等算法 刘新宇 1 November 17, 2016 1刘新宇 Version: 0.6180339887498949 Email: liuxinyu95@gmail.com
