Menu

Datová struktura kruhového propojeného seznamu v C ++ s ilustrací

  • Hlavní
  • Jiný
  • Datová struktura kruhového propojeného seznamu v C ++ s ilustrací

circular linked list data structure c with illustration

Vyzkoušejte Náš Nástroj Pro Odstranění Problémů

Kompletní přehled kruhového propojeného seznamu.

Kruhový propojený seznam je variantou propojeného seznamu. Jedná se o propojený seznam, jehož uzly jsou spojeny tak, že tvoří kruh.

V kruhovém propojeném seznamu není další ukazatel posledního uzlu nastaven na hodnotu null, ale obsahuje adresu prvního uzlu, čímž tvoří kruh.

=> Navštivte zde a dozvíte se C ++ od nuly.

Kruhový propojený seznam

Co se naučíte:

Kruhový propojený seznam v C ++

Uspořádání zobrazené níže je pro jednotlivě propojený seznam.

jednotlivě propojený seznam

Kruhový propojený seznam může být jednotlivě propojený seznam nebo dvojnásobně propojený seznam. V dvojnásobně kruhovém propojeném seznamu je předchozí ukazatel prvního uzlu připojen k poslednímu uzlu, zatímco další ukazatel posledního uzlu je připojen k prvnímu uzlu.

Jeho zastoupení je uvedeno níže.

dvojnásobně kruhový propojený seznam

Prohlášení

Uzel v kruhovém propojeném seznamu můžeme deklarovat jako jakýkoli jiný uzel, jak je znázorněno níže:

struct Node { int data; struct Node *next; };

Abychom mohli implementovat kruhový propojený seznam, udržujeme externí ukazatel „poslední“, který ukazuje na poslední uzel v kruhovém propojeném seznamu. Proto poslední -> další bude ukazovat na první uzel v propojeném seznamu.

Tím zajistíme, že když vložíme nový uzel na začátek nebo na konec seznamu, nemusíme procházet celým seznamem. Je to proto, že poslední ukazuje na poslední uzel, zatímco poslední -> další ukazuje na první uzel.

To by nebylo možné, kdybychom namířili externí ukazatel na první uzel.

Základní operace

Kruhový propojený seznam podporuje vkládání, mazání a procházení seznamu. Nyní budeme podrobně diskutovat o každé z operací.

Vložení

Můžeme vložit uzel do kruhového propojeného seznamu buď jako první uzel (prázdný seznam), na začátek, na konec, nebo mezi ostatní uzly. Podívejme se na každou z těchto operací vložení pomocí níže uvedeného obrázkového znázornění.

# 1) Vložte do prázdného seznamu

Vložte do prázdného seznamu

Pokud v kruhovém seznamu nejsou žádné uzly a seznam je prázdný, poslední ukazatel má hodnotu null, pak vložíme nový uzel N nasměrováním posledního ukazatele na uzel N, jak je znázorněno výše. Další ukazatel N bude ukazovat na samotný uzel N, protože existuje pouze jeden uzel. N se tak stane prvním i posledním uzlem v seznamu.

# 2) Vložte na začátek seznamu

Vložte na začátek seznamu

Jak je znázorněno ve výše uvedené reprezentaci, když přidáme uzel na začátku seznamu, další ukazatel posledního uzlu ukazuje na nový uzel N, čímž se z něj stane první uzel.

N-> další = poslední-> další

Last-> next = N

# 3) Vložte na konec seznamu

poslední uzel ukazuje na nový uzel

Chcete-li vložit nový uzel na konec seznamu, postupujte takto:

jaká je nejlepší aplikace VR

N-> další = poslední -> další;
poslední -> další = N
poslední = N

# 4) Vložte mezi seznam

Vložte mezi seznam

Předpokládejme, že musíme vložit nový uzel N mezi N3 a N4, nejprve musíme projít seznamem a vyhledat uzel, za který se má vložit nový uzel, v tomto případě jeho N3.

Po nalezení uzlu provedeme následující kroky.

N -> další = N3 -> další;
N3 -> další = N

Tím se vloží nový uzel N za N3.

Vymazání

Operace odstranění kruhového propojeného seznamu zahrnuje vyhledání uzlu, který má být odstraněn, a následné uvolnění jeho paměti.

