Meni

Kružno povezana struktura podataka popisa na C ++ s ilustracijom

  • Glavni
  • Ostalo
  • Kružno povezana struktura podataka popisa na C ++ s ilustracijom

circular linked list data structure c with illustration

Cjelovit pregled popisa s kružnim vezama.

Kružni povezani popis varijacija je povezanog popisa. To je povezani popis čiji su čvorovi povezani na takav način da tvori krug.

Na kružno povezanom popisu sljedeći pokazivač zadnjeg čvora nije postavljen na nulu, ali sadrži adresu prvog čvora čineći tako krug.

=> Posjetite ovdje da biste C ++ naučili od nule.

Kružno povezani popis

Što ćete naučiti:

Kružno povezani popis na C ++

Aranžman prikazan u nastavku odnosi se na pojedinačno povezani popis.

pojedinačno povezani popis

Kružno povezani popis može biti pojedinačno ili dvostruko povezan popis. Na dvostruko kružno povezanom popisu, prethodni pokazivač prvog čvora povezan je sa posljednjim čvorom, dok je sljedeći pokazivač zadnjeg čvora povezan s prvim čvorom.

Njegova reprezentacija prikazana je u nastavku.

dvostruko kružno povezani popis

Izjava

Čvor na kružno povezanom popisu možemo deklarirati kao bilo koji drugi čvor kako je prikazano dolje:

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

Da bismo implementirali kružno povezani popis, održavamo vanjski pokazivač 'zadnji' koji pokazuje na posljednji čvor na kružno povezanom popisu. Stoga će last-> next pokazati na prvi čvor na povezanom popisu.

Na taj način osiguravamo da kada umetnemo novi čvor na početak ili na kraj popisa, ne trebamo prelaziti cijeli popis. To je zato što posljednje upućuje na zadnji čvor, dok zadnje-> sljedeće ukazuje na prvi čvor.

To ne bi bilo moguće da smo vanjski pokazivač usmjerili na prvi čvor.

Osnovne operacije

Kružno povezani popis podržava umetanje, brisanje i zaokretanje popisa. Sada ćemo detaljno razgovarati o svakoj od operacija.

Umetanje

Čvor možemo umetnuti u kružno povezan popis ili kao prvi čvor (prazan popis), na početku, na kraju ili između ostalih čvorova. Pogledajmo svaku od ovih operacija umetanja pomoću slikovnog prikaza u nastavku.

# 1) Umetnite prazan popis

Umetnite u prazan popis

Kada na kružnom popisu nema čvorova, a popis je prazan, posljednji je pokazivač null, tada ubacujemo novi čvor N usmjeravanjem posljednjeg pokazivača na čvor N kao što je gore prikazano. Sljedeći pokazivač od N ukazat će na sam čvor N jer postoji samo jedan čvor. Tako N postaje prvi, kao i posljednji čvor na popisu.

# 2) Umetnite na početak popisa

Umetnite na početak popisa

Kao što je prikazano u gornjoj predstavi, kada čvor dodamo na početak popisa, sljedeći pokazivač zadnjeg čvora usmjerava na novi čvor N, čineći ga time prvim čvorom.

N-> next = last-> next

Posljednje-> sljedeće = N

# 3) Umetnite na kraj popisa

zadnji čvor pokazuje na novi čvor

Da bismo umetnuli novi čvor na kraj popisa, slijedimo ove korake:

N-> next = last -> next;
zadnji -> sljedeći = N
zadnji = N

# 4) Umetnite između popisa

Umetnite između popisa

Pretpostavimo da trebamo umetnuti novi čvor N između N3 i N4, prvo moramo preći popis i locirati čvor nakon kojeg treba umetnuti novi čvor, u ovom slučaju njegov N3.

Nakon što se čvor pronađe, izvodimo sljedeće korake.

N -> sljedeći = N3 -> sljedeći;
N3 -> sljedeći = N

Ovo umeće novi čvor N nakon N3.

Brisanje

Operacija brisanja kružno povezanog popisa uključuje pronalaženje čvora koji se želi izbrisati, a zatim oslobađanje njegove memorije.

Za to održavamo dva dodatna pokazivača curr i prev, a zatim prelazimo popis za lociranje čvora. Dani čvor koji se treba izbrisati može biti prvi čvor, posljednji čvor ili čvor između. Ovisno o mjestu postavljamo pokazivače curr i prev, a zatim brišemo curr čvor.

