數據結構 Python 語言描述 (Fundamentals of Python: Data Structures)

Kenneth A .Lambert是華盛頓與李大學的計算機科學教授和系主任。他教授編程課程30 年，並且是計算機科學教育的積極研究者。Lambert編著以及與人合著了一共2 5 本教材，包括與Douglas Nance和Thomas Naps編寫的一系列C++ 入門教材，與Martin Osbor ne編寫的一系列Java入門教材， 以及一系列Python入門教材。他還是《Easy GUI Progr amming in Python》的作者。

第1章Python編程基礎1 
1.1基本程序要素1 
1.1.1程序和模塊1 
1.1.2 Python程序示例：猜數字1 
1.1.3編輯、編譯並運行
Python程序2 
1.1.4程序註釋3 
1.1.5詞法元素3 
1.1.6拼寫和命名慣例3 
1.1.7語法元素4 
1.1.8字面值4 
1.1.9字符串字面值4 
1.1.10運算符和表達式5 
1.1.11函數調用5 
1.1.12 print函數5 
1.1.13 input函數5 
1.1.14類型轉換函數和
混合模式運算6 
1.1.15可選的和關鍵字
函數參數6 
1.1.16變量和賦值語句6 
1.1.17 Python數據類型7 
1.1.18 import語句7 
1.1.19獲取關於程序組件
的幫助7 
1.2控制語句8 
1.2.1條件式語句8 
1.2.2使用if __name__ == 
"__main__" 9 
1.2.3循環語句10
1.3字符串及其運算10 
1.3.1運算符10 
1.3.2格式化字符串以便輸出11 
1.3.3對象和方法調用13 
1.4內建Python集合及其操作13 
1.4.1列表14 
1.4.2元組14 
1.4.3遍歷序列14 
1.4.4字典15 
1.4.5搜索一個值15 
1.4.6對集合應用模式匹配15 
1.5編寫新的函數16 
1.5.1函數定義16 
1.5.2遞歸函數17 
1.5.3嵌套的函數定義19 
1.5.4高階函數19 
1.5.5使用lambda表達式
創建匿名函數20 
1.6捕獲異常20 
1.7文件及其操作21 
1.7.1文本文件的輸出22 
1.7.2將數字寫入到一個
文本文件22 
1.7.3從文本文件讀取文本23 
1.7.4從文件讀取數字24 
1.7.5使用pickle讀寫對象24 
1.8創建新的類25 
1.9編程項目28 

第2章集合概覽30 
2.1集合類型30 
2.1.1線性集合30 
2.1.2層級集合31
2.1.3圖集合31 
2.1.4無序集合31 
2.1.5有序集合31 
2.1.6集合類型的分類32 
2.2集合上的操作32 
2.3集合的實現34 
2.4小結35 
2.5複習題35 
2.6編程項目36 

第3章搜索、排序和復雜度分析37 
3.1評估算法的性能37 
3.1.1度量算法的運行時間37 
3.1.2統計指令39 
3.1.3度量算法所使用的內存41 
3.1.4練習3.1 41 
3.2複雜度分析41 
3.2.1複雜度的階41 
3.2.2大O表示法43 
3.2.3常量比例的作用43 
3.2.4練習3.2 43 
3.3搜索算法44 
3.3.1搜索最小值44 
3.3.2順序搜索一個列表44 
3.3.3最好情況、最壞情況和
平均情況的性能45 
3.3.4有序列表的二叉搜索45 
3.3.5比較數據項47 
3.3.6練習3.3 48 
3.4基本排序算法48 
3.4.1選擇排序48 
3.4.2冒泡排序49 
3.4.3插入排序50
3.4.4再談最好情況、最壞情
況和平均情況的性能52 
3.4.5練習3.4 52 
3.5更快的排序53 
3.5.1快速排序簡介53 
3.5.2合併排序56 
3.5.3練習3.5 59 
3.6指數算法：遞歸式的
Fibonacci 59 
3.7案例學習：算法探查器61 
3.7.1需求61 
3.7.2分析61 
3.7.3設計62 
3.7.4實現（編寫代碼） 63 
3.8小結65 
3.9複習題66 
3.10編程項目67 

