← Volver a los ejercicios

Las tres implementaciones enlazadas: sumar sin perder nada

Tres funciones suman los elementos de un TAD sobre nodos usando solo su contrato, y lo dejan como estaba. Cada TAD tiene n = 12 elementos. Un avance es una ejecución de actual = actual->siguiente en el ciclo de nodoEn, que es lo que usa obtener(p) para llegar a la posición p.

1. La lista, por posición

int sumar(Lista &l) {
  int suma = 0;
  int p = 0;
  while (p < l.tamano()) {
    suma = suma + l.obtener(p);
    p = p + 1;
  }
  return suma;
}
¿Cuántos avances hace en total?

2. La cola, dándole la vuelta

int sumar(Cola &c) {
  int suma = 0;
  int k = 0;
  int n = c.tamano();
  while (k < n) {
    suma = suma + c.frente();
    c.encolar(c.frente());
    c.desencolar();
    k = k + 1;
  }
  return suma;
}
¿Cuántos avances hace?
¿Cuántos nodos reserva con new?

3. La pila, con una auxiliar

int sumar(Pila &p) {
  Pila aux;
  int suma = 0;
  while (!p.vacia()) {
    suma = suma + p.tope();
    aux.apilar(p.tope());
    p.desapilar();
  }
  while (!aux.vacia()) {
    p.apilar(aux.tope());
    aux.desapilar();
  }
  return suma;
}
¿Cuántas llamadas a apilar hace, sumando las dos pilas?

4. ¿Cuál es Θ(n²) en tiempo?