目　　錄
前言
第1章緒論1
1.1計算機問題求解1
1.1.1程序開發過程1
1.1.2　一個簡單例子3
1.2　問題求解：交叉路口的紅綠燈安排4
1.2.1問題分析和嚴格化5
1.2.2圖的頂點分組和算法6
1.2.3算法的精化和Python描述7
1.2.4討論8
1.3算法和算法分析10
1.3.1問題、問題實例和算法10
1.3.2算法的代價及其度量14
1.3.3算法分析19
1.3.4Python程序的計算代價（復雜度）21
1.4數據結構23
1.4.1數據結構及其分類24
1.4.2計算機內存對象錶示26
1.4.3Python對象和數據結構30
練習32
第2章抽象數據類型和Python類34
2.1抽象數據類型34
2.1.1數據類型和數據構造34
2.1.2抽象數據類型的概念36
2.1.3抽象數據類型的描述37
2.2Python的類39
2.2.1有理數類39
2.2.2類定義進階40
2.2.3本書采用的ADT描述形式43
2.3類的定義和使用44
2.3.1類的基本定義和使用44
2.3.2實例對象：初始化和使用45
2.3.3幾點說明47
2.3.4繼承49
2.4Python異常53
2.4.1異常類和自定義異常53
2.4.2異常的傳播和捕捉54
2.4.3內置的標準異常類54
2.5類定義實例：學校人事管理係統中的類55
2.5.1問題分析和設計56
2.5.2人事記錄類的實現57
2.5.3討論62
本章總結63
練習64
第3章綫性錶66
3.1綫性錶的概念和錶抽象數據類型66
3.1.1錶的概念和性質66
3.1.2錶抽象數據類型67
3.1.3綫性錶的實現：基本考慮69
3.2順序錶的實現69
3.2.1基本實現方式69
3.2.2順序錶基本操作的實現71
3.2.3順序錶的結構74
3.2.4Python的list76
3.2.5順序錶的簡單總結78
3.3鏈接錶79
3.3.1綫性錶的基本需要和鏈接錶79
3.3.2單鏈錶79
3.3.3單鏈錶類的實現84
3.4鏈錶的變形和操作88
3.4.1單鏈錶的簡單變形88
3.4.2循環單鏈錶91
3.4.3雙鏈錶92
3.4.4兩個鏈錶操作95
3.4.5不同鏈錶的簡單總結98
3.5錶的應用99
3.5.1Josephus問題和基於“數組”概念的解法99
3.5.2基於順序錶的解100
3.5.3基於循環單鏈錶的解101
本章總結102
練習103
第4章　字符串107
4.1　字符集、字符串和字符串操作107
4.1.1　字符串的相關概念107
4.1.2　字符串抽象數據類型109
4.2　字符串的實現109
4.2.1　基本實現問題和技術109
4.2.2　實際語言裏的字符串110
4.2.3　Python的字符串111
4.3　字符串匹配（子串查找）112
4.3.1　字符串匹配112
4.3.2　串匹配和樸素匹配算法113
4.3.3　無迴溯串匹配算法（KMP算法）115
4.4　字符串匹配問題119
4.4.1　串匹配/搜索的不同需要120
4.4.2　一種簡化的正則錶達式122
4.5　Python正則錶達式123
4.5.1　概況124
4.5.2　基本情況124
4.5.3　主要操作125
4.5.4　正則錶達式的構造126
4.5.5　正則錶達式的使用132
本章總結132
練習133
第5章　棧和隊列135
5.1　概述135
5.1.1　棧、隊列和數據使用順序135
5.1.2　應用環境136
5.2　棧：概念和實現136
5.2.1　棧抽象數據類型137
5.2.2　棧的順序錶實現137
5.2.3　棧的鏈接錶實現139
5.3　棧的應用140
5.3.1　簡單應用：括號匹配問題140
5.3.2　錶達式的錶示、計算和變換142
5.3.3　棧與遞歸149
5.4　隊列155
5.4.1　隊列抽象數據類型155
5.4.2　隊列的鏈接錶實現155
5.4.3　隊列的順序錶實現156
5.4.4　隊列的list實現158
5.4.5　隊列的應用160
5.5　迷宮求解和狀態空間搜索162
5.5.1　迷宮求解：分析和設計162
5.5.2　求解迷宮的算法164
5.5.3　迷宮問題和搜索167
5.6　幾點補充171
5.6.1　幾種與棧或隊列相關的結構171
5.6.2　幾個問題的討論172
本章總結173
練習173
第6章　二叉樹和樹176
6.1　二叉樹：概念和性質176
6.1.1　概念和性質177
6.1.2　抽象數據類型181
6.1.3　遍曆二叉樹181
6.2　二叉樹的list實現183
6.2.1　設計和實現183
6.2.2　二叉樹的簡單應用：錶達式樹185
6.3　優先隊列188
6.3.1　概念188
6.3.2　基於綫性錶的實現189
6.3.3　樹形結構和堆191
6.3.4　優先隊列的堆實現192
6.3.5　堆的應用：堆排序195
6.4　應用：離散事件模擬196
6.4.1　通用的模擬框架197
6.4.2　海關檢查站模擬係統198
6.5　二叉樹的類實現202
6.5.1　二叉樹結點類203
6.5.2　遍曆算法204
6.5.3　二叉樹類208
6.6　哈夫曼樹209
6.6.1　哈夫曼樹和哈夫曼算法209
6.6.2　哈夫曼算法的實現210
6.6.3　哈夫曼編碼211
6.7　樹和樹林212
6.7.1　實例和錶示213
6.7.2　定義和相關概念213
6.7.3　抽象數據類型和操作215
6.7.4　樹的實現216
6.7.5　樹的Python實現218
本章總結220
練習220
第7章圖224
7.1概念、性質和實現224
7.1.1　定義和圖示224
7.1.2　圖的一些概念和性質225
7.1.3　圖抽象數據類型227
7.1.4　圖的錶示和實現228
7.2　圖結構的Python實現231
7.2.1　鄰接矩陣實現231
7.2.2　壓縮的鄰接矩陣（鄰接錶）實現233
7.2.3　小結235
7.3　基本圖算法235
7.3.1　圖的遍曆236
7.3.2　生成樹238
7.4　*小生成樹240
7.4.1　*小生成樹問題240
7.4.2　Kruskal算法240
7.4.3　Prim算法243
*7.4.4　Prim算法的改進246
7.4.5　*小生成樹問題247
7.5　*短路徑248
7.5.1　*短路徑問題248
7.5.2　求解單源點*短路徑的Dijkstra算法248
7.5.3　求解任意頂點間*短路徑的Floyd算法252
7.6　AOV/AOE網及其算法255
7.6.1　AOV網、拓撲排序和拓撲序列255
7.6.2　拓撲排序算法257
7.6.3　AOE網和關鍵路徑258
7.6.4　關鍵路徑算法259
本章總結261
練習262
第8章　字典和集閤265
8.1　數據存儲、檢索和字典265
8.1.1　數據存儲和檢索265
8.1.2　字典實現的問題267
8.2　字典綫性錶實現269
8.2.1　基本實現269
8.2.2　有序綫性錶和二分法檢索270
8.2.3　字典綫性錶總結272
8.3　散列和散列錶273
8.3.1　散列的思想和應用273
8.3.2　散列函數275
8.3.3　衝突的內消解：開地址技術277
8.3.4　外消解技術280
8.3.5　散列錶的性質280
8.4　集閤282
8.4.1　集閤的概念、運算和抽象數據類型282
8.4.2　集閤的實現283
8.4.3　特殊實現技術：位嚮量實現285
8.5　Python的標準字典類dict和set286
8.6　二叉排序樹和字典287
8.6.1　二叉排序樹288
8.6.2　**二叉排序樹295
8.6.3　一般情況的**二叉排序樹297
8.7　平衡二叉樹302
8.7.1　定義和性質302
8.7.2　AVL樹類303
8.7.3　插入操作304
8.7.4　相關問題310
8.8　動態多分支排序樹311
8.8.1　多分支排序樹311
8.8.2　B樹312
8.8.3　B+ 樹314
本章總結315
練習316
第9章　排序319
9.1　問題和性質319
9.1.1　問題定義319
9.1.2　排序算法320
9.2　簡單排序算法323
9.2.1　插入排序323
9.2.2　選擇排序325
9.2.3　交換排序327
9.3　快速排序328
9.3.1　快速排序的錶實現329
9.3.2　程序實現330
9.3.3　復雜度331
9.3.4　另一種簡單實現332
9.4　歸並排序332
9.4.1　順序錶的歸並排序333
9.4.2　歸並算法的設計問題333
9.4.3　歸並排序函數定義333
9.4.4　算法分析335
9.5　其他排序方法335
9.5.1　分配排序和基數排序335
9.5.2　一些與排序有關的問題338
9.5.3　Python係統的list排序339
本章總結340
練習342
參考文獻344
· · · · · · (收起)