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

第一部分　基礎(chǔ)知識
第1章  導(dǎo)論  2
1.1  算法  2
1.2  問題示例：連通性（connectivity）  4
練習(xí)  7
1.3  并集—查找算法  7
練習(xí)  17
1.4  展望  18
練習(xí)  19
1.5  小結(jié)  19
第2章  算法分析原理  22
2.1  實(shí)現(xiàn)與試驗(yàn)分析  22
練習(xí)  25
2.2  算法分析  25
練習(xí)  27
2.3  函數(shù)增長  27
練習(xí)  32
2.4  O記號  32
練習(xí)  35
2.5  基本遞推式  36
練習(xí)  38
2.6  算法分析示例  39
練習(xí)  43
2.7  保證、預(yù)測與限制  44
練習(xí)  46
第一部分參考文獻(xiàn)  47
第二部分　數(shù)據(jù)結(jié)構(gòu)
第3章  基本數(shù)據(jù)結(jié)構(gòu)  49
3.1  基石  50
練習(xí)  57
3.2  數(shù)組  57
練習(xí)  63
3.3  鏈表  64
練習(xí)  69
3.4  基本表處理  70
練習(xí)  77
3.5  表的內(nèi)存分配  77
練習(xí)  80
3.6  串  80
練習(xí)  84
3.7  復(fù)合數(shù)據(jù)結(jié)構(gòu)  84
練習(xí)  92
第4章  抽象數(shù)據(jù)類型  93
4.1  抽象對象與對象集合  95
練習(xí)  97
4.2  下推棧ADT  97
練習(xí)  99
4.3  棧ADT客戶程序示例  99
練習(xí)  104
4.4  棧ADT實(shí)現(xiàn)  105
練習(xí)  108
4.5  創(chuàng)建新ADT  109
練習(xí)  111
4.6  FIFO隊(duì)列及廣義隊(duì)列  111
練習(xí)  117
4.7  重復(fù)項(xiàng)和索引項(xiàng)  118
練習(xí)  121
4.8  一級ADT  122
練習(xí)  130
4.9  ADT應(yīng)用示例  131
練習(xí)  134
4.10  展望  135
第5章  遞歸和樹  136
5.1  遞歸算法  136
練習(xí)  141
5.2  分治  142
練習(xí)  155
5.3  動態(tài)規(guī)劃  156
練習(xí)  160
5.4  樹  163
練習(xí)  168
5.5  二叉樹的數(shù)學(xué)性質(zhì)  169
練習(xí)  171
5.6  樹遍歷  172
練習(xí)  175
5.7  遞歸二叉樹算法  177
練習(xí)  181
5.8  圖遍歷  182
練習(xí)  187
5.9  展望  188
第二部分參考文獻(xiàn)  189
第三部分　排序
第6章  基本排序方法  191
6.1  游戲規(guī)則  192
練習(xí)  195
6.2  選擇排序  196
練習(xí)  197
6.3  插入排序  198
練習(xí)  199
6.4  冒泡排序  200
練習(xí)  201
6.5  基本排序的性能特征  201
練習(xí)  206
6.6  希爾排序  206
練習(xí)  212
6.7  其他數(shù)據(jù)類型的排序  214
練習(xí)  217
6.8  索引與指針排序  218
練習(xí)  223
6.9  鏈表的排序  223
練習(xí)  225
6.10  鍵索引計(jì)數(shù)  226
練習(xí)  228
第7章  快速排序  229
7.1  基本算法  229
練習(xí)  233
7.2  快速排序的性能特征  233
練習(xí)  236
7.3  棧大小  236
練習(xí)  239
7.4  小子文件  239
練習(xí)  240
7.5  三元素中值法劃分  242
練習(xí)  245
7.6  重復(fù)鍵  245
練習(xí)  246
7.7  串和向量  248
練習(xí)  249
7.8  選擇  249
練習(xí)  251
第8章  歸并和歸并排序  253
8.1  二路歸并  254
練習(xí)  255
8.2  抽象就位歸并  255
練習(xí)  256
8.3  自頂向下歸并  257
練習(xí)  259
8.4  基本算法的改進(jìn)  259
練習(xí)  261
8.5  自底向上歸并排序  261
練習(xí)  265
8.6  歸并排序的性能特征  265
練習(xí)  266
8.7  歸并排序的鏈?zhǔn)綄?shí)現(xiàn)  267
練習(xí)  269
8.8  回顧遞歸  270
練習(xí)  271
第9章  優(yōu)先隊(duì)列與堆排序  272
練習(xí)  274
9.1  基本實(shí)現(xiàn)方法  274
練習(xí)  276
9.2  堆數(shù)據(jù)結(jié)構(gòu)  277
練習(xí)  278
9.3  堆的算法  278
練習(xí)  284
9.4  堆排序  285
練習(xí)  291
9.5  優(yōu)先隊(duì)列ADT  292
練習(xí)  295
9.6  索引項(xiàng)的優(yōu)先隊(duì)列  295
練習(xí)  298
9.7  二項(xiàng)式隊(duì)列  298
練習(xí)  306
第10章  基數(shù)排序  307
10.1  位（bit）、字節(jié)（byte）和字（word）  308
練習(xí)  310
10.2  二分快速排序  310
練習(xí)  314
10.3  MSD基數(shù)排序  315
練習(xí)  321
10.4  三路基數(shù)快速排序  321
練習(xí)  325
10.5  LSD基數(shù)排序  325
練習(xí)  329
10.6  基數(shù)排序的性能特征  329
練習(xí)  332
10.7  亞線性時間排序  332
練習(xí)  335
第11章  特殊目的排序方法  336
11.1  巴切奇偶?xì)w并排序  337
練習(xí)  341
11.2  排序網(wǎng)絡(luò)  341
練習(xí)  347
11.3  外部排序  349
練習(xí)  353
11.4  排序歸并的實(shí)現(xiàn)  353
練習(xí)  358
11.5  并行排序歸并  359
練習(xí)  361
第三部分參考文獻(xiàn)  362
第四部分　搜索
第12章  符號表和二叉搜索樹  365
12.1  符號表抽象數(shù)據(jù)類型  366
練習(xí)  369
12.2  鍵索引搜索  370
練習(xí)  372
12.3  順序搜索  372
練習(xí)  376
12.4  二分搜索  377
練習(xí)  381
12.5  二叉搜索樹（BST）  381
練習(xí)  387
12.6  BST的性能特征  388
練習(xí)  390
12.7  符號表的索引實(shí)現(xiàn)  392
練習(xí)  394
12.8  在BST根部的插入  395
練習(xí)  399
12.9  其他ADT函數(shù)的BST實(shí)現(xiàn)  400
練習(xí)  406
第13章  平衡樹  408
練習(xí)  410
13.1  隨機(jī)BST  410
練習(xí)  415
13.2  分裂BST  416
練習(xí)  422
13.3  自頂向下2-3-4樹  422
練習(xí)  427
13.4  紅-黑樹  427
練習(xí)  434
13.5  跳表  436
練習(xí)  443
13.6  性能特征  443
練習(xí)  445
第14章  哈希方法  446
14.1  哈希函數(shù)  446
練習(xí)  453
14.2  分離鏈  454
練習(xí)  457
14.3  線性探測法  458
練習(xí)  461
14.4  雙哈希法  462
練習(xí)  466
14.5  動態(tài)哈希表  467
練習(xí)  469
14.6  展望  470
練習(xí)  473
第15章  基數(shù)搜索  474
15.1  位搜索樹  474
練習(xí)  478
15.2  Trie  479
練習(xí)  485
15.3  Patricia Tries  486
練習(xí)  492
15.4  多路trie和TST  493
練習(xí)  504
15.5  文本串索引算法  506
練習(xí)  508
第16章  外部搜索  510
16.1  游戲規(guī)則  511
16.2  索引順序訪問  512
練習(xí)  515
16.3  B樹  515
練習(xí)  524
16.4  可擴(kuò)展哈希法  525
練習(xí)  533
16.5  展望  534
練習(xí)  534
第四部分參考文獻(xiàn)  536