算法：C语言实现

出版时间：2006-9  出版社：机械工业出版社  作者：塞奇威克  页数：702  
Tag标签：无  

内容概要

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

作者简介

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

书籍目录

Contents  Chater 1.Introduction    1.1  Algorithms    1.2  A Samle Problem-Connectivity    1.3  Union-Find Algorithms    1.4  Perspective    1.5  Summary of Topics  Chapter 2.Priciples of Algorithm Anaylysis    2.1 Implementation and Empirical Analysis    2.2  Analysis of Algorithms    2.3  Growth of Functions    2.4  Big-Oh notation    2.5  Basic Recurrences    2.6  Examples of Algorithm Analysis    2.7  Guarantees,Predictions,and LimitationsData Stuctures  Chapter 3.Elementary Data Structures    3.1  Building Blocks    3.2  Arrays    3.3  Linked Lists    3.4  Elementary List Processing    3.5  Memory Allocation for Lists    3.6  Stuings    3.7  Compound Data Sturctures  Chapter 4.Abstract Data Types  Chapter 5.Recursion and TreesSorting  Chapter 6.Elementary Sorting Methods  Chapter 7.Quicksort  Chapter 8:Merging and Mergesort  Chapter 9:Priority Queues and Heapsort  Chapter 10:Radix Sorting  Chapter 11:Special-Purpose SortsSearching  Chapter 12.Symbol Tables and BSTs  Chapter 13.Balanced Trees  Chapter 14.Hashing  Chpater 15.Radix Search  Chapter 16.External SearchingIndex

媒体关注与评论

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

用户评论 (总计59条)

•   本书将基础的数据结构和相应算法都解释得很详细，作者的解释是一种引导性的，很适合初学者
•   对算法与数据结构讲解的很透彻，是一本值得仔细阅读理解的好书。
•   看这本书会比更容易理解数据结构，书中代码也都是c的实现
•   东西讲的很清楚，但是代码中有些不太好习惯，很是就开始了ADT介绍其实知道ADT才知道头文件的作用，。。。。
•   质量一般，内容不错
•   还是这本好
•   可以接受的价格！书本内容很好！值得购买！
•   这本书很适合程序员参考，书中的代码很经典。
•   印的着实粗糙~字体看上去不舒服
•   书的内容不错，书的质量真的不咋的，而且，英文看得压力本来就大，现在看得就是难受了。。。。
•   　　将算法，算法代码居然是错误的，我晕死
  　　第5章递归与树
  　　程序5.12背包问题
  　　
  　　int knap(int cap);
  　　谁看过这个算法？完全不正确......
  　　
  　　
  　　求推荐，中文算法书，要求算法代码绝对无错误的，谢谢
  　　
•   　　手头有国外的英文版3rd eidition，也有机械工业的中文版3rd eidition。可是为什么中文版比英文版薄了好多？
  　　
  　　看过国内的英文版，或者国外英文版的同学谁能说一下，是不是翻译版有删减啊。
  　　
  　　我没仔细看，红黑树那一节，我的英文版有12页左右，可是中文版大概只有7页。
  　　
  　　没人发现这个问题吗？
•   　　　　花了四个月时间，终于将此书第1-4部分读完了，放下书的那一刻无比高兴哈哈。
  　　　　Robert Sedgewick老爷子真不是盖的，对算法的讲解清晰易懂，C语言程序简短紧凑，令人称绝，实际上很多算法实现堪称完美：红黑树的插入，Batcher odd-event sort，汉诺伊的递归结构，背包的DP，快排的划分，原地归并，……你很难能再去减少一行或省去一个循环。自己写过那么多年的C程序，也只能叹息无法达到这种准确、精炼、紧凑同时做到极高标准的水平。话说这书还是1997年出版的呢。
  　　　　跟《算法导论》做个小比较：《算法导论》讲太多算法性能分析和数学证明了，对更注重工程的一般软件人员，这本算法书明显更合适。
  　　　　唯一可惜的是，书里经常提到的第5部分字符串算法一直没有出版，实际上出版的第5部分是图算法，不知道他老人家还有没有精力把那部分也
  　　　　结论：可手边常备:-)
  　　
