CollectionandGenerics

集合和通用課件常用資料結(jié)構(gòu)陣列（array）鏈結(jié)串列（linkedlist）樹（tree）雜湊表（hashtable）1-2Array存取元素的速度快。插入或移除元素值時(shí)，并不方便1-3Array陣列欲改變長(zhǎng)度必須重新建立另一個(gè)陣列。1-4LinkedList存取節(jié)點(diǎn)的速度較慢。變更鏈結(jié)串列的長(zhǎng)度很方便。1-5LinkedList插入或刪除節(jié)點(diǎn)也很方便。1-6Tree有「排序」的功能。節(jié)點(diǎn)資料的存取比較慢。BinaryTree1-7HashTable資料以keyvaluepaired的形式存在。一個(gè)元素包含一個(gè)key和一個(gè)value，透過key可以取得value。存取資料的速度快。較浪費(fèi)存儲(chǔ)器空間。1-8JavaCollection在撰寫程序時(shí),常需要處理一群同性質(zhì)資料的集合,為了方便程序處理這樣的集合,JavaAPI特別在java.util套件中提供了一組界面和類別,讓我們可建立這類資料集合的物件,這個(gè)物件就稱之為Collection(集合物件)。為了使這些集合類別有一致性,Java特別將Collection相關(guān)界面設(shè)計(jì)成一完整的CollectionsFramework架構(gòu)。1-9CollectionsFramework當(dāng)程序需要處理集合式的資料時(shí)(例如要處理學(xué)生數(shù)據(jù)庫(kù)),就可利用CollectionsFramework中的集合類別來(lái)建立代表學(xué)生資料的集合物件,接著即可利用集合類別提供的現(xiàn)成方法,來(lái)處理集合物件中的每一筆資料。1-10CollectionsFrameworkCollection界面：身為最上層的界面,它可代表任何物件集合

