數據結構與算法（Python語言實現）

目錄CONTENTS

 

 

 

第1章緒論1

1.1算法和算法分析1

1.1.1什麽是算法1

1.1.2算法的時間復雜度及其表示法3

1.2數據結構6

1.2.1數據的邏輯結構6

1.2.2數據的存儲結構7

1.2.3數據結構上的操作8

小結8

習題8

第2章Python語言鞏固與提高10

2.1一些Python語言操作的時間復雜度10

2.2函數11

2.2.1lambda表達式11

2.2.2高階函數和閉包12

2.2.3global變量和nonlocal變量13

2.2.4函數參數的默認值14

★2.2.5生成器(電子文檔)14

2.3面向對象程序設計15

2.3.1類和對象15

2.3.2對象的比較18

2.3.3迭代器19

2.3.4類的特殊方法21

習題23

第3章線性表26

3.1順序表26

3.2鏈表29

3.2.1單鏈表29

3.2.2循環單鏈表33

3.2.3雙鏈表33

3.2.4靜態鏈表37

3.3順序表和鏈表的選擇37

小結38

習題39

第4章枚舉與二分法40

4.1枚舉40

4.1.1案例: 八皇後問題(P0070)40

4.1.2案例: 特殊密碼鎖(P0090)41

4.2二分法43

4.2.1案例: 網線主管(P0120)43

★4.2.2案例: 好鬥的牛(P0130)45

小結46

習題46

第5章遞歸和分治49

5.1用遞歸進行枚舉50

5.1.1案例: N皇後問題(P0230)50

5.1.2案例: 全排列(P0240)52

5.2解決用遞歸形式定義的問題54

5.2.1案例: 波蘭表達式(P0250)54

5.2.2案例: 繪制雪花曲線56

5.3用遞歸進行問題分解56

5.3.1案例: 上臺階(P0260)56

5.3.2案例: 算24(P0270)57

5.3.3案例: 7的倍數取法有多少種(P0290)58

5.4分治59

5.4.1案例: 求排列的逆序數(P0300)59

5.4.2案例: 漢諾塔問題(P0310)61

5.4.3案例: 快速冪62

小結63

習題63

第6章棧和隊列65

6.1棧65

6.1.1案例: 括號配對(P0410)65

6.1.2案例: 後序表達式求值(P0420)66

★6.1.3案例: 四則運算表達式求值(P0440)68

6.1.4案例: 合法出棧序列(P0450)69

★★6.2棧和遞歸的關系(電子文檔)71

6.3隊列71

6.3.1隊列的基本實現71

6.3.2循環隊列72

6.3.3Python語句自帶的隊列(電子文檔)75

★★6.3.4案例: 滑動窗口(P0460)75

6.4用鏈表實現棧和隊列77

小結77

習題78

第7章二叉樹80

7.1二叉樹的概念80

7.2二叉樹的性質82

7.3二叉樹的表示84

7.3.1用類表示二叉樹84

7.3.2用列表表示二叉樹85

7.3.3完全二叉樹的表示85

7.4二叉樹的遍歷86

7.4.1二叉樹的前序、後序、中序和按層次遍歷86

★7.4.2案例: 文本縮進二叉樹(P0560)88

7.4.3案例: 根據二叉樹前中序序列建樹(P0570)90

★★★7.4.4案例: 根據後序表達式建立表達式樹(P0580)(電子文檔)91

★7.4.5非遞歸方式遍歷二叉樹92

★★7.5線索二叉樹93

7.6堆96

7.6.1堆的概念96

7.6.2堆的操作97

7.6.3建堆99

7.6.4堆的實現和優先隊列99

7.6.5Python中的堆(電子文檔)102

7.7哈夫曼樹102

7.7.1哈夫曼樹的概念和構造102

7.7.2案例: 柵欄修補(P0590)103

7.7.3哈夫曼編碼104

小結107

習題108

第8章樹、森林和並查集111

8.1樹的概念111

8.2樹的實現112

8.2.1樹的直觀表示法112

8.2.2案例: 括號嵌套樹(P0740)113

8.2.3樹的兒子兄弟表示法114

