设计一个递归算法,删除不带头结点的单链表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);// 递归调用 } }
二、递归代码图文详解
如上图,假如有n个结点,从第一个结点开始遍历,若我们第一个结点为X,那么要完成删除链表中所有值为X的结点,相当于第一个结点已经知道了,后面的n-1结点也按照同样的方法操作就可以了。
如上图,假如第一个结点要留下,后面的n-1结点使用Del_X_recursion(L->next,X)递归函数执行完毕,在执行过程中肯定有留下来的,也有删掉的,但我们不必知道里面具体是如何实现的。只要后面n-1个结点执行完毕后,这个递归函数就可以结束了。
然后从最里层返回到上一层,一直return第一层,程序结束。出口函数结束。
最后是删除X结点的操作,如下图
(1)p=L;假如p指针指向的第一个结点为X,这是我们要删除的结点;
(2)L=L->next;接下来L指向下一个结点
(3)delete p;删除X结点
最后,再次调用Del_X_recursion(L,X);递归函数,从L开始,把其作为第一个结点递归的调用。一直将所有的X删除为止。
发表评论