第 1章　緒論 1

11　問題引入 1

12　什么是數據結構 3

121　數據的邏輯結構 3

122　數據的存儲結構 4

123　數據的操作 5

13　算法分析 5

131　算法的基本概念 5

132　時間復雜度 6

133　空間復雜度 11

14　算法優(yōu)化 11

141　時間復雜度為O(n3)的算法11

142　時間復雜度為O(n2)的算法 12

143　時間復雜度為O(nlogn)的算法 13

144　時間復雜度為O(n)的算法 15

15　大型應用實現：火車票管理系統(tǒng)總覽 16

16　小結 17

17　習題 18

第 2章　線性表 19

21　問題引入 19

22　線性表的定義 20

23　線性表的實現 20

231　線性表的順序實現 20

232　線性表的鏈接實現 23

24　線性表的簡單應用 27

241　大整數處理 27

242　多項式求和 32

25　大型應用實現：列車運行計劃管理類 34

26　小結 36

27　習題 37

第3章　隊列與棧 38

31　問題引入 38

32　隊列 38

321　隊列的定義 39

322　隊列的順序實現 39

323　隊列的鏈接實現 44

324　隊列的簡單應用：排隊洗衣 45

33　棧 47

331　棧的定義 47

332　棧的順序實現 48

333　棧的鏈接實現 50

334　棧的簡單應用：括號匹配 52

34　大型應用實現：排隊交易類 53

35　小結 55

36　習題 55

第4章　樹與優(yōu)先級隊列 57

41　問題引入 57

42　樹的定義 57

43　二叉樹 59

431　二叉樹的定義 59

432　二叉樹的順序實現 63

433　二叉樹的鏈接實現 63

434　 二叉樹的簡單應用：哈夫曼編碼

和哈夫曼樹 69

44　優(yōu)先級隊列 74

441　優(yōu)先級隊列的定義 74

442　優(yōu)先級隊列的實現 74

443　 優(yōu)先級隊列的簡單應用：

任務調度 81

45　大型應用實現：帶優(yōu)先級的排隊

交易類 82

46　小結 83

47　習題 83

第5章　集合與靜態(tài)查找表 85

51　問題引入 85

52　集合的定義 85

53　靜態(tài)查找表 86

531　無序查找的實現 86

532　有序查找的實現 87

54　集合的簡單應用：并查集 89

55　大型應用實現：列車運行圖類（1） 92

56　小結 94

57　習題 94

第6章　動態(tài)查找表 96

61　問題引入 96

62　動態(tài)查找表的定義 96

63　二叉查找樹 97

631　二叉查找樹的定義 97

632　二叉查找樹的實現 97

64　AVL樹102

641　AVL樹的定義 102

642　AVL樹的實現 104

65　紅黑樹 112

651　紅黑樹的定義 112

652　紅黑樹的實現 114

66　哈希表 123

661　哈希表的定義 124

662　哈希表的實現 124

67　大型應用實現：旅客管理類129

68　小結 131

69　習題 132

第7章　排序 134

71　問題引入 134

72　排序的定義 134

73　插入排序 135

731　直接插入排序 135

732　二分插入排序 136

733　希爾排序 136

74　選擇排序 138

741　直接選擇排序 138

742　堆排序 139

75　交換排序 141

751　冒泡排序 141

752　快速排序 142

76　歸并排序 144

77　基數排序 145

78　小結 147

79　習題 148

第8章　外部查找與排序 150

81　問題引入 150

82　外部查找表的定義 150

83　B樹 151

831　B樹的定義 151

832　B樹的實現 152

84　B 樹 155

841　B 樹的定義 155

842　B 樹的實現 158

85　外排序 174

851　外排序的定義 174

852　外排序的實現 174

86　大型應用實現：余票管理類與行程

管理類 177

87　小結 183

88　習題 183

第9章　圖 185

91　問題引入 185

92　圖的定義 185

93　圖的實現 188

931　鄰接矩陣 188

932　鄰接表 191

94　圖的遍歷 194

941　深度優(yōu)先搜索（DFS） 194

942　廣度優(yōu)先搜索（BFS） 196

95　圖的遍歷的簡單應用 197

951　圖的連通性 197

952　歐拉回路 198

953　拓撲排序 202

954　關鍵路徑 204

96　大型應用實現：列車運行圖類（2） 206

97　小結 209

98　習題 209

第 10章　最小生成樹與最短路徑 211

101　問題引入 211

102　最小生成樹 211

1021　最小生成樹的定義 211

1022　克魯斯卡爾算法 212

1023　普里姆算法 214

103　單源最短路徑 217

1031　非加權圖的單源最短路徑 217

1032　加權圖的單源最短路徑 219

1033　 帶有負權值圖的單源最短

路徑 221

1034　無環(huán)圖的單源最短路徑 222

104　所有頂點對的最短路徑 223

105　大型應用實現：列車運行圖類（3） 224

106　小結 226

107　習題 226

第 11章　算法設計思想 228

111　枚舉法 228

112　貪婪算法 229

113　分治法 230

114　回溯法 233

115　動態(tài)規(guī)劃 235

116　隨機算法 237

117　算法綜合分析：外賣配送任務 238

118　小結 240

119　習題 240

附錄A　書中部分命題的證明 242

A1　證明二叉樹的性質 242

A2　 證明兩種遍歷方法是否能夠唯一確定

一棵二叉樹 244

A3　證明AVL樹的高度是對數級別的 245

A4　 證明AVL樹插入后至多只需要調整一個

結點即可恢復平衡 246

A5　 證明快速排序的平均時間復雜度為

O(nlogn) 246

A6　 證明歸并排序的時間復雜度為

O(nlogn) 247

附錄B　電子資源與運行環(huán)境配置 248

B1　動手練平臺 248

B2　電子資料倉庫 248

B3　本地環(huán)境搭建和倉庫代碼運行 249

B31　Linux環(huán)境 249

B32　Windows環(huán)境 255

B33　macOS環(huán)境 260