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

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

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ 1: Τι είναι αυτό; 

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ 1: Σταθερό μέγεθος. Εντάξει, τόσο γιατί είναι σταθερό μέγεθος καλό όμως; 

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

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

Τι άλλο πάνω μέρος του μια σειρά; Ναι; 

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ 1: Όλα τα - Ορίστε; 

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ 1: Όλα τα κουτιά στη μνήμη ή ένα δίπλα στο άλλο. Και αυτό είναι χρήσιμο - γιατί; Αυτό είναι αλήθεια. Αλλά πώς μπορούμε να εκμεταλλευτεί την αλήθεια; 

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ 1: Ακριβώς, μπορούμε να παρακολουθείτε όπου τα πάντα είναι μόνο με τη γνώση μία διεύθυνση, δηλαδή η διεύθυνση της πρώτο byte του εν λόγω κομμάτι της μνήμης. Ή στην περίπτωση των χορδών, η διεύθυνση του πρώτου char σε αυτό το string. Και από εκεί, μπορούμε να βρούμε το τέλος του string. Μπορούμε να βρούμε το δεύτερο στοιχείο, το τρίτο στοιχείο, και ούτω καθεξής. 

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

Αλλά έχει υπάρξει κάποια μειονεκτήματα. Αυτό δεν είναι μια σειρά κάνει πολύ εύκολα; Τι είναι αυτό δεν είναι καλοί; 

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ 1: Τι είναι αυτό; 

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

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

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

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

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ 1: Μια μεταβλητή και ένα δείκτη, ή Πιο συγκεκριμένα, ένας int, για Ν, και ένα δείκτη στο κάτω μέρος. Και οι δύο από αυτούς τυχαίνει να είναι 32 bits, σε τουλάχιστον σε έναν υπολογιστή, όπως αυτό CS50 Appliance, και έτσι είναι που εξίσου σε μέγεθος. 

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

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

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

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

Έτσι, το μειονέκτημα, τότε, μια συνδεδεμένη λίστα είναι αυτό; Τι είναι ένα τίμημα που είμαστε προφανώς πληρώνει; 

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

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

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

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

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

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

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

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

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

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

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

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

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

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ 1: Ναι, έτσι είναι ένα τοπικό αρχείο. Έτσι, αν είναι ένα τοπικό αρχείο της δικής σας εδώ στη γραμμή 15, για παράδειγμα, μπορείτε να χρησιμοποιήσετε τα διπλά εισαγωγικά, αντί των γωνιακών παρενθέσεων. 

Τώρα αυτό είναι το είδος της ενδιαφέρον. Παρατηρήστε ότι έχω δηλώσει μια παγκόσμια μεταβλητή σε αυτό το πρόγραμμα on line 18 καλείται αρχικά, η ιδέα είναι αυτό είναι πρόκειται να είναι ένας δείκτης για την πρώτη κόμβο σε συνδεδεμένη λίστα μου, και έχω προετοιμαστεί να null, επειδή έχω δεν έχει χορηγηθεί καμία πραγματική κόμβους ακριβώς ακόμα. 

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

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

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

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

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

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

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

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

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

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

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

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

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

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ 1: Ακριβώς, ήταν αστέρι, και τότε ήταν αστέρι dot n, με παρένθεση εδώ, το οποίο μοιάζει, ειλικρινά, νομίζω ότι πολλά πιο αινιγματικά για να διαβάσετε. Αλλά δείκτη αστέρων, όπως πάντα, μέσα εκεί. Και μόλις είστε εκεί, ποια δεδομένα τομέα θέλετε να αποκτήσετε πρόσβαση; Καλά θα χρησιμοποιήσω την τελεία συμβολισμό για να αποκτήσετε πρόσβαση α structs πεδίο δεδομένων, και Συγκεκριμένα θέλουν n. 

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

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

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

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

