Ringikujuline lingitud loend: eelised ja puudused

Autor: Sarah Chen Sarah Chen
Hours Ajakohastatud

Mis on ringikujuline lingitud loend?

Ringikujuline lingitud loend on sõlmede jada, mis on paigutatud nii, et iga sõlme saab ise tagasi otsida. Siin on "sõlm" enesele viitav element, mis viitab ühele või kahele sõlmele selle vahetus läheduses.

Allpool on kujutatud 3 sõlmega ringikujulist lingitud loendit.

Ringikujuline lingitud loend

Siin näete, et iga sõlm on ise jälgitav. Ülaltoodud näide on ringikujuline üksikult lingitud loend.

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

Ringikujuline lingitud loend

Põhi- Operalingitud loendites

Ringikujulise lingitud loendi põhitoimingud on järgmised:

  1. sisestamine
  2. Kustutamine ja
  3. Läbisõit
  • Sisestamine on protsess, mille käigus asetatakse sõlm ümmarguse lingitud loendi määratud asukohta.
  • Kustutamine on lingitud loendist olemasoleva sõlme eemaldamise protsess. Sõlme saab tuvastada selle väärtuse esinemise või asukoha järgi.
  • Ringlingitud loendi läbimine on protsess, mille käigus kuvatakse kogu lingitud loendi sisu ja pöördutakse tagasi lähtesõlme.

Järgmises jaotises saate aru sõlme sisestamisest ja ümmarguses üksikult lingitud loendis võimalikud sisestamise tüübid.

sisestamine Operamine

Esialgu peate looma ühe sõlme, mis osutab iseendale, nagu on näidatud sellel pildil. Ilma selle sõlmeta loob sisestamine esimese sõlme.

sisestamine Operamine

Järgmiseks on kaks võimalust.

  • Sisestamine ringikujulise lingitud loendi praegusesse asukohta. See vastab sisestamisele tavalise ainsuse lingitud loendi lõppu. Ringikujulises lingitud loendis on algus ja lõpp samad.
  • Sisestamine pärast indekseeritud sõlme. Sõlm tuleks identifitseerida indeksi numbriga, mis vastab selle elemendi väärtusele.

Sisestamiseks ringikujulise lingitud loendi algusesse/lõppu, st kohta, kus esimene sõlm lisati,

  • Peate katkestama olemasoleva iseühenduse olemasoleva sõlmega
  • Uue sõlme järgmine osuti lingib olemasoleva sõlmega.
  • Viimase sõlme järgmine osuti osutab sisestatud sõlmele.

MÄRKUS. Kursorit, mis on märgi juht või ringi algus/lõpp, saab muuta. See naaseb ikkagi samasse sõlme ka läbisõidul, mida arutatakse eelnevalt.

Punktide (a) i–iii etapid on näidatud allpool:

sisestamine Operamine

(Olemasolev sõlm)

sisestamine Operamine

SAMM 1) Katkesta olemasolev link

sisestamine Operamine

SAMM 2) Edasilingi loomine (uuest sõlmest olemasolevasse sõlme)

sisestamine Operamine

SAMM 3) Loo silmuslink esimesele sõlmele

Järgmisena proovite sisestada pärast sõlme.

Näiteks sisestame sõlme "VALUE2" järele "VALUE0". Oletame, et lähtepunktiks on sõlm väärtusega "VALUE0".

  • Peate katkestama esimese ja teise sõlme vahelise joone ja asetama sõlm "VALUE2" vahele.
  • Esimese sõlme järgmine osuti peab linkima selle sõlmega ja selle sõlme järgmine osuti varasema teise sõlmega.
  • Ülejäänud korraldus jääb muutumatuks. Kõik sõlmed on ise jälgitavad.

MÄRKUS. Kuna tegemist on tsüklilise paigutusega, hõlmab sõlme sisestamine iga sõlme jaoks sama protseduuri. Tsükli lõpetav osuti lõpetab tsükli nagu iga teinegi sõlm.

See on näidatud allpool:

sisestamine Operamine

(Ütleme, et sõlme on ainult kaks. See on triviaalne juhtum)

sisestamine Operamine

SAMM 1) Eemaldage ühendatud sõlmede vaheline sisemine lüli

sisestamine Operamine

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

sisestamine Operamine

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

SEOTUD ARTIKLID

kustutamine Operamine

Oletame 3-sõlmelise ringikujulise lingitud loendi. Kustutamise juhtumid on toodud allpool:

  • Praeguse elemendi kustutamine
  • Kustutamine pärast elementi.

