Ringikujuline lingitud loend: eelised ja puudused

Mis on ringikujuline lingitud loend?

Ringjadaga seotud loend on sõlmede jada, mis on paigutatud nii, et iga sõlme saab uuesti leida.traciseendale. Iga „sõlm” on enesele viitav element, millel on pointerid ühele või kahele sõlmele selle vahetus läheduses.

Allpool on kujutatud 3 sõlmega ringikujulist lingitud loendit.

Siin näete, et iga sõlm on uuestitraciseendale kättesaadav. Ülaltoodud näide on ringikujuline ühekordselt lingitud loend.

Märkus: Lihtsaim ringikujuline lingitud loend on üksiksõlm, mille järgmine pointer tracnaaseb iseenda juurde, nagu allpool näidatud.

Põhi- Operaringloendites

Kolm põhilist toimingut ringloendi puhul on:

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 seda uuesti.tractagasi lähtesõlme.

Järgmises osas selgitatakse, kuidas lisamine toimib ja millised on kaks võimalikku lisamistüüpi ringikujulises üheselt lingitud loendis.

sisestamine Operamine

Esmalt lood ühe sõlme, mille järgmine pointer osutab tagasi iseendale, nagu allpool näidatud. Ilma selle seemnesõlmeta saab esimesest lisamisest loendi esimene sõlm.

Järgmiseks on kaks võimalust.

• Lisamine ringikujuliselt lingitud loendi praegusesse positsiooni. See vastab lisamisele tavalise üheselt lingitud loendi algusesse või lõppu – ringikujuliselt lingitud loendis on algus ja lõpp sama punkt.
• Sisestamine pärast indekseeritud sõlme. Sõlm tuleks identifitseerida indeksi numbriga, mis vastab selle elemendi väärtusele.

Ringikujulise lingitud loendi algusesse või lõppu – st kohta, kuhu lisati esimene sõlm – lisamiseks toimige järgmiselt.

• 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: Ringi algust või lõppu tähistava kursori saab ümber määrata mis tahes sõlmele. Läbiminek naaseb ikkagi samasse sõlme, nagu selles artiklis hiljem käsitletakse.

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

(Olemasolev sõlm)

Step 1) Katkesta olemasolev link

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

Step 3) Loo silmuslink esimesele sõlmele

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

Näiteks sisesta „VALUE2” pärast sõlme, millel on „VALUE0”, eeldades, et alguspunktiks on sõlm, millel on „VALUE0”.

• Katkesta esimese ja teise sõlme vaheline ühendus ning aseta sõlm, mille vahele jääb „VALUE2“.
• Esimese sõlme järgmine pointer lingib uue sõlmega ja uue sõlme järgmine pointer lingib sellega, mis oli varem teine ​​sõlm.
• Ülejäänud paigutus jääb samaks. Kõik sõlmed on ümber ehitatud.tracendale võimelised.

MÄRKUS: Kuna tegemist on tsüklilise paigutusega, on sõlme lisamise protseduur olenemata valitud positsioonist identne. Tsüklit sulgev kursor käitub nagu iga teine ​​loendis olev kursor.

See on näidatud allpool:

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

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

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

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

Kustutamine Operamine

Oletame kolme sõlmega ringikujulist lingitud loendit. Kaks kustutamise juhtu on:

• Praeguse elemendi kustutamine
• Kustutamine pärast elementi.

Kustutamine alguses/lõpus:

1. Liikuge viimasest sõlmest esimesse sõlme.
2. Lõpust kustutamine nõuab ainult ühte läbimisetappi, viimasest sõlmest esimesse sõlme.
3. Kustuta seos viimase ja esimese sõlme vahel.
4. Linkige viimane sõlm esimese sõlme järgmise elemendiga.
5. Vabastage esimene sõlm.

(Olemasolev seadistus)

Step 1) Eemalda ümmargune link

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

Step 3) Vabasta / eralda esimene sõlm

Kustutamine pärast sõlme:

1. Liigutakse seni, 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.

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

Step 2) Eemalda eelmise ja praeguse sõlme vaheline link ning seejärel linki eelmine sõlm otse sõlmega, millele osutab praeguse sõlme järgmine pointer (sõlm pärast VALUE1).

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

Ringikujulise lingitud loendi läbimine

Ringlingitud loendi läbimiseks viimasest pointerist alates kontrollige kõigepealt, kas viimane pointer on NULL. Kui see ei ole NULL, kontrollige, kas loendis on ainult üks element. Vastasel juhul liikuge loendis ajutise pointeriga, kuni jõuate uuesti viimase pointerini, nagu on näidatud allolevas animatsioonis.

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. Ringlingitud loendid on kasulikud loendi lõpu toimingute jaoks, kuna nende algus ja lõpp langevad kokku. Algorithms näiteks ringjadastamine võimaldab järjekorras olevate protsesside vahel sujuvalt liikuda, ilma rippuvate või NULL-viidetega kokku puutumata.
3. Ringlingitud loend toetab endiselt kõiki üheselt lingitud loendi tavalisi toiminguid. Ringlingitud loend kahekordselt lingitud loend võib isegi kaotada vajaduse täispika läbimise järele elemendi leidmiseks – halvimal juhul asub sihtmärk alguskursori vastas, seega tuleb läbida maksimaalselt pool loendist.

