Estrutura de dados indicada para ficha de cliente? - C - Portugal-a-Programar
Estrutura de dados indicada para ficha de cliente?
Por Nazgulled, 21 de Março de 2009 em C
Estruturas de dados em C nunca foi o meu forte e poucos conhecimentos tenho sobre elas... Conheço os nomes e tal, mas pouco entendo de cada uma. O que sempre usei foi listas ligadas e pronto...
O que eu preciso agora é de ter uma estrutura de dados indicada para fichas de clientes onde o cliente tem Nome (óbvio) e NIF pelo menos, entre outros. Certamente terá outras coisas, mas estes são os dados falados no enunciado do trabalho e são importantes no sentido que para procurar um cliente estes têm de ser usados.
O meu pouco conhecimento em estruturas de dados aponta-me para hash maps, mas será o mais indicado?
Se o é, o que é que pode ser o par chave/valor? E o que é que representa a hash? Não pode ser simplesmente o NIF visto ser um número diferente para cada cliente? Apesar de eu não saber bem o que significa a hash no contexto de hash maps e/ou como se usa ou como faço para procurar determinado cliente.
Agradecia ajuda nisto o mais rápido possível visto ter que entregar as estruturas de dados e funções de manutenção ate amanhã a meia noite e ainda não comecei. Óbvio que o mais certo é ficar a meio, mas tenho de tentar e pelo menos entregar o máximo que conseguir...
Concordo, se o NIF é único podes usá-lo como chave.
Quanto a ser o mais indicado. Eu diria que sim, visto que é irrelevante manter uma ordem entre os clientes (penso eu, pelo menos não me parece fazer sentido).
Pois, mas como o faço? É que eu já não tenho muito tempo para andar a estudar e a perceber tudo ao pormenor... E pelo que vi, não estou a ver como ter um hash map dinamico (n tem logica especificar o numerox max de clientes) onde o nif seja a chave e como é que uso essa chave para aceder ao resto do perfil do cliente.
Alguns exemplos básicos dava imenso jeito...
Penso que vais precisar de ter os dados indexados pelo NIF e pelo nome, não?
Eu usaria um hash map, que me permitiria aceder aos elementos pelo NIF, e uma árvore binária, para poder aceder aos elementos pelo nome (pois aqui a ordem deverá ser importante).
Não sei exactamente que tipo de hash map estás a pensar em implementar, mas penso que a melhor opção é usares chaining addressing, que tem uma capacidade ilimitada, mesmo que nunca alteres o tamanho da tabela. Mesmo assim, quando um hash map começa a ficar cheio, é aconselhável alocar uma nova tabela (com maior tamanho, por exemplo, o dobro), e passar para lá os elementos. Apesar desta operação demorar bastante tempo, raramente será realizada (a menos que pouco alteres o tamanho da tabela quando a aumentas).
Como é que eu uso um hash map e um árvore binária ao mesmo tempo para indexar os mesmo dados?
E uma árvore binária para os nomes? Não estou a ver como fazê-la... Que nomes é que ponho do lado direito e que nomes ponho do lado esquerdo?
O problema é mesmo esse, eu não faço ideia dos "tipos" de hash map que existem e muito menos a melhor opção...
No hash map tens uma referência para um bloco de dados, e na árvore tens outra referência para os mesmos dados.
Árvore binária de procura (e de preferência balanceada).
Vê o artigo de tabelas de hash da wikipedia. Penso que dá para ter uma ideia das coisas.
Eu já li a wikipedia e montes de outros sites e documentos, o problema é mesmo eu entender isto em pouco tempo. Não gosto, nem consigo trabalhar sobre pressão... Já não tenho muito tempo, eu gosto de fazer as coisas com calma e entende-las como deve ser e neste momento não tenho tempo para isso, mas sem as entender como é que vou fazer o que quer que seja?
Relativamente à árvore binária de procura, eu sempre fiz isso com inteiros, não faço ideia como fazer para nomes.
A única coisa que muda é a função de comparação. Neste caso tens de usar o strcmp.
Mas isso não é demasiado pesado para estar sempre a comprar strings?
A menos que estejas sempre a comparar um string tipo "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab" com a string "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", não vai ser assim tão pesado... Comparar "joão" com "manuel" resume-se a comparar um byte.
Os hash map, ou pões a colisões todas numa lista (ficando todos os elementos associados àquela posição), ou procuras uma nova posição para a colisão (que pode resultar numa nova colisão...). Penso que normalmente a solução usada é a da lista, e parece-me que é a que tem melhor desempenho na generalidade dos casos.
Dá para me dares um exemplo dessa tabela de hash (chaining address) usando um numero (NIF) como chave? Eu estou a ver se trato da árvore binária para procurar por nome. O meu colega de grupo está a fazer isso da hash mas tiver o código dele e acho que tem algumas coisas mal e/ou esta a confundir alguma coisa e gostava de ter um exemplo pa perceber melhor e tentar melhorar/adaptar o código dele...
Dado o teu pouco tempo, acho melhor implementares apenas uma das estruturas de dados: hash map ou uma árvore binária de pesquisa (balanceada).
Eu sugiro usares 2 hash maps porque acho que precisas de menos tempo para os perceber e implementar do que uma árvore balanceada. Num fazes o hash dos nomes e no outro dos NIFs.
Podes ver aqui uma página do manual de preparação do estágio das olimpiadas de informática sobre hash tables. É mais implementação do que explicação... mas deve ajudar.
Nope, árvores balanceadas já eu percebo... hash maps é que não. Fazer uma árvore binária de procura para os nomes, faço eu num instante, agora o resto é que não...
Árvores binárias de procura deves perceber, só não devem é ser balanceadas... Essas dão um pouco mais de trabalho
Sim, mas balanceadas nem se quer penso nelas neste momento...
Já agr, as árvores têm q ser balanceadas porquê? Desculpem, mas ñ estou a atingir. A inserção deve ser feita por ordem, elas vão estar smp ordenadas...
Eu estou a fazer o mesmo trabalho que tu, acho eu. Estava a pensar em duas árvores, uma com os NIFs e outra com os caracteres. Qd o user evoca a inserção de um cliente, tens q inserir, por ordem, nas duas árvores.
Mas para os clientes até uma lista ligada serve. Como é para andar smp a pesquisar os meus colegas de curso q percebem mais q eu recomendaram-me a(s) árvore(s). Já estão feitas, mas até vou entregar nesta fase as listas ligadas e acabou, depois qd estiver tudo perfeitinho lá entrego as árvores.
Ter as árvores equilibradas não ter nada a ver com a ordem. Tem a ver com o facto de tentar manter a profundidade da árvore o mais baixo possível para que os itens sejam encontrados o mais depressa possível.
Peço desculpa por não ter dado conta.
Sem dúvida q realmente faz diferença.
E o tal exemplo de hashmap? Não podem ajudar?
Eu sei que existem muitos na net mas ainda não encontrei um decente... Decente no sentido de ser fácil de ler o código porque a maior parte das coisas as pessoas têm tendência a complicar, não sei porquê...