Elenco collegato circolare in C ++

Possiamo inserire elementi nell'elenco circolare collegato da qualsiasi parte dell'elenco; Tuttavia, non possiamo inserire elementi nell'array da qualsiasi parte dell'elenco poiché è in memoria contigua. L'ultimo elemento in un elenco collegato circolare mantiene l'indirizzo dell'elemento successivo, mentre l'ultimo elemento mantiene l'indirizzo del primo elemento. Una catena circolare è formata dagli elementi che si riferiscono l'uno all'altro in uno schema circolare.

Poiché l'elenco collegato circolare ha una dimensione dinamica, la memoria può essere allocata solo quando è necessaria. L'articolo dimostrerà l'elenco circolare collegato con le illustrazioni del programma C ++ in C++.

Applicazione dell'elenco circolare collegato

Un elenco circolare collegato è quello in cui tutti i nodi sono collegati in un cerchio. Non esiste un elemento null nell'elenco collegato circolare. Un punto di partenza può essere qualsiasi nodo. A partire da qualsiasi luogo nell'elenco, possiamo attraversare l'intero elenco. Tutto quello che dobbiamo fare ora è aspettare fino a quando il primo nodo è di nuovo raggiungibile. Lì abbiamo alcune applicazioni di un elenco circolare collegato come segue:

1. I nostri personal computer, che eseguono diverse app, sono un esempio di come l'elenco circolare collegato viene utilizzato nella vita reale. Tutte le app in esecuzione sono archiviate in un elenco collegato circolare e il sistema operativo assegna a ciascuno un determinato fascia orario da eseguire. Il sistema operativo continua a correre sull'elenco collegato fino a quando non vengono eseguiti tutti i programmi.
2. I giochi multiplayer sono un altro eccellente esempio. Tutti i giocatori sono archiviati in un elenco circolare collegato, con il puntatore che avanza quando scade l'opportunità di ogni giocatore.
3. La coda circolare può essere creata utilizzando anche un elenco di colletti circolari. Dobbiamo conservare entrambi i puntatori, anteriori e posteriori, in memoria in ogni momento in coda, ma è necessario solo un puntatore in un elenco circolare.

Esempio 1: Creazione di un attraversamento dell'elenco collegato circolare in C++

L'unica differenza è che in un elenco circolare legato Elenco. L'implementazione del codice di attraversamento dell'elenco circolare in C ++ è mostrata di seguito.

Nel primo passo, abbiamo definito una classe come "nodo", in cui abbiamo dichiarato una variabile INT come "mydata". La variabile "mydata" è i dati per il nodo. Il puntatore è anche dichiarato in questa classe come "Next" per il puntatore al nodo successivo nell'elenco circolare collegato.

Dopo il "nodo" di classe, abbiamo una funzione chiamata "Push", che inserisce il nodo all'inizio dell'elenco circolare collegato. Abbiamo definito il costruttore, che passa il riferimento del puntatore head_node della classe "nodo" e la variabile "mydata" come parametro. Il nuovo puntatore viene creato come "myptr", che ha chiamato e assegnato il "nodo".

Quindi, il puntatore della temperatura viene dichiarato "temp", che ha il head_node. Ci sono puntatori come "PTR1" e "PTR2" che sono chiamati "MyData" e puntatore "Next" e prendono i loro indirizzi. Successivamente, abbiamo un'istruzione if in cui c'è solo head_node ed è nullo. Se l'elenco collegato circolare è nullo, aggiungi l'ultimo nodo con l'aiuto di un ciclo while. Altrimenti, l'istruzione else verrà eseguita in cui la testa punta al primo nodo dell'elenco.

Quindi, abbiamo creato un'altra funzione come "displaylist" e, nel costruttore di questa funzione, abbiamo appena superato la testa del nodo dell'elenco circolare collegato. La funzione visualizzerà i nodi in un elenco collegato circolare tramite un ciclo do-while dopo l'istruzione IF, che ha la condizione che la testa del nodo non dovrebbe essere uguale a null.

Infine, esiste il metodo principale, che testerà l'implementazione descritta in precedenza. Il capo puntatore del "nodo" di classe è stato impostato su "null" nel metodo principale. Quindi, aggiungi i dati all'elenco collegato con l'aiuto del metodo push (). La "testa" viene passata alla funzione "displaylist", che mostrerà l'elenco collegato circolare.

#includere
Utilizzo dello spazio dei nomi std;
nodo di classe

pubblico:
int mydata;
Nodo *Next;
;
void push (nodo ** head_node, int mydata)

Nodo *myptr1 = new node ();
Nodo *temp = *head_node;
Myptr1-> myData = myData;
Myptr1-> next = *head_node;
if (*head_node != Null)

mentre (temp-> successiva != *head_node)
temp = temp-> Next;
temp-> next = myptr1;

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

void DisplayList (nodo *testa)

Nodo *temp = head;
Se (testa != Null)

Fare

cout
mentre (temp != testa);


int main ()

Nodo *head = null;
Push (& Head, 2001);
Push (& Head, 2015);
Push (& Head, 2006);
Push (& Head, 2022);
cout<< "Circular Linked List:\n ";
DisplayList (Head);
cout<< "\n ";
restituzione 0;

L'elenco collegato circolare implementato nell'output del codice precedente viene visualizzato nella seguente immagine.

Esempio2: dividere l'elenco circolare collegato in due metà in C++

Il seguente programma rende possibile la suddivisione di un elenco collegato circolare in due parti. Diamo un'occhiata all'implementazione di come abbiamo diviso l'elenco collegato circolare in C++.

Innanzitutto, abbiamo un "nodo" di classe in cui abbiamo definito una variabile "elementi" e il puntatore "successivo" del nodo. I membri del "nodo" di classe sono pubblici in questo programma. Quindi, abbiamo costruito una funzione chiamata "Halveist" in cui abbiamo diviso l'elenco dall'inizio con la testa in due elenchi. Head1_node e head2_node sono riferimenti ai due nodi testa.

Nella funzione, abbiamo dichiarato due puntatori, "S_PTR" e "F_PTR", che ha la testa dell'elenco collegato. Se l'istruzione IF viene utilizzata per il nodo testa contenente un valore nullo, allora abbiamo un ciclo while che afferma che f_ptr-> successivo diventa testa se l'elenco circolare ha nodi dispari e f_ptr-> next-> successivo diventa testa se il L'elenco contiene anche nodi.

Dopo il ciclo while, abbiamo nuovamente utilizzato l'istruzione IF in cui la condizione è "se l'elenco contiene un numero uniforme di elementi, F_PTR dovrebbe essere spostato e impostare il puntatore head1_node del primo tempo". Nell'istruzione IF successiva, abbiamo impostato il head2_node nella seconda metà dell'elenco collegato.

Abbiamo assegnato S_PTR-> accanto a F_PTR-> accanto per creare il secondo mezzo circolare dell'elenco, e quindi S_PTR-> è mantenuto uguale alla testa dell'elenco e fa il primo seminterrato.

La seconda funzione viene creata come "push", che viene utilizzata per inserire un nodo all'inizio di un elenco collegato circolare con questa funzione. Nella funzione, la condizione implica se il head_node dell'elenco collegato circolare non è nullo, quindi impostato accanto all'ultimo nodo. La terza funzione, "DisplayList", viene generata per la visualizzazione dell'elenco collegato circolare.

Quindi, abbiamo la funzione principale, in cui abbiamo inizializzato la testa, il head1_node e head2_node vuoto. Il metodo push viene utilizzato per inserire i valori nell'elenco collegato e tramite il comando cout, verranno visualizzati l'elenco circolare collegato e l'elenco collegato circolare diviso.

#includere
Utilizzo dello spazio dei nomi std;
Classe Mynode

pubblico:
articoli int;
Mynode *Next;
;
void halvelist (mynode *head, mynode ** head1_node, mynode ** head2_node)

Mynode *s_ptr = head;
Mynode *f_ptr = head;
if (head == null)
ritorno;
while (f_ptr-> successivo != head &&
f_ptr-> Next-> Next != testa)

f_ptr = f_ptr-> next-> next;
S_PTR = S_PTR-> Next;

