Meny

Sirkulær sammenkoblet liste Datastruktur i C ++ med illustrasjon

  • Hoved
  • Annen
  • Sirkulær sammenkoblet liste Datastruktur i C ++ med illustrasjon

circular linked list data structure c with illustration

Prøv Instrumentet Vårt For Å Eliminere Problemer

En komplett oversikt over sirkulær koblet liste.

En sirkulær koblet liste er en variant av den koblede listen. Det er en koblet liste hvis noder er koblet sammen på en slik måte at den danner en sirkel.

I den sirkulære koblede listen er ikke neste peker til den siste noden satt til null, men den inneholder adressen til den første noden og danner dermed en sirkel.

=> Besøk her for å lære C ++ fra grunnen.

Rundkoblet liste

Hva du vil lære:

Sirkulær koblet liste i C ++

Arrangementet vist nedenfor er for en enkelt koblet liste.

enkeltkoblet liste

En sirkulær koblet liste kan være en enkelt koblet liste eller en dobbelt koblet liste. I en dobbelt sirkulær koblet liste er den forrige pekeren til den første noden koblet til den siste noden mens den neste pekeren til den siste noden er koblet til den første noden.

Dens fremstilling er vist nedenfor.

dobbelt sirkulær koblet liste

Erklæring

Vi kan erklære en node i en sirkulær koblet liste som hvilken som helst annen node som vist nedenfor:

struct Node { int data; struct Node *next; };

For å implementere den sirkulære koblede listen, opprettholder vi en ekstern peker 'siste' som peker til den siste noden i den sirkulære koblede listen. Derfor vil siste-> neste peke på den første noden i den koblede listen.

Ved å gjøre dette, sørger vi for at når vi setter inn en ny node i begynnelsen eller slutten av listen, trenger vi ikke å krysse hele listen. Dette er fordi de siste peker til den siste noden mens siste-> neste peker til den første noden.

Dette hadde ikke vært mulig hvis vi hadde pekt den eksterne pekeren mot den første noden.

Grunnleggende operasjoner

Den sirkulære koblede listen støtter innsetting, sletting og kryssing av listen. Vi vil diskutere hver av operasjonene i detalj nå.

Innsetting

Vi kan sette inn en node i en sirkulær koblet liste enten som en første node (tom liste), i begynnelsen, til slutt eller mellom de andre nodene. La oss se hver av disse innsettingsoperasjonene ved hjelp av en illustrasjon nedenfor.

# 1) Sett inn i en tom liste

Sett inn i en tom liste

Når det ikke er noen noder i sirkulær liste og listen er tom, er den siste pekeren null, så setter vi inn en ny node N ved å peke den siste pekeren til noden N som vist ovenfor. Den neste pekeren til N vil peke på selve noden N, da det bare er en node. Dermed blir N den første så vel som den siste noden i listen.

# 2) Sett inn i begynnelsen av listen

Sett inn i begynnelsen av listen

Som vist i representasjonen ovenfor, når vi legger til en node i begynnelsen av listen, peker den neste pekeren til den siste noden til den nye noden N og gjør den til en første node.

N-> neste = siste-> neste

Siste-> neste = N

# 3) Sett inn på slutten av listen

siste node peker mot den nye noden

For å sette inn en ny node på slutten av listen følger vi disse trinnene:

hvordan du kjører .bin-filer

N-> neste = siste -> neste;
siste -> neste = N
siste = N

# 4) Sett inn mellom listen

Sett inn mellom listen

Anta at vi trenger å sette inn en ny node N mellom N3 og N4, vi må først krysse listen og finne noden etter hvilken den nye noden skal settes inn, i dette tilfellet dens N3.

Etter at noden er lokalisert, utfører vi følgende trinn.

N -> neste = N3 -> neste;
N3 -> neste = N

Dette setter inn en ny node N etter N3.

Sletting

Sletteoperasjonen av den sirkulære koblede listen innebærer å finne noden som skal slettes og deretter frigjøre minnet.

For dette opprettholder vi to ekstra pekere curr og prev og krysser deretter listen for å finne noden. Den gitte noden som skal slettes, kan være den første noden, den siste noden eller noden i mellom. Avhengig av plasseringen setter vi curr og forrige pekere og sletter deretter curr node.

