Java程序设计——09集合框架

1、计算机科学与技术学院赵志崑赵志崑问题问题 随机点名器程序中如何解决100人的限制？ 方法1：将预留空间改得足够大。 造成内存空间浪费。 如何确定多少为足够大。 方法2：动态生成数组。 效率较低 方法3：使用链表。Student students = new Student10000;Selector1.javawhile(line != null) students1 = new StudenttotalCount+1; System.arraycopy(student,0,students,0,totalCount); students1totalCount = student; stude

2、nts = students1; totalCount+; line = in.readLine();Selector2.javaclass Student private String id; private String name; private String department; public Student next; public Student(); 赵志崑JavaJava对基本数据结构的支持对基本数据结构的支持 链表是一种非常常用的数据结构，类似的还有队列、集合等等，是否所有这些数据结构都要自己来实现呢？ 编写程序有两个关键问题，数据结构和算法。 数据结构是组织和存储数据的方

3、法 算法是操作数据的方法 有些数据结构和算法在绝大多数程序中都要用到，开发工具的设计者就寻找一种机制，能够让开发人员不用每次都做重复劳动。 头文件和库函数：最原始的方法。 模板库(STL)：C+中采用的方法。 类和接口：Java中采用的方法。 Java的设计者在设计Java时，充分考虑了这一点，通过单根继承(Object类)，使用简单的类和接口提供了对许多基本数据结构的支持。赵志崑常用数据结构和算法常用数据结构和算法 基本数据结构有四种：数组、链表、树和网。 常用基本算法有两大类：排序和查找(搜索)。 排序：将一组数据逻辑上按一定顺序存放。 查找：从一组数据中找出满足某一要求的数据。赵志崑功能

4、定义和具体实现分开功能定义和具体实现分开 Java中采用功能定义和具体实现分开的思想。 功能定义：定义从外部看到的模型的功能，即模型可以如何使用。 具体实现：模型内部的实现机制。 例如： 录音机功能包括录音和放音。 这些功能可以用磁带录音机、Mp3等来实现。录音机功能录音放音磁带录音机磁头磁带马达Mp3播放器芯片闪存功能定义具体实现赵志崑接口和实现接口和实现 接口：Java中用接口来描述一个模型在逻辑上的功能。 实现：Java中用具体的类来实现这些功能，在这些类中用某个具体的数据结构来实现接口定义的功能。 例如：队列可以用链表实现。12345队首队尾60出队入队数据链接数据链接数据链接表头表尾

5、数据链接数据链接Interface Queue void add(Object obj); Object remove(); int size();class LinkedList implements Queue public void add (Object obj); public Object remove (); public int size (); private LinkedList header; private LinkedList tail; private class Entry Object element; Entry next; 队列链表赵志崑接口和实现分开接口和

6、实现分开 将接口和实现分开：一种功能可以有多种实现方法。 例如：队列既可以用链表实现，也可以用循环数组实现。 编写程序时，了解接口即可完成逻辑功能，了解具体实现则可以提高程序效率和适用性。12345队首队尾60出队入队数据链接数据链接数据链接表头表尾数据链接数据链接队列链表32154开头结尾循环数组赵志崑集合框架中的接口集合框架中的接口 框架(framework)是类和接口的集合，这些类和接口拥有许多有用的功能和机制。使用其中的某个或几个类和接口，能够完成一些特定功能。RandomAccessCollectionListSetSortedSetMapSortedMapIteratorListI

7、terator集合接口映射接口枚举器接口随机访问标志接口赵志崑ListList列表列表 List描述列表接口，列表中元素可以重复，有先后顺序。public interface List extends Collection boolean add(Object o)：将元素将元素o添加到列表最后。添加到列表最后。void clear()：清空列表内容。清空列表内容。boolean contains(Object o)：判断列表中是否包含元素判断列表中是否包含元素o。Object get(int index)：获取列表中获取列表中index位置的元素。位置的元素。int indexOf(Obje

8、ct o)：获取元素获取元素o在列表中的位置。在列表中的位置。boolean isEmpty()：列表是否为空。列表是否为空。int lastIndexOf(Object o)：获取列表中最后一个获取列表中最后一个o出现的位置。出现的位置。ListIterator listIterator()：获取一个枚举器。获取一个枚举器。Object remove(int index)：去除位置去除位置index的元素。的元素。boolean remove(Object o)：去除列表中第一个出现的去除列表中第一个出现的o元素。元素。Object set(int index, Object element

9、)：用用element取代位置取代位置index的元素。的元素。int size()：返回列表中元素个数。返回列表中元素个数。List subList(int fromIndex, int toIndex)：得到一个子范围。得到一个子范围。Object toArray()：将列表转化为一个数组。将列表转化为一个数组。赵志崑SetSet集合集合Set描述一个数学概念上的集合，集合中元素不能重复，没有先后顺序之分。public interface Set extends Collection boolean add(Object o)：将元素将元素o加入集合。加入集合。boolean addAll

