數(shù)據(jù)結(jié)構(gòu)與問題求解（C++版）

定　價(jià)：￥86.00

作　者：	（美）Mark Allen Weiss著；張麗萍譯
出版社：	清華大學(xué)出版社
叢編項(xiàng)：	國外經(jīng)典教材·計(jì)算機(jī)科學(xué)與技術(shù)
標(biāo)　簽：	數(shù)據(jù)結(jié)構(gòu)

購買這本書可以去

ISBN：	9787302111665	出版時(shí)間：	2005-01-01	包裝：	平裝
開本：	26cm	頁數(shù)：	738頁	字?jǐn)?shù)：

內(nèi)容簡介

　　本書從抽象思想、問題解決以及C編程語言使用的觀點(diǎn)介紹了數(shù)據(jù)結(jié)構(gòu)和算法。本書中包含了C的最新特性，任何地方都可以完全使用標(biāo)準(zhǔn)模板庫（STL）。C允許程序員分開編寫接口和實(shí)現(xiàn)，將它們保存在單獨(dú)編譯的文件中，并隱藏實(shí)現(xiàn)的具體細(xì)節(jié)。本書深入了一層：數(shù)據(jù)結(jié)構(gòu)的接口和實(shí)現(xiàn)在本書的不同部分討論。第一部分（對象和C）、第二部分（算法和構(gòu)建塊）、第三部分（應(yīng)用程序）打基礎(chǔ)，專門討論各種基本概念并提供實(shí)踐中的一些例子。第四部分（實(shí)現(xiàn)）介紹數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。接口與實(shí)現(xiàn)的這種分離促進(jìn)了抽象思想。將類接口放在實(shí)現(xiàn)之前編寫與使用，這就迫使讀者去思考各種數(shù)據(jù)結(jié)構(gòu)的功能性和潛能（例如，在實(shí)現(xiàn)優(yōu)先隊(duì)列之前就使用它了）。特色：加入了C最新的發(fā)展，包含一個(gè)有關(guān)模型的新章節(jié)，并且從頭到尾都使用了vector類。包含在恰當(dāng)時(shí)使用了STL的修訂材料。介紹高級使用C較重要的細(xì)節(jié)的同時(shí)，介紹了類和繼承（這兩者簡化了最初的表示法）的一些新內(nèi)容。闡述了數(shù)據(jù)結(jié)構(gòu)的STL接口，并提供了STL實(shí)現(xiàn)，同時(shí)也提供了不使用STL的簡化過的接口，這使得理解數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識更加簡單，沒有了STL的復(fù)雜性。包含大量的代碼。這些都已被全面重寫并測試過，可兼容當(dāng)前各種各樣的編譯器。本書前言序言本書是為計(jì)算機(jī)科學(xué)專業(yè)的第2學(xué)期的課程而編寫的，從典型的《數(shù)據(jù)結(jié)構(gòu)》（CS-2，即計(jì)算機(jī)科學(xué)專業(yè)第2學(xué)期）開始直到高級的數(shù)據(jù)結(jié)構(gòu)和算法分析。CS-2課程的內(nèi)容經(jīng)歷過一段時(shí)間的演變。盡管多數(shù)人都同意這樣的主題安排，但在具體的細(xì)節(jié)上還是有較大的分歧。獲得一致認(rèn)可的主題是軟件開發(fā)的原則，最突出的是封裝和信息隱藏的概念。理論上，所有的CS-2課程都傾向于包含運(yùn)行時(shí)分析、遞歸、基本的排序方法和初等數(shù)據(jù)結(jié)構(gòu)。許多大學(xué)還開設(shè)了高級課程，主題涉及到高級的數(shù)據(jù)結(jié)構(gòu)、算法、運(yùn)行時(shí)分析。本書中的材料設(shè)計(jì)同時(shí)考慮到這兩種級別，因此讀者不必再另外購買其他教科書。盡管如此，爭論最激烈的還是CS-2中編程語言的選擇以及其他幾項(xiàng)必要的基本選擇，包括：是否這么早就介紹面向?qū)ο蟮脑O(shè)計(jì)或基于對象的設(shè)計(jì)。對數(shù)學(xué)水平的要求。在實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)及其使用之間達(dá)到恰當(dāng)?shù)钠胶恻c(diǎn)，以及與所選語言相關(guān)的編程細(xì)節(jié)。筆者寫本書的目的是，從抽象思維和問題求解的角度來介紹數(shù)據(jù)結(jié)構(gòu)和算法。筆者試圖覆蓋所有與數(shù)據(jù)結(jié)構(gòu)、分析及其C實(shí)現(xiàn)有關(guān)的重要內(nèi)容，同時(shí)對那些理論上似乎很有意義但實(shí)際上很少使用的數(shù)據(jù)結(jié)構(gòu)，則是避而遠(yuǎn)之。幾乎不可能有哪本書能像本書一樣在一門課程里講述所有不同的數(shù)據(jù)結(jié)構(gòu)，包括數(shù)據(jù)結(jié)構(gòu)的使用。因此，筆者設(shè)計(jì)了本教材，以便讓教師能夠靈活地選擇主題。教師需要在實(shí)踐和理論之間尋求平衡，然后選擇最適合課程需要的主題。正如此序言后面所討論的那樣，筆者對課本進(jìn)行了細(xì)致的組織，盡可能地降低了各章之間的依賴性。統(tǒng)一的方法筆者的基本假設(shè)是基于任何語言的軟件開發(fā)工具都有一個(gè)龐大的庫，許多數(shù)據(jù)結(jié)構(gòu)就是這些庫的一部分。筆者預(yù)感到數(shù)據(jù)結(jié)構(gòu)教學(xué)的重心將從實(shí)現(xiàn)轉(zhuǎn)向使用。在本書中，筆者采用了一套獨(dú)特的方法，將數(shù)據(jù)結(jié)構(gòu)分成規(guī)范和實(shí)現(xiàn)，并充分利用已有的數(shù)據(jù)結(jié)構(gòu)庫，即標(biāo)準(zhǔn)模板庫（StandardTemplateLibrary，STL）。在第二部分將會(huì)有一章（第7章）單獨(dú)講述適合大多數(shù)應(yīng)用程序的STL子集。第二部分還講述了基本的分析技術(shù)、遞歸和排序。第三部分介紹使用STL數(shù)據(jù)結(jié)構(gòu)的應(yīng)用程序。直到第四部分已經(jīng)使用數(shù)據(jù)結(jié)構(gòu)之后，才開始介紹STL的實(shí)現(xiàn)。因?yàn)镾TL是C的一部分（較早的編譯器則使用本教材中的STL代碼，請參閱稍后的"代碼可用性"部分），學(xué)生可以使用現(xiàn)有的軟件組件來設(shè)計(jì)大型項(xiàng)目。盡管本書中大量使用了STL，但本書并非針對STL的專著，也不是專門講述STL實(shí)現(xiàn)的入門讀物。本書的重點(diǎn)在于數(shù)據(jù)結(jié)構(gòu)和基本的問題求解技術(shù)。當(dāng)然，數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)中使用的技術(shù)大都適用于STL的實(shí)現(xiàn)，因此在第四部分有幾章介紹了STL的實(shí)現(xiàn)。然而，教師可以選擇第四部分中較簡單的實(shí)現(xiàn)，而不必討論STL協(xié)議。第7章介紹了STL，這對理解第三部分的代碼很有必要。筆者只是使用了一些基本的STL。許多教師更喜歡定義、實(shí)現(xiàn)，然后使用每個(gè)數(shù)據(jù)結(jié)構(gòu)的傳統(tǒng)方法。由于第三部分和第四部分中的材料之間并不存在依賴關(guān)系，因此可以利用本書輕松地教授傳統(tǒng)方法。預(yù)備技能閱讀本書的學(xué)生應(yīng)該了解一門面向?qū)ο蠡蛎嫦蜻^程的編程語言。必須了解編程語言的基本特征，包括基元數(shù)據(jù)類型、運(yùn)算符、控制結(jié)構(gòu)、函數(shù)（方法）、輸入和輸出（但并不需要了解數(shù)組和類）。已初步接觸過C或Java的學(xué)生可能會(huì)覺得前兩章的某些內(nèi)容很簡單。但其他部分所講的C技術(shù)細(xì)節(jié)則相對比較深?yuàn)W，在入門課程中可能不會(huì)講到這些知識。學(xué)習(xí)了其他語言課程的學(xué)生應(yīng)該從第1章開始學(xué)習(xí)，并且應(yīng)該仔細(xì)研讀。還應(yīng)該查閱附錄A，因?yàn)楦戒汚中討論了某些專屬于C的語言問題。如果喜歡同時(shí)參閱一本C參考書，可以參考第1章中給出的推薦書目。離散數(shù)學(xué)方面的知識對學(xué)習(xí)本書很有幫助，但并非絕對必要。本書給出了幾個(gè)數(shù)學(xué)證明，但對于更復(fù)雜的證明，則提示讀者復(fù)習(xí)有關(guān)的數(shù)學(xué)知識。第8章以及第19～24章需要具備一定程度的數(shù)學(xué)技能。教師可以輕松地選擇跳過數(shù)學(xué)證明，而只介紹證明結(jié)果。本書中所有的數(shù)學(xué)證明都被清晰地標(biāo)出來了，并與本書正文部分分開。