Kustutamine alguses/lõpus:

  1. Liikuge viimasest sõlmest esimesse sõlme.
  2. Lõpust kustutamiseks peaks olema ainult üks läbimise samm, 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.

kustutamine Operamine

(Olemasolev seadistus)

kustutamine Operamine

STEP 1) Eemaldage ringlink

kustutamine Operamine

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

kustutamine Operamine

SAMM 3) Vabastage / eraldage esimene sõlm

Kustutamine pärast sõlme:

  1. Liikuge, kuni järgmine sõlm on kustutatav sõlm.
  2. Liikuge järgmisele sõlmele, asetades kursori eelmisele sõlmele.
  3. Ühendage eelmine sõlm praegusele sõlmele järgneva sõlmega, kasutades selle järgmist kursorit.
  4. Vabastage praegune (lingitud) sõlm.

kustutamine Operamine

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

kustutamine Operamine

SAMM 2) Eemaldage seos eelmise ja praeguse sõlme vahel. Linkige selle eelmine sõlm järgmise sõlmega, millele osutab praegune sõlm (väärtusega 1).

kustutamine Operamine

SAMM 3) Vabastage või eraldage praegune sõlm.

Ringikujulise lingitud loendi läbimine

Ringikujulise lingitud loendi läbimiseks, alustades viimasest kursorist, kontrollige, kas viimane osuti ise on NULL. Kui see tingimus on vale, kontrollige, kas elemente on ainult üks. Vastasel juhul liikuge ajutise kursori abil, kuni jõuate uuesti viimase kursorini või nii mitu korda kui vaja, nagu on näidatud alloleval GIF-il.

Ringikujulise lingitud loendi läbimine

Ringikujulise lingitud loendi eelised

Mõned ringikujuliste lingitud loendite eelised on järgmised:

  1. Koodis ei nõuta NULL-määrangut. Ringikujuline loend ei osuta kunagi NULL-i osutile, kui see pole täielikult eraldatud.
  2. Ringikujulised lingitud loendid on kasulikud lõppoperatsioonide jaoks, kuna algus ja lõpp langevad kokku. Algorithms nagu Round Robini ajakava, saab korralikult kõrvaldada protsessid, mis on järjestatud ringikujuliselt, ilma rippuvate või NULL-i viideteta.
  3. Ringlingitud loend täidab ka kõiki üksikult lingitud loendi tavalisi funktsioone. Tegelikult ringikujuline topeltlingitud loendid allpool käsitletav võib isegi kaotada vajaduse elemendi asukoha leidmiseks täispika läbimise järele. See element oleks kõige rohkem ainult algusest täpselt vastupidine, täites vaid poole lingitud loendist.

Ringliku lingitud loendi puudused

Ringikujulise lingitud loendi kasutamise puudused on järgmised:

  1. Ringnimekirjad on võrreldes nendega keerulised üksikult lingitud loendid.
  2. RevRingloendi erse on keerukas, võrreldes üksikute või kahekordsete loenditega.
  3. Kui seda ei käsitleta hoolikalt, võib kood minna lõpmatusse tsüklisse.
  4. Raskem leida loendi lõppu ja tsükli juhtimist.
  5. Sisestades alguses, peame viimase sõlme leidmiseks läbima täieliku loendi. (Rakendamise perspektiiv)

Üksiklingitud loend ringikujulise lingitud loendina

Soovitame teil proovida allolevat koodi lugeda ja rakendada. See näitab ringikujuliste lingitud loenditega seotud kursori aritmeetikat.

#include<stdio.h>
#include<stdlib.h>

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()
{
...

Üksiklingitud loend

Koodi selgitus:

  1. Esimesed kaks koodirida on vajalikud kaasatud päisefailid.
  2. Järgmises jaotises kirjeldatakse iga eneseviitesõlme struktuuri. See sisaldab struktuuriga sama tüüpi väärtust ja kursorit.
  3. Iga struktuur lingib korduvalt sama tüüpi struktuuriobjektidega.
  4. Funktsioonide prototüübid on erinevad:
    1. Elemendi lisamine tühja lingitud loendisse
    2. Sisestamine juures praegu osutas ringikujulise lingitud loendi asukoht.
    3. Sisestamine pärast konkreetset indekseeritud väärtus lingitud loendis.
    4. Eemaldamine/kustutamine pärast konkreetset indekseeritud väärtus lingitud loendis.
    5. Ringikujulise lingitud loendi praegu suunatud positsiooni 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)

