[Powered by Google Translate] Στον προγραμματισμό, θα πρέπει συχνά να αποτελούν τους καταλόγους των τιμών, όπως τα ονόματα των μαθητών σε ένα τμήμα ή τις επιδόσεις τους στις τελευταίες κουίζ. 

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

Όταν τους δηλώνουν, είμαστε υποχρεωμένη να πείτε μπροστά πόσο μεγάλη είναι, δηλαδή, πόσα στοιχεία μπορούν να αποθηκεύσουν και πόσο μεγάλη είναι αυτά τα στοιχεία, η οποία καθορίζεται από τον τύπο τους. Για παράδειγμα, int arr (10) μπορεί να αποθηκεύσει 10 αντικείμενα που είναι το μέγεθος ενός int. 

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

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

Εδώ είναι μερικά κώδικα C για μια σχέση πολύ απλή λίστα των ακεραίων. Μπορείτε να δείτε ότι έχουμε εκπροσωπούνται σε κάθε κόμβο στη λίστα ως ένα struct που περιέχει 2 πράγματα, ένας ακέραιος για την αποθήκευση ονομάζεται «val» και ένα σύνδεσμο στον επόμενο κόμβο της λίστας που εμείς εκπροσωπούμε ως δείκτη που ονομάζεται «επόμενο». Με αυτό τον τρόπο, μπορούμε να εντοπίσουμε ολόκληρη τη λίστα με ένα μόνο δείκτη στο πρώτο κόμβο, και στη συνέχεια μπορούμε να ακολουθήσουμε τα επόμενα δείκτες στο 2ο κόμβο, στο 3ο κόμβο, στο 4ο κόμβο, και ούτω καθεξής, μέχρι να φτάσουμε στο τέλος της λίστας. 

Ίσως να είναι σε θέση να βλέπετε 1 πλεονέκτημα αυτό έχει πάνω από την στατική δομή συστοιχίας - με μια συνδεδεμένη λίστα, δεν χρειαζόμαστε ένα μεγάλο κομμάτι της μνήμης συνολικά. Το 1ο κόμβο της λίστας θα μπορούσε να ζήσει σε αυτό το χώρο στη μνήμη, και ο 2ος κόμβος θα μπορούσε να είναι σε όλη τη διαδρομή εδώ. Μπορούμε να πάρουμε σε όλους τους κόμβους ανεξάρτητα από το πού στη μνήμη θα είναι, διότι ξεκινώντας από το πρώτο κόμβο, το επόμενο δείκτη κάθε κόμβου μας λέει ακριβώς πού να πάει δίπλα. 

Επιπλέον, δεν έχουμε να πούμε εκ των προτέρων πόσο μεγάλη είναι μια συνδεδεμένη λίστα θα είναι ο τρόπος που κάνουμε με στατικές συστοιχίες, αφού μπορούμε να συνεχίσουμε να προσθέτουμε κόμβους σε μια λίστα εφ 'όσον υπάρχει χώρος κάπου στη μνήμη για νέους κόμβους. Ως εκ τούτου, συνδεδεμένες λίστες είναι εύκολο να αλλάξετε το μέγεθος δυναμικά. Πείτε, αργότερα στο πρόγραμμα θα πρέπει να προσθέσετε περισσότερους κόμβους στη λίστα μας. Για να εισάγετε ένα νέο κόμβο στην λίστα μας on the fly, το μόνο που έχουμε να κάνουμε είναι να εκχωρήσει μνήμη για αυτόν τον κόμβο, γδούπο της αξίας των δεδομένων, και τοποθετήστε το στη συνέχεια, όπου θέλουμε με την προσαρμογή των κατάλληλων δεικτών. 

