Java程序設(shè)計(jì)——09集合框架

1、計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院趙志崑趙志崑問題問題 隨機(jī)點(diǎn)名器程序中如何解決100人的限制？ 方法1：將預(yù)留空間改得足夠大。 造成內(nèi)存空間浪費(fèi)。 如何確定多少為足夠大。 方法2：動(dòng)態(tài)生成數(shù)組。 效率較低 方法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對基本數(shù)據(jù)結(jié)構(gòu)的支持對基本數(shù)據(jù)結(jié)構(gòu)的支持 鏈表是一種非常常用的數(shù)據(jù)結(jié)構(gòu)，類似的還有隊(duì)列、集合等等，是否所有這些數(shù)據(jù)結(jié)構(gòu)都要自己來實(shí)現(xiàn)呢？ 編寫程序有兩個(gè)關(guān)鍵問題，數(shù)據(jù)結(jié)構(gòu)和算法。 數(shù)據(jù)結(jié)構(gòu)是組織和存儲(chǔ)數(shù)據(jù)的方

3、法 算法是操作數(shù)據(jù)的方法 有些數(shù)據(jù)結(jié)構(gòu)和算法在絕大多數(shù)程序中都要用到，開發(fā)工具的設(shè)計(jì)者就尋找一種機(jī)制，能夠讓開發(fā)人員不用每次都做重復(fù)勞動(dòng)。 頭文件和庫函數(shù)：最原始的方法。 模板庫(STL)：C+中采用的方法。 類和接口：Java中采用的方法。 Java的設(shè)計(jì)者在設(shè)計(jì)Java時(shí)，充分考慮了這一點(diǎn)，通過單根繼承(Object類)，使用簡單的類和接口提供了對許多基本數(shù)據(jù)結(jié)構(gòu)的支持。趙志崑常用數(shù)據(jù)結(jié)構(gòu)和算法常用數(shù)據(jù)結(jié)構(gòu)和算法 基本數(shù)據(jù)結(jié)構(gòu)有四種：數(shù)組、鏈表、樹和網(wǎng)。 常用基本算法有兩大類：排序和查找(搜索)。 排序：將一組數(shù)據(jù)邏輯上按一定順序存放。 查找：從一組數(shù)據(jù)中找出滿足某一要求的數(shù)據(jù)。趙志崑功能

4、定義和具體實(shí)現(xiàn)分開功能定義和具體實(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)接口和實(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ù)鏈接表頭表尾

5、數(shù)據(jù)鏈接數(shù)據(jù)鏈接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; 隊(duì)列鏈表趙志崑接口和實(shí)現(xiàn)分開接口和

6、實(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è)類和接口，能夠完成一些特定功能。RandomAccessCollectionListSetSortedSetMapSortedMapIteratorListI

7、terator集合接口映射接口枚舉器接口隨機(jī)訪問標(biāo)志接口趙志崑ListList列表列表 List描述列表接口，列表中元素可以重復(fù)，有先后順序。public interface List extends Collection boolean add(Object o)：將元素將元素o添加到列表最后。添加到列表最后。void clear()：清空列表內(nèi)容。清空列表內(nèi)容。boolean contains(Object o)：判斷列表中是否包含元素判斷列表中是否包含元素o。Object get(int index)：獲取列表中獲取列表中index位置的元素。位置的元素。int indexOf(Obje

8、ct o)：獲取元素獲取元素o在列表中的位置。在列表中的位置。boolean isEmpty()：列表是否為空。列表是否為空。int lastIndexOf(Object o)：獲取列表中最后一個(gè)獲取列表中最后一個(gè)o出現(xiàn)的位置。出現(xiàn)的位置。ListIterator listIterator()：獲取一個(gè)枚舉器。獲取一個(gè)枚舉器。Object remove(int index)：去除位置去除位置index的元素。的元素。boolean remove(Object o)：去除列表中第一個(gè)出現(xiàn)的去除列表中第一個(gè)出現(xiàn)的o元素。元素。Object set(int index, Object element

9、)：用用element取代位置取代位置index的元素。的元素。int size()：返回列表中元素個(gè)數(shù)。返回列表中元素個(gè)數(shù)。List subList(int fromIndex, int toIndex)：得到一個(gè)子范圍。得到一個(gè)子范圍。Object toArray()：將列表轉(zhuǎn)化為一個(gè)數(shù)組。將列表轉(zhuǎn)化為一個(gè)數(shù)組。趙志崑SetSet集合集合Set描述一個(gè)數(shù)學(xué)概念上的集合，集合中元素不能重復(fù)，沒有先后順序之分。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)：判斷兩個(gè)集合是否相等。判斷兩個(gè)集合是否相等。boolean isEmpty()：判斷集合是否為空。判斷集合是否為空。Iterator iterator()：返回一個(gè)枚舉器。返回一個(gè)枚舉器。boolea