這些物件可以是有次序性或無(wú)次序性、有重復(fù)或沒有重復(fù)均可。此界面定義了基本的集合操作方法,象是新增/移除集合中的元素、將另一個(gè)集合新增進(jìn)來(lái)或移除、將集合物件轉(zhuǎn)成陣列的形式等等。1-11CollectionsFrameworkSet及SortedSet界面：Set代表的是沒有重復(fù)元素的集合,和Collection界面一樣Set界面也提供基本的元素新增/移除等方SortedSet界面則是表示集合中的元素已經(jīng)過排序,因此SortedSet界面也多定義了幾個(gè)與次序相關(guān)的方法,例如可傳回最前面或最后面元素的方法。1-12CollectionsFrameworkList界面：List代表有次序性,但元素可能有重復(fù)的集合。List的元素有類似于陣列元素的索引碼,因此可透過List界面的方法,快速存取到指定的元素、或某范圍內(nèi)的元素。1-13CollectionsFramework簡(jiǎn)介Map及SortedMap界面：Map是個(gè)有鍵-值(key-value)對(duì)應(yīng)關(guān)系的元素集合,例如每個(gè)學(xué)號(hào)對(duì)應(yīng)到一名學(xué)生,就是一種Map對(duì)應(yīng),其中key的值不能有重復(fù)。SortedMap界面,則是代表有次序性的Map集合。1-14基本管理方法基本管理的方法有以下幾個(gè)：1-15大量元素管理方法為方便一次進(jìn)行大量元素的增刪動(dòng)作,Collection界面提供以下幾個(gè)實(shí)用的方法：1-16陣列轉(zhuǎn)換如果遇到需用陣列的方式來(lái)操作集合的情況,就可用下列方法將集合內(nèi)容存到一個(gè)全新的陣列中,然后用該陣列進(jìn)行處理。1-17SetSet界面代表的是元素內(nèi)容都不重復(fù)的集合,在Set類型的集合物件中,每個(gè)元素都是不同的。Set界面方法都是繼承自Collection界面。由于元素內(nèi)容都不重復(fù),所以無(wú)法用add()、addAll()等方法將重復(fù)的元素加入Set類型的集合物件中。1-18Set實(shí)作Set界面的類別為抽象類別AbstractSet,它有三個(gè)衍生類別：HashSet、LinkedHashSet、TreeSet。1-19Set1-20SetAbstractCollection這個(gè)抽象類別看似沒什么重要,其實(shí)它也提供了一個(gè)實(shí)用的方法toString()。由于所有的集合類別都是AbstractCollection的衍生類別,所以使用任何類別時(shí),都可直接用System.out.println()將其內(nèi)容輸出,因?yàn)閠oString()方法會(huì)自動(dòng)替我們將集合內(nèi)容轉(zhuǎn)成字符串。1-21Set各集合類別的建構(gòu)方法都和陣列一樣可指定初始的大小,例如以下就是建立可存放10個(gè)元素的TreeSet類別物件：設(shè)定的只是初始大小。稍后隨程序運(yùn)作需要,有更多元素加入集合時(shí),集合的大小也會(huì)隨之?dāng)U大,不像陣列一開始設(shè)定大小后就不能變動(dòng)。1-22HashSetHashSet適用于任何希望元素不重復(fù),但不在意其次序性的集合。要建立HashSet物件可先建立空的HashSet物件,再自行用add()方法將物件加入1-23HashSet以下范例就是用HashSet設(shè)計(jì)一個(gè)文字接龍游戲,程序會(huì)建立一個(gè)HashSet物件,而使用者每輸入一個(gè)新詞,就會(huì)加到HashSet物件中。由于HashSet中不能有重復(fù)的元素,所以使用者輸入重復(fù)的詞,就無(wú)法被加到HashSet中,游戲即結(jié)束。程序內(nèi)容如下：1-24HashSet1-25HashSet1-26HashSet1-27HashSet從上列程序最后輸出的結(jié)果可發(fā)現(xiàn),HashSet物件中元素的順序和加入時(shí)的順序并不相同,這即是HashSet無(wú)次序性的特性。如果希望元素的次序能保持一致,則可改用LinkedHashSet。1-28LinkedHashSetLinkedHashSet是HashSet的子類別,兩者的特性也類似,只不過LinkedHashSet會(huì)讓集合物件中各元素維持加入時(shí)的順序。我們直接將上述的范例程序改用LinkedHashSet類別即可發(fā)現(xiàn)：1-29LinkedHashSet1-30LinkedHashSet1-31LinkedHashSet1-32LinkedHashSet1-33TreeSetTreeSet與其他類別最大的差異在于TreeSet實(shí)作了具有排序功能的SortedSet界面,一旦物件加入集合就會(huì)自動(dòng)排序。也因?yàn)檫@個(gè)特點(diǎn),此類別多了幾個(gè)和次序有關(guān)的方法可用：1-34TreeSet1-35TreeSet1-36TreeSet1-37TreeSet1-38ListList適用于有次序性、元素可能重復(fù)的集合。List集合在使用上和陣列有些類似,因?yàn)長(zhǎng)ist集合中的元素,也都可透過索引(index)來(lái)存取。1-39List界面與相關(guān)類別1-40Listadd()和set()方法感覺上都是將第index元素設(shè)為物件element,其實(shí)兩者的意義差別很大：set()是將原位置上的物件取代掉；但add()則是加入新物件,而原物件則是往后移。1-41List在java.util套件中實(shí)作List界面的只有AbstractList抽象類別,其衍生類別則有

