第1章第2节练习题1 递归删除指定结点
最后更新于：2022-04-01 19:50:37
## 问题描述
> 设计一个递归算法，删除不带头节点的单链表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)](http://blog.csdn.net/u013595419/article/details/50481785)中的[2.5.2删除自身结点](http://blog.csdn.net/u013595419/article/details/50481785#t12)来实现该算法。应当注意到如果最后一个结点的数据域为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的结点，目前个人暂没想到解决办法，改天再想。
';