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

肯尼思.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的示例程序：猜數字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函數調用5
1．1．11 print函數6
1．1．12 input函數6
1．1．13類型轉換函數和混合模式操作6
1．1．14可选和關鍵字函數參數6
1．1．15變量和賦值語句7
1．1．16 Python的數據類型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循環語句10
1．3字符串及其運算11
1．3．1運算符11
1．3．2格式化字符串以便輸出12
1．3．3對象和方法調用13
1．4 Python內置的多項集及其操作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創建新函數17
1．5．1函數定義17
1．5．2遞歸函數18
1．5．3函數的嵌套定義19
1．5．4高階函數20
1．5．5使用lambda表達式創建匿名函數21
1．6捕獲異常21
1．7文件及其操作22
1．7．1文本文件的輸出23
1．7 ．2將數字寫入文本文件23
1．7．3從文本文件讀取文本24
1．7．4從文件讀取數據25
1．7．5使用pickle讀寫對象26
1．8創建新類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類型轉換36
2．2．3克隆和相等性36
2．3迭代器和高階函數37
2．4多項集的實現37
2．5章節總結38
2．6複習題39
2．7編程項目40

第3章搜索、排序以及復雜度分析41
3．1衡量算法的效率41
3．1．1衡量算法的運行時42
3．1．2統計指令數43
3．1．3衡量算法使用的內存45
3．2複雜度分析45
3．2 ．1複雜度的階45
3．2．2大O表示法47
3．2．3比例常數的作用47
3．3搜索算法48
3．3．1最小值搜索48
3．3．2順序搜索列表49
3．3．3最好情況、最壞情況以及平均情況下的性能49
3．3．4基於有序列表的二分搜索50
3．3．5比較數據元素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指數複雜度的算法：遞歸斐波那契63
3．7案例研究：算法分析器65
3．7．1案例需求65
3．7．2案例分析65
3．7．3案例設計66
3．7．4案例實現（編碼） 67
3．8章節總結69
3．9複習題70
3．10編程項目71

第4章數組和鏈接結構73
4．1數組數據結構73
4．1．1隨機訪問和連續內存75
4 ．1．2靜態內存和動態內存76
4．1．3物理尺寸和邏輯尺寸76
4．2數組的操作77
4．2．1增大數組的尺寸77
4．2．2減小數組的尺寸78
4．2．3將元素插入增大的數組78
4．2．4從數組裡刪除元素79
4．2．5複雜度的權衡：時間、空間和數組80
4．3二維數組（網格） 81
4．3．1使用網格81
4．3．2創建並初始化網格82
4．3．3定義Grid類82
4．3．4參差不齊的網格和多維數組83
4．4鏈接結構84
4．4．1單向鏈接結構和雙向鏈接結構84
4．4．2非連續內存和節點85
4．4． 3定義單向鏈接節點類86
4．4．4使用單向鏈接節點類87
4．5單向鏈接結構上的操作88
4．5．1遍歷88
4．5．2搜索89
4．5．3替換90
4．5．4在開始處插入90
4．5．5在結尾處插入91
4．5．6在開始處刪除92
4．5．7在結尾處刪除93
4．5．8在任意位置處插入94
4．5．9在任意位置處刪除95
4．5．10複雜度的權衡：時間、空間和單向鏈接結構96
4．6鏈接上的變化97
4．6．1包含虛擬頭節點的環狀鏈接結構97
4．6．2雙向鏈接結構98
4．7章節總結100
4．8複習題101
4．9編程項目102

第5章接口、實現和多態104
5．1開發接口104
5 ．1．1設計包接口105
5．1．2指定參數和返回值106
5．2構造函數和類的實現107
5．2．1前置條件、後置條件、異常和文檔107
5．2．2在Python裡編寫接口108
5．3開發基於數組的實現110
5．3．1選擇並初始化數據結構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開發基於鏈接的實現114
5．4．1初始化數據結構115
5．4．2完成迭代器115
5．4．3完成clear和add方法115
5．4．4完成remove方法116
5．5兩種包實現的運行時性能117
5．6測試包的兩種實現117
5．7使用UML繪製包資源118
5．8章節總結119
5．9複習題120
5．10編程項目120

