數據結構與算法（C/C++語言實現）

郭煒，北京大學信息科學技術學院教師。曾擔任北京大學ACM大學生程序設計競賽隊教練9年。在中國大學MOOC獨立開設的《程序設計與算法》系列課程獲評國家精品在線開放課程。在華文慕課和另一教師合開的《程序設計實習》獲評國家精品在線開放課程。編著有《新標準C++程序設計》、 《Python程序設計基礎及實踐(慕課版)》、《新標準C++程序設計》、 《Python程序設計基礎及實踐(慕課版)》、《算法基礎與在線實踐》、《ACM國際大學生程序設計競賽亞洲區預選賽真題題解》 等教材。

目錄

 

 

第1章緒論1

1.1算法和算法分析1

1.1.1什麼是算法1

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

1.2數據結構7

1.2.1數據的邏輯結構7

1.2.2數據的存儲結構7

1.2.3數據結構上的操作8

小結8

習題9

第2章C++語言快速入門和溫故知新10

2.1從C到C++10

2.1.1文件名和頭文件10

2.1.2輸入/輸出11

2.1.3結構體名直接作為類型名12

2.1.4引用12

2.1.5const關鍵字13

2.1.6函數參數默認值14

2.1.7函數參數傳引用14

2.1.8函數重載15

2.1.9auto類型15

2.1.10基於範圍的for循環16

2.1.11動態內存分配16

2.1.12統一的初始化方式18

2.1.13Lambda表達式18

2.1.14小節習題19

2.2面向對象程序設計19

2.2.1類和對象的概念19

2.2.2this指針21

2.2.3類的靜態成員21

2.2.4類成員的可訪問範圍22

2.2.5構造函數24

2.2.6析構函數25

2.2.7運算符的重載27

2.2.8函數對象28

2.2.9小節習題28

2.3模板與泛型程序設計29

2.3.1函數模板30

2.3.2類模板32

2.3.3標準模板庫35

2.3.4小節習題42

第3章線性表44

3.1順序表44

3.1.1順序表的概念和操作44

3.1.2C++中的順序表46

3.2鏈表47

3.2.1單鏈表47

3.2.2循環單鏈表51

3.2.3雙鏈表51

3.2.4靜態鏈表55

3.2.5C++中的鏈表56

3.3順序表和鏈表的選擇56

小結57

習題57

第4章枚舉與二分法59

4.1枚舉59

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

4.1.2案例: 奧數問題(P0100)60

4.1.3案例: 特殊密碼鎖(P0090)62

4.2二分法64

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

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

小結68

習題68

第5章遞歸和分治70

5.1用遞歸進行枚舉71

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

5.1.2案例: 奧數問題(P0100)的遞歸解法73

5.1.3案例: 全排列(P0240)74

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

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

★5.2.2案例: 分形盒(P0255)78

5.3用遞歸進行問題分解79

5.3.1案例: 上臺階(P0260)79

5.3.2案例: 算24(P0270)81

5.3.3案例: 放蘋果(P0280)82

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

5.4分治84

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

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

5.4.3案例: 快速冪87

小結88

習題88

第6章棧和隊列90

6.1棧90

6.1.1棧的概念和C++中的棧90

6.1.2案例: 括號配對(P0410)90

6.1.3案例: 後序表達式求值(P0420)92

★6.1.4案例: 中序表達式轉後序表達式(P0430)93

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

6.1.6案例: 合法出棧序列(P0450)98

★★6.2棧和遞歸的關系99

6.3隊列102

6.3.1基本實現102

6.3.2循環隊列103

6.3.3C++中的隊列105

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

★6.3.5案例: 用兩個棧模擬一個隊列109

6.4用鏈表實現棧和隊列109

小結110

習題110

第7章二叉樹113

7.1二叉樹的概念113

7.2二叉樹的性質115

7.3二叉樹的表示117

7.3.1用類表示二叉樹117

7.3.2完全二叉樹的表示117

7.4二叉樹的遍歷118

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

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

★7.4.3案例: 求二叉樹的寬度(P0630)123

★★★7.4.4案例: 根據後序表達式建立表達式樹(P0580)124

★★7.4.5案例: 文本縮進二叉樹(P0560)126

★7.4.6非遞歸方式遍歷二叉樹127

★★7.5線索二叉樹129

7.6堆132

7.6.1堆的概念132

7.6.2堆的操作133

7.6.3建堆135

7.6.4堆的實現和優先隊列135

7.7哈夫曼樹138

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

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

7.7.3哈夫曼編碼140

小結143

習題143

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

8.1樹的概念146

8.2樹的實現147

8.2.1直觀表示法147

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

8.2.3兒子兄弟表示法149

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

8.2.5父結點表示法152

8.3森林152

8.4並查集153

8.4.1並查集的概念和用途153

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

小結157

習題157

第9章字符串159

9.1字符串的編碼159

9.2字符串的實現160

9.3字符串的匹配算法161

9.3.1暴力匹配算法161

★★9.3.2KMP字符串匹配算法162

小結166

習題166

第10章動態規劃168

10.1什麼是動態規劃168

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

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

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

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

★★10.6案例: 最長公共子序列(P0910)179

小結181

習題181

第11章圖的遍歷和搜索183

11.1圖的定義和術語183

11.2圖的表示185

11.2.1鄰接矩陣185

11.2.2鄰接表186

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

11.3圖的遍歷187

11.3.1深度優先遍歷187

11.3.2案例: 深度優先遍歷一個無向圖(P1020)189

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

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

11.3.5廣度優先遍歷196

11.4圖的搜索198

11.4.1概述198

11.4.2深度優先搜索200

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

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

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

11.4.6廣度優先搜索206

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

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

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

11.5深搜和廣搜的選擇213

小結213

習題214

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

12.1最短路217

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

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

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

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

12.2最小生成樹226

12.2.1概述226

12.2.2最小生成樹的性質228

12.2.3Prim算法229

12.2.4Kruskal算法231

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

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

12.3拓撲排序237

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

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

★12.4關鍵路徑240

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

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

小結245

習題245

第13章排序248

13.1插入排序249

13.1.1直接插入排序249

13.1.2折半插入排序251

13.1.3希爾排序252

13.2選擇排序253

13.2.1簡單選擇排序253

13.2.2堆排序254

13.3歸並排序256

13.4交換排序259

13.4.1冒泡排序260

13.4.2快速排序261

13.5分配排序264

13.5.1桶排序264

13.5.2計數排序266

13.5.3基數排序267

★13.6外排序269

13.6.1置換選擇排序270

13.6.2多路歸並和敗者樹274

小結278

習題279

第14章查找281

14.1線性表查找281

14.1.1順序查找281

14.1.2二分查找282

14.1.3分塊查找285

14.2樹表查找286

14.2.1二叉查找樹286

★14.2.2平衡二叉樹(AVL樹)294

★14.2.3紅黑樹302

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

14.2.5C++中的二叉查找樹317

14.3散列表321

14.3.1散列函數設計322

14.3.2散列表的插入和沖突消解324

14.3.3散列表的刪除和查找327

14.3.4散列表的效率分析328

14.3.5C++中的散列表329

小結329

習題331

第15章貪心算法335

15.1案例: 聖誕老人的禮物(P1370)335

15.2案例: 電影節(P1380)336

小結338

習題338

第16章數組和矩陣340

16.1數組340

16.2特殊矩陣的壓縮存儲342

小結344

習題344

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

參考文獻347