第12章泛型与集合框架-ppt课件

1、12.1 泛型泛型 泛型泛型Generics是在是在JDK1.5中推出的，其主中推出的，其主要目的是可以建立具有类型平安的集合框架，如要目的是可以建立具有类型平安的集合框架，如链表、散列映射等数据构造链表、散列映射等数据构造 泛型的目的泛型的目的 Java泛型的主要目的是可以建立具有类型平安泛型的主要目的是可以建立具有类型平安的数据构造，如链表、散列表等数据构造，最重的数据构造，如链表、散列表等数据构造，最重要的一个优点就是：在运用这些泛型类建立的数要的一个优点就是：在运用这些泛型类建立的数据构造时，不用进展强迫类型转换，即不要求进据构造时，不用进展强迫类型转换，即不要求进展运转时类型检查。展

2、运转时类型检查。 JDK1.5是支持泛型的编译器，它将运转时的类是支持泛型的编译器，它将运转时的类型检查提早到编译时执行，使代码更平安。型检查提早到编译时执行，使代码更平安。12.1.1 泛型类泛型类 可以运用可以运用“class 称号称号声明一个类，声明一个类，为了和普通的类有所区别，这样声明的类称作泛为了和普通的类有所区别，这样声明的类称作泛型类，如：型类，如： class ShowObject E是其中的泛型，也就是并没有指定是其中的泛型，也就是并没有指定E是何种类是何种类型型 泛型类的类体和和普通类的类体完全类似，由成泛型类的类体和和普通类的类体完全类似，由成员变量和方法构成员变量和方

3、法构成 举例举例public class ShowObjectpublic showMess(E b) String mess=b.toString(); System.out.println(mess); 12.1.2 泛型类声明对象泛型类声明对象 和普通的类相比，泛型类声明和创建对象时，类和普通的类相比，泛型类声明和创建对象时，类名后多了一对名后多了一对“，而且必需求用详细的类型，而且必需求用详细的类型交换交换“中的泛型。中的泛型。 Dog.java public class Dog public String toString() return Cat.java public class

4、 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(); 阐明阐明 泛型类中的泛型变量只能调用泛型类中的泛型变量只能调用Object类中的方法，类中的方法，因此因此C

5、at和和Dog类都重写了类都重写了Object类的类的toString()方法。方法。12.1.3 泛型接口泛型接口 可以运用可以运用“interface 称号称号声明一声明一个接口，这样声名的接口称作泛型接口如个接口，这样声名的接口称作泛型接口如 interface Listen void listen(E x); 注：普通类实现泛型接口时，必需指定泛型接口注：普通类实现泛型接口时，必需指定泛型接口中泛型列表中的详细类型中泛型列表中的详细类型例例12-2interface Listen void listen(E x);class Student implements Listen publ

