算法：C语言实现

出版时间：2009-10  出版社：机械工业出版社  作者：塞奇威克  页数：456  译者：霍红卫  
Tag标签：无  

前言

写本书的目的是为了对当今使用最为重要的计算机算法做一综述，并为需要学习这方面知识的越来越多的读者提供基础的技术。本书可以在学生掌握了所需的基本程序设计技巧，熟悉了计算机系统，但还未学过计算机科学或计算机应用高级领域的专业课程的时候，用作计算机科学的第二。第三或第四门课程的教科书。此外，由于本书包含了大量有用算法的实现，以及关于这些算法的性能特征的详细信息，因而它还可用于自学，或者作为从事计算机系统或应用程序开发人员的参考手册。宽广的视角使得本书成为计算机算法领域最合适的入门读物。对于新的一版，我不仅完全重写了它的内容，而且还添加了一千多个练习。一百多幅图表和数十个新程序。我还给所有图表和程序添加了详细的注释。新的素材不仅涵盖了新的主题，而且还包含对经典算法的更完整解释。抽象数据类型是这本书的重点，这使得程序应用更广泛，并且与现代面向对象的程序设计环境更紧密。读过本书旧版本的人一定会发现，新版本包含了更为丰富的新信息，所有读者将发现大量的教学资料为掌握基本概念提供了有效途径。由于新的素材数量过多，所以我们把新版本分为两卷（每一卷的容量都大约为旧版本的大小），本书是第一卷。这卷书中包含了基本概念。数据结构。排序算法和搜索算法，第二卷涵盖的高级算法及应用是以第一卷的基本抽象概念和方法为基础的。这个新版中的关于基本原理和数据结构的所有素材几乎都是新的。这本书不仅适合于程序员和计算机科学专业的学生，而且也适合于想利用计算机并想使它运行更快或是想要解决更大问题的人们。这本书中的算法代表了过去50年来所研究的知识主体。对于大量应用问题，这些知识主体已经成为有效使用计算机的不可缺少的部分。从物理学中的N-体模拟问题到分子生物学中的序列分析问题，在此所描述的基本方法在科学研究中已日显重要。另外，对于从数据库系统到Internet搜索引擎，这些方法已经成为现代软件系统的重要组成部分。随着计算机应用的覆盖面越来越广，基本算法的影响也日益显著。本书的目标是要提供一种资源，使广大学生以及专业人士可以了解并有效利用这些算法解决计算机应用中出现的问题。

内容概要

本书细腻讲解计算机算法的C语言实现。全书分为四部分，共16章。包括基本算法分析原理，基本数据结构、抽象数据结构、递归和树等数据结构知识，选择排序、插入排序、冒泡排序、希尔排序、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序方法，并比较了各种排序方法的性能特征，在进一步讲解符号表、树等抽象数据类型的基础上，重点讨论散列方法、基数搜索以及外部搜索方法。书中提供了用C语言描述的完整算法源程序，并且配有丰富的插图和练习，还包含大量简洁的实现将理论和实践成功地相结合，这些实现均可用在真实应用上。
本书内容丰富，具有很强的实用价值，适合作为高等院校计算机及相关专业本科生算法课程的教材，也是广大研究人员的极佳参考读物。

作者简介

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

书籍目录

