Sirkulær koblet liste i C ++

Vi kan legge elementer i den sirkulære koblede listen hvor som helst på listen; Vi kan imidlertid ikke sette inn elementer i matrisen hvor som helst på listen siden det er i sammenhengende minne. Det siste elementet i en sirkulær koblet liste holder adressen til neste element, mens det siste elementet holder adressen til det første elementet. En sirkulær kjede dannes av elementene som refererer til hverandre i et sirkulært mønster.

Ettersom den sirkulære koblede listen har en dynamisk størrelse, kan minnet bare tildeles når det trengs. Artikkelen vil demonstrere den sirkulære koblede listen med C ++ programillustrasjoner i C++.

Bruk av sirkulær koblet liste

En sirkulær koblet liste er en der alle nodene er koblet sammen i en sirkel. Det er ikke noe nullelement i den sirkulære koblede listen. Et begynnelsespunkt kan være hvilken som helst node. Med utgangspunkt i et hvilket som helst sted på listen, kan vi krysse hele listen. Alt vi trenger å gjøre nå er å vente til den første noden er nådd igjen. Der har vi noen applikasjoner av en sirkulær koblet liste som følger:

1. Våre personlige datamaskiner, som kjører flere apper, er et eksempel på hvordan den sirkulære koblede listen brukes i det virkelige liv. Alle løpende apper lagres i en sirkulær koblet liste, og OS tildeler hver enkelt en bestemt tidsluke for å utføre. Operativsystemet fortsetter å sløyfe over den koblede listen til alle programmene er utført.
2. Multiplayer -spill er et annet utmerket eksempel. Alle spillerne er lagret i en sirkulær koblet liste, med pekeren som går foran når hver spillers mulighet utløper.
3. Sirkulærkøen kan også opprettes ved hjelp av en sirkulær koblet liste. Vi må beholde både pekere, foran og bak, til enhver tid i en kø, men bare en peker er nødvendig i en sirkulær koblet liste.

Eksempel 1: Opprette sirkulær koblet liste Traversal i C++

Den eneste forskjellen er at noden i den siste posisjonen i en sirkulær koblet liste vil ha sin neste lenke til listen Liste. Implementeringen av sirkulær koblet listekode i C ++ er vist nedenfor.

I det første trinnet har vi definert en klasse som "node", der vi har erklært en int -variabel som "mydata". Variabelen “MyData” er dataene for noden. Pekeren er også erklært i denne klassen som "neste" for pekeren til neste node i den sirkulære koblede listen.

Etter klassen “Node” har vi en funksjon som heter “Push”, som setter inn noden i begynnelsen av den sirkulære koblede listen. Vi definerte konstruktøren, som passerer head_node -pekerreferansen til klassen “Node” og variabelen “MyData” som en parameter. Den nye pekeren er opprettet som “MyPTR”, som har kalt og tildelt “Node”.

Deretter blir temp -pekeren erklært som "temp", som har head_node. Det er pekere som “PTR1” og “PTR2” som kalles “MyData” og Pointer “Next” og tar adressene sine. Etter det har vi en IF -uttalelse der det bare er head_node, og det holdes null. Hvis den sirkulære koblede listen er null, kan du legge til den neste til den siste noden ved hjelp av en stundsløyfe. Ellers vil den andre uttalelsen bli utført der hodet peker på listenes første node.

Deretter har vi opprettet en annen funksjon som "DisplayList", og i konstruktøren av denne funksjonen har vi nettopp passert nodehodet på den sirkulære koblede listen. Funksjonen vil vise nodene i en sirkulær koblet liste gjennom en do-mens Loop etter IF-setningen, som har betingelse av at noden ikke skal være lik null.

Endelig er det hovedmetoden, som vil teste implementeringen beskrevet tidligere. Pekerhodet til klassen “Node” er satt til “Null” i hovedmetoden. Legg deretter til dataene i den koblede listen ved hjelp av Push () -metoden. "Head" sendes til funksjonen "DisplayList", som viser den sirkulære koblede listen.

