Ringkirjaga seotud loend: eelised programmi C näitega

Lang L: none (table-of-contents):

Anonim

Mis on ümmargune lingitud loend?

Ringikujuline lingitud loetelu on sõlmede jada, mis on paigutatud nii, et iga sõlme saab enda juurde tagasi otsida. Siin on "sõlm" isereferatiivne element, mis osutab iI vahetus läheduses asuvat ühte või kahte sõlme.

Allpool on kujutatud ümmargust lingitud loendit, millel on 3 sõlme.

Siin näete, et iga sõlm on iseenda jaoks tagantjärele jälgitav. Eespool toodud näide on ümmargune üksi lingitud loend.

Märkus. Kõige lihtsam ümmargune lingitud loend on sõlm, mis jälgib ainult ennast, nagu näidatud

Selles ümmarguse lingitud loendi õpetuses saate teada:

  • Mis on ümmargune lingitud loend?
  • Põhitoimingud
  • Sisestamine
  • Kustutustoiming
  • Ringikujulise lingitud loendi läbimine
  • Ringkirjaga seotud loendi eelised
  • Üksikult lingitud ümmarguse lingina
  • Ringkirjaga seotud loendi rakendused

Põhitoimingud

Ringlingitud loendi põhitoimingud on järgmised:

  1. Sisestamine
  2. Kustutamine ja
  3. Läbimine
  • Sisestamine on sõlme asetamine ümmarguse lingitud loendi kindlaksmääratud kohta.
  • Kustutamine on olemasoleva sõlme eemaldamine lingitud loendist. Sõlme saab tuvastada selle väärtuse esinemise või asukoha järgi.
  • Ümmarguse lingitud loendi läbimine on kogu lingitud loendi sisu kuvamine ja algsõlme juurde tagasi liikumine.

Järgmises jaotises saate aru sõlme sisestamisest ja ümmarguse üksikult lingitud loendi võimalikest sisestamise tüüpidest.

Sisestamine

Esialgu peate looma ühe sõlme, mis osutab iseendale, nagu sellel pildil näidatud. Ilma selle sõlmeta loob sisestamise esimene sõlm.

Järgmisena on kaks võimalust:

  • Lisamine ümmarguse lingitud loendi praegusele kohale. See vastab sisestamisele tavalise ainsuse lingitud loendi lõpus. Ümmarguse lingiga loendis on algus ja lõpp ühesugused.
  • Lisamine indekseeritud sõlme järele. Sõlme peaks identifitseerima indeksi numbriga, mis vastab selle elemendi väärtusele.

Ümmarguse lingitud loendi algusesse / lõppu sisestamiseks, see on selles kohas, kuhu esimene sõlm lisati,

  • Peate katkestama olemasoleva iselingi olemasoleva sõlmega
  • Uue sõlme järgmine osuti seob olemasoleva sõlme.
  • Viimase sõlme järgmine osuti osutab sisestatud sõlmele.

MÄRKUS. Kursorit, mis on märgistusmeister või ringi algus / lõpp, saab muuta. See naaseb ikkagi läbisõidul samasse sõlme, mida arutati edasi.

Järgnevalt on toodud punktide a) i-iii etapid:

(Olemasolev sõlm)

1. SAMM: katkestage olemasolev link

SAMM 2) Looge edasilink (uuest sõlmest olemasolevaks)

SAMM 3) Looge silmuslink esimesele sõlmele

Järgmisena proovite sisestada sõlme järele.

Näiteks sisestagem "VALUE0" sõlme järele "VALUE2". Oletame, et alguspunktiks on sõlm väärtusega "VALUE0".

  • Peate katkestama joone esimese ja teise sõlme vahel ning asetama nende vahele "VALUE2".
  • Esimese sõlme järgmine osuti peab linkima selle sõlme ja selle sõlme järgmine osuti peab linkima varasema teise sõlme.
  • Ülejäänud kokkulepe jääb muutumatuks. Kõik sõlmed on enda jaoks tagantjärele jälgitavad.

MÄRKUS. Kuna on olemas tsükliline paigutus, hõlmab sõlme sisestamine sama protseduuri mis tahes sõlme puhul. Tsükli lõpuleviiv kursor viib tsükli lõpule nagu kõik muud sõlmed.

See on näidatud allpool:

(Oletame, et sõlme on ainult kaks. See on tühine juhtum)

