c liste double liée circulaire delete_node – iterate traverse le noeud supprimé lors du premier passage après suppression

Tous, dans GNU c, j’ai une liste circulaire doublement chaînée sur laquelle j’essaye d’implémenter une fonction delete_node. Cela fonctionne correctement pour tous les nœuds sauf le nœud 0. Il supprime le nœud 0 (free ()), mais la première fois que la liste est parcourue après la suppression du nœud 0, elle est toujours présente pour la première passe, ce qui entraîne l’arrêt de l’itération échouer. Les bases de la mise en œuvre sont:

struct record { char *line; int lineno; int linetype; struct record *prev; struct record *next; }; typedef struct record rec; void iterfwd (rec *list) { rec *iter = list; // second copy to iterate list if (iter == NULL) { fprintf (stdout,"%s(), The list is empty\n",__func__); } else { do { printf ("%2d - prev: %p cur: %p next: %p\n", iter->lineno, iter->prev, iter, iter->next); iter = iter->next; } while (iter != list); } } void delete_node (rec *list, int num) { rec *iter = list; // second copy to iterate list int cnt = 0; int found = 0; if (iter == NULL) { fprintf (stdout,"%s(), The list is empty\n",__func__); } else { // traverse list forward (check cnt == num, else if end -> Out Of Range) do { if (cnt == num) { found=1; (iter->prev)->next = iter->next; (iter->next)->prev = iter->prev; free (iter); break; } iter = iter-> next; cnt++; } while (iter != list); if (found != 1) { fprintf (stderr, "%s(), Error: record to delete is out of range (%d)\n", __func__, num); } } } int main (int argc, char *argv[]) { struct record *textfile = NULL; // instance of record, pointer to list int node = 0; node = (argc >= 2) ? atoi (argv[1]) : 0; textfile = fillrecord (); // fill textfile circular linked-list iterfwd (textfile); delete_node (textfile, node); iterfwd (textfile); return 0; } 

Une liste complète est ici: http://www.3111skyline.com/dl/dev/prg/src/ll-double-cir.c.txt

La liste est remplie de 50 enregistrements de données à tester et j’ai inséré des instructions printf pour confirmer les opérations du pointeur. La suppression de tout nœud sauf le nœud 0 fonctionne comme prévu (voici les adresses de pointeur pour iter-> prev, iter, iter-> next pour les lignes concernées [pré et post-suppression] pour une suppression du nœud 10):

  9 - prev: 0x603490 cur: 0x603520 next: 0x6035b0 10 - prev: 0x603520 cur: 0x6035b0 next: 0x603640 <-- delete_node 11 - prev: 0x6035b0 cur: 0x603640 next: 0x6036d0 9 - prev: 0x603490 cur: 0x603520 next: 0x603640 10 - prev: 0x603520 cur: 0x6035b0 next: 0x603640 <-- (node deleted) 11 - prev: 0x603520 cur: 0x603640 next: 0x6036d0 

Lors du prochain parcours de la liste, tout fonctionne comme prévu:

  7 - prev: 0x603370 cur: 0x603400 next: 0x603490 8 - prev: 0x603400 cur: 0x603490 next: 0x603520 9 - prev: 0x603490 cur: 0x603520 next: 0x603640 11 - prev: 0x603520 cur: 0x603640 next: 0x6036d0 12 - prev: 0x603640 cur: 0x6036d0 next: 0x603760 

Cependant, si le noeud 0 est supprimé, le noeud delete_node gère correctement les pointeurs:

 49 - prev: 0x604b10 cur: 0x604ba0 next: 0x603010 0 - prev: 0x604ba0 cur: 0x603010 next: 0x6030a0 <-- delete_node 1 - prev: 0x603010 cur: 0x6030a0 next: 0x603130 49 - prev: 0x604b10 cur: 0x604ba0 next: 0x6030a0 0 - prev: 0x604ba0 cur: 0x603010 next: 0x6030a0 <-- (node deleted) 1 - prev: 0x604ba0 cur: 0x6030a0 next: 0x603130 

Mais ensuite, lors de la première tentative de parcours dans la liste après suppression, le nœud 0 apparaît au premier passage, ce qui provoque la condition d’iterator ‘while (iter! = List)’ et échoue: elle rest bloquée dans une boucle:

  0 - prev: 0x604ba0 cur: 0x603010 next: 0x6030a0 1 - prev: 0x604ba0 cur: 0x6030a0 next: 0x603130 2 - prev: 0x6030a0 cur: 0x603130 next: 0x6031c0 3 - prev: 0x603130 cur: 0x6031c0 next: 0x603250 4 - prev: 0x6031c0 cur: 0x603250 next: 0x6032e0  47 - prev: 0x6049f0 cur: 0x604a80 next: 0x604b10 48 - prev: 0x604a80 cur: 0x604b10 next: 0x604ba0 49 - prev: 0x604b10 cur: 0x604ba0 next: 0x6030a0 1 - prev: 0x604ba0 cur: 0x6030a0 next: 0x603130 2 - prev: 0x6030a0 cur: 0x603130 next: 0x6031c0 3 - prev: 0x603130 cur: 0x6031c0 next: 0x603250 

Comme indiqué ci-dessus, après que l’iterator ait parcouru 0-49, le nœud supprimé 0 disparaît et il recommence à parcourir correctement 1-49. À ce stade, il est en boucle car le conditionnel (iter! = List) est toujours vrai (node 0 disparaît empêchant iter d’égaler la liste). Il s’agit d’une liste purement circulaire, aucun nœud HEAD ou TAIL n’est défini sur null, la fin-> next pointe vers le début de la liste et la première-> prev pointe vers la fin. Quelle est l’astuce pour que la fonction delete_node () fonctionne pour le noeud 0, de sorte que la première itération après la suppression commence par 1 et non par l’ancien 0 qui disparaît ensuite?

Vous ne modifiez pas le pointeur de l’ appelant lorsque vous demandez au noeud même vers lequel il pointe en tant que demande de suppression. Ce qui suit, une version réduite de certains de vos codes, illustre une façon de procéder:

 #include  #include  typedef struct record rec; struct record { int data; rec *prev, *next; }; void delete_node (rec ** pp, int num) { if (!*pp) return; // find the num'th node while (num-- && *pp) pp = &(*pp)->next; // setup victim rec *victim = *pp; // non-self-reference node means just rewire if (victim && (victim != victim->next)) { victim->prev->next = victim->next; victim->next->prev = victim->prev; *pp = victim->next; } else { // deleted node was self-referenced. last node *pp = NULL; } free(victim); } void iterfwd(const rec* list) { const rec *p = list; printf("list: %p\n", list); if (p) { for (; p; p = (p->next != list ? p->next : NULL)) printf("prev: %p, self:%p, next:%p, data = %d\n", p->prev, p, p->next, p->data); } puts(""); } void insert(rec **pp, int data) { // setup new node rec *newp = malloc(sizeof(*newp)); newp->data = data; if (!*pp) { newp->next = newp->prev = newp; *pp = newp; } else { // insert between prev and head. newp->next = *pp; (*pp)->prev->next = newp; newp->prev = (*pp)->prev; (*pp)->prev = newp; } } int main() { rec *list = NULL; int i; for (i=1; i<=5; ++i) insert(&list, i); iterfwd(list); // delete fourth node (0-based) delete_node(&list, 3); iterfwd(list); // delete first node (0-based) delete_node(&list, 0); iterfwd(list); // delete first node (0-based) delete_node(&list, 0); iterfwd(list); // delete first node (0-based) delete_node(&list, 0); iterfwd(list); // delete first node (0-based) delete_node(&list, 0); iterfwd(list); return 0; } 

Sortie (évidemment dépendante du système)

Notez comment le pointeur transmis (adresse de passage) est modifié lors de la suppression de l'élément 0.

 list: 0x100103af0 prev: 0x100103b70, self:0x100103af0, next:0x100103b10, data = 1 prev: 0x100103af0, self:0x100103b10, next:0x100103b30, data = 2 prev: 0x100103b10, self:0x100103b30, next:0x100103b50, data = 3 prev: 0x100103b30, self:0x100103b50, next:0x100103b70, data = 4 prev: 0x100103b50, self:0x100103b70, next:0x100103af0, data = 5 list: 0x100103af0 prev: 0x100103b70, self:0x100103af0, next:0x100103b10, data = 1 prev: 0x100103af0, self:0x100103b10, next:0x100103b30, data = 2 prev: 0x100103b10, self:0x100103b30, next:0x100103b70, data = 3 prev: 0x100103b30, self:0x100103b70, next:0x100103af0, data = 5 list: 0x100103b10 prev: 0x100103b70, self:0x100103b10, next:0x100103b30, data = 2 prev: 0x100103b10, self:0x100103b30, next:0x100103b70, data = 3 prev: 0x100103b30, self:0x100103b70, next:0x100103b10, data = 5 list: 0x100103b30 prev: 0x100103b70, self:0x100103b30, next:0x100103b70, data = 3 prev: 0x100103b30, self:0x100103b70, next:0x100103b30, data = 5 list: 0x100103b70 prev: 0x100103b70, self:0x100103b70, next:0x100103b70, data = 5 list: 0x0