數據結構：Python語言描述第2版

《數據結構：Python語言描述第2版》是2021年人民郵電出版社出版的圖書。

基本介紹

• 中文名：數據結構：Python語言描述第2版
• 作者：[美]肯尼思·A.蘭伯特
• 出版社：人民郵電出版社
• 出版時間：2021年7月1日
• 開本：16 開
• 裝幀：平裝
• ISBN：9787115551481

內容簡介

本書用 Python 語言來講解數據結構及實現方法。全書首先概述 Python 編程的功能—這些功能是實際編程和解決問題時所必需的；其次介紹抽象數據類型的規範、實現和套用，多項集類型，以及接口和實現之間的重要差異；隨後介紹線性多項集、棧、佇列和列表；最後介紹樹、圖等內容。本書附有大量的複習題和編程項目，旨在幫助讀者鞏固所學知識。

本書不僅適合高等院校計算機專業師生閱讀，也適合對 Python 感興趣的讀者和程式設計師閱讀。

圖書目錄

第 1章 Python編程基礎 1

1．1 基本程式要素 1

1．1．1 程式和模組 1

1．1．2 Python的示例程式：猜數字 2

1．1．3 編輯、編譯並運行Python程式 3

1．1．4 程式注釋 3

1．1．5 詞法元素 3

1．1．6 拼寫和命名慣例 4

1．1．7 語法元素 4

1．1．8 字面值 4

1．1．9 運算符和表達式 5

1．1．10 函式調用 5

1．1．11 print函式 6

1．1．12 input函式 6

1．1．13 類型轉換函式和混合模式操作 6

1．1．14 可選和關鍵字函式參數 6

1．1．15 變數和賦值語句 7

1．1．16 Python的數據類型 7

1．1．17 import語句 7

1．1．18 獲取關於程式組件的幫助 8

1．2 控制語句 8

1．2．1 條件語句 9

1．2．2 使用if _name_ == "_main_" 9

1．2．3 循環語句 10

1．3 字元串及其運算 11

1．3．1 運算符 11

1．3．2 格式化字元串以便輸出 12

1．3．3 對象和方法調用 13

1．4 Python內置的多項集及其操作 14

1．4．1 列表 14

1．4．2 元組 15

1．4．3 遍歷整個序列 15

1．4．4 字典 15

1．4．5 搜尋一個值 16

1．4．6 通過模式匹配來訪問多項集 16

1．5 創建新函式 17

1．5．1 函式定義 17

1．5．2 遞歸函式 18

1．5．3 函式的嵌套定義 19

1．5．4 高階函式 20

1．5．5 使用lambda表達式創建匿名函式 21

1．6 捕獲異常 21

1．7 檔案及其操作 22

1．7．1 文本檔案的輸出 23

1．7．2 將數字寫入文本檔案 23

1．7．3 從文本檔案讀取文本 24

1．7．4 從檔案讀取數據 25

1．7．5 使用pickle讀寫對象 26

1．8 創建新類 27

1．9 編程項目 29

第 2章 多項集的概述 32

2．1 多項集類型 32

2．1．1 線性多項集 33

2．1．2 分層多項集 33

2．1．3 圖多項集 33

2．1．4 無序多項集 33

2．1．5 有序多項集 34

2．1．6 多項集類型的分類 34

2．2 多項集操作 35

2．2．1 所有多項集類型中的基本操作 35

2．2．2 類型轉換 36

2．2．3 克隆和相等性 36

2．3 疊代器和高階函式 37

2．4 多項集的實現 37

2．5 章節總結 38

2．6 複習題 39

2．7 編程項目 40

第3章 搜尋、排序以及複雜度分析 41

3．1 衡量算法的效率 41

3．1．1 衡量算法的運行時 42

3．1．2 統計指令數 43

3．1．3 衡量算法使用的記憶體 45

3．2 複雜度分析 45

3．2．1 複雜度的階 45

3．2．2 大O表示法 47

3．2．3 比例常數的作用 47

3．3 搜尋算法 48

3．3．1 最小值搜尋 48

3．3．2 順序搜尋列表 49

3．3．3 最好情況、最壞情況以及平均情況下的性能 49

3．3．4 基於有序列表的二分搜尋 50

3．3．5 比較數據元素 51