Γι 'αυτό και δεν θα σταθώ στην άλλη υλοποιήσεις εισαγωγή και διαγραφή και διάσχισης, οι δύο πρώτοι από τα οποία είναι αρκετά εμπλέκονται. Και νομίζω ότι είναι αρκετά εύκολο να πάρει χάνεται όταν το κάνουν προφορικά. Αλλά τι μπορούμε να κάνουμε εδώ είναι προσπαθούν να καθορίσουν τον τρόπο καλύτερα να το κάνετε αυτό οπτικά. Επειδή θα ήθελα να προτείνω ότι, αν θέλετε να εισαγάγετε τα στοιχεία σε αυτό υπάρχουσα λίστα, η οποία έχει πέντε στοιχεία - 9, 17, 22, 26, και 33 - αν επρόκειτο να εφαρμόσει αυτό κώδικα, θα πρέπει να εξετάσει πώς να πάει για να γίνει αυτό. 

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

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

Ας κόβω από ίσως ένα τόσο εύκολο ή ακόμα και ευκολότερη υπόθεση, μιλώντας σχετικά. Ας υποθέσουμε ότι θέλετε να εισαγάγετε το τον αριθμό 35 σε ταξινομημένη σειρά. Ανήκει προφανώς εκεί. Λοιπόν, τι δείκτη είναι προφανώς πρόκειται να πρέπει να ενημερώνεται σε αυτό το σενάριο; Δείκτη 34 είναι να γίνει δεν είναι null αλλά η διεύθυνση του struct περιέχει τον αριθμό 35. Έτσι, αυτό είναι υπόθεση δύο. Έτσι, ήδη, είμαι το είδος του quantizing πόση δουλειά έχω να κάνω εδώ. 

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

Αλλά τότε θα πρέπει, επίσης, ότι το νέο κόμβο, 23 στην περίπτωση αυτή, για να έχει δείκτη του δείχνει σε ποιον; 26. Και εκεί πρόκειται να είναι μια σειρά των πράξεων εδώ. Διότι, αν το κάνω αυτό ανόητα, και εγώ για την έναρξη παράδειγμα κατά την έναρξη της ο κατάλογος, και ο στόχος μου είναι να τοποθετήσετε 23. Και μπορώ να ελέγξω, αυτό ανήκει εδώ, κοντά εννιά; Όχι. Μήπως ανήκει εδώ, δίπλα στο 17; Όχι. Μήπως ανήκει εδώ δίπλα στο 22; Ναι. 

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

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

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

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

Εντάξει, αφού είσαι εδώ πρώτα, θα θέλατε να είναι η μία αδέξια σε γυαλί Google εδώ; Εντάξει, ναι, εντάξει, γυαλί, εγγραφή βίντεο. Εντάξει, είστε καλοί να πάτε. 

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

ΣΠΟΥΔΑΣΤΩΝ: Ben. 

ΟΜΙΛΗΤΗΣ 1: Μπεν; Εντάξει, Μπεν, θα είναι η πρώτη, κυριολεκτικά. Έτσι θα πάμε για να σας στείλουμε στο τέλος του σταδίου. Εντάξει, και το όνομά σας; 

ΣΠΟΥΔΑΣΤΩΝ: Jason. 

ΟΜΙΛΗΤΗΣ 1: Jason, εντάξει θα είστε είναι ο αριθμός εννέα. Έτσι, εάν θέλετε να ακολουθήσετε Ben με αυτόν τον τρόπο. 

ΣΠΟΥΔΑΣΤΩΝ: Jill. 

ΟΜΙΛΗΤΗΣ 1: Jill, θα πάμε να 17, το οποίο, αν είχα κάνει αυτό περισσότερο έξυπνα, θα είχα ξεκίνησε στο άλλο άκρο. Μπορείτε να πάτε με αυτόν τον τρόπο. 22. Και εσύ είσαι; 

ΣΠΟΥΔΑΣΤΩΝ: Mary. 

ΟΜΙΛΗΤΗΣ 1: Mary, θα είναι 22. Και το όνομά σου είναι; 

ΣΠΟΥΔΑΣΤΩΝ: Chris. 

ΟΜΙΛΗΤΗΣ 1: Chris, θα είναι 26. Και μετά τέλος. 

ΣΠΟΥΔΑΣΤΩΝ: Diana. 

ΟΜΙΛΗΤΗΣ 1: Diana, θα είναι 34. Έτσι θα έρθει για πάνω από εδώ. 

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

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

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

ΣΠΟΥΔΑΣΤΩΝ: Brian. 

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