Z tohoto důvodu udržujeme dva další ukazatele proud a prev a poté procházíme seznamem a vyhledáme uzel. Daný uzel, který má být odstraněn, může být první uzel, poslední uzel nebo uzel mezi nimi. V závislosti na umístění nastavíme ukazatele proudu a prev a poté uzel proudu odstraníme.

Níže je uvedeno obrazové znázornění operace odstranění.

operace mazání

Traverz

Traversal je technika návštěvy každého uzlu. V lineárně propojených seznamech, jako je jednotlivě propojený seznam a dvojnásobně propojené seznamy, je procházení snadné, protože navštěvujeme každý uzel a zastavíme se, když narazíme na NULL.

V kruhovém propojeném seznamu to však není možné. V kruhovém propojeném seznamu začínáme od dalšího z posledního uzlu, který je prvním uzlem, a procházíme každý uzel. Zastavíme, když opět dosáhneme prvního uzlu.

Nyní představujeme implementaci operací kruhového propojeného seznamu pomocí C ++ a Java. Zde jsme implementovali operace vkládání, mazání a procházení. Pro jasné pochopení jsme zobrazili kruhový propojený seznam jako

Traverz

K poslednímu uzlu 50 tedy opět připojíme uzel 10, který je prvním uzlem, čímž jej označíme jako kruhový propojený seznam.

#include using namespace std; struct Node { int data; struct Node *next; }; //insert a new node in an empty list struct Node *insertInEmpty(struct Node *last, int new_data) { // if last is not null then list is not empty, so return if (last != NULL) return last; // allocate memory for node struct Node *temp = new Node; // Assign the data. temp -> data = new_data; last = temp; // Create the link. last->next = last; return last; } //insert new node at the beginning of the list struct Node *insertAtBegin(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //set new data to node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; return last; } //insert new node at the end of the list struct Node *insertAtEnd(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //assign data to new node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; last = temp; return last; } //insert a new node in between the nodes struct Node *insertAfter(struct Node *last, int new_data, int after_item) { //return null if list is empty if (last == NULL) return NULL; struct Node *temp, *p; p = last -> next; do { if (p ->data == after_item) { temp = new Node; temp -> data = new_data; temp -> next = p -> next; p -> next = temp; if (p == last) last = temp; return last; } p = p -> next; } while(p != last -> next); cout << 'The node with data '< next; // Point to the first Node in the list. // Traverse the list starting from first node until first node is visited again do { cout <

data <'; p = p -> next; } while(p != last->next); if(p == last->next) coutdata==key && (*head)->next==*head) { free(*head); *head=NULL; } Node *last=*head,*d; // If key is the head if((*head)->data==key) { while(last->next!=*head) // Find the last node of the list last=last->next; // point last node to next of head or second node of the list last->next=(*head)->next; free(*head); *head=last->next; } // end of list is reached or node to be deleted not there in the list while(last->next!=*head&&last->next->data!=key) { last=last->next; } // node to be deleted is found, so free the memory and display the list if(last->next->data==key) { d=last->next; last->next=d->next; cout<<'The node with data '<

Výstup:

Vytvořený kruhový propojený seznam je následující:

10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10

Uzel s daty 10 je odstraněn ze seznamu

Kruhový propojený seznam po odstranění 10 je následující:

20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 20

Dále představujeme implementaci Java pro operace kruhového propojeného seznamu.

