计算机算法与程序设计PDF电子书下载

第1章 绪论 1

1.1算法研究的意义 1

1.2算法与程序 7

1.3算法的描述工具 13

1.4算法的复杂性分析 16

1.4.1时间复杂度 16

1.4.2空间复杂度 19

1.5常用数学分析公式 21

第2章 数据抽象与数据结构 24

2.1数据抽象概念 24

2.1.1数据结构的基本概念和术语 24

2.1.2数据抽象 25

2.2基本数据结构 28

2.2.1线性表与向量 28

2.2.2链表 31

2.2.3栈和队列 33

2.2.4二叉树 39

2.2.5图 42

2.3关键数据结构拓广 45

2.3.1哈希表 45

2.3.2并查集（等价类） 48

2.3.3线段树 50

2.3.4二叉堆 52

第3章 初等数论 55

3.1数论基础 55

3.1.1素数与算术基本定理 55

3.1.2最大公约数与最小公倍数 56

3.2同余方程 58

3.2.1同余方程概念 58

3.2.2中国剩余定理 60

3.3数论函数 61

3.3.1欧拉函数 61

3.3.2积性函数 63

3.4素数和整除 64

3.4.1筛法求素数 64

3.4.2整数N的因子函数 65

3.5高精度计算 67

第4章 组合数学初步 72

4.1加法原理与乘法原理 72

4.2鸽笼原理和Ramsey数 74

4.3递推关系和生成函数 76

4.3.1 Fibonacci数 77

4.3.2 Catalan数 78

4.3.3第二类Stirling数 81

4.4排列组合 82

4.4.1字典序排列 82

4.4.2组合算法 83

4.4.3二项式系数 85

4.5容斥原理 86

4.5.1容斥原理的概念 86

4.5.2错排问题 87

4.6 Polya定理及其应用 89

第5章 递归与分治策略 94

5.1递归概念 94

5.1.1递归与递归调用 94

5.1.2递归应用 98

5.2分治法概述 100

5.2.1分治法基本思想 100

5.2.2分治算法设计和特点 101

5.3分治法的基本应用 103

5.3.1最大最小值 103

5.3.2 Strassen矩阵乘法 104

5.4分治法解骑士周游 107

5.5大整数乘法 109

5.5.1常规大整数乘法 109

5.5.2分治法解大整数乘法 111

5.6棋盘覆盖问题 112

第6章 贪心算法 114

6.1贪心算法概述 114

6.1.1贪心举例 114

6.1.2贪心算法的理论基础 116

6.1.3贪心算法与动态规划算法的区别 117

6.2背包问题 118

6.3机器任务调度算法 119

6.3.1多机调度问题 119

6.3.2活动安排问题 120

6.4最小生成树 122

6.4.1普里姆（Prim）算法 122

6.4.2克鲁斯卡尔（Kruskal）算法 123

6.5哈夫曼（Huffman）树及其应用 126

6.5.1 Huffman树 126

6.5.2哈夫曼编码 129

6.5.3 Huffman算法的正确性 130

第7章 动态规划 132

7.1动态规划算法思想 132

7.1.1动态规划最优决策原理 132

7.1.2动态规划求解步骤 134

7.1.3动态规划的数学抽象 137

7.2矩阵连乘问题 138

7.3最长子序列探索 141

7.3.1最长递增子序列 141

7.3.2最长公共子序列 143

7.4多段图的最短路径 145

7.5资源分配问题 149

7.6树状动态规划 151

第8章 搜索技术 154

8.1盲目搜索算法 154

8.1.1对分搜索 154

8.1.2 DFS与BFS搜索算法 156

8.1.3盲目搜索算法应用 160

8.2回溯算法 162

8.3启发式搜索 165

8.3.1启发式搜索策略 165

8.3.2 A*算法 167

8.4博弈问题 170

8.4.1博弈树 170

8.4.2极小极大搜索法 172

8.5 α-β剪枝技术 173

第9章 图论算法 176

9.1基本概念和定理 176

9.1.1可行遍性问题 177

9.1.2平面图 177

9.1.3独立集、覆盖与支配集 180

9.2最短路径 182

9.2.1 Dijkstra算法 182

9.2.2 Floyd算法求一对点最短路径 184

9.3道路和回路 186

9.3.1欧拉道路和欧拉回路 186

9.3.2哈密尔顿图和货郎担问题 188

9.4网络流算法 193

9.4.1基本概念 193

9.4.2最大流问题 195

9.4.3最小费用流 198

9.5二分图相关问题 200

9.5.1二分图的最大匹配 200

9.5.2二分图的最佳匹配 203

第10章 计算几何 207

10.1计算几何基本问题 207

10.1.1矢量与线段 207

10.1.2几何计算公式 209

10.2点与线段的关系 212

10.2.1点与线段的距离 212

10.2.2线段与直线的交点 214

10.3多边形 217

10.3.1多边形基本概念 217

10.3.2点与多边形的关系 218

10.4凸包问题 219

10.4.1判断凸包 219

10.4.2寻找凸包 220

10.5欧拉定理及其应用 221

第11章 排序 224

11.1排序基础 224

11.2比较排序法 225

11.2.1插入排序 225

11.2.2冒泡排序 227

11.2.3简单选择排序 228

11.3基于分治策略的排序算法 229

11.3.1快速排序 229

11.3.2归并排序 233

11.4堆排序 235

11.4.1树状选择排序 235

11.4.2堆排序 235

11.5基数排序 238

11.6排序小结 241

第12章 算法与程序经典实例 44

12.1计算机算法设计实例 244

12.2国际竞赛程序实例分析 252