AULA_2_Revisao

Prévia do material em texto

Aula 2 – Revisão 
Algoritmo e Estrutura de Dados III 
SIF 130 
Vanessa Souza 
Universidade Federal de Itajubá – Instituto de Matemática e Computação 
Tipo Abstrato de Dados (TAD) 
 Um tipo abstrato de dados é formado por um 
conjunto de valores e por uma série de operações 
que podem ser aplicadas sobre esses valores. 
 
 Um TAD estabelece o conceito de tipo de dado 
divorciado da sua representação (modelo 
matemático). 
 
 Na representação de um TAD, emprega-se uma 
estrutura de dados. 
Tipo Abstrato de Dados (TAD) 
 Exemplo : considere uma aplicação que utilize uma 
lista de inteiros. 
 Conjunto de valores : LISTA de inteiros 
 Operações: 
 Crie a lista vazia 
 Obtenha o primeiro elemento da lista; se a lista estiver 
vazia, então retorne nulo 
 Insira um elemento na lista 
 Exclua um elemento na lista 
Estruturas de Dados 
 Meio para armazenar e organizar dados na memória 
com o objetivo de facilitar o acesso e as 
modificações. 
 
 As estruturas diferem umas das outras pela 
disposição ou manipulação de seus dados. 
 
 Podem ser estáticas ou dinâmicas 
Estruturas de Dados– Vetor Estático 
 A forma mais simples de uma estrutura de dados é 
denominada Vetor, onde os elementos são 
armazenados na memória de forma indexada e 
contínua. 
Vetor estático 
Estruturas de Dados– Vetor Estático 
 A forma mais simples de uma estrutura de dados é 
denominada Vetor, onde os elementos são 
armazenados na memória de forma indexada e 
contínua. 
Vetor estático 
Posições contínuas de memória!! 
Seu tamanho e localização na memória não se alteram durante a execução 
Estruturas de Dados– Vetor Estático 
 A referência a uma posição de um vetor indica o 
cálculo de uma posição de memória a partir do início 
do vetor 
vet[3] = vet + 3*sizeof(int) 
vet 
Estruturas de Dados– Vetor Estático 
 A referência a uma posição de um vetor indica o 
cálculo de uma posição de memória a partir do início 
do vetor 
vet[3] = vet + 3*sizeof(int) 
vet 
Estruturas de Dados– Matriz 
 E uma matriz?? 
Estruturas de Dados– Matriz Estática 
 E uma matriz?? 
mat[l][c]= mat + (l*tamCol + coluna)*sizeof(int) 
mat[1][0]= mat + (1*2 + 0)*sizeof(int) 
mat 
Estruturas de Dados 
 Vetor X TAD 
 Matriz X TAD 
Estruturas de Dados 
 Vetor X TAD 
 Criar vetor vazio 
 Instanciar elementos no vetor 
 Acessar elementos no vetor 
Estruturas de Dados 
 Estruturas de dados estáticas são mais simples e 
fáceis de usar. 
 
 Mas para a maioria das aplicações não se sabe a 
priori o número de elementos necessários na 
resolução do problema. 
 
 Solução : ESTRUTURAS DE DADOS DINÂMICAS 
 a quantidade de elementos pode ser alterada sempre que 
necessário. 
Estruturas de Dados Dinâmicas 
 Estruturas de dados encadeadas são mais 
convenientes para estes tipos de problemas, pois: 
 Evitam-se as movimentações de dados nas operações de 
inclusão e exclusão de dados. 
 O esforço computacional destas operações é, praticamente, 
constante. 
Estruturas de Dados Dinâmicas 
 A alocação dinâmica de memória é a base 
das estruturas dinâmicas de dados. 
 
 Uma estrutura dinâmica de dados é, tipicamente um 
conjunto de nós (nodes) ligados por um conjunto de 
arcos direcionados (directed edge) entre esses nós. 
 Os nós contêm a informação e os arcos são ligações 
