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 10Supongamos que
inserto la cadena "A"la suma de los valores ascii de cada caracter es
6565%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.
#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
}
}
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"); t1.- Guardar una cadenan
t2.- Buscar una candenan
t3.- Borrar una cadenan
t0.- Salir.ttt");
printf("n*********************************n");
switch(op)
{
case 1:
clavecadena=clave(cadenaux);
pos=hash(clavecadena);
insertar(&(ptabla[pos]), cadenaux);
for(pos=0;pos<MAXA;pos++) mostrar(ptabla[pos]);
break;
}
}while(op!=0);
}
