《算法精解：C语言描述》

书名：算法精解：C语言描述
作者：【美】Kyle Loudon
译者：肖翔　陈舸
设计：王多　唐洋
排版：济南阿古达
ISBN： 978-7-111-39426-6

书最大的特点是理论与实践相结合，这主要体现在以下几点上：

书中第一部分从讲述相关的C语言基础知识和算法分析方法入手，在随后的章节中采用软件工程中的良好准则，结合作者的实践经验将基于接口的C程序设计理念贯穿全书。使得本书中的数据结构和算法实现能够以接口的形式充分得到复用。
书中的代码实现主要以教学为目的，但也同样考虑到了实现效率的问题。对于实现方案的选择和取舍，都有详细的说明和解释。每章末尾的“问与答”将加深读者对相关章节的理解。
除了对数据结构和算法本身的介绍，书中所有的应用举例都来自于真实的应用。这绝不是一般的练习题，而是算法和数据结构在真实世界中的应用。包括操作系统中的页帧管理、页面置换算法、表达式处理等等。通过实际的例子向读者展示了数据结构和算法的威力，有助于培养我们抽象建模的能力，从而更有效的将学到的知识用于解决实际问题中。

总的来说，这是一本对“打基础”很有帮助的书。书中对常见的数据结构如链表、栈、队列、集合、哈希表、树、堆、图都做了详细的分析并给出了具体的实现。算法方面除了最为常见的排序和检索外，还有数值计算、数据压缩、数据加密、几何计算等方面的主题。

本书结构

本书分为3部分。第1部分由介绍性的内容组成，它们对于读者理解接下来的章节有很大帮助。第2部分介绍了计算机科学中最基本的几种数据结构。第3部分介绍用于解决常见问题的各种算法。接下来的内容将以更详尽的方式来描述和说明每一部分的主题，以及每个部分的各章的提要。

第1部分

第1部分包括第1～4章。第1章介绍数据结构和算法的概念，并给出使用数据结构和算法的原因。这一章也介绍一些与软件工程相关的思想和主题，这些思想会贯穿全书。第2章讨论一系列与指针相关的主题。指针在本书中大量出现，因此这一章可作为对指针的回顾和复习。第3章介绍递归，这是一种在许多数据结构和算法中都会用到的技术。第4章介绍算法的分析方法。这一章中的内容用来分析本书中介绍的算法。

第2部分

第2部分包括第5～11章。第5章介绍多种形式的链表，包括单链表、双向链表以及循环链表。第6章介绍栈和队列，它们分别按照后进先出以及先进先出的方式来存储和返回数据。第7章介绍集合以及用来描述集合这种数据结构的数学知识。第8章介绍链式和开地址哈希表，还包含如何选择一个好的哈希函数以及如何解决哈希碰撞的内容。第9章介绍二叉树和AVL树，也包含多种树的周游算法。第10章介绍堆和优先级队列，这种数据结构有助于快速确定集合中的最大或最小元素。第11章介绍图，以及在许多图算法中常用到的两种重要算法：广度优先查找和深度优先查找。

第3部分

第3部分包含第12～17章。第12章涵盖多种排序算法，包括插入排序、快速排序、归并排序、计数排序以及基数排序，这一章也介绍二分查找。第13章涵盖数值计算方法，包括多项式插值算法、最小二乘估计以及用来解方程的牛顿迭代法。第14章介绍关于数据压缩的算法，包括霍夫曼编码以及LZ77。第15章讨论用于数据加密的DES和RSA算法。第16章涵盖图算法，包括用于确定最小生成树的Prim算法、确定最短路径的Dijkstra算法，以及解决旅行商问题的算法。第17章介绍几何算法，包括检测两条线段是否相交、凸包计算以及计算球面上两点间的弧长。

本书主要特点

这里列出的一些特点使我相信本书能够成为一本涵盖数据结构和算法方面的独特技术类图书。

