動手學數據結構與算法

俞勇，享受国务院特殊津贴专家，首批“国家高层次人才特殊支持计划”教学名师，上海交通大学特聘教授，上海交通大学ACM班创始人，APEX数据与知识管理实验室主任。曾获得“全国模范教师”“全国师德标兵”“CCF杰出教育奖”“上海市五一劳动奖章”和“上海交通大学校长奖”等荣誉。2018年创办了伯禹人工智能学院，在上海交通大学ACM班人工智能专业课程体系的基础上，对人工课程体系进行创新，致力于培养卓越的人工智能算法工程师和研究员。翁惠玉，上海交通大学教授，长期担任ACM班程

序设计和数据结构课程的主讲教师，著有“十二五”普通高等教育本科国家级规划教

材《数据结构：思想与实现》（第2版）、工业和信息化部“十四五”规划教材《C++

程序——设计思想与方法》（慕课版）（第4版）等。 傅凌玥，上海交通大学博士生，本科毕业于上海交通大学ACM班；担任2019学年ACM班“数据结构”“编程综合实践”课程助教，2022学年工科平台“程序设计思想与方法（C++）”课程助教。周聪，上海交通大学博士生，本科毕业于上海交通大学ACM班；担任2020学年ACM班“程序设计”“数据结构”“编程综合实践”课程助教组组长，2021学年ACM班“程序设计”课程助教组组长。

第 1章　緒論 1

11　問題引入 1

12　什麽是數據結構 3

121　數據的邏輯結構 3

122　數據的存儲結構 4

123　數據的操作 5

13　算法分析 5

131　算法的基本概念 5

132　時間復雜度 6

133　空間復雜度 11

14　算法優化 11

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

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

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

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

15　大型應用實現：火車票管理系統總覽 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章　樹與優先級隊列 57

41　問題引入 57

42　樹的定義 57

43　二叉樹 59

431　二叉樹的定義 59

432　二叉樹的順序實現 63

433　二叉樹的鏈接實現 63

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

和哈夫曼樹 69

44　優先級隊列 74

441　優先級隊列的定義 74

442　優先級隊列的實現 74

443　 優先級隊列的簡單應用：

任務調度 81

45　大型應用實現：帶優先級的排隊

交易類 82

46　小結 83

47　習題 83

第5章　集合與靜態查找表 85

51　問題引入 85

52　集合的定義 85

53　靜態查找表 86

531　無序查找的實現 86

532　有序查找的實現 87

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

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

56　小結 94

57　習題 94

第6章　動態查找表 96

61　問題引入 96

62　動態查找表的定義 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　深度優先搜索（DFS） 194

942　廣度優先搜索（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　無環圖的單源最短路徑 222

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

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

106　小結 226

107　習題 226

第 11章　算法設計思想 228

111　枚舉法 228

112　貪婪算法 229

113　分治法 230

114　回溯法 233

115　動態規劃 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　電子資源與運行環境配置 248

B1　動手練平臺 248

B2　電子資料倉庫 248

B3　本地環境搭建和倉庫代碼運行 249

B31　Linux環境 249

B32　Windows環境 255

B33　macOS環境 260