Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2023/2024

Ejemplos de errores en el ejercicio 6.d del tema 2

La siguiente implementación contiene 4 errores: corrígelos.

void ColaDePrioridadDeDobleFin::eliminar(int prioridad) {
   if (minimo == nullptr) {
      throw("Intentando eliminar en una cola de prioridad vacia");
   } else if (minimo->prioridad == prioridad) {
      Nodo * aux = minimo->siguiente;
      delete minimo;
      minimo = aux;
      laTalla--;
   } else if (maximo->prioridad == prioridad) {
      Nodo * aux = maximo->anterior;
      delete maximo;
      maximo = aux;
      laTalla--;
   } else {
      for (Nodo * aux = minimo; aux != nullptr; aux = aux->siguiente) {
	 if (aux->prioridad == prioridad) {
	    Nodo * basura =  aux;
	    basura->anterior->siguiente = basura->siguiente;
	    basura->siguiente->anterior = basura->anterior;
	    delete basura;
	    laTalla--;
	 }
      }
      throw("Intentando eliminar un elemento que no esta");
   }
}
      

¿Por qué es incorrecta?

  1. En el bucle tras ejecutar delete basura no podemos avanzar con aux = aux->siguiente.

  2. No se está tratando bien el caso en que había un solo dato y se elimina, con lo que deben cambiar tanto minimo como maximo.

  3. Tras eliminar el mínimo falta que el nuevo mínimo tenga nullptr como valor de anterior.

  4. Tras eliminar el máximo falta que el nuevo máximo tenga nullptr como valor de siguiente.

A continuación se muestra una forma de arreglar esos errores:

void ColaDePrioridadDeDobleFin::eliminar(int prioridad) {
   if (minimo == nullptr) { // Habia cero
      throw("Intentando eliminar en una cola de prioridad vacia");
   } else if (minimo == maximo && minimo->prioridad == prioridad) { // Habia uno y se elimina
      delete minimo;
      minimo = nullptr;
      maximo = nullptr;
      laTalla = 0;
   } else if (minimo->prioridad == prioridad) { // Habia mas de uno y se elimina el primero
      Nodo * aux = minimo->siguiente;
      delete minimo;
      minimo = aux;
      minimo->anterior = nullptr;
      laTalla--;
   } else if (maximo->prioridad == prioridad) { // Habia mas de uno y se elimina el ultimo
      Nodo * aux = maximo->anterior;
      delete maximo;
      maximo = aux;
      maximo->siguiente = nullptr;
      laTalla--;
   } else { // Habia mas de uno y se elimina uno que no es el primero ni el ultimo
      for (Nodo * aux = minimo; aux != nullptr; aux = aux->siguiente) {
	 if (aux->prioridad == prioridad) {
	    Nodo * basura =  aux;
	    basura->anterior->siguiente = basura->siguiente;
	    basura->siguiente->anterior = basura->anterior;
	    delete basura;
	    laTalla--;
	    return;
	 }
      }
      throw("Intentando eliminar un elemento que no esta");
   }
}