DAVID MALAN: Εντάξει. Καλώς ήρθατε και πάλι στο CS50. Αυτή είναι η αρχή της εβδομάδας 8. Και υπενθυμίζουν ότι το πρόβλημα σύνολο 5 έληξε με ένα μικρό κομμάτι της μια πρόκληση. Έτσι, με την προϋπόθεση να ανακτηθεί όλες σας Μέλη διδασκαλίας και φωτογραφίες της CA στο αρχείο card.raw, θα είναι επιλέξιμες να βρούμε τώρα όλους εκείνους τους ανθρώπους, και ένας τυχερός νικητής θα φύγετε με ένα από αυτά τα πράγματα, η κίνηση άλμα συσκευής που μπορείτε να χρησιμοποιήσετε για την τελική έργα, για παράδειγμα. 

Αυτό, κάθε χρόνο, οδηγεί στην ένα κομμάτι της creepiness. Και έτσι αυτό που σκέφτηκα να κάνουμε είναι να μοιραστώ μαζί σας μερικές από τις σημειώσεις που έχουν πάει εμπρός και πίσω πάνω ο κατάλογος του προσωπικού των καθυστερήσεων. Για παράδειγμα, μόλις χθες το βράδυ, απόσπασμα unquote, από ένα από το προσωπικό μέλη, «είχα μόνο ένα χτύπημα φοιτητή την πόρτα μου για να τραβήξετε μια φωτογραφία μαζί μου. Stalkers, μπορώ να σας πω ». Ξεκίνησε αρκετά περιγραφική και στη συνέχεια κινηθήκαμε για να, μια ώρα περίπου αργότερα, "είχα μια φοιτητής με περιμένει μετά το τμήμα και είχε όλα τα ονόματα και τις φωτογραφίες μας σε μερικά φύλλα χαρτιού. «Εντάξει. Έτσι, οργανωμένη, αλλά δεν όλα αυτά ανατριχιαστικό ακόμα. 

Στη συνέχεια, "Ήμουν έξω από την πόλη αυτό το Σαββατοκύριακο, και όταν το πήρα πίσω, υπήρχε ένα στην μου υπνοδωμάτιο. »[γέλια] DAVID MALAN: Next απόσπασμα από το προσωπικό μέλος, "ένας φοιτητής ήρθε στο σπίτι μου Somerville στις τέσσερις το πρωί. "Next προσωπικού, «Πήρα στο ξενοδοχείο μου στο San Φρανσίσκο και ένας μαθητής περίμενε μου στο λόμπι με τρεις φωτογραφικές μηχανές DSLR. " Είδος της κάμερας. "Δεν είμαι καν για το προσωπικό αυτό το εξάμηνο, αλλά ένας μαθητής έσπασε στο σπίτι μου, αυτό πρωί και καταγράφεται το όλο θέμα με γυαλί Google. "Και τότε, τέλος, "Τουλάχιστον 12 άνθρωποι ήταν ανυπόμονα αναμονή για μένα όταν βγήκα από μου λιμουζίνα, και στη συνέχεια θα ξύπνησε. «Εντάξει. Έτσι, ανάμεσα στις φωτογραφίες, όπως μπορείτε να θυμάστε, είναι αυτός ο άνθρωπος εδώ, που σας θα μπορούσε να γνωρίζει, όπως Milo Μπανάνα, ο οποίος ζει με Lauren Carvalho, το κεφάλι μας διδασκαλίας Fellow. Ο Μάιλο, ο Milo, έλα εδώ αγόρι. Milo. Milo. Το μυαλό εσείς, φοράει Google Glass, έτσι θα σας δείξει όλα αυτά μετά. Έτσι, αυτό είναι Milo, αν θα θέλατε να να λάβει μια φωτογραφία μαζί του αργότερα. Αν θέλετε να κοιτάξει έξω στο κοινό εκεί. OK. Αυτό είναι καλό υλικό. Λοιπόν, Milo Μπανάνα. Ω, μην το κάνεις αυτό. 

[Γέλια] 

OK. Έτσι, μια λέξη, στη συνέχεια για το τι μέλλει γενέσθαι, γιατί όπως έχουμε αρχίσει να μετάβασης, Συγκεκριμένα αυτή την εβδομάδα, από C σε ένα περιβάλλον κειμένου γραμμής εντολών σε PHP και JavaScript και SQL και HTML και CSS σε μια web-based περιβάλλον, θα είμαστε εξοπλισμό σας με όλα τα περισσότερες γνώσεις για την δυνητικών τελικών σχεδίων. Προς το σκοπό αυτό, το μάθημα έχει παράδοση της διεξαγωγής σεμιναρίων που είναι εφαπτόμενο σε θέματα στην πορεία. Πάρα πολύ σχετίζονται με τον προγραμματισμό και την app ανάπτυξη και ούτω καθεξής, αλλά όχι απαραίτητα διερευνηθεί από δική του διδακτέα ύλη του μαθήματος. 

Έτσι, αν μπορεί να σας ενδιαφέρει σε ένα ή περισσότερα από τα σεμινάρια της φετινής χρονιάς, εγγραφείτε στο cs50.net/seminar. Υπάρχουν μεγάλα σεμινάρια σε cs50.net/seminars. Και στο ρόστερ μέχρι στιγμής για το τρέχον έτος είναι καταπληκτικές εφαρμογές Web με Ruby on Σιδηροτροχιές, η οποία είναι μια εναλλακτική λύση γλώσσα PHP. Υπολογιστική Γλωσσολογία. Εισαγωγή στην Ίο, η οποία είναι η πλατφόρμας που χρησιμοποιείται για το iPhone και iPad ανάπτυξη. JavaScript για Web Apps, θα καλύψουμε αυτό, αλλά σε αυτό το σεμινάριο, θα πάτε σε περισσότερες λεπτομέρειες. 

