2023/7/22《Java面向?qū)ο蟪绦蛟O(shè)計》第13章配合<Java面向?qū)ο蟪绦蛟O(shè)計>例子源代碼一起使用Powerpoint制作：耿祥義張躍平泛型與集合框架12023/7/22主要內(nèi)容泛型鏈表堆棧散列映射樹集樹映射難點樹映射導(dǎo)讀22023/7/22在jdk1.2之后，Java提供了實現(xiàn)常見數(shù)據(jù)結(jié)構(gòu)的類，這些實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的類通稱為Java集合框架。在JDK1.5后，Java集合框架開始支持泛型，本章首先介紹泛型，然后講解常見數(shù)據(jù)結(jié)構(gòu)類的用法。概述32023/7/22§13.1泛型泛型（Generics）是在JDK1.5中推出的，其主要目的是可以建立具有類型安全的集合框架，如鏈表、散列映射等數(shù)據(jù)結(jié)構(gòu)。42023/7/22§13.1.1泛型類聲明可以使用“class名稱<泛型列表>”聲明一個類,為了和普通的類有所區(qū)別，這樣聲明的類稱作泛型類,如：

classPeople<E>

參考：Cone.java

52023/7/22§13.1.2使用泛型類聲明對象泛型類聲明和創(chuàng)建對象時，類名后多了一對“<>”，而且必須要用具體的類型替換“<>”中的泛型。例如：Cone<Circle>coneOne;coneOne=newCone<Circle>(newCircle());例題13-162023/7/22§13.1.3泛型接口可以使用“interface名稱<泛型列表>”聲明一個接口，這樣聲名的接口稱作泛型接口如

interfaceComputer<E>

例題13-272023/7/228.1Java中的集合類結(jié)構(gòu)

Java提供了集合類(Collection)及其API，于是用戶可以通過統(tǒng)一的操作接口，使得從一種數(shù)據(jù)結(jié)構(gòu)到另一種數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換極為方便，簡化了程序員編程時的負(fù)擔(dān)。任何集合框架包括三部分內(nèi)容：對外的接口接口的實現(xiàn)對集合運算的算法集合API的根是一個集合接口，存放于java.util包中。Collection接口定義了所有屬于集合的類都應(yīng)該具有的通用方法。82023/7/228.1Java中的集合類結(jié)構(gòu)Java集合框架結(jié)構(gòu)由兩顆接口樹構(gòu)成：第一棵樹根節(jié)點為Collection接口，它定義了所有集合的基本操作，如添加、刪除、遍歷等。它的子接口Set、List等則提供了更加特殊的功能。

92023/7/22Collection接口102023/7/22第二棵樹根節(jié)點為Map接口。與哈希表類似，保持的是鍵值對的集合，可以通過鍵來實現(xiàn)對值元素的快速訪問。112023/7/22Map接口第二棵樹根節(jié)點為Map接口。與哈希表類似，保持的是鍵值對的集合，可以通過鍵來實現(xiàn)對值元素的快速訪問。122023/7/22132023/7/228.2Collection接口方法名功能說明booleanadd(Objecto)插入單個對象booleanaddAll(Collectionc)添加另外一個集合對象c中的所有對象Object[]toArray()以數(shù)組的形式返回內(nèi)容Object[]toArray(Object[]a)以數(shù)組的形式返回內(nèi)容Iteratoriterator()返回一個實現(xiàn)了Iterator接口的對象voidclear()清空所有對象booleanremove(Objecto)刪除指定的對象booleanramoveAll(Collectionc)刪除c中所擁有的對象booleanretainAll(Collectionc)保留指定的對象booleancontains(Objecto)檢查是否包含有指定的對象booleancontainsAll(Collectionc)檢查是否包含c中所包含的對象booleanisEmpty()判斷集合是否為空intsize()獲取集合中的對象個數(shù)142023/7/2213.2List接口List接口是包含有序元素的一種Collection子接口，其中的元素必須按序存放。元素之間的順序關(guān)系可以由插入的時間先后決定，也可以由元素值的大小決定。List接口使用類似于數(shù)組下標(biāo)的索引的概念表示元素在List中的位置。用戶能夠使用索引來訪問List中的元素。索引從0開始。為了保持元素的有序的特性，List接口新增加了大量的方法，使之能夠在序列中間根據(jù)具體位置添加和刪除元素。

152023/7/22§13.2鏈表鏈表是由若干個稱作節(jié)點的對象組成的一種數(shù)據(jù)結(jié)構(gòu)，每個節(jié)點含有一個數(shù)據(jù)和下一個節(jié)點的引用。162023/7/22List接口的主要方法

