所以我一直在尝试解决一本书中的这个练习(C编程:A Modern Approach - K.N. King Chapter 17 exercise 6):
修改delete_from_list函数,使其仅使用一个指针变量,而不是两个(cur和prev)。
struct node {
int value;
struct node *next;
};
struct node *delete_from_list(struct node *list, int n)
{
struct node *cur, *prev;
for (cur = list, prev = NULL;
cur != NULL && cur->value != n;
prev = cur, cur = cur->next)
;
if (cur == NULL)
return list;
if (prev == NULL)
list = list->next;
else
prev->next = cur->next;
free(cur);
return list;
}
(The函数返回列表的头部)
一种方法是将第一个函数参数更改为指向指针的指针,但这在下面的练习中会被要求。
我真的想不出一种方法来解决这个问题,只使用一个局部变量,而不发生内存泄漏或未定义的行为。
struct node *delete_from_list(struct node *list, int n)
{
struct node *p = list;
if (!p)
return NULL;
if (p->value == n) {
list = list->next;
free(p);
return list;
}
while (p->next && p->next->value != n)
p = p->next;
if (p->next)
// free(p->next); // undefined behavior
p->next = p->next->next; // memory leak
return list;
}
另一种方法是递归,但我自己从来没有想到过这一点。我怀疑这是练习的意图,因为这本书中的练习并不复杂(这是我想不出来的第一个),而且在前一章中只有几个简单的递归练习。而且我认为从技术上讲,它并不是一个真正的局部变量,因为每次调用函数都会得到新的变量副本。
struct node *delete_from_list(struct node *list, int n)
{
struct node *t;
if (list == NULL)
return NULL;
if (list->value == n) {
t = list->next;
free(list);
return t;
}
list->next = delete_from_list(list->next, n);
return list;
}
还有别的办法吗
3条答案
按热度按时间bkhjykvo1#
虽然可以只用一个变量重写循环(正如您已经知道的那样),但寻找一种不使用至少一个变量就释放内存的方法似乎没有多大意义。
顺便说一句,在这种情况下增加一个额外的间接层可以让你用更少的分支编写更紧凑的代码。更具体地说,删除列表的第一个元素不再是一个“特殊情况”(在你的代码中是这样的)
在任何情况下,不使用额外的局部变量的要求都不够明确,正如@larsmans在评论中指出的那样。如果
free
使用自己的局部变量怎么办?它是否可以?如果可以,那么编写自己的free
版本可能是可以的然后在
delete_from_list
中使用它从而“消除”额外的局部变量。
ioekq8ef2#
好吧,这里有另一种真正不使用辅助变量的方法:
它所做的只是简单地将节点的
value
s移动到前一个节点,最后删除最后一个节点。愚蠢的,我不得不说,但它做了受到挑战的事情。在这个过程中,我不需要任何其他变量,不是整数,不是指针,也不是指向指针的指针。下面是一个函数示例:http://ideone.com/gEy7Q0
ymdaylpp3#
这里有一个想法,只使用一个指针局部变量(不包括
list
),并且不将值从一个节点移动到另一个节点,而是旨在首先使目标节点成为列表的尾节点。然后删除是微不足道的。为了使目标节点成为尾部,我们可以如下进行:
next
成员(为NULL)再次遍历列表,在目标节点处停止。因此,现在原始尾节点不再是尾节点,而是有目标节点跟随它。目标节点现在有两个对其的引用,来自其原始前趋节点和原始尾节点。next
成员,但我们忽略它)。就这样。不过还有一个问题:如果要删除的值在列表中多次出现,则它将不起作用。为了解决这个问题,我们可以用一个特殊的值来标记要删除的节点,我们将假设该值在列表中的其他地方没有使用。例如:
INT_MAX
。它看起来是这样的:
但我怀疑这是演习的目的。