Estruturas de Dados - Pilhas, Filas, Listas encadeadas

RooT · 11 de agosto de 2009

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:

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

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:

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.

RooT · 7 de dezembro de 2009

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!

gustavo 555 · 17 de janeiro de 2010

Bom, RooT não li o topico inteiro, até porque só de ler o titulo não entendi bulhufas. Estou começando e creio que logo entenderei o que você disse aqui...

Mas só pela iniciativa já esta de parabens!

Até mais!

RooT · 17 de janeiro de 2010

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

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!

baciotti · 1 de maio de 2010

Estou aprendendo listas ligadas agora e preciso fazer um exercicio em C++ com funcoes (subrotins) para inserir itens, retirar, listar alem do main.

Isso tudo SEM PONTEIROS, porque a gente ainda nao aprendeu.

Alguma sugestao ?

RooT · 2 de maio de 2010

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.

baciotti · 2 de maio de 2010

Sim realmente é estranho, segundo palavras dele, ele só quer passar o conceito báscio de listas primeiramente.

O proximo passo é ensinar ponteiros.

Se bem que pelo que ouvi dizer ponteiros nao sao estão dificeis de aprender ne?

RooT · 2 de maio de 2010

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:

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

massaaki · 15 de junho de 2010

Parabens pelo topico, acredito que vá ajudar muita gente, pois também já tive problemas com Lista Ligada.

socho · 1 de setembro de 2010

valeu RooT muito bom o seu tópico, estou cursando o segundo semestre de sistemas para internet e estava precisando muito aprender sobre Pilhas, Filas, Listas encadeadas na materia de estruturas de dados muito bom mesmo valeu:lol: