Pyöreä linkitetty luettelo: Edut C-ohjelman esimerkillä

Sisällysluettelo:

Anonim

Mikä on pyöreä linkitetty luettelo?

Pyöreä linkitetty luettelo on solmujen sarja, joka on järjestetty siten, että jokainen solmu voidaan jäljittää itseensä. Tässä "solmu" on itseviittaava elementti, joka osoittaa osoittimia yhteen tai kahteen solmuun välittömässä läheisyydessä.

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

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

Huomaa: Yksinkertaisin pyöreä linkitetty luettelo on solmu, joka jäljittää vain itsensä kuvan osoittamalla tavalla

Tässä kiertolinkkiluettelon opetusohjelmassa opit:

  • Mikä on pyöreä linkitetty luettelo?
  • Perustoiminnot
  • Lisäys
  • Poistotoiminto
  • Pyöreän linkitetyn luettelon kulkeminen
  • Pyöreän linkitetyn luettelon edut
  • Yksittäisesti linkitetty luettelo pyöreänä linkitettynä luettelona
  • Pyöreän linkitetyn luettelon sovellukset

Perustoiminnot

Pyöreän linkitetyn luettelon perustoiminnot ovat:

  1. Lisäys
  2. Poisto ja
  3. Liikkuminen
  • Lisäys on solmun sijoittaminen tiettyyn kohtaan pyöreässä linkitetyssä luettelossa.
  • Poisto on prosessi, jolla olemassa oleva solmu poistetaan linkitetystä luettelosta. Solmu voidaan tunnistaa sen arvon esiintymisen tai sijainnin perusteella.
  • Pyöreän linkitetyn luettelon läpikäynti on prosessi, jolla koko linkitetyn luettelon sisältö näytetään ja palataan takaisin lähdesolmulle.

Seuraavassa osassa ymmärretään solmun lisäys ja mahdolliset lisäystyypit Yksittäisesti linkitetyssä ympyräluettelossa.

Lisäys

Aluksi sinun on luotava yksi solmu, joka osoittaa itseensä kuvan osoittamalla tavalla. Ilman tätä solmua lisäys luo ensimmäisen solmun.

Seuraavaksi on kaksi mahdollisuutta:

  • Lisäys pyöreän linkitetyn luettelon nykyiseen sijaintiin. Tämä vastaa lisäystä säännöllisen yksittäisen linkitetyn luettelon alkuun. Pyöreässä linkitetyssä luettelossa alku ja loppu ovat samat.
  • Lisäys indeksoidun solmun jälkeen. Solmu tulisi tunnistaa sen indeksiarvoa vastaavalla indeksinumerolla.

Lisätään pyöreän linkitetyn luettelon alkuun / loppuun, joka on paikassa, johon 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.

HUOMAUTUS: Osoitin, joka on tunnuksen päällikkö tai ympyrän alku / loppu, voidaan muuttaa. Se palaa edelleen samaan solmuun liikenteessä, josta keskustellaan etukäteen.

Vaiheet kohdassa (a) i-iii on esitetty alla:

(Olemassa oleva solmu)

VAIHE 1) Katkaise nykyinen linkki

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

VAIHE 3) Luo silmukka-linkki ensimmäiseen solmuun

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

Lisätään esimerkiksi "VALUE2" solmun "VALUE0" jälkeen. Oletetaan, että aloituskohta on solmu, jolla on "VALUE0".

  • Sinun on katkaistava ensimmäisen ja toisen solmun välinen viiva ja sijoitettava solmu "VALUE2" 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.
  • Loput järjestelystä pysyvät ennallaan. Kaikki solmut ovat itse jäljitettävissä.

HUOMAUTUS: Koska syklinen järjestely on olemassa, solmun lisääminen edellyttää samaa menettelyä kaikille solmuille. Syklin loppuun saattava osoitin suorittaa jakson samalla tavalla kuin kaikki muutkin solmut.

Tämä näkyy alla:

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

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

VAIHE 2) Liitä vasemmanpuoleinen solmu uuteen solmuun

VAIHE 3) Liitä uusi solmu oikeanpuoleiseen solmuun.

Poistotoiminto

Oletetaan, että 3-solmuinen pyöreä linkitetty luettelo. Poistamistapaukset on esitetty alla:

  • Poistetaan nykyinen elementti
  • Poisto elementin jälkeen.

Poisto alussa / lopussa:

  1. Kulje ensimmäiseen solmuun viimeisestä solmusta.
  2. Poistamiseksi lopusta on oltava vain yksi kulkuvaihe, viimeisestä solmusta ensimmäiseen solmuun.
  3. Poista linkki viimeisen ja seuraavan solmun välillä.
  4. Linkitä viimeinen solmu ensimmäisen solmun seuraavaan elementtiin.
  5. Vapauta ensimmäinen solmu.

(Olemassa olevat asetukset)

VAIHE 1 ) Poista pyöreä lenkki

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

VAIHE 3) Vapauta / jaa ensimmäinen solmu

Poisto solmun jälkeen:

  1. Siirtyminen seuraavaan solmuun asti on poistettava solmu.
  2. Kulje seuraavaan solmuun ja aseta osoitin edelliseen solmuun.
  3. Yhdistä edellinen solmu nykyisen solmun jälkeiseen solmuun sen seuraavalla osoittimella.
  4. Vapauta nykyinen (poistettu) solmu.

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

VAIHE 2) Poista linkki edellisen ja nykyisen solmun välillä. Yhdistä edellinen solmu seuraavaan solmuun, jonka nykyinen solmu osoittaa (arvolla VALUE1).

VAIHE 3) Vapauta tai jaa nykyinen solmu.

Pyöreän linkitetyn luettelon kulkeminen

Voit kiertää ympyränmuotoisen linkitetyn luettelon viimeisestä osoittimesta alkaen tarkistamalla, onko viimeinen osoitin itse NULL. Jos tämä ehto on väärä, tarkista, onko elementtejä vain yksi. Muussa tapauksessa kulje väliaikaisen osoittimen avulla, kunnes viimeinen osoitin saavutetaan uudelleen tai niin monta kertaa kuin tarvitaan, kuten alla olevassa GIF: ssä on esitetty.

Pyöreän linkitetyn luettelon edut

Joitakin pyöreiden linkitettyjen luetteloiden etuja ovat:

  1. Ei vaatimusta NULL-määritykselle koodissa. Pyöreä luettelo ei koskaan osoita NULL-osoitinta, ellei sitä ole täysin jaettu.
  2. Pyöreät linkitetyt luettelot ovat edullisia lopputoiminnoille, koska alku ja loppu ovat samanlaisia. Algoritmit, kuten Round Robin -aikataulu, voivat siististi eliminoida prosessit, jotka ovat jonossa pyöreällä tavalla kohtaamatta roikkuvia tai NULL-viitteellisiä osoittimia.
  3. Pyöreä linkitetty luettelo suorittaa myös kaikki linkitetyn luettelon säännölliset toiminnot. Itse asiassa jäljempänä käsitellyt kaksinkertaisesti linkitetyt pyöreät luettelot voivat jopa eliminoida tarpeen käyttää täyspitkää kulkua elementin löytämiseksi. Tämä elementti olisi korkeintaan vain täsmälleen päinvastainen kuin alku, täyttäen vain puolet linkitetystä luettelosta.

Yhdistetysti linkitetty luettelo pyöreänä linkitettynä luettelona

Sinua kehotetaan yrittämään lukea ja ottaa käyttöön alla oleva koodi. Se esittää pyöreisiin linkitettyihin luetteloihin liittyvän osoittimen aritmeettisen.

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

Koodin selitys:

  1. Kaksi ensimmäistä koodiriviä ovat välttämättömiä mukana olevia otsikkotiedostoja.
  2. Seuraava osio kuvaa kunkin itseviittaussolmun rakenteen. Se sisältää arvon ja osoittimen, joka on samantyyppinen kuin rakenne.
  3. Jokainen rakenne linkittää toistuvasti saman tyyppisiin rakenneobjekteihin.
  4. Toiminnalle on erilaisia ​​prototyyppejä:
    1. Elementin lisääminen tyhjään linkitettyyn luetteloon
    2. Lisätään pyöreän linkitetyn luettelon tällä hetkellä terävään kohtaan.
    3. Lisätään tietyn indeksoidun arvon jälkeen linkitettyyn luetteloon.
    4. Poistaminen / poistaminen linkitetyn luettelon tietyn indeksoidun arvon jälkeen.
    5. Poistetaan pyöreän linkitetyn luettelon kärjessä olevasta kohdasta
  5. Viimeinen toiminto tulostaa jokaisen elementin pyöreän liikenteen kautta linkitetyn luettelon missä tahansa 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:

  1. Määritä addEmpty-koodille tyhjä solmu malloc-funktiolla.
  2. Sijoita tälle solmulle tiedot lämpötilamuuttujaan.
  3. Määritä ja linkitä ainoa muuttuja lämpötilamuuttujaan
  4. 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

  1. Jos lisättävää elementtiä ei ole, muista lisätä tyhjään luetteloon ja palauttaa hallinta.
  2. Luo väliaikainen elementti nykyisen elementin jälkeen.
  3. Liitä osoittimet kuvan mukaisesti.
  4. Palauta viimeinen osoitin kuten edellisessä toiminnossa.
