1、第19章 Java中的數(shù)據(jù)結構 上一章重點講述了數(shù)據(jù)結構、數(shù)據(jù)結構接口的基本知識，主要是以理論加上少量的實例進行講解。本章將繼續(xù)上一章的內(nèi)容，通過實例來進一步加深對數(shù)據(jù)結構的認識。本章的實例分析數(shù)據(jù)結構、各種不同類型的接口，以及這些結構的具體實現(xiàn)過程。19.1 鏈表 如果把數(shù)組作為一種數(shù)據(jù)結構，可能對讀者來說更容易理解。數(shù)組這種結構有一個很大的缺點，數(shù)組中的所有元素都按序排列，如果要刪除其中一個元素，后面的所有元素都需要依次向前方移動一個位置。如果這個數(shù)組元素很多，那么依次移動的次數(shù)就會明顯增多，從而耗費大量的系統(tǒng)資源。 為了能夠解決這個問題，數(shù)據(jù)結構引入了鏈表這個結構。下面將為讀者講述，有關

2、鏈表這種數(shù)據(jù)結構的定義和具體實現(xiàn)。19.1.1 什么是Java中的鏈表 本節(jié)介紹一種新的數(shù)據(jù)結構：鏈表。在Java語言中，鏈表中的元素存儲在一條鏈的節(jié)點上，不像數(shù)組是按序存儲在一系列連續(xù)的空間中。仔細分析圖19.1，讀者會明白它們的區(qū)別所在。分析為什么鏈表作為一種數(shù)據(jù)結構比數(shù)組要好？如圖19.2所示。（具體內(nèi)容請參照本書）19.1.2 用程序代碼段實現(xiàn)對鏈表的添加 下面演示一個有關操作鏈表中數(shù)據(jù)的實例，代碼如下所示。（具體內(nèi)容請參照本書）19.1.3 用程序代碼段實現(xiàn)對鏈表的刪除 下面再演示一個復雜的實例，其流程如圖19.6所示。（具體內(nèi)容請參照本書）19.2 數(shù)組列表類 數(shù)組列表類就是數(shù)組的

3、一個引申類，它繼承了數(shù)組的特點，并且又在數(shù)組基礎上有了自己所獨特的優(yōu)勢。本節(jié)介紹如何使用數(shù)據(jù)列表類。19.2.1 什么是數(shù)組列表類 數(shù)組的容量一旦被初始化設定好，就不可以再更改。這對于正在運行的程序來說，是一種缺陷。在程序設計過程中，經(jīng)常會遇到一些不確定的因素，導致無法確定一個數(shù)組的容量。為了解決這個問題，Java程序語言引進了數(shù)組列表。 數(shù)組列表就是一個可以動態(tài)變化容量的數(shù)組，其根據(jù)正在運行的程序的變化，隨時改變數(shù)組的容量，以滿足程序的需要。（具體內(nèi)容請參照本書）19.2.2 通過實例熟悉數(shù)組列表如何存儲數(shù)據(jù) 在舉實例之前，先介紹ArrayList類的一些方法函數(shù)。（具體內(nèi)容請參照本書）19

4、.3 散列表 前面介紹了鏈表和數(shù)組列表的知識，本節(jié)將介紹另一種數(shù)據(jù)結構：散列表。散列表跟鏈表和數(shù)組列表比起來，有什么不同？有什么優(yōu)點，又有什么缺點呢？ 19.3.1 什么是散列表 在鏈表和數(shù)組列表中，要想查找某個特定的元素，就必須從頭開始遍歷。如果一個鏈表或者一個數(shù)組列表擁有的元素數(shù)量很大，那么就需要耗費大量的系統(tǒng)資源，去遍歷整個數(shù)據(jù)結構。如何克服這個弊??？此時，就引進了另一個數(shù)據(jù)結構：散列表。 散列表通過“鍵值對應的形式存儲元素。它是一個無序的數(shù)據(jù)結構，跟鏈表和數(shù)組列表不同，鏈表和數(shù)組列表都是有序的數(shù)據(jù)結構。這種數(shù)據(jù)結構的最大缺點就是無法控制元素出現(xiàn)的順序，但同時正是因為它的無序，使得它可以

