1. 首页
  2. PHP
  3. PHP 实现递归删除链表元素

PHP 实现递归删除链表元素

码农天地 -
PHP 实现递归删除链表元素

这篇文件介绍一下 递归，递归的本质是将原来的问题转化为更小的同一个问题，解决这些更小问题的过程。下面通过两个递归的例子帮助学习对递归的理解。

1.递归数组求和

例如某个数组 $arr = [1,2,3,4,5,6,7,8,9,10]; 需要求和，通过实现递归函数对数组求和来帮助学习对递归的理解。

1.1 输出文件 output_recursion.php
<?php
require 'ArrayRecursion.php';
/**
 * 递归实现数组求和
 */
$arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
echo ArrayRecursion::recursionSum($arr);
1.2 ArrayRecursion 类

这是一个实现数组递归求和的代码，其中 recursionSum() 是一个递归函数，相当于把求和过程转化为更小的求和，最终实现想要的结果：

<?php
/**
 * 使用递归对数组求和 方便对递归的理解
 * Class ArrayRecursion
 */
class ArrayRecursion
{
    public static function sum(array $arr) {
        return self::recursionSum($arr);
    }
    public static function recursionSum(array $arr, $i = 0) {
        if (count($arr) == $i) {
            return 0;
        }
        return $arr[$i] + self::recursionSum($arr, $i + 1);
    }
}
Tips：这个求和过程仅仅只是帮助学习递归思想，实际求和可以直接遍历数组。2.递归删除链表某个元素

例如某个链表 10->9->8->99->7->99->6->5->99->4->3->2->1->null 需要删除其中值等于 99 的元素，可以通过实现递归来得到删除指定元素的效果。

2.1 输出文件 output_recursion.php
<?php
require 'LinkedList.php';
require 'LinkedListRecursion.php';
/**
 * 首先实例化一个链表，向链表中添加50个元素
 */
$linkedList = new LinkedList();
for ($i = 0; $i < 50; $i++) {
    if ($i % 7 == 0) {
        $linkedList->addFirst(99);
    } else {
        $linkedList->addFirst($i);
    }
}
echo $linkedList->toString();
/**打印链表中元素
 * 99->48->47->46->45->44->43->99->41->40->39->
 * 38->37->36->99->34->33->32->31->30->29->99->27->
 * 26->25->24->23->22->99->20->19->18->17->16->15->
 * 99->13->12->11->10->9->8->99->6->5->4->3->2->1->99->null
 */
//将链表对象传入一个能删除指定元素的方法，如 99
echo LinkedListRecursion::deleteElement($linkedList, 99)->toString();
/**打印
 * 48->47->46->45->44->43->41->40->
 * 39->38->37->36->34->33->32->31->
 * 30->29->27->26->25->24->23->22->
 * 20->19->18->17->16->15->13->12->
 * 11->10->9->8->6->5->4->3->2->1->null
 */
2.2 LinkedList & Node 链表类

这是一个链表类，可以使用 addFirst() 方法向链表头部添加元素，可使用 getHead() 获取链表 head 节点对象信息，可以使用 setHead() 改变 head，另外下面定义了一个链表节点类 Node：

<?php
/**
 * 链表的实现
 * Class LinkedList
 */
