Lista ligada circular em C ++

Podemos colocar itens na lista ligada circular de qualquer lugar da lista; No entanto, não podemos inserir elementos na matriz de qualquer lugar da lista, pois ela está em memória contígua. O último elemento em uma lista ligada circular mantém o endereço do próximo elemento, enquanto o último elemento mantém o endereço do primeiro elemento. Uma corrente circular é formada pelos elementos que se referem um ao outro em um padrão circular.

Como a lista ligada circular tem um tamanho dinâmico, a memória pode ser alocada apenas quando for necessário. O artigo demonstrará a lista ligada circular com as ilustrações do programa C ++ em C++.

Aplicação de lista ligada circular

Uma lista ligada circular é aquela em que todos os nós estão conectados em um círculo. Não há elemento nulo na lista ligada circular. Um ponto de partida pode ser qualquer nó. A partir de qualquer lugar da lista, podemos atravessar toda a lista. Tudo o que precisamos fazer agora é esperar até que o primeiro nó seja alcançado novamente. Lá temos algumas aplicações de uma lista ligada circular da seguinte maneira:

1. Nossos computadores pessoais, que executam vários aplicativos, são um exemplo de como a lista ligada circular é utilizada na vida real. Todos os aplicativos em execução são armazenados em uma lista ligada circular, e o sistema operacional atribui a cada um certo horário para executar. O sistema operacional continua a dar um loop sobre a lista vinculada até que todos os programas sejam executados.
2. Jogos multiplayer são outro excelente exemplo. Todos os jogadores são armazenados em uma lista ligada circular, com o ponteiro avançando quando a oportunidade de cada jogador expirar.
3. A fila circular pode ser criada usando uma lista ligada circular também. Devemos manter os dois ponteiros, na frente e na traseira, na memória o tempo todo em uma fila, mas apenas um ponteiro é necessário em uma lista ligada circular.

Exemplo 1: Criação de travessia de lista ligada circular em C++

A única diferença é que, em uma lista ligada circular, o nó na última posição terá seu próximo link para a cabeça da lista, enquanto que, em uma lista linear vinculada, o último nó teria seu próximo ponto para o fundo do fundo do Lista. A implementação do código de travessia da lista ligada circular em C ++ é mostrada abaixo.

Na primeira etapa, definimos uma classe como "nó", na qual declaramos uma variável int como "mydata". A variável "mydata" é os dados para o nó. O ponteiro também é declarado nesta classe como "próximo" para o ponteiro para o próximo nó na lista ligada circular.

Após a classe "Nó", temos uma função chamada "push", que insere o nó no início da lista ligada circular. Definimos o construtor, que passa a referência do ponteiro Head_Node da classe "Nó" e da variável "mydata" como um parâmetro. O novo ponteiro é criado como "MyPtr", que chamou e atribuiu o "nó".

Então, o ponteiro temporário é declarado como "temp", que tem o head_node. Existem ponteiros como "ptr1" e "ptr2" que são chamados "mydata" e ponteiro "a seguir" e levam seus endereços. Depois disso, temos uma declaração IF na qual há apenas Head_Node, e é mantida nula. Se a lista ligada circular for nula, adicione o próximo ao último nó com a ajuda de um loop de um tempo. Caso contrário, a declaração else será executada na qual a cabeça aponta para o primeiro nó da lista.

Em seguida, criamos outra função como "Lista de exibição" e, no construtor desta função, acabamos de passar pela cabeça do nó da lista ligada circular. A função exibirá os nós em uma lista ligada circular por meio de um loop de fazer-depois da instrução IF, que tem a condição de que a cabeça do nó não deve ser igual a NULL.

Finalmente, existe o método principal, que testará a implementação descrita anteriormente. A cabeça do ponteiro da classe “Nó” foi definida como “NULL” no método principal. Em seguida, adicione os dados à lista vinculada com a ajuda do método push (). A "cabeça" é passada para a função "DisplayList", que mostrará a lista ligada circular.

#incluir
usando namespace std;
Nó da classe

