數據結構（Java版）

目錄

 

 

配套資源

第1章緒論1

1.1認識數據結構1

1.1.1圖書館書目自動檢索系統1

1.1.2人機對弈2

1.1.3比賽時間安排2

1.2基本概念和術語4

1.3算法與算法分析8

1.3.1算法的概念8

1.3.2算法的描述方式9

1.3.3算法評價標準11

1.3.4算法分析11

1.4“數據結構”課程的形成和發展14

課後練習15

 

第2章線性表16

2.1線性表的定義及邏輯結構16

2.1.1線性表的定義、概念16

2.1.2線性表的常用運算17

2.1.3線性表的ADT描述17

2.2線性表的順序存儲結構及算法17

2.2.1線性表的順序存儲結構17

2.2.2線性表的順序存儲算法18

2.3線性表的鏈式存儲結構及算法23

2.3.1線性表的鏈式存儲結構23

2.3.2線性表的鏈式存儲算法24

2.4線性表的應用40

2.4.1鏈表的合並40

2.4.2一元多項式的相加43

2.5順序表和鏈表的比較47

課後練習48第3章棧49

3.1棧的定義及邏輯定義49

3.1.1棧的定義49

3.1.2棧的常用運算50

3.1.3棧的ADT描述50

3.2棧的順序存儲結構及運算51

3.2.1棧的順序存儲結構51

3.2.2順序棧的操作52

3.2.3順序棧的例子55

3.3棧的鏈式存儲及運算56

3.3.1棧的鏈式存儲結構56

3.3.2鏈棧的操作57

3.3.3順序棧與鏈棧小結61

3.4兩棧共享62

3.5棧與遞歸67

3.5.1棧的舉例67

3.5.2遞歸69

3.6棧的應用71

3.6.1回文71

3.6.2表達式括號匹配72

3.6.3算術表達式求值74

課後練習83

 

第4章隊列84

4.1隊列的概念及特征84

4.1.1隊列的概念84

4.1.2隊列的特征84

4.1.3隊列的常用運算85

4.1.4隊列的ADT描述85

4.2隊列與計算機系統85

4.2.1解決主機與外部設備之間速度不匹配的問題85

4.2.2解決由多用戶引起的資源競爭問題86

4.3隊列的順序存儲結構與操作86

4.3.1隊列的順序存儲結構86

4.3.2順序隊列的操作87

4.3.3順序隊列的溢出及解決方法91

4.4循環隊列93

4.4.1循環隊列存儲及表示93

4.4.2循環隊列的操作94

4.5隊列的鏈式存儲結構與操作97

4.5.1隊列鏈式存儲結構97

4.5.2鏈隊列的兩種形式97

4.5.3鏈隊列的操作98

4.5.4循環隊列和鏈隊列的對比101

4.6隊列的應用102

4.6.1舞伴問題102

4.6.2小貓釣魚遊戲105

4.6.3劉謙魔術揭秘108

課後練習110

 

第5章數組、特殊矩陣111

5.1數組的邏輯結構及ADT描述111

5.1.1數組的概念111

5.1.2數組的邏輯結構111

5.1.3數組的操作112

5.1.4數組的ADT描述114

5.2數組的順序存儲結構及運算114

5.2.1二維數組的順序存儲114

5.2.2三維數組的順序存儲116

5.2.3n維數組的順序存儲116

5.2.4數組的順序存儲小結116

5.3特殊矩陣的壓縮存儲117

5.3.1對稱矩陣的壓縮存儲117

5.3.2三角矩陣的壓縮存儲118

5.3.3帶狀矩陣的壓縮存儲119

5.4稀疏矩陣的壓縮存儲120

5.4.1稀疏矩陣的定義120

5.4.2稀疏矩陣的存儲結構120

5.5線性結構小結121

課後練習122

 

第6章樹和二叉樹123

6.1樹的概念124

6.1.1樹的定義124

6.1.2樹的數據結構定義及ADT描述125

6.1.3樹的基本術語126

6.1.4樹的表示方法127

6.1.5樹的存儲結構129

6.2二叉樹131

6.2.1二叉樹的定義性質131

6.2.2二叉樹的存儲結構134

6.2.3二叉樹的遍歷141

6.2.4二叉樹的應用157

6.3樹、森林與二叉樹的關系172

6.3.1樹、森林與二叉樹的轉換172

6.3.2樹的遍歷174

課後練習175

 

第7章查找176

7.1查找的基本概念176

7.2靜態查找177

7.2.1順序查找177

7.2.2折半查找180

7.2.3分塊查找184

7.3動態查找188

7.3.1樹狀查找188

7.3.2散列查找196

課後練習202

 

第8章排序204

8.1排序的基本概念204

8.1.1排序204

8.1.2排序的分類204

8.1.3排序的特性205

8.1.4排序的時間開銷205

8.2排序算法205

8.2.1插入排序205

8.2.2交換排序211

8.2.3選擇排序219

8.2.4歸並排序225

8.2.5基數排序228

8.3排序算法比較229

課後練習230

 

第9章圖231

9.1圖的概念231

9.1.1圖的定義231

9.1.2圖的分類232

9.1.3圖的基本術語232

9.2圖的存儲235

9.2.1鄰接矩陣存儲結構236

9.2.2鄰接表存儲結構240

9.2.3圖存儲結構小結245

9.3圖的遍歷246

9.3.1深度優先搜索法246

9.3.2廣度優先搜索法248

9.4圖的應用254

9.4.1最小生成樹254

9.4.2最短路徑261

9.4.3拓撲排序262

課後練習265

 

參考文獻266