PHP中怎么利用數組實現單鏈表

本篇文章為大家展示了PHP中怎么利用數組實現單鏈表，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

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中怎么利用數組實現單鏈表，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。