Java常見數(shù)據(jù)結(jié)構(gòu)實現(xiàn)

1、常見數(shù)據(jù)結(jié)構(gòu)的常見數(shù)據(jù)結(jié)構(gòu)的Java實現(xiàn)實現(xiàn) 我們在編寫程序時經(jīng)常要和各種數(shù)據(jù)打交道我們在編寫程序時經(jīng)常要和各種數(shù)據(jù)打交道, ,為處理這些為處理這些數(shù)據(jù)所選的數(shù)據(jù)結(jié)構(gòu)對于我們的程序的運行效率是非常重要的數(shù)據(jù)所選的數(shù)據(jù)結(jié)構(gòu)對于我們的程序的運行效率是非常重要的. .這章講述幾種常見的數(shù)據(jù)結(jié)構(gòu)的這章講述幾種常見的數(shù)據(jù)結(jié)構(gòu)的Java Java 實現(xiàn)實現(xiàn). . 在學習數(shù)據(jù)結(jié)構(gòu)這門課程的時候在學習數(shù)據(jù)結(jié)構(gòu)這門課程的時候, ,人們要用具體的算法去實人們要用具體的算法去實現(xiàn)相應的數(shù)據(jù)結(jié)構(gòu)現(xiàn)相應的數(shù)據(jù)結(jié)構(gòu), ,例如例如, ,為了實現(xiàn)鏈表這種數(shù)據(jù)結(jié)構(gòu)為了實現(xiàn)鏈表這種數(shù)據(jù)結(jié)構(gòu), ,需要實需要實現(xiàn)往鏈表中插入節(jié)點或從

2、鏈表中刪除節(jié)點的算法現(xiàn)往鏈表中插入節(jié)點或從鏈表中刪除節(jié)點的算法, ,感覺有些煩感覺有些煩瑣瑣. . 在在jdk1.2 jdk1.2 之后之后,Java ,Java 提供了實現(xiàn)常見數(shù)據(jù)結(jié)構(gòu)的類提供了實現(xiàn)常見數(shù)據(jù)結(jié)構(gòu)的類, ,創(chuàng)建創(chuàng)建鏈表等數(shù)據(jù)結(jié)構(gòu)和創(chuàng)建數(shù)組一樣簡單鏈表等數(shù)據(jù)結(jié)構(gòu)和創(chuàng)建數(shù)組一樣簡單, ,不再需要你去寫具體的不再需要你去寫具體的算法算法. .我們主要講述這些類的用法我們主要講述這些類的用法, ,但對這些數(shù)據(jù)結(jié)構(gòu)的原理的但對這些數(shù)據(jù)結(jié)構(gòu)的原理的掌握對于我們熟練地用好這些類還是很有幫助的掌握對于我們熟練地用好這些類還是很有幫助的. .26.1鏈表鏈表如果需要處理一些類型相同的數(shù)據(jù)如果需要

3、處理一些類型相同的數(shù)據(jù), ,人們習慣上使人們習慣上使用數(shù)組這種數(shù)據(jù)結(jié)構(gòu)用數(shù)組這種數(shù)據(jù)結(jié)構(gòu), ,但數(shù)組在使用之前必須定義但數(shù)組在使用之前必須定義大小大小, ,而且不能動態(tài)定義大小而且不能動態(tài)定義大小. .有時可能給數(shù)組分有時可能給數(shù)組分配了太多的單元而浪費了寶貴的內(nèi)存資源配了太多的單元而浪費了寶貴的內(nèi)存資源, ,糟糕的糟糕的一方面是一方面是, ,程序運行時需要處理的數(shù)據(jù)可能多于數(shù)程序運行時需要處理的數(shù)據(jù)可能多于數(shù)組的單元組的單元. .當需要動態(tài)地減少或增加數(shù)據(jù)項時當需要動態(tài)地減少或增加數(shù)據(jù)項時, ,可可以使用鏈表這種數(shù)據(jù)結(jié)構(gòu)以使用鏈表這種數(shù)據(jù)結(jié)構(gòu). .鏈表是由若干個稱作節(jié)點的對象組成的一種數(shù)據(jù)鏈

4、表是由若干個稱作節(jié)點的對象組成的一種數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu), ,每個節(jié)點含有一個數(shù)據(jù)和下一個節(jié)點對象的每個節(jié)點含有一個數(shù)據(jù)和下一個節(jié)點對象的引用引用( (單鏈表單鏈表 ), ),或含有一個數(shù)據(jù)并含有上一個節(jié)或含有一個數(shù)據(jù)并含有上一個節(jié)點對象的引用和下一個節(jié)點對象的引用點對象的引用和下一個節(jié)點對象的引用( (雙鏈表雙鏈表) .) .1 .創(chuàng)建鏈表創(chuàng)建鏈表使用使用java.util java.util 包中的包中的LinkedListLinkedList類創(chuàng)建一個鏈類創(chuàng)建一個鏈表表. .例如例如, ,LinkedList mylist=new LinkedList();LinkedList mylist=n

