ΟΜΙΛΗΤΗΣ 1: Εντάξει, έτσι αυτό είναι CS50 Αυτό είναι το τέλος της εβδομάδας πέντε. Και υπενθυμίζουν ότι η τελευταία φορά που άρχισε να ψάχνει στο εκτροφέα δεδομένων δομές που άρχισε να λύσει προβλήματα, που άρχισαν να εισάγουν νέα προβλήματα, αλλά το κλειδί σε αυτό Ήταν το είδος του περάσματος ότι εμείς άρχισε να κάνει από κόμβο σε κόμβο. Έτσι, αυτό βέβαια είναι ένα μεμονωμένα συνδεδεμένη λίστα. Και από μόνες που συνδέονται, Θέλω να πω ότι υπάρχει μόνο μία νήμα μεταξύ κάθε μία από αυτές κόμβων. Βγάζει μπορείτε να κάνετε εκτροφέα πράγματα όπως διπλά συνδεδεμένες λίστες σύμφωνα με την οποία έχετε ένα βέλος πηγαίνει προς τις δύο κατευθύνσεις, η οποία μπορεί να βοηθήσει με συγκεκριμένες αποδόσεις. Αλλά αυτό έλυσε το πρόβλημα; Τι πρόβλημα είχε αυτό το λύσει; Γιατί μας νοιάζει τη Δευτέρα; Γιατί, θεωρητικά, δεν φροντίζουμε τη Δευτέρα; Τι κάνει? 

Κοινό: Μπορούμε να αλλάξετε το μέγεθος δυναμικά. 

ΟΜΙΛΗΤΗΣ 1: Εντάξει, ώστε να μπορούμε να δυναμικά αλλάξετε το μέγεθός του. Μπράβο τους δυο σας. Έτσι, μπορείτε να αλλάξετε το μέγεθος δυναμικά αυτή δομή δεδομένων, ενώ μια σειρά, ανάκληση, θα πρέπει να γνωρίζουμε εκ των προτέρων πόσο χώρο θέλετε και αν χρειάζεστε λίγο περισσότερο χώρο, είστε το είδος του από την τύχη. Θα πρέπει να δημιουργήσετε μια εντελώς νέα σειρά. Θα πρέπει να μετακινήσετε όλα σας δεδομένα από το ένα στο άλλο, τελικά ελευθερώσει την παλιά σειρά αν μπορείτε, και στη συνέχεια να προχωρήσει. Ποια ακριβώς αισθάνεται πολύ δαπανηρή και πολύ αναποτελεσματική, και πράγματι μπορεί να είναι. Αλλά αυτό δεν είναι όλα καλά. Έχουμε πληρώσει ένα τίμημα, τι ήταν ένα από τις πιο προφανείς τις τιμές μας πληρώσουν χρησιμοποιώντας μια συνδεδεμένη λίστα; 

Κοινό: Πρέπει να χρησιμοποιήσουμε διπλό χώρο για κάθε μία. ΟΜΙΛΗΤΗΣ 1: Ναι, γι 'αυτό χρειαζόμαστε τουλάχιστον διπλάσιο χώρο. Στην πραγματικότητα, κατάλαβα αυτή η εικόνα του έστω και λίγο παραπλανητικό, γιατί σε CS50 IDE σε πολλά σύγχρονα υπολογιστές, ένας δείκτης ή μια διεύθυνση δεν είναι στην πραγματικότητα τέσσερεις bytes. Είναι πολύ συχνά αυτά οκτώ ημέρες bytes, το οποίο σημαίνει το κάτω μέρος πιο ορθογώνια υπάρχει στην πραγματικότητα είναι το είδος του δύο φορές μεγάλο όσο αυτό που έχω σχεδιάσει, πράγμα που σημαίνει ότι είστε χρησιμοποιώντας τρεις φορές πολύ χώρο καθώς μπορεί να έχουμε διαφορετικά. Τώρα, την ίδια στιγμή, είμαστε εξακολουθεί να μιλάει bytes, έτσι δεν είναι; Εμείς δεν μιλάμε απαραίτητα megabytes ή gigabytes, εκτός αν αυτές οι δομές δεδομένων πάρει μεγάλες. 

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

Έτσι, αυτό είναι μόνο ένα τμήμα κώδικα C, ούτε καν ένα πλήρες πρόγραμμα ότι πραγματικά γρήγορα χτυπημένη. Δεν είναι σε απευθείας σύνδεση στην κατανομή κώδικα, διότι δεν θα λειτουργεί πραγματικά. Αλλά έχω παρατηρήσει μόνο με ένα σχόλιο, δήλωσε, dot dot dot, υπάρχει κάτι εκεί, dot dot dot, κάτι εκεί. Και ας δούμε ποια είναι τα ζουμερά μέρη είναι. Έτσι, στη γραμμή των τριών, Υπενθυμίζω ότι αυτό είναι τώρα προτείναμε την κήρυξη κόμβο τελευταία ώρα, ένα από αυτά τα ορθογώνια αντικείμενα. Έχει μια int που θα καλέσουμε Ν, αλλά θα μπορούσαμε να το ονομάσουμε κάτι, και, στη συνέχεια, ένα αστέρι struct node ονομάζεται επόμενη. Και ακριβώς για να είναι σαφές, ότι η δεύτερη γραμμή, on line έξι, τι είναι αυτό; Τι είναι αυτό που κάνει για μας; Επειδή σίγουρα μοιάζει περισσότερο κρυπτικό από το συνηθισμένο μεταβλητές μας. 

Κοινό: Κάνει το μετακινήσετε πάνω από ένα. 

ΟΜΙΛΗΤΗΣ 1: Κάνει το μετακινήσετε πάνω από ένα. Και για να είμαι πιο ακριβής, θα αποθηκεύσει τη διεύθυνση του κόμβου που είναι γραφτό να γίνει σημασιολογικά δίπλα του, σωστά; Έτσι, δεν πρόκειται να κατ 'ανάγκην κάτι κινείται. Είναι ακριβώς πρόκειται να αποθηκεύσετε μια τιμή, η οποία είναι πρόκειται να είναι η διεύθυνση από κάποιο άλλο κόμβο, και γι 'αυτό έχουμε πει struct κόμβο αστέρι, το αστέρι που δηλώνει ένα δείκτη ή μια διεύθυνση. Εντάξει, έτσι και τώρα, αν υποθέσουμε ότι έχουμε Αυτό το Ν στη διάθεσή μας, και ας υποθέσουμε ότι κάποιος άλλος έχει παρεμβάλλεται ένα σωρό ακεραίων σε μια συνδεδεμένη λίστα. Και αυτό είναι συνδεδεμένη λίστα τόνισε από κάποιο σημείο μια μεταβλητή που ονομάζεται λίστα που είναι πέρασε εδώ ως παράμετρος, πώς μπορώ να πάω για γραμμή 14 εφαρμογή αναζήτησης; Με άλλα λόγια, αν είμαι εκτελεστικών η λειτουργία του οποίου σκοπός στη ζωή είναι να λάβει μια int και στη συνέχεια το ξεκινώντας από μια συνδεδεμένη λίστα, ότι είναι ένας δείκτης για τη συνδεδεμένη λίστα. Όπως και το πρώτο, ο οποίος πιστεύω ότι ο David Ήταν εθελοντής μας την Δευτέρα, έδειχνε σε ολόκληρη η συνδεδεμένη λίστα, είναι σαν να περνάτε David σε όσο το επιχείρημά μας εδώ. Πώς θα πάτε για την διάσχιση αυτή τη λίστα; Λοιπόν, αποδεικνύεται ότι, ακόμη και αν δείκτες είναι σχετικά νέα τώρα σε μας, μπορούμε να το κάνουμε αυτό σχετικά ευθέως. 

Πάω να πάει μπροστά και να να κηρύξει μια προσωρινή μεταβλητή που με σύμβαση πρόκειται ακριβώς να ονομάζεται δείκτης ή PTR, αλλά θα μπορούσατε να το ονομάσετε οτιδήποτε θέλετε. Και Πάω να προετοιμαστεί αυτό στην αρχή της λίστας. Έτσι, μπορείτε να σκεφτείτε το είδος αυτό όπως μου το δάσκαλο την άλλη μέρα, είδος δείχνει σε κάποιον μεταξύ των ανθρώπων μας ως εθελοντές. Έτσι, είμαι μια προσωρινή μεταβλητή που είναι απλά δείχνοντας το ίδιο πράγμα ότι συμπτωματικά μας το όνομα εθελοντής Δαβίδ επίσης να επισημανθούν. Τώρα, ενώ ο δείκτης είναι Δεν μηδενική, γιατί ανάκληση null ότι είναι κάποια ιδιαίτερη αξία φρουρού η οριοθετεί το τέλος του καταλόγου, Έτσι, ενώ δεν είμαι δείχνοντας το εδάφους όπως και την περασμένη εθελοντή μας ήταν, ας πάμε μπροστά και να κάνουμε το εξής. Αν pointer-- και τώρα έχω το είδος του θέλουν να κάνουμε ό, τι κάναμε με τον μαθητή structure-- εάν δείκτη κουκκίδα δίπλα equals-- μάλλον, αν ο δείκτης dot Ν ισούται ισούται η μεταβλητή Ν, ο επιχείρημα που έχει περάσει μέσα, Στη συνέχεια θέλω να πάω μπροστά και να πω επιστρέψει true. Έχω βρεθεί ο αριθμός Ν εσωτερικό του ένας από τους κόμβους των συνδεδεμένων λίστα μου. Αλλά η τελεία δεν είναι πλέον λειτουργεί στο πλαίσιο αυτό, επειδή δείκτη, PTR, είναι πράγματι ένας δείκτης, μια διεύθυνση, μπορούμε πραγματικά να θαυμάσια χρησιμοποιήσει τελικά ένα κομμάτι της σύνταξης ότι το είδος των σημάτων διαισθητική λογική και πραγματικότητα χρησιμοποιήστε ένα βέλος εδώ, πράγμα που σημαίνει να πάει από ότι η διεύθυνση στο ακέραιο εκεί. Γι 'αυτό είναι πολύ παρόμοια πνεύματος στο χειριστή τελεία, αλλά επειδή δείκτης δεν είναι ένας δείκτης και όχι η ίδια η πραγματική struct, εμείς απλά χρησιμοποιήστε το βέλος. 

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

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

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

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

