Programación General > C/C++
Tablas Hash
(1/1)
raulazzo:
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 --- #include<stdio.h>#include<stdlib.h> #define MAXC 10//MAXIMO TAMAÑO DE UNA CADENA#define MAXA 10//TAMAÑO DE LA TABLA struct nodo{ char *cadena; struct nodo *siguiente;}; int clave (char cadenaux[MAXC])//OBTIENE LA SUMA DE LOS VALORES ASCII DE CADA CARACTER DE LA CADENA{ int clave=0, ascii, i=0; while((ascii=cadenaux[i++])!='') clave+=ascii; return clave;} int hash (int clave)//SE DETERMINA LA POSICIO EN LA QUE SE GUARDARA LA CADENA{ int posicion=clave%MAXA; return posicion;} void insertar(struct nodo **ptabla, char cadena[MAXC])//INSERTAR NUEVO ELEMENTO EN UNA LISTA{ struct nodo *nuevo = (struct nodo*) malloc(sizeof(struct nodo));//CREAMOS EL NUEVO NODO nuevo->cadena = cadena;//GUARDAMOS CADENA nuevo->siguiente = NULL;//COMO SE VA A INSERTAR AL FINAL, SERA EL QUE APUNTE A NULL struct nodo *actual=*ptabla;//CREAMOS UN PUNTERO AUXILIAR A NODO if (*ptabla==NULL) { *ptabla=nuevo;//SI LISTA VACIA, ENTONCES: NUEVO ES EL PRIMER ELEMENTO } else { while (actual->siguiente != NULL) { printf("n %s n", actual->cadena); actual = actual->siguiente;//SI NO ESTA VACIA, SE RECORRE LA LISTA } actual->siguiente =nuevo;//EL ULTIMO NODO AHORA ANTECEDE AL NUEVO }} void mostrar(struct nodo *ptabla)//IMPRIMIR LA TABLA{ struct nodo *actual=ptabla;//ACTUAL ES UN PUNTERO AUXILIAR PARA RECORRER LA LISTA while (actual!=NULL)//MIENTRAS NO SEA EL FINAL DE LA LISTA { printf("[ %s ]->", actual->cadena);//IMPRIME EL DATO DEL NODO CORRESPONDIENTE actual = actual->siguiente;//AVANZAMOS AL SIGUIENTE NODO } printf("NULLnn");} main(){ struct nodo *ptabla[MAXA];//ARREGLO DE PUNTEROS PARA NODOS char cadenaux[MAXC];//ARREGLO AUXILIAR PARA GUARDAR CADENA INTRODUCIDA int op, clavecadena, pos;//VARIABLES USADAS PARA MENU Y POSICION EN EL ARREGLO for(pos=0;pos<MAXA;pos++) ptabla[pos]=NULL; do { printf("n*********************************n"); printf("nnTABLA HASHnn t1.- Guardar una cadenan t2.- Buscar una candenan t3.- Borrar una cadenan t0.- Salir.ttt"); scanf("%i", &op); printf("n*********************************n"); switch(op) { case 1: printf("nIntroduce cadenan"); fflush(stdin); gets(cadenaux); clavecadena=clave(cadenaux); pos=hash(clavecadena); insertar(&(ptabla[pos]), cadenaux); for(pos=0;pos<MAXA;pos++) mostrar(ptabla[pos]); break; } }while(op!=0);}
Navegación
Ir a la versión completa