Listas circulares (Ring Buffer)

Maio 2017



Requisitos

Os tipos de dados
As estruturas
O uso do typedef
Os ponteiros
As funções do usuário
As listas simplesmente encadeadas
As listas duplamente encadeadas

Esta dica tem por objetivo a compreensão das listas circulares. Saiba que, a escolha de implementação será em função de suas necessidades.

Definição

A lista circular é uma espécie de lista simplesmente ou duplamente encadeada, com 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 apontará para o primeiro elemento da lista, em vez do valor NULL, como vimos no caso das listas simplesmente 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 vai recomeçar no primeiro elemento. Em suma, trata-se de uma rotação.

A construção do protótipo 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.
O ponteiro seguinte será obrigatoriamente do mesmo tipo que o elemento, caso contrário ele não poderá 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, é melhor salvar certos elementos: o primeiro elemento, o último elemento, o número de elementos. Para tanto, outra estrutura vai ser utilizada (isso não é imprescindível, as variáveis podem ser utilizadas).
Veja a composição:
typedef struct ListaDetectada {    
Elemento início;
Elemento fim;
int tamanho;
}Liste;


O ponteiro início integra o endereço do primeiro elemento da lista.
O ponteiro de fim terá o endereço do último elemento da lista.
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 ú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

Protótipo da função:
void inicialização (Lista lista);

Dita operação deve ser realizada antes de qualquer outra operação na lista.
Ela inicializa o ponteiro início e o ponteiro de fim sempre através do ponteiro NULL, e o tamanho, com o valor 0.

A função
void inicialização (Lista lista){    
liste > início = NULL;
liste > fim = NULL;
tamanho = 0;
}
a

Inserção de um elemento na lista

Veja o algoritmo de inserção e de backup dos elementos:
Declaração de elementos a serem inseridos
Alocação da memória para o novo elemento
Preenchimento do conteúdo do campo de dados
A atualização dos ponteiros com alvo no primeiro e no último elemento, se necessário.
Caso especial: em uma lista com um único elemento, o primeiro também é o último.
Atualização do tamanho da fila

Inserção em uma lista vazia

Protótipo da função:
int ins_lista_circ_vazia(Lista  lista, char dado);

A função volta em -1 com falha, se não ela retorna 0.

Passos :


Alocação da memória para o novo elemento
Preenchimento do campo de dados do novo elemento
O ponteiro seguinte do novo elemento apontará para ele mesmo (é a etapa que torna a lista circular)
Os ponteiros início e de fim apontarão para o novo elemento
O tamanho é atualizado


A 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 uma lista não vazia

Protótipo da função:
int ins_lista_circ(Lista  lista, Elemento em andamento, char dado);


A função exibe-se novamebne -1 em caso de falha, se não ela retorna 0.

A inserção será efetuada no final da lista.

Passos:


Alocação da memória para o novo elemento

Preenchimento do campo de dados do novo elemento

O ponteiro seguinte do novo elemento aponta para o endereço do primeiro elemento (manter a lista circular)

O ponteiro início não muda

O ponteiro fim aponta para o novo elemento

O tamanho é incrementado com uma unidade


A 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 um elemento da lista

Veja o algoritmo de remoção de um elemento da lista:


Utilização de um ponteiro temporário para salvar o endereço de elementos a serem removidos

O elemento a ser suprimido se encontra depois do elemento em andamento.

Fazer o ponteiro seguinte do elemento em andamento apontar para o endereço do ponteiro seguinte do elemento a ser removido.


Liberar a memória ocupada pelo elemento excluído
Atualizar o tamanho da lista

Para remover um elemento da lista, há várias situações:
1.Remover da lista
2.Remo ver o último elemento da lista

Remoção no início da lista

Protótipo da função:
int remov_lista_circ(Lista lista);
. A função exibe-se em -1 se falha, se não ela volta em 0.

Etapas:


O ponteiro remov_elem conterá o endereço do primeiro elemento.
O ponteiro início apontará para o segundo elemento.
O ponteiro seguinte do último elemento apontará para o primeiro elemento (que era o segundo, antes da remoção.)

O tamanho da lista será decrementado de um elemento


A 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);
liste > tamanho--;
return 0;
}

Remoção em uma lista comum apenas um elemento

Protótipo da função:
int remov_lista_circ_única (Lista lista);


A função volta-1 em caso de falha, caso contrário ela retorna 0.

Etapas:
O ponteiro remov_elem conterá o endereço do elemento (a lista contém apenas um elemento)
O ponteiro início apontará para NULL
O ponteiro fim apontará para NULL
O tamanho da lista será decrementado de um elemento


A 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 inteira você deverá se posicionar no início da lista (isso é possível com o ponteiro início).
Em seguida, ao usar o ponteiro seguinte de cada elemento, a lista é percorrida do primeiro ao último elemento.
Em comparação com as listas simples e duplamente encadeadas, onde a condição de parada é dada pela ponteiro seguinte do último elemento, que equivale a NULL para a lista circular, não há ponto de parada, a menos que você escolha um.

Veja duas variantes de exibição: exibição da lista (do primeiro para o último elemento) e xibição da lista, sem condição de parada (ao infinito)

Exibição da lista (do primeiro ao último elemento)

Utilizaremos o tamanho da lista para a condição de parada.
A 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;
}
}

Exibição da lista sem condição de parada (ao infinito)

A função
/ 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;
}
}

Destruição da lista

Eu utilizei, na destruição da lista, a remoção no início da lista enquanto o tamanho fosse superior a 1; em seguida, a remoção em uma lista com apenas um elemento.

A 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;
}

Veja também

As listas simplesmente encadeadas
As listas duplamente encadeadas
As pilhas
As filas

Veja também

Artigo original publicado por . Tradução feita por pintuda. Última modificação: 6 de outubro de 2016 às 09:10 por ninha25.
Este documento, intitulado 'Listas circulares (Ring Buffer)', está disponível sob a licença Creative Commons. Você pode copiar e/ou modificar o conteúdo desta página com base nas condições estipuladas pela licença. Não se esqueça de creditar o CCM (br.ccm.net) ao utilizar este artigo.