C++ Lista Circular Simplesmente Encadeada

[alefsilvaf]

Olá, programadores.

Tenho tido dificuldade pra entender sobre manipulação de uma lista circular, uma vez que os conteúdos encontrados na interwebs sobre o assunto mudam bastante de artigo pra artigo.

O que mais me incomoda é que não consigo entender como implementar uma função que inverta uma lista circular, fazendo com que, por exemplo:

Ela passe de 1-2-3-4-5 para 5-4-3-2-1.

Todo material que encontrei fez a função sem ter uma "cabeça", mesmo assim tentei desenvolver o algoritmo, e ele inverte uma lista quase que por completo, com exceção do primeiro elemento.

Alguém pode me dar uma dica de como "consertar" o algoritmo para que ele faça direito sua função de inverter?

 

#include<bits/stdc++.h>
#define TRUE 1
#define FALSE 0
using namespace std;
struct no
{
    int dado;
    struct no *prox;
};
typedef struct
{
    struct no *inicio;
    struct no *fim;
} listaC;

void create(listaC *q)
{
    q->inicio=NULL;
    q->fim=NULL;
}

int isEmpty(listaC q)
{
    if (q.inicio==NULL)
        return (TRUE);
    else
        return (FALSE);
}

int insereinicio(listaC *q, int d)
{
    struct no *aux;
    if (q->inicio == NULL)
    {
        aux= (struct no *) malloc(sizeof(struct no));
        aux->dado = d;
        q->inicio = aux;
        q->fim = aux;
        aux->prox = q->inicio;
        return(TRUE);
    }
    aux= (struct no *) malloc(sizeof(struct no));
    aux->dado = d;
    aux->prox = q->inicio;
    q->inicio = aux;
    q->fim->prox = aux;
    return(TRUE);
}

void inverter(listaC *resp){
    no* atual = resp->inicio; 
    resp->inicio = NULL; 
    do{ 
      
        no* corrente = atual; 
        atual = atual->prox; 
        corrente->prox = resp->inicio; 
        resp->inicio = corrente; 
      
    }while (atual);  
} 

void imprime(listaC q)
{
    struct no *aux;
    if (!isEmpty(q))
    {
        aux = q.inicio;
        if (aux != q.fim)
        {
            do
            {
                printf("%d->%d ", aux->dado,aux->prox->dado);

                aux = aux->prox;
            }
            while (aux != q.inicio);
        }
        else
            printf("%d->NULL ", aux->dado);
    }
    else
        cout<<"Lista vazia..."<<endl;

}

int main()
{
    int x,q,res=0;
    listaC L;
    create(&L);
  	insereinicio(&L,1);
	insereinicio(&L,2);
	insereinicio(&L,3);
	insereinicio(&L,4);
	insereinicio(&L,5);
		cout<<"Antes de inverter: \n";
	imprime(L);
    inverter(&L);
		cout<<"\nDepois de inverter: \n";
	imprime(L);	
 	return 0;
}

 

Desde já, obrigado.

[alefsilvaf]

void inverter(listaC *resp){
    no* atual = resp->inicio; 
    resp->inicio= NULL; 
    while (atual) { 
      
        no* corrente = atual; 
        atual = atual->prox; 
        corrente->prox = resp->inicio; 
        resp->inicio = corrente; 
      
    } 
    swap(resp->inicio,resp->fim);
} 

Consegui saciar o que pedia no exercício, não sei se é o jeito certo, mas foi! Então vim compartilhar a solução. Se você que está lendo conhecer outra maneira, por favor, pode dizer.

[arfneto]

Olá

 

listas circulares em especial quando tem uma capacidade limitada --- buffers circulares comuns em áudio/vídeo/transmissão --- são uma estrutura curiosa, em especial quando tem iteradores e a estrutura ainda não está cheia.

 

Mas no caso de uma lista encadeada circular talvez seja mais simples ter ao inserir já dois ponteiros e um indicador marcando qual o sentido atual, e uma disciplina marcando se uma operação de inserção ocorre no fim ou no começo, que vai ser o mesmo lugar: um novo elemento será o primeiro ou o último --- como em pilhas FIFO/LIFO --- e o resto. E o sentido inicial seria um prâmetro agregado à estrutura, como a capacidade e o tamanho

 

O resto da implementação seguiria igual, eu acho,escrevendo sem pensar muito  

adicionado 8 minutos depois

 Então tem uma necessidade objetiva de inverter uma lista encadeada apenas, e não está de fato usando uma lista circular? 

