數據結構 Python 語言描述 (Fundamentals of Python: Data Structures)
內容描述
在電腦科學中，數據結構是一門進階性課程，概念抽象，難度較大。Python語言的語法簡單，交互性強。用Python來講解數據結構等主題，比C語言等實現起來更為容易，更為清晰。
《數據結構 Python語言描述》第1章簡單介紹了Python語言的基礎知識和特性。第2章到第4章對抽象數據類型、數據結構、復雜度分析、數組和線性鏈表結構進行了詳細介紹，第5章和第6章重點介紹了面向對象設計的相關知識、第5章包括接口和實現之間的重點差異、多態以及信息隱藏等內容，第6章主要講解繼承的相關知識，第7章到第9章以棧、隊列和列表為代表，介紹了線性集合的相關知識。第10章介紹了各種樹結構，第11章講解了集和字典的相關內容，第12章介紹了圖和圖處理算法。每章最後，還給出了復習題和案例學習，幫助讀者鞏固和思考。
《數據結構 Python語言描述》不僅適合高等院校電腦專業師生閱讀，也適合對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
作者介紹
Kenneth A .Lambert是華盛頓與李大學的計算機科學教授和系主任。他教授編程課程30 年，並且是計算機科學教育的積極研究者。Lambert編著以及與人合著了一共2 5 本教材，包括與Douglas Nance和Thomas Naps編寫的一系列C++ 入門教材，與Martin Osbor ne編寫的一系列Java入門教材， 以及一系列Python入門教材。他還是《Easy GUI Progr amming in Python》的作者。
相關書籍
Practical Machine Learning and Image Processing: For Facial Recognition, Object Detection, and Pattern Recognition Using Python
2017-12-01
_@9787301306017_https://static.coderbridge.com/images/books/9787301306017.jpg)