本书细腻讲解计算机算法的C语言实现。全书分为四部分，共16章。包括基本算法分析原理，基本数据结构、抽象数据结构、递归和树等数据结构知识，选择排序、插入排序、冒泡排序、希尔排序、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序方法，并比较了各种排序方法的性能特征，在进一步讲解符号表、树等抽象数据类型的基础上，重点讨论散列方法、基数搜索以及外部搜索方法。

基本信息

内容概要

作者简介

目录

译者序

前言

基本信息

原书名： Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching (3rd Edition) (Pts. 1-4)原出版社： Addison-Wesley Professional

作者： (美)Robert Sedgewick

译者： 霍红卫[同译者作品

出版社：机械工业出版社

出版日期：2009 年10月

开本：16开页码：456版次：3-1

内容概要

书中提供了用C语言描述的完整算法源程序，并且配有丰富的插图和练习，还包含大量简洁的实现将理论和实践成功地相结合，这些实现均可用在真实应用上。.本书内容丰富，具有很强的实用价值，适合作为高等院校计算机及相关专业本科生算法课程的教材，也是广大研究人员的极佳参考读物。本书是Sedgewick彻底修订和重写的C算法系列的第一本。全书分为四部分，共16章。第一部分“基础知识”(第1～2章)介绍基本算法分析原理。第二部分“数据结构”(第3～5章)讲解算法分析中必须掌握的数据结构知识，主要包括基本数据结构、抽象数据结构、递归和树。第三部分“排序”(第6～11章)按章节顺序分别讨论基本排序方法(如选择排序、插入排序、冒泡排序、希尔排序等)、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序方法，并比较了各种排序方法的性能特征。第四部分“搜索”(第12～16章) 在进一步讲解符号表、树等抽象数据类型的基础上，重点讨论散列方法、基数搜索以及外部搜索方法。..书中提供了用C语言描述的完整算法源程序，并且配有丰富的插图和练习。作者用简洁的实现将理论和实践成功地结合了起来，这些实现均可在真实应用上测试，使得本书自问世以来备受程序员的欢迎。本书可作为高等院校计算机相关专业算法与数据结构课程的教材和补充读物，也可供自学之用。

作者简介

：

Robed Sedgewick拥有斯坦福大学博士学位(导师为Donald E. Knuth)，昔林斯顿大学计算机科学系教授，Adobe Systems公司董事，曾是XeroxPARC的研究人员，还曾就职于美国国防部防御分析研究所以及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 .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

译者序

本书是算法方面的优秀著作之一。它系统地阐述了算法的特征以及它们可能应用的场合，讨论了算法分析与理论计算机科学的关系，并通过实验数据和分析结果表明选择何种算法来解决实际问题。书中包含了基本概念、数据结构、排序算法和搜索算法。.

这本书不仅适合于程序员和计算机科学专业的学生，而且也适合于那些想利用计算机并想使它运行更快或是想要解决更大问题的人们。书中的算法代表了过去50年来所研究的知识主体。对于大量应用问题，这些知识主体已经成为有效使用计算机不可缺少的部分。从物理学中的N-体模拟问题到分子生物学中的序列分析问题，在此所描述的基本方法在科学研究中已日显重要。另外，从数据库系统到Internet搜索引擎，这些方法已经成为现代软件系统的重要组成部分。随着计算机应用的覆盖面越来越广，基本算法的影响也日益显著。

本书主要内容及特点如下：

扩展介绍了数组、链表、串、树和其他基本数据结构。

为排序、选择、优先队列ADT实现和符号表ADT（查找）实现提供了多达100多个算法。

介绍了多路基数排序、随机BST、伸展树、跳跃表、多路trie等新的数据结构。..

为算法提供了很多可视化的信息，还有大量实验研究和基本分析研究，从而为选择算法解决实际问题提供了依据。

增加了1000多个新练习，从而有助于深入了解算法的特征。

本书以大量图例说明算法的工作过程，使得算法更加易于理解和掌握。

适合作为高等院校算法设计课程的教材，同时可作为从事软件开发和工程设计的专业人员的参考书。

由于时间较紧及译者水平有限，译文难免有错误及不妥之处，恳请读者批评指正。...

译者

于西安电子科技大学计算机学院

2009年4月

前言

写本书的目的是为了对当今使用最为重要的计算机算法做一综述，并为需要学习这方面知识的越来越多的读者提供基础的技术。本书可以在学生掌握了所需的基本程序设计技巧，熟悉了计算机系统，但还未学过计算机科学或计算机应用高级领域的专业课程的时候，用作计算机科学的第二、第三或第四门课程的教科书。此外，由于本书包含了大量有用算法的实现，以及关于这些算法的性能特征的详细信息，因而它还可用于自学，或者作为从事计算机系统或应用程序开发人员的参考手册。宽广的视角使得本书成为计算机算法领域最合适的入门读物。.

对于新的一版，我不仅完全重写了它的内容，而且还添加了一千多个练习、一百多幅图表和数十个新程序。我还给所有图表和程序添加了详细的注释。新的素材不仅涵盖了新的主题，而且还包含对经典算法的更完整解释。抽象数据类型是这本书的重点，这使得程序应用更广泛，并且与现代面向对象的程序设计环境更紧密。读过本书旧版本的人一定会发现，新版本包含了更为丰富的新信息，所有读者将发现大量的教学资料为掌握基本概念提供了有效途径。

由于新的素材数量过多，所以我们把新版本分为两卷（每一卷的容量都大约为旧版本的大小），本书是第一卷。这卷书中包含了基本概念、数据结构、排序算法和搜索算法；第二卷涵盖的高级算法及应用是以第一卷的基本抽象概念和方法为基础的。这个新版中的关于基本原理和数据结构的所有素材几乎都是新的。

这本书不仅适合于程序员和计算机科学专业的学生，而且也适合于想利用计算机并想使它运行更快或是想要解决更大问题的人们。这本书中的算法代表了过去50年来所研究的知识主体。对于大量应用问题，这些知识主体已经成为有效使用计算机的不可缺少的部分。从物理学中的N-体模拟问题到分子生物学中的序列分析问题，在此所描述的基本方法在科学研究中已日显重要。另外，对于从数据库系统到Internet搜索引擎，这些方法已经成为现代软件系统的重要组成部分。随着计算机应用的覆盖面越来越广，基本算法的影响也日益显著。本书的目标是要提供一种资源，使广大学生以及专业人士可以了解并有效利用这些算法解决计算机应用中出现的问题。

本书范围

本书共有16章，分为四大部分：基础、数据结构、排序和搜索。这里的说明是想使读者对尽可能多的基本算法有一个了解。本书描述的从二项队列到帕氏线索这个范围内的独创性的方法，都与计算机科学核心的基本范型相关。第二卷由另外四部分组成，涵盖了字符串算法、几何算法、图算法和高级主题。写这些书的主要意图是把各个领域中应用的基本方法集合在一起，从而为用计算机求解问题提供最好的方法。

如果你已经学过计算机科学的一两门课程，如C、Java或C++这样的高级程序设计语言课程，或者可能还有讲授程序设计系统的基本概念的课程，或者具有同等的程序设计经验，那么一定会非常欣赏本书提供的资料。因此，本书是为那些熟悉现代程序设计语言和现代计算机系统的基本特性的人而编写的。书中给出的参考文献会有助于弥补背景知识的不足。

由于用来支持分析结果的大部分数学知识都包含在本书中（或者做出标记不在本书之中），因而尽管具有完备的数学知识肯定会有帮助，但专门对数学知识的准备不是必要的。

教学中的用法

在教学中如何使用本书内容具有很大的灵活性，这取决于教师的偏好以及学生所做的准备。这里所描述的算法多年以来已经得到广泛应用，而且无论对于实际的程序员还是计算机科学专业的学生，这些算法都代表了基本的知识主体。书中涵盖了足够的基本内容可用作数据结构课程的学习，也有足够详细的高级主题用于算法课程的学习。有些教师可能希望强调与实现和实践有关的内容，而另外一些教师则可能把重点放在分析和理论概念上。

教学中使用的电子文档、程序设计示例作业、为学生提供的交互式练习以及其他课程有关的资料都可在本书的主页上找到。

关于数据结构和算法的基础课程可以把重点放在第二部分的基本数据结构及其他们在第三、四部分实现中的应用。关于算法设计与分析的课程可以把重点放在第一部分和第五部分中的基础内容，然后在第三部分和第四部分研究算法达到良好渐近性能的方法。关于软件工程的课程可能会省略数学和高级算法的内容，并把重点放在如何把给出的算法实现集成到大的程序或系统中。关于算法的课程则可能进行综述并引入所有这些领域的概念。

本书的早期版本在近年来为世界各地的学院或大学用作计算机科学的第二或第三门课程的教材或其他课程的补充阅读材料。在普林斯顿大学，我们的经验表明这本书内容覆盖面广，为主修课程提供计算机科学的导引，并可在后续的算法分析、系统程序设计以及理论计算机科学的课程中对它进行扩充，同时为其他学科的学生提供一整套的技术，使他们能很快学以致用。

这一版中的大多数练习是新添加的，分为几种类型。一类练习的目的是为了测试对课文中内容的理解，要求读者能够完成某个例子或应用课文中描述的概念。另一类练习则涉及实现算法和把算法整理到一起，或者进行实验研究从而对各种算法进行比较以及了解其性质。还有一类练习则是一些重要信息的知识库，其详细程度本身不适合放在正文中。阅读并思考这些练习，会使每个读者受益匪浅。

算法的实用性

若希望更有效地使用计算机，可以把这本书用作参考书，或用于自学。具有程序设计经验的人可以从本书中找到有关某个特殊主题的信息。对于更大范围的读者，尽管某些情况下，某一章中的算法使用了前一章中的方法，但你仍可以独立于本书的其他章节阅读本书的某个章节。

本书的定位是研究有可能实用的算法。本书提供了算法的详尽信息，读者可以放心地实现和调试算法，并使算法能够用于求解某个问题，或者为某个应用提供相关功能。书中包括了所讨论方法的完整实现，并在一系列一致的示例程序中给出了这些操作的描述。由于我们使用了实际代码，而不是伪代码，因而在实际中可以很快地使用这些程序。通过访问本书的主页可以得到程序的代码清单。

实际上，书中算法的实际应用会产生数百幅图表。正是这些图表提供的立体视觉直观地发现了许多算法。..

本书详细讨论了算法的特征以及它们可能应用的场合。尽管并不强调，但是书中论述了算法分析与理论计算机科学的联系。在适当的时候，书中都给出了经验性的数据和分析结果用以说明为什么选择使用某些算法。如果有趣，书中还会描述所讨论的实际算法与纯理论结果之间的关系。关于算法性能特征和实现的某种信息的综合、概括和讨论都会贯穿本书的始终。