[Παίζει μουσική] 

ANDI PENG: Καλώς ήρθατε στην εβδομάδα 6 του τμήματος. Θα παρέκκλινε από το βιοτικό μας χρόνος τμήμα της Τρίτης απόγευμα σε αυτό το υπέροχο την Κυριακή το πρωί. Σας ευχαριστώ για τον καθένα που μαζί μου σήμερα, αλλά σοβαρά, ένα χειροκρότημα. 

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

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

Έτσι, γρήγορα, πριν ξεκινήσουμε, η ατζέντα για σήμερα έχει ως εξής. Όπως μπορείτε να δείτε, είμαστε βασικά ταχείας βολής μέσα από ένα σωρό δομών δεδομένων πραγματικά, πραγματικά, πραγματικά γρήγορα. Έτσι ως τέτοια, δεν θα είναι σούπερ διαδραστικά σήμερα. Δεν θα πρέπει ακριβώς να μου φωνάζει το είδος του Πράγματα που, και αν μπορώ να σας μπερδέψει, Αν πάω πάρα πολύ γρήγορα, επιτρέψτε μου να ξέρω. Είναι απλά διάφορα στοιχεία δομές, και ως μέρος από το chipset σας για αυτή την ερχόμενη βδομάδα, θα κληθούν να εφαρμόσουν ένα από αυτά, ίσως δύο από them-- δύο από αυτούς στο PSET σας. Εντάξει, έτσι είμαι απλώς πρόκειται να ξεκινήσουμε με κάποιες ανακοινώσεις. Θα πάμε πάνω από στοίβες και ουρές περισσότερο βάθος από ό, τι κάναμε πριν από το κουίζ. Θα πάμε πάνω συνδέεται λίστα και πάλι, για μια ακόμη φορά, περισσότερο σε βάθος από ό, τι είχαμε πριν από την κουίζ. Και τότε θα μιλήσουμε για χασίς πίνακες, τα δέντρα και προσπαθεί, η οποία είναι όλα πολύ απαραίτητο για το chipset σας. Και τότε θα πάμε πάνω από κάποια χρήσιμες συμβουλές για pset5. 

Εντάξει, έτσι κουίζ 0. Ο μέσος όρος ήταν 58%. Θα ήταν πολύ χαμηλή, και έτσι εσείς όλοι έκανε πολύ, πολύ καλά σύμφωνα με αυτό. 

Λίγο πολύ, κανόνας είναι, αν είστε εντός μια τυπική απόκλιση της μέσης δεδομένου μάλιστα ότι είμαστε σε μια λιγότερο άνετο μέρος, είσαι μια χαρά. Είσαι σε καλό δρόμο. Η ζωή είναι ωραία. 

Ξέρω ότι είναι τρομακτικό να σκεφτεί κανείς ότι Πήρα σαν ένα 40% σε αυτό το κουίζ. Πάω να αποτύχει αυτή την κατηγορία. Σας υπόσχομαι, δεν είστε πρόκειται να αποτύχει την κατηγορία. Είσαι μια χαρά. 

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

Εντάξει, έτσι pset5, αυτό είναι ένα πραγματικά παράξενο εβδομάδα για Yale, με την έννοια ότι το chipset μας οφείλεται Τετάρτη το μεσημέρι, συμπεριλαμβανομένων ο αείμνηστος μέρα, γι 'αυτό είναι πραγματικά θεωρητικά οφείλεται Τρίτη το μεσημέρι. Μάλλον κανείς δεν τελείωσε στις Τρίτη το μεσημέρι. Αυτό είναι εντελώς καλά. Εμείς πάμε για να έχουμε ώρες γραφείου απόψε, καθώς το βράδυ της Δευτέρας. Και όλα τα τμήματα αυτής της εβδομάδας θα πράγματι να μετατραπεί σε εργαστήρια, έτσι αισθάνεται ελεύθερη να σκάσει στα κάθε ενότητα που θέλετε, και θα είναι είδος μίνι-PSET εργαστήρια για βοήθεια σχετικά με αυτό. Έτσι ως τέτοιο, αυτό είναι το μόνο τμήμα όπου είμαστε διδακτικό υλικό. Όλα τα άλλα τμήματα θα εστιάσει αποκλειστικά στη βοήθεια για την PSET. Ναι; 

Κοινό: Πού είναι οι ώρες γραφείου; 

ANDI PENG: Ώρες εργασίας γραφείου tonight-- Ω, καλή ερώτηση. Νομίζω ώρες γραφείου απόψε είναι Teal ή Commons. Εάν ελέγχετε σε απευθείας σύνδεση CS50 και πηγαίνετε σε ώρες γραφείου, θα πρέπει να υπάρχει ένα πρόγραμμα που σας όπου όλοι τους είναι λέει. 

Ξέρω είτε απόψε ή αύριο είναι κιρκίρι, και νομίζω ότι μπορεί να έχουμε commons για την άλλη νύχτα. Δεν ειμαι σιγουρος. Καλή ερώτηση. Έλεγχος CS50. 

Cool, οποιεσδήποτε ερωτήσεις σχετικά με το χρονοδιάγραμμα για την επόμενη σαν τρεις μέρες; Υπόσχομαι εσείς σαν τον Δαβίδ είπε, αυτή είναι η κορυφή του λόφου. Εσείς είστε σχεδόν εκεί. Μόλις τρεις μέρες. Φύγε από εκεί, και στη συνέχεια όλοι θα κατέβει. Θα έχουμε ένα ωραίο CS-δωρεάν διάλειμμα. Καλωσόρισες πίσω. Θα βουτήξει διαδίκτυο προγραμματισμός και ανάπτυξη, πράγματα που είναι πολύ διασκεδαστικό σύγκριση για μερικά από τα άλλα psets. Και αυτό θα είναι ψύχρα, και θα έχουν πολλή διασκέδαση. Θα έχουμε περισσότερες καραμέλα. Συγγνώμη για την καραμέλα. Ξέχασα καραμέλα. Ήταν μια πρόχειρη πρωί. Έτσι, εσείς είστε σχεδόν εκεί, και είμαι πραγματικά περήφανος για σας παιδιά. 

Εντάξει, έτσι στοίβες. Που αγάπησε το ερώτημα για τον Jack και τα ρούχα του στο κουίζ; Κανένας? Εντάξει, αυτό είναι εντάξει. 

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

Ουσιαστικά, σκεφτείτε ένα στοίβα όπως και κάθε στοίβα αντικειμένων όπου μπορείτε να βάλετε τα πράγματα στο επάνω μέρος, και Στη συνέχεια μπορείτε να πεταχτεί έξω από την κορυφή. Έτσι LIFO είναι το ακρωνύμιο που μας αρέσουν να use-- Τελευταία In, First Out. Και έτσι αντέξει στο επάνω μέρος της στοίβα είναι το πρώτο που βγαίνει. Και έτσι οι δύο όροι θα ήθελα να συμφωνήσω με τα οποία καλούνται ώθησης και ποπ. Όταν πατήσετε κάτι πάνω στο στοίβα, και μπορείτε να επανακάμψει. 

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

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

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

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

Έτσι, για παράδειγμα, αυτό το υπέροχο ερώτημα ήταν σε ένα κουίζ σας. Ουσιαστικά πώς θα ωθήσει πάνω στην κορυφή της στοίβας. Πολύ απλά. Αν το δει κανείς, θα περπατήσετε μέσα από αυτό. Εάν [δεν ακούγεται] size-- θυμηθείτε, κάθε φορά που θέλουν να έχουν πρόσβαση σε οποιαδήποτε παράμετρος μέσα σε ένα struct, κάνετε το όνομα της struct.parameter. 

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

Θέλετε να αποκτήσετε πρόσβαση στο εσωτερικό του stack σας, έτσι s.strings, και θα πάμε για να θέσει το νέο αριθμό ότι θέλετε να εισαγάγετε στο εκεί. Ας πούμε απλά ότι θα θελήσουμε να εισάγετε int n στη στοίβα, θα μπορούσαμε να κάνουμε s.strings, παρένθεση, s.size ισούται με n. Επειδή το μέγεθος είναι όπου είμαστε Αυτή τη στιγμή είναι στη στοίβα αν θα πάμε για να ωθήσει τον, εμείς απλά πρόσβαση όπου το μέγεθος είναι, η τρέχουσα πληρότητα της στοίβας, και πιέστε το int n επάνω σε αυτό. Και μετά θέλουμε να βεβαιωθείτε ότι είμαστε επίσης που αυξάνει το μέγεθος του n, έτσι ώστε να μπορείτε να παρακολουθείτε έχουμε προστίθεται ένα επιπλέον πράγμα στη στοίβα. Τώρα έχουμε ένα μεγαλύτερο μέγεθος. Μήπως αυτό εδώ έχει νόημα να ο καθένας, πώς λογικά λειτουργεί; Ήταν το είδος του γρήγορα. Κοινό: Μπορείτε να πάτε πάνω οι s.stringss.strings [s.size] και πάλι; ANDI PENG: Σίγουρα, ναι, τι κάνει s.size σήμερα μας δίνουν; Κοινό: Είναι το τρέχον μέγεθος. ANDI PENG: Ακριβώς, έτσι ώστε η Ευρετήριο που το μέγεθός μας είναι, και έτσι θέλουμε να θέσει το νέο ακέραιο ότι θέλουμε να εισαγάγει s.size. Βγάζει νόημα αυτό? Επειδή s.strings, όλα αυτά είναι είναι το όνομα της συστοιχίας. Όλα είναι είναι η πρόσβαση σειρά μέσα struct μας, και έτσι αν θέλουμε να τοποθετήστε n σε αυτό το δείκτη, μπορούμε μόνο να έχει πρόσβαση μέσα σε αγκύλες s.size. Δροσερός. 

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

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

Κοινό: Θα αυτές οι διαφάνειες και όλο αυτό το πράγμα είναι μέχρι σήμερα-ish; ANDI PENG: Πάντα, Ναι. Πάω να προσπαθήσουμε να βάλουμε Αυτό σαν μια ώρα μετά. Θα email Δαβίδ, ο Δαβίδ θα προσπαθήσει να το βάζουμε σαν μια ώρα μετά από αυτό. 

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

Έτσι, αυτό που μας αρέσει να αποκαλούμε αυτό είναι dequeueing και enqueueing. Αν θέλουμε να προσθέσουμε κάτι στην ουρά μας, εμείς Τοποθέτηση στην ουρά. Αν θέλουμε να dequeue, ή να λάβει κάτι μακριά, εμείς dequeue. 

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

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

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

Κοινό: [δεν ακούγεται] ANDI PENG: Ακριβώς, που θέλετε να προσθέσετε ανάλογα με το έχετε γράψει. Είτε αυτό είναι κενό ή ότι είναι κενό. Έτσι θέλετε να προσθέσετε πιθανώς εδώ γιατί αν το μέγεθος is-- αν όλα αυτά είναι πλήρη, θέλετε να προστεθεί εδώ, σωστά; 

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

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

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

