设计一个递归算法,删除不带头结点的单链表L中所有值为x的结点
问题描述:
设计一个递归算法,删除不带头结点的单链表L中所有值为x的结点。问题解答:
设f(L, x)的功能是删除以L为首结点指针的单链表中所有值等于x的结点,则显然有 f(L->next, x)的功能是删除以L->next为首结点指针的单链表中所有值等于x的结点。由此,可以推出递归模型如下:终止条件:
f(L, x) ≡ 不做任何事情; 若L为空表或只有一个结点
f(L, x)≡删除*L 结点;f(L->next, x); 若 L->data==x
递归主体:
f(L, x)≡f(L->next, x); 其他情况
本题代码如下:
void Del_X_3 (Linklist &L, ElemType x) { //递归实现在单链表L中删除值为x的结点 LNode *p; //p指向待删除结点 if (L==NULL) //递归出口 return; if (L->data==x) { //若L所指结点的值为x p=L; //删除*L,并让L指向下一结点 L=L->next; free(p); Del_X_3(L,x) ; //递归调用 }else //若L所指结点的值不为x Del_X_3 (L->next, x) ; //递归调用 }算法需要借助一个递归工作栈,深度为O(n),时间复杂度为O(n)。有读者认为直接free掉p结点会造成断链,实际上因为L为引用,是直接对原链表进行操作,因此不会断链。