=================================================================
Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I
Examen final - 2023/2024
23 de enero de 2024
Ejercicio 1
Borrador
=================================================================



Las siguientes dos soluciones tienen coste temporal en el peor caso O(a + b).

En la segunda solucion, se implementa y utiliza una funcion auxiliar insertarAlFinal
con el codigo que se repite dos veces en la primera solucion.

En ambas se supone que se dispone de los siguientes constructores (en el examen no se pedian):

Conjunto::Nodo::Nodo(int d, Nodo * s)
   : dato{d}, siguiente{s} {
}

Conjunto::Conjunto() : primero{nullptr} {
}


Solucion 1
==========

Conjunto Conjunto::diferenciaSimetrica(const Conjunto & c2) const {
   Conjunto c3;
   Nodo * n1 = primero,
      * n2 = c2.primero,
      * ultimo;
      
   while (n1 != nullptr || n2 != nullptr)
      if (n1 == nullptr || (n2 != nullptr && n2->dato < n1->dato)) { // Insertar n2->dato
	 if (c3.primero == nullptr) {
	    c3.primero = new Nodo(n2->dato, nullptr);
	    ultimo = c3.primero;
	 } else {
	    ultimo->siguiente = new Nodo(n2->dato, nullptr);
	    ultimo = ultimo->siguiente;
	 }
	 n2 = n2->siguiente;
      } else if (n2 == nullptr || n1->dato < n2->dato) { // Insertar n1->dato
	 if (c3.primero == nullptr) {
	    c3.primero = new Nodo(n1->dato, nullptr);
	    ultimo = c3.primero;
	 } else {
	    ultimo->siguiente = new Nodo(n1->dato, nullptr);
	    ultimo = ultimo->siguiente;
	 }
	 n1 = n1->siguiente;
      } else { // Pasar
	 n1 = n1->siguiente;
	 n2 = n2->siguiente;
      }
   return c3;
}

Solucion 2
==========

void Conjunto::insertarAlFinal(Nodo * & ultimo, int dato) {

   if (primero == nullptr) {
      primero = new Nodo(dato, nullptr);
      ultimo = primero;
   } else {
      ultimo->siguiente = new Nodo(dato, nullptr);
      ultimo = ultimo->siguiente;
   }
   
}
   
Conjunto Conjunto::diferenciaSimetrica(const Conjunto & c2) const {
   Conjunto c3;
   Nodo * n1 = primero,
      * n2 = c2.primero,
      * ultimo;
      
   while (n1 != nullptr || n2 != nullptr)
      if (n1 == nullptr || (n2 != nullptr && n2->dato < n1->dato)) {
	 c3.insertarAlFinal(ultimo, n2->dato);
	 n2 = n2->siguiente;
      } else if (n2 == nullptr || n1->dato < n2->dato) {
	 c3.insertarAlFinal(ultimo, n1->dato);
	 n1 = n1->siguiente;
      } else {
	 n1 = n1->siguiente;
	 n2 = n2->siguiente;
      }
   return c3;
}