數據結構和算法 Python 和 C++ 語言描述

David M. Reed

美國Capital大學計算機科學系教授，負責教授Python和C++編程。
他擁有俄亥俄州立大學計算機博士學位。約翰·策勒（John Zelle）美國Wartburg大學數學和計算機系教授。
他負責教授Python程序設計課程，是《Python程序設計(第3版）》一書的作者。  

目錄：  
第1章抽象與分析.................................... 1
1.1概要..... .......................................... 1
1.1.1大型編程.. .......................... 1
1.1.2前方的道路................. ....... 2
1.2功能的抽象................................... 3
1.2. 1契約式設計........................ 3
1.2.2驗證先驗條件.............. ...... 6
1.2.3自上而下的設計................ 9
1.2.4記錄副作用............ .......... 11
1.3算法分析.................................... . 12
1.3.1線性搜索.......................... 12
1.3.2二分搜索........... ............... 14
1.3.3非正式的算法比較.......... 15
1.3.4算法的正式分析........ ...... 17
1.3.5大O符號與Θ符號......... 21
1.4小結...................... ....................... 23
1.5練習............................................. 23

第2章數據的抽象.................................. 27
2.1概要......... .................................... 27
2.2抽像數據類型......... .................... 27
2.2.1從數據類型到抽像數據
類型................... ............... 28
2.2.2定義抽像數據類型.......... 28
2.2.3實現抽像數據類型......... . 30
2.3抽像數據類型和對象................. 32
2.3.1規範.................... .............. 32
2.3.2實現............................... ... 34
2.3.3改變存儲方式.................. 35
2.3.4面向對象的設計和編程.... 36
2.4抽像數據類型的實例：
數據集（Dataset）.................. 38
2.4.1面向對象設計的過程...... 38
2.4.2定義一個抽像數據
類型... ............................... 39
2.4.3實現這個抽像數據類型.... 41
2.5抽像數據類型的實例：
有理數（Rational） ................42
2.5.1運算符重載.... ..................42
2.5.2有理數（Rational）類...44
2.6增量開發以及單元測試............ ..45
2.7小結............................................. 48
2.8練習.............................................48

第3章容器類..........................................52
3.1概要. ............................................52
3.2 Python的列表. ............................52
3.3順序集合：撲克牌牌組............. .53
3.4有序集合：手牌.........................56
3.4.1創建橋牌的手牌....... ........56
3.4.2比較撲克牌......................58
3.4.3撲克牌排序...... ................59
3.5 Python裡列表的實現.................61
3.5.1基於數組的列表...............61
3.5.2效率分析...................... ....62
3.6 Python的字典（選讀） .............63
3.6.1字典抽像數據類型...........63
3.6.2熟悉Python字典.............64
3.6.3字典的實現......................65
3.6.4擴展示例：馬爾可夫鏈.....67
3.7小結...................................... .......70
3.8練習........................................ .....71

第4章鍊式結構和迭代器......................75
4.1概要.......... ...................................75
4.2 Python的內存模型......... ............75
傳遞參數................................... ...80
4.3鍊錶實現.....................................81
4.4鍊錶抽像數據類型的實現..........85
4.5迭代器.................................. .......95
4.5.1 Python的迭代器..............95
4.5.2在鍊錶（LList）裡
添加迭代器................ ......96
4.5.3通過Python的生成器來
迭代................................. 97
4.6基於游標的列表API（選讀） .... 99
4.6.1游標（Cursor）的
API .......................... ......... 99
4.6.2 Python的游標列表
（CursorList）............ 100
4.6.3鍊式結構的游標列表
（CursorList）..... ....... 102
4.7鍊錶vs數組............................. 104
4.8小結...... ..................................... 104
4.9練習.......... ................................. 105

第5章堆棧和隊列.......... ...................... 109
5.1概要......................... .................. 109
5.2堆棧............................. .............. 109
5.2.1堆棧抽像數據類型........ 109
5.2.2堆棧的簡單應用............ 110
5.2.3堆棧的實現........ ............ 112
5.2.4應用程序：處理算術
方程............................ ... 113
5.2.5應用程序：語法的處理
（選讀） ......................... 116
5.3隊列...... ..................................... 119
5.3.1隊列抽像數據類型..... ... 119
5.3.2隊列的簡單應用............ 120
5.4隊列的實現...................... ......... 121
5.5應用程序示例：隊列的模擬
（選讀） ............................. ........ 123
5.6小結....................................... .... 128
5.7練習........................................... 128

第6章遞歸............................................ 133
6.1概要........................................... 133
6.2遞歸定義................................... 134
6.3簡單的遞歸示例...... ................. 136
6.3.1示例：字符串反轉........ 136
6.3.2示例：字謎........ ............ 137
6.3.3示例：快速計算指數.... 138
6.3.4示例：二分搜索............ 139
6.4遞歸的分析............................... 140
6.5排序................ ...........................142
6.5.1遞歸設計：歸併排序.....142
6.5.2分析歸併排序.. ..............144
6.6一個“難”題：漢諾塔............146
6.7小結.......... .................................149
6.8練習.............. .............................150

第7章樹................ ................................156
7.1概要............... ............................156
7.2樹的術語................. ..................156
7.3示例應用程序：表達式樹........158
7.4樹的存儲方式...........................159
7.5應用：二叉搜索樹...................160
7.5.1二分查找屬性................160
7.5.2實現一個二叉搜索樹.....161
7.5.3遍歷整個二叉搜索樹
（BST） ....................... ....166
7.5.4二叉搜索樹（BST）的
運行時分析....................168
7.6使用二叉搜索樹（BST）來
實現映射（選讀）....................169
7.7小結...................... .....................171
7.8練習.......................... .................172

第8章為Python程序員準備的
C++簡介..................... ................177
8.1概要............................... ............177
8.2 C++的歷史和背景....................178
8.3註釋、代碼塊、變量名和
關鍵字........................................182
8.4數據類型和變量聲明. ..............183
8.5 Include語句、命名空間
以及輸入/輸出......................... ..186
8.6編譯...........................................189
8.7表達式和運算符優先級............191
8.8條件語句........................... ........193
8.9數據類型轉換...........................196
8.10循環語句...... ...........................197
8.11數組.................... .....................199
8.11.1一維數組...................... .199
8.11.2多維數組.......................201
8.11.3字符數組.............. ........ 201
8.12函數的細節............................. 202
8.12.1聲明、定義以及原型.... 202
8.12.2值傳遞.......................... 205
8.12.3引用傳遞...................... 205
8.12.4將數組作為參數傳遞.... 206
8.12.5常量參數.... ................... 208
8.12.6默認參數...................... 208
8.13頭文件和內聯函數................. 209
8.14斷言與測試....................... ...... 213
8.15變量的作用域以及生命週期.... 214
8.16 Python程序員編寫C++程序
時的常見錯誤................... ...... 215
8.17其他的C++相關話題
（選讀）.................................. . 216
8.17.1 C++的Switch語句.... 216
8.17.2創建C++的命名空間.... 218
8.17.3全局變量.................. .... 219
8.18小結......................................... 220
8.19練習......................................... 220

第9章C++類.. ...................................... 224
9.1基本的語法和語義................... 224
9.2字符串..................... .................. 232
9.3文件輸入和輸出....................... 234
9.4運算符重載............................... 236
9.5類變量和方法............ ............... 242
9.6小結................................ ........... 246
9.7練習.................................... ....... 246

第10章C++的動態內存...................... 250
10.1概要.......... ............................... 250
10.2 C++的指針.............. ................ 254
10.3動態數組.............................. ... 259
10.4動態內存類............................. 263
10.4.1析構函數...... ................ 263
10.4.2複製構造函數.............. 265
10.4.3賦值運算符...... ............ 268
10.4.4完整的動態數組類...... 270
10.4.5引用返回類型.............. 275
10.5動態內存錯誤.......... ............... 276
10.5.1內存洩漏......................276
10.5.2訪問無效內存...............277
10.5.3內存錯誤總結...............280
10.6小結.......... ...............................281
10.7練習................ .........................281

第11章C++的鍊式結構................ .......285
11.1概要........................................ .285
11.2 C++鍊式結構的類..................286
11.3 C++鍊錶................... ...............288
11.4 C++鏈接的動態內存錯誤.......298
11.5小結................. ........................299
11.6練習....................... ..................300

第12章C++模板.......................... ........302
12.1概要.........................................302
12.2模板方法... ..............................303
12.3模板類................ .....................305
12.3.1標準模板庫的
vector類................... .305
12.3.2用戶定義的模板類.......308
12.4小結.............................. ........... 311
12.5練習.................................... .....312

第13章堆、平衡樹和散列表..............314
13.1概要................. ........................314
13.2優先隊列和堆.................... .....314
13.2.1堆排序..........................320
13.2.2關於堆和優先隊列
實現的說明. .................320
13.3平衡樹............................. ........321
13.4其他的樹結構.........................329
13.5散列表.....................................329
13.6小結....... ..................................339
13.7練習............. ............................339

第14章圖................. .............................343
14.1概要.................. .......................343
14.2圖數據結構...................... .......344
14.3 *短路徑算法.........................347
14.3.1無權*短路徑... ............347
14.3.2加權*短路徑...............350
14.4深度優先算法.......... ...............353
14.5 *小生成樹............................. 357
14.5.1 Kruskal算法................ 358
14.5.2不交集數據結構.......... 358
14.5.3 Prim算法.... ................. 361
14.6小結.............................. ........... 361
14.7練習......................................... 362

第15章算法技術. ................................ 365
15.1概要............... .......................... 365
15.2分治算法................... .............. 365
15.2.1分析遞歸函數.............. 366
15.2.2快速排序......... .............368
15.3貪心算法................................. 372
15.4動態規劃.................................378
15.4.1 *長公共子序列.... .......379
15.4.2記憶化..........................382
15.4.3矩陣鏈乘法.... ..............382
15.5 NP完全問題...........................383
15.6小結. ........................................384
15.7練習....... ..................................385
術語表............. ...........................................387