數據結構(C語言，慕課版)

目    錄 

第1章  緒論 1

1.1  數據結構的發展 1

1.2  數據結構的概念 2

1.2.1  數據結構研究的領域 3

1.2.2  數據結構研究的內容 5

1.2.3  數據 5

1.2.4  數據結構 6

1.2.5  數據類型 8

1.3  算法和算法分析 9

1.3.1  算法的概念 10

1.3.2  算法的復雜性分析 10

1.4  習題 13

第2章  線性表 16

2.1  線性表的類型定義 16

2.2  線性表的順序映像 19

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

2.2.2  順序存儲結構的特點 20

2.2.3  典型操作的算法實現 21

2.2.4  主要操作的算法分析 24

2.3  線性表的鏈式映像 25

2.3.1  線性鏈表的定義 25

2.3.2  線性鏈表的類型定義及典型操作 26

2.3.3  其他形式的鏈表 30

2.4  線性表實現方法的比較 37

2.4.1  順序表和鏈表的比較 37

2.4.2  線性鏈表定義的改進 38

2.5  一元多項式的表示及相加 40

2.6  習題 44

第3章  棧 49

3.1  棧的定義 49

3.1.1  棧的特點及定義 49

3.1.2  棧的抽象數據類型定義 50

3.2  棧的存儲表示及實現 51

3.2.1  棧的順序存儲表示 51

3.2.2  棧的鏈式存儲表示 52

3.3  棧的應用 53

3.3.1  數制轉換 53

3.3.2  括號匹配的檢驗 54

3.3.3  行編輯程序問題 55

3.3.4  迷宮求解問題 56

3.3.5  表達式求值 57

3.3.6  遞歸的實現 60

3.4  習題 63

第4章  隊列 65

4.1  隊列的定義 65

4.2  隊列類型的實現 66

4.2.1  隊列的順序存儲——循環隊列 67

4.2.2  隊列的鏈式存儲——鏈隊列 69

4.3  隊列的應用——離散事件模擬 70

4.4  習題 74

第5章  串 76

5.1  串類型的定義 76

5.1.1  串的基本概念 76

5.1.2  串的抽象數據類型定義 77

5.1.3  串與線性表的區別 79

5.2  串的表示和實現 80

5.2.1  串的定長順序存儲表示 80

5.2.2  串的堆分配存儲表示 81

5.2.3  串的塊鏈存儲表示 82

5.3  串的模式匹配算法 83

5.3.1  簡單匹配算法 83

5.3.2  KMP算法 86

5.4  串應用舉例 ——文本編輯 92

5.4.1  文本編輯概述 93

5.4.2  文本編輯程序 94

5.5  習題 94

第6章  數組 95

6.1  數組的基本概念 95

6.2  數組的順序存儲及實現 97

6.2.1  數組的存儲方式 97

6.2.2  數組的順序存儲表示和實現 98

6.3  矩陣的壓縮存儲 100

6.3.1  對稱矩陣的壓縮存儲 100

6.3.2  三角矩陣的壓縮存儲 101

6.3.3  對角矩陣的壓縮存儲 102

6.4  稀疏矩陣 103

6.4.1  稀疏矩陣的定義 103

6.4.2  稀疏矩陣的抽象數據類型定義 103

6.4.3  稀疏矩陣的壓縮存儲 104

6.5  習題 113

第7章  廣義表 115

7.1  廣義表的定義 115

7.2  廣義表的存儲結構 117

7.2.1  廣義表的頭尾鏈表存儲表示 117

7.2.2  廣義表的元素存儲表示 118

7.3  廣義表操作的實現 118

7.3.1  創建廣義表 118

7.3.2  求表的深度 120

7.3.3  廣義表的結點操作 121

7.3.4  刪除廣義表 122

7.3.5  求廣義表的長度 123

7.3.6  廣義表的復制 123

7.4  習題 125

第8章  樹 127

8.1  樹的類型定義和基本術語 127

8.1.1  樹的定義 127

8.1.2  樹的常用術語 130

8.1.3  線性結構與樹形結構的比較 131

8.2  樹和森林的存儲結構 131

8.2.1  樹的存儲結構 131

8.2.2  樹和森林的遍歷 134