funcionais entre os nós que permitem percorrer a estrutura 
de dados. 
Estruturas de Dados Dinâmicas 
 Assim, o elemento da estrutura de dados deve conter 
as informações que serão armazenadas por ela e o(s) 
ponteiro(s) representando os arcos. 
 Exemplo : Lista de Vinhos 
Estruturas de Dados Dinâmicas 
 Assim, o elemento da estrutura de dados deve conter 
as informações que serão armazenadas por ela e o(s) 
ponteiro(s) representando os arcos. 
 Exemplo : Lista de Vinhos 
Codigo 
Safra prox 
Tipo 
Estruturas de Dados Dinâmicas 
 As operações sobre um conjunto dinâmico podem ser 
agrupadas em duas categorias: 
 Consulta 
 Retorna informações sobre o conjunto 
 procuraElemento(S, x) 
 MenorElemento(S) 
 MaiorElemento(S) 
 Vazio(S) 
 Operações de Modificação 
 Alteram o conjunto 
 insereElemento(S,x) 
 removeElemento(S,x) 
 alteraElemento(S,x,A, k) 
Estruturas de Dados Dinâmicas 
 As operações sobre um conjunto dinâmico podem ser 
agrupadas em duas categorias: 
 Consulta 
 Retorna informações sobre o conjunto 
 procuraCodigoVinho(Lista, codigo) 
 procuraSafraVinho(Lista, safra) 
 VinhoSafraMaisAntiga(Lista) 
 VinhoSafraMaisNova(Lista) 
 Vazio(Lista) 
 Operações de Modificação 
 Alteram o conjunto 
 insereVinho(Lista, vinho) 
 removeVinho(Lista, codigo) 
 alteraVinho(Lista, codigo, atributoAlterado, novoValor) 
Estruturas de Dados Dinâmicas 
Estruturas 
de dados 
Elementares 
Lista 
Fila 
Pilha 
Árvore 
binária 
Avançadas 
Árvores 
balanceadas 
Hash 
Grafos 
Estruturas de Dados Dinâmicas 
O que diferencia uma estrutura da outra? 
Estruturas 
de dados 
Elementares 
Lista 
Fila 
Pilha 
Árvore 
binária 
Avançadas 
Árvores 
balanceadas 
Hash 
Grafos 
Estruturas de Dados Dinâmicas 
 
 O QUE VOCÊ PRECISA GUARDAR? 
 
 COMO VOCÊ PRECISA GUARDAR? 
 
 O QUE VOCÊ PRECISA FAZER COM ESSES DADOS? 
Estruturas de Dados Dinâmicas 
 O QUE VOCÊ PRECISA GUARDAR? 
 Dado 
 
 COMO VOCÊ PRECISA GUARDAR? 
 Estrutura de Dados 
 
 O QUE VOCÊ PRECISA FAZER COM ESSES DADOS? 
 Operações 
Estruturas 
de dados 
Elementares 
Lista 
Fila 
Pilha 
Árvore 
binária 
Avançadas 
Árvores 
balanceadas 
Hash 
Grafos 
Estruturas de Dados Dinâmicas 
LISTA 
Listas 
 Estrutura de dados em que os objetos estão organizados 
em uma ordem linear. 
 
 Diferente de um vetor, a ordem linear é determinada por 
um ponteiro em cada objeto. 
 
 Operações: 
 Inserir 
 Onde? 
 Remover 
 Onde? 
 Consultar 
 Elemento, maior, menor, vazia 
Listas 
Qual o endereço de memória do elemento 4? 
Listas 
prox endereço de memória 
prox 
Listas 
 Exemplo: 
 Representar o conjunto dinâmico {3, 4, 5, 6} numa lista 
ligada ordenada de forma crescente. 
Listas 
 Exemplo: 
 Representar o conjunto dinâmico {3, 4, 5, 6} numa lista 
