[ΜΟΥΣΙΚΗ ΠΑΙΖΟΝΤΑΣ] DAVID J. MALAN: Εντάξει. Αυτό είναι CS50. Αυτή είναι η εβδομάδα των πέντε συνεχιστεί, και εμείς έχουμε κάποια καλά νέα και άσχημα νέα. Έτσι, τα καλά νέα είναι ότι το CS50 ξεκινά την ερχόμενη Παρασκευή. Αν θα θέλατε να ενωθούν μαζί μας, κατευθυνθείτε προς το συνηθισμένο URL εδώ. Ακόμα καλύτερα νέα, καμία διάλεξη την ερχόμενη Δευτέρα 13 του μηνός. Ελαφρώς λιγότερο καλύτερα νέα, κουίζ μηδέν είναι την επόμενη Τετάρτη. Περισσότερες λεπτομέρειες μπορούν να βρέθηκαν σε αυτό το URL εδώ. Και κατά τη διάρκεια των επόμενων δύο ημερών θα πρέπει να συμπληρώσετε τα κενά σε σχέση με τις αίθουσες ότι θα έχουμε διατηρούνται. Η καλύτερη είδηση ​​είναι ότι θα υπάρχει είναι μια ανασκόπηση πορεία σε ολόκληρη την συνεδρία την ερχόμενη Δευτέρα το βράδυ. Μείνετε συντονισμένοι με την πορεία του ιστοσελίδα για την τοποθεσία και τις λεπτομέρειες. Τμήματα, έστω και αν είναι ένα διακοπές, θα συναντηθεί, επίσης, καθώς και. Best news, διάλεξη την επόμενη Παρασκευή. Έτσι, αυτό είναι μια παράδοση που έχουν, σύμφωνα με την εξεταστέα ύλη. Μόνο-- πρόκειται να είναι καταπληκτικό. Θα δείτε τα πράγματα όπως δομών δεδομένων σταθερό χρόνο και πίνακες κατακερματισμού και δέντρα και προσπαθεί. Και θα μιλήσουμε για τα προβλήματα γενεθλίων. Ένα σωρό πράγματα περιμένει την επόμενη Παρασκευή. OK. Εν πάση περιπτώσει. Έτσι, υπενθυμίζουν ότι έχουμε πάει εστιάζοντας σε αυτή την εικόνα για το τι είναι μέσα από τη μνήμη του υπολογιστή μας. Έτσι, μνήμη RAM ή είναι όπου τα προγράμματα Υπάρχουν ενώ είστε τους λειτουργία. Αν κάνετε διπλό κλικ σε μια εικονίδιο για να τρέξει κάποιο πρόγραμμα ή κάντε διπλό κλικ σε ένα εικονίδιο για να ανοίξετε κάποιο αρχείο, είναι φορτωμένο από το σκληρό σας οδηγείτε ή μονάδα στερεάς κατάστασης στη μνήμη RAM, Random Access Memory, όπου ζει μέχρι να σβήσει, το lap-top καπάκι κλείνει, ή να κλείσετε το πρόγραμμα. 

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

Έτσι, όταν κάνετε διπλό κλικ Microsoft Word για Mac ή το PC σας, ή όταν εκτελείτε dot κάθετο Mario σε μια Linux υπολογιστή στο παράθυρο του τερματικού σας, τα μηδενικά και αυτά που συνθέτουν Word ή Mario αποθηκεύονται προσωρινά στη μνήμη RAM του υπολογιστή σας στο λεγόμενο τμήμα κειμένου για ένα συγκεκριμένο πρόγραμμα. Κάτω από αυτό πηγαίνει προετοιμασία και έχει προετοιμαστεί δεδομένων. Αυτό είναι τα πράγματα όπως καθολικές μεταβλητές, ότι δεν έχω χρησιμοποιήσει πολλές από τις, αλλά σε ορισμένες περιπτώσεις έχουμε είχε καθολικές μεταβλητές ή στατικά ορίζονται χορδές ότι είναι σκληρό κωδικοποιημένες λέξεις όπως "γεια" που δεν λαμβάνονται από τον χρήστη που είναι σκληρό κωδικοποιούνται στο πρόγραμμά σας. 

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

ΚΟΙΝΟ: Λειτουργίες. 

DAVID J. MALAN: Για λειτουργίες; Με ποια έννοια για τις λειτουργίες; 

ΚΟΙΝΟ: Όταν καλείτε μια συνάρτηση, η Τα επιχειρήματα που αντιγράφονται στη στοίβα. 

DAVID J. MALAN: Ακριβώς. Όταν καλείτε μια συνάρτηση, της Τα επιχειρήματα που αντιγράφονται στη στοίβα. Έτσι, κάθε Χ ή Υ ή Α ή Β ότι είστε περνώντας σε λειτουργία Τα προσωρινά τεθεί σε η λεγόμενη στοίβα, όπως ακριβώς ένας από τους Annenberg τραπεζαρία δίσκοι αίθουσα, και επίσης τα πράγματα όπως οι τοπικές μεταβλητές. Εάν η λειτουργία foo σας ή μετάθεσης λειτουργία έχουν τοπικές μεταβλητές, όπως η θερμοκρασία, τα δύο αυτά καταλήγουν στη στοίβα. Τώρα, εμείς δεν θα μιλήσουμε πολύ για τους, αλλά αυτές οι μεταβλητές περιβάλλοντος στο κάτω μέρος είδαμε πριν από λίγο καιρό, όταν Ήμουν futzing στο πληκτρολόγιο μία ημέρα και άρχισα πρόσβαση σε πράγματα όπως argv 100 ή argv 1000, Απλά elements-- ξεχάσω η numbers-- αλλά ότι δεν θα έπρεπε να είναι προσβάσιμες από εμένα. Αρχίσαμε να βλέπουμε κάποια funky σύμβολα που εμφανίζονται στην οθόνη. Αυτοί ήταν λεγόμενες μεταβλητές περιβάλλοντος όπως η παγκόσμια ρυθμίσεις για μου πρόγραμμα ή για τον υπολογιστή μου, δεν άσχετα με την πρόσφατη bug που συζητήσαμε, Shellshock, αυτό ήταν μαστίζουν αρκετά υπολογιστές. 

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

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

Έτσι, ανεξάρτητα από λέξη που πληκτρολογεί ο χρήστης στο η γραμμή μετά το όνομα αυτού του προγράμματος, και, στη συνέχεια, αυτή η αυθαίρετη λειτουργία επάνω κορυφή, στ, παίρνει σε μια σειρά, AKA char *, όπως έχουμε αρχίσει να συζητούν, και αυτό που αποκαλεί απλά "bar." Αλλά θα μπορούσαμε να το ονομάσουμε τίποτα. Και τότε δηλώνει, στο εσωτερικό της f, μια σειρά από χαρακτήρες ονομάζεται c-- 12 τέτοιες χαρακτήρες. 

Τώρα, με την ιστορία που έλεγε Πριν από ένα χρόνο, όπου στη μνήμη είναι c, ή είναι αυτοί 12 χαρακτ πρόκειται να καταλήξετε; Ακριβώς για να είναι σαφής. Ναι; 

ΚΟΙΝΟ: Στο στοίβα. 

DAVID J. MALAN: Από την στοίβα. Έτσι c είναι μια τοπική μεταβλητή. Ζητάμε από 12 χαρακτήρες ή 12 bytes. Όσοι πρόκειται να καταλήξετε σχετικά με το λεγόμενο στοίβα. Τώρα είναι επιτέλους αυτή η άλλη λειτουργία αυτό είναι πραγματικά αρκετά χρήσιμο, αλλά δεν έχω χρησιμοποιήσει πραγματικά μόνοι μας, strncopy. Σημαίνει αντίγραφο εγχόρδων, αλλά μόνο γράμματα n, n χαρακτήρες. Έτσι, n χαρακτήρες θα είναι αντιγραφεί από το μπαρ σε c. Και πόσα; Το μήκος της ράβδου. Έτσι με άλλα λόγια, ότι μία γραμμή, strncopy, πρόκειται να αντιγράψετε αποτελεσματικά μπαρ για να γ. 

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

ΚΟΙΝΟ: Δεν περιλαμβάνονται δωμάτιο για το null χαρακτήρα. DAVID J. MALAN: Δεν περιλαμβάνονται δωμάτιο για το null χαρακτήρα. Δυνητικά, σε αντίθεση πρακτικές του παρελθόντος δεν το κάνουμε, ακόμη και έχουν τόσο πολύ ως συν 1 φιλοξενήσει αυτό το null χαρακτήρα. Αλλά αυτό είναι ακόμα χειρότερο από αυτό. Τι άλλο μπορούμε παραλείποντας να κάνουμε; Ναι; 

ΚΟΙΝΟ: [δεν ακούγεται] DAVID J. MALAN: Perfect. Έχουμε σκληρά κωδικοποιημένους 12 αρκετά αυθαίρετα. Αυτό δεν είναι τόσο η πρόβλημα, αλλά το γεγονός ότι δεν είμαστε καν να ελέγχει εάν το μήκος της ράβδου είναι μικρότερο από 12, περίπτωση κατά την οποία πρόκειται να ασφαλές για να το θέσω στη μνήμη που ονομάζεται c που έχουμε διατεθεί. Πράγματι, εάν το μπαρ είναι σαν 20 χαρακτήρες, η λειτουργία αυτή φαίνεται να αντιγραφή 20 χαρακτήρες από το μπαρ σε c, έτσι λαμβάνοντας τουλάχιστον 8 bytes ότι δεν πρέπει να είναι. Αυτό είναι το συμπέρασμα εδώ. 

Έτσι, με λίγα λόγια, σπασμένα πρόγραμμα. Δεν είναι μια τέτοια μεγάλη υπόθεση. Ίσως μπορείτε να πάρετε ένα σφάλμα κατάτμησης. Έχουμε όλοι είχαν σφάλματα στα προγράμματα. Όλοι μας μπορεί να έχει σφάλματα σε προγράμματα τώρα. Αλλά ποια είναι η επίπτωση; Λοιπόν, εδώ είναι ένα μεγεθυσμένο στην έκδοση της ότι η εικόνα της μνήμης του υπολογιστή μου. Αυτό είναι το κάτω μέρος της στοίβας μου. Και πράγματι, στο κάτω μέρος είναι ό, τι είναι που ονομάζεται μητρική ρουτίνα στοίβα, φανταχτερό τρόπο του λέγοντας ότι είναι κύριος. Έτσι ώστε όποιος καλείται η συνάρτηση f που μιλάμε. Έτσι, αυτό είναι το κάτω μέρος της στοίβας. Η διεύθυνση επιστροφής είναι κάτι νέο. Είναι πάντα εκεί, πάντα σε αυτήν την εικόνα. Εμείς απλά δεν επέστησε την προσοχή σε αυτό. Επειδή αποδεικνύεται ο τρόπος c λειτουργεί είναι ότι όταν μία λειτουργία καλεί άλλη, όχι μόνο κάνουν τα επιχειρήματα που λειτουργία να ωθείται στη στοίβα, όχι μόνο οι τοπικές η λειτουργία του μεταβλητές πάρει έσπρωξε στη στοίβα, κάτι που ονομάζεται διεύθυνση επιστροφής παίρνει επίσης να θέσει στη στοίβα. Συγκεκριμένα, αν η κύρια κλήσεις foo, κύρια του δική του διεύθυνση στη μνήμη, βόδι κάτι, αποτελεσματικά παίρνει θέσει στη στοίβα έτσι ώστε όταν f γίνεται από την εκτέλεση του ξέρει πού να πηδήσει πίσω στο κείμενο τμήμα, προκειμένου να συνεχίσει την εκτέλεση. 

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

Αλλά ο τρόπος υπολογιστές εδώ και καιρό που τα πράγματα όπως οι τοπικές μεταβλητές και επιχειρήματα είναι σαν αυτό. Έτσι, στην κορυφή αυτής της εικόνας σε το μπλε είναι το πλαίσιο στοίβας για f, έτσι ώστε όλα της μνήμης ότι f Συγκεκριμένα χρησιμοποιεί. Έτσι, κατά συνέπεια, παρατηρούμε ότι bar είναι σε αυτή την εικόνα. Bar ήταν το επιχείρημά του. Και υποστήριξε ότι τα επιχειρήματα για να λειτουργίες να ωθείται στη στοίβα. Και c, φυσικά, είναι Επίσης, σε αυτή την εικόνα. 

Και μόνο για συμβολισμούς σκοπούς, παρατηρήσετε στο πάνω αριστερή γωνία είναι αυτό που θα ήταν γ υποστήριγμα 0 και Στη συνέχεια ελαφρώς προς τα κάτω προς τα δεξιά είναι c βραχίονα 11. Έτσι, με άλλα λόγια, μπορείτε να φανταστείτε ότι υπάρχει ένα πλέγμα από bytes εκεί, πρώτο εκ των οποίων είναι πάνω αριστερά, κάτω από το οποίο είναι η τελευταία από τις 12 bytes. 

Αλλά τώρα προσπαθούν να προχωρήσετε μπροστά. Τι πρόκειται να συμβεί, αν περνάμε σε μια γραμμή κορδόνι που είναι περισσότερο από c; Και δεν είμαστε ελέγχοντας αν Είναι πράγματι περισσότερο από 12. Ποιο μέρος αυτής της εικόνας θα να αντικατασταθούν από bytes 0, 1, 2, 3, dot dot dot, 11, και έπειτα κακή, 12, 13 έως 19? Τι πρόκειται να συμβεί εδώ, αν συμπεράνουμε από την παραγγελία ότι ο βραχίονας είναι 0 στην κορυφή και γ βραχίονα 11 είναι είδος προς τα κάτω προς τα δεξιά; Ναι; 

ΚΟΙΝΟ: Λοιπόν, πρόκειται να αντικαταστήσετε τη γραμμή char *. 

DAVID J. MALAN: Ναι, μοιάζει θα πάμε να αντικαταστήσετε char * μπαρ. Και το χειρότερο, αν σας στείλουν σε ένα πραγματικά μεγάλο string, θα μπορούσε να αντικαταστήσει ακόμη και τι; Η διεύθυνση επιστροφής. Πράγμα που και πάλι, είναι ακριβώς όπως ένα τριμμένη φρυγανιά για να πει το πρόγραμμα που να πάει πίσω όταν f γίνεται να ονομάζεται. 

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

Μόλις κολλάει το πρόγραμμά σας, αυτό είναι ένα καταπληκτικό πράγμα. Επειδή αυτό σημαίνει ότι ή έχει ανακαλύψει τι είναι πιθανόν πράγματι ένα bug. Και τότε μπορεί να πάρει πιο έξυπνοι και να αρχίσει εστιάζοντας περισσότερο στενά σχετικά με το πώς να εκμεταλλευτούν αυτό το bug. Συγκεκριμένα, τι αυτός ή αυτή θα μπορούσε κάνετε είναι να στείλετε, στην καλύτερη περίπτωση, γεια σου. Δεν είναι μεγάλη υπόθεση. Είναι μια σειρά που είναι αρκετά σύντομη. Αλλά ό, τι και αν αυτός ή αυτή στέλνει, και εμείς θα το γενικεύσουμε, όπως, επίθεση code-- έτσι μηδενικά και αυτά που κάνουμε τα πράγματα όπως rm-rf, που απομακρύνουν τα πάντα από τον σκληρό δίσκο ή να στείλει spam ή με κάποιο τρόπο επιτεθεί το μηχάνημα; 

Έτσι, αν κάθε ένα από αυτά γράμματα Α αντιπροσωπεύει ακριβώς, εννοιολογικά, επίθεση, επίθεση, επίθεση, επίθεση, μερικές κακές κώδικα ότι κάποιος άλλος έγραψε, αλλά αν το πρόσωπο αυτό είναι αρκετά έξυπνος όχι μόνο να περιλαμβάνει όλα αυτών rm-RFS, αλλά επίσης έχουν τελευταία bytes του ή της είναι ένας αριθμός που αντιστοιχεί στη διεύθυνση του του ή το δικό της κώδικα επίθεσης ότι αυτός ή αυτή πέρασε σε μόλις παρέχοντας τη στη γραμμή, μπορείτε να ξεγελάσουν αποτελεσματικά τον υπολογιστή σε παρατηρήσει όταν f γίνεται η εκτέλεση, Ω, ήρθε η ώρα για μένα να πηδήξει πίσω στην κόκκινη διεύθυνση επιστροφής. Αλλά γιατί αυτός ή αυτή έχει κάπως επικαλύπτονται ότι η διεύθυνση επιστροφής με το δικό τους αριθμό, και είναι αρκετά έξυπνος να έχουν διαμορφωθεί ότι αριθμός να αναφερθώ, όπως σας δείτε το super top αριστερή γωνία εκεί, η πραγματική διεύθυνση του υπολογιστή μνήμη ορισμένων από κώδικα επίθεσης τους, κακός μπορεί να ξεγελάσουν τον υπολογιστή σε εκτέλεση δική του κώδικα. 

Και ότι ο κώδικας, και πάλι, μπορεί να είναι οτιδήποτε. Είναι γενικά ονομάζεται Κωδικός κέλυφος, το οποίο είναι ακριβώς ένας τρόπος για να πούμε ότι δεν είναι γενικά κάτι τόσο απλό όπως rm-rf. Είναι πραγματικά κάτι σαν Bash, ή ένα πραγματικό πρόγραμμα που του δίνει ή προγραμματικό έλεγχο της να εκτελέσει οτιδήποτε άλλο που θέλουν να. Έτσι, με λίγα λόγια, όλα αυτά απορρέει από το απλό γεγονός ότι αυτό το bug που εμπλέκονται όχι έλεγχο τα όρια του πίνακα σας. Και επειδή ο τρόπος υπολογιστές εργασίας είναι ότι χρησιμοποιούν τη στοίβα από αποτελεσματικά, εννοιολογικά, πυθμένα επάνω, αλλά στη συνέχεια τα στοιχεία ωθείτε επάνω στη στοίβα αυξηθεί πάνω προς τα κάτω, αυτό είναι εξαιρετικά προβληματικό. Τώρα, υπάρχουν τρόποι για να αντιμετωπίσετε αυτό. Και ειλικρινά, υπάρχουν γλώσσες με την οποία να επιλύσετε αυτό. Java είναι το ανοσοποιητικό, για παράδειγμα, για το συγκεκριμένο θέμα. Επειδή δεν σας δίνουν υποδείξεις. Δεν σας δώσει άμεση διευθύνσεις μνήμης. Έτσι, με αυτή τη δύναμη που έχουμε να αγγίξει τίποτα στη μνήμη που θέλετε έρχεται, ομολογουμένως, μεγάλο κίνδυνο. 

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

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

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

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

Τώρα, το αντίστροφο της malloc είναι δωρεάν. Και πράγματι, ο κανόνας σας πρέπει να αρχίσει την έγκριση είναι κάποια, οποιαδήποτε, κάθε φορά που χρησιμοποιείτε malloc θα πρέπει να τον εαυτό σας να χρησιμοποιήσετε δωρεάν, τελικά, σε αυτό το ίδιο δείκτη. Όλο αυτό το διάστημα έχουμε γράψει buggy, προβληματικό κώδικα, για πολλούς λόγους. Αλλά ένα από τα οποία έχει χρησιμοποιώντας τη βιβλιοθήκη CS50, η οποία το ίδιο είναι σκόπιμα buggy, είναι διαρροών μνήμης. Κάθε φορά που έχετε ονομάσει GetString κατά τη διάρκεια των τελευταίων εβδομάδων ζητάμε από το λειτουργικό συστήματος, το Linux, για τη μνήμη. Και έχετε ποτέ τη στιγμή που θα δοθεί πίσω. Και αυτό δεν είναι, σε πρακτική, ένα καλό πράγμα. 