Üksiklingitud loend

Koodi selgitus:

  1. Koodi addEmpty jaoks eraldage malloc funktsiooni abil tühi sõlm.
  2. Asetage selle sõlme andmed tempmuutujasse.
  3. Määrake ja linkige ainuke muutuja ajutise muutujaga
  4. Tagastab viimase elemendi main() / 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;
…

Üksiklingitud loend

Koodi selgitus

  1. Kui sisestatavat elementi pole, peaksite kindlasti lisama tühja loendisse ja tagastama juhtelemendi.
  2. Looge ajutine element, mis asetatakse praeguse elemendi järele.
  3. Ühendage osutid, nagu näidatud.
  4. Tagastab viimase osuti 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");
...

Üksiklingitud loend

Koodi selgitus:

  1. Kui loendis pole elementi, ignoreerige andmeid, lisage aktiivne üksus loendi viimaseks üksuseks ja tagastage juhtelement
  2. Iga iteratsiooni puhul do-while tsüklis veenduge, et oleks olemas eelmine osuti, mis sisaldab viimati läbitud tulemust.
  3. Alles siis võib toimuda järgmine läbisõit.
  4. Kui andmed leitakse või temp jõuab tagasi viimase kursorini, siis do-while lõpeb. Koodi järgmine jaotis otsustab, mida tuleb üksusega teha.
...
    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)
...

Üksiklingitud loend

Koodi selgitus:

  1. Kui kogu loend on läbitud, kuid üksust ei leitud, kuvage teade "üksust ei leitud" ja tagastage juhtimine helistajale.
  2. Kui sõlm on leitud ja/või sõlm pole veel viimane sõlm, looge uus sõlm.
  3. on siin eelmine sõlm uue sõlmega. Ühendage praegune sõlm temp-iga (läbiminev muutuja).
  4. See tagab, et element paigutatakse ringikujulises lingitud loendis konkreetse sõlme järele. Tagasi 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)

Üksiklingitud loend

Koodi selgitus

  1. Ainult viimase (praeguse) sõlme eemaldamiseks kontrollige, kas see loend on tühi. Kui on, ei saa ühtegi elementi eemaldada.
  2. Temp muutuja lihtsalt läbib ühe lingi edasi.
  3. Ühendage viimane osuti esimesele järgneva kursoriga.
  4. Vabastage temperatuurinäidik. See eraldab linkimata viimase osuti.
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");
...

Üksiklingitud loend

Koodi selgitus

  1. Nagu eelmise eemaldamisfunktsiooni puhul, kontrollige, kas elementi pole. Kui see on tõsi, ei saa ühtegi elementi eemaldada.
  2. viiteid kustutatava elemendi leidmiseks on määratud kindlad positsioonid.
  3. Osutajad on üksteise järel edasi tõstetud. (eelmine temp maha jäänud)
  4. Protsess jätkub, kuni element leitakse või järgmine element liigub tagasi viimase kursori 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;

Üksiklingitud loend

Programmi selgitus

  1. Kui element leiti pärast kogu lingitud loendi läbimist, kuvatakse veateade, mis ütleb, et üksust ei leitud.
  2. Vastasel juhul eemaldatakse element linkidest ja vabastatakse sammudes 3 ja 4.
  3. Eelmine osuti on lingitud kustutatava elemendi (temp) poolt kui "järgmine" märgitud aadressiga.
  4. Temperatuuri osuti eraldatakse seetõttu ja vabastatakse.
...
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;
    }
}

Üksiklingitud loend

Koodi selgitus

  1. Piilumine või läbimine pole võimalik, kui vaja on null. Kasutaja peab määrama või sisestama sõlme.
  2. Kui sõlm on ainult üks, pole vaja läbida, sõlme sisu saab printida ja while-tsükkel ei käivitu.
  3. Kui sõlmpunkte on rohkem kui üks, prindib temp kõik elemendid kuni viimase elemendini.
  4. Hetkel, kui jõutakse viimase elemendini, tsükkel lõpeb ja funktsioon tagastab põhifunktsiooni kutse.

Ringliku lingitud loendi rakendused

  • Ringplaanimise rakendamine süsteemiprotsessides ja ringgraafiku rakendamine kiires graafikas.
  • Token rings ajakava koostamine arvutivõrkudes.
  • Seda kasutatakse kuvaseadmetes, nagu kaupluste tahvlid, mis nõuavad pidevat andmete läbimist.