數據結構和演算法（Python和C++語言描述）

第1章抽象與分析　1
1．1　概要　1
1．1．1　大型程式設計．　1
1．1．2　前方的道路　2
1．2　功能的抽象　3
1．2．1　契約式設計　3
1．2．2　驗證先驗條件　6
1．2．3　自上而下的設計．　9
1．2．4　記錄副作用．　11
1．3　演演算法分析．　12
1．3．1　線性搜索　12
1．3．2　二分搜索　14
1．3．3　非正式的演算法比較．　15
1．3．4　演算法的正式分析　17
1．3．5　大O符號與Θ符號　21
1．4　小結　23
1．5　練習　23

第2章資料的抽象．　27
2．1　概要　27
2．2　抽象資料類型　27
2．2．1　從資料類型到抽象資料
類型．　28
2．2．2　定義抽象資料類型．　28
2．2．3　實現抽象資料類型．　30
2．3　抽象資料類型和物件　32
2．3．1　規範．　32
2．3．2　實現．　34
2．3．3　改變存儲方式　35
2．3．4　物件導向的設計和程式設計．　36
2．4　抽象資料類型的實例：
資料集（Dataset）　38
2．4．1　物件導向設計的過程　38
2．4．2　定義一個抽象資料
類型．　39
2．4．3　實現這個抽象資料類型．　41
2．5　抽象資料類型的實例：
有理數（Rational）　．42
2．5．1　運運算元重載．42
2．5．2　有理數（Rational）類44
2．6　增量開發以及單元測試45
2．7　小結48
2．8　練習48

第3章容器類52
3．1　概要52
3．2　Python的列表52
3．3　順序集合：撲克牌牌組53
3．4　有序集合：手牌．56
3．4．1　創建橋牌的手牌56
3．4．2　比較撲克牌．58
3．4．3　撲克牌排序．59
3．5　Python裡列表的實現61
3．5．1　基於陣列的清單61
3．5．2　效率分析62
3．6　Python的字典（選讀）．63
3．6．1　字典抽象資料類型63
3．6．2　熟悉Python字典．64
3．6．3　字典的實現．65
3．6．4　擴展示例：瑪律可夫鏈67
3．7　小結70
3．8　練習71

第4章鏈式結構和反覆運算器．75
4．1　概要75
4．2　Python的記憶體模型75
傳遞參數80
4．3　鏈表實現．81
4．4　鏈表抽象資料類型的實現．85
4．5　反覆運算器95
4．5．1　Python的反覆運算器95
4．5．2　在鏈表（LList）裡
添加反覆運算器．96
4．5．3　通過Python的生成器來
反覆運算　97
4．6　基於遊標的清單API（選讀）．　99
4．6．1　遊標（Cursor）的
API　99
4．6．2　Python的遊標清單
（CursorList）　100
4．6．3　鏈式結構的遊標清單
（CursorList）　102
4．7　鏈表vs陣列　104
4．8　小結．　104
4．9　練習．　105

第5章堆疊和佇列　109
5．1　概要．　109
5．2　堆疊．　109
5．2．1　堆疊抽象資料類型　109
5．2．2　堆疊的簡單應用　110
5．2．3　堆疊的實現　112
5．2．4　應用程式：處理算術
方程．　113
5．2．5　應用程式：語法的處理
（選讀）　．　116
5．3　佇列．　119
5．3．1　佇列抽象資料類型　119
5．3．2　佇列的簡單應用　120
5．4　佇列的實現．　121
5．5　應用程式示例：佇列的類比
（選讀）　．　123
5．6　小結．　128
5．7　練習．　128

第6章遞迴　133
6．1　概要．　133
6．2　遞迴定義　134
6．3　簡單的遞迴示例　136
6．3．1　示例：字串反轉　136
6．3．2　示例：字謎　137
6．3．3　示例：快速計算指數．　138
6．3．4　示例：二分搜索　139
6．4　遞迴的分析．　140
6．5　排序．142
6．5．1　遞迴設計：歸併排序142
6．5．2　分析歸併排序．144
6．6　一個“難”題：漢諾塔146
6．7　小結．149
6．8　練習．150

