泛型與集合框架ppt課件

1、第12章泛型與集合框架 12.1 泛型泛型 泛型泛型Generics是在是在JDK1.5中推出的，其主中推出的，其主要目的是可以建立具有類型平安的集合框架，如要目的是可以建立具有類型平安的集合框架，如鏈表、散列映射等數(shù)據(jù)構(gòu)造鏈表、散列映射等數(shù)據(jù)構(gòu)造 泛型的目的泛型的目的 Java泛型的主要目的是可以建立具有類型平安泛型的主要目的是可以建立具有類型平安的數(shù)據(jù)構(gòu)造，如鏈表、散列表等數(shù)據(jù)構(gòu)造，最重的數(shù)據(jù)構(gòu)造，如鏈表、散列表等數(shù)據(jù)構(gòu)造，最重要的一個(gè)優(yōu)點(diǎn)就是：在運(yùn)用這些泛型類建立的數(shù)要的一個(gè)優(yōu)點(diǎn)就是：在運(yùn)用這些泛型類建立的數(shù)據(jù)構(gòu)造時(shí)，不用進(jìn)展強(qiáng)迫類型轉(zhuǎn)換，即不要求進(jìn)據(jù)構(gòu)造時(shí)，不用進(jìn)展強(qiáng)迫類型轉(zhuǎn)換，即不要

2、求進(jìn)展運(yùn)轉(zhuǎn)時(shí)類型檢查。展運(yùn)轉(zhuǎn)時(shí)類型檢查。 JDK1.5是支持泛型的編譯器，它將運(yùn)轉(zhuǎn)時(shí)的類是支持泛型的編譯器，它將運(yùn)轉(zhuǎn)時(shí)的類型檢查提早到編譯時(shí)執(zhí)行，使代碼更平安。型檢查提早到編譯時(shí)執(zhí)行，使代碼更平安。12.1.1 泛型類泛型類 可以運(yùn)用可以運(yùn)用“class 稱號(hào)稱號(hào)聲明一個(gè)類，聲明一個(gè)類，為了和普通的類有所區(qū)別，這樣聲明的類稱作泛為了和普通的類有所區(qū)別，這樣聲明的類稱作泛型類，如：型類，如： class ShowObject E是其中的泛型，也就是并沒有指定是其中的泛型，也就是并沒有指定E是何種類是何種類型型 泛型類的類體和和普通類的類體完全類似，由成泛型類的類體和和普通類的類體完全類似，由成員

3、變量和方法構(gòu)成員變量和方法構(gòu)成 舉例舉例public class ShowObjectpublic showMess(E b) String mess=b.toString(); System.out.println(mess); 12.1.2 泛型類聲明對(duì)象泛型類聲明對(duì)象 和普通的類相比，泛型類聲明和創(chuàng)建對(duì)象時(shí)，類和普通的類相比，泛型類聲明和創(chuàng)建對(duì)象時(shí)，類名后多了一對(duì)名后多了一對(duì)“，而且必需求用詳細(xì)的類型，而且必需求用詳細(xì)的類型交換交換“中的泛型。中的泛型。 Dog.java public class Dog public String toString() return Cat.java

