×
Ir ao conteúdo
  • Cadastre-se

Estruturas de Dados - Pilhas, Filas, Listas encadeadas


RooT

Posts recomendados

Após ver inúmeras perguntas sobre a implementação de estruturas de dados em C, resolvi fazer este tópico para esclarecer de maneira geral o funcionamento dessas estruturas.


As estruturas de dados têm larga aplicação na computação em geral. Sistemas Operacionais e aplicativos as utilizam para várias atividades importantíssimas, como gerenciamento de memória, execução de processos, armazenamento e gerenciamento de dados no disco, etc. Ou seja, não faltam motivos para um estudante da área ou qualquer desenvolvedor/programador saberem a fundo e com fluência sobre o assunto.


É necessário que você tenha conhecimento prévio e boa fluência com ponteiros, passagem de parâmetros e comandos na linguagem C, pois isso é de fundamental importância. Afinal, quem está procurando uma ajuda com as estruturas de dados, supõe-se que já tenha tal conhecimento “na ponta da língua”.


Muito bem, vamos ao que interessa.


Pilhas


O funcionamento de uma pilha consiste numa estratégia chamada LIFO (last in, first out – último a entrar, primeiro a sair). Além disso, o único elemento que se pode acessar na pilha é o elemento do topo da mesma, ou seja, o último a ser empilhado. Pense numa pilha de pratos. Quando se vai lavá-los, você não começa retirando o que está mais abaixo, e sim o que está no topo da pilha. É basicamente assim que esse tipo de estrutura funciona.


Implementaremos as seguintes funções para Pilha:


typedef struct pilha Pilha; //redefinição do tipo struct pilha para simplesmente Pilha


- Pilha* pilha_cria (void); //cria uma pilha
- void pilha_insere (Pilha* p, float v); // empilha um novo elemento
- float pilha_retira (Pilha* p); //retira um elemento (o último)
- int pilha_vazia (Pilha* p); //verifica se a pilha está vazia
- void pilha_libera (Pilha* p); //esvazia toda a estrutura alocada para a pilha, liberando seus elementos


Podemos implementar uma pilha utilizando vetores, aonde os elementos serão armazenados, ocupando as primeiras posições do vetor. Dessa forma, se temos n elementos armazenados na pilha, o elemento vet[n-1] representa o do topo.


[SIZE=2]#define N 50[/SIZE][SIZE=2]struct pilha {[/SIZE][SIZE=2]int n;[/SIZE][SIZE=2]float vet[N];[/SIZE][SIZE=2]};[/SIZE][SIZE=2]typedef struct pilha Pilha;[/SIZE]


A função que cria a pilha aloca dinamicamente essa estrutura e inicializa a pilha como sendo vazia, ou seja, com o número de elementos igual a zero.
[SIZE=2]Pilha* pilha_cria (void) {[/SIZE][SIZE=2]Pilha* p = (Pilha*)malloc(sizeof(Pilha));[/SIZE][SIZE=2]p->n = 0; //[/SIZE][SIZE=2][I]inicializa com zero elementos[/I][/SIZE][SIZE=2]return p;[/SIZE][SIZE=2]}[/SIZE]
Como nossa pilha está implementada usando um vetor de tamanho fixo, devemos sempre verificar se existe espaço para inserção de um novo elemento.
[SIZE=2]void pilha_insere (Pilha* p, float v){[/SIZE][SIZE=2]if (p->n == N) //[/SIZE][SIZE=2][I]verifica se a capacidade do vetor foi esgotada[/I][/SIZE][SIZE=2]{[/SIZE][SIZE=2] printf (“Capacidade da pilha estourou!\n”);[/SIZE][SIZE=2] exit (1);[/SIZE][SIZE=2]}[/SIZE][SIZE=2][I]/*insere o novo elemento na próxima posição livre*/[/I][/SIZE][SIZE=2]p->vet[p->n] = v;[/SIZE][SIZE=2]p->n++;[/SIZE][SIZE=2]}[/SIZE]
A função de remoção retira um elemento (o que estiver no topo) e retorna esse elemento, daí o retorno dessa função ser do tipo float, pois esse é o tipo do dado que estamos armazenando na pilha. Se for um dado de outro tipo (char, por exemplo), bastaria você alterar o tipo de retorno da função para char.
[SIZE=2]float pilha_remove (Pilha* p)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]float v;[/SIZE][SIZE=2]if (pilha_vazia (p)) [/SIZE][SIZE=2] {[/SIZE][SIZE=2] printf (“Pilha está vazia!\n”);[/SIZE][SIZE=2] exit(1);[/SIZE][SIZE=2] }[/SIZE][SIZE=2]/*agora retira o elemento do topo da pilha*/[/SIZE][SIZE=2]v = p->vet[p->(n-1)];[/SIZE][SIZE=2]p->n--;[/SIZE][SIZE=2]return v;[/SIZE][SIZE=2]}[/SIZE]
Podemos implementar a função que verifica se a pilha está vazia da seguinte maneira:
[SIZE=2]int pilha_vazia (Pilha* p)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]return (p->n == 0); /*se isto for verdade, será retornado o conteúdo dos parêntesis, caso contrário será retornado zero. */[/SIZE][SIZE=2]}[/SIZE]
E agora a função para liberar a memória alocada para a pilha:
[SIZE=2]void pilha_libera (Pilha* p)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]free(p);[/SIZE][SIZE=2]}[/SIZE]


