Fila Em Linguagem C

Faculdade Salesiana Dom Bosco de Piracicaba

Autores Diego Doná Jordan Toledo Wellinton Rodrigo

Estrutura de Dados: Fila

Piracicaba 2009

Faculdade Salesiana Dom Bosco de Piracicaba

Autores Diego Doná Jordan Toledo Wellinton Rodrigo

Estrutura de Dados: Fila

Trabalho

de

Aproveitamento

da

disciplina de Algoritmos e Programação II apresentado como exigência parcial para obtenção do grau de Bacharel em Sistemas de Informação no Centro Universitário orientação

Salesiano, dos

sob

Professores

Magossi e José Carlos Magossi.

Piracicaba 2009

a

Silvia

Autor: ____________________________________________________ Autor: ____________________________________________________ Autor: ____________________________________________________ Título: ____________________________________________________ Trabalho sobre filas, apresentado como exigência parcial para obtenção de nota do segundo semestre do curso de Sistemas de Informação na Instituição Faculdade Salesiana Dom Bosco de Piracicaba. Trabalho referente à nota do primeiro semestre de Sistemas de Informação entregue em __/__/____ pelos professores:

(Assinatura) ________________________________________________ (Titulação/nome/instituição) (Assinatura) ________________________________________________ (Titulação/nome/instituição)

Piracicaba 2009

RESUMO

Tratamos neste trabalho sobre a fila, um tipo de Estrutura de Dados muito utilizado na computação. Fazemos a associação com elementos da vida real, para facilitar o entendimento, demonstramos a lógica utilizada e apresentamos o código final em linguagem C. Além do funcionamento padrão da fila, como inserção e retirada de elementos, apresentamos funcionalidades como ordenação, busca e exibição da fila.

Palavras-chave:

1. Estrutura de Dados; 2. Fila; 3. Linguagem C;

SUMÁRIO 1. Introdução...........................................................................................................6 2. Filas na vida real, filas na computação ...............................................................7 3. Problema associado à fila...................................................................................7 4. Tipos de Fila .......................................................................................................7 4.1. Fila linear......................................................................................................8 4.2. Fila Circular ..................................................................................................9 5. Código fonte comentado...................................................................................10 5.1. Cabeçalho do arquivo ................................................................................10 5.2. Função Main ..............................................................................................11 5.3. Função Inserir ............................................................................................13 5.4. Função Eliminar .........................................................................................13 5.5. Função Mostrar ..........................................................................................14 5.6. Função Preencher ......................................................................................14 5.7. Função BubbleSort ....................................................................................15 5.8. Função BuscaSequencial...........................................................................15 6. Conclusão.........................................................................................................17 7. Referência Bibliográfica ....................................................................................18

6

Introdução Quando pensamos numa fila da vida real, seja uma fila de atendimento no banco, na padaria ou no supermercado, imaginamos elementos – normalmente pessoas – sendo atendidos em ordem de chegada. Pessoas chegam ao final da fila e pessoas são atendidas, saindo da fila. O importante é notar a ordem que existe nela. Ninguém deveria “furar” a fila. Se você é o terceiro da fila, não será atendido em segundo lugar, nem em quarto. Será atendido em terceiro lugar. Existem exceções, podemos deixar alguém com mais prioridade passar a nossa frente, trocar de lugar e outras modificações na ordem original. Entretanto, existe uma ordem a ser respeita. “A idéia fundamental da fila é que só podemos inserir um novo elemento no final da fila e só podemos retirar o elemento do início” (W. Celes e J. L. Rangel, Apostila de Estruturas de Dados, pg. 126). Uma fila nada mais é que uma sequência de elementos ordenadas pela ordem de chegada, tanto na vida real como na programação.

7

Filas na vida real, filas na computação Na computação, ao invés de pessoas, utilizamos caracteres e números, por exemplo. Para representar a ordem de chegada e saída, podemos utilizar um vetor. Adotamos a posição n-1 ou a 0 como ponto de chegada e saída. Uma fila de banco pode ser visualizada quarteirões antes do ponto inicial, algumas vezes. No computador as filas também podem possuir muitos elementos, mas precisamos escrever uma rotina que a mostre ao usuário, caso seja interessante.

Problema associado à fila Um sistema de impressora em rede, recebendo arquivos de diversos computadores para serem impressos é um exemplo de utilização de fila. Se não utilizássemos uma estrutura com fila, criar uma ordem de impressão seria impossível.

Tipos de Fila Quando lidamos com filas na computação, podemos classificá-las em pelo menos dois tipos: Filas e Filas circulares. A fila “linear” é de uma implementação mais simples e é mais fácil de modificar conforme a necessidade, porém, exige um esforço de processamento maior. A fila circular é mais complexa, mais difícil de modificar, mas paga com uma velocidade maior em seu processamento.

