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

          

          

          
	
          

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


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

          

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

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

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

          　　鏈表類List的源代碼如下： 

          

          import java.io.*; 
          public class List 
          { 
          　          /*用變量來實(shí)現(xiàn)表頭*/ 
          　          private Node Head=null; 
          　          private Node Tail=null; 
          　          private Node Pointer=null; 
          　          private int Length=0; 
          　          public void deleteAll() 
          　          /*清空整個(gè)鏈表*/ 
          　          { 
          　　Head          =null; 
          　　Tail          =null; 
          　　Pointer          =null; 
          　　Length          =0; 
          　}           
          　          public void reset() 
          　          /*鏈表復(fù)位，使第一個(gè)結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)*/ 
          　          { 
          　　Pointer          =null; 
          　}           
          　          public boolean isEmpty() 
          　          /*判斷鏈表是否為空*/ 
          　          { 
          　　          return(Length==0); 
          　}           
          　          public boolean isEnd() 
          　          /*判斷當(dāng)前結(jié)點(diǎn)是否為最后一個(gè)結(jié)點(diǎn)*/ 
          　          { 
          　　          if(Length==0) 
          　　　          throw new java.lang.NullPointerException(); 
          　　          else if(Length==1) 
          　　　          return true; 
          　　          else 
          　　　          return(cursor()==Tail); 
          　}           
          　          public Object nextNode() 
          　          /*返回當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的值，并使其成為當(dāng)前結(jié)點(diǎn)*/ 
          　          { 
          　　          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é)點(diǎn)的值*/ 
          　          { 
          　　Node temp          =cursor(); 
          　　          return temp.data; 
          　}           
          　　 
          　          public void insert(Object d) 
          　          /*在當(dāng)前結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)，并使其成為當(dāng)前結(jié)點(diǎn)*/ 
          　          { 
          　　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é)點(diǎn)移出鏈表，下一個(gè)結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)，如果移出的結(jié)點(diǎn)是最后一個(gè)結(jié)點(diǎn)，則第一個(gè)結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)*/ 
          　          { 
          　　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é)點(diǎn)的指針*/ 
          　          { 
          　　          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(); 
          　　　　　          //確保用戶看清程序運(yùn)行結(jié)果 
          　　　　}           
          　　　　          catch(IOException e) 
          　　　　          {} 
          　　　}           
          　　}           
          　　          class Node 
          　　          /*構(gòu)成鏈表的結(jié)點(diǎn)定義*/ 
          　　          { 
          　　　Object data; 
          　　　Node next; 
          　　　Node(Object d) 
          　　　          { 
          　　　　data          =d; 
          　　　　next          =null; 
          　　　}           
          　　}           
          

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

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

          

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

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

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

          
	
          
	


          
	    
    




          








          

				
			
          
		          		
	
          
	
          
		
			


		
	
          

          


    







          
        
	




主站蜘蛛池模板：
句容市|
五大连池市|
潞西市|
营口市|
邳州市|
府谷县|
河东区|
从江县|
墨玉县|
南靖县|
黑水县|
海南省|
攀枝花市|
休宁县|
平定县|
临湘市|
牡丹江市|
南澳县|
遂昌县|
五大连池市|
郧西县|
化德县|
聂拉木县|
仪陇县|
朝阳县|
宽城|
枝江市|
金平|
义马市|
棋牌|
大关县|
中超|
玉林市|
土默特左旗|
城步|
嘉义县|
柯坪县|
沙坪坝区|
蒙山县|
沾益县|
广东省|