數據結構與算法及其航空航天應用（C語言版）（項目式微課版）

趙學武，鄭州航空工業管理學院智能工程學院人工智能系副主任，近年來的主要研究方向為數據挖掘、機器學習、腦科學和大數據。

車葵，鄭州航空工業管理學院副教授，主要研究領域為軟件工程、信息安全。

趙妍，鄭州航空工業管理學院副教授，主要研究領域為知識發現與模式識別。

第 1 部分 數據結構

第 1 章 數據結構概述 2

11 數據結構的基本概念 2

111 什麼是數據結構 2

112 基本概念與術語 2

12 數據結構的內容 4

121 數據的邏輯結構 4

122 數據的物理結構 6

123 數據的運算 7

13 算法基礎 8

131 算法的概念 8

132 算法的特性 8

133 算法的評價 9

134 算法的復雜度 9

14 如何學習和運用數據結構與算法 12

15 習題 12

第 1 篇 線性結構

第 2 章 線性表 16

21 實例引入 16

211 合並兩個有序線性表 16

212 一元多項式的運算 16

213 約瑟夫環問題 16

214 簡單的管理系統 17

22 線性表的概念與基本操作 17

221 線性表的概念 17

222 線性表的基本操作 17

23 線性表的順序存儲及運算 18

231 順序表 18

232 順序表的基本運算 18

24 線性表的鏈式存儲及運算 24

241 單鏈表 24

242 循環鏈表 30

243 雙向鏈表 30

244 靜態鏈表 32

25 順序表與鏈表的比較 33

26 線性表的典型應用 33

261 應用實例一：合並有序線性表 33

262 應用實例二：一元多項式的運算 33

263 應用實例三：約瑟夫環問題 37

264 應用實例四：超市商品管理系統 38

27 航空航天應用實例分析與實現 39

271 航空售票系統 39

272 系統訂購機票 41

273 系統增加航線 42

274 系統刪除航線 42

275 系統退票 43

28 習題 43

第3 章 棧與隊列 46

31 實例引入 46

32 棧 47

321 棧的概念與基本運算 47

322 棧的順序存儲 48

323 棧的鏈式存儲 51

324 棧的典型應用 54

33 隊列 56

331 隊列的概念與基本運算 56

332 隊列的存儲 56

333 隊列的典型應用 61

34 航空航天應用實例分析與實現 62

35 習題 64

第4 章 串 68

41 實例引入 68

42 串的概念及基本運算 68

421 串的概念 68

422 串的基本運算 69

43 串的順序存儲結構與運算 69

431 串的定長順序存儲與運算 69

432 串的堆存儲與運算 71

44 串的鏈式存儲結構與運算 72

441 塊鏈串 72

442 塊鏈串的運算 73

45 串的模式匹配 74

451 BF 算法 74

452 KMP 算法 75

46 航空航天應用實例分析與實現 76

47 習題 77

第5 章 數組和廣義表 80

51 實例引入 80

52 數組 80

521 數組的定義 80

522 數組的順序存儲 81

53 矩陣的壓縮存儲 82

531 特殊矩陣的壓縮存儲 82

532 稀疏矩陣的壓縮存儲 85

54 廣義表 85

541 廣義表的概念與存儲 85

542 廣義表的基本操作 88

55 航空航天應用實例分析與實現 91

56 習題 92

第 2 篇 樹形結構

第6 章 樹 96

61 實例引入 96

611 數據編碼壓縮問題 96

612 樹與等價類劃分問題 96

613 表達式的樹形表示及求值 96

614 N 皇後問題 97

62 樹的相關概念 97

621 樹的定義與表示 97

622 樹的基本術語 97

623 樹的基本操作 98

63 二叉樹的定義、性質和存儲 99

631 二叉樹的定義和性質 99

632 二叉樹的存儲 102

64 二叉樹的遍歷與應用 104

641 二叉樹的遍歷 104

