数据结构（从概念到Java实现）

“数据结构”是计算机相关专业的核心主干基础课程，它是一门实践性较强而理论知识较为抽象的课程，其重点和难点在于让学生理解和掌握算法的设计与分析，使学生具有较好的数据抽象能力、算法设计能力和创新思维能力，对学生来说学习难度较大。
本书注重理论与实践的结合，采用循序渐进的方法进行讲解，主要特点如下。
（1） 本书为一体化教程，融合了基础知识讲解、基础知识测试、实验、实验拓展和课程设计等内容。知识讲解和上机实验部分（第1~6章）首先给出知识导图，使学习者对本章内容有一定的了解和认识。然后从基本概念入手，逐步介绍其特点和基本操作的实现、主要算法的基本思想和实现步骤，接着通过实例进一步讲述如何应用，后通过上机实验使学习者理解和掌握相关的原理和方法。
（2） 精简内容、强化基础。本书遵循“有用、够用、实用”的基本原则，重点放在基础知识的介绍，且语言言简意赅，剔除了部分难度较大的内容。
（3） 本书采用了以Java语言为主、C 为辅的描述形式。目前，Java和C 语言是比较流行的面向对象的程序设计语言。Java是一种完全面向对象的程序设计语言，具有卓越的通用性、高效性、平台移植性和安全性，得到了广泛的应用。而C 通常适合那些需要“硬件级”操作的软件。两者之间的区别在于，C 更接近机器语言，因此其软件运行速度更快且能够直接与计算机内存、磁盘、CPU或者其他设备进行协作。本书对于算法的描述语言以Java为主，C 为辅，即对于各种数据结构的抽象数据类型描述采用Java接口实现，对于基本操作和主要算法均给出了Java源代码和C 源代码。
全书可概括为两部分。
部分包括知识讲解和上机实验，共6章： 第1章为概述，介绍了Java和C 编译环境、数据结构的基本概念、算法的基本概念和抽象数据类型。第2章为线性表结构；第3章为树结构；第4章为图结构；这三章介绍了各大结构的特点、基本操作、抽象数据类型和主要操作的算法实现，并融合了各结构中涉及的查找算法。第5章为排序算法，主要介绍了四大类型的排序算法的原理、步骤和算法实现。第6章为串与数组，主要介绍串、数组和矩阵结构的特点和应用。
第二部分为课程设计，共5章，主要是三大结构的综合应用，选取了九大问题，包括约瑟夫环、图书管理、迷宫、停车管理、排队就餐、哈夫曼编码、英文文本对比、校园地图和校园超市选址。通过课程设计提高学习者应用所学的原理和方法解决实际问题的能力。

本书由广东交通职业技术学院赖小平和庄越进行策划与审核，并与广东理工学院向志华、李清霞共同完成书稿的编写工作，第1、2、4、6章由赖小平编写，第3章由庄越编写，第5章由李清霞编写，第7、8、9、10、11章为课程设计部分，由向志华编写。
由于编者水平有限，书中难免有不足之处，恳请广大师生读者批评、指正。

编者2020年12月

本书注重理论与实践的结合，采用循序渐进的方法，全面系统地介绍了数据结构相关的概念和算法。 全书可概括为两部分，部分为知识讲解和上机实验，共6章，主要介绍线性表、树、图等基本数据结构的特点、基本操作、抽象数据类型、存储方式、实现方法和相关的典型应用，以及常用的排序方法和实现方法，此部分将知识点的讲解、知识检测与实验相融合。第二部分为课程设计，共5章，主要是三大结构的综合应用，选取了九大问题，包括约瑟夫环、图书管理、迷宫、停车管理、排队就餐、哈夫曼编码、英文文本对比、校园地图和校园超市选址。通过课程设计提高学习者应用所学的原理和方法解决实际问题的能力。 本书适合普通高等院校计算机相关专业的学生使用。