3．4 基本的排序算法 52

3．4．1 選擇排序 53

3．4．2 冒泡排序 53

3．4．3 插入排序 55

3．4．4 再論最好情況、最壞情況以及平均情況下的性能 56

3．5 更快的排序 57

3．5．1 快速排序 57

3．5．2 歸併排序 60

3．6 指數複雜度的算法：遞歸斐波那契 63

3．7 案例研究：算法分析器 65

3．7．1 案例需求 65

3．7．2 案例分析 65

3．7．3 案例設計 66

3．7．4 案例實現（編碼） 67

3．8 章節總結 69

3．9 複習題 70

3．10 編程項目 71

第4章 數組和連結結構 73

4．1 數組數據結構 73

4．1．1 隨機訪問和連續記憶體 75

4．1．2 靜態記憶體和動態記憶體 76

4．1．3 物理尺寸和邏輯尺寸 76

4．2 數組的操作 77

4．2．1 增大數組的尺寸 77

4．2．2 減小數組的尺寸 78

4．2．3 將元素插入增大的數組 78

4．2．4 從數組裡刪除元素 79

4．2．5 複雜度的權衡：時間、空間和數組 80

4．3 二維數組（格線） 81

4．3．1 使用格線 81

4．3．2 創建並初始化格線 82

4．3．3 定義Grid類 82

4．3．4 參差不齊的格線和多維數組 83

4．4 連結結構 84

4．4．1 單向連結結構和雙向連結結構 84

4．4．2 非連續記憶體和節點 85

4．4．3 定義單向連結節點類 86

4．4．4 使用單向連結節點類 87

4．5 單向連結結構上的操作 88

4．5．1 遍歷 88

4．5．2 搜尋 89

4．5．3 替換 90

4．5．4 在開始處插入 90

4．5．5 在結尾處插入 91

4．5．6 在開始處刪除 92

4．5．7 在結尾處刪除 93

4．5．8 在任意位置處插入 94

4．5．9 在任意位置處刪除 95

4．5．10 複雜度的權衡：時間、空間和單向連結結構 96

4．6 連結上的變化 97

4．6．1 包含虛擬頭節點的環狀連結結構 97

4．6．2 雙向連結結構 98

4．7 章節總結 100

4．8 複習題 101

4．9 編程項目 102

第5章 接口、實現和多態 104

5．1 開發接口 104

5．1．1 設計包接口 105

5．1．2 指定參數和返回值 106

5．2 構造函式和類的實現 107

5．2．1 前置條件、後置條件、異常和文檔 107

5．2．2 在Python里編寫接口 108

5．3 開發基於數組的實現 110

5．3．1 選擇並初始化數據結構 110

5．3．2 先完成簡單的方法 111

5．3．3 完成疊代器 112

5．3．4 完成使用疊代器的方法 112

5．3．5 in運算符和_contains_方法 113

5．3．6 完成remove方法 113

5．4 開發基於連結的實現 114

5．4．1 初始化數據結構 115

5．4．2 完成疊代器 115

5．4．3 完成clear和add方法 115

5．4．4 完成remove方法 116

5．5 兩種包實現的運行時性能 117

5．6 測試包的兩種實現 117

5．7 使用UML繪製包資源 118

5．8 章節總結 119

5．9 複習題 120

5．10 編程項目 120

第6章 繼承與抽象類 122

6．1 使用繼承定製已經存在的類 122

6．1．1 已有類的子類 123

6．1．2 修改_init_方法 123

6．1．3 添加新的_contains_方法 124

6．1．4 修改已有的add方法 125

6．1．5 修改已有的_add_方法 126

6．1．6 ArraySortedBag的運行時性能 126

6．1．7 Python里類的層次結構的解釋 126

6．2 使用抽象類消除冗餘代碼 127

6．2．1 設計AbstractBag類 127

6．2．2 重新編寫AbstractBag類的_init_方法 128

6．2．3 修改AbstractBag的子類 129

6．2．4 在AbstractBag里模板化_add_方法 129

6．3 所有多項集的抽象類 130

6．3．1 把AbstractCollection添加到多項集的層次結構里 130

6．3．2 在_eq_方法裡使用兩個疊代器 131

6．4 多項集的專家級框架 132

