Kruhový propojený seznam: Výhody s příkladem programu C.

Obsah:

Anonim

Co je to kruhový propojený seznam?

Kruhový propojený seznam je posloupnost uzlů uspořádaných tak, aby každý uzel mohl být vysledován sám k sobě. Zde je „uzel“ samoreferenční prvek s ukazateli na jeden nebo dva uzly v bezprostřední blízkosti II.

Níže je znázorněn kruhový propojený seznam se 3 uzly.

Zde vidíte, že každý uzel je zpětně vysledovatelný. Příklad zobrazený výše je kruhový jednotlivě propojený seznam.

Poznámka: Nejjednodušším kruhovým propojeným seznamem je uzel, který sleduje pouze sám sebe, jak je znázorněno

V tomto výukovém programu kruhového propojeného seznamu se naučíte:

  • Co je to kruhový propojený seznam?
  • Základní operace
  • Vkládací operace
  • Operace mazání
  • Procházení kruhového propojeného seznamu
  • Výhody kruhového propojeného seznamu
  • Singly-linked list as a Circular Linked List
  • Aplikace kruhového propojeného seznamu

Základní operace

Základní operace v kruhovém propojeném seznamu jsou:

  1. Vložení
  2. Vymazání a
  3. Traverz
  • Vložení je proces umístění uzlu na určené místo v kruhovém propojeném seznamu.
  • Odstranění je proces odebrání existujícího uzlu ze spojeného seznamu. Uzel lze identifikovat podle výskytu jeho hodnoty nebo podle jeho polohy.
  • Traversal of circle linked list is the process of displaying the whole linked list's contents and retracing back to the source node.

V další části pochopíte vložení uzlu a možné typy vložení do kruhového jednotlivě propojeného seznamu.

Vkládací operace

Zpočátku musíte vytvořit jeden uzel, který ukazuje na sebe, jak je znázorněno na tomto obrázku. Bez tohoto uzlu vytvoří vložení první uzel.

Dále existují dvě možnosti:

  • Vložení na aktuální pozici kruhového propojeného seznamu. To odpovídá vložení na začátek konce pravidelného singulárního propojeného seznamu. V kruhovém propojeném seznamu jsou začátek a konec stejné.
  • Vložení za indexovaný uzel. Uzel by měl být identifikován indexovým číslem odpovídajícím hodnotě jeho prvku.

Pro vložení na začátek / konec kruhového propojeného seznamu, tedy na pozici, kde byl přidán vůbec první uzel,

  • Budete muset přerušit existující vlastní odkaz na existující uzel
  • Další ukazatel nového uzlu bude odkazovat na existující uzel.
  • Další ukazatel posledního uzlu bude ukazovat na vložený uzel.

POZNÁMKA: Ukazatel, který je hlavním tokenem nebo začátek / konec kruhu, lze změnit. Stále se vrátí do stejného uzlu při procházení, diskutováno dopředu.

Kroky v (a) i-iii jsou uvedeny níže:

(Stávající uzel)

KROK 1) Přerušte stávající odkaz

KROK 2) Vytvořte dopředný odkaz (z nového uzlu do stávajícího uzlu)

KROK 3) Vytvořte smyčkový odkaz na první uzel

Dále zkusíte vložení za uzel.

Například vložíme „VALUE2“ za uzel s „VALUE0“. Předpokládejme, že výchozím bodem je uzel s hodnotou „VALUE0“.

  • Budete muset přerušit čáru mezi prvním a druhým uzlem a umístit uzel s hodnotou „VALUE2“ mezi.
  • Další ukazatel prvního uzlu musí odkazovat na tento uzel a další ukazatel tohoto uzlu musí odkazovat na dřívější druhý uzel.
  • Zbytek uspořádání zůstává nezměněn. Všechny uzly jsou zpětně vysledovatelné.

POZNÁMKA: Protože existuje cyklické uspořádání, vložení uzlu zahrnuje stejný postup pro jakýkoli uzel. Ukazatel, který dokončí cyklus, dokončí cyklus stejně jako jakýkoli jiný uzel.

Toto je uvedeno níže:

(Řekněme, že existují pouze dva uzly. Toto je triviální případ)

KROK 1) Odstraňte vnitřní spojení mezi připojenými uzly

KROK 2) Připojte uzel na levé straně k novému uzlu