class LinkedList
{
    private $dummyHead;
    private $size;
    /**
     * 初始化链表 null->null
     * LinkedList constructor.
     */
    public function __construct() {
        $this->dummyHead = new Node(null, null);
        $this->size = 0;
    }
    /**
     * 获取链表大小
     * @return int
     */
    public function getSize(): int {
        return $this->size;
    }
    /**
     * 判断链表是否为空
     * @return bool
     */
    public function isEmpty(): bool {
        return $this->size == 0;
    }
    /**
     * 在链表的第 index 位置添加元素
     * @param int $index
     * @param $e
     */
    public function add(int $index, $e): void {
        if ($index < 0 || $index > $this->size) {
            echo "索引范围错误";
            exit;
        }
        $prve = $this->dummyHead;
        for ($i = 0; $i < $index; $i++) {
            $prve = $prve->next;
        }
        //将上插入位置的上一个位置的 next 节点指向插入节点，插入节点的 next 节点信息指向原上节点的 next 节点
        $prve->next = new Node($e, $prve->next);
        $this->size++;
    }
    /**
     * 向链表开头添加元素
     * @param $e
     */
    public function addFirst($e): void {
        $this->add(0, $e);
    }
    /**
     * 向链表末尾添加元素
     * @param $e
     */
    public function addLast($e): void {
        $this->add($this->size, $e);
    }
    /**
     * 获取链表第 index 位置元素
     * @param $index
     */
    public function get($index) {
        if ($index < 0 || $index > $this->size) {
            echo "索引范围错误";
            exit;
        }
        $node = $this->dummyHead;
        for ($i = 0; $i < $index + 1; $i++) {
            $node = $node->next;
        }
        return $node->e;
    }
    /**
     * 获取链表第一个元素
     * @return mixed
     */
    public function getFirst() {
        return $this->get(0);
    }
    /**
     * 获取链表最后一个元素
     * @return mixed
     */
    public function getLast() {
        return $this->get($this->size - 1);
    }
    /**
     * 修改链表中第 index 位置元素值
     * @param $index
     * @param $e
     */
    public function update($index, $e) {
        if ($index < 0 || $index > $this->size) {
            echo "索引范围错误";
            exit;
        }
        $node = $this->dummyHead;
        for ($i = 0; $i < $index + 1; $i++) {
            $node = $node->next;
        }
        $node->e = $e;
    }
    /**
     * 判断链表中是否存在某个元素
     * @param $e
     * @return bool
     */
    public function contains($e): bool {
        for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {
            if ($node->e == $e) {
                return true;
            }
        }
        return true;
    }
    /**
     * 删除链表中第 index 位置元素
     * @param $index
     */
    public function remove($index) {
        if ($index < 0 || $index > $this->size) {
            echo "索引范围错误";
            exit;
        }
        if ($this->size == 0) {
            echo "链表已经是空";
            exit;
        }
        $prve = $this->dummyHead;
        for ($i = 0; $i < $index; $i++) {
            $prve = $prve->next;
        }
        $node = $prve->next;
        $prve->next = $node->next;
        $this->size--;
        return $node->e;
    }
    /**
     * 删除链表头元素
     */
    public function removeFirst() {
        return $this->remove(0);
    }
    /**
     * 删除链表末尾元素
     */
    public function removeLast() {
        return $this->remove($this->size - 1);
    }
    /**
     * 获取头结点信息
     * @return mixed
     */
    public function getHead() {
        return $this->dummyHead->next;
    }
    /**
     * 设置头
     * @param Node $head
     */
    public function setHead(Node $head) {
        $this->dummyHead->next = $head;
    }
    /**
     * 链表元素转化为字符串显示
     * @return string
     */
    public function toString(): string {
        $str = "";
        for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {
            $str .= $node->e . "->";
        }
        return $str . "null";
    }
}
class Node
{
    public $e;//节点元素
    public $next; //下个节点信息
    /**
     * 构造函数 设置节点信息
     * Node constructor.
     * @param $e
     * @param $next
     */
    public function __construct($e, $next) {
        $this->e = $e;
        $this->next = $next;
    }
}
2.3 LinkedListRecursion 类

这个类定义了一个 deleteElement(LinkedList $linkedList, $val) 方法可以将传进的链表类中指定元素值的节点删除掉(实际是节点的 next 重新指向)，recursionDelete($head, $val) 方法是一个递归函数，它能递归删除 head 中指定元素值等于 $val 的节点删除:

<?php
/**
 * 递归删除链表指定元素
 * Class LinkedListRecursion
 */
class LinkedListRecursion
{
    public static function deleteElement(LinkedList $linkedList, $val) {
        $linkedList->setHead(self::recursionDelete($linkedList->getHead(), $val));
        return $linkedList;
    }
    private static function recursionDelete($head, $val) {
        if ($head == null) {
            return null;
        } else {
            if ($head->e == $val) {
                return self::recursionDelete($head->next, $val);
            } else {
                $head->next = self::recursionDelete($head->next, $val);
                return $head;
            }
        }
    }
}

代码仓库 ：https://gitee.com/love-for-po...

扫码关注爱因诗贤公众号

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。

php介绍

PHP即“超文本预处理器”，是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言，与C语言类似，是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习，使用广泛，主要适用于Web开发领域。
更多关于php的阅读
上一篇： PHP使用栈实现队列
下一篇： php ie下载文件名乱码怎么办

Tags 标签

php算法程序员

扩展阅读

隐藏apache版本信息
2018-09-30 10:56:15 []
CentOS 6.5安装php5.6
2018-09-30 11:36:53 []
PHP版ZIP压缩解压类库
2018-12-22 13:11:00 []
CentOS7.2安装 PHP7.3.4 操作详细教程
2020-06-28 19:09:43 []
PHP 设置脚本超时时间、PHP脚本内存限制设置
2020-06-28 19:09:43 []
PHP 函数filesize获取文件大小错误，一直不变
2020-06-28 19:09:43 []
Linux php: command not found
2020-02-05 01:30:13 []
php 缓冲区 buffer 原理
2020-06-28 19:09:43 []
PHP中三种设置脚本最大执行时间的方法
2020-06-28 19:17:34 []

加个好友，技术交流

1628738909466805.jpg

码农天地

首页 HTML/CSS WEB服务器 PHP Linux 数据库 异常报错 插件工具 美文欣赏 站长直荐
友情链接：码农天地爱厂家深圳钻石回收麦思会议

Copyright © 2019-2024| 沪ICP备19030844号-2 | SiteMap