En illustrasjon av slettingsoperasjonen er vist nedenfor.

slettingsoperasjon

Gjennomgang

Traversal er en teknikk for å besøke hver eneste node. I lineære koblede lister som enkeltkoblede lister og dobbeltkoblede lister, er det enkelt å krysse når vi besøker hver node og stopper når NULL oppstår.

Dette er imidlertid ikke mulig i en sirkulær koblet liste. I en sirkulær koblet liste starter vi fra den neste av den siste noden som er den første noden og krysser hver node. Vi stopper når vi igjen når den første noden.

Nå presenterer vi en implementering av sirkulær koblede listeoperasjoner ved bruk av C ++ og Java. Vi har implementert innsetting, sletting og kryssoperasjoner her. For en klar forståelse har vi avbildet den sirkulære koblede listen som

Gjennomgang

Således til den siste noden 50, fester vi igjen noden 10 som er den første noden, og indikerer derved den som en sirkulær koblet liste.

#include using namespace std; struct Node { int data; struct Node *next; }; //insert a new node in an empty list struct Node *insertInEmpty(struct Node *last, int new_data) { // if last is not null then list is not empty, so return if (last != NULL) return last; // allocate memory for node struct Node *temp = new Node; // Assign the data. temp -> data = new_data; last = temp; // Create the link. last->next = last; return last; } //insert new node at the beginning of the list struct Node *insertAtBegin(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //set new data to node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; return last; } //insert new node at the end of the list struct Node *insertAtEnd(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //assign data to new node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; last = temp; return last; } //insert a new node in between the nodes struct Node *insertAfter(struct Node *last, int new_data, int after_item) { //return null if list is empty if (last == NULL) return NULL; struct Node *temp, *p; p = last -> next; do { if (p ->data == after_item) { temp = new Node; temp -> data = new_data; temp -> next = p -> next; p -> next = temp; if (p == last) last = temp; return last; } p = p -> next; } while(p != last -> next); cout << 'The node with data '< next; // Point to the first Node in the list. // Traverse the list starting from first node until first node is visited again do { cout <

data <'; p = p -> next; } while(p != last->next); if(p == last->next) coutdata==key && (*head)->next==*head) { free(*head); *head=NULL; } Node *last=*head,*d; // If key is the head if((*head)->data==key) { while(last->next!=*head) // Find the last node of the list last=last->next; // point last node to next of head or second node of the list last->next=(*head)->next; free(*head); *head=last->next; } // end of list is reached or node to be deleted not there in the list while(last->next!=*head&&last->next->data!=key) { last=last->next; } // node to be deleted is found, so free the memory and display the list if(last->next->data==key) { d=last->next; last->next=d->next; cout<<'The node with data '<

Produksjon:

Den rundkoblede listen som er opprettet, er som følger:

10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10

Noden med data 10 slettes fra listen

Rundkoblet liste etter sletting av 10 er som følger:

20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 20

Deretter presenterer vi en Java-implementering for Circular linked-listeoperasjonene.

