Curso 2023/2024
Las siguientes soluciones tiene coste temporal O(n) siendo n la talla de la cola de prioridad.
Verifica que tu solución funciona correctamente en los siguientes casos:
si la cola de prioridad estaba vacía;
si había un solo dato;
si se elimina el mínimo; o
si se elimina el máximo.
void ColaDePrioridadDeDobleFin::eliminar(int prioridad) { for (Nodo * actual = minimo; actual != nullptr && actual->prioridad <= prioridad; actual = actual->siguiente) { if (actual->prioridad == prioridad) { if (minimo == maximo) { minimo = maximo = nullptr; } else if (actual == minimo) { minimo = minimo->siguiente; minimo->anterior = nullptr; } else if (actual == maximo) { maximo = maximo->anterior; maximo->siguiente = nullptr; } else { actual->anterior->siguiente = actual->siguiente; actual->siguiente->anterior = actual->anterior; } delete actual; laTalla--; return; } } throw string("Intentando eliminar un elemento que no esta"); }
Observa bien las asignaciones en que hemos de poner nullptr
donde hasta ahora teniamos la dirección del nodo eliminado: eso no
sucede automáticamente al eliminarlo.
Pregunta 1 ¿Sería mejor comprobar si es el mínimo o el máximo antes del bucle, en vez de hacerlo en cada iteración?
Respuesta 1 No se hace en cada iteración, está dentro del bucle pero solo se hace una vez, cuando se encuentra el dato a eliminar.
Pregunta 2 En el caso minimo ==
maximo
, ¿no faltaría comprobar si hay un solo elemento o hay
varios elementos iguales?
Respuesta 2 Si el contenido de la cola de
prioridad son n elementos iguales, hay n nodos; si n > 1,
minimo
es la dirección de un
nodo, maximo
es la dirección de otro nodo, y
no se cumple minimo == maximo
. Si, en ese
bucle, minimo == maximo
, es porque hay un
solo nodo.
void ColaDePrioridadDeDobleFin::eliminar(int prioridad) { eliminar(prioridad, minimo); } void ColaDePrioridadDeDobleFin::eliminar(int prioridad, Nodo * inicio) { if (inicio == nullptr || inicio->prioridad > prioridad) throw string("Intentando eliminar un elemento que no esta"); if (inicio->prioridad == prioridad) { if (inicio->siguiente != nullptr) inicio->siguiente->anterior = inicio->anterior; else maximo = inicio->anterior; if (inicio->anterior != nullptr) inicio->anterior->siguiente = inicio->siguiente; else minimo = inicio->siguiente; delete inicio; laTalla--; } else eliminar(prioridad, inicio->siguiente); }