Έτσι, αν θέλω να ωθήσει κάτι στη στοίβα, Υποθέτω Καλώ την ώθηση λειτουργία, και Λέω ωθήσει 50, όπως και ο αριθμός 50, όπου θα προτείνατε Μου επιστήσω σε αυτή την σειρά; Υπάρχουν πέντε διαφορετικές πιθανές απαντήσεις. Πού θέλετε να ωθήσει τον αριθμό 50; Αν ο στόχος εδώ, πάλι, καλέστε το ώθηση λειτουργία, περνούν σε ένα επιχείρημα 50, όπου μπορώ να το πω; Πέντε possible-- 20% πιθανότητα μαντέψουν σωστά. Ναι; 

Κοινό: Πολύ σωστά. 

ΟΜΙΛΗΤΗΣ 1: Πολύ σωστά. Υπάρχει τώρα μια πιθανότητα 25% μαντέψουν σωστά. Έτσι ώστε θα ήταν πραγματικά ωραία. Κατά σύμβαση, θα πω με μια σειρά, θα ξεκινήσει γενικά στα αριστερά, αλλά θα μπορούσαμε σίγουρα ξεκινούν από τη σωστή. Έτσι, η αεροτομή εδώ θα είμαι κατά πάσα πιθανότητα πρόκειται να αντλήσει από την αριστερά, ακριβώς όπως σε μια κανονική σειρά, όπου Αρχίζω να πηγαίνει αριστερά προς τα δεξιά. Αλλά αν μπορείτε να αναστρέψετε η αριθμητική, πρόστιμο. Δεν είναι μόνο τα συμβατικά. Εντάξει, θέλω να κάνω μια περισσότερες αλλαγές όμως. Τώρα που έχω έσπρωξε κάτι στη στοίβα, τι γίνεται στη συνέχεια; 

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

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

Περιμένετε ένα λεπτό, είμαι σκέψης πίσω σε δύο εβδομάδες όταν αρχίσαμε να μιλάμε για συστοιχίες, όπου αυτό ήταν μηδενική θέση, Αυτή ήταν η θέση ενός, αυτό ήταν τοποθεσίας δυο, αυτό είναι η τοποθεσία τρία, τέσσερα, μοιάζει με το σχέση μεταξύ του μεγέθους και το στοιχείο που θέλετε να καταργήσετε από τον πίνακα φαίνεται να είναι ακριβώς ό, τι; Μέγεθος μείον ένα. Και έτσι αυτό είναι το πώς οι άνθρωποι Γνωρίζουμε 61 έρχεται πρώτη. Πώς είναι ο υπολογιστής πρόκειται να ξέρει; Όταν κωδικό σας, όπου μπορείτε πιθανώς θέλουμε να κάνουμε το μέγεθος μείον ένα, έτσι τρείς μείον ένα είναι δύο και ότι Σημαίνει ότι θέλουμε να απαλλαγούμε από 61. Και τότε μπορούμε πράγματι να ενημερώσετε το μέγεθος, έτσι ώστε το μέγεθος τώρα πηγαίνει από τρεις σε δύο μόνο. Και ακριβώς για να είναι σχολαστικός, Πάω να προτείνει ότι είμαι γίνει, έτσι δεν είναι; Μπορείτε προτεινόμενη διαισθητικά σωστά θα πρέπει να απαλλαγούμε από 61. Αλλά δεν έχουν 'αυτό το είδος είδος ξεφορτωθεί 61; Έχω ξεχάσει αποτελεσματικά ότι είναι πραγματικά εκεί. Και σκεφτείτε ότι πίσω σε PSET4, αν έχετε διαβάσει Το άρθρο σχετικά με την εγκληματολογία, το PDF ότι είχαμε εσείς διαβάζετε, ή θα Θα διαβάσετε αυτή την εβδομάδα για PSET4. Θυμηθείτε ότι αυτό είναι πραγματικά συναφές με η όλη ιδέα της εγκληματολογίας υπολογιστή. Τι κάνει ένας υπολογιστής είναι γενικά απλά ξεχνάει όπου κάτι είναι, αλλά δεν πάει και όπως προσπαθήστε να το μηδέν ή η παράκαμψη εκείνα τα κομμάτια με μηδενικά και μονάδες ή κάποιο άλλο τυχαίο πρότυπο αν δεν το πράξουν οι ίδιοι σκόπιμα. Έτσι ήταν η διαίσθησή σας Εντάξει, ας απαλλαγούμε από 61. Αλλά στην πραγματικότητα, δεν έχουμε να ενοχλεί. Εμείς απλά πρέπει να ξεχνάμε ότι είναι εκεί με την αλλαγή του μεγέθους μας. 

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

Τώρα γιατί συμβαίνει αυτό; Τώρα απλά πρέπει να αισθάνονται άνετα με το γεγονός ότι όταν το πρόγραμμά μου τρέχει, Προφανώς Πάω να πρέπει να ζητήσει από τον άνθρωπο, πόσους αριθμούς θέλετε να αποθηκεύσετε; Έτσι, η είσοδος πρέπει να προέλθει από κάπου. Αλλά από τη στιγμή ξέρω ότι αριθμός, τότε μπορώ μόνο χρησιμοποιήσετε ό, τι λειτουργεί για να δώσει μου ένα κομμάτι της μνήμης; Μπορώ να χρησιμοποιήσω malloc. Και μπορώ να πω οποιοδήποτε αριθμό των bytes Θέλω πίσω για αυτές τις Nths. Και το μόνο που έχω να αποθηκεύουν σε αριθμούς μεταβλητή εδώ μέσα αυτού του struct θα πρέπει να είναι αυτό; Τι πηγαίνει πραγματικά σε το αριθμοί σε αυτό το σενάριο; Ναι, ένας δείκτης για την πρώτη byte του εν λόγω κομμάτι της μνήμης, ή πιο συγκεκριμένα, η διεύθυνση από το πρώτο από τα bytes. Δεν έχει σημασία αν είναι ένα byte ή ένα δισεκατομμύριο bytes, Απλά πρέπει να νοιάζονται για το πρώτο. Επειδή ό, τι εγγυήσεις και malloc εγγυήσεις λειτουργικό σύστημα μου, είναι ότι το κομμάτι της μνήμης μου πάρει, πρόκειται να είναι συνεχόμενες. Δεν πρόκειται να είναι κενά. Έτσι, αν έχω ζητήσει 50 byte ή 1.000 bytes, όλοι πηγαίνουν να πλάτη με πλάτη με πλάτη. Και εφ 'όσον θυμάμαι πόσο μεγάλη, πόσο πολύ ζήτησα, όλα όσα πρέπει να ξέρετε Είναι η πρώτη τέτοια διεύθυνση. 

Έτσι τώρα έχουμε τη δυνατότητα στον κώδικα. Αν και, πρόκειται να μας πάρει περισσότερο χρόνο για να γράψω αυτό επάνω, θα μπορούσαμε τώρα να ανακατανείμει τις μνήμες από μόνο την αποθήκευση σε διαφορετική διεύθυνση εκεί αν θέλουμε ένα μεγαλύτερο ή ακόμη και ένα μικρότερο κομμάτι της μνήμης. Έτσι, εδώ σε ένα εμπόριο off. Τώρα έχουμε δυναμισμό. Έχουμε ακόμα contiguousness είμαι διεκδίκηση. Επειδή malloc θα μας δώσει ένα συνεχές κομμάτι της μνήμης. Αλλά αυτό πρόκειται να είναι ένας πόνος στο ο λαιμός μας, ο προγραμματιστής, πραγματικά να κωδικοποιήσει επάνω. Είναι απλά περισσότερη δουλειά. Χρειαζόμαστε κώδικα παρόμοιο με αυτό που ήμουν χτυπώντας έξω μόλις πριν από ένα χρόνο. Πολύ εφικτό, αλλά προσθέτει πολυπλοκότητα. Και έτσι ο χρόνος του έργου, προγραμματιστής ο χρόνος είναι ένα ακόμη πόρο ότι ίσως χρειαστεί να δαπανήσει κάποια στιγμή να πάρει νέα χαρακτηριστικά. Και τότε φυσικά υπάρχει μια ουρά. Δεν θα υπεισέλθω σε αυτό μία στις πολλές λεπτομέρειες. Αλλά είναι πολύ παρόμοια στο πνεύμα. Θα μπορούσε να εφαρμόσει μια ουρά, και αντίστοιχων ενεργειών της, Τοποθέτηση στην ουρά ή dequeue, όπως προσθέσετε ή να αφαιρέσετε, είναι ακριβώς ένα φανταχτερό τρόπο λέγοντας ότι, Τοποθέτηση στην ουρά ή dequeue, ως εξής. Μπορώ να δώσω στον εαυτό μου μόνο ένα struct ότι έχει και πάλι έναν αριθμό σειρά του, ότι και πάλι έχει ένα μέγεθος, αλλά γιατί χρειάζομαι τώρα να παρακολουθείτε την μπροστά από μια ουρά; Δεν χρειάζεται να γνωρίζετε το μπροστινό μέρος του stack μου. Λοιπόν, αν και πάλι για μια queue-- ας σκληρά κώδικα, όπως έχει σαν πέντε ακέραιοι εδώ δυνητικά. Έτσι, αυτό είναι μηδέν, ένα, δύο, τρία, τέσσερα. Αυτό πρόκειται να είναι κάλεσε και πάλι τους αριθμούς. Και αυτό θα πρέπει να ονομάζεται μέγεθος. 

Γιατί δεν αρκεί να έχουν μόνο το μέγεθος; Λοιπόν, ας πιέσουμε τις ίδιες αριθμούς. Γι 'αυτό και εγώ pushed-- enqueued, ή έσπρωξε. Τώρα θα Τοποθέτηση στην ουρά 50, και στη συνέχεια, 51, 61 και στη συνέχεια, και dot dot dot. Έτσι ώστε να είναι Τοποθέτηση στην ουρά. Ι enqueued 50, τότε 51, τότε 61. Και αυτό είναι ολόιδια σε μια στοίβα μέχρι στιγμής, πλην I χρειάζεται να κάνετε μία αλλαγή. Θα πρέπει να ενημερώσετε αυτό το μέγεθος, γι 'αυτό πάω από μηδέν έως ένα και δύο με τρεις τώρα. Πώς μπορώ να dequeue; Τι συμβαίνει με dequeue; Ποιος θα βγει από αυτήν την πρώτη λίστα αν είναι η γραμμή στο Apple Store; Έτσι, 50. Έτσι είναι το είδος της πιο περίπλοκη αυτή τη φορά. Εκτιμώντας τελευταία φορά που ήταν σούπερ εύκολο να κάνει ακριβώς το μέγεθος μείον ένα, Θα φτάσουμε στο τέλος του πίνακα αποτελεσματικά μου όπου βρίσκονται οι αριθμοί, αφαιρεί 61. Αλλά δεν θέλω να καταργήσετε 61. Θέλω να πάρω 50, ο οποίος υπήρχε στις 5:00 π.μ. να παρατάξει για το νέο iPhone ή οτιδήποτε. Και έτσι για να απαλλαγούμε από 50, Ι Δεν μπορούμε απλά να το κάνετε αυτό, σωστά; Μπορώ να περάσουν από 50. Αλλά εμείς απλά είπαμε Δεν χρειάζεται να είναι τόσο πρωκτική ως προς το μηδέν ή να αποκρύψετε τα δεδομένα. Εμείς απλά να ξεχνάμε από πού είναι. 

