Estrutura de Dados

Transcrição

Estrutura de Dados

Estruturas de Dados
e
Técnicas de Programação
c 2010-2011 Tomasz Kowaltowski
Copyright Instituto de Computação
Universidade Estadual de Campinas
Algumas transparências foram adaptadas da apostila Estruturas de Dados
e Técnicas de Programação de autoria de Cláudio L. Lucchesi e Tomasz
Kowaltowski.
Tomasz Kowaltowski
Instituto de Computação
Universidade Estadual de Campinas
Estas transparências somente podem ser copiadas para uso pessoal dos
docentes e alunos das disciplinas oferecidas pelo Instituto de Computação
da UNICAMP.
www.ic.unicamp.br/∼tomasz
c
2011
T. Kowaltowski Estruturas de Dados e Técnicas de Programação
1
c
2011
2
Pré-requisito e objetivos
Introdução
I
Pré-requisito: curso básico de programação em C
I
Objetivos:
I
I
I
Programação em (relativamente) baixo nı́vel
Técnicas de programação e estruturação de dados
Preparação para:
I
I
I
I
I
I
c
2011
Introdução
3
Análise de algoritmos
Programação de sistemas
Programação em geral
Bancos de dados
Engenharia de software
...
c
2011
Introdução
4
Programa
I
I
I
I
I
I
I
I
I
I
I
I
I
I
Introdução à análise de algoritmos
Estruturação elementar de dados: matrizes, registros, apontadores
Estruturas lineares: pilhas, filas, filas duplas
Recursão e retrocesso
Árvores binárias: representação, percursos
Árvores gerais: representação, percursos
Aplicação de árvores:
árvores de busca (AVL), filas de prioridade,
árvores B, árvores rubro-negras, árvores digitais
Listas generalizadas
Espalhamento
Processamento de cadeias de caracteres
Gerenciamento de memória
Algoritmos de ordenação
Algoritmos em grafos
Tipos abstratos de dados e orientação a objetos
c
2011
Introdução
Bibliografia
5
Bibliografia
6
G. H. Gonnet.
Handbook of Algorithms and Data Structures.
Addison-Wesley, 1984.
A. V. Aho, J. E. Hopcroft, and J. Ullman.
Data Structures and Algorithms.
E. Horowitz and S. Sahni.
Fundamentals of Data Structures in Pascal.
Computer Science Press, 1984.
A. Drozdek.
Estrutura de Dados e Algoritmos em C++.
Thomson, 2002.
D. E. Knuth.
The Art of Computer Programming, volume I: Fundamental
Algorithms.
J. L. Szwarcfiter e L. Markenzon.
Estruturas de Dados e seus Algoritmos.
LTC Editora, 1994.
C. L. Lucchesi e T. Kowaltowski.
Estruturas de Dados e Técnicas de Programação.
Instituto de Computação – UNICAMP, 2003.
E. M. Reingold and W. J. Hanson.
Data Structures.
Little Brown and Company, 1983.
P. Feofiloff.
Algoritmos em Linguagem C.
Elsevier Editora Ltda., 2009.
c
2011
c
2011
R. Sedgewick.
Algorithms in C.
Bibliografia
7
c
2011
Bibliografia
8
D. F. Stubbs and N. W. Webre.
Data Structures with Abstract Data Types and Pascal.
Brooks/Cole, 1985.
A. M. Tenenbaum, Y. Langsam, and M. J. Augenstein.
Data Structures using C.
Prentice-Hall, 1990.
Noções de Análise de Algoritmos
N. Wirth.
Algorithms + Data Structures = Programs.
Prentice-Hall, 1976.
N. Ziviani.
Projeto de Algoritmos (2a. ed.)
Thomson, 2004.
c
2011
Bibliografia
9
Escolha da estrutura
(a)
10
Exemplo de análise de trechos de programas
Importância da escolha de estrutura de dados – busca do k-ésimo
elemento numa seqüência:
...
x = a[k];
...
c
2011
...
p = a;
i = 0;
w h i l e ( i <k ) {
p = p−>p r o x ;
i ++;
}
x = p−>i n f o ;
...
...
f o r ( i =0; i <n ; i ++)
x = a+b ;
...
(a)
(b)
análise simples (1)
análise detalhada (2)
(b)
...
f o r ( i =0; i <n ; i ++)
f o r ( j =0; j <n ; j ++)
x = a+b ;
...
(c)
a
1
2
b
n
5n + 2
c
n2
5n2 + 5n + 2
(1): atribuições (2): atribuições, operações aritméticas e comparações
(a) Número de operações constante (vetor).
(b) Número de operações proporcional a k (lista ligada).
c
2011
...
x = a+b ;
...
As duas análises produzem resultados proporcionais para valores crescentes
de n.
11
c
2011
12
Notação O()
Exemplo de análise de um procedimento de ordenação
Definição:
f (n) = O(g(n)) se existem n0 e k com f (n) ≤ k ∗ g(n) para todo n > n0 .
Exemplos:
c = O(1)
para qualquer constante c
2 = O(1)
5n + 2 = O(n)
5n2 + 5n + 2 = O(n2 )
O número de comparações de elementos de v, para cada valor de i, é
n − i − 1. O número total de comparações será:
n2 = O(n3 )
nk = O(nk+1 ),
loga n = O(logb n),
v o i d Ordena ( i n t v [ ] , i n t n ) {
i n t i , k , m, t ;
f o r ( i =0; i <n −1; i ++) {
m = i;
f o r ( k=i +1; k<n ; k++)
i f ( v [ k]< v [m] ) m = k ;
t = v [ i ] ; v [ i ] = v [m ] ; v [m] = t ;
}
} /∗ Ordena ∗/
k≥0
n−2
X
a, b > 0
(n − i − 1) =
log2 n = O(log10 n)
i=0
ou seja, o número de comparações é da ordem de O(n2 ).
Outras notações importantes: Θ(), Ω(), etc.
c
2011
13
Crescimento de algumas funções
n log2 n
1
0
2
1
4
2
8
3
16
4
32
5
64
6
128
7
n log2 n
0
2
8
24
64
160
384
896
n2
1
4
16
64
256
1.024
4.096
16.384
n2 n
+
2
2
c
2011
14
Exemplo
n3
1
8
64
512
4.096
32.768
262.144
2.097.152
c
2011
2n
2
4
16
256
65.536
4.294.967.296
≈ 18×1018
≈ 34×1037
Suponha duas máquinas M1 e M2 , sendo a primeira cem vezes mais
rápida do que a segunda. Ambas as máquinas executam um algoritmo de
busca num vetor ordenado de comprimento n. A máquina M1 executa o
algoritmo de busca sequencial (pior caso: n operações); a máquina M2
executa o algoritmo de busca binária (pior caso: log2 n operações).
A seguinte tabela poderia ser obtida através de medidas experimentais de
tempo de execução para vetores de diversos tamanhos, usando alguma
unidade de tempo conveniente.
15
c
2011
16
Exemplo (cont.)
n
M1 (rápida)
M2 (lenta)
16
32
64
128
256
512
1024
2048
...
220
221
...
230
16
32
64
128
256
512
1024
2048
...
1.048.576
2.097.152
...
1.073.741.824
400
500
600
700
800
900
1000
1100
...
2000
2100
...
3000
Execução de programas
Supondo que a unidade seja 1µs (microssegundo), 2.097.152µs corresponde a 17
minutos e 1.073.741.824µs equivale a cerca de 12 horas.
c
2011
17
Exemplo de funções simples
c
2011
18
Exemplo de funções com alocação dinâmica
void g ( i n t x , i n t ∗y ) {
∗y = x ;
} /∗ g ∗/
i n t main ( ) {
int i ;
char c ;
char v [ 5 ] ;
f (& i ) ;
return 0;
} /∗ main ∗/
void f ( i n t ∗z ) {
int y ;
char b ;
y = 235;
g(y , z );
} /∗ f ∗/
typedef char Cadeia [ 5 ] ;
t y p e d e f C a d e i a ∗ ApCadeia ;
typedef struct {
C a d e i a nome ;
int idade ;
} Reg , ∗ApReg ;
v o i d A l o c a ( ApCadeia ∗ c , ApReg ∗ r ) {
api = malloc ( sizeof ( int ) ) ;
∗ api = 10;
∗c = malloc ( s i z e o f ( Cadeia ) ) ;
∗ r = m a l l o c ( s i z e o f ( Reg ) ) ;
} /∗ A l o c a ∗/
ApCadeia apc ;
ApReg a p r ;
int ∗ api ;
i n t main ( ) {
A l o c a (&apc ,& a p r ) ; f r e e ( apc ) ;
f r e e ( apr ) ; f r e e ( api ) ;
return 0;
} /∗ main ∗/
Pilha de execução (supõe inteiros de dois bytes):
apc
i
c
v
y
z
235
b
235
main
f
apr
c
api
r
y
x
global
235
main
Aloca
pilha de execução
g
10
Obs.: Na realidade, os inteiros são armazenados sob a forma binária.
c
2011
memória dinâmica
19
c
2011
20
Exemplo de função recursiva
i n t main ( ) {
i n t m;
m = fat (4);
return 0;
} /∗ main ∗/
int fat ( int n) {
i f ( n==0)
return 1;
else
r e t u r n n∗ f a t ( n −1);
} /∗ f a t ∗/
m
res
n
res
n
res
n
res
n
res
n
24
24
4
6
3
2
2
1
1
1
0
c
2011
Estruturas ligadas
21
Listas ligadas simples
c
2011
Estruturas ligadas
22
Inserção e remoção com passagem por valor
p
...
...
Declarações (equivalentes):
typedef
struct RegLista ∗ Lista ;
typedef
struct RegLista {
T info ;
L i s t a prox ;
} RegLista ;
p
typedef
struct RegLista {
T info ;
struct RegLista ∗ prox ;
} RegLista , ∗ L i s t a ;
c
2011
Estruturas ligadas
23
...
x
void I n s e r e ( L i s t a p , T x ) {
Lista q =
malloc ( sizeof ( RegLista ) ) ;
q−>i n f o = x ;
q−>p r o x = p−>p r o x ;
p−>p r o x = q ;
}
q
v o i d Remove ( L i s t a p , T ∗ x ) {
L i s t a q = p−>p r o x ;
∗ x = q−>i n f o ;
p−>p r o x = q−>p r o x ;
free (q );
}
c
2011
Estruturas ligadas
24
Inserção e remoção com passagem por valor (cont.)
Inserção e remoção com passagem por referência
...
...
...
x
p
p
...
x
q
q
I
O argumento p é o apontador para o predecessor do nó a ser inserido
ou removido.
I
A função ’Remove’ não pode remover um nó que é o único da lista.
I
A função ’Insere’ não pode inserir um nó no inı́cio da lista, inclusive
se ela for vazia.
v o i d I n s e r e ( L i s t a ∗p , T x ) {
Lista q =
malloc ( sizeof ( RegLista ) ) ;
q−>i n f o = x ;
q−>p r o x = ∗p ;
∗p = q ;
}
v o i d Remove ( L i s t a ∗p , T ∗ x ) {
L i s t a q = ∗p ;
∗ x = q−>i n f o ;
∗p = q−>p r o x ;
free (q );
}
Esta convenção elimina os problemas da passagem por valor. Note-se que
as variáveis p e q têm tipos diferentes.
c
2011
Estruturas ligadas
25
Lista simples com nó cabeça
c
2011
Estruturas ligadas
26
Estruturas ligadas
28
Lista simples circular
p
...
p
...
Lista vazia:
p
Problema: lista vazia?
Esta convenção permite o uso de passagem por valor nas funções básicas.
O campo de informação do nó cabeça pode ser aproveitado para guardar
alguma informação adicional (por exemplo, o comprimento da lista).
c
2011
Estruturas ligadas
27
c
2011
Lista circular com nó cabeça
Busca em lista circular com nó cabeça – sentinelas
Lista BuscaCircular (
Lista p , T x) {
/∗ Busca sem s e n t i n e l a ∗/
Lista q = p;
do {
q = q−>p r o x ;
} w h i l e ( ( q!=p ) &&
( q−>i n f o != x ) ) ;
i f ( q==p )
r e t u r n NULL ;
else
return q ;
}
p
...
Lista vazia:
p
c
2011
Estruturas ligadas
29
Lista duplamente ligada com nó cabeça
Lista BuscaCircular (
Lista p , T x) {
/∗ Busca com s e n t i n e l a ∗/
Lista q = p;
q−>i n f o = x ;
do {
q = q−>p r o x ;
} w h i l e ( q−>i n f o != x ) ;
i f ( q==p )
r e t u r n NULL ;
else
return q ;
}
c
2011
Estruturas ligadas
30
Operações sobre listas duplamente ligadas
typedef
struct RegListaDupla {
T info ;
s t r u c t R e g L i s t a D u p l a ∗ esq , ∗ d i r ;
} RegListaDupla , ∗ ListaDupla ;
p
...
Lista vazia:
void InsereDuplaEsq (
ListaDupla p , T x) {
ListaDupla q =
malloc ( s i z e o f ( RegListaDupla ) ) ;
q−>i n f o = x ;
q−>e s q = p−>e s q ;
q−>d i r = p ;
p−>esq−>d i r = q ;
p−>e s q = q ;
}
p
I
É possı́vel percorrer os elementos nas duas direções, a partir de
qualquer lugar da lista.
I
É possı́vel remover o elemento apontado.
c
2011
v o i d RemoveDupla (
ListaDupla p , T ∗x ) {
p−>esq−>d i r = p−>d i r ;
p−>d i r −>e s q = p−>e s q ;
∗ x = p−>i n f o ;
free (p );
}
A função ’RemoveDupla’ supõe que há pelo menos um elemento na lista.
Estruturas ligadas
31
c
2011
Estruturas ligadas
32
Exemplo: operações com polinômios
Exemplo de função: impressão
Seja um polinômio de grau n:
P (x) = an xn + an−1 xn−1 + . . . + a1 x1 + a0 x0
t y p e d e f s t r u c t AuxPol {
int
expo ;
float
coef ;
s t r u c t AuxPol ∗ p r o x ;
} Termo , ∗ P o l i n o m i o ;
onde an 6= 0, exceto possivelmente no caso n = 0.
Representação ligada omite os termos não nulos. Por exemplo, os
polinômios:
P1 (x) = 5x20 − 3x5 + 7
e
P2 (x) = 0:
podem ser representados por:
p1
-1
5
p2
20
-3
5
7
0
void ImprimePolinomio ( Polinomio p) {
i f ( p−>p r o x==p ) {
p r i n t f ( ” P o l i n ô m i o n u l o \n” ) ;
return ;
}
p = p−>p r o x ;
w h i l e ( p−>expo !=−1) {
p r i n t f ( ”(%2d , % 5 . 1 f ) ” ,
p−>expo , p−>c o e f ) ;
p = p−>p r o x ;
}
p r i n t f ( ” \n” ) ;
}
-1
Por convenção, o expoente do nó cabeça é -1.
c
2011
Estruturas ligadas
33
Soma de polinômios: paradigma de intercalação
-1
q
-1
Exemplo:
qq
50
10
0
−30
...
rr
rr0
-1
34
Matrizes esparsas
...
qq0
r
Estruturas ligadas
pp
pp0
p
c
2011
...
As variáveis pp e qq representam os termos correntes dos polinômios
dentro da malha de repetição e a variável rr aponta para o último termo já
calculado da soma; pp0, qq0 e rr0 são os valores iniciais das variáveis pp,
qq e rr.
A implementação das operações é um exercı́cio. Note-se que o produto de
dois polinômios pode ser calculado como uma sequência de somas de
produtos de um polinômio por um termo.
c
2011
Estruturas ligadas
35
0
0
0
20
0
0
0 −60
0
0
0
5
Dada uma matriz n × n, quando o número de elementos não nulos é uma
percentagem pequena de n2 (não é o caso do exemplo!), pode ser
conveniente representar a matriz por meio de uma estrutura de listas
ortogonais.
Suporemos, neste exemplo, que as linhas e as colunas são numeradas a
partir de 1.
c
2011
Estruturas ligadas
36
Matrizes esparsas: listas ortogonais
Operações sobre matrizes esparsas
Alguns exemplos:
-1
1
-1
-1
-1
1
1
-1
2
-1
3
-1
4
typedef
s t r u c t RegEsparsa {
int linha , coluna ;
d o u bl e v a l o r ;
s t r u c t RegEsparsa ∗ d i r e i t a , ∗ abaixo ;
} RegEsparsa , ∗ Matriz ;
1
50
2
-1
2
1
2
3
10
3
-1
4
-1
4
1
50
10
0
−30
20
4
-30
3
4
-60
0
0
0
0
0
20
0
−60
v o i d I n i c i a l i z a M a t r i z ( M a t r i z ∗a , i n t m, i n t n ) ;
void LiberaMatriz ( Matriz a ) ;
d o ub l e E l e m e n t o M a t r i z ( M a t r i z a , i n t i , i n t j ) ;
v o i d A t r i b u i M a t r i z ( M a t r i z a , i n t i , i n t j , do ubl e x ) ;
void SomaMatrizes ( Matriz a , Matriz b , Matriz ∗c ) ;
void M u l t i p l i c a M a t r i z e s ( Matriz a , Matriz b , Matriz ∗c ) ;
4
5
O acesso à matriz é feito a partir do nó cabeça das listas das cabeças das
linhas e das colunas (super-cabeça!).
c
2011
0
0
0
5
Estruturas ligadas
37
É importante notar os casos em que a passagem do argumento do tipo
’Matriz’ é feita por referência. (Nas duas últimas operações, a variável ’c’
recebe o resultado.)
c
2011
Estruturas ligadas
38
Estruturas lineares em geral: operações tı́picas
Estruturas lineares
c
2011
Estruturas lineares
39
I
selecionar e modificar o k-ésimo elemento;
I
inserir um novo elemento entre as posições k e k + 1;
I
remover o k-ésimo elemento;
I
concatenar duas sequências;
I
desdobrar uma sequência;
I
copiar uma sequência;
I
determinar o tamanho de uma sequência;
I
buscar um elemento que satisfaz uma propriedade;
I
ordenar uma sequência;
I
aplicar um procedimento a todos os elementos de uma sequência;
I
...
c
2011
Estruturas lineares
40
Estruturas lineares particulares
Pilha: implementação sequencial
empilha (insere)
0
...
I
...
Pilha (stack): inserção e remoção na mesma extremidade da estrutura
desempilha (remove)
I
topo
Fila (queue): inserção numa extremidade (fim) e remoção na outra
extremidade (inı́cio)
Pilha vazia:
I
Fila dupla (double ended queue): inserção e remoção em ambas
extremidades da estrutura
0
...
topo
(-1)
Inicialmente: topo=-1.
c
2011
Estruturas lineares
41
Pilha: implementação sequencial (cont.)
c
2011
Estruturas lineares
42
Estruturas lineares
44
Pilha: implementação ligada
empilha (insere)
0
...
...
topo
...
desempilha (remove)
topo
Pilha vazia:
typedef
struct {
i n t topo ;
T e l e m e n t o s [TAM MAX ] ;
} Pilha ;
v o i d E m p i l h a ( P i l h a ∗p , T x ) {
i f ( ( ∗ p ) . t o p o==(TAM MAX−1))
TrataErro (” Pilha cheia ” ) ;
( ∗ p ) . t o p o++;
((∗ p ) . elementos ) [ ( ∗ p ) . topo ] = x ;
}
topo
(Uma lista ligada simples.)
Exercı́cio: a função “Desempilha”.
c
2011
Estruturas lineares
43
c
2011
Pilha: implementação ligada (cont.)
Fila: implementação sequencial
remove
...
...
...
insere
topo
...
frente
typedef struct ElemPilha {
T info ;
struct
ElemPilha ∗ prox ;
} ElemPilha , ∗ P i l h a ;
v o i d E m p i l h a ( P i l h a ∗p , T x ) {
Pilha q =
malloc ( s i z e o f ( ElemPilha ) ) ;
i f ( q==NULL)
T r a t a E r r o ( ” F a l t a memória ” ) ;
q−>i n f o = x ;
q−Prox = ∗p ;
∗p = q ;
}
fim
Convenção: frente precede o primeiro elemento da fila; consequentemente,
o tamanho da fila é dado por fim−frente.
Fila vazia:
... ...
frente
fim
Condição de fila vazia: frente == fim.
Inicialmente: frente = fim = −1.
Exercı́cio: a função “Desempilha”.
c
2011
Estruturas lineares
45
Fila: implementação ligada circular
c
2011
n-1
0
1
2
3
fim
...
..
.
...
Fila vazia:
fila
frente
.
..
fim
frente
fim
Convenção: frente precede o primeiro elemento da fila; consequentemente,
o tamanho da fila é dado por (fim−frente + n)%n.
A fila pode ser representada por uma única variável (fila) ou um par de
variáveis (frente e fim).
c
2011
46
Fila: implementação sequencial circular
fila
frente
Estruturas lineares
Estruturas lineares
47
c
2011
Estruturas lineares
48
Fila: implementação sequencial circular (cont.)
n-1 0
1
2
3
n-1 0 1
2
#d e f i n e TAM MAX FILA 1000
...
...
Fila: implementação sequencial circular (cont.)
typedef struct {
i n t frente , fim ;
T e l e m e n t o s [ TAM MAX FILA ] ;
} Fila ;
.
..
3
...
frente
...
frente
..
fim
fim
Condições:
I
I
I
I
I
Inicial: frente == fim == 0 (ou qualquer outro valor)
Fila vazia: frente == fim
Fila cheia: frente == fim (a mesma condição!)
Solução 1: sacrificar uma posição do vetor; a condição de fila cheia
fica: frente == (fim + 1)%n.
Solução 2: uma variável adicional inteira com o tamanho da fila ou
booleana indicando se a fila está vazia.
c
2011
Estruturas lineares
49
void I n s e r e F i l a ( F i l a ∗f , T x ) {
i f ( ( ∗ f ) . f r e n t e ==(((∗ f ) . f i m+1)%TAM MAX FILA ) )
TrataErro (” F i l a cheia ” ) ;
( ∗ f ) . f i m = ( ( ∗ f ) . f i m+1)%TAM MAX FILA ;
(∗ f ) . elementos [ ( ∗ f ) . fim ] = x ;
}
Exercı́cio: a função “RemoveFila”.
c
2011
Estruturas lineares
50
Aplicações de pilhas
I
Processamento de linguagens parentéticas:
I
c
2011
I
51
linguagens de programação
XML
I
Implementação da recursão
I
Percurso de estruturas hierárquicas (árvores)
I
Avaliação expressões em notação pós-fixa (notação polonesa reversa)
I
Transformação entre notações
c
2011
52
Exemplo de aplicação simples: balanceamento de parênteses
Correto
()
[()]
[]()[()[]]
((([[[]]])))
Pilha
Vazia
(
([
([(
([([
([(
([([
([([(
([([
([(
([
(
Vazia
Incorreto
(
)
[)
()()[
)(
c
2011
Balanceamento de parênteses (cont.)
53
Notações para expressões aritméticas
c
2011
Infixa:
I
I
I
Notação pós-fixa:
um operador unário precede o operando
um operador binário separa os dois operandos
parênteses indicam prioridades
I
Pós-fixa: os operadores seguem os operandos
I
Pré-fixa: os operadores precedem os operandos
pós-fixa
a
ab+
abc ∗ +
ab + c∗
c
2011
54
(3 + 5) ∗ 2 − (10 − 3)/2
3 5 + 2 ∗ 10 3 − 2/−
Estados consecutivos da pilha:
Pilha
Vazia
3
3 5
8
8 2
16
16 10
16 10 3
16 7
16 7 2
16 3
13
Exemplos:
infixa
a
a+b
a+b∗c
(a + b) ∗ c
Exemplo: avaliação de expressões sob forma pós-fixa
Notação infixa:
I
Resto da sequência
([([][()])])
[([][()])])
([][()])])
[][()])])
][()])])
[()])])
()])])
)])])
])])
)])
])
)
pré-fixa
a
+ab
+a ∗ bc
∗ + abc
55
Entrada
3 5 + 2 ∗ 10 3 − 2/−
5 + 2 ∗ 10 3 − 2/−
+2 ∗ 10 3 − 2/−
2 ∗ 10 3 − 2/−
∗10 3 − 2/−
10 3 − 2/−
3 − 2/−
−2/−
2/−
/−
−
Vazia
c
2011
56
Exemplo: transformação de notação infixa para pós-fixa
Transformação de notação infixa para pós-fixa (cont.)
a ∗ b + c ∗ d e /f − g ∗ h
Entrada infixa:
Saı́da pós-fixa:
Saı́da
a
a
ab
ab∗
ab∗
ab ∗ c
ab ∗ c
ab ∗ cd
ab ∗ cd
ab ∗ cde
ab ∗ cde∧
a ∗ b + c ∗ d ∧ e / f −g ∗ h
a b ∗ c d e ∧ ∗ f /+g h ∗−
I
As varáveis são copiadas diretamente para a saı́da.
I
Os operadores precisam ser lembrados numa pilha.
I
Um operador é copiado da pilha para a saı́da somente quando aparece
na entrada um operador de prioridade menor ou igual.
c
2011
Pilha
∗
∗
+
+
+∗
+∗
+∗∧
+∗∧
+∗
Entrada
a ∗ b + c ∗ d ∧ e/f − g ∗ h
∗ b + c ∗ d ∧ e/f − g ∗ h
b + c ∗ d ∧ e/f − g ∗ h
+ c ∗ d ∧ e/f − g ∗ h
+ c ∗ d ∧ e/f − g ∗ h
c ∗ d ∧ e/f − g ∗ h
∗d ∧ e/f − g ∗ h
d ∧ e/f − g ∗ h
∧ e/f − g ∗ h
e/f − g ∗ h
/f − g ∗ h
/f − g ∗ h
(continua)
57
c
2011
58
Transformação de notação infixa para pós-fixa (cont.)
Saı́da
ab ∗ cde ∧ ∗
ab ∗ cde ∧ ∗
ab ∗ cde ∧ ∗f
ab ∗ cde ∧ ∗f /
ab ∗ cde ∧ ∗f /+
ab ∗ cde ∧ ∗f /+
ab ∗ cde ∧ ∗f / + g
ab ∗ cde ∧ ∗f / + g
ab ∗ cde ∧ ∗f / + gh
ab ∗ cde ∧ ∗f / + gh∗
ab ∗ cde ∧ ∗f / + gh ∗ −
Pilha
+
+/
+/
+
−
−
−∗
−∗
−
c
2011
Entrada
/f − g ∗ h
f −g∗h
−g∗h
−g∗h
−g∗h
g∗h
∗h
h
Exemplos de recursão
59
c
2011
60
Exemplo 1: função fatorial
Exemplo 2: números de Fibonacci
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
int f a t o r i a l ( int n) {
i f ( n==0)
return 1;
else
r e t u r n n∗ f a t o r i a l ( n −1);
}
int fibo ( int n) {
i f ( n<=1)
return n ;
else
r e t u r n f i b o ( n−1)+ f i b o ( n −2);
}
i n t i , f =1;
f o r ( i =1; i <=n ; i ++)
f = f∗i ;
return f ;
}
int fibo ( int n) {
i n t f 1 =0, f 2 =1 , f 3 , i ;
f o r ( i =1; i <=n ; i ++) {
f 3 = f 1+f 2 ;
f1 = f2 ;
f2 = f3 ;
}
return f1 ;
}
Eficiência: ambos O(n) (n multiplicações).
Eficiência:
n = 100:
c
2011
61
Exemplo 3: Torres de Hanoi
.
..
..
.
O(1.6n )
O(n)
≈ 1020 somas
100 somas
c
2011
62
Torres de Hanoi: transferência recursiva de N-1 discos
.
..
N
A
B
C
(origem)
(destino)
(auxiliar)
..
.
X
N
Y
Z
Hanoi(X,Z,Y,N-1)
Objetivo: transferir os N discos da torre A para a torre B, usando a torre C
como auxiliar.
Regras:
.
..
I
um disco de cada vez
I
disco de diâmetro maior não pode ficar em cima de um disco de
diâmetro menor
X
Y
..
.
N-1
Z
Solução recursiva: função Hanoi(org,dest,aux,n).
c
2011
63
c
2011
64
Torres de Hanoi: movimento do maior disco
.
..
X
Y
..
.
Torres de Hanoi: transferência recursiva final de N-1 discos
.
..
N-1
Z
X
Y
Move X para Y
Y
c
2011
..
.
.
..
N-1
Z
X
65
Torres de Hanoi: função Hanoi
Z
..
.
N
Y
Z
c
2011
66
Torres de Hanoi: exemplos de saı́da
v o i d Hanoi ( c h a r org , c h a r d e s t , c h a r aux , i n t n ) {
i f ( n>0) {
Hanoi ( org , aux , d e s t , n −1);
p r i n t f ( ”Mova de %c p a r a %c \n” , org , d e s t ) ;
Hanoi ( aux , d e s t , org , n −1);
}
}
I
Chamada inicial: Hanoi(’A’,’B’,’C’,64).
I
Número de movimentos: 2N − 1 (prova por indução).
I
Este é o número mı́nimo.
c
2011
N-1
Hanoi(Z,Y,X,N-1)
.
..
X
..
.
N=1:
N=3:
Mova de A p a r a B
Mova
Mova
Mova
Mova
Mova
Mova
Mova
N=2:
Mova de A p a r a C
Mova de A p a r a B
Mova de C p a r a B
67
c
2011
de
de
de
de
de
de
de
A
A
B
A
C
C
A
para
para
para
para
para
para
para
B
C
C
B
A
B
B
68
Torres de Hanoi: exemplos de saı́da (cont.)
Exemplo 4: geração de permutações
Problema: Gerar todas as permutações dos m elementos de um vetor.
N=4
Mova
Mova
Mova
Mova
Mova
Mova
Mova
Mova
...
de
de
de
de
de
de
de
de
A
A
C
A
B
B
A
A
para
para
para
para
para
para
para
para
C
B
B
C
A
C
C
B
Mova
Mova
Mova
Mova
Mova
Mova
Mova
de
de
de
de
de
de
de
c
2011
C
C
B
C
A
A
C
para
para
para
para
para
para
para
B
A
A
B
C
B
B
...
0
69
k-1
Suponha uma função Permuta(k,m) que gera (imprime) todas as
permutações dos elementos de 0 a k-1, seguidas dos elementos de k a
m-1.
I
A chamada inicial Permuta(m,m) resolveria o problema.
I
A solução consistirá em trocar o elemento de ı́ndice k-1
consecutivamente com todos os elementos que o precedem e aplicar a
função recursivamente.
c
2011
Geração das permutações (cont.)
Passo recursivo: i=k-1, ..., 0
Função Permuta:
...
i
...
k-1
v o i d Permuta ( i n t k , i n t m) {
i f ( k==0)
I m p r i m e (m) ;
else {
int i ;
f o r ( i=k −1; i >=0; i −−) {
Troca ( i , k −1);
Permuta ( k −1,m) ;
Troca ( i , k −1);
}
}
}
m-1
k
Troca(i,k-1)
...
...
i
...
k-1
m-1
k
Permuta(k-1,m)
...
0
...
i
...
k-1
...
...
i
...
k-1
c
2011
k
70
...
0
k-1
k
m-1
m-1
k
Troca(i,k-1)
0
...
...
0
m-1
I
0
k
I
A função Imprime imprime os m elementos do vetor.
I
Chamada inicial: Permuta(m,m).
m-1
71
c
2011
72
Saı́da de Permuta(2,3)
1
2
1
3
3
2
2
1
3
1
2
3
3
3
2
2
1
1
Exemplos de retrocesso
Desafio: imprimir em ordem lexicográfica:
1
1
2
2
3
3
2
3
1
3
1
2
3
2
3
1
2
1
c
2011
73
Exemplo 1: movimentos do cavalo
-1
2
-2
-1
0
2
1
2
1
3
0
4
7
5
74
Um percurso da posição (0,0) até (4,4) (existem 27.419 soluções).
0
1
2
3
0
1
4
9
12
1
10
13
6
3
2
5
2
11
8
7
14
0
1
Movimentos do cavalo (cont.)
Movimentos possı́veis do cavalo no jogo de xadrez:
-2
c
2011
3
6
c
2011
4
75
c
2011
4
15
76
Um percurso da posição (0,0) até (4,4) cobrindo todas as posições:
0
1
2
3
4
0
1
12
17
6
23
1
18
7
22
11
16
2
13
2
19
24
5
3
8
21
4
15
10
4
3
14
9
20
25
Tipos de solução:
1. Achar uma solução
2. Achar uma solução que cobre todas as posições livres
3. Enumerar todas as soluções
Observação: Esta não é a melhor maneira de resolver este problema mas
ilustra bem o mecanismo geral de retrocesso.
Obs.: Não existe solução para o tabuleiro da transparência anterior
(provar!).
c
2011
77
78
Movimentos do cavalo: achar uma solução
#d e f i n e TAM MAX 20
#d e f i n e NUM MOV 8
t y p e d e f enum { f a l s e , t r u e } B o o l e a n ;
i n t t a b [TAM MAX ] [ TAM MAX ] ;
i n t d l [NUM MOV] = { −1, −2, −2, −1, 1 , 2 ,
i n t dc [NUM MOV] = { 2 , 1 , −1, −2, −2, −1,
v o i d ImprimeTab ( i n t tam ) {
int i , j ;
f o r ( i =0; i <tam ; i ++) {
f o r ( j =0; j <tam ; j ++)
p r i n t f ( ”%5d” , t a b [ i ] [ j ] ) ;
p r i n t f ( ” \n” ) ;
}
}
c
2011
2,
1,
-2
-1
-1
2
-2
};
};
1
2
0
B o o l e a n TentaMovimento ( i n t tam , i n t num , i n t l i n ,
i n t c o l , i n t l d , i n t cd ) {
int k ,
l p , cp ;
Boolean r e s = f a l s e ;
i f ((0<= l i n ) && ( l i n <tam ) && (0<= c o l ) &&
( c o l <tam ) && ( t a b [ l i n ] [ c o l ]==0)) {
t a b [ l i n ] [ c o l ] = num ;
i f ( ( l i n==l d ) && ( c o l==cd ) ) {
r e s = t r u e ; ImprimeTab ( tam ) ;
} else { k = 0;
do { l p = l i n +d l [ k ] ; cp = c o l+dc [ k ] ;
r e s = TentaMovimento ( tam , num+1 , l p , cp , l d , cd ) ;
k++;
} w h i l e ( ( ! r e s ) && ( k<NUM MOV ) ) ;
}
tab [ l i n ] [ c o l ] = 0;
}
return res ;
}
1
2
1
3
0
4
7
0
1
2
5
6
Chamada inicial: TentaMovimento(tam,1,lo,co,ld,cd)
c
2011
79
c
2011
80
Movimentos do cavalo: exemplo de entrada e saı́da
0
0
1
2
3
1
2
3
Movimentos do cavalo: achar uma solução completa
B o o l e a n TentaMovimento ( i n t tam , i n t num , i n t l i n ,
i n t c o l , i n t l d , i n t cd , i n t noc ) {
int k ,
l p , cp ;
Boolean r e s = f a l s e ;
i f ((0<= l i n ) && ( l i n <tam ) && (0<= c o l ) &&
t a b [ l i n ] [ c o l ] = num ;
i f ( ( l i n==l d ) && ( c o l==cd ) && ( ( noc+num)==tam∗tam ) ) {
r e s = t r u e ; ImprimeTab ( tam ) ;
} else { k = 0;
do { l p = l i n +d l [ k ] ;
cp = c o l+dc [ k ] ;
res =
TentaMovimento ( tam , num+1, l p , cp , l d , cd , noc ) ;
k++;
} w h i l e ( ( ! r e s ) && ( k<NUM MOV ) ) ;
}
tab [ l i n ] [ c o l ] = 0;
}
return res ;
}
4
1 4 9 12
10 13 6 3
5 2 11 8
7 14
15
4
Entrada
S aı́ d a
−−−−−−−−−− −−−−−−−−−−−−−−−−−−−−−−−
5
0
4
0
3
4
−1
0
4
4
4
0
−1
1
10
5
0
−1
4
13
2
7
0
c
2011
9
6
11
14
0
12
3
8
0
0
−1
0
0
−1
15
Chamada inicial: TentaMovimento(tam,1,lo,co,ld,cd,ocupadas)
81
Movimentos do cavalo: achar todas as soluções
82
RECURSÃO E RETROCESSO
RCURÇÃO ER RTROCESOS
ˆ ˆ
ˆ ˆ
ˆ ˆ
|
|
|
|
| |
I S
R I
I R
I
Operações elementares:
I
I
I
I
Chamada inicial: TentaMovimento(tam,1,lo,co,ld,cd)
Exemplo 2: distância de edição
v o i d TentaMovimento ( i n t tam , i n t num , i n t l i n ,
i n t c o l , i n t l d , i n t cd ) {
int k ,
l p , cp ;
i f ((0<= l i n ) && ( l i n <tam ) && (0<= c o l ) &&
t a b [ l i n ] [ c o l ] = num ;
i f ( ( l i n==l d ) && ( c o l==cd ) ) {
ImprimeTab ( tam ) ;
} else { k = 0;
do { l p = l i n +d l [ k ] ;
cp = c o l+dc [ k ] ;
TentaMovimento ( tam , num+1, l p , cp , l d , cd ) ;
k++;
} w h i l e ( k<NUM MOV) ;
}
tab [ l i n ] [ c o l ] = 0;
}
}
c
2011
c
2011
83
A: avanço (subentendido)
I: inserção
S: substituição
R: remoção
I
Cada operação recebe um custo (avanço, em geral, zero)
I
Problema: achar uma sequência de operações que torna as cadeias
iguais ao custo total mı́nimo.
c
2011
84
Distância de edição: função Distancia
Distância de edição: desafios
i n t D i s t a n c i a ( char ∗ t e s t e , char ∗ c o r r e t a ) {
i n t d I n s , dRem , dSub ;
i f ( ( ( ∗ t e s t e )==NUL CHAR) && ( ( ∗ c o r r e t a )==NUL CHAR ) )
return 0;
d I n s = dRem = dSub = INT MAX ;
i f ( ( ( ∗ t e s t e )!=NUL CHAR) && ( ( ∗ c o r r e t a )!=NUL CHAR) &&
( ( ∗ t e s t e )==(∗ c o r r e t a ) ) )
r e t u r n D i s t a n c i a ( t e s t e +1 , c o r r e t a +1);
i f ( ( ( ∗ t e s t e )!=NUL CHAR) && ( ( ∗ c o r r e t a )!=NUL CHAR ) )
dSub = c u s t o S u b+D i s t a n c i a ( t e s t e +1 , c o r r e t a +1);
i f ( ( ∗ t e s t e )!=NUL CHAR)
dRem = custoRem+D i s t a n c i a ( t e s t e +1 , c o r r e t a ) ;
i f ( ( ∗ c o r r e t a )!=NUL CHAR)
d I n s = c u s t o I n s+D i s t a n c i a ( t e s t e , c o r r e t a +1);
r e t u r n min ( d I n s , min ( dRem , dSub ) ) ;
}
c
2011
85
I
Melhorar o desempenho do algoritmo: o algoritmo é exponencial não
sendo viável, sob esta forma, em aplicações práticas
I
Imprimir o número de operações de cada tipo (avanço, inserção,
remoção e substituição) para obter a solução
I
Imprimir a sequência de operações para obter a solução
c
2011
86
Esquema de função recursiva
v o i d Exemplo ( T1 x1 , T2 x2 , . . . ) {
S1 y1 ; S2 y2 ; . . . ;
C i ; /∗ Comandos i n i c i a i s ∗/
i f (E ( . . . ) ) {
C0 ;
/∗ Caso b a s e ∗/
} e l s e { /∗ Chamadas r e c u r s i v a s ∗/
C1 ; Exemplo ( e11 , e12 , . . . ) ;
C2 ; Exemplo ( e21 , e22 , . . . ) ;
C3 ; Exemplo ( e31 , e32 , . . . ) ;
...;
Cm; Exemplo ( em1 , em2 , . . . ) ;
Cf ;
}
}
Eliminação da recursão
Os sı́mbolos Ci, C0, C1, . . ., Cm e Cf representam sequências,
possivelmente vazias, de comandos.
c
2011
87
c
2011
88
Esquema de eliminação da recursão
Esquema de eliminação da recursão (cont.)
t y p e d e f enum { chamada1 , chamada2 , chamada3 , . . . } Chamadas ;
t y p e d e f enum { e n t r a d a , s a i d a , r e t o r n o } Acoes ;
S1 y1 ; S2 y2 ; . . . ;
/∗ v a r i á v e i s l o c a i s o r i g i n a i s ∗/
T1 t1 , T2 t2 , . . . ;
/∗ v a r i á v e i s t e m p o r á r i a s ∗/
P i l h a f ; Chamadas ch ; Acoes a c a o ;
I n i c i a l i z a P i l h a (& f ) ; a c a o = e n t r a d a ;
do {
switch ( acao ) {
v o i d Exemplo ( T1 x1 , T2 x2 , . . . )
c a s e ( e n t r a d a ) : . . . break ;
S1 y1 ; S2 y2 ; . . . ;
c a s e ( r e t o r n o ) : . . . break ;
i f (E ( . . . ) ) {
C0 ;
case ( s a i d a ) :
break ;
} else {
}
/∗ Chamadas r e c u r s i v a s ∗/
C1 ;
Exemplo ( e11 , e12 , . . . ) ;
} w h i l e ( a c a o != s a i d a ) ;
C2 ;
Exemplo ( e21 , e22 , . . . ) ;
}
C3 ;
Exemplo ( e31 , e32 , . . . ) ;
{
case ( e n t r a d a ) :
Ci ;
/∗ Comandos i n i c i a i s ∗/
i f (E ( . . . ) ) {
C0 ;
a c a o = r e t o r n o ; /∗ Caso b a s e ∗/
} else {
/∗ P r i m e i r a chamada r e c u r s i v a ∗/
C1 ; E m p i l h a ( f , x1 , x2 , . . . , y1 , y2 , . . . , chamada1 ) ;
t 1 = e11 ; t 2 = e12 ; . . . ;
x1 = t 1 ; x2 = t 2 ;
...;
/∗ R e c a l c u l a a r g u m e n t o s ∗/
}
break ;
S1 y1 ; S2 y2 ; . . . ;
i f (E ( . . . ) ) {
C0 ;
} else {
C1 ;
Exemplo ( e11 , e12 , . . . ) ;
C2 ;
Exemplo ( e21 , e22 , . . . ) ;
C3 ;
Exemplo ( e31 , e32 , . . . ) ;
...;
Cm;
Exemplo ( em1 , em2 , . . . ) ;
Cf ;
}
}
...;
Cm;
Exemplo ( em1 , em2 , . . . ) ;
Cf ;
}
}
c
2011
89
Esquema de eliminação da recursão (cont.)
case ( r e t o r n o ) :
i f ( P i l h a V a z i a ( f ) ) acao = s a i d a ;
else {
D e s e m p i l h a ( f ,& x1 ,& x2 , . . . , & y1 ,& y2 , . . . , & ch ) ;
s w i t c h ( ch ) {
c a s e ( chamada1 ) :
t 1 = e21 ; t 2 = e22 ; . . . ;
x1 = t 1 ; x2 = t 2 ; . . . ;
a c a o = e n t r a d a ; break ;
v o i d Exemplo ( T1 x1 , T2 x2 , . . . )
t 1 = e31 ; t 2 = e32 ; . . . ;
S1 y1 ; S2 y2 ; . . . ;
x1 = t 1 ; x2 = t 2 ; . . . ;
i f (E ( . . . ) ) {
a c a o = e n t r a d a ; break ;
C0 ;
...;
} else {
c a s e ( chamadam ) :
C1 ;
Exemplo ( e11 , e12 , . . . ) ;
C2 ;
Exemplo ( e21 , e22 , . . . ) ;
Cf ; break ;
C3 ;
Exemplo ( e31 , e32 , . . . ) ;
} /∗ s w i t c h ( ch ) ∗/
...;
Cm;
Exemplo ( em1 , em2 , . . . ) ;
}
Cf ;
break ;
}
c
2011
90
92
{
i f ( n==0)
return 1;
else
}
}
c
2011
91
c
2011
Função fatorial (cont.)
t y p e d e f enum { chamada1 } Chamadas ;
i n t res , t1 ;
do {
switch ( acao ) {
c a s e ( e n t r a d a ) : . . . break ;
c a s e ( r e t o r n o ) : . . . break ;
case ( s a i d a ) :
break ;
}
} w h i l e ( a c a o != s a i d a ) ;
return res ;
} /∗ f a t o r i a l ∗/
c
2011
i f ( n==0) {
r e s = 1 ; acao = r e t o r n o ;
} else {
E m p i l h a ( f , n , chamada1 ) ;
t 1 = n ; n = t1 −1;
}
break ;
i f ( n==0)
return 1;
else
}
93
c
2011
94
Exemplo 2: função Hanoi
i f ( P i l h a V a z i a ( f ) ) acao = s a i d a ;
else {
D e s e m p i l h a ( f ,&n ,& ch ) ;
i f ( n==0)
return 1;
else
r e s = n∗ r e s ;
}
break ;
}
break ;
i f ( ! ( n >0))
;
else {
}
}
Obs.: Note como neste caso a variável res é usada para guardar o
resultado da função.
c
2011
i f ( n==0)
return 1;
else
}
95
c
2011
96
Função Hanoi (cont.)
t y p e d e f enum { chamada1 , chamada2 } ;
char t1 ; char t2 ; char t3 ; i n t t4 ;
do {
switch ( acao ) {
c a s e ( e n t r a d a ) : . . . ; break ;
c a s e ( r e t o r n o ) : . . . ; break ;
c a s e ( s a i d a ) : break ;
v o i d Hanoi ( c h a r org , c h a r d e s t , c h a r
}
i f ( ! ( n >0))
;
} w h i l e ( a c a o != s a i d a ) ;
else {
}
i f ( ! ( n >0)) {
acao = r e t o r n o ;
} else {
E m p i l h a ( f , org , d e s t , aux , n , chamada1 ) ;
t 1 = o r g ; t 2 = aux ; t 3 = d e s t ; t 4 = n −1;
o r g = t 1 ; d e s t = t 2 ; aux = t 3 ; n = t 4 ;
}
break ;
aux , i n t n ) {
p r i n t f ( ”Mova de %c p a r a %c\n” , org , d e s t ) ;
}
}
c
2011
97
i f ( ! ( n >0))
;
else {
}
}
c
2011
98
Exemplo de eliminação da recursão caudal
i f ( PilhaVazia ( f ))
acao = s a i d a ;
else {
D e s e m p i l h a ( f ,& org ,& d e s t ,& aux ,&n ,& ch ) ;
E m p i l h a ( f , org , d e s t , aux , n , chamada2 ) ;
t 1 = aux ; t 2 = d e s t ; t 3 = o r g ; t 4 = n −1;
o r g = t 1 ; d e s t = t 2 ; aux = t 3 ; n = t 4 ;
acao = e n t r a d a ;
break ;
c a s e ( chamada2 ) : v o i d Hanoi ( c h a r org , c h a r d e s t , c h a r aux , i n t n ) {
i f ( ! ( n >0))
break ;
;
}
else {
break ;
}
}
c
2011
99
Aplicável quando a última ação dentro do corpo da função é uma
chamada recursiva: reaproveita o mesmo registro de ativação da função,
mudando os valores dos argumentos.
i f ( n>0) {
}
}
char t ;
w h i l e ( n>0) {
t = org ;
o r g = aux ; aux = t ;
}
}
c
2011
100
Exemplo simples de recursão mútua
int g( int n );
Recursão mútua: Análise sintática
c
2011
101
Análise de expressões
int g( int n) {
i f ( n==0)
return 1;
else
r e t u r n f ( n −1);
}
c
2011
102
Programa de tradução de infixa para pós-fixa:
Expressões com operadores binários ‘+’, ‘−’, ‘∗’, ‘/’ e parênteses ‘(’ e ‘)’:
e = t1 ⊕ t2 ⊕ · · · ⊕ tn ,
n≥1
t = f1 ⊗ f2 ⊗ · · · ⊗ fn ,
n≥1
f =x
int f ( int n) {
i f ( n==0)
return 0;
else
r e t u r n g ( n −1);
}
ou
void Expressao ( ) ;
v o i d Termo ( ) ;
void Fator ( ) ;
void InPos () {
pe = &e n t r a d a [ 0 ] ;
Expressao ( ) ;
i f ( ( ∗ pe )!= ’ \0 ’ )
Erro ( ) ;
}
f = (e)
c
2011
c h a r e n t r a d a [TAM MAX ] ;
c h a r ∗ pe ;
103
c
2011
104
Fator
f =x
Termo
ou
f = (e)
t = f1 ⊗ f2 ⊗ · · · ⊗ fn ,
void Fator () {
c h a r c o r r e n t e = ∗ pe ;
switch ( c o r r e n t e ) {
case ’ a ’ :
case ’ b ’ : . . . :
case ’ z ’ :
S a i ( c o r r e n t e ) ; pe++; break ;
case ’ ( ’ :
pe++;
Expressao ( ) ;
i f ( ( ∗ pe)== ’ ) ’ )
pe++;
else
Erro ( ) ;
break ;
default :
Erro ( ) ;
}
}
c
2011
v o i d Termo ( ) {
c h a r op ;
Fator ( ) ;
do {
op = ∗ pe ;
i f ( ( op==’ ∗ ’ ) | | ( op==’ / ’ ) ) {
pe++;
Fator ( ) ;
S a i ( op ) ;
} else
break ; /∗ do ∗/
} while ( true ) ;
}
105
Expressão
e = t1 ⊕ t2 ⊕ · · · ⊕ tn ,
n≥1
c
2011
106
Operador de exponenciação
n≥1
Fator redefinido:
void Expressao () {
c h a r op ;
Termo ( ) ;
do {
op = ∗ pe ;
i f ( ( op==’+ ’ ) | | ( op==’− ’ ) ) {
pe++;
Termo ( ) ;
S a i ( op ) ;
} else
break ; /∗ do ∗/
} while ( true ) ;
}
c
2011
f = p1 ∧ p2 ∧ · · · ∧ pn ,
n≥1
Primário:
p=x
ou
p = (e)
Prioridade? Solução:
f =p
107
ou
f =p∧f
c
2011
108
Fator redefinido
Primário
p=x
f =p
ou
ou
p = (e)
void Primario () {
c o r r e n t e = ∗ pe ;
switch ( c o r r e n t e ) {
case ’ a ’ :
case ’ b ’ : . . . :
case ’ z ’ :
S a i ( c o r r e n t e ) ; pe++; break ;
case ’ ( ’ :
pe++;
Expressao ( ) ;
i f ( ( ∗ pe)== ’ ) ’ )
pe++;
else
Erro ( ) ;
break ;
default :
Erro ( ) ;
}
}
f =p∧f
void Fator () {
Primario ( ) ;
i f ( ( ∗ pe)== ’ ˆ ’ ) {
pe++;
Fator ( ) ;
Sai ( ’ˆ ’ ) ;
}
}
c
2011
109
c
2011
110
Analogia para expressões e termos
e=t
ou
e=e⊕t
t=f
ou
t=t⊗f
Problemas:
I
como distinguir as alternativas
I
repetição infinita no segundo caso (recursão esquerda)
Árvores binárias
void Expressao () {
...;
i f (???)
Termo ( ) ;
else
Expressao ( ) ;
...
}
c
2011
111
c
2011
112
Exemplo de árvore binária 1: pedigree
R. J. B.
Sean
Lakeview
Lois
R. J. B.
Sean
Carina de
Wood Ladge
Ator dos
Seis Irmãos
Exemplo de árvore binária 2: árvore de decisão
Arisca dos
Seis Irmãos
Johnson
Fancy Boots
Lady
Weberly
x1 ≤ x2
V
R. J. B. Hill
R. J. B. Helvetia
Scotland dos Seis Irmãos
Matarazzo’s Beauty
x2 ≤ x3
x2 ≤ x3
V
Carina de Wood Ladge
Jesse James
F
x1 , x2 , x3
V
x1 ≤ x3
V
Sugarted’s Bonnie
I
I
c
2011
113
Exemplo de árvore geral 1: descendentes
Grego
Clássico
Germânico
Germânico
Setentrional
IndoEuropeu
IndoIraniano
Itálico
Hindustano
I
Persa
Latim
Português
Castelhano
Francês
Italiano
Catalão
Eslavo
Polonês
Russo
Checo
Báltico
Lituano
Letão
x2 , x1 , x3
x2 , x3 , x1
A árvore representa as decisões tomadas por um algoritmo de
ordenação usando operações de comparação; V: verdadeiro, F: falso.
I
Devido à natureza das comparações, a árvore é binária.
c
2011
114
Hominidae
Subfamı́lia
Hominini
Gênero
115
Gorillini
Homo
Espécie
Homo
sapiens
Subespécie
Homo sapiens
sapiens
I
Ponginae
Homininae
Tribo
A árvore é incompleta e não necessariamente exata.
Cada elemento pode ter um número variável de sucessores: árvore
geral.
c
2011
x3 , x1 , x2
F
I
I
I
V
Famı́lia
Inglês
Alemão
Holandês
Dinamarquês
Norueguês
Sueco
Hindi
Urdu
Persa
Antigo
BaltoEslavo
x3 , x2 , x1
Exemplo de árvore geral 2: descendentes
Grego Moderno
Germânico
Ocidental
F
x1 ≤ x3
F
x1 , x3 , x2
Alguns nomes são repetidos: eles devem ser tratados como instâncias
separadas.
Pela própria natureza da árvore, cada elemento tem dois
predecessores: árvore binária.
F
Homo
habilis
Homo
neanderthalensis
Pan
...
Chimpanzé
Bonobo
Gorilla
Pongo
Gorila
Orangotango
Árvore da famı́lia Hominidae determinada por comparação de DNA de
várias espécies (incompleta).
Cada elemento pode ter um número variável de sucessores: árvore
geral.
c
2011
116
Exemplo de árvore geral 3: organograma
Definição de árvore binária
UNICAMP
Uma árvore binária é um conjunto de nós que:
IC
DSC
DSI
IMECC
DTC
DE
DM
...
FEEC
DMA
DCA
DEB
...
DT
FCM
DAP
DAN
...
I
ou é vazio (árvore binária vazia)
I
ou contém um nó especial denominado raiz da árvore e o resto do
conjunto está particionado em duas árvores binárias disjuntas
(possivelmente vazias), denominadas subárvore esquerda e subárvore
direita.
DTO
Obs.: A UNICAMP tem 21 unidades acadêmicas. Algumas unidades têm
mais de 10 departamentos.
c
2011
117
Representação gráfica, convenções e conceitos
A
c
2011
C
F
Uma árvore binária com n nós tem:
nı́vel 3
I
H
nı́vel 4
I
I
Raiz da árvore: A
Filho esquerdo de A: B
Pai de F : C
Descendentes de B: B, D, E e G
Folhas: D, G e H
Nı́veis: indicados na figura
Subárvores binárias vazias: 9
120
nı́vel 2
I
G
Fatos sobre árvores binárias
I
E
118
nı́vel 1
B
D
Filho direito de A: C
Irmão de E: D
Antepassados de H: H, F , C e A
Nós internos: todos exceto as folhas
Altura (profundidade) – nı́vel máximo: 4
Subárvores binárias não vazias: 7
I
altura máxima n
altura mı́nima dlog2 (n + 1)e
subárvores vazias: n + 1
subárvores não vazias: n − 1 (se n > 0)
Uma árvore binária de altura h tem:
I
I
no mı́nimo h nós
no máximo 2h − 1 nós
Obs.: Alguns autores começam a numeração dos nı́veis a partir de zero.
c
2011
119
c
2011
Representação ligada comum
Representação ligada com três apontadores
p
p
A
A
B
B
C
D
E
C
D
F
G
E
G
H
H
O terceiro apontador possibilita descer e subir pela estrutura,
analogamente às listas duplamente ligadas.
O acesso a todos os nós da árvore pode ser realizado através de um
apontador para a raiz.
c
2011
F
121
Representação com o campo pai apenas
c
2011
122
Representação seqüencial: árvores binárias completas
A
0
A
B
C
B
I
1
2
C
3
D
E
F
G
J
M
4
5
6
D
E
G
H
K
L
N
O
7
8
9
10
11
12
13
14
H
Problemas:
I
É necessário haver acesso (apontadores) pelo menos a todas as folhas.
I
Não é possı́vel distinguir entre os filhos esquerdos e direitos.
c
2011
F
123

 filho esquerdo: 2n + 1 (n ≥ 0)
filho direito:
2n + 2 (n ≥ 0)
Nó n:

pai:
b(n − 1)/2c (n > 0)
A
B
I
C
F
J
M
D
E
G
H
K
L
N
O
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
c
2011
124
Representação seqüencial: árvores binárias quase completas
Percursos em profundidade
I
Pré-ordem:
Visitar a raiz
Percorrer a subárvore esquerda em pré-ordem
Percorrer a subárvore direita em pré-ordem
I
Pós-ordem:
Percorrer a subárvore esquerda em pós-ordem
Percorrer a subárvore direita em pós-ordem
Visitar a raiz
I
Inordem (ou ordem simétrica):
Percorrer a subárvore esquerda em inordem
Visitar a raiz
Percorrer a subárvore direita em inordem
A
0
B
I
1
2
C
F
J
M
3
4
5
6
D
E
G
H
K
7
8
9
10
11
A
B
I
C
F
J
M
D
E
G
H
K
0
1
2
3
4
5
6
7
8
9
10
11
c
2011
125
Exemplos de percurso em profundidade
c
2011
126
Percurso em largura
Percurso por nı́veis, da esquerda para a direita:
A
A
B
nı́vel 1
C
B
D
E
C
F
D
G
nı́vel 2
E
F
nı́vel 3
H
G
H
nı́vel 4
Pré-ordem: A,B,D,E,G,C,F ,H
Pós-ordem: D,G,E,B,H,F ,C,A
Inordem: D,B,G,E,A,F ,H,C
c
2011
Percurso: A,B,C,D,E,F ,G,H
127
c
2011
128
Implementação recursiva de percursos
t y p e d e f s t r u c t NoArvBin {
T info ;
s t r u c t NoArvBin ∗ esq , ∗ d i r ;
} NoArvBin , ∗ A r v B i n ;
v o i d InOrdem ( A r v B i n p ) {
i f ( p!=NULL) {
InOrdem ( p−>e s q ) ;
Visita (p );
InOrdem ( p−>d i r ) ;
}
} /∗ InOrdem ∗/
Eliminação da recursão caudal
v o i d PreOrdem ( A r v B i n p ) {
i f ( p!=NULL) {
Visita (p );
PreOrdem ( p−>e s q ) ;
PreOrdem ( p−>d i r ) ;
}
} /∗ PreOrdem ∗/
v o i d PosOrdem ( A r v B i n p ) {
i f ( p!=NULL) {
PosOrdem ( p−>e s q ) ;
PosOrdem ( p−>d i r ) ;
Visita (p );
}
} /∗ PosOrdem ∗/
c
2011
129
Percurso em pré-ordem, usando uma pilha explı́cita
i f ( p!=NULL) {
Visita (p );
PreOrdem ( p−>d i r ) ;
}
w h i l e ( p!=NULL) {
Visita (p );
p = p−>d i r ;
}
I
Transformação análoga pode ser feita para a inordem.
I
E a pós-ordem?
c
2011
X
E
Visita X
130
Percurso em pré-ordem, usando uma pilha explı́cita (cont.)
A figura indica a situação inicial e final do percurso de uma árvore
arbitrária (pode ser vazia). Inicialmente, o apontador para a árvore deve
estar no topo da pilha. Terminado o percurso, a pilha terá um elemento a
menos.
c
2011
131
D
Percorre E
c
2011
Percorre D
132
Percurso em pré-ordem, usando uma pilha (cont.)
Percurso em largura, usando uma fila
Os nós da árvore a serem visitados são guardados numa fila.
Pilha pl ;
I n i c i a l i z a P i l h a (& p l ) ;
E m p i l h a (& p l , p ) ;
do {
D e s e m p i l h a (& p l ,&p ) ;
i f ( p!=NULL) {
Visita (p );
E m p i l h a (& p l , p−>d i r ) ;
E m p i l h a (& p l , p−>e s q ) ;
}
} while ( ! PilhaVazia ( pl ) ) ;
c
2011
X
nı́vel k
nı́vel k+1
E
D
Visita X
133
Percurso em largura, usando uma fila (cont.)
c
2011
134
Comparação dos percursos em pré-ordem e em largura
Pilha pl ;
E m p i l h a (& p l , p ) ;
do {
D e s e m p i l h a (& p l ,&p ) ;
i f ( p!=NULL) {
Visita (p );
E m p i l h a (& p l , p−>d i r ) ;
E m p i l h a (& p l , p−>e s q ) ;
}
} while ( ! PilhaVazia ( pl ) ) ;
void Largura ( ArvBin p ) {
Fila fl ;
I n i c i a l i z a F i l a (& f l ) ;
I n s e r e F i l a (& f l , p ) ;
do {
R e m o v e F i l a (& f l ,&p ) ;
i f ( p!=NULL) {
Visita (p );
I n s e r e F i l a (& f l , p−>e s q ) ;
I n s e r e F i l a (& f l , p−>d i r ) ;
}
} while ( ! FilaVazia ( f l ) ) ;
} /∗ L a r g u r a ∗/
void Largura ( ArvBin p ) {
Fila fl ;
I n i c i a l i z a F i l a (& f l ) ;
I n s e r e F i l a (& f l , p ) ;
do {
R e m o v e F i l a (& f l ,&p ) ;
i f ( p!=NULL) {
Visita (p );
I n s e r e F i l a (& f l , p−>e s q ) ;
I n s e r e F i l a (& f l , p−>d i r ) ;
}
} while ( ! FilaVazia ( f l ) ) ;
} /∗ L a r g u r a ∗/
Quase idênticos, exceto a troca de esquerda pela direita!
c
2011
135
c
2011
136
Preordem com pilha otimizada
Pré-ordem com pilha embutida: Deutsch, Schorr e Waite
NULL
Pilha pl ;
Boolean fim = f a l s e ;
do {
i f ( p!=NULL) {
Visita (p );
i f ( p−>d i r !=NULL)
E m p i l h a ( p l , p−>d i r ) ;
p = p−>e s q ;
} else i f ( PilhaVazia ( pl ))
fim = true
else
D e s e m p i l h a ( p l ,&p ) ;
} while ( ! fim ) ;
...
...
...
p
t
...
I
I
I
137
Pré-ordem com pilha embutida (cont.)
... ...
...
A variável p aponta para a subárvore a ser percorrida.
A variável t aponta para o topo de uma pilha formada pelos nós que
levam ao nó p (apontadores invertidos).
Cada nó deverá conter uma marca indicando qual dos dois
apontadores está invertido.
A função seguinte implementa os três percursos em profundidade.
c
2011
138
140
Desafios:
v o i d DSW( A r v B i n p ) {
A r v B i n t = NULL ;
ArvBin q ;
Boolean sobe ;
do {
/∗ à e s q u e r d a ∗/
P r e V i s i t a ( p ) ; p−>marca = MarcaEsq ; q = p−>e s q ;
p−>e s q = t ; t = p ; p = q ;
}
sobe = t r u e ;
w h i l e ( s o b e && ( t !=NULL ) ) {
s w i t c h ( t−>marca ) {
c a s e MarcaEsq :
/∗ à d i r e i t a ∗/
I n V i s i t a ( t ) ; s o b e = f a l s e ; t−>marca = M arc aD ir ;
q = p ; p = t−>d i r ; t−>d i r = t−>e s q ; t−>e s q = q ;
break ;
c a s e M ar c a D i r :
/∗ s o b e ∗/
P o s V i s i t a ( t ) ; q = t−>d i r ; t−>d i r = p ; p = t ; t = q ;
break ;
}
}
} w h i l e ( t !=NULL ) ;
}
c
2011
...
...
I
c
2011
...
139
I
melhorar a pré-ordem com pilha otimizada
I
inordem com pilha otimizada
I
pós-ordem com pilha otimizada
c
2011
Reconstrução de árvores binárias
Reconstrução de árvores binárias (cont.)
A
Pré-ordem AB:
A
B
B
Inordem AB:
A
A
B
B
Pós-ordem AB:
B
A
I
a partir da pré-ordem, determine a raiz da árvore
I
dada a raiz, ela separa a inordem em inordens das suas subárvores
esquerda e direita
I
a partir da pré-ordem, são determinadas as pré-ordens das subárvores
que têm os mesmos comprimentos das respectivas inordens
I
recursivamente são reconstruı́das as subárvores
A
A
Pré-ordem AB e pós-ordem BA:
Verifica-se facilmente que a pré-ordem (ou a pós-ordem) combinada com a
inordem determinam, de maneira única, a forma da árvore. No caso da
pré-ordem e inordem, pode-se seguir o seguinte algoritmo:
B
B
A
B
Conclusão: uma única ordem e a combinação de pré- e pós-ordens não
determinam a árvore de maneira única.
c
2011
O caso da pós-ordem é análogo.
141
c
2011
142
Representações externas de árvores binárias
A
B
I
I
percursos canônicos: inordem e pré (ou pós)
-ordem (já visto):
DBGEAF HC
ABDEGCF H
C
D
E
F
G
H
Árvores binárias de busca
percurso canônico com indicadores de subárvores (pré-ordem):
A11 B11 D00 E10 G00 C10 F01 H00
O ı́ndice 0 indica a ausência e 1 indica a existência de filho esquerdo
ou direito.
I
descrição parentética (inordem):
(((()D())B((()G())E()))A((()F (()H()))C()))
() representa uma árvore vazia; (αXβ) representa uma árvore de raiz
X e subárvores descritas pelas cadeias α e β.
c
2011
143
c
2011
144
Exemplo de árvore de busca: números
Exemplo de árvore de busca: nomes
jul
16
set
fev
8
27
ago
5
15
jan
out
mai
21
abr
10
Para qualquer nó da árvore, os elementos da sua subárvore esquerda
(direita) são menores ou iguais (maiores ou iguais) do que o elemento do
nó.
c
2011
145
Inserção em árvore de busca
mar
Para qualquer nó da árvore, os elementos da sua subárvore esquerda
(direita) precedem (seguem) em ordem alfabética o elemento do nó.
c
2011
146
Inserção recursiva
Y
Y
X <Y
X >Y
Y
Y
B o o l e a n I n s e r e A r v B u s c a ( A r v B i n ∗p , T x ) {
/∗ V e r s ã o r e c u r s i v a ∗/
i f ( ( ∗ p)==NULL) {
∗p = m a l l o c ( s i z e o f ( NoArvBin ) ) ;
( ∗ p)−>e s q = ( ∗ p)−> d i r = NULL ;
( ∗ p)−> i n f o = x ;
return true ;
} else {
T i n f o = ( ∗ p)−> i n f o ;
i f ( xe s q ) , x ) ;
e l s e i f ( x>i n f o )
r e t u r n I n s e r e A r v B u s c a (&((∗ p)−> d i r ) , x ) ;
else
return f a l s e ;
}
}
I
c
2011
jun
nov
A inserção de um valor X cria uma nova folha em lugar de uma subárvore
vazia. O ponto de inserção é determinado pelo percurso da árvore usando
a propriedade de árvores de busca.
X
dez
25
X
I
147
Note-se o uso de passagem de parâmetro p por referência.
Esta versão apresenta somente recursão caudal que pode ser
facilmente eliminada.
c
2011
148
Inserção iterativa
Remoção em árvore de busca
Caso 1: pelo menos uma das subárvores é vazia:
B o o l e a n I n s e r e A r v B u s c a ( A r v B i n ∗p , T x ) {
/∗ V e r s ã o i t e r a t i v a ∗/
T info ;
w h i l e ( ( ∗ p )!=NULL) {
i n f o = ( ∗ p)−> i n f o ;
i f ( xe s q ) ;
e l s e i f ( x>i n f o )
p = &((∗ p)−> d i r ) ;
else
return f a l s e ;
}
∗p = m a l l o c ( s i z e o f ( NoArvBin ) ) ;
( ∗ p)−>e s q = ( ∗ p)−> d i r = NULL ;
( ∗ p)−> i n f o = x ;
return true ;
}
p
X
I
I
I
I
c
2011
149
Remoção em árvore de busca (cont.)
p é o endereço do campo ou da variável que contém o apontador para
o nó com a informação X.
O caso de ambas as subárvores vazias também está coberto.
O caso de subárvore esquerda vazia mas direita não vazia é análogo.
O nó com a informação X pode ser liberado.
c
2011
150
Inserções e remoções em árvores binárias de busca
Caso 2: as duas subárvores são não vazias
I
p
p
Problema: a altura da árvore pode crescer muito já que numa árvore
com n nós:
I
X
X
Y
I
I
Se n ≈ 1.000:
I
I
Y
I
Y
Substituir a informação X por Y – o valor máximo contido na
subárvore esquerda (ou mı́nimo na subárvore direita).
I
I
I
Remover o nó que originalmente continha Y (sua subárvore direita é
vazia – aplica-se o caso 1).
I
Implementação: exercı́cio.
c
2011
151
altura máxima 1.000
altura mı́nima 10
Se n ≈ 1.000.000:
I
I
altura máxima n
altura mı́nima dlog2 (n + 1)e
altura máxima 1.000.000
altura mı́nima 20
O pior caso ocorre, por exemplo, quando a inserção é feita em ordem
(crescente ou descrescente)
c
2011
152
Árvores de altura balanceada (AVL)
Balanceamento de árvores
I
I
Algoritmo óbvio não garante balanceamento
Balanceamento perfeito (altura mı́nima):
I
I
I
eficiência de busca: O(log n)
eficiência de inserção: O(n) – inaceitável
I
Autores: G. M. Adel’son-Vel’skiı̆ e E. M. Landis (1962)
I
Uma árvore binária de busca é do tipo AVL se ela é vazia, ou então,
se para todos os seus nós a diferença de alturas entre as subárvores
esquerda e direita é no máximo 1, em valor absoluto.
I
A diferença entre as alturas direita e esquerda é chamada fator de
balanceamento.
Balanceamento aproximado:
I
I
árvores AVL – eficiência de busca, inserção e remoção: O(log n)
árvores rubro-negras – eficiência de busca, inserção e remoção:
O(log n)
c
2011
153
Exemplos de árvores AVL
c
2011
F0
−
F1
F2
−
0
+
+
0
F3
F4
−
−
−
0
−
0
0
154
Pior caso de desbalanceamento: árvores de Fibonacci
NULL
0
−
0
−
−
0
−
0
0
0
Forma geral – altura h ≥ 2:
Fh
0
−
Note-se que a primeira árvore é de altura mı́nima enquanto que a segunda
não é.
Fh−1
c
2011
155
Fh−2
c
2011
156
Árvores de Fibonacci: propriedades
Inserção em árvores AVL
−
Fh−1
A explicação a seguir supõe que a inserção é realizada por uma função
recursiva cujo cabeçalho é:
Fh−2
I
Para uma dada altura h, a árvore contém o número mı́nimo de nós
possı́vel preservando ainda a propriedade AVL.
I
Qualquer outra árvore AVL com o mesmo número de nós tem altura
menor ou igual – este é o pior caso.
I
Número de nós de Fh : N (h) = N (h − 1) + N (h − 2) + 1,
I
Demonstra-se por indução: N (h) = fh+2 − 1, onde fi é o i-ésimo
número de Fibonacci.
p
p
Usando a aproximação fi ≈ ((1 + (5))/2)i / (5) obtém-se:
h ≈ 1, 44 log2 (n + 2) (no máximo).
I
h≥2
B o o l e a n B u s c a I n s e r e ( ArvAVL ∗p , T x , B o o l e a n ∗ a l t ) ;
onde
I
I
I
I
I
I
Operação de busca usará O(log n) operações.
I
A ser visto: inserção e remoção também usarão O(log n) operações.
p: endereço da variável que contém o apontador para a árvore
x: valor a ser inserido de algum tipo T conveniente
alt: endereço da variável na qual é devolvida a informação que indica
se a árvore aumentou ou não de altura
se não houver aumento de altura numa chamada recursiva, o resto da
árvore não sofre mudança
conforme será visto, o aumento da altura será no máximo de um e
pode acontecer somente numa árvore vazia ou então cuja raiz tem
fator de balanceamento igual a zero; neste caso, o fator resultante
será diferente de zero, exceto quando a árvore era vazia.
O valor devolvido pela função indica se a inserção foi efetivamente
realizada ou se o elemento x já pertencia à arvore.
c
2011
157
Inserção em árvores AVL (cont.)
c
2011
Explicação geral: caso de chamada recursiva com aumento de altura
p
x
α
alt: ?
158
Explicação geral: caso de chamada recursiva sem aumento de altura
p
p
x
?
x
α
alt: ?
p
x
alt: false
h
h
α
Neste caso, haverá modificação no nó corrente com possı́vel propagação
para as chamadas anteriores.
Neste caso, não haverá mais modificações na árvore.
c
2011
alt: true
h+1
h
α
?
159
c
2011
160
Caso 2: Inserção do lado mais baixo:
+
Caso 1: Inserção em árvore vazia:
0
h
0
NULL
+
h
h
X
x
h=0
x
h=1
alt: true
Neste caso a altura h aumenta. Este fato será propagado no retorno da
função através de valor verdadeiro da variável alt.
Nos casos seguintes, será suposto sempre que a inserção foi realizada na
subárvore esquerda; o caso da inserção do lado direito é análogo.
alt: false
O conteúdo do retângulo representa o resultado da chamada recursiva. O
fator de balanceamento será modificado somente se a árvore esquerda
aumentou de tamanho.
Neste caso a altura permanece inalterada. Este fato será propagado no
retorno da função através de valor falso da variável alt. Como
consequência, o processo de inserção pára (exceto os retornos).
c
2011
161
c
2011
162
Caso 4: Inserção do lado mais alto
−
−
Caso 3: Inserção quando as duas alturas são iguais
0
h-1
h
−
0
h+1
h
h+1
x
alt: true
h+1
x
alt: true
x
alt: true
Neste caso, se houve aumento de altura na chamada recursiva, a altura
total também aumentará. Este fato será propagado no retorno da função
através de valor verdadeiro da variável alt.
Neste caso, se houve aumento de altura na chamada recursiva, a árvore
deixará de ser do tipo AVL. Haverá então dois subcasos, dependendo do
lado da subárvore esquerda em que houve inserção. A identificação do
subcaso será feita pelo valor do fator de balanceamento final da subárvore
que aumentou de altura durante a chamada recursiva.
Nos dois casos haverá rearranjos convenientes mas locais da árvore.
c
2011
163
c
2011
164
Caso 4a: inserção do lado esquerdo da subárvore (rotação LL)
Caso 4b: inserção do lado direito da subárvore (rotação LR)
−
−
−
−
A
A
+
−
B
B
h-1
h-1
+0−
h+1
C
h+1
T3
T1 h-1
T2
h-2
h-2 T
1
h-2
x
x
x
T4
h-2
T2 h-2/h-3 T3
x
x
alt: true
alt: true
0
0
C
C
−/0
0
0
B
B
0/+
B
A
h
0
A
h
h-2 T
1
T1 h-1
x
T2
h-2 T
3
h-2
x
h-2/h-3
T2
T3
x
x
T4
h-2
x
alt: false
alt: false
Neste caso é realizada uma transformação denominada rotação simples LL
(esquerda, esquerda). A altura final permanece inalterada e a variável alt
recebe valor falso.
c
2011
Neste caso, a inserção pode ter sido realizada na subárvore esquerda ou
direita do lado que cresceu, ou então no próprio nó C quando h = 2. Os
fatores de balanceamento finais dependem disto, mas o da raiz será 0. A
transformação é denominada rotação dupla LR (esquerda, direita). A
altura final permanece inalterada e a variável alt recebe valor falso.
c
2011
165
Função de inserção em árvores AVL
166
Função de inserção em árvores AVL (cont.)
i f ( ∗ a l t ) { /∗ aumento de a l t u r a ∗/
ArvAVL p1 , p2 ;
s w i t c h ( ( ∗ p)−> b a l ) {
c a s e m a i s : ( ∗ p)−> b a l = z e r o ; ∗ a l t = f a l s e ; break ;
c a s e z e r o : ( ∗ p)−> b a l = menos ; break ;
c a s e menos :
p1 = ( ∗ p)−>e s q ;
i f ( p1−>b a l==menos ) {
/∗ R o t a çã o s i m p l e s LL ∗/
} else {
/∗ R o t a çã o d u p l a LR ∗/
}
p1−>b a l = z e r o ; ∗ a l t = f a l s e ;
break ;
}
}
return true ;
} else {
/∗ d e s c e à d i r e i t a − a n á l o g o ∗/
}
B o o l e a n B u s c a I n s e r e ( ArvAVL ∗p , T x , B o o l e a n ∗ a l t ) {
/∗ D e v o l v e ’ t r u e ’ ou ’ f a l s e ’ c o n f o r m e houve ou não i n s e r ç ã o ;
s e houve i n s e r ç ã o , ’ a l t ’ i n d i c a s e houve aumento da a l t u r a .
∗/
i f ( ∗ p==NULL) {
∗p = m a l l o c ( s i z e o f ( NoArvAVL ) ) ;
( ∗ p)−>e s q = ( ∗ p)−> d i r = NULL ; ( ∗ p)−> i n f o = x ;
( ∗ p)−> b a l = z e r o ; ∗ a l t = t r u e ;
return true ;
} else {
T i n f o = ( ∗ p)−> i n f o ;
i f ( x==i n f o )
return f a l s e ;
e l s e i f ( xe s q ) , x , a l t ) ;
i f (! res )
return f a l s e ;
}
c
2011
167
c
2011
168
Exemplos de inserção em árvores AVL
Exemplos de inserção em árvores AVL (cont.)
Inserção de 33:
Inserção de 63:
−
50
−
50
−
65
+
25
−
20
0
+
35
−
45
0
10
+
55
30
−
65
+
25
−
20
0
70
0
10
0
40
0
0
60
−
45
30
−
20
0
70
0
0
60
+
35
0
60
− 0
45
55
0
10
0
30
70
0
63
0
40
63
40
Neste caso, a inserção causou uma rotação simples do tipo RR, afetando
os nós marcados.
169
c
2011
170
Remoção em árvores AVL
Inserção de 41:
1. Transformação em remoção de uma folha - três casos:
I
−
50
−
50
−
65
+
25
−
20
+
35
+
55
−
45
0
10
+
55
−
65
+
25
0
40
Exemplos de inserção em árvores AVL (cont.)
0
+
35
0
10
Neste caso, houve uma inserção simples e a mudança de fatores de
balanceamento afetou os nós marcados.
c
2011
−
65
−
20
0
0
33
−
50
+
25
70
−
45
+
30
0
60
+
55
0
35
0
33
−
50
30
0
60
−
65
+
25
−
20
70
0
I
0
+
35
0
10
0
0
70
0
30
0
41
60
0
40
I
+
55
0
40
2. Remoção propriamente dita.
45
41
Neste caso, a inserção causou uma rotação dupla do tipo LR, afetando os
nós marcados.
c
2011
o nó tem grau zero: já é uma folha
o nó tem grau um: pela propriedade AVL, a sua única subárvore é
necessariamente constituı́da por uma folha, cujo valor é copiado para o
nó pai; o nó a ser eliminado é a folha da subárvore
o nó tem grau dois: o seu valor é substitı́do pelo maior valor contido na
sua subárvore esquerda (ou o menor valor contido na sua subárvore
direita); o nó que continha o menor (ou maior) valor copiado tem
necessariamente grau zero ou um, recaindo num dos casos anteriores.
171
3. O algoritmo de remoção será apresentado novamente como uma
função recursiva que indica se houve diminuição da altura da árvore
após a remoção. Serão estudados apenas os casos de remoção do
lado esquerdo; os outros são análogos.
4. A implementação do algoritmo é um exercı́cio.
c
2011
172
Remoção em árvores AVL (cont.)
Caso 2: Remoção quando as duas alturas são iguais
0
0
+
Caso 1: Remoção de uma folha
h
h
h
NULL
0
X
x
alt: true
h=0
alt: false
h=1
O conteúdo do retângulo representa o resultado da chamada recursiva. O
fator de balanceamento será modificado somente se a árvore esquerda
diminuiu de tamanho.
Neste caso a altura h diminui. Este fato será propagado no retorno da
função através de valor verdadeiro da variável alt.
Neste caso, mesmo que haja diminuição de altura na chamada recursiva, a
altura total permanece a mesma. Este fato será propagado no retorno da
função através de valor falso da variável alt.
c
2011
173
c
2011
174
Caso 4: Remoção do lado mais baixo
Caso 3: Remoção do lado mais alto
+
−
−
+
0
h
h
h-1
h
x
x
alt: true
alt: true
alt: true
Neste caso, se a chamada recursiva indica diminuição da altura da
subárvore, a altura final da árvore também diminui e o processo continua.
c
2011
h-2
h-1
175
Caso a subárvore esquerda tenha sua altura diminuı́da, a árvore deixa de
ser do tipo AVL. Há três subcasos, dependendo do fator de balanceamento
do filho direito da raiz.
Note-se que, neste caso, tem-se h ≥ 3.
c
2011
176
Caso 4a: Fator de balanceamento 0 (rotação RR)
Caso 4b: Fator de balanceamento +1 (rotação RR)
+
+
+
A
+
A
0
+
B
h
B
h-2
h
T1 h-3
alt: true
h-2
h-2
T2
h-2
h-3
T3
h-3
T2
h-2
T3
−
−
B
B
0
0
B
B
+
0
A
A
h
h-2
h-3
T2
T3
h-3
T1
h-1
h-1
h-2
T3
h-3
T1
T1
alt: true
T2
h-2
alt: true
alt: false
Neste caso é realizada uma transformação denominada rotação simples RR
(direita, direita). A altura final permanece inalterada e a variável alt
recebe valor falso. O processo de ajuste da árvore pára.
c
2011
177
Neste caso também é realizada a transformação denominada
rotação simples RR (direita, direita). A altura final diminui e a variável alt
recebe o valor verdadeiro. O processo de ajuste da árvore continua.
c
2011
178
Exemplos de remoção em árvores AVL
Caso 4c: Fator de balanceamento -1 (rotação RL)
+
Remoção de 40:
+
A
−
B
h
h-2
h-3
T1
−
50
+0−
C
alt: true
T2 h-3/h-4 T3
T4
h-3
0
0
−/0
−
45
30
25
0
−
20
70
0
60
0
+
55
0
35
0
10
0
70
0
30
45
0
60
0
B
40
h-1
h-3/h-4
T2
T3
T1
+
55
−
65
0
0/+
A
h-3
+
35
0
10
C
C
50
−
65
+
25
−
20
0
0
T4
h-3
alt: true
Neste caso também é realizada uma transformação denominada
rotação dupla RL (direita, esquerda). A altura final diminui e a variável
alt recebe o valor verdadeiro. O processo de ajuste da árvore continua.
c
2011
179
Neste caso, houve uma remoção simples e a mudança de fatores de
balanceamento afetou os nós marcados.
c
2011
180
Exemplos de remoção em árvores AVL (cont.)
Remoção de 60:
−
50
0
35
−
65
+
25
−
20
0
+
35
−
45
0
10
+
55
30
−
25
0
−
20
70
0
60
−
45
0
30
0
0
10
Árvores do tipo B
+
50
0
65
0
40
0
55
70
(B trees)
0
40
Neste caso, a remoção causou, após a volta da chamada com a raiz
original, uma rotação dupla do tipo LR, afetando os nós marcados.
c
2011
181
Discos magnéticos
c
2011
Árvores do tipo B
182
Discos magnéticos (cont.)
Esboço esquemático do corte vertical de uma unidade com quatro discos
(oito superfı́cies):
Esboço esquemático de uma superfı́cie de um disco:
0
..
.
1
2
uma trilha
3
um cilindro
(trilhas iguais)
4
5
6
7
cabeças leitoras/gravadoras
setores
c
2011
Árvores do tipo B
183
c
2011
Árvores do tipo B
184
Árvores B
Discos magnéticos (cont.)
Dados para um disco fictı́cio de 40 gigabytes:
I
I
I
10 cabeças leitoras/gravadoras
I
20.000 trilhas (2.000 por superfı́cie)
I
400 setores por trilha
I
512 bytes por setor (unidade mı́nima de endereçamento)
I
tempo médio de busca da trilha endereçada (seek): ∆S
(10 milissegundos)
1. todas as folhas de T têm o mesmo nı́vel;
2. cada nó interno tem um número variável r de registros de informação e
r+1 de filhos, onde

 bb/2c ≤ r ≤ b se nó 6= raiz

