AED – Algoritmos e Estruturas de Dados
Notas de aula – 2s05
Alexandre Gonçalves Silva
Ilustrações: Gilmário Santos, André Körbes e Alexandre Silva
Fonte: Projeto de Ensino de Gilmário Santos e Adriano Fiorese
Tópicos
•
•
•
•
•
•
Tipo de Dado Abstrato
TDA Pilha
TDA Fila
TDA Lista
Árvore Binária de Busca
Algoritmos de Ordenação
2
Filas
• Estrutura FIFO – First In, First Out
– Primeiro elemento inserido é o primeiro a ser removido
• Aplicadas em situações onde há necessidade de
registrar uma série de elementos em seqüência,
acessando-os na ordem de sua ocorrência.
• Ilustração de uma fila: pessoas, uma após a outra,
esperando atendimento em um caixa de
supermercado.
3
Introdução
• Filas permitem manipulações em duas
extremidades: no início (ou frente) e no fim (ou
cauda).
• Inserções são feitas na cauda.
• Remoções são feitas na frente.
• Aplicações: implementação de filas de
impressão/processos, simulações, percurso em
largura em árvores, algoritmos de inundação.
4
Operações de Fila
• Na Fila, pode-se:
– Criar
• Instanciar objeto
• Exemplo de “relógio global”:
–T0: fila vazia
–T2: insere B
–T1: insere A
–T3: insere C
– Inserir
• Inserir na cauda
– Remover
• Remover da frente
– Buscar
• Consultar a frente
– Destruir
• Desalocar objeto
5
Implementação de Fila
•
Estática
– Alocação feita apenas na criação para a quantidade máxima de elementos,
desalocação feita apenas na destruição do objeto
– Limitação no número máximo de elementos
– Uso de vetor, estrutura de acesso eficiente
– Desperdício de memória
•
Dinâmica
– Alocação a cada inserção (insere), desalocação a cada remoção (remove) de um
elemento
– Sem limitação para o número de elementos (a não ser de memória)
– Uso de lista de nós encadeados, eficiente pois há referências da frente e cauda
– Não há desperdício de memória
6
Fila Estática (FE)
7
Possibilidades de FE
• Fila Estática Simples (FES) – Sem reaproveitamento do vetor. Pode
ocorrer uma situação de “falso cheio” (último elemento inserido está
na última posição do vetor, porém há posições iniciais disponíveis de
remoções já realizadas).
• Fila Estática com Movimentação de Dados
– Na Remoção (FEMR) – Reutilização da primeira posição do vetor após
uma remoção através da cópia dos elementos para uma posição à frente.
– Na Inserção (FEMI) – Reutilização do vetor (se for o caso) após uma
inserção em condição de “falso cheio”, através do deslocamento dos
elementos para as primeiras posições.
• Fila Estática Circular (FEC) – Inserção do elemento, em condição de
“falso cheio”, na primeira posição.
8
Fila Estática Simples (FES)
9
Criando a FES
10
Inserindo na FES
11
Buscando e Removendo na FES
12
Falso Cheio na FES
Cheio
Falso Cheio
13
Fila Estática com Movimentação
de Dados na Remoção (FEMR)
14
Removendo na FEMR
15
Fila Estática com Movimentação
de Dados na Inserção (FEMI)
16
Inserindo na FEMI
17
Fila Estática Circular (FEC)
18
Estrutura da FEC
Descritor
typedef struct {
int tamVet;
int tamInfo;
int quant;
int frente;
int cauda;
void **vet;
} FEC;
Inserção
...
if (p->quant < p->tamVet)
if (p->cauda == tamVet-1)
p->cauda = 0;
...
Remoção
...
if (p->frente == p->tamVet-1)
p->frente = 0;
...
19
Mecanismo de Inserção e
Remoção na FEC
20
Fila Dinâmica (FD)
21
Simplesmente (FDSE) e
Duplamente Encadeada (FDDE)
22
Fila de Prioridade (FP)
23
Comparando na FP
• O TDA não conhece o tipo de seus elementos.
• Cada aplicação apresenta critérios de prioridade específicos (exemplo:
idade, gestante, data de expedição, etc).
• Exemplo de lógica de comparação de prioridades da aplicação a ser
passada, como parâmetro (ponteiro para função), ao TDA:
int compara(void *p1, void *p2) {
pElemento e1 = (pElemento) p1;
pElemento e2 = (pElemento) p2;
if (e1->prior > e2->prior)
return MAIOR;
else if (e1->prior < e2->prior)
return MENOR;
else
return IGUAL;
}
24
Inserindo na FP
• Quanto maior a prioridade do elemento, mais
próximo do início da fila ele é inserido.
• Pode-se optar em modificar apenas a remoção ou
apenas a inserção de modo que os elementos
sejam retirados na ordem decrescente de sua
prioridade.
• A inserção modificada consiste na comparação, de
nó em nó, até que se encontre um elemento de
prioridade menor que a do elemento a ser inserido.
25
Código da inserção na FP (simplesmente encadeada)
int insereFP(pFP p, void *novo, int (*Compara)(void *p1, void *p2)) {
pNoFP aux, ant, pos;
aux = (pNoFP) malloc(sizeof(NoFP));
if (aux == NULL)
return FRACASSO;
aux->dados = malloc(p->tamInfo);
if (aux->dados == NULL) {
free(aux); return FRACASSO;
}
memcpy(aux->dados, novo, p->tamInfo);
aux->prox = NULL;
if (testaVaziaFP(p) == SIM) {
p->frente = aux; p->cauda = aux; return SUCESSO;
}
ant = NULL;
pos = p->frente;
while ((pos != NULL) && (Compara(novo, pos->dados) != MAIOR)) {
ant = pos; pos = pos->prox;
}
if (ant == NULL) {
aux->prox = p->frente; p->frente = aux; return SUCESSO;
}
aux->prox = pos; ant->prox = aux; return SUCESSO;
}
26
Multi-Fila Estática Circular
(MFEC)
27
Modelo da MFEC
28