La suppression du premier nœud de la liste liée pose des problèmes

J’implémente une liste chaînée et elle doit avoir pour fonction de lui permettre de rechercher et de supprimer un nœud dont la valeur est cssortingng.

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

Cela fonctionne bien, mais lors de la suppression de la tête, des déchets sont imprimés. Que se passe-t-il et comment puis-je résoudre ce problème? Est-ce que j’ai des memory leaks? Par curiosité, le terme “racine” ou “tête” est-il plus communément utilisé pour le premier nœud d’une liste chaînée?

La première chose à réaliser est que supprimer un élément d’une liste chaînée implique de changer exactement une valeur de pointeur: le pointeur qui nous pointe . Il peut s’agir du pointeur head externe qui pointe vers le premier élément de la liste ou de l’un des pointeurs ->next la liste. Dans les deux cas, ce pointeur doit être changé; sa nouvelle valeur doit devenir la valeur du pointeur ->next du noeud à supprimer.

Afin de changer un object (à l’intérieur d’une fonction), nous avons besoin d’un pointeur sur celui-ci. Nous devons changer un pointeur, nous aurons donc besoin d’un pointeur à pointeur .

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

Le nombre de conditions if peut même être réduit à une en effectuant le travail incorrect dans la boucle et en revenant de la boucle, mais ce serait un peu un bidouillage:

 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 } 

Mais que se passe-t-il si la liste n’est pas unique et que nous souhaitons supprimer tous les nœuds qui remplissent la condition? Nous modifions un peu la logique de la boucle et ajoutons un compteur:

 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 } 

Mise à jour: et un programme de pilote pour le tester:

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

Et la sortie:

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

Vous changez la racine dans la fonction, vous devez donc passer un double pointeur:

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

Vous construisez une liste en pointant sur le premier noeud.

Ensuite, vous supprimez le premier noeud, mais ne mettez pas à jour le pointeur sur la liste pour qu’il pointe vers le second.

Assurez-vous simplement que votre fonction vérifie si vous supprimez le premier nœud et renvoyez toujours un pointeur sur le premier pointeur de la liste finale. Sinon, au lieu du paramètre node *root , transmettez node **root afin de pouvoir modifier la référence dans votre fonction (bien que je n’aime pas cette façon de travailler).