Introducción

Un vector dinámico no es más que un vector con capacidad para crecer y decrecer.

Una instancia v del tipo de datos abstracto Vector dinámico sobre el  tipo float es un array unidimensional de un determinado tamaño n, que puede crecer y decrecer a petición del usuario. Lo podemos representar como:

 

  {v[0], v[1] ,..., v[n-1] }

 

Donde v[i] es el valor almacenado en la posición i del vector.

 

La eficiencia en espacio es O(n), donde n es el número de posiciones del vector que almacena un valor distinto de d .

Primitivas del vector dinámico

 Dentro del TDA Vector dinámico hemos propuesto las siguientes primitivas, aunque como siempre esto no quiere decir que sean las únicas para todos los casos:

 

·              Vector_dinamico (int n = 0) -> constructor por defecto, nos crea un vector dinámico vacío.

PARÁMETROS : n -> indica el número de componentes inicial reservados para el vector.

 

·              Vector_disperso (const Vector_dinamico& original) -> constructor de copia, crea un vector dinámico que es copia del vector disperso original.

PARÁMETROS :  original -> vector dinámico que se copia.

 

·              Int size () const  -> devuelve el número de componentes que puede almacenar en este instante el vector.

 

·              Float& operator [ ] (int i)  -> acceso a un elemento, devuelve la referencia al elemento, se puede usar para almacenar un valor en esa posición.

PARÁMETROS : i -> la posición del vector donde está el componente. 0 <= i < size ().

 

·              Const float& operator [ ] (int i)  -> acceso a un elemento de un vector constante, devuelve la referencia al elemento, se supone que el vector no se puede modificar y por tanto es acceso de sólo lectura.

PARÁMETROS : i -> la posición del vector donde está el componente. 0 <= i < size ().

 

·              Void resize (int n)  -> redimensiona el vector dinámico.

PARÁMETROS : n -> el nuevo tamaño del vector. n >= 0.

POSTCONDICIÓN : los valores almacenados antes de la redimensión no se pierden (excepto los que se salen  del nuevo rango de índices).

 

·              Vector_dinamico& operator = (const Vector_dinamico& original) -> operador de asignación, copia en el vector dinámico que hace la llamada  el vector dinámico original.

PARÁMETROS :  original -> vector dinámico que se copia.

 

·              ~Vector_dinamico () -> destructor, elimina todos los elementos del vector, liberando los recursos usados.

Ejemplos de uso

                     En este apartado vamos a mostrar unos ejemplos para que comprendamos el funcionamiento de las primitivas del TDA Vector dinámico:

Buscar un elemento en un vector

Esta función nos busca un elemento e en un vector dinámico, devolviendo –1 si no se encuentra en el vector, o la posición que ocupa si se encuentra.

 

Vector_Dinamico v;

 

int Buscar (const Vector_Dinamico& v, int e)

   {

   if (v.size() == 0)

      return -1;

  else

        {

        for (int i = 0; i < v.size(); i++)

       if ( v[i] = = e )

      return i;

        return –1;

        }

    }

 

 

Borrar un elemento del vector dinámico

 

Esta función nos borra el elemento del vector dinámico que ocupa la posición pasada como argumento, comprimiendo los datos.

 

Vector_Dinamico v;

 

void Borrar (const Vector_Dinamico& v, int pos)

   {

   assert (pos >= 0 && pos < v.size());

   for (int i = pos; i < v.size()-1; i++)

        datos[i] = datos[i+1];

   v.resize (nelementos-1);    

   }

 

Implementación del vector dinámico

El vector dinámico se implementa con un vector, el cual llamaremos datos, es un vector de tipo float. Luego también el objeto vector dinámico, como el vector disperso, tiene una variable nelementos que nos indica el tamaño del vector.

 

A continuación especificaremos 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 dinámico representa al vector de tamaño n:

 

{ rep.datos[0], rep.datos[1], ..., rep.datos[nelementos-1] }

 

 

Invariante de Representación

 

Un objeto válido rep del TDA Vector dinámico debe cumplir:

 

-                     rep.nelementos >= 0.

 

-                     rep.datos apunta a una zona de memoria con capacidad para albergar nelementos valores de tipo float.

 

 

         De manera que la clase Vector_Dinámico en C++ tendría el siguiente aspecto:

 

Class Vector_Dinamico

       {

       

       Public:

       Vector_Dinamico (int n = 0);

       Vector_Dinamico (const Vector_Dinamico& original);

       int size () const;

       float& operator[ ] (int i);

       const float& operator[ ] (int i) const;

       void resize (int n);

       Vector_Dinamico& operator= (const Vector_Dinamico& original);

      ~Vector_Dinamico ();

 

       Private:

float *datos;

int nelementos;

 

       }

 

Pasemos ahora a ver la implementación de cada una de las primitivas enunciadas con anterioridad en C++: