第1章 數據抽象：牆 1
1.1 麵嚮對象的概念 2
1.1.1 麵嚮對象分析與設計 2
1.1.2 麵嚮對象解決方案的特徵 3
1.2 獲得更好的解決方案 4
1.2.1 內聚 5
1.2.2 耦閤 5
1.3 規範 6
1.3.1 操作契約 7
1.3.2 特殊情況 8
1.3.3 抽象 9
1.3.4 信息隱藏 10
1.3.5 最小且完整的接口 11
1.4 抽象數據類型 12
1.4.1 設計ADT 14
1.4.2 涉及其他ADT的ADT 17
1.5 ADT包 18
1.5.1 確定行為 18
1.5.2 指定數據和操作 19
1.5.3 ADT的模闆接口 22
1.5.4 使用ADT包 24
C++片段1 C++類 29
C1.1 待解決的問題 30
C1.1.1 私有數據字段 31
C1.1.2 構造函數和析構函數 32
C1.1.3 方法 32
C1.1.4 防止編譯錯誤 33
C1.2 實現解決方案 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 遞歸值函數：n的階乘 49
2.2.2 箱式跟蹤 52
2.3 執行動作的遞歸 55
2.4 遞歸與數組 62
2.4.1 逆置數組項 63
2.4.2 摺半查找 64
2.4.3 查找數組中的最大值 68
2.4.4 查找數組中第k個最小值 69
2.5 組織數據 71
2.6 更多示例 75
2.6.1 Fibonacci數列(兔子繁殖) 75
2.6.2 組織遊行隊伍 78
2.6.3 從n個事物中選齣k個 79
2.7 遞歸和效率 81
第3章 基於數組的實現 91
3.1 辦法 92
3.1.1 核心方法 93
3.1.2 使用大小固定的數組 93
3.2 ADT包的基於數組的實現 94
3.2.1 頭文件 95
3.2.2 定義核心方法 96
3.2.3 測試核心方法 98
3.2.4 實現更多方法 101
3.2.5 刪除項的方法 103
3.2.6 測試 106
3.3 在實現中使用遞歸 107
3.3.1 getIndexOf方法 107
3.3.2 getFrequencyOf方法 108
C++片段2 指針、多態和內存分配 113
C2.1 變量的內存分配和方法的前期
綁定 114
C2.2 需要解決的問題 115
C2.3 指針與程序的自由存儲 116
C2.3.1 釋放內存 118
C2.3.2 避免內存泄漏 119
C2.3.3 避免懸掛指針 122
C2.4 虛方法和多態 124
C2.5 數組的動態分配 126
第4章 基於鏈錶的實現 129
4.1 預備知識 130
4.2 ADT包的基於鏈錶的實現 133
4.2.1 頭文件 134
4.2.2 定義核心方法 135
4.2.3 實現更多方法 138
4.3 在基於鏈錶的實現中使用遞歸 143
4.4 測試多個ADT實現 145
4.5 比較基於數組的實現和基於鏈錶的實現 148
第5章 作為問題求解技術的遞歸 155
5.1 定義語言 156
5.1.1 語法知識基礎 156
5.1.2 兩種簡單的語言 158
5.2 代數錶達式 160
5.2.1 代數錶達式的類型 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 遞歸和數學歸納法的關係 179
5.4.1 遞歸階乘函數的正確性 179
5.4.2 Hanoi塔的工作量 180
第6章 棧 189
6.1 ADT棧 190
6.1.1 在設計解決方案期間開發ADT 190
6.1.2 ADT棧的規範 192
6.2 棧的簡單應用 197
6.2.1 檢查括號匹配 197
6.2.2 識彆語言中的字符串 199
6.3 棧在代數錶達式中的應用 200
6.3.1 計算後綴錶達式 201
6.3.2 中綴錶達式與後綴錶達式的等價轉換 202
6.4 使用棧查找航班圖 205
6.5 棧和遞歸的關係 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章 實現ADT棧 235
7.1 基於數組的實現 236
7.2 基於鏈錶的實現 239
7.3 在實現中使用異常 243
第8章 列錶 247
8.1 指定ADT列錶 248
8.2 使用列錶操作 252
8.3 ADT列錶的模闆接口 255
第9章 實現列錶 259
9.1 基於數組的ADT列錶實現 260
9.1.1 頭文件 261
9.1.2 實現文件 262
9.2 基於鏈錶的ADT列錶實現 266
9.2.1 頭文件 266
9.2.2 實現文件 268
9.2.3 在LinkedList的方法中使用遞歸 275
9.3 兩種實現的比較 279
第10章 算法的效率 283
10.1 什麼是好的解決方案 284
10.2 測量算法的效率 285
10.2.1 算法的執行時間 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 基數排序 319
11.3 各種排序算法的比較 321
C++片段4 類關係和重用 325
C4.1 迴顧繼承 326
C4.1.1 類的公有、私有和受保護部分 331
C4.1.2 公有、私有和受保護繼承 332
C4.1.3 is-a和as-a關係 333
C4.2 包含：has-a關係 334
C4.3 迴顧抽象基類 335
第12章 有序錶及其實現 339
12.1 指定ADT有序錶 340
12.1.1 ADT有序錶的模闆接口 342
12.1.2 使用有序錶的操作 343
12.2 基於鏈錶的實現 344
12.2.1 頭文件 344
12.2.2 實現文件 345
12.2.3 基於鏈錶的實現的效率 348
12.3 使用ADT列錶的實現 348
12.3.1 包含 349
12.3.2 公有繼承 352
12.3.3 私有繼承 356
第13章 隊列和優先隊列 363
13.1 ADT隊列 364
13.2 ADT隊列的簡單應用 367
13.2.1 讀取字符串 367
13.2.2 識彆迴文 368
13.3 ADT優先隊列 369
13.4 應用：模擬 371
13.5 麵嚮位置和麵嚮值的ADT 379
第14章 隊列和優先隊列的實現 387
14.1 ADT隊列的實現 388
14.1.1 使用ADT列錶的實現 388
14.1.2 基於鏈錶的實現 390
14.1.3 基於數組的實現 394
14.1.4 比較實現 399
14.2 ADT優先隊列的實現 400
C++片段5 運算符重載和友元訪問 405
C5.1 重載運算符 406
C5.1.1 重載=進行賦值 408
C5.1.2 重載+進行連接 410
C5.2 友元訪問和<<的重載 411
第15章 樹 415
15.1 術語 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 創建二叉查找樹 435
15.3.4 遍曆二叉查找樹 437
15.3.5 二叉查找樹操作的效率 437
第16章 樹的實現 443
16.1 二叉樹中的節點 444
16.1.1 基於數組的錶示 444
16.1.2 基於鏈錶的錶示 446
16.2 ADT二叉樹基於鏈錶的實現 447
16.2.1 頭文件 447
16.2.2 實現 450
16.3 ADT二叉查找樹基於鏈錶的實現 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 實現迭代器 483
C6.2 迭代器的高級功能 485
第17章 堆 489
17.1 ADT堆 490
17.2 堆的基於數組的實現 493
17.2.1 基於數組的堆操作的算法 494
17.2.2 實現 498
17.3 ADT優先隊列的堆實現 502
17.4 堆排序 504
第18章 字典及其實現 511
18.1 ADT字典 512
18.2 可能的實現 517
18.2.1 ADT字典的基於數組的有序實現 519
18.2.2 ADT字典的二叉查找樹實現 521
18.3 選擇實現 523
18.4 散列 529
18.4.1 散列函數 532
18.4.2 解決衝突 534
18.4.3 散列的效率 539
18.4.4 如何確立散列函數 542
18.4.5 字典遍曆：散列的低效操作 543
18.4.6 使用散列和分離鏈實現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樹中插入數據 558
19.2.4 從2-3樹中刪除數據 562
19.3 2-3-4樹 567
19.3.1 查找和遍曆2-3-4樹 569
19.3.2 在2-3-4樹中插入數據 569
19.3.3 從2-3-4樹中刪除數據 572
19.4 紅-黑樹 573
19.4.1 查找和遍曆紅-黑樹 575
19.4.2 紅-黑樹的插入和刪除 575
19.5 AVL樹 577
第20章 圖 583
20.1 術語 584
20.2 將圖作為ADT 587
20.3 圖的遍曆 591
20.3.1 深度優先查找 592
20.3.2 廣度優先查找 593
20.4 圖的應用 595
20.4.1 拓撲排序 595
20.4.2 生成樹 598
20.4.3 最小生成樹 600
20.4.4 最短路徑 603
20.4.5 迴路 606
20.4.6 一些復雜問題 608
第21章 外部存儲中的數據處理 615
21.1 瞭解外部存儲 616
21.2 排序外部文件的數據 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 標準模闆庫 647
C7.1 STL容器 648
C7.1.1 STL容器適配器 649
C7.1.2 順序容器 650
C7.1.3 關聯容器 654
C7.2 STL算法 657
附錄A 迴顧C++基礎 659
附錄B 編程中的重要主題 697
附錄C 統一建模語言 719
附錄D 軟件生命周期 727
附錄E 數學歸納法 733
附錄F 算法驗證 737
附錄G C++文件基礎 741
附錄H C++頭文件和標準函數 751
附錄I C++文檔係統 755
附錄J ASCII字符代碼 757
附錄K 針對Java編程人員的C++知識 759
附錄L 針對Python編程人員的C++
知識 767
· · · · · · (收起)