算法:C语言实现(第1～4部分)基础知识、数据结构、排序及搜索(原书第3版)

    书籍
    计算机书籍
本书细腻讲解计算机算法的C语言实现。全书分为四部分，共16章。包括基本算法分析原理，基本数据结构、抽象数据结构、递归和树等数据结构知识，选择排序、插入排序、冒泡排序、希尔排序、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序方法，并比较了各种排序方法的性能特征，在进一步讲解符号表、树等抽象数据类型的基础上，重点讨论散列方法、基数搜索以及外部搜索方法。书中提供了用C语言描述的完整算法源程序，并且配有丰富的插图和练习，还包含大量简洁的实现将理论和实践成功地相结合，这些实现均可用在真实应用上。.

本书内容丰富，具有很强的实用价值，适合作为高等院校计算机及相关专业本科生算法课程的教材，也是广大研究人员的极佳参考读物。

本书是Sedgewick彻底修订和重写的C算法系列的第一本。全书分为四部分，共16章。第一部分“基础知识”(第1～2章)介绍基本算法分析原理。第二部分“数据结构”(第3～5章)讲解算法分析中必须掌握的数据结构知识，主要包括基本数据结构、抽象数据结构、递归和树。第三部分“排序”(第6～11章)按章节顺序分别讨论基本排序方法(如选择排序、插入排序、冒泡排序、希尔排序等)、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序方法，并比较了各种排序方法的性能特征。第四部分“搜索”(第12～16章) 在进一步讲解符号表、树等抽象数据类型的基础上，重点讨论散列方法、基数搜索以及外部搜索方法。..

书中提供了用C语言描述的完整算法源程序，并且配有丰富的插图和练习。作者用简洁的实现将理论和实践成功地结合了起来，这些实现均可在真实应用上测试，使得本书自问世以来备受程序员的欢迎。

本书可作为高等院校计算机相关专业算法与数据结构课程的教材和补充读物，也可供自学之用。

本书作者的网站http://www.cs.princeton.edu/～rs/为程序员提供了本书的源代码和勘误表。...

塞奇威克（Robert Sedgewick），拥有斯坦福大学博士学位（导师为donald
E.Knuth），普林斯顿大学计算机科学系教授，Adobe Systems公司董事，曾是Xerox
PARC的研究人员，还曾就职于美国国防防御分析研究所以及INRIA。除本书外，他还与Philippe
Flajolet合著了《算法分析导论》

出版者的话.
译者序
前言
第一部分 基础知识
第1章 引言 1
1.1　算法 1
1.2　典型问题—连通性 2
1.3　合并－查找算法 5
1.4　展望 12
1.5　主题概述 13
第2章　算法分析的原理 15
2.1　实现和经验分析 15
2.2　算法分析 17
2.3　函数的增长 19
2.4　大O符号 23
2.5　基本递归方程 27
2.6　算法分析示例 29
2.7　保证、预测及局限性 33
第二部分 数据结构
第3章　基本数据结构 37

　　本书是算法方面的优秀著作之一。它系统地阐述了算法的特征以及它们可能应用的场合，讨论了算法分析与理论计算机科学的关系，并通过实验数据和分析结果表明选择何种算法来解决实际问题。书中包含了基本概念、数据结构、排序算法和搜索算法。.
　　这本书不仅适合于程序员和计算机科学专业的学生，而且也适合于那些想利用计算机并想使它运行更快或是想要解决更大问题的人们。书中的算法代表了过去50年来所研究的知识主体。对于大量应用问题，这些知识主体已经成为有效使用计算机不可缺少的部分。从物理学中的N-体模拟问题到分子生物学中的序列分析问题，在此所描述的基本方法在科学研究中已日显重要。另外，从数据库系统到Internet搜索引擎，这些方法已经成为现代软件系统的重要组成部分。随着计算机应用的覆盖面越来越广，基本算法的影响也日益显著。
　　本书主要内容及特点如下：
　　扩展介绍了数组、链表、串、树和其他基本数据结构。
　　为排序、选择、优先队列ADT实现和符号表ADT（查找）实现提供了多达100多个算法。
　　介绍了多路基数排序、随机BST、伸展树、跳跃表、多路trie等新的数据结构。..
　　为算法提供了很多可视化的信息，还有大量实验研究和基本分析研究，从而为选择算法解决实际问题提供了依据。
　　增加了1000多个新练习，从而有助于深入了解算法的特征。
　　本书以大量图例说明算法的工作过程，使得算法更加易于理解和掌握。
　　适合作为高等院校算法设计课程的教材，同时可作为从事软件开发和工程设计的专业人员的参考书。
　　由于时间较紧及译者水平有限，译文难免有错误及不妥之处，恳请读者批评指正。...
　　译者
　　于西安电子科技大学计算机学院
　　2009年4月
　　

