第15章_泛型与集合框架.ppt

1、泛型 链表 堆栈 散列映射 树集 树映射 难点 树映射,主要内容,在jdk1.2之后，Java提供了实现常见数据结构的类，这些实现数据结构的类通称为Java集合框架。在JDK1.5后，Java集合框架开始支持泛型，本章首先介绍泛型，然后讲解常见数据结构类的用法。,概述,15.1 泛型,泛型（Generics）是在JDK1.5中推出的，其主要目的是可以建立具有类型安全的集合框架，如链表、散列映射等数据结构。,15.1.1 泛型类声明,可以使用“class 名称”声明一个类,为了和普通的类有所区别，这样声明的类称作泛型类,如： class People 其中People是泛型类的名称，E是其中的泛

2、型，也就是说我们并没有指定E是何种类型的数据，它可以是任何对象或接口，但不能是基本类型数据。泛型类声明时，“泛型列表”给出的泛型可以作为类的成员变量的类型、方法的类型以及局部变量的类型。 参考：Cone.java P451 设计一个锥，锥只关心它的底面积是多少，并不关心底的具体形状，它关心的是用底面积和高计算出自身的体积。,锥定义类：Cone.java,public class Cone double height; E bottom; /用泛型类E声明对象bottom,只能调用Object类中的方法 public Cone (E b) bottom=b; public void setHei