第7章樹156
7．1　概要．156
7．2　樹的術語156
7．3　示例應用程式：運算式樹158
7．4　樹的存儲方式159
7．5　應用：二叉搜尋樹．160
7．5．1　二分查找屬性．160
7．5．2　實現一個二叉搜尋樹161
7．5．3　遍歷整個二叉搜尋樹
（BST）　166
7．5．4　二叉搜尋樹（BST）的
運行時分析168
7．6　使用二叉搜尋樹（BST）來
實現映射（選讀）169
7．7　小結．171
7．8　練習．172

第8章為Python程式師準備的
C++簡介．177
8．1　概要．177
8．2　C++的歷史和背景178
8．3　注釋、代碼塊、變數名和
關鍵字．182
8．4　資料類型和變數聲明183
8．5　Include語句、命名空間
以及輸入/輸出186
8．6　編譯．189
8．7　運算式和運運算元優先順序191
8．8　條件陳述式193
8．9　資料類型轉換196
8．10　迴圈語句197
8．11　陣列199
8．11．1　一維陣列199
8．11．2　多維陣列201
8．11．3　字元陣列．　201
8．12　函數的細節　202
8．12．1　聲明、定義以及原型．　202
8．12．2　值傳遞　205
8．12．3　引用傳遞．　205
8．12．4　將陣列作為參數傳遞．　206
8．12．5　常量參數　208
8．12．6　默認參數．　208
8．13　標頭檔和內聯函數　209
8．14　斷言與測試　213
8．15　變數的作用域以及生命週期．　214
8．16　Python程式師編寫C++程式
時的常見錯誤．　215
8．17　其他的C++相關話題
（選讀）　216
8．17．1　C++的Switch語句．　216
8．17．2　創建C++的命名空間．　218
8．17．3　全域變數．　219
8．18　小結　220
8．19　練習　220

第9章C++類．　224
9．1　基本的語法和語義．　224
9．2　字串　232
9．3　檔輸入和輸出　234
9．4　運運算元重載．　236
9．5　類變數和方法　242
9．6　小結．　246
9．7　練習．　246

第10章C++的動態記憶體．　250
10．1　概要　250
10．2　C++的指針　254
10．3　動態陣列　259
10．4　動態記憶體類　263
10．4．1　析構函數．　263
10．4．2　複製構造函數　265
10．4．3　設定運運算元　268
10．4．4　完整的動態陣列類　270
10．4．5　引用返回類型　275
10．5　動態記憶體錯誤．　276
10．5．1　記憶體洩漏．276
10．5．2　訪問無效記憶體277
10．5．3　記憶體錯誤總結280
10．6　小結281
10．7　練習281

第11章C++的鏈式結構285
11．1　概要285
11．2　C++鏈式結構的類286
11．3　C++鏈表．288
11．4　C++連結的動態記憶體錯誤．298
11．5　小結299
11．6　練習300

第12章C++範本．302
12．1　概要302
12．2　範本方法303
12．3　範本類．305
12．3．1　標準範本庫的
vector　類305
12．3．2　使用者定義的範本類．308
12．4　小結　311
12．5　練習312

第13章堆、平衡樹和散列表314
13．1　概要314
13．2　優先佇列和堆．314
13．2．1　堆排序320
13．2．2　關於堆和優先佇列
實現的說明320
13．3　平衡樹．321
13．4　其他的樹結構．329
13．5　散列表．329
13．6　小結339
13．7　練習339

第14章圖．343
14．1　概要343
14．2　圖資料結構344
14．3　最短路徑演算法．347
14．3．1　無權最短路徑347
14．3．2　加權最短路徑350
14．4　深度優先演算法．353
14．5　最小生成樹　357
14．5．1　Kruskal演算法．　358
14．5．2　不交集資料結構．　358
14．5．3　Prim演算法　361
14．6　小結　361
14．7　練習　362

第15章演算法技術　365
15．1　概要　365
15．2　分治演算法　365
15．2．1　分析遞迴函數　366
15．2．2　快速排序．368
15．3　貪心演算法372
15．4　動態規劃378
15．4．1　最長公共子序列379
15．4．2　記憶化382
15．4．3　矩陣鏈乘法382
15．5　NP完全問題383
15．6　小結384
15．7　練習385
術語表387