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

2023-07-13 10:27:04 244
前言
这篇文章介绍一下递归，递归的本质是将原来的问题转化为更小的同一个问题，解决这些更小问题的过程。下面通过两个递归的例子帮助学习对递归的理解。
1.递归数组求和
例如某个数组$arr=[1,2,3,4,5,6,7,8,9,10];需要求和，通过实现递归函数对数组求和来帮助学习对递归的理解。
1.1输出文件output_recursion.php

1.2ArrayRecursion类
这是一个实现数组递归求和的代码，其中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->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
echoLinkedListRecursion::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.2LinkedList&Node链表类
这是一个链表类，可以使用addFirst()方法向链表头部添加元素，可使用getHead()获取链表head节点对象信息，可以使用setHead()改变head，另外下面定义了一个链表节点类Node：
null
*LinkedListconstructor.
*/
publicfunction__construct(){
$this->dummyHead=newNode(null,null);
$this->size=0;
}
/**
*获取链表大小
*@returnint
*/
publicfunctiongetSize():int{
return$this->size;
}
/**
*判断链表是否为空
*@returnbool
*/
publicfunctionisEmpty():bool{
return$this->size==0;
}
/**
*在链表的第index位置添加元素
*@paramint$index
*@param$e
*/
publicfunctionadd(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=newNode($e,$prve->next);
$this->size++;
}
/**
*向链表开头添加元素
*@param$e
*/
publicfunctionaddFirst($e):void{
$this->add(0,$e);
}
/**
*向链表末尾添加元素
*@param$e
*/
publicfunctionaddLast($e):void{
$this->add($this->size,$e);
}
/**
*获取链表第index位置元素
*@param$index
*/
publicfunctionget($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;
}
/**
*获取链表第一个元素
*@returnmixed
*/
publicfunctiongetFirst(){
return$this->get(0);
}
/**
*获取链表最后一个元素
*@returnmixed
*/
publicfunctiongetLast(){
return$this->get($this->size-1);
}
/**
*修改链表中第index位置元素值
*@param$index
*@param$e
*/
publicfunctionupdate($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
*@returnbool
*/
publicfunctioncontains($e):bool{
for($node=$this->dummyHead->next;$node!=null;$node=$node->next){
if($node->e==$e){
returntrue;
}
}
returntrue;
}
/**
*删除链表中第index位置元素
*@param$index
*/
publicfunctionremove($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;
}
/**
*删除链表头元素
*/
publicfunctionremoveFirst(){
return$this->remove(0);
}
/**
*删除链表末尾元素
*/
publicfunctionremoveLast(){
return$this->remove($this->size-1);
}
/**
*获取头结点信息
*@returnmixed
*/
publicfunctiongetHead(){
return$this->dummyHead->next;
}
/**
*设置头
*@paramNode$head
*/
publicfunctionsetHead(Node$head){
$this->dummyHead->next=$head;
}
/**
*链表元素转化为字符串显示
*@returnstring
*/
publicfunctiontoString():string{
$str="";
for($node=$this->dummyHead->next;$node!=null;$node=$node->next){
$str.=$node->e."->";
}
return$str."null";
}
}
classNode
{
public$e;//节点元素
public$next;//下个节点信息
/**
*构造函数设置节点信息
*Nodeconstructor.
*@param$e
*@param$next
*/
publicfunction__construct($e,$next){
$this->e=$e;
$this->next=$next;
}
}
2.3LinkedListRecursion类
这个类定义了一个deleteElement(LinkedList$linkedList,$val)方法可以将传进的链表类中指定元素值的节点删除掉(实际是节点的next重新指向)，recursionDelete($head,$val)方法是一个递归函数，它能递归删除head中指定元素值等于$val的节点删除:
setHead(self::recursionDelete($linkedList->getHead(),$val));
return$linkedList;
}

/**
*递归函数递归删除链表元素
*@param$head
*@param$val
*@returnnull
*/
privatestaticfunctionrecursionDelete($head,$val){
if($head==null){
returnnull;
}else{
if($head->e==$val){
returnself::recursionDelete($head->next,$val);
}else{
$head->next=self::recursionDelete($head->next,$val);
return$head;
}
}
}
}
代码仓库：https://gitee.com/love-for-po...
总结
到此这篇关于利用PHP实现递归删除链表元素的文章就介绍到这了,更多相关PHP递归删除链表元素内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。
利用PHP实现递归删除链表元素的方法示例

热门推荐

随机推荐