4、public class Cat public String toString() return 一只小花貓一只小花貓; public class Example12_1 public static void main(String args ) ShowObject showDog = new ShowObject(); showDog.showMess(new Dog(); ShowObject showCat = new ShowObject(); showCat.showMess(new Cat(); 闡明闡明 泛型類中的泛型變量只能調(diào)用泛型類中的泛型變量只能調(diào)用Object類中的方法

5、，類中的方法，因此因此Cat和和Dog類都重寫了類都重寫了Object類的類的toString()方法。方法。12.1.3 泛型接口泛型接口 可以運(yùn)用可以運(yùn)用“interface 稱號(hào)稱號(hào)聲明一個(gè)聲明一個(gè)接口，這樣聲名的接口稱作泛型接口如接口，這樣聲名的接口稱作泛型接口如 interface Listen void listen(E x); 注：普通類實(shí)現(xiàn)泛型接口時(shí)，必需指定泛型接口注：普通類實(shí)現(xiàn)泛型接口時(shí)，必需指定泛型接口中泛型列表中的詳細(xì)類型中泛型列表中的詳細(xì)類型例例12-2interface Listen void listen(E x);class Student implements

6、 Listen public void listen(Piano p) p.play(); class Teacher implements Listen public void listen(Violin v) v.play(); class Piano public void play() System.out.println(鋼琴協(xié)奏曲鋼琴協(xié)奏曲:黃河黃河); class Violin public void play() System.out.println(小提琴協(xié)奏曲小提琴協(xié)奏曲:梁祝梁祝); public class Example12_2 public static void

7、main(String args ) Student zhang=new Student(); System.out.println(學(xué)生聽學(xué)生聽:); zhang.listen(new Piano(); Teacher teacher=new Teacher(); System.out.println(教師聽教師聽:); teacher.listen(new Violin(); Java集合框架集合框架 在在Java言語(yǔ)中，設(shè)計(jì)者對(duì)常用的數(shù)據(jù)構(gòu)造和算言語(yǔ)中，設(shè)計(jì)者對(duì)常用的數(shù)據(jù)構(gòu)造和算法做了一些規(guī)范接口和實(shí)現(xiàn)詳細(xì)實(shí)現(xiàn)接口法做了一些規(guī)范接口和實(shí)現(xiàn)詳細(xì)實(shí)現(xiàn)接口的類。的類。 一切籠統(tǒng)出來(lái)的數(shù)據(jù)構(gòu)造和

8、算法統(tǒng)稱為一切籠統(tǒng)出來(lái)的數(shù)據(jù)構(gòu)造和算法統(tǒng)稱為Java集集合框架合框架 Java程序員在詳細(xì)運(yùn)用時(shí)，不用思索數(shù)據(jù)構(gòu)造程序員在詳細(xì)運(yùn)用時(shí)，不用思索數(shù)據(jù)構(gòu)造和算法實(shí)現(xiàn)細(xì)節(jié)，只需求用這些類創(chuàng)建出來(lái)的一和算法實(shí)現(xiàn)細(xì)節(jié)，只需求用這些類創(chuàng)建出來(lái)的一些對(duì)象，然后直接運(yùn)用就可以了，提高了編程效些對(duì)象，然后直接運(yùn)用就可以了，提高了編程效率率Java 容器類容器類 容器類可以大大提高編程效率和編程才干容器類可以大大提高編程效率和編程才干 Java2容器類類庫(kù)的用途是容器類類庫(kù)的用途是“保管對(duì)象，它分保管對(duì)象，它分為兩類：為兩類： Collection-一組獨(dú)立的元素，通常這些元素一組獨(dú)立的元素，通常這些元素都服從某

9、種規(guī)那么。都服從某種規(guī)那么。List必需堅(jiān)持元素特定的順必需堅(jiān)持元素特定的順序，而序，而Set不能有反復(fù)元素。不能有反復(fù)元素。 Map-一組成對(duì)的一組成對(duì)的“鍵值對(duì)對(duì)象，即其元素是鍵值對(duì)對(duì)象，即其元素是成對(duì)的對(duì)象成對(duì)的對(duì)象集合框架的層次構(gòu)造集合框架的層次構(gòu)造闡明闡明 Collection是集合接口，集合框架的根是集合接口，集合框架的根,代表一組代表一組Object Set子接口：里面的元素不允許反復(fù)子接口：里面的元素不允許反復(fù) List子接口：里面的元素可以反復(fù)子接口：里面的元素可以反復(fù)闡明闡明 Set和和List對(duì)比：對(duì)比： Set：檢索元素效率低下，刪除和插入效率高。：檢索元素效率低下，刪

10、除和插入效率高。 插入和刪除不會(huì)引起元素位置改動(dòng)插入和刪除不會(huì)引起元素位置改動(dòng) List：和數(shù)組類似，：和數(shù)組類似，List可以動(dòng)態(tài)增長(zhǎng)，查找元可以動(dòng)態(tài)增長(zhǎng)，查找元素效率高。素效率高。闡明闡明 Set的子類：的子類： HashSet 以哈希表的方式存放元素，插入刪除速度很快以哈希表的方式存放元素，插入刪除速度很快 TreeSet 堅(jiān)持次序的堅(jiān)持次序的Set，底層為樹構(gòu)造。運(yùn)用它可以從，底層為樹構(gòu)造。運(yùn)用它可以從Set中提取有序的序列。中提取有序的序列。 List的子類：的子類： ArrayList：動(dòng)態(tài)數(shù)組順序構(gòu)造：動(dòng)態(tài)數(shù)組順序構(gòu)造 LinkedList：鏈表鏈?zhǔn)綐?gòu)造：鏈表鏈?zhǔn)綐?gòu)造12.2 鏈

11、表鏈表 鏈表是由假設(shè)干個(gè)稱作節(jié)點(diǎn)的對(duì)象組成的一種數(shù)鏈表是由假設(shè)干個(gè)稱作節(jié)點(diǎn)的對(duì)象組成的一種數(shù)據(jù)構(gòu)造，每個(gè)節(jié)點(diǎn)含有一個(gè)數(shù)據(jù)和下一個(gè)節(jié)點(diǎn)的據(jù)構(gòu)造，每個(gè)節(jié)點(diǎn)含有一個(gè)數(shù)據(jù)和下一個(gè)節(jié)點(diǎn)的援用，或含有一個(gè)數(shù)據(jù)并含有上一個(gè)節(jié)點(diǎn)的援用援用，或含有一個(gè)數(shù)據(jù)并含有上一個(gè)節(jié)點(diǎn)的援用和下一個(gè)節(jié)點(diǎn)的援用和下一個(gè)節(jié)點(diǎn)的援用 數(shù)據(jù)數(shù)據(jù)援用援用援用援用數(shù)據(jù)數(shù)據(jù)null援用援用數(shù)據(jù)數(shù)據(jù)援用援用援用援用數(shù)據(jù)數(shù)據(jù)援用援用 null圖圖12.3 雙鏈表表示圖雙鏈表表示圖12.2.1 LinkedList泛型類泛型類 java.util包中的包中的LinkedList泛型類創(chuàng)建的對(duì)泛型類創(chuàng)建的對(duì)象以鏈表構(gòu)造存儲(chǔ)數(shù)據(jù)，習(xí)慣上稱象以鏈表構(gòu)

