第 1章　緒論 1

11　問(wèn)題引入 1

12　什么是數(shù)據(jù)結(jié)構(gòu) 3

121　數(shù)據(jù)的邏輯結(jié)構(gòu) 3

122　數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 4

123　數(shù)據(jù)的操作 5

13　算法分析 5

131　算法的基本概念 5

132　時(shí)間復(fù)雜度 6

133　空間復(fù)雜度 11

14　算法優(yōu)化 11

141　時(shí)間復(fù)雜度為O(n3)的算法11

142　時(shí)間復(fù)雜度為O(n2)的算法 12

143　時(shí)間復(fù)雜度為O(nlogn)的算法 13

144　時(shí)間復(fù)雜度為O(n)的算法 15

15　大型應(yīng)用實(shí)現(xiàn)：火車(chē)票管理系統(tǒng)總覽 16

16　小結(jié) 17

17　習(xí)題 18

第 2章　線性表 19

21　問(wèn)題引入 19

22　線性表的定義 20

23　線性表的實(shí)現(xiàn) 20

231　線性表的順序?qū)崿F(xiàn) 20

232　線性表的鏈接實(shí)現(xiàn) 23

24　線性表的簡(jiǎn)單應(yīng)用 27

241　大整數(shù)處理 27

242　多項(xiàng)式求和 32

25　大型應(yīng)用實(shí)現(xiàn)：列車(chē)運(yùn)行計(jì)劃管理類(lèi) 34

26　小結(jié) 36

27　習(xí)題 37

第3章　隊(duì)列與棧 38

31　問(wèn)題引入 38

32　隊(duì)列 38

321　隊(duì)列的定義 39

322　隊(duì)列的順序?qū)崿F(xiàn) 39

323　隊(duì)列的鏈接實(shí)現(xiàn) 44

324　隊(duì)列的簡(jiǎn)單應(yīng)用：排隊(duì)洗衣 45

33　棧 47

331　棧的定義 47

332　棧的順序?qū)崿F(xiàn) 48

333　棧的鏈接實(shí)現(xiàn) 50

334　棧的簡(jiǎn)單應(yīng)用：括號(hào)匹配 52

34　大型應(yīng)用實(shí)現(xiàn)：排隊(duì)交易類(lèi) 53

35　小結(jié) 55

36　習(xí)題 55

第4章　樹(shù)與優(yōu)先級(jí)隊(duì)列 57

41　問(wèn)題引入 57

42　樹(shù)的定義 57

43　二叉樹(shù) 59

431　二叉樹(shù)的定義 59

432　二叉樹(shù)的順序?qū)崿F(xiàn) 63

433　二叉樹(shù)的鏈接實(shí)現(xiàn) 63

434　 二叉樹(shù)的簡(jiǎn)單應(yīng)用：哈夫曼編碼

和哈夫曼樹(shù) 69

44　優(yōu)先級(jí)隊(duì)列 74

441　優(yōu)先級(jí)隊(duì)列的定義 74

442　優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn) 74

443　 優(yōu)先級(jí)隊(duì)列的簡(jiǎn)單應(yīng)用：

任務(wù)調(diào)度 81

45　大型應(yīng)用實(shí)現(xiàn)：帶優(yōu)先級(jí)的排隊(duì)

交易類(lèi) 82

46　小結(jié) 83

47　習(xí)題 83

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

51　問(wèn)題引入 85

52　集合的定義 85

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

531　無(wú)序查找的實(shí)現(xiàn) 86

532　有序查找的實(shí)現(xiàn) 87

54　集合的簡(jiǎn)單應(yīng)用：并查集 89

55　大型應(yīng)用實(shí)現(xiàn)：列車(chē)運(yùn)行圖類(lèi)（1） 92

56　小結(jié) 94

57　習(xí)題 94

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

61　問(wèn)題引入 96

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

63　二叉查找樹(shù) 97

631　二叉查找樹(shù)的定義 97

632　二叉查找樹(shù)的實(shí)現(xiàn) 97

