數據結構

本書是針對高職高專院校計算機專業和相關專業的數據結構課程的特點而編寫的教材。

本書根據教學大綱所規定的內容，詳細介紹了數據結構的基本概念、基本結構和演演算法等重要內容，每章之後配有豐富的練習題目，以利於讀者理解知識內容和適應考試。

本書由長期從事數據結構教學工作的高校計算機專業教師編寫。全書通俗易懂、重點突出、概念表達嚴謹、知識結構邏輯性強，既便於教學又便於自學。

本書可以作為高職高專院校學生學習數據結構的教材或其他人員的自學教材。

第1章緒論 1

1.1什麼是數據結構 1

1.2基本概念和術語 2

1.3運算、演演算法和演演算法分析 3

1.3.1運算 4

1.3.2演演算法及其描述 4

1.3.3演演算法分析和演演算法複雜度 4

1.4習題 5

第2章線性表 8

2.1線性表的定義和基本運算 8

2.2線性表的順序存儲結構 9

2.2.1線性表順序存儲結構的概念 9

2.2.2線性表順序存儲的實現 10

2.3線性表的鏈式存儲結構 11

2.3.1單鏈表 12

2.3.2循環鏈表 15

2.3.3雙向鏈表 15

2.4鏈表的上機實習 17

2.4.1實習1 17

2.4.2實習2 21

2.4.3實習3 21

2.5習題 22

第3章棧和隊列 29

3.1棧 29

3.1.1棧的定義 29

3.1.2棧的存儲結構及其基本運算的實現 30

3.2隊列 32

3.2.1隊列的定義 33

3.2.2隊列的基本運算 33

3.2.3隊列的存儲結構及其基本運算的實現 34

3.3棧和隊列上機實習 38

3.3.1實習1 38

3.3.2實習2 39

3.3.3實習3 39

3.3.4實習4 40

3.4習題 40

第4章數組和串 47

4.1數組 47

4.1.1數組的概念和運算 47

4.1.2數組的順序存儲和訪問 48

4.1.3矩陣的壓縮存儲 49

4.2串 55

4.2.1串的基本概念 56

4.2.2串的基本運算 56

4.2.3串的存儲結構 57

4.3上機實習 63

4.3.1實習1 63

4.3.2實習2 65

4.4習題 66

第5章樹 69

5.1樹 69

5.1.1樹的基本概念 69

5.1.2樹的表示 71

5.1.3樹的基本運算 71

5.2二叉樹 72

5.2.1二叉樹的概念 72

5.2.2二叉樹的性質 75

5.2.3二叉樹的存儲結構 77

5.2.4二叉樹的遍歷 79

5.2.5哈夫曼樹和哈夫曼編碼 83

5.3樹和森林 87

5.3.1樹的存儲結構 88

5.3.2樹、森林與二叉樹的轉換 91

5.3.3樹和森林的遍歷 93

5.4上機實習 94

5.4.1實習1 94

5.4.2實習2 96

5.5習題 99

第6章圖 104

6.1圖的定義和術語 104

6.1.1圖的定義 104

6.1.2圖的相關術語 105

6.2圖的基本操作 106

6.3圖的存儲表示 107

6.3.1圖的鄰接矩陣 107

6.3.2鄰接表 109

6.4圖的遍歷 110

6.4.1深度優先搜索 111

6.4.2廣度優先搜索 112

6.5生成樹和最小生成樹 113

6.5.1生成樹 113

6.5.2最小生成樹 113

6.6習題 115

第7章內部排序 118

7.1排序概述 118

7.1.1排序的定義 118

7.1.2穩定排序與非穩定排序 119

7.1.3內部排序與外部排序 119

7.1.4排序記錄的存儲方式 119

7.2插入排序 120

7.2.1直接插入排序 120

7.2.2折半插入排序 121

7.2.3表插入排序 122

7.2.4希爾排序 125

7.3快速排序 127

7.3.1起泡排序 127

7.3.2快速排序方法 128

7.4選擇排序 130

7.4.1簡單選擇排序 131

7.4.2堆排序 131

7.5基數排序 135

7.6各種內部排序方法的比較 138

7.7上機實習 139

7.7.1實習1 139

7.7.2實習2 141

7.8習題 144

第8章查找 150

8.1查找的基本概念 150

8.2線性表的查找 152

8.2.1順序查找 152

8.2.2二分查找 153

8.2.3分塊查找 155

8.3樹結構的查找 157

8.3.1二叉排序樹 157

8.3.2平衡二叉樹 164

8.3.3B－樹 172

8.4散列技術 177

8.4.1散列表 177

8.4.2散列函數的構造方法 178

8.4.3處理衝突的方法 180

8.4.4散列表的查找 182

8.4.5散列技術性能分析 183

8.5上機實習 185

8.5.1實習1 185

8.5.2實習2 187

8.5.3實習3 189

8.6習題 190

第9章文件 193

9.1文件的基本概念 193

9.2順序文件 195

9.3索引文件 196

9.3.1索引文件的特點和術語 196

9.3.2索引文件的存儲 197

9.3.3索引文件的檢索與修改 197

9.4索引順序文件 198

9.4.1ISAM文件 198

9.4.2VSAM文件 200

9.5散列文件 201

9.5.1散列文件的存儲 201

9.5.2散列文件的查找 201

9.5.3散列文件的刪除操作 202

9.6多關鍵字文件 202

9.6.1多重表文件的概念 202

9.6.2倒排文件 203

9.7習題 204

各章習題答案 209

參考文獻 213

數據結構(C語言)

目錄