<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》 孫淑玲、王太權、陳意云 

    
	
    
	


    
	    
    




    








    

				
			
    
		    		
	
    
	
    
		
			


		
	
    

    


    







    
        
	



主站蜘蛛池模板：
亚洲中文字幕久久无码|
国产精品美女久久久免费
|
亚洲人成图片小说网站|
久久免费区一区二区三波多野|
日韩免费a级在线观看|
二级毛片免费观看全程|
久久夜色精品国产噜噜亚洲AV|
毛片基地免费观看|
亚洲精品视频免费观看|
久久亚洲AV成人出白浆无码国产|
无码日韩人妻av一区免费|
一级黄色免费毛片|
亚洲妓女综合网99|
亚洲精品无码99在线观看|
一级特黄aaa大片免费看|
亚洲精品在线播放视频|
免费永久国产在线视频|
最近免费视频中文字幕大全|
久久精品国产亚洲AV电影网|
亚洲欧洲无码AV电影在线观看|
AV无码免费永久在线观看|
亚洲一区在线视频观看|
亚洲一区无码精品色|
72pao国产成视频永久免费|
亚洲精品国产肉丝袜久久|
无码欧精品亚洲日韩一区夜夜嗨|
曰批免费视频播放在线看片二
|
亚洲av中文无码乱人伦在线播放
|
国产无遮挡裸体免费视频|
外国成人网在线观看免费视频|
亚洲av无码av在线播放|
久久久久亚洲精品日久生情|
亚洲午夜精品久久久久久浪潮|
久久天天躁狠狠躁夜夜免费观看|
精品国产免费人成网站|
真正全免费视频a毛片|
亚洲深深色噜噜狠狠网站|
亚洲最大的成网4438|
狠狠亚洲狠狠欧洲2019|
国产精品免费_区二区三区观看|
2019中文字幕在线电影免费|