07_TAD e Estruturas elementares

Prévia do material em texto

1
Tipo Abstrato de Dado e Estruturas
Elementares
1
Prof. Cláudio Campelo, PhD
Departamento de Sistemas & Computação / UFCG
Estrutura de Dados e 
Algoritmos
Introdução
2
� Conjuntos são fundamentais para matemática e 
ciência da computação
� Matemática: imutável (naturais, inteiros)
� Computação: dinâmico (modificam o tamanho)
� Manipulação de conjuntos em computação envolve
� Inserir, deletar, pertinência
� Qualquer conjunto que suporta as operações acima é 
chamado de dicionário
2
Conjuntos Dinâmicos
3
� Elementos são objetos contendo uma
chave e possivelmente dados satélite
� Alguns conjuntos dinâmicos pressupoem
que existe uma relação de ordem entre 
as chaves. Isso permite falar do próximo
elemento ao invés de um elemento
específico.
chave
dados 
satélites
Conjuntos Dinâmicos
4
� Operações sobre um conjunto dinâmico S:
� Consultas: search(k)
� Modificações: insert(x), delete(x), minimum(S), 
maximum(S), successor(x), predecessor(x)
� Exemplos:
� Vetor, pilha, fila, listas
� Árvore binária, AVL, splay, B, preto-vermelho
� Tabelas de dispersão (hash)
chave
dados 
satélites
3
Tipo Abstrato de Dado (TAD)
5
� É um contrato de serviço
� Estabelece como cliente e servidor devem se comportar
para que tudo funcione
� Formalmente é uma especificação abstrata de um 
tipo
� Encapsula a estrutura de dados
� Agrupa a estrutura de dados e operações. A escolha da 
representação é influenciada pelas operações.
� Abstrai de uma implementação específica (não diz como 
é implementado)
� É util para dizer em que consiste o serviço e como
ele deve ser usado.
Tipo Abstrato de Dado (TAD)
6
� Como definir um TAD em Java?
� Como implementar um TAD em Java?
4
Tipo Abstrato de Dado (TAD)
7
� Como definir um TAD em Java?
� Uso de interfaces
� Interface é um contrato em aberto
� Cumprimento dos aspectos sintáticos � garantidos pelo
compilador
� Cumprimento dos aspectos semânticos � depende da
boa programação
� Como implementar um TAD em Java?
� Seguir a assinatura da interface
� Seguir a semântica especificada para os serviços da
interface
Tipo Abstrato de Dado (TAD)
8
� Consequências do uso de TAD
� Bom uso de interfaces:
� Desacopla código do cliente do servidor (melhora a 
modularidade)
� Facilita mudanças do tipo concreto em uma aplicação
(aumenta estensibilidade)
� Permite reuso de tipos
� O bom uso requer que se identifique:
� Interfaces adequadas para o problema
� Boas implementações de cada interface
� Programe para interfaces, não para
implementações!
5
Estruturas de Dados Elementares
9
Vetor
10
� É a mais básica das estruturas de dados. 
� Vetores são matrizes unidimensionais e também 
são chamados de arrays. 
� Acesso direto ao elemento através de indexação
� Exemplo
� A = [10, 5, -2, 0, 7]
� Acesso: A[2];
� Modificação: A[3] = 19;
6
Vetor
11
� Operações
� Inserir x
� O(?)
� Remover x
� O(?)
� Pesquisar x
� O(?)
� Pesquisar k-ésimo elemento
� O(?)
Vetor
12
� Operações
� Inserir x
� O(1)
� Remover x
� O(n)
� Pesquisar x
� O(n)
� Pesquisar k-ésimo elemento
� O(1)
7
Vetor (API de Java)
13
� Vector
� http://www.docjar.com/html/api/java/util/Vector.java.html
� Operações
� indexOf
� elementAt
� addElement
� removeElement
� remove(int i)
Pilha (Stack) - Intuição
14
8
Pilha (Stack)
15
� Conjunto dinâmico onde a operação de remoção
segue uma política específica
� Definição
� Estrutura de dados em que a inserção e a remoção de 
elementos de uma seqüência se faz pela mesma 
extremidade, geralmente designada por topo da pilha.
� Política de acesso LIFO = Last-in First-out
Pilha (Stack)
16
� Operações (interface)
� Criar uma pilha vazia (create)
� Inserir/Empilhar (push)
� Deletar/Desempilhar (pop)
� Acessar o elemento do topo (top)
� Verificar se está vazia (isEmpty)
� Verificar se está cheia (isFull)
9
Pilha (Stack)
17
� Interface em Java
� Como seria a interface de uma pilha genérica em
Java? 
Pilha (Stack)
18
� Interface em Java
� Como descrever uma pilha genérica em Java? 
public interface Stack<T> {
public void push(T elem) throws StackOverflowException;
public T pop() throws StackUnderflowException;
public T top();
public boolean isEmpty();
public boolean isFull();
}
public class StackOverflowException extends Exception {
public StackOverflowException() {
super(“Stack is full");
}
}
10
Pilha (Stack)
19
� Interface em Java
� Como descrever uma pilha genérica em Java? 
public interface Stack<T> {
public void push(T elem) throws StackOverflowException;
public T pop() throws StackUnderflowException;
public T top();
public boolean isEmpty();
public boolean isFull();
}
public class StackOverflowException extends Exception {
public StackOverflowException() {
super(“Stack is full");
}
}
E o create da pilha?
Pilha (Stack)
20
� Implementação com array
push(17);
push(3); pop();
11
Stack (funcionamento)
21
inicialização
top
Stack(funcionamento)
22
push(elemento)
top
12
Stack (funcionamento)
23
push(elemento)
push(elemento)
top
Stack (funcionamento)
24
push(elemento)
push(elemento)
push(elemento)
top
13
Stack (funcionamento)
25
push(elemento)
push(elemento)
push(elemento)
push(elemento)
top
Stack (funcionamento)
26
push(elemento)
push(elemento)
push(elemento)
push(elemento)
pop()
top
retornado
14
Stack (funcionamento)
27
push(elemento)
push(elemento)
push(elemento)
push(elemento)
pop()
pop()
top
retornado
Stack (funcionamento)
28
push(elemento)
push(elemento)
push(elemento)
push(elemento)
pop()
pop()
pop()
top
retornado
15
Stack (funcionamento)
29
push(elemento)
push(elemento)
push(elemento)
push(elemento)
pop()
pop()
pop()
pop()
top
retornado
Stack (funcionamento)
30
push(elemento)
push(elemento)
push(elemento)
push(elemento)
pop()
pop()
pop()
pop()
pop()
top
StackUnderflow
16
Implementação
31
Stack-Full(S)
1 if top[S] = size[S]
2 then TRUE
3 else FALSE
Push(S,x)
1 if Stack-Full(S)
2 then error “overflow”
3 else top[S] ← top[S] + 1
4 S[top[S]] ← x
Implementação
32
Stack-Full(S)
1 if top[S] = size[S]
2 then TRUE
3 else FALSE
Push(S,x)
1 if Stack-Full(S)
2 then error “overflow”
3 else top[S] ← top[S] + 1
4 S[top[S]] ← x
Opcional
17
Implementação
33
Stack-Full(S)
1 if top[S] = size[S]
2 then TRUE
3 else FALSE
Push(S,x)
1 if Stack-Full(S)
2 then error “overflow”
3 else top[S] ← top[S] + 1
4 S[top[S]] ← x
Essencial
Implementação
Stack-Full(S)
1 if top[S] = size[S]
2 then TRUE
3 else FALSE
Push(S,x)
1 if Stack-Full(S)
2 then error “overflow”
3 else top[S] ← top[S] + 1
4 S[top[S]] ← x
Qual a complexidade de
cada serviço?
18
Implementação
35
Stack-Full(S)
1 if top[S] = size[S]
2 then TRUE
3 else FALSE
Push(S,x)
1 if Stack-Full(S)
2 then error “overflow”
3 else top[S] ← top[S] + 1
4 S[top[S]] ← x
Qual a complexidade de
cada serviço?
Ɵ(1)
Ɵ(1)
Implementação
36
Stack-Full(S)
1 if top[S] = size[S]
2 then TRUE
3 else FALSE
Push(S,x)
1 if Stack-Full(S)
2 then error “overflow”
3 else top[S] ← top[S] + 1
4 S[top[S]] ← x
Qual a complexidade de
cada serviço?
Ɵ(1)
Ɵ(1)
Ɵ(1)
Ɵ(1)
19
Exercício
37
� Como fica o estado de uma pilha inicialmente vazia
após a execução dos comandos:
� push(10)
� push(5)
� pop()
� push(7)
� top()
� pop()
� isEmpty()
Stack (Aplicação)
38
� Processamento de expressões aritméticas em 
calculadoras
� (1+5)*7 = 1 5 + 7 * = 42
� Execução de programas
� Quando uma rotinachama outra rotina, a primeira deve 
saber como prosseguir quando a segunda for concluída.
� Exemplo: fatorial
� Browser (botão voltar)
� Função “desfazer” do editores de texto
20
Pilha (aplicação)
39
f(0) = 1
f(n) = n*f(n-1)
top
f(5) = 5*f(4)
f(5) 5*f(4)
Pilha (aplicação)
40
f(0) = 1
f(n) = n*f(n-1)
top
f(5) = 5*f(4)
f(5) 5*
f(4)
21
Pilha (aplicação)
41
f(0) = 1
f(n) = n*f(n-1)
top
f(5) = 5*f(4)
f(4) = 4*f(3)
f(5) 5*
f(4) 4*
f(3)
Pilha (aplicação)
42
f(0) = 1
f(n) = n*f(n-1)
top
f(5) = 5*f(4)
f(4) = 4*f(3)
f(3) = 3*f(2)
f(5) 5*
f(4) 4*
f(3) 3*
f(2)
22
Pilha (aplicação)
43
f(0) = 1
f(n) = n*f(n-1)
top
f(5) = 5*f(4)
f(4) = 4*f(3)
f(3) = 3*f(2)
f(2) = 2*f(1)
f(5) 5*
f(4) 4*
f(3) 3*
f(2) 2*
f(1)
Pilha (aplicação)
44
f(0) = 1
f(n) = n*f(n-1)
topf(5) = 5*f(4)
f(4) = 4*f(3)
f(3) = 3*f(2)
f(2) = 2*f(1)
f(1) = 1*f(0)
f(5) 5*
f(4) 4*
f(3) 3*
f(2) 2*
f(1) 1*
f(0)
23
Pilha (aplicação)
45
f(0) = 1
f(n) = n*f(n-1)
topf(5) = 5*f(4)
f(4) = 4*f(3)
f(3) = 3*f(2)
f(2) = 2*f(1)
f(1) = 1*f(0)
f(0) = 1
f(5) 5*
f(4) 4*
f(3) 3*
f(2) 2*
f(1) 1*
1
Pilha (aplicação)
46
f(0) = 1
f(n) = n*f(n-1)
top
f(5) = 5*f(4)
f(4) = 4*f(3)
f(3) = 3*f(2)
f(2) = 2*f(1)
f(1) = 1*1
f(5) 5*
f(4) 4*
f(3) 3*
f(2) 2*
1
1
24
Pilha (aplicação)
47
f(0) = 1
f(n) = n*f(n-1)
top
f(5) = 5*f(4)
f(4) = 4*f(3)
f(3) = 3*f(2)
f(2) = 2*1*1
f(5) 5*
f(4) 4*
f(3) 3*
2
1
1
Pilha (aplicação)
48
f(0) = 1
f(n) = n*f(n-1)
top
f(5) = 5*f(4)
f(4) = 4*f(3)
f(3) = 3*2*1*1
f(5) 5*
f(4) 4*
6
2
1
1
25
Pilha (aplicação)
49
f(0) = 1
f(n) = n*f(n-1)
top
f(5) = 5*f(4)
f(4) = 4*3*2*1*1
f(5) 5*
24
6
2
1
1
Pilha (aplicação)
50
f(0) = 1
f(n) = n*f(n-1)
top
f(5) = 5*4*3*2*1*1
120
24
6
2
1
1
26
Pilha (aplicação)
51
f(0) = 1
f(n) = n*f(n-1)
top
120
24
6
2
1
1
120
retornado
Fila (Queue) - Intuição
52
27
Fila (Queue)
53
� Conjunto dinâmico com políticas de acesso
específicas
� Definição
� Estrutura de dados em que a respeita a ordem temporal 
dos elementos. 
� Os elementos são introduzidos na cauda
� Os elementos são removidos da cabeça
� FIFO = First In, First Out.
Fila (Queue)
54
� Operações (interface)
� Criar uma pilha vazia (create)
� Inserir/Enfileirar (enqueue)
� Deletar/Remover (dequeue)
� Acessar o elemento da cabeça (head)
� Verificar se está vazia (isEmpty)
� Verificar se está cheia (isFull)
28
Fila (Queue)
55
� Interface em Java
� Como descrever uma Fila genérica em Java?
public interface Queue<T> {
public void enqueue(T elem) throws QueueOverflowException;
public T dequeue() throws QueueUnderflowException;
public T head();
public boolean isEmpty();
public boolean isFull();
}
public class QueueOverflowException extends Exception {
public QueueOverflowException() {
super(“Fila cheia");
}
}
Fila (Queue)
56
� Interface em Java
� Como descrever uma Fila genérica em Java?
public interface Queue<T> {
public void enqueue(T elem) throws QueueOverflowException;
public T dequeue() throws QueueUnderflowException;
public T head();
public boolean isEmpty();
public boolean isFull();
}
public class QueueOverflowException extends Exception {
public QueueOverflowException() {
super(“Fila cheia");
}
}
E o create da fila?
29
Fila (funcionamento)
57
Fila (funcionamento)
58
enqueue
30
Fila (funcionamento)
59
enqueue
enqueue
Fila (funcionamento)
60
enqueue
enqueue
enqueue
31
Fila (funcionamento)
61
enqueue
enqueue
enqueue
dequeue
Fila (funcionamento)
62
enqueue
enqueue
enqueue
dequeue
dequeue
32
Fila (funcionamento)
63
enqueue
enqueue
enqueue
dequeue
dequeue
dequeue
Fila (funcionamento)
64
enqueue
enqueue
enqueue
dequeue
dequeue
dequeue
dequeue
QueueUnderflowException
33
Fila (Implementação)
65
isEmpty(){
return tail == -1
}
isFull(){
return tail == A.length-1
}
enqueue(item){
if (not isFull()){
A[++tail]=item
}else{
//error:queue is full
}
}
dequeue(){
if (not isEmpty()){
result = A[0]
shiftLeft()
tail--;
}else{
//error:queue is empty
}
return result;
}
dequeue(){
if (not isEmpty()){
result = A[0]
shiftLeft()
return result;
}else{
//error:queue is empty
}
return result;
}
Fila (Implementação)
66
isEmpty(){
return tail == -1
}
isFull(){
return tail == A.length-1
}
enqueue(item){
if (not isFull()){
A[++tail]=item
}else{
//error:queue is full
}
}
shiftLeft(){
for i : 0 .. tail{
A[i] = A[i+1]
}
}
34
Fila (Implementação)
67
Qual a complexidade?
isEmpty(){
return tail == -1
}
isFull(){
return tail == A.length-1
}
enqueue(item){
if (not isFull()){
A[++tail]=item
}else{
//error:queue is full
}
}
dequeue(){
if (not isEmpty()){
result = A[0]
shiftLeft()
tail--;
}else{
//error:queue is empty
}
return result;
}
isEmpty(){
return tail == -1
}
isFull(){
return tail == A.length-1
}
enqueue(item){
if (not isFull()){
A[++tail]=item
}else{
//error:queue is full
}
}
dequeue(){
if (not isEmpty()){
result = A[0]
shiftLeft()
return result;
}else{
//error:queue is empty
}
return result;
}
Fila (Implementação)
68
Qual a complexidade?
35
Fila (Implementação)
69
� Como evitar a operação de shift em uma fila?
Fila (Implementação)
70
� Como evitar a operação de shift em uma fila?
� Sabendo o início e o fim da fila!
36
Exercício
71
� Como fica o estado de uma fila inicialmente vazia
após a execução dos comandos:
� enqueue(10)
� enqueue(5)
� dequeue()
� enqueue(7)
� head()
� dequeue()
� isEmpty()
Fila (Implementação)
72
� Conhecendo o início e o fim da fila
enqueue(17); enqueue(3); enqueue(5)
dequeue();
37
Fila (Implementação)
73
� Conhecendo o início e o fim da fila
Fila (Implementação)
74
� Conhecendo o início e o fim da fila
IF (not isFull()) IF (not isEmpty())
38
Fila (Implementação)
75
� Conhecendo o início e o fim da fila
Qual o custo das operações?
Fila (Implementação)
76
� Conhecendo o início e o fim da fila
Qual o custo das operações?
39
Referências
77
� Capítulo 11