Kruhový prepojený zoznam: Výhody s príkladom programu C.

Obsah:

Anonim

Čo je kruhový prepojený zoznam?

Kruhový prepojený zoznam je postupnosť uzlov usporiadaných tak, aby bolo možné každý uzol vyhľadať sám za seba. Tu je „uzol“ sebareferenčný prvok s ukazovateľmi na jeden alebo dva uzly v bezprostrednej blízkosti II.

Nižšie je znázornený kruhový prepojený zoznam s 3 uzlami.

Tu vidíte, že každý uzol je vysledovateľný sám pre seba. Vyššie uvedený príklad je kruhový jednotlivo prepojený zoznam.

Poznámka: Najjednoduchším kruhovo prepojeným zoznamom je uzol, ktorý sleduje iba seba, ako je to znázornené

V tomto výučbe s kruhovým prepojeným zoznamom sa dozviete:

  • Čo je kruhový prepojený zoznam?
  • Základné operácie
  • Operácia vkladania
  • Operácia vymazania
  • Prechod kruhového prepojeného zoznamu
  • Výhody kruhového prepojeného zoznamu
  • Samostatne prepojený zoznam ako kruhový prepojený zoznam
  • Aplikácie kruhového prepojeného zoznamu

Základné operácie

Základné operácie na kruhovo prepojenom zozname sú:

  1. Vloženie
  2. Vymazanie a
  3. Traverz
  • Vkladanie je proces umiestnenia uzla na určené miesto v kruhovo prepojenom zozname.
  • Vymazanie je proces odstránenia existujúceho uzla z prepojeného zoznamu. Uzol je možné identifikovať podľa výskytu jeho hodnoty alebo podľa jeho polohy.
  • Prechod kruhového prepojeného zoznamu je proces zobrazenia obsahu celého prepojeného zoznamu a návratu späť k zdrojovému uzlu.

V nasledujúcej časti pochopíte vloženie uzla a možné typy vloženia do kruhového jednotlivo prepojeného zoznamu.

Operácia vkladania

Spočiatku musíte vytvoriť jeden uzol, ktorý ukazuje na seba, ako je to znázornené na tomto obrázku. Bez tohto uzla vloženie vytvorí prvý uzol.

Ďalej existujú dve možnosti:

  • Vkladanie na aktuálnej pozícii kruhového prepojeného zoznamu. To zodpovedá vloženiu na začiatok konca pravidelného singulárneho prepojeného zoznamu. V kruhovo prepojenom zozname sú začiatok a koniec rovnaké.
  • Vloženie za indexovaný uzol. Uzol by mal byť identifikovaný indexovým číslom zodpovedajúcim hodnote jeho prvku.

Pre vloženie na začiatok / koniec kruhového prepojeného zoznamu, teda na pozíciu, kde bol pridaný vôbec prvý uzol,

  • Budete musieť prerušiť existujúce prepojenie na existujúci uzol
  • Ďalší ukazovateľ nového uzla bude odkazovať na existujúci uzol.
  • Nasledujúci ukazovateľ posledného uzla bude smerovať na vložený uzol.

POZNÁMKA: Ukazovateľ, ktorý je predlohou tokenu alebo začiatkom / koncom kruhu, je možné zmeniť. Stále sa vráti do toho istého uzla pri prechode, o ktorom sme hovorili vopred.

Kroky v bodoch (a) i-iii sú uvedené nižšie:

(Existujúci uzol)

KROK 1) Prerušte existujúci odkaz

KROK 2) Vytvorte priamy odkaz (z nového uzla do existujúceho)

KROK 3) Vytvorte slučkový odkaz na prvý uzol

Ďalej vyskúšate vloženie za uzol.

Napríklad vložíme „VALUE2“ za uzol s „VALUE0“. Predpokladajme, že východiskovým bodom je uzol s hodnotou „VALUE0“.

  • Budete musieť prerušiť hranicu medzi prvým a druhým uzlom a umiestniť medzi ne uzol s hodnotou „VALUE2“.
  • Nasledujúci ukazovateľ prvého uzla musí odkazovať na tento uzol a ďalší ukazovateľ tohto uzla musí odkazovať na predchádzajúci druhý uzol.
  • Zvyšok usporiadania zostáva nezmenený. Všetky uzly sú spätne vysledovateľné.

POZNÁMKA: Pretože existuje cyklické usporiadanie, vloženie uzla vyžaduje rovnaký postup pre akýkoľvek uzol. Ukazovateľ, ktorý dokončí cyklus, dokončí cyklus rovnako ako ktorýkoľvek iný uzol.

Toto je zobrazené nižšie:

(Povedzme, že existujú iba dva uzly. Toto je triviálny prípad)

KROK 1) Odstráňte vnútorné spojenie medzi pripojenými uzlami

