数据结构（Java版）

体现以就业为导向、产学结合的发展道路。学科和专业同步加强，按企业需要和岗位需求对接培养内容。

采用项目驱动、案例引导的编写模式。坚持“工作流程化”“任务驱动式”，突出“走向职业化”的特点。

专家、教师共建团队，优化编写队伍。把握行业发展和创新教材发展的方向，融入专业教学的课程设置与教材内容。

开发课程教学资源，推进专业信息化建设。开发网络课程、虚拟仿真实训平台等数字化教学资源，建立动态、共享的课程信息化资源库。

“数据结构”是计算机及相关专业的重要专业基础课程。通过本门课程的学习，学生不仅要掌握基本的理论知识，更重要的是要提高自身的实践能力。本书就是以计算机软件相关工作岗位员工必须掌握的知识为核心，以高职教育所培养的学生应具备的能力为依据，以突出实践性和实用性为目的进行设计编写的。

全书共分为8个模块，内容包括概述，线性表，栈和队列，数组、串和广义表，树和二叉树，图，排序，查找。并附有配套源代码、教学PPT、教学实施案例、教学设计大纲、习题答案等教学资源。

本书是根据高职高专教育的特点进行组织和编写的，参加本书编写的人员均为一线项目研发人员且又都是多年教授数据结构和Java系列课程的教学一线骨干教师。本书主要特色有：

（1）对各类数据结构的分析按照“实例引入－逻辑结构－存储结构－基本运算的代码实现－典型应用实例－知识巩固”的顺序进行讲述。

（2）内容选取合理，组织得当。理论部分以够用为度，突出实践内容。每章都由实例引入，并且配套一定数量的应用实例（配有完整代码）进行上机练习，有助于对理论知识的理解，并提高学生的Java编程能力。

（3）每章知识巩固部分为学生提供了理论知识、真题在线、实训任务三个方面的练习题。“理论知识”部分的习题都是精挑细选的，有加强概念理解的选择题、判断题，有帮助理解算法思想的简答题，也有培养算法设计能力的算法设计题；“真题在线”部分提供了历年计算机等级考试、程序员考试涉及到的真题；“实训任务”部分提供了完整的、可运行的程序上机实验供读者参考，以加深读者对所学知识的理解和应用。

本书适合作为高职高专计算机及相关专业的“数据结构”课程教材，也可作为计算机应用系统开发人员及相关人员学习数据结构知识的参考书或培训教材。

本书由李云平任主编，梁平、张扬、曹燕任副主编，参加编写的有许博、纪全、孙成昊老师，也为本书的校对和资源建设做了大量细致的工作，中国水利水电出版社的有关负责同志对本书的出版给予了大力支持。在本书编写过程中参考了大量国内外计算机网络文献资料，在此，谨向这些著作者以及为本书出版付出辛勤劳动的同志深表感谢。

由于作者水平所限，书中难免有不足与疏漏之处，敬请广大读者批评指正。

序
前言

模块1 概述 1
1.1 什么是数据结构 2
1.1.1 数据结构的起源及发展状况 2
1.1.2 数据结构的3种基本结构 2
1.2 数据结构的相关概念和术语 5
1.3 数据结构的研究内容 6
1.3.1 逻辑结构 6
1.3.2 存储结构 7
1.3.3 运算 8
1.3.4 数据结构三方面的关系 8
1.4 数据类型与抽象数据类型 9
1.4.1 数据类型 9
1.4.2 抽象数据类型 9
1.5 算法及其性能分析 9
1.5.1 数据结构与算法的关系 10
1.5.2 算法的概念及特点 10
1.5.3 算法的设计要求 11
1.5.4 算法的性能分析 11
1.6 小结 14
1.7 知识巩固 14
1.7.1 理论知识 14
1.7.2 实训任务 15
模块2 线性表 16
2.1 实例引入 17
2.2 线性表的逻辑结构 18
2.2.1 线性表的定义 18
2.2.2 线性表的基本运算 19
2.3 线性表的顺序存储结构及运算实现 20
2.3.1 顺序表的定义 20
2.3.2 顺序表的基本运算实现 21
2.3.3 顺序表在Java类库中的实现 24
2.4 线性表的链式存储结构及运算实现 25
2.4.1 单链表 26
2.4.2 双向链表 29
2.4.3 循环链表 32
2.4.4 链表在Java类库中的实现 33
2.5 应用举例 34
2.5.1 使用顺序表实现教师电话管理系统 34
2.5.2 使用链表实现教师电话管理系统 39
2.6 小结 45
2.7 知识巩固 46
2.7.1 理论知识 46
2.7.2 真题在线 48
2.7.3 实训任务 50
模块3 栈和队列 51
3.1 实例引入 52
3.2 栈 52
3.2.1 栈的概念及基本运算 52
3.2.2 栈的顺序存储结构及其算法实现 53
3.2.3 栈的链式存储结构及其算法实现 56
3.2.4 栈在Java类库中的实现 58
3.3 队列 58
3.3.1 队列的概念及基本运算 58
3.3.2 队列的顺序存储结构及其算法实现 59
3.3.3 队列的链式存储结构及其算法实现 63
3.3.4 队列在Java类库中的实现 64
3.4 应用举例 65
3.4.1 栈的应用举例 65
3.4.2 队列的应用举例 69
3.5 小结 71
3.6 知识巩固 72
3.6.1 理论知识 72
3.6.2 真题在线 74
3.6.3 实训任务 78
模块4 数组、串和广义表 79
4.1 实例引入 79
4.2 数组 80
4.2.1 数组的逻辑结构 80
4.2.2 数组的顺序存储结构 82
4.2.3 特殊矩阵的压缩存储 83
4.3 串 89
4.3.1 串的基本概念 89
4.3.2 串的基本运算 90
4.3.3 串的存储结构 93
4.4 广义表 94
4.5 应用举例 96
4.5.1 求班级成绩的平均分和最高分 96
4.5.2 矩阵相乘 97
4.6 小结 98
4.7 知识巩固 98
4.7.1 理论知识 98
4.7.2 真题在线 100
4.7.3 实训任务 101
模块5 树和二叉树 102
5.1 实例引入 102
5.2 树 103
5.2.1 树的逻辑结构 103
5.2.2 树在Java类库中的实现 105
5.3 二叉树 106
5.3.1 二叉树的逻辑结构 106
5.3.2 二叉树的性质 108
5.3.3 二叉树的存储结构及运算实现 110
5.3.4 二叉树的遍历 115
5.4 树、森林和二叉树的关系 120
5.4.1 树的存储结构 120
5.4.2 树、森林与二叉树的相互转换 123
5.4.3 树与森林的遍历 127
5.5 哈夫曼树及其应用 127
5.5.1 哈夫曼树的定义 128
5.5.2 哈夫曼树的构造 129
5.5.3 哈夫曼编码 130
5.6 应用举例 133
5.6.1 电文的编码和译码 134
5.6.2 二叉树遍历实现 138
5.7 小结 141
5.8 知识巩固 141
5.8.1 理论知识 141
5.8.2 真题在线 144
5.8.3 实训任务 145
模块6 图 146
6.1 实例引入 146
6.2 图的逻辑结构 148
6.2.1 图的定义 148
6.2.2 图的基本概念 148
6.3 图的存储结构及算法实现 153
6.3.1 邻接矩阵 153
6.3.2 邻接表 155
6.4 图的遍历 157
6.4.1 深度优先搜索遍历 158
6.4.2 广度优先搜索遍历 164
6.5 图的应用 170
6.5.1 最小生成树 170
6.5.2 最短路径 177
6.5.3 拓扑排序 180
6.6 应用举例 182
6.6.1 教学计划安排 183
6.6.2 旅游购票方案 187
6.7 小结 190
6.8 知识巩固 191
6.8.1 理论知识 191
6.8.2 真题在线 194
6.8.3 实训任务 196
模块7 排序 197
7.1 实例引入 197
7.2 排序基本概念 198
7.3 插入排序 199
7.3.1 直接插入排序 199
7.3.2 希尔排序 201
7.4 交换排序 203
7.4.1 冒泡排序 203
7.4.2 快速排序 205
7.5 选择排序 208
7.5.1 直接选择排序 209
7.5.2 堆排序 210
7.6 其他排序 213
7.6.1 归并排序 214
7.6.2 基数排序 215
7.7 应用举例 218
7.7.1 学生成绩查询结果排序 218
7.7.2 设置高端监视哨 219
7.8 小结 221
7.9 知识巩固 222
7.9.1 理论知识 222
7.9.2 真题在线 226
7.9.3 实训任务 228
模块8 查找 229
8.1 实例引入 229
8.2 查找基本概念 230
8.3 静态查找表 231
8.3.1 顺序查找 231
8.3.2 折半查找 233
8.3.3 分块查找 235
8.4 动态查找表 236
8.4.1 二叉排序树 237
8.4.2 平衡二叉树 241
8.5 哈希表 243
8.5.1 哈希表的基本概念 243
8.5.2 哈希函数的构造方法 244
8.5.3 处理哈希冲突的方法 247
8.6 应用举例 249
8.6.1 字符串的折半查找 249
8.6.2 学生成绩分段查找统计功能 250
8.7 小结 251
8.8 知识巩固 252
8.8.1 理论知识 252
8.8.2 真题在线 256
8.8.3 实训任务 257
知识巩固参考答案 258