ligada ordenada de forma crescente. 
3 
Listas 
 Exemplo: 
 Representar o conjunto dinâmico {3, 4, 5, 6} numa lista 
ligada ordenada de forma crescente. 
3 4 
Listas 
 Exemplo: 
 Representar o conjunto dinâmico {3, 4, 5, 6} numa lista 
ligada ordenada de forma crescente. 
3 4 5 
Listas 
 Exemplo: 
 Representar o conjunto dinâmico {3, 4, 5, 6} numa lista 
ligada ordenada de forma crescente. 
3 4 5 6 
Listas 
 Exemplo: 
 Representar o conjunto dinâmico {3, 4, 5, 6} numa lista 
ligada ordenada de forma crescente. 
3 4 5 6 
Início da Lista Fim da Lista 
Listas 
 Exemplo: 
 Inserir o elemento 1 à lista criada 
3 4 5 6 
Início da Lista Fim da Lista 
Listas 
 Exemplo: 
 Inserir o elemento 1 à lista criada 
3 4 5 6 
Início da Lista Fim da Lista 
Instanciar o objeto 1 
1 
Listas 
 Exemplo: 
 Inserir o elemento 1 à lista criada 
3 4 5 6 
Início da Lista Fim da Lista 
Encontrar o local correto (primeiro 
número maior que 1) 
Listas 
 Exemplo: 
 Inserir o elemento 1 à lista criada 
3 4 5 6 
Início da Lista Fim da Lista 
1 
Movimentar os ponteiros e, nesse caso, o 
início da lista passa a ser o elemento 1. 
Listas 
 Exemplo: 
 Inserir o elemento8 à lista criada 
3 4 5 6 
Início da Lista Fim da Lista 
1 
Listas 
 Exemplo: 
 Inserir o elemento 8 à lista criada 
3 4 5 6 
Início da Lista Fim da Lista 
1 8 
Movimentar os ponteiros e, nesse caso, o 
fim da lista passa a ser o elemento 8. 
Listas 
 Exemplo: 
 Inserir o elemento 7 à lista criada 
3 4 5 6 
Início da Lista Fim da Lista 
1 8 
Listas 
 Exemplo: 
 Inserir o elemento 7 à lista criada 
3 4 5 6 
Início da Lista Fim da Lista 
1 8 
Instanciar o objeto 7 e encontrar o local correto para inserir 
7 
Listas 
 Exemplo: 
 Inserir o elemento 7 à lista criada 
3 4 5 6 
Início da Lista Fim da Lista 
1 8 
7 Movimentar os ponteiros 
Listas 
 Sentinelas 
 Objeto fictício que nos permite especificar condições 
limites. 
3 4 5 6 
Início da Lista 
Fim da Lista 
1 8 
7 
Cabeça 
Listas 
 Sentinelas 
 Objeto fictício que nos permite especificar condições 
limites. 
3 4 5 6 
Início da Lista 
Fim da Lista 
1 8 
7 
Cabeça 
Com o "list head", os “casos especiais” não 
serão mais necessários!! 
Listas 
 Remover o elemento 4 da lista 
3 4 5 6 
Início da Lista 
Fim da Lista 
1 8 
7 
Cabeça 
Listas 
 Remover o elemento 4 da lista 
3 4 5 6 
Início da Lista 
Fim da Lista 
1 8 
7 
Cabeça 
Encontrar o elemento na lista 
Listas 
 Remover o elemento 4 da lista 
3 4 5 6 
Início da Lista 
Fim da Lista 
1 8 
7 
Cabeça 
Movimentar os ponteiros 
Listas 
 Remover o elemento 4 da lista 
3 5 6 
Início da Lista 
Fim da Lista 
1 8 
7 
Cabeça 
Liberar a memória 
Vetor x Lista 
 Vetor 
 existe uma ordenação física dos elementos (posições 
consecutivas de memória). 
 As movimentações de dados são necessárias para manter o 
