第1章 算法基础知识 1
1.1方法 1
1.2算法和数据结构 2
1.3伪代码 2
1.4算法的特点 4
1.4.1大O符号 5
1.4.2常见的运行时间函数 7
1.4.3可视化函数 12
1.5实际因素 12
1.6总结 13
练习 13
第2章 数值算法 16
2.1随机化数据 16
2.1.1随机数生成 16
2.1.2随机化数组 20
2.1.3生成不均匀分布 21
2.2寻找最大公约数 21
2.3求幂运算 23
2.4有关素数的运算 24
2.4.1寻找素数因子 24
2.4.2寻找素数 26
2.4.3素性测试 27
2.5进行数值积分 28
2.5.1矩形规则 28
2.5.2梯形规则 29
2.5.3自适应求积 30
2.5.4蒙特卡罗积分 32
2.6查找零 32
2.7总结 34
练习 34
第3章 链表 36
3.1基本概念 36
3.2单链表 37
3.2.1遍历链表 37
3.2.2查找单元格 37
3.2.3使用哨兵 38
3.2.4在开头添加单元格 39
3.2.5在结尾添加单元格 40
3.2.6在某个单元格后插入单元格 40
3.2.7删除单元格 41
3.3双向链表 42
3.4有序链表 43
3.5链表算法 44
3.5.1复制链表 44
3.5.2链表的插入排序 45
3.6链表的选择排序 46
3.7多线程链表 47
3.8循环链表 48
3.8.1标记单元格 49
3.8.2使用散列表 50
3.8.3链表回溯 51
3.8.4反转链表 51
3.8.5乌龟和兔子 53
3.8.6双向链表中的循环问题 55
3.9总结 55
练习 55
第4章 数组 57
4.1基本概念 57
4.2一维数组 58
4.2.1查找元素 58
4.2.2查找最大值、最小值、平均值 59
4.2.3插入元素 60
4.2.4移除元素 61
4.3非零下界 61
4.3.1二维数组 61
4.3.2多维数组 62
4.4三角形数组 64
4.5稀疏数组 66
4.5.1找到行或列 67
4.5.2获取值 68
4.5.3设置值 69
4.5.4删除值 71
4.6矩阵 72
4.7总结 74
练习 74
第5章 栈和队列 76
5.1栈 76
5.1.1栈的链表实现 76
5.1.2栈的数组实现 77
5.1.3双向栈 78
5.1.4栈的算法 79
5.2队列 84
5.2.1队列的链表实现 84
5.2.2队列的数组实现 85
5.2.3专用队列 86
5.3总结 87
练习 87
第6章 排序 89
6.1时间复杂度为O（N2）的算法 89
6.1.1数组中的插入排序 89
6.1.2数组中的选择排序 90
6.1.3冒泡排序 91
6.2时间复杂度为O（N logN）的算法 93
6.2.1堆排序 93
6.2.2快速排序 98
6.2.3归并排序 103
6.3时间复杂度为亚O（N logN）的算法 105
6.3.1计数排序 106
6.3.2桶排序 107
6.4总结 108
练习 108
第7章 搜索 110
7.1线性搜索 110
7.2二分搜索 111
7.3插值搜索 112
7.4总结 113
练习 113
第8章 散列表 114
8.1散列表的基础知识 114
8.2链 115
8.3开放寻址 116
8.3.1删除记录 117
8.3.2线性探测 118
8.3.3二次探测 119
8.3.4伪随机探测 120
8.3.5双散列 120
8.3.6有序散列 121
8.4总结 122
练习 123
第9章 递归 125
9.1基础算法 125
9.1.1阶乘 125
9.1.2斐波那契数 127
9.1.3汉诺塔 128
9.2图算法 130
9.2.1科赫曲线 130
9.2.2希尔伯特曲线 131
9.2.3谢尔宾斯基曲线 132
9.2.4垫片 134
9.3回溯算法 134
9.3.1八皇后问题 136
9.3.2骑士巡游 138
9.4选择与排列 140
9.4.1循环选择 140
9.4.2重复选择 141
9.4.3不重复选择 142
9.4.4元素可重复的排列 143
9.4.5元素不重复的排列 144
9.5消去递归 145
9.5.1尾递归的消除 145
9.5.2存储中间值 146
9.5.3一般递归的消除 148
9.6总结 150
练习 151
第10章树 153
10.1树的术语 153
10.2二叉树属性 155
10.3树的表示 157
10.3.1建立树的通用方法 157
10.3.2构造完全树 159
10.4树的遍历 160
10.4.1前序遍历 160
10.4.2中序遍历 162
10.4.3后序遍历 163
10.4.4深度优先遍历 164
10.4.5遍历的运行时间 164
10.5排序树 165
10.5.1添加结点 165
10.5.2查找结点 166
10.5.3删除结点 167
10.6线索树 168
10.6.1建立线索树 169
10.6.2使用线索树 171
10.7特化树算法 172
10.7.1动物游戏 172
10.7.2表达式求值 173
10.7.3四叉树 175
10.7.4 Trie树 179
10.8总结 182
练习 182
第11章 平衡树 185
11.1 AVL树 185
11.1.1添加值 185
11.1.2删除值 187
11.2 2-3树 187
11.2.1添加值 188
11.2.2删除值 189
11.3 B树 191
11.3.1添加值 191
11.3.2删除值 192
11.4平衡树变体 193
11.4.1自上而下的B树 193
11.4.2 B＋树 193
11.5总结 194
练习 195
第12章 决策树 196
12.1游戏搜索树 196
12.1.1极小化极大值算法 197
12.1.2初始步骤和反应 199
12.1.3启发式游戏树 200
12.2搜索通用决策树 201
12.2.1优化问题 202
12.2.2穷举搜索 202
12.2.3分支界限 203
12.2.4决策树的启发式搜索 205
12.2.5其他决策树问题 209
12.3总结 212
练习 195
第13章 基本网络算法 214
13.1网络术语 214
13.2网络的表示方法 216
13.3网络的遍历 218
13.3.1深度优先遍历 218
13.3.2广度优先遍历 220
13.3.3连通性测试 221
13.3.4生成树 223
13.3.5最小生成树 224
13.4寻找路径 225
13.4.1寻找任一路径 225
13.4.2标签设置最短路径 225
13.4.3标签校正最短路径 227
13.4.4任意两点间最短路径 228
13.5总结 232
练习 232
第14章 更多的网络算法 234
14.1拓扑排序 234
14.2回路检测 236
14.3地图着色 237
14.3.1两色着色 237
14.3.2三色着色 238
14.3.3四色着色 239
14.3.4五色着色 239
14.3.5其他地图着色算法 241
14.4最大流 242
14.4.1工作分配 243
14.4.2最小割 244
14.5总结 245
练习 246
第15章 字符串算法 247
15.1括号匹配 247
15.1.1求算术表达式 248
15.1.2构建解析树 248
15.2模式匹配 249
15.2.1DFA 249
15.2.2为正则表达式建立DFA 251
15.2.3 NFA 252
15.3字符串搜索 253
15.4计算编辑距离 256
15.5总结 258
练习 258
第16章 密码学 260
16.1术语 260
16.2换位密码 261
16.2.1行/列换位 261
16.2.2列换位 262
16.2.3路由加密算法 263
16.3替换密码 264
16.3.1凯撒替换 264
16.3.2维吉尼亚密码 265
16.3.3简单替换密码 266
16.3.4一次性密码本 266
16.4分组密码 267
16.4.1代换-置换网络 267
16.4.2 Feistel密码 268
16.5公钥加密和RSA 269
16.5.1欧拉函数 270
16.5.2在取模运算下的乘法逆元素 270
16.5.3一个RSA的例子 270
16.5.4现实思考 271
16.6加密技术的其他用途 271
16.7总结 272
练习 273
第17章 复杂性理论 274
17.1符号 274
17.2复杂性分类 275
17.3归约 277
17.3.1 3SAT 278
17.3.2二分图匹配 278
17.4 NP难问题 279
17.5检测、报告和优化问题 279
17.5.1检测≤p报告 279
17.5.2报告≤p优化 280
17.5.3报告≤p检测 280
17.5.4优化≤p报告 280
17.6 NP完全问题 281
17.7总结 282
练习 283
第18章 分布式程序设计 284
18.1并行的种类 284
18.1.1脉动阵列 284
18.1.2分布式计算 286
18.1.3多CPU的处理 287
18.1.4竞争条件 287
18.1.5死锁 290
18.1.6量子计算 291
18.2分布式算法 291
18.2.1调试分布式算法 292
18.2.2高度并行算法 292
18.2.3归并排序 293
18.2.4哲学家进餐 294
18.2.5两个将军问题 296
18.2.6拜占庭将军 297
18.2.7一致性 298
18.2.8领导人选举 301
18.2.9快照 301
18.2.10时钟同步 302
18.3总结 303
练习 303
第19章 面试难题 305
19.1面试难题提问 306
19.2面试难题回答 307
19.3总结 309
练习 311
附录A算法概念综述 312
附录B练习解答 320
索引 371