删除链表中的第一个节点有问题 [英] Deleting first node in linked list has problems

问题描述

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

I'm implementing a linked list and it needs to have a function that when given a head of a linked list and a cstring, it finds and deletes a node whose value is the 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;
    }
}

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

It works alright but when deleting the head some garbage gets printed out. What is happening and how can I fix this? Do I have any memory leaks? Out of curiosity is the term "root" or "head" more commonly used for the first node in a linked list?

推荐答案

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

The first thing to realise is that removing an element from a linked list involves changing exactly one pointer value: the pointer that points at us. This can be the external head pointer that points to the first list element, or one of the ->next pointers inside the list. In both cases that pointer needs to be changed; its new value should become the value of the ->next pointer of the node to be deleted.

为了改变某个对象(从函数内部)，我们需要一个指向它的指针.我们需要改变一个指针，所以我们需要一个指向指针的指针.

In order to change some object (from within a function) we need a pointer to it. We need to change a pointer, so we will need a pointer to pointer.

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 条件的数量甚至可以通过在循环中进行肮脏的工作并从循环中返回来减少到一个，但这会有点麻烦:

The number of if conditions can even be reduced to one by doing the dirty work in the loop,and returning from the loop but that would be a bit of a 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
}

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

But what if the list is not unique, and we want to delete all the nodes that satisfy the condition? We just alter the loop logic a bit and add a counter:

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
}

更新:和一个驱动程序来测试它:

Update: and a driver program to test it:

#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
", cnt );
cnt = seachAndDestroy( &root, "ccc" );
printf("Cnt(ccc) := %u
", cnt );
cnt = seachAndDestroy( &root, "aaa" );
printf("Cnt(aaa) := %u
", cnt );
printf("Root now = %p
", (void*) root );

return 0;
}

和输出:

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

这篇关于删除链表中的第一个节点有问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！