8.2.4案例: 樹轉兒子兄弟樹(P0750)115

8.2.5樹的父結點表示法117

8.3森林117

8.4並查集118

8.4.1並查集的概念和用途118

8.4.2案例: The Suspects疑似病人(P0760)120

小結122

習題122

第9章字符串匹配124

9.1暴力匹配算法124

★★9.2KMP匹配算法125

小結130

習題130

第10章動態規劃132

10.1什麽是動態規劃132

10.2動態規劃解題的一般思路136

10.3案例: 簡單背包問題(P0880)138

★★10.4案例: 不簡單的出棧序列統計(P0890)140

★10.5案例: 最長上升子序列(P0900)142

★★10.6案例: 最長公共子序列(P0910)(電子文檔)143

小結144

習題144

第11章圖的遍歷和搜索146

11.1圖的定義和術語146

11.2圖的表示148

11.2.1鄰接矩陣148

11.2.2鄰接表149

11.2.3鄰接表和鄰接矩陣的對比150

11.3圖的遍歷151

11.3.1深度優先遍歷151

11.3.2案例: 輸出無向圖深度優先遍歷序列(P1020)152

11.3.3案例: 城堡的房間(P1030)155

11.3.4案例: 判斷無向圖是否連通及是否有迴路(P1040)156

11.3.5廣度優先遍歷158

11.4圖的搜索160

11.4.1概述160

11.4.2深度優先搜索162

11.4.3案例: 走迷宮之一(P1050)166

11.4.4案例: 走迷宮之二(P1060)167

11.4.5案例: 走迷宮之三(P1070)167

11.4.6廣度優先搜索168

11.4.7案例: 抓住那頭牛(P1080)169

11.4.8案例: “走迷宮之三”的廣搜解法(P1070)171

★★11.4.9案例: 拯救行動(P1100)172

11.5深搜和廣搜的選擇174

小結174

習題175

第12章圖論基礎應用算法178

12.1最短路178

12.1.1單源最短路問題的Dijkstra算法178

12.1.2案例: 簡單的糖果分配 (P1220)181

★12.1.3求每對頂點之間最短路的Floyd算法184

★12.1.4案例: 奶牛比賽 (P1230)186

12.2最小生成樹188

12.2.1概述188

★★12.2.2最小生成樹的性質189

12.2.3Prim算法190

12.2.4Kruskal算法192

★12.2.5案例: 團結真的就是力量(P1235)193

★★12.2.6案例: 北極網絡(P1240)196

12.3拓撲排序198

12.3.1拓撲排序的定義和算法198

12.3.2案例: 火星人家族樹 (P1250)199

★12.4關鍵路徑201

12.4.1關鍵路徑的定義和算法201

★★12.4.2案例: 火星大工程(P1260)204

小結206

習題206

第13章排序209

13.1插入排序210

13.1.1直接插入排序210

13.1.2折半插入排序213

13.1.3希爾排序213

13.2選擇排序214

13.2.1簡單選擇排序214

13.2.2堆排序215

13.3歸並排序217

13.4交換排序220

13.4.1冒泡排序220

13.4.2快速排序221

13.5分配排序224

13.5.1桶排序224

13.5.2計數排序(電子文檔)226

13.5.3基數排序226

★13.6外排序228

13.6.1置換選擇排序229

13.6.2多路歸並和敗者樹233

小結236

習題237

第14章查找239

14.1線性表查找239

14.1.1順序查找239

14.1.2二分查找240

14.1.3Python的二分查找庫bisect(電子文檔)242

14.1.4分塊查找242

14.2樹表查找243

14.2.1二叉查找樹244

★14.2.2平衡二叉樹251

★14.2.3紅黑樹257

★14.2.4外存查找: B樹和B+樹258

14.3哈希表268

14.3.1哈希函數設計268

14.3.2哈希表的插入和沖突消解271

14.3.3哈希表的刪除和查找274

14.3.4哈希表的效率分析275

★★14.3.5Python中的哈希表(電子文檔)276

小結276

習題278

附錄A北京大學在線程序評測平臺OpenJudge使用說明282

參考文獻284