利用PHP实现递归删除链表元素的方法示例
前言
这篇文章介绍一下 递归,递归的本质是将原来的问题转化为更小的同一个问题,解决这些更小问题的过程。狼蚁网站SEO优化通过两个递归的例子帮助学习对递归的理解。
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,另外狼蚁网站SEO优化定义了一个链表节点类 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; } /** * 递归函数 递归删除链表元素 * @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; } } } }
代码仓库 :...
总结
到此这篇关于利用PHP实现递归删除链表元素的文章就介绍到这了,更多相关PHP递归删除链表元素内容请搜索狼蚁SEO以前的文章或继续浏览狼蚁网站SEO优化的相关文章希望大家以后多多支持狼蚁SEO!
编程语言
- 机械手焊接机器人编程 机械手焊接设备编程
- vb数据库编程实例,vb做数据库
- tiobe世界编程语言排行榜,全球编程语言排行
- 成都java编程培训 成都it编程培训中心
- 编程基础培训,编程基础知识培训
- flash游戏编程基础教程,flash游戏开发教程
- 不会英语能学编程吗 不会英语可以学程序员吗
- 爱心代码编程C语言 爱心代码编程c语言公式
- c语言编程学习入门 c语言编程快速入门
- 西门子plc编程培训 西门子plc编程培训班
- 哪里可以学编程 台州哪里可以学编程
- 少儿编程哪个好 少儿编程哪个品牌好
- 编程是什么意思,图形编程是什么意思
- c语言编程软件下载,c语言编程软件在哪下载
- java编程软件下载,java编程下载手机版
- ug编程培训学校,ug编程培训教程