快捷導(dǎo)航

PHP實(shí)現(xiàn)鏈表的定義與反轉(zhuǎn)功能示例

更新時(shí)間：2018年06月09日 09:32:33 作者：徐彬

這篇文章主要介紹了PHP實(shí)現(xiàn)鏈表的定義與反轉(zhuǎn)功能,結(jié)合實(shí)例形式分析了PHP鏈表的基本定義、添加、移除、遍歷以及兩種反轉(zhuǎn)操作相關(guān)實(shí)現(xiàn)技巧,需要的朋友可以參考下

本文實(shí)例講述了PHP實(shí)現(xiàn)鏈表的定義與反轉(zhuǎn)功能。分享給大家供大家參考，具體如下：

PHP定義鏈表及添加、移除、遍歷等操作：

<?php
class Node
{
  private $Data;//節(jié)點(diǎn)數(shù)據(jù)
  private $Next;//下一節(jié)點(diǎn)
 
  public function setData($value){
    $this->Data=$value;
  }
 
  public function setNext($value){
     $this->Next=$value;
  }  
 
  public function getData(){
    return $this->Data;
  }
 
  public function getNext(){
    return $this->Next;
  }
 
  public function __construct($data,$next){
    $this->setData($data);
    $this->setNext($next);
  }
}
class LinkList
{
  private $header;//頭節(jié)點(diǎn)
  private $size;//長(zhǎng)度
  public function getSize()
 {
    $i=0;
    $node=$this->header;
    while($node->getNext()!=null)
    {  
  $i++;
      $node=$node->getNext();
    }
    return $i;
  }
 
  public function setHeader($value){
    $this->header=$value;
  }
 
  public function getHeader(){
    return $this->header;
  }
 
  public function __construct(){
    header("content-type:text/html; charset=utf-8");
    $this->setHeader(new Node(null,null));
  }
  /**
  *@author MzXy
  *@param $data--要添加節(jié)點(diǎn)的數(shù)據(jù)
  * 
  */
  public function add($data)
  {
    $node=$this->header;
    while($node->getNext()!=null)
    {
      $node=$node->getNext();
    }
    $node->setNext(new Node($data,null));
  }
   /**
  *@author MzXy
  *@param $data--要移除節(jié)點(diǎn)的數(shù)據(jù)
  * 
  */
  public function removeAt($data)
  {
    $node=$this->header;
    while($node->getData()!=$data)
    {
      $node=$node->getNext();
    }
    $node->setNext($node->getNext());
    $node->setData($node->getNext()->getData());
  }
   /**
  *@author MzXy
  *@param 遍歷
  * 
  */
  public function get()
  {
    $node=$this->header;
    if($node->getNext()==null){
      print("數(shù)據(jù)集為空!");
      return;
    }
    while($node->getNext()!=null)
    {
      print('['.$node->getNext()->getData().'] -> ');
      if($node->getNext()->getNext()==null){break;}
      $node=$node->getNext();
    }
  }
   /**
  *@author MzXy
  *@param $data--要訪問(wèn)的節(jié)點(diǎn)的數(shù)據(jù)
  * @param 此方法只是演示不具有實(shí)際意義
  * 
  */
  public function getAt($data)
  {
    $node=$this->header->getNext();
  if($node->getNext()==null){
      print("數(shù)據(jù)集為空!");
      return;
    }
    while($node->getData()!=$data)
    {
      if($node->getNext()==null){break;}
      $node=$node->getNext();
    }
    return $node->getData();    
  }
   /**
  *@author MzXy
  *@param $value--需要更新的節(jié)點(diǎn)的原數(shù)據(jù) --$initial---更新后的數(shù)據(jù)
  * 
  */
  public function update($initial,$value)
  {
     $node=$this->header->getNext();
 if($node->getNext()==null){
     print("數(shù)據(jù)集為空!");
      return;
    }
    while($node->getData()!=$data)
    {
      if($node->getNext()==null){break;}
      $node=$node->getNext();
    }
 $node->setData($initial);   
  }
}
$lists = new LinkList();
$lists -> add(1);
$lists -> add(2);
$lists -> get();
echo '<pre>';
print_r($lists);
echo '</pre>';
?>

反轉(zhuǎn)鏈表操作：

1. 常用的方法：左右交替，下一個(gè)結(jié)點(diǎn)保存，上一個(gè)結(jié)點(diǎn)替換該結(jié)點(diǎn)的下個(gè)結(jié)點(diǎn)。實(shí)現(xiàn)替換。

代碼：

function ReverseList($pHead)
{
  // write code here
  if($pHead == null || $pHead->next == null){
    return $pHead;
  }
  $p = $pHead;
  $q = $pHead->next;
  $pHead->next = null;//$pHead 變?yōu)槲仓羔?
  while($q){
    $r = $q->next;
    $q->next = $p;
    $p = $q;
    $q = $r;
  }
  return $p;
}

2. 使用遞歸方法。三個(gè)結(jié)點(diǎn)，頭結(jié)點(diǎn)，首節(jié)點(diǎn)，第二個(gè)結(jié)點(diǎn)。把首節(jié)點(diǎn)后面的所有結(jié)點(diǎn)當(dāng)成第二個(gè)結(jié)點(diǎn)，依次循環(huán)下去，由于要滿足 $pHead != null || $pHead->next != null ；所以不會(huì)出現(xiàn)遍歷不完的情況

function ReverseList($pHead)
{
  // write code here
  if($pHead == null || $pHead->next == null){
    return $pHead;
  }
  $res = ReverseList($pHead->next);
  $pHead->next->next = $pHead;
  $pHead->next = null;
  return $res;
}

更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計(jì)算法總結(jié)》、《php字符串(string)用法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學(xué)運(yùn)算技巧總結(jié)》

希望本文所述對(duì)大家PHP程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: