Apskritasis susietasis sąrašas: Privalumai naudojant C programos pavyzdį

Turinys:

Anonim

Kas yra žiedinis susietas sąrašas?

Apskritas susietas sąrašas yra mazgų seka, išdėstyta taip, kad kiekvieną mazgą būtų galima susieti su savimi. Čia „mazgas“ yra į save nukreipiantis elementas, nukreipiantis į vieną ar du mazgus, esančius artimiausioje aplinkoje.

Žemiau pateikiamas apskrito susieto sąrašo, kuriame yra 3 mazgai, vaizdas.

Čia galite pamatyti, kad kiekvienas mazgas yra atsekamas pats sau. Aukščiau pateiktas pavyzdys yra apskritas atskirai susietas sąrašas.

Pastaba: paprasčiausias žiedinis susietas sąrašas yra mazgas, kuris seka tik save, kaip parodyta

Šioje apykaitinio susieto sąrašo pamokoje sužinosite:

  • Kas yra žiedinis susietas sąrašas?
  • Pagrindinės operacijos
  • Įterpimo operacija
  • Ištrynimo operacija
  • Apskrito susieto sąrašo perėjimas
  • Apskrito susieto sąrašo privalumai
  • Vienas susietas sąrašas kaip žiedinis susietas sąrašas
  • Apskrito susieto sąrašo programos

Pagrindinės operacijos

Pagrindinės apykaitinio susieto sąrašo operacijos yra šios:

  1. Įterpimas
  2. Ištrinimas ir
  3. Perėjimas
  • Įterpimas yra mazgas dedamas į nurodytą vietą žiediniame susietame sąraše.
  • Trynimas yra esamo mazgo pašalinimas iš susieto sąrašo. Mazgą galima atpažinti pagal jo vertės atsiradimą arba pagal jo padėtį.
  • Apskrito susieto sąrašo perėjimas yra viso susieto sąrašo turinio rodymo ir grįžimo prie šaltinio mazgo procesas.

Kitame skyriuje suprasite mazgo įterpimą ir galimus įterpimo į apskritą pavienių susietų sąrašą tipus.

Įterpimo operacija

Iš pradžių turite sukurti vieną mazgą, kuris nukreiptų į save, kaip parodyta šiame paveikslėlyje. Be šio mazgo įterpimas sukuria pirmąjį mazgą.

Toliau yra dvi galimybės:

  • Įterpimas dabartinėje apskrito susieto sąrašo vietoje. Tai atitinka įterpimą įprasto vienaskaitos susieto sąrašo pabaigoje. Apskrito susieto sąrašo pradžia ir pabaiga yra vienodi.
  • Įterpimas po indeksuoto mazgo. Mazgas turėtų būti identifikuojamas pagal indekso numerį, atitinkantį jo elemento vertę.

Norėdami įterpti žiedinio susieto sąrašo pradžioje / pabaigoje, t. Y. Vietoje, kur buvo pridėtas pirmasis mazgas,

  • Turėsite nutraukti esamą susiejimą su esamu mazgu
  • Kitas naujo mazgo žymeklis bus susietas su esamu mazgu.
  • Kitas paskutinio mazgo rodyklė nukreips į įterptą mazgą.

PASTABA: žymeklį, kuris yra prieigos raktas, arba apskritimo pradžią / pabaigą, galima pakeisti. Vis tiek jis grįš į tą patį mazgą, aptartą iš anksto.

Toliau pateikiami a) i-iii veiksmai:

(Esamas mazgas)

1 ŽINGSNIS. Nutraukite esamą saitą

2 ŽINGSNIS) Sukurkite persiuntimo nuorodą (iš naujo mazgo į esamą)

3 ŽINGSNIS) Sukurkite kilpos nuorodą į pirmąjį mazgą

Tada bandysite įterpti po mazgą.

Pavyzdžiui, įterpkime „VALUE2“ po mazgo su „VALUE0“. Tarkime, kad pradinis taškas yra mazgas su „VALUE0“.

  • Turėsite nutraukti liniją tarp pirmojo ir antrojo mazgo ir tarp jų įdėti mazgą su „VALUE2“.
  • Pirmasis mazgo kitas rodyklė turi susieti su šiuo mazgu, o kitas šio mazgo rodiklis turi susieti su ankstesniu antruoju mazgu.
  • Likusi susitarimo dalis lieka nepakitusi. Visi mazgai yra atsekami patys sau.

PASTABA: Kadangi yra ciklinis išdėstymas, mazgo įterpimas apima tą pačią procedūrą bet kuriam mazgui. Ciklo užbaigimo žymeklis užbaigia ciklą, kaip ir bet kurį kitą mazgą.

Tai parodyta žemiau:

(Tarkime, kad yra tik du mazgai. Tai nereikšmingas atvejis)

1 ŽINGSNIS) Nuimkite vidinę jungtį tarp prijungtų mazgų

2 ŽINGSNIS) Prijunkite kairįjį mazgą prie naujo mazgo

3 ŽINGSNIS) Prijunkite naują mazgą prie dešinės pusės mazgo.

Ištrynimo operacija

Tarkime, kad yra 3 mazgų žiedinis susietas sąrašas. Ištrinimo atvejai pateikti toliau:

  • Trinamas dabartinis elementas
  • Ištrynimas po elemento.

Ištrynimas pradžioje / pabaigoje:

  1. Eikite į pirmąjį mazgą iš paskutinio mazgo.
  2. Norėdami ištrinti iš galo, turėtų būti tik vienas perėjimo žingsnis, nuo paskutinio mazgo iki pirmojo mazgo.
  3. Ištrinkite saitą tarp paskutinio mazgo ir kito mazgo.
  4. Susiekite paskutinį mazgą su kitu pirmojo mazgo elementu.
  5. Išlaisvinkite pirmąjį mazgą.

(Esama sąranka)

1 ŽINGSNIS ) Nuimkite žiedinę grandinę

2 VEIKSMAI) Pašalinkite ryšį tarp pirmo ir kito, susiekite paskutinį mazgą su mazgu, einančiu po pirmojo

3 ŽINGSNIS) Išlaisvinkite / paskirstykite pirmąjį mazgą

Ištrynimas po mazgo:

  1. Traversas iki kito mazgo yra ištrinamas mazgas.
  2. Eikite į kitą mazgą, uždėdami žymeklį ant ankstesnio mazgo.
  3. Prijunkite ankstesnį mazgą prie mazgo po dabartinio mazgo naudodami kitą jo rodyklę.
  4. Atlaisvinkite dabartinį (ištrintą) mazgą.

1 ŽINGSNIS. Tarkime, kad turime ištrinti mazgą su „VALUE1“.

2 ŽINGSNIS) Pašalinkite ryšį tarp ankstesnio mazgo ir dabartinio mazgo. Susiekite ankstesnį mazgą su kitu mazgu, nurodytu dabartinio mazgo (su VALUE1).

3 ŽINGSNIS) Atlaisvinkite arba išspręskite dabartinį mazgą.

Apskrito susieto sąrašo perėjimas

Norėdami pereiti į žiedinį susietą sąrašą, pradedant nuo paskutinio rodyklės, patikrinkite, ar pats paskutinis rodyklė yra NULL. Jei ši sąlyga yra klaidinga, patikrinkite, ar yra tik vienas elementas. Priešingu atveju eikite naudodami laikiną rodyklę, kol vėl pasieksite paskutinį rodyklę, arba tiek kartų, kiek reikia, kaip parodyta žemiau esančiame GIF.

Apskrito susieto sąrašo privalumai

Kai kurie žiedinių susietų sąrašų privalumai yra šie:

  1. Nereikia NULL priskyrimo kodui. Žiediniame sąraše niekada nenurodomas NULL žymeklis, nebent jis būtų visiškai paskirstytas.
  2. Žiediniai susieti sąrašai yra naudingi baigiant operacijas, nes pradžia ir pabaiga sutampa. Tokie algoritmai, kaip „Round Robin“ planavimas, gali tvarkingai pašalinti procesus, kurie yra eilės eilėje, nesusidūrę su kabančiais ar NULL referenciniais rodikliais.
  3. Apskritasis susietasis sąrašas taip pat atlieka visas įprastas vieno susieto sąrašo funkcijas. Tiesą sakant, toliau aptarti žiediniai dvigubai susieti sąrašai netgi gali panaikinti poreikį atlikti visą ilgį, norint rasti elementą. Šis elementas būtų tik visiškai priešingas pradžiai, užpildydamas tik pusę susieto sąrašo.

Vienas susietas sąrašas kaip žiedinis susietas sąrašas

Raginame pabandyti perskaityti ir įdiegti žemiau pateiktą kodą. Čia pateikiama rodyklės aritmetika, susieta su žiediniais susietais sąrašais.

#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(){…

Kodo paaiškinimas:

  1. Pirmosios dvi kodo eilutės yra būtini įtraukti antraštės failai.
  2. Kitame skyriuje aprašoma kiekvieno į save nukreipiančio mazgo struktūra. Jame yra to paties tipo vertė ir žymeklis kaip ir struktūroje.
  3. Kiekviena struktūra pakartotinai susieja su to paties tipo struktūros objektais.
  4. Yra skirtingi funkcijų prototipai:
    1. Elemento įtraukimas į tuščią susietą sąrašą
    2. Įterpiama į apskrito susieto sąrašo padėtį šiuo metu .
    3. Įterpiama po tam tikra indeksuota reikšmė susietame sąraše.
    4. Pašalinimas / ištrynimas po tam tikros indeksuojamos vertės susietame sąraše.
    5. Pašalinimas šiuo metu pažymėtame apskrito susieto sąrašo taške
  5. Paskutinė funkcija išspausdina kiekvieną elementą per apskritą perėjimą bet kurioje susieto sąrašo būsenoje.
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)

