Tabela de hashing

Nesta aula, vimos a estrutura tabela de hashing (ou de espalhamento). A aplicação para esta estrutura foi buscar a palavra mais freqüente em um texto. Em particular, pegamos o texto da bíblia sagrada em inglês e descobrimos que a palavra mais freqüente é "the".

/**
* MAC 2301 - Laboratório de Programação
*
* Exercício da aula 11
*
* Assunto: Lista de espalhamento (hashing table)
* Aplicação: descobrir a palavra mais freqüente num texto longo
*
**/

#include 
#include 
#include 

#define MAX_PALAVRA 80
#define MAX 167 /* tamanho da tabela de hashing -> melhor se for um primo */

typedef struct node
{
 char palavra[MAX_PALAVRA];
 int freq;
 struct node* prox;
} noh;

/**
* Função de "espalhamento". Pode ser qualquer função que
* leve um dado de um nó num número entre 0 e MAX
* O ideal é que ela distribua uniformemente entre os
* possíveis resultados para diminuir o número de colisões.
**/
int funcaoDeHashing(char palavra[MAX_PALAVRA])
{
 int resultado = (int) palavra[0] % MAX;

 /* correção de um bug: caracteres acentuados viravam valores negativos */
 if(resultado < 0)
   resultado = -resultado;
 return resultado;
}

void insereNaLista(char novaEntrada[MAX_PALAVRA], noh** lista) /* sem cabeça */
{
 int encontrou;
 noh *novo, *varre;
 varre = *lista;
 while(varre != NULL)
 {
   /* se encontrou novaEntrada na lista, apenas
    * incrementa o contador da freqüência e sai da função */
   if(strcmp(varre->palavra, novaEntrada) == 0)
   {
     (varre->freq)++;
     return;
   }
   varre = varre->prox;
 }
 /* se chegar nesse ponto, não há a novaEntrada na lista, então inserimos */
 novo = malloc(sizeof(noh));
 strcpy(novo->palavra, novaEntrada);
 novo->freq = 1;
 if(*lista != NULL)
   novo->prox = *lista;
 else
   novo->prox = NULL;
 *lista = novo;
}

/* Função de inserção na tabela de hashing */
void insereNaTabela(char novaEntrada[MAX_PALAVRA], noh* tabela[MAX])
{
 insereNaLista(novaEntrada, &(tabela[funcaoDeHashing(novaEntrada)]));
}


/**
* Procedimento usado apenas para depurar.
**/
void imprimeLista(noh *lista)
{
 noh *varre = lista;
 printf("\n\n  -----\n |\n | Conteúdo da lista: \n |\n"); fflush(NULL);
 while(varre != NULL)
 {
   printf(" |  %s \n", varre->palavra);
   varre = varre->prox;
 }
 printf(" |\n  -----\n\n"); fflush(NULL);
}

/**
* Procedimento usado apenas para depurar.
**/
void imprimeTudo(noh* tabela[MAX])
{
 int i;
 noh* varre;

 varre = malloc(sizeof(noh));

 printf("\nEstado atual: \n");

 for(i = 0; i < MAX; i++)
 {
   varre = tabela[i];
   while(varre != NULL)
   {
     printf(" [%d] -> %s apareceu %d vezes\n", i,
            varre->palavra, varre->freq);
     varre = varre->prox;
   }
 }
 printf("----\n\n");
 fflush(NULL);
}

void removeLista(noh* lista) /* sem cabeça */
{
 noh* varre;
 if(lista != NULL)
 {
   if(lista->prox != NULL)
   {
     varre = lista->prox;
     while(varre != NULL)
     {
       lista->prox = varre->prox;
       free(varre);
       varre = lista->prox;
     }
   }
   free(lista);
 }
}

void imprimeResultado(noh* tabela[MAX])
{
 int i, freqMax;
 noh* varre;
 noh* maisFrequentes; /* lista com as palavras com a frqüência máxima */

 maisFrequentes = NULL;
 freqMax = 0;
 varre = malloc(sizeof(noh));
 for(i = 0; i < MAX; i++)
 {
   varre = tabela[i];
   while(varre != NULL)
   {
     if(varre->freq == freqMax)
     {
       insereNaLista(varre->palavra, &maisFrequentes);
     }
     else if (varre->freq > freqMax)
     {
       freqMax = varre->freq;
       removeLista(maisFrequentes);
       maisFrequentes = NULL;
       insereNaLista(varre->palavra, &maisFrequentes);
     }
     varre = varre->prox;
   }
 }
 printf("\n\n   Palavra(s) mais freqüênte(s) no texto (%dx):\n\n", freqMax);
 varre = maisFrequentes;
 while (varre != NULL)
 {
   printf("      \"%s\"\n", varre->palavra);
   varre = varre->prox;
 }
 printf("\n\n   ");
}


int main()
{
 noh* tabela[MAX];
 noh* umNoh;
 char umaPalavra[MAX_PALAVRA];
 int final, i;

 umNoh = NULL;

 /* inicializando a tabela inteira de hashing com null */
 for(i = 0; i < MAX; i++)
   tabela[i] = NULL;

 /* Pega a primeira palavra da entrada padrão */
 final = scanf("%s", &umaPalavra);

 /* Laço que pega cada palavra da entrada padrão
  * e insere na tabela de hashing */
 while(final != EOF)
 {
   insereNaTabela(umaPalavra, tabela);
   final = scanf("%s", &umaPalavra);
 }

 imprimeResultado(tabela);

 system("pause");

 printf("\n");

 return 0;
}