C算法（第一卷：基础、数据结构、排序和搜索）（第三版）
点击看大图基本信息
内容简介回到顶部↑
《C算法》介绍了当今最重要的算法，共分3卷，本书是第1卷。第1卷分4部分、共16章。第一部分“基础知识”（第1～2章）介绍了基本算法分析原理。第二部分“数据结构”（第3～5章）讲解算法分析中必须掌握的数据结构知识。主要包括基本数据结构、抽象数据结构、递归和树。第三部分“排序”（第6～11章）按章节顺序分别讨论了基本排序方法（如选择排序、插入排序、冒泡排序、希尔排序等）、快速排序方法，归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊目的排序方法，并比较了各种排序方法的性能特征。第四部分“搜索”（第12～16章）在进一步讲解符号表、树等抽象数据类型的基础上，重点讨论哈希方法、基数搜索以及外部搜索方法。
书中提供了用C语言描述的完整算法源程序，并且配有丰富的插图和练习。可作为高等院校相关专业的教材和补充读物，也可供自学之用。
书中提供了用C语言描述的完整算法源程序，并且配有丰富的插图和练习。可作为高等院校相关专业的教材和补充读物，也可供自学之用。
作译者回到顶部↑
目录回到顶部↑
第一部分 基础知识
第1章 导论 2
1.1 算法 2
1.2 问题示例：连通性（connectivity） 4
练习 7
1.3 并集—查找算法 7
练习 17
1.4 展望 18
练习 19
1.5 小结 19
第2章 算法分析原理 22
2.1 实现与试验分析 22
练习 25
2.2 算法分析 25
练习 27
2.3 函数增长 27
练习 32
2.4 o记号 32
练习 35
2.5 基本递推式 36
第1章 导论 2
1.1 算法 2
1.2 问题示例：连通性（connectivity） 4
练习 7
1.3 并集—查找算法 7
练习 17
1.4 展望 18
练习 19
1.5 小结 19
第2章 算法分析原理 22
2.1 实现与试验分析 22
练习 25
2.2 算法分析 25
练习 27
2.3 函数增长 27
练习 32
2.4 o记号 32
练习 35
2.5 基本递推式 36
译者序回到顶部↑
译者的话
将数据结构和算法比作计算机科学的基石毫不为过，追求程序的高效是永恒的主题。Robert Sedgewick以三卷AlgorithmslnC宏大篇幅对算法的意义进行了全新的诠释(第三卷尚未出版)。算法已不再是纯粹的运算实现，它已经发展成一门设计艺术!新版Algorithms in C不仅浓缩了过去几十年间应用于计算机科学领域的最重要、最高效算法，而且紧紧抓住算法的性能特征进行讨论。权威的资料、层次分明的讲解、丰富的配套练习，正是全世界无数院校将它作为算法首选教科书的原因。
本书为三卷本Algorithms in C的第一卷，主要包括基础知识、数据结构、排序和搜索4部分内容。为了便于教师因材施教，全书内容安排层次性清晰、重点突出。与传统参考书相比，主要有如下特点：
． 各章内容相对独立，可以单独阅读，或者根据实际教学需要，选择性地组合讲解。
． 为所有重要算法提供了可靠的实现代码。
． 配套插图丰富，并提供了详细的注释，使学习效果事半功倍。
． 提供了大量练习。更重要的是，作者将这些练习按不同层次、不同学习目的，将这些练习分类。
． 详尽的参考文献，并综述各部分内容的主要参考文献。
在翻译过程中，我感觉最深刻的还有两点。第一点，作者所提供的所有源码尽量保持统一的风格、尽量使用抽象数据类型，因此，用其他高级编程语言来改写这些程序可以轻松实现。第二点，全书将算法分析与数据结构的讲解融为一体。这种相得益彰的讲授方式的优势不言而喻。
作为译者，也作为读者，面对这些优秀的算法，我毫不犹豫地将它们运用到我的编程实践中。在应用实践中，有以下几点体会：
． 应用某一算法前，建议先掌握其性能特征，确保选择的算法不一定是最快的，但必须是 最优的。
． 要透彻理解课文中讲解的算法原理，最好的办法是完成每一章后面的相关练习。
为了方便读者的学习，本书提供了英中对照的索引，并按字母顺序排列。
在我国，Algorithms in C的英文影印版已经用作许多高校的算法和数据结构教学的参考书。因此，为广刘币生和自学者早日奉上中文版无疑具有重要的意义，也使我感觉到责任的重大。但由于水平有限，且时间仓促，错误在所难免，希望广大读者不吝指正。我的联系E-mail：web_zhou@21cn．com。
译者
2003年6月
将数据结构和算法比作计算机科学的基石毫不为过，追求程序的高效是永恒的主题。Robert Sedgewick以三卷AlgorithmslnC宏大篇幅对算法的意义进行了全新的诠释(第三卷尚未出版)。算法已不再是纯粹的运算实现，它已经发展成一门设计艺术!新版Algorithms in C不仅浓缩了过去几十年间应用于计算机科学领域的最重要、最高效算法，而且紧紧抓住算法的性能特征进行讨论。权威的资料、层次分明的讲解、丰富的配套练习，正是全世界无数院校将它作为算法首选教科书的原因。
本书为三卷本Algorithms in C的第一卷，主要包括基础知识、数据结构、排序和搜索4部分内容。为了便于教师因材施教，全书内容安排层次性清晰、重点突出。与传统参考书相比，主要有如下特点：
． 各章内容相对独立，可以单独阅读，或者根据实际教学需要，选择性地组合讲解。
． 为所有重要算法提供了可靠的实现代码。
． 配套插图丰富，并提供了详细的注释，使学习效果事半功倍。
． 提供了大量练习。更重要的是，作者将这些练习按不同层次、不同学习目的，将这些练习分类。
． 详尽的参考文献，并综述各部分内容的主要参考文献。
在翻译过程中，我感觉最深刻的还有两点。第一点，作者所提供的所有源码尽量保持统一的风格、尽量使用抽象数据类型，因此，用其他高级编程语言来改写这些程序可以轻松实现。第二点，全书将算法分析与数据结构的讲解融为一体。这种相得益彰的讲授方式的优势不言而喻。
作为译者，也作为读者，面对这些优秀的算法，我毫不犹豫地将它们运用到我的编程实践中。在应用实践中，有以下几点体会：
． 应用某一算法前，建议先掌握其性能特征，确保选择的算法不一定是最快的，但必须是 最优的。
． 要透彻理解课文中讲解的算法原理，最好的办法是完成每一章后面的相关练习。
为了方便读者的学习，本书提供了英中对照的索引，并按字母顺序排列。
在我国，Algorithms in C的英文影印版已经用作许多高校的算法和数据结构教学的参考书。因此，为广刘币生和自学者早日奉上中文版无疑具有重要的意义，也使我感觉到责任的重大。但由于水平有限，且时间仓促，错误在所难免，希望广大读者不吝指正。我的联系E-mail：web_zhou@21cn．com。
译者
2003年6月
前言回到顶部↑
本书旨在综述当今程序员使用的最重要的计算机算法，同时为越来越多需要学习这些算法的人讲解基本技术。本书可以用作学习计算机科学的第二、第三或第四门课程的教科书，供那些掌握了基本编程技能并熟悉了计算机系统，但还未学习计算机科学或着计算机应用的高阶领域专业课程的学生来选修。本书也可以作为从事计算机系统或应用程序开发的自学教材或参考书，因为它包含有用算法的实现以及这些算法性能特征的详细信息。本书讲解全面，也是一本合适的算法导论书。
我全部重写了新版内容，添加了1000多个新练习、100多幅新图以及许多新程序。我还为所有插图和程序添加了详细的注释。这些新材料既包含了一些新主题，还对许多经典算法提供了更全面的解释。整本书还添加了一个重点内容，即抽象数据类型，使得这些程序更加通用、更适应于现代面向对象编程环境。阅读过本书旧版的读者在新版中可以学到大量新知识；所有读者都可以阅读到丰富的教学材料，通过它们可以快速掌握一些重要概念。
由于添加了大量新材料，所以将新版分为二卷，每一卷都与旧版篇幅相当，本书为第一卷。这一卷包括基本概念、数据结构、排序算法以及搜索算法；第二卷在本书基本抽象和方法的基础上讲解高级算法和应用。在新版本中，几乎所有基础知识和数据结构的材料都是新的。
本书所面向的对象并不仅仅是程序员和计算机专业的学生。几乎每个计算机的使用者都希望计算机能够进行得更快或者能够解决更大的问题。本书中的算法代表过去50年的知识发展水平，针对各种不同的应用，在高效使用计算机中不可或缺。从物理学上的N-体模拟(N-body simulation)问题到分子生物学中的基因序列问题，这里描述的基本方法已成为科学研究中的核心要素：而且从数据库系统到因特网搜索引擎，它们已成为现代软件系统的核心部分。随着计算机的应用范围越来越广泛，本书介绍的一些基本方法的影响也随之增大。对于那些有志于掌握这些基本算法，并且灵巧地利用它们作为将来所从事的计算机应用的基本工具的学生和专业人员，本书的目标就是作为他们实现理想的宝贵资源。
讨论范围
本书分16章，共4部分：基础知识、数据结构、排序和搜索。这里的描述是为了让读者对尽可能广泛的基本算法的基本性质有一个大概的了解。这里描述了从二项式队列到patricia trie等精巧方法，它们都与计算机科学核心中的基本范例相关。第二卷包括另外4部分，涉及串、几何体、图以及高级主题。我编撰这两本书的目的是，从不同的领域将这些基本方法汇集起来，为读者提供已知的通过计算机解决问题的最佳方法。
如果你选修过计算机学科中的一到两门预备课程，或者有过与之相当的编程经验，则会从本书受益最大。这些选修课程可以是一门高级编程语言，如C、Java或C++，也可以是讲述编程系统基本概念的课程。因而，本书面向那些熟悉现代编程语言以及现代计算机系统基本特征的读者。对正文中讲解的知识，读者通过参考文献可以进一步详细了解。
大部分支撑本书分析结果的数学内容都是独立的(或者作为超出了本书的讨论范围而标记出来)，因此，学习本书需要很少的数学预备知识，当然，深厚的数学造诣对学习过程无疑是有益的。
如何在课程中使用
根据老师的教学方法上的差异以及学生的预备知识的多寡，讲授本书的方式可以灵活多变。这里描述的算法多年来得到了广泛的应用，而且代表着熟练程序员以及计算机科学学生的核心知识面。本书包含了很多的数据结构方面的基本内容，因此，可以用于数据结构课程的教学。本书也对算法进行了相当详细的讨论，并提供了足够的高级内容，因此，也可以用于算法课程的教学。一些老师可能希望重点讲解实现以及实际应用上的问题，另外一些老师可能希望重点讨论分析和理论概念。
在本书的主页上，可以找到用于授课的整套幻灯片、示例编程作业布置、学生使用的交互练习以及其他一些材料。
数据结构和算法的基本课程可以重点讲解第二部分中的基本数据结构以及第三、四部分中在实现里的运用。算法设计和分析课程可以重点讲解第一部分和第5章中的基本内容，然后学习第三部分和第四部分中的算法，学习这些算法是如何达到好的渐近性能的。软件工程课程可以忽略数学和高级算法内容，重点讲解如何在大型程序或系统中集成书中提供的实现。算法课程对于所有这些内容，可以采取综述、简介的方式来讲授。
近几年，全球很多院校使用本书的旧版本作为计算机科学的第二或第三门课程教材，同时也作为其他课程的辅助阅读内容。在普林斯顿大学，我们的教学经验是，本书所囊括的内容可以作为主修课的计算机科学导论，在算法分析、系统编程以及理论计算机科学等后续课程上可以进一步深入，同时，还为其他学科中不断增长的学生群体提供丰富的技能，他们可以将这些技术立即完美地付之于实践。
书中的练习分为几类(在新版本中，大部分练习为新添加的)。有些练习是为了测试读者对课文内容的理解，只是要求读者完成一个例子，或者应用正文中描述的概念。有些练习包括实现代码和算法的综合，或者通过试验研究比较算法的变种，并学习其性质。还有一些练习提供了许多重要而详细的信息，这些信息不适合于在正文中讲解。每位读者阅读和思考这些练习都会有收获。
算法的实用
任何希望更高效使用计算机的人都可以将本书作为参考书，或者用于自学。具有编程经验的人在全书各章节都可以找到特定主题的有用信息。虽然在某些情况下，某一章中的算法可能借用前面章节的方法，但在很大程度上，读者可以独立阅读各章节。
本书的目标就是学习那些可能运用于实践的算法。它提供了足够的信息，读者可以胸有成竹地运行、调试程序，并且获得有效算法来解决实际问题，或者为应用程序提供功能。书中提供了所讨论方法的完整实现代码，描述了一系列相关联的例程中的运算。因为我们提供的是实际代码，而不是伪码，所以这些程序可以直接运用于实践。在本书的主页可以下载所有程序源代码。
实际上，在整本书中，为每个算法都展示了实际应用，并且配制了相关的数百幅说明图示。通过这种直观的演示说明，许多算法变得浅显易懂。
书中详细讨论了这些算法的特征和它们可以发挥作用的场合。算法分析和理论计算机科学的联系虽然不是重点内容，但也在本书中安排了适当的篇幅进行讲解。适当的时候会引用试验和分析结论，来说明优先选择某些算法的原因。必要的时候，书中还会描述所讨论的实际算法与纯理论结论之间的关系。本书自始至终地综合、归纳和探讨了算法及其实现的性能特征的专门信息。
编程语言
我全部重写了新版内容，添加了1000多个新练习、100多幅新图以及许多新程序。我还为所有插图和程序添加了详细的注释。这些新材料既包含了一些新主题，还对许多经典算法提供了更全面的解释。整本书还添加了一个重点内容，即抽象数据类型，使得这些程序更加通用、更适应于现代面向对象编程环境。阅读过本书旧版的读者在新版中可以学到大量新知识；所有读者都可以阅读到丰富的教学材料，通过它们可以快速掌握一些重要概念。
由于添加了大量新材料，所以将新版分为二卷，每一卷都与旧版篇幅相当，本书为第一卷。这一卷包括基本概念、数据结构、排序算法以及搜索算法；第二卷在本书基本抽象和方法的基础上讲解高级算法和应用。在新版本中，几乎所有基础知识和数据结构的材料都是新的。
本书所面向的对象并不仅仅是程序员和计算机专业的学生。几乎每个计算机的使用者都希望计算机能够进行得更快或者能够解决更大的问题。本书中的算法代表过去50年的知识发展水平，针对各种不同的应用，在高效使用计算机中不可或缺。从物理学上的N-体模拟(N-body simulation)问题到分子生物学中的基因序列问题，这里描述的基本方法已成为科学研究中的核心要素：而且从数据库系统到因特网搜索引擎，它们已成为现代软件系统的核心部分。随着计算机的应用范围越来越广泛，本书介绍的一些基本方法的影响也随之增大。对于那些有志于掌握这些基本算法，并且灵巧地利用它们作为将来所从事的计算机应用的基本工具的学生和专业人员，本书的目标就是作为他们实现理想的宝贵资源。
讨论范围
本书分16章，共4部分：基础知识、数据结构、排序和搜索。这里的描述是为了让读者对尽可能广泛的基本算法的基本性质有一个大概的了解。这里描述了从二项式队列到patricia trie等精巧方法，它们都与计算机科学核心中的基本范例相关。第二卷包括另外4部分，涉及串、几何体、图以及高级主题。我编撰这两本书的目的是，从不同的领域将这些基本方法汇集起来，为读者提供已知的通过计算机解决问题的最佳方法。
如果你选修过计算机学科中的一到两门预备课程，或者有过与之相当的编程经验，则会从本书受益最大。这些选修课程可以是一门高级编程语言，如C、Java或C++，也可以是讲述编程系统基本概念的课程。因而，本书面向那些熟悉现代编程语言以及现代计算机系统基本特征的读者。对正文中讲解的知识，读者通过参考文献可以进一步详细了解。
大部分支撑本书分析结果的数学内容都是独立的(或者作为超出了本书的讨论范围而标记出来)，因此，学习本书需要很少的数学预备知识，当然，深厚的数学造诣对学习过程无疑是有益的。
如何在课程中使用
根据老师的教学方法上的差异以及学生的预备知识的多寡，讲授本书的方式可以灵活多变。这里描述的算法多年来得到了广泛的应用，而且代表着熟练程序员以及计算机科学学生的核心知识面。本书包含了很多的数据结构方面的基本内容，因此，可以用于数据结构课程的教学。本书也对算法进行了相当详细的讨论，并提供了足够的高级内容，因此，也可以用于算法课程的教学。一些老师可能希望重点讲解实现以及实际应用上的问题，另外一些老师可能希望重点讨论分析和理论概念。
在本书的主页上，可以找到用于授课的整套幻灯片、示例编程作业布置、学生使用的交互练习以及其他一些材料。
数据结构和算法的基本课程可以重点讲解第二部分中的基本数据结构以及第三、四部分中在实现里的运用。算法设计和分析课程可以重点讲解第一部分和第5章中的基本内容，然后学习第三部分和第四部分中的算法，学习这些算法是如何达到好的渐近性能的。软件工程课程可以忽略数学和高级算法内容，重点讲解如何在大型程序或系统中集成书中提供的实现。算法课程对于所有这些内容，可以采取综述、简介的方式来讲授。
近几年，全球很多院校使用本书的旧版本作为计算机科学的第二或第三门课程教材，同时也作为其他课程的辅助阅读内容。在普林斯顿大学，我们的教学经验是，本书所囊括的内容可以作为主修课的计算机科学导论，在算法分析、系统编程以及理论计算机科学等后续课程上可以进一步深入，同时，还为其他学科中不断增长的学生群体提供丰富的技能，他们可以将这些技术立即完美地付之于实践。
书中的练习分为几类(在新版本中，大部分练习为新添加的)。有些练习是为了测试读者对课文内容的理解，只是要求读者完成一个例子，或者应用正文中描述的概念。有些练习包括实现代码和算法的综合，或者通过试验研究比较算法的变种，并学习其性质。还有一些练习提供了许多重要而详细的信息，这些信息不适合于在正文中讲解。每位读者阅读和思考这些练习都会有收获。
算法的实用
任何希望更高效使用计算机的人都可以将本书作为参考书，或者用于自学。具有编程经验的人在全书各章节都可以找到特定主题的有用信息。虽然在某些情况下，某一章中的算法可能借用前面章节的方法，但在很大程度上，读者可以独立阅读各章节。
本书的目标就是学习那些可能运用于实践的算法。它提供了足够的信息，读者可以胸有成竹地运行、调试程序，并且获得有效算法来解决实际问题，或者为应用程序提供功能。书中提供了所讨论方法的完整实现代码，描述了一系列相关联的例程中的运算。因为我们提供的是实际代码，而不是伪码，所以这些程序可以直接运用于实践。在本书的主页可以下载所有程序源代码。
实际上，在整本书中，为每个算法都展示了实际应用，并且配制了相关的数百幅说明图示。通过这种直观的演示说明，许多算法变得浅显易懂。
书中详细讨论了这些算法的特征和它们可以发挥作用的场合。算法分析和理论计算机科学的联系虽然不是重点内容，但也在本书中安排了适当的篇幅进行讲解。适当的时候会引用试验和分析结论，来说明优先选择某些算法的原因。必要的时候，书中还会描述所讨论的实际算法与纯理论结论之间的关系。本书自始至终地综合、归纳和探讨了算法及其实现的性能特征的专门信息。
编程语言
相关资源回到顶部↑
· 【推荐】众多高校学子口口相传，他们共同的选择--华清远见嵌入式学院(嵌入式Linux就业课程、3G手机开发就业课程，通过入学测试即签100%就业协议，4个月集中实训，世界500强企业成功就业保障！！！)· 【亚嵌教育 嵌入式培训专家】(嵌入式培训，嵌入式Linux培训，ARM培训,Linux培训，3G培训，Android培训，WINCE培训，DSP培训，FPGA培训，嵌入式就业培训)
· 程序员的7种武器(正则表达式、编程语言、数据库、算法、软件调试、开发环境)
· C/C++ 经典著作(《C专家编程》《C++ Templates中文版》《C和指针 》《C陷阱与缺陷》《C++沉思录》)
加载中...
