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

作者：佚名 2009-11-25 10:31:35

PHP數組實現單鏈表主要是依靠PHP的數組系統用來模擬單鏈表的數據結構，希望本文所描述的內容對新手們有些幫助。

我們今天為大家帶來的時候如何運用PHP數組實現單鏈表的具體方法。對于初學者來說，數組的正確和靈活運用還是比較生疏的，希望通過本文的介紹能夠增加我們的編碼經驗，提高我們的變成能力。

#t#PHP數組實現單鏈表結構

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

單鏈表簡介：

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

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

<?php 
class LinkList   
{  
   /**  
    * 成員變量  
    * @var array    $linkList       鏈表數組  
    * @var number   $listHeader     表頭索引  
    * @var number   $listLength     鏈表長度  
    * @var number   $existedCounts  記錄鏈表中出現過的元素的個數，和$listLength不同的是, 刪除一  
    *                               個元素之后，該值不需要減1，這個也可以用來為新元素分配索引。                            
    */  
   protected  $linkList  =array();  
   protected  $listLength=0;  
   protected  $listHeader=null;  
   protected  $existedCounts=0;  
   /**  
    * 構造函數  
    *   構造函數可以帶一個數組參數，如果有參數，則調用成員方法  
    * createList將數組轉換成鏈表，并算出鏈表長度.如果沒有參  
    * 數，則生成一空鏈表.空鏈表可以通過調用成員方法createList  
    * 生成鏈表.  
    * @access public  
    * @param  array $arr 需要被轉化為鏈表的數組  
    */  
   public function __construct($arr='')  
   {  
     $arr!=null&&$this->createList($arr);  
   }  
   /**  
    * 生成鏈表的函數  
    *   將數組轉變成鏈表，同時計算出鏈表長度。分別賦值給成員標量  
    * $linkList和$listLength.  
    * @access public  
    * @param  array $arr 需要被轉化為鏈表的數組  
    * @return boolean  true表示轉換成功，false表示失敗    
    */  
  public function createList($arr)  
  {   
   if (!is_array($arr))   
    return false;  
   $length=count($arr);  
   for($i=0;$i<$length;$i++)  
   {     
       if($i==$length-1)  
       {  
        //每個鏈表結點包括var和next兩個索引，var表示結點值，next為下一個結點的索引  
        //***一個結點的next為null  
        $list[$i]['var']  =$arr[$i];  
        $list[$i]['next'] =null;  
       }  
       else   
       {  
        $list[$i]['var']  =$arr[$i];  
        $list[$i]['next'] =$i+1;  
       }  
   }  
   $this->linkList      =$list;  
   $this->listLength    =$length;  
   $this->existedCounts =$length;  
   $this->listHeader=0;  
   return true;  
  }  
  /**  
   * 將鏈表還原成一維數組  
   * @access public  
   * @return array    $arr  生成的一維數組  
   */  
  public function returnToArray()  
  {   
   $arr=array();  
   $tmp=$this->linkList[$this->listHeader];  
    for($i=0;$i<$this->listLength;$i++)  
   {  
     $arr[]=$tmp['var'];  
     if ($i!=$this->listLength-1)   
     {  
     $tmp=$this->linkList[$tmp['next']];  
     }  
   }  
   return $arr;  
  }  
public function getLength()  
  {  
          return $this->listLength;  
  }  
  /**  
   * 計算一共刪除過多少個元素  
   * @access public   
   * @return number $count 到目前為止刪除過的元素個數  
   */  
  public function getDeletedNums()  
  {  
          $count=$this->existedCounts-$this->listLength;  
          return $count;  
  }  
  /**  
   * 通過元素索引返回元素序號  
   * @access protected  
   * @param  $index     元素的索引號  
   * @return $num       元素在鏈表中的序號  
   */  
  public function getElemLocation($index)  
  {  
  if (!array_key_exists($index,$this->linkList))   
   return false;  
    $arrIndex=$this->listHeader;  
    for($num=1;$tmp=$this->linkList[$arrIndex];$num++)  
    {  
            if ($index==$arrIndex)   
            break;  
            else   
            {  
                    $arrIndex=$tmp['next'];  
            }  
    }  
    return $num;  
  }  
  /**  
   * 獲取第$i個元素的引用  
   *   這個保護方法不能被外界直接訪問，許多服務方法以來與次方法。  
   * 它用來返回鏈表中第$i個元素的引用，是一個數組  
   * @access protected  
   * @param  number $i 元素的序號  
   * @return reference 元素的引用  
   */  
  protected function &getElemRef($i)  
  {  
          //判斷$i的類型以及是否越界  
          $result=false;  
          if (!is_numeric($i)||(int)$i<=0||(int)$i>$this->listLength)   
          return $result;  
   //由于單鏈表中的任何兩個元素的存儲位置之間沒有固定關系，要取得第i個元素必須從  
   //表頭開始查找，因此單鏈表是非隨機存儲的存儲結構。  
   $j=0;  
   $value=&$this->linkList[$this->listHeader];  
   while ($j<$i-1)  
   {  
           $value=&$this->linkList[$value['next']];  
           $j++;  
   }  
   return $value;  
  }  
  /**  
   * 返回第i個元素的值  
   * @access public  
   * @param  number $i     需要返回的元素的序號，從1開始  
   * @return mixed  第i個元素的值  
   */  
  public function getElemvar($i)  
  {  
    $var=$this->getElemRef($i);  
    if ($var!=false)   
    {  
            return $var['var'];  
    }  
    else return false;  
  }  
  /**  
   *   在第i個元素之后插入一個值為var的新元素  
   *   i的取值應該為[1,$this->listLength]，如果i=0，表示在表的最前段插入，  
   * 如果i=$this->listLength，表示在表的末尾插入,插入的方法為，將第$i-1個元素  
   * 的next指向第$i個元素，然后將第$i個元素的next指向第$i+1個元素，這樣就實現了插入  
   * @access public  
   * @param  number $i   在位置i插入新元素  
   * @param  mixed  $var 要插入的元素的值   
   * @return boolean  成功則返回true,否則返回false  
   */  
  public function insertIntoList($i,$var)  
  {  
          if (!is_numeric($i)||(int)$i<0||(int)$i>$this->listLength)   
          return false;  
          if ($i==0)   
          {  
          //如果$i-0，則在表最前面添加元素，新元素索引為$listLength，這樣是確保不會  
          //覆蓋原來的元素，另外這種情況需要重新設置$listHeader  
              $this->linkList[$this->existedCounts]['var'] =$var;  
              $this->linkList[$this->existedCounts]['next']=$this->listHeader;  
              $this->listHeader=$this->existedCounts;  
              $this->listLength++;  
              $this->existedCounts++;  
              return true;          
          }  
   $value=&$this->getElemRef($i);  
   $this->linkList[$this->existedCounts]['var'] =$var;  
   $this->linkList[$this->existedCounts]['next']=($i==$this->listLength?null:$value['next']);  
   $value['next']=$this->existedCounts;  
   $this->listLength++;  
   $this->existedCounts++;  
   return true;  
  }  
  /**  
   * 刪除第$i個元素  
   *   刪除第$i個元素，該元素為取值應該為[1，$this->listLength],需要注意，刪除元素之后，  
   * $this->listLength減1,而$this->existedCounts不變。刪除的方法為將第$i-1個元素的  
   * next指向第$i+1個元素，那么第$i個元素就從鏈表中刪除了。  
   * @access public  
   * @param  number $i 將要被刪除的元素的序號  
   * @return boolean    成功則返回true,否則返回false  
   */  
  public function delFromList($i)  
  {  
          if (!is_numeric($i)||(int)$i<=0||(int)$i>$this->listLength)   
          return false;  
    if ($i==1)   
    {  
    //若刪除的結點為頭結點，則需要從新設置鏈表頭  
      $tmp=$this->linkList[$this->listHeader];  
      unset($this->linkList[$this->listHeader]);  
      $this->listHeader=$tmp['next'];  
      $this->listLength--;  
      return true;  
    }  
    else   
    {  
     $value    =&$this->getElemRef($i);  
     $prevValue=&$this->getElemRef($i-1);  
     unset($this->linkList[$prevValue['next']]);  
     $prevValue['next']=$value['next'];  
     $this->listLength--;  
     return true;  
    }  
  }  
/**  
  * 對鏈表的元素排序  
  *  謹慎使用此函數，排序后鏈表將被從新初始化，原有的成員變量將會被覆蓋  
  * @accse public  
  * @param  boolean  $sortType='true' 排序方式,true表示升序，false表示降序，默認true     
  */  
public function listSort($sortType='true')  
{  
   //從新修改關聯關系可能會更復雜，所以我選擇先還原成一維數組，然后對數組排序，然后再生成鏈表  
   $arr=$this->returnToArray();  
   $sortType?sort($arr):rsort($arr);  
   $this->createList($arr);  
}  
}  
?>

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

責任編輯：曹凱來源： phpchina.com

PHP數組實現單鏈表