Hvad er en cirkulær sammenkædet liste?
En cirkulær sammenkædet liste er en sekvens af noder arrangeret på en sådan måde, at hver knude kan trækkes tilbage til sig selv. Her er en "node" et selvhenvisende element med pegepunkter til en eller to noder i iIs umiddelbare nærhed.
Nedenfor er en gengivelse af en cirkulær sammenkædet liste med 3 noder.
Her kan du se, at hver knude kan trækkes tilbage for sig selv. Eksemplet vist ovenfor er en cirkulær enkeltkædet liste.
Bemærk: Den mest enkle cirkulære sammenkædede liste er en knude, der kun sporer til sig selv som vist
I denne cirkulære sammenkædede listevejledning lærer du:
- Hvad er en cirkulær sammenkædet liste?
- Grundlæggende funktioner
- Brug af indsættelse
- Sletning
- Gennemgang af en cirkulær sammenkædet liste
- Fordele ved cirkulær sammenkædet liste
- Enkeltkædet liste som en cirkulærkædet liste
- Anvendelser af den cirkulære sammenkædede liste
Grundlæggende funktioner
De grundlæggende operationer på en cirkulær sammenkædet liste er:
- Indskud
- Sletning og
- Traversal
- Indsættelse er processen med at placere en node på en bestemt position i den cirkulære sammenkædede liste.
- Sletning er processen med at fjerne en eksisterende node fra den linkede liste. Noden kan identificeres ved forekomsten af dens værdi eller ved dens position.
- Gennemgang af en cirkulær sammenkædet liste er processen med at vise hele den sammenkædede listeindhold og vende tilbage til kildeknudepunktet.
I det næste afsnit vil du forstå indsættelse af en node og hvilke typer indsættelse, der er mulige i en cirkulær enkelt forbundet liste.
Brug af indsættelse
Oprindeligt skal du oprette en node, der peger på sig selv som vist på dette billede. Uden denne knude opretter indsættelse den første knude.
Dernæst er der to muligheder:
- Indsættelse på den aktuelle position på den cirkulære sammenkædede liste. Dette svarer til indsættelse i begyndelsen af slutningen af en almindelig, linket liste. I en cirkulær sammenkædet liste er begyndelsen og slutningen den samme.
- Indsættelse efter en indekseret node. Noden skal identificeres med et indeksnummer, der svarer til dens elementværdi.
Til indsættelse i begyndelsen / slutningen af den cirkulære sammenkædede liste, det vil sige på den position, hvor den første nogensinde knude blev tilføjet,
- Du bliver nødt til at bryde den eksisterende selvlink til den eksisterende node
- Den nye nodes næste markør vil linke til den eksisterende node.
- Den sidste nodes næste markør peger på den indsatte node.
BEMÆRK: Markøren, der er tokenmasteren eller begyndelsen / slutningen af cirklen, kan ændres. Det vil stadig vende tilbage til den samme knude på en traversal, diskuteret fremad.
Trin i (a) i-iii er vist nedenfor:
(Eksisterende knude)
TRIN 1) Bryd det eksisterende link
TRIN 2) Opret et fremadgående link (fra ny node til en eksisterende node)
TRIN 3) Opret et looplink til den første node
Dernæst vil du prøve at indsætte efter en node.
Lad os f.eks. Indsætte "VALUE2" efter noden med "VALUE0". Lad os antage, at startpunktet er noden med "VALUE0".
- Du bliver nødt til at bryde linjen mellem den første og anden node og placere noden med "VALUE2" imellem.
- Den første nodes næste markør skal linke til denne node, og denne nodes næste markør skal linke til den tidligere anden node.
- Resten af arrangementet forbliver uændret. Alle noder kan trækkes tilbage for sig selv.
BEMÆRK: Da der er et cyklisk arrangement, indfører en node den samme procedure for enhver node. Markøren, der fuldfører en cyklus, fuldender cyklussen ligesom enhver anden knude.
Dette er vist nedenfor:
(Lad os sige, at der kun er to noder. Dette er et trivielt tilfælde)
TRIN 1) Fjern det indre link mellem de tilsluttede knudepunkter
TRIN 2) Tilslut den venstre knude til den nye knude
TRIN 3) Tilslut den nye knude til højre knude.
Sletning
Lad os antage en cirkulær sammenkædet liste med 3 knudepunkter. Sagerne til sletning er angivet nedenfor:
- Sletning af det aktuelle element
- Sletning efter et element.
Sletning i begyndelsen / slutningen:
- Gå gennem den første knude fra den sidste knude.
- For at slette fra slutningen skal der kun være et traversal trin fra den sidste node til den første node.
- Slet linket mellem den sidste node og den næste node.
- Link den sidste node til det næste element i den første node.
- Gratis den første knude.
(Eksisterende opsætning)
TRIN 1 ) Fjern det cirkulære led
TRIN 2) Fjern forbindelsen mellem den første og den næste, knyt den sidste node til den node, der følger den første
TRIN 3) Frigør / deallokér den første knude
Sletning efter en node:
- Traverser indtil den næste node er den node, der skal slettes.
- Gå gennem den næste knude, placer en markør på den forrige knude.
- Forbind den forrige node til noden efter den nuværende node ved hjælp af dens næste markør.
- Frigør den aktuelle (delinkede) node.
TRIN 1) Lad os sige, at vi har brug for at slette en node med "VALUE1."
TRIN 2) Fjern forbindelsen mellem den forrige node og den aktuelle node. Link dets tidligere node med den næste node, der peges af den aktuelle node (med VALUE1).
TRIN 3) Frigør eller deallokér den aktuelle node.
Gennemgang af en cirkulær sammenkædet liste
For at krydse en cirkulær sammenkædet liste startende fra en sidste markør skal du kontrollere, om den sidste markør i sig selv er NULL. Hvis denne betingelse er falsk, skal du kontrollere, om der kun er et element. Ellers skal du krydse ved hjælp af en midlertidig markør, indtil den sidste markør nås igen eller så mange gange som nødvendigt, som vist i GIF nedenfor.
Fordele ved cirkulær sammenkædet liste
Nogle af fordelene ved cirkulære lister er:
- Intet krav til en NULL-opgave i koden. Den cirkulære liste peger aldrig på en NULL-markør, medmindre den er fuldt deallokaliseret.
- Cirkulære sammenkædede lister er fordelagtige for slutoperationer siden begyndelsen og slutningen falder sammen. Algoritmer som Round Robin-planlægningen kan pænt eliminere processer, der står i kø på en cirkulær måde uden at støde på dinglende eller NULL-henvisende markører.
- Cirkulærkoblet liste udfører også alle regelmæssige funktioner på en enkeltkædet liste. Faktisk kan cirkulære dobbeltkoblede lister, der er diskuteret nedenfor, endda eliminere behovet for en gennemgang i fuld længde for at lokalisere et element. Dette element ville højst kun være modsat starten og udfylde kun halvdelen af den sammenkædede liste.
Enkeltkædet liste som en cirkulær sammenkædet liste
Du opfordres til at forsøge at læse og implementere koden nedenfor. Den præsenterer pegearitmetikken, der er knyttet til cirkulære lister.
#include#include struct 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 af kode:
- De to første kodelinjer er de nødvendige inkluderede headerfiler.
- Det næste afsnit beskriver strukturen for hver selvhenvisende node. Den indeholder en værdi og en markør af samme type som strukturen.
- Hver struktur linker gentagne gange til strukturgenstande af samme type.
- Der er forskellige funktionsprototyper til:
- Tilføjelse af et element til en tom linket liste
- Indsættelse på den aktuelt spidse position af en cirkulær sammenkædet liste.
- Indsættelse efter en bestemt indekseret værdi på den linkede liste.
- Fjernelse / sletning efter en bestemt indekseret værdi på den sammenkædede liste.
- Fjernelse af den aktuelle punkt på en cirkulær sammenkædet liste
- Den sidste funktion udskriver hvert element gennem en cirkulær gennemgang i en hvilken som helst tilstand på den linkede liste.
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 af kode:
- For addEmpty-koden skal du tildele en tom node ved hjælp af malloc-funktionen.
- For denne node skal du placere dataene i temp-variablen.
- Tildel og link den eneste variabel til tempvariablen
- Returner det sidste element til hovedkonteksten () / applikationen.
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 af kode
- Hvis der ikke er noget element at indsætte, skal du sørge for at føje til en tom liste og returnere kontrol.
- Opret et midlertidigt element, der skal placeres efter det aktuelle element.
- Forbind markørerne som vist.
- Returner den sidste markør som i den foregående funktion.
… 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 af kode:
- Hvis der ikke er noget element på listen, skal du ignorere dataene, tilføje det aktuelle element som det sidste element på listen og returnere kontrol
- For hver iteration i do-while-løkken skal du sikre dig, at der er en tidligere markør, der holder det sidst gennemkørte resultat.
- Først da kan den næste gennemgang forekomme.
- Hvis dataene findes, eller temp når tilbage til den sidste markør, afsluttes do-while. Det næste afsnit af kode bestemmer, hvad der skal gø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 af kode:
- Hvis hele listen er blevet krydset, men elementet ikke findes, skal du vise en meddelelse om "element ikke fundet" og derefter returnere kontrol til den, der ringer op.
- Hvis der er fundet en node, og / eller noden endnu ikke er den sidste node, skal du oprette en ny node.
- Link den forrige knude med den nye knude. Forbind den aktuelle node med temp (traversal-variablen).
- Dette sikrer, at elementet placeres efter en bestemt node i den cirkulære sammenkædede liste. Gå tilbage til den, der ringer op.
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 af kode
- For kun at fjerne den sidste (aktuelle) node, skal du kontrollere, om denne liste er tom. Hvis det er tilfældet, kan intet element fjernes.
- Temp-variablen krydser bare et link fremad.
- Knyt den sidste markør til markøren efter den første.
- Frigør tempemarkøren. Den omplacerer den ikke-tilknyttede sidste markør.
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 af kode
- Som med den tidligere fjernelsesfunktion, skal du kontrollere, om der ikke er noget element. Hvis dette er sandt, kan intet element fjernes.
- Markører tildeles specifikke positioner for at finde det element, der skal slettes.
- Markørerne er fremskredne, den ene bag den anden. (tidligere bag temp.)
- Processen fortsætter, indtil et element er fundet, eller det næste element trækkes tilbage til den sidste markør.
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 af programmet
- Hvis elementet blev fundet efter at have krydset hele den sammenkædede liste, vises en fejlmeddelelse om, at elementet ikke blev fundet.
- Ellers delinkeres elementet og frigøres i trin 3 og 4.
- Den forrige markør er knyttet til den adresse, der peges som "næste" af det element, der skal slettes (temp).
- Tempemarkøren bliver derfor deallokeret 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 af kode
- Kig eller gennemkørsel er ikke mulig, hvis der er behov for nul. Brugeren skal allokere eller indsætte en node.
- Hvis der kun er en node, er der ikke behov for at krydse, nodens indhold kan udskrives, og while-løkken udføres ikke.
- Hvis der er mere end en node, så udskriver temp hele elementet indtil det sidste element.
- I det øjeblik det sidste element er nået, løkken afsluttes, og funktionen vender tilbage til hovedfunktionen.
Anvendelser af den cirkulære sammenkædede liste
- Implementering af round-robin planlægning i systemprocesser og cirkulær planlægning i højhastighedsgrafik.
- Token ring planlægning i computernetværk.
- Det bruges i displayenheder som butikskort, der kræver kontinuerlig gennemlæsning af data.