Circular Linked List: Fordeler med C-programeksempel

Innholdsfortegnelse:

Anonim

Hva er en sirkulær koblet liste?

En sirkulær koblet liste er en sekvens av noder ordnet slik at hver node kan trekkes tilbake til seg selv. Her er en "node" et selvhenvisende element med pekere til en eller to noder i iIs umiddelbare nærhet.

Nedenfor er en skildring av en sirkulær koblet liste med 3 noder.

Her kan du se at hver node kan trekkes tilbake for seg selv. Eksemplet vist ovenfor er en sirkulær enkeltkoblet liste.

Merk: Den mest enkle sirkulære koblede listen er en node som bare sporer til seg selv som vist

I denne veiledningen om sirkulær koblet liste vil du lære:

  • Hva er en sirkulær koblet liste?
  • Grunnleggende operasjoner
  • Innsettingsoperasjon
  • Slettingsoperasjon
  • Gjennomgang av en sirkulær koblet liste
  • Fordeler med sirkulær koblet liste
  • Enkelinket liste som en sirkulær koblet liste
  • Anvendelser av den sirkulære koblede listen

Grunnleggende operasjoner

De grunnleggende operasjonene på en sirkulær koblet liste er:

  1. Innsetting
  2. Sletting og
  3. Gjennomgang
  • Innsetting er prosessen med å plassere en node på en spesifisert posisjon i den sirkulære koblede listen.
  • Sletting er prosessen med å fjerne en eksisterende node fra den koblede listen. Noden kan identifiseres ved forekomsten av verdien eller ved posisjonen.
  • Gjennomgang av en sirkulær koblet liste er prosessen med å vise hele innholdet på den koblede listen og gå tilbake til kildenoden.

I neste avsnitt vil du forstå innsetting av en node, og hvilke typer innføring som er mulig i en sirkulær enkeltkoblet liste.

Innsettingsoperasjon

Opprinnelig må du opprette en node som peker mot seg selv som vist i dette bildet. Uten denne noden oppretter innsetting den første noden.

Deretter er det to muligheter:

  • Innsetting på gjeldende posisjon i den sirkulære koblede listen. Dette tilsvarer innsetting i begynnelsen av slutten av en vanlig singularkoblet liste. I en sirkulær koblet liste er begynnelsen og slutten den samme.
  • Innsetting etter en indeksert node. Noden skal identifiseres med et indeksnummer som tilsvarer elementverdien.

For å sette inn på begynnelsen / slutten av den sirkulære koblede listen, det vil si den posisjonen der den aller første noden ble lagt til,

  • Du må bryte den eksisterende selvkoblingen til den eksisterende noden
  • Den nye noden neste peker vil lenke til den eksisterende noden.
  • Den siste nodens neste peker vil peke på den innsatte noden.

MERK: Pekeren som er tokenmasteren eller begynnelsen / slutten av sirkelen kan endres. Det vil fortsatt gå tilbake til samme node på en traversal, diskutert fremover.

Trinn i (a) i-iii er vist nedenfor:

(Eksisterende node)

TRINN 1) Bryt den eksisterende lenken

TRINN 2) Opprett en viderekobling (fra ny node til en eksisterende node)

TRINN 3) Opprett en sløyfelink til den første noden

Deretter vil du prøve innsetting etter en node.

La oss for eksempel sette inn "VALUE2" etter noden med "VALUE0". La oss anta at startpunktet er noden med "VALUE0".

  • Du må bryte linjen mellom den første og andre noden og plassere noden med "VALUE2" i mellom.
  • Den første nodens neste peker må lenke til denne noden, og denne nodens neste peker må koble til den tidligere andre noden.
  • Resten av ordningen forblir uendret. Alle noder kan trekkes tilbake for seg selv.

MERK: Siden det er et syklisk arrangement, innebærer det å sette inn en node den samme prosedyren for en hvilken som helst node. Pekeren som fullfører en syklus fullfører syklusen akkurat som alle andre noder.

Dette vises nedenfor:

(La oss si det er bare to noder. Dette er et trivielt tilfelle)

TRINN 1) Fjern den indre koblingen mellom de tilkoblede nodene

TRINN 2) Koble noden til venstre til den nye noden

TRINN 3) Koble den nye noden til noden til høyre.

Slettingsoperasjon

La oss anta en 3-node sirkulær koblet liste. Sakene for sletting er gitt nedenfor:

  • Slette det nåværende elementet
  • Sletting etter et element.

Sletting i begynnelsen / slutten:

  1. Kryss til den første noden fra den siste noden.
  2. For å slette fra slutten, bør det bare være ett traversalt trinn, fra den siste noden til den første noden.
  3. Slett koblingen mellom siste node og neste node.
  4. Koble den siste noden til neste element i den første noden.
  5. Gratis den første noden.

(Eksisterende oppsett)

TRINN 1 ) Fjern den sirkulære lenken

TRINN 2) Fjern koblingen mellom første og neste, lenke den siste noden, til noden som følger den første

TRINN 3) Fritt / deallocate den første noden

Sletting etter en node:

  1. Kryss til neste node er noden som skal slettes.
  2. Kryss til neste node, og plasser en peker på den forrige noden.
  3. Koble den forrige noden til noden etter den nåværende noden, ved hjelp av neste peker.
  4. Frigjør den nåværende (delinkede) noden.

TRINN 1) La oss si at vi trenger å slette en node med "VALUE1."

TRINN 2) Fjern koblingen mellom forrige node og nåværende node. Koble den forrige noden til den neste noden som er pekt av den nåværende noden (med VALUE1).

TRINN 3) Frigjør eller del lokaliser den nåværende noden.

Gjennomgang av en sirkulær koblet liste

For å krysse en sirkellinket liste, startende fra en siste peker, sjekk om den siste pekeren er NULL. Hvis denne tilstanden er falsk, sjekk om det bare er ett element. Ellers kan du krysse ved hjelp av en midlertidig peker til den siste pekeren er nådd igjen, eller så mange ganger som nødvendig, som vist i GIF nedenfor.

Fordeler med sirkulær koblet liste

Noen av fordelene med sirkulære lister er:

  1. Ingen krav til NULL-oppgave i koden. Den sirkulære listen peker aldri mot en NULL-peker med mindre den er fullstendig distribuert.
  2. Rundkoblede lister er fordelaktige for sluttoperasjoner siden begynnelse og slutt sammenfaller. Algoritmer som Round Robin-planlegging kan pent eliminere prosesser som står i kø på en sirkulær måte uten å støte på dinglende eller NULL-refererende pekere.
  3. Rundkoblet liste utfører også alle vanlige funksjoner i en enkeltkoblet liste. Faktisk kan sirkulære dobbeltkoblede lister diskutert nedenfor til og med eliminere behovet for en fullverdig traversal for å finne et element. Dette elementet ville maksimalt bare være motsatt av starten, og fullføre bare halvparten av den koblede listen.

Enkeltkoblet liste som en sirkulær koblet liste

Du oppfordres til å prøve å lese og implementere koden nedenfor. Den presenterer pekeren aritmetikk assosiert med sirkulære koblede lister.

#include#includestruct node{int item;struct node *next;};struct node* addToEmpty(struct node*,int);struct node *insertCurrent(struct node *, int);struct node *insertAfter(struct node *, int, int);struct node *removeAfter(struct node *, int);struct node *removeCurrent(struct node *);void peek(struct node *);int main(){…

Forklaring av kode:

  1. De to første kodelinjene er de nødvendige inkluderte overskriftsfilene.
  2. Den neste delen beskriver strukturen til hver selvhenvisende node. Den inneholder en verdi og en peker av samme type som strukturen.
  3. Hver struktur knytter gjentatte ganger til strukturobjekter av samme type.
  4. Det er forskjellige funksjonsprototyper for:
    1. Legge til et element i en tom koblet liste
    2. Setter inn på den nåværende spisse posisjonen til en sirkulær koblet liste.
    3. Setter inn etter en bestemt indeksert verdi i den koblede listen.
    4. Fjerne / slette etter en bestemt indeksert verdi i den koblede listen.
    5. Fjerner på den nåværende spisse posisjonen til en sirkulær koblet liste
  5. Den siste funksjonen skriver ut hvert element gjennom en sirkulær traversal i en hvilken som helst tilstand i den koblede listen.
int main(){struct node *last = NULL;last = insertCurrent(last,4);last = removeAfter(last, 4);peek(last);return 0;}struct node* addToEmpty(struct node*last, int data){struct node *temp = (struct node *)malloc(sizeof( struct node));temp->item = data;last = temp;last->next = last;return last;}struct node *insertCurrent(struct node *last, int data)

Forklaring av kode:

  1. For addEmpty-koden, tildel en tom node ved hjelp av malloc-funksjonen.
  2. For denne noden plasserer du dataene til temp-variabelen.
  3. Tilordne og koble den eneste variabelen til tempvariabelen
  4. Returner det siste elementet til hovedkonteksten () / applikasjonen.
struct node *insertCurrent(struct node *last, int data){if(last == NULL){return addToEmpty(last, data);}struct node *temp = (struct node *)malloc(sizeof( struct node));temp -> item = data;temp->next = last->next;last->next = temp;return last;}struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;…

