SoloCodigo

Programación General => C/C++ => Mensaje iniciado por: raulazzo en Miércoles 18 de Noviembre de 2009, 05:34

Título: Tablas Hash
Publicado por: raulazzo en Miércoles 18 de Noviembre de 2009, 05:34

Quiero implementar tablas hash en C, se me ocurrió declarar un arreglo de punteros para los nodos de listas enlazadas.

Uso listas enlazadas para solucionar los problemas de colisión.

La función hash que utilizo es: Dada una cadena, obtengo la suma de los valores ascii de cada caracter de la cadena, al resultado le aplico la operación: resultado%tamaño_lista (módulo), lo que resulte sera la posición donde se guarde el dato.

Hasta ahora sólo he hecho las funciones para insertar un nodo y para mostrar la tabla, pero tengo un problema:
En una tabla de tamaño 10
Supongamos que inserto la cadena "A"
la suma de los valores ascii de cada caracter es 65
65%10=5, entonces la cadena "A" se guardará en la posición 5.

hasta ahí todo perfecto. Si introduzco otra cadena "A" se guarda en la misma posición pero en la lista anidada.
Si imprimen la tabla podrán ver que todo parece estar bien.

Ahora si introduzco una cadena "B", resulta que se guardará en la posición 6; y así ocurre, la cadena se guarda en la posición indicada, pero si imprimo de nuevo la tabla, resulta que todas las cadenas en la tabla son "B".
y si introdujera otra distinta, todas se convierten en la última.

Dejo mi código para que si pueden me indiquen qué hago mal, porque por más que le doy vueltas no veo mi error.
ejecuten el progrma y hagan las operaciones que les digo para que vean bien el problema.
Agradezco mucho me ayuden a entender.

Código: C

1.  
2. #include<stdio.h>
3. #include<stdlib.h>
4.  
5. #define MAXC 10//MAXIMO TAMAÑO DE UNA CADENA
6. #define MAXA 10//TAMAÑO DE LA TABLA
7.  
8. struct nodo
9. {
10.     char *cadena;
11.     struct nodo *siguiente;
12. };
13.  
14. int clave (char cadenaux[MAXC])//OBTIENE LA SUMA DE LOS VALORES ASCII DE CADA CARACTER DE LA CADENA
15. {
16.     int clave=0, ascii, i=0;
17.    
18.     while((ascii=cadenaux[i++])!='')
19.         clave+=ascii;
20.     return clave;
21. }
22.  
23. int hash (int clave)//SE DETERMINA LA POSICIO EN LA QUE SE GUARDARA LA CADENA
24. {
25.     int posicion=clave%MAXA;
26.    
27.     return posicion;
28. }
29.  
30. void insertar(struct nodo **ptabla, char cadena[MAXC])//INSERTAR NUEVO ELEMENTO EN UNA LISTA
31. {
32.     struct nodo *nuevo = (struct nodo*) malloc(sizeof(struct nodo));//CREAMOS EL NUEVO NODO
33.     nuevo->cadena = cadena;//GUARDAMOS CADENA
34.     nuevo->siguiente = NULL;//COMO SE VA A INSERTAR AL FINAL, SERA EL QUE APUNTE A NULL
35.     struct nodo *actual=*ptabla;//CREAMOS UN PUNTERO AUXILIAR A NODO
36.    
37.     if (*ptabla==NULL)
38.     {
39.         *ptabla=nuevo;//SI LISTA VACIA, ENTONCES: NUEVO ES EL PRIMER ELEMENTO
40.     }
41.     else
42.     {
43.         while (actual->siguiente != NULL)
44.         {
45.             printf("n %s n", actual->cadena);
46.             actual = actual->siguiente;//SI NO ESTA VACIA, SE RECORRE LA LISTA
47.         }
48.         actual->siguiente =nuevo;//EL ULTIMO NODO AHORA ANTECEDE AL NUEVO
49.     }
50. }
51.  
52. void mostrar(struct nodo *ptabla)//IMPRIMIR LA TABLA
53. {
54.     struct nodo *actual=ptabla;//ACTUAL ES UN PUNTERO AUXILIAR PARA RECORRER LA LISTA
55.    
56.     while (actual!=NULL)//MIENTRAS NO SEA EL FINAL DE LA LISTA
57.     {
58.         printf("[ %s ]->", actual->cadena);//IMPRIME EL DATO DEL NODO CORRESPONDIENTE
59.         actual = actual->siguiente;//AVANZAMOS AL SIGUIENTE NODO
60.     }
61.     printf("NULLnn");
62. }
63.  
64. main()
65. {
66.     struct nodo *ptabla[MAXA];//ARREGLO DE PUNTEROS PARA NODOS
67.     char cadenaux[MAXC];//ARREGLO AUXILIAR PARA GUARDAR CADENA INTRODUCIDA
68.     int op, clavecadena, pos;//VARIABLES USADAS PARA MENU Y POSICION EN EL ARREGLO
69.    
70.     for(pos=0;pos<MAXA;pos++) ptabla[pos]=NULL;
71.    
72.     do
73.     {
74.         printf("n*********************************n");
75.         printf("nnTABLA HASHnn
76.        t1.- Guardar una cadenan
77.        t2.- Buscar una candenan
78.        t3.- Borrar una cadenan
79.        t0.- Salir.ttt");
80.         scanf("%i", &op);
81.         printf("n*********************************n");
82.        
83.         switch(op)
84.         {
85.             case 1:
86.                 printf("nIntroduce cadenan");
87.                 fflush(stdin);
88.                 gets(cadenaux);
89.                 clavecadena=clave(cadenaux);
90.                 pos=hash(clavecadena);
91.                 insertar(&(ptabla[pos]), cadenaux);
92.                 for(pos=0;pos<MAXA;pos++) mostrar(ptabla[pos]);
93.                 break;
94.         }
95.     }while(op!=0);
96. }
97.  
98.