數(shù)據(jù)結(jié)構(gòu).PPT

常見數(shù)據(jù)結(jié)構(gòu)的Java實現(xiàn),常見數(shù)據(jù)結(jié)構(gòu),鏈表 散列集 向量 棧 樹集,鏈表,如果需要處理一些類型相同的數(shù)據(jù),人們習慣上使用數(shù)組這種數(shù)據(jù)結(jié)構(gòu),但數(shù)組在使用之前必須定義大小,而且不能動態(tài)定義大小.有時可能給數(shù)組分配了太多的單元而浪費了寶貴的內(nèi)存資源,糟糕的一方面是,程序運行時需要處理的數(shù)據(jù)可能多于數(shù)組的單元.當需要動態(tài)地減少或增加數(shù)據(jù)項時,可以使用鏈表這種數(shù)據(jù)結(jié)構(gòu)。 鏈表是由若干個稱作節(jié)點的對象組成的一種數(shù)據(jù)結(jié)構(gòu),每個節(jié)點含有一個數(shù)據(jù)和下一個節(jié)點對象的引用(單鏈表 ),或含有一個數(shù)據(jù)并含有上一個節(jié)點對象的引用和下一個節(jié)點對象的引用(雙鏈表) 。,創(chuàng)建鏈表,使用java.util 包中的LinkedList類創(chuàng)建一個鏈表.例如, LinkedList mylist=new LinkedList(); 創(chuàng)建了一個空鏈表.然后mylist鏈表可以使用add()方法向這個鏈表依次增加節(jié)點.例如 mylist.add(“It”);mylist.add(“is”); mylist.add(“a”);mylist.add(“door”); mylist可以使用方法 public Object get(index i)獲取第i個節(jié)點中存儲的數(shù)據(jù). 存放在節(jié)點中的數(shù)據(jù)都被看作是一個Object 對象.,import java.util.*; public class LinkListOne public static void main(String args) LinkedList mylist=new LinkedList(); mylist.add(“It“); /鏈表中的第一個節(jié)點. mylist.add(“is“); /鏈表中的第二個節(jié)點. mylist.add(“a“); /鏈表中的第三個節(jié)點. mylist.add(“door“); /鏈表中的第四個節(jié)點. int number=mylist.size(); /獲取鏈表的長度. for(int i=0;inumber;i+) String temp=(String)mylist.get(i); System.out.println(“第“+i+“節(jié)點中的數(shù)據(jù):“+temp); ,注:由于任何類都是Object 類的子類,因此可以把任何一個對象作為鏈表的節(jié)點對象.需要注意的是當使用get()獲取一個節(jié)點對象后,要用類型轉(zhuǎn)換運算符轉(zhuǎn)化回原來的類型.,2、LinkedList類中的常用方法 public boolean add(Object element) 向鏈表的末尾填加一個新的節(jié)點對象elememt. public void add(int index ,Object element) 向鏈表的指定位置尾填加一個新的節(jié)點對象elememt. public void addFirst(Object element) 把節(jié)點對象 elememt 填加到鏈表的表頭. public void addLast(Object element) 把節(jié)點對象elememt 填加到鏈表的末尾. public void clear() 刪除鏈表的所有節(jié)點對象. public Obiect remove(int index) 刪除指定位置上的節(jié)點對象. public boolean remove(Object element) 將首次出現(xiàn)的節(jié)點對象elemen刪除. public Obiect removeFirst() 刪除第一個節(jié)點對象,并返回這個節(jié)點對象.,public Obiect removeLast() 刪除最后一個節(jié)點對象. public Object get(int index) 得到鏈表中指定位置處的節(jié)點對象. public Object getFirst() 得到鏈表中第一個節(jié)點對象. public Object getLast() 得到鏈表中最后一個節(jié)點對象. public int indexOf(Object element) 返回節(jié)點對象element 在鏈表 中首次出現(xiàn)的位置,如果鏈表中無此節(jié) 點對象則返回-1. public int lastIndexOf(Object element) 返回節(jié)點對象element 在 鏈表中最后出現(xiàn)的位置,如果鏈表中無此節(jié) 點對象則返回-1. public Object set(int index ,Object element) 用節(jié)點對象element 替換鏈表中指定位置處的節(jié)點對象.并返回被替換的對象。 public int size() 返回鏈表的長度,即節(jié)點的個數(shù). public boolean contains(Object element) 判斷鏈表節(jié)點對象中是 否含有element.,看下面的例子 ExampleList.java,使用Iterator類遍歷鏈表,前面的例子借助get方法實現(xiàn)了遍歷鏈表。也可以借助Iterator對象實現(xiàn)遍歷鏈表，一個鏈表對象可以使用iterator()方法獲取一個Iterator對象，Iterator對象中每個數(shù)據(jù)成員剛好是鏈表結(jié)點中的數(shù)據(jù)，而且這些數(shù)據(jù)成員是按順序存放在Iterator對象中的。Iterator對象使用next()方法可以得到其中的數(shù)據(jù)成員。顯然使用Iterator要比get方法遍歷的速度快。,3、使用Iterator類遍歷鏈表 (迭代器) 在上面的例子中我們借助get 方法實現(xiàn)了遍歷鏈表. 我們可以借助Iterator 對象實現(xiàn)遍歷鏈表,一個鏈表對象可以使用iterator()方法獲取一個Iterator 對象,后者使用next()方法遍歷鏈表.在下面的例子 中,我們把學生的成績存放在一個鏈表中,并實現(xiàn)了遍歷鏈表. 例子：ExampleList2.java,ArrayList和LinkedList在性能上各有優(yōu)缺點，都有各自所適用的地方，總的說來可以描述如下： 1. 對ArrayList和LinkedList而言，在列表末尾增加一個元素所花的開銷都是固定的。對ArrayList而言，主要是在內(nèi)部數(shù)組中增加一 項，指向所添加的元素，偶爾可能會導致對數(shù)組重新進行分配；而對LinkedList而言，這個開銷是統(tǒng)一的，分配一個內(nèi)部Entry對象。 2.在ArrayList的中間插入或刪除一個元素意味著這個列表中剩余的元素都會被移動；而在LinkedList的中間插入或刪除一個元素的開銷是固定的。 3.LinkedList不支持高效的隨機元素訪問。 4.ArrayList的空間浪費主要體現(xiàn)在在list列表的結(jié)尾預(yù)留一定的容量空間，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗相當?shù)目臻g可以這樣說：當操作是在一列數(shù)據(jù)的后面添加數(shù)據(jù)而不是在前面或中間，并且需要隨機地訪問其中的元素時，使用ArrayList會提供比較好的性能；當你的操作是在一列數(shù)據(jù)的前面或中間添加或刪除數(shù)據(jù)，并且按照順序訪問其中的元素時，就應(yīng)該使用LinkedList了,散列表,散列表是使用相關(guān)關(guān)鍵字查找被存儲的數(shù)據(jù)項的一種數(shù)據(jù)結(jié)構(gòu),關(guān)鍵字不可以發(fā)生邏輯沖突,即不要兩個數(shù)據(jù)項使用相同的關(guān)鍵字,如果出現(xiàn)兩個數(shù)據(jù)項對應(yīng)相同的關(guān)鍵字,那么,先前散列表中的數(shù)據(jù)項將被替換.散列表在它需要更多的存儲空間時會自動增大容量. 例如,如果散列表的裝載因子是0.75,那么當散列表的容量被使用了75%時,它就把容量增加到原始容量的2倍. 對于數(shù)組和鏈表這兩種數(shù)據(jù)結(jié)構(gòu),如果要查找它們存儲的某個特定的元素卻不知道它的位置,就需要從頭開始訪問元素直到找到匹配的為止；如果數(shù)據(jù)結(jié)構(gòu)中包含很多的元素,就會浪費時間.這時最好使用散列表來存儲要查找的數(shù)據(jù).,使用java.util包中的Hashtable類來創(chuàng)建散列表對象,該類的常用方法如下 public Hashtable() 創(chuàng)建具有默認容量和裝載因子為0.75 的散列表. public Hashtable (int itialCapacity) 創(chuàng)建具有指定容量和裝載因子為0.75的散列表. public Hashtable(int initialCapacity,float loadFactor) 創(chuàng)建具有默認容量和指定裝載因子散列表. public void clear() 清空散列表. public boolean contains(Object o) 判斷散列表是否有含有元素o. public Object get(Object key) 獲取散列表中具有關(guān)鍵字key的數(shù)據(jù)項. public boolean isEmpty() 判斷散列表是否為空.,public Object put(Object key ,Object value) 向散列表添加數(shù)據(jù)項value并把關(guān)鍵字key關(guān)聯(lián)到數(shù)據(jù)項value. public Object remove(Object key) 刪除關(guān)鍵字是key 的數(shù)據(jù)項. public int size() 獲取散列表中關(guān)鍵字的數(shù)目. public Enumeration keys() 返回散列表所用的關(guān)鍵字的一個枚舉對象. 使用上述的get 方法可以從散列表中檢索某個數(shù)據(jù).我們還可以借助Enumeration 對象實現(xiàn)遍歷散列表,一個散列表可以使用elements()方法獲取一個Enumeration 對象,后者使用nextElement()方法遍歷散列表.,Vector 向量,Java的 java.util包中的Vector類負責創(chuàng)建一個向量對象.如果你已經(jīng)學會使用數(shù)組,那么很容易就會使用向量.當我們創(chuàng)建一個向量時不用象數(shù)組那樣必須要給出數(shù)組的大小.向量創(chuàng)建后,例如,Vector a=new Vector(),a可以使用add(Object o)把任何對象添加到向量的末尾,向量的大小會自動的增加.可以使用add(int index ,Object o)把一個對象追加到該向量的指定位置. 向量a可以使用elementAt(int index )獲取指定索引處的向量的元素（索引初始位置是0）a可以使用方法size()獲取向量所含有的元素的個數(shù).另外,與數(shù)組不同的是向量的元素類型不要求一致.需要注意的是,當你把某一種類型的對象放入一個向量后,數(shù)據(jù)被默認為是Object 對象,因此當向量中取出一個元素時應(yīng)用強制類型轉(zhuǎn)化運算符轉(zhuǎn)化為原來的類型.,Vector類的常用方法 public void add(Object o) 將對象o添加到向量的末尾. public void add(int index Object o)將對象o插入到向量的指定位置. public void addElements(Object o)將對象o添加到向量的末尾. public boolean contains(Object o)判斷對象o是否為向量的成員. public Object elementAt(int index)獲取指定位置處的成員. public Object get(int index)獲取此向量指定位置處的成員. public Object firstElement()獲取此向量的第一個成員. public Object lastElement()獲取此向量的最后一個成員.,public int indexOf(Obkect o) 獲取對象o在此向量中首次出現(xiàn)的位置. public int indexOf(Obkect o,int index) 從指定位置查找對象o 在此向量中首次現(xiàn)的位置. public int lastIndexOf(Object o) 獲取對象o在此向量中最后出現(xiàn)的位置. public int lastIndexOf(Object o,int index) 對象o在此向量位置index之前最后出現(xiàn)的位置. public Object remove(int index) 從此向量中刪除指定位置處的成員,并返回這個成員. public void removeAllElements() 刪除向量的所有成員. public boolean removeElement(Object o) 刪除第一次出現(xiàn)的成員o.,public boolean removeElementAt(int index) 刪除指定位置處的成員. public void set(int index,Object o) 把指定位置處的成員用o替換掉. public void setElementAt(Object o,int index)把指定位置處的成員用o替換掉. public Enumeration elements()獲取一個枚舉對象.,棧,棧是一種”后進先出”的數(shù)據(jù)結(jié)構(gòu),只能在一端進行輸入或輸出數(shù)據(jù)的操作.堆棧把第一個放入該堆棧的數(shù)據(jù)放在最底下,而把后續(xù)放入的數(shù)據(jù)放在已有數(shù)據(jù)的頂上,如圖所示.,使用java.util包中的Stack類創(chuàng)建一個棧對象 public Object push(Object data); 輸入數(shù)據(jù),實現(xiàn)壓棧操作 public Object pop(); 輸出數(shù)據(jù),實現(xiàn)彈棧操作 public Object peek(); 查看棧頂端的數(shù)據(jù),但不刪除該數(shù)據(jù) public boolean empty(); 判斷棧是否還有數(shù)據(jù),有數(shù)據(jù)返回false ,否則返回true public int search(Object data); 獲取數(shù)據(jù)在棧中的位置,最頂端的位置是1，向下依次增加，如果棧不含此數(shù)據(jù)，返回-1。,樹集,樹集是有一些節(jié)點對象組成的數(shù)據(jù)結(jié)構(gòu),節(jié)點按著樹形一層一層的排列,如下圖所示.,1.用構(gòu)造方法TreeSet()創(chuàng)建一個樹集 可以使用java.util包中的TreeSet來創(chuàng)建一個樹集,如 TreeSet mytree=new TreeSet(); 然后使用add方法為樹集添加節(jié)點 mytree.add(“boy“); mytree.add(“zoo“); mytree.add(“apple“); mytree.add(“girl“); 和鏈表不同的是,當使用構(gòu)造方法TreeSet()創(chuàng)建樹集后,再用add 方法增加節(jié)點時,節(jié)點會按其存放的數(shù)據(jù)的字典序一層一層地依次排列,在同一層中的節(jié)點從左到右按字典序遞增排列,下一層的都比上一層的小.mytree的示意圖如下圖.,兩個字符串對象s1,s2可以使用 pare(s2); 按字典序比較大小,即pare(s2) =0時二者相同,pare(s2) 0時,稱s1 大于 s2，pare(s2) 0時,稱s1 小于s2.,2.用構(gòu)造方法TreeSet(Comparator c)創(chuàng)建一個樹集 但很多對象不適合用字典序進行比較,這時我們在創(chuàng)建樹集時可自己規(guī)定節(jié)點按著什么樣的”大小”順序排列.假如我們有四個學生對象,他們有姓名和成績,我們想把這四個對象做為一個樹集的節(jié)點,并按著成績的高低排列節(jié)點,而不是按著姓名的字典序排列節(jié)點. 首先創(chuàng)建學生的Student類必須實現(xiàn)接口 Comparable.Comparable 接口中有一個方法 public int compareTo(Object b) Student類通過實現(xiàn)這個接口來規(guī)定它創(chuàng)建的對象的大小關(guān)系,如下所示.,Java規(guī)定 當 pareTo(b) 時,稱二者相等 pare(s2)0 時,稱a大于b pare(s2)0 時,稱a小于b. 然后用帶Comparator參數(shù)的構(gòu)造方法 TreeSet(Comparator c); 創(chuàng)建一個樹集,通過參數(shù)c規(guī)定樹集的節(jié)點按怎樣的順序排列,如下所示 TreeSet mytree=new TreeSet(new Comparator() public int compare(Object a,Object b) Student stu1=(Student)a; Student stu2=(Student)b; return