算法之美：隱匿在數據結構背後的原理(C++版)

第1章從數據到算法.1
1.1數據與數據結構.1
1.1.1數據及其類型.1
1.1.2數據結構簡介.3
1.2算法.5
1.2.1算法的概念.5
1.2.2算法的分析.8
1.2.3算法的設計.12
1.3C++中的STL.18
1.3.1STL簡介.19
1.3.2STL構成.20
1.3.3STL的不同版本.22
本章參考文獻.23
第2章指針與數組——也談中國古代兵制.24
2.1指針.24
2.1.1內存與地址.24
2.1.2指針的語法.27
2.1.3使用指針變量.29
2.1.4函數與參數傳遞.31
2.2數組.36
2.2.1結構型數據類型.37
2.2.2數組定義與初始化.37
2.2.3數組與指針.41
2.2.4數組的抽象數據類型.45
2.3數組應用舉例.48
2.3.1Z字形編排問題.48
2.3.2大整數乘法問題.51
2.3.3九宮格問題.52
2.4動態內存管理.53
2.4.1關鍵詞new和delete53
2.4.2避免內存錯誤.56
本章參考文獻.61
第3章字符串與模式匹配——夢里尋她千百度.62
3.1基本概念與定義.62
3.1.1C++中的字符串.62
3.1.2字符串抽象數據類型.65
3.2文本的精確匹配.66
3.2.1BF算法.66
3.2.2MP算法.67
3.2.3KMP算法.72
3.2.4BM算法.75
3.2.5BMH算法.81
3.3文本的模糊匹配.83
3.3.1全局編輯距離.83
3.3.2局部最佳對准.86
3.3.3N元距離模型.87
3.3.4語音編碼模型.88
本章參考文獻.89
第4章鏈表——老鷹捉小雞.91
4.1鏈表的概念.91
4.2單向鏈表.92
4.2.1單向鏈表的結構.92
4.2.2單向鏈表的操作算法.94
4.2.3有序鏈表的合並算法.101
4.3單向循環鏈表.102
4.3.1單向循環鏈表的結構.102
4.3.2單向循環鏈表的實現.103
4.3.3約瑟夫環的問題.107
4.3.4魔術師發牌問題.108
4.3.5拉丁方陣的問題.109
4.4雙向循環鏈表.110
4.4.1雙向循環鏈表的結構.110
4.4.2雙向循環鏈表的實現111
4.4.3維吉尼亞加密法問題.115
4.5游標類的設計與實現.117
4.5.1游標類的結構.117
4.5.2游標類的實現.118
4.6STL與鏈表.122
4.6.1STL中鏈表類的接口.122
4.6.2遍歷.124
4.6.3元素的插入與刪除.125
本章參考文獻.126
第5章先進先出與后進先出——簡單而深刻.127
5.1摞盤子的策略.127
5.1.1棧的結構.127
5.1.2棧的操作及實現.129
5.1.3括號匹配問題.132
5.1.4停車場模擬問題.133
5.2排隊的智慧.136
5.2.1隊列的結構.136
5.2.2隊列的操作及實現.138
5.2.3舞伴問題.142
5.2.4楊輝三角問題.143
5.2.5游程編碼問題.145
5.3優先級隊列——兼談頁面置換算法.146
5.3.1優先級隊列的結構.146
5.3.2優先級隊列的實現.149
5.4STL中的棧與隊列.150
5.4.1STL中的stack.151
5.4.2STL中的queue.153
5.4.3STL中的priority_queue.155
本章參考文獻.158
第6章遞歸——老和尚講故事.159
6.1遞歸的概念.159
6.1.1定義.159
6.1.2應用遞歸的原則.162
6.1.3遞歸和非遞歸的轉化.168
6.2分治法.170
6.2.1分治法簡述.171
6.2.2漢諾塔問題.172
6.2.3傳染病問題.174
6.3回溯法.176
6.3.1回溯法簡述.176
6.3.2迷宮問題.176
6.3.3八皇后問題.180
本章參考文獻.183
第7章樹——從紅樓夢說起.184
7.1認識樹這種結構.184
7.1.1基本定義.184
7.1.2一些術語.186
7.1.3樹的抽象.187
7.2花開二枝分外香——二叉樹及相關算法.188
7.2.1二叉樹的定義.188
7.2.2二叉樹的性質.190
7.2.3二叉樹的實現.191
7.2.4二叉樹的遍歷算法.196
7.2.5二叉樹線索化算法.200
7.3合抱之木，生於毫末——從樹到森林.203
7.3.1樹的存儲表示.203
7.3.2樹的實現.206
7.3.3樹與森林的遍歷算法.209
7.3.4森林與二叉樹的轉換.211
7.4哈夫曼樹——最優二叉樹編碼算法.213
7.4.1哈夫曼編碼.213
7.4.2構造哈夫曼樹.215
7.4.3哈夫曼編碼的實現.216
7.5堆.220
7.5.1堆的概念.220
7.5.2堆的建立.221
7.5.3堆的操作.223
7.6基於STL實現樹結構.224
7.6.1STL中的vector.224
7.6.2STL中的map.228
本章參考文獻.230
第8章圖——始於哥尼斯堡的七橋問題.231
8.1圖的基本概念.231
8.1.1圖的定義.231
8.1.2圖的術語.232
8.1.3圖的運算.236
8.1.4圖的抽象數據類型.237
8.2圖的存儲與表示.239
8.2.1圖的鄰接矩陣表示.239
8.2.2圖的鄰接表表示.241
8.2.3兩種表示法的比較.243
8.3圖的遍歷.244
8.3.1歐拉路徑與歐拉回路.244
8.3.2哈密爾頓路徑與哈密爾頓回路.248
8.3.3廣度優先遍歷算法.252
8.3.4深度優先遍歷算法.254
8.4最短路徑問題.258
8.4.1固定起點最短路徑問題.258
8.4.2非固定起點最短路徑問題.264
8.4.3最短路徑的動態規划解法.266
8.5最小生成樹.273
8.5.1最小生成樹的定義.273
8.5.2克魯斯卡爾算法.275
8.5.3普里姆算法.279
本章參考文獻.283
第9章樹形搜索結構——做一名出色的園藝師.284
9.1二叉搜索樹.284
9.1.1二叉搜索樹的概念.284
9.1.2二叉搜索樹的操作.285
9.1.3二叉搜索樹的實現.288
9.1.4二叉搜索樹的分析.291
9.2自平衡的二叉搜索樹——AVL樹.294
9.2.1AVL樹的概念.294
9.2.2AVL樹的旋轉.295
9.2.3AVL樹的實現.299
9.3樹中亦有「紅與黑」.303
9.3.1紅黑樹的概念.303
9.3.2紅黑樹的操作.306
9.3.3紅黑樹的實現.314
9.4基於Trie樹的單詞檢索.314
9.4.1Trie樹的概念.315
9.4.2Trie樹的表示.316
9.4.3Trie樹的實現.317
本章參考文獻.320
第10章集合與字典——再言搜索之話題.321
10.1集合論基礎.321
10.1.1集合的概念.321
10.1.2集合的運算.323
10.2集合的實現.325
10.2.1位向量集合.325
10.2.2單鏈表集合.330
10.3字典.337
10.3.1字典的概念.338
10.3.2搜索運算.342
10.4散列.346
10.4.1散列的概念.347
10.4.2散列函數.348
10.4.3字符串散列.351
10.4.4處理散列沖突.353
10.5拼寫檢查問題.358
10.6不相交集.363
10.6.1不相交集的概念.363
10.6.2不相交集的實現.366
10.6.3犯罪團伙的問題.369
10.6.4路徑壓縮的實現.370
10.7STL中的set.371
本章參考文獻.374
第11章排序——有序讓世界更美好.375
11.1排序問題概述.375
11.1.1基本概念和定義.375
11.1.2排序算法的分類.376
11.1.3排序算法的分析.377
11.2插入排序.378
11.2.1直接插入排序.378
11.2.2二分插入排序.380
11.2.3希爾排序.382
11.3選擇排序.384
11.3.1直接選擇排序.384
11.3.2堆排序.386
11.4交換排序.390
11.4.1冒泡排序.390
11.4.2雞尾酒排序.392
11.4.3快速排序.395
11.5歸並排序.399
11.6計數排序.403
本章參考文獻.407
附錄經典求職面試題目.408