从算法到程序

第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.1LUP分解法概述177

4.2.2LU分解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.3FFT191

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.1Graham扫描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.1Euclid算法284

6.3.2EUCLID算法的运行时间284

6.3.3Euclid算法的迭代版本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.2MillerRabin的随机素数检测308

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

6.5.4程序实现310

6.6整数分解313

6.6.1Pollard的ρ探索法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.30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.2Huffman编码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.2KMP算法530

11.1.3程序实现535

11.1.4应用535

11.2最长回文子串问题541

11.2.1强力算法542

11.2.2Manacher算法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第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

本书第1章讨论算法设计、分析的基本概念。第2章讨论算法设计中最常用的几个数据结构，包括链表、栈、队列、二叉搜索树、散列表等。第3章讨论了算法设计的两个基本策略：渐增策略与分支策略。第1～3章的内容，为读者阅读本书以后的内容奠定了基础。第4章讨论几个代数计算的基本问题及其算法，包括矩阵运算、解线性方程组、多项式运算等。第5章讨论几个关于计算几何的基本问题及其算法，包括线段的相交判断、平面点集的凸包计算、最邻近点对问题等。第6章讨论了关于整数运算的基本问题，包括大整数的表示与运算、最大公约数计算、模运算、素数判定及整数因数分解等。第4～6章的内容为读者深入学习解决各种复杂问题奠定了解决数学计算问题的基础。第7~9章分别用回溯策略、动态规划策略及贪婪策略研究、解决计算机应用面临的最普遍、最典型的组合优化问题。第10章讨论图的搜索算法及其应用，包括深度优先搜索、拓扑排序、有向图的强连通分支计算、关节点计算、广度优先搜索、网络最大流及二部图的最大匹配等问题。第11章讨论了几个文本搜索的有趣算法，包括著名的KMP模式匹配算法、线性时间计算字符串中最长回文子串的Manacher算法、用动态规划策略寻求字符串中指定模式的最佳近似匹配的算法。对所有的的经典算法及数据结构，书中给出C语言的实现函数，形成一个通用的函数库，并详尽地加以解析。伴随各种算法的设计、分析及程序实现，书中给出了丰富多彩的应用问题及其解决方案的讨论，并给出了完整的程序代码。所有程序代码都经过反复调试，第12章介绍这些代码的使用方法。所有代码都以网络资源的方式提供给读者，访问下载地址为www.tup.com.cn。本书无论是对初学算法及程序设计入门的大学生读者还是对已经在职场打拼多年的程序员并有提高自身理论修养及技术水平愿望的读者都有开卷有益的意义。

本书以数学计算为先导，组合优化为主线。
本书实现在算法理论指导下的编程实践。
本书含有48个应用问题编程实践，全面体验算法理论的力量。
本书PPT教案与完整源代码可到清华大学出版社官网下载。