KROK 2) Pripojte uzol na ľavej strane k novému uzlu

KROK 3) Pripojte nový uzol k uzlu na pravej strane.

Operácia vymazania

Predpokladajme 3-uzlový kruhový prepojený zoznam. Prípady odstránenia sú uvedené nižšie:

  • Odstraňuje sa aktuálny prvok
  • Vymazanie po prvku.

Vymazanie na začiatku / na konci:

  1. Prejdite na prvý uzol z posledného uzla.
  2. Ak chcete položku odstrániť z konca, mal by existovať iba jeden krok priechodu, od posledného uzla po prvý uzol.
  3. Odstráňte prepojenie medzi posledným uzlom a ďalším uzlom.
  4. Prepojte posledný uzol s ďalším prvkom prvého uzla.
  5. Uvoľnite prvý uzol.

(Existujúce nastavenie)

KROK 1 ) Odstráňte kruhový článok

KROKY 2) Odstráňte prepojenie medzi prvým a ďalším, prepojte posledný uzol s uzlom nasledujúcim za prvým

KROK 3) Uvoľnite / uvoľnite prvý uzol

Vymazanie za uzlom:

  1. Traverz, až kým ďalší uzol nebude uzlom, ktorý sa má vymazať.
  2. Prejdite na nasledujúci uzol a umiestnite kurzor na predchádzajúci uzol.
  3. Pripojte predchádzajúci uzol k uzlu za súčasným uzlom pomocou nasledujúceho ukazovateľa.
  4. Uvoľnite aktuálny (prerušený) uzol.

KROK 1) Povedzme, že musíme vymazať uzol s hodnotou „VALUE1“.

KROK 2) Odstráňte spojenie medzi predchádzajúcim a súčasným uzlom. Prepojte jeho predchádzajúci uzol s ďalším uzlom označeným aktuálnym uzlom (s VALUE1).

KROK 3) Uvoľnite alebo uvoľnite aktuálny uzol.

Prechod kruhového prepojeného zoznamu

Ak chcete prechádzať kruhovo prepojeným zoznamom, počínajúc od posledného ukazovateľa, skontrolujte, či samotný posledný ukazovateľ má hodnotu NULL. Ak je táto podmienka nepravdivá, skontrolujte, či existuje iba jeden prvok. V opačnom prípade prechádzajte pomocou dočasného ukazovateľa, kým sa znova nedosiahne posledný ukazovateľ, alebo toľkokrát, koľkokrát je potrebné, ako je to znázornené v obrázku GIF nižšie.

Výhody kruhového prepojeného zoznamu

Niektoré z výhod zoznamov kruhového prepojenia sú:

  1. V kóde nie je požiadavka na priradenie NULL. Kruhový zoznam nikdy neukazuje na ukazovateľ NULL, pokiaľ nie je úplne uvoľnený.
  2. Kruhové prepojené zoznamy sú výhodné pre konečné operácie, pretože začiatok a koniec sa zhodujú. Algoritmy, ako je plánovanie Round Robin, môžu prehľadne eliminovať procesy, ktoré sú radené cyklicky, bez toho, aby sa vyskytli visiace alebo referenčné ukazovatele NULL.
  3. Kruhový prepojený zoznam tiež vykonáva všetky bežné funkcie jednotlivo prepojeného zoznamu. V skutočnosti kruhové dvojnásobne prepojené zoznamy, o ktorých sa diskutuje nižšie, môžu dokonca vylúčiť potrebu priechodu celou dĺžkou na vyhľadanie prvku. Tento prvok by bol nanajvýš iba presne oproti začiatku a dokončil by iba polovicu prepojeného zoznamu.

Samostatne prepojený zoznam ako kruhový prepojený zoznam

Odporúčame vám pokúsiť sa prečítať a implementovať kód uvedený nižšie. Predstavuje aritmetiku ukazovateľa spojenú s kruhovo prepojenými zoznamami.

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

Vysvetlenie kódu:

  1. Prvé dva riadky kódu sú potrebné zahrnuté hlavičkové súbory.
  2. Ďalšia časť popisuje štruktúru každého sebareferenčného uzla. Obsahuje hodnotu a ukazovateľ rovnakého typu ako štruktúra.
  3. Každá štruktúra opakovane odkazuje na objekty štruktúry rovnakého typu.
  4. Existujú rôzne funkčné prototypy pre:
    1. Pridanie prvku do prázdneho prepojeného zoznamu
    2. Vkladanie na kruhovo prepojený zoznam v aktuálnej polohe.
    3. Vkladanie za konkrétnu indexovanú hodnotu do prepojeného zoznamu.
    4. Odstránenie / odstránenie po konkrétnej indexovanej hodnote v prepojenom zozname.
    5. Odstraňuje sa na kruhovo prepojenom zozname v súčasnej polohe na špici
  5. Posledná funkcia vytlačí každý prvok kruhovým prechodom v ktoromkoľvek stave prepojeného zoznamu.
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)

