Java常見數(shù)據(jù)結構實現(xiàn).ppt

1、常見數(shù)據(jù)結構的Java實現(xiàn),我們在編寫程序時經(jīng)常要和各種數(shù)據(jù)打交道,為處理這些數(shù)據(jù)所選的數(shù)據(jù)結構對于我們的程序的運行效率是非常重要的.這章講述幾種常見的數(shù)據(jù)結構的Java 實現(xiàn). 在學習數(shù)據(jù)結構這門課程的時候,人們要用具體的算法去實現(xiàn)相應的數(shù)據(jù)結構,例如,為了實現(xiàn)鏈表這種數(shù)據(jù)結構,需要實現(xiàn)往鏈表中插入節(jié)點或從鏈表中刪除節(jié)點的算法,感覺有些煩瑣. 在jdk1.2 之后,Java 提供了實現(xiàn)常見數(shù)據(jù)結構的類,創(chuàng)建鏈表等數(shù)據(jù)結構和創(chuàng)建數(shù)組一樣簡單,不再需要你去寫具體的算法.我們主要講述這些類的用法,但對這些數(shù)據(jù)結構的原理的掌握對于我們熟練地用好這些類還是很有幫助的.,26.1鏈表,如果需要處理一些類

2、型相同的數(shù)據(jù),人們習慣上使用數(shù)組這種數(shù)據(jù)結構,但數(shù)組在使用之前必須定義大小,而且不能動態(tài)定義大小.有時可能給數(shù)組分配了太多的單元而浪費了寶貴的內存資源,糟糕的一方面是,程序運行時需要處理的數(shù)據(jù)可能多于數(shù)組的單元.當需要動態(tài)地減少或增加數(shù)據(jù)項時,可以使用鏈表這種數(shù)據(jù)結構. 鏈表是由若干個稱作節(jié)點的對象組成的一種數(shù)據(jù)結構,每個節(jié)點含有一個數(shù)據(jù)和下一個節(jié)點對象的引用(單鏈表 ),或含有一個數(shù)據(jù)并含有上一個節(jié)點對象的引用和下一個節(jié)點對象的引用(雙鏈表) .,1 .創(chuàng)建鏈表,使用java.util 包中的LinkedList類創(chuàng)建一個鏈表.例如, LinkedList mylist=new Linked

3、List(); 創(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 my

4、list=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 類的子類,因此可以把任何一個

5、對象作為鏈表的節(jié)點對象.需要注意的是當使用get()獲取一個節(jié)點對象后,要用類型轉換運算符轉化回原來的類型.,linkedlist.java,26.4散列表,散列表是使用相關關鍵字查找被存儲的數(shù)據(jù)項的一種數(shù)據(jù)結構,關鍵字不可以發(fā)生邏輯沖突,即不要兩個數(shù)據(jù)項使用相同的關鍵字,如果出現(xiàn)兩個數(shù)據(jù)項對應相同的關鍵字,那么,先前散列表中的數(shù)據(jù)項將被替換.散列表在它需要更多的存儲空間時會自動增大容量. 例如,如果散列表的裝載因子是0.75,那么當散列表的容量被使用了75%時,它就把容量增加到原始容量的2倍. 對于數(shù)組和鏈表這兩種數(shù)據(jù)結構,如果要查找它們存儲的某個特定的元素卻不知道它的位置,就需要從頭開始訪

6、問元素直到找到匹配的為止；如果數(shù)據(jù)結構中包含很多的元素,就會浪費時間.這時最好使用散列表來存儲要查找的數(shù)據(jù).,hastable.java,26.5 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可以使用

7、elementAt(int index )獲取指定索引處的向量的元素（索引初始位置是0）a可以使用方法size()獲取向量所含有的元素的個數(shù).另外,與數(shù)組不同的是向量的元素類型不要求一致.需要注意的是,當你把某一種類型的對象放入一個向量后,數(shù)據(jù)被默認為是Object 對象,因此當向量中取出一個元素時應用強制類型轉化運算符轉化為原來的類型.,Vector類的常用方法 public boolean add(Object o) 將對象o添加到向量的末尾. public void add(int index, Object o)將對象o插入到向量的指定位置. public void addElemen

8、ts(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(Object o) 獲取對象o在此向量中首次出現(xiàn)的位置. public

9、int indexOf(Object 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 Object set(int index,Object o) 把指定位置處的成員用o替換掉. public void setElementAt(Object o,int index)把指定位置處的成員用o替換掉. public Enumeration el