从算法到程序PDF格式文档图书下载

第1章 计算问题 1

1.1 计算问题及其算法 1

1.1.1 计算问题及其描述 1

1.1.2 算法及其描述 2

1.1.3 伪代码的使用约定 3

1.1.4 算法分析 4

1.1.5 算法运行时间的渐近表示 5

1.2 数据结构 6

1.2.1 什么是数据结构 6

1.2.2 数据结构对算法效率的影响 7

1.2.3 字典与字典操作 8

1.3 程序设计 10

1.3.1 算法与程序 10

1.3.2 数据类型的抽象与代码通用性 11

1.4 数据的输入输出 13

1.4.1 应用问题 13

1.4.2 标准输入输出 15

1.4.3 文件输入输出 20

1.5 计数问题 22

1.5.1 简单模拟 23

1.5.2 加法原理和乘法原理 25

1.5.3 计算四边形个数 31

第2章 数据结构基础 37

2.1 线性表 38

2.1.1 线性表的链表表示 38

2.1.2 对链表的操作 39

2.1.3 链表的程序实现 42

2.1.4 链表应用 47

2.2 栈 53

2.2.1 栈的概念及其链表实现 53

2.2.2 栈的程序实现 54

2.2.3 栈的应用 56

2.3 队列 62

2.3.1 队列的概念及其链表实现 62

2.3.2 队列的程序实现 63

2.3.3 队列的应用 64

2.4 二叉搜索树 68

2.4.1 二叉树及其在计算机中的表示 68

2.4.2 二叉搜索树 76

2.4.3 二叉搜索树的查询操作 76

2.4.4 二叉搜索树中元素的增删 78

2.4.5 红-黑树及其性质 80

2.4.6 红-黑树的操作 83

2.4.7 红-黑树的程序实现 92

2.4.8 二叉搜索树的应用 102

2.5 散列表 102

2.5.1 直接寻址表与散列表 102

2.5.2 用拉链法解决冲突 104

2.5.3 散列表的程序实现 106

2.5.4 散列表的应用 109

第3章 基本算法设计策略 112

3.1 渐增型算法 112

3.1.1 有序序列的合并问题 112

3.1.2 序列的划分问题 117

3.2 分治算法 121

3.2.1 归并排序算法 122

3.2.2 快速排序算法 126

3.2.3 序统计与选择问题 130

3.3 排序问题的讨论 132

3.3.1 排序的性质 132

3.3.2 比较型排序算法的时间复杂度 133

3.3.3 应用 136

3.4 堆与基于堆的优先队列 141

3.4.1 堆的概念及其创建 141

3.4.2 基于二叉堆的优先队列 149

3.4.3 应用 153

第4章 代数计算 169

4.1 矩阵及其计算 169

4.1.1 矩阵与向量 169

4.1.2 矩阵的运算 171

4.1.3 矩阵的性质 173

4.1.4 矩阵的程序实现 174

4.2 矩阵的LUP分解 176

4.2.1 LUP分解法概述 177

4.2.2 LU分解 178

4.2.3 计算LUP分解 179

4.2.4 程序实现 182

4.3 解线性方程组 183

4.3.1 前代法和回代法 183

4.3.2 用LUP分解计算矩阵的逆 185

4.3.3 程序实现 186

4.4 多项式及其计算 188

4.4.1 多项式及其表示 188

4.4.2 多项式的运算 190

4.4.3 FFT 191

4.4.4 程序实现 199

4.5 应用 204

4.5.1 多项式的泰勒展开式 204

4.5.2 完善序列 208

4.5.3 函数的有理式逼近 211

第5章 计算几何 218

5.1 线段的性质 218

5.1.1 叉积及其应用 219

5.1.2 向量的极角 222

5.1.3 程序实现 223

5.2 判断是否存在线段相交 226

5.2.1 算法描述与分析 227

5.2.2 程序实现 230

5.3 求凸壳 234

5.3.1 Graham扫描 235

5.3.2 程序实现 239

5.4 求最邻近点对 242

5.4.1 算法描述与分析 242

5.4.2 程序实现 245

5.5 应用 248

5.5.1 光导管 248

5.5.2 最小边界矩形 255

5.5.3 德克萨斯一日游 260

第6章 数论算法 264

6.1 整数的表示 264

6.1.1 整数的表示 264

6.1.2 整数的算术运算 264

6.1.3 程序实现 269

6.1.4 应用 275

6.2 初等数论的概念 277

6.3 最大公约数 283

6.3.1 Euclid算法 284

6.3.2 EUCLID算法的运行时间 284

6.3.3 Euclid算法的迭代版本 286

6.3.4 程序实现 287

6.3.5 应用 289

6.4 模运算 294

6.4.1 模加法和乘法 295

6.4.2 解模线性方程 296

6.4.3 元素的幂 299