12、造存儲(chǔ)數(shù)據(jù)，習(xí)慣上稱LinkedList類類創(chuàng)建的對(duì)象為鏈表對(duì)象。例如，創(chuàng)建的對(duì)象為鏈表對(duì)象。例如， LinkedList list = new LinkedList(); 創(chuàng)建一個(gè)空雙鏈表。創(chuàng)建一個(gè)空雙鏈表。 運(yùn)用運(yùn)用LinkedList泛型類聲明創(chuàng)建鏈表時(shí)，必泛型類聲明創(chuàng)建鏈表時(shí)，必需求指定需求指定E的詳細(xì)類型，然后鏈表就可以運(yùn)用的詳細(xì)類型，然后鏈表就可以運(yùn)用add(E obj)方法向鏈表依次添加節(jié)點(diǎn)方法向鏈表依次添加節(jié)點(diǎn) 舉例舉例 list.add(“他好他好); list.add(“十一高興十一高興); list.add(“留意休憩留意休憩); 此時(shí)，鏈表里有此時(shí)，鏈表里有3個(gè)節(jié)點(diǎn)，節(jié)

13、點(diǎn)自動(dòng)鏈接在一同個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)自動(dòng)鏈接在一同12.2.2 常用方法常用方法 以下是以下是LinkedList泛型類實(shí)現(xiàn)泛型類實(shí)現(xiàn)Lis泛型接口中泛型接口中的一些常用方法。的一些常用方法。 public boolean add(E element) public void add(int index ,E element) public void clear() public E remove(int index) public boolean remove(E element) public E get(int index) public int indexOf(E element) publi

14、c int lastIndexOf(E element) public E set(int index ,E element) public int size() public boolean contains(Object element) 以下是以下是LinkedList泛型類本身新添加的一些泛型類本身新添加的一些常用方法常用方法 public void addFirst(E element) public void addLast(E element) public E getFirst() public E getLast() public E removeFirst() public

15、 E removeLast() public Object clone() 12.2.3 遍歷鏈表遍歷鏈表 當(dāng)用戶需求遍歷集合中的對(duì)象時(shí)，該當(dāng)運(yùn)用該集當(dāng)用戶需求遍歷集合中的對(duì)象時(shí)，該當(dāng)運(yùn)用該集合提供的迭代器，而不是讓集合本身來(lái)遍歷其中合提供的迭代器，而不是讓集合本身來(lái)遍歷其中的對(duì)象。由于迭代器遍歷集合的方法在找到集合的對(duì)象。由于迭代器遍歷集合的方法在找到集合中的一個(gè)對(duì)象的同時(shí)，也得到待遍歷的后繼對(duì)象中的一個(gè)對(duì)象的同時(shí)，也得到待遍歷的后繼對(duì)象的援用，因此迭代器可以快速地遍歷集合。的援用，因此迭代器可以快速地遍歷集合。什么是迭代器什么是迭代器 迭代器是一個(gè)實(shí)現(xiàn)了迭代器是一個(gè)實(shí)現(xiàn)了Iterator接

16、口的類的對(duì)象接口的類的對(duì)象 一切實(shí)現(xiàn)了一切實(shí)現(xiàn)了Collection接口的類都有一個(gè)稱號(hào)為接口的類都有一個(gè)稱號(hào)為iterator的方法來(lái)獲取迭代器的方法來(lái)獲取迭代器 鏈表對(duì)象可以運(yùn)用鏈表對(duì)象可以運(yùn)用iterator()方法獲取一個(gè)方法獲取一個(gè)Iterator對(duì)象，該對(duì)象就是針對(duì)當(dāng)前鏈表的迭代對(duì)象，該對(duì)象就是針對(duì)當(dāng)前鏈表的迭代器器 next方法：前往迭代器中的一個(gè)元素方法：前往迭代器中的一個(gè)元素 hasNext方法：假設(shè)容器里還有元素，那么為方法：假設(shè)容器里還有元素，那么為true例例12-3 import java.util.*; public class Example12_3 public

