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

定　價：￥86.00

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

購買這本書可以去

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

內(nèi)容簡介

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

作者簡介

暫缺《數(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ù)傳遞機制 7
1.2.6 常量基元數(shù)組 9
1.2.7 多維數(shù)組 9
1.2.8 標準庫類型string 9
1.3 C++中的指針語法 10
1.4 動態(tài)內(nèi)存管理 14
1.4.1 new運算符 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ù)、深復制與淺復制 21
1.6.3 非鄰接鏈表：鏈表 23
小結(jié) 24
學習目標 24
常見錯誤 25
網(wǎng)上資源 26
練習 26
簡答題 26
實踐題 28
編程項目 28
參考文獻 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 接口和實現(xiàn)的分離 35
2.2.4 析構(gòu)函數(shù)、復制構(gòu)造函數(shù)和賦值運算符（=） 38
2.2.5 默認的構(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 運算符重載 49
2.3.4 輸入、輸出和友元 52
2.4 一些常用術語 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ào)用？
哪些采用了默認行為 65
2.8 組合 66
小結(jié) 67
學習目標 68
常見錯誤 69
Internet資源 70
練習 70
簡答題 70
理論題 71
編程項目 72
參考文獻 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 實現(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ù)、復制賦值和復制構(gòu)造函數(shù) 89
3.6 Fancy模板 89
3.6.1 多平臺參數(shù) 89
3.6.2 默認的模板參數(shù) 90
3.6.3 保留字typename 90
3.7 與模板有關的bug 90
3.7.1 錯誤消息和改變的規(guī)則 91
3.7.2 模板匹配算法 91
3.7.3 模板中的嵌套類 91
3.7.4 類模板中的靜態(tài)成員 91
小結(jié) 91
學習目標 91
常見錯誤 92
Internet資源 92
練習 93
簡答題 93
實踐題 93
編程項目 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)綁定和動態(tài)綁定 101
4.2.6 默認的構(gòu)造函數(shù)、復制構(gòu)造函數(shù)、復制賦值運算符和析構(gòu)函數(shù) 103
4.2.7 構(gòu)造函數(shù)和析構(gòu)函數(shù)virtual或非virtual 104
4.2.8 抽象方法和抽象類 105
4.3 例子：擴展Shape類 108
4.4 微妙的C++細節(jié) 112
4.4.1 參數(shù)的靜態(tài)綁定 113
4.4.2 默認參數(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
學習目標 119
常見錯誤 119
Internet資源 120
練習 120
簡答題 120
實踐題 122
編程項目 122
參考文獻 122
第5章設計模式 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 迭代器設計1 137
5.4.2 迭代器設計2 139
5.4.3 基于繼承的迭代器和
factory 139
5.5 合成（對） 144
5.6 觀察者 144
小結(jié) 148
學習目標 148
常見錯誤 149
Internet資源 149
練習 150
簡答題 150
理論題 150
實踐題 150
編程項目 152
參考文獻 152
第二部分算法和構(gòu)建代碼塊
第6章算法分析 153
6.1 什么是算法分析 153
6.2 算法運行時間的例子 156
6.3 最大連續(xù)子數(shù)列和問題 157
6.3.1 直觀的O(N3)算法 158
6.3.2 改進的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 算法分析的檢驗 173
6.8 Big-Oh分析的限制 174
小結(jié) 174
學習目標 174
常見錯誤 175
Internet資源 175
練習 176
簡答題 176
理論題 177
實踐題 179
編程項目 179
參考文獻 180
第7章標準模板庫 182
7.1 簡介 182
7.2 堆棧和隊列 183
7.2.1 堆棧 184
7.2.2 堆棧和計算機語言 185
7.2.3 隊列 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 實現(xiàn)帶有迭代器的vector 193
7.6 順序表和鏈表 195
7.6.1 list類 195
7.6.2 堆棧和隊列 196
7.7 集合 197
7.8 映射 199
7.9 優(yōu)先隊列 200
小結(jié) 203
學習目標 204
常見錯誤 204
Internet資源 205
練習 205
簡答題 205
理論題 205
實踐題 206
編程項目 206
參考文獻 208
第8章遞歸 209
8.1 遞歸的概念 209
8.2 背景知識：數(shù)學歸納法 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ù)值應用 223
8.4.1 模運算 223
8.4.2 模冪運算 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 分治法運行時間的一般上限 235
8.6 動態(tài)規(guī)劃 237
8.7 回溯法 241
小結(jié) 244
學習目標 244
常見錯誤 245
Internet資源 245
練習 246
簡答題 246
理論題 246
實踐題 247
編程項目 248
參考文獻 249
第9章排序算法 250
9.1 排序為何重要 250
9.2 預備知識 251
9.3 插入排序和其他簡單排序的分析 252
9.4 希爾排序 254
9.5 歸并排序 257
9.5.1 排過序的數(shù)組的線性時間合并 257
9.5.2 歸并排序算法 259
9.6 快速排序 261
9.6.1 快速排序算法 261
9.6.2 快速排序的分析 263
9.6.3 支點的選擇 265
9.6.4 分組策略 267
9.6.5 同支點相等的鍵 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
學習目標 279
常見錯誤 279
Internet資源 279
練習 280
簡答題 280
理論題 280
實踐題 281
編程項目 282
參考文獻 283
第10章隨機 285
10.1 為什么我們需要隨機數(shù) 285
10.2 隨機數(shù)生成器 286
10.3 非均勻隨機數(shù) 290
10.4 生成隨機排列 291
10.5 隨機算法 293
10.6 隨機素數(shù)測試 295
小結(jié) 298
學習目標 298
常見錯誤 298
Internet資源 299
練習 299
簡答題 299
理論題 299
實踐題 300
編程項目 300
參考文獻 301
第三部分應用程序
第11章娛樂與游戲 302
11.1 單詞查找拼圖 302
11.1.1 理論 303
11.1.2 C++實現(xiàn) 304
11.2 Tic-Tac-Toe游戲 309
11.2.1 a- b修剪 309
11.2.2 變換表 312
11.2.3 計算機國際象棋 316
小結(jié) 316
學習目標 317
常見錯誤 317
Internet資源 317
練習 317
簡答題 317
理論題 317
實踐題 318
編程項目 318
參考文獻 319
第12章堆棧和編譯器 320
12.1 對稱符號檢查器 320
12.1.1 基本算法 320
12.1.2 實現(xiàn) 321
12.2 簡單計算器 330
12.2.1 后綴自動機 330
12.2.2 中綴到后綴的轉(zhuǎn)換 332
12.2.3 實現(xiàn) 333
12.2.4 表達式樹 341
小結(jié) 343
學習目標 343
常見錯誤 343
Internet資源 343
練習 344
簡答題 344
理論題 344
實踐題 344
編程項目 345
參考文獻 345
第13章實用工具 346
13.1 文件壓縮 346
13.1.1 前綴碼 347
13.1.2 霍夫曼算法 348
13.1.3 實現(xiàn) 350
13.2 交叉引用生成程序 366
13.2.1 基本概念 366
13.2.2 C++實現(xiàn) 366
小結(jié) 370
學習目標 370
常見錯誤 371
Internet資源 371
練習 371
簡答題 371
理論題 371
實踐題 372
編程項目 372
參考文獻 373
第14章仿真 375
14.1 Josephus問題 375
14.1.1 簡單的解決方案 376
14.1.2 一個更有效的算法 376
14.2 事件驅(qū)動仿真 380
14.2.1 基本思想 380
14.2.2 實例：調(diào)制解調(diào)器
庫仿真 381
小結(jié) 388
學習目標 388
常見錯誤 389
Internet資源 389
練習 389
簡答題 389
理論題 389
實踐題 390
編程項目 390
第15章圖和路徑 391
15.1 定義 391
15.2 無權(quán)最短路徑問題 403
15.2.1 理論 403
15.2.2 C++實現(xiàn) 406
15.3 正的有權(quán)最短路徑問題 407
15.3.1 理論：迪杰斯特拉算法 407
15.3.2 C++實現(xiàn) 410
15.4 負的有權(quán)最短路徑問題 412
15.4.1 理論 412
15.4.2 C++實現(xiàn) 413
15.5 無環(huán)圖的路徑問題 414
15.5.1 拓撲排序 415
15.5.2 無環(huán)最短路徑算法的理論 416
15.5.3 C++實現(xiàn) 417
15.5.4 應用：關鍵路徑分析 419
小結(jié) 421
學習目標 422
常見錯誤 422
Internet資源 423
練習 423
簡答題 423
理論證明 423
實踐題 424
編程項目 425
參考文獻 426
第四部分實現(xiàn)
第16章堆棧和隊列 427
16.1 動態(tài)數(shù)組實現(xiàn) 427
16.1.1 堆棧 427
16.1.2 隊列 431
16.2 鏈表實現(xiàn) 436
16.2.1 堆棧 436
16.2.2 隊列 441
16.3 兩種方法的比較 444
16.4 STL堆棧和隊列適配器 445
16.5 雙頭隊列 446
小結(jié) 447
學習目標 447
常見錯誤 448
Internet資源 448
練習 448
簡答題 448
實踐題 449
編程項目 449
第17章鏈表 450
17.1 基本概念 450
17.1.1 header節(jié)點 452
17.1.2 迭代器類 453
17.2 C++實現(xiàn) 454
17.3 雙鏈表和循環(huán)鏈表 462
17.4 排序鏈表 464
17.5 實現(xiàn)STL鏈表類 466
小結(jié) 479
學習目標 480
常見錯誤 480
Internet資源 480
練習 481
簡答題 481
理論題 481
實踐題 482
編程項目 483
第18章樹 485
18.1 一般樹 485
18.1.1 定義 485
18.1.2 實現(xiàn) 486
18.1.3 應用：文件系統(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
學習目標 512
常見錯誤 512
Internet資源 512
練習 513
簡答題 513
理論題 514
實踐題 514
編程項目 514
第19章二叉查找樹 516
19.1 基本概念 516
19.1.1 操作 517
19.1.2 C++實現(xiàn) 518
19.2 順序統(tǒng)計C++實現(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++實現(xiàn) 545
19.5.4 自頂往下刪除 551
19.6 AA-樹 553
19.6.1 插入 554
19.6.2 刪除 556
19.6.3 C++實現(xiàn) 557
19.7 實現(xiàn)STL set類和map類 561
19.8 B樹 575
小結(jié) 580
學習目標 581
常見錯誤 581
Internet資源 582
練習 582
簡答題 582
理論題 583
實踐題 583
編程項目 584
參考文獻 584
第20章散列表 587
20.1 基本概念 587
20.2 散列函數(shù) 588
20.3 線形探測法 590
20.3.1 線性探測法的簡單
分析（naive analysis） 591
20.3.2 實際情況：原始集聚 592
20.3.3 查找運算分析 593
20.4 二次探測法 594
20.4.1 C++實現(xiàn) 598
20.4.2 二次探測法分析 603
20.5 分離鏈接法 603
20.6 散列表與二叉查找樹 604
20.7 散列化應用程序 604
小結(jié) 605
學習目標 605
常見錯誤 606
Internet資源 606
練習 606
簡答題 606
實踐題 607
編程項目 608
參考文獻 608
第21章優(yōu)先級隊列：二叉堆 610
21.1 基本思想 610
21.1.1 結(jié)構(gòu)屬性 611
21.1.2 堆順序?qū)傩?612
21.1.3 允許的操作 613
21.2 基本操作的實現(xiàn) 615
21.2.1 insert操作 615
21.2.2 deleteMin操作 616
21.3 buildHeap操作：線性時間的堆構(gòu)造函數(shù) 619
21.4 STL priority_queue實現(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
學習目標 634
常見錯誤 635
Internet資源 635
練習 635
簡答題 635
理論題 635
實踐題 637
編程項目 637
參考文獻 638
第五部分高級數(shù)據(jù)結(jié)構(gòu)
第22章伸展樹 639
22.1 自我調(diào)整和攤銷分析 639
22.1.1 攤銷時間限制 640
22.1.2 簡單的自我調(diào)整策略 641
22.2 基本的自底往上伸展樹 642
22.3 基本伸展樹操作 644
22.4 自底往上伸展樹分析 645
22.5 自頂往下伸展樹 649
22.6 實現(xiàn)自頂往下伸展樹 652
22.7 伸展樹與其他查找樹的比較 657
小結(jié) 658
學習目標 658
常見錯誤 658
Internet資源 659
練習 659
簡答題 659
理論題 659
實踐題 660
編程項目 660
參考文獻 660
第23章合并優(yōu)先級隊列 661
23.1 偏斜堆 661
23.1.1 合并是基礎 661
23.1.2 簡化的堆排序樹合并 662
23.1.3 偏斜堆：簡單修改 662
23.1.4 偏斜堆分析 663
23.2 對偶堆 665
23.2.1 對偶堆的操作 666
23.2.2 對偶堆的實現(xiàn) 668
23.2.3 應用：Dijkstra最短加權(quán)
路徑算法 674
小結(jié) 676
學習目標 676
常見錯誤 676
Internet資源 677
練習 677
簡答題 677
理論題 677
實踐題 678
編程項目 678
參考文獻 678
第24章不相交集類 680
24.1 等價關系 680
24.2 動態(tài)等價和兩個應用 680
24.2.1 應用：生成迷宮 681
24.2.2 應用：最小伸展樹 684
24.2.3 應用：最近共同祖先問題 686
24.3 快速查找算法 689
24.4 快速合并算法 690
24.4.1 巧妙的合并算法 691
24.4.2 路徑壓縮 693
24.5 C++實現(xiàn) 694
24.6 針對按秩合并與路徑壓縮的
最壞情形 695
合并/查找算法分析 696
小結(jié) 701
學習目標 701
常見錯誤 702
Internet資源 702
練習 702
簡答題 702
理論題 703
實踐題 703
編程項目 703
參考文獻 704
附錄
附錄A C++相關信息 706
A.1 沒有編譯器實現(xiàn)該標準 706
A.2 不常見的C++運算符 706
A.2.1 自增運算符與自減運算符 706
A.2.2 類型轉(zhuǎn)換 707
A.2.3 按位運算符 708
A.2.4 條件運算符 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
常見錯誤 717
附錄B 運算符 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++實現(xiàn)：數(shù)組名稱是一個指針 723
D.1.2 多維數(shù)組 726
D.1.3 char * 類型、const指針和常量字符串 726
D.2 動態(tài)數(shù)組分配：new [ ]和delete [ ] 729
D.3 指針算術運算、指針跳和基本迭代 733
D.3.1 *、&和[ ]優(yōu)先級的含意 734
D.3.2 指針算術的含意 734
D.3.3 指針跳例子 736
D.3.4 使用指針跳的意義 737
常見錯誤 738
Internet資源 738