•   　　美国大学本科生课程“Algorithm and Data Structure”的指定教材，我偷懒，下了中文版来看，实在是忍不了翻译，看回英文版。明明很简单的一句话能叫译者说的不明所以。真是译成这样不如不译啊。。。
•   　　翻译质量较差，像是未加任何处理的英文直译，不符合中文阅读习惯，另有不少不知所云的地方。如188页的《6.10 关键字索引统计》中有这样的叙述：“一种方法是计算0的个数，然后再次扫描输入a，使用两个表示统计数的一个数组，把元素分布在临时数组b中。”。为了不影响阅读，我一般都直接看代码（有些代码也有bug，如172页程序6.5 希尔排序的实现）。。。。挺影响阅读心情的
•   　　Prof. Sedgewick is a noted authority on searching and sorting algorithms, and a former student of Knuth's. The text is authoritative, lucid, and detailed. It is also full of mistakes, poorly edited, and much of the code has serious and not so serious bugs.
  　　不说算法的好与坏，至少做到正确，不误人子弟吧，代码中充斥着bug，加上折磨人的翻译，难道非要自虐不成吗？
•   　　书是相当的好，翻译的超级的烂啊，感觉是直译的，直接按照英文单词顺序翻译过来的，还有翻译错误的地方，简直无语了，拿本词典自己看也比看中文的强。 还建议看看那本算法分析导论，数学知识比较多，写的很好，不愧是算法大师和算法大师的高徒啊，呵呵。
•   　　也许关于算法方面的最大的误解，就是没有意识到它是由关系密切而又非常不同的两个部分组成的。
  　　
  　　对于一个给定的问题，选择哪一种算法才是最适合的？选定算法之后，在编程环境中又是如何实现这个算法，是使用已有的库还是自己从头开始编写，是用 X 语言还是 Y 语言？这个算法实现和已有的程序结合得如何，需要对它进行修改吗？它的实际运行速度是快是慢？
  　　
  　　以上这些，都是算法在实现阶段需要考虑的问题，这些问题主要是和工程相关的，是大部分编程人员日常工作中最常见也是最重要的部分。
  　　
  　　另一方面，设计一种崭新的算法，或者改进一个已有的算法，并对这个算法进行严密的分析以研究其性能特征，将它和已有的算法进行对比以判断孰优孰劣，等等，这些问题主要是和数学相关的，由一些算法 Guru 和研究人员（在守卫森严的科技大楼内秘密地）进行。
  　　
  　　当然，将算法简单地划分为实现和设计/分析两部分有点过于简单化了，因为它们实际上是无法分割的一个整体，比如说，离开分析的话，我们又怎么能确定算法的效率呢？而离开了效率的话，也就无所谓算法了，因为如果不考虑时间和空间效率的话，那么问题的任何一个正确的解就足以解决所有问题了。
  　　
  　　不过，即便如此，我们也应该注意到，目前被广泛使用的绝大部分算法，都已经经过了详细而透彻的分析了，在很多时候，编程人员要做的就是根据已有的算法资料，选择一个合适的算法，然后实现它，这就完了，至于对算法进行分析的场景，一般来说也就非常少了。
  　　
  　　如果对前面的几段话做一个总结，我们就得出了一个结论：比起学习算法分析，学习算法实现的相关知识要来得更有用和更实用。
  　　
  　　然而，不幸的是，市面上销售的大部分算法书籍，以及人们推荐得最多的算法书籍，基本都是以算法分析为主，在这类算法书中，一个个优美的算法被分解成支离破碎的数学研究对象，在这些书里面，你会看见严谨的数学论证，完整的数学分析和（数学家写算法书赚外快时最喜欢用的难看的）伪代码，但是却看不见从低效算法逐步向高效算法推进的求精过程，看不见不同算法/数据结构之间的相似性和差异性，因为它们都被小心地隔离开来了。
  　　
  　　这本《Algorithms in C》最难能可贵的地方就是，它是一本关注算法的实现和实用性的算法书：书中的示例程序使用的都是真实可运行的 C 代码；它详细地讲解了很多实际使用算法时会遇到的问题，比如说，内存占用、浮点数、随机算法的安全性和库的移植等问题；它还给出算法的完整的 API 和 client 端示例，并列出算法的实验分析结果，配合简短的描述来完整地展示算法的运行效率。
  　　
  　　以上这些，都是算法在实际应用中需要关注的问题，但是，即使抛开这些实用性优点不说，这本书也是一本写得非常好的算法书：书中使用了大量的图片和图表来演示算法的完整执行过程，并且章节的安排也非常合理，新内容可以很自然地引申出来，沿着书一直读下去可以看到如何对一个算法进行改进，从低效到高效，再到最优化，这是学习算法中最有趣而又最能体现算法之美的地方，而这些有趣的部分，在那些将算法分解得支离破碎的算法分析书中，是不可能看到的。
  　　
  　　---
  　　
  　　补充：
  　　
  　　似乎有部分评论说这本书的翻译不好，这套书的中文版和英文影印版我都有，我觉得这本书的翻译蛮不错的，也没发现什么明显的错误。
  　　
  　　而且这套书原文的倒装句比较多，读起来比较慢，我个人还是推荐买中文版。