Και Valgrind, ένα από τα εργαλείων που έχουν εισαχθεί στο Pset 4, είναι όλα για να σας βοηθήσει να τώρα βρείτε σφάλματα όπως αυτό. Αλλά ευτυχώς για Pset 4 δεν χρειάζεται να χρησιμοποιούν τη βιβλιοθήκη CS50 ή GetString. Έτσι, τυχόν σφάλματα που σχετίζονται με τη μνήμη είναι τελικά, θα είναι δική σας. 

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

Έτσι, μια σειρά έμοιαζε με αυτό. Και αυτό ήταν το κλειδί σε περίπου ένα array είναι ότι σας δίνει back-to-back κομμάτια της μνήμη, καθεμία από τις οποίες πρόκειται να είναι του ίδιου τύπου, int, int, int, int, ή char, char, char, char. Αλλά υπάρχουν μερικά μειονεκτήματα. Αυτό, για παράδειγμα, είναι μια σειρά από έξι μέγεθος. Ας υποθέσουμε ότι μπορείτε να συμπληρώσετε αυτό το array με έξι αριθμών και, στη συνέχεια, για οποιουσδήποτε λόγους, χρήστη σας θέλει να δώσει έχετε ένα έβδομο αριθμό. Πού έχεις βάλει; 

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

ΚΟΙΝΟ: [δεν ακούγεται] 

DAVID J. MALAN: Συγγνώμη; 

ΚΟΙΝΟ: Βάλτε το στην άκρη. 

DAVID J. MALAN: Βάλτε το στην άκρη. Έτσι ακριβώς πάνω προς τα δεξιά, έξω από το παράθυρο. Ποια θα ήταν ωραίο, αλλά Αποδεικνύεται ότι δεν μπορεί να το κάνει. Διότι, αν δεν έχετε ζητήσει γι 'αυτό το κομμάτι της μνήμης, θα μπορούσε να είναι τυχαίο ότι αυτή η χρησιμοποιείται από κάποια άλλη μεταβλητή συνολικά. Σκεφτείτε μια εβδομάδα ή έτσι, όταν εμείς που τα ονόματα Zamyla και Davin και Gabe του στη μνήμη. Ήταν κυριολεκτικά πλάτη με πλάτη με πλάτη. Έτσι, δεν μπορούμε απαραιτήτως εμπιστοσύνη ότι όποιες και αν είναι εδώ είναι διαθέσιμα για να τα χρησιμοποιήσετε. 

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

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

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

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

Τι κι αν, αντί της ακριβώς την αποθήκευση των αριθμών, όπως 9, 17, 22, 26, 34, τι θα γινόταν αν δεν αποθηκεύονται μόνο ένας αριθμός, αλλά ένας δείκτης δίπλα σε κάθε τέτοιο αριθμό; Έτσι, τόσο πολύ όπως θα περάστε ένα βελόνα μέσα από ένα σωρό από ύφασμα, κάπως δέσιμο πράγματα μαζί, παρομοίως μπορεί εμείς με δείκτες, όπως ενσαρκώνεται από βέλη εδώ, το είδος της ύφανσης μαζί αυτά τα ορθογώνια παραλληλόγραμμα με την αποτελεσματική χρήση ενός δείκτη δίπλα σε κάθε αριθμό στον οποίο επισημαίνει σε κάποιο επόμενο αριθμό, ότι επισημαίνει, με τη σειρά τους, ορισμένες επόμενο αριθμό; Έτσι, με άλλα λόγια, ό, τι αν πραγματικά θέλαμε να εφαρμόσει κάτι σαν αυτό; Καλά Δυστυχώς, αυτές ορθογώνια, τουλάχιστον το ένα με 9, 17, 22, και ούτω καθεξής, αυτά δεν είναι πλέον ωραίο πλατείες με μόνο αριθμούς. Το κάτω μέρος, ορθογώνιο κάτω 9, για παράδειγμα, αντιπροσωπεύει αυτό που θα πρέπει να είναι ένας δείκτης, 32 bits. Τώρα, δεν είμαι ακόμα γνωρίζουν κάθε τύπο δεδομένων σε C που σας δίνει όχι μόνο μια int αλλά ένας δείκτης εντελώς. 

Έτσι ποια είναι η λύση, αν θέλουμε να εφεύρουν τη δική μας απάντηση σε αυτό; Ναι; 

ΚΟΙΝΟ: [δεν ακούγεται] 

DAVID J. MALAN: Τι είναι αυτό; 

ΚΟΙΝΟ: Νέα δομή. 

DAVID J. MALAN: Ναι, οπότε γιατί Δεν έχουμε δημιουργήσει μια νέα δομή, ή σε C, ένα struct; Έχουμε δει structs πριν, αν εν συντομία, όπου ασχοληθήκαμε με μια δομή φοιτητή όπως αυτός, ο οποίος είχε ένα όνομα και ένα σπίτι. Σε Pset 3 ξεμπλοκάρισμα χρησιμοποιήσατε μια ολόκληρη μάτσο structs-- GRect και GOvals ότι Στάνφορντ που δημιουργήθηκε για να cluster πληροφορίες μαζί. Έτσι, ό, τι και αν πάρουμε την ίδια την ιδέα της οι λέξεις-κλειδιά "typedef" και "struct" και στη συνέχεια κάποιες φοιτητή-ειδικά πράγματα, και να εξελιχθεί αυτή στο εξής: typedef struct node-- και ο κόμβος είναι μόνο μια πολύ γενική επιστήμη των υπολογιστών όρος για κάτι σε μια δομή δεδομένων, ένα δοχείο σε μια δομή δεδομένων. Ένας κόμβος που ισχυρίζονται πρόκειται να έχουν ένα int n, εντελώς απλή, και στη συνέχεια λίγο πιο κρυφά, αυτή η δεύτερη γραμμή, struct node * επόμενο. Αλλά σε λιγότερο τεχνικούς όρους, τι είναι η δεύτερη γραμμή του κώδικα μέσα στα άγκιστρα; Ναι; 

ΚΟΙΝΟ: [δεν ακούγεται] DAVID J. MALAN: A δείκτη σε άλλο κόμβο. Έτσι, κατά γενική ομολογία, την σύνταξη λίγο αινιγματικό. Αλλά αν το διαβάσετε κυριολεκτικά, επόμενο είναι το όνομα μιας μεταβλητής. Τι είναι ο τύπος δεδομένων του; Είναι λίγο φλύαρο αυτή τη φορά, αλλά είναι του τύπου struct node *. Κάθε φορά που έχουμε δει κάτι αστέρων, ότι σημαίνει ότι είναι ένας δείκτης για το συγκεκριμένο τύπο δεδομένων. Μέχρι την επόμενη είναι προφανώς ένα δείκτης σε μια struct node. 

Τώρα, τι είναι ένας κόμβος struct; Λοιπόν, παρατηρήσετε θα δείτε εκείνες ίδιες λέξεις στην πάνω δεξιά. Και πράγματι, θα δείτε επίσης τη λέξη "Κόμβος" εδώ κάτω στο κάτω μέρος αριστερά. Και αυτό είναι στην πραγματικότητα μια ευκολία. Παρατηρήστε ότι στον ορισμό των φοιτητών μας υπάρχει η λέξη "σπουδαστής" μόνο μία φορά. Και αυτό γιατί ένα μαθητή αντικείμενο δεν ήταν αυτοαναφορική. Δεν υπάρχει τίποτα στο εσωτερικό του φοιτητή ότι πρέπει να επισημάνω ένα άλλο μαθητή, PerSay. Αυτό θα είναι το είδος της παράξενο στον πραγματικό κόσμο. 

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

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

Έτσι, αν τώρα ήθελε να ξεκινήσει την εφαρμογή της παρούσας συνδεδεμένη λίστα, πώς θα μπορούσαμε να μεταφράσει κάτι σαν αυτό να κωδικοποιήσει; Λοιπόν, ας δούμε ένα παράδειγμα ένα πρόγραμμα το οποίο στην πραγματικότητα χρησιμοποιεί μια συνδεδεμένη λίστα. Μεταξύ κώδικα της διανομής του σήμερα είναι ένα πρόγραμμα που ονομάζεται Λίστα Zero. Και αν μπορώ να εκτελέσω αυτό δημιούργησα ένα super απλό GUI, Graphical User Interface, αλλά είναι πραγματικά ακριβώς printf. Και τώρα έχω δώσει τον εαυτό μου μερικά μενού options-- Διαγραφή, Εισαγωγή, Αναζήτηση, και Traverse. Και Quit. Αυτά είναι μόνο κοινές λειτουργίες σε ένα δομή δεδομένων γνωστή ως λίστα σύνδεσμο. 

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

Οπότε ας προσπαθήσουμε αυτό. Ας πάμε μπροστά και τύπου 2. Και στη συνέχεια, Πάω να εισάγετε τον αριθμό, ας πούμε 9. Enter. Και τώρα το πρόγραμμά μου είναι απλά προγραμματισμένο να πω, η λίστα είναι τώρα 9. Τώρα, αν θα προχωρήσει και Δεν Τοποθετήστε πάλι, ας Θέλω να προχωρήσει και σμίκρυνση και πληκτρολογήστε 17. Τώρα λίστα μου είναι 9, τότε 17. Αν το κάνω, τοποθετήστε και πάλι, ας παραλείψετε μία. Αντί για 22, σύμφωνα με την εικόνα που έχουμε κοιτάζοντας εδώ, επιτρέψτε μου να βγαίνουμε μπροστά και τοποθετήστε 26 επόμενη. Έτσι, Πάω να πληκτρολογήσετε 26. Ο κατάλογος είναι όπως περιμένω. Αλλά τώρα, ακριβώς για να δούμε αν αυτό το κώδικα πρόκειται να είναι ευέλικτη, επιτρέψτε μου τώρα Τύπος 22, η οποία τουλάχιστον εννοιολογικά, αν είμαστε Κρατώντας αυτό διευθετηθεί, η οποία είναι πράγματι πρόκειται να είναι ένα άλλο στόχο τώρα, θα πρέπει να πάμε σε μεταξύ 17 και 26. Γι 'αυτό και πατήστε Enter. Πράγματι, αυτό λειτουργεί. Και τώρα επιτρέψτε μου να εισάγετε το τελευταία, ανά την εικόνα, 34. 