Όποιος θέλει να λάβει μια μαχαιριά σε εξηγώντας γιατί έχετε πήρε αυτό το περίπλοκο πράγμα εδώ; Βλέπουμε την επιστροφή μας υπέροχο φίλο μέτρο. Όπως εσείς θα έρθει σύντομα να αναγνωρίσει στον προγραμματισμό, σχεδόν οποιαδήποτε στιγμή χρειάζεστε κάτι να τυλίξει γύρω από κάτι, συντελεστής θα είναι ο τρόπος για να το κάνουμε. Έτσι γνωρίζοντας ότι, δεν θέλει κανείς να προσπαθήσουμε να τα εξηγήσουμε αυτή τη γραμμή του κώδικα; Ναι, όλες οι απαντήσεις είναι αποδεκτή και ευπρόσδεκτη. Κοινό: Μιλάς σε μένα; ANDI PENG: Ναι. Κοινό: Ω, όχι συγγνώμη. ANDI PENG: ΟΚ, οπότε ας με τα πόδια μέσα από αυτό τον κωδικό. Έτσι, όταν προσπαθείτε να προσθέσει κάτι σε μια ουρά, στην όμορφη περίπτωση που η κεφαλή συμβαίνει να είναι ακριβώς εδώ, είναι πολύ εύκολο για μας απλά να πάτε στο τέλος εισάγετε κάτι, σωστά; Αλλά το νόημα του μια ουρά είναι ότι η κεφαλή μπορεί πραγματικά δυναμικά αλλάζουν ανάλογα με το πού θα θέλουν το ξεκίνημα του q μας να είναι, και ως εκ τούτου, την ουρά Επίσης, πρόκειται να αλλάξει. 

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

Τώρα θέλουμε να προσθέσουμε κάτι για να Η ουρά, αλλά όπως μπορείτε να δείτε τα παιδιά, δεν είναι τόσο απλό όσο ακριβώς προσθέστε ό, τι είναι μετά από το μέγεθος γιατί τότε θα ξεμείνει από τα όρια των πραγματικών σειρά μας. Πού θέλουμε πραγματικά να προσθέσω είναι εδώ. Αυτή είναι η ομορφιά του μια ουρά είναι ότι για εμάς, οπτικά Μοιάζει η γραμμή πηγαίνει όπως αυτό, αλλά όταν αποθηκεύονται σε μια δομή δεδομένων, θα το δώσει ως σαν ένα κύκλο. Το είδος των τυλίγεται γύρω από προς τα εμπρός με τον ίδιο τρόπο ότι μια γραμμή μπορεί επίσης να τυλίξετε περίπου ανάλογα με όπου κι αν βρίσκεστε θέλουν να αρχή της γραμμής να είναι. Και έτσι αν πάρουμε ένα κοιτάξτε εδώ κάτω, ας λένε θελήσαμε να δημιουργήσουμε ένα λειτουργία που ονομάζεται Τοποθέτηση στην ουρά. Θέλαμε να προσθέσουμε int n σε εκείνο το q. Αν q.size q-- θα καλέσουμε ότι τα δεδομένα μας structure-- αν queue.size μας δεν το κάνει ισούται με την ικανότητα ή αν είναι μικρότερη από την ικανότητα, q.strings είναι η σειρά μας μέσα στο q. Εμείς πάμε για να ρυθμίσετε ότι ισούται με q.heads, η οποία είναι ακριβώς εδώ, καθώς q.size μέτρο από την ικανότητα, η οποία τυλίξτε μας πίσω εδώ γύρω. 

Έτσι, σε αυτό το παράδειγμα, ο δείκτης της κεφαλής είναι 1, σωστά; Ο δείκτης του μέγεθος είναι 0, 1, 2, 3, 4. Έτσι μπορούμε να κάνουμε 1 συν 4 συντελεστή από την ικανότητά μας, το οποίο είναι 5. Τι πάει να μας δώσει; Τι είναι ο δείκτης που βγαίνει από αυτό; 

Κοινό: 0. 

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

Ξέρω ότι το είδος του εγκεφάλου teaser ειδικά δεδομένου ότι αυτό ήρθε στον απόηχο του κουίζ σας. Αλλά ελπίζουμε όλοι Τώρα μπορείτε να καταλάβετε γιατί αυτή η λύση ή αυτή λειτουργία είναι ο τρόπος που είναι. Όποιος είναι λίγο ασαφές σχετικά με αυτό; ΕΝΤΆΞΕΙ. 

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

Και έτσι όταν dequeue, Μου ψευδοκώδικας επίσης. Μη διστάσετε να αν θέλετε να επιχειρήσει κωδικοποίησης αυτό. Θέλετε να μετακινήσετε το κεφάλι, έτσι δεν είναι; Αν ήθελα να dequeue, Ι θα κινηθεί το κεφάλι πάνω. Αυτό θα είναι το κεφάλι. 

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

Εντάξει, έτσι θα πάμε να μιλήσουμε λίγο περισσότερο σε βάθος περίπου συνδεδεμένες λίστες γιατί θα είναι πολύ, πολύ πολύτιμη για σας κατά τη διάρκεια αυτής της εβδομάδας psets. Συνδεδεμένες λίστες, όπως εσείς μπορεί να θυμηθεί, όλα αυτά είναι είναι κόμβοι που είναι κόμβοι ορισμένων τιμές τόσο της αξίας και ένα δείκτη τα οποία συνδέονται μεταξύ τους οι εν λόγω δείκτες. Και έτσι η struct σχετικά με το πώς δημιουργούμε ένας κόμβος εδώ είναι ότι έχουν int n, η οποία είναι ό, τι η τιμή σε ένα κατάστημα ή σπάγκο n ή όπως αλλιώς θέλετε να αποκαλούν, ο char αστέρι n. Struct αστέρι κόμβος, που είναι ο δείκτης ότι θέλετε να έχετε σε κάθε κόμβο, θα πάμε να έχει αυτό Σημείο δείκτη προς το επόμενο. Θα έχετε το κεφάλι από μία συνδεδεμένη λίστα που είναι πρόκειται να επισημαίνουν το υπόλοιπο της οι τιμές ούτω καθεξής και ούτω καθεξής μέχρι να φθάσουν τελικά στο τέλος. Και αυτό το τελευταίο κόμβος είναι απλά πρόκειται να μην έχουν ένα δείκτη. Είναι πρόκειται να επισημάνω null, και ότι όταν ξέρετε ότι έχετε χτυπήσει το τέλος συνδεδεμένη λίστα σας είναι όταν την τελευταία δείκτη σας δεν δείχνουν τίποτα. 

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

