面向?qū)ο缶幊蹋篔ava中的抽象數(shù)據(jù)類型——轉(zhuǎn)載

eclipse

面向?qū)ο缶幊蹋篔ava中的抽象數(shù)據(jù)類型

作者： ZDNET CHINA 特稿
Tuesday, February 5 2002 12:40 AM


  

在本文中，我們將考察Java中的數(shù)據(jù)類型，但是我們將介紹抽象數(shù)據(jù)類型（ADT）的概念。我們還將通過介紹Java Collections Framework（Java 集合架構(gòu)）來學(xué)習(xí)Java定義的一些ADT。

ADT
一個ADT是一個僅由保存的數(shù)據(jù)類型和可能在這個數(shù)據(jù)類型上進(jìn)行的操作定義的。開發(fā)者們只能通過ADT的操作方法來訪問ADT的屬性，而且他們不會知道這個數(shù)據(jù)類型內(nèi)部各種操作是如何實現(xiàn)的。

在Java中，我們常常使用一個接口來給出一個操作集合而不需要透露這些操作實現(xiàn)的細(xì)節(jié)。記住一個接口定義了一個方法集而Java類必須實現(xiàn)這個集合以便滿足它的強(qiáng)制性條件或者實現(xiàn)這個接口的一個實例。

線性表，堆棧和隊列
當(dāng)我們談?wù)揂DT的時候，經(jīng)常會說到線性表，堆棧和隊列。我們不會討論這些數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)，但我們會討論為什么它們被稱為ADT。

一個線性表是有限個元素的集合，其元素以線性的方式進(jìn)行排列并提供對它的元素的直接訪問。一個堆棧是一個后進(jìn)先出（LIFO）的有序線性表，元素從堆棧頭加入，并從堆棧頭取出。一個隊列是一個先進(jìn)先出的有序線性表，元素從隊列尾加入，并從隊列頭取出。

線性表，堆棧和隊列的內(nèi)部結(jié)構(gòu)可以用許多方式實現(xiàn)。例如，我們可以使用一個有序數(shù)組或者一個鏈表來實現(xiàn)每個結(jié)構(gòu)。關(guān)鍵的一點是不論你如何實現(xiàn)其內(nèi)部結(jié)構(gòu)，它對外的接口總是不變的。這使得你能夠修改或者升級底層的實現(xiàn)過程而不需要改變公共接口部分。

Java 集合架構(gòu)
Java 2軟件開發(fā)包（SDK）提供了一些新類來支持大多數(shù)常用的ADT。這些類被稱為Java集合類（類似于MFC中的集合類），它們協(xié)同工作從而形成Java 集合架構(gòu)。這個集合架構(gòu)提供了一套將數(shù)據(jù)表示成所謂的集合抽象數(shù)據(jù)的接口和類。

java.util.Collection接口被用來表示任意的成組的對象，也就是元素。這個接口提供基本的諸如添加，刪除，和查詢這樣的操作。Collection接口還提供了一個iterator方法。iterator方法返回java.util.Iterator接口的一個實例。而Iterator接口又提供了hasNext, next, 和 remove方法。使用Iterator接口提供的方法，你可以從頭到尾循環(huán)遍歷一個Collection對象中的實例并能夠安全的刪除iterator(游標(biāo))所表示的元素。

java.util.AbstractCollection 是所有集合架構(gòu)類的基礎(chǔ)。AbstractCollection 類提供了對java.util.Collection 接口中除iterator和size方法以外的所有方法的實現(xiàn)。這兩個例外的方法由所有繼承java.util.AbstractCollection的子類實現(xiàn)。

實現(xiàn)一個接口的類必須提供對所有接口方法的實現(xiàn)。因為集合架構(gòu)中的一些接口方法是可選的，所以必須有一種方法來通知調(diào)用者某種方法沒有實現(xiàn)。當(dāng)一個可選的方法被實現(xiàn)而這個方法又并沒有被實現(xiàn)的時候，就會拋出一個UnsupportedOperationException 異常。UnsupportedOperationException 類繼承了RuntimeException 類。這使得調(diào)用者能夠調(diào)用所有的集合操作而不需要把每次調(diào)用都放在一個try-catch對里。

List線性表
List接口繼承了Collection接口并定義了一個允許相同元素存在的有序集合。List接口還附加了一些使用一個數(shù)值型索引值并基于元素在線性表中的位置來操作Collection中元素的方法。這些操作包括add,get,set和remove。

List接口還提供了listIterator方法。這個方法返回java.util.ListIterator 接口的一個實例，這個實例能夠讓你從頭至尾或者從尾至頭的遍歷一個線性表。java.util.ListIterator 繼承了java.util.Iterator 接口。因此，它支持對它代表的Collection中的元素的添加和修改。

下面的例子演示了如何從后向前遍歷一個列表的元素。要完成這個工作，必須在遍歷開始之前把ListIterator定位于列表最后一個元素之后。

ListIterator iter = aList.listIterator(aList.size())&#59;
while (iter.hasPrevious())
   System.out.println(iter.previous().toString())&#59;
}
集合架構(gòu)提供了對List接口的兩個實現(xiàn)：LinkedList（鏈表）和ArrayList（數(shù)組列表，即靜態(tài)列表）。這兩個實現(xiàn)都支持對其元素的隨機(jī)訪問。一個ArrayList實例支持?jǐn)?shù)組風(fēng)格的操作并支持?jǐn)?shù)組大小的改變操作。一個LinkedList的實例則提供了在列表開始和結(jié)尾添加，刪除和提供元素的顯式的支持。使用這些新方法，一個程序員可以簡單的把一個LinedList當(dāng)做堆棧或者隊列使用，如下：

LinkedList aQueue = new LinkedList(aCollection)&#59;
aQueue.addFirst(newElement)&#59;
Object   anElement = aQueue.removeLast()&#59;
LinkedList  aStack = new LinkedList(aCollection)&#59;
aStack.addFirst(newElement)&#59;
Object   anElement= aStack.removeFirst()&#59;
表A中的代碼片段使用java.util.ArrayList 和 java.util.LinkedList演示了對java.util.List接口的實現(xiàn)實例的一些常用的操作。這些操作包括添加元素，隨機(jī)訪問元素和顯式的在列表尾刪除元素。

知其然不知其所以然是大有好處的
ADT提供了一個將對象公共接口中的操作和其具體的實現(xiàn)分開的強(qiáng)有力的工具。這使得一個ADT的實現(xiàn)可以不斷變化和演化同時保持其公共接口不變。Java集合架構(gòu)提供了大量的接口和其實現(xiàn)用來代表基本元素的集合并可以用來創(chuàng)建有用的ADT。

在我們的下一篇文章中，我們將更深入的學(xué)習(xí)集合架構(gòu)來表示更多的類，而且我們還會討論集合架構(gòu)的查找和排序功能