tempo médio de latência – espera pelo setor endereçado: ∆L
(10 milissegundos)
I
tempo de transferência de dados: ∆T (60 megabytes/segundo)
I
Estes tempos são várias ordens de grandeza maiores do que tempo de
acesso à memória RAM (tipicamente 100.000 vezes).
I
Número de acessos: altura da árvore – log2 n não é mais aceitável
I
Solução: logk n, com k >> 2
Árvores do tipo B
1≤r≤b
se nó = raiz
3. cada folha tem um número variável r de registros obedecendo à mesma
restrição do item anterior;
4. os campos de informação contidos nos registros obedecem à
propriedade de árvores de busca.
I
c
2011
Autores: Rudolf Bayer e Ed McCreight (1971)
T é uma árvore B de ordem b ≥ 2 se:
I
I
Alguns autores definem de maneira diferente o conceito de ordem.
Pode-se provar que a altura máxima h de uma árvore B de ordem b
que contém n registros é dada por:
logbb/2c (n + 1)/2.
c
2011
185
Árvores do tipo B
186
Exemplo de árvore B de ordem 3
Exemplo de árvore B de ordem 5
Neste caso, cada nó tem no mı́nimo um e no máximo três registros de
informação.
Neste caso, cada nó tem no mı́nimo dois e no máximo cinco registros de
informação.
50
125
7 15 40
17 50 83
3
5
20 35 48
60 70
203
51 80
85
c
2011
150
205
Árvores do tipo B
1
187
2
3
5
10 12 13
20 21 25 30 32 45 46
55 56 57
c
2011
61 62 63
Árvores do tipo B
71 72 75 76 80
188
Números mı́nimos e máximos de registros
Exemplos de inserção
Inserção de 81:
125
Árvore B de ordem 255:
17 50 83
mı́nimo
nı́vel
1
2
3
4
5
Total
nós
1
2
2 × 1281
2 × 1282
2 × 1283
4.227.331
máximo
nós
registros
1
1 × 255
2561
2561 × 255
2562
2562 × 255
3
256
2563 × 255
2564
2564 × 255
4.311.810.305 1.099.511.627.775
registros
1
2 × 127
2 × 1281 × 127
2 × 1282 × 127
2 × 1283 × 127
536.870.911
3
5
20 35 48
203
51 80
85
150
205
125
17 50 83
3
5
20 35 48
203
51 80 81
85
150
205
Neste caso, foi feita inserção numa folha com espaço disponı́vel. Houve h
leituras e uma gravação (h é a altura da árvore). O processo não se
propaga.
c
2011
Árvores do tipo B
189
Exemplos de inserção (cont.)
c
2011
Árvores do tipo B
190
Representação de árvores B
Inserção de 33:
125
#d e f i n e ORDEM 255
17 50 83
203
t y p e d e f s t r u c t NoArvB ∗ ArvB ;
3
20 35 48
5
51 80
85
150
205
t y p e d e f s t r u c t NoArvB {
i n t numregs ;
ArvB f i l h o s [ORDEM+ 1 ] ;
T i n f o [ORDEM ] ;
} NoArvBin ;
50 125
17 35
3
5
20 33
48
83
51 80
203
85
150
205
A capacidade de uma folha seria excedida e foi feita uma quebra que
propagou-se para cima. Haveria no máximo h leituras e 2h+1 gravações
(se a raiz também fosse quebrada).
c
2011
Árvores do tipo B
191
Esta representação será usada para simular árvores B na memória RAM.
Normalmente, árvores B são implementadas em memórias externas como
discos. O endereçamento em discos é usado em lugar de apontadores
comuns.
c
2011
Árvores do tipo B
192
Inserção em árvores B
Inserção em árvores B (cont.)
A explicação a seguir supõe que a inserção é realizada por uma função
recursiva auxiliar cujo cabeçalho é:
Explicação geral: caso de chamada recursiva sem propagação no retorno
B o o l e a n I n s e r e R e c A r v B ( ArvB ∗p , ArvB ∗ s , T ∗x , B o o l e a n ∗ p r o p ) ;
p
x
α
s
?
prop: ?
p
x
?
s
?
prop: false
onde
I
I
I
p: endereço da variável que contém o apontador para a árvore
prop: endereço da variável na qual é devolvida a informação que
indica se houve propagação de inserção no retorno
x: endereço de uma variável
I
I
numa chamada: contém o valor a ser inserido de algum tipo T
conveniente
no retorno, se houver propagação: contém o valor a ser propagado que
separa os valores das árvores apontadas por p e por s
s: endereço da variável que contém o apontador para a árvore
propagada (se houver)
I se não houver propagação numa chamada recursiva, o resto da árvore
não sofre mudança
O valor devolvido pela função indica se a inserção foi efetivamente
realizada ou se o elemento x já pertencia à arvore.
I
c
2011
Árvores do tipo B
193
α
Neste caso, não haverá mais modificações na árvore.
c
2011
Árvores do tipo B
194
Explicação geral: caso de chamada recursiva com propagação no retorno
p
x
α
s
?
prop: ?
Caso 1: árvore vazia
p
x
<
α
x
α
s
p
x
α
s
?
prop: ?
prop: true
s
β
p
>
prop: true
Neste caso, são adotados valores das variáveis x, s e prop de maneira a
recair no caso geral de propagação.
α
Neste caso, a modificação deverá ser propagada para cima. O valor α da
variável x foi inserido numa das duas árvores (ou é o β). Se p apontava
para a raiz da árvore, será necessário criar uma nova raiz, com um único
valor β, e subárvores apontadas por p e s.
c
2011
Árvores do tipo B
195
c
2011
Árvores do tipo B
196
Caso 2: inserção com espaço disponı́vel (r < b)
Caso 3: inserção sem espaço disponı́vel (r = b)
p
p
i−1
0
r −1
i
... xi−1 xi
0
b−1
i−1
b−1
i
... xi−1 xi
...
x
α
s
?
...
xb−1
x
α
s
?
prop: ?
prop: ?
Ti
(inserção recursiva em Ti )
Ti
(inserção recursiva em Ti )
p
i−1
0
r −1
i
... xi−1 xi
p
i−1
0
...
x
r
i
... xi−1 β
xi
b−1
...
x
s
?
?
Árvores do tipo B
197
b−1 b
i
xi
xb−1
...
x
?
s
?
prop: ?
x
?
s
?
prop: ?
(equivalente)
p
0
b−1 b
k
...
...
yk
yb
Tk Tk+1
p
0
k
yk−1
xb−1
x
β
prop: true
s
i−1
b−1 b
i
xi
...
xb−1
x
?
s
?
prop: ?
Neste caso, o valor propagado após a chamada recursiva não pode ser
absorvido pois o nó teria que ser aumentado além da capacidade máxima;
continua com quebra do nó (o espaço extra é apenas conceitual).
c
2011
Árvores do tipo B
198
Função de inserção auxiliar (esboço)
Caso 3: inserção sem espaço disponı́vel – quebra do nó
i−1
...
prop: false
... xi−1 β
0
... xi−1 β
c
2011
0
b−1
i
prop: true
s
β
Neste caso, o valor propagado após a chamada recursiva é absorvido no nó
corrente e a propagação pára.
p
i−1
... xi−1 xi
p
p
0
b−1
Tb+1
b−1
0
x yk
s
b−k
b−1
yk+1
prop: true
Tk
Tk+1
Tb+1
O nó corrente é quebrado em dois; o primeiro (nó original apontado por p)
retém k = db/2e+1 primeiros registros; o k-ésimo elemento e um novo nó
com b−k registros restantes são propagados de volta.
c
2011
Árvores do tipo B
199
B o o l e a n I n s e r e R e c A r v B ( ArvB ∗p , ArvB ∗ s , T ∗x , B o o l e a n ∗ p r o p ) {
int i ;
Boolean i n s e r i u ;
i f ( p==NULL) {
∗ p r o p = t r u e ; ∗ s = NULL ; r e t u r n t r u e ;
}
i = I n d i c e A r v B ( p , x ) ; // l o c a l i z a o p o n t o de i n s e r ç ã o
i f ( ( i <((∗ p)−>numregs ) ) && ( x==((∗p)−> i n f o ) [ i ] ) ) {
∗ prop = f a l s e ; return f a l s e ;
}
i n s e r i u = I n s e r e R e c A r v B (&((∗ p)−> f i l h o s [ i ] ) , s , x , p r o p ) ;
i f (∗ prop ) {
I n s e r e I n f o A r v B ( p , s , x , i ) } ; // i n s e r e ’ s ’ e ’ x ’ no nó
( ( ∗ p)−>numregs )++;
i f ( ( ( ∗ p)−>numregs<=ORDEM) )
∗ prop = f a l s e ;
else {
QuebraNoArvB ( p , s , x ) ; ∗ p r o p = t r u e ; // q u e b r a
}
}
return i n s e r i u ;
}
c
2011
Árvores do tipo B
200
Função de inserção inicial
Exemplos de remoção
Remoção de 51:
125
B o o l e a n I n s e r e A r v B ( ArvB ∗p , T ∗ x ) {
/∗ D e v o l v e ’ f a l s e ’ s e o v a l o r de ’ x ’ j á o c o r r e na á r v o r e ’ p ’ ∗/
Boolean prop ;
ArvB q , s ;
B o o l e a n i n s e r i u = I n s e r e R e c A r v B ( p ,& s , x ,& p r o p ) ;
i f ( prop ) {
q = ( ArvB ) m a l l o c ( s i z e o f ( NoArvB ) ) ;
q−>numregs = 1 ;
( q−> f i l h o s ) [ 0 ] = ∗p ;
( q−> f i l h o s ) [ 1 ] = s ;
( q−>i n f o ) [ 0 ] = ∗ x ;
∗p = q ;
}
return i n s e r i u ;
}
O eventual aumento da altura da árvore se dará sempre nesta função.
17 50 83
3
5
20 35 48
203
51 80
85
150
205
125
17 50 83
3
5
20 35 48
203
80
85
150
205
Neste caso, foi feita remoção numa folha com número de registros acima
do mı́nimo. Houve h leituras e uma gravação (h é a altura da árvore). O
processo não se propaga.
Em todos os casos, a remoção deverá iniciar-se numa folha. Se necessário,
um elemento de um nó interno deverá ser substituı́do convenientemente.
c
2011
Árvores do tipo B
201
c
2011
Exemplos de remoção (cont.)
Exemplos de remoção (cont.)
Remoção de 85:
Remoção de 150:
125
5
20 35 48
203
51 80
85
150
17 50 83
205
3
5
20 35 48
203
51 80
125
5
20 35 48
203
51
83
150
150
17 50
205
3
Neste caso, foi feita remoção numa folha com número mı́nimo de
registros, e foi feito um “empréstimo” de um nó irmão imediato com sobra
de registros. O empréstimo passa pelo nó pai a fim de manter a
propriedade de árvore de busca. Haveria no máximo h + 2 leituras e três
gravações. O processo não se propaga.
c
2011
85
205
83
17 50 80
3
202
125
17 50 83
3
Árvores do tipo B
Árvores do tipo B
203
5
20 35 48
125
51 80
85
203 205
Neste caso, foi feita remoção numa folha com número mı́nimo de registros
e cujos irmãos também estão no mı́nimo. Foi feita então uma junção de
dois nós e incluı́do o valor do nó pai que os separa. A remoção deste valor
do nó pai seguirá o mesmo esquema de remoções, e poderá se propagar
até a raiz. Haveria no máximo 3h − 2 leituras e 2h − 1 gravações.
c
2011
Árvores do tipo B
204
Observações
I
I
I
I
I
I
I
Variantes de árvores B
Verifica-se facilmente que tanto no caso de quebras (inserção) como
no caso de junções (remoção), os nós resultantes preservam as
propriedades de árvores B.
O número de leituras e gravações é sempre proporcional à altura da
árvore.
O nó raiz da árvore é normalmente guardado na memória, diminuindo
o número de acessos ao disco.
De acordo com a definição das árvores B, a utlização mı́nima do
espaço dos nós é de cerca de 50%; pode-se provar que a utilização
média é de cerca de 69%.
Usando técnicas probabilı́sticas, pode-se mostrar que as operações
mais complicadas são muito infrequentes.
A remoção pode ser implementada de maneira análoga à inserção e
será deixada para exercı́cio.
Uma árvore B inicial pode ser construı́da por inserções sucessivas o
que seria muito ineficiente; na prática, utiliza-se um algoritmo direto.
c
2011
Árvores do tipo B
205
I
Árvores B∗ : o número de registros ocupados de um nó é no mı́nimo
da sua capacidade.
I
Árvores B+ :
I
I
I
nós internos com chaves apenas para orientar o percurso
pares (chave, valor) apenas nas folhas
regra de descida:
I
I
I
I
subárvore esquerda: menor
subárvore direita: maior ou igual
apontadores em lugar de valores tornando mais eficiente a
movimentação dos registros durante inserções e remoções
ligações facilitando percurso em ordem de chaves
c
2011
Árvores do tipo B
206
Variantes de árvores B (cont.)
Exemplo de árvore B+ de ordem 3:
23
4
6
8
11
15
11
12
Filas de prioridade
26
14
15
18
20
23
25
26
29
(Priority queues)
35
Setas tracejadas indicam apontadores para os valores da informação. A
lista ligada das folhas permite percurso simples e eficiente em ordem de
chaves.
c
2011
Árvores do tipo B
207
c
2011
Filas de prioridade
208
2
3
Definição e propriedades
I
Exemplo
Uma fila de prioridade é uma árvore binária com as propriedades:
I
I
a árvore é completa ou quase completa;
em cada nó da árvore, o valor da chave é maior ou igual aos valores
das chaves dos filhos (e consequentemente, de todos os descendentes).
I
Uma fila de prioridade não é uma árvore de busca!
I
A determinação do elemento máximo de uma fila de prioridade pode
ser feita em tempo constante (está na raiz).
I
As operações de inserção e de remoção podem ser realizadas em
tempo proporcional à altura (O(log n)).
I
I
95
0
88
1
75
2
30
3
45
4
15
7
10
8
40
5
38
6
23
9
Implementação sequencial (heap):
Filas de prioridade podem ser implementadas eficientemente de
maneira sequencial.
95
88
75
30
45
40
38
15
10
23
0
1
2
3
4
5
6
7
8
9
Em algumas aplicações é conveniente utilizar filas de prioridade em
que um elemento é menor ou igual a todos os seus descendentes.
c
2011
Filas de prioridade
209
c
2011
Filas de prioridade
210
Operação de subida
Operação de descida
Supondo que, exceto pelo último elemento, a árvore é uma fila de
prioridade, a operação torna a árvore inteira uma fila válida.
Supondo que, exceto por um único valor que não é maior ou igual do que
seus descendentes, a árvore é uma fila de prioridade, a operação torna a
árvore inteira uma fila válida.
95
0
95
0
88
1
75
2
30
3
15
7
45
4
10
8
23
9
40
5
90
10
95
0
90
1
38
6
75
2
30
3
15
7
88
4
10
8
23
9
40
5
13
1
38
6
45
10
15
7
88
4
10
8
23
9
40
5
88
1
38
6
75
2
30
3
15
7
23
4
10
8
40
5
38
6
13
9
Setas duplas indicam as operações de troca a serem realizadas.
Obviamente, o número de operações de troca executadas é, no máximo,
igual à altura da árvore original (log2 n).
Filas de prioridade
75
2
30
3
Setas duplas indicam as operações de troca a serem realizadas.
c
2011
95
0
211
Obviamente, o número de operações de troca executadas é menor do que
a altura da árvore original (log2 n).
c
2011
Filas de prioridade
212
Implementação das operações
#d e f i n e TAM MAX 50
typedef struct {
T v e t o r [TAM MAX ] ;
i n t tam ;
} Heap ;
Implementação das operações (cont.)
v o i d Sobe ( Heap ∗h , i n t m) {
i n t j = (m−1)/2;
T x = ( ∗ h ) . v e t o r [m ] ;
w h i l e ( (m>0) && ( ( ∗ h ) . v e t o r [ j ]< x ) ) {
( ∗ h ) . v e t o r [m] = ( ∗ h ) . v e t o r [ j ] ;
m = j;
j = ( j −1)/2;
}
( ∗ h ) . v e t o r [m] = x ;
} /∗ Sobe ∗/
Note-se que as operações de troca foram otimizadas com a utilização da
variável temporária x.
v o i d Desce ( Heap ∗h , i n t m) {
i n t k = 2∗m+1;
T x = ( ∗ h ) . v e t o r [m ] ;
w h i l e ( k <(∗h ) . tam ) {
i f ( ( k <((∗ h ) . tam ) −1) && ( ( ∗ h ) . v e t o r [ k ] <(∗ h ) . v e t o r [ k + 1 ] ) )
k++;
i f ( x <(∗h ) . v e t o r [ k ] ) {
( ∗ h ) . v e t o r [m] = ( ∗ h ) . v e t o r [ k ] ;
m = k;
k = 2∗ k +1;
} else
break ;
}
( ∗ h ) . v e t o r [m] = x ;
} /∗ Desce ∗/
Também neste caso, as operações de troca foram otimizadas.
c
2011
Filas de prioridade
213
Construção inicial
Filas de prioridade
214
Inserção e remoção
Dado um vetor com elementos em ordem arbitrária, deve-se transformá-lo
numa fila de prioridade:
v o i d C o n s t r o i H e a p 1 ( Heap ∗h ) {
int i ;
f o r ( i =1; i <(∗h ) . tam ; i ++)
Sobe ( h , i ) ;
} /∗ C o n s t r o i H e a p 1 ∗/
Note-se que a função RemoveHeap remove e devolve na variável x o
elemento máximo da fila. Obviamente, as duas funções realizam no
máximo O(n log n) operações.
Verifica-se facilmente que a eficiência da função ConstroiHeap1 é
O(n log n). Pode-se demonstrar, também, que a eficiência de
ConstroiHeap2 é O(n) (linear).
Filas de prioridade
v o i d I n s e r e H e a p ( Heap ∗h , T x ) {
v e t o r [ ( ∗ h ) . tam ] = x ;
( ( ∗ h ) . tam)++;
Sobe ( h , ( ( ∗ h ) . tam ) −1);
} /∗ I n s e r e H e a p ∗/
v o i d RemoveHeap ( Heap ∗h , T ∗ x ) {
∗x = (∗ h ) . v e t o r [ 0 ] ;
( ( ∗ h ) . tam)−−;
(∗ h ) . v e t o r [ 0 ] =
( ∗ h ) . v e t o r [ ( ∗ h ) . tam ] ;
Desce ( h , 0 ) ;
} /∗ RemoveHeap ∗/
v o i d C o n s t r o i H e a p 2 ( Heap ∗h ) {
int i ;
f o r ( i =((∗ h ) . tam −2)/2; i >=0; i −−)
Desce ( h , i ) ;
} /∗ C o n s t r o i H e a p 2 ∗/
c
2011
c
2011
215
c
2011
Filas de prioridade
216
Algoritmo de ordenação Heapsort
O algoritmo constrói um heap inicial. Em seguida, remove um a um o
elemento máximo e o coloca na posição final do vetor.
v o i d H e a p S o r t ( Heap ∗h ) {
i n t i , n = ( ∗ h ) . tam ;
/∗ c o n s t r ó i heap ∗/
f o r ( i =(n −2)/2; i >=0; i −−)
Desce ( h , i ) ;
/∗ o r d e n a ∗/
f o r ( i=n −1; i >0; i −−) {
T t = (∗ h ) . v e t o r [ 0 ] ;
(∗ h ) . v e t o r [ 0 ] = (∗ h ) . v e t o r [ i ] ;
(∗ h ) . v e t o r [ i ] = t ;
( ∗ h ) . tam−−;
Desce ( h , 0 ) ;
}
( ∗ h ) . tam = n ;
} /∗ H e a p S o r t ∗/
Árvores gerais
Número de operações: O(n log n) (um dos algoritmos ótimos).
c
2011
Filas de prioridade
217
Exemplo de árvore geral
c
2011
Árvores gerais
218
Representação de árvores gerais
A
B
F
C
G
H
D
#d e f i n e GRAU MAX 10
typedef struct
NoArvGeral ∗ ArvGeral ;
typedef s t r u c t NoArvGeral {
T info ;
i n t grau ;
A r v G e r a l f i l h o s [ GRAU MAX ] ;
} NoArvGeral ;
E
I
J
K
L
I
árvores gerais nunca são vazias
I
as subárvores são ordenadas: primeira, segunda, etc
I
o número de subárvores pode ser qualquer, inclusive zero
I
conceitos naturais: grau, filhos, pai, descendente, altura, etc
c
2011
Árvores gerais
...
...
p = malloc ( s i z e o f ( NoArvGeral ) ) ;
p = m a l l o c ( s i z e o f ( N o A r v G e r a l )+
( grau −1)∗ s i z e o f ( A r v G e r a l ) ) ;
...
...
219
typedef struct
NoArvGeral ∗ ArvGeral ;
typedef s t r u c t NoArvGeral {
T info ;
i n t grau ;
ArvGeral f i l h o s [ 1 ] ;
} NoArvGeral ;
c
2011
Árvores gerais
220
Florestas
Floresta representada como árvore binária
Uma floresta é uma sequência, possivelmente vazia, de árvores gerais.
A
B
C
Exemplo:
D
A
D
J
E
K
B
F
L
G
M
J
C
H
E
K
F
L
G
H
M
I
N
O
Q
I
N
O
P
P
Q
I
o campo esquerdo aponta para a raiz da primeira subárvore original
I
o campo direito aponta para o nó irmão seguinte
I
as raı́zes das árvores da floresta são consideradas irmãs.
Note-se que as subárvores de um nó de uma árvore geral constituem uma
floresta.
c
2011
Árvores gerais
221
Floresta representada como árvore binária (cont.)
c
2011
Árvores gerais
222
Percursos em profundidade de florestas
Os percursos de uma floresta F = (T1 , T2 , . . . , Tm ) são definidos por:
I
A árvore binária B(F ) que representa uma floresta
F = (T1 , T2 , . . . , Tm ) é definida por:
I
I
árvore binária vazia se F é uma floresta vazia (m = 0);
árvore binária cuja raiz contém a mesma informação da raiz de T1 ; cuja
subárvore esquerda é dada por B((T11 , T12 , . . . , T1m1 )) onde
(T11 , T12 , . . . , T1m1 ) é a floresta das subárvores de T1 ; e cuja subárvore
direita é dada por B((T2 , . . . , Tm )).
I
Conclui-se facilmente que toda floresta tem uma única representação
binária.
I
A implementação de árvores binárias é mais simples.
I
Exercı́cio: definir a transformação contrária F(T ) que obtém a
floresta a partir da árvore binária T que a representa.
I
Exercı́cio: verificar se toda árvore binária representa uma floresta.
c
2011
Árvores gerais
223
I
Pré-ordem de florestas:
Visitar a raiz de T1
Percorrer a floresta F1 em pré-ordem de florestas
Percorrer a floresta (T2 , . . . , Tm ) em pré-ordem de
florestas
I
Pós-ordem de florestas:
Percorrer a floresta F1 em pós-ordem de florestas
Percorrer a floresta (T2 , . . . , Tm ) em pós-ordem de
florestas
I
Inordem de florestas:
Percorrer a floresta F1 em inordem de florestas
Percorrer a floresta (T2 , . . . , Tm ) em inordem de florestas
c
2011
Árvores gerais
224
Percursos em profundidade de florestas (cont.)
A
B
Percursos em profundidade de florestas (cont.)
C
Propriedades:
D
J
E
K
F
L
G
M
H
I
N
O
P
I
percurso de uma floresta F produz o mesmo resultado que o percurso
(binário) correspondente da árvore B(F ).
I
pré-ordem de florestas é semelhante à pré-ordem de árvores binárias
I
inordem de florestas é semelhante à pós-ordem de árvores binárias
I
pós-ordem de florestas não tem uma interpretação natural
Q
Desafio:
Pré-ordem: A,D,J,E,K,L,F ,G,M ,B,C,H,I,N ,O,Q,P
Elabore um algoritmo para percurso em largura de árvores gerais sob
representação binária.
Pós-ordem: J,L,K,M ,G,F ,E,D,Q,P ,O,N ,I,H,C,B,A
Inordem: J,D,K,L,E,F ,M ,G,A,B,H,N ,Q,O,P ,I,C
c
2011
Árvores gerais
225
c
2011
Árvores gerais
226
Árvores digitais
228
Conjuntos de cadeias de caracteres
Exemplo:
Árvores digitais
a
an
and
are
as
(Tries)
c
2011
Árvores digitais
227
at
be
but
by
for
from
had
have
he
her
his
i
in
is
it
c
2011
no
not
of
on
or
a
an
and
are
as
Árvore digital
a
b
f
n
i
h
at
be
but
by
for
from
had
have
he
her
his
i
in
is
it
no
not
of
on
or
Implementação de árvores digitais
o
a
b
y
c
z
...
n
r
s
e
t
e
d
u y
o r
r
t
a
o
e
d v
m
n
i
r
s
o
t
s
f
n r
t
I
I
e
Algoritmos de busca, inserção e remoção óbvios (exercı́cio).
Uso de memória:
I
Arestas são rotuladas com as letras das palavras.
Nós cheios indicam o fim de uma cadeia.
São fatorados os prefixos comuns das cadeias.
Números para o exemplo:
I
I
I
I
I
I
I
I
39
20
19
25
I
I
I
I
c
2011
Árvores digitais
Árvore digital com subcadeias
Eliminando apontadores das folhas:
I
nós
folhas
nós internos (não folhas)
nós cheios (25 palavras)
a
an
and
are
as
at
be
but
by
for
from
had
have
he
her
19 × 26 = 494 campos apontadores
38 campos são não nulos
Existem alternativas mais econômicas para representar os nós.
c
2011
229
his
i
in
is
it
Árvores digitais
Autômato finito minimal acı́clico
no
not
of
on
or
Exemplo: as 15 formas dos verbos ingleses: do, redo e undo
d
d
a
b
f
n
i
h
230
do
does
did
doing
done
o
redo
redoes
redid
redoing
redone
undo
undoes
undid
undoing
undone
r
e
u
n
s
d
i
e
o
i
g
n
n
e
n
r
s
re
e
t
s
s
e
u y
ut
o r
y
or
a
d
n
i
rom
is
d v
d
e
d
r
ve r
n
s
t
s
o
f
t
f
n r
n
r
I
I
t
I
t
I
São fatorados tanto os prefixos quanto os sufixos comuns das cadeias.
Algoritmo de busca igual ao de árvores digitais.
Algoritmos de inserção e de remoção muito mais complicados.
Uso de memória:
I
I
I
Uso de memória:
I
I
I
c
2011
Se fosse árvore digital:
I
I
I
Árvores digitais
231
11 × 26 = 286 campos apontadores (nós internos)
26 × 26 = 676 campos apontadores (nós internos)
37 campos seriam não nulos
As estruturas para um exemplo análogo em português seriam maiores
(mais de 50 formas verbais) mas resultariam em muito mais economia.
c
2011
Árvores digitais
232
Conceito e exemplos
I
I
Um átomo é um inteiro ou uma cadeia de caracteres.
Uma lista generalizada é uma sequência:
(α1 , α2 , . . . , αn )
I
I
I
c
2011
233
Expansão de listas
onde αi denota um átomo ou uma lista generalizada (definição
recursiva).
Exemplos de listas:
A: ((4,7),(4,7,(8)))
B: ((1,4),(7,8))
C: (3,B,B)
D: (5,8,D)
E: ()
As listas A, B, C, D e E têm, respectivamente, 2, 2, 3, 3 e 0
elementos.
A definição de átomo poderia ser estendida para outros tipos de
valores.
c
2011
Implementação compartilhada
A:
B:
C:
D:
E:
((4,7),(4,7,(8)))
((1,4),(7,8))
(3,B,B)
(5,8,D)
()
A:
4
4
A:
B:
C:
D:
E:
234
((4,7),(4,7,(8)))
((1,4),(7,8))
(3,B,B)
(5,8,D)
()
7
7
8
As listas C e D podem ser expandidas com as definições correspondentes:
B:
C: (3,((1,4),(7,8)),((1,4),(7,8)))
D: (5,8,(5,8,(5,8,(...))))
1
A lista D tem três elementos, mas inclui um número infinito de inteiros,
por ser recursiva.
c
2011
7
235
C:
3
D:
5
E:
NULL
8
4
8
c
2011
236
A:
B:
C:
D:
E:
Implementação com cópia
((4,7),(4,7,(8)))
((1,4),(7,8))
(3,B,B)
(5,8,D)
()
Representação de listas generalizadas
3
7
B:
1
C:
7
1
5
8
4
7
1
4
5
8
8
4
typedef struct RegListaGen ∗ ListaGen ;
8
typedef struct RegListaGen {
ListaGen prox ;
B o o l e a n eAtomo ;
union {
i n t atomo ;
/∗ ’ eAtomo ’ v e r d a d e i r o ∗/
ListaGen l i s t a ;
/∗ ’ eAtomo ’ f a l s o ∗/
} info ;
} RegListaGen ;
8
5
8
D:
...
I
Não é possı́vel completar a expansão da lista D.
I
As representações das listas A, B e E não mudam.
c
2011
237
Exemplo de manipulação
c
2011
238
Representação alternativa
Função de contagem de átomos:
i n t ContaAtomos ( L i s t a G e n p ) {
int s = 0;
i f ( p−>eAtomo )
s ++;
else
s += ContaAtomos ( p−>i n f o . l i s t a ) ;
p = p−>p r o x ;
}
return s ;
} /∗ ContaAtomos ∗/
typedef struct RegListaGen ∗ ListaGen ;
typedef struct RegListaGen {
B o o l e a n v i s i t a d o ; /∗ i n i c i a l m e n t e f a l s o ∗/
ListaGen prox ;
B o o l e a n eAtomo ;
union {
i n t atomo ;
/∗ ’ eAtomo ’ v e r d a d e i r o ∗/
L i s t a G e n l i s t a ; /∗ ’ eAtomo ’ f a l s o ∗/
} info ;
} RegListaGen ;
Problemas com compartilhamento:
I
contagem repetida (caso da lista C ); pode ser intencional
I
repetição infinita (caso da lista D)
c
2011
239
c
2011
240
Exemplo de manipulação
Exemplo de aplicação
Função geral de contagem de átomos:
Manipulação de polinômios em múltiplas variáveis:
P (x, y, z) = x10 y 3 z 2 + 2x8 y 3 z 2 + 3x8 y 2 z 2 + x4 y 4 z − 6x3 y 4 z + 2yz
i n t ContaAtomos ( L i s t a G e n p ) {
int s = 0;
w h i l e ( ( p!=NULL) && ! ( p−>v i s i t a d o ) ) {
p−>v i s i t a d o = t r u e ;
i f ( p−>eAtomo )
s ++;
else
s += ContaAtomos ( p−>i n f o . l i s t a ) ;
p = p−>p r o x ;
}
return s ;
} /∗ ContaAtomos ∗/
Representação possı́vel para cada termo:
coef
Problema: restauração dos valores do campo visitado para o próximo
percurso.
c
2011
Representação de polinômios
y
x
I
Problema: muito inflexı́vel, somente para polinômios em três variáveis.
I
Alternativa: um polinômio em k ≥ 1 variáveis pode ser considerado
um polinômio em uma variável, com coeficientes que são polinômios
em k−1 variáveis, etc:
P (x, y, z) = ((x10 + 2x8 )y 3 + 3x8 y 2 )z 2 + ((x4 − 6x3 )y 4 + 2x0 y)z
241
((x10 + 2x8 )y 3 + 3x8 y 2 )z 2 + ((x4 − 6x3 )y 4 + 2x0 y)z
c
2011
Alternativa 2: representação que elimina polinômios “degenerados”
z
y
4
2
1
1
y
x
x
1
4
2
3
x
−6 3
y
x
1
4
x
3
8
10
2
8
2
1
x
3
8
10
2
8
2
4
0
x
y
242
((x10 + 2x8 )y 3 + 3x8 y 2 )z 2 + ((x4 − 6x3 )y 4 + 2x0 y)z
1
2
Representação de polinômios (cont.)
Alternativa 1: representação uniforme em todos os nı́veis:
z
z
3
x
1
2
0
−6 3
2
1
2x0 y
Note-se que o termo
é representado de maneira completa. Esta
representação torna os algoritmos mais simples.
c
2011
Note-se que o termo 2x0 y é representado como 2y. Esta representação
economiza memória (retângulo tracejado).
243
c
2011
244
Declaração de tipo
LISP: uma linguagem para processamento de listas
t y p e d e f s t r u c t Termo ∗ApTermo ;
t y p e d e f ApTermo P o l i n o m i o ;
t y p e d e f s t r u c t Termo {
Polinomio prox ;
B o o l e a n eCabeca ;
union {
char v a r i a v e l ;
/∗ s e é c a b e ç a ∗/
struct {
/∗ s e é termo ∗/
int expoente ;
Boolean c o e f I n t e i r o ;
union {
int coefInt ;
Polinomio coefPolin ;
} coef ;
} termo ;
} no ;
} Termo ;
I
Programas são expressos como listas.
I
Dados são átomos e listas.
Aplicações:
I
I
I
I
I
inteligência artificial
scripts para Emacs
scripts para AutoCAD
...
Exercı́cio: escrever as funções de soma e de multiplicação para polinômios
em múltiplas variáveis.
c
2011
245
LISP (cont.)
c
2011
246
LISP (cont.)
Exemplo 2: concatenação e inversão de listas
( defun c o n c a t ( p q )
( cond ( n u l l p )
q
( cons ( c a r p ) ( c o n c a t ( c d r p ) q ) )
)
)
( defun f a t o r i a l ( n )
( cond ( l e q n 1 )
1
( mult n ( f a t o r i a l ( minus n 1 ) ) )
)
)
( defun i n v e r t e ( p )
( cond ( n u l l p )
nil
( concat ( i n v e r t e ( cdr p )) ( car p ))
)
)
I
A expressão: (fatorial 5) produz: 120.
I
Deve-se notar o uso de notação pré-fixa.
I
As implementações comuns de LISP permitem o uso de sı́mbolos de
operações como <=, + e ∗ em lugar de átomos.
I
I
I
I
c
2011
247
A expressão: (inverte ’(A B C D)) produz D C B A.
A expressão (car L) devolve o primeiro elemento da lista L.
A expressão (cdr L) devolve a lista L sem o primeiro elemento.
A operação (cons x L) devolve a lista L com o elemento x inserido
na frente da lista.
c
2011
248
Tabelas de espalhamento
Exemplo de tabela com b = 7 linhas e s = 3 colunas:
1
Espalhamento
f (’jo~
ao’) →
(Hashing ou scattering)
0
1
2
3
4
5
6
2
3
jo~
ao
Supõe-se, neste caso, que:
c
2011
Espalhamento
249
Tabelas de espalhamento (cont.)
I
a função de espalhamento f produz resultados entre 0 e 6
I
f (’jo~
ao’) = 3
I
existem no máximo três valores (s) a serem inseridos que produzem o
mesmo valor da função f .
c
2011
Espalhamento
250
Virtudes e poblemas
Exemplo de tabela com b = 26 linhas e s = 2 colunas:
0
1
2
3
4
5
1
ant^
onio
2
átila
I
I
carlos
douglas
ernesto
I
célio
est^
ev~
ao
I
simplicidade
busca muito rápida (se a função de espalhamento for eficiente)
Problemas
I
···
24
25
Virtudes
I
I
escolha da função de espalhamento
tratamento de colisões
tratamento de estouro da tabela
zoroastro
Foi usada uma função (muito ingênua!) de espalhamento: ı́ndice da
primeira letra (a: 0, b: 1, ...).
c
2011
Espalhamento
251
c
2011
Espalhamento
252
Construção de funções de espalhamento
Construção de funções de espalhamento (cont.)
Divisão
I
O nome, tratado como um número na base 26, é dividido por um
número p relativamente primo f (x) = x mod p; p será adotado como
o número de linhas da tabela.
I
Para p = 51 terı́amos:
Propriedades desejáveis:
I
I
I
I
eficiência de cálculo
bom espalhamento
Técnicas:
I
I
f (carlos) = ( ((((2 × 26 + 0) × 26 + 17) × 26 + 11)
espalhamento mı́nimo perfeito
espalhamento pseudo-aleatório: combinação de várias técnicas
×26 + 14) × 26 + 18 ) mod 51
= 24.069.362 mod 51 = 14
I
c
2011
Espalhamento
253
Na realidade, o cálculo pode ser simplificado, com a operação mod
aplicada a cada passo.
c
2011
Espalhamento
254
Dobramento (folding)
Seleção de algarismos e meio-do-quadrado
I
O nome é tratado como uma sequência de algarismos ou de bytes ou
de bits, e uma subsequência é selecionada para representar o ı́ndice.
I
Por exemplo, suponhamos que todos os nomes são representados
como a sequência de dı́gitos x = d0 d1 · · · d11 em alguma base
conveniente; uma escolha seria f (x) = d3 d5 d9 .
I
Exemplo: a representação de ‘carlos’ poderia ser 020017111418.
Supusemos que cada letra é indicada por dois dı́gitos que indicam a
posição no alfabeto, ou seja 00 para ‘a’, 01 para ‘b’, etc. Terı́amos
então f (carlos) = 074.
I
Frequentemente, antes de fazer a seleção, é calculado o quadrado do
identificador (tratado como número); é o método
“meio-do-quadrado” (mid-square).
c
2011
Espalhamento
255
I
O nome é tratado como uma sequência de algarismos ou de bytes ou
de bits, e algumas subsequências são combinadas por operações
convenientes para produzir um ı́ndice.
I
Por exemplo, suponhamos que todos os nomes são representados
como uma sequência de bits x = b0 b1 b2 b3 b4 · · · ; uma escolha seria:
f (x) = b0 b1 b2 b3 b4 b5 ⊕ b6 b7 b8 b9 b10 b11 ⊕ · · ·
onde ⊕ denota a operação de ou exclusivo bit a bit.
I
Exemplo: a representação de ‘carlos’ usada anteriormente poderia
ser (com cinco bits para cada número):
00010 00000 10001 01011 01110 10010
produzindo a sequencia de bits: 000100000010001010110111010010 e
o resultado:
f (000100000010001010110111010010) =
000100 ⊕ 000010 ⊕ 001010 ⊕ 110111 ⊕ 010010 = 101001 = 4110
c
2011
Espalhamento
256
Tratamento de colisões: endereçamento aberto
Reespalhamento linear
ant^
onio, carlos, douglas, célio, armando, zoroastro, átila, alfredo
Usando (f (x) + i) mod b, (i = 0, 1, · · · ), procura a primeira posição livre.
I
Busca sistemática de outras entradas disponı́veis na tabela:
I
I
I
0
1
2
3
4
5
6
7
···
25
reespalhamento linear
reespalhamento quadrático
reespalhamento duplo
I
Em todos os casos, os algoritmos de busca, inserção e remoção
deverão ser coerentes.
I
Exemplos usam: ant^
onio, carlos, douglas, célio, armando,
zoroastro, átila, alfredo (nesta ordem).
c
2011
Espalhamento
257
ant^
onio
armando
carlos
douglas
célio
átila
alfredo
···
zoroastro
c
2011
Espalhamento
258
Reespalhamento quadrático
Reespalhamento duplo
ant^
ant^
Usando (f (x) + i2 ) mod b, (i = 0, 1, · · · ), procura a primeira posição livre.
I
0
1
2
3
4
5
6
7
8
9
···
25
ant^
onio
armando
carlos
douglas
átila
I
célio
alfredo
···
zoroastro
c
2011
Espalhamento
259
Usando (f (x) + i × g(x)) mod b, (i = 0, 1, · · · ) procura a primeira
posição livre.
0
ant^
onio
g(x) é a função de reespalhamento;
1
por exemplo, g(x) = (c mod 3) + 1
2
carlos
onde c é a segunda letra.
3
douglas
4
célio
5
6
armando
7
8
átila
9
alfredo
···
···
25 zoroastro
c
2011
Espalhamento
260
Remoção
I
Lápides (tombstones):
I
I
I
Eficiência com endereçamento aberto
entradas que indicam posições ocupadas para fins de busca, mas livres
para fins de inserção.
podem ser usadas com qualquer esquema de espalhamento
I
C(n) = (2 − α)/(2 − 2α)
onde:
Exemplo: remoção da entrada armando (tabela com reespalhamento
linear):
0
1
2
3
4
5
6
7
···
25
ant^
onio
armando
carlos
douglas
célio
átila
alfredo
···
zoroastro
0
1
2
3
4
5
6
7
···
25
c
2011
Número médio de comparações para encontrar um elemento:
I
I
I
ant^
onio
++++++++
carlos
douglas
célio
átila
alfredo
I
Exemplo de tabela com 1000 entradas:
···
zoroastro
Espalhamento
261
Tratamento de colisões: listas ligadas
c
2011
I
armando
antônio
antônio
I
I
carlos
célio
douglas
3
carlos
I
5
...
zoroastro
As listas poderiam ser ordenadas.
c
2011
α = n/b (fator de carga, α > 0)
n é o número de entradas
b é o tamanho da tabela
Exemplo de tabela com 1000 entradas:
n
100
200
400
500
1000
2000
4
25
262
onde:
1
2
Espalhamento
Número médio de comparações para encontrar um elemento:
I
armando
antônio
átila
C(n)
1,06
1,13
1,21
1,33
1,50
1,75
2,17
3,00
5,50
10,5
C(n) = 1 + α/2
Exemplo:
ant^
armando
antônio
alfredo
átila
n
100
200
300
400
500
600
700
800
900
950
Eficiência com encadeamento
Técnica de encadeamento (chaining): utiliza listas ligadas para manter
entradas com o mesmo valor da função de espalhamento.
0
α = n/b (fator de carga, 0 ≤ α ≤ 1)
n é o número de entradas
b é o tamanho da tabela
Espalhamento
263
C(n)
1,05
1,10
1,20
1,25
1,50
2,00
c
2011
Espalhamento
264
Compressão de textos
I
I
I
(Codificação de Huffman)
c
2011
Objetivos:
265
economia de espaço
velocidade de transmissão
I
Representação normal: um byte (8 bits) por caractere (alfabetos
“comuns”)
I
Compressão por contagem (run-length encoding)
I
Codificação de Huffman
I
Algoritmos de codificação aritmética (Lempel-Ziv – zip, gzip, winzip,
et.)
c
2011
266
Árvores binárias de codificação
Codificação de Huffman
Codificação fixa
a: 000
b: 001
c: 010
d: 011
e: 100
f: 101
100
I
Explora frequências de ocorrência de caracteres
I
Exemplo de alfabeto: A = {a, b, c, d, e, f }
frequência de cada letra
codificação usando 3 bits
codificação de tamanho variável
I
a
45
000
0
b
13
001
101
0
86
c
12
010
100
d
16
011
111
e
9
100
1101
f
5
101
1100
Para um arquivo de 100.000 caracteres:
I
I
codificação fixa: 300.000 bits
codificação variável: 224.000 bits (economia de 25%)
c
2011
1
267
14
0
1
1
0
58
0
a:45
0
28
b:13
c:12
14
1
d:16
0
e:9
1
f:5
I
Os rótulos das arestas da raiz até uma folha compõem o código da
letra correspondente.
I
Para obter o código de uma letra, é necessário percorrer a árvore
partindo da folha correspondente até a raiz.
I
Exemplo: abc = 000k001k010 = 000001010.
c
2011
268
Árvores binárias de codificação (cont.)
Codificação variável
a: 0
b: 101
c: 100
Construção da árvore de Huffman
d: 111
e: 1101
f: 1100
I
100
0
1. Construa uma floresta de folhas, cada uma correspondendo a um
caractere, com a respectiva frequência como seu peso.
2. Enquanto a floresta tiver mais de uma árvore, repita:
1
a:45
55
0
1
25
0
Algoritmo (guloso):
I
I
30
1
0
1
I
c:12
14
b:13
0
d:16
1
I
A solução não é única (pode haver várias escolhas de peso mı́nimo),
mas todos os resultados são equivalentes quanto à eficiência de
compressão.
I
Se o alfabeto for razoavelmente grande, pode-se utilizar uma fila de
prioridade para selecionar, em cada passo, duas árvores de menor
peso.
e:9
f:5
procure na floresta duas árvores t1 e t2 de menor peso
construa uma nova árvore binária t, com subárvores t1 e t2 , e com peso
que é a soma dos pesos das duas subárvores
remova t1 e t2 da floresta, e insira t.
I
O código de uma letra não pode constituir um prefixo de uma outra
letra.
I
Exemplo: abc = 0k101k100 = 0101100.
c
2011
269
Construção da árvore de Huffman (cont.)
c
2011
270
Exemplo:
a:45
c:12
b:13
e:9
d:16
a:45
f:5
14
d:16
f:5
a:45
b:13
c:12
a:45
e:9
14
b:13
30
14
b:13
d:16
25
f:5
f:5
c:12
25
c:12
d:16
e:9
14
d:16
f:5
a:45
25
e:9
c
2011
c:12
e:9
b:13
271
c
2011
272
a:45
25
c:12
30
14
b:13
d:16
a:45
100
55
0
f:5
25
c:12
a:45
1
e:9
a:45
30
14
b:13
55
0
f:5
25
e:9
1
1
0
25
d:16
55
0
c:12
30
14
b:13
0
30
f:5
c:12
14
b:13
f:5
1
d:16
1
e:9
d:16
e:9
c
2011
273
c
2011
274
Observações
I
Adotadas certas hipóteses, demonstra-se a otimalidade de compressão
I
Algoritmo de compressão: para cada letra, deve acessar a folha
correspondente da árvore e reconstruir o caminho à raiz – pode ser
preprocessado
I
Algoritmo de descompressão: percorre a árvore a partir da raiz
seguindo o caminho indicado por bits da codificação
Variantes:
I
I
I
I
árvore fixa, por exemplo, uma para cada lı́ngua
árvore por texto (acompanha o arquivo)
árvores dinâmicas (Faller, Gallager e Knuth).
c
2011
275
c
2011
276
Gerenciamento explı́cito
Configuração genérica da memória:
Vários aspectos:
disp
I
alocação com e sem disciplina de pilha
I
caracterı́sticas da linguagem de programação
I
registros de tamanho fixo ou variável
I
gerenciamento explı́cito (malloc e free)
I
gerenciamento implı́cito (coleta de lixo e contagem de referências)
I
gerenciamento misto
Livre:
m
M
disp
I
I
I
277
A variável disp (memória disponı́vel) é global.
A lista das áreas livres é ordenada pelo valor dos apontadores.
M denota o tamanho da área livre inicial; m de uma área livre ou em
uso.
A função de alocação devolve o apontador para o primeiro byte livre
da área.
c
2011
Gerenciamento explı́cito (cont.)
Uma versão muito simples de malloc(n) (f é o tamanho da parte fixa de
cada área – apontador mais o campo de tamanho):
Uma versão muito simples de free(p):
1. procure na lista disp o primeiro elemento (ou o elemento de tamanho
mı́nimo) p com tamanho≥ n+f
2. remova p da lista disp
3. quebre a área apontada por p em duas partes: uma p1 de tamanho
n + f e outra p2 com o que sobrar (se houver sobra suficiente)
4. insira p2 na lista disp (se existir)
278
1. procure na lista disp o ponto de inserção para p (ordem crescente dos
apontadores)
2. verifique se o predecessor e/ou sucessor de p neste ponto são
adjacentes à área apontada por p
3. se for possı́vel, junte a área liberada à predecessora e/ou à sucessora,
modificando os campos de tamanho
4. atualize a lista
5. devolva p1 + f
c
2011
?
Configuração inicial:
I
c
2011
Em uso:
m
279
c
2011
280
Marcas de fronteira
Livre:
Problemas:
Em uso:
t
m
t
f
m
f
I
O que fazer quando malloc não acha uma área de tamano suficiente –
requer outra área ao sistema operacional
I
Fragmentação – após várias alocações e liberações, com tamanhos
variáveis, haverá tendência a produzir muitas área livres pequenas
I
As áreas livres constituem uma lista duplamente ligada.
I
m denota o tamanho da área.
I
Busca numa lista ligada pode ser ineficiente
Algumas soluções:
I
t e f denotam os valores booleanos que indicam se a área é livre.
I
da área.
I
Não é necessário fazer uma busca na lista para encontrar as áreas
vizinhas.
I
Exercı́cio: esboçar a implementação das funções malloc e free.
I
I
I
blocos com marcas de fronteira (boundary tags)
sistema de blocos conjugados (buddy system)
c
2011
281
Sistema de blocos conjugados
I
8-15
0-1
k=3
0-3
k=2
4-7
0-1
k=1
2-3
6-7
8-9
12-15
10-11
12-13
Em uso:
I
k=0
0
I
I
I
I
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Uma árvore binária imaginária em que cada nó representa um bloco
de alocação.
Cada folha da árvore representa um bloco mı́nimo de alocação.
Cada nı́vel k da árvore (a partir das folhas) representa a alocação de
uma área constituı́da de 2k blocos mı́nimos.
Áreas conjugadas (irmãs) facilmente reconhecidos pelos ı́ndices sob
forma binária.
O exemplo exibe a árvore para uma memória de 24 = 16 blocos.
c
2011
t
k
f
k
14-15
I
I
282
Formato das áreas:
Livre:
8-11
4-5
Sistema de blocos conjugados (cont.)
0-15
k=4
c
2011
283
I
I
I
t e f denotam os valores booleanos que indicam se a área é livre.
k indica que o tamanho da área é 2k .
Para cada valor de k, existe uma lista duplamente ligada disp[k] de
blocos livres de tamanho 2k .
da área.
Dado o número do bloco inicial de uma área (em binário) de tamanho
2k , o número da área conjugada é determinado complementando o
k-ésimo bit (a partir da direita); exemplo de bloco 12 para k = 2:
1210 = 11002 =⇒ 10002 = 810
Portanto, a área conjugada de quatro blocos tem inı́cio no bloco 8.
c
2011
284
Esboço da função malloc(n) (f é o tamanho da parte fixa de cada área –
marca de uso, tamanho):
Esboço da função free(p):
1. procure um k tal que 2k ≥ n + f , e a lista de blocos para k não está
vazia; remova desta lista uma área p
2. se 2k−1 ≥ n + f , quebre a área p em duas (conjugadas), acerte os
tamanhos e insira uma delas na lista de áreas para tamanho k − 1
1. seja k o expoente correspondente ao tamanho de p
2. calcule o endereço da área q conjugada de p
3. se a área q está livre:
I
I
3. repita o passo anterior para k − 2, k − 3, ..., enquanto possı́vel
I
I
4. devolva o apontador p + f
Note-se que o desperdı́cio de memória de uma área pode chegar a quase
50%.
c
2011
285
remova q da lista disp[k]
junte as áreas p e q para formar uma nova área livre p
faça k = k+1
volte ao passo inicial
4. se a área q não está livre (ou não existe – p já é a memória inteira),
insira p na lista disp[k]
c
2011
286
Gerenciamento implı́cito
Uma outra alternativa é utilizar os números de Fibonacci:
0-12
Coleta de lixo (garbage collection)
F7 = 13
F6 = 8
I
0-7
Caracterı́sticas:
I
F5 = 5
I
8-12
0-4
I
F4 = 3
0-2
5-7
8-10
I
I
F3 = 2
0-1
3-4
5-6
8-9
11-12
I
Fases:
I
I
F2 = 1
0
I
I
1
2
3
4
5
6
7
8
9
10
11
12
Esta solução diminui o desperdı́cio de memória, mas torna mais
complicados os algoritmos.
Exercı́cio: esboçar as funções malloc e free para esta alternativa.
c
2011
287
operação de alocação implı́cita em algumas operações
não existe operação de liberação explı́cita ou é opcional
liberação de memória realizada, em geral, quando não há mais espaço
para alocar
exemplos: Java, LISP, Prolog, Perl, Python, Modula-3, ...
contra-exemplos: C, Pascal, C++, ...
I
marcação
coleta ou compactação
caso haja compactação: cálculo de destino; atualização dos
apontadores; cópia dos blocos
c
2011
288
Marcação e coleta
Marcação e coleta (cont.)
Exemplo de situação inicial:
I
Hipóteses
I
I
I
I
I
I
I
I
Localização conhecida das variáveis apontadoras na pilha de execução.
Localização conhecida de apontadores em cada bloco.
Blocos de tamanho fixo ou com campos de comprimento.
Marcas de utilização em cada bloco, inicialmente falsas.
f
supõe blocos iguais
setas mais fortes: apontadores nas variáveis na pilha de execução
blocos acessı́veis a serem marcados marcados em cor cinza
f
f
f
f
f
f
f
f
f
f
f
t
f
t
f
t
t
f
t
t
f
f
f
f
f
f
f
f
f
Após a marcação:
Algoritmo:
I
I
Percurso análogo à pré-ordem e marcação a partir das variáveis na
pilha.
Percurso linear da memória para coleta de blocos livres e restauração
das marcas.
f
t
t
Após a coleta:
f
f
f
disp
c
2011
289
I
I
I
290
Hipóteses simplificadoras:
I
c
2011
Função de marcação:
tamanho fixo de registros
localização conhecida dos apontadores (um vetor)
v o i d Marcar ( ApBloco p ) {
int i ;
i f ( p!=NULL) {
i f ( ! p−>marca ) {
p−>marca = t r u e ;
f o r ( i =0; i <p−>numAps ; i ++)
Marcar ( p−>a p o n t s [ i ] ) ;
}
}
} / ∗ Marcar ∗/
Declarações:
t y p e d e f s t r u c t B l o c o ∗ ApBloco ;
typedef s t r u c t Bloco {
B o o l e a n marca ;
ApBloco d e s t i n o ; /∗ s e h o u v e r compactação ∗/
. . .
i n t numAps ;
ApBloco a p o n t s [ NUM MAX APONTS ] ;
} Bloco ;
ApBloco d i s p ; /∗ i n i c i a l m e n t e t o d o s o s b l o c o s ∗/
B l o c o memoria [ TAM MEM DIN ] ;
c
2011
A função Marcar deve ser chamada para cada variável apontadora na pilha
de execução.
291
c
2011
292
Marcação e compactação
Função de coleta:
I
Hipóteses
I
void Coletar () {
int i ;
d i s p = NULL ;
f o r ( i =0; i <TAM MEM DIN ; i ++)
i f ( memoria [ i ] . marca ) /∗ em u s o ∗/
memoria [ i ] . marca = f a l s e ;
e l s e { /∗ i n s e r e na l i s t a d i s p o nı́ v e l ∗/
memoria [ i ] . a p o n t s [ 0 ] = d i s p ;
d i s p = &(memoria [ i ] ) ;
}
} /∗ C o l e t a r ∗/
c
2011
I
I
I
I
Algoritmo:
I
I
I
I
Localização conhecida das variáveis apontadoras na pilha de execução.
Localização conhecida de apontadores em cada bloco.
Blocos de tamanho fixo ou com campos de comprimento.
Marcas de utilização em cada bloco, inicialmente falsas.
Percurso análogo à pré-ordem e marcação a partir das variáveis na
pilha.
Cálculo dos novos endereços dos blocos.
Atualização dos campos apontadores.
Compactação (cópia).
c
2011
293
Marcação e compactação (cont.)
Exemplo de situação inicial:
Após o cálculo dos novos endereços (tracejados):
supõe blocos iguais
setas mais fortes: apontadores nas variáveis na pilha de execução
I blocos acessı́veis a serem marcados marcados em cor cinza
294
I
I
f
t
t
t
f
t
f
t
t
f
t
t
Após a atualização dos apontadores, inclusive os da pilha:
f
f
f
f
f
f
f
f
f
f
f
f
f
Após a marcação:
f
t
t
t
f
t
f
t
t
f
t
t
t
t
f
t
f
t
t
f
t
t
f
f
f
Após a compactação:
t
disp
Após o cálculo dos novos endereços (tracejados):
f
f
t
t
t
f
t
f
t
t
f
t
f
f
f
f
f
f
f
f
t
A variável disp aponta para o inı́cio da área contı́gua liberada pela
operação de compactação (não é necessário usar uma lista ligada).
c
2011
295
c
2011
296
I
São adotadas as mesmas hipóteses do caso de marcação e coleta.
I
A função marcar é a mesma.
I
Função de cálculo dos novos endereços:
Função de atualização dos apontadores:
void A t u a l i z a () {
int i , j = 0;
i f ( memoria [ i ] . marca )
f o r ( j =0; j <memoria [ i ] . numAps ; j ++) {
memoria [ i ] . a p o n t s [ j ] =
( memoria [ i ] . a p o n t s [ j ])−> d e s t i n o ;
}
} /∗ A t u a l i z a ∗/
void C a l c u l a r D e s t i n o () {
int i , j = 0;
i f ( memoria [ i ] . marca ) {
memoria [ i ] . d e s t i n o = &(memoria [ j ] ) ;
j ++;
}
d i s p = &(memoria [ j ] ) ; /∗ p r i m e i r o b l o c o l i v r e ∗/
} /∗ C a l c u l a r D e s t i n o ∗/
c
2011
Devem ser atualizadas também todas as variáveis apontadoras na pilha de
execução.
297
298
Contagem de referências
Função de compactação:
v o i d Move ( ) {
int i ;
i f ( memoria [ i ] . marca ) {
memoria [ i ] . marca = f a l s e ;
∗ ( memoria [ i ] . d e s t i n o ) = memoria [ i ] ;
}
} /∗ Move ∗/
Adaptação para blocos de tamanho variável: introduzir o campo tamanho
em cada bloco e adaptar as funções.
c
2011
c
2011
299
I
As técnicas de coleta de lixo (marcação e coleta ou compactação)
encontram e liberam toda a memória disponı́vel de uma vez.
I
O processo pode ser bastante demorado, com tempo de execução
proporcional ao tamanho total da memória dinâmica.
I
A execução da coleta de lixo interrompe o processo em curso; esta
interrupção pode demorar mais do que seria aceitável am algumas
aplicações.
I
Dependendo da complexidade das estruturas de dados criadas pelo
programa, a fase de marcação pode exigir memória adicional
apreciável para manter a pilha de execução.
I
A técnica de contagem de referências tem a caracterı́stica de, em
geral, distribuir o tempo de gerenciamento de memória ao longo da
execução normal do programa.
c
2011
300
Contagem de referências (cont.)
I
Contagem de referências (cont.)
Cada bloco alocado possui um campo inteiro refs contendo o número de
variáveis (normais ou dinâmicas) que apontam para o bloco.
I
Durante a alocação de um bloco, o seu campo refs recebe o valor inicial 1.
I
Toda variável ou campo apontador, antes de ser atribuı́do, recebe o valor
NULL.
I
I
I
I
I
I
I
v o i d A t r i b u i A p o n t ( ApBloco ∗p ,
ApBloco q ) {
i f ( q!=NULL) ( q−>r e f s )++;
i f ( ( ∗ p )!=NULL) {
( ( ∗ p)−> r e f s )−−;
i f ( ( ( ∗ p)−> r e f s )==0)
DesalocaRefs (∗ p ) ;
}
∗p = q ;
}
c
2011
301
desaloca o bloco apontado por p
decrementa os contadores dos blocos referidos em p
caso algum destes contadores torne-se nulo, a função é chamada
recursivamente
Problemas:
I
Todo comando de atribuição que envolve apontadores é implementado pela
função AtrbuiApont(ApBloco *p, ApBloco q):
t y p e d e f s t r u c t B l o c o ∗ ApBloco ;
typedef s t r u c t Bloco {
int refs ;
. . .
i n t numAps ;
ApBloco
a p o n t s [ NUM MAX APONTS ] ;
} Bloco ;
A função DesalocaRefs(p):
dependendo das estruturas de dados, o tempo de execução de comando
de atribuição entre apontadores é imprevisı́vel devido à recurisividade
da função DesalocaRefs
o método, como exposto, não funciona para estruturas com
circularidades; exemplo:
2
1
1
1
1
1
1
1
p
após a atribuição p = NULL:
1
1
p
Os nós da lista não seriam liberados. Alguns sistemas utilizam um
esquema misto: contagem de referências e coleta de lixo.
c
2011
302
Tipos abstratos de dados
I
I
I
Abstração de Dados e Objetos
typedef void ∗ Figura ;
Figura Retangulo ( f l o a t alt , f l o a t l a r g ) ;
Figura Circulo ( float raio ) ;
F i g u r a Quadrado ( f l o a t l a d o ) ;
f l o a t Area ( F i g u r a f i g ) ;
v o i d T r a n s l a d a r ( F i g u r a f i g , f l o a t dx , f l o a t dy ) ;
void Desenhar ( Figura f i g ) ;
I
I
c
2011
Um tipo abstrato de dados (TAD) é constituı́do por um conjunto de
valores e um conjunto de operações sobre estes valores.
Os valores possuem uma representação e podem ser muito simples
(inteiros, bytes, ...) ou bastante complexos (pilhas, árvores, ...).
Exemplo de especificação de um TAD Figura através de declarações
em C:
303
A espoecificação de um tipo como “void ∗” é uma técnica comum
em C para “esconder” a implementação.
Normalmente, estas declarações, chamadas às vezes de interface ou
API (Application Programming Interface) estariam num arquivo
denominado figuras.h.
c
2011
304
Tipos abstratos de dados (cont.)
I
I
Usando a especificação, é possı́vel escrever programas que utilizam o
TAD, mesmo sem completar a sua implementação.
Exemplo de utilização do TAD Figura:
I
I
t y p e d e f enum { RETANGULO, CIRCULO , QUADRADO } F o r m a F i g u r a ;
#i n c l u d e ” f i g u r a s . h”
i n t main ( ) {
Figura c = Circulo (10.0);
Figura r = Retangulo (10.0 , 2 0 . 0 ) ;
F i g u r a q = Quadrado ( 5 0 . 0 ) ;
Transladar ( r , 5 . 0 , 8 . 0 ) ;
Desenhar ( q ) ;
p r i n t f ( ”%f \n” , Area ( c ) ) ;
p r i n t f ( ”%f \n” , Area ( r ) ) ;
p r i n t f ( ”%f \n” , Area ( q ) ) ;
return 0;
} /∗ main ∗/
I
I
typedef struct {
F o r m a F i g u r a f orma ;
f l o a t posx , p o s y ;
union {
struct {
float alt , larg ;
} lados ;
float raio ;
} dados ;
} RegFigura , ∗ Figura ;
As funções Circulo, Retangulo e Quadrado devem construir e devolver
as representações dos valores correspondentes (construtores).
A função main poderia estar num arquivo denominado main.c.
c
2011
305
I
I
Figura
?
?
forma posx
posy
lados
Retangulo
0
forma posx
Circulo
posy
alt
posy
raio
larg
1
?
forma posx
lados
Quadrado
2
forma posx
posy
alt
larg
Deve-se notar a diferença entre os tipos Figura e Figura.
Normalmente, estas declarações (e as seguintes) estariam num
arquivo figuras.c.
c
2011
306
Declarações dos construtores:
Figura Retangulo ( f l o a t alt ,
float larg ) {
Figura f =
malloc ( sizeof ( RegFigura ) ) ;
f −>forma = RETANGULO ;
f −>p o s x = 0 . 0 ;
f −>p o s y = 0 . 0 ;
f −>d a d o s . l a d o s . a l t = a l t ;
f −>d a d o s . l a d o s . l a r g = l a r g ;
return f ;
} /∗ R e t a n g u l o ∗/
A implementação de um TAD depende de vários fatores, mas deve
seguir sempre a sua especificação.
Exemplo de declarações “naturais” para implementar o TAD Figura:
Declarações das funções:
Figura Circulo ( float raio ) {
Figura f =
f −>forma = CIRCULO ;
f −>p o s x = 0 . 0 ;
f −>p o s y = 0 . 0 ;
f −>d a d o s . r a i o = r a i o ;
return f ;
} /∗ C i r c u l o ∗/
F i g u r a Quadrado ( f l o a t l a d o ) {
Figura f =
Retangulo ( lado , lado ) ;
f −>forma = QUADRADO;
return f ;
} /∗ Quadrado ∗/
c
2011
307
f l o a t Area ( F i g u r a f i g ) {
Figura f = fig ;
s w i t c h ( f −>forma ) {
c a s e RETANGULO :
c a s e QUADRADO:
r e t u r n ( f −>d a d o s . l a d o s . a l t ) ∗
( f −>d a d o s . l a d o s . l a r g ) ;
c a s e CIRCULO :
r e t u r n PI ∗ ( f −>d a d o s . r a i o ) ∗
( f −>d a d o s . r a i o ) ;
default :
e x i t ( 1 ) ; /∗ I m p o s sı́ v e l ∗/
}
} /∗ Area ∗/
void Transladar ( Figura f ig ,
f l o a t dx ,
f l o a t dy ) {
Figura f = fig ;
f −>p o s x += dx ;
f −>p o s y += dy ;
} /∗ T r a n s l a d a r ∗/
void Desenhar ( Figura f ) {
/∗ Não f o i i m p l e m e n t a d a ∗/
} /∗ D e s e n h a r ∗/
c
2011
308
I
I
I
I
Nesta implementação do TAD Figura, a estrutura de dados que
implementa o tipo e as funções são implementadas separadamente.
É possı́vel mudar a implementação de maneira que as funções passem
fazer parte da própria estrutura de dados – uma caracterı́stica de
objetos; neste caso são denominados métodos.
Nesta nova implementação do exemplo, por simplicidade, a técnica
será aplicada somente à função Area, mas poderia ser estendida às
outras funções.
Trata-se de uma nova implementação da mesma interface;
consequentemente os arquivos figuras.h (repetido abaixo) e
main.c permanecem iguais.
typedef void ∗ Figura ;
Figura Retangulo ( f l o a t alt , f l o a t l a r g ) ;
Figura Circulo ( float raio ) ;
F i g u r a Quadrado ( f l o a t l a d o ) ;
f l o a t Area ( F i g u r a f i g ) ;
v o i d T r a n s l a d a r ( F i g u r a f i g , f l o a t dx , f l o a t dy ) ;
void Desenhar ( Figura f i g ) ;
c
2011
309
Declaração de Figura com um método:
t y p e d e f f l o a t f u n c A r e a ( F i g u r a ) ; /∗ t i p o f u n ç ã o ∗/
t y p e d e f enum { RETANGULO, CIRCULO , QUADRADO } F o r m a F i g u r a ;
typedef struct {
F o r m a F i g u r a forma ;
f u n c A r e a ∗ Area ;
/∗ a p o n t a d o r p a r a f u n ç ã o ∗/
union {
struct { float alt , larg ; } lados ;
float raio ;
} dados ;
} RegFigura , ∗ Figura ;
c
2011
310
Declarações dos construtores:
Funções do tipo funcArea:
Figura Retangulo ( f l o a t alt ,
float larg ) {
Figura f =
f −>forma = RETANGULO ;
f −>p o s x = 0 . 0 ;
f −>p o s y = 0 . 0 ;
f −>Area = A r e a R e t a n g u l o ;
f −>d a d o s . l a d o s . a l t = a l t ;
f −>d a d o s . l a d o s . l a r g = l a r g ;
return f ;
} /∗ R e t a n g u l o ∗/
f l o a t AreaRetangulo ( Figura f i g ) {
Figura f = fig ;
r e t u r n ( f −>d a d o s . l a d o s . a l t ) ∗ ( f −>d a d o s . l a d o s . l a r g ) ;
} /∗ A r e a R e t a n g u l o ∗/
float AreaCirculo ( Figura f i g ) {
Figura f = fig ;
r e t u r n PI ∗ ( f −>d a d o s . r a i o ) ∗ ( f −>d a d o s . r a i o ) ;
} /∗ A r e a C i r c u l o ∗/
c
2011
311
Figura Circulo ( float raio ) {
Figura f =
f −>forma = CIRCULO ;
f −>p o s x = 0 . 0 ;
f −>p o s y = 0 . 0 ;
f −>Area = A r e a C i r c u l o ;
f −>d a d o s . r a i o = r a i o ;
return f ;
} /∗ C i r c u l o ∗/
F i g u r a Quadrado ( f l o a t l a d o ) {
Figura f =
Retangulo ( lado , lado ) ;
f −>forma = QUADRADO;
return f ;
} /∗ Quadrado ∗/
c
2011
312
Objetos
I
Declarações das funções:
I
f l o a t Area ( F i g u r a f i g ) {
r e t u r n ( ( F i g u r a ) f i g )−>Area ( f i g ) ;
}
I
v o i d T r a n s l a d a r ( F i g u r a f i g , f l o a t dx , f l o a t dy ) {
Figura f = fig ;
f −>p o s x += dx ;
f −>p o s y += dy ;
} /∗ T r a n s l a d a r ∗/
I
I
I
O exemplo anterior demonstra que é possı́vel simular, dentro de
algumas limitações, a implementação de objetos numa linguagem que
não incorpora este conceito.
Há vários aspectos que ficam a cargo do próprio programador,
especialmente a consistência de tipos, fonte comum de erros.
O exemplo anterior será transformado de maneira a ilustrar a
implementação de objetos numa linguagem que possui este conceito.
Será usada uma linguagem fictı́cia, uma extensão simples de C.
Não serão tratados vários aspectos como por exemplo polimorfismo,
visibilidade etc.
Figura
Exemplo de hierarquia das classes:
void Desenhar ( Figura f i g ) {
/∗ Não f o i i m p l e m e n t a d a ∗/
} /∗ D e s e n h a r ∗/
Cı́rculo
Retângulo
Quadrado
c
2011
313
Objetos (cont.)
c l a s s Figura {
/∗ não e x i s t e c o n s t r u t o r ∗/
f l o a t Area ( ) { } ;
void Desenhar ( ) { } ;
f l o a t T r a n s l a d a r ( f l o a t dx , dy ) {
t h i s . p o s x += dx ;
t h i s . p o s y += dy ;
}
} /∗ F i g u r a ∗/
314
Objetos (cont.)
posx
0
posy
(Classe pai)
1
Area (Figura)
2
Desenhar (Figura)
3
Transladar (Figura)
Todos os objetos de uma classe apontam para a mesma tabela de
métodos. Pode haver mais informações. Neste exemplo, todas as funções
foram transformadas em métodos.
c
2011
c
2011
315
c l a s s Retangulo extends Figura {
float alt , larg ;
Retangulo ( f l o at a , f l o at l ) {
this . alt = a;
this . larg = l ;
posx
posy
alt
t h i s . posx = 0 . 0 ;
t h i s . posy = 0 . 0 ;
Classe Figura
0
}
Area (Retangulo)
1
f l o a t Area ( ) {
Desenhar (Retangulo)
2
return a l t ∗ l a r g ;
Transladar (Figura)
3
}
Girar90 (Retangulo)
4
void Desenhar ( ) { . . . } ;
Retangulo Girar90 () {
r e t u r n new R e t a n g u l o ( t h i s . l a r g , t h i s . a l t ) ;
}
} /∗ R e t a n g u l o ∗/
c
2011
larg
316
Objetos (cont.)
Objetos (cont.)
c l a s s Quadrado e x t e n d s R e t a n g u l o {
Quadrado ( f l o a t l ) {
super ( l , l ) ;
}
posx
posy
} /∗ R e t a n g u l o ∗/
alt
0
Classe Retângulo
1
Area (Retangulo)
2
3
Transladar (Figura)
4
Girar90 (Retangulo)
c l a s s Circulo extends Figura {
float raio ;
Circulo ( float r ) {
t h i s . posx = 0 . 0 ;
t h i s . posy = 0 . 0 ;
this . raio = r ;
0
}
1
f l o a t Area ( ) {
r e t u r n PI ∗ s q r ( r a i o ) ;
2
}
3
void Desenhar ( ) { . . . } ;
4
void D u p l i c a r ( ) {
t h i s . r a i o = 2.0∗ t h i s . r a i o ;
}
} /∗ R e t a n g u l o ∗/
larg
Somente o construtor é diferente da classe Retangulo.
c
2011
317
Objetos (cont.)
c
2011
posx
posy
raio
Classe Figura
Area (Circulo)
Desenhar (Circulo)
Transladar (Figura)
Duplicar (Circulo)
318
Objetos (cont.)
Representação de todas as classes:
Exemplo de uso dos objetos:
Figura
0
(Classe pai)
1
Area (Figura)
2
Desenhar (Figura)
3
Transladar (Figura)
Retangulo
0
Circulo
0
1
Area (Retangulo)
1
Area (Circulo)
2
2
Desenhar (Circulo)
3
Transladar (Figura)
3
Transladar (Figura)
4
Girar90 (Retangulo)
4
Duplicar (Circulo)
Quadrado
0
1
Area (Retangulo)
2
3
Transladar (Figura)
4
Girar90 (Retangulo)
c
2011
i n t main ( ) {
F i g u r a f = new C i r c u l o ( 1 0 . 0 ) ;
Retangulo r =
new R e t a n g u l o ( 1 0 . 0 , 2 0 . 0 ) ;
Quadrado q = new Quadrado ( 5 0 . 0 ) ;
C i r c u l o c = new C i r c u l o ( 3 0 . 0 ) ;
p r i n t f ( ”%f \n” , f . Area ( ) ) ;
p r i n t f ( ”%f \n” , r . Area ( ) ) ;
c . Desenhar ( ) ;
f = q;
f . Transladar (5.0 ,8.0);
f . Desenhar ( ) ;
p r i n t f ( ”%f \n” , f . Area ( ) ) ;
/∗ comandos i n v á l i d o s ∗/
f . Duplicar ();
f . Girar90 ( ) ;
c . Girar90 ( ) ;
c = r;
q = f;
} /∗ main ∗/
Os comandos inválidos seriam detectados pelo compilador.
319
c
2011
320
Generalidades
I
Ordenação interna e externa
I
Ordenação ótima por comparações: O(n log n)
Algoritmos por comparação:
I
I
I
I
I
c
2011
321
transposição (bubblesort, quicksort)
inserção (inserção simples, shellsort)
seleção (seleção simples, heapsort)
intercalação (iterativo, recursivo)
I
Outros algoritmos: distribuição (radix sort)
I
Ordenação estável: mantém a ordem relativa dos registros de com
chaves iguais.
c
2011
Ordenação ótima por comparações
Ordenação ótima por comparações (cont.)
Árvore de decisão para ordenar três elementos x1 , x2 e x3 :
Caso geral de n elementos:
I
x1 ≤ x2
V
F
I
x2 ≤ x3
x2 ≤ x3
V
F
x1 , x2 , x3
V
x1 ≤ x3
V
x1 , x3 , x2
x3 , x1 , x2
V
x2 , x1 , x3
x3 , x2 , x1
F
x2 , x3 , x1
I
A árvore tem 3! = 6 folhas (permutações de 3 elementos).
I
A altura da árvore é 3.
I
Portanto, o número mı́nimo de comparações, no pior caso, é 3.
c
2011
A árvore de decisão deverá ter n! folhas (número de permutações de
n elementos).
Uma árvore de altura h tem no máximo 2h folhas.
Deve-se ter, portanto:
2h ≥ n!
=⇒ h ≥ dlog2 (n!)e
Pela aproximação de Stirling:
log2 n
+ O(1)
dlog2 (n!)e = n log2 n − n/(ln 2) +
2
Para valores grandes de n, o primeiro termo é dominante:
F
x1 ≤ x3
F
I
322
dlog2 (n!)e ≈ n log2 n
I
I
323
O número mı́nimo de comparações, no pior caso, é O(n log2 n).
Portanto, não existe nenhum algoritmo de ordenação mais eficiente
que utiliza apenas comparações de elementos.
c
2011
324
Algoritmos: declarações comuns
Algoritmo bubble sort
0
n-1
d
typedef struct Vetor {
int n ;
i n t dados [ 1 ] ;
} V e t o r , ∗ ApVetor ;
v o i d t r o c a ( i n t ∗x , i n t ∗ y ) {
int t = ∗x ;
∗x = ∗y ;
∗y = t ;
} /∗ t r o c a ∗/
j =⇒
v o i d b u b b l e S o r t ( ApVetor v ) {
/∗ Exemplo de t r a n s p o s i ç ã o ∗/
i n t n = v−>n , i , j ;
i n t ∗d = ( v−>d a d o s ) ;
f o r ( i=n −1; i >0; i −−)
f o r ( j =0; j d [ j +1])
t r o c a (&d [ j ] ,& d [ j + 1 ] ) ;
} /∗ b u b b l e S o r t ∗/
I
Os algoritmos de ordenação serão apresentados como funções em
linguagem C que ordenam um vetor de dados que faz parte de uma
estrutura denominada Vetor.
I
Nesta declaração, n denota o tamanho verdadeiro do vetor dados que
dependerá do parâmetro passado à função malloc quando o vetor for
alocado.
I
Vários algoritmos fazem trocas de valores entre elementos do vetor
indicadas por chamadas da função troca.
I
I
I
I
c
2011
325
Inserção simples
0
n-1
I
I
326
p
0
n-1
d
i =⇒
v o i d i n s e r c a o ( ApVetor v ) {
i n t n = v−>n , i , j , t ;
i n t ∗d = ( v−>d a d o s ) ;
f o r ( i =0; i <n −1; i ++) {
t = d [ i +1];
j = i;
w h i l e ( ( j >=0)&&(t<d [ j ] ) ) {
d [ j +1] = d [ j ] ;
j −−;
}
d [ j +1] = t ;
}
} /∗ i n s e r c a o ∗/
I
Seleção simples
t
i =⇒
I
Os elementos entre i+ 1 e n−1 já estão ordenados.
Os elementos d[j] (abaixo de i) são “empurrados” se necessáro; o
maior deles acaba em seu lugar final.
Verifica-se facilmente que o número de comparações executado por
este algoritmo é sempre (n2 −n)/2 (da ordem de O(n2 )).
É um algoritmo estável.
c
2011
d
I
⇐= i
Os elementos entre 0 e i já estão ordenados.
Os elementos menores do que d[i+1] são “empurrados” à direita e
d[i+1] inserido no seu lugar.
No pior caso, O(n2 ) comparações; no melhor caso, O(n).
Um bom algoritmo se os dados já estão parcialmente ordenados.
c
2011
327
v o i d s e l e c a o ( ApVetor v ) {
i n t n = v−>n , i , j , p ;
i n t ∗d = ( v−>d a d o s ) ;
f o r ( i =0; i <n −1; i ++) {
p = i;
f o r ( j=i +1; j <n ; j ++)
i f ( d [ j ]<d [ p ] )
p = j;
t r o c a (&d [ i ] ,& d [ p ] ) ;
}
} /∗ s e l e c a o ∗/
I
I
I
I
Os elementos entre 0 e i−1 já estão ordenados.
O elemento mı́nimo entre as posições i e n−1 (d[p]) troca de lugar
com o elemento d[i].
O número de comparações é sempre da ordem de O(n2 ).
c
2011
328
Algoritmo Quicksort
Algoritmo Quicksort (cont.)
I
Quicksort foi idealizado por C. A. R. Hoare em 1962.
I
É um algoritmo recursivo que ordena segmentos do vetor dado.
I
A ordenação do vetor inteiro é realizada através da chamada de uma
função auxiliar com argumentos que cobrem o vetor:
v o i d q u i c k S o r t A u x ( ApVetor v , i n t esq , i n t d i r ) {
/∗ s u p õ e esq<=d i r ∗/
i n t ∗d = ( v−>d a d o s ) ;
i n t i = esq , j = d i r ;
i n t p i v o t = d [ ( i n t ) ( ( e s q+d i r ) / 2 ) ] ;
/∗ p a r t i c i o n a ∗/
do {
w h i l e ( d [ i ] p i v o t ) j −−;
i f ( i <=j ) {
t r o c a (&d [ i ] ,& d [ j ] ) ;
i ++; j −−;
}
} w h i l e ( i <=j ) ;
/∗ o r d e n a ∗/
i f ( esq<j ) q u i c k S o r t A u x ( v , esq , j ) ;
i f ( d i r >i ) q u i c k S o r t A u x ( v , i , d i r ) ;
} /∗ q u i c k S o r t A u x ∗/
v o i d q u i c k S o r t ( ApVetor v ) {
q u i c k S o r t A u x ( v , 0 , ( v−>n ) −1);
} /∗ q u i c k S o r t ∗/
I
A função auxiliar quickSortAux implementa de fato o algoritmo.
c
2011
329
c
2011
do {
w h i l e ( d [ i ] p i v o t ) j −−;
i f ( i<=j ) {
t r o c a (&d [ i ] , & d [ j ] ) ;
i ++; j −−;
}
} w h i l e ( i<=j ) ;
I
I
Inı́cio do particionamento:
p
330
do {
w h i l e ( d [ i ] p i v o t ) j −−;
i f ( i<=j ) {
t r o c a (&d [ i ] ,& d [ j ] ) ;
i ++; j −−;
}
} w h i l e ( i<=j ) ;
Situação após uma troca:
0
esq
i
j
≥p
≤p
dir
n-1
dir
n-1
(pivot)
d
0
esq
dir
n-1
≤p
d
I
⇐= j
i =⇒
Situação quando termina o particionamento:
0
I
Situação genérica após uma troca:
0
esq
≥p
esq
j
i
d
i
j
≥p
≤p
dir
n-1
≤p
≥p
d
≤p
c
2011
Pode haver apenas um ou nenhum elemento entre j e i. Se houver,
ele é necessariamente igual ao pivô e está na sua posição final.
≥p
331
c
2011
332
do {
w h i l e ( d [ i ] p i v o t ) j −−;
i f ( i<=j ) {
t r o c a (&d [ i ] , & d [ j ] ) ;
i ++; j −−;
}
} w h i l e ( i<=j ) ;
I
I
I
I
I
I
Situação quando termina o particionamento:
esq
0
j
i
Escolha do pivô:
I
Eficiência:
n-1
dir
I
d
I
≤p
I
≥p
I
I
Situação após as chamadas recursivas – o segmento está ordenado:
esq
0
n-1
dir
I
d
em princı́pio, o algoritmo funciona com qualquer valor do pivô
o ideal seria um pivô que particiona o segmento em duas partes de
comprimentos iguais
algumas implementações utilizam a média de alguns poucos elementos
na implementação aqui exibida foi usado o valor do elemento do meio
no pior caso o algoritmo realiza da ordem de O(n2 ) operações
em média e no melhor caso são O(n log n) operações
na prática são quase sempre O(n log n) operações
é o algoritmo de ordenação interna mais utilizado e faz parte das
bibliotecas de várias linguagens (por exemplo, qsort em C)
Estabilidade:
I
I
sob a forma apresentada, o algoritmo não é estável
exercı́cios:
I
I
c
2011
333
exibir um exemplo que demonstra a falta de estabilidade
modificar o algoritmo para que seja estável
c
2011
Exemplo de execução do Quicksort:
Pivot: 65
03
07
09
<
58
30
12
78
23
73
40
*
65
92
42
87
49
27
29
12
44
i
44
03
07
09
58
30
40
73
40
65
92
42
87
49
27
30
12
44
40
23
i
23
29
65
92
42
87
49
58
30
12
44
40
23
29
40
i
40
27
42
87
58
30
12
44
40
23
29
40
27
92
i
49
09
58
30
12
44
40
23
29
40
27
49
42
i
42
j
87
j
87
i
49
j
92
27
j
65
29
j
73
03
07
09
58
03
07
09
03
07
09
03
07
30
i
12
j
12
44
*
58
29
40
27
49
>
42
30
i
44
40
j
40
58
29
40
27
49
42
30
44
40
58
29
40
27
49
42
Vetor original:
07
49
73
58
30
72
44
78
23
09
40
65
92
42
87
03
27
29
40
12
------------------------------------------------------------------------------------------------------
07
03
07
03
Pivot: 03
<
*
03
07
j
i
Pivot: 07
<*
03
07
j
73
i
09
09
j
>
09
58
30
72
44
78
23
58
i
58
i
30
72
44
78
30
72
44
78
23
j
23
334
(< e > delimitam o segmento corrente; ∗ marca o pivô)
Pivot: 09
<
07
03
*
09
49
27
29
40
42
87
j
87
>
12
40
65
92
42
73
40
65
92
49
27
29
40
12
73
40
65
92
42
87
49
27
29
40
12
40
j
78
>
72
72
78
72
73
78
72
65
73
78
72
92
65
73
78
72
87
92
65
73
78
72
87
92
65
73
78
72
87
92
65
73
78
72
Pivot: 23
58
30
72
44
78
23
73
40
65
92
42
87
49
27
29
40
12
58
30
72
44
78
23
73
40
65
92
42
87
49
27
29
40
12
03
07
09
<
23
03
07
09
23
09
<*
12
j
Pivot: 23
>
09
i
c
2011
03
335
07
>
23
i
c
2011
336
Pivot: 29
03
07
09
12
23
<
27
03
07
09
12
23
27
03
07
09
12
23
27
44
i
29
29
j
40
40
i
40
i
58
58
j
58
*
29
49
>
42
Pivot: 40
30
44
40
j
40
87
92
65
73
78
72
30
49
42
87
92
65
73
78
72
44
40
30
49
42
87
92
65
73
78
72
03
07
09
12
23
27
29
30
40
03
07
09
12
23
27
29
30
40
<
40
i=j
40
j
*
44
49
>
42
87
92
65
73
78
72
58
i
44
49
42
87
92
65
73
78
72
<
42
*
44
i
44
>
58
87
92
65
73
78
72
58
87
92
65
73
78
72
<*
49
>
58
i
87
92
65
73
78
72
92
*
87
73
78
>
72
87
73
78
72
58
Pivot: 44
Pivot: 27
03
07
09
12
23
j
<*
27
>
29
i
40
58
44
40
30
49
42
87
92
65
73
78
03
07
09
12
23
27
29
30
40
40
03
07
09
12
23
27
29
30
40
40
42
j
09
12
23
27
29
30
40
40
42
44
j
72
49
j
49
i
Pivot: 40
03
07
09
12
23
27
29
<
30
03
07
09
12
23
27
29
30
03
07
09
12
23
27
29
30
58
i
40
i=j
40
j
44
44
44
i
*
40
j
58
58
40
49
>
42
Pivot: 49
87
92
65
73
78
72
03
40
49
42
87
92
65
73
78
72
40
49
42
87
92
65
73
78
72
07
Pivot: 65
03
07
09
12
23
27
29
30
40
40
42
44
49
58
03
07
09
12
23
27
29
30
40
40
42
44
49
58
Pivot: 30
03
07
09
12
23
27
29
j
<*
30
>
40
i
44
58
40
49
42
c
2011
87
92
65
73
78
72
337
c
2011
<
65
i=j
65
j
92
i
338
Intercalação iterativa (Mergesort)
Pivot: 73
03
07
09
12
23
27
29
30
40
40
42
44
49
58
65
<
72
03
07
09
12
23
27
29
30
40
40
42
44
49
58
65
72
09
12
23
27
29
30
40
40
42
44
49
58
65
j
09
12
23
27
29
30
40
40
42
44
49
58
65
87
i
73
j
*
73
87
i
78
j
78
>
92
07
O algoritmo de intercalação iterativa foi provavelmente um dos
primeiros algoritmos de ordenação interna propostos: John von
Neumann (1945).
I
O algoritmo consiste em várias passagens pelo vetor, intercalando
segmentos consecutivos de tamanhos 1, 2, 4, 8, ..., até completar o
vetor.
I
Utiliza um vetor auxiliar; os dois vetores são usados alternadamente
para guardar os resultados da intercalação.
I
Se necessário, há um passo adicional para copiar os resultados do
vetor auxiliar para o original.
I
O número de comparações deste algoritmo é da ordem de O(n log n)
(ótimo).
I
O algoritmo é estável.
92
Pivot: 72
03
I
<*
72
>
73
i
87
78
92
72
73
<
78
j
*
87
i
>
92
<*
87
>
92
i
Pivot: 78
03
07
Pivot: 87
03
07
09
12
23
27
29
30
40
40
42
44
49
58
65
72
73
78
j
-----------------------------------------------------------------------------------------------------Resultado:
03
07
09
12
23
27
29
30
40
40
42
44
49
c
2011
58
65
72
73
78
87
92
339
c
2011
340
Intercalação iterativa (cont.)
0
n-1
v→d
...
w→d
...
v→d
...
w→d
...
v→d
...
v o i d i n t e r c a l a I t e r a t i v o ( ApVetor v ) {
/∗ Ordena de 2 em 2 , de 4 em 4 , . . . , p o r i n t e r c a l a ç ã o ∗/
i n t n = v−>n ;
i n t td = 1 ;
/∗ 1 , 2 , 4 , . . . ∗/
i n t esq , d i r , l d ;
i n t tamanho = s i z e o f ( V e t o r )+ s i z e o f ( i n t ) ∗ ( n −1);
Boolean par = f a l s e ;
ApVetor w = ( ApVetor ) m a l l o c ( tamanho ) ;
w−>n = v−>n ;
•••
(continua)
Quando n não é uma potência de 2, os últimos segmentos de cada estágio
podem ficar mais curtos do que os outros.
c
2011
341
342
w h i l e ( td<n ) {
esq = 0; par = ! par ;
do {
d i r = e s q+t d ; l d = d i r+t d ;
i f ( d i r >=n ) { /∗ l a d o d i r e i t o v a z i o ∗/
d i r = n ; l d = n −1;
} e l s e i f ( l d >n )
ld = n ;
i f ( p a r ) i n t e r c a l a I t e r a t i v o A u x ( v , w , esq , d i r , l d ) ;
else
i n t e r c a l a I t e r a t i v o A u x (w , v , esq , d i r , l d ) ;
e s q = d i r+t d ;
} w h i l e ( esq<n ) ;
t d = 2∗ t d ;
}
i f ( p a r ) memcpy ( v , w , tamanho ) ;
f r e e (w ) ;
} /∗ i n t e r c a l a I t e r a t i v o ∗/
c
2011
c
2011
v o i d i n t e r c a l a I t e r a t i v o A u x ( ApVetor v , ApVetor w ,
i n t esq , i n t d i r , i n t l d ) {
/∗ I n t e r c a l a v . d a d o s [ e s q : d i r −1] e
v . d a d o s [ d i r : l d −1] em w . d a d o s [ e s q : l d −1] ∗/
i n t ∗ dv = ( v−>d a d o s ) , ∗dw = (w−>d a d o s ) ;
i n t i = esq , j = d i r , k= e s q ;
w h i l e ( ( i <d i r )&&( j <l d ) ) {
i f ( dv [ i ]<=dv [ j ] ) {
dw [ k ] = dv [ i ] ; i ++;
} else {
dw [ k ] = dv [ j ] ; j ++;
}
k++;
}
w h i l e ( i <d i r ) { dw [ k ] = dv [ i ] ; i ++; k++; }
w h i l e ( j <l d ) { dw [ k ] = dv [ j ] ; j ++; k++; }
} /∗ i n t e r c a l a I t e r a t i v o A u x ∗/
343
c
2011
344
Intercalação recursiva
Exemplo de execução:
Vetor original:
07
49
73
58
30
72
44
78
23
09
40
65
92
42
87
03
27
29
40
12
----------------------------------------------------------------------------------------------------
I
Passos do algoritmo:
I
td=1:
| 07
49 | 58
73 | 30
72 | 44
78 | 09
23 | 40
65 | 42
92 | 03
87 | 27
29 | 12
40 |
td=2:
| 07
49
73 | 30
44
78 | 09
23
65 | 03
42
92 | 12
27
40 |
I
58
72
40
87
29
I
I
td=4:
| 07
30
44
49
58
72
73
78 | 03
09
23
40
42
65
87
92 | 12
27
29
40 |
td=8:
| 03
07
09
23
30
40
42
44
58
65
72
73
78
87
92 | 12
27
29
40 |
td=16:
| 03
07
09
12
23
27
29
30
49
40
40
42
44
49
58
65
72
73
78
87
quebrar o vetor v dado em dois vetores v1 e v2 , de tamanhos
aproximadamente iguais
se o tamanho de v1 é maior que 1, ordená-lo recursivamente
se o tamanho de v2 é maior que 1, ordená-lo recursivamente
intercalar os vetores v1 e v2 , deixando o resultado no vetor v original
I
É fácil verificar que o número de comparações é da ordem de
O(n log n) (ótimo).
I
Se implementado corretamente, o algoritmo é estável.
92 |
---------------------------------------------------------------------------------------------------Resultado:
03
07
09
12
23
27
29
30
40
40
42
44
49
c
2011
58
65
72
73
78
87
92
345
Intercalação recursiva (cont.)
c
2011
346
0
n-1
v→d
quebra
v1→d
v2→d
rec
rec
v1→d
v2→d
v o i d i n t e r c a l a R e c u r s i v o ( ApVetor v ) {
i n t n = v−>n ;
i f ( n>1) {
i n t ∗ dv = v−>d a d o s ; ApVetor v1 , v2 ;
i n t i , nv1 = ( i n t ) ( n / 2 ) , nv2 = n−nv1 ;
v1 = ( ApVetor ) m a l l o c ( s i z e o f ( V e t o r )+ s i z e o f ( i n t ) ∗ ( nv1 − 1 ) ) ;
v2 = ( ApVetor ) m a l l o c ( s i z e o f ( V e t o r )+ s i z e o f ( i n t ) ∗ ( nv2 − 1 ) ) ;
v1−>n = nv1 ; v2−>n = nv2 ;
f o r ( i =0; i <nv1 ; i ++) ( v1−>d a d o s ) [ i ] = dv [ i ] ;
f o r ( i =0; i <nv2 ; i ++) ( v2−>d a d o s ) [ i ] = dv [ i+nv1 ] ;
i n t e r c a l a R e c u r s i v o ( v1 ) ; i n t e r c a l a R e c u r s i v o ( v2 ) ;
i n t e r c a l a R e c u r s i v o A u x ( v1 , v2 , v ) ;
f r e e ( v1 ) ;
f r e e ( v2 ) ;
}
} /∗ i n t e r c a l a R e c u r s i v o ∗/
v→d
c
2011
347
c
2011
348
Comparação dos algoritmos de ordenação interna
Tempos em milisegundos:
i n t e r c a l a R e c u r s i v o A u x ( ApVetor u , ApVetor v , ApVetor w) {
I n t e r c a l a o s v e t o r e s u e v , d e i x a n d o o r e s u l t a d o em w . ∗/
i = 0, j = 0, k;
nu = u−>n , nv = v−>n , n = nu+nv ;
∗ du = ( u−>d a d o s ) , ∗ dv = ( v−>d a d o s ) ,
∗dw = (w−>d a d o s ) ;
f o r ( k =0; k<n ; k++) {
i f ( ( i <nu)&&( j <nv ) ) {
i f ( du [ i ]<=dv [ j ] ) { dw [ k ] = du [ i ] ; i ++; }
e l s e { dw [ k ] = dv [ j ] ; j ++; }
} else {
i f ( i <nu ) { dw [ k ] = du [ i ] ; i ++; }
e l s e { dw [ k ] = dv [ j ] ; j ++; }
}
}
} /∗ i n t e r c a l a R e c u r s i v o A u x ∗/
void
/∗
int
int
int
c
2011
349
Ordenação externa: intercalação balanceada múltipla
n
Interc.
Interc.
Interc.
iter.
recur.1
recur.2
------------------------------------------------------------------------------------------------16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
I
I
I
I
Faça a intercalação múltipla dos arquivos f1 , f2 , f3 , ... .
Obs.: Se o número nf de arquivos fi é razoavelmente grande (mais que 5 a
10), pode ser usada uma fila de prioridades de tamanho nf .
0.004
0.004
0.009
0.017
0.039
0.085
0.151
0.322
0.703
1.510
3.279
7.133
15.489
33.404
0.003
0.005
0.009
0.016
0.035
0.074
0.124
0.268
0.573
1.233
2.605
5.520
11.546
24.359
0.005
0.005
0.014
0.016
0.033
0.072
0.130
0.279
0.604
1.290
2.721
5.769
12.192
26.042
0.005
0.010
0.021
0.053
0.107
0.218
0.371
0.805
1.646
3.570
7.442
15.563
32.772
68.350
0.004
0.006
0.010
0.018
0.046
0.083
0.144
0.302
0.654
1.404
2.968
6.189
13.167
27.769
Desafio: programar esta versão.
c
2011
I
I
I
I
I
I
Quicksort
I
I
Leia o máximo número de registros de f que cabem na memória num
vetor v.
Ordene v usando um dos algoritmos de ordenação internos (por
exemplo, quicksort).
Escreva o conteúdo de v em arquivo fi .
i=i+1
c
2011
0.005
0.003
0.003
0.009
0.004
0.007
0.031
0.009
0.016
0.106
0.030
0.050
0.404
0.106
0.179
1.685
0.450
0.674
5.969
1.336
2.079
21.301
5.282
8.136
84.809
21.273
32.121
338.462
84.498
127.803
1351.672
340.743
514.325
5390.648 1366.402 2054.017
21565.843 5450.148 8213.796
89281.419 21772.341 32872.943
Heapsort
350
Ordenação digital ou por distribuição (radix sort)
i=1
Enquanto há dados em f :
I
Selecao
A última coluna corresponde a uma implementação otimizada do
algoritmo de intercalação recursivo que evita alocação e liberação de
espaço em cada chamada.
Passos do algoritmo, dado um arquivo f :
I
(2^4)
(2^5)
(2^6)
(2^7)
(2^8)
(2^9)
(2^10)
(2^11)
(2^12)
(2^13)
(2^14)
(2^15)
(2^16)
(2^17)
Insercao
I
I
I
Bubble
351
O algoritmo baseia-se em procedimentos que eram utilizados para
ordenar cartões perfurados com máquinas classificadoras.
A chave de cada registro de informação é tratada como uma cadeia
de caracteres (ou um número numa base conveniente b) de
comprimento m.
Os registros são distribuı́dos em b sequências, conforme o último
caractere da chave (mantendo a ordem relativa original).
As b sequências são (conceitualmente) concatenadas em ordem
crescente do caractere usado na distribuição.
Os dois passos anteriores são repetidos para o penúltimo, o
antepenúltimo, etc, caractere da chave.
Após m distribuições, o vetor estará ordenado.
O número de operações é no mı́nimo da ordem de O(nm),
dependendo da implementação.
O algoritmo é estável.
c
2011
352
Ordenação digital (cont.)
Exemplo (m = 2):
Vetor original:
07
49
73
58
30
72
44
78
23
09
40
65
92
42
87
03
27
29
40
12
Distribuiç~
ao pelo último dı́gito:
0:
30
1:
40
40
|
|
2:
3:
72
92
42
12
|
73
4:
23
03
|
44
5:
|
65
6:
|
7:
|
8:
07
87
27
|
58
FIM
9:
78
|
49
09
29
Distribuiç~
ao pelo penúltimo dı́gito:
0:
03
1:
07
09
|
12
2:
|
23
3:
27
29
|
30
4:
|
40
5:
40
42
44
49
|
58
6:
|
65
7:
|
72
73
78
|
8:
9:
87 |
92
Resultado:
03
07
09
12
23
27
29
30
40
40
42
44
49
c
2011
58
65
72
73
78
87
92
353
c
2011
FIM
354

Estrutura de Dados

Transcrição

Documentos relacionados

Avaliaç˜ao de Monografias

A comunicaÃ§Ã£o imprescindÃ vel para o sucesso

ALQUIMISTA - Instituto de Química

Ementa sugerida para mini curso de Data Mining

Bina Fonyat - Galeria da Gávea

Técnicas clássicas de distorção para síntese de sinais musicais

27 de agosto, aniversário de Nascimento de Madre Teresa de

Análise de Classificadores de Seqüências Projetados por

LAR DE SANTOS CELEBRAÇÃO DE BODAS DE DIAMANTE Já

Lista de exercícios 03