利用PHP實(shí)現(xiàn)遞歸刪除鏈表元素的方法示例
更新時(shí)間：2020年10月23日 08:30:27 作者：愛(ài)因詩(shī)賢
這篇文章主要給大家介紹了關(guān)于如何利用PHP實(shí)現(xiàn)遞歸刪除鏈表元素的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
前言
這篇文章介紹一下 遞歸，遞歸的本質(zhì)是將原來(lái)的問(wèn)題轉(zhuǎn)化為更小的同一個(gè)問(wèn)題，解決這些更小問(wèn)題的過(guò)程。下面通過(guò)兩個(gè)遞歸的例子幫助學(xué)習(xí)對(duì)遞歸的理解。
1.遞歸數(shù)組求和
例如某個(gè)數(shù)組 $arr = [1,2,3,4,5,6,7,8,9,10]; 需要求和，通過(guò)實(shí)現(xiàn)遞歸函數(shù)對(duì)數(shù)組求和來(lái)幫助學(xué)習(xí)對(duì)遞歸的理解。
1.1 輸出文件 output_recursion.php
<?php require 'ArrayRecursion.php'; /** * 遞歸實(shí)現(xiàn)數(shù)組求和 */ $arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; echo ArrayRecursion::recursionSum($arr);
1.2 ArrayRecursion 類(lèi)
這是一個(gè)實(shí)現(xiàn)數(shù)組遞歸求和的代碼，其中 recursionSum() 是一個(gè)遞歸函數(shù)，相當(dāng)于把求和過(guò)程轉(zhuǎn)化為更小的求和，最終實(shí)現(xiàn)想要的結(jié)果：
<?php
/**
* 使用遞歸對(duì)數(shù)組求和 方便對(duì)遞歸的理解
* 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：這個(gè)求和過(guò)程僅僅只是幫助學(xué)習(xí)遞歸思想，實(shí)際求和可以直接遍歷數(shù)組。
2.遞歸刪除鏈表某個(gè)元素
例如某個(gè)鏈表 10->9->8->99->7->99->6->5->99->4->3->2->1->null 需要?jiǎng)h除其中值等于 99 的元素，可以通過(guò)實(shí)現(xiàn)遞歸來(lái)得到刪除指定元素的效果。
2.1 輸出文件 output_recursion.php
<?php
require 'LinkedList.php';
require 'LinkedListRecursion.php';
/**
* 首先實(shí)例化一個(gè)鏈表，向鏈表中添加50個(gè)元素
*/
$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
*/
//將鏈表對(duì)象傳入一個(gè)能刪除指定元素的方法，如 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 鏈表類(lèi)
這是一個(gè)鏈表類(lèi)，可以使用 addFirst() 方法向鏈表頭部添加元素，可使用 getHead() 獲取鏈表 head 節(jié)點(diǎn)對(duì)象信息，可以使用 setHead() 改變 head，另外下面定義了一個(gè)鏈表節(jié)點(diǎn)類(lèi) Node：
<?php
/**
* 鏈表的實(shí)現(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 "索引范圍錯(cuò)誤";
exit;
}
$prve = $this->dummyHead;
for ($i = 0; $i < $index; $i++) {
$prve = $prve->next;
}
//將上插入位置的上一個(gè)位置的 next 節(jié)點(diǎn)指向插入節(jié)點(diǎn)，插入節(jié)點(diǎn)的 next 節(jié)點(diǎn)信息指向原上節(jié)點(diǎn)的 next 節(jié)點(diǎn)
$prve->next = new Node($e, $prve->next);
$this->size++;
}
/**
* 向鏈表開(kāi)頭添加元素
* @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 "索引范圍錯(cuò)誤";
exit;
}
$node = $this->dummyHead;
for ($i = 0; $i < $index + 1; $i++) {
$node = $node->next;
}
return $node->e;
}
/**
* 獲取鏈表第一個(gè)元素
* @return mixed
*/
public function getFirst() {
return $this->get(0);
}
/**
* 獲取鏈表最后一個(gè)元素
* @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 "索引范圍錯(cuò)誤";
exit;
}
$node = $this->dummyHead;
for ($i = 0; $i < $index + 1; $i++) {
$node = $node->next;
}
$node->e = $e;
}
/**
* 判斷鏈表中是否存在某個(gè)元素
* @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 "索引范圍錯(cuò)誤";
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);
}
/**
* 獲取頭結(jié)點(diǎn)信息
* @return mixed
*/
public function getHead() {
return $this->dummyHead->next;
}
/**
* 設(shè)置頭
* @param Node $head
*/
public function setHead(Node $head) {
$this->dummyHead->next = $head;
}
/**
* 鏈表元素轉(zhuǎn)化為字符串顯示
* @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é)點(diǎn)元素
public $next; //下個(gè)節(jié)點(diǎn)信息
/**
* 構(gòu)造函數(shù) 設(shè)置節(jié)點(diǎn)信息
* Node constructor.
* @param $e
* @param $next
*/
public function __construct($e, $next) {
$this->e = $e;
$this->next = $next;
}
}
2.3 LinkedListRecursion 類(lèi)
這個(gè)類(lèi)定義了一個(gè) deleteElement(LinkedList $linkedList, $val) 方法可以將傳進(jìn)的鏈表類(lèi)中指定元素值的節(jié)點(diǎn)刪除掉(實(shí)際是節(jié)點(diǎn)的 next 重新指向)，recursionDelete($head, $val) 方法是一個(gè)遞歸函數(shù)，它能遞歸刪除 head 中指定元素值等于 $val 的節(jié)點(diǎn)刪除:
<?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;
}
}
}
}
代碼倉(cāng)庫(kù) ：https://gitee.com/love-for-po...
總結(jié)
到此這篇關(guān)于利用PHP實(shí)現(xiàn)遞歸刪除鏈表元素的文章就介紹到這了,更多相關(guān)PHP遞歸刪除鏈表元素內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Javascript 拖拽雛形(逐行分析代碼，讓你輕松了拖拽的原理)
這篇文章主要介紹了Javascript 拖拽雛形(逐行分析代碼，讓你輕松了拖拽的原理),需要的朋友可以參考下2015-01-01
JavaScript生成驗(yàn)證碼并實(shí)現(xiàn)驗(yàn)證功能
這篇文章主要介紹了JavaScript生成驗(yàn)證碼并實(shí)現(xiàn)驗(yàn)證功能的相關(guān)資料,代碼簡(jiǎn)單易懂，非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友可以參考下2016-09-09
這篇文章主要介紹了NestJs 靜態(tài)目錄配置，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03
javascript元素動(dòng)態(tài)創(chuàng)建實(shí)現(xiàn)方法
這篇文章主要介紹了javascript元素動(dòng)態(tài)創(chuàng)建實(shí)現(xiàn)方法,涉及javascript操作元素的相關(guān)技巧,需要的朋友可以參考下2015-05-05
ES6學(xué)習(xí)筆記之正則表達(dá)式和字符串正則方法分析
這篇文章主要介紹了ES6學(xué)習(xí)筆記之正則表達(dá)式和字符串正則方法,結(jié)合實(shí)例形式對(duì)比分析了ES5與ES6正則操作的常用函數(shù)功能與用法區(qū)別,需要的朋友可以參考下2017-04-04
這篇文章主要介紹了ES6 十大特性的相關(guān)資料，幫助大家更好的理解和使用JavaScript，感興趣的朋友可以了解下2020-12-12
JavaScript腳本性能優(yōu)化注意事項(xiàng)
本文總結(jié)了我在JavaScript編程中所找到的提高JavaScript運(yùn)行性能的一些方法，其實(shí)這些經(jīng)驗(yàn)都基于幾條原則2008-11-11
在一門(mén)編程語(yǔ)言中，布爾操作符的重要性堪比相等操作符。如果沒(méi)有測(cè)試兩個(gè)值關(guān)系的能力，那么諸如if...else和循環(huán)之類(lèi)的語(yǔ)句就不會(huì)有用武之地了。布爾操作符一共有3個(gè)： 非、與、或2012-08-08
JavaScript對(duì)象的四種創(chuàng)建方法
這篇文章主要介紹了JavaScript對(duì)象的四種創(chuàng)建方法，首先我們通過(guò)確定一個(gè)對(duì)象的屬性和方法展開(kāi)主題相關(guān)內(nèi)容，需要的小伙伴可以參考一下2022-08-08
JS小功能(onmouseover實(shí)現(xiàn)選擇月份)實(shí)例代碼
這篇文章主要介紹了onmouseover實(shí)現(xiàn)選擇月份實(shí)例代碼，有需要的朋友可以參考一下2013-11-11