Κυκλική συνδεδεμένη λίστα: Πλεονεκτήματα με παράδειγμα προγράμματος Γ

Πίνακας περιεχομένων:

Anonim

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

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

Ακολουθεί μια απεικόνιση μιας κυκλικής συνδεδεμένης λίστας με 3 κόμβους.

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

Σημείωση: Η πιο απλή κυκλική συνδεδεμένη λίστα, είναι ένας κόμβος που εντοπίζεται μόνο στον εαυτό του όπως φαίνεται

Σε αυτόν τον οδηγό κυκλικής συνδεδεμένης λίστας, θα μάθετε:

  • Τι είναι μια κυκλική συνδεδεμένη λίστα;
  • Βασικές λειτουργίες
  • Λειτουργία εισαγωγής
  • Λειτουργία διαγραφής
  • Διασταύρωση μιας κυκλικής συνδεδεμένης λίστας
  • Πλεονεκτήματα της κυκλικής συνδεδεμένης λίστας
  • Λίστα μεμονωμένη σύνδεση ως κυκλική συνδεδεμένη λίστα
  • Εφαρμογές της κυκλικής συνδεδεμένης λίστας

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

Οι βασικές λειτουργίες σε μια κυκλική συνδεδεμένη λίστα είναι:

  1. Εισαγωγή
  2. Διαγραφή και
  3. Διασχίζοντας
  • Η εισαγωγή είναι η διαδικασία τοποθέτησης ενός κόμβου σε καθορισμένη θέση στην κυκλική συνδεδεμένη λίστα.
  • Η διαγραφή είναι η διαδικασία κατάργησης ενός υπάρχοντος κόμβου από τη συνδεδεμένη λίστα. Ο κόμβος μπορεί να αναγνωριστεί από την εμφάνιση της τιμής του ή από τη θέση του.
  • Η διέλευση μιας κυκλικής συνδεδεμένης λίστας είναι η διαδικασία εμφάνισης ολόκληρου του περιεχομένου της συνδεδεμένης λίστας και της ανίχνευσης του κόμβου προέλευσης.

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

Λειτουργία εισαγωγής

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

Στη συνέχεια, υπάρχουν δύο δυνατότητες:

  • Εισαγωγή στην τρέχουσα θέση της κυκλικής συνδεδεμένης λίστας. Αυτό αντιστοιχεί στην εισαγωγή στην αρχή του τέλους μιας κανονικής ενότητας μεμονωμένων συνδέσμων. Σε μια κυκλική συνδεδεμένη λίστα, η αρχή και το τέλος είναι τα ίδια.
  • Εισαγωγή μετά από ευρετήριο κόμβου. Ο κόμβος πρέπει να αναγνωρίζεται από έναν αριθμό ευρετηρίου που αντιστοιχεί στην τιμή του στοιχείου.

Για εισαγωγή στην αρχή / τέλος της κυκλικής συνδεδεμένης λίστας, δηλαδή στη θέση όπου προστέθηκε ο πρώτος κόμβος,

  • Θα πρέπει να διακόψετε τον υπάρχοντα αυτοσύνδεση με τον υπάρχοντα κόμβο
  • Ο επόμενος δείκτης του νέου κόμβου θα συνδεθεί με τον υπάρχοντα κόμβο.
  • Ο επόμενος δείκτης του τελευταίου κόμβου θα δείχνει στον κόμβο που έχει εισαχθεί.

ΣΗΜΕΙΩΣΗ: Ο δείκτης που είναι το κύριο διακριτικό ή η αρχή / το τέλος του κύκλου μπορεί να αλλάξει. Θα συνεχίσει να επιστρέφει στον ίδιο κόμβο σε μια διασταύρωση, που συζητήθηκε μπροστά.

Τα βήματα στο (a) i-iii φαίνονται παρακάτω:

(Υφιστάμενος κόμβος)

ΒΗΜΑ 1) Σπάστε τον υπάρχοντα σύνδεσμο

ΒΗΜΑ 2) Δημιουργία συνδέσμου προς τα εμπρός (από νέο κόμβο σε υπάρχοντα κόμβο)