第6章繼承與抽像類122
6．1使用繼承定制已經存在的類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裡類的層次結構的解釋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添加到多項集的層次結構裡130
6．3．2在_eq_方法裡使用兩個迭代器131
6．4多項集的專家級框架132
6．5章節總結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把中綴表達式轉換為後綴表達式144
7．3．4回溯算法146
7．3．5內存管理148
7．4棧的實現150
7．4．1測試驅動150
7．4．2將棧添加到多項集的層次結構151
7．4 ．3棧的數組實現152
7．4．4棧的鏈接實現153
7．4．5抽象棧類的作用155
7．4．6兩種實現的時間和空間複雜度分析156
7．5案例研究：計算後綴表達式157
7．5．1案例需求157
7．5．2案例分析157
7．5．3案例設計160
7．5．4案例實現163
7．6章節總結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的輪詢調度173
8．4隊列的實現174
8．4．1隊列的鏈接實現174
8．4．2隊列的數組實現175
8．4．3兩種實現的時間和空間複雜度分析177
8．5案例研究：超市收銀排隊的模擬178
8．5．1案例需求178
8．5．2案例分析178
8．5．3用戶交互接口178
8．5．4類和它們的職責179
8．6優先隊列184
8．7案例研究：急診室調度程序188
8．7．1案例需求188
8．7．2案例分析188
8．7．3類189
8．7．4案例設計與實現189
8．8章節總結191
8．9複習題192
8． 10編程項目193

第9章列表194
9．1列表的概述194
9．2使用列表195
9．2．1基於索引的操作196
9．2．2基於內容的操作196
9．2．3基於位置的操作196
9．2．4列表接口200
9．3列表的應用201
9．3．1堆存儲管理201
9．3．2磁盤文件管理202
9．3．3其他多項集的實現203
9．4列表的實現204
9．4．1 AbstractList類的作用204
9．4．2基於數組的實現205
9．4．3列表的鏈接實現207
9．4．4兩種實現的時間和空間複雜度分析209
9．5實現列表迭代器211
9．5．1列表迭代器的角色和職責211
9．5．2設置和實例化列表迭代器類211
9．5．3列表迭代器裡的導航方法212
9． 5．4列表迭代器裡的變異器方法213
9．5．5設計鏈接列表的列表迭代器215
9．5．6列表迭代器實現的時間和空間複雜度分析215
9．6案例研究：開發有序列表215
9．6．1案例需求215
9．6．2案例分析215
9．6．3案例設計216
9．6．4案例實現（編碼） 218
9．7遞歸列表的處理219
9．7． 1類Lisp列表的基本操作220
9．7．2類Lisp列表的遞歸遍歷221
9．7．3創建類Lisp列表222
9．7．4類Lisp列表的內部結構223
9．7．5使用_repr _在IDLE裡輸出類Lisp列表224
9．7．6列表和函數式編程225
9．8章節總結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用樹結構的原因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開發二叉查找樹240
10．6．1二叉查找樹接口240
10．6．2鏈接實現的數據結構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節點類的設計與實現251
10．8．4解析器類的設計與實現253
10．9二叉樹的數組實現254
10．10堆的實現255
10．11章節總結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集合的實現264
11．3集合的數組實現和鏈接實現264
11．3．1 AbstractSet類265
11．3．2 ArraySet類266
11．4使用字典266
11．5字典的數組實現和鏈接實現267
11．5．1 Entry類268
11．5．2 AbstractDict類269
11．5．3 ArrayDict類270
11．5．4字典的數組實現和鏈接實現的複雜度分析271
11．6哈希策略272
11．6．1衝突與密度的關係272
11．6．2非數字鍵的哈希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案例實現281
11．8集合的哈希實現283
11．9字典的哈希實現285
11．10有序集合和有序字典287
11．11章節總結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廣度優先遍歷和深度優先遍歷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開發圖多項集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案例實現（編碼） 320
12．10章節總結323
12．11複習題324
12．12編程項目325