赖小平，女，1979年生，副教授，广东交通职业技术学院教师、广东省粤科标准化研究院标准化与知识产权教育专家，曾任广东远光软件股份有限公司任软件工程师\广东理工学院信息技术学院副院长，2015-2019 连续被聘为全国职业院校技能大赛裁判员。

第1章概述001
1.1编程环境001
1.1.1Java编程环境001
1.1.2C 编程环境003
1.2数据结构008
1.2.1基本概念008
1.2.2逻辑结构009
1.2.3存储结构010
1.3算法012
1.3.1算法的定义012
1.3.2算法特性012
1.3.3算法描述013
1.3.4算法分析014
1.4抽象数据类型015
1.5本章小结016
1.6基础知识检测016
1.7上机实验017
1.7.1实验1： 熟悉编程环境017
1.7.2实验2： 简单算法设计与分析018
1.7.3实验拓展019
第2章线性表结构020
2.1线性表基本概念020
2.2线性表的顺序存储021
2.2.1顺序存储的概念021
2.2.2顺序存储结构的实现022
2.2.3性能分析024
2.2.4顺序表查找优化025
2.3线性表的链式存储026
2.3.1链式存储的概念026
2.3.2单向链表027
2.3.3双向链表031
2.3.4顺序表与链表的比较032
2.4栈032
2.4.1栈的基本概念032
2.4.2栈的基本操作032
2.4.3栈的抽象数据类型033
2.4.4顺序栈033
2.4.5链式栈034
2.5队列036
数据结构(从概念到Java实现)