Άλμα κίνησης, οπότε θα έχουμε πραγματικά κάποια από τους φίλους μας από την κίνηση Leap, η ίδια η εταιρεία, μαζί μας. Αύριο, στην πραγματικότητα, για την παροχή ένα hands-on σεμινάριο, αν που σας ενδιαφέρουν. Meteor.js, μια εναλλακτική τεχνική για τη χρησιμοποιώντας JavaScript δεν είναι σε ένα πρόγραμμα περιήγησης, αλλά σε ένα διακομιστή. Node.js, η οποία είναι πάρα πολύ σε αυτό το πνεύμα, καθώς και. Κομψή σχεδίαση Android. Android είναι μια πολύ δημοφιλής εναλλακτική λύση σε iOS και Windows Phone και άλλες κινητές πλατφόρμες. Και Security Web ενεργητικής άμυνας. 

Έτσι, στην πραγματικότητα, αν θα θέλατε να συμμετάσχουν σε αυτό, επιτρέψτε μου να σημειώστε αυτό. Είμαστε στην ευχάριστη θέση να πω ότι τους φίλους μας στο Leap Πρόταση, η οποία είναι μια νεοσύστατη εταιρεία - Αυτή η συσκευή είναι πραγματικά μόλις ήρθε out πριν από λίγους μήνες - έχει δωρίσει ευγενικά 30 τέτοιες συσκευές στην τάξη για όσες φοιτητές, εάν θα θέλατε να δανειστεί το υλικό προς το τέλος του εξαμήνου και να το χρησιμοποιούν για ένα πραγματικό τελικό σχέδιο. Υποστηρίζουν μια σειρά από γλώσσες. Κανένας από αυτούς C, κανένας από αυτούς PHP, έτσι υλοποίηση ενός ή περισσότερων από αυτά τα σεμινάρια θα μπορούσε να αποδειχθεί ενδιαφέρον. Και όλα αυτά θα γυριστεί στη το γεγονός ότι δεν είστε σε θέση να παραστεί αυτοπροσώπως. Το πρόγραμμα θα ανακοινωθεί μέσω του email όπως στερεοποιηθεί δωμάτια. 

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

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

ΚΟΙΝΟ: Δυναμική μέγεθος. 

DAVID MALAN: Δυναμική μέγεθος. Έτσι, ενώ στην σειρά, θα πρέπει να γνωρίζουμε το μέγεθος της εκ των προτέρων, όταν να το διαθέσει. Σε συνδεδεμένη λίστα, δεν το κάνετε Πρέπει να γνωρίζετε ότι. Μπορείτε απλά malloc, ή, γενικότερα, διαθέσει ένα πρόσθετο κόμβο, να το πω έτσι, κάθε φορά που θα θέλετε να εισαγάγετε περισσότερα δεδομένα. Και ο κόμβος έχει προκαθορισμένο κανένα νόημα. Είναι απλά ένας γενικός όρος που περιγράφει κάποιο είδος του περιέκτη που είμαστε χρήση στη δομή των δεδομένων μας για να αποθηκεύσετε κάποιες σημείο ενδιαφέροντος, που στην προκειμένη περίπτωση που τυχαίνει να είναι ακέραιοι. 

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

ΚΟΙΝΟ: Απαιτεί περισσότερη μνήμη. 

DAVID MALAN: Απαιτεί περισσότερα μνήμης, πώς ακριβώς; 

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

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

Τι συμβαίνει με το χρόνο λειτουργίας του κάτι σαν αναζήτηση, αν θέλω να βρείτε κάποια αξία και εσωτερικό από μια συνδεδεμένη λίστα; Τι τρέχει χρόνο μου να γίνει; Big O κ. Αν είναι ταξινομημένο σε; Τι θα συμβεί αν η δομή των δεδομένων είναι ταξινομημένο; Μπορώ να κάνω καλύτερα από τις μεγάλες O ν για την αναζήτηση; Όχι, γιατί στη χειρότερη περίπτωση θα μπορούσε πολύ καλά να ταξινομηθούν, αλλά ο αριθμός ψάχνετε για να είναι μεγάλο. Θα μπορούσε να είναι ο αριθμός 100, ο οποίος μπορεί να συμβεί να είναι όλα ο τρόπος στο τέλος. Και επειδή μπορείτε να έχετε πρόσβαση μόνο ένα συνδεδεμένο Στον κατάλογο του παρόντος εφαρμογή από τρόπος πρώτο κόμβο του, είστε ακόμα είδος από την τύχη. Θα πρέπει να διασχίσει το όλο θέμα από την αρχή μέχρι το τέλος για να βρει ότι η μεγάλη αξία σαν 100. Ή, για να διαπιστωθεί εάν είναι δεν είναι καν εκεί. 

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

Τώρα, πώς θα γίνει αυτό; Λοιπόν, αν πάμε στην οθόνη εδώ, αν μπορούμε Νέα υλοποίηση γρήγορα αυτά τα δεδομένα δομή - χειρόγραφό μου δεν είναι όλα αυτά που μεγάλη εδώ, αλλά εμείς θα προσπαθήσουμε. Έτσι typedef struct, και τι έκανα θέλετε να καλέσετε αυτό το πράγμα εδώ; Κόμβου. Γι 'αυτό θα μας πάρει άρχισε. Και τώρα, τι πρέπει να είναι μέσα από Η δομή των δεδομένων για το εν λόγω μεμονωμένα συνδεδεμένη λίστα; Πώς πολλούς τομείς; 

Έτσι δύο. Ένα είναι αρκετά εύκολο. Έτσι, int n. Και θα μπορούσαμε να ονομάσουμε n οτιδήποτε θέλουμε, αλλά θα πρέπει να είναι ένα int αν είμαστε εφαρμογή συνδεδεμένη λίστα για ints. Και τώρα τι κάνει το δεύτερο τομέα πρέπει να είναι; Struct κόμβο *. Έτσι, αν κάνω struct node *, και στη συνέχεια θα να καλέσετε αυτό, επίσης, ό, τι θέλω, αλλά απλώς να είναι σαφές ότι θα καλέσετε την επόμενη, όπως έχουμε ήδη κάνει. Και τότε εγώ θα κλείσει άγκιστρα μου. 

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

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

