算法I-IV（C++实现）：基础、数据结构、排序和搜索（第三版）——国外经典计算机科学教材 - (2010 年度畅销榜NO.692 )

Robert Sedgewick完全重写了他的著作，对它进行了充分的扩展和更新，涵盖了目前重要的算法和数据结构。Christopher Van Wyk和Sedgewick开发的新实现采用的是C++语言，这种实现不仅能够直接地表达算法，而且给编程者提供了实践的方法，以便在真正的应用中测试这些算法。\r\n 新的版本提供了很多新算法，而且对每个算法的解释也比以前的版本详细很多。新的版面设计以及详细、富有创意并且具有注释的插图，使本书的表达能力大大地提高了。第三版保留了将理论和实践成功混合在一些的特点，正是这一点，使Sedgewick的著作成为25万多名程序员无价的参考资源。\r\n 本书是全卷的前半部分，涵盖了基本的数据结构、排序算法、搜索算法以及它们的相关应用。虽然本书实质上可以用于各种语言的程序设计，Christopher Van Wyk和Sedgewick的实现都采用了C++类和ADT实现的自然对应。\r\n 本书的精彩内容包括：\r\n ●扩展了对数组、链表、字符串树及其他基本数据结构的介绍。 \r\n ●比以前的版本更加着重于抽象数据类型(ADT)、模块化程序设计方法、面向对象的程序设\r\n 计方法和C++类。 \r\n ●有关排序、选择、优先级队列ADT实现和符号表ADT(搜索)实现的算法，超过100个。 \r\n ●关于二项式队列、多路基数排序、随机化BST、发散树、跳跃表、多叉线索、8树、可扩充\r\n 散列等，采用了新的实现。\r\n ●关于算法的量化分析，是比较算法的依据。\r\n ●1000多条新的练习，帮助读者学习算法。 \r\n 无论是你初学算法，还是想找一本将最新C++经典算法和新算法融入程序设计的参考手册，你都会发现本书提供了丰富的有用信息。

出版说明\r\n前言\r\n第一部分 基本原理\r\n 第一章 简介\r\n 1.1 算法\r\n 1.2 示例：连通问题\r\n 1.3 合并－查找算法\r\n 1.4 前景展望\r\n 1.5 总结\r\n 第二章 算法分析原理\r\n 2.1 实现和经验分析\r\n 2.2 算法分析\r\n 2.3 函数的增长\r\n 2.4 大O符号\r\n 2.5 递归基础知识\r\n 2.6 算法分析举例\r\n 2.7 保证、预测和限制\r\n 第一部分参考资料\r\n第二部分 数据结构\r\n 第三章 基本数据结构\r\n 3.1 构建组件\r\n 3.2 数组\r\n 3.3 链表\r\n 3.4 基本的链表处理\r\n 3.5 链表的内存分配\r\n 3.6 字符串\r\n 3.7 复合数据结构\r\n 第四章 抽象数据类型\r\n 4.1 抽象对象和对象集合\r\n 4.2 下推栈ADT\r\n 4.3 栈ADT客户示例\r\n 4.4 栈ADT的实现\r\n 4.5 创建一个新ADT\r\n 4.6 FIFO队列和广义队列\r\n 4.7 复制和索引项\r\n 4.8 一级ADT\r\n 4.9 基于应用的ADT范例\r\n 4.10 前景展望\r\n 第五章 递归与树\r\n 5.1 递归算法\r\n 5.2 分治法\r\n 5.3 动态编程\r\n 5.4 树\r\n 5.5 二叉树的数学性质\r\n 5.6 树遍历\r\n 5.7 递归二叉树算法\r\n 5.8 图通历\r\n 5.9 前景展望\r\n 第二部分参考资料\r\n第三部分 排序算法\r\n 第六章 基本排序方法\r\n 6.1 游戏规则\r\n 6.2 选择排序\r\n 6.3 插入排序\r\n 6.4 冒泡排序\r\n 6.5 基本排序方法的执行特性\r\n 6.6 Shell排序法\r\n 6.7 对其他类型的文件进行排序\r\n 6.8 索引和指针排序\r\n 6.9 链表排序\r\n 6.10 关键字索引统计\r\n 第七章 快速排序\r\n 7.1 基本算法\r\n 7.2 快速排序算法的性能特性\r\n 7.3 栈大小\r\n 7.4 小的子文件\r\n 7.5 利用三个元素的中间元素来划分\r\n 7.6 重复值\r\n 7.7 字符串和向量\r\n 7.8 选择\r\n 第八章 归并及归并排序\r\n 8.1 二路归并\r\n 8.2 抽象的合适归并算法\r\n 8.3 自顶向下的归并排序\r\n 8.4 对基本排序方法进行改进\r\n 8.5 自底向上的归并排序\r\n 8.6 执行典型的归并排序算法\r\n 8.7 使用链表执行归并排序\r\n 8.8 再次讨论递归过程\r\n 第九章 优先队列与堆排序\r\n 9.1 基本的实现方法\r\n 9.2 堆的数据结构\r\n 9.3 基于堆的算法\r\n 9.4 堆排序\r\n 9.5 优先队列抽象数据类型\r\n 9.6 索引元素的优先队列\r\n 9.7 二项式队列\r\n 第十章 基数排序\r\n 10.1 比特、字节、字\r\n 10.2 二进制快速排序\r\n 10.3 MSD基数排序\r\n 10.4 三路基数快速排序\r\n 10.5 LSD基数排序\r\n 10.6 基数排序的特性\r\n 10.7 运行时间低于线性的排序\r\n 第十一章 特殊用途的排序方法\r\n 11.1 巴彻尔奇偶归并排序\r\n 11.2 排序网络\r\n 11.3 外部排序\r\n 11.4 “排序－归并”的实现\r\n 11.5 并行“排序－归并”\r\n 第三部分参考资料\r\n第四部分 搜索算法\r\n 第十二章 符号表和二叉搜索树\r\n 12.1 符号表抽象数据类型（ADT）\r\n 12.2 关键字索引检索\r\n 12.3 顺序搜索\r\n 12.4 二叉搜索\r\n 12.5 二叉搜索树\r\n 12.6 BST的性能特性\r\n 12.7 符号表的索引实现\r\n 12.8 在BST的根进行的插入\r\n 12.9 其他ADT函数的BST实现\r\n 第十三章 平衡树\r\n 13.1 随机化BST\r\n 13.2 发散BST\r\n 13.3 自上而下2－3－4树\r\n 13.4 红黑树\r\n 13.5 跳跃表\r\n 13.6 性能特性\r\n 第十四章 散列\r\n 14.1 散列函数\r\n 14.2 链地址法\r\n 14.3 线性探测\r\n 14.4 双重散列\r\n 14.5 动态散列表\r\n 14.6 综述\r\n 第十五章 基数检索\r\n 15.1 数字搜索树\r\n 15.2 线索（trie）\r\n 15.3 帕氏线索\r\n 15.4 多叉线索和TST\r\n 15.5 文本字符索引算法\r\n 第十六章 外部排序\r\n 16.1 游戏规则\r\n 16.2 索引顺序存取\r\n 16.3 B树\r\n 16.4 可扩充散列\r\n 16.5 综述\r\n 第四部分参考资料

Robert Sedgewick是普林斯顿大学计算机系的William O.Baker教授，也是Adobe Systems公司的主管，曾经在Xerox PARC、IDA和INRIA公司担任研究员。
Christopher J.Van Wyk是Drew大学数学和计算机系的教授，曾在BELL实验室担任研究员，现在是那里的顾问。

