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

算法：C语言实现（第1～4部分） 基础知识、数据结构、排序及搜索 （原书第3版）　
Algorithms in C Parts 1-4: Fundamentals, Data Structures, Sorting, Searching
Third Edition

(美)　Robert Sedgewick (普林斯顿大学)　著　 霍红卫 (西安电子科技大学)　 译

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

本书是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合著了《算法分析导论》一书。

写本书的目的是为了对当今使用最为重要的计算机算法做一综述，并为需要学习这方面知识的越来越多的读者提供基础的技术。本书可以在学生掌握了所需的基本程序设计技巧，熟悉了计算机系统，但还未学过计算机科学或计算机应用高级领域的专业课程的时候，用作计算机科学的第二、第三或第四门课程的教科书。此外，由于本书包含了大量有用算法的实现，以及关于这些算法的性能特征的详细信息，因而它还可用于自学，或者作为从事计算机系统或应用程序开发人员的参考手册。宽广的视角使得本书成为计算机算法领域最合适的入门读物。
对于新的一版，我不仅完全重写了它的内容，而且还添加了一千多个练习、一百多幅图表和数十个新程序。我还给所有图表和程序添加了详细的注释。新的素材不仅涵盖了新的主题，而且还包含对经典算法的更完整解释。抽象数据类型是这本书的重点，这使得程序应用更广泛，并且与现代面向对象的程序设计环境更紧密。读过本书旧版本的人一定会发现，新版本包含了更为丰富的新信息，所有读者将发现大量的教学资料为掌握基本概念提供了有效途径。
由于新的素材数量过多，所以我们把新版本分为两卷（每一卷的容量都大约为旧版本的大小），本书是第一卷。这卷书中包含了基本概念、数据结构、排序算法和搜索算法；第二卷涵盖的高级算法及应用是以第一卷的基本抽象概念和方法为基础的。这个新版中的关于基本原理和数据结构的所有素材几乎都是新的。
这本书不仅适合于程序员和计算机科学专业的学生，而且也适合于想利用计算机并想使它运行更快或是想要解决更大问题的人们。这本书中的算法代表了过去50年来所研究的知识主体。对于大量应用问题，这些知识主体已经成为有效使用计算机的不可缺少的部分。从物理学中的N-体模拟问题到分子生物学中的序列分析问题，在此所描述的基本方法在科学研究中已日显重要。另外，对于从数据库系统到Internet搜索引擎，这些方法已经成为现代软件系统的重要组成部分。随着计算机应用的覆盖面越来越广，基本算法的影响也日益显著。本书的目标是要提供一种资源，使广大学生以及专业人士可以了解并有效利用这些算法解决计算机应用中出现的问题。
本书范围
本书共有16章，分为四大部分：基础、数据结构、排序和搜索。这里的说明是想使读者对尽可能多的基本算法有一个了解。本书描述的从二项队列到帕氏线索这个范围内的独创性的方法，都与计算机科学核心的基本范型相关。第二卷由另外四部分组成，涵盖了字符串算法、几何算法、图算法和高级主题。写这些书的主要意图是把各个领域中应用的基本方法集合在一起，从而为用计算机求解问题提供最好的方法。
如果你已经学过计算机科学的一两门课程，如C、Java或C++这样的高级程序设计语言课程，或者可能还有讲授程序设计系统的基本概念的课程，或者具有同等的程序设计经验，那么一定会非常欣赏本书提供的资料。因此，本书是为那些熟悉现代程序设计语言和现代计算机系统的基本特性的人而编写的。书中给出的参考文献会有助于弥补背景知识的不足。
由于用来支持分析结果的大部分数学知识都包含在本书中（或者做出标记不在本书之中），因而尽管具有完备的数学知识肯定会有帮助，但专门对数学知识的准备不是必要的。
教学中的用法
在教学中如何使用本书内容具有很大的灵活性，这取决于教师的偏好以及学生所做的准备。这里所描述的算法多年以来已经得到广泛应用，而且无论对于实际的程序员还是计算机科学专业的学生，这些算法都代表了基本的知识主体。书中涵盖了足够的基本内容可用作数据结构课程的学习，也有足够详细的高级主题用于算法课程的学习。有些教师可能希望强调与实现和实践有关的内容，而另外一些教师则可能把重点放在分析和理论概念上。
教学中使用的电子文档、程序设计示例作业、为学生提供的交互式练习以及其他课程有关的资料都可在本书的主页上找到。
关于数据结构和算法的基础课程可以把重点放在第二部分的基本数据结构及其他们在第三、四部分实现中的应用。关于算法设计与分析的课程可以把重点放在第一部分和第五部分中的基础内容，然后在第三部分和第四部分研究算法达到良好渐近性能的方法。关于软件工程的课程可能会省略数学和高级算法的内容，并把重点放在如何把给出的算法实现集成到大的程序或系统中。关于算法的课程则可能进行综述并引入所有这些领域的概念。
本书的早期版本在近年来为世界各地的学院或大学用作计算机科学的第二或第三门课程的教材或其他课程的补充阅读材料。在普林斯顿大学，我们的经验表明这本书内容覆盖面广，为主修课程提供计算机科学的导引，并可在后续的算法分析、系统程序设计以及理论计算机科学的课程中对它进行扩充，同时为其他学科的学生提供一整套的技术，使他们能很快学以致用。
这一版中的大多数练习是新添加的，分为几种类型。一类练习的目的是为了测试对课文中内容的理解，要求读者能够完成某个例子或应用课文中描述的概念。另一类练习则涉及实现算法和把算法整理到一起，或者进行实验研究从而对各种算法进行比较以及了解其性质。还有一类练习则是一些重要信息的知识库，其详细程度本身不适合放在正文中。阅读并思考这些练习，会使每个读者受益匪浅。
算法的实用性
若希望更有效地使用计算机，可以把这本书用作参考书，或用于自学。具有程序设计经验的人可以从本书中找到有关某个特殊主题的信息。对于更大范围的读者，尽管某些情况下，某一章中的算法使用了前一章中的方法，但你仍可以独立于本书的其他章节阅读本书的某个章节。
本书的定位是研究有可能实用的算法。本书提供了算法的详尽信息，读者可以放心地实现和调试算法，并使算法能够用于求解某个问题，或者为某个应用提供相关功能。书中包括了所讨论方法的完整实现，并在一系列一致的示例程序中给出了这些操作的描述。由于我们使用了实际代码，而不是伪代码，因而在实际中可以很快地使用这些程序。通过访问本书的主页可以得到程序的代码清单。
实际上，书中算法的实际应用会产生数百幅图表。正是这些图表提供的立体视觉直观地发现了许多算法。
本书详细讨论了算法的特征以及它们可能应用的场合。尽管并不强调，但是书中论述了算法分析与理论计算机科学的联系。在适当的时候，书中都给出了经验性的数据和分析结果用以说明为什么选择使用某些算法。如果有趣，书中还会描述所讨论的实际算法与纯理论结果之间的关系。关于算法性能特征和实现的某种信息的综合、概括和讨论都会贯穿本书的始终。
编程语言
书中所有实现所用的程序设计语言均为C语言。任何特定语言都有优缺点。我们使用C语言是因为它是一种广泛使用的语言，并且能够为本书的实现提供所需的特征。由于没有多少结构是C语言所特有的，因而用C语言编写的程序可以很容易地变成用其他现代编程语言书写的程序。在适当的时候，我们会使用标准C语言中的术语，但本书并不打算成为C语言程序设计的参考手册。
在这一版中有很多新的程序，旧版本的很多程序也已更新，主要目的是使它们在用作抽象数据类型时更具有易读性。对程序所做的广泛的实验性比较研究贯穿在本书中。
本书以前的版本是用Pascal、C++和Modula-3来呈现基本程序的。在本书的主页上可得到这些代码。新程序的代码和用新语言，如Java书写的代码将在适当的时候添加进来。
本书的目标是以尽可能简单、直接的方式呈现算法。在尽可能的情况下利用一致的风格，使得相似的程序看起来相似。对于书中的许多算法，无论使用哪种语言，算法都具有相似性。例如，Quicksort是一种快速排序算法（取了一个著名的例子），无论它是用Algol60、Basic、Fortran、Smalltalk、Ada、Pascal、C、PostScript、Java表示的，还是其他无数程序设计语言和环境表示的，都证明它是一种有效的排序方法。
我们力争编写精致、简明和可移植的代码实现，但同时关注实现的效率，因而我们在开发的各个阶段就试图了解代码的性能特征。第一章包含这种方法的一个详细例子，用以说明如何用这种方法开发一个算法的高效C语言实现，并简略介绍了本书其余部分的内容。
致谢
对于本书早期的版本，很多人提供了有用的反馈信息。特别要提出的是普林斯顿大学和布朗大学的数百名学生们在过去数年的学习过程中一直承受着初稿的粗糙。特别要感谢Trina Avery和Tom Freeman对于第一版的出版所给予的帮助。还要感谢Janet Incerpi，是她的创造力和聪明才智使我们利用早期原始的数字排版硬件和软件制作出本书的第一版。感谢Marc Brown在算法可视化方面做的研究，他创建了本书中的诸多插图，而本书中的很多图表正来源于此。感谢Dava Hanson，对于我提出的关于C语言方面的所有问题，他总是乐于回答。我还要感谢众多读者，他们对各个版本提供了详尽的评论，这其中包括：Guy Almes、Jon Bentley、Marc Brown、Jay Gischer、Allan Heydon、Kennedy Lemke、Udi Manber、Dana Richards、Join Reif、M. Rosenfeld、Stephen Seidman、Michael Quinn和William Ward。
为了完成这一版本，我有幸与Addison-Wesley的Peter Gordon和Debbie Lafferty一起工作。他们耐心地指导这个项目的完成，使其经历了从一般性的修改到大幅度重写的过程。同样我还有幸与Addison-Wesley的许多专业人员一起工作。这个项目的性质使得本书带给他们非同寻常的挑战，对于他们的忍耐力我致以诚挚的感谢。
在写这本书的过程中，我得到了两位良师益友。在此我要特别向他们表示感谢。Steve Summit从技术的角度对各版本的初稿都做了仔细的检查，并向我提供了数千条详尽的意见，尤其是关于程序方面的建议。Steve很清楚我的目标是要提供精致、有效且实用的实现代码，他的意见不仅帮助我给出实现一致性的度量标准，而且还帮助我对其中一部分作了重大的改进。Lyn Dupre也对我的手稿提供了数千条的意见，这些建议对我来说是无价之宝，不仅帮助我改正和避免了许多语法错误，而且更重要的是，使我找到一种一致性的编写风格，由此才使我把如此繁多的技术资料整理在一起。能够有机会向Steve和Lyn学习，我万分感激。他们的投入对于本书的完成至关重要。
我在这里所写的内容大多受益于Don Knuth的授课和著作，他是我在斯坦福大学的导师。尽管Don对本书没有直接的影响，但在本书中仍然能够感受到他的存在，因为正是他为算法研究奠定了科学基础，才使得像本书这样的工作得以完成。我的朋友兼同事Philippe Flajolet，是使算法分析发展成为一个成熟领域的主力，对这本书具有同样的影响力。
非常感谢普林斯顿大学、布朗大学以及法国国立计算机与自动化研究所（Institute National de Recherce en Informatique et Automatique，INRIA）给予的支持，在这些地方，我完成了本书大部分的工作。还要感谢美国国防部防御分析研究所（Institute for Defense Analysis）以及施乐的帕洛阿尔托研究中心（Xeror Palo Alto Research Center），我在他们那里的访问期间完成了本书的一些工作。本书的某些部分离不开国家自然科学基金（National Science Foundation）和海军研究中心（Office of Naval Research）的慷慨支持。最后，我要感谢Bill Bowen、Aaron Lemonick和Neil Rudenstine，他们为普林斯顿大学建立了一个良好的学术环境，使我能够在这样良好的环境中，在承担众多其他事务的同时完成本书的准备。