Filas


Basicamente o que diferencia a fila da pilha é a ordem de saída dos elementos. Enquanto na pilha o elemento retirado é sempre o último a entrar (o do topo da pilha), na fila sempre é retirado o primeiro elemento a entrar na estrutura. Podemos fazer uma analogia com uma fila de banco por exemplo, onde a primeira pessoa a ser atendida é a que chega primeiro. À medida que outras pessoas chegam na fila, deverão permanecer na fila aguardando que sejam atendidas, seguindo este critério.


Implementaremos as seguintes funções para filas:


typedef struct fila Fila; //redefinição do tipo struct fila para simplesmente Fila

- Fila* fila_cria (void); //cria uma fila
- void fila_insere (Fila* p, float v); // enfileira um novo elemento
- float fila_retira (Fila* p); //retira um elemento (primeiro)
- int fila_vazia (Fila* p); //verifica se a fila está vazia
- void fila_libera (Fila* p); //esvazia toda a estrutura alocada para a fila, liberando seus elementos


Mais uma vez, para simplificar, vamos implementar uma fila a partir de um vetor. Como um vetor em C tem uma quantidade fixa de elementos, digamos, N elementos, observe que mais uma vez temos um limite na quantidade de elementos a serem armazenados na fila.


De acordo com a ideia central da fila (FIFO - primeiro a entrar, primeiro a sair), ao usarmos um vetor para implementação da fila, observe que, quando retiramos elementos dela, é como se a fila “andasse” no vetor, pois ao se retirar elemento(s) da fila, o índice do vetor que representa o topo da fila se altera. Por exemplo, imagine um vetor de N = 6 posições. Se inserirmos 4 elementos, teremos as 4 primeiras posições da fila ocupadas. Ao retirarmos 2 elementos (lembre-se que serão retirados os 2 primeiros), temos agora a situação em que o 1º elemento da fila, ou seja, o topo dela, será representado pelo 3º elemento inicialmente inserido, conforme ilustra a figura:


figura1kjs.jpg

Se retirarmos 2 elementos, teremos a seguinte situação:


figura2kdy.jpg

A partir de agora, o 1º elemento da fila passa a ser o elemento 55, que foi o 3º elemento inserido, presente no índice 2 do vetor. Observe que vetores em C sempre iniciam com índice 0 e não 1.


Por causa desse fato, precisamos fazer uma alteração nos índices do vetor a cada vez que realizarmos uma remoção de quaisquer elementos da fila. Essa reordenação é feita de forma “circular” no vetor, afim de aproveitar as posições liberadas quando se retira elementos. No exemplo citado, teríamos a seguinte situação ilustrativa, após essa reordenação:


figura3qji.jpg

Essa reordenação de índices pode ser feita utilizando uma função específica:
[SIZE=2]Static int incr (int i)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]return (i+1)%N;[/SIZE][SIZE=2]}[/SIZE]


Pode-se dispensar o uso desta função utilizando diretamente apenas o incremento circular, já que essa função seria sistematicamente chamada a cada vez que se retirar elementos da fila, e isso é um processo computacionalmente custoso. O incremento circular ficaria assim:


[SIZE=2]i = (i+1)%N;[/SIZE]


Para a interface da fila, podemos utilizar uma estrutura contando 3 campos: um vetor de tamanho N, um inteiro n para representar o número de elementos armazenados na fila e um índice ini para o início da fila.


Tendo o índice para o início da fila, podemos calcular o índice para o final da fila, que chamaremos de fim da seguinte maneira:


[SIZE=2][I]fim = (ini+n)%N;[/I][/SIZE]


A estrutura da fila fica então:


