Organizaciones de ficheros – Ventajas e inconvenientes (resumen)

• Apilo
  • Inconvenientes
    • Al no estar ordenados los registros, las búsquedas son lentas.
    • No se controla la redundancia de información.
    • Requiere un mantenimiento del fichero para hacer los borrados físicos.
• Secuencial
  • Ventajas respecto a la organización de apilo
    • Permite recorrer el fichero de forma ordenada rápidamente(cuando se ordena por la clave).
    • Buscar un registro es más rápido.
  • Inconvenientes
    • Solo se puede ordenar por la clave.
    • Hay que reorganizar el fichero constantemente.
• Encadenada
  • Ventajas respecto a la organización secuencial
    • Permite ordenar por varios criterios.
    • Reduce el coste de mantener información relacionada.
  • Inconvenientes
    • Coste de las reorganizaciones cuando hay más de una cadena.
    • Pueden presentar problemas de pérdida de información si las cadenas son simples y los punteros se deterioran.
• Secuencial indexada
  • Ventajas respecto a la organización encadenada
    • Acceso secuencial y directo muy rápido.
    • El fichero de derrama está ordenado (en la organización secuencial no ).
  • Inconvenientes
    • Solo puede existir un clave.
    • La zona de derrama hace que las operaciones sobre el fichero sean mas lentas.
    • Ocupa mas espacio en el disco que los ficheros secuenciales.
• Indexada
  • Ventajas respecto a la organización secuencial indexada
    • No tiene zona de derrama.
    • Permite crear varios índices.
    • Accesos rápidos a los registros por varias claves.
  • Inconvenientes
    • Si el árbol no es B+ puede que el árbol esté desbalanceado o sea difícil el acceso secuencial.
• Hashing
  • Ventajas respecto a la organización indexada
    • Tiempo constante de acceso al registro.
  • Inconvenientes
    • Dependiendo de la función de hash se pueden producir sinónimos.

Implementación del tipo cola usando un vector

Fichero colaVector.hpp

#ifndef __COLA_VECTOR_HPP__
#define __COLA_VECTOR_HPP__

#include 
#include 
#include "colainterfaz.hpp"


/*!\brief Espacio de nombres para la asignatura Estructura de datos.*/
namespace ed 
{

//using std::vector;

 template
 class Cola:public ColaInterfaz
 {
  public:
   // constructor por defecto
   Cola(unsigned int limite=10)
   {
    assert(limite>0);
    
    _elementos.resize(limite);
    _limite=limite;
    _cabeza=0;
    _indice=0;
      }

   // constructor copia
   Cola(const Cola  &c)
   {
    _elementos.resize(c._elementos.size());
    _cabeza=c._cabeza;
    _indice=c._indice;
    _limite=c._limite;
    _elementos=c._elementos; // es un vector STL
   } 
   
   // no hace falta crearlas para esta implementación
   /*
   // Sobrecarga del operador de asignación con una cola
   Cola &operator=(const Cola &c) throw()
   {
    _cabeza=c._cabeza;
    _indice=c._indice;
    _limite=c._limite; 
    _elementos=c._elementos;
   }
   // Destructor
   ~Cola()
   {
   }
   */

    void insertar(const G &x) throw()
   {
    assert(not estaLlena());
    
    _elementos[ _indice % _limite ]= x;
    _indice=_indice+1;
   }

    void eliminar() throw ()
   {
    assert(not estaVacia());

    _cabeza=_cabeza+1;
   }
   
    const G & cabeza() const throw ()
   {
    assert(not estaVacia());
    
    return _elementos[_cabeza%_limite];
   }

   bool estaVacia () const throw ()
   {
    return (_indice==_cabeza)? true : false;
   }

   bool estaLlena ()  const throw (){
    return ((_indice-_cabeza)==_limite)? true : false;
   }

   private:
   std::vector  _elementos;
   unsigned int _indice;
   unsigned int _cabeza;
   unsigned int _limite;
 };


} //namespace ed

#endif //__COLA_VECTOR_HPP__