Αλλά αν μπορώ να αλλάξω το νούμερό μου τώρα δυο, είναι αυτό επαρκείς πληροφορίες να γνωρίζουν τι συμβαίνει στην ουρά μου; Όχι ακριβώς. Όπως το νούμερό μου είναι δύο, αλλά πού αρχίζει η ουρά, ειδικά αν έχω ακόμα αυτοί ίδιους αριθμούς στη μνήμη. 50, 51, 61. Γι 'αυτό πρέπει να θυμάστε τώρα, όπου το μέτωπο είναι. Και έτσι όπως προτείνεται μέχρι εκεί, θα έχουμε μόλις που ονομάζεται Νιοστή μπροστά, του οποίου η αρχική αξία θα έπρεπε να είναι αυτό; Μηδέν, μόνο η αρχή της λίστας. Τώρα, όμως, εκτός από την Decrementing το μέγεθος, εμείς απλά αυξήσετε το μέτωπο. Τώρα εδώ είναι ένα άλλο πρόβλημα. Έτσι, τη στιγμή συνεχίζω. Ας υποθέσουμε ότι αυτή είναι ο αριθμός των όπως 121, 124, και στη συνέχεια, διάολε, Είμαι έξω χώρο. Αλλά περιμένετε ένα λεπτό, δεν είμαι. Έτσι, σε αυτό το σημείο στην ιστορία, ας υποθέσουμε ότι το μέγεθος είναι ένα, δύο, τρία, τέσσερα, έτσι υποθέσουμε ότι η μέγεθος είναι τέσσερα, το μέτωπο είναι ένα, έτσι 51 βρίσκεται στο μπροστινό μέρος. Θέλω να βάλω έναν άλλο αριθμό εδώ, αλλά, διάολε, είμαι από το διάστημα. Αλλά δεν είμαι πραγματικά, έτσι δεν είναι; Πού θα μπορούσε να βάζω μερικά πρόσθετη αξία, όπως 171; Ναι, θα μπορούσα ακριβώς το είδος του επιστρέψω εκεί, σωστά; Και στη συνέχεια διασχίζουν το 50, ή απλά το αντικαταστήσετε με 171. Και αν αναρωτιέστε γιατί αριθμοί μας πήρε τόσο τυχαία, αυτά είναι συνήθως λαμβάνονται υπολογιστή μαθήματα επιστήμης στο Χάρβαρντ μετά CS50. Αλλά αυτό ήταν μια καλή βελτιστοποίηση, γιατί τώρα δεν είμαι σπατάλη χώρου. Έχω ακόμα να θυμόμαστε πόσο μεγάλο είναι αυτό το πράγμα είναι συνολική. Είναι πέντε συνολικά. Επειδή δεν θέλω να ξεκινήσετε την αντικατάσταση 51. Έτσι τώρα είμαι ακόμα έξω από το διάστημα, έτσι ώστε το ίδιο πρόβλημα όπως και πριν. Αλλά μπορείτε να δείτε πώς τώρα στον κώδικά σας, ίσως Πρέπει να γράψω ένα λίγο πιο πολυπλοκότητα για να συμβεί αυτό. Και στην πραγματικότητα, ό, τι χειριστή σε C πιθανότατα αφήνει κάνετε μαγικά αυτό το κυκλικότητα; Ναι τελεστής του υπόλοιπου, το σύμβολο τοις εκατό. Έτσι τι είναι είδος δροσερό για μια ουρά, ακόμα κι αν κρατάμε την κατάρτιση πινάκων όπως αυτές όπως ευθείες γραμμές, αν είδος σκεφτείτε ως κάμπτοντας περίπου ως έναν κύκλο, τότε απλά διαισθητικά αυτό το είδος των έργων ψυχικά Νομίζω ότι λίγο πιο καθαρά. Θα πρέπει ακόμα να εφαρμόσουν ότι νοητικό μοντέλο στον κώδικα. Έτσι δεν είναι ότι σκληρά, εν τέλει, για την εφαρμογή της, αλλά εξακολουθεί να χάνουμε την size-- μάλλον, η δυνατότητα να αλλάξετε το μέγεθος, αν δεν κάνουμε αυτό. 

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

Έτσι, ταινία μικρού μήκους, αν θέλετε. Μια κίνηση που ορισμένοι λαούς σε ένα άλλο πανεπιστήμιο μαζί ότι έχουμε προσαρμοσμένο για αυτή τη συζήτηση. Πρόκειται Τζακ εκμάθηση της στοιχεία σχετικά με τις ουρές και τα στατιστικά. 

ΦΙΛΜ: Μια φορά κι έναν καιρό, υπήρχε ένας τύπος που ονομάζεται Jack. Όταν ήρθε να κάνει φίλους, Τζακ δεν είχε ταλέντο. Έτσι ο Jack πήγε να μιλήσει με το πιο δημοφιλής τύπος ήξερε. Πήγε στο Λου και ρώτησε, τι μπορώ να κάνω; Lou είδε ότι ο φίλος του Ήταν πραγματικά στενοχωρημένος. Λοιπόν, άρχισε, μόλις κοίτα πώς είστε ντυμένοι. Δεν έχετε ρούχα με μια διαφορετική ματιά; Ναι, είπε ο Τζακ. Εγώ σίγουρα κάνω. Έλα στο σπίτι μου και Θα τους δείξω. Έτσι πήγε να του Jack. Και ο Τζακ έδειξε Lou το παράθυρο όπου φυλάσσονται όλα τα πουκάμισα του, και το παντελόνι του, και τις κάλτσες του. Lou είπε, βλέπω ότι έχετε όλα τα ρούχα σας σε ένα σωρό. Γιατί δεν φορούν μερικά άλλα μόλις για λίγο; 

Τζακ είπε, καλά, όταν αφαιρέστε τα ρούχα και κάλτσες, Τους πλένουμε και το βάζουμε τους μακριά στο κουτί. Στη συνέχεια, έρχεται το επόμενο το πρωί και μέχρι I hop. Πηγαίνω στο παράθυρο και να πάρει τα ρούχα μου από την κορυφή. Lou συνειδητοποίησε γρήγορα το πρόβλημα με τον Τζακ. Συνέχισε ρούχα, CD, και βιβλία στη στοίβα. Όταν έφτασε για κάτι για να διαβάσετε ή να φορέσει, ότι θα επιλέξουν την κορυφή βιβλίο ή εσώρουχα. Στη συνέχεια, όταν είχε κάνει, Θα το διορθώσουμε πίσω. Επιστροφή θα πάει, στην κορυφή της στοίβας. Γνωρίζω τη λύση, είπε μια θριαμβευτική δυνατά. Θα πρέπει να μάθουν να αρχίσετε να χρησιμοποιείτε μια ουρά. Λου πήρε τα ρούχα του Jack και κρέμασαν τους στην ντουλάπα. Και όταν είχε αδειάσει το πλαίσιο, ο ίδιος απλά πετιέται. 

Στη συνέχεια, είπε, τώρα Τζακ, στο τέλος της η ημέρα, βάλτε τα ρούχα σας στο αριστερό Όταν βάζετε μακριά. Στη συνέχεια, αύριο το πρωί, όταν δείτε τον ήλιο, να πάρει τα ρούχα σας στα δεξιά, από το τέλος της γραμμής. Μην βλέπετε; δήλωσε ο Lou. Θα είναι τόσο ωραία. Θα φοράτε πάντα μια φορά πριν φορέσετε κάτι δύο φορές. Και με τα πάντα στις ουρές ντουλάπα και ράφι του, Τζακ άρχισε να αισθάνεται αρκετά σίγουρος για τον εαυτό του. Όλες οι ευχαριστίες προς τον Lou και υπέροχη ουρά του. ΟΜΙΛΗΤΗΣ 1: Εντάξει, αυτό είναι αξιολάτρευτο. Έτσι, αυτό που έχει πραγματικά συμβαίνει για κάτω από το καπό τώρα; Ότι έχουμε δείκτες, ότι έχουμε malloc, ότι έχουμε τη δυνατότητα να δημιουργήσουμε κομμάτια της μνήμης για τους εαυτούς μας δυναμικά. Έτσι, αυτό είναι μια εικόνα που είδαμε τις προάλλες. Δεν είχαμε πραγματικά να κατοικήσει σε αυτό, αλλά αυτή η εικόνα έχει αρχίσει εδώ και κάτω Η κουκούλα για εβδομάδες τώρα. Και έτσι αυτό αντιπροσωπεύει, απλά ένα ορθογώνιο που έχουμε ζωγραφίσει, μνήμη του υπολογιστή σας. Και ίσως υπολογιστή σας, ή CS50 ID, έχει ένα gigabyte μνήμης RAM ή ή δύο gigabytes ή τέσσερις. Δεν έχει τόση σημασία. Το λειτουργικό σας σύστημα Windows ή Mac OS ή Linux, επιτρέπει ουσιαστικά το πρόγραμμά σας να πιστεύω ότι έχει πρόσβαση στο σύνολο του μνήμη του υπολογιστή σας, ακόμα κι αν μπορούσε να τρέχει πολλαπλά προγράμματα ταυτόχρονα. Έτσι, στην πραγματικότητα, ότι δεν λειτουργεί πραγματικά. Αλλά αυτό είναι το είδος της μια ψευδαίσθηση δοθεί σε όλα τα προγράμματα σας. Έτσι, αν είχατε δύο συναυλίες της μνήμης RAM, αυτό είναι το πώς ο υπολογιστής μπορεί να το σκέφτομαι αυτό. 

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

