Deleting first node in linked list has problems

问题:

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?

回答1:

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;
}

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\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;
}

And the output:

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

回答2:

You are changing the root inside the function, thus you need to pass a double pointer:

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

回答3:

You construct a list by pointing to the first node.

Then you delete the first node, but do not update the pointer to the list to point to the second one

Just make your function check if you are deleting the first node, and always return a pointer to the first pointer of the final list. Alternatively, instead of node *root parameter, pass node **root so you can modifiy the reference in your function (although I don't like this way of working).