数据结构与算法简明教程（Java语言版）"
本书是“数据结构与算法”课程(Java语言描述)的基本教材。全书突出数据逻辑结构主线，在编写思路和材料组织上具有体现整体架构、注重本质关联、彰显关键细节和强化实例讲解等特点。书中基本算法和实例实现程序都经过Java 8标准版(JDK 1.8版本)平台调试运行，能够实现课程的教材学习到实验操作的有效对接。
本书可分为三部分（共10章）： 第一部分是课程概述(第1章)； 第二部分是基于内存的数据结构(第2~7章)，包括线性结构(第2~4章)、树结构(第5~6章)、图结构(第7章)； 第三部分是高级部分(第8~10章)，包括查找(第8章)、排序(第9章)和文件(第10章)。
本书可作为高等院校计算机信息科学与技术及其相关专业本科生教材，也可作为非计算机专业开设相应计算机专业基础课的教材，还可作为自学教材。
“数据结构”是计算机及相关领域重要专业基础课之一。近年来，随着计算机网络技术的快速发展，Java语言使用日趋普遍； 同时，计算机相关领域对计算机软件技术使用的需求与层次也在不断地深化，非计算机专业开设诸如“数据结构与算法”等计算机课程也已逐步成为一种常态。根据不同层次学科专业编写基于Java语言相关教材业已形成一种日益明显的现实需求。本书就是在这种实际背景之下根据近年来教学实践编写完成的。
本书可分为三部分（共10章）： 第一部分是课程概述（第1章）； 第二部分是基于内存的数据结构（第2~7章），包括线性结构（第2~4章）、树结构（第5~6章）、图结构（第7章）； 第三部分是高级部分（第8~10章），包括查找（第8章）、排序（第9章）和文件（第10章）。“数据结构与算法”早已成为经典课程，本书组织体系建立在常规框架之内； 但由于“经典”通常都具涉及面广泛以及“重点”与“难点”同步情形，因此“数据结构”常常被认为是需要下工夫才能“教好”和花气力方可“学通”的专业基础课程之一，对于非计算机专业的相应教学来说更是如此。本书编著者和其他计算机科研与教学领域的同仁们一样，期望在本课程教学与改革方面尽自己的一份努力。通过基于C和C++语言“数据结构与算法”教学积累与基于Java语言数据结构方面教学实践，希望在教材中体现出下述特点，以适应现实教学方面的需求。
（1） 突出主线，从整体上理解相关内容。数据逻辑结构是本课程主线，课程所有内容都围绕其展开。既然是主线，就可以在各个层面上都有所体现。在教材开首“绪论”中提出“集合—线性表—树形—图”的基本逻辑结构线索，同时在讲授其后各章具体内容中也不断展开螺旋式上推强化。
① 线性结构的基础性。“线性表”是所有逻辑结构的基础，这可从下述两个方面进行描述，首先，体现在线性表内容的组织编排上： 线性表的一般概念与技术，基于更新限制的线性表——“栈”和“队列”，基于元素数据类型扩充与限制的线性表——“多维数组”和“字符串”； 另外，其他逻辑结构在最终技术处理的末端都能归结为线性表： 通过“遍历”技术，“树”和“图”实际上转化为线性表进行处理，“查找”和“排序”初始结构以线性表为基础。
② 集合结构的灵活性。“集合”作为一种逻辑数据结构，其结构约束最为简洁，由于“查找”和“排序”内容众多、技术复杂，使用集合作为初始数据结构就为各种具体算法实现提供了灵活展开的平台，如将所需排序的数据集合视为按照“工作顺序”组成的查找表时，就可根据实际需要采用基于“顺序表”查找、基于“树表”查找和基于“散列表”查找等。
③ 逻辑结构的层次性。图型结构是最为一般的数据结构，树形可视为“无环有根”的图结构，线性表可视为至多只有唯一父结点和子结点的树结构，集合可视为按照“工作顺序”得到的线性表，由此“高层复杂”结构可以通过适当方法转化“底层基本”结构进行操作。
（2） 强调实例，从具体中把握抽象原理。“数据结构”课程中不少概念和算法都比较抽象，如树和二叉树的递归定义、模式匹配的KMP算法、平衡树算法和希尔算法等。其抽象性表现在两个方面，首先是一般描述抽象，其次是编程实现抽象。大凡抽象之物都是人们出于各种需要对“具体实际”进行了不同层面和角度的“加工”，越是抽象，就越需要弄清其“直观”的本源，越需要通过“具体”的形象作为理解与把握方面的支撑。实际上，只有建立在“直观实例”之上的理解才是真正哲学和心理学意义上的理解。因此，选择和编排好相应的实例图示是讲清讲透抽象概念与算法的关键点。本书努力做到在保持科学性和逻辑性前提之下，凡是重要的概念、原理和算法都配有相应的直观图解，而难度较高的部分其相应图示都尽量详尽细微。实践证明，这样做教师可能会感觉“好讲”，同学们也可能会感到“易学”。
（3） 注重关联，从逻辑网络中建构知识。“数据结构”课程涉及概念和算法众多，初看起来似乎内容庞杂。实际上，作为一门经典课程，经过无数专家们的千锤百炼，早已成为一个逻辑脉络清晰与彼此精密套接的科学体系，问题是在教和学的过程当中实时进行把握和梳理，并不断地加以强调和体现。各个知识点只有放在整体体系合适的部位才能彰显其意义和作用，才能具有“鲜活”机体部件的价值。“数据结构”就是数据元素之间的“组织关系”，这种关系从计算机逻辑处理角度上考虑，是按照集合的“具有相同类型”的非结构特征语义关系、线性表的“前驱/后继”顺序关系、树形结构的“双亲/子女”层次关系和图结构的“邻接/路径”的到达关系等由简单到复杂的“正向”逐次推进； 而如果从技术处理角度上来看，却又是“图”通过“生成树”与树关联、“树”通过“遍历”与线性表关联这样由复杂到简单的“反向”递解推回。此外，“图”的各种概念繁多，但其中逻辑框架却可以理清： 图的基础元语是“顶点”和“边(弧)”，表示数据元素的顶点之间的关系元语是“邻接”。具邻接关系的顶点可以看作具有“强”关系，由非邻接关系分出一类“弱”关系——路径相连关系，这与树结构中从“父子关系”到“祖先子孙关系”演进过程类似。图的其他众多概念与算法都以此为初始，例如所有顶点都具“邻接关系”的图是“完全图”、所有顶点都具“路径连接”的图是“连通图”，再继续一般化，在非连通图中分解出连通分支等，如此这般，各基本概念都在图的元语整体框架中找到自己的位置，由此又有对这些概念进行处理验证和应用的各类算法，分散的个别对象形成同一的严密整体。
（4） 突出细节，由精微处体现关键。从某种意义上来看，“数据结构与算法”课程中许多概念，特别是算法都堪称“艺术精品”，而艺术品成功的关键在于其有“闪光细节”的展现。其实，课程中许多“细节”还是理解和掌握相应问题的关键所在，正如常说的“细节决定品质”和“一滴水中见太阳”。在理清整体脉络框架的前提之下，讲清有关“精微细节”，不仅可以有效深刻地掌握相应概念算法，同时也可以使得略显枯燥的课程能不时闪现出自己特有的魅力，激发学习者的学习热情。如在相关概念当中，单链表头结点的意义、链栈和链队不设头结点的缘由、循环队列辅助存储单元rear的设置、广义表嵌套性与数据树形结构的关联以及二分查找的中点mid设计等。再如相关算法当中，KMP算法“已有匹配信息”有效重用，顺序查找算法中“监视哨”的设立，希尔排序中的“跳跃式”分组，快速排序中的“大跨步”移动数据元素和堆排序中的“输出和调整”策略等等。这些也许并不适合仅做“描述性”的一般讲授，可能需要参透讲清，这些“细节”实际上正是课程极为精彩的组成部分，既是理解和把握相关原理技术的“牛鼻子”，也是值得课程学习者欣赏和玩味的闪光点。
当然，上述只是我们编写教材的一些基本设想并依此进行了初步实践，相关考虑还多有商榷之处，即使有了一些想法也未必在书中就得到比较满意的实现。实际上，由于编著者水平所限，教材中疏漏和不足之处在所难免，恳请专家和同仁们不吝指教。
本书编写过程中参考借鉴了国内外相关教材，其中主要部分参见教材的参考书目，特在此向各位专家作者表示衷心感谢！
本书可作为计算机专业和非计算机相关专业“数据结构与算法”教材，也适合于具有Java语言基础的读者自学。
教材由叶小平组织统筹，其中第1、2、3、8和9章主要由叶小平编写，第4、5、6、7和10章主要由陈瑛编写，何文海参与第7、10章工作并编写测试教材中主要程序。
编者
2016年5月
第1章绪论
1.1数据与数据类型
1.1.1数据的基本概念
1.1.2数据项与数据元素
1.1.3数据类型与抽象数据类型
1.2数据逻辑与存储结构
1.2.1数据逻辑结构
1.2.2数据存储结构
1.3数据运算与算法
1.3.1数据运算
1.3.2算法及其基本要求
1.3.3算法设计与分析
1.4“数据结构”课程的地位与教材内容
1.4.1“数据结构”课程的地位
1.4.2本书内容组织
本章小结
第2章线性表
2.1线性表概念
2.1.1线性表逻辑结构
2.1.2线性表ADT描述
2.2线性表的顺序存储
2.2.1顺序存储结构
2.2.2顺序表的基本操作
2.3线性表的链式存储
2.3.1单链表概念
2.3.2单链表的基本操作
2.3.3线性表存储结构比较
2.4链式存储其他实现方式
2.4.1循环链表
2.4.2双向链表
2.4.3静态链表
2.5单链表应用及迭代器
2.5.1单链表倒置
2.5.2两个有序链表合并
2.5.3一元多项式计算
2.5.4迭代器
本章小结
第3章栈和队列
3.1栈
3.1.1栈基本概念
3.1.2栈的顺序存储
3.1.3栈的链式存储
3.2栈的应用
3.2.1数制转换
3.2.2栈在递归中的应用
3.2.3栈在括号匹配中的应用
3.2.4表达式求值
3.2.5迷宫求解
3.3队列
3.3.1队列基本概念
3.3.2队列的顺序存储
3.3.3队列的链式存储
3.4队列的应用
本章小结
第4章数组和串
4.1数组
4.1.1二维数组
4.1.2矩阵的顺序表示与实现
4.1.3特殊矩阵的压缩存储
4.1.4稀疏矩阵的压缩存储
4.2串
4.2.1串及相关概念
4.2.2串的基本操作
4.2.3串的顺序存储
4.2.4串的链式存储
4.2.5串的模式匹配
本章小结
第5章树
5.1树结构及相关概念
5.1.1树的基本概念
5.1.2树的相关概念
5.2树的存储
5.2.1父结点表示法存储
5.2.2子结点表示法存储
5.2.3左子/右兄弟结点表示法存储
5.3树的遍历
5.3.1广度优先遍历
5.3.2深度优先遍历
本章小结
第6章二叉树及应用
6.1二叉树的概念及性质
6.1.1二叉树及其相关概念
6.1.2二叉树的基本性质
6.2二叉树的存储
6.2.1二叉树的顺序存储
6.2.2二叉树的链式存储
6.3二叉树的遍历
6.3.1先序遍历、中序遍历与后序遍历
6.3.2基于递归遍历算法
6.3.3基于非递归遍历算法
6.4线索二叉树
6.4.1线索与线索二叉树
6.4.2线索二叉树创建
6.4.3线索二叉树操作
6.5Huffman树及其应用
6.5.1编码及分类
6.5.2Huffman树
6.5.3基于顺序存储Huffman树
6.5.4Huffman编码
6.6树与二叉树的转换
6.6.1树转换为二叉树
6.6.2二叉树还原为树
6.6.3森林与二叉树的转换
本章小结
第7章图
7.1图的数据结构
7.1.1图的基本概念
7.1.2路径与连通
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.5有向网图的应用
7.6有向无环图的应用
7.6.1AOV网与拓扑排序
7.6.2AOE网与关键路径
本章小结
第8章查找
8.1数据查找
8.2基于线性表的查找
8.2.1顺序查找
8.2.2分块查找
8.2.3二分查找
8.3基于二叉树的查找
8.3.1二叉查找树概念
8.3.2基于二叉查找树的查找
8.3.3二叉查找树插入与生成算法
8.3.4二叉查找树删除
8.3.5平衡二叉树
8.4基于散列表的查找
8.4.1常用散列函数构建
8.4.2散列冲突处理
本章小结
第9章排序
9.1数据排序
9.1.1排序的基本概念
9.1.2排序算法性能分析
9.2插入排序
9.2.1直接插入排序
9.2.2二分插入排序
9.2.3Shell排序
9.3交换排序
9.3.1冒泡排序
9.3.2快速排序
9.4选择排序
9.4.1直接选择排序
9.4.2堆排序
9.5归并排序
9.6外排序
9.6.1外排序的基本步骤
9.6.2败者树k路归并算法
9.6.3k路归并算法实现
本章小结
第10章文件
10.1文件及其分类
10.1.1文件概述
10.1.2文件结构与操作
10.2顺序文件
10.2.1顺序文件存储结构
10.2.2顺序存储的实现
10.3索引文件
10.3.1索引表与索引文件
10.3.2ISAM文件
10.3.3VSAM文件
10.4动态索引B树
10.4.1B树
10.4.2B+树
10.5散列文件
10.6多关键码文件
10.6.1多重表文件
10.6.2倒排文件
本章小结
参考文献
加入时，请写明：“学校+姓名”，并写明“加入教师群”，只限教师。