17、 static void main(String args ) List list=new LinkedList(); list.add(大家好大家好); list.add(國(guó)慶國(guó)慶60周年周年); list.add(十一高興十一高興); Iterator iter=list.iterator(); while(iter.hasNext() String te=iter.next(); System.out.print(te+ ); System.out.println(); long endTime=System.currentTimeMillis(); for(int i=0;ilist.

18、size();i+) String te=list.get(i); System.out.print(te+ ); JDK1.5之前沒有泛型的之前沒有泛型的LinkedList類，可以用類，可以用普通的普通的LinkedList創(chuàng)建一個(gè)鏈表對(duì)象，如創(chuàng)建一個(gè)鏈表對(duì)象，如 LinkedList mylist=new LinkedList(); 然后然后mylist鏈表可以運(yùn)用鏈表可以運(yùn)用add(Object obj)方法方法向這個(gè)鏈表依次添加節(jié)點(diǎn)。由于任何類都是向這個(gè)鏈表依次添加節(jié)點(diǎn)。由于任何類都是Object類的子類，因此可以把任何一個(gè)對(duì)象作為類的子類，因此可以把任何一個(gè)對(duì)象作為鏈表節(jié)點(diǎn)中的對(duì)象

19、鏈表節(jié)點(diǎn)中的對(duì)象 運(yùn)用集合框架本卷須知沒有運(yùn)用泛型運(yùn)用集合框架本卷須知沒有運(yùn)用泛型ObjectObjectObject參與集合參與集合從集合中取出從集合中取出(Rabbit) object(Car) object(Student) objectRabbitCarStudentRabbitCarStudent任何對(duì)象參與集合類后，自動(dòng)轉(zhuǎn)變?yōu)槿魏螌?duì)象參與集合類后，自動(dòng)轉(zhuǎn)變?yōu)镺bjectObject類型；取出類型；取出時(shí)，需求進(jìn)展強(qiáng)迫類型轉(zhuǎn)換，恢復(fù)為特定的類型時(shí)，需求進(jìn)展強(qiáng)迫類型轉(zhuǎn)換，恢復(fù)為特定的類型 例例12-4 運(yùn)用了運(yùn)用了JDK1.5版本之前的版本之前的LinkedList12.2.4 排序與

20、查找排序與查找 假設(shè)鏈表中的數(shù)據(jù)是實(shí)現(xiàn)了假設(shè)鏈表中的數(shù)據(jù)是實(shí)現(xiàn)了Comparable接口的接口的類的實(shí)例，比如類的實(shí)例，比如String對(duì)象，那么對(duì)象，那么Java.util包中包中的的Collections類調(diào)用類調(diào)用sort(List list)方法可方法可以對(duì)參數(shù)指定的列表進(jìn)展排序，即按節(jié)點(diǎn)中的存以對(duì)參數(shù)指定的列表進(jìn)展排序，即按節(jié)點(diǎn)中的存儲(chǔ)的對(duì)象的大小升序陳列節(jié)點(diǎn)。儲(chǔ)的對(duì)象的大小升序陳列節(jié)點(diǎn)。 Collections類類 留意區(qū)分和留意區(qū)分和Collection接口的的區(qū)別接口的的區(qū)別 Collections是一個(gè)類，該類里的是一個(gè)類，該類里的 方法都是靜態(tài)方法都是靜態(tài)的方法，主要是用來(lái)

21、對(duì)集合的操作的。的方法，主要是用來(lái)對(duì)集合的操作的。 是個(gè)非常有用的類是個(gè)非常有用的類 String類實(shí)現(xiàn)了泛型接口類實(shí)現(xiàn)了泛型接口Comparable中的中的compareTo(E b)方法，使得字符串可以按字典方法，使得字符串可以按字典序比較大小，假設(shè)一個(gè)鏈表序比較大小，假設(shè)一個(gè)鏈表list如下添加節(jié)點(diǎn)：如下添加節(jié)點(diǎn)： list.add(bird); list.add(apple); list.add(cat); 那么用那么用sort方法排序方法排序list： Collection.sort(list); 之后，之后，list中三個(gè)節(jié)點(diǎn)中的數(shù)據(jù)將依次是中三個(gè)節(jié)點(diǎn)中的數(shù)據(jù)將依次是apple，b

22、ird和和cat。如何比較兩個(gè)對(duì)象如何比較兩個(gè)對(duì)象 一個(gè)類可以實(shí)現(xiàn)泛型接口一個(gè)類可以實(shí)現(xiàn)泛型接口Comparable中的中的comareTo(E b)方法來(lái)指定該類實(shí)例相互比較大小關(guān)方法來(lái)指定該類實(shí)例相互比較大小關(guān)系的準(zhǔn)那么，實(shí)現(xiàn)系的準(zhǔn)那么，實(shí)現(xiàn)Comparable接口類創(chuàng)建的對(duì)接口類創(chuàng)建的對(duì)象可以調(diào)用象可以調(diào)用compareTo(E b)方法和參數(shù)指定的對(duì)象方法和參數(shù)指定的對(duì)象比較大小關(guān)系。假設(shè)比較大小關(guān)系。假設(shè)a和和b是實(shí)現(xiàn)是實(shí)現(xiàn)Comparable接接口類創(chuàng)建的兩個(gè)對(duì)象，當(dāng)口類創(chuàng)建的兩個(gè)對(duì)象，當(dāng) apareTo(b)0 時(shí)，稱時(shí)，稱a大于大于b， apareTo(b)=0， 時(shí)，稱時(shí)，稱

