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.
Ejemplo: Se busca 4.
Se compara con el elemento medio
(5) y se descarta la segunda mitad.
|
|
|
|
|
|
|
|
|
|
Se compara con el elemento medio
de la primera mitad (3) y s descarta la primera mitad.
|
|
|
|
|
|
Se compara con el elemento medio
de la segunda mitad (4) y encuentra el valor buscado.
|
|
|
|
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.
struct tabla{
int llave;struct tabla tabhash[10];
int libre;
};
return(dato%MAX);}
tabhash[p].llave = dato;}
tabhash[p].libre = !VACIO;
i= (p+1)%MAX;}
while(i!=p && i != -1)if(tabhash[i].libre == VACIO)if(i==p) printf("Overflow");
{tabhash[i].llave = dato;}
tabhash[i].libre = !VACIO;
i=-1;
else i = ++i % MAX;
}
return(TRUE);else{
i= (p+1)%MAX;}
while(i!=p)if(tabhash[i].llave == dato) return(TRUE);return(FALSE);
else i = ++i % MAX;
}
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.
int dato;
struct nodo *sgte;
};
struct nodo *tabla[TAM];
tabla[i]=NULL;}
