C算法（第一卷 基础、数据结构、排序和搜索）

本书旨在综述当今程序员使用的最重要的计算机算法，同时为越来越多要学习这些算法的人讲解基本技术，本书可以用作学习计算机的科学的第二、第三或第四课程的教科书，供那些掌握了基本编程技能并熟悉了计算机系统，但还未学习计算机科学或着计算机应用的高阶领域专业课程的学生来选修，本书也可以作为从事计算机系统应用程序形象发的自学教材或参考书，因为它包含有用的算法的实现以及这些算法性能特征的详细信息。本书讲解全面，也是一本合适的算法导论书。RdbertSedgewick斯坦福大学博士，普林斯顿大学计算机科学系的教授，AdobeSystems公司董事。曾是XeroxPARC的研究人员，也曾就职于美国国防部防御分析研究所以及INRIA。《C算法》介绍了当今最重要的算法，共分3卷，本书是第1卷。第1卷分4部分、共16章。第一部分“基础知识”（第1～2章）介绍了基本算法分析原理。第二部分“数据结构”（第3～5章）讲解算法分析中必须掌握的数据结构知识。主要包括基本数据结构、抽象数据结构、递归和树。第三部分“排序”（第6～11章）按章节顺序分别讨论了基本排序方法（如选择排序、插入排序、冒泡排序、希尔排序等）、快速排序方法，归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊目的排序方法，并比较了各种排序方法的性能特征。第四部分“搜索”（第12～16章）在进一步讲解符号表、树等抽象数据类型的基础上，重点讨论哈希方法、基数搜索以及外部搜索方法。书中提供了用C语言描述的完整算法源程序，并且配有丰富的插图和练习。可作为高等院校相关专业的教材和补充读物，也可供自学之用。