2.6哈希表040
2.6.1哈希表的基本概念040
2.6.2常用的哈希函数041
2.6.3冲突处理方法043
2.7本章小结044
2.8基础知识检测045
2.9上机实验045
2.9.1实验1： 顺序表的基本操作046
2.9.2实验2： 链表的基本操作049
2.9.3实验3： 栈的基本操作051
2.9.4实验4： 哈希表的应用053
2.9.5实验拓展054
第3章树结构055
3.1树基本概念055
3.1.1树的定义056
3.1.2树的基本术语056
3.1.3树的基本操作057
3.1.4树的抽象数据类型057
3.2二叉树的基本概念058
3.2.1二叉树的定义058
3.2.2二叉树的性质059
3.2.3二叉树与树的区别059
3.3二叉树的存储结构060
3.3.1二叉树的顺序存储结构060
3.3.2二叉树的链式存储结构061
3.4二叉树的建立与遍历065
3.4.1基于深度优先遍历策略的二叉树遍历065
3.4.2基于广度优先遍历策略的二叉树遍历067
3.4.3二叉树的建立方法068
3.5二叉排序树071
3.5.1二叉排序树的定义071
3.5.2基于二叉排序树的查找过程072
3.5.3二叉排序树中插入结点072
3.5.4二叉排序树中删除结点074
3.6哈夫曼树的应用076
3.6.1哈夫曼树的基本概念076
3.6.2哈夫曼树的构造方法077
3.6.3哈夫曼编码的构造方法078
3.7树的存储与遍历079
3.7.1树的存储结构079
3.7.2树的遍历083
3.7.3树、森林与二叉树之间的转换083
3.8基础知识检测085
3.9上机实验086
3.9.1实验1： 二叉树的建立与遍历086
3.9.2实验2： 二叉排序树的查找算法实现088
3.9.3实验3： 哈夫曼树的应用090
3.9.4实验拓展091
第4章图结构092
4.1图的基本概念092
4.1.1相关术语093
4.1.2图的基本操作095
4.1.3图的抽象数据类型095
4.2图的存储结构095
4.2.1邻接矩阵095
4.2.2邻接表101
4.2.3邻接矩阵与邻接表的对比107
4.3图的遍历107
4.4图的应用111
4.4.1小生成树111
4.4.2拓扑排序114
4.4.3短路径115
4.4.4关键路径118
4.5基础知识检测120
4.6上机实验122
4.6.1实验1： 图的存储122
4.6.2实验2： 图的遍历124
4.6.3实验3: 图的应用126
4.6.4实验拓展126
第5章排序算法127
5.1排序的基本概念127
5.2插入排序130
5.2.1直接插入排序130
5.2.2二分插入排序131
5.2.3希尔排序132
5.3交换排序134
5.3.1冒泡排序134
5.3.2快速排序135
5.4选择排序138
5.4.1直接选择排序138
5.4.2堆排序139
5.5合并排序142
5.5.1递归合并排序142
5.5.2非递归合并排序143
5.6基础知识检测144
5.7上机实验145
5.7.1实验1： 几种排序算法的实现145
5.7.2实验2： 排序算法时间性能比较147
5.7.3实验拓展149
第6章串与数组150
6.1串150
6.2数组157
6.3特殊矩阵的压缩存储158
6.4本章小结159
6.5基础知识检测159
6.6上机实验160
6.6.1实验1： 串的基本操作160
6.6.2实验2： 稀疏矩阵基本操作167
6.6.3实验拓展172
第7章课程设计概述173
7.1课程设计教学大纲173
7.2课程设计撰写规范175
第8章线性表的应用179
8.1基于约瑟夫环的数字游戏数据结构设计179
8.1.1任务分析180
8.1.2数据结构选择181
8.1.3算法设计与实现181
8.1.4算法运行界面示例183
8.2图书管理系统的设计184
8.2.1任务分析184
8.2.2数据结构选择185
8.2.3算法设计与实现187
8.2.4算法运行界面示例193
第9章栈和队列的应用196
9.1迷宫问题196
9.1.1任务分析196
9.1.2数据结构选择197
9.1.3算法设计与实现198
9.1.4算法运行界面示例201
9.2停车场管理方案的数据结构设计202
9.2.1任务分析203
9.2.2数据结构选择203
9.2.3算法设计与实现205
9.2.4算法运行界面示例207
9.3排队就餐管理方案设计208
9.3.1任务分析209
9.3.2数据结构选择209
9.3.3算法设计与实现210
9.3.4算法运行界面示例212
第10章树的应用213
10.1哈夫曼编/译码器213
10.1.1任务分析214
10.1.2数据结构选择214
10.1.3算法设计与实现215
10.1.4算法运行界面示例217
10.2英文文本比对器219
10.2.1任务分析219
10.2.2数据结构选择220
10.2.3算法设计与实现220
10.2.4算法运行界面示例221
第11章图的应用223
11.1校园地图设计及其应用223
11.1.1任务分析223
11.1.2数据结构选择224
11.1.3算法设计与实现224
11.1.4算法运行界面示例226
11.2校园超市选址方案设计228
11.2.1任务分析229
11.2.2数据结构选择229
11.2.3算法设计与实现230
11.2.4算法运行界面示例232
参考文献234

1.本书为一体化教程，融合了基础知识讲解、基础知识测试、实验、实验拓展和课程设计等内容。各章首先给出知识导图，使学习者对本章内容有一定的了解和认识。然后从基本概念入手，逐步介绍其特点和基本操作的实现、主要算法的基本思想和实现步骤，接着通过实例进一步讲述如何应用，后通过上机实验使学习者理解和掌握相关的原理和方法。 
2.精简内容、强化基础。本书遵循“有用、够用、实用”基本原则，重点放在基础知识的介绍，且语言言简意赅，剔除了部分难度较大的内容。 
3.本书采用了Java语言为主、C 为辅的描述形式。 
4.本书在内容编排上，以应用型本科专业实践教学需要为出发点，注重基础训练与综合创新训练相结合，本书的编者都是来自高校教学一线的专业教师，在文字表达上充分考虑学生的知识基础，在内容编排上图文并茂，尽可能将操作步骤形象化地展示在学习者面前。