DAVID MALAN: Ακριβώς. Ακριβώς. Επειδή C παίρνει πραγματικά κυριολεκτικά και βλέπει μόνο τον ορισμό του κόμβου μέχρι εδώ, δεν μπορείτε να αναφέρονται σε αυτήν εδώ. Έτσι έχουμε αυτό το είδος της προτίμησης δήλωση εδώ, το οποίο είναι ομολογουμένως πιο φλύαρη. Struct κόμβο, αυτό σημαίνει ότι μπορούμε να έχουμε πρόσβαση τώρα στο εσωτερικό της δομής των δεδομένων. 

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

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

Ονόματα. Θα μπορούσαμε να κάνουμε ονόματα όπως κάναμε την τελευταία φορά. Και πραγματικά, μπορείτε να αποθηκεύσετε οτιδήποτε. Και θα δούμε πάλι αυτό το PHP και JavaScript. Μια hash table είναι ένα ωραίο είδος της Ελβετίας Μαχαίρι στρατού που σας επιτρέπει να αποθηκεύετε λίγο πολύ ό, τι θέλετε στο εσωτερικό της αυτό με τη συμμετοχή κλειδιά με τιμές. Κλειδιά με τις αξίες. 

Τώρα, σε αυτή την απλή περίπτωση, μας πλήκτρα είναι απλά αριθμοί. Είμαστε εφαρμογή μιας hash πίνακας ως πίνακας. Και έτσι τα πλήκτρα είναι 0, 1, 2, και ούτω καθεξής. Και έτσι, ως άνθρωποι, αποφάσισε τον περασμένο εβδομάδα ότι ξέρετε τι, αν είμαστε Θα ονόματα κατάστημα, ας αυθαίρετα, αλλά αρκετά λογικές, υποθέσουμε ότι η Alice, ένα Ένα όνομα, απλά θα πρέπει να αναπροσαρμόζονται σε 0. Και ο Bob, ένα όνομα Β, θα πρέπει να αναπροσαρμόζονται μέσα σε 1, και ούτω καθεξής. Έτσι είχαμε μια χαρτογράφηση μεταξύ των εισόδων, τα οποία είναι χορδές, και το χασίς περιοχές, οι οποίες είναι αριθμοί. 

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

Είναι πρόκειται να επιστρέψει ένα int. Είναι πρόκειται να ονομάζεται hash, και είναι πρόκειται να αποδεχθούν ως επιχείρημα το string, ή μπορούμε να είμαστε πιο κατάλληλη στιγμή, και να πω char *, θα το ονομάσουμε s. Και τότε όλη αυτή η λειτουργία έχει να κάνει, σε τελική ανάλυση, είναι η επιστροφή σε int. Τώρα, πώς το κάνει που θα μπορούσαν να να μην είναι τόσο σαφής. Πάω να εφαρμόσουν αυτό χωρίς καμία μορφή ελέγχου σφαλμάτων τώρα. Είμαι ακριβώς πρόκειται να τυφλά πει, επιστροφή Όποια και αν είναι s βραχίονα 0, μείον, ας πούμε, το κεφάλαιο ένα ερωτηματικό. 

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

Αυτό που περιγράφεται περασμένη εβδομάδα προφορικά, όπως απλά μια διαδικασία χαρτογράφησης των Alice να 0 και 1, Bob να μπορεί να εκφραστεί σίγουρα πιο formulaically ως C λειτουργούν εδώ. Ονομάζεται και πάλι hash, παίρνει ένα string ως εισόδου, και στη συνέχεια να κάνει με κάποιο τρόπο κάτι με την εν λόγω είσοδο για να παράγει μία έξοδο. Δεν σε αντίθεση με μαύρο κουτί περιγραφή μας που έχουμε καιρό κάνει. Δεν ξέρω πώς αυτό θα μπορούσε να είναι εργάζονται κάτω από το καπό. 

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

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

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

Έτσι, αντί να προτείνει, και όχι μόνο γραμμικά σχολαστικά για ανοιχτούς χώρους και plopping τα ονόματα εκεί, πρότεινε ένα πιό φανταχτερό προσέγγιση. Μια hash table εφαρμοστεί ακόμα με ένα συστοιχία των δεικτών, αλλά ο τύπος δεδομένων οι δείκτες ήταν τώρα δείκτες. Δείκτες σε ό, τι; Δείκτες σε συνδεδεμένες λίστες. 

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

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

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

DAVID MALAN: OK. Άκουσα αρχή. Γιατί στην αρχή; 

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

DAVID MALAN: OK. Είναι αλφαβητική σειρά, έτσι ώστε να είναι ωραία. Αυτό είναι ένα καλό ξενοδοχείο. Θα σώσει εμένα κάποια στιγμή ενδεχομένως. Δεν θα επιτρέψτε μου να κάνω δυαδική αναζήτηση, αλλά εγώ θα μπορούσε τουλάχιστον να είναι σε θέση να ξεσπάσει ενός βρόχου, αν αντιλαμβάνομαι, λοιπόν, είμαι τρόπο παρελθόν ήταν ο Ααρών θα είναι σε αυτό το ταξινόμηση συνδεδεμένη λίστα. Δεν πρέπει να χάνουμε χρόνο μου κοιτάζοντας σε όλη τη διαδρομή μέχρι το τέλος. Έτσι, αυτό είναι λογικό. Γιατί αλλιώς μπορεί να θέλετε να εισαγάγετε η σύγκρουση στο όνομα του αρχή της λίστας; Τι είναι αυτό; 

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