第4章數組和鍊錶結構69 
4.1數組數據結構69 
4.1.1隨機訪問和連續內存71 
4.1.2靜態內存和動態內存72 
4.1.3物理大小和邏輯大小72 
4.1.4練習4.1 73 
4.2數組的操作73 
4.2.1增加數組的大小73 
4.2.2減小數組的大小74 
4.2.3在數組中插入一項74 
4.2.4從數組中刪除一項75 
4.2.5複雜度權衡：時間、
空間和數組76 
4.2.6練習4.2 76 
4.3二維數組77
4.3.1處理網格77 
4.3.2創建並初始化網格77 
4.3.3定義Grid類78 
4.3.4雜亂的網格和多維數組79 
4.3.5練習4.3 79 
4.4鍊錶結構80 
4.4.1單鍊錶結構和雙鍊錶
結構80 
4.4.2非連續性內存和節點81 
4.4.3定義一個單鍊錶節點類82 
4.4.4使用單鍊錶節點類82 
4.4.5練習4.4 84 
4.5單鍊錶結構上的操作84 
4.5. 1遍歷84 
4.5.2搜索85 
4.5.3替換86 
4.5.4在開始處插入86 
4.5.5在末尾插入87 
4.5.6從開始處刪除87 
4.5.7從末尾刪除88 
4.5.8在任何位置插入89 
4.5.9從任意位置刪除90 
4.5.10複雜度權衡：時間、
空間和單鍊錶結構91 
4.5.11練習4.5 92 
4.6鍊錶的變體92 
4.6.1帶有一個啞頭節點
的循環鍊錶結構92 
4.6.2雙鍊錶結構93 
4.6.3練習4.6 95 
4.7小結95 
4.8複習題96
4.9編程項目96 

第5章接口、實現和多態98 
5.1開發接口98 
5.1.1定義包接口98 
5.1.2指定參數和返回值99 
5.1.3構造方法和實現類101 
5.1.4先驗條件、後驗條件、
異常和文檔101 
5.1.5用Python編寫接口102 
5.1.6練習5.1 103 
5.2開發一個基於數組的實現103 
5.2.1選擇並初始化數據
結構103 
5.2.2先完成容易的方法104 
5.2. 3完成迭代器105 
5.2.4完成使用迭代器
的方法106 
5.2.5 in運算符和__contains__ 
方法106 
5.2.6完成remove方法107 
5.2.7練習5.2 107 
5.3開發一個基於鍊錶的實現107 
5.3.1初始化數據結構108 
5.3.2完成迭代器109 
5.3.3完成clear和add方法109 
5.3.4完成remove方法109 
5.3.5練習5.3 110 
5.4兩個包實現的運行時性能110 
5.5測試兩個包實現111 
5.6用UML圖表示包資源112
5.7小結113 
5.8複習題113 
5.9編程項目114 

第6章繼承和抽像類115 
6.1使用繼承定制一個已有的類115 
6.1.1已有類的子類化115 
6.1.2再談__init__方法116 
6.1.3添加新的contains方法117 
6.1.4修改已有的add方法117 
6.1.5 ArraySortedBag的運行
時間性能118 
6.1.6 Python中的類層級118 
6.1.7練習6.1 119 
6.2使用抽像類去除代碼冗餘性119 
6.2.1設計一個
AbstractBag類119 
6.2.2重新編寫AbstractBag 
中的__init__方法120 
6.2.3修改AbstractBag 
的子類120 
6.2.4將AbstractBag中的
__add__方法泛化121 
6.3所有集合的一個抽像類122 
6.3.1將AbstractCollection 
整合到集合層級中122 
6.3.2在__eq__方法中使用
兩個迭代器123 
6.3.3練習6.2 124 
6.4小結124
6.5複習題124 
6.6編程項目125 

