第1章第2节练习题1 递归删除指定结点

问题描述

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

算法思想

因为题目要求使用递归的方式删除指定结点，那么我们可以先列出递归的基本模型：

指针p指向要删除的结点，指针q则为要删除结点的后继结点。

递归出口：

    if(p==NULL){
return;
    }

递归主体：

    if(p->data==x){
            p->data=q->data;
            p->next=q->next;
free(q);
            DelNodeX(p,x);
    }else{
        DelNodeX(p->next,x);
    }

因为本题中，没有设置头节点，当删除的时候必须从第一个结点开始删除，因此我们参考第1章第2节线性表的链式表示(1)中的2.5.2删除自身结点来实现该算法。应当注意到如果最后一个结点的数据域为x时，需要区别对待。此时，指针q为空，如果继续执行p->data=q->data时明显会出错，但也因为是最后一个结点，此时只需将指针p直接赋值为NULL便可。

算法描述如下：

算法描述

void DelNodeX(LNode *p, ElemType x)
{
if(p==NULL){
return;
    }
    LNode*  q=p->next;
if(p->data==x){
if(q!=NULL){
            p->data=q->data;
            p->next=q->next;
        }else{
            p=NULL;
        }
free(q);
        DelNodeX(p,x);
    }else{
        DelNodeX(p->next,x);
    }
}

具体代码见附件

---

附件

#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;
struct LNode *next;
}LNode,*LinkList;

LinkList CreatList();
void DelNodeX(LNode*,ElemType);
void Print(LNode*);

int main(int argc,char* argv[])
{
    ElemType e=3;

    LNode *p;
    p=CreatList();
    Print(p);
    DelNodeX(p,e);
    Print(p);
return 0;
}
//尾插法建立单链表
LinkList CreatList()
{
    LNode *p;
    LNode *s;
    ElemType x;
scanf("%d",&x);
    p=(LNode*)malloc(sizeof(LNode));
    p->data=x;
    LNode *r=p;
while(1){
scanf("%d",&x);
if(x==999){
break;
        }
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
    }
    r->next=NULL;   
return p;
}
//删除指定节点
void DelNodeX(LNode *p, ElemType x)
{
if(p==NULL){
return;
    }

    LNode*  q=p->next;
if(p->data==x){
if(q!=NULL){
            p->data=q->data;
            p->next=q->next;
        }else{
            p=NULL;
        }
free(q);
        DelNodeX(p,x);
    }else{
        DelNodeX(p->next,x);
    }
}
//打印所有节点
void Print(LNode *p)
{
while(p){
printf("%4d",p->data);
        p=p->next;
    }
printf("\n");
}

注：此种解法存在一个Bug，当最后一个或最后多个连续结点均为数据域为x的结点时，会留下一个数据域为x的结点，目前个人暂没想到解决办法，改天再想。