Ο τελικός κόμβος μιας συνδεδεμένης λίστας που έχει βρόχο θα αναφέρεται σε έναν άλλο κόμβο στην ίδια λίστα και όχι στον NULL. Εάν υπάρχει ένας κόμβος σε μια συνδεδεμένη λίστα στον οποίο μπορεί να προσπελαστεί επανειλημμένα ακολουθώντας τον επόμενο δείκτη, η λίστα λέγεται ότι έχουν κύκλο.
Συνήθως, ο τελευταίος κόμβος της Συνδεδεμένης Λίστας αναφέρεται σε μια αναφορά NULL για να υποδηλώσει το συμπέρασμα της λίστας. Ωστόσο, σε μια συνδεδεμένη λίστα με βρόχο, ο τελικός κόμβος της λίστας αναφέρεται σε έναν κόμβο έναρξης, έναν εσωτερικό κόμβο ή τον εαυτό του. Επομένως, σε τέτοιες περιπτώσεις, πρέπει να αναγνωρίσουμε και να τερματίσουμε τον βρόχο ορίζοντας την αναφορά του επόμενου κόμβου σε NULL. Το τμήμα ανίχνευσης του βρόχου σε μια συνδεδεμένη λίστα εξηγείται σε αυτό το άρθρο.
Στη C++, υπάρχουν πολλοί τρόποι για να βρείτε βρόχους σε μια συνδεδεμένη λίστα:
Προσέγγιση βάσει πίνακα κατακερματισμού : Αυτή η προσέγγιση αποθηκεύει τις διευθύνσεις των κόμβων που επισκεφτήκατε σε έναν πίνακα κατακερματισμού. Ένας βρόχος στη συνδεδεμένη λίστα υπάρχει εάν ένας κόμβος υπάρχει ήδη στον πίνακα κατακερματισμού όταν τον επισκεφτείτε ξανά.
Η προσέγγιση του κύκλου του Floyd : Ο αλγόριθμος «χελώνα και λαγός», κοινώς γνωστός ως αλγόριθμος εύρεσης κύκλου του Floyd: Αυτή η τεχνική χρησιμοποιεί δύο δείκτες, ο ένας κινείται πιο αργά από τον άλλο και ο άλλος κινείται πιο γρήγορα. Ο πιο γρήγορος δείκτης θα ξεπεράσει τελικά τον πιο αργό δείκτη εάν υπάρχει ένας βρόχος στη συνδεδεμένη λίστα, αποκαλύπτοντας την ύπαρξη του βρόχου.
Αναδρομική μέθοδος : Αυτή η μέθοδος περνά από τη συνδεδεμένη λίστα καλώντας τον εαυτό της ξανά και ξανά. Η συνδεδεμένη λίστα περιέχει έναν βρόχο εάν ο τρέχων κόμβος έχει προηγουμένως επισκεφτεί.
Προσέγγιση που βασίζεται σε στοίβα : Αυτή η προσέγγιση αποθηκεύει τις διευθύνσεις των κόμβων που έχετε επισκεφτεί σε μια στοίβα. Ένας βρόχος στη συνδεδεμένη λίστα υπάρχει εάν ένας κόμβος βρίσκεται ήδη εκεί στη στοίβα όταν τον επισκεφτείτε ξανά.
Ας εξηγήσουμε κάθε προσέγγιση λεπτομερώς για να κατανοήσουμε την έννοια.
Προσέγγιση 1: Προσέγγιση HashSet
Η χρήση κατακερματισμού είναι η πιο απλή μέθοδος. Εδώ, περνάμε τη λίστα μία προς μία, ενώ διατηρούμε έναν πίνακα κατακερματισμού με τις διευθύνσεις κόμβων. Ως εκ τούτου, υπάρχει ένας βρόχος εάν ποτέ τρέξουμε στην επόμενη διεύθυνση του τρέχοντος κόμβου που περιέχεται ήδη στον πίνακα κατακερματισμού. Διαφορετικά, δεν υπάρχει βρόχος στη Συνδεδεμένη Λίστα, εάν βρεθούμε σε NULL (δηλαδή, φτάσουμε στο τέλος της Συνδεδεμένης λίστας).
Θα είναι αρκετά εύκολο να εφαρμοστεί αυτή η στρατηγική.
Κατά τη διέλευση της συνδεδεμένης λίστας, θα χρησιμοποιήσουμε ένα unordered_hashmap και θα συνεχίσουμε να προσθέτουμε κόμβους σε αυτό.
Τώρα, μόλις συναντήσουμε έναν κόμβο που εμφανίζεται ήδη στον χάρτη, θα ξέρουμε ότι έχουμε φτάσει στην αρχή του βρόχου.
-
- Επιπλέον, κρατήσαμε δύο δείκτες σε κάθε βήμα, headNode δείχνοντας τον τρέχοντα κόμβο και lastNode δείχνει τον προηγούμενο κόμβο του τρέχοντος κόμβου, ενώ επαναλαμβάνει.
- Ως δικό μας headNode δείχνει τώρα στον κόμβο έναρξης του βρόχου και ως lastNode έδειχνε τον κόμβο στον οποίο έδειχνε η κεφαλή (δηλαδή, αναφέρεται στο lastNode του βρόχου), μας headNode αυτή τη στιγμή δείχνει προς τον κόμβο έναρξης του βρόχου.
- Ο βρόχος θα σπάσει με τη ρύθμιση l astNode->next == NULL .
Κάνοντας αυτό, ο τερματικός κόμβος βρόχου αντί να αναφέρεται στον αρχικό κόμβο του βρόχου, αρχίζει να δείχνει στο NULL.
Η μέση πολυπλοκότητα χρόνου και χώρου της μεθόδου κατακερματισμού είναι O(n). Ο αναγνώστης πρέπει πάντα να γνωρίζει ότι η εφαρμογή της ενσωματωμένης δομής δεδομένων κατακερματισμού στη γλώσσα προγραμματισμού θα καθορίσει τη συνολική χρονική πολυπλοκότητα σε περίπτωση σύγκρουσης στον κατακερματισμό.
Υλοποίηση προγράμματος C++ για την παραπάνω μέθοδο (HashSet):
#include
χρησιμοποιώντας namespace std?
struct Κόμβος {
int αξία?
struct Κόμβος * Επόμενο;
} ;
Κόμβος * newNode ( int αξία )
{
Κόμβος * tempNode = νέος κόμβος;
tempNode- > αξία = αξία;
tempNode- > επόμενο = NULL;
ΕΠΙΣΤΡΟΦΗ tempNode;
}
// Προσδιορίστε και εξαλείψτε τυχόν πιθανούς βρόχους
// σε μια συνδεδεμένη λίστα με αυτή τη λειτουργία.
void functionHashMap ( Κόμβος * headNode )
{
// Δημιουργήθηκε ένας unordered_map για την εφαρμογή του χάρτη Hash
unordered_map < Κόμβος * , ενθ > hash_map;
// δείκτη στο lastNode
Κόμβος * lastNode = NULL;
ενώ ( headNode ! = NULL ) {
// Εάν λείπει ένας κόμβος από τον χάρτη, προσθέστε τον.
αν ( hash_map.find ( headNode ) == hash_map.end ( ) ) {
hash_map [ headNode ] ++;
lastNode = headNode;
headNode = headNode- > Επόμενο;
}
// Εάν υπάρχει κύκλος, σειρά ο τελικός κόμβος είναι ο επόμενος δείκτης στο NULL.
άλλο {
lastNode->next = NULL;
Διακοπή;
}
}
}
// Εμφάνιση συνδεδεμένης λίστας
κενή οθόνη (Node* headNode)
{
ενώ (headNode != NULL) {
cout << headNode->value << ' ';
headNode = headNode->next;
}
cout << endl;
}
/* Κύρια λειτουργία*/
int main()
{
Node* headNode = newNode(48);
headNode->next = headNode;
headNode->next = newNode(18);
headNode->next->next = newNode(13);
headNode->next->next->next = newNode(2);
headNode->next->next->next->next = newNode(8);
/* Δημιουργία βρόχου στο linkedList */
headNode->next->next->next->next->next = headNode->next->next;
functionHashMap(headNode);
printf('Συνδεδεμένη λίστα χωρίς βρόχο \n');
εμφάνιση (headNode);
επιστροφή 0;
}
Παραγωγή:
Συνδεδεμένη λίστα χωρίς βρόχο
48 18 13 2 8
Η εξήγηση βήμα προς βήμα του κώδικα παρέχεται παρακάτω:
-
- Το αρχείο κεφαλίδας bits/stdc++.h>, το οποίο περιέχει όλες τις κοινές βιβλιοθήκες C++, περιλαμβάνεται στον κώδικα.
- Κατασκευάζεται μια δομή που ονομάζεται 'Node' και έχει δύο μέλη: μια αναφορά στον επόμενο κόμβο στη λίστα και έναν ακέραιο που ονομάζεται 'value'.
- Με μια ακέραια τιμή ως είσοδο και τον δείκτη 'επόμενο' ορισμένο σε NULL, η συνάρτηση 'newNode' δημιουργεί έναν νέο κόμβο με αυτήν την τιμή.
- Η λειτουργία ' functionHashMap' ορίζεται, το οποίο παίρνει ως είσοδο έναν δείκτη στον κεντρικό κόμβο της συνδεδεμένης λίστας.
- Μεσα στην ' functionHashMap ' συνάρτηση, δημιουργείται ένας unordered_map με το όνομα 'hash_map', ο οποίος χρησιμοποιείται για την υλοποίηση μιας δομής δεδομένων χάρτη κατακερματισμού.
- Ένας δείκτης στον τελευταίο κόμβο της λίστας αρχικοποιείται σε NULL.
- Ένας βρόχος while χρησιμοποιείται για τη διέλευση της συνδεδεμένης λίστας, η οποία ξεκινά από τον κύριο κόμβο και συνεχίζει έως ότου ο κόμβος κεφαλής είναι NULL.
- Ο δείκτης lastNode ενημερώνεται στον τρέχοντα κόμβο μέσα στον βρόχο while, εάν ο τρέχων κόμβος (headNode) δεν υπάρχει ήδη στον χάρτη κατακερματισμού.
- Εάν ο τρέχων κόμβος βρεθεί στον χάρτη, σημαίνει ότι υπάρχει ένας βρόχος στη συνδεδεμένη λίστα. Για να αφαιρέσετε τον βρόχο, ο επόμενος δείκτης του lastNode Έχει οριστεί ΜΗΔΕΝΙΚΟ και ο βρόχος while έχει σπάσει.
- Ο κύριος κόμβος της συνδεδεμένης λίστας χρησιμοποιείται ως είσοδος για μια συνάρτηση που ονομάζεται 'display', η οποία εξάγει την τιμή κάθε κόμβου στη λίστα από την αρχή μέχρι το τέλος.
- Στο κύριος λειτουργία, δημιουργώντας έναν βρόχο.
- Η συνάρτηση «functionHashMap» καλείται με τον δείκτη headNode ως είσοδο, ο οποίος αφαιρεί τον βρόχο από τη λίστα.
- Η τροποποιημένη λίστα εμφανίζεται χρησιμοποιώντας τη λειτουργία «εμφάνιση».
Προσέγγιση 2: Ο κύκλος του Floyd
Ο αλγόριθμος ανίχνευσης κύκλου του Floyd, συχνά γνωστός ως αλγόριθμος της χελώνας και του λαγού, παρέχει τη βάση για αυτήν τη μέθοδο εντοπισμού κύκλων σε μια συνδεδεμένη λίστα. Ο «αργός» δείκτης και ο «γρήγορος» δείκτης, που διασχίζουν τη λίστα με διάφορες ταχύτητες, είναι οι δύο δείκτες που χρησιμοποιούνται σε αυτήν την τεχνική. Ο γρήγορος δείκτης προχωρά δύο βήματα ενώ ο αργός δείκτης προχωρά ένα βήμα κάθε επανάληψη. Υπάρχει ένας κύκλος στη συνδεδεμένη λίστα εάν τα δύο σημεία έρχονται αντιμέτωπα.
1. Με τον κύριο κόμβο της συνδεδεμένης λίστας, αρχικοποιούμε δύο δείκτες που ονομάζονται γρήγορος και αργός.
2. Τώρα τρέχουμε έναν βρόχο για να μετακινηθούμε στη συνδεδεμένη λίστα. Ο γρήγορος δείκτης θα πρέπει να μετακινηθεί δύο θέσεις μπροστά από τον αργό δείκτη σε κάθε βήμα επανάληψης.
3. Δεν θα υπάρχει βρόχος στη συνδεδεμένη λίστα εάν ο γρήγορος δείκτης φτάσει στο τέλος της λίστας (fastPointer == NULL ή fastPointer->next == NULL). Εάν όχι, οι γρήγοροι και αργοί δείκτες θα συναντηθούν τελικά, πράγμα που σημαίνει ότι η συνδεδεμένη λίστα έχει έναν βρόχο.
Υλοποίηση προγράμματος C++ για την παραπάνω μέθοδο (Κύκλος Floyd’s):
#include
χρησιμοποιώντας namespace std?
/* Κόμβος λίστας συνδέσμων */
struct Κόμβος {
int δεδομένα?
struct Κόμβος * Επόμενο;
} ;
/* Λειτουργία αφαίρεσης βρόχου. */
void deleteLoop ( struct Κόμβος * , κατασκευή Κόμβου * ) ;
/* Αυτό λειτουργία εντοπίζει και εξαλείφει βρόχους λίστας. Αποδίδει 1
αν υπήρχε ένας βρόχος σε η λίστα; αλλού , επιστρέφει 0 . */
int detectAndDeleteLoop ( struct Κόμβος * λίστα )
{
struct Κόμβος * slowPTR = λίστα, * fastPTR = λίστα;
// Επαναλάβετε για έλεγχο αν ο βρόχος είναι εκεί.
ενώ ( αργόPTR && fastPTR && fastPTR- > Επόμενο ) {
slowPTR = αργόPTR- > Επόμενο;
fastPTR = fastPTR- > Επόμενο- > Επόμενο;
/* Εάν το slowPTR και το fastPTR συναντηθούν κάποια στιγμή έπειτα εκεί
είναι ένας βρόχος */
αν ( slowPTR == fastPTR ) {
deleteLoop ( slowPTR, λίστα ) ;
/* ΕΠΙΣΤΡΟΦΗ 1 για να υποδείξει ότι έχει ανακαλυφθεί βρόχος. */
ΕΠΙΣΤΡΟΦΗ 1 ;
}
}
/* ΕΠΙΣΤΡΟΦΗ 0 για να υποδείξει ότι δεν έχει ανακαλυφθεί βρόχος. */
ΕΠΙΣΤΡΟΦΗ 0 ;
}
/* Λειτουργία διαγραφής βρόχου από συνδεδεμένη λίστα.
Το loopNode δείχνει σε έναν από τους κόμβους βρόχου και το headNode δείχνει
στον κόμβο έναρξης της συνδεδεμένης λίστας */
void deleteLoop ( struct Κόμβος * loopNode, struct Node * headNode )
{
struct Κόμβος * ptr1 = loopNode;
struct Κόμβος * ptr2 = loopNode;
// Μετρήστε πόσοι είναι οι κόμβοι σε ο βρόχος.
ανυπόγραφο int k = 1 , Εγώ;
ενώ ( ptr1- > Επόμενο ! = ptr2 ) {
ptr1 = ptr1- > Επόμενο;
k++;
}
// Διορθώστε έναν δείκτη στο headNode
ptr1 = headNode;
// Και ο άλλος δείκτης σε k κόμβους μετά το headNode
ptr2 = headNode;
Για ( i = 0 ; Εγώ < κ; i++ )
ptr2 = ptr2- > Επόμενο;
/* Όταν και τα δύο σημεία μετακινούνται ταυτόχρονα,
θα συγκρουστούν στο βρόχο αρχικός κόμβος του. */
ενώ (ptr2 != ptr1) {
ptr1 = ptr1->επόμενο;
ptr2 = ptr2->επόμενο;
}
// Λήψη του κόμβου' μικρό τελευταίος δείκτης.
ενώ ( ptr2- > Επόμενο ! = ptr1 )
ptr2 = ptr2- > Επόμενο;
/* Για να κλείσετε τον βρόχο, σειρά το μεταγενέστερο
κόμβος στον βρόχο του τερματικού κόμβου. */
ptr2->next = NULL;
}
/* Λειτουργία για εμφάνιση συνδεδεμένης λίστας */
void displayLinkedList(struct Node* node)
{
// εμφάνιση της συνδεδεμένης λίστας μετά τη διαγραφή του βρόχου
ενώ (κόμβος != NULL) {
cout << κόμβος->δεδομένα << ' ';
node = node->next;
}
}
struct Node* newNode(int key)
{
struct Node* temp = new Node();
temp->data = κλειδί;
temp->next = NULL;
θερμοκρασία επιστροφής?
}
// Κύριος κώδικας
int main()
{
struct Node* headNode = newNode(48);
headNode->next = newNode(18);
headNode->next->next = newNode(13);
headNode->next->next->next = newNode(2);
headNode->next->next->next->next = newNode(8);
/* Δημιουργία βρόχου */
headNode->next->next->next->next->next = headNode->next->next;
// εμφάνιση του βρόχου στη συνδεδεμένη λίστα
//displayLinkedList(headNode);
detectAndDeleteLoop(headNode);
cout << 'Συνδεδεμένη λίστα μετά από κανένα βρόχο \n';
displayLinkedList(headNode);
επιστροφή 0;
}
Παραγωγή:
Συνδεδεμένη λίστα μετά από κανένα βρόχο
48 18 13 2 8
Εξήγηση:
-
- Οι σχετικές κεφαλίδες, όπως 'bits/stdc++.h' και 'std::cout', περιλαμβάνονται πρώτα.
- Στη συνέχεια δηλώνεται η δομή 'Node', η οποία αντιπροσωπεύει έναν κόμβο στη συνδεδεμένη λίστα. Ένας επόμενος δείκτης που οδηγεί στον ακόλουθο κόμβο στη λίστα περιλαμβάνεται μαζί με ένα ακέραιο πεδίο δεδομένων σε κάθε κόμβο.
- Στη συνέχεια, ορίζει το 'deleteLoop' και το 'detectAndDeleteLoop', δύο συναρτήσεις. Ένας βρόχος αφαιρείται από μια συνδεδεμένη λίστα χρησιμοποιώντας την πρώτη μέθοδο και ένας βρόχος ανιχνεύεται στη λίστα χρησιμοποιώντας τη δεύτερη συνάρτηση, η οποία στη συνέχεια καλεί την πρώτη διαδικασία για την αφαίρεση του βρόχου.
- Μια νέα συνδεδεμένη λίστα με πέντε κόμβους δημιουργείται στην κύρια συνάρτηση και δημιουργείται ένας βρόχος ορίζοντας τον επόμενο δείκτη του τελευταίου κόμβου στον τρίτο κόμβο.
- Στη συνέχεια, πραγματοποιεί κλήση στη μέθοδο 'detectAndDeleteLoop' ενώ μεταβιβάζει τον κύριο κόμβο της συνδεδεμένης λίστας ως όρισμα. Για τον εντοπισμό βρόχων, αυτή η συνάρτηση χρησιμοποιεί την προσέγγιση «Αργοί και γρήγοροι δείκτες». Χρησιμοποιεί δύο δείκτες που ξεκινούν στην κορυφή της λίστας, slowPTR και fastPTR. Ενώ ο γρήγορος δείκτης μετακινεί δύο κόμβους ταυτόχρονα, ο αργός δείκτης μετακινεί μόνο έναν κόμβο τη φορά. Ο γρήγορος δείκτης θα ξεπεράσει τελικά τον αργό δείκτη εάν η λίστα περιέχει έναν βρόχο και τα δύο σημεία θα συγκρουστούν στον ίδιο κόμβο.
- Η συνάρτηση καλεί τη συνάρτηση «deleteLoop» εάν βρει βρόχο, τροφοδοτώντας τον κύριο κόμβο της λίστας και τη διασταύρωση των αργών και γρήγορων δεικτών ως είσοδοι. Αυτή η διαδικασία δημιουργεί δύο δείκτες, ptr1 και ptr2, στον κύριο κόμβο της λίστας και μετράει τον αριθμό των κόμβων στον βρόχο. Μετά από αυτό, προωθεί έναν κόμβο δείκτη, όπου k είναι ο συνολικός αριθμός κόμβων στον βρόχο. Στη συνέχεια, μέχρι να συναντηθούν στην αρχή του βρόχου, προχωρά και τα δύο σημεία έναν κόμβο κάθε φορά. Στη συνέχεια, ο βρόχος σπάει ορίζοντας τον επόμενο δείκτη του κόμβου στο τέλος του βρόχου σε NULL.
- Μετά την αφαίρεση του βρόχου, εμφανίζει τη συνδεδεμένη λίστα ως τελικό βήμα.
Προσέγγιση 3: Αναδρομή
Η αναδρομή είναι μια τεχνική για την επίλυση προβλημάτων με τη διαίρεση τους σε μικρότερα, ευκολότερα υποπροβλήματα. Η αναδρομή μπορεί να χρησιμοποιηθεί για τη διέλευση μιας μεμονωμένης συνδεδεμένης λίστας σε περίπτωση που βρεθεί βρόχος εκτελώντας συνεχώς μια συνάρτηση για τον επόμενο κόμβο της λίστας μέχρι να φτάσει στο τέλος της λίστας.
Σε μια μεμονωμένη συνδεδεμένη λίστα, η βασική αρχή πίσω από τη χρήση της αναδρομής για την εύρεση ενός βρόχου είναι να ξεκινήσετε από την κορυφή της λίστας, να επισημάνετε τον τρέχοντα κόμβο ως επισκέψιμο σε κάθε βήμα και, στη συνέχεια, να προχωρήσετε στον επόμενο κόμβο επικαλώντας αναδρομικά τη συνάρτηση για αυτός ο κόμβος. Η μέθοδος θα επαναληφθεί πάνω από την πλήρη συνδεδεμένη λίστα επειδή καλείται αναδρομικά.
Η λίστα περιέχει έναν βρόχο εάν η συνάρτηση συναντά έναν κόμβο που έχει προηγουμένως επισημανθεί ως επίσκεψη. Σε αυτήν την περίπτωση, η συνάρτηση μπορεί να επιστρέψει true. Η μέθοδος μπορεί να επιστρέψει false εάν φτάσει στο τέλος της λίστας χωρίς να εκτελείται σε έναν κόμβο που επισκέφτηκε, πράγμα που υποδεικνύει ότι δεν υπάρχει βρόχος.
Αν και αυτή η τεχνική για τη χρησιμοποίηση της αναδρομής για την εύρεση ενός βρόχου σε μια ενιαία συνδεδεμένη λίστα είναι απλή στη χρήση και κατανόηση, μπορεί να μην είναι η πιο αποτελεσματική όσον αφορά την πολυπλοκότητα του χρόνου και του χώρου.
Υλοποίηση προγράμματος C++ για την παραπάνω μέθοδο (Recursion):
#include
χρησιμοποιώντας namespace std?
struct Κόμβος {
int δεδομένα?
Κόμβος * Επόμενο;
Bool επισκέφθηκε?
} ;
// Ανίχνευση βρόχου συνδεδεμένης λίστας λειτουργία
bool detectLoopLinkedList ( Κόμβος * headNode ) {
αν ( headNode == NULL ) {
ΕΠΙΣΤΡΟΦΗ ψευδής ; // Εάν η συνδεδεμένη λίστα είναι κενή, το βασικό υπόθεση
}
// Υπάρχει ένας βρόχος αν ο τρέχων κόμβος έχει
// έχει ήδη επισκεφθεί.
αν ( headNode- > επισκέφθηκε ) {
ΕΠΙΣΤΡΟΦΗ αληθής ;
}
// Προσθέστε ένα σημάδι επίσκεψης στον τρέχοντα κόμβο.
headNode- > επισκέφθηκε = αληθής ;
// Καλώντας τον κωδικό Για τον επόμενο κόμβο επανειλημμένα
ΕΠΙΣΤΡΟΦΗ detectLoopLinkedList ( headNode- > Επόμενο ) ;
}
int main ( ) {
Κόμβος * headNode = νέος κόμβος ( ) ;
Κόμβος * secondNode = νέος κόμβος ( ) ;
Κόμβος * τρίτος κόμβος = νέος κόμβος ( ) ;
headNode- > δεδομένα = 1 ;
headNode- > επόμενο = δεύτερος κόμβος;
headNode- > επισκέφθηκε = ψευδής ;
δεύτερος κόμβος- > δεδομένα = 2 ;
δεύτερος κόμβος- > επόμενος = τρίτος κόμβος;
δεύτερος κόμβος- > επισκέφθηκε = ψευδής ;
τρίτος κόμβος- > δεδομένα = 3 ;
τρίτος κόμβος- > επόμενο = NULL; // Χωρίς βρόχο
τρίτος κόμβος- > επισκέφθηκε = ψευδής ;
αν ( detectLoopLinkedList ( headNode ) ) {
cout << 'Εντοπίστηκε βρόχος στη συνδεδεμένη λίστα' << endl;
} αλλού {
cout << 'Δεν εντοπίστηκε βρόχος στη συνδεδεμένη λίστα' << endl;
}
// Δημιουργία βρόχου
τρίτος κόμβος- > επόμενο = δεύτερος κόμβος;
αν ( detectLoopLinkedList ( headNode ) ) {
cout << 'Εντοπίστηκε βρόχος στη συνδεδεμένη λίστα' << endl;
} αλλού {
cout << 'Δεν εντοπίστηκε βρόχος στη συνδεδεμένη λίστα' << endl;
}
ΕΠΙΣΤΡΟΦΗ 0 ;
}
Παραγωγή:
Δεν εντοπίστηκε βρόχος σε συνδεδεμένη λίστα
Εντοπίστηκε βρόχος σε συνδεδεμένη λίστα
Εξήγηση:
-
- Η λειτουργία detectLoopLinkedList() σε αυτό το πρόγραμμα δέχεται την κεφαλή της συνδεδεμένης λίστας ως είσοδο.
- Η αναδρομή χρησιμοποιείται από τη συνάρτηση για επανάληψη στη συνδεδεμένη λίστα. Ως βασική περίπτωση για την αναδρομή, ξεκινά με τον προσδιορισμό εάν ο τρέχων κόμβος είναι NULL. Εάν ναι, η μέθοδος επιστρέφει false, υποδεικνύοντας ότι δεν υπάρχει βρόχος.
- Στη συνέχεια, ελέγχεται η τιμή της ιδιότητας 'visited' του τρέχοντος κόμβου για να διαπιστωθεί εάν έχει προηγουμένως επισκεφθεί. Επιστρέφει true εάν έχει γίνει επίσκεψη, υποδηλώνοντας ότι βρέθηκε βρόχος.
- Η συνάρτηση επισημαίνει τον τρέχοντα κόμβο ως επισκέψιμο, εάν έχει ήδη επισκεφθεί, αλλάζοντας την ιδιότητα 'visited' του σε true.
- Στη συνέχεια, ελέγχεται η τιμή της μεταβλητής που επισκέφθηκε για να διαπιστωθεί εάν ο τρέχων κόμβος έχει επισκεφτεί προηγουμένως. Εάν έχει χρησιμοποιηθεί στο παρελθόν, πρέπει να υπάρχει βρόχος και η συνάρτηση επιστρέφει true.
- Τέλος, η συνάρτηση καλεί τον εαυτό της με τον επόμενο κόμβο στη λίστα περνώντας headNode->next ως επιχείρημα. Αναδρομικά , αυτό εκτελείται μέχρι είτε να βρεθεί ένας βρόχος είτε να γίνει επίσκεψη όλων των κόμβων. Σημαίνει ότι η συνάρτηση ορίζει τη μεταβλητή επίσκεψης σε true, εάν ο τρέχων κόμβος δεν έχει γίνει ποτέ επίσκεψη πριν καλέσει τον εαυτό του αναδρομικά για τον ακόλουθο κόμβο στη συνδεδεμένη λίστα.
- Ο κώδικας δημιουργεί τρεις κόμβους και τους ενώνει για να δημιουργήσει μια συνδεδεμένη λίστα στο κύρια λειτουργία . Η μέθοδος detectLoopLinkedList() στη συνέχεια καλείται στον κύριο κόμβο της λίστας. Το πρόγραμμα παράγει « Ο βρόχος αφαιρέθηκε στη συνδεδεμένη λίστα ' αν detectLoopLinkedList() επιστρέφει true? αλλιώς, βγάζει ' Δεν εντοπίστηκε βρόχος στη συνδεδεμένη λίστα '.
- Στη συνέχεια, ο κώδικας εισάγει έναν βρόχο στη συνδεδεμένη λίστα ορίζοντας τον επόμενο δείκτη του τελευταίου κόμβου στον δεύτερο κόμβο. Στη συνέχεια, ανάλογα με το αποτέλεσμα της συνάρτησης, εκτελείται detectLoopLinkedList() ξανά και παράγει είτε ' Ο βρόχος αφαιρέθηκε στη συνδεδεμένη λίστα ' ή ' Δεν εντοπίστηκε βρόχος στη συνδεδεμένη λίστα .»
Προσέγγιση 4: Χρήση στοίβας
Οι βρόχοι σε μια συνδεδεμένη λίστα μπορούν να βρεθούν χρησιμοποιώντας μια στοίβα και τη μέθοδο 'depth-first search' (DFS). Η θεμελιώδης ιδέα είναι η επανάληψη μέσω της συνδεδεμένης λίστας, ωθώντας κάθε κόμβο στη στοίβα, εάν δεν έχει ήδη επισκεφτεί. Ένας βρόχος αναγνωρίζεται εάν συναντηθεί ξανά ένας κόμβος που βρίσκεται ήδη στη στοίβα.
Ακολουθεί μια σύντομη περιγραφή της διαδικασίας:
-
- Δημιουργήστε μια κενή στοίβα και μια μεταβλητή για να καταγράψετε τους κόμβους που έχετε επισκεφθεί.
- Σπρώξτε τη συνδεδεμένη λίστα στη στοίβα, ξεκινώντας από την κορυφή. Σημειώστε ότι το κεφάλι έχει επισκεφθεί.
- Σπρώξτε τον επόμενο κόμβο στη λίστα στη στοίβα. Προσθέστε ένα σημάδι επίσκεψης σε αυτόν τον κόμβο.
- Καθώς διασχίζετε τη λίστα, σπρώξτε κάθε νέο κόμβο στη στοίβα για να υποδείξετε ότι έχει επισκεφθεί.
- Ελέγξτε εάν ένας κόμβος που έχει προηγουμένως επισκεφτεί βρίσκεται στην κορυφή της στοίβας, εάν συναντηθεί. Εάν ναι, έχει βρεθεί ένας βρόχος και ο βρόχος αναγνωρίζεται από τους κόμβους στη στοίβα.
- Αφαιρέστε τους κόμβους από τη στοίβα και συνεχίστε να διασχίζετε τη λίστα εάν δεν βρεθεί βρόχος.
Υλοποίηση προγράμματος C++ για την παραπάνω μέθοδο (Στοίβα)
#include
#include
χρησιμοποιώντας namespace std?
struct Κόμβος {
int δεδομένα?
Κόμβος * Επόμενο;
} ;
// Λειτουργία ανίχνευσης βρόχου σε μια συνδεδεμένη λίστα
bool detectLoopLinkedList ( Κόμβος * headNode ) {
σωρός < Κόμβος *> σωρός;
Κόμβος * tempNode = headNode;
ενώ ( tempNode ! = NULL ) {
// αν το επάνω στοιχείο της στοίβας ταιριάζει
// ο τρέχων κόμβος και η στοίβα δεν είναι άδεια
αν ( ! στοίβα.άδειο ( ) && στοίβα.κορυφή ( ) == tempNode ) {
ΕΠΙΣΤΡΟΦΗ αληθής ;
}
στοίβα.σπρώχνω ( tempNode ) ;
tempNode = tempNode- > Επόμενο;
}
ΕΠΙΣΤΡΟΦΗ ψευδής ;
}
int main ( ) {
Κόμβος * headNode = νέος κόμβος ( ) ;
Κόμβος * secondNode = νέος κόμβος ( ) ;
Κόμβος * τρίτος κόμβος = νέος κόμβος ( ) ;
headNode- > δεδομένα = 1 ;
headNode- > επόμενος = δεύτερος κόμβος;
δεύτερος κόμβος- > δεδομένα = 2 ;
δεύτερος κόμβος- > επόμενος = τρίτος κόμβος;
τρίτος κόμβος- > δεδομένα = 3 ;
τρίτος κόμβος- > επόμενο = NULL; // Χωρίς βρόχο
αν ( detectLoopLinkedList ( headNode ) ) {
cout << 'Εντοπίστηκε βρόχος στη συνδεδεμένη λίστα' << endl;
} αλλού {
cout << 'Δεν εντοπίστηκε βρόχος στη συνδεδεμένη λίστα' << endl;
}
// Δημιουργία βρόχου
τρίτος κόμβος- > επόμενο = δεύτερος κόμβος;
αν ( detectLoopLinkedList ( headNode ) ) {
cout << 'Εντοπίστηκε βρόχος στη συνδεδεμένη λίστα' << endl;
} αλλού {
cout << 'Δεν εντοπίστηκε βρόχος στη συνδεδεμένη λίστα' << endl;
}
Παραγωγή:
Δεν εντοπίστηκε βρόχος σε συνδεδεμένη λίστα
Εντοπίστηκε βρόχος σε συνδεδεμένη λίστα
Εξήγηση:
Αυτό το πρόγραμμα χρησιμοποιεί μια στοίβα για να ανακαλύψει εάν μια λίστα μεμονωμένα συνδεδεμένη έχει βρόχο.
- 1. Η βιβλιοθήκη ροής εισόδου/εξόδου και η βιβλιοθήκη στοίβας υπάρχουν και οι δύο στην πρώτη γραμμή.
2. Ο τυπικός χώρος ονομάτων περιλαμβάνεται στη δεύτερη γραμμή, επιτρέποντάς μας να έχουμε πρόσβαση στις λειτουργίες της βιβλιοθήκης ροής εισόδου/εξόδου χωρίς να χρειάζεται να βάλουμε πρόθεμα 'std::'.
3. Η ακόλουθη γραμμή ορίζει τη δομή Node, η οποία αποτελείται από δύο μέλη: έναν ακέραιο που ονομάζεται 'data' και έναν δείκτη σε έναν άλλο Κόμβο που ονομάζεται 'next'.
4. Η κεφαλή της συνδεδεμένης λίστας είναι μια είσοδος για τη μέθοδο detectLoopLinkedList(), η οποία ορίζεται στην επόμενη γραμμή. Η συνάρτηση παράγει μια τιμή boolean που υποδεικνύει εάν βρέθηκε βρόχος ή όχι.
5. Μια στοίβα από δείκτες κόμβου που ονομάζεται 'stack' και ένας δείκτης σε έναν κόμβο με το όνομα 'tempNode' που έχει αρχικοποιηθεί με την τιμή του headNode δημιουργούνται και οι δύο μέσα στη συνάρτηση.
6. Στη συνέχεια, εφόσον το tempNode δεν είναι μηδενικός δείκτης, εισάγουμε έναν βρόχο while.
(α) Το επάνω στοιχείο της στοίβας πρέπει να ταιριάζει με τον τρέχοντα κόμβο για να προσδιορίσουμε ότι δεν είναι κενό. Επιστρέφουμε true εάν αυτό συμβαίνει επειδή βρέθηκε βρόχος.
(β) Εάν η προαναφερθείσα συνθήκη είναι ψευδής, ο δείκτης του τρέχοντος κόμβου ωθείται στη στοίβα και το tempNode ορίζεται στον ακόλουθο κόμβο στη συνδεδεμένη λίστα.
7. Επιστρέφουμε false μετά τον βρόχο while γιατί δεν παρατηρήθηκε βρόχος.
8. Κατασκευάζουμε τρία αντικείμενα Node και τα αρχικοποιούμε στη συνάρτηση main(). Δεδομένου ότι δεν υπάρχει βρόχος στο πρώτο παράδειγμα, ορίσαμε σωστά τους «επόμενους» δείκτες κάθε Κόμβου.
Συμπέρασμα:
Συμπερασματικά, η καλύτερη μέθοδος ανίχνευσης βρόχων σε μια συνδεδεμένη λίστα εξαρτάται από τη συγκεκριμένη περίπτωση χρήσης και τους περιορισμούς του προβλήματος. Το Hash Table και ο αλγόριθμος εύρεσης κύκλου του Floyd είναι αποτελεσματικές μέθοδοι και χρησιμοποιούνται ευρέως στην πράξη. Η στοίβα και η αναδρομή είναι λιγότερο αποτελεσματικές μέθοδοι, αλλά είναι πιο διαισθητικές.