•   　　用图示化方式说明算法的特点，是本书的一大特色。
  　　只是翻译者实在是欠骂，这么垃圾的翻译还不如不译，糟蹋了这么好的一本书！！
  　　封面上都写上你的名字了，都不怕遭人骂吗？！
  　　留给别人翻译多好啊！！
•   　　作者的主页上好像也找不到，只有书中的code和errta（话说我提交的edition3 的一个error貌似也无人理睬。）不知道有没有人愿意讨论下里面的习题？我刚看到栈那里。
  　　
  　　这个评论到底要多长才行……
•   　　P32 表2-4
  　　“当M增加一倍时，顺序搜索的时间也增加一倍，但二分搜索几乎不变”
  　　
  　　其中M当为N。
  　　
  　　因为顺序搜索的时间复杂度跟MN正比而二分搜索跟MlogN正比，显而易见M增加时两种算法耗时均线性递增。
  　　
  　　嗯，我的评论很短么？居然不让发表？？好吧，我刷个屏看看。
  　　刷屏刷屏刷屏刷屏刷屏
•   　　除去图算法，第一至第四部分页数不多，但是内容详实。学算法最需要的是什么？是想象力！想象数据结构在内存中是如何变化的，查看其中的奥秘学习其中的思想。可是算法难学啊，因为有些复杂算法不好想象。这本书从数据结构到排序到搜索，介绍了每个分类里面的几大经典，各个都有配图，比如原位排序的数值调整，二叉搜索树的旋转平衡，都有配图详细说明。　　书虽不厚，但是经典的都写到了，而且言简意赅通俗易懂。快速排序、堆排序、归并排序等常用排序，二叉搜索、红黑树、哈希表、Trie树、外部搜索，面面俱到。内容详实，配图生动，非常难得的一本好书，五星推荐。
•   　　书是好书，不过还是推荐看原版的，翻译得实在。。。而且明显感觉不同的章节是不同的人翻的，虽然只写了一个译者
•   　　在小百合算法版看到 ufx222 对这本书的评价才注意到这本书。引用他的评价：
  　　
  　　“只推荐C语言的版本；而且不推荐看中文版，中文版翻译得非常之差。这是一本非常重视算法实现的书，即使是资深的优化程序的人也不会对Sedgewick的C程序有不满。作者对于基本算法都给了很多很多形象的图示。”
  　　
  　　看这本书前言的时候注意到作者 Robert Sedgewick 是 Knuth 的学生。
  　　
  　　当参考书看过书中的几段，如 quicksort, merge-sort, binary search tree, red-black tree。书中算法的实现的确很精巧。比如 merge 的实现，书中使用的方法在拷贝数组时，将其中一个数组反序拷贝，这样合并时就可以很方便的处理数组边界。介绍过 2-3-4 tree 以后再介绍了 red-black tree，通过将这两者联系起来使读者更容易理解 red-black tree 的思想。在 balanced search tree 一章末尾还有各种平衡搜索树在实际使用中性能的比较。我就是看到这个才明白 C++ STL 中的 map 等数据结构为什么使用 red-black tree 而不使用其他的平衡搜索树。
  　　
  　　看过的只是书中的一小部分，但已经感受到本书对算法实现的重视，有不少漂亮的 trick。书中实现的代码可以从作者网站上下载。
