Curso 2023/2024
Algunos errores habituales de estudiantes que, habiendo estudiado, no lo hacen del todo bien, propios de este ejercicio (sin considerar otros más generales como utilizar mal las instrucciones de control de flujo) consisten en:
No considerar que el nuevo dato puede ser el nuevo mínimo, puede ser el nuevo máximo, y puede ser ambas cosas si la cola de prioridad estaba vacía.
No tratar bien el caso en que el nuevo dato coincide con el que ya era el mínimo o el máximo.
No crear el nuevo nodo (con new
).
Poner al revés lo que va a la izquierda y a la derecha
de una asignación, por ejemplo nuevo =
minimo
en vez de minimo = nuevo
.
Hacer menos asignaciones de las necesarias, por ejemplo hacer solo 3 donde deben hacerse 4 asignaciones.
Que sobre o falte algún atributo, por ejemplo
utilizar n->siguiente
donde debe
ir n->anterior->siguiente
o viceversa.
Acceder a mivariable->miatributo
en una situación en la que
mivariable
puede
valer nullptr
.
La siguiente implementación contiene 7 errores: corrígelos.
ColaDePrioridadDeDobleFin::Nodo::Nodo(int laPrioridad) : prioridad{laPrioridad}, anterior{nullptr}, siguiente{nullptr} { } ColaDePrioridadDeDobleFin::ColaDePrioridadDeDobleFin() : minimo{nullptr}, maximo{nullptr}, laTalla{0} { } void ColaDePrioridadDeDobleFin::insertar(int prioridad) { laTalla++; if (minimo == nullptr) { minimo = new Nodo(prioridad); maximo = new Nodo(prioridad); } if (prioridad <= minimo->prioridad) { Nodo * nuevo = new Nodo(prioridad); nuevo->siguiente = minimo; minimo = nuevo; } else if (prioridad >= maximo->prioridad) { Nodo * nuevo = new Nodo(prioridad); nuevo->anterior = maximo; maximo = nuevo; } else { for (Nodo * actual = minimo; actual != maximo; actual = actual->siguiente) { if (actual->prioridad >= prioridad) { Nodo * nuevo = new Nodo(prioridad); nuevo->siguiente = actual; nuevo->anterior = actual->anterior; actual->anterior = nuevo; actual->anterior->siguiente = nuevo; } } } }
En el caso minimo == nullptr
(dentro del
primer if
) se están creando dos nodos en vez de uno.
Falta el else
asociado al
primer if
para que no vuelva a insertar.
En el caso prioridad <= minimo->prioridad
(dentro del
segundo if
) falta hacer que el nodo con el viejo mínimo
tenga como anterior el nodo con el nuevo mínimo.
En el caso prioridad >= maximo->prioridad
(dentro del
tercer if
) falta hacer que el nodo con el viejo máximo
tenga como siguiente el nodo con el nuevo máximo.
Ese bucle no debería terminar al llegar a maximo
sino al
llegar a nullptr
; tal como está, no inserta lo que deba ir
delante del viejo máximo (haz una traza de lo que sucede, por ejemplo,
si tenemos 10, 20, 30 y 40 en la cola y queremos insertar 35).
Falta terminar el bucle tras insertar el nuevo nodo para que no siga insertando.
Las dos últimas asignaciones dentro del bucle deben hacerse en el orden inverso.
A continuación se muestra una forma de arreglar esos errores:
void ColaDePrioridadDeDobleFin::insertar(int prioridad) { laTalla++; if (minimo == nullptr) { minimo = new Nodo(prioridad); maximo = minimo; } else if (prioridad <= minimo->prioridad) { Nodo * nuevo = new Nodo(prioridad); nuevo->siguiente = minimo; minimo->anterior = nuevo; minimo = nuevo; } else if (prioridad >= maximo->prioridad) { Nodo * nuevo = new Nodo(prioridad); nuevo->anterior = maximo; maximo->siguiente = nuevo; maximo = nuevo; } else { for (Nodo * actual = minimo; actual != nullptr; actual = actual->siguiente) { if (actual->prioridad >= prioridad) { Nodo * nuevo = new Nodo(prioridad); nuevo->siguiente = actual; nuevo->anterior = actual->anterior; actual->anterior->siguiente = nuevo; actual->anterior = nuevo; break; } } } }