Java数据结构和算法系列文章，源码.zip

## 数据结构 - [基本概念](#基本概念) - [抽象数据类型](#抽象数据类型) 人们在使用计算机解决客观世界中存在的具体问题时，通常过程如下：首先通过对客观世界的认知形成印象和概念从而得到了信息，在此基础上建立概念模型，它必须能够如实地反映客观世界中的事物以及事物间的联系；根据概念模型将实际问题转化为计算机能够理解的形式，然后设计程序；用户通过人机交互界面与系统交流，使系统执行相应操作，最后解决实际的问题。 数据结构主要与在上述过程中从建立概念模型到实现模型转化并为后续程序设计提供基础的内容相关。它是用来反映一个概念模型的内部构成，即一个概念模型由那些成分数据构成，以什么方式构成，呈现什么结构。数据结构主要是研究程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。 ### 基本概念 - **数据（data）**是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。 数据的含义非常广泛，除了通常的数值数据、字符、字符串是数据以外，声音、图像等一切可以输入计算机并能被处理的都是数据。例如除了表示人的姓名、身高、体重等的字符、数字是数据，人的照片、指纹、三维模型、语音指令等也都是数据。 - **数据元素（dataelement）**是数据的基本单位，是数据集合的个体，在计算机程序中通常作为一个整体来进行处理。例如一条描述一位学生的完整信息的数据记录就是一个数据元素；空间中一点的三维坐标也可以是一个数据元素。数据元素通常由若干个数据项组成，例如描述学生相关信息的姓名、性别、学号等都是数据项；三维坐标中的每一维坐标值也是数据项。数据项具有原子性，是不可分割的最小单位。 - **数据对象（dataobject）**是性质相同的数据元素的集合，是数据的子集。例如一个学校的所有学生的集合就是数据对象，空间中所有点的集合也是数据对象。 - **数据结构（datastructure）**是指相互之间存在一种或多种特定关系的数据元素的集合。是组织并存储数据以便能够有效使用的一种专门格式，它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。 由于信息可以存在于逻辑思维领域，也可以存在于计算机世界，因此作为信息载体的数据同样存在于两个世界中。表示一组数据元素及其相互关系的数据结构同样也有两种不同的表现形式，一种是数据结构的逻辑层面，即数据的**逻辑结构**；一种是存在于计算机世界的物理层面，即数据的**存储结构**。 数据的逻辑结构按照数据元素之间相互关系的特性来分，可以分为以下四种结构：**集合、线性结构、树形结构和图状结构**。主要有线性表、栈、队列、树和图，其中线性表、栈、队列属于线性结构，树和图属于非线性结构。 ### 抽象数据类型 抽象数据类型是描述数据结构的一种理论工具。在介绍抽象数据类型之前我们先介绍一下数据类型的基本概念。 **数据类型（datatype）**是一组性质相同的数据元素的集合以及加在这个集合上的一组操作。例如Java语言中就有许多不同的数据类型，包括数值型的数据类型、字符串、布尔型等数据类型。以Java中的int型为例，int型的数据元素的集合是[-2147483648,2147483647]间的整数，定义在其上的操作有加、减、乘、除四则运算，还有模运算等。 定义数据类型的作用一个是隐藏计算机硬件及其特性和差别，使硬件对于用户而言是透明的，即用户可以不关心数据类型是怎么实现的而可以使用它。定义数据类型的另一个作用是，用户能够使用数据类型定义的操作，方便的实现问题的求解。例如，用户可以使用Java定义在int型的加法操作完成两个整数的加法运算，而不用关心两个整数的加法在计算机中到底是如何实现的。这样不但加快了用户解决问题的速度，也使得用户可以在更高的层面上考虑问题。 与机器语言、汇编语言相比，高级语言的出现大大地简便了程序设计。但是要将解答问题的步骤从非形式的自然语言表达到形式化的高级语言表达，仍然是一个复杂的过程，仍然要做很多繁杂琐碎的事情，因而仍然需要抽象。对于一个明确的问题，要解答这个问题，总是先选用该问题的一个数据模型。接着，弄清该问题所选用的数据模型在已知条件下的初始状态和要求的结果状态，以及隐含着的两个状态之间的关系。然后探索从数据模型的已知初始状态出发到达要求的结果状态所必需的运算步骤。 我们在探索运算步骤时，首先应该考虑顶层的运算步骤，然后再考虑底层的运算步骤。所谓顶层的运算步骤是指定义在数据模型级上的运算步骤，或叫宏观运算。它们组成解答问题步骤的主干部分。其中涉及的数据是数据模型中的一个变量，暂时不关心它的数据结构；涉及的运算以数据模型中的数据变量作为运算对象，或作为运算结果，或二者兼而为之，简称为定义在数据模型上的运算。由于暂时不关心变量的数据结构，这些运算都带有抽象性质，不含运算的细节。所谓底层的运算步骤是指顶层抽象的运算的具体实现。它们依赖于数据模型的结构，依赖于数据模型结构的具体表示。因此，底层的运算步骤包括两部分：一是数据模型的具体表示；二是定义在该数据模型上的运算的具体实现。我们可以把它们理解为微观运算。于是，底层运算是顶层运算的细化，底层运算为顶层运算服务。为了将顶层算法与底层算法隔开，使二者在设计时不会互相牵制、互相影响，必须对二者的接口进行一次抽象。让底层只通过这个接口为顶层服务，顶层也只通过这个接口调用底层的运算。这个接口就是抽象数据类型。 **抽象数据类型（abstractdatatype,简称ADT）**由一种数据模型和在该数据模型上的一组操作组成。 抽象数据类型包括定义和实现两个方面，其中定义是独立于实现的。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部的实现无关，即无论它的内部结构如何变化，只要它的逻辑特性不变，都不会影响到它的使用。其内部的变化（抽象数据类型实现的变化）只是可能会对外部在使用它解决问题时的效率上产生影响，因此我们的一个重要任务就是如何简单、高效地实现抽象数据类型。很明显，对于不同的运算组，为使组中所有运算的效率都尽可能地高，其相应的数据模型具体表示的选择将是不同的。在这个意义下，数据模型的具体表示又依赖于数据模型上定义的那些运算。特别是，当不同运算的效率互相制约时，还必须事先将所有的运算的相应使用频度排序，让所选择的数据模型的具体表示优先保证使用频度较高的运算有较高的效率。 我们应该看到，抽象数据类型的概念并不是全新的概念。抽象数据类型和数据类型在实质上是一个概念，只不过是对数据类型的进一步抽象，不仅限于各种不同的计算机处理器中已经实现的数据类型，还包括为解决更为复杂的问题而由用户自定义的复杂数据类型。例如高级语言都有的“