| Pregunta: | 21498 - TABLAS HASH-DICCIONARIO |
| Autor: | Maria Morales |
| Debo implementar un diccionario por medio de Tablas de dispersión tanto abiertas como cerradas. El problema esta en que como cada palabra debe tener su definición no encuentro la manera de construir la función para la tabla. Pensé que talvez al utilizar la función atoi podia pasar caracteres a enteros y a partir de ahi implementar la función pero como el usuario será capaz de introducir una palabra para su busqueda en la tabla mi idea creo que no es valida. Quisiera ver si me pueden ayudar a la vez como la dispersión cerradas es un vector como hago para meter do objetos en el mismo campo, o es acaso que dería ser implementada con plantillas y que cada objeto sea predefinido de dos componentes?... | |
| Respuesta: | NewBe |
| No entiendo mucho que dices, pero creo que se lo que quieres hacer: para meter las palabras en el hash primero tienes que combertir las cadenas en numeros, ¿como? muy sencillo, tienes que ir combirtiendo cada letra de tu vector de caracteres en un numero, este numero debe de se el valor en ascii de la letra e ir sumando cada letra de la palabra, ya sumadas todas las letras que conforman la primer palabra y despues hay que sacarle el modulo de acuerdo al tamaño del hash. por ejemplo: si la primer palabra fuese: Maria y si suponemos el vector que sostiene toda la estructura fuera de tamaño 15. M =77 en ascii a=97 r=114 i=105 a=97 suma=490 te daras cuenta que no podrias meter en el vector en la posicion 490 la palabra Maria, ya que no existe la posición 490. Ahora si a 490 le sacamos el modulo deacuerdo con el tamaño 15 de nuestro vector: (en pascal) pos:=490 mod 15 "pos" tendria un valor de 10 que si esta dentro de el rango de posiciones de el vector que sostene el hash hipoteticamente si la suma de nuestras letras dieran un valor igual al tamaño del vector el residuo seria igual a cero y como en C la posicion 0 existe, no habria problema. de esta manera obtenemos el indice de la posicion de los punteros que se sostinen del vector (0)->null (1)->null (3)->null . . (10)->Maria->nul . (n)->null Hay que tener en cuenta que este indice solo nos indica en que parte del vector se hace la inserción, y antes de hacer la incersion hay que verificar si la palabra ya existe en la cadena por ejemplo si la palabras fueran: Maria, ddd, Maria, Hola tendriamos: Maria =pos 10 ddd =pos 0 ZPA =pos 10 Maria =pos 10 Hola =pos 11 mas o menos quedaria así (0)->ddd->null (1)->null (3)->null . . (10)->Maria->ZPA->nul (11)->Hola->nul . . (15)->null Espero que esto te sirva de algo... | |