Για παράδειγμα, αν θέλαμε να τοποθετήσετε ένα κόμβο μεταξύ το 2ο και 3ο κόμβους της λίστας,  δεν θα πρέπει να μετακινήσετε το 2ο ή 3ο κόμβους καθόλου. Πείτε είμαστε εισάγοντας αυτό το κόκκινο κόμβο. Το μόνο που θα έχετε να κάνετε είναι δίπλα δείκτη του νέου κόμβου στο σημείο να τον 3ο κόμβο και στη συνέχεια επανακαλωδίωναν επόμενο δείκτη του 2ου κόμβου να επισημάνει νέο κόμβο μας. Έτσι, μπορούμε να αλλάξετε το μέγεθος των καταλόγων μας on the fly δεδομένου ότι ο υπολογιστής μας δεν βασίζεται σε ευρετηρίαση, αλλά μάλλον για τη σύνδεση με δείκτες για να τις αποθηκεύσετε. 

Ωστόσο, ένα μειονέκτημα της συνδεδεμένες λίστες είναι ότι, σε αντίθεση με μια στατική σειρά, ο υπολογιστής δεν μπορεί να πηδήξει μόνο στη μέση της λίστας. Δεδομένου ότι ο υπολογιστής έχει να επισκεφτεί κάθε κόμβο στην συνδεδεμένη λίστα για να φτάσουμε στο επόμενο, πρόκειται να λάβει περισσότερο χρόνο για να βρείτε ένα συγκεκριμένο κόμβο από ό, τι θα ήταν σε μία συστοιχία. Για να διασχίσει ολόκληρη η λίστα παίρνει χρόνο ανάλογο προς το μήκος του πίνακα, ή O (n) σε ασυμπτωτικό συμβολισμό. Κατά μέσο όρο, φθάνοντας σε κάθε κόμβο Επίσης, χρειάζεται χρόνο ανάλογο του n. 

Τώρα, ας γράψει πραγματικά κάποια κώδικα που λειτουργεί με συνδεδεμένες λίστες. Ας πούμε ότι θέλουμε μια συνδεδεμένη λίστα ακεραίων. Μπορούμε να αποτελέσει κόμβο στη λίστα μας και πάλι ως ένα struct με 2 πεδία, μια ακέραια τιμή που ονομάζεται «val» και ένα επόμενο δείκτη στον επόμενο κόμβο της λίστας. Λοιπόν, φαίνεται αρκετά απλό. 

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

Έτσι, θα χρειαστούμε ένα δείκτη ειδικά για την διάσχιση το οποίο θα καλέσουμε «ανίχνευσης». Θα ανιχνεύσουμε μέσα από όλα τα στοιχεία της λίστας ακολουθώντας την αλυσίδα των επόμενοι δείκτες. Το μόνο που έχετε αποθηκεύσει είναι ένας δείκτης στον κόμβο 1ο, ή «κεφαλή» της λίστας. Επικεφαλής σημεία στον κόμβο 1ο. Είναι του τύπου δείκτη-σε-κόμβο. 

Για να πάρετε την πραγματική 1ο κόμβο της λίστας, πρέπει να dereference αυτό το δείκτη, αλλά για να μπορέσουμε να το dereference, θα πρέπει να ελέγξετε αν ο δείκτης είναι μηδενική πρώτα. Αν είναι μηδενική, η λίστα είναι κενή, και θα πρέπει να εκτυπώσετε ένα μήνυμα που, επειδή η λίστα είναι κενή, δεν υπάρχει τελευταίο κόμβο. Αλλά, ας υποθέσουμε ότι η λίστα δεν είναι κενή. Αν δεν είναι, τότε θα πρέπει να ανιχνεύσουμε μέσα από ολόκληρη την λίστα μέχρι να φτάσουμε στο τελευταίο κόμβο της λίστας, και πώς μπορούμε να πει εάν ψάχνουμε στο τελευταίο κόμβο της λίστας; 

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

Έτσι, αν ερπυστριοφόρο → επόμενο είναι μηδενική, θυμηθείτε ότι η σύνταξη βέλος είναι μια συντόμευση για την εύρεση τιμών ένα δείκτη σε struct, στη συνέχεια, την πρόσβαση επόμενο πεδίο της ισοδυναμεί με την αμήχανη: (Ερπυστριοφόρο *). Επόμενη. Μόλις βρήκαμε τον τελευταίο κόμβο, θέλουμε να εκτυπώσετε ερπυστριοφόρο → val, η τιμή στον τρέχοντα κόμβο γνωρίζουμε ποια είναι η τελευταία. Διαφορετικά, αν δεν είμαστε ακόμα στο τελευταίο κόμβο της λίστας, πρέπει να προχωρήσουμε στο επόμενο κόμβο της λίστας και ελέγξτε αν αυτό είναι το τελευταίο. Για να το κάνετε αυτό, εμείς που απλώς δείκτη ανίχνευσης μας να επισημάνει στην επόμενη αξία του τρέχοντος κόμβου, δηλαδή, ο επόμενος κόμβος στη λίστα. Αυτό γίνεται με ρύθμιση ερπυστριοφόρο = ερπυστριοφόρο → επόμενη. Τότε επαναλάβουμε αυτή τη διαδικασία, με μια θηλιά, για παράδειγμα, μέχρι να βρούμε το τελευταίο κόμβο. Έτσι, για παράδειγμα, εάν ερπυστριοφόρα έδειχνε στο κεφάλι, θέτουμε ερπυστριοφόρο να επισημάνω με ερπυστριοφόρο → επόμενη, η οποία είναι η ίδια όπως στο επόμενο πεδίο του κόμβου πρώτο. Έτσι, τώρα ανίχνευσής μας είναι στραμμένη στο 2ο κόμβο, και, πάλι, επαναλαμβάνουμε αυτό με έναν βρόχο, μέχρι να βρεθεί το τελευταίο κόμβο, δηλαδή, όπου δίπλα δείκτης του κόμβου δείχνει σε null. Και εκεί έχουμε, βρήκαμε το τελευταίο κόμβο της λίστας, και να εκτυπώσετε την αξία του, χρησιμοποιούμε μόνο ερπυστριοφόρο → val. 

Διασχίζοντας δεν είναι τόσο κακή, αλλά τι γίνεται με την εισαγωγή; Ας υποθέσουμε ότι θέλετε να εισάγετε έναν ακέραιο στην 4η θέση σε έναν ακέραιο κατάλογο. Αυτό είναι μεταξύ των σημερινών 3ου και 4ου κόμβους. Πάλι, πρέπει να διασχίσει το λίστα μόνο για να φτάσετε στο 3ο στοιχείο, το ένα είμαστε μετά την εισαγωγή. Έτσι, δημιουργούμε ένα δείκτη ανίχνευσης και πάλι να διασχίσει τη λίστα, ελέγξτε αν ο δείκτης κεφάλι μας είναι μηδενική, και αν δεν είναι, το σημείο ανίχνευσης δείκτη μας στον κόμβο κεφάλι. Έτσι, είμαστε στο στοιχείο 1ο. Πρέπει να προχωρήσουμε 2 περισσότερα στοιχεία για να μπορέσουμε να εισάγετε, ώστε να μπορούμε να χρησιμοποιούμε ένα for loop int i = 1? i <3? i + + και σε κάθε επανάληψη του βρόχου, εκ των προτέρων δείκτη ανίχνευσής μας προς τα εμπρός με 1 κόμβο ελέγχοντας αν επόμενο πεδίο του τρέχοντος κόμβου είναι άκυρη, και αν δεν είναι, μετακινήστε το δείκτη του ανίχνευσής μας στον επόμενο κόμβο θέτοντας το ίσο με το επόμενο δείκτη του τρέχοντος κόμβου. Έτσι, αφού για το βρόχο μας λέει να κάνουμε ότι δύο φορές, έχουμε φτάσει στο 3ο κόμβο, και μόλις ο δείκτης ανίχνευσής μας έχει φτάσει στο κόμβο μετά που θέλουμε να εισάγετε νέα μας ακέραιο, πώς μπορούμε πραγματικά να κάνουμε την εισαγωγή; 

Λοιπόν, τα νέα μας ακέραιος πρέπει να εισαχθεί μέσα στον κατάλογο ως μέρος της δικής της struct node, δεδομένου ότι αυτό είναι πραγματικά μια ακολουθία κόμβων. Έτσι, ας κάνουμε ένα νέο δείκτη στον κόμβο που ονομάζεται «new_node," και που να δείχνουν ότι η μνήμη τώρα διαθέσει στο σωρό για τον ίδιο κόμβο, και πόση μνήμη χρειαζόμαστε να διαθέσει; Λοιπόν, το μέγεθος ενός κόμβου, και θέλουμε να θέσουμε στον τομέα της val στο ακέραιο ότι θέλουμε να εισάγετε. Ας πούμε, 6. Τώρα, ο κόμβος περιέχει ακέραια τιμή μας. Είναι επίσης καλή πρακτική να προετοιμαστεί επόμενο πεδίο του νέου κόμβου να επισημάνω σε null, αλλά τώρα τι; 

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

