c circular doble lista-enlazada: atraviesa fwd / rev para el nodo final da una dirección de puntero diferente

publicación relacionada: c circular doble lista enlazada delete_node – iterar atraviesa el nodo eliminado en la primera pasada después de eliminar

Todos, implementando una búsqueda para el nodo que corresponde al número de línea ‘x’ antes de eliminar ese nodo, encontré un problema en el que tanto la búsqueda directa como la inversa identifican el nodo correcto, pero el indicador de la dirección del nodo de la persona que llama se informa de manera diferente mediante la búsqueda inversa que para el delantero? Esto se aplica solo al último nodo (el número de línea más alto). Si solo se utiliza la búsqueda forwrd (pba_fwd_iter_test), entonces el último nodo se elimina correctamente. Sin embargo, si se usa la búsqueda inversa (pba_rev_iter_test), entonces la dirección establecida por “(victim-> next) -> prev = victim-> prev;” es incorrecto, establece “(víctima-> siguiente) -> prev = (víctima-> siguiente) -> anterior”. Por ejemplo, llegar al nodo final con una búsqueda inversa y luego realizar los resultados de delete_node en lo siguiente:

49: 7 - (line to delete) This is a line of text that is somewhere around 50 to 80 characters in length 48 - prev: 0x604a80 cur: 0x604b10 next: 0x604ba0 49 - prev: 0x604b10 cur: 0x604ba0 next: 0x603010 <-- delete_node 0 - prev: 0x604ba0 cur: 0x603010 next: 0x6030a0 48 - prev: 0x604a80 cur: 0x604b10 next: 0x603010 49 - prev: 0x604b10 cur: 0x604ba0 next: 0x603010 <-- (node deleted) 0 - prev: 0x603010 cur: 0x603010 next: 0x6030a0 \_______________\______ Error (should be prev: 0x604b10) 

@WhosCraig ayudó amablemente con la función delete_node, que funciona bien, pero no puedo entender por qué, al ubicar el mismo nodo con la búsqueda inversa, no se puede establecer el comando delete_node “(victim-> next) -> prev = victim-> prev; ” correctamente. Como prueba de la búsqueda inversa, simplemente puse un nodo adicional hacia el principio y luego avanzé un nodo al nodo en cuestión y luego el delete_node funcionó bien. (simplemente un adicional: list = & (* list) -> prev; list = & (* list) -> next ;. Por lo tanto, el problema tiene algo que ver con el estado del puntero al llegar al nodo final con una búsqueda inversa En lugar de una búsqueda hacia adelante, eso es lo que necesito que me ayude a averiguar. Aquí está la salida de las direcciones de puntero después de las búsquedas hacia adelante y hacia atrás, así como el seguimiento rápido -> anterior -> siguiente:

 =========== pba_fwd_iter_test() =========== passing list = &(*list)->next to tstpptr (0x605b28) tstpptr(): list : 0x605b28 tstpptr(): &list : 0x7ffff14633a8 tstpptr(): *list : 0x605ba0 tstpptr(): &(*list) : 0x605b28 next : 0x605bb8 =========== pba_rev_iter_test() =========== passing list = &(*list)->next to tstpptr (0x604020) tstpptr(): list : 0x604020 tstpptr(): &list : 0x7ffff14633a8 tstpptr(): *list : 0x605ba0 tstpptr(): &(*list) : 0x604020 next : 0x605bb8 passing list = &(*list)->next to tstpptr (0x605b28) tstpptr(): list : 0x605b28 tstpptr(): &list : 0x7ffff14633a8 tstpptr(): *list : 0x605ba0 tstpptr(): &(*list) : 0x605b28 prev; &(*list)->next tstpptr(): &(*list)->next : 0x605bb8 

Los siguientes son los fragmentos de código relevantes con el enlace a la fuente completa al principio. Gracias por cualquier ayuda que pueda proporcionar:

 /* full source: http://www.3111skyline.com/dl/dev/prg/src/ll-double-cir-1.c.txt */ struct record { char *line; int lineno; int linetype; struct record *prev; struct record *next; }; typedef struct record rec; void // traverse in fwd direction to find hightest line no. pba_fwd_iter_test (rec **list, int num); void // traverse in rev direction to find hightest line no. pba_rev_iter_test (rec **list, int num); void // dump the pointers for examination tstpptr (rec **list); int main (int argc, char *argv[]) { //  fill struct with 50 records for testing (lineno '0' based 0-49) pba_fwd_iter_test (&textfile, 49); pba_rev_iter_test (&textfile, 49); return 0; } void pba_fwd_iter_test (rec **list, int num) { printf ("=========== %s() ===========\n",__func__); int linemax = getmaxline (*list); int iterno = 0; while (((*list)->lineno != num) && (iterno next; } printf ("passing list = &(*list)->next to tstpptr (%p)\n", list); tstpptr (list); } void pba_rev_iter_test (rec **list, int num) { printf ("=========== %s() ===========\n",__func__); int linemax = getmaxline (*list); int iterno = 0; while (((*list)->lineno != num) && (iterno prev; } printf ("passing list = &(*list)->next to tstpptr (%p)\n", list); tstpptr (list); // increment prev then next and check ptr values again list = &(*list)->prev; list = &(*list)->next; printf ("passing list = &(*list)->next to tstpptr (%p)\n", list); tstpptr (list); } void tstpptr (rec **list) { fprintf (stdout, "%s(): list : %p\n", __func__, list); fprintf (stdout, "%s(): &list : %p\n", __func__, &list); fprintf (stdout, "%s(): *list : %p\n", __func__, *list); fprintf (stdout, "%s(): &(*list) : %p\n", __func__, &(*list)); fprintf (stdout, "%s(): &(**list) : %p\n\n", __func__, &(**list)); fprintf (stdout, "%s(): &(*list)->next : %p\n\n", __func__, &(*list)->next); } 

Creo que veo el problema, no creo que haya uno. El valor importante es *list , que es el mismo en todos los casos. Creo que imprimir la lista y la lista, etc., solo está nublando el problema.

En su iterador hacia adelante, la list apunta a la ubicación de la next variable del elemento # 48.

En su iterador hacia atrás, la list está apuntando a la ubicación de la variable prev del elemento # 0.

En ambos casos, * la lista apunta al elemento correcto # 49.

Ambas funciones serían mucho más simples si solo tomaran un rec * , en lugar de un rec ** , entonces sería más obvio que tomar la dirección de la variable de la list no es lo que quieres.

Tomé su código del sitio 3111skyline.com, pero no llama a las funciones de borrado (ni a muchas de las otras funciones). Agregué una función validate_list() que confirma que su lista está construida correctamente. Y creé un bucle para eliminar filas de tu lista, como esto:

 static void validate_list(rec *list) { assert(list != 0); assert(list->next != 0); assert(list->prev != 0); rec *iter = list; do { assert(iter != 0); assert(iter->next != 0); assert(iter->prev != 0); assert(iter == iter->next->prev); assert(iter == iter->prev->next); printf("Node: %p (n = %p; p = %p) %2d [%s]\n", (void *)iter, (void *)iter->next, (void *)iter->prev, iter->lineno, iter->line); iter = iter->next; } while (iter != list); } int main(void) { rec *textfile = fillrecord(); validate_list(textfile); for (int i = 0; i < 49; i++) { delete_node(&textfile, (i * 13 + 31) % (50 - i)); validate_list(textfile); } return 0; } 

Todo parece funcionar bien para mí. El siguiente paso sería reemplazar la secuencia determinista (pero no particularmente obvia) generada por la expresión con números aleatorios para verificar que funcione de esa manera también, pero el código me parece limpio.