Nesse caso basta adaptar a função que lista imprime*(). Como não tem ponteiros para o outro lado ao passar para cada terceiro nó pode inverter os ponteiros dos dois anteriores porque não há outro vínculo exceto o único ponteiro mesmo. O início da lista vai ao final apontar claro para NULL, e ao encontrar o fim da lista original esse será o novo início...

 

Pode testar com a técnica que se usa para classificar listas por vários critérios quando a estrutura é muito grande: cria uma nova lista sem estrutura, apontando apenas para os nós da lista original, e assim pode conferir o resultado sem risco porque se zoar os ponteiros antes de testar tudo já era: deve perder tudo.

[alefsilvaf]

9 minutos atrás, arfneto disse:

Olá

 

listas circulares em especial quando tem uma capacidade limitada --- buffers circulares comuns em áudio/vídeo/transmissão --- são uma estrutura curiosa, em especial quando tem iteradores e a estrutura ainda não está cheia.

 

Mas no caso de uma lista encadeada circular talvez seja mais simples ter ao inserir já dois ponteiros e um indicador marcando qual o sentido atual, e uma disciplina marcando se uma operação de inserção ocorre no fim ou no começo, que vai ser o mesmo lugar: um novo elemento será o primeiro ou o último --- como em pilhas FIFO/LIFO --- e o resto. E o sentido inicial seria um prâmetro agregado à estrutura, como a capacidade e o tamanho

 

O resto da implementação seguiria igual, eu acho,escrevendo sem pensar muito  

Eu tenho as funções de inserir no fim e no começo, ainda não sei como definir a direção, mas vou ter que descobrir háháhá ( ) o próximo exercício pede que eu simule duas engrenagens com listas circulares duplamente encadeadas e gire elas, uma no sentido horário e outro no anti-horário até que o inicio de ambas se encontrem em um ponto kkk

[arfneto]

4 minutos atrás, Aleffeels disse:

Eu tenho as funções de inserir no fim e no começo, ainda não sei como definir a direção, mas vou ter que descobrir háháhá ( ) o próximo exercício pede que eu simule duas engrenagens com listas circulares duplamente encadeadas e gire elas, uma no sentido horário e outro no anti-horário até que o inicio de ambas se encontrem em um ponto kkk

 

Essa é uma situação folclórica mas um pouco simplificada porque as duas listas que serão abstração das engrenagens então já devem ser criadas com tamanho fixo e completas, e com talvez um único dado que seria o número do dente.  divertido isso

[alefsilvaf]

2 minutos atrás, arfneto disse:

 

Essa é uma situação folclórica mas um pouco simplificada porque as duas listas que serão abstração das engrenagens então já devem ser criadas com tamanho fixo e completas, e com talvez um único dado que seria o número do dente.  divertido isso

Isso mesmo! E as duas são obrigatoriamente de tamanhos diferentes pra ficar mais legal. Meu professor é um crânio!

[Ansi C]

8 horas atrás, Aleffeels disse:

void inverter(listaC *resp){
    no* atual = resp->inicio; 
    resp->inicio= NULL; 
    while (atual) { 
      
        no* corrente = atual; 
        atual = atual->prox; 
        corrente->prox = resp->inicio; 
        resp->inicio = corrente; 
      
    } 
    swap(resp->inicio,resp->fim);
} 

Consegui saciar o que pedia no exercício, não sei se é o jeito certo, mas foi! Então vim compartilhar a solução. Se você que está lendo conhecer outra maneira, por favor, pode dizer. 

 

Já foi dito que início e fim são os mesmos.

Logo não tem null. ( confuso?)

 

Essa função se circular teria loop infinito.

 

Nos artigos em algum lugar foi mencionado que o termo circular descreve o comportamento do tipo. Em resumo a menor lista circular tem 1 nó (um ponto inicial que também é o final).

 

O teste para continuar é se atual é diferente de início.

 

[arfneto]

35 minutos atrás, Mauro Britivaldo disse:

Já foi dito que início e fim são os mesmos.

Logo não tem null. ( confuso?)

 

Essa função se circular teria loop infinito.

 

Nos artigos em algum lugar foi mencionado que o termo circular descreve o comportamento do tipo. Em resumo a menor lista circular tem 1 nó (um ponto inicial que também é o final).

 

O teste para continuar é se atual é diferente de início

 

Sim. Exatamente como descreveu.

 

Por definição uma lista circular é assim, circular, e o processamento segue infinitamente. Não tem um NULL exceto para o momento em que a lista está vazia.

 

A menor lista circular tem um nó, que é o caso de qualquer lista.

 

A gente usa muito isso em processos em que a prioridade é do lado do atendimento, então você tem uma fila em que você não recusa ninguém, atende o primeiro e eventualmente descarta o mais antigo quando atinge uma certa capacidade.