Búsqueda Binaria

Código: binaria(int A[], int clave, int inf, int sup) {

%IMAGE_1%

Al ser recursivo, hemos de actualizar límites. If (inf > sup) Return -1; Medio = (inf + sup) / 2; If (clave < A[medio]) Return binaria(A, clave, medio + 1, sup); Return medio;

Ejemplo: %IMAGE_2%

Busca el %IMAGE_3% y el %IMAGE_4%. El orden de llamada es: binaria(A, 25, 0, 8), binaria(A, 25, 5, 8). La función devuelve 6.

El orden de llamada es binaria(A, 7, 0, 8), binaria(A, 7, 0, 3), binaria(A, 7, 2, 3), binaria(A, 7, 3, 3), binaria(A, 7, 3, 2). Como inf > sup, entramos en el if y la función devuelve -1.

Tablas Hash

De cada estructura, elijo un campo que identifica de forma única a esa estructura. Una función hash se aplica a la clave y devuelve la posición de la tabla donde está almacenada esa clave. Para dos claves distintas, la función hash ha de devolver posiciones distintas, es decir, no debe haber colisiones. Esto se llama factor de carga.

%IMAGE_5%

donde %IMAGE_6% es el número de elementos almacenados y %IMAGE_7% es el tamaño de la tabla. Lo recomendable es que %IMAGE_8%, es decir, que el %IMAGE_9% de la tabla esté vacía para poder arreglar las colisiones que surjan. Así:

%IMAGE_10% %IMAGE_11%

Donde %IMAGE_12% es el conjunto de claves y %IMAGE_13% son las posiciones dentro del vector.

Propiedades: A una función hash se le pedirá que no tenga muchas colisiones y que el tiempo de evaluación sea constante.

Tipos de Funciones Hash

Aritmética Modular

%IMAGE_14% donde %IMAGE_15% es el tamaño de la tabla. Es recomendable que el tamaño no sea un múltiplo de 2 ni un múltiplo de 10. Lo óptimo tendrá que ser el número primo más cercano que cumpla el factor de carga.

Ejemplo: Considerar una aplicación en la que hay que almacenar 800 registros. El campo clave elegido es el número de identificación. Elegir el tamaño de la tabla de dispersión y utilizar aritmética modular para calcular la posición que ocupan los elementos cuyo número de identificación es el siguiente: 245643 %IMAGE_16%. Hemos de elegir un número primo cercano. Elegimos el 997. %IMAGE_17%. El resto es %IMAGE_18% y es la posición de la tabla donde se alojará el número.

Método del Plegamiento

%IMAGE_19%. Donde %IMAGE_20% son trozos de la clave.

Ejemplo: Los registros de pasajeros de un tren de largo recorrido se identifican por un campo de %IMAGE_21% dígitos que se va a utilizar como clave para crear una tabla hash de 1.000 posiciones. Se utiliza como función hash el método del plegamiento haciendo grupos de %IMAGE_22% dígitos. Aplicar esta función a los registros y ver en qué posición quedan. %IMAGE_23% %IMAGE_24%. Como no cabe en la tabla de %IMAGE_25% hago módulo %IMAGE_26%.

Método de la Mitad del Cuadrado

Calculamos el cuadrado de la clave: %IMAGE_28%. Elegir dígitos en determinadas posiciones.

Ejemplo: Aplicar el método de mitad del cuadrado a los mismos registros del ejercicio anterior eligiendo los dígitos que se encuentran en las posiciones %IMAGE_29% empezando a numerar por la derecha. %IMAGE_30% %IMAGE_31%

Método de la Multiplicación

Se multiplica %IMAGE_32% donde %IMAGE_33%. Coger parte decimal a la que llamamos %IMAGE_34%. Multiplicamos %IMAGE_35%. Coger parte entera.

Ejemplo: %IMAGE_36% con %IMAGE_37%. %IMAGE_38%. %IMAGE_39%.

Resolución de Colisiones

Encadenamiento: Cuando dos valores distintos van a una misma posición en la tabla hash, puedo hacer que en esa posición de la tabla haya una lista enlazada que tenga todos los elementos que ocupen esa posición.

Direccionamiento Abierto: Cuando calculamos la función hash, nos da una posición y esa está ocupada, lo que hacemos es probar con una lista de posiciones que se llama secuencia de sondeo.

Sondeo Lineal.

Inserción. Clave %IMAGE_40% y %IMAGE_41%. La primera posición que probamos es %IMAGE_42%. Si %IMAGE_43% está ocupada, probamos con %IMAGE_44%, etc. Puede ocurrir que lleguemos al final de la tabla. Cuando llegamos, no paramos, probamos con la %IMAGE_45%, luego con la %IMAGE_46% hasta llegar a %IMAGE_47% si hace falta.

Ejemplo: Existen %IMAGE_48% elementos cuyas claves son %IMAGE_49%. Para cada una de ellas, la función Hash que utilizamos genera los siguientes valores:

Buscar: Empezamos por %IMAGE_50%. Si coincide, lo hemos encontrado. Si no, seguimos la secuencia de sondeo. Si llegamos de nuevo a la posición %IMAGE_51% o a una posición vacía, podemos decir que no está en la lista.

Definición: Un agrupamiento primario ocurre cuando hay varias posiciones consecutivas ocupadas. Esto implica que para encontrar un sitio libre hay que pasar varias posiciones para llegar a un sitio vacío. Además, una vez lo encuentro y añado otro nuevo, el problema se complica porque tendré un agrupamiento primario un poco más largo. Lo solucionaremos con el siguiente tipo de sondeo.

Sondeo Cuadrático.

Inserción. Clave %IMAGE_52% y %IMAGE_53%. La primera posición que probamos es %IMAGE_54%. Si %IMAGE_55% está ocupada, probamos con %IMAGE_56% %IMAGE_57%. Puede ocurrir que lleguemos al final de la tabla. Cuando llegamos al final, no paramos, cogemos el resto.

Ejemplo: Tenemos una tabla de tamaño %IMAGE_58%.

Sondeo.

Inserción. Clave %IMAGE_59% y %IMAGE_60% y %IMAGE_61%. Probamos con %IMAGE_62%.

Ejemplo: Para resolver colisiones se utiliza el método de doble dispersión, el primero es aritmética modular y el segundo el método de la multiplicación. Encontrar los elementos con las claves %IMAGE_63% en una tabla de tamaño %IMAGE_64%.