DAVID MALAN: Θα μπορούσε να πάρει πολύ χρόνο για να φτάσουμε στο τέλος της λίστας. Και στην πραγματικότητα, περισσότερο και περισσότερο. Τα περισσότερα ονόματα που εισάγετε ότι Ξεκινήστε με ένα, το μεγαλύτερο που αλυσίδας πρόκειται να πάρει. Η πλέον ότι συνδέεται λίστα πρόκειται να πάρει. Έτσι, είστε πραγματικά ακριβώς σπαταλάτε το χρόνο σας. Ίσως είστε σε καλύτερη θέση διατηρώντας σταθερό χρόνο εισαγωγής, μεγάλη O 1, από πάντα βάζοντας το όνομα συγκρούονται σε η αρχή του συνδεδεμένη λίστα, και να μην ανησυχείτε τόσο πολύ σχετικά με την ταξινόμηση. 

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

Γι 'αυτό και στη συνέχεια κοίταξε αυτό το πράγμα, το οποίο είναι πραγματικά η άλλη μεγάλη ευκαιρία για την p-set 6. Και να συνειδητοποιήσουν, αν δεν το έχετε ήδη, Zamyla καταδύσεις σε δύο από αυτές, hash πίνακες και προσπαθεί, με περισσότερες λεπτομέρειες. Και το βίντεο που περιγράφει είναι ενσωματωμένα σε ρ-σετ spec. Αυτό ήταν ένα trie - Τ-Κ-Ι-Ε. Και αυτό που ήταν ενδιαφέρον για Αυτό ήταν ότι ο χρόνος εκτέλεσης από την αναζήτηση για ένα όνομα, όπως Maxwell τελευταία φορά, ήταν μεγάλη O από τι; Τι είναι αυτό; 

ΚΟΙΝΟ: Ο αριθμός των γραμμάτων. 

DAVID MALAN: Αριθμός γράμματα. Άκουσα δύο πράγματα. Αριθμός των γραμμάτων και σταθερό χρόνο. Οπότε ας πάμε με το πρώτο. Ο αριθμός των γραμμάτων. Λοιπόν, αυτή η δομή δεδομένων, την ανάκληση, είναι σαν ένα δέντρο, ένα δέντρο της οικογένειας, καθένα από Οι κόμβοι των οποίων αποτελούνται από συστοιχίες. Και οι συστοιχίες είναι δείκτες άλλα τέτοια κόμβους, ή άλλα τέτοια συστοιχίες στο δέντρο. 

Έτσι, αν θέλαμε να στη συνέχεια να καθορίσει αν Maxwell είναι εδώ, θα μπορούσα να πάω στην πρώτη σειρά, στην κορυφή του το δέντρο, η λεγόμενη ρίζα, κορυφή η trie, και στη συνέχεια ακολουθήστε το δείκτη m, τότε το ένα δείκτη, τότε x, W, E, L, l. Και τότε, όταν βλέπω κάποιο ειδικό σύμβολο, συμβολίζεται εδώ ως ένα τρίγωνο. Στον κώδικα θα δείτε προτείνουμε να υλοποιείται ως bool, λέγοντας απλώς ναι ή όχι, μια λέξη σταματά εδώ. 

Λοιπόν, από τη στιγμή που έχουμε πάει στο Μ-Α-Χ-Π-Ε-L-L, αισθάνεται σαν επτά, ίσως οκτώ αν πάμε ένα παρελθόν, οκτώ βήματα για να βρείτε Maxwell. Ή ας το ονομάσουμε Κ. παρά να θυμηθούμε το τελευταίο φορά, υποστήριξε ότι αν υπάρχει ρεαλιστικά ένα μέγιστο μήκος για μια λέξη, όπως η 40-ορισμένοι-περίεργο χαρακτήρες, ένα Μέγιστο μήκος συνεπάγεται μια σταθερή τιμή. Έτσι, πραγματικά, ναι, αυτό είναι τεχνικώς μεγάλη O 8 ή 7, ή πραγματικά μεγάλη O Κ., όμως, αν υπάρχει ένα πεπερασμένο όριο για το τι Κ θα μπορούσε να είναι, είναι μια σταθερά. Και γι 'αυτό είναι μεγάλη O 1 στη το τέλος της ημέρας. 

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

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

Και δεν είναι. Αυτό δεν είναι απαραίτητα τα δεδομένα δομή θα πρέπει να κλίνουν προς, γιατί όπως πίνακες κατακερματισμού, δίλημμα. Ποια είναι η τιμή που πληρώνετε εδώ; Μνήμη. Θέλω να πω, αυτό είναι μια φρικτή ποσό της μνήμης. Και δεν μπορείτε να δείτε αρκετά εδώ γιατί ο συγγραφέας αυτής της εικόνας προφανώς περικομμένο όλες τις συστοιχίες, και εμείς δεν βλέπουμε πολλά Α και Του Β και του Γ και του Q και του Y και το Ζ σε αυτές τις συστοιχίες. Αλλά είναι εκεί. 

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

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

Εντάξει. Πώς, λοιπόν, γι 'αυτό; Ο καθένας αναγνωρίζει το οποίο D-Hall; OK. Έτσι, τρεις από εμάς κάνουμε. Mather Σώμα. Έτσι, αυτό είναι για φαγητό Mather του. Πάω στοίχημα ότι όλοι οι αίθουσες φαγητού έχουν στοίβες των δίσκων όπως αυτό. Και αυτό είναι πραγματικά αντιπροσωπευτικό του κάτι που έχουμε προφανώς ήδη δει. Εμείς αυτό που ονομάζεται κυριολεκτικά μια στοίβα. Και η στοίβα, από την άποψη της σας μνήμη του υπολογιστή, είναι όπου τα δεδομένα πηγαίνει ενώ οι λειτουργίες που ονομάζεται. 

Για παράδειγμα, τι είδους πράγματα πάνε στη στοίβα σε σχέση με τη Διάταξη μνήμης έχουμε συζητήσει σε εβδομάδες παρελθόν; Τι είναι αυτό; 

ΚΟΙΝΟ: Οι κλήσεις σε συναρτήσεις. 

DAVID MALAN: Λυπάμαι. 

ΚΟΙΝΟ: Οι κλήσεις σε συναρτήσεις. 