11、n remove(Object o)：從集合中刪除元素從集合中刪除元素o。int size()：返回集合元素個(gè)數(shù)。返回集合元素個(gè)數(shù)。Object toArray()：將集合轉(zhuǎn)化為一個(gè)數(shù)組。將集合轉(zhuǎn)化為一個(gè)數(shù)組。趙志崑列表與集合功能之比較列表與集合功能之比較 列表中元素有位置的概念，集合中元素沒有。 列表中可以含有重復(fù)元素，集合中不能。列表列表-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描述一個(gè)自動(dòng)排序的集合，除了Set中的功能外，還能夠自動(dòng)為集合中的元素排序。public interface SortedSet extends Set Object first()：返回第一個(gè)元素。返回第一個(gè)元素。Object last()：

14、返回最后一個(gè)元素。返回最后一個(gè)元素。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()：下一個(gè)元素。下一個(gè)元素。void remove()：從集合中刪除剛枚舉過的元素從集合中刪除剛枚舉過的元素ListIterator用于枚舉列表中的所有元素。public interface ListIterator extends Iterator void add(Object o)：在當(dāng)前位置插入一個(gè)元素。在當(dāng)前位置插入一個(gè)元素。boolean hasNext()：正向是否還有其他元素。正向是否還有其他元素。boolean hasPrevious()：反向是否還有其他

16、元素反向是否還有其他元素Object next()：下一個(gè)元素。下一個(gè)元素。int nextIndex()：返回下一個(gè)元素的位置。返回下一個(gè)元素的位置。Object previous()：上一個(gè)元素上一個(gè)元素int previousIndex()：返回上一個(gè)元素的位置。返回上一個(gè)元素的位置。void remove()：刪除剛剛訪問過的元素。刪除剛剛訪問過的元素。void set(Object o)：用用o覆蓋剛剛訪問過的元素。覆蓋剛剛訪問過的元素。IteratorListIterator趙志崑集合框架中的舊類集合框架中的舊類 集合框架是從Java2開始才有的，但之前已有一些“舊類”，這些類現(xiàn)在

17、也被納入集合框架中。AbstractListListVectorStackRandomAccessHashtableMapProperties容器類堆棧類趙志崑集合框架中的新類集合框架中的新類 Java2新加入的類。HashMapMapAbstractMapTreeMapSortedMapAbstractCollectionListAbstractListLinkedListRandomAccessSetAbstractSequentialListListArrayListAbstractSetHashSetTreeSetCollection兩個(gè)列表類兩個(gè)集合類趙志崑LinkedListLin

18、kedList鏈?zhǔn)搅斜礞準(zhǔn)搅斜?LinkedList是用雙向循環(huán)鏈表來實(shí)現(xiàn)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數(shù)組列表數(shù)組列表 ArrayList是一個(gè)用數(shù)組來實(shí)現(xiàn)列表功能的類。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(容器)的實(shí)現(xiàn)機(jī)制與ArrayList相同，區(qū)別在于：Vector支持多線程同步讀寫，ArrayList不支持。Vector的效率比ArrayList低。趙志崑列表舉例列表舉例創(chuàng)建一個(gè)鏈?zhǔn)搅斜?，保存整?shù)對象0-9，然后輸出可以轉(zhuǎn)化為數(shù)組輸出；可以用枚舉器輸出；將上述功能改為用數(shù)組列表實(shí)現(xiàn)；應(yīng)用多態(tài)見見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()+ ;用數(shù)組列表實(shí)現(xiàn)（用數(shù)組列表實(shí)現(xiàn)（Test1_2.java）ArrayLi

