程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 網頁編程 >> PHP編程 >> 關於PHP編程 >> PHP數組實現單鏈表的具體代碼分享

PHP數組實現單鏈表的具體代碼分享

編輯:關於PHP編程

我們今天為大家帶來的時候如何運用PHP數組實現單鏈表結構

此類主要是依靠PHP強大的數組系統來模擬出單鏈表類型的數據結構。 本人完全憑借自己的 興趣來編寫此類,並未考慮其實用性,主要是給大家理解一些簡單的數據結構知識,同時也訓練 一下PHP中的數組運用能力。

單鏈表簡介:

單鏈表是最簡單的鏈表表示。用它來表示線性表時,每一個數據元素占用一個結點(node)。一個 結點一般由兩個域組成,一個域存放數據元素data; 另一個域存放一個指向鏈表中下一個結點的指針link,它指出下一個結點 的開始存儲地址。而最後一個結點的指針為空。單鏈表中數據元素之間的邏 輯關系是由結點中的指針指示的,換句話說,指針為數據元素之間的邏輯關系的映象,則邏輯上相鄰的兩個元素其存儲的物理位置不要求緊鄰,因此, 這種存儲結構為非順序映像或鏈式映像。當然,在PHP沒有指針這個概念,但是我們可以用關聯數組來模擬。

