Un conjunto de reales se puede ver como un vector dinámico que no tiene elementos repetidos y sus elementos están ordenados.
Una instancia del tipo de datos abstracto Conjunto de reales es un conjunto de números de tipo float.
El número de elementos del conjunto se denomina cardinal o tamaño del conjunto. Un conjunto de tamaño cero se denomina vacío.
Lo podemos representar como:
{e1,e2,e3...,en}
Donde n es el número de elementos del conjunto. La eficiencia en espacio es O(n).
Dentro del TDA Conjunto de reales hemos propuesto las siguientes primitivas :
· Conjunto_Reales ( ) -> constructor del TDA, nos crea un conjunto vacío.
· Bool posicion_elemento (int& pos, float val) const -> localizador de una posición en el conjutno, nos dice si el valor val está en el conjutno, devolviendo en pos la posición donde está en caso de devolver true o donde debería insertarse en el caso de devolver false.
PARÁMETROS : val -> valor del índice a localizar en el conjunto.
pos -> parámetro pasado por referencia.
· Bool insertar (float f) -> añade un elemento al conjunto, devuelve true si el número de elementos ha aumentado, y false en el caso de que el elemento ya estaba en el conjunto.
PARÁMETROS : f -> valor a insertar en el conjunto.
· Bool borrar (float f) -> elimina un elemento al conjunto, devuelve true si el número de elementos ha disminuido, y false en el caso de que el elemento no estuviera en el conjunto.
PARÁMETROS : f -> valor a eliminar del conjunto.
· Bool pertenece (float f) const -> consulta la existencia de un elemento en el conjunto.
PARÁMETROS : f -> valor a consultar en el conjunto.
· Float elemento (int i) const -> devuelve el valor i-ésimo del conjunto.
PARÁMETROS : i -> indica el elemento del conjunto que queremos obtener.
PRECONDICIÓN : 0 <= i < size ();
· Bool vacio () const -> nos dice si el conjunto está vacío (size () == 0).
· Int size () const -> devuelve el número de elementos del conjunto, es decir, el cardinal.
Escribir los elementos de un conjunto
Esta función nos va imprimiendo en pantalla cada elemento del conjunto.
Conjunto_Reales c;
void Imprimir (Conjunto_Reales c)
{
if (c.vacio())
return;
else
{
for (int i = 0; i < c.size(); i++)
{
float x=c.elemento(i);
cout << x << ", ";
}
cout << endl;
}
}
El conjunto de reales tiene un vector dinámico v, este vector simula el comportamiento del conjunto. Tenemos también como siempre el cardinal o tamaño del conjunto que viene determinado por la variable nelementos.
 |
Vamos a ver la especificación tanto de la función de abstracción como del invariante de la representación del conjunto de reales:
Función de Abstracción
Un objeto válido rep del TDA Conjunto de reales representa al vector :
{ rep.v[0], rep.v[1], ..., rep.v[rep.nelementos] }
Invariante de Representación
Un objeto válido rep del TDA Conjunto de reales debe cumplir:
- rep.v.size () >= rep.nelementos.
- rep.nelementos >= 0.
- rep.v[i] < rep.v[j] para todo i, j tal que 0 <= i < j < rep.nelementos.
De manera que la clase Conjunto_Reales en C++ tendría el siguiente aspecto:
Class Conjunto_Reales
{
Public:
Conjunto_Reales ();
bool insertar (float f);
bool borrar (float f);
bool pertenece (float f) const;
float elemento (int i) const;
bool vacio () const;
int size () const;
Private:
Vector_Dinamico v;
int nelementos;
bool posicion_elemento (int& pos, float val) const;
}
Pasemos ahora a ver la implementación de cada una de las primitivas enunciadas con anterioridad en C++:
Conjunto_Reales::Conjunto_Reales()
{
nelementos = 0;
}
bool Conjunto_Reales::posicion_elemento(int& pos, int val) const
{
int izq=0, der=nelementos-1,centro;
while (der-izq>=0)
{
centro=(izq+der)/2;
if (val<v[centro])
der=centro-1;
else if (val>v[centro])
izq=centro+1;
else {
pos=centro;
return true;
}
}
pos= izq;
return false;
}
bool Conjunto_Reales::insertar(float f)
{
int pos;
if (posicion_elemento(pos,f))
return false;
else {
if (v.size()==nelementos)
if (v.size()==0)
v.resize(1);
else v.resize(2*v.size());
for (int j=nelementos; j>pos; --j)
v[j]=v[j-1];
v[pos]= f;
nelementos++;
return true;
}
}
bool Conjunto_Reales::borrar(float f)
{
int pos;
if (posicion_elemento(pos,f))
{
nelementos--;
for (int j=pos;j<nelementos;++j)
[j]=v[j+1];
if (nelementos<v.size()/4)
v.resize(v.size()/2);
return true;
}
else return false;
}
bool Conjunto_Reales::pertenece(float f) const
{
int pos;
return posicion_elemento(pos,f);
}
float Conjunto_Reales::elemento(int i) const
{
assert(0<=i && i<=v.size());
return v[i];
}
bool Conjunto_Reales::vacio() const
{
return nelementos == 0;
}
int Conjunto_Reales::size() const
{
return nelementos;
}