Nesta aula, vimos a estrutura tabela de hashing (ou de espalhamento). A aplicacao para esta estrutura foi buscar a palavra mais frequente em um texto. Em particular, pegamos o texto da biblia sagrada em ingles e descobrimos que a palavra mais frequente e "the"./*** MAC 2301 - Laboratorio de Programacao** Exercicio da aula 11** Assunto: Lista de espalhamento (hashing table)* Aplicacao: descobrir a palavra mais frequente 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;/*** Funcao de "espalhamento". Pode ser qualquer funcao que* leve um dado de um no num numero entre 0 e MAX* O ideal e que ela distribua uniformemente entre os* possiveis resultados para diminuir o numero de colisoes.**/int funcaoDeHashing(char palavra[MAX_PALAVRA]){ int resultado = (int) palavra[0] % MAX; /* correcao de um bug: caracteres acentuados viravam valores negativos */ if(resultado < 0) resultado = -resultado; return resultado;}void insereNaLista(char novaEntrada[MAX_PALAVRA], noh** lista) /* sem cabeca */{ int encontrou; noh *novo, *varre; varre = *lista; while(varre != NULL) { /* se encontrou novaEntrada na lista, apenas * incrementa o contador da frequencia e sai da funcao */ if(strcmp(varre->palavra, novaEntrada) == 0) { (varre->freq)++; return; } varre = varre->prox; } /* se chegar nesse ponto, nao ha a novaEntrada na lista, entao inserimos */ novo = malloc(sizeof(noh)); strcpy(novo->palavra, novaEntrada); novo->freq = 1; if(*lista != NULL) novo->prox = *lista; else novo->prox = NULL; *lista = novo;}/* Funcao de insercao 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 | Conteudo 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 cabeca */{ 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 frquencia maxima */ 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 frequente(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] =