算法设计与分析PDF电子书下载

1.1 算法简介 1

1.1.1 算法的定义 1

第1章 算法概述 1

1.1.2 算法的重要性 2

1.1.3 一个简单例子的算法表示 2

1.1.4 求最大公约数算法的细化 4

1.2 常见问题的类型 6

1.2.1 排序问题 6

1.2.2 搜索问题 7

1.2.3 字符串问题 7

1.2.4 图论问题 8

1.2.5 组合数学问题 8

1.2.6 几何问题 8

1.2.7 数值计算问题 8

1.2.8 加密问题 8

1.3.1 了解问题的内容 9

1.3.2 确定计算设备的能力 9

1.3 解决问题的一般步骤 9

1.3.3 选择精确或者近似的算法 10

1.3.4 选择合适的数据结构 10

1.3.5 选择算法设计技术 10

1.3.6 设计算法 11

1.3.7 确认算法的正确性 11

1.3.8 对该算法的分析 12

1.3.9 对算法的程序实现 12

一、选择题 13

小结 13

综合练习一 13

二、问答题 14

第2章 算法设计基础 15

2.1 常用数据结构 15

2.1.1 数组与链表 15

2.1.2 栈与队列 17

2.1.3 图与树 18

2.1.4 集合与字典 26

2.2.1 分治法 27

2.2 常用算法设计方法 27

2.2.2 贪婪法 29

2.2.3 动态规划法 30

2.2.4 回溯法 31

2.2.5 分支限定法 31

小结 31

综合练习二 32

一、选择题 32

二、问答题 33

第3章 算法分析基础 34

3.1 算法分析的基本框架 34

3.1.1 确定算法输入量 34

3.1.2 确定算法时间 34

3.1.3 算法时间复杂度的渐进表示法 36

3.1.4 具体输入对算法执行效率的影响 37

3.1.5 算法分析框架的摘要重述 38

3.2 时间复杂度渐进分析的数学基础 38

3.2.1 渐进性态的数学概念 38

3.2.2 算法渐进分析的数学表达 40

3.2.3 渐进分析的重要方法与结论 41

3.2.4 算法渐进复杂度分析的重要性 42

3.3 算法分析举例 43

3.3.1 非递归算法分析 43

3.3.2 递归算法分析 46

3.4 递归算法分析再讨论 51

3.4.1 序列与递推关系 51

3.4.2 递推关系的计算方法 51

小结 53

综合练习三 54

一、选择题 54

二、问答题 55

第4章 排序算法 56

4.1 排序相关的概念 56

4.1.1 偏序集 56

4.1.2 排序算法复杂性的计算 56

4.2 交换排序 57

4.2.1 冒泡排序 57

4.2.2 双向冒泡排序 59

4.2.3 快速排序 60

4.3 插入排序 64

4.3.1 直接插入排序 64

4.3.2 折半插入排序 66

4.3.3 希尔排序 67

4.3.4 链表插入排序 68

4.4 选择排序 70

4.4.1 直接选择排序 70

4.4.2 锦标赛排序 71

4.5 堆与堆排序 73

4.5.1 堆的概念 73

4.5.2 堆的构建与堆结点的插入 74

4.5.3 堆结点的删除 76

4.5.4 堆排序 76

4.6 归并排序 77

4.6.1 合并过程 78

4.6.2 递归的归并排序 78

4.7 统计排序 79

4.6.3 迭代的归并排序 79

4.7.1 比较统计排序 80

4.7.2 分布统计排序 81

4.8 外排序简介 82

小结 83

综合练习四 84

一、选择题 84

二、问答题 85

5.1.2 搜索环境 86

5.1.3 索引的使用 86

5.1 搜索相关的概念 86

5.1.1 搜索表与关键字 86

第5章 搜索算法 86

5.1.4 搜索算法效率的衡量 87

5.2 静态搜索表的算法 87

5.2.1 顺序搜索算法 87

5.2.2 有序表的折半搜索 88

5.2.3 Fibonacci搜索 92

5.3 二叉搜索树搜索 95

5.3.1 二叉搜索树相关概念 96

5.3.2 二叉搜索树的搜索 96

5.3.3 二叉搜索树的插入 98

5.3.4 二叉搜索树的删除 99

5.3.5 二叉搜索树效率分析 100

5.4 AVL树 101

5.4.1 AVL树相关概念 101

5.4.2 AVL树的平衡旋转 102

5.4.3 AVL树的插入 104

5.4.4 AVL树的删除 105

5.4.5 AVL树的高度 106

5.5 2-3树 107

5.5.1 基本概念 107

5.5.2 搜索算法 107

5.5.3 插入算法 107

5.5.4 2-3树的高度 108

5.6 最优二叉搜索树 108

5.6.1 一般情况下时间复杂度计算 108

5.6.2 最优二叉搜索树构造算法 110

5.6.3 最优二叉搜索树构造实例 112

5.7 索引结构 113

5.7.1 线性索引结构 114

5.7.2 多级索引 115

5.7.3 动态m路搜索树 116

5.7.4 平衡m路搜索树（B树） 117

5.8 散列方法 118

5.8.1 散列方法介绍 118

5.8.3 散列函数的建立 119

5.8.2 散列方法的过程 119

5.8.4 冲突的解决 121

5.8.5 散列效率的衡量 122

小结 122

综合练习五 123

一、选择题 123

二、问答题 124

6.1.2 数据表的模式 125

6.1.1 数据表元素的惟一性 125

6.1 搜索问题扩展 125

第6章 类搜索算法与字符串匹配算法 125

6.1.3 确定数据表中不同的元素 127

6.1.4 确定数据表第k小的元素 128

6.2 搜索与排序 130

6.2.1 比较排序算法复杂度 130

6.2.2 搜索算法与排序 131

6.2.3 预排序算法 132

6.3 字符串匹配算法 133

6.3.1 字符串匹配的基本概念 133

6.3.2 直接匹配算法 133

6.3.3 KMP算法 135

6.3.4 Horspool算法 139

6.3.5 BM算法 142

6.3.6 RK算法 145

综合练习六 147

一、选择题 147

小结 147

二、问答题 148

第7章 图与树相关算法 149

7.1 二叉树的遍历 149

7.1.1 中序遍历 149

7.1.2 前序遍历 150

7.1.3 后序遍历 151

7.1.4 二叉树遍历的应用 152

7.2.1 二叉树的确定 154

7.2 二叉树的计数 154

7.2.2 中序遍历的非递归算法 155

7.2.3 二叉树个数 155

7.3 图的遍历 156

7.3.1 深度优先搜索 157

7.3.2 广度优先搜索 160

7.3.3 DFS与BFS比较 162

7.3.4 DFS的应用：重连通图 163

7.4.2 带权图的路径长度 164

7.4.1 图的路径长度 164

7.4 图的路径与带权路径 164

7.3.5 BFS的应用：最短路径 164

7.4.3 带权路径的表示方法 165

7.4.4 路径长度问题分类 165

7.5 两点之间的最短路径 166

7.5.1 非负权图的Dijkstra算法 166

7.5.2 任意权值的Bellman-Ford算法 168

7.6.1 Warshall算法 171

7.6 任意点之间的最短路径 171

7.6.2 Floyd算法 172

7.7 最小生成树 174

7.7.1 Kruskal算法 174

7.7.2 Prim算法 176

7.8 最大流量问题 177

7.8.1 网络流量问题与线性规划 177

7.8.2 最大流量的Edmonds-Karp算法 178

7.9 最小费用最大流量问题 183

7.10.1 最小带权路径长度 186

7.10 霍夫曼树 186

7.10.2 霍夫曼树的应用 187

7.11 图的应用举例 188

7.11.1 七桥问题 188

7.11.2 人狼羊菜渡船问题 189

7.11.3 课程安排问题 190

小结 191

综合练习七 191

一、选择题 191

二、问答题 193

第8章 几何问题算法 194

8.1 几何形体在计算机中的表示 194

8.1.1 基本几何形体的表示 194

8.1.2 直线段的显示算法 194

8.2 初等几何问题算法 197

8.2.1 直线相交判断 197

8.2.2 直线的倾角 199

8.3 最近邻点问题算法 199

8.3.1 最近邻点的一般解法 199

8.3.2 最近邻点问题的分治法 200

8.4 凸包问题算法 203

8.4.1 包问题的一般算法 203

8.4.2 包问题的分治法 204

小结 205

综合练习八 205

一、选择题 205

二、问答题 206

第9章 数值算法 207

9.1 杨辉三角 207

9.2 多项式求值 208

9.2.1 一般算法 208

9.2.2 Horner法则 209

9.2.3 二进制求幂算法 210

9.3 大整数乘法 211

9.3.1 算法思想 212

9.4.1 线性方程组 213

9.4 线性方程组与高斯消元法 213

9.3.3 算法分析 213

9.3.2 算法伪代码 213

9.4.2 高斯消元法 214

9.4.3 矩阵的LU分解 216

9.5 矩阵基本运算 217

9.5.1 矩阵乘法 217

9.5.2 矩阵的逆 218

小结 219

9.5.3 矩阵行列式 219

综合练习九 220

一、选择题 220

二、问答题 220

第10章 组合问题算法 221

10.1 排列问题 221

10.1.1 降低规模求解算法 221

10.1.2 Johnson-Trotter算法 222

10.1.3 字典排序算法 222

10.2.1 降低规模的幂集算法 223

10.2.2 求幂集的位串法 223

10.2 幂集问题 223

10.3 背包问题 224

10.3.1 超递增序列背包问题的求解 224

10.3.2 背包问题的穷举法 224

10.3.3 动态规划法求解背包问题 225

10.4 旅行家问题 227

小结 227

一、选择题 228

综合练习十 228

二、问答题 229

第11章 加密算法与安全机制 230

11.1 加密算法 230

11.1.1 DES算法 230

11.1.2 RSA算法 236

11.1.3 MD5算法 241

11.1.4 算法实现与性能比较 244

11.2 安全机制 244

11.2.1 鉴别协议 244

11.2.2 消息完整性协议 247

11.2.3 公开密钥分发协议 248

小结 251

综合练习十一 252

一、选择题 252

二、问答题 253

第12章 算法复杂性理论简介 254

12.1 算法问题 254

12.1.1 可解问题与不可解问题 254

12.1.2 P问题与NP问题 255

12.1.3 NP理论的核心问题 256

12.2 图灵机简介 256

小结 258

综合练习十二 258

一、选择题 258

二、问答题 259

附录 算法伪代码索引 260

参考答案 263

参考文献 268