使用递归算法删除不带头结点单链表L中所有值为X的结点

  • 2019-07-21 17:08:06
  • 3,562 次阅读
  • 稿源:天马行空

设计一个递归算法,删除不带头结点的单链表L中所有值为X的结点。

根据题目中,删除单链表L中所有值为X的结点,也就把if(data == x)的值删掉。本题的重点是考察递归算法,同时要求单链表不带头结点。

那么,下面具体看看使用递归算法是如何实现的。

一、递归算法代码

void Del_X_recursion(Linklist &L,int X)
 {
	if(L == NULL) return; // 递归函数出口return;
	if(L->data !=X) // 若L所指结点的值不为X
	{
		Del_X_recursion(L->next,X);// 递归调用
		return; //递归出口return;
	}
	if(L->data ==X) 
	{
	LNode *p;
	p=L;  // p指向要删除的结点
	L=L->next;
	delete p;
	Del_X_recursion(L,X);// 递归调用
	}
 }

二、递归代码图文详解

使用递归算法删除不带头结点单链表L中所有值为X的结点

如上图,假如有n个结点,从第一个结点开始遍历,若我们第一个结点为X,那么要完成删除链表中所有值为X的结点,
相当于第一个结点已经知道了,后面的n-1结点也按照同样的方法操作就可以了。

recursion-image1

如上图,假如第一个结点要留下,后面的n-1结点使用Del_X_recursion(L->next,X)递归函数执行完毕,在执行过程中肯定有留下来的,也有删掉的,但我们不必知道里面具体是如何实现的。只要后面n-1个结点执行完毕后,这个递归函数就可以结束了。
然后从最里层返回到上一层,一直return第一层,程序结束。出口函数结束。

最后是删除X结点的操作,如下图

recursion image2
recursion image3

(1)p=L;假如p指针指向的第一个结点为X,这是我们要删除的结点;

(2)L=L->next;接下来L指向下一个结点

(3)delete p;删除X结点

最后,再次调用Del_X_recursion(L,X);递归函数,从L开始,把其作为第一个结点递归的调用。一直将所有的X删除为止。

喜欢 1

文章评论 (0)

表情

大眼 可爱 大笑 坏笑 害羞 发怒 折磨 快哭了 大哭 白眼 晕 流汗 困 腼腆 惊讶 憨笑 色 得意 骷髅 囧 睡觉 眨眼 亲亲 疑问 闭嘴 难过 淡定 抗议 鄙视 猪头