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

问题描述

我实施一个链表，它需要有一个给定的一个链表和一个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?

推荐答案

要认识到的第一件事是的从链表的移除元素涉及到更改一个指针值：指针指着我们的。这可以是外部头指针指向第一个列表元素，或之一 - ＆gt;接下来指针名单内。在这两种情况下的该指针需要改变;其新的价值应成为价值的 - 方式＆gt;节点的下一个指针被删除

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

和输出：

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

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