出版者的话
译者序
前言
第一部分　基础知识
　第1章　引言
　 1.1　算法
　 1.2　典型问题——连通性
　 1.3　合并一查找算法
　 1.4　展望
　 1.5　主题概述
　第2章　算法分析的原理
　　2.1　实现和经验分析
　　2.2　算法分析
　　2.3　函数的增长
　　2.4　大O符号
　　2.5　基本递归方程
　　2.6　算法分析示例
　　2.7　保证、预测及局限性
第二部分　数据结构
　第3章　基本数据结构
　 3.1　构建组件
　 3.2　数组
　 3.3　链表
　 3.4　链表的基本处理操作
　 3.5　链表的内存分配
　 3.6　字符串
　 3.7　复合数据结构
　第4章　抽象数据类型
　 4.1　抽象对象和对象集
　 4.2　下推栈ADT
　 4.3　栈ADT客户示例
　 4.4　栈ADT的实现
　 4.5　创建一个新ADT
　 4.6　FIFO队列和广义队列
　 4.7　复制和索引项
　 4.8　一级ADT
　 4.9　基于应用的ADT示例
　 4.10　展望
　第5章　递归与树
　 5.1　递归算法
　 5.2　分治法
　 5.3　动态规划
　 5.4　树
　 5.5　树的数学性质
　 5.6　树的遍历
　 5.7　递归二叉树算法
　 5.8　图的遍历
　 5.9　综述
第三部分　排序
　第6章　基本排序方法
　　6.1　游戏规则
　　6.2　选择排序
　　6.3　插入排序
　　6.4　冒泡排序
　　6.5　基本排序方法的性能特征
　　6.6　希尔排序
　　6.7　对其他类型的数据进行排序
　　6.8　索引和指针排序
　　6.9　链表排序
　　6.10　关键字索引统计
　第7章　快速排序
　 7.1　基本算法
　 7.2　快速排序算法的性能特征
　 7.3　栈大小
　 7.4　小的子文件
　 7.5　三者取中划分
　 7.6　重复关键字
　 7.7　字符串和向量
　　……
　第8章　归并与归并排序
　第9章　优先队列和堆排序
　第10章　基数排序
　第11章　特殊用途的排序方法
第四部分　搜索
　第12章　符号表和二叉搜索树
　第13章　平衡树
　第14章　散列
　第15章　基数搜索
　第16章　外部搜索

章节摘录

插图：还有一个例子出现在某种程序设计环境中，连通性可用来断言两个变量名是否等价。问题是在经过这样的断言序列之后，能够确定两个给定的名字是否等价。这个应用激发了我们打算考虑的几个算法的研制。它直接将我们的问题与一种简单抽象关联起来，为使算法具有广泛应用而提供了一种方法。我们即将看到这一点。像上一段描述的变量名等价问题这样的应用程序要求我们把每个不同的变量名与一个整数关联起来。这种关联关系也隐含在前面描述的网络连接和电路连接的应用中。在第10章至第16章，我们将会以一种更高效的方法考虑提供这种连接关系的大量算法。因此，不失一般性，本章假设有N个对象，每个都与0一N一1之间的一个整数名对应。我们正在寻求完成特定和良定义任务的程序，可能还想要解决其他许多相关的问题。在研制算法时我们面对的首要任务之一是确信我们已经以合理的方式指定了问题。我们要求算法的越多，它完成任务所需要的时间和空间越多。不可能量化这个关系，并且我们在发现一个问题难以求解或是求解代价昂贵，或是在好的情况下，发现算法可以比原始说明提供更多有用的信息时，我们常常修改这个问题的说明。例如，我们的连通问题的说明只要求我们的程序知道任意给定对p—q是否是连通的，并不能够表明连接那个对的任何方式。添加这样一个说明的要求会使问题更加困难，会涉及其他的算法，我们将在第5章简略讨论，并在第7章详细讨论。前面这段提到的说明要比原始说明要求更多的信息，我们也可以要求更少的信息。例如，我们可能只想回答这样的问题：“M个连接足以把Ⅳ个对象都连接起来吗？”这个问题表明，要研制一个高效的算法，常常需要我们对正在处理的抽象对象进行高级推理。在这种情况下，由图论基本结果可以得出所有Ⅳ个对象是连通的，当且仅当连通算法输出的对的个数恰好为N一1（见5．4节）。换句话说，连通算法永远不会输出多于N一1个对，这是因为一旦它输出N一1个对，则它从那个时刻遇见的任何对将会是连通的。因此，我们可以修改求解连通问题的程序，增加一个计数器就可以得到一个回答yes-no问题的程序，而不输出那些前面不连通的每个对，当计数器的值为N-1时，程序回答“yes”，否则回答“no”。这个问题只是我们希望回答关于连通性的许多问题中的一个例子。输入对的集合称为图（graph），输出对的集合称为图的生成树，它连接了所有对象。我们在第七部分考察图、生成树以及所有相关算法的性质。

媒体关注与评论

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

用户评论 (总计113条)

•   计算机最核心的就是算法，数据结构
•   算法实现的经典书籍。要是能把这一本书和另外一本图论结合到一起的书就好了。内容和算法导论比比较简单，容易懂。和程序设计艺术比就更简单了。推荐算法入门者读，多多练习才是王道嘛。
•   首先送书很快，让我异常惊讶，书的内容很棒，一般在学习算法方面的内容的图书的时候都会被大量的数学分析而吓跑，而这本书不会，作者以其独到的笔锋带你进入另一个算法的世界
•   想要研究一下算法的C语言实现，所以就买了这边书。
•   本书是一本非常专业的书籍。难度有点大。但是认真研究完后确实能够提高你的数据结构的运用能力。这本书要慢慢地品味，切不可马虎。但是本书的价格确实贵了一点。而且还将图的部分分到另一本书上面，明显是为了赚钱，因为本书根本不厚。经典书籍有很多，但是知识也是有价的啊。
•   算法：C语言实现
•   个人比较笨一点，对伪代码实现的算法，有些看不懂，所以就买了这本书，没想到这本书讲的如此详细，让我受宠若惊
•   很优秀的书，看过前三章，感觉它可以超越我看过的任何算法书籍
•   很经典的算法解析类的书，是程序员必备
•   这本书很经典，将各种算法通过具体的事例来进行讲解，加快了学习的速度
•   对算法很有帮助，尤其是学习C语言的同学
•   感觉没有算法导论这本书写的好,但是有兴趣的买来看看吧
•   翻译得还不错，关于数据结构很不错的书，要继续读下去
•   算法经典书，值得一看
•   一本值得收藏的算法书。
•   很经典的算法教材哦
•   比起严蔚敏所谓的数据结构至少算是好书了
•   最近在学习算法，这么一本书很值得学习。
•   不错，看过电子书觉得不错才买的，算法中不错的书吧
•   大致上用C语言描述伪代码，值得仔细地研究
•   我是配套买的，虽然计算机二级过了，但是嘛，学的毕竟是皮毛，所以想认真钻研一下，书确实不错，不愧为经典之作！！！
•   学长推荐的书，代码部分非常经典，值得一读！
•   看书必看经典，这名话还是很有价值的。在历史的磨练下，很多书只是一时红火，而真正的经典留了下来。这本书就是其中之一，感慨的是，国内许多所谓大作占用发展基金，到头来很多却是滥竽充数的货色。我认为只有用心之作才能得到读者的真正欢迎。
•   实现很好，对自己帮助很大，实用
•   纯C的代码，不像清华版的都是vc，上机直接运行
•   C语言写的很好
•   很经典的书 适合初学者,只是有些贵了
•   这本书的包装碉堡了，书的外面还有一层膜。
•   书看起来不错，不适合初学者
•   书挺不错，挺经典，不过没太怎么看，送人了
•   书还没看，内容不评论。书质量很好，包装也很认真，印刷很清晰，很满意。赞一个当当的快递员，服务态度真的没话说。
•   书很好，内容需要自己仔细的推敲
•   不用怀疑很好的书
•   挺有用的书 工具必备
•   国外的书，很不错。
•   书的质量很好，对自己很有帮助
•   回过头再重新掌握基础的东西，才能有提高
•   写得很好，不过有些难。初学编程者不太适合学习。
•   东西是正品的。内容不好说，是外国人写的东西，不像中国人写的好理解，主要是让人去思考。
•   我才刚看这本书，内容有待以后再说，印刷很清楚，不足是纸薄了点
•   这本书是我转战互联网的智囊
•   本书确实很好！但是有些细节翻译的不够完美
•   图文并茂 物超所值 值得仔细研究
•   非常不错，非常适合初学者学习
•   有点深奥，但经典来的
•   先去图书馆借了看，感觉不错，买了一本，就可以在上面做笔记了！
•   书不错，值得一看，我是拿来收藏的
•   收货很快，目视不错哦，希望收获可以很多
•   同事说不错哦
•   买到的书籍都是新的，没有损坏，发货速度也非常快，非常满意
•   包装挺好的，还没看，应该不错
•   同事要求买的，看起来挺好的
•   不多说了，给好评
•   好书 值得研究
•   买来自己查阅的
•   做工挺好， 字体清晰。
•   不过还是谢谢了
•   一直收藏着等下册一起买呢，口碑好
•   女儿说现在还用不上，要到下学期。
•   买了几次，质量都很好，人品看来不错哈
•   唉,写什么呢好书呗
•   值得一看，让我受益匪浅。
  
  
  
  
  
  
  
  
  
  
•   是一本好工具书。
•   该书应该还算是不错啊
•   不错，就是课后习题如果有答案对照一下 就更完美了
•   希望大家都多关注
•   还不错，看了一段时间
•   对初学者有点难，不过确实是好书哦
•   挺好的，给同事买的，看起来挺不错的。
•   因为对算法和数据结构了解不是很好，这本书比较基础，所以感觉不错的……
•   这本书把算法原理讲解的很透彻，有些人喜欢TAOCP，个人认为TAOCP太过理论，如果要是偏重使用性还是这本书好些，读过这本再去读TAOCP就没有那么艰涩的感觉了
•   有点贵，但是本书总体编写还是非常不错的。可以当作算法设计的入门经典
•   经典算法理论，送货速度也挺快，纸的质量有待提高
•   这个是给有经验的c语言开发者看的，我发现我看起来很吃力，新手初学者应该不要买。里面的内容真的很好，很紧凑，就算看不透彻也觉得值了，值得收藏。
•   还在初级阶段，一点一点的看。书的内容十分经典。
•   书没得说，就是有点贵，本来以为特别厚呢，谁知道才400多页。
•   书很好，是正版 ，就是纸张有点薄
•   书还行，大概翻了下，文字过多，代码过少。
•   看过 不错 值得拥有
•   好书啊。。值得研究
•   逻辑思想表述不错！
•   和K的经典相比，可以作为速查
•   内容很好，毋庸置疑，翻译确实不咋地，要发挥想象力
•   刚寄过来时有点破损，别的都好。找了很久，就是没找到英文版的，早就听说翻译不是很好，看的时候确实有困惑的地方。但是，又一想，译者的水平总比我高。
•   书本身的质量不错，送货速度也快，如果时间充裕的话还是建议读英文版的吧，翻译的确不敢恭维，总感觉别扭
•   就是翻译得有点难懂
•   好书，需要静下心来看
•   还可以 还在看
•   算法方面的参考书，没看呢还
•   原书应该不错，霍红卫翻译太差了
  买了高教出的计算精髓（第3版）也是被他给糟蹋了！
