EDA Tarea 3, 1 sem 2004

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:

Para la generación de la función de hash, considere alguna de estas sugerencias.
Es importante escribir código reutilizable, por usted en otras tareas o proyectos o por otros. Por ello implemente cada estructura de datos en forma "limpia", es decir las funciones genéricas y no versiones "impuras" que eventualmente mejoran marginalmente el desempeño de esta tarea. Por ejemplo, en el manejo de la tabla hash y sin pensar en reutilización de código, usted podría crear una función que busque una palabra y si no la encuentra la inserte inmediatamente (eventualmente al final de la lista, allí se dio cuenta que no estaba). Lo mejor será, implementar sólo la búsqueda. Si como resultado de su invocación se retorna NULL (no se encontró, esta constante está en sdtio.h), usted invocará insertar como un llamado independiente. En resumen trate en lo posible en desacloplar el código de openHash.c , linkedList.c, sort.c y cualquier otro archivo que usted cree, del problema particular que muletilla.c está resolviendo.
Como idea considere, si le parece adecuado, procesar todas las palabras del texto en su tabla hash (la cual se deberá reescalar sola cuando corresponda), luego copiar la tabla hash completa hacia una lista o arreglo, el cual es ordenado por sort.c . Posteriormente envia a pantalla el resultados de la lista o arreglo ordenado.
Para seleccionar las palabra por palabra del texto considere esta sugerencia.

Para identificar una palabra, puede usar una código como el siguiente:

      
      #define UPPER_TO_LOWER ('a' - 'A')
      string w;
      char c;
      do
	{
	  "lea un caracter del archivo y póngalo en c";
          if ("llegó a fin de archivo") break;
	  if ((c >= 'A') && (c <= 'Z'))
	    c += UPPER_TO_LOWER;
	  if ((c >= 'a') && (c <= 'z'))
	    "Agrenar a w el caracter c";
	}
      while ((c >= 'a') && (c <= 'z'));
      Agregar a w el caracter \0; /* todo string en C termina con un byte de valor cero */
       /* aquí tenemos la palabra en minúscula escrita contenida en w */

Más ayuda se incluirá en la medida que surjan preguntas.