Meni

Struktura podatkov krožnega povezanega seznama v jeziku C ++ z ilustracijo

  • Glavni
  • Drugo
  • Struktura podatkov krožnega povezanega seznama v jeziku C ++ z ilustracijo

circular linked list data structure c with illustration

Preizkusite Naš Instrument Za Odpravo Težav

Popoln pregled krožno povezanega seznama.

Krožno povezan seznam je različica povezanega seznama. To je povezan seznam, katerega vozlišča so povezana tako, da tvorijo krog.

Na krožno povezanem seznamu naslednji kazalec zadnjega vozlišča ni nastavljen na nič, vsebuje pa naslov prvega vozlišča, s čimer tvori krog.

=> Obiščite tukaj, če se želite naučiti C ++ iz nič.

Krožno povezan seznam

Kaj se boste naučili:

Krožno povezan seznam v jeziku C ++

Spodaj prikazana ureditev je za posamezno povezan seznam.

enojno povezan seznam

Krožno povezan seznam je lahko posamezno povezan ali dvojno povezan seznam. Na dvojno krožno povezanem seznamu je prejšnji kazalec prvega vozlišča povezan z zadnjim vozliščem, medtem ko je naslednji kazalec zadnjega vozlišča povezan s prvim vozliščem.

Njegova predstavitev je prikazana spodaj.

dvojno krožno povezan seznam

Izjava

Vozlišče na krožno povezanem seznamu lahko prijavimo kot katero koli drugo vozlišče, kot je prikazano spodaj:

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

Za izvedbo krožno povezanega seznama vzdržujemo zunanji kazalec 'zadnji', ki kaže na zadnje vozlišče na krožno povezanem seznamu. Zato bo last-> next kazal na prvo vozlišče na povezanem seznamu.

S tem zagotovimo, da ko vstavimo novo vozlišče na začetek ali konec seznama, nam ni treba prečkati celotnega seznama. To je zato, ker zadnje kaže na zadnje vozlišče, medtem ko zadnje-> naslednje kaže na prvo vozlišče.

To ne bi bilo mogoče, če bi zunanji kazalec usmerili na prvo vozlišče.

Osnovne operacije

Krožno povezan seznam podpira vstavljanje, brisanje in prehod seznama. Zdaj bomo podrobno razpravljali o vsaki operaciji.

Vstavitev

Vozlišče lahko vstavimo v krožno povezan seznam bodisi kot prvo vozlišče (prazen seznam), na začetku, na koncu ali med drugimi vozlišči. Oglejmo si vsako od teh postopkov vstavljanja s spodnjo slikovno predstavitvijo.

# 1) Vstavite na prazen seznam

Vstavite na prazen seznam

Ko na krožnem seznamu ni vozlišč in je seznam prazen, je zadnji kazalec ničen, nato vstavimo novo vozlišče N, tako da zadnji kazalec usmerimo na vozlišče N, kot je prikazano zgoraj. Naslednji kazalec N bo kazal na samo vozlišče N, saj je vozlišče samo eno. Tako N postane tako prvo kot zadnje vozlišče na seznamu.

# 2) Vstavite na začetek seznama

Vstavite na začetek seznama

Kot je prikazano v zgornji predstavitvi, ko vozlišče dodamo na začetek seznama, naslednji kazalec zadnjega vozlišča kaže na novo vozlišče N, s čimer postane prvo vozlišče.

N-> naslednji = zadnji-> naslednji

Zadnji-> naslednji = N

# 3) Vstavite na koncu seznama

zadnje vozlišče kaže na novo vozlišče

Če želite na konec seznama vstaviti novo vozlišče, sledimo tem korakom:

vprašanje in odgovori za preizkušanje programske opreme za izkušene

N-> naslednji = zadnji -> naslednji;
zadnji -> naslednji = N
zadnji = N

# 4) Vstavite med seznam

Vstavite med seznam

Recimo, da moramo med N3 in N4 vstaviti novo vozlišče N, najprej moramo prečkati seznam in poiskati vozlišče, po katerem naj bi bilo novo vozlišče vstavljeno, v tem primeru N3.

Ko se vozlišče nahaja, izvedemo naslednje korake.

N -> naslednji = N3 -> naslednji;
N3 -> naslednji = N

To vstavi novo vozlišče N za N3.

Izbris

Postopek brisanja krožno povezanega seznama vključuje iskanje vozlišča, ki ga je treba izbrisati, in nato sprostitev njegovega pomnilnika.

