利用PHP实现递归删除链表元素的方法示例

前言

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

1.递归数组求和

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

1.1 输出文件 output_recursion.php

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



Tips：这个求和过程仅仅只是帮助学习递归思想，实际求和可以直接遍历数组。
2.递归删除链表某个元素
例如某个链表 10->9->8->99->7->99->6->5->99->4->3->2->1->null 需要删除其中值等于 99 的元素，可以通过实现递归来得到删除指定元素的效果。
2.1 输出文件 output_recursion.php

addFirst(99);
  } else {
    $linkedList->addFirst($i);
  }
}
echo $linkedList->toString();

//将链表对象传入一个能删除指定元素的方法，如 99
echo linkedListRecursion::deleteElement($linkedList, 99)->toString();


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

dummyHead = new Node(null, null);
    $this->size = 0;
  }
  
  public function getSize(): int {
    return $this->size;
  }
  
  public function isEmpty(): bool {
    return $this->size == 0;
  }
  
  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++;
  }
  
  public function addFirst($e): void {
    $this->add(0, $e);
  }
  
  public function addLast($e): void {
    $this->add($this->size, $e);
  }
  
  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;
  }
  
  public function getFirst() {
    return $this->get(0);
  }
  
  public function getLast() {
    return $this->get($this->size - 1);
  }
  
  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;
  }
  
  public function contains($e): bool {
    for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {
      if ($node->e == $e) {
 return true;
      }
    }
    return true;
  }
  
  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);
  }
  
  public function getHead() {
    return $this->dummyHead->next;
  }
  
  public function setHead(Node $head) {
    $this->dummyHead->next = $head;
  }
  
  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; //下个节点信息
  
  public function __construct($e, $next) {
    $this->e = $e;
    $this->next = $next;
  }
}

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

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...
总结
到此这篇关于利用PHP实现递归删除链表元素的文章就介绍到这了,更多相关PHP递归删除链表元素内容请搜索考高分网以前的文章或继续浏览下面的相关文章希望大家以后多多支持考高分网！