Menu

Struktura danych listy połączonej cyklicznie w C ++ z ilustracją

  • Główny
  • Inny
  • Struktura danych listy połączonej cyklicznie w C ++ z ilustracją

circular linked list data structure c with illustration

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Pełny przegląd listy połączonej cyklicznie.

Lista połączona cyklicznie jest odmianą listy połączonej. Jest to lista połączona, której węzły są połączone w taki sposób, że tworzy okrąg.

Na liście połączonej cyklicznie następny wskaźnik ostatniego węzła nie jest ustawiony na zero, ale zawiera adres pierwszego węzła, tworząc w ten sposób okrąg.

=> Odwiedź tutaj, aby nauczyć się C ++ od podstaw.

Lista połączona cyklicznie

Czego się nauczysz:

Lista połączona cyklicznie w C ++

Poniższy układ dotyczy listy połączonej pojedynczo.

lista pojedynczo połączona

Lista połączona cyklicznie może być listą połączoną pojedynczo lub listą połączoną podwójnie. Na podwójnie kołowej liście połączonej poprzedni wskaźnik pierwszego węzła jest połączony z ostatnim węzłem, podczas gdy następny wskaźnik ostatniego węzła jest połączony z pierwszym węzłem.

Jego reprezentację przedstawiono poniżej.

lista połączona podwójnie kołowo

Deklaracja

Możemy zadeklarować węzeł na cyklicznej liście połączonej jako każdy inny węzeł, jak pokazano poniżej:

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

Aby zaimplementować cykliczną listę połączoną, utrzymujemy zewnętrzny wskaźnik „ostatni”, który wskazuje na ostatni węzeł na cyklicznej liście połączonej. Stąd last-> next wskaże pierwszy węzeł na połączonej liście.

W ten sposób zapewniamy, że kiedy wstawimy nowy węzeł na początku lub na końcu listy, nie będziemy musieli przechodzić przez całą listę. Dzieje się tak, ponieważ ostatni wskazuje na ostatni węzeł, a ostatni-> następny wskazuje na pierwszy węzeł.

Nie byłoby to możliwe, gdybyśmy wskazali zewnętrzny wskaźnik na pierwszy węzeł.

Podstawowe operacje

Lista połączona cyklicznie obsługuje wstawianie, usuwanie i przeglądanie listy. Omówimy teraz szczegółowo każdą operację.

Wprowadzenie

Możemy wstawić węzeł na cyklicznej liście połączonej jako pierwszy węzeł (pusta lista), na początku, na końcu lub pomiędzy innymi węzłami. Przyjrzyjmy się każdej z tych operacji wstawiania, używając poniższej reprezentacji graficznej.

# 1) Wstaw na pustą listę

Wstaw na pustą listę

Gdy nie ma węzłów na liście cyklicznej, a lista jest pusta, ostatni wskaźnik jest pusty, a następnie wstawiamy nowy węzeł N, wskazując ostatni wskaźnik na węzeł N, jak pokazano powyżej. Następny wskaźnik N będzie wskazywał na sam węzeł N, ponieważ jest tylko jeden węzeł. W ten sposób N staje się pierwszym i ostatnim węzłem na liście.

# 2) Wstaw na początku listy

Wstaw na początku listy

Jak pokazano na powyższej ilustracji, kiedy dodajemy węzeł na początku listy, następny wskaźnik ostatniego węzła wskazuje na nowy węzeł N, czyniąc go tym samym pierwszym węzłem.

N-> next = last-> next

Last-> next = N

# 3) Wstaw na końcu listy

ostatni węzeł wskazuje na nowy węzeł

Aby wstawić nowy węzeł na końcu listy, wykonujemy następujące kroki:

przekazywanie tablic do metod w java

N-> next = last -> next;
ostatnia -> następna = N
ostatnia = N

# 4) Wstaw między listą

Wstaw między listą

Załóżmy, że musimy wstawić nowy węzeł N między N3 i N4, najpierw musimy przejść przez listę i zlokalizować węzeł, za którym ma zostać wstawiony nowy węzeł, w tym przypadku jego N3.

Po zlokalizowaniu węzła wykonujemy następujące kroki.

N -> next = N3 -> next;
N3 -> next = N

Spowoduje to wstawienie nowego węzła N po N3.

Usunięcie

Operacja usunięcia listy połączonej cyklicznie obejmuje zlokalizowanie węzła, który ma zostać usunięty, a następnie zwolnienie jego pamięci.

W tym celu utrzymujemy dwa dodatkowe wskaźniki curr i prev, a następnie przechodzimy przez listę, aby zlokalizować węzeł. Dany węzeł do usunięcia może być pierwszym węzłem, ostatnim węzłem lub węzłem pośrednim. W zależności od lokalizacji ustawiamy wskaźniki curr i prev, a następnie usuwamy węzeł curr.