Robert Sedgewick
Marly-le-Roi，法国，1983年2月
普林斯顿，新泽西州，1990年1月
詹姆斯镇，罗得岛，1997年8月
有关练习的注释
给练习分类是一件充满风险的事情，因为本书的读者具备的知识背景和经验参差不齐。虽然如此，指导仍然是适宜的，所以许多练习都加了一个记号，以帮助你判断如何动手解决它们。
测试你对内容理解程度的练习标以空心三角符号，如下所示：
7.1　按前面例子的风格，给出快速排序算法应用于文件内容为EASYQUESTION每一步的排序结果。
通常，这样的练习是与正文中的例子直接相关。它们并不特别难，但是做这些练习可能教会你一个事实或一个概念，它们可能是你在阅读正文时感到困惑不解的问题。
给正文中添加新的和需要思考信息的练习标以空心圆符号，如下所示：
○ 13.23　比较你从练习13.22所得结果和从下面过程所得结果：利用程序13.2和程序13.3对一棵N个节点的随机树执行删除最大关键字，并重新插入该关键字的操作，其中N = 10，100和1000。对于每个N，要求达到N2次的插入－删除对操作。
这样的练习鼓励你考虑与书中内容相关的重要概念，或者回答出现在你阅读正文时遇到的一个问题。即使你没有时间做这些练习，你也会发现阅读这些练习是非常有价值的。
具有挑战性的练习标以黑色圆点，如下所示：
8.45　假设归并排序将文件按随机方式进行划分，而不是恰好平分。使用这样的方法对包含N个元素的文件进行排序，平均需要使用多少次比较？
这种练习可能需要花费大量时间才能完成，这取决于你的经验。一般而言，最有效的方法是分几个时期来解决它们。
少数难度极大的练习标以两个黑色圆点，如下所示：
ゥ 15.28　证明由N个随机位串所构建的线索的高度约为2lgN。提示：考虑生日问题（见性质14.2）。
这种练习类似于研究文献上陈述的问题，但书中的内容可能为你试图（可能成功）解决它们做好了准备。
对于考察你的程序设计能力和数学能力的练习，则没有明确记号。这些要求程序设计能力或数学分析能力的练习是一种自我检查。我们鼓励所有的读者都通过实现算法以测试自己对算法的理解程度。对于程序员或者程序设计课程的学生来说，这样的练习很简单，而对于那些近来很少编程的人来说，则会有一定难度：
4.45　写一个客户程序从命令行的第一个参数中取一个整数N，然后打印出N个扑克牌局，方法是把N个项放到一个随机队列中（见练习4.4），然后打印出从队列中一次拣出五张牌的结果。
类似的情况，我们鼓励所有的读者努力探索有关算法性质的分析基础。对于一个科学工作者或者离散数学课程的学生来说，这样的练习很简单，而对于那些近来很少做数学分析的人来说，仍然会有一定的难度：
1.12　在一棵由加权快速合并算法在最坏情况下构造的2n个节点的树中，试计算从一个节点到树根节点的平均距离。
还有更多的练习需要你去阅读和掌握。我希望这里有足够的练习能够激励你积极地加深对自己感兴趣主题的理解，而不仅仅满足于简单阅读正文所得到的收获。

