Un vector disperso no es más que un vector donde tenemos múltiples elementos dispersos en un rango amplio de su índice.
Una instancia v del tipo de datos abstracto Vector disperso sobre el tipo float es un array unidimensional con índices enteros positivos sin limitación de rango. Este tipo de dato se diseña especialmente para los problemas en los que el vector almacena en la mayoría de sus posiciones un valor predeterminado d, mientras que modifica un pequeño conjunto de ellas. Lo podemos representar como:
{(i[0],v[0]),(i[1],v[1]),...,(i[n-1],v[n-1]),(*,d)}
Donde en el vector hay n posiciones (desde 0 a n-1), y donde cada índice i del vector tiene asociado un valor v, d es el valor por defecto que tienen los índices que no se encuentran en i.
La eficiencia en espacio es O(n), donde n es el número de posiciones del vector que almacena un valor distinto de d .
Dentro del TDA Vector disperso hemos propuesto las siguientes primitivas, aunque esto no quiere decir que sean las mejores ni las más adecuadas para todos los casos:
· Vector_disperso () -> constructor primitivo, nos crea un vector disperso vacío.
· Vector_disperso (const Vector_disperso& orig) -> constructor de copia, crea un vector disperso que es copia del vector disperso orig.
PARÁMETROS : orig -> vector disperso que se copia.
· Int nelementos () const -> devuelve el número de elementos del vector disperso.
· Bool posicion_indice (int& pos, int i) const -> localizador de una posición en el vector disperso, nos dice si la posición i está en el vector, 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 : i -> valor del índice a localizar en el vector.
pos -> parámetro pasado por referencia.
· Void expandir () -> aumenta la memoria reservada para el vector disperso.
POSTCONDICIÓN : si el número de elementos es 0, construye un vector con un elemento, si no, lo hace de tamaño 2*nelementos.
· Void contraer () -> disminuye la memoria reservada para el vector disperso.
PRECONDICIÓN : nelementos <= reservados / 2.
POSTCONDICIÓN : reservados vale la mitad y el vector disperso apunta a una zona de memoria con la mitad de capacidad.
· Vector_disperso& operator = (const Vector_disperso& orig) -> operador de asignación, copia en el vector disperso que hace la llamada el vector disperso orig.
PARÁMETROS : orig -> vector disperso que se copia.
· Float get_default () const -> devuelve el valor por defecto de las posiciones no asignadas en el vector disperso.
· Void set_default (float f) -> asigna un nuevo valor al valor por defecto del vector disperso.
PARÁMETROS : f -> nuevo valor por defecto en las posiciones no asignadas.
PRECONDICIÓN : el vector no puede tener ninguna posición asignada, por ejemplo, después de la creación..
· Float get (int i) const -> devuelve el valor almacenado en la posición i, si no se ha almacenado ninguno anteriormente, se devolverá el valor por defecto.
PARÁMETROS : i -> posición del vector a la que se accede.
· Void set (int i, float f) -> asigna un nuevo valor f en la posición i del vector.
PARÁMETROS : i -> posición del vector a la que se asigna un valor.
f -> valor a asignar a la posición i.
· ~Vector_disperso () -> destructor, elimina todos los elementos del vector, liberando los recursos usados.
En este apartado vamos a mostrar un ejemplo para que comprendamos el funcionamiento de las primitivas del TDA Vector disperso:
Averiguar el valor máximo en un vector disperso
Esta función recorre el vector disperso y nos devuelve el máximo del vector.
Vector_Disperso v;
float maximo ()
{
float max;
if (v.nelementos() == 0)
{
cerr << "Upsss máximo de???? asignamos cero" << endl;
max = 0.0;
}
else {
max = v.datos[0].valor;
for (int i = 1 ; i < v.nelementos(); i++)
if (max < v.datos[i].valor)
max = v.datos[i].valor;
}
return max;
}
El vector disperso se implementa como es obvio con un vector pero ese vector, el cual llamaremos datos, es un vector de una estructura llamada Elementos, la cual contiene un índice entero y un valor real, des este modo tenemos asociado a cada índice su valor.
Luego también el objeto vector disperso tiene una variable nelementos que nos indica el tamaño del vector, reservados que son las posiciones de memoria reservadas hasta el momento y que no tienen por qué estar todas completas, y por último el valor por defecto d.
 |
