09集合類型數(shù)據(jù)結(jié)構(gòu)教學課件

09集合類型數(shù)據(jù)結(jié)構(gòu)6、法律的基礎(chǔ)有兩個，而且只有兩個……公平和實用?！?、有兩種和平的暴力，那就是法律和禮節(jié)?！璧?、法律就是秩序，有好的法律才有好的秩序?！獊喞锸慷嗟?、上帝把法律和公平湊合在一起，可是人類卻把它拆開?！椤た茽栴D10、一切法律都是無用的，因為好人用不著它們，而壞人又不會因為它們而變得規(guī)矩起來。——德謨耶克斯09集合類型數(shù)據(jù)結(jié)構(gòu)09集合類型數(shù)據(jù)結(jié)構(gòu)6、法律的基礎(chǔ)有兩個，而且只有兩個……公平和實用?！?、有兩種和平的暴力，那就是法律和禮節(jié)?！璧?、法律就是秩序，有好的法律才有好的秩序?！獊喞锸慷嗟?、上帝把法律和公平湊合在一起，可是人類卻把它拆開?！椤た茽栴D10、一切法律都是無用的，因為好人用不著它們，而壞人又不會因為它們而變得規(guī)矩起來?！轮円怂笿ava程序設(shè)計趙志崑山東財政學院計算機信息工程學院問題抽獎器程序中如何解決100人的限制？方法1：將預留空間改得足夠大。造成內(nèi)存空間浪費。如何確定多少為足夠大。方法2：動態(tài)生成數(shù)組。效率較低方法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(){…};…}功能定義和具體實現(xiàn)分開Java中采用功能定義和具體實現(xiàn)分開的思想。功能定義：定義從外部看到的模型的功能，即模型可以如何使用。具體實現(xiàn)：模型內(nèi)部的實現(xiàn)機制。例如：錄音機功能包括錄音和放音。這些功能可以用磁帶錄音機、Mp3等來實現(xiàn)。錄音機功能錄音放音磁帶錄音機磁頭磁帶馬達Mp3播放器芯片善存功能定義具體實現(xiàn)接口和實現(xiàn)接口：Java中用接口來描述一個模型在邏輯上的功能。實現(xiàn)：Java中用具體的類來實現(xiàn)這些功能，在這些類中用某個具體的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)接口定義的功能。例如：隊列可以用鏈表實現(xiàn)。12345隊首隊尾60出隊入隊數(shù)據(jù)鏈接數(shù)據(jù)鏈接數(shù)據(jù)鏈接表頭表尾數(shù)據(jù)鏈接數(shù)據(jù)鏈接InterfaceQueue{voidadd(Objectobj);Objectremove();intsize();}classLinkedListimplementsQueue{publicvoidadd(Objectobj){…};publicObjectremove(){…};publicintsize(){…};privateLinkedListheader;privateLinkedListtail;privateclassEntry{Objectelement;Entrynext;}}隊列鏈表接口和實現(xiàn)分開將接口和實現(xiàn)分開：一種功能可以有多種實現(xiàn)方法。例如：隊列既可以用鏈表實現(xiàn)，也可以用循環(huán)數(shù)組實現(xiàn)。編寫程序時，了解接口即可完成邏輯功能，了解具體實現(xiàn)則可以提高程序效率和適用性。12345隊首隊尾60出隊入隊數(shù)據(jù)鏈接數(shù)據(jù)鏈接數(shù)據(jù)鏈接表頭表尾數(shù)據(jù)鏈接數(shù)據(jù)鏈接隊列鏈表32154開頭結(jié)尾循環(huán)數(shù)組集合框架中的接口框架(framework)是類和接口的集合，這些類和接口擁有許多有用的功能和機制。使用其中的某個或幾個類和接口，能夠完成一些特定功能。RandomAccessCollectionListSetSortedSetMapSortedMapIteratorListIterator集合接口映射接口枚舉器接口隨機訪問標志接口List——列表List描述列表接口，列表中元素可以重復，有先后順序。publicinterfaceListextendsCollection{ booleanadd(Objecto)：將元素o添加到列表最后。 voidclear()：清空列表內(nèi)容。 booleancontains(Objecto)：判斷列表中是否包含元素o。 Objectget(intindex)：獲取列表中index位置的元素。 intindexOf(Objecto)：獲取元素o在列表中的位置。 booleanisEmpty()：列表是否為空。 intlastIndexOf(Objecto)：獲取列表中最后一個o出現(xiàn)的位置。 ListIteratorlistIterator()：獲取一個枚舉器。 Objectremove(intindex)：去除位置index的元素。 booleanremove(Objecto)：去除列表中第一個出現(xiàn)的o元素。 Objectset(intindex,Objectelement)：用element取代位置index的元素。 intsize()：返回列表中元素個數(shù)。 ListsubList(intfromIndex,inttoIndex)：得到一個子范圍。 Object[]toArray()：將列表轉(zhuǎn)化為一個數(shù)組。

}Set——集合Set描述一個數(shù)學概念上的集合，集合中元素不能重復，沒有先后順序之分。publicinterfaceSetextendsCollection{ booleanadd(Objecto)：將元素o加入集合。 booleanaddAll(Collectionc)：將集合c中元素并入集合。 voidclear()：清空集合。 booleancontains(Objecto)：判斷集合中是否包含元素o。 booleancontainsAll(Collectionc)：判斷集合是否全部包含c中元素。 booleanequals(Objecto)：判斷兩個集合是否相等。 booleanisEmpty()：判斷集合是否為空。 Iteratoriterator()：返回一個枚舉器。 booleanremove(Objecto)：從集合中刪除元素o。 intsize()：返回集合元素個數(shù)。 Object[]toArray()：將集合轉(zhuǎn)化為一個數(shù)組。}列表與集合功能之比較列表中元素有位置的概念，集合中元素沒有。列表中可以含有重復元素，集合中不能。列表-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開始才有的，但之前已有一些“舊類”，這些類現(xiàn)在也被納入集合框架中。AbstractListListVectorStackRandomAccessHashtableMapProperties容器類堆棧類集合框架中的新類Java2新加入的類。HashMapMapAbstractMapTreeMapSortedMapAbstractCollectionListAbstractListLinkedListRandomAccessSetAbstractSequentialListListArrayListAbstractSetHashSetTreeSetCollection兩個列表類兩個集合類LinkedList——鏈式列表LinkedList是用雙向循環(huán)鏈表來實現(xiàn)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——數(shù)組列表ArrayList是一個用數(shù)組來實現(xiàn)列表功能的類。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(容器)的實現(xiàn)機制與ArrayList相同，區(qū)別在于：Vector支持多線程同步讀寫，ArrayList不支持。Vector的效率比ArrayList低。列表舉例創(chuàng)建一個鏈式列表，保存整數(shù)對象0-9，然后輸出可以轉(zhuǎn)化為數(shù)組輸出；可以用枚舉器輸出；將上述功能改為用數(shù)組列表實現(xiàn)；應用多態(tài)見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()+"";用數(shù)組列表實現(xiàn)（Test1_2.java）

ArrayListl=newArrayList();應用多態(tài)

Listl=newArrayList();用Vector(容器)實現(xiàn)

Listl=newVector();轉(zhuǎn)化為數(shù)組

Object[]pl=l.toArray();列表中元素的類型列表中可以放不同類型的對象由于多態(tài)性和單根繼承，列表中使用的Object類型的引用可以指向任何對象。見Test1_3.java可以為列表中元素設(shè)置類型檢查在聲明列表引用、列表對象和枚舉器對象時，可以設(shè)置對列表中元素的類型檢查。見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是用散列表實現(xiàn)集合功能的類。散列(O(C))能夠解決鏈表和數(shù)組中的無序數(shù)據(jù)查找問題(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是用平衡二叉樹實現(xiàn)有序集合功能的類。樹集是個有序集合，其插入操作的速度比散列集慢(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;......}平衡二叉樹：左子樹中元素都比本節(jié)點小，右子樹中元素都比本節(jié)點大。左右子樹長度之差不超過１。樹的層數(shù)＝[Log2n]+1１２３５４６集合舉例創(chuàng)建一個散列集，保存整數(shù)對象0-9，然后用枚舉器輸出；將上述功能改為用樹集實現(xiàn)；將添加對象的順序改變，輸出結(jié)果不變。應用多態(tài)；添加類型檢查見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);}}用樹集實現(xiàn) TreeSetset=newTreeSet();應用多態(tài) 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?？梢蕴砑宇愋蜋z查。見Selector2.java。見Selector1.java(用數(shù)組列表實現(xiàn))將學生信息保存在列表中： Liststudents=newArrayList();讀入信息時用add方法將信息添加到列表中： students.add(student);學生數(shù)量用size()方法獲得： intj=rand.nextInt(students.size());選出學生用get()方法，注意要造型： StudentselectedOne=(Student)(students.get(j));將選出的學生從列表中刪除用remove()方法： students.remove(j);改為用鏈式列表實現(xiàn)，只需改為： Liststudents=newLinkedList();簡單常用算法Collections類提供了一系列靜態(tài)方法，可以實現(xiàn)簡單常用算法。publicclassCollections{ staticintbinarySearch(Listlist,Objectkey)二分查找 staticvoidfill(Listlist,Objectobj)填充 staticObjectmax(Collectioncoll)最大值 staticObjectmin(Collectioncoll)最小值 staticbooleanreplaceAll(Listlist,ObjectoldVal,ObjectnewVal)替換 staticvoidreverse(Listlist)反向 staticvoidrotate(Listlist,intdistance)循環(huán)移動 staticvoidshuffle(Listlist)打亂 staticvoidsort(Listlist)排序 staticvoidswap(Listlist,inti,intj)交換}Collections使用舉例將列表中元素順序打亂。求列表中最大值Collections.max(l);排序Collections.sort(l);(排序算法可參考demo\applet\sortDemo)反向Collections.reverse(l);循環(huán)移動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類型的對象可以按照數(shù)值大小排序，一般對象如何排序？如Student對象。試驗：Test5.java將Collections的sort方法應用于Student對象。造成的原因：察看Collections.sort方法的幫助文檔，得知sort應用的對象必須實現(xiàn)Comparable接口。解決方法：為Student類實現(xiàn)Comparable接口。實現(xiàn)了Comparable接口的對象兩兩之間可以比較大小。實現(xiàn)Comparable接口classStudentimplementsComparable{publicintcompareTo(Objecto){Studentother=(Student)o;return(idpareTo(other.id));}}帶類型檢查classStudentimplementsComparable<St