Dando continuidade ao nosso Curso de Programação C e ao módulo sobre a estrutura de busca tabela hash, vamos ver nesta aula como implementar uma TABELA HASH com lista encadeada na prática.
Nesta versão nós teremos um vetor de listas encadeadas. Assim, cada posição de nossa tabela terá uma lista simplesmente encadeada. Dessa forma, não será necessário fazer tratamento de colisões, uma vez que os elementos de mesmo índice serão inseridos na mesma lista.
Vamos iniciar desenvolvendo as estruturas que iremos utilizar, neste caso a estrutura nó e a estrutura lista.
/*
Estruturas para a lista simplesmente encadeada.
*/
typedef struct no{
int chave;
struct no *proximo;
}No;
typedef struct{
No *inicio;
int tam;
}Lista;
No início todas as listas devem estar vazias. Então o primeiro passo é fazer um procedimento para inicializar cada lista, fazendo o início igual a nulo e o tamanho igual a zero.
/*
Procedimento para inicializar corretamente cada lista da tabela.
*/
void inicializarLista(Lista *l){
l->inicio = NULL;
l->tam = 0;
}
Como cada posição da tabela contêm uma lista encadeada, precisamos desenvolver funções ou procedimentos para as principais funcionalidades de uma lista: inserir, buscar, imprimir. Como já abordamos estes temas nas aulas sobre listas simplesmente encadeadas vamos apenas apresentar o código sem muitos detalhes.
/*
Procedimento para inserir um elemento no início na lista recebida como parâmetro
*/
void inserir_na_lista(Lista *l, int valor){
No *novo = malloc(sizeof(No));
if(novo){
novo->chave = valor;
novo->proximo = l->inicio;
l->inicio = novo;
l->tam++;
}
else
printf("\n\tErro ao alocar memoria!\n");
}
// Função para buscar um elemento. Retorna o elemento encontrado ou zero caso contrário.
int buscar_na_lista(Lista *l, int valor){
No *aux = l->inicio;
while(aux && aux->chave != valor)
aux = aux->proximo;
if(aux)
return aux->chave;
return 0;
}
// Procedimento para imprimir a lista recebida como parâmetro.
void imprimir_lista(Lista *l){
No *aux = l->inicio;
printf(" Tam: %d: ", l->tam);
while(aux){
printf("%d ", aux->chave);
aux = aux->proximo;
}
}
Como cada posição da tabela terá uma lista encadeada, precisamos percorrer toda a tabela inicializando cada lista com o primeiro procedimento que desenvolvemos, como apresentado a seguir.
/*
Procedimento que percorre a tabela inicializando cada lista
*/
void inicializarTabela(Lista t[]){
int i;
for(i = 0; i < TAM; i++)
inicializarLista(&t[i]);
}
A função hash não sofre nenhuma alteração. Continuaremos utilizando o resto da divisão pelo tamanho da tabela, como apresentado a seguir.
/*
Função hash ou função de espalhamento
*/
int funcaoHash(int chave){
return chave % TAM;
}
Agora que já temos a tabela com cada lista devidamente inicializada, podemos pensar no procedimento para inserção. Este procedimento receberá o valor a ser inserido, irá obter através da função hash o índice da tabela onde o elemento será inserido e chamará o procedimento de inserção para a lista daquela posição.
/*
Procedimento para inserir um elemento na tabela hash
*/
void inserir(Lista t[], int valor){
int id = funcaoHash(valor);
inserir_na_lista(&t[id], valor);
}
Também precisamos realizar buscas em nossa tabela, afinal essa é a principal utilidade de uma tabela hash, tornar o processo de busca mais eficiente. A função a seguir recebe a tabela e o valor a ser procurado, gera o índice de acesso e utiliza a função de busca da lista encadeada para finalizar a busca.
/*
Procedimento para realizar uma busca na tabela.
*/
int busca(Lista t[], int chave){
int id = funcaoHash(chave);
return buscar_na_lista(&t[id], chave);
}
Pode ser interessante imprimir toda a tabela. O procedimento a seguir realiza essa tarefa, recebe a tabela como parâmetro e, fazendo uso do procedimento de impressão da lista encadeada, imprime todas as listas.
/*
Procedimento para imprimir toda a tabela.
*/
void imprimir(Lista t[]){
int i;
for(i = 0; i < TAM; i++){
printf("%2d = ", i);
imprimir_lista(&t[i]);
printf("\n");
}
}
A seguir apresentamos o código completo de teste para uma tabela hash com lista encadeada inclusive com um menu de opções dentro da função principal.
Código de exemplo completo em C para uma tabela hash com listas encadeadas
/*
Aula 261: Tabela Hash com lista encadeada
Código escrito por Wagner Gaspar
Setembro de 2021
*/
// 2 * 15 = 31
#define TAM 31
typedef struct no{
int chave;
struct no *proximo;
}No;
typedef struct{
No *inicio;
int tam;
}Lista;
void inicializarLista(Lista *l){
l->inicio = NULL;
l->tam = 0;
}
void inserir_na_lista(Lista *l, int valor){
No *novo = malloc(sizeof(No));
if(novo){
novo->chave = valor;
novo->proximo = l->inicio;
l->inicio = novo;
l->tam++;
}
else
printf("\n\tErro ao alocar memoria!\n");
}
int buscar_na_lista(Lista *l, int valor){
No *aux = l->inicio;
while(aux && aux->chave != valor)
aux = aux->proximo;
if(aux)
return aux->chave;
return 0;
}
void imprimir_lista(Lista *l){
No *aux = l->inicio;
printf(" Tam: %d: ", l->tam);
while(aux){
printf("%d ", aux->chave);
aux = aux->proximo;
}
}
void inicializarTabela(Lista t[]){
int i;
for(i = 0; i < TAM; i++)
inicializarLista(&t[i]);
}
int funcaoHash(int chave){
return chave % TAM;
}
void inserir(Lista t[], int valor){
int id = funcaoHash(valor);
inserir_na_lista(&t[id], valor);
}
int busca(Lista t[], int chave){
int id = funcaoHash(chave);
return buscar_na_lista(&t[id], chave);
}
void imprimir(Lista t[]){
int i;
for(i = 0; i < TAM; i++){
printf("%2d = ", i);
imprimir_lista(&t[i]);
printf("\n");
}
}
int main(){
int opcao, valor, retorno;
Lista tabela[TAM];
inicializarTabela(tabela);
do{
printf("\n\t0 - Sair\n\t1 - Inserir\n\t2 - Buscar\n\t3 -Imprimir\n");
scanf("%d", &opcao);
switch(opcao){
case 1:
printf("\tQual valor desseja inserir? ");
scanf("%d", &valor);
inserir(tabela, valor);
break;
case 2:
printf("\tQual valor desseja buscar? ");
scanf("%d", &valor);
retorno = busca(tabela, valor);
if(retorno != 0)
printf("\tValor encontrado: %d\n", retorno);
else
printf("\tValor nao encontrado!\n");
break;
case 3:
imprimir(tabela);
break;
default:
printf("Opcao invalida!\n");
}
}while(opcao != 0);
return 0;
}