vetor ordenado "sem buracos". 
 
 Lista encadeada 
 existe uma ordenação lógica dos elementos da lista (os 
elementos da lista ocupam posições quaisquer de memória, 
não necessariamente consecutivas). 
 É preciso indicar (por meio de um outro ponteiro) qual é o 
“primeiro” elemento da lista. 
Lista – Tipos especiais 
 Lista duplamente encadeada 
 
 
 
 
3 5 6 1 8 7 Cabeça 
contém não apenas ponteiros para o “próximo” 
elemento, como também ponteiros para o 
elemento “anterior”. 
 
List Tail 
Lista – Tipos Especiais 
 Lista circular 
3 5 6 1 8 7 Cabeça 
Numa lista circular, o ponteiro prox do “último” elemento 
aponta para o “primeiro” elemento da lista e o ponteiro ant 
do “primeiro” elemento aponta para o “último” elemento da 
lista. 
Estruturas 
de dados 
Elementares 
Lista 
Fila 
Pilha 
Árvore 
binária 
Avançadas 
Árvores 
balanceadas 
Hash 
Grafos 
Estruturas de Dados Dinâmicas 
Filas 
 Como as pilhas, as filas também têm um papel muito 
importante na Ciência da Computação. Aplicações envolvendo 
filas são muito comuns em situações nas quais é preciso 
“esperar sua vez” para ter acesso a algum serviço. 
 
 Exemplo: filas de processos para serem executados pelo 
sistema operacional. Normalmente, estes processos 
correspondem a tarefas que competem entre si por um 
determinado recurso, como tarefas esperando para serem 
impressas ou tarefas esperando por uma fatia de tempo do 
processador. 
 
 Em alguns casos, existe uma ordem de prioridade para 
atendimento aos elementos de uma fila (fila de prioridades). 
Filas 
 Estrutura de dados que implementa a norma primeiro a 
entrar, primeiro a sair ou FIFO (First In First Out). 
 
 Principais operações: 
 Verifica se a fila está vazia ou não 
 Inclui um novo elemento no fim da fila 
 Exclui o elemento do início da fila 
 Outras operações: 
 Excluir todos os elementos da fila 
 Retornar o primeiro elemento da fila, sem excluí-lo 
 Retornar o último elemento da fila, sem excluí-lo 
Listas 
 Exemplo: 
 Representar o conjunto dinâmico {3, 4, 5, 6} numa fila. 
Listas 
 Exemplo: 
 Representar o conjunto dinâmico {3, 4, 5, 6} numa fila. 
3 4 5 6 
Início da fila Fim da fila 
Listas 
 Exemplo: 
 Remover elemento da fila. 
3 4 5 6 
Início da fila Fim da fila 
Listas 
 Exemplo: 
 Remover elemento da fila. 
3 4 5 6 
Início da fila Fim da fila 
Sempre sai o primeiro da fila 
Listas 
 Exemplo: 
 Remover elemento da fila. 
4 5 6 
Início da fila Fim da fila 
Limpa memória 
Estruturas 
de dados 
Elementares 
Lista 
Fila 
Pilha 
Árvore 
binária 
Avançadas 
Árvores 
balanceadas 
Hash 
Grafos 
Estruturas de Dados Dinâmicas 
Pilha 
 A pilha é uma das estruturas de dados mais importantes na Ciência da 
Computação. 
 
 Imagine, por exemplo, que um programa contém três funções: A, B e C. Considere 
que a função A chama B e B chama a função C. 
 
 Evidentemente, a função B não pode terminar seu processamento enquanto a 
função C não retornar. Analogamente, A não pode terminar enquanto B não 
retornar de seu processamento. 
 
 Portanto, as funções A, B e C têm a propriedade “a última função que começou sua 
execução será a primeira função a terminar seu processamento”. 
 
 Como cada função necessita de seus próprios dados, esses dados devem ser 
alocados em uma estrutura que apresenta esta mesma propriedade, ou seja, uma 
pilha. 
Pilha 
 Outra aplicação importante das pilhas é a avaliação 