#inkludere
ved hjelp av navneområdet STD;
Klasseknute

offentlig:
int mydata;
Node *Neste;
;
void push (node ​​** head_node, int mydata)

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

mens (temp-> neste != *head_node)
temp = temp-> neste;
temp-> neste = myptr1;

ellers
Myptr1-> neste = myptr1;
*head_node = myptr1;

void displayList (node ​​*head)

Node *temp = hode;
hvis (hode != Null)

gjøre

cout
mens (temp != hode);


int main ()

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

Den sirkulære koblede listen implementert i ovennevnte kodeutgang vises i følgende bilde.

Eksempel2: Del den sirkulære koblede listen i to halvdeler i C++

Følgende program gjør splitting av en sirkulær koblet liste i to mulige deler. La oss se på implementeringen av hvordan vi deler den sirkulære koblede listen i C++.

Først har vi en klasse "node" der vi har definert en variabel "elementer" og pekeren "neste" av noden. Medlemmene av klassen "Node" er offentlige i dette programmet. Deretter bygde vi en funksjon som heter "Halvelist" der vi delte listen fra begynnelsen med hodet i to lister. Head1_node og head2_node er referanser til de to resulterende koblede listene 'hodeknuter.

I funksjonen har vi erklært to tips, “S_PTR” og “F_PTR”, som har sjefen for den koblede listen. Hvis IF-setningen brukes til hodeknuten som inneholder en nullverdi, har vi en stundsløyfe som sier at F_PTR-> Neste blir hode hvis sirkulærlisten har rare noder, og F_PTR-> Neste-> Neste blir hode hvis Listen inneholder jevn noder.

Etter mens Loop har vi igjen brukt IF -setningen der tilstanden er "Hvis listen inneholder til og med antall elementer, bør F_PTR flyttes og angi Head1_Node -pekeren i første omgang". I neste IF -uttalelse har vi satt head2_node til andre halvdel av den koblede listen.

Vi har tildelt S_PTR-> ved siden av F_PTR-> ved siden av for å lage den andre halvsirkulære på listen, og deretter holdes S_PTR-> LISTE på listen og gjør den første halvsirkelen S_PTR->.

Den andre funksjonen er opprettet som "push", som brukes til å sette inn en node i starten av en sirkulær koblet liste med denne funksjonen. I funksjonen innebærer tilstanden om head_noden til den sirkulære koblede listen ikke er null, og deretter sett ved siden av den siste noden. Den tredje funksjonen, "DisplayList", genereres for at den sirkulære koblede listen skal vises.

Deretter har vi hovedfunksjonen, der vi har initialisert hodet, head1_node og head2_node tom. Push -metoden brukes til å sette inn verdiene i den koblede listen, og gjennom COUT -kommandoen vises den sirkulære koblede listen og den delte sirkulære koblede listen.

#inkludere
ved hjelp av navneområdet STD;
klasse MyNode

offentlig:
int elementer;
Mynode *Neste;
;
void halvelist (myNode *head, myNode ** head1_node, myNode ** head2_node)

MyNode *s_ptr = hode;
MyNode *f_ptr = hode;
if (head == null)
komme tilbake;
mens (f_ptr-> neste != head &&
f_ptr-> neste-> Neste != hode)

F_PTR = F_PTR-> NESTE-> NESTE;
S_PTR = S_PTR-> Neste;

if (f_ptr-> next-> next == head)
f_ptr = f_ptr-> neste;
*head1_node = head;
if (head-> neste != hode)
*head2_node = s_ptr-> neste;
f_ptr-> neste = S_PTR-> Neste;
s_ptr-> neste = hode;

void push (myNode ** head_node, int elementer)

Mynode *newPtr = new Mynode ();
Mynode *temp = *head_node;
NewPtr-> elementer = elementer;
NewPtr-> next = *head_node;
if (*head_node != Null)

