09集合类型数据结构教学课件

09集合类型数据结构6、法律的基础有两个，而且只有两个……公平和实用。——伯克7、有两种和平的暴力，那就是法律和礼节。——歌德8、法律就是秩序，有好的法律才有好的秩序。——亚里士多德9、上帝把法律和公平凑合在一起，可是人类却把它拆开。——查·科尔顿10、一切法律都是无用的，因为好人用不着它们，而坏人又不会因为它们而变得规矩起来。——德谟耶克斯09集合类型数据结构09集合类型数据结构6、法律的基础有两个，而且只有两个……公平和实用。——伯克7、有两种和平的暴力，那就是法律和礼节。——歌德8、法律就是秩序，有好的法律才有好的秩序。——亚里士多德9、上帝把法律和公平凑合在一起，可是人类却把它拆开。——查·科尔顿10、一切法律都是无用的，因为好人用不着它们，而坏人又不会因为它们而变得规矩起来。——德谟耶克斯Java程序设计赵志崑山东财政学院计算机信息工程学院问题抽奖器程序中如何解决100人的限制？方法1：将预留空间改得足够大。造成内存空间浪费。如何确定多少为足够大。方法2：动态生成数组。效率较低方法3：使用链表。Student[]students=newStudent[10000];Selector1.javawhile(line!=null){……students1=newStudent[totalCount+1];System.arraycopy(student,0,students,0,totalCount);students1[totalCount]=student;students=students1;totalCount++;line=in.readLine();}Selector2.javaclassStudent{privateStringid;privateStringname;privateStringdepartment;publicStudentnext;publicStudent(){…};…}功能定义和具体实现分开Java中采用功能定义和具体实现分开的思想。功能定义：定义从外部看到的模型的功能，即模型可以如何使用。具体实现：模型内部的实现机制。例如：录音机功能包括录音和放音。这些功能可以用磁带录音机、Mp3等来实现。录音机功能录音放音磁带录音机磁头磁带马达Mp3播放器芯片善存功能定义具体实现接口和实现接口：Java中用接口来描述一个模型在逻辑上的功能。实现：Java中用具体的类来实现这些功能，在这些类中用某个具体的数据结构来实现接口定义的功能。例如：队列可以用链表实现。12345队首队尾60出队入队数据链接数据链接数据链接表头表尾数据链接数据链接InterfaceQueue{voidadd(Objectobj);Objectremove();intsize();}classLinkedListimplementsQueue{publicvoidadd(Objectobj){…};publicObjectremove(){…};publicintsize(){…};privateLinkedListheader;privateLinkedListtail;privateclassEntry{Objectelement;Entrynext;}}队列链表接口和实现分开将接口和实现分开：一种功能可以有多种实现方法。例如：队列既可以用链表实现，也可以用循环数组实现。编写程序时，了解接口即可完成逻辑功能，了解具体实现则可以提高程序效率和适用性。12345队首队尾60出队入队数据链接数据链接数据链接表头表尾数据链接数据链接队列链表32154开头结尾循环数组集合框架中的接口框架(framework)是类和接口的集合，这些类和接口拥有许多有用的功能和机制。使用其中的某个或几个类和接口，能够完成一些特定功能。RandomAccessCollectionListSetSortedSetMapSortedMapIteratorListIterator集合接口映射接口枚举器接口随机访问标志接口List——列表List描述列表接口，列表中元素可以重复，有先后顺序。publicinterfaceListextendsCollection{ booleanadd(Objecto)：将元素o添加到列表最后。 voidclear()：清空列表内容。 booleancontains(Objecto)：判断列表中是否包含元素o。 Objectget(intindex)：获取列表中index位置的元素。 intindexOf(Objecto)：获取元素o在列表中的位置。 booleanisEmpty()：列表是否为空。 intlastIndexOf(Objecto)：获取列表中最后一个o出现的位置。 ListIteratorlistIterator()：获取一个枚举器。 Objectremove(intindex)：去除位置index的元素。 booleanremove(Objecto)：去除列表中第一个出现的o元素。 Objectset(intindex,Objectelement)：用element取代位置index的元素。 intsize()：返回列表中元素个数。 ListsubList(intfromIndex,inttoIndex)：得到一个子范围。 Object[]toArray()：将列表转化为一个数组。

}Set——集合Set描述一个数学概念上的集合，集合中元素不能重复，没有先后顺序之分。publicinterfaceSetextendsCollection{ booleanadd(Objecto)：将元素o加入集合。 booleanaddAll(Collectionc)：将集合c中元素并入集合。 voidclear()：清空集合。 booleancontains(Objecto)：判断集合中是否包含元素o。 booleancontainsAll(Collectionc)：判断集合是否全部包含c中元素。 booleanequals(Objecto)：判断两个集合是否相等。 booleanisEmpty()：判断集合是否为空。 Iteratoriterator()：返回一个枚举器。 booleanremove(Objecto)：从集合中删除元素o。 intsize()：返回集合元素个数。 Object[]toArray()：将集合转化为一个数组。}列表与集合功能之比较列表中元素有位置的概念，集合中元素没有。列表中可以含有重复元素，集合中不能。列表-Listbooleanadd(Objecto)voidclear()booleancontains(Objecto)booleanisEmpty()booleanremove(Objecto)intsize()Object[]toArray()