　　写本书的目的是为了对当今使用最为重要的计算机算法做一综述，并为需要学习这方面知识的越来越多的读者提供基础的技术。本书可以在学生掌握了所需的基本程序设计技巧，熟悉了计算机系统，但还未学过计算机科学或计算机应用高级领域的专业课程的时候，用作计算机科学的第二、第三或第四门课程的教科书。此外，由于本书包含了大量有用算法的实现，以及关于这些算法的性能特征的详细信息，因而它还可用于自学，或者作为从事计算机系统或应用程序开发人员的参考手册。宽广的视角使得本书成为计算机算法领域最合适的入门读物。.
　　对于新的一版，我不仅完全重写了它的内容，而且还添加了一千多个练习、一百多幅图表和数十个新程序。我还给所有图表和程序添加了详细的注释。新的素材不仅涵盖了新的主题，而且还包含对经典算法的更完整解释。抽象数据类型是这本书的重点，这使得程序应用更广泛，并且与现代面向对象的程序设计环境更紧密。读过本书旧版本的人一定会发现，新版本包含了更为丰富的新信息，所有读者将发现大量的教学资料为掌握基本概念提供了有效途径。
　　由于新的素材数量过多，所以我们把新版本分为两卷（每一卷的容量都大约为旧版本的大小），本书是第一卷。这卷书中包含了基本概念、数据结构、排序算法和搜索算法；第二卷涵盖的高级算法及应用是以第一卷的基本抽象概念和方法为基础的。这个新版中的关于基本原理和数据结构的所有素材几乎都是新的。
　　这本书不仅适合于程序员和计算机科学专业的学生，而且也适合于想利用计算机并想使它运行更快或是想要解决更大问题的人们。这本书中的算法代表了过去50年来所研究的知识主体。对于大量应用问题，这些知识主体已经成为有效使用计算机的不可缺少的部分。从物理学中的N-体模拟问题到分子生物学中的序列分析问题，在此所描述的基本方法在科学研究中已日显重要。另外，对于从数据库系统到Internet搜索引擎，这些方法已经成为现代软件系统的重要组成部分。随着计算机应用的覆盖面越来越广，基本算法的影响也日益显著。本书的目标是要提供一种资源，使广大学生以及专业人士可以了解并有效利用这些算法解决计算机应用中出现的问题。
　　本书范围
　　本书共有16章，分为四大部分：基础、数据结构、排序和搜索。这里的说明是想使读者对尽可能多的基本算法有一个了解。本书描述的从二项队列到帕氏线索这个范围内的独创性的方法，都与计算机科学核心的基本范型相关。第二卷由另外四部分组成，涵盖了字符串算法、几何算法、图算法和高级主题。写这些书的主要意图是把各个领域中应用的基本方法集合在一起，从而为用计算机求解问题提供最好的方法。
　　如果你已经学过计算机科学的一两门课程，如C、Java或C++这样的高级程序设计语言课程，或者可能还有讲授程序设计系统的基本概念的课程，或者具有同等的程序设计经验，那么一定会非常欣赏本书提供的资料。因此，本书是为那些熟悉现代程序设计语言和现代计算机系统的基本特性的人而编写的。书中给出的参考文献会有助于弥补背景知识的不足。
　　由于用来支持分析结果的大部分数学知识都包含在本书中（或者做出标记不在本书之中），因而尽管具有完备的数学知识肯定会有帮助，但专门对数学知识的准备不是必要的。
　　教学中的用法
　　在教学中如何使用本书内容具有很大的灵活性，这取决于教师的偏好以及学生所做的准备。这里所描述的算法多年以来已经得到广泛应用，而且无论对于实际的程序员还是计算机科学专业的学生，这些算法都代表了基本的知识主体。书中涵盖了足够的基本内容可用作数据结构课程的学习，也有足够详细的高级主题用于算法课程的学习。有些教师可能希望强调与实现和实践有关的内容，而另外一些教师则可能把重点放在分析和理论概念上。
　　教学中使用的电子文档、程序设计示例作业、为学生提供的交互式练习以及其他课程有关的资料都可在本书的主页上找到。
　　关于数据结构和算法的基础课程可以把重点放在第二部分的基本数据结构及其他们在第三、四部分实现中的应用。关于算法设计与分析的课程可以把重点放在第一部分和第五部分中的基础内容，然后在第三部分和第四部分研究算法达到良好渐近性能的方法。关于软件工程的课程可能会省略数学和高级算法的内容，并把重点放在如何把给出的算法实现集成到大的程序或系统中。关于算法的课程则可能进行综述并引入所有这些领域的概念。
　　本书的早期版本在近年来为世界各地的学院或大学用作计算机科学的第二或第三门课程的教材或其他课程的补充阅读材料。在普林斯顿大学，我们的经验表明这本书内容覆盖面广，为主修课程提供计算机科学的导引，并可在后续的算法分析、系统程序设计以及理论计算机科学的课程中对它进行扩充，同时为其他学科的学生提供一整套的技术，使他们能很快学以致用。
　　这一版中的大多数练习是新添加的，分为几种类型。一类练习的目的是为了测试对课文中内容的理解，要求读者能够完成某个例子或应用课文中描述的概念。另一类练习则涉及实现算法和把算法整理到一起，或者进行实验研究从而对各种算法进行比较以及了解其性质。还有一类练习则是一些重要信息的知识库，其详细程度本身不适合放在正文中。阅读并思考这些练习，会使每个读者受益匪浅。
　　算法的实用性
　　若希望更有效地使用计算机，可以把这本书用作参考书，或用于自学。具有程序设计经验的人可以从本书中找到有关某个特殊主题的信息。对于更大范围的读者，尽管某些情况下，某一章中的算法使用了前一章中的方法，但你仍可以独立于本书的其他章节阅读本书的某个章节。
　　本书的定位是研究有可能实用的算法。本书提供了算法的详尽信息，读者可以放心地实现和调试算法，并使算法能够用于求解某个问题，或者为某个应用提供相关功能。书中包括了所讨论方法的完整实现，并在一系列一致的示例程序中给出了这些操作的描述。由于我们使用了实际代码，而不是伪代码，因而在实际中可以很快地使用这些程序。通过访问本书的主页可以得到程序的代码清单。
　　实际上，书中算法的实际应用会产生数百幅图表。正是这些图表提供的立体视觉直观地发现了许多算法。..
　　本书详细讨论了算法的特征以及它们可能应用的场合。尽管并不强调，但是书中论述了算法分析与理论计算机科学的联系。在适当的时候，书中都给出了经验性的数据和分析结果用以说明为什么选择使用某些算法。如果有趣，书中还会描述所讨论的实际算法与纯理论结果之间的关系。关于算法性能特征和实现的某种信息的综合、概括和讨论都会贯穿本书的始终。
　　编程语言

