Título: Ayuda con problema de hashing en C Publicado por: Albpenu en 27 Mayo 2021, 19:29 pm Buenas tardes, compas, he estado dándole vueltas a este ejercicio y creo que no sé plantearlo correctamente:
-------------------------------------------------------- ENUNCIADO: Hashing. Se desea implementar un buscador de documentos de manera que al introducir una palabra de búsqueda nos devuelva el nombre de todos los documentos donde aparece esa palabra (no debe devolver el documento completo, sólo el nombre del documento). La implementación debe realizarse usando obligatoriamente una tabla hash y de dos maneras diferentes como se indica a continuación: i. (1,5 puntos) Gestionando las colisiones mediante una técnica de direccionamiento cerrado a elegir por el alumno (lineal, cuadrática o dependiente de clave con recorrido completo). La valoración dependerá de la complejidad de la técnica elegida, siendo lineal y cuadrática menos compleja que la dependiente de clave. ii. (1,5 puntos) Gestionando las colisiones mediante encadenamiento. En este caso se debe además devolver los nombres de los documentos ordenados por relevancia para cada palabra, siendo un documento A más relevante que un documento B para una palabra P si número_palabras(P, A) > número_palabras(P, B), es decir, el número de ocurrencias de P en el documento A es mayor que en el documento B. A continuación se muestra un ejemplo del comportamiento deseado del programa. Suponga que se tienen los tres siguientes documentos D1 D2 D3 Al buscar la palabra “perro”, el programa debe devolver los nombres de documentos “D1” y “D3”. Además, en el apartado b) debe devolver D3 antes que D1 ya que Número_palabras(“perro”, D1) = 1; Número_palabras(“perro”, D3) = 2; por tanto D3 > D1 Se pueden usar los documentos de texto “docA.txt”, “docB.txt” y “docC.txt” adjuntos con este enunciado para probar el programa realizado. Notas importantes: El usuario no puede indicar ni el tamaño de la tabla, ni el campo clave ni ningún otro parámetro de hashing, de eso se debe encargar el programa automáticamente. Se valorará altamente que la tabla hash se cree de manera dinámica y se vaya redimensionando su tamaño según sea necesario o cuando se supere el un factor de carga fijado por el alumno. --------------------------------------------------------- LO QUE LLEVO HECHO: *** EN EL MAIN.C: #include "hashing.h" #include <stdio.h> #include <stdlib.h> #include <locale.h> int main(int argc, char *argv[]) { // Codificación en español para la terminal setlocale(LC_ALL, ""); char word[256]; int tam = 0; printf("Escriba la palabra a buscar: "); scanf("%s",word); tam = fileWordsCounter("docC.txt"); myreg t_hash[tam]; init(t_hash, tam);// PONE TODA LA TABLA A -1 (FREE) insert(t_hash, tam); search(word, t_hash, tam); //readFile("docA.txt",word); // if(key == -1) // printf("La palabra a buscar no existe en los documentos"); // else{ // printf("Tabla hash[%d]: ",key); // printfList(hashTable[key]); // } system("PAUSE"); return EXIT_SUCCESS; } ***EN EL HASHING.C: #include "hashing.h" #include <stdio.h> #include <stdlib.h> #include <string.h> int fileWordsCounter(char *fileName){ char ch; int words = 0; char word[50]; FILE *fp = fopen(fileName, "r"); if(fp==NULL) { printf("\n ¡No se puede abrir el archivo! \n"); exit(0); } else { while((ch = fgetc(fp)) != EOF && fscanf(fp,"%s",word)) { words++; } } return words; } void init(myreg t_hash[], int tam){ int i; for(i = 0; i < tam; i++){ t_hash.key = 0; t_hash.value = "LIBRE"; } } void insert(myreg t_hash[], char *fileName, int tam){ int pos; pos = H(reg.key, tam); FILE *fp = fopen(fileName, "r"); if(fp==NULL) { printf("\n ¡No se puede abrir el archivo! \n"); exit(0); } else { for(int i = 0; i < tam, i++) { fscanf() } } } int search(myreg t_hash[], int id, int tam){ int pos; pos = H(id, tam); if(t_hash[pos].key == FREE) return -1; //NO EXISTE; PARO DE BUSCAR if(t_hash[pos].key == id) return pos; else{ printf("Colisión\n"); return -1; //CAMBIAR CONVENIENTEMENTE SEGÚN ESTRATEGIA } } void readFile(char *fileName, char *word){ char filewords[120]; struct word myreg; FILE *fp = fopen(fileName, "r"); if(fp==NULL) { printf("\n ¡No se puede abrir el archivo! \n"); exit(0); } int count = 0; int total = 0; while(fscanf(fp,"%s",filewords) != EOF) { if (strcmp(filewords, word) == 0) { count++; } } if(count == 0) { printf("\nEl documento '%s' no contiene la palabra '%s'\n",fileName,word); } else if(count == 1) { printf("\nLa palabra '%s' se repite 1 vez en el documento '%s'\n",word,fileName); myreg.key = count; } else { printf("\nLa palabra '%s' se repite %d veces en el documento '%s'\n",word,count,fileName); myreg.key = count; } printf("\n"); fclose(fp); } // N/M, donde N es el numero de elemento insertados // M es el tamano de la tabla hash float loadfactor(myreg t_hash[], int tam) { int n_elems = 0; int i; for(i = 0; i < tam; i++){ if(t_hash.key != LIBRE && t_hash.key != BORRADO) n_elems++; } return ((float)n_elems/tam); } void show(myreg t_hash[], int tam){ int i; for(i = 0; i < tam; i++){ printf("%d | ", t_hash); } printf("\n"); } ***Muchísimas gracias por la ayuda, compas!😊😊😊😊*** - EN HASHING.H puse esto: #ifndef HASHING_H_INCLUDED #define HASHING_H_INCLUDED #define FREE -1 #define DELETED -2 typedef struct word{ char key; char value; } myreg; int fileWordsCounter(char *fileName); void init(myreg t_hash[], int tam) void insert(myreg t_hash[], myreg reg, int tam); int search(myreg t_hash[], int id, int tam); void show(myreg t_hash[], int tam); #endif // HASHING_H_INCLUDED Muchas gracias de nuevo y disculpad mi desconocimiento en esto...😥😥😥 |