Μενού

Δομή δεδομένων κυκλικής συνδεδεμένης λίστας σε C ++ με απεικόνιση

  • Κύριος
  • Αλλα
  • Δομή δεδομένων κυκλικής συνδεδεμένης λίστας σε C ++ με απεικόνιση

circular linked list data structure c with illustration

Δοκιμάστε Το Όργανο Μας Για Την Εξάλειψη Των Προβλημάτων

Μια πλήρης επισκόπηση της κυκλικής συνδεδεμένης λίστας.

Μια κυκλική συνδεδεμένη λίστα είναι μια παραλλαγή της συνδεδεμένης λίστας. Είναι μια συνδεδεμένη λίστα των οποίων οι κόμβοι συνδέονται με τέτοιο τρόπο ώστε να σχηματίζει κύκλο.

Στην κυκλική συνδεδεμένη λίστα, ο επόμενος δείκτης του τελευταίου κόμβου δεν έχει οριστεί σε μηδέν, αλλά περιέχει τη διεύθυνση του πρώτου κόμβου σχηματίζοντας έτσι έναν κύκλο.

=> Επισκεφθείτε εδώ για να μάθετε C ++ από το μηδέν.

Κυκλική συνδεδεμένη λίστα

Τι θα μάθετε:

Κυκλική συνδεδεμένη λίστα σε C ++

Η διάταξη που φαίνεται παρακάτω είναι για μια λίστα που συνδέεται μεμονωμένα.

μία λίστα

Μια κυκλική συνδεδεμένη λίστα μπορεί να είναι μια μεμονωμένη λίστα ή μια διπλά συνδεδεμένη λίστα. Σε μια διπλά κυκλική συνδεδεμένη λίστα, ο προηγούμενος δείκτης του πρώτου κόμβου συνδέεται με τον τελευταίο κόμβο ενώ ο επόμενος δείκτης του τελευταίου κόμβου συνδέεται με τον πρώτο κόμβο.

Η αναπαράστασή του φαίνεται παρακάτω.

διπλή κυκλική συνδεδεμένη λίστα

Δήλωση

Μπορούμε να δηλώσουμε έναν κόμβο σε μια κυκλική συνδεδεμένη λίστα όπως οποιονδήποτε άλλο κόμβο όπως φαίνεται παρακάτω:

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

Προκειμένου να εφαρμοστεί η κυκλική συνδεδεμένη λίστα, διατηρούμε έναν εξωτερικό δείκτη «τελευταίο» που δείχνει τον τελευταίο κόμβο της κυκλικής συνδεδεμένης λίστας. Ως εκ τούτου, το τελευταίο-> επόμενο θα δείχνει τον πρώτο κόμβο της συνδεδεμένης λίστας.

Με αυτόν τον τρόπο διασφαλίζουμε ότι όταν εισάγουμε έναν νέο κόμβο στην αρχή ή στο τέλος της λίστας, δεν χρειάζεται να διασχίσουμε ολόκληρη τη λίστα. Αυτό συμβαίνει επειδή το τελευταίο σημείο στον τελευταίο κόμβο ενώ το τελευταίο-> επόμενο σημείο στον πρώτο κόμβο.

Αυτό δεν θα ήταν δυνατό αν είχαμε δείξει τον εξωτερικό δείκτη στον πρώτο κόμβο.

Βασικές λειτουργίες

Η κυκλική συνδεδεμένη λίστα υποστηρίζει εισαγωγή, διαγραφή και διέλευση της λίστας. Θα συζητήσουμε λεπτομερώς κάθε μία από τις λειτουργίες τώρα.

Εισαγωγή

Μπορούμε να εισαγάγουμε έναν κόμβο σε μια κυκλική συνδεδεμένη λίστα είτε ως έναν πρώτο κόμβο (κενή λίστα), στην αρχή, στο τέλος ή μεταξύ των άλλων κόμβων. Ας δούμε καθεμία από αυτές τις ενέργειες εισαγωγής χρησιμοποιώντας μια εικονική αναπαράσταση παρακάτω.

# 1) Εισαγωγή σε μια κενή λίστα

Εισαγωγή σε μια κενή λίστα

Όταν δεν υπάρχουν κόμβοι στην κυκλική λίστα και η λίστα είναι κενή, ο τελευταίος δείκτης είναι null, τότε εισάγουμε έναν νέο κόμβο N δείχνοντας τον τελευταίο δείκτη στον κόμβο N όπως φαίνεται παραπάνω. Ο επόμενος δείκτης του Ν θα δείξει τον ίδιο τον κόμβο Ν καθώς υπάρχει μόνο ένας κόμβος. Έτσι ο Ν γίνεται ο πρώτος και τελευταίος κόμβος στη λίστα.

