算法基础PDF电子书下载

第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