數據結構基礎及實踐

目錄

第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.5迭代器22

第3章線性表25

3.1順序表25

3.1.1順序表的概念和操作25

3.1.2Java中的順序表28

3.2鏈表28

3.2.1單鏈表29

3.2.2循環單鏈表32

3.2.3雙鏈表33

3.2.4靜態鏈表36

★★3.2.5Java中的鏈表37

3.3順序表和鏈表的選擇39

小結40

習題40

第4章數組和矩陣42

4.1數組42

4.2特殊矩陣的壓縮存儲45

4.3小結47

4.4習題47

第5章遞歸和分治49

5.1用遞歸進行枚舉50

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

5.1.2案例: 全排列(P0240)52

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

5.2.1案例： 波蘭表達式(P0250)55

★★5.2.2案例： 繪制雪花曲線56

5.3用遞歸進行問題分解58

5.3.1案例: 上臺階(P0260)58

5.3.2案例： 數字三角形(P0265)60

5.3.3案例: 算24(P0270)61

5.4分治63

5.4.1案例: 漢諾塔問題(P0310)63

5.4.2案例： 快速冪64

小結65

習題65

第6章棧和隊列67

6.1棧67

6.1.1棧的概念和Java中的棧67

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

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

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

6.1.5案例: 合法出棧序列(P0450)73

★★6.2棧和遞歸的關系75

6.3隊列76

6.3.1基本實現76

6.3.2循環隊列77

6.3.3Java中的隊列80

★6.3.4案例: 用兩個棧模擬一個隊列81

★★6.3.5案例: 滑動窗口(P0460)82

6.4用鏈表實現棧和隊列84

小結84

習題85

第7章二叉樹87

7.1二叉樹的概念87

7.2二叉樹的性質89

7.3二叉樹的表示91

7.3.1用類表示二叉樹91

7.3.2完全二叉樹的表示92

7.4二叉樹的遍歷92

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

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

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

7.4.4案例： 擴展二叉樹 (P0700)99

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

★7.5線索二叉樹101

7.6堆104

7.6.1堆的概念104

7.6.2堆的操作105

7.6.3建堆107

7.6.4堆的實現和優先隊列107

7.7哈夫曼樹110

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

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

7.7.3哈夫曼編碼113

小結115

習題116

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

8.1樹的概念119

8.2樹的實現120

8.2.1樹的直觀表示法120

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

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

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

8.2.5樹的父結點表示法125

8.3森林125

8.4並查集126

8.4.1並查集的概念和用途126

8.4.2案例: The Suspects——疑似病人(P0760)128

小結130

習題130

第9章字符串132

9.1字符串的編碼132

9.2字符串的實現133

9.3字符串的匹配算法134

9.3.1暴力匹配算法134

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

小結140

習題140

第10章圖的遍歷和搜索142

10.1圖的定義和術語142

10.2圖的表示144

10.2.1鄰接矩陣144

10.2.2鄰接表145

10.2.3鄰接表和鄰接矩陣的對比146

10.3圖的遍歷146

10.3.1深度優先遍歷146

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

10.3.3案例: 城堡的房間(P1030)151

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

10.3.5廣度優先遍歷155

10.4圖的搜索157

10.4.1概述157

10.4.2深度優先搜索159

10.4.3案例: 走迷宮之一(P1050)162

10.4.4案例: 走迷宮之二(P1060)164

10.4.5案例: 走迷宮之三(P1070)164

10.4.6廣度優先搜索166

10.4.7案例: 抓住那頭牛(P1080)166

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

★★10.4.9案例: 拯救行動(P1100)170

10.5深搜和廣搜的選擇172

小結172

習題173

第11章圖論基礎應用算法176

11.1最短路176

11.1.1單源最短路問題的Dijkstra算法176

11.1.2案例: 簡單的糖果分配(P1220)178

★11.1.3求每對頂點之間最短路的Floyd算法182

★11.1.4案例: 奶牛比賽(P1230)184

11.2最小生成樹185

11.2.1概述185

11.2.2最小生成樹的性質187

11.2.3Prim算法189

11.2.4Kruskal算法190

★11.2.5案例: 團結真的就是力量(P1235)192

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

11.3拓撲排序197

11.3.1拓撲排序的定義和算法197

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

★11.4關鍵路徑200

11.4.1關鍵路徑的定義和算法200

★★11.4.2案例: 火星大工程(P1260)203

小結205

習題206

第12章排序208

12.1插入排序209

12.1.1直接插入排序209

12.1.2折半插入排序211

12.1.3希爾排序212

12.2選擇排序213

12.2.1簡單選擇排序213

12.2.2堆排序215

12.3歸並排序217

12.4交換排序220

12.4.1冒泡排序220

12.4.2快速排序222

12.5分配排序226

12.5.1桶排序226

12.5.2計數排序227

12.5.3基數排序228

★12.6外排序231

12.6.1置換選擇排序231

12.6.2多路歸並和敗者樹235

小結240

習題240

第13章查找243

13.1線性表查找243

13.1.1順序查找243

13.1.2二分查找244

13.1.3分塊查找250

13.2樹表查找251

13.2.1二叉查找樹251

★13.2.2平衡二叉樹(AVL樹)259

★13.2.3紅黑樹264

★13.2.4外存查找: B樹和B+樹266

13.2.5Java中的二叉查找樹274

13.3散列表278

13.3.1散列函數設計279

13.3.2散列表的插入和沖突消解281

13.3.3散列表的刪除和查找283

13.3.4散列表的效率分析284

13.3.5Java中的散列表285

小結288

習題290

參考文獻294