Recursividade e Tabelas Hash em Estrutura de Dados

Prévia do material em texto

Estrutura de Dados 1 
UNIP - Ciência da Computação e Sistemas de Informação 
 
 
 
Estrutura de Dados 
 
AULA 10 
Recursividade e Tabelas Hash 
Estrutura de Dados 2 
Recursividade 
• Ao atingir o topo da escada, a tarefa de a subir está terminada; 
– Enquanto o topo não for atingido; 
• Avançar um degrau; 
• e retomar a tarefa de subir as escadas, mas agora, tendo já 
avançado um dos degraus, a dimensão do problema aparece 
mais reduzida. 
• Uma função que é dita recursiva é aquela que invoca ela mesma. 
• Porém é preciso um cuidado especial para não cairmos em um 
looping infinito. 
• Geralmente, para que uma função não fique invocando ela mesma 
indefinidamente, devemos definir, na função, testes condicionais 
sobre o parâmetro para saber onde devemos parar de invocar a 
função. 
• Recursividade brinda soluções simples e elegantes, evitando 
estruturas de repetição. 
 
Estrutura de Dados 3 
Recursividade 
• Fatorial 
– 0! = 1 (por convenção) 
– 1! = 1 = 1 * 0! 
– 2! = 2 * 1 = 2 * 1! = 2 * 1 = 2 
– 3! = 3 * 2 * 1 = 3 * 2! = 3 * 2 = 6 
– 4! = 4 * 3 * 2 * 1 = 4 * 3! = 4 * 6 = 24 
– ... 
– n! = n * (n-1) * (n-2) * ... * 1 = n * (n - 1)! 
 
• Podemos daqui concluir que: 
• Caso base: 0! = 1 ; caso em que o valor é conhecido por definição 
ou convenção 
• Caso geral n! = n * (n-1)! ; caso que recorre à própria função que se 
pretende resolver 
Estrutura de Dados 4 
Recursividade 
public class Fatorial{ 
 public static void main (String args []){ 
 Scanner ler = new Scanner(System.in); 
 int n; 
 System.out.printf("Digite um inteiro positivo: "); 
 n = ler.nextInt (); 
 System.out.printf("%d! = %d\n", n, fatorial(n)); 
 System.exit(0); 
}//fim main 
 
public static int fatorial(int n){ 
 if(n == 1) 
 return 1; 
 else 
 return (n * fatorial(n-1)); 
}//fim método fatorial 
}//fim classe 
Estrutura de Dados 5 
Tabelas Hash 
• Uma tabela hash é uma estrutura que permite associar 
uma chave a um valor e, posteriormente, ter acesso ao 
valor a partir de sua chave associada. A chave é 
transformada por uma função em uma posição na tabela; 
usando sempre essa transformação, a localização de 
chaves na tabela é realizada rapidamente. 
Fonte: http://www.dca.fee.unicamp.br/cursos/PooJava/collections/h_hasht.html 
Estrutura de Dados 6 
Tabelas Hash 
• Hashing é uma tabela composta por um vetor com M 
posições e cada posição representa um endereço onde 
os elementos a serem armazenado nele possuem um 
valor chave que é utilizado para calcular o endereço na 
tabela onde deverão ser alocados. 
• Para criação da função hashing é o método da divisão 
onde uma chave X é mapeada em M endereços da tabela 
hashing calculando o resto da divisão de X por M, ou 
seja: h(x) = x mod m. 
 
Fonte: http://www.manfred.com.br/index.php/bsi/estrutura-de-dados-i/146-aula-
14-tabela-hash-em-java 
Estrutura de Dados 7 
Tabelas Hash 
 h(x) = x mod m. 
 
• Exemplo: 
 
• Em uma tabela hashing de tamanho 10 e a chave inserida é 
100 será armazenado na posição 0. 
 
• Ao aplicar a função de hashing sobre um conjunto de chaves, 
duas ou mais chaves podem ser mapeadas para o mesmo 
endereço, esta situação é chamada de colisão, para resolver 
este problema é utilizado o encadeamento dos endereços da 
tabela hashing ou se usa de outra alternativa, como a do 
endereçamento aberto. 
Estrutura de Dados 8 
Tabelas Hash 
• Exemplo de codificação em Java de tabelas Hash 
pode ser encontrado em: 
 
Fonte: http://www.manfred.com.br/index.php/bsi/estrutura-de-dados-i/146-aula-
14-tabela-hash-em-java