AbstractSquentialList、ArrayList、LinkedList1-42List界面與相關(guān)類別1-43ArrayList我們可將ArrayList看成是個(gè)伸縮自如的陣列,原本的陣列在宣告之后,元素的數(shù)量就固定了,不能再增加元素的個(gè)數(shù),此外若要在陣列中插入一個(gè)元素,并讓原來(lái)的元素都向后移一個(gè)位置,也必須自已做相關(guān)處理,相當(dāng)不便,但使用ArrayList就不會(huì)這么麻煩了。1-44ArrayList然而不斷地變動(dòng)大小或配置過多未用的空間對(duì)程序/系統(tǒng)的效能也有些負(fù)面影響,因此ArrayList也提供了2個(gè)與使用空間有關(guān)的管理方法：1-45ArrayList在新增ArrayList物件的元素后，Java程序可以使用for循環(huán)配合索引取得每一個(gè)物件元素，如下所示：for(inti=0;i<alist.size();i++)System.out.print(alist.get(i)+"");程序碼使用size()方法取得元素?cái)?shù)，get()方法配合索引位置取出ArrayList物件的元素。1-46ArrayList1-47ArrayList1-48ArrayList1-49LinkedListLinkedList是另一類型的List類別,LinkedList的特點(diǎn)是它提供了一組專門處理集合中第一個(gè)、最后一個(gè)元素的方法：1-50LinkedList由于上述的特性,LinkedList很適合用來(lái)實(shí)作兩種基本的資料結(jié)構(gòu)(DataStructure)：即堆棧及隊(duì)列。所謂堆棧是指一種后進(jìn)先出(LIFO,LastInFirstOut)的資料結(jié)構(gòu),物件要被取出時(shí),必須等其它比它后加入的物件全部被拿出來(lái)后,才能將它拿出來(lái)。至于隊(duì)列(queue)則是一種先進(jìn)先出(FIFO)的資料結(jié)構(gòu),像生活中常見的排隊(duì)購(gòu)物1-51LinkedList1-52LinkedList1-53LinkedList1-54MapMap界面是用來(lái)存放鍵值對(duì)(key-valuepair)對(duì)應(yīng)關(guān)系的元素集合

在加入元素時(shí),必須指定此元素的key及value兩項(xiàng)內(nèi)容,而且key的內(nèi)容不可重復(fù)。例如有個(gè)學(xué)生的集合,就可用學(xué)號(hào)為鍵、學(xué)生姓名為值。如果在加入元素過程中,加入了重復(fù)的鍵,則新的值會(huì)取代舊的值。1-55Map由于上述的特性,因此Map界面只有isEmpty()、size()這兩個(gè)方法而元素的新增/移除需改用下列方法：1-56Map整個(gè)Map集合的操作則有以下的方法可使用：1-57MapSortedMap類別除了繼承Map類別外,還提供以下幾個(gè)類似于SortedSet的方法：1-58Map界面與相關(guān)類別Map/SortedMap的相關(guān)類別關(guān)系如下：1-59MapAbstractMap有5種衍生類別,但一般只用到HashMap和TreeMap,HashMap是用來(lái)存放不需強(qiáng)調(diào)先后次序的鍵值對(duì)集合至于對(duì)應(yīng)的TreeMap也和TreeSet一樣,會(huì)自動(dòng)將集合中的鍵值對(duì)排序所以適合用來(lái)存放需排序的鍵值對(duì),且用鍵搜尋值的執(zhí)行效率較佳。1-60Map界面與相關(guān)類別1-61Map界面與相關(guān)類別1-62Map界面與相關(guān)類別1-63列舉在C/C++語(yǔ)言中，我們可以使用enum關(guān)鍵字自行定義新的型別(type)，在Java5.0中也加入了列舉(enum)的用法。列舉的語(yǔ)法如下所列：enum列舉名稱{列舉值1,列舉值2,…}其中的列舉值一般習(xí)慣以全部大寫的字母命名。1-64列舉1-65列舉1-661-67EnumerationInterfaceEnumerationenum=…;while(enum.hasMoreElements()){Objecto=enum.nextElement();processObject(o);}for(Enumerationenum=…;enum.hasMoreElements();){Objecto=enum.nextElement();processObject(o);}提供一個(gè)走訪群集內(nèi)所有元素的標(biāo)準(zhǔn)方式IteratorIterator是java.util套件中的另一個(gè)界面,它并不是用來(lái)建立集合,而是用來(lái)逐一瀏覽集合中所有元素的一項(xiàng)工具。所有的Collection類別都有個(gè)iterator()方法,以集合物件呼叫此方法可傳回一Iterator物件,我們可用此物件呼叫Iterator界面的方法來(lái)逐一處理集合中的元素。1-68IteratorMap型的類別則無(wú)iterator()方法可傳回Iterator物件,但我們可取得代表Map物件的集合物件,再用它建立Iterator物件。Iterator界面提供了3個(gè)瀏覽集合物件的方法：1-69Iterator1-70Iterator1-71For-EachFor-Each循環(huán)JDK5.0新增語(yǔ)法的用法,For-Each循環(huán)適合用于集合物件上。For-Each循環(huán)仍然是我們用過的for循環(huán),但是其語(yǔ)法有點(diǎn)不一樣：它不需指定條件表達(dá)式等內(nèi)容,而是要指定一個(gè)您要逐一讀取所有元素的集合物件(或是陣列),以及一個(gè)代表單一元素的變量,其它部份則和for循環(huán)相同。1-72For-Each循環(huán)1-73For-Each循環(huán)1-74利用集合物件產(chǎn)生樂透號(hào)碼前面曾用過Math.random()產(chǎn)生隨機(jī)數(shù)的方式來(lái)產(chǎn)生隨機(jī)的樂透號(hào)碼,我們用List類型的集合物件來(lái)產(chǎn)生樂透號(hào)碼。1-75利用集合物件產(chǎn)生樂透號(hào)碼Collections類別有一個(gè)特別的方法shuffle(),可將參數(shù)所指的List物件中的元素順序打亂重排,shuffle的意思就是洗牌

