Algoritmos y Estructuras de Datos - VJ1215

Solución del ejercicio 2.f del tema 2

Las siguientes soluciones tienen coste temporal en el peor caso O(n) y en el mejor caso O(1), siendo n la talla de la cola.

Solución recursiva 1

int Cola::buscarPosicion(int dato) const {

   return buscarPosicion(dato, primero);

}

int Cola::buscarPosicion(int dato, Nodo * n) const {

   if (n == nullptr)
      return -1;
  
   if (n->dato == dato)
      return 0;

   int posicion = buscarPosicion(dato, n->siguiente);

   return (posicion == -1) ? -1 : posicion + 1;
   // Equivale a: if (posicion == -1) return -1; else return posicion + 1;

}

Solución recursiva 2

int Cola::buscarPosicion(int dato) const {

   return buscarPosicion(dato, primero, 0);

}

int Cola::buscarPosicion(int dato, Nodo * n, int contador) const {

   if (n == nullptr)
      return -1;
  
   if (n->dato == dato)
      return contador;

   return buscarPosicion(dato, n->siguiente, contador + 1);

}