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

是一門描述數據的結構和某些著名算法的學科，在高校普遍存在的一門課程

本書全面系統地介紹了計算機科學教育中的一個重要組成部分——數據結構，並以C++語言實現相關的算法。書中主要強調了數據結構和算法之間的聯繫，使用面向對象的方法介紹數據結構，其內容包括算法的複雜度分析、鍊表、棧佇列、遞歸技術、二叉樹、圖、排序以及散列。本書還清楚地闡述了同類教材中較少提到的記憶體管理、數據壓縮和字元串匹配主題。書中包含大量的示例分析和圖形，便於讀者進一步理解和鞏固所學的知識。

基本介紹

• 書名：數據結構與算法：C++版（第3版）
• 作者：曹蓉蓉等
• 定價：69元
• 英文名：Data structure and algorithm

書籍信息

印次：1-4
ISBN：9787302119982
出版日期：2006.01.01
印刷日期：2008.12.31

圖書目錄

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

1.1抽象數據類型 1

1.2封裝 1

1.3繼承 5

1.4指針 7

1.4.1指針和數組 9

1.4.2指針和複製構造函式 11

1.4.3指針和析構函式 13

1.4.4指針和引用變數 14

1.4.5函式指針 16

1.5多態性 17

1.6C++和面向對象程式設計 19

1.7標準模板庫 20

1.7.1容器 20

1.7.2疊代器 20

1.7.3算法 21

1.7.4函式對象 21

1.8標準模板庫中的向量 23

1.9數據結構與面向對象編程 30

1.10案例分析：隨機訪問檔案 30

1.11習題 39

1.12程式設計作業 41

第2章複雜度分析 44

2.1計算複雜度和漸近複雜度 44

2.2大O符號 45

2.3大O符號的性質 47

2.4Ω符號與Θ符號 48

2.5可能的問題 49

2.6複雜度舉例 49

2.7確定漸近複雜度舉例 51

2.8最好、平均和最壞情況 52

2.9阻尼複雜度 55

2.10NP完整性 58

2.11習題 60

第3章鍊表 64

3.1單鍊表 64

3.1.1插入 69

3.1.2刪除 71

3.1.3查找 75

3.2雙鍊表 75

3.3循環鍊表 79

3.4跳躍鍊表 80

3.5自組織鍊表 85

3.6稀疏表 89

3.7標準模板庫中的鍊表 91

3.8標準模板庫中的雙端佇列 95

3.9小結 99

3.10案例分析：圖書館 100

3.11習題 107

3.12程式設計作業 109

第4章棧與佇列 113

4.1棧 113

4.2佇列 119

4.3優先佇列 125

4.4標準模板庫中的棧 126

4.5標準模板庫中的佇列 127

4.6標準模板庫中的優先佇列 128

4.7案例分析：迷宮問題 130

4.8習題 135

4.9程式設計作業 136

第5章遞歸 139

5.1遞歸定義 139

5.2函式調用與遞歸實現 141

5.3遞歸調用的剖析 143

5.4尾部遞歸 145

5.5非尾部遞歸 146

5.6間接遞歸 151

5.7嵌套遞歸 153

5.8不合理遞歸 153

5.9回溯 156

5.10小結 162

5.11案例分析：遞歸下降解釋器 163

5.12習題 169

5.13程式設計作業 172

第6章二叉樹 175

6.1樹、二叉樹和二叉搜尋樹 175

6.2二叉樹的實現 178

6.3二叉搜尋樹的查找 181

6.4樹的遍歷 183

6.4.1廣度優先遍歷 183

6.4.2深度優先遍歷 184

6.4.3不用棧實現的深度優先遍歷 190

6.5插入 195

6.6刪除 198

6.6.1合併刪除 198

6.6.2通過複製進行刪除 201

6.7樹的平衡 203

6.7.1DSW算法 205

6.7.2AVL樹 207

6.8自調整樹 212

6.8.1自重新構造樹 212

6.8.2“張開”策略 213

6.9堆 217

6.9.1將堆作為優先佇列 219

6.9.2將數組組織為堆 221

6.10波蘭記號和表達式樹 224

6.11案例分析：計算單詞出現的

頻率 228

6.12習題 234

6.13程式設計作業 237

第7章多叉樹 243

7.1B樹家族 243

