Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2023/2024

Ejemplos de errores en el ejercicio 6.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:

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

¿Por qué es incorrecta?

  1. En el caso minimo == nullptr (dentro del primer if) se están creando dos nodos en vez de uno.

  2. Falta el else asociado al primer if para que no vuelva a insertar.

  3. 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.

  4. 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.

  5. 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).

  6. Falta terminar el bucle tras insertar el nuevo nodo para que no siga insertando.

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