C++數據結構與算法（第4版）

內容簡介

本書主要講述數據結構的三個重要特性。首先，著重強調了數據結構與其算法之間的聯繫，包括算法的複雜度分析。其次，數據結構是以面向對象的方式呈現的，以與當前的設計以及實現範式一致。為了加強封裝以及分解，特彆強調了信息隱藏原則。最後，本書的重要組成部分之一是數據結構的實現，在此選擇C++作為程式語言。C++語言是由C語言演化而來的面向對象語言，是一種廣泛套用於產業界以及學術界的優秀程式語言。用該語言來介紹數據結構非常有效，並且很自然。由於C++在編程中的廣泛套用以及語言本身的面向對象特性，使用該語言講述數據結構以及算法課程是非常合舉烏槓適的，即使是入門級課程也是如此。

這本《C++數據結構與算法(第4版)》全面系統地介紹了數據結構，並以C++語言實現相關的算法。主要強調了數據結構和算法之間的聯繫，使用面向對象的方法介紹數據結構，其內容包括算法的複雜度分析、鍊表、棧、佇列、遞歸、二叉樹、圖、排序和散列。本書還清晰地闡述了同類教材中較少提到的記憶體管理、數據壓縮和字元串匹配等主題。書中包含大量的示例分析和圖形陵享捆糠，便於讀者進一步理解和鞏固所學的知識。

圖書目錄

第1章C++面向對象程式設計 1

1.1抽象數據類型 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標準模板庫 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.2大O表示法 44

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.2Huffman編碼 463

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

C++數據結構與算法（第4版）

基本介紹

內容簡介

圖書目錄

相關詞條

熱門詞條