[SIZE=2]#define N 100[/SIZE][SIZE=2]struct fila [/SIZE][SIZE=2]{[/SIZE][SIZE=2]int n;[/SIZE][SIZE=2]int ini;[/SIZE][SIZE=2]float vet[N];[/SIZE][SIZE=2]}[/SIZE]


A função que cria a fila:


[SIZE=2]Fila* fila_cria (void)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]Fila* f = (Fila*) malloc(sizeof(Fila));[/SIZE][SIZE=2]f->n = 0; //[/SIZE][SIZE=2][I]inicializa a fila vazia;[/I][/SIZE][SIZE=2]f->ini = 0; //[/SIZE][SIZE=2][I]escolhe uma posição inicial;[/I][/SIZE][SIZE=2]return f;[/SIZE][SIZE=2]}[/SIZE]


A função que insere elementos na fila deve verificar se existe espaço disponível para esta inserção, e inserir o elemento no final da fila, utilizando o índice fim, conforme já falamos anteriormente:


[SIZE=2]void fila_insere (Fila* f, float v)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]int fim;[/SIZE][SIZE=2]if (f-> == N)[/SIZE][SIZE=2]{[/SIZE][SIZE=2] printf (“Fila não tem espaço disponível”);[/SIZE][SIZE=2] exit (1);[/SIZE][SIZE=2] }[/SIZE][SIZE=2]fim = (f->ini + f->n)%N; [/SIZE][SIZE=2][I]//cálculo do índice do último elemento[/I][/SIZE][SIZE=2]f->vet[fim] = v;[/SIZE][SIZE=2]f->n++;[/SIZE][SIZE=2]}[/SIZE]


A função para retirar um elemento da fila verifica se a fila já está ou não vazia:


[SIZE=2]float fila_retira (Fila* f)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]float v;[/SIZE][SIZE=2]if (fila_vazia(f))[/SIZE][SIZE=2]{ [/SIZE][SIZE=2] [/SIZE][SIZE=2] printf (“Fila vazia\n”);[/SIZE][SIZE=2] exit (1);[/SIZE][SIZE=2] [/SIZE][SIZE=2]}[/SIZE][SIZE=2]v = f->vet[f->ini];[/SIZE][SIZE=2]f->ini = (f->ini + 1) % N;[/SIZE][SIZE=2]f->n--;[/SIZE][SIZE=2]return v;[/SIZE]


Função para verificar se a fila está vazia:


[SIZE=2]int fila_vazia (Fila* f)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]return (f->n == 0);[/SIZE][SIZE=2]}[/SIZE]


Função para liberar toda a memória alocada para a fila:


[SIZE=2]void fila_libera (Fila* f)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]free (f);[/SIZE][SIZE=2]}[/SIZE]




Listas encadeadas


Listas são estruturas de dados que contém um conjunto de blocos de memória que armazenam dados. Esses blocos são encadeados (ligados) por ponteiros, formando uma espécie de “corrente”, onde as peças dessa corrente estão ligadas umas as outras. O encadeamento de listas pode ser de dois tipos: simplesmente encadeada e duplamente encadeada.


Listas simplesmente encadeadas


Listas simplesmente encadeadas possuem um único ponteiro, que apontará para o próximo elemento da lista.
[SIZE=2]struct lista {[/SIZE][SIZE=2]int info;[/SIZE][SIZE=2]struct lista* prox;[/SIZE][SIZE=2]}[/SIZE][SIZE=2]typedef struct lista Lista;[/SIZE]


A função que cria uma lista simplesmente encadeada retornará um NULL do tipo da lista, ou seja, uma lista totalmente vazia:


[SIZE=2]Lista* lst_cria (void)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]return NULL;[/SIZE][SIZE=2]}[/SIZE]


A função de inserção insere novos elementos no início da lista encadeada, pois esta é a maneira mais simples de se inserir elementos numa lista, seja ela simplesmente ou duplamente encadeada. É importante lembrar que uma lista é representada pelo ponteiro para o primeiro elemento dela todos os demais elementos estão encadeados um a um sucessivamente, a partir do primeiro. Ou seja, para se acessar qualquer elemento da lista, basta fornecer o ponteiro para o primeiro elemento e ir percorrendo elemento a elemento até se chegar no elemento desejado.


[SIZE=2]Lista* lst_insere (Lista* l, int i)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]Lista* novo = (Lista*) malloc (sizeof(Lista));[/SIZE][SIZE=2]novo->info = i;[/SIZE][SIZE=2]novo->prox = l;[/SIZE][SIZE=2]return novo;[/SIZE][SIZE=2]}[/SIZE]


Observe que o novo elemento é encadeado aos demais já existentes na lista (caso ela já tenha outros elementos) e a nova lista é representada pelo novo elemento inserido, que passa a ser o 1º da lista.


Função que imprime na tela os elementos da lista:


[SIZE=2]void lst_imprime (Lista* l)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]Lista*p;[/SIZE][SIZE=2]for (p = l; p != NULL; p = p->prox)[/SIZE][SIZE=2] {[/SIZE][SIZE=2] [/SIZE][SIZE=2] printf (“info = %d\n”, p->info);[/SIZE][SIZE=2] }[/SIZE][SIZE=2]}[/SIZE]


Função para verificar se a lista está vazia:


[SIZE=2]int lst_vazia (Lista* l)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]return (l == NULL);[/SIZE][SIZE=2]}[/SIZE]


Para criarmos uma função que busque um determinado elemento, vamos implementá-la de forma a retornar um ponteiro para o elemento buscado. Como sempre, você pode alterar a maneira de retorno de quaisquer das funções aqui mostradas, de forma a se enquadrar melhor ao seu caso.


[SIZE=2]Lista* lst_retira (Lista* l, int v)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]Lista* ant = NULL;[/SIZE][SIZE=2]Lista* p = l;[/SIZE][SIZE=2]while (p != NULL && p->info !=[/SIZE][SIZE=2] v)[/SIZE][SIZE=2] {[/SIZE][SIZE=2] ant = p;[/SIZE][SIZE=2] p = p->prox;[/SIZE][SIZE=2] }[/SIZE][SIZE=2]if (p == NULL)[/SIZE][SIZE=2] return l;[/SIZE][SIZE=2]if (ant == NULL)[/SIZE][SIZE=2] {[/SIZE][SIZE=2] l = p->prox;[/SIZE][SIZE=2] }[/SIZE][SIZE=2]else[/SIZE][SIZE=2] {[/SIZE][SIZE=2]ant->prox = p->prox;[/SIZE][SIZE=2]}[/SIZE][SIZE=2]free (p);[/SIZE][SIZE=2]return l;[/SIZE][SIZE=2]}[/SIZE]


Função para liberar os elementos da lista:


[SIZE=2]void lst_libera (Libera* l)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]Lista* p= l;[/SIZE][SIZE=2]while (p != NULL)[/SIZE][SIZE=2]{[/SIZE][SIZE=2] Lista* t = p->prox;[/SIZE][SIZE=2]free (p);[/SIZE][SIZE=2]p = t;[/SIZE][SIZE=2]}[/SIZE][SIZE=2]}[/SIZE]




Listas duplamente encadeadas


Uma lista duplamente encadeada possui 2 ponteiros em cada nó, um para o próximo elemento e outro para o anterior (ant e prox respectivamente). Isso possibilita “andarmos” para “frente” e para “trás” ao longo da lista.


Logicamente, a estrutura desse tipo de lista é diferente das listas simplesmente encadeadas:


[SIZE=2]struct lista2 [/SIZE][SIZE=2]{[/SIZE][SIZE=2]int info;[/SIZE][SIZE=2]struct lista2* ant;[/SIZE][SIZE=2]struct lista2* prox;[/SIZE][SIZE=2]};[/SIZE][SIZE=2]typedef struct lista2 Lista2;[/SIZE]


Função de inserção no início:


[SIZE=2]Lista2* lst2_insere (Lista2* l, int v)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]Lista2* novo = (Lista2*)malloc(sizeof(Lista2));[/SIZE][SIZE=2]novo->info = v;[/SIZE][SIZE=2]novo->prox = l;[/SIZE][SIZE=2]novo->ant = NULL;[/SIZE][SIZE=2]if (l != NULL)[/SIZE][SIZE=2] l->ant = novo;[/SIZE][SIZE=2]return novo;[/SIZE][SIZE=2]}[/SIZE]


Função de busca:


[SIZE=2]Lista2* lst2_busca (Lista2* l, int v)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]Lista2* p;[/SIZE][SIZE=2]for (p = l; p != NULL; p = p->prox)[/SIZE][SIZE=2] [/SIZE][SIZE=2]if (p->info == v)[/SIZE][SIZE=2] return p;[/SIZE][SIZE=2]return NULL; [/SIZE][SIZE=2][I]//não encontrou o elemento[/I][/SIZE]


Função para retirar um elemento:


[SIZE=2]Lista2* lst2_retira (Lista* l, int v)[/SIZE][SIZE=2]{[/SIZE][SIZE=2]Lista2* p = busca(l, v); [/SIZE][SIZE=2][I]//procura o elemento [/I][/SIZE][SIZE=2]if (p == NULL) [/SIZE][SIZE=2][I]//testa se é o 1º elemento[/I][/SIZE][SIZE=2] return l;[/SIZE][SIZE=2]if (l == p)[/SIZE][SIZE=2] l = p->prox;[/SIZE][SIZE=2]else[/SIZE][SIZE=2] [/SIZE][SIZE=2]p->ant->prox = p->ant;[/SIZE][SIZE=2]if (p->prox != NULL) [/SIZE][SIZE=2][I]//verifica se é o último elemento[/I][/SIZE][SIZE=2] [/SIZE][SIZE=2]p->prox->ant = p->ant;[/SIZE][SIZE=2]free (p);[/SIZE][SIZE=2]return l;[/SIZE][SIZE=2]}[/SIZE]
Além dessas estruturas, é possível criar muitas outras até mesmo juntando estruturas diferentes para se formar uma. Por exemplo, você pode implementar uma pilha ou fila utilizando uma lista encadeada ao invés de um vetor, como fizemos. O retorno das funções podem ser diferentes, de acordo com a necessidade, e assim por diante. As estruturas de dados são “maleáveis” e você pode utilizá-las como quiser, desde que preserve os conceitos fundamentais de cada uma.

Nada do que foi explanado aqui foi copiado de alguém, apenas os códigos das funções que utilizei de um livro de estruturas de dados, chamado “Introdução a Estruturas de Dados”, de Waldemar Celes.

Sintam-se a vontade para fazer sugestões e críticas à respeito do texto, no intuito de melhorar o fácil entendimento do mesmo a todos, principalmente iniciantes. Peço também que não utilizem este tópico para postar códigos escritos com a intenção de avaliarmos de está certo ou não, pois existem vários tópicos aqui no fórum para este fim. Este tópico é apenas para ensinar e tirar dúvidas a respeito das estruturas de dados em C, portanto peço que o utilizem com bom censo.

Um abraço.
  • Curtir 7
Link para o comentário
Compartilhar em outros sites

  • 3 meses depois...

Pessoal, vocês podem comentar sobre o assunto do tópico, caso hajam sujestões para melhorias, postem aí, será de muito bom grado.

Em breve acrescentarei os algoritmos à respeito das Árvores, deixa só terminar esse semestre, pois estou bem enrolado e sem tempo.

Abraços!

Link para o comentário
Compartilhar em outros sites

  • mês depois...

Olá gustavo, obrigado pelo seu comentário, o primeiro após um bom tempo deste tópico :D.

Já que você é iniciante em programação, recomendo fortemente que estude detalhadamente os ponteiros na linguagem C, pois muitos estudantes de programação não dão a devida importância a esse assunto e quando chega nas Estruturas de Dados se sentem muito perdidos, pois aqui esse conceito é largamente explorado.

Bons estudos!

Link para o comentário
Compartilhar em outros sites

  • 3 meses depois...

Não entendo como um professor pode tentar ensinar seus alunos as listas encadeadas sem o conceito de ponteiro...Sinceramente eu nem saberia lhe explicar isso sem ponteiros, deixo essa tarefa para teu próprio professor vir aqui dizer.

Link para o comentário
Compartilhar em outros sites

Aprender o conceito de ponteiros e muito fácil, o problema é manipular a sintaxe deles e muita gente experiente em programação se enrola bastante na hora de lidar com ponteiros. Em C++ isso é mais tranquilo porque a própria linguagem lhe dá uma certa abstração deles, mas eu não saberia lhe explicar como funciona uma lista sem o conceito de ponteiros.

Eles são muito importantes nas listas. Veja um exemplo de lista simplesmente encadeada e uma duplamente encadeada, respectivamente:

listasimplesmenteencade.gif

listaduplamenteencadead.jpg

As setas representam exatamente os ponteiros. Agora, como explicar o funcionamento dessa estrutura sem o aluno saber o que é uma variável ponteiro?

Link para o comentário
Compartilhar em outros sites

  • mês depois...
  • 2 meses depois...
  • DiF removeu o destaque deste tópico
Visitante
Este tópico está impedido de receber novos posts.

Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×
×
  • Criar novo...

Aprenda a ler resistores e capacitores

EBOOK GRÁTIS!

CLIQUE AQUI E BAIXE AGORA MESMO!