Και υπενθυμίζουν τώρα ότι αυτό είναι σημαντικό. Διότι αν δεν έχουν κάτι σαν ανταλλαγής και δύο τοπικές μεταβλητές όπως Α και Β και αλλάζουμε αυτές τις αξίες από τη μία και δύο σε δύο και, ανάκληση ότι, όταν επιστρέφει ανταλλαγής, είναι σαν τη φέτα, της μνήμης είναι μόλις φύγει. Στην πραγματικότητα, είναι ακόμα forensically εκεί. Και κάτι ακόμα πραγματικά εκεί. Αλλά εννοιολογικά, είναι όπως αν και είναι εντελώς φύγει. Και έτσι η κύρια δεν γνωρίζει οποιαδήποτε από τις εργασίες ότι έγινε σε αυτή την λειτουργία εναλλαγής, αν δεν είναι στην πραγματικότητα πέρασε σε εκείνους επιχειρήματα από το δείκτη ή με αναφορά. Τώρα, η θεμελιώδης λύση σε αυτό το πρόβλημα με την ανταλλαγή περνά από τα πράγματα στη διεύθυνση. Αλλά αποδεικνύεται, πάρα πολύ, τι είναι συνεχίζεται πάνω από αυτό το μέρος του ορθογωνίου όλο αυτό το διάστημα είναι Υπάρχει όμως περισσότερη μνήμη μέχρι εκεί. Και όταν δυναμικά εκχώρηση μνήμης, είτε πρόκειται για εσωτερικό της GetString, η οποία έχουμε κάνει για σας στο CS50 βιβλιοθήκη, ή αν εσείς καλέστε malloc και να ζητήσει το λειτουργικό σύστημα για ένα κομμάτι της μνήμη, δεν προέρχεται από τη στοίβα. Προέρχεται από μια άλλη χώρα στη μνήμη του υπολογιστή σας αυτό ονομάζεται ο σωρός. Και αυτό δεν είναι κάτι διαφορετικό. Είναι η ίδια μνήμη RAM. Είναι η ίδια μνήμη. Είναι ακριβώς η μνήμη RAM που είναι μέχρι εκεί, αντί του εδώ κάτω. 

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

Και αποδεικνύεται ότι κακός, τους λαούς που είναι ιδιαίτερα καλή με τον προγραμματισμό, και προσπαθεί να χαράξει σε ηλεκτρονικούς υπολογιστές, μπορεί να εκμεταλλευτεί αυτή την πραγματικότητα. Στην πραγματικότητα, ας εξετάσουμε ένα μικρό απόσπασμα. Έτσι, αυτό είναι ένα παράδειγμα μπορείτε να διαβάσετε για περισσότερες λεπτομέρειες σχετικά με την Wikipedia. Θα δείξετε το Το άρθρο αν και περίεργη. Αλλά υπάρχει μια επίθεση σε γενικές γραμμές γνωστή ως υπερχείλιση μνήμης που έχει υπάρξει για όσο χρονικό διάστημα οι άνθρωποι είχαν την ικανότητα να χειραγωγούν μνήμη του υπολογιστή, ειδικά σε C. Έτσι, αυτό είναι ένα πολύ αυθαίρετο πρόγραμμα, αλλά ας το διαβάσει από κάτω προς τα πάνω. Κύρια μέσα argc char αστέρων argv. Έτσι είναι ένα πρόγραμμα που διαρκεί επιχειρήματα της γραμμής εντολών. Και όλα τα βασικά δεν φαίνεται να είναι η κλήση μια λειτουργία, την αποκαλούν F για την απλότητα. Και σε ό, τι περνάει; Argv του ενός. Γι 'αυτό περνά στο F ανεξαρτήτως η λέξη είναι ότι ο χρήστης πληκτρολογήσει στη γραμμή μετά από την Το όνομά προγράμματος σε όλα. Τόσο πολύ, όπως Καίσαρα ή Vigenere, η οποία Θα θυμάστε ίσως να κάνει με argv. 

Έτσι τι είναι F; F παίρνει σε μια σειρά ως μοναδικό επιχείρημα, AKA ένα αστέρι κάρβουνου, το ίδιο πράγμα, σαν ένα string. Και αυτό λέγεται αυθαίρετα μπαρ σε αυτό το παράδειγμα. Και στη συνέχεια, char c 12, μόνο σε απλή γλώσσα, τι είναι char c βραχίονα 12 κάνει για μας; Τι θα κάνουμε; Διαθέτοντας τη μνήμη, ειδικά 12 byte για 12 χαρακτήρες. Ακριβώς. Και τότε η τελευταία γραμμή, ανακατεύουμε και αντίγραφο, πιθανώς έχετε δει. Αυτό είναι ένα αντίγραφο συμβολοσειράς η λειτουργία του οποίου σκοπός στη ζωή είναι να αντιγράψετε το δεύτερο επιχείρημα της σε πρώτο επιχείρημά της, αλλά μόνο μέχρι ένα ορισμένο αριθμό bytes. Έτσι, το τρίτο επιχείρημα λέει, πόσα bytes θα πρέπει να αντιγράψετε; Το μήκος της ράβδου, ανεξάρτητα από το χρήστης πληκτρολογήσει. Και τα περιεχόμενα του Μπαρ, ότι χορδών, αντιγραφεί στη μνήμη στραμμένο στο C. 

Έτσι, αυτό φαίνεται κάπως ανόητο, και αυτό είναι. Είναι μια σκηνοθετημένη παράδειγμα, αλλά είναι αντιπροσωπευτικό της τάξης των φορέων επίθεσης, ένας τρόπος για να επιτεθεί σε ένα πρόγραμμα. Όλα είναι ωραία και καλά, αν ο χρήστης τύποι σε μια λέξη που είναι 11 χαρακτήρες ή λιγότερες, καθώς η αντίστροφη κάθετος μηδέν. Τι θα συμβεί αν ο χρήστης πληκτρολογήσει σε περισσότερες από 11 ή 12 ή 20 ή 50 χαρακτήρες; Τι είναι αυτό το πρόγραμμα πρόκειται να κάνει; Δυνητικά SEG σφάλμα. Είναι πρόκειται να αντιγράψετε τυφλά ό, τι στο μπαρ μέχρι με το μήκος του, η οποία είναι κυριολεκτικά τα πάντα στο μπαρ, στην διεύθυνση επισήμανε σε C. Αλλά C έχει μόνο προληπτικά δίνεται ως 12 bytes. Αλλά δεν υπάρχει κανένας πρόσθετος έλεγχος. Δεν υπάρχει, αν οι συνθήκες. Δεν υπάρχει έλεγχος σφαλμάτων εδώ. 

Και έτσι ό, τι αυτό το πρόγραμμα είναι πρόκειται να κάνουμε είναι ακριβώς τυφλά αντιγράψετε ένα πράγμα στο άλλο. Και έτσι, αν βγάλουμε αυτό ως εικόνα, είναι εδώ μόνο μια φέτα του χώρου μνήμης. Έτσι παρατηρήσετε στο κάτω μέρος, που έχουν την τοπική μεταβλητή γραμμή. Έτσι, αυτό το δείκτη που πρόκειται να store-- και όχι ότι η τοπική επιχείρημα ότι είναι πρόκειται να αποθηκεύσετε τη γραμμή κορδόνι. Και στη συνέχεια, μόλις παρατηρήσετε πάνω από αυτό σε μια στοίβα, γιατί κάθε φορά που θα ρωτήσω για τη μνήμη στη στοίβα, πηγαίνει λίγο πάνω από αυτό με εικόνες, Παρατηρήστε ότι έχουμε 12 bytes εκεί. Το κορυφαίο αριστερό βραχίονα C είναι μηδέν και το κάτω δεξιά ένα είναι C βραχίονα 11. Αυτό είναι ακριβώς το πώς οι υπολογιστές πρόκειται να το βάλω έξω. Έτσι απλά διαισθητικά, αν έχει περισσότερες από 12 χαρακτήρες συνολικά, συμπεριλαμβανομένων η ανάστροφη κάθετο μηδέν, όπου είναι η 12 ή το βραχίονα C 12 πρόκειται να πάει; Ή μάλλον, όπου είναι η 12η χαρακτήρα ή το 13ο χαρακτήρα, η εκατοστή χαρακτήρα θα για να καταλήξει στην εικόνα; Πάνω ή κάτω; 

Δεξιά, γιατί ακόμα κι αν η ίδια η στοίβα μεγαλώνει προς τα πάνω, τη στιγμή που έχετε βάλει τα πράγματα σε αυτό, για λόγους σχεδίασης, βάζει τη μνήμη από πάνω προς τα κάτω. Έτσι, αν έχετε περισσότερα από 12 bytes, θα πάμε να αρχίσουν να αντικαταστήσετε μπαρ. Τώρα αυτό είναι ένα bug, αλλά είναι δεν είναι πραγματικά μια μεγάλη υπόθεση. Αλλά είναι μια μεγάλη υπόθεση, γιατί υπάρχει περισσότερα πράγματα συμβαίνουν στη μνήμη. Τόσο εδώ είναι πώς μπορούμε να θέσει ένα γεια, να είναι σαφής. Αν έχω πληκτρολογήσει στο γεια στη γραμμή. Η-Ε-Ε-Ε-Ο ανάποδη μηδέν, καταλήγει στο αυτά τα 12 bytes, και είμαστε εξαιρετικά ασφαλή. Όλα είναι καλά. Αλλά αν πληκτρολογήσετε κάτι πλέον, είναι δυνητικά πρόκειται να παρεισφρήσουν χώρο μπαρ. Ακόμα χειρότερα όμως, αποδεικνύεται από όλο αυτό το διάστημα, ακόμα κι αν ποτέ δεν έχουμε μιλήσει για αυτό, η στοίβα χρησιμοποιείται για άλλα πράγματα. Δεν είναι μόνο τοπικές μεταβλητές. 

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