所以shuffle()方法就是把List物件做洗牌的動(dòng)作,所以整個(gè)元素順序就會(huì)亂成一團(tuán),所以我們只要固定取某位置的一組元素,就會(huì)取到不同的內(nèi)容。1-76利用集合物件產(chǎn)生樂透號(hào)碼1-77利用集合物件產(chǎn)生樂透號(hào)碼1-78陽(yáng)春型英漢字典在日常先活中我們常會(huì)用到很多各式各樣的字典：例如英漢字典要用Java實(shí)作這類字典,最方便的做法就是使用Map類型物件。而要讓搜尋動(dòng)作效率最佳,則要使用TreeMap類別。1-79陽(yáng)春型英漢字典以下的陽(yáng)春型英漢字典的范例程序,就是從文字檔中讀取英文單字與中文解釋對(duì)照,并建立TreeMap物件供使用者進(jìn)行查詢：1-80陽(yáng)春型英漢字典1-81陽(yáng)春型英漢字典1-82陽(yáng)春型英漢字典1-83陽(yáng)春型英漢字典1-84泛型Java的集合物件-說(shuō)明「泛型Java」（GenericJava）是JDK5.0版在Java語(yǔ)法上的重大變革，提供類似C++語(yǔ)言的「樣版」（Templates）語(yǔ)法，新增編譯階段的集合物件型態(tài)檢查功能，可以減少程序碼中取出元素所需的大量型態(tài)轉(zhuǎn)換。1-85加入Generics之前1-86Java為保持語(yǔ)言的簡(jiǎn)單性，強(qiáng)迫程序員在使用Collections時(shí)必須記住所擁有的元素型別；取出元素并進(jìn)一步處理前，必須先轉(zhuǎn)型，從Object轉(zhuǎn)為實(shí)際型別。LinkedListmyList=newLinkedList();myList.add(newInteger(0));myList.add(newInteger(1));Integertempi=(Integer)myList.iterator().next();Generics加入Generics之后1-87如果以generictypes擴(kuò)充Java語(yǔ)言，就能以更直接的方式表現(xiàn)collection的相關(guān)信息，于是編譯器可追蹤記錄實(shí)際的元素型別，您也就不再需要轉(zhuǎn)型。有助于程序的開發(fā)與除錯(cuò)。

LinkedList<Integer>iList=newLinkedList<Integer>();iList.add(newInteger(0));iList.add(newInteger(1));Integertempi=iList.iterator().next();GenericsJava/C++泛型技術(shù)的根本差異1-88template<typenameT,...>classlist{...};#include<list>list<int>li;list<string>ls;list<double>ld;classlist;//string版本list<int>li;list<string>ls;list<double>ld;classlist;//int版本classlist;//double版本publicclassLinkedList<E>

{...};importjava.util.*LinkedList<Integer>...;LinkedList<String>...;LinkedList<Double>...;publicclassLinkedList{...};importjava.util.*LinkedList...;LinkedList...;LinkedList...;listjava.util.LinkedList.java.exe.class.class膨脹法擦拭法C++JavaGenerics同質(zhì)(homogenous)容器與異質(zhì)(heterogenous)容器1-89同質(zhì)容器：元素型別必須相同。C++STL的容器都是同質(zhì)容器。list<int>myList;