# 2) Εισαγωγή στην αρχή της λίστας

Εισαγωγή στην αρχή της λίστας

Όπως φαίνεται στην παραπάνω αναπαράσταση, όταν προσθέτουμε έναν κόμβο στην αρχή της λίστας, ο επόμενος δείκτης του τελευταίου κόμβου δείχνει τον νέο κόμβο Ν, καθιστώντας τον έτσι έναν πρώτο κόμβο.

N-> next = τελευταίο-> επόμενο

Τελευταίο-> επόμενο = Ν

# 3) Εισαγωγή στο τέλος της λίστας

ο τελευταίος κόμβος δείχνει τον νέο κόμβο

Για να εισαγάγετε έναν νέο κόμβο στο τέλος της λίστας, ακολουθούμε τα εξής βήματα:

γυαλιά εικονικής πραγματικότητας για xbox 360

N-> next = τελευταίο -> επόμενο
τελευταία -> επόμενη = Ν
τελευταία = Ν

# 4) Εισαγωγή μεταξύ της λίστας

Εισαγωγή μεταξύ της λίστας

Ας υποθέσουμε ότι πρέπει να εισαγάγουμε έναν νέο κόμβο N μεταξύ N3 και N4, πρέπει πρώτα να διασχίσουμε τη λίστα και να εντοπίσουμε τον κόμβο μετά τον οποίο θα εισαχθεί ο νέος κόμβος, στην περίπτωση αυτή, ο N3.

Αφού εντοπιστεί ο κόμβος, εκτελούμε τα ακόλουθα βήματα.

N -> next = N3 -> επόμενο;
N3 -> επόμενο = Ν

Αυτό εισάγει έναν νέο κόμβο N μετά το N3.

Διαγραφή

Η λειτουργία διαγραφής της κυκλικής συνδεδεμένης λίστας περιλαμβάνει τον εντοπισμό του κόμβου που πρόκειται να διαγραφεί και στη συνέχεια απελευθέρωση της μνήμης του.

Γι 'αυτό διατηρούμε δύο πρόσθετα σημεία δείκτη και prev και μετά διασχίζουμε τη λίστα για να εντοπίσουμε τον κόμβο. Ο δεδομένος κόμβος που θα διαγραφεί μπορεί να είναι ο πρώτος κόμβος, ο τελευταίος κόμβος ή ο ενδιάμεσος κόμβος. Ανάλογα με την τοποθεσία ορίζουμε τους δείκτες νομισμάτων και prev και μετά διαγράφουμε τον κόμβο νομισμάτων.

Μια εικονική αναπαράσταση της λειτουργίας διαγραφής φαίνεται παρακάτω.

λειτουργία διαγραφής

Διασχίζοντας

Το Traversal είναι μια τεχνική επίσκεψης σε κάθε κόμβο. Σε γραμμικές συνδεδεμένες λίστες όπως λίστες μεμονωμένες συνδέσεις και λίστες διπλά συνδεδεμένες, η διέλευση είναι εύκολη καθώς επισκέπτουμε κάθε κόμβο και σταματάμε όταν συναντάμε NULL.

Ωστόσο, αυτό δεν είναι δυνατό σε μια κυκλική συνδεδεμένη λίστα. Σε μια κυκλική συνδεδεμένη λίστα, ξεκινάμε από τον επόμενο του τελευταίου κόμβου που είναι ο πρώτος κόμβος και διασχίζουμε κάθε κόμβο. Σταματάμε όταν φτάσουμε και πάλι στον πρώτο κόμβο.

Τώρα παρουσιάζουμε μια εφαρμογή των λειτουργιών κυκλικής συνδεδεμένης λίστας χρησιμοποιώντας C ++ και Java. Εφαρμόσαμε εδώ ενέργειες εισαγωγής, διαγραφής και διέλευσης. Για μια σαφή κατανόηση, έχουμε απεικονίσει την κυκλική συνδεδεμένη λίστα ως

Διασχίζοντας

Έτσι, στον τελευταίο κόμβο 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 για τις λειτουργίες λίστας κυκλικής σύνδεσης.

//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

Πλεονεκτήματα μειονεκτήματα

Ας συζητήσουμε μερικά πλεονεκτήματα και μειονεκτήματα της κυκλικής συνδεδεμένης λίστας.