público:
int mydata;
Nó *a seguir;
;
push void (nó ** head_node, int mydata)

Nó *myptr1 = new node ();
Nó *temp = *head_node;
Myptr1-> mydata = mydata;
Myptr1-> next = *head_node;
if (*head_node != Nulo)

enquanto (temp-> próximo != *head_node)
temp = temp-> a seguir;
temp-> próximo = myptr1;

outro
Myptr1-> next = myptr1;
*head_node = myptr1;

Void DisplayList (nó *cabeça)

Nó *temp = cabeça;
if (cabeça != Nulo)

fazer

cout
enquanto (temp != cabeça);


int main ()

Nó *head = null;
push (& Head, 2001);
push (& Head, 2015);
push (& Head, 2006);
push (& Head, 2022);
cout<< "Circular Linked List:\n ";
Displaylist (cabeça);
cout<< "\n ";
retornar 0;

A lista ligada circular implementada na saída de código acima é exibida na imagem a seguir.

Exemplo2: Divida a lista ligada circular em duas metades em C++

O programa a seguir torna a divisão de uma lista ligada circular em duas partes possíveis. Vejamos a implementação de como dividimos a lista ligada circular em C++.

Primeiro, temos um "nó" de classe onde definimos uma variável "itens" e o ponteiro "próximo" do nó. Os membros da classe “nó” são públicos neste programa. Em seguida, construímos uma função chamada "Halvelist", na qual dividimos a lista desde o início com a cabeça em duas listas. O Head1_Node e Head2_Node são referências aos dois nós da cabeça do Linked Lists resultante.

Na função, declaramos dois ponteiros, "S_PTR" e o "F_PTR", que tem o chefe da lista vinculada. Se a instrução IF for usada para o nó da cabeça que contém um valor nulo, temos um loop de tempo que afirma que F_PTR-> Next se tornará cabeça se a lista circular tiver nós ímpares, e F_PTR-> Next-> Next se tornará cabeça se o A lista contém nós até os nós.

Após o while loop, usamos novamente a declaração IF na qual a condição é “Se a lista contiver números pares de elementos, F_PTR deve ser movido e definir o ponteiro Head1_Node da primeira metade”. Na instrução IF a seguir, definimos o Head2_Node para a segunda metade da lista vinculada.

Atribuímos o S_PTR-> ao lado do F_PTR-> Em seguida para tornar o segundo meio-circular da lista e, em seguida, S_PTR-> é mantido igual à cabeça da lista e faz com que o primeiro meio círculo.

A segunda função é criada como "push", que é utilizada para inserir um nó no início de uma lista ligada circular com esta função. Na função, a condição implica se o head_node da lista ligada circular não for nula e depois definido ao lado do último nó. A terceira função, "DisplayList", é gerada para a lista vinculada circular a ser exibida.

Em seguida, temos a função principal, onde inicializamos a cabeça, Head1_Node e Head2_Node vazios. O método push é usado para inserir os valores na lista vinculada e, através do comando cout, a lista ligada circular e a lista ligada circular dividida serão exibidas.

#incluir
usando namespace std;
MyNode de classe

público:
Itens int;
MyNode *a seguir;
;
halvelist void (MyNode *Head, MyNode ** Head1_Node, MyNode ** Head2_Node)

MyNode *s_ptr = head;
MyNode *f_ptr = head;
if (cabeça == null)
retornar;
while (f_ptr-> próximo != Head &&
F_PTR-> Próximo-> Próximo != cabeça)

F_PTR = F_PTR-> NEXT-> NEXT;
S_PTR = S_PTR-> NEXT;

if (f_ptr-> próximo-> next == Head)
F_PTR = F_PTR-> NEXT;
*head1_node = head;
If (Head-> Próximo != cabeça)
*head2_node = s_ptr-> próximo;
f_ptr-> próximo = s_ptr-> próximo;
s_ptr-> próximo = cabeça;

void push (myNode ** head_node, int itens)

MyNode *newPtr = new MyNode ();
MyNode *temp = *head_node;
Newptr-> itens = itens;
Newptr-> next = *head_node;
if (*head_node != Nulo)