642 二叉樹遍歷的應用 107

65 線索二叉樹 111

651 線索二叉樹的基本概念 111

652 二叉樹的線索化 112

653 線索二叉樹的遍歷 113

66 樹和森林 114

661 樹的表示與存儲 114

662 樹、森林與二叉樹的轉換 116

663 樹和森林的遍歷 118

67 哈夫曼樹及應用 118

671 哈夫曼樹 119

672 哈夫曼編譯碼 122

68 航空航天應用實例分析與實現 124

69 習題 125

第3 篇 圖狀結構

第7 章 圖 130

71 實例引入 130

711 城市交通問題 130

712 工程問題 131

72 圖的相關概念 131

721 圖的概念 131

722 圖的基本操作 132

73 圖的存儲表示 133

731 鄰接矩陣表示法 133

732 鄰接表表示法 137

733 十字鏈表表示法 140

734 多重鏈表表示法 141

74 圖的遍歷 142

741 圖的深度優先搜索遍歷 142

742 圖的廣度優先搜索遍歷 143

75 圖的典型應用 144

751 最小生成樹 144

752 最短路徑 148

753 拓撲排序 151

754 關鍵路徑 153

76 航空航天應用實例分析與實現 154

761 航空飛行線路規劃系統的結構體類型 154

762 航空飛行線路規劃系統實現 155

77 習題 156

第4 篇 查找與排序

第8 章 查找 162

81 查找的相關概念 162

82 靜態查找 163

821 順序查找 163

822 折半查找 164

823 分塊查找 166

83 動態查找 168

831 基於二叉樹的查找 168

832 基於B 樹的查找 177

84 哈希表查找 182

841 哈希表的定義 182

842 哈希函數的構造方法 183

843 處理沖突的方法 184

844 哈希表查找 187

845 哈希表的查找分析 189

85 航空航天應用實例分析與實現 189

851 航空售票系統查詢航班 189

852 航空售票系統查詢訂單 190

853 航空售票系統查詢航班候補乘客訂單 191

86 習題 191

第9 章 排序 196

91 排序的相關概念 196

911 排序方法的穩定性 196

912 排序方法的分類 196

92 插入類排序 198

921 直接插入排序 198

922 折半插入排序 200

923 希爾排序 201

93 交換類排序 202

931 冒泡排序 202

932 快速排序 204

94 選擇類排序 205

941 簡單選擇排序 205

942 樹形選擇排序 207

943 堆排序 207

95 歸並類排序 211

96 分配類排序 212

961 多關鍵字排序 212

962 鏈式基數排序 213

97 外部排序 215

971 外部排序概述 215

972 置換選擇排序 216

973 多路歸並外排序 219

98 航空航天應用實例分析與實現 221

99 習題 222

第 2 部分 算法設計

第 10 章 算法設計方法 226

101 算法概述 226

1011 算法概念與表示 226

1012 算法的描述 226

1013 表達算法的抽象機制 228

1014 算法復雜性分析 228

102 遞歸與分治 232

1021 遞歸的概念與原理 233

1022 分治法的基本思想 235

1023 分治法的典型應用 236

103 動態規劃 240

1031 問題引入 241

1032 動態規劃算法的基本要素與基本步驟 241

1033 動態規劃算法的典型應用舉例 242

104 貪心算法 253

1041 問題引入 253

1042 貪心算法的基本要素與特點 253

1043 貪心算法的典型應用 254

105 回溯法 259

1051 問題引入 259

1052 回溯法的算法框架 259

1053 回溯法的典型應用 264

1054 小結 268

106 分支限界法 268

1061 問題引入 268

1062 分支限界法的基本思想 268

1063 分支限界法的典型應用 273

107 算法設計策略比較 283

108 航空航天應用案例分析與算法設計 284

1081 飛行規劃案例 284

1082 飛機維修次序案例 286

1083 航運裝載案例 286

109 習題 288

參考文獻 292