Objectget(intindex)intindexOf(Objecto)intlastIndexOf(Objecto)ListIteratorlistIterator()Objectremove(intindex)Objectset(intindex,Objectelement)ListsubList(intfromIndex,inttoIndex)集合-Setbooleanadd(Objecto)voidclear()booleancontains(Objecto)booleanisEmpty()booleanremove(Objecto)intsize()Object[]toArray()booleanaddAll(Collectionc)booleancontainsAll(Collectionc)booleanequals(Objecto)Iteratoriterator()SortedSet——有序集合SortedSet描述一个自动排序的集合，除了Set中的功能为，还能够自动为集合中的元素排序。publicinterfaceSortedSetextendsSet{ Objectfirst()：返回第一个元素。 Objectlast()：返回最后一个元素。 SortedSetheadSet(ObjecttoElement)：返回比toElement小的元素。 SortedSettailSet(ObjectfromElement)：返回比fromElement大的元素。 SortedSetsubSet(ObjectfromElement,ObjecttoElement)：返回fromElement和toElement之间的元素。}Iterator——枚举器Iterator用于枚举集合或列表中的所有元素。publicinterfaceIterator{ booleanhasNext()：是否还没有枚举完。

Objectnext()：下一个元素。

voidremove()：从集合中删除刚枚举过的元素}ListIterator用于枚举列表中的所有元素。publicinterfaceListIteratorextendsIterator{ voidadd(Objecto)：在当前位置插入一个元素。

booleanhasNext()：正向是否还有其他元素。

booleanhasPrevious()：反向是否还有其他元素

Objectnext()：下一个元素。

intnextIndex()：返回下一个元素的位置。

Objectprevious()：上一个元素

intpreviousIndex()：返回上一个元素的位置。

voidremove()：删除刚刚访问过的元素。

voidset(Objecto)：用o覆盖刚刚访问过的元素。}IteratorListIterator集合框架中的旧类集合框架是从Java2开始才有的，但之前已有一些“旧类”，这些类现在也被纳入集合框架中。AbstractListListVectorStackRandomAccessHashtableMapProperties容器类堆栈类集合框架中的新类Java2新加入的类。HashMapMapAbstractMapTreeMapSortedMapAbstractCollectionListAbstractListLinkedListRandomAccessSetAbstractSequentialListListArrayListAbstractSetHashSetTreeSetCollection两个列表类两个集合类LinkedList——链式列表LinkedList是用双向循环链表来实现List接口的类。privateEntryaddBefore(Objecto,Entrye){

EntrynewEntry=newEntry(o,e,e.previous);newEntry.previous.next=newEntry;newEntry.next.previous=newEntry;size++;modCount++;returnnewEntry;}}见LinkedList.javapublicclassLinkedListextendsAbstractSequentialListimplementsList,Cloneable,java.io.Serializable{privatestaticclassEntry{Objectelement;

Entrynext;

Entryprevious;Entry(Objectelement,Entrynext,Entryprevious){

this.element=element;this.next=next;this.previous=previous;}}表头ObjectnextpreviousObjectnextpreviousObjectnextpreviousObjectnextpreviousObjectnextprevious待插入的EntryArrayList——数组列表ArrayList是一个用数组来实现列表功能的类。elementDataoldCapacitynewCapacitySystem.arraycopy见ArrayList.javapublicclassArrayListextendsAbstractListimplementsList,RandomAccess,Cloneable,java.io.Serializable{privatetransientObjectelementData[];publicvoidensureCapacity(intminCapacity){modCount++;intoldCapacity=elementData.length;

if(minCapacity>oldCapacity){ObjectoldData[]=elementData;intnewCapacity=(oldCapacity*3)/2+1;if(newCapacity<minCapacity)newCapacity=minCapacity;

elementData=newObject[newCapacity];

System.arraycopy(oldData,0,elementData,0,size);}}}Vector(容器)的实现机制与ArrayList相同，区别在于：Vector支持多线程同步读写，ArrayList不支持。Vector的效率比ArrayList低。列表举例创建一个链式列表，保存整数对象0-9，然后输出可以转化为数组输出；可以用枚举器输出；将上述功能改为用数组列表实现；应用多态见Test1_1.javaimportjava.util.*;publicclassTest1{publicstaticvoidmain(String[]args){LinkedListl=newLinkedList();for(inti=0;i<10;i++){ l.add(newInteger(i));}Strings="";for(inti=0;i<l.size();i++){ Objecto=l.get(i); s+=o+"";}System.out.println(s);}}用枚举器输出

Iteratoriterator=l.iterator(); while(iterator.hasNext()) s+=iterator.next()+"";用数组列表实现（Test1_2.java）

ArrayListl=newArrayList();应用多态

Listl=newArrayList();用Vector(容器)实现

Listl=newVector();转化为数组

Object[]pl=l.toArray();列表中元素的类型列表中可以放不同类型的对象由于多态性和单根继承，列表中使用的Object类型的引用可以指向任何对象。见Test1_3.java可以为列表中元素设置类型检查在声明列表引用、列表对象和枚举器对象时，可以设置对列表中元素的类型检查。见Test1_4.java//Test1_3.javaimportjava.util.*;publicclassTest1_3{publicstaticvoidmain(String[]args){Listl=newLinkedList();l.add(newInteger(5));l.add(newFloat(2.3f));l.add(newBoolean(true));l.add("string");……}}//Test1_4.javaimportjava.util.*;publicclassTest1_4{publicstaticvoidmain(String[]args){List<Integer>l=newLinkedList<Integer>();for(inti=0;i<10;i++)l.add(newInteger(i));Strings="";Iterator<Integer>iterator=l.iterator();while(iterator.hasNext()){

Integero=iterator.next(); s+=o+"";}System.out.println(s);}}HashSet——散列(哈希)集HashSet是用散列表实现集合功能的类。散列(O(C))能够解决链表和数组中的无序数据查找问题(O(n))。见HashMap.javapublicclassHashMapextendsAbstractMapimplementsMap,Cloneable,Serializable{Entry[]table;staticclassEntryimplementsMap.Entry{finalObjectkey;Objectvalue;finalinthash;Entrynext;}publicbooleancontainsKey(Objectkey){Objectk=maskNull(key);inthash=hash(k);inti=indexFor(hash,table.length);Entrye=table[i];while(e!=null){if(e.hash==hash&&eq(k,e.key))returntrue;e=e.next;}returnfalse;}}见HashSet.javapublicclassHashSetextendsAbstractSetimplementsSet,Cloneable,java.io.Serializable{privateHashMapmap;......}012…N-2N-1散列表TreeSet——树集TreeSet是用平衡二叉树实现有序集合功能的类。树集是个有序集合，其插入操作的速度比散列集慢(O(Log2n))。见TreeMap.javapublicclassTreeMapextendsAbstractMapimplementsSortedMap,Cloneable,java.io.Serializable{privatetransientEntryroot=null;......privateEntrygetEntry(Objectkey){Entryp=root;while(p!=null){intcmp=compare(key,p.key);if(cmp==0)returnp;elseif(cmp<0)p=p.left;

elsep=p.right;}returnnull;}}见TreeSet.javapublicclassTreeSetextendsAbstractSetimplementsSortedSet,Cloneable,java.io.Serializable{privateSortedMapm;......}平衡二叉树：左子树中元素都比本节点小，右子树中元素都比本节点大。左右子树长度之差不超过１。树的层数＝[Log2n]+1１２３５４６集合举例创建一个散列集，保存整数对象0-9，然后用枚举器输出；将上述功能改为用树集实现；将添加对象的顺序改变，输出结果不变。应用多态；添加类型检查见Test2_1.javaimportjava.util.*;publicclassTest2_1{publicstaticvoidmain(String[]args){HashSetset=newHashSet();for(inti=0;i<10;i++){ set.add(newInteger(i));}Strings="";Iteratoriterator=set.iterator();while(iterator.hasNext()){ Objecto=iterator.next(); s+=o+"";}System.out.println(s);}}用树集实现 TreeSetset=newTreeSet();应用多态 Setset=newTreeSet();改变添加对象的顺序 for(inti=9;i>=0;i--) set.add(newInteger(i));添加类型检查（Test2_2.java） Set<Integer>set=newHashSet<Integer>(); …… Iterator<Integer>iterator=set.iterator(); ……