Με άλλα λόγια, αν αυτό το χρήστης πληκτρολογεί στη γραμμή, Δεν είναι μόνο κάτι αβλαβείς, όπως γειά σου, αλλά στην πραγματικότητα είναι κώδικας που είναι ισοδύναμη για να διαγράψετε όλα τα αρχεία του χρήστη; Ή email Κωδικός πρόσβασης τους σε μένα; Ή ξεκινήσει η καταγραφή τους πληκτρολογήσεις, σωστά; Υπάρχει ένας τρόπος, ας προβλέπουν σήμερα, ότι θα μπορούσαν να πληκτρολογήσετε όχι μόνο γεια κόσμο ή το όνομά τους, θα μπορούσαν κατ 'ουσίαν περνούν στον κώδικα, και μηδενικά αυτά, ότι ο υπολογιστής τα λάθη και για τις δύο κώδικα και μια διεύθυνση. Έτσι, αν και κάπως αφηρημένα, εάν η πληκτρολογεί ο χρήστης σε αρκετά αντιμωλία κώδικα ότι θα γενικεύσουμε εδώ Α Α είναι επίθεση ή αντιπάλους. Έτσι απλά κακά πράγματα. Εμείς δεν νοιάζονται για το αριθμούς ή τα μηδενικά ή αυτές σήμερα, έτσι ώστε να καταλήξουμε αντικαθιστώντας το κόκκινο τμήμα, παρατηρήσετε ότι η ακολουθία των bytes. O 835 C μηδέν οκτώ μηδέν. Και τώρα, όπως το άρθρο της Wikipedia εδώ έχει προτείνει, αν τώρα πραγματικά να αρχίσετε επισήμανση των bytes στο του υπολογιστή σας μνήμη, ό, τι το άρθρο της Wikipedia είναι προτείνουσα είναι ότι, ό, τι και αν η διεύθυνση του εν λόγω πάνω αριστερά byte είναι 80 C 0 3508. 

Με άλλα λόγια, αν ο κακός είναι αρκετά έξυπνος με τον κωδικό του ή της να βάλει πραγματικά έναν αριθμό που εδώ αντιστοιχεί στη διεύθυνση του κώδικα αυτός ή αυτή εγχέεται στον υπολογιστή, μπορείτε μπορεί να εξαπατήσει τον υπολογιστή στο να κάνει κάτι. Αφαίρεση αρχείων, ηλεκτρονικό ταχυδρομείο πράγματα, εισπνοή της κυκλοφορίας σας, κυριολεκτικά οτιδήποτε θα μπορούσε να είναι εγχέεται μέσα στον υπολογιστή. Και έτσι η υπερχείλιση του buffer επίθεση στον πυρήνα της είναι απλά μια ηλίθια, ηλίθια επιτακτικών έναν πίνακα που δεν έχει τα όριά της ελεγχθούν. Και αυτό είναι ό, τι είναι εξαιρετικά επικίνδυνη και ταυτόχρονα σούπερ ισχυρό σε C είναι ότι έχουμε πράγματι πρόσβαση σε οποιοδήποτε σημείο στη μνήμη. Είναι στο χέρι μας, οι προγραμματιστές, που γράφουν το αρχικό κώδικα για να ελέγξετε το μήκος του κάθε καταριέται πίνακες που είμαστε χειρισμό. Έτσι για να είναι σαφές, ποια είναι η λύση; Αν επαναφέρετε σε αυτό κώδικα, δεν πρέπει απλώς να αλλάξετε το μήκος της ράβδου, τι αλλιώς θα πρέπει να είμαι έλεγχο; Τι άλλο πρέπει να να κάνει για να αποτρέψετε αυτήν την επίθεση εξ ολοκλήρου; Δεν θέλω να πω ακριβώς τυφλά ότι θα πρέπει να αντιγράψετε και πολλά bytes όπως είναι το μήκος της ράβδου. Θέλω να πω, όπως αντιγραφή ο αριθμός των bytes που βρίσκονται σε μπαρ μέχρι η χορηγούμενη μνήμη, ή 12 μέγιστα. Γι 'αυτό χρειάζεται κάποιο είδος αν η κατάσταση ότι δεν ελέγχει το μήκος της ράβδου, αλλά αν υπερβαίνει το 12, εμείς απλά σκληρά κώδικα 12 ως η μέγιστη δυνατή απόσταση. Διαφορετικά, η λεγόμενη ρυθμιστικό επίθεση υπερχείλισης μπορεί να συμβεί. Στο κάτω μέρος των εν λόγω διαφάνειες, αν είστε περίεργοι να διαβάσετε περισσότερα είναι η πραγματική αρχικό άρθρο αν θέλετε να ρίξετε μια ματιά. 

Αλλά τώρα, μεταξύ των τιμών που καταβάλλονται εδώ ήταν ανεπάρκειες. Έτσι ώστε ήταν μια γρήγορη χαμηλό επίπεδο ματιά σε ό, τι μπορεί να προκύψουν προβλήματα τώρα που έχουμε να έχουν πρόσβαση σε μνήμη υπολογιστή. Αλλά ένα άλλο πρόβλημα που ήδη σκόνταψε τη Δευτέρα ήταν μόνο η αναποτελεσματικότητα από μία συνδεδεμένη λίστα. Είμαστε πίσω σε γραμμικό χρόνο. Δεν έχουμε πλέον ένα συνεχόμενο πίνακα. Δεν έχουμε τυχαίας προσπέλασης. Δεν μπορούμε να χρησιμοποιήσουμε πλατεία συμβολισμός βραχίονα. Έχουμε κυριολεκτικά πρέπει να χρησιμοποιήσετε ένα βρόχο while όπως αυτό που έγραψα πριν από λίγο. Αλλά τη Δευτέρα, εμείς ισχυρίστηκε ότι μπορούμε σέρνονται πίσω στη σφαίρα της αποτελεσματικότητας επιτυγχάνοντας κάτι που είναι λογαριθμική ίσως, ή καλύτερα ακόμα, ίσως ακόμα και κάτι που είναι λεγόμενη σταθερά χρόνου. Λοιπόν, πώς μπορούμε να το κάνουμε αυτό με την χρήση αυτών των νέων εργαλεία, αυτές οι διευθύνσεις, οι δείκτες, threading και τα πράγματα του δικού μας; Λοιπόν, ας υποθέσουμε ότι Εδώ, αυτά είναι ένα μάτσο των αριθμών που θέλετε να αποθηκεύσετε σε ένα δομή των δεδομένων και την αναζήτηση αποτελεσματικά. Πρέπει οπωσδήποτε να κάνετε rewind σε εβδομάδα δύο, να ρίξει αυτά σε μια σειρά, και να κάνετε χρήση της δυαδικής αναζήτησης. Διαίρει και βασίλευε. Και στην πραγματικότητα γράψατε δυαδική αναζήτηση στο PSET3, όπου θα εφαρμοστεί το πρόγραμμα εύρημα. Αλλά ξέρετε τι. Υπάρχει το είδος της μια πιο έξυπνος τρόπος για να γίνει αυτό. Είναι λίγο πιο εξελιγμένα και ίσως μας επιτρέπει να δούμε γιατί δυαδικό αναζήτησης είναι τόσο πολύ πιο γρήγορα. Κατ 'αρχάς, ας εισάγουν η έννοια ενός δέντρου. Που αν και σε δέντρα πραγματικότητα το είδος του μεγαλώνουν σαν αυτό, στον κόσμο των υπολογιστών επιστήμη που το είδος του μεγαλώνουν προς τα κάτω σαν ένα οικογενειακό δέντρο, όπου έχετε παππούδες σας ή μεγάλη παππούδες και γιαγιάδες ή οτιδήποτε στην κορυφή, τον πατριάρχη και η γυναίκα αρχηγός φυλής της οικογένειας, μόνο ένα λεγόμενη ρίζα, κόμβος, παρακάτω που είναι τα παιδιά της, κάτω από το οποίο είναι παιδιά της, ή απόγονοι του γενικότερα. Και ο καθένας κρέμεται από το κάτω μέρος της οικογένειας δέντρο, εκτός του ότι η νεότερος στην οικογένεια, Μπορείτε επίσης απλά να είναι γενικά ονομάζονται τα φύλλα του δέντρου. 

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

Έτσι τι είναι ωραίο σε μια δυαδικό δένδρο αναζήτησης, είναι ότι το ένα, μπορούμε να την εφαρμόσουν με ένα struct, όπως ακριβώς αυτό. Και ακόμα κι αν είμαστε ρίχνουν παρτίδες των δομών σε σας, ότι είναι κάπως διαισθητική τώρα ελπίζουμε. Η σύνταξη είναι ακόμα σίγουροι για απόκρυφες, αλλά τα περιεχόμενα ενός κόμβου σε αυτό context-- και κρατάμε χρησιμοποιώντας τη λέξη κόμβο, είτε πρόκειται για ένα ορθογώνιο στην οθόνη ή έναν κύκλο, είναι μερικά μόνο από γενική δοχείο, σε αυτή την περίπτωση ενός δέντρου, όπως εκείνη είδαμε, χρειαζόμαστε έναν ακέραιο σε κάθε ένα από τους κόμβους και στη συνέχεια θα πρέπει δίποντα κατάδειξης προς τα αριστερά παιδιού και το δικαίωμα του παιδιού, αντίστοιχα. Έτσι, αυτό είναι το πώς θα μπορούσαμε εφαρμόσουν ότι σε μια struct. Και πώς θα μπορούσε να μπορώ να εφαρμόσουν τον κωδικό; Λοιπόν, ας ρίξουμε μια γρήγορη ματιά σε αυτό το μικρό παράδειγμα. Δεν είναι λειτουργική, αλλά έχω αντιγραφεί και επικολληθεί αυτή τη δομή. Και αν η λειτουργία μου για ένα δυαδικό δέντρο αναζήτησης ονομάζεται αναζήτηση, και αυτό παίρνει δύο επιχειρήματα, ένας ακέραιος Ν και ένα δείκτη σε ένα κόμβο, έτσι ένα δείκτη στο δέντρο ή ένας δείκτης στη ρίζα ενός δέντρου, πώς μπορώ να πάω για την αναζήτηση για το Ν; Λοιπόν, πρώτα, γιατί είμαι που ασχολούνται με δείκτες, Πάω να κάνω μια επιταγή λογική. Αν ίσων δέντρο ισούται με null, είναι Ν σε αυτό το δέντρο ή όχι σε αυτό το δέντρο; Δεν μπορεί να είναι, σωστά; Αν είμαι παρελθόν null, δεν υπάρχει τίποτα εκεί. Θα μπορούσαμε απλώς να τυφλά λένε επιστρέφει false. Αν μου δώσεις τίποτα, εγώ σίγουρα δεν μπορεί να βρείτε οποιοδήποτε αριθμό Ν Λοιπόν, τι άλλο μπορεί να μου ελέγχει τώρα; Πάω να πω και άλλο αν το Ν είναι λιγότερο από ό, τι είναι στο κόμβο του δένδρου ότι έχω παραδοθεί Ν αξία. Με άλλα λόγια, εάν ο αριθμός είμαι ψάχνουν, N, είναι μικρότερο από τον κόμβο ότι κοιτάω. Και ο κόμβος Ψάχνω σε ονομάζεται δέντρο, και ανάκληση από το προηγούμενο παράδειγμα για να πάρει την τιμή σε ένα δείκτη, Μπορώ να χρησιμοποιήσω το συμβολισμό βέλος. Έτσι, αν το Ν είναι μικρότερο από το βέλος δέντρο Ν, θέλω να πάω εννοιολογικά αριστερά. Πώς μπορώ να εκφράζουν τα αριστερά η αναζήτηση; Για να είμαι σαφής, αν αυτό είναι η εν λόγω εικόνα, και έχω περάσει ότι κορυφαιους arrow ότι είναι στραμμένο προς τα κάτω. Αυτός είναι ο δείκτης δέντρο μου. Είμαι δείχνει στη ρίζα του δέντρου. Και ψάχνω για παράδειγμα, για ο αριθμός 44, αυθαίρετα. Είναι 44 ή μικρότερη μεγαλύτερη από 55 προφανώς; Γι 'αυτό είναι λιγότερο από ό, τι. Και έτσι αυτή η προϋπόθεση δεν ισχύει αν. Έτσι εννοιολογικά, τι θέλω να αναζήτηση Επόμενο αν ψάχνω για 44; Ναι; 

