← Volver a los ejercicios

Ejercicios sobre las implementaciones: concatenar dos colas

Otra operación para la cola sobre nodos: c.concatenar(d) pone todos los elementos de d detrás de los de c, en su orden, y deja d vacía. Como es un método de la clase, ve los punteros de las dos colas. Las colas de prueba son c = ⟨5, 2⟩ y d = ⟨9, 4, 7⟩.

1. El resultado

void concatenar(Cola &otra) {
  if (otra.cabeza != NULL) {
    if (ultimo == NULL) {
      cabeza = otra.cabeza;
    } else {
      ultimo->siguiente = otra.cabeza;
    }
    ultimo = otra.ultimo;
    n = n + otra.n;
    otra.cabeza = NULL;
    otra.ultimo = NULL;
    otra.n = 0;
  }
}
¿Cuánto vale d.tamano()?

2. Lo que cuesta

Con n = c.tamano() y m = d.tamano(), ¿cuánto cuesta en tiempo?

3. Con el contrato

Fuera de la clase solo se puede usar el contrato:

while (!d.vacia()) {
  c.encolar(d.frente());
  d.desencolar();
}

Sobre las mismas colas, ¿cuántos nodos se reservan con new y cuántos se liberan con delete?

¿Cuántos nodos se reservan con new?
¿Cuántos se liberan con delete?

4. Cuando c está vacía

Alguien simplifica el método y deja siempre ultimo->siguiente = otra.cabeza;, sin el if (ultimo == NULL). ¿Qué pasa con c vacía y d = ⟨9, 4, 7⟩?

5. Por qué vaciar d

¿Qué pasa si se quitan las tres últimas asignaciones, las que dejan d en cero?