Κοινό: Επειδή είστε όλοι συνδεδεμένοι, αλλά δεν γνωρίζουμε ακριβώς πού [ΜΗ ΑΚΟΥΣΤΌΣ]. 

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

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

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

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

Και στη συνέχεια, μόλις φτάσετε εδώ κάτω, ενώ ο δείκτης δεν είναι ίσο με null, έτσι ώστε ο βρόχος στον οποίο είμαστε θα είναι στη συνέχεια διέρχονται το υπόλοιπο του καταλόγου μας, γιατί ό, τι συμβαίνει όταν ο δείκτης ισούται με μηδενική; Ξέρουμε ότι have-- 

Κοινό: [δεν ακούγεται] 

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

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

Σε αντίθετη περίπτωση, θέλετε να ορίσετε το δείκτη στον επόμενο κόμβο. Αυτό είναι ό, τι η γραμμή εδώ κάνει. Ο δείκτης ισούται με το δείκτη του επόμενου. Όλοι δούμε πώς αυτό λειτουργεί; 

Και ουσιαστικά πρόκειται για απλά διασχίζουν το σύνολο του καταλόγου, επαναφορά του δείκτη σας κάθε φορά μέχρι μπορείτε τελικά να χτυπήσει το τέλος της λίστας. Και ξέρετε ότι δεν υπάρχουν περισσότερους κόμβους να ψάξετε μέσα, και, στη συνέχεια, μπορείτε να επιστρέψετε ψευδής επειδή ξέρετε ότι, OH, καλά, αν ήμουν σε θέση να αναζητήσετε μέσω της σύνολό της λίστας. Αν σε αυτό το παράδειγμα, αν ήθελα να ψάξουν για την αξία του 10, και αρχίζω στο κεφάλι, και Ψάχνω σε όλη τη διαδρομή προς τα κάτω, και εγώ τελικά πήρε σε αυτό, το οποίο ένας δείκτης που δείχνει προς null, Ξέρω ότι, χάλια, υποθέτω 10 δεν είναι σε Αυτή η λίστα γιατί δεν μπορούσα να το βρω. Και είμαι στο τέλος της λίστας. Και σε αυτήν την περίπτωση μπορείτε να ξέρετε Πάω να επιστρέψει false. 

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

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

Κοινό: Είναι δυναμική, έτσι είναι ευκολότερο to-- 

ANDI PENG: Ακριβώς, έτσι ώστε να είναι δυναμική, η οποία σημαίνει ότι μπορεί να επεκτείνει και να συρρικνωθεί ανάλογα με τις ανάγκες του χρήστη. Και έτσι, με αυτή την έννοια, δεν χρειαζόμαστε να σπαταλούν άσκοπα το χώρο αποθήκευσης, γιατί αν δεν ξέρω πόσες τιμές θέλω για την αποθήκευση, δεν έχει νόημα για μένα για να δημιουργήσει μια σειρά, γιατί αν θέλω να αποθηκεύσει 10 τιμές και μπορώ να δημιουργήσω μια σειρά από 1.000, που είναι μια μεγάλη σπατάλη μνήμης, που έχουν εγκριθεί. Γι 'αυτό θέλουμε να χρησιμοποιήσουμε ένα συνδεδεμένο κατάλογος να είναι σε θέση να δυναμικά αλλάξετε ή να συρρικνωθεί το μέγεθος μας. 

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

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

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

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

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

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

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

Και μετά θα πάμε για να ελέγξετε για να δείτε αν νέο ίσων ισούται με μηδενική. Θυμηθείτε τι είπαμε; Ό, τι malloc, τι πρέπει να κάνετε πάντα; Θα πρέπει πάντοτε να ελέγχετε έστω και αν αυτή είναι άκυρη. 

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

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

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

Γι 'αυτό είναι μια διαδικασία δύο σταδίων. Έχετε να εκχωρήσει πρώτα ό, τι δημιουργείτε. Ορίστε αυτό το δείκτη για το αναφοράς, και στη συνέχεια θα να το είδος της dereference ο πρώτος δείκτης και κατευθύνεται προς το νέο κόμβο. Όπου κι αν θέλετε να το τοποθετήσετε, ότι η λογική θα ισχύει. 

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

Εντάξει, έτσι κωδικός θα είναι εδώ. Εσείς ρίξτε μια ματιά μετά το τμήμα. Θα είναι εκεί. 

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

Κοινό: Θα ήταν ακόμα είναι μια παρόμοια διαδικασία σαν την ανάθεση δείκτη και Στη συνέχεια την ανάθεση αυτού του pointer, αλλά θα πρέπει να εντοπίσετε εκεί. 

ANDI PENG: Ακριβώς, έτσι ακριβώς η ίδια διαδικασία, εκτός από εσάς πρέπει να εντοπίσετε πού ακριβώς σας θέλουν το νέο δείκτη για να πάει σε, οπότε αν θέλετε να εισάγετε στο η μέση συνδέονται list-- ΟΚ, Ας πούμε ότι είναι συνδεδεμένη λίστα μας. Αν θέλουμε να το τοποθετήσετε ακριβώς εδώ, θα πάμε για να δημιουργήσετε ένα νέο κόμβο. Εμείς πάμε για να malloc. Εμείς πάμε για να δημιουργήσετε ένα νέο κόμβο. Εμείς πάμε για να ορίσετε το δείκτη του κόμβου εδώ. 

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

Τι θα λέγατε για εισαγωγή στο τέλος; Αν ήθελα να το προσθέσετε here-- αν ήθελα να προσθέσετε ένα νέο κόμβο στο τέλος του καταλόγου, Πως θα πάτε για να κάνει αυτό; Κοινό: Έτσι σήμερα, η επισήμανε τελευταίο να null. ANDI PENG: Ναι. Ακριβώς, οπότε αυτό σήμερα είναι στραμμένο προς γνωρίζετε, και έτσι υποθέτω, με αυτή την έννοια, είναι πολύ εύκολο να προσθέσετε στο τέλος της λίστας. Το μόνο που έχετε να κάνετε είναι να το ρυθμίσετε ίσο με null και, στη συνέχεια, με γρήγορους ρυθμούς. Ακριβώς εκεί, είναι πολύ εύκολο. Πολυ απλα. 

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

Χαλαρώστε, ηρέμησε, πάρτε μια βαθιά ανάσα. Ισοπαλία έξω συνδεδεμένη λίστα σας. Εάν λέτε, ξέρω πού ακριβώς Πρέπει να εισάγετε αυτό σε και ξέρω ακριβώς πώς να επανεκχώρηση μου δείκτες, πολύ, πολύ πιο εύκολο να φανταστείτε out-- πολύ, πολύ εύκολο να μην χαθείτε στα σφάλματα του κώδικα σας. Όλοι εντάξει με αυτό; ΕΝΤΆΞΕΙ. 

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

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

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

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

Εντάξει, έτσι τώρα είμαι πραγματικά να περάσετε πιθανώς σαν 15 να 20 λεπτά ή το μεγαλύτερο μέρος του υπόλοιπου χρόνου σε τμήμα μιλάμε για πίνακες κατακερματισμού. Πόσοι από σας παιδιά έχουν διαβάσει pset5 spec; Εντάξει, καλά. Αυτό είναι υψηλότερο από το 50% των κανονικά. Είναι εντάξει. 

Έτσι όπως εσείς θα δείτε, είστε πρόκληση pset5 θα είναι να εφαρμόσει ένα λεξικό όπου μπορείτε να φορτώσετε πάνω από 140.000 λέξεις ότι θα σας δώσει και ο ορθογραφικός έλεγχος ενάντια σε όλο το κείμενο. Θα σας δώσουμε τυχαία κομμάτια της λογοτεχνίας. Θα σας δώσει την Οδύσσεια. Θα σας δώσει την Ιλιάδα. Θα σας δώσω Austin Powers. 

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

Έτσι υποθέτω ότι ο ευκολότερος τρόπος για να το κάνετε αυτό, θα δημιουργήσει πιθανώς μια σειρά, έτσι δεν είναι; Ο ευκολότερος τρόπος αποθήκευσης είναι εσείς μπορεί να δημιουργήσει μια σειρά από 140,000 λέξεις και απλά τοποθετήστε τους όλους εκεί και στη συνέχεια να τα διασχίζουν με δυαδική αναζήτηση ή από τις επιλογές ή not-- λυπηρό το γεγονός ότι διαλογής. Μπορείτε να τα ταξινομήσετε και στη συνέχεια να διασχίσει τους μέσω της δυαδικής αναζήτησης ή απλά γραμμική αναζήτηση και μόνο τελικό οι λέξεις, αλλά ότι παίρνει ένα τεράστιο ποσό της μνήμης, και δεν είναι πολύ αποτελεσματική. 

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

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

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

Έτσι, δεν ξέρω, είμαστε ένα πρόγραμμα χρήστη, όπου θα χρεωθείτε με Δεν arbitrarily-- αυθαίρετα, με την προσπάθεια να σκεπτικά σκεφτείτε καλά εξισώσεων να είναι σε θέση να εξαπλωθεί από το σύνολο των αξιών σας κατά τρόπο που να μπορούν εύκολα να έχουν πρόσβαση αυτό αργότερα με σαν μια εξίσωση ότι εσείς οι ίδιοι, ξέρετε. Έτσι, με την έννοια αν ήθελα να πάω να μάνγκο, το ξέρω, OH, ξεκινά με το m. Πρέπει να είναι στο δείκτη 12. Δεν χρειάζεται να ψάξει μέσω τίποτα. Ξέρω exactly-- θα μπορούσα απλά πηγαίνετε στο ο δείκτης των 12 και τραβήξτε ότι έξω. 

Όλοι σαφής σχετικά με το πώς μια συνάρτηση hash πίνακα δουλεύει; Είναι το είδος του απλά μια πιο περίπλοκη σειρά. Αυτό είναι όλο αυτό είναι. ΕΝΤΆΞΕΙ. 

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

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

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

Και έτσι εδώ, αν μου ήθελε να εισαγάγετε μούρο, Το ξέρω, εντάξει, θα πάω στην είσοδο μέσω της λειτουργίας κατακερματισμού μου. Πάω να καταλήξετε με το δείκτη 1, και στη συνέχεια, Πάω να είναι σε θέση να έχουν μόνο ένα μικρότερο υποσύνολο αυτό γίγαντας 140.000 λέξη λεξικό. Και τότε μπορώ να εξετάσουμε μόνο μέσω 1/26 από αυτό. 

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

Έτσι hash λειτουργία είναι αυτή η εξίσωση ότι τρέχετε το είδος της εισόδου σας μέσα για να πάρει ό, τι του δείκτη Θέλετε να αναθέσει προς την κατεύθυνση. Και έτσι, σε αυτό το παράδειγμα, όλοι θέλαμε να κάνει ήταν να πάρει το πρώτο γράμμα, τη σειρά του ότι σε ένα δείκτη, τότε μπορεί να αποθηκεύσει ότι σε συνάρτηση κατακερματισμού μας. Όλα που κάνουμε εδώ είναι ότι είμαστε μετατρέποντας το πρώτο γράμμα. Έτσι keykey [0] είναι μόνο το πρώτο γράμμα από ό, τι εγχόρδων είμαστε έχοντας, είμαστε περνώντας. Είμαστε το μετατρέπει σε κεφαλαία, και είμαστε αφαιρώντας από κεφαλαίο A, οπότε το μόνο που κάνει μας δίνει έναν αριθμό στο οποίο μπορούμε να κατακερματίσει τις αξίες μας πάνω. 

Και μετά θα πάμε να επιστρέψετε hash μέτρο ΜΕΓΕΘΟΣ. Να είστε πολύ, πολύ προσεκτικοί διότι, θεωρητικά, εδώ hash αξία σας θα μπορούσε να είναι άπειρη. Θα μπορούσε απλά να συνεχίσω και επάνω και επάνω. Θα μπορούσε να είναι κάποια πραγματικά, πραγματικά μεγάλη αξία, αλλά επειδή πίνακα κατακερματισμού σας που έχετε δημιουργήσει έχει μόνο 26 δείκτες, θέλετε να βεβαιωθείτε ότι σας modulusing έτσι ώστε να Δεν run-- είναι το ίδιο πράγμα όπως queue-- σας έτσι ώστε να μην τρέξει το κάτω μέρος της συνάρτησης κατακερματισμού σας. 

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

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

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

Αν ήθελα να insert-- τι είναι ένα φρούτα που ξεκινά με, δεν ξέρω, Β, εκτός από μούρο, μπανάνα. 

Κοινό: Blackberry. 

ANDI PENG: Blackberry, βατόμουρο. Πού βατόμουρο πάει εδώ; Λοιπόν, στην πραγματικότητα δεν έχουν ταξινομηθεί αυτό ακόμα, αλλά θεωρητικά αν θέλαμε να έχουμε αυτό με αλφαβητική σειρά, όπου θα πρέπει BlackBerry πάει; 

Κοινό: [δεν ακούγεται] 

ANDI PENG: Ακριβώς, αφού εδώ, σωστά; Αλλά δεδομένου ότι είναι πολύ δύσκολο να reorder-- Υποθέτω ότι είναι στο χέρι σας παιδιά. Εσείς μπορείτε εντελώς να εφαρμόσουν ό, τι θέλετε. Ο πιο αποτελεσματικός τρόπος για να γίνει αυτό ίσως θα ήταν να ταξινομήσετε τα συνδεδεμένα σας λίστα σε αλφαβητική σειρά, και έτσι όταν είστε εισάγοντας τα πράγματα, θέλετε να είναι σίγουρος για την εισαγωγή τους σε αλφαβητική σειρά έτσι ώστε στη συνέχεια, όταν είστε προσπαθούν να τα αναζητήσετε, δεν χρειάζεται να διασχίσει τα πάντα. Ξέρετε πού ακριβώς είναι, και είναι ευκολότερο. 

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

Κοινό: Εάν προσπαθείτε να create-- Υποθέτω ότι όπως αυτό είναι ένα πολύ απλό κατακερματισμού λειτουργία. Και αν θέλαμε να κάνουμε πολλαπλά στρώματα της εν λόγω παρόμοια, Εντάξει, θέλουμε να διαχωριστούν σε όπως και όλα τα γράμματα του αλφαβήτου και στη συνέχεια και πάλι να αρέσει ένα άλλο σύνολο από γράμματα του αλφαβήτου μέσα σε αυτό, είμαστε βάζοντας σαν ένα hash πίνακα μέσα σε έναν πίνακα κατακερματισμού, ή σαν μια συνάρτηση μέσα σε μια συνάρτηση; Ή είναι that-- 

ANDI PENG: Έτσι κατακερματισμού σας function-- πίνακα κατακερματισμού σας μπορεί να είναι τόσο μεγάλη όσο θέλετε να. Έτσι, με αυτή την έννοια, σκέφτηκα ήταν πολύ εύκολη, πολύ απλό για μένα να βασίζεται ακριβώς το είδος σχετικά με τις επιστολές της πρώτης λέξης. Και έτσι υπάρχει μόνο 26 επιλογές. Μπορώ να πάρω μόνο 26 από τις επιλογές 0-25 επειδή μπορούν μόνο ξεκινήστε από το Α ως το Ω, αλλά αν ήθελες για να προσθέσετε, ίσως, μεγαλύτερη πολυπλοκότητα ή να τρέξει πιο γρήγορα η ώρα να σας hash πίνακα, θα πρέπει οπωσδήποτε μπορεί να κάνει όλα τα είδη των πραγμάτων. Μπορείτε να φτιάξετε το δικό σας εξίσωση που σας δίνει πιο διανομή σε σας Δηλαδή, στη συνέχεια, όταν κάνετε αναζήτηση, πρόκειται να είναι ταχύτερη. 

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

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

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

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

Δροσερός. Εντάξει, τώρα έχουμε ένα διαφορετικό είδος δομή δεδομένων που ονομάζεται ένα δέντρο. Ας προχωρήσουμε και να μιλήσουμε για προσπαθεί τα οποία είναι σαφώς διαφορετική, αλλά στην ίδια κατηγορία. Ουσιαστικά, όλα είναι ένα δέντρο αντί της οργάνωσης των δεδομένων στο γραμμικό τρόπο ότι ένας πίνακας κατακερματισμού που does-- Ξέρεις, είναι πήρε μια κορυφή και πυθμένα και τότε το είδος του συνδέσμου εκτός από ένα it-- δέντρο έχει μια κορυφή, το οποίο μπορείτε να καλέσετε τη ρίζα, και στη συνέχεια να έχει φύλλα όλα γύρω από αυτό. 

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

Πίνακας κατακερματισμού μοιάζει με ένα τραπέζι. Ένα δέντρο μοιάζει ακριβώς όπως ένα δέντρο. Όλα είναι είναι ένα ξεχωριστό τρόπος οργάνωσης των κόμβων ανάλογα με το ποιες είναι οι ανάγκες σας. 

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

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

Έτσι, εδώ, αν Πάω να αναζητήσετε η αξία των 66, θα μπορεί να αρχίσει σε 55. Είναι μεγαλύτερη από 66 55; Ναι είναι, έτσι ξέρω mus αναζήτηση i n το δικαίωμα δείκτη του δέντρου. Έχω πάει σε 77. Εντάξει, είναι μικρότερη από 66 ή μεγαλύτερο από 77; Είναι λιγότερο από ό, τι, έτσι ξέρετε, OH, ότι πρέπει να είναι η αριστερά κόμβο. 

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