ΕΝΤΑΞΕΙ, έτσι τώρα θέλουμε να εισάγετε Brian και πέντε. Έτσι, έλα εδώ δίπλα Ben μόνο για μια στιγμή. Και μπορείτε να πείτε προφανώς όπου αυτή η ιστορία πηγαίνει. Αλλά ας σκεφτούμε προσεκτικά σχετικά με η σειρά των πράξεων. Και είναι ακριβώς αυτή η οπτική που πρόκειται να παρατάξει με αυτό το δείγμα κώδικα. Έτσι, εδώ έχω PTR επισημαίνοντας αρχικά όχι σε Ben, per se, αλλά σε ό, τι εκτιμούν ότι περιέχει, η οποία σε αυτή την περίπτωση είναι - τι είναι το όνομά σας και πάλι; 

ΣΠΟΥΔΑΣΤΩΝ: Jason. 

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

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

Εντάξει, έτσι ώστε να έχουν λίγα υποψηφίων. Είτε Ben ή εγώ ή και Brian ή Jason ή όλοι οι άλλοι, που δείκτες πρέπει να αλλάξουν; Πόσοι συνολικά; 

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

Ποιος παίρνει επισήμανε σε ποιον; 

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ 1: Εντάξει έτσι Brian έχει στο σημείο στο Jason. Αλλά έχω χάσει τα ίχνη του εν λόγω δείκτη; Ξέρω όπου ο Ιάσονας είναι; 

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

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

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

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

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

ΣΠΟΥΔΑΣΤΩΝ: Diana. 

ΟΜΙΛΗΤΗΣ 1: Diana δείχνει, βέβαια, σε null με το αριστερό χέρι. Έτσι, όταν κάνει Habata πραγματικότητα ανήκουν καθαρά; Προς τα αριστερά, εδώ. Λοιπόν, πώς μπορώ να ξέρω να την βάλει εδώ Νομίζω ότι έχω μαντάρα. Γιατί αυτό είναι PTR τέχνης αυτή τη στιγμή; Null. Έτσι, ακόμη και αν, οπτικά, μπορούμε Προφανώς δείτε όλα αυτά παιδιά εδώ στη σκηνή. Δεν έχω παρακολουθημένη του προηγούμενου πρόσωπο στη λίστα. Δεν έχω ένα δάχτυλο επισημαίνοντας, σε αυτή την περίπτωση, ο κόμβος αριθμό 34. 

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

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

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

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

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

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

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

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

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

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ 1: Συγνώμη; 

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ 1: Demeron; OK Ανέβα. Θα πρέπει να είναι 20. Μπορείτε προφανώς πρόκειται να ανήκουν μεταξύ 17 και 22. Έτσι, επιτρέψτε μου να μάθουν το μάθημά μου. Πάω να ξεκινήσει δείκτη δείχνοντας Brian. Και Πάω να έχουν το αριστερό μου χέρι μόνο ενημέρωση για Brian όπως προχωρήσουμε σε Jason, ο έλεγχος έχει 20 λιγότερα από εννέα; Όχι. 20 είναι λιγότερο από 17; Όχι. Είναι 20 λιγότερο από το 22; Ναι. Έτσι δείκτες ή τα χέρια ό, τι πρέπει να αλλάξει εκεί που δείχνει τώρα; 

Έτσι, μπορούμε να κάνουμε 17 δείχνοντας σε 20. Έτσι, αυτό είναι εντάξει. Πού θέλουμε να επισημάνουμε δείκτη σας τώρα; Σε 22. Και ξέρουμε όπου το 22 είναι, και πάλι ευχαριστώ την προσωρινή δείκτη μου. Έτσι, είμαστε εντάξει εκεί. Έτσι, λόγω αυτής της προσωρινής αποθήκευσης Έχω κρατήσει παρακολουθείτε όπου ο καθένας είναι. Και τώρα μπορείτε να πάτε σε οπτικά, όπου ανήκετε, και τώρα χρειαζόμαστε 1, 2, 3, 4, 5, 6, 7, 8, 9 μπάλες άγχος, και το χειροκρότημά του για αυτά τα παιδιά, αν μπορούσαμε. Όμορφα γίνει. 

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

ΟΜΙΛΗΤΗΣ 1: Εντάξει. Και μπορεί να κρατήσει τα κομμάτια χαρτιού ως αναμνηστικά. 

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

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

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

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

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

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

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

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

Έχουμε 26 επιλογές. Όταν θέλουμε να την βάλει; Τη θέλουμε στο βραχίονα μηδέν, έτσι δεν είναι; Α για την Αλίκη, ας το ονομάσουμε αυτό το μηδενικό. Και B θα είναι ένα, και C θα είναι δύο. Έτσι θα πάμε για να γράψει Το όνομα της Αλίκης μέχρι εδώ. Αν στη συνέχεια τοποθετήστε Bob, του όνομα θα πάει εδώ. Charlie θα πάει εδώ. Και ούτω καθεξής κάτω μέσω Αυτή η δομή δεδομένων. 

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

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

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

Αλλά φυσικά, ότι είμαι αφελής εδώ, έτσι δεν είναι; Τι γίνεται αν υπάρχει ένα Aaron στην τάξη; Ή Alicia; Ή οποιαδήποτε άλλα ονόματα που αρχίζουν με A. Όταν θα πάμε να θέσει το εν λόγω πρόσωπο, έτσι δεν είναι; Θέλω να πω, αυτή τη στιγμή υπάρχει μόνο τρεις οι άνθρωποι στο τραπέζι, οπότε ίσως είμαστε πρέπει να θέσει Aaron στη θέση μηδέν ένα δύο τρία. 

Σωστά, θα μπορούσατε να βάλετε ένα εδώ. Στη συνέχεια, όμως, αν προσπαθήσουμε να εισαγάγετε τον David σε Ο κατάλογος αυτός, όπου ο Δαβίδ πάτε; Τώρα το σύστημά μας ξεκινά το σπάσιμο κάτω, δεξιά; Επειδή τώρα ο David καταλήγει εδώ αν Aaron είναι πραγματικά εδώ. Και έτσι τώρα όλη αυτή η ιδέα του να έχετε ένα καθαρή δομή των δεδομένων που μας δίνει σταθερές εισαγωγές χρόνος δεν είναι πλέον σταθερό χρόνο, γιατί έχω να έλεγχο, oh, damnit, κάποιος είναι ήδη στη θέση της Αλίκης. 

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

Έτσι, εντάξει, εγώ θα το διορθώσω αυτό. Το πρόβλημα εδώ είναι ότι είχα 26 στοιχεία σε αυτή την συστοιχία. Επιτρέψτε μου να το αλλάξετε. Ωχ. Επιτρέψτε μου να το αλλάξετε έτσι ώστε αντί να της μέγεθος 26 στο σύνολο, παρατηρήσετε το κάτω μέρος Δείκτης πρόκειται να αλλάξει στο n μείον 1. Αν 26 είναι σαφώς πολύ μικρό για «τον άνθρωπο ονόματα, γιατί υπάρχουν χιλιάδες ονόματα του κόσμου, ας κάνουν σε 100 ή 1.000 ή 10.000. Ας διαθέσει μόνο πολύ περισσότερο χώρο. 

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

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

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

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

Έτσι, αν hash Alice είναι ένα όνομα, μια συνάρτηση κατακερματισμού, να το πω έτσι, θα πρέπει να επιστρέψει έναν αριθμό. Σε αυτή την περίπτωση είναι μηδέν αν ανήκει σε θέση μηδέν, ένα, εάν ανήκει σε μία θέση, και ούτω καθεξής. Έτσι συνάρτηση κατακερματισμού μου μέχρι στιγμής έχει εξαιρετικά απλή, μόνο κοιτάζοντας το πρώτο γράμμα στο όνομα κάποιου. Αλλά μια hash συνάρτηση παίρνει ως input κάποιο κομμάτι των δεδομένων, string, ένας int, οτιδήποτε. Και φτύσει συνήθως μια σειρά. Και ο αριθμός αυτός είναι όπου αυτά τα δεδομένα στοιχείο ανήκει σε μία δομή δεδομένων γνωστή εδώ ως ένα πίνακα κατακερματισμού. 

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

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ 1: Ναι, έτσι και εδώ έχουμε η μόχλευση των συνδεδεμένων λιστών. Γι 'αυτό φαίνεται λίγο διαφορετικά από ό, τι επέστησε νωρίτερα. Αλλά εμείς φαίνεται να έχουν σε μία συστοιχία στην αριστερή πλευρά. Αυτό είναι ένα ευρετήριο, για κανένα ιδιαίτερος λόγος. Αλλά είναι ακόμα μια σειρά. Είναι μια σειρά από δείκτες. Και καθένα από αυτά τα στοιχεία, καθένα από τα οι κύκλοι ή καθέτους - η κάθετος εκπροσωπούν null - κάθε ένα από αυτά δείκτες προφανώς δείχνοντας Τι δομή δεδομένων; Μια συνδεδεμένη λίστα. 

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

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

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

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