7.1.1B樹 244

7.1.2B*樹 252

7.1.3B+樹 253

7.1.4前綴B+樹 255

7.1.5位樹 257

7.1.6R樹 258

7.1.72-4樹 260

7.1.8標準模板庫中的集和多集 270

7.1.9標準模板庫中的映射和多

映射 274

7.2trie 278

7.3小結 285

7.4案例分析：拼寫檢查器 285

7.5習題 293

7.6程式設計作業 294

第8章圖 299

8.1圖的表示法 300

8.2圖的遍歷 301

8.3最短路徑 304

8.4環的檢測 311

8.5生成樹 314

8.6連通性 316

8.6.1無向圖中的連通性 316

8.6.2有向圖中的連通性 318

8.7拓撲排序 320

8.8網路 321

8.8.1最大流 321

8.8.2成本最低的最大流 329

8.9匹配 332

8.9.1穩定匹配問題 337

8.9.2分配問題 339

8.9.3非二分圖中的匹配集合 341

8.10歐拉(Eulerian)圖與漢密爾

頓(Hamiltonian)圖 343

8.10.1歐拉圖 343

8.10.2漢密爾頓圖 345

8.11給圖加上顏色 350

8.12圖理論中的NP完整性問題 352

8.12.1派系問題 352

8.12.2三色問題 353

8.12.3頂點覆蓋問題 354

8.12.4漢密爾頓環問題 355

8.13案例分析：惟一代表 356

8.14習題 365

8.15程式設計作業 369

第9章排序 374

9.1基本的排序算法 375

9.1.1插入排序 375

9.1.2選擇排序 377

9.1.3冒泡排序 379

9.2決策樹 380

9.3高效排序算法 383

9.3.1希爾排序 383

9.3.2堆排序 386

9.3.3快速排序 389

9.3.4歸併排序 393

9.3.5基數排序 396

9.4標準模板庫中的排序 400

9.5小結 403

9.6案例分析：多項式相加 403

9.7習題 409

9.8程式設計作業 411

第10章散列 415

10.1散列函式 415

10.1.1除余法 416

10.1.2摺疊法 416

10.1.3平方取中法 416

10.1.4提取法 417

10.1.5基數轉換法 417

10.2衝突解決方法 417

10.2.1開放定址法 418

10.2.2連結法 422

10.2.3桶定址 424

10.3刪除 425

10.4理想散列函式 426

10.4.1Cichelli方法 426

10.4.2FHCD算法 429

10.5可擴展檔案的散列函式 430

10.5.1可擴展散列 431

10.5.2線性散列 433

10.6案例分析：使用桶的散列 435

10.7習題 442

10.8程式設計作業 443

第11章數據壓縮 446

11.1數據壓縮的條件 446

11.2Huffman編碼 447

11.3Run-Length編碼方式 458

11.4Ziv-Lempel編碼方式 459

11.5案例分析：Huffman方法

和Run-Length編碼方式 462

11.6習題 471

11.7程式設計作業 471

第12章記憶體管理 474

12.1sequential-fit方法 475

12.2Nonsequential-fit方法 475

12.3無用單元回收 483

12.3.1標記和清除 483

12.3.2複製方法 489

12.3.3遞增的無用單元回收 490

12.4小結 496

12.5案例分析 496

12.6習題 503

12.7程式設計作業 504

第13章字元串匹配 509

13.1字元串的精確匹配 509

13.1.1簡單的算法 509

13.1.2Knuth-Morris-Pratt算法 512

13.1.3Boyer-Moore算法 518

13.1.4多次搜尋 527

13.1.5面向位的方法 528

13.1.6單詞集合的匹配 532

13.1.7正則表達式的匹配 537

13.1.8後綴trie和樹 540

13.1.9後綴數組 545

13.2字元串的模糊匹配 546

13.2.1字元串的近似性 547

13.2.2有k個錯誤的字元串匹配 552

13.3案例分析：最長的共有子字

符串 555

13.4習題 561

13.5程式設計作業 563

附錄A計算大O 566

A.1調和數序列n 566

A.2函式的近似值 566

A.3快速排序中平均情況的大O 568

A.4隨機二叉樹中的平均路徑

長度 569

A.5AVL樹中的節點數 570

附錄B標準模板庫中的算法 572

附錄CNP完整性 581