目 錄
Introduction to C++ Programming and Data Structures, Fifth Edition
第17章 遞歸 1
17.1 簡介 1
17.2 案例研究：計算階乘 2
17.3 案例研究：斐波那契數 8
17.4 使用遞歸解決問題 12
17.5 遞歸輔助函數 16
17.5.1 選擇排序 18
17.5.2 二分查找 20
17.6 漢諾塔 22
17.7 八皇后問題 26
17.8 遞歸與迭代 30
17.9 尾遞歸 31
關鍵術語 34
章節(jié)總結 35
編程練習 35
第18章 開發(fā)高效算法 46
18.1 簡介 47
18.2 使用大O表示法衡量算法效率 47
18.3 示例：確定大O 50
18.4 分析算法時間復雜度 56
18.4.1 分析二分查找 56
18.4.2 分析選擇排序 57
18.4.3 分析漢諾塔問題 58
18.4.4 常見的遞歸關系 59
18.4.5 比較常見的增長函數 59
18.5 使用動態(tài)規(guī)劃求斐波那契數 63
18.6 使用歐幾里得算法求最大
公約數 66
18.7 尋找質數的高效算法 72
18.8 使用分治法尋找最近點對 81
18.9 使用回溯法解決八皇后問題 84
18.10 案例研究：尋找凸包 88
18.10.1 禮品包裝算法 89
18.10.2 Graham算法 90
18.11 字符串匹配 92
18.11.1 Boyer-Moore算法 95
18.11.2 Knuth-Morris-Pratt算法 98
關鍵術語 102
章節(jié)總結 103
編程練習 104
第19章 排序 111
19.1 簡介 111
19.2 插入排序 112
19.3 冒泡排序 115
19.4 歸并排序 117
19.5 快速排序 123
19.6 堆排序 127
19.6.1 存儲堆 129
19.6.2 添加新節(jié)點 130
19.6.3 刪除根 131
19.6.4 Heap類 134
19.6.5 使用Heap類進行排序 137
19.6.6 堆排序的時間復雜度 139
19.7 桶排序和基數排序 140
19.8 外部排序 143
19.8.1 實現第一階段 145
19.8.2 實現第二階段 146
19.8.3 合成兩個階段 149
19.8.4 外部排序復雜度 150
關鍵術語 151
章節(jié)總結 151
編程練習 151
第20章 鏈表、隊列和優(yōu)先級隊列 154
20.1 簡介 154
20.2 節(jié)點 155
20.3 LinkedList類 159
20.4 實現LinkedList 163
20.4.1 實現addFirst
(T element) 164
20.4.2 實現addLast
(T element) 165
20.4.3 實現add(int index,
T element) 166
20.4.4 實現removeFirst() 168
20.4.5 實現removeLast() 170
20.4.6 實現removeAt
(int index) 171
20.4.7 LinkedList的源代碼 173
20.4.8 LinkedList的時間
復雜度 175
20.5 迭代器 179
20.6 C++11 foreach循環(huán) 184
20.7 鏈表的變體 186
20.8 隊列 189
20.9 優(yōu)先級隊列 192
關鍵術語 196
章節(jié)總結 196
編程練習 197
第21章 二叉查找樹 200
21.1 簡介 200
21.2 二叉查找樹基礎知識 201
21.3 表示二叉查找樹 202
21.4 訪問二叉查找樹中的節(jié)點 204
21.5 查找元素 204
21.6 將元素插入二叉查找樹 206
21.7 樹的遍歷 208
21.8 BST類 210
21.9 刪除二叉查找樹中的元素 216
21.10 BST的迭代器 224
21.11 案例研究：數據壓縮 227
關鍵術語 232
章節(jié)總結 233
編程練習 233
第22章 STL容器 236
22.1 簡介 236
22.2 STL基礎 237
22.3 STL迭代器 243
22.3.1 迭代器的類型 245
22.3.2 迭代器運算符 246
22.3.3 預定義迭代器 248
22.3.4 istream_iterator和ostream_iterator 250
22.4 C++11自動類型推斷 252
22.5 序列容器 253
22.5.1 序列容器：vector 254
22.5.2 序列容器：deque 257
22.5.3 序列容器：list 259
22.6 關聯容器 263
22.6.1 關聯容器：set和
multiset 263
22.6.2 關聯容器：map和
multimap 265
22.7 容器適配器 269
22.7.1 容器適配器：stack 269
22.7.2 容器適配器：queue 270
22.7.3 容器適配器：priority_
queue 272
關鍵術語 274
章節(jié)總結 275
編程練習 276
第23章 STL算法 280
23.1 簡介 281
23.2 算法類型 282
23.3 copy函數 284
23.4 fill和fill_n 287
23.5 將函數作為參數傳遞 289
23.6 generate和generate_n 293
23.7 remove、remove_if、
remove_copy和
remove_copy_if 295
23.8 replace、replace_if、replace_copy和
replace_copy_if 299
23.9 find、find_if、find_end和
find_first_of 303
23.10 search和search_n 309
鄂公網安備 42010302001612號 