•   本来书是看内容。但是当我把袋子打开后，发现书的封面有很多折痕。感觉这本书好像被损坏过。
•   经典书，好好学习中！
•   这是一本非常棒的书，因为我看过算法导论了，所以看这本书感受特深，更加贴近实际，很多工程化的考虑。但是，这本书翻译极其烂，我不是耸人听闻，我曾经花了不到三天读完head first那本七百多页的设计模式，但是这本书我花了三天才刚读完前三章！歧义非常多，错字、落字，你一句话说不明白，你分几句话讲也行啊，各种复合结构的句式，非常复杂，断句麻烦的比读原版还累！！更不要提那些翻译错误了！！翻译的极其烂，比我上两天吐槽的那本python基础教程翻译的还要烂！而且又烂的升了级！！！强烈大家读原版书，相信我，读原版也比读这个人翻译的容易！
•   都是一些很好的基础书籍，有很都实用性很强的例子，是一本入门的好书。
•   书的内容还是不错的...但是有些地方翻译的很突兀，翻译不给力；代码也存在部分错误；不过耐心看下去还是很有收获的.....
•   书来了，大概翻了一下，翻译确实有点问题，不过内容还是不错的。but！！！！书的特点说有一千多道的练习题，但是没有答案。连参考答案都没有，翻遍了百度和google都没有，我有种蛋蛋的忧伤。
•   个人怀疑该书是分段承包翻译的，有的章节好，有的章节烂
•   就是翻译的不太好，其他的都很好。
•   这次的书，头天晚上定的，第二天中午就到。书的印刷质量很好，内容也很经典，正在看。
•   学习c语言算法,必读之作