写作本书的意图是纵览当今所使用的最重要的计算机算法, 并为越来越多需要了解这方面知识的读者讲解基础的技术. 本书可以在学生掌握了基本的程序设计技能, 熟悉了计算机系统, 但是还没有学习过计算机科学或计算机应用的高级领域的专门课程时, 作为计算机科学的第二. 第三或第四门课程的教科书. 此外, 由于本书包含了大量有用算法的实现和关于其性能特征的详细信息, 所以它还适用于自学, 或作为那些从事计算机系统或应用程序开发的人员的参考手册. 宽广的视角使本书成为了计算机算法领域最合适的入门读物. 对于这新的一版, 我不仅完全重写了它的内容, 而且还添加了一千多个练习. 一百多幅图和许多程序, 此外还给所有的图和程序都添加了详细的注释. 新的素材涵盖了两个方面的内容——新的主题和对许多经典算法的更完整的解释. 抽象数据类型是这本书的新重点, 这个新重点使程序的应用更广泛, 并且与现代程序设计环境的关系更紧密. 读过本书旧版本的人一定会发现, 新版本包含了更为丰富的新信息. 所有读者都能感到大量的教学性资料为掌握基本概念提供了有效的途径. 由于新的素材数量过多, 所以我们把新版本分成了两卷(每一卷的容量大约都相当于旧的版本), 本书就是第一卷. 这一卷包括基本概念. 数据结构. 排序算法和搜索算法, 第二卷涵盖的高级算法和应用程序是以第一卷介绍的基本抽象概念和方法为基础的. 在这一版中, 几乎所有关于基本原理和数据结构的素材都是新的. 这本书不仅仅是为程序设计人员和计算机科学系的学生而编写的, 凡是想使计算机运行得更快, 或想用它解决更多问题的人都可以使用这本书. 本书中的算法代表了过去50多年所研究的知识的主体, 对于形形色色的应用程序来说, 它们已经成为有效使用计算机所不可缺少的. 从物理学中的N体仿真到分子生物学中的基因序列问题, 这些基础算法已成为科学研究的要素, 从数据库系统到Internet搜索引擎, 它们已经成为现代软件系统的实质. 随着计算机应用领域的不断扩大, 本书介绍的大量基础算法的效用也在逐渐增长. 本书的目标就是成为学生和那些想了解基础算法并且能够灵活地运用这些算法作为基本工具来处理任意计算机应用程序的专业人士的资源. 范围 本书共有十六章, 分为四大部分：基本原理. 数据结构. 排序算法和搜索算法. 这里的说明是想让读者对尽可能多的基础算法的基本特性有一个了解. 本书介绍的算法已经经过多年的广泛应用, 代表了程序员和计算机科学系学生掌握的知识的主体. 从二项式队列到帕氏线索算法这个范围内的有创见的方法都与计算机科学核心的基础范例相关. 第二卷由另外四部分构成, 它们分别为字符串处理算法. 几何算法. 图形算法和高级主题. 我写这本书的主要意图是将各个领域应用的基础方法集合起来, 从而提供用计算机解决基本问题的最好方法. 如果你已经学习过一两门计算机科学的初级课程(如C抖. Java或C等高级语言的程序设计课程, 可能还有讲解程序设计系统的基础概念的课程)或者具有同等的程序设计经验, 那么一定会非常欣赏本书提供的资料. 因此, 本书是为每个熟悉现代程序设计语言和现代计算机系统的基本特性的人而编写的. 书中所建议的参考文献有助于你弥补背景知识的不足. 由于用来支持分析结果的大部分数学知识都来源于本书之内(或者被标记为不在本书范围之内), 所以尽管具有完备的数学知识无疑会有很大帮助, 但是专门的数学准备却不是必需的. 课程中的用法 如何教授本书的内容具有极大的灵活性, 这是由教师的经验和学生的知识储备决定的. 这里有充足的基础内容用来教授初学者数据结构, 也有充足的高级主题来教授高年级学生算法设计与分析. 有些教师可能想着重于实现和实践方面的内容, 有些教师则可能想着重于分析和理论概念方面的内容. 我为这本书的使用设计了多种课程学习资料, 其中包括讲稿用的幻灯片. 程序设计作业. 家庭作业以及示例测验和交互式练习. 访问本书的主页http：／／www.awl.com／cseng／titles／O-201—35088-2可以得到这些资料. 关于数据结构和算法的基础课程可能会着重于第二部分中的基本数据结构和它们在第三. 四部分中的实现中的使用. 关于算法设计和分析的课程可能会着重于第一部分和第五章中的基础内容, 然后研究第三. 四部分中的算法如何达到良好的渐近性能的方法. 关于软件工程的课程可能会省略数学和高级算法部分的内容, 而着重于如何把这里给出的算法实现集成到大的应用程序或系统中. 关于算法的课程则可能采用通盘考虑的方法并介绍所有领域内的概念. 本书的早期版本近年来被全世界各大学院和大学用作计算机科学的第二或第三门课程的教材或其他课程的补充性阅读材料. 在普林斯顿大学, 我们的经验是这本书内容广泛, 为专业学生提供了计算机科学的引论, 此后有关算法分析. 系统程序设计和理论性计算机科学的课程都可以对它进行扩展, 此外它还给其他学科的学生提供了一整套方法, 他们可以立刻将这些方法很好地利用起来. 本书中的练习(大部分是这一版新添的)分为几种类型. 有些专用于测试对文中内容的理解程度, 只要求读者完成一个练习或应用文中介绍的概念. 有些则涉及到算法的实现和结合, 或者根据学习经验比较各种算法来学习它们的特性. 还有一些则是重要内容的深入探讨, 这些内容不适于放在正文中. 仔细阅读和思考这些练习会使每个读者受益匪浅. 实际应用的算法 任何想更加有效地使用计算机的人都可以把这本书作为参考手册或自学材料. 具有程序设计经验的人可以在这本书中找到许多专业主题的内容. 对于更大范围内的读者, 则可以阅读个别独立的章节, 尽管有时某一章中的算法会用到前一章中介绍的方法. 本书的定位是研究有可能实际用到的算法. 它提供的专业工具信息很中肯, 读者可以放心地实现. 调试和试验算法, 来解决问题或在应用程序中提供功能性. 本书中讨论的算法都有完整的实现, 而且在一系列连贯的示例中还有关于操作这些应用程序的描述. 由于我们使用的是真正的代码, 而不是伪代码, 所以你可以便捷地将它们应用到实际当中. 访问本书的主页可以得到各个程序的清单. 你可以以多种方式利用这些有指导意义的程序来研究算法. 阅读这些代码可以检测你对算法细节的理解程度, 或者弄明白初始化. 边界条件处理和其他常常给程序设计带来挑战的问题的解决方法. 还可以试着运行一下代码来查看运行中的算法, 根据经验研究它们的性能, 并将你得到的结果与书中的表进行对照, 或者尝试着对它们进行一些修改. 在适当的时候, 书中会列出经验数据和分析结果以说明为什么选择某些算法. 当要引起注意时, 它会描述实际应用的算法和纯理论的结果之间的关系. 尽管没有强调算法分析和理论计算机科学之间的联系, 但是上下文中仍然对它们进行了说明. 有关算法和实现的性能特征被综合在一起, 进行了概括, 在本书中随处可见. 程序设计语言 本书中所有实现所用的程序设计语言都是C++. 其中的程序使用了大量标准的C++语法, 而且文中还对每个结构做了简要说明. 我和Chris Van Wyk基于类. 模板和重载操作符开发了一种C++程序设计形式, 我们认为这种形式是把算法和数据结构当作真正的程序来表示的一种有效方式. 我们努力使实现的代码精致. 紧凑. 高效, 并具有可移植性. 由于这种形式无论何时都是一致的, 所以用它开发的相似程序看起来就比较相像. 本书中的许多算法本身就具有相似性, 而与实现它们的语言无关, 例如快速排序算法就是进行快速排序(一个典型的例子), 无论它是用Ada. Algol-60. Basic. C. C++. Fortran. Java. Mesa. MoDula-3. Pascal. PostScript. Smalltalk以及其他无法尽数的程序设计语言实现的, 还是在证明了它是高效排序方法的环境中实现的. 一方面, 我们的代码是根据用这些语言或大量其他的语言(本书还有一个用C语言实现的版本, 此外用Java实现的版本很快就会面世)实现算法的经验形成的, 另一方面, 某些语言的某些特性是根据它们的设 计者使用本书介绍的某些算法和数据结构的经验形成的. 第一章中包含一个复杂的例子, 说明如何用这种方法开发算法的高效C++实现. 第二章描述了对这些算法进行分析的方法. 第三和第四章说明并验证了我们用来实现数据类型和ADT实现的基本机制. 这四章为本书的其余章节打下了基础.