tabela de dispersao
Tabelas de dispersão fechada
Pesquisas em vector
• pesquisa linear
• pesquisa dicotómica
• mais rápida do que a pesquisa linear mas, para ser utilizada, o vector tem de estar ordenado
Exercício: Faça um programa para ler de um ficheiro nomes de pilotos (considerando que o número do carro é determinado pela ordem de leitura) e, de seguida, permita indicar de forma rápida o número do carro de determinado piloto. Se o nome do piloto não existir, deve apresentar uma mensagem referindo tal facto
2004/05
AED - DI / FCT / UNL
2
Tabelas de dispersão - motivação uma generalização de um vector que, em determinadas condições, permite aceder rapidamente à informação, ainda que esta não esteja ordenada
inserção
• numa inserção, a posição onde se insere o elemento é função do valor do elemento, independentemente da ordem de inserção
• outras operações:
• pesquisa
•
2004/05
remoção
AED - DI / FCT / UNL
3
Função de dispersão e colisão
• função de dispersão: converte a chave genérica do elemento num índice da tabela (a entrada) entrada chave
(elemento)
função de dispersão ...
tabela
• se a função de dispersão indicar a mesma entrada para duas chaves distintas, então surge um problema de colisão
2004/05
AED - DI / FCT / UNL
4
Função de dispersão
•
o desempenho da tabela de dispersão depende da capacidade da função de dispersão distribuir uniformemente as chaves
•
características desejáveis para a função de dispersão:
•
eficiente
•
distribuição uniforme dos elementos pela tabela
• princípios
• função simples
• a dimensão da tabela deve ser um número primo
2004/05
AED - DI / FCT / UNL
5
Resolução de colisões
• dispersão aberta
• cada posição da tabela contem um apontador para uma lista de chaves com a mesma entrada
•
dispersão fechada
• existem sempre posições livres
• cada posição da tabela contem uma só chave. Se o