5、快速查找特定的元素。（具體內(nèi)容請參照本書）19.3.2 通過實例熟悉散列表如何存儲數(shù)據(jù) 在舉實例之前，先介紹散列表的構造器和常用的方法。只有了解這些方法，才能更好的應用散列表來存儲數(shù)據(jù)。散列表的構造器代碼如下所示：（具體內(nèi)容請參照本書）19.4 散列集 上一節(jié)介紹了散列表，本節(jié)將介紹是散列集，兩種數(shù)據(jù)結構只是一字之差。那么它們有什么區(qū)別？散列集又有什么可取之處呢？本節(jié)將通過實例來展示散列集的作用。19.4.1 什么是散列集 散列表和散列集這兩種數(shù)據(jù)結構，功能基本相同，不過它們實現(xiàn)的接口不一樣。散列表實現(xiàn)的是MAP映像接口，而散列集實現(xiàn)了Set接口。另外，散列表是線性同步，而散列集是非線性同步。

6、散列集既然實現(xiàn)了Set接口，也就實現(xiàn)了Collection接口，所以它是一個集合。仍然是add方法添加元素，接下來介紹散列集的構造器和常用方法函數(shù)。（具體內(nèi)容請參照本書）19.4.2 通過實例熟悉散列集如何存儲數(shù)據(jù) 本節(jié)將通過一個實例，熟悉散列集的用法。在這里有一點要說明，散列集可以采用迭代器進行遍歷。散列集和散列表一樣，都不能擁有相同的元素。散列集通過內(nèi)部散列碼計算元素存儲地址，這一點與散列表一樣，只不過散列集沒有鍵值。下面針對散列集的數(shù)據(jù)結構舉一個實例，實例的流程如圖19.9所示。（具體內(nèi)容請參照本書）19.5 樹集 前面講過鏈表、數(shù)組列表、散列表、散列集，本節(jié)將講述另一種數(shù)據(jù)結構：樹。樹

7、這種數(shù)據(jù)結構用在什么情況下？它與前面幾種數(shù)據(jù)結構有什么區(qū)別？本節(jié)通過實例講述樹這種數(shù)據(jù)結構，并逐個解答上面的問題。19.5.1 什么是樹集 樹集有點像散列集，但與散列集不同，樹集是一種有序的數(shù)據(jù)結構。樹集可以使用任何次序在這種數(shù)據(jù)結構中添加元素。當遍歷時，元素出現(xiàn)次序是有序的。不過這種次序由系統(tǒng)自動完成。（具體內(nèi)容請參照本書）19.5.2 通過實例熟悉樹集如何存儲數(shù)據(jù) 本節(jié)將通過實例，熟悉樹集在數(shù)據(jù)存儲方面的作用。下面看一個有關樹集的實例，實例流程如圖19.10所示。（具體內(nèi)容請參照本書）19.6 映像 集合是一種可以快速找到已經(jīng)存在的元素的數(shù)據(jù)結構。但如果數(shù)據(jù)庫中擁有大量的數(shù)據(jù)，一般不用集合

8、，因為它會耗費系統(tǒng)大量的資源和時間，去遍歷整個數(shù)據(jù)結構。前面講過散列表，其實散列表就是一種映像。下面將詳細講述映像及散列映像、樹映像，并通過實例讓讀者對映像的概念，有更深的認識。19.6.1 什么是映像 映像是一種采用“鍵值值的對應方式存儲的數(shù)據(jù)結構形式。在映像中，除了散列表，還有樹映像和散列映像。由于映像不能使用迭代器，所以映像擁有get方法函數(shù)。無論是樹映像，還是散列映像或散列表，它們的使用方法都差不多。下面通過實例了解熟悉樹映像。19.6.2 通過實例熟悉映像如何存儲數(shù)據(jù) 本小節(jié)將通過實例，學習如何通過映像存儲和操作數(shù)據(jù)。樹映像實例的流程如圖19.11所示。（具體內(nèi)容請參照本書）19.7

9、 枚舉 枚舉Enumeration接口有兩個方法，一個是hasElements，另一個nextElement。這個兩個方法的用法，與迭代器中的hasnext和next的用法基本一樣，不過在實際開發(fā)中，能遇到枚舉的機會不是很多。19.8 屬性集 屬性集property set是一種特殊類型的映像結構，Properties繼承自Hashtable。它有3個特點如下所示： 關鍵字和值都是字符串。 屬性集可以用文件保存，也可以從文件中裝入。 有兩個屬性列表：主屬性列表和缺省屬性列表。 （具體內(nèi)容請參照本書）19.9 常見疑難解答19.9.1 哪些是線程安全的的數(shù)據(jù)結構 答：在集合框架中，有些類是線程安全的，這些都在JDK1.1中。在JDK1.2之后，就出現(xiàn)許多非線程安全的類。下面是這些線程安全的同步的類： Vector：比ArrayList多了個同步化機制線程安全）。 Statck：堆棧類，先進后出。 Hashtable：比HashMap多了個線程安全。 Enumeration：枚舉，相當于迭代器。 （具體內(nèi)容請參照本書）19.9