6、ic 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(钢琴协奏曲钢琴协奏曲:黄河黄河); class Violin public void play() System.out.println(小提琴协奏曲小提琴协奏曲:梁祝梁祝); public class Example12_2 public static void main(String

7、args ) Student zhang=new Student(); System.out.println(学生听学生听:); zhang.listen(new Piano(); Teacher teacher=new Teacher(); System.out.println(教师听教师听:); teacher.listen(new Violin(); Java集合框架集合框架 在在Java言语中，设计者对常用的数据构造和算言语中，设计者对常用的数据构造和算法做了一些规范接口和实现详细实现接口法做了一些规范接口和实现详细实现接口的类。的类。 一切笼统出来的数据构造和算法统称为一切笼统出来的

8、数据构造和算法统称为Java集集合框架合框架 Java程序员在详细运用时，不用思索数据构造程序员在详细运用时，不用思索数据构造和算法实现细节，只需求用这些类创建出来的一和算法实现细节，只需求用这些类创建出来的一些对象，然后直接运用就可以了，提高了编程效些对象，然后直接运用就可以了，提高了编程效率率Java 容器类容器类 容器类可以大大提高编程效率和编程才干容器类可以大大提高编程效率和编程才干 Java2容器类类库的用途是容器类类库的用途是“保管对象，它分保管对象，它分为两类：为两类： Collection-一组独立的元素，通常这些元素都一组独立的元素，通常这些元素都服从某种规那么。服从某种规那

9、么。List必需坚持元素特定的顺序，必需坚持元素特定的顺序，而而Set不能有反复元素。不能有反复元素。 Map-一组成对的一组成对的“键值对对象，即其元素键值对对象，即其元素是成对的对象是成对的对象集合框架的层次构造集合框架的层次构造阐明阐明 Collection是集合接口，集合框架的根是集合接口，集合框架的根,代表一组代表一组Object Set子接口：里面的元素不允许反复子接口：里面的元素不允许反复 List子接口：里面的元素可以反复子接口：里面的元素可以反复阐明阐明 Set和和List对比：对比： Set：检索元素效率低下，删除和插入效率高。：检索元素效率低下，删除和插入效率高。 插入和

10、删除不会引起元素位置改动插入和删除不会引起元素位置改动 List：和数组类似，：和数组类似，List可以动态增长，查找元可以动态增长，查找元素效率高。素效率高。阐明阐明 Set的子类：的子类： HashSet 以哈希表的方式存放元素，插入删除速度很快以哈希表的方式存放元素，插入删除速度很快 TreeSet 坚持次序的坚持次序的Set，底层为树构造。运用它可以从，底层为树构造。运用它可以从Set中提取有序的序列。中提取有序的序列。 List的子类：的子类： ArrayList：动态数组顺序构造：动态数组顺序构造 LinkedList：链表链式构造：链表链式构造12.2 链表链表 链表是由假设干个

11、称作节点的对象组成的一种数链表是由假设干个称作节点的对象组成的一种数据构造，每个节点含有一个数据和下一个节点的据构造，每个节点含有一个数据和下一个节点的援用，或含有一个数据并含有上一个节点的援用援用，或含有一个数据并含有上一个节点的援用和下一个节点的援用和下一个节点的援用 数据数据援用援用援用援用数据数据null援用援用数据数据援用援用援用援用数据数据援用援用 null图图12.3 双链表表示图双链表表示图12.2.1 LinkedList泛型类泛型类 java.util包中的包中的LinkedList泛型类创建的对泛型类创建的对象以链表构造存储数据，习惯上称象以链表构造存储数据，习惯上称Li

12、nkedList类类创建的对象为链表对象。例如，创建的对象为链表对象。例如， LinkedList list = new LinkedList(); 创建一个空双链表。创建一个空双链表。 运用运用LinkedList泛型类声明创建链表时，必泛型类声明创建链表时，必需求指定需求指定E的详细类型，然后链表就可以运用的详细类型，然后链表就可以运用add(E obj)方法向链表依次添加节点方法向链表依次添加节点 举例举例 list.add(“他好他好); list.add(“十一高兴十一高兴); list.add(“留意休憩留意休憩); 此时，链表里有此时，链表里有3个节点，节点自动链接在一同个节点，

13、节点自动链接在一同12.2.2 常用方法常用方法 以下是以下是LinkedList泛型类实现泛型类实现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) public int lastIn

14、dexOf(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 E removeLas

15、t() public Object clone() 12.2.3 遍历链表遍历链表 当用户需求遍历集合中的对象时，该当运用该集当用户需求遍历集合中的对象时，该当运用该集合提供的迭代器，而不是让集合本身来遍历其中合提供的迭代器，而不是让集合本身来遍历其中的对象。由于迭代器遍历集合的方法在找到集合的对象。由于迭代器遍历集合的方法在找到集合中的一个对象的同时，也得到待遍历的后继对象中的一个对象的同时，也得到待遍历的后继对象的援用，因此迭代器可以快速地遍历集合。的援用，因此迭代器可以快速地遍历集合。什么是迭代器什么是迭代器 迭代器是一个实现了迭代器是一个实现了Iterator接口的类的对象接口的类的对

16、象 一切实现了一切实现了Collection接口的类都有一个称号为接口的类都有一个称号为iterator的方法来获取迭代器的方法来获取迭代器 链表对象可以运用链表对象可以运用iterator()方法获取一个方法获取一个Iterator对象，该对象就是针对当前链表的迭代对象，该对象就是针对当前链表的迭代器器 next方法：前往迭代器中的一个元素方法：前往迭代器中的一个元素 hasNext方法：假设容器里还有元素，那么为方法：假设容器里还有元素，那么为true例例12-3 import java.util.*; public class Example12_3 public static void

17、 main(String args ) List list=new LinkedList(); list.add(大家好大家好); list.add(国庆国庆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.size();i+) S

18、tring te=list.get(i); System.out.print(te+ ); JDK1.5之前没有泛型的之前没有泛型的LinkedList类，可以用类，可以用普通的普通的LinkedList创建一个链表对象，如创建一个链表对象，如 LinkedList mylist=new LinkedList(); 然后然后mylist链表可以运用链表可以运用add(Object obj)方法方法向这个链表依次添加节点。由于任何类都是向这个链表依次添加节点。由于任何类都是Object类的子类，因此可以把任何一个对象作为类的子类，因此可以把任何一个对象作为链表节点中的对象链表节点中的对象 运用集

19、合框架本卷须知没有运用泛型运用集合框架本卷须知没有运用泛型ObjectObjectObject参与集合参与集合从集合中取出从集合中取出(Rabbit) object(Car) object(Student) objectRabbitCarStudentRabbitCarStudent任何对象参与集合类后，自动转变为任何对象参与集合类后，自动转变为ObjectObject类型；取出类型；取出时，需求进展强迫类型转换，恢复为特定的类型时，需求进展强迫类型转换，恢复为特定的类型 例例12-4 运用了运用了JDK1.5版本之前的版本之前的LinkedList12.2.4 排序与查找排序与查找 假设链表

20、中的数据是实现了假设链表中的数据是实现了Comparable接口的接口的类的实例，比如类的实例，比如String对象，那么对象，那么Java.util包中包中的的Collections类调用类调用sort(List list)方法可方法可以对参数指定的列表进展排序，即按节点中的存以对参数指定的列表进展排序，即按节点中的存储的对象的大小升序陈列节点。储的对象的大小升序陈列节点。 Collections类类 留意区分和留意区分和Collection接口的的区别接口的的区别 Collections是一个类，该类里的是一个类，该类里的 方法都是静态方法都是静态的方法，主要是用来对集合的操作的。的方法，

21、主要是用来对集合的操作的。 是个非常有用的类是个非常有用的类 String类实现了泛型接口类实现了泛型接口Comparable中的中的compareTo(E b)方法，使得字符串可以按字典方法，使得字符串可以按字典序比较大小，假设一个链表序比较大小，假设一个链表list如下添加节点：如下添加节点： list.add(bird); list.add(apple); list.add(cat); 那么用那么用sort方法排序方法排序list： Collection.sort(list); 之后，之后，list中三个节点中的数据将依次是中三个节点中的数据将依次是apple，bird和和cat。如何比

22、较两个对象如何比较两个对象 一个类可以实现泛型接口一个类可以实现泛型接口Comparable中的中的comareTo(E b)方法来指定该类实例相互比较大小关方法来指定该类实例相互比较大小关系的准那么，实现系的准那么，实现Comparable接口类创建的对接口类创建的对象可以调用象可以调用compareTo(E b)方法和参数指定的对象方法和参数指定的对象比较大小关系。假设比较大小关系。假设a和和b是实现是实现Comparable接接口类创建的两个对象，当口类创建的两个对象，当 apareTo(b)0 时，称时，称a大于大于b， apareTo(b)=0， 时，称时，称a等于等于b。如何查找一

23、个对象如何查找一个对象 当链表节点中的对象是实现泛型接口当链表节点中的对象是实现泛型接口Comparable的类的实例时，就可以运用的类的实例时，就可以运用sort方法对链表进展排序操作。方法对链表进展排序操作。 有时需求查找链表中能否含有和指定数据相等的有时需求查找链表中能否含有和指定数据相等的数据，那么首先要对链表排序，然后运用数据，那么首先要对链表排序，然后运用Collections类里的类里的 public static int binarySearch(List list, T key) 查找链表中能否含有和数据查找链表中能否含有和数据key相等的数据相等的数据 12-512.2.5

24、 洗牌与旋转洗牌与旋转 Collections类还提供了将链表中的数据重新随类还提供了将链表中的数据重新随机陈列的类方法以及旋转链表中数据的类方法，机陈列的类方法以及旋转链表中数据的类方法，方法的详细解释如下方法的详细解释如下 public static void shuffle(List list)：随机：随机陈列陈列list中的节点。中的节点。 static void rotate(List list, int distance)：旋转：旋转链表中的节点，调用该方法后，链表中的节点，调用该方法后，list索引为索引为i的节点中的节点中的数据将是调用该方法前索引为的数据将是调用该方法前索引为

25、(i-distance) mod list.size()的节点中的数据。的节点中的数据。 例如，假设例如，假设list节点数据依次为：节点数据依次为：a b c d e，那么执，那么执行行Collections.rotate(list,1)之后，之后，list节点数据依次节点数据依次为为e a b c d。当方法的参数。当方法的参数distance取正值时，向右取正值时，向右转动转动list中的数据，取负值时向左转动中的数据，取负值时向左转动list中的数据。中的数据。图图12.6 洗牌与旋转洗牌与旋转 public static void reverse(List list)：翻转：翻转li

26、st中的数据。假设中的数据。假设list节点中的数据依次为：节点中的数据依次为：a b c d e，那么在那么在Collections.reverse(list)之后，之后，list节点中的节点中的数据依次为数据依次为e d c b a。 12-6，12-7 12-7：假设干个人围成一圈，从某个人开场顺时：假设干个人围成一圈，从某个人开场顺时针数到第针数到第3个人，该人丛圈中退出，然后继续顺个人，该人丛圈中退出，然后继续顺时针数到第时针数到第3个人，该人从圈中退出，依次类推，个人，该人从圈中退出，依次类推，程序输出圈中最后剩下的人程序输出圈中最后剩下的人12.3 堆栈堆栈 堆栈是一种堆栈是一种

27、“后进先出的数据构造后进先出的数据构造 运用运用java.util包中的包中的Stack泛型类创建一个泛型类创建一个堆栈对象，堆栈对象可以运用堆栈对象，堆栈对象可以运用 public E push(E item); 实现压栈操作。运用实现压栈操作。运用 public E pop(); 实现出栈操作。实现出栈操作。 运用运用 public boolean empty(); 判别堆栈能否还有数据，有数据前往判别堆栈能否还有数据，有数据前往false ，否，否那么前往那么前往true。运用。运用 public E peek(); 获取堆栈顶端的数据，但不删除该数据。运用获取堆栈顶端的数据，但不删除该

28、数据。运用 public int search(Object data); 获取数据在堆栈中的位置，最顶端的位置是，获取数据在堆栈中的位置，最顶端的位置是，向下依次添加，假设堆栈不含此数据，那么前往向下依次添加，假设堆栈不含此数据，那么前往-1。12-8Fibonacci数列，用栈实现数列，用栈实现12.4 散列映射散列映射:HashMap 关于关于Map: 实现实现Map接口的对象会将键接口的对象会将键Key)映射至值映射至值Value 值指的是要存入容器的对象。值指的是要存入容器的对象。 在将对象存入在将对象存入Map对象时，需求同时给定一个键，对象时，需求同时给定一个键，要取回对象时可以

29、指定，这样就可以获得与键对要取回对象时可以指定，这样就可以获得与键对应的对象值。应的对象值。 Map中每一个键都是独一的，不能有反复的键。中每一个键都是独一的，不能有反复的键。 Map拥有本人的排序机制拥有本人的排序机制Map承继关系承继关系MapSortedMapHashtableLinkedHashMapHashMapTreeMap12.4.1 HashMap泛型类泛型类 HashMap泛型类实现了泛型接口泛型类实现了泛型接口Map，HashMap类中的绝大部分方类中的绝大部分方法都是法都是Map接口方法的实现。接口方法的实现。 编程时，可以运用接口回调技术，即把编程时，可以运用接口回调技

30、术，即把HashMap对象的援用赋值给对象的援用赋值给Map接接口变量，那么接口变量就可以调用类实现的接口口变量，那么接口变量就可以调用类实现的接口方法方法 HashMap对象采用散列表这种数据构造对象采用散列表这种数据构造存储数据，习惯上称存储数据，习惯上称HashMap对象为散对象为散列映射或哈希映射。散列映射用于存储列映射或哈希映射。散列映射用于存储“键键/值值对，允许把任何数量的对，允许把任何数量的“键键/值对存储在一同。值对存储在一同。键不可以发生逻辑冲突，即不要两个数据项运用键不可以发生逻辑冲突，即不要两个数据项运用一样的键，假设出现两个数据项对应一样的键，一样的键，假设出现两个数

31、据项对应一样的键，那么，先前散列映射中的那么，先前散列映射中的“键键/值对将被交换值对将被交换 HashMap中常用方法中常用方法 public V put(K key,V value) 该方法将键值对对象存放到映射中该方法将键值对对象存放到映射中 public V get(Object key) 前往散列映射中运前往散列映射中运用用key做键的做键的“键键/值对中的值值对中的值 import java.util.*; public class HashMapDemopublic static void main(String args)Map map1=new HashMap();Strin

32、g 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() 前往当前散列映射的一个克隆。前往当前散列映射的一个克隆。 public boolean containsKey(Object key) 假设散列映射有假设散列映射有“键键/值对

33、运用了参数指定的键，方法前往值对运用了参数指定的键，方法前往true，否那么前往，否那么前往false。 public boolean containsValue(Object value) 假设散列映射假设散列映射有有“键键/值对的值是参数指定的值，方法前往值对的值是参数指定的值，方法前往true，否那么前，否那么前往往false。 public boolean isEmpty() 假设散列映射不含任何假设散列映射不含任何“键键/值值对，方法前往对，方法前往true，否那么前往，否那么前往false。 public V remove(Object key) 删除散列映射中键为参数指定删除散列

34、映射中键为参数指定的的“键键/值对，并前往键对应的值。值对，并前往键对应的值。 public int size() 前往散列映射的大小，即散列映射中前往散列映射的大小，即散列映射中“键键/值值对的数目。对的数目。12.4.3 遍历散列映射遍历散列映射 HashMap类里：类里：public Collection values()方法前往一个实现方法前往一个实现Collection接口类创建的接口类创建的对象，其中包括一切值对象。对象，其中包括一切值对象。 可以运用接口回调技术，即将该对象的援用赋给可以运用接口回调技术，即将该对象的援用赋给Collection接口变量，该接口变量可以回调接口变量

35、，该接口变量可以回调iterator()方法获取一个方法获取一个Iterator对象，这个对象，这个Iterator对象存放着散列映射中一切对象存放着散列映射中一切“键键/值对值对中的中的“值值 import java.util.*; public class HashMapDemopublic static void main(String args)Map map1=new HashMap();map1.put(book,书书);map1.put(apple,苹果苹果);map1.put(Language,言语言语);Collection c1=map1.values();Iterator

36、 it1=c1.iterator();while(it1.hasNext() System.out.println(it1.next();System.out.println();for(String s:map1.values() System.out.println(s); 思索思索 1输出的次序并不是按当初参与的次序输出输出的次序并不是按当初参与的次序输出的的 2假设想要在迭代一切的对象时，按照插入假设想要在迭代一切的对象时，按照插入的顺序来陈列，那么可以运用的顺序来陈列，那么可以运用LinkedHashMap，它是它是HashMap的子类。的子类。 3只需是实现只需是实现Collect

37、ion接口的对象，都可接口的对象，都可以运用加强的以运用加强的for循环功能来迭代一切的值循环功能来迭代一切的值12.4.3 基于散列映射的查询基于散列映射的查询 对于经常需求进展查找的数据可以采用散列映射对于经常需求进展查找的数据可以采用散列映射来存储这样的数据，即为数据指定一个查找它的来存储这样的数据，即为数据指定一个查找它的关键字，然后按着关键字，然后按着“健健-值对，将关键字和数值对，将关键字和数据一并存入散列映射中据一并存入散列映射中 例例12-9 英语单词查询的运用程序英语单词查询的运用程序12.5 树集树集 12.5.1 TreeSet泛型类泛型类 TreeSet类是实现类是实现

38、Set接口和接口和SortedSet接口接口的类的类 SortedSet提供的方法让他有序得取出对应位置提供的方法让他有序得取出对应位置的对象。的对象。 TreeSet类创建的对象称作树集。类创建的对象称作树集。树集树集 树集采用树构造存储数据，树节点中的数据会按树集采用树构造存储数据，树节点中的数据会按存放的数据的存放的数据的“大小顺序一层一层地依次陈列，大小顺序一层一层地依次陈列，在同一层中的节点从左到右按字从小大递增陈列，在同一层中的节点从左到右按字从小大递增陈列，下一层的都比上一层的小下一层的都比上一层的小 运用运用 import java.util.*; public class T

39、reeSetDemo1 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对象，执行结果会自动按照字对象，执行结果会自动按照字典顺序进展陈列。典顺序进展陈列。 按照字典顺序来陈列按照字典顺序来陈列String对象是对象是TreeSet默许默许的的12.5.2 节点的大小关系节

40、点的大小关系 当一个树集中的数据是实现当一个树集中的数据是实现Comparable泛型泛型接口类创建的对象时，节点就按对象的大小关系接口类创建的对象时，节点就按对象的大小关系顺序陈列顺序陈列12.5.3 TreeSet类的常用方法类的常用方法 public boolean add(E o) 向树集添加加节点，节点中的数据向树集添加加节点，节点中的数据由参数指定，添加胜利前往由参数指定，添加胜利前往true，否那么前往，否那么前往false。 public void clear() 删除树集中的一切节点。删除树集中的一切节点。 public void contains(Object o) 假设树

41、集中有包含参数指定假设树集中有包含参数指定的对象，该方法前往的对象，该方法前往true，否那么前往，否那么前往false 。 public E first() 前往树集中的第一个节点中的数据最小的节前往树集中的第一个节点中的数据最小的节点。点。 public E last() 前往最后一个节点中的数据最大的节点。前往最后一个节点中的数据最大的节点。 public isEmpty() 判别能否是空树集，假设树集不含任何节点，判别能否是空树集，假设树集不含任何节点，该方法前往该方法前往true 。 public boolean remove(Object o) 删除树集中的存储参数指删除树集中的存储参数指定的对象的最小节点，假设删除胜利，该方法前往定的对象的最小节点，假设删除胜利，该方法前往true，否那，否那么前往么前往false。 public int size() 前往树集中节点的数目前往树集中节点的数目 例例12-10 树集按