常用算法深入学习实录 [平装] 7121213230

对于任何一门编程语言来说，算法都是程序的“灵魂”。正是因为算法如此重要，所以笔者精心编写了本书，希望通过书中的内容引领广大读者一起探讨学习算法的奥秘，带领广大读者真正步入程序开发的高级世界。 本书共分15章，循序渐进、由浅入深地详细讲解算法的核心内容，并通过具体实例的实现过程演练各个知识点的具体用法。本书首先详细讲解算法的基础知识，剖析了将算法称为“程序灵魂”的原因。然后详细讲解算法技术的核心内容，主要包括八大算法思想、数据结构、树、图、查找、内部排序、外部排序和文件等知识点的具体用法。接下来通过具体实例详细讲解各种算法经典问题的解决方案，主要包括解决经典的数据结构问题、解决数学问题、解决趣味问题、解决图像问题和解决奥赛问题的具体方案等。另外，书中还讲解了算法技术在现实编程项目中的作用和具体用法。《常用算法深入学习实录》编辑推荐：对于任何一门编程语言来说，算法都是程序的“灵魂”。正是因为算法如此重要，所以笔者精心编写了《常用算法深入学习实录》，希望通过书中的内容引领广大读者一起探讨学习算法的奥秘，带领广大读者真正步入程序开发的高级 世界。《常用算法深入学习实录》不但适合C语言的初学者学习，也适合有一定程序开发基础的读者阅读。对于有一定C／C++开发经验的读者来说，《常用算法深入学习实录》具有很高的参考价值。 第1章 都说算法是程序的“灵魂” 1.1 开始学习算法 1.1.1 算法的特征和发展由来 1.1.2 何为算法 1.2 计算机中的算法 1.2.1 认识计算机中的算法 1.2.2 为什么是程序的“灵魂” 1.3 表示算法的方法 1.3.1 用流程图来表示算法 1.3.2 用N—S流程图来表示算法 1.3.3 用计算机语言表示算法 1.4 学好算法的秘诀 第2章 分析妙趣横生的算法思想 2.1 八大算法思想 2.2 比较“笨”的枚举算法思想 2.2.1 枚举算法基础 2.2.2 实践演练 2.3 聪明一点的递推算法思想 2.3.1 递推算法基础 2.3.2 实践演练 2.4 充分利用自己的递归算法思想 2.4.1 递归算法基础 2.4.2 实践演练 2.5 各个击破的分治算法思想 2.5.1 分治算法基础 2.5.2 实践演练 2.6 贪心算法思想并不贪婪 2.6.1 贪心算法基础 2.6.2 实践演练 2.7 试探法算法思想是一种委婉的做法 2.7.1 试探法算法基础 2.7.2 实践演练 2.8 迭代算法 2.8.1 迭代算法基础 2.8.2 实践演练 2.9 模拟算法思想 2.9.1 模拟算法的思路 2.9.2 实践演练 第3章 走在算法的路上之——分析简单的 数据结构 3.1 学习编程的注意事项 3.2 什么是线性表 3.2.1 线性表的特性 3.2.2 顺序表操作 3.2.3 链表操作 3.3 守规矩的先进先出的队列 3.3.1 队列基础 3.3.2 链队列和循环队列 3.3.3 队列的基本操作 3.3.4 队列的链式存储 3.4 后进先出的栈 3.4.1 什么是栈 3.4.2 栈的基本分类 3.4.3 实践演练 第4章 走在算法的路上之——树 4.1 树引发的关系 4.1.1 树的概念 4.1.2 何谓二叉树 4.1.3 二叉树存储 4.1.4 操作二叉树 4.1.5 遍历二叉树 4.1.6 测试二叉树 4.1.7 线索二叉树 4.1.8 线索二叉树的表示 4.1.9 实践演练线索二叉树的操作 4.2 霍夫曼树 4.2.1 霍夫曼树基础 4.2.2 实践演练 第5章 走在算法的路上之——图 5.1 从哥尼斯堡七桥问题说起 5.2 几个相关概念 5.3 存储结构 5.3.1 表示顶点之间相邻关系的邻接矩阵 5.3.2 邻接表 5.3.3 合作的产物——十字链表 5.3.4 实践演练 5.4 遍历图 5.4.1 深度优先搜索 5.4.2 广度优先搜索 5.4.3 遍历算法的那点事 5.4.4 测试图的遍历实例 5.5 图的连通性 5.5.1 无向图的连通分量 5.5.2 最小生成树 5.5.3 关键路径 5.6 寻求最短的路径 5.6.1 求某一顶点到其他各顶点的最短路径 5.6.2 任意一对顶点间的最短路径 第6章 体验查找算法带来的魅力 6.1 几个相关概念 6.2 基于线性表的查找法 6.2.1 顺序查找法 6.2.2 折半查找法 6.2.3 分块查找法 6.3 基于树的查找 6.3.1 二叉排序树 6.3.2 平衡二叉排序树 6.4 哈希法 6.4.1 哈希法基础 6.4.2 处理冲突 6.4.3 哈希表的查找过程 6.5 索引查找 6.5.1 索引查找的过程 6.5.2 实践演练 第7章 内部排序 7.1 排序基础 7.1.1 排序的目的和过程 7.1.2 内部排序与外部排序 7.1.3 稳定排序与不稳定排序 7.2 霸道的插入排序 7.2.1 直接插入排序 7.2.2 折半插入排序 7.2.3 表插入排序 7.2.4 希尔排序 7.3 交换类排序法 7.3.1 冒泡排序（相邻比序法） 7.3.2 快速排序 7.4 选择类排序法 7.4.1 直接选择排序 7.4.2 树形选择排序 7.4.3 堆排序 7.4.4 实践演练 7.5 归并排序 7.5.1 归并排序思想 7.5.2 二路归并算法的思路 7.5.3 实现归并排序 7.5.4 实践演练 7.6 基数排序 7.6.1 多关键字排序 7.6.2 链式基数排序 第8章 外部排序和文件 8.1 外部信息方便了我们的生活 8.1.1 磁带存储器 8.1.2 磁盘存储器 8.2 外部排序的基本方法 8.2.1 磁盘排序 8.2.2 磁带排序 8.3 什么是文件 8.4 文件的组织方式 8.4.1 顺序文件 8.4.2 索引文件 8.4.3 ISAM文件 8.4.4 VSAM文件 8.4.5 散列文件 8.4.6 多关键字文件 第9章 从应聘开始谈算法 9.1 面试 9.1.1 面试前的准备 9.1.2 常见的面试错误 9.2 常见的算法笔试题 第10章 经典的数据结构问题 10.1 约瑟夫环 10.2 大整数运算 10.2.1 数组实现大整数运算 10.2.2 使用链表实现大整数运算 10.3 计算机进制转换 10.4 将中序表达式转换为后序表达式 第11章 解决数学问题 11.1 最大公约数和最小公倍数 11.2 哥德巴赫猜想 11.3 完全数 11.4 亲密数 11.5 自守数 11.6 方程求解 11.6.1 高斯消元法解方程组 11.6.2 用二分法解非线性方程 11.6.3 用牛顿迭代法解非线性方程 11.7 矩阵运算 11.8 一元多项式运算 11.8.1 一元多项式的加法运算 11.8.2 一元多项式的减法运算 第12章 解决趣味问题 12.1 歌星大奖赛 12.2 借书方案 12.3 打鱼还是晒网 12.4 捕鱼和分鱼 12.5 出售金鱼 12.6 平分七筐鱼 12.7 绳子的长度和井深 12.8 鸡兔同笼 12.9 汉诺塔 12.9.1 递归法 12.9.2 非递归法 12.10 马踏棋盘 12.10.1 使用循环查找法 12.10.2 使用递归法 12.10.3 使用栈方法 12.11 三色球问题 12.12 新郎和新娘问题 12.13 计算年龄几何 第13章 解决图像问题 13.1 八皇后问题 13.1.1 使用递归法 13.1.2 使用循环法 13.2 生命游戏 13.3 黑白棋问题 13.4 骑士迷宫问题 13.5 迷宫中的所有路径 第14章 算法的经典问题 14.1 存钱利息最大化 14.2 背包问题 14.2.1 使用动态规划法 14.2.2 使用递归法 14.3 农夫过河 14.4 三色旗 14.5 取石子 14.6 停车场管理 14.7 约瑟夫生者死者游戏 第15章 解决奥赛问题 15.1 孪生素数问题 15.2 百钱买百鸡问题 15.3 马克思手稿中的数学题 15.4 正整数分解为质因数 15.5 水仙花数 15.6 素数 15.6.1 求1000以内的所有素数 15.6.2 求1000以内的回文素数 15.6.3 求1000以内的平方回文数 15.7 阶乘 15.7.1 使用递归法 15.7.2 实现大数的阶乘 15.8 青蛙过河 15.9 过河卒 15.10 素数组合 15.11 校验码问题 15.12 老师排座位 15.13 模拟立体图 15.14 采药问题 15.15 等价表达式问题 15.16 购买年货问题 可以将算法理解为由基本运算及规定的运算顺序所构成的完整解题步骤；或者看成按照要求设计好的有限的确切计算序列，并且这样的步骤和序列可以解决一类问题。对于任何一门编程语言来说，算法都是“程序”的灵魂。正是因为算法如此重要，所以笔者精心编写了本书，希望通过书中的内容引领广大读者一起探讨学习算法的奥秘，带领广大读者真正步入程序开发的高级世界。这是一本讲解C语言算法核心内容和具体用法的书，可作为C语言初学者的入门教程，同时也可为专业程序开发人士提供一些参考。本书以“讲清语法、学以致用”为指导思想，不仅仅将笔墨局限于语法讲解上，而且还通过一个个鲜活、典型的小实例来达到学以致用的目的。 算法还重要吗 我们先不要给算法是否还重要轻易地下一个结论，现在先来看看一种现象：哪种语言是开发者们可以高高兴兴地用来编程的？在当前的市面中，基本上每个月都会有一些对语言使用程度做的排名。其实，编程语言又能体现出算法的相关价值。也许你掌握了好几种语言，但随着工作时间的增加和对技术的深入研究，你会发现：不是具体的技术而是算法这些基本的东西成为技术深入的“软肋”，特别是在紧要关口，这个“软肋”往往就会更疼。 到目前为止，笔者认为自己目前工作中创造性东西比以前少了很多。很多算法已经被包装到了语言和工具中, 作为一个开发者，也就不像以前那样费力地去学习了。而往往有些算法只适用于本语言或工具，而且只能解决某些问题，移植到别的情况下则无法使用。笔者也是在开始学习C语言后才感到算法适用范围有所不同。而最为别扭的是，你发现以前在用ASP.NET和Visual Studio开发工具中对于有些问题已经界定好了思路。人都是懒惰的，既然有现成的东西可用，为何要费力去创新？这也就导致了长期使用单一编程环境的开发者视野上比较狭隘。开发者很难有属于自己的思维方式，这就是有些人说自己做到一定程度后成了熟练“代码工人”的原因。 Ruby之父松本行弘就曾表示，注重的是算法而不是工具。如果没有自己的思维方式和编程逻辑，很容易对某种具体的技术或者工具产生依赖性，而这些编程工具和技术往往是国外开发的。假设有一天我们没有这些现成的工具和技术该怎么办？岂不是一穷二白了吗？但是如果有了稳固的算法，思维编程世界里的东西都不可怕。 算法是一种本质的回归 现实世界的变化真是快，仿佛前天刚刚出了Java，而昨天又出了一个C#，明天和后天还不知道要出一个什么XXX￥￥语言和新技术，于是广大程序员们就成了那赶潮大军中的一员。越往后走就会发现：越深入，步伐走得越慢，需要了解的技术就越多，做的东西越深。造成越来越力不从心的原因是“内功”不到位。C、C#、Java只是用来练习“武功”的招式，“内功”则是这些花哨武功招式后的本质。招式可以有很多种，但是如果没有“内功”，则招式变换再多也只是表面文章罢了，这样注定成不了一个名副其实的“武林高手”。 本书的内容 本书共分15章，循序渐进、由浅入深地详细讲解算法的核心内容，并通过具体实例的实现过程演练各个知识点的具体用法。本书首先详细讲解算法的基础知识，剖析了将算法称为“程序灵魂”的原因。然后详细讲解算法技术的核心内容，主要包括八大算法思想、数据结构、树、图、查找、内部排序、外部排序和文件等知识点的具体用法。接下来通过具体实例详细讲解各种算法经典问题的解决方案，主要包括解决经典的数据结构问题、解决数学问题、解决趣味问题、解决图像问题和解决奥赛问题的具体方案等。全书采用故事性与趣味性相结合的讲解方式，还穿插了学习技巧和职场生存法则，讲解了程序员所必须掌握的基本素养；并且紧跟时代潮流，讲解了算法技术在现实编程项目中的作用和具体用法。 本书特色 本书内容相当丰富，实例内容覆盖全面。我们的目标是通过一本图书，提供多本图书的价值，读者可以根据自己的需要有选择地阅读。在内容的编写上，本书具有以下特色。 （1）结构合理 从读者的实际需要出发，科学安排知识结构，内容由浅入深、叙述清楚，具有很强的知识性和实用性，几乎涵盖了C语言算法所有的知识点。 （2）易学易懂 本书条理清晰、语言简洁，可帮助读者快速掌握每个知识点；每个部分既相互连贯又自成体系，使读者既可以按照本书编排的章节顺序进行学习，也可以根据自己的需求对某一章节进行有针对性的学习。 （3）实用性强 本书彻底摒弃枯燥的理论和简单的操作，注重实用性和可操作性，详细讲解了各个部分的源码知识，使读者在掌握相关的操作技能的同时，还能学习到相应的基础知识。 （4）案例精讲，深入剖析 本书有许多经典示例，使读者不但对书中的理论知识进行了系统的复习，而且能够从实战中轻松掌握各个知识点的综合运用技巧，为读者将来更深层次的学习打下坚实的基础。 （5）附带教学资源丰富 本书附带的光盘中包含丰富的教学资源，既有长时间的实例讲解视频，也有实用的知识点讲解视频，还有附赠的综合实例。通过这些附属资源，使读者的学习过程更加便捷。 ■ daima：保存了本书中所有实例的完整源码。 ■ PPT：为读者和教研人员设计了精美的PPT文件，供学习和教学使用。 ■ 实例讲解视频：保存了本书中所有实例的讲解视频，讲解详细，便于读者理解、掌握。 ■ 知识点讲解视频：保存了本书中各知识点的讲解视频，讲解细致并深入，便于读者课余时间学习并掌握。 （6）提供了完善的售后技术支持 为了给读者营造良好的学习环境，本书的策划团队提供了在线论坛www.topchuban.com，为读者提供服务。读者可以登录此网站，与本书作者探讨学习中遇到的问题。 读者对象 ■ 初学C语言的自学者 ■ 大中专院校计算机及相关专业学生 ■ 从事软件开发的程序员 ■ 编程爱好者 ■ 有一定C基础的开发者或学生 ■ 相关培训机构的老师和学员 致谢 参与本书编写工作的还有管西京、李冬艳、代林峰、黄河、曹臻、白桦、伍杰、刘英田、刘继虎、王玉芹、程星、朱万林、杨阳、徐亮等。本团队在本书的编写过程中，得到了电子工业出版社工作人员的大力支持，正是各位编辑的求实、耐心和效率才使本书得以快速出版。另外也十分感谢我的家人，在我写作的时候给予了我巨大的支持。另外，鉴于本团队水平有限，纰漏和不尽如人意之处在所难免，恳请读者提出意见或建议，以便修订并使之更臻完善。 编者 2013年8月 版权页： 插图：