DAVID MALAN: Κλήσεις προς τις λειτουργίες, αλλά Συγκεκριμένα, αυτό που είναι στο εσωτερικό του καθενός από αυτά τα πλαίσια; Τι είδους πράγματα; Ναι. Έτσι, οι τοπικές μεταβλητές. Κάθε φορά που χρειάζεται κάποια τοπική αποθήκευση, σαν ένα επιχείρημα, ή int I, ή int temp, ή ό, τι η τοπική μεταβλητή, έχουμε ήδη βάζοντας ότι στη στοίβα. Και λέμε μια στοίβα, διότι αυτής της ιδέας layering. Ακριβώς το είδος των αγώνων με την πραγματικότητα, η έννοια αυτού. 

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

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

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

Έτσι τι είναι ενδιαφέρον για μια στοίβα είναι ότι με το σχεδιασμό, Είναι μια δομή δεδομένων LIFO. Silly τρόπος περιγραφής τελευταία in, first out. Έτσι, ο τελευταίος αριθμός στο αυτή τη φορά ήταν 17. Έτσι, αν θέλω να σκάσει κάτι off της στοίβας, μπορεί να είναι μόνο 17. Έτσι, υπάρχει μια υποχρεωτική σειρά πράξεις εδώ, όπου το τελευταίο στοιχείο στο πρέπει να είναι η πρώτη έξω. Εξ ου και το ακρωνύμιο, LIFO. 

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

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

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

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

Αλλά ακριβώς για να κρατήσει τα πράγματα ομαλή, κανονικά θα ήθελα να επιστήσω μια σειρά, όπως αυτό, αλλά αυτό είναι το είδος της Νίκαιας αν ταιριάζουν με την πραγματικότητα, ή ταιριάζουν με το νοητικό μοντέλο. Έτσι, επιτρέψτε μου να επιστήσω την αντ 'αυτού τη σειρά κάθετα, το οποίο είναι ακριβώς, και πάλι, απόδοση καλλιτέχνη. Δεν έχει τόση σημασία τι είναι κάτω από το καπό. Και εμείς θα πούμε ότι, από προεπιλογή, δυναμικότητα πρόκειται να είναι τρεις. Έτσι, αυτό θα είναι μηδέν τοποθεσίας, αυτή η θα είναι θέση 1, η παρούσα θα είναι θέση 2. 

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

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

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

STEVEN: Όχι πολύ. 

DAVID MALAN: Εντάξει, όχι πολύ. Γνωρίζουμε τι είναι μέσα του μεγέθους, ξέρουμε τι είναι μέσα αυτού του πίνακα εδώ; 

STEVEN: Μόνο τυχαίο κωδικό, έτσι δεν είναι; Απλά - 

DAVID MALAN: Ναι, είμαι πρόκειται να αποκαλούν κώδικα, αλλά τυχαία - 

STEVEN: πράγματα. 

DAVID MALAN: Τα πράγματα όπως τυχαία 

STEVEN: Bits. 

DAVID MALAN: Bits, έτσι δεν είναι; Έτσι, οι τιμές σκουπίδια, έτσι δεν είναι; Έτσι μεταθέσεις από 0 και 1'S. Απομεινάρια των προηγούμενων χρήσεων της παρούσας μνήμης. Και εμείς πραγματικά δεν ξέρω ποιες είναι οι αξίες Οι, έτσι ώστε να επιστήσει τους τυπικά ως ερωτηματικά. 

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

STEVEN: Δίσκος είναι sub 3. 

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

STEVEN: Zero. 

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

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

STEVEN: Εντός - το μέγεθος; 

DAVID MALAN: OK. Μέγεθος πρέπει να γίνει αυτό; 

STEVEN: Μέγεθος θα είναι ένα. 

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

STEVEN: Θα πάμε από κάτω μέχρι 9. 

DAVID MALAN: 9. Εντάξει, καλή. Έτσι, ακόμα δεν έχει σημασία τι είναι σε θέση ένα ή δύο επειδή είναι τιμές σκουπίδια, αλλά δεν θα πρέπει να ενοχλεί ψάχνει εκεί, επειδή το μέγεθος είναι μας λέει ότι μόνο το πρώτο στοιχείο είναι πραγματικά νόμιμη. Έτσι τώρα πατάω 17 στην λίστα του. Τι συμβαίνει με αυτήν την εικόνα; 

STEVEN: Έτσι, το μέγεθος δεν πρόκειται να πάει σε δύο. 

DAVID MALAN: OK. Είσαι γόμα - ουπς. Είσαι μια γόμα. 

STEVEN: Eraser. 

DAVID MALAN: Είσαι μια βούρτσα. 

STEVEN: Brush. 

DAVID MALAN: OK. Και τι άλλο; 

STEVEN: Και τότε - 

DAVID MALAN: Πιέσαμε 17. 

STEVEN: Έχουμε κολλήσει 17 στην κορυφή, έτσι ώστε - 

DAVID MALAN: Εντάξει, καλά. 

STEVEN: - να πέσει κάτω. 

DAVID MALAN: Εντάξει. Είναι εύκολο να πάρει. Είμαι δεν πρόκειται να σας βοηθήσει αυτή τη φορά. Πιέστε 22. 

STEVEN: Έγινε. Να γίνει μια γόμα. Είμαι γίνεται μια βούρτσα. Και τότε Βάζω 22. 

DAVID MALAN: 22. Εξαιρετικό. Έτσι, για μια ακόμη φορά. Είμαι τώρα πρόκειται να πιέσει πάνω στη στοίβα 26. 

STEVEN: Ooh. Θεέ μου. Μπορείτε αλιεύονται με πραγματικά από τη φρουρά. 

DAVID MALAN: Δεν έκανε δείτε αυτό έρχεται; 

STEVEN: Δεν είδα αυτό που έρχονται. Θα μπορούσαμε εκ νέου αρχική ικανότητα; 