Ακριβώς, θέλω να αναζήτηση στο αριστερό παιδί, ή το αριστερό υπο-δέντρο αυτής της εικόνας. Και στην πραγματικότητα, επιτρέψτε μου μέσα η εικόνα εδώ κάτω για μια στιγμή, δεδομένου ότι Δεν μπορώ να το μηδέν αυτό. Αν αρχίσω εδώ στο 55, και Γνωρίζω ότι η τιμή 44 Ψάχνω για να η αριστερά, είναι το είδος σαν λυσσασμένο τον τηλεφωνικό κατάλογο στο το μισό ή το σχίσιμο του δέντρου στο μισό. Δεν έχω πλέον να νοιάζονται για όλη αυτή μισο του δέντρου. Και όμως, περιέργως από την άποψη της δομή, αυτό το πράγμα εδώ ότι ξεκινά με 33, ότι η ίδια η είναι ένα δυαδικό δένδρο αναζήτησης. Είπα τη λέξη αναδρομικό πριν, διότι Πράγματι, αυτό είναι μια δομή δεδομένων που εξ ορισμού είναι αναδρομική. Μπορεί να έχετε ένα δέντρο που είναι αυτό μεγάλο, αλλά κάθε ένα από τα παιδιά του αντιπροσωπεύει ένα δέντρο λίγο μικρότερο. Αντί να είναι ο παππούς ή γιαγιά, τώρα είναι απλά η μαμά or-- Δεν μπορώ να μην say-- μαμά ή τον μπαμπά, ότι θα ήταν παράξενο. Αντ 'αυτού τα δύο παιδιά εκεί θα ήταν σαν τον αδελφό και αδελφών. Μια νέα γενιά του οικογενειακού δέντρου. Αλλά δομικά, είναι η ίδια ιδέα. Και αποδεικνύεται έχω μια λειτουργία με την οποία μπορώ να αναζητήσω μια δυαδική αναζήτηση δέντρο. Ονομάζεται αναζήτησης. Ψάχνει για Ν στο δέντρο βέλος αριστερά αλλιώς εάν Ν είναι μεγαλύτερη από την τιμή ότι είμαι σήμερα σε. 55 στην ιστορία πριν από λίγο. Έχω μια λειτουργία που ονομάζεται αναζήτησης που μπορώ μόνο Ν περάσει αυτό και αναδρομικά αναζήτηση η υπο-δέντρο και μόλις επιστροφή όποια και αν είναι η απάντηση. Αλλιώς έχω κάποια τελευταία περίπτωση βάση εδώ. 

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

Λοιπόν, τι άλλα προβλήματα μπορούμε να λύσουμε; Έτσι, ένα γρήγορο βήμα μακριά από δέντρα για μια στιγμή. Εδώ είναι, ας πούμε, τη γερμανική σημαία. Και είναι σαφές ότι υπάρχει μοτίβο σε αυτήν τη σημαία. Και υπάρχουν πολλά σημαίες στον κόσμο που είναι τόσο απλό όσο αυτό σε όρους χρωμάτων και σχεδίων τους. Αλλά ας υποθέσουμε ότι αυτό αποθηκεύεται ως ένα .gif, Ή σε μορφή JPEG ή bitmap, ή ping, οποιαδήποτε γραφική μορφή αρχείου με το οποίο είστε εξοικειωμένοι, μερικά από τα οποία είμαστε παίζουν με στο PSET4. Αυτό δεν φαίνεται να αποθηκεύσει αξιόλογη μαύρο pixel, μαύρο pixel, μαύρο pixel, τελεία, τελεία, τελεία, ένα σωρό μαύρα pixel για πρώτη scanline, ή γραμμή, τότε ένα σωρό το ίδιο, τότε ένα σωρό του ίδιου, και στη συνέχεια μια σωρό από κόκκινα εικονοστοιχεία, κόκκινα εικονοστοιχεία, κόκκινα εικονοστοιχεία, τότε ένας ολόκληρος δέσμη των κίτρινα pixels, κίτρινο, σωστά; 

Υπάρχει τέτοια αναποτελεσματικότητα εδώ. Πώς θα διαισθητικά συμπιέσει τη γερμανική σημαία όταν η εφαρμογή της ως ένα αρχείο; Όπως και το είδος των πληροφοριών δεν μπορούμε να κόπο αποθήκευση στο δίσκο, προκειμένου για να μειώσετε το μέγεθος του αρχείου μας από παρόμοια ένα megabyte σε kilobyte, κάτι μικρότερα; Όπου βρίσκεται η απόλυση εδώ να είναι σαφές; Τι μπορείτε να κάνετε; Ναι; Ακριβώς. Γιατί δεν θυμόμαστε όχι το χρώμα του κάθε pixel καταριέται όπως ακριβώς κάνετε στο PSET4 με τη μορφή αρχείου bitmap, γιατί δεν αντιπροσωπεύουν μόλις το αριστερότερη στήλη εικονοστοιχείων, για παράδειγμα μια δέσμη των μαύρων pixels, ένα μάτσο κόκκινο, και ένα σωρό κίτρινο, και στη συνέχεια απλά με κάποιο τρόπο να κωδικοποιεί το ιδέα Επαναλάβετε αυτήν 100 φορές ή επαναλάβετε αυτό 1.000 φορές; Όταν το 100 ή 1.000 είναι απλά ένας ακέραιος αριθμός, έτσι ώστε να μπορεί να περάσει με ένα μόνο αριθμό αντί εκατοντάδες ή χιλιάδες πρόσθετων pixels. Και πράγματι, αυτό είναι το πώς εμείς θα μπορούσε να συμπιέσει τη γερμανική σημαία. Και Τώρα τι γίνεται με τη γαλλική σημαία; Και λίγο κάποιο είδος ψυχική άσκηση, η οποία σημαίας μπορεί να συμπιεστεί περισσότερο στο δίσκο; Η γερμανική σημαία ή η γαλλική σημαία, αν πάρουμε αυτή την προσέγγιση; Η γερμανική σημαία, επειδή υπάρχει περισσότερο οριζόντιες απολύσεις. Και από το σχεδιασμό, πολλά γραφικά αρχείο μορφές όντως λειτουργούν ως γραμμές σάρωσης οριζόντια. Θα μπορούσε να λειτουργήσει κάθετα, ακριβώς ανθρωπότητα αποφάσισε χρόνια πριν ότι θα γενικά σκέφτομαι σειρά πραγμάτων από σειρά αντί ανά στήλη. Έτσι, πράγματι, αν ήταν να εξετάσουμε το αρχείο το μέγεθος της μια γερμανική σημαία και ένα γαλλικό σημαία, εφ 'όσον η ανάλυση είναι το ίδιο, το ίδιο πλάτος και ύψος, αυτό Εδώ πρόκειται να είναι μεγαλύτερο, γιατί Πρέπει να επαναλάβω τον εαυτό σας τρεις φορές. Θα πρέπει να καθορίσετε μπλε, επαναλάβετε τον εαυτό σας, το λευκό, επαναλαμβάνω τον εαυτό σας, το κόκκινο, επαναλάβετε τον εαυτό σας. Μπορείτε όχι μόνο να πάνε όλα ο τρόπος προς τα δεξιά. Και, παρεμπιπτόντως, να κάνει καταργήστε την συμπίεση είναι παντού, αν αυτά είναι τέσσερα καρέ από ένα video-- σας Ίσως να θυμάστε ότι μια ταινία ή βίντεο είναι γενικά όπως 29 ή 30 καρέ ανά δευτερόλεπτο. Είναι σαν ένα μικρό κτύπημα βιβλίο όπου θα απλά δείτε την εικόνα, εικόνα, εικόνα, εικόνα, εικόνα, απλά σούπερ γρήγορα ώστε να μοιάζει με οι ηθοποιοί στην οθόνη κινούνται. Εδώ είναι ένα αγριομελισσών για πάνω από ένα μπουκέτο λουλούδια. Και αν και θα μπορούσε να είναι το είδος του δύσκολο να δει κανείς με την πρώτη ματιά, το μόνο πράγμα κινείται Αυτή η ταινία είναι η μέλισσα. 

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

Αλλά πώς μπορείτε να συμπιέσετε κείμενο; Πώς θα πάτε για τη συμπίεση κειμένου; Λοιπόν, κάθε ένα από τους χαρακτήρες Ascii είναι ένα byte, ή οκτώ κομμάτια. Και αυτό είναι το είδος των χαζή, σωστά; Επειδή ίσως τύπου Α και Ε και Ι και Ο και U πολύ πιο συχνά από ό, τι, όπως W ή Q ή Ζ, ανάλογα με τη γλώσσα στην οποία είστε γραπτώς βεβαίως. Και έτσι γιατί είμαστε χρησιμοποιώντας οκτώ bits για κάθε γράμμα, συμπεριλαμβανομένων των λιγότερο δημοφιλή γράμματα, έτσι δεν είναι; Γιατί να μην χρησιμοποιούν λιγότερα bits για τα σούπερ δημοφιλής γράμματα, όπως Ε, τα πράγματα να μαντέψετε για πρώτη φορά στην Τροχός της Τύχης, και να χρησιμοποιούν περισσότερα bits για τα λιγότερο δημοφιλή γράμματα; Γιατί; Επειδή είμαστε ακριβώς πρόκειται να χρησιμοποιούν λιγότερο συχνά. 

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

