Tarea 2 CC31A

Plazo: 2 semanas
Entrega: Lunes 26 de septiembre

Descripción

Hacer funciones en C que permitan hacer búsqueda eficiente de strings. Esto es como un diccionario, donde busco un string y quiero obtener un valor asociado. Se les pide implementar una tabla de hashing con encadenamiento abierto para la implementación.

La interfaz a implementar (dict.h) es

/*
 * Funciones para implementar un diccionario
 */ 

/*
 * Inicializa una tabla de hashing de tamaño n listas
 * Cuando n es más grande tengo menos colisiones pero gasto más memoria
 */
DICT *init_dict(int n);

/*
 * Agrega un par (llave, valor) al diccionario
 * Si la llave ya estaba en el diccionario, deben reemplazar el valor
 * antiguo por el nuevo valor
 */
void add_dict(DICT *dict, char *llave, void *val);

/*
 * busca en un diccionario una llave y retorna su valor
 * o NULL si no estaba
 */
void *search_dict(DICT *dict, char *llave);

/*
 * libera todos los nodos del diccionario
 * y toda la estructura asociada
 */
void free_dict(DICT *dict); 

/*
 * Aplica una función f sobre todos los pares (llave, valor)
 */
void map_dict(DICT *dict, void (*f)(char *, void *));

Deben definir el tipo DICT e implementar todas estas funciones. La función de hashing a usar para la distribución en la tabla de tamaño n es:

int hash(char *s, int n) {
    int h = 0;

    while(*s)
	h += *s++;

    return h%n;
}

La tabla de hashing es un arreglo de n punteros a listas enlazadas para agregar los pares que coinciden con el mismo número de hashing.

Ejemplo de Uso

Se les provee el programa testdict.c que llama a las funciones con varios argumentos. Requieren crear el archivo de declaración de la interfaz dict.h. La salida exacta que debieran obtener está en el archivo outdict.txt para que la comparen.

Condiciones de Entrega

La tarea debe entregarse antes del plazo final y debe compilar sin errores y ejecutar, o no será evaluada. Si tienen una tarea que funciona en parte, pero no completa, entréguenla a tiempo y obtendrán algo de nota.

Deben entregar dict.c y dict.h