Revirtiendo una doble cola circular sin un centinela

Question

Hola Stackoverflow estoy trabajando en mi tarea y estoy tratando de revertir una doble cola circular ligado sin un centinela. Aquí están mis estructuras de datos:

struct DLink {

 TYPE value;

 struct DLink * next;

 struct DLink * prev;
};

struct cirListDeque {

 int size;
 struct DLink *back;
};

Aquí está mi enfoque para revertir la doble cola:

void reverseCirListDeque(struct cirListDeque* q) {

struct DLink* current;

struct DLink* temp;



temp = q->back->next;

q->back->next = q->back->prev;

q->back->prev = temp;



current = q->back->next;

while(current != q->back) {

    temp = current->next;

    current->next = current->prev;

    current->prev = temp;



    current = current->next;

}

}

Sin embargo, cuando lo ejecuto y poner los valores 1, 2 y 3 en el mismo (TYPE es sólo un alias para int en este caso) y revertirla consigo 2, 1, 3. ¿Alguien tiene alguna idea de lo que yo puede estar haciendo mal?

Gracias de antemano.

Answer 1

current = q->back->next;

while(current != q->back->next)
{
    /* This code will never run, cause you guaranteed right before the while
     * that current == q->back->next .
     */
}

Actualización: Lo que hay que hacer ahora, una vez que haya revertido todos los punteros (que parece que funciona ahora, a juzgar por sus resultados), se ajusta el puntero "atrás" para Back-> Anterior

.

Answer 2

Cuando se trabaja con tipos abstractos de datos - listas, colas, deques, etc., siempre que estén involucrados punteros, lo que realmente ayuda a extraer la estructura de datos y sus punteros en un diagrama en papel. Etiqueta de todo. A continuación, el código lo que se ve. Lo que realmente hace que sea mucho más fácil. No he utilizado deques desde la universidad, pero asegúrese de que usted no está confundiendo anterior, siguiente, y de vuelta, ya que ello podría ser el problema. También asegúrese de comprobar si hay punteros nulos antes de la eliminación de referencias de ellos.

Esperemos que esto ayuda sin dar directamente la respuesta de distancia. Su profesor puede apreciar eso. ; -)

Answer 3

No es una respuesta directa a su problema, pero de vuelta en la escuela, me encontré con la de visualización de datos depurador , para ser un valor incalculable para para depuración de problemas como este.

Answer 4

La forma más fácil y rápida de hacer esto sería sólo para cambiar su interpretación de la dirección de la cola.

La dirección se almacena en el cirListDeque y su movimiento de nodo a nodo se llevaría a cabo con el conocimiento de la dirección actual de la cola.