=================================================================
Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I
Evaluacion continua - 2022/2023
24 de octubre de 2022
Ejercicio 1
Borrador
=================================================================

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

En las tres primeras se hace uso de los siguientes constructores:

Conjunto::Nodo::Nodo(int elDato)
   : dato{elDato}, siguiente{nullptr} {
}

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

En las dos ultimas, el constructor de Nodo que se usa es:

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


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

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


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

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

void Conjunto::insertarAlFinal(int dato, Nodo * & ultimo) {
   if (primero == nullptr) {
      primero = new Nodo(dato);
      ultimo = primero;
   } else {
      ultimo->siguiente = new Nodo(dato);
      ultimo = ultimo->siguiente;
   }
}


Solucion 3
==========

Conjunto Conjunto::interseccion(const Conjunto & c2) const {
   Conjunto resultado;
   interseccion(primero, c2.primero, resultado.primero);
   return resultado;
}

void Conjunto::interseccion(Nodo * n1, Nodo * n2, Nodo * & n) const {
   if (n1 == nullptr || n2 == nullptr)
      return;
   if (n1->dato < n2->dato)
      interseccion(n1->siguiente, n2, n);
   else if (n2->dato < n1->dato)
      interseccion(n1, n2->siguiente, n);
   else {
      n = new Nodo(n1->dato);
      interseccion(n1->siguiente, n2->siguiente, n->siguiente);
   }
}


Solucion 4
==========

Conjunto Conjunto::interseccion(const Conjunto & c2) const {
   Conjunto resultado;
   interseccion(primero, c2.primero, resultado);
   return resultado;
}

void Conjunto::interseccion(Nodo * n1, Nodo * n2, Conjunto & resultado) const {
   if (n1 == nullptr || n2 == nullptr)
      return;
   if (n1->dato < n2->dato)
      interseccion(n1->siguiente, n2, resultado);
   else if (n2->dato < n1->dato)
      interseccion(n1, n2->siguiente, resultado);
   else {
      interseccion(n1->siguiente, n2->siguiente, resultado);
      resultado.primero = new Nodo(n1->dato, resultado.primero);
   }
}


Solucion 5
==========

Conjunto Conjunto::interseccion(const Conjunto & c2) const {
   Conjunto alReves, resultado;
   Nodo * n1 = primero;
   Nodo * n2 = c2.primero;
   while (n1 != nullptr && n2 != nullptr)
      if (n1->dato < n2->dato)
	 n1 = n1->siguiente;
      else if (n2->dato < n1->dato)
	 n2 = n2->siguiente;
      else {
	 alReves.primero = new Nodo(n1->dato, alReves.primero);
	 n1 = n1->siguiente;
	 n2 = n2->siguiente;
      }
   for (Nodo * n = alReves.primero; n != nullptr; n = n->siguiente)
      resultado.primero = new Nodo(n->dato, resultado.primero);
   return resultado;
}