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.
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
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.
Código:
#define N 50 struct pilha { int n; float vet[N]; }; typedef struct pilha Pilha;
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.
Código:
Pilha* pilha_cria (void) { Pilha* p = (Pilha*)malloc(sizeof(Pilha)); p->n = 0; //inicializa com zero elementos return p; }
Código:
void pilha_insere (Pilha* p, float v){ if (p->n == N) //verifica se a capacidade do vetor foi esgotada { printf (“Capacidade da pilha estourou!\n”); exit (1); } /*insere o novo elemento na próxima posição livre*/ p->vet[p->n] = v; p->n++; }
Código:
float pilha_remove (Pilha* p) { float v; if (pilha_vazia (p)) { printf (“Pilha está vazia!\n”); exit(1); } /*agora retira o elemento do topo da pilha*/ v = p->vet[p->(n-1)]; p->n--; return v; }
Código:
int pilha_vazia (Pilha* p) { return (p->n == 0); /*se isto for verdade, será retornado o conteúdo dos parêntesis, caso contrário será retornado zero. */ }
Código:
void pilha_libera (Pilha* p) { free(p); }
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 idéia 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:
Código:
Static int incr (int i) { return (i+1)%N; }
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:
Código:
i = (i+1)%N;
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:
Código:
fim = (ini+n)%N;
A estrutura da fila fica então:
Código:
#define N 100 struct fila { int n; int ini; float vet[N]; }
A função que cria a fila:
Código:
Fila* fila_cria (void) { Fila* f = (Fila*) malloc(sizeof(Fila)); f->n = 0; //inicializa a fila vazia; f->ini = 0; //escolhe uma posição inicial; return f; }
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:
Código:
void fila_insere (Fila* f, float v) { int fim; if (f-> == N) { printf (“Fila não tem espaço disponível”); exit (1); } fim = (f->ini + f->n)%N; //cálculo do índice do último elemento f->vet[fim] = v; f->n++; }
A função para retirar um elemento da fila verifica se a fila já está ou não vazia:
Código:
float fila_retira (Fila* f) { float v; if (fila_vazia(f)) { printf (“Fila vazia\n”); exit (1); } v = f->vet[f->ini]; f->ini = (f->ini + 1) % N; f->n--; return v;
Função para verificar se a fila está vazia:
Código:
int fila_vazia (Fila* f) { return (f->n == 0); }
Função para liberar toda a memória alocada para a fila:
Código:
void fila_libera (Fila* f) { free (f); }
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.
Código:
struct lista { int info; struct lista* prox; } typedef struct lista Lista;
A função que cria uma lista simplesmente encadeada retornará um NULL do tipo da lista, ou seja, uma lista totalmente vazia:
Código:
Lista* lst_cria (void) { return NULL; }
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.
Código:
Lista* lst_insere (Lista* l, int i) { Lista* novo = (Lista*) malloc (sizeof(Lista)); novo->info = i; novo->prox = l; return novo; }
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:
Código:
void lst_imprime (Lista* l) { Lista*p; for (p = l; p != NULL; p = p->prox) { printf (“info = %d\n”, p->info); } }
Função para verificar se a lista está vazia:
Código:
int lst_vazia (Lista* l) { return (l == NULL); }
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.
Código:
Lista* lst_retira (Lista* l, int v) { Lista* ant = NULL; Lista* p = l; while (p != NULL && p->info != v) { ant = p; p = p->prox; } if (p == NULL) return l; if (ant == NULL) { l = p->prox; } else { ant->prox = p->prox; } free (p); return l; }
Função para liberar os elementos da lista:
Código:
void lst_libera (Libera* l){ Lista* p= l; while (p != NULL) { Lista* t = p->prox; free (p); p = t; } }
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:
Código:
struct lista2 { int info; struct lista2* ant; struct lista2* prox; }; typedef struct lista2 Lista2;
Função de inserção no início:
Código:
Lista2* lst2_insere (Lista2* l, int v) { Lista2* novo = (Lista2*)malloc(sizeof(Lista2)); novo->info = v; novo->prox = l; novo->ant = NULL; if (l != NULL) l->ant = novo; return novo; }
Função de busca:
Código:
Lista2* lst2_busca (Lista2* l, int v) { Lista2* p; for (p = l; p != NULL; p = p->prox) if (p->info == v) return p; return NULL; //não encontrou o elemento
Função para retirar um elemento:
Código:
Lista2* lst2_retira (Lista* l, int v) { Lista2* p = busca(l, v); //procura o elemento if (p == NULL) //testa se é o 1º elemento return l; if (l == p) l = p->prox; else p->ant->prox = p->ant; if (p->prox != NULL) //verifica se é o último elemento p->prox->ant = p->ant; free (p); return l; }
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.
Fonte: http://forum.clubedohardware.com.br , Escrito por RooT
Membro
Membro desde Fev/2008
Tangamandápio