从算法到程序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数据结构类 531

11.1.3代数记算类函数 534

11.1.4计算几何类函数 536

11.1.5数论计算类函数 537

11.1.6回溯搜索类函数 539

11.1.7动态规划类函数 540

11.1.8贪婪策略类函数 540

11.1.9图的搜索类函数 541

11.2实验平台的搭建 542

11.2.1集成开发环境的安装 542

11.2.2实验项目的建立 542

11.3应用问题程序的运行实例 544

11.3.1加载程序文件 544

11.3.2调试程序 545

11.3.3各应用问题加载文件清单 546

11.4函数库的扩展 554

11.4.1向已有的源文件中添加新函数 554

11.4.2创建新的源文件 555

参考文献 557