数据结构与算法——C++实现 微课视频版

本教材主要介绍线性表、树和图三类基本数据结构，并学习常用的查找和排序算法，培养算法分析的能力。本教材以工程应用为导向，每章起始既引入典型的工程应用问题，引导学生更深入地理解数据结构知识。现有教材的图形化描述多为流程图，不符合规范面向对象的要求，部分代码风格不良。本教材采用规范的UML语言对算法进行描述，并严格遵守阿里代码风格。本教材引入网络流行用语，以轻松诙谐的方式介绍复杂的理论知识。本教材面向普通高等学院计算机类相关专业，已经完成C++程序设计课程学习的本科生，同时也可以满足其他工科专业的本科生学习数据结构的需求。

数据结构是计算机专业的核心基础课程之一，在计算机及相关专业教学中占有十分重要的地位，也是其他理工类专业的重要选修课程。本书主要介绍线性表、树和图三种重要的基本数据结构，以及如何应用这些基本数据结构解决实际问题，在此基础上穿插讲解了一些在计算机发展目前做出重要贡献的经典算法，并以查找和排序为专题介绍了这两类算法。 本书既具有较强的理论性，又注重实际动手能力的培养，提供了丰富的图例和大量接近可执行版本的代码样例。通过阅读和学习，读者将了解数据对象的特性，掌握数据的逻辑结构与存储结构，初步具备数据组织和算法设计能力，从而提高学生的程序设计技能，为后续课程的学习和科研工作的参与打下良好的基础。 本书面向普通高等学校计算机及相关专业已经完成C++程序设计课程学习的本科生，也适用于其他理工类专业有学习数据结构需求的本科生和希望强化专业基础知识进入信息行业的非计算机专业学生阅读，还可作为计算机行业软硬件开发人员的参考书。

慕晨，男，博士，长安大学信息工程学院副教授，计算机科学系主任，重量一流专业“计算机科学与技术”负责人。2009年博士毕业于西安交通大学。负责计算机科学与技术重量一流专业、很好工程师，以及留学生班的申报、教学实施和教学改革工作。承担计算机科学与技术及很好工程师的“数据结构”课程的本科生教学工作约10年20余次，同时还承担“数据结构”留学生英文课程的教学工作，对数据结构课程的教学内容和教学方法有深刻的理解，在教学中实施了多项教学组织、评价等方面的改革。

第1章绪论
1．1数据结构的基本概念
1．1．1数据结构的定义与研究对象
1．1．2数据结构在程序设计中的作用
1．1．3逻辑结构与存储结构
1．2抽象数据类型与C++类
1．2．1抽象数据类型的基本概念
1．2．2设计与实现：无人驾驶汽车
1．3算法与算法分析
1．3．1算法的基本概念
1．3．2算法描述的工具
1．3．3算法评价与渐进复杂度思想
1．3．4算法的复杂度分析
1．4本章小结
本章习题
扩展阅读：唐纳德·欧文·克努特和他的天书
第2章线性表
2．1线性表及其逻辑结构
2．1．1线性表的定义
2．1．2线性表的抽象数据类型定义
2．2线性表的顺序存储和实现
2．2．1线性表的顺序存储
2．2．2顺序表基本操作的实现
2．3线性表的链接存储和实现
2．3．1线性表的链接存储
2．3．2单链表
2．3．3单链表基本操作的实现
2．3．4双向链表
2．3．5循环链表
2．3．6静态链表
2．4顺序表与链表的比较
2．5可怕的死亡游戏
2．5．1一维数组
2．5．2顺序表
2．5．3循环链表
2．5．4数学建模
2．6本章小结
本章习题
扩展阅读：复杂系统的计算机仿真方法
第3章栈和队列
3．1引言
3．2栈
3．2．1栈的定义
3．2．2栈的顺序存储结构及其实现
3．2．3两栈共享空间
3．2．4栈的链接存储结构及其实现
3．3队列
3．3．1队列的定义
3．3．2队列的顺序存储结构及其实现
3．3．3双端队列
3．3．4队列的链接存储结构及其实现
3．4栈和队列的应用
3．4．1数制转换
3．4．2函数的调用与递归
3．4．3表达式求值
3．4．4魔王语言翻译官
3．5本章小结
本章习题
扩展阅读：排队论
第4章串和数组
4．1引言
4．2字符串与模式匹配
4．2．1字符串的逻辑结构
4．2．2字符串的存储结构
4．2．3模式匹配
4．3数组和矩阵的压缩存储
4．3．1数组与矩阵
4．3．2特殊矩阵的压缩存储
4．3．3稀疏矩阵的压缩存储
4．4本章小结
本章习题
扩展阅读：暴力破解
第5章树和二叉树
5．1引言
5．2树与树的存储结构
5．2．1树的基本概念
5．2．2树的逻辑结构
5．2．3树的存储结构
5．3二叉树的逻辑结构
5．3．1二叉树的基本概念
5．3．2二叉树的基本性质
5．3．3二叉树的抽象数据类型
5．3．4二叉树的遍历
5．3．5二叉树的构造
5．4二叉树的存储结构
5．4．1顺序存储结构
5．4．2链式存储结构
5．4．3线索链表
5．5树、森林和二叉树的转换
5．5．1树和二叉树的对应关系
5．5．2树、森林和二叉树的相互转换
5．5．3树、森林和二叉树遍历操作的关系
5．6哈夫曼树和哈夫曼编码
5．6．1哈夫曼树的定义
5．6．2哈夫曼树的构造
5．6．3前缀编码和哈夫曼编码
5．7本章小结
本章习题
扩展阅读：树结构的设计模式——组合模式
第6章图
6．1引言
6．2图的定义和基本概念
6．2．1图的定义
6．2．2图的基本概念
6．2．3图的抽象数据类型
6．3图的存储
6．3．1邻接矩阵
6．3．2邻接表
6．4图的遍历
6．4．1深度优先遍历
6．4．2广度优先遍历
6．5图的典型应用
6．5．1最小生成树
6．5．2最短路径
6．5．3有向无环图及其应用
6．6本章小结
本章习题
扩展阅读：艾兹格·W.迪杰斯特拉
第7章查找
7．1查找的基本概念
7．2线性表的查找
7．2．1顺序查找
7．2．2折半查找
7．3树表的查找技术
7．3．1二叉排序树
7．3．2平衡二叉树
7．4散列表
7．4．1散列表的概念
7．4．2常用的散列函数
7．4．3处理冲突的方法
7．4．4散列表的查找分析
7．5B树
7．5．1B树的概念与查找
7．5．2B树的插入、构造和删除
7．6本章小结
本章习题
扩展阅读：启发式搜索算法
第8章排序
8．1排序的基本概念
8．2插入排序
8．2．1直接插入排序
8．2．2希尔排序
8．3交换排序
8．3．1冒泡排序
8．3．2快速排序
8．4选择排序
8．4．1简单选择排序
8．4．2堆排序
8．5归并排序
8．6分配排序
8．6．1桶式排序
……