动手学数据结构与算法

.名家作品：上海交通大学ACM班创始人俞勇教授、翁惠玉教授等编写；

.理论扎实：基于上交大多年的数据结构课程体系编写；

.配套资源丰富：在线代码运行环境+在线视频课程+习题+配套课件+代码实战课程+师资培训课程。

.可搭配配套代码实战课程学习，跨越理论与实战的鸿沟 

.动手练平台，支持读者在线运行和下载使用代码

本书系统介绍了数据结构与算法的基本概念和相关知识，既注重理论，又注重算法设计，更突出代码实现，是一本着眼于数据结构与基本算法的教学实践的教材。 本书介绍了线性表、队列与栈、树与优先级队列、集合与静态查找表、动态查找表、排序、外部查找与排序、图、最小生成树与最短路径、算法设计思想等内容，将数据结构的理论与真实应用的实践紧密结合，从各种数据结构的代码实现到火车票管理系统的代码实现，手把手地指导读者学习数据结构与算法，帮助读者轻松掌握数据结构与算法的基本知识及基本技能，为后续进行更多专业课程的学习打下扎实基础。

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

翁惠玉，上海交通大学教授，长期担任ACM班程序设计和数据结构课程的主讲教师，著有“十二五”普通高等教育本科国家级规划教材《数据结构：思想与实现》（第2版）、工业和信息化部“十四五”规划教材《C++程序——设计思想与方法》（慕课版）（第4版）等。

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

周聪，上海交通大学博士生，本科毕业于上海交通大学ACM班；担任2020学年ACM班“程序设计”“数据结构”“编程综合实践”课程助教组组长，2021学年ACM班“程序设计”课程助教组组长。

本书体现了“问题先导，应用贯穿”的教材设计逻辑。从“问题引入”开始，展开介绍数据结构的定义与实现，并通过火车票管理系统逐步深入实践。本书还配备动手练平台和电子资料仓库，为读者的动手实践提供丰富的环境和资源。本书适合作为高校数据结构与算法课程的教材，也适合对计算机领域感兴趣的读者阅读。

——何钦铭  “国家高层次人才特殊支持计划”入选者、 “CCF杰出教育奖”获得者、 浙江大学教授，博士生导师

本书将复杂的数据结构与算法概念融入真实的火车票管理系统中，帮助读者在解决实际问题的过程中掌握相关知识和技能。俞勇教授及其团队为读者呈现了一个集理论与实践于一体的学习框架，让 读者能在实际操作中感受到数据结构与算法的魅力和价值。

——张铭  “CCF杰出教育奖”获得者、北京大学教授，博士生导师

高质量的教科书应该主打深入浅出，才不致读者望而生畏。本书从身边的实际应用出发，引导读者循序渐进地学习。本书还配备在线实验平台，手把手地指导读者将理论和方法运用于代码实现中。早年曾听说“故圣人之教，常俯而就之”，今天看到俞勇教授的这本教材，才晓得程子诚不欺我。

——邓俊辉  北京市高等学校教学名师、清华大学教授 

数据结构与算法的高效学习方法就是上手实践，从做小练习题到实现大项目，不断提升对其掌握程度。本书极好地执行了这个理念，相信读者跟着本书实践一遍，一定可以打下扎实的基础。

——李沐 上海交通大学2004级ACM班毕业生、前亚马逊资深首席科学家、《动手学深度学习》作者

本书凝聚了ACM班多年数据结构与算法课程实践的经验，用真实的应用实践贯穿全书。强烈推荐本书给所有希望在计算机科学领域打下扎实基础的同学。

——陈天奇 上海交通大学2006级ACM班毕业生、卡内基梅隆大学助理教授 

本书不仅在理论讲解上深入浅出，还注重动手编程和实践技巧，真正做到了让初学者轻松入门，让有经验者精进不懈。 

——杨笛一  上海交通大学2009级ACM班毕业生、斯坦福大学助理教授 

看到本书的试读版本时，曾经在教室里聆听翁 惠玉老师讲授数据结构的回忆涌上心头。尽管我在 课堂上仔细聆听每一个知识点，但课后仍然需要花 大量时间去查阅资料和代码范例。本书则完全解决 了我当时的烦恼，将数据结构与算法的理论知识与 代码实践结合起来。强烈推荐！ 

——张伟楠  上海交通大学2007级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