AED – Algoritmos e Estruturas de Dados

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

Notas de aula – 2s05

2

Tópicos

• Tipo de Dado Abstrato

• TDA Pilha

• TDA Fila

• TDA Lista

• Árvore Binária de Busca

• Algoritmos de Ordenação

3

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.

4

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.

5

Operações de Fila

• Na Fila, pode-se:– Criar

• Instanciar objeto

– Inserir • Inserir na cauda

– Remover • Remover da frente

– Buscar • Consultar a frente

– Destruir• Desalocar objeto

• Exemplo de “relógio global”:–T0: fila vazia

–T1: insere A

–T2: insere B

–T3: insere C

6

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

7

Fila Estática (FE)

8

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.

9

Fila Estática Simples (FES)

10

Criando a FES

11

Inserindo na FES

12

Buscando e Removendo na FES

13

Falso Cheio na FES

Cheio Falso Cheio

14

Fila Estática com Movimentação de Dados na Remoção (FEMR)

15

Removendo na FEMR

16

Fila Estática com Movimentação de Dados na Inserção (FEMI)

17

Inserindo na FEMI

18

Fila Estática Circular (FEC)

19

Estrutura da FEC

Descritortypedef 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;

... ...

if (p->frente == p->tamVet-1) p->frente = 0;

...

Remoção

20

Mecanismo de Inserção e Remoção na FEC

21

Fila Dinâmica (FD)

22

Simplesmente (FDSE) e Duplamente Encadeada (FDDE)

23

Fila de Prioridade (FP)

24

Comparando na FP

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;}

• 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:

25

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.

26

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;

}

27

Multi-Fila Estática Circular (MFEC)

28

Modelo da MFEC