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程序设计有所帮助。

(0)

相关推荐

  • PHP从尾到头打印链表实例讲解

    题目 输入一个链表,从尾到头打印链表每个节点的值. 题解 一种是使用栈. 第二种是递归. 代码 //递归版本 function printListFromTailToHead($head) { if($head == NULL){ return []; } $arr = array(); $cur = $head; if($cur->next != null){ $arr = printListFromTailToHead($cur->next); } array_push($arr, $cu

  • 实现php删除链表中重复的结点

    删除链表中重复的结点: 定义两个指针pre和current 两个指针同时往后移动,current指针如果与后一个结点值相同,就独自往前走直到没有相等的 pre指针next直接指向current指针的后一个,把相同的都跳过 pre=linkList current=linkList while current!=null if current->data==current->next->data value=current->data while value==current->

  • PHP实现合并两个排序链表的方法

    本文实例讲述了PHP实现合并两个排序链表的方法.分享给大家供大家参考,具体如下: 问题 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 解决思路 简单的合并排序.由于两个数列本来就是递增的,所以每次将两个数列中较小的部分拿过来就可以了. 实现代码 <?php /*class ListNode{ var $val; var $next = NULL; function __construct($x){ $this->val = $x; } }*/ f

  • php数据结构之顺序链表与链式线性表示例

    本文实例讲述了php数据结构之顺序链表与链式线性表.分享给大家供大家参考,具体如下: 链表操作 1.     InitList(L):初始化链表 2.     DestroyList(L):删除连接 3.     ClearList(L):清空链表 4.     ListEmpty(L):判断是否为空 5.     ListLength(L):链表长度 6.     getElem(L,i):取出元素 7.     LocateElem(L,e):判断e是否在链表中 8.     PriorEl

  • PHP获取链表中倒数第K个节点的方法

    本文实例讲述了PHP获取链表中倒数第K个节点的方法.分享给大家供大家参考,具体如下: 问题 输入一个链表,输出该链表中倒数第k个结点. 解决思路 注意这个题目是返回节点,而不是返回值.返回值的话可以用栈来存储.返回节点则不能这样做. 设置两个指针,先让第一个指针移动k-1次.然后两个指针同时移动,当第一个指针到达最后一个节点,第二个指针就在倒数第k个节点. 注意边界:K长度可能超出链表长度,所以当第一个指针的next为空时,返回null 实现代码 <?php /*class ListNode{

  • PHP双向链表定义与用法示例

    本文实例讲述了PHP双向链表定义与用法.分享给大家供大家参考,具体如下: 由于需要对一组数据多次进行移动操作,所以写个双向链表.但对php实在不熟悉,虽然测试各个方法没啥问题,就是不知道php语言深层的这些指针和unset有什么注意的地方,贴出来让大家教育吧.效率没测试....求谅解- <?php /** * **双向链表 * @author zhiyuan12@ */ /** * 链表元素结点类 */ class Node_Element { public $pre = NULL; // 前驱

  • 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 functio

  • java 中链表的定义与使用方法

    java 中链表的定义与使用方法 Java实现链表主要依靠引用传递,引用可以理解为地址,链表的遍历多使用递归,这里我存在一个疑问同一个类的不同对象的的相同方法的方法内调用算不算递归. 这里我写的是单向链表; 实例代码: package com.example.java; public class MyLink { public static void main(String [] args){ Link l=new Link(); mytype[] la; mytype dsome=new my

  • Java 链表的定义与简单实例

     Java 链表的定义与简单实例 Java实现链表主要依靠引用传递,引用可以理解为地址,链表的遍历多使用递归,这里我存在一个疑问同一个类的不同对象的的相同方法的方法内调用算不算递归. 这里我写的是单向链表; package com.example.java; public class MyLink { public static void main(String [] args){ Link l=new Link(); mytype[] la; mytype dsome=new mytype("

  • Python实现单链表中元素的反转

    给定一个单链表,将其反转.其实很容易想到,只需要修改每个结点的指针指向:即令后一个结点指向前一个结点,并且将表头指针指向最后一个结点即可. 这个过程可以用循环实现,也可以用递归来实现. 1.用循环来实现: class LNode:     def __init__(self, elem):         self.elem = elem         self.pnext = None   def reverse(head):     if head is None or head.pnex

  • AngularJS指令与指令之间的交互功能示例

    本文实例讲述了AngularJS指令与指令之间的交互功能.分享给大家供大家参考,具体如下: 前面一篇文章<AngularJS指令与控制器之间的交互功能示例>我们了解了指令与控制器之间的交互,接下来看看指令与指令之间是如何进行交互的. 1.首先来了解一下什么是独立scope 为了更好的理解独立scope,我们来看一段代码: <div ng-controller="myController1"> <hello></hello> <hel

  • JavaWeb 中Cookie实现记住密码的功能示例

    本文主要内容: •1.什么是Cookie •2.Cookie带来的好处 •3.Cookie的主要方法 一.什么是Cookie cookie是一种WEB服务器通过浏览器在访问者的硬盘上存储信息的手段.Cookie的目的就是为用户带来方便,为网站带来增值.虽然有着许多误传,事实上Cookie并不会造成严重的安全威胁.Cookie永远不会以任何方式执行,因此也不会带来病毒或攻击你的系统.另外,由于浏览器一般只允许存放300个Cookie,每个站点最多存放20个Cookie,每个Cookie的大小限制为

  • Python实现两款计算器功能示例

    本文实例为大家分享了Python实现计算器功能示例代码,供大家参考,具体内容如下 1.简单计算器 #计算一个表达式的时候,首先肯定是先算括号里面的,再算乘除法,后算加减法 import re # 1.去括号 def remove_kuohao(expression): ''' 这是一个去除括号的函数 :param expression: 传进来的表达式 :return: 计算后的结果 ''' while True: ret = re.search(r'\([^(]*?\)',expression

  • Python实现翻转数组功能示例

    本文实例讲述了Python实现翻转数组功能.分享给大家供大家参考,具体如下: 题目描述 给定一个长度为n的整数数组a,元素均不相同,问数组是否存在这样一个片段,只将该片段翻转就可以使整个数组升序排列.其中数组片段[l,r]表示序列a[l], a[l+1], ..., a[r].原始数组为 a[1], a[2], ..., a[l-2], a[l-1], a[l], a[l+1], ..., a[r-1], a[r], a[r+1], a[r+2], ..., a[n-1], a[n], 将片段[

  • Python使用matplotlib实现绘制自定义图形功能示例

    本文实例讲述了Python使用matplotlib实现绘制自定义图形功能.分享给大家供大家参考,具体如下: 一 代码 from matplotlib.path importPath from matplotlib.patches importPathPatch import matplotlib.pyplot as plt fig, ax = plt.subplots() #定义绘图指令与控制点坐标 #其中MOVETO表示将绘制起点移动到指定坐标 #CURVE4表示使用4个控制点绘制3次贝塞尔曲

  • AngularJS实现的锚点楼层跳转功能示例

    本文实例讲述了AngularJS实现的锚点楼层跳转功能.分享给大家供大家参考,具体如下: <!DOCTYPE html> <html ng-app="myApp"> <head> <meta charset="UTF-8"> <title>anchor</title> <style> #wei div{ width:100%; height:720px; background: re

随机推荐