數據結構

“數據結構”是計算機科學及相關學科的一門核心專業基礎課，主要討論各種數據結構在計算機中的存儲表示及算法實現，是一門集技術性、理論性和實踐性於一體的課程。本書綜合了諸多院校的課程教學大綱以及教育部2018年考研大綱中《計算機學科專業基礎綜合考試大綱》進行編寫，書中所有算法描述均採用標準C語言。教材內容安排合理，難易程度適中，講解深入淺出。每部分內容都配備有對應的程序實例和豐富的習題，可有效增強讀者對經典算法的理解和運用能力。全書共9章，內容包括緒論、線性表、棧和隊列、串、數組和廣義表、樹和二叉樹、圖、查找、排序。

本書主要面向本科及大中專計算機及相關專業的在校學生和具有C語言程序設計基礎的數據結構自學者，既可作為高校數據結構課程的教材，又可供從事軟件設計和開發的技術人員參考。 ^[2] 

第1章　緒論 1

1.1　什麼是數據結構 1

1.2　數據結構的概念及有關術語 1

1.3　算法和算法分析 5

習題 7

第2章　線性表 9

2.1　線性表的定義 9

2.2　線性表的基本運算 9

2.3　順序存儲結構線性表 10

2.3.1　線性表的順序存儲結構 10

2.3.2　順序存儲結構線性表的基本運算 11

2.3.3　順序存儲結構線性表的應用 15

2.4　鏈式存儲結構線性表 20

2.4.1　單鏈表 20

2.4.2　循環鏈表 28

2.4.3　雙向鏈表 29

2.4.4　靜態鏈表 30

2.4.5　鏈式存儲結構線性表的應用 31

2.5　小結 38

習題 38

第3章　棧和隊列 42

3.1　棧 42

3.1.1　棧的定義及基本運算 42

3.1.2　順序存儲結構棧的基本運算 42

3.1.3　鏈式存儲結構棧的基本運算 45

3.1.4　棧的應用實例 47

3.1.5　棧與遞歸 48

3.2　隊列 50

3.2.1　隊列的定義及基本運算 50

3.2.2　順序存儲結構隊列的基本運算 50

3.2.3　鏈式存儲結構隊列的基本運算 53

3.2.4　隊列的應用 55

3.3　小結 57

習題 58

第4章　串 61

4.1　串的概念及基本運算 61

4.1.1　串的基本概念 61

4.1.2　串的基本運算 62

4.2　順序存儲結構串的運算 63

4.2.1　串的定長順序存儲結構 63

4.2.2　定長順序存儲結構串的基本運算 64

4.3　串的堆分配存儲結構及其運算 66

4.3.1　串的堆分配存儲結構 66

4.3.2　堆分配存儲結構串的運算 66

4.4　串的鏈式存儲結構及基本運算 68

4.4.1　串的鏈式存儲結構 68

4.4.2　鏈串的基本運算 69

4.5　串的模式匹配 70

4.5.1　簡單模式匹配算法——BF算法 70

4.5.2　無回溯的模式匹配算法——KMP算法 72

*4.5.3　next函數的改進 77

4.6　小結 79

習題 79

第5章　數組和廣義表 81

5.1　數組 81

5.1.1　數組的定義及邏輯結構 81

5.1.2　數組的存儲結構 83

5.1.3　特殊矩陣的壓縮存儲 84

5.1.4　數組應用舉例 88

5.2　廣義表 91

5.2.1　廣義表的定義 91

5.2.2　廣義表的存儲結構 93

5.2.3　廣義表基本操作實現 94

5.2.4　廣義表應用舉例 97

5.3　小結 98

習題 99

第6章　樹和二叉樹 102

6.1　樹的定義及有關術語 102

6.1.1　樹的定義 102

6.1.2　常用術語 102

6.2　二叉樹 103

6.2.1　二叉樹的定義 103

6.2.2　二叉樹的性質 105

6.2.3　二叉樹的存儲結構 105

6.2.4　二叉樹的遍歷 107

6.2.5　線索二叉樹 113

6.2.6　哈夫曼樹 117

6.3　樹和森林 122

6.3.1　樹的存儲結構 122

6.3.2　樹或森林與二叉樹的轉換 124

6.3.3　樹和森林的遍歷 125

6.4　小結 126

習題 126

第7章　圖 130

7.1　圖的定義及有關術語 130

7.2　圖的存儲結構 134

7.2.1　鄰接矩陣 134

7.2.2　鄰接表 137

7.2.3　十字鏈表 139

*7.2.4　鄰接多重表 141

7.3　圖的遍歷 143

7.3.1　深度優先搜索 143

7.3.2　廣度優先搜索 145

7.3.3　圖的連通性 148

7.4　最小生成樹 150

7.4.1　普里姆算法 150

7.4.2　克魯斯卡爾算法 153

7.5　有向無環圖及其應用 156

7.5.1　拓撲排序 156

7.5.2　關鍵路徑 161

7.6　最短路徑 166

7.6.1　單源最短路徑 166

7.6.2　每一對頂點之間的最短路徑 169

7.7　圖的應用實例 172

7.8　小結 174

習題 175

第8章　查找 180

8.1 查找的有關概念 180

8.2　線性表的查找 181

8.2.1　順序查找 181

8.2.2　二分查找 182

8.2.3　分塊查找 184

8.3　樹表的查找 185

8.3.1　二叉排序樹 185

8.3.2　平衡二叉樹 190

8.3.3　B-樹 193

8.3.4　B+樹 196

8.4　哈希查找 197

8.4.1　哈希表的概念及哈希函數的構造 197

8.4.2　哈希表的建立 199

8.4.3　衝突的處理方法 199

8.4.4　哈希查找的實現 201

8.5　小結 202

習題 203

第9章　排序 206

9.1　排序的有關概念 206

9.2　插入排序 207

9.2.1　直接插入排序 207

9.2.2　折半插入排序 208

9.2.3　希爾排序 209

9.3　交換排序 211

9.3.1　冒泡排序 211

9.3.2　快速排序 212

9.4　選擇排序 214

9.4.1　簡單選擇排序 214

9.4.2　堆排序 216

9.5　歸併排序 219

9.6　基數排序 221

9.7　多關鍵字排序 223

9.8　小結 224

習題 225

參考文獻 229 ^[2]