《數據結構：Python語言描述》是2020年2月人民郵電出版社出版的圖書，作者是[美] Kenneth A. Lambert。
基本介紹
- 書名：數據結構：Python語言描述
- 作者：[美] Kenneth A. Lambert
- 出版社：人民郵電出版社
- 出版時間：2020年2月
- 頁數：300 頁
- 定價：69 元
- 開本：16 開
- 裝幀：平裝
- ISBN：9787115464613
內容簡介,圖書目錄,
內容簡介
在計算機科學中，數據結構是一門進階性備組課程，概念抽象，難度較大。Python語言的語法簡單，互動性強。用Python來講解數據結構等主題，比C語言等實現起來更為容易，更為清晰。
《數據結構 Python語言描述》第 1章簡單介紹了Python語言的基礎知識和特性。第 2章到第4章對抽象數據類型、數據結構、複雜度分析、數組和線性鍊表結構進行了詳細介紹，第5章和第6章重點介紹了面向對象設計的相關知識、第5章包括接口和實現之間的重點差異、多態以及信息隱藏等內容，第6章主要講解繼承的相關知識，第7章到第9章以棧、佇列和列表為代表，介紹芝歡棄境了線性集合的相關知識。第 10章介紹了各種樹結構，第 11章槓凳洪講解了集和字典的相關內容，第 12章介紹了圖和圖處理算法。每章**後，還給出了複習題和案例學習，幫助讀者鞏固和思考。
《數據結構 Python語言描述》不僅適合高等院校計算機專業師生閱讀，也適合對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
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