DAVID MALAN: Αυτό είναι μια καλή ερώτηση. Έτσι, έχουμε το είδος του εαυτού μας ζωγραφισμένα σε μια γωνία εδώ. Πραγματικά δεν υπάρχει κανένας καλός για Steven επειδή έχουμε διατεθεί αυτό το array στατικά, να το πω έτσι, μέσα της δομής των δεδομένων. Και έχουμε ουσιαστικά σκληρό κωδικοποιούνται να είναι το μέγεθος του τρία. Έτσι, δεν μπορούμε να ανακατανείμει πραγματικά. 

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

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

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

STEVEN: Σας ευχαριστώ. 

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

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

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

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

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

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

Αλλά αυτό είναι εντάξει, σωστά, γιατί έχουμε δει πώς να το κάνουμε αυτό. Και τη στιγμή που θα πάρει άνετα εφαρμογή κάτι σαν ένα συνδεδεμένο λίστα, η οποία θα πρέπει να κάνετε αν επιλέξουν να εφαρμόσουν ένα πίνακα κατακερματισμού με separate chaining για p-set 6, μπορείτε να να το χρησιμοποιήσετε ως ένα δομικό στοιχείο, ή συστατικό, ή στο Scratch μιλήσει, ένα διαδικασία, κάτι που βάζετε εσείς, δημιουργήσει το δικό σας κομμάτι του παζλ που μπορείτε στη συνέχεια να ξαναχρησιμοποιήσετε. Έτσι, ανταλλαγές, αλλά και πιθανές λύσεις ότι έχουμε πραγματικά δει πριν. 

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

Λοιπόν, ας το ονομάσουμε μια ουρά, μια γραμμή. Επομένως, οι Βρετανοί θα αποκαλούν συνήθως ένα ουρά έτσι, αυτό είναι ένα ωραίο όνομα. Και οι δύο λειτουργίες που μια ουρά υποστηρίζει ότι θα καλέσετε έναν enqueue λειτουργία και dequeue λειτουργία, οι οποίες είναι παρόμοιες σε πνεύμα για να πιέσει και να σκάσει. Είναι ακριβώς το είδος της διαφορετικής σύμβαση, τι είμαστε καλώντας αυτές. Αλλά για να enqueue σημαίνει κάτι για να προσθέσετε ή εισάγετε με τη δομή των δεδομένων. Για dequeue μέσα για να το αφαιρέσετε. Αλλά ενώ μια στοίβα ήταν δεδομένα LIFO δομή, μια ουρά είναι το πρώτο στην, first out δομή δεδομένων. 

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

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

Αλλά προτείνω ότι θα πρέπει να παρακολουθείτε όχι μόνο από το μέγεθος της ουρά, πόσα πράγματα βρίσκονται σε αυτό. Έτσι, το μέγεθος είναι το σημερινό μέγεθος, η ικανότητα είναι το μέγιστο μέγεθος. Απλά και πάλι, η ονοματολογία κατά συνθήκη. Γιατί χρειάζομαι ένα επιπλέον int μέσα του μια ουρά για να παρακολουθείτε ποιος είναι μπροστά από τη γραμμή; Γιατί πρέπει να το κάνουμε αυτό σε αυτή την περίπτωση; 

Λοιπόν, πώς είναι αυτή η εικόνα πρόκειται να αλλάξει; Μπορώ ίσως επαναχρησιμοποίηση περισσότερα αυτής της εικόνας. Επιτρέψτε μου να πάμε μπροστά και να διαγράψει ό, τι είναι εδώ. Θα δώσει σε αυτό μια ελαφρώς διαφορετικό όνομα εδώ. Ας απαλλαγούμε από το 17, ας απαλλαγούμε του 9, ας απαλλαγούμε από το 3. Και ας προσθέσουμε ένα άλλο πράγμα. Προτείνω ότι πρέπει να παρακολουθείτε το μπροστινό μέρος της λίστας, το οποίο είναι ακριβώς πρόκειται να είναι ένα int, καθώς και. Και θα πάμε να το κρατήσετε απλό. Δεν συνδεδεμένη λίστα για τώρα. 

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

Κάθε ένας από εσάς είναι τώρα πρόκειται να είναι ένα αγόρι ανεμιστήρα στη γραμμή της Apple. Δεν θα λαμβάνουν Apple το υλικό στο τέλος του παρόντος όμως. Εντάξει. Έτσι είστε αριθμό 9, είστε αριθμός 17, αριθμός 22. Αυτά είναι αυθαίρετοι αριθμοί, όπως φοιτητής ταυτότητες ή οτιδήποτε. Και ακριβώς σε μια στιγμή, ας αρχίσουμε να αρχίσουμε να προσθέτουμε πράγματα. Και θα τρέξει το πλοίο εδώ αυτή τη φορά. 

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

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

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

ΚΟΙΝΟ: Μπορούμε να προχωρήσουμε - 

DAVID MALAN: Όχι, αυτό είναι εντάξει. Είναι τεράστιο εκεί. Έτσι, 17 είναι τώρα στο εσωτερικό της ουράς. Θα πρέπει να ενημερώσετε το οποίο πεδίων τώρα όμως; Εντάξει, σίγουρα το μέγεθος. Και τι γίνεται μπροστά; Εντάξει, όχι. Μέτωπο δεν πρέπει να αλλάξει, διότι σε αντίθεση με μια στοίβα, έχουμε θέλουν να διατηρήσουν δικαιοσύνη. Έτσι, αν 9 ήρθε στην πρώτη, θέλουμε 9 να είναι η πρώτη έξω από τη γραμμή και μέσα στο κατάστημα. 

Στην πραγματικότητα, ας δούμε αυτό. Πριν εισάγουμε 22, ας να προχωρήσει και να dequeue 9. Ποιο είναι το όνομά σας και πάλι; 

Κοινό: Jake. 

DAVID MALAN: Jake πρόκειται να dequeued τώρα. Έτσι, μπορείτε να πάρετε για να περπατήσει στο κατάστημα. Και να υποκρινόμαστε ότι το κατάστημα είναι εκεί. Και τώρα τι χρειάζεται - DIT-dit-dit! Τι πρέπει να γίνει τώρα; Απόφαση του σχεδιασμού. Έτσι, δεν είναι μια κακή ένστικτο, αλλά - τι είναι το όνομά σας και πάλι; 