Forklaring av kode

  1. Hvis det ikke er noe element å sette inn, bør du sørge for å legge til en tom liste og returnere kontrollen.
  2. Opprett et midlertidig element å plassere etter det nåværende elementet.
  3. Koble pekepinnene som vist.
  4. Returner den siste pekeren som i forrige funksjon.
… struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;if (last == NULL){return addToEmpty(last, item);}do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found. Please try again");…

Forklaring av kode:

  1. Hvis det ikke er noe element i listen, kan du ignorere dataene, legge til gjeldende element som det siste elementet i listen og returnere kontrollen
  2. For hver iterasjon i gjør-mens-sløyfen, sørg for at det er en tidligere peker som holder det siste gjennomkjørte resultatet.
  3. Først da kan neste gjennomgang forekomme.
  4. Hvis dataene blir funnet, eller temperaturen når tilbake til den siste pekeren, avsluttes gjør-mens-tiden. Den neste delen av koden bestemmer hva som må gjøres med varen.
… if(temp->item != data){printf("Element not found. Please try again");return last;}else{newnode = (struct node *)malloc(sizeof(struct node));newnode->item = item;prev->next = newnode;newnode->next = temp;}return last;}struct node *removeCurrent(struct node *last)…

Forklaring av kode:

  1. Hvis hele listen har blitt krysset, men elementet ikke blir funnet, viser du en "element ikke funnet" -melding og returnerer deretter kontrollen til den som ringer.
  2. Hvis det er funnet en node, og / eller noden ennå ikke er den siste noden, må du opprette en ny node.
  3. Koble den forrige noden med den nye noden. Koble den nåværende noden med temp (traversal-variabelen).
  4. Dette sikrer at elementet plasseres etter en bestemt node i den sirkulære koblede listen. Gå tilbake til den som ringer.
struct node *removeCurrent(struct node *last){if(last == NULL){printf("Element Not Found");return NULL;}struct node *temp = last->next;last->next = temp->next;free(temp);return last;}struct node *removeAfter(struct node *last, int data)

Forklaring av kode

  1. For å fjerne bare den siste (nåværende) noden, sjekk om denne listen er tom. Hvis det er det, kan ikke noe element fjernes.
  2. Tempvariabelen krysser bare en lenke fremover.
  3. Koble den siste pekeren til pekeren etter den første.
  4. Frigjør vikepekeren. Den avdeler den ukoblede siste pekeren.
struct node *removeAfter(struct node *last,int data){struct node *temp = NULL,*prev = NULL;if (last == NULL){printf("Linked list empty. Cannot remove any element\n");return NULL;}temp = last->next;prev = temp;do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found");…

Forklaring av kode

  1. Som med forrige fjerningsfunksjon, sjekk om det ikke er noe element. Hvis dette stemmer, kan ikke noe element fjernes.
  2. Pekere tildeles spesifikke posisjoner for å finne elementet som skal slettes.
  3. Pekerne er avanserte, den ene bak den andre. (tidligere bak temp)
  4. Prosessen fortsetter til et element er funnet, eller neste element trekkes tilbake til den siste pekeren.
if(temp->item != data){printf("Element not found");return last;}else{prev->next = temp->next;free(temp);}return last;}void peek(struct node * last){struct node *temp = last;if (last == NULL){return;

Forklaring av programmet

  1. Hvis elementet ble funnet etter å ha krysset hele den koblede listen, vises en feilmelding som sier at elementet ikke ble funnet.
  2. Ellers deles elementet og frigjøres i trinn 3 og 4.
  3. Den forrige pekeren er koblet til adressen pekt som "neste" av elementet som skal slettes (temp).
  4. Temp-pekeren blir derfor distribuert og frigjort.
… void peek(struct node * last){struct node *temp = last;if (last == NULL){return;}if(last -> next == last){printf("%d-", temp->item);}while (temp != last){printf("%d-", temp->item);temp = temp->next;}}

Forklaring av kode

  1. Titt eller gjennomkjøring er ikke mulig hvis det ikke er behov for null. Brukeren må tildele eller sette inn en node.
  2. Hvis det bare er en node, er det ikke behov for å krysse, nodeens innhold kan skrives ut, og mens loop ikke utføres.
  3. Hvis det er mer enn en node, skriver temp ut alt elementet til det siste elementet.
  4. I det øyeblikket det siste elementet er nådd, sløyfen avsluttes, og funksjonen returnerer anropet til hovedfunksjonen.

Anvendelser av den sirkulære koblede listen

  • Implementering av rund-robin planlegging i systemprosesser og sirkulær planlegging i høyhastighets grafikk.
  • Token ringer planlegging i datanettverk.
  • Den brukes i displayenheter som butikkbrett som krever kontinuerlig gjennomgang av data.