Integero=iterator.next();列表与集合比较举例列表中元素有位置的概念，集合中元素没有。列表中可以含有重复元素，集合中不能。对Test1_1.java改进importjava.util.*;publicclassTest1_1{publicstaticvoidmain(String[]args){ LinkedListl=newLinkedList(); for(inti=0;i<10;i++) l.add(newInteger(i)); for(inti=0;i<10;i++) l.add(newInteger(i)); Strings=""; Object[]pl=l.toArray(); for(inti=0;i<pl.length;i++) s+=pl[i]+""; System.out.println(s);}}输出：01234567890123456789对Test2_1.java改进importjava.util.*;publicclassTest2_1{publicstaticvoidmain(String[]args){ HashSetset=newHashSet(); for(inti=0;i<10;i++) set.add(newInteger(i)); for(inti=0;i<10;i++) set.add(newInteger(i)); Strings=""; Iteratoriterator=set.iterator(); while(iterator.hasNext()) s+=iterator.next()+""; System.out.println(s);}}输出：0123456789用列表改进Selector用列表改进Selector。见Selector1.java。可以添加类型检查。见Selector2.java。见Selector1.java(用数组列表实现)将学生信息保存在列表中： Liststudents=newArrayList();读入信息时用add方法将信息添加到列表中： students.add(student);学生数量用size()方法获得： intj=rand.nextInt(students.size());选出学生用get()方法，注意要造型： StudentselectedOne=(Student)(students.get(j));将选出的学生从列表中删除用remove()方法： students.remove(j);改为用链式列表实现，只需改为： Liststudents=newLinkedList();简单常用算法Collections类提供了一系列静态方法，可以实现简单常用算法。publicclassCollections{ staticintbinarySearch(Listlist,Objectkey)二分查找 staticvoidfill(Listlist,Objectobj)填充 staticObjectmax(Collectioncoll)最大值 staticObjectmin(Collectioncoll)最小值 staticbooleanreplaceAll(Listlist,ObjectoldVal,ObjectnewVal)替换 staticvoidreverse(Listlist)反向 staticvoidrotate(Listlist,intdistance)循环移动 staticvoidshuffle(Listlist)打乱 staticvoidsort(Listlist)排序 staticvoidswap(Listlist,inti,intj)交换}Collections使用举例将列表中元素顺序打乱。求列表中最大值Collections.max(l);排序Collections.sort(l);(排序算法可参考demo\applet\sortDemo)反向Collections.reverse(l);循环移动Collections.rotate(l,1);二分查找l.remove(newInteger(2));Collections.sort(l);//先排序Collections.binarySearch(l,newInteger(3));Test4.javaimportjava.util.*;publicclassTest1{publicstaticvoidmain(String[]args){ LinkedListl=newLinkedList(); for(inti=0;i<10;i++) l.add(newInteger(i));

Collections.shuffle(l); printList(l);}publicstaticvoidprintList(Listl){ Strings=""; Iteratoriterator=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接口classStudentimplementsComparable{publicintcompareTo(Objecto){Studentother=(Student)o;return(idpareTo(other.id));}}带类型检查classStudentimplementsComparable<St