Ayuda con problema de hashing en C

Iniciado por Albpenu, 27 Mayo 2021, 19:29 PM

0 Miembros y 1 Visitante están viendo este tema.

Albpenu

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...😥😥😥