/*
Hola, en esta tabla hash, utilizo el direccionamiento dupla, es decir el uso de dos funciones para determinar la posición. es muy sencillo, al llegar una llave, le aplica la función y ve si el espacio está disponible(flag=false), si está , entra el nuevo valor y cambia el flag a true, si no (a esto se le llama colisión) se incrementa el valor de i, igual en la eliminación, se ve si es igual al dato q se quiere eliminar, si no lo vuelve a buscar incrementando i, si llega a ser mayor q tablesize, el dato no existe, si lo encuentra lo único que hace es cambiar el flag a falsey de manera análoga con la búsqueda.
*******************************************************************
*Algoritmia y Estructura de Datos 1 *
*David Rodolfo Torres Palao *
*Solo unos pocos elegidos...pertenecen de verdad al gran mundo *
*******************************************************************
*/
#include
#include
#include
#include
#include
#include
class TablaHash;
class nodo{
private:
int dato;
bool estado;
public:
nodo()
{
dato=0;
estado=false;/*true=hay , false=no hay*/
}
friend class TablaHash;
};
class TablaHash{
private:
int m;
int tablesize;
nodo *t;
public:
TablaHash(int n)
{
tablesize=n;
m=n-2;
t=new nodo[n];
}
void ingresar(int);
void eliminar(int);
void buscar(int);
int funcion(int,int);
};
void TablaHash::eliminar(int k)
{
int i=0,j;
do
{
j=this->funcion(k,i);
if(t[j].dato==k)
{
t[j].estado=false;
return;;
}
else
i++;
}while(i
cout<<"Dato no encontrado\n";
getch();
}
void TablaHash::buscar(int k)
{
int i=0,j;
do
{
j=this->funcion(k,i);
if(t[j].dato==k && t[j].estado)
{
cout<<"El dato esta en la posicion "<
getch();
return;
}
else
i++;
}while(i
cout<<"Elemento no encontrado\n";
getch();
}
void TablaHash::ingresar(int k)
{
int i=0,j;
do
{
j=this->funcion(k,i);
if(!t[j].estado)
{
t[j].estado=true;
t[j].dato=k;
return;
}
else
i++;
}while(i
cout<<"Tabla llena!\n";
}
int TablaHash::funcion(int x, int i)
{
return(((x%tablesize)+i*(1+(x%m)))%tablesize);
}
void main(void)
{
int opc;
int n;
TablaHash *h1;
cout<<"Ingresar tamano de la tabla: ";
cin>>n;
h1=new TablaHash(n);
for(;;)
{
system("cls");
cout<<"Menu\n"
<<"1.Buscar\n"
<<"2.Ingresar Dato\n"
<<"3.Eliminar Dato\n"
<<"4.Salir\n\n";
do
{
cout<<"Seleccione una opcion: ";
cin>>opc;
if(opc<=0 || opc>4)
cout<<"No existe tal opcion\n";
}while(opc<=0 || opc>4);
switch(opc)
{
case 1:
cout<<"Ingresar dato: ";
cin>>n;
h1->buscar(n);
break;
case 2:
cout<<"Ingresar dato: ";
cin>>n;
h1->ingresar(n);
break;
case 3:
cout<<"Ingrese dato: ";
cin>>n;
h1->eliminar(n);
break;
case 4:
cout<<"Ejecucion Finalizada \n";
system("PAUSE");
return;
}
}
}