Tabela de Espalhamento em C

Prévia do material em texto

Público 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
ALGORITMOS E ESTRUTURA DE 
DADOS 
 
 
 
 
 
Roteiro 
Aula Prática 
 
2 
 
Público 
ROTEIRO DE AULA PRÁTICA 
 
PROGRAMAÇÃO EM BANCO DE DADOS: 
 
Unidade: U3_DEFINIÇÃO_E_USOS_DE_TABELAS_DE_ESPALHAMENTO 
Aula: A2_OPERAÇÕES EM_TABELAS_DE_ESPALHAMENTO 
 
OBJETIVOS 
Definição dos objetivos da aula prática: 
- Compreender o funcionamento das tabelas de espalhamento e o tratamento de colisões.; 
- Implementar técnicas de tratamento de colisões em uma tabela de espalhamento utilizando a 
linguagem de programação C. 
 
SOLUÇÃO DIGITAL: 
 
“GDBOnline” 
O GDBonline é uma ferramenta online que permite a compilação e execução de código 
diretamente em um navegador da web, sem a necessidade de instalar um software localmente. 
Ele oferece suporte a várias linguagens de programação, incluindo a linguagem de programação 
C, sendo útil tanto para aprendizado quanto para testes rápidos de código. A plataforma 
proporciona uma interface simples e acessível, permitindo que usuários possam testar, depurar 
e compartilhar seus códigos de uma maneira rápida e fácil. 
LINK SOLUÇÃO DIGITAL ONLINE (EXCETO ALGETEC): https://www.onlinegdb.com 
 
PROCEDIMENTOS PRÁTICOS E APLICAÇÕES 
Procedimento/Atividade nº 1 
Inserir o nome do experimento: Tabela de Espalhamento 
 
Atividade proposta: Nesta atividade, você será desafiado a implementar uma tabela de 
espalhamento (hash table) que utiliza um método de tratamento de colisões. O cenário envolve 
a criação de um sistema de gerenciamento de senhas, onde múltiplos usuários devem ser 
cadastrados e suas informações (nome de usuário e senha) precisam ser armazenadas de 
maneira eficiente em uma tabela de espalhamento. 
Porém, é possível que várias senhas gerem o mesmo valor de hash, o que causa uma colisão. 
Para lidar com esse problema, você deverá escolher e implementar uma técnica de tratamento 
de colisões, como encadeamento (listas ligadas) ou endereçamento aberto (linear probing). 
https://www.onlinegdb.com/
 
3 
 
Público 
Além disso, será necessário implementar operações de inserção e busca de elementos na tabela 
de espalhamento, garantindo que o sistema de senhas funcione corretamente, mesmo diante de 
colisões. 
 
Procedimentos para a realização da atividade: Siga as etapas descritas a seguir para realizar 
a atividade. Nessa prática, você deverá utilizar a ferramenta GDBOnline para construir o algoritmo 
solicitado na situação proposta. 
 
• Acesse o link e selecione a linguagem como é apresentada na Figura 01. Escolha a 
linguagem C: 
 
Figura 01 – Ferramenta GDBOnline. 
 
Fonte: Elaborada pelo autor. 
 
Agora basta adicionar a codificação necessária para criar o seu algoritmo. Dessa forma, se 
atente as solicitações feitas no item “atividade proposta”. 
 
Orientações: 
• Estude como funcionam as tabelas de espalhamento (hash tables) e os métodos de 
tratamento de colisões, como encadeamento com listas ligadas ou endereçamento 
aberto. 
• Implemente, na linguagem C, uma tabela de espalhamento que utilize uma técnica 
de tratamento de colisões para garantir que múltiplos valores que geram o mesmo 
hash possam ser armazenados e acessados corretamente. 
 
4 
 
Público 
• Teste a sua tabela de espalhamento com diferentes cenários de entrada, 
simulando situações onde colisões ocorrem e precisam ser tratadas de maneira 
eficiente. 
 
Teste os comandos no “GDBOnline” para garantir que realmente estejam funcionando 
corretamente. 
 
 
Avaliando os resultados: 
Responda a seguinte questão de acordo com o cenário a seguir: 
Durante o desenvolvimento do sistema de gerenciamento de senhas utilizando uma tabela de 
espalhamento, você percebeu que a eficiência das operações de busca, inserção e tratamento 
de colisões varia de acordo com a função hash utilizada e com a técnica aplicada (encadeamento 
ou endereçamento aberto). Por que é importante compreender o impacto da função hash e dos 
métodos de tratamento de colisões no desempenho de sistemas que armazenam e acessam 
informações sensíveis, como senhas de usuários? 
Checklist: 
• Implementar uma função de hash eficiente para a tabela de espalhamento. 
• Aplicar uma técnica de tratamento de colisões (encadeamento ou endereçamento 
aberto). 
• Implementar as operações de inserção e busca na tabela de espalhamento. 
• Testar a tabela de espalhamento com entradas que geram colisões. 
• Garantir que os elementos sejam corretamente armazenados e acessados, mesmo em 
situações de colisão. 
 
 
RESULTADOS 
Resultados do experimento: 
O estudante deve entregar um arquivo em PDF contendo toda a codificação necessária para 
realizar o exercício. 
O arquivo deverá conter: 
• Capa; 
• Folha de rosto com os dados da disciplina e do aluno; 
• Codificação completa do exercício; 
• Prints da execução dos comandos no GDBOnline; 
• Referências bibliográficas (quando houver). 
 
 
5 
 
Público 
Resultados de Aprendizagem: 
Ao final da atividade, espera-se que o aluno: 
• Compreenda o funcionamento das tabelas de de espalhamento; 
• Capaz de implementar soluções para o tratamento de colisões utilizando técnicas como 
encadeamento ou endereçamento aberto; 
• Seja capaz de aplicar a estrutura de dados de hash table para otimizar a busca e 
armazenamento de informações, garantindo eficiência no tratamento de colisões.