Εντάξει. Έτσι, για τώρα επιτρέψτε μου να ορίζουν ότι Διαγραφή και Traverse και Αναζήτηση κάνουμε, στην πραγματικότητα, λειτουργεί. Στην πραγματικότητα, αν δεν τρέξει Αναζήτηση, ας αναζήτηση για τον αριθμό 22, Enter. Διαπίστωσε 22. Έτσι, αυτό είναι ό, τι αυτό Πρόγραμμα Λίστα Zero κάνει. 

Αλλά τι πραγματικά συμβαίνει στο ότι υλοποιεί αυτό; Λοιπόν, το πρώτο που θα μπορούσε να έχει, και μάλιστα Θα έχετε, ένα αρχείο που ονομάζεται list0.h. Και κάπου εκεί είναι αυτό γραμμή, typedef, struct node, τότε έχω άγκιστρα μου, int n, και Στη συνέχεια struct-- ό, τι ήταν ο ορισμός; Struct node επόμενη. Έτσι χρειαζόμαστε το αστέρι. Τώρα τεχνικά φτάσουμε σε η συνήθεια της σχεδίασης είναι εδώ. Μπορείτε να δείτε τα βιβλία και σε απευθείας σύνδεση αναφορές που κάνουν εκεί. Είναι λειτουργικά ισοδύναμες. Στην πραγματικότητα, αυτό είναι λίγο πιο χαρακτηριστική. Αλλά θα είμαι συνεπής με ό, τι κάναμε την τελευταία φορά και να το κάνουμε αυτό. Και στη συνέχεια, τέλος, Πάω να το κάνουμε αυτό. 

Έτσι, σε ένα αρχείο κεφαλίδας κάπου, σε list0.h σήμερα είναι ο ορισμός struct, και ίσως και κάποια άλλα πράγματα. Εν τω μεταξύ, σε list0c υπάρχει πρόκειται να είναι μερικά πράγματα. Αλλά θα πάμε για λίγο ξεκινήσει και να μην τελειώσει αυτό. List0.h είναι ένα αρχείο που θέλω να συμπεριλάβουν στο φάκελο C μου. Και τότε σε κάποιο σημείο είμαι πρόκειται να έχουν int, κύρια, άκυρη. Και στη συνέχεια, Πάω να έχουν κάποια to-do είναι εδώ. Είμαι, επίσης, πρόκειται να έχει ένα πρωτότυπο, όπως κενό, αναζήτηση, int, n, σκοπός της οποίας στη ζωή είναι για να αναζητήσετε ένα στοιχείο. Και στη συνέχεια κάτω εδώ ισχυρίζομαι μέσα σημερινή κώδικα, κενό, αναζήτηση, int, n, Δεν ερωτηματικό, αλλά ανοιχτή σε αγκύλες. Και τώρα θέλω να με κάποιο τρόπο αναζήτησης για ένα στοιχείο σε αυτή τη λίστα. Αλλά δεν έχουμε αρκετό πληροφορίες στην οθόνη ακόμα. Δεν έχω πραγματικά αντιπροσώπευε την ίδια τη λίστα. Έτσι, ένας τρόπος που θα μπορούσε να εφαρμόσει μια συνδεδεμένη λίστα σε ένα πρόγραμμα Θα είναι σαν να θέλω να κάνω κάτι όπως Κηρύσσω την λίστα συνδέονται εδώ. Για λόγους απλότητας, Πάω να αυτό το παγκόσμιο, αν και σε γενικές γραμμές μπορούμε Δεν πρέπει να το κάνετε αυτό πάρα πολύ. Αλλά αυτό θα απλοποιήσει αυτό το παράδειγμα. Θέλω, λοιπόν, να δηλώσουν μια συνδεδεμένη λίστα εδώ. Τώρα, πώς θα μπορούσε να το κάνω αυτό; 

Εδώ είναι η εικόνα μιας συνδεδεμένης λίστας. Και δεν το κάνω πραγματικά γνωρίζουμε αυτή τη στιγμή πώς Πάω να πάει για την εκπροσωπούν τόσα πολλά πράγματα με ένα μόνο μεταβλητή στη μνήμη. Αλλά σκεφτείτε για ένα λεπτό. Όλο αυτό το διάστημα είχαμε χορδές, το οποίο εμείς, στη συνέχεια, αποκάλυψε ότι είναι συστοιχίες χαρακτήρες, η οποία στη συνέχεια θα έδειξε να είναι μόνο ένας δείκτης στον πρώτο χαρακτήρα σε μια σειρά από χαρακτήρες ότι είναι null τερματιστεί. Έτσι, με αυτή τη λογική, και με αυτό είδος εικόνα της σποράς τις σκέψεις σας, τι χρειάζεται να είμαστε πραγματικά γράφετε σε μας κώδικα για να αντιπροσωπεύουν μια συνδεδεμένη λίστα; Πόσο αυτών των πληροφοριών χρειαζόμαστε να συλλάβει τον κωδικό C, θα λέγατε; Ναι; 

ΚΟΙΝΟ: Χρειαζόμαστε ένα δείκτη σε ένα κόμβο. DAVID J. MALAN: Ένας δείκτης σε κόμβο. Ειδικότερα, η οποία κόμβος θα σας ένστικτα είναι να κρατήσει ένα δείκτη για να? 

ΚΟΙΝΟ: Το πρώτο κόμβο. 

DAVID J. MALAN: Ναι, ίσως μόνο η πρώτη. Και παρατηρήσετε, το πρώτο κόμβος είναι ένα διαφορετικό σχήμα. Είναι μόνο το μισό μέγεθος του struct, επειδή είναι πράγματι ένας δείκτης. Έτσι τι μπορείτε να κάνετε είναι πράγματι δηλώσει μια συνδεδεμένη λίστα είναι του τύπου κόμβου *. Και ας πούμε ότι είναι το πρώτο και να προετοιμαστεί για να null. Έτσι, null, και πάλι, είναι που έρχονται στην εικόνα εδώ. Όχι μόνο είναι null χρησιμοποιείται ως σαν μια ειδική τιμή επιστροφής για πράγματα όπως GetString και malloc, null είναι επίσης το μηδέν δείκτη, η έλλειψη ενός δείκτη, αν θέλετε. Σημαίνει απλώς ότι τίποτα δεν είναι ακόμα εδώ. Τώρα το πρώτο, θα μπορούσα να έχω ονομάζεται αυτό το τίποτα. Θα μπορούσα να είχα την αποκάλεσε "λίστα" ή οποιοδήποτε αριθμό άλλων πραγμάτων. Αλλά είμαι χαρακτηρίζοντάς την "πρώτη", έτσι ώστε να ευθυγραμμιστεί με αυτήν την εικόνα. Έτσι ακριβώς όπως ένα string μπορεί να εκπροσωπείται με τη διεύθυνση του πρώτου byte του, έτσι μπορεί μια συνδεδεμένη λίστα. Και θα δούμε και άλλα στοιχεία να εκπροσωπούνται δομές με ένα μόνο δείκτη, ένα 32-bit βέλος, δείχνοντας κατά την πρώτη κιόλας κόμβου στη δομή. 

Αλλά τώρα ας προβλέψει ένα πρόβλημα. Αν είμαι μόνο να θυμόμαστε στο πρόγραμμά μου τη διεύθυνση του πρώτου κόμβου, η πρώτη ορθογώνιο σε αυτή τη δομή δεδομένων, τι είχε καλύτερα να είναι η περίπτωση για την εφαρμογή της υπόλοιπης λίστα μου; Τι είναι μια βασική λεπτομέρεια που πρόκειται για να εξασφαλιστεί αυτό λειτουργεί πραγματικά; Και με το "λειτουργεί πραγματικά" I Δηλαδή, σαν ένα string, ας πάμε από τον πρώτο χαρακτήρα στο όνομα του Davin στη δεύτερη, με το τρίτο, εις το τέταρτο, μέχρι το τέλος, πώς ξέρουμε πότε είμαστε στο τέλος από μια συνδεδεμένη λίστα που μοιάζει με αυτό; Όταν είναι null. Και έχω εκπροσωπείται αυτού του είδους, όπως σαν μια ηλεκτρική δύναμη μηχανικός, με το μικρό γείωσης σύμβολο, των ειδών. Αλλά αυτό ακριβώς σημαίνει null σε αυτή την περίπτωση. Μπορείτε να σχεδιάσετε οποιοδήποτε αριθμό τρόπους, αλλά αυτό το συγγραφέα έτυχε να χρησιμοποιούν αυτό το σύμβολο εδώ. 

Εφ 'όσον είμαστε κλωστή όλα από αυτούς τους κόμβους μεταξύ τους, μόνο θυμόμαστε όπου το πρώτο είναι, εφ ' όπως βάζουμε ένα ειδικό σύμβολο σε το πολύ τελευταίο κόμβο στη λίστα, και θα χρησιμοποιήσει μηδενική, γιατί αυτό είναι ό, τι έχουμε στη διάθεσή μας, ο κατάλογος είναι πλήρης. Και ακόμα κι αν σας δώσω μόνο ένα δείκτη για να το πρώτο στοιχείο, εσείς, ο προγραμματιστής, σίγουρα μπορεί να έχει πρόσβαση το υπόλοιπο. Αλλά ας αφήσουμε το μυαλό σας περιπλανηθεί λίγο, αν δεν είναι ήδη αρκετά wandered-- τι είναι πρόκειται να είναι ο χρόνος εκτέλεσης του εύρεση τίποτα σε αυτή τη λίστα; Γαμώτο, αυτό είναι μεγάλο O του n, το οποίο δεν είναι κακό, για να είμαστε δίκαιοι. Αλλά είναι γραμμική. Έχουμε δώσει μέχρι ποιο χαρακτηριστικό συστοιχιών μετακινώντας περισσότερα προς αυτήν την εικόνα της δυναμικής υφασμένα από κοινού ή συνδέονται με τους κόμβους; Έχουμε παραιτηθεί τυχαίας προσπέλασης. Ένας πίνακας είναι ωραία γιατί μαθηματικά τα πάντα είναι πίσω στην πλάτη με πλάτη με πλάτη. Ακόμα κι αν αυτή την εικόνα φαίνεται αρκετά, και ακόμη αν και μοιάζει με αυτούς τους κόμβους Τα όμορφα απόσταση μεταξύ τους, στην πραγματικότητα θα μπορούσαν να είναι οπουδήποτε. ΟΧ1, ΟΧ50, Ox123, Ox99, αυτά κόμβοι θα μπορούσαν να είναι οπουδήποτε. Επειδή malloc κάνει εκχώρηση μνήμης από το σωρό, αλλά οπουδήποτε στο σωρό. Δεν χρειάζεται απαραιτήτως να ξέρετε ότι είναι πρόκειται να είναι πλάτη με πλάτη με πλάτη. Και έτσι αυτή η εικόνα στην πραγματικότητα είναι δεν πρόκειται να είναι αρκετά αυτό το όμορφο. 

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