de expressões aritméticas escritas na forma posfixa 
(notação polonesa). 
 
 Avaliar fechamento de parênteses 
 Funções recursivas em compiladores; 
 Mecanismo de desfazer/refazer dos editores de texto; 
 Navegação entre páginas Web; 
 
Pilha 
 Estrutura de dados que implementa uma norma de 
último a entrar, primeiro a sair, ou LIFO (Last In First 
Out). 
Pilha 
 Estrutura de dados que implementa uma norma de 
último a entrar, primeiro a sair, ou LIFO (Last In First Out). 
 
 Operações Básicas: 
 Empilhar 
 Desempilhar 
 Verifica se a pilha está vazia 
 
 Outras operações: 
 Excluir todos os elementos da pilha 
 Retornar o topo da pilha sem excluí-lo. 
Pilha 
 A operação INSERT sobre uma pilha é chamada PUSH. 
 A operação DELETE é chamada POP. 
O topo é sempre o começo da lista. 
Só insere e remove do começo da lista!!! 
Pilha 
 Exemplo: 
 Representar o conjunto dinâmico {3, 4, 5, 6} numa pilha. 
Pilha 
 Exemplo: 
 Representar o conjunto dinâmico {3, 4, 5, 6} numa pilha. 
3 Topo 
Push(P, 3) 
Pilha 
 Exemplo: 
 Representar o conjunto dinâmico {3, 4, 5, 6} numa pilha. 
3 
Topo 
Push(P, 4) 
4 
Pilha 
 Exemplo: 
 Representar o conjunto dinâmico {3, 4, 5, 6} numa pilha. 
3 
Topo 
Push(P, 5) 
4 
5 
Pilha 
 Exemplo: 
 Representar o conjunto dinâmico {3, 4, 5, 6} numa pilha. 
3 
Topo Push(P, 6) 
4 
5 
6 
Pilha 
 Exemplo: 
 Remover elemento da pilha 
3 
Topo 
Pop(P) 
O argumento do Pop é só a pilha. 
PQ?? 
4 
5 
6 
Pilha 
 Exemplo: 
 Remover elemento da pilha 
3 
Topo 
Pop(P) 
Mudar o top 
4 
5 
6 
Pilha 
 Exemplo: 
 Remover elemento da pilha 
3 
Topo 
Pop(P) 
Liberar memória 
4 
5 
RECURSIVIDADE 
Recursividade 
 Um método que chama a si mesmo, direta ou 
indiretamente, é dito recursivo. 
 
 Exemplo : Fibonacci 
 A sucessão de Fibonacci ou sequência de Fibonacci é 
uma sequência de números naturais, na qual os primeiros 
dois termos são 0 e 1, e cada termo subsequente 
corresponde à soma dos dois precedentes. 
Recursividade 
Recursividade fatorial(5) 
 
 
fatorial(4)*5 
Recursividade 
 fatorial(5) 
 
 
fatorial(3)*4 
fatorial(4)*5 
Recursividade 
 fatorial(5) 
 
 fatorial(2)*3 
fatorial(3)*4 
fatorial(4)*5 
Recursividade 
 fatorial(5) 
 
 
fatorial(1)*2 
fatorial(2)*3 
fatorial(3)*4 
fatorial(4)*5 
Recursividade 
 fatorial(5) 
 
 
fatorial(1) 
fatorial(1)*2 
fatorial(2)*3 
fatorial(3)*4 
fatorial(4)*5 
Recursividade 
 fatorial(5) 
 
 
1 
fatorial(1)*2 
fatorial(2)*3 
fatorial(3)*4 
fatorial(4)*5 
Recursividade 
 fatorial(5) 
 
 
1 
1*2 = 2 
fatorial(2)*3 
fatorial(3)*4 
fatorial(4)*5 
Recursividade 
 fatorial(5) 
 
 
