Estruturas de Dados - Busca - Parte 1 (Dibio)

Prévia do material em texto

dibio@unb.br
Assuntos 
● Pesquisa/Busca
● Algoritmos e TADs para Pesquisa
● Dicionário 
● Pesquisa Sequencial
● Pesquisa Binária
● Exemplos com armazenamento simples (vetor)
● Transformações de chave (Hashing), 
espalhamento
– Funções de transformação simples
– Exemplo em C
dibio@unb.br
Pesquisa/Busca
● Como recuperar informação a partir de uma 
grande quantidade de dados armazenada?
● Informação dividida em registros 
● Cada registro possui uma chave a ser usada para 
pesquisa (i.e. elemento, dado característico, rótulo)
● Objetivo da pesquisa: encontrar uma, ou mais, 
ocorrências de registros com chaves iguais à usada 
na pesquisa.
● Pode­se obter sucesso, ou não, para essas 
ocorrências.
dibio@unb.br
Conjuntos de registros
dibio@unb.br
Como pesquisar, buscar um 
registro, depende da aplicação
● Considerando:
– Quantidade de dados 
– Arquivo sujeito a inserções e retiradas frequentes
● Se conteúdo do arquivo for estável, considera­se 
minimizar o tempo de pesquisa sem a preocupação 
de nova estruturação do arquivo
dibio@unb.br
Algoritmos de Pesquisa como 
Tipos Abstratos de Dados (TADs)
dibio@unb.br
Dicionário
dibio@unb.br
Pesquisa em Dicionário 
organizada por acesso direto a 
uma tabela
dibio@unb.br
Pesquisa Sequencial
● Método de pesquisa mais simples e direto, onde a 
partir do primeiro registro todos os elementos são 
pesquisados sequencialmente até encontrar, ou 
não, a chave procurada.
dibio@unb.br
Exemplo com armazenamento 
feito por vetores
dibio@unb.br
Operações inicializa e pesquisa do 
TAD
dibio@unb.br
TAD cont.
dibio@unb.br
Considerações Pesquisa 
Sequencial
● Pesquisa retorna o índice do registro que contém a 
chave x;
● Caso não a encontre, retorna 0 (zero);
● A implementação não suporta mais de um registro 
com a mesma chave;
● Para aplicações com mais de um registro com a 
mesma chave faz­se necessário incluir um 
argumento a mais na função Pesquisa, que contém 
o índice a partir do qual pesquisar;
dibio@unb.br
TAD cont. (com índice)
dibio@unb.br
Considerações Pesquisa 
Sequencial
dibio@unb.br
Considerações Pesquisa 
Sequencial
dibio@unb.br
Pesquisa Binária
dibio@unb.br
Exemplo de uma Pesquisa Binária
dibio@unb.br
Exemplo Pesquisa Binária
Indice Binaria(TipoChave x, Tabela *T) {
 
 Indice i, Esq, Dir; 
 if (T->n == 0) return 0; 
 else { 
 Esq = 1; 
 Dir = T->n; 
 do { 
 i = (Esq + Dir) / 2; 
 if (x > T->Item[i].Chave) 
 Esq = i + 1; 
 else 
 Dir = i - 1; 
 } 
 while ( (x != T->Item[i].Chave) && 
 (Esq <= Dir) );
if (x == T->Item[i].Chave) 
 return i; 
 else 
 return 0; 
 } 
} 
dibio@unb.br
Considerações Pesquisa Binária
dibio@unb.br
Transformações de chave 
(Hashing), espalhamento
dibio@unb.br
Transformações de chave 
(Hashing), espalhamento
dibio@unb.br
Função de transformação 
Hashing)
dibio@unb.br
Transformações de chave 
(Hashing), espalhamento
dibio@unb.br
Transformações de chave 
(Hashing), espalhamento
dibio@unb.br
Transformações de chave 
(Hashing), espalhamento
dibio@unb.br
Funções de transformação
dibio@unb.br
Funções de transformação 
(método mais utilizado)
dibio@unb.br
Funções de transformação 
(método mais utilizado)
dibio@unb.br
Funções de transformação para 
chaves não­numéricas
dibio@unb.br
Funções de transformação para 
chaves não­numéricas (porque 
usar pesos?)
dibio@unb.br
Exemplo em linguagem C
dibio@unb.br
Exemplo em linguagem C (função 
de transformação)
dibio@unb.br
E as colisões?
● Quando mais de um registro estiver relacionado à 
mesma chave?
dibio@unb.br
Lidar com colisões usando listas 
encadeadas (próxima aula)
dibio@unb.br
Referências
●   Celes, W.; Cerqueira, R. & Rangel, J.L. 
  Introducão a Estruturas de Dados, Editora 
  Campus (Elsevier), RJ, 2004.
●   Cormen, T.; Leiserson, C.  & Rivest, R. 
  Algoritmos: teoria e prática, Campus Editora, RJ, 
  2002.
●   Tenenbaum, A.; Langsam, Y. & Augenstein, M. 
  Estruturas de Dados usando C, Makron Books, 
  RJ, 1995.
● Ziviani, N. Projetos de Algoritmos com 
Implementações em Pascal e C, Cengage 
Learning, SP, 2004.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35