对于在数学分析方面不算熟练且需要留意理论算法的普通程序员来说，本书是一本可读性很强的优秀读本。他们应该会从中获益良多。
　　——Steve Summit，《C Programming FAQs》的作者
　　Sedgewick有一种真正的天赋，可以用易于理解的方式来解释概念。书中采用了一些易懂的实战程序，其篇幅仅有一页左右，这更是锦上添花。而书中大量采用的图、程序、表格也会极大帮助读者的学习和理解，这使本书更显得与众不同。
　　——William A. Ward，南亚拉巴马大学
　　本书是Sedgewick彻底修订和重写的C算法系列的第一本。全书分为四部分，共16章。第一部分“基础知识” (第1~2章) 介绍基本算法分析原理。第二部分“数据结构” (第3~5章) 讲解算法分析中必须掌握的数据结构知识，主要包括基本数据结构、抽象数据结构、递归和树。第三部分“排序” (第6~11章) 按章节顺序分别讨论基本排序方法 (如选择排序、插入排序、冒泡排序、希尔排序等) 、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊目的排序方法，并比较了各种排序方法的性能特征。第四部分“搜索” (第12~16章) 在进一步讲解符号表、树等抽象数据类型的基础上，重点讨论哈希方法、基数搜索以及外部搜索方法。
　　书中提供了用C语言描述的完整算法源程序，并且配有丰富的插图和练习。作者用简洁的实现将理论和实践成功地结合了起来，这些实现均可在真实应用上测试，使得本书自问世以来备受程序员的欢迎。
　　本书可作为高等院校计算机相关专业算法与数据结构课程的教材和补充读物，也可供自学之用。
　　本书作者的网http://www.cs.princeton.edu/~rs/为程序员提供了本书的源代码和勘误表。

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

