欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

PHP实现链表的定义与反转功能示例

程序员文章站 2022-05-25 16:51:02
本文实例讲述了php实现链表的定义与反转功能。分享给大家供大家参考,具体如下: php定义链表及添加、移除、遍历等操作:

本文实例讲述了php实现链表的定义与反转功能。分享给大家供大家参考,具体如下:

php定义链表及添加、移除、遍历等操作:

<?php
class node
{
  private $data;//节点数据
  private $next;//下一节点
 
  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;//头节点
  private $size;//长度
  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--要添加节点的数据
  * 
  */
  public function add($data)
  {
    $node=$this->header;
    while($node->getnext()!=null)
    {
      $node=$node->getnext();
    }
    $node->setnext(new node($data,null));
  }
   /**
  *@author mzxy
  *@param $data--要移除节点的数据
  * 
  */
  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("数据集为空!");
      return;
    }
    while($node->getnext()!=null)
    {
      print('['.$node->getnext()->getdata().'] -> ');
      if($node->getnext()->getnext()==null){break;}
      $node=$node->getnext();
    }
  }
   /**
  *@author mzxy
  *@param $data--要访问的节点的数据
  * @param 此方法只是演示不具有实际意义
  * 
  */
  public function getat($data)
  {
    $node=$this->header->getnext();
  if($node->getnext()==null){
      print("数据集为空!");
      return;
    }
    while($node->getdata()!=$data)
    {
      if($node->getnext()==null){break;}
      $node=$node->getnext();
    }
    return $node->getdata();    
  }
   /**
  *@author mzxy
  *@param $value--需要更新的节点的原数据 --$initial---更新后的数据
  * 
  */
  public function update($initial,$value)
  {
     $node=$this->header->getnext();
 if($node->getnext()==null){
     print("数据集为空!");
      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>';
?>

反转链表操作:

1. 常用的方法:左右交替,下一个结点保存,上一个结点替换该结点的下个结点。实现替换。

代码:

function reverselist($phead)
{
  // write code here
  if($phead == null || $phead->next == null){
    return $phead;
  }
  $p = $phead;
  $q = $phead->next;
  $phead->next = null;//$phead 变为尾指针
  while($q){
    $r = $q->next;
    $q->next = $p;
    $p = $q;
    $q = $r;
  }
  return $p;
}

2. 使用递归方法。三个结点,头结点,首节点,第二个结点。把首节点后面的所有结点当成第二个结点,依次循环下去,由于要满足 $phead != null || $phead->next != null ;所以不会出现遍历不完的情况

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;
}

更多关于php相关内容感兴趣的读者可查看本站专题:《php数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《php数组(array)操作技巧大全》、《php常用遍历算法与技巧总结》及《php数学运算技巧总结

希望本文所述对大家php程序设计有所帮助。