Pyöreä linkitetty luettelo: edut ja haitat

Mikä on pyöreä linkitetty luettelo?

Pyöreä linkitetty lista on solmusarja, joka on järjestetty siten, että jokainen solmu voidaan jäljittää itseensä. Tässä "solmu" on itseviittauselementti, jossa on osoittimet yhteen tai kahteen sen välittömässä läheisyydessä olevaan solmuun.

Alla on esitys pyöreästä linkitetystä luettelosta, jossa on 3 solmua.

Täällä voit nähdä, että jokainen solmu on jäljitettävissä itseensä. Yllä oleva esimerkki on pyöreä yksittäin linkitetty luettelo.

Huomautus: Yksinkertaisin pyöreä linkitetty lista on solmu, joka jäljittää vain itsensä kuvan mukaisesti

Perus OperaCircular Linked -luetteloissa

Pyöreän linkitetyn luettelon perustoiminnot ovat:

lisäys
Poisto ja
traversal

Lisäys on prosessi, jossa solmu asetetaan tiettyyn kohtaan pyöreässä linkitetyssä luettelossa.
Poistaminen on prosessi, jossa olemassa oleva solmu poistetaan linkitetystä luettelosta. Solmu voidaan tunnistaa sen arvon esiintymisen tai sijainnin perusteella.
Pyöreän linkitetyn luettelon läpikulku on prosessi, jossa näytetään koko linkitetyn luettelon sisältö ja palataan takaisin lähdesolmuun.

Seuraavassa osiossa ymmärrät solmun lisäämisen ja mahdolliset lisäystyypit kiertokirjeessä yksitellen linkitetyssä luettelossa.

lisäys OperaTUKSEN

Aluksi sinun on luotava yksi solmu, joka osoittaa itseensä, kuten tässä kuvassa näkyy. Ilman tätä solmua lisäys luo ensimmäisen solmun.

Seuraavaksi on kaksi mahdollisuutta:

Lisäys pyöreän linkitetyn luettelon nykyiseen paikkaan. Tämä vastaa lisäystä tavallisen linkitetyn yksikköluettelon loppuun. Pyöreässä linkitetyssä luettelossa alku ja loppu ovat samat.
Lisäys indeksoidun solmun jälkeen. Solmu tulee tunnistaa sen elementtiarvoa vastaavalla indeksinumerolla.

Lisääminen pyöreän linkitetyn luettelon alkuun/loppuun, eli kohtaan, jossa ensimmäinen solmu lisättiin,

Sinun on katkaistava olemassa oleva itselinkki olemassa olevaan solmuun
Uuden solmun seuraava osoitin linkittää olemassa olevaan solmuun.
Viimeisen solmun seuraava osoitin osoittaa lisättyyn solmuun.

HUOMAA: Osoitin, joka on merkkipäällikkö tai ympyrän alku/loppu, voidaan muuttaa. Se palaa silti samaan solmuun läpikäynnin aikana, josta keskustellaan eteenpäin.

Kohdan (a) i-iii vaiheet näytetään alla:

(Olemassa oleva solmu)

VAIHE 1) Katkaise olemassa oleva linkki

VAIHE 2) Luo eteenpäin linkki (uudesta solmusta olemassa olevaan solmuun)

VAIHE 3) Luo silmukkalinkki ensimmäiseen solmuun

Seuraavaksi yrität lisätä solmun jälkeen.

Lisätään esimerkiksi "ARVO2" solmun "VALUE0" perään. Oletetaan, että aloituspiste on solmu, jonka arvo on "VALUE0".

Sinun on katkaistava viiva ensimmäisen ja toisen solmun välillä ja asetettava solmu "ARVO2":n väliin.
Ensimmäisen solmun seuraavan osoittimen on linkitettävä tähän solmuun ja tämän solmun seuraavan osoittimen on linkitettävä aikaisempaan toiseen solmuun.
Muu järjestely säilyy ennallaan. Kaikki solmut ovat jäljitettävissä itsestään.

HUOMAA: Koska on olemassa syklinen järjestely, solmun lisääminen sisältää saman menettelyn mille tahansa solmulle. Osoitin, joka päättää jakson, päättää jakson aivan kuten mikä tahansa muu solmu.

Tämä näkyy alla:

(Sanotaan, että solmuja on vain kaksi. Tämä on triviaali tapaus)

VAIHE 1) Poista sisälinkki liitettyjen solmujen välillä

VAIHE 2) Yhdistä vasemmanpuoleinen solmu uuteen solmuun

VAIHE 3) Yhdistä uusi solmu oikeanpuoleiseen solmuun.

poisto OperaTUKSEN

Oletetaan 3-solmun pyöreä linkitetty lista. Poistotapaukset on esitetty alla:

Nykyisen elementin poistaminen
Poistaminen elementin jälkeen.

Poisto alussa/lopussa:

