=================================================================
Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I
Evaluacion continua - 2023/2024
17 de noviembre de 2023
Ejercicio 1
Borrador
=================================================================


En este ejercicio se dejaba libertad para que la solucion fuese recursiva o no.
Se muestran a continuacion dos soluciones posibles, una no recursiva y una recursiva.


Coste de ambas soluciones
=========================

Coste temporal en el peor caso: O(a + b)


Constructores
=============

Conjunto::Nodo::Nodo(float elDato, Nodo * elSiguiente)
   : dato{elDato}, siguiente{elSiguiente} {
}

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


Solucion no recursiva
=====================

void Conjunto::diferenciaSimetrica(const Conjunto & c2) {
   Nodo * n1 = primero,
      * n2 = c2.primero,
      * anterior;
      
   while (n2 != nullptr)
      if (n1 == nullptr || n2->dato < n1->dato) { // Insertar n2->dato
	 if (n1 == primero) {
	    primero = new Nodo(n2->dato, primero);
	    anterior = primero;
	 } else {
	    anterior->siguiente = new Nodo(n2->dato, n1);
	    anterior = anterior->siguiente;
	 }
	 n2 = n2->siguiente;
      } else if (n1->dato == n2->dato) { // Eliminar n1->dato
	 Nodo * basura = n1;
	 if (n1 == primero)
	    primero = n1->siguiente;
	 else
	    anterior->siguiente = n1->siguiente;
	 n1 = n1->siguiente;
	 n2 = n2->siguiente;
	 delete basura;
      } else { // Conservar n1->dato
	 anterior = n1;
	 n1 = n1->siguiente;
      }
}


Solucion recursiva
==================

void Conjunto::diferenciaSimetrica(const Conjunto & c2) {
   diferenciaSimetrica(primero, c2.primero);
}

void Conjunto::diferenciaSimetrica(Nodo * & n1, Nodo * n2) {
   if (n2 != nullptr)
      if (n1 == nullptr || n2->dato < n1->dato) { // Insertar n2->dato
	 n1 = new Nodo(n2->dato, n1);
	 diferenciaSimetrica(n1->siguiente, n2->siguiente);
      } else if (n1->dato == n2->dato) { // Eliminar n1->dato
	 Nodo * basura = n1;
	 n1 = n1->siguiente;
	 delete basura;
	 diferenciaSimetrica(n1, n2->siguiente);
      } else // Conservar n1->dato
	 diferenciaSimetrica(n1->siguiente, n2);
}