數據結構：Python語言描述

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