Cool δομή δεδομένων, το είδος του περίπλοκο να εφαρμοστεί, τον κόμβο. Όπως μπορείτε να δείτε, όλα είναι είναι η struct του κόμβου είναι ότι έχετε μια αριστερά και το δικαίωμα δείκτη. Αυτό είναι όλο αυτό είναι. Έτσι, όχι μόνο που έχει μια X ή προηγούμενο. Έχετε μια αριστερή ή δεξιά, και στη συνέχεια, μπορείτε να το είδος της διασύνδεσης τους Ωστόσο, μπορείτε να το επιλέξετε. 

Εντάξει, είμαστε στην πραγματικότητα θα μόλις πάρει μερικά λεπτά. Έτσι θα πάμε να επιστρέψουμε εδώ. Όπως είπα και προηγουμένως, Ι το είδος του εξήγησε η λογική πίσω από το πώς εμείς θα αναζητήσετε μέσα από αυτό. Εμείς πάμε για να προσπαθήσουμε pseudocoding αυτό για να δείτε αν μπορούμε να το είδος του να εφαρμοστεί η ίδια λογική της δυαδικής αναζήτησης σε ένα διαφορετικό είδος δομής δεδομένων. Αν εσείς θέλετε να πάρετε σαν ένα ζευγάρι λεπτά για να σκεφτείτε ακριβώς για αυτό. ΕΝΤΆΞΕΙ. Εντάξει, Πάω να στην πραγματικότητα μόνο να σας δώσει the-- όχι, θα μιλήσουμε για την πρώτη ψευδοκώδικα. Έτσι δεν θέλει κανείς για να δώσει ένα πλήγμα σε ό, τι το πρώτο πράγμα που θέλετε να κάνετε όταν είστε ξεκινάμε αναζήτηση είναι; Αν ψάχνετε η αξία των 66, τι είναι Το πρώτο πράγμα που θέλουμε να κάνουμε, αν θέλουμε να δυαδική αναζήτηση αυτό το δέντρο; 

Κοινό: Θέλετε να δείτε σωστά και κοιτάξτε αριστερά και δείτε [δεν ακούγεται] μεγαλύτερο αριθμό. 

ANDI PENG: Ναι, ακριβώς. Έτσι θα πάμε να δούμε στη ρίζα σας. Υπάρχουν πολλοί τρόποι που μπορείτε να καλέσετε αυτό, οι άνθρωποι κόμβο γονέα σας πω. Θα ήθελα να πω, επειδή ρίζα αυτό είναι σαν την ρίζα του δέντρου. Θα πάμε να δούμε κόμβο-ρίζα σας, και να είστε πρόκειται να δούμε είναι μεγαλύτερη 66 ή μικρότερο από 55. Και αν αυτό είναι μεγαλύτερο από ό, τι, καλά, αυτό είναι μεγαλύτερη από ό, τι, πού θέλουμε να δούμε; Πού θέλουμε να αναζητήσετε τώρα, έτσι δεν είναι; Θέλουμε να αναζητήσετε το δεξιό μισό αυτού του δέντρου. 

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

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

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

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

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

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

Όλα είναι μια trie είναι συγκεκριμένο είδος δέντρου που έχει τιμές που πηγαίνουν σε άλλες αξίες. Έτσι, αντί να έχουν ένα δυαδικό δέντρο με την έννοια ότι μόνο ένα πράγμα που μπορεί να δείξει σε δύο, μπορείτε να έχετε σημείο ένα πράγμα σε πολλά, πολλά πράγματα. Έχετε ουσιαστικά συστοιχίες μέσα από τα οποία μπορείτε να αποθηκεύσετε δείκτες που παραπέμπουν σε άλλες σειρές. 

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

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

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

Και here-- OH, το επόμενο e-mail στο [δεν ακούγεται] είναι Α Έτσι θα δούμε σε αυτό το φάσμα. Θα βρείτε την όγδοη αξία, και στη συνέχεια να κοιτάξουμε να δούμε, OH, hey, είναι ότι μια λέξη, είναι Β-Α μια λέξη; Είναι μια λέξη που δεν είναι. Έχουμε να συνεχίσετε να ψάχνετε. 

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

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

ΟΚ κομπλε. Έτσι Β-Α-Τ, και στη συνέχεια θα πάμε να αναζητήσετε. Την επόμενη φορά που θα πάμε για να δείτε, ω, hey, είναι αλήθεια, έτσι Ξέρω ότι αυτό πρέπει να είναι μια λέξη. 

Ίδιο πράγμα για ζωολογικό κήπο. Έτσι, εδώ είναι το πράγμα τώρα, αν θέλουμε ήθελε να ψάξετε ζωολογικό κήπο, αυτή τη στιγμή, σήμερα ζωολογικός κήπος δεν είναι μια λέξη στο λεξικό μας επειδή, όπως εσείς να δείτε, η πρώτον, ότι έχουμε μια Boolean return true βρίσκεται στο τέλος του ζουμ. Έχουμε Ζ-O-O-M. 

Και έτσι και εδώ, δεν έχουμε στην πραγματικότητα η λέξη, ζωολογικό κήπο, στο λεξικό μας επειδή αυτό το πλαίσιο ελέγχου δεν είναι επιλεγμένο. Έτσι, ο υπολογιστής δεν Γνωρίζουμε ότι ζωολογικός κήπος είναι μια λέξη επειδή ο τρόπος που έχουμε αποθηκεύονται αυτό, μόνο ένα ζουμ εδώ στην πραγματικότητα έχει μια τιμή Boolean που είναι ήδη μετατραπεί αλήθεια. Έτσι, αν θέλουμε να εισαχθεί η λέξη, ζωολογικό κήπο, στο λεξικό μας, πώς θα πάει για να κάνει αυτό; Τι πρέπει να κάνουμε για να βεβαιωθείτε ότι μας υπολογιστή γνωρίζει ότι η Ζ-Ο-Ο είναι μια λέξη και δεν είναι η πρώτη λέξη είναι Ζ-O-O-M; 

