C++數據結構與算法(第4版)

C++數據結構與算法(第4版)

《C++數據結構與算法(第4版)》是2014年清華大學出版社出版的圖書,作者是Adam Drozdek。

基本介紹

  • 中文名:C++數據結構與算法(第4版)
  • 作者:Adam Drozdek
  • 譯者:徐丹 吳偉敏
  • 出版時間:2014年10月01日
  • 出版社:清華大學出版社
  • ISBN:9787302376682
  • 定價:79.8 元
內容簡介,圖書目錄,

內容簡介

本書主要講述數據結構的三個重要特性。首先,著重強調了數據結構與其算法之間的聯繫,包括算法的複雜度分析。其次,數據結構是以面向對象的方式呈現的,以與當前的設計以及實現範式一致。為了加強封裝以及分解,特彆強調了信息隱藏原則。最後,本書的重要組成部分之一是數據結構的實現,在此選擇C++作為程式語言。C++語言是由C語言演化而來的面向對象語言,是一種廣泛套用於產業界以及學術界的優秀程式語言。用該語言來介紹數據結構非常有效,並且很自然。由於C++在編程中的廣泛套用以及語言本身的面向對象特性,使用該語言講述數據結構以及算法課程是非常合舉烏槓適的,即使是入門級課程也是如此。
這本《C++數據結構與算法(第4版)》全面系統地介紹了數據結構,並以C++語言實現相關的算法。 主要強調了數據結構和算法之間的聯繫,使用面向對象的方法介紹數據結構,其內容包括算法的複雜度分析、鍊表、棧、佇列、遞歸、二叉樹、圖、排序和散列。本書還清晰地闡述了同類教材中較少提到的記憶體管理、數據壓縮和字元串匹配等主題。書中包含大量的示例分析和圖形陵享捆糠,便於讀者進一步理解和鞏固所學的知識。

圖書目錄