Siirry ensimmäiseen solmuun viimeisestä solmusta.
Lopusta poistamista varten tulee olla vain yksi läpikulkuvaihe, viimeisestä solmusta ensimmäiseen solmuun.
Poista linkki viimeisen ja seuraavan solmun välillä.
Linkitä viimeinen solmu ensimmäisen solmun seuraavaan elementtiin.
Vapauta ensimmäinen solmu.

(nykyinen kokoonpano)

STEP 1) Poista pyöreä linkki

VAIHE 2) Poista linkki ensimmäisen ja seuraavan välillä, linkitä viimeinen solmu ensimmäistä seuraavaan solmuun

VAIHE 3) Vapauta/vapauta ensimmäinen solmu

Poistaminen solmun jälkeen:

Kulje, kunnes seuraava solmu on poistettava solmu.
Siirrä seuraavaan solmuun asettamalla osoittimen edelliseen solmuun.
Yhdistä edellinen solmu nykyisen solmun jälkeiseen solmuun käyttämällä sen seuraavaa osoitinta.
Vapauta nykyinen (linkitetty) solmu.

VAIHE 1) Sanotaan, että meidän on poistettava solmu, jossa on "VALUE1".

VAIHE 2) Poista linkki edellisen ja nykyisen solmun välillä. Yhdistä sen edellinen solmu seuraavaan nykyisen solmun osoittamaan solmuun (arvolla VALUE1).

VAIHE 3) Vapauta tai vapauta nykyinen solmu.

Pyöreän linkitetyn luettelon läpikäynti

Jos haluat kulkea pyöreän linkitetyn luettelon läpi viimeisestä osoittimesta alkaen, tarkista, onko viimeinen osoitin itse NULL. Jos tämä ehto on epätosi, tarkista, onko elementtejä vain yksi. Muussa tapauksessa käytä väliaikaista osoitinta, kunnes viimeinen osoitin saavutetaan uudelleen, tai niin monta kertaa kuin tarvitaan alla olevan GIF:n mukaisesti.

Pyöreän linkitetyn luettelon edut

Jotkut pyöreän linkitetyn luettelon eduista ovat:

Ei vaatimusta NULL-määrityksestä koodissa. Pyöreä luettelo ei koskaan osoita NULL-osoittimeen, ellei sitä ole kokonaan vapautettu.
Pyöreät linkitetyt listat ovat edullisia loppuoperaatioille, koska alku ja loppu ovat samat. Algorithms kuten Round Robin -ajoitus voi siististi eliminoida prosesseja, jotka ovat jonossa ympyrämuodossa ilman roikkuvia tai NULL-viittausosoittimia.
Pyöreä linkitetty lista suorittaa myös kaikki yksittäin linkitetyn luettelon säännölliset toiminnot. Itse asiassa pyöreä kaksoislinkitetyt luettelot Jäljempänä käsitellyt toiminnot voivat jopa poistaa tarpeen tehdä täyspitkä läpikulku elementin paikantamiseksi. Tämä elementti olisi korkeintaan vain täsmälleen vastakkainen alkuun nähden ja täydentäisi vain puolet linkitetystä luettelosta.

Pyöreän linkitetyn luettelon haitat

Pyöreän linkitetyn luettelon käytön haitat ovat alla:

Pyöreät luettelot ovat monimutkaisia verrattuna yksittäin linkitetyt luettelot.
Revpyöreän listan erse on monimutkainen verrattuna yksittäisiin tai kaksinkertaisiin luetteloihin.
Jos sitä ei käsitellä huolellisesti, koodi saattaa kulkea äärettömässä silmukassa.
Vaikeampi löytää luettelon lopusta ja silmukan ohjauksesta.
Lisäämällä aloituskohtaan meidän on kuljettava koko luettelo löytääksemme viimeisen solmun. (Toteutusnäkökulma)

Yksittäin linkitetty luettelo kiertokirjeenä linkitettynä luettelona

Sinun kannattaa yrittää lukea ja ottaa käyttöön alla oleva koodi. Se esittää ympyrämuotoisiin linkitettyihin listoihin liittyvän osoittimen aritmetiikkaa.

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

Koodin selitys:

Kaksi ensimmäistä koodiriviä ovat tarvittavat sisällytettävät otsikkotiedostot.
Seuraavassa osiossa kuvataan kunkin itseviittaavan solmun rakenne. Se sisältää arvon ja osoittimen, jotka ovat samaa tyyppiä kuin rakenne.
Jokainen rakenne linkittää toistuvasti samantyyppisiin rakenneobjekteihin.
On olemassa erilaisia toimintoprototyyppejä:
1. Elementin lisääminen tyhjään linkitettyyn luetteloon
2. Asennus osoitteessa tällä hetkellä osoittanut pyöreän linkitetyn luettelon sijainti.
3. Lisääminen tietyn jälkeen indeksoitu arvo linkitetyssä luettelossa.
4. Poistaminen/poistaminen tietyn jälkeen indeksoitu arvo linkitetyssä luettelossa.
5. Poistetaan pyöreän linkitetyn luettelon tällä hetkellä osoittamasta kohdasta
Viimeinen funktio tulostaa jokaisen elementin pyöreän läpikulun missä tahansa linkitetyn luettelon tilassa.

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)

