Slides TD Parcial2-81-90

Vista previa del material en texto

Cadena � Destructor
▶ Una clase A en C++ siempre tiene un método destructor: ~A()
▶ El método destructor se invoca automáticamente cuando el
objeto se termina el scope del objeto.
▶ El método destructor también se invoca cuando el objeto se
destruye explícitamente con un delete.
▶ En general, si no usamos memoria dinámica de manera
explítica, no es necesario que implementemos el método.
▶ En cambio, si usamos new en nuestros métodos tenemos que
ocuparnos que toda la memoria que pedimos se libere con un
delete.
26
Cadena � Destructor
Se debe agregar el destructor a la interfaz de la clase:
1 class Cadena {
2 public:
3 Cadena();
4 int longitud() const;
5 int iesimo(int pos) const;
6 void agregarAtras(int e);
7 int sumar() const;
8 ~Cadena(); // Método destructor de Cadena
9
10 private:
11 // ...
12 }
27
Cadena � Destructor
Y se debe dar su implementación, asegurandose de liberar toda la
memoria del heap que se haya �pedido� para construir y modi�car el
objeto.
1 Cadena::~Cadena() {
2 nodo * actual = primero;
3 while (actual != nullptr) {
4 nodo* sig = actual->siguiente;
5 delete actual;
6 actual = sig;
7 }
8 primero = nullptr;
9 }
28
Cadena � estructura alternativa
1 private:
2 struct nodo {
3 //...
4 };
5 nodo* primero;
6 nodo* ultimo;
7 int _longitud;
8 // Rep:
9 // - La cadena de nodos está correctamente conectada
10 // (no tiene ciclos)
11 // - _longitud coincide con la cantidad de objetos nodo
12 // encadenados
13 // - ultimo coincide con el valor del último nodo*
14 // alcanzable desde primero
15 };
¾Cómo afecta a los algoritmos vistos?
29
Cadena � Algoritmos
1 int Cadena::longitud() const {
2 return _longitud;
3 }
4
5 void Cadena::agregarAtras(int e) const {
6 nodo* nuevo = new nodo(e);
7 if (ultimo != nullptr) {
8 ultimo->siguiente = nuevo;
9 ultimo = nuevo;
10 } else {
11 primero = nuevo;
12 ultimo = nuevo;
13 }
14 _longitud++;
15 }
30
Cadena � Complejidad (mejorada)
Algoritmo Complejidad
Cadena() Θ(1)
longitud() Θ(1)
iesimo(pos) Θ(n)
agregarAtras(e) Θ(1)
sumar() Θ(n)
31
C++: Recordemos Cadena
1 class Cadena {
2 public:
3 Cadena(); // Post: *this.longitud() = 0
4
5 int longitud() const;
6 int iesimo(int pos) const;
7 // Pre: 0 <= pos < *this.longitud()
8
9 void agregarAtras(int e);
10 // Post: this.longitud() = *this_0.longitud()+1 and
11 // *this.iesimo(*this.longitud()-1) = e and
12 // (ParaTodo i:int) 0 <= i < *this_0.longitud()
13 // => *this.iesimo(i) = *this_0.iesimo(i)
14 //...
3
C++: recorrer elementos
Yo usuario de Cadena, ¾cómo la recorro de principio a �n?
1 int contar_pares(const Cadena& c) {
2 return res;
3 for (int i = 0; i < c.longitud(); i++){
4 if (c.iesimo(i) % 2 == 0);
5 res++;
6 }
7 return res;
8 }
¾Qué complejidad tiene esto?
4
C++: Eliminar elemento
1 class Cadena {
2 public:
3 // ...
4
5 void eliminar_posicion(int pos);
6 // Pre: 0 <= pos < *this.longitud()
7 // Post: this.longitud() = *this_0.longitud()-1 and
8 // (ParaTodo i:int) (0 <= i < pos
9 // => *this.iesimo(i) = *this_0.iesimo(i))
10 // and (pos <= i < *this.longitud())
11 // => *this.iesimo(i) = *this_0.iesimo(i+1)
¾Qué complejidad tiene esta operación?
5
Cadena: eliminar elementos
Yo usuario de Cadena, ¾cómo elimino ciertos elementos?
1 int solo_pares(Cadena& c) {
2 int i = 0;
3 while (i < c.longitud()){
4 if (c.iesimo(i) % 2 != 0);
5 c.eliminar_posicion(i);
6 else
7 i++;
8 }
9 return res;
10 }
Nuevamente, ¾qué complejidad tiene esto?
6