添加删除元素_PHP 实现递归删除链表元素

柔光的暖阳◎ 2022-11-19 11:23 179阅读 0赞

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

### 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
     *///将链表对象传入一个能删除指定元素的方法，如 99echo 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-poetry/data-structure

扫码关注爱因诗贤

![4ef1ea97b7c46e977e4473b2c79a8a40.png][]

[4ef1ea97b7c46e977e4473b2c79a8a40.png]: /images/20221119/c604087803a54ae9a228943c6be8fe45.png