[Παίζει μουσική]
>> DAVID Malan: Αυτό είναι CS50.
Και αυτό είναι το ξεκίνημα και το end-- όπως literally-- σχεδόν το τέλος
της εβδομάδας έξι.
>> Σκέφτηκα να μοιραστώ ένα λίγο ένα διασκεδαστικό γεγονός.
Έχω τραβήξει αυτό επάνω από ένα που τα δεδομένα του παρελθόντος εξαμήνου.
Ίσως να θυμάστε ότι σας ζητάμε για κάθε σύνολο φόρμα p αν έχετε παρακολουθήσει σε απευθείας σύνδεση
ή αν έχετε παρακολουθήσει στο πρόσωπο.
Και εδώ είναι τα δεδομένα.
Μέχρι σήμερα ήταν πολύ προβλέψιμη.
Αλλά θέλαμε να περάσετε λίγο του χρόνου μαζί σας, ωστόσο.
Θα μπορούσε κάποιος ήθελε να εικάσουμε γιατί αυτό γράφημα είναι τόσο αλλοιωμένες, πάνω κάτω, πάνω κάτω,
έτσι με συνέπεια;
Τι κάνουν κάθε μία από τις κορυφές και γούρνες αντιπροσωπεύουν;
>> ΚΟΙΝΟ: [δεν ακούγεται]
DAVID Malan: Πράγματι.
Και πιο διασκεδαστικά, Θεός φυλάξοι, κρατάμε μια διάλεξη την Παρασκευή
στην αρχή του εξαμήνου, αυτό είναι που βλέπουμε να συμβαίνουν.
Έτσι, σήμερα, συμμετέχουμε σε ένα κομμάτι περισσότερα για τις δομές δεδομένων.
Και για να σας δώσει περισσότερο από ένα στερεό νοητικό μοντέλο για τα προβλήματα σε πέντε,
που είναι τώρα έξω.
Ορθογραφικά λάθη, όπου, θα θα παραδώσει ένα αρχείο κειμένου περίπου 100.000
συν αγγλικές λέξεις, και θα πάμε να έχουν
για να καταλάβω πώς να τους φορτώσει έξυπνα στη μνήμη, στη μνήμη RAM, χρησιμοποιώντας κάποια δεδομένα
δομή της επιλογής σας.
>> Τώρα, μία τέτοια δομή δεδομένων θα μπορούσε να είναι, αλλά κατά πάσα πιθανότητα δεν θα πρέπει να είναι,
η αρκετά απλοϊκή συνδεδεμένη λίστα, που παρουσιάσαμε την προηγούμενη φορά.
Και μια συνδεδεμένη λίστα είχε τουλάχιστον ένα πλεονέκτημα σε σχέση με μία συστοιχία.
Τι είναι ένα πλεονέκτημα μια συνδεδεμένη λίστα αναμφισβήτητα;
>> ΚΟΙΝΟ: Εισαγωγή.
>> DAVID Malan: Εισαγωγή.
Τι εννοείτε με αυτό;
>> ΚΟΙΝΟ: Οπουδήποτε μαζί ο κατάλογος [δεν ακούγεται].
>> DAVID Malan: Καλή.
Έτσι, μπορείτε να εισαγάγετε ένα στοιχείο οπουδήποτε θέλετε στη μέση της λίστας
χωρίς να χρειάζεται να ανακατέψει τίποτα, οποία καταλήξαμε, σε διαλογή μας
συζητήσεις, δεν είναι απαραιτήτως ένα καλό πράγμα,
γιατί χρειάζεται χρόνος για να προχωρήσουμε στην πραγματικότητα όλες εκείνες ανθρώπους αριστερά ή προς τα δεξιά.
Και έτσι με μια συνδεδεμένη λίστα, μπορείτε να απλά διαθέσουν με malloc, ένας νέος κόμβος,
και στη συνέχεια να ενημερώσετε ένα ζευγάρι των pointers-- δύο, τρεις εγχειρήσεις max--
και είμαστε σε θέση να σχισμή κάποιον σε οποιοδήποτε σημείο σε μια λίστα.
>> Τι άλλο ήταν συμφέρουσα σχετικά με μια συνδεδεμένη λίστα;
Ναι;
>> ΚΟΙΝΟ: [δεν ακούγεται]
DAVID Malan: Τέλεια.
Τέλεια.
Είναι πραγματικά δυναμική.
Και ότι δεν είστε διαπράττουν, εκ των προτέρων, σε κάποιο σταθερό μέγεθος
κομμάτι της μνήμης, όπως θα έχετε σε με μια σειρά, ανοδικοί των οποίων
είναι ότι μπορείτε να διαθέσετε κόμβους μόνο στις η ζήτηση έτσι χρησιμοποιώντας μόνο όσο χώρο
όπως έχετε πραγματικά ανάγκη.
Σε αντίθεση με μια σειρά, ίσως τυχαία κατανομή πολύ λίγο.
Και τότε ακριβώς πρόκειται να είναι ένας πόνος στο λαιμό
να ανακατανείμει ένα νέο μεγαλύτερο φάσμα, αντιγραφή τα πάντα πάνω, ελευθερώστε την παλιά σειρά,
και στη συνέχεια να προχωρήσουμε για την επιχείρησή σας.
Ή, ακόμη χειρότερα, θα μπορούσε να διαθέσει τρόπο περισσότερη μνήμη από ό, τι πραγματικά χρειάζεται,
και έτσι θα πάμε να έχουν ένα πολύ αραιοκατοικημένες σειρά, να το πω έτσι.
>> Έτσι, μια συνδεδεμένη λίστα σας δίνει αυτά πλεονεκτήματα του δυναμισμού και ευελιξίας
με εισαγωγές και διαγραφές.
Αλλά σίγουρα πρέπει να υπάρχει μια τιμή που καταβάλλεται.
Στην πραγματικότητα, ένα από τα θέματα διερευνηθούν σε ένα κουίζ μηδέν
Ήταν ένα ζευγάρι των εμπορικών-offs έχουμε δει μέχρι στιγμής.
Έτσι τι είναι ένα τίμημα που καταβάλλεται ή μειονέκτημα συνδεδεμένη λίστα;
Ναι.
>> ΚΟΙΝΟ: Όχι τυχαία πρόσβαση.
>> DAVID Malan: Όχι τυχαία πρόσβαση.
Αλλά ποιος νοιάζεται;
Τυχαία πρόσβαση δεν ακούγεται συναρπαστικό.
>> ΚΟΙΝΟ: [δεν ακούγεται]
DAVID Malan: Ακριβώς.
Αν θέλετε να έχετε ένα ορισμένο algorithm--
και επιτρέψτε μου πραγματικά προτείνουν δυαδική αναζήτηση ειδικότερα, η οποία
είναι μία έχουμε χρησιμοποιήσει αρκετά bit-- εάν δεν έχετε τυχαίας προσπέλασης,
δεν μπορείτε να κάνετε αυτή την απλή αριθμητική εύρεσης σαν το μεσαίο στοιχείο
και το άλμα δικαίωμα σε αυτό.
Μπορείτε αντ 'αυτού πρέπει να ξεκινήσει κατά την πρώτη στοιχείου και γραμμικά αναζήτηση από την αριστερά
προς τα δεξιά αν θέλετε να βρείτε η μεσαία ή οποιοδήποτε άλλο στοιχείο.
>> ΚΟΙΝΟ: Χρειάζονται μάλλον περισσότερη μνήμη.
>> DAVID Malan: Παίρνει περισσότερη μνήμη.
Πού είναι ότι οι πρόσθετες το κόστος που προέρχεται από τη μνήμη;
>> ΚΟΙΝΟ: [δεν ακούγεται]
DAVID Malan: Ακριβώς.
Σε αυτήν την περίπτωση εδώ, είχαμε μια συνδεδεμένη λίστα για ακέραιους αριθμούς,
και όμως είμαστε διπλασιασμό το ποσό της μνήμης
χρειαζόμαστε επίσης από την αποθήκευση αυτών των δεικτών.
Τώρα, λιγότερο από ένα big deal, όπως structs σας πάρουν τα μεγαλύτερα
και είστε αποθήκευση και όχι στον αριθμό, αλλά ίσως ένας φοιτητής ή κάποιο άλλο αντικείμενο.
Αλλά το σημείο σίγουρα παραμένει.
Και έτσι ένας αριθμός ενεργειών σε συνδεδεμένες λίστες κλήθηκαν
ήταν μεγάλη O της n-- γραμμική.
Τα πράγματα όπως εισαγωγή ή αναζήτηση ή διαγραφή σε περίπτωση που ένα στοιχείο
έτυχε να είναι στο τέλος του ο κατάλογος αν είναι ταξινομημένο ή όχι.
>> Μερικές φορές μπορείτε να πάρετε τυχεροί και σε έτσι ώστε τα κατώτερα όρια για τις πράξεις αυτές
θα μπορούσε επίσης να είναι σταθερό χρόνο αν είστε πάντα ψάχνει στο πρώτο στοιχείο,
για παράδειγμα.
Αλλά τελικά, υποσχεθήκαμε για να επιτευχθεί το άγιο δισκοπότηρο
των δομών δεδομένων, ή κάποια προσέγγιση αυτών,
μέσω της σταθερής του χρόνου.
Μπορούμε να βρούμε στοιχεία ή να προσθέσετε στοιχεία ή να αφαιρέσετε στοιχεία από μια λίστα;
Θα δούμε αρκετά σύντομα.
Και αποδεικνύεται ότι ένα των μηχανισμών είμαστε
πρόκειται να αρχίσετε να χρησιμοποιείτε σήμερα, ετήσια χρήση σε π έθεσε πέντε,
είναι στην πραγματικότητα αρκετά εξοικειωμένοι.
Για παράδειγμα, εάν πρόκειται για μια δέσμη βιβλία εξετάσεων, καθένα από τα οποία
έχει ένας φοιτητής πρώτη το όνομα και το επίθετο σε αυτό,
και εγώ τους πάρει από στο τέλος της εξέτασης,
και είναι όλα όμορφα πολύ σε μια τυχαία σειρά,
και θέλουμε να πάμε για τη διαλογή Αυτές οι εξετάσεις, έτσι ώστε κάποτε στοιβάζονταν
είναι απλά πολύ πιο εύκολο και γρηγορότερα για να τους παραδώσει πίσω έξω
για μαθητές με αλφαβητική σειρά.
Ποιο θα είναι το ένστικτό σας για ένα σωρό εξετάσεις, όπως αυτό;
>> Λοιπόν, αν είστε σαν κι εμένα, σας μπορεί να δει ότι αυτό είναι m,
έτσι Πάω να είδος τεθεί αυτό σε, αν αυτό είναι το τραπέζι μου ή στο πάτωμα μου, όπου
Είμαι εξαπλώνεται πράγματα out-- ή σειρά μου really--
Θα ήθελα να βάλει όλα της κας εκεί.
Ω.
Εδώ είναι ένα A. Έτσι θα μπορούσα θέσει τα Ως εδώ.
Ω.
Εδώ είναι ένα άλλο Α Πάω να θέσω εδώ.
Εδώ είναι μια Ζ Εδώ είναι ένα άλλο Μ Και έτσι Θα ήθελα να αρχίσουμε να κάνουμε σωρούς σαν αυτό.
Και τότε ίσως θα ήθελα να πάω σε αργότερα και το είδος της πολύ nitpicky-LY είδος
οι επιμέρους σωρούς.
Αλλά το θέμα είναι ότι θα δούμε στην είσοδο που είμαι χέρια
και θα ήθελα να κάνω κάποια υπολογίζεται απόφαση με βάση την είσοδο.
Αν ξεκινά με Α, το έβαλε εκεί πέρα.
Αν ξεκινά με το Ζ, το έβαλε πάνω εκεί, και πάντα στο μεταξύ.
>> Έτσι, αυτό είναι μια τεχνική που είναι γενικά γνωστό ως hashing-- H-A-S-H--
πράγμα που σημαίνει γενικά λαμβάνοντας ως εισόδου και χρησιμοποιώντας αυτή την είσοδο για τον υπολογισμό
μια τιμή, γενικά ένας αριθμός, και ότι αριθμός είναι ο δείκτης σε μια αποθήκη
δοχείο, όπως μία συστοιχία.
Έτσι με άλλα λόγια, μπορεί να έχω μια hash λειτουργία, όπως και εγώ στο κεφάλι μου,
ότι αν δω κάποιον που είναι όνομα που ξεκινά με Α,
Πάω να χαρτογραφήσει ότι στο μηδέν στο κεφάλι μου.
Και αν δω κάποιον με Ζ, είμαι πρόκειται να χαρτογραφήσει ότι σε 25 στο κεφάλι μου
και στη συνέχεια να θέσει ότι σε η τελευταία πιο σωρό.
>> Τώρα, αν νομίζετε ότι για να μην του εγκεφάλου μου αλλά ένα πρόγραμμα C, τι αριθμούς θα μπορούσε να
θα στηριχθεί για να επιτευχθεί το ίδιο αποτέλεσμα;
Με άλλα λόγια, αν είχε τον ASCII χαρακτήρα Α,
πώς μπορώ να προσδιορίσω τι κουβά για να το θέσω σε;
Πιθανότατα δεν θέλουν να το βάζουμε σε κάδο 65, η οποία
θα είναι σαν εκεί για κανέναν καλό λόγο.
Πού θέλετε να βάλετε ένα όσον αφορά την τιμή ASCII του;
Πού θέλετε να κάνετε για να ASCII του αξία να καταλήξουμε σε μια πιο έξυπνη κάδο
για να το θέσω σε;
>> ΚΟΙΝΟ: Μείον Α
>> DAVID Malan: Ναι.
Έτσι μείον Α ή μείον συγκεκριμένα 65 αν είναι
ένα κεφάλαιο Α ή 98 εάν είναι ένα πεζό α.
Και έτσι αυτό θα μας επιτρέψει να, πολύ απλά και πολύ αριθμητικά,
βάλει κάτι σε ένα κουβά όπως αυτό.
Έτσι αποδεικνύεται μπορούμε πραγματικά να κάνουμε αυτό, καθώς ακόμη και με τα κουίζ.
>> Έτσι, μπορείτε να ανακαλέσετε σας κύκλο σας Όνομα διδασκαλία τους συναδέλφους του στο εξώφυλλο.
Και τα ονόματα του TF οργανώθηκαν σε αυτές τις στήλες με αλφαβητική σειρά,
Λοιπόν, είτε το πιστεύετε είτε όχι, όταν όλα τα 80 συν μας
πήρε μαζί τις προάλλες στο βαθμό, το τελευταίο βήμα στη διαδικασία βαθμολόγησης μας
είναι να hash τις κουίζ σε μια μεγάλη χώρο του δαπέδου στο [δεν ακούγεται]
και να θέσει κουίζ όλοι έξω ακριβώς τη σειρά του TF τους
ονόματα στο εξώφυλλο, γιατί τότε είναι πολύ πιο εύκολο για εμάς
για να αναζητήσετε μέσα από αυτό χρησιμοποιώντας την γραμμική αναζήτηση ή κάποιο είδος της ευφυΐας
για μια TF για να βρείτε ή του κουίζ των μαθητών της.
>> Έτσι, αυτή η ιδέα του κατακερματισμού ότι θα δείτε είναι
αρκετά ισχυρό είναι στην πραγματικότητα αρκετά συνηθισμένη και πολύ έξυπνο,
σαν ίσως χωρίζουν και Conquer ήταν στην εβδομάδα μηδέν.
Εγώ γρήγορα προς τα εμπρός για την hackathon ένα-δύο χρόνια πριν.
Αυτό ήταν Zamyla και ένα ζευγάρι των άλλους μαθητές χαιρετισμό του προσωπικού
όπως ήρθαν σε.
Και είχαμε ένα σωρό αναδίπλωσης τραπέζια εκεί με ετικέτες ονομάτων.
Και είχαμε τις ετικέτες όνομα του οργανωμένου με, όπως τα Ως εκεί
και η Zs εκεί.
Και έτσι ένα από τα TFs πολύ έξυπνα έγραψε αυτό ως τις οδηγίες
για την ημέρα.
Και στην 12η εβδομάδα του εξαμήνου αυτού του όλα γίνονται τέλεια αίσθηση και ο καθένας
δεν ήξερε τι να κάνει.
Αλλά οποτεδήποτε έχετε ουρά με τον ίδιο τρόπο,
είστε εφαρμογή η ίδια έννοια του κατακερματισμού.
Οπότε ας το λίγο επισημοποιήσει.
Εδώ είναι ένας πίνακας.
Είναι που να είναι λίγο ευρύ μόνο για να απεικονίσει, οπτικά,
ότι θα μπορούσαμε να βάλει χορδές σε κάτι σαν αυτό.
Και αυτή η σειρά είναι σαφώς από το μέγεθος 26 συνολικά.
Και το πράγμα που ονομάζεται τραπέζι αυθαίρετα.
Αλλά αυτό είναι μόνο παράδοση ενός καλλιτέχνη από ό, τι ένας πίνακας κατακερματισμού θα μπορούσε να είναι.
>> Έτσι, ένας πίνακας κατακερματισμού τώρα πρόκειται να είναι ένα υψηλότερο επίπεδο δομής δεδομένων.
Στο τέλος της ημέρας είμαστε για να δείτε ότι σας
μπορεί να εφαρμόσει ένα πίνακα κατακερματισμού, η οποία μοιάζει πολύ με τη γραμμή check-in
σε ένα hackathon πολύ σαν αυτό πίνακας που χρησιμοποιείται για τη διαλογή βιβλία εξετάσεις.
Αλλά ένας πίνακας κατακερματισμού είναι είδος αυτού του υψηλού επιπέδου
έννοια που θα μπορούσε να χρησιμοποιήσει μια σειρά κάτω από το καπό για να την εφαρμόσει,
ή θα μπορούσε να χρησιμοποιήσει μια λίστα μήκος, ή ακόμη και ίσως ορισμένες άλλες δομές δεδομένων.
Και τώρα που είναι η theme-- λήψη ορισμένα από τα βασικά συστατικά
σαν μια σειρά και αυτό το κτίριο μπλοκάρουν τώρα από μια λίστα μήκους
και να δούμε τι άλλο μπορούμε να χτίσουμε πάνω από αυτά, όπως και τα συστατικά
σε μια συνταγή, καθιστώντας όλο και περισσότερο ενδιαφέρουσα και χρήσιμη τελικά αποτελέσματα.
>> Έτσι με τον πίνακα κατακερματισμού θα μπορούσαμε να το εφαρμόσει
στη μνήμη εικονογραφικά σαν αυτό, αλλά πώς θα μπορούσε πραγματικά να κωδικοποιηθεί μέχρι;
Καλά, ίσως, όσο πιο απλά είναι αυτό.
Αν η χωρητικότητα σε όλα τα καλύμματα, είναι απλά κάποια constant-- για παράδειγμα 26,
για 26 επιστολές του alphabet-- Θα ήθελα να καλέσετε μεταβλητή τραπέζι μου,
και εγώ μπορεί να ισχυριστεί ότι θα πάω να θέσει char αστέρια εκεί, ή σπάγκο.
Γι 'αυτό είναι τόσο απλό όσο αυτό αν θέλουν να εφαρμόσουν ένα πίνακα κατακερματισμού.
Και όμως, αυτό είναι πραγματικά ακριβώς μια σειρά.
Αλλά και πάλι, ένα hash πίνακας είναι τώρα τι θα
καλέστε έναν αφηρημένο τύπο δεδομένων που είναι ακριβώς Ταξινόμηση των εννοιολογική διαστρωμάτωση στην κορυφή
κάτι πιο πεζά ήθελα τώρα μια σειρά.
>> Τώρα, πώς πηγαίνουμε για την επίλυση των προβλημάτων;
Λοιπόν, νωρίτερα είχα την πολυτέλεια έχουν αρκετό χώρο τραπέζι εδώ
έτσι ώστε θα μπορούσα να βάλω το κουίζ οπουδήποτε ήθελα.
Έτσι, όπως θα μπορούσε να πάει εδώ.
Zs θα μπορούσε να πάει εδώ.
Κα μπορεί να πάει εδώ.
Και τότε είχα κάποια επιπλέον χώρο.
Αλλά αυτό είναι ένα κομμάτι από ένα εξαπατήσει δικαιώματος τώρα, γιατί αυτόν τον πίνακα, αν πραγματικά
σκεφτόμουν σαν μια σειρά, είναι απλά πρόκειται να είναι από κάποιο σταθερό μέγεθος.
>> Έτσι, τεχνικά, αν μου τραβήξει μέχρι κουίζ κάποιου άλλου φοιτητή
και να δείτε, ω, αυτό το άτομο είναι Όνομα ξεκινάει με ένα Α πάρα πολύ,
Ι το είδος θέλετε να το βάλετε εκεί.
Αλλά μόλις το έβαλα εκεί, αν ο πίνακας αυτός αποτελεί πράγματι μια σειρά,
Πάω να προεξεχόντων ή clobbering όποιος κουίζ αυτού του μαθητή είναι.
Σωστά;
Εάν αυτό είναι ένας πίνακας, ένα μόνο πράγμα μπορεί να πάει σε καθένα από αυτά τα κύτταρα ή στοιχείων.
Και γι 'αυτό το είδος έχει για να επιλέξετε και να επιλέξετε.
>> Τώρα νωρίτερα Ι το είδος του εξαπατημένοι και έκανε αυτό ή εγώ
ακριβώς το είδος των στοιβάζονται τους πάνω από κάθε άλλο.
Αλλά αυτό δεν πρόκειται να πετάξει στον κώδικα.
Έτσι, όταν θα μπορούσε να βάλω το δεύτερος φοιτητής του οποίου το όνομα
είναι ένα, αν το μόνο που είχα είναι αυτό διαθέσιμος χώρος στο τραπέζι;
Και έχω χρησιμοποιήσει τρεις υποδοχές και μοιάζει σαν να υπάρχει μόνο μερικά άλλα.
Τι θα μπορούσατε να κάνετε;
ΚΟΙΝΟ: [δεν ακούγεται]
DAVID Malan: Ναι.
Ίσως απλά ας την κρατήσουμε απλή.
Σωστά;
Δεν χωράει όπου θέλω να το θέσω.
Έτσι, Πάω να το θέσουμε από τεχνική όπου ένας Β θα πάει.
Τώρα, βέβαια, αρχίζω να ζωγραφίσει τον εαυτό μου σε μια γωνία.
Αν φτάσουμε σε ένα μαθητή του οποίου το όνομα είναι πράγματι Β,
τώρα B πρόκειται να μετακινηθεί λίγο προς τα εμπρός, όπως θα μπορούσε να συμβεί, yep,
αν αυτό είναι ένα Β, τώρα πρέπει να πάει εδώ.
>> Και έτσι αυτό πολύ γρήγορα θα μπορούσε να καταστεί προβληματική,
αλλά είναι μια τεχνική που στην πραγματικότητα αναφέρεται ως γραμμική διερεύνηση,
όπου μπορείτε απλά να εξετάσει σας συστοιχία να είναι κατά μήκος της γραμμής.
Και ακριβώς το είδος του καθετήρα ή επιθεωρούν κάθε διαθέσιμο στοιχείο
ψάχνει για ένα διαθέσιμο σημείο.
Και το συντομότερο μπορείτε να βρείτε ένα, μπορείτε να ρίξετε εκεί.
>> Τώρα, η τιμή που καταβάλλεται τώρα για αυτή τη λύση είναι αυτό;
Έχουμε μια σταθερή σειρά μεγέθους, και όταν εισάγω τα ονόματα
σε αυτό, τουλάχιστον αρχικά, τι είναι ο χρόνος εκτέλεσης της εισαγωγής
για την τοποθέτηση των μαθητών κουίζ στη σωστή κάδους;
Big O τι;
>> ΚΟΙΝΟ: Ν.
DAVID Malan: Άκουσα μεγάλη O Ν.
Δεν είναι αλήθεια.
Αλλά εμείς θα δώσουμε έμφαση, εκτός γιατί ακριβώς σε μια στιγμή.
Τι άλλο μπορεί να είναι;
>> ΚΟΙΝΟ: [δεν ακούγεται]
DAVID Malan: Και επιτρέψτε μου να το κάνω οπτικά.
Έτσι, υποθέστε ότι αυτό είναι το γράμμα S.
>> ΚΟΙΝΟ: Είναι μία.
DAVID Malan: Είναι μία.
Σωστά;
Αυτό είναι ένας πίνακας, ο οποίος σημαίνει ότι έχουμε τυχαία πρόσβαση.
Και αν σκεφτούμε αυτό ως μηδέν και αυτό ως 25,
και συνειδητοποιούμε ότι, Ω, εδώ είναι είσοδος μου S,
Σίγουρα μπορεί να μετατρέψει S, ένας χαρακτήρας ASCII,
σε έναν αντίστοιχο αριθμό μεταξύ μηδέν και 25
και αμέσως μετά το βάζουμε εκεί που ανήκει.
>> Αλλά φυσικά, το συντομότερο πάρω να το δεύτερο πρόσωπο που το όνομα του είναι Α ή Β ή Γ
τελικά, αν έχω χρησιμοποιήσει το γραμμική σχολαστικά ως λύση μου,
ο χρόνος εκτέλεσης του εισαγωγή στη χειρότερη περίπτωση
είναι πραγματικά πρόκειται να περιέλθει σε τι;
Και εγώ δεν το ακούω εδώ σωστά από νωρίς.
ΚΟΙΝΟ: [δεν ακούγεται]
DAVID Malan: Έτσι είναι n πράγματι μία φορά έχετε ένα αρκετά μεγάλο σύνολο δεδομένων.
Έτσι, από τη μία πλευρά, αν σειρά σας είναι αρκετά μεγάλη
και τα δεδομένα σας είναι αρκετά αραιή, μπορείτε να πάρει αυτό το όμορφο σταθερό χρόνο.
Αλλά μόλις ξεκινήσετε όλο και περισσότερα στοιχεία,
και απλά στατιστικά μπορείτε να πάρετε περισσότερα άτομα με το γράμμα
Α, όπως το όνομά τους ή το γράμμα Β, θα μπορούσε δυνητικά
περιέλθει σε κάτι πιο γραμμική.
Έτσι, δεν είναι αρκετά τέλειο.
Έτσι, θα μπορούσαμε να κάνουμε καλύτερα;
>> Λοιπόν, τι ήταν μας λύση πριν, όταν εμείς
θέλουν να έχουν μεγαλύτερη δυναμική από ό, τι κάτι σαν μια σειρά επιτρέπονται;
ΚΟΙΝΟ: [δεν ακούγεται]
DAVID Malan: Τι εισάγουμε;
Ναι.
Έτσι, μια συνδεδεμένη λίστα.
Λοιπόν, ας δούμε τι συνδέεται κατάλογος θα μπορούσε να κάνει για μας αντ 'αυτού.
Λοιπόν, επιτρέψτε μου να προτείνω να επιστήσει την εικόνα ως εξής.
Τώρα αυτό είναι μια διαφορετική εικόνα από ένα παράδειγμα
από ένα διαφορετικό κείμενο, στην πραγματικότητα, ότι είναι στην πραγματικότητα χρησιμοποιώντας ένα πίνακα μεγέθους 31.
Και ο συγγραφέας απλά αποφάσισε να hash χορδές
όχι με βάση τα ονόματα του ατόμου, αλλά βασίζεται σε ημερομηνιες γέννησης τους.
Ανεξαρτήτως του μήνα, κατάλαβα αν γεννηθεί την πρώτη του μήνα
ή η 31η του μήνα, ο συγγραφέας θα hash βασίζεται στην εν λόγω τιμή,
έτσι ώστε να εξαπλωθεί τα ονόματα από λίγο περισσότερο από ακριβώς 26 σημεία μπορεί να επιτρέψει.
Και ίσως είναι λίγο πιο ομοιόμορφη ό, τι συμβαίνει με τα γράμματα του αλφαβήτου,
γιατί φυσικά υπάρχει πιθανώς περισσότεροι άνθρωποι στον κόσμο με τα ονόματα
ότι ξεκινούν με ένα από τα σίγουρα κάποια άλλα γράμματα της αλφαβήτου.
Έτσι ίσως αυτό είναι λίγο πιο ομοιόμορφη, υποθέτοντας
μια ομοιόμορφη κατανομή των βρεφών σε ένα μήνα.
>> Αλλά, φυσικά, αυτό εξακολουθεί να είναι ατελής.
Σωστά;
Είμαστε έχοντας συγκρούσεις.
Πολλαπλές οι άνθρωποι σε αυτό δομή δεδομένων είναι ακόμα
έχουν την ίδια ημερομηνία γέννησης, τουλάχιστον είστε ανεξάρτητα από το μήνα.
Αλλά αυτό που έχει κάνει ο συγγραφέας;
Λοιπόν, φαίνεται σαν να έχουμε μια σειρά στην αριστερή πλευρά που κάθετα,
αλλά αυτό είναι μόνο παράδοση ενός καλλιτέχνη.
Δεν έχει σημασία ποια κατεύθυνση συντάξει μια σειρά, είναι ακόμα μια σειρά.
Τι είναι αυτό μια σειρά από φαινομενικά;
>> ΚΟΙΝΟ: συνδεδεμένη λίστα.
>> DAVID Malan: Ναι.
Μοιάζει σαν να είναι ένα συστοιχία συνδεδεμένη λίστα.
Έτσι και πάλι, σε αυτό το σημείο του είδους από τη χρήση αυτών των δομών δεδομένων τώρα
ως συστατικά σε περισσότερες ενδιαφέρουσες λύσεις,
μπορείτε να πάρετε απολύτως θεμελιώδη, όπως και μια σειρά,
και στη συνέχεια να λάβει κάτι περισσότερο ενδιαφέρουσα σαν μια συνδεδεμένη λίστα
και ακόμα να τα συνδυάσετε σε ένα ακόμη πιο ενδιαφέρουσα δομή δεδομένων.
Και πράγματι, αυτό επίσης θα να ονομάζεται ένα πίνακα κατακερματισμού,
οπότε η συστοιχία είναι πραγματικά ο πίνακας κατακερματισμού,
αλλά ότι ο πίνακας κατακερματισμού έχει αλυσίδες, να το πω έτσι,
ότι μπορεί να αυξηθεί ή να συρρικνωθεί με βάση το τον αριθμό των στοιχείων που θέλετε να εισαγάγετε.
>> Τώρα, ως εκ τούτου, ό, τι είναι ο χρόνος τρέχει τώρα;
Αν θέλετε να εισάγετε κάποιον του οποίου τα γενέθλια είναι η 31η Οκτωβρίου,
πού αυτός ή αυτή να πάει;
Εντάξει.
Στο κάτω μέρος όπου λέει 31.
Και αυτό είναι τέλειο.
Αυτό ήταν σταθερό χρόνο.
Αλλά τι θα γίνει αν βρεθεί κάποιος άλλος του οποίου τα γενέθλια είναι, ας δούμε,
Οκτώβριος, Νοέμβριος, Δεκέμβριος 31;
Πού είναι αυτός ή αυτή πρόκειται να πάει;
Το ίδιο πράγμα.
Δύο βήμα όμως.
Αυτό είναι σταθερή και αν δεν είναι;
Εντάξει.
Αυτή τη στιγμή είναι.
Αλλά στη γενική περίπτωση, οι περισσότεροι άνθρωποι προσθέτουμε,
πιθανολογικά, θα πάμε να πάρει όλο και περισσότερες συγκρούσεις.
>> Τώρα αυτό είναι μια μικρή καλύτερα, διότι είναι τεχνικά
τώρα αλυσίδες μου θα μπορούσε να είναι σε η χειρότερη περίπτωση για πόσο καιρό;
Αν τοποθετήσετε n άνθρωποι σε αυτή την πιο εξελιγμένα δομή δεδομένων, n οι άνθρωποι,
στη χειρότερη περίπτωση, πρόκειται να είναι n.
Γιατί;
>> ΚΟΙΝΟ: Γιατί αν όλοι έχει γενέθλια την ίδια μέρα,
από όπου και αν πρόκειται να είναι μία γραμμή.
DAVID Malan: Τέλεια.
Θα μπορούσε να είναι λίγο σκηνοθετημένη, αλλά πραγματικά στη χειρότερη περίπτωση,
αν ο καθένας έχει γενέθλια την ίδια μέρα, λαμβάνοντας υπόψη τις εισροές που έχετε,
θα πάμε να έχουν ένα μαζικά μακράς αλύσου.
Και έτσι, θα μπορούσε να είναι μια κλήση hash πίνακα, αλλά πραγματικά είναι
απλά μια μαζική συνδεδεμένη λίστα με ένα σωρό σπατάλη χώρου.
Αλλά σε γενικές γραμμές, αν υποθέσουμε ότι τουλάχιστον γενέθλια είναι uniform--
και κατά πάσα πιθανότητα δεν είναι.
Κάνω ότι μέχρι.
Αλλά αν υποθέσουμε, για η χάρη της συζήτησης
ότι είναι, στη συνέχεια, στη θεωρία, εάν Αυτό είναι η κατακόρυφη αναπαράσταση
του πίνακα, και στη συνέχεια, ελπίζω να είστε πρόκειται να πάρει αλυσίδες που είναι, ξέρετε,
περίπου το ίδιο μήκος, όπου κάθε ένα από αυτά αντιπροσωπεύει μια ημέρα του μήνα.
>> Τώρα, αν υπάρχει 31 ημέρες το μήνα, αυτό σημαίνει ότι χρόνος μου τρέχει πραγματικά
Είναι μεγάλη O Ν πάνω από 31, το οποίο αισθάνεται καλύτερα από ό, τι γραμμική.
Αλλά αυτό ήταν ένα από μας δεσμεύσεις μια-δυο εβδομάδες
Πριν από κάθε φορά που ήρθε στην έκφραση ο χρόνος εκτέλεσης ενός αλγορίθμου;
Αρκεί να δει κανείς μόνο στο υψηλό όρος τάξης.
Σωστά;
31 είναι σίγουρα χρήσιμη.
Αλλά αυτό είναι ακόμα μεγάλη O Ν.
Αλλά ένα από τα θέματα του προβλήματος που πέντε
πρόκειται να είναι σε Αναγνωρίζετε ότι απολύτως,
ασυμπτωτικά, θεωρητικά Αυτή η δομή δεδομένων
δεν είναι καλύτερη από ό, τι ακριβώς μία μαζική συνδεδεμένη λίστα.
Και πράγματι, στη χειρότερη περίπτωση, αυτό hash πίνακας θα μπορούσε να περιέλθει σε αυτό.
>> Αλλά στον πραγματικό κόσμο, με εμάς τους ανθρώπους ότι η δική τους Mac ή το PC ή ο, τιδήποτε
και τρέχουν πραγματικό κόσμο λογισμικού σε πραγματικό κόσμο των δεδομένων,
η οποία αλγόριθμο θα πας να προτιμάτε;
Το ένα που παίρνει τέλος βήματα ή το μία η οποία παίρνει n διαιρείται με 31 βήματα
να βρείτε κάποιο κομμάτι των δεδομένων ή να αναζητήσετε κάποιες πληροφορίες;
Θέλω να πω, απολύτως τις 31 μάρκες μια διαφορά στον πραγματικό κόσμο.
Είναι 31 φορές πιο γρήγορα.
Και εμείς οι άνθρωποι είναι σίγουρα πρόκειται να το εκτιμήσουν.
>> Έτσι αντιλαμβάνονται τη διχοτόμηση υπάρχει ανάμεσα στην πραγματικότητα
μιλάμε για τα πράγματα θεωρητικά και ασυμπτωτικά που σίγουρα
έχει αξία, όπως έχουμε δει, αλλά στον πραγματικό κόσμο,
αν σας ενδιαφέρει να κάνουμε απλώς το ανθρώπινη χαρούμενος για γενικές εισροές,
θα μπορούσε κάλλιστα να δεχθεί Το γεγονός ότι, ναι, αυτό είναι γραμμική,
αλλά είναι 31 φορές πιο γρήγορα από ό, τι θα μπορούσε να είναι γραμμική.
Και ακόμα καλύτερα, δεν πρέπει απλώς να κάνουμε κάτι αυθαίρετο σαν ημερομηνία γέννησης,
Θα μπορούσαμε να περάσουμε λίγο περισσότερο χρόνο και εξυπνάδα
και να σκεφτούμε τι μπορούμε να κάνουμε, όνομα και ίσως ενός ατόμου
ημερομηνία γέννησής τους να συνδυάζουν εκείνες συστατικά για να καταλάβω κάτι
ότι είναι πραγματικά περισσότερο ομοιόμορφη και λιγότερο αλλοιωμένες,
να το πω έτσι από αυτή την εικόνα σήμερα δείχνει ότι θα μπορούσε να είναι.
Πώς θα μπορούσαμε να εφαρμόσουμε στον κώδικα;
Λοιπόν, επιτρέψτε μου να προτείνω να απλά δανειστεί κάποια σύνταξη έχουμε
χρησιμοποιείται ένα ζευγάρι φορές μέχρι στιγμής.
Και Πάω να καθορίσουν ένας κόμβος, ο οποίος και πάλι
είναι ένας γενικός όρος για μερικά μόνο δοχείο για κάποια δομή δεδομένων.
Πάω να προτείνω ένα string πηγαίνει εκεί.
Αλλά θα πάμε για να αρχίσετε να παίρνετε εκείνους που έτρεχαν τροχούς μακριά τώρα.
>> Δεν υπάρχει πλέον η CS50 βιβλιοθήκη Πραγματικά, αν θέλετε
να το χρησιμοποιήσει για την τελική σας έργου, η οποία είναι λεπτή,
αλλά τώρα θα πάμε για να τραβήξει πίσω το κουρτίνα και να πω ότι είναι απλά ένα αστέρι ΧΑΡ.
Έτσι, η λέξη υπάρχει πρόκειται να είναι το όνομα του ατόμου στο ερώτημα.
Και τώρα έχω ένα σύνδεσμο εδώ στον επόμενο κόμβο
έτσι ώστε αυτές να αντιπροσωπεύουν κάθε ένα από τους κόμβους
στην αλυσίδα, δυνητικά, μιας συνδεδεμένης λίστας.
>> Και τώρα πώς μπορώ να δηλώνω ο ίδιος ο πίνακας κατακερματισμού;
Πώς μπορώ να δηλώσει όλη αυτή τη δομή;
Λοιπόν, πραγματικά, πολύ όπως εγώ χρησιμοποίησα ένα δείκτη απλά το πρώτο στοιχείο μιας λίστας
πριν, ομοίως μπορώ μόνο να πω Απλώς χρειάζεται μια δέσμη των δεικτών
να εφαρμόσει όλη αυτή πίνακα κατακερματισμού.
Πάω να έχουν μια σειρά ονομάζεται πίνακας για πίνακα κατακερματισμού.
Είναι πρόκειται να είναι του μεγέθους χωρητικότητας.
Αυτό είναι το πόσα στοιχεία μπορούν να χωρέσουν σε αυτό.
Και καθένα από αυτά τα στοιχεία σε αυτό σειρά πρόκειται να είναι ένα αστέρι κόμβο.
Γιατί;
Λοιπόν, κατ 'αυτή την εικόνα, τι είμαι την εφαρμογή του πίνακα κατακερματισμού ως
αποτελεσματικά η αρχή είναι ακριβώς Αυτή η σειρά που έχουμε χαραγμένη κάθετα,
καθένας εκ των οποίων πλατείες αντιπροσωπεύει ένα δείκτη.
Ότι αυτοί που έχουν καθέτους μέσω αυτών είναι μόνο άκυρη.
Και εκείνοι που έχουν βέλη πηγαίνει προς τα δεξιά
είναι πραγματική δείκτες για την πραγματική κόμβους, όθεν την έναρξη μιας συνδεδεμένης λίστας.
>> Μέχρι εδώ, λοιπόν, είναι πώς μπορούμε να εφαρμόσει ένα πίνακα κατακερματισμού που
υλοποιεί Ξεχωριστές αλυσίδες.
Τώρα μπορούμε να κάνουμε καλύτερα;
Εντάξει είχα υποσχεθεί τελευταία φορά που θα μπορούσαμε να επιτύχουμε συνεχή χρόνο.
Και εγώ το είδος σας έδωσε σταθερό χρόνο εδώ,
αλλά στη συνέχεια δεν είπε πραγματικά σταθερό χρόνο γιατί είναι ακόμα
εξαρτάται από την συνολική αριθμό στοιχείων
είστε στη χάραξη της η δομή δεδομένων.
Αλλά ας υποθέσουμε ότι το κάναμε αυτό.
Επιτρέψτε μου να πάω πίσω στην οθόνη εδώ.
Επιτρέψτε μου να προεξέχει επίσης αυτό εδώ, σαφή η οθόνη, και ας υποθέσουμε ότι το έκανα αυτό.
Ας υποθέσουμε Ήθελα να εισάγετε το όνομα Daven σε σε δομή δεδομένων μου.
>> Θέλω, λοιπόν, να εισαγάγετε μια συμβολοσειρά Daven μέσα στην δομή δεδομένων.
Τι θα γίνει αν δεν χρησιμοποιείτε ένα hash πίνακα, αλλά μπορώ να χρησιμοποιήσω
κάτι που είναι πιο δέντρο-όπως σαν ένα οικογενειακό δέντρο, όπου
έχετε κάποια ρίζα κατά τη κορυφή και, στη συνέχεια, οι κόμβοι και τα φύλλα
ότι πάει προς τα κάτω και προς τα έξω.
Ας υποθέσουμε λοιπόν, ότι εγώ θέλετε να εισάγετε Daven του
σε ό, τι είναι σήμερα μια κενή λίστα.
Πάω να κάνω το εξής: είμαι πρόκειται να δημιουργήσει έναν κόμβο σε αυτή την οικογένεια
δέντρο-όπως δομή δεδομένων που φαίνεται λίγο σαν αυτό, καθένα από τα οποία
ορθογώνια έχει, ας πούμε, για σήμερα 26 στοιχεία σε αυτό.
Και κάθε ένα από τα κύτταρα σε αυτήν την σειρά θα
να εκπροσωπεί το γράμμα του αλφαβήτου.
>> Συγκεκριμένα, Πάω για τη θεραπεία Αυτό είναι ένα, τότε Β, στη συνέχεια το C, τότε το D,
αυτό εδώ.
Έτσι, αυτό πρόκειται για την αποτελεσματική αντιπροσωπεύουν το γράμμα Δ
Αλλά για να εισαγάγετε όλα τα Daven του το όνομα πρέπει να κάνω λίγο περισσότερο.
Έτσι είμαι πρώτος πρόκειται να hash, να το πω έτσι.
Πάω να δούμε το πρώτο γράμμα σε Daven το οποίο είναι προφανώς ένα D,
και Πάω να διαθέσει ένας κόμβος που μοιάζει
όπως this-- ένα μεγάλο ορθογώνιο μεγάλο αρκετό για να χωρέσει ολόκληρο το αλφάβητο.
>> Τώρα D γίνεται.
Τώρα Α Δ-Α-ν-Ε-Ν είναι ο στόχος.
Και τώρα τι Πάω να κάνουμε είναι αυτό.
Μόλις άρχισα Δ ειδοποίηση δεν υπάρχει δείκτης εκεί.
Είναι αξίες σκουπίδια αυτή τη στιγμή, ή θα μπορούσε να γίνει η προετοιμασία της σε null.
Αλλά επιτρέψτε μου να συνεχίσω με Αυτή η ιδέα της οικοδόμησης ενός δέντρου.
Επιτρέψτε μου να διαθέσει άλλο ένα από αυτά κόμβους που έχει 26 στοιχεία σε αυτό.
>> Και ξέρετε τι;
Αν αυτό είναι μόνο ένας κόμβος σε μνήμη που Δημιούργησα με malloc, χρησιμοποιώντας ένα struct
όπως θα δούμε σύντομα, Πάω να κάνω this--
Πάω να σχεδιάσετε ένα βέλος από το πράγμα που αντιπροσώπευε D προς τα κάτω
σε αυτό το νέο κόμβο.
Και τώρα, για πρώτη φορά το επόμενο επιστολή στο όνομα Daven του,
V-- D-Α-V-- Πάω να πάει μπροστά και σχεδιάστε ένα άλλο κόμβο, όπως αυτό,
σύμφωνα με την οποία, οι V στοιχεία εδώ, η οποία θα συντάξει για instance-- κραυγών.
Εμείς δεν θα τραβήξει εκεί.
Είναι πρόκειται να πάει εδώ.
>> Στη συνέχεια θα πάμε να θεωρούν ότι αυτό είναι V.
Και στη συνέχεια κάτω από εδώ θα πάμε στο ευρετήριο κάτω από το V σε αυτό που θα εξετάσει Ε
Και στη συνέχεια, από εδώ θα πάμε να πηγαίνετε έχει ένα από αυτούς τους κόμβους εδώ.
Και τώρα έχουμε μια ερώτηση για να απαντήσει.
Πρέπει με κάποιο τρόπο να δείξει ότι είμαστε στο τέλος του string Daven.
Γι 'αυτό και θα μπορούσε απλά αφήστε το null.
>> Αλλά τι γίνεται αν έχουμε Daven του πλήρες όνομα, επίσης, το οποίο
είναι, όπως έχουμε πει, Ντάβενπορτ;
Έτσι, ό, τι και αν είναι Daven στην πραγματικότητα μια συμβολοσειρά,
ένα πρόθεμα του μια πολύ μεγαλύτερη χορδών;
Δεν μπορούμε απλά να μόνιμα να πω τίποτα δεν πρόκειται
να πάω εκεί, γιατί θα μπορούσαμε να Ποτέ εισάγετε μια λέξη όπως Davenport
σε αυτή τη δομή δεδομένων
>> Λοιπόν, τι θα μπορούσαμε να κάνουμε, αντιθέτως, είναι τη θεραπεία κάθε ένα από αυτά τα στοιχεία
όπως ίσως έχει δύο στοιχείων στο εσωτερικό τους.
Ένα είναι ένας δείκτης, πράγματι, όπως έχω ήδη κάνει.
Έτσι, κάθε ένα από αυτά τα πλαίσια Δεν είναι μόνο ένα κύτταρο.
Αλλά τι θα γινόταν αν η κορυφή ένα-- το κάτω μέρος κάποιου
πρόκειται να είναι μηδενική, γιατί δεν υπάρχει Davenport ακριβώς ακόμα.
Τι θα συμβεί αν η κορυφή ενός είναι κάποια ιδιαίτερη αξία;
Και αυτό πρόκειται να είναι μια μικρή σκληρά για να είναι αυτό το μέγεθος επιστήσει.
Αλλά ας υποθέσουμε ότι είναι απλά ένα σημάδι ελέγχου.
Ελέγξτε.
D-Α-V-Ε-Ν είναι ένα string σε αυτή τη δομή δεδομένων.
>> Εν τω μεταξύ, αν είχα περισσότερο χώρο εδώ, θα μπορούσα να κάνω Ρ-Ο-Ρ-Τ,
και θα μπορούσα να βάλω το check-in κόμβο που έχει το γράμμα Τ στο τέλος.
Έτσι, αυτό είναι ένα μαζικά σύνθετη-αναζητούν δομή δεδομένων.
Και το χειρόγραφό μου σίγουρα δεν βοηθά.
Αλλά αν ήθελα να τοποθετήσετε κάτι αλλιώς, σκεφτείτε τι θα κάνουμε.
Αν θέλαμε να βάλει ο David στο, είχαμε ακολουθήσει την ίδια λογική, D-Α-V,
αλλά τώρα θα ήθελα να επισημάνω στην επόμενη στοιχείο όχι από Ε, αλλά από Ι Δ
Έτσι, εκεί πρόκειται να είναι περισσότερους κόμβους σε αυτό το δέντρο.
Εμείς πάμε για να έχουν malloc κλήση περισσότερο.
Αλλά δεν θέλω να κάνω μια πλήρες χάος αυτής της εικόνας.
Ας δούμε, αντί σε ένα που είναι ήδη προ-διαμορφωθεί
όπως αυτό με όχι τελεία, τελεία, τελείες, αλλά μόνο συντετμημένη συστοιχίες.
Αλλά κάθε ένα από τους κόμβους σε αυτό το δέντρο μέχρι εδώ
αντιπροσωπεύει την ίδια thing-- μια σειρά Ray μεγέθους 26.
>> Ή αν θέλουμε να είμαστε πραγματικά σωστή τώρα, τι
αν το όνομα κάποιου ατόμου ως μια απόστροφο, ας
υποθέσουμε ότι κάθε κόμβος έχει στην πραγματικότητα όπως και 27 ευρετήρια σε αυτό, όχι μόνο 26.
Μέχρι τώρα αυτό πρόκειται να είναι ένας δεδομένα δομή ονομάζεται trie-- Τ-Κ-Ι-Ε.
Ένα trie, η οποία υποτίθεται ότι είναι ιστορικά ένα έξυπνο όνομα για ένα δέντρο
που είναι βελτιστοποιημένη για ανάκτησης, η οποία φυσικά,
γράφεται με Ι-Ε έτσι είναι trie.
Αλλά αυτή είναι η ιστορία του trie.
>> Έτσι, ένα trie είναι αυτό το δέντρο-όπως δεδομένα δομή, όπως ένα οικογενειακό δέντρο
ότι συμπεριφέρεται τελικά σαν αυτό.
Και εδώ είναι απλώς άλλο ένα παράδειγμα ενός σωρό ονόματα άλλων ανθρώπων.
Αλλά το ερώτημα τώρα στο χέρι είναι ό, τι έχουν
έχουμε αποκτήσει με την εισαγωγή αναμφισβήτητα μια πιο πολύπλοκη δομή δεδομένων, και ένα,
ειλικρινά, ότι χρησιμοποιεί πολλή μνήμη.
>> Διότι ακόμη και αν, αυτή τη στιγμή, είμαι μόνο
χρησιμοποιώντας το δείκτη του D's και Α και V και Ες και της NS,
Είμαι σπατάλη ένα καλό των πολύ μνήμη.
Αλλά πού θα περάσουν έναν πόρο, Τείνω να μην κερδίσει πίσω ένα άλλο.
Έτσι, αν ξοδεύω περισσότερο χώρο, τι είναι ίσως η ελπίδα;
Ότι είμαι ξοδεύουν λιγότερο, τι;
ΚΟΙΝΟ: Λιγότερο χρόνο.
DAVID Malan: Ώρα.
Τώρα γιατί θα μπορούσε αυτό να είναι;
Λοιπόν, ποια είναι η εισαγωγή χρόνο, από την άποψη των μεγάλων O τώρα,
από ένα όνομα όπως Daven ή Davenport ή Δαβίδ;
Λοιπόν, Daven ήταν πέντε βήματα.
Davenport θα είναι εννέα βήματα, οπότε θα ήταν μερικά ακόμη βήματα.
Ο David θα είναι πέντε βήματα, καθώς και.
Έτσι, αυτές είναι συγκεκριμένες αριθμούς, αλλά σίγουρα υπάρχει
ένα άνω φράγμα για το μήκος του ονόματος κάποιου.
Και πράγματι, το πρόβλημα σύνολα των πέντε προδιαγραφής,
θα πάμε να προτείνει ότι αυτό είναι κάτι
ότι είναι 40-μερικοί-περίεργο χαρακτήρες.
>> Ρεαλιστικά, κανείς δεν έχει ένα απείρως μεγάλο όνομα,
το οποίο είναι να πούμε ότι το μήκος ενός το όνομα ή το μήκος μιας συμβολοσειράς θα μπορούσαμε
έχουν ορισμένα η κατάσταση της δομής είναι αναμφισβήτητα ό, τι;
Είναι σταθερή.
Σωστά;
Θα μπορούσε να είναι μια μεγάλη σταθερά, όπως 40-κάτι, αλλά είναι σταθερή.
Και δεν έχει καμία εξάρτηση από το πόσες άλλα ονόματα είναι σε αυτή τη δομή δεδομένων.
Με άλλα λόγια, αν μου ήθελε να εισάγετε τώρα
Colton ή Γαβριήλ ή Rob ή Zamyla ή Alison ή Μπελίντα ή οποιαδήποτε άλλα ονόματα
από το προσωπικό σε αυτά τα δεδομένα δομή, είναι ο χρόνος τρέχει
της εισάγοντας άλλα ονόματα πρόκειται να είναι καθόλου κρούση
από το πόσο πολλά άλλα στοιχεία είναι στη δομή των δεδομένων που έχουν ήδη;
Δεν είναι.
Σωστά;
Επειδή είμαστε η αποτελεσματική χρήση των Αυτό το hash πίνακα πολλαπλών στρωμάτων.
Και ο χρόνος εκτέλεσης του οποιαδήποτε από αυτές τις εργασίες
δεν εξαρτάται από τον αριθμό των στοιχεία που βρίσκονται στη δομή δεδομένων
ή ότι τελικά θα να είναι στη δομή δεδομένων,
αλλά το μήκος του τι ειδικώς;
>> Το κορδόνι είναι εισαχθεί, το οποίο κάνει
Αυτό ασυμπτωτικά σταθερό time-- μεγάλη O ενός.
Και ειλικρινά, μόνο σε το πραγματικό κόσμο, αυτό
σημαίνει εισάγοντας το όνομα Daven παίρνει σαν πέντε βήματα, ή εννέα Davenport
βήματα, ή Δαβίδ πέντε βήματα.
Αυτό είναι αρκετά καταριέται μικρούς χρόνους λειτουργίας.
Και, πράγματι, αυτό είναι ένα πολύ καλό πράγμα, ειδικά όταν
δεν είναι εξαρτάται από την συνολική αριθμός των στοιχείων εκεί.
Λοιπόν, πώς θα μπορούσαμε να εφαρμόσουμε το είδος της δομής στον κώδικα;
Είναι λίγο πιο πολύπλοκο, αλλά εξακολουθεί να είναι
απλά μια εφαρμογή βασικά δομικά στοιχεία.
Πάω να επαναπροσδιορίσει κόμβος μας ως εξής:
bool ονομάζεται word-- και αυτό θα μπορούσε να ονομάζεται τίποτα.
Αλλά η bool αντιπροσωπεύει αυτό που μου επέστησε ως ένα σημάδι ελέγχου.
Ναι.
Αυτό είναι το τέλος μιας συμβολοσειράς σε αυτή τη δομή δεδομένων.
>> Και, φυσικά, το αστέρι κόμβος υπάρχει αναφορά για τα παιδιά.
Και, πράγματι, ήθελε απλά ένα οικογενειακό δέντρο, σας
θα εξετάσει τους κόμβους που κρέμονται από
του πυθμένα κάποιου γονέα στοιχείο για να είναι τα παιδιά.
Και έτσι τα παιδιά πρόκειται να είναι ένας πίνακας του 27, το 27ο το ένα
απλά να είναι για την απόστροφο.
Εμείς πάμε για να ταξινομήσετε της ειδικής περίπτωσης αυτής.
Έτσι μπορείτε να έχετε ορισμένους ονόματα με αποστρόφους.
Ίσως ακόμη και παύλα θα πρέπει πάω εκεί, αλλά θα
δείτε το σύνολο P 5 έχουμε μόνο φροντίδα σχετικά με γράμματα και αποστρόφους.
>> Και τότε πώς θα αντιπροσωπεύουν η ίδια η δομή δεδομένων;
Πώς μπορείτε να αντιπροσωπεύουν τη ρίζα αυτής trie, να το πω έτσι;
Λοιπόν, ήθελα απλά με μια συνδεδεμένη λίστα, μπορείτε χρειάζεται ένα δείκτη προς το πρώτο στοιχείο.
Με ένα trie χρειάζεστε μόνο ένα δείκτη στη ρίζα αυτής της trie.
Και από εκεί μπορείτε να hash το δρόμο σας προς τα κάτω όλο και βαθύτερα
σε κάθε άλλο κόμβο στη δομή.
Έτσι, απλά με αυτό μπορεί να εμείς εκπροσωπούμε αυτό το struct.
>> Τώρα Meanwhile-- Ω, ερώτηση.
>> ΚΟΙΝΟ: Τι είναι λέξη bool;
>> DAVID Malan: λέξη Bool είναι ακριβώς αυτή η ενσάρκωση C
από ό, τι περιέγραψα σε αυτό το πλαίσιο εδώ, όταν
Άρχισα χωρίζοντας το καθένα από τα στοιχεία συστοιχίας σε δύο κομμάτια.
Το ένα είναι ένας δείκτης στον επόμενο κόμβο.
Το άλλο πρέπει να είναι κάτι σαν ένα κουτί ελέγχου
να πω ναι, υπάρχει μια Daven λέξη που τελειώνει εδώ,
γιατί δεν θέλουμε, αυτή τη στιγμή, ο Dave.
>> Ακόμα κι αν ο Dave πρόκειται να είναι μια νόμιμη λέξη, αυτός δεν είναι στην trie
ακόμα.
Και D δεν είναι μια λέξη.
Και D-Α δεν είναι μια λέξη ή ένα όνομα.
Έτσι, το σήμα ελέγχου δείχνει μόνο τη στιγμή που θα
χτύπησε ο κόμβος αυτός είναι ο προηγούμενη πορεία των χαρακτήρων
πραγματικά ένα string που έχετε εισάγει.
Έτσι, αυτό είναι όλο το bool είναι εκεί να κάνει για εμάς.
>> Οποιεσδήποτε άλλες ερωτήσεις σχετικά προσπαθεί;
Ναι.
>> ΚΟΙΝΟ: Ποια είναι η επικάλυψη;
Τι γίνεται αν έχετε ένα Ντέιβ και Daven;
DAVID Malan: Τέλεια.
Τι γίνεται αν έχετε ένα Ντέιβ και Daven;
Έτσι αν εισάγουμε, να πω ένα ψευδώνυμο, για David-- Dave-- D-Α-V-Ε;
Αυτό είναι στην πραγματικότητα εξαιρετικά απλή.
Έτσι είμαστε μόνο πρόκειται να διαρκέσει τέσσερα βήματα.
D-Α-V-E. Και τι πρέπει να κάνω κάνουμε μια φορά χτύπησα ότι η τέταρτη κόμβο;
Απλά πρόκειται να ελέγξει.
Είμαστε ήδη καλό να πάει.
Έγινε.
Τέσσερα στάδια.
Σταθερή χρόνο ασυμπτωτικά.
Και τώρα έχουμε δηλώσει ότι τόσο ο Dave και Daven είναι χορδές στη δομή.
Έτσι, δεν αποτελεί πρόβλημα.
Και παρατηρήστε πώς η παρουσία της Daven δεν το κάνει
να λάβει περισσότερο χρόνο ή λιγότερο χρόνο για τον Dave και το αντίστροφο.
>> Λοιπόν, τι άλλο μπορούμε να κάνουμε τώρα;
Έχουμε χρησιμοποιήσει αυτήν την παρομοίωση πριν των δίσκων που αντιπροσωπεύουν κάτι.
Αλλά αποδεικνύεται ότι ένα στοίβα των δίσκων είναι στην πραγματικότητα
εκδηλωτικός άλλου αφηρημένων στοιχείων type-- ένα υψηλότερο επίπεδο δομής δεδομένων
ότι στο τέλος της ημέρας είναι ακριβώς σαν μια σειρά ή μια συνδεδεμένη λίστα
ή κάτι πιο πεζά.
Αλλά είναι μια πιο ενδιαφέρουσα εννοιολογική αντίληψη.
Μια στοίβα, όπως αυτές Θήκες εδώ στο Mather,
γενικά ονομάζονται απλά that-- μια στοίβα.
>> Και σε αυτό το είδος της δομής δεδομένων έχετε δύο operations--
έχετε ένα ονομάζεται ώθηση για προσθέτοντας κάτι στη στοίβα,
σαν να βάζουμε άλλο δίσκο αντίγραφα στην κορυφή της στοίβας.
Και τότε ποπ, η οποία θα σημαίνει λαμβάνει το ανώτερο δίσκο μακριά.
Αλλά τι είναι κλειδί για μια στοίβα είναι ότι αυτό πήρε αυτό το περίεργο χαρακτηριστικό.
Καθώς το προσωπικό τραπεζαρία είναι αναδιατάσσοντας τους δίσκους για το επόμενο γεύμα,
τι πρόκειται να είναι αλήθεια για το πώς οι μαθητές
αλληλεπιδρούν με αυτή τη δομή δεδομένων;
ΚΟΙΝΟ: Θα πάμε να σκάσει εφάπαξ.
DAVID Malan: Θα πάμε να pop εφάπαξ, ελπίζω, την κορυφή.
Διαφορετικά είναι ακριβώς το είδος της ηλίθια να πάνε όλα το δρόμο προς τα κάτω.
Σωστά;
Η δομή δεδομένων που πραγματικά δεν επιτρέπουν μπορείτε να αρπάξει την κάτω δίσκο τουλάχιστον
εύκολα.
Έτσι, υπάρχει αυτό το περίεργο ιδιοκτησίας σε μια στοίβα
ότι το τελευταίο στοιχείο είναι πρόκειται να είναι η πρώτη έξω.
Και οι επιστήμονες υπολογιστών καλέστε Αυτό LIFO-- διαρκέσει in, first out.
Και αυτό πραγματικά δεν έχει ενδιαφέρουσες εφαρμογές.
Δεν είναι κατ 'ανάγκην τόσο προφανής όσο μερικοί άλλους, αλλά μπορεί, πράγματι, να είναι χρήσιμα,
και μπορεί, πράγματι, να εφαρμοστεί σε μια-δυο διαφορετικούς τρόπους.
>> Έτσι μία, και στην πραγματικότητα, ας μου να μην βουτήξει σε αυτό.
Ας κάνουμε αυτό αντ 'αυτού.
Ας ρίξουμε μια ματιά σε αυτό που είναι σχεδόν το ίδια ιδέα, αλλά είναι λίγο πιο δίκαιη.
Σωστά;
Αν είστε ένας από αυτούς αγόρια ανεμιστήρα ή τα κορίτσια που του αρέσει πραγματικά τα προϊόντα της Apple
και σας ξύπνησε στις 3:00 π.μ. να παρατάξει σε κάποιο κατάστημα
για να πάρετε την πολύ τελευταίες iPhone, μπορείτε θα μπορούσαν να έχουν ουρά σαν αυτό.
>> Τώρα μια ουρά είναι πολύ σκόπιμα το όνομα.
Είναι μια γραμμή επειδή υπάρχει κάποια δικαιοσύνη σ 'αυτό.
Σωστά;
Είναι το είδος του θα αναρροφάται αν έχετε πήρε εκεί πρώτα στο Apple Store
αλλά είστε αποτελεσματικά το κατώτατο δίσκο, επειδή οι εργαζόμενοι της Apple στη συνέχεια,
ποπ το τελευταίο πρόσωπο που πήρε πραγματικά στην γραμμή.
Έτσι, στοίβες και ουρές, ακόμη και αν λειτουργικά από όπου και αν το είδος του same--
είναι ακριβώς αυτή η συλλογή των πόρων που είναι
πρόκειται να αυξηθεί και shrink-- του εκεί Αυτή η πτυχή της δικαιοσύνης σε αυτό,
τουλάχιστον στον πραγματικό κόσμο, όπου οι εργασίες που ασκούν
είναι ριζικά διαφορετικές.
Μια stack-- μια ουρά rather-- λέγεται για να έχει
δύο λειτουργίες: n ουρά και δ ουρά.
Ή μπορείτε να καλέσετε πολλά πράγματα.
Αλλά απλά θέλετε να συλλάβει η αντίληψη ότι μία είναι η προσθήκη
και ένα τελικά αφαίρεση.
>> Τώρα κάτω από την κουκούλα, τόσο η στοίβα και μια ουρά θα μπορούσε να υλοποιηθεί με ποιον τρόπο;
Εμείς δεν θα πάμε στον κώδικα του επειδή το υψηλότερο επίπεδο
ιδέα είναι είδος πιο προφανής.
Θέλω να πω, τι κάνουν οι άνθρωποι;
Αν είμαι το πρώτο πρόσωπο στην Μήλο Αποθηκεύστε και αυτή είναι η μπροστινή πόρτα,
Ξέρετε, εγώ είμαι πρόκειται να σταθεί εδώ.
Και η επόμενη ατόμου πρόκειται να σταθεί εδώ.
Λοιπόν, τι δομή δεδομένων προσφέρεται σε μια ουρά;
>> ΚΟΙΝΟ: Μια ουρά.
DAVID Malan: Λοιπόν, μια ουρά.
Σίγουρα.
Τι άλλο;
>> ΚΟΙΝΟ: Μια συνδεδεμένη λίστα.
>> DAVID Malan: Ένα συνδεδεμένο λίστα θα μπορούσε να εφαρμόσει.
Και μια συνδεδεμένη λίστα είναι ωραίο, διότι τότε μπορεί να αυξηθεί αυθαίρετα μεγάλη αντίθεση
να έχουν κάποιο σταθερό αριθμό των ανθρώπων στο κατάστημα.
Αλλά ίσως ένα σταθερό αριθμό των θέσεων είναι νόμιμη.
Διότι, αν έχουν μόνο σαν 20 iphones την πρώτη ημέρα, ίσως
που χρειάζονται μόνο ένα πίνακα μεγέθους 20 να εκπροσωπεί την ουρά, η οποία
μόνο να πω τώρα μόλις αρχίζουμε να μιλάμε σχετικά με αυτές τις υψηλότερες προβλήματα επίπεδο,
μπορείτε να το εφαρμόσει σε οποιοδήποτε αριθμό τρόπων.
Και υπάρχει πιθανώς ακριβώς πρόκειται να είναι ένα εμπόριο μακριά στο χώρο και το χρόνο
ή μόνο στο δικό σας κώδικα πολυπλοκότητα.
>> Τι γίνεται με μια στοίβα;
Λοιπόν, μια στοίβα, έχουμε δει πάρα πολύ θα μπορούσε απλώς να είναι αυτοί οι δίσκοι.
Και θα μπορούσε να εφαρμόσει αυτό μια σειρά.
Αλλά σε κάποιο σημείο, αν χρησιμοποιείτε μια συστοιχία, τι πρόκειται να συμβεί με τους δίσκους
προσπαθείτε να βάλετε κάτω;
Εντάξει.
Είστε μόνο πρόκειται να να είναι σε θέση να πάει τόσο ψηλά.
Και νομίζω ότι στην Mather ότι είναι πραγματικά εσοχή σε εκείνο το άνοιγμα.
Έτσι, πράγματι, είναι σχεδόν όπως Mather χρησιμοποιεί
μία συστοιχία σταθερού μεγέθους, επειδή μπορείτε μόνο
χωρέσει τόσα πολλά δίσκους σε αυτό το άνοιγμα στην ο τοίχος κάτω από τα γόνατα των ανθρώπων.
Και έτσι ώστε να μπορεί να λέγεται ότι είναι ένας πίνακας,
αλλά θα μπορούσαμε βεβαίως να εφαρμόσουν ότι γενικότερα με μια συνδεδεμένη λίστα.
>> Λοιπόν, τι γίνεται με άλλη δομή δεδομένων;
Επιτρέψτε μου να σηκώσει μια άλλη οπτική εδώ.
Κάτι σαν σχετικά με το πώς αυτό εδώ;
Γιατί μπορεί να είναι χρήσιμο να μην έχουν κάτι σαν φανταχτερό ως trie, η οποία
είδαμε είχε αυτές τις πολύ μεγάλη κόμβους, καθένα από τα οποία βρίσκεται σε μία συστοιχία;
Αλλά ό, τι και αν κάνουμε κάτι περισσότερο απλά, σαν ένα παλιό οικογενειακό δέντρο του σχολείου,
καθένας εκ των οποίων οι κόμβοι εδώ μόλις αποθήκευση ενός αριθμού.
Αντί για ένα όνομα ή έναν απόγονο μόλις την αποθήκευση ενός αριθμού, όπως αυτό.
>> Λοιπόν, η ορολογία που χρησιμοποιούμε σε δομών δεδομένων που είναι και οι δύο προσπάθειες
και δέντρα, όπου ένα trie, και πάλι, είναι μόνο ένα οποίου οι κόμβοι είναι συστοιχίες,
εξακολουθεί να είναι αυτό που θα μπορούσε χρησιμοποιούν από το δημοτικό
όταν κάνατε μια οικογένεια tree-- φύλλα και η ρίζα
του δέντρου και τα παιδιά του γονέα και τα αδέλφια τους.
Και θα μπορούσαμε να εφαρμόσουν ένα δέντρο, για παράδειγμα, ως απλά ως αυτό.
Ένα δέντρο, αν ως κόμβος, ένας από Αυτοί οι κύκλοι που έχει ένα αριθμό,
δεν πρόκειται να έχουν ένα δείκτη, αλλά δύο.
Και το συντομότερο μπορείτε να προσθέσετε ένα δεύτερο δείκτη,
μπορεί πραγματικά να κάνει τώρα το είδος δύο διαστάσεων δεδομένα
δομές στη μνήμη.
Μοιάζει πολύ με ένα δισδιάστατο σειρά, μπορείτε να
έχουν το είδος των δύο διαστάσεων συνδεδεμένες λίστες, αλλά αυτά
ότι ακολουθούν ένα μοτίβο όπου δεν υπάρχει κύκλους.
Είναι πραγματικά ένα δέντρο με ένα παππούς και γιαγιά δρόμο μέχρι εδώ και, στη συνέχεια,
μερικοί γονείς και παιδιά και εγγόνια και δισέγγονα.
και ούτω καθεξής.
>> Αλλά τι είναι πραγματικά τακτοποιημένο για αυτό πάρα πολύ, απλά για να σας πειράζω με ένα κομμάτι του κώδικα,
ανάκληση αναδρομή από λίγο πίσω, σύμφωνα με την οποία
να γράψετε μια συνάρτηση που καλεί τον εαυτό της.
Αυτή είναι μια όμορφη ευκαιρία να εφαρμόσει κάτι
όπως η αναδρομή, επειδή θεωρούν αυτό.
>> Αυτό είναι ένα δέντρο.
Και έχω μια μικρή πρωκτική με το πώς Έβαλα τα ακέραιοι στο δρόμο.
Τόσο μεγάλο μέρος έτσι ώστε να έχει μια ειδική name-- ένα δυαδικό δέντρο αναζήτησης.
Τώρα έχουμε ακούσει δυαδικό αναζήτησης, αλλά μπορεί να σας
εργάζονται πίσω από το όνομα αυτό το πράγμα;
Ποιο είναι το σχέδιο για το πώς θα παρεμβάλλονται οι ακέραιοι σε αυτό το δέντρο;
Δεν είναι αυθαίρετη.
Υπάρχει κάποιο μοτίβο.
Ναι.
>> ΚΟΙΝΟ: μικρότερα στα αριστερά.
>> DAVID Malan: Ναι.
Μικρότερα βρίσκονται στα αριστερά.
Οι μεγαλύτερες από αυτές είναι στα δεξιά.
Τέτοια ότι μια αληθινή δήλωση είναι μια γονέας είναι μεγαλύτερη από ό, τι το αριστερό παιδί του,
αλλά λιγότερο από το δικαίωμα του παιδιού της.
Και αυτό από μόνο του είναι ακόμη ένα αναδρομικές λεκτική ορισμό
επειδή μπορείτε να εφαρμόσετε ότι ίδια λογική σε κάθε κόμβο
και μόνο πυθμένες έξω, μία βασική περίπτωση, αν
θα είναι, όταν χτύπησε ένα από τα τα φύλλα, να το πω έτσι,
όπου μια άδεια έχει επιπλέον κανένα παιδί.
>> Τώρα πώς μπορεί να σας βρει τον αριθμό 44;
Θα ξεκινούν από τη ρίζα και να πω, hm.
55 δεν είναι 44 Κι εγώ θέλω να πάω δεξιά ή θέλω να πάμε αριστερά;
Λοιπόν, προφανώς θέλετε να πάτε αριστερά.
Και έτσι ακριβώς όπως το τηλέφωνο βιβλίο παράδειγμα σε δυαδική αναζήτηση
γενικότερα.
Αλλά είμαστε το εκτελεστικών τώρα λίγο πιο δυναμικά
από μια σειρά μπορεί να επιτρέψει.
Και στην πραγματικότητα, αν θέλετε να δείτε κατά τον κώδικα, με την πρώτη ματιά σίγουρος.
Μοιάζει με ένα σωρό γραμμές.
Αλλά είναι όμορφα απλό.
Αν θέλετε να υλοποιήσετε μια συνάρτηση που ονομάζεται αναζήτηση των οποίων ο σκοπός στη ζωή
είναι να ψάξει για μια αξία όπως n, ένας ακέραιος αριθμός,
και είστε περάσει σε ένα pointer-- ένα δείκτη στον κόμβο των ριζών,
μάλλον, από αυτό το δέντρο από το οποίο μπορείτε να έχετε πρόσβαση σε όλα τα άλλα,
παρατηρήστε πώς ευθέως μπορείτε να εφαρμόσετε τη λογική.
Αν το δέντρο είναι μηδενική, προφανώς δεν είναι εκεί.
Ας επιστρέψει false.
Σωστά;
Αν το χέρι τίποτα, δεν υπάρχει τίποτα εκεί.
>> Αλλιώς, εάν το η είναι μικρότερο από δέντρο βέλος n-- τώρα arrow n,
Υπενθυμίζουμε εισαγάγαμε σούπερ εν συντομία την άλλη μέρα,
και αυτό σημαίνει ότι μόλις de-αναφοράς για την δείκτη και να εξετάσουμε το πεδίο που ονομάζεται n.
Έτσι, αυτό σημαίνει να πάει εκεί και κοιτάξτε στο πεδίο που ονομάζεται n.
Έτσι, αν n, η τιμή που σας δίνεται, είναι λιγότερο από την τιμή στο ακέραιο δέντρα,
Που θέλετε να πάτε;
Στα αριστερά.
>> Έτσι παρατηρήσετε την αναδρομή.
Είμαι returning-- δεν είναι αλήθεια.
Δεν είναι ψευδείς.
Είμαι επιστρέφουν ανεξάρτητα από την απάντηση είναι από μια κλήση στον εαυτό μου, περνώντας
ένα n ξανά, η οποία είναι περιττή, αλλά αυτό που είναι ελαφρώς διαφορετική τώρα;
Πώς είμαι καθιστώντας το πρόβλημα μικρότερο;
Είμαι περνώντας ως δεύτερη επιχείρημα, δεν είναι η ρίζα του δέντρου,
αλλά το αριστερό παιδί σε αυτή την περίπτωση.
Έτσι περνάω στο αριστερό παιδί.
>> Εν τω μεταξύ, εάν η είναι μεγαλύτερο από ο κόμβος είμαι σήμερα κοιτάζοντας,
Γυρεύω την δεξιά πλευρά.
Αλλιώς, αν το δέντρο δεν είναι μηδενική, και εάν το στοιχείο δεν είναι προς τα αριστερά
και δεν είναι προς τα δεξιά, τι είναι θαυμάσια η περίπτωση;
Έχουμε βρει πραγματικά τον κόμβο στο ερώτηση, και έτσι επιστρέφουμε αλήθεια.
>> Έτσι έχουμε μόλις γδαρμένο από την επιφάνεια τώρα μερικές από αυτές τις δομές δεδομένων.
Στο πρόβλημα που πέντε που θα διερευνήσει αυτά ακόμη περαιτέρω,
και θα σας δοθεί το σχέδιό σας επιλογή του πώς να πάει για αυτό.
Αυτό που θα ήθελα να ολοκληρώσω με είναι μόλις 30 δευτερολέπτων τρέιλερ
του τι περιμένει την επόμενη εβδομάδα και πέρα.
>> Όπως έχουμε begin-- ευτυχώς ίσως think-- μετάβαση μας σιγά-σιγά
από τον κόσμο της C και κάτω λεπτομέρειες εφαρμογής επίπεδο,
σε έναν κόσμο στον οποίο μπορούμε να πάρουμε για δεδομένο ότι κάποιος άλλος έχει τέλος
εφαρμοστούν αυτά τα δεδομένα δομές για εμάς,
και θα αρχίσουν να καταλαβαίνουν το πραγματικό κόσμο μέσα από την εφαρμογή
web-based προγράμματα και ιστοσελίδες γενικότερα
καθώς επίσης και η ίδια η ασφάλεια επιπτώσεις που έχουμε μόνο
αρχίσει να γρατσουνίσει την επιφάνεια της.
Εδώ είναι τι μας περιμένει στις μέρες που έρχονται.
>> [ΑΝΑΠΑΡΑΓΩΓΗ]
>> -Αυτός Ήρθε με ένα μήνυμα, με ένα πρωτόκολλο όλα δικά του.
Ήρθε σε έναν κόσμο της σκληρής firewalls, routers αδιάφορος,
και κινδύνους πολύ χειρότερη από τον θάνατο.
Είναι γρήγορο.
Είναι ισχυρή.
Είναι το πρωτόκολλο TCP / IP, και πήρε τη διεύθυνσή σας.
"Πολεμιστές του Net."
[ΤΕΛΟΣ VIDEO Αναπαραγωγή]
DAVID Malan: Ερχόμενοι την επόμενη εβδομάδα.
Θα σας δούμε στη συνέχεια.
[ΑΝΑΠΑΡΑΓΩΓΗ]
-Και Τώρα, «βαθιές σκέψεις" από Daven Farnham.
-David Ξεκινά πάντα διαλέξεις με, "Εντάξει."
Γιατί όχι, "Εδώ είναι η λύση στο σύνολο το πρόβλημα αυτής της εβδομάδας "
ή «Δίνουμε όλοι σας ένα Α;"
[Γέλια]
[ΤΕΛΟΣ VIDEO Αναπαραγωγή]