Vysvetlenie kódu:

  1. Pre kód addEmpty pridelte prázdny uzol pomocou funkcie malloc.
  2. V tomto uzle umiestnite údaje do dočasnej premennej.
  3. Priraďte a prepojte jedinú premennú s dočasnou premennou
  4. Vráťte posledný prvok do kontextu main () / aplikácie.
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;…

Vysvetlenie kódu

  1. Ak nie je možné vložiť žiadny prvok, mali by ste nezabudnúť pridať do prázdneho zoznamu a vrátiť ovládací prvok.
  2. Vytvorte dočasný prvok, ktorý chcete umiestniť za aktuálny prvok.
  3. Prepojte ukazovatele podľa obrázka.
  4. Vráti posledný ukazovateľ ako v predchádzajúcej funkcii.
… 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");…

Vysvetlenie kódu:

  1. Ak v zozname nie je žiadny prvok, údaje ignorujte, pridajte aktuálnu položku ako poslednú položku v zozname a vráťte ovládací prvok
  2. Pre každú iteráciu v slučke do-while sa uistite, že existuje predchádzajúci ukazovateľ, ktorý obsahuje výsledok posledného prechodu.
  3. Až potom môže dôjsť k ďalšiemu prechodu.
  4. Ak sa nájdu údaje alebo sa teplota vráti späť na posledný ukazovateľ, ukončenie procesu sa ukončí. O tom, čo sa má s položkou urobiť, rozhoduje ďalšia časť kódu.
… 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)…

Vysvetlenie kódu:

  1. Ak prešiel celý zoznam, ale položka sa nenašla, zobrazte správu „položka sa nenašla“ a potom volajúcemu vráťte riadenie.
  2. Ak je nájdený uzol a / alebo uzol ešte nie je posledným uzlom, vytvorte nový uzol.
  3. Prepojte predchádzajúci uzol s novým uzlom. Prepojte aktuálny uzol s teplotou (premenná prechodu).
  4. To zaisťuje, že sa prvok umiestni za konkrétny uzol v zozname kruhových odkazov. Vráťte sa k volajúcemu.
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)

Vysvetlenie kódu

  1. Ak chcete odstrániť iba posledný (aktuálny) uzol, skontrolujte, či je tento zoznam prázdny. Ak je, potom nie je možné odstrániť žiadny prvok.
  2. Premenná temp práve posúva jeden odkaz vpred.
  3. Pripojte posledný ukazovateľ k ukazovateľu za prvým.
  4. Uvoľnite ukazovateľ dočasnej teploty. Zruší spojenie posledného neprepojeného ukazovateľa.
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");…

Vysvetlenie kódu

  1. Rovnako ako v prípade predchádzajúcej funkcie odstránenia, skontrolujte, či tu nie je žiadny prvok. Ak je to pravda, potom nemožno odstrániť žiadny prvok.
  2. Ukazovateľom sa priraďujú konkrétne polohy na vyhľadanie prvku, ktorý sa má vymazať.
  3. Ukazovatele sú posunuté jeden za druhým. (predtým za teplotou)
  4. Proces pokračuje, kým sa nenájde prvok, alebo kým sa ďalší prvok nevráti k poslednému ukazovateľu.
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;

Vysvetlenie programu

  1. Ak sa prvok našiel po prechode celým prepojeným zoznamom, zobrazí sa chybové hlásenie s informáciou, že položka sa nenašla.
  2. V opačnom prípade je prvok v krokoch 3 a 4 prerušený a uvoľnený.
  3. Predchádzajúci ukazovateľ je prepojený s adresou označenou ako „ďalšia“ prvkom, ktorý sa má vymazať (dočasná).
  4. Ukazovateľ teploty je preto uvoľnený a uvoľnený.
… 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;}}

Vysvetlenie kódu

  1. Nahliadnutie alebo prechod nie je možný, ak je potrebných nula. Používateľ musí prideliť alebo vložiť uzol.
  2. Ak je iba jeden uzol, nie je potrebné prechádzať, obsah uzla je možné vytlačiť a slučka while sa nespustí.
  3. Ak je viac ako jeden uzol, dočasná vytlačí celú položku až do posledného prvku.
  4. V okamihu dosiahnutia posledného prvku sa slučka ukončí a funkcia vráti volanie hlavnej funkcii.

Aplikácie kruhového prepojeného zoznamu

  • Implementácia pravidelného plánovania v systémových procesoch a kruhového plánovania vo vysokorýchlostnej grafike.
  • Plánovanie tokenov krúžkov v počítačových sieťach.
  • Používa sa v zobrazovacích jednotkách, ako sú napríklad vývesky, ktoré vyžadujú nepretržitý prechod údajov.