fila estrutura de dados

Prévia do material em texto

Estrutura de dadosEstrutura de dados
FILA FILA 
20132013
Prof Melo
Apresentação
• Técnico em Desenvolvimento de Sistemas - Ibratec, Recife-PE
• Bacharel em Sistemas de Informação – FIR, Recife-PE
• Especialista em Docência no Ensino Superior – Faculdade 
Maurício de Nassau, Recife-PE
• Mestre em Ciência da Computação – UFPE/CIN, Recife-PE
• Currículo Lattes http://lattes.cnpq.br/0759508594425296)
• Homepage https://sites.google.com/site/hildebertomelo/
Disciplinas Lecionadas
• Desenvolvimento de Aplicações Desktop
• Programação Orientada a Objetos
• Estrutura de Dados
• Tecnologia da Informação & Sociedade
• Sistemas Operacionais
• Sistemas Distribuídos
• Introdução a Informática
• Lógica de Programação
• Informática Aplicada a Saúde
• Banco de Dados
• Projeto de Banco de Dados
• Análise de Projetos Orientado a Objetos
• Programação Cliente Servidor
• Linguagens de Programação: C, C#, Pascal, PHP, ASP, Delphi, Java, JavaScript
• Programação WEB
FILA
• Uma fila é uma lista linear na qual todas as 
inserções são realizadas em uma das 
extremidades (fim da fila). E, além disso, 
todas as remoções e os acessos são 
realizados em outra extremidade (início da 
fila). Esse é o motivo pelo qual as filas são 
denominadas listas FIFO (First-In First-
Out). 
FILA
• Cada vez que uma operação de inserção é
executada, um novo elemento é colocado no final 
da fila. Na remoção, é sempre retornado o 
elemento que aguarda há mais tempo na fila, ou 
seja, aquele posicionado no começo. A ordem de 
saída corresponde diretamente à ordem de 
entrada dos elementos na fila, de modo que os 
primeiros elementos que entram são os primeiros 
a sair.
FILA
• Um exemplo bastante comum de filas verifica-se 
num balcão de atendimento onde pessoas formam 
uma fila para aguardar até serem atendidas. 
Naturalmente, devemos desconsiderar os casos de 
pessoas que “furam” a fila ou que desistem de 
aguardar! Diferentemente das filas no mundo real, 
o tipo de dados abstrato não suporta
FILA
• Uma fila suporta três operações básicas, 
tradicionalmente denominadas como: 
• - Top: acessa o elemento posicionado no início 
da fila;
• - Push: insere um novo elemento no final da 
fila;
• - Pop: remove um elemento do início da fila.
FILA
• Exemplos de declaração de uma FILA em C
Typedef struct registro{ 
char nome[60];
int idade;
float salario; 
}tregistro;
Typedef struct fila{
struct registro dado;
struct fila *prox;
}tfila;
Tfila *inicio;
Tfila *fim;
Inserir – FILA - Passos
• Alocar memória para um elemento auxiliar do 
tipo fila
• Verificar se a FILA está vazia
– Sim – vazia
• O fim e o início da fila deverão apontar para o mesmo endereço 
de memória(auxiliar)
– Não 
• Fazer a inclusão do elemento no final da fila
• Este elemento recém criado deverá ser o fim da fila
• O próximo do final deverá apontar para NULL
Inserir FILA - PUSH
• void Inserir () {
– Tfila * aux = (Tfila *)malloc (sizeof(Tfila));
– if ( (*inicio) == NULL) {
– *inicio = *aux;
– } else {
– (*fim).prox = *aux;
– }
– (*fim) = *aux;
– Scanf(“%s”,(*fim).dado.nome);
– Scanf(“%i”,(*fim).dado.idade);
– Scanf(“%f”,(*fim).dado.salario);
• }
Ler – FILA - Passos
• Verificar se a fila está vazia
–Sim – vazia
• Exibir mensagem de fila vazia
–Não – vazia
• Exibir as informações do início da fila
Ler FILA - TOP
• void ler () {
– if (*inicio != NULL) {
• printf(“%s”,(*inicio).dado.nome);
• printf(“%i”,(* inicio).dado.idade);
• printf(“%f”,(* inicio).dado.salario);
– } else{
• Printf(“Fila vazia”);
– }
• }
Remover – FILA - Passos
• declarar um elemento auxiliar do tipo fila, para 
marcar o início que deverá ser removido
• Verificar se a FILA está vazia
– Não – vazia
• Marcar o início da fila com a variável auxiliar
• Atualizar o início da fila, o início da fila deverá ser o elemento 
logo depois do início
• Devolver a memória do antigo início (aux)
– Sim
• Exibir a mensagem fila vazia
Remover FILA - POP
• void remover () {
– Tfila * aux; 
– if (*inicio != NULL) {
• (*aux) = *inicio;
• (*inicio) = (*inicio).prox;
• Free(*aux);
– } else{
• Printf(“Fila vazia”);
– }
• }
Destruir - FILA
• Ao terminar o programa deveremos 
devolver todos os espaços de memória 
requisitados, para isso criaremos um 
procedimento para destruir a FILA
Destruir - FILA
• void Destruir () {
• Tfila *aux = (*inicio);
• while (*inicio != NULL) {
• (*inicio) = *inicio.prox;
• free (*aux);
• *aux = (*inicio);
• }
• (*inicio) = NULL;
• }
Perguntas...
Bibliografia
• Livro(s) Texto(s):
• PREISS, Bruno R. Estrutura de Dados e 
Algoritmos. Rio de Janeiro: Campus, 2001.
• PEREIRA, Silvio L. Estruturas de dados 
fundamentais. São Paulo: Érica, 2000.
• AZEREDO, Paulo A. Métodos de 
Classificação de Dados e Análise de suas 
Complexidades. Rio de Janeiro: Campus, 
1995.
Bibliografia
• Livros de referencia:
• WEISS, M. A. Data structures and algorithm 
analysis in C++. California: Benjamin/Cummings, 
1999.
• SEDGEWICK, R. Algorithms in C++: Fundamentals, 
data structures, sorting, searching. New York: 
Addison-Wesley, 2001.
• TANENBAUM, Aaron; LANGSAM, Y. & 
AUGENSTEIN, M. Estruturas de Dados usando C. 
São Paulo: Makron Books, 1995.
• LAFORE, R. Aprenda em 24 horas estrutura de 
dados e algoritmo. Rio de Janeiro: Campus, 1999.
• MORAES, Celso R. Estruturas de Dados e 
Algoritmos. São Paulo: Berkeley Brasil, 2001.