Algoritmos y Estructuras de Datos - VJ1215

Ejemplos de errores en el ejercicio 3.c del tema 2

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

Solución

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