64　AVL樹(shù)102

641　AVL樹(shù)的定義 102

642　AVL樹(shù)的實(shí)現(xiàn) 104

65　紅黑樹(shù) 112

651　紅黑樹(shù)的定義 112

652　紅黑樹(shù)的實(shí)現(xiàn) 114

66　哈希表 123

661　哈希表的定義 124

662　哈希表的實(shí)現(xiàn) 124

67　大型應(yīng)用實(shí)現(xiàn)：旅客管理類(lèi)129

68　小結(jié) 131

69　習(xí)題 132

第7章　排序 134

71　問(wèn)題引入 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　基數(shù)排序 145

78　小結(jié) 147

79　習(xí)題 148

第8章　外部查找與排序 150

81　問(wèn)題引入 150

82　外部查找表的定義 150

83　B樹(shù) 151

831　B樹(shù)的定義 151

832　B樹(shù)的實(shí)現(xiàn) 152

84　B 樹(shù) 155

841　B 樹(shù)的定義 155

842　B 樹(shù)的實(shí)現(xiàn) 158

85　外排序 174

851　外排序的定義 174

852　外排序的實(shí)現(xiàn) 174

86　大型應(yīng)用實(shí)現(xiàn)：余票管理類(lèi)與行程

管理類(lèi) 177

87　小結(jié) 183

88　習(xí)題 183

第9章　圖 185

91　問(wèn)題引入 185

92　圖的定義 185

93　圖的實(shí)現(xiàn) 188

931　鄰接矩陣 188

932　鄰接表 191

94　圖的遍歷 194

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

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

95　圖的遍歷的簡(jiǎn)單應(yīng)用 197

951　圖的連通性 197

952　歐拉回路 198

953　拓?fù)渑判?202

954　關(guān)鍵路徑 204

96　大型應(yīng)用實(shí)現(xiàn)：列車(chē)運(yùn)行圖類(lèi)（2） 206

97　小結(jié) 209

98　習(xí)題 209

第 10章　最小生成樹(shù)與最短路徑 211

101　問(wèn)題引入 211

102　最小生成樹(shù) 211

1021　最小生成樹(shù)的定義 211

1022　克魯斯卡爾算法 212

1023　普里姆算法 214

103　單源最短路徑 217

1031　非加權(quán)圖的單源最短路徑 217

1032　加權(quán)圖的單源最短路徑 219

1033　 帶有負(fù)權(quán)值圖的單源最短

路徑 221

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

104　所有頂點(diǎn)對(duì)的最短路徑 223

105　大型應(yīng)用實(shí)現(xiàn)：列車(chē)運(yùn)行圖類(lèi)（3） 224

106　小結(jié) 226

107　習(xí)題 226

第 11章　算法設(shè)計(jì)思想 228

111　枚舉法 228

112　貪婪算法 229

113　分治法 230

114　回溯法 233

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

116　隨機(jī)算法 237

117　算法綜合分析：外賣(mài)配送任務(wù) 238

118　小結(jié) 240

119　習(xí)題 240

附錄A　書(shū)中部分命題的證明 242

A1　證明二叉樹(shù)的性質(zhì) 242

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

一棵二叉樹(shù) 244

A3　證明AVL樹(shù)的高度是對(duì)數(shù)級(jí)別的 245

A4　 證明AVL樹(shù)插入后至多只需要調(diào)整一個(gè)

結(jié)點(diǎn)即可恢復(fù)平衡 246

A5　 證明快速排序的平均時(shí)間復(fù)雜度為

O(nlogn) 246

A6　 證明歸并排序的時(shí)間復(fù)雜度為

O(nlogn) 247

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

B1　動(dòng)手練平臺(tái) 248

B2　電子資料倉(cāng)庫(kù) 248

B3　本地環(huán)境搭建和倉(cāng)庫(kù)代碼運(yùn)行 249

B31　Linux環(huán)境 249

B32　Windows環(huán)境 255

B33　macOS環(huán)境 260