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

目錄

第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數據結構上的操作7

小結8

習題8

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

2.1接口和多態10

2.2內部類和內部接口12

2.3匿名類、Lambda表達式和函數式接口13

2.4泛型16

2.4.1泛型的概念和作用16

2.4.2泛型類、泛型接口和泛型函數17

2.4.3泛型數組22

★★2.4.4泛型的上下界22

★★2.5迭代器25

第3章線性表27

3.1順序表27

3.1.1順序表的概念和操作27

3.1.2Java中的順序表30

3.2鏈表30

3.2.1單鏈表31

3.2.2循環單鏈表34

3.2.3雙鏈表35

3.2.4靜態鏈表38

★★3.2.5Java中的鏈表39

3.3順序表和鏈表的選擇41

小結42

習題42

第4章枚舉與二分法44

4.1枚舉44

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

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

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

4.1.4案例: 假幣問題(P0080)49

4.2二分法51

4.2.1案例: 解方程(P0110)52

4.2.2案例: 網線主管(P0120)53

★4.2.3案例: 好鬥的牛(P0130)55

小結56

習題56

第5章遞歸和分治59

5.1用遞歸進行枚舉59

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

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

5.1.3案例: 全排列(P0240)63

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

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

★★5.2.2案例: 繪制雪花曲線66

5.3用遞歸進行問題分解69

5.3.1案例: 上臺階(P0260)69

5.3.2案例: 算24(P0270)70

5.3.3案例: 放蘋果(P0280)71

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

5.4分治73

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

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

5.4.3案例: 快速冪77

小結78

習題78

第6章棧和隊列80

6.1棧80

6.1.1棧的概念和Java中的棧80

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

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

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

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

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

★★6.2棧和遞歸的關系90

6.3隊列92

6.3.1基本實現93

6.3.2循環隊列93

6.3.3Java中的隊列96

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

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

6.4用鏈表實現棧和隊列100

小結101

習題101

第7章二叉樹103

7.1二叉樹的概念103

7.2二叉樹的性質105

7.3二叉樹的表示107

7.3.1用類表示二叉樹107

7.3.2完全二叉樹的表示108

7.4二叉樹的遍歷108

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

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

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

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

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

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

★★7.5線索二叉樹120

7.6堆125

7.6.1堆的概念125

7.6.2堆的操作125

7.6.3建堆127

7.6.4堆的實現和優先隊列128

7.7哈夫曼樹131

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

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

7.7.3哈夫曼編碼133

小結135

習題136

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

8.1樹的概念139

8.2樹的實現140

8.2.1樹的直觀表示法140

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

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

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

8.2.5樹的父結點表示法145

8.3森林145

8.4並查集146

8.4.1並查集的概念和用途146

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

小結150

習題150

第9章字符串152

9.1字符串的編碼152

9.2字符串的實現153

9.3字符串的匹配算法154

9.3.1暴力匹配算法154

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

小結160

習題160

第10章動態規劃162

10.1什麽是動態規劃162

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

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

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

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

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

小結176

習題176

第11章圖的遍歷和搜索178

11.1圖的定義和術語178

11.2圖的表示180

11.2.1鄰接矩陣180

11.2.2鄰接表181

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

11.3圖的遍歷182

11.3.1深度優先遍歷182

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

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

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

11.3.5廣度優先遍歷191

11.4圖的搜索193

11.4.1概述193

11.4.2深度優先搜索195

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

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

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

11.4.6廣度優先搜索202

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

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

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

11.5深搜和廣搜的選擇209

小結209

習題210

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

12.1最短路213

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

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

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

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

12.2最小生成樹223

12.2.1概述223

12.2.2最小生成樹的性質224

12.2.3Prim算法226

12.2.4Kruskal算法227

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

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

12.3拓撲排序234

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

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

★12.4關鍵路徑237

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

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

小結242

習題243

第13章排序245

13.1插入排序246

13.1.1直接插入排序246

13.1.2折半插入排序248

13.1.3希爾排序248

13.2選擇排序250

13.2.1簡單選擇排序250

13.2.2堆排序251

13.3歸並排序253

13.4交換排序256

13.4.1冒泡排序256

13.4.2快速排序258

13.5分配排序262

13.5.1桶排序262

13.5.2計數排序263

13.5.3基數排序264

★13.6外排序267

13.6.1置換選擇排序267

13.6.2多路歸並和敗者樹271

小結276

習題276

第14章查找279

14.1線性表查找279

14.1.1順序查找279

14.1.2二分查找280

14.1.3Java的二分查找函數282

14.1.4分塊查找283

14.2樹表查找284

14.2.1二叉查找樹284

★14.2.2平衡二叉樹292

★14.2.3紅黑樹300

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

14.2.5Java中的二叉查找樹315

14.3散列表319

14.3.1散列函數設計319

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

14.3.3散列表的刪除和查找324

14.3.4散列表的效率分析325

14.3.5Java中的散列表326

小結329

習題331

第15章貪心算法335

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

15.2案例: 電影節(P1380)337

小結338

習題339

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

參考文獻341