【文章內(nèi)容簡介】 == x) return i。 return 1。 } – 二分查找。在 0到 n1中間選一個正整數(shù) k，用 k把原來的有序序列分為三個有序子序列： ? a[0]， a[1]， … ， a[k1] ? a[k] ? a[k+1]， a[k+2]， … ， a[n1] 對象數(shù)組 34 ? 具有排序數(shù)組的類 SortedIntArray – search方法運用二分查找算法：在給定的數(shù)組范圍內(nèi)查找某一元素，如果存在，返回元素所在的下標(biāo)位置，如果不存在，則返回元素應(yīng)該在的位置（如果要將此元素插入到數(shù)組中，且保持?jǐn)?shù)組仍然有序的位置） – 將此功能與插入功能相結(jié)合，可實現(xiàn)對數(shù)組元素進行排序 public class SortedIntArray { private int capacity。 private Integer [ ] rep。 private int size。 public SortedIntArray(int n){ capacity = n。 rep = new Integer[capacity]。 } 在已排序的數(shù)組中查找 (續(xù) ) —— 例 7_4 對象數(shù)組 35 public SortedIntArray( ) { this(100)。 } private int search(int i, int lower, int upper) { int index = lower。 if (upper = lower) { int middle = (upper + lower) / 2。 int current = rep[middle].intValue( )。 if (current == i) { index = middle。 } else if (current i) { index = search(i, middle + 1, upper)。 } else { index = search(i, lower, middle 1)。 } } return index。 } 在已排序的數(shù)組中查找 (續(xù) ) —— 例 7_4 對象數(shù)組 36 public int search(int i) { return search(i, 0, size 1)。 } public SortedIntArray insert(int i){ Int index = search(i)。 for(int j = size。 j index。 j) { rep[j] = rep[j 1]。 } rep[index] = new Integer(i)。 ++size。 return this。 } public SortedIntArray remove(int i){ int index = search(i)。 if (rep[index].intValue( ) == i){ size。 for (int j = index。 j size。 ++j){ rep[j] = rep[j + 1]。} } return this。 } 在已排序的數(shù)組中查找 (續(xù) ) —— 例 7_4 對象數(shù)組 37 public String toString( ){ String toReturn = 。 for (int i = 0。 i size。 ++i){ toReturn += rep[i].toString( ) + , 。 } return toReturn。 } static public void main(String [ ] args){ SortedIntArray anArray = new SortedIntArray( )。 (4).insert(9).insert(7).insert(1).insert(3). insert(2).insert(8).insert(7)。 (anArray)。 (1).remove(8).remove(7).remove(3)。 (anArray)。 } } 在已排序的數(shù)組中查找 (續(xù) ) —— 例 7_4 對象數(shù)組 38 ? 運行結(jié)果 1, 2, 3, 4, 7, 7, 8, 9, 2, 4, 7, 9, 在已排序的數(shù)組中查找 (續(xù) ) —— 例 7_4運行結(jié)果 對象數(shù)組 39 集合 ? 數(shù)組的優(yōu)點 – 是 Java提供的隨機訪問對象序列的最有效方法 – 是一個簡單的線性序列，訪問元素的速度較快 ? 數(shù)組的缺點 – 大小自創(chuàng)建以后就固定了，在其整個生存期內(nèi)其大小不可改變 – 數(shù)組元素只能是同一類型 ? 集合 – 可動態(tài)改變其大小 – 可在序列中存儲不同類型的數(shù)據(jù) 40 ? 集合 – 把具有相同性質(zhì)的一類東西，匯聚成一個整體 – 在 Java2中有很多與集合有關(guān)的接口及類 – 它們被組織在以 Collection及 Map接口為根的層次結(jié)構(gòu)中，稱為 集合框架 – 在 Java2之前，在 Java ，沒有完整的集合框架。只有一些簡單的可以自擴展的容器類 ? Vector ? Hashtable 集合 (續(xù) ) 集 合 41 Java集合框架 ? 集合框架 (Java Collections Framework) – 為表示和操作集合而規(guī)定的一種統(tǒng)一的標(biāo)準(zhǔn)的體系結(jié)構(gòu) – 提供了一些現(xiàn)成的數(shù)據(jù)結(jié)構(gòu)可供使用，程序員可以利用集合框架快速編寫代碼，并獲得優(yōu)良性能 – 包含三大塊內(nèi)容 ? 對外的接口：表示集合的抽象數(shù)據(jù)類型，使集合的操作與表示分開 ? 接口的實現(xiàn)：指實現(xiàn)集合接口的 Java類，是可重用的數(shù)據(jù)結(jié)構(gòu) ? 對集合運算的算法：是指執(zhí)行運算的方法，例如在集合上進行查找和排序 集 合 42 ? 集合框架接口 – 聲明了對各種集合類型執(zhí)行的一般操作 – 包括 Collection、 Set、 List、 SortedSet、 Map、 SortedMap – 基本結(jié)構(gòu)如圖 Java集合框架 (續(xù) ) —— 對外的接口 集 合 43 ? 類層次如圖，包括 4個接口、 4個抽象類及 6個具體類 Java集合框架 (續(xù) ) —— Collection接口 Collection AbstractCollection Vector ArrayList Stack List Set SortedSet AbstractSet AbstractList AbstractSequentialList HashSet TreeSet LinkedList 集 合 44 ? Collection接口 – 聲明了一組操作成批對象的抽象方法：查詢方法、修改方法 – 查詢方法 ? int size() – 返回集合對象中包含的元素個數(shù) ? boolean isEmpty() – 判斷集合對象中是否還包含元素，如果沒有任何元素，則返回 true ? boolean contains(Object obj) – 判斷對象是否在集合中 ? boolean containsAll(Collection c) – 判斷方法的接收者對象是否包含集合中的所有元素 Java集合框架 (續(xù) ) —— Collection接口 集 合 45 – 修改方法包括 ? boolean add(Object obj) – 向集合中增加對象 ? boolean addAll(Collection c) – 將參數(shù)集合中的所有元素增加到接收者集合中 ? boolean remove(Object obj) –從集合中刪除對象 ? boolean removeAll(Collection c) 將參數(shù)集合中的所有元素從接收者集合中刪除 ? boolean retainAll(Collection c) – 在接收者集合中保留參數(shù)集合中的所有元素，其它元素都刪除 ? void clear() – 刪除集合中的所有元素 Java集合框架 (續(xù) ) —— Collection接口 集 合 46 ? Set接口 – 擴展了 Collection – 禁止重復(fù)的元素 ，是數(shù)學(xué)中“集合”的抽象 – 對 equals和 hashCode操作有了更強的約定，如果兩個Set對象包含同樣的元素，二者便是相等的 – 實現(xiàn)它的兩個主要類是哈希集合 (HashSet)及樹集合(TreeSet) ? SortedSet接口 – 一種特殊的 Set – 其中的元素是升序排列的，還增加了與次序相關(guān)的操作 – 通常用于存放詞匯表這樣的內(nèi)容 Java集合框架 (續(xù) ) —— Set、 SortedSet接口 集 合 47 ? List接口 – 擴展了 Collection – 可包含重復(fù)元素 – 元素是有順序的，每個元素都有一個 index值（從 0開始）標(biāo)明元素在列表中的位置 – 實現(xiàn)它的四個主要類是 ? Vector ? ArrayList：一種類似數(shù)組的形式進行存儲，因此它的隨機訪問速度極快 ? LinkedList：內(nèi)部實現(xiàn)是鏈表，適合于在鏈表中間需要頻繁進行插入和刪除操作 ? 棧 Stack Java集合框架 (續(xù) ) —— List接口 集 合 48 ? Map接口 – 不是 Collection接口的繼承 – 用于維護鍵 /值對 (key/value pairs) – 描述了從不重復(fù)的鍵到值的映射，是一個從關(guān)鍵字到值的映射對象 – 其中不能有重復(fù)的關(guān)鍵字，每個關(guān)鍵字最多能夠映射到一個值 ? SortedMap接口 – 一種特殊的 Map，其中的關(guān)鍵字是升序排列的 – 與 SortedSet對等的 Map，通常用于詞典和電話目錄等 Java集合框架 (續(xù) ) —— Map、 SortedMap接口 集 合 49 ? 接口的實現(xiàn) – Collection沒有直接的實現(xiàn)，只是作為其他集合接口的最小公分母 – 除 Collection 以外，其余五個接口都有實現(xiàn) – 主要的實現(xiàn)有 ? Set?HashSet ? SortedSet?TreeSet ? List?Vector / ArrayList / LinkedList ? Map?HashMap ? SortedMap?TreeMap Java集合框架 (續(xù) ) —— 接口的實現(xiàn) 集 合 50 ? 對集合運算的算法 – 大多數(shù)算法都是用于操作 List對象 – 有兩個 (min和 max)可用于任意集合對象 ? 排序算法 sort – 對 List重新排序，使其中的元素按照某種次序關(guān)系升序排列 – 有兩種形式 ? 簡單形式只是將元素按照自然次序排列 ? 第二種形式需要一個附加的 Comparator對象作為參數(shù)，用于規(guī)定比較規(guī)則，可用于實現(xiàn)反序或特殊次序排序 Java集合框架 (續(xù) ) —— 對集合運算的算法 集 合 51 ? 洗牌算法 shuffle – 其作用與排序算法恰好相反，它打亂 List中的任何次序。也就是說以隨機方式重排元素，任何次序出現(xiàn)的幾率都是相等的 – 在實現(xiàn)偶然性游戲的時候，這個算法很有用，例如洗牌 ? 常規(guī)數(shù)據(jù)處理算法 – reverse:：將一個 List中的元素反向排列 – fill：用指定的值覆寫 List中的每一個元素，這個操作在重新初始化 List時有用 – copy:：接受兩個參數(shù)，目標(biāo) List和源 List，將源中的元素復(fù)制到目標(biāo)，覆寫其中的內(nèi)容。目標(biāo) List必須至少與源一樣長，如果更長，則多余的部分內(nèi)容不受影響 Java集合框架 (續(xù) ) —— 對集合運算的算法 集 合 52