Estrutura de Dados Dinâmica Fila

Prévia do material em texto

ESTRUTURAS DE DADOS D INÂMICAS – F ILAS
Algoritmos II
DAMAS, Luís. Linguagem C - 10. ed. / ©2007 Rio de Janeiro, RJ: Livros Técnicos e Científicos, ©2007.
Conceito
� Uma das possiveis aplicações da alocação dinâmica
de memória se dá através da implementação de uma
estrutura classica denominada Fila
� Uma fila é carcterizada basicamente por um regra:
� O primeiro a entrar é o primeiro a sair, obedecendo assim uma
estratégia FIFO (First In First Out)
� Como não sabemos inicialmente a quantidade de 
individuos que uma fila de espera pode ter, 
precisamos criar uma fila que aumente ou diminua
conforme a necessidade
DAMAS, Luís. Linguagem C - 10. ed. / ©2007 Rio de Janeiro, RJ: Livros Técnicos e Científicos, ©2007.
Conceito
� Para esta tarefa, precisamos de uma estrutura
composta pelos dados que serão armazenados e um 
ponteiro para a próxima posição da fila.
� Portanto, a fila será suportada por um ponteiro
� Se o ponteiro for NULL é porque a fila está vazia
� Se não, é porque tem pelo menos um elemento
DAMAS, Luís. Linguagem C - 10. ed. / ©2007 Rio de Janeiro, RJ: Livros Técnicos e Científicos, ©2007.
Conceito
� Uma Fila vazia pode ser representada por um 
ponteiro ligado a terra:
� Ao adicionarmos o próximo elemento da Fila, o 
estado desta seria o seguinte:
Idade 10
Nome Tiago
Prox
DAMAS, Luís. Linguagem C - 10. ed. / ©2007 Rio de Janeiro, RJ: Livros Técnicos e Científicos, ©2007.
Conceito
� Cada vez que for inserido um novo elemento na Fila, 
este será sempre colocado no final:
� Para retirar um elemento da fila, este deve sair
sempre pela ordem em que entrou. 
� Com base no exemplo, o primeiro a sair terá que ser
Tiago, a seguir Luísa e por fim Ana
Idade 30
Nome Ana
Prox
Idade 10
Nome Tiago
Prox
Idade 20
Nome Luísa
Prox
DAMAS, Luís. Linguagem C - 10. ed. / ©2007 Rio de Janeiro, RJ: Livros Técnicos e Científicos, ©2007.
Exemplo
//inicio do código e criação da estrutura de pessoa
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct sPessoa
{
int Idade;
char Nome[20+1];
struct sPessoa *Prox;
} PESSOA;
typedef PESSOA *FILA;
...
DAMAS, Luís. Linguagem C - 10. ed. / ©2007 Rio de Janeiro, RJ: Livros Técnicos e Científicos, ©2007.
Exemplo
//Insere um novo registro no fim da Fila
void Inserir(FILA *Fila, int Idade, char *Nome)
{
if (*Fila == NULL)
{
*Fila = (FILA) malloc(sizeof(PESSOA));
if(*Fila==NULL) return;
(*Fila)->Idade = Idade;
strcpy((*Fila)->Nome, Nome);
(**Fila).Prox = NULL;
}
else
Inserir(& (**Fila).Prox, Idade, Nome);
}
...
DAMAS, Luís. Linguagem C - 10. ed. / ©2007 Rio de Janeiro, RJ: Livros Técnicos e Científicos, ©2007.
Exemplo
//Apaga o primeiro elemento da Fila (se existir)
void Apagar (FILA *Fila)
{ PESSOA *Tmp = *Fila;
if (*Fila == NULL) /* Não existem elementos */
return;
*Fila = (*Fila)-> Prox;
free(Tmp);
}
//Lista todos os elementos da Fila recursivamente
void Listar (FILA Fila)
{
if (Fila==NULL)
return; /* Não existem elementos */
printf("%d %s\n",Fila->Idade, Fila->Nome);
Listar(Fila->Prox); /* Lista os outros */
}
...
DAMAS, Luís. Linguagem C - 10. ed. / ©2007 Rio de Janeiro, RJ: Livros Técnicos e Científicos, ©2007.
Exemplo
main(){
FILA F;
Inic(&F);
puts("Iniciar:");
Listar(F);
puts("Inserir: ");
Inserir(&F,10,"Tiago");
Inserir(&F,20,"Luisa");
Inserir(&F,30,"Ana");
puts("Listar 3");
Listar(F);
Apagar(&F);
puts("Listar 2");
Listar(F);
Apagar(&F);
puts("Listar 1");
Listar(F);
Apagar(&F);
puts("Listar Nada");
Listar(F);
Apagar(&F);
puts("Listar Nada");
Listar(F);
}
DAMAS, Luís. Linguagem C - 10. ed. / ©2007 Rio de Janeiro, RJ: Livros Técnicos e Científicos, ©2007.