數據結構（Python語言描述）

第1章 Python編程基礎 1
1.1 基本程序要素 1
1.1.1 程序和模塊 1
1.1.2 Python程序示例：猜數字 1
1.1.3 編輯、編譯並運行Python程序 2
1.1.4 程序注釋 3
1.1.5 詞法元素 3
1.1.6 拼寫和命名慣例 3
1.1.7 語法元素 4
1.1.8 字面值 4
1.1.9 字符串字面值 4
1.1.10 運算符和表達式 5
1.1.11 函數調用 5
1.1.12 print函數 5
1.1.13 input函數 5
1.1.14 類型轉換函數和混合模式運算 6
1.1.15 可選的和關鍵字函數參數 6
1.1.16 變量和賦值語句 6
1.1.17 Python數據類型 7
1.1.18 import語句 7
1.1.19 獲取關於程序組件的幫助 7
1.2 控制語句 8
1.2.1 條件式語句 8
1.2.2 使用if __name__ ==”__main__” 9
1.2.3 循環語句 10
1.3 字符串及其運算 10
1.3.1 運算符 10
1.3.2 格式化字符串以便輸出 11
1.3.3 對象和方法調用 13
1.4 內建Python集合及其操作 13
1.4.1 列表 14
1.4.2 元組 14
1.4.3 遍歷序列 14
1.4.4 字典 15
1.4.5 搜索一個值 15
1.4.6 對集合應用模式匹配 15
1.5 編寫新的函數 16
1.5.1 函數定義 16
1.5.2 遞歸函數 17
1.5.3 嵌套的函數定義 19
1.5.4 高階函數 19
1.5.5 使用lambda表達式創建匿名函數 20
1.6 捕獲異常 20
1.7 文件及其操作 21
1.7.1 文本文件的輸出 22
1.7.2 將數字寫入到一個文本文件 22
1.7.3 從文本文件讀取文本 23
1.7.4 從文件讀取數字 24
1.7.5 使用pickle讀寫對象 24
1.8 創建新的類 25
1.9 編程項目 28

第2章 集合概覽 30
2.1 集合類型 30
2.1.1 線性集合 30
2.1.2 層級集合 31
2.1.3 圖集合 31
2.1.4 無序集合 31
2.1.5 有序集合 31
2.1.6 集合類型的分類 32
2.2 集合上的操作 32
2.3 集合的實現 34
2.4 小結 35
2.5 復習題 35
2.6 編程項目 36

第3章 搜索、排序和復雜度分析 37
3.1 評估算法的性能 37
3.1.1 度量算法的運行時間 37
3.1.2 統計指令 39
3.1.3 度量算法所使用的內存 41
3.1.4 練習3.1 41
3.2 復雜度分析 41
3.2.1 復雜度的階 41
3.2.2 大O表示法 43
3.2.3 常量比例的作用 43
3.2.4 練習3.2 43
3.3 搜索算法 44
3.3.1 搜索最小值 44
3.3.2 順序搜索一個列表 44
3.3.3 最好情況、最壞情況和平均情況的性能 45
3.3.4 有序列表的二叉搜索 45
3.3.5 比較數據項 47
3.3.6 練習3.3 48
3.4 基本排序算法 48
3.4.1 選擇排序 48
3.4.2 冒泡排序 49
3.4.3 插入排序 50
3.4.4 再談最好情況、最壞情況和平均情況的性能 52
3.4.5 練習3.4 52
3.5 更快的排序 53
3.5.1 快速排序簡介 53
3.5.2 合並排序 56
3.5.3 練習3.5 59
3.6 指數算法：遞歸式的Fibonacci 59
3.7 案例學習：算法探查器 61
3.7.1 需求 61
3.7.2 分析 61
3.7.3 設計 62
3.7.4 實現（編寫代碼） 63
3.8 小結 65
3.9 復習題 66
3.10 編程項目 67