24、st l = new ArrayList();應(yīng)用多態(tài)應(yīng)用多態(tài)List l = new ArrayList();用用Vector(容器容器)實(shí)現(xiàn)實(shí)現(xiàn)List l = new Vector();轉(zhuǎn)化為數(shù)組轉(zhuǎn)化為數(shù)組Object pl = l.toArray();趙志崑列表中元素的類型列表中元素的類型 列表中可以放不同類型的對象 由于多態(tài)性和單根繼承，列表中使用的Object類型的引用可以指向任何對象。見Test1_3.java 可以為列表中元素設(shè)置類型檢查 在聲明列表引用、列表對象和枚舉器對象時(shí)，可以設(shè)置對列表中元素的類型檢查。見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是用散列表實(shí)現(xiàn)集合功能的類。散列(O(C)能夠解決鏈表和數(shù)組中的無序數(shù)據(jù)查找問題(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是用平衡二叉樹實(shí)現(xiàn)有序集合功能的類。樹集是個(gè)有序集合，其插入操

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; .平衡二叉樹：左子樹中元素都比本節(jié)點(diǎn)小，右子樹中元素都比本節(jié)點(diǎn)大。左右子樹長度之差不超過。樹的層數(shù)Log2n+1趙志崑集合舉例集合舉例創(chuàng)建一個(gè)散列集，保存整數(shù)對象0-9，然后用枚舉器輸出；將上述功能改為用樹集實(shí)現(xiàn)；將添加對象的順序改變，輸出結(jié)果

31、不變。應(yīng)用多態(tài)；添加類型檢查見見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、較舉例列表與集合比較舉例 列表中元素有位置的概念，集合中元素沒有。 列表中可以含有重復(fù)元素，集合中不能。對對Test1_1.java改進(jìn)改進(jìn)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改進(jìn)改進(jìn)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趙志崑用列表改進(jìn)用列表改進(jìn)SelectorSelector 用列表改進(jìn)Selector。見Selector1.java。 可以添加類型檢查。見Selector2.java。見見Selector1.java(用數(shù)組列表實(shí)現(xiàn)用數(shù)組列表實(shí)現(xiàn))將學(xué)生信息保存在列表中：List students = new A

35、rrayList();讀入信息時(shí)用add方法將信息添加到列表中：students.add(student);學(xué)生數(shù)量用size()方法獲得：int j = rand.nextInt(students.size();選出學(xué)生用get()方法，注意要造型：Student selectedOne = (Student)(students.get(j);將選出的學(xué)生從列表中刪除用remove()方法：students.remove(j);改為用鏈?zhǔn)搅斜韺?shí)現(xiàn)，改為用鏈?zhǔn)搅斜韺?shí)現(xiàn)，只需改為：List students = new LinkedList();趙志崑簡單常用算法簡單常用算法Collection

36、s類提供了一系列靜態(tài)方法，可以實(shí)現(xiàn)簡單常用算法。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)循環(huán)移動(dòng)循環(huán)移動(dòng)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);循環(huán)移動(dòng)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類型的對象可以按照數(shù)值大小排序，一般對象如何排序？如Student對象。 試驗(yàn)：Test5.java將Collections的sort方法應(yīng)用于Student對象。 造成的原因：察看Collections.sort方法的幫助文檔，得知sort應(yīng)用的對象必須實(shí)現(xiàn)Comparable接口。 解決方法： 為Student類實(shí)現(xiàn)Comparable接口。 實(shí)現(xiàn)了Comparable接口的對象兩兩之間可以比較大小。實(shí)現(xiàn)實(shí)現(xiàn)Comparable接口接口class Student implements Comparable public int compareTo(Object o) Student other = (Student)o; return( pareTo(oth