作者簡介

暫缺《數(shù)據(jù)結(jié)構(gòu)與問題求解（C++版）》作者簡介

圖書目錄

第一部分對象和C++
第1章數(shù)組、指針和結(jié)構(gòu) 1
1.1 什么是指針、數(shù)組和結(jié)構(gòu) 1
1.2 數(shù)組和字符串 2
1.2.1 頭等對象與次等對象的對比 2
1.2.2 使用Vector 3
1.2.3 調(diào)整Vector大小 5
1.2.4 push_back大小與容量 7
1.2.5 參數(shù)傳遞機(jī)制 7
1.2.6 常量基元數(shù)組 9
1.2.7 多維數(shù)組 9
1.2.8 標(biāo)準(zhǔn)庫類型string 9
1.3 C++中的指針語法 10
1.4 動(dòng)態(tài)內(nèi)存管理 14
1.4.1 new運(yùn)算符 15
1.4.2 垃圾收集與delete 15
1.4.3 過期指針、雙重刪除及其他 16
1.5 引用變量 17
1.6 結(jié)構(gòu) 19
1.6.1 指向結(jié)構(gòu)的指針 21
1.6.2 外部數(shù)據(jù)與內(nèi)部數(shù)據(jù)、深復(fù)制與淺復(fù)制 21
1.6.3 非鄰接鏈表：鏈表 23
小結(jié) 24
學(xué)習(xí)目標(biāo) 24
常見錯(cuò)誤 25
網(wǎng)上資源 26
練習(xí) 26
簡答題 26
實(shí)踐題 28
編程項(xiàng)目 28
參考文獻(xiàn) 28
第2章對象和類 30
2.1 什么是面向?qū)ο缶幊?30
2.2 類的基本語法 31
2.2.1 類成員 31
2.2.2 附加的構(gòu)造函數(shù)語法和訪問函數(shù) 33
2.2.3 接口和實(shí)現(xiàn)的分離 35
2.2.4 析構(gòu)函數(shù)、復(fù)制構(gòu)造函數(shù)和賦值運(yùn)算符（=） 38
2.2.5 默認(rèn)的構(gòu)造函數(shù) 43
2.3 附加的C++類特性 43
2.3.1 調(diào)整后的構(gòu)造函數(shù)中的初始化與賦值 47
2.3.2 類型轉(zhuǎn)換 48
2.3.3 運(yùn)算符重載 49
2.3.4 輸入、輸出和友元 52
2.4 一些常用術(shù)語 54
2.4.1 避免使用友元 54
2.4.2 靜態(tài)類成員 55
2.4.3 整型類常量的陷阱 55
2.5 異常 56
2.6 String類 57
2.7 要點(diǎn)重述：進(jìn)行了哪些調(diào)用？
哪些采用了默認(rèn)行為 65
2.8 組合 66
小結(jié) 67
學(xué)習(xí)目標(biāo) 68
常見錯(cuò)誤 69
Internet資源 70
練習(xí) 70
簡答題 70
理論題 71
編程項(xiàng)目 72
參考文獻(xiàn) 75
第3章模板 76
3.1 模板的概念 76
3.2 函數(shù)模板 76
3.3 排序函數(shù)模板 78
3.4 類模板 81
3.4.1 MemoryCell模板 81
3.4.2 實(shí)現(xiàn)vector類模板 85
3.5 模板的模板：matrix類 87
3.5.1 數(shù)據(jù)成員、構(gòu)造函數(shù)和基本附件 88
3.5.2 operator [ ] 89
3.5.3 析構(gòu)函數(shù)、復(fù)制賦值和復(fù)制構(gòu)造函數(shù) 89
3.6 Fancy模板 89
3.6.1 多平臺參數(shù) 89
3.6.2 默認(rèn)的模板參數(shù) 90
3.6.3 保留字typename 90
3.7 與模板有關(guān)的bug 90
3.7.1 錯(cuò)誤消息和改變的規(guī)則 91
3.7.2 模板匹配算法 91
3.7.3 模板中的嵌套類 91
3.7.4 類模板中的靜態(tài)成員 91
小結(jié) 91
學(xué)習(xí)目標(biāo) 91
常見錯(cuò)誤 92
Internet資源 92
練習(xí) 93
簡答題 93
實(shí)踐題 93
編程項(xiàng)目 93
第4章繼承 94
4.1 什么是繼承 94
4.2 繼承的基本知識 97
4.2.1 可視性規(guī)則 98
4.2.2 構(gòu)造函數(shù)和基類初始化 98
4.2.3 添加成員 99
4.2.4 覆蓋方法 101
4.2.5 靜態(tài)綁定和動(dòng)態(tài)綁定 101
4.2.6 默認(rèn)的構(gòu)造函數(shù)、復(fù)制構(gòu)造函數(shù)、復(fù)制賦值運(yùn)算符和析構(gòu)函數(shù) 103
4.2.7 構(gòu)造函數(shù)和析構(gòu)函數(shù)virtual或非virtual 104
4.2.8 抽象方法和抽象類 105
4.3 例子：擴(kuò)展Shape類 108
4.4 微妙的C++細(xì)節(jié) 112
4.4.1 參數(shù)的靜態(tài)綁定 113
4.4.2 默認(rèn)參數(shù) 114
4.4.3 派生類方法隱藏基類方法 114
4.4.4 覆蓋方法的兼容返回類型 115
4.4.5 私有繼承 116
4.4.6 友元 116
4.4.7 值調(diào)用與多態(tài)并不混淆 117
4.5 多重繼承 117
小結(jié) 118
學(xué)習(xí)目標(biāo) 119
常見錯(cuò)誤 119
Internet資源 120
練習(xí) 120
簡答題 120
實(shí)踐題 122
編程項(xiàng)目 122
參考文獻(xiàn) 122
第5章設(shè)計(jì)模式 123
5.1 模式的概念 123
5.2 Functor（函數(shù)對象） 124
5.3 適配器和包裝器 129
5.3.1 指針包裝器 129
5.3.2 常數(shù)引用包裝器 134
5.3.3 適配器更改接口 135
5.4 迭代器 136
5.4.1 迭代器設(shè)計(jì)1 137
5.4.2 迭代器設(shè)計(jì)2 139
5.4.3 基于繼承的迭代器和
factory 139
5.5 合成（對） 144
5.6 觀察者 144
小結(jié) 148
學(xué)習(xí)目標(biāo) 148
常見錯(cuò)誤 149
Internet資源 149
練習(xí) 150
簡答題 150
理論題 150
實(shí)踐題 150
編程項(xiàng)目 152
參考文獻(xiàn) 152
第二部分算法和構(gòu)建代碼塊
第6章算法分析 153
6.1 什么是算法分析 153
6.2 算法運(yùn)行時(shí)間的例子 156
6.3 最大連續(xù)子數(shù)列和問題 157
6.3.1 直觀的O(N3)算法 158
6.3.2 改進(jìn)的O(N2)算法 160
6.3.3 線性算法 161
6.4 一般的Big-Oh規(guī)則 164
6.5 對數(shù) 167
6.6 靜態(tài)查找問題 169
6.6.1 順序查找 169
6.6.2 折半查找 169
6.6.3 插值查找 172
6.7 算法分析的檢驗(yàn) 173
6.8 Big-Oh分析的限制 174
小結(jié) 174
學(xué)習(xí)目標(biāo) 174
常見錯(cuò)誤 175
Internet資源 175
練習(xí) 176
簡答題 176
理論題 177
實(shí)踐題 179
編程項(xiàng)目 179
參考文獻(xiàn) 180
第7章標(biāo)準(zhǔn)模板庫 182
7.1 簡介 182
7.2 堆棧和隊(duì)列 183
7.2.1 堆棧 184
7.2.2 堆棧和計(jì)算機(jī)語言 185
7.2.3 隊(duì)列 186
7.3 容器和迭代器 187
7.3.1 容器 187
7.3.2 迭代器 188
7.4 STL算法 189
7.4.1 STL函數(shù)對象 189
7.4.2 二分查找法 191
7.4.3 排序 193
7.5 實(shí)現(xiàn)帶有迭代器的vector 193
7.6 順序表和鏈表 195
7.6.1 list類 195
7.6.2 堆棧和隊(duì)列 196
7.7 集合 197
7.8 映射 199
7.9 優(yōu)先隊(duì)列 200
小結(jié) 203
學(xué)習(xí)目標(biāo) 204
常見錯(cuò)誤 204
Internet資源 205
練習(xí) 205
簡答題 205
理論題 205
實(shí)踐題 206
編程項(xiàng)目 206
參考文獻(xiàn) 208
第8章遞歸 209
8.1 遞歸的概念 209
8.2 背景知識：數(shù)學(xué)歸納法 210
8.3 基本遞歸 212
8.3.1 以任意基數(shù)打印數(shù)字 213
8.3.2 遞歸算法有效的原因 215
8.3.3 遞歸算法的作用原理 216
8.3.4 遞歸不宜太多 217
8.3.5 樹 218
8.3.6 附加例子 219
8.4 數(shù)值應(yīng)用 223
8.4.1 模運(yùn)算 223
8.4.2 模冪運(yùn)算 224
8.4.3 最大公約數(shù)和乘法逆元素 225
8.4.4 RSA密碼系統(tǒng) 228
8.5 分治算法 230
8.5.1 最大鄰近子序列和問題 230
8.5.2 基本分治遞歸分析 233
8.5.3 分治法運(yùn)行時(shí)間的一般上限 235
8.6 動(dòng)態(tài)規(guī)劃 237
8.7 回溯法 241
小結(jié) 244
學(xué)習(xí)目標(biāo) 244
常見錯(cuò)誤 245
Internet資源 245
練習(xí) 246
簡答題 246
理論題 246
實(shí)踐題 247
編程項(xiàng)目 248
參考文獻(xiàn) 249
第9章排序算法 250
9.1 排序?yàn)楹沃匾?250
9.2 預(yù)備知識 251
9.3 插入排序和其他簡單排序的分析 252
9.4 希爾排序 254
9.5 歸并排序 257
9.5.1 排過序的數(shù)組的線性時(shí)間合并 257
9.5.2 歸并排序算法 259
9.6 快速排序 261
9.6.1 快速排序算法 261
9.6.2 快速排序的分析 263
9.6.3 支點(diǎn)的選擇 265
9.6.4 分組策略 267
9.6.5 同支點(diǎn)相等的鍵 268
9.6.6 中值劃分 269
9.6.7 小數(shù)組 270
9.6.8 C++快速排序例程 270
9.7 排序選擇 272
9.8 排序的下限 274
9.9 間接排序 275
9.9.1 使用指針將Comparable
副本數(shù)減少為2N 275
9.9.2 避免附加數(shù)組 276
小結(jié) 278
學(xué)習(xí)目標(biāo) 279
常見錯(cuò)誤 279
Internet資源 279
練習(xí) 280
簡答題 280
理論題 280
實(shí)踐題 281
編程項(xiàng)目 282
參考文獻(xiàn) 283
第10章隨機(jī) 285
10.1 為什么我們需要隨機(jī)數(shù) 285
10.2 隨機(jī)數(shù)生成器 286
10.3 非均勻隨機(jī)數(shù) 290
10.4 生成隨機(jī)排列 291
10.5 隨機(jī)算法 293
10.6 隨機(jī)素?cái)?shù)測試 295
小結(jié) 298
學(xué)習(xí)目標(biāo) 298
常見錯(cuò)誤 298
Internet資源 299
練習(xí) 299
簡答題 299
理論題 299
實(shí)踐題 300
編程項(xiàng)目 300
參考文獻(xiàn) 301
第三部分應(yīng)用程序
第11章娛樂與游戲 302
11.1 單詞查找拼圖 302
11.1.1 理論 303
11.1.2 C++實(shí)現(xiàn) 304
11.2 Tic-Tac-Toe游戲 309
11.2.1 a- b修剪 309
11.2.2 變換表 312
11.2.3 計(jì)算機(jī)國際象棋 316
小結(jié) 316
學(xué)習(xí)目標(biāo) 317
常見錯(cuò)誤 317
Internet資源 317
練習(xí) 317
簡答題 317
理論題 317
實(shí)踐題 318
編程項(xiàng)目 318
參考文獻(xiàn) 319
第12章堆棧和編譯器 320
12.1 對稱符號檢查器 320
12.1.1 基本算法 320
12.1.2 實(shí)現(xiàn) 321
12.2 簡單計(jì)算器 330
12.2.1 后綴自動(dòng)機(jī) 330
12.2.2 中綴到后綴的轉(zhuǎn)換 332
12.2.3 實(shí)現(xiàn) 333
12.2.4 表達(dá)式樹 341
小結(jié) 343
學(xué)習(xí)目標(biāo) 343
常見錯(cuò)誤 343
Internet資源 343
練習(xí) 344
簡答題 344
理論題 344
實(shí)踐題 344
編程項(xiàng)目 345
參考文獻(xiàn) 345
第13章實(shí)用工具 346
13.1 文件壓縮 346
13.1.1 前綴碼 347
13.1.2 霍夫曼算法 348
13.1.3 實(shí)現(xiàn) 350
13.2 交叉引用生成程序 366
13.2.1 基本概念 366
13.2.2 C++實(shí)現(xiàn) 366
小結(jié) 370
學(xué)習(xí)目標(biāo) 370
常見錯(cuò)誤 371
Internet資源 371
練習(xí) 371
簡答題 371
理論題 371
實(shí)踐題 372
編程項(xiàng)目 372
參考文獻(xiàn) 373
第14章仿真 375
14.1 Josephus問題 375
14.1.1 簡單的解決方案 376
14.1.2 一個(gè)更有效的算法 376
14.2 事件驅(qū)動(dòng)仿真 380
14.2.1 基本思想 380
14.2.2 實(shí)例：調(diào)制解調(diào)器
庫仿真 381
小結(jié) 388
學(xué)習(xí)目標(biāo) 388
常見錯(cuò)誤 389
Internet資源 389
練習(xí) 389
簡答題 389
理論題 389
實(shí)踐題 390
編程項(xiàng)目 390
第15章圖和路徑 391
15.1 定義 391
15.2 無權(quán)最短路徑問題 403
15.2.1 理論 403
15.2.2 C++實(shí)現(xiàn) 406
15.3 正的有權(quán)最短路徑問題 407
15.3.1 理論：迪杰斯特拉算法 407
15.3.2 C++實(shí)現(xiàn) 410
15.4 負(fù)的有權(quán)最短路徑問題 412
15.4.1 理論 412
15.4.2 C++實(shí)現(xiàn) 413
15.5 無環(huán)圖的路徑問題 414
15.5.1 拓?fù)渑判?415
15.5.2 無環(huán)最短路徑算法的理論 416
15.5.3 C++實(shí)現(xiàn) 417
15.5.4 應(yīng)用：關(guān)鍵路徑分析 419
小結(jié) 421
學(xué)習(xí)目標(biāo) 422
常見錯(cuò)誤 422
Internet資源 423
練習(xí) 423
簡答題 423
理論證明 423
實(shí)踐題 424
編程項(xiàng)目 425
參考文獻(xiàn) 426
第四部分實(shí)現(xiàn)
第16章堆棧和隊(duì)列 427
16.1 動(dòng)態(tài)數(shù)組實(shí)現(xiàn) 427
16.1.1 堆棧 427
16.1.2 隊(duì)列 431
16.2 鏈表實(shí)現(xiàn) 436
16.2.1 堆棧 436
16.2.2 隊(duì)列 441
16.3 兩種方法的比較 444
16.4 STL堆棧和隊(duì)列適配器 445
16.5 雙頭隊(duì)列 446
小結(jié) 447
學(xué)習(xí)目標(biāo) 447
常見錯(cuò)誤 448
Internet資源 448
練習(xí) 448
簡答題 448
實(shí)踐題 449
編程項(xiàng)目 449
第17章鏈表 450
17.1 基本概念 450
17.1.1 header節(jié)點(diǎn) 452
17.1.2 迭代器類 453
17.2 C++實(shí)現(xiàn) 454
17.3 雙鏈表和循環(huán)鏈表 462
17.4 排序鏈表 464
17.5 實(shí)現(xiàn)STL鏈表類 466
小結(jié) 479
學(xué)習(xí)目標(biāo) 480
常見錯(cuò)誤 480
Internet資源 480
練習(xí) 481
簡答題 481
理論題 481
實(shí)踐題 482
編程項(xiàng)目 483
第18章樹 485
18.1 一般樹 485
18.1.1 定義 485
18.1.2 實(shí)現(xiàn) 486
18.1.3 應(yīng)用：文件系統(tǒng) 487
18.2 二叉樹 490
18.3 遞歸和樹 496
18.4 樹遍歷：迭代器類 499
18.4.1 后序遍歷 502
18.4.2 中序遍歷 506
18.4.3 前序遍歷 508
18.4.4 層序遍歷 509
小結(jié) 511
學(xué)習(xí)目標(biāo) 512
常見錯(cuò)誤 512
Internet資源 512
練習(xí) 513
簡答題 513
理論題 514
實(shí)踐題 514
編程項(xiàng)目 514
第19章二叉查找樹 516
19.1 基本概念 516
19.1.1 操作 517
19.1.2 C++實(shí)現(xiàn) 518
19.2 順序統(tǒng)計(jì)C++實(shí)現(xiàn) 526
19.3 分析二叉查找樹操作 530
19.4 AVL樹 533
19.4.1 屬性 534
19.4.2 單旋轉(zhuǎn) 536
19.4.3 雙旋轉(zhuǎn) 538
19.4.4 AVL插入總結(jié) 540
19.5 紅-黑樹 541
19.5.1 自底向上插入 541
19.5.2 自頂向下紅-黑樹 543
19.5.3 C++實(shí)現(xiàn) 545
19.5.4 自頂往下刪除 551
19.6 AA-樹 553
19.6.1 插入 554
19.6.2 刪除 556
19.6.3 C++實(shí)現(xiàn) 557
19.7 實(shí)現(xiàn)STL set類和map類 561
19.8 B樹 575
小結(jié) 580
學(xué)習(xí)目標(biāo) 581
常見錯(cuò)誤 581
Internet資源 582
練習(xí) 582
簡答題 582
理論題 583
實(shí)踐題 583
編程項(xiàng)目 584
參考文獻(xiàn) 584
第20章散列表 587
20.1 基本概念 587
20.2 散列函數(shù) 588
20.3 線形探測法 590
20.3.1 線性探測法的簡單
分析（naive analysis） 591
20.3.2 實(shí)際情況：原始集聚 592
20.3.3 查找運(yùn)算分析 593
20.4 二次探測法 594
20.4.1 C++實(shí)現(xiàn) 598
20.4.2 二次探測法分析 603
20.5 分離鏈接法 603
20.6 散列表與二叉查找樹 604
20.7 散列化應(yīng)用程序 604
小結(jié) 605
學(xué)習(xí)目標(biāo) 605
常見錯(cuò)誤 606
Internet資源 606
練習(xí) 606
簡答題 606
實(shí)踐題 607
編程項(xiàng)目 608
參考文獻(xiàn) 608
第21章優(yōu)先級隊(duì)列：二叉堆 610
21.1 基本思想 610
21.1.1 結(jié)構(gòu)屬性 611
21.1.2 堆順序?qū)傩?612
21.1.3 允許的操作 613
21.2 基本操作的實(shí)現(xiàn) 615
21.2.1 insert操作 615
21.2.2 deleteMin操作 616
21.3 buildHeap操作：線性時(shí)間的堆構(gòu)造函數(shù) 619
21.4 STL priority_queue實(shí)現(xiàn) 622
21.5 高級操作：decreaseKey和merge 625
21.6 內(nèi)部排序：堆排序 625
21.7 外部排序 628
21.7.1 我們?yōu)槭裁葱枰碌乃惴?628
21.7.2 外部排序模型 628
21.7.3 簡單的算法 629
21.7.4 多路歸并 630
21.7.5 多相歸并 631
21.7.6 置換選擇 632
小結(jié) 634
學(xué)習(xí)目標(biāo) 634
常見錯(cuò)誤 635
Internet資源 635
練習(xí) 635
簡答題 635
理論題 635
實(shí)踐題 637
編程項(xiàng)目 637
參考文獻(xiàn) 638
第五部分高級數(shù)據(jù)結(jié)構(gòu)
第22章伸展樹 639
22.1 自我調(diào)整和攤銷分析 639
22.1.1 攤銷時(shí)間限制 640
22.1.2 簡單的自我調(diào)整策略 641
22.2 基本的自底往上伸展樹 642
22.3 基本伸展樹操作 644
22.4 自底往上伸展樹分析 645
22.5 自頂往下伸展樹 649
22.6 實(shí)現(xiàn)自頂往下伸展樹 652
22.7 伸展樹與其他查找樹的比較 657
小結(jié) 658
學(xué)習(xí)目標(biāo) 658
常見錯(cuò)誤 658
Internet資源 659
練習(xí) 659
簡答題 659
理論題 659
實(shí)踐題 660
編程項(xiàng)目 660
參考文獻(xiàn) 660
第23章合并優(yōu)先級隊(duì)列 661
23.1 偏斜堆 661
23.1.1 合并是基礎(chǔ) 661
23.1.2 簡化的堆排序樹合并 662
23.1.3 偏斜堆：簡單修改 662
23.1.4 偏斜堆分析 663
23.2 對偶堆 665
23.2.1 對偶堆的操作 666
23.2.2 對偶堆的實(shí)現(xiàn) 668
23.2.3 應(yīng)用：Dijkstra最短加權(quán)
路徑算法 674
小結(jié) 676
學(xué)習(xí)目標(biāo) 676
常見錯(cuò)誤 676
Internet資源 677
練習(xí) 677
簡答題 677
理論題 677
實(shí)踐題 678
編程項(xiàng)目 678
參考文獻(xiàn) 678
第24章不相交集類 680
24.1 等價(jià)關(guān)系 680
24.2 動(dòng)態(tài)等價(jià)和兩個(gè)應(yīng)用 680
24.2.1 應(yīng)用：生成迷宮 681
24.2.2 應(yīng)用：最小伸展樹 684
24.2.3 應(yīng)用：最近共同祖先問題 686
24.3 快速查找算法 689
24.4 快速合并算法 690
24.4.1 巧妙的合并算法 691
24.4.2 路徑壓縮 693
24.5 C++實(shí)現(xiàn) 694
24.6 針對按秩合并與路徑壓縮的
最壞情形 695
合并/查找算法分析 696
小結(jié) 701
學(xué)習(xí)目標(biāo) 701
常見錯(cuò)誤 702
Internet資源 702
練習(xí) 702
簡答題 702
理論題 703
實(shí)踐題 703
編程項(xiàng)目 703
參考文獻(xiàn) 704
附錄
附錄A C++相關(guān)信息 706
A.1 沒有編譯器實(shí)現(xiàn)該標(biāo)準(zhǔn) 706
A.2 不常見的C++運(yùn)算符 706
A.2.1 自增運(yùn)算符與自減運(yùn)算符 706
A.2.2 類型轉(zhuǎn)換 707
A.2.3 按位運(yùn)算符 708
A.2.4 條件運(yùn)算符 710
A.3 命令參數(shù) 710
A.4 輸入和輸出 710
A.4.1 基本的流操作 711
A.4.2 順序文件 714
A.4.3 字符串流 714
A.5 名字空間 716
A.6 C++新特性 717
常見錯(cuò)誤 717
附錄B 運(yùn)算符 719
附錄C 某些庫例程 720
C.1 <ctype.h>和<cctype>中聲明的例程 720
C.2 <limits.h>和<climits>中聲明的常量 720
C.3 <math.h>和<cmath>中聲明的例程 721
C.4 <stdlib.h>和<cstdlib>中聲明的例程 721
附錄D C++中的基元數(shù)組 723
D.1 基元數(shù)組 723
D.1.1 C++實(shí)現(xiàn)：數(shù)組名稱是一個(gè)指針 723
D.1.2 多維數(shù)組 726
D.1.3 char * 類型、const指針和常量字符串 726
D.2 動(dòng)態(tài)數(shù)組分配：new [ ]和delete [ ] 729
D.3 指針?biāo)阈g(shù)運(yùn)算、指針跳和基本迭代 733
D.3.1 *、&和[ ]優(yōu)先級的含意 734
D.3.2 指針?biāo)阈g(shù)的含意 734
D.3.3 指針跳例子 736
D.3.4 使用指針跳的意義 737
常見錯(cuò)誤 738
Internet資源 738