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

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

}Set——集合Set描述一個(gè)數(shù)學(xué)概念上的集合，集合中元素不能重復(fù)，沒有先后順序之分。publicinterfaceSetextendsCollection{ booleanadd(Objecto)：將元素o加入集合。 booleanaddAll(Collectionc)：將集合c中元素并入集合。 voidclear()：清空集合。 booleancontains(Objecto)：判斷集合中是否包含元素o。 booleancontainsAll(Collectionc)：判斷集合是否全部包含c中元素。 booleanequals(Objecto)：判斷兩個(gè)集合是否相等。 booleanisEmpty()：判斷集合是否為空。 Iteratoriterator()：返回一個(gè)枚舉器。 booleanremove(Objecto)：從集合中刪除元素o。 intsize()：返回集合元素個(gè)數(shù)。 Object[]toArray()：將集合轉(zhuǎn)化為一個(gè)數(shù)組。}列表與集合功能之比較列表中元素有位置的概念，集合中元素沒有。列表中可以含有重復(fù)元素，集合中不能。列表-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描述一個(gè)自動(dòng)排序的集合，除了Set中的功能為，還能夠自動(dòng)為集合中的元素排序。publicinterfaceSortedSetextendsSet{ Objectfirst()：返回第一個(gè)元素。 Objectlast()：返回最后一個(gè)元素。 SortedSetheadSet(ObjecttoElement)：返回比toElement小的元素。 SortedSettailSet(ObjectfromElement)：返回比fromElement大的元素。 SortedSetsubSet(ObjectfromElement,ObjecttoElement)：返回fromElement和toElement之間的元素。}Iterator——枚舉器Iterator用于枚舉集合或列表中的所有元素。publicinterfaceIterator{ booleanhasNext()：是否還沒有枚舉完。

Objectnext()：下一個(gè)元素。

voidremove()：從集合中刪除剛枚舉過的元素}ListIterator用于枚舉列表中的所有元素。publicinterfaceListIteratorextendsIterator{ voidadd(Objecto)：在當(dāng)前位置插入一個(gè)元素。

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

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

Objectnext()：下一個(gè)元素。

intnextIndex()：返回下一個(gè)元素的位置。

Objectprevious()：上一個(gè)元素

intpreviousIndex()：返回上一個(gè)元素的位置。

voidremove()：刪除剛剛訪問過的元素。

voidset(Objecto)：用o覆蓋剛剛訪問過的元素。}IteratorListIterator集合框架中的舊類集合框架是從Java2開始才有的，但之前已有一些“舊類”，這些類現(xiàn)在也被納入集合框架中。AbstractListListVectorStackRandomAccessHashtableMapProperties容器類堆棧類集合框架中的新類Java2新加入的類。HashMapMapAbstractMapTreeMapSortedMapAbstractCollectionListAbstractListLinkedListRandomAccessSetAbstractSequentialListListArrayListAbstractSetHashSetTreeSetCollection兩個(gè)列表類兩個(gè)集合類LinkedList——鏈?zhǔn)搅斜鞮inkedList是用雙向循環(huán)鏈表來實(shí)現(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是一個(gè)用數(shù)組來實(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(容器)的實(shí)現(xiàn)機(jī)制與ArrayList相同，區(qū)別在于：Vector支持多線程同步讀寫，ArrayList不支持。Vector的效率比ArrayList低。列表舉例創(chuàng)建一個(gè)鏈?zhǔn)搅斜恚４嬲麛?shù)對(duì)象0-9，然后輸出可以轉(zhuǎn)化為數(shù)組輸出；可以用枚舉器輸出；將上述功能改為用數(shù)組列表實(shí)現(xiàn)；應(yīng)用多態(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ù)組列表實(shí)現(xiàn)（Test1_2.java）

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

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

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

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