數(shù)據(jù)結(jié)構 Python語言描述 第2版
定 價：119.9 元
- 作者：[美]肯尼思· A.蘭伯特（Kenneth A. Lambert ）
- 出版時間：2021/7/1
- ISBN：9787115551481
- 出 版 社：人民郵電出版社
- 中圖法分類：TP311.12
- 頁碼：326
- 紙張：
- 版次：02
- 開本：16開
本書用 Python 語言來講解數(shù)據(jù)結(jié)構及實現(xiàn)方法。全書首先概述 Python 編程的功能—這些功能是實際編程和解決問題時所必需的；其次介紹抽象數(shù)據(jù)類型的規(guī)范、實現(xiàn)和應用，多項集類型，以及接口和實現(xiàn)之間的重要差異；隨后介紹線性多項集、棧、隊列和列表；最后介紹樹、圖等內(nèi)容。本書附有大量的復習題和編程項目，旨在幫助讀者鞏固所學知識。
本書不僅適合高等院校計算機專業(yè)師生閱讀，也適合對 Python 感興趣的讀者和程序員閱讀。
1.美國華盛頓與李大學（Washington and Lee University）計算機科學系肯尼思·A. 蘭伯特（Kenneth A. Lambert）教授的全新力作。
2.國外著名高等院校信息科學與技術優(yōu)秀教材升級版。
3.采用Python語言循序漸進的講解數(shù)據(jù)結(jié)構及實現(xiàn)方法，內(nèi)容全面，包括編程基礎、面向?qū)ο缶幊�、�?shù)據(jù)結(jié)構以及軟件開發(fā)生命周期。
4.書中包含大量實戰(zhàn)案例研究，復習題和編程項目，幫助讀者鞏固所學知識。
3.異步社區(qū)為讀者提供本書的配套資源下載服務。
肯尼思·A. 蘭伯特（Kenneth A. Lambert）是一名計算機科學教授，也是美國華盛頓與李大學（Washington and Lee University）計算機科學系的系主任。他教授“程序設計概論”課程已有 30 多年，并且一直是計算機科學教育領域的活躍研究者。Lambert 自行撰寫或與他人合著的書多達 28 本，包括一系列 Python 的入門圖書、與 Douglas Nance 和 Thomas Naps一起編寫的一系列 C++的入門圖書、與 Martin Osborne 一起編寫的一系列 Java 的入門圖書，等等。
第 1章 Python編程基礎 1
1.1 基本程序要素 1
1.1.1 程序和模塊 1
1.1.2 Python的示例程序：猜數(shù)字 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 函數(shù)調(diào)用 5
1.1.11 print函數(shù) 6
1.1.12 input函數(shù) 6
1.1.13 類型轉(zhuǎn)換函數(shù)和混合模式操作 6
1.1.14 可選和關鍵字函數(shù)參數(shù) 6
1.1.15 變量和賦值語句 7
1.1.16 Python的數(shù)據(jù)類型 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 循環(huán)語句 10
1.3 字符串及其運算 11
1.3.1 運算符 11
1.3.2 格式化字符串以便輸出 12
1.3.3 對象和方法調(diào)用 13
1.4 Python內(nèi)置的多項集及其操作 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 創(chuàng)建新函數(shù) 17
1.5.1 函數(shù)定義 17
1.5.2 遞歸函數(shù) 18
1.5.3 函數(shù)的嵌套定義 19
1.5.4 高階函數(shù) 20
1.5.5 使用lambda表達式創(chuàng)建匿名函數(shù) 21
1.6 捕獲異常 21
1.7 文件及其操作 22
1.7.1 文本文件的輸出 23
1.7.2 將數(shù)字寫入文本文件 23
1.7.3 從文本文件讀取文本 24
1.7.4 從文件讀取數(shù)據(jù) 25
1.7.5 使用pickle讀寫對象 26
1.8 創(chuàng)建新類 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 類型轉(zhuǎn)換 36
2.2.3 克隆和相等性 36
2.3 迭代器和高階函數(shù) 37
2.4 多項集的實現(xiàn) 37
2.5 章節(jié)總結(jié) 38
2.6 復習題 39
2.7 編程項目 40
第3章 搜索、排序以及復雜度分析 41
3.1 衡量算法的效率 41
3.1.1 衡量算法的運行時 42
3.1.2 統(tǒng)計指令數(shù) 43
3.1.3 衡量算法使用的內(nèi)存 45
3.2 復雜度分析 45
3.2.1 復雜度的階 45
3.2.2 大O表示法 47
3.2.3 比例常數(shù)的作用 47
3.3 搜索算法 48
3.3.1 最小值搜索 48
3.3.2 順序搜索列表 49
3.3.3 最好情況、最壞情況以及平均情況下的性能 49
3.3.4 基于有序列表的二分搜索 50
3.3.5 比較數(shù)據(jù)元素 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 指數(shù)復雜度的算法：遞歸斐波那契 63
3.7 案例研究：算法分析器 65
3.7.1 案例需求 65
3.7.2 案例分析 65
3.7.3 案例設計 66
3.7.4 案例實現(xiàn)（編碼） 67
3.8 章節(jié)總結(jié) 69
3.9 復習題 70
3.10 編程項目 71
第4章 數(shù)組和鏈接結(jié)構 73
4.1 數(shù)組數(shù)據(jù)結(jié)構 73
4.1.1 隨機訪問和連續(xù)內(nèi)存 75
4.1.2 靜態(tài)內(nèi)存和動態(tài)內(nèi)存 76
4.1.3 物理尺寸和邏輯尺寸 76
4.2 數(shù)組的操作 77
4.2.1 增大數(shù)組的尺寸 77
4.2.2 減小數(shù)組的尺寸 78
4.2.3 將元素插入增大的數(shù)組 78
4.2.4 從數(shù)組里刪除元素 79
4.2.5 復雜度的權衡：時間、空間和數(shù)組 80
4.3 二維數(shù)組（網(wǎng)格） 81
4.3.1 使用網(wǎng)格 81
4.3.2 創(chuàng)建并初始化網(wǎng)格 82
4.3.3 定義Grid類 82
4.3.4 參差不齊的網(wǎng)格和多維數(shù)組 83
4.4 鏈接結(jié)構 84
4.4.1 單向鏈接結(jié)構和雙向鏈接結(jié)構 84
4.4.2 非連續(xù)內(nèi)存和節(jié)點 85
4.4.3 定義單向鏈接節(jié)點類 86
4.4.4 使用單向鏈接節(jié)點類 87
4.5 單向鏈接結(jié)構上的操作 88
4.5.1 遍歷 88
4.5.2 搜索 89
4.5.3 替換 90
4.5.4 在開始處插入 90
4.5.5 在結(jié)尾處插入 91
4.5.6 在開始處刪除 92
4.5.7 在結(jié)尾處刪除 93
4.5.8 在任意位置處插入 94
4.5.9 在任意位置處刪除 95
4.5.10 復雜度的權衡：時間、空間和單向鏈接結(jié)構 96
4.6 鏈接上的變化 97
4.6.1 包含虛擬頭節(jié)點的環(huán)狀鏈接結(jié)構 97
4.6.2 雙向鏈接結(jié)構 98
4.7 章節(jié)總結(jié) 100
4.8 復習題 101
4.9 編程項目 102
第5章 接口、實現(xiàn)和多態(tài) 104
5.1 開發(fā)接口 104
5.1.1 設計包接口 105
5.1.2 指定參數(shù)和返回值 106
5.2 構造函數(shù)和類的實現(xiàn) 107
5.2.1 前置條件、后置條件、異常和文檔 107
5.2.2 在Python里編寫接口 108
5.3 開發(fā)基于數(shù)組的實現(xiàn) 110
5.3.1 選擇并初始化數(shù)據(jù)結(jié)構 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 開發(fā)基于鏈接的實現(xiàn) 114
5.4.1 初始化數(shù)據(jù)結(jié)構 115
5.4.2 完成迭代器 115
5.4.3 完成clear和add方法 115
5.4.4 完成remove方法 116
5.5 兩種包實現(xiàn)的運行時性能 117
5.6 測試包的兩種實現(xiàn) 117
5.7 使用UML繪制包資源 118
5.8 章節(jié)總結(jié) 119
5.9 復習題 120
5.10 編程項目 120
第6章 繼承與抽象類 122
6.1 使用繼承定制已經(jīng)存在的類 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里類的層次結(jié)構的解釋 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添加到多項集的層次結(jié)構里 130
6.3.2 在_eq_方法里使用兩個迭代器 131
6.4 多項集的專家級框架 132
6.5 章節(jié)總結(jié) 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 把中綴表達式轉(zhuǎn)換為后綴表達式 144
7.3.4 回溯算法 146
7.3.5 內(nèi)存管理 148
7.4 棧的實現(xiàn) 150
7.4.1 測試驅(qū)動 150
7.4.2 將棧添加到多項集的層次結(jié)構 151
7.4.3 棧的數(shù)組實現(xiàn) 152
7.4.4 棧的鏈接實現(xiàn) 153
7.4.5 抽象棧類的作用 155
7.4.6 兩種實現(xiàn)的時間和空間復雜度分析 156
7.5 案例研究：計算后綴表達式 157
7.5.1 案例需求 157
7.5.2 案例分析 157
7.5.3 案例設計 160
7.5.4 案例實現(xiàn) 163
7.6 章節(jié)總結(jié) 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的輪詢調(diào)度 173
8.4 隊列的實現(xiàn) 174
8.4.1 隊列的鏈接實現(xiàn) 174
8.4.2 隊列的數(shù)組實現(xiàn) 175
8.4.3 兩種實現(xiàn)的時間和空間復雜度分析 177
8.5 案例研究：超市收銀排隊的模擬 178
8.5.1 案例需求 178
8.5.2 案例分析 178
8.5.3 用戶交互接口 178
8.5.4 類和它們的職責 179
8.6 優(yōu)先隊列 184
8.7 案例研究：急診室調(diào)度程序 188
8.7.1 案例需求 188
8.7.2 案例分析 188
8.7.3 類 189
8.7.4 案例設計與實現(xiàn) 189
8.8 章節(jié)總結(jié) 191
8.9 復習題 192
8.10 編程項目 193
第9章 列表 194
9.1 列表的概述 194
9.2 使用列表 195
9.2.1 基于索引的操作 196
9.2.2 基于內(nèi)容的操作 196
9.2.3 基于位置的操作 196
9.2.4 列表接口 200
9.3 列表的應用 201
9.3.1 堆存儲管理 201
9.3.2 磁盤文件管理 202
9.3.3 其他多項集的實現(xiàn) 203
9.4 列表的實現(xiàn) 204
9.4.1 AbstractList類的作用 204
9.4.2 基于數(shù)組的實現(xiàn) 205
9.4.3 列表的鏈接實現(xiàn) 207
9.4.4 兩種實現(xiàn)的時間和空間復雜度分析 209
9.5 實現(xiàn)列表迭代器 211
9.5.1 列表迭代器的角色和職責 211
9.5.2 設置和實例化列表迭代器類 211
9.5.3 列表迭代器里的導航方法 212
9.5.4 列表迭代器里的變異器方法 213
9.5.5 設計鏈接列表的列表迭代器 215
9.5.6 列表迭代器實現(xiàn)的時間和空間復雜度分析 215
9.6 案例研究：開發(fā)有序列表 215
9.6.1 案例需求 215
9.6.2 案例分析 215
9.6.3 案例設計 216
9.6.4 案例實現(xiàn)（編碼） 218
9.7 遞歸列表的處理 219
9.7.1 類Lisp列表的基本操作 220
9.7.2 類Lisp列表的遞歸遍歷 221
9.7.3 創(chuàng)建類Lisp列表 222
9.7.4 類Lisp列表的內(nèi)部結(jié)構 223
9.7.5 使用_repr_在IDLE里輸出類Lisp列表 224
9.7.6 列表和函數(shù)式編程 225
9.8 章節(jié)總結(jié) 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 用樹結(jié)構的原因 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 開發(fā)二叉查找樹 240
10.6.1 二叉查找樹接口 240
10.6.2 鏈接實現(xiàn)的數(shù)據(jù)結(jié)構 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 節(jié)點類的設計與實現(xiàn) 251
10.8.4 解析器類的設計與實現(xiàn) 253
10.9 二叉樹的數(shù)組實現(xiàn) 254
10.10 堆的實現(xiàn) 255
10.11 章節(jié)總結(jié) 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 集合的實現(xiàn) 264
11.3 集合的數(shù)組實現(xiàn)和鏈接實現(xiàn) 264
11.3.1 AbstractSet類 265
11.3.2 ArraySet類 266
11.4 使用字典 266
11.5 字典的數(shù)組實現(xiàn)和鏈接實現(xiàn) 267
11.5.1 Entry類 268
11.5.2 AbstractDict類 269
11.5.3 ArrayDict類 270
11.5.4 字典的數(shù)組實現(xiàn)和鏈接實現(xiàn)的復雜度分析 271
11.6 哈希策略 272
11.6.1 沖突與密度的關系 272
11.6.2 非數(shù)字鍵的哈希 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 案例實現(xiàn) 281
11.8 集合的哈希實現(xiàn) 283
11.9 字典的哈希實現(xiàn) 285
11.10 有序集合和有序字典 287
11.11 章節(jié)總結(jié) 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 廣度優(yōu)先遍歷和深度優(yōu)先遍歷 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 開發(fā)圖多項集 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 案例實現(xiàn)（編碼） 320
12.10 章節(jié)總結(jié) 323
12.11 復習題 324
12.12 編程項目 325
書單推薦