6．5 章節總結 134

6．6 複習題 134

6．7 編程項目 135

第7章 棧 137

7．1 棧的概述 137

7．2 使用棧 138

7．2．1 棧接口 138

7．2．2 棧的實例化 140

7．2．3 示例應用程式：括弧匹配 140

7．3 棧的3個應用程式 142

7．3．1 算術表達式的求值 142

7．3．2 計算後綴表達式 143

7．3．3 把中綴表達式轉換為後綴表達式 144

7．3．4 回溯算法 146

7．3．5 記憶體管理 148

7．4 棧的實現 150

7．4．1 測試驅動 150

7．4．2 將棧添加到多項集的層次結構 151

7．4．3 棧的數組實現 152

7．4．4 棧的連結實現 153

7．4．5 抽象棧類的作用 155

7．4．6 兩種實現的時間和空間複雜度分析 156

7．5 案例研究：計算後綴表達式 157

7．5．1 案例需求 157

7．5．2 案例分析 157

7．5．3 案例設計 160

7．5．4 案例實現 163

7．6 章節總結 165

7．7 複習題 165

7．8 編程項目 166

第8章 佇列 168

8．1 佇列的概述 168

8．2 佇列接口及其使用 169

8．3 佇列的兩個套用 171

8．3．1 計算機模擬 171

8．3．2 CPU的輪詢調度 173

8．4 佇列的實現 174

8．4．1 佇列的連結實現 174

8．4．2 佇列的數組實現 175

8．4．3 兩種實現的時間和空間複雜度分析 177

8．5 案例研究：超市收銀排隊的模擬 178

8．5．1 案例需求 178

8．5．2 案例分析 178

8．5．3 用戶互動接口 178

8．5．4 類和它們的職責 179

8．6 優先佇列 184

8．7 案例研究：急診室調度程式 188

8．7．1 案例需求 188

8．7．2 案例分析 188

8．7．3 類 189

8．7．4 案例設計與實現 189

8．8 章節總結 191

8．9 複習題 192

8．10 編程項目 193

第9章 列表 194

9．1 列表的概述 194

9．2 使用列表 195

9．2．1 基於索引的操作 196

9．2．2 基於內容的操作 196

9．2．3 基於位置的操作 196

9．2．4 列表接口 200

9．3 列表的套用 201

9．3．1 堆存儲管理 201

9．3．2 磁碟檔案管理 202

9．3．3 其他多項集的實現 203

9．4 列表的實現 204

9．4．1 AbstractList類的作用 204

9．4．2 基於數組的實現 205

9．4．3 列表的連結實現 207

9．4．4 兩種實現的時間和空間複雜度分析 209

9．5 實現列表疊代器 211

9．5．1 列表疊代器的角色和職責 211

9．5．2 設定和實例化列表疊代器類 211

9．5．3 列表疊代器里的導航方法 212

9．5．4 列表疊代器里的變異器方法 213

9．5．5 設計連結列表的列表疊代器 215

9．5．6 列表疊代器實現的時間和空間複雜度分析 215

9．6 案例研究：開發有序列表 215

9．6．1 案例需求 215

9．6．2 案例分析 215

9．6．3 案例設計 216

9．6．4 案例實現（編碼） 218

9．7 遞歸列表的處理 219

9．7．1 類Lisp列表的基本操作 220

9．7．2 類Lisp列表的遞歸遍歷 221

9．7．3 創建類Lisp列表 222

9．7．4 類Lisp列表的內部結構 223

9．7．5 使用_repr_在IDLE里輸出類Lisp列表 224

9．7．6 列表和函式式編程 225

9．8 章節總結 225

9．9 複習題 226

9．10 編程項目 227

第 10章 樹 229

10．1 樹的概述 229

10．1．1 樹的術語 229

10．1．2 普通樹和二叉樹 230

10．1．3 樹的遞歸定義 231

10．2 用樹結構的原因 232

10．3 二叉樹的形狀 233

10．4 二叉樹的遍歷 235

10．4．1 前序遍歷 235

10．4．2 中序遍歷 236

10．4．3 後序遍歷 236

10．4．4 層次遍歷 237

10．5 二叉樹的3種常見套用 237

10．5．1 堆 237

10．5．2 二叉查找樹 238

