數據結構 Python語言描述

《數據結構 Python語言描述》一書由Kenneth，A.，Lambert，蘭伯特 所著，人民郵電出版社出版發行。

基本介紹

• 中文名：數據結構 Python語言描述
• 作者：Kenneth、A.，Lambert、蘭伯特
• 出版社：人民郵電出版社
• 出版時間：2017年12月1日
• 頁數：300 頁
• 開本：16 開
• 裝幀：平裝
• ISBN：9787115464613 

內容簡介

在計算機科學中，數據結構是一門進階性課程，概念抽象，難度較大。Python語言的語法簡單，互動性強。用Python來講解數影汽肯凳據結構等主題，比C語言等實現起來更為容易，更為清晰。

《數據結構 Python語言描述》第1章簡單介紹了Python語言的基礎知識和特性。第2章到第4章對抽象數據類型、數據結構、複雜度分析、數組和線性鍊表結構進行了詳細介紹，第5章和第6章重點介紹了面向對象設計的相關知識、第5章包括接口和實現之間的重點差異、多態以及信息隱藏等內容，第6章主要講解繼承的相關知識，第7章到第9章以棧、佇列和列表為代表，介紹了線性集合的相關知識。第10章介紹了各種樹結構，第11章講解了集和字典的相關內容，第12章介紹了圖和圖處理算法。每章最後，還給出了複習題和案例學習，幫助讀者鞏固和思考。

《數據結構 Python語言描述》不僅適合高等院校計算機專業師生閱讀，也適合對Python感興趣的讀者和程式設計師閱讀。

作者簡介

Kenneth A .Lambert是華盛頓與李大學的計算機科學教授和系主任。他教授編程課程30 年 ，並且是計算機科學教育的積極研究者。Lambert編著以及與人合著了一共2 5 本教材，包括與Douglas Nance和Thomas Naps編寫的一系列C++ 入門教材，與Martin Osbor ne編寫的一系列Java入門教材， 以及一系列Python入門教材。他還是《Easy GUI Progr amming in 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

"__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