Algoritmo e Estrutura de Dados - 07

Prévia do material em texto

ESTRUTURAS DE DADOS 
E ALGORITMOS
 2015, Gizelle Kupac Vianna (PPGMMC/UFRRJ)
Calendário
• Prova: dia 13/04 (quarta-feira)
• Matéria:
• Estruturas de Dados Estáticas:
• Pilhas, Filas e Listas (Simples e Circulares)
• Algoritmos de Ordenação (Bubble-sort, Inserção e 
Seleção)
• Algoritmos de Busca (Sequencial e Binária)
Gizelle Kupac Vianna (PPGMMC/UFRRJ) 2
FILAS SEQUENCIAIS
Aula10
3Gizelle Kupac Vianna (PPGMMC/UFRRJ)
Filas Sequenciais
• Na implementação mais simples de uma fila, as 
inserções são realizadas em uma extremidade 
do vetor (no fim), enquanto as remoções são 
realizadas na outra extremidade (no início).
• Operações de uma fila: 
• Cria_fila
• Fila_vazia
• Fila_cheia
• Enfileirar
• Desenfileirar
4Gizelle Kupac Vianna (PPGMMC/UFRRJ)
Definição do Tipo Fila
typedef struct{
int i,f;
tno no [TAM];
} tfila;
• A fila pode ser criada colocando-se I = 0 e F = -1. 
• Fila vazia: I > F
• Fila cheia: F = TAM-1
5Gizelle Kupac Vianna (PPGMMC/UFRRJ)
Operações com Filas
• Cria Fila 
void cria_fila(tfila *fi){
fi-> i=0;
fi->f= -1;
} 
• Fila Vazia
int fila_vazia (tfila fi){ 
if (fi.i> fi.f)
return 1;
return 0;
}
6Gizelle Kupac Vianna (PPGMMC/UFRRJ)
Operações com Filas
• Fila Cheia
int fila_cheia(tfila fi){
return (fi.f == tam-1)
}
• Enfileirar
int enfileirar(tfila *fi, tno chave){ 
if (fila_cheia(*fi))
return 0;
fi-> f++;
fi->no[fi->f]=chave;
return 1; 
} 
7Gizelle Kupac Vianna (PPGMMC/UFRRJ)
Operações com Filas
• Desenfileirar
int desenfileirar (tfila*fi, tno *chave){
if (fila_vazia(*fi))
return 0;
*chave=fi-> no[fi->i];
fi->i++;
return 1;
} 
8Gizelle Kupac Vianna (PPGMMC/UFRRJ)
Filas Sequenciais
• Problema da fila cheia: 
• A fila pode ir se deslocando para a direita, após 
algumas operações de inserção e/ou remoções. Em 
algum momento, a função fila_cheia irá sinalizar um 
valor falso-positivo.
• De fato, a fila só deveria estar cheia quando não 
existisse nenhum elemento vazio no vetor.
• Soluções?
Gizelle Kupac Vianna (PPGMMC/UFRRJ) 9
Filas Sequenciais
• Soluções possíveis:
• 1ª SOLUÇÃO: Se antes da remoção I=F, a fila deverá 
ser reinicializada após a operação.
• 2ª SOLUÇÃO: A cada remoção, deslocar a fila para a 
esquerda:
• Nenhuma das duas soluções é eficiente!
10Gizelle Kupac Vianna (PPGMMC/UFRRJ)
Filas Sequenciais
• 3ª SOLUÇÃO: Os elementos da fila são armazenados 
consecutivamente, a partir da posição de início, 
podendo “dar a volta” e continuar a partir da posição 0 
do vetor => Filas Circulares!
• Exemplo:
11
0 1 2 3 4 5 6 7 8 9
A
max = 10
início = 7
fim = 1
n = 5 
Primeiro
elemento
Último 
elemento
Gizelle Kupac Vianna (PPGMMC/UFRRJ)
Filas Circulares Sequenciais
• Cria Fila (p->inic agora aponta para o elemento 
imediatamente anterior ao primeiro da fila):
void cria_fila (tfila *pf) {
pf->inic = pf->fim = tam-1;
}
• Fila Vazia
int fila_vazia (tfila f) {
if (f.inic == f.fim)
return 1;
return 0;
}
Gizelle Kupac Vianna (PPGMMC/UFRRJ) 12
Filas Circulares Sequenciais
• Fila Cheia
int fila_cheia (tfila f) {
if ((f.fim%tam)+1 == f.inic) return 1;
return 0;
}
• Enfileirar
int enfileirar (tfila *pf, int elem) {
if (fila_cheia(*pf)) return 0;
pf->fim=(pf->fim+1)%tam;
pf->no[pf->fim] = elem;
return 1;
}
Gizelle Kupac Vianna (PPGMMC/UFRRJ) 13
Filas Circulares Sequenciais
• Desenfileirar:
int desenfileirar (tfila *pf, int *elem) {
if (fila_vazia(*pf))
return 0;
pf->inic = (pf->inic+1)%tam;
*elem = pf->no[pf->inic];
return 1;
}
Gizelle Kupac Vianna (PPGMMC/UFRRJ) 14
Filas
• Todas as operações são O(1)
• A política de inserção e remoção de dados à 
maneira de uma fila é conhecida como “FIFO” –
First In First Out
15Gizelle Kupac Vianna (PPGMMC/UFRRJ)