第7章棧127 
7.1棧概覽127 
7.2使用棧128 
7.2.1棧接口128 
7.2.2初始化一個棧129 
7.2.3示例應用程序：
匹配括號129 
7.2.4練習7.1 131 
7.3棧的3種應用131 
7.3.1計算算術表達式131 
7.3.2計算後綴表達式132 
7.3.3練習7.2 133 
7.3.4將中綴表達式轉換為
後綴表達式133 
7.3.5練習7.3 135 
7.3 .6回溯算法135 
7.3.7內存管理137 
7.4棧的實現138 
7.4.1測試驅動程序138 
7.4.2將棧添加到集合層級中139 
7.4.3數組實現140 
7.4.4鍊錶實現141 
7.4.5 AbstractStack類的
作用144 
7.4.6兩種實現的時間和
空間分析144 
7.4.7練習7.4 145 
7.5案例學習：計算後綴表達式145 
7.5.1要求145 
7.5.2分析145
7.5.3設計148 
7.5.4實現150 
7.6小結153 
7.7複習題153 
7.8編程項目154 

第8章隊列156 
8.1隊列概覽156 
8.2隊列接口及其應用157 
練習8.1 158 
8.3隊列的兩個應用159 
8.3.1模擬159 
8.3.2輪詢CPU調度161 
8.3.3練習8.2 161 
8.4隊列的實現161 
8.4.1隊列的鍊錶實現161 
8.4.2數組實現163 
8.4.3兩種實現的時間和
空間複雜度分析164 
8.4 .4練習8.3 165 
8.5案例學習：模擬超市排隊
結賬165 
8.5.1要求165 
8.5.2分析165 
8.5.3用戶界面166 
8.5.4類及其作用166 
8.6優先隊列171 
練習8.4 175 
8.7案例學習：急症室調度175 
8.7.1需求175 
8.7.2分析175 
8.7.3類176 
8.7.4設計和實現177 
8.8小結179
8.9複習題179 
8.10編程項目180 

第9章列表182 
9.1概覽182 
9.2使用列表183 
9.2.1基於索引的操作183 
9.2.2基於內容的操作183 
9.2.3基於位置的操作184 
9.2.4列表的接口187 
9.2.5練習9.1 188 
9.3列表的應用188 
9.3.1堆存儲管理188 
9.3.2組織磁盤上的文件189 
9.3.3其他集合的實現190 
9.4列表實現191 
9.4.1 AbstractList類的角色191 
9.4. 2基於數組的實現192 
9.4.3鍊錶實現194 
9.4.4兩種實現的時間和
空間分析196 
9.4.5練習9.2 197 
9.5實現列表迭代器197 
9.5.1列表迭代器的角色
和作用197 
9.5.2設置和實例化一個
列表迭代器類198 
9.5.3列表迭代器中的導
航方法199 
9.5.4列表迭代器中的修
改器方法200 
9.5.5鍊錶列表的列表迭
代器的設計201
9.5.6列表迭代器實現的
時間和空間分析201 
9.6案例學習：開發一個有序
的列表201 
9.6.1要求201 
9.6.2分析202 
9.6.3設計202 
9.6.4實現（代碼） 204 
9.7小結205 
9.8複習題205 
9.9編程項目206
 