Κοινό: David. 

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

Δεν είναι μεγάλη υπόθεση αν ο David κάνει με ένα βήμα, αλλά και πάλι, σκεφτείτε ότι πίσω σε όταν είχαμε οκτώ εθελοντές σχετικά με την στάδιο και έχουμε κάνει σαν εισαγωγή ταξινόμησης, όπου θα έπρεπε να ξεκινήσει κινούνται όλοι γύρω. Αυτό πήρε ακριβά, έτσι δεν είναι; Αυτό με κάνει να μαζεύομαι για το μεγάλο Ο Ν, μεγάλη O Ν τετράγωνο και πάλι. Δεν είναι συναίσθημα όπως ένα ιδανικό αποτέλεσμα. 

Οπότε ας ενημερώσει μόνο αυτό. Έτσι, το μέγεθος της ουράς δεν είναι πλέον 2. Είναι τώρα απλά 1. Αλλά μπορώ να ενημερώσετε τώρα κάτι Δεν είχα ενημερώσει πριν, η Μπροστά από τη λίστα. Θα μπορούσα να πω, είναι ότι η θέση 1; Έτσι τώρα έχουμε αξία σκουπίδια εδώ, αξία σκουπίδια εδώ και David στο μέση αυτής της σκουπίδια. Όμως, η δομή δεδομένων είναι ακόμα άθικτο. 

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

Λοιπόν, τι θα συμβεί στη συνέχεια; Enqueue Ας - ποιο είναι το όνομά σου; 

Κοινό: Κάλεν. 

DAVID MALAN: Κάλεν. Ας enqueue ένα Κάλεν, και 22 είναι τώρα στην ουρά. Και τώρα τι πρέπει να αλλάξει εδώ; Μέτωπο δεν πρόκειται να αλλάξει, προφανώς. Μέγεθος πρόκειται να αλλάξει για να είναι ξανά 2. Και 22 τελειώνει εδώ, 9 εξακολουθεί να είναι παρούσα, αλλά είναι ουσιαστικά ένα αξίας σκουπίδια τώρα. Είναι απλά ένα απομεινάρι του παρελθόντος Τζέικ. 

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

Τώρα, όμως, τι θα συμβεί; Ας υποθέσουμε ότι εγώ enqueue, 26; Νιώθω σαν να ανήκω εδώ. Έτσι είμαι που enqueued. Γι 'αυτό το είδος ανήκουν εδώ. Και ακόμα κι αν δεν είναι αρκετά εκτιμώ αυτό οπτικά στη σκηνή, επειδή έχουμε αρκετό χώρο, θα πρέπει να δεν πρέπει να στέκεται εδώ, γιατί; 

ΚΟΙΝΟ: Είσαι εκτός ορίων. 

DAVID MALAN: Σωστά. Είμαι έξω από τα όρια. Έχω δείκτη πέρα ​​από την όρια αυτής της συστοιχίας. Πραγματικά θα πρέπει να είναι σε μία από τις τρεις πιθανές τοποθεσίες. Τώρα, πού είναι πιο φυσικό να πάτε; Προτείνω να μόχλευση μια εβδομάδα ένα τέχνασμα. Ο χειριστής mod, το ποσοστό. Επειδή είμαι τεχνικά στέκεται σε θέση 3, αλλά να κάνω 3 ικανότητα mod, έτσι 3, ένα σύμβολο τοις εκατό, 3 - χωρητικότητα είναι 3. Τι είναι αυτό; Ποιο είναι το υπόλοιπο όταν διαιρείτε το 3 επί 3; 0. 

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

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

Οποιεσδήποτε ερωτήσεις σχετικά με στοίβες, ή αυτή η ουρά; 

ΚΟΙΝΟ: Είναι ο λόγος θα πρέπει να έχετε το μέγεθος, έτσι ώστε να γνωρίζετε Πού να έχει ένα πρόσωπο; 

DAVID MALAN: Ακριβώς. Θα πρέπει να γνωρίζουν το μέγεθος του πίνακα γιατί πρέπει να γνωρίζουμε ακριβώς πώς πολλές από αυτές τις αξίες είναι νόμιμες, και έτσι ώστε να μπορώ να βρω πού να τεθεί το επόμενο πρόσωπο. Ακριβώς. Το μέγεθος είναι - στην πραγματικότητα, δεν είχαμε ενημερώσει αυτό ακόμα. Εγώ ο ίδιος πρόσθεσε σε 26. Το μέγεθος είναι τώρα, όχι 1, αλλά 2. Έτσι τώρα αυτό βοηθά πράγματι να βρω το επικεφαλής της λίστας, η οποία δεν είναι 0, δεν 1, αλλά είναι 2. Το μπροστινό μέρος του καταλόγου είναι πράγματι αριθμό 22. Επειδή ήρθε στην πρώτη, οπότε θα πρέπει να να επιτραπεί η είσοδος στο κατάστημα πριν από μένα, παρόλο που οπτικά Στέκομαι πλησιέστερα στο κατάστημα. 

Εντάξει; Ένα χειροκρότημα για αυτά τα παιδιά και εμείς θα τους αφήσουμε έξω από εκεί. 

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

DAVID MALAN: Θα μπορούσα να αφήσει κρατάτε το δίσκο. Θα μπορούσαμε να δούμε τι θα συμβεί αν θέλετε, αλλά ίσως όχι. Εντάξει. Έτσι, αυτό που κάνει τώρα που μας άφησε; Λοιπόν, επιτρέψτε μου να προτείνω να υπάρχει μια μερικές άλλες δομές δεδομένων θα μπορούσαμε ξεκινήσετε την προσθήκη στην εργαλειοθήκη μας, που θα πραγματικά να είναι αρκετά, είναι αρκετά σχετική με έχουμε βουτήξει πράγματα web. Το οποίο και πάλι, έχει κάποιο είδος της σύνδεσης στα δένδρα, με τη μορφή κάτι που ονομάζεται DOM, το έγγραφο μοντέλο αντικειμένου. Αλλά θα δούμε περισσότερα από ότι πριν από καιρό. 

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

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

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

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

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