Ι; Ι; Ή τι about-- ή εγώ; Ίσως ήταν μόνο δύο δεξιά της Ε; Έτσι υπάρχει αυτό το πρόβλημα της decodability με Morse κώδικα, σύμφωνα με την οποία, εκτός αν η άτομο που σας έστειλε το μήνυμα στην πραγματικότητα διακόπτει έτσι μπορείτε να ταξινομήσετε του δουν ή να ακούσουν τα κενά μεταξύ των γραμμάτων, δεν είναι επαρκής μόνο για να στείλετε ένα ρεύμα από μηδενικά και μονάδες, ή τελείες και παύλες, επειδή υπάρχει ασάφεια. Ε είναι μια μοναδική τελεία, οπότε αν δείτε δύο τελείες ή να ακούσετε δύο τελείες, ίσως είναι δυο Ε ή ίσως είναι ένα I. Έτσι, χρειαζόμαστε ένα σύστημα το οποίο είναι ένα λίγο πιο έξυπνοι από αυτό. Έτσι, ένας άνθρωπος που ονομάζεται Huffman χρόνια Πριν ήρθε με ακριβώς αυτό. Γι 'αυτό ακριβώς πρόκειται να λάβει μια γρήγορη ματιά κατά πόσο τα δέντρα είναι συναφές με αυτό. Ας υποθέσουμε ότι αυτή είναι κάποια ηλίθιο μήνυμα που θέλετε να στείλετε, που αποτελείται από μόλις Α, Β, Γ D's και της Ε, αλλά υπάρχει πολλή απόλυσης εδώ. Δεν είναι γραφτό να είναι η αγγλική. Δεν είναι κρυπτογραφημένα. Είναι απλά ένα ηλίθιο μήνυμα με πολλές επαναλήψεις. Έτσι, αν πραγματικά μετράνε όλα τα Α, Β, Γ, D, και Ε, είναι εδώ είναι η συχνότητα. 20% των γραμμάτων είναι Α, το 45% από τα γράμματα είναι Ε, καθώς και τρεις άλλες συχνότητες. Εμείς υπολογίζονται μέχρι εκεί με το χέρι και έκανε ακριβώς τα μαθηματικά. 

Έτσι αποδεικνύεται ότι Huffman, πριν από λίγο καιρό, συνειδητοποίησε ότι, ξέρετε τι, αν μπορώ να ξεκινήσω κτίριο Ένα δέντρο ή δάσος από δέντρα, αν θέλετε, ως εξής, μπορώ να κάνω το εξής. Πάω να δώσει σε κάθε κόμβο από τις επιστολές που με νοιάζει και θα πάω να αποθηκεύσετε εντός αυτού του κόμβου οι συχνότητες ως πλωτό σημείο τιμή, ή θα μπορούσατε να χρησιμοποιήσετε μια Ν, πάρα πολύ, αλλά θα χρησιμοποιούν μόνο ένα πλωτήρα εδώ. Και ο αλγόριθμος που πρότεινε ότι θα είναι λαμβάνουν αυτό το δάσος του ενιαίου κόμβου δέντρα, τόσο σούπερ δέντρα βραχείας περιόδου, και ξεκινάτε τη σύνδεση τους με νέες ομάδες, νέους γονείς, αν θέλετε. Και το κάνετε αυτό επιλέγοντας το δύο μικρότερα συχνότητες σε μια στιγμή. Έτσι πήρα 10% και 10%. Μπορώ να δημιουργήσω ένα νέο κόμβο. Και καλώ Ο νέος κόμβος 20%. 

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

Και έτσι αυτό που προτείνεται είναι Hoffman, αν θέλετε να αντιπροσωπεύουν ένα Β, αντί να αντιπροσωπεύουν τον αριθμό 66 ως ένα αρχείο ASCII το οποίο είναι οκτώ ολόκληρο bits, ξέρετε τι, ακριβώς κατάστημα το πρότυπο μηδέν, μηδέν, μηδέν, μηδέν, επειδή αυτό είναι το μονοπάτι από το δέντρο μου, κ δέντρο Huffman του, στο φύλλο από τη ρίζα. Αν θέλετε να αποθηκεύσετε το Ε, αντιθέτως, δεν στείλει οκτώ bits που αποτελούν Ε Αντ 'αυτού, να στείλετε ποιο μοτίβο των bits; Ένα. Και τι είναι καλό για αυτό είναι ότι το E είναι η πιο δημοφιλής επιστολή, και προσπαθείτε να χρησιμοποιήσετε το συντομότερη κώδικα για αυτό. Η επόμενη πιο δημοφιλή επιστολή μοιάζει να Ήταν A. Και έτσι πόσα bits έκανε να προτείνει τη χρήση γι 'αυτό; Μηδέν, ένα. 

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

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

Τώρα οι στοίβες μεγάλωναν, η οποία Είναι μια σκόπιμη σχεδιασμό πράγμα εδώ. Αλλά τι άλλο θα μπορούσε να κάνω; Έτσι, στην πραγματικότητα, εδώ έχουμε ένα μάτσο παλιά σχολικά βιβλία εξετάσεις. Ας υποθέσουμε ότι ένα μάτσο ονόματα μαθητές είναι εδώ. Εδώ είναι ένα μεγαλύτερο πίνακα κατακερματισμού. Αντί των τεσσάρων κάδων, Έχω, ας πούμε 26. Και δεν ήθελε να πάει να δανειστεί 26 τα πράγματα από το εξωτερικό [? Annenberg?], Έτσι Εδώ είναι πέντε, που αντιπροσωπεύουν Α έως Ζ Κι αν δείτε ένα μαθητή του οποίου το όνομα αρχίζει με Α, Πάω να του κουίζ ή να την βάλει εκεί. Αν κάποιος ξεκινά με C, πάνω από εκεί, A-- στην πραγματικότητα, δεν ήθελε να το κάνει αυτό. Β πηγαίνει εδώ. Έτσι έχω Α και Β και C. Και Τώρα εδώ είναι ένα άλλο μαθητή. Αλλά αν αυτό πίνακα κατακερματισμού είναι υλοποιείται με μια σειρά, Είμαι το είδος του βιδωθεί σε αυτό το σημείο, έτσι δεν είναι; Ι το είδος πρέπει να θέσει αυτό το κάπου. 

Έτσι, ένας τρόπος που μπορώ να λύσει αυτό, όλα δεξιά, Α είναι απασχολημένος, Β είναι απασχολημένος, C είναι απασχολημένος. Πάω να τον βάλουν στο Δ Έτσι, στο Κατ 'αρχάς, έχω τυχαία άμεση πρόσβαση σε καθένα από τους κάδους για τους μαθητές. Αλλά τώρα αυτό είναι το είδος των αποκεντρωμένων σε κάτι γραμμικό, γιατί αν θέλετε να ψάξετε για κάποιον του οποίου το όνομα αρχίζει με Α, μπορώ να ελέγξω εδώ. Αλλά αν αυτό δεν είναι η A φοιτητής Ψάχνω για, Ι το είδος πρέπει να αρχίσετε να ελέγχετε οι κάδοι, γιατί ό, τι έκανα Ήταν ένα είδος γραμμικά εξετάσουν τη δομή των δεδομένων. Ένας ηλίθιος τρόπος για να πούμε απλά κοιτάξτε για το πρώτο διαθέσιμο άνοιγμα, και να θέσει ως σχέδιο Β, να το πω έτσι, ή το σχέδιο Α στην περίπτωση αυτή, η αξία στη θέση αυτή αντ 'αυτού. Αυτό είναι ακριβώς έτσι ώστε αν έχετε πήρε 26 θέσεις και δεν φοιτητών με την επωνυμία Q ή Ζ, ή κάτι παρόμοιο ότι, τουλάχιστον είστε με τη χρήση του χώρου. 

Αλλά έχουμε ήδη δει περισσότερα έξυπνες λύσεις εδώ, σωστά; Τι θα κάνετε αντί εάν έχετε μια σύγκρουση; Αν δύο άνθρωποι έχουν το όνομα Α, τι θα έχουν μια πιο έξυπνη και άνω διαισθητική λύση όχι μόνο Μια θέση όπου D είναι υποτίθεται ότι είναι; Γιατί δεν μπορώ ακριβώς να πάτε εκτός [? Annenberg?], όπως malloc, έναν άλλο κόμβο, το έθεσε εδώ, και στη συνέχεια βάλτε ότι ένας μαθητής εδώ. Έτσι ώστε να έχουν ουσιαστικά κάποιο είδος μιας συστοιχίας, ή ίσως και πιο κομψά, όπως είμαστε Αρχίζουμε να βλέπουμε μια συνδεδεμένη λίστα. 

Και έτσι ένα πίνακα κατακερματισμού είναι μια δομή ότι θα μπορούσε να μοιάζει ακριβώς όπως αυτό, αλλά πιο έξυπνα, σας κάτι που ονομάζεται Ξεχωριστές αλυσίδες, όπου ένα πίνακα κατακερματισμού απλούστατα είναι ένας πίνακας, κάθε ένα από του οποίου τα στοιχεία δεν είναι ένας αριθμός, είναι η ίδια συνδεδεμένη λίστα. Έτσι ώστε να μπορείτε να πάρετε σούπερ γρήγορη πρόσβαση αποφασίζουν πού να hash αξία σας. Μοιάζει πολύ με τον κάρτες παράδειγμα, Έκανα εξαιρετικά γρήγορες αποφάσεις. Καρδιές πηγαίνει εδώ, τα διαμάντια πηγαίνει εδώ. Ίδιο εδώ, Α πηγαίνει εδώ, Δ πηγαίνει εδώ, Β πηγαίνει εδώ. Έτσι σούπερ γρήγορη ματιά-ups, και εάν τυχαίνει να τρέχει σε μια υπόθεση όπου έχεις συγκρούσεις, δύο οι άνθρωποι με το ίδιο όνομα, καλά τότε μπορείτε απλά να αρχίσετε τα συνδέουν μεταξύ τους. Και ίσως να τους κρατήσει ταξινομημένο αλφαβητικά, ίσως όχι. Αλλά τουλάχιστον τώρα έχουμε τον δυναμισμό. Έτσι, από τη μία πλευρά έχουμε σούπερ γρήγορο χρονική σταθερά, και το είδος του γραμμικού χρόνου που εμπλέκονται, αν αυτές συνδέονται με τις λίστες να αρχίσει να πάρει λίγο καιρό. 

