利用PHP實現(xiàn)遞歸刪除鏈表元素的方法示例

更新時間：2020年10月23日 08:30:27 作者：愛因詩賢

這篇文章主要給大家介紹了關于如何利用PHP實現(xiàn)遞歸刪除鏈表元素的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧

前言

這篇文章介紹一下遞歸，遞歸的本質是將原來的問題轉化為更小的同一個問題，解決這些更小問題的過程。下面通過兩個遞歸的例子幫助學習對遞歸的理解。

1.遞歸數(shù)組求和

例如某個數(shù)組 $arr = [1,2,3,4,5,6,7,8,9,10]; 需要求和，通過實現(xiàn)遞歸函數(shù)對數(shù)組求和來幫助學習對遞歸的理解。

1.1 輸出文件 output_recursion.php

<?php
require 'ArrayRecursion.php';
/**
 * 遞歸實現(xiàn)數(shù)組求和
 */
$arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
echo ArrayRecursion::recursionSum($arr);

1.2 ArrayRecursion 類

這是一個實現(xiàn)數(shù)組遞歸求和的代碼，其中 recursionSum() 是一個遞歸函數(shù)，相當于把求和過程轉化為更小的求和，最終實現(xiàn)想要的結果：

<?php
/**
 * 使用遞歸對數(shù)組求和 方便對遞歸的理解
 * 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：這個求和過程僅僅只是幫助學習遞歸思想，實際求和可以直接遍歷數(shù)組。

2.遞歸刪除鏈表某個元素

例如某個鏈表 10->9->8->99->7->99->6->5->99->4->3->2->1->null 需要刪除其中值等于 99 的元素，可以通過實現(xiàn)遞歸來得到刪除指定元素的效果。

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 節(jié)點對象信息，可以使用 setHead() 改變 head，另外下面定義了一個鏈表節(jié)點類 Node：

<?php
/**
 * 鏈表的實現(xiàn)
 * 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 節(jié)點指向插入節(jié)點，插入節(jié)點的 next 節(jié)點信息指向原上節(jié)點的 next 節(jié)點
    $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 "鏈表已經(jīng)是空";
      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;//節(jié)點元素
  public $next; //下個節(jié)點信息
  /**
   * 構造函數(shù) 設置節(jié)點信息
   * Node constructor.
   * @param $e
   * @param $next
   */
  public function __construct($e, $next) {
    $this->e = $e;
    $this->next = $next;
  }
}

2.3 LinkedListRecursion 類

這個類定義了一個 deleteElement(LinkedList $linkedList, $val) 方法可以將傳進的鏈表類中指定元素值的節(jié)點刪除掉(實際是節(jié)點的 next 重新指向)，recursionDelete($head, $val) 方法是一個遞歸函數(shù)，它能遞歸刪除 head 中指定元素值等于 $val 的節(jié)點刪除:

<?php
/**
 * 遞歸刪除鏈表指定元素
 * Class LinkedListRecursion
 */
class LinkedListRecursion
{
  public static function deleteElement(LinkedList $linkedList, $val) {
    $linkedList->setHead(self::recursionDelete($linkedList->getHead(), $val));
    return $linkedList;
  }
  
   /**
   * 遞歸函數(shù) 遞歸刪除鏈表元素
   * @param $head
   * @param $val
   * @return null
   */
  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實現(xiàn)遞歸刪除鏈表元素的文章就介紹到這了,更多相關PHP遞歸刪除鏈表元素內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: