《泛型与集合框架骄阳书苑》由会员分享，可在线阅读，更多相关《泛型与集合框架骄阳书苑（116页珍藏版）》请在金锄头文库上搜索。
1、网 络 程 序 设 计JAVAJAVA网络程序设计网络程序设计SsandyYao1骄阳书苑泛型与集合框架泛型与集合框架P136 P136 例例7-77-7P137 P137 例例7-87-8P140 P140 例例7-107-10P141 P141 例例7-117-11P143 P143 例例7-127-122骄阳书苑P145 P145 例例7-137-13P146 P146 例例7-147-14P148 P148 例例7-157-15P149 P149 作业题作业题3-43-4泛型与集合框架泛型与集合框架3骄阳书苑1 LinkedList1 LinkedList泛型类泛型类2 HashSet
2、2 HashSet泛型类泛型类3 HashMap3 HashMap泛型类泛型类4 TreeSet4 TreeSet泛型类泛型类5 TreeMap5 TreeMap泛型类泛型类6 Stack6 Stack泛型类泛型类泛型与集合框架泛型与集合框架4骄阳书苑什么是集合框架 集合框架：集合框架：是为表示和操作集是为表示和操作集合而规定的一种统一标准的体系结构。合而规定的一种统一标准的体系结构。 集合中只能容纳对象。集合中只能容纳对象。 对象会自动扩展，以容纳添加到其对象会自动扩展，以容纳添加到其中的所有对象。中的所有对象。 Java 2 Java 2的集合类型被统一组织在的集合类型被统一组织在Java
3、Java集合框架（集合框架（Java Collections Java Collections FrameworkFramework）当中。）当中。5骄阳书苑什么是集合框架JavaJava的集合框架提供了一套设计优良的接口的集合框架提供了一套设计优良的接口和类，使程序员操作成批的数据或对象元素和类，使程序员操作成批的数据或对象元素极为方便，极大的减化了程序员编程时的负极为方便，极大的减化了程序员编程时的负担。担。JavaJava的集合框架的核心接口为：的集合框架的核心接口为：Collection、Map、Iterator，这三个接口是以后要使用的，这三个接口是以后要使用的最重要，最多的接口。最
4、重要，最多的接口。Java 2Java 2的集合类型被统一组织在的集合类型被统一组织在JavaJava集合框集合框架（架（Java Collections FrameworkJava Collections Framework）当中。）当中。6骄阳书苑什么是集合框架CollectionListSetMapSortedSetSortedMapArrayListLinkedListHashSetTreeSetHashMapTreeMapAbstractListAbstractSetAbstractMapAbstractSequentialListAbstractCollection7骄阳书苑什么是
5、集合框架按具体集合类使用上的特性来分的话，主要按具体集合类使用上的特性来分的话，主要有三类：有三类：List、Set和和Map。List是有序的，但允许重复。是有序的，但允许重复。Set是无序的，但不允许重复。是无序的，但不允许重复。Map主要表现的是键值对的概念。主要表现的是键值对的概念。8骄阳书苑集合与数组的区别数组是定长，即创建后固定不变；集合是不数组是定长，即创建后固定不变；集合是不定长的，其长度可以动态增长或减少。定长的，其长度可以动态增长或减少。数组是同构的，即数组中的元素是相同的类数组是同构的，即数组中的元素是相同的类型；集合可以是异构的，当然也可以通过泛型；集合可以是异构的，当
6、然也可以通过泛型创建类型安全的同构集合。型创建类型安全的同构集合。数组中可以存放基本数据类型或对象；集合数组中可以存放基本数据类型或对象；集合只存放对象。只存放对象。9骄阳书苑Collection接口Collection接口是在整个接口是在整个Java集合中集合中List和和Set的父接口，此接口定义如下：的父接口，此接口定义如下：public interface Collection extends Iterable此接口使用了泛型。此接口使用了泛型。10骄阳书苑Collection接口常用方法：常用方法：add(E e)/remove(Object o)添加或移除元素。添加或移除元素。cl
7、ear() 清空集合中的所有元素。清空集合中的所有元素。contains(Object o)如果此集合包含指定的元素，则返回如果此集合包含指定的元素，则返回true。iterator() 返回在此集合内的元素的迭代器。返回在此集合内的元素的迭代器。size() 获取集合获取集合 中的元素个数。中的元素个数。toArray()/toArray(T a)返回包含些集合中的所有元素的数组。返回包含些集合中的所有元素的数组。11骄阳书苑List接口List是是Collection的子接口，里面的所有内容的子接口，里面的所有内容都是允许重复。都是允许重复。它在它在Collection接口的基础上做了不少
8、的扩接口的基础上做了不少的扩展。比较典型的方法有：展。比较典型的方法有：add()，get()，remove()，listIterator()。12骄阳书苑什么是迭代器模式迭代器模式：提供一种方法，它能够用来遍迭代器模式：提供一种方法，它能够用来遍历（访问）集合的部分或全部元素，而又不历（访问）集合的部分或全部元素，而又不暴露其内部的表示。暴露其内部的表示。Java的集合框架已经实现好了迭代器模式，的集合框架已经实现好了迭代器模式，只需要使用即可。只需要使用即可。13骄阳书苑什么是链表？ 以以链式结构链式结构存储的线性表称之为线性链存储的线性表称之为线性链表。表。 特点是该线性表中的数据元素可
9、以用任特点是该线性表中的数据元素可以用任意的存储单元来存储。线性表中逻辑相邻的意的存储单元来存储。线性表中逻辑相邻的两元素的存储空间可以是不连续的。为表示两元素的存储空间可以是不连续的。为表示逻辑上的顺序关系，对表的每个数据元素除逻辑上的顺序关系，对表的每个数据元素除存储本身的信息之外，还需存储一个指示其存储本身的信息之外，还需存储一个指示其直接衔接的信息。这两部分信息组成数据元直接衔接的信息。这两部分信息组成数据元素的存储映象，称为结点。素的存储映象，称为结点。14骄阳书苑7.4 LinkedList泛型类 使用使用LinkedListLinkedList泛型类可以创建泛型类可以创建链表结构
10、的数据对象。链表是由若干个链表结构的数据对象。链表是由若干个节点组成的一个种数据结构，每个节点节点组成的一个种数据结构，每个节点含有一个数据和下一个节点的引用（单含有一个数据和下一个节点的引用（单链表），或含有一个数据以及上一个节链表），或含有一个数据以及上一个节点的引用和下一个节点的引用（双链表）点的引用和下一个节点的引用（双链表），节点的索引从，节点的索引从0 0开始。链表适合动态改开始。链表适合动态改变它存储的数据，如增加、删除节点等。变它存储的数据，如增加、删除节点等。15骄阳书苑7.4 LinkedList泛型类1 1、LinkedListLinkedList对象对象 java.ut
11、iljava.util包中的包中的LinkedListLinkedList泛泛型类创建的对象以链表结构存储数据，型类创建的对象以链表结构存储数据，习惯上称习惯上称LinkedListLinkedList类创建的对象为类创建的对象为链表对象。例如，链表对象。例如，LinkedList mylist=new LinkedList mylist=new LinkedList();LinkedList();16骄阳书苑7.4 LinkedList泛型类创建一个空双链表。然后创建一个空双链表。然后mylistmylist可以可以使用使用add(String obj)add(String obj)方法向链
12、表依方法向链表依次增加节点，节点中的数据是参数次增加节点，节点中的数据是参数objobj指定对象的引用，如：指定对象的引用，如： mylist.add(mylist.add(“HowHow”);); mylist.add( mylist.add(“AreAre”);); mylist.add( mylist.add(“YouYou”););17骄阳书苑7.4 LinkedList泛型类 mylist.add(“Java”); 这时，双链表这时，双链表mylistmylist就有了就有了4 4个个节点，节点是自动连接在一起的，不节点，节点是自动连接在一起的，不需要我们再去做连接。也就是说，不需要
13、我们再去做连接。也就是说，不需要我们去操作安排节点中所存放的需要我们去操作安排节点中所存放的下一个或上一个节点的引用。下一个或上一个节点的引用。18骄阳书苑7.4 LinkedList泛型类2 2、常用方法、常用方法 以下是以下是LinkedListLinkedList泛型类的泛型类的一些常用方法：一些常用方法：lpublic boolean add(E public boolean add(E element)element)向链表的末尾添加一个向链表的末尾添加一个新的节点，该节点中的数据是参数新的节点，该节点中的数据是参数elementelement指定的对象。指定的对象。19骄阳书苑7.
14、4 LinkedList泛型类lpublic void add(int index,E element)向链表的指定位置添向链表的指定位置添加一个新的节点，该节点中的数据是加一个新的节点，该节点中的数据是参数参数elementelement指定的对象。指定的对象。lpublic void addFirst(E element)向链表的头添加一个新向链表的头添加一个新的节点，该节点中的数据是参数的节点，该节点中的数据是参数elementelement指定的对象。指定的对象。20骄阳书苑7.4 LinkedList泛型类lpublic void addLast(E element)向链表的末尾添加
15、一向链表的末尾添加一个新的节点，该节点中的数据是参数个新的节点，该节点中的数据是参数elementelement指定的对象。指定的对象。lpublic void clear()删除链删除链表中的所有节点，使当前链表成为空表中的所有节点，使当前链表成为空链表。链表。21骄阳书苑7.4 LinkedList泛型类lpublic E remove(int index)删除链表中指定位置上的节点。删除链表中指定位置上的节点。lpublic boolean remove(E element)删除首次出现含有数删除首次出现含有数据据elementelement的节点。的节点。lpublic E remov
16、eFirst()删除删除链表中第一个节点，并返回这个节点链表中第一个节点，并返回这个节点中的对象。中的对象。22骄阳书苑7.4 LinkedList泛型类lpublic E removeLast()删除删除链表中最后一个节点，并返回这个节链表中最后一个节点，并返回这个节点中的对象。点中的对象。lpublic E get(int index)得到得到链表中指定位置处节点中的对象。链表中指定位置处节点中的对象。lpublic E getFirst()得到链表得到链表中第一个节点的对象。中第一个节点的对象。23骄阳书苑7.4 LinkedList泛型类lpublic E getLast()得到链表中
17、最后一得到链表中最后一个节点的对象。个节点的对象。lpublic int indexOf(E element)返回返回含有数据含有数据elementelement的节点在链表中首次出现的的节点在链表中首次出现的位置，如果链表中无此节点则返回位置，如果链表中无此节点则返回-1-1。lpublic int lastindexOf(E element)返返回含有数据回含有数据elementelement的节点在链表中最后出现的节点在链表中最后出现的位置，如果链表中无此节点则返回的位置，如果链表中无此节点则返回-1-1。24骄阳书苑7.4 LinkedList泛型类lpublic E set(int
18、index,E element)将当前链表将当前链表indexindex位位置节点中的对象替换为参数置节点中的对象替换为参数elementelement指定的对象，并返回被替换的对象。指定的对象，并返回被替换的对象。lpublic int size()返回链表的返回链表的长度，即节点的个数。长度，即节点的个数。25骄阳书苑7.4 LinkedList泛型类lpublic boolean contains(Object element)判断链表节点中是否判断链表节点中是否有节点含有对象有节点含有对象elementelement。lpublic Object clone()得到当得到当前链表的一个
19、克隆链表，该克隆链表前链表的一个克隆链表，该克隆链表中的节点数据的改变不会影响到当前中的节点数据的改变不会影响到当前链表中节点的数据，反之亦然。链表中节点的数据，反之亦然。26骄阳书苑例例7-77-7：import java.util.*;class Student String name; int score; Student(String name,int score) this.name=name; this.score=score; 27骄阳书苑例例7-67-6：public class Example7_7 public static void main(String args) L
20、inkedList mylist=new LinkedList(); Student stu1=new Student(张张小一小一,78), stu2=new Student(王小二王小二,98), stu3=new Student(李大山李大山,67); mylist.add(stu1); mylist.add(stu2);28骄阳书苑例例7-77-7： mylist.add(stu3); int number=mylist.size(); System.out.println(现现在在链链表中有表中有+number+个个节节点点:); for(int i=0;inumber;i+) St
21、udent temp=mylist.get(i);System.out.printf(第第+i+节节点中的数点中的数据据,学生学生:%s,分数分数:%dn,temp.name,temp.score); 29骄阳书苑例例7-77-7：Student removeSTU=mylist.remove(1);System.out.printf(被被删删除的除的节节点中的数据是点中的数据是:%s,%dn,removeSTU.name,removeSTU.score);Student replaceSTU=mylist.set(1,new Student(赵钩赵钩林林,68);System.out.pri
22、ntf(被替被替换换的的节节点中的数据是点中的数据是:%s,%dn,replaceSTU.name,replaceSTU.score);number=mylist.size();30骄阳书苑例例7-77-7： System.out.println(现现在在链链表中有表中有+number+个个节节点点:);for(int i=0;inumber;i+) Student temp=mylist.get(i);System.out.printf(第第+i+节节点中的数据点中的数据,学学生生:%s,分数分数:%dn,temp.name,temp.score); 31骄阳书苑例例7-77-7： if(m
23、ylist.contains(stu1)System.out.println(链链表包含表包含+stu1+:);System.out.println(stu1.name+,+stu1.score); elseSystem.out.println(链链表没有表没有节节点含有点含有+stu1); 32骄阳书苑7.4 LinkedList泛型类3、遍历链表、遍历链表 在例在例7-7中借助中借助get()方法实现了遍历链方法实现了遍历链表。我们可以借助泛型类表。我们可以借助泛型类Iterator实实现遍历链表，一个链表对象可以使用现遍历链表，一个链表对象可以使用iterator()方法返回一个方法返回
24、一个Iterator类型的对象，类型的对象，该对象中每个数据成员刚好是链表节点该对象中每个数据成员刚好是链表节点中的数据，而且这些数据成员是按顺序中的数据，而且这些数据成员是按顺序存放在存放在Iterator对象中的。对象中的。33骄阳书苑7.4 LinkedList泛型类如果链表是如果链表是“Student类型类型”的链表，即的链表，即链表节点中的数据是链表节点中的数据是Student类创建的对类创建的对象，那么该链表使用象，那么该链表使用iterator()方法返回方法返回一个一个Iterator类型的对象，该类型的对象，该对象使用对象使用next()方法遍历链表。方法遍历链表。34骄阳书
25、苑例例7-87-8：遍历链表。：遍历链表。import java.util.*;class Student String name ; int number; float score;Student(String name,int number,float score) this.name=name; this.number=number; this.score=score; 35骄阳书苑例例7-87-8：遍历链表。：遍历链表。public class Example7_8 public static void main(String args) LinkedList mylist=new L
26、inkedList();Student stu_1=new Student(赵赵民民 ,9012,80.0f),stu_2=new Student(钱钱青青 ,9013,90.0f), stu_3=new Student(孙孙枚枚 ,9014,78.0f),stu_4=new Student(周右周右 ,9015,55.0f);36骄阳书苑例例7-87-8：遍历链表。：遍历链表。 mylist.add(stu_1); mylist.add(stu_2); mylist.add(stu_3); mylist.add(stu_4); Iterator iter=mylist.iterator();
27、37骄阳书苑例例7-87-8：遍历链表。：遍历链表。 while(iter.hasNext() Student te=iter.next(); /使用使用next()方法遍方法遍历链历链表。表。 System.out.println(te.name+ +te.number+ +te.score); 38骄阳书苑7.4 LinkedList泛型类4、LinkedList泛型类实现的接口泛型类实现的接口 LinkedList泛型类实现了泛型接口泛型类实现了泛型接口List，而，而List接口是接口是Collection接接口的子接口。口的子接口。LinkedList类中的绝大部分类中的绝大部分方法
28、都是接口方法的实现。编程时，可以使方法都是接口方法的实现。编程时，可以使用接口回调技术，即把用接口回调技术，即把LinkedList对象的对象的引用赋值给引用赋值给Collection接口或接口或List接接口变量，那么接口就可以调用实现的接口方口变量，那么接口就可以调用实现的接口方法。法。39骄阳书苑7.4 LinkedList泛型类5、JDK 1.5之前的之前的LinkedList类类 JDK 1.5之前没有泛型的之前没有泛型的LinkedList类，可类，可以用普通的以用普通的LinkedList创建一个链表对象，创建一个链表对象，如：如：LinkedList mylist=new Li
29、nkedList();创建了一个空双链表，然后创建了一个空双链表，然后mylist链表可以链表可以使用使用add(Object obj)方法向这个链表依次添方法向这个链表依次添加节点。加节点。40骄阳书苑7.4 LinkedList泛型类由于任何类都是由于任何类都是Object类的子类，因此类的子类，因此可以把任何一个对象作为链表节点中的可以把任何一个对象作为链表节点中的对象。需要注意的是，使用对象。需要注意的是，使用get()获取一获取一个节点中的对象时，要用类型转制运算个节点中的对象时，要用类型转制运算符转换回原来的类型。符转换回原来的类型。41骄阳书苑7.4 LinkedList泛型类
30、Java泛型的主要目的是可以建立具有泛型的主要目的是可以建立具有类型安全的集合框架，如链表、散列表类型安全的集合框架，如链表、散列表等数据结构，最重要的一个优点就是：等数据结构，最重要的一个优点就是：在使用这些泛型类建立的数据结构时，在使用这些泛型类建立的数据结构时，不必进行强制类型转换，即不要求进行不必进行强制类型转换，即不要求进行运行时类型检查。运行时类型检查。42骄阳书苑7.4 LinkedList泛型类JDK 1.5是支持泛型的编译器，它将运行是支持泛型的编译器，它将运行时类型检查提前到编译时执行，使得代时类型检查提前到编译时执行，使得代码更加安全。如果使用旧版本的码更加安全。如果使用
31、旧版本的LinkedList类，类，SDK 1.5编译器会给出警编译器会给出警告信息，但程序仍能正常运行。告信息，但程序仍能正常运行。43骄阳书苑例例7-97-9：旧版本：旧版本LinkedListLinkedList的例子。的例子。import java.util.*;public class Example7_9 public static void main(String args) LinkedList mylist=new LinkedList(); mylist.add(It); /链链表中的第一个表中的第一个节节点。点。 mylist.add(is); /链链表中的第二个表中的第
32、二个节节点。点。 mylist.add(a); /链链表中的第三个表中的第三个节节点。点。 mylist.add(door); /链链表中的第四个表中的第四个节节点。点。 int number=mylist.size(); /获获取取链链表的表的长长度。度。44骄阳书苑例例7-87-8：旧版本：旧版本LinkedListLinkedList的例子。的例子。 for(int i=0;inumber;i+) String temp=(String)mylist.get(i); /必必须须强强制制转换转换取出的数据。取出的数据。System.out.println(第第+i+节节点中的数据点中的数据
33、:+temp); 45骄阳书苑例例7-87-8：旧版本：旧版本LinkedListLinkedList的例子。的例子。 Iterator iter=mylist.iterator(); while(iter.hasNext() String te=(String)iter.next();/必必须须强强制制转换转换取出的数据。取出的数据。 System.out.println(te); 46骄阳书苑7.4 LinkedList泛型类 注：注：Java也提供了顺序结构的动态数组类也提供了顺序结构的动态数组类ArrayList，数组采用顺序结构来存储数，数组采用顺序结构来存储数据。可以有效利用空间，
34、可用于存储大量的据。可以有效利用空间，可用于存储大量的数据。数组不适合动态改变它存储的数据，数据。数组不适合动态改变它存储的数据，如增加、删除单元等。由于数组采用顺序结如增加、删除单元等。由于数组采用顺序结构存储数据，数组获得第构存储数据，数组获得第n单元中的数据的速单元中的数据的速度要比链表获得第度要比链表获得第n单元中的数据快。类单元中的数据快。类ArrayList的很多方法与类的很多方法与类LinkedList类类似，两者的本质区别就是：一个使用顺序结似，两者的本质区别就是：一个使用顺序结构，一个使用链表结构。构，一个使用链表结构。47骄阳书苑Set接口Set接口是接口是Collecti
35、on的子接口，的子接口，Set内的元素内的元素是唯一的。是唯一的。Set接口并没有对接口并没有对Collection接口进行扩展，接口进行扩展，但在具体方法的含义上进行了进一步的约定。但在具体方法的含义上进行了进一步的约定。48骄阳书苑7.5 HashSet泛型类 HashSet泛型类在数据组织上类似数学泛型类在数据组织上类似数学上的集合，可以进行上的集合，可以进行“交交”、“并并”、“差差”等运算。等运算。1、HashSet对象对象 HashSet泛型类创建的对象称为集合，泛型类创建的对象称为集合，例如：例如： HashSet set=new HashSet();49骄阳书苑7.5 Hash
36、Set泛型类那么那么set就是一个可以存储就是一个可以存储String类型数据的类型数据的集合，集合，set可以调用可以调用add(String s)方法将方法将String类型数据添加到集合中，添加到集合中的数类型数据添加到集合中，添加到集合中的数据称做集合的元素。集合不允许有相同的元据称做集合的元素。集合不允许有相同的元素，也就是说，如果素，也就是说，如果b已经是集合中的元素，已经是集合中的元素，那么再执行那么再执行set.add(b)操作是无效的。集合对操作是无效的。集合对象的初始容量是象的初始容量是16个字节，装载因子是个字节，装载因子是0.75。也就是说，如果集合添加的元素超过总容量
37、也就是说，如果集合添加的元素超过总容量的的75时，集合的容量将增加一倍。时，集合的容量将增加一倍。50骄阳书苑7.5 HashSet泛型类2、常用方法、常用方法 以下是以下是HashSet泛型类的常用泛型类的常用方法：方法：public boolean add(E o)向集合向集合添加参数指定的元素。添加参数指定的元素。public void clear()清空集合，清空集合，使集合不含有任何元素。使集合不含有任何元素。51骄阳书苑7.5 HashSet泛型类lpublic boolean contains(Object o)判断参数指定的数据是否属于判断参数指定的数据是否属于集合。集合。lp
38、ublic boolean isEmpty()判判断集合是否为空。断集合是否为空。lpublic boolean remove(Object o)删除集合中参数指定的元素。删除集合中参数指定的元素。52骄阳书苑7.5 HashSet泛型类lpublic int size()返回集合中的元素个返回集合中的元素个数。数。lObject toArray()将集合元素存放到将集合元素存放到数组中，并返回这个数组。数组中，并返回这个数组。lboolean containsAll(HashSet set)判判断当前集合是否包含参数指定的集合断当前集合是否包含参数指定的集合。lpublic Object c
39、lone()得到当前集合得到当前集合的一个克隆对象，该对象中元素的改变不会的一个克隆对象，该对象中元素的改变不会影响到当前集合中的元素，反之亦然。影响到当前集合中的元素，反之亦然。53骄阳书苑7.5 HashSet泛型类 我们可以借助泛型类我们可以借助泛型类Iterator实实现遍历集合，一个集合对象可以使用现遍历集合，一个集合对象可以使用iterator()方法返回一个方法返回一个Iterator类型的对象，类型的对象，如果集合是如果集合是“Student类型类型”的集合，那的集合，那么该链表使用么该链表使用iterator()方法返回一个方法返回一个Iterator类型的对象，该对象类型的
40、对象，该对象使用使用next()方法遍历集合。方法遍历集合。54骄阳书苑例例7-107-10：遍历集合。：遍历集合。import java.util.*;class Student String name; int score; Student(String name,int score) this.name=name; this.score=score; 55骄阳书苑例例7-107-10：遍历集合。：遍历集合。public class Example7_10 public static void main(String args) Student zh=new Student(张红铭张红铭,
41、77), wa=new Student(王家家王家家,68), li=new Student(李佳佳李佳佳,67); HashSet set=new HashSet(); HashSet subset=new HashSet();56骄阳书苑例例7-107-10：遍历集合。：遍历集合。 set.add(zh); set.add(wa); set.add(li); subset.add(wa); subset.add(li); if(set.contains(wa) System.out.println(集合集合set中含有中含有:+wa.name); 57骄阳书苑例例7-107-10：遍历集合
42、。：遍历集合。if(set.containsAll(subset)System.out.println(集合集合set包含集合包含集合subset); int number=subset.size(); System.out.println(集合集合subset中有中有+number+个元素个元素:); Object s=subset.toArray();58骄阳书苑例例7-107-10：遍历集合。：遍历集合。 for(int i=0;is.length;i+)System.out.printf(姓名姓名:%s,分数分数:%dn,(Student)si).name,(Student)si).s
43、core); number=set.size(); System.out.println(集合集合set中有中有+number+个元素个元素:);59骄阳书苑例例7-107-10：遍历集合。：遍历集合。Iterator iter=set.iterator(); while(iter.hasNext() Student te=iter.next(); System.out.printf(学生学生:%s,分数分数:%dn,te.name,te.score); 60骄阳书苑7.5 HashSet泛型类3、集合的交、并与差、集合的交、并与差 集合对象调用集合对象调用boolean addAll(Has
44、hSet set)方法可以与参数指定方法可以与参数指定的集合求并运算，使得当前集合成为两的集合求并运算，使得当前集合成为两个集合的并集。个集合的并集。 集合对象调用集合对象调用boolean retainAll(HashSet set)方法可以与参数指方法可以与参数指定的集合求交运算，使得当前集合成为定的集合求交运算，使得当前集合成为两个集合的交集。两个集合的交集。61骄阳书苑7.5 HashSet泛型类 集合对象调用集合对象调用boolean removeAll(HashSet set)方法可以与参数方法可以与参数指定的集合求差运算，使得当前集合成指定的集合求差运算，使得当前集合成为两个集合
45、的差集。（属于集合为两个集合的差集。（属于集合A，但，但不属于集合不属于集合B的部分。）的部分。） 参数指定的集合必须与当前集合是同参数指定的集合必须与当前集合是同种类型的集合，否则上述方法返回种类型的集合，否则上述方法返回false。62骄阳书苑例例7-117-11：求集合：求集合A A、B B的对称差集合，即求的对称差集合，即求(A-B)(B-A)(A-B)(B-A)。import java.util.*;public class Example7_11 public static void main(String args) Integer one=new Integer(1), two
46、=new Integer(2), three=new Integer(3), four=new Integer(4), five=new Integer(5), six=new Integer(6); 63骄阳书苑例例7-117-11：求集合：求集合A A、B B的对称差集合，即求的对称差集合，即求(A-B)(B-A)(A-B)(B-A)。HashSet A=new HashSet(),B=new HashSet(),tempSet=new HashSet(); A.add(one); A.add(two); A.add(three); A.add(four); B.add(one); B.a
47、dd(two);64骄阳书苑例例7-117-11：求集合：求集合A A、B B的对称差集合，即求的对称差集合，即求(A-B)(B-A)(A-B)(B-A)。 B.add(five); B.add(six);tempSet=(HashSet)A.clone(); A.removeAll(B);/A变变成成调调用用该该方法之前的方法之前的A集合与集合与B集合的集合的差集。差集。 B.removeAll(tempSet);/B变变成成调调用用该该方法之前的方法之前的B集合与集合与tempSet集集合的差集。合的差集。65骄阳书苑例例7-117-11：求集合：求集合A A、B B的对称差集合，即求的对
48、称差集合，即求(A-B)(B-A)(A-B)(B-A)。 B.addAll(A);/B就是最初的就是最初的A与与B的的对对称差。称差。 int number=B.size(); System.out.println(A和和B的的对对称差集合称差集合有有+number+个元素个元素:); Iterator iter=B.iterator(); while(iter.hasNext() Integer te=iter.next();System.out.printf(%d，,te.intValue(); 66骄阳书苑7.5 HashSet泛型类 请同学们思考，为什么在这个地请同学们思考，为什么在这
49、个地方不能直接把数据添加到集合当中去方不能直接把数据添加到集合当中去？67骄阳书苑7.5 HashSet泛型类4、HashSet泛型类实现的接口泛型类实现的接口 HashSet泛型类实现了泛型接口泛型类实现了泛型接口Set，而，而Set接口是接口是Collection接口的子接口。接口的子接口。HashSet类中的绝大类中的绝大部分方法都是接口方法的实现。编程时，部分方法都是接口方法的实现。编程时，可以使用接口回调技术，即把可以使用接口回调技术，即把HashSet对象的引用赋值给对象的引用赋值给Collection接口变量或接口变量或Set接口变接口变量，那么接口就可以调用实现的接口方量，那么
50、接口就可以调用实现的接口方法。法。68骄阳书苑7.6 HashMap泛型类 HashMap也是一个很实用的也是一个很实用的类，类，HashMap对象采用散列表这对象采用散列表这种数据结构存储数据，习惯上称种数据结构存储数据，习惯上称HashMap对象为散列映射对象。对象为散列映射对象。散列映射用于存储键散列映射用于存储键/值数据对，允许把值数据对，允许把任何数量的键任何数量的键/值数据对存储在一起。键值数据对存储在一起。键不可以发生逻辑冲突，两个数据项不要不可以发生逻辑冲突，两个数据项不要使用相同的键，如果出现两个数据项对使用相同的键，如果出现两个数据项对应相同的键，那么先前散列映射中的键应相
51、同的键，那么先前散列映射中的键/值数据对将被替换。值数据对将被替换。69骄阳书苑7.6 HashMap泛型类 散列映射在它需要更多的存储空间散列映射在它需要更多的存储空间时会自动增加容量。例如，如果散列映时会自动增加容量。例如，如果散列映射的装载因子是射的装载因子是0.75，那么当散列映射，那么当散列映射的容量被使用了的容量被使用了75时，它就把容量增时，它就把容量增加到原始容量的加到原始容量的2倍。对于数组和链表这倍。对于数组和链表这两种数据结构，如果要查找它们存储的两种数据结构，如果要查找它们存储的某个特定的元素却不知道它的位置，就某个特定的元素却不知道它的位置，就需要从头开始访问元素直到
52、找到匹配的需要从头开始访问元素直到找到匹配的为止；如果数据结构中包含很多的元素，为止；如果数据结构中包含很多的元素，就会浪费时间。就会浪费时间。70骄阳书苑7.6 HashMap泛型类这时最好使用散列映射来存储要查找的这时最好使用散列映射来存储要查找的数据，使用散列映射可以减少检索的开数据，使用散列映射可以减少检索的开销。销。 散列方法不同于其他的查找方法散列方法不同于其他的查找方法（顺序查找、二分查找）。它不以关键（顺序查找、二分查找）。它不以关键字的比较为基本操作，采用直接寻址技字的比较为基本操作，采用直接寻址技术。在理想情况下，无须任何比较就可术。在理想情况下，无须任何比较就可以找到待查
53、关键字。以找到待查关键字。71骄阳书苑7.6 HashMap泛型类1、HashMap对象对象 HashMap泛型类创建的对象称泛型类创建的对象称为散列映射，例如：为散列映射，例如：HashMap hashtable=new HashMap ();72骄阳书苑7.6 HashMap泛型类那么，那么，hashtable就可以存储键就可以存储键/值数据对，值数据对，其中的键必须是一个其中的键必须是一个String对象，键对对象，键对应的值必须是应的值必须是Student对象。对象。hashtable可可以调用以调用public V put(K key,V value)将键将键/值数据对存放到散列映射
54、当中，同时返值数据对存放到散列映射当中，同时返回键所对应的值。回键所对应的值。73骄阳书苑7.6 HashMap泛型类2、常用方法、常用方法HashMap泛型类的常用方法：泛型类的常用方法：lpublic void clear()清空散列映射。清空散列映射。lpublic Object clone()返回当前散返回当前散列映射的一个克隆。列映射的一个克隆。74骄阳书苑7.6 HashMap泛型类lpublic boolean containsKey(Object key)如果散列映射有键如果散列映射有键/值数据对的值数据对的值是参数指定的键，方法返回值是参数指定的键，方法返回true，否，否则
55、返回则返回false。lpublic boolean containsValue(Object value)如果散列映射有键如果散列映射有键/值数据对值数据对的值是参数指定的值，方法返回的值是参数指定的值，方法返回true，否则返回否则返回false。75骄阳书苑7.6 HashMap泛型类lpublic V get(Object key)返回散列返回散列映射中使用映射中使用key作为键的键作为键的键/值对中的值。值对中的值。lpublic boolean isEmpty()如果散列如果散列映射不含任何键映射不含任何键/值对，方法返回值对，方法返回true，否则返回否则返回false。76骄阳
56、书苑7.6 HashMap泛型类lpublic V remove(Object key)删除删除散列映射中键为参数指定的键散列映射中键为参数指定的键/值对，并值对，并返回键对应的值。返回键对应的值。lpublic int size()返回散列映射的大返回散列映射的大小，即散列映射中键小，即散列映射中键/值对的数目。值对的数目。77骄阳书苑7.6 HashMap泛型类3、遍历散列映射、遍历散列映射 如果想获得散列映射中所有键如果想获得散列映射中所有键/值对中的值，值对中的值，首先使用：首先使用：public Collection values()方法返回一个实现方法返回一个实现Collectio
57、n接口类创建接口类创建的对象的引用，并要求将该对象的引用返回的对象的引用，并要求将该对象的引用返回到到Collection接口变量中。接口变量中。values()方法返方法返回的对象中存储了散列映射中所有键回的对象中存储了散列映射中所有键/值对中值对中的的“值值”，这样接口变量就可以调用类实现，这样接口变量就可以调用类实现的方法，如获取的方法，如获取Iterator对象，然后输出所有对象，然后输出所有的值。的值。78骄阳书苑例例7-127-12：遍历散列映射。：遍历散列映射。import java.util.*;class Book String ISBN,name; Book(String
58、ISBN,String name) this.name=name; this.ISBN=ISBN; 79骄阳书苑例例7-127-12：遍历散列映射。：遍历散列映射。public class Example7_12 public static void main(String args) Book book1=new Book(7302033218,C+基基础础教程教程), book2=new Book(7808315162,Java编编程程语语言言), book3=new Book(7302054991,J2ME无无线线设备编设备编程程); String key=7808315162;80骄阳
59、书苑例例7-127-12：遍历散列映射。：遍历散列映射。HashMap table=new HashMap(); table.put(book1.ISBN,book1); table.put(book2.ISBN,book2); table.put(book3.ISBN,book3); if(table.containsKey(key)System.out.println(table.get(key).name+有有货货); 81骄阳书苑例例7-127-12：遍历散列映射。：遍历散列映射。 Book b=table.get(7302054991); System.out.println(书书名
60、名:+b.name+,ISBN:+b.ISBN); int number=table.size(); System.out.println(散列映射中有散列映射中有+number+个元素个元素:); Collection collection=table.values();82骄阳书苑例例7-127-12：遍历散列映射。：遍历散列映射。Iterator iter=collection.iterator(); while(iter.hasNext() Book te=iter.next();System.out.printf(书书名名:%s,ISBN:%sn,te.name,te.ISBN);
61、83骄阳书苑7.6 HashMap泛型类4、HashMap泛型类实现的接口泛型类实现的接口 HashMap泛型类实现了泛型接泛型类实现了泛型接口口Map，而，而HashMap类中类中的绝大部分方法都是的绝大部分方法都是Map接口方接口方法的实现。编程时，可以使用接口回调法的实现。编程时，可以使用接口回调技术，即把技术，即把HashMap对象的引用对象的引用赋值给赋值给Map接口变量，那么接口接口变量，那么接口就可以调用实现的接口方法。就可以调用实现的接口方法。84骄阳书苑7.7 TreeSet泛型类 TreeSet类是实现类是实现Set接口的类，接口的类，它的大部分方法都是接口方法的实现。它的
62、大部分方法都是接口方法的实现。TreeSet泛型类创建的对象称为树集。泛型类创建的对象称为树集。 树集是一个有序集合，可以按照任树集是一个有序集合，可以按照任何顺序将元素插入到该集合。何顺序将元素插入到该集合。85骄阳书苑7.7 TreeSet泛型类例如：例如： TreeSet tree=new TreeSet();那么那么tree就是一个可以存储就是一个可以存储Student类型类型数据的集合，数据的集合，tree可以调用可以调用add(Student s)方法将方法将Student类型的数据添加到树集类型的数据添加到树集中。存放到树集的对象按对象的串表示中。存放到树集的对象按对象的串表示升
63、序排列。升序排列。86骄阳书苑7.7 TreeSet泛型类 TreeSet要求添加到树集中的节点要求添加到树集中的节点对象必须实现对象必须实现Comparable接口，也就是接口，也就是创建实现创建实现Comparable接口类的对象。比接口类的对象。比如，如，String类实现了类实现了Comparable接口中接口中的的compareTo(Object str)方法，字符串方法，字符串调用调用compareTo(String s)方法按字典序方法按字典序与参数与参数s指定的字符串比较大小。也就是：指定的字符串比较大小。也就是：87骄阳书苑7.7 TreeSet泛型类TreeSet mytr
64、eenew TreeSet();然后就可以使用然后就可以使用add()方法向树集中添加方法向树集中添加节点了。节点了。 Comparable 接口强行对实现它的接口强行对实现它的每个类的对象进行整体排序。此排序被每个类的对象进行整体排序。此排序被称为该类的自然排序，类的称为该类的自然排序，类的 compareTo 方法被称为它的自然比较方法。方法被称为它的自然比较方法。 88骄阳书苑7.7 TreeSet泛型类TreeSet泛型类的常用方法：泛型类的常用方法：lpublic boolean add(E o)向树集添向树集添加对象，添加成功返回加对象，添加成功返回true，否则返回，否则返回fa
65、lse。lpublic void clear()删除树集中的所删除树集中的所有对象。有对象。89骄阳书苑7.7 TreeSet泛型类lpublic boolean contains(Object o)如果包含对象如果包含对象o方法返回方法返回true，否则返回，否则返回false。lpublic E first()返回树集中的第一返回树集中的第一个对象（最小的对象）。个对象（最小的对象）。lpublic E last()返回树集中的最后返回树集中的最后一个对象（最大的对象）。一个对象（最大的对象）。90骄阳书苑7.7 TreeSet泛型类lpublic boolean isEmpty()判断是
66、否判断是否是空树集，如果树集不含对象返回是空树集，如果树集不含对象返回true。lpublic boolean remove(Object o)删除树集中的对象删除树集中的对象o。lpublic int size()返回树集中的对象返回树集中的对象数目。数目。91骄阳书苑7.7 TreeSet泛型类 我们在创建树集时可自己规定树集我们在创建树集时可自己规定树集中的对象按照什么样的顺序排列，要求中的对象按照什么样的顺序排列，要求添加到树集中的节点对象必须实现添加到树集中的节点对象必须实现Comparable接口类的实例，也就是实现接口类的实例，也就是实现Comparable接口类所创建的对象。假
67、如接口类所创建的对象。假如我们有我们有4个学生对象，他们有姓名和成绩，个学生对象，他们有姓名和成绩，我们想把这我们想把这4个对象添加到树集中，并按个对象添加到树集中，并按照成绩的高低排列，而不是按照姓名的照成绩的高低排列，而不是按照姓名的字典序排列节点。字典序排列节点。92骄阳书苑7.7 TreeSet泛型类 首先创建学生的首先创建学生的Student类实现接口类实现接口Comparable。Comparable接口有一个接口有一个方法：方法：public int compareTo(Object b);Student类通过实现这个接口来规定它创类通过实现这个接口来规定它创建的对象的大小关系，
68、如下所示：建的对象的大小关系，如下所示：93骄阳书苑7.7 TreeSet泛型类class Student implement Comparable int english=0; String name; Student(int e,String n) english=e;name=n; public int compareTo(Object b) Student st=(Student) b; return (this.english-st.english); 94骄阳书苑7.7 TreeSet泛型类 Java规定：当规定：当pareTo(b)=0时，时，两者相等；两者相等； pareTo(
69、b)0时，称时，称a大大于于b；pareTo(b)0时，称时，称a小于小于b。95骄阳书苑7.7 TreeSet泛型类 当当mytree每次添加对象时，都会调每次添加对象时，都会调用接口中的方法实现对象大小的互相比用接口中的方法实现对象大小的互相比较，但较，但mytree调用接口方法的过程编程调用接口方法的过程编程人员是不可见的。人员是不可见的。Sun公司在编写开发公司在编写开发TreeSet类时已经实现了这一机制。类时已经实现了这一机制。96骄阳书苑例例7-137-13：把：把StudentStudent对象添加到树集中，并按照成绩的高低排列。对象添加到树集中，并按照成绩的高低排列。impo
70、rt java.util.*; class Student implements Comparable int english=0; String name; Student(int e,String n) english=e;name=n; public int compareTo(Object b) Student st=(Student)b; return (this.english-st.english); 97骄阳书苑例例7-137-13：把：把StudentStudent对象添加到树集中，并按照成绩的高低排列。对象添加到树集中，并按照成绩的高低排列。public class Exa
71、mple7_13 public static void main(String args)TreeSet mytree=new TreeSet(); Student st1,st2,st3; st1=new Student(90,zhan ying); st2=new Student(66,wang heng); st3=new Student(86,Liuh qing); mytree.add(st1); mytree.add(st2); mytree.add(st3);98骄阳书苑例例7-137-13：把：把StudentStudent对象添加到树集中，并按照成绩的高低排列。对象添加到树集
72、中，并按照成绩的高低排列。Iterator te=mytree.iterator(); while(te.hasNext() Student stu=te.next(); System.out.println( +stu.name+ +stu.english); 99骄阳书苑7.7 TreeSet泛型类 注：树集中不允许出现大小相等的注：树集中不允许出现大小相等的两个节点。例如，在上述例子中如果再两个节点。例如，在上述例子中如果再添加语句：添加语句： st4=new Student(90,”Zhang ying”); mytree.add(st4);是无效的。如果允许成绩相同，可把上是无效的。
73、如果允许成绩相同，可把上述例子中述例子中Student类中的类中的compareTo方法方法更改为：更改为：100骄阳书苑7.7 TreeSet泛型类 public int compareTo(Object b) Student st=(Student) b; if (this.english-st.english)=0) return 1; elsereturn (this.english-st.english) 101骄阳书苑7.8 TreeMap泛型类 TreeMap类实现了类实现了Map接口。接口。TreeMap提供了按排序顺序存储关键字提供了按排序顺序存储关键字/值对的有效手段。应该
74、注意的是，不像值对的有效手段。应该注意的是，不像散列映射（散列映射（HashMap），树映射），树映射（TreeMap）保证它的元素按照关键字）保证它的元素按照关键字升序排列。下面是升序排列。下面是TreeMap的构造函数：的构造函数： TreeMap() TreeMap(Comparator comp)102骄阳书苑7.8 TreeMap泛型类 第一种形式构造的树映射，按关键第一种形式构造的树映射，按关键字的大小顺序来排序树映射中的键字的大小顺序来排序树映射中的键/值对，值对，关键字的大小顺序是按其字符串表示的关键字的大小顺序是按其字符串表示的字典顺序。第二种形式构造的树映射，字典顺序。第二
75、种形式构造的树映射，关键字的大小顺序按关键字的大小顺序按Comparator接口规接口规定的大小顺序，树映射按关键字的大小定的大小顺序，树映射按关键字的大小顺序来排序树映射中的关键字顺序来排序树映射中的关键字/值对。值对。 TreeMap类的常用方法与类的常用方法与HashMap类相似。类相似。103骄阳书苑例例7-147-14：使用：使用TreeMapTreeMap，分别按照学生的身高和体重排序对象。，分别按照学生的身高和体重排序对象。import java.util.*;class MyKey implements Comparable int number=0; MyKey(int nu
76、mber) this.number=number; public int compareTo(Object b) MyKey st=(MyKey)b; if(this.number-st.number)=0) return -1; elsereturn (this.number-st.number); 104骄阳书苑例例7-147-14：使用：使用TreeMapTreeMap，分别按照学生的身高和体重排序对象。，分别按照学生的身高和体重排序对象。class Student String name=null; int height,weight; Student(int w,int h,Stri
77、ng name) weight=w; height=h; this.name=name; 105骄阳书苑例例7-147-14：使用：使用TreeMapTreeMap，分别按照学生的身高和体重排序对象。，分别按照学生的身高和体重排序对象。public class Example7_14 public static void main(String args ) Student s1=new Student(65,177,“张三张三), s2=new Student(85,168,“李四李四); TreeMap treemap=new TreeMap(); treemap.put(new MyKe
78、y(s1.weight),s1); treemap.put(new MyKey(s2.weight),s2); int number=treemap.size();106骄阳书苑例例7-147-14：使用：使用TreeMapTreeMap，分别按照学生的身高和体重排序对象。，分别按照学生的身高和体重排序对象。System.out.println(树映射中有树映射中有+number+个对象个对象:);Collection collection=treemap.values();Iterator iter=collection.iterator(); while(iter.hasNext() St
79、udent te=iter.next(); System.out.printf(%s,%d(公斤公斤)n,te.name,te.weight); treemap.clear();107骄阳书苑例例7-147-14：使用：使用TreeMapTreeMap，分别按照学生的身高和体重排序对象。，分别按照学生的身高和体重排序对象。 treemap.put(new MyKey(s1.height),s1); treemap.put(new MyKey(s2.height),s2); number=treemap.size();System.out.println(树映射中有树映射中有+number+个对
80、象个对象:); collection=treemap.values(); iter=collection.iterator(); while(iter.hasNext() Student te=iter.next();System.out.printf(%s,%d(厘米厘米)n,te.name,te.height); 108骄阳书苑7.9 Stack泛型类 堆栈是一种堆栈是一种“后进先出后进先出”的数据的数据结构，只能在一端进行输入或输出数结构，只能在一端进行输入或输出数据的操作。堆栈把每一个放入该堆栈据的操作。堆栈把每一个放入该堆栈的数据放在最底下，而把后续放入的的数据放在最底下，而把后续放
81、入的数据放在已有数据的上面，结构如下数据放在已有数据的上面，结构如下图所示。图所示。109骄阳书苑7.9 Stack泛型类110骄阳书苑7.9 Stack泛型类 向堆栈中输入数据的操作称为向堆栈中输入数据的操作称为“入入栈栈”，从栈中输出数据的操作称为，从栈中输出数据的操作称为“出出栈栈”。由于堆栈总是在顶端进行数据的。由于堆栈总是在顶端进行数据的输入与输出操作，所以出栈输出（删除）输入与输出操作，所以出栈输出（删除）最后入栈的数据，这就是最后入栈的数据，这就是“后进先出后进先出”的来历。的来历。 使用使用java.util包中的包中的Stack类创建一个类创建一个堆栈对象，堆栈对象可以使用：
82、堆栈对象，堆栈对象可以使用：111骄阳书苑7.9 Stack泛型类public E push(E item);输入数据，实现入栈操作；输入数据，实现入栈操作；使用：使用：public E pop();输出数据，实现出栈操作；输出数据，实现出栈操作；使用：使用：public boolean empty();判断堆栈是否还有数据，有数据返回判断堆栈是否还有数据，有数据返回false，否则返回，否则返回true；112骄阳书苑7.9 Stack泛型类使用：使用：public E peek();获取堆栈顶端的数据，但不删除数据；获取堆栈顶端的数据，但不删除数据；使用：使用：public int sea
83、rch(Object data);获取数据在堆栈中的位置，最顶端的位获取数据在堆栈中的位置，最顶端的位置是置是1，向下依次增加，如果堆栈中不包，向下依次增加，如果堆栈中不包含此数据，则返回含此数据，则返回-1。113骄阳书苑7.9 Stack泛型类 堆栈是很灵活的数据结构，使用堆堆栈是很灵活的数据结构，使用堆栈可以节省内存的开销。比如，递归是栈可以节省内存的开销。比如，递归是一种很消耗内存的算法，我们可以借助一种很消耗内存的算法，我们可以借助堆栈消除大部分递归，达到和递归算法堆栈消除大部分递归，达到和递归算法同样的目的。同样的目的。 Fibonacci整数序列是我们熟悉的一个整数序列是我们熟悉
84、的一个递归序列，它的第递归序列，它的第n项是前两项的和，第项是前两项的和，第一项和第二项都是一项和第二项都是1。114骄阳书苑例例7-157-15：用堆栈输出递归序列。：用堆栈输出递归序列。import java.util.*;public class Example7_15 public static void main(String args) Stack stack=new Stack(); stack.push(new Integer(1); stack.push(new Integer(1); int k=1; while(k=10) for(int i=1;i=2;i+) 115骄阳书苑例例7-157-15：用堆栈输出递归序列。：用堆栈输出递归序列。 Integer F1=stack.pop(); int f1=F1.intValue(); Integer F2=stack.pop(); int f2=F2.intValue(); Integer temp=new Integer(f1+f2);System.out.println(+temp.toString(); stack.push(temp); stack.push(F2); k+; 116骄阳书苑