enquanto (temp-> próximo != *head_node)
temp = temp-> a seguir;
temp-> next = newptr;

outro
Newptr-> next = newPtr; / *Para o primeiro myNode */
*head_node = newptr;

Void DisplayList (MyNode *Head)

MyNode *temp = cabeça;
if (cabeça != Nulo)

cout<fazer
cout while (temp != cabeça);


int main ()

int myListsize, eu;
MyNode *Head = NULL;
MyNode *head1 = null;
MyNode *head2 = null;
push (& Head, 10);
push (& Head, 90);
push (& Head, 40);
push (& Head, 70);
cout<< "Circular Linked List";
Displaylist (cabeça);
Halvelist (Head, & Head1, & Head2);
cout<< "\nFirst Halve Circular Linked List";
DisplayList (Head1);
cout<< "\nSecond Halve Circular Linked List";
DisplayList (Head2);
retornar 0;

Aqui temos a saída da lista Circular Linkada original, a saída da primeira lista vinculada semi-circular e a segunda metade da lista ligada circular.

Exemplo 3: Classificação da lista ligada circular em C++

Na primeira etapa, temos uma classe “NodeList”, que contém variáveis ​​e ponteiros de membros na classe. Em seguida, criamos uma função "SortInsertion", que insere um novo nó em uma lista classificada. Esta função requer um ponteiro para o nó da cabeça porque pode alterar a cabeça da lista vinculada à entrada.

Depois disso, temos uma declaração IF para a lista de nodelas, que contém apenas um nó. O ponto de Head_Node para o novo nó. No caso, se a declaração, atribuímos os dados da lista de nodelas à corrente.

Aqui, um novo nó é adicionado antes do nó da cabeça. O bloco if-else tem um loop de tempo que tem uma condição; Se o valor for menor que o valor da cabeça, o próximo ou o último nó deve ser alterado. O loop while apenas identificará o nó antes do ponto de inserção.

Depois disso, fizemos um new_nodelist, o próximo nó que localiza o próximo nó do ponteiro. Então, atual-> Em seguida, temos que mudar a localização do ponteiro para o próximo. Para imprimir os nós da lista vinculada, chamamos uma função de "Showlist".

No final, temos a principal função em que inicializamos uma matriz e iteramos sobre a matriz especificada, que será uma matriz classificada.

#incluir
usando namespace std;
Classe NodeList

público:
valores int;
Nodelist *a seguir;
;
Void SortInsertion (NodElist ** Head_Node, Nodelist* new_nodelist)

Nodelist * atual = * head_node;
if (atual == null)

new_nodelist-> next = new_nodelist;
*head_node = new_nodelist;

caso contrário, se (current-> valores> = new_nodelist-> valores)

while (atual-> próximo != *head_node)
Current = Current-> Next;
atual-> next = new_nodelist;
new_nodelist-> next = *head_node;
*head_node = new_nodelist;

outro

while (atual-> próximo!= *head_node &&
Current-> Next-> valores valores)
Current = Current-> Next;
new_nodelist-> next = current-> próximo;
atual-> next = new_nodelist;


Void Showlist (Nodelist *BEGIN)

Nodelist *temp;
se (comece != Nulo)

temp = começo;
fazer
cout while (temp != começar);


int main ()

int myarr [] = 31, 5, 23, 99, 30;
int list_size, i;
Nodelist *BEGIN = NULL;
Nodelist *temp;
para (i = 0; Ivalues ​​= myarr [i];
SortInsertion (& Begin, Temp);

cout<<"Sorted Circular Linked List:\n";
SHOWLIST (BEGIN);
cout<<"\n";
retornar 0;

A lista ligada circular classificada é exibida na tela seguinte do Ubuntu.

Conclusão

Isso termina nossa discussão sobre como inserir, dividir e classificar nós em uma lista ligada circular em c++. Uma lista ligada circular é usada em muitas aplicações que exigem muita flexibilidade. Espero que isso ajude você a remover a ambiguidade relacionada à lista ligada circular em C++.