23、a等于等于b。如何查找一個(gè)對(duì)象如何查找一個(gè)對(duì)象 當(dāng)鏈表節(jié)點(diǎn)中的對(duì)象是實(shí)現(xiàn)泛型接口當(dāng)鏈表節(jié)點(diǎn)中的對(duì)象是實(shí)現(xiàn)泛型接口Comparable的類的實(shí)例時(shí)，就可以運(yùn)用的類的實(shí)例時(shí)，就可以運(yùn)用sort方法對(duì)鏈表進(jìn)展排序操作。方法對(duì)鏈表進(jìn)展排序操作。 有時(shí)需求查找鏈表中能否含有和指定數(shù)據(jù)相等的有時(shí)需求查找鏈表中能否含有和指定數(shù)據(jù)相等的數(shù)據(jù)，那么首先要對(duì)鏈表排序，然后運(yùn)用數(shù)據(jù)，那么首先要對(duì)鏈表排序，然后運(yùn)用Collections類里的類里的 public static int binarySearch(List list, T key) 查找鏈表中能否含有和數(shù)據(jù)查找鏈表中能否含有和數(shù)據(jù)key相等的數(shù)據(jù)相等的數(shù)

24、據(jù) 12-512.2.5 洗牌與旋轉(zhuǎn)洗牌與旋轉(zhuǎn) Collections類還提供了將鏈表中的數(shù)據(jù)重新隨類還提供了將鏈表中的數(shù)據(jù)重新隨機(jī)陳列的類方法以及旋轉(zhuǎn)鏈表中數(shù)據(jù)的類方法，機(jī)陳列的類方法以及旋轉(zhuǎn)鏈表中數(shù)據(jù)的類方法，方法的詳細(xì)解釋如下方法的詳細(xì)解釋如下 public static void shuffle(List list)：隨機(jī)：隨機(jī)陳列陳列l(wèi)ist中的節(jié)點(diǎn)。中的節(jié)點(diǎn)。 static void rotate(List list, int distance)：旋轉(zhuǎn)：旋轉(zhuǎn)鏈表中的節(jié)點(diǎn)，調(diào)用該方法后，鏈表中的節(jié)點(diǎn)，調(diào)用該方法后，list索引為索引為i的節(jié)點(diǎn)中的節(jié)點(diǎn)中的數(shù)據(jù)將是調(diào)用該方法前索引為的數(shù)

25、據(jù)將是調(diào)用該方法前索引為(i-distance) mod list.size()的節(jié)點(diǎn)中的數(shù)據(jù)。的節(jié)點(diǎn)中的數(shù)據(jù)。 例如，假設(shè)例如，假設(shè)list節(jié)點(diǎn)數(shù)據(jù)依次為：節(jié)點(diǎn)數(shù)據(jù)依次為：a b c d e，那么執(zhí)，那么執(zhí)行行Collections.rotate(list,1)之后，之后，list節(jié)點(diǎn)數(shù)據(jù)依次節(jié)點(diǎn)數(shù)據(jù)依次為為e a b c d。當(dāng)方法的參數(shù)。當(dāng)方法的參數(shù)distance取正值時(shí)，向右取正值時(shí)，向右轉(zhuǎn)動(dòng)轉(zhuǎn)動(dòng)list中的數(shù)據(jù)，取負(fù)值時(shí)向左轉(zhuǎn)動(dòng)中的數(shù)據(jù)，取負(fù)值時(shí)向左轉(zhuǎn)動(dòng)list中的數(shù)據(jù)。中的數(shù)據(jù)。圖圖12.6 洗牌與旋轉(zhuǎn)洗牌與旋轉(zhuǎn) public static void reverse(List l

26、ist)：翻轉(zhuǎn)：翻轉(zhuǎn)list中的數(shù)據(jù)。假設(shè)中的數(shù)據(jù)。假設(shè)list節(jié)點(diǎn)中的數(shù)據(jù)依次為：節(jié)點(diǎn)中的數(shù)據(jù)依次為：a b c d e，那么在那么在Collections.reverse(list)之后，之后，list節(jié)點(diǎn)中的節(jié)點(diǎn)中的數(shù)據(jù)依次為數(shù)據(jù)依次為e d c b a。 12-6，12-7 12-7：假設(shè)干個(gè)人圍成一圈，從某個(gè)人開場(chǎng)順時(shí)：假設(shè)干個(gè)人圍成一圈，從某個(gè)人開場(chǎng)順時(shí)針數(shù)到第針數(shù)到第3個(gè)人，該人叢圈中退出，然后繼續(xù)順個(gè)人，該人叢圈中退出，然后繼續(xù)順時(shí)針數(shù)到第時(shí)針數(shù)到第3個(gè)人，該人從圈中退出，依次類推，個(gè)人，該人從圈中退出，依次類推，程序輸出圈中最后剩下的人程序輸出圈中最后剩下的人12.3 堆棧堆

27、棧 堆棧是一種堆棧是一種“后進(jìn)先出的數(shù)據(jù)構(gòu)造后進(jìn)先出的數(shù)據(jù)構(gòu)造 運(yùn)用運(yùn)用java.util包中的包中的Stack泛型類創(chuàng)建一個(gè)泛型類創(chuàng)建一個(gè)堆棧對(duì)象，堆棧對(duì)象可以運(yùn)用堆棧對(duì)象，堆棧對(duì)象可以運(yùn)用 public E push(E item); 實(shí)現(xiàn)壓棧操作。運(yùn)用實(shí)現(xiàn)壓棧操作。運(yùn)用 public E pop(); 實(shí)現(xiàn)出棧操作。實(shí)現(xiàn)出棧操作。 運(yùn)用運(yùn)用 public boolean empty(); 判別堆棧能否還有數(shù)據(jù)，有數(shù)據(jù)前往判別堆棧能否還有數(shù)據(jù)，有數(shù)據(jù)前往false ，否，否那么前往那么前往true。運(yùn)用。運(yùn)用 public E peek(); 獲取堆棧頂端的數(shù)據(jù)，但不刪除該數(shù)據(jù)。運(yùn)用獲取堆

28、棧頂端的數(shù)據(jù)，但不刪除該數(shù)據(jù)。運(yùn)用 public int search(Object data); 獲取數(shù)據(jù)在堆棧中的位置，最頂端的位置是，獲取數(shù)據(jù)在堆棧中的位置，最頂端的位置是，向下依次添加，假設(shè)堆棧不含此數(shù)據(jù)，那么前往向下依次添加，假設(shè)堆棧不含此數(shù)據(jù)，那么前往-1。12-8Fibonacci數(shù)列，用棧實(shí)現(xiàn)數(shù)列，用棧實(shí)現(xiàn)12.4 散列映射散列映射:HashMap 關(guān)于關(guān)于Map: 實(shí)現(xiàn)實(shí)現(xiàn)Map接口的對(duì)象會(huì)將鍵接口的對(duì)象會(huì)將鍵Key)映射至值映射至值Value 值指的是要存入容器的對(duì)象。值指的是要存入容器的對(duì)象。 在將對(duì)象存入在將對(duì)象存入Map對(duì)象時(shí)，需求同時(shí)給定一個(gè)鍵，對(duì)象時(shí)，需求同時(shí)給定

29、一個(gè)鍵，要取回對(duì)象時(shí)可以指定，這樣就可以獲得與鍵對(duì)要取回對(duì)象時(shí)可以指定，這樣就可以獲得與鍵對(duì)應(yīng)的對(duì)象值。應(yīng)的對(duì)象值。 Map中每一個(gè)鍵都是獨(dú)一的，不能有反復(fù)的鍵。中每一個(gè)鍵都是獨(dú)一的，不能有反復(fù)的鍵。 Map擁有本人的排序機(jī)制擁有本人的排序機(jī)制Map承繼關(guān)系承繼關(guān)系MapSortedMapHashtableLinkedHashMapHashMapTreeMap12.4.1 HashMap泛型類泛型類 HashMap泛型類實(shí)現(xiàn)了泛型接口泛型類實(shí)現(xiàn)了泛型接口Map，HashMap類中的絕大部分方類中的絕大部分方法都是法都是Map接口方法的實(shí)現(xiàn)。接口方法的實(shí)現(xiàn)。 編程時(shí)，可以運(yùn)用接口回調(diào)技術(shù)，即把編

30、程時(shí)，可以運(yùn)用接口回調(diào)技術(shù)，即把HashMap對(duì)象的援用賦值給對(duì)象的援用賦值給Map接接口變量，那么接口變量就可以調(diào)用類實(shí)現(xiàn)的接口口變量，那么接口變量就可以調(diào)用類實(shí)現(xiàn)的接口方法方法 HashMap對(duì)象采用散列表這種數(shù)據(jù)構(gòu)造對(duì)象采用散列表這種數(shù)據(jù)構(gòu)造存儲(chǔ)數(shù)據(jù)，習(xí)慣上稱存儲(chǔ)數(shù)據(jù)，習(xí)慣上稱HashMap對(duì)象為散對(duì)象為散列映射或哈希映射。散列映射用于存儲(chǔ)列映射或哈希映射。散列映射用于存儲(chǔ)“鍵鍵/值值對(duì)，允許把任何數(shù)量的對(duì)，允許把任何數(shù)量的“鍵鍵/值對(duì)存儲(chǔ)在一同。值對(duì)存儲(chǔ)在一同。鍵不可以發(fā)生邏輯沖突，即不要兩個(gè)數(shù)據(jù)項(xiàng)運(yùn)用鍵不可以發(fā)生邏輯沖突，即不要兩個(gè)數(shù)據(jù)項(xiàng)運(yùn)用一樣的鍵，假設(shè)出現(xiàn)兩個(gè)數(shù)據(jù)項(xiàng)對(duì)應(yīng)一樣的鍵，