方法名功能說明voidadd(intindex,Objectelement)在指定位置上添加一個對象booleanaddAll(intindex,Collectionc)將c中的所有對象添加到指定位置ListIteratorlistIterator()返回一個ListIteratorListIteratorlistIterator(intindex)返回指定的ListIteratorObjectget(intindex)返回指定位置的對象Objectremove(intindex)刪除指定位置的對象Objectset(intindex,objectelement)用元素element取代位置index上的元素,返回被取代的元素intindexOf(objecto)返回第一個匹配對象的位置intlastIndexOf(objecto)返回最后一個匹配對象的索引172023/7/2213.2.1LinkedList類

LinkedList類提供了使用雙向鏈表實現(xiàn)數(shù)據(jù)存儲的方法，可按序號檢索數(shù)據(jù)，并能夠進(jìn)行向前或向后遍歷。由于插入數(shù)據(jù)時只需要記錄元素的前后項即可，所以插入數(shù)度較快，因此適合于在鏈表中間需要頻繁進(jìn)行插入和刪除的操作。182023/7/22§13.2.1LinkedList<E>泛型類◆

LinkedList<E>泛型類創(chuàng)建的對象以鏈表結(jié)構(gòu)存儲數(shù)據(jù)，習(xí)慣上稱LinkedList類創(chuàng)建的對象為鏈表對象。例如，LinkedList<String>mylist=newLinkedList<String>();創(chuàng)建一個空雙鏈表。

◆

add(Eobj)向鏈表依次增加節(jié)點192023/7/22Linkedlist接口的主要方法

方法名功能說明publicbooleanadd(Objectelement)向鏈表末尾添加一個新的結(jié)點publicbooleanadd(intindex，Objecto)將對象o添加到鏈表中由index指定位置publicbooleanaddFirst(Objecto)將對象o添加到鏈表的頭部publicbooleanaddLast(Objecto)將對象向o添加到鏈表的末尾publicbooleanclear()刪除鏈表的所有節(jié)點，成為空鏈表publicObjectremove(intindex)刪除指定位置上的結(jié)點publicObjectremove(Objecto)刪除首次出現(xiàn)含有o的結(jié)點publicObjectget(intindex)返回鏈表中index位置處的結(jié)點對象202023/7/22

ArrayList類是List接口的一個可變長數(shù)組的實現(xiàn)，即一個ArrayList類對象可以動態(tài)改變大小。每個ArrayList類對象都有一個容量(Capacity)，用于存儲元素的數(shù)組的大小。容量可隨著不斷添加新元素而自動增加。序列以初始長度創(chuàng)建，當(dāng)長度超過時，集合自動變大；當(dāng)刪除對象時，集合自動變小。集合中允許存儲null值。ArrayList類的隨機訪問速度快，但是向表中插入和刪除比較慢。當(dāng)需要插入大量元素時，在插入前可以調(diào)用ensureCapacity方法來增加ArrayList的容量以提高插入效率。8.4.2ArrayList類212023/7/22ArrayList常用的構(gòu)造函數(shù)如下：ArrayList()：構(gòu)建一個空的ArrayList對象。ArrayList(Collectionc)：構(gòu)建一個ArrayList對象，并且將集合c中所有元素添加進(jìn)去。ArrayList(intinitialCapacity)：構(gòu)建一個擁有特定容量的空ArrayList對象。ArrayList的很多成員方法與LinkedList相似，兩者的本質(zhì)區(qū)別是一個使用順序結(jié)構(gòu)，另一個使用鏈表結(jié)構(gòu)，因此，它也可以使用LinkedList類提供的方法進(jìn)行列表的操作。8.4.2ArrayList類222023/7/22232023/7/228.5Iterator接口除了使用集合對象的get()方法可以實現(xiàn)對集合中的元素的遍歷外。利用迭代器(Iterator)也可以實現(xiàn)元素遍歷。

迭代器是一個實現(xiàn)了Iterator接口或者ListIterator接口的對象。ListIterator繼承了Iterator，可以進(jìn)行雙向遍歷以及元素的修改。242023/7/22252023/7/22

Iterator迭代器只能前向循環(huán)，如果需要雙向遍歷，則可以使用更高級的ListIterator迭代器，ListIterator接口繼承自Iterator接口。

ListIterator迭代器除了有next()方法外，還新增了hasprevious()方法和previous()方法，實現(xiàn)前向遍歷。ListIterator還可以定位當(dāng)前的索引位置，調(diào)用nextIndex()和previousIndex()就可以實現(xiàn)。

262023/7/22272023/7/22282023/7/2213.3Stack類在Java語言中，Stack類是java.util包中專門用來實現(xiàn)棧的工具類。Stack類繼承自Vector類，因此它是Vector的一個子類，實現(xiàn)了一個后進(jìn)先出的堆棧。Stack類繼承了Vector類的所有方法，還新增了一些方法使得Vector類能夠?qū)崿F(xiàn)堆棧的操作。292023/7/221、創(chuàng)建Stack類對象