Κοινό: [δεν ακούγεται] 

ANDI PENG: Ακριβώς, έχουμε θέλετε να βεβαιωθείτε ότι αυτό το εδώ, ότι η τιμή είναι Boolean ελέγχεται καλά ότι αυτό είναι αλήθεια. Ζ-Ο-Ο, τότε θα πάμε για να ελέγξει ότι, έτσι ώστε να γνωρίζουμε ακριβώς, hey, ζωολογικός κήπος είναι μια λέξη. Πάω να πω το υπολογιστή που είναι μια λέξη έτσι ότι όταν οι έλεγχοι του υπολογιστή, γνωρίζει ότι ζωολογικός κήπος είναι μια λέξη. 

Επειδή θυμάμαι όλα αυτά τα δεδομένα δομές, είναι πολύ εύκολο για μας να πει, OH, νυχτερίδα είναι μια λέξη. Ο ζωολογικός κήπος είναι μια λέξη. Ζουμ είναι μια λέξη. Αλλά όταν το κτίριο, ο υπολογιστής δεν έχει ιδέα. 

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

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

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

Εμείς πάμε για να ορίσετε το Η, Πρώτα απ 'όλα, αυτό το null, θα πάμε για να απαλλαγούμε από. Εμείς πάμε για να έχουν οι προς τα κάτω το σημείο Η. Αν δείτε ένα H, το θέλουμε για να πάει κάπου αλλού. 

Εδώ, μπορούμε στη συνέχεια να ελέγξετε μακριά ναι. Αν χτυπήσει ένα H μετά την T, ω, τότε ξέρουμε ότι αυτό είναι μια λέξη. Η Boolean πρόκειται να επιστρέψει αλήθεια. Όλοι σαφής σχετικά με το πώς συνέβη αυτό; ΕΝΤΆΞΕΙ. 

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

Και έτσι pset4, της 5-- Ω, αυτό είναι λάθος. Pset5 είναι ορθογραφικά λάθη. Όπως είπα και πριν, θα πάμε να, μια φορά και πάλι, να κατεβάσετε τον πηγαίο κώδικα από εμάς. Εκεί πρόκειται να είναι τρία κύρια πράγματα που θα πρέπει να κατεβάσετε. Θα κατεβάσετε λεξικά, KERS, και τα κείμενα. 

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

Και έτσι οι τρεις συστάδες προγράμματα που θα σας δώσουμε καλούνται dictionary.c, dictionary.h, και speller.c. Και έτσι όλα dictionary.c κάνει είναι να τι θα σας ζητηθεί να εφαρμόσουν. Φορτώνει λέξεις. Θα σημάνει ελέγχους αυτούς, και να σιγουρεύεται ότι όλα είναι σωστά τοποθετημένη. 

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

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

Και το μεγαλύτερο μέρος αυτής της πρόκλησης είναι για εσείς να τροποποιήσετε πραγματικά dictionary.c. Εμείς πάμε για να σας δώσω 140.000 λέξεις σε ένα λεξικό. Εμείς πάμε για να σας δώσω ένα κείμενο αρχείο που έχει αυτά τα λόγια, και θέλουμε να είστε σε θέση να οργανώσει τους σε ένα πίνακα κατακερματισμού ή trie γιατί όταν σας ζητάμε να σημάνει check-- φανταστείτε εάν είστε ξόρκι τον έλεγχο, όπως Οδύσσεια του Ομήρου. Είναι σαν αυτό το τεράστιο, τεράστια δοκιμασία. 

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

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

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

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

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

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

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

Κοινό: μας επιτρέπεται να αν ήθελε να ερευνήσει ταχύτερους τρόπους να κάνει πίνακες κατακερματισμού σε απευθείας σύνδεση, μπορούμε να κάνουμε ότι και αναφέρουν κώδικα κάποιου άλλου; ANDI PENG: Ναι, μια χαρά. Έτσι, αν εσείς διαβάζετε το spec, υπάρχει μια γραμμή στο spec που λέει σας παιδιά είναι εντελώς δωρεάν για την έρευνα hash λειτουργίες για το τι είναι μερικά από τους πιο γρήγορους συναρτήσεις κατακερματισμού να τρέξει τα πράγματα από μέσα, όπως Εφ 'όσον αναφέρω εν λόγω κώδικα. Έτσι, μερικοί άνθρωποι έχουν ήδη κατάλαβα γρήγορα τρόπους για να γίνει ξόρκι πούλια, του γρήγορου τρόποι αποθήκευση πληροφοριών. Συνολικά μέχρι σας παιδιά, αν θέλουν να πάρουν ακριβώς αυτό, έτσι δεν είναι; Βεβαιωθείτε ότι είστε επικαλούμενη. Η πρόκληση εδώ πραγματικά ότι προσπαθούμε να δοκιμάσει είναι να διασφαλίσουμε ότι γνωρίζετε το δρόμο σας γύρω από δείκτες. Όσον αφορά την εφαρμογή σας η πραγματική συνάρτηση κατακερματισμού και έρχονται με παρόμοια τα μαθηματικά για να το κάνουμε αυτό, εσείς μπορείτε να ερευνήσετε ανεξαρτήτως μεθόδους σε απευθείας σύνδεση εσείς θέλετε. Ναι; 

Κοινό: Μπορούμε να αναφέρω μόνο με τη χρήση του [δεν ακούγεται]; 

ANDI PENG: Ναι. Μπορείτε απλά, στο σχόλιό σας, μπορείτε να αναφέρω, όπως, OH, που λαμβάνονται από μπλα, μπλα, μπλα, συνάρτηση κατακερματισμού. Όποιος έχει οποιαδήποτε απορία; Είμαστε πραγματικά breezed μέσα από το τμήμα σήμερα. Θα είμαι εδώ για να απαντήσει σε ερωτήσεις, καθώς και. 

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

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

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

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

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