1. SAMM) Eemaldage ühendatud sõlmede sisemine link

SAMM 2) Ühendage vasakpoolne sõlm uue sõlmega

SAMM 3) Ühendage uus sõlm parempoolse sõlmega.

Kustutustoiming

Oletagem 3-sõlmelist ümmarguse lingiga loendit. Kustutamise juhtumid on toodud allpool:

  • Praeguse elemendi kustutamine
  • Kustutamine elemendi järel.

Kustutamine alguses / lõpus:

  1. Liikuge viimase sõlme esimese sõlme juurde.
  2. Lõpust kustutamiseks peaks olema ainult üks läbisamm, viimasest sõlmest esimese sõlmeni.
  3. Kustutage link viimase ja järgmise sõlme vahel.
  4. Linkige viimane sõlm esimese sõlme järgmise elemendiga.
  5. Vabastage esimene sõlm.

(Olemasolev seadistus)

1. SAMM ) Eemaldage ümmargune lüli

SAMMUD 2) Eemaldage link esimese ja järgmise vahel, linkige viimane sõlm esimesele järgneva sõlmega

3. SAMM) Vabastage / jagage esimene sõlm

Kustutamine sõlme järel:

  1. Travers kuni järgmise sõlmeni on kustutatav sõlm.
  2. Liikuge järgmisele sõlmele, asetades kursori eelmisele sõlmele.
  3. Ühendage eelmine sõlm pärast käesolevat sõlme järgmise osuti abil.
  4. Vabastage praegune (kustutatud) sõlm.

SAMM 1) Oletame, et peame kustutama sõlme väärtusega "VALUE1".

SAMM 2) Eemaldage link eelmise ja praeguse sõlme vahel. Linkige oma eelmine sõlm järgmise, praeguse sõlme osundatava sõlmega (väärtusega VALUE1).

SAMM 3) Vabastage või jagage praegune sõlm lahti.

Ringikujulise lingitud loendi läbimine

Ringikujulise lingitud loendi läbimiseks kontrollige, kas viimane osuti on NULL. Kui see tingimus on vale, kontrollige, kas seal on ainult üks element. Muul juhul liikuge ajutise kursori abil seni, kuni viimane kursor jõuab uuesti või nii mitu korda kui vaja, nagu on näidatud allpool GIF-is.

Ringkirjaga seotud loendi eelised

Mõned ringlingitud loendite eelised on järgmised:

  1. Koodis pole NULL-määrangut. Ringkiri ei osuta kunagi NULL-osutile, kui see pole täielikult jaotatud.
  2. Ringikujulised loendid on lõppoperatsioonide jaoks kasulikud, kuna algus ja lõpp langevad kokku. Sellised algoritmid nagu Round Robin ajakava võimaldavad kenasti kõrvaldada ringikujulises järjekorras olevad protsessid ilma rippuvate või NULL-viitavate osutajateta.
  3. Ringlingitud loend täidab ka kõiki lingitud loendi kõiki tavapäraseid funktsioone. Tegelikult võivad allpool käsitletud ümmargused topeltlingitud loendid isegi kaotada vajaduse täispika läbimise järele elemendi leidmiseks. See element oleks maksimaalselt ainult algusele täpselt vastupidine, täites vaid poole lingitud loendist.

Üksikult lingitud ümmarguse lingina

Soovitame teil proovida allolevat koodi lugeda ja rakendada. See esitab ümmarguste lingidega seotud kursori aritmeetika.

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

Koodi selgitus:

  1. Esimesed kaks koodirida on vajalikud kaasatud päisefailid.
  2. Järgmises jaotises kirjeldatakse iga enesele viitava sõlme struktuuri. See sisaldab struktuuriga sama tüüpi väärtust ja osutit.
  3. Iga struktuur lingib korduvalt sama tüüpi struktuuriobjektidega.
  4. Funktsioonide prototüüpe on erinevaid:
    1. Elemendi lisamine tühja lingitud loendisse
    2. Lisamine ümmarguse lingitud loendi parajasti teravasse kohta.
    3. Lisamine lingitud loendisse konkreetse indekseeritud väärtuse järele.
    4. Kindla indekseeritud väärtuse eemaldamine / kustutamine lingitud loendis.
    5. Ümmarguse lingitud loendi parajasti teravast kohast eemaldamine
  5. Viimane funktsioon prindib iga elemendi ringikujulise läbimise kaudu lingitud loendi mis tahes olekus.
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)

Koodi selgitus:

  1. Koodi addEmpty jaoks eraldage malloc-funktsiooni abil tühi sõlm.
  2. Selle sõlme jaoks asetage andmed muutujale temp.
  3. Määrake ja linkige ainus muutuja temp muutujaga
  4. Viige viimane element tagasi peamise () / rakenduse konteksti.
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;…

Koodi selgitus

  1. Kui sisestada pole ühtegi elementi, peaksite kindlasti lisama tühja loendisse ja tagastama juhtelemendi.
  2. Looge ajutine element, mis asetatakse praeguse elemendi järele.
  3. Linkige kursorid nagu näidatud.
  4. Tagastab viimase kursori nagu eelmises funktsioonis.
… 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");…

Koodi selgitus:

  1. Kui loendis pole ühtegi elementi, ignoreerige andmeid, lisage praegune üksus loendi viimase üksusena ja tagastage juhtelement
  2. Veendumissilmus iga iteratsiooni korral veenduge, et oleks olemas eelmine kursor, mis hoiab viimast läbitud tulemust.
  3. Alles siis võib tekkida järgmine läbisõit.
  4. Kui andmed leitakse või temp jõuab viimase osuti juurde, lõpetatakse tööaeg. Järgmine koodijagu otsustab, mida üksusega teha tuleb.
… 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)…

Koodi selgitus:

  1. Kui kogu loend on läbitud, kuid üksust ei leita, kuvage teade "üksust ei leitud" ja tagastage seejärel helistajale juhtimine.
  2. Kui mõni sõlm on leitud ja / või sõlm pole veel viimane sõlm, siis looge uus sõlm.
  3. Linkige eelmine sõlm uue sõlmega. Linkige praegune sõlm tempiga (läbitav muutuja).
  4. See tagab, et element paigutatakse ümmarguse lingitud loendi konkreetse sõlme taha. Naaske helistaja juurde.
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)

Koodi selgitus

  1. Ainult viimase (praeguse) sõlme eemaldamiseks kontrollige, kas see loend on tühi. Kui see on nii, siis ei saa ühtegi elementi eemaldada.
  2. Temp muutuja läbib lihtsalt ühe lingi edasi.
  3. Linkige viimane osuti pärast esimest.
  4. Vabastage tempokursor. See jaotab lingimata viimase kursori.
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");…

Koodi selgitus

  1. Nagu eelmise eemaldamisfunktsiooni puhul, kontrollige, kas elementi pole. Kui see on tõsi, siis ei saa ühtegi elementi eemaldada.
  2. Kursoritele määratakse kustutatava elemendi leidmiseks kindlad positsioonid.
  3. Osutajad on arenenud, üksteise taga. (eelmine temp taga)
  4. Protsess jätkub seni, kuni leitakse element või järgmine element pöördub tagasi viimase osuti juurde.
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;

Programmi selgitus

  1. Kui element leiti pärast kogu lingitud loendi läbimist, kuvatakse tõrketeade, et üksust ei leitud.
  2. Vastasel juhul tühistatakse element 3. ja 4. etapis.
  3. Eelmine osuti on seotud aadressiga, mille kustutatav element (temp) osutab järgmiseks.
  4. Seepärast jaotatakse temp pointer ja vabastatakse see.
… 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;}}

Koodi selgitus

  1. Piilumine või läbimine pole võimalik, kui vajatakse nulli. Kasutaja peab sõlme eraldama või sisestama.
  2. Kui on ainult üks sõlm, pole vaja läbida, sõlme sisu saab printida ja while-silmus ei käivitu.
  3. Kui sõlme on rohkem kui üks, prindib temp kogu üksuse viimase elemendini.
  4. Hetkel, kui viimane element on saavutatud, lõpetatakse silmus ja funktsioon tagastab kõne põhifunktsioonile.

Ringkirjaga seotud loendi rakendused

  • Ümberplaneerimise rakendamine süsteemiprotsessides ja ringgraafiku rakendamine kiirgraafikas.
  • Token helistab arvutivõrkude ajakava koostamisel.
  • Seda kasutatakse kuvariüksustes nagu kaupluste tahvlid, mis nõuavad andmete pidevat läbimist.