Slikovni prikaz postupka brisanja prikazan je u nastavku.

operacija brisanja

Preokret

Prelazak je tehnika posjećivanja svakog čvora. U linearno povezanim popisima poput pojedinačno povezanih i dvostruko povezanih popisa, prelazak je jednostavan jer posjetimo svaki čvor i zaustavimo se kada se naiđe na NULL.

Međutim, to nije moguće na kružno povezanom popisu. U kružno povezanom popisu započinjemo od sljedećeg posljednjeg čvora koji je prvi čvor i prelazimo svaki čvor. Zaustavljamo se kad ponovno dođemo do prvog čvora.

Sada predstavljamo implementaciju operacija kružnog povezanog popisa pomoću C ++ i Jave. Ovdje smo implementirali operacije umetanja, brisanja i prelaska. Radi jasnog razumijevanja, kružno povezani popis prikazali smo kao

Preokret

Tako na posljednji čvor 50, opet priključujemo čvor 10 koji je prvi čvor, označavajući ga time kružno povezanim popisom.

aplikacija za slobodno vrijeme za iphone i android
#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 '<

Izlaz:

Stvoreni kružno povezani popis je sljedeći:

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

Čvor s podacima 10 briše se s popisa

Kružno povezani popis nakon brisanja 10 je sljedeći:

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

Dalje, predstavljamo implementaciju Jave za operacije kružnog povezanog popisa.

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

Izlaz:

Stvorena je kružno povezana lista:

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

Nakon brisanja 40, kružni je popis:

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

Prednosti mane

Razmotrimo neke prednosti i nedostatke kružno povezanog popisa.

Prednosti:

  • Možemo ići do bilo kojeg čvora i preći s bilo kojeg čvora. Samo se trebamo zaustaviti kad ponovno posjetimo isti čvor.
  • Kako posljednji čvor pokazuje na prvi čvor, prelazak na prvi čvor sa zadnjeg čvora čini samo jedan korak.

Mane:

  • Obrtanje kružno povezanog popisa je glomazno.
  • Kako su čvorovi povezani u krug, za popis ne postoji odgovarajuće označavanje za početak ili kraj. Stoga je teško pronaći kraj popisa ili kontrolu petlje. Ako se ne pobrine, implementacija može završiti u beskonačnoj petlji.
  • Ne možemo se vratiti na prethodni čvor ni u jednom koraku. Moramo preći cijeli popis od početka.

Primjene kružno povezanih popisa

  • Primjena kružno povezanog popisa u stvarnom vremenu može biti operativni sustav s više programiranja u kojem planira više programa. Svaki program dobiva namjenski vremenski žig za izvršenje nakon čega se resursi prosljeđuju drugom programu. To se kontinuirano odvija u ciklusu. Ovaj se prikaz može učinkovito postići pomoću kružno povezanog popisa.
  • Igre koje se igraju s više igrača mogu se predstaviti i pomoću kružno povezanog popisa u kojem je svaki igrač čvor koji ima priliku igrati.
  • Kružno povezani popis možemo koristiti za predstavljanje kružnog reda. Na taj način možemo ukloniti dva pokazivača sprijeda i straga koji se koriste za red. Umjesto toga, možemo koristiti samo jedan pokazivač.

Zaključak

Kružno povezani popis zbirka je čvorova u kojima su čvorovi međusobno povezani kako bi stvorili krug. To znači da je umjesto da sljedeći pokazivač zadnjeg čvora postavi na nulu, on povezan s prvim čvorom.

Kružno povezani popis koristan je u predstavljanju struktura ili aktivnosti koje treba ponavljati iznova i iznova nakon određenog vremenskog intervala poput programa u okruženju s više programa. Također je korisno za dizajniranje kružnog reda.

Kružno povezani popisi podržavaju razne operacije poput umetanja, brisanja i prelaska. Stoga smo operacije detaljno vidjeli u ovom vodiču.

U sljedećoj temi o strukturama podataka naučit ćemo o strukturi složenih podataka.

=> Ovdje pogledajte kako biste ovdje vidjeli A-Z of C ++ Tutorials Training.

Preporučena literatura

^