if (f_ptr-> next-> next == head)
f_ptr = f_ptr-> Next;
*head1_node = head;
if (head-> Next != testa)
*head2_node = s_ptr-> Next;
f_ptr-> next = s_ptr-> next;
s_ptr-> next = head;

void push (mynode ** head_node, int elementi)

MyNode *newptr = new MyNode ();
Mynode *temp = *head_node;
Newptr-> elementi = elementi;
Newptr-> next = *head_node;
if (*head_node != Null)

mentre (temp-> successiva != *head_node)
temp = temp-> Next;
temp-> next = newptr;

altro
Newptr-> next = newptr; / *Per il primo mynode */
*head_node = newptr;

void DisplayList (MyNode *Head)

Mynode *temp = head;
Se (testa != Null)

cout<Fare
cout while (temp != testa);


int main ()

int myliszeze, io;
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 (Head);
Halvelist (Head, & Head1, & Head2);
cout<< "\nFirst Halve Circular Linked List";
DisplayList (head1);
cout<< "\nSecond Halve Circular Linked List";
DisplayList (head2);
restituzione 0;

Qui abbiamo l'output dell'elenco collegato circolare originale, l'output del primo elenco collegato a metà circolare e la seconda metà dell'elenco collegato circolare.

Esempio 3: ordinamento dell'elenco collegato circolare in C++

Nel primo passo, abbiamo una classe "nodelist", che contiene variabili membri e puntatori della classe. Quindi, abbiamo creato una funzione "Sortinsertion", che inserisce un nuovo nodo in un elenco ordinato. Questa funzione richiede un puntatore al nodo della testa perché può modificare la testa dell'elenco collegato input.

Successivamente, abbiamo un'istruzione IF per nodelist, che contiene solo nodo in esso. Il head_node punta al nuovo nodo. Nell'istruzione altro, se abbiamo assegnato i dati di NODELIST alla corrente.

Qui, viene aggiunto un nuovo nodo prima del nodo. Il blocco IF-Else ha un ciclo while che ha una condizione; Se il valore è inferiore al valore della testa, il nodo successivo o ultimo deve essere modificato. Il ciclo while identificherà solo il nodo prima del punto di inserimento.

Successivamente, abbiamo realizzato un new_nodelist, il nodo successivo che individua il nodo successivo del puntatore. Quindi, Current-> Next, dobbiamo cambiare la posizione del puntatore a quella successiva. Per stampare i nodi dell'elenco collegato, abbiamo definito una funzione "showlist".

Alla fine, abbiamo la funzione principale in cui abbiamo inizializzato un array e iterali sul array specificato, che sarà un array ordinato.

#includere
Utilizzo dello spazio dei nomi std;
Classe NODELIST

pubblico:
valori int;
Nodelist *Next;
;
void SortInsertion (nodelist ** head_node, nodelist* new_nodelist)

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

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

else if (corrente-> valori> = new_nodelist-> valori)

mentre (Current-> Next != *head_node)
Current = Current-> Next;
Current-> Next = new_nodelist;
new_nodelist-> next = *head_node;
*head_node = new_nodelist;

altro

mentre (Current-> Next!= *head_node &&
corrente-> Next-> Valori valori)
Current = Current-> Next;
new_nodelist-> Next = Current-> Next;
Current-> Next = new_nodelist;


void showlist (nodelist *inizio)

Nodelist *temp;
Se (inizia != Null)

temp = inizio;
Fare
cout while (temp != inizia);


int main ()

int myarr [] = 31, 5, 23, 99, 30;
int list_size, i;
Nodelist *inizio = null;
Nodelist *temp;
per (i = 0; ivalues ​​= myarr [i];
Sortinsertion (& inizio, temp);

cout<<"Sorted Circular Linked List:\n";
showlist (inizio);
cout<<"\n";
restituzione 0;

L'elenco collegato circolare ordinato viene visualizzato nella seguente schermata di Ubuntu.

Conclusione

Questo termina la nostra discussione su come inserire, dividere e ordinare i nodi in un elenco circolare collegato in C++. Un elenco circolare collegato viene utilizzato in molte applicazioni che richiedono molta flessibilità. Spero che questo ti aiuti a rimuovere l'ambiguità relativa all'elenco circolare collegato in C++.