• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Nazgulled

Estrutura de dados indicada para ficha de cliente?

20 mensagens neste tópico

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...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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).

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?

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).

O problema é mesmo esse, eu não faço ideia dos "tipos" de hash map que existem e muito menos a melhor opção...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Como é que eu uso um hash map e um árvore binária ao mesmo tempo para indexar os mesmo dados?

No hash map tens uma referência para um bloco de dados, e na árvore tens outra referência para os mesmos 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?

Árvore binária de procura (e de preferência balanceada).

O problema é mesmo esse, eu não faço ideia dos "tipos" de hash map que existem e muito menos a melhor opção...

Vê o artigo de tabelas de hash da wikipedia. Penso que dá para ter uma ideia das coisas.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A única coisa que muda é a função de comparação. Neste caso tens de usar o strcmp. :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mas isso não é demasiado pesado para estar sempre a comprar strings?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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 :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sim, mas balanceadas nem se quer penso nelas neste momento... :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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ê...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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ê...

http://librcg.rcg-pt.net/hashmap_8c-source.html

A implementação deve estar um pouco mais complexa do que aquilo que precisas.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora