[Παίζει μουσική] ΟΜΙΛΗΤΗΣ 1: Εντάξει. Όλοι καλωσορίσω πίσω στην ενότητα. Ελπίζω να είστε όλοι με επιτυχία ανακτώνται από το κουίζ σας από την περασμένη εβδομάδα. Ξέρω ότι είναι λίγο τρελός μερικές φορές. Όπως είπα και πριν, αν είστε στο πλαίσιο της τυπικής απόκλισης, Πραγματικά δεν ανησυχείτε γι 'αυτό, ιδιαίτερα για μια λιγότερο άνετα τμήμα. Αυτό είναι σχετικά με το πού θα πρέπει να είναι. Αν κάνατε μεγάλη, τότε φοβερό. Συγχαρητήρια σε εσάς. Και εάν αισθάνεστε σαν να πρέπει λίγο περισσότερη βοήθεια, παρακαλούμε μην διστάσετε να επικοινωνήσετε έξω σε κάποιο από τα ΤΡ. Είμαστε όλοι εδώ για να βοηθήσουμε. Αυτός είναι ο λόγος για τον οποίο διδάσκουμε. Γι 'αυτό είμαι εδώ κάθε Δευτέρα για εσάς παιδιά και στα γραφεία ώρες την Πέμπτη. Έτσι, μη διστάσετε να επιτρέψτε μου να ξέρω αν είστε ανησυχούν για τίποτα ή αν υπάρχει κάτι για το κουίζ ότι θα θέλατε πραγματικά να αντιμετωπίσει. Επομένως, η ατζέντα για σήμερα είναι όλα τα σχετικά με τις δομές δεδομένων. Μερικά από αυτά είναι ακριβώς πρόκειται να είναι ακριβώς για να έχετε εξοικειωθεί με αυτά. Δεν μπορεί ποτέ να εφαρμόσουν τους σε αυτή την κατηγορία. Μερικά από αυτά θέλετε, όπως για ορθογράφο το chipset σας. Θα έχετε την επιλογή σας ανάμεσα σε πίνακες κατακερματισμού και προσπαθεί. Έτσι θα είμαστε σίγουρα να πηγαίνει πέρα ​​από εκείνους. Είναι πρόκειται να είναι σίγουρα περισσότερο από το είδος ενός τμήματος υψηλού επιπέδου σήμερα, όμως, επειδή υπάρχουν πολλά από αυτά, και αν πήγαμε σε λεπτομέρειες υλοποίησης για όλα αυτά, δεν θα ακόμη και να πάρετε μέσα από συνδεδεμένες λίστες και ίσως ένα μικρό κομμάτι των πινάκων κατακερματισμού. Έτσι φέρει μαζί μου. Εμείς δεν πρόκειται να κάνουμε όσο κωδικοποίησης αυτή τη φορά. Εάν έχετε οποιεσδήποτε ερωτήσεις σχετικά με αυτό ή θέλετε να δω να υλοποιούνται ή να το δοκιμάσετε για τον εαυτό σας, Θα ήθελα να συστήσω σίγουρα πρόκειται να study.cs50.net, η οποία έχει παραδείγματα όλα αυτά. Θα έχουν Powerpoints μου με τις σημειώσεις που έχουμε τείνουν να χρησιμοποιούν καθώς και λίγο προγραμματισμό ασκήσεις, ειδικά για τα πράγματα όπως συνδεδεμένες λίστες και δυαδικό δέντρα στοίβες και συνθήματα. Έτσι, λίγο πιο υψηλό επίπεδο, το οποίο μπορεί να είναι καλό για σας παιδιά. Έτσι, με αυτό, θα ξεκινήσετε. Και επίσης, yes-- κουίζ. Νομίζω ότι οι περισσότεροι από εσάς που είναι σε τμήμα μου έχουν κουίζ σας, αλλά ο καθένας έρχεται σε ή κάποιο λόγο δεν κάνουν, έχουν δίκιο εδώ στο μπροστινό μέρος. Έτσι, συνδεδεμένες λίστες. Ξέρω ότι αυτό το είδος του πηγαίνει στην πλάτη πριν κουίζ σας. Αυτή ήταν η εβδομάδα πριν ότι μάθαμε σχετικά με αυτό. Αλλά σε αυτή την περίπτωση, απλά θα πάει λίγο περισσότερο σε βάθος. Επομένως, γιατί θα μπορούσαμε να επιλέξουν ένα συνδεδεμένη λίστα πάνω από μια σειρά; Αυτό που τους διακρίνει; Ναι; ΚΟΙΝΟ: Μπορείτε να επεκτείνετε ένα συνδεδεμένο λίστα έναντι σταθερού μεγέθους μιας συστοιχίας. ΟΜΙΛΗΤΗΣ 1: Δεξιά. Ένας πίνακας έχει σταθερό μέγεθος, ενώ ένα συνδεδεμένη λίστα έχει ένα μεταβλητό μέγεθος. Έτσι, αν δεν ξέρουμε πώς πολύ θέλουμε να αποθηκεύσουμε, μια συνδεδεμένη λίστα μας δίνει μια μεγάλη τρόπος για να το κάνουμε αυτό, διότι μπορούμε μόνο προσθέσετε σε έναν άλλο κόμβο και να προσθέσετε στην άλλο κόμβο και να προσθέσετε σε ένα άλλο κόμβο. Αλλά τι θα μπορούσε να είναι ένα trade-off; Υπάρχει κάποιος που θυμάται το εμπόριο-off μεταξύ συστοιχιών και συνδεδεμένες λίστες; Mmhmm; ΚΟΙΝΟ: Θα πρέπει να περάσουν από όλα τον τρόπο μέσω της συνδεδεμένη λίστα βρείτε ένα στοιχείο σε μια λίστα. Σε έναν πίνακα, μπορείτε να απλά να βρείτε ένα στοιχείο. ΟΜΙΛΗΤΗΣ 1: Δεξιά. Έτσι, με arrays-- ΚΟΙΝΟ: [δεν ακούγεται]. ΟΜΙΛΗΤΗΣ 1: Με συστοιχίες, έχουμε ό, τι λέγεται τυχαία πρόσβαση. Σημαίνει ότι αν θέλουμε ό, τι είναι ποτέ το πέμπτο σημείο του καταλόγου ή το πέμπτο σημείο μας σειρά, μπορούμε να το αρπάξει μόνο. Αν είναι μια συνδεδεμένη λίστα, έχουμε για να μετακινηθείτε μέσα, σωστά; Έτσι πρόσβαση σε ένα στοιχείο σε ένας πίνακας είναι σταθερό χρόνο, ενώ με μια συνδεδεμένη λίστα που θα πιο πιθανό να είναι γραμμικό χρόνο, επειδή ίσως στοιχείο μας είναι όλος ο τρόπος στο τέλος. Πρέπει να ψάξετε μέσα από τα πάντα. Έτσι, με όλα αυτά τα δεδομένα δομές θα πάμε να περάσετε λίγο περισσότερο χρόνο για, ποια είναι τα συν και τα αρνητικά. Πότε μπορεί να θέλουμε να χρησιμοποιήστε ένα πάνω στο άλλο; Και αυτό είναι το είδος του μεγαλύτερο πράγμα που πρέπει να πάρει. Έτσι, έχουμε εδώ το ορισμός ενός κόμβου. Είναι σαν ένα στοιχείο στο συνδεδεμένη λίστα μας, σωστά; Έτσι, είμαστε όλοι εξοικειωμένοι με structs typedef μας, το οποίο πήγαμε πάνω στην αναθεώρηση τελευταία φορά. Ήταν ουσιαστικά μόνο τη δημιουργία Ένας άλλος τύπος δεδομένων που θα μπορούσαμε να χρησιμοποιήσουμε. Και σε αυτή την περίπτωση, είναι μερικά κόμβο ότι θα κρατήσει κάποια ακέραιο. Και τότε ποιο είναι το δεύτερο μέρος εδώ; Όποιος; ΚΟΙΝΟ: [δεν ακούγεται]. ΟΜΙΛΗΤΗΣ 1: Ναι. Είναι ένας δείκτης στον επόμενο κόμβο. Έτσι, αυτό θα πρέπει πραγματικά να είναι εδώ. Αυτό είναι ένας δείκτης τύπου κόμβος στο επόμενο πράγμα. Και αυτό είναι ό, τι περιλαμβάνει τον κόμβο μας. Cool. Εντάξει, έτσι με την αναζήτηση, όπως ήμασταν ακριβώς λέει πριν από το χέρι, εάν είστε πρόκειται να ψάξετε μέσα, θα πρέπει να επαναλάβει στην πραγματικότητα μέσω της συνδεδεμένης λίστας σας. Έτσι, αν ψάχνετε για τον αριθμό 9, θα ξεκινήσει στις κεφάλι μας και αυτό μας δείχνει στην αρχή της συνδεδεμένης λίστας μας, σωστά; Και λέμε, εντάξει, το κάνει αυτό κόμβος περιέχει τον αριθμό 9; Όχι; Εντάξει, πάμε στο επόμενο. Ακολουθήστε αυτό. Μήπως αυτό περιέχει τον αριθμό 9; Όχι. Ακολουθήστε το επόμενο. Έτσι πρέπει να επαναλάβει στην πραγματικότητα μέσω της συνδεδεμένης λίστας μας. Δεν μπορούμε απλά να πάμε κατευθείαν εκεί όπου 9 είναι. Και αν εσείς πραγματικά θέλετε να δείτε κάποια ψευδο-κώδικα μέχρι εκεί. Έχουμε κάποια λειτουργία αναζήτησης εδώ ότι παίρνει in-- τι χρειάζεται σε; Τι νομίζετε; Τόσο εύκολο. Τι είναι αυτό; ΚΟΙΝΟ: [δεν ακούγεται]. ΟΜΙΛΗΤΗΣ 1: Ο αριθμός που ψάχνουμε. Σωστά; Και τι θα ήταν αυτό αντιστοιχεί σε; Είναι ένας δείκτης για; ΚΟΙΝΟ: Ένας κόμβος. ΟΜΙΛΗΤΗΣ 1: Ένας κόμβος στη λίστα ότι ψάχνουμε σε, σωστά; Έτσι έχουμε μερικές κόμβους είναι δείκτης εδώ. Αυτό είναι ένα σημείο που πρόκειται να στην πραγματικότητα διέτρεξε τη λίστα μας. Θέτουμε το ίσο στη λίστα γιατί αυτό είναι ακριβώς ότι αυτό ισούται με το έναρξη της συνδεδεμένης λίστας μας. Και ενώ δεν είναι NULL, ενώ εξακολουθούμε να έχουμε τα πράγματα στη λίστα μας, ελέγξτε για να δείτε αν ο κόμβος έχει ο αριθμός που ψάχνουμε. Επιστροφή αλήθεια. Διαφορετικά, θα ενημερώσει, σωστά; Αν είναι NULL, βγαίνουμε μας ενώ βρόχο και επιστρέφει false γιατί αυτό σημαίνει ότι δεν έχουν βρεθεί. Μήπως ο καθένας να πάρει το πώς αυτό λειτουργεί; ΟΚ. Έτσι, με την εισαγωγή, σας έχουν τρεις διαφορετικούς τρόπους. Μπορείτε να προσθέσετε το πρόθεμα, μπορείτε να προσθέσετε και μπορείτε να τοποθετήσετε σε ανάμικτες. Σε αυτή την περίπτωση, είμαστε πρόκειται να κάνει μια βάλε. Ξέρει κανείς πώς αυτά τρεις περιπτώσεις ενδέχεται να διαφέρουν; Οπότε βάλε σημαίνει ότι βάζετε αυτό στο μπροστινό μέρος της λίστας σας. Έτσι, αυτό θα σήμαινε ότι δεν έχει σημασία τι κόμβος σας είναι, δεν έχει σημασία ποια είναι η αξία είναι, θα πάμε για να το θέσω εδώ μπροστά, εντάξει; Είναι πρόκειται να είναι η πρώτη στοιχείο στη λίστα σας. Αν προσάρτησή, πρόκειται να πάει στο πίσω μέρος της λίστας σας. Και τοποθετήστε σε ανάμικτες σημαίνει ότι είστε πρόκειται να θέσει πραγματικά σε θέση όπου κρατά συνδεδεμένη λίστα σας ταξινομούνται. Και πάλι, πώς μπορείτε να χρησιμοποιήσετε εκείνους και όταν χρησιμοποιείτε τους θα ποικίλλει ανάλογα με την περίπτωσή σας. Αν δεν χρειάζεται να να ταξινομηθούν, βάλε τείνει να είναι αυτό που οι περισσότεροι άνθρωποι χρησιμοποιούν γιατί δεν το κάνετε πρέπει να περάσουν από όλη τη λίστα για να βρείτε το τέλος για να το προσθέσετε στο, σωστά; Μπορείτε να το κολλήσετε ακριβώς δεξιά μέσα. Έτσι θα πάμε μέσα από μια εισαγωγή 1 τώρα. Έτσι, ένα πράγμα που θα πάω να το συνιστώ ανεπιφύλακτα σε αυτό το chipset είναι να σχεδιάσετε τα πράγματα έξω, όπως πάντα. Είναι πολύ σημαντικό να ενημερώσετε υποδείξεις σας με τη σωστή σειρά γιατί αν τους ενημερώσετε ελαφρώς εκτός λειτουργίας, θα πάμε να καταλήξετε χάνει τμήματα της λίστας σας. Έτσι, για παράδειγμα, στην περίπτωση αυτή, είμαστε λέει το κεφάλι ακριβώς σημείο προς 1. Αν εμείς κάνουμε ότι χωρίς να αποθηκεύσετε αυτό το 1, δεν έχουμε καμία ιδέα για το τι 1 πρέπει να επισημάνω τώρα γιατί έχουμε χάσει ό, τι το κεφάλι επεσήμανε. Έτσι, ένα πράγμα που πρέπει να θυμάστε όταν κάνεις μια βάλε είναι να σώσει ό, τι το σημεία της κεφαλής για την πρώτη, τότε η επανεκχώρηση, και στη συνέχεια να ενημερώσετε τι νέο κόμβο σας θα πρέπει να επισημάνω. Σε αυτήν την περίπτωση, αυτός είναι ένας τρόπος για να το κάνουμε. Έτσι, αν είχαμε κάνει αυτό τον τρόπο όπου εμείς απλά εκ νέου το κεφάλι, χάνουμε βασικά μας ολόκληρη τη λίστα, σωστά; Ένας τρόπος να γίνει αυτό είναι να έχετε 1 σημείο για να δίπλα, και στη συνέχεια να έχουν το σημείο το κεφάλι προς 1. Ή μπορείτε να κάνετε κάτι σαν το προσωρινής αποθήκευσης, τα οποία μίλησα. Αλλά η ανακατανομή σας δείκτες με τη σωστή σειρά πρόκειται να είναι πολύ, πολύ σημαντικό για αυτό το chipset. Διαφορετικά, θα πάμε να έχουν ένα hash πίνακα ή μια δοκιμή που είναι ακριβώς πρόκειται να είναι μέρος μόνο από τις λέξεις που σας θέλετε και στη συνέχεια mmhmm you're--; ΚΟΙΝΟ: Ποια ήταν η προσωρινή πράγμα αποθήκευσης μιλούσατε για; ΟΜΙΛΗΤΗΣ 1: Η προσωρινή αποθήκευση. Έτσι, βασικά άλλο τρόπο θα μπορούσατε να κάνετε αυτό έχει αποθηκεύσει το κεφάλι του κάτι, όπως αποθηκεύουν την προσωρινή μεταβλητή. Αναθέστε το σε 1 και στη συνέχεια να ενημερώσετε 1 στο σημείο σε ό, τι το κεφάλι χρησιμοποιείται για να υποδείξει. Με αυτό τον τρόπο είναι προφανώς πιο κομψό γιατί Δεν χρειάζεται μια προσωρινή αξία, αλλά ακριβώς προσφέρει έναν άλλο τρόπο για να το κάνουμε. Και πρέπει πραγματικά να κάνουμε έχουν μερικά κωδικό για αυτό. Έτσι, για την συνδεδεμένη λίστα, εμείς έχουν πραγματικά κάποιο κώδικα. Έτσι, τοποθετήστε εδώ, αυτό προσθέτοντας στην αρχή. Έτσι, αυτό που μπαίνει στο κεφάλι. Έτσι το πρώτο πράγμα, που πρέπει να δημιουργήσετε νέο κόμβο σας, φυσικά, και ελέγξτε για NULL. Πάντα καλό. Και τότε θα πρέπει να ορίσετε τις τιμές. Κάθε φορά που δημιουργείτε ένα νέο κόμβο, Δεν ξέρω τι είναι να υποδεικνύουν στην επόμενη, έτσι θέλετε να γίνει η προετοιμασία για την τιμή null. Αν δεν καταλήγουν επισημαίνοντας κάτι αλλού, παίρνει εκ νέου και είναι μια χαρά. Αν αυτό είναι το πρώτο πράγμα στη λίστα, χρειάζεται να επισημάνω σε μηδέν, επειδή αυτό είναι το τέλος της λίστας. Έτσι, στη συνέχεια, να το τοποθετήσετε, βλέπουμε εδώ Οι εκχώρηση την επόμενη τιμή του κόμβου μας να είναι ό, τι το κεφάλι είναι, η οποία είναι ό, τι είχαμε εδώ. Αυτό είναι ό, τι ακριβώς έκανε. Και τότε είμαστε ανάθεση κεφάλι στο σημείο στο νέο κόμβο μας, γιατί θυμηθείτε, νέα είναι μερικά δείκτη σε έναν κόμβο, και αυτό ακριβώς είναι το κεφάλι. Γι 'αυτό ακριβώς είμαστε έχουν αυτό το βέλος accessor. Cool; Mmhmm; ΚΟΙΝΟ: Μήπως πρέπει να προετοιμάσει νέες δίπλα σε null πρώτη, ή μπορούμε απλά να γίνει η προετοιμασία για το κεφάλι; ΟΜΙΛΗΤΗΣ 1: Νέα επόμενη πρέπει να είναι NULL, για να ξεκινήσετε επειδή δεν ξέρετε όπου πρόκειται να είναι. Επίσης, αυτό είναι το είδος του ήθελα απλώς ένα παράδειγμα. Μπορείτε να ορίσετε το ίσο με NULL μόνο για να κάνουν βεβαιωθείτε ότι όλες οι βάσεις σας καλύπτονται πριν κάνετε οποιαδήποτε αλλαγή, έτσι ώστε είστε πάντα εγγυημένο ότι θα να δείχνουν προς μια συγκεκριμένη τιμή έναντι σαν αξία σκουπίδια. Διότι, ναι, έχουμε αναθέσει νέες επόμενη αυτόματα, αλλά είναι περισσότερο σαν ένα καλή πρακτική να γίνει η προετοιμασία με αυτόν τον τρόπο και στη συνέχεια να εκχωρήσετε εκ νέου. Εντάξει, έτσι διπλά συνδεδεμένες λίστες τώρα. Τι νομίζετε; Αυτό που είναι διαφορετικό με διπλά συνδεδεμένες λίστες; Έτσι, σε συνδεδεμένες λίστες μας, μπορούμε να κινηθούν μόνο προς μία κατεύθυνση, σωστά; Έχουμε μόνο την επόμενη. Μπορούμε μόνο να πάμε μπροστά. Με μια διπλά συνδεδεμένη λίστα, μπορούμε επίσης να κινηθεί προς τα πίσω. Έτσι δεν έχουμε μόνο το αριθμό που θέλετε να αποθηκεύσετε, έχουμε όταν επισημαίνει στην επόμενη και όπου μόλις ήρθε από. Έτσι, αυτό επιτρέπει την κάποια καλύτερη διάσχιση. Έτσι, διπλά συνδεδεμένων κόμβων, πολύ παρόμοια, σωστά; Μόνο η διαφορά είναι τώρα έχουν ένα επόμενο και προηγούμενο. Είναι η μόνη διαφορά. Έτσι, αν ήμασταν για να προσθέσετε το πρόθεμα ή append-- μας δεν έχουν κανένα κώδικα για αυτό επάνω here-- αλλά αν ήταν να προσπαθήσουμε και να τοποθετήστε το, το σημαντικό πράγμα είναι που πρέπει να κάνετε ότι είστε ανάθεση δύο προηγούμενες σας και σας επόμενο δείκτη σωστά. Έτσι, σε αυτή την περίπτωση, τι θα κάνατε όχι μόνο να προετοιμάσει την επόμενη, θα προετοιμαστεί προηγούμενο. Αν είμαστε στην κορυφή της λίστας, μπορούμε θα κάνει όχι μόνο το κεφάλι ίση νέα, αλλά τα νέα μας τα προηγούμενα θα πρέπει να στραμμένη προς την κεφαλή, σωστά; Αυτή είναι η μόνη διαφορά. Και αν θέλετε περισσότερη πρακτική με αυτά με συνδεδεμένες λίστες, με εισαγωγής, με τη διαγραφή, με ένθετο σε μια μεγάλη λίστα, παρακαλώ ελέγξτε έξω study.cs50.net. Υπάρχει ένα μάτσο μεγάλες ασκήσεις. Θα ήθελα να συστήσω ανεπιφύλακτα. Μακάρι να είχαμε χρόνο να περάσει μέσα τους αλλά υπάρχει πολλή των δομών δεδομένων για να περάσει. Εντάξει, έτσι πίνακες κατακερματισμού. Αυτό είναι ίσως το πιο χρήσιμο κομμάτι για το chipset σας εδώ επειδή θα πάμε να είναι την εφαρμογή ενός από αυτά, ή μια δοκιμή. Μου αρέσει πραγματικά πίνακες κατακερματισμού. Είναι αρκετά δροσερό. Έτσι, βασικά, τι που συμβαίνει είναι ένας πίνακας κατακερματισμού είναι όταν χρειαζόμαστε πραγματικά ταχεία εισαγωγή, διαγραφή και αναζήτηση. Αυτά είναι τα πράγματα που είμαστε δίνοντας προτεραιότητα σε ένα πίνακα κατακερματισμού. Μπορούν να πάρουν αρκετά μεγάλο, αλλά όπως θα δούμε με το προσπαθεί, υπάρχουν πράγματα που είναι πολύ μεγαλύτερες. Αλλά βασικά, όλα ένα hash πίνακας είναι μια συνάρτηση κατακερματισμού ότι σας λέει ποια κουβά για να βάλει κάθε των δεδομένων σας, καθένα από τα στοιχεία σας σε. Ένας απλός τρόπος για να σκεφτώ έναν πίνακα κατακερματισμού είναι ότι είναι απλά κουβάδες των πραγμάτων, σωστά; Έτσι, όταν είστε τακτοποιήσει τα πράγματα από όπως και το πρώτο γράμμα του ονόματός τους, αυτό είναι το είδος του σαν ένα πίνακα κατακερματισμού. Έτσι, αν ήμουν στην ομάδα σας παιδιά είναι σε ομάδες όποιος ξεκινά όνομά του με Α εδώ, ή όποιος είναι τα γενέθλιά είναι τον Ιανουάριο, Φεβρουάριο, Μάρτιο, οτιδήποτε άλλο, ότι είναι αποτελεσματικά δημιουργία ενός πίνακα κατακερματισμού. Είναι απλά δημιουργώντας κουβάδες ότι ταξινομήσετε τα στοιχεία σας σε έτσι ώστε να μπορείτε να τα βρείτε ευκολότερα. Γι 'αυτόν τον τρόπο, όταν χρειάζομαι για να βρείτε ένα από εσάς, Δεν έχω να αναζητήσετε μέσα από κάθε ένα από τα ονόματά σας. Μπορώ να είμαι όπως, OH, ξέρω ότι Γενέθλια Danielle είναι in-- ΚΟΙΝΟ: --April. ΟΜΙΛΗΤΗΣ 1: Απρίλιο. Έτσι κοιτάζω τον Απρίλιο μου κουβά, και με λίγη τύχη, αυτή θα είναι η μόνη εκεί και ο χρόνος μου ήταν σταθερή σε αυτή την έννοια, ενώ αν έχω να κοιτάξουμε μέσα από ένα σωρό ανθρώπους, πρόκειται να διαρκέσει πολύ περισσότερο. Έτσι hash πίνακες είναι πραγματικά μόνο κουβάδες. Εύκολος τρόπος για να σκεφτώ τους. Έτσι, ένα πολύ σημαντικό πράγμα για ένα πίνακα κατακερματισμού είναι μια συνάρτηση κατακερματισμού. Έτσι τα πράγματα που μόλις μίλησα, όπως πρώτο γράμμα της πρώτης σας όνομα ή μήνα τα γενέθλιά σας, αυτά είναι ιδέες που πραγματικά συσχετίζονται με μια συνάρτηση κατακερματισμού. Είναι απλά ένας τρόπος για να κριθεί η οποία Σας κάδο στοιχείο είστε πηγαίνει σε, εντάξει; Έτσι για αυτό το chipset, μπορείτε να αναζητήσετε σχεδόν κάθε συνάρτηση κατακερματισμού που θέλετε. Δεν πρέπει να είναι δική σας. Υπάρχουν μερικά πραγματικά δροσερά αυτά έξω εκεί που κάνει όλα τα είδη των τρελά μαθηματικά. Και αν θέλετε να κάνετε σας ορθογράφος σούπερ γρήγορο, Θα ήθελα σίγουρα εξετάσουμε σε ένα από αυτά. Αλλά υπάρχουν επίσης και η απλές, όπως η υπολογιστική το άθροισμα των λέξεων, όπως κάθε γράμμα έχει έναν αριθμό. Υπολογίστε το ποσό. Αυτό καθορίζει τον κάδο. Έχουν, επίσης, τις εύκολες αυτά που είναι ακριβώς όπως όλα τα Α είναι εδώ, όλα τα Β είναι εδώ. Κάθε ένα από αυτά. Βασικά, αυτό σας λέει ακριβώς που Δείκτης σειρά στοιχείων σας θα πρέπει να πάει σε. Απλά να αποφασίσει την bucket-- είναι όλα μια συνάρτηση κατακερματισμού είναι. Έτσι, εδώ έχουμε ένα παράδειγμα το οποίο είναι μόνο το πρώτο γράμμα του string ότι ήμουν ακριβώς μιλάμε. Έτσι έχετε κάποια hash που είναι ακριβώς η πρώτο γράμμα της συμβολοσειράς σας μείον Α, το οποίο θα σας δώσει μερικές αριθμός μεταξύ 0 και 25. Και ό, τι θέλετε να κάνετε είναι να βεβαιωθείτε ότι αυτό αντιπροσωπεύει το μέγεθος του κατακερματισμού σας table-- πόσοι κάδοι υπάρχουν. Με πολλά από αυτά hash λειτουργίες, είναι πρόκειται να επιστρέφουν τιμές που θα μπορούσαν να είναι πολύ πάνω από τον αριθμό των κάδων ότι έχετε πραγματικά στον πίνακα κατακερματισμού σας, έτσι πρέπει να κάνετε βέβαιος και mod από αυτούς. Διαφορετικά, πρόκειται να πει, Ω, θα πρέπει να είναι σε κάδο 5.000 αλλά έχετε μόνο 30 κουβάδες στον πίνακα κατακερματισμού σας. Και φυσικά, όλοι γνωρίζουμε ότι είναι πρόκειται να οδηγήσει σε κάποια τρελά λάθη. Γι 'αυτό φροντίστε να mod από το το μέγεθος του πίνακα κατακερματισμού σας. Cool. Έτσι συγκρούσεις. Είναι όλοι καλά μέχρι στιγμής; Mmhmm; ΚΟΙΝΟ: Γιατί θα ήταν επιστρέφει μια τέτοια μαζική τιμή; ΟΜΙΛΗΤΗΣ 1: Ανάλογα με τον αλγόριθμο ότι η συνάρτηση κατακερματισμού σας χρησιμοποιεί. Μερικοί απ 'αυτούς θα κάνουμε τρελό πολλαπλασιασμό. Και είναι όλα για να πάρει μια ομοιόμορφη κατανομή, έτσι ώστε να κάνουν κάποια πραγματικά τρελά πράγματα μερικές φορές. Αυτό είναι όλο. Οτιδήποτε άλλο; ΟΚ. Έτσι συγκρούσεις. Βασικά, όπως είπα και προηγουμένως, στην καλύτερη περίπτωση, κάθε κάδο κοιτάζω μέσα είναι πρόκειται να έχουν ένα πράγμα, οπότε δεν έχω να εξετάσουμε όλα, σωστά; Ι είτε ξέρουν ότι είναι εκεί ή είναι όχι, και αυτό είναι που θέλουμε πραγματικά. Αλλά αν έχουμε δεκάδες χιλιάδες σημεία δεδομένων και μικρότερη από αυτόν τον αριθμό κάδων, θα πάμε να έχουν συγκρούσεις όπου τελικά κάτι θα πρέπει να καταλήξουν σε μια κουβά που έχει ήδη ένα στοιχείο. Έτσι, το ερώτημα είναι, τι μπορούμε να κάνουμε σε αυτή την περίπτωση; Τι πρέπει να κάνουμε; Έχουμε ήδη κάτι εκεί; Μήπως εμείς απλά το ρίξει έξω; Όχι. Πρέπει να κρατήσει και τους δύο. Έτσι ο τρόπος που εμείς συνήθως το κάνουμε αυτό είναι ό, τι; Ποια είναι η δομή δεδομένων εμείς απλά μίλησε; ΚΟΙΝΟ: συνδεδεμένη λίστα. ΟΜΙΛΗΤΗΣ 1: Μια συνδεδεμένη λίστα. Έτσι τώρα, αντί για κάθε ένα από αυτά κουβάδες έχοντας μόλις ένα στοιχείο, πρόκειται να περιέχει μια συνδεδεμένη λίστα τα στοιχεία που κατακερματίζεται σε αυτό. Εντάξει, ο καθένας έχει το είδος του να πάρει αυτή την ιδέα; Επειδή εμείς δεν θα μπορούσε να έχει μια σειρά γιατί δεν ξέρουμε πόσα πράγματα πρόκειται να είναι εκεί. Μια συνδεδεμένη λίστα μας επιτρέπει να έχουν ακριβώς τον ακριβή αριθμό στον οποίο οι Οι κατακερματίζεται σε αυτό το κουβά, σωστά; Έτσι γραμμική σχολαστικά είναι βασικά αυτό idea-- Είναι ένας τρόπος για να ασχοληθεί με μια σύγκρουση. Τι μπορείτε να κάνετε είναι αν, σε αυτό το περίπτωση, μούρο ήταν κατακερματισμένο σε 1 και έχουμε ήδη κάτι εκεί, απλά συνεχίστε προς τα κάτω έως ότου μπορείτε να βρείτε μια κενή υποδοχή. Αυτός είναι ένας τρόπος για να το χειριστεί. Ο άλλος τρόπος για να χειριστεί είναι με αυτό που μόλις called-- το συνδεδεμένο Λίστα λέγεται αλυσιδωτή σύνδεση. Έτσι, η ιδέα αυτή λειτουργεί αν πίνακα κατακερματισμού σας νομίζετε είναι πολύ μεγαλύτερο από σύνολο των δεδομένων σας ή αν έχετε θέλετε να δοκιμάσετε και την ελαχιστοποίηση αλυσιδωτή σύνδεση μέχρι να είναι απολύτως απαραίτητο. Έτσι, ένα πράγμα είναι γραμμική σχολαστικά προφανώς σημαίνει ότι η συνάρτηση κατακερματισμού σας δεν είναι τόσο χρήσιμα επειδή θα πάμε να καταλήξετε με συνάρτηση κατακερματισμού σας, να πάρει σε ένα σημείο, μπορείτε γραμμικό καθετήρα προς τα κάτω για να κάποια θέση που είναι διαθέσιμες. Αλλά τώρα, φυσικά, τίποτα άλλο που καταλήγει εκεί, εσείς πρόκειται να πρέπει να αναζήτηση ακόμη πιο κάτω. Και υπάρχουν πολλά περισσότερα δαπάνη αναζήτησης που πηγαίνει στην εισαγωγή ενός στοιχείου στον πίνακα κατακερματισμού σας τώρα, σωστά; Και τώρα, όταν θα πάτε και να προσπαθήσουμε και να βρούμε μούρο και πάλι, θα πάμε να το hash, και πρόκειται να πω, Ω, κοιτάξτε στον κάδο 1, και δεν πρόκειται να είναι σε κάδο 1, ώστε να είστε πρόκειται να πρέπει να διασχίσει μέσω του υπολοίπου αυτών. Έτσι είναι μερικές φορές χρήσιμο, αλλά στις περισσότερες περιπτώσεις, θα πάμε να πούμε ότι αλυσοποίησης είναι ό, τι θέλετε να κάνετε. Έτσι μιλήσαμε για το θέμα αυτό νωρίτερα. Πήρα λίγο μπροστά από τον εαυτό μου. Αλλά αλυσοποίησης είναι βασικά ότι κάθε κουβά στον πίνακα κατακερματισμού σας είναι απλά μια συνδεδεμένη λίστα. Έτσι, ένας άλλος τρόπος, ή πιο τεχνική τρόπο, να σκεφτούμε ένα πίνακα κατακερματισμού είναι ότι είναι απλά μια σειρά από συνδεδεμένες λίστες, οι οποίες όταν γράφετε λεξικό σας και προσπαθείτε να το φορτώσετε, σκέφτεται ως ένα σειρά από συνδεδεμένες λίστες θα καταστήσει πολύ πιο εύκολο για να προετοιμαστεί. ΚΟΙΝΟ: Έτσι πίνακα κατακερματισμού έχει ένα προκαθορισμένο μέγεθος, σαν [δεν ακούγεται] κάδων; ΟΜΙΛΗΤΗΣ 1: Δεξιά. Γι 'αυτό έχει ένα συγκεκριμένο αριθμό κάδων που determine-- οποία εσείς πρέπει να αισθανθείτε ελεύθερος να παίξει με. Μπορεί να είναι αρκετά δροσερό για να δούμε τι θα συμβεί όπως μπορείτε να αλλάξετε τον αριθμό σας κάδων. Αλλά ναι, θα έχει ένα ορίσετε τον αριθμό των κάδων. Αυτό σας επιτρέπει να χωρέσει ως πολλά στοιχεία που χρειάζεστε είναι αυτό Ξεχωριστές αλυσίδες, όπου μπορείτε Οι συνδεδεμένες λίστες σε κάθε κάδο. Αυτό σημαίνει πίνακα κατακερματισμού σας θα είναι ακριβώς το μέγεθος ότι θα πρέπει να είναι, σωστά; Αυτό είναι το νόημα της συνδεδεμένες λίστες. Cool. Έτσι, ο καθένας ΟΚ εκεί; Εντάξει. Αχ. Τι ακριβώς συνέβη; Πραγματικά τώρα. Μαντέψτε κάποιος με σκοτώνει. Εντάξει θα πάμε για να πάει σε προσπάθειες, οι οποίες είναι λίγο τρελός. Μου αρέσει πίνακες κατακερματισμού. Νομίζω ότι είναι πραγματικά δροσερό. Προσπαθεί είναι δροσερό, πάρα πολύ. Έτσι κάνει κάποιος που θυμάται τι μια δοκιμή είναι; Θα πρέπει να έχουν περάσει πάνω εν συντομία σε διάλεξη; Θυμάστε το είδος του πώς λειτουργεί; ΚΟΙΝΟ: Είμαι απλά κουνώντας ότι εμείς δεν πάμε πάνω από αυτό. ΟΜΙΛΗΤΗΣ 1: Εμείς δεν πάει πέρα ​​από αυτό. Εντάξει, είμαστε πραγματικά πρόκειται να πάει πάνω από αυτό τώρα είναι αυτό που λέμε. ΚΟΙΝΟ: Αυτό είναι ένα δέντρο ανάκτησης. ΟΜΙΛΗΤΗΣ 1: Ναι. Είναι ένα δέντρο ανάκτησης. Awesome. Έτσι, ένα πράγμα που πρέπει να παρατηρήσετε εδώ είναι ότι εμείς Ψάχνουμε σε μεμονωμένους χαρακτήρες εδώ, σωστά; Έτσι, πριν με συνάρτηση κατακερματισμού μας, έψαχναν τις λέξεις ως σύνολο, και τώρα ψάχνουμε περισσότερο στους χαρακτήρες, σωστά; Έτσι έχουμε Maxwell εδώ και Μέντελ. Έτσι ουσιαστικά ένα try-- ένας τρόπος να σκεφτούμε για αυτό είναι ότι κάθε επίπεδο εδώ Είναι μια σειρά από γράμματα. Έτσι, αυτή είναι η ρίζα του κόμβου σας εδώ, σωστά; Αυτό έχει όλους τους χαρακτήρες του αλφάβητο για την έναρξη της κάθε λέξης. Και ό, τι θέλετε να κάνετε είναι να ας πούμε, εντάξει, έχουμε κάποια λέξη Μ. Εμείς πάμε να δούμε για Maxwell, έτσι πάμε στο Μ Και Μ σημεία σε όλη την άλλα ένας πίνακας όπου κάθε λέξη, εφ 'όσον υπάρχει Είναι μια λέξη που έχει ένα ως τη δεύτερη επιστολή, εφ 'όσον υπάρχει μια λέξη που Β έχει ως δεύτερη επιστολή, θα έχει ένα δείκτη πηγαίνει σε κάποιο επόμενο πίνακα. Μάλλον δεν υπάρχει μια λέξη που MP κάτι, έτσι ώστε στη θέση Ρ σε αυτό σειρά, θα ήταν απλώς να NULL. Θα πω, εντάξει, δεν υπάρχει λέξη ότι έχει Μ ακολουθούμενη από μια P, εντάξει; Έτσι, αν το σκεφτούμε, κάθε ένα από αυτά τα μικρότερα πράγματα είναι στην πραγματικότητα μία από αυτές μεγάλες συστοιχίες από το Α έως το Z. Λοιπόν, τι θα μπορούσε να είναι ένα από τα πράγματα αυτό είναι το είδος της ένα μειονέκτημα μια δοκιμή; ΚΟΙΝΟ: Μια πολλή μνήμη. ΟΜΙΛΗΤΗΣ 1: Είναι ένας τόνος της μνήμης, σωστά; Κάθε ένα από αυτά τα μπλοκ εδώ αντιπροσωπεύει 26 θέσεις, 26 στοιχείο του πίνακα. Έτσι, προσπαθεί να πάρει απίστευτα χώρο βαρύ. Αλλά είναι πολύ γρήγορη. Έτσι απίστευτα γρήγορα, αλλά Πραγματικά χώρο αναποτελεσματική. Είδος πρέπει να υπολογίσετε από τα οποία το ένα που θέλετε. Αυτά είναι πραγματικά δροσερό για το chipset σας, αλλά καταλαμβάνουν πολλή μνήμη, έτσι ώστε να ανταλλάξει. Ναι; ΚΟΙΝΟ: Θα ήταν δυνατόν να δημιουργήσει μια δοκιμή και στη συνέχεια Μόλις έχετε όλα τα δεδομένα σε αυτό που σας need-- Δεν ξέρω αν αυτό θα είχε νόημα. Ήμουν να απαλλαγούμε από όλα τα NULL χαρακτήρες, αλλά στη συνέχεια, δεν θα είναι σε θέση να δείκτη them-- ΟΜΙΛΗΤΗΣ 1: Μπορείτε ακόμα να τους χρειάζονται. ΚΟΙΝΟ: - με τον ίδιο τρόπο κάθε φορά. ΟΜΙΛΗΤΗΣ 1: Ναι. Χρειάζεται η μηδενική χαρακτήρες για να αφήσει ξέρετε αν δεν υπάρχει μια λέξη. Ben είχατε κάτι που θέλετε; ΟΚ. Εντάξει, έτσι θα πάμε για να πάει λίγο πιο σε τεχνικές λεπτομέρειες πίσω μια δοκιμή και να εργαστούν μέσα από ένα παράδειγμα. Εντάξει, έτσι αυτό είναι το ίδιο πράγμα. Ενώ σε μια συνδεδεμένη λίστα, κύρια μας είδος of-- ποια είναι η λέξη που θέλω; - όπως η κατασκευή μπλοκ ήταν ένας κόμβος. Σε μια δοκιμή, έχουμε επίσης ένα κόμβο, αλλά είναι ορίζεται διαφορετικά. Έτσι έχουμε κάποια bool ότι αντιπροσωπεύει το αν μια λέξη στην πραγματικότητα υφίσταται σε αυτή τη θέση, και στη συνέχεια έχουμε κάποια σειρά here-- ή μάλλον, Αυτό είναι ένας δείκτης σε μια σειρά 27 χαρακτήρων. Και αυτό είναι, στην περίπτωση αυτή, αυτό 27-- Είμαι βέβαιος ότι όλοι σας είστε όπως, περιμένετε, υπάρχουν 26 γράμματα του αλφαβήτου. Γιατί έχουμε 27; Έτσι, ανάλογα με το τρόπο που εφαρμόζουν αυτό, Αυτό είναι από ένα PSET ότι επιτρέπεται για αποστρόφους. Έτσι, γι 'αυτό η επιπλέον μία. Θα πρέπει, επίσης, σε ορισμένες περιπτώσεις η μηδενική τερματισμού περιλαμβάνεται ως ένα από τα χαρακτήρων που του επιτρέπεται να είναι, και αυτό είναι το πώς να ελέγχετε να δούμε αν είναι το τέλος της λέξης. Αν σας ενδιαφέρει, ελέγξτε Βίντεο του Kevin για study.cs50, καθώς και η Wikipedia έχει μερικές καλές πόρους εκεί. Αλλά θα πάμε να περάσουν ακριβώς το είδος για το πώς θα μπορούσε να λειτουργήσει μέσα από μια δοκιμή αν σας δίνεται μία. Έτσι έχουμε ένα σούπερ απλό εδώ ότι έχει την ένδειξη "νυχτερίδα" και "ζουμ" σε αυτά. Και όπως βλέπουμε εδώ, αυτό το μικρό χώρο εδώ αντιπροσωπεύει bool μας ότι λέει, ναι, αυτό είναι μια λέξη. Και τότε αυτό έχει μας συστοιχίες των χαρακτήρων, σωστά; Γι 'αυτό και πρόκειται να περάσουν από εύρεση "νυχτερίδα" σε αυτή την προσπάθεια. Έτσι αρχίζουν στην κορυφή, δεξιά; Και γνωρίζουμε ότι η Β αντιστοιχεί στο ο δεύτερος δείκτης, το δεύτερο στοιχείο σε αυτή την συστοιχία, διότι a και b. Έτσι, περίπου το δεύτερο. Και λέει, εντάξει, δροσερό, έπεται ότι σε η επόμενη σειρά, γιατί αν θυμόμαστε, δεν είναι ότι κάθε ένα από αυτά πράγματι περιέχει το στοιχείο. Κάθε μία από αυτές τις συστοιχίες περιέχει ένα δείκτη, σωστά; Είναι μια σημαντική διάκριση να κάνει. Ξέρω ότι αυτό πρόκειται να be-- προσπαθεί είναι πραγματικά σκληρά για να πάρει την πρώτη φορά, έτσι ώστε ακόμη και αν αυτή είναι η δεύτερη ή τρίτη φορά και εξακολουθεί να είναι το είδος της φαινομενικά δύσκολο, Υπόσχομαι αν πάτε ρολόι η σύντομη και πάλι αύριο, αυτό θα κάνει πιθανότατα πολύ πιο λογικό. Χρειάζονται πολλά για να χωνέψει. Έχω ακόμα μερικές φορές είμαι όπως, περιμένετε, τι είναι μια δοκιμή; Πώς μπορώ να χρησιμοποιήσω αυτό; Έτσι, έχουμε Β σε αυτή την περίπτωση, το οποίο είναι το δεύτερο δείκτη μας. Αν είχαμε, ας πούμε, γ ή δ ή οποιοδήποτε άλλο έγγραφο, θα πρέπει να χάρτη που πίσω στο ευρετήριο της σειρά μας ότι αντιστοιχεί σε. Έτσι, θα μπορέσουμε να κάνουμε σαν rchar και εμείς απλά αφαιρούμε ένα για να χαρτογραφήσει σε 0 έως 25. Όλοι καλά πώς μπορούμε χάρτης χαρακτήρες μας; ΟΚ. Έτσι πάμε στο δεύτερο και εμείς βλέπουμε ότι, ναι, δεν είναι σε NULL. Μπορούμε να προχωρήσουμε σε αυτή την επόμενη σειρά. Έτσι, πάμε στην επόμενη αυτή σειρά εδώ. Και λέμε, εντάξει, τώρα είμαστε Πρέπει να δούμε αν ένας είναι εδώ. Είναι μια μηδενική ή μήπως πραγματικά να προχωρήσουμε; Έτσι, μια πραγματικότητα κινείται διαβιβάζει σε αυτήν την σειρά. Και λέμε, εντάξει, t είναι η τελευταία επιστολή μας. Έτσι πάμε στο t στο δείκτη. Και τότε θα προχωρήσουμε επειδή υπάρχει ένα άλλο. Και αυτό λέει βασικά ότι, ναι, λέει ότι υπάρχει μια λέξη here-- ότι αν ακολουθήσετε αυτό μονοπάτι, που έχουν φθάσει σε μια λέξη, η οποία γνωρίζουμε ότι είναι "νυχτερίδα". Ναι; ΚΟΙΝΟ: Είναι πρότυπο για να έχει ότι ως δείκτη 0 και στη συνέχεια να έχουν ένα είδος σε 1 ή να έχουν στο τέλος; ΟΜΙΛΗΤΗΣ 1: Όχι. Έτσι, αν κοιτάξουμε πίσω σε μας δήλωση εδώ, είναι μια bool, γι 'αυτό είναι δική του στοιχείο στον κόμβο σας. Έτσι δεν είναι μέρος της συστοιχίας. Cool. Έτσι, όταν θα τελειώσει το λόγο μας και είμαστε σε αυτή τη σειρά, αυτό που θέλουμε να κάνουμε είναι να κάνει έναν έλεγχο για αυτό είναι μια λέξη. Και σε αυτή την περίπτωση, θα επιστρέψει ναι. Έτσι, σε αυτό το σημείωμα, γνωρίζουμε ότι "ζωολογικός κήπος" - γνωρίζουμε ως άνθρωποι ότι "ζωολογικός κήπος" είναι μια λέξη, σωστά; Αλλά προσπαθήστε εδώ θα λένε, όχι, δεν είναι. Και θα έλεγα ότι επειδή εμείς Δεν έχουν οριστεί ως μια λέξη εδώ. Ακόμα κι αν μπορούμε να διασχίζουν μέσα σε αυτό το φάσμα, Αυτή η δοκιμή θα έλεγα ότι, όχι, ζωολογικός κήπος δεν είναι στο λεξικό σας γιατί δεν έχουμε ορίζεται ως τέτοια. Έτσι, ένας τρόπος για να γίνει that-- Ω, συγγνώμη, αυτό το ένα. Έτσι, σε αυτή την περίπτωση, "ζωολογικός κήπος" δεν είναι μια λέξη, αλλά είναι στην προσπάθεια μας. Αλλά σε αυτό το ένα, ας πούμε θέλουμε εισάγει τη λέξη "μπάνιο," τι συμβαίνει Είναι ακολουθούμε through-- β, Α, Τ. Είμαστε σε αυτή τη σειρά, και πάμε για να αναζητήσετε h. Στην περίπτωση αυτή, όταν εξετάσουμε το δείκτη σε ώρα, αυτό είναι που δείχνουν προς NULL, εντάξει; Έτσι, αν δεν είναι ρητά επισημαίνοντας μια άλλη σειρά, θα υποθέσουμε ότι όλοι οι δείκτες σε αυτήν την σειρά είναι στραμμένες σε null. Έτσι, στην περίπτωση αυτή, h είναι στραμμένη σε null έτσι δεν μπορούμε να κάνουμε τίποτα, έτσι θα επιστρέψει επίσης ψευδείς, "λουτρό" δεν είναι εδώ. Έτσι τώρα είμαστε στην πραγματικότητα πρόκειται να περάσουν από πώς θα μπορούμε πραγματικά να πω ότι «ζωολογικός κήπος» είναι στην προσπάθεια μας. Πώς εισάγουμε "ζωολογικό κήπο" σε προσπάθεια μας; Έτσι, με τον ίδιο τρόπο που ξεκινήσαμε με συνδεδεμένη λίστα μας, ξεκινάμε από τη ρίζα. Σε περίπτωση αμφιβολίας, ξεκινούν από η ρίζα αυτών των πραγμάτων. Και εμείς θα πούμε, εντάξει, z. z υπάρχει σε αυτό, και να το κάνει. Έτσι είστε κινείται προς επόμενη σειρά σας, εντάξει; Και στη συνέχεια στο επόμενο, λέμε, εντάξει, δεν υπάρχει o; Κάνει. Αυτό πάλι. Και ούτω καθεξής επόμενο μας, έχουμε πει, Εντάξει, "ζωολογικό κήπο" υπάρχει ήδη εδώ. Όλα πρέπει να κάνετε είναι να ορίσετε αυτή την ίση στην αλήθεια, ότι υπάρχει μια λέξη. Αν είχε ακολουθήσει τα πάντα μέχρι και πριν από εκείνο το σημείο, είναι μια λέξη, τόσο απλά που είναι ίση με τέτοια. Ναι; ΚΟΙΝΟ: Μέχρι τότε κάνει ότι σημαίνει ότι «BA» είναι μια λέξη που επίσης; ΟΜΙΛΗΤΗΣ 1: Όχι. Έτσι, σε αυτή την περίπτωση, "βα" θα πάρει Εδώ, θα λέγαμε είναι μια λέξη, και θα εξακολουθεί να υπάρχει. Εντάξει; Mmhmm; ΚΟΙΝΟ: Μέχρι τη στιγμή που θα είναι ένα λέξη και λέτε ναι, τότε θα περιέχει να πάει να μ? ΟΜΙΛΗΤΗΣ 1: Έτσι, αυτό έχει να κάνει with-- είστε φόρτωση αυτό. Λέτε "ζωολογικός κήπος" είναι μια λέξη. Όταν πηγαίνετε να check-- όπως, ας πούμε ότι θέλετε να πείτε, δεν "ζωολογικός κήπος" υπάρχουν σε αυτό το λεξικό; Είστε μόνο πρόκειται να ψάξετε για "ζωολογικό κήπο" και, στη συνέχεια, ελέγξτε για να δείτε αν είναι μια λέξη. Ποτέ δεν πρόκειται να κινηθεί μέσα σε m, διότι αυτό δεν είναι αυτό που ψάχνετε. Έτσι, αν πραγματικά θέλαμε να προσθέστε το «λουτρό» σε αυτή την προσπάθεια, εμείς θα κάνουμε το ίδιο πράγμα όπως κάναμε με την «ζωολογικό κήπο», εκτός θα δούμε ότι, όταν εμείς να προσπαθήσουμε και να πάρει ώρες, δεν υπάρχει. Έτσι, μπορείτε να σκεφτείτε αυτό ως προσπαθεί για να προσθέσετε ένα νέο κόμβο σε μια συνδεδεμένη λίστα, γι 'αυτό θα πρέπει να προσθέσετε ένα άλλο μία από αυτές τις συστοιχίες, όπως έτσι. Και τότε αυτό που κάνουμε είναι να οριστεί ακριβώς το h στοιχείο αυτού του πίνακα δείχνουν προς αυτό. Και τότε τι θα θέλουμε να κάνουμε εδώ; Προσθέστε την ισότιμη αλήθεια γιατί είναι μια λέξη. Cool. Το ξέρω. Προσπαθεί να μην είναι η πιο συναρπαστική. Πίστεψέ με, το ξέρω. Έτσι, ένα πράγμα που πρέπει να συνειδητοποιήσουμε με προσπάθειες, Είπα, ότι είναι πολύ αποδοτικό. Έτσι έχουμε τους δει καταλαμβάνουν έναν τόνο του χώρου. Θα είστε το είδος της σύγχυσης. Επομένως, γιατί θα έχουμε ποτέ χρησιμοποιήσει αυτά; Χρησιμοποιούμε αυτά επειδή είναι απίστευτα αποτελεσματική. Έτσι, εάν είστε ποτέ ψάχνουν μέχρι μια λέξη, είστε μόνο που οριοθετείται από το μήκος της λέξης. Έτσι, αν ψάχνετε για ένα λέξη που είναι μήκους πέντε, είστε μόνο πρόκειται ποτέ να πρέπει να κάνει το πολύ πέντε συγκρίσεις, εντάξει; Έτσι καθιστά ουσιαστικά σταθερή. Όπως εισαγωγή και αναζήτηση είναι βασικά σταθερό χρόνο. Έτσι, αν ποτέ να πάρετε κάτι σε συνεχή χρόνο, αυτό είναι τόσο καλό όσο παίρνει. Δεν μπορείτε να πάρετε καλύτερα από ό, τι σταθερό χρόνο για αυτά τα πράγματα. Έτσι, αυτό είναι ένα από τα τεράστιο συν του προσπαθεί. Αλλά αυτό είναι ένα πολύ χώρο. Έτσι, κατά κάποιο τρόπο πρέπει να αποφασίσει τι είναι πιο σημαντικό για εσάς. Και για τους σημερινούς υπολογιστές, η χώρο ότι μια δοκιμή μπορεί να διαρκέσει έως ίσως δεν επηρεάζει σας τόσο πολύ, αλλά ίσως έχουμε να κάνουμε με κάτι ότι έχει πολύ, πολύ περισσότερα πράγματα, και μια δοκιμή απλά δεν είναι λογικό. Ναι; ΚΟΙΝΟ: Περιμένετε, έτσι έχετε 26 επιστολές σε κάθε μία; ΟΜΙΛΗΤΗΣ 1: Mmhmm. Ναι, έχετε 26. Έχετε κάποια είναι δείκτης λέξη και, στη συνέχεια, έχετε 26 δείκτες σε κάθε μία. Και όπου και αν point-- ΚΟΙΝΟ: Και κάθε 26, δεν το καθένα έχει 26; ΟΜΙΛΗΤΗΣ 1: Ναι. Και γι 'αυτό, όπως μπορείτε δείτε, διαστέλλεται αρκετά γρήγορα. Εντάξει. Έτσι θα πάμε να μπει σε δέντρα, τα οποία Νιώθω σαν να είναι ευκολότερος και μάλλον θα είναι μια ωραία μικρή ανάπαυλα από προσπαθεί εκεί. Έτσι, ελπίζουμε ότι οι περισσότεροι από εσάς έχουν δει ένα δέντρο πριν. Δεν αρέσει το όμορφο αυτοί έξω, που εγώ Δεν ξέρω αν κάποιος πήγε σε εξωτερικούς χώρους πρόσφατα. Πήγα μήλο να πάρει αυτό το Σαββατοκύριακο, και Θεέ μου, ήταν όμορφη. Δεν ήξερα φύλλα θα μπορούσε να εξετάσει αυτό αρκετά. Έτσι, αυτό είναι μόνο ένα δέντρο, σωστά; Είναι μερικά μόνο κόμβο, και επισημαίνει σε μια δέσμη των άλλων κόμβων. Όπως μπορείτε να δείτε εδώ, αυτό είναι το είδος της ένα επαναλαμβανόμενο θέμα. Κόμβοι κατάδειξης σε κόμβους είναι το είδος του η ουσία πολλών δομών δεδομένων. Δεν εξαρτάται μόνο από το πώς εμείς πρέπει να επισημάνω σε κάθε άλλη και πώς θα διασχίσει μέσα από αυτά και πώς μπορούμε εισάγετε Πράγματα που καθορίζει διαφορετικά χαρακτηριστικά τους. Έτσι, μερικά μόνο ορολογία, το οποίο έχω χρησιμοποιήσει πριν. Έτσι ρίζα είναι ό, τι είναι στην κορυφή. αυτό είναι όπου μπορούμε πάντα να ξεκινήσετε. Μπορείτε να σκεφτείτε από το ως το κεφάλι επίσης. Αλλά για τα δέντρα, έχουμε την τάση να αναφέρονται σε αυτήν ως τη ρίζα. Οτιδήποτε στο κάτω μέρος here-- στο πολύ, πολύ bottom-- Δεν θεωρούνται φύλλα. Έτσι, πηγαίνει μαζί με το όλο θέμα δέντρο, σωστά; Τα φύλλα είναι στα άκρα του δέντρου σας. Και στη συνέχεια, έχουμε επίσης ένα ζευγάρι των όρους για να μιλήσουμε για τους κόμβους σε σχέση ο ένας στον άλλο. Έτσι έχουμε γονέα, τα παιδιά, και τα αδέλφια. Έτσι, στην περίπτωση αυτή, 3 είναι η γονέας 5, 6, και 7. Έτσι, ο γονέας είναι ό, τι είναι ένα βήμα πάνω από ό, τι είστε αναφέρεστε, έτσι απλά σαν ένα οικογενειακό δέντρο. Ας ελπίσουμε ότι όλα αυτά είναι λίγο λίγο πιο έξυπνο από ό, τι τις προσπάθειες. Τα αδέλφια είναι κάποια που έχουν την ίδια μητρική, σωστά; Είναι στο ίδιο επίπεδο εδώ. Και τότε, όπως ήμουν λένε, τα παιδιά είναι απλώς ό, τι είναι ένα βήμα παρακάτω το συγκεκριμένο κόμβο, εντάξει; Cool. Έτσι, ένα δυαδικό δένδρο. Μπορεί κανείς να τολμούσα να πω σε έναν από τους τα χαρακτηριστικά του δυαδικού δένδρου; ΚΟΙΝΟ: Max δύο φύλλα. ΟΜΙΛΗΤΗΣ 1: Δεξιά. Έτσι, το μέγιστο όριο των δύο φύλλων. Έτσι, σε αυτό το ένα πριν, είχαμε αυτό το ένα ότι είχε τρεις, αλλά σε ένα δυαδικό δέντρο, έχετε ένα μέγιστο των δύο παιδιά ανά γονέα, σωστά; Υπάρχει ένα άλλο ενδιαφέρον χαρακτηριστικό. Ξέρει κανείς αυτό; Δυαδικό δέντρο. Έτσι, ένα δυαδικό δέντρο θα έχει τα πάντα για the-- αυτό δεν είναι sorted-- αλλά σε ένα ταξινομημένο δυαδικό δέντρο, τα πάντα σχετικά με το δικαίωμα είναι μεγαλύτερη από την μητρική, και τα πάντα για την αριστερά είναι μικρότερο από το γονέα. Και αυτό ήταν ένα κουίζ ερώτηση πριν, οπότε καλό να γνωρίζουμε. Έτσι, ο τρόπος που ορίζουμε αυτό, και πάλι, έχουμε ένα άλλο κόμβο. Αυτό μοιάζει πολύ με αυτό; Διπλάσια ΚΟΙΝΟ: Συνδεδεμένες λίστες ΟΜΙΛΗΤΗΣ 1: Ένα διπλό συνδεδεμένη λίστα, σωστά; Έτσι, αν αντικαταστήσουμε αυτό με την προηγούμενη και την επόμενη, Αυτό θα ήταν μια διπλά συνδεδεμένη λίστα. Αλλά σε αυτή την περίπτωση, εμείς στην πραγματικότητα έχουν αριστερά και δεξιά και αυτό είναι όλο. Διαφορετικά, είναι ακριβώς το ίδιο. Έχουμε ακόμα το στοιχείο ψάχνετε για, και έχετε μόνο δύο δείκτες πρόκειται για ό, τι γίνεται στη συνέχεια. Ναι, έτσι δυαδικό δέντρο αναζήτησης. Αν παρατηρήσετε, τα πάντα σχετικά με το εδώ είναι μεγαλύτερη than-- ή ό, τι αμέσως προς τα δεξιά εδώ είναι μεγαλύτερο από ό, τι εδώ είναι μικρότερη. Έτσι, αν ήμασταν για να αναζητήσετε μέσα από αυτό, πρέπει να εξετάσουμε πολύ κοντά σε δυαδική αναζήτηση εδώ, σωστά; Εκτός αντί να ψάχνει στο μισό της συστοιχίας, είμαστε απλά κοιτάζοντας είτε αριστερά πλευρά ή η δεξιά πλευρά του δένδρου. Γι 'αυτό παίρνει λίγο πιο απλό, νομίζω. Έτσι, αν ρίζα σας είναι NULL, προφανώς είναι απλά ψευδής. Και αν είναι εκεί, προφανώς αυτό είναι αλήθεια. Αν είναι λιγότερο από ό, τι, ψάχνουμε το αριστερό. Αν είναι μεγαλύτερη από ό, τι, ψάχνουμε το δικαίωμα. Είναι ακριβώς σαν δυαδική αναζήτηση, απλά μια διαφορετική δομή δεδομένων ότι είμαστε χρησιμοποιούν. Αντί μίας συστοιχίας, είναι ακριβώς ένα δυαδικό δέντρο. ΟΚ, στοίβες. Και, επίσης, φαίνεται σαν να θα μπορούσαν να έχουν λίγο χρόνο. Αν το κάνουμε, είμαι στην ευχάριστη θέση να πάει πάνω από οποιοδήποτε από αυτό και πάλι. Εντάξει, έτσι στοίβες. Υπάρχει κάποιος που θυμάται τι stacks-- οποιαδήποτε χαρακτηριστικά μιας στοίβας; Εντάξει, έτσι οι περισσότεροι από εμάς, νομίζω, τρώνε στην τραπεζαρία halls-- όσο εμείς μπορεί να μην αρέσει σε. Αλλά, προφανώς, μπορείτε να σκεφτείτε μια στοίβα κυριολεκτικά ακριβώς όπως μια στοίβα δίσκων ή ένα σωρό από πράγματα. Και τι είναι σημαντικό να συνειδητοποιήσουμε είναι ότι είναι something-- το χαρακτηριστικό ότι καλούμε by-- είναι LIFO. Ξέρει κανείς τι σημαίνει; Mmhmm; ΚΟΙΝΟ: Τελευταία in, first out. ΟΜΙΛΗΤΗΣ 1: Δεξιά, διαρκούν in, first out. Έτσι, αν γνωρίζουμε, αν είμαστε στοίβαγμα πράγματα up, το πιο εύκολο πράγμα να αρπάξει off-- και ίσως το μόνο πράγμα που μπορούμε να αρπάξει εκτός αν στοίβα μας είναι μεγάλη enough-- είναι ότι η κορυφαία στοιχείο. Έτσι, ό, τέθηκε σε last-- όπως βλέπουμε εδώ, ό, τι ωθήθηκε στις περισσότερες recently-- είναι πρόκειται να είναι η πρώτη πράγμα που θα σκάσει μακριά, εντάξει; Έτσι, αυτό που έχουμε εδώ είναι άλλο struct typedef. Αυτό είναι πραγματικά ακριβώς όπως ένα Crash Course στη δομή δεδομένων, οπότε δεν υπάρχουν πολλά που ρίχνονται σε σας παιδιά. Το ξέρω. Έτσι, ένα ακόμη struct. Yay για δομές. Και σε αυτή την περίπτωση, είναι μερικά δείκτη σε μία συστοιχία που έχει κάποια ικανότητα. Έτσι, αυτό αντιπροσωπεύει το stack μας Εδώ, όπως και την πραγματική σειρά μας ότι κρατά τα στοιχεία μας. Και τότε εδώ έχουμε κάποιο μέγεθος. Και συνήθως, θέλετε να κρατήσετε κομμάτι του πόσο μεγάλο stack σας είναι γιατί ό, τι πρόκειται να επιτρέψει μπορείτε να κάνετε είναι εάν ξέρετε το μέγεθος, σας επιτρέπει να πω, Εντάξει, είμαι σε ικανότητα; Μπορώ να προσθέσω τίποτα περισσότερο; Και αυτό σας λέει επίσης όπου η κορυφή της στοίβας σας είναι έτσι ώστε να ξέρετε τι σας μπορεί πραγματικά να απογειωθεί. Και αυτό είναι πραγματικά πρόκειται να να είναι λίγο πιο σαφής εδώ. Έτσι, για την ώθηση, ένα πράγμα, αν ήταν ποτέ να εφαρμόσει ώθηση, όπως ήμουν ακριβώς λέει, σας στοίβα έχει περιορισμένο μέγεθος, σωστά; Σειρά μας είχε κάποια ικανότητα. Είναι μια σειρά. Είναι ένα σταθερό μέγεθος, γι 'αυτό πρέπει να βεβαιωθείτε ότι δεν είμαστε βάζοντας περισσότερα σε σειρά μας από ό, τι εμείς στην πραγματικότητα έχουν χώρο για. Έτσι, όταν είστε δημιουργώντας μια ώθηση λειτουργία, το πρώτο πράγμα που κάνετε είναι να πούμε, εντάξει, έχω χώρο στη στοίβα μου; Διότι, αν δεν το κάνω, συγγνώμη, Δεν μπορώ να αποθηκεύσετε το στοιχείο σας. Αν το κάνω, τότε θέλετε να αποθηκεύσετε αυτό στην κορυφή της στοίβας, έτσι; Και αυτός είναι ο λόγος που έχουμε να παρακολουθείτε το μέγεθος μας. Αν δεν παρακολουθείτε το μέγεθος μας, δεν ξέρουμε πού να το θέσω. Δεν ξέρουμε πόσα πράγματα βρίσκονται σε συστοιχία μας ήδη. Όπως προφανώς υπάρχουν τρόποι ότι ίσως θα μπορούσα να το κάνω. Θα μπορούσε να προετοιμάσει τα πάντα για να NULL και, στη συνέχεια, ελέγξτε για την τελευταία NULL, αλλά ένα πολύ πιο εύκολο πράγμα είναι απλά να πω, εντάξει, να παρακολουθείτε το μέγεθος. Όπως ξέρω ότι έχω τέσσερα στοιχεία σε σειρά μου, έτσι το επόμενο πράγμα ότι βάζουμε σε, είμαστε πρόκειται να αποθηκεύσετε στο ευρετήριο 4. Και τότε, φυσικά, αυτό σημαίνει ότι έχετε πίεσε επιτυχώς κάτι σε στοίβα σας, θέλουν να αυξήσουν το μέγεθος έτσι ώστε να γνωρίζουν πού είστε, ώστε ότι μπορείτε να ωθήσει περισσότερα πράγματα σχετικά. Έτσι, αν προσπαθούμε να σκάσει κάτι από τη στοίβα, τι θα μπορούσε να είναι το πρώτο πράγμα ότι θέλουμε να ελέγξουμε για; Προσπαθείς να λάβει κάτι από το stack σας. Είσαι σίγουρος ότι υπάρχει κάτι το stack σας; Όχι. Λοιπόν, τι θα μπορούσαμε να θέλετε να ελέγξετε; ΚΟΙΝΟ: [δεν ακούγεται]. ΟΜΙΛΗΤΗΣ 1: Αναχώρηση για το μέγεθος; Μέγεθος. Θέλουμε, λοιπόν, να ελέγξετε για να δείτε αν μέγεθος μας είναι μεγαλύτερη από 0, εντάξει; Και αν είναι, τότε θέλουμε να μειώσετε μέγεθος μας από το 0 και να επιστρέψετε αυτό. Γιατί; Στο πρώτο ήμασταν πιέζει, εμείς έσπρωξε στο μέγεθος και στη συνέχεια ενημερώνεται το μέγεθος. Σε αυτή την περίπτωση, είμαστε Decrementing μέγεθος και στη συνέχεια, λαμβάνοντας μακριά, εκρίζωση από σειρά μας. Γιατί θα μπορούσαμε να το κάνουμε αυτό; Έτσι, αν έχω ένα πράγμα για το stack μου, τι θα είναι το μέγεθος μου σε εκείνο το σημείο; 1. Και πού είναι το στοιχείο 1 αποθηκεύεται; Σε ό, τι δείκτη; ΚΟΙΝΟ: 0. ΟΜΙΛΗΤΗΣ 1: 0. Έτσι, σε αυτή την περίπτωση, έχουμε πρέπει πάντα να κάνουν sure-- αντί να επιστρέψει μέγεθος μείον 1, γιατί εμείς γνωρίζουν ότι το στοιχείο μας είναι πρόκειται να αποθηκεύονται στους μείον 1 ανεξάρτητα από το μέγεθός μας είναι, αυτό απλά φροντίζει για αυτό. Είναι μια ελαφρώς πιο κομψό τρόπο. Και εμείς απλά θα ελαττωθεί μας μέγεθος και, στη συνέχεια, το μέγεθος επιστρέψουν. Mmhmm; ΚΟΙΝΟ: Υποθέτω ότι μόνο σε γενικές γραμμές, γιατί θα ήταν αυτή η δομή δεδομένων είναι επωφελής; ΟΜΙΛΗΤΗΣ 1: Εξαρτάται από το πλαίσιο σας. Έτσι, για ορισμένα από τη θεωρία, αν εργάζεστε with-- ΟΚ, επιτρέψτε μου να δούμε αν υπάρχει μια ευεργετική ότι είναι ευεργετικό για περισσότερο από έξω της CS. Με στοίβες, κάθε φορά που θα χρειαστεί να παρακολουθείτε κάτι που είναι η πιο πρόσφατη που προστίθεται είναι όταν θα πάμε να θέλετε να χρησιμοποιήσετε μια στοίβα. Και δεν μπορώ να σκεφτώ ένα καλό παράδειγμα του ότι αυτή τη στιγμή. Αλλά κάθε φορά που το πιο πρόσφατο πράγμα που είναι πιο σημαντικό για εσάς, ότι όταν μια στοίβα πρόκειται να είναι χρήσιμη. Προσπαθώ να σκεφτώ αν υπάρχει μια καλή χρονιά για αυτό. Αν νομίζω ότι ένα καλό παράδειγμα στην επόμενη 20 λεπτά, εγώ θα σας πω σίγουρα. Αλλά συνολικά, αν υπάρχει κάτι, όπως είπα οι περισσότεροι, όπου οι πιο πρόσφατες είναι το πιο σημαντικό, ότι είναι όπου μια στοίβα μπαίνει στο παιχνίδι. Ότι οι ουρές είναι είδος για το αντίθετο. Και όλα τα μικρά σκυλιά. Δεν είναι αυτό το μεγάλο, σωστά; Νιώθω σαν να πρέπει να απλά έχουν ένα βίντεο λαγουδάκι ακριβώς στη μέση του ενότητα για σας παιδιά επειδή αυτό είναι ένα έντονο τομή. Έτσι, μια ουρά. Βασικά μια ουρά είναι σαν μια γραμμή. Εσείς Είμαι βέβαιος ότι αυτή η καθημερινή χρήση, ακριβώς όπως σε αίθουσες τραπεζαρία μας. Έτσι πρέπει να πάμε σε και να πάρει τους δίσκους μας, είμαι βεβαιωθείτε ότι έχετε να περιμένουν στην ουρά να σύρετε ή να πάρετε το φαγητό σας. Έτσι, η διαφορά εδώ είναι ότι αυτό είναι FIFO. Έτσι, αν LIFO ήταν τελευταία στην πρώτη έξω, FIFO είναι first in, first out. Έτσι, αυτό είναι όπου ό, τι βάζετε την πρώτη είναι το πιο σημαντικό σας. Έτσι, αν ήταν σε αναμονή σε line-- μπορεί να σας φανταστείτε αν πήγε να πάει να πάρει το νέο iPhone και ήταν μια στοίβα όπου ο τελευταίο άτομο στη γραμμή πήρε την πρώτη, οι άνθρωποι θα σκοτώσουν ο ένας τον άλλον. Έτσι FIFO, είμαστε όλοι πολύ εξοικειωμένοι με το πραγματικό κόσμο εδώ, και αυτό έχει να κάνει με πραγματικά το είδος της αναδημιουργώντας όλη αυτή την γραμμή και οι ουρές δομή. Έτσι, ενώ με τη στοίβα, έχουμε ώθηση και ποπ. Με μια ουρά, έχουμε Τοποθέτηση στην ουρά και dequeue. Έτσι Τοποθέτηση στην ουρά σημαίνει βασικά το βάζουμε πάνω στο πίσω μέρος, και dequeue μέσα λάβουν μακριά από το μέτωπο. Έτσι δομή δεδομένων μας είναι ένα λίγο πιο περίπλοκη. Έχουμε ένα δεύτερο πράγμα που πρέπει να παρακολουθείτε. Έτσι, χωρίς το κεφάλι, αυτό είναι ακριβώς μια στοίβα, σωστά; Αυτή είναι η ίδια δομή ως μια στοίβα. Το μόνο πράγμα διαφορετικό τώρα είναι εμείς έχουν αυτό το κεφάλι, το οποίο ό, τι νομίζετε πρόκειται να παρακολουθείτε; ΚΟΙΝΟ: Η πρώτη. ΟΜΙΛΗΤΗΣ 1: Δεξιά, η το πρώτο πράγμα που βάλαμε στο. Ο επικεφαλής της ουράς μας. Όποιος είναι πρώτος στη γραμμή. Εντάξει, οπότε αν κάνουμε Τοποθέτηση στην ουρά. Πάλι, με οποιοδήποτε από Αυτές οι δομές δεδομένων, δεδομένου ότι έχουμε να κάνουμε με μια σειρά, θα πρέπει να ελέγξετε αν έχουμε χώρο. Αυτό είναι το είδος του σαν να μου λέει σας παιδιά, αν ανοίξετε ένα αρχείο, θα πρέπει να ελέγξετε για μηδενική. Με οποιαδήποτε από αυτές τις στοίβες και ουρές, θα πρέπει να έχετε για να δούμε αν υπάρχει χώρος, γιατί είμαστε που ασχολούνται με τα σταθερά συστήματα μεγέθους, όπως βλέπουμε here-- 0, 1, όλα έως 5. Λοιπόν, τι κάνουμε σε αυτή την περίπτωση είναι επιταγή για να δούμε αν έχουμε ακόμα χώρο. Είναι το μέγεθος μας λιγότερο από την ικανότητα; Αν ναι, θα πρέπει να το αποθηκεύσετε σε η ουρά και ανανεώνουμε το μέγεθος μας. Λοιπόν, τι θα μπορούσε να είναι η ουρά σε αυτή την περίπτωση; Δεν είναι γραμμένο ρητά. Πώς θα μπορούμε να το αποθηκεύσετε; Ποια θα ήταν η ουρά είναι; Ας περπατήσει μέσα από αυτό το παράδειγμα. Έτσι, αυτό είναι μια σειρά από μέγεθος 6, σωστά; Και έχουμε τώρα, το μέγεθος μας είναι 5. Και όταν βάζουμε μέσα, αυτό συμβαίνει να πάει στο πέμπτο δείκτη, σωστά; Έτσι αποθηκεύετε σε ουρά. Ένας άλλος τρόπος για να γράψει ουρά θα ήταν απλά είναι σειρά μας στο δείκτη του μεγέθους, σωστά; Αυτό είναι το μέγεθος 5. Το επόμενο πράγμα που πρόκειται να πάει σε 5. Cool; ΟΚ. Παίρνει λίγο πιο περίπλοκη όταν αρχίζουμε μπέρδεμα με το κεφάλι. Ναι; ΚΟΙΝΟ: Μήπως αυτό σημαίνει ότι εμείς θα έχουν δηλώσει έναν πίνακα που Ήταν μεγάλη πέντε στοιχεία και Στη συνέχεια προσθέτουμε σε αυτό; ΟΜΙΛΗΤΗΣ 1: Όχι. Έτσι, σε αυτή την περίπτωση, αυτό είναι μια στοίβα. Αυτό θα πρέπει να δηλώνονται ως μια σειρά από μέγεθος 6. Και σε αυτή την περίπτωση, έχουμε απλά έχουν ένα χώρο αριστερά. Εντάξει, έτσι ένα πράγμα είναι αυτό περίπτωση, εάν το κεφάλι μας είναι στο 0, τότε μπορούμε απλά να το προσθέσετε στο μέγεθος. Αλλά παίρνει μια λίγο πιο περίπλοκη επειδή στην πραγματικότητα, αυτοί δεν έχουν μια διαφάνεια για αυτό, έτσι Πάω να συντάξει μία, διότι δεν είναι είναι ότι αρκετά απλό μόλις αρχίσετε να απαλλαγούμε από τα πράγματα. Έτσι, ενώ με μια στοίβα το μόνο που έχετε ποτέ να ανησυχείτε για το τι είναι το μέγεθος όταν θέλετε να προσθέσετε κάτι σε, με μια ουρά θα πρέπει επίσης να βεβαιωθείτε ότι το κεφάλι σας είναι λογιστικά, επειδή ένα δροσερό πράγμα για ουρές είναι ότι, αν δεν είστε σε χωρητικότητα, μπορείτε πραγματικά να κάνετε το τυλίξετε γύρω. Εντάξει, έτσι ένα thing-- OH, Αυτό είναι τρομερό κιμωλία. Ένα πράγμα που πρέπει να εξεταστεί είναι η περίπτωση. Θα κάνουμε ακριβώς πέντε. Εντάξει, έτσι θα πάμε να λένε ότι το κεφάλι είναι εδώ. Αυτό είναι 0, 1, 2, 3, 4. Το κεφάλι είναι εκεί, και παρακαλώ να έχετε τα πράγματα σε αυτά. Και θέλουμε να προσθέσουμε κάτι σε, σωστά; Έτσι, το πράγμα που πρέπει να γνωρίζουμε είναι ότι το κεφάλι είναι πάντα πρόκειται να κινηθεί με αυτό τον τρόπο και τότε βρόχο πίσω γύρω, εντάξει; Έτσι, αυτή η ουρά έχει χώρο, σωστά; Έχει χώρο στην αρχή, είδος του αντίθετου αυτό. Έτσι, αυτό που πρέπει να κάνουμε είναι να πρέπει να υπολογίσει την ουρά. Αν ξέρετε ότι σας το κεφάλι δεν έχει μετακινηθεί, ουρά είναι ακριβώς σειρά σας σε ο δείκτης του μεγέθους. Αλλά στην πραγματικότητα, αν χρησιμοποιείτε μια ουρά, το κεφάλι σου είναι πιθανόν να ενημερώνεται. Έτσι, αυτό που χρειάζεται να κάνετε είναι να πράγματι υπολογίσει την ουρά. Έτσι, αυτό που κάνουμε είναι αυτός ο τύπος εδώ, η οποία Πάω να σας αποκαλύψω παιδιά σκέφτομαι, και Στη συνέχεια θα μιλήσουμε γι 'αυτό. Έτσι, αυτό είναι ικανότητα. Έτσι, αυτό θα είναι πράγματι να σας δώσει έναν τρόπο να το κάνουμε. Επειδή σε αυτή την περίπτωση, τι; Το κεφάλι μας είναι στο 1, το μέγεθος μας είναι 4. Αν mod ότι από 5, παίρνουμε 0, η οποία είναι όπου θα πρέπει να εισάγετε. Έτσι, στη συνέχεια, στην επόμενη περίπτωση, αν ήταν να το κάνετε αυτό, λέμε, εντάξει, ας dequeue κάτι. Εμείς dequeue αυτό. Βγάζουμε το στοιχείο αυτό, σωστά; Και τώρα το κεφάλι μας προς τα εδώ, και θέλουμε να προσθέσουμε σε ένα άλλο πράγμα. Αυτή είναι βασικά η πίσω από τη γραμμή μας, σωστά; Ουρές να τυλίξετε γύρω από τη συστοιχία. Αυτή είναι μία από τις κύριες διαφορές. Στοίβες, δεν μπορείτε να το κάνετε αυτό. Με ουρές, μπορείτε να γιατί όλα αυτά τα θέματα είναι ότι ξέρετε τι ήταν πιο πρόσφατα πρόσθεσε. Από ό, τι πρόκειται να προστεθεί στην Αυτή η αριστερά κατεύθυνση, σε αυτή την περίπτωση, και, στη συνέχεια, τυλίξτε γύρω, μπορείτε να να συνεχίσει βάζοντας σε νέα στοιχεία στο μπροστινό μέρος της συστοιχίας γιατί δεν είναι πραγματικά το μπροστινό μέρος του πίνακα πια. Μπορείτε να σκεφτείτε από την αρχή του συστοιχία ως όπου το κεφάλι σας πραγματικά είναι. Έτσι, αυτός ο τύπος είναι το πώς να υπολογίσετε την ουρά σου. Μήπως αυτό έχει νόημα; ΟΚ. Εντάξει, dequeue, και στη συνέχεια, εσείς έχετε 10 λεπτά να μου υποβάλετε οποιεσδήποτε ερωτήσεις διευκρινιστική θέλετε, γιατί ξέρω ότι είναι τρελό. Εντάξει, έτσι με τον ίδιο τρόπο-- Δεν ξέρω αν εσείς παρατηρήσει, αλλά CS είναι όλα σχετικά με τα πρότυπα. Τα πράγματα είναι λίγο πολύ το ίδιο, μόνο με μικροσκοπικά τσιμπήματα. Έτσι ίδιο πράγμα εδώ. Θα πρέπει να ελέγξετε για να δείτε αν όντως έχουν κάτι στην ουρά μας, σωστά; Ας πούμε, εντάξει, είναι το μέγεθός μας είναι μεγαλύτερη από 0; Cool. Αν το κάνουμε, τότε μπορούμε να μετακινήσετε το κεφάλι μας, η οποία είναι αυτό που μόλις αποδειχθεί εδώ. Ενημερώνουμε το κεφάλι μας να είναι ένα ακόμη. Και τότε θα ελαττώσει μας μεγέθους και να επιστρέψετε το στοιχείο. Υπάρχει πολύ πιο συγκεκριμένη κώδικα για study.cs50.net, και συστήνω ανεπιφύλακτα να πάτε μέσα από αυτό, αν έχετε χρόνο, ακόμα κι αν είναι απλά ένα ψευδο-κώδικα. Και αν εσείς θέλετε να μιλήσετε μέσω ότι μαζί μου ένας προς έναν, παρακαλώ επιτρέψτε μου γνωρίζει. Θα ήμουν ευτυχής να. Δομές δεδομένων, εάν παίρνετε CS 124, θα γνωρίζουμε ότι οι δομές δεδομένων πάρει πολύ διασκέδαση και αυτό είναι μόνο η αρχή. Έτσι, ξέρω ότι είναι δύσκολο. Είναι εντάξει. Παλεύουμε. Εξακολουθώ να κάνω. Γι 'αυτό μην ανησυχείτε πάρα πολύ για αυτό. Αλλά αυτό είναι βασικά σας Crash Course σε δομές δεδομένων. Ξέρω ότι είναι πολλά. Υπάρχει κάτι που μπορούμε Θα ήθελα να πάμε ξανά; Οτιδήποτε θέλουμε να μιλήσουμε μέσα; Ναι; ΚΟΙΝΟ: Για αυτό το παράδειγμα, έτσι η νέα ουρά είναι στο 0 πάνω από αυτό; ΟΜΙΛΗΤΗΣ 1: Ναι. ΚΟΙΝΟ: Εντάξει. Έτσι, στη συνέχεια, περνάει, θα είχατε 1 συν 4 or-- ΟΜΙΛΗΤΗΣ 1: Έτσι θα έλεγαν, όταν θέλουμε να πάει να κάνει αυτό ξανά; Κοινό: Ναι. Έτσι, αν ήταν υπολογίζοντας out-- όπου είναι να υπολογίσετε την ουρά από το γεγονός ότι; ΟΜΙΛΗΤΗΣ 1: Έτσι, η ουρά ήταν in-- Έχω αλλάξει αυτό. Έτσι, σε αυτό το παράδειγμα εδώ, αυτό ήταν η συστοιχία ψάχνουμε, εντάξει; Έτσι έχουμε τα πράγματα σε 1, 2, 3, και 4. Έτσι έχουμε το κεφάλι μας είναι ίση με 1 σε αυτό το σημείο, και το μέγεθος μας είναι ίση με 4 σε αυτό το σημείο, σωστά; Θα συμφωνήσουμε όλοι ότι είναι η περίπτωση; Έτσι κάνουμε το κεφάλι συν το μέγεθος, το οποίο μας δίνει 5, και στη συνέχεια εμείς mod από 5. Παίρνουμε 0, η οποία μας λέει ότι είναι 0 όπου είναι η ουρά μας, όπου έχουμε χώρο. ΚΟΙΝΟ: Τι είναι ένα καπάκι; ΟΜΙΛΗΤΗΣ 1: Η ικανότητα. Λυπάμαι. Έτσι, αυτό είναι το μέγεθος του πίνακα σας. Ναι; ΚΟΙΝΟ: [δεν ακούγεται] πριν θα επιστρέψει το στοιχείο; ΟΜΙΛΗΤΗΣ 1: Προχωρούμε λοιπόν η το κεφάλι ή να επιστρέψετε τη στιγμή; Έτσι, αν προχωρήσουμε ένα, να ελαττώσει το μέγεθος; Περίμενε. Σίγουρα ξέχασα άλλο. Δεν πειράζει. Δεν υπάρχει άλλο τύπο. Ναι, θα θέλετε να επιστρέψετε το κεφάλι και στη συνέχεια, μετακινηθείτε προς τα πίσω. ΚΟΙΝΟ: Εντάξει, γιατί σε αυτό το σημείο, το κεφάλι ήταν στο 0, και στη συνέχεια θέλετε να επιστρέψετε δείκτης 0 και στη συνέχεια να κάνουν το κεφάλι 1; ΟΜΙΛΗΤΗΣ 1: Δεξιά. Νομίζω ότι υπάρχει μια άλλη τύπο κάτι σαν αυτό. Εγώ δεν το έχουν στην κορυφή της κεφαλής μου ως Δεν θέλω να σας δώσει το λάθος. Αλλά νομίζω ότι είναι απόλυτα έγκυρο να ας πούμε, εντάξει, να αποθηκεύσετε αυτή element-- ανεξαρτήτως στοιχείο το κεφάλι του is-- ελαττώσει σας μέγεθος, μετακινήστε το κεφάλι σας πάνω και επιστροφή ό, τι το στοιχείο αυτό είναι. Αυτό είναι απολύτως έγκυρη. ΟΚ. Νιώθω σαν αυτό δεν είναι όπως το most-- δεν είστε πρόκειται να περπατήσει από εδώ όπως, ναι, ξέρω ότι προσπαθεί. Μου πήρε όλα. Αυτό είναι ΟΚ. Υπόσχομαι. Αλλά δομές δεδομένων είναι κάτι που παίρνει πολύ χρόνο για να το συνηθίσετε. Πιθανώς ένα από τα δυσκολότερα τα πράγματα, νομίζω, κατά τη διάρκεια. Γι 'αυτό παίρνει σίγουρα επανάληψη και αναζητούν at-- μου Δεν ήξερα πραγματικά συνδεδεμένες λίστες έως ότου έκανα πάρα πολύ μαζί τους, με τον ίδιο τρόπο που δεν το έκανα πραγματικά καταλαβαίνω δείκτες μέχρι Είχα να το διδάξει για δύο χρόνια και να κάνω τη δική μου psets με αυτό. Χρειάζεται πολλή επανάληψη και χρόνο. Και τελικά, αυτό θα το είδος κάντε κλικ. Αλλά εν τω μεταξύ, αν έχετε το είδος ενός υψηλού επιπέδου κατανόηση του τι Αυτά τα κάνουν, τα πλεονεκτήματα τους και cons-- το οποίο είναι ό, τι είμαστε πραγματικά τείνουν να δώσουν έμφαση, ειδικά κατά τη διάρκεια intro. Όπως, γιατί θα χρησιμοποιήσουμε δοκιμάστε πάνω από μια σειρά; Όπως, ποια είναι τα θετικά και αρνητικά καθενός από αυτά; Και η κατανόηση τους συμβιβασμούς μεταξύ κάθε μία από αυτές τις δομές είναι αυτό που είναι πολύ πιο σημαντικό αυτή τη στιγμή. Μπορεί να υπάρχει ένας τρελός ερώτηση ή δύο που είναι πρόκειται να σας ζητήσω να εφαρμόσουν push ή εφαρμογή ποπ ή Τοποθέτηση στην ουρά και dequeue. Αλλά για το μεγαλύτερο μέρος, έχοντας ότι υψηλότερο επίπεδο κατανόησης και περισσότερα από μια διαισθητική κατανόηση είναι πιο σημαντική από ό, τι στην πραγματικότητα να είναι σε θέση να την εφαρμόσουν. Θα ήταν πραγματικά φοβερό εάν όλοι σας θα μπορούσε να πάει έξω και να πάει να εφαρμόσουν μια δοκιμή, αλλά καταλαβαίνουμε ότι δεν είναι κατ 'ανάγκην το πιο λογικό πράγμα τώρα. Αλλά μπορείτε να το chipset σε σας, αν θέλετε σε, και στη συνέχεια θα έχετε την πρακτική, και, στη συνέχεια, ίσως θα πραγματικά καταλαβαίνουν. Ναι; ΚΟΙΝΟ: Εντάξει, έτσι ποια είναι εννοούσαμε να χρησιμοποιήσετε το το chipset; Χρειάζεται να χρησιμοποιήσετε ένα από αυτά; ΟΜΙΛΗΤΗΣ 1: Ναι. Έτσι, έχετε την επιλογή σας. Υποθέτω ότι σε αυτή την περίπτωση, μπορούμε μιλήσουμε για το το chipset λίγο γιατί έτρεξα μέσω αυτών. Έτσι, στο το chipset σας, έχετε σας επιλογή του προσπαθεί ή πίνακες κατακερματισμού. Μερικοί άνθρωποι θα προσπαθήσουν και χρησιμοποιήστε τα φίλτρα άνθιση, αλλά εκείνοι τεχνικά δεν είναι σωστό. Λόγω της πιθανολογική φύση τους, δίνουν ψευδώς θετικά αποτελέσματα μερικές φορές. Είναι δροσερή ματιά σε, όμως. Το συνιστώ ανεπιφύλακτα ψάχνετε σε αυτούς τουλάχιστον. Αλλά έχετε την επιλογή σας μεταξύ ενός πίνακα κατακερματισμού και μια δοκιμή. Και αυτό πρόκειται να είναι, όπου φορτώνετε στο λεξικό σας. Και θα πρέπει να επιλέξετε συνάρτηση κατακερματισμού σας, θα πρέπει να επιλέξετε πόσες Κάδοι έχετε, και θα ποικίλλουν. Όπως και αν έχετε περισσότερους κάδους, ίσως θα τρέξει πιο γρήγορα. Αλλά ίσως να σπαταλάτε ένα πολύ χώρο με αυτόν τον τρόπο, όμως. Θα πρέπει να το καταλάβω. Mmhmm; ΚΟΙΝΟ: Είπατε πριν ότι μπορούμε να χρησιμοποιήσουμε άλλες συναρτήσεις κατακερματισμού, ότι δεν έχουμε να δημιουργήσετε μια συνάρτηση κατακερματισμού; ΟΜΙΛΗΤΗΣ 1: Ναι, σωστά. Έτσι, κυριολεκτικά για την συνάρτηση κατακερματισμού σας, όπως το google "συνάρτηση κατακερματισμού" και να ψάξουν για μερικά δροσερά αυτά. Δεν αναμένεται να οικοδομήσουμε τις δικές σας συναρτήσεις κατακερματισμού. Οι άνθρωποι ξοδεύουν τους Θέσεις για αυτά τα πράγματα. Γι 'αυτό μην ανησυχείτε για την οικοδόμηση δική σας. Βρείτε ένα σε απευθείας σύνδεση για να αρχίσει με. Μερικά από αυτά θα πρέπει να χειριστείτε λίγο για να βεβαιωθείτε ότι οι τύποι επιστροφής ταιριάζουν και εταζέρα, έτσι στην αρχή, Θα ήθελα να συστήσω χρησιμοποιώντας κάτι πραγματικά εύκολο που ίσως μόνο hashes για το πρώτο γράμμα. Και στη συνέχεια, αφού έχετε αυτή την εργασία, ενσωματώνει ένα ψύκτη συνάρτηση κατακερματισμού. Mmhmm; ΚΟΙΝΟ: Θα προσπαθήσουμε να είναι ή αποτελεσματική, αλλά μόνο πιο δύσκολο να, like-- ΟΜΙΛΗΤΗΣ 1: Έτσι μια δοκιμή, νομίζω, είναι διαισθητικά δύσκολο να εφαρμοστούν αλλά είναι πολύ γρήγορη. Ωστόσο, καταλαμβάνει περισσότερο χώρο. Και πάλι, μπορείτε να βελτιστοποιήσετε τις δύο αυτές διαφορετικούς τρόπους και υπάρχουν τρόποι to-- ΚΟΙΝΟ: Πώς θα βαθμολογούνται σε αυτό; Μήπως matter-- ΟΜΙΛΗΤΗΣ 1: Έτσι είστε βαθμολογούνται κανονικό τρόπο. Θα πάμε για να βαθμολογηθούν για το σχεδιασμό. Όποιον τρόπο κι αν κάνετε, θέλετε να βεβαιωθείτε ότι είναι τόσο κομψό όπως μπορεί να είναι και τόσο αποτελεσματικές όσο μπορεί να είναι. Αλλά αν επιλέξετε μια δοκιμή ή κατακερματισμού τραπέζι, εφ 'όσον αυτό λειτουργεί, είμαστε ευχαριστημένοι με αυτό. Και αν μπορείτε να χρησιμοποιήσετε κάτι που hashes για το πρώτο γράμμα, ότι είναι εντάξει, όπως ίσως όπως ο σχεδιασμός-σοφός. Είμαστε, επίσης, φθάνοντας το σημείο σε αυτό το semester-- Δεν ξέρω αν σας παιδιά noticed-- αν είστε βαθμούς το chipset μειωθεί λίγο λόγω του σχεδιασμού και εταζέρα, ότι είναι απολύτως εντάξει. Είναι να πάρει σε ένα σημείο όπου σας προγράμματα γίνονται όλο και πιο περίπλοκη. Υπάρχουν περισσότερες θέσεις μπορείτε να βελτιώσετε. Γι 'αυτό είναι απόλυτα φυσιολογικό. Δεν είναι ότι είστε κάνει χειρότερα για το chipset σας. Είναι ακριβώς θέλουμε να είμαστε πιο δύσκολο για σας τώρα. Έτσι, ο καθένας έχει το συναίσθημα. Απλώς βαθμολογούνται όλα psets σας. Ξέρω ότι ο καθένας έχει το συναίσθημα. Έτσι, δεν πρέπει να ανησυχούν γι 'αυτό. Και εάν έχετε οποιεσδήποτε ερωτήσεις σχετικά με πριν psets ή τρόπους μπορείτε να βελτιώσετε, Προσπαθώ και να σχολιάσει το συγκεκριμένο θέσεις, αλλά μερικές φορές είναι αργά και έχω κουραστεί. Υπάρχουν άλλα πράγματα εκεί σχετικά με τις δομές δεδομένων; Είμαι βέβαιος ότι εσείς δεν κάνετε πραγματικά θέλω να μιλήσω γι 'αυτούς πια, αλλά αν υπάρχουν, είμαι στην ευχάριστη θέση να πάει πάνω τους, καθώς και οτιδήποτε από διάλεξη αυτό το παρελθόν εβδομάδα ή την περασμένη εβδομάδα. Ξέρω ότι την περασμένη εβδομάδα ήταν όλα επανεξέτασης, έτσι μπορεί να έχουμε υπερπηδηθούν κάποια αναθεώρηση από τη διάλεξη. Οποιεσδήποτε άλλες ερωτήσεις μπορώ να απαντήσω; Εντάξει, εντάξει. Λοιπόν, εσείς να πάρετε πίσω 15 λεπτά νωρίτερα. Ελπίζω ότι αυτό ήταν ημι-χρήσιμο, τουλάχιστον, και εγώ θα σας δούμε παιδιά την επόμενη εβδομάδα, ή την Πέμπτη τις ώρες γραφείου. Οι αιτήσεις εκεί για σνακ για την επόμενη εβδομάδα, αυτό είναι το πράγμα; Επειδή ξέχασα καραμέλα σήμερα. Και έφερα καραμέλα τελευταία εβδομάδα, αλλά ήταν Ημέρα του Κολόμβου, έτσι υπήρχαν όπως και έξι άτομα που είχε τέσσερις σακούλες των καραμέλα για τους εαυτούς τους. Μπορώ να φέρω αστρικές εκρήξεις και πάλι, αν σας αρέσει. Αστρικές εκρήξεις; Εντάξει, ακούγεται καλό. Έχετε μια μεγάλη μέρα, παιδιά.