当前位置:首页 > PHP教程 > php高级应用 > 列表

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

发布:smiling 来源: PHP粉丝网  添加日期:2021-09-25 15:42:50 浏览: 评论:0 

这篇文章主要介绍了PHP实现链表的定义与反转功能,结合实例形式分析了PHP链表的基本定义、添加、移除、遍历以及两种反转操作相关实现技巧,需要的朋友可以参考下。

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

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

  1. <?php 
  2. class Node 
  3.   private $Data;//节点数据 
  4.   private $Next;//下一节点 
  5.    
  6.   public function setData($value){ 
  7.     $this->Data=$value
  8.   } 
  9.    
  10.   public function setNext($value){ 
  11.      $this->Next=$value
  12.   }   
  13.    
  14.   public function getData(){ 
  15.     return $this->Data; 
  16.   } 
  17.    
  18.   public function getNext(){ 
  19.     return $this->Next; 
  20.   } 
  21.    
  22.   public function __construct($data,$next){ 
  23.     $this->setData($data); 
  24.     $this->setNext($next); 
  25.   } 
  26. class LinkList 
  27.   private $header;//头节点 
  28.   private $size;//长度 
  29.   public function getSize() 
  30.  { 
  31.     $i=0; 
  32.     $node=$this->header; 
  33.     while($node->getNext()!=null) 
  34.     {   
  35.   $i++; 
  36.       $node=$node->getNext(); 
  37.     } 
  38.     return $i
  39.   } 
  40.    
  41.   public function setHeader($value){ 
  42.     $this->header=$value
  43.   } 
  44.    
  45.   public function getHeader(){ 
  46.     return $this->header; 
  47.   } 
  48.    
  49.   public function __construct(){ 
  50.     header("content-type:text/html; charset=utf-8"); 
  51.     $this->setHeader(new Node(null,null)); 
  52.   } 
  53.   /** 
  54.   *@author MzXy 
  55.   *@param $data--要添加节点的数据 
  56.   *  
  57.   */ 
  58.   public function add($data
  59.   { 
  60.     $node=$this->header; 
  61.     while($node->getNext()!=null) 
  62.     { 
  63.       $node=$node->getNext(); 
  64.     } 
  65.     $node->setNext(new Node($data,null)); 
  66.   } 
  67.    /** 
  68.   *@author MzXy 
  69.   *@param $data--要移除节点的数据 
  70.   *  
  71.   */ 
  72.   public function removeAt($data
  73.   { 
  74.     $node=$this->header; 
  75.     while($node->getData()!=$data
  76.     { 
  77.       $node=$node->getNext(); 
  78.     } 
  79.     $node->setNext($node->getNext()); 
  80.     $node->setData($node->getNext()->getData()); 
  81.   } 
  82.    /** 
  83.   *@author MzXy 
  84.   *@param 遍历 
  85.   *  
  86.   */ 
  87.   public function get() 
  88.   { 
  89.     $node=$this->header; 
  90.     if($node->getNext()==null){ 
  91.       print("数据集为空!"); 
  92.       return
  93.     } 
  94.     while($node->getNext()!=null) 
  95.     { 
  96.       print('['.$node->getNext()->getData().'] -> '); 
  97.       if($node->getNext()->getNext()==null){break;} 
  98.       $node=$node->getNext(); 
  99.     } 
  100.   } 
  101.    /** 
  102.   *@author MzXy 
  103.   *@param $data--要访问的节点的数据 
  104.   * @param 此方法只是演示不具有实际意义 
  105.   *  
  106.   */ 
  107.   public function getAt($data
  108.   { 
  109.     $node=$this->header->getNext(); 
  110.   if($node->getNext()==null){ 
  111.       print("数据集为空!"); 
  112.       return
  113.     } 
  114.     while($node->getData()!=$data
  115.     { 
  116.       if($node->getNext()==null){break;} 
  117.       $node=$node->getNext(); 
  118.     } 
  119.     return $node->getData();     
  120.   } 
  121.    /** 
  122.   *@author MzXy 
  123.   *@param $value--需要更新的节点的原数据 --$initial---更新后的数据 
  124.   *  
  125.   */ 
  126.   public function update($initial,$value
  127.   { 
  128.      $node=$this->header->getNext(); 
  129.  if($node->getNext()==null){ 
  130.      print("数据集为空!"); 
  131.       return
  132.     } 
  133.     while($node->getData()!=$data
  134.     { 
  135.       if($node->getNext()==null){break;} 
  136.       $node=$node->getNext(); 
  137.     } 
  138.  $node->setData($initial);    
  139.   } 
  140. $lists = new LinkList(); 
  141. $lists -> add(1); 
  142. $lists -> add(2); 
  143. $lists -> get(); 
  144. echo '<pre>'
  145. print_r($lists); 
  146. echo '</pre>'
  147. ?> 

反转链表操作:

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

代码:

  1. function ReverseList($pHead
  2.   // write code here 
  3.   if($pHead == null || $pHead->next == null){ 
  4.     return $pHead
  5.   } 
  6.   $p = $pHead
  7.   $q = $pHead->next; 
  8.   $pHead->next = null;//$pHead 变为尾指针 
  9.   while($q){ 
  10.     $r = $q->next; 
  11.     $q->next = $p
  12.     $p = $q
  13.     $q = $r
  14.   } 
  15.   return $p

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

  1. function ReverseList($pHead
  2.   // write code here 
  3.   if($pHead == null || $pHead->next == null){ 
  4.     return $pHead
  5.   } 
  6.   $res = ReverseList($pHead->next); 
  7.   $pHead->next->next = $pHead
  8.   $pHead->next = null; 
  9.   return $res
  10. }

Tags: PHP链表定义 PHP链表反转

分享到: