c double link-list circolare delete_node – iterate attraversa il nodo eliminato al primo passaggio dopo l’eliminazione

Tutto, in GNU c, ho una lista circolare doppiamente concatenata che sto cercando di implementare una funzione delete_node su. Funziona bene per tutti i nodes eccetto il nodo 0. Elimina il nodo 0 (gratuito), ma la prima volta che la lista viene attraversata dopo aver cancellato il nodo 0, è ancora presente per il primo passaggio, facendo sì che il condizionale fermi l’iterazione a fallire. Le basi dell’implementazione sono:

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

Un elenco completo è qui: http://www.3111skyline.com/dl/dev/prg/src/ll-double-cir.c.txt

L’elenco è pieno di 50 record di dati per il test e ho inserito istruzioni printf per confermare le operazioni del puntatore. L’eliminazione di qualsiasi nodo eccetto il nodo 0 funziona come previsto (il seguente è l’indirizzo del puntatore per iter-> prev, iter, iter-> successivo per le righe interessate [pre- e post-cancella] per la cancellazione del nodo 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 

Nella successiva traversa dell’elenco, tutto funziona come previsto:

  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 

Tuttavia, se il nodo 0 viene eliminato, delete_node gestisce correttamente i puntatori:

 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 

Ma poi nel primo tentativo di attraversare la lista dopo la cancellazione, il nodo 0 appare al primo passaggio, facendo sì che le condizioni dell’iteratore “while (iter! = List)” falliscano e si blocchino in un loop:

  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 

Come mostrato sopra, dopo che l’iteratore attraversa 0-49, il nodo cancellato 0 scompare e inizia di nuovo a muoversi correttamente 1-49, ma a quel punto è in un ciclo perché il condizionale (iter! = Elenco) è sempre true (nodo 0 scompare impedendo l’iter da una lista sempre uguale). Questa è una lista circolare pura, non ci sono nodes HEAD o TAIL impostati su null, la fine-> next punta all’inizio della lista e la prima-> prev punta alla fine. Qual è il trucco per far funzionare la funzione delete_node () per il nodo 0 in modo tale che la prima iterazione dopo l’eliminazione inizi con 1 e non il vecchio 0 che poi scompare?

Non stai modificando il puntatore del chiamante quando richiedi il nodo stesso a cui punta come richiesta di cancellazione. Quanto segue, una versione ridotta di alcuni dei tuoi codici, dimostra un modo per farlo:

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

Uscita (ovviamente dipendente dal sistema)

Si noti come il puntatore passato (passa per indirizzo) viene modificato quando si richiede la rimozione dell'elemento 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