ΒΗΜΑ 3) Δημιουργήστε έναν σύνδεσμο βρόχου στον πρώτο κόμβο

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

Για παράδειγμα, ας εισαγάγουμε το "VALUE2" μετά τον κόμβο με το "VALUE0". Ας υποθέσουμε ότι το σημείο εκκίνησης είναι ο κόμβος με "VALUE0".

  • Θα πρέπει να σπάσετε τη γραμμή μεταξύ του πρώτου και του δεύτερου κόμβου και να τοποθετήσετε τον κόμβο με το "VALUE2" στο μεταξύ.
  • Ο επόμενος δείκτης του πρώτου κόμβου πρέπει να συνδέεται με αυτόν τον κόμβο και ο επόμενος δείκτης αυτού του κόμβου πρέπει να συνδέεται με τον προηγούμενο δεύτερο κόμβο.
  • Το υπόλοιπο της ρύθμισης παραμένει αμετάβλητο. Όλοι οι κόμβοι είναι ανιχνεύσιμοι από τον εαυτό τους.

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

Αυτό φαίνεται παρακάτω:

(Ας πούμε ότι υπάρχουν μόνο δύο κόμβοι. Αυτή είναι μια ασήμαντη περίπτωση)

ΒΗΜΑ 1) Αφαιρέστε τον εσωτερικό σύνδεσμο μεταξύ των συνδεδεμένων κόμβων

ΒΗΜΑ 2) Συνδέστε τον αριστερό κόμβο στον νέο κόμβο

ΒΗΜΑ 3) Συνδέστε τον νέο κόμβο στον κόμβο δεξιά πλευρά.

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

Ας υποθέσουμε μια κυκλική συνδεδεμένη λίστα 3 κόμβων. Οι περιπτώσεις διαγραφής δίνονται παρακάτω:

  • Διαγραφή του τρέχοντος στοιχείου
  • Διαγραφή μετά από ένα στοιχείο.

Διαγραφή στην αρχή / τέλος:

  1. Περάστε στον πρώτο κόμβο από τον τελευταίο κόμβο.
  2. Για διαγραφή από το τέλος, θα πρέπει να υπάρχει μόνο ένα βήμα διέλευσης, από τον τελευταίο κόμβο έως τον πρώτο κόμβο.
  3. Διαγράψτε τη σύνδεση μεταξύ του τελευταίου κόμβου και του επόμενου κόμβου.
  4. Συνδέστε τον τελευταίο κόμβο με το επόμενο στοιχείο του πρώτου κόμβου.
  5. Απελευθερώστε τον πρώτο κόμβο.

(Υφιστάμενη ρύθμιση)

ΒΗΜΑ 1 ) Αφαιρέστε τον κυκλικό σύνδεσμο

ΒΗΜΑΤΑ 2) Αφαιρέστε το σύνδεσμο μεταξύ του πρώτου και του επόμενου, συνδέστε τον τελευταίο κόμβο, με τον κόμβο μετά τον πρώτο

ΒΗΜΑ 3) Ελευθερώστε / αφαιρέστε τον πρώτο κόμβο

Διαγραφή μετά από έναν κόμβο

  1. Διασχίστε μέχρι τον επόμενο κόμβο είναι ο κόμβος που θα διαγραφεί.
  2. Περάστε στον επόμενο κόμβο, τοποθετώντας ένα δείκτη στον προηγούμενο κόμβο.
  3. Συνδέστε τον προηγούμενο κόμβο στον κόμβο μετά τον παρόντα κόμβο, χρησιμοποιώντας τον επόμενο δείκτη.
  4. Απελευθερώστε τον τρέχοντα (αποσυνδεδεμένο) κόμβο.

ΒΗΜΑ 1) Ας πούμε ότι πρέπει να διαγράψουμε έναν κόμβο με το "VALUE1".

ΒΗΜΑ 2) Καταργήστε τη σύνδεση μεταξύ του προηγούμενου κόμβου και του τρέχοντος κόμβου. Συνδέστε τον προηγούμενο κόμβο του με τον επόμενο κόμβο που δείχνει ο τρέχων κόμβος (με VALUE1).

ΒΗΜΑ 3) Δωρεάν ή απενεργοποιήστε τον τρέχοντα κόμβο.

Διασταύρωση μιας κυκλικής συνδεδεμένης λίστας

Για να διασχίσετε μια κυκλική συνδεδεμένη λίστα, ξεκινώντας από έναν τελευταίο δείκτη, ελέγξτε αν ο ίδιος ο τελευταίος δείκτης είναι NULL. Εάν αυτή η συνθήκη είναι ψευδής, ελέγξτε αν υπάρχει μόνο ένα στοιχείο. Διαφορετικά, διασχίστε έναν προσωρινό δείκτη μέχρι να φτάσετε ξανά στον τελευταίο δείκτη, ή όσες φορές χρειάζεται, όπως φαίνεται στο GIF παρακάτω.

Πλεονεκτήματα της κυκλικής συνδεδεμένης λίστας

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

  1. Δεν απαιτείται απαίτηση για εκχώρηση NULL στον κώδικα. Η κυκλική λίστα δεν δείχνει ποτέ έναν δείκτη NULL, εκτός εάν έχει αφαιρεθεί πλήρως.
  2. Οι κυκλικές συνδεδεμένες λίστες είναι επωφελείς για τελικές λειτουργίες από την αρχή και το τέλος συμπίπτουν. Αλγόριθμοι όπως ο προγραμματισμός Round Robin μπορούν να εξαλείψουν τακτοποιημένες διεργασίες που βρίσκονται σε ουρά με κυκλικό τρόπο χωρίς να συναντώνται δείκτες αναφοράς ή NULL.
  3. Η κυκλική συνδεδεμένη λίστα εκτελεί επίσης όλες τις κανονικές λειτουργίες μιας μεμονωμένης συνδεδεμένης λίστας. Στην πραγματικότητα, οι κυκλικές διπλά συνδεδεμένες λίστες που συζητούνται παρακάτω μπορούν ακόμη και να εξαλείψουν την ανάγκη για ένα πλήρες μήκος για να εντοπίσει ένα στοιχείο. Αυτό το στοιχείο θα ήταν το πολύ ακριβώς αντίθετο από την αρχή, συμπληρώνοντας μόλις τη μισή συνδεδεμένη λίστα.

Singly Linked List ως κυκλική συνδεδεμένη λίστα

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

#include#includestruct node{int item;struct node *next;};struct node* addToEmpty(struct node*,int);struct node *insertCurrent(struct node *, int);struct node *insertAfter(struct node *, int, int);struct node *removeAfter(struct node *, int);struct node *removeCurrent(struct node *);void peek(struct node *);int main(){…

Επεξήγηση κωδικού:

  1. Οι δύο πρώτες γραμμές κώδικα είναι τα απαραίτητα αρχεία κεφαλίδας.
  2. Η επόμενη ενότητα περιγράφει τη δομή κάθε κόμβου αυτοαναφοράς. Περιέχει μια τιμή και δείκτη του ίδιου τύπου με τη δομή.
  3. Κάθε δομή συνδέεται επανειλημμένα με δομή αντικειμένων του ίδιου τύπου.
  4. Υπάρχουν διαφορετικά πρωτότυπα λειτουργιών για:
    1. Προσθήκη στοιχείου σε μια κενή συνδεδεμένη λίστα
    2. Εισαγωγή στην τρέχουσα επισημασμένη θέση μιας κυκλικής συνδεδεμένης λίστας.
    3. Εισαγωγή μετά από μια συγκεκριμένη τιμή ευρετηρίου στη συνδεδεμένη λίστα.
    4. Κατάργηση / Διαγραφή μετά από μια συγκεκριμένη τιμή ευρετηρίου στη συνδεδεμένη λίστα.
    5. Κατάργηση στην τρέχουσα αιχμηρή θέση μιας κυκλικής συνδεδεμένης λίστας
  5. Η τελευταία συνάρτηση εκτυπώνει κάθε στοιχείο μέσω κυκλικής διέλευσης σε οποιαδήποτε κατάσταση της συνδεδεμένης λίστας.
