Dando continuidade ao estudo da estrutura de busca tabela hash, na aula de hoje vamos aprender como criar uma TABELA HASH com várias structs e não apenas um número inteiro.
Para este exemplo iremos criar uma tabela hash linear com vetor, sem fazer uso de listas encadeadas. Isso implica que será necessário tratar colisões.
Vamos iniciar criando nossas estruturas. Iremos trabalhar com o tipo pessoa. Cada pessoa terá um nome, um cpf, que será nossa chave de busca, uma data de nascimento, um endereço e um contrato de trabalho que serão outras estruturas. O contrato de trabalho também terá em seu interior uma data, mas neste caso a data de assinatura do contrato. Estes são apenas alguns dados, outros podem ser acrescentados a fim de tornar o exemplo mais completo.
/*
Estruturas a serem utilizadas
*/
typedef struct{
int dia, mes, ano;
}Data;
typedef struct{
char rua[50];
char bairro[50];
char cidade[50];
char pais[50];
int num, cep;
}Endereco;
typedef struct{
int codigo;
Data dataAss; // data de assinatura do contrato
char cargo[50];
float salario;
}Contrato;
typedef struct{
char nome[50];
int cpf;
Data dataNas; // data de nascimento
Endereco end;
Contrato contr;
}Pessoa;
A fim de tornar o código mais legível, é interessante que cada estrutura tenha suas funções e procedimentos individuais. Assim, o processo de impressão das informações de uma pessoa será feito pelo conjunto de procedimentos a seguir.
/*
Procedimento para imprimir uma data
*/
void imprimirData(Data d){
printf("%d/%d/%d\n", d.dia, d.mes, d.ano);
}
// Procedimento para imprimir um endereço
void imprimirEndereco(Endereco end){
printf("\tEndereco:\n");
printf("\t\tRua: %s", end.rua);
printf("\t\tBairro: %s", end.bairro);
printf("\t\tCidade: %s", end.cidade);
printf("\t\tPais: %s", end.pais);
printf("\t\tNumero: %d\n", end.num);
printf("\t\tCep: %d\n", end.cep);
}
// procedimento para imprimir um contrato
void imprimirContrato(Contrato c){
printf("\tContrato %d:\n", c.codigo);
printf("\t\tCargo: %s", c.cargo);
printf("\t\tSalario R$%.2f\n", c.salario);
printf("\t\tData de ad.: ");
imprimirData(c.dataAss); // chama a impressão da data apresentada acima
}
// procedimento para imprimir os dados de uma pessoa
void imprirPessoa(Pessoa p){
printf("\n\tNome: %s", p.nome);
printf("\tCpf: %d\n", p.cpf);
printf("\tData de nas.: ");
imprimirData(p.dataNas); // usa o imprimir data acima
imprimirEndereco(p.end); // usa o imprimir endereço acima
imprimirContrato(p.contr); // usa o imprimir contrato acima
}
Assim como na impressão, também será necessário ler todas estas informações a partir do teclado. As funções a seguir farão isso.
/*
Função para ler uma data
*/
Data lerData(){
Data d;
printf("\nDigite a data no formato dd mm aaaa: ");
scanf("%d%d%d", &d.dia, &d.mes, &d.ano);
getchar();
return d;
}
// Função para ler um endereço
Endereco lerEndereco(){
Endereco end;
printf("\nRua: ");
fgets(end.rua, 49, stdin);
printf("\nBairro: ");
fgets(end.bairro, 49, stdin);
printf("\nCidade: ");
fgets(end.cidade, 49, stdin);
printf("\nPais: ");
fgets(end.pais, 49, stdin);
printf("\nNumero: ");
scanf("%d", &end.num);
printf("\nCep: ");
scanf("%d", &end.cep);
getchar();
return end;
}
// Função para ler um contrato
Contrato lerContrato(){
Contrato c;
printf("\nCodigo do contrato: ");
scanf("%d", &c.codigo);
printf("\nData de assinatura: ");
c.dataAss = lerData(); // chama a função para ler uma data
printf("\nCargo: ");
fgets(c.cargo, 49, stdin);
printf("\nSalario: R$");
scanf("%f", &c.salario);
getchar();
return c;
}
// Função para ler os dados de uma pessoa
Pessoa lerPessoa(){
Pessoa p;
printf("\nNome: ");
fgets(p.nome, 49, stdin);
printf("\nCpf: ");
scanf("%d", &p.cpf);
printf("\nData de nascimento: ");
p.dataNas = lerData(); // chama a função para ler uma data
p.contr = lerContrato(); // chama a função para ler um contrato
p.end = lerEndereco(); // chama a função para ler um endereço
return p;
}
Agora que já criamos as estruturas necessárias, os procedimentos de impressão de cada estrutura e as funções para ler cada uma das estruturas, podemos pensar na tabela propriamente dita. Nossa tabela será um vetor de pessoas. Como o cpf será nossa chave e precisamos saber identificar as posições vazias, precisamos percorrer a tabela e dizer que todas as posições estão vazias no início. Isso será feito pelo procedimento a seguir, que faz todo cpf ser igual a zero.
/*
Procedimento que inicializa a tabela hash
*/
void inicializarTabela(Pessoa t[]){
int i;
for(i = 0; i < TAM; i++)
t[i].cpf = 0; // cpf igual a zero significa posição vazia
}
Manteremos aqui a nossa função hash dos exemplos anteriores.
/*
Função hash ou função de espalhamento
*/
int funcaoHash(int chave){
return chave % TAM;
}
A seguir apresento o procedimento para realizar a inserção de uma pessoa na tabela hash. Observe que o procedimento recebe apenas a tabela e em seu interior faço a leitura de uma pessoa. Esta foi a minha abordagem, nada impede que a leitura dos dados da pessoa a ser inserida seja feita antes e passado como parâmetro. Outro detalhe é que não estamos utilizando lista encadeada, então é necessário tratar colisão.
/*
Procedimento para inserir uma pessoa na tabela hash
*/
void inserir(Pessoa t[]){
Pessoa p = lerPessoa();
int id = funcaoHash(p.cpf);
while(t[id].cpf != 0){
id = funcaoHash(id + 1);
}
t[id] = p;
}
A seguir é apresentado o procedimento para realizar a busca. Ele recebe como parâmetro a tabela e um cpf a ser procurado. Seu retorno é um ponteiro para a pessoa, se o cpf for encontrado, ou null caso contrário.
/*
Procedimento para realizar a busca
*/
Pessoa* busca(Pessoa t[], int chave){
int id = funcaoHash(chave);
printf("\nIndice gerada: %d\n", id);
while(t[id].cpf != 0){
if(t[id].cpf == chave)
return &t[id];
else
id = funcaoHash(id + 1);
}
return NULL;
}
A seguir fazemos a impressão de toda a tabela. Como muitas posições podem estar vazias, cpf igual a zero, imprimimos apenas as posições cujo cpf é diferente de zero.
/*
Procedimento para imprimir a tabela
*/
void imprimir(Pessoa t[]){
int i;
for(i = 0; i < TAM; i++){
printf("%d\n", i);
if(t[i].cpf != 0)
imprirPessoa(t[i]);
printf("\n----------------------\n");
}
}
Código de exemplo completo em C para uma Tabela Hash de Pessoas
/*
Aula 262: Tabela Hash com struct
Código escrito por Wagner Gaspar
Setembro de 2021
*/
// 2 * 15 = 31
#define TAM 15
typedef struct{
int dia, mes, ano;
}Data;
typedef struct{
char rua[50];
char bairro[50];
char cidade[50];
char pais[50];
int num, cep;
}Endereco;
typedef struct{
int codigo;
Data dataAss;
char cargo[50];
float salario;
}Contrato;
typedef struct{
char nome[50];
int cpf;
Data dataNas;
Endereco end;
Contrato contr;
}Pessoa;
// -------------- impressão das informaões de uma Pessoa ------------------------
void imprimirData(Data d){
printf("%d/%d/%d\n", d.dia, d.mes, d.ano);
}
void imprimirEndereco(Endereco end){
printf("\tEndereco:\n");
printf("\t\tRua: %s", end.rua);
printf("\t\tBairro: %s", end.bairro);
printf("\t\tCidade: %s", end.cidade);
printf("\t\tPais: %s", end.pais);
printf("\t\tNumero: %d\n", end.num);
printf("\t\tCep: %d\n", end.cep);
}
void imprimirContrato(Contrato c){
printf("\tContrato %d:\n", c.codigo);
printf("\t\tCargo: %s", c.cargo);
printf("\t\tSalario R$%.2f\n", c.salario);
printf("\t\tData de ad.: ");
imprimirData(c.dataAss);
}
void imprirPessoa(Pessoa p){
printf("\n\tNome: %s", p.nome);
printf("\tCpf: %d\n", p.cpf);
printf("\tData de nas.: ");
imprimirData(p.dataNas);
imprimirEndereco(p.end);
imprimirContrato(p.contr);
}
// ------------ Leitura dos dados de uma Pessoa -------------------------
Data lerData(){
Data d;
printf("\nDigite a data no formato dd mm aaaa: ");
scanf("%d%d%d", &d.dia, &d.mes, &d.ano);
getchar();
return d;
}
Endereco lerEndereco(){
Endereco end;
printf("\nRua: ");
fgets(end.rua, 49, stdin);
printf("\nBairro: ");
fgets(end.bairro, 49, stdin);
printf("\nCidade: ");
fgets(end.cidade, 49, stdin);
printf("\nPais: ");
fgets(end.pais, 49, stdin);
printf("\nNumero: ");
scanf("%d", &end.num);
printf("\nCep: ");
scanf("%d", &end.cep);
getchar();
return end;
}
Contrato lerContrato(){
Contrato c;
printf("\nCodigo do contrato: ");
scanf("%d", &c.codigo);
printf("\nData de assinatura: ");
c.dataAss = lerData();
printf("\nCargo: ");
fgets(c.cargo, 49, stdin);
printf("\nSalario: R$");
scanf("%f", &c.salario);
getchar();
return c;
}
Pessoa lerPessoa(){
Pessoa p;
printf("\nNome: ");
fgets(p.nome, 49, stdin);
printf("\nCpf: ");
scanf("%d", &p.cpf);
printf("\nData de nascimento: ");
p.dataNas = lerData();
p.contr = lerContrato();
p.end = lerEndereco();
return p;
}
// ---------- funções e procedimentos para a tabela hash -----------
void inicializarTabela(Pessoa t[]){
int i;
for(i = 0; i < TAM; i++)
t[i].cpf = 0;
}
int funcaoHash(int chave){
return chave % TAM;
}
void inserir(Pessoa t[]){
Pessoa p = lerPessoa();
int id = funcaoHash(p.cpf);
while(t[id].cpf != 0){
id = funcaoHash(id + 1);
}
t[id] = p;
}
Pessoa* busca(Pessoa t[], int chave){
int id = funcaoHash(chave);
printf("\nIndice gerada: %d\n", id);
while(t[id].cpf != 0){
if(t[id].cpf == chave)
return &t[id];
else
id = funcaoHash(id + 1);
}
return NULL;
}
void imprimir(Pessoa t[]){
int i;
for(i = 0; i < TAM; i++){
printf("%d\n", i);
if(t[i].cpf != 0)
imprirPessoa(t[i]);
printf("\n----------------------\n");
}
}
int main(){
int opcao, valor, retorno;
Pessoa *buscar, tabela[TAM];
inicializarTabela(tabela);
do{
printf("\n\t0 - Sair\n\t1 - Inserir\n\t2 - Buscar\n\t3 -Imprimir\n");
scanf("%d", &opcao);
getchar();
switch(opcao){
case 1:
inserir(tabela);
break;
case 2:
printf("\tQual cpf desseja buscar? ");
scanf("%d", &valor);
buscar = busca(tabela, valor);
if(buscar){
printf("\nCpf encontrado:\n");
imprirPessoa(*buscar);
}
else
printf("\tCpf nao encontrado!\n");
break;
case 3:
imprimir(tabela);
break;
default:
printf("Opcao invalida!\n");
}
}while(opcao != 0);
return 0;
}