8.3  習題 138

第9章  二叉樹 140

9.1  二叉樹的定義和性質 140

9.1.1  二叉樹的定義 140

9.1.2  兩類特殊的二叉樹 143

9.1.3  二叉樹的重要特性 143

9.2  二叉樹的存儲結構 144

9.2.1  二叉樹的順序存儲表示 144

9.2.2  二叉樹的鏈式存儲表示 145

9.3  二叉樹的遍歷與應用 146

9.3.1  二叉樹的三種遍歷算法 147

9.3.2  二叉樹遍歷算法的非遞歸描述 150

9.3.3  二叉樹遍歷算法的應用 153

9.4  線索二叉樹 158

9.4.1  線索二叉樹的定義 158

9.4.2  線索鏈表的遍歷 159

9.4.3  線索鏈表的建立 161

9.4.4  中序線索二叉樹中插入結點 162

9.4.5  線索二叉樹的優缺點 163

9.5  樹、森林和二叉樹 163

9.5.1  森林與二叉樹之間的轉換 163

9.5.2  森林與二叉樹轉換的操作 164

9.5.3  樹、森林的遍歷和二叉樹遍歷的對應關系 165

9.6  哈夫曼樹及其應用 166

9.6.1  哈夫曼樹 166

9.6.2  哈夫曼編碼 168

9.7  習題 172

第10章  圖 176

10.1  圖的基本概念 176

10.1.1  圖的定義和術語 176

10.1.2  圖的抽象數據類型定義 178

10.2  圖的存儲結構 180

10.2.1  鄰接矩陣(數組)表示法 180

10.2.2  鄰接表表示法 183

10.2.3  十字鏈表表示法 186

10.2.4  鄰接多重表表示法 187

10.3  圖的遍歷 189

10.3.1  深度優先搜索遍歷 189

10.3.2  廣度優先搜索遍歷 190

10.4  圖的連通性問題 192

10.4.1  無向圖的連通分量和生成樹 192

10.4.2  有向圖的強連通分量 194

10.4.3  最小生成樹 195

10.5  有向無環圖及其應用 200

10.5.1  拓撲排序 200

10.5.2  關鍵路徑 203

10.6  最短路徑 207

10.6.1  單源最短路徑 208

10.6.2  每一對頂點間的最短路徑 211

10.7  習題 213

第11章  查找 216

11.1  查找表 216

11.2  靜態查找表 218

11.2.1  順序表的查找 218

11.2.2  有序表的查找 220

11.2.3  索引順序表的查找 222

11.3  動態查找表 224

11.3.1  二叉排序樹 224

11.3.2  平衡二叉樹 229

11.3.3  B-樹 235

11.3.4  B+樹 243

11.4  哈希表 244

11.4.1  什麽是哈希表 244

11.4.2  哈希函數的構造方法 246

11.4.3  哈希表處理沖突的方法 248

11.4.4  哈希表的查找及分析 251

11.5  習題 255

第12章  內部排序 258

12.1  排序概述 258

12.1.1  排序的概念 258

12.1.2  排序方法的穩定性 259

12.1.3  內部排序和外部排序 259

12.1.4  內部排序的分類 259

12.2  插入排序 260

12.2.1  直接插入排序 260

12.2.2  折半插入排序 262

12.2.3  2-路插入排序 263

12.2.4  表插入排序 265

12.2.5  希爾排序 268

12.3  交換排序 269

12.3.1  起泡排序 270

12.3.2  快速排序 271

12.4  選擇排序 273

12.4.1  簡單選擇排序 273

12.4.2  堆排序 274

12.5  歸並排序 277

12.6  基數排序 279

12.6.1  多關鍵字排序 279

12.6.2  鏈式基數排序 281

12.7  各種內部排序方法的比較討論 283

12.8  習題 284

第13章  外部排序 286

13.1  外部排序的方法 286

13.2  歸並排序 287

13.2.1  2-路平衡歸並排序 287 

13.2.2  多段2-路歸並排序 288

13.2.3  多路平衡歸並排序 288

13.3  置換選擇排序 290

13.3.1  置換選擇排序的處理過程 291

13.3.2  置換選擇排序算法 291

13.4  習題 294

參考文獻 295