C算法（第一卷 基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)、排序和搜索）

第一部分　基礎(chǔ)知識
第1章  導論  2
1.1  算法  2
1.2  問題示例：連通性（connectivity）  4
練習  7
1.3  并集—查找算法  7
練習  17
1.4  展望  18
練習  19
1.5  小結(jié)  19
第2章  算法分析原理  22
2.1  實現(xiàn)與試驗分析  22
練習  25
2.2  算法分析  25
練習  27
2.3  函數(shù)增長  27
練習  32
2.4  O記號  32
練習  35
2.5  基本遞推式  36
練習  38
2.6  算法分析示例  39
練習  43
2.7  保證、預(yù)測與限制  44
練習  46
第一部分參考文獻  47
第二部分　數(shù)據(jù)結(jié)構(gòu)
第3章  基本數(shù)據(jù)結(jié)構(gòu)  49
3.1  基石  50
練習  57
3.2  數(shù)組  57
練習  63
3.3  鏈表  64
練習  69
3.4  基本表處理  70
練習  77
3.5  表的內(nèi)存分配  77
練習  80
3.6  串  80
練習  84
3.7  復(fù)合數(shù)據(jù)結(jié)構(gòu)  84
練習  92
第4章  抽象數(shù)據(jù)類型  93
4.1  抽象對象與對象集合  95
練習  97
4.2  下推棧ADT  97
練習  99
4.3  棧ADT客戶程序示例  99
練習  104
4.4  棧ADT實現(xiàn)  105
練習  108
4.5  創(chuàng)建新ADT  109
練習  111
4.6  FIFO隊列及廣義隊列  111
練習  117
4.7  重復(fù)項和索引項  118
練習  121
4.8  一級ADT  122
練習  130
4.9  ADT應(yīng)用示例  131
練習  134
4.10  展望  135
第5章  遞歸和樹  136
5.1  遞歸算法  136
練習  141
5.2  分治  142
練習  155
5.3  動態(tài)規(guī)劃  156
練習  160
5.4  樹  163
練習  168
5.5  二叉樹的數(shù)學性質(zhì)  169
練習  171
5.6  樹遍歷  172
練習  175
5.7  遞歸二叉樹算法  177
練習  181
5.8  圖遍歷  182
練習  187
5.9  展望  188
第二部分參考文獻  189
第三部分　排序
第6章  基本排序方法  191
6.1  游戲規(guī)則  192
練習  195
6.2  選擇排序  196
練習  197
6.3  插入排序  198
練習  199
6.4  冒泡排序  200
練習  201
6.5  基本排序的性能特征  201
練習  206
6.6  希爾排序  206
練習  212
6.7  其他數(shù)據(jù)類型的排序  214
練習  217
6.8  索引與指針排序  218
練習  223
6.9  鏈表的排序  223
練習  225
6.10  鍵索引計數(shù)  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  重復(fù)鍵  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  歸并排序的鏈式實現(xiàn)  267
練習  269
8.8  回顧遞歸  270
練習  271
第9章  優(yōu)先隊列與堆排序  272
練習  274
9.1  基本實現(xiàn)方法  274
練習  276
9.2  堆數(shù)據(jù)結(jié)構(gòu)  277
練習  278
9.3  堆的算法  278
練習  284
9.4  堆排序  285
練習  291
9.5  優(yōu)先隊列ADT  292
練習  295
9.6  索引項的優(yōu)先隊列  295
練習  298
9.7  二項式隊列  298
練習  306
第10章  基數(shù)排序  307
10.1  位（bit）、字節(jié)（byte）和字（word）  308
練習  310
10.2  二分快速排序  310
練習  314
10.3  MSD基數(shù)排序  315
練習  321
10.4  三路基數(shù)快速排序  321
練習  325
10.5  LSD基數(shù)排序  325
練習  329
10.6  基數(shù)排序的性能特征  329
練習  332
10.7  亞線性時間排序  332
練習  335
第11章  特殊目的排序方法  336
11.1  巴切奇偶歸并排序  337
練習  341
11.2  排序網(wǎng)絡(luò)  341
練習  347
11.3  外部排序  349
練習  353
11.4  排序歸并的實現(xiàn)  353
練習  358
11.5  并行排序歸并  359
練習  361
第三部分參考文獻  362
第四部分　搜索
第12章  符號表和二叉搜索樹  365
12.1  符號表抽象數(shù)據(jù)類型  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  符號表的索引實現(xiàn)  392
練習  394
12.8  在BST根部的插入  395
練習  399
12.9  其他ADT函數(shù)的BST實現(xiàn)  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  哈希函數(shù)  446
練習  453
14.2  分離鏈  454
練習  457
14.3  線性探測法  458
練習  461
14.4  雙哈希法  462
練習  466
14.5  動態(tài)哈希表  467
練習  469
14.6  展望  470
練習  473
第15章  基數(shù)搜索  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  游戲規(guī)則  511
16.2  索引順序訪問  512
練習  515
16.3  B樹  515
練習  524
16.4  可擴展哈希法  525
練習  533
16.5  展望  534
練習  534
第四部分參考文獻  536