删除链表中的第一个节点有问题

我正在实现一个链表,它需要有一个函数,当给定一个链表和一个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; } } 

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

首先要意识到从链表中删除一个元素涉及到只改变一个指针值:指向我们的指针。 这可以是指向第一个列表元素的外部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条件甚至可以减少为1的数量,但这将是一个黑客攻击:

 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  #include  #include  #include  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) 

您正在更改函数内的根,因此您需要传递一个双指针:

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

您可以通过指向第一个节点来构建列表。

然后删除第一个节点,但不要更新指向列表的指针以指向第二个节点

只需让您的函数检查是否要删除第一个节点,并始终返回指向最终列表的第一个指针的指针。 或者,代替node *root参数,传递node **root这样你就可以修改函数中的引用(虽然我不喜欢这种工作方式)。