霍红卫：霍红卫: 1963年8月出生，博士。现为西安电子科技大学计算机学院教授。主要研究方向：算法分析与设计、并行与分布式计算、遗传算法、生物信息学中的优化算法。著作有：《算法设计与分析》、《并行分类算法》和《Exercises & Solutions on Algorithms》。

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

译者
于西安电子科技大学计算机学院
2009年4月

出版者的话
译者序
前言

第一部分　 基础知识
第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
3.1　构建组件 37
3.2　数组 44
3.3　链表 49
3.4　链表的基本处理操作 54
3.5　链表的内存分配 60
3.6　字符串 63
3.7　复合数据结构 66
第4章　抽象数据类型 74
4.1　抽象对象和对象集 76
4.2　下推栈ADT 78
4.3　栈ADT客户示例 79
4.4　栈ADT的实现 84
4.5　创建一个新ADT 87
4.6　FIFO队列和广义队列 90
4.7　复制和索引项 95
4.8　一级ADT 99
4.9　基于应用的ADT示例 106
4.10　展望 110
第5章　递归与树 111
5.1　递归算法 111
5.2　分治法 116
5.3　动态规划 127
5.4　树 133
5.5　树的数学性质 138
5.6　树的遍历 140
5.7　递归二叉树算法 145
5.8　图的遍历 149
5.9　综述 155
第三部分　 排　　序
第6章　基本排序方法 157
6.1　游戏规则 158
6.2　选择排序 161
6.3　插入排序 162
6.4　冒泡排序 164
6.5　基本排序方法的性能特征 166
6.6　希尔排序 171
6.7　对其他类型的数据进行排序 177
6.8　索引和指针排序 180
6.9　链表排序 185
6.10　关键字索引统计 188
第7章　快速排序 191
7.1　基本算法 191
7.2　快速排序算法的性能特征 195
7.3　栈大小 198
7.4　小的子文件 201
7.5　三者取中划分 203
7.6　重复关键字 206
7.7　字符串和向量 209
7.8　选择 210
第8章　归并与归并排序 213
8.1　两路归并 213
8.2　抽象原位归并 215
8.3　自顶向下的归并排序 216
8.4　基本算法的改进 219
8.5　自底向上的归并排序 220
8.6　归并排序的性能特征 223
8.7　归并排序的链表实现 225
8.8　改进的递归过程 227
第9章　优先队列和堆排序 229
9.1　基本操作的实现 231
9.2　堆数据结构 233
9.3　基于堆的算法 235
9.4　堆排序 240
9.5　优先队列ADT 244
9.6　索引数据项的优先队列 247
9.7　二项队列 250
第10章　基数排序 258
10.1　位、字节和字 259
10.2　二进制快速排序 261
10.3　MSD基数排序 265
10.4　三路基数快速排序 271
10.5　LSD基数排序 274
10.6　基数排序的性能特征 278
10.7　亚线性时间排序 280
第11章　特殊用途的排序方法 284
11.1　Batcher奇偶归并排序 284
11.2　排序网 289
11.3　外部排序 295
11.4　排序－归并的实现 299
11.5　并行排序/归并 303
第四部分　 搜　　索
第12章　符号表和二叉搜索树 307
12.1　符号表抽象数据类型 308
12.2　关键字索引搜索 311
12.3　顺序搜索 313
12.4　二分搜索 318
12.5　二叉搜索树 321
12.6　BST的性能特征 327
12.7　符号表的索引实现 329
12.8　在BST的根节点插入 332
12.9　其他ADT函数的BST实现 336
第13章　平衡树 343
13.1　随机化BST 345
13.2　伸展BST 350
13.3　自顶向下2-3-4树 355
13.4　　红黑树 360
13.5　跳跃表 368
13.6　性能特征 374
第14章　散列 377
14.1　散列函数 377
14.2　链地址法 385
14.3　线性探测法 388
14.4　双重散列表 392
14.5　动态散列表 396
14.6　综述 399
第15章　基数搜索 402
15.1　数字搜索树 402
15.2　线索 406
15.3　帕氏线索 413
15.4　　多路线索和TST 419
15.5　文本字符串索引算法 430
第16章　外部搜索 434
16.1　游戏规则 435
16.2　索引顺序访问 436
16.3　B树 438
16.4　 可扩展散列 447
16.5　综述 455出版者的话
译者序
前言