　　对于在数学分析方面不算熟练且需要留意理论算法的普通程序员来说，本书是一本可读性很强的优秀读本。他们应该会从中获益良多。.
　　——Steve Summit，《C Programming FAQs》的作者
　　Sedgewick有一种真正的天赋，可以用易于理解的方式来解释概念。书中采用了一些易懂的实战程序，其篇幅仅有一页左右，这更是锦上添花。而书中大量采用的图、程序、表格也会极大帮助读者的学习和理解，这使本书更显得与众不同。...
　　——William A. Ward，南亚拉巴马大学
　　

　　还有一个例子出现在某种程序设计环境中，连通性可用来断言两个变量名是否等价。问题是在经过这样的断言序列之后，能够确定两个给定的名字是否等价。这个应用激发了我们打算考虑的几个算法的研制。它直接将我们的问题与一种简单抽象关联起来，为使算法具有广泛应用而提供了一种方法。我们即将看到这一点。
　　像上一段描述的变量名等价问题这样的应用程序要求我们把每个不同的变量名与一个整数关联起来。这种关联关系也隐含在前面描述的网络连接和电路连接的应用中。在第10章至第16章，我们将会以一种更高效的方法考虑提供这种连接关系的大量算法。因此，不失一般性，本章假设有N个对象，每个都与0一N一1之间的一个整数名对应。
　　我们正在寻求完成特定和良定义任务的程序，可能还想要解决其他许多相关的问题。在研制算法时我们面对的首要任务之一是确信我们已经以合理的方式指定了问题。我们要求算法的越多，它完成任务所需要的时间和空间越多。不可能量化这个关系，并且我们在发现一个问题难以求解或是求解代价昂贵，或是在好的情况下，发现算法可以比原始说明提供更多有用的信息时，我们常常修改这个问题的说明。
　　例如，我们的连通问题的说明只要求我们的程序知道任意给定对p—q是否是连通的，并不能够表明连接那个对的任何方式。添加这样一个说明的要求会使问题更加困难，会涉及其他的算法，我们将在第5章简略讨论，并在第7章详细讨论。
　　前面这段提到的说明要比原始说明要求更多的信息，我们也可以要求更少的信息。例如，我们可能只想回答这样的问题：“M个连接足以把Ⅳ个对象都连接起来吗？”这个问题表明，要研制一个高效的算法，常常需要我们对正在处理的抽象对象进行高级推理。在这种情况下，由图论基本结果可以得出所有Ⅳ个对象是连通的，当且仅当连通算法输出的对的个数恰好为N一1（见5．4节）。换句话说，连通算法永远不会输出多于N一1个对，这是因为一旦它输出N一1个对，则它从那个时刻遇见的任何对将会是连通的。因此，我们可以修改求解连通问题的程序，增加一个计数器就可以得到一个回答yes-no问题的程序，而不输出那些前面不连通的每个对，当计数器的值为N-1时，程序回答“yes”，否则回答“no”。这个问题只是我们希望回答关于连通性的许多问题中的一个例子。输入对的集合称为图（graph），输出对的集合称为图的生成树，它连接了所有对象。我们在第七部分考察图、生成树以及所有相关算法的性质。
　　……