這本經(jīng)典、暢銷的數(shù)據(jù)結(jié)構(gòu)教材詳細介紹了數(shù)據(jù)抽象的基礎(chǔ)知識，強調(diào)作為面向?qū)ο蠓椒ɑA(chǔ)原理的規(guī)范和實施之間的區(qū)別。書中使用的軟件工程原則和概念以及UML圖便于增強學(xué)生的理解。

本書特點

◆詳細介紹了數(shù)據(jù)抽象，強調(diào)規(guī)范和實現(xiàn)之間的區(qū)別

◆廣泛介紹了各種面向?qū)ο蟮木幊碳夹g(shù)

◆重點是核心的數(shù)據(jù)結(jié)構(gòu)，而不是非必要的C++語言語法

◆說明了類和ADT在問題解決過程中的作用

◆詮釋了ADT的主要應(yīng)用，如查找航班圖、事件驅(qū)動的模擬和八皇后問題

◆大部分章節(jié)中的例子都使用了標(biāo)準模板庫(STL)

◆介紹了遞歸

◆附錄中提供了基本的C++語法，以幫助學(xué)生從其他語言轉(zhuǎn)換為C++

目錄

第1章 數(shù)據(jù)抽象：墻 1
1.1 面向?qū)ο蟮母拍?2
1.1.1 面向?qū)ο蠓治雠c設(shè)計 2
1.1.2 面向?qū)ο蠼鉀Q方案的特征 3
1.2 獲得更好的解決方案 4
1.2.1 內(nèi)聚 5
1.2.2 耦合 5
1.3 規(guī)范 6
1.3.1 操作契約 7
1.3.2 特殊情況 8
1.3.3 抽象 9
1.3.4 信息隱藏 10
1.3.5 最小且完整的接口 11
1.4 抽象數(shù)據(jù)類型 12
1.4.1 設(shè)計ADT 14
1.4.2 涉及其他ADT的ADT 17
1.5 ADT包 18
1.5.1 確定行為 18
1.5.2 指定數(shù)據(jù)和操作 19
1.5.3 ADT的模板接口 22
1.5.4 使用ADT包 24
C++片段1 C++類 29
C1.1 待解決的問題 30
C1.1.1 私有數(shù)據(jù)字段 31
C1.1.2 構(gòu)造函數(shù)和析構(gòu)函數(shù) 32
C1.1.3 方法 32
C1.1.4 防止編譯錯誤 33
C1.2 實現(xiàn)解決方案 34
C1.3 模板 35
C1.4 繼承 37
C1.4.1 基類和派生類 38
C1.4.2 重寫基類方法 40
C1.5 虛方法和抽象類 42
C1.5.1 虛方法 42
C1.5.2 抽象類 43
第2章 遞歸：鏡子 45
2.1 遞歸解決方案 46
2.2 返回值的遞歸 48
2.2.1 遞歸值函數(shù)：n的階乘 49
2.2.2 箱式跟蹤 52
2.3 執(zhí)行動作的遞歸 55
2.4 遞歸與數(shù)組 62
2.4.1 逆置數(shù)組項 63
2.4.2 折半查找 64
2.4.3 查找數(shù)組中的最大值 68
2.4.4 查找數(shù)組中第k個最小值 69
2.5 組織數(shù)據(jù) 71
2.6 更多示例 75
2.6.1 Fibonacci數(shù)列(兔子繁殖) 75
2.6.2 組織游行隊伍 78
2.6.3 從n個事物中選出k個 79
2.7 遞歸和效率 81
第3章 基于數(shù)組的實現(xiàn) 91
3.1 辦法 92
3.1.1 核心方法 93
3.1.2 使用大小固定的數(shù)組 93
3.2 ADT包的基于數(shù)組的實現(xiàn) 94
3.2.1 頭文件 95
3.2.2 定義核心方法 96
3.2.3 測試核心方法 98
3.2.4 實現(xiàn)更多方法 101
3.2.5 刪除項的方法 103
3.2.6 測試 106
3.3 在實現(xiàn)中使用遞歸 107
3.3.1 getIndexOf方法 107
3.3.2 getFrequencyOf方法 108
C++片段2 指針、多態(tài)和內(nèi)存分配 113
C2.1 變量的內(nèi)存分配和方法的前期
綁定 114
C2.2 需要解決的問題 115
C2.3 指針與程序的自由存儲 116
C2.3.1 釋放內(nèi)存 118
C2.3.2 避免內(nèi)存泄漏 119
C2.3.3 避免懸掛指針 122
C2.4 虛方法和多態(tài) 124
C2.5 數(shù)組的動態(tài)分配 126
第4章 基于鏈表的實現(xiàn) 129
4.1 預(yù)備知識 130
4.2 ADT包的基于鏈表的實現(xiàn) 133
4.2.1 頭文件 134
4.2.2 定義核心方法 135
4.2.3 實現(xiàn)更多方法 138
4.3 在基于鏈表的實現(xiàn)中使用遞歸 143
4.4 測試多個ADT實現(xiàn) 145
4.5 比較基于數(shù)組的實現(xiàn)和基于鏈表的實現(xiàn) 148
第5章 作為問題求解技術(shù)的遞歸 155
5.1 定義語言 156
5.1.1 語法知識基礎(chǔ) 156
5.1.2 兩種簡單的語言 158
5.2 代數(shù)表達式 160
5.2.1 代數(shù)表達式的類型 160
5.2.2 前綴表達式 162
5.2.3 后綴表達式 166
5.2.4 完全括號化表達式 168
5.3 回溯 168
5.3.1 查找航線 168
5.3.2 八皇后問題 173
5.4 遞歸和數(shù)學(xué)歸納法的關(guān)系 179
5.4.1 遞歸階乘函數(shù)的正確性 179
5.4.2 Hanoi塔的工作量 180
第6章 棧 189
6.1 ADT棧 190
6.1.1 在設(shè)計解決方案期間開發(fā)ADT 190
6.1.2 ADT棧的規(guī)范 192
6.2 棧的簡單應(yīng)用 197
6.2.1 檢查括號匹配 197
6.2.2 識別語言中的字符串 199
6.3 棧在代數(shù)表達式中的應(yīng)用 200
6.3.1 計算后綴表達式 201
6.3.2 中綴表達式與后綴表達式的等價轉(zhuǎn)換 202
6.4 使用棧查找航班圖 205
6.5 棧和遞歸的關(guān)系 212
C++片段3 異常 221
C3.1 背景知識 222
C3.2 斷言 223
C3.3 拋出異常 224
C3.4 處理異常 227
C3.4.1 多個catch塊 228
C3.4.2 未捕獲的異常 229
C3.5 程序員定義的異常類 232
第7章 實現(xiàn)ADT棧 235
7.1 基于數(shù)組的實現(xiàn) 236
7.2 基于鏈表的實現(xiàn) 239
7.3 在實現(xiàn)中使用異常 243
第8章 列表 247
8.1 指定ADT列表 248
8.2 使用列表操作 252
8.3 ADT列表的模板接口 255
第9章 實現(xiàn)列表 259
9.1 基于數(shù)組的ADT列表實現(xiàn) 260
9.1.1 頭文件 261
9.1.2 實現(xiàn)文件 262
9.2 基于鏈表的ADT列表實現(xiàn) 266
9.2.1 頭文件 266
9.2.2 實現(xiàn)文件 268
9.2.3 在LinkedList的方法中使用遞歸 275
9.3 兩種實現(xiàn)的比較 279
第10章 算法的效率 283
10.1 什么是好的解決方案 284
10.2 測量算法的效率 285
10.2.1 算法的執(zhí)行時間 286
10.2.2 算法增長率 287
10.2.3 分析與大O表示法 288
10.2.4 正確分析問題 291
10.2.5 查找算法的效率 293
第11章 排序算法及其效率 299
11.1 基本排序算法 300
11.1.1 選擇排序 300
11.1.2 起泡排序 303
11.1.3 插入排序 305
11.2 較快排序算法 307
11.2.1 歸并排序 307
11.2.2 快速排序 312
11.2.3 基數(shù)排序 319
11.3 各種排序算法的比較 321
C++片段4 類關(guān)系和重用 325
C4.1 回顧繼承 326
C4.1.1 類的公有、私有和受保護部分 331
C4.1.2 公有、私有和受保護繼承 332
C4.1.3 is-a和as-a關(guān)系 333
C4.2 包含：has-a關(guān)系 334
C4.3 回顧抽象基類 335
第12章 有序表及其實現(xiàn) 339
12.1 指定ADT有序表 340
12.1.1 ADT有序表的模板接口 342
12.1.2 使用有序表的操作 343
12.2 基于鏈表的實現(xiàn) 344
12.2.1 頭文件 344
12.2.2 實現(xiàn)文件 345
12.2.3 基于鏈表的實現(xiàn)的效率 348
12.3 使用ADT列表的實現(xiàn) 348
12.3.1 包含 349
12.3.2 公有繼承 352
12.3.3 私有繼承 356
第13章 隊列和優(yōu)先隊列 363
13.1 ADT隊列 364
13.2 ADT隊列的簡單應(yīng)用 367
13.2.1 讀取字符串 367
13.2.2 識別回文 368
13.3 ADT優(yōu)先隊列 369
13.4 應(yīng)用：模擬 371
13.5 面向位置和面向值的ADT 379
第14章 隊列和優(yōu)先隊列的實現(xiàn) 387
14.1 ADT隊列的實現(xiàn) 388
14.1.1 使用ADT列表的實現(xiàn) 388
14.1.2 基于鏈表的實現(xiàn) 390
14.1.3 基于數(shù)組的實現(xiàn) 394
14.1.4 比較實現(xiàn) 399
14.2 ADT優(yōu)先隊列的實現(xiàn) 400
C++片段5 運算符重載和友元訪問 405
C5.1 重載運算符 406
C5.1.1 重載=進行賦值 408
C5.1.2 重載+進行連接 410
C5.2 友元訪問和<<的重載 411
第15章 樹 415
15.1 術(shù)語 416
15.1.1 樹的類型 417
15.1.2 樹的高度 419
15.1.3 滿二叉樹、完全二叉樹和平衡二叉樹 421
15.1.4 二叉樹的最大和最小高度 422
15.2 ADT二叉樹 425
15.2.1 二叉樹的遍歷 425
15.2.2 二叉樹的操作 428
15.2.3 ADT二叉樹的模板接口 430
15.3 ADT二叉查找樹 432
15.3.1 二叉查找樹的操作 433
15.3.2 查找二叉查找樹 434
15.3.3 創(chuàng)建二叉查找樹 435
15.3.4 遍歷二叉查找樹 437
15.3.5 二叉查找樹操作的效率 437
第16章 樹的實現(xiàn) 443
16.1 二叉樹中的節(jié)點 444
16.1.1 基于數(shù)組的表示 444
16.1.2 基于鏈表的表示 446
16.2 ADT二叉樹基于鏈表的實現(xiàn) 447
16.2.1 頭文件 447
16.2.2 實現(xiàn) 450
16.3 ADT二叉查找樹基于鏈表的實現(xiàn) 458
16.3.1 ADT二叉查找樹操作的算法 458
16.3.2 BinarySearchTree類 469
16.4 在文件中保存二叉查找樹 471
16.5 樹排序 474
16.6 一般樹 474
C++片段6 迭代器 479
C6.1 迭代器 480
C6.1.1 常見的迭代器操作 481
C6.1.2 使用迭代器操作 482
C6.1.3 實現(xiàn)迭代器 483
C6.2 迭代器的高級功能 485
第17章 堆 489
17.1 ADT堆 490
17.2 堆的基于數(shù)組的實現(xiàn) 493
17.2.1 基于數(shù)組的堆操作的算法 494
17.2.2 實現(xiàn) 498
17.3 ADT優(yōu)先隊列的堆實現(xiàn) 502
17.4 堆排序 504
第18章 字典及其實現(xiàn) 511
18.1 ADT字典 512
18.2 可能的實現(xiàn) 517
18.2.1 ADT字典的基于數(shù)組的有序?qū)崿F(xiàn) 519
18.2.2 ADT字典的二叉查找樹實現(xiàn) 521
18.3 選擇實現(xiàn) 523
18.4 散列 529
18.4.1 散列函數(shù) 532
18.4.2 解決沖突 534
18.4.3 散列的效率 539
18.4.4 如何確立散列函數(shù) 542
18.4.5 字典遍歷：散列的低效操作 543
18.4.6 使用散列和分離鏈實現(xiàn)ADT字典 544
第19章 平衡查找樹 551
19.1 平衡查找樹 552
19.2 2-3樹 553
19.2.1 遍歷2-3樹 555
19.2.2 查找2-3樹 556
19.2.3 在2-3樹中插入數(shù)據(jù) 558
19.2.4 從2-3樹中刪除數(shù)據(jù) 562
19.3 2-3-4樹 567
19.3.1 查找和遍歷2-3-4樹 569
19.3.2 在2-3-4樹中插入數(shù)據(jù) 569
19.3.3 從2-3-4樹中刪除數(shù)據(jù) 572
19.4 紅-黑樹 573
19.4.1 查找和遍歷紅-黑樹 575
19.4.2 紅-黑樹的插入和刪除 575
19.5 AVL樹 577
第20章 圖 583
20.1 術(shù)語 584
20.2 將圖作為ADT 587
20.3 圖的遍歷 591
20.3.1 深度優(yōu)先查找 592
20.3.2 廣度優(yōu)先查找 593
20.4 圖的應(yīng)用 595
20.4.1 拓撲排序 595
20.4.2 生成樹 598
20.4.3 最小生成樹 600
20.4.4 最短路徑 603
20.4.5 回路 606
20.4.6 一些復(fù)雜問題 608
第21章 外部存儲中的數(shù)據(jù)處理 615
21.1 了解外部存儲 616
21.2 排序外部文件的數(shù)據(jù) 618
21.3 外部字典 624
21.3.1 確定外部文件的索引 626
21.3.2 外部散列 629
21.3.3 B-樹 632
21.3.4 遍歷 639
21.3.5 多索引 640
C++片段7 標(biāo)準模板庫 647
C7.1 STL容器 648
C7.1.1 STL容器適配器 649
C7.1.2 順序容器 650
C7.1.3 關(guān)聯(lián)容器 654
C7.2 STL算法 657
附錄A 回顧C++基礎(chǔ) 659
附錄B 編程中的重要主題 697
附錄C 統(tǒng)一建模語言 719
附錄D 軟件生命周期 727
附錄E 數(shù)學(xué)歸納法 733
附錄F 算法驗證 737
附錄G C++文件基礎(chǔ) 741
附錄H C++頭文件和標(biāo)準函數(shù) 751
附錄I C++文檔系統(tǒng) 755
附錄J ASCII字符代碼 757
附錄K 針對Java編程人員的C++知識 759
附錄L 針對Python編程人員的C++
知識 767