Πλεονεκτήματα:

  • Μπορούμε να πάμε σε οποιονδήποτε κόμβο και να διασχίσουμε από οποιονδήποτε κόμβο. Πρέπει απλώς να σταματήσουμε όταν επισκέπτουμε ξανά τον ίδιο κόμβο.
  • Καθώς ο τελευταίος κόμβος δείχνει τον πρώτο κόμβο, η μετάβαση στον πρώτο κόμβο από τον τελευταίο κόμβο παίρνει μόνο ένα βήμα.

Μειονεκτήματα:

  • Η αντιστροφή μιας κυκλικής συνδεδεμένης λίστας είναι δυσκίνητη.
  • Καθώς οι κόμβοι συνδέονται για να σχηματίσουν κύκλο, δεν υπάρχει κατάλληλη σήμανση για αρχή ή τέλος για τη λίστα. Ως εκ τούτου, είναι δύσκολο να βρεθεί το τέλος της λίστας ή το στοιχείο ελέγχου βρόχου. Εάν δεν ληφθεί μέριμνα, μια εφαρμογή μπορεί να καταλήξει σε έναν άπειρο βρόχο.
  • Δεν μπορούμε να επιστρέψουμε στον προηγούμενο κόμβο σε ένα βήμα. Πρέπει να διασχίσουμε ολόκληρη τη λίστα από την πρώτη.

Εφαρμογές κυκλικής συνδεδεμένης λίστας

  • Η εφαρμογή σε πραγματικό χρόνο κυκλικής συνδεδεμένης λίστας μπορεί να είναι ένα λειτουργικό σύστημα πολλαπλού προγραμματισμού όπου προγραμματίζει πολλά προγράμματα. Σε κάθε πρόγραμμα παρέχεται μια ειδική χρονική σήμανση για εκτέλεση μετά την οποία οι πόροι μεταφέρονται σε άλλο πρόγραμμα. Αυτό συνεχίζεται συνεχώς σε έναν κύκλο. Αυτή η αναπαράσταση μπορεί να επιτευχθεί αποτελεσματικά χρησιμοποιώντας μια κυκλική συνδεδεμένη λίστα.
  • Τα παιχνίδια που παίζονται με πολλούς παίκτες μπορούν επίσης να αναπαρασταθούν χρησιμοποιώντας μια κυκλική συνδεδεμένη λίστα στην οποία κάθε παίκτης είναι ένας κόμβος που έχει την ευκαιρία να παίξει.
  • Μπορούμε να χρησιμοποιήσουμε μια κυκλική συνδεδεμένη λίστα για να αντιπροσωπεύσουμε μια κυκλική ουρά. Κάνοντας αυτό, μπορούμε να αφαιρέσουμε τους δύο δείκτες μπροστά και πίσω που χρησιμοποιούνται για την ουρά. Αντ 'αυτού, μπορούμε να χρησιμοποιήσουμε μόνο έναν δείκτη.

συμπέρασμα

Μια κυκλική συνδεδεμένη λίστα είναι μια συλλογή κόμβων στους οποίους οι κόμβοι συνδέονται μεταξύ τους για να σχηματίσουν έναν κύκλο. Αυτό σημαίνει ότι αντί να ορίσετε τον επόμενο δείκτη του τελευταίου κόμβου σε μηδέν, συνδέεται με τον πρώτο κόμβο.

Μια κυκλική συνδεδεμένη λίστα είναι χρήσιμη για την αναπαράσταση δομών ή δραστηριοτήτων που πρέπει να επαναλαμβάνονται ξανά και ξανά μετά από ένα συγκεκριμένο χρονικό διάστημα, όπως προγράμματα σε περιβάλλον πολλαπλού προγραμματισμού. Είναι επίσης ευεργετικό για το σχεδιασμό κυκλικής ουράς.

Οι κυκλικές συνδεδεμένες λίστες υποστηρίζουν διάφορες λειτουργίες όπως εισαγωγή, διαγραφή και διαβάσεις. Έτσι, έχουμε δει λεπτομερώς τις λειτουργίες σε αυτό το σεμινάριο.

Στο επόμενο θέμα μας σχετικά με τις δομές δεδομένων, θα μάθουμε για τη δομή δεδομένων στοίβας.

=> Δείτε εδώ για να δείτε τα εκπαιδευτικά σεμινάρια A-Z Of C ++.

Συνιστώμενη ανάγνωση

^