int main(){struct node *last = NULL;last = insertCurrent(last,4);last = removeAfter(last, 4);peek(last);return 0;}struct node* addToEmpty(struct node*last, int data){struct node *temp = (struct node *)malloc(sizeof( struct node));temp->item = data;last = temp;last->next = last;return last;}struct node *insertCurrent(struct node *last, int data)

Επεξήγηση κωδικού:

  1. Για τον κώδικα addEmpty, εκχωρήστε έναν κενό κόμβο χρησιμοποιώντας τη συνάρτηση malloc.
  2. Για αυτόν τον κόμβο, τοποθετήστε τα δεδομένα στη μεταβλητή temp.
  3. Εκχωρήστε και συνδέστε τη μόνη μεταβλητή με τη μεταβλητή temp
  4. Επιστρέψτε το τελευταίο στοιχείο στο κύριο () / περιβάλλον εφαρμογής.
struct node *insertCurrent(struct node *last, int data){if(last == NULL){return addToEmpty(last, data);}struct node *temp = (struct node *)malloc(sizeof( struct node));temp -> item = data;temp->next = last->next;last->next = temp;return last;}struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;…

Επεξήγηση του κωδικού

  1. Εάν δεν υπάρχει στοιχείο για εισαγωγή, τότε πρέπει να βεβαιωθείτε ότι έχετε προσθέσει σε μια κενή λίστα και το στοιχείο ελέγχου επιστροφής.
  2. Δημιουργήστε ένα προσωρινό στοιχείο για τοποθέτηση μετά το τρέχον στοιχείο.
  3. Συνδέστε τους δείκτες όπως φαίνεται.
  4. Επιστρέψτε τον τελευταίο δείκτη όπως στην προηγούμενη συνάρτηση.
… struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;if (last == NULL){return addToEmpty(last, item);}do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found. Please try again");…

Επεξήγηση κωδικού:

  1. Εάν δεν υπάρχει στοιχείο στη λίστα, αγνοήστε τα δεδομένα, προσθέστε το τρέχον στοιχείο ως το τελευταίο στοιχείο στη λίστα και ελέγξτε την επιστροφή
  2. Για κάθε επανάληψη του βρόχου do-while, βεβαιωθείτε ότι υπάρχει ένας προηγούμενος δείκτης που κρατά το τελευταίο αποτέλεσμα.
  3. Μόνο τότε μπορεί να συμβεί η επόμενη διασταύρωση.
  4. Εάν τα δεδομένα βρεθούν, ή η θερμοκρασία φτάσει στον τελευταίο δείκτη, το do-while τερματίζεται. Η επόμενη ενότητα του κώδικα αποφασίζει τι πρέπει να γίνει με το αντικείμενο.
… if(temp->item != data){printf("Element not found. Please try again");return last;}else{newnode = (struct node *)malloc(sizeof(struct node));newnode->item = item;prev->next = newnode;newnode->next = temp;}return last;}struct node *removeCurrent(struct node *last)…

Επεξήγηση κωδικού:

  1. Εάν ολόκληρη η λίστα έχει διασταυρωθεί, αλλά το στοιχείο δεν βρέθηκε, εμφανίστε ένα μήνυμα "item not found" και, στη συνέχεια, επιστρέψτε τον έλεγχο στον καλούντα.
  2. Εάν υπάρχει ένας κόμβος ή / και ο κόμβος δεν είναι ακόμη ο τελευταίος κόμβος, τότε δημιουργήστε έναν νέο κόμβο.
  3. Συνδέστε τον προηγούμενο κόμβο με τον νέο κόμβο. Συνδέστε τον τρέχοντα κόμβο με temp (η μεταβλητή μετακίνησης).
  4. Αυτό εξασφαλίζει ότι το στοιχείο τοποθετείται μετά από έναν συγκεκριμένο κόμβο στην κυκλική συνδεδεμένη λίστα. Επιστροφή στον καλούντα.
struct node *removeCurrent(struct node *last){if(last == NULL){printf("Element Not Found");return NULL;}struct node *temp = last->next;last->next = temp->next;free(temp);return last;}struct node *removeAfter(struct node *last, int data)