KROK 3) Připojte nový uzel k uzlu na pravé straně.

Operace mazání

Předpokládejme kruhový propojený seznam se 3 uzly. Případy smazání jsou uvedeny níže:

  • Odstranění aktuálního prvku
  • Odstranění za prvkem.

Mazání na začátku / na konci:

  1. Přejděte na první uzel z posledního uzlu.
  2. Chcete-li odstranit od konce, měl by existovat pouze jeden krok procházení, od posledního uzlu k prvnímu uzlu.
  3. Odstraňte propojení mezi posledním uzlem a dalším uzlem.
  4. Propojte poslední uzel s dalším prvkem prvního uzlu.
  5. Uvolněte první uzel.

(Stávající nastavení)

KROK 1 ) Odstraňte kruhový článek

KROKY 2) Odeberte propojení mezi prvním a dalším, propojte poslední uzel s uzlem následujícím za prvním

KROK 3) Uvolněte / uvolněte první uzel

Odstranění za uzlem:

  1. Procházejte až do dalšího uzlu, který je uzlem, který má být odstraněn.
  2. Přejděte na další uzel a umístěte ukazatel na předchozí uzel.
  3. Připojte předchozí uzel k uzlu za současným uzlem pomocí jeho dalšího ukazatele.
  4. Uvolněte aktuální (přerušený) uzel.

KROK 1) Řekněme, že musíme odstranit uzel s hodnotou „VALUE1“.

KROK 2) Odeberte spojení mezi předchozím uzlem a aktuálním uzlem. Propojte jeho předchozí uzel s dalším uzlem, na který ukazuje aktuální uzel (s VALUE1).

KROK 3) Uvolněte nebo uvolněte aktuální uzel.

Procházení kruhového propojeného seznamu

Chcete-li procházet kruhovým propojeným seznamem, počínaje od posledního ukazatele, zkontrolujte, zda je samotný poslední ukazatel NULL. Pokud je tato podmínka nepravdivá, zkontrolujte, zda existuje pouze jeden prvek. V opačném případě procházejte pomocí dočasného ukazatele, dokud nedosáhnete posledního ukazatele znovu, nebo tolikrát, kolikrát je potřeba, jak je znázorněno níže v GIF.

Výhody kruhového propojeného seznamu

Mezi výhody kruhových propojených seznamů patří:

  1. Žádný požadavek na přiřazení NULL v kódu. Kruhový seznam nikdy neodkazuje na ukazatel NULL, pokud není zcela uvolněn.
  2. Kruhové propojené seznamy jsou výhodné pro koncové operace, protože začátek a konec se shodují. Algoritmy, jako je plánování Round Robin, mohou úhledně eliminovat procesy, které jsou ve frontě cyklicky, aniž by narazily na visící nebo referenční ukazatele NULL.
  3. Kruhový propojený seznam také vykonává všechny běžné funkce jednotlivě propojeného seznamu. Ve skutečnosti kruhové dvojitě propojené seznamy, které jsou popsány níže, mohou dokonce eliminovat potřebu procházení celé délky k vyhledání prvku. Tento prvek by byl nanejvýš pouze přesně opačný než začátek a dokončil by jen polovinu propojeného seznamu.

Singly Linked List as a Circular Linked List

Doporučujeme vám pokusit se přečíst a implementovat níže uvedený kód. Představuje aritmetiku ukazatele spojenou s kruhově propojenými seznamy.

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

Vysvětlení kódu:

  1. První dva řádky kódu jsou nezbytné zahrnuté hlavičkové soubory.
  2. Následující část popisuje strukturu každého samoreferenčního uzlu. Obsahuje hodnotu a ukazatel stejného typu jako struktura.
  3. Každá struktura opakovaně odkazuje na objekty struktury stejného typu.
  4. Existují různé funkční prototypy pro:
    1. Přidání prvku do prázdného propojeného seznamu
    2. Vkládání na aktuálně zaměřenou pozici kruhového propojeného seznamu.
    3. Vkládání za konkrétní indexovanou hodnotu do propojeného seznamu.
    4. Odebrání / odstranění po určité indexované hodnotě v propojeném seznamu.
    5. Odebrání na aktuálně namířené pozici kruhového propojeného seznamu
  5. Poslední funkce vytiskne každý prvek kruhovým průchodem v jakémkoli stavu propojeného seznamu.
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)