Έτσι, η πρώτη Πάω να πάει μπροστά και να κηρύξει κόμβο *. Και Πάω να το ονομάσουμε δείκτη, μόνο κατά σύμβαση. Και Πάω να προετοιμαστεί για την πρώτη. Και τώρα μπορώ να το κάνω αυτό σε έναν αριθμό τρόπων. Αλλά Πάω να λάβει μια κοινή προσέγγιση. Ενώ δείκτης δεν είναι ίση προς null, και ότι είναι έγκυρη σύνταξη. Και αυτό σημαίνει απλά να κάνετε τα εξής, έτσι εφ 'όσον δεν είστε δείχνοντας τίποτα. Τι θέλω να κάνω; 

Αν δείκτη dot n, επιτρέψτε μου να επανέλθω στο ότι, equals-- ισούται με τι; Τι αξία ψάχνω; Η πραγματική n που ψηφίστηκε. Έτσι, εδώ είναι ένα άλλο χαρακτηριστικό της C και πολλές γλώσσες. Ακόμη και αν η δομή που ονομάζεται κόμβος έχει μια τιμή n, εντελώς νόμιμα να έχουν επίσης μια τοπική επιχείρημα ή μεταβλητή που ονομάζεται n. Διότι ακόμα και εμείς, με ανθρώπινα μάτια, μπορεί να διακρίνει ότι αυτή η είναι πιθανώς διαφορετική από αυτή n. Επειδή η σύνταξη είναι διαφορετική. Έχετε μια τελεία και ένα δείκτη, ενώ αυτό δεν έχει τέτοιο πράγμα. Έτσι, αυτό είναι εντάξει. Αυτό είναι εντάξει για να τους καλέσει τα ίδια πράγματα. 

Αν δεν μπορείτε να βρείτε αυτό, είμαι πρόκειται να θέλουν να κάνουν κάτι όπως ανακοινώσει ότι βρήκαμε n. Και αυτό θα το αφήσουμε ως σχόλιο ή κωδικό ψευδοκώδικα. Αλλιώς, και εδώ είναι η ενδιαφέρον μέρος, ό, τι θέλω να κάνω εάν το τρέχον κόμβο δεν περιέχουν n που με νοιάζει; Πώς μπορώ να επιτύχουν τα ακόλουθα; Αν το δάχτυλό μου στο η στιγμή είναι PTR, και είναι δείχνοντας σε ό, τι πρώτος δείχνοντας, πώς μπορώ να μετακινήσετε το δάχτυλό μου στον επόμενο κόμβο στον κώδικα; Λοιπόν, ποιο είναι το ψίχουλο είμαστε πρόκειται να ακολουθήσει σε αυτή την περίπτωση; ΚΟΙΝΟ: [δεν ακούγεται]. DAVID J. MALAN: Ναι, έτσι ώστε την επόμενη. Έτσι, αν πάω πίσω για να μου κώδικα εδώ, πράγματι, είμαι πρόκειται να προχωρήσει και να πω δείκτη, η οποία Είναι απλά μια προσωρινή variable-- είναι ένα παράξενο όνομα, ptr, αλλά Είναι ακριβώς όπως temp-- Πάω να ορίσετε δείκτη ίση με ό, τι δείκτη is-- και πάλι, αυτό πρόκειται να είναι ένα μικρό αμαξάκι για μια moment-- dot επόμενη. Με άλλα λόγια, είμαι πρόκειται να πάρει μου δάχτυλο που να υποδεικνύουν αυτόν τον κόμβο εδώ και είμαι έτοιμος να πω, ξέρετε αυτό, ρίξτε μια ματιά στο επόμενο πεδίο και μετακινήστε το δάχτυλό σας για να ό, τι είναι να υποδεικνύουν. Και αυτό πρόκειται να Επαναλαμβάνω, επαναλαμβάνω, επαναλάβετε. Αλλά όταν κάνει το δάχτυλό μου σταματήσουμε να κάνουμε τίποτα σε όλα; Μόλις το τι γραμμή κλωτσιές κώδικα σε; ΚΟΙΝΟ: [δεν ακούγεται] DAVID J. MALAN: Εάν το σημείο, ενώ δείκτης δεν είναι ίσο με το μηδέν. Σε κάποιο σημείο το δάχτυλό μου θα πρέπει να δείχνει σε null και Πάω να συνειδητοποιήσουν αυτό είναι το τέλος αυτής της λίστας. Τώρα, αυτό είναι λίγο λευκό ψέμα για λόγους απλότητας. Αποδεικνύεται ότι ακόμα κι αν μόλις έμαθε αυτό dot σημειογραφία για τις δομές, δείκτης δεν είναι ένα struct. ptr είναι αυτό; Ακριβώς για να είναι πιο nitpicky. Είναι ένας δείκτης σε κόμβο. Δεν είναι το ίδιο ένας κόμβος. Αν δεν είχα αστέρι εδώ, δείκτης absolutely-- είναι ένας κόμβος. Αυτό είναι σαν μια εβδομάδα δήλωση μιας μεταβλητής, ακόμη και αν η λέξη «κόμβος» είναι νέα. 

Αλλά μόλις εισάγουμε ένα αστέρι, είναι τώρα ένας δείκτης σε κόμβο. Και, δυστυχώς, δεν μπορείτε να χρησιμοποιήσετε ο συμβολισμός κουκκίδα για την ύπαρξη δείκτη. Θα πρέπει να χρησιμοποιήσετε το βέλος σημειογραφία, η οποία, εντυπωσιακά, Είναι η πρώτη φορά κάθε κομμάτι της σύνταξης φαίνεται διαισθητικό. Αυτό μοιάζει κυριολεκτικά σαν ένα βέλος. Και αυτό είναι ένα καλό πράγμα. Και εδώ κάτω κυριολεκτικά Μοιάζει με ένα βέλος. Έτσι, νομίζω ότι είναι η la-- εγώ δεν κάνω ότι είμαι πάνω-διάπραξη here-- I Πιστεύω ότι είναι το τελευταίο νέο κομμάτι της σύνταξης θα πάμε να δούμε. Και ευτυχώς, είναι όντως λίγο πιο διαισθητικό. 

Τώρα, για όσους από εσάς μπορεί να προτιμούν τον παλιό τρόπο, μπορείτε ακόμα να χρησιμοποιήσετε το συμβολισμό με την τελεία. Αλλά, όπως κάθε Δευτέρα συνομιλία, πρέπει πρώτα Πρέπει να πάμε εκεί, πηγαίνετε στο ότι αντιμετώπιση, και στη συνέχεια πρόσβαση στο χώρο. Έτσι, αυτό είναι επίσης σωστό. Και ειλικρινά, αυτό είναι ένα λίγο πιο σχολαστικός. Είστε κυριολεκτικά λέγοντας, dereference ο δείκτης και να πάει εκεί. Στη συνέχεια, πιάσε .n, το πεδίο που ονομάζεται n. Αλλά ειλικρινά, κανείς δεν θέλει να πληκτρολογήσετε ή να διαβάσετε αυτό. Και έτσι ο κόσμος εφευρέθηκε ο συμβολισμός βέλος, το οποίο είναι ισοδύναμο, πανομοιότυπα, Είναι απλά συντακτική ζάχαρη. Έτσι, ένα φανταχτερό τρόπο λέγοντας αυτό Φαίνεται καλύτερα, ή φαίνεται απλούστερη. 

Έτσι, τώρα θα πάω να κάνω κάτι άλλο. Πάω να πω "διάλειμμα" από τη στιγμή έχω Βρέθηκε έτσι δεν συνεχίσετε να ψάχνετε για αυτό. Αλλά αυτή είναι η ουσία της λειτουργίας αναζήτησης. Αλλά είναι πολύ πιο εύκολο, στην τέλος, να μην περπατάτε μέσα από τον κώδικα. Αυτή είναι πράγματι η επίσημη εφαρμογή αναζήτησης στον κώδικα της διανομής του σήμερα. Τολμώ να πω ότι το ένθετο δεν είναι ιδιαίτερα διασκεδαστικό να περπατήσετε μέσα οπτικά, ούτε να διαγράψετε, ακόμα και αν και στο τέλος της ημέρας βράζουν κάτω αρκετά απλά heuristics. 

Έτσι, ας κάνουμε αυτό. Αν εσείς θα το χιούμορ μου εδώ, έκανα φέρει ένα σωρό μπάλες άγχος. Έφερα ένα μάτσο αριθμούς. Και θα μπορούσαμε να πάρετε μόνο λίγα εθελοντές να αντιπροσωπεύει 9, 17, 20, 22, 29, και 34? Έτσι, ουσιαστικά όλοι που είναι εδώ σήμερα. Αυτό ήταν ένα, δύο, τρία, τέσσερα, πέντε, έξι άτομα. Και έχω κληθεί να go-- δείτε, δεν ένα στο πίσω σηκώνει τα χέρια τους. ΟΚ, ένα, δύο, τρία, τέσσερα, five-- επιτρέψτε μου να φορτώσει balance-- έξι. OK, θα έρθει σε έξι up. Θα χρειαστούμε άλλους ανθρώπους. Φέραμε επιπλέον μπάλες άγχος. Και αν μπορούσε, για μόνο μια στιγμή, γραμμή τον εαυτό σας επάνω ακριβώς όπως αυτή την εικόνα εδώ. 

