C++數據結構與算法（第4版）簡(jiǎn)介，目錄書(shū)摘

內容簡(jiǎn)介:　　這本《C++數據結構與算法(第4版)》全面系統地介紹了數據結構，并以C++語(yǔ)言實(shí)現相關(guān)的算法。
　　主要強調了數據結構和算法之間的聯(lián)系，使用面向對象的方法介紹數據結構，其內容包括算法的復雜度分析、鏈表、棧、隊列、遞歸、二叉樹(shù)、圖、排序和散列。本書(shū)還清晰地闡述了同類(lèi)教材中較少提到的內存管理、數據壓縮和字符串匹配等主題。書(shū)中包含大量的示例分析和圖形，便于讀者進(jìn)一步理解和鞏固所學(xué)的知識。

目錄:第1章  C++面向對象程序設計 1
1.1  抽象數據類(lèi)型 1
1.2  封裝 1
1.3  繼承 5
1.4  指針 7
1.4.1  指針與數組 10
1.4.2  指針與復制構造函數 12
1.4.3  指針與析構函數 14
1.4.4  指針和引用變量 14
1.4.5  函數指針 17
1.5  多態(tài)性 18
1.6  C++和面向對象程序設計 20
1.7  標準模板庫 20
1.7.1  容器 21
1.7.2  迭代器 21
1.7.3  算法 21
1.7.4  函數對象 22
1.8  標準模板庫中的向量 24
1.9  數據結構與面向對象編程 29
1.10  案例分析：隨機訪(fǎng)問(wèn)文件 30
1.11  習題 38
1.12  編程練習 40
參考書(shū)目 42
第2章  復雜度分析 43
2.1  計算復雜度以及漸近復雜度 43
2.2  大O表示法 44
2.3  大O表示法的性質(zhì) 46
2.4  Ω表示法與Θ表示法 47
2.5  可能存在的問(wèn)題 48
2.6  復雜度示例 49
2.7  確定漸近復雜度示例 50
2.8  最好、平均和最壞情況 51
2.9  攤銷(xiāo)復雜度(amortized complexity) 54
2.10  NP完整性 57
2.11  習題 59
參考書(shū)目 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  標準模板庫中的鏈表 89
3.8  小結 92
3.9  案例分析：圖書(shū)館 93
3.10  習題 101
3.11  編程練習 102
參考書(shū)目 105
第4章  棧與隊列 107
4.1  棧 107
4.2  隊列 113
4.3  優(yōu)先隊列 119
4.4  標準模板庫中的棧 119
4.5  標準模板庫中的隊列 120
4.6  標準模板庫中的優(yōu)先隊列 121
4.7  標準模版庫中的雙端隊列 123
4.8  案例分析：迷宮問(wèn)題 127
4.9  習題 131
4.10  編程練習 133
參考書(shū)目 134
第5章  遞歸 135
5.1  遞歸定義 135
5.2  函數調用與遞歸實(shí)現 137
5.3  分析遞歸調用 139
5.4  尾遞歸 142
5.5  非尾遞歸 142
5.6  間接遞歸 147
5.7  嵌套遞歸 148
5.8  不合理遞歸 149
5.9  回溯 152
5.10  小結 157
5.11  案例分析：遞歸下降解釋器 158
5.12  習題 165
5.13  編程練習 167
參考書(shū)目 169
第6章  二叉樹(shù) 171
6.1  樹(shù)、二叉樹(shù)和二叉查找樹(shù) 171
6.2  二叉樹(shù)的實(shí)現 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  復制刪除 196
6.7  樹(shù)的平衡 198
6.7.1  DSW算法 200
6.7.2  AVL樹(shù) 202
6.8  自適應樹(shù)(self-adjusting tree) 207
6.8.1  自重新構造樹(shù)(self-restructuring tree) 207
6.8.2  “張開(kāi)”策略(splaying) 208
6.9  堆 212
6.9.1  將堆作為優(yōu)先隊列 213
6.9.2  用數組實(shí)現堆 215
6.10  treap樹(shù) 218
6.11  k-d樹(shù) 221
6.12  波蘭表示法和表達式樹(shù) 225
6.13  案例分析：計算單詞出現的頻率 229
6.14  習題 235
6.15  編程練習 239
參考書(shū)目 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  標準模板庫中的集合(set)以及多重集合(multiset) 278
7.1.10  標準模板庫中的映射(map)和多映射(multimap) 282
7.2  trie 286
7.3  小結 292
7.4  案例分析：拼寫(xiě)檢查器 292
7.5  習題 300
7.6  編程練習 301
參考書(shū)目 304
第8章  圖 307
8.1  圖的表示法 308
8.2  圖的遍歷 309
8.3  最短路徑 312
8.4  環(huán)的檢測 319
8.5  生成樹(shù) 322
8.6  連通性 324
8.6.1  無(wú)向圖中的連通性 324
8.6.2  有向圖中的連通性 326
8.7  拓撲排序 328
8.8  網(wǎng)絡(luò ) 329
8.8.1  最大流 329
8.8.2  成本最低的最大流 337
8.9  匹配 340
8.9.1  穩定匹配問(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  習題 372
8.15  編程練習 376
參考書(shū)目 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  基數排序 405
9.3.6  計數排序 408
9.4  標準模板庫中的排序 410
9.5  小結 414
9.6  案例分析：多項式相加 414
9.7  習題 420
9.8  編程練習 422
參考書(shū)目 423
第10章  散列 427
10.1  散列函數 427
10.1.1  除余法 428
10.1.2  折疊法 428
10.1.3  平方取中法 429
10.1.4  提取法 429
10.1.5  基數轉換法 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  理想散列函數 438
10.4.1  Cichelli方法 438
10.4.2  FHCD算法 440
10.5  再散列 442
10.6  可擴展文件的散列函數 444
10.6.1  可擴展散列 445
10.6.2  線(xiàn)性散列 446
10.7  案例分析：使用桶的散列 449
10.8  習題 456
10.9  編程練習 457
參考書(shū)目 458
第11章  數據壓縮 461
11.1  數據壓縮的條件 461
11.2  Huffman編碼 463
11.3  Run-Length編碼方式 473
11.4  Ziv-Lempel編碼方式 474
11.5  案例分析：Huffman方法和Run-Length編碼方式 476
11.6  習題 485
11.7  編程練習 486
參考書(shū)目 487
第12章  內存管理 489
12.1  sequential-fit方法 490
12.2  nonsequential-fit方法 491
12.3  垃圾回收 497
12.3.1  標記和清除 498
12.3.2  復制方法 504
12.3.3  遞增的垃圾回收 505
12.3.4  分代垃圾回收 510
12.4  小結 513
12.5  案例分析 514
12.6  習題 521
12.7  編程練習 522
參考書(shū)目 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  正則表達式的匹配 555
13.1.8  后綴trie和樹(shù) 558
13.1.9  后綴數組 563
13.2  字符串的模糊匹配 564
13.2.1  字符串的近似性 565
13.2.2  有k個(gè)錯誤的字符串匹配 570
13.3  案例分析：最長(cháng)的共有子字符串 573
13.4  習題 580
13.5  編程練習 581
參考書(shū)目 582
附錄A  計算大O 585
附錄B  標準模板庫中的算法 591
附錄C  NP完整性 599