Koodin selitys:

Varaa addEmpty-koodille tyhjä solmu malloc-funktiolla.
Aseta tämän solmun tiedot temp-muuttujaan.
Määritä ja linkitä ainoa muuttuja temp-muuttujaan
Palauta viimeinen elementti main() / application kontekstiin.

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;
…

Koodin selitys

Jos lisättävää elementtiä ei ole, muista lisätä tyhjään luetteloon ja palauttaa ohjaus.
Luo väliaikainen elementti nykyisen elementin jälkeen.
Yhdistä osoittimet kuvan mukaisesti.
Palauta viimeinen osoitin edellisen funktion tapaan.

...
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");
...

Koodin selitys:

Jos luettelossa ei ole elementtiä, ohita tiedot, lisää nykyinen kohde luettelon viimeiseksi kohteeksi ja palauta ohjaus
Varmista jokaisessa do-while-silmukan iteraatiossa, että on olemassa edellinen osoitin, joka sisältää viimeksi kuljetetun tuloksen.
Vasta sitten voi tapahtua seuraava kiertokulku.
Jos tiedot löytyvät tai lämpötila palaa viimeiseen osoittimeen, do-while päättyy. Seuraava koodin osa päättää, mitä tuotteelle on tehtävä.

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

Koodin selitys:

Jos koko luettelo on käyty läpi, mutta kohdetta ei löydy, näytä "kohdetta ei löydy" -viesti ja palauta sitten hallinta soittajalle.
Jos solmu löytyy ja/tai solmu ei ole vielä viimeinen solmu, luo uusi solmu.
Linkki edellinen solmu uudella solmulla. Yhdistä nykyinen solmu temp-arvoon (läpikulkumuuttuja).
Tämä varmistaa, että elementti sijoitetaan tietyn solmun jälkeen pyöreässä linkitetyssä luettelossa. Palaa soittajan luo.

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)

Koodin selitys

Jos haluat poistaa vain viimeisen (nykyisen) solmun, tarkista, onko tämä luettelo tyhjä. Jos on, mitään elementtiä ei voida poistaa.
Temp-muuttuja kulkee vain yhden linkin eteenpäin.
Yhdistä viimeinen osoitin ensimmäisen jälkeen olevaan osoittimeen.
Vapauta lämpötilan osoitin. Se purkaa linkittämättömän viimeisen osoittimen.

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");
...

Koodin selitys

Kuten edellisessä poistotoiminnossa, tarkista, ettei siinä ole elementtiä. Jos tämä on totta, mitään elementtiä ei voida poistaa.
Osoittimet niille on määritetty tietyt paikat poistettavan elementin löytämiseksi.
Osoittimet ovat edistyneet, toinen toistensa takana. (edellinen lämpötilan jälkeen)
Prosessi jatkuu, kunnes elementti löytyy tai seuraava elementti palaa viimeiseen osoittimeen.

    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;

Ohjelman selitys

Jos elementti löytyy koko linkitetyn luettelon läpikäynnin jälkeen, näyttöön tulee virheilmoitus, jossa sanotaan, että kohdetta ei löydy.
Muussa tapauksessa elementti puretaan ja vapautetaan vaiheissa 3 ja 4.
Edellinen osoitin linkitetään poistettavan elementin (temp) "seuraavaksi" osoittamaan osoitteeseen.
Lämpöosoitin vapautetaan siksi ja vapautetaan.

...
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;
    }
}

Koodin selitys

Kurkistus tai läpikulku ei ole mahdollista, jos tarvitaan nollaa. Käyttäjän on allokoitava tai lisättävä solmu.
Jos solmuja on vain yksi, ei tarvitse kulkea läpi, solmun sisältö voidaan tulostaa, eikä while-silmukka suoriteta.
Jos solmuja on useampi kuin yksi, niin temp tulostaa kaiken kohteen viimeiseen elementtiin asti.
Kun viimeinen elementti saavutetaan, silmukka päättyy ja funktio palauttaa kutsun pääfunktiolle.

Circular Linked List -sovellukset

Round-robin-aikataulutuksen toteuttaminen järjestelmäprosesseissa ja kiertoajoitus nopeassa grafiikassa.
Token rings -aikataulu tietokoneverkoissa.
Sitä käytetään näyttöyksiköissä, kuten myymälätauluissa, jotka vaativat jatkuvaa tietojen läpikulkua.

Saatat tykätä: