View
224
Download
4
Category
Preview:
DESCRIPTION
Apostila completa com conceitos e exercicios.
Citation preview
1
Curso Superior de Tecnologia em TelemticaProgramao e Estruturas de Dados
Filas Fundamentos e Implementaes
Copyright2010Prof. Csar Rocha
cesarocha@ifpb.edu.br
2
Objetivos
Explorar os conceitos fundamentais acerca do uso de filasfilas utilizando a linguagem C Organizao e implementao, caractersticas,
vantagens, desvantagens, regras de utilizao, operaes bsicas e algoritmos de implementao
Neste mdulo, sero abordadas ainda as seguintes implementaes de filas: seqencial, encadeada seqencial, encadeada e circulare circular Este mdulo ser utilizado como referncia na
entrega dos futuros projetos Implementao das estruturas e algoritmos, criao
das bibliotecasbibliotecas e prticas de laboratrio
3
Motivao
Uma das estruturas de dados mais utilizadas em programao a filafila Um exemplo de utilizao em computao a
implementao de uma fila de impresso
Assim como na pilha, os acessos aos elementos em uma fila tambm seguem uma regra : Lembre-se da pilha, onde: LLast IIn FFirst OOut Porm, uma fila : FFirst IIn FFirst OOut
A idia fundamentalA idia fundamental S podemos inserir um novo n no final da fila S podemos retirar a partir do incio da fila
4
Estratgia
Pode-se fazer uma analogia com uma fila de clientes em um banco qualquer: o primeiro a entrar na fila, ser o primeiro a sair e ser
atendido (retiramos ele do incio ou frente da fila) o ltimo cliente deve entrar no final da fila e, portanto,
ser o ltimo a sair (ou ser atendido) na fila
Portanto: No podemos retirar qualquer cliente da fila! Apenas clientes que esto na frente da fila
No podemos inserir um cliente na fila de tal forma que ele no seja o ltimo no conjunto de clientes
5
Propriedades
Propriedades de uma fila: Existem nn elementos enfileirados; E1E1 o elemento no incio (ou frente) da fila; EnEn o ltimo elemento da fila;
A insero de um primeiro elemento E1E1 em uma fila vazia, torna-o o primeiro a sair da estrutura No se pode consultar qualquer elemento A insero sempre feita depois do elemento EnEn A retirada sempre feita no elemento E1E1
6
Neste estgio, estaremos trabalhando com trs tipos de filas: seqenciaisseqenciais, encadeadas encadeadas e circularescirculares Seqencial: neste TAD, os elementos da fila so
armazenados em endereos seqenciais. Materializada na forma de um vetorvetor (arranjo ou matriz).
Tipos de filas
v[ ]
preciso controlar o incio e o final da fila. Note os campos frente e fim.
Como poderamos adaptar uma lista seqencial uma fila?
preciso controlar preciso controlar o incio e o final da o incio e o final da fila. Note os campos fila. Note os campos frente e fim.frente e fim.
Como poderamos Como poderamos adaptar uma lista adaptar uma lista seqencial uma seqencial uma fila?fila?
?...???
?...??A
Fila Vazia
Insere A
?...?BAInsere B
?...CBAInsere C
Frente= 0 e Fim= -1
Frente= 0 e Fim= 0
Frente= 0 e Fim= 1
Frente= 0 e Fim= 2
?...CB?Retira Frente= 1 e Fim= 2
7
(Continuao.) Encadeada: neste TAD, os elementos da fila so
elementos encadeados por ponteirosponteiros
Circular: caso particular de filas. Iremos levantar e comentar a necessidade da implementao circular mais frente
Importante:Importante: so apenas diferentes maneiras de se implementar o TAD, porm todas as trs formas seguem a mesma filosofia FFirst IIn FFirst OOut
Tipos de filas
TFilaEnc f* 12 09
8
Filas seqenciais
Pense um pouco...Pense um pouco... O que voc acha que seria necessrio para
implementar uma biblioteca de um novo TAD que representasse uma fila seqencial? um vetor de elementos (tamanho pr-definido) duas variveis que controlem a frente e o fim da fila
/* filaseq.h */void criarFila(TFila *fila);int filaVazia(TFila *fila);int filaCheia(TFila *fila);int enfileirar(TFila *fila, int dado);int desenfileirar(TFila *fila, int *d);void imprimir(TFila *fila);
/* filaseq.h */void criarFila(TFila *fila);int filaVazia(TFila *fila);int filaCheia(TFila *fila);int enfileirar(TFila *fila, int dado);int desenfileirar(TFila *fila, int *d);void imprimir(TFila *fila);
/* estruturao */typedef struct fila {
int elementos[MAX];int frente;int fim;
}TFila;
/* estruturao */typedef struct fila {
int elementos[MAX];int frente;int fim;
}TFila;
9
Mas... h problemas!Mas... h problemas!
Voc deve ter percebido que a parte ocupada do vetor pode chegar ultima posio Ou seja, a fila seqencial vai se deslocando da
esquerda (frente) para direita (fim) em cada retirada
Existem dois elementos vazios na fila, mas nenhum outro elemento pode mais ser inserido! fila.fim chegou condio de limite (MAX -1)
??DC?Fila
Insere E e F
Retira C
Insere G
Frente= 1 e Fim= 2
Frente= 1 e Fim= 4
Frente= 2 e Fim= 4
Frente= 2 e Fim= 4
FEDC?
FED??
FED??
10
Mas... h problemas!Mas... h problemas!
E agora?E agora? Do jeito que est, pode-se chegar a uma situao
(absurda) em que a fila estar vazia, mas nenhum elemento novo poder mais ser inserido! Concluso: a representao seqencial, descrita
anteriormente, parece no ser muito boa!
Poderamos mudar a funo desenfileirar() E fazer o deslocamento esquerda de todos os
elementos a cada retirada na frente da fila, mas... ...e se a fila tivesse 100 elementos?
Havamos criticado o deslocamento da lista seqencial!
11
SoluoSoluo
O que se quer reaproveitar as primeiras posieslivres do vetor sem implementar um re-arranjo (trabalhoso) de todos os elementos a cada retirada Para isso, pode-se incrementar as posies do vetor de
maneira circular Ou seja, se o ltimo elemento da fila ocupar a ltima
posio do vetor, inserimos os novos elementos a partir do incio do vetor!
Graficamente:Graficamente:
Insere G Frente= 2 e Fim= 0FEDG
12
Filas encadeadas
O que fazer quando o nmero mximo de elementos na fila no conhecido? Devemos implementar a fila usando uma estrutura de
dados dinmica (com alocaoalocao dinmicadinmica) Podemos empregar os conceitos vistos nas listas
simplesmente (ou duplamente) encadeadas
Entretanto, as regras de insero/remoo, agora, iro mudar! Algumas funes da lista encadeada (inserir ou remover
mediante uma posio qualquer, entre outras) devero ser eliminadas neste novo TAD
13
Filas encadeadas - modus operandi
O primeiro elemento (incio) da lista encadeada poder representar a frente atual da fila Assim, cada novo elemento ser inserido no final da lista.
Conseqentemente e, sempre que solicitado, retiramos o elemento a partir do incio da lista
Desta forma, vamos precisar de apenas duas funes auxiliares na lista: uma para inserir no fim (enfileirar) outra para remover do incio (desenfileirar)
H apenas uma desvantagem: Para cada elemento a ser inserido na fila, teremos que
percorrer todos os nodos at encontrar o ltimo.
14
Fila encadeada com n descritor
Vamos utilizar os conhecimentos auferidos em tcnicas de encadeamento! Neste caso em particular, iremos alocar um n
cabea para que possamos ter acesso direto ao final da fila (promover performance)
100 110 120
TFilaEncCab f
03Vantagens
Acesso direto aoprimeiro nodo;
Acesso direto aoltimo nodo;
Informao sobre o tamanho da lista.
VantagensVantagens
AcessoAcesso diretodireto aoaoprimeiroprimeiro nodonodo;;
AcessoAcesso diretodireto aoaoltimoltimo nodonodo;;
InformaoInformao sobresobre o o tamanhotamanho dada listalista..
Cabea
15
Algoritmos em C
O que dever ser feito pelo aluno: Escolha e instalao do ambiente a ser trabalhado no
laboratrio Modelagem deste TAD (dados e operaes) Implementao dos algoritmos de operaes bsicas
vistos em sala de aula na linguagem C Utilizao das regras de modelagem vistas no mdulo
anterior (criao de bibliotecas) e modularizao Implantao de cdigo legvel e bem documentado Nomes de variveis condizentes com o problema Prtica de laboratrio
16
Para um bom aproveitamento:Para um bom aproveitamento:
O aluno deve identificar a relao entre TAD (biblioteca e modularizao) com a implementao da fila no cdigo! Resolva todas as questes da prprtica de tica de
laboratlaboratrio de filas circular e encadeadario de filas circular e encadeada Procure o professor ou monitor da disciplina e
questione conceitos, listas, etc. No deixe para codificar tudo e acumular assunto
para a primeira avaliao. Este apenas um dos assuntos abordados na prova!
ObjetivosMotivaoEstratgiaPropriedadesTipos de filasTipos de filasFilas seqenciaisFilas encadeadasFilas encadeadas - modus operandiFila encadeada com n descritorAlgoritmos em CRecommended