第一部分　 基础知识
第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
3.1　构建组件 37
3.2　数组 44
3.3　链表 49
3.4　链表的基本处理操作 54
3.5　链表的内存分配 60
3.6　字符串 63
3.7　复合数据结构 66
第4章　抽象数据类型 74
4.1　抽象对象和对象集 76
4.2　下推栈ADT 78
4.3　栈ADT客户示例 79
4.4　栈ADT的实现 84
4.5　创建一个新ADT 87
4.6　FIFO队列和广义队列 90
4.7　复制和索引项 95
4.8　一级ADT 99
4.9　基于应用的ADT示例 106
4.10　展望 110
第5章　递归与树 111
5.1　递归算法 111
5.2　分治法 116
5.3　动态规划 127
5.4　树 133
5.5　树的数学性质 138
5.6　树的遍历 140
5.7　递归二叉树算法 145
5.8　图的遍历 149
5.9　综述 155
第三部分　 排　　序
第6章　基本排序方法 157
6.1　游戏规则 158
6.2　选择排序 161
6.3　插入排序 162
6.4　冒泡排序 164
6.5　基本排序方法的性能特征 166
6.6　希尔排序 171
6.7　对其他类型的数据进行排序 177
6.8　索引和指针排序 180
6.9　链表排序 185
6.10　关键字索引统计 188
第7章　快速排序 191
7.1　基本算法 191
7.2　快速排序算法的性能特征 195
7.3　栈大小 198
7.4　小的子文件 201
7.5　三者取中划分 203
7.6　重复关键字 206
7.7　字符串和向量 209
7.8　选择 210
第8章　归并与归并排序 213
8.1　两路归并 213
8.2　抽象原位归并 215
8.3　自顶向下的归并排序 216
8.4　基本算法的改进 219
8.5　自底向上的归并排序 220
8.6　归并排序的性能特征 223
8.7　归并排序的链表实现 225
8.8　改进的递归过程 227
第9章　优先队列和堆排序 229
9.1　基本操作的实现 231
9.2　堆数据结构 233
9.3　基于堆的算法 235
9.4　堆排序 240
9.5　优先队列ADT 244
9.6　索引数据项的优先队列 247
9.7　二项队列 250
第10章　基数排序 258
10.1　位、字节和字 259
10.2　二进制快速排序 261
10.3　MSD基数排序 265
10.4　三路基数快速排序 271
10.5　LSD基数排序 274
10.6　基数排序的性能特征 278
10.7　亚线性时间排序 280
第11章　特殊用途的排序方法 284
11.1　Batcher奇偶归并排序 284
11.2　排序网 289
11.3　外部排序 295
11.4　排序－归并的实现 299
11.5　并行排序/归并 303
第四部分　 搜　　索
第12章　符号表和二叉搜索树 307
12.1　符号表抽象数据类型 308
12.2　关键字索引搜索 311
12.3　顺序搜索 313
12.4　二分搜索 318
12.5　二叉搜索树 321
12.6　BST的性能特征 327
12.7　符号表的索引实现 329
12.8　在BST的根节点插入 332
12.9　其他ADT函数的BST实现 336
第13章　平衡树 343
13.1　随机化BST 345
13.2　伸展BST 350
13.3　自顶向下2-3-4树 355
13.4　　红黑树 360
13.5　跳跃表 368
13.6　性能特征 374
第14章　散列 377
14.1　散列函数 377
14.2　链地址法 385
14.3　线性探测法 388
14.4　双重散列表 392
14.5　动态散列表 396
14.6　综述 399
第15章　基数搜索 402
15.1　数字搜索树 402
15.2　线索 406
15.3　帕氏线索 413
15.4　　多路线索和TST 419
15.5　文本字符串索引算法 430
第16章　外部搜索 434
16.1　游戏规则 435
16.2　索引顺序访问 436
16.3　B树 438
16.4　 可扩展散列 447
16.5　综述 455