动手学数据结构与算法

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

俞勇，享受国务院特殊津贴专家，首批“国家高层次人才特殊支持计划”教学名师，上海交通大学特聘教授，上海交通大学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