5、ew LinkedList();創(chuàng)建了一個空鏈表創(chuàng)建了一個空鏈表. .然后然后mylistmylist鏈表可以使用鏈表可以使用add()add()方法向這個鏈表依次增加節(jié)點方法向這個鏈表依次增加節(jié)點. .例如例如mylist.add(mylist.add(“ItIt”);mylist.add();mylist.add(“isis”););mylist.add(mylist.add(“a a”);mylist.add();mylist.add(“doordoor”););mylistmylist可以使用方法可以使用方法public Object get(index i)public Object

6、 get(index i)獲取第獲取第i i個節(jié)點中存?zhèn)€節(jié)點中存儲的數(shù)據(jù)儲的數(shù)據(jù). .存放在節(jié)點中的數(shù)據(jù)都被看作是一個存放在節(jié)點中的數(shù)據(jù)都被看作是一個Object Object 對象對象. .import java.util.*;public class LinkListOne public static void main(String args) LinkedList mylist=new LinkedList(); mylist.add(It); /鏈表中的第一個節(jié)點鏈表中的第一個節(jié)點. mylist.add(is); /鏈表中的第二個節(jié)點鏈表中的第二個節(jié)點. mylist.add(a)

7、; /鏈表中的第三個節(jié)點鏈表中的第三個節(jié)點. mylist.add(door); /鏈表中的第四個節(jié)點鏈表中的第四個節(jié)點. int number=mylist.size(); /獲取鏈表的長度獲取鏈表的長度. for(int i=0;i 時,稱s1 大于s2,pare(s2) 時時,稱稱a大于大于pare(s2) 時時,稱稱a小于小于b.然后用帶然后用帶Comparator參數(shù)的構(gòu)造方法參數(shù)的構(gòu)造方法TreeSet(Comparator c);創(chuàng)建一個樹集創(chuàng)建一個樹集,通過參數(shù)通過參數(shù)c規(guī)定樹集的節(jié)點按怎樣的順序排列規(guī)定樹集的節(jié)點按怎樣的順序排列,如下所示如下所示TreeSet mytree=

8、new TreeSet(new Comparator()public int compare(Object a,Object b)Student stu1=(Student)a;Student stu2=(Student)b;return pareTo(stu2););注注 Comparator 是是java.util 包中的一個接口包中的一個接口,compare 是接口中的方是接口中的方法法,因此必須給出方法體因此必須給出方法體.注注 樹集中不容許出現(xiàn)大小相等的兩個節(jié)點樹集中不容許出現(xiàn)大小相等的兩個節(jié)點, ,例如例如, ,在上述在上述例子中如果再添加語句例子中如果再添加語句st5=new S

9、tudent(76,keng wenyi); mytree.add(st5);st5=new Student(76,keng wenyi); mytree.add(st5);是無效的是無效的. .如果允許成績相同如果允許成績相同, ,可把上述例子中可把上述例子中Student Student 類類中的中的compareTo compareTo 方法更改為方法更改為public int compareTo(Object b)public int compareTo(Object b) Student st=(Student)b; Student st=(Student)b;if(this.eng

10、lish-st.English)=0)if(this.english-st.English)=0)return 1;return 1;elseelsereturn (this.english-st.english);return (this.english-st.english); 注注 理論上已經(jīng)知道理論上已經(jīng)知道, ,把一個元素插入樹集的合適位置要比把一個元素插入樹集的合適位置要比插入數(shù)組或鏈表中的合適位置效率高插入數(shù)組或鏈表中的合適位置效率高. .TreeSetTreeSet類的一些常用方法類的一些常用方法public boolean add(Object o) public boole

11、an add(Object o) 向樹集添加加節(jié)點向樹集添加加節(jié)點, ,添加成功返回添加成功返回true,true,否則返回否則返回false.false.public void clear() public void clear() 刪除所有的節(jié)點刪除所有的節(jié)點. .public void contains(Object o) public void contains(Object o) 如果包含節(jié)點如果包含節(jié)點o o返回返回true .true .public Object first() public Object first() 返回根節(jié)點返回根節(jié)點, ,即第一個節(jié)點即第一個節(jié)點 最小的節(jié)點最小的節(jié)點 . .public Object last() public Object last() 返回最后一個節(jié)點返回最后一個節(jié)點 最大的節(jié)點最大的節(jié)點 . .public isEmpty() public isEmpty()