PHP數組實現單鏈表的代碼如下:

  1. <?php 
  2. class LinkList   
  3. {  
  4.    /**  
  5.     * 成員變量  
  6.     * @var array    $linkList       鏈表數組  
  7.     * @var number   $listHeader     表頭索引  
  8.     * @var number   $listLength     鏈表長度  
  9.     * @var number   $existedCounts  記錄鏈表中出現過的元素的個數,和$listLength不同的是, 刪除一  
  10.     *                               個元素之後,該值不需要減1,這個也可以用來為新元素分配索引。                            
  11.     */  
  12.    protected  $linkList  =array();  
  13.    protected  $listLength=0;  
  14.    protected  $listHeader=null;  
  15.    protected  $existedCounts=0;  
  16.    /**  
  17.     * 構造函數  
  18.     *   構造函數可以帶一個數組參數,如果有參數,則調用成員方法  
  19.     * createList將數組轉換成鏈表,並算出鏈表長度.如果沒有參  
  20.     * 數,則生成一空鏈表.空鏈表可以通過調用成員方法createList  
  21.     * 生成鏈表.  
  22.     * @access public  
  23.     * @param  array $arr 需要被轉化為鏈表的數組  
  24.     */  
  25.    public function __construct($arr='')  
  26.    {  
  27.      $arr!=null&&$this->createList($arr);  
  28.    }  
  29.    /**  
  30.     * 生成鏈表的函數  
  31.     *   將數組轉變成鏈表,同時計算出鏈表長度。分別賦值給成員標量  
  32.     * $linkList和$listLength.  
  33.     * @access public  
  34.     * @param  array $arr 需要被轉化為鏈表的數組  
  35.     * @return boolean  true表示轉換成功,false表示失敗    
  36.     */  
  37.   public function createList($arr)  
  38.   {   
  39.    if (!is_array($arr))   
  40.     return false;  
  41.    $length=count($arr);  
  42.    for($i=0;$i<$length;$i++)  
  43.    {     
  44.        if($i==$length-1)  
  45.        {  
  46.         //每個鏈表結點包括var和next兩個索引,var表示結點值,next為下一個結點的索引  
  47.         //最後一個結點的next為null  
  48.         $list[$i]['var']  =$arr[$i];  
  49.         $list[$i]['next'] =null;  
  50.        }  
  51.        else   
  52.        {  
  53.         $list[$i]['var']  =$arr[$i];  
  54.         $list[$i]['next'] =$i+1;  
  55.        }  
  56.    }  
  57.    $this->linkList      =$list;  
  58.    $this->listLength    =$length;  
  59.    $this->existedCounts =$length;  
  60.    $this->listHeader=0;  
  61.    return true;  
  62.   }  
  63.   /**  
  64.    * 將鏈表還原成一維數組  
  65.    * @access public  
  66.    * @return array    $arr  生成的一維數組  
  67.    */  
  68.   public function returnToArray()  
  69.   {   
  70.    $arr=array();  
  71.    $tmp=$this->linkList[$this->listHeader];  
  72.     for($i=0;$i<$this->listLength;$i++)  
  73.    {  
  74.      $arr[]=$tmp['var'];  
  75.      if ($i!=$this->listLength-1)   
  76.      {  
  77.      $tmp=$this->linkList[$tmp['next']];  
  78.      }  
  79.    }  
  80.    return $arr;  
  81.   }  
  82. public function getLength()  
  83.   {  
  84.           return $this->listLength;  
  85.   }  
  86.   /**  
  87.    * 計算一共刪除過多少個元素  
  88.    * @access public   
  89.    * @return number $count 到目前為止刪除過的元素個數  
  90.    */  
  91.   public function getDeletedNums()  
  92.   {  
  93.           $count=$this->existedCounts-$this->listLength;  
  94.           return $count;  
  95.   }  
  96.   /**  
  97.    * 通過元素索引返回元素序號  
  98.    * @access protected  
  99.    * @param  $index     元素的索引號  
  100.    * @return $num       元素在鏈表中的序號  
  101.    */  
  102.   public function getElemLocation($index)  
  103.   {  
  104.   if (!array_key_exists($index,$this->linkList))   
  105.    return false;  
  106.     $arrIndex=$this->listHeader;  
  107.     for($num=1;$tmp=$this->linkList[$arrIndex];$num++)  
  108.     {  
  109.             if ($index==$arrIndex)   
  110.             break;  
  111.             else   
  112.             {  
  113.                     $arrIndex=$tmp['next'];  
  114.             }  
  115.     }  
  116.     return $num;  
  117.   }  
  118.   /**  
  119.    * 獲取第$i個元素的引用  
  120.    *   這個保護方法不能被外界直接訪問,許多服務方法以來與次方法。  
  121.    * 它用來返回鏈表中第$i個元素的引用,是一個數組  
  122.    * @access protected  
  123.    * @param  number $i 元素的序號  
  124.    * @return reference 元素的引用  
  125.    */  
  126.   protected function &getElemRef($i)  
  127.   {  
  128.           //判斷$i的類型以及是否越界  
  129.           $result=false;  
  130.           if (!is_numeric($i)||(int)$i<=0||(int)$i>$this->listLength)   
  131.           return $result;  
  132.    //由於單鏈表中的任何兩個元素的存儲位置之間沒有固定關系,要取得第i個元素必須從  
  133.    //表頭開始查找,因此單鏈表是非隨機存儲的存儲結構。  
  134.    $j=0;  
  135.    $value=&$this->linkList[$this->listHeader];  
  136.    while ($j<$i-1)  
  137.    {  
  138.            $value=&$this->linkList[$value['next']];  
  139.            $j++;  
  140.    }  
  141.    return $value;  
  142.   }  
  143.   /**  
  144.    * 返回第i個元素的值  
  145.    * @access public  
  146.    * @param  number $i     需要返回的元素的序號,從1開始  
  147.    * @return mixed  第i個元素的值  
  148.    */  
  149.   public function getElemvar($i)  
  150.   {  
  151.     $var=$this->getElemRef($i);  
  152.     if ($var!=false)   
  153.     {  
  154.             return $var['var'];  
  155.     }  
  156.     else return false;  
  157.   }  
  158.   /**  
  159.    *   在第i個元素之後插入一個值為var的新元素  
  160.    *   i的取值應該為[1,$this->listLength],如果i=0,表示在表的最前段插入,  
  161.    * 如果i=$this->listLength,表示在表的末尾插入,插入的方法為,將第$i-1個元素  
  162.    * 的next指向第$i個元素,然後將第$i個元素的next指向第$i+1個元素,這樣就實現了插入  
  163.    * @access public  
  164.    * @param  number $i   在位置i插入新元素  
  165.    * @param  mixed  $var 要插入的元素的值   
  166.    * @return boolean  成功則返回true,否則返回false  
  167.    */  
  168.   public function insertIntoList($i,$var)  
  169.   {  
  170.           if (!is_numeric($i)||(int)$i<0||(int)$i>$this->listLength)   
  171.           return false;  
  172.           if ($i==0)   
  173.           {  
  174.           //如果$i-0,則在表最前面添加元素,新元素索引為$listLength,這樣是確保不會  
  175.           //覆蓋原來的元素,另外這種情況需要重新設置$listHeader  
  176.               $this->linkList[$this->existedCounts]['var'] =$var;  
  177.               $this->linkList[$this->existedCounts]['next']=$this->listHeader;  
  178.               $this->listHeader=$this->existedCounts;  
  179.               $this->listLength++;  
  180.               $this->existedCounts++;  
  181.               return true;          
  182.           }  
  183.    $value=&$this->getElemRef($i);  
  184.    $this->linkList[$this->existedCounts]['var'] =$var;  
  185.    $this->linkList[$this->existedCounts]['next']=($i==$this->listLength?null:$value['next']);  
  186.    $value['next']=$this->existedCounts;  
  187.    $this->listLength++;  
  188.    $this->existedCounts++;  
  189.    return true;  
  190.   }  
  191.   /**  
  192.    * 刪除第$i個元素  
  193.    *   刪除第$i個元素,該元素為取值應該為[1,$this->listLength],需要注意,刪除元素之後,  
  194.    * $this->listLength減1,而$this->existedCounts不變。刪除的方法為將第$i-1個元素的  
  195.    * next指向第$i+1個元素,那麼第$i個元素就從鏈表中刪除了。  
  196.    * @access public  
  197.    * @param  number $i 將要被刪除的元素的序號  
  198.    * @return boolean    成功則返回true,否則返回false  
  199.    */  
  200.   public function delFromList($i)  
  201.   {  
  202.           if (!is_numeric($i)||(int)$i<=0||(int)$i>$this->listLength)   
  203.           return false;  
  204.     if ($i==1)   
  205.     {  
  206.     //若刪除的結點為頭結點,則需要從新設置鏈表頭  
  207.       $tmp=$this->linkList[$this->listHeader];  
  208.       unset($this->linkList[$this->listHeader]);  
  209.       $this->listHeader=$tmp['next'];  
  210.       $this->listLength--;  
  211.       return true;  
  212.     }  
  213.     else   
  214.     {  
  215.      $value    =&$this->getElemRef($i);  
  216.      $prevValue=&$this->getElemRef($i-1);  
  217.      unset($this->linkList[$prevValue['next']]);  
  218.      $prevValue['next']=$value['next'];  
  219.      $this->listLength--;  
  220.      return true;  
  221.     }  
  222.   }  
  223. /**  
  224.   * 對鏈表的元素排序  
  225.   *  謹慎使用此函數,排序後鏈表將被從新初始化,原有的成員變量將會被覆蓋  
  226.   * @accse public  
  227.   * @param  boolean  $sortType='true' 排序方式,true表示升序,false表示降序,默認true     
  228.   */  
  229. public function listSort($sortType='true')  
  230. {  
  231.    //從新修改關聯關系可能會更復雜,所以我選擇先還原成一維數組,然後對數組排序,然後再生成鏈表  
  232.    $arr=$this->returnToArray();  
  233.    $sortType?sort($arr):rsort($arr);  
  234.    $this->createList($arr);  
  235. }  
  236. }  
  237. ?> 

上面這段代碼就是PHP數組實現單鏈表的源碼編寫,希望對大家有所幫助。


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved