c函数:只使用一个局部指针变量从单链表中删除节点

eanckbw9  于 2023-04-19  发布在  其他
关注(0)|答案(3)|浏览(124)

所以我一直在尝试解决一本书中的这个练习(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;
}

还有别的办法吗

bkhjykvo

bkhjykvo1#

虽然可以只用一个变量重写循环(正如您已经知道的那样),但寻找一种不使用至少一个变量就释放内存的方法似乎没有多大意义。
顺便说一句,在这种情况下增加一个额外的间接层可以让你用更少的分支编写更紧凑的代码。更具体地说,删除列表的第一个元素不再是一个“特殊情况”(在你的代码中是这样的)

struct node *delete_from_list(struct node *list, int n)
{
    struct node **pcur;

    for (pcur = &list; *pcur != NULL && (*pcur)->value != n; pcur = &(*pcur)->next)
        ;

    if (*pcur != NULL)
    {
      struct node *cur = *pcur;
      *pcur = (*pcur)->next;
      free(cur);
    }

    return list;
}

在任何情况下,不使用额外的局部变量的要求都不够明确,正如@larsmans在评论中指出的那样。如果free使用自己的局部变量怎么办?它是否可以?如果可以,那么编写自己的free版本可能是可以的

struct node *my_free(struct node *node)
{
  struct node *next = node->next;  
  free(node);
  return next;
}

然后在delete_from_list中使用它

if (*pcur != NULL)
  *pcur = my_free(*pcur)

从而“消除”额外的局部变量。

ioekq8ef

ioekq8ef2#

好吧,这里有另一种真正不使用辅助变量的方法:

struct node * listdelete( struct node * list, int n ) {
    if ( list == NULL )
        return list;

    struct node * caret = list;
    if ( list->value == n ) {
        list = list->next;
        free( caret );
    }
    else {
        while ( caret->next != NULL && caret->next->value != n ) {
            caret = caret->next;
        }
        while ( caret->next->next != NULL ) {
            caret->next->value = caret->next->next->value;
            caret = caret->next;
        }
        free( caret->next );
        caret->next = NULL;
    }

    return list;
}

它所做的只是简单地将节点的value s移动到前一个节点,最后删除最后一个节点。愚蠢的,我不得不说,但它做了受到挑战的事情。在这个过程中,我不需要任何其他变量,不是整数,不是指针,也不是指向指针的指针。
下面是一个函数示例:http://ideone.com/gEy7Q0

ymdaylpp

ymdaylpp3#

这里有一个想法,只使用一个指针局部变量(不包括list),并且不将值从一个节点移动到另一个节点,而是旨在首先使目标节点成为列表的尾节点。然后删除是微不足道的。
为了使目标节点成为尾部,我们可以如下进行:

  • 首先处理边界情况(空链表或要删除的节点是第一个节点)。
  • 查找目标节点。如果未找到,则返回原始列表指针。
  • 如果目标节点恰好也是尾部,那么我们可以删除该节点并返回列表指针。
  • 找到尾节点。
  • “滥用”尾节点的next成员(为NULL)再次遍历列表,在目标节点处停止。因此,现在原始尾节点不再是尾节点,而是有目标节点跟随它。目标节点现在有两个对其的引用,来自其原始前趋节点和原始尾节点。
  • 再次遍历链表,这一次将目标节点的原始前导节点与它的后继节点链接起来。现在我们有了一个链表,其中目标节点被原始尾节点引用一次。
  • 继续遍历,直到我们再次遇到目标节点,并将其删除,就像它是尾部一样(它实际上有一个非NULL的next成员,但我们忽略它)。

就这样。不过还有一个问题:如果要删除的值在列表中多次出现,则它将不起作用。为了解决这个问题,我们可以用一个特殊的值来标记要删除的节点,我们将假设该值在列表中的其他地方没有使用。例如:INT_MAX
它看起来是这样的:

struct node *delete_from_list(struct node *list, int n) {
    struct node *cur = list;

    // Boundary cases
    if (list == NULL) return NULL;
    if (list->value == n) {
        list = list->next;
        free(cur);
        return list;
    }

    // Find the node with value n:
    while (cur->next != NULL && cur->next->value != n) cur = cur->next;

    if (cur->next == NULL) return list; // Nothing to delete

    // If the found node is not the tail node, we will first make it the tail
    if (cur->next->next != NULL) {
        // Mark the node with INT_MAX as value, assuming that doesn't occur elsewhere
        cur->next->value = INT_MAX;
    
        // find the tail of the list
        while (cur->next != NULL) cur = cur->next;
        
        // Use tail's next member to walk to the marked node
        cur->next = list;
        while (cur->next->value != INT_MAX) {
            cur->next = cur->next->next; // cur doesn't move; only its next member
        }
        
        // Find predecessor of the node to delete
        cur = list;
        while (cur->next->value != INT_MAX) cur = cur->next;
    
        // Unlink that node here (it still is linked to by original tail node)
        cur = cur->next = cur->next->next;
    
        // Find the node again, which we can now consider the tail
        while (cur->next->value != INT_MAX) cur = cur->next;
    }
    
    // As cur->next is the tail, we don't need to know its next pointer, and can free it
    free(cur->next);

    // Detach that tail node:
    cur->next = NULL;

    return list;
}

但我怀疑这是演习的目的。

相关问题