kooyee ‘s blog
          
			開源軟件， 眾人努力的結(jié)晶， 全人類的共同財富
		          		
	
          

          

          

          
	
          

          posts - 103, comments - 55, trackbacks - 0, articles - 66
          
	
 
 ::
首頁 ::
新隨筆 ::
聯(lián)系 ::
聚合
 ::
管理


          
		          		
	
          
	
          
		
			
          
			
          
		          		
		
			
          
				
					
	
          
		
          
			
          
				[J2SE] Java語言中鏈表和雙向鏈表的實現(xiàn)
			
          
 			Posted on 2007-08-02 00:04 kooyee 閱讀(244) 評論(0)  編輯  收藏  所屬分類: Java  
			
			


		
          
		
          鏈表是一種重要的數(shù)據(jù)結(jié)構(gòu)，在程序設(shè)計中占有很重要的地位。C語言和C＋＋語言中是用指針來實現(xiàn)鏈表結(jié)構(gòu)的，由于Java語言不提供指針，所以有人認為在Java語言中不能實現(xiàn)鏈表，其實不然，Java語言比C和C＋＋更容易實現(xiàn)鏈表結(jié)構(gòu)。Java語言中的對象引用實際上是一個指針（本文中的指針均為概念上的意義，而非語言提供的數(shù)據(jù)類型），所以我們可以編寫這樣的類來實現(xiàn)鏈表中的結(jié)點。 

          

          class Node 
          { 
          　Object data; 
          　Node next;          //指向下一個結(jié)點 
          }
          

          　　將數(shù)據(jù)域定義成Object類是因為Object類是廣義超類，任何類對象都可以給其賦值，增加了代碼的通用性。為了使鏈表可以被訪問還需要定義一個表頭，表頭必須包含指向第一個結(jié)點的指針和指向當(dāng)前結(jié)點的指針。為了便于在鏈表尾部增加結(jié)點，還可以增加一指向鏈表尾部的指針，另外還可以用一個域來表示鏈表的大小，當(dāng)調(diào)用者想得到鏈表的大小時，不必遍歷整個鏈表。下圖是這種鏈表的示意圖： 
          鏈表的數(shù)據(jù)結(jié)構(gòu) 

          　　我們可以用類List來實現(xiàn)鏈表結(jié)構(gòu)，用變量Head、Tail、Length、Pointer來實現(xiàn)表頭。存儲當(dāng)前結(jié)點的指針時有一定的技巧，Pointer并非存儲指向當(dāng)前結(jié)點的指針，而是存儲指向它的前趨結(jié)點的指針,當(dāng)其值為null時表示當(dāng)前結(jié)點是第一個結(jié)點。那么為什么要這樣做呢？這是因為當(dāng)刪除當(dāng)前結(jié)點后仍需保證剩下的結(jié)點構(gòu)成鏈表，如果Pointer指向當(dāng)前結(jié)點，則會給操作帶來很大困難。那么如何得到當(dāng)前結(jié)點呢，我們定義了一個方法cursor(),返回值是指向當(dāng)前結(jié)點的指針。類List還定義了一些方法來實現(xiàn)對鏈表的基本操作，通過運用這些基本操作我們可以對鏈表進行各種操作。例如reset()方法使第一個結(jié)點成為當(dāng)前結(jié)點。insert(Object d)方法在當(dāng)前結(jié)點前插入一個結(jié)點，并使其成為當(dāng)前結(jié)點。remove()方法刪除當(dāng)前結(jié)點同時返回其內(nèi)容，并使其后繼結(jié)點成為當(dāng)前結(jié)點，如果刪除的是最后一個結(jié)點，則第一個結(jié)點變?yōu)楫?dāng)前結(jié)點。 

          　　鏈表類List的源代碼如下： 

          

          import java.io.*; 
          public class List 
          { 
          　          /*用變量來實現(xiàn)表頭*/ 
          　          private Node Head=null; 
          　          private Node Tail=null; 
          　          private Node Pointer=null; 
          　          private int Length=0; 
          　          public void deleteAll() 
          　          /*清空整個鏈表*/ 
          　          { 
          　　Head          =null; 
          　　Tail          =null; 
          　　Pointer          =null; 
          　　Length          =0; 
          　}           
          　          public void reset() 
          　          /*鏈表復(fù)位，使第一個結(jié)點成為當(dāng)前結(jié)點*/ 
          　          { 
          　　Pointer          =null; 
          　}           
          　          public boolean isEmpty() 
          　          /*判斷鏈表是否為空*/ 
          　          { 
          　　          return(Length==0); 
          　}           
          　          public boolean isEnd() 
          　          /*判斷當(dāng)前結(jié)點是否為最后一個結(jié)點*/ 
          　          { 
          　　          if(Length==0) 
          　　　          throw new java.lang.NullPointerException(); 
          　　          else if(Length==1) 
          　　　          return true; 
          　　          else 
          　　　          return(cursor()==Tail); 
          　}           
          　          public Object nextNode() 
          　          /*返回當(dāng)前結(jié)點的下一個結(jié)點的值，并使其成為當(dāng)前結(jié)點*/ 
          　          { 
          　　          if(Length==1) 
          　　　          throw new java.util.NoSuchElementException(); 
          　　          else if(Length==0) 
          　　　          throw new java.lang.NullPointerException(); 
          　　          else 
          　　          { 
          　　　Node temp          =cursor(); 
          　　　Pointer          =temp; 
          　　　          if(temp!=Tail) 
          　　　　          return(temp.next.data); 
          　　　          else 
          　　　　          throw new java.util.NoSuchElementException(); 
          　　}           
          　}           
          　          public Object currentNode() 
          　          /*返回當(dāng)前結(jié)點的值*/ 
          　          { 
          　　Node temp          =cursor(); 
          　　          return temp.data; 
          　}           
          　　 
          　          public void insert(Object d) 
          　          /*在當(dāng)前結(jié)點前插入一個結(jié)點，并使其成為當(dāng)前結(jié)點*/ 
          　          { 
          　　Node e          =new Node(d); 
          　　          if(Length==0) 
          　　          { 
          　　　Tail          =e; 
          　　　Head          =e; 
          　　}           
          　　          else 
          　　          { 
          　　　Node temp          =cursor(); 
          　　　e.next          =temp; 
          　　　          if(Pointer==null) 
          　　　　Head          =e; 
          　　　          else 
          　　　　Pointer.next          =e; 
          　　}           
          　　Length＋＋; 
          　}           
          　          public int size() 
          　          /*返回鏈表的大小*/ 
          　          { 
          　　          return (Length); 
          　}           
          　          public Object remove() 
          　          /*將當(dāng)前結(jié)點移出鏈表，下一個結(jié)點成為當(dāng)前結(jié)點，如果移出的結(jié)點是最后一個結(jié)點，則第一個結(jié)點成為當(dāng)前結(jié)點*/ 
          　          { 
          　　Object temp; 
          　　          if(Length==0) 
          　　　          throw new java.util.NoSuchElementException(); 
          　　          else if(Length==1) 
          　　          { 
          　　　temp          =Head.data; 
          　　　deleteAll(); 
          　　}           
          　　          else 
          　　          { 
          　　　Node cur          =cursor(); 
          　　　temp          =cur.data; 
          　　　          if(cur==Head) 
          　　　　Head          =cur.next; 
          　　　          else if(cur==Tail) 
          　　　          { 
          　　　　Pointer.next          =null; 
          　　　　Tail          =Pointer; 
          　　　　reset(); 
          　　　}           
          　　　          else 
          　　　　Pointer.next          =cur.next; 
          　　　　Length－－; 
          　　}           
          　　          return temp; 
          　}           
          　          private Node cursor() 
          　          /*返回當(dāng)前結(jié)點的指針*/ 
          　          { 
          　　          if(Head==null) 
          　　　          throw new java.lang.NullPointerException(); 
          　　          else if(Pointer==null) 
          　　　          return Head; 
          　　          else 
          　　　          return Pointer.next; 
          　}           
          　          public static void main(String[] args) 
          　          /*鏈表的簡單應(yīng)用舉例*/ 
          　          { 
          　　List a          =new List (); 
          　　          for(int i=1;i<=10;i＋＋) 
          　　　a.insert(          new Integer(i)); 
          　　　System.out.println(a.currentNode()); 
          　　　          while(!a.isEnd()) 
          　　　　System.out.println(a.nextNode()); 
          　　　　a.reset(); 
          　　　　          while(!a.isEnd()) 
          　　　　          { 
          　　　　　a.remove(); 
          　　　　}           
          　　　　a.remove(); 
          　　　　a.reset(); 
          　　　　          if(a.isEmpty()) 
          　　　　　System.out.println(          "There is no Node in List \n"); 
          　　　　　System.in.println(          "You can press return to quit\n"); 
          　　　　          try 
          　　　　          { 
          　　　　　System.in.read(); 
          　　　　　          //確保用戶看清程序運行結(jié)果 
          　　　　}           
          　　　　          catch(IOException e) 
          　　　　          {} 
          　　　}           
          　　}           
          　　          class Node 
          　　          /*構(gòu)成鏈表的結(jié)點定義*/ 
          　　          { 
          　　　Object data; 
          　　　Node next; 
          　　　Node(Object d) 
          　　　          { 
          　　　　data          =d; 
          　　　　next          =null; 
          　　　}           
          　　}           
          

          　　讀者還可以根據(jù)實際需要定義新的方法來對鏈表進行操作。雙向鏈表可以用類似的方法實現(xiàn)只是結(jié)點的類增加了一個指向前趨結(jié)點的指針。 

          　　可以用這樣的代碼來實現(xiàn)： 

          

          class Node 
          { 
          　Object data; 
          　Node next; 
          　Node previous; 
          　Node(Object d) 
          　          { 
          　　data          =d; 
          　　next          =null; 
          　　previous          =null; 
          　}           
          }           
          

          　　當(dāng)然，雙向鏈表基本操作的實現(xiàn)略有不同。鏈表和雙向鏈表的實現(xiàn)方法，也可以用在堆棧和隊列的實現(xiàn)中，這里就不再多寫了，有興趣的讀者可以將List類的代碼稍加改動即可。

          參考文獻：《網(wǎng)絡(luò)編程語言JAVA》 孫淑玲、王太權(quán)、陳意云 

          
	
          
	


          
	    
    




          








          

				
			
          
		          		
	
          
	
          
		
			


		
	
          

          


    







          
        
	




主站蜘蛛池模板：
云南省|
定陶县|
砚山县|
尉犁县|
金寨县|
绥江县|
二连浩特市|
铁岭县|
黄平县|
南皮县|
罗城|
常州市|
星子县|
浦北县|
南江县|
锦州市|
卫辉市|
内丘县|
天峨县|
台前县|
阳信县|
明光市|
洮南市|
辉南县|
三原县|
嘉禾县|
拜泉县|
正定县|
陕西省|
汕尾市|
土默特右旗|
章丘市|
彝良县|
漠河县|
常宁市|
青神县|
香河县|
资溪县|
仙游县|
上林县|
民县|