//Java class to demonstrate circular linked list operations class Main { static class Node { int data; Node next; }; //insert a new node in the empty list static Node insertInEmpty(Node last, int new_data) { // if list is not empty, return if (last != null) return last; Node temp = new Node(); // create a new node temp.data = new_data; // assign data to new node last = temp; last.next = last; // Create the link return last; } //insert a new node at the beginning of the list static Node insertAtBegin(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); //set data for the node temp.data = new_data; temp.next = last.next; last.next = temp; return last; } //insert a new node at the end of the list static Node insertAtEnd(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); temp.data = new_data; temp.next = last.next; last.next = temp; last = temp; return last; } //insert node in between the nodes in the list static Node addAfter(Node last, int new_data, int after_item) { //if list is null, return if (last == null) return null; Node temp, p; p = last.next; do { if (p.data == after_item) { temp = new Node(); temp.data = new_data; temp.next = p.next; p.next = temp; if (p == last) last = temp; return last; } p = p.next; { while(p != last.next); System.out.println('The node with data ' + after_item + ' not present in the list.'); return last; } //traverse the circular linked list static void traverse(Node last) { Node p; // If list is empty, return. if (last == null) { System.out.println('Cicular linked List is empty.'); return; } p = last.next; // Point to first Node of the list. // Traversing the list. do{ System.out.print(p.data + '==>'); p = p.next; } while(p != last.next); if(p == last.next) System.out.print(p.data); System.out.print(' '); } //delete a node from the list static Node deleteNode(Node head, int key) { //if list is null, return if (head == null) return null; // Find the required node that is to be deleted Node curr = head, prev = new Node(); while (curr.data != key) { if (curr.next == head) { System.out.printf(' Given node ' + key + ' is not found' + “in the list!'); break; } prev = curr; curr = curr.next; } // Check if node is only node if (curr.next == head) { head = null; return head; } // If more than one node, check if it is first node if (curr == head) { prev = head; while (prev.next != head) prev = prev.next; head = curr.next; prev.next = head; } // check if node is last node else if (curr.next == head) { prev.next = head; } else { prev.next = curr.next; } System.out.println('After deleting ' + key + ' the circular list is:'); traverse(head); return head; } // Main code public static void main(String() args){ Node last = null; last = insertInEmpty(last, 30); last = insertAtBegin(last, 20); last = insertAtBegin(last, 10); last = insertAtEnd(last, 40); last = insertAtEnd(last, 60); last = addAfter(last, 50, 40); System.out.println('Circular linked list created is:'); traverse(last); last = deleteNode(last,40); } }

Výstup:

Vytvořený kruhový propojený seznam je:

10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10

Po odstranění 40 je kruhový seznam:

10 ==> 20 ==> 30 ==> 50 ==> 60 ==> 10

Výhody nevýhody

Pojďme diskutovat o některých výhodách a nevýhodách kruhového propojeného seznamu.

Výhody:

  • Můžeme jít do libovolného uzlu a procházet z libovolného uzlu. Musíme jen přestat, když znovu navštívíme stejný uzel.
  • Protože poslední uzel ukazuje na první uzel, přechod na první uzel z posledního uzlu vyžaduje jediný krok.

Nevýhody:

  • Obrácení kruhového propojeného seznamu je těžkopádné.
  • Vzhledem k tomu, že uzly jsou spojeny do kruhu, neexistuje žádné správné označení začátku nebo konce seznamu. Proto je obtížné najít konec seznamu nebo ovládacího prvku smyčky. Pokud se nestaráte, implementace může skončit v nekonečné smyčce.
  • Nemůžeme se vrátit do předchozího uzlu v jediném kroku. Nejprve musíme projít celý seznam.

Aplikace kruhového propojeného seznamu

  • Aplikace kruhového propojeného seznamu v reálném čase může být víceprogramový operační systém, kde se plánuje více programů. Každý program dostane vyhrazené časové razítko, po kterém se prostředky předají jinému programu. To pokračuje nepřetržitě v cyklu. Tuto reprezentaci lze efektivně dosáhnout pomocí kruhového propojeného seznamu.
  • Hry, které se hrají s více hráči, lze také reprezentovat pomocí kruhového propojeného seznamu, ve kterém je každý hráč uzlem, který má šanci hrát.
  • K reprezentaci kruhové fronty můžeme použít kruhový propojený seznam. Tímto způsobem můžeme odstranit dva ukazatele vpředu a vzadu, které se používají pro frontu. Místo toho můžeme použít pouze jeden ukazatel.

Závěr

Kruhový propojený seznam je kolekce uzlů, ve kterých jsou uzly navzájem propojeny a tvoří kruh. To znamená, že místo nastavení dalšího ukazatele posledního uzlu na null je propojen s prvním uzlem.

Kruhový propojený seznam je užitečný při reprezentaci struktur nebo aktivit, které je třeba opakovat znovu a znovu po určitém časovém intervalu, jako jsou programy v prostředí pro více programů. Je to také výhodné pro návrh kruhové fronty.

Kruhové propojené seznamy podporují různé operace, jako je vkládání, mazání a procházení. V tomto tutoriálu jsme tedy operace viděli podrobně.

V našem dalším tématu o datových strukturách se dozvíme o datové struktuře zásobníku.

=> Podívejte se sem a podívejte se zde na A-Z výukových kurzů C ++.

Doporučené čtení

^