mens (temp-> neste != *head_node)
temp = temp-> neste;
temp-> neste = newPtr;

ellers
NewPtr-> next = newPtr; / *For den første myNode */
*head_node = newPtr;

void displayList (myNode *head)

MyNode *temp = hode;
hvis (hode != Null)

cout<Gjør
cout mens (temp != hode);


int main ()

int myListSize, jeg;
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 (hode);
Halvelist (Head, & Head1, & Head2);
cout<< "\nFirst Halve Circular Linked List";
DisplayList (Head1);
cout<< "\nSecond Halve Circular Linked List";
DisplayList (Head2);
retur 0;

Her har vi utdataene fra den originale sirkulære koblede listen, utdataene fra den første halvsirkulære koblede listen, og andre halvdel av den sirkulære koblede listen.

Eksempel 3: Sortering av den sirkulære koblede listen i C++

I det første trinnet har vi en "nodelist", som inneholder medlemsvariabler og pekere i klassen. Deretter har vi laget en funksjon "sortinsertion", som setter inn en ny node i en sortert liste. Denne funksjonen krever en peker til hodeknuten fordi den kan endre den koblede listenes hode.

Etter det har vi en IF -uttalelse for nodelist, som bare inneholder node i den. Head_node peker på den nye noden. I det andre, hvis uttalelse, har vi tildelt dataene fra nodelisten til gjeldende.

Her blir en ny node lagt til før hodeknuten. If-Else-blokken har en stundsløyfe som har en tilstand; Hvis verdien er mindre enn hovedverdien, må neste eller siste node endres. Mens sløyfen vil bare identifisere noden før innsettingspunktet.

Etter det laget vi en ny_nodelist, den neste noden som lokaliserer pekerens neste node. Deretter, nåværende-> Neste, må vi endre pekerens plassering til neste. For å skrive ut nodene på den koblede listen, har vi kalt en funksjon "showlist".

Til slutt har vi hovedfunksjonen der vi har initialisert en matrise og iterert over den spesifiserte matrisen, som vil være en sortert matrise.

#inkludere
ved hjelp av navneområdet STD;
Klasse nodelist

offentlig:
int -verdier;
Nodelist *Neste;
;
void sortinsertion (nodelist ** head_node, nodelist* new_nodelist)

Nodelist * Current = * head_node;
if (current == null)

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

annet hvis (gjeldende-> verdier> = new_nodelist-> verdier)

mens (strøm-> neste != *head_node)
Nåværende = strøm-> Neste;
Current-> neste = new_nodelist;
new_nodelist-> next = *head_node;
*head_node = new_nodelist;

ellers

mens (strøm-> neste!= *head_node &&
Nåværende-> Neste-> Verdier verdier)
Nåværende = strøm-> Neste;
new_nodelist-> next = current-> neste;
Current-> neste = new_nodelist;


Void Showlist (Nodelist *Begynn)

Nodelist *temp;
hvis (begynn != Null)

temp = begynn;
Gjør
cout mens (temp != begynn);


int main ()

int myarr [] = 31, 5, 23, 99, 30;
int list_size, i;
Nodelist *BEGIN = NULL;
Nodelist *temp;
for (i = 0; ivalues ​​= myarr [i];
Sortinsertion (& begynn, temp);

cout<<"Sorted Circular Linked List:\n";
Showlist (begynn);
cout<<"\n";
retur 0;

Den sorterte sirkulære koblede listen vises på følgende skjerm av Ubuntu.

Konklusjon

Dette avslutter diskusjonen vår om hvordan du kan sette inn, dele og sortere noder i en sirkulær koblet liste i C++. En sirkulær koblet liste brukes i mange applikasjoner som krever mye fleksibilitet. Jeg håper dette vil hjelpe deg å fjerne tvetydighet relatert til den sirkulære koblede listen i C++.