31、一樣的鍵，假設(shè)出現(xiàn)兩個(gè)數(shù)據(jù)項(xiàng)對(duì)應(yīng)一樣的鍵，那么，先前散列映射中的那么，先前散列映射中的“鍵鍵/值對(duì)將被交換值對(duì)將被交換 HashMap中常用方法中常用方法 public V put(K key,V value) 該方法將鍵值對(duì)對(duì)象存放到映射中該方法將鍵值對(duì)對(duì)象存放到映射中 public V get(Object key) 前往散列映射中運(yùn)前往散列映射中運(yùn)用用key做鍵的做鍵的“鍵鍵/值對(duì)中的值值對(duì)中的值 import java.util.*; public class HashMapDemopublic static void main(String args)Map map1=new Has

32、hMap();String key1=book;String key2=apple;map1.put(key1,書書);map1.put(key2,蘋果蘋果);System.out.println(map1.get(key1);System.out.println(map1.get(key2); HashMap中常用方法中常用方法 public void clear() 清空散列映射。清空散列映射。 public Object clone() 前往當(dāng)前散列映射的一個(gè)克隆。前往當(dāng)前散列映射的一個(gè)克隆。 public boolean containsKey(Object key) 假設(shè)散列映射有假

33、設(shè)散列映射有“鍵鍵/值對(duì)運(yùn)用了參數(shù)指定的鍵，方法前往值對(duì)運(yùn)用了參數(shù)指定的鍵，方法前往true，否那么前往，否那么前往false。 public boolean containsValue(Object value) 假設(shè)散列映射假設(shè)散列映射有有“鍵鍵/值對(duì)的值是參數(shù)指定的值，方法前往值對(duì)的值是參數(shù)指定的值，方法前往true，否那么前，否那么前往往false。 public boolean isEmpty() 假設(shè)散列映射不含任何假設(shè)散列映射不含任何“鍵鍵/值值對(duì)，方法前往對(duì)，方法前往true，否那么前往，否那么前往false。 public V remove(Object key) 刪除散列映

34、射中鍵為參數(shù)指定刪除散列映射中鍵為參數(shù)指定的的“鍵鍵/值對(duì)，并前往鍵對(duì)應(yīng)的值。值對(duì)，并前往鍵對(duì)應(yīng)的值。 public int size() 前往散列映射的大小，即散列映射中前往散列映射的大小，即散列映射中“鍵鍵/值值對(duì)的數(shù)目。對(duì)的數(shù)目。12.4.3 遍歷散列映射遍歷散列映射 HashMap類里：類里：public Collection values()方法前往一個(gè)實(shí)現(xiàn)方法前往一個(gè)實(shí)現(xiàn)Collection接口類創(chuàng)建的接口類創(chuàng)建的對(duì)象，其中包括一切值對(duì)象。對(duì)象，其中包括一切值對(duì)象。 可以運(yùn)用接口回調(diào)技術(shù)，即將該對(duì)象的援用賦給可以運(yùn)用接口回調(diào)技術(shù)，即將該對(duì)象的援用賦給Collection接口變量，該

35、接口變量可以回調(diào)接口變量，該接口變量可以回調(diào)iterator()方法獲取一個(gè)方法獲取一個(gè)Iterator對(duì)象，這個(gè)對(duì)象，這個(gè)Iterator對(duì)象存放著散列映射中一切對(duì)象存放著散列映射中一切“鍵鍵/值對(duì)值對(duì)中的中的“值值 import java.util.*; public class HashMapDemopublic static void main(String args)Map map1=new HashMap();map1.put(book,書書);map1.put(apple,蘋果蘋果);map1.put(Language,言語(yǔ)言語(yǔ));Collection c1=map1.value

36、s();Iterator it1=c1.iterator();while(it1.hasNext() System.out.println(it1.next();System.out.println();for(String s:map1.values() System.out.println(s); 思索思索 1輸出的次序并不是按當(dāng)初參與的次序輸出輸出的次序并不是按當(dāng)初參與的次序輸出的的 2假設(shè)想要在迭代一切的對(duì)象時(shí)，按照插入假設(shè)想要在迭代一切的對(duì)象時(shí)，按照插入的順序來(lái)陳列，那么可以運(yùn)用的順序來(lái)陳列，那么可以運(yùn)用LinkedHashMap，它是它是HashMap的子類。的子類。 3只需是實(shí)現(xiàn)

37、只需是實(shí)現(xiàn)Collection接口的對(duì)象，都可接口的對(duì)象，都可以運(yùn)用加強(qiáng)的以運(yùn)用加強(qiáng)的for循環(huán)功能來(lái)迭代一切的值循環(huán)功能來(lái)迭代一切的值12.4.3 基于散列映射的查詢基于散列映射的查詢 對(duì)于經(jīng)常需求進(jìn)展查找的數(shù)據(jù)可以采用散列映射對(duì)于經(jīng)常需求進(jìn)展查找的數(shù)據(jù)可以采用散列映射來(lái)存儲(chǔ)這樣的數(shù)據(jù)，即為數(shù)據(jù)指定一個(gè)查找它的來(lái)存儲(chǔ)這樣的數(shù)據(jù)，即為數(shù)據(jù)指定一個(gè)查找它的關(guān)鍵字，然后按著關(guān)鍵字，然后按著“健健-值對(duì)，將關(guān)鍵字和數(shù)據(jù)值對(duì)，將關(guān)鍵字和數(shù)據(jù)一并存入散列映射中一并存入散列映射中 例例12-9 英語(yǔ)單詞查詢的運(yùn)用程序英語(yǔ)單詞查詢的運(yùn)用程序12.5 樹集樹集 12.5.1 TreeSet泛型類泛型類 Tre

38、eSet類是實(shí)現(xiàn)類是實(shí)現(xiàn)Set接口和接口和SortedSet接口接口的類的類 SortedSet提供的方法讓他有序得取出對(duì)應(yīng)位置提供的方法讓他有序得取出對(duì)應(yīng)位置的對(duì)象。的對(duì)象。 TreeSet類創(chuàng)建的對(duì)象稱作樹集。類創(chuàng)建的對(duì)象稱作樹集。樹集樹集 樹集采用樹構(gòu)造存儲(chǔ)數(shù)據(jù)，樹節(jié)點(diǎn)中的數(shù)據(jù)會(huì)按樹集采用樹構(gòu)造存儲(chǔ)數(shù)據(jù)，樹節(jié)點(diǎn)中的數(shù)據(jù)會(huì)按存放的數(shù)據(jù)的存放的數(shù)據(jù)的“大小順序一層一層地依次陳列，大小順序一層一層地依次陳列，在同一層中的節(jié)點(diǎn)從左到右按字從小大遞增陳列，在同一層中的節(jié)點(diǎn)從左到右按字從小大遞增陳列，下一層的都比上一層的小下一層的都比上一層的小 運(yùn)用運(yùn)用 import java.util.*; pu

39、blic class TreeSetDemo1 public static void main(String args)Set set1=new TreeSet();set1.add(book);set1.add(boy);set1.add(apple);set1.add(zoo);for(String name:set1) System.out.println(name); 闡明闡明 由于參與的由于參與的String對(duì)象，執(zhí)行結(jié)果會(huì)自動(dòng)按照字對(duì)象，執(zhí)行結(jié)果會(huì)自動(dòng)按照字典順序進(jìn)展陳列。典順序進(jìn)展陳列。 按照字典順序來(lái)陳列按照字典順序來(lái)陳列String對(duì)象是對(duì)象是TreeSet默許默許的的12.

40、5.2 節(jié)點(diǎn)的大小關(guān)系節(jié)點(diǎn)的大小關(guān)系 當(dāng)一個(gè)樹集中的數(shù)據(jù)是實(shí)現(xiàn)當(dāng)一個(gè)樹集中的數(shù)據(jù)是實(shí)現(xiàn)Comparable泛型泛型接口類創(chuàng)建的對(duì)象時(shí)，節(jié)點(diǎn)就按對(duì)象的大小關(guān)系接口類創(chuàng)建的對(duì)象時(shí)，節(jié)點(diǎn)就按對(duì)象的大小關(guān)系順序陳列順序陳列12.5.3 TreeSet類的常用方法類的常用方法 public boolean add(E o) 向樹集添加加節(jié)點(diǎn)，節(jié)點(diǎn)中的數(shù)據(jù)向樹集添加加節(jié)點(diǎn)，節(jié)點(diǎn)中的數(shù)據(jù)由參數(shù)指定，添加勝利前往由參數(shù)指定，添加勝利前往true，否那么前往，否那么前往false。 public void clear() 刪除樹集中的一切節(jié)點(diǎn)。刪除樹集中的一切節(jié)點(diǎn)。 public void contains(O

41、bject o) 假設(shè)樹集中有包含參數(shù)指定假設(shè)樹集中有包含參數(shù)指定的對(duì)象，該方法前往的對(duì)象，該方法前往true，否那么前往，否那么前往false 。 public E first() 前往樹集中的第一個(gè)節(jié)點(diǎn)中的數(shù)據(jù)最小的節(jié)前往樹集中的第一個(gè)節(jié)點(diǎn)中的數(shù)據(jù)最小的節(jié)點(diǎn)。點(diǎn)。 public E last() 前往最后一個(gè)節(jié)點(diǎn)中的數(shù)據(jù)最大的節(jié)點(diǎn)。前往最后一個(gè)節(jié)點(diǎn)中的數(shù)據(jù)最大的節(jié)點(diǎn)。 public isEmpty() 判別能否是空樹集，假設(shè)樹集不含任何節(jié)點(diǎn)，判別能否是空樹集，假設(shè)樹集不含任何節(jié)點(diǎn)，該方法前往該方法前往true 。 public boolean remove(Object o) 刪除樹集中的存儲(chǔ)參數(shù)指刪除樹集中的存儲(chǔ)參數(shù)指定的對(duì)象的最小節(jié)點(diǎn)，假設(shè)刪除勝利，該方法前往定的對(duì)象的最小節(jié)點(diǎn)，假設(shè)刪除勝利，該方法前往true，否那，否那么前往么前往false。 public int size() 前往樹集中節(jié)點(diǎn)的數(shù)目前往樹集中節(jié)點(diǎn)的數(shù)目 例例12-10 樹集