//Java class to demonstrate circular linked list operations class Main { static class Node { int data; Node next; }; //insert a new node in the empty list static Node insertInEmpty(Node last, int new_data) { // if list is not empty, return if (last != null) return last; Node temp = new Node(); // create a new node temp.data = new_data; // assign data to new node last = temp; last.next = last; // Create the link return last; } //insert a new node at the beginning of the list static Node insertAtBegin(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); //set data for the node temp.data = new_data; temp.next = last.next; last.next = temp; return last; } //insert a new node at the end of the list static Node insertAtEnd(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); temp.data = new_data; temp.next = last.next; last.next = temp; last = temp; return last; } //insert node in between the nodes in the list static Node addAfter(Node last, int new_data, int after_item) { //if list is null, return if (last == null) return null; Node temp, p; p = last.next; do { if (p.data == after_item) { temp = new Node(); temp.data = new_data; temp.next = p.next; p.next = temp; if (p == last) last = temp; return last; } p = p.next; { while(p != last.next); System.out.println('The node with data ' + after_item + ' not present in the list.'); return last; } //traverse the circular linked list static void traverse(Node last) { Node p; // If list is empty, return. if (last == null) { System.out.println('Cicular linked List is empty.'); return; } p = last.next; // Point to first Node of the list. // Traversing the list. do{ System.out.print(p.data + '==>'); p = p.next; } while(p != last.next); if(p == last.next) System.out.print(p.data); System.out.print(' '); } //delete a node from the list static Node deleteNode(Node head, int key) { //if list is null, return if (head == null) return null; // Find the required node that is to be deleted Node curr = head, prev = new Node(); while (curr.data != key) { if (curr.next == head) { System.out.printf(' Given node ' + key + ' is not found' + “in the list!'); break; } prev = curr; curr = curr.next; } // Check if node is only node if (curr.next == head) { head = null; return head; } // If more than one node, check if it is first node if (curr == head) { prev = head; while (prev.next != head) prev = prev.next; head = curr.next; prev.next = head; } // check if node is last node else if (curr.next == head) { prev.next = head; } else { prev.next = curr.next; } System.out.println('After deleting ' + key + ' the circular list is:'); traverse(head); return head; } // Main code public static void main(String() args){ Node last = null; last = insertInEmpty(last, 30); last = insertAtBegin(last, 20); last = insertAtBegin(last, 10); last = insertAtEnd(last, 40); last = insertAtEnd(last, 60); last = addAfter(last, 50, 40); System.out.println('Circular linked list created is:'); traverse(last); last = deleteNode(last,40); } }

Produksjon:

Rundkoblet liste opprettet er:

10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10

Etter å ha slettet 40 er den sirkulære listen:

10 ==> 20 ==> 30 ==> 50 ==> 60 ==> 10

Fordeler ulemper

La oss diskutere noen fordeler og ulemper ved den sirkulære koblede listen.

Fordeler:

  • Vi kan gå til hvilken som helst node og krysse fra hvilken som helst node. Vi trenger bare å stoppe når vi besøker samme node igjen.
  • Når den siste noden peker på den første noden, tar det bare ett trinn å gå til den første noden fra den siste noden.

Ulemper:

  • Å omgjøre en sirkulær koblet liste er tungvint.
  • Ettersom nodene er koblet sammen for å danne en sirkel, er det ingen riktig merking for begynnelse eller slutt for listen. Derfor er det vanskelig å finne slutten på listen eller loopkontrollen. Hvis det ikke blir tatt vare på, kan en implementering havne i en uendelig løkke.
  • Vi kan ikke gå tilbake til forrige node i et enkelt trinn. Vi må krysse hele listen fra først.

Anvendelser av sirkulær koblet liste

  • Sanntids anvendelse av sirkulær koblet liste kan være et flerprogrammeringsoperativsystem der det planlegger flere programmer. Hvert program får en dedikert tidsstempel å utføre, hvoretter ressursene blir overført til et annet program. Dette fortsetter kontinuerlig i en syklus. Denne representasjonen kan oppnås effektivt ved hjelp av en sirkulær koblet liste.
  • Spill som spilles med flere spillere kan også representeres ved hjelp av en sirkulær koblet liste der hver spiller er en node som får sjansen til å spille.
  • Vi kan bruke en sirkulær koblet liste for å representere en sirkulær kø. Ved å gjøre dette kan vi fjerne de to pekerne foran og bak som brukes til køen. I stedet kan vi bare bruke en peker.

Konklusjon

En sirkulær koblet liste er en samling noder der nodene er koblet til hverandre for å danne en sirkel. Dette betyr at i stedet for å sette neste peker til den siste noden til null, er den koblet til den første noden.

En sirkulær koblet liste er nyttig for å representere strukturer eller aktiviteter som må gjentas igjen og igjen etter et bestemt tidsintervall, for eksempel programmer i et flerprogrammeringsmiljø. Det er også gunstig for å designe en sirkulær kø.

Sirkulære sammenkoblede lister støtter forskjellige operasjoner som innsetting, sletting og traversaler. Dermed har vi sett operasjonene i detalj i denne opplæringen.

I vårt neste tema om datastrukturer vil vi lære om stabeldatastrukturen.

=> Sjekk her for å se AZ av C ++ opplæringsveiledninger her.

Anbefalt lesing

^