程序设计算法基础PDF电子书下载

第1章 Linux操作系统与编程环境 1

1.1 Linux基础 1

1.2 编译器 1

1.2.1 Code::Blocks安装 2

1.2.2 Code::Blocks编程环境配置 2

1.2.3 Code::Blocks编写程序 3

1.3 编译C＋＋文件 7

1.4 ACM国际大学生程序设计竞赛 8

1.5 自动评测系统 11

1.5.1 评测系统反馈 11

1.5.2 国内知名评测系统 12

第2章 算法入门 13

2.1 快速幂取模算法 13

2.1.1 模运算 13

2.1.2 幂取模的计算 16

2.1.3 例题讲解 19

2.2 算法 21

2.2.1 算法的定义 21

2.2.2 学习算法的意义 22

2.2.3 算法复杂度分析 22

第3章 基本数据结构 28

3.1 基本线性数据结构 28

3.1.1 线性表 28

3.1.2 栈 35

3.1.3 队列 37

3.1.4 例题讲解 40

3.2 二叉搜索树 45

3.2.1 二叉搜索树的定义 45

3.2.2 二叉搜索树的实现 47

3.3 C＋＋标准模板库 55

3.3.1 vector 55

3.3.2 set 58

3.3.3 map 60

3.3.4 priority＿queue 62

3.3.5 例题讲解 64

3.4 练习题 67

第4章 基本算法设计 69

4.1 枚举 69

4.1.1 枚举算法的定义 69

4.1.2 枚举算法的解题过程 69

4.1.3 枚举算法的特点 70

4.1.4 例题讲解 70

4.2 递推 73

4.2.1 递推的概念 73

4.2.2 递推与数列 73

4.2.3 斐波那契数列 73

4.2.4 递推的两种顺序 74

4.2.5 例题讲解 74

4.3 递归 76

4.3.1 递归的定义 76

4.3.2 递归的要求 76

4.3.3 递归与递推 77

4.3.4 例题讲解 78

4.4 贪心算法 80

4.4.1 贪心算法的概念 80

4.4.2 贪心算法的原理 80

4.4.3 例题讲解 81

4.5 分治算法 83

4.5.1 分治的基本思想 83

4.5.2 分治的一般解题步骤 83

4.5.3 分治的特点 84

4.5.4 归并排序 84

4.5.5 例题讲解 85

4.6 模拟 85

4.6.1 高精度计算 86

4.6.2 矩阵运算 91

4.6.3 例题讲解 94

47哈希 97

4.7.1 直接寻址表 97

4.7.2 哈希表 98

4.7.3 例题讲解 104

4.8 二分法 107

4.8.1 二分查找 107

4.8.2 二分逼近 108

4.8.3 求解性问题的二分策略 110

4.8.4 例题讲解 112

4.9 练习题 115

第5章 排序算法 118

5.1 基于比较的排序算法 118

5.1.1 简单排序 118

5.1.2 快速排序 122

5.1.3 限制和优势 123

5.2 基于统计的排序算法 124

5.2.1 计数排序 124

5.2.2 基数排序 125

5.3 例题讲解 127

5.4 练习题 127

第6章 图的基本算法 128

6.1 图的定义及存储方法 128

6.1.1 图的定义 128

6.1.2 有向图和无向图 129

6.1.3 路径与连通 129

6.1.4 图的存储结构 130

6.2 图的遍历及拓扑排序 135

6.2.1 图的深度优先遍历 135

6.2.2 图的宽度优先遍历 137

6.2.3 图的拓扑排序 137

6.2.4 例题讲解 140

6.3 最小生成树 140

6.3.1 Kruskal算法 140

6.3.2 Prim算法 142

6.4 单源最短路径 143

6.4.1 Dijkstra算法 144

6.4.2 Bellman-Ford算法 146

6.4.3 SPFA算法 147

6.4.4 差分约束系统 149

6.4.5 例题讲解 150

6.5 每对顶点的最短路径 154

6.5.1 最短路径和矩阵乘法 154

6.5.2 Floyd算法 157

6.5.3 例题讲解 158

6.6 练习题 161

第7章 并查集和线段树 164

7.1 并查集 164

7.1.1 并查集的基本概念 164

7.1.2 并查集的操作 165

7.1.3 例题讲解 171

7.2 线段树 176

7.2.1 线段树的概念与性质 176

7.2.2 线段树的基本操作 178

7.2.3 例题讲解 186

7.3 练习题 190

第8章 字符串问题 193

8.1 Trie树 193

8.1.1 Trie树的基本概念 193

8.1.2 Trie树的操作 194

8.1.3 例题讲解 197

8.2 KMP算法 200

8.2.1 BF算法简介 200

8.2.2 KMP算法原理和实现 201

8.2.3 例题讲解 205

8.3 Z算法与Manacher算法 207

8.3.1 Z算法 207

8.3.2 Manacher算法 210

8.3.3 例题讲解 214

8.4 练习题 214

第9章 搜索 217

9.1 状态空间和状态空间搜索 217

9.2 宽度优先搜索 218

9.2.1 基本概念 218

9.2.2 算法分析与实现 218

9.2.3 例题讲解 219

9.3 深度优先搜索 223

9.3.1 基本概念 223

9.3.2 算法分析与实现 223

9.3.3 例题讲解 224

9.4 双向宽度优先搜索 226

9.5 A＊搜索 227

9.5.1 基本概念 228

9.5.2 算法分析与实现 228

9.5.3 例题讲解 229

9.6 剪枝 229

9.6.1 基本概念 229

9.6.2 可行性剪枝 230

9.6.3 最优性剪枝 230

9.6.4 例题讲解 230

9.7 练习题 235

第10章 初等数论 237

10.1 初等数论简介 237

10.2 最大公约数和扩展欧几里得算法 237

10.2.1 欧几里得算法 238

10.2.2 扩展欧几里得算法 239

10.2.3 例题讲解 240

10.3 线性方程与同余方程 240

10.3.1 线性方程 240

10.3.2 例题讲解 241

10.4 乘法逆元 241

10.4.1 整数集合下逆元的求解方法 241

10.4.2 例题讲解 242

10.5 中国剩余定理 242

10.5.1 中国剩余定理 242

10.5.2 中国剩余定理的扩展 244

10.6 质数筛法与质因数分解 246

10.6.1 埃拉托斯特尼（Eratosthenes）筛法 246

10.6.2 欧拉（Euler）筛法 246

10.6.3 质因数分解 247

10.7 欧拉函数 249

10.7.1 欧拉函数与欧拉定理 249

10.7.2 例题讲解 251

10.8 原根与剩余系 251

10.9 指数方程与高次同余方程 253

10.9.1 指数方程 253

10.9.2 高次同余方程 257

10.9.3 例题讲解 260

10.10 高斯消元 264

10.11 练习题 268

第11章 动态规划入门 272

11.1 动态规划概述 272

11.1.1 数字三角形 272

11.1.2 组合数 274

11.1.3 动态规划方法求解的问题类型 275

11.1.4 例题讲解 275

11.2 背包问题 275

11.2.1 0-1背包 275

11.2.2 完全背包 277

11.2.3 多重背包 278

11.3 经典动态规划问题 281

11.3.1 最长上升子序列 281

11.3.2 最长公共子序列 282

11.3.3 矩阵链相乘问题 283

11.4 练习题 284

参考文献 285