數據結構與問題求解C 版（第2版）

圖書簡介

從抽象思想、問題解決以及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

數據結構與問題求解C 版（第2版）

基本介紹

圖書簡介

目錄

相關詞條

熱門詞條