Kodo paaiškinimas:

  1. Naudodami „malloc“ funkciją, „addEmpty“ kodui priskirkite tuščią mazgą.
  2. Šiame mazge įdėkite duomenis į temp kintamąjį.
  3. Priskirkite ir susiekite vienintelį kintamąjį su temp kintamuoju
  4. Grąžinkite paskutinį elementą į pagrindinį () / programos kontekstą.
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;…

Kodo paaiškinimas

  1. Jei nėra elemento, kurį įterpti, turėtumėte įsitikinti, kad įtraukėte į tuščią sąrašą ir grąžinkite valdiklį.
  2. Sukurkite laikiną elementą, kurį įdėsite po dabartiniu elementu.
  3. Susiekite rodykles, kaip parodyta.
  4. Grąžinkite paskutinį rodyklę, kaip ir ankstesnėje funkcijoje.
… 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");…

Kodo paaiškinimas:

  1. Jei sąraše nėra elemento, nepaisykite duomenų, pridėkite dabartinį elementą kaip paskutinį elementą sąraše ir grąžinkite valdiklį
  2. Kiekvienai „do-while“ ciklo iteracijai įsitikinkite, kad yra ankstesnis žymeklis, kuriame laikomas paskutinis įveiktas rezultatas.
  3. Tik tada gali įvykti kitas perėjimas.
  4. Jei duomenys randami arba temp pasiekia paskutinį rodyklę, „do-while“ baigiasi. Kitas kodo skyrius nusprendžia, ką reikia daryti su elementu.
… 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)…

Kodo paaiškinimas:

  1. Jei visas sąrašas buvo perkeltas, tačiau elementas nerastas, rodykite pranešimą „elementas nerastas“ ir tada grąžinkite valdymą skambinančiajam.
  2. Jei mazgas rastas ir (arba) mazgas dar nėra paskutinis mazgas, sukurkite naują mazgą.
  3. Susiekite ankstesnį mazgą su nauju mazgu. Susiekite dabartinį mazgą su temp (perėjimo kintamasis).
  4. Tai užtikrina, kad elementas būtų dedamas po tam tikru mazgeliu žiediniame susietame sąraše. Grįžkite pas skambintoją.
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)

Kodo paaiškinimas

  1. Norėdami pašalinti tik paskutinį (dabartinį) mazgą, patikrinkite, ar šis sąrašas tuščias. Jei taip, tada negalima pašalinti jokio elemento.
  2. Temp kintamasis tiesiog pereina vieną nuorodą į priekį.
  3. Susiekite paskutinį rodyklę su rodikliu po pirmojo.
  4. Atlaisvinkite laikrodžio rodyklę. Jis išskiria nesusietą paskutinį rodyklę.
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");…

Kodo paaiškinimas

  1. Kaip ir ankstesnės pašalinimo funkcijos atveju, patikrinkite, ar nėra elemento. Jei tai tiesa, tada elemento pašalinti negalima.
  2. Norint rasti elementą, kurį norite ištrinti, rodyklėms priskiriamos konkrečios pozicijos.
  3. Rodyklės yra pažengusios viena už kitos. (ankstesnė už temp.)
  4. Procesas tęsiasi tol, kol randamas elementas arba kitas elementas grįžta į paskutinį rodyklę.
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;

Programos paaiškinimas

  1. Jei elementas rastas perėjus visą susietą sąrašą, rodomas klaidos pranešimas, sakantis, kad elementas nerastas.
  2. Kitu atveju elementas pašalinamas ir atlaisvinamas atliekant 3 ir 4 veiksmus.
  3. Ankstesnis rodyklė yra susieta su adresu, kurį nurodė „kitas“ ištrinamas elementas (temp).
  4. Todėl laikinas rodyklė yra paskirstyta ir atlaisvinta.
… 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;}}

Kodo paaiškinimas

  1. Žvilgsnis ar perėjimas neįmanomas, jei reikalingas nulis. Vartotojui reikia skirti arba įterpti mazgą.
  2. Jei yra tik vienas mazgas, nereikia kirsti, mazgo turinį galima atsispausdinti ir „while“ kilpa nevykdoma.
  3. Jei yra daugiau nei vienas mazgas, tada temp spausdina visą elementą iki paskutinio elemento.
  4. Kai pasiekiamas paskutinis elementas, ciklas baigiasi ir funkcija grąžina skambutį į pagrindinę funkciją.

Apskrito susieto sąrašo programos

  • Pirmojo planavimo planavimo įgyvendinimas sistemos procesuose ir apskrito planavimas didelės spartos grafikoje.
  • Žetonų žiedai planuoja kompiuterinius tinklus.
  • Jis naudojamas rodymo įrenginiuose, pavyzdžiui, parduotuvių lentose, kur reikalingas nuolatinis duomenų perėjimas.