Мени

Структура података кружно повезане листе на Ц ++ са илустрацијом

  • Главни
  • Остало
  • Структура података кружно повезане листе на Ц ++ са илустрацијом

circular linked list data structure c with illustration

Испробајте Наш Инструмент За Елиминисање Проблема

Комплетан преглед кружно повезане листе.

Кружна повезана листа је варијација повезане листе. То је повезана листа чији су чворови повезани на такав начин да чини круг.

У кружно повезаној листи, следећи показивач последњег чвора није постављен на нулу, али садржи адресу првог чвора чиме се формира круг.

=> Посетите овде да бисте научили Ц ++ из огреботина.

Кружно повезана листа

Шта ћете научити:

Кружно повезана листа на Ц ++

Аранжман приказан доле је за појединачно повезану листу.

појединачно повезана листа

Кружно повезана листа може бити појединачно повезана или двоструко повезана листа. У двоструко кружно повезаној листи, претходни показивач првог чвора повезан је са последњим чвором, док је следећи показивач последњег чвора повезан са првим чвором.

Његов приказ је приказан у наставку.

двоструко кружно повезана листа

Изјава

Чвор на кружно повезаној листи можемо прогласити било којим другим чвором као што је приказано доле:

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

Да бисмо применили кружно повезану листу, одржавамо спољни показивач „задњи“ који показује на последњи чвор на кружно повезаној листи. Отуда ће ласт-> нект усмерити на први чвор на повезаној листи.

На тај начин осигуравамо да када уметнемо нови чвор на почетак или на крај листе, не треба да прелазимо целу листу. То је зато што последње упућује на последњи чвор, док последње-> следеће указује на први чвор.

То не би било могуће да смо спољни показивач усмерили на први чвор.

Основне операције

Кружно повезана листа подржава уметање, брисање и обртање листе. Сада ћемо детаљно разговарати о свакој од операција.

Уметање

Чвор можемо уметнути у кружно повезану листу или као први чвор (празна листа), на почетку, на крају или између осталих чворова. Погледајмо сваку од ових операција уметања користећи сликовни приказ у наставку.

# 1) Уметните у празну листу

Уметните у празну листу

Када у кружној листи нема чворова, а листа је празна, последњи показивач је нула, тада убацујемо нови чвор Н усмеравајући последњи показивач на чвор Н као што је горе приказано. Следећи показивач од Н указаће на сам чвор Н јер постоји само један чвор. Тако Н постаје први, као и последњи чвор на листи.

# 2) Уметните на почетак листе

Уметните на почетак листе

Као што је приказано у горњој представи, када чвор додамо на почетак листе, следећи показивач последњег чвора указује на нови чвор Н, чинећи га тако првим чвором.

Н-> нект = ласт-> нект

Последње-> следеће = Н.

# 3) Уметните на крај листе

последњи чвор указује на нови чвор

Да бисмо уметнули нови чвор на крају листе, следимо ове кораке:

двоструко повезана листа ц ++ имплементација

Н-> нект = ласт -> нект;
последње -> следеће = Н.
последњи = Н.

# 4) Уметните између листе

Уметните између листе

Претпоставимо да треба да уметнемо нови чвор Н између Н3 и Н4, прво треба да пређемо листу и лоцирамо чвор након чега треба да се уметне нови чвор, у овом случају његов Н3.

Након што се чвор пронађе, изводимо следеће кораке.

Н -> следеће = Н3 -> следеће;
Н3 -> следећи = Н.

Ово умеће нови чвор Н после Н3.

Делетион

Операција брисања кружно повезане листе укључује проналажење чвора који треба избрисати и ослобађање његове меморије.

За ово одржавамо два додатна показивача цурр и прев, а затим прелазимо листу да бисмо лоцирали чвор. Дати чвор који треба избрисати може бити први чвор, последњи чвор или чвор између. У зависности од локације постављамо показиваче цурр и прев, а затим бришемо цурр чвор.

Сликовити приказ операције брисања приказан је у наставку.

операција брисања

Преокрет

Прелазак је техника посећивања сваког чвора. У линеарно повезаним листама попут појединачно повезаних и двоструко повезаних листа, прелазак је једноставан јер обилазимо сваки чвор и заустављамо се када се наиђе на НУЛЛ.

Међутим, то није могуће на кружно повезаној листи. У кружно повезаној листи почињемо од следећег последњег чвора који је први чвор и прелазимо сваки чвор. Заустављамо се када поново дођемо до првог чвора.

Сада представљамо имплементацију кружно повезаних операција листе користећи Ц ++ и Јаву. Овде смо применили операције уметања, брисања и преласка. Ради јасног разумевања, кружно повезану листу приказали смо као

Преокрет

Тако на последњи чвор 50 поново прикључујемо чвор 10 који је први чвор, означавајући га тиме као кружно повезану листу.

#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 '<

Излаз:

Створена кружно повезана листа је следећа:

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

Чвор са подацима 10 се брише са листе

Кружно повезана листа након брисања 10 је следећа:

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

Даље, представљамо Јава имплементацију за операције кружне повезане листе.

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

Излаз:

Створена кружно повезана листа је:

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

Након брисања 40, кружни списак је:

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

Предности Мане

Размотримо неке предности и недостатке кружно повезане листе.

Предности:

  • Можемо ићи до било ког чвора и прећи са било ког чвора. Само треба да се зауставимо када поново посетимо исти чвор.
  • Како последњи чвор показује на први чвор, прелазак на први чвор са последњег чвора чини само један корак.

Мане:

  • Обртање кружно повезане листе је незгодно.
  • Како су чворови повезани у круг, нема одговарајуће ознаке за почетак или крај листе. Стога је тешко пронаћи крај листе или контролу петље. Ако се не побрине, имплементација може завршити у бесконачној петљи.
  • Не можемо се вратити на претходни чвор ни у једном кораку. Морамо прећи целу листу од прве.

Примене кружно повезане листе

  • Примена кружно повезане листе у реалном времену може бити оперативни систем са више програма, у којем се планира више програма. Сваки програм добија наменску временску ознаку за извршење након чега се ресурси прослеђују другом програму. То се непрекидно одвија у циклусу. Овај приказ се може ефикасно постићи помоћу кружно повезане листе.
  • Игре које се играју са више играча могу се представити и помоћу кружно повезане листе у којој је сваки играч чвор који има прилику да игра.
  • Кружно повезану листу можемо користити за представљање кружног реда. На овај начин можемо уклонити два показивача предњи и задњи који се користе за ред. Уместо тога, можемо користити само један показивач.

Закључак

Кружно повезана листа је колекција чворова у којима су чворови повезани једни са другима како би се формирао круг. То значи да је уместо да следећи показивач последњег чвора постави на нулу, он је повезан са првим чвором.

Кружно повезана листа је корисна у представљању структура или активности које треба поновити изнова и изнова након одређеног временског интервала попут програма у окружењу са више програма. Такође је корисно за дизајнирање кружног реда.

Кружно повезане листе подржавају разне операције попут уметања, брисања и преласка. Стога смо операције детаљно видели у овом упутству.

У следећој теми о структурама података научићемо о структури података стека.

=> Погледајте овде да бисте видели А-З Ц ++ туторијала за обуку овде.

Препоручено читање

^