fila e arranjos

Prévia do material em texto

Apostila de C online e gratuita
C Progressivo.net
Índice Básico Teste e Laços Função Vetores Ponteiros Strings Structs Alocação
Filas em C - Como Programar (Tutorial de C sobre Queue -
Estrutura de Dados)
Neste Tutorial de C de nossa apostila online, vamos falar sobre uma importante estrutura de dados
dinâmica, que é a fila.
Junto com as listas encadeadas e as pilhas em C, formam o conjunto de estrutura de dados mais
importantes e usados.
Curso de Programação em C, online e com CERTIFICADO! Clique e Obtenha o seu!
As filas (queue, em inglês) são um tipo de estrutura dinâmica de dados onde os elementos (ou nós)
estão arranjados em lista que obedece as seguintes regras:
- Ao inserir um nó, ele vai para a última posição da estrutura
- Ao retirar um nó, é tirado o primeiro elemento da estrutura
Este tipo de estrutura de dados é dita ser FIFO (First in, first out), ou seja, o primeiro elemento a entrar
na estrutura é o primeiro a sair.
O nome fila, por si só, já é auto-explicativo.
Imagine uma fila de banco. A primeira pessoa que chegou na fila, é a que vai ser atendida primeiro.
E se chegar mais alguém? Ela vai demorar mais pra ser atendida.
E se chegar uma outra? Ela será a última a ser atendida, pois quem está na sua frente é atendido
antes.
Ou seja, sempre que inserimos elementos nessa fila, inserimos ao final.
E sempre que retiramos, estamos tirando o primeiro elemento da fila (o mais antigo), pois o que está na
frente que vai sair antes.
Resumindo: inserimos ao fim, e retiramos do começo.
Diferente das pilhas em C (stack), onde colocamos no fim e retiramos do fim.
Simples, não?
Vamos entender agora a lógica para programar uma fila em C, do zero.
Ok, agora que já sabemos o que é uma fila e como funciona, vamos começar a implementar essa
estrutura de dados em C, partindo do zero, apenas baseado no que sabemos da definição de FIFO.
Inicialmente criamos uma struct chamada Node, que é vai criar os nós de nossa estrutura de dados.
Filas em C - Tutorial de Queue
Filas em C - Como Programar a Estrutura de Dados
Função main(), opcao() e menu()
+654   Recomende isto no Google
Linguagem C (Review)
Livro Recomendado
Gostou dos tutoriais?
Ajude a divulgar!
Seja o primeiro de seus
amigos a curtir isso.
C Progr
5,2 mil curtidas
…
Curtir Página
Conteúdo original -
Todos os direitos
reservados
Filas em C - Como Programar (Tutorial de C sob... http://www.cprogressivo.net/2014/05/Filas-em-...
1 de 7 20/09/2016 15:57
Vamos colocar nela um inteiro, o "num" para armazenar um valor qualquer inserido pelo usuário.
Obrigatoriamente, temos que inserir nessa struct um ponteiro de seu próprio tipo.
Vamos chamar esse ponteiro de "prox" pois ele vai servir para apontar para o próximo nó da estrutura.
Caso esse ponteiro aponte para NULL, é porque seu nó é o último da fila ou a fila está vazia.
De resto, a função principal main() simplesmente fica chamando (em um looping do while) a função
menu(), que simplesmente exibe as opções possíveis para se trabalhar com a fila em C.
Depois que o usuário escolhe o que fazer, sua escolha é enviada para a função opcao(), que usa um
teste condicional do tipo switch para invocar a função correta.
Inicialmente, criamos um ponteiro para a struct Node, é o "FILA", e ele é a representação de nossa
estrutura de dados do tipo fila.
Seu inteiro não importa, a função deste ponteiro é definida pelo seu ponteiro "prox".
O vetor "prox" aponta pro primeiro elemento da fila, e caso ele não exista, a fila está vazia e "prox"
aponta para NULL.
Fazemos isso na função inicia(), que inicializa a fila fazendo: FILA->prox = NULL
Devemos sempre lembrar de alocar memória para cada nó de nossa fila, o que é feito pela função
aloca().
No decorrer de nosso programa sobre estrutura de dados do tipo fila, muitas vezes será necessário
checar se a fila está vazia ou não.
Isso é feito de uma maneira bem simples: checando o ponteiro "prox" da struct "FILA".
Se apontar pra NULL, a fila está vazia. Do contrário, tem pelo menos um elemento na fila.
Antes de mais nada, vamos usar a função aloca() para reservar um espaço em memória para o novo
nó, o "novo". Como este novo nó será o último da fila, seu ponteiro "prox" deve apontar para NULL.
Esta foi a primeira parte do processo de se adicionar um elemento em uma fila.
A segunda parte é adicionar este novo nó ao final da fila, e para tal, devemos achar o último nó da fila.
Primeiro checamos se a fila está vazia, pois se tiver, basta colocar no novo nó em FILA->prox
Caso não esteja, criamos um ponteiro "tmp" que vai apontar para todos os elementos da fila em busca
do último. Ele começa no primeiro elemento, que está em "FILA->prox".
Se "tmp->prox" apontar para NULL, o ponteiro aponta para o último da fila.
Senão, devemos seguir adiante com o ponteiro (tmp = tmp->prox) até acharmos o último elemento.
Achando, colocamos lá o novo nó, o "novo".
A variável inteira "tam" é para definir o tamanho da fila (número de nós). Usaremos este inteiro na
função "exibe()", que vai exibir os elementos da fila.
Vamos agora retirar um elemento da fila.
E segunda a lógica deste tipo de estrutura de dados, vamos retirar o primeiro nó.
Antes de tudo, checamos se a fila não está vazia.
Se estiver, trabalho feito, pois não precisaremos retirar nó algum da estrutura de dados.
Caso a fila não esteja vazia, precisamos identificar o primeiro elemento e o segundo (na verdade, não é
obrigado que exista um segundo elemento). O que precisamos fazer é que "FILA->prox" não aponte
mais para o primeiro elemento, e sim para o segundo.
Vamos usar um ponteiro "tmp" para apontar para o primeiro elemento da fila: tmp = FILA->prox
Se "tmp" aponta para o primeiro elemento, então "tmp->prox" aponta para o segundo elemento ou
NULL, caso a fila só tenha um nó.
Agora vamos fazer a ligação entre o ponteiro base (FILA) e o segundo elemento (ou NULL) da fila:
FILA->prox = tmp->prox
Pronto. Tiramos o primeiro elemento da jogada, pois se ninguém aponta para ele, ele não faz mais
parte da estrutura de dados.
Função aloca() e inicia()
Função vazia()
Função insere()
Função retira()
Visite também
Política de Privacidade
Filas em C - Como Programar (Tutorial de C sob... http://www.cprogressivo.net/2014/05/Filas-em-...
2 de 7 20/09/2016 15:57
Interessante, não?
Note que declaramos a função "retira()" como sendo do tipo struct Node, pois é uma boa prática
retornar o nó que retiramos, pois geralmente retiramos ele da estrutura para fazer algo, trabalhar em
cima dele. Depois que retornamos ele pra função "opcao()" liberamos o espaço que havia sido alocado
para ele.
Esta função serve somente para mostrar os números ("num") existentes em cada nó, para você poder
adicionar, retirar e ver o que vai acontecendo com a fila.
Ou seja, esta função tem mais propósitos didáticos, pra você ver as coisas realmente funcionamento na
sua frente, como devem funcionar.
Basicamente pegamos um ponteiro "tmp" e fazemos ele apontar para cada um dos nós, exibindo o
número. Para saber o tanto de nós existentes e a ordem, usamos a variável "tam" que é incrementada
quando adicionamos nó na fila (função insere) e decrementada quando tiramos elementos da estrutura
de dados (função retira).
Esta função simplesmente tem por objetivo ir em cada nó e liberar a memória alocada.
Para tal, usamos dois ponteiros.
Um ponteiro aponta para um nó ("atual"), e o outro ponteiro aponta para o nó seguinte ("proxNode").
Liberamos o primeiro ponteiro, ou seja, aquele nó deixa de existir.
Se tivéssemos só este ponteiro, nos perderíamos na fila.
Porém, o ponteiro que aponta para o nó seguinte da fila serve pra isso, pois agora temos o ponteiro
para o próximo elemento da fila "proxNode").
Agora damos um passo pra frente, fazendo um ponteiro apontar para este próximo elemento ("atual =
proxNode"), e o ponteiro próximo, para umaposição a frente ("proxNode = proxNode->prox").
E repetimos o processo até que o nó atual seja NULL (fim da fila).
#include <stdio.h>
#include <stdlib.h>
struct Node{
int num;
struct Node *prox;
};
typedef struct Node node;
int tam;
int menu(void);
void opcao(node *FILA, int op);
void inicia(node *FILA);
int vazia(node *FILA);
node *aloca();
void insere(node *FILA);
node *retira(node *FILA);
void exibe(node *FILA);
void libera(node *FILA);
int main(void)
{
node *FILA = (node *) malloc(sizeof(node));
if(!FILA){
printf("Sem memoria disponivel!\n");
exit(1);
}else{
inicia(FILA);
int opt;
Função exibe()
Função libera()
Fila em C - Código Fonte Completo
Filas em C - Como Programar (Tutorial de C sob... http://www.cprogressivo.net/2014/05/Filas-em-...
3 de 7 20/09/2016 15:57
do{
opt=menu();
opcao(FILA,opt);
}while(opt);
free(FILA);
return 0;
}
}
int menu(void)
{
int opt;
printf("Escolha a opcao\n");
printf("0. Sair\n");
printf("1. Zerar fila\n");
printf("2. Exibir fila\n");
printf("3. Adicionar Elemento na Fila\n");
printf("4. Retirar Elemento da Fila\n");
printf("Opcao: "); scanf("%d", &opt);
return opt;
}
void opcao(node *FILA, int op)
{
node *tmp;
switch(op){
case 0:
libera(FILA);
break;
case 1:
libera(FILA);
inicia(FILA);
break;
case 2:
exibe(FILA);
break;
case 3:
insere(FILA);
break;
case 4:
tmp= retira(FILA);
if(tmp != NULL){
printf("Retirado: %3d\n\n", tmp->num);
libera(tmp);
}
break;
default:
printf("Comando invalido\n\n");
}
}
void inicia(node *FILA)
{
FILA->prox = NULL;
tam=0;
}
int vazia(node *FILA)
{
if(FILA->prox == NULL)
Filas em C - Como Programar (Tutorial de C sob... http://www.cprogressivo.net/2014/05/Filas-em-...
4 de 7 20/09/2016 15:57
return 1;
else
return 0;
}
node *aloca()
{
node *novo=(node *) malloc(sizeof(node));
if(!novo){
printf("Sem memoria disponivel!\n");
exit(1);
}else{
printf("Novo elemento: "); scanf("%d", &novo->num);
return novo;
}
}
void insere(node *FILA)
{
node *novo=aloca();
novo->prox = NULL;
if(vazia(FILA))
FILA->prox=novo;
else{
node *tmp = FILA->prox;
while(tmp->prox != NULL)
tmp = tmp->prox;
tmp->prox = novo;
}
tam++;
}
node *retira(node *FILA)
{
if(FILA->prox == NULL){
printf("Fila ja esta vazia\n");
return NULL;
}else{
node *tmp = FILA->prox;
FILA->prox = tmp->prox;
tam--;
return tmp;
}
}
void exibe(node *FILA)
{
if(vazia(FILA)){
printf("Fila vazia!\n\n");
return ;
}
node *tmp;
tmp = FILA->prox;
printf("Fila :");
while( tmp != NULL){
printf("%5d", tmp->num);
tmp = tmp->prox;
}
printf("\n ");
int count;
for(count=0 ; count < tam ; count++)
printf(" ^ ");
Filas em C - Como Programar (Tutorial de C sob... http://www.cprogressivo.net/2014/05/Filas-em-...
5 de 7 20/09/2016 15:57
Tags: Apostila de C, Curso de C, Estrutura de Dados, Estrutura Dinâmica de Dados, Filas, Queue,
Tutorial de C
printf("\nOrdem:");
for(count=0 ; count < tam ; count++)
printf("%5d", count+1);
printf("\n\n");
}
void libera(node *FILA)
{
if(!vazia(FILA)){
node *proxNode,
 *atual;
atual = FILA->prox;
while(atual != NULL){
proxNode = atual->prox;
free(atual);
atual = proxNode;
}
}
}
5 comentários:
augustowebd disse...
Olá, em primeiro lugar, parabéns pelo excelente trabalho.
Analisando o código, fiquei na dúvida se na opção 4 do case, "retirar", onde se lê:
"
if(tmp != NULL){
printf("Retirado: %3d\n\n", tmp->num);
libera(tmp);
}
"
Não deveria ser:
"
if(tmp != NULL){
printf("Retirado: %3d\n\n", tmp->num);
libera(tmp);
}
"
?
Mais uma vez, parabéns!
26 de fevereiro de 2015 08:42
Frank disse...
Olá! O código está dando bug. Depois que retiro um elemento é peço pra exibir,
entra em loop infinito. Tentei várias maneiras de corrigir esse bug mas não consigo,
ainda tenho dificuldade pra lidar com ponteiros. Parabéns, ótima matéria
4 de março de 2015 20:17
Joilson Rodrigues disse...
respondendo a duvida do que Frank disse, não sou especialista só curioso ao bug
que ele referiu sofre o loop infinito quando ele retira um elemento e exibe a lista, eu
resolvi dessa maneira setei null e liberei a memoria de temp
Filas em C - Como Programar (Tutorial de C sob... http://www.cprogressivo.net/2014/05/Filas-em-...
6 de 7 20/09/2016 15:57
Postagem mais recente Postagem mais antigaPágina inicial
Assinar: Postar comentários (Atom)
Postar um comentário
tmp->prox =NULL;
free(tmp->prox);
21 de abril de 2015 11:30
Carlos Augusto Grispan disse...
Excelente apostila. Quem dera os professores fossem tão claros. Parabéns!
Uma pequena correção:
em case 4, trocar libera(tmp) por free(tmp).
Abraços e estou esperando o conteúdo sobre árvores.
14 de maio de 2015 12:16
kinhopr disse...
frank
e só vc ignorar a linha Libera(tmp);
comenta ela e o programa roda blz
//libera(tmp);
if(tmp != NULL){
printf("Retirado: %3d\n\n", tmp->num);
libera(tmp);
}
17 de maio de 2015 14:16
Gostou desse tutorial de C?
Sabia que o acervo do portal C Progressivo é o mesmo, ou maior que, de um livro ou curso presencial?
E o melhor: totalmente gratuito.
Mas para nosso projeto se manter é preciso divulgação.
Para isso, basta curtir nossa página no Facebook e/ou clicar no botão +1 do Google.
Contamos e precisamos de seu apoio.
Publicidade
Melhor visualizado com Google Chrome e Mozilla Firefox
Filas em C - Como Programar (Tutorial de C sob... http://www.cprogressivo.net/2014/05/Filas-em-...
7 de 7 20/09/2016 15:57