數據結構與算法：Python語言描述（第2版）

裘宗燕: 北京大學數學學院信息科學系教授。長期從事計算機軟件與理論、程序設計語言和符號計算方面的研究和教學工作。已出版多部著作和譯著，包括《程序設計語言基礎》（譯著，北京大學出版社，1990），《Mathematica數學軟件系統的應用與程序設計》（編著，北京大學出版社，1994），《計算概論（上）》（合著，高等教育出版社，1997），《從問題到程序—程序設計與C語言引論》（編著，北京大學出版社，1999）等；自2000年以來，他先後為機械工業出版社華章分社翻譯了《程序設計實踐》（2000），《C++程序設計語言（特別版）》（2001），《C++語言的設計和演化》（2002），《程序設計語言——概念和結構》（2002），《從規範出發的程序設計》（2003），《計算機程序的構造和解釋》（2004）等一系列經典著作，他認真的工作作風、嚴謹的治學態度，以及所做出的巨大貢獻，贏得廣大讀者的好評。在北京大學教授的主要課程：計算概論（一年級本科生，主要內容為C語言程序設計），程序設計技術與方法（本科生），程序設計語言原理（研究生），算法和數據結構（本科生），算法設計與分析（本科生和研究生），數理邏輯（本科生）等。

前言
第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 算法的代價及其度量13
1.3.3 算法分析19
1.3.4 Python程序的計算代價（複雜度）21
1.4 數據結構24
1.4.1 數據結構及其分類24
1.4.2 計算機內存對象表示27
1.4.3 Python對象和數據結構30
練習32
第2章 抽像數據類型和Python類34
2.1 抽像數據類型34
2.1.1 數據類型和數據構造34
2.1.2 抽像數據類型的概念36
2.1.3 抽像數據類型的描述37
2.2 Python的類和麵向對象編程39
2.2.1 類的定義和使用39
2.2.2 繼承44
2.2.3 異常類和自定義異常48
2.2.4 本書採用的ADT描述形式50
總結50
練習51
第3章 線性表53
3.1 線性表的概念和表抽像數據類型53
3.1.1 表的概念和性質53
3.1.2 表抽像數據類型53
3.1.3 線性表的實現：基本考慮55
3.2 順序表56
3.2.1 基本實現方式56
3.2.2 順序表基本操作的實現57
3.2.3 順序表的實現結構61
3.2.4 Python的list64
3.2.5 順序表的簡單總結65
3.3 ***表66
3.3.1 線性表的基本需要和***表66
3.3.2 單鍊錶67
3.3.3 單鍊錶類的實現72
3.4 鍊錶的變形和操作75
3.4.1 單鍊錶的簡單變形75
3.4.2 循環單鍊錶78
3.4.3 雙鍊錶79
3.4.4 兩個鍊錶操作81
3.4.5 在順序表裡實現“鍊錶”85
3.4.6 不同鍊錶的簡單總結86
3.5 表的應用87
3.5.1 Josephus問題和基於數組概念的解法87
3.5.2 基於順序表的解88
3.5.3 基於循環單鍊錶的解88
*3.6 廣義表和數組 本書中標星號的小節為選學/選講內容。 89
3.6.1 廣義表89
3.6.2 數組92
3.6.3 矩陣94
總結97
練習98
第4章 字符串102
4.1 字符集、字符串和字符串操作102
4.1.1 字符串的相關概念102
4.1.2 字符串抽像數據類型104
4.2 字符串的實現104
4.2.1 基本實現問題和技術104
4.2.2 實際語言裡的字符串105
4.2.3 Python的字符串106
4.3 字符串匹配（子串查找）107
4.3.1 字符串匹配問題107
4.3.2 串匹配和朴素匹配算法108
4.3.3 無回溯串匹配算法（KMP算法）110
4.4 字符串匹配問題115
4.4.1 串匹配/搜索的不同需要115
4.4.2 一種簡化的正則表達式117
*4.5 Python正則表達式119
4.5.1 正則表達式標準庫包re119
4.5.2 基本情況119
4.5.3 主要操作120
4.5.4 正則表達式的構造121
4.5.5 正則表達式的使用127
總結127
練習128
第5章 棧和隊列130
5.1 概述130
5.1.1 棧、隊列和數據使用順序130
5.1.2 應用環境131
5.2 棧：概念和實現131
5.2.1 棧抽像數據類型131
5.2.2 棧的順序表實現132
5.2.3 棧的***表實現134
5.3 棧的應用134
5.3.1 簡單應用：括號匹配問題135
5.3.2 表達式的表示、計算和變換137
5.3.3 棧與遞歸144
5.4 隊列149
5.4.1 隊列抽像數據類型149
5.4.2 隊列的***表實現150
5.4.3 隊列的順序表實現150
5.4.4 隊列的list實現152
5.4.5 隊列的應用155
5.5 迷宮求解和狀態空間搜索156
5.5.1 迷宮求解：分析和設計156
5.5.2 求解迷宮的算法159
5.5.3 迷宮問題和搜索161
5.6 幾點補充166
5.6.1 與棧或隊列相關的幾種結構166
5.6.2 順序實現和***實現166
總結167
練習168
第6章 二叉樹和樹170
6.1 二叉樹170
6.1.1 概念和性質170
6.1.2 抽像數據類型175
6.1.3 遍歷二叉樹176
6.2 二叉樹的list實現177
6.2.1 設計和實現178
6.2.2 二叉樹的簡單應用：表達式樹179
6.3 優先隊列182
6.3.1 概念182
6.3.2 基於線性表的實現183
6.3.3 樹形結構和堆185
6.3.4 優先隊列的堆實現186
6.3.5 堆的應用：堆排序189
6.4 應用：離散事件模擬190
6.4.1 通用的模擬框架191
6.4.2 海關檢查站模擬系統192
6.5 二叉樹的類實現196
6.5.1 二叉樹結點類197
6.5.2 遍曆算法198
6.5.3 二叉樹類202
6.6 哈夫曼樹203
6.6.1 哈夫曼樹和哈夫曼算法203
6.6.2 哈夫曼算法的實現204
6.6.3 哈夫曼編碼205
6.7 樹和樹林207
6.7.1 實例和表示207
6.7.2 定義和相關概念208
6.7.3 抽像數據類型和操作210
6.7.4 樹的實現211
6.7.5 樹的Python實現212
*6.8 等價類和查並集214
6.8.1 概念和問題214
6.8.2 樸素實現215
6.8.3 用樹表示集合215
6.8.4 優化結構217
總結219
練習220
第7章 圖224
7.1 概念、性質和實現224
7.1.1 定義和圖示224
7.1.2 圖的一些概念和性質225
7.1.3 圖抽像數據類型228
7.1.4 圖的表示和實現228
7.2 圖的Python實現231
7.2.1 鄰接矩陣實現232
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 最短路徑247
7.5.1 最短路徑問題248
7.5.2 求解單源點最短路徑：Dijkstra算法248
7.5.3 求解所有頂點之間的最短路徑：Floyd算法251
7.5.4 最短路徑問題254
7.6 AOV網/AOE網及其算法254
7.6.1 AOV網、拓撲排序和拓撲序列255
7.6.2 拓撲排序算法256
7.6.3 AOE網和關鍵路徑258
7.6.4 關鍵路徑算法258
總結261
練習261
第8章 字典和集合264
8.1 數據存儲、檢索和字典264
8.1.1 數據存儲和檢索264
8.1.2 字典實現的問題266
8.2 字典的線性表實現268
8.2.1 基本實現268
8.2.2 有序順序表和二分法檢索269
8.2.3 線性表字典總結271
8.3 散列和散列表272
8.3.1 散列的思想和應用272
8.3.2 散列函數274
8.3.3 衝突的內消解：開地址技術276
8.3.4 外消解技術279
8.3.5 散列表的性質279
8.4 集合281
8.4.1 集合的概念、運算和抽像數據類型281
8.4.2 集合的實現283
8.4.3 特殊實現技術：位向量實現284
8.5 Python的標準字典類dict和集合類set285
8.6 二叉排序樹和字典286
8.6.1 二叉排序樹287
8.6.2 二叉排序樹294
8.6.3 一般情況的二叉排序樹296
8.7 平衡二叉樹301
8.7.1 定義和性質302
8.7.2 AVL樹類303
8.7.3 插入操作303
*8.7.4 刪除操作309
8.7.5 幾種二叉排序樹的對比312
8.8 動態多分支排序樹和外存字典313
8.8.1 多分支排序樹313
8.8.2 B樹314
8.8.3 B＋樹316
*8.8.4 外存字典317
總結319
練習320
第9章 排序322
9.1 問題和性質322
9.1.1 問題定義322
9.1.2 排序算法323
9.2 簡單排序算法325
9.2.1 插入排序326
9.2.2 選擇排序327
9.2.3 交換排序329
9.3 快速排序331
9.3.1 快速排序的表實現331
9.3.2 程序實現332
9.3.3 複雜度分析333
9.3.4 另一種簡單實現334
9.4 歸併排序335
9.4.1 順序表的歸併排序示例335
9.4.2 歸併算法的設計和實現336
9.4.3 算法分析337
9.5 其他排序方法和問題338
9.5.1 分配排序和基數排序338
9.5.2 一些情況340
9.5.3 Python系統的排序算法342
*9.6 外排序問題和算法343
9.6.1 外存數據的排序問題343
9.6.2 基本外存排序算法343
9.6.3 多路歸併345
總結347
練習348
參考文獻350