问题描写叙述

设计一个递归算法，删除不带头节点的单链表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);    }

由于本题中，没有设置头节点。当删除的时候必须从第一个结点開始删除。因此我们參考中的来实现该算法。

应当注意到假设最后一个结点的数据域为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
      
       #include
       
        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的结点，眼下个人暂没想到解决的方法，改天再想。