Funciones HASH - Algoritmos y Programación II

La tabla HASH es una forma de insertar elementos en un arreglo, dicha inserción no depende de una comparación de valores (mayor o menor) sino que depende de una función determinada (f(x), siendo "x" el elemento a insertar. Estas funciones de dispersión pueden ser las siguientes:

• Aritmética modular:  f(x) = x módulo de m; En lenguaje C f(x) = x % m. Siendo "x" el elemento y "m" el tamaño de la tabla.
• Plegamiento:  X = X1 X2 X3 X4...Xn  -->  f(x) = X1+X2+X3+X4+...+Xn.
• Mitad del cuadrado: Calcula  X²  y se extraen determinados dígitos del mismo.
• Método de la multiplicación: Se calcula lo siguiente:
• R* X
• D = R+X-L[(R*X)]
• f(X) = [M*D]                    Siendo X el dato y R un valor real.

Clasificación de las tablas de hash:

Tabla de hash abierta: Esta tabla contiene en cada una de las posiciones del arreglo una lista. De esta forma:

• Tabla de hash cerrada: En este tipo de tabla, a diferencia del anterior, solo puede haber un elemento por casilla en la tabla. Se puede dar el caso donde dos elementos distintos, al aplicarle a función de dispersión, arrojan la misma posición, estas situaciones son llamadas COLISIONES, que se pueden resolver de la siguiente manera:
• Exploración lineal: Consiste en sumar una unidad a la posición obtenida hasta encontrar una casilla disponible, es decir, P= P, P+1, P+2... 
• Exploración cuadrática: En este caso la colisión se resuelve así: P= P, P+1², P+2², P+3², P+4²… 
• Doble dirección dispersa: Sea f(x)= p y otra función f'(x) = p' se genera lo siguiente: P= P, P+P', P+2P', P+3P', P+4+'...

NOTA: Si la cantidad de elemento a insertar es "m", es recomendable que el tamaño de la tabla sea el primer número primo inmediatamente superior a m. 

Para  observar un ejemplo de una tabla de hash abierta en el lenguaje de programación C presiona aquí:  https://docs.google.com/leaf?id=0B_tJ5vXCSmOoNWY3MmU5YjQtYmFkZS00OGM4LThkY2EtYjA1MjY3MDNiOTU0&hl=en    

Para observar un ejemplo de una tabla de hash cerrada en el lenguaje de programación C presiona aquí:  https://docs.google.com/leaf?id=0B_tJ5vXCSmOoNTVjYjVjYzgtOGYyMC00MDk0LWFkMzktYWZkODBiNDI2ODA4&hl=en              


                    

Método de ordenamiento "INSERCIÓN" - Lenguaje C

El método de "inserción" está basado en la técnica que utilizan los jugadores de cartas para odernar sus cartas. El jugador va insertando cada una de las cartas en la posición correspondiente.

Se considera una parte de la lista ya ordenada, ubicando cada elemento y colocándolo en el lugar que corresponde tomándo en cuenta su valor, como se muestra en la siguiente imágen:

Para implementar este método en el lenguaje de programación C, se debe emplear el siguiente procedimiento:

void ordenar(int vector[])

{
   int i, a, aux;

   for (i=1; i < 4; i++)
   {
      aux = vector[i];

      for (a=i-1; a >= 0 && vector[a] > aux; a--)
      {
         vector[a + 1] = vector[a];

      }

      vector[a+1] = aux;

   }
}

Para observar una corrida en frío de dicho procedimiento puede hacer click en el link para WINDOWS:  https://docs.google.com/leaf?id=0B_tJ5vXCSmOoMzJhMGIwZmQtYWRlYy00ZjczLTgwYzgtNjM3N2Q2MjFiMjhh&hl=en&authkey=CN2DjY8O

O click aquí para UBUNTU:  https://docs.google.com/leaf?id=0B_tJ5vXCSmOoOWY4Y2IxNDYtZGVlNi00NThhLTg2ZDktYWFjYTQ5NDE0M2Rh&hl=en&authkey=CLzA_HM

Sumar pilas - Algoritmos y Programación II

El siguiente programa tiene la finalidad de sumar dos números mediante la estructura dinámica de pilas.

En principio, el sistema muestra un menú donde el usuario elige entre "sumar pilas" y "salir":

Posteriormente, los dos números son pedidos al usuario:

Luego, se ejecuta la función "sumar", y se imprimen por pantalla los dos números, sus pilas correspondientes, el resultado de la suma, y a su vez, el resultado en una pila:

Este programa está realizado bajo el concepto de multiarchivo y multiplataforma, es decir, es compatible con WINDOWS y UBUNTU, para ello es necesario modificar el código definiendo o no el macro RUN_WINDOWS.

Para acceder al código del sistema presione el siguiente link: https://docs.google.com/leaf?id=0B_tJ5vXCSmOoZWM5ODhmYTQtMGU4NS00YTg3LWI1ZWYtY2ZiYjBiZDMwYzc1&hl=en&authkey=CPzDtsYK





Calculadora - Algoritmos y Programación II

     Este programa consiste en una calculadora que permite realizar operaciones matemáticas básicas (suma, resta, multiplicación y división) de dos números.

     Dicha calculadora fue realizada en el lenguaje de programación C, utilizando el método de multiarchivo y multiplataforma, es decir, puede funcionar en los sistemas operativos WINDOWS y UBUNTU.

     Para que la calculadora funcione en los diferentes sistemas operativos se debe hacer un cambio en el archivo "stdprincipal.h" de la siguiente forma:

Para UBUNTU                                                                                     Para WINDOWS

             

    Para utilizar la calculadora, en principio, el sistema muestra un menú donde el usuario puede elegir entre "usar la calculadora" o "salir" del sistema:

     Al presionar la tecla "1", el sistema procede a pedirle al usuario los dos número con los que se realizará la operación; posteriormente, el usuario debe indicar cuál de las operaciones desea utilizar, y el sistema mostrará en pantalla el resultado:

    Para utilizar la calculadora acceder al siguiente enlace: https://docs.google.com/leaf?id=0B_tJ5vXCSmOoMDZiYWQxMDYtNzEwZC00ZDE3LWI1YzktMThkODU3ZTBkODA1&authkey=CLbszOEP&hl=en