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

作者：(美国)塞奇威克(Robert Sedgewick) 译者：霍红卫 　
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 下推栈ADT78
4．3 栈ADT客户示例79
4．4 栈ADT的实现84
4．5 创建一个新ADT87
4．6 FIFO伫列和广义伫列90
4．7 複製和索引项95
4．8 一级ADT99
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．1 0关键字索引统计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 优先伫列ADT244
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 随机化BST345
13．2 伸展BST350
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 多路线索和TST419
15．5 文本字元串索引算法430

第16章 外部搜寻434
16．1 游戏规则435
16．2 索引顺序访问436
16．3 B树438
16．4 可扩展散列447
16．5 综述455

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

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