Site hosted by Angelfire.com: Build your free website today!


MÉTODOS DE BÚSQUEDA


 

Encontrar información en un arreglo desordenado requiere una búsqueda secuencial comenzando en el primer elemento y parando cuando se encuentra el elemento buscado o cuando se alcanza el final del arreglo. Este método es el que se tiene que utilizar con datos desordenados aunque también se puede aplicar a datos ordenados. Si la datos ya han sido ordenados, es más aconsejable utilizar el algoritmo de búsqueda binaria, que incrementa ampliamente la velocidad de búsqueda.

La búsqueda secuencial es fácil de codificar. El siguiente algoritmo busca el valor x en el arreglo a de n elementos, retornando la ubicación del elemento buscado o 1 si el elemento no existe en el arreglo.



BuscaSec (a, n, x)
{ for(i=0; i <n; ++i) if(x==a[i]) return(i); return(-1);   }

  La búsqueda secuencial no es la más eficiente pero es la única alternativa si el arreglo se encuentra desordenado. Si los datos del arreglo se encuentran ordenados, entonces se puede usar el método de búsqueda binaria. Para encontrar el elemento buscado se compara con el de la mitad del arreglo. Si es igual, se encontró. Si es mayor que el elemento buscado, entonces se compara con el elemento de la mitad de la primera mitad; en caso contrario, se comprueba el elemento de la mitad de la segunda mitad. Este proceso se repite hasta encontrar el elemento o no queden elementos por comprobar.

Ejemplo: Se busca 4.

Se compara con el elemento medio (5) y se descarta la segunda mitad.
 

1
2
3
4
5
6
7
8
9

 

Se compara con el elemento medio de la primera mitad (3) y s descarta la primera mitad.
 
1
2
3
4
5

 

Se compara con el elemento medio de la segunda mitad (4) y encuentra el valor buscado.
 
3
4
5

 


Búsqueda Hashing

El tiempo ocupado en ordenar un arreglo y buscar un elemento mediante la búsqueda binaria es similar al de buscar secuencialmente en un arreglo desordenado, por lo cual se creó un método alternativo para trabajar con las operaciones básicas para los datos (ingresar, eliminar y buscar), el Hashing. Su principal característica es que ingresa cada elemento en un lugar específico determinado por el módulo de éste, por lo cual cada vez que se necesite buscar un elemento sólo bastará calcular su posición por el mismo método.

Existen dos formas de Hashing distintas. El primero, llamado Hashing Cerrado, es una estructura de datos estática por lo cual usa un tamaño fijo para el almacenamiento, por lo que limita el tamaño de los conjuntos. El segundo, llamado Hashing Abierto, es una estructura de datos dinámica por lo cual no impone un límite al tamaño del conjunto.
 
 

HASHING CERRADO

Existen distintos tipos de Hashing cerrados. Los más comunes son el lineal, el doble y el directo, y se diferencian unos de otros por la forma de resolver las colisiones.

El Hashing lineal resuelve el problema de las colisiones asignando el primer lugar disponible recorriendo circularmente la tabla. Cuando elimina recorre toda la tabla para asegurarse de que lo eliminó. Sufre de agrupamiento primario, dado que cuando existen colisiones la tabla crece por su corrimiento y luego cualquier inserción tendrá colisión.

El Hashing doble aplica una segunda función Hashing cuando se produce una colisión, para determinar el incremento con el cual buscar la próxima posición. Esta alternativa requiere tablas con números primos de elementos para asegurar el recorrido de todos los lugares posibles.

El Hashing directo trabaja con un almacén auxiliar, también llamado OVERFLOW, en el cual se almacenan las colisiones.

A continuación se presentan las funciones para un Hashing lineal.



#define TRUE 1
#define FALSE 0
#define VACIO 1

struct tabla{

int llave;
int libre;
};
struct tabla tabhash[10];



int hashing(int dato)
{
return(dato%MAX);
}



void insertar (int dato)
{
int p, i;
p=hashing(dato);
if(tabhash[p].libre == VACIO)
{
tabhash[p].llave = dato;
tabhash[p].libre = !VACIO;
}
else{
i= (p+1)%MAX;
while(i!=p && i != -1)
if(tabhash[i].libre == VACIO)
{
tabhash[i].llave = dato;
tabhash[i].libre = !VACIO;
i=-1;
}
else i = ++i % MAX;
if(i==p) printf("Overflow");
}
}



int pertenece(int dato)
{
int p, i;
p=hashing(dato);
if(tabhash[p].libre != VACIO && tabhash[p].llave == dato)
return(TRUE);
else{
i= (p+1)%MAX;
while(i!=p)
if(tabhash[i].llave == dato) return(TRUE);
else i = ++i % MAX;
return(FALSE);
}
}



void eliminar(int dato)
{
int p,i;
p=hashing(dato);
if(tabhash[p].libre != VACIO && tabhash[p].llave == dato)
tabhash[p].libre = VACIO;
else{
i= (p+1)%MAX;
while(i!=p && i != -1)
if(tabhash[i].libre != VACIO && tabhash[i].llave == dato)
{
tabhash[i].libre = VACIO;
i=-1;
}
else i = ++i % MAX;
}
}


HASHING ABIERTO

El Hashing abierto maneja las colisiones generando una lista enlazada en cada una de las posiciones de la tabla, es decir, si dos valores poseen un mismo valor para Hashing estarán dentro de una misma lista enlazada.

Las funciones para un Hashing abierto son las siguientes.



struct nodo {
int dato;
struct nodo *sgte;
};


struct nodo *tabla[TAM];



void inittab(int talla)
{
int i;
for(i=0;i< talla;i++)
tabla[i]=NULL;
}



struct nodo *insertar(struct nodo *head, int data)
{
if(head==NULL) {
head=( struct nodo *)malloc(sizeof(struct nodo));
head->dato=data;
head->sgte=NULL;
}
else
head->sgte=insertar(head->sgte,data);
return(head);
}



hashing(int val,int largo)
{
return(val%largo);
}