Kaj je krožno povezan seznam?
Krožno povezan seznam je zaporedje vozlišč, razporejenih tako, da se lahko vsako vozlišče povleče nase. Tu je "vozlišče" samoreferenčni element s kazalci na eno ali dve vozlišči v neposredni bližini II.
Spodaj je prikaz krožno povezanega seznama s 3 vozlišči.
Tu lahko vidite, da je vsako vozlišče mogoče izslediti do sebe. Zgornji primer je krožno posamično povezan seznam.
Opomba: Najbolj preprost krožno povezan seznam je vozlišče, ki sledi samo sebi, kot je prikazano
V tej vadnici s krožnim povezanim seznamom boste izvedeli:
- Kaj je krožno povezan seznam?
- Osnovne operacije
- Postopek vstavljanja
- Postopek brisanja
- Prehod krožno povezanega seznama
- Prednosti krožno povezanega seznama
- Enovezen seznam kot krožno povezan seznam
- Uporabe krožno povezanega seznama
Osnovne operacije
Osnovne operacije na krožno povezanem seznamu so:
- Vstavitev
- Izbris in
- Prehod
- Vstavljanje je postopek postavitve vozlišča na določen položaj na krožno povezanem seznamu.
- Brisanje je postopek odstranjevanja obstoječega vozlišča s povezanega seznama. Vozlišče je mogoče prepoznati po pojavu njegove vrednosti ali položaju.
- Prehod krožnega povezanega seznama je postopek prikaza celotne vsebine povezanega seznama in povratek nazaj do izvornega vozlišča.
V naslednjem razdelku boste razumeli vstavljanje vozlišča in vrste vstavljanja, ki so možne v krožnem posamično povezanem seznamu.
Postopek vstavljanja
Sprva morate ustvariti eno vozlišče, ki kaže nase, kot je prikazano na tej sliki. Brez tega vozlišča vstavljanje ustvari prvo vozlišče.
Nato obstajata dve možnosti:
- Vstavitev na trenutni položaj krožno povezanega seznama. To ustreza vstavitvi na začetek konca običajnega singularno povezanega seznama. Na krožno povezanem seznamu sta začetek in konec enaka.
- Vstavljanje po indeksiranem vozlišču. Vozlišče mora biti označeno s številko indeksa, ki ustreza vrednosti njegovega elementa.
Za vstavljanje na začetek / konec krožno povezanega seznama, to je na mesto, kjer je bilo dodano prvo vozlišče,
- Prekiniti boste morali obstoječo samopovezavo do obstoječega vozlišča
- Naslednji kazalec novega vozlišča se bo povezal z obstoječim vozliščem.
- Naslednji kazalec zadnjega vozlišča bo kazal na vstavljeno vozlišče.
OPOMBA: Kazalec, ki je glavni žeton ali začetek / konec kroga, lahko spremenite. Še vedno se bo vrnil na isto vozlišče na prehodu, o katerem smo razpravljali naprej.
Koraki v (a) i-iii so prikazani spodaj:
(Obstoječe vozlišče)
KORAK 1) Prekinite obstoječo povezavo
KORAK 2) Ustvarite posredniško povezavo (od novega vozlišča do obstoječega vozlišča)
KORAK 3) Ustvari povezavo do prvega vozlišča
Nato poskusite vstaviti za vozlišče.
Za vozlišče na primer vstavimo "VALUE2" z "VALUE0". Predpostavimo, da je izhodišče vozlišče z "VALUE0".
- Prekiniti boste morali črto med prvim in drugim vozliščem in vmes postaviti vozlišče z "VALUE2".
- Naslednji kazalec prvega vozlišča se mora povezati na to vozlišče, naslednji kazalec tega vozlišča pa na prejšnje drugo vozlišče.
- Preostali dogovor ostane nespremenjen. Vsa vozlišča so sama do sebe.
OPOMBA: Ker je ciklična razporeditev, vstavljanje vozlišča vključuje enak postopek za katero koli vozlišče. Kazalec, ki zaključi cikel, zaključi cikel tako kot katero koli drugo vozlišče.
To je prikazano spodaj:
(Recimo, da sta le dve vozlišči. To je nepomemben primer)
KORAK 1) Odstranite notranjo povezavo med povezanimi vozlišči
KORAK 2) Levo stransko vozlišče povežite z novim vozliščem
KORAK 3) Novo vozlišče povežite z vozliščem na desni strani.
Postopek brisanja
Predpostavimo 3-vozliščni krožno povezan seznam. Primeri za izbris so navedeni spodaj:
- Brisanje trenutnega elementa
- Izbris po elementu.
Izbris na začetku / koncu:
- Prehod na prvo vozlišče iz zadnjega vozlišča.
- Če želite izbrisati s konca, mora biti samo en korak prečkanja, od zadnjega do prvega vozlišča.
- Izbrišite povezavo med zadnjim in naslednjim vozliščem.
- Zadnje vozlišče povežite z naslednjim elementom prvega vozlišča.
- Osvobodite prvo vozlišče.
(Obstoječa namestitev)
KORAK 1 ) Odstranite krožni člen
KORAKI 2) Odstranite povezavo med prvim in naslednjim, povežite zadnje vozlišče do vozlišča, ki sledi prvemu
KORAK 3) Sprostite / odstranite prvo vozlišče
Izbris po vozlišču:
- Premaknite se do naslednjega vozlišča, ki ga želite izbrisati.
- Premaknite se na naslednje vozlišče in postavite kazalec na prejšnje vozlišče.
- Prejšnje vozlišče povežite z vozliščem za sedanjim vozliščem z naslednjim kazalcem.
- Osvobodite trenutno (delinked) vozlišče.
KORAK 1) Recimo, da moramo vozlišče izbrisati z »VALUE1«.
KORAK 2) Odstranite povezavo med prejšnjim in trenutnim vozliščem. Povežite njegovo prejšnje vozlišče z naslednjim vozliščem, ki ga kaže trenutno vozlišče (z VALUE1).
KORAK 3) Sprostite ali odstranite trenutno vozlišče.
Prehod krožno povezanega seznama
Če želite prečkati krožno povezan seznam, začenši z zadnjim kazalcem, preverite, ali je zadnji kazalec NULL. Če je ta pogoj napačen, preverite, ali je samo en element. V nasprotnem primeru prehodite z začasnim kazalcem, dokler znova ne dosežete zadnjega kazalca, ali tolikokrat, kot je potrebno, kot je prikazano v spodnjem GIF-u.
Prednosti krožno povezanega seznama
Nekatere prednosti krožno povezanih seznamov so:
- V kodi ni zahteve za dodelitev NULL. Krožni seznam nikoli ne kaže na kazalec NULL, če ni popolnoma odstranjen.
- Krožno povezani seznami so koristni za končne operacije, saj se začetek in konec sovpadata. Algoritmi, kot je razporejanje Round Robin, lahko lepo odpravijo procese, ki so v krogu v čakalni vrsti, ne da bi pri tem naleteli na bingljajoče ali NULL-referenčne kazalce.
- Krožno povezan seznam opravlja tudi vse običajne funkcije posamezno povezanega seznama. Dejansko lahko spodaj obravnavani krožni dvojno povezani seznami celo odpravijo potrebo po celovitem prehodu za iskanje elementa. Ta element bi bil kvečjemu le ravno nasprotno od začetka in bi dopolnil le polovico povezanega seznama.
Enotno povezan seznam kot krožno povezan seznam
Priporočamo vam, da poskusite prebrati in uporabiti spodnjo kodo. Predstavlja aritmetiko kazalca, povezano s krožno povezanimi seznami.
#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(){…
Pojasnilo kode:
- Prvi dve vrstici kode sta nujni priloženi datoteki glave.
- Naslednji odsek opisuje strukturo vsakega samoreferenčnega vozlišča. Vsebuje vrednost in kazalec iste vrste kot struktura.
- Vsaka struktura se večkrat poveže s strukturnimi objekti iste vrste.
- Obstajajo različni prototipi funkcij za:
- Dodajanje elementa na prazen povezan seznam
- Vstavljanje na trenutno usmerjenem položaju krožno povezanega seznama.
- Vstavljanje za določeno indeksirano vrednost na povezani seznam.
- Odstranjevanje / brisanje za določeno indeksirano vrednostjo na povezanem seznamu.
- Odstranjevanje na trenutno usmerjenem položaju krožno povezanega seznama
- Zadnja funkcija natisne vsak element skozi krožno prečkanje v katerem koli stanju povezanega seznama.
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)
Pojasnilo kode:
- Za kodo addEmpty s funkcijo malloc dodelite prazno vozlišče.
- Za to vozlišče postavite podatke v spremenljivko temp.
- Edino spremenljivko dodelite in povežite s spremenljivko temp
- Vrnite zadnji element v kontekst main () / application.
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;…
Pojasnilo kode
- Če ni elementa za vstavljanje, morate dodati na prazen seznam in vrniti nadzor.
- Ustvarite začasni element za trenutni element.
- Povežite kazalce, kot je prikazano.
- Vrni zadnji kazalec kot v prejšnji funkciji.
… 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");…
Pojasnilo kode:
- Če na seznamu ni elementa, prezrite podatke, dodajte trenutni element kot zadnji element na seznamu in vrnite nadzor
- Za vsako ponovitev v zanki do-while zagotovite, da obstaja prejšnji kazalec, ki vsebuje zadnji prehodni rezultat.
- Šele nato se lahko zgodi naslednji prehod.
- Če podatke najdemo ali pa temp seže nazaj do zadnjega kazalca, se časovni potek konča. Naslednji odsek kode določa, kaj je treba storiti s predmetom.
… 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)…
Pojasnilo kode:
- Če je bil celoten seznam prehoden, vendar elementa ni mogoče najti, prikažite sporočilo "element not found" in nato vrnite nadzor klicatelju.
- Če najdete vozlišče in / ali še ni zadnje vozlišče, ustvarite novo vozlišče.
- Povežite prejšnje vozlišče z novim vozliščem. Povežite trenutno vozlišče s temp (spremenljivka prečkanja).
- To zagotavlja, da je element postavljen za določeno vozlišče na krožno povezanem seznamu. Vrnite se na klicatelja.
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)
Pojasnilo kode
- Če želite odstraniti samo zadnje (trenutno) vozlišče, preverite, ali je ta seznam prazen. Če je, potem nobenega elementa ni mogoče odstraniti.
- Spremenljivka temp samo preusmeri eno povezavo naprej.
- Povežite zadnji kazalec s kazalcem za prvim.
- Osvobodite kazalnik temperature. Oslobodi nepovezanega zadnjega kazalca.
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");…
Pojasnilo kode
- Kot pri prejšnji funkciji odstranjevanja preverite, ali ni elementa. Če je to res, potem nobenega elementa ni mogoče odstraniti.
- Kazalcem se dodelijo določeni položaji za iskanje elementa, ki ga želite izbrisati.
- Kazalci so napredni, eden za drugim. (prejšnja za temp)
- Postopek se nadaljuje, dokler ni najden element ali pa se naslednji element umakne do zadnjega kazalca.
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;
Pojasnilo programa
- Če je element najden po prehodu celotnega povezanega seznama, se prikaže sporočilo o napaki, da element ni bil najden.
- V nasprotnem primeru se element v korakih 3 in 4 loči in osvobodi.
- Prejšnji kazalec je povezan z naslovom, ki ga element, ki ga želite izbrisati (temp) kaže kot "naslednji".
- Kazalec temperature je zato sproščen in sproščen.
… 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;}}
Pojasnilo kode
- Pogled ali prehod ni mogoč, če ni potrebno nič. Uporabnik mora dodeliti ali vstaviti vozlišče.
- Če je samo eno vozlišče, ni potrebe po prehodu, vsebino vozlišča je mogoče natisniti in zanka while se ne izvede.
- Če je več vozlišč več, potem temp natisne ves element do zadnjega elementa.
- V trenutku, ko je dosežen zadnji element, se zanka konča in funkcija vrne klic glavni funkciji.
Uporabe krožno povezanega seznama
- Izvajanje razporejanja okroglih robin v sistemskih procesih in krožno razporejanje v hitri grafiki.
- Razporejanje žetonov v računalniških omrežjih.
- Uporablja se v prikazovalnih enotah, kot so prodajne deske, ki zahtevajo neprekinjeno prečkanje podatkov.