Za to vzdržujemo dva dodatna kazalca curr in prev in nato prehodimo seznam, da poiščemo vozlišče. Dano vozlišče, ki ga je treba izbrisati, je lahko prvo vozlišče, zadnje vozlišče ali vozlišče vmes. Glede na lokacijo nastavimo kazalca curr in prev in nato izbrišemo vozlišče curr.

Slikovna predstavitev postopka brisanja je prikazana spodaj.

operacija brisanja

Prehod

Prehod je tehnika obiska vsakega vozlišča. V linearnih povezanih seznamih, kot so posamično povezani seznami in dvojno povezani seznami, je prehod enostaven, saj obiščemo vsako vozlišče in se ustavimo ob NULL.

Vendar to na krožno povezanem seznamu ni mogoče. Na krožno povezanem seznamu začnemo od naslednjega zadnjega vozlišča, ki je prvo vozlišče, in prehodimo vsako vozlišče. Ustavimo se, ko ponovno pridemo do prvega vozlišča.

Zdaj predstavljamo izvedbo operacij krožno povezanega seznama z uporabo C ++ in Jave. Tu smo izvedli operacije vstavljanja, brisanja in prečkanja. Zaradi jasnega razumevanja smo krožno povezani seznam prikazali kot

Prehod

Tako na zadnje vozlišče 50 spet pritrdimo vozlišče 10, ki je prvo vozlišče, s čimer ga označimo kot krožno povezan 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 '<

Izhod:

Ustvarjen krožno povezan seznam je naslednji:

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

Vozlišče s podatki 10 se izbriše s seznama

Krožno povezan seznam po izbrisu 10 je naslednji:

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

Nato predstavimo implementacijo Jave za operacije krožnega povezanega seznama.

//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); } }

Izhod:

Ustvarjen krožno povezan seznam je:

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

Po izbrisu 40 je okrožni seznam:

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

Prednosti / slabosti

Pogovorimo se o nekaterih prednostih in slabostih krožno povezanega seznama.

Prednosti:

  • Lahko gremo na katero koli vozlišče in prehodimo iz katerega koli vozlišča. Nehati se moramo, ko znova obiščemo isto vozlišče.
  • Ko zadnje vozlišče kaže na prvo vozlišče, gre v prvo vozlišče iz zadnjega vozlišče samo en korak.

Slabosti:

  • Obračanje krožno povezanega seznama je okorno.
  • Ko so vozlišča povezana v krog, ni ustrezne oznake za začetek ali konec seznama. Zato je težko najti konec seznama ali kontrolnika zanke. Če ne bo poskrbljeno, bo izvedba morda končala v neskončni zanki.
  • V enem koraku se ne moremo vrniti na prejšnje vozlišče. Celoten seznam moramo prehoditi od prvega.

Uporabe krožno povezanega seznama

  • Realnočasovna uporaba krožno povezanega seznama je lahko operacijski sistem z več programi, v katerem načrtuje več programov. Vsak program dobi namenski časovni žig za izvedbo, po katerem se viri posredujejo drugemu programu. To se nadaljuje neprekinjeno v ciklu. To predstavitev je mogoče učinkovito doseči s krožno povezanim seznamom.
  • Igre, ki se igrajo z več igralci, so lahko predstavljene tudi s krožno povezanim seznamom, v katerem je vsak igralec vozlišče, ki ima priložnost igrati.
  • Krožno povezan seznam lahko uporabimo za predstavitev krožne čakalne vrste. S tem lahko odstranimo kazalca spredaj in zadaj, ki se uporablja za čakalno vrsto. Namesto tega lahko uporabimo le en kazalec.

Zaključek

Krožno povezan seznam je zbirka vozlišč, v katerih so vozlišča med seboj povezana, da tvorijo krog. To pomeni, da je namesto nastavitve naslednjega kazalca zadnjega vozlišča na nič, povezan s prvim vozliščem.

Krožno povezan seznam je koristen pri predstavljanju struktur ali dejavnosti, ki jih je treba znova in znova ponoviti po določenem časovnem intervalu, kot so programi v okolju z več programi. Koristna je tudi za oblikovanje krožne čakalne vrste.

Krožno povezani seznami podpirajo različne operacije, kot so vstavljanje, brisanje in prečkanje. Tako smo v tej vadnici podrobno videli postopke.

V naslednji temi o podatkovnih strukturah bomo spoznali strukturo podatkovnih skladov.

=> Tukaj si oglejte A-Z o vajah za usposabljanje za C ++.

Priporočeno branje

^