《數據結構與問題求解C 版（第2版）》是出版於2006-年9月5日的一本書。
基本介紹
- 書名：《數據結構與問題求解C 版（第2版）》
- ISBN：9787302111665
- 定價：86元
- 出版社：清華大學出版社
- 出版時間：2006年9月5日
- 裝幀：平裝
圖書簡介,目錄,
圖書簡介
從抽象思想、問題解決以及C++程式語言使用的觀點介紹了數據結構和算法。本書中包含了C++的最新特性，任何地方都可以完全使用標準模板庫（STL）。
C++允許程式設計師分開編寫接口和實現，將它們保存在單獨編譯的檔案中，並隱藏實現的具體細節。本書深入了一層：數據結構的接口和實現在本書的不同部分討論。第一部分（對象和C++）、第二部分（算法和構建塊）、第三部分（應用程式）打基礎，專門討論各種基本概念並提供實踐中的一些例子。第四部分（實現）介紹數據結構的實現。接口與實現的這種分離促進了抽象思想。將類接口放在實現之前編寫與使用，這就迫使讀者去思考各種數據結構的功能性和潛能（例如，在實現優先佇列之前就使用它了）。
目錄
第一部分對象和C++
第1章數組、指針和結構 1
1.1什麼是指針、數組和結構 1
1.2數組和字元串 2
1.2.1頭等對象與次等
對象的對比 2
1.2.2使用Vector 3
1.2.3調整Vector大小 5
1.2.4push_back大小與容量 7
1.2.5參數傳遞機制 7
1.2.6常量基元數組 9
1.2.7多維數組 9
1.2.8標準庫類型string 9
1.3C++中的指針語法 10
1.4動態記憶體管理 14
1.4.1new運算符 15
1.4.2垃圾收集與delete 15
1.4.3過期指針、雙重刪除
及其他 16
1.5引用變數 17
1.6結構 19
1.6.1指向結構的指針 21
1.6.2外部數據與內部數據、
深複製與淺複製 21
1.6.3非鄰接鍊表：鍊表 23
小結 24
學習目標 24
常見錯誤 25
網上資源 26
練習 26
簡答題 26
實踐題 28
編程項目 28
參考文獻 28
第2章對象和類 30
2.1什麼是面向對象編程 30
2.2類的基本語法 31
2.2.1類成員 31
2.2.2附加的構造函式語法和
訪問函式 33
2.2.3接口和實現的分離 35
2.2.4析構函式、複製構造函式
和賦值運算符（=） 38
2.2.5默認的構造函式 43
2.3附加的C++類特性 43
2.3.1調整後的構造函式中的
初始化與賦值 47
2.3.2類型轉換 48
2.3.3運算符重載 49
2.3.4輸入、輸出和友元 52
2.4一些常用術語 54
2.4.1避免使用友元 54
2.4.2靜態類成員 55
2.4.3整型類常量的陷阱 55
2.5異常 56
2.6String類 57
2.7要點重述：進行了哪些調用？
哪些採用了默認行為 65
2.8組合 66
小結 67
學習目標 68
常見錯誤 69
Internet資源 70
練習 70
簡答題 70
理論題 71
編程項目 72
參考文獻 75
第3章模板 76
3.1模板的概念 76
3.2函式模板 76
3.3排序函式模板 78
3.4類模板 81
3.4.1MemoryCell模板 81
3.4.2實現vector類模板 85
3.5模板的模板：matrix類 87
3.5.1數據成員、構造函式和
基本附屬檔案 88
3.5.2operator[] 89
3.5.3析構函式、複製賦值和
複製構造函式 89
3.6Fancy模板 89
3.6.1多平台參數 89
3.6.2默認的模板參數 90
3.6.3保留字typename 90
3.7與模板有關的bug 90
3.7.1錯誤訊息和改變的規則 91
3.7.2模板匹配算法 91
3.7.3模板中的嵌套類 91
3.7.4類模板中的靜態成員 91
小結 91
學習目標 91
常見錯誤 92
Internet資源 92
練習 93
簡答題 93
實踐題 93
編程項目 93
第4章繼承 94
4.1什麼是繼承 94
4.2繼承的基本知識 97
4.2.1可視性規則 98
4.2.2構造函式和基類初始化 98
4.2.3添加成員 99
4.2.4覆蓋方法 101
4.2.5靜態綁定和動態綁定 101
4.2.6默認的構造函式、複製構造
函式、複製賦值運
算符和析構函式 103
4.2.7構造函式和析構函式
virtual或非virtual 104
4.2.8抽象方法和抽象類 105
4.3例子：擴展Shape類 108
4.4微妙的C++細節 112
4.4.1參數的靜態綁定 113
4.4.2默認參數 114
4.4.3派生類方法隱藏
基類方法 114
4.4.4覆蓋方法的兼容返回
類型 115
4.4.5私有繼承 116
4.4.6友元 116
4.4.7值調用與多態並不混淆 117
4.5多重繼承 117
小結 118
學習目標 119
常見錯誤 119
Internet資源 120
練習 120
簡答題 120
實踐題 122
編程項目 122
參考文獻 122
第5章設計模式 123
5.1模式的概念 123
5.2Functor（函式對象） 124
5.3適配器和包裝器 129
5.3.1指針包裝器 129
5.3.2常數引用包裝器 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
小結 148
學習目標 148
常見錯誤 149
Internet資源 149
練習 150
簡答題 150
理論題 150
實踐題 150
編程項目 152
參考文獻 152
第二部分算法和構建代碼塊
第6章算法分析 153
6.1什麼是算法分析 153
6.2算法運行時間的例子 156
6.3最大連續子數列和問題 157
6.3.1直觀的O(N3)算法 158
6.3.2改進的O(N2)算法 160
6.3.3線性算法 161
6.4一般的Big-Oh規則 164
6.5對數 167
6.6靜態查找問題 169
6.6.1順序查找 169
6.6.2折半查找 169
6.6.3插值查找 172
6.7算法分析的檢驗 173
6.8Big-Oh分析的限制 174
小結 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.4STL算法 189
7.4.1STL函式對象 189
7.4.2二分查找法 191
7.4.3排序 193
7.5實現帶有疊代器的vector 193
7.6順序表和鍊表 195
7.6.1list類 195
7.6.2堆疊和佇列 196
7.7集合 197
7.8映射 199
7.9優先佇列 200
小結 203
學習目標 204
常見錯誤 204
Internet資源 205
練習 205
簡答題 205
理論題 205
實踐題 206
編程項目 206
參考文獻 208
第8章遞歸 209
8.1遞歸的概念 209
8.2背景知識：數學歸納法 210
8.3基本遞歸 212
8.3.1以任意基數列印數字 213
8.3.2遞歸算法有效的原因 215
8.3.3遞歸算法的作用原理 216
8.3.4遞歸不宜太多 217
8.3.5樹 218
8.3.6附加例子 219
8.4數值套用 223
8.4.1模運算 223
8.4.2模冪運算 224
8.4.3最大公約數和乘法
逆元素 225
8.4.4RSA密碼系統 228
8.5分治算法 230
8.5.1最大鄰近子序列和問題 230
8.5.2基本分治遞歸分析 233
8.5.3分治法運行時間的
一般上限 235
8.6動態規劃 237
8.7回溯法 241
小結 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排過序的數組的線性
時間合併 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小數組 270
9.6.8C++快速排序例程 270
9.7排序選擇 272
9.8排序的下限 274
9.9間接排序 275
9.9.1使用指針將Comparable
副本數減少為2N 275
9.9.2避免附加數組 276
小結 278
學習目標 279
常見錯誤 279
Internet資源 279
練習 280
簡答題 280
理論題 280
實踐題 281
編程項目 282
參考文獻 283
第10章隨機 285
10.1為什麼我們需要隨機數 285
10.2隨機數生成器 286
10.3非均勻隨機數 290
10.4生成隨機排列 291
10.5隨機算法 293
10.6隨機素數測試 295
小結 298
學習目標 298
常見錯誤 298
Internet資源 299
練習 299
簡答題 299
理論題 299
實踐題 300
編程項目 300
參考文獻 301
第三部分應用程式
第11章娛樂與遊戲 302
11.1單詞查找拼圖 302
11.1.1理論 303
11.1.2C++實現 304
11.2Tic-Tac-Toe遊戲 309
11.2.1a-b修剪 309
11.2.2變換表 312
11.2.3計算機西洋棋 316
小結 316
學習目標 317
常見錯誤 317
Internet資源 317
練習 317
簡答題 317
理論題 317
實踐題 318
編程項目 318
參考文獻 319
第12章堆疊和編譯器 320
12.1對稱符號檢查器 320
12.1.1基本算法 320
12.1.2實現 321
12.2簡單計算器 330
12.2.1後綴自動機 330
12.2.2中綴到後綴的轉換 332
12.2.3實現 333
12.2.4表達式樹 341
小結 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實現 350
13.2交叉引用生成程式 366
13.2.1基本概念 366
13.2.2C++實現 366
小結 370
學習目標 370
常見錯誤 371
Internet資源 371
練習 371
簡答題 371
理論題 371
實踐題 372
編程項目 372
參考文獻 373
第14章仿真 375
14.1Josephus問題 375
14.1.1簡單的解決方案 376
14.1.2一個更有效的算法 376
14.2事件驅動仿真 380
14.2.1基本思想 380
14.2.2實例：數據機
庫仿真 381
小結 388
學習目標 388
常見錯誤 389
Internet資源 389
練習 389
簡答題 389
理論題 389
實踐題 390
編程項目 390
第15章圖和路徑 391
15.1定義 391
15.2無權最短路徑問題 403
15.2.1理論 403
15.2.2C++實現 406
15.3正的有權最短路徑問題 407
15.3.1理論：迪傑斯特拉算法 407
15.3.2C++實現 410
15.4負的有權最短路徑問題 412
15.4.1理論 412
15.4.2C++實現 413
15.5無環圖的路徑問題 414
15.5.1拓撲排序 415
15.5.2無環最短路徑算法
的理論 416
15.5.3C++實現 417
15.5.4套用：關鍵路徑分析 419
小結 421
學習目標 422
常見錯誤 422
Internet資源 423
練習 423
簡答題 423
理論證明 423
實踐題 424
編程項目 425
參考文獻 426
第四部分實現
第16章堆疊和佇列 427
16.1動態數組實現 427
16.1.1堆疊 427
16.1.2佇列 431
16.2鍊表實現 436
16.2.1堆疊 436
16.2.2佇列 441
16.3兩種方法的比較 444
16.4STL堆疊和佇列適配器 445
16.5雙頭佇列 446
小結 447
學習目標 447
常見錯誤 448
Internet資源 448
練習 448
簡答題 448
實踐題 449
編程項目 449
第17章鍊表 450
17.1基本概念 450
17.1.1header節點 452
17.1.2疊代器類 453
17.2C++實現 454
17.3雙鍊表和循環鍊表 462
17.4排序鍊表 464
17.5實現STL鍊表類 466
小結 479
學習目標 480
常見錯誤 480
Internet資源 480
練習 481
簡答題 481
理論題 481
實踐題 482
編程項目 483
第18章樹 485
18.1一般樹 485
18.1.1定義 485
18.1.2實現 486
18.1.3套用：檔案系統 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
小結 511
學習目標 512
常見錯誤 512
Internet資源 512
練習 513
簡答題 513
理論題 514
實踐題 514
編程項目 514
第19章二叉查找樹 516
19.1基本概念 516
19.1.1操作 517
19.1.2C++實現 518
19.2順序統計 526
C++實現 526
19.3分析二叉查找樹操作 530
19.4AVL樹 533
19.4.1屬性 534
19.4.2單旋轉 536
19.4.3雙旋轉 538
19.4.4AVL插入總結 540
19.5紅-黑樹 541
19.5.1自底向上插入 541
19.5.2自頂向下紅-黑樹 543
19.5.3C++實現 545
19.5.4自頂往下刪除 551
19.6AA-樹 553
19.6.1插入 554
19.6.2刪除 556
19.6.3C++實現 557
19.7實現STLset類和map類 561
19.8B樹 575
小結 580
學習目標 581
常見錯誤 581
Internet資源 582
練習 582
簡答題 582
理論題 583
實踐題 583
編程項目 584
參考文獻 584
第20章散列表 587
20.1基本概念 587
20.2散列函式 588
20.3線形探測法 590
20.3.1線性探測法的簡單
分析（naiveanalysis） 591
20.3.2實際情況：原始集聚 592
20.3.3查找運算分析 593
20.4二次探測法 594
20.4.1C++實現 598
20.4.2二次探測法分析 603
20.5分離連結法 603
20.6散列表與二叉查找樹 604
20.7散列化應用程式 604
小結 605
學習目標 605
常見錯誤 606
Internet資源 606
練習 606
簡答題 606
實踐題 607
編程項目 608
參考文獻 608
第21章優先權佇列：二叉堆 610
21.1基本思想 610
21.1.1結構屬性 611
21.1.2堆順序屬性 612
21.1.3允許的操作 613
21.2基本操作的實現 615
21.2.1insert操作 615
21.2.2deleteMin操作 616
21.3buildHeap操作：線性時間的
堆構造函式 619
21.4STLpriority_queue實現 622
21.5高級操作：decreaseKey和
merge 625
21.6內部排序：堆排序 625
21.7外部排序 628
21.7.1我們為什麼需要
新的算法 628
21.7.2外部排序模型 628
21.7.3簡單的算法 629
21.7.4多路歸併 630
21.7.5多相歸併 631
21.7.6置換選擇 632
小結 634
學習目標 634
常見錯誤 635
Internet資源 635
練習 635
簡答題 635
理論題 635
實踐題 637
編程項目 637
參考文獻 638
第五部分高級數據結構
第22章伸展樹 639
22.1自我調整和攤銷分析 639
22.1.1攤銷時間限制 640
22.1.2簡單的自我調整策略 641
22.2基本的自底往上伸展樹 642
22.3基本伸展樹操作 644
22.4自底往上伸展樹分析 645
22.5自頂往下伸展樹 649
22.6實現自頂往下伸展樹 652
22.7伸展樹與其他查找樹的比較 657
小結 658
學習目標 658
常見錯誤 658
Internet資源 659
練習 659
簡答題 659
理論題 659
實踐題 660
編程項目 660
參考文獻 660
第23章合併優先權佇列 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對偶堆的實現 668
23.2.3套用：Dijkstra最短加權
路徑算法 674
小結 676
學習目標 676
常見錯誤 676
Internet資源 677
練習 677
簡答題 677
理論題 677
實踐題 678
編程項目 678
參考文獻 678
第24章不相交集類 680
24.1等價關係 680
24.2動態等價和兩個套用 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.5C++實現 694
24.6針對按秩合併與路徑壓縮的
最壞情形 695
合併/查找算法分析 696
小結 701
學習目標 701
常見錯誤 702
Internet資源 702
練習 702
簡答題 702
理論題 703
實踐題 703
編程項目 703
參考文獻 704
附錄
附錄AC++相關信息 706
A.1沒有編譯器實現該標準 706
A.2不常見的C++運算符 706
A.2.1自增運算符與自減運
算符 706
A.2.2類型轉換 707
A.2.3按位運算符 708
A.2.4條件運算符 710
A.3命令參數 710
A.4輸入和輸出 710
A.4.1基本的流操作 711
A.4.2順序檔案 714
A.4.3字元串流 714
A.5名字空間 716
A.6C++新特性 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
附錄DC++中的基元數組 723
D.1基元數組 723
D.1.1C++實現：數組名稱是
一個指針 723
D.1.2多維數組 726
D.1.3char*類型、const指針
和常量字元串 726
D.2動態數組分配：new[]和
delete[] 729
D.3指針算術運算、指針跳和
基本疊代 733
D.3.1*、&和[]優先權的含意 734
D.3.2指針算術的含意 734
D.3.3指針跳例子 736
D.3.4使用指針跳的意義 737
常見錯誤 738
Internet資源 738