Vysvětlení kódu:

  1. U kódu addEmpty přidělte prázdný uzel pomocí funkce malloc.
  2. U tohoto uzlu umístěte data do dočasné proměnné.
  3. Přiřaďte a propojte jedinou proměnnou s dočasnou proměnnou
  4. Vraťte poslední prvek do kontextu main () / aplikace.
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;…

Vysvětlení kódu

  1. Pokud není žádný prvek k vložení, měli byste se ujistit, že přidáte do prázdného seznamu a vrátíte ovládací prvek.
  2. Vytvořte dočasný prvek, který umístíte za aktuální prvek.
  3. Propojte ukazatele podle obrázku.
  4. Vrátí poslední ukazatel jako v předchozí funkci.
… 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");…

Vysvětlení kódu:

  1. Pokud v seznamu není žádný prvek, ignorujte data, přidejte aktuální položku jako poslední položku v seznamu a vraťte ovládací prvek
  2. Pro každou iteraci ve smyčce do-while zajistěte, aby existoval předchozí ukazatel, který obsahuje výsledek posledního procházení.
  3. Teprve potom může dojít k dalšímu průchodu.
  4. Pokud jsou data nalezena nebo teplota dosáhne zpět k poslednímu ukazateli, do-while končí. Další část kódu rozhodne, co je třeba s položkou udělat.
… 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)…

Vysvětlení kódu:

  1. Pokud prošel celý seznam, ale položka nebyla nalezena, zobrazte zprávu „položka nebyla nalezena“ a poté vráťte řízení volajícímu.
  2. Pokud je nalezen uzel a / nebo uzel ještě není posledním uzlem, vytvořte nový uzel.
  3. Propojte předchozí uzel s novým uzlem. Propojte aktuální uzel s temp (proměnná pro procházení).
  4. Tím je zajištěno, že je prvek umístěn za určitým uzlem v kruhovém propojeném seznamu. Vraťte se k volajícímu.
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)

Vysvětlení kódu

  1. Chcete-li odebrat pouze poslední (aktuální) uzel, zkontrolujte, zda je tento seznam prázdný. Pokud ano, nelze odstranit žádný prvek.
  2. Proměnná temp právě projde jeden odkaz vpřed.
  3. Propojte poslední ukazatel s ukazatelem za prvním.
  4. Uvolněte dočasný ukazatel. Zruší spojení nepropojeného posledního ukazatele.
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");…

Vysvětlení kódu

  1. Stejně jako u předchozí funkce odebrání zkontrolujte, zda zde není žádný prvek. Pokud je to pravda, nelze odstranit žádný prvek.
  2. Ukazatelům jsou přiřazeny konkrétní pozice k vyhledání prvku, který má být odstraněn.
  3. Ukazatele jsou pokročilé, jeden za druhým. (předchozí za teplotou)
  4. Proces pokračuje, dokud není prvek nalezen, nebo dokud se další prvek nevrátí k poslednímu ukazateli.
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;

Vysvětlení programu

  1. Pokud byl prvek nalezen po procházení celým propojeným seznamem, zobrazí se chybová zpráva, že položka nebyla nalezena.
  2. Jinak je prvek v krocích 3 a 4 odpojen a uvolněn.
  3. Předchozí ukazatel je propojen s adresou označenou jako „další“ prvkem, který má být odstraněn (dočasná).
  4. Ukazatel dočasné teploty je proto uvolněn a uvolněn.
… 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;}}

Vysvětlení kódu

  1. Nahlédnutí nebo průchod není možný, pokud je potřeba nula. Uživatel potřebuje přidělit nebo vložit uzel.
  2. Pokud existuje pouze jeden uzel, není třeba procházet, lze obsah uzlu vytisknout a smyčka while se nespustí.
  3. Pokud existuje více než jeden uzel, dočasná vytiskne všechny položky až do posledního prvku.
  4. V okamžiku, kdy je dosaženo posledního prvku, smyčka se ukončí a funkce vrátí volání hlavní funkce.

Aplikace kruhového propojeného seznamu

  • Implementace kruhového plánování v systémových procesech a kruhové plánování ve vysokorychlostní grafice.
  • Plánování tokenových kroužků v počítačových sítích.
  • Používá se v zobrazovacích jednotkách, jako jsou prodejní desky, které vyžadují nepřetržité procházení dat.