题目:1,设计一个递归算法,删除不带头结点的单链表L中所有值为x的结点。
答案:
void Del_x_3(Linklist &L,ElemType x){//递归实现在单链表中删除值为x的结点
LNode *p;//P指向待删除结点
if(L==NULL)return;//递归出口
if (L->data==x){//若L所指结点的值为×
p=L;//删除*L,并让L指向下一结点
L=L->next;
free(p) ;
Del_x_3 (L,x);//递归调用
)
else Del_x_3(L->next,x);//若工所指结点的值不为x
}
我的疑问:
不懂之处在这里,为什么这里能直接L=L->next,这样链表不就断了吗
p=L;//删除*L,并让L指向下一结点
L=L->next;
free(p) ;
答案是这样解释的:有读者认为直接去掉p结点会造成断链,实际上因为工为引用,是直接对原链表进行操作的,因此不会断链。
附上我验证的源程序(确实不会断链)
#include <stdio.h>
#include <stdlib.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
typedef struct Node{
int data;
Node *next;
}Node,*LinkList;
/*
尾插法
*/
void Init(LinkList H,int a[],int n){
H->next = NULL;
Node *r = H;//保持在最后
for(int i = 0;i<n;i++){
Node *node = (Node *)malloc(sizeof(Node));
node->data = a[i];
node->next = NULL;
r->next = node;
r = node;
}
}
void show(LinkList H){
Node *p = H->next;
while(p!=NULL){
printf("%d",p->data);
p = p->next;
}
}
//递归
void Del_x_3(LinkList &L,int data){
Node *node;
if(L == NULL)return;
if(L->data == data){
node = L;
L=L->next;
free(node);
Del_x_3(L,data);
}
else{
Del_x_3(L->next,data);
}
}
int main(int argc, char** argv) {
//初始化动作
LinkList L;
int n = 5;
int a[n];
printf("初始化列表,请输入5个数据\n");
for(int i = 0; i<n ;i++){
scanf("%d",&a[i]);
}
Init(L,a,n);
show(L);
printf("\n");
Del_x_3(L,1);
show(L);
return 0;
}