Listas circulares (Ring Buffer)
Listas circulares, também chamados de ring buffer, são estruturas de dados que tem como principal diferencial a devolução de elementos consumidos para o final do buffer. Esse artigo tem o objetivo de apresentar os conceitos básicos das listas circulares ao usuário para que ele possa entender seu uso e suas funções.
Requisitos
Os requisitos das listas circulares são os seguintes: os tipos de dados, as estruturas, o uso do typedef, os ponteiros, a função usuário, as listas simplesmente encadeadas e as listas duplamente encadeadas.
Definição
A lista circular é uma espécie de lista simples ou duplamente encadeada, mas que possui uma característica adicional para o deslocamento na lista: ela não tem fim.
Para tornar a lista interminável, o ponteiro seguinte do último elemento sempre apontará para o primeiro elemento da lista, em vez do valor NULL, como ocorre nas listas simples e duplamente encadeadas.
Nas listas circulares, nunca chegaremos a uma posição a partir da qual não poderemos mais nos mover. Chegando ao último elemento, o deslocamento recomeça no primeiro elemento. Em suma, ela funciona em rotação, daí seu nome de circular.
Como construir o modelo de um elemento da lista
Para determinar um elemento da lista, será usado o tipo struct. O elemento da lista conterá um campo dado e um ponteiro seguinte, que será obrigatoriamente do mesmo tipo que o elemento. Caso
contrário, ele será incapaz de apontar para o elemento. O ponteiro seguinte permitirá o acesso ao próximo elemento.
typedef struct ElementoLista {
char dado;
struct ElementoLista seguinte;
}Elemento;
Para controlar a lista, o melhor é salvar certos elementos: o primeiro elemento, o último elemento e o número de elementos. Para tanto, outra estrutura será utilizada. Esse procedimento não é obrigatório, já que você pode utilizar variáveis.
typedef struct ListaDetectada {
Elemento início;
Elemento fim;
int tamanho;
}Liste;
O ponteiro início possui o endereço do primeiro elemento da lista. O ponteiro fim tem o endereço do último elemento da lista e a variável tamanho abrigará o número de elementos.
Seja qual for a posição na lista, os ponteiros início e fim sempre apontam, respectivamente, para o primeiro e o último elemento. O campo tamanho abrigará o número de elementos da lista, independentemente da operação efetuada na lista.
Operações nas listas circulares
Inicialização
Modelo da função:
void inicialização (Lista lista);
Essa operação deve ser realizada antes de qualquer outra operação na lista. Ela posiciona os ponteiros início e fim no valor NULL e seu tamanho em valor 0.
Função:
void inicialização (Lista lista){
liste > início = NULL;
liste > fim = NULL;
tamanho = 0;
}
Inserção de elemento na lista
A seguir, vejamos o algoritmo de inserção e o registro dos elementos: declaração de elementos a ser inseridos, alocação da memória para o novo elemento, preenchimento do conteúdo do campo de dados, atualização dos ponteiros para o primeiro e último elemento, se necessário. Em listas com apenas um elemento, o primeiro e o último elementos são o mesmo.
Inserção em lista vazia
Modelo da função:
int ins_lista_circ_vazia(Lista lista, char dado);
A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0.
Etapas: alocação da memória para o novo elemento, preenchimento do campo de dados do novo elemento, ponteiro seguinte do novo elemento apontará para ele mesmo (é a etapa que torna a lista circular), ponteiros início e fim apontarão para o novo elemento e o tamanho é atualizado:
Função:
/ inserção em uma lista vazia /
int ins_lista_circ_vazia(Lista lista, char dado){
Elemento novo_elemento;
if (( novo_elemento = (Elemento ) malloc (sizeof (Elemento)))
== NULL)
return -1;
if ((novo_elemento > dado = (char ) malloc (50 sizeof (char)))
== NULL)
return -1;
strcpy (novo_elemento > dado, dado);
novo_elemento > seguinte = novo_elemento;
liste > início = novo_elemento;
liste > fim = novo_elemento;
liste > tamanho++;
return 0;
}
Inserção em lista não vazia
Modelo da função:
int ins_lista_circ(Lista lista, Elemento em andamento, char dado);
A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0. A inserção será efetuada no final da lista.
Etapas: alocação da memória para o novo elemento, preenchimento do campo de dados do novo elemento, ponteiro seguinte do novo elemento aponta para o endereço do primeiro elemento (manter a lista circular), ponteiro início não muda, ponteiro fim aponta para o novo elemento e o tamanho aumenta em uma unidade.
Função:
/ inserção em uma lista não vazia /
int ins_lista_circ(Lista lista, Elemento em andamento, char dado){
Elemento novo_elemento;
if ((novo_elemento = (Elemento ) malloc (sizeof (Elemento)))
== NULL)
return -1;
if ((novo_elemento > dado = (char ) malloc (50 sizeof (char)))
== NULL)
return -1;
strcpy (novo_elemento > dado, dado);
if(em andamento != lisa > fim)
return -1;
novo_elemento > seguinte = em andamento > seguinte;
em andamento > seguinte = novo_elemento;
lista > fim = novo_elemento;
lista > tamanho++;
return 0;
}
Remoção de elemento da lista
Vejamos o algoritmo de remoção de um elemento da lista: uso de um ponteiro temporário para salvar o endereço de elementos a ser removidos, o elemento a ser suprimido está depois do elemento atual.
O ponteiro seguinte do elemento atual aponta para o endereço do ponteiro seguinte do elemento a ser removido. Também será liberada memória ocupada pelo elemento excluído e o tamanho da lista será atualizado.
Para eliminar um elemento da lista, há duas situações: eliminar um elemento dentro da lista ou eliminar o último elemento da lista.
Remoção no início da lista
Modelo da função:
int remov_lista_circ(Lista lista);
.
A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0. A inserção será efetuada no final da lista.
Etapas: ponteiro remov_elem conterá o endereço do primeiro elemento, ponteiro início apontará para o segundo elemento, ponteiro seguinte do último elemento apontará para o primeiro elemento, que era o segundo antes da remoção</bold>. O tamanho da lista perde uma unidade.
Função:
/ remoção no início da lista /
int remov_lista_circ(Lista lista){
if (lista > tamanho < 2)
return -1;
Elemento remov_elemento;
remov_elemento = lista > início;
lista > início = lista > início > seguinte;
lista > fim > seguinte = lista > início;
free (remov_elemento > dado);
free (remov_elemento);
lista > tamanho--;
return 0;
}
Remoção em lista com apenas um elemento
Modelo da função:
int remov_lista_circ_única (Lista lista);
A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0. A inserção será efetuada no final da lista.
Etapas: ponteiro remov_elem conterá o endereço do elemento (único da lista), ponteiro início apontará para NULL, ponteiro fim apontará para NULL. O tamanho da lista perde uma unidade.
Função:
/ remoção em uma lista com apenas um elemento/
int remov_lista_circ_única(Lista lista){
if (lista > tamanho != 1)
return -1;
Elemento remov_elemento;
remov_elemento = lista > início;
lista > início = NULL;
lista > fim = NULL;
free (remov_elemento > dado);
free (remov_elemento);
lista > tamanho--;
return 0;
}
Exibir a lista
Para exibir a lista completa, você deve se posicionar no início da lista (com o ponteiro início). Em seguida, com o ponteiro seguinte de cada elemento, a lista é percorrida do primeiro ao último elemento.
Em comparação com as listas simples e duplamente encadeadas, nas quais a condição de parada é dada pela ponteiro seguinte do último elemento - equivalente a NULL - na lista circular, não há ponto de parada, a menos que você escolha um.
Vejamos duas variações de visualização: exibição da lista (do primeiro ao último elemento) e exibição da lista sem condição de parada (indefinidamente).
Exibir do primeiro ao último elemento
Utilizaremos o tamanho da lista para a condição de parada.
Função:
/ exibição da lista /
void exibe (Lista lista){
Elemento em andamento;
em andamento = lista > início;
int i;
for(i=0;i<lista > tamanho;++i){
printf ("%p - %s\n", em andamento, em andamento > dado);
em andamento = em andamento > seguinte;
}
}
Exibir sem condição de parada
Função:
/ percorrer a lista indefinidamente/
void exibe_infinito (Lista lista){
Elemento em andamento;
em andamento = lista > início;
while (1){
printf ("%p - %s\n", em andamento, em andamento > dado);
em andamento = em andamento > seguinte;
}
}
Destruição da lista
Para destruir toda a lista, utilizamos a remoção no início da lista pois o tamanho é superior a 1. Logo depois, eliminamos uma lista com apenas um elemento.
Função:
/ destruir a lista /
void destruir (Lista lista){
while (lista > tamanho > 0){
if(lista>tamanho > 1)
remov_lista_circ (lista);
else
remov_lista_circ_única(lista);
}
}
Exemplo completo
lista_circ.h
/ ---------- lista_circ.h ----------- /
typedef struct ElementoListaCirc {
char dado;
struct ElementoListaCirc seguinte;
} Elemento;
typedef struct ListaDetectadaCirc {
Elemento início;
Elemento fim;
int tamanho;
} Liste;
/ inicialização de la lista /
void inicialização (Lista lista);
/ INSERÇÃO /
/ inserção em uma lista vazia /
int ins_lista_circ_vazia(Lista lista, char dado);
int ins_lista_circ(Lista lista, Elemento em andamento, char dado);
/ REMOÇÃO /
int remov_lista_circ (Lista lista);
int remov_lista_circ_única (Lista lista);
int menu (Lista lista);
void exibe (Lista lista);
void exibe_infinito (Lista lista);
void destruir (Lista lista);
/ -------- FIM lista_circ.h --------- /
lista_circ_function.h
/\
lista_circ_function.h
\/
void inicialização (Lista lista){
lista > início = NULL;
lista > fim = NULL;
lista > tamanho = 0;
}
/ Inserção em uma lista vazia /
int ins_lista_circ_vazia(Lista lista, char dado){
Elemento novo_elemento;
if ((novo_elemento = (Elemento ) malloc (sizeof (Elemento)))
== NULL)
return -1;
if ((novo_elemento > dado = (char ) malloc (50 sizeof (char)))
== NULL)
return -1;
strcpy (novo_elemento > dado, dado);
novo_elemento > seguinte = novo_elemento;
liste > início = novo_elemento;
liste > fim = novo_elemento;
liste > tamanho++;
return 0;
}
/ inserção em uma lista não vazia /
int ins_lista_circ(Lista lista, Elemento em andamento, char dado){
Elemento novo_elemento;
if ((novo_elemento= (Elemento ) malloc (sizeof (Elemento)))
== NULL)
return -1;
if ((novo_elemento > dado = (char ) malloc (50 sizeof (char)))
== NULL)
return -1;
strcpy (novo_elemento > dado, dado);
if(em andamento!= lista > fim)
return -1;
novo_elemento > seguinte = em andamento > seguinte;
em andamento > seguinte = novo_elemento;
lista > fim = novo_elemento;
lista > tamanho++;
return 0;
}
/ remoção no início da lista /
int remov_lista_circ(Lista lista){
if (lista > tamanho < 2)
return -1;
Elemento remov_elemento;
remov_elemento = lista > início;
lista > início = lista > início > seguinte;
lista>fim > seguinte = lista > início;
free (remov_elemento > dado);
free (remov_elemento);
liste > tamanho--;
return 0;
}
/ remoção em uma lista com um único elemento/
int remov_lista_circ_única (Lista lista){
if (lista > tamanho != 1)
return -1;
Elemento remov_elemento;
remov_elemento = lista > início;
lista > início = NULL;
lista > fim = NULL;
free (remov_elemento > dado);
free (remov_elemento);
lista > tamanho--;
return 0;
}
/ Exibição da lista /
void exibe (Lista lista){
Elemento em andamento;
em andamento = lista > início;
int i;
for(i=0;i<lista > tamanho;++i){
printf ("%p - %s\n", em andamento, em andamento > dado);
em andamento = em andamento > seguinte;
}
}
/ percorrer a lista ao infinito/
void exibe_infinito (Lista lista){
Elemento em andamento;
em andamento = lista > início;
while (1){
printf ("%p - %s\n", em andamento, em andamento > dado);
em andamento = em andamento > seguinte;
}
}
/ destruir a lista /
void destruir (Lista lista){
while (lista > tamanho > 0){
if(lista > tamanho > 1)
remov_lista_circ (lista);
else
remov_lista_circ_única (lista);
}
}
int menu (Lista lista){
int escolha; printf(" MENU \n");
if (lista > tamanho == 0){
printf ("1. Adição do primeiro elemento\n");
printf ("2. Fechar\n");
}else {
printf ("1. Adição de um elemento\n");
printf ("2. Remoção no inicio (a lista deve ter pelo menos 2 elementos)\n");
printf ("3. Remoção em uma lista com apenas um elemento\n");
printf ("4. Exibe lista circular\n");
printf ("5. Exibe lista circular [Ctrl+C] para fechar o programa\n");
printf ("6. Destruir a lista\n");
printf ("7. Fechar\n");
}
printf ("\n\nFaça sua escolha: ");
scanf ("%d", &escolha);
getchar();
if(liste > tamanho == 0 && escolha == 2)
escolha = 7;
return escolha;
}
/ -------- FIM lista_circ_function --------- /
lista_circ.c
/\
liste_circ.c
\/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "lista_circ.h"
#include "lista_circ_function.h"
int main (void)
{
char escolha;
char nome;
Lista lista;
Elemento em andamento;
if ((lista = (Lista ) malloc (sizeof (Lista))) == NULL)
return -1;
if ((nome = (char ) malloc (50)) == NULL)
return -1;
em andamento = NULL;
escolha = 'o';
inicialização (lista);
while (escolha!= 7){
escolha = menu (lista);
switch (escolha){
casa 1:
printf ("Entre um elemento: ");
scanf ("%s", nome);
getchar ();
if(lista > tamanho == 0)
ins_lista_circ_vazio (lista,nome);
else
ins_lista_circ (lista,lista > fim,nome);
printf ("%d elementos: início=%s, fim=%s\n",
lista > tamanho,
lista > início > dado,
lista > fim > dado);
exibe (lista);
break;
casa 2:
if(lista > tamanho < 2)
break;
remov_lista_circ (liste);
if (lista > tamanho != 0)
printf ("%d elementos:início=%s, fim=%s\n",
lista > tamanho,
lista > início > dado,
lista > fim > dado);
exibe (lista);
break;
casa 3:
if(lista > tamanho != 1)
break;
remov_lista_circ_única(liste);
printf("A lista está vazia\n");
break;
casa 4:
exibe (lista);
break;
casa 5:
exibe_infinito (lista);
break;
casa 6:
destruir (lista);
printf ("a lista foi destruída: %d elementos\n", lista > tamanho);
break;
}
}
return 0;
}
Foto: © Everypixel.
- Lista circular
- Lista circular em c - Melhores respostas
- Lista encadeada circular - Melhores respostas
- Lista simplesmente encadeada - Dicas -C
- Lista duplamente encadeada em c - Dicas -C
- Lista little alchemy - Dicas -Videogames
- Lista de contatos gmail - Dicas -Gmail
- Email em lista de espera - Fórum E-mail
Assine nossa newsletter!
