C删除链接列表中的节点
问题描述:
我有这个程序,它具有创建列表的功能,删除一个节点,如果它的值等于功能delete_node()
的参数x
,然后它打印链表节点。创建和打印工作正常,但我无法删除值为x
的节点。我得到我的原始列表或空白列表。C删除链接列表中的节点
#include <stdio.h>
struct list {
int value;
struct list *next;
};
struct list *create_list(struct list *l, int x) {
//allocate memory for new tmp node
struct list *tmp = malloc(sizeof(struct list));
tmp->value = x;
//tmp shtohet ne koke te listes
tmp->next = l;
//l behet koka e listes
l = tmp;
return l;
}
struct list *delete_node(struct list *l, int x) {
while (l) {
if(l->value == x) {
//printf("%d", x);
struct list *tmp = malloc(sizeof(struct list));
tmp->value = l->next->value;
tmp->next = l->next->next;
l = tmp;
printf("%d ", tmp->value);
}
l = l->next;
}
return l;
}
int main() {
struct list *l = NULL;
for (int i=5; i>-6; --i)
l = create_list(l, i);
l = delete_node(l, 3);
while (l) {
printf("%d ", l->value);
l = l->next;
}
printf("\n");
return 0;
}
答
下面是对有问题的代码的修复。
struct list *delete_node(struct list *l, int x) {
struct list *prev, *retval=l;
while (l) {
if(l->value == x) {
if(l==retval) {
retval=l->next;
free(l);
l=retval;
} else {
prev->next=l->next;
free(l);
l=prev;
}
}
prev = l;
l = l->next;
}
return retval;
}
您不需要分配更多内存来丢弃不需要的节点。你这样做会严重泄漏记忆。
您需要跟踪列表的头部。这是retval的用途。如果x
未找到或在非头节点中找到,则您将返回相同的头部。如果在头节点中找到x
,您将返回下一个节点。
您还需要跟踪前一个节点,以便能够告诉前一个节点当前节点将被释放。这对单链表是必需的。
+0
谢谢@alvits –
答
删除的关键是跟踪以前的模式。
通过凝视“假”头节点,简化了while
循环。
struct list *delete_node(struct list *l, int x) {
struct list start; // Code only uses the next field
start.next = l;
struct list *p = &start;
while (p->next) {
struct list *q = p->next;
if (q->value == x) {
p->next = q->next;
free(q);
break;
}
p->next = q;
}
return start.next;
}
你正在遍历链表,直到你到达结尾,因此当列表中的任何地方没有找到'x'时,'return l'将返回NULL。当找到'x'时,你扔掉原始记录并返回下一条记录的副本,最后扔掉2条记录,然后继续遍历列表的其余部分,最后返回NULL。 – alvits