Estrutura de Dados - Tabela Hash Utilizando Linguagem C

1 Problema A TechParts é uma pequena empresa especializada em manutenção e venda de peças de equipamentos eletrônicos e de informática localizada em uma cidade de médio porte Nos últimos dois anos a empresa cresceu rapidamente ampliando o número de clientes e fornecedores Esse crescimento trouxe benefícios mas também gerou um problema sério a dificuldade em organizar e consultar o estoque de peças Atualmente os funcionários registram todas as informações em planilhas eletrônicas Esse processo é lento repetitivo e propenso a erros Imagine a situação um cli ente pede uma peça específica mas o atendente precisa percorrer centenas de linhas até encontrar o código correto isso pode levar minutos preciosos Além disso é comum encontrar peças cadastradas mais de uma vez com pequenas variações no código gerando confusão no controle da quantidade e do preço Com mais de 10 mil peças cadastradas a gerência percebeu que esse método manual não é sustentável Diante disso você estagiárioa do curso de Engenharia de Software foi convidadoa para propor uma solução computacional prática e eficiente Após uma análise inicial você concluiu que o uso de tabelas hash é a técnica mais adequada para esse problema Esse tipo de estrutura de dados permite consultar inserir e remover elementos em tempo médio constante O1 trazendo agilidade e organização para o estoque da TechParts 2 Descrição do Problema Seu desafio é desenvolver um sistema em linguagem C que implemente um módulo de gerenciamento de estoque da TechParts usando hashing O sistema deverá ser capaz de Cadastrar novas peças Consultar peças já registradas Remover peças do estoque Apresentar estatísticas sobre a tabela hash Salvar e carregar dados em arquivos Permitir diferentes funções de hash para comparar eficiência Cada peça possui como chave única um código alfanumérico ex A1234 CAB009 PCB7781 Além do código deve armazenar Descrição até 60 caracteres Quantidade em estoque inteiro Preço unitário float 3 O que é um Bucket Em uma tabela hash um bucket é cada posição da tabela onde os elementos podem ser armazenados A função de hash pega a chave código da peça e a transforma em um índice numérico que aponta para um bucket específico Um bucket pode conter Nenhum elemento quando está vazio Um único elemento se não houve colisão 2 Vários elementos quando ocorre colisão e usamos listas encadeadas por exemplo Exemplo visual Suponha uma tabela hash com m 10 1 ndice 0 1 2 3 4 5 6 7 8 9 2 Bucket Se o código CAB009 gerar índice 3 ele será colocado no bucket 3 Se outro código também gerar índice 3 ocorre uma colisão Nesse caso ambos ficam armazenados no mesmo bucket em uma lista encadeada Analogia Imagine um armário cheio de gavetas numeradas A função de hash indica em qual gaveta você deve guardar uma peça Se duas peças diferentes caírem na mesma gaveta elas ficam juntas colisão O sistema precisa de um método para organizar essas colisões de forma a garantir que a busca seja sempre eficiente 4 Menu de Operações O sistema deve apresentar um menu interativo semelhante ao seguinte 1 2 SISTEMA DE ESTOQUE TECHPARTS 3 4 5 Selecione uma opcao 6 7 1 Inserir nova peca 8 2 Buscar peca por codigo 9 3 Remover peca do estoque 10 4 Exibir estatisticas da tabela 11 5 Carregar pecas de um arquivo CSV 12 6 Salvar tabela em arquivo CSV 13 7 Trocar funcao de hash Divisao Multiplicacao 14 8 Encerrar o programa 15 16 17 Digite a opcao desejada 5 Condições Técnicas A tabela hash deve ser implementada com encadeamento separado listas ligadas em cada bucket Tamanho inicial da tabela m 101 número primo 3 Quando o fator de carga α n m ultrapassar 075 deve ocorrer rehash automático dobrando aproximadamente o tamanho e escolhendo o próximo número primo Implementar duas funções hash Método da Divisão Método da Multiplicação Permitir alternar a função de hash com rehash automático Tratar entradas inválidas códigos duplicados arquivos CSV incorretos etc 6 Entrada e Saída Entrada menu interativo 1 a 8 Ao inserir solicitar codigo descricao qtde preco CSV cada linha no formato codigodescricaoqtdepreco ignorar cabeçalho Saída mensagens claras como Peça inserida com sucesso Código já existente Item não encontrado 7 Exemplo de Arquivo CSV Aqui está um exemplo de arquivo estoquecsv que pode ser usado para testar o sistema 1 codigodescricaoqtdepreco 2 A1234Sensor de temperatura151250 3 CAB009Cabo HDMI 2 metros402590 4 PCB7781Placa de rede PCIE1013000 5 BAT202Bateria notebook Dell821000 6 MEM16GBMemria RAM DDR4 16GB2532000 7 FAN120Cooler FAN 120mm304500 8 SSD500SSD Kingston 500GB1228000 9 MON24FHDMonitor 24 polegadas FullHD585000 10 MOUWL01Mouse sem fio Logitech209990 11 KEYMECHTeclado Mecnico Redragon725000 8 Atualizações Solicitadas pela Empresa Após a primeira versão do sistema a TechParts solicitou novas funcionalidades 1 Implementar também o método da dobra folding para códigos alfanuméricos e comparar com os outros dois 2 Desenvolver uma função para medir o número médio de comparações nas buscas e comparar os resultados 4 3 Produzir um relatório curto 12 páginas explicando Qual função hash apresentou melhor dispersão Qual tratamento de colisão foi mais eficiente Como os resultados se aproximam da teoria Dica final para os alunos Leiam atentamente o enunciado O objetivo deste exer cício não é apenas programar mas compreender na prática por que hashing é uma técnica fundamental em Estruturas de Dados e como ele se aplica em problemas reais de organização e busca Exemplo de Menu Listing 1 Exemplo mínimo de estrutura do programa em C 1 include stdioh 2 include stdlibh 3 include stringh 4 5 Estruturas e p r o t t i p o s aqui 6 7 int mainvoid 8 int opcao 0 9 inicializa tabela hash m 101 10 11 do 12 printf 13 printf SISTEMA DE ESTOQUE TECHPARTS 14 printf 15 printf1 Inserir nova p e a 16 printf2 Buscar p e a por c d i g o 17 printf3 Remover p e a do estoque 18 printf4 Exibir e s t a t s t i c a s da tabela 19 printf5 Carregar p e a s de um arquivo CSV 20 printf6 Salvar tabela em arquivo CSV 21 printf7 Trocar f u n o de hash D i v i s o M u l t i p l i c a o 22 printf8 Encerrar o programa 23 printfDigite a o p o desejada 24 25 if scanfd opcao 1 26 tratamento de entrada i n v l i d a 27 fprintfstderr Entrada i n v l i d a 28 consumir buffer 29 break 30 31 32 switch opcao 33 case 1 inserir break 34 case 2 buscar break 5 35 case 3 remover break 36 case 4 e s t a t s t i c a s break 37 case 5 carregar CSV break 38 case 6 salvar CSV break 39 case 7 alternar hash rehash break 40 case 8 printfEncerrando break 41 default printf O p o i n v l i d a 42 43 while opcao 8 44 45 liberar recursos 46 return 0 47 1 Inserir nova peça Entrada 1 1 Inserir nova peca 2 codigo CAB009 3 descricao Cabo HDMI 2 metros 4 qtde 40 5 preco 2590 Saída sucesso 1 Peca CAB009 inserida com sucesso Saída duplicado 1 Erro ja existe uma peca cadastrada com o codigo CAB009 2 Buscar peça por código Entrada 1 2 Buscar pea por codigo 2 codigo CAB009 Saída encontrada 1 Peca encontrada 2 Codigo CAB009 3 Descricao Cabo HDMI 2 metros 4 Quantidade 40 5 Preco 2590 Saída não encontrada 1 Nenhuma peca encontrada com o codigo informado 6 3 Remover peça Entrada 1 3 Remover peca do estoque 2 codigo CAB009 Saída removida 1 Peca CAB009 removida com sucesso Saída não encontrada 1 Erro nao foi encontrada peca com o codigo CAB009 4 Exibir estatísticas Entrada 1 4 Exibir estatisticas da tabela Saída 1 Tamanho da tabela m 101 2 Numero de itens n 7 3 Fator de carga alpha 0069 4 Buckets utilizados 6 594 5 Maior lista colisoes 2 5 Carregar CSV Entrada 1 5 Carregar peas de um arquivo CSV 2 arquivo estoquecsv Saída 1 10 itens carregados de estoquecsv 6 Salvar CSV Entrada 1 6 Salvar tabela em arquivo CSV 2 arquivo backupcsv Saída 1 Tabela salva em backupcsv 7 7 Trocar função de hash Entrada 1 7 Trocar funcao de hash Saída 1 Funcao hash alterada para Multiplicacao 2 Rehash automatico realizado Novo tamanho da tabela 211 8 Encerrar Entrada 1 8 Encerrar o programa Saída 1 Encerrando o sistema ate logo 8