3、ght(double h) height=h; public double computerVolume() String s=bottom.toString();/泛型变量只能调用从Object类继承的或重写的方法 double area=Double.parseDouble(s); return 1.0/3.0*area*height; ,15.1.2 使用泛型类声明对象,泛型类声明和创建对象时，类名后多了一对“”，而且必须要用具体的类型替换“”中的泛型。例如： Cone coneOne; coneOne =new Cone(new Circle(); 例题15-1,Circle.java

4、,public class Circle double area,radius; Circle(double r) radius=r; public String toString() /重写Object类的toString()方法 area=radius*radius*Math.PI; return +area; ,Rect.java,public class Rect double sideA,sideB,area; Rect(double a,double b) sideA=a; sideB=b; public String toString() area=sideA*sideB; re

5、turn +area; ,测试类,public class Example15_1 public static void main(String args) Circle circle=new Circle(10); Cone coneOne=new Cone(circle);/创建一个（圆）锥对象 coneOne.setHeight(16); System.out.println(coneOputerVolume(); Rect rect=new Rect(15,23); Cone coneTwo=new Cone(rect);/创建一个（方）锥对象 coneTwo.setHeight(98

6、); System.out.println(coneTputerVolume(); ,15.1.3 泛型接口,可以使用“interface 名称”声明一个接口，这样声名的接口称作泛型接口如 interface Computer interface Computer void makeChorus(E x,F y); class Chorus implements Computer public void makeChorus(E x,F y) x.toString(); y.toString(); ,class 乐器 public String toString() System.out.pr

7、intln(|3 5 1-|1 3 5-|12 35 2-|); return ; class 歌手 public String toString() System.out.println(你和我,我和你,同住地球村); return ; public class Example13_2 public static void main(String args ) Chorus model=new Chorus(); 歌手 pengliyuan=new 歌手(); 乐器 piano=new 乐器(); model.makeChorus(pengliyuan,piano); ,15.2 链表,链表

8、是由若干个称作节点的对象组成的一种数据结构，每个节点含有一个数据和下一个节点的引用 。,15.2.1 LinkedList泛型类, LinkedList泛型类创建的对象以链表结构存储数据，习惯上称LinkedList类创建的对象为链表对象。例如， LinkedList mylist=new LinkedList(); 创建一个空双链表。 add(E obj) 向链表依次增加节点,15.2.2 常用方法, LinkedList泛型类实现Lis泛型接口中的一些常用方法。 public boolean add(E element) 向链表末尾添加一个新的节点，该节点中的数据是参数elememt指定的

9、数据。 public void add(int index ,E element) 向链表的指定位置添加一个新的节点，该节点中的数据是参数elememt指定的数据。 public void clear() 删除链表的所有节点，使当前链表成为空链表。 public E remove(int index) 删除指定位置上的节点。 public boolean remove(E element) 删除首次出现含有数据elemen的节点。 public E get(int index) 得到链表中指定位置处节点中的数据。 LinkedList泛型类本身新增加的一些常用方法 public void ad

10、dFirst(E element) 向链表的头添加新节点，该节点中的数据是参数elememt指定的数据。 public void addLast(E element) 向链表的末尾添加新节点，该节点中的数据是参数elememt指定的数据。 public E getFirst() 得到链表中第一个节点中的数据。 public E getLast() 得到链表中最后一个节点中的数据。 public E removeFirst() 删除第一个节点，并返回这个节点中的数据。 ,迭代器,while,do-while和for用来控制循环,有时将它们划分为“迭代语句”。语句会重复执行,直到起控制作用的布尔表

11、达式(Boolean-expression)得到“假”的结果为止。 迭代器(也是一种设计模式)的概念可以用于达成不重写代码就可以应用于不同类型的容器。一个聚合对象，如一个列表(List)或者一个集合(Set)，应该提供一种方法来让别人可以访问它的元素，而又不需要暴露它的内部结构。迭代器是一个对象,它的工作是遍历并选择序列中的对象,而客户端程序员不必知道或关心该序列底层的结构(也就是不同容器的类型)。此外,迭代器通常被称为“轻量级”对象：创建它的代价小。 Java的Iterator就是一种迭代器(只能单向移动),它只能用来: 1.使用方法iterator()要求容器返回一个Iterator.第一

12、次调用Iterator的next()方法时,它返回序列的第一个元素; 2.使用next()获得序列中的下一个元素; 3.使用hasNext()检查序列中是否还有元素; 4.使用remove()将迭代器新近返回的元素删除.,15.2.3 遍历链表,import java.util.*; public class Example15_2 public static void main(String args) LinkedList list=new LinkedList(); for(int i=0;i iter=list.iterator(); long starttime=System.cur

13、rentTimeMillis(); while(iter.hasNext() String te=iter.next(); long endTime=System.currentTimeMillis(); long result=endTime-starttime; System.out.println(使用迭代器遍历集合所用时间:+result+毫秒); starttime=System.currentTimeMillis(); for(int i=0;ilist.size();i+) String te=list.get(i); endTime=System.currentTimeMill

14、is(); result=endTime-starttime; System.out.println(使用get方法遍历集合所用时间:+result+毫秒); ,顺序结构的动态数组表类ArrayList,数组表不适合动态地改变它存储的数据，如增加、删除等，但由于数组表采用顺序结构存储，随机访问的速度比链表的快。 ArrayList类的很多方法与LinkedList类似，两者的本质区别：一个使用顺序结构、一个使用链式结构。,例题15-3 老版的用法,import java.util.*; public class Example13_4 public static void main(Strin

15、g args) LinkedList mylist=new LinkedList(); mylist.add(你); /链表中的第一个节点 mylist.add(好); /链表中的第二个节点 int number=mylist.size(); /获取链表的长度 for(int i=0;inumber;i+) String temp=(String)mylist.get(i); /必须强制转换取出的数据 System.out.println(第+i+节点中的数据:+temp); Iterator iter=mylist.iterator(); while(iter.hasNext() Strin

16、g te=(String)iter.next(); /必须强制转换取出的数据 System.out.println(te); ,15.2.4 排序与查找,Collections类提供的用于排序和查找的类方法如下： public static sort(List list) 该方法可以将list中的元素升序排列。 int binarySearch(List list, T key,CompareTo c) 使用折半法查找list是否含有和参数key相等的元素，如果key链表中某个元素相等，方法返回和key相等的元素在链表中的索引位置（链表的索引位置从0考试），否则返回-1。 例子4中，Stude

17、nt类通过实现Comparable接口规定该类的对象的大小关系（按height值的大小确定大小关系，即学生按其身高确定之间的大小关系）。链表添加了3个Student对象，Collections调用sort方法将链表中的对象按身其height值升序排序，并查找一个对象的height值是否和链表中某个对象的height值相同。运行效果如图15.5。,例4 Comparable接口问题,import java.util.*; class Student implements Comparable int height=0; String name; Student(String n,int h) n

18、ame=n; height = h; public int compareTo(Object b) / 两个Student对象相等当且仅当二者的height值相等 Student st=(Student)b; return (this.height-st.height); ,Comparable接口问题,public class Example15_4 public static void main(String args ) List list = new LinkedList(); list.add(new Student(张三,188); list.add(new Student(李四,

19、178); list.add(new Student(周五,198); Iterator iter=list.iterator(); System.out.println(排序前,链表中的数据); while(iter.hasNext() Student stu=iter.next(); System.out.println(+ 身高:+stu.height); ,Comparable接口问题,Collections.sort(list); System.out.println(排序后,链表中的数据); iter=list.iterator(); while(iter.hasN

20、ext() Student stu=iter.next(); System.out.println(+ 身高:+stu.height); Student zhaoLin = new Student(zhao xiao lin,178); int index = Collections.binarySearch(list,zhaoLin,null); if(index=0) System.out.println(zhaoL+和链表中+list.get(index).name+身高相同); ,15.3 堆栈,堆栈是一种“后进先出”的数据结构，只能在一端进行输入或输出数

21、据的操作。 Stack泛型类创建一个堆栈对象，堆栈对象常用方法： public E push(E item);实现压栈操作 public E pop();实现弹栈操作。 public boolean empty();判断堆栈是否还有数据。 public E peek();获取堆栈顶端的数据，但不删除该数据。 public int search(Object data);获取数据在堆栈中的位置。 例题15-6,15.4 散列映射,HashMap对象采用散列表这种数据结构存储数据，习惯上称HashMap对象为散列映射。 例如 HashMap hashtable= HashSet(); hashta

22、ble可以存储“键/值”对数据。 相关方法： public V put(K key,V value)将键/值对数据存放到散列映射中，该方法同时返回键所对应的值。,15.4.2 常用方法,public void clear() 清空散列映射。 public Object clone() 返回当前散列映射的一个克隆。 public boolean containsKey(Object key) 如果散列映射有“键/值”对使用了参数指定的键，方法返回true，否则返回false。 public boolean containsValue(Object value) 如果散列映射有“键/值”对的值是参

23、数指定的值。 public V get(Object key) 返回散列映射中使用key做键的“键/值”对中的值。 public boolean isEmpty() 如果散列映射不含任何“键/值”对，方法返回true，否则返回false。 public V remove(Object key) 删除散列映射中键为参数指定的“键/值”对，并返回键对应的值。 public int size() 返回散列映射的大小，即散列映射中“键/值”对的数目。,15.4.3 遍历散列映射,public Collection values()方法返回一个实现Collection接口类创建的对象。 使用接口回调技术

24、，即将该对象的引用赋给Collection接口变量，该接口变量可以回调iterator()方法获取一个Iterator对象，这个Iterator对象存放着散列映 射中所有“键/值”对中的“值”。,15.4.4 基于散列映射的查询,对于经常需要进行查找的数据可以采用散列映射来存储这样的数据，即为数据指定一个查找它的关键字，然后按着“健-值”对，将关键字和数据一并存入散列映射中。 例题15-7,15.5 树集,TreeSet类创建的对象称作树集。 例如 TreeSet mytree=new TreeSe(); 然后使用add方法为树集添加节点，例如 mytree.add(boy);,15.5.2

25、节点的大小关系,树集用add方法添加节点，节点会按其存放的数据的“大小”顺序一层一层地依次排列，在同一层中的节点从左到右按“大小”顺序递增排列，下一层的都比上一层的小。,15.5.3 TreeSet类的常用方法,public boolean add(E o) 向树集添加加节点。 public void clear() 删除树集中的所有节点。 public void contains(Object o) 如果树集中有包含参数指定的对象，该方法返回true，否则返回false 。 public E first() 返回树集中的第一个节点中的数据（最小的节点）。 public E last() 返回最后一个节点中的数据（最大的节