【正文】 ? A、鏈表 B、隊(duì)列 ? C、棧 D、關(guān)聯(lián)數(shù)組 ? 使用堆棧結(jié)構(gòu)輸出的若干項(xiàng)，其中 =2+2，=3， =8。 ? 注意：當(dāng)你把某一種類型的對(duì)象放入一個(gè)向量后，數(shù)據(jù)被默認(rèn)為是 Object對(duì)象，因此當(dāng)向量中取出一個(gè)元素時(shí)應(yīng)用強(qiáng)制類型轉(zhuǎn)化運(yùn)算符轉(zhuǎn)化為原來(lái)的類型。與數(shù)組一樣，它包含可以使用整數(shù)索引進(jìn)行訪問(wèn)的組件。 向量 ? Java的 Vector 類負(fù)責(zé)創(chuàng)建一個(gè)向量對(duì)象，可以實(shí)現(xiàn)可增長(zhǎng)的對(duì)象數(shù)組。 HashSet和 TreeSet的比較： ? HashSet是基于 Hash算法實(shí)現(xiàn)的，其性能通常都優(yōu)于 TreeSet。 ? 只有在不在乎集合中的各個(gè)元素的順序時(shí)，才能使用散列集。 ? Java的集合庫(kù)提供了一個(gè) HashSet類，用于根據(jù)散列表來(lái)實(shí)現(xiàn)一個(gè)散列集；構(gòu)造函數(shù)如下： ? HashSet(int initialCapacity)。如果大致知道散列表最終會(huì)擁有多少個(gè)元素，那么應(yīng)該將初始散列表元的數(shù)量設(shè)置為大約是預(yù)期元素?cái)?shù)量的 150%，最好是將散列表的大小設(shè)置成一個(gè)素?cái)?shù)。 Hashtable類的應(yīng)用 ? 在下面的例子中，使用 Hashtable()創(chuàng)建一個(gè)散列表，存放 Student對(duì)象，每個(gè) Student對(duì)象用該對(duì)象的學(xué)號(hào)作為關(guān)鍵字。 ? public int size()：獲取散列表中關(guān)鍵字的數(shù)目。 ? public Object put(Object key,Object value)：向散列表添加數(shù)據(jù)項(xiàng) value并把關(guān)鍵字 key關(guān)聯(lián)到數(shù)據(jù)項(xiàng) value。 ? public Object get(Object key)：獲取散列表中具有關(guān)鍵字 key的數(shù)據(jù)項(xiàng)。 ? public void clear()：清空散列表。 ? public Hashtable(int itialCapacity)：創(chuàng)建具有指定容量和裝載因子為 的散列表。 ? if (n != null) { ? (two = + n)。 ? (three, new Integer(3))。 ? (one, new Integer(1))。 下面這個(gè)示例 1213創(chuàng)建了一個(gè)數(shù)字的哈希表。例如，如果散列表的裝載因子是 ，那么當(dāng)散列表的容量被使用了 75%時(shí)，它就把容量增加到原始容量的２倍。散列表是使用相關(guān)關(guān)鍵字查找被存儲(chǔ)的數(shù)據(jù)項(xiàng)的一種數(shù)據(jù)結(jié)構(gòu)，關(guān)鍵字必須唯一，任何非 null 對(duì)象都可以用作鍵或值。 ? (姓名 + + 英語(yǔ) + )。 ? iter = ()。 ? (樹(shù)映射中有 + number + 個(gè)對(duì)象 :按英語(yǔ)成績(jī)排序 :)。 k++) { ? (key[k], student[k])。 ? } ? for (int k = 0。 k 。 ? } ? ()。 ? while (()) { ? Student1 stu = (Student1) ()。 ? Collection collection = ()。 ? } ? int number = ()。 k 。 k++) { ? key[k] = new StudentKey(student[k].math)。 ? for (int k = 0。 k++) { ? student[k] = new Student1(str[k], math[k], english[k])。 ? for (int k = 0。 ? double english[] = { 67, 66, 90, 56 }。 ? String str[] = { 趙一 , 錢二 , 孫三 , 李四 }。 ? return (key2)。 ? } ? } ? public class ep12_12 { ? public static void main(String args[]) { ? TreeMap treemap = new TreeMap(new Comparator() { ? public int pare(Object a, Object b) { ? StudentKey key1 = (StudentKey) a。 ? math = m。 ? double math, english。 ? } else { ? return (int) (( ) * 1000)。 ? } ? public int pareTo(Object b) { ? StudentKey st = (StudentKey) b。 ? class StudentKey implements Comparable { ? double d = 0。 【 例 1212】 本例使用了 TreeMap，分別按學(xué)生的英語(yǔ)成績(jī)和數(shù)學(xué)成績(jī)排序結(jié)點(diǎn)。TreeMap類的常用構(gòu)造方法如下： ? TreeMap()：構(gòu)造一個(gè)新的空映射，該映射按照鍵的自然順序排序。 ? 方法添加結(jié)點(diǎn)，該結(jié)點(diǎn)不僅存儲(chǔ)數(shù)據(jù) value，而且也存儲(chǔ)和其關(guān)聯(lián)的關(guān)鍵字 key，也就是說(shuō)，樹(shù)映射的結(jié)點(diǎn)存儲(chǔ)“關(guān)鍵字 /值”對(duì)。 TreeMap類實(shí)現(xiàn)了 Map接口，稱TreeMap對(duì)象為樹(shù)映射。 ? public int size()：返回節(jié)點(diǎn)數(shù)目。 ? public isEmpty()：判斷是否是空樹(shù)集，如果樹(shù)集不含節(jié)點(diǎn)返回true 。 ? public Object first()：返回根節(jié)點(diǎn)，即第一個(gè)節(jié)點(diǎn)（最小的節(jié)點(diǎn)）。 ? public void clear()：刪除所有的節(jié)點(diǎn)。 ? 注： Comparator是 ，pare是接口中的方法，因此必須給出方法體。 ? return (stu2)。 ? } ? } 2．用構(gòu)造方法 TreeSet(Comparator c)創(chuàng)建一個(gè)樹(shù)集，通過(guò)參數(shù) c規(guī)定樹(shù)集的節(jié)點(diǎn)按怎樣的順序排列： ? TreeSet mytree=new TreeSet(new Comparator(){ ? public int pare(Object a,Object b){ ? Student stu1=(Student)a。 ? return ( )。 ? name = n。 ? String name。 Java規(guī)定： (b)＝０時(shí)，稱二者相等； (s2)０時(shí)，稱 a大于 b； (s2)０時(shí)，稱 a小于 b。 Comparable接口中有一個(gè)方法： public int pareTo(Object b)。 ? 假如我們有四個(gè)學(xué)生對(duì)象，他們有姓名和成績(jī)，我們想把這四個(gè)對(duì)象做為一個(gè)樹(shù)集的節(jié)點(diǎn)，并按著成績(jī)的高低排列節(jié)點(diǎn)，而不是按著姓名的字典序排列節(jié)點(diǎn)。 ? while (()) ? ( + ())。 ? (girl)。 ? (zoo)。 ? class TreeOne { ? public static void main(String args[]) { ? TreeSet mytree = new TreeSet()。 【 例 128】 本例使用構(gòu)造方法 TreeSet()創(chuàng)建了一個(gè)樹(shù)集，并填加了 4個(gè)節(jié)點(diǎn)。 ? (girl)。 //然后使用 add方法為樹(shù)集添加節(jié)點(diǎn)： ? (zoo)。 TreeSet()創(chuàng)建一個(gè)樹(shù)集 ? 可以使用 TreeSet來(lái)創(chuàng)建一個(gè)樹(shù)集，如 ? TreeSet mytree=new TreeSet()。樹(shù)集是由一些節(jié)點(diǎn)對(duì)象組成的數(shù)據(jù)結(jié)構(gòu)，節(jié)點(diǎn)按著樹(shù)形一層一層的排列。 ? Java集合庫(kù)中提供了 TreeSet類。 ? 用方法 getFirst()實(shí)現(xiàn)棧頂數(shù)據(jù)查詢。 ? 用方法 addFirst(Object element)實(shí)現(xiàn)進(jìn)棧操作。 ? Fibonacii整數(shù)序列是我們熟悉的一個(gè)遞歸序列，它的第 n項(xiàng)是前兩項(xiàng)的和，第一項(xiàng)和第二項(xiàng)是１。 ? } ? } ? } 程序運(yùn)行后的結(jié)果如下所示： ? 堆棧是很靈活的數(shù)據(jù)結(jié)構(gòu)，使用堆?？梢怨?jié)省內(nèi)存的開(kāi)銷。 ? while (!(())) { ? Integer temp = (Integer) ()。 ? (new Integer(5))。 ? (new Integer(3))。 ? (new Integer(1))。 ? import .*。 ? public int search(Object data) //返回對(duì)象在棧中的位置，最頂端的位置是１，向下依次增加，如果堆棧不含此數(shù)據(jù)，則返回 1。 ? 使用 Stack類創(chuàng)建一個(gè)堆棧對(duì)象，堆棧對(duì)象可以使用以下方法： ? public Object push(Object data) //輸入數(shù)據(jù)，實(shí)現(xiàn)壓棧操作 ? public Object pop() //輸出數(shù)據(jù)，實(shí)現(xiàn)彈棧操作 ? public boolean empty() //測(cè)試堆棧是否為空。 棧的物理存儲(chǔ)可以用順序存儲(chǔ)結(jié)構(gòu) ， 也可以用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 。 ? } ? } ? } 程序運(yùn)行后的效果如下所示： 棧 ? 棧 （ Stack） 也是一種特殊的線性表 ， 是限定僅在表尾進(jìn)行插入和刪除運(yùn)算的線性表 ， 是一種后進(jìn)先出 （ LIFO） 的數(shù)據(jù)結(jié)構(gòu) 。 ? while (()) { ? Student te = (Student) ()。 ? (stu_4)。 ? (stu_2)。 ? Student stu_1 = new Student(趙好民 , 9012, ), stu_2 = new Student( ? 錢小青 , 9013, ), stu_3 = new Student(孫力枚 , 9014, ), stu_4 = new Student( ? 周左右 , 9015, )。 ? = score。 ? Student(String name, int number, float score) { ? = name。 ? int number。 ? import .*。在下面的例子 123中，我們把學(xué)生的成績(jī)存放在一個(gè)鏈表中，并實(shí)現(xiàn)了遍歷鏈表。 ? 在例子 121和例子 122中我們借助 get方法實(shí)現(xiàn)了遍歷鏈表。 ? void remove()：從迭代器指向的集合中移除迭代器返回的最后一個(gè)元素。 ? Boolean hasNext()：如果仍有元素可以迭代，則返回 true。很明顯，對(duì)容器對(duì)象的訪問(wèn)必然涉及到遍歷算法。它的定義為：提供一種方法訪問(wèn)一個(gè)容器（ container）對(duì)象中各個(gè)元素，而又不需暴露該對(duì)象的內(nèi)部細(xì)節(jié)。 ? (第 + i + 節(jié)點(diǎn)中的數(shù)據(jù)： + temp)。 i number。 ? (現(xiàn)在鏈表中有 + number + 個(gè)節(jié)點(diǎn)： )。 ? (0, open)。 ? } ? (0)。 i++) { ? String temp = (String) (i)。 ? for (int i = 0。 ? number = ()。 ? number = ()。 ? (第 + i + 節(jié)點(diǎn)中的數(shù)據(jù)： + temp)。 i number。 ? (現(xiàn)在鏈表中有 + number + 個(gè)節(jié)點(diǎn)： )。 ? (a)。 ? public class ep12_2 { ? public static void main(String args[]) { ? LinkedList list = new LinkedList()。 【 例 122】 本例包含了 LinkedList類中的一些常用方法。 ? public int size( ) //返回量表的長(zhǎng)度，即節(jié)點(diǎn)的個(gè)數(shù)。 ? public int lastIndexOf(Object element)：返回節(jié)點(diǎn)對(duì)象 element在鏈表中最后出現(xiàn)的位置，如果鏈表中無(wú)此節(jié)點(diǎn)對(duì)象則返回 1。 ? public Object getLast() //得到鏈表最后一個(gè)節(jié)點(diǎn)的對(duì)象。 ? public Object removeLast() //刪除最后一個(gè)節(jié)點(diǎn)，并返回這個(gè)節(jié)點(diǎn)中的對(duì)象。 ? public void addLast(Object element) //向鏈表尾添加新節(jié)點(diǎn)，該節(jié)點(diǎn)中的數(shù)據(jù)是參數(shù) element指定的對(duì)象。 ? public void add(int index, Object element ) //向鏈表指定位置添加節(jié)點(diǎn)，該節(jié)點(diǎn)中的數(shù)據(jù)是參數(shù) element指定的對(duì)象。 ? (第 +