Έτσι, σε ένα δωμάτιο του n CS50 μαθητών, τι είναι η πιθανότητα ότι τουλάχιστον δύο μαθητές στο δωμάτιο έχουν τα ίδια γενέθλια; Έτσι, υπάρχει αυτό. λίγα Hund - 200, 300 άτομα εδώ και αρκετά εκατοντάδες άτομα στο σπίτι σήμερα. Έτσι, αν θέλετε να αναρωτηθούμε τι είναι η πιθανότητα δύο άτομα σε αυτό το δωμάτιο έχουν την ίδια ημερομηνία γέννησης, μπορούμε να το καταλάβουν αυτό. Και εγώ ισχυρίζομαι στην πραγματικότητα υπάρχουν δύο άτομα με την ίδια γενέθλια. 

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

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

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

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

Και το φαγητό από αυτήν την καμπύλη είναι ότι το συντομότερο θα έχετε να αρέσει 40 φοιτητές, είστε επάνω σε μια πιθανότητα 90% combinatorically των δύο ή περισσότερα άτομα που έχουν η ίδια γενέθλια. Και τη στιγμή που μπορείτε να πάρετε για τα 58 άτομα είναι σχεδόν το 100% της μια ευκαιρία οι δύο άτομα σε ένα δωμάτιο πρόκειται να έχουν το ίδια γενέθλια, ακόμα κι αν δεν υπάρχει 365 ή 366 πιθανές κουβάδες, και μόνο 58 άτομα σε ένα δωμάτιο. Απλά στατιστικά είναι πιθανό να πάρετε συγκρούσεις, η οποία σε σύντομο παρακινεί αυτή τη συζήτηση. Ότι ακόμα κι αν πάρετε φανταχτερό εδώ, και αρχίζουν να έχουν αυτές τις αλυσίδες, είμαστε ακόμα πρόκειται να έχει συγκρούσεις. 

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

Αν πάλι υπάρχει 31 δυνατό Γενέθλια σε έναν δεδομένο μήνα. Και είμαστε συσσώρευση απλά ο καθένας - Στην πραγματικότητα αυτό είναι ένα ηλίθιο παράδειγμα. Ας κάνουμε 26 αντ 'αυτού. Έτσι, αν έχουν στην πραγματικότητα οι άνθρωποι των οποίων τα ονόματα Ξεκινήστε με ένα έως Z, δίνοντας έτσι 26 μας δυνατότητες. Και είμαστε χρησιμοποιώντας μια δομή δεδομένων, όπως το ένα μόλις είδαμε, με την οποία έχουμε μια σειρά από δείκτες, καθένα από τα οποία σημεία σε μια συνδεδεμένη λίστα, όπου το πρώτος κατάλογος είναι ο καθένας με το όνομα Alice. Ο δεύτερος κατάλογος είναι κάθε με το όνομα που αρχίζει με Α, ξεκινώντας με το Β, και ούτω καθεξής. 