Έτσι, αυτό το είδος της μια ανόητη, geeky αστείο χρόνια. Στο CS50 hack-a-thon, όταν οι μαθητές κάνουν check-in, μερικά TF ή CA κάθε χρόνο νομίζει ότι είναι αστείο να ανεχτούμε ένα σημάδι σαν αυτό, όπου μόνο σημαίνει ότι εάν το όνομά σας ξεκινά με ένα Α, πάει με αυτόν τον τρόπο. Αν το όνομα σας ξεκινά με Β, πηγαίνετε this-- ΟΚ, Είναι αστείο ίσως αργότερα στο εξάμηνο. Αλλά υπάρχει και μια άλλη τρόπος για να γίνει αυτό, πάρα πολύ. Γύρνα πίσω σε αυτό. 

Έτσι υπάρχει αυτή η δομή. Και αυτή είναι η τελευταία μας δομή για σήμερα, το οποίο είναι κάτι που ονομάζεται trie. T-R-Ι-Ε, η οποία για κάποιο λόγο είναι μικρή για την ανάκτηση, αλλά αυτό λέγεται trie. Έτσι, ένα trie είναι μια άλλη ενδιαφέρουσα αμάλγαμα από πολλές από αυτές τις ιδέες. Είναι ένα δέντρο, που έχουμε δει στο παρελθόν. Δεν είναι ένα δυαδικό δένδρο αναζήτησης. Είναι ένα δέντρο με οποιοδήποτε αριθμό των παιδιών, αλλά κάθε ένα από τα παιδιά σε ένα trie είναι ένας πίνακας. Μια σειρά μεγέθους, δηλαδή, 26 ή ίσως και 27 αν θέλετε να υποστηρίξετε ενωτικό ονόματα ή σε αποστρόφους τα ονόματα των ανθρώπων. 

Και έτσι αυτή είναι μια δομή δεδομένων. Και αν δει κανείς από την κορυφή προς τα κάτω, σαν να κοιτάξουμε την κορυφή κόμβο εκεί, Μ, είναι που δείχνουν προς το αριστερότερο πράγμα εκεί, η οποία στη συνέχεια τα Α, Χ, W, E, L, L. Αυτό είναι απλά μια δομή δεδομένων που αυθαίρετα αποθηκεύει τα ονόματα των ανθρώπων. Και Maxwell αποθηκεύονται μόνο μετά από ένα μονοπάτι της συστοιχίας σε συστοιχίας σε σειρά. Αλλά τι είναι καταπληκτικό για μια trie είναι ότι, λαμβάνοντας υπόψη ότι μια συνδεδεμένη λίστα και ακόμη μια σειρά, το καλύτερο που έχουμε πάρει ποτέ είναι γραμμικό χρόνο ή λογαριθμική χρόνο ψάχνοντας κάποιος επάνω. Σε αυτή τη δομή δεδομένων μιας trie, εάν δομή δεδομένων μου έχει ένα όνομα σε αυτό και ψάχνω για Maxwell, είμαι Θα τον βρείτε αρκετά γρήγορα. Απλά κοιτάξτε για το Μ-Α-Χ-W-Ε-Ε-Ε. Αν αυτό δομή δεδομένων, αντιθέτως, αν το Ν είναι ένα εκατομμύριο, αν υπάρχει εκατομμύρια ονόματα σε αυτή τη δομή δεδομένων, Maxwell είναι ακόμα πρόκειται να είναι ανιχνεύσιμο μετά από μόλις Μ-Α-Χ-W-Ε-Ε-Ε βήματα. Και τα βήματα David-- D-A-V-I-D. Με άλλα λόγια, με την οικοδόμηση μια δομή δεδομένων που είναι πήρε όλες αυτές τις συστοιχίες, τα οποία όλα αυτοσυντηρηθούν τυχαίας προσπέλασης, Μπορώ να αρχίσετε να ψάχνετε μέχρι ανθρώπων όνομα χρησιμοποιώντας ένα χρονικό διάστημα που είναι ανάλογη με τον αριθμό δεν πράγματα στη δομή δεδομένων, ένα εκατομμύριο, όπως τα υπάρχοντα ονόματα. Ο χρόνος που χρειάζεται για να μου βρείτε M-A-X-W-E-L-L σε αυτή τη δομή δεδομένων είναι ανάλογη όχι προς τα μέγεθος της δομής των δεδομένων, αλλά με το μήκος του ονόματος. Και πραγματικά η ονόματα ψάχνουμε μέχρι δεν πρόκειται ποτέ να είναι τρελό καιρό. Ίσως κάποιος να έχει ένα χαρακτήρα 10 αναφέρουμε, 20 το όνομα του χαρακτήρα. Είναι σίγουρα πεπερασμένα, σωστά; Υπάρχει ένας άνθρωπος στη Γη που έχει τη μεγαλύτερη δυνατή όνομα, αλλά αυτό το όνομα είναι μια σταθερά Μήκος αξία, έτσι δεν είναι; Αυτό δεν μεταβάλλεται με οποιαδήποτε έννοια. Έτσι, με αυτόν τον τρόπο, έχουμε επιτυγχάνεται μια δομή δεδομένων που είναι σταθερά χρόνου look-up. Θα έχει λάβει ορισμένα μέτρα ανάλογα με το μήκος της εισόδου, αλλά όχι ο αριθμός του ονόματος στη δομή δεδομένων. Έτσι, αν έχουμε διπλασιάσει τον αριθμό των ονομάτων το επόμενο έτος από ένα δισεκατομμύριο σε δύο δισεκατομμύρια, διαπίστωση Maxwell πρόκειται να πάρει ακριβώς τον ίδιο αριθμό από επτά βήματα να τον βρει. Και έτσι φαίνεται να έχουμε επιτύχει άγιο δισκοπότηρο μας χρόνου λειτουργίας. 

Έτσι, μερικές γρήγορες ανακοινώσεις. Quiz μηδέν έρχεται επάνω. Περισσότερα για αυτό στην ιστοσελίδα του μαθήματος κατά τις επόμενες δύο ημέρες. Δευτέρα lecture-- είναι αργία εδώ στο Harvard τη Δευτέρα. Δεν είναι στο New Haven, έτσι παίρνουμε την κατηγορία προς Νιου Χέιβεν για διάλεξη την Δευτέρα. Τα πάντα θα κινηματογραφηθεί και μεταδοθεί ζωντανά ως συνήθως, αλλά ας τελειώσει σήμερα με ένα δεύτερο συνδετήρα 30 που ονομάζεται «βαθιές σκέψεις" από Daven Farnham, η οποία εμπνεύστηκε το περασμένο έτος μέχρι το Σάββατο «Βαθιές σκέψεις" Night Live της από τον Jack Handy, η οποία θα πρέπει να κάνει τώρα νόημα. 

ΦΙΛΜ: Και τώρα, "Deep Σκέψεις "από Daven Farnham. Πίνακας κατακερματισμού. 

ΟΜΙΛΗΤΗΣ 1: Εντάξει, αυτό είναι για τώρα. Θα σας δούμε την επόμενη εβδομάδα. 

DOUG: Για να το δείτε σε δράση. Έτσι, ας ρίξουμε μια ματιά σε αυτό τώρα. Έτσι, εδώ, έχουμε μια σειρά αδιαχώριστα. 

IAN: Doug, μπορείτε να προχωρήσετε και επανεκκίνηση αυτό για μόνο ένα δευτερόλεπτο, παρακαλώ. Εντάξει, κάμερες τροχαίο, έτσι δράσης, όταν είστε έτοιμοι, Νταγκ, εντάξει; DOUG: Εντάξει, έτσι αυτό που έχουμε εδώ είναι μια σειρά αδιαχώριστα. Και έχω χρωματιστά όλα τα στοιχεία κόκκινο για να δείξει ότι είναι, στην πραγματικότητα, αδιαχώριστα. Έτσι, υπενθυμίζουν ότι το πρώτο πράγμα που κάνουμε είναι να ξεκαθαρίσουμε το αριστερό μισό του πίνακα. Τότε θα λύσουμε το δικαίωμα μισο της συστοιχίας. Και ya-δα, ya-δα, ya-da, Τους συγχωνεύονται. Και έχουμε μια εντελώς ταξινομημένο πίνακα. Έτσι, αυτό είναι το πώς λειτουργεί ταξινόμηση με συγχώνευση. 

IAN: Πω πω, whoa, whoa, κομμένα, κομμένα, κομμένα, κομμένα. Doug, μπορείτε όχι μόνο να ya-δα, ya-da, Ya-ντα, το δρόμο σας μέσα από τη συγχώνευση του είδους. 

DOUG: έκανα ακριβώς. Είναι εντάξει. Είμαστε καλοί να πάτε. Ας κρατήσει το τροχαίο. Έτσι κι αλλιώς, 

IAN: Θα πρέπει να εξηγήσουν πληρέστερη από αυτό. Αυτό απλά δεν είναι αρκετό. DOUG: Ian, δεν το κάνουμε Πρέπει να πάμε πίσω σε ένα. Είναι εντάξει. Έτσι κι αλλιώς, αν συνεχίσουμε με merge-- Ian, είμαστε στη μέση των γυρισμάτων. 

IAN: Ξέρω. Και δεν μπορούμε απλώς να ya-δα, ya-da, Ya-da, μέσα από την όλη διαδικασία. Θα πρέπει να εξηγήσει πώς η δύο πλευρές να συγχωνεύονται. 

DOUG: Αλλά έχουμε ήδη εξήγησε πώς τα δύο sides-- 

IAN: Έχετε μόλις φαίνεται τους μια σειρά συγχώνευσης. DOUG: Ξέρουν τη διαδικασία. Είναι μια χαρά. Έχουμε περάσει πάνω από δέκα φορές. 

IAN: Απλά παραληφθεί σωστά πάνω του. Εμείς πάμε πίσω σε ένα, δεν μπορείς Ya-δα, ya-δα πάνω του. Εντάξει, πίσω σε ένα. 

DOUG: Πρέπει να πάω πίσω μέσω όλων των διαφανειών; Θεέ μου. Είναι σαν έκτη φορά, Ian. Είναι εντάξει. 

IAN: Εντάξει. Είστε έτοιμοι? Εξαιρετική. Δράση.