每一章的格式保持统一
每一章（不包括第1章中的介绍性内容）都遵循一致的格式。根据读者当前的需要，这种格式使得本书大部分内容都可以以教材或参考资料的形式来阅读。
明确的主题和应用
每一章（除了第1章外）都以一个概要性的介绍开始，接着是一系列明确的主题以及与它们相关的真实应用介绍。
对每个操作、算法和例子的分析
本书针对抽象数据类型的每个操作、第12～17章的每种算法以及每个示例都提供详细的分析。关于算法分析的技术在第4章中介绍。
真实示例，不只是简单的练习
书中所有的示例都来自真实的应用，不只是一般的练习题。这样的示例更令人兴奋，也能够从中学到更多的知识。
具体实现都采用正式的代码
所有的实现都用C语言编写而不是用伪代码来表示。这种方式的好处在于当实现许多数据结构和算法时，有很多细节问题是伪代码所不能解决的。
问与答引人深思
每一章的末尾（除了第1章外）都会有一系列的问题和对应的回答。这些问与答着重强调了这一章中的重要思想，而且还能使读者接触到一些附加的主题。
列出了相关的主题以进一步研究
每一章的最后一节（除了第1章外）都会列出一系列与本章主题相关的内容，以便读者进一步探讨。每一个相关主题都以一段简短的介绍来呈现。
大量的交叉引用和标注
交叉引用和标注将主题在一处提及，然后在别处介绍。因而能够方便地定位其他信息。
精心组织主题和相关应用
某一章中的数据结构和算法会采用其他章节介绍过的数据结构和算法来实现。因而，这可以作为如何利用其他数据结构和算法的例子。所有的相关依赖都通过交叉引用和标注的形式精心标记。
除了涵盖最重要的主题之外还有更多其他的内容
本书涵盖计算机科学领域中最基本的数据结构和算法。书中还介绍其他几个并不常出现在数据结构和算法类图书中的主题。其中包括数值计算方法、数据压缩、数据加密以及几何算法。

关于书中的代码

书中的所有实现都采用C语言编写。选择C语言是因为它仍然是当今使用最广泛的通用编程语言。C语言也是最好的编程语言之一，不仅用来探索数据结构和算法的细节，同时还能够使用在较高层次上。关于书中的代码，有些事情需要注意。

所有的代码以教学目的为优先
代码注重运行效率上的考虑，但所有代码的主要目的是以清晰的形式阐述相关的主题。
所有的代码都在4种平台上做过完整的测试
用于测试的平台包括：HP-UX 10.20、SunOs 5.6、Red HatLinux 5.1以及DOS/Windows NT/95/98。可以从附赠光盘的readme文件中获取更多的信息。
头文件中记录了所有的公共接口
每个实现都包含一个头文件以归档公有接口。书给出了代码头文件。但是，只包含函数原型的头文件并没有给出。（比如，示例12-1包含sort.h，但并没有给出头文件，因为它只包含各个排序函数的原型而已。）
静态函数当做私有函数来使用
静态函数拥有文件作用域，只在定义它的文件内有效，因此把静态函数作为私有函数使用。某个特定于数据结构或算法实现的函数都不属于公有接口的一部分。
命名规则适用于全书所有的代码
常量全部以大写字母来定义。数据类型和全局变量以大写字母开头。局部变量以小写字母开头。抽象数据类型的操作以类型名开头，采用小写字母形式，紧跟着是一条下划线，然后是操作名的小写形式。
所有的代码都包含大量注释
注释可以帮助开发者不用读太多代码就能够理解代码的逻辑。当需要在正文中联系代码和解释时这非常有用。
用typedef重命名的结构体名就是它本身
结构体的名称总是在typedef之后的别名上再加一条下划线。对于有自我引用行为的结构体（比如第5章中的链表），命名结构体自身是很有必要的。为了保持一致性，书所有的结构体都采用这种命名方式。
所有void函数都显式包含return语句
尽管这不是必需的，但这有助于快速定位函数的返回位置，而不必费力地去匹配的大括号。