Ποια είναι η πιθανή μήκος κάθε οι κατάλογοι αν υποθέσουμε ένα ωραίο καθαρό διανομή των ονομάτων Α έως Ζ σε όλη την δομή των δεδομένων; Υπάρχει n ανθρώπους στη δομή δεδομένων διαιρείται με 26, αν είναι όμορφα απλώνονται σε όλο το δομή δεδομένων. Έτσι, το μήκος καθενός από αυτά αλυσίδες είναι n διαιρείται με 26. Αλλά σε μεγάλο συμβολισμό O, τι είναι αυτό; Τι είναι αυτό πραγματικά; Έτσι, είναι πραγματικά ακριβώς n, έτσι δεν είναι; Επειδή έχουμε πει και στο παρελθόν, ότι ugh σας χωρίζουν από 26. Ναι, στην πραγματικότητα είναι πιο γρήγορα. Αλλά στη θεωρία, δεν είναι θεμελιωδώς όλα αυτά πιο γρήγορα. 

Γι 'αυτό και δεν φαίνεται να είναι όλα αυτά πολύ πιο κοντά σε αυτό το Άγιο Δισκοπότηρο. Στην πραγματικότητα, αυτό είναι μόνο γραμμικό χρόνο. Heck, σε αυτό το σημείο, γιατί δεν απλά χρησιμοποιήστε ένα τεράστιο συνδεδεμένη λίστα; Γιατί δεν χρησιμοποιούμε απλώς μια τεράστια πίνακα για να αποθηκεύσετε τα ονόματα των ο καθένας στο δωμάτιο; Λοιπόν, υπάρχει ακόμα κάτι συναρπαστικό για ένα πίνακα κατακερματισμού; Υπάρχει ακόμα υπάρχει κάτι συναρπαστικό για μια δομή δεδομένων που μοιάζει με αυτό; Αυτό. 

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ 1: Δεξιά, και πάλι αν είναι απλά ένα γραμμικό αλγόριθμο του χρόνου, και ένα γραμμική δομή του χρόνου τα δεδομένα, γιατί δεν μπορώ να αποθηκεύουν μόνο το όνομα του καθενός σε ένα μεγάλο array, ή σε ένα συνδεδεμένο μεγάλη λίστα; Και σταματήσει να κάνει CS πολύ πιο δύσκολο ό, τι πρέπει να είναι; Τι είναι συναρπαστικό γι 'αυτό, ακόμα και αν και το γδαρμένο έξω; 

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

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

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

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

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

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

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

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ 1: Στην αριστερή. Έτσι, αυτό που είναι ενδιαφέρον με αυτά τα δεδομένα δομή είναι αντί κατάστημα της συμβολοσειρά Μ-Α-Χ-W-E-L-L backslash μηδέν, όλα συνεχόμενα, τι αντί να κάνετε ακολουθεί. Εάν αυτό είναι ένα trie όπως η δομή των δεδομένων, κάθε ένα από τους κόμβους των οποίων είναι και πάλι μια σειρά, και θέλετε να αποθηκεύσετε Maxwell, θα πρέπει πρώτα δείκτη και έτσι ο κόμβος της ρίζας, έτσι να μιλήσει, το κορυφαίο κόμβο, στη θέση M, δεξιά, έτσι ώστε περίπου στη μέση. Και στη συνέχεια, από εκεί, θα ακολουθήσει μια δείκτη σε κόμβους του παιδιού, να το πω έτσι. Έτσι, με την έννοια οικογενειακό δέντρο, μπορείτε να ακολουθήσετε προς τα κάτω. Και αυτό θα οδηγήσει σε ένα άλλο κόμβο στην αριστερή εκεί, η οποία είναι ακριβώς ένα άλλο πίνακα. 

Και στη συνέχεια, αν θέλετε να αποθηκεύσετε Maxwell, μπορείτε να βρείτε το δείκτη που αντιπροσωπεύει Α, το οποίο είναι αυτό εδώ. Στη συνέχεια πηγαίνετε στον επόμενο κόμβο. Και σημειώστε - αυτό είναι γιατί η εικόνα του λίγο παραπλανητική - ο κόμβος βλέμμα σούπερ μικρό. Αλλά για το δικαίωμα αυτό είναι Υ και Ζ. Είναι ακριβώς ο συγγραφέας έχει περικοπεί η εικόνα έτσι ώστε να μπορείτε πραγματικά δείτε τα πράγματα. Διαφορετικά, αυτή η εικόνα θα είναι εξαιρετικά ευρύ. Έτσι τώρα μπορείτε δείκτη στην θέση Χ, στη συνέχεια, W, E, τότε L, στη συνέχεια L. Τότε τι είναι αυτή η περιέργεια; 

