集合类型数据结构.ppt

Java程序设计,赵志崑 山东财政学院计算机信息工程学院 ,问题,抽奖器程序中如何解决100人的限制？ 方法1：将预留空间改得足够大。 造成内存空间浪费。 如何确定多少为足够大。 方法2：动态生成数组。 效率较低 方法3：使用链表。,Student students = new Student10000;,Selector1.java while(line != null) students1 = new StudenttotalCount+1; System.arraycopy(student,0,students,0,totalCount); students1totalCount = student; students = students1; totalCount+; line = in.readLine(); ,Selector2.java class Student private String id; private String name; private String department; public Student next; public Student(); ,Java对基本数据结构的支持,链表是一种非常常用的数据结构，类似的还有队列、集合等等，是否所有这些数据结构都要自己来实现呢？ 编写程序有两个关键问题，数据结构和算法。 数据结构是组织和存储数据的方法 算法是操作数据的方法 有些数据结构和算法在绝大多数程序中都要用到，开发工具的设计者就寻找一种机制，能够让开发人员不用每次都做重复劳动。 头文件和库函数：最原始的方法。 模板库(STL)：C+中采用的方法。 类和接口：Java中采用的方法。 Java的设计者在设计Java时，充分考虑了这一点，通过单根继承(Object类)，使用简单的类和接口提供了对许多基本数据结构的支持。,常用数据结构和算法,基本数据结构有四种：数组、链表、树和网。 常用基本算法有两个：排序和查找(搜索)。 排序：将一组数据逻辑上按一定顺序存放。 查找：从一组数据中找出满足某一要求的数据。,功能定义和具体实现分开,Java中采用功能定义和具体实现分开的思想。 功能定义：定义从外部看到的模型的功能，即模型可以如何使用。 具体实现：模型内部的实现机制。 例如： 录音机功能包括录音和放音。 这些功能可以用磁带录音机、Mp3等来实现。,功能定义,具体实现,接口和实现,接口：Java中用接口来描述一个模型在逻辑上的功能。 实现：Java中用具体的类来实现这些功能，在这些类中用某个具体的数据结构来实现接口定义的功能。 例如：队列可以用链表实现。,接口和实现分开,将接口和实现分开：一种功能可以有多种实现方法。 例如：队列既可以用链表实现，也可以用循环数组实现。 编写程序时，了解接口即可完成逻辑功能，了解具体实现则可以提高程序效率和适用性。,集合框架中的接口,框架(framework)是类和接口的集合，这些类和接口拥有许多有用的功能和机制。使用其中的某个或几个类和接口，能够完成一些特定功能。,RandomAccess,集合接口,映射接口,枚举器接口,随机访问标志接口,List列表,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(Object 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)：用element取代位置index的元素。 int size()：返回列表中元素个数。 List subList(int fromIndex, int toIndex)：得到一个子范围。 Object toArray()：将列表转化为一个数组。 ,Set集合,Set描述一个数学概念上的集合，集合中元素不能重复，没有先后顺序之分。 public interface Set extends Collection boolean add(Object o)：将元素o加入集合。 boolean addAll(Collection c)：将集合c中元素并入集合。 void clear()：清空集合。 boolean contains(Object o)：判断集合中是否包含元素o。 boolean containsAll(Collection c)：判断集合是否全部包含c中元素。 boolean equals(Object o)：判断两个集合是否相等。 boolean isEmpty()：判断集合是否为空。 Iterator iterator()：返回一个枚举器。 boolean remove(Object o)：从集合中删除元素o。 int size()：返回集合元素个数。 Object toArray()：将集合转化为一个数组。 ,列表与集合功能之比较,列表中元素有位置的概念，集合中元素没有。 列表中可以含有重复元素，集合中不能。,列表-List boolean add(Object o) void clear() boolean contains(Object o) boolean isEmpty() boolean remove(Object o) int size() Object toArray() 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),集合-Set boolean add(Object o) void clear() boolean contains(Object o) boolean isEmpty() boolean remove(Object o) int size() Object toArray() boolean addAll(Collection c) boolean containsAll(Collection c) boolean equals(Object o) Iterator iterator(),SortedSet有序集合,SortedSet描述一个自动排序的集合，除了Set中的功能为，还能够自动为集合中的元素排序。 public interface SortedSet extends Set Object first()：返回第一个元素。 Object last()：返回最后一个元素。 SortedSet headSet(Object toElement)：返回比toElement小的元素。 SortedSet tailSet(Object fromElement)：返回比fromElement大的元素。 SortedSet subSet(Object fromElement, Object toElement)：返回fromElement和toElement之间的元素。 ,Iterator枚举器,Iterator用于枚举集合或列表中的所有元素。 public interface Iterator boolean hasNext()：是否还没有枚举完。 Object next()：下一个元素。 void remove()：从集合中删除刚枚举过的元素 ListIterator用于枚举列表中的所有元素。 public interface ListIterator extends Iterator void add(Object o)：在当前位置插入一个元素。 boolean hasNext()：正向是否还有其他元素。 boolean hasPrevious()：反向是否还有其他元素 Object next()：下一个元素。 int nextIndex()：返回下一个元素的位置。 Object previous()：上一个元素 int previousIndex()：返回上一个元素的位置。 void remove()：删除刚刚访问过的元素。 void set(Object o)：用o覆盖刚刚访问过的元素。 ,集合框架中的旧类,集合框架是从Java2开始才有的，但之前已有一些“旧类”，这些类现在也被纳入集合框架中。,集合框架中的新类,Java2新加入的类。,LinkedList链式列表,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.java,public class LinkedList extends AbstractSequentialList 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; ,ArrayList数组列表,ArrayList是一个用数组来实现列表功能的类。,见ArrayList.java public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable private transient Object 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 ObjectnewCapacity; System.arraycopy(oldData, 0, elementData, 0, size); ,Vector(容器)的实现机制与ArrayList相同，区别在于： Vector支持多线程同步读写，ArrayList不支持。 Vector的效率比ArrayList低。,列表举例,创建一个链式列表，保存整数对象0-9，然后输出 可以转化为数组输出；可以用枚举器输出； 将上述功能改为用数组列表实现； 应用多态,见Test1_1.java import java.util.*; public class Test1 public static void main(String args) 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） ArrayList 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.java import java.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.java import java.util.*; public class Test1_4 public static void main(String args) List l = new LinkedList(); for(int i=0;i iterator = l.iterator(); while(iterator.hasNext() Integer o = iterator.next(); s += o+“ “; System.out.println(s); ,HashSet散列(哈希)集,HashSet是用散列表实现集合功能的类。散列(O(C)能够解决链表和数组中的无序数据查找问题(O(n)。,见HashMap.java public class HashMap extends 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 = tablei; while (e != null) if (e.hash = hash ,见HashSet.java public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable private HashMap map; ,TreeSet树集,TreeSet是用平衡二叉树实现有序集合功能的类。树集是个有序集合，其插入操作的速度比散列集慢(O(Log2n)。,见TreeMap.java public 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 (cmp 0) p = p.left; else p = p.right; return null; ,见TreeSet.java public class TreeSet extends AbstractSet implements SortedSet, Cloneable, java.io.Serializable private SortedMap m; ,平衡二叉树： 左子树中元素都比本节点小， 右子树中元素都比本节点大。 左右子树长度之差不超过。 树的层数Log2n+1,集合举例,创建一个散列集，保存整数对象0-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); String s = “; Iterator iterator = set.iterator(); while(iterator.hasNext() Object o = iterator.next(); s += o+“ “; System.out.println(s); ,用树集实现 TreeSet set = new TreeSet();,应用多态 Set set = new TreeSet();,改变添加对象的顺序 for(int i=9;i=0;i-) set.add(new Integer(i);,添加类型检查（Test2_2.java） Set set = new HashSet(); Iterator iterator = set.iterator(); Integer o = iterator.next();,列表与集合比较举例,列表中元素有位置的概念，集合中元素没有。 列表中可以含有重复元素，集合中不能。,对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(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 Integer(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,用列表改进Selector,用列表改进Selector。见Selector1.java。 可以添加类型检查。见Selector2.java。,见Selector1.java(用数组列表实现) 将学生信息保存在列表中： List students = new ArrayList(); 读入信息时用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();,简单常用算法,Collections类提供了一系列静态方法，可以实现简单常用算法。 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)替换 static 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)交换 ,Collections使用举例,将列表中元素顺序打乱。 求列表中最大值 Collections.max(l); 排序 Collections.sort(l); (排序算法可参考demoappletsortDemo) 反向 Collections.reverse(l); 循环移动 Collections.rotate(l,1); 二分查找 l.remove(new Integer(2); Collections.sort(l);/先排序 Collections.binarySearch(l,new Integer(3);,Test4.java import java.util.*; public class Test1 public static void main(String args) LinkedList l = new LinkedList(); for(int i=0;i10;i+) l.add(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); ,Comparable接口,问题： 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(other.id ) ); ,带类型检查 class Student implements Comparable public int compareTo(Student o) return( id