數據結構（Java語言版）（第2版）（微課版）

王學軍，承德石油高等專科學校計算機與信息工程系教授，主授課程：C語言程序設計、數據結構、VB程序設計、計算方法、計算機基礎

目　錄

 

第 1章　緒論　1

1.1　數據結構的3種基本結構　1

1.1.1　線性結構　1

1.1.2　層次結構　3

1.1.3　網狀結構　4

1.2　數據結構研究的主要問題　6

1.3　算法及描述　7

1.3.1　算法與算法特性　7

1.3.2　算法表示　8

1.4　算法效率分析　10

習題　11

 

第 2章　Java語言基礎知識　13

2.1　實例引入　13

2.2　Java語言概述　14

2.3　面向對象程序設計簡述　14

2.3.1　面向對象程序設計的基本概念　15

2.3.2　面向對象程序設計的基本特征　15

2.4　Java語言基礎知識　16

2.4.1　數據類型　17

2.4.2　運算符　18

2.4.3　流程控制　18

2.4.4　數組　21

2.4.5　類與對象　23

2.4.6　類的封裝性　26

2.4.7　類的繼承性　27

2.4.8　類的多態性　27

2.4.9　抽象類和內部類　28

2.4.10　接口　29

2.4.11　包　29

2.4.12　異常處理　31

2.4.13　Java標準數據流　33

2.5　Java語言中的“指針”實現　35

2.6　JDK1.5新增特性　38

2.6.1　泛型　39

2.6.2　增強的集合遍歷結構　39

2.6.3　自動裝箱/拆箱　39

2.6.4　枚舉類型　40

2.6.5　靜態import　40

2.6.6　從終端讀取數據　41

2.6.7　格式化輸出　41

2.6.8　可變參數　41

習題　42

 

第3章　線性表　44

3.1　實例引入　44

3.2　線性表的概述　45

3.2.1　線性表的概念　45

3.2.2　線性表的存儲結構及操作　46

3.3　順序表的基本操作及實現　46

3.3.1　順序表的概述　46

3.3.2　順序表的基本操作及實現　47

3.4　鏈表的基本操作及實現　50

3.4.1　鏈表　50

3.4.2　鏈表的分類　52

3.4.3　單鏈表的基本運算及實現　53

3.4.4　其他形式的鏈表的相關運算　54

3.4.5　算法實例　55

3.5　線性表的應用　56

3.5.1　順序表的連接　56

3.5.2　字符串的逆轉算法　57

習題　60

 

第4章　棧和隊列　61

4.1　實例引入　61

4.2　棧的相關概述　62

4.2.1　棧的定義　62

4.2.2　棧的相關概念　62

4.2.3　棧的操作過程　62

4.2.4　棧的存儲結構　64

4.3　用數組實現順序棧及操作　65

4.4　用類實現鏈式棧及相應操作　67

4.5　隊列的相關概述　70

4.5.1　隊列的定義　70

4.5.2　隊列的相關概念　70

4.5.3　隊列的存儲結構　70

4.6　用數組實現順序隊列及相應操作　71

4.7　用類實現鏈隊列及相應操作　74

4.8　棧和隊列的實例應用　76

習題　81

 

第5章　數組和廣義表　82

5.1　實例引入　82

5.2　數組　83

5.2.1　數組的基本概念　83

5.2.2　一維數組　84

5.2.3　二維數組　84

5.3　特殊矩陣　88

5.3.1　對稱矩陣　89

5.3.2　三角矩陣　90

5.3.3　對角矩陣　91

5.4　稀疏矩陣　91

*5.5　廣義表　98

5.5.1　廣義表的概念　98

5.5.2　廣義表的存儲結構　100

習題　100

 

第6章　串　102

6.1　實例引入　102

6.2　串的概述　103

6.3　串的順序存儲結構　104

6.3.1　通過String類處理串　104

6.3.2　通過StringBuffer類處理串　106

6.4　串的鏈式存儲結構　108

6.4.1　鏈串的實現　108

6.4.2　鏈串基本算法　109

習題　111

 

第7章　樹與二叉樹　113

7.1　實例引入　113

7.2　樹　114

7.2.1　樹的定義　114

7.2.2　樹的表示方法　115

7.2.3　樹的抽象數據類型　116

7.2.4　樹的存儲結構　117

7.3　二叉樹　119

7.3.1　二叉樹的定義　119

7.3.2　二叉樹的性質　120

7.3.3　二叉樹的抽象數據類型　122

7.3.4　二叉樹的存儲結構　122

7.4　二叉樹的節點類及二叉樹類　124

7.4.1　二叉樹節點類　124

7.4.2　二叉樹類　125

7.5　二叉樹的遍歷　126

7.5.1　二叉樹遍歷算法　126

7.5.2　二叉樹遍歷算法的實現　127

7.5.3　非遞歸的二叉樹遍歷算法　129

7.5.4　二叉樹遍歷的應用　130

7.6　線索二叉樹　131

7.6.1　線索二叉樹的定義　132

7.6.2　線索二叉樹的存儲結構　132

7.6.3　遍歷線索二叉樹　133

7.6.4　構造中序線索二叉樹　134

7.7　樹和森林　135

7.7.1　樹、森林與二叉樹的轉換　135

7.7.2　樹和森林的遍歷　137

7.8　樹的應用　138

7.8.1　二叉排序樹　138

7.8.2　哈夫曼樹和哈夫曼編碼　144

*7.8.3　判定樹　152

習題　154

 

第8章　圖　156

8.1　實例引入　156

8.2　圖的基本概念　157

8.2.1　圖的定義　157

8.2.2　圖的相關概念　159

8.3　圖的存儲結構　162

8.3.1　鄰接矩陣　162

8.3.2　鄰接表　164

8.4　圖的遍歷　165

8.4.1　深度優先搜索遍歷　165

8.4.2　廣度優先搜索遍歷　169

8.5　生成樹和**小生成樹　173

8.5.1　生成樹　173

8.5.2　Kruskal算法　174

8.5.3　Prim算法　175

8.6　**短路徑問題　177

8.7　拓撲排序　183

8.7.1　有向無環圖　183

8.7.2　拓撲排序　183

8.8　AOE網與關鍵路徑　187

8.8.1　AOE網　187

8.8.2　關鍵路徑　187

8.9　綜合示例　191

習題　200

 

第9章　查找　203

9.1　實例引入　203

9.2　基本概念與術語　205

9.2.1　查找的概念　205

9.2.2　查找方法　205

9.3　順序查找法　205

9.4　折半查找法　207

9.5　二叉排序樹法　209

9.6　哈希查找法　213

9.6.1　哈希查找概念　214

9.6.2　哈希函數　215

9.6.3　沖突解決方法　217

9.7　應用實例　219

習題　222

 

第 10章　排序　224

10.1　實例引入　224

10.2　排序的概念　225

10.3　排序的分類　225

10.3.1　按照存儲交換分類　225

10.3.2　按照內部排序的過程分類　226

10.3.3　按照排序的穩定性分類　226

10.4　插入排序　226

10.4.1　直接插入排序　226

10.4.2　希爾排序　228

10.5　交換排序　230

10.5.1　冒泡排序　230

10.5.2　快速排序　231

10.6　選擇排序　233

10.6.1　直接選擇排序　233

10.6.2　堆排序　234

10.7　其他排序　236

10.7.1　歸並排序　237

10.7.2　基數排序　238

10.8　排序的工程應用舉例　240

習題　242