本書全面系統地介紹了計算機科學教育中的一個重要組成部分——數據結構，并以C++語言實現相關的算法。書中主要強調了數據結構和算法之間的聯系，使用面向對象的方法介紹數據結構，其內容包括算法的復雜度分析、鏈表、棧隊列、遞歸技術、二叉樹、圖、排序以及散列。本書還清楚地闡述了同類教材中較少提到的內存管理、數據壓縮和字符串匹配主題。書中包含大量的示例分析和圖形，便于讀者進一步理解和鞏固所學的知識。
前 言
數據結構知識是計算機科學教育的一個基本組成部分，其他許多計算機科學領域都構建在這個基礎之上。對于想從事實際的軟件設計、實現、測試、維護工作的學生而言，掌握基本數據結構的知識是非常必要的。本書介紹的內容將會給從事以上工作的讀者提供必要的知識。
本書突出了數據結構中的三個重要方面。首先，強調了數據結構與其算法之間的聯系，包括算法的復雜度分析。接著，依照當前的設計和實現范例，使用面向對象的方法來介紹數據結構，特別強調了有助于封裝與分解的信息隱藏原理。最后，本書的一個重要組成部分是數據結構的實現，它選擇C++作為編程語言。
C++語言是C語言面向對象的后裔，在業界和學術界得到了廣泛的應用，是一種非常優秀的編程語言。自然地，我們就選用C++來介紹數據結構。而且，由于C++語言在應用程序設計中的廣泛使用以及這門語言的面向對象特性，使用它來講授數據結構和算法課程(即使是入門級的課程)是非常合理的。
本書大多數章節都包括一個案例分析，它闡明了一個完整的、使用特定算法和數據結構的環境。為了說明所論述的主題的廣泛應用范圍，這些案例分析都是從計算機科學的不同領域中挑選出來的，包括解釋程序、符號計算和文件處理。
本書自始至終包含了簡要的C++程序例子，舉例說明數據結構在實踐中的重要性。然而，理論分析同樣也很重要，所以算法的探討都包含了對算法效率的分析。
要特別留意關于遞歸的介紹，因為即使是最高明的學生，在這個方面也會出現一些問題。經驗表明，如果考慮運行時棧的話，就可以極好地說明遞歸的含義。我們不但在遞歸一章里在跟蹤遞歸函數時顯示出了棧的變化，在其他章節里也說明了棧的變化。比如說，如果不解釋系統在運行時棧上所做的工作，甚至一個短小的樹遍歷函數也可能難于理解。在討論數據結構和算法時，脫離系統，只從純理論的角度出發是沒有什么用處的。
這本書討論的重點是數據結構，而附帶介紹其他一些主題僅僅是為了更好地理解數據結構。算法都是從數據結構的角度來討論的，所以沒有對各種算法進行全面的討論，也沒有列出介紹一個算法所需要的全部內容。然而，如前所述，本書將深入論述遞歸。另外，對算法的復雜度分析也介紹得比較詳細。
第1和3~8章介紹了許多不同的數據結構以及使用這些數據結構的算法，分析了每一種算法的效率，同時給出了改進算法的建議。
● 第1章介紹了面向對象程序設計的基本原理，介紹了動態內存分配、指針的使用以及標準模板庫(Standard Template Library，STL)。
● 第2章講述了一些評價算法效率的方法。
● 第3章介紹了不同類型的鏈表，著重闡述了其指針實現。
● 第4章介紹了棧、隊列及其應用。
● 第5章對遞歸進行了詳細討論。論述了不同類型的遞歸，并剖析了其中的一個遞歸
調用。
● 第6章討論了二叉樹，包括二叉樹的實現、遍歷和搜索。在這一章中還介紹了平衡樹。
● 第7章詳細介紹了更一般化的樹，比如森林、2-4樹、B樹。
● 第8章介紹圖。
第9~12章給出了前面章節所介紹的數據結構的不同應用，并強調了這些應用在數據結構方面的問題。
● 第9章詳細介紹了排序，以及一些基礎的和非基礎的方法。
● 第10章討論了散列，它是搜索算法中最重要的主題之一。在強調數據結構使用的同時介紹了各種各樣的技術。
● 第11章討論了數據壓縮算法和相應的數據結構。
● 第12章介紹了內存管理的多種方法和相應的數據結構。
● 第13章介紹了字符串的精確匹配和模糊匹配的許多算法。
● 附錄A詳細介紹了在第2章中提到的大O符號。
● 附錄B介紹了標準模板庫(STL)中的標準算法。
● 附錄C證明了Cook理論，并用一個例子進行了說明。
每一章都包含了對一些材料的討論，并配以合適的圖表和表格。除第2章外，所有的章節都包括一個案例分析，這個案例分析是該章所討論的特性的一個范例。所有的案例分析都在PC上用Visual C++編譯器測試過，還在Unix上用g++編譯器測試過，只有von Koch snowflake除外，它只在PC上用Visual C++測試過。每一章的最后是一些不同難度的練習題。除了第2章之外，所有的章節都包括了程序設計作業以及一些最新的相關參考書籍。
第1~6章(2.9、3.4、6.4.3、6.7、6.8節除外)包含了構成任何數據結構課程基礎的核心內容。應該按照順序來學習這些章。其后的6章內容可以按照任意次序學習。一個學期的課程可以包括1~6章、第9章，以及10.1和10.2節。整本書可以在一個學年中學完。
本書中示例程序的源代碼可以通過Web站點http://www.course.com或http://www. tupwk.com.cn /downpage進行訪問。
第3版的改動
新版本擴展了舊版本，主要包括一些當前未涉及到的新主題，如下：
● 第13章中的模式匹配算法
● 2.10節粗略介紹了NP完整性，8.12節列舉了NP完整性的問題范例，附錄C討論了Cook理論
● 一些新圖(8.9.1節、8.10.1節、8.10.2節和8.11節中的某些圖)
● 7.1.7節討論了vh樹的刪除算法
在整本書中還有許多小的改動。
目 錄
第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.6 C++和面向對象程序設計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.10 NP完整性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.1 DSW算法205
6.7.2 AVL樹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.1 B樹家族243
7.1.1 B樹244
7.1.2 B*樹252
7.1.3 B+樹253
7.1.4 前綴B+樹255
7.1.5 位樹257
7.1.6 R樹258
7.1.7 2-4樹260
7.1.8 標準模板庫中的集和多集270
7.1.9 標準模板庫中的映射和多
映射274
7.2 trie278
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.1 Cichelli方法426
10.4.2 FHCD算法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.2 Huffman編碼447
11.3 Run-Length編碼方式458
11.4 Ziv-Lempel編碼方式459
11.5 案例分析：Huffman方法
和Run-Length編碼方式462
11.6 習題471
11.7 程序設計作業471
第12章 內存管理474
12.1 sequential-fit方法475
12.2 Nonsequential-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.2 Knuth-Morris-Pratt算法512
13.1.3 Boyer-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 計算大O566
A.1 調和數序列n566
A.2 函數的近似值566
A.3 快速排序中平均情況的大O568
A.4 隨機二叉樹中的平均路徑
長度569
A.5 AVL樹中的節點數570
附錄B 標準模板庫中的算法572
附錄C NP完整性581
新書資訊