Εντάξει. Ας δούμε, τι είναι το όνομά σας; 

ΚΟΙΝΟ: Andrew. 

DAVID J. MALAN: Andrew, είστε αριθμό 9. Χαίρω πολύ. Εδώ θα πάτε. ΚΟΙΝΟ: Jen. DAVID J. MALAN: Jen. David. Αριθμός 17. Ναι; 

ΚΟΙΝΟ: Είμαι η Τζούλια. 

DAVID J. MALAN: Τζούλια, David. Αριθμός 20. ΚΟΙΝΟ: Christian. DAVID J. MALAN: Christian, David. Αριθμός 22. Και; 

ΚΟΙΝΟ: JP. DAVID J. MALAN: JP. Αριθμός 29. Έτσι προχωρήστε και να πάρει in-- Ωχ. Ωχ. Αναμονής. 20. Υπάρχει κάποιος που έχει ένα δείκτη; ΚΟΙΝΟ: Έχω ένα Sharpie. DAVID J. MALAN: Έχεις ένα Sharpie; OK. Και όμως κάποιοι έχουν ένα κομμάτι χαρτί; Αποθηκεύστε τη διάλεξη. Έλα. ΚΟΙΝΟ: Έχουμε το πήρα. DAVID J. MALAN: Μας πήρε; Εντάξει, σας ευχαριστώ. Εδώ πάμε. Αυτή η από εσάς; Απλά έσωσε την ημέρα. Έτσι, 29. Εντάξει. I ανορθόγραφη 29, αλλά ΟΚ. Προχωρήστε. Εντάξει, εγώ θα σας δώσω στυλό σας πίσω στιγμιαία. Έτσι έχουμε αυτά τα παιδιά εδώ. Ας έχουμε ένα άλλο. Gabe, θέλετε να παίξετε το πρώτο στοιχείο εδώ; Θα πρέπει να επισημάνω σε αυτά τα ωραία λαοί. Έτσι, 9, 17, 20, 22, ταξινόμησης των 29, και στη συνέχεια 34. Μήπως χάνουμε κάποιον; Έχω μια 34. Όταν did-- OK, ο οποίος θέλει να είναι 34; Εντάξει, έλα επάνω, 34. Εντάξει, αυτό θα είναι αξίζει το αποκορύφωμα. Ποιο είναι το όνομά σου; 

ΚΟΙΝΟ: Peter. 

DAVID J. MALAN: Peter, έλα επάνω. Εντάξει, τόσο εδώ είναι μια σωρό των κόμβων. Κάθε ένας από εσάς παιδιά αντιπροσωπεύει ένα από αυτά τα ορθογώνια. Και Gabe, το ελαφρώς παράξενο άνθρωπο έξω, αντιπροσωπεύει την πρώτη. Έτσι δείκτης του είναι λίγο μικρότερο στην οθόνη από ό, τι όλοι οι άλλοι. Και σε αυτή την περίπτωση, καθένα από τα αριστερά τα χέρια πρόκειται είτε να κλίνουν προς τα κάτω, εκπροσωπώντας έτσι null, έτσι μόλις η απουσία ενός δείκτη, ή πρόκειται να δείχνουν σε έναν κόμβο δίπλα σας. 

Έτσι τώρα, αν κοσμούν τον εαυτό σας όπως την εικόνα εδώ, να προχωρήσει και να το σημείο σε κάθε άλλη, με Gabe ιδίως κατάδειξης σε τον αριθμό 9 για να εκπροσωπεί τη λίστα. OK, και τον αριθμό 34, το αριστερό χέρι σας Πρέπει απλά να δείχνει στο πάτωμα. 

Εντάξει, έτσι αυτό είναι η συνδεδεμένη λίστα. Έτσι, αυτό είναι το σενάριο στο ερώτημα. Και πράγματι, αυτή είναι αντιπροσωπευτική από μια κατηγορία προβλημάτων ότι μπορείτε να προσπαθήσετε να λύσετε με κωδικό. Θέλετε να τοποθετήσετε τελικά ένα νέο στοιχείο στη λίστα. Σε αυτή την περίπτωση, θα πάμε να δοκιμάστε να τοποθετήσετε τον αριθμό 55. Αλλά εκεί πρόκειται να είναι διαφορετικές περιπτώσεις για να εξετάσει. Και πράγματι, αυτό πρόκειται να είναι ένα από το big-εικόνα Takeaways εδώ, είναι, ποιες είναι οι διαφορετικές περιπτώσεις. Ποια είναι η διαφορετική εάν οι συνθήκες ή υποκαταστήματα που το πρόγραμμά σας μπορεί να έχει; 

Λοιπόν, ο αριθμός που προσπαθείτε να ένθετο, που γνωρίζουμε τώρα είναι 55, αλλά αν δεν ξέρατε εκ των προτέρων, τολμώ να πω πέφτει σε τουλάχιστον τρία πιθανές καταστάσεις. Πού θα μπορούσε ένα νέο στοιχείο είναι; ΚΟΙΝΟ: Και το τέλος ή τη μέση. David J. MALAN: Στο τέλος, σε η μέση, ή στην αρχή. Γι 'αυτό και ισχυρίζονται ότι υπάρχει τουλάχιστον τρία προβλήματα που πρέπει να λύσουμε. Ας επιλέξουν τι είναι ίσως αναμφισβήτητα το πιο απλό ένα, όπου το νέο στοιχείο ανήκει στην αρχή. Έτσι, Πάω να έχουν κωδικό αρκετά όπως η αναζήτηση, η οποία μόλις έγραψα. Και Πάω να έχουν ptr, η οποία Θα εκπροσωπώ εδώ με το δάχτυλό μου, ως συνήθως. 

Και να θυμάστε, ποια αξία δεν έχουμε προετοιμαστεί ptr να; Έτσι μπορούμε να προετοιμαστεί για να null αρχικά. Αλλά τότε τι κάναμε κάποτε εμείς ήταν μέσα λειτουργία αναζήτησης μας; Θέσαμε αυτό ισούται με το πρώτο, πράγμα που δεν σημαίνει να γίνει αυτό. Αν ορίσω ptr ίσο με το πρώτο, τι θα πρέπει να το χέρι μου πραγματικά να δείχνετε; Δεξιά. Έτσι, αν Gabe και εγώ θα να είναι ίσες τιμές εδώ, χρειαζόμαστε τόσο για το σημείο στο νούμερο 9. 

Έτσι, αυτό ήταν η αρχή της ιστορίας μας. Και τώρα αυτό είναι μόνο απλή, ακόμη και αν η σύνταξη είναι νέα. Εννοιολογικά αυτό είναι ακριβώς γραμμική αναζήτηση. 55 είναι ίση προς 9; Ή μάλλον, ας πούμε λιγότερο από 9. Επειδή προσπαθώ να καταλάβω πού να βάλει 55. Λιγότερο από 9, λιγότερο από 17, λιγότερο από 20, λιγότερο από 22, λιγότερο από 29, μικρότερο από 34, όχι. Μέχρι τώρα είμαστε στην περίπτωση μία από τουλάχιστον τρία. 

Αν θέλετε να εισάγετε 55 πάνω από εδώ, τι γραμμές κώδικα ανάγκη να εκτελεστεί; Πώς κάνει αυτή την εικόνα της οι άνθρωποι πρέπει να αλλάξουν; Τι μπορώ να κάνω με το αριστερό χέρι μου; Αυτό θα πρέπει να είναι μηδενική αρχικά, επειδή είμαι στο τέλος της λίστας. Και τι πρέπει να γίνει εδώ με τον Peter, ήταν; Αυτός είναι προφανώς πρόκειται να το σημείο μου. Γι 'αυτό και ισχυρίζονται ότι υπάρχει τουλάχιστον δύο γραμμές του κώδικα του δείγματος κώδικα από σήμερα ότι πρόκειται να εφαρμόσουν αυτό σενάριο της προσθήκης 55 στην ουρά. Και θα μπορούσα να έχω κάποιον hop και μόνο αντιπροσωπεύουν 55; Εντάξει, θα είναι το νέο 55. 

Έτσι, τώρα τι θα γίνει αν το επόμενο σενάριο έρχεται μαζί, και θέλουμε να εισάγετε κατά τη αρχίζουν ή η επικεφαλής του εν λόγω καταλόγου; Και τι είναι το όνομά σας, τον αριθμό 55; 

ΚΟΙΝΟ: Jack. 

DAVID J. MALAN: Jack; Εντάξει, ωραίο να σας γνωρίσουμε. Καλώς ήρθατε. Έτσι τώρα θα πάμε να εισαγωγή, ας πούμε, τον αριθμό 5. Εδώ είναι η δεύτερη περίπτωση του τρεις καταλήξαμε με πριν. Έτσι, αν 5 ανήκει στην αρχή, ας δούμε πώς θα βρούμε ότι έξω. Θα προετοιμαστεί ptr μου δείκτη για τον αριθμό 9 και πάλι. Και συνειδητοποίησα, oh, 5 είναι μικρότερο από 9. Έτσι διορθώσετε αυτή την εικόνα για μας. Ποιανού τα χέρια, Gabe ή Δαβίδ ή-- τι όνομα τον αριθμό 9 του; 

ΚΟΙΝΟ: Jen. 

DAVID J. MALAN: hands-- Τζεν ποια από τα χέρια μας πρέπει να αλλάξει; Εντάξει, έτσι Gabe σημεία σε ό, τι τώρα; Σε μένα. Είμαι ο νέος κόμβος. Γι 'αυτό θα πρέπει ακριβώς το είδος της κίνησης εδώ για να δείτε οπτικά. Και εν τω μεταξύ, τι μπορώ να επισημάνω ότι; Ακόμα, όπου είμαι δείχνοντας. Έτσι, αυτό είναι όλο. Έτσι ακριβώς πραγματικά μια σειρά από διορθώσεις στον κώδικα αυτό το συγκεκριμένο θέμα, φαίνεται. Εντάξει, έτσι αυτό είναι καλό. Και μπορεί κάποιος να είναι ένα σύμβολο κράτησης θέσης για το 5; Έλα πάνω. Θα έχετε την επόμενη φορά. 

