本书主要介绍几种经典数据结构和算法，按照“线性结构、树结构、图结构、集合结构”四大模块循序渐进地展开，涵盖全国硕士研究生招生考试计算机学科专业基础考试大纲的核心知识点。本书特色内容：闯关模块，以真题作为闯关任务，夯实理论基础；算法拓展模块，以经典算法作为拓展训练任务，提升实践能力；价值**模块（见电子课件），将思政元素与基本概念、理论和实例相融合，沁润品格、提升素养；丰富的配套资源，登录华信教育资源网（www.hxedu.com.cn）注册后免费下载。本书将C++作为数据结构的算法描述语言，将数据结构与面向对象技术有机结合。书中的算法讲解都有完整的C++代码实现，并在Visual Studio 2010环境下编译通过。本书既可作为应用型、职业型高等院校计算机及相关专业的数据结构课程教材，也可作为考研、专升本考试等的参考书，还可作为工程技术人员的工具书。

第1章 概论1 1.1 什么是数据结构1 1.2 基本概念和术语4 1.3 算法和算法分析7 1.3.1 算法的定义及特性7 1.3.2 算法的设计要求8 1.3.3 算法效率的衡量方法9 1.3.4 算法的时间复杂度9 1.3.5 算法的空间复杂度15 1.4 抽象数据类型16 习题118 第2章 线性表19 2.1 线性表的类型定义19 2.1.1 线性表的概念19 2.1.2 线性表的抽象数据类型20 2.2 线性表的顺序表示和实现21 2.2.1 线性表的顺序表示21 2.2.2 顺序表基本运算的实现22 2.3 线性表的链式表示和实现26 2.3.1 线性表的链式表示27 2.3.2 单链表上基本运算的实现30 2.4 双链表37 2.5 循环链表41 2.6 线性表实现方法的比较43 2.7 算法拓展44 习题248 第3章 栈和队列51 3.1 栈51 3.1.1 栈��类型定义51 3.1.2 顺序栈的表示和实现53 3.1.3 链栈的表示和实现55 3.2 栈的应用举例57 3.2.1 十进制数转换为其他进制数57 3.2.2 表达式中括号的匹配检查58 3.2.3 表达式求值59 3.2.4 利用栈消除递归67 3.3 队列71 3.3.1 队列的类型定义71 3.3.2 循环队列—队列的顺序表示和实现73 3.3.3 链队列—队列的链式表示和实现76 3.4 算法拓展78 习题381 第4章 串83 4.1 串的基本概念83 4.2 串的表示和实现84 4.2.1 串的顺序存储结构84 4.2.2 串的链式存储结构87 4.3 串的模式匹配88 4.3.1 朴素的模式匹配算法88 4.3.2 KMP算法89 习题494 第5章 数组96 5.1 基本概念96 5.2 矩阵的压缩存储99 5.2.1 特殊矩阵99 5.2.2 稀疏矩阵102 5.3 算法拓展109 习题5112 第6章 树和二叉树115 6.1 树的概念115 6.2 二叉树的概念和性质117 6.2.1 二叉树的概念和抽象数据类型117 6.2.2 二叉树的性质119 6.3 二叉树的表示和实现121 6.3.1 二叉树的存储结构121 6.3.2 二叉树的遍历123 6.3.3 二叉树的其他基本运算130 6.4 树和森林132 6.4.1 树的存储结构133 6.4.2 树、森林和二叉树的相互转换135 6.4.3 树和森林的遍历138 6.4.4 树和森林的其他基本运算141 *6.5 线索二叉树143 6.6 算法拓展145 习题6145 第7章 树和二叉树的应用148 *7.1 表达式树148 7.2 哈夫曼树和哈夫曼编码153 7.2.1 哈夫曼树153 7.2.2 哈夫曼编码157 7.3 堆和优先级队列160 7.3.1 堆160 7.3.2 优先级队列161 *7.4 并查集167 7.5 算法拓展169 习题7171 第8章 图173 8.1 图的概念173 8.2 图的存储结构177 8.2.1 邻接矩阵177 8.2.2 邻接表181 *8.2.3 十字链表186 *8.2.4 邻接多重表187 8.3 图的遍历187 8.3.1 深度优先遍历187 8.3.2 广度优先遍历190 8.3.3 图的连通分量和生成树192 8.4 算法拓展193 习题8194 第9章 图的应用197 9.1 *小生成树197 9.1.1 *小生成树的概念197 9.1.2 Prim算法198 9.1.3 Kruskal算法201 9.2 有向无环图及其应用204 9.2.1 拓扑排序205 9.2.2 关键路径210 9.3 *短路径216 9.3.1 单源点*短路径216 9.3.2 每对顶点之间的*短路径220 9.4 算法拓展223 习题9224 第10章 集合与查找226 10.1 基本概念226 10.2 静态查找表上的查找227 10.2.1 顺序查找227 10.2.2 折半查找229 10.2.3 分块查找233 10.3 动态查找表上的查找234 10.3.1 二叉查找树234 10.3.2 平衡二叉树241 *10.3.3 B树254 *10.3.4 B+树259 *10.3.5 字典树260 10.4 算法拓展261 习题10264 第11章 散列表267 11.1 散列表的概念267 11.2 构造散列函数的方法268 11.2.1 直接定址法268 11.2.2 折叠法268 11.2.3 数字分析法268 11.2.4 平方取中法268 11.2.5 除留余数法269 11.3 解决冲突的方法269 11.3.1 闭散列法269 11.3.2 开散列法272 11.4 散列表的查找性能分析272 11.5 散列表的实现273 11.5.1 闭散列表的表示和实现274 11.5.2 开散列表的表示和实现278 11.5.3 闭散列表与开散列表的比较281 习题11281 第12章 排序283 12.1 排序的基本概念283 12.2 插入排序284 12.2.1 直接插入排序284 12.2.2 折半插入排序285 12.2.3 希尔排序285 12.3 交换排序287 12.3.1 冒泡排序287 12.3.2 快速排序288 12.4 选择排序292 12.4.1 直接选择排序292 12.4.2 堆排序292 *12.4.3 锦标赛排序295 12.5 归并排序296 *12.6 基数排序298 12.7 各种内部排序算法的比较300 *12.8 外部排序303 12.8.1 置换选择排序304 12.8.2 多路归并排序305 习题12306 附录A 情景项目309 参考资料313