《數據結構與算法：Python語言實現》是2019年11月機械工業出版社出版的圖書，作者是[美]麥可T.古德里奇（Michael T.Goodrich）、羅伯特·塔馬。
基本介紹
- 中文名：數據結構與算法：Python語言實現
- 作者：[美]麥可T.古德里奇（Michael T.Goodrich）、羅伯特·塔馬
- 出版社：機械工業出版社
- 出版時間：2019年11月
- 定價：109 元
- 開本：16 開
- 裝幀：平裝
- ISBN：9787111606604
內容簡介,圖書目錄,
內容簡介
本書採用Python語言介紹數據結構和算法，包括其設計、分析和實施。本書原始碼簡潔、明確，面向對象的觀點貫穿始終，通過繼承最大限度地提高代碼重用，同時彰顯不同抽象數據類型和算法之間的異同。
圖書目錄
出版者的話
譯者序
前言
致謝
作者簡介
第1章 Python入門 1
1.1 Python概述 1
1.1.1 Python解釋器 1
1.1.2 Python程式預覽 1
1.2 Python對象 2
1.2.1 標識符、對象和賦值語句 2
1.2.2 創建和使用對象 4
1.2.3 Python的內置類 4
1.3 表達式、運算符和優先權 8
1.4 控制流程 12
1.4.1 條件語句 12
1.4.2 循環語句 14
1.5 函式 16
1.5.1 信息傳遞 17
1.5.2 Python的內置函式 19
1.6 簡單的輸入和輸出 20
1.6.1 控制台輸入和輸出 21
1.6.2 檔案 21
1.7 異常處理 22
1.7.1 拋出異常 23
1.7.2 捕捉異常 24
1.8 疊代器和生成器 26
1.9 Python的其他便利特點 28
1.9.1 條件表達式 29
1.9.2 解析語法 29
1.9.3 序列類型的打包和解包 30
1.10 作用域和命名空間 31
1.11 模組和import語句 32
1.12 練習 34
擴展閱讀 36
第2章 面向對象編程 37
2.1 目標、原則和模式 37
2.1.1 面向對象的設計目標 37
2.1.2 面向對象的設計原則 38
2.1.3 設計模式 39
2.2 軟體開發 40
2.2.1 設計 40
2.2.2 偽代碼 41
2.2.3 編碼風格和文檔 42
2.2.4 測試和調試 43
2.3 類定義 44
2.3.1 例子：CreditCard類 45
2.3.2 運算符重載和Python的特殊方法 48
2.3.3 例子：多維向量類 50
2.3.4 疊代器 51
2.3.5 例子：Range類 52
2.4 繼承 53
2.4.1 擴展CreditCard類 54
2.4.2 數列的層次圖 57
2.4.3 抽象基類 60
2.5 命名空間和面向對象 62
2.5.1 實例和類命名空間 62
2.5.2 名稱解析和動態調度 65
2.6 深拷貝和淺拷貝 65
2.7 練習 67
擴展閱讀 70
第3章 算法分析 71
3.1 實驗研究 71
3.2 本書使用的7種函式 74
3.2.1 常數函式 74
3.2.2 對數函式 74
3.2.3 線性函式 75
3.2.4 n-log-n函式 75
3.2.5 二次函式 76
3.2.6 三次函式和其他多項式 77
3.2.7 指數函式 77
3.2.8 比較增長率 79
3.3 漸近分析 79
3.3.1 大O符號 80
3.3.2 比較分析 82
3.3.3 算法分析示例 84
3.4 簡單的證明技術 89
3.4.1 示例 89
3.4.2 反證法 89
3.4.3 歸納和循環不變數 90
3.5 練習 91
擴展閱讀 95
第4章 遞歸 96
4.1 說明性的例子 96
4.1.1 階乘函式 96
4.1.2 繪製英式標尺 97
4.1.3 二分查找 99
4.1.4 檔案系統 101
4.2 分析遞歸算法 104
4.3 遞歸算法的不足 106
4.4 遞歸的其他例子 109
4.4.1 線性遞歸 109
4.4.2 二路遞歸 112
4.4.3 多重遞歸 113
4.5 設計遞歸算法 114
4.6 消除尾遞歸 115
4.7 練習 116
擴展閱讀 118
第5章 基於數組的序列 119
5.1 Python序列類型 119
5.2 低層次數組 119
5.2.1 引用數組 121
5.2.2 Python中的緊湊數組 122
5.3 動態數組和攤銷 124
5.3.1 實現動態數組 126
5.3.2 動態數組的攤銷分析 127
5.3.3 Python列表類 130
5.4 Python序列類型的效率 130
5.4.1 Python的列表和元組類 130
5.4.2 Python的字元串類 134
5.5 使用基於數組的序列 136
5.5.1 為遊戲存儲高分 136
5.5.2 為序列排序 138
5.5.3 簡單密碼技術 140
5.6 多維數據集 142
5.7 練習 145
擴展閱讀 147
第6章 棧、佇列和雙端佇列 148
6.1 棧 148
6.1.1 棧的抽象數據類型 148
6.1.2 簡單的基於數組的棧實現 149
6.1.3 使用棧實現數據的逆置 152
6.1.4 括弧和HTML標記匹配 152
6.2 佇列 155
6.2.1 佇列的抽象數據類型 155
6.2.2 基於數組的佇列實現 156
6.3 雙端佇列 160
6.3.1 雙端佇列的抽象數據類型 160
6.3.2 使用環形數組實現雙端佇列 161
6.3.3 Python collections模組中的雙端佇列 162
6.4 練習 163
擴展閱讀 165
第7章 鍊表 166
7.1 單向鍊表 166
7.1.1 用單向鍊表實現棧 169
7.1.2 用單向鍊表實現佇列 171
7.2 循環鍊表 173
7.2.1 輪轉調度 173
7.2.2 用循環鍊表實現佇列 174
7.3 雙向鍊表 175
7.3.1 雙向鍊表的基本實現 177
7.3.2 用雙向鍊表實現雙端佇列 179
7.4 位置列表的抽象數據類型 180
7.4.1 含位置信息的列表抽象數據類型 182
7.4.2 雙向鍊表實現 183
7.5 位置列表的排序 186
7.6 案例研究：維護訪問頻率 186
7.6.1 使用有序表 187
7.6.2 啟發式動態調整列表 188
7.7 基於連結的序列與基於數組的序列 190
7.8 練習 192
擴展閱讀 195
第8章 樹 196
8.1 樹的基本概念 196
8.1.1 樹的定義和屬性 196
8.1.2 樹的抽象數據類型 199
8.1.3 計算深度和高度 201
8.2 二叉樹 203
8.2.1 二叉樹的抽象數據類型 204
8.2.2 二叉樹的屬性 206
8.3 樹的實現 207
8.3.1 二叉樹的鏈式存儲結構 207
8.3.2 基於數組表示的二叉樹 212
8.3.3 一般樹的鏈式存儲結構 214
8.4 樹的遍歷算法 214
8.4.1 樹的先序和後序遍歷 214
8.4.2 樹的廣度優先遍歷 216
8.4.3 二叉樹的中序遍歷 216
8.4.4 用Python實現樹遍歷 217
8.4.5 樹遍歷的套用 220
8.4.6 歐拉圖和模板方法模式* 223
8.5 案例研究：表達式樹 227
8.6 練習 230
擴展閱讀 235
第9章 優先權佇列 236
9.1 優先權佇列的抽象數據類型 236
9.1.1 優先權 236
9.1.2 優先權佇列的抽象數據類型的實現 236
9.2 優先權佇列的實現 237
9.2.1 組合設計模式 237
9.2.2 使用未排序列表實現優先權佇列 238
9.2.3 使用排序列表實現優先權佇列 239
9.3 堆 241
9.3.1 堆的數據結構 241
9.3.2 使用堆實現優先權佇列 242
9.3.3 基於數組的完全二叉樹表示 244
9.3.4 Python的堆實現 246
9.3.5 基於堆的優先權佇列的分析 248
9.3.6 自底向上構建堆* 248
9.3.7 Python的heapq模組 251
9.4 使用優先權佇列排序 252
9.4.1 選擇排序和插入排序 253
9.4.2 堆排序 254
9.5 適應性優先權佇列 255
9.5.1 定位器 256
9.5.2 適應性優先權佇列的實現 256
9.6 練習 259
擴展閱讀 263
第10章 映射、哈希表和跳躍表 264
10.1 映射和字典 264
10.1.1 映射的抽象數據類型 264
10.1.2 套用：單詞頻率統計 266
10.1.3 Python的MutableMapping抽象基類 267
10.1.4 我們的MapBase類 267
10.1.5 簡單的非有序映射實現 268
10.2 哈希表 269
10.2.1 哈希函式 270
10.2.2 哈希碼 271
10.2.3 壓縮函式 274
10.2.4 衝突處理方案 274
10.2.5 負載因子、重新哈希和效率 276
10.2.6 Python哈希表的實現 278
10.3 有序映射 281
10.3.1 排序檢索表 282
10.3.2 有序映射的兩種套用 286
10.4 跳躍表 288
10.4.1 跳躍表中的查找和更新操作 289
10.4.2 跳躍表的機率分析* 292
10.5 集合、多集和多映射 294
10.5.1 集合的抽象數據類型 294
10.5.2 Python的MutableSet抽象基類 295
10.5.3 集合、多集和多映射的實現 297
10.6 練習 298
擴展閱讀 302
第11章 搜尋樹 303
11.1 二叉搜尋樹 303
11.1.1 遍歷二叉搜尋樹 303
11.1.2 搜尋 305
11.1.3 插入和刪除 306
11.1.4 Python實現 307
11.1.5 二叉搜尋樹的性能 311
11.2 平衡搜尋樹 312
11.3 AVL樹 316
11.3.1 更新操作 318
11.3.2 Python實現 320
11.4 伸展樹 322
11.4.1 伸展 322
11.4.2 何時進行伸展 323
11.4.3 Python實現 324
11.4.4 伸展樹的攤銷分析* 325
11.5 （2，4）樹 328
11.5.1 多路搜尋樹 328
11.5.2 （2，4）樹的操作 330
11.6 紅黑樹 334
11.6.1 紅黑樹的操作 335
11.6.2 Python實現 341
11.7 練習 343
擴展閱讀 348
第12章 排序與選擇 349
12.1 為什麼要學習排序算法 349
12.2 歸併排序 349
12.2.1 分治法 349
12.2.2 基於數組的歸併排序的實現 351
12.2.3 歸併排序的運行時間 353
12.2.4 歸併排序與遞歸方程* 354
12.2.5 歸併排序的可選實現 355
12.3 快速排序 357
12.3.1 隨機快速排序 361
12.3.2 快速排序的額外最佳化 362
12.4 再論排序：算法視角 364
12.4.1 排序下界 365
12.4.2 線性時間排序：桶排序和基數排序 366
12.5 排序算法的比較 367
12.6 Python的內置排序函式 369
12.7 選擇 370
12.7.1 剪枝搜尋 370
12.7.2 隨機快速選擇 371
12.7.3 隨機快速選擇分析 371
12.8 練習 372
擴展閱讀 376
第13章 文本處理 377
13.1 數位化文本的多樣性 377
13.2 模式匹配算法 378
13.2.1 窮舉 378
13.2.2 Boyer-Moore算法 379
13.2.3 Knuth-Morris-Pratt算法 382
13.3 動態規劃 385
13.3.1 矩陣鏈乘積 385
13.3.2 DNA和文本序列比對 386
13.4 文本壓縮和貪心算法 389
13.4.1 霍夫曼編碼算法 390
13.4.2 貪心算法 391
13.5 字典樹 391
13.5.1 標準字典樹 391
13.5.2 壓縮字典樹 394
13.5.3 後綴字典樹 395
13.5.4 搜尋引擎索引 396
13.6 練習 397
拓展閱讀 400
第14章 圖算法 401
14.1 圖 401
14.2 圖的數據結構 405
14.2.1 邊列表結構 406
14.2.2 鄰接列表結構 407
14.2.3 鄰接圖結構 408
14.2.4 鄰接矩陣結構 409
14.2.5 Python實現 409
14.3 圖遍歷 412
14.3.1 深度優先搜尋 413
14.3.2 深度優先搜尋的實現和擴展 416
14.3.3 廣度優先搜尋 419
14.4 傳遞閉包 421
14.5 有向非循環圖 424
14.6 最短路徑 426
14.6.1 加權圖 427
14.6.2 Dijkstra算法 428
14.7 最小生成樹 434
14.7.1 Prim-Jarník算法 435
14.7.2 Kruskal算法 438
14.7.3 不相交分區和聯合查找結構 442
14.8 練習 445
擴展閱讀 451
第15章 記憶體管理和B樹 452
15.1 記憶體管理 452
15.1.1 記憶體分配 452
15.1.2 垃圾回收 453
15.1.3 Python解釋器使用的額外記憶體 455
15.2 存儲器層次結構和快取 456
15.2.1 存儲器系統 456
15.2.2 高速快取策略 456
15.3 外部搜尋和B樹 460
15.3.1 （a，b）樹 460
15.3.2 B樹 462
15.4 外部存儲器中的排序 462
15.5 練習 464
拓展閱讀 465
附錄A Python中的字元串 466
附錄B 有用的數學定理 469
參考文獻 474