Εντάξει, έτσι now-- και ως ένα μέρος, τα ονόματα Δεν έχω κάνει ρητή μνεία του δικαιώματος τώρα, pred, δείκτης ο προκάτοχός και νέο δείκτη, που είναι μόνο τα ονόματα που δίνονται στο δείγμα κώδικα για τους δείκτες ή τα χέρια μου που είναι είδος προς τα γύρω. Ποιο είναι το όνομά σου; 

ΚΟΙΝΟ: Christine. 

DAVID J. MALAN: Christine. Καλώς ήρθατε. Εντάξει, ας εξετάσουμε τώρα ένα ελαφρώς πιο ενοχλητικό σενάριο, σύμφωνα με την οποία θέλω να εισάγετε κάτι σαν 26 σε αυτό. 20; Τι; Αυτά are-- καλό που έχουμε αυτό το στυλό. Εντάξει, 20. Αν κάποιος θα μπορούσε να πάρει ένα άλλο κομμάτι της χαρτί έτοιμο, ακριβώς στην case-- εντάξει. Ω, ενδιαφέρουσα. Λοιπόν αυτό είναι ένα παράδειγμα ενός bug διάλεξη. Εντάξει ναι, ποιο είναι το όνομά σας και πάλι; ΚΟΙΝΟ: Τζούλια. DAVID J. MALAN: Τζούλια, μπορείτε να ποπ και να προσποιείσαι ότι δεν ήταν ποτέ εκεί; Εντάξει, αυτό δεν συνέβη ποτέ. Σας ευχαριστώ. Έτσι, ας υποθέσουμε ότι θέλουμε να εισάγετε Julia σε αυτό συνδεδεμένη λίστα. Είναι ο αριθμός 20. Και φυσικά αυτή είναι πρόκειται να ανήκουν σε η begin-- δεν αναφέρουν τίποτα ακόμα. Έτσι, το χέρι σας μπορεί να είναι το είδος του κάτω μηδενική ή κάποια αξία σκουπίδια. Ας πούμε την γρήγορη ιστορία. Είμαι δείχνοντας τον αριθμό 5 αυτή τη φορά. Τότε μπορώ να ελέγξω 9. Τότε μπορώ να ελέγξω 17. Τότε μπορώ να ελέγξω 22. Και συνειδητοποιώ, ooh, Τζούλια πρέπει να πάει πριν από τις 22. Λοιπόν, τι πρέπει να συμβεί; Ποιανού τα χέρια θα πρέπει να αλλάξει; Τζούλια, η δική μου, ή-- τι είναι το όνομά σας και πάλι; 

ΚΟΙΝΟ: Christian. 

DAVID J. MALAN: Χριστιανός ή; 

ΚΟΙΝΟ: Andy. 

DAVID J. MALAN: Andy. Χριστιανική ή Άντι; Andy πρέπει να επισημάνει; Τζούλια. Εντάξει. Έτσι Andy, θέλεις να επισημάνω στην Τζούλια; Αλλά περιμένετε ένα λεπτό. Στην ιστορία μέχρι σήμερα, Είμαι το είδος του ενός στο τέλος, με την έννοια ότι δείκτης είναι το πράγμα που είναι μετακίνηση μέσα στη λίστα. Θα μπορούσαμε να έχουμε ένα όνομα για τον Andy, αλλά δεν υπάρχει μεταβλητή που ονομάζεται Andy. Η μόνη άλλη μεταβλητή που έχουμε είναι πρώτο, που είναι αντιπροσωπεύεται από Gabe. 

Έτσι, αυτό είναι πραγματικά γιατί έτσι τώρα δεν έχω χρειάζεται αυτό. Αλλά τώρα στην οθόνη υπάρχει αναφέρουμε και πάλι από προβλ δείκτη. Έτσι, επιτρέψτε μου να είμαι πιο σαφής. Αν αυτό είναι δείκτης, είχα την καλύτερη πάρετε μια λίγο πιο έξυπνο για την επανάληψη μου. Αν δεν σας πειράζει να μου περνάει εδώ και πάλι, δείχνοντας εδώ, δείχνοντας εδώ. Αλλά επιτρέψτε μου να έχουν μια pred δείκτη, δείκτη προκάτοχό του, ότι είναι το είδος του δείχνοντας το στοιχείο Ήμουν ακριβώς στο. Έτσι, όταν πάω εδώ, τώρα αριστερά ενημερώσεις χέρι μου. Όταν πάω εδώ αριστερά ενημερώσεις χέρι μου. Και τώρα δεν έχω μόνο ένα δείκτη για να το στοιχείο που πηγαίνει μετά Julia, Έχω ακόμα ένα δείκτη για να Andy, το στοιχείο πριν. Έτσι έχετε πρόσβαση, κατ 'ουσίαν, φρυγανιά, αν θέλετε, σε όλες τις απαιτούμενες δείκτες. 

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

Τώρα, υπάρχουν σίγουρα κάποια άλλη δραστηριότητες που θα μπορούσαν να εφαρμόσουν. Και αυτές οι εικόνες εδώ ακριβώς απεικονίζουν τι κάναμε με τους ανθρώπους. Τι γίνεται με την αφαίρεση; Αν θέλω να, για παράδειγμα, αφαιρέσετε τον αριθμό 34 ή 55, Θα ήθελα να έχουμε το ίδιο είδος κώδικα, αλλά Πάω να χρειαστεί μία ή δύο βήματα. Γιατί ό, τι είναι νέο; Αν μπορώ να αφαιρέσω κάποιον στο τέλος, όπως τον αριθμό 55 και στη συνέχεια 34, τι πρέπει να αλλάξει, όπως το κάνω αυτό; Δεν έχω να evict-- τι είναι το όνομά σας και πάλι; 

ΚΟΙΝΟ: Jack. 

DAVID J. MALAN: Jack. Θα πρέπει όχι μόνο να evict-- ελεύθερη Jack, τόσο κυριολεκτικά καλέστε δωρεάν Jack, ή τουλάχιστον ο δείκτης εκεί, αλλά τώρα τι πρέπει να αλλάξει με τον Πέτρο; Το χέρι του καλύτερη εκκίνηση προς τα κάτω. Επειδή το συντομότερο Καλώ δωρεάν Jack, αν Πέτρου ακόμα δείχνοντας Jack και ως εκ τούτου, να κρατήσει διέρχονται ο κατάλογος και η πρόσβαση αυτή δείκτη, ότι όταν παλιός φίλος του κατακερματισμού μας σφάλμα θα μπορούσε πράγματι να κλωτσήσει in. Επειδή έχουμε δώσει το πίσω μνήμης με τον Τζακ. 

Μπορείτε να μείνετε εκεί αδέξια για μια στιγμή. Επειδή έχουμε μόνο ένα ζευγάρι τελικές εργασίες για να εξετάσει. Αφαίρεση της κεφαλής της λίστας, ή ο beginning-- και αυτό κάποιου λίγο ενοχλητικό. Επειδή έχουμε να γνωρίζουμε ότι Gabe είναι το είδος των ειδικών σε αυτό το πρόγραμμα. Διότι πράγματι, έχει τη δική του δείκτη. Δεν είναι μόνο που επισήμανε σε, όπως σχεδόν όλοι οι άλλοι εδώ. 

Έτσι, όταν η κεφαλή της λίστας είναι απομακρύνονται, τα χέρια του οποίου πρέπει να αλλάξει τώρα; Ποιο είναι το όνομά σας και πάλι; 

ΚΟΙΝΟ: Christine. 

DAVID J. MALAN: Είμαι χάλια σε ονόματα, προφανώς. Έτσι, Christine και Gabe, των οποίων τα χέρια θα πρέπει να αλλάξει όταν προσπαθούμε να αφαιρέσετε Christine, αριθμός 5, από την εικόνα; Εντάξει, ας κάνουμε Gabe. Gabe πρόκειται να επισημάνω, κατά πάσα πιθανότητα, στο νούμερο 9. Ποιο είναι το επόμενο όμως θα πρέπει να συμβεί; ΚΟΙΝΟ: Christine θα πρέπει να είναι null [δεν ακούγεται]. DAVID J. MALAN: Εντάξει, θα έπρεπε ίσως make-- άκουσα "null" κάπου. ΚΟΙΝΟ: Null και χωρίς αυτήν. DAVID J. MALAN: Null τι; ΚΟΙΝΟ: Null και χωρίς αυτήν. DAVID J. MALAN: Null και χωρίς αυτήν. Έτσι αυτό είναι πολύ εύκολη. Και αυτό είναι τέλειο ότι είστε τώρα το είδος να στέκεται εκεί, δεν ανήκουν. Επειδή έχετε πάει αποσυνδεδεμένη από τη λίστα. Έχετε αποτελεσματικά ήταν ορφανά από τη λίστα. Και έτσι είχαμε καλύτερη καλέστε δωρεάν τώρα και στο εξής Christine για να δώσουμε αυτή τη μνήμη πίσω. Διαφορετικά, κάθε φορά που διαγράψετε ένα κόμβο από τη λίστα θα μπορούσε να κάνει τη λίστα μικρότερη, αλλά στην πραγματικότητα δεν μειώνεται το μέγεθος στη μνήμη. Και έτσι, αν συνεχίσουμε να προσθέτουμε και προσθέτοντας, προσθέτοντας πράγματα στη λίστα, ο υπολογιστής μου θα μπορούσε να πάρει πιο αργή και πιο αργή και πιο αργά, επειδή είμαι εξαντλείται μνήμη, ακόμα και αν δεν είμαι στην πραγματικότητα χρησιμοποιώντας bytes Κριστίν της μνήμης πια. 

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

[Χειροκρότημα] 

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