publicStack()；它建立一個空的堆棧2、壓棧與出棧操作publicObjectpush(Objectitem)：將指定的對象壓入棧

publicObjectpop()：將棧頂?shù)膶ο髲臈Ｖ腥〕?、檢查棧是否為空

publicbooleanempty()：測試堆棧是否為空，若堆棧中沒有對象元素，則返回true，否則返回false4、查看棧頂端的數(shù)據(jù)，但不刪除該數(shù)據(jù)。

publicobjectpeek()5、獲取數(shù)據(jù)在堆棧中的位置。最頂端的位置是1，向下依次增加。如果堆棧不含有此數(shù)據(jù)，則返回-1。publicsearch(Objectdata)例:13.6302023/7/2213.4Map及HashMap接口312023/7/22Map接口的主要方法

方法名功能說明Objectput(Objectkey,Objectvalue)插入新的對象，并用key作為其鍵字voidputAll(Mapt)將另一個Map中的所有對象復(fù)制進(jìn)來SetentrySet()返回映射中的關(guān)鍵字－值對的集合SetkeySet()返回映射中所有關(guān)鍵字的集合Collectionvalues()返回映射中所有值的集合Objectremove(Objectkey)刪除指定的對象Objectget(Objectkey)獲取與key相聯(lián)系的對象booleancontainsKey(Objectkey)判斷是否包含指定的鍵值booleancontainsValue(Objectvalue)判斷是否包含指定的對象322023/7/22

Map接口的一個抽象類是AbstractMap。在這個抽象類中，部分地實現(xiàn)了Map接口中的成員方法，使得具體的映射類不必實現(xiàn)Map接口中的每個成員方法。AstractMap抽象類有三個子類：TreeMapHashMapWeakHashMap：

AstractMap抽象類332023/7/22

(1)TreeMap描述了一個按鍵值升序排列的映射,它有一些擴(kuò)展的方法，如firstKey()，lastKey()等，還可以從TreeMap中指定一個范圍以取得其子Map。

(2)HashMap描述的一個映射中允許存儲空對象，由于鍵必須唯一，所以只能有一個空鍵值。(3)WeakHashMap是一種改進(jìn)的HashMap，它描述了一個映射，當(dāng)集合中的某些內(nèi)容不再使用時需清除掉無用的數(shù)據(jù)，并使用垃圾回收機制進(jìn)行回收。AstractMap抽象類342023/7/22HashMap通過哈希運算可以快速查找一個鍵，因此在適合于在Map中插入、刪除和定位元素。如果要按照自然順序或者自定義順序遍歷關(guān)鍵字，TreeMap會更好些。

2．HashMap352023/7/22由于HashMap實現(xiàn)了Map接口，因此它沒有自己的新方法。HashMap的構(gòu)造方法如下：HashMap()：創(chuàng)建一個空的HashMap集合。HashMap(Mapt)：創(chuàng)建一個哈希集，將t中所有元素添加進(jìn)去。HashMap(intinitialCapacity)：創(chuàng)建一個擁有特定容量的空HashMap集合。HashMap(intinitialCapacity，floatloadFactor)：創(chuàng)建一個擁有特定容量和加載因子的空HashMap。362023/7/22

散列表中的容量

是指能夠存儲對象的數(shù)量。當(dāng)對象存儲的數(shù)目到達(dá)容量乘以加載因子的值時，容量將會自動地增加到原容量的2倍加1，加1的目的是確保散列表的容量為質(zhì)數(shù)或奇數(shù)。例如:aMap對象最初的容量為151，當(dāng)存儲對象的數(shù)量達(dá)到91時，容量將會自動增加到303。372023/7/22§13.4散列映射

§13.4.1HashMap<K,V>泛型類

HashMap<K,V>對象采用散列表這種數(shù)據(jù)結(jié)構(gòu)存儲數(shù)據(jù)，習(xí)慣上稱HashMap<K,V>對象為散列映射。例如HashMap<String,Student>hashtable=HashSet<String,Student>();hashtable可以存儲“鍵/值”對數(shù)據(jù)。

相關(guān)方法：publicVput(Kkey,Vvalue)將鍵/值對數(shù)據(jù)存放到散列映射中，該方法同時返回鍵所對應(yīng)的值。382023/7/22

loadFactor是0.01.0之間的一個數(shù)，通常默認(rèn)為0.75。加載因子定義了哈希集合充滿什么程度時就要增加容量。即當(dāng)元素的數(shù)目大于哈希集容量和加載因子之積時，哈希集容量將擴(kuò)展。392023/7/22HashMap類的主要成員方法方法描述Objectput(Objectkey,Objectvalue)用鍵值key存儲對象valuevoidputAll(Mapmap)將map中的所有鍵值/對象傳遞給當(dāng)前的散列表Objectget(Objectkey)返回鍵值key所對應(yīng)的對象remove(Objectkey)刪除key鍵值所對應(yīng)的對象SetKeySet()返回一個Set對象，其內(nèi)容為所有的鍵值SetentrySet()返回一個Set對象，其內(nèi)容為所有的鍵值/對象對Collectionvalues()返回一個Collection對象，其內(nèi)容為散列表中存儲的所有對象ObjectgetKey()返回對象的鍵值ObjectgetValue()返回所對應(yīng)的對象voidsetValue(Objectnew)將對象設(shè)置為new402023/7/22§13.4.2常用方法publicvoidclear()

清空散列映射。publicObjectclone()

返回當(dāng)前散列映射的一個克隆。publicbooleancontainsKey(Objectkey)

如果散列映射有“鍵/值”對使用了參數(shù)指定的鍵，方法返回true，否則返回false。publicbooleancontainsValue(Objectvalue)

如果散列映射有“鍵/值”對的值是參數(shù)指定的值。publicVget(Objectkey)

返回散列映射中使用key做鍵的“鍵/值”對中的值。publicbooleanisEmpty()

如果散列映射不含任何“鍵/值”對，方法返回true，否則返回false。publicVremove(Objectkey)

刪除散列映射中鍵為參數(shù)指定的“鍵/值”對，并返回鍵對應(yīng)的值。publicintsize()

返回散列映射的大小，即散列映射中“鍵/值”對的數(shù)目。412023/7/22§13.6樹映射

TreeMap<K,V>類實現(xiàn)了Map<K,V>接口，稱TreeMap<K,V>對象為樹映射。樹映射使用publicVput(Kkey,Vvalue);方法添加節(jié)點。例題13-9422023/7/22§13.4.3遍歷散列映射publicCollection<V>values()方法返回一個實現(xiàn)Collection<V>接口類創(chuàng)建的對象。使用接口回調(diào)技術(shù)，即將該對象的引用賦給Collection<V>接口變量，該接口變量可以回調(diào)iterator()方法獲取一個Iterator對象，這個Iterator對象存放著散列映射中所有“鍵/值”對中的“值”。432023/7/2213.5Set接口Set接口是一種不包含重復(fù)元素的Collection的子接口。Set接口中并沒有引入新方法，它提供的基本方法和Collection接口類似。442023/7/22452023/7/22Set接口派生了一個SortedSet接口和一個抽象類AbstractSet。SortedSet接口用來描述有序的元素集合，TreeSet實現(xiàn)了這個接口，它將放入其中的元素按序存放，要求其中的對象是可排序的。抽象類AbstractSet實現(xiàn)了部分Collection接口，并有一個子類HashSet，它以散列方式表示集合內(nèi)容。

462023/7/22§13.5樹集

§13.5.1TreeSet<E>泛型類

TreeSet<E>類創(chuàng)建的對象稱作樹集。例如TreeSet<String>mytree=newTreeSe<String>();然后使用add方法為樹集添加節(jié)點，例如mytree.add("boy");472023/7/22§13.5.2節(jié)點的大小關(guān)系

樹集用add方法添加節(jié)點，節(jié)點會按其存放的數(shù)據(jù)的“大小”順序一層一層地依次排列，在同一層中的節(jié)點從左到右按“大小”順序遞增排列，下一層的都比上一層的小。482023/7/22§13.5.3TreeSet類的常用方法publicbooleanadd(Eo)

向樹集添加加節(jié)點。publicvoidclear()

刪除樹集中的所有節(jié)點。publicvoidcontains(Objecto)

如果樹集中有包含參數(shù)指定的對象，該方法返回true，否則返回false。publicEfirst()

返回樹集中的第一個節(jié)點中的數(shù)據(jù)（最小的節(jié)點）。publicElast()

返回最后一個節(jié)點中的數(shù)據(jù)（最大的節(jié)點）。publicisEmpty()

判斷是否是空樹集，如果樹集不含任何節(jié)點，該方法返回true。publicbooleanremove(Objecto)

刪除樹集中的存儲參數(shù)指定的對象的最小節(jié)點。publicintsize()

返回樹集中節(jié)點的數(shù)目。例題13-8492023/7/22HashSet類

HashSet類是實現(xiàn)了Set接口的標(biāo)準(zhǔn)類，它創(chuàng)建了一個使用哈希表存儲的集合，能快速定位一個元素，從而可以優(yōu)化查詢的速度，特別是在查找大集合時HashSet類比較有用。HashSet的構(gòu)造函數(shù)如下：HashSet()：創(chuàng)建一個空的哈希集。HashSet(Collectionc)：創(chuàng)建一個哈希集，并且將集合c中所有元素添加進(jìn)去。HashSet(intinitialCapacity)：創(chuàng)建一個擁有特定容量的空哈希集。HashSet(intinitialCapacity，floatloadFactor)：創(chuàng)