c - 删除链表第一个节点有问题

Question

我正在实现一个链表，它需要一个函数，当给定一个链表的头部和一个 cstring 时，它会找到并删除一个值为 cstring 的节点。

typedef struct node
{
  char entry[21];
  struct node* next;
} node;


/*returns true if node with phrase value found, otherwise false*/
bool findAndRemove(node* root, char phrase[21])
{
    if(root != NULL)
    {
        node* previous = NULL;
        while(root->next != NULL)
        {
            if(strcmp(root->entry, phrase) == 0)//found
            {
                if(previous == NULL)//node to delete is at head
                {
                    node* tmp = root;
                    root = root->next;
                    free(tmp);
                    return true;
                }
                previous->next = root->next;
                free(root);
                return true;
            }
            previous = root;
            root = root->next;
        }
        return false;
    }
}

它工作正常但是当删除头部时会打印出一些垃圾。发生了什么事，我该如何解决？我有内存泄漏吗？出于好奇，术语“根”或“头”更常用于链表中的第一个节点吗？

Answer 1

首先要意识到的是，从链表中删除一个元素涉及更改恰好一个指针值:指向我们的指针。这可以是指向第一个列表元素的外部 head 指针，也可以是列表内部的 ->next 指针之一。在这两种情况下，都需要更改那个指针；它的新值应该成为要删除节点的->next指针的值。

为了改变一些对象(从一个函数中)，我们需要一个指向它的指针。我们需要更改一个指针，因此我们需要一个指向指针的指针。

bool findAndRemove1(node **ptp, char *phrase)
{
    node *del;

    for( ;*ptp; ptp = &(*ptp)->next) {
        if( !strcmp((*ptp)->entry, phrase) ) { break; } //found
        }

      /* when we get here, ptp either
      ** 1) points to the pointer that points at the node we want to delete
      ** 2) or it points to the NULL pointer at the end of the list
      **    (in the case nothing was found)
      */
    if ( !*ptp) return false; // not found

    del = *ptp;
    *ptp = (*ptp)->next;
    free(del);
    return true;
}

if 条件的数量甚至可以通过在循环中进行脏工作并从循环中返回来减少到一个，但这会有点 hack:

bool findAndRemove2(node **ptp, char *phrase)
{

    for( ;*ptp; ptp = &(*ptp)->next) {
        node *del;
        if( strcmp((*ptp)->entry, phrase) ) continue; // not the one we want

          /* when we get here, ptp MUST
          ** 1) point to the pointer that points at the node we want to delete
          */
        del = *ptp;
        *ptp = (*ptp)->next;
        free(del);
        return true;
        }
    return false; // not found
}

但是如果列表不唯一，我们要删除所有满足条件的节点怎么办？我们只是稍微改变一下循环逻辑并添加一个计数器:

unsigned searchAndDestroy(node **ptp, char *phrase)
{
    unsigned cnt;

    for( cnt=0 ;*ptp; ) {
        node *del;
        if( strcmp((*ptp)->entry, phrase) ) { // not the one we want
             ptp = &(*ptp)->next;
             continue; 
             }
          /* when we get here, ptp MUST point to the pointer that points at the node we wish to delete
          */
        del = *ptp;
        *ptp = (*ptp)->next;
        free(del);
        cnt++;
        }
    return cnt; // the number of deleted nodes
}

更新:和测试它的驱动程序:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct  list {
        struct list *next;
        char entry[20];
        } node;

void node_add( node **ptp, char *str)
{
node *new;

for (   ; *ptp; ptp = &(*ptp)->next) {
        if (strcmp ((*ptp)->entry, str) < 0) continue;
        }
new = malloc (sizeof *new);
strcpy(new->entry, str);
new->next = *ptp;
*ptp = new;
}

int main (void)
{
node *root = NULL;
unsigned cnt;

node_add (& root, "aaa" );
node_add (& root, "aaa" );
node_add (& root, "bbb" );
node_add (& root, "ccc" );
node_add (& root, "aaa" );
cnt = seachAndDestroy( &root, "bbb" );
printf("Cnt(bbb) := %u\n", cnt );
cnt = seachAndDestroy( &root, "ccc" );
printf("Cnt(ccc) := %u\n", cnt );
cnt = seachAndDestroy( &root, "aaa" );
printf("Cnt(aaa) := %u\n", cnt );
printf("Root now = %p\n", (void*) root );

return 0;
}

输出:

plasser@pisbak:~/usenet$ ./a.out
Cnt(bbb) := 1
Cnt(ccc) := 1
Cnt(aaa) := 3
Root now = (nil)