10、(Collection c)：将集合将集合c中元素并入集合。中元素并入集合。void clear()：清空集合。清空集合。boolean contains(Object o)：判断集合中是否包含元素判断集合中是否包含元素o。boolean containsAll(Collection c)：判断集合是否全部包含判断集合是否全部包含c中元素。中元素。boolean equals(Object o)：判断两个集合是否相等。判断两个集合是否相等。boolean isEmpty()：判断集合是否为空。判断集合是否为空。Iterator iterator()：返回一个枚举器。返回一个枚举器。boolea

11、n remove(Object o)：从集合中删除元素从集合中删除元素o。int size()：返回集合元素个数。返回集合元素个数。Object toArray()：将集合转化为一个数组。将集合转化为一个数组。赵志崑列表与集合功能之比较列表与集合功能之比较 列表中元素有位置的概念，集合中元素没有。 列表中可以含有重复元素，集合中不能。列表列表-Listboolean add(Object o)void clear()boolean contains(Object o)boolean isEmpty()boolean remove(Object o)int size()Object toArra

12、y() Object get(int index)int indexOf(Object o)int lastIndexOf(Object o)ListIterator listIterator()Object remove(int index)Object set(int index, Object element)List subList(int fromIndex, int toIndex)集合集合-Setboolean add(Object o)void clear()boolean contains(Object o) boolean isEmpty()boolean remove(O

13、bject o)int size()Object toArray()boolean addAll(Collection c)boolean containsAll(Collection c) boolean equals(Object o) Iterator iterator()赵志崑SortedSetSortedSet有序集合有序集合SortedSet描述一个自动排序的集合，除了Set中的功能外，还能够自动为集合中的元素排序。public interface SortedSet extends Set Object first()：返回第一个元素。返回第一个元素。Object last()：

14、返回最后一个元素。返回最后一个元素。SortedSet headSet(Object toElement)：返回比返回比toElement小的元素。小的元素。SortedSet tailSet(Object fromElement)：返回比返回比fromElement大的元素。大的元素。 SortedSet subSet(Object fromElement, Object toElement)：返回返回fromElement和和toElement之间的元素。之间的元素。赵志崑IteratorIterator枚举器枚举器Iterator用于枚举集合或列表中的所有元素。public interf

15、ace Iterator boolean hasNext()：是否还没有枚举完。是否还没有枚举完。Object next()：下一个元素。下一个元素。void remove()：从集合中删除刚枚举过的元素从集合中删除刚枚举过的元素ListIterator用于枚举列表中的所有元素。public interface ListIterator extends Iterator void add(Object o)：在当前位置插入一个元素。在当前位置插入一个元素。boolean hasNext()：正向是否还有其他元素。正向是否还有其他元素。boolean hasPrevious()：反向是否还有其他

16、元素反向是否还有其他元素Object next()：下一个元素。下一个元素。int nextIndex()：返回下一个元素的位置。返回下一个元素的位置。Object previous()：上一个元素上一个元素int previousIndex()：返回上一个元素的位置。返回上一个元素的位置。void remove()：删除刚刚访问过的元素。删除刚刚访问过的元素。void set(Object o)：用用o覆盖刚刚访问过的元素。覆盖刚刚访问过的元素。IteratorListIterator赵志崑集合框架中的旧类集合框架中的旧类 集合框架是从Java2开始才有的，但之前已有一些“旧类”，这些类现在

17、也被纳入集合框架中。AbstractListListVectorStackRandomAccessHashtableMapProperties容器类堆栈类赵志崑集合框架中的新类集合框架中的新类 Java2新加入的类。HashMapMapAbstractMapTreeMapSortedMapAbstractCollectionListAbstractListLinkedListRandomAccessSetAbstractSequentialListListArrayListAbstractSetHashSetTreeSetCollection两个列表类两个集合类赵志崑LinkedListLin

