下载掌阅APP，畅读海量书库
立即打开
天施地生，其益无方。凡益之道，与时偕行。
——《周易·益卦·彖传》
自20世纪90年代互联网进入商用并迅速兴起，到21世纪20年代大数据、人工智能技术的快速迭代，直至近几年大语言模型的迅猛崛起，这短短的30多年，科技有了极大的进步，社会有了极大的发展，不仅改变了世界的格局，也改变了人们的生活。
为了顺应时代的变化，专业教育何为？专业人才何所？2021年我们开始筹划一套可以“动手学”的人工智能系列教材——新一代人工智能实战型人才培养系列教程，这套教材将分期出版，第一期包括《动手学强化学习》《动手学机器学习》《动手学自然语言理解》《动手学计算机视觉》《动手学博弈论》《动手学数据结构与算法》等6册，稍后还会推出第二期，甚至第三期。
十年磨一剑，廿年亮一剑。自2002年上海交通大学ACM班创办至今已有20多年，这个以培养计算机科学家及行业领袖为宗旨的班级，已在国内外的学术界和工业界小有名气，其“秘籍”到底是什么？或许可以通过阅读和学习这套教材得知真相。
这套教材将满足高等院校的计算机专业、人工智能专业及新工科专业的学生，从事科研工作的高校教师、科研院所人员，转行到IT行业的从业人员及自学人群等对人工智能进行系统的理论学习，学后能够直接上手实战的需要。这是目前国内第一套可以“动手学”的人工智能系列教材，希望能为我国的人工智能实战型人才培养及人工智能落地做些有益的探索与实践。欢迎高等院校的教师与学生、科研院所及企业的研究人员与工程师、社会人士使用这套教材。
任何事物都有从无到有、从无序到有序的发展过程，人类社会的进化也是如此。有序就是循规蹈矩，有了规和矩才能画出圆和方。于是，世界万物也就有了各自的“形状”。
所谓数据结构与算法，则是用一定的“规则”和“方法”对大千世界的“重塑”。这里的规则，既不是抽象的数学，也不是具象的物理，它既要符合数学、物理等学科的思维，又要符合生活常理，更不同的是，它是一种计算机能表示，甚至能理解的方法。使用这些规则和方法，我们就可以方便地利用计算机重塑现实世界，为我们创作未来世界打下良好的基础。
计算机学科已经渗透到各个领域及行业，因此几乎所有专业（包括人工智能专业）都无法完全脱离计算机专业，数据结构是计算机类专业最基础，也是最重要的核心课程之一，它为其他后继课程的学习奠定了基础，很多学校在新工科平台的培养计划中也将其列为必修课程，数据结构的重要性不言而喻。同时，数据结构与算法又是一门实践性非常强的课程，这门课的难点不是理解不了知识点，而是想不出算法，更是写不出代码。但是，已有的教材主要注重知识点的描述方式与形式，例如用生活场景和动画展现，无法在教学过程中解决其实践性特点所带来的学习上的真正困难。那么，如何在教学过程中将理论讲解与代码实践无缝衔接，让学生真正做到边学边练呢？本书试图给出答案。
本书以动手练平台与电子资料仓库的形式为读者提供课程辅助材料和代码。书中将每一章的原理讲解部分与其代码实践部分耦合，读者在学完一个知识点原理后能立即以代码实践的形式学习其实现方式。更重要的是，可以直接对代码进行在线运行和修改，完成对一种数据结构的原理学习和代码实践。这样的学习方式能帮助读者更好地将理论知识点与实践能力点对应，也能帮助老师更高效地授课、布置作业和批改作业。
通过长期的程序设计及数据结构的教学探索与实践经验总结，我们特编写了本书，旨在分享上海交通大学ACM班的培养模式及教学方法，使读者不再畏惧代码，让每一个普通人都能上手“拿捏”代码，成为人工智能时代的弄潮儿，为我国乃至世界人工智能的发展贡献一份力量。
本书的编写遵循“问题先导，应用贯穿；描述简洁，代码其中”的原则。全书共包含11章，以火车票管理系统大型应用为主线，介绍涉及的基本概念、实现及应用。除了第1章和第11章，每章结构的安排基本按照问题引入、定义与实现、简单应用、大型应用实现、小结与习题的框架。
第1章 由火车票管理系统这个大型应用引入数据结构的基本概念（逻辑结构、存储结构、操作定义和操作实现等）、算法分析（时间复杂度、空间复杂度等）及优化，并介绍火车票管理系统的需求分析、系统构成及涉及的数据管理类。
第2章 介绍线性表的基本概念（定义、实现与简单应用），并介绍大型应用中列车运行计划管理类的实现。
第3章 介绍队列与栈的基本概念（定义、实现与简单应用），并介绍大型应用中排队交易类的实现。
第4章 介绍树的定义、二叉树与优先级队列的基本概念（定义、实现与简单应用）、哈夫曼树与哈夫曼编码，并介绍大型应用中带优先级的排队交易类的实现。
第5章 介绍集合的定义、静态查找表及并查集，并介绍大型应用中列车运行图类及旅途中的站点可达性查询的实现。
第6章 介绍二叉查找树、AVL树、红黑树、哈希表的基本概念（定义、实现），并介绍大型应用中旅客管理类的实现。
第7章 介绍排序的定义、插入排序、选择排序、交换排序、归并排序和基数排序。
第8章 介绍外部查找表的定义、B树、B+树、外排序，并介绍大型应用中余票管理类与行程管理类的实现。
第9章 介绍图的定义、实现、遍历（深度优先搜索、广度优先搜索）及图的遍历的简单应用（连通性、欧拉回路、拓扑排序及关键路径），并介绍大型应用中列车运行图类的线路途经站点查询的实现。
第10章 介绍最小生成树（定义、克鲁斯卡尔算法及普里姆算法）、单源最短路径（非加权图、加权图、带有负权值图及无环图的最短路径）、所有顶点对的最短路径，并介绍大型应用中列车运行图类的最优路线查询的实现。
第11章 介绍枚举法、贪婪算法、分治法、回溯法、动态规划、随机算法，并通过一个外卖配送任务实例进行算法综合分析。
本书的11章内容皆为数据结构与算法的主干知识，所有希望系统掌握数据结构基本知识及基本算法的读者都应该学习这些内容。
本书包括纸质图书与电子资源两部分。纸质图书包括相关数据结构的定义、实现、简单应用、大型应用的实现代码。电子资源包括三部分——理论解读视频、动手练平台与电子资料仓库，均可通过http://hds.boyuai.com访问，动手练平台与电子资料仓库的具体使用方法参见附录B。纸质图书的正文中还将提供对应视频课程的二维码，供读者使用手机扫描学习。本书提供的代码都是基于C++编写的，读者需要具有一定的C++编程基础。
读者可以根据自己的需求自行选择感兴趣的纸质内容或电子资源进行学习实践。例如，只想学习各种数据结构的基本概念而不关注具体实现细节的读者，可以只阅读代码以外的文字部分；已经了解了算法的实现，只想动手进行代码实践的读者，可以只关注代码的具体实现部分，直接使用动手练平台与电子资料仓库。
本书具有如下特色：
● 以大型应用中的实际场景作为问题引入，使读者在学习知识点前体验“有用”；
● 为各类数据结构配备完整的代码实现，使读者能将理论与实践相联系，更真切地感受“好用”；
● 完整地实现数据结构中公认最烦琐的B+树，使读者消除恐惧，领略“可用”；
● 以大型应用的实现贯穿本书所有章节，使读者在了解知识点的同时亲历“实用”。
本书是数据结构与算法的入门读物，也可以作为高校数据结构与算法课程的教材或者辅助教材。本书面向的读者主要是对数据结构与算法感兴趣的高校学生（包括本科生和研究生）、教师、企业及研究院所的研究人员及工程师。在阅读本书之前，读者需要掌握一些C++程序设计语言的基本语法和编程技能。由于编写时间有限，书中难免会有一些不足之处，恳请读者批评指正，以便再版时修改、完善。希望每一位读者在学习完本书之后都能有所收获，为本系列后续教材的学习以及投身人工智能事业打下良好的基础。
学而时习之，不亦乐乎。
——《论语》
同学们，动起手来，快乐学习，轻松编程，共创未来！
由衷感谢上海交通大学ACM班的历届助教及学生长期以来的积累，他们为本书做出了卓越贡献。
感谢ACM班21级的冯跃洋、杨晋晟同学完成本书中大型应用实现及火车票管理系统的完整代码及调试，为本书的代码实现做出了重要贡献。
感谢ACM班22级的王鲲鹏、王冠杰、张世奇、陈瑞茗、李紫燕为本书绘制插图。