8

Fila linear Simplesmente usamos um vetor e uma variável auxiliar para marcar o fim da fila. Adotamos um lado do vetor para ser a entrada e o outro automaticamente será onde os elementos entram – o fim da fila. O esforço de processamento dessa alternativa se encontra quando retiramos um elemento da fila. Devemos re-organizar a fila, para que a posição eliminada não fique vazia, senão, num momento nossa fila estará completamente cheia e não poderemos inserir elementos.

Representação de uma Fila simples quando se retira um elemento.

Com um vetor de 4 posições ocupadas por inteiros, não parece grande problema. Mas com 100 elementos ocupados por outros vetores pode ser uma dificuldade. Temos que passar por todas as posições para ajustar corretamente.

9

Fila Circular Também utilizamos um vetor, mas dessa vez, com duas variáveis auxiliares: Início e

Fim.

Conforme

inserimos,

incrementamos

Fim.

Conforme

retiramos,

incrementamos o Começo. Se chegarmos ao fim do vetor, voltamos ao começo. É um ciclo de retiradas e inserções. Nosso algoritmo precisa prever mais detalhes, tomando cuidado para não estourar o limite e nem deixar as variáveis com os valores errados. Por outro lado, nos livramos da necessidade de iterar por todas as posições para organizar a fila.

Simulação de retirada e inserção numa fila circular, incrementando as variáveis auxiliares.

Na figura acima, retiramos o primeiro elemento. O Começo fica na segunda casa. Em seguida, inserimos um elemento. Fim fica valendo 1, pois já está na última posição livre e a próxima casa seria justamente a primeira. Por fim, retiramos mais um elemento. Note que se fossemos inserir mais algo, ele ficaria na casa ao lado direito do número 5.

10

Código fonte comentado Para facilitar o desenvolvimento do algoritmo e aplicação, o sistema de fila organizará apenas uma determinada quantidade de números inteiros, num sistema de fila circular.

Cabeçalho do arquivo

#include <stdio.h> #include <string.h> #define NUM 4 void inserir(int lista[], int num, int *c, int *f); void mostrar(int lista[], int tam); void eliminar(int lista[], int *c, int *f); void bubbleSort(int lista[], int *c, int *f); void buscaSequencial(int lista[], int numero); void preencher(int lista[], int tam);

Temos o include padrão (stdio.h) e o string.h, para poder usar a função toupper. Além disso, declaramos uma constante com o tamanho da fila e o cabeçalho das funções. As funções inserir, eliminar e bubbleSort usam algo um pouco diferente: int *c e int *f. Com isso, requisitamos um endereço de memória de um inteiro, não um valor inteiro. Fazemos isso, pois, podemos em cada função mexer com o começou e/ou fim da fila. Isso se chama passagem por referência. Com essa técnica, dispensamos o return, pois estamos lidando diretamente com o valor contido no endereço e o seu valor altera a variável que foi passada na função main.

11 Inserir será responsável por colocar os números na fila. Pede-se a fila, o numero a ser inserido e dois endereços de memória (c e f). Mostrar vai permitir a visualização da fila. Pede-se a lista e o seu tamanho. Eliminar retira o primeiro item na fila. Pede-se a fila e dois endereços de memória (c e f). BubbleSort é o algoritmo de ordenação da lista. Pede-se a fila e dois endereços de memória (c e f). BuscaSequencial é o algoritmo de busca na fila. Pede-se a fila e o número a ser buscado. Preencher é uma função auxiliar, utilizada apenas para zerar todas as posições do vetor. Fazemos isso, pois convencionamos 0 como “vazio”. Pede-se a fila e o seu tamanho.

Função Main

int main(int argc, char *argv[]) { //fC = fila Circular, c = começo, f = fim int fC[NUM],c=0,f=0,numInsert,numBusca; char opcao; preencher(fC,NUM); printf("Programa de simulacao de fila.\n"); printf("Para inserir um numero, digite 'i'\n"); printf("Para eliminar um numero, digite 'e'\n"); printf("Para buscar um numero, digite 'b' e informe o numero\n"); printf("Para organizar a fila, digite 'o'\n"); printf("Para sair, digite 's'\n\n"); do { //printf("Choose your destiny: "); printf("Qual sua escolha? "); fflush(stdin); scanf("%c",&opcao); if(toupper(opcao) == 'I') { printf("Digite o valor a ser inserido: "); scanf("%d",&numInsert);

12 inserir(fC,numInsert,&c,&f); printf("\nVisualizacao da fila: "); mostrar(fC,NUM);

} else if(toupper(opcao) == 'E') { eliminar(fC,&c,&f); printf("Visualizacao da fila: "); mostrar(fC,NUM); printf("\n"); } else if(toupper(opcao) == 'B') { printf("Digite o valor a ser buscado: "); scanf("%d",&numBusca); buscaSequencial(fC,numBusca); } else if(toupper(opcao) == 'O') { bubbleSort(fC,&c,&f); printf("\nVisualizacao da fila ordenada: "); mostrar(fC,NUM); } } while(toupper(opcao) != 'S'); system("PAUSE"); return 0; }

