數(shù)據(jù)結(jié)構(gòu)：Python語言描述（第2版）

第 1章 Python編程基礎(chǔ) 1
1．1 基本程序要素 1
1．1．1 程序和模塊 1
1．1．2 Python的示例程序：猜數(shù)字 2
1．1．3 編輯、編譯并運(yùn)行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 運(yùn)算符和表達(dá)式 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 可選和關(guān)鍵字函數(shù)參數(shù) 6
1．1．15 變量和賦值語句 7
1．1．16 Python的數(shù)據(jù)類型 7
1．1．17 import語句 7
1．1．18 獲取關(guān)于程序組件的幫助 8
1．2 控制語句 8
1．2．1 條件語句 9
1．2．2 使用if _name_ == _main_ 9
1．2．3 循環(huán)語句 10
1．3 字符串及其運(yùn)算 11
1．3．1 運(yùn)算符 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表達(dá)式創(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 多項集的實(shí)現(xiàn) 37
2．5 章節(jié)總結(jié) 38
2．6 復(fù)習(xí)題 39
2．7 編程項目 40
第3章 搜索、排序以及復(fù)雜度分析 41
3．1 衡量算法的效率 41
3．1．1 衡量算法的運(yùn)行時 42
3．1．2 統(tǒng)計指令數(shù) 43
3．1．3 衡量算法使用的內(nèi)存 45
3．2 復(fù)雜度分析 45
3．2．1 復(fù)雜度的階 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ù)復(fù)雜度的算法：遞歸斐波那契 63
3．7 案例研究：算法分析器 65
3．7．1 案例需求 65
3．7．2 案例分析 65
3．7．3 案例設(shè)計 66
3．7．4 案例實(shí)現(xiàn)（編碼） 67
3．8 章節(jié)總結(jié) 69
3．9 復(fù)習(xí)題 70
3．10 編程項目 71
第4章 數(shù)組和鏈接結(jié)構(gòu) 73
4．1 數(shù)組數(shù)據(jù)結(jié)構(gòu) 73
4．1．1 隨機(jī)訪問和連續(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 復(fù)雜度的權(quán)衡：時間、空間和數(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é)構(gòu) 84
4．4．1 單向鏈接結(jié)構(gòu)和雙向鏈接結(jié)構(gòu) 84
4．4．2 非連續(xù)內(nèi)存和節(jié)點(diǎn) 85
4．4．3 定義單向鏈接節(jié)點(diǎn)類 86
4．4．4 使用單向鏈接節(jié)點(diǎn)類 87
4．5 單向鏈接結(jié)構(gòu)上的操作 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 復(fù)雜度的權(quán)衡：時間、空間和單向鏈接結(jié)構(gòu) 96
4．6 鏈接上的變化 97
4．6．1 包含虛擬頭節(jié)點(diǎn)的環(huán)狀鏈接結(jié)構(gòu) 97
4．6．2 雙向鏈接結(jié)構(gòu) 98
4．7 章節(jié)總結(jié) 100
4．8 復(fù)習(xí)題 101
4．9 編程項目 102
第5章 接口、實(shí)現(xiàn)和多態(tài) 104
5．1 開發(fā)接口 104
5．1．1 設(shè)計包接口 105
5．1．2 指定參數(shù)和返回值 106
5．2 構(gòu)造函數(shù)和類的實(shí)現(xiàn) 107
5．2．1 前置條件、后置條件、異常和文檔 107
5．2．2 在Python里編寫接口 108
5．3 開發(fā)基于數(shù)組的實(shí)現(xiàn) 110
5．3．1 選擇并初始化數(shù)據(jù)結(jié)構(gòu) 110
5．3．2 先完成簡單的方法 111
5．3．3 完成迭代器 112
5．3．4 完成使用迭代器的方法 112
5．3．5 in運(yùn)算符和_contains_方法 113
5．3．6 完成remove方法 113
5．4 開發(fā)基于鏈接的實(shí)現(xiàn) 114
5．4．1 初始化數(shù)據(jù)結(jié)構(gòu) 115
5．4．2 完成迭代器 115
5．4．3 完成clear和add方法 115
5．4．4 完成remove方法 116
5．5 兩種包實(shí)現(xiàn)的運(yùn)行時性能 117
5．6 測試包的兩種實(shí)現(xiàn) 117
5．7 使用UML繪制包資源 118
5．8 章節(jié)總結(jié) 119
5．9 復(fù)習(xí)題 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的運(yùn)行時性能 126
6．1．7 Python里類的層次結(jié)構(gòu)的解釋 126
6．2 使用抽象類消除冗余代碼 127
6．2．1 設(shè)計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é)構(gòu)里 130
6．3．2 在_eq_方法里使用兩個迭代器 131
6．4 多項集的專家級框架 132
6．5 章節(jié)總結(jié) 134
6．6 復(fù)習(xí)題 134
6．7 編程項目 135
第7章 棧 137
7．1 棧的概述 137
7．2 使用棧 138
7．2．1 棧接口 138
7．2．2 棧的實(shí)例化 140
7．2．3 示例應(yīng)用程序：括號匹配 140
7．3 棧的3個應(yīng)用程序 142
7．3．1 算術(shù)表達(dá)式的求值 142
7．3．2 計算后綴表達(dá)式 143
7．3．3 把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式 144
7．3．4 回溯算法 146
7．3．5 內(nèi)存管理 148
7．4 棧的實(shí)現(xiàn) 150
7．4．1 測試驅(qū)動 150
7．4．2 將棧添加到多項集的層次結(jié)構(gòu) 151
7．4．3 棧的數(shù)組實(shí)現(xiàn) 152
7．4．4 棧的鏈接實(shí)現(xiàn) 153
7．4．5 抽象棧類的作用 155
7．4．6 兩種實(shí)現(xiàn)的時間和空間復(fù)雜度分析 156
7．5 案例研究：計算后綴表達(dá)式 157
7．5．1 案例需求 157
7．5．2 案例分析 157
7．5．3 案例設(shè)計 160
7．5．4 案例實(shí)現(xiàn) 163
7．6 章節(jié)總結(jié) 165
7．7 復(fù)習(xí)題 165
7．8 編程項目 166
第8章 隊列 168
8．1 隊列的概述 168
8．2 隊列接口及其使用 169
8．3 隊列的兩個應(yīng)用 171
8．3．1 計算機(jī)模擬 171
8．3．2 CPU的輪詢調(diào)度 173
8．4 隊列的實(shí)現(xiàn) 174
8．4．1 隊列的鏈接實(shí)現(xiàn) 174
8．4．2 隊列的數(shù)組實(shí)現(xiàn) 175
8．4．3 兩種實(shí)現(xiàn)的時間和空間復(fù)雜度分析 177
8．5 案例研究：超市收銀排隊的模擬 178
8．5．1 案例需求 178
8．5．2 案例分析 178
8．5．3 用戶交互接口 178
8．5．4 類和它們的職責(zé) 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 案例設(shè)計與實(shí)現(xiàn) 189
8．8 章節(jié)總結(jié) 191
8．9 復(fù)習(xí)題 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 列表的應(yīng)用 201
9．3．1 堆存儲管理 201
9．3．2 磁盤文件管理 202
9．3．3 其他多項集的實(shí)現(xiàn) 203
9．4 列表的實(shí)現(xiàn) 204
9．4．1 AbstractList類的作用 204
9．4．2 基于數(shù)組的實(shí)現(xiàn) 205
9．4．3 列表的鏈接實(shí)現(xiàn) 207
9．4．4 兩種實(shí)現(xiàn)的時間和空間復(fù)雜度分析 209
9．5 實(shí)現(xiàn)列表迭代器 211
9．5．1 列表迭代器的角色和職責(zé) 211
9．5．2 設(shè)置和實(shí)例化列表迭代器類 211
9．5．3 列表迭代器里的導(dǎo)航方法 212
9．5．4 列表迭代器里的變異器方法 213
9．5．5 設(shè)計鏈接列表的列表迭代器 215
9．5．6 列表迭代器實(shí)現(xiàn)的時間和空間復(fù)雜度分析 215
9．6 案例研究：開發(fā)有序列表 215
9．6．1 案例需求 215
9．6．2 案例分析 215
9．6．3 案例設(shè)計 216
9．6．4 案例實(shí)現(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é)構(gòu) 223
9．7．5 使用_repr_在IDLE里輸出類Lisp列表 224
9．7．6 列表和函數(shù)式編程 225
9．8 章節(jié)總結(jié) 225
9．9 復(fù)習(xí)題 226
9．10 編程項目 227
第 10章 樹 229
10．1 樹的概述 229
10．1．1 樹的術(shù)語 229
10．1．2 普通樹和二叉樹 230
10．1．3 樹的遞歸定義 231
10．2 用樹結(jié)構(gòu)的原因 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種常見應(yīng)用 237
10．5．1 堆 237
10．5．2 二叉查找樹 238
10．5．3 表達(dá)式樹 239
10．6 開發(fā)二叉查找樹 240
10．6．1 二叉查找樹接口 240
10．6．2 鏈接實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu) 242
10．6．3 二叉查找樹的復(fù)雜度分析 246
10．7 遞歸下降解析和編程語言 247
10．7．1 語法簡介 247
10．7．2 識別、解析和解釋語言里的句子 249
10．7．3 詞法分析和掃描器 249
10．7．4 解析策略 249
10．8 案例研究：解析和表達(dá)式樹 250
10．8．1 案例需求 250
10．8．2 案例分析 250
10．8．3 節(jié)點(diǎn)類的設(shè)計與實(shí)現(xiàn) 251
10．8．4 解析器類的設(shè)計與實(shí)現(xiàn) 253
10．9 二叉樹的數(shù)組實(shí)現(xiàn) 254
10．10 堆的實(shí)現(xiàn) 255
10．11 章節(jié)總結(jié) 258
10．12 復(fù)習(xí)題 258
10．13 編程項目 259
第 11章 集合和字典 261
11．1 使用集合 261
11．2 Python的集合類 262
11．2．1 使用集合的交互示例 263
11．2．2 集合的應(yīng)用 263
11．2．3 集合和包之間的關(guān)系 263
11．2．4 集合與字典之間的關(guān)系 263
11．2．5 集合的實(shí)現(xiàn) 264
11．3 集合的數(shù)組實(shí)現(xiàn)和鏈接實(shí)現(xiàn) 264
11．3．1 AbstractSet類 265
11．3．2 ArraySet類 266
11．4 使用字典 266
11．5 字典的數(shù)組實(shí)現(xiàn)和鏈接實(shí)現(xiàn) 267
11．5．1 Entry類 268
11．5．2 AbstractDict類 269
11．5．3 ArrayDict類 270
11．5．4 字典的數(shù)組實(shí)現(xiàn)和鏈接實(shí)現(xiàn)的復(fù)雜度分析 271
11．6 哈希策略 272
11．6．1 沖突與密度的關(guān)系 272
11．6．2 非數(shù)字鍵的哈希 273
11．6．3 線性探測法 275
11．6．4 二次探測法 276
11．6．5 鏈?zhǔn)椒?277
11．6．6 復(fù)雜度分析 278
11．7 案例研究：分析哈希策略 279
11．7．1 案例需求 279
11．7．2 案例分析 279
11．7．3 案例設(shè)計 281
11．7．4 案例實(shí)現(xiàn) 281
11．8 集合的哈希實(shí)現(xiàn) 283
11．9 字典的哈希實(shí)現(xiàn) 285
11．10 有序集合和有序字典 287
11．11 章節(jié)總結(jié) 288
11．12 復(fù)習(xí)題 289
11．13 編程項目 290
第 12章 圖 292
12．1 使用圖的原因 292
12．2 圖的術(shù)語 293
12．3 圖的存儲方式 296
12．3．1 鄰接矩陣 296
12．3．2 鄰接表 297
12．3．3 兩種存儲方式的分析 298
12．3．4 對運(yùn)行時的進(jìn)一步思考 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 拓?fù)渑判?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 案例實(shí)現(xiàn)（編碼） 320
12．10 章節(jié)總結(jié) 323
12．11 復(fù)習(xí)題 324
12．12 編程項目 325