Pero no podemos saber de antemano el tamaño máximo de los conjuntos que vamos a usar, si ponemos muy grande el tamaño máximo podemos deperdiciar memoria, pero si lo ponemos muy pequeño pueden darse muchos casos en los cuales no sea suficiente este tamaño. La anterior versión no hace un uso racional de la memoria.
Por ello, vamos a implementar un versión de Conjunto basada en el Arreglo que nos permita tener el tamaño justo de memoria que necesitamos, este sería un conjunto dinámico. Veamos:
conjuntoDin.h
Autor: L. Alejandro Bernal R.
Fecha: 2000.12.01
Descripción: Implementa el TDA Conjunto mediante un arreglo dinámico.
*/
#ifndef _CONJUNTODIN_H_
#define _CONJUNTODIN_H_
#include <stdlib.h>
#include "arregloExc.h"
/*
TDA Conjunto
Descripción: Un conjunto es una colleción de elementos del mismo tipo que no están repetidos.
Invariante: Conjunto=<elem[0],...,elem[n-1]> y (Para todo i,0 <= i<n,elem[i] pertenece a TipoB y (Para todo ,0 <= j<n y j != i,elem[i] != elem[j])) ))
*/
template<class TipoB>
class Conjunto
{
private:
// Atributos:
Arreglo<TipoB> elem; // Elementos del conjunto guardados en un arreglo dinámico.
public:
// Operaciones:
/*
Operación adic
Descripción: Adiciona un elemento al conjunto.
Descripción operacional: adic: Conjunto x TipoB -> Conjunto
Precondición: conjunto=<elem[0],...,elem[n-1]> y nuevo pertenece a TipoB
Poscondición: ( (Para todo i,0 <= i<n,nuevo != elem[i])) -> conjunto=<elem[0],...,elem[n-1],nuevo> ))y ( ( Existe un i,0 <= i<n,nuevo=elem[i])) -> conjunto=<elem[0],...,elem[n-1]> ))
*/
void adic(TipoB nuevo);
/*
Operación pertenece
Descripción: Dice si el elemento está en el conjunto.
Descripción operacional: pertenece: Conjunto x TipoB -> Booleano
Precondición: el pertenece a TipoB
Poscondición: pertenece=( Existe un elem pertenece a conjunto,elem=el))
*/
int pertenece(TipoB el);
/*
Operación +
Descripción: Une dos conjuntos en un tercero, este último tiene todos los elementos de los conjuntos originarios.
Descripción operacional: +: Conjunto x Conjunto -> Conjunto
Precondición: conjunto=<e[0],...,e[n-1]> y otro pertenece a Conjunto y otro=<o[0],...,o[n-1]>
Poscondición: +=<e[0],...,e[n-1],o[0],...,o[n-1]>
*/
Conjunto operator +(Conjunto &otro);
/*
Operación *
Descripción: La intersección de dos conjuntos es otro conjunto que solo tiene los elementos comunes.
Descripción operacional: *: Conjunto x Conjunto -> Conjunto
Precondición: conjunto=<e[0],...,e[n-1]> y otro pertenece a Conjunto y otro=<o[0],...,o[n-1]>
Poscondición: *=<elem|Pata todo elem,elem pertenece a conjunto y elem pertenece a otro>
*/
Conjunto operator *(Conjunto &otro);
}; // template<class TipoB> class Conjunto
/*
Operación adic
Descripción: Adiciona un elemento al conjunto.
Descripción operacional: adic: Conjunto x TipoB -> Conjunto
Precondición: conjunto=<elem[0],...,elem[n-1]> y nuevo pertenece a TipoB
Poscondición: ( (Para todo i,0 <= i<n,nuevo != elem[i])) -> conjunto=<elem[0],...,elem[n-1],nuevo> ))y ( ( Existe un i,0 <= i<n,nuevo=elem[i])) -> conjunto=<elem[0],...,elem[n-1]> ))
*/
template<class TipoB>
void Conjunto<TipoB>::adic(TipoB nuevo)
{
if(pertenece(nuevo)){
return;
}
elem[elem.tam()] = nuevo;
}
/*
Operación pertenece
Descripción: Dice si el elemento está en el conjunto.
Descripción operacional: pertenece: Conjunto x TipoB -> Booleano
Precondición: el pertenece a TipoB
Poscondición: pertenece=( Existe un elem pertenece a conjunto,elem=el))
*/
template<class TipoB>
int Conjunto<TipoB>::pertenece(TipoB el)
{
for(int i = 0; i < elem.tam(); i++){
if(el == elem[i]){
return 1;
}
}
return 0;
}
/*
Operación +
Descripción: Une dos conjuntos en un tercero, este último tiene todos los elementos de los conjuntos originarios.
Descripción operacional: +: Conjunto x Conjunto -> Conjunto
Precondición: conjunto=<e[0],...,e[n-1]> y otro pertenece a Conjunto y otro=<o[0],...,o[n-1]>
Poscondición: +=<e[0],...,e[n-1],o[0],...,o[n-1]>
*/
template<class TipoB>
Conjunto<TipoB> Conjunto<TipoB>::operator +(Conjunto &otro)
{
Conjunto nuevo; // Conjunto unión.
int i; // Recorre los conjuntos
for(i = 0; i < elem.tam(); i++){
nuevo.adic(elem[i]);
}
for(i = 0; i < otro.elem.tam(); i++){
nuevo.adic(otro.elem[i]);
}
return nuevo;
}
/*
Operación *
Descripción: La intersección de dos conjuntos es otro conjunto que solo tiene los elementos comunes.
Descripción operacional: *: Conjunto x Conjunto -> Conjunto
Precondición: conjunto=<e[0],...,e[n-1]> y otro pertenece a Conjunto y otro=<o[0],...,o[n-1]>
Poscondición: *=<elem|\forall elem,elem pertenece a conjunto y elem pertenece a otro>
*/
template <class TipoB> Conjunto<TipoB> Conjunto<TipoB>::operator *(Conjunto &otro)
{
Conjunto nuevo; // Conjunto intersección.
for(int i = 0; i < elem.tam(); i++){
if(otro.pertenece(elem[i])){
nuevo.adic(elem[i]);
}
}
return nuevo;
}
#endif
//------- Fin conjunto.h
La clase Arreglo encapsula todos los detalles de implementación, tanto que no es necesario para nuestra implementación dinámica de conjunto estar pensando que por debajo hay un apuntadores o no.
Una TDA bien diseñado y un clase bien implementada se reconocen por que ocultan todos los detalles de la implementación.
