>> [Παίζει μουσική]
>> DOUG LLOYD: Εντάξει, έτσι ώστε σε αυτό το σημείο στην πορεία,
έχουμε καλύψει πολλά από τα βασικά στοιχεία του C. Γνωρίζουμε πολλά για τις μεταβλητές, πίνακες,
δείκτες, όλα αυτά καλά πράγματα.
Αυτά είναι όλα χτισμένα είδους για να δείτε και τις βασικές αρχές,
αλλά μπορούμε να κάνουμε περισσότερα, έτσι δεν είναι;
Μπορούμε να συνδυάσουμε τα πράγματα μαζί με ενδιαφέροντες τρόπους.
>> Και έτσι ας το κάνουμε αυτό, ας ξεκινήσουμε για την επέκτασή τους από ό, τι μας δίνει C,
και να αρχίσει να δημιουργήσετε το δικό μας δεδομένα δομές που χρησιμοποιούν τα κτίρια αυτά
μπλοκ μαζί για να κάνουμε κάτι πραγματικά πολύτιμη, χρήσιμες.
Ένας τρόπος για να γίνει αυτό είναι για να μιλήσουμε για συλλογές.
Έτσι μέχρι τώρα είχαμε ένα είδος δεδομένων δομή για την αναπαράσταση των συλλογών
του αρέσει αξίες, παρόμοιες τιμές.
Αυτό θα ήταν ένας πίνακας.
Έχουμε συλλογές των ακεραίων, ή συλλογές των χαρακτήρων και ούτω καθεξής.
>> Δομές είναι επίσης ένα είδος δεδομένων δομή για τη συλλογή πληροφοριών,
αλλά δεν είναι για τη συλλογή, όπως τιμές.
Συνδυάζει συνήθως διαφορετικούς τύπους δεδομένων μαζί μέσα από ένα ενιαίο κουτί.
Αλλά δεν είναι η ίδια που χρησιμοποιούνται για την αλυσίδα μαζί
ή συνδεθείτε μαζί παρόμοιες αντικείμενα, όπως μια σειρά.
Οι πίνακες είναι μεγάλη για στοιχείο κοιτάζω προς τα πάνω, αλλά ανάκληση
ότι είναι πολύ δύσκολο για την εισαγωγή σε μια σειρά,
εκτός και αν είμαστε εισαγωγή στο το τέλος του εν λόγω πίνακα.
>> Και το καλύτερο παράδειγμα που έχω γι 'αυτό είναι το είδος εισαγωγής.
Αν θυμάστε το βίντεο μας σε ταξινόμηση με εισαγωγή,
υπήρχε πολλή τα έξοδα που απαιτούνται με
για να πάρει στοιχεία, και μεταφορά τους έξω από το δρόμο για να χωρέσει κάτι
στη μέση του πίνακα σας.
Πίνακες υποφέρουν επίσης από το άλλο πρόβλημα, το οποίο είναι η ακαμψία.
Όταν δηλώνουμε έναν πίνακα, παίρνουμε έναν πυροβολισμό σε αυτό.
Παίρνουμε να πω, θέλω αυτό πολλά στοιχεία.
Μπορεί να είναι 100, θα μπορούσε να είναι 1.000, θα μπορούσε να
είναι x όπου χ είναι ένας αριθμός ο χρήστης μας έδωσε σε μια γραμμή ή στη γραμμή
γραμμή.
>> Αλλά έχουμε πάρει μόνο έναν πυροβολισμό σε αυτό, εμείς Δεν έχετε να στη συνέχεια να πω OH, πραγματικά μου
απαιτούνται 101, ή χρειαζόμουν x συν 20.
Πάρα πολύ αργά, έχουμε ήδη δηλώσει το σειρά, και αν θέλουμε να πάρουμε 101 ή x
συν 20, θα πρέπει να δηλώσουν μια εντελώς διαφορετική σειρά,
αντιγράψτε όλα τα στοιχεία του πίνακα πάνω, και στη συνέχεια έχουμε αρκετά.
Και τι θα γίνει αν είμαστε πάλι λάθος, τι αν πράγματι χρειαζόμαστε 102 ή x συν 40,
πρέπει να το κάνουμε αυτό και πάλι.
Έτσι είναι πολύ άκαμπτη για την αλλαγή μεγέθους των δεδομένων μας,
αλλά αν συνδυάσουμε μαζί μερικά από τα βασικά στοιχεία που έχουμε ήδη
έμαθαν για τους δείκτες και τις δομές, ιδίως με τη χρήση δυναμικής μνήμης
κατανομή με malloc, εμείς μπορεί να βάλει αυτά τα κομμάτια μαζί
Για να δημιουργήσετε μια νέα δεδομένα structure-- ένα μεμονωμένα συνδεδεμένη λίστα θα μπορούσαμε να say--
ότι μας επιτρέπει να αναπτυχθούν και να συρρικνωθεί μια συλλογή των τιμών
και δεν θα έχουμε καμία σπατάλη χώρου.
>> Έτσι και πάλι, καλούμε αυτήν την ιδέα, Η έννοια αυτή, μια συνδεδεμένη λίστα.
Ειδικότερα, σε αυτό το βίντεο είμαστε μιλάμε για μεμονωμένα συνδεδεμένη λίστα,
και στη συνέχεια ένα άλλο βίντεο θα μιλήσουμε για διπλά συνδεδεμένες λίστες, οι οποίες
είναι απλά μια παραλλαγή σε ένα θέμα εδώ.
Αλλά ένα μεμονωμένα συνδεδεμένη λίστα αποτελείται από κόμβους,
κόμβοι είναι απλώς μια αφηρημένη term-- είναι απλώς κάτι καλώ
αυτό είναι ένα είδος δομή, βασικά, είμαι;
Απλά πρόκειται να την ονομάσω ένα node-- και αυτό κόμβος έχει δύο μέλη, ή δύο πεδία.
Έχει δεδομένων, συνήθως μια ακέραιος, ο πλωτήρας χαρακτήρα,
ή θα μπορούσε να είναι κάποιο άλλο τύπο δεδομένων ότι έχετε ορίσει με έναν τύπο def.
Και περιέχει ένα δείκτη σε άλλος κόμβος του ίδιου τύπου.
>> Έτσι έχουμε δύο πράγματα στο εσωτερικό του Αυτός ο κόμβος, δεδομένων και ένα δείκτη
σε άλλο κόμβο.
Και αν αρχίσουν να απεικονίσει αυτό, μπορείτε να το σκεφτείτε
σαν μια αλυσίδα των κόμβων που συνδέονται μεταξύ τους.
Έχουμε την πρώτη κόμβος, περιέχει δεδομένα, και ένα δείκτη
στον δεύτερο κόμβο, το οποίο περιέχει δεδομένων, και ένα δείκτη στον τρίτο κόμβο.
Και έτσι αυτό είναι ο λόγος που το αποκαλούμε ένα συνδεδεμένη λίστα, από όπου και αν συνδέονται μεταξύ τους.
>> Τι κάνει αυτή την ειδική δομή κόμβου μοιάζει;
Λοιπόν, αν θυμάστε από το βίντεο μας Ορισμός των ειδικών τύπων, με τον τύπο def,
μπορούμε να ορίσουμε μια structure-- και πληκτρολογήστε καθορίσει μια δομή σαν αυτή.
tyepdef struct sllist, και τότε είμαι χρησιμοποιώντας την τιμή λέξη εδώ αυθαίρετα
να αναφέρουν οποιοδήποτε τύπο δεδομένων πραγματικά.
Θα μπορούσατε να δώσετε έναν ακέραιο ή πλωτήρα, θα μπορούσατε να έχετε ό, τι θέλετε.
Δεν είναι μόνο να περιορίζεται ακέραιοι, ή κάτι τέτοιο.
Έτσι, η τιμή είναι απλά μια αυθαίρετη τύπο δεδομένων, και στη συνέχεια ένα δείκτη
σε άλλο κόμβο του ίδιου τύπου.
>> Τώρα, υπάρχει μια μικρή αλιευμάτων εδώ με τον καθορισμό μιας δομής
όταν πρόκειται για μια δομή εαυτού αναφορική.
Θα πρέπει να έχουν προσωρινό όνομα για τη δομή μου.
Στο τέλος της ημέρας Ι σαφώς θέλετε να το ονομάσετε
SLL κόμβο, αυτό είναι τελικά το νέο Ονομα μέρος του ορισμού του τύπου μου,
αλλά δεν μπορώ να χρησιμοποιήσω SLL κόμβο στη μέση αυτού.
Ο λόγος είναι, δεν έχω δημιούργησε έναν τύπο που ονομάζεται SLL κόμβου
μέχρι να χτυπήσει αυτό το τελικό σημείο εδώ.
Μέχρι εκείνο το σημείο, πρέπει να έχω ένας άλλος τρόπος για να αναφερθεί σε αυτό το είδος των δεδομένων.
>> Και αυτό είναι μια αυτο αναφορών τύπο δεδομένων.
Είναι? S έναν τύπο δεδομένων ενός δομή που περιέχει ένα δεδομένων,
και ένα δείκτη σε ένα άλλο δομή του ίδιου τύπου.
Γι 'αυτό και πρέπει να είναι σε θέση να αναφερθεί σε Αυτός ο τύπος δεδομένων τουλάχιστον προσωρινά,
δίνοντας έτσι την προσωρινή Το όνομά του struct sllist
μου επιτρέπει να πω στη συνέχεια, θέλω ένα δείκτη σε άλλο struct sllist,
ένα αστέρι struct sllist, και στη συνέχεια, αφού έχω ολοκληρώσει τον ορισμό,
Μπορώ τώρα να καλέσετε αυτό το είδος ένα κόμβο SLL.
>> Έτσι, γι 'αυτό θα δείτε εκεί ένα προσωρινό όνομα εδώ,
αλλά μια μόνιμη όνομα εδώ.
Μερικές φορές μπορεί να δείτε ορισμοί της δομής,
για παράδειγμα, ότι δεν είναι αυτο αναφορών, ότι
Δεν έχει ένα όνομα προσδιοριστικό εδώ.
Θα ήθελα απλώς να πω typedef struct, ανοίξτε σγουρά στήριγμα και στη συνέχεια να την ορίσουμε.
Αλλά αν είστε struct είναι αυτο αναφορών, καθώς αυτό είναι,
θα πρέπει να καθορίσετε ένα προσωρινό όνομα τύπου.
Αλλά τελικά, τώρα ότι έχουμε κάνει αυτό,
απλά μπορεί να αναφέρεται σε Αυτοί οι κόμβοι, οι μονάδες αυτές,
όπως SLL κόμβων για σκοπούς από το υπόλοιπο αυτού του βίντεο.
>> Εντάξει, έτσι ώστε να γνωρίζουν πώς να δημιουργήσετε μια συνδεδεμένη λίστα κόμβων.
Ξέρουμε πώς να καθορίσει μια συνδεδεμένη λίστα κόμβων.
Τώρα, αν θα πάμε για να ξεκινήσετε τη χρήση τους για τη συλλογή πληροφοριών,
υπάρχει ένα ζεύγος πράξεων που πρέπει να κατανοήσουν και να εργαστεί με.
Πρέπει να ξέρετε πώς να δημιουργήσετε μια συνδεδεμένη λίστα από αέρα κοπανιστό.
Εάν δεν υπάρχει κατάλογος ήδη, θέλουμε να αρχίσουμε μία.
Γι 'αυτό και πρέπει να είναι σε θέση για να δημιουργήσετε μια συνδεδεμένη λίστα,
θα πρέπει να αναζητήσετε πιθανώς στη λίστα σύνδεσμο
για να βρείτε ένα στοιχείο που ψάχνουμε.
Πρέπει να είμαστε σε θέση να εισαγάγετε νέα πράγματα στη λίστα,
θέλουμε λίστα μας να είναι σε θέση να αναπτυχθούν.
Και ομοίως, θέλουμε να είναι σε θέση για να διαγράψετε τα πράγματα από τη λίστα μας,
θέλουμε λίστα μας να είναι σε θέση να συρρικνωθεί.
Και στο τέλος μας προγραμμάτων, ιδίως
αν θυμηθούμε ότι είμαστε δυναμική εκχώρηση μνήμης
για την κατασκευή αυτών των καταλόγων κατά κανόνα, θέλουμε να ελευθερώσουμε το σύνολο των εν λόγω μνήμη
όταν τελειώσετε την εργασία με αυτό.
Και έτσι πρέπει να είμαστε σε θέση να διαγράψετε ένα ολόκληρη η συνδεδεμένη λίστα σε ένα αποτύχει προσγειωνόμαστε.
Ας πάμε μέσα ορισμένες από αυτές τις
και πώς θα μπορούσαμε να τα απεικονίσει, μιλώντας σε κώδικα ειδικά ψευδοκώδικα.
Έτσι θέλουμε να δημιουργήσουμε μια συνδεδεμένη λίστα, οπότε ίσως θα
θέλουμε να ορίσουμε μια συνάρτηση με αυτό το πρωτότυπο.
SLL κόμβο αστέρων, δημιουργούν, και περνώ σε ένα επιχείρημα, κάποια αυθαίρετη δεδομένα
πληκτρολογήστε ξανά, από κάποια αυθαίρετη τύπο δεδομένων.
Αλλά είμαι returning-- αυτή τη λειτουργία θα πρέπει να να επιστρέψει σε μένα ένα δείκτη, σε μεμονωμένα
συνδεδεμένη λίστα κόμβων.
Και πάλι, προσπαθούμε να δημιουργήσουμε μια συνδεδεμένη λίστα από το πουθενά,
γι 'αυτό χρειάζεται ένα δείκτη ο κατάλογος αυτός όταν είμαι γίνει.
>> Έτσι, ποια είναι τα βήματα που εμπλέκονται εδώ;
Λοιπόν, το πρώτο πράγμα που είμαι πρόκειται να κάνουμε είναι δυναμικά
διατεθεί χώρος για ένα νέο κόμβο.
Και πάλι, είμαστε αυτό δημιουργεί εκ του μηδενός αέρα, γι 'αυτό πρέπει να malloc χώρο για αυτό.
Και φυσικά, άμεσα αφού malloc,
πάντα βεβαιωθείτε ότι μας pointer-- δεν πήραμε πίσω null.
Διότι αν προσπαθήσουμε και υποχώρηση ένα κενό δείκτη,
θα πάμε να υποστούν μια segfault και εμείς δεν το θέλουμε αυτό.
>> Στη συνέχεια, θέλουμε να συμπληρώσει το πεδίο, θέλουμε να προετοιμάσει το πεδίο τιμής
και να προετοιμάσει το επόμενο πεδίο.
Και μετά θέλουμε to-- τελικά η πρωτότυπο λειτουργία indicates-- θέλουμε
να επιστρέψει ένα δείκτη σε ένα κόμβο SLL.
Έτσι, αυτό που κάνει αυτό μοιάζουν οπτικά;
Λοιπόν, πρώτα θα πάμε να δυναμικά διατεθεί χώρος για ένα νέο κόμβο SLL,
γι 'αυτό είναι ότι malloc-- μια οπτική αναπαράσταση
του κόμβου που μόλις δημιουργήσαμε.
Και βεβαιωθείτε δεν είναι null-- σε αυτή την περίπτωση,
η εικόνα δεν θα έχει δείξει μέχρι αν ήταν άκυρη,
θα είχαμε ξεμείνει από μνήμη, έτσι είμαστε καλοί να πάτε εκεί.
Έτσι, τώρα είμαστε στο βήμα C, προετοιμάσει το πεδίο κόμβους αξία.
Λοιπόν, με βάση αυτή τη λειτουργία καλέστε είμαι με τη χρήση εδώ,
Μοιάζει θέλω να μεταφέρω σε 6, Γι 'αυτό θα 6 στο πεδίο της τιμής.
Τώρα, να προετοιμάσει το επόμενο πεδίο.
Λοιπόν, τι θα πάω να κάνω εκεί, δεν υπάρχει τίποτα δίπλα, δεξιά,
αυτό είναι το μόνο πράγμα στη λίστα.
Ποιο είναι λοιπόν το επόμενο πράγμα στη λίστα;
>> Δεν θα πρέπει να επισημάνω κάτι, σωστά.
Δεν υπάρχει τίποτα άλλο εκεί, οπότε ό, τι είναι η έννοια που γνωρίζουμε ότι είναι nothing--
δείκτες σε τίποτα;
Θα πρέπει να είναι ίσως θέλουμε για να τεθεί ένα κενό δείκτη εκεί,
και θα αντιπροσωπεύουν το null pointer όπως ακριβώς ένα κόκκινο κουτί,
δεν μπορούμε να προχωρήσουμε περαιτέρω.
Όπως θα δούμε λίγο αργότερα, θα έχουμε τελικά αλυσίδες
βέλη που συνδέουν Αυτοί οι κόμβοι μαζί,
αλλά όταν χτύπησε το κόκκινο κουτί, αυτό είναι μηδενική,
δεν μπορούμε να προχωρήσουμε περαιτέρω, αυτό είναι το τέλος της λίστας.
>> Και τέλος, θέλουμε απλώς να επιστρέφει ένα δείκτη σε αυτόν τον κόμβο.
Γι 'αυτό και θα το ονομάζουμε νέα, και θα επιστρέψει νέα
έτσι ώστε να μπορεί να χρησιμοποιηθεί σε Όποια και αν είναι η λειτουργία το δημιούργησε.
Έτσι εκεί πάμε, Έχουμε δημιουργήσει ένα μεμονωμένα συνδεδεμένη λίστα κόμβων από το πουθενά,
και τώρα έχουμε μια λίστα μπορούμε να εργαστούμε με.
>> Τώρα, ας πούμε ήδη έχουν μια μεγάλη αλυσίδα,
και θέλουμε να βρούμε κάτι σε αυτό.
Και θέλουμε μια λειτουργία που πρόκειται να επιστρέψει αληθής ή ψευδής, ανάλογα
σχετικά με το εάν υπάρχει η τιμή στον εν λόγω κατάλογο.
Ένα πρωτότυπο λειτουργία, ή δήλωση για την εν λόγω λειτουργία,
Μπορεί να μοιάζει με this-- bool βρείτε, και τότε θα θέλετε να περάσετε σε δύο επιχειρήματα.
>> Το πρώτο, είναι ένας δείκτης για την πρώτου στοιχείου της συνδεδεμένης λίστας.
Αυτό είναι πραγματικά κάτι που θα θέλουν πάντα να παρακολουθείτε,
και στην πραγματικότητα θα μπορούσε να είναι κάτι που Μπορείτε ακόμη και να θέσει σε μια καθολική μεταβλητή.
Αφού δημιουργήσετε μια λίστα, μπορείτε πάντα, πάντα
θέλετε να παρακολουθείτε την πολύ πρώτο στοιχείο της λίστας.
Με αυτόν τον τρόπο μπορείτε να ανατρέξετε σε όλα τα άλλα στοιχεία από μόνο μετά την αλυσίδα,
χωρίς να χρειάζεται να κρατήσει δείκτες άθικτα σε κάθε μεμονωμένο στοιχείο.
Το μόνο που χρειάζεται να παρακολουθείτε την πρώτη ένα, αν είναι όλα δεμένους.
>> Και στη συνέχεια το δεύτερο πράγμα που είμαστε περνώντας και πάλι
είναι αυθαίρετα some-- ανεξάρτητα από τον τύπο των δεδομένων είμαστε
ψάχνετε εκεί είναι μέσα ελπίζουμε ότι ένας από τους κόμβους της λίστας.
Έτσι, ποια είναι τα βήματα;
Λοιπόν, το πρώτο πράγμα που κάνουμε είναι δημιουργούμε ένα εγκάρσιο δείκτη
που δείχνουν προς το κεφάλι τους καταλόγους.
Λοιπόν, γιατί να το κάνουμε αυτό, έχουμε ήδη έχουν ένα δείκτη στο κεφάλι τους καταλόγους,
γιατί δεν μπορούμε απλά να μεταφερθεί η μία γύρω;
Λοιπόν, όπως είπα, Είναι πραγματικά σημαντικό για εμάς
να κρατούν πάντα κομμάτι της πρώτο στοιχείο στη λίστα.
Και γι 'αυτό είναι πραγματικά καλύτερα για να δημιουργήσετε ένα αντίγραφο από αυτό,
και να τις χρησιμοποιούν για να μετακινούνται έτσι δεν μπορούμε ποτέ μετακινήσετε κατά λάθος μακριά, ή εμείς πάντα
έχουν ένα δείκτη σε κάποιο σημείο που είναι δεξιά στο πρώτο στοιχείο της λίστας.
Έτσι είναι καλύτερα να δημιουργηθεί μια δεύτερο που χρησιμοποιούμε για να προχωρήσουμε.
>> Στη συνέχεια συγκρίνει μόνο αν το πεδίο αξία αυτού του κόμβου
είναι αυτό που ψάχνετε, και αν είναι όχι, απλά να προχωρήσουμε στο επόμενο κόμβο.
Και συνεχίζουμε να το κάνουμε αυτό πάνω, και πάνω, και πάνω,
μέχρι να βρείτε είτε το στοιχείο, ή χτυπάμε
null-- έχουμε φτάσει στο τέλος του καταλόγου και δεν είναι εκεί.
Αυτό πρέπει να χτυπήσει ένα κουδούνι αισίως για να σας, όπως ακριβώς γραμμική αναζήτηση,
είμαστε απλά αναπαράγει σε ένα μεμονωμένα συνδεδεμένη δομή καταλόγου
αντί να χρησιμοποιεί μια σειρά για να το κάνουμε.
>> Έτσι, εδώ είναι ένα παράδειγμα της ένα μεμονωμένα συνδεδεμένη λίστα.
Αυτός αποτελείται από πέντε κόμβους, και έχουμε
ένας δείκτης στο κεφάλι της κατάλογο, το οποίο ονομάζεται λίστα.
Το πρώτο πράγμα που θέλουμε να κάνουμε είναι να και πάλι, να δημιουργήσει αυτό το δείκτη διάσχισης.
Έτσι, έχουμε τώρα δύο δείκτες ότι το σημείο για το ίδιο πράγμα.
>> Τώρα, εδώ παρατηρήσετε επίσης, δεν το έκανα Πρέπει να malloc κανένα χώρο για Trav.
Δεν είπα Trav ισούται με malloc κάτι, αυτός ο κόμβος υπάρχει ήδη,
ότι ο χώρος στη μνήμη υπάρχει ήδη.
Έτσι, όλα είμαι πραγματικά κάνει είναι δημιουργώντας έναν άλλο δείκτη σε αυτό.
Δεν είμαι mallocing πρόσθετη χώρο, έχουν μόλις τώρα δίποντα
που δείχνουν προς το ίδιο πράγμα.
>> Έτσι είναι 2 αυτό που ψάχνω;
Λοιπόν, όχι, έτσι ώστε αντί να είμαι πρόκειται να κινηθεί στο επόμενο.
Έτσι, βασικά θα έλεγα, Trav Trav ισούται με το επόμενο.
Είναι 3 τι ψάχνω, όχι.
Γι 'αυτό και συνεχίζουν να πάει μέσω, μέχρι που τελικά
φτάσετε στο 6 το οποίο είναι αυτό που ψάχνω για βασίζονται στην κλήση της συνάρτησης
Έχω στην κορυφή εκεί, και έτσι είμαι γίνει.
>> Τώρα, τι εάν το στοιχείο είμαι αναζητάτε δεν είναι στη λίστα,
Είναι ακόμα πρόκειται να λειτουργήσει;
Λοιπόν, παρατηρήστε ότι ο κατάλογος εδώ είναι ελαφρά διαφορετική,
και αυτό είναι ένα άλλο πράγμα που είναι σημαντικό με συνδεδεμένες λίστες,
δεν χρειάζεται να διατηρηθεί τους σε κάποια συγκεκριμένη σειρά.
Μπορείτε, αν θέλετε, αλλά μπορεί να έχετε ήδη παρατηρήσει
ότι δεν είμαστε παρακολούθηση των ποιος είναι ο αριθμός των στοιχείων βρισκόμαστε.
>> Και αυτό είναι το είδος του ένα εμπόριο που θα έχουν με συνδεδεμένη λίστα στίχους συστοιχίες,
είναι ότι δεν έχουμε τυχαίας προσπέλασης πια.
Δεν μπορούμε απλά να πω, θέλω να πάει στο 0th στοιχείο,
ή η 6η στοιχείο του πίνακα μου, το οποίο μπορώ να κάνω σε μια σειρά.
Δεν μπορώ να πω ότι θέλω να πάω να το 0th στοιχείο, ή το 6ο στοιχείο,
ή το 25ο στοιχείο της συνδεδεμένης λίστας μου, δεν υπάρχει δείκτης που συνδέονται με αυτά.
Και γι 'αυτό δεν έχει τόση σημασία αν διατηρούμε κατάλογο μας σε τάξη.
Αν θέλετε να σας σίγουρα μπορεί, αλλά δεν υπάρχει
κανένας λόγος για τον οποίο πρέπει να να συντηρηθεί με οποιαδήποτε σειρά.
Έτσι και πάλι, ας προσπαθήσουμε και βρείτε 6 σε αυτή τη λίστα.
Λοιπόν, ξεκινάμε με το αρχίζουν, δεν βρίσκουμε 6,
και στη συνέχεια θα συνεχίσουν να μην εύρεση 6, μέχρι να φτάσουμε τελικά εδώ.
Έτσι τώρα Trav σημεία στον κόμβο που περιέχουν 8, έξι δεν είναι εκεί.
>> Έτσι, το επόμενο βήμα θα είναι για να μεταβείτε στον επόμενο δείκτη,
έτσι λένε Trav Trav ισούται με το επόμενο.
Λοιπόν, Trav επόμενο, που υποδεικνύεται από το κόκκινο κουτί εκεί, είναι μηδενική.
Έτσι, δεν υπάρχει πουθενά αλλού να πάει, και έτσι σε αυτό το σημείο
μπορούμε να συμπεράνουμε ότι πετύχαμε το τέλος του συνδεδεμένη λίστα,
και 6 δεν είναι εκεί.
Και θα πρέπει να επιστραφεί ψευδείς σε αυτή την περίπτωση.
>> Εντάξει, πώς θα τοποθετήσετε μια νέα κόμβου στη συνδεδεμένη λίστα;
Έτσι είμαστε σε θέση να δημιουργήσουμε μια συνδεδεμένη λίστα από το πουθενά,
αλλά πιθανόν να θέλετε να οικοδομήσουμε μια αλυσίδα και δεν
δημιουργήσετε ένα μάτσο ξεχωριστοί κατάλογοι.
Θέλουμε να έχουμε μια λίστα που έχει μια δέσμη των κόμβων σε αυτό,
όχι μια χούφτα των καταλόγων με ένα μόνο κόμβο.
Γι 'αυτό και δεν μπορεί να κρατήσει μόνο χρησιμοποιώντας Δημιουργία συνάρτηση που ορίζεται νωρίτερα, τώρα είμαστε
θέλετε να εισάγετε σε μια κατάλογο που ήδη υπάρχει.
>> Έτσι αυτή την περίπτωση, θα πάμε για να περάσει σε δύο επιχειρήματα,
ο δείκτης στο κεφάλι του ότι συνδεδεμένη λίστα που θέλετε να προσθέσετε στο.
Και πάλι, γι 'αυτό είναι τόσο σημαντικό να έχουμε πάντα
Παρακολουθήστε αυτό, επειδή Είναι ο μόνος τρόπος που μπορούμε πραγματικά
πρέπει να αναφέρονται στο σύνολο καταλόγου είναι μόνο με ένα δείκτη προς το πρώτο στοιχείο.
Θέλουμε, λοιπόν, να περάσει σε ένα δείκτη σε αυτή πρώτο στοιχείο,
και ανεξάρτητα από την αξία μας θέλετε να προσθέσετε στη λίστα.
Και τελικά αυτή η λειτουργία πρόκειται να επιστρέψει ένα δείκτη
με το νέο επικεφαλής μιας συνδεδεμένης λίστας.
>> Ποια είναι τα βήματα που εμπλέκονται εδώ;
Λοιπόν, ακριβώς όπως με τη δημιουργία, θα πρέπει να κατανέμει δυναμικά
χώρος για ένα νέο κόμβο, και ελέγξτε για να βεβαιωθείτε βέβαιος ότι δεν τρέχουν έξω από τη μνήμη, και πάλι,
επειδή είμαστε χρησιμοποιώντας malloc.
Στη συνέχεια, θέλουμε να συμπληρώσετε και τοποθετήστε τον κόμβο,
έτσι που ο αριθμός, ανεξαρτήτως val είναι μέσα στον κόμβο.
Θέλουμε να εισάγετε τον κόμβο στο η αρχή της συνδεδεμένης λίστας.
>> Υπάρχει ένας λόγος για τον οποίο εγώ θέλετε να το κάνετε αυτό, και
θα μπορούσε να αξίζει να ρίξουμε μια δεύτερη για να διακόψετε το βίντεο εδώ,
και σκεφτείτε γιατί θα ήθελα να ένθετο κατά την έναρξη ενός συνδεδεμένου
κατάλογο.
Και πάλι, ανέφερα νωρίτερα ότι πραγματικά δεν το κάνει
σημασία αν το διατηρήσουμε σε οποιαδήποτε Προκειμένου, οπότε ίσως αυτό είναι μια ένδειξη.
Και είδες τι θα συνέβαινε αν ήθελε to-- ή από μόλις ένα δευτερόλεπτο
πριν, όταν πηγαίναμε μέσω της αναζήτησης σας
μπορούσα να δω τι θα μπορούσε να συνέβαινε αν προσπαθούσαμε
να προστεθεί στο τέλος της λίστας.
Επειδή δεν έχουμε ένα δείκτη στο τέλος της λίστας.
>> Έτσι, ο λόγος για τον οποίο θα ήθελα για να εισαγάγετε στην αρχή,
είναι γιατί μπορώ να το κάνω αμέσως.
Έχω ένα δείκτη στην αρχή, και θα δούμε αυτό σε μια οπτική σε ένα δευτερόλεπτο.
Αλλά αν θέλετε να εισάγετε στο τέλος, Πρέπει να ξεκινήσουμε από την αρχή,
διασχίζουν όλη τη διαδρομή προς το τέλος, και στη συνέχεια να το θέτει.
Έτσι, αυτό θα σήμαινε ότι εισάγοντας στο τέλος της λίστας
θα γίνει ο ν λειτουργία, πηγαίνοντας πίσω
στη συζήτησή μας της υπολογιστική πολυπλοκότητα.
Θα ήθελα να γίνει ένα o Ν λειτουργίας, όπου όπως η λίστα μεγάλωσε και μεγαλύτερες,
και μεγαλύτερα, αυτό θα γίνεται όλο και πιο δύσκολο να αναστρέψει κάτι
on στο τέλος.
Αλλά είναι πάντα πολύ εύκολο να καρφί κάτι από την αρχή,
είστε πάντα στην αρχή.
>> Και θα δούμε μια οπτική του ξανά.
Και στη συνέχεια, όταν θα τελειώσετε, μία φορά έχουμε εισαχθεί το νέο κόμβο,
θέλουμε να επιστρέψουμε στο δείκτη μας ο νέος επικεφαλής μιας συνδεδεμένης λίστας, η οποία
δεδομένου ότι είμαστε η εισαγωγή σε ξεκινώντας, θα είναι πράγματι
ένα δείκτη προς τον κόμβο που μόλις δημιουργήσαμε.
Ας απεικονίσει αυτό, γιατί πιστεύω ότι θα βοηθήσει.
>> Τόσο εδώ είναι λίστα μας, αποτελείται από τέσσερα στοιχεία, ένας κόμβος που περιέχει 15,
η οποία οδηγεί σε ένα κόμβο που περιέχουν 9, η οποία
επισημαίνει σε έναν κόμβο που περιέχει 13, η οποία οδηγεί σε ένα κόμβο που περιέχει
10, η οποία έχει την μηδενική δείκτη επόμενο δείκτης της
έτσι ώστε να είναι το τέλος της λίστας.
Έτσι θέλουμε να εισαγάγετε ένα νέος κόμβος με την τιμή 12
στην αρχή αυτού του λίστα, τι κάνουμε;
Λοιπόν, πρώτα malloc χώρο για την κόμβος, και στη συνέχεια βάζουμε 12 εκεί.
>> Έτσι τώρα έχουμε φτάσει ένα σημείο λήψης απόφασης, έτσι δεν είναι;
Έχουμε ένα ζευγάρι των δείκτες που θα μπορούσαμε να
κίνηση, η οποία θα πρέπει να προχωρήσουμε πρώτα;
Θα πρέπει να κάνουμε για να το σημείο 12 ο νέος επικεφαλής της list--
ή με συγχωρείτε, πρέπει να κάνουμε 12 επισημαίνουν την παλιά κεφαλή της λίστας;
Ή μήπως πρέπει να πούμε ότι η Λίστα τώρα αρχίζει στις 12.
Υπάρχει μια διάκριση εκεί, και θα εξετάσουμε
σε ό, τι συμβαίνει με τα δύο σε ένα δευτερόλεπτο.
>> Αλλά αυτό οδηγεί σε ένα μεγάλο θέμα για την πλαϊνή μπάρα,
η οποία είναι ότι ένα από τα δυσκολότερο πράγματα με συνδεδεμένες λίστες
είναι να οργανώσει τους δείκτες με τη σωστή σειρά.
Αν τα πράγματα κινούνται εκτός λειτουργίας, μπορείτε να καταλήξετε λάθος
ορφανούς το υπόλοιπο της λίστας.
Και εδώ είναι ένα παράδειγμα.
Έτσι, ας πάμε με την ιδέα of-- Λοιπόν, έχουμε δημιουργήσει μόλις 12.
Ξέρουμε 12 πρόκειται να είναι ο νέος επικεφαλής της λίστας,
και έτσι γιατί δεν μπορούμε απλά μετακινήστε ο δείκτης κατάλογο στο σημείο εκεί.
>> Εντάξει, έτσι ώστε να είναι καλή.
Έτσι τώρα, όπου κάνει 12 επόμενο σημείο;
Θέλω να πω, οπτικά μπορούμε να δούμε ότι θα δείχνει 15,
καθώς οι άνθρωποι είναι πραγματικά προφανές για μας.
Πώς ξέρει ο υπολογιστής;
Δεν έχουμε τίποτα που δείχνουν προς 15 πια, σωστά;
>> Έχουμε χάσει κάθε ικανότητα να αναφερθώ 15.
Δεν μπορούμε να πούμε νέα βέλος δίπλα ίσων κάτι, δεν υπάρχει τίποτα εκεί.
Στην πραγματικότητα, έχουμε μείνει ορφανά το υπόλοιπο της λίστας
με αυτόν τον τρόπο, έχουμε κατά λάθος σπάσει την αλυσίδα.
Και σίγουρα δεν θέλουμε να το κάνουμε αυτό.
>> Ας πάμε πίσω και δοκιμάστε ξανά.
Ίσως το σωστό πράγμα που κάνει είναι να βρίσκεται δίπλα του δείκτη 12
στην παλιά κεφαλή του πρώτου καταλόγου, τότε μπορούμε να προχωρήσουμε πάνω από τη λίστα.
Και στην πραγματικότητα, αυτή είναι η σωστή σειρά ώστε να
πρέπει να ακολουθήσουν όταν είμαστε σε συνεργασία με μεμονωμένα συνδεδεμένη λίστα.
Εμείς πάντα θέλουμε να συνδέσετε το νέο στοιχείο στη λίστα,
πριν πάρουμε αυτό το είδος του σημαντικό βήμα της αλλαγής
όπου ο επικεφαλής της συνδεδεμένης λίστας είναι.
Και πάλι, αυτό είναι ένα τέτοιο βασικό πράγμα, δεν θέλουμε να χαθούν τα ίχνη του.
>> Έτσι θέλουμε να βεβαιωθείτε ότι όλα δεμένους,
πριν προχωρήσουμε αυτό το δείκτη.
Και έτσι αυτό θα ήταν η σωστή σειρά, η οποία είναι η σύνδεση 12 στη λίστα,
τότε λένε ότι ο κατάλογος ξεκινά μια 12.
Αν λέγαμε η λίστα ξεκινά στις 12 και Στη συνέχεια προσπάθησε να συνδέσει 12 στον κατάλογο,
έχουμε ήδη δει τι συμβαίνει.
Χάνουμε τη λίστα κατά λάθος.
>> Εντάξει, έτσι ένα ακόμη πράγμα που πρέπει να συζητήσουμε.
Τι γίνεται αν θέλουμε να απαλλαγούμε από μια ολόκληρη συνδεδεμένη λίστα με τη μία;
Και πάλι, είμαστε mallocing όλα αυτά χώρο, και έτσι
Πρέπει να την απελευθερώσει όταν τελειώσουμε.
Έτσι, τώρα θέλουμε να διαγράψετε ολόκληρη η συνδεδεμένη λίστα.
Λοιπόν, τι θέλουμε να κάνουμε;
>> Αν έχουμε φτάσει στο null pointer, θέλουν να σταματήσουν, αλλιώς, απλά να διαγράψετε
το υπόλοιπο της λίστας και, στη συνέχεια, με ελευθερώσει.
Διαγράψτε το υπόλοιπο του καταλόγου, και στη συνέχεια ελευθερώσει την τρέχοντα κόμβο.
Τι κάνει αυτό ακούγεται σαν, ποια τεχνική έχει μιλήσαμε
περίπου στο παρελθόν Μήπως αυτό ακούγεται σαν;
Διαγραφή όλοι οι άλλοι, τότε έρχονται πίσω και να διαγράψετε μου.
>> Αυτό είναι αναδρομή, κάναμε το πρόβλημα λίγο μικρότερο,
λέμε να διαγράψετε όλους άλλο, τότε μπορείτε να μου διαγράψετε.
Και περαιτέρω κάτω από το δρόμο, ο κόμβος Θα πω, διαγράψτε όλους τους άλλους.
Αλλά τελικά θα φτάσουμε το σημείο όπου η λίστα είναι μηδενική,
και αυτό είναι βασικό μας.
>> Έτσι, ας ρίξουμε μια ματιά σε αυτό, και πώς αυτό θα μπορούσε να λειτουργήσει.
Τόσο εδώ είναι λίστα μας, είναι το ίδιο λίστα ήμασταν ακριβώς μιλάμε,
και εκεί τα βήματα.
Υπάρχει πολλή κειμένου εδώ, αλλά ελπίζουμε ότι η οπτικοποίηση θα βοηθήσει.
>> Γι 'αυτό και have-- και εγώ, επίσης, τράβηξε μέχρι καρέ stack μας εικόνα
το βίντεο σχετικά με στοίβες κλήση, και ελπίζουμε ότι όλα αυτά
μαζί θα σας δείξει τι συμβαίνει.
Τόσο εδώ είναι ψευδοκώδικας κωδικό μας.
Αν φτάσουμε σε μηδενική δείκτης, να σταματήσει, διαφορετικά,
θα διαγράψει το υπόλοιπο της λίστας, να ελευθερώσετε τον τρέχοντα κόμβο.
Έτσι τώρα, list-- ο δείκτης που είμαστε
περνώντας να καταστρέψει σημεία 12.
12 δεν είναι ένα κενό δείκτη, έτσι είμαστε πρόκειται να διαγράψει το υπόλοιπο της λίστας.
>> Ποια είναι η διαγραφή εμάς τους υπόλοιπους που συμμετέχουν;
Λοιπόν, αυτό σημαίνει ότι κάνοντας μια καλούν να καταστρέψει, λέγοντας
ότι το 15 είναι η αρχή της υπόλοιπο της λίστας θέλουμε να καταστρέψουμε.
Και έτσι η κλήση για την καταστροφή 12 είναι το είδος του σε αναμονή.
Είναι παγώσει εκεί, περιμένοντας για το καλούν να καταστρέψει 15, για να τελειώσει τη δουλειά του.
>> Λοιπόν, 15 δεν είναι ένα κενό δείκτη, και γι 'αυτό πρόκειται να πω, εντάξει,
καλά, διαγράψτε το υπόλοιπο της λίστας.
Το υπόλοιπο της λίστας ξεκινά στις 9, και έτσι απλά θα
περιμένετε μέχρι να διαγράψετε όλα ότι πράγματα, στη συνέχεια να επανέλθει και να διαγράψει εμένα.
Καλά 9 πρόκειται να πείτε, καλά, Δεν είμαι ένα μηδενικό δείκτη,
έτσι θα διαγράψει το υπόλοιπο της λίστας από εδώ.
Και έτσι πρέπει να δοκιμάσετε και να καταστρέψουν 13.
13 λέει, δεν είμαι κενό δείκτη, ίδιο πράγμα, το μεταθέτει.
10 δεν είναι null pointer, 10 περιέχει ένα κενό δείκτη,
αλλά 10 δεν είναι η ίδια null pointer τώρα,
και γι 'αυτό το μεταθέτει πάρα πολύ.
>> Και τώρα απαριθμήσει τα σημεία εκεί, πραγματικά θα ήθελε να some--
αν είχα περισσότερο χώρο στην εικόνα, θα επισημάνω κάποια τυχαία χώρο
ότι δεν ξέρουμε τι είναι.
Είναι το κενό δείκτη όμως, η λίστα είναι κυριολεκτικά τώρα είναι τιμές null.
Είναι που δείχνει δεξιά μέσα σε αυτό το κόκκινο κουτί.
Έχουμε φτάσει σε ένα κενό δείκτη, έτσι μπορούμε να σταματήσουμε, και τελειώσατε.
>> Και έτσι ώστε μοβ πλαίσιο είναι now-- κατά τη κορυφή της stack-- που είναι το ενεργό πλαίσιο,
αλλά έχει κάνει.
Αν έχουμε φτάσει σε ένα κενό δείκτη, να σταματήσει.
Εμείς δεν κάνουμε τίποτα, δεν μπορούν να απελευθερώσουν ένα κενό δείκτη,
δεν είχαμε οποιαδήποτε malloc χώρο, και έτσι τελειώσαμε.
Έτσι αυτό το πλαίσιο λειτουργίας καταστρέφεται, και εμείς
resume-- έχουμε πάρει όπου είχαμε μείνει μακριά με το επόμενο υψηλότερο, το οποιο
Είναι αυτό το σκούρο μπλε πλαίσιο εδώ.
Έτσι παίρνουμε δεξιά όπου φύγαμε μακριά.
Θα διαγραφεί το υπόλοιπο του λίστα ήδη, έτσι και τώρα είμαστε
πρόκειται να απελευθερώσει τις τρέχουσες κόμβους.
Έτσι τώρα μπορούμε να ελευθερώσουμε τον κόμβο αυτό, και τώρα έχουμε φτάσει στο τέλος της λειτουργίας.
Και έτσι ώστε το πλαίσιο λειτουργίας καταστρέφεται, και εμείς pick up στο φως μπλε.
>> Γι 'αυτό says-- έχω ήδη done-- διαγράφοντας το υπόλοιπο της λίστας, έτσι
απελευθερώσει το τρέχοντα κόμβο.
Και τώρα το κίτρινο πλαίσιο είναι πίσω στην κορυφή της στοίβας.
Και έτσι όπως βλέπετε, είμαστε τώρα καταστρέφοντας τη λίστα από δεξιά προς τα αριστερά.
>> Τι θα είχε συμβεί, αν και, αν είχαμε κάνει τα πράγματα με λάθος τρόπο;
Ακριβώς όπως όταν προσπαθήσαμε για να προσθέσετε ένα στοιχείο.
Αν μπέρδεμα της αλυσίδας, εφόσον δεν είχαμε συνδέσει τις υποδείξεις
με τη σωστή σειρά, αν θέλουμε απλά ελευθέρωσε το πρώτο στοιχείο,
αν θέλουμε απλά να απελευθερωθεί η επικεφαλής της λίστας, τώρα
δεν έχουν τρόπο να αναφερθώ το υπόλοιπο της λίστας.
Και έτσι θα έχουμε ορφανά τα πάντα,
θα είχαμε ό, τι είναι ονομάζεται διαρροή μνήμης.
Αν θυμάστε από το βίντεο μας για δυναμική κατανομή μνήμης,
αυτό δεν είναι πολύ καλό πράγμα.
>> Έτσι, όπως είπα, υπάρχει είναι αρκετές λειτουργίες
ότι πρέπει να χρησιμοποιήσουμε για να εργαστούν με συνδεθεί αποτελεσματικά λίστα.
Και μπορεί να έχετε παρατηρήσει έχω παραλείψει ένα, Διαγραφή ενός στοιχείου από ένα συνδεδεμένο
κατάλογο.
Ο λόγος που το έκανε αυτό είναι στην πραγματικότητα το είδος του
δύσκολο να σκεφτούμε πώς να διαγράψετε ένα ενιαίο στοιχείο από μεμονωμένα
συνδεδεμένη λίστα.
Πρέπει να είμαστε σε θέση να υπερπηδήσει κάτι στη λίστα, η οποία
σημαίνει να πάμε σε μια point-- μας θέλετε να διαγράψετε αυτό το node--
αλλά για να το κάνει έτσι δεν χάνουν καμία πληροφορία,
θα πρέπει να συνδέσετε αυτό κόμβος εδώ, εδώ.
>> Γι 'αυτό ίσως να έκανε λάθος ότι από οπτικής απόψεως.
Έτσι είμαστε στην αρχή μας κατάλογο, είμαστε προχωρά μέσω,
που θέλετε να διαγράψετε αυτό το κόμβο.
Αν θέλουμε απλά να το διαγράψετε, έχουμε σπάσει την αλυσίδα.
Αυτός ο κόμβος εδώ αναφέρεται σε οτιδήποτε άλλο,
περιέχει την αλυσίδα από εδώ και πέρα.
>> Έτσι, αυτό που πρέπει να κάνουμε πραγματικότητα αφού φτάσει σε αυτό το σημείο,
είναι ότι πρέπει να κάνουν ένα βήμα πίσω ένα, και συνδέστε τον κόμβο αυτό πάνω σε αυτόν τον κόμβο,
έτσι ώστε να μπορέσουμε στη συνέχεια να διαγράψετε το ένα στη μέση.
Αλλά απλά συνδεδεμένες λίστες δεν μας παρέχουν έναν τρόπο για να πάει προς τα πίσω.
Γι 'αυτό πρέπει είτε να κρατήσει δίποντα, και να τους μετακινεί
το είδος των off βήμα, το ένα πίσω από το άλλα, όπως πάμε, ή να φτάσουμε σε ένα σημείο
και στη συνέχεια να στείλει ένα άλλο δείκτη μέσα.
Και όπως μπορείτε να δείτε, μπορεί να πάρει λίγο βρώμικο.
Ευτυχώς, έχουμε Ένας άλλος τρόπος για την επίλυση ότι,
όταν μιλάμε για διπλά συνδεδεμένες λίστες.
>> Είμαι ο Νταγκ Lloyd, αυτό είναι CS50.