18、kedList链式列表链式列表 LinkedList是用双向循环链表来实现List接口的类。 private Entry addBefore(Object o, Entry e) Entry newEntry = new Entry(o, e, e.previous); newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; size+; modCount+; return newEntry; 见见LinkedList.javapublic class LinkedList extends AbstractSe

19、quentialList implements List, Cloneable, java.io.Serializable private static class Entry Object element; Entry next; Entry previous; Entry(Object element, Entry next, Entry previous) this.element = element; this.next = next; this.previous = previous; 表头ObjectnextpreviousObjectnextpreviousObjectnextp

20、reviousObjectnextpreviousObjectnextprevious待插入的Entry赵志崑ArrayListArrayList数组列表数组列表 ArrayList是一个用数组来实现列表功能的类。elementDataoldCapacitynewCapacitySystem.arraycopy见见ArrayList.javapublic class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable private transient Obj

21、ect elementData; public void ensureCapacity(int minCapacity) modCount+; int oldCapacity = elementData.length; if (minCapacity oldCapacity) Object oldData = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity minCapacity) newCapacity = minCapacity; elementData = new ObjectnewCapac

22、ity; System.arraycopy(oldData, 0, elementData, 0, size); Vector(容器)的实现机制与ArrayList相同，区别在于：Vector支持多线程同步读写，ArrayList不支持。Vector的效率比ArrayList低。赵志崑列表举例列表举例创建一个链式列表，保存整数对象0-9，然后输出可以转化为数组输出；可以用枚举器输出；将上述功能改为用数组列表实现；应用多态见见Test1_1.javaimport java.util.*;public class Test1 public static void main(String args)

