前    言

　　数据结构是普通院校计算机及相关专业的一门必修核心课程，主要讨论和研究从现实世界中抽象出来的数据的各种逻辑结构、在计算机中的存储结构，以及对其进行的各种处理运算的方法和算法。通过学习这门课程，使学生掌握如何利用计算机对数据进行有效的组织、存储和运算，为进一步学好后续各门计算机专业课程和进行软件开发打下良好的     基础。

　　数据的逻辑结构大致分为集合结构、线性结构、树型结构和图型结构4种。数据在计算机中的存储结构大致分为顺序结构、链接结构、索引结构和散列结构4种。对数据进行的各种运算主要有插入运算、删除运算、查找运算、遍历运算、排序运算等。

　　开设数据结构课程需要借助一种计算机程序设计语言进行，在目前广泛使用的程序设计语言中，Java程序设计语言是最流行和面向对象程度最完善的语言。利用Java语言中的接口能够准确地描述任一种数据结构的逻辑定义和运算，利用任一种存储结构所定义的存储类型能够有效地实现接口。总之，采用面向对象的程序设计方法和使用Java语言讲授数据结构课程正在逐渐兴起。

　　本书采用面向对象的Java语言描述数据结构及其算法，是作者多年来教材编写和教学经验的结晶，是对以往利用计算机语言编写数据结构教材的丰富、发展和完善。全书共分为11章，分别为绪论、集合、线性表、稀疏矩阵和广义表、栈和队列、树和二叉树、常用二叉树、图、图的应用、查找、排序。在第1章中，结合数据表实例开门见山地给出了数据的4种逻辑结构，接着给出了算法的描述和评价等内容，为展开叙述后续章节的内容奠定基础。在第2章中，介绍了集合的抽象数据类型和接口，以及在顺序和链接存储结构下的具体实现。在第3章中，介绍了一般线性表的接口定义和在顺序与链接存储结构下的具体实现，以及有序线性表对一般线性表的继承与实现。在第4章中，介绍了稀疏矩阵的三元组表示和进行的各种矩阵运算，同时讨论了广义表的定义和运算。在第5章中，分别介绍了栈和队列的数据结构特点、运算方法和实现，着重讨论了栈与递归的关系、一些典型问题的递归求解方法、栈在算术表达式计算中的应用等内容。在第6章和第7章中，讨论了树和二叉树的定义、性质、存储结构和遍历方法，以及二叉搜索树、堆、哈夫曼树、平衡二叉树的定义、存储和运算。在第8章和第9章中，介绍了图的基本概念、图的3种存储结构、图的深度和广度优先遍历、图的最小生成树、最短路径、拓扑排序和关键路径等内容。在第10章中，主要介绍了二分查找、索引查找、散列查找、B树查找等内容。最后一章为排序，主要介绍了插入排序、选择排序、交换排序、归并排序和外存文件排序等       内容。

　　书中的所有程序和算法都在Java开发和运行环境下调试通过，确保了算法的正确性和有效性。为了配合本书教学，作者同时编写和出版了相配套的《数据结构实用教程（Java语言描述）习题参考解答》一书，供同学们选用。在此书中，给出了每章内容的知识要点、课后练习题以及参考解答。练习题包括选择题、填空题、运算题、算法分析题、算法设计题等各种题型，通过做练习，能够巩固和提高对基本概念的理解深度和分析与设计算法的能力。

　　学习本教材应具备Java语言程序设计的基础知识，教学时数应安排在80学时左右，其中，讲授与上机实验的时数之比约为2:1，有条件的学校要尽量多安排上机时间。

　　本书结构设计和内容编写全部由笔者完成，虽然本人有多年编写数据结构教材的经验，但由于水平有限，错误和不足之处在所难免，敬请专家和读者批评指正。

　　徐孝凯  ?

　　2012年9月

??

??

??

??

II

数据结构实用教程（Java语言描述）

III

前    言