数据结构(从概念到Java实现)

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

本书注重理论与实践的结合，采用循序渐进的方法，全面系统地介绍了数据结构相关的概念和算法。全书可概括为两部分，第一部分为知识讲解和上机实验，共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
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