•   请问英文版在哪买的？
•   我在taobao上找的打印版，eng原本，不是机械他们的出的。大概70rmb吧。
•   四个月？
  看我能不能用四个月把这个本书看完。
•   没错，直接读代码更好，看文字很郁闷...
•   英文原版的已经看到500多页，没遇到很多bug。
  Prof. Sedgewick is a noted authority on searching and sorting algorithms, and a former student of Knuth's. The text is authoritative, lucid, and detailed. 对。
  It is also full of mistakes, poorly edited, and much of the code has serious and not so serious bugs. 错。
•   其实说白了就是学术也给工业的区别。不同目标的方向和侧重点都不同
•   看完第一章併查集，我就被惊呆了，還不說那些NB的配圖~~(>_<)~~
•   《图算法》还有一个优点，Sedgewick一直在书中引导读者去思考各种图算法的共性，在更高的层次上统一地看待图算法
•   @Silverbullettt
  《图算法》我还没怎么读，但是有这本书的保证，还是很值得期待的。
•   推荐 Algorithms 4th edition，算是本书的“升级版”（虽然示例代码全变成了 Java 比较悲剧
•   我怎么觉得读起来难受的很,不通顺
•   你们读过么？？ 就乱评价
•   翻译之烂已经到了无法忍受的地步，我就想知道用谷歌翻译还会比这更烂么，这个叫霍红卫的大博导的母语是不是汉语，还是她翻译之后根本就没勇气再自己审一遍。
•   神一般的翻译
  我看哭了
  如果有空真该直接看英文的
•   是啊，逼我们不得不学好英语啊
•   英文版本的哪有卖啊???????????
•   第一章，第一段就看不懂，句子p也不通。
•   嗯，这个错是中文版里的，我手头无英文版的c版本，下载了一个c++的，该版本无此问题。
•   别挑了，我拜读了这位大姐翻译的《图算法》，里头N多小错误。。。
•   不过书是好书！我很喜欢，塞吉威克老哥的书代码很漂亮
•   嗯，对于我这种看不进去算法导论的人还是挺适合的……
•   据说翻译不太理想。呵呵。有原文电子版么？
•   我也想求英文电子版
•   谷歌学术里面都有
•   我也这么觉得，中文版的有时感觉那个句子实在太别扭了
•   我也很想说，刚看几页实在受不了了...
•   听你说这么说，果断买一本
•   谢谢你的评论
•   昨晚刚买了中文版的....
•   为什么只推荐c版的，java版的怎么样？
•   唉，买了中文版的了，读了前几页，觉得有点别扭。。。
•   我非常非常喜欢这本书的代码实现，Sedgewick真是了不起
•   出第4版了，java的
•   能看英文版的就别看中文版的吧；翻译版的通常比较烂。
•   只看了前面一点 目前看了不少数学方面的习题 很不满 额