Jun 6 2011

Estrutura de dados–Implementando Fila com C

Category: C ANSIthalessuzuki @ 09:26

Olá “PessoALL”.

Nesta postagem abordarei um assunto que muitas vezes nos dá dores de cabeça enquanto estamos estudando Estrutura de Dados, mais especificamente, Filas.

Funcionamento:

Em Estrutura de Dados, uma fila tem a mesma estrutura de uma lista encadeada, porém, seu funcionamento é diferente. Filas possuem a característica FIFO (First In First Out - primeiro a entrar, primeiro a sair).

Podemos fazer uma analogia com uma fila de banco, por exemplo, onde o primeiro cliente a chegar será o primeiro a ser atendido e os próximos clientes a chegar, deverão entrar na fila aguardando o atendimento, seguindo este critério.

Sendo sua idéia principal a característica First In First Out, quando removemos um elemento da fila, deverá sempre ser removido o primeiro elemento. Sendo assim, novos elementos deverão ser inseridos na última posição.

Suponhamos que temos a seguinte fila:

Fila_1

Caso o número 5 seja inserido, teremos a seguinte fila:

Fila_2

Agora, para removermos um elemento da fila, temos que respeitar a característica FIFO, portanto, removeremos sempre o primeiro número, no caso o 1:

Fila_3

Ao removermos o 1, o início da fila passa a ser o próximo elemento, que na nossa fila é o 2.

Agora que já aprendemos o conceito da Fila, podemos ir para a ação! Cool

Este código foi feito de maneira dinâmica, mas também podemos fazer de me maneira estática usando vetores.

Precisamos definir o nosso tipo fila na nossa biblioteca fila.h:

 

  1. typedef struct filaNo{   
  2.      int dado;   
  3.      struct filaNo* prox; // Definição dos nós da fila   
  4.   }tfilaNo;                    
  5. typedef struct tfila {        
  6.      tfilaNo* inicio;   
  7.      tfilaNo* final;      // Definição do tipo fila   
  8.   } tfila;  

Quando criamos nosso tipo fila os ponteiros de inicio e fim da fila precisam apontar para null. A função criar_fila faz esta ação.

  1. void cria_fila (tfila *F)   
  2. {   
  3.    F->inicio = F->final = NULL;   
  4. }  

O método fila_vazia diz se nossa fila está vazia ou não.

  1. int fila_vazia (tfila F)   
  2. {   
  3.    if(F.inicio == NULL && F.final == NULL) return 1;   
  4.    else return 0;   
  5. }  

Para inserir um novo nó na fila, precisamos alocar na memória um novo nó, atribuir o valor a este nó, apontar o último nó e o ponteiro do final da fila para este novo nó. Caso a fila esteja vazia, este novo nó será o primeiro e os ponteiros do início e final da fila apontarão para este novo nó.

A nossa função de inserção ficará do seguinte modo:

  1. int inserir_fila (tfila *F, int valor)   
  2. {   
  3.    tfilaNo *novo;   
  4.    novo = (tfilaNo*) malloc(sizeof(tfilaNo));   
  5.    if (novo == NULL) return 0;  /* Erro ao alocar o novo nó */  
  6.    novo->dado = valor;   //   
  7.    novo->prox = NULL;    //Atribuição do valor e apontando o próximo para NULL   
  8.    if (fila_vazia(*F))   
  9.       F->inicio = novo;  // Se a fila estiver vazia, o novo nó sera o primeiro da fila   
  10.    else  
  11.       (F->final)->prox = novo;   
  12.    F->final = novo;     // Senão, o ponteiro para o final da fila apontará para o novo nó   
  13.    return 1;   
  14. }  

Para removermos um nó da fila, usaremos a função auxiliar primeiro_fila, como o nome já diz, retorna o primeiro elemento da fila para que possamos removê-lo.

  1. int primeiro_fila (tfila F, int *dado){   
  2.    if (fila_vazia(F)) return 0;   
  3.       *dado = (F.inicio)->dado;   
  4.    return 1;   
  5. }  

Na função remover_fila, fazemos a chamada da função primeiro_fila. Caso o nó retornado seja o último da fila, o ponteiro final da fila apontará para null. O ponteiro do início da fila apontará para onde o nó que será removido aponta. Caso ele seja o último, o ponteiro início apontará para null, já que o próximo nó do que estamos removendo aponta para null.

  1. int remover_fila (tfila *F, int *valor)   
  2. {   
  3.    tfilaNo *aux;   
  4.    if (fila_vazia(*F)) return 0;  /* fila vazia  */  
  5.    primeiro_fila(*F,valor);     // Remove o primeiro nó   
  6.    if (F->inicio == F->final)   // Se existir somente um nó na fila, apontamos o final da fila para NULL   
  7.       F->final = NULL;   
  8.    aux = F->inicio;               // Atribuímos o nó retornado da fila ao nó auxiliar    
  9.    F->inicio = (F->inicio)->prox; // O início da fila apontará para o próximo nó do que estamos removendo   
  10.    free(aux);                      
  11.    return 1;   
  12. }  

Tendo nossos métodos principais prontos, podemos criar a fila da seguinte maneira no nosso método main().

  1. int main(int argc, char *argv[])   
  2. {   
  3.   tfila doc;                                     
  4.   int a;   
  5.      
  6.   cria_fila(&doc);      
  7.   inserir_fila (&doc ,1);   
  8.   inserir_fila (&doc ,2);   
  9.   inserir_fila (&doc ,3);   
  10.   inserir_fila (&doc ,4);   
  11.   inserir_fila (&doc ,5);     
  12.      
  13.   while(!fila_vazia(doc)){   
  14.         remover_fila(&doc,&a);         
  15.         printf("    %d\n", a);   
  16.   }   
  17.      
  18.   system("PAUSE");     
  19.   return 0;   
  20. }  

Inserimos os números de 1 a 5 na nossa fila e, em seguida, removemos os valores da fila enquanto ela não estiver vazia. Executando nosso código, temos o seguinte resultado:

Fila_4

 

Espero que este exemplo ajude. Abaixo estão algumas referências.

Referências:

[1] http://java2s.com/Code/C/Data-Structure-Algorithm/QueueinC.htm

[2] http://msdn.microsoft.com/pt-br/library/tze823w7(v=vs.90).aspx

[3] http://forum.clubedohardware.com.br/estruturas-dados-pilhas/702596

[4] Herbert Schildt, C Completo e Total 3ª Ed.

 

Se você deseja fazer o download do projeto (Dev-C++) segue -> Fila.rar (7.99 kb).

Até a próxima.

 

Portanto, qualquer que me confessar diante dos homens, eu o confessarei diante de meu Pai, que está nos céus. (Mateus 10:32)

Share or Bookmark this post…

Tags: , , , , ,

Kommentare

1.
trackback DotNetKicks.com says:

Estrutura de dados - Implementando Fila com C

You've been kicked (a good thing) - Trackback from DotNetKicks.com

2.
Rodrigo Silva Rodrigo Silva Brazil says:

Vei, tá foda...

Voeg kommentaar By


(Sal you Gravatar ikone vertoon)

  Country flag

biuquote
  • Opmerkings
  • Voorskou
Loading