Em main() damos uma mensagem na tela de como utilizar o programa. Lemos um caractere e o testamos contra todas as possibilidades disponíveis. I permite inserir novos elementos na fila, lendo o número a ser inserido e chamando a função Inserir. E elimina o primeiro elemento da fila. B busca um elemento na fila. O permite a ordenação do vetor. S termina o programa

13

Função Inserir

void inserir(int lista[], int num, int *c, int *f) { //F e C são iguais (mesma casa) //Porém esta casa está em branco. Quero poder preenche-la //"Se a casa esta em branco, preencha, mas não aumente F" //(não aumentamos F pois só preenchemos a ultima casa) if((*f+1) % NUM == *c && lista[*f] == 0) { lista[*f] = num; } //F e C NÃO são iguais e a casa está vazia (0) //preencho e aumento F else if((*f+1) % NUM != *c && lista[*f] == 0) { lista[*f] = num; *f = (*f+1) % NUM; } //F e C NÃO são iguais(eliminei algo) e a casa está ocupada //mudamos de casa para não sobrescrever //e depois preenchemos a nova casa com o valor else if((*f+1) % NUM != *c && lista[*f] != 0) { *f = (*f+1) % NUM; lista[*f] = num; } //para todos os outros casos... else printf("A fila esta cheia, nenhum elemento inserido.\n"); }

Função Eliminar

void eliminar(int lista[], int *c, int *f) { //se o começo e o fim estiverem na mesma casa //e ela estiver "vazia" (representado por 0) if(*f == *c && lista[*c] == 0) printf("A fila esta vazia, nenhum elemento retirado.\n\n"); else {

14 lista[*c] = 0; //se F e C forem iguais evito de C passar o F //se não quebraria a ordem da fila if(*f != *c) { *c = (*c+1) % NUM; }

}

//se estiverem na mesma casa, passo ambos para a próxima //isso evita de inserir na última casa após ordenação else { *f = (*f+1) % NUM; *c = (*c+1) % NUM; }

}

Função Mostrar

void mostrar(int lista[], int tam) { int i; for(i = 0; i <= tam -1; i++) printf("[%d]",lista[i]); printf("\n\n"); }

Função Preencher

void preencher(int lista[], int tam) { int i; for(i = 0; i <= tam -1; i++) lista[i] = 0; }

15

Função BubbleSort

void bubbleSort(int lista[], int *c, int *f) { int i=0, tmp; //começa com verdade short int troca=1; while(troca) { //rezo pra que fique organizado troca=0; for(i=0; i < NUM; i++) { if(lista[i] > lista[i+1]) { tmp = lista[i];

} }

lista[i] = lista[i+1]; lista[i+1] = tmp; troca=1;

}

//está ordenado, re-iniciamos o fim começo da fila *c = 0; *f = NUM-1; }

Função BuscaSequencial

void buscaSequencial(int lista[], int numero) { int i=0; short int achou=0; for(i=0; i < NUM; i++) { if(lista[i] == numero) { printf("\nElemento %d encontrado na posicao %d.\n\n",numero,i+1); achou=1; break; }

16 } if(!achou) printf("\nElemento nao encontrado. Foi mal.\n\n"); }

17

Conclusão Com a utilização de filas temos uma ferramenta de organização interessante, que pode ter muitas funcionalidades implementadas. Poderíamos ter feito com que o elemento na saída fosse processado e retirado automaticamente – como no caso da fila de impressão. É importante utilizar este recurso. Se filas são importantes na vida real, elas também têm seu espaço garantido na área da computação.

18

Referência Bibliográfica Waldemar Celes; José Lucas Rangel. Apostila de Estruturas de Dados. Curso de Engenharia – PUC-RIO, 2002. Universidade de São Paulo - São Carlos, SP, Instituto de Ciências Matemáticas e de Computação, Departamento de Computação e Estatística. Material sobre fila circular. Disponível em http://www.icmc.usp.br/~sce182/fcirc.html, acesso em 21 out. 2009. HTMLSTAFF. Estrutura de Dados em C – Fila Circular com operador módulo. Disponível em http://www.htmlstaff.org/ver.php?id=3960, acesso em 31 de ago. 2009.