<rt id="bn8ez"></rt>
<label id="bn8ez"></label>
  • 

    • <span id="bn8ez"></span>
    

    <label id="bn8ez"><meter id="bn8ez"></meter></label>
    

    
    

    




    







												


        



    
	
    
		
			

    

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

    

    

    
	
    

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


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


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

    

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

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

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

    　　鏈表類List的源代碼如下： 

    

    import java.io.*; 
    public class List 
    { 
    　    /*用變量來實現表頭*/ 
    　    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() 
    　    /*鏈表復位，使第一個結點成為當前結點*/ 
    　    { 
    　　Pointer    =null; 
    　}     
    　    public boolean isEmpty() 
    　    /*判斷鏈表是否為空*/ 
    　    { 
    　　    return(Length==0); 
    　}     
    　    public boolean isEnd() 
    　    /*判斷當前結點是否為最后一個結點*/ 
    　    { 
    　　    if(Length==0) 
    　　　    throw new java.lang.NullPointerException(); 
    　　    else if(Length==1) 
    　　　    return true; 
    　　    else 
    　　　    return(cursor()==Tail); 
    　}     
    　    public Object nextNode() 
    　    /*返回當前結點的下一個結點的值，并使其成為當前結點*/ 
    　    { 
    　　    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() 
    　    /*返回當前結點的值*/ 
    　    { 
    　　Node temp    =cursor(); 
    　　    return temp.data; 
    　}     
    　　 
    　    public void insert(Object d) 
    　    /*在當前結點前插入一個結點，并使其成為當前結點*/ 
    　    { 
    　　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() 
    　    /*將當前結點移出鏈表，下一個結點成為當前結點，如果移出的結點是最后一個結點，則第一個結點成為當前結點*/ 
    　    { 
    　　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() 
    　    /*返回當前結點的指針*/ 
    　    { 
    　　    if(Head==null) 
    　　　    throw new java.lang.NullPointerException(); 
    　　    else if(Pointer==null) 
    　　　    return Head; 
    　　    else 
    　　　    return Pointer.next; 
    　}     
    　    public static void main(String[] args) 
    　    /*鏈表的簡單應用舉例*/ 
    　    { 
    　　List a    =new List (); 
    　　    for(int i=1;i&lt;=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(); 
    　　　　　    //確保用戶看清程序運行結果 
    　　　　}     
    　　　　    catch(IOException e) 
    　　　　    {} 
    　　　}     
    　　}     
    　　    class Node 
    　　    /*構成鏈表的結點定義*/ 
    　　    { 
    　　　Object data; 
    　　　Node next; 
    　　　Node(Object d) 
    　　　    { 
    　　　　data    =d; 
    　　　　next    =null; 
    　　　}     
    　　}     
    

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

    　　可以用這樣的代碼來實現： 

    

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

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

    參考文獻：《網絡編程語言JAVA》 孫淑玲、王太權、陳意云 

    
	
    
	


    
	    
    




    








    

				
			
    
		    		
	
    
	
    
		
			


		
	
    

    


    







    
        
	



主站蜘蛛池模板：
色妞WWW精品免费视频|
国产亚洲精品看片在线观看|
亚洲av无一区二区三区|
亚洲综合久久夜AV |
亚洲无砖砖区免费|
老湿机一区午夜精品免费福利|
亚洲色WWW成人永久网址|
青娱乐免费视频在线观看|
国产成人va亚洲电影|
内射少妇36P亚洲区|
免费一级毛片在线播放不收费|
污污网站免费观看|
精品国产日韩亚洲一区91|
久久久久亚洲精品影视|
国产在线98福利播放视频免费
|
羞羞网站免费观看|
黑人精品videos亚洲人|
特级淫片国产免费高清视频|
免费国产午夜高清在线视频|
日韩亚洲人成网站|
亚洲国产av一区二区三区丶|
亚洲精品无码久久久影院相关影片
|
自拍日韩亚洲一区在线|
亚洲精品制服丝袜四区|
日本xxwwxxww在线视频免费|
亚洲视频免费在线观看|
国产精品美女久久久免费
|
亚洲第一se情网站|
亚洲无成人网77777|
国产亚洲精品观看91在线|
国产jizzjizz视频免费看|
99久久久精品免费观看国产|
国产成人一区二区三区视频免费|
免费夜色污私人影院网站电影|
亚洲精品美女在线观看|
国产亚洲综合久久系列|
亚洲毛片网址在线观看中文字幕|
在线精品免费视频无码的
|
亚洲爱情岛论坛永久|
亚洲欧洲精品成人久久奇米网|
日本视频免费在线|