Estructura de Datos y Algoritmos
1er. Sem 2004
Tarea 3: Frecuencia de Palabras usando Tablas Hash
El objetivo de esta tarea es
ejercitar la programación y manejo de tablas hash.
Desarrolle el programa
>$ muletilla [<nombre_de_archivo_de_entrada>]
El programa muletilla recibe
un argumento opcional correspondiente al nombre de un archivo de de
texto legible. Como salida entrega en pantalla dos columnas mostrando
el listado de todas las palabras que aparecieron en el texto en una
columna y su frecuencia de aparición en la otra. Este
listado debe estar ordenado por frecuencia de aparición, y para
igual freceuncia de aparición por orden alfabético de las
palabras.
Si el argumento no aparece, el procesamiento se hace sobre las palabras
ingresadas por teclado.
Para su implementación se pide usar una tabla hash abierto. Como
no se conoce el número de palabras por adelantado, su tabla hash
parte con capacidad para 16 listas. Si el factor de ocupación
llega a 1 (uno), la próxima inserción debe expandir
su
tabla hash al doble y trasladar todos los datos a la nueva tabla.
Su tarea debe ser estructurada en los siguientes archivos, use los
mismos nombres.
openHash.c : En este
archivo usted debe implementar todos los llamados para manejar la tabla
hash. En él usted pondrá por ejemplo las funciones de
búsqueda e inserción de un dato en la tabla. Incluya
además una función para duplicar la tabla y otroa para
recorrer todos los datos ingresados en la tabla hash.
hashFunction.c: En este archivo
usted pondrá la función a utilizar para mapear un string
(la palabra) en un valor de la tabla. Esta función tendrá
un prototipo como int hash(char * str, int length, int hashCapacity);
linkedList.c : En este archivo
usted pondrá las operaciones que permiten manejar una lista
doblemente enlazada como las a utilizar en la tabla de hast abierto.
Incluya aquí todas las funciones que requiere para la
manipulación de esta lista, por ejmplo insertar, buscar,
eliminar.
sort.c: En este archivo usted
implemente algunos de los métodos de ordenamiendo antes visto
para ordenar su salida.
muletilla.c: contiene el
main que enlaza todo el programa.
La corrección de su tarea se hará en aragorn.elo.utfsm.cl
Ayuda: