本書基于Python語言介紹了數據結構與算法的基本知識，主要內容包括抽象數據類型和Python面向對象程序設計、線性表、字符串、棧和隊列、二叉樹和樹、集合、排序以及算法的基本知識。本書延續問題求解的思路，從解決問題的目標來組織教學內容，注重理論與實踐的并用。
目 錄
前言
第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
新書資訊