1. Java面向对象程序设计 [主编 姜春磊 陈虹洁]
2. C语言程序设计实验指导与实训（第二版） [主编 倪燃]
3. Python程序设计及实践教程 [肖朝晖]
4. C语言程序设计 [魏琴 刘祖珉 赵仕波 肖阳春]
5. C语言程序设计实验教程 [张小刚 司春景]
6. 电气控制与PLC程序设计（第二版） [胡冠山]
7. Java Web项目化设计实践教程 [邱云 曾陈萍]
8. C语言程序设计（第三版） [主编 丁红 王立新 蔡开立]
9. Python数据分析 [主编　冯志辉　赵磊　李放]
10. Python程序设计与应用（第二版） [主编 张广渊]
11. C程序设计实践教程 [刘卫国]
12. C程序设计（慕课版） [刘卫国]
13. 程序设计基础实践教程（C/C++语言版） [张桂芬 葛丽娜]
14. C++案例项目精讲 [主编 杨国兴]
15. SwiftUI完全开发 [李智威 著]
16. MySQL数据库项目式教程 [陈亚峰]
17. C语言程序设计习题与实验指导（第二版） [主编 甄增荣 张宾]
18. C语言程序设计（第二版） [主编 甄增荣 田云霞]
19. Unity3D虚拟现实应用开发实践 [主 编 刘龙]
20. Python程序设计 [主编 姜春磊 陈虹洁]
21. C语言程序设计实践教程（活页式） [主编 郑茵 陈巍 滕泓虬]
22. 面向对象程序设计 [主编 张勇 张平华 赵小龙]
23. 数据结构（Python语言描述） [曹岳辉　刘卫国　康松林　编著]
24. Python程序设计基础及实战 [主编　刘健]
25. C语言程序设计 [姜雪]
26. Python程序设计实践教程 [王鹤琴 蔡正保]
27. C++程序设计实践教程（第三版） [主编 刘卫国 曹岳辉]
28. C++程序设计（第三版） [主编 曹岳辉 刘卫国]
29. C语言程序设计项目化教程（活页式） [主编 张利华 潘晓利]
30. 机器人流程自动化（RPA）实战——基于UiPath [主编　金鑫]