23、 LinkedList l = new LinkedList(); for(int i=0;i10;i+) l.add(new Integer(i); String s = ; for(int i=0; il.size(); i+) Object o = l.get(i);s += o + ; System.out.println(s); 用枚举器输出用枚举器输出Iterator iterator = l.iterator();while(iterator.hasNext() s += iterator.next()+ ;用数组列表实现（用数组列表实现（Test1_2.java）ArrayLi

24、st l = new ArrayList();应用多态应用多态List l = new ArrayList();用用Vector(容器容器)实现实现List l = new Vector();转化为数组转化为数组Object pl = l.toArray();赵志崑列表中元素的类型列表中元素的类型 列表中可以放不同类型的对象 由于多态性和单根继承，列表中使用的Object类型的引用可以指向任何对象。见Test1_3.java 可以为列表中元素设置类型检查 在声明列表引用、列表对象和枚举器对象时，可以设置对列表中元素的类型检查。见Test1_4.java/Test1_3.javaimport j

25、ava.util.*;public class Test1_3 public static void main(String args) List l = new LinkedList(); l.add(new Integer(5); l.add(new Float(2.3f); l.add(new Boolean(true); l.add(string); /Test1_4.javaimport java.util.*;public class Test1_4 public static void main(String args) List l = new LinkedList(); fo

26、r(int i=0;i10;i+) l.add(new Integer(i); String s = ; Iterator iterator = l.iterator(); while(iterator.hasNext() Integer o = iterator.next();s += o+ ; System.out.println(s); 赵志崑HashSetHashSet散列散列( (哈希哈希) )集集 HashSet是用散列表实现集合功能的类。散列(O(C)能够解决链表和数组中的无序数据查找问题(O(n)。见见HashMap.javapublic class HashMap exten

27、ds AbstractMap implements Map, Cloneable, Serializable Entry table; static class Entry implements Map.Entry final Object key; Object value; final int hash; Entry next; public boolean containsKey(Object key) Object k = maskNull(key); int hash = hash(k); int i = indexFor(hash, table.length); Entry e =

28、 tablei; while (e != null) if (e.hash = hash & eq(k, e.key) return true; e = e.next; return false; 见见HashSet.javapublic class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable private HashMap map; .012N-2N-1散列表赵志崑TreeSetTreeSet树集树集 TreeSet是用平衡二叉树实现有序集合功能的类。树集是个有序集合，其插入操

29、作的速度比散列集慢(O(Log2n)。见见TreeMap.javapublic class TreeMap extends AbstractMap implements SortedMap, Cloneable, java.io.Serializable private transient Entry root = null; . private Entry getEntry(Object key) Entry p = root; while (p != null) int cmp = compare(key,p.key); if (cmp = 0) return p; else if (cm

30、p 0) p = p.left; else p = p.right; return null; 见见TreeSet.javapublic class TreeSet extends AbstractSet implements SortedSet, Cloneable, java.io.Serializable private SortedMap m; .平衡二叉树：左子树中元素都比本节点小，右子树中元素都比本节点大。左右子树长度之差不超过。树的层数Log2n+1赵志崑集合举例集合举例创建一个散列集，保存整数对象0-9，然后用枚举器输出；将上述功能改为用树集实现；将添加对象的顺序改变，输出结果

31、不变。应用多态；添加类型检查见见Test2_1.javaimport java.util.*;public class Test2_1 public static void main(String args) HashSet set = new HashSet(); for(int i=0;i=0;i-) set.add(new Integer(i);添加类型检查（添加类型检查（Test2_2.java）Set set = new HashSet();Iterator iterator = set.iterator();Integer o = iterator.next();赵志崑列表与集合比

32、较举例列表与集合比较举例 列表中元素有位置的概念，集合中元素没有。 列表中可以含有重复元素，集合中不能。对对Test1_1.java改进改进import java.util.*;public class Test1_1 public static void main(String args) LinkedList l = new LinkedList();for(int i=0;i10;i+) l.add(new Integer(i);for(int i=0;i10;i+) l.add(new Integer(i);String s = ;Object pl = l.toArray();for

33、(int i=0;ipl.length;i+) s += pli+ ;System.out.println(s); 输出：0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9对对Test2_1.java改进改进import java.util.*;public class Test2_1 public static void main(String args) HashSet set = new HashSet();for(int i=0;i10;i+) set.add(new Integer(i);for(int i=0;i10;i+) set.add(new In

34、teger(i);String s = ;Iterator iterator = set.iterator();while(iterator.hasNext() s += iterator.next()+ ;System.out.println(s); 输出：0 1 2 3 4 5 6 7 8 9赵志崑用列表改进用列表改进SelectorSelector 用列表改进Selector。见Selector1.java。 可以添加类型检查。见Selector2.java。见见Selector1.java(用数组列表实现用数组列表实现)将学生信息保存在列表中：List students = new A

35、rrayList();读入信息时用add方法将信息添加到列表中：students.add(student);学生数量用size()方法获得：int j = rand.nextInt(students.size();选出学生用get()方法，注意要造型：Student selectedOne = (Student)(students.get(j);将选出的学生从列表中删除用remove()方法：students.remove(j);改为用链式列表实现，改为用链式列表实现，只需改为：List students = new LinkedList();赵志崑简单常用算法简单常用算法Collection

36、s类提供了一系列静态方法，可以实现简单常用算法。public class Collections static int binarySearch(List list, Object key)二分查找二分查找static void fill(List list, Object obj)填充填充static Object max(Collection coll)最大值最大值static Object min(Collection coll)最小值最小值static boolean replaceAll(List list, Object oldVal, Object newVal)替换替换stat

37、ic void reverse(List list)反向反向static void rotate(List list, int distance)循环移动循环移动static void shuffle(List list)打乱打乱static void sort(List list)排序排序static void swap(List list, int i, int j)交换交换赵志崑CollectionsCollections使用举例使用举例将列表中元素顺序打乱。求列表中最大值Collections.max(l);排序Collections.sort(l);(排序算法可参考demoapple

38、tsortDemo)反向Collections.reverse(l);循环移动Collections.rotate(l,1);二分查找l.remove(new Integer(2);Collections.sort(l);/先排序Collections.binarySearch(l,new Integer(3);Test4.javaimport java.util.*;public class Test1 public static void main(String args) LinkedList l = new LinkedList();for(int i=0;i10;i+) l.add(

39、new Integer(i);Collections. shuffle(l);printList(l); public static void printList(List l) String s = ;Iterator iterator = l.iterator();while(iterator.hasNext() s += iterator.next()+ ;System.out.println(s); 赵志崑ComparableComparable接口接口 问题： Integer类型的对象可以按照数值大小排序，一般对象如何排序？如Student对象。 试验：Test5.java将Collections的sort方法应用于Student对象。 造成的原因：察看Collections.sort方法的帮助文档，得知sort应用的对象必须实现Comparable接口。 解决方法： 为Student类实现Comparable接口。 实现了Comparable接口的对象两两之间可以比较大小。实现实现Comparable接口接口class Student implements Comparable public int compareTo(Object o) Student other = (Student)o; return( pareTo(oth