1 
1*2 = 2 
2*3 = 6 
fatorial(3)*4 
fatorial(4)*5 
Recursividade 
 fatorial(5) 
 
 
1 
1*2 = 2 
2*3 = 6 
6*4 = 24 
fatorial(4)*5 
Recursividade 
 fatorial(5) 
 
 
1 
1*2 = 2 
2*3 = 6 
6*4 = 24 
24*5=120 
Recursividade 
 Vantagens 
 Simplifica a solução de alguns problemas 
 Algoritmos recursivos são mais compactos para alguns tipos 
de algoritmo, mais legíveis e mais fáceis de ser 
compreendidos e implementados. 
 
 Desvantagens 
 Por usarem intensamente a pilha de execução, os algoritmos 
recursivos tendem a ser mais lentos e a consumir mais 
memória que os iterativos, porém pode valer a pena 
sacrificar a eficiência em benefício da clareza. 
 Erros de implementação podem levar a estoure de pilha. 
Recursividade 
 Quadro comparativo da execução de algoritmos para 
o cálculo do Fibonacci. 
 
 
 
 
 
 
 Evitar uso de recursividade quando existe uma 
solução óbvia por iteração. 
n 10 20 30 50 100 
Recursivo 8 ms 1 s 2 min 21 dias 109 anos 
Iterativo 0.17 ms 0.33 ms 0.5 ms 0.75 ms 1.5 ms 
Estruturas de Dados Básicas 
 Ok, eu sei como funciona uma lista, fila e pilha. Mas 
como implementa isso? 
Estruturas de Dados Dinâmicas 
 O QUE VOCÊ PRECISA GUARDAR? 
 Dado 
 
 COMO VOCÊ PRECISA GUARDAR? 
 Estrutura de Dados 
 
 O QUE VOCÊ PRECISA FAZER COM ESSES DADOS? 
 Operações 
Estruturas de Dados Dinâmicas 
 O QUE VOCÊ PRECISA GUARDAR? 
 Dado 
 Vinho 
 
 COMO VOCÊ PRECISA GUARDAR? 
 Estrutura de Dados 
 Lista Ordenada 
 
 O QUE VOCÊ PRECISA FAZER COM ESSES DADOS? 
 Operações 
 Inserir, Remover, Consultar pelo código, pela safra e pelo tipo 
Listas 
 Operação : 
 Iniciar lista 
Inicializar lista vazia : Cabeça da Lista 
Listas 
 Operação : 
 Iniciar lista 
Cabeça da Lista 
Listas 
 Operação : 
 Iniciar lista 
Cabeça da Lista 
Listas 
 Operação : 
 Iniciar lista 
 Forma + correta 
Cabeça da Lista 
Listas 
Inserir ordenado código 1 
Listas 
Inserir ordenado código 8 
Listas 
Inserir ordenado código 7 
Listas 
Inserir ordenado código 7 
Instanciar vinho de código 7 
prox do objeto 7 aponta para o prox do objeto 6; 
prox do objeto 6 aponta para o novo objeto; 
Listas 
Listas 
Exercício 
 Implementar uma lista simplesmente encadeada de 
produtos. Cada um dos registros (produto) deve conter: 
 Código (inteiro sem sinal) 
 Nome (string de 50 caracteres) 
 Preço (float) 
 Estoque (inteiro sem sinal) 
 
 Os produtos devem ser lidos de um arquivo chamado 
entrada.txt 
 
 Considerar que o código do produto é único 
 
 
Exercício 
 A lista deve estar sempre ordenada de forma crescente 
pelo código do produto e suporta as seguintes operações: 
 Inicializa lista 
 Insere na lista 
 Remove da lista 
 Mostra elementos da lista 
 Consulta produto na lista pelo nome 
 Soma quantidade total em estoque (soma do estoque de todos os 
produtos) 
 Calcula a média dos preços dos produtos 
 Encontrar os produtos de maior e menor preços