第19章 Java中的数据结构,上一章重点讲述了数据结构、数据结构接口的基本知识，主要是以理论加上少量的实例进行讲解。本章将继续上一章的内容，通过实例来进一步加深对数据结构的认识。本章的实例分析数据结构、各种不同类型的接口，以及这些结构的具体实现过程。,19.1 链表,如果把数组作为一种数据结构，可能对读者来说更容易理解。数组这种结构有一个很大的缺点，数组中的所有元素都按序排列，如果要删除其中一个元素，后面的所有元素都需要依次向前方移动一个位置。如果这个数组元素很多，那么依次移动的次数就会明显增多，从而耗费大量的系统资源。 为了能够解决这个问题，数据结构引入了链表这个结构。下面将为读者讲述，有关链表这种数据结构的定义和具体实现。,19.1.1 什么是Java中的链表,本节介绍一种新的数据结构：链表。在Java语言中，链表中的元素存储在一条链的节点上，不像数组是按序存储在一系列连续的空间中。仔细分析图19.1，读者会明白它们的区别所在。分析为什么链表作为一种数据结构比数组要好？如图19.2所示。（具体内容请参照本书）,19.1.2 用程序代码段实现对链表的添加,下面演示一个有关操作链表中数据的实例，代码如下所示。（具体内容请参照本书）,19.1.3 用程序代码段实现对链表的删除,下面再演示一个复杂的实例，其流程如图19.6所示。（具体内容请参照本书）,19.2 数组列表类,数组列表类就是数组的一个引申类，它继承了数组的特点，并且又在数组基础上有了自己所独特的优势。本节介绍如何使用数据列表类。,19.2.1 什么是数组列表类,数组的容量一旦被初始化设定好，就不可以再更改。这对于正在运行的程序来说，是一种缺陷。在程序设计过程中，经常会遇到一些不确定的因素，导致无法确定一个数组的容量。为了解决这个问题，Java程序语言引进了数组列表。 数组列表就是一个可以动态变化容量的数组，其根据正在运行的程序的变化，随时改变数组的容量，以满足程序的需要。（具体内容请参照本书）,19.2.2 通过实例熟悉数组列表如何存储数据,在举实例之前，先介绍ArrayList类的一些方法函数。（具体内容请参照本书）,19.3 散列表,前面介绍了链表和数组列表的知识，本节将介绍另一种数据结构：散列表。散列表跟链表和数组列表比起来，有什么不同？有什么优点，又有什么缺点呢？,19.3.1 什么是散列表,在链表和数组列表中，要想查找某个特定的元素，就必须从头开始遍历。如果一个链表或者一个数组列表拥有的元素数量很大，那么就需要耗费大量的系统资源，去遍历整个数据结构。如何克服这个弊病？此时，就引进了另一个数据结构：散列表。 散列表通过“键值对应”的形式存储元素。它是一个无序的数据结构，跟链表和数组列表不同，链表和数组列表都是有序的数据结构。这种数据结构的最大缺点就是无法控制元素出现的顺序，但同时正是因为它的无序，使得它可以快速查找特定的元素。（具体内容请参照本书）,19.3.2 通过实例熟悉散列表如何存储数据,在举实例之前，先介绍散列表的构造器和常用的方法。只有了解这些方法，才能更好的应用散列表来存储数据。散列表的构造器代码如下所示：（具体内容请参照本书）,19.4 散列集,上一节介绍了散列表，本节将介绍是散列集，两种数据结构只是一字之差。那么它们有什么区别？散列集又有什么可取之处呢？本节将通过实例来展示散列集的作用。,19.4.1 什么是散列集,散列表和散列集这两种数据结构，功能基本相同，不过它们实现的接口不一样。散列表实现的是MAP（映像）接口，而散列集实现了Set接口。另外，散列表是线性同步，而散列集是非线性同步。散列集既然实现了Set接口，也就实现了Collection接口，所以它是一个集合。仍然是add方法添加元素，接下来介绍散列集的构造器和常用方法函数。（具体内容请参照本书）,19.4.2 通过实例熟悉散列集如何存储数据,本节将通过一个实例，熟悉散列集的用法。在这里有一点要说明，散列集可以采用迭代器进行遍历。散列集和散列表一样，都不能拥有相同的元素。散列集通过内部散列码计算元素存储地址，这一点与散列表一样，只不过散列集没有键值。下面针对散列集的数据结构举一个实例，实例的流程如图19.9所示。（具体内容请参照本书）,19.5 树集,前面讲过链表、数组列表、散列表、散列集，本节将讲述另一种数据结构：树。树这种数据结构用在什么情况下？它与前面几种数据结构有什么区别？本节通过实例讲述树这种数据结构，并逐个解答上面的问题。,19.5.1 什么是树集,树集有点像散列集，但与散列集不同，树集是一种有序的数据结构。树集可以使用任何次序在这种数据结构中添加元素。当遍历时，元素出现次序是有序的。不过这种次序由系统自动完成。（具体内容请参照本书）,19.5.2 通过实例熟悉树集如何存储数据,本节将通过实例，熟悉树集在数据存储方面的作用。下面看一个有关树集的实例，实例流程如图19.10所示。（具体内容请参照本书）,19.6 映像,集合是一种可以快速找到已经存在的元素的数据结构。但如果数据库中拥有大量的数据，一般不用集合，因为它会耗费系统大量的资源和时间，去遍历整个数据结构。前面讲过散列表，其实散列表就是一种映像。下面将详细讲述映像及散列映像、树映像，并通过实例让读者对映像的概念，有更深的认识。,19.6.1 什么是映像,映像是一种采用“键值值”的对应方式存储的数据结构形式。在映像中，除了散列表，还有树映像和散列映像。由于映像不能使用迭代器，所以映像拥有get方法函数。无论是树映像，还是散列映像或散列表，它们的使用方法都差不多。下面通过实例了解熟悉树映像。,19.6.2 通过实例熟悉映像如何存储数据,本小节将通过实例，学习如何通过映像存储和操作数据。树映像实例的流程如图19.11所示。（具体内容请参照本书）,19.7 枚举,枚举Enumeration接口有两个方法，一个是hasElements，另一个nextElement。这个两个方法的用法，与迭代器中的hasnext和next的用法基本一样，不过在实际开发中，能遇到枚举的机会不是很多。,19.8 属性集,属性集（property set）是一种特殊类型的映像结构，Properties继承自Hashtable。它有3个特点如下所示： 关键字和值都是字符串。 属性集可以用文件保存，也可以从文件中装入。 有两个属性列表：主属性列表和缺省属性列表。 （具体内容请参照本书）,19.9 常见疑难解答,19.9.1 哪些是线程安全的的数据结构,答：在集合框架中，有些类是线程安全的，这些都在JDK1.1中。在JDK1.2之后，就出现许多非线程安全的类。下面是这些线程安全的同步的类： Vector：比ArrayList多了个同步化机制（线程安全）。 Statck：堆栈类，先进后出。 Hashtable：比HashMap多了个线程安全。 Enumeration：枚举，相当于迭代器。 （具体内容请参照本书）,19.9.2 Vector是什么样的数据结构,答：没有讲述它的原因，是因为目前使用它的频率不高。一般用数组列表代替它，因为它们的使用方法几乎一样，唯独不同的就在线程安全方面。数组列表是非线程安全类，在实现线程编程时，要自己处理安全问题，而Vector则是线程安全类，自动会处理安全问题。（具体内容请参照本书）,