第10章樹208 
10.1樹的概覽208 
10.1.1樹的術語208 
10.1.2普通的樹和二叉樹209 
10.1.3樹的遞歸定義210 
10.1.4練習10.1 210 
10.2為什麼要使用樹210 
10.3二叉樹的形狀211 
練習10.2 213 
10.4二叉樹的3種常見應用213 
10.4.1堆213 
10.4.2二叉搜索樹214 
10.4.3表達式樹215 
10.4.4練習10.3 216 
10.5二叉樹的遍歷216 
10.5.1前序遍歷216 
10.5.2中序遍歷217 
10.5.3後序遍歷217 
10.5.4層序遍歷217 
10.6開發二叉搜索樹217
10.6.1二叉搜索樹接口218 
10.6.2鍊錶實現的數據結構219 
10.6.3二叉搜索樹的複雜度
分析223 
10.6.4練習10.4 224 
10.7遞歸的後代解析和編程語言224 
10.7.1語法簡介224 
10.7.2在語言中識別、解析
和解釋句子226 
10.7.3詞法分析和掃描器226 
10.7.4解析策略227 
10.8案例學習：解析和表達式樹227 
10.8.1要求227 
10.8.2分析228 
10.8 .3節點類的設計和實現228 
10.8.4解析器類的設計和
實現230 
10.9二叉樹的數組實現231 
練習10.5 232 
10.10實現堆232 
練習10.6 234 
10.11小結234 
10.12複習題235 
10.13編程項目236 

第11章集和字典238 
11.1使用集238 
11.2 Python的set類239 
11.2.1集的一個示例會話239 
11.2.2集的應用240 
11.2.3集和包的關係240
11.2.4集和字典的關係240 
11.2.5集的實現240 
11.2.6練習11.1 241 
11.3集的基於數組和鍊錶的實現241 
11.3.1 AbstractSet類241 
11.3.2 ArraySet類242 
11.4使用字典243 
11.5基於數組和基於鍊錶的
字典實現244 
11.5.1 Item類244 
11.5.2 AbstractDict類245 
11.5.3 ArrayDict類246 
11.5.4集和字典的基於數組
和列表的實現的複雜
度分析247 
11.5.5練習11.2 248 
11.6哈希策略248 
11.6.1衝突和密度的關係249 
11.6.2非數字鍵的哈希250 
11.6.3線性探測251 
11.6.4二次探測252 
11.6.5鏈化253 
11.6.6複雜度分析253 
11.6.7練習11.3 254 
11.7案例學習：探查哈希策略254 
11.7.1需求255 
11.7.2分析255 
11.7.3設計256 
11.8集的哈希實現258
11.9字典的哈希實現261 
練習11.4 263 
11.10有序的集和字典263 
11.11小結264 
11.12複習題264 
11.13編程項目265

第12章圖267 
12.1圖的術語267 
練習12.1 269 
12.2為什麼使用圖270 
12.3圖的表示270 
12.3.1相鄰矩陣270 
12.3.2鄰接表271 
12.3.3兩種表示的分析272 
12.3.4運行時間的進一步考慮272 
12.3.5練習12.2 273 
12.4圖的遍歷273 
12.4.1泛型遍歷算法273 
12.4.2廣度優先遍歷和深度
優先遍歷274 
12.4.3圖區域275 
12.4.4練習12.3 276 
12.5圖中的樹276 
12.5.1生成樹和森林276 
12.5.2最小生成樹277 
12.5.3最小生成樹的算法277 
12.6拓撲排序279 
12.7最短路徑問題279 
12.7.1 Dijkstra算法280 
12.7.2初始化步驟280
12.7.3計算步驟281 
12.7.4無限的表示和用法282 
12.7.5分析282 
12.7.6練習12.4 282 
12.7.7 Floyd算法283 
12.7.8分析283 
12.8開發一個圖集合284 
12.8.1使用圖集合的示例284 
12.8.2 LinkedDirected- 
Graph類285 
12.8.3 LinkedVertex類288 
12.8.4 LinkedEdge類289 
12.9案例學習：測試圖算法290 
12.9.1需求290 
12.9.2分析290 
12.9.3 GraphDemoView類和
GraphDemoModel類291 
12.9 .4實現（代碼） 292 
12.10小結295 
12.11複習題296 
12.12編程項目297 
附錄供Python程序員使用的
集合框架299