Επεξήγηση του κωδικού

  1. Για να καταργήσετε μόνο τον τελευταίο (τρέχοντα) κόμβο, ελέγξτε αν αυτή η λίστα είναι κενή. Εάν είναι, τότε κανένα στοιχείο δεν μπορεί να αφαιρεθεί.
  2. Η μεταβλητή temp διασχίζει έναν σύνδεσμο προς τα εμπρός.
  3. Συνδέστε τον τελευταίο δείκτη με τον δείκτη μετά τον πρώτο.
  4. Απελευθερώστε το δείκτη temp. Απενεργοποιεί τον μη συνδεδεμένο τελευταίο δείκτη.
struct node *removeAfter(struct node *last,int data){struct node *temp = NULL,*prev = NULL;if (last == NULL){printf("Linked list empty. Cannot remove any element\n");return NULL;}temp = last->next;prev = temp;do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found");…

Επεξήγηση του κωδικού

  1. Όπως και με την προηγούμενη λειτουργία αφαίρεσης, ελέγξτε αν δεν υπάρχει στοιχείο. Εάν αυτό ισχύει, τότε κανένα στοιχείο δεν μπορεί να αφαιρεθεί.
  2. Οι δείκτες έχουν εκχωρηθεί συγκεκριμένες θέσεις για να εντοπίσουν το στοιχείο που θα διαγραφεί.
  3. Οι δείκτες είναι προχωρημένοι, ο ένας πίσω από τον άλλο. (prev πίσω temp)
  4. Η διαδικασία συνεχίζεται έως ότου βρεθεί ένα στοιχείο ή το επόμενο στοιχείο επανατοποθετηθεί στον τελευταίο δείκτη.
if(temp->item != data){printf("Element not found");return last;}else{prev->next = temp->next;free(temp);}return last;}void peek(struct node * last){struct node *temp = last;if (last == NULL){return;

Επεξήγηση του προγράμματος

  1. Εάν το στοιχείο βρέθηκε μετά από διέλευση ολόκληρης της συνδεδεμένης λίστας, εμφανίζεται ένα μήνυμα σφάλματος που λέει ότι το στοιχείο δεν βρέθηκε.
  2. Διαφορετικά, το στοιχείο αποσυνδέεται και απελευθερώνεται στα βήματα 3 και 4.
  3. Ο προηγούμενος δείκτης συνδέεται με τη διεύθυνση που επισημαίνεται ως "επόμενη" από το στοιχείο που θα διαγραφεί (temp).
  4. Επομένως, ο δείκτης θερμοκρασίας απενεργοποιείται και απελευθερώνεται.
… void peek(struct node * last){struct node *temp = last;if (last == NULL){return;}if(last -> next == last){printf("%d-", temp->item);}while (temp != last){printf("%d-", temp->item);temp = temp->next;}}

Επεξήγηση του κωδικού

  1. Το peek ή το traversal δεν είναι εφικτό εάν δεν χρειάζεται. Ο χρήστης πρέπει να εκχωρήσει ή να εισαγάγει έναν κόμβο.
  2. Εάν υπάρχει μόνο ένας κόμβος, δεν χρειάζεται να διασχίσετε, το περιεχόμενο του κόμβου μπορεί να εκτυπωθεί και ο βρόχος while δεν εκτελείται.
  3. Εάν υπάρχουν περισσότεροι από ένας κόμβοι, τότε η θερμοκρασία εκτυπώνει όλο το στοιχείο μέχρι το τελευταίο στοιχείο.
  4. Μόλις επιτευχθεί το τελευταίο στοιχείο, ο βρόχος τερματίζεται και η συνάρτηση επιστρέφει κλήση στην κύρια λειτουργία.

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

  • Εφαρμογή προγραμματισμού round-robin σε διαδικασίες συστήματος και κυκλικού προγραμματισμού σε γραφικά υψηλής ταχύτητας.
  • Προγραμματισμός κουδουνισμάτων σε δίκτυα υπολογιστών.
  • Χρησιμοποιείται σε μονάδες προβολής όπως πίνακες καταστημάτων που απαιτούν συνεχή διασταύρωση δεδομένων.