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

本書特點(diǎn)

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

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

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

◆說(shuō)明了類和ADT在問(wèn)題解決過(guò)程中的作用

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

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

◆介紹了遞歸

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

目錄

第1章 數(shù)據(jù)抽象：墻 1
1.1 面向?qū)ο蟮母拍?2
1.1.1 面向?qū)ο蠓治雠c設(shè)計(jì) 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è)計(jì)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 待解決的問(wèn)題 30
C1.1.1 私有數(shù)據(jù)字段 31
C1.1.2 構(gòu)造函數(shù)和析構(gòu)函數(shù) 32
C1.1.3 方法 32
C1.1.4 防止編譯錯(cuò)誤 33
C1.2 實(shí)現(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í)行動(dòng)作的遞歸 55
2.4 遞歸與數(shù)組 62
2.4.1 逆置數(shù)組項(xiàng) 63
2.4.2 折半查找 64
2.4.3 查找數(shù)組中的最大值 68
2.4.4 查找數(shù)組中第k個(gè)最小值 69
2.5 組織數(shù)據(jù) 71
2.6 更多示例 75
2.6.1 Fibonacci數(shù)列(兔子繁殖) 75
2.6.2 組織游行隊(duì)伍 78
2.6.3 從n個(gè)事物中選出k個(gè) 79
2.7 遞歸和效率 81
第3章 基于數(shù)組的實(shí)現(xiàn) 91
3.1 辦法 92
3.1.1 核心方法 93
3.1.2 使用大小固定的數(shù)組 93
3.2 ADT包的基于數(shù)組的實(shí)現(xiàn) 94
3.2.1 頭文件 95
3.2.2 定義核心方法 96
3.2.3 測(cè)試核心方法 98
3.2.4 實(shí)現(xiàn)更多方法 101
3.2.5 刪除項(xiàng)的方法 103
3.2.6 測(cè)試 106
3.3 在實(shí)現(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 需要解決的問(wèn)題 115
C2.3 指針與程序的自由存儲(chǔ) 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ù)組的動(dòng)態(tài)分配 126
第4章 基于鏈表的實(shí)現(xiàn) 129
4.1 預(yù)備知識(shí) 130
4.2 ADT包的基于鏈表的實(shí)現(xiàn) 133
4.2.1 頭文件 134
4.2.2 定義核心方法 135
4.2.3 實(shí)現(xiàn)更多方法 138
4.3 在基于鏈表的實(shí)現(xiàn)中使用遞歸 143
4.4 測(cè)試多個(gè)ADT實(shí)現(xiàn) 145
4.5 比較基于數(shù)組的實(shí)現(xiàn)和基于鏈表的實(shí)現(xiàn) 148
第5章 作為問(wèn)題求解技術(shù)的遞歸 155
5.1 定義語(yǔ)言 156
5.1.1 語(yǔ)法知識(shí)基礎(chǔ) 156
5.1.2 兩種簡(jiǎn)單的語(yǔ)言 158
5.2 代數(shù)表達(dá)式 160
5.2.1 代數(shù)表達(dá)式的類型 160
5.2.2 前綴表達(dá)式 162
5.2.3 后綴表達(dá)式 166
5.2.4 完全括號(hào)化表達(dá)式 168
5.3 回溯 168
5.3.1 查找航線 168
5.3.2 八皇后問(wèn)題 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è)計(jì)解決方案期間開(kāi)發(fā)ADT 190
6.1.2 ADT棧的規(guī)范 192
6.2 棧的簡(jiǎn)單應(yīng)用 197
6.2.1 檢查括號(hào)匹配 197
6.2.2 識(shí)別語(yǔ)言中的字符串 199
6.3 棧在代數(shù)表達(dá)式中的應(yīng)用 200
6.3.1 計(jì)算后綴表達(dá)式 201
6.3.2 中綴表達(dá)式與后綴表達(dá)式的等價(jià)轉(zhuǎn)換 202
6.4 使用棧查找航班圖 205
6.5 棧和遞歸的關(guān)系 212
C++片段3 異常 221
C3.1 背景知識(shí) 222
C3.2 斷言 223
C3.3 拋出異常 224
C3.4 處理異常 227
C3.4.1 多個(gè)catch塊 228
C3.4.2 未捕獲的異常 229
C3.5 程序員定義的異常類 232
第7章 實(shí)現(xiàn)ADT棧 235
7.1 基于數(shù)組的實(shí)現(xiàn) 236
7.2 基于鏈表的實(shí)現(xiàn) 239
7.3 在實(shí)現(xiàn)中使用異常 243
第8章 列表 247
8.1 指定ADT列表 248
8.2 使用列表操作 252
8.3 ADT列表的模板接口 255
第9章 實(shí)現(xiàn)列表 259
9.1 基于數(shù)組的ADT列表實(shí)現(xiàn) 260
9.1.1 頭文件 261
9.1.2 實(shí)現(xiàn)文件 262
9.2 基于鏈表的ADT列表實(shí)現(xiàn) 266
9.2.1 頭文件 266
9.2.2 實(shí)現(xiàn)文件 268
9.2.3 在LinkedList的方法中使用遞歸 275
9.3 兩種實(shí)現(xiàn)的比較 279
第10章 算法的效率 283
10.1 什么是好的解決方案 284
10.2 測(cè)量算法的效率 285
10.2.1 算法的執(zhí)行時(shí)間 286
10.2.2 算法增長(zhǎng)率 287
10.2.3 分析與大O表示法 288
10.2.4 正確分析問(wèn)題 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 類的公有、私有和受保護(hù)部分 331
C4.1.2 公有、私有和受保護(hù)繼承 332
C4.1.3 is-a和as-a關(guān)系 333
C4.2 包含：has-a關(guān)系 334
C4.3 回顧抽象基類 335
第12章 有序表及其實(shí)現(xiàn) 339
12.1 指定ADT有序表 340
12.1.1 ADT有序表的模板接口 342
12.1.2 使用有序表的操作 343
12.2 基于鏈表的實(shí)現(xiàn) 344
12.2.1 頭文件 344
12.2.2 實(shí)現(xiàn)文件 345
12.2.3 基于鏈表的實(shí)現(xiàn)的效率 348
12.3 使用ADT列表的實(shí)現(xiàn) 348
12.3.1 包含 349
12.3.2 公有繼承 352
12.3.3 私有繼承 356
第13章 隊(duì)列和優(yōu)先隊(duì)列 363
13.1 ADT隊(duì)列 364
13.2 ADT隊(duì)列的簡(jiǎn)單應(yīng)用 367
13.2.1 讀取字符串 367
13.2.2 識(shí)別回文 368
13.3 ADT優(yōu)先隊(duì)列 369
13.4 應(yīng)用：模擬 371
13.5 面向位置和面向值的ADT 379
第14章 隊(duì)列和優(yōu)先隊(duì)列的實(shí)現(xiàn) 387
14.1 ADT隊(duì)列的實(shí)現(xiàn) 388
14.1.1 使用ADT列表的實(shí)現(xiàn) 388
14.1.2 基于鏈表的實(shí)現(xiàn) 390
14.1.3 基于數(shù)組的實(shí)現(xiàn) 394
14.1.4 比較實(shí)現(xiàn) 399
14.2 ADT優(yōu)先隊(duì)列的實(shí)現(xiàn) 400
C++片段5 運(yùn)算符重載和友元訪問(wèn) 405
C5.1 重載運(yùn)算符 406
C5.1.1 重載=進(jìn)行賦值 408
C5.1.2 重載+進(jìn)行連接 410
C5.2 友元訪問(wèn)和<<的重載 411
第15章 樹(shù) 415
15.1 術(shù)語(yǔ) 416
15.1.1 樹(shù)的類型 417
15.1.2 樹(shù)的高度 419
15.1.3 滿二叉樹(shù)、完全二叉樹(shù)和平衡二叉樹(shù) 421
15.1.4 二叉樹(shù)的最大和最小高度 422
15.2 ADT二叉樹(shù) 425
15.2.1 二叉樹(shù)的遍歷 425
15.2.2 二叉樹(shù)的操作 428
15.2.3 ADT二叉樹(shù)的模板接口 430
15.3 ADT二叉查找樹(shù) 432
15.3.1 二叉查找樹(shù)的操作 433
15.3.2 查找二叉查找樹(shù) 434
15.3.3 創(chuàng)建二叉查找樹(shù) 435
15.3.4 遍歷二叉查找樹(shù) 437
15.3.5 二叉查找樹(shù)操作的效率 437
第16章 樹(shù)的實(shí)現(xiàn) 443
16.1 二叉樹(shù)中的節(jié)點(diǎn) 444
16.1.1 基于數(shù)組的表示 444
16.1.2 基于鏈表的表示 446
16.2 ADT二叉樹(shù)基于鏈表的實(shí)現(xiàn) 447
16.2.1 頭文件 447
16.2.2 實(shí)現(xiàn) 450
16.3 ADT二叉查找樹(shù)基于鏈表的實(shí)現(xiàn) 458
16.3.1 ADT二叉查找樹(shù)操作的算法 458
16.3.2 BinarySearchTree類 469
16.4 在文件中保存二叉查找樹(shù) 471
16.5 樹(shù)排序 474
16.6 一般樹(shù) 474
C++片段6 迭代器 479
C6.1 迭代器 480
C6.1.1 常見(jiàn)的迭代器操作 481
C6.1.2 使用迭代器操作 482
C6.1.3 實(shí)現(xiàn)迭代器 483
C6.2 迭代器的高級(jí)功能 485
第17章 堆 489
17.1 ADT堆 490
17.2 堆的基于數(shù)組的實(shí)現(xiàn) 493
17.2.1 基于數(shù)組的堆操作的算法 494
17.2.2 實(shí)現(xiàn) 498
17.3 ADT優(yōu)先隊(duì)列的堆實(shí)現(xiàn) 502
17.4 堆排序 504
第18章 字典及其實(shí)現(xiàn) 511
18.1 ADT字典 512
18.2 可能的實(shí)現(xiàn) 517
18.2.1 ADT字典的基于數(shù)組的有序?qū)崿F(xiàn) 519
18.2.2 ADT字典的二叉查找樹(shù)實(shí)現(xiàn) 521
18.3 選擇實(shí)現(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 使用散列和分離鏈實(shí)現(xiàn)ADT字典 544
第19章 平衡查找樹(shù) 551
19.1 平衡查找樹(shù) 552
19.2 2-3樹(shù) 553
19.2.1 遍歷2-3樹(shù) 555
19.2.2 查找2-3樹(shù) 556
19.2.3 在2-3樹(shù)中插入數(shù)據(jù) 558
19.2.4 從2-3樹(shù)中刪除數(shù)據(jù) 562
19.3 2-3-4樹(shù) 567
19.3.1 查找和遍歷2-3-4樹(shù) 569
19.3.2 在2-3-4樹(shù)中插入數(shù)據(jù) 569
19.3.3 從2-3-4樹(shù)中刪除數(shù)據(jù) 572
19.4 紅-黑樹(shù) 573
19.4.1 查找和遍歷紅-黑樹(shù) 575
19.4.2 紅-黑樹(shù)的插入和刪除 575
19.5 AVL樹(shù) 577
第20章 圖 583
20.1 術(shù)語(yǔ) 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 拓?fù)渑判?595
20.4.2 生成樹(shù) 598
20.4.3 最小生成樹(shù) 600
20.4.4 最短路徑 603
20.4.5 回路 606
20.4.6 一些復(fù)雜問(wèn)題 608
第21章 外部存儲(chǔ)中的數(shù)據(jù)處理 615
21.1 了解外部存儲(chǔ) 616
21.2 排序外部文件的數(shù)據(jù) 618
21.3 外部字典 624
21.3.1 確定外部文件的索引 626
21.3.2 外部散列 629
21.3.3 B-樹(shù) 632
21.3.4 遍歷 639
21.3.5 多索引 640
C++片段7 標(biāo)準(zhǔn)模板庫(kù) 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(jī)++基礎(chǔ) 659
附錄B 編程中的重要主題 697
附錄C 統(tǒng)一建模語(yǔ)言 719
附錄D 軟件生命周期 727
附錄E 數(shù)學(xué)歸納法 733
附錄F 算法驗(yàn)證 737
附錄G C++文件基礎(chǔ) 741
附錄H C++頭文件和標(biāo)準(zhǔn)函數(shù) 751
附錄I C++文檔系統(tǒng) 755
附錄J ASCII字符代碼 757
附錄K 針對(duì)Java編程人員的C++知識(shí) 759
附錄L 針對(duì)Python編程人員的C++
知識(shí) 767