6.4.4 应用 303

6.5 素数检测 305

6.5.1 伪素数检测 305

6.5.2 Miller-Rabin的随机素数检测 308

6.5.3 Miller-Rabin素数检测的错误率 310

6.5.4 程序实现 310

6.6 整数分解 313

6.6.1 Pollard的ρ探索法 313

6.6.2 程序实现 317

6.6.3 应用 320

第7章 回溯策略 323

7.1 组合问题 323

7.1.1 组合问题的例子 323

7.1.2 组合问题的形式化描述 325

7.2 组合问题的回溯算法 326

7.2.1 解空间的树状结构 326

7.2.2 解决组合问题的回溯算法 328

7.2.3 回溯算法的框架 333

7.3 子集树和排列树 339

7.3.1 子集树问题 339

7.3.2 排列树问题 343

7.3.3 应用 349

7.4 用回溯算法解决组合优化问题 360

7.4.1 组合优化问题 360

7.4.2 用回溯策略解决组合优化问题 362

7.4.3 应用 365

第8章 动态规划策略 375

8.1 组装线调度问题 376

8.1.1 问题描述 376

8.1.2 算法设计与分析 378

8.1.3 应用——牛牛玩牌 381

8.2 最长公共子序列 386

8.2.1 问题描述 386

8.2.2 算法设计与分析 386

8.2.3 程序实现 389

8.2.4 应用 390

8.3 0-1背包问题 398

8.3.1 问题描述 398

8.3.2 算法设计与分析 398

8.3.3 程序实现 401

8.3.4 应用 402

8.4 带权有向图中任意两点间的最短路径 409

8.4.1 问题描述 409

8.4.2 算法设计与分析 410

8.4.3 程序实现 413

8.4.4 应用——牛牛聚会 415

第9章 贪婪策略 419

9.1 活动选择问题 419

9.1.1 算法描述与分析 419

9.1.2 程序实现 423

9.1.3 贪婪算法与动态规划 424

9.1.4 应用——海岸雷达 425

9.2 Huffman编码 428

9.2.1 算法描述与分析 428

9.2.2 应用——R叉Huffman树 433

9.2.3 程序实现 437

9.3 最小生成树 443

9.3.1 算法描述与分析 443

9.3.2 程序实现 446

9.3.3 应用——北方通信网 448

9.4 单源最短路径问题 453

9.4.1 算法描述与分析 453

9.4.2 程序实现 456

9.4.3 应用——西气东送 458

第10章 图的搜索算法 465

10.1 深度优先搜索 466

10.1.1 算法描述与分析 466

10.1.2 程序实现 469

10.1.3 有向无圈图的拓扑排序 472

10.1.4 应用——全排序 478

10.2 有向图的强连通分支 482

10.2.1 算法描述与分析 482

10.2.2 程序实现 486

10.2.3 应用——亲情号 489

10.3 无向图的双连通分支 494

10.3.1 算法描述与分析 494

10.3.2 程序实现 497

10.3.3 应用——雌雄大盗 498

10.4 广度优先搜索 504

10.4.1 算法描述与分析 504

10.4.2 程序实现 507

10.4.3 应用——攻城掠地 508

10.5 流网络与最大流问题 512

10.5.1 算法描述与分析 512

10.5.2 程序实现 521

10.5.3 应用 523

第11章 文本搜索 528

11.1 固定模式的串匹配 528

11.1.1 强力算法 528

11.1.2 KMP算法 530

11.1.3 程序实现 535

11.1.4 应用 535

11.2 最长回文子串问题 541

11.2.1 强力算法 542

11.2.2 Manacher算法 543

11.2.3 程序实现 547

11.2.4 应用 549

11.3 近似匹配 550

11.3.1 最小编辑距离 550

11.3.2 最佳近似匹配 552

11.3.3 程序实现 555

11.3.4 应用 556

第12章 代码实验 560

12.1 头文件清单 560

12.1.1 基本应用类函数 560

12.1.2 数据结构类 563

12.1.3 代数记算类函数 566

12.1.4 计算几何类函数 568

12.1.5 数论计算类函数 569

12.1.6 回溯搜索类函数 571

12.1.7 动态规划类函数 572

12.1.8 贪婪策略类函数 572

12.1.9 图的搜索类函数 573

12.1.10 文本搜索类函数 574

12.2 实验平台的搭建 574

12.2.1 集成开发环境的安装 574

12.2.2 实验项目的建立 575

12.3 应用问题程序的运行实例 576

12.3.1 加载程序文件 576

12.3.2 调试程序 578

12.3.3 各应用问题加载文件清单 579

12.4 函数库的扩展 587

12.4.1 向已有的源文件中添加新函数 587

12.4.2 创建新的源文件 588

参考文献 589

查看更多关于从算法到程序的内容