Vamos a especificar a continuación la función de abstracción y el invariante de la representación del vector disperso:
Función de Abstracción
Un objeto válido rep del TDA Vector disperso representa al vector :
{ ( rep.datos[0].indice, rep.datos[0].valor ) , ..., ( rep.datos[rep.nelementos-1].indice, rep.datos[rep.nelementos-1].valor ), (*, rep.valor_por_defecto) }
Invariante de Representación
Un objeto válido rep del TDA Vector disperso debe cumplir:
1. rep.nelementos >= 0.
2. rep.reservados >= 0.
3. rep.datos apunta a una zona de memoria con capacidad para albergar reservados valores de tipo Elemento.
4. 0 <= rep.datos[i].indice < rep.datos[j].indice para todo i,j tal que ;
0 <= i < j < rep.nelementos.
De manera que la clase Vector_Disperso en C++ tendría el siguiente aspecto:
Class Vector_Disperso
{
Public:
Vector_Disperso ();
Vector_Disperso (const Vector_Disperso& orig);
Vector_Disperso& operator= (const Vector_Disperso& original);
int nelementos () const;
float get_default () const;
void set_default (float f);
float get (int i) const;
void set (int i, float f);
~Vector_Disperso ();
Private:
struct Elemento
{
int indice;
float valor;
};
Elemento *datos;
int nelementos;
int reservados;
float valor_por_defecto;
bool posición_indice (int& pos, int i) const;
void expandir ();
void contraer ();
}
Pasemos ahora a ver la implementación de cada una de las primitivas enunciadas con anterioridad en C++:
bool Vector_Disperso::posicion_indice(int& pos, int i) const
{
int izq=0, der=nelementos-1,centro;
while (der-izq>=0)
{
centro=(izq+der)/2;
if (i<datos[centro].indice)
der=centro-1;
else if (i>datos[centro].indice)
izq=centro+1;
else {
pos=centro;
return true;
}
}
pos= izq;
return false;
}
void Vector_Disperso::expandir()
{
reservados= (nelementos==0)?1:nelementos*2;
Elemento * nuevos_datos= new float[reservados];
for (int j= 0; j<nelementos ;++j)
nuevos_datos[j]= datos[j];
delete[] datos;
datos= nuevos_datos;
}
void Vector_Disperso::contraer()
{
assert(nelementos<=reservados/2);
reservados= reservados/2;
Elemento * nuevos_datos= new float[reservados];
for (int j= 0; j<nelementos ;++j)
nuevos_datos[j]= datos[j];
delete[] datos;
datos= nuevos_datos;
}
Vector_Disperso::Vector_Disperso()
{
datos=0;
nelementos=reservados=0;
valor_por_defecto= 0.0;
}
Vector_Disperso::Vector_Disperso(const Vector_Disperso& orig)
{
valor_por_defecto= orig.valor_por_defecto;
reservados= nelementos= orig.nelementos;
if (nelementos>0)
{
datos= new Elemento[nelementos];
for (int i=0; i<nelementos;++i)
datos[i]= original.datos[i];
}
else datos=0;
}
Vector_Disperso& Vector_Disperso::operator= (const Vector_Disperso& original)
{
if (this!= &original)
{
if (reservados>0)
delete[] datos;
valor_por_defecto= orig.valor_por_defecto;
reservados= nelementos= orig.nelementos;
if (nelementos>0)
{
datos= new Elemento[nelementos];
for (int i=0; i<nelementos;++i)
datos[i]= original.datos[i];
}
else datos=0;
}
return *this;
}
float Vector_Disperso::get_default() const
{
return valor_por_defecto;
}
void Vector_Disperso::set_default(float f)
{
assert (nelementos==0);
valor_por_defecto= f;
}
float Vector_Disperso::get(int i) const
{
int pos;
if (posicion_indice(pos,i))
return datos[pos].valor;
else return valor_por_defecto;
}
void Vector_Disperso::set(int i, float f)
{
int pos;
if (posicion_indice(pos,i))
{
if (f!=valor_por_defecto)
datos[pos].valor= f;
else {
nelementos= nelementos-1;
for (int j=pos;j<nelementos;++j)
datos[j]=datos[j+1];
if (nelementos<reservados/4)
contraer();
}
}
else {
if (f!=valor_por_defecto)
{
if (nelementos==reservados)
expandir();
for (int j=nelementos; j>pos; --j)
datos[j]= datos[j-1];
datos[pos].indice= i;
datos[pos].valor= f;
++nelementos;
}
}
}
int Vector_Disperso::nelementos() const
{
return nelementos;
}
Vector_Disperso::~Vector_Disperso()
{
if (reservados>0)
delete[] datos;
}