… 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:

  1. Jos luettelossa ei ole elementtiä, ohita tiedot, lisää nykyinen kohde luettelon viimeiseksi kohteeksi ja palauta hallinta
  2. Varmista jokaisessa do-while -silmukan iteraatiossa, että on olemassa edellinen osoitin, joka pitää viimeisen kulkeman tuloksen.
  3. Vasta sitten voi tapahtua seuraava kulku.
  4. Jos tiedot löytyvät tai lämpötila saavuttaa viimeisen osoittimen, do-while päättyy. Seuraava koodin osa päättää, mitä kohteelle 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:

  1. Jos koko luettelo on ylitetty, mutta kohdetta ei löydy, näytä viesti "kohdetta ei löydy" ja palauta sitten hallinta soittajalle.
  2. Jos solmu on löydetty ja / tai solmu ei ole vielä viimeinen solmu, luo uusi solmu.
  3. Linkitä edellinen solmu uuteen. Yhdistä nykyinen solmu lämpötilaan (kulkemismuuttuja).
  4. Tämä varmistaa, että elementti sijoitetaan tietyn solmun jälkeen pyöreään linkitettyyn luetteloon. 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

  1. Jos haluat poistaa vain viimeisen (nykyisen) solmun, tarkista, onko tämä luettelo tyhjä. Jos se on, mitään elementtiä ei voida poistaa.
  2. Lämpötilamuuttuja kulkee vain yhden linkin eteenpäin.
  3. Linkitä viimeinen osoitin osoittimeen ensimmäisen jälkeen.
  4. Vapauta lämpötilan osoitin. Se jakaa 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

  1. Kuten edellisessä poistotoiminnossa, tarkista, onko elementtiä. Jos tämä on totta, mitään elementtiä ei voida poistaa.
  2. Osoittimille määritetään tietyt sijainnit poistettavan elementin paikantamiseksi.
  3. Osoittimet ovat edistyneet, peräkkäin. (edellinen lämpötilan takana)
  4. 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

  1. Jos löydetty elementti on kulkenut läpi koko linkitetyn luettelon, näyttöön tulee virheilmoitus, jonka mukaan kohdetta ei löydy.
  2. Muussa tapauksessa elementti poistetaan ja vapautetaan vaiheissa 3 ja 4.
  3. Edellinen osoitin on linkitetty osoitteeseen, jonka poistettava elementti (lämpötila) osoittaa "seuraavaksi".
  4. Lämpötilan osoitin on siis jaettu ja vapautettu.
… 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

  1. Kurkistus tai liikkuminen ei ole mahdollista, jos tarvitset nollaa. Käyttäjän on allokoitava tai lisättävä solmu.
  2. Jos solmuja on vain yksi, ei tarvitse kulkea, solmun sisältö voidaan tulostaa, ja while-silmukka ei toteudu.
  3. Jos solmuja on useampia, lämpötila tulostaa kaikki kohteet viimeiseen elementtiin asti.
  4. Heti kun viimeinen elementti on saavutettu, silmukka päättyy ja toiminto palauttaa puhelun päätoimintoon.

Pyöreän linkitetyn luettelon sovellukset

  • Pyöreän ajoituksen toteuttaminen järjestelmäprosesseissa ja pyöreä ajoitus nopeassa grafiikassa.
  • Tunnus soi aikataulutuksen tietokoneverkoissa.
  • Sitä käytetään näyttöyksiköissä, kuten myymälälevyissä, jotka edellyttävät jatkuvaa tiedonsiirtoa.