Algoritmos y Estructuras de Datos - VJ1215

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

De las siguientes soluciones, tres son incorrectas, contienen errores de programación básica, piensa cuáles son. La otra es ineficiente, piensa cuál es y por qué. Supón que en todas ellas se hace uso de un método insertar implementado previamente, cuyo coste es O(1) cuando el elemento insertado es el nuevo mínimo o el nuevo máximo.

Ejemplo de solución incorrecta 1

void ColaDePrioridadDeDobleFin::unir(const ColaDePrioridadDeDobleFin & cola1,
                                     const ColaDePrioridadDeDobleFin & cola2) {

   vaciar();

   Nodo * nodo1 = cola1.minimo, * nodo2 = cola2.minimo;

   while (nodo1 != nullptr && nodo2 != nullptr)
      if (nodo1->prioridad <= nodo2->prioridad) {
	 insertar(nodo1->prioridad);
	 nodo1 = nodo1->siguiente;
      } else {
	 insertar(nodo2->prioridad);
	 nodo2 = nodo2->siguiente;
      }
   
}

¿Por qué es incorrecta?

Cuando se alcanza el final de una de las dos colas, pueden quedar elementos en la otra.

Ejemplo de solución incorrecta 2

void ColaDePrioridadDeDobleFin::unir(const ColaDePrioridadDeDobleFin & cola1,
                                     const ColaDePrioridadDeDobleFin & cola2) {

   vaciar();

   Nodo * nodo1 = cola1.minimo, * nodo2 = cola2.minimo;

   while (nodo1 != nullptr || nodo2 != nullptr)
      if (nodo1->prioridad <= nodo2->prioridad) {
	 insertar(nodo1->prioridad);
	 nodo1 = nodo1->siguiente;
      } else {
	 insertar(nodo2->prioridad);
	 nodo2 = nodo2->siguiente;
      }
   
}

¿Por qué es incorrecta?

Si se alcanza el final de una de las colas antes que el final de la otra, eso va a fallar.

Ejemplo de solución incorrecta 3

void ColaDePrioridadDeDobleFin::unir(const ColaDePrioridadDeDobleFin & cola1,
                                     const ColaDePrioridadDeDobleFin & cola2) {

   vaciar();

   Nodo * nodo1 = cola1.minimo;
   while (nodo1 != nullptr) {
      insertar(nodo1->prioridad);
      nodo1 = nodo1->siguiente;
   }
   
   Nodo * nodo2 = cola2.minimo;
   while (nodo2 != nullptr) {
      insertar(nodo2->prioridad);
      nodo2 = nodo2->siguiente;
   }
   
}

¿Por qué es incorrecta?

Cada llamada a insertar en el primer bucle tiene coste O(1), pera cada llamada a insertar en el segundo bucle tiene coste O(n). Por tanto, esta solución tiene coste O(n²). Esto sucede, por ejemplo, si tenemos dos colas de talla n y todos los elementos de la segunda cola deben situarse justo antes del último elemento de la primera cola: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] y [90, 91, 92, 93, 94, 95, 96, 97, 98, 99].

Ejemplo de solución incorrecta 4

void ColaDePrioridadDeDobleFin::unir(const ColaDePrioridadDeDobleFin & cola1,
                                     const ColaDePrioridadDeDobleFin & cola2) {

   vaciar();
   
   return unir(cola1.minimo, cola2.minimo);
   
}

void ColaDePrioridadDeDobleFin::unir(Nodo * nodo1,
				     Nodo * nodo2) {
   
   if (nodo1 != nullptr || nodo2 != nullptr)
      if (nodo2 == nullptr) {
	 insertar(nodo1->prioridad);
	 return unir(nodo1->siguiente, nodo2);
      } else if (nodo1 == nullptr) {
	 insertar(nodo2->prioridad);
	 return unir(nodo1, nodo2->siguiente);
      } else if (nodo1->prioridad <= nodo2->prioridad) {
	 insertar(nodo1->prioridad);
	 return unir(nodo1->siguiente, nodo2);
      } else {
	 insertar(nodo2->prioridad);
	 return unir(nodo1, nodo2->siguiente);
      }
   
}

¿Por qué es incorrecta?

Sobra return delante de cada llamada a un método que no devuelve nada porque es void.