myList.push_back(3);異質(zhì)容器：元素型別可以不同。JavaCollections都是異質(zhì)容器。LinkedListmyList=newLinkedList();myList.add(newDouble(4.4));

myList.add(newString("jjhou"));編譯器建立int版-list元素型別是ObjectGenerics泛型Java的集合物件-泛型型態(tài)泛型Java可以使用「泛型型態(tài)」（GenericTypes）來(lái)擴(kuò)充Java語(yǔ)言，簡(jiǎn)單的說(shuō)，就是在建立集合物件時(shí)，以泛型型態(tài)指定集合物件儲(chǔ)存元素的資料型態(tài)，如下所示：

HashSet<Btype>hset=newHashSet<Byte>();HashSet<Float>hset=newHashSet<Float>();HashSet<String>hset=newHashSet<String>();使用”<”和”>”括起資料型態(tài)就是泛型型態(tài)，它是用來(lái)指定集合物件儲(chǔ)存元素的資料型態(tài)。1-90泛型1-91HashMap類別–實(shí)作Map界面(說(shuō)明)HashMap類別實(shí)作Map界面，相當(dāng)于是舊版的Hashtable類別，其儲(chǔ)存元素有2個(gè)：key鍵值和其對(duì)應(yīng)值，允許儲(chǔ)存null值。HashMap類別提供數(shù)種過載的建構(gòu)子，在Java程序建立HashMap物件（5.0版），如下所示：HashMap<String,String>hmap=newHashMap<String,String>();上述程序碼建立HashMap物件，因?yàn)閮?chǔ)存元素有鍵值和對(duì)應(yīng)值，所以指定2個(gè)泛型型態(tài)。1-92同質(zhì)容器與多型（Polymorphism）應(yīng)用1-93JavaCollections原就充份運(yùn)用多型：相當(dāng)于LinkedListStrokeRectCircleObject22113344665577LinkedList<Object>myList=newLinkedList<Object>();182b182c5182cStrokeRectCirclex:Integer

y:Integer

r:Integerl:Integer

t:Integer

w:Integer

h:Integerw:Integer

ia:ArrayList

<Integer>Generics同質(zhì)容器與多型（Polymorphism）應(yīng)用1-94為更好地運(yùn)用多型，可這么寫：

ShapeObjectStrokeRectCirclex:Integer

y:Integer

r:Integerl:Integer

t:Integer

w:Integer

h:Integerw:Integer

ia:ArrayList

<Integer>22113344665577LinkedList<Shape>myList=newLinkedList<Shape>();182b182c5182cStrokeRectCircleGenerics在JDK1.5中撰寫GenericClasses1-95ShapeObjectStrokeRectCirclex:T

y:T

r:Tl:T

t:T

w:T

h:Tw:T

a:ArrayList<T>22113344665577LinkedList<Shape>sList=newLinkedList<Shape>();182b182c5182cStroke<Integer,Integer>Rect<Integer>Circle<Integer>TTW,TLinkedList<Shape>sList=newLinkedList<Shape>();sList.add(newStroke<Integer,Integer>(…));sList.add(newRect<Integer>(…));sList.add(newCircle<Integer>(…));draw()

len()

compareTo()GenericsGenericClasses/Algorithms1-96ArrayList<String>strList=newArrayList<String>();strList.add("zero");strList.add("one");strList.add("two");strList.add("five");System.out.println(strList);

//[zero,one,two,five]Stringstr=Collections.max(strList);Collections.sort(strList);staticmethodsGenericsBoxing&UnBoxing的影響1-97LinkedList<Integer>iList=newLinkedList<Integer>();iList.add(newInteger(0));iList.add(newInteger(1));iList.add(newInteger(5));iList.add(newInteger(2));LinkedList<Integer>iList=newLinkedList<Integer>();iList.add(0); //boxingiList.add(1);iList.add(5);iList.add(2);inti=iList.get(2); //un-boxingGenerics容器元素必須是object（不可為純數(shù)值）范例importjava.util.*;importjava.text.*;classWordList{SortedMaptable;//SortedhashmapformaintainingthewordlistpublicWordList(){table=newTreeMap();}publicvoidadd(Stringword){Integerval;