第1章C++面向對象程式設計 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多態匪兵嚷性 18
1.6C++和面向對象程式設計 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案例分析:隨機訪問檔案 30
1.11習題 38
1.12編程練習 40
參考書目 42
第2章複雜度分析踏榆奔 43
2.1計算複雜度以及漸近複雜度 43
2.3大O表示法的性質 46
2.4Ω表示法與Θ表示法 47
2.5可能存在的問題 48
2.6複雜度示例 49
2.7確定漸近複雜度示例 50
2.8最好、平均和最壞情況 51
2.9攤銷複雜度(amortizedcomplexity) 54
2.10NP完整性 57
2.11習題 59
參考書目 61
第3章鍊表 63
3.1單向歡院戒鍊表 63
3.1.1插入 68
3.1.2刪除 70
3.1.3查找 74
3.2雙向鍊表 74
3.3循環鍊表 78
3.4跳躍鍊表(skiplist) 79
3.5自組織鍊表 83
3.6稀疏表 87
3.7標準模板庫中的鍊表 89
3.8小結 92
3.9案例分析:圖書館 93
3.10習題 101
3.11編程練判灶習 102
參考書目 105
第4章棧與佇列 107
4.1棧 107
4.2佇列 113
4.3優先佇列 119
4.4標準模板庫中的棧 119
4.5標準盛熱晚遙模板庫中的佇列 120
4.6標準模板庫中的優先佇列 121
4.7標準模版庫中的雙端佇列 123
4.8案例分析:迷宮問題 127
4.9習題 131
4.10編程練習 133
參考書目 134
第5章遞歸 135
5.1遞歸定義 135
5.2函式調用與遞歸實現 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
參考書目 169
第6章二叉樹 171
6.1樹、二叉樹和二叉查找樹 171
6.2二叉樹的實現 174
6.3二叉查找樹的查找 176
6.4樹的遍歷 179
6.4.1廣度優先遍歷 179
6.4.2深度優先遍歷 180
6.4.3不使用棧的深度優先遍歷 186
6.5插入 191
6.6刪除 193
6.6.1合併刪除 194
6.6.2複製刪除 196
6.7樹的平衡 198
6.7.1DSW算法 200
6.7.2AVL樹 202
6.8自適應樹(self-adjustingtree) 207
6.8.1自重新構造樹(self-restructuringtree) 207
6.8.2“張開”策略(splaying) 208
6.9堆 212
6.9.1將堆作為優先佇列 213
6.9.2用數組實現堆 215
6.10treap樹 218
6.11k-d樹 221
6.12波蘭表示法和表達式樹 225
6.13案例分析:計算單詞出現的頻率 229
6.14習題 235
6.15編程練習 239
參考書目 242
第7章多叉樹 245
7.1B樹家族 245
7.1.1B樹 247
7.1.2B*樹 254
7.1.3B+樹 255
7.1.4前綴B+樹 257
7.1.5k-dB樹 259
7.1.6位樹 264
7.1.7R樹 265
7.1.82-4樹 267
7.1.9標準模板庫中的集合(set)以及多重集合(multiset) 278
7.1.10標準模板庫中的映射(map)和多映射(multimap) 282
7.2trie 286
7.3小結 292
7.4案例分析:拼寫檢查器 292
7.5習題 300
7.6編程練習 301
參考書目 304
第8章圖 307
8.1圖的表示法 308
8.2圖的遍歷 309
8.3最短路徑 312
8.4環的檢測 319
8.5生成樹 322
8.6連通性 324
8.6.1無向圖中的連通性 324
8.6.2有向圖中的連通性 326
8.7拓撲排序 328
8.8網路 329
8.8.1最大流 329
8.8.2成本最低的最大流 337
8.9匹配 340
8.9.1穩定匹配問題 344
8.9.2分配問題 346
8.9.3非二分圖中的匹配集合 348
8.10歐拉(Eulerian)圖與漢密爾頓(Hamiltonian)圖 349
8.10.1歐拉圖 349
8.10.2漢密爾頓圖 352
8.11圖的上色問題 356
8.12圖論中的NP完整性問題 359
8.12.1派系問題 359
8.12.2三色問題 360
8.12.3頂點覆蓋問題 361
8.12.4漢密爾頓環問題 361
8.13案例分析:唯一代表 363
8.14習題 372
8.15編程練習 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決策樹 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
參考書目 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開放定址法 430
10.2.2連結法 435
10.2.3桶定址 436
10.3刪除 437
10.4理想散列函式 438
10.4.1Cichelli方法 438
10.4.2FHCD算法 440
10.5再散列 442
10.6可擴展檔案的散列函式 444
10.6.1可擴展散列 445
10.6.2線性散列 446
10.7案例分析:使用桶的散列 449
10.8習題 456
10.9編程練習 457
參考書目 458
第11章數據壓縮 461
11.1數據壓縮的條件 461
11.3Run-Length編碼方式 473
11.4Ziv-Lempel編碼方式 474
11.5案例分析:Huffman方法和Run-Length編碼方式 476
11.6習題 485
11.7編程練習 486
參考書目 487
第12章記憶體管理 489
12.1sequential-fit方法 490
12.2nonsequential-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
參考書目 524
第13章字元串匹配 527
13.1字元串的精確匹配 527
13.1.1簡單的算法 527
13.1.2Knuth-Morris-Pratt算法 530
13.1.3Boyer-Moore算法 536
13.1.4多次搜尋 545
13.1.5面向位的方法 546
13.1.6單詞集合的匹配 550
13.1.7正則表達式的匹配 555
13.1.8後綴trie和樹 558
13.1.9後綴數組 563
13.2字元串的模糊匹配 564
13.2.1字元串的近似性 565
13.2.2有k個錯誤的字元串匹配 570
13.3案例分析:最長的共有子字元串 573
13.4習題 580
13.5編程練習 581
參考書目 582
附錄A計算大O 585
附錄B標準模板庫中的算法 591
附錄CNP完整性 599
3.3循環鍊表 78
3.4跳躍鍊表(skiplist) 79
3.5自組織鍊表 83
3.6稀疏表 87
3.7標準模板庫中的鍊表 89
3.8小結 92
3.9案例分析:圖書館 93
3.10習題 101
3.11編程練習 102
參考書目 105
第4章棧與佇列 107
4.1棧 107
4.2佇列 113
4.3優先佇列 119
4.4標準模板庫中的棧 119
4.5標準模板庫中的佇列 120
4.6標準模板庫中的優先佇列 121
4.7標準模版庫中的雙端佇列 123
4.8案例分析:迷宮問題 127
4.9習題 131
4.10編程練習 133
參考書目 134
第5章遞歸 135
5.1遞歸定義 135
5.2函式調用與遞歸實現 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
參考書目 169
第6章二叉樹 171
6.1樹、二叉樹和二叉查找樹 171
6.2二叉樹的實現 174
6.3二叉查找樹的查找 176
6.4樹的遍歷 179
6.4.1廣度優先遍歷 179
6.4.2深度優先遍歷 180
6.4.3不使用棧的深度優先遍歷 186
6.5插入 191
6.6刪除 193
6.6.1合併刪除 194
6.6.2複製刪除 196
6.7樹的平衡 198
6.7.1DSW算法 200
6.7.2AVL樹 202
6.8自適應樹(self-adjustingtree) 207
6.8.1自重新構造樹(self-restructuringtree) 207
6.8.2“張開”策略(splaying) 208
6.9堆 212
6.9.1將堆作為優先佇列 213
6.9.2用數組實現堆 215
6.10treap樹 218
6.11k-d樹 221
6.12波蘭表示法和表達式樹 225
6.13案例分析:計算單詞出現的頻率 229
6.14習題 235
6.15編程練習 239
參考書目 242
第7章多叉樹 245
7.1B樹家族 245
7.1.1B樹 247
7.1.2B*樹 254
7.1.3B+樹 255
7.1.4前綴B+樹 257
7.1.5k-dB樹 259
7.1.6位樹 264
7.1.7R樹 265
7.1.82-4樹 267
7.1.9標準模板庫中的集合(set)以及多重集合(multiset) 278
7.1.10標準模板庫中的映射(map)和多映射(multimap) 282
7.2trie 286
7.3小結 292
7.4案例分析:拼寫檢查器 292
7.5習題 300
7.6編程練習 301
參考書目 304
第8章圖 307
8.1圖的表示法 308
8.2圖的遍歷 309
8.3最短路徑 312
8.4環的檢測 319
8.5生成樹 322
8.6連通性 324
8.6.1無向圖中的連通性 324
8.6.2有向圖中的連通性 326
8.7拓撲排序 328
8.8網路 329
8.8.1最大流 329
8.8.2成本最低的最大流 337
8.9匹配 340
8.9.1穩定匹配問題 344
8.9.2分配問題 346
8.9.3非二分圖中的匹配集合 348
8.10歐拉(Eulerian)圖與漢密爾頓(Hamiltonian)圖 349
8.10.1歐拉圖 349
8.10.2漢密爾頓圖 352
8.11圖的上色問題 356
8.12圖論中的NP完整性問題 359
8.12.1派系問題 359
8.12.2三色問題 360
8.12.3頂點覆蓋問題 361
8.12.4漢密爾頓環問題 361
8.13案例分析:唯一代表 363
8.14習題 372
8.15編程練習 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決策樹 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
參考書目 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開放定址法 430
10.2.2連結法 435
10.2.3桶定址 436
10.3刪除 437
10.4理想散列函式 438
10.4.1Cichelli方法 438
10.4.2FHCD算法 440
10.5再散列 442
10.6可擴展檔案的散列函式 444
10.6.1可擴展散列 445
10.6.2線性散列 446
10.7案例分析:使用桶的散列 449
10.8習題 456
10.9編程練習 457
參考書目 458
第11章數據壓縮 461
11.1數據壓縮的條件 461
11.3Run-Length編碼方式 473
11.4Ziv-Lempel編碼方式 474
11.5案例分析:Huffman方法和Run-Length編碼方式 476
11.6習題 485
11.7編程練習 486
參考書目 487
第12章記憶體管理 489
12.1sequential-fit方法 490
12.2nonsequential-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
參考書目 524
第13章字元串匹配 527
13.1字元串的精確匹配 527
13.1.1簡單的算法 527
13.1.2Knuth-Morris-Pratt算法 530
13.1.3Boyer-Moore算法 536
13.1.4多次搜尋 545
13.1.5面向位的方法 546
13.1.6單詞集合的匹配 550
13.1.7正則表達式的匹配 555
13.1.8後綴trie和樹 558
13.1.9後綴數組 563
13.2字元串的模糊匹配 564
13.2.1字元串的近似性 565
13.2.2有k個錯誤的字元串匹配 570
13.3案例分析:最長的共有子字元串 573
13.4習題 580
13.5編程練習 581
參考書目 582
附錄A計算大O 585
附錄B標準模板庫中的算法 591
附錄CNP完整性 599

相關詞條

熱門詞條

聯絡我們