动手学数据结构与算法

·名家作品：上海交通大学ACM班创始人俞勇教授、翁惠玉教授等编写； ·理论扎实：基于上交大多年的数据结构课程体系编写； ·配套资源丰富：在线代码运行环境+在线视频课程+习题+配套课件+代码实战课程+师资培训课程。 ·可搭配配套代码实战课程学习，跨越理论与实战的鸿沟 ·动手练平台，支持读者在线运行和下载使用代码

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

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