第四篇　Java数据结构

第18章　数据结构的接口

本章将重点讲述数据结构中的一些基本概念，同时还讲述什么是Collection接口，什么又是Iterator接口，使用什么类来实现这些接口。本章的目的主要是对数据结构的接口做一个初步的、概念性的介绍，让读者能够清楚这些接口的用处，以便在实际开发中灵活运用。

本章重点：

数据结构的实现。

Collection集合接口与Iterator迭代器接口。

Map映射接口。

List链表接口和Set接口。

本节讲述数据结构的优点，数据结构其实就是规定数据是以何种形式存储，例如以队列的形式、以散列表的形式，还是以树的形式或者以映像的形式。

每一种存储方式都有不同的优势，因为每一种结构对应着存储不同种类的数据，只要使用了好的数据结构，那么读取或搜索数据将会更快、更准确。

数据按一定的方式组织起来就是数据结构，它体现了数据与数据之间的关系，可以从两个角度来分类：一个是存储结构，另一个是逻辑结构。

为了能够说明数据结构的含义，先解释下面的一些基本概念。

数据是对客观事物的符号的表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体来处理。一个数据元素由多个数据项组成，数据项是数据不可分割的最小单位。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一个二元组，记为：data_structure=（D, S）。

其中D为数据元素的集合，S是D上关系的集合。

数据元素相互之间的关系称为结构。根据数据元素之间关系的不同特性，通常分为下列4类基本结构：

集合：数据元素同属一个集合。

线性结构：数据元素间存在一对一的关系。

树形结构：结构中元素间是一对多的关系。

图（网）状结构：结构中元素间是多对多的关系。

数据的逻辑结构和物理结构：

逻辑结构：数据元素之间存在的关系（逻辑关系）称为数据的逻辑结构。

物理结构：数据结构在计算机中的表示称为数据的物理结构。

一种逻辑结构可映像成不同的存储结构：顺序存储结构和非顺序存储结构（链式存储结构和散列结构）。

Java语言类库提供了不少接口，其中有很多是关于数据结构的。所谓数据结构的接口，就是规定了此种数据结构如何存储数据。例如常见的数据结构接口：队列接口。

interface Queue

{

void add（Object obj）；

//向队尾插入元素

Object remove（）；

//从队头删除元素

int size（）；

//查看队列的长度

}

可以通过实现这个接口，将数据存储到这种数据结构中，以方便存取。在Java类库中像这样的接口有很多，希望读者在闲暇时间，逐个尝试地编写代码，从而达到对知识的融会贯通。