這本《C 數(shù)據(jù)結(jié)構(gòu)與算法(第4版)》全面系統(tǒng)地介紹了數(shù)據(jù)結(jié)構(gòu)，并以C 語(yǔ)言實(shí)現(xiàn)相關(guān)的算法。書中主要強(qiáng)調(diào)了數(shù)據(jù)結(jié)構(gòu)和算法之間的聯(lián)系，使用面向?qū)ο蟮姆椒ń榻B數(shù)據(jù)結(jié)構(gòu)，其內(nèi)容包括算法的復(fù)雜度分析、鏈表、棧、隊(duì)列、遞歸、二叉樹(shù)、圖、排序和散列。本書還清晰地闡述了同類教材中較少提到的內(nèi)存管理、數(shù)據(jù)壓縮和字符串匹配等主題。書中包含大量的示例分析和圖形，便于讀者進(jìn)一步理解和鞏固所學(xué)的知識(shí)。
◆ 本書的示例分析貫穿全書，便于學(xué)生在真實(shí)的環(huán)境下了解數(shù)據(jù)結(jié)構(gòu)的概念
◆ 本書每章最后都提供了編程練習(xí)，給學(xué)生提供額外的實(shí)踐機(jī)會(huì)，鞏固所學(xué)內(nèi)容
◆ 本書配以大量的圖形，使學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)有直觀的理解
Adam Drozdek畢業(yè)于美國(guó)萊特州立大學(xué)，現(xiàn)任迪尤肯大學(xué)計(jì)算機(jī)科學(xué)系副教授，出版過(guò)多部數(shù)據(jù)結(jié)構(gòu)和算法方面的專業(yè)書籍，包括本書和Data Structures and Algorithms in Java 等。
第1章 C 面向?qū)ο蟪绦蛟O(shè)計(jì)1
1.1 抽象數(shù)據(jù)類型1
1.2 封裝1
1.3 繼承5
1.4 指針7
1.4.1 指針與數(shù)組10
1.4.2 指針與復(fù)制構(gòu)造函數(shù)12
1.4.3 指針與析構(gòu)函數(shù)14
1.4.4 指針和引用變量14
1.4.5 函數(shù)指針17
1.5 多態(tài)性18
1.6 C 和面向?qū)ο蟪绦蛟O(shè)計(jì)20
1.7 標(biāo)準(zhǔn)模板庫(kù)20
1.7.1 容器21
1.7.2 迭代器21
1.7.3 算法21
1.7.4 函數(shù)對(duì)象22
1.8 標(biāo)準(zhǔn)模板庫(kù)中的向量24
1.9 數(shù)據(jù)結(jié)構(gòu)與面向?qū)ο缶幊?9
1.10 案例分析：隨機(jī)訪問(wèn)文件30
1.11 習(xí)題38
1.12 編程練習(xí)40
參考書目42
第2章 復(fù)雜度分析43
2.1 計(jì)算復(fù)雜度以及漸近復(fù)雜度43
2.2 大O表示法44
2.3 大O表示法的性質(zhì)46
2.4 Ω表示法與Θ表示法47
2.5 可能存在的問(wèn)題48
2.6 復(fù)雜度示例49
2.7 確定漸近復(fù)雜度示例50
2.8 最好、平均和最壞情況51
2.9 攤銷復(fù)雜度(amortized plexity)54
2.10 NP完整性57
2.11 習(xí)題59
參考書目61
第3章 鏈表63
3.1 單向鏈表63
3.1.1 插入68
3.1.2 刪除70
3.1.3 查找74
3.2 雙向鏈表74
3.3 循環(huán)鏈表78
3.4 跳躍鏈表(skip list)79
3.5 自組織鏈表83
3.6 稀疏表87
3.7 標(biāo)準(zhǔn)模板庫(kù)中的鏈表89
3.8 小結(jié)92
3.9 案例分析：圖書館93
3.10 習(xí)題101
3.11 編程練習(xí)102
參考書目105
第4章 棧與隊(duì)列107
4.1 棧107
4.2 隊(duì)列113
4.3 優(yōu)先隊(duì)列119
4.4 標(biāo)準(zhǔn)模板庫(kù)中的棧119
4.5 標(biāo)準(zhǔn)模板庫(kù)中的隊(duì)列120
4.6 標(biāo)準(zhǔn)模板庫(kù)中的優(yōu)先隊(duì)列121
4.7 標(biāo)準(zhǔn)模版庫(kù)中的雙端隊(duì)列123
4.8 案例分析：迷宮問(wèn)題127
4.9 習(xí)題131
4.10 編程練習(xí)133
參考書目134
第5章 遞歸135
5.1 遞歸定義135
5.2 函數(shù)調(diào)用與遞歸實(shí)現(xiàn)137
5.3 分析遞歸調(diào)用139
5.4 尾遞歸142
5.5 非尾遞歸142
5.6 間接遞歸147
5.7 嵌套遞歸148
5.8 不合理遞歸149
5.9 回溯152
5.10 小結(jié)157
5.11 案例分析：遞歸下降解釋器158
5.12 習(xí)題165
5.13 編程練習(xí)167
參考書目169
第6章 二叉樹(shù)171
6.1 樹(shù)、二叉樹(shù)和二叉查找樹(shù)171
6.2 二叉樹(shù)的實(shí)現(xiàn)174
6.3 二叉查找樹(shù)的查找176
6.4 樹(shù)的遍歷179
6.4.1 廣度優(yōu)先遍歷179
6.4.2 深度優(yōu)先遍歷180
6.4.3 不使用棧的深度優(yōu)先遍歷186
6.5 插入191
6.6 刪除193
6.6.1 合并刪除194
6.6.2 復(fù)制刪除196
6.7 樹(shù)的平衡198
6.7.1 DSW算法200
6.7.2 AVL樹(shù)202
6.8 自適應(yīng)樹(shù)(self-adjusting tree)207
6.8.1 自重新構(gòu)造樹(shù)(self-restructuring tree)207
6.8.2 “張開(kāi)”策略(splaying)208
6.9 堆212
6.9.1 將堆作為優(yōu)先隊(duì)列213
6.9.2 用數(shù)組實(shí)現(xiàn)堆215
6.10 treap樹(shù)218
6.11 k-d樹(shù)221
6.12 波蘭表示法和表達(dá)式樹(shù)225
6.13 案例分析：計(jì)算單詞出現(xiàn)的頻率229
6.14 習(xí)題235
6.15 編程練習(xí)239
參考書目242
第7章 多叉樹(shù)245
7.1 B樹(shù)家族245
7.1.1 B樹(shù)247
7.1.2 B*樹(shù)254
7.1.3 B 樹(shù)255
7.1.4 前綴B 樹(shù)257
7.1.5 k-d B樹(shù)259
7.1.6 位樹(shù)264
7.1.7 R樹(shù)265
7.1.8 2-4樹(shù)267
7.1.9 標(biāo)準(zhǔn)模板庫(kù)中的集合(set)以及多重集合(multiset)278
7.1.10 標(biāo)準(zhǔn)模板庫(kù)中的映射(map)和多映射(multimap)282
7.2 trie286
7.3 小結(jié)292
7.4 案例分析：拼寫檢查器292
7.5 習(xí)題300
7.6 編程練習(xí)301
參考書目304
第8章 圖307
8.1 圖的表示法308
8.2 圖的遍歷309
8.3 最短路徑312
8.4 環(huán)的檢測(cè)319
8.5 生成樹(shù)322
8.6 連通性324
8.6.1 無(wú)向圖中的連通性324
8.6.2 有向圖中的連通性326
8.7 拓?fù)渑判?28
8.8 網(wǎng)絡(luò)329
8.8.1 最大流329
8.8.2 成本最低的最大流337
8.9 匹配340
8.9.1 穩(wěn)定匹配問(wèn)題344
8.9.2 分配問(wèn)題346
8.9.3 非二分圖中的匹配集合348
8.10 歐拉(Eulerian)圖與漢密爾頓 (Hamiltonian)圖349
8.10.1 歐拉圖349
8.10.2 漢密爾頓圖352
8.11 圖的上色問(wèn)題356
8.12 圖論中的NP完整性問(wèn)題359
8.12.1 派系問(wèn)題359
8.12.2 三色問(wèn)題360
8.12.3 頂點(diǎn)覆蓋問(wèn)題361
8.12.4 漢密爾頓環(huán)問(wèn)題361
8.13 案例分析：唯一代表363
8.14 習(xí)題372
8.15 編程練習(xí)376
參考書目377
第9章 排序381
9.1 基本的排序算法382
9.1.1 插入排序382
9.1.2 選擇排序384
9.1.3 冒泡排序386
9.1.4 梳排序388
9.2 決策樹(shù)389
9.3 高效排序算法392
9.3.1 希爾排序392
9.3.2 堆排序395
9.3.3 快速排序397
9.3.4 歸并排序402
9.3.5 基數(shù)排序405
9.3.6 計(jì)數(shù)排序408
9.4 標(biāo)準(zhǔn)模板庫(kù)中的排序410
9.5 小結(jié)414
9.6 案例分析：多項(xiàng)式相加414
9.7 習(xí)題420
9.8 編程練習(xí)422
參考書目423
第10章 散列427
10.1 散列函數(shù)427
10.1.1 除余法428
10.1.2 折疊法428
10.1.3 平方取中法429
10.1.4 提取法429
10.1.5 基數(shù)轉(zhuǎn)換法429
10.1.6 全域散列法429
10.2 沖突解決方法430
10.2.1 開(kāi)放定址法430
10.2.2 鏈接法435
10.2.3 桶定址436
10.3 刪除437
10.4 理想散列函數(shù)438
10.4.1 Cichelli方法438
10.4.2 FHCD算法440
10.5 再散列442
10.6 可擴(kuò)展文件的散列函數(shù)444
10.6.1 可擴(kuò)展散列445
10.6.2 線性散列446
10.7 案例分析：使用桶的散列449
10.8 習(xí)題456
10.9 編程練習(xí)457
參考書目458
第11章 數(shù)據(jù)壓縮461
11.1 數(shù)據(jù)壓縮的條件461
11.2 Huffman編碼463
11.3 Run-Length編碼方式473
11.4 Ziv-Lempel編碼方式474
11.5 案例分析：Huffman方法和Run-Length編碼方式476
11.6 習(xí)題485
11.7 編程練習(xí)486
參考書目487
第12章 內(nèi)存管理489
12.1 sequential-fit方法490
12.2 nonsequential-fit方法491
12.3 垃圾回收497
12.3.1 標(biāo)記和清除498
12.3.2 復(fù)制方法504
12.3.3 遞增的垃圾回收505
12.3.4 分代垃圾回收510
12.4 小結(jié)513
12.5 案例分析514
12.6 習(xí)題521
12.7 編程練習(xí)522
參考書目524
第13章 字符串匹配527
13.1 字符串的精確匹配527
13.1.1 簡(jiǎn)單的算法527
13.1.2 Knuth-Morris-Pratt算法530
13.1.3 Boyer-Moore算法536
13.1.4 多次搜索545
13.1.5 面向位的方法546
13.1.6 單詞集合的匹配550
13.1.7 正則表達(dá)式的匹配555
13.1.8 后綴trie和樹(shù)558
13.1.9 后綴數(shù)組563
13.2 字符串的模糊匹配564
13.2.1 字符串的近似性565
13.2.2 有k個(gè)錯(cuò)誤的字符串匹配570
13.3 案例分析：最長(zhǎng)的共有子字符串573
13.4 習(xí)題580
13.5 編程練習(xí)581
參考書目582
附錄A 計(jì)算大O585
附錄B 標(biāo)準(zhǔn)模板庫(kù)中的算法591
附錄C NP完整性599
新書資訊