Έτσι, αυτό που προτείνω είναι η εφαρμογή από μια λειτουργία αναζήτησης. Λαμβάνοντας υπόψη δύο εισόδους - οπότε σκεφτείτε το σαν ένα μαύρο κουτί. Δεδομένων δύο εισόδους, n, ένας int, και ένα δείκτης σε ένα δέντρο, ένα δείκτη σε μια κόμβου, ή πραγματικά η ρίζα ενός δέντρου, I ισχυρίζονται ότι αυτή η λειτουργία μπορεί να επιστρέψει αληθής ή ψευδής, η αξία n είναι στο εσωτερικό αυτού του δέντρου. 

Τι υπάρχει μέσα σε αυτό το μαύρο κουτί; Λοιπόν, τέσσερα υποκαταστήματα. Η πρώτη απλά ελέγχει. Αν το δέντρο είναι null, απλά επιστρέφει false. Αν δεν υπάρχει κόμβος, δεν υπάρχει n, δεν υπάρχει αριθμός, απλά επιστρέφει false. Αν όμως, n, η αξία που ψάχνετε για, είναι μικρότερο από δέντρο βέλος n, και ακριβώς για να είναι σαφές, τι σημαίνει αυτό όταν Γράφω δέντρου και στη συνέχεια το βέλος σημειογραφία, n; Ακριβώς. Αυτό σημαίνει ότι dereference δείκτη που ονομάζεται δέντρο. Πήγαινε εκεί, και στη συνέχεια να πάρει μέσα από αυτό κόμβο και να πάρει το πεδίο που ονομάζεται n. Και στη συνέχεια συγκρίνει την πραγματική n που ήταν πέρασε στην Αναζήτηση εναντίον της. 

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

Πώς να διευθετηθεί. Οπότε ας βελτιώσετε τον ορισμό του δέντρου εδώ δεν είναι μόνο ένα δέντρο, το οποίο μπορεί έχει οποιοδήποτε αριθμό των παιδιών. Όχι μόνο ένα δυαδικό δέντρο, το οποίο μπορεί να έχει 0, 1, ή 2 μέγιστα. Αλλά ως ένα δυαδικό δένδρο αναζήτησης, ή BST, το οποίο είναι μόνο ένα φανταχτερό τρόπο λέγοντας μια δυαδικό δέντρο τέτοια ώστε κάθε κόμβου αριστερό παιδί, αν υπάρχει, είναι λιγότερο από τον κόμβο. Και το δικαίωμα του παιδιού του κάθε κόμβου, εάν υπάρχει, είναι μεγαλύτερο από τον ίδιο κόμβο. 

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

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

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

Με άλλα λόγια, αν είμαι σήμερα σε 55 και ψάχνω για το 99, ξέρω ότι το 99 είναι μεγαλύτερη από 55, έτσι ακριβώς όπως εγώ έσκισε οι εβδομάδες τηλεφωνικό πριν και πήγε δεξιά, ομοίως είμαστε πρόκειται να πάει εδώ. Και δεν ξέρω αν είναι στα δεξιά μου παιδί, και δεν είναι, 77 είναι εκεί, αλλά Ξέρω ότι είναι προς αυτή την κατεύθυνση. Καλώ λοιπόν αναζήτηση για το δικαίωμα του παιδιού μου, 77, και αφήστε το σχήμα αναζήτησης έξω από εκεί αν 99 σε αυτό το αυθαίρετο παράδειγμα είναι στην πραγματικότητα εκεί. 

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

Έτσι, αν ψάχνω για 55 σε αυτό το σημείο στην ιστορία, αυτός ο κλάδος της δέντρο θα επιστρέψει true. Έτσι, αυτό που είναι ενδιαφέρον εδώ είναι ότι εμείς στην πραγματικότητα, σε αντίθεση με το παρελθόν εβδομάδες, έχουμε το είδος των δύο περιπτώσεων βάσης. Και δεν χρειάζεται να είναι όλα στην κορυφή. Η κορυφή είναι μια βασική περίπτωση, διότι αν η δέντρου είναι null, δεν υπάρχει τίποτα να κάνω. Μόλις επιστρέψει ένα σκληρό κωδικοποιημένο τιμή ΨΕΥΔΕΣ. 

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

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

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

Και μία από τις απογοητεύσεις σε αυτό σημείο στο εξάμηνο είναι ότι θα Μόλις εφαρμόσουν ορθογράφος σε πολύ λιγότερα γραμμές κώδικα που χρησιμοποιούν άλλες γλώσσες από C επιτρέπει στον εαυτό του, αλλά και για λόγους που θα καταλάβετε σύντομα. Αυτή θα είναι η πρώτη τέτοια ιστοσελίδα. Θα είναι εντελώς απογοητευτικό, το πρώτο που κάνουμε. Θα πω απλώς, hello world. Αλλά αν δεν έχετε δει πριν, αυτό είναι HTML, HyperText Markup Language. 

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

Σκέφτηκα να σας δώσω ένα τρέιλερ από ό, τι θα είστε σε θέση να κάνει μετά τη λήψη CS50. Επιτρέψτε μου να πάω στο cs.harvard.edu / ληστεύουν, homepage δικό Rob Bowden μας. Έκανε αυτό για μας. Έτσι, θα είναι σύντομα σε θέση να το κάνουμε αυτό. Και επίσης, αυτό που ακούσατε σήμερα το πρωί - αυτό που ακούσαμε σήμερα το πρωί - 

[HAMSTER DANCE MUSIC] 

- Εσείς θα είναι σε θέση να κάνουν αυτό. Που μας περιμένει την Τετάρτη. Θα δούμε τότε. 

[HAMSTER DANCE MUSIC] DAVID MALAN: Στο επόμενο CS50 -