问题描述
设计一个递归算法,删除不带头节点的单链表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的结点,目前个人暂没想到解决办法,改天再想。