第4章 數組和鏈表結構 69
4.1 數組數據結構 69
4.1.1 隨機訪問和連續內存 71
4.1.2 靜態內存和動態內存 72
4.1.3 物理大小和邏輯大小 72
4.1.4 練習4.1 73
4.2 數組的操作 73
4.2.1 增加數組的大小 73
4.2.2 減小數組的大小 74
4.2.3 在數組中插入一項 74
4.2.4 從數組中刪除一項 75
4.2.5 復雜度權衡：時間、空間和數組 76
4.2.6 練習4.2 76
4.3 二維數組 77
4.3.1 處理網格 77
4.3.2 創建並初始化網格 77
4.3.3 定義Grid類 78
4.3.4 雜亂的網格和多維數組 79
4.3.5 練習4.3 79
4.4 鏈表結構 80
4.4.1 單鏈表結構和雙鏈表結構 80
4.4.2 非連續性內存和節點 81
4.4.3 定義一個單鏈表節點類 82
4.4.4 使用單鏈表節點類 82
4.4.5 練習4.4 84
4.5 單鏈表結構上的操作 84
4.5.1 遍歷 84
4.5.2 搜索 85
4.5.3 替換 86
4.5.4 在開始處插入 86
4.5.5 在末尾插入 87
4.5.6 從開始處刪除 87
4.5.7 從末尾刪除 88
4.5.8 在任何位置插入 89
4.5.9 從任意位置刪除 90
4.5.10 復雜度權衡：時間、空間和單鏈表結構 91
4.5.11 練習4.5 92
4.6 鏈表的變體 92
4.6.1 帶有一個啞頭節點的循環鏈表結構 92
4.6.2 雙鏈表結構 93
4.6.3 練習4.6 95
4.7 小結 95
4.8 復習題 96
4.9 編程項目 96

第5章 接口、實現和多態 98
5.1 開發接口 98
5.1.1 定義包接口 98
5.1.2 指定參數和返回值 99
5.1.3 構造方法和實現類 101
5.1.4 先驗條件、后驗條件、異常和文檔 101
5.1.5 用Python編寫接口 102
5.1.6 練習5.1 103
5.2 開發一個基於數組的實現 103
5.2.1 選擇並初始化數據結構 103
5.2.2 先完成容易的方法 104
5.2.3 完成迭代器 105
5.2.4 完成使用迭代器的方法 106
5.2.5 in運算符和__contains__方法 106
5.2.6 完成remove方法 107
5.2.7 練習5.2 107
5.3 開發一個基於鏈表的實現 107
5.3.1 初始化數據結構 108
5.3.2 完成迭代器 109
5.3.3 完成clear和add方法 109
5.3.4 完成remove方法 109
5.3.5 練習5.3 110
5.4 兩個包實現的運行時性能 110
5.5 測試兩個包實現 111
5.6 用UML圖表示包資源 112
5.7 小結 113
5.8 復習題 113
5.9 編程項目 114

第6章 繼承和抽象類 115
6.1 使用繼承定制一個已有的類 115
6.1.1 已有類的子類化 115
6.1.2 再談__init__方法 116
6.1.3 添加新的contains方法 117
6.1.4 修改已有的add方法 117
6.1.5 ArraySortedBag的運行時間性能 118
6.1.6 Python中的類層級 118
6.1.7 練習6.1 119
6.2 使用抽象類去除代碼冗余性 119
6.2.1 設計一個AbstractBag類 119
6.2.2 重新編寫AbstractBag中的__init__方法 120
6.2.3 修改AbstractBag的子類 120
6.2.4 將AbstractBag中的__add__方法泛化 121
6.3 所有集合的一個抽象類 122
6.3.1 將AbstractCollection整合到集合層級中 122
6.3.2 在__eq__方法中使用兩個迭代器 123
6.3.3 練習6.2 124
6.4 小結 124
6.5 復習題 124
6.6 編程項目 125

第7章 棧 127
7.1 棧概覽 127
7.2 使用棧 128
7.2.1 棧接口 128
7.2.2 初始化一個棧 129
7.2.3 示例應用程序：匹配括號 129
7.2.4 練習7.1 131
7.3 棧的3種應用 131
7.3.1 計算算術表達式 131
7.3.2 計算后綴表達式 132
7.3.3 練習7.2 133
7.3.4 將中綴表達式轉換為后綴表達式 133
7.3.5 練習7.3 135
7.3.6 回溯算法 135
7.3.7 內存管理 137
7.4 棧的實現 138
7.4.1 測試驅動程序 138
7.4.2 將棧添加到集合層級中 139
7.4.3 數組實現 140
7.4.4 鏈表實現 141
7.4.5 AbstractStack類的作用 144
7.4.6 兩種實現的時間和空間分析 144
7.4.7 練習7.4 145
7.5 案例學習：計算后綴表達式 145
7.5.1 要求 145
7.5.2 分析 145
7.5.3 設計 148
7.5.4 實現 150
7.6 小結 153
7.7 復習題 153
7.8 編程項目 154

第8章 隊列 156
8.1 隊列概覽 156
8.2 隊列接口及其應用 157
練習8.1 158
8.3 隊列的兩個應用 159
8.3.1 模擬 159
8.3.2 輪詢CPU調度 161
8.3.3 練習8.2 161
8.4 隊列的實現 161
8.4.1 隊列的鏈表實現 161
8.4.2 數組實現 163
8.4.3 兩種實現的時間和空間復雜度分析 164
8.4.4 練習8.3 165
8.5 案例學習：模擬超市排隊結賬 165
8.5.1 要求 165
8.5.2 分析 165
8.5.3 用戶界面 166
8.5.4 類及其作用 166
8.6 優先隊列 171
練習8.4 175
8.7 案例學習：急症室調度 175
8.7.1 需求 175
8.7.2 分析 175
8.7.3 類 176
8.7.4 設計和實現 177
8.8 小結 179
8.9 復習題 179
8.10 編程項目 180

第9章 列表 182
9.1 概覽 182
9.2 使用列表 183
9.2.1 基於索引的操作 183
9.2.2 基於內容的操作 183
9.2.3 基於位置的操作 184
9.2.4 列表的接口 187
9.2.5 練習9.1 188
9.3 列表的應用 188
9.3.1 堆存儲管理 188
9.3.2 組織磁盤上的文件 189
9.3.3 其他集合的實現 190
9.4 列表實現 191
9.4.1 AbstractList類的角色 191
9.4.2 基於數組的實現 192
9.4.3 鏈表實現 194
9.4.4 兩種實現的時間和空間分析 196
9.4.5 練習9.2 197
9.5 實現列表迭代器 197
9.5.1 列表迭代器的角色和作用 197
9.5.2 設置和實例化一個列表迭代器類 198
9.5.3 列表迭代器中的導航方法 199
9.5.4 列表迭代器中的修改器方法 200
9.5.5 鏈表列表的列表迭代器的設計 201
9.5.6 列表迭代器實現的時間和空間分析 201
9.6 案例學習：開發一個有序的列表 201
9.6.1 要求 201
9.6.2 分析 202
9.6.3 設計 202
9.6.4 實現（代碼） 204
9.7 小結 205
9.8 復習題 205
9.9 編程項目 206

