内容简介
本书主要介绍了数据结构的基本概念和基本算法。全书共分9个项目，主要内括绪论、线表、栈和队列、串、多维数组和广义表、树、图、查找和排序等。各项目中所涉及的数据结构与算法均给予了Java语言描述（所有程序都已运行通过），以便读者巩固和提高运用Java语行程序设计的能力。 本书在内容的选取、概念的引入、文字的叙述及例题和选择等方面都力求遵循面向应用、逻辑结构简明合理、由浅人深、深入浅出、循序、便于自学的原则，突出其实用与应用。 本书可作为计算机专业教材，也适合作为非计算机专业辅修计算机专业课程的教材，还可以供从事计算机软件开发的科技人员自学参考。
目录
项目一 绪论 任务一 数据结构的基本概念 一、学结构的原因 二、什么是数据结构 三、基本概念和术语 四、数据类型与抽象数据类型 任务二 算法和算法分析简介 一、算法 二、算法的描述 三、算法评价 实训 验证哥德巴赫猜想 小结 项目二 线表 任务一 线表的定义和基本操作 任务二 线表的顺序存储结构 一、线表的顺序存储结构 二、线表在顺序存储结构下的运算 任务三 线表的链式存储结构 一、线链表 二、循环链表 三、双向链表 实训 顺序表和链表的应用 小结 项目三 栈和队列 任务一 栈 一、栈的定义及其运算 二、栈的顺序存储结构 三、栈的链式存储结构 任务二 算术表达式求值 任务三 队列 一、队列的定义及其运算 二、队列的顺序存储结构 三、队列的链式存储结构 四、其他队列 实训 栈与队列的应用 小结 项目四 串 任务一 串的基本概念 一、串的定义 二、主串和子串 任务二 串的存储结构 一、串值的存储 二、串名的存储映像 任务三 串的基本运算及其实现 一、串的基本运算 二、串的基本运算的实现 实训 文本编辑系统 小结 项目五 多维数组和广义表 任务一 多维数组 一、多维数组的概念 二、多维数组在计算机内的存放 任务二 多维数组的存储结构 一、行优先顺序 二、列优先顺序 任务三 特殊矩阵及其压缩存储 一、特殊矩阵 二、压缩存储 任务四 稀疏矩阵 一、稀疏矩阵的存储 二、稀疏矩阵的运算 任务五 广义表 一、基本概念 二、存储结构 三、基本运算 实训 迷宫问题 小结 项目六 树 任务一 树结构的定义与基本操作 一、树的定义及相关术语 二、树的存储结构 三、树的基本操作 任务二 二叉树 一、二叉树的定义与基本操作 二、二叉树的：质 三、二叉树的存储结构 四、树与二叉树的相互转换 任务三 遍历二叉树 一、先序遍历 二、中序遍历 三、后序遍历 四、层次遍历 任务四 线索二叉树 一、线索二叉树的基本概念 二、中序次序线索化算法 任务五 二又排序树 一、二叉排序树的定义 二、二叉排序树的生成 三、删除二叉排序树上的结点 任务六 哈夫曼树和哈夫曼算法 一、哈夫曼树的定义 二、构造哈夫曼树——哈夫曼算法 三、哈夫曼树的应用 实训 哈夫曼编码 小结 项目七 图 任务一 基本定义和术语 一、基本定义和术语 二、抽象数据类型 任务二 图的存储结构 一、邻接矩阵 二、邻接表 任务三 图的遍历 一、深度优先搜索遍历 二、广度优先搜索遍历 任务四 小生成树 任务五 短路径 一、单源点短路径 二、所有顶点对之间的短路径 任务六 拓扑排序 实训 图的遍历应用 小结 项目八 查找 任务一 顺序查找 任务二 折半查找 任务三 分块查找 任务四 哈希表 一、哈希表和哈希函数的概念 二、哈希函数的构造方法 三、冲突处理 实训 学生档案管理系统 小结 项目九 排序 任务一 插入排序 一、线插入排序 二、折半插入排序 任务二 希尔排序 任务三 选择排序 任务四 堆排序 任务五 快速排序 任务六 归并排序 任务七 基数排序 任务八 外部排序 任务九 各种排序方法的比较 实训 排序系统 小结 参考文献
摘要与插图
任务一数据结构的基本概念
众所周知，20世纪40年代，电子计算机问世的直接原因是为了解决弹道学的计算问题。早期电子计算机的应用范围，几乎只局限于科学和工程计算，其处理的对象也是纯数值的信息，所以人们把这类计算称为数值计算。
50年来，电子计算机的发展异常迅猛，这不仅体现在计算机本身运算速度不断提高、信息存储量日益扩大、价格逐步下降等方面，更重要的是，计算机广泛应用于情报检索、企业管理和系统工程等方面，这已远远超出了数值计算的范围，渗透到了人类社会活动的一切领域。与此相对应，计算机的处理对象也从简单的纯数值信息发展到非数值的且具有结构的信息。因此，再把电子计算机简单地看行数值计算的工具，把数据仅理解为纯数值的信息，显得太狭隘了。现代计算机科学的观点是把计算机程序处理的一切数值的和非数值的信息，乃程序都统称为数据(Data)，而电子计算机则是加工处理数据(信息)的工具。
处理对象的转变导致系统程序和应用程序的规模越来越大，结构也变得更加复杂，单凭程序设计人员的经验和技巧已难以设计出效率高、可靠强的程序，数据的表示方法和组织形式已成为影响数据处理效率的关键。因此，这要求人们对计算机程序所加工的对行系统的研究，即研究数据的特及数据之间存在的关系——数据结构(Data Structure)。
数据结构是随着电子计算机的产展而发展起来的一门计算机课程。数据结构所讨论的有关问题，早先是为解决系统程序设计中的具体技术问题而出现在“编译程序”和“操作系统”中的。数据结构作为一门独立的课程在国外是从1968年开始设立的。在这之前，它的某些内容曾在其他课程如表处理语言中有所阐述。1968年，在美国一些大学计算机系的教学计划中，虽然把“数据结构”规定为一门课程，但对课程的范围没有做明确的规定。当时，数据结构几乎和图论是和表、树的理论为同义语。随后，数据结构这个概念扩充到网络、集合代数论、格、关系等方面，从而变成了现在称为“离散结构”的内容。然而，由于数据磐须在计算机行处理，所以不仅要考虑数据本身的数学质，还必须考虑数据的存储结构，这一步扩大了数据结构的内容。
1968年，美国唐·欧·克努特教授了数据结构的初体系，他所著的《计算机程序设计技巧卷基本算法》是本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，程序结构设计成为程序设计方法学的主要内容，人们越来越重视数据结构，认为程序设计的实质是对确定的问题选择一种好的结构，并设计一种好的算法。从20世纪70年代中期到80年代初，各种版本的数据结构著作相继出现。
目前，在我国数据结构也已经不仅是计算机专业教学计划课程之一，还是其他非计算机专业的主要选修课程之一。
“数据结构”在计算机科学中是～门综合的专业基础课。数据结构的研究不仅涉及计算机硬件(是编码理论、存储装置和存取方法等)的研究范围，还和计算机软件的研究有着密切的关系，因为无论是编译程序还是操作系统，都涉及数据元素在存储器中的分配问题。当研究信息检索时，也必须考虑如何组织数据，以便查找和存取数据元素。因此，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。我国从1978年开始，各院校先后开设了数据结构这门课。1982年的全国计算机教育学术讨论会和1983年的全国大专类计算机专业教学工作讨论会都把数据结构确定为计算机类各专业的核心课程之一。这是因为在计算机科学中，数据结构这门课的内容不仅是一般程序设计(是非数值程序设计)的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。
值得注意的是，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构已得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点来讨论数据结构，已成为一种新的趋势，越来越被人们重视。由此可见，数据结构技术正处于迅速发展的阶段。同时，随着电子计算机的发展和更新，新的数据结构也将会不断出现。
……