Ringliku lingitud loendi puudused

Ringikujulise lingitud loendi kasutamise puudused on järgmised:

1. Ringloendid on keerukamad kui üksikult lingitud loendid.
2. RevRingloendi loomine on keerulisem kui ühe- või kahekordselt lingitud loendi tühistamine.
3. Kui tsükli lõpetamist ei käsitleta hoolikalt, võib läbimiskood siseneda lõpmatusse tsüklisse.
4. Loendi lõppu on raskem leida ja õigeid tsükli juhtimistingimusi kirjutada.
5. Alguses lisamine nõuab kogu loendi läbimist, et jõuda viimase sõlmeni (rakenduse seisukohast).

Üksiklingitud loend ringikujulise lingitud loendina

Soovitame teil lugeda ja rakendada allolevat C-koodi. See illustreerib ringja üheselt lingitud loendiga seotud pointeri 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()
{
...

Koodi selgitus:

1. Esimesed kaks koodirida on vajalikud kaasatud päisefailid.
2. Järgmises osas defineeritakse iga enesele viitava sõlme struktuur. See sisaldab väärtust ja sama tüüpi pointerit kui struktuur.
3. Iga struktuuri eksemplar lingib teiste 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)

Koodi selgitus:

1. Koodi „addToEmpty” jaoks eraldage malloc() funktsiooni abil tühi sõlm.
2. Asetage sissetulevad andmed ajutisse sõlme.
3. Määra ajutine sõlm viimaseks ja sea selle järgmine pointer iseendale, nii et üksik sõlm osutab tagasi iseendale.
4. Tagasta viimane pointer tagasi 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;
…

Koodi selgitus

1. Kui loend on tühi, anna see üle funktsioonile addToEmpty() ja tagasta kontroll.
2. Loo ajutine sõlm, mis asetatakse praeguse sõlme järele.
3. Ühenda kursorid ülaltoodud diagrammil näidatud viisil.
4. Tagasta viimane pointer, mis vastab eelmises funktsioonis kasutatud mustrile.

...
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 loend on tühi, ignoreerige otsinguvõtit, lisage praegune üksus loendi ainsaks sõlmeks ja tagastage juhtelement.
2. Igas do-while tsükli iteratsioonis hoiab eelmine pointer viimati läbitud tulemust.
3. Alles siis toimub järgmine läbimisetapp.
4. „do-while“ funktsioon lõpeb, kui sihtandmed leitakse või kui „temp“ jõuab uuesti viimase pointerini. Järgnev koodiplokk otsustab, mida leitud objektiga peale hakata.

...
    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 nimekiri on läbi käidud, aga soovitud elementi ei leita, kuvatakse teade „Elementi ei leitud” ja kontroll tagastatakse helistajale.
2. Kui sihtsõlm leitakse, eraldage väärtusele uus sõlm.
3. on siin eelmise sõlme uue sõlmega ja lingi uue sõlme järgmine pointer muutujaga temp (läbimismuutuja).
4. See paigutab uue elemendi ringikujulises lingitud loendis kohe sihtsõlme järele. Seejärel naaseb juhtimine kutsujale.

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. Viimase (praeguse) sõlme eemaldamiseks kontrollige kõigepealt, kas loend on tühi. Kui on, siis ei saa ühtegi elementi eemaldada.
2. Muutuja temp liigutab ühe lüli edasi.
3. Seo viimane pointer esimesele sõlmele järgneva sõlmega.
4. Vabastage ajutine pointer, et vabastada linkimata sõlm.

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 kõigepealt, kas loend on tühi. Kui on, siis ei saa ühtegi elementi eemaldada.
2. Kaks osutid kustutatava elemendi leidmiseks on määratud kindlad positsioonid.
3. Osutajad nihutatakse üksteise järel edasi (eelmised rajad, ajutine).
4. Läbimine jätkub seni, kuni sihtelement leitakse või järgmine pointer jõuab uuesti viimase sõlmeni.

    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 kogu lingitud loend läbitakse sihtmärki leidmata, kuvatakse teade „Elementi ei leitud”.
2. Vastasel juhul elemendi linkimine katkestatakse ja see vabastatakse 3. ja 4. etapis.
3. Eelmine pointer on lingitud sõlmega, millele osutab temp'i järgmine pointer (sõlm pärast kustutatavat).
4. Seejärel vabastatakse temperatuuri indikaator.

...
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. Peek-läbimine pole võimalik, kui sõlmi pole ühtegi — kasutaja peab kõigepealt sõlme eraldama või lisama.
2. Kui sõlmi on ainult üks, pole läbimist vaja — sõlme sisu trükitakse otse ja while-tsüklit ei käivitata.
3. Kui sõlmi on rohkem kui üks, prindib temp kõik elemendid kuni viimase elemendini.
4. Viimase elemendini jõudes tsükkel lõpeb ja funktsioon tagastab juhtimise funktsioonile main().

Ringliku lingitud loendi rakendused

• Ringplaanimise rakendamine süsteemiprotsessides ja ringgraafiku rakendamine kiires graafikas.
• Token-ringi ajastamine arvutivõrkudes.
• Kasutatakse kuvamisüksustes, näiteks digitaalsetes müügikohtades, mis vajavad pidevat andmete läbimist.

KKK