第10章 樹 208
10.1 樹的概覽 208
10.1.1 樹的術語 208
10.1.2 普通的樹和二叉樹 209
10.1.3 樹的遞歸定義 210
10.1.4 練習10.1 210
10.2 為什麼要使用樹 210
10.3 二叉樹的形狀 211
練習10.2 213
10.4 二叉樹的3種常見應用 213
10.4.1 堆 213
10.4.2 二叉搜索樹 214
10.4.3 表達式樹 215
10.4.4 練習10.3 216
10.5 二叉樹的遍歷 216
10.5.1 前序遍歷 216
10.5.2 中序遍歷 217
10.5.3 后序遍歷 217
10.5.4 層序遍歷 217
10.6 開發二叉搜索樹 217
10.6.1 二叉搜索樹接口 218
10.6.2 鏈表實現的數據結構 219
10.6.3 二叉搜索樹的復雜度分析 223
10.6.4 練習10.4 224
10.7 遞歸的后代解析和編程語言 224
10.7.1 語法簡介 224
10.7.2 在語言中識別、解析和解釋句子 226
10.7.3 詞法分析和掃描器 226
10.7.4 解析策略 227
10.8 案例學習：解析和表達式樹 227
10.8.1 要求 227
10.8.2 分析 228
10.8.3 節點類的設計和實現 228
10.8.4 解析器類的設計和實現 230
10.9 二叉樹的數組實現 231
練習10.5 232
10.10 實現堆 232
練習10.6 234
10.11 小結 234
10.12 復習題 235
10.13 編程項目 236

第11章 集和字典 238
11.1 使用集 238
11.2 Python的set類 239
11.2.1 集的一個示例會話 239
11.2.2 集的應用 240
11.2.3 集和包的關系 240
11.2.4 集和字典的關系 240
11.2.5 集的實現 240
11.2.6 練習11.1 241
11.3 集的基於數組和鏈表的實現 241
11.3.1 AbstractSet類 241
11.3.2 ArraySet類 242
11.4 使用字典 243
11.5 基於數組和基於鏈表的字典實現 244
11.5.1 Item類 244
11.5.2 AbstractDict類 245
11.5.3 ArrayDict類 246
11.5.4 集和字典的基於數組和列表的實現的復雜度分析 247
11.5.5 練習11.2 248
11.6 哈希策略 248
11.6.1 沖突和密度的關系 249
11.6.2 非數字鍵的哈希 250
11.6.3 線性探測 251
11.6.4 二次探測 252
11.6.5 鏈化 253
11.6.6 復雜度分析 253
11.6.7 練習11.3 254
11.7 案例學習：探查哈希策略 254
11.7.1 需求 255
11.7.2 分析 255
11.7.3 設計 256
11.8 集的哈希實現 258
11.9 字典的哈希實現 261練習11.4 263
11.10 有序的集和字典 263
11.11 小結 264
11.12 復習題 264
11.13 編程項目 265

第12章 圖 267
12.1 圖的術語 267練習12.1 269
12.2 為什麼使用圖 270
12.3 圖的表示 270
12.3.1 相鄰矩陣 270
12.3.2 鄰接表 271
12.3.3 兩種表示的分析 272
12.3.4 運行時間的進一步考慮 272
12.3.5 練習12.2 273
12.4 圖的遍歷 273
12.4.1 泛型遍歷算法 273
12.4.2 廣度優先遍歷和深度優先遍歷 274
12.4.3 圖區域 275
12.4.4 練習12.3 276
12.5 圖中的樹 276
12.5.1 生成樹和森林 276
12.5.2 最小生成樹 277
12.5.3 最小生成樹的算法 277
12.6 拓撲排序 279
12.7 最短路徑問題 279
12.7.1 Dijkstra算法 280
12.7.2 初始化步驟 280
12.7.3 計算步驟 281
12.7.4 無限的表示和用法 282
12.7.5 分析 282
12.7.6 練習12.4 282
12.7.7 Floyd算法 283
12.7.8 分析 283
12.8 開發一個圖集合 284
12.8.1 使用圖集合的示例 284
12.8.2 LinkedDirected-Graph類 285
12.8.3 LinkedVertex類 288
12.8.4 LinkedEdge類 289
12.9 案例學習：測試圖算法 290
12.9.1 需求 290
12.9.2 分析 290
12.9.3 GraphDemoView類和GraphDemoModel類 291
12.9.4 實現（代碼） 292
12.10 小結 295
12.11 復習題 296
12.12 編程項目 297

附錄 供Python程序員使用的
集合框架 299