Έτσι, για να απλοποιηθεί αυτό, ας πούμε ότι 4 πρώτους κόμβους μας ονομάζονται Α, Β, Γ, και Δ, με τα βέλη που αντιπροσωπεύουν την αλυσίδα από δείκτες που συνδέουν τους κόμβους. Έτσι, θα πρέπει να εισάγετε νέο κόμβο μας μεταξύ κόμβων στο C και D. Είναι ζωτικής σημασίας να το κάνει με τη σωστή σειρά, και θα σας δείξω γιατί. 

Ας ρίξουμε μια ματιά σε λάθος τρόπος για να το κάνει πρώτα. Γεια σου, ξέρουμε ο νέος κόμβος πρέπει να έρθει αμέσως μετά C, οπότε ας δίπλα δείκτη Γ στο σημείο να new_node. Εντάξει, φαίνεται εντάξει, εμείς απλά πρέπει να τελειώσει μέχρι τώρα από κάνοντας επόμενο σημείο δείκτη του νέου κόμβου στο Δ, αλλά περιμένετε, πώς μπορούμε να το κάνουμε αυτό; Το μόνο πράγμα που θα μπορούσε να μας πει πού ήταν D, ήταν ο επόμενος δείκτης προηγουμένως αποθηκευτεί στο C, αλλά εμείς ξαναέγραψε ακριβώς αυτό το δείκτη να επισημάνει στο νέο κόμβο, έτσι δεν έχουμε πλέον καμία ένδειξη όπου D είναι στη μνήμη, και έχουμε χάσει το υπόλοιπο της λίστας. Δεν είναι καλή σε όλα. 

Έτσι, πώς θα το κάνουμε αυτό το δικαίωμα; Κατ 'αρχάς, το σημείο δίπλα δείκτη του νέου κόμβου στο D. Τώρα, τόσο η νέα κόμβου και C επόμενοι δείκτες οδηγούν στον ίδιο κόμβο, D, αλλά αυτό είναι εντάξει. Τώρα μπορούμε να επισημάνω επόμενο δείκτη Γ στο νέο κόμβο. Έτσι, έχουμε κάνει αυτό χωρίς να χάσει όλα τα δεδομένα. Σε κώδικα, το C είναι ο τρέχων κόμβος ότι η διάσχιση δείκτης ανίχνευσης δείχνει να, και D εκπροσωπείται από τον κόμβο υποδεικνύεται από επόμενο πεδίο της τρέχουσας κόμβου, ή ερπυστριοφόρο → επόμενη. Έτσι, θέτουμε πρώτη επόμενη δείκτη του νέου κόμβου να επισημάνω με ερπυστριοφόρο → επόμενη, με τον ίδιο τρόπο που είπαμε επόμενο δείκτη new_node θα πρέπει να δείχνουν Δ στην εικόνα. Στη συνέχεια, μπορούμε να θέσουμε επόμενο δείκτη του τρέχοντος κόμβου στο νέο κόμβο μας, ακριβώς όπως έπρεπε να περιμένουμε να επισημάνω C έως new_node στο σχέδιο. Τώρα όλα είναι σε τάξη, και δεν χάσαμε παρακολούθηση όλων των δεδομένων, και ήμασταν σε θέση να μόλις κολλήσει νέος κόμβος μας στη μέση της λίστας χωρίς την ανοικοδόμηση της όλο αυτό το πράγμα ή ακόμα και οποιαδήποτε αλλαγή στοιχείων ο τρόπος με τον οποίο θα έπρεπε να με σύμβαση ορισμένου μήκους πίνακα. 

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

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

Το όνομά μου είναι Steinkamp Jackson, αυτό είναι CS50.