Ένα, και το είπαμε πριν, ποια είναι η λειτουργία χρόνος αναζήτησης για ένα κατάλογος από την άποψη των μεγάλων O; Τι είναι ένα άνω φράγμα για τη λειτουργία χρόνο ψάχνοντας μια συνδεδεμένη λίστα όπως εφαρμόζεται από τους εθελοντές μας εδώ; Είναι μεγάλη O του n, γραμμική. Επειδή, στη χειρότερη περίπτωση, το στοιχείο, όπως το 55, θα μπορούσε να ψάχνει για μπορεί να είναι, όπου Jack ήταν, σε όλη τη διαδρομή στο τέλος. Και, δυστυχώς, σε αντίθεση με μια σειρά δεν μπορεί να πάρει φανταχτερά αυτή τη φορά. Ακόμα κι αν όλοι οι άνθρωποι μας ήταν ταξινομούνται από μικρά στοιχεία, 5, σε όλη τη διαδρομή μέχρι το μεγαλύτερο στοιχείο, 55, αυτό είναι συνήθως ένα καλό πράγμα. Αλλά αυτό που κάνει αυτή την υπόθεση δεν επιτρέπουν πλέον να κάνουμε; ΚΟΙΝΟ: [δεν ακούγεται] DAVID J. MALAN: Πείτε ξανά; ΚΟΙΝΟ: τυχαίας προσπέλασης. DAVID J. MALAN: τυχαίας προσπέλασης. Και με τη σειρά του αυτό σημαίνει ότι μπορούμε όχι χρησιμοποιούν πλέον αδύναμο μηδενικά, διαίσθηση, και τον κατάφωρο χρησιμοποιώντας δυαδικό αναζητήσετε και να διαίρει και βασίλευε. Διότι ακόμα κι αν οι άνθρωποι θα μπορούσαν προφανώς δείτε ότι ο Andy ή Χριστιανός περίπου στη μέση της λίστας, γνωρίζουμε μόνο ότι ως υπολογιστή με αποκορύφωση τη λίστα από την αρχή. Έτσι έχουμε δώσει μέχρι αυτή την τυχαία πρόσβαση. 

Έτσι, μεγάλη O ν τώρα είναι το ανώτερο δεσμεύεται για το χρόνο αναζήτησης. Τι γίνεται με το ωμέγα της αναζήτησης; Ποιο είναι το κατώτερο όριο για την αναζήτηση για κάποιο αριθμό σε αυτή τη λίστα; ΚΟΙΝΟ: [δεν ακούγεται] DAVID J. MALAN: Πείτε ξανά; ΚΟΙΝΟ: One. DAVID J. MALAN: One. Τόσο σταθερό χρόνο. Στην καλύτερη περίπτωση, Christine είναι πράγματι στην αρχή της λίστας. Και ψάχνουμε για αριθμός 5, έτσι τη βρήκαμε. Έτσι, δεν είναι μεγάλη υπόθεση. Αλλά πήρε να είναι σε η ξεκινώντας από τη λίστα σε αυτή την περίπτωση. Τι γίνεται με κάτι σαν Διαγραφή; Τι γίνεται αν θέλετε να διαγράψετε ένα στοιχείο; Τι είναι το άνω όριο και κάτω φράγμα σχετικά με τη διαγραφή κάτι από ένα συνδεδεμένο λίστα; ΚΟΙΝΟ: [δεν ακούγεται] DAVID J. MALAN: Πείτε ξανά; ΚΟΙΝΟ: n. DAVID J. MALAN: n είναι Πράγματι, το ανώτατο όριο. Επειδή στη χειρότερη περίπτωση θα προσπαθήσουμε να διαγράψετε Jack, όπως μόλις κάναμε. Αυτός είναι όλος ο τρόπος στο τέλος. Μας παίρνει για πάντα, ή n βήματα για να τον βρει. Έτσι, αυτό είναι ένα άνω φράγμα. Αυτό είναι γραμμική, βέβαιος. Και η καλύτερη περίπτωση χρόνος τρέχει, ή τα χαμηλότερα όρια στην καλύτερη περίπτωση θα είναι σταθερό χρόνο. Επειδή ίσως προσπαθούμε να διαγράψετε Christine, και εμείς απλά να πάρετε τυχεροί αυτή είναι στην αρχή. Τώρα, περιμένετε ένα λεπτό. Gabe ήταν, επίσης, στην αρχή, και θα έπρεπε επίσης να ενημερώσετε Gabe. Έτσι, ότι δεν ήταν απλά ένα βήμα. Έτσι είναι πράγματι σταθερές ώρα, στην καλύτερη περίπτωση, για να αφαιρέσετε το μικρότερο στοιχείο; Είναι, αν και θα μπορούσε να είναι δύο, τρεις, ή ακόμη και 100 γραμμές κώδικα, αν είναι το ίδιο αριθμό γραμμές, όχι σε κάποιο βρόχο, και ανεξάρτητο από το μέγεθος από τη λίστα, απολύτως. Διαγραφή του στοιχείου σε η αρχή της λίστας, ακόμα κι αν έχουμε να κάνουμε με Gabe, εξακολουθεί να είναι σταθερό χρόνο. 

Έτσι, αυτό φαίνεται σαν μια τεράστιο βήμα προς τα πίσω. Και τι χάσιμο χρόνου αν, σε μία εβδομάδα και εβδομάδες μηδέν είχαμε όχι μόνο Κωδικός ψευδοκώδικα αλλά πραγματικό κώδικα να εφαρμόσει κάτι που είναι log βάση n, ή να συνδεθείτε, μάλλον, από n, βάσης 2, από την άποψη του χρόνου λειτουργίας του. Έτσι, γιατί στο καλό θα θέλουμε να αρχίσουμε χρησιμοποιώντας κάτι σαν μια συνδεδεμένη λίστα; Ναι. 

ΚΟΙΝΟ: Έτσι, μπορείτε να προσθέσετε στοιχεία στη συστοιχία. DAVID J. MALAN: Έτσι, μπορείτε να προσθέσετε στοιχεία στη συστοιχία. Και αυτό είναι πάρα πολύ θεματικό. Και εμείς θα συνεχίσουμε να βλέπουμε αυτό, αυτό το εμπόριο-off, πολύ όπως έχουμε δει μια trade-off με συγχώνευση ταξινόμησης. Θα μπορούσε πραγματικά να επιταχύνει αναζήτηση ή ταξινόμηση, μάλλον, αν περάσουν λίγο περισσότερο χώρο και έχουν ένα επιπλέον κομμάτι της μνήμης ή μια σειρά για συγχώνευση ταξινόμησης. Αλλά ξοδεύουμε περισσότερα χώρο, αλλά έχουμε εξοικονόμηση χρόνου. Σε αυτή την περίπτωση, είμαστε δίνοντας το χρόνο, αλλά είμαστε κερδίζει την ευελιξία, δυναμισμό, αν θέλετε, η οποία είναι αναμφισβήτητα ένα θετικό στοιχείο. 

Είμαστε, επίσης, οι δαπάνες χώρο. Με ποια έννοια είναι ένα συνδεδεμένο λίστα πιο ακριβά από την άποψη του χώρου από μια σειρά; Πού είναι ο επιπλέον χώρος που προέρχονται από; Ναι; 

ΚΟΙΝΟ: [δεν ακούγεται] δείκτη. 

DAVID J. MALAN: Ναι, μπορούμε έχουν επίσης το δείκτη. Έτσι, αυτό είναι ενοχλητικό minorly ότι δεν είμαι πλέον I αποθήκευση μόνο ένα int να αντιπροσωπεύουν ένα int. Είμαι αποθήκευση ενός int και ένα δείκτη, η οποία είναι επίσης 32 bits. Έτσι είμαι κυριολεκτικά διπλασιασμό το ποσό του χώρου που εμπλέκονται. Έτσι, αυτό είναι ένα trade-off, αλλά ότι είναι στην περίπτωση της int. Ας υποθέσουμε ότι δεν είστε αποθήκευση int, αλλά ας υποθέσουμε ότι κάθε ένα από αυτά τα ορθογώνια ή το καθένα από αυτά τον άνθρωπο, που αντιπροσωπεύουν μια λέξη, μια αγγλική λέξη που μπορεί να είναι πέντε χαρακτήρες, 10 χαρακτήρες, ίσως ακόμη περισσότερο. Στη συνέχεια, προσθέτοντας μόλις 32 περισσότερα bits μπορεί να είναι λιγότερο από ένα big deal. 

Τι θα συμβεί αν κάθε ένα από τους μαθητές στη διαδήλωση ήταν κυριολεκτικά structs μαθητή ότι έχουν ονόματα και τα σπίτια και ίσως αριθμούς τηλεφώνου και Twitter λαβές και τα παρόμοια. Έτσι, όλα τα πεδία που ξεκινήσαμε μιλάμε για την άλλη μέρα, πολύ λιγότερο από ένα big deal, όπως κόμβους μας πάρει πιο ενδιαφέρουσα και μεγάλη για να περάσετε, ε, ένα πρόσθετο pointer ακριβώς για να τους συνδέουν μεταξύ τους. Αλλά, πράγματι, είναι ένα trade-off. Και πράγματι, ο κώδικας είναι πιο περίπλοκη, όπως θα δείτε από ξεφυλλίζει ότι το συγκεκριμένο παράδειγμα. Αλλά τι θα γινόταν αν δεν υπήρχαν κάποια Άγιο Δισκοπότηρο εδώ. Τι θα συμβεί αν δεν κάνουμε ένα βήμα προς τα πίσω, αλλά ένα τεράστιο βήμα προς τα εμπρός και να εφαρμόσουν ένα στοιχεία δομή μέσω της οποίας εμείς μπορούν να βρουν στοιχεία, όπως ο Jack ή Christine ή οποιαδήποτε άλλα στοιχεία σε αυτήν την σειρά σε πραγματικό συνεχή χρόνο; Αναζήτηση είναι σταθερή. Διαγραφή είναι σταθερή. Ένθετο είναι σταθερή. Όλες αυτές οι λειτουργίες είναι σταθερές. Αυτό θα είναι το ιερό δισκοπότηρο μας. Και αυτό είναι όπου εμείς θα πάρει την επόμενη φορά. Τα λέμε τότε.