Métodos de Pesquisa

Prévia do material em texto

Estrutura de dadosEstrutura de dados
MMéétodos de Pesquisa todos de Pesquisa 
20132013
Prof Melo
Apresentação
• Técnico em Desenvolvimento de Sistemas - Ibratec, Recife-PE
• Bacharel em Sistemas de Informação – FIR, Recife-PE
• Especialista em Docência no Ensino Superior – Faculdade 
Maurício de Nassau, Recife-PE
• Mestre em Ciência da Computação – UFPE/CIN, Recife-PE
• Currículo Lattes http://lattes.cnpq.br/0759508594425296)
• Homepage https://sites.google.com/site/hildebertomelo/
Disciplinas Lecionadas
• Desenvolvimento de Aplicações Desktop
• Programação Orientada a Objetos
• Estrutura de Dados
• Tecnologia da Informação & Sociedade
• Sistemas Operacionais
• Sistemas Distribuídos
• Introdução a Informática
• Lógica de Programação
• Informática Aplicada a Saúde
• Banco de Dados
• Projeto de Banco de Dados
• Análise de Projetos Orientado a Objetos
• Programação Cliente Servidor
• Linguagens de Programação: C, C#, Pascal, PHP, ASP, Delphi, Java, JavaScript
• Programação WEB
Conteúdo
• Definição
• Arquivos
• Registros
• Chave primária
• Métodos de pesquisa
– Seqüencial
– Seqüencial ordenado
– Seqüencial com ordenação
– Binária
– Relativa
– Hashing
Métodos de Pesquisa
• Algorítimos para manipulação de 
conjuntos de dados
•Métodos para pesquisa e localização 
de um registro ou conjunto de 
registro dentro de um arquivo ou 
tabela
Arquivo ou Tabelas
• Coleção de entradas ou registros, cada 
uma delas formada por um conjunto de 
campos ou atributos
• Armazenamento de informações sobre 
objetos de um mesmo tipo
Número Nome Data Nasc Salário
10130 Jose 25 07 50 1200
10850 Paulo 23 12 51 11000
12700 Pedro 10 06 53 7000
...
11600 Edison 05 03 47 9800
Registro ou Entrada
• Coleção de atributos ou campos que 
formam uma entrada em um arquivo
• Conjunto de informações sobre um 
objeto armazenado em uma coleção
Chave Primária
• Campo ou conjunto de campos que 
identificam unicamente cada uma das 
entradas de uma tabela
• Características:
–O valor da chave primária não pode ser nulo
–Não pode existir mais de um registro ou 
entrada com o mesmo valor para a chave 
primária
Pesquisa Sequencial
• Método mais simples de pesquisa e 
localização de uma entrada em uma tabela
• Varredura seqüencial da tabela até localizar 
o registro cujo atributo chave é o 
procurado, ou encontrar o fim da tabela
• Características:
– Baixo desempenho
– Fácil implementação
Pesquisa Sequencial (Comparações)
• Número de Comparações:
Pior caso: NC = n
Melhor caso: NC = 1
Caso médio: NC = (n + 1) / 2, onde n é o 
número de registros da 
tabela.
Sem sucesso: NC = n + 1
Pesquisa Sequencial (Algoritmo)
algoritmo pesquisa-seqüêncial
defina t: tabela; // Tabela onde será
feita a pesquisa
n, // Número de entradas 
da tabela
arg: chave; // Valor a ser 
localizado
declare i, // Índice para 
percorrer a tabela
r: Numérico // Posição onde se 
localiza a entrada
// procurada na tabela.
r = 0 // r = 0 implica não 
encontrado
repita para i = 1 até n
se t[i].chave = arg então
r = i
Pesquisa Sequencial em Tabelas Ordenadas
• O atributo chave procurado na tabela 
deverá está ordenado.
• Acelera a pesquisa para valores não 
existentes, pois permite comparação >= 
para finalizar a pesquisa na tabela.
• Características:
– Baixo desempenho
– Fácil implementação
– Alta dependência dos dados armazenados 
Pesquisa Sequencial em Tabelas Ordenadas
algoritmo pesquisa-seqüencial-ordenado
defina t: tabela; // Tabela onde será feita a 
pesquisa
n, // Número de entradas da tabela
arg: chave; // Valor a ser localizado
declare i, // Índice para percorrer a tabela
r: numérico // Posição onde se localiza a 
entrada
// procurada na tabela. 
r = 0 // r = 0 implica não encontrado
repita para i = 1 até n
se t[i].chave => arg então
se t[i] = arg então
r = i
fim-se
interrompa
fim-se
fim-repita
fim-algoritmo
Pesquisa Seqüencial com Ordenação das Entradas
• A medida em que se pesquisa os registros 
são ordenados, colocando-se os mais 
utilizados no início da tabela.
• Características:
–Baixo desempenho
– Fácil implementação
–Maior custo de processamento 
Pesquisa Seqüencial com Ordenação das Entradas
algoritmo Pesquisa-Sequencial-Auto-Ordenada
defina t: Ponteiro; // Ponteiro para a primeira entrada da 
tabela (Topo)
arg: chave; // Valor a ser localizado
declare i, // Índice para percorrer a tabela
a, // Índice anterior ao nó pesquisado
r: Numérico // Posição onde se localiza a entrada 
procurada na tabela
r = nil // r = nil implica não encontrado
i = t
repita enquanto (i <> nil) e (r = nil)
se i^.chave => arg então
r = i
se i <> t então
a^.prox = i^.prox
i^.prox = t
t = i
fim-se 
senão
a = i
i = i^.prox
fim-se
fim-repita
Pesquisa Binária
• Método pesquisa aplicado a tabelas ordenadas
• A pesquisa é feita através comparação com o 
registro médio da tabela e restringindo 
sucessivamente o intervalo da mesma
• Características:
– Alta dependência dos dados
– Melhor desempenho
– Implementação mais complexa
Pesquisa Binária (Comparações)
• Número de Comparações:
Melhor caso: NC = 1
Pior caso: NC = n
Caso médio: NC = (log 2 n) + 1, onde n é o 
número de registros da tabela.
Sem sucesso: NC = n + 1
Pesquisa Binária (Algoritmo)
algoritmo pesauisa-binária
defina t: tabela; // Tabela onde será feita a pesquisa
n, // Número de registros da tabela
arg: chave; // Valor a ser localizado
declare i, // Índice início do intervalo
f, // Índice fim do intervalo
p, // Índice da posição atual
r: numérico // Posição onde se localiza a entrada
// procurada na tabela.
r = 0 // r = 0 implica não encontrado
i = 1
f = n
repita enquanto (i <= f) e (r = 0)
p = (i + f) div 2 // Calcula ponto médio do intervalo
se t[p].chave = arg então
r = p
senão se t[p].chave < arg então
i = p + 1
senão
f = p – 1
fim-se
fim-repita
fim-algoritmo
Pesquisa Relativa
• Método de armazenamento e pesquisa em tabelas.
• Aplicado a tabelas cuja chave primária e de pesquisa são:
– Numérica
– Não esparsa
• A organização física dos registros segue o valor da chave de 
cada registro, ou seja, a chave 1 está na posição 1, a 2 na 
posição 2, e a N na n-ésima posição;
• Necessidade de se criar um campo extra para indicar se a 
entrada é válida ou não;
• Características:
– Alta dependência dos dados
– Alta dependência da organização do arquivo
– Perda de espaço em memória
– Melhor desempenho na pesquisa
Pesquisa Relativa (Continuação)
• Cada registro é colocado na posição 
relativa da chave no arquivo:
CoR Descrição Flag
1 Azul 1
2 Amarelo 1
0
4 Verde 1
5 Vermelho 1
0
0
8 Branco 1
… … …
Pesquisa Relativa (Comparações)
• Número de Comparações:
Melhor caso: NC = 1
Pior caso: NC = 1
Caso médio: NC = 1
Sem sucesso:NC = 1
Pesquisa com Cálculo de Endereço (HASH)
• Método de armazenamento e pesquisa em tabelas.
• Consiste em gerar uma função, hashing, que transforma uma chave 
em um número inteiro e não espaço em um determinado 
intervalo.
• O armazenamento é feito calculando-se a posição física do registro 
através da função hashing e gravando o registro na posição 
indicada.
• Caso exista colisão deverá existir um procedimento especial para 
tratamento da mesma.
• Características:
– Menor dependência dos dados;
– Alto desempenho na pesquisa;
– Perda de espaço em memória; 
– Maior complexidade de implementação;
– Necessidade de controle de colisões;
Função Hashing
• Função que mapeia uma chave em um 
inteiro dentro do intervalo [0, M-1], onde 
M é o tamanho máximo da tabela.
• Ex.: f(chave) = resto(chave, M)
onde M deverá ser um número 
primo
Função Hashing para chaves não numéricas
• Pode-se utilizar o valor ASCII de cada caractere da 
chave para gerar um número inteiro dentro do 
intervalo [0, M-1], onde M é o tamanho máximo da 
tabela.• Ex.: f(chave) = soma=0
repita para i=1 até tamanho(chave)
soma=soma + (ORD(chave[i]) * i)
fim-repita 
resultado=resto(soma, M)
Pesquisa Hashing (Continuação)
• Cada registro é colocado na posição 
relativa do resultado da função 
hashing aplicada a chave:
CPF Nome Flag Prox
1111111111
1
Hildeberto 1
2222222222
2
Melo 1
0
3333333333
3
Jose 1
4444444444
4
Carlos 1
0
f(111111111)=0
f(222222222)=1
f(333333333)=3
f(444444444)=4
f(212121212)=6
Pesquisa Hashing (Algoritmo de leitura)
refinamento Hashing(chave)
resultado = resto(chave, 7)
fim-refinamento
refinamento Trata-Registro(pos)
se pos<=0 então // Fim da lista de colisões
“Não encontrado”
senão se T[Pos].chave = arg e T[Pos].flag = 1 então
“Achou”
senão
Trata-Registro(T[pos].prox)
fim-se
fim-refinamento
algoritmo Le-Hashing
defina T: Tabela // Tabela onde será feita a pesquisa
arg: chave // Valor a ser localizado
Trata-Registro(Hashing(arg))
fim-algoritmo
Pesquisa Hashing (Algoritmo de gravação)
refinamento Hashing(chave)
resultado = Resto(chave, 7)
fim-refinamento
refinamento Trata-Registro(pos)
se pos<=0 então // Fim da lista de colisões
Grava-Colisão()
senão se T[Pos].chave = arg e T[Pos].flag = 1 então
“Duplicado”
senão
Trata-Registro(T[pos].prox)
fim-se
fim-refinamento
algoritmo Grava-Hashing
defina T: tabela // Tabela onde será feita a pesquisa
arg: chave // Valor a ser gravado
declare pos: numérico // Posição onde será gravado o registro
pos = Hashing(arg)
repita enquanto T.tamanho() < pos
Grave-Vazio()
fim-repita
se T[Pos].flag = 0 então 
Grava-Registro()
senão
Trata-Registro(pos)
fim-se
fim-algoritmo
Perguntas...
Bibliografia
• Livro(s) Texto(s):
• PREISS, Bruno R. Estrutura de Dados e 
Algoritmos. Rio de Janeiro: Campus, 2001.
• PEREIRA, Silvio L. Estruturas de dados 
fundamentais. São Paulo: Érica, 2000.
• AZEREDO, Paulo A. Métodos de 
Classificação de Dados e Análise de suas 
Complexidades. Rio de Janeiro: Campus, 
1995.
• http://www.nuperc.unifacs.br/
Bibliografia
• Livros de referencia:
• WEISS, M. A. Data structures and algorithm 
analysis in C++. California: Benjamin/Cummings, 
1999.
• SEDGEWICK, R. Algorithms in C++: Fundamentals, 
data structures, sorting, searching. New York: 
Addison-Wesley, 2001.
• TANENBAUM, Aaron; LANGSAM, Y. & 
AUGENSTEIN, M. Estruturas de Dados usando C. 
São Paulo: Makron Books, 1995.
• LAFORE, R. Aprenda em 24 horas estrutura de 
dados e algoritmo. Rio de Janeiro: Campus, 1999.
• MORAES, Celso R. Estruturas de Dados e 
Algoritmos. São Paulo: Berkeley Brasil, 2001.