　　译者：周良忠畅销图书《C++实践之路》的译者周良忠，1970年生。本科毕业于武汉化工学院计算机应用专业。1995毕业于中国科学院武汉岩土力学研究所，获硕士学位，1997年获得博士学位。1998年创办云巅工作室（http：//www.cloudcrown.com），为个人、中小企业提供专业软件定做服务。近几年开发了多款广受欢迎的共享软件。精通C++、C#、Java、Perl等开发语言。2001年开始从事计算机科技图书的创作和翻译工作，最新翻译力作有《C#PrimerPlus中文版》、《C++实践之路》等。SymbianOS软件开发开发：应用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
练习  38
2.6  算法分析示例  39
练习  43
2.7  保证、预测与限制  44
练习  46
第一部分参考文献  47
第二部分　数据结构
第3章  基本数据结构  49
3.1  基石  50
练习  57
3.2  数组  57
练习  63
3.3  链表  64
练习  69
3.4  基本表处理  70
练习  77
3.5  表的内存分配  77
练习  80
3.6  串  80
练习  84
3.7  复合数据结构  84
练习  92
第4章  抽象数据类型  93
4.1  抽象对象与对象集合  95
练习  97
4.2  下推栈ADT  97
练习  99
4.3  栈ADT客户程序示例  99
练习  104
4.4  栈ADT实现  105
练习  108
4.5  创建新ADT  109
练习  111
4.6  FIFO队列及广义队列  111
练习  117
4.7  重复项和索引项  118
练习  121
4.8  一级ADT  122
练习  130
4.9  ADT应用示例  131
练习  134
4.10  展望  135
第5章  递归和树  136
5.1  递归算法  136
练习  141
5.2  分治  142
练习  155
5.3  动态规划  156
练习  160
5.4  树  163
练习  168
5.5  二叉树的数学性质  169
练习  171
5.6  树遍历  172
练习  175
5.7  递归二叉树算法  177
练习  181
5.8  图遍历  182
练习  187
5.9  展望  188
第二部分参考文献  189
第三部分　排序
第6章  基本排序方法  191
6.1  游戏规则  192
练习  195
6.2  选择排序  196
练习  197
6.3  插入排序  198
练习  199
6.4  冒泡排序  200
练习  201
6.5  基本排序的性能特征  201
练习  206
6.6  希尔排序  206
练习  212
6.7  其他数据类型的排序  214
练习  217
6.8  索引与指针排序  218
练习  223
6.9  链表的排序  223
练习  225
6.10  键索引计数  226
练习  228
第7章  快速排序  229
7.1  基本算法  229
练习  233
7.2  快速排序的性能特征  233
练习  236
7.3  栈大小  236
练习  239
7.4  小子文件  239
练习  240
7.5  三元素中值法划分  242
练习  245
7.6  重复键  245
练习  246
7.7  串和向量  248
练习  249
7.8  选择  249
练习  251
第8章  归并和归并排序  253
8.1  二路归并  254
练习  255
8.2  抽象就位归并  255
练习  256
8.3  自顶向下归并  257
练习  259
8.4  基本算法的改进  259
练习  261
8.5  自底向上归并排序  261
练习  265
8.6  归并排序的性能特征  265
练习  266
8.7  归并排序的链式实现  267
练习  269
8.8  回顾递归  270
练习  271
第9章  优先队列与堆排序  272
练习  274
9.1  基本实现方法  274
练习  276
9.2  堆数据结构  277
练习  278
9.3  堆的算法  278
练习  284
9.4  堆排序  285
练习  291
9.5  优先队列ADT  292
练习  295
9.6  索引项的优先队列  295
练习  298
9.7  二项式队列  298
练习  306
第10章  基数排序  307
10.1  位（bit）、字节（byte）和字（word）  308
练习  310
10.2  二分快速排序  310
练习  314
10.3  MSD基数排序  315
练习  321
10.4  三路基数快速排序  321
练习  325
10.5  LSD基数排序  325
练习  329
10.6  基数排序的性能特征  329
练习  332
10.7  亚线性时间排序  332
练习  335
第11章  特殊目的排序方法  336
11.1  巴切奇偶归并排序  337
练习  341
11.2  排序网络  341
练习  347
11.3  外部排序  349
练习  353
11.4  排序归并的实现  353
练习  358
11.5  并行排序归并  359
练习  361
第三部分参考文献  362
第四部分　搜索
第12章  符号表和二叉搜索树  365
12.1  符号表抽象数据类型  366
练习  369
12.2  键索引搜索  370
练习  372
12.3  顺序搜索  372
练习  376
12.4  二分搜索  377
练习  381
12.5  二叉搜索树（BST）  381
练习  387
12.6  BST的性能特征  388
练习  390
12.7  符号表的索引实现  392
练习  394
12.8  在BST根部的插入  395
练习  399
12.9  其他ADT函数的BST实现  400
练习  406
第13章  平衡树  408
练习  410
13.1  随机BST  410
练习  415
13.2  分裂BST  416
练习  422
13.3  自顶向下2-3-4树  422
练习  427
13.4  红-黑树  427
练习  434
13.5  跳表  436
练习  443
13.6  性能特征  443
练习  445
第14章  哈希方法  446
14.1  哈希函数  446
练习  453
14.2  分离链  454
练习  457
14.3  线性探测法  458
练习  461
14.4  双哈希法  462
练习  466
14.5  动态哈希表  467
练习  469
14.6  展望  470
练习  473
第15章  基数搜索  474
15.1  位搜索树  474
练习  478
15.2  Trie  479
练习  485
15.3  Patricia Tries  486
练习  492
15.4  多路trie和TST  493
练习  504
15.5  文本串索引算法  506
练习  508
第16章  外部搜索  510
16.1  游戏规则  511
16.2  索引顺序访问  512
练习  515
16.3  B树  515
练习  524
16.4  可扩展哈希法  525
练习  533
16.5  展望  534
练习  534
第四部分参考文献  536