10．5．3 表達式樹 239

10．6 開發二叉查找樹 240

10．6．1 二叉查找樹接口 240

10．6．2 連結實現的數據結構 242

10．6．3 二叉查找樹的複雜度分析 246

10．7 遞歸下降解析和程式語言 247

10．7．1 語法簡介 247

10．7．2 識別、解析和解釋語言裡的句子 249

10．7．3 詞法分析和掃描器 249

10．7．4 解析策略 249

10．8 案例研究：解析和表達式樹 250

10．8．1 案例需求 250

10．8．2 案例分析 250

10．8．3 節點類的設計與實現 251

10．8．4 解析器類的設計與實現 253

10．9 二叉樹的數組實現 254

10．10 堆的實現 255

10．11 章節總結 258

10．12 複習題 258

10．13 編程項目 259

第 11章 集合和字典 261

11．1 使用集合 261

11．2 Python的集合類 262

11．2．1 使用集合的互動示例 263

11．2．2 集合的套用 263

11．2．3 集合和包之間的關係 263

11．2．4 集合與字典之間的關係 263

11．2．5 集合的實現 264

11．3 集合的數組實現和連結實現 264

11．3．1 AbstractSet類 265

11．3．2 ArraySet類 266

11．4 使用字典 266

11．5 字典的數組實現和連結實現 267

11．5．1 Entry類 268

11．5．2 AbstractDict類 269

11．5．3 ArrayDict類 270

11．5．4 字典的數組實現和連結實現的複雜度分析 271

11．6 哈希策略 272

11．6．1 衝突與密度的關係 272

11．6．2 非數字鍵的哈希 273

11．6．3 線性探測法 275

11．6．4 二次探測法 276

11．6．5 鏈式法 277

11．6．6 複雜度分析 278

11．7 案例研究：分析哈希策略 279

11．7．1 案例需求 279

11．7．2 案例分析 279

11．7．3 案例設計 281

11．7．4 案例實現 281

11．8 集合的哈希實現 283

11．9 字典的哈希實現 285

11．10 有序集合和有序字典 287

11．11 章節總結 288

11．12 複習題 289

11．13 編程項目 290

第 12章 圖 292

12．1 使用圖的原因 292

12．2 圖的術語 293

12．3 圖的存儲方式 296

12．3．1 鄰接矩陣 296

12．3．2 鄰接表 297

12．3．3 兩種存儲方式的分析 298

12．3．4 對運行時的進一步思考 299

12．4 圖的遍歷 299

12．4．1 通用遍歷算法 300

12．4．2 廣度優先遍歷和深度優先遍歷 300

12．4．3 圖的組件 302

12．5 圖裡的樹 303

12．5．1 生成樹和生成森林 303

12．5．2 最小生成樹 303

12．5．3 最小生成樹的算法 304

12．6 拓撲排序 306

12．7 最短路徑問題 306

12．7．1 Dijkstra算法 307

12．7．2 初始化步驟 307

12．7．3 計算步驟 308

12．7．4 無窮大的表示和使用 309

12．7．5 分析 309

12．7．6 Floyd算法 310

12．7．7 分析 311

12．8 開發圖多項集 311

12．8．1 圖多項集的用法示例 311

12．8．2 LinkedDirectedGraph類 312

12．8．3 LinkedVertex類 316

12．8．4 LinkedEdge類 317

12．9 案例研究：測試圖算法 318

12．9．1 案例需求 318

12．9．2 案例分析 318

12．9．3 GraphDemoView類和GraphDemoModel類 319

12．9．4 案例實現（編碼） 320

12．10 章節總結 323

12．11 複習題 324

12．12 編程項目 325

作者簡介

肯尼思.A. 蘭伯特（Kenneth A. Lambert）是一名計算機科學教授，也是美國華盛頓與李大學（Washington and Lee University）計算機科學系的系主任。他教授“程式設計概論”課程已有 30 多年，並且一直是計算機科學教育領域的活躍研究者。Lambert 自行撰寫或與他人合著的書多達 28 本，包括一系列 Python 的入門圖書、與 Douglas Nance 和 Thomas Naps一起編寫的一系列 C++的入門圖書、與 Martin Osborne 一起編寫的一系列 Java 的入門圖書，等等。