Graficzne przedstawienie operacji usuwania jest pokazane poniżej.

operacja usunięcia

Traversal

Traversal to technika odwiedzania każdego węzła. W przypadku list połączonych liniowo, takich jak listy pojedynczo i podwójnie, przechodzenie jest łatwe, ponieważ odwiedzamy każdy węzeł i zatrzymujemy się po napotkaniu wartości NULL.

Nie jest to jednak możliwe w przypadku listy połączonej cyklicznie. W przypadku okrągłej listy połączonej zaczynamy od następnego z ostatniego węzła, który jest pierwszym węzłem, i przechodzimy przez każdy węzeł. Zatrzymujemy się, gdy ponownie osiągamy pierwszy węzeł.

Teraz przedstawiamy implementację cyklicznych operacji na listach połączonych przy użyciu C ++ i Javy. Zaimplementowaliśmy tutaj operacje wstawiania, usuwania i przechodzenia. Aby ułatwić zrozumienie, przedstawiliśmy listę połączoną cyklicznie jako

Traversal

Zatem do ostatniego węzła 50 ponownie dołączamy węzeł 10, który jest pierwszym węzłem, wskazując w ten sposób jako listę połączoną cyklicznie.

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

Wynik:

Utworzona cykliczna lista połączona jest następująca:

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

Węzeł z danymi 10 zostanie usunięty z listy

Lista z linkami cyklicznymi po usunięciu 10 jest następująca:

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

Następnie przedstawiamy implementację Java dla operacji na listach połączonych cyklicznie.

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

Wynik:

Utworzona cyklicznie połączona lista to:

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

Po usunięciu 40 lista cykliczna wygląda następująco:

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

Zalety wady

Omówmy niektóre zalety i wady listy połączonej w okólniku.

Zalety:

  • Możemy przejść do dowolnego węzła i przejść z dowolnego węzła. Musimy się tylko zatrzymać, gdy ponownie odwiedzimy ten sam węzeł.
  • Ponieważ ostatni węzeł wskazuje na pierwszy węzeł, przejście do pierwszego węzła z ostatniego węzła zajmuje tylko jeden krok.

Niedogodności:

  • Odwracanie listy połączonej cyklicznie jest uciążliwe.
  • Ponieważ węzły są połączone w okrąg, nie ma odpowiedniego oznaczenia początku ani końca listy. Dlatego trudno jest znaleźć koniec listy lub kontrolę pętli. W przeciwnym razie implementacja może zakończyć się nieskończoną pętlą.
  • Nie możemy wrócić do poprzedniego węzła w jednym kroku. Musimy przejść całą listę od początku.

Zastosowania listy połączonej cyklicznie

  • Stosowanie listy połączonej cyklicznie w czasie rzeczywistym może być systemem operacyjnym obsługującym wiele programów, w którym planuje się wiele programów. Każdy program otrzymuje dedykowany znacznik czasu do wykonania, po którym zasoby są przekazywane do innego programu. Dzieje się to w sposób ciągły w cyklu. Reprezentację tę można skutecznie uzyskać za pomocą okrężnej listy połączonej.
  • Gry, w które gra wielu graczy, można również przedstawić za pomocą okrągłej połączonej listy, na której każdy gracz jest węzłem, który ma szansę zagrać.
  • Możemy użyć cyklicznej listy połączonej do reprezentowania cyklicznej kolejki. W ten sposób możemy usunąć dwa przednie i tylne wskaźniki używane do kolejki. Zamiast tego możemy użyć tylko jednego wskaźnika.

Wniosek

Lista połączona cyklicznie to zbiór węzłów, w których węzły są połączone ze sobą, tworząc okrąg. Oznacza to, że zamiast ustawiać następny wskaźnik ostatniego węzła na wartość null, jest on połączony z pierwszym węzłem.

Lista połączona cyklicznie jest pomocna w reprezentowaniu struktur lub czynności, które muszą być powtarzane wielokrotnie po określonym przedziale czasu, jak programy w środowisku wieloprogramowym. Jest to również korzystne przy projektowaniu kolejek kołowych.

Listy połączone cyklicznie obsługują różne operacje, takie jak wstawianie, usuwanie i przechodzenie. Dlatego szczegółowo omówiliśmy operacje w tym samouczku.

W następnym temacie dotyczącym struktur danych dowiemy się o strukturze danych stosu.

=> Sprawdź tutaj, aby zobaczyć samouczki szkoleniowe od A do Z języka C ++ tutaj.

rekomendowane lektury

^