算法与数据结构PDF电子书下载

第1章 开胃菜：整数运算 1

1.1 加法 2

1.2 乘法：学校方法 2

1.3 结果检查 5

1.4 递归版的学校方法 6

1.5 Karatsuba乘法 7

1.6 算法工程 9

1.7 程序 10

1.8 引理1.5和定理1.7的证明 13

1.9 实现提示 14

1.9.1 C++ 14

1.9.2 Java 14

1.10 历史注释与进一步的读物 15

第2章 概述 16

2.1 渐近表示法 16

2.2 机器模型 19

2.2.1 外部存储器 20

2.2.2 并行处理 21

2.3 伪代码 21

2.3.1 变量和基本数据类型 21

2.3.2 语句 23

2.3.3 过程与函数 23

2.3.4 面向对象 25

2.4 设计正确的算法和程序 25

2.4.1 断言和不变量 26

2.4.2 循环不变量 26

2.4.3 数据结构不变量 27

2.4.4 验证算法 27

2.5 一个示例：二分查找 27

2.6 基本算法分析 29

2.6.1 求和 29

2.6.2 递推 30

2.6.3 全局参数 33

2.7 平均情况分析 33

2.7.1 递增计数器 33

2.7.2 从左到右的最大值 34

2.7.3 线性搜索 35

2.8 随机算法 36

2.8.1 形式模型 37

2.8.2 Las Vegas和Monte Carlo算法 38

2.9 图 39

2.9.1 第一个图算法 41

2.9.2 树 41

2.9.3 有序树 42

2.10 P与NP 43

2.11 实现提示 45

2.11.1 C++ 45

2.11.2 Java 46

2.12 历史注释与进一步的读物 46

第3章 用数组与链表表示序列 47

3.1 链表 48

3.1.1 双链表 48

3.1.2 单链表 51

3.2 无界数组 52

3.2.1 无界数组的平摊分析：全局参数 53

3.2.2 无界数组的平摊分析：局部参数 55

3.2.3 二进制计数器的平摊分析 55

3.3 平摊分析 56

3.3.1 平摊分析：势能方法或银行账户方法 57

3.3.2 势能方法的普遍性 58

3.4 栈与队列 58

3.5 链表与数组 60

3.6 实现提示 61

3.6.1 C++ 61

3.6.2 Java 62

3.7 历史注释与进一步的读物 62

第4章 散列表与关联数组 64

4.1 链接法散列 66

4.2 通用散列 67

4.3 线性探测散列 71

4.4 链接法与线性探测法 72

4.5 完全散列 73

4.6 实现提示 75

4.6.1 C++ 76

4.6.2 Java 76

4.7 历史注释与进一步的读物 76

第5章 排序与选择 78

5.1 简单排序 80

5.2 归并排序——O（nlogn）的排序算法 81

5.3 下界 83

5.4 快速排序 85

5.4.1 分析 85

5.4.2 细化 87

5.5 选择 89

5.6 打破下界 91

5.7 外部排序 93

5.7.1 多路归并 94

5.7.2 采样排序 94

5.8 实现提示 96

5.8.1 C/C++ 97

5.8.2 Java 97

5.9 历史注释与进一步的读物 97

第6章 优先级队列 99

6.1 二叉堆 100

6.2 可寻址的优先级队列 104

6.2.1 配对堆 104

6.2.2 斐波那契堆 106

6.3 外部存储器 109

6.4 实现提示 110

6.4.1 C++ 110

6.4.2 Java 110

6.5 历史注释与进一步的读物 111

第7章 有序序列 112

7.1 二叉搜索树 113

7.2 （a,b）-树与红黑树 115

7.3 更多的操作 121

7.3.1 连接 121

7.3.2 拆分 122

7.4 更新操作的平摊分析 123

7.5 增强搜索树 124

7.5.1 父指针 125

7.5.2 子树大小 125

7.6 实现提示 126

7.6.1 C++ 127

7.6.2 Java 127

7.7 历史注释与进一步的读物 128

第8章 图的表示 130

8.1 无序的边序列 131

8.2 邻接数组——静态图 132

8.3 邻接表——动态图 132

8.4 邻接矩阵表示 133

8.5 隐式表示 134

8.6 实现提示 134

8.6.1 C++ 135

8.6.2 Java 135

8.7 历史注释与进一步的读物 135

第9章 图的遍历 137

9.1 广度优先搜索 137

9.2 深度优先搜索 139

9.2.1 DFS编号、完成时间和拓扑排序 140

9.2.2 强连通分量 142

9.3 实现提示 147

9.3.1 C++ 147

9.3.2 Java 148

9.4 历史注释与进一步的读物 148

第10章 最短路径 149

10.1 从基本概念到遗传算法 150

10.2 有向无环图 153

10.3 非负边代价（Dijkstra算法） 153

10.4 Dijkstra算法的平均情况分析 156

10.5 单调整数优先级队列 157

10.5.1 桶队列 157

10.5.2 基数堆 158

10.6 任意边代价（Bellman-Ford算法） 161

10.7 所有点对最短路径和节点的势 162

10.8 最短路径查询 163

10.8.1 目标定向搜索 164

10.8.2 等级 166

10.8.3 中转节点路线 166

10.9 实现提示 167

10.9.1 C++ 167

10.9.2 Java 167

10.10 历史注释与进一步的读物 168

第11章 最小生成树 169

11.1 割和环的性质 170

11.2 Jarník-Prim算法 171

11.3 Kruskal算法 172

11.4 并-查数据结构 173

11.5 外部存储器 176

11.5.1 Semiexternal的Kruskal算法 176

11.5.2 边收缩 176

11.5.3 Sibeyn算法 176

11.6 应用程序 178

11.6.1 Steiner树问题 178

11.6.2 旅行推销员之旅 179

11.7 实现提示 180

11.7.1 C++ 180

11.7.2 Java 180

11.8 历史注释与进一步的读物 180

第12章 遗传方法优化 182

12.1 线性规划：黑盒求解器 183

12.1.1 整数线性规划 185

12.2 贪婪算法：永不回头 186

12.3 动态规划：子问题的构建 189

12.4 系统搜索：有疑问，用蛮力 192

12.4.1 求解整数线性规划 194

12.5 局部搜索：全局思考，局部行动 194

12.5.1 爬山 195

12.5.2 模拟退火：从自然中学习 196

12.5.3 局部搜索的优化 201

12.6 进化算法 201

12.7 实现提示 203

12.8 历史注释与进一步的读物 204

附录A 205

A.1 数学符号 205

A.2 数学概念 206

A.3 概率论基础 207

A.4 有用的公式 210

A.4.1 证明 211

参考文献 213