数据与算法PDF电子书下载

第1章 数据、数学模型和算法 1

1.1 数据时代 1

1.1.1 什么是数据 1

1.1.2 大数据时代 2

1.1.3 数据的重要性 4

1.2 数据的表示 5

1.2.1 二元关系及其性质 5

1.2.2 数据的逻辑结构 9

1.2.3 数据的存储结构 12

1.2.4 抽象数据类型 12

1.3 数学模型 13

1.3.1 什么是数学模型 13

1.3.2 数学模型的种类 14

1.3.3 数学模型与计算机 15

1.3.4 数据结构 16

1.4 算法及复杂度分析 16

1.4.1 什么是算法 16

1.4.2 问题与解 17

1.4.3 算法的分析与评价 18

1.5 本章小结 22

第2章 线性结构 24

2.1 线性表 24

2.1.1 线性表的概念及其抽象数据类型 24

2.1.2 线性表的顺序存储——顺序表 27

2.1.3 线性表的链式存储——链表 30

2.1.4 线性表小结 35

2.2 栈 35

2.2.1 栈的概念与实现 35

2.2.2 栈的应用 38

2.2.3 递归 41

2.3 队列 48

2.3.1 队列的概念与实现 48

2.3.2 优先级队列 51

2.4 字符串 55

2.4.1 字符串的概念和ADT 55

2.4.2 字符串的存储表示 56

2.4.3 字符串的模式匹配和简单匹配算法 57

2.4.4 KMP算法 58

2.5 本章小结 61

第3章 树与二叉树 62

3.1 树的基本概念 62

3.1.1 普遍存在的树结构 62

3.1.2 树的定义和性质 65

3.2 二叉树 67

3.2.1 二叉树的定义和性质 68

3.2.2 二叉树的表示和实现 70

3.2.3 二叉树的遍历 76

3.2.4 二叉树运算 81

3.2.5 二叉树的建立 83

3.3 二叉树的应用 84

3.3.1 表达式求值 84

3.3.2 二叉搜索树 85

3.3.3 Huffman树与编码 89

3.3.4 堆 95

3.4 并查集 102

3.5 本章小结 103

第4章 图 105

4.1 图的基本概念 105

4.1.1 图的定义和概念 105

4.1.2 图的抽象数据类型 110

4.1.3 欧拉路径 110

4.2 图的存储结构 112

4.2.1 图的邻接矩阵表示 112

4.2.2 图的邻接表表示 115

4.2.3 图的其他表示方法 119

4.3 图的遍历 122

4.3.1 图的深度优先遍历 123

4.3.2 图的广度优先遍历 124

4.3.3 图遍历的应用 125

4.3.4 图的连通性 128

4.4 有向图与有向无环图 129

4.4.1 有向图的连通性和传递闭包 129

4.4.2 有向无环图和拓扑排序 132

4.4.3 关键路径 135

4.5 最小生成树 137

4.5.1 图的生成树与最小生成树 137

4.5.2 普里姆（Prim）算法 139

4.5.3 克鲁斯卡尔（Kruskal）算法 142

4.6 最短路径问题 144

4.6.1 单源最短路径 145

4.6.2 全源最短路径 147

4.7 最大流 149

4.7.1 网络流的基本概念 150

4.7.2 Ford-Fulkerson方法 151

4.8 匹配 154

4.8.1 二分图和匹配的基本概念 154

4.8.2 匈牙利算法 155

4.8.3 最大匹配与最大流 157

4.9 本章小结 157

第5章 查找和排序 159

5.1 线性查找表 159

5.1.1 顺序查找 160

5.1.2 折半查找 161

5.1.3 斐波那契查找 162

5.1.4 线性查找表的性能比较 163

5.2 静态索引结构 164

5.2.1 索引查找 164

5.2.2 索引存储方式 164

5.2.3 索引文件结构 167

5.3 二叉搜索树查找性能 169

5.4 散列方法 172

5.4.1 散列技术的基本思想 172

5.4.2 散列函数 173

5.4.3 冲突处理 175

5.4.4 散列的删除 178

5.4.5 散列的性能 178

5.5 排序的概念及算法性能分析 179

5.6 基本排序方法 180

5.6.1 冒泡排序 181

5.6.2 插入排序 182

5.6.3 直接选择排序 187

5.6.4 基本排序方法的比较 188

5.7 快速排序 189

5.7.1 快速排序的过程 189

5.7.2 快速排序的性能分析 191

5.8 归并排序 192

5.8.1 二路归并 192

5.8.2 自底向上的归并排序 192

5.8.3 自顶向下的归并排序 194

5.9 堆和堆排序 195

5.9.1 堆排序的思想 195

5.9.2 堆排序的实现 197

5.10 内排序方法分析 198

5.10.1 排序方法的下界 198

5.10.2 内排序方法的比较 199

5.11 本章小结 200

第6章 数值计算问题 202

6.1 引言 202

6.2 近似与误差 204

6.2.1 误差的定义 204

6.2.2 误差的分类 209

6.2.3 条件数与敏感性 212

6.3 实数的表示与运算 214

6.3.1 浮点数系统 214

6.3.2 浮点运算 217

6.4 一元方程求解 219

6.4.1 一元方程 219

6.4.2 二分法 220

6.4.3 不动点法 222

6.4.4 牛顿法 225

6.4.5 迭代误差分析 229

6.5 线性方程组求解 232

6.5.1 线性方程组 232

6.5.2 向量与矩阵范数 234

6.5.3 线性方程组敏感性 239

6.5.4 线性方程组直接解法 242

6.5.5 线性方程组迭代解法 252

6.6 拟合与插值 256

6.6.1 线性最小二乘 256

6.6.2 多项式插值 264

6.7 本章小结 267

第7章 最优化初步 268

7.1 优化问题及其性质 268

7.2 无约束优化问题 271

7.2.1 优化条件 271

7.2.2 一维优化 272

7.2.3 多维优化 275

7.3 约束优化问题 279

7.3.1 优化条件 279

7.3.2 序列二次规划法 282

7.3.3 障碍法 284

7.4 凸优化 286

7.4.1 凸集合 286

7.4.2 凸函数 289

7.4.3 凸优化问题 292

7.5 组合优化的数值求解 294

7.5.1 组合优化问题 294

7.5.2 线性规划初步 296

7.5.3 顶点覆盖的线性规划求解 297

7.6 本章小结 298

第8章 随机算法 299

8.1 随机性与随机数 299

8.2 舍伍德与拉斯维加斯算法 301

8.3 蒙特卡洛算法 304

8.4 模拟退火与遗传算法 307

8.5 本章小结 310

第9章 算法设计思想 311

9.1 蛮力法 311

9.2 分治法 313

9.2.1 分治法的运行时间 314

9.2.2 分治法应用举例 316

9.2.3 减治法 319

9.2.4 变治法 321

9.3 贪心法 323

9.4 动态规划 326

9.4.1 动态规划的基本原理 326

9.4.2 算法设计举例 328

9.5 搜索算法：回溯法与分支定界法 334

9.5.1 组合优化问题的解空间 334

9.5.2 回溯法 338

9.5.3 分支定界法 342