Λοιπόν, αν είστε με τη χρήση αυτού του είδους των νέων να λάβει σχετικά με το πώς να αποθηκεύσετε ένα string σε ένα δομή των δεδομένων, θα πρέπει ακόμα να ουσιαστικά ελέγχουν off στα δεδομένα δομή ότι μια λέξη τελειώνει εδώ. Με άλλα λόγια, κάθε ένα από αυτούς τους κόμβους με κάποιο τρόπο θα πρέπει να θυμόμαστε ότι πράγματι ακολούθησε όλες αυτές τις υποδείξεις και αφήνοντας λίγο ψίχα ψωμιού στο κάτω μέρος της εδώ αυτό δομή για να δείξει Μ-Α-Χ-W-E-L-L είναι Πράγματι, σε αυτή τη δομή δεδομένων. 

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

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

Έτσι, αυτό είναι μια trie. Και τώρα το ερώτημα είναι, τι τρέχει του χρόνου; Είναι μεγάλη O Ν; Είναι κάτι άλλο; Λοιπόν, αν έχετε n ονόματα σε αυτά τα δεδομένα δομή, Maxwell είναι ένα μόνο από τους, τι είναι ο χρόνος εκτέλεσης του εισαγωγή ή την εύρεση Maxwell; Τι είναι ο χρόνος εκτέλεσης της εισαγωγής Maxwell; Αν υπάρχει n άλλα ονόματα ήδη στον πίνακα; Ναι; 

ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ 1: Ναι, αυτό είναι το μήκος το όνομα, έτσι δεν είναι; Έτσι, Μ-Α-Χ-w-e-l-l έτσι ώστε να αισθάνεται σαν αυτό αλγόριθμος είναι μεγάλη O επτά. Τώρα, φυσικά, το όνομα θα ποικίλουν σε μήκος. Ίσως αυτό είναι ένα σύντομο όνομα. Ίσως είναι ένα μεγαλύτερο όνομα. Αλλά αυτό είναι το κλειδί εδώ είναι ότι είναι ένας σταθερός αριθμός. Και ίσως δεν είναι πολύ σταθερή, Αλλά ο Θεός, αν ρεαλιστικά, σε λεξικό, είναι πιθανόν να υπάρχει κάποιο όριο σχετικά με τον αριθμό των γραμμάτων σε μια το όνομα του ατόμου σε μια συγκεκριμένη χώρα. 

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

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

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

Αλλά στο κλείσιμο ας ρίξουμε 50 ή έτσι δευτερόλεπτα για να λάβει μια ματιά σε ό, τι βρίσκεται την ερχόμενη εβδομάδα και πέρα ​​έχουμε μετάβαση από αυτή την γραμμή εντολών κόσμο, εάν τα προγράμματα C τα πράγματα web βάση και γλώσσες όπως η PHP και JavaScript και το ίδιο το διαδίκτυο, πρωτόκολλα όπως το HTTP, το οποίο έχετε θεωρείται δεδομένη για πολλά χρόνια τώρα, και δακτυλογραφημένες πλέον κάθε ημερών, ίσως, ή δει. Και θα αρχίσουμε να φλούδα πίσω την στρώματα του τι είναι το διαδίκτυο. Και τι είναι ο κώδικας που κρύβεται πίσω από τη σημερινή εργαλεία. Έτσι, 50 δευτερόλεπτα αυτού του teaser εδώ. Σας δίνω Πολεμιστές του Net. 

[PLAYBACK VIDEO] 

-Ήρθε με ένα μήνυμα. Με ένα πρωτόκολλο όλα δικά του. Ήρθε σε έναν κόσμο της σκληρής firewalls, αδιάφορος routers, και τους κινδύνους μακριά χειρότερη από τον θάνατο. Είναι γρήγορος. Είναι ισχυρή. Είναι TCPIP. Και πήρε τη διεύθυνσή σας. Πολεμιστές του Net. 

[PLAYBACK VIDEO END] 

ΟΜΙΛΗΤΗΣ 1: Αυτό είναι το πώς το Διαδίκτυο πρέπει να λειτουργήσει ως της επόμενης εβδομάδας.