數(shù)據(jù)結(jié)構(gòu)：Python語(yǔ)言描述

第1章 Python編程基礎(chǔ)\t1
1．1 基本程序要素\t1
1．1．1 程序和模塊\t1
1．1．2 Python程序示例：猜數(shù)字\t1
1．1．3 編輯、編譯并運(yùn)行
Python程序\t2
1．1．4 程序注釋\t3
1．1．5 詞法元素\t3
1．1．6 拼寫和命名慣例\t3
1．1．7 語(yǔ)法元素\t4
1．1．8 字面值\t4
1．1．9 字符串字面值\t4
1．1．10 運(yùn)算符和表達(dá)式\t5
1．1．11 函數(shù)調(diào)用\t5
1．1．12 print函數(shù)\t5
1．1．13 input函數(shù)\t5
1．1．14 類型轉(zhuǎn)換函數(shù)和
混合模式運(yùn)算\t6
1．1．15 可選的和關(guān)鍵字
函數(shù)參數(shù)\t6
1．1．16 變量和賦值語(yǔ)句\t6
1．1．17 Python數(shù)據(jù)類型\t7
1．1．18 import語(yǔ)句\t7
1．1．19 獲取關(guān)于程序組件
的幫助\t7
1．2 控制語(yǔ)句\t8
1．2．1 條件式語(yǔ)句\t8
1．2．2 使用if __name__ ==
__main__\t9
1．2．3 循環(huán)語(yǔ)句\t10
1．3 字符串及其運(yùn)算\t10
1．3．1 運(yùn)算符\t10
1．3．2 格式化字符串以便輸出\t11
1．3．3 對(duì)象和方法調(diào)用\t13
1．4 內(nèi)建Python集合及其操作\t13
1．4．1 列表\t14
1．4．2 元組\t14
1．4．3 遍歷序列\(zhòng)t14
1．4．4 字典\t15
1．4．5 搜索一個(gè)值\t15
1．4．6 對(duì)集合應(yīng)用模式匹配\t15
1．5 編寫新的函數(shù)\t16
1．5．1 函數(shù)定義\t16
1．5．2 遞歸函數(shù)\t17
1．5．3 嵌套的函數(shù)定義\t19
1．5．4 高階函數(shù)\t19
1．5．5 使用lambda表達(dá)式
創(chuàng)建匿名函數(shù)\t20
1．6 捕獲異常\t20
1．7 文件及其操作\t21
1．7．1 文本文件的輸出\t22
1．7．2 將數(shù)字寫入到一個(gè)
文本文件\t22
1．7．3 從文本文件讀取文本\t23
1．7．4 從文件讀取數(shù)字\t24
1．7．5 使用pickle讀寫對(duì)象\t24
1．8 創(chuàng)建新的類\t25
1．9 編程項(xiàng)目\t28
第2章 集合概覽\t30
2．1 集合類型\t30
2．1．1 線性集合\t30
2．1．2 層級(jí)集合\t31
2．1．3 圖集合\t31
2．1．4 無序集合\t31
2．1．5 有序集合\t31
2．1．6 集合類型的分類\t32
2．2 集合上的操作\t32
2．3 集合的實(shí)現(xiàn)\t34
2．4 小結(jié)\t35
2．5 復(fù)習(xí)題\t35
2．6 編程項(xiàng)目\t36
第3章 搜索、排序和復(fù)雜度分析\t37
3．1 評(píng)估算法的性能\t37
3．1．1 度量算法的運(yùn)行時(shí)間\t37
3．1．2 統(tǒng)計(jì)指令\t39
3．1．3 度量算法所使用的內(nèi)存\t41
3．1．4 練習(xí)3．1\t41
3．2 復(fù)雜度分析\t41
3．2．1 復(fù)雜度的階\t41
3．2．2 大O表示法\t43
3．2．3 常量比例的作用\t43
3．2．4 練習(xí)3．2\t43
3．3 搜索算法\t44
3．3．1 搜索最小值\t44
3．3．2 順序搜索一個(gè)列表\t44
3．3．3 最好情況、最壞情況和
平均情況的性能\t45
3．3．4 有序列表的二叉搜索\t45
3．3．5 比較數(shù)據(jù)項(xiàng)\t47
3．3．6 練習(xí)3．3\t48
3．4 基本排序算法\t48
3．4．1 選擇排序\t48
3．4．2 冒泡排序\t49
3．4．3 插入排序\t50
3．4．4 再談最好情況、最壞情
況和平均情況的性能\t52
3．4．5 練習(xí)3．4\t52
3．5 更快的排序\t53
3．5．1 快速排序簡(jiǎn)介\t53
3．5．2 合并排序\t56
3．5．3 練習(xí)3．5\t59
3．6 指數(shù)算法：遞歸式的
Fibonacci\t59
3．7 案例學(xué)習(xí)：算法探查器\t61
3．7．1 需求\t61
3．7．2 分析\t61
3．7．3 設(shè)計(jì)\t62
3．7．4 實(shí)現(xiàn)（編寫代碼）\t63
3．8 小結(jié)\t65
3．9 復(fù)習(xí)題\t66
3．10 編程項(xiàng)目\t67
第4章 數(shù)組和鏈表結(jié)構(gòu)\t69
4．1 數(shù)組數(shù)據(jù)結(jié)構(gòu)\t69
4．1．1 隨機(jī)訪問和連續(xù)內(nèi)存\t71
4．1．2 靜態(tài)內(nèi)存和動(dòng)態(tài)內(nèi)存\t72
4．1．3 物理大小和邏輯大小\t72
4．1．4 練習(xí)4．1\t73
4．2 數(shù)組的操作\t73
4．2．1 增加數(shù)組的大小\t73
4．2．2 減小數(shù)組的大小\t74
4．2．3 在數(shù)組中插入一項(xiàng)\t74
4．2．4 從數(shù)組中刪除一項(xiàng)\t75
4．2．5 復(fù)雜度權(quán)衡：時(shí)間、
空間和數(shù)組\t76
4．2．6 練習(xí)4．2\t76
4．3 二維數(shù)組\t77
4．3．1 處理網(wǎng)格\t77
4．3．2 創(chuàng)建并初始化網(wǎng)格\t77
4．3．3 定義Grid類\t78
4．3．4 雜亂的網(wǎng)格和多維數(shù)組\t79
4．3．5 練習(xí)4．3\t79
4．4 鏈表結(jié)構(gòu)\t80
4．4．1 單鏈表結(jié)構(gòu)和雙鏈表
結(jié)構(gòu)\t80
4．4．2 非連續(xù)性內(nèi)存和節(jié)點(diǎn)\t81
4．4．3 定義一個(gè)單鏈表節(jié)點(diǎn)類\t82
4．4．4 使用單鏈表節(jié)點(diǎn)類\t82
4．4．5 練習(xí)4．4\t84
4．5 單鏈表結(jié)構(gòu)上的操作\t84
4．5．1 遍歷\t84
4．5．2 搜索\t85
4．5．3 替換\t86
4．5．4 在開始處插入\t86
4．5．5 在末尾插入\t87
4．5．6 從開始處刪除\t87
4．5．7 從末尾刪除\t88
4．5．8 在任何位置插入\t89
4．5．9 從任意位置刪除\t90
4．5．10 復(fù)雜度權(quán)衡：時(shí)間、
空間和單鏈表結(jié)構(gòu)\t91
4．5．11 練習(xí)4．5\t92
4．6 鏈表的變體\t92
4．6．1 帶有一個(gè)啞頭節(jié)點(diǎn)
的循環(huán)鏈表結(jié)構(gòu)\t92
4．6．2 雙鏈表結(jié)構(gòu)\t93
4．6．3 練習(xí)4．6\t95
4．7 小結(jié)\t95
4．8 復(fù)習(xí)題\t96
4．9 編程項(xiàng)目\t96
第5章 接口、實(shí)現(xiàn)和多態(tài)\t98
5．1 開發(fā)接口\t98
5．1．1 定義包接口\t98
5．1．2 指定參數(shù)和返回值\t99
5．1．3 構(gòu)造方法和實(shí)現(xiàn)類\t101
5．1．4 先驗(yàn)條件、后驗(yàn)條件、
異常和文檔\t101
5．1．5 用Python編寫接口\t102
5．1．6 練習(xí)5．1\t103
5．2 開發(fā)一個(gè)基于數(shù)組的實(shí)現(xiàn)\t103
5．2．1 選擇并初始化數(shù)據(jù)
結(jié)構(gòu)\t103
5．2．2 先完成容易的方法\t104
5．2．3 完成迭代器\t105
5．2．4 完成使用迭代器
的方法\t106
5．2．5 in運(yùn)算符和__contains__
方法\t106
5．2．6 完成remove方法\t107
5．2．7 練習(xí)5．2\t107
5．3 開發(fā)一個(gè)基于鏈表的實(shí)現(xiàn)\t107
5．3．1 初始化數(shù)據(jù)結(jié)構(gòu)\t108
5．3．2 完成迭代器\t109
5．3．3 完成clear和add方法\t109
5．3．4 完成remove方法\t109
5．3．5 練習(xí)5．3\t110
5．4 兩個(gè)包實(shí)現(xiàn)的運(yùn)行時(shí)性能\t110
5．5 測(cè)試兩個(gè)包實(shí)現(xiàn)\t111
5．6 用UML圖表示包資源\t112
5．7 小結(jié)\t113
5．8 復(fù)習(xí)題\t113
5．9 編程項(xiàng)目\t114
第6章 繼承和抽象類\t115
6．1 使用繼承定制一個(gè)已有的類\t115
6．1．1 已有類的子類化\t115
6．1．2 再談__init__方法\t116
6．1．3 添加新的contains方法\t117
6．1．4 修改已有的add方法\t117
6．1．5 ArraySortedBag的運(yùn)行
時(shí)間性能\t118
6．1．6 Python中的類層級(jí)\t118
6．1．7 練習(xí)6．1\t119
6．2 使用抽象類去除代碼冗余性\t119
6．2．1 設(shè)計(jì)一個(gè)
AbstractBag類\t119
6．2．2 重新編寫AbstractBag
中的__init__方法\t120
6．2．3 修改AbstractBag
的子類\t120
6．2．4 將AbstractBag中的
__add__方法泛化\t121
6．3 所有集合的一個(gè)抽象類\t122
6．3．1 將AbstractCollection
整合到集合層級(jí)中\(zhòng)t122
6．3．2 在__eq__方法中使用
兩個(gè)迭代器\t123
6．3．3 練習(xí)6．2\t124
6．4 小結(jié)\t124
6．5 復(fù)習(xí)題\t124
6．6 編程項(xiàng)目\t125
第7章 棧\t127
7．1 棧概覽\t127
7．2 使用棧\t128
7．2．1 棧接口\t128
7．2．2 初始化一個(gè)棧\t129
7．2．3 示例應(yīng)用程序：
匹配括號(hào)\t129
7．2．4 練習(xí)7．1\t131
7．3 棧的3種應(yīng)用\t131
7．3．1 計(jì)算算術(shù)表達(dá)式\t131
7．3．2 計(jì)算后綴表達(dá)式\t132
7．3．3 練習(xí)7．2\t133
7．3．4 將中綴表達(dá)式轉(zhuǎn)換為
后綴表達(dá)式\t133
7．3．5 練習(xí)7．3\t135
7．3．6 回溯算法\t135
7．3．7 內(nèi)存管理\t137
7．4 棧的實(shí)現(xiàn)\t138
7．4．1 測(cè)試驅(qū)動(dòng)程序\t138
7．4．2 將棧添加到集合層級(jí)中\(zhòng)t139
7．4．3 數(shù)組實(shí)現(xiàn)\t140
7．4．4 鏈表實(shí)現(xiàn)\t141
7．4．5 AbstractStack類的
作用\t144
7．4．6 兩種實(shí)現(xiàn)的時(shí)間和
空間分析\t144
7．4．7 練習(xí)7．4\t145
7．5 案例學(xué)習(xí)：計(jì)算后綴表達(dá)式\t145
7．5．1 要求\t145
7．5．2 分析\t145
7．5．3 設(shè)計(jì)\t148
7．5．4 實(shí)現(xiàn)\t150
7．6 小結(jié)\t153
7．7 復(fù)習(xí)題\t153
7．8 編程項(xiàng)目\t154
第8章 隊(duì)列\(zhòng)t156
8．1 隊(duì)列概覽\t156
8．2 隊(duì)列接口及其應(yīng)用\t157
練習(xí)8．1\t158
8．3 隊(duì)列的兩個(gè)應(yīng)用\t159
8．3．1 模擬\t159
8．3．2 輪詢CPU調(diào)度\t161
8．3．3 練習(xí)8．2\t161
8．4 隊(duì)列的實(shí)現(xiàn)\t161
8．4．1 隊(duì)列的鏈表實(shí)現(xiàn)\t161
8．4．2 數(shù)組實(shí)現(xiàn)\t163
8．4．3 兩種實(shí)現(xiàn)的時(shí)間和
空間復(fù)雜度分析\t164
8．4．4 練習(xí)8．3\t165
8．5 案例學(xué)習(xí)：模擬超市排隊(duì)
結(jié)賬\t165
8．5．1 要求\t165
8．5．2 分析\t165
8．5．3 用戶界面\t166
8．5．4 類及其作用\t166
8．6 優(yōu)先隊(duì)列\(zhòng)t171
練習(xí)8．4\t175
8．7 案例學(xué)習(xí)：急癥室調(diào)度\t175
8．7．1 需求\t175
8．7．2 分析\t175
8．7．3 類\t176
8．7．4 設(shè)計(jì)和實(shí)現(xiàn)\t177
8．8 小結(jié)\t179
8．9 復(fù)習(xí)題\t179
8．10 編程項(xiàng)目\t180
第9章 列表\t182
9．1 概覽\t182
9．2 使用列表\t183
9．2．1 基于索引的操作\t183
9．2．2 基于內(nèi)容的操作\t183
9．2．3 基于位置的操作\t184
9．2．4 列表的接口\t187
9．2．5 練習(xí)9．1\t188
9．3 列表的應(yīng)用\t188
9．3．1 堆存儲(chǔ)管理\t188
9．3．2 組織磁盤上的文件\t189
9．3．3 其他集合的實(shí)現(xiàn)\t190
9．4 列表實(shí)現(xiàn)\t191
9．4．1 AbstractList類的角色\t191
9．4．2 基于數(shù)組的實(shí)現(xiàn)\t192
9．4．3 鏈表實(shí)現(xiàn)\t194
9．4．4 兩種實(shí)現(xiàn)的時(shí)間和
空間分析\t196
9．4．5 練習(xí)9．2\t197
9．5 實(shí)現(xiàn)列表迭代器\t197
9．5．1 列表迭代器的角色
和作用\t197
9．5．2 設(shè)置和實(shí)例化一個(gè)
列表迭代器類\t198
9．5．3 列表迭代器中的導(dǎo)
航方法\t199
9．5．4 列表迭代器中的修
改器方法\t200
9．5．5 鏈表列表的列表迭
代器的設(shè)計(jì)\t201
9．5．6 列表迭代器實(shí)現(xiàn)的
時(shí)間和空間分析\t201
9．6 案例學(xué)習(xí)：開發(fā)一個(gè)有序
的列表\t201
9．6．1 要求\t201
9．6．2 分析\t202
9．6．3 設(shè)計(jì)\t202
9．6．4 實(shí)現(xiàn)（代碼）\t204
9．7 小結(jié)\t205
9．8 復(fù)習(xí)題\t205
9．9 編程項(xiàng)目\t206
第10章 樹\t208
10．1 樹的概覽\t208
10．1．1 樹的術(shù)語(yǔ)\t208
10．1．2 普通的樹和二叉樹\t209
10．1．3 樹的遞歸定義\t210
10．1．4 練習(xí)10．1\t210
10．2 為什么要使用樹\t210
10．3 二叉樹的形狀\t211
練習(xí)10．2\t213
10．4 二叉樹的3種常見應(yīng)用\t213
10．4．1 堆\t213
10．4．2 二叉搜索樹\t214
10．4．3 表達(dá)式樹\t215
10．4．4 練習(xí)10．3\t216
10．5 二叉樹的遍歷\t216
10．5．1 前序遍歷\t216
10．5．2 中序遍歷\t217
10．5．3 后序遍歷\t217
10．5．4 層序遍歷\t217
10．6 開發(fā)二叉搜索樹\t217
10．6．1 二叉搜索樹接口\t218
10．6．2 鏈表實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)\t219
10．6．3 二叉搜索樹的復(fù)雜度
分析\t223
10．6．4 練習(xí)10．4\t224
10．7 遞歸的后代解析和編程語(yǔ)言\t224
10．7．1 語(yǔ)法簡(jiǎn)介\t224
10．7．2 在語(yǔ)言中識(shí)別、解析
和解釋句子\t226
10．7．3 詞法分析和掃描器\t226
10．7．4 解析策略\t227
10．8 案例學(xué)習(xí)：解析和表達(dá)式樹\t227
10．8．1 要求\t227
10．8．2 分析\t228
10．8．3 節(jié)點(diǎn)類的設(shè)計(jì)和實(shí)現(xiàn)\t228
10．8．4 解析器類的設(shè)計(jì)和
實(shí)現(xiàn)\t230
10．9 二叉樹的數(shù)組實(shí)現(xiàn)\t231
練習(xí)10．5\t232
10．10 實(shí)現(xiàn)堆\t232
練習(xí)10．6\t234
10．11 小結(jié)\t234
10．12 復(fù)習(xí)題\t235
10．13 編程項(xiàng)目\t236
第11章 集和字典\t238
11．1 使用集\t238
11．2 Python的set類\t239
11．2．1 集的一個(gè)示例會(huì)話\t239
11．2．2 集的應(yīng)用\t240
11．2．3 集和包的關(guān)系\t240
11．2．4 集和字典的關(guān)系\t240
11．2．5 集的實(shí)現(xiàn)\t240
11．2．6 練習(xí)11．1\t241
11．3 集的基于數(shù)組和鏈表的實(shí)現(xiàn)\t241
11．3．1 AbstractSet類\t241
11．3．2 ArraySet類\t242
11．4 使用字典\t243
11．5 基于數(shù)組和基于鏈表的
字典實(shí)現(xiàn)\t244
11．5．1 Item類\t244
11．5．2 AbstractDict類\t245
11．5．3 ArrayDict類\t246
11．5．4 集和字典的基于數(shù)組
和列表的實(shí)現(xiàn)的復(fù)雜
度分析\t247
11．5．5 練習(xí)11．2\t248
11．6 哈希策略\t248
11．6．1 沖突和密度的關(guān)系\t249
11．6．2 非數(shù)字鍵的哈希\t250
11．6．3 線性探測(cè)\t251
11．6．4 二次探測(cè)\t252
11．6．5 鏈化\t253
11．6．6 復(fù)雜度分析\t253
11．6．7 練習(xí)11．3\t254
11．7 案例學(xué)習(xí)：探查哈希策略\t254
11．7．1 需求\t255
11．7．2 分析\t255
11．7．3 設(shè)計(jì)\t256
11．8 集的哈希實(shí)現(xiàn)\t258
11．9 字典的哈希實(shí)現(xiàn)\t261
練習(xí)11．4\t263
11．10 有序的集和字典\t263
11．11 小結(jié)\t264
11．12 復(fù)習(xí)題\t264
11．13 編程項(xiàng)目\t265
第12章 圖\t267
12．1 圖的術(shù)語(yǔ)\t267
練習(xí)12．1\t269
12．2 為什么使用圖\t270
12．3 圖的表示\t270
12．3．1 相鄰矩陣\t270
12．3．2 鄰接表\t271
12．3．3 兩種表示的分析\t272
12．3．4 運(yùn)行時(shí)間的進(jìn)一步
考慮\t272
12．3．5 練習(xí)12．2\t273
12．4 圖的遍歷\t273
12．4．1 泛型遍歷算法\t273
12．4．2 廣度優(yōu)先遍歷和深度
優(yōu)先遍歷\t274
12．4．3 圖區(qū)域\t275
12．4．4 練習(xí)12．3\t276
12．5 圖中的樹\t276
12．5．1 生成樹和森林\t276
12．5．2 最小生成樹\t277
12．5．3 最小生成樹的算法\t277
12．6 拓?fù)渑判騖t279
12．7 最短路徑問題\t279
12．7．1 Dijkstra算法\t280
12．7．2 初始化步驟\t280
12．7．3 計(jì)算步驟\t281
12．7．4 無限的表示和用法\t282
12．7．5 分析\t282
12．7．6 練習(xí)12．4\t282
12．7．7 Floyd算法\t283
12．7．8 分析\t283
12．8 開發(fā)一個(gè)圖集合\t284
12．8．1 使用圖集合的示例\t284
12．8．2 LinkedDirected-
Graph類\t285
12．8．3 LinkedVertex類\t288
12．8．4 LinkedEdge類\t289
12．9 案例學(xué)習(xí)：測(cè)試圖算法\t290
12．9．1 需求\t290
12．9．2 分析\t290
12．9．3 GraphDemoView類和
GraphDemoModel類\t291
12．9．4 實(shí)現(xiàn)（代碼）\t292
12．10 小結(jié)\t295
12．11 復(fù)習(xí)題\t296
12．12 編程項(xiàng)目\t297
附錄 供Python程序員使用的
集合框架\t299