《數據結構與算法（Python語言實現）》是由郭煒編寫的計算機類圖書，於2023年7月由中國水利水電出版社出版發行。
基本介紹
- 中文名：數據結構與算法（Python語言實現）
- 作者：郭煒
- 出版時間：2023年7月
- 出版社：中國水利水電出版社
- 頁數：380 頁
- 字數：558
- ISBN：9787522615974
- 類別：程式設計
- 定價：89.8 元
- 開本：16 開
- 裝幀：平裝
內容簡介,圖書目錄,本書特色,
內容簡介
《數據結構與算法（Python語言實現）》是一本全面、細緻、通俗易懂的數據結構和算法教材。數據結構與算法，是理論和實踐必須緊密結合的課程。對各類數據結構和算法，不但要掌握其理論，還應該能夠熟 練地編程實現。相比大多數數據結構和算法教材，本書的最大特點就是高標準的實踐性。除了少數特別複雜的數據結構，95%的數據結構和算法，都給出了完整可運行的代碼，共 115 份，並且這些代碼幾乎都在具體的例題中。
本書的例題和編程習題都可以在北京大學的線上程式評測平台OpenJudge上提交解題程式並自動評判對錯。
本書內容和習題按難度做了明確分級，因此不論計算機相關專業還是非計算機相關專業的師生，都可 以從中各取所需。本書可以作為數據結構和算法入門教材，也可以作為考研和找工作時提高面試成功率的秘籍。
圖書目錄
第1章 緒 論.................................................................................................... 1
1.1 算法和算法分析.......................................................................................... 1
1.1.1 什麼是算法..................................................................................................... 1
1.1.2 算法的時間複雜度及其表示法..........................................................................3
1.2 數據結構............................................................................................................ 6
1.2.1 數據的邏輯結構................................................................................................ 7
1.2.2 數據的存儲結構............................................................................................ 8
1.2.3 數據結構上的操作 ......................................................................................8
1.3 小結..................................................................................................................... 8
1.4 習題...................................................................................................................... 9
第2章 Python語言鞏固與提高............................................................... 11
2.1 Python變數的指針本質................................................................................... 11
2.2 Python操作的時間複雜度..................................................................... 15
2.3 函 數............................................................................................................ 17
2.3.1 lambda表達式........................................................................................... 17
2.3.2 高階函式和閉包............................................................................................ 17
2.3.3 global變數和nonlocal變數............................................................................. 19
2.3.4 函式參數的默認值 ...................................................................................... 20
2.3.5 參數個數可變的函式 .................................................................................. 20
★ 2.3.6 生成器 ...................................................................................................... 21
★ 2.3.7 裝飾器............................................................................... 23
2.4 面向對象程式設計............................................................................. 25
2.4.1 類和對象.......................................................................................... 25
2.4.2 記憶體垃圾自動回收和析構函式............................................................ 29
2.4.3 靜態屬性和靜態方法 .........................................................................30
2.4.4 私有屬性、私有方法和property裝飾器....................................... 31
2.4.5 繼承（派生）..................................................................................... 32
2.4.6 對象的比較................................................................................................... 35
2.4.7 疊代器.............................................................................................. 37
2.4.8 類的特殊方法................................................................................................ 38
2.4.9 類方法及修改類的方法 ............................................................................... 40
2.4.10 內部類....................................................................................................... 41
2.5 習題.......................................................................................................... 42
第3章 線性表.................................................................................................. 45
3.1 順序表................................................................................................................ 45
3.2 鏈 表.....................................................................................................................48
3.2.1 單鍊表.................................................................................................. 48
3.2.2 循環單鍊表................................................................................................ 53
3.2.3 雙鍊表..................................................................................................... 54
3.2.4 靜態鍊表........................................................................................................ 59
3.3 順序表和鍊表的選擇....................................................................................... 59
3.4 小結.............................................................................................................. 60
3.5 習題.................................................................................................................. 61
第4章 枚舉與二分法...................................................................................... 62
4.1 枚舉.................................................................................................................... 62
4.1.1 案例：八皇后問題（P0070）.............................................................................. 62
4.1.2 案例：假幣問題（P0080）.............................................................................. 63
4.1.3 案例：特殊密碼鎖（P0090）............................................................................ 65
4.1.4 案例：奧數問題（P0100）.................................................................................. 67
4.2二分法........................................................................................................ 68
4.2.1 案例：解方程（P0110）..................................................................... 69
4.2.2 案例：網線主管（P0120）........................................................... 70
★ 4.2.3 案例：好鬥的牛（P0130）....................................................... 72
4.3 小結........................................................................................... 73
4.4 習題................................................................................... 73
第5章 遞歸和分治........................................................................................... 76
5.1 用遞歸進行枚舉......................................................................................... 76
5.1.1 案例：N皇后問題（P0230）........................................................ 76
5.1.2 案例：奧數問題（P0100）的遞歸解法 ...................................... 78
5.1.3 案例：全排列（P0240）........................................................... 79
5.2 解決用遞歸形式定義的問題 .................................................................. 81
5.2.1 案例：波蘭表達式（P0250）....................................................... 81
5.2.2 案例：繪製雪花曲線 .................................................................................. 83
5.3 用遞歸進行問題分解.......................................................................... 85
5.3.1 案例：上台階（P0260）...................................................................... 85
5.3.2 案例：算 24（P0270）........................................................................... 86
5.3.3 案例：放蘋果（P0280）............................................................... 88
5.3.4 案例：7 的倍數取法有多少種（P0290）...................................................... 89
5.4 分 治........................................................................................................ 90
5.4.1 案例：求排列的逆序數（P0300）.................................................................. 90
5.4.2 案例：漢諾塔問題（P0310）........................................................ 92
5.4.3 案例：快速冪................................................................................ 93
5.5 小結..................................................................................................... 94
5.6 習題.......................................................................................................... 95
第6章 棧和佇列 .............................................................................................. 97
6.1 棧....................................................................................................................... 97
6.1.1 案例：括弧配對（P0410）............................................ 97
6.1.2 案例：後序表達式求值（P0420）................................................... 98
★ 6.1.3 案例：中序表達式轉後序表達式（P0430）.................................. 100
★ 6.1.4 案例：四則運算表達式求值（P0440）..................................................... 102
6.1.5 案例：合法出棧序列（P0450）.............................................................. 103
★★ 6.2 棧和遞歸的關係...................................................................................... 105
6.3 隊 列........................................................................................................... 108
6.3.1 基本實現..................................................................................................... 108
6.3.2 循環佇列.............................................................................................. 109
6.3.3 Python中的佇列....................................................................................... 112
★★ 6.3.4 案例：滑動視窗（P0460）........................................................... 113
★ 6.3.5 案例：用兩個棧實現佇列 ........................................................... 115
6.4 用鍊表實現棧和佇列...................................................................................... 116
6.5 小結............................................................................................................. 116
6.6 習題................................................................................................................ 117
第7章 二叉樹................................................................................................ 119
7.1 二叉樹的概念................................................................................................... 119
7.2 二叉樹的性質............................................................................................. 122
7.3 二叉樹的表示............................................................................................. 124
7.3.1 用類表示二叉樹............................................................................. 124
7.3.2 用列表表示二叉樹 ................................................................................... 124
7.3.3 完全二叉樹的表示 .......................................................................... 124
7.4 二叉樹的遍歷.............................................................................................. 125
7.4.1 二叉樹的前序遍歷、後序遍歷、中序遍歷和按層遍歷................ 125
★ 7.4.2 案例：文本縮進二叉樹（P0560）............................................................ 128
7.4.3 案例：根據二叉樹前序遍歷序列和中序序列建立樹（P0570）............. 130
★★★ 7.4.4 案例：根據後序表達式建立表達式樹（P0580）.................. 132
★ 7.4.5 生成器方式遍歷二叉樹 ................................................................ 134
★ 7.4.6 非遞歸方式遍歷二叉樹 ............................................................... 134
★★ 7.5 線索二叉樹............................................................................................ 135
7.6 堆.............................................................................................................. 140
7.6.1 堆的概念............................................................................................... 140
7.6.2 堆的操作................................................................................................... 141
7.6.3 建堆.......................................................................................................... 143
7.6.4 堆的實現和優先佇列 ................................................................................ 144
7.6.5 Python中的堆................................................................................................. 146
7.7 哈夫曼樹............................................................................................................ 147
7.7.1 哈夫曼樹的概念和構造............................................................................... 147
7.7.2 案例：柵欄修補（P0590）........................................................ 148
7.7.3 哈夫曼編碼........................................................................................ 149
7.8 小結................................................................................................................. 152
7.9 習題........................................................................................................... 153
第 8章 樹、森林和並查集.............................................................................. 156
8.1 樹的概念 ................................................................................................... 156
8.2 樹的實現.................................................................................................... 157
8.2.1 直觀表示法................................................................................................... 157
8.2.2 案例：括弧嵌套樹（P0740）................................................................. 158
8.2.3 兒子-兄弟表示法....................................................................................... 159
8.2.4 案例：樹轉兒子-兄弟樹（P0750）.................................................... 160
8.2.5 父結點表示法................................................................................................ 162
8.3 森林................................................................................................................... 162
8.4 並查集............................................................................................................... 163
8.4.1 並查集的概念和用途 ............................................................................... 163
8.4.2 案例：疑似病人（P0760）................................................................ 165
8.5 小結................................................................................................................. 167
8.6 習題.................................................................................................................... 168
第 9章 字元串................................................................................................ 170
9.1 字元串的編碼................................................................................................. 170
9.2 字元串的實現.................................................................................................... 171
9.3 字元串的匹配算法...................................................................................... 173
9.3.1 暴力匹配算法............................................................................................... 173
★★ 9.3.2 KMP字元串匹配算法......................................................................... 174
9.4 小結.......................................................................................................... 180
9.5 習題.............................................................................................................. 180
第 10章 動態規劃 .......................................................................................... 181
10.1 什麼是動態規劃............................................................................................ 181
10.2 動態規劃解題的一般思路................................................................. 186
10.3 案例：簡單背包問題（P0880）.......................................................... 187
★★ 10.4 案例：不簡單的出棧序列統計（P0890）............................................... 190
★ 10.5 案例：最長上升子序列（P0900）................................................... 191
★★ 10.6 案例：最長公共子序列（P0910）............................................... 192
10.7 小結.............................................................................................................. 194
10.8 習題.......................................................................................................... 195
第 11章 圖的遍歷和搜尋 ............................................................................... 197
11.1 圖的定義和術語............................................................... 197
11.2 圖的表示............................................................................................ 199
11.2.1 鄰接矩陣............................................................................................. 199
11.2.2 鄰接表........................................................................................................ 200
11.2.3 鄰接表和鄰接矩陣的比較 .................................................................... 201
11.3 圖的遍歷........................................................................................................ 201
11.3.1 深度優先遍歷.............................................................................................. 202
11.3.2 案例：輸出無向圖深度優先遍歷序列（P1020）..................... 203
11.3.3 案例：城堡的房間（P1030）............................................................ 206
11.3.4 案例：判斷無向圖是否連通及是否有迴路（P1040）.............................. 208
11.3.5 廣度優先遍歷............................................................................................... 210
11.4 圖的搜尋................................................................................................ 212
11.4.1 概述.............................................................................................................. 212
11.4.2 深度優先搜尋............................................................................................... 214
11.4.3 案例：走迷宮之一（P1050）................................................. 218
11.4.4 案例：走迷宮之二（P1060）.................................................................... 219
11.4.5 案例：走迷宮之三（P1070）.............................................................. 220
11.4.6 廣度優先搜尋........................................................................................... 221
11.4.7 案例：抓住那頭牛（P1080）......................................................................... 222
11.4.8 案例：“走迷宮之三”的廣度優先搜尋解法（P1070）.................................. 224
★★ 11.4.9 案例：拯救行動（P1100）................................................................. 225
11.4.10 深度優先搜尋和廣度優先搜尋的選擇.................................................... 228
11.5 小結.................................................................................................................. 229
11.6 習題............................................................................................................ 229
第 12章 圖論基礎套用算法............................................................................ 233
12.1 最短路............................................................................................ 233
12.1.1 單源最短路問題的Dijkstra算法......................................................... 233
12.1.2 案例： 簡單的糖果分配 （P1220）........................................................ 237
★ 12.1.3 求每對頂點之間最短路的Floyd算法 ............................................... 240
★ 12.1.4 案例: 奶牛比賽（P1230）......................................... 242
12.2 最小生成樹.......................................................................................... 243
12.2.1 概述.................................................................................... 243
★★ 12.2.2 最小生成樹的性質................................................................... 244
12.2.3 Prim算法..................................................................................... 245
12.2.4 Kruskal算法................................................................................ 247
★ 12.2.5 案例： 團結就是力量 （P1234）................................................. 248
★★ 12.2.6 案例：北極網路（P1240）............................................. 252
12.3 拓撲排序................................................................................................ 253
12.3.1 拓撲排序的定義和算法 ................................................................... 253
12.3.2 案例：火星人家族樹（P1250）........................................................ 254
★ 12.4 關鍵路徑............................................................................... 256
12.4.1 關鍵路徑的定義和算法 ....................................................................... 256
★★ 12.4.2 案例：火星大工程（P1260）.................................................................. 259
12.5 小結................................................................................................................. 261
12.6 習題......................................................................................... 262
第 13章 排序.................................................................................................. 265
13.1 插入排序........................................................................................................ 266
13.1.1 直接插入排序.......................................................................................... 266
13.1.2 折半插入排序............................................................................................ 269
13.1.3 希爾排序...................................................................................................... 269
13.2 選擇排序......................................................................................................... 270
13.2.1 簡單選擇排序...................................................................................... 270
13.2.2 堆排序......................................................................................................... 272
13.3 歸併排序.................................................................................................. 274
13.4 交換排序......................................................................................................... 277
13.4.1 冒泡排序...................................................................................................... 277
13.4.2 快速排序...................................................................................................... 278
13.5 分配排序................................................................................................ 282
13.5.1 桶排序....................................................................................................... 282
13.5.2 計數排序..................................................................................................... 283
13.5.3 基數排序............................................................................................... 284
★ 13.6 外排序 ............................................................................................... 287
13.6.1 置換——選擇排序 ................................................................................ 288
13.6.2 多路歸併和敗者樹 .......................................................................... 292
13.7 小結................................................................................................................ 296
13.8 習題........................................................................................................... 297
第 14章 查找.................................................................................................. 300
14.1 線性表查找................................................................................................... 300
14.1.1 順序查找..................................................................................................... 300
14.1.2 二分查找................................................................................................. 301
14.1.3 Python的二分查找庫bisect.................................................................... 303
14.1.4 分塊查找..................................................................................................... 305
14.2 樹表查找......................................................................................................... 306
14.2.1 二叉查找樹................................................................................................... 306
14.2.1.1 二叉查找樹插入結點 ...................................................................... 307
14.2.1.2 二叉查找樹刪除結點 ....................................................................... 308
14.2.1.3 二叉查找樹的實現及時間複雜度分析......................................... 310
★ 14.2.2 AVL樹（平衡二叉樹）................................................................... 315
★ 14.2.2.1 AVL樹插入結點...................................................................... 315
★★★ 14.2.2.2 AVL樹刪除結點.................................................................. 320
★ 14.2.3 紅黑樹 ................................................................................................... 323
★ 14.2.3.1 紅黑樹的定義和性質........................................................................ 323
★★ 14.2.3.2 在紅黑樹中插入結點............................................................... 325
★★★ 14.2.3.3 紅黑樹刪除結點................................................................ 327
★ 14.2.4 外存查找：B-樹和B+樹.......................................................................... 330
14.2.4.1 B-樹的定義................................................................................................. 331
14.2.4.2 B-樹的查找................................................................................................. 332
14.2.4.3 B-樹的插入操作......................................................................................... 333
14.2.4.4 B-樹的刪除操作......................................................................................... 334
14.2.4.5 B+樹......................................................................................... 337
14.2.4.6 B-樹、B+樹和紅黑樹對比........................................................................ 339
14.3 散列表............................................................................................................. 340
14.3.1 散列函式設計.................................................................................... 341
14.3.2 散列表的插入和衝突消解 ........................................................................ 343
14.3.4 散列表的刪除和查找 ................................................................................ 346
14.3.5 散列表的效率分析 ................................................................................. 347
★★ 14.3.6 Python中的散列表 ............................................................................. 348
14.3.6.1 Python的哈希函式........................................................................ 348
14.3.6.2 Python的散列表策略................................................................... 351
14.4 小結............................................................................................................... 352
14.5 習題................................................................................................................. 354
第 15章 貪心算法 .......................................................................................... 359
15.1 案例：聖誕老人的禮物（P1370）..................................................................... 359
15.2 案例：電影節（P1380）...................................................................................... 360
15.3 小結................................................................................................................ 362
15.4 習題...................................................................................................................362
附錄 北京大學線上程式評測平台OpenJudge使用說明 ................................ 364
參考文獻................................................................................................................... 366
本書特色
1.本書的知識覆蓋面更廣，尤其是算法部分。
2.本書內容和習題按難度明確分級，重難點突出
3.高標準的實踐性，本書95%的數據結構和算法提供了完整可運行的代碼，並且這些代碼幾乎都在具體的例題中。
4.本書的例題和編程習題均可在北京大學線上程式評測平台 OpenJudge（以下簡稱 OJ）上提交解題程式。該平台包含兩萬多道編程題，程式提交後會自動評判對錯。
5.配套資源豐富，本書附贈課程講義以及 120 多個精心編寫、風格簡潔優美的程式源碼。
6.作者結合多年講課經驗歸納整合成書
作者在北京大學講授“數據結構與算法”“程式設計實習”“Python程式設計”“ICPC大學生程式設計競賽實踐”等課程多年，曾擔任北京大學ACM國際大學生程式設計競賽隊教練10年。本書即是對這些課程教學經驗的歸納與整合。
7.線上服務，提供本書專屬讀者線上服務交流圈。
