[Powered by Google Translate] [Εβδομάδα 6, Συνέχεια] [David J. Malan] [Πανεπιστήμιο του Χάρβαρντ] [Αυτό είναι CS50.] [CS50.TV] Αυτό είναι CS50 και αυτό είναι το τέλος της εβδομάδας 6. Έτσι CS50x, ένα από τα πρώτα μαθήματα του Χάρβαρντ που συμμετέχουν στην πρωτοβουλία EDX Πράγματι, έκανε το ντεμπούτο του την περασμένη Δευτέρα. Αν θέλετε να πάρετε μια γεύση από το τι άλλοι στο Διαδίκτυο ακολουθούν τώρα μαζί με, μπορείτε να κατευθυνθείτε προς x.cs50.net. Αυτό θα σας ανακατευθύνει στην κατάλληλη θέση για edx.org, η οποία ήταν και αυτή όπου άλλα μαθήματα από το MIT και το Berkeley ζουν τώρα. Θα πρέπει να εγγραφείτε για ένα λογαριασμό? Θα βρείτε ότι το υλικό είναι σε μεγάλο βαθμό η ίδια όπως είχατε αυτό το εξάμηνο, αν και καθυστέρησε μερικές εβδομάδες, όπως έχουμε πάρει τα πάντα έτοιμα. Αλλά ό, τι οι μαθητές στο CS50x θα δούμε τώρα είναι μια διεπαφή αρκετά όπως αυτό. Αυτό, για παράδειγμα, είναι Zamyla οδηγεί το walkthrough για σετ προβλήματος 0. Μόλις συνδεθείτε με edx.org, ένας φοιτητής CS50x βλέπει τα είδη των πραγμάτων που θα περιμένατε να δείτε σε ένα μάθημα: η διάλεξη για τη Δευτέρα, διάλεξη για την Τετάρτη, διάφορα σορτς, τα σύνολα πρόβλημα, τα περάσματα, αρχεία PDF. Επιπλέον, όπως βλέπετε εδώ, αυτόματες μεταφράσεις της αγγλικής μεταγραφές σε κινεζικά, ιαπωνικά, ισπανικά, ιταλικά, και ένα σωρό άλλες γλώσσες που σίγουρα θα είναι ατελής όπως εμείς τους ανοίγουμε με προγραμματισμό χρησιμοποιώντας κάτι που ονομάζεται ένα API, ή διεπαφή προγραμματισμού εφαρμογών, από την Google που μας επιτρέπει να μετατρέψετε Αγγλικά σε αυτές τις άλλες γλώσσες. Αλλά χάρη στο υπέροχο πνεύμα μερικών εκατοντάδων εθελοντών-plus, τυχαίους ανθρώπους στο διαδίκτυο που προσφέρθηκαν ευγενικά να συμμετάσχουν σε αυτό το έργο, θα πρέπει σταδιακά να βελτιωθεί η ποιότητα των μεταφράσεων από τους ανθρώπους που έχουν διορθώσει τα λάθη που οι υπολογιστές μας έχουν κάνει. 

Έτσι αποδεικνύεται είχαμε λίγα περισσότεροι φοιτητές δείχνουν μέχρι τη Δευτέρα από ό, τι αρχικά αναμενόταν. Στην πραγματικότητα, τώρα έχει CS50x 100.000 άνθρωποι μετά μαζί στο σπίτι. Έτσι συνειδητοποιήσει ότι είναι όλα μέρος αυτής της εναρκτήριας κατηγορίας του κάνει αυτή την πορεία στην επιστήμη των υπολογιστών εκπαίδευση γενικότερα, ευρύτερα, προσβάσιμα. Και η πραγματικότητα είναι τώρα, με μερικά από αυτά τα τεράστια online μαθήματα, όλα αρχίζουν με αυτούς τους πολύ μεγάλους αριθμούς, όπως φαίνεται να έχουν γίνει εδώ. Αλλά ο στόχος, εν τέλει, για CS50x είναι πραγματικά να πάρει, όπως πολλοί άνθρωποι στην γραμμή του τερματισμού όσο το δυνατόν. Από τη σχεδίαση, CS50x πρόκειται να προσφέρει από αυτό περασμένη Δευτέρα σε όλη τη διαδρομή μέσα από 15 του Απριλίου 2013, έτσι ώστε οι λαοί που έχουν δεσμεύσεις αλλού σχολείο, την εργασία, την οικογένεια, άλλες συγκρούσεις και τα παρόμοια, έχουν λίγο περισσότερη ευελιξία με την οποία να βουτήξει σε αυτή την πορεία, η οποία, αρκεί να πούμε, είναι αρκετά φιλόδοξα, αν γίνει μόνο κατά τη διάρκεια του μόλις τρεις μήνες κατά τη διάρκεια μιας συνήθους εξάμηνο. Αλλά αυτοί οι μαθητές θα αντιμετωπιστούν οι ίδιες ομάδες πρόβλημα, που βλέπουν το ίδιο περιεχόμενο, έχοντας πρόσβαση στις ίδιες σορτς και τα παρόμοια. Έτσι συνειδητοποιούμε ότι είμαστε όλοι πραγματικά σε αυτή μαζί. Και ένας από τους στόχους τέλος του CS50x δεν είναι μόνο για να πάρει όσες λαοί στη γραμμή του τερματισμού και να τους δώσουμε αυτή την πρωτόγνωρη κατανόηση της επιστήμης των υπολογιστών και τον προγραμματισμό, αλλά και να έχουν τους έχουν αυτή την κοινή εμπειρία. Ένα από τα καθοριστικά χαρακτηριστικά των 50 στην πανεπιστημιούπολη, ελπίζουμε, έχει αυτό το είδος των κοινόχρηστων εμπειρία, προς το καλύτερο ή προς το χειρότερο, μερικές φορές, αλλά έχοντας τα άτομα αυτά να στραφούν σε προς τα αριστερά και προς τα δεξιά, και ώρες γραφείου και ο hackathon και η εύλογη. Είναι λίγο δύσκολο να το κάνουμε αυτό σε πρόσωπο με τους λαούς σε απευθείας σύνδεση, αλλά CS50x θα ολοκληρωθεί τον Απρίλιο με την πρώτη CS50 Expo, το οποίο θα είναι ένα online προσαρμογή της ιδέας μας της δίκαιης όπου οι χιλιάδες μαθητές θα κληθούν όλοι να υποβάλουν 1 - σε 2-λεπτών βίντεο, είτε ένα screencast του τελικού σχεδίου ή βίντεο τους από τους κουνώντας γεια και μιλούν για το έργο τους και να demoing, πολύ όπως και οι προκάτοχοί σας έχουν κάνει εδώ στην πανεπιστημιούπολη στην εύλογη, έτσι ώστε μέχρι το τέλος του εξαμήνου, η ελπίδα είναι να έχουμε μια παγκόσμια έκθεση των τελικών σχεδίων των CS50x φοιτητών, σαν εκείνο που σας περιμένει αυτό το Δεκέμβρη στην πανεπιστημιούπολη. Έτσι, περισσότερα για αυτό κατά τους μήνες που έρχονται. 

Με 100.000 σπουδαστές, όμως, έρχεται μια ανάγκη για λίγα ΑΠ. Δεδομένου ότι εσείς είστε απίστευτα το μονοπάτι εδώ και λαμβάνοντας CS50 αρκετές εβδομάδες πριν από την κυκλοφορία αυτού του υλικού για τους λαούς για EDX, συνειδητοποιούν θα θέλαμε να συμμετέχουν, όπως πολλοί από τους σπουδαστές μας όσο το δυνατόν σε αυτή την πρωτοβουλία, τόσο κατά τη διάρκεια του εξαμήνου, καθώς και αυτό το χειμώνα και την ερχόμενη άνοιξη. Έτσι, αν θα θέλατε να λάβετε μέρος σε CS50x, ιδιαίτερα για ένταξη στην CS50x Συζητήστε, η έκδοση του EDX CS50 Συζητήστε, το οποίο πολλοί από εσάς έχουν χρησιμοποιήσει στην πανεπιστημιούπολη, η σε απευθείας σύνδεση πίνακα ανακοινώσεων, παρακαλώ να το κάνετε αυτό στο κεφάλι URL, να μας πείτε ποιος είστε, επειδή θα θέλαμε να δημιουργήσουν μια ομάδα φοιτητών και προσωπικού και το διδακτικό προσωπικό όσο στην πανεπιστημιούπολη που απλά παίζουν μαζί και να βοηθήσει έξω. Και όταν βλέπουν μια ερώτηση που είναι εξοικειωμένοι με αυτούς, ακούτε ένα φοιτητή αναφέρουν κάποια bug κάπου εκεί έξω, σε κάποια χώρα στο Διαδίκτυο, και ότι τα δαχτυλίδια ένα κουδούνι, γιατί είχε πάρα πολύ το ίδιο θέμα στο d-αίθουσα πριν από λίγο καιρό, ελπίζω τότε μπορείτε να συνάδουν και να μοιραστείτε την εμπειρία σας. Επομένως, σας παρακαλώ μην συμμετάσχουν εάν θα θέλατε. 

Μαθήματα επιστήμης των υπολογιστών στο Χάρβαρντ έχουν ένα κομμάτι της παράδοσης, CS50 μεταξύ τους, να έχουν κάποια ένδυσης, κάποια ρούχα, που μπορείτε να φοράτε με περηφάνια στο τέλος του εξαμήνου, λέγοντας πολύ περήφανα ότι έχετε τελειώσει CS50 και πήρε CS50 και τα παρόμοια, και προσπαθούμε πάντα να εμπλέξουν τους μαθητές σε αυτή τη διαδικασία όσο το δυνατόν περισσότερο, σύμφωνα με την οποία καλούμε, όλο αυτό το διάστημα του εξαμήνου, οι φοιτητές να υποβάλουν τα σχέδια χρησιμοποιώντας το Photoshop, ή ό, τι το εργαλείο της επιλογής που θέλετε να χρησιμοποιήσετε εάν είστε ένας σχεδιαστής, να υποβάλουν σχέδια για T-shirts και φούτερ και ομπρέλες και φουλάρια λίγο για τα σκυλιά που έχουμε τώρα και τα παρόμοια. Και ό, τι είναι τότε - οι νικητές κάθε χρόνο, στη συνέχεια εκτίθενται στην ιστοσελίδα του μαθήματος στο store.cs50.net. Τα πάντα πωλείται σε τιμή κόστους εκεί, αλλά η ιστοσελίδα τρέχει το ίδιο ακριβώς και επιτρέπει στους ανθρώπους να επιλέξετε τα χρώματα και τα σχέδια που τους αρέσει. Έτσι σκέφτηκα ότι θα μοιράζονται μόνο μερικά από τα σχέδια του περασμένου έτους που ήταν στο δικτυακό τόπο εκτός από αυτό εδώ, το οποίο είναι μια ετήσια παράδοση. «Κάθε μέρα είμαι ακολ Faultn" ήταν ένα από τα αιτήματα πέρυσι, η οποία εξακολουθεί να είναι διαθέσιμη εκεί για τους αποφοίτους. Είχαμε αυτό το ένα, "CS50, ιδρύθηκε το 1989." Ένα από Bowdens μας, Rob, ήταν πολύ δημοφιλής πέρυσι. "Ομάδα Bowden" γεννήθηκε, το σχέδιο αυτό υποβλήθηκε, μεταξύ των κορυφαίων πωλητών. Όπως ήταν αυτό εδώ. Πολλοί άνθρωποι είχαν "Πυρετός Bowden", σύμφωνα με τις καταγραφές των πωλήσεων. Συνειδητοποιήστε ότι θα μπορούσε τώρα να είναι το σχέδιό σας εκεί, επάνω στο Διαδίκτυο. Περισσότερες λεπτομέρειες για το θέμα αυτό στην επόμενη θέτει πρόβλημα να έρθει. 

Ένα ακόμη εργαλείο: είχατε κάποια έκθεση και ελπίζω τώρα κάποια hands-on εμπειρία με το GDB, το οποίο είναι, φυσικά, ένα πρόγραμμα εντοπισμού σφαλμάτων και σας επιτρέπει να χειριστείτε το πρόγραμμά σας σε ένα αρκετά χαμηλό επίπεδο, κάνει ό, τι τα είδη των πραγμάτων; Τι σημαίνει GDB σας επιτρέπουν να το κάνετε; Ναι; Δώσε μου κάτι. [Απάντηση Φοιτητής, ακατάληπτο] Καλή. Βήμα σε λειτουργία, έτσι ώστε να μην πρέπει απλώς να πληκτρολογήσετε run και έχουν το χτύπημα του προγράμματος μέσω σύνολό της, εκτύπωση από τα πράγματα στην κανονική έξοδο. Αντίθετα, μπορείτε να το βήμα μέσα από το γραμμή προς γραμμή, είτε πληκτρολογώντας επόμενη για να πάει γραμμή προς γραμμή, γραμμή βήμα ή να βουτήξει σε μια λειτουργία, συνήθως αυτό που γράψατε. Τι άλλο GDB σας επιτρέπουν να κάνετε; Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Εκτύπωση μεταβλητών. Έτσι, εάν θέλετε να κάνετε μια μικρή ενδοσκόπηση μέσα από το πρόγραμμα σας χωρίς να χρειάζεται να καταφύγουν σε γραπτή printf δηλώσεις σε όλη τη χώρα, μπορείτε να εκτυπώσετε μόνο μια μεταβλητή ή να εμφανίσετε μια μεταβλητή. Τι άλλο μπορείτε να κάνετε με ένα πρόγραμμα εντοπισμού σφαλμάτων, όπως GDB; [Απάντηση Φοιτητής, ακατάληπτο] Ακριβώς. Μπορείτε να ορίσετε σημεία διακοπής? Μπορείτε να πείτε την εκτέλεση διάλειμμα στην κύρια λειτουργία ή τη λειτουργία foo. Μπορείτε να πείτε την εκτέλεση διάλειμμα στη γραμμή 123. Και όρια ευαισθησίας είναι μια πραγματικά ισχυρή τεχνική διότι αν έχετε μια γενική αίσθηση για το πού το πρόβλημά σας πιθανότατα είναι, δεν πρέπει να χάνουμε χρόνο με την ενίσχυση σύνολο του προγράμματος. Μπορείτε να μεταβείτε ουσιαστικά εκεί και μετά αρχίστε την πληκτρολόγηση - ενίσχυση μέσα από αυτό το βήμα ή τον επόμενο ή τα παρόμοια. Όμως, τα αλιεύματα με κάτι σαν GDB είναι ότι σας βοηθά, ο άνθρωπος, βρείτε τα προβλήματά σας και να βρείτε σφάλματα σας. Αυτό δεν σημαίνει απαραίτητα να τους βρείτε τόσα πολλά για σας. 

Γι 'αυτό και εισήγαγε την άλλη style50 ημέρα, το οποίο είναι ένα μικρό εργαλείο της γραμμής εντολών που προσπαθεί να στυλιζάρω κωδικό σας λίγο πιο καθαρά από ό, τι, ο άνθρωπος, θα μπορούσε να έχει γίνει. Αλλά αυτό, επίσης, είναι πραγματικά ακριβώς ένα αισθητικό πράγμα. Αλλά αποδεικνύεται ότι υπάρχει αυτό το άλλο εργαλείο που ονομάζεται Valgrind που είναι λίγο πιο απόκρυφες να χρησιμοποιήσετε. Τα αποτελέσματά του είναι atrociously αινιγματικά με την πρώτη ματιά. Αλλά είναι θαυμάσια χρήσιμο, ειδικά τώρα που είμαστε στο τμήμα του όρου Όπου και αν αρχίζουν να χρησιμοποιούν malloc και δυναμική κατανομή μνήμης. Τα πράγματα μπορούν να πάνε πολύ, πολύ γρήγορα λάθος. Διότι, αν ξεχάσετε να ελευθερώσετε τη μνήμη σας, ή έχετε κάποια dereference NULL δείκτη, ή μπορείτε dereference κάποιο δείκτη σκουπίδια, ό, τι είναι συνήθως το σύμπτωμα που προκύπτει; Seg σφάλμα. Και μπορείτε να πάρετε αυτό το αρχείο πυρήνα κάποιον αριθμό των kilobyte ή megabytes που αντιπροσωπεύει την κατάσταση της μνήμης του προγράμματός σας, όταν συνετρίβη, αλλά το πρόγραμμα σας διαχωρίζονται από βλάβες τελικά, σφάλμα κατάτμησης, που σημαίνει κάτι κακό συνέβη σχεδόν πάντα συνδέονται σε μια μνήμη που σχετίζονται λάθος που κάνατε κάπου. Έτσι Valgrind σας βοηθά να βρείτε τα πράγματα όπως αυτό. Είναι ένα εργαλείο που εκτελείτε, όπως GDB, αφού έχετε καταρτίζονται πρόγραμμα σας, αλλά αντί να τρέξετε το πρόγραμμά σας άμεσα, μπορείτε να εκτελέσετε Valgrind και να περάσετε το πρόγραμμά σας, ακριβώς όπως κάνετε με το GDB. Τώρα, η χρήση του, για να πάρει το καλύτερο είδος της παραγωγής, είναι λίγο καιρό, έτσι εκεί στην κορυφή της οθόνης θα δείτε Valgrind-v. "-V" σχεδόν καθολικά σημαίνει φλύαρη όταν χρησιμοποιείτε προγράμματα σε υπολογιστή με Linux. Έτσι, αυτό σημαίνει φτύσει περισσότερα δεδομένα από ό, τι ίσως από προεπιλογή. "- Έλεγχος διαρροών = πλήρης." Αυτό που λέει ακριβώς επιταγή για όλες τις πιθανές διαρροές μνήμης, τα λάθη που μπορεί να έγιναν. Αυτό, επίσης, είναι ένα κοινό παράδειγμα με προγράμματα Linux. Σε γενικές γραμμές, αν έχετε ένα όρισμα γραμμής εντολών αυτό είναι ένα «διακόπτη», που υποτίθεται για να αλλάξει τη συμπεριφορά του προγράμματος, και αυτό είναι ένα μόνο γράμμα, είναι-κατά, αλλά αν αυτό είναι ενεργοποιημένο, μόνο από το σχεδιασμό του προγραμματιστή, είναι μια λέξη ή πλήρη σειρά των λέξεων, το επιχείρημα της γραμμής εντολών ξεκινά με -. Αυτά είναι μόνο τα ανθρώπινα, αλλά θα τους δούμε όλο και περισσότερο. Και έπειτα, τελικά, "a.out" είναι η αυθαίρετη όνομα για το πρόγραμμα σε αυτό το συγκεκριμένο παράδειγμα. Και εδώ είναι μερικά εκπρόσωπος εξόδου. 

Πριν κοιτάξουμε τι μπορεί να σημαίνει αυτό, επιτρέψτε μου να πάει πάνω σε ένα απόσπασμα του κώδικα εδώ. Και επιτρέψτε μου να μετακινήσετε αυτό το έξω από το δρόμο, σύντομα, και ας ρίξουμε μια ματιά στο memory.c, το οποίο είναι αυτό το σύντομο παράδειγμα εδώ. Έτσι, σε αυτό το πρόγραμμα, επιτρέψτε μου να μεγεθύνετε τις λειτουργίες και τις ερωτήσεις. Έχουμε μια κύρια λειτουργία που απαιτεί μια λειτουργία, στ, και στη συνέχεια, τι στ προχωρήσει να κάνει, σε ελαφρώς τεχνικό αγγλικά; Τι σημαίνει στ προχωρήσει να κάνει; Πόσο περίπου θα αρχίσω με τη γραμμή 20, και τη θέση του αστεριού δεν έχει σημασία, αλλά εγώ θα πρέπει ακριβώς να είναι συνεπής εδώ με την τελευταία διάλεξη. Ποια είναι η γραμμή 20 κάνει για μας; Από την αριστερή πλευρά. Θα το σπάσει περαιτέρω. Int * x: τι κάνει ότι κάνει; Εντάξει. Είναι δηλώνοντας ένα δείκτη, και τώρα ας είναι ακόμα πιο τεχνικό. Τι σημαίνει, πολύ συγκεκριμένα, να δηλώσει ένα δείκτη; Κάποιος άλλος; Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Πάρα πολύ. Έτσι, μπορείτε να διαβάζετε στη δεξιά πλευρά του συμβόλου του ίσον. Ας επικεντρωθούν στα αριστερά, ακριβώς στο int * x. Αυτό σημαίνει "δηλώνει" ένα δείκτη, αλλά τώρα ας βουτήξει σε πιο βαθιά σε αυτόν τον ορισμό. Τι σημαίνει ότι συγκεκριμένα, τεχνικά σημαίνει; Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Εντάξει. Είναι ετοιμάζεται να αποθηκεύσετε μία διεύθυνση στη μνήμη. Καλή. Και ας πάρουμε ένα βήμα παραπέρα? Αυτό είναι που κηρύσσει μια μεταβλητή, x, που είναι 32 bits. Και ξέρω ότι είναι 32 bit, επειδή - Δεν είναι επειδή είναι ένα int, επειδή είναι ένας δείκτης σε αυτή την περίπτωση. Σύμπτωση ότι είναι ένα και το αυτό με έναν int, αλλά το γεγονός ότι υπάρχει το αστέρι σημαίνει ότι υπάρχει αυτό είναι ένας δείκτης και στη συσκευή, όπως με πολλούς υπολογιστές, αλλά όχι όλες, δείκτες είναι 32 bits. Στις πιο σύγχρονο εξοπλισμό, όπως τις τελευταίες υπολογιστές Mac, οι τελευταίες υπολογιστές, μπορεί να έχετε 64-bit δείκτες, αλλά στη συσκευή, αυτά τα πράγματα είναι 32 bits. Γι 'αυτό και θα τυποποιηθούν σε αυτό. Πιο συγκεκριμένα, η ιστορία συνεχίζεται ως εξής: Εμείς "δηλώνουν" ένα δείκτη? Τι σημαίνει αυτό; Έχουμε προετοιμάσει για να αποθηκεύσετε μια διεύθυνση μνήμης. Τι σημαίνει αυτό; Έχουμε δημιουργήσει μια μεταβλητή που ονομάζεται x που καταλαμβάνει 32 bits που θα αποθηκεύσει σύντομα τη διεύθυνση του ακεραίου. Και αυτό είναι πιθανώς περίπου τόσο ακριβής όσο μπορούμε να πάρουμε. Είναι ωραία κινείται προς τα εμπρός για να απλοποιήσει τον κόσμο και να πω κηρύξει δείκτη που ονομάζεται x. Δηλώστε ένα δείκτη, αλλά συνειδητοποιούν και να κατανοήσουν τι πραγματικά συμβαίνει ακόμη και σε εκείνες τις λίγες μόλις χαρακτήρες. 

Τώρα, αυτό είναι σχεδόν λίγο πιο εύκολη, ακόμα κι αν είναι μεγαλύτερη έκφραση. Έτσι, αυτό που κάνει αυτό, που είναι τώρα τόνισε: "malloc (10 * sizeof (int))?" Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Καλή. Και θα το πάρω εκεί. Είναι ένα κομμάτι κατανομή της μνήμης για δέκα ακέραιοι. Και τώρα ας βουτήξει σε λίγο βαθύτερα? Αυτό είναι ένα κομμάτι κατανομή της μνήμης για δέκα ακέραιοι. Τι είναι η malloc στη συνέχεια επιστρέφει; Η διεύθυνση του εν λόγω κομμάτι, ή, πιο συγκεκριμένα, η διεύθυνση του πρώτου byte του εν λόγω κομμάτι. Πώς λοιπόν είμαι, ο προγραμματιστής, για να ξέρετε πού αυτό το κομμάτι της μνήμης άκρα; Ξέρω ότι είναι συνεχόμενες. Malloc, εξ ορισμού, θα σας δώσει ένα συνεχόμενο τμήμα της μνήμης. Δεν υπάρχουν κενά σε αυτό. Έχετε πρόσβαση σε κάθε byte σε αυτό το κομμάτι, πλάτη με πλάτη με πλάτη, αλλά πώς μπορώ να ξέρω όπου το τέλος του τρέχοντος κομμάτι της μνήμης είναι; Όταν χρησιμοποιείτε malloc; [Απάντηση Φοιτητής, ακατάληπτο] Καλή. Δεν κάνουμε. Θα πρέπει να θυμόμαστε. Θα πρέπει να θυμάστε ότι θα χρησιμοποιηθεί η τιμή 10, και δεν χρειάζεται καν να φαίνεται ότι έχουν κάνει εδώ. Αλλά η ευθύνη είναι αποκλειστικά για μένα. Strlen, που έχουμε γίνει λίγο εξαρτάται από για έγχορδα, λειτουργεί μόνο εξαιτίας αυτής της σύμβασης που έχει \ 0 ή αυτή η ειδική nul χαρακτήρα, NUL, στο τέλος του string. Αυτό δεν ισχύει μόνο για την αυθαίρετη κομμάτια της μνήμης. Είναι στο χέρι σας. Έτσι, γραμμή 20, λοιπόν, διαθέτει ένα μεγάλο κομμάτι της μνήμης που μπορεί να αποθηκεύσει δέκα ακέραιοι, και αποθηκεύει τη διεύθυνση του πρώτου byte του εν λόγω κομμάτι της μνήμης του που ονομάζεται μεταβλητή x. Ergo, η οποία είναι ένας δείκτης. Έτσι, γραμμή 21, δυστυχώς, ήταν ένα λάθος. Αλλά, πρώτα τι είναι αυτό που κάνει; Είναι λέγοντας κατάστημα στη θέση 10, 0 τιμαριθμική αναπροσαρμογή, από το κομμάτι της μνήμης που ονομάζεται x η τιμή 0. 

Έτσι παρατηρούμε μια-δυο πράγματα συμβαίνουν. Ακόμα κι αν το x είναι ένας δείκτης, ανάκληση από μερικές εβδομάδες πριν ότι μπορείτε ακόμα να χρησιμοποιήσετε τον πίνακα στυλ σημειογραφία βραχίονα πλατεία. Επειδή αυτό είναι πραγματικά σύντομη-χέρι συμβολισμό για την πιο αινιγματικά εμφάνιση αριθμητική δείκτη. όπου θα κάναμε κάτι σαν αυτό: Πάρτε το x διεύθυνση, κινούνται πάνω από 10 σημεία, τότε πάμε εκεί σε ό, τι διεύθυνση αποθηκεύεται σε αυτή τη θέση. Αλλά ειλικρινά, αυτό είναι ακριβώς φρικτό να διαβάσετε και να πάρει άνετα με. Έτσι, ο κόσμος χρησιμοποιεί συνήθως τις αγκύλες, ακριβώς επειδή είναι τόσο πολύ πιο φιλικό προς τον άνθρωπο για να διαβάσετε. Αλλά αυτό είναι ό, τι πραγματικά συμβαίνει κάτω από την κουκούλα? χ είναι μια διεύθυνση, όχι μια συστοιχία, per se. Έτσι, αυτό αποθηκεύει 0 στο σημείο 10 στο x. Γιατί είναι αυτό το κακό; Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Ακριβώς. Θα διατεθεί μόνο δέκα ints, αλλά μετράμε από το 0 κατά τον προγραμματισμό σε C, έτσι ώστε να έχετε πρόσβαση σε 0 1 2 3 4 5 6 7 8 9, αλλά όχι 10. Έτσι, είτε το πρόγραμμα πρόκειται να seg βλάβη ή δεν είναι. Αλλά εμείς δεν γνωρίζουμε πραγματικά? Αυτό είναι ένα είδος nondeterministic συμπεριφορά. Είναι πραγματικά εξαρτάται από το αν είμαστε τυχεροί. Αν αποδειχθεί ότι το λειτουργικό σύστημα δεν πειράζει αν μπορώ να χρησιμοποιήσω αυτό το επιπλέον byte, ακόμη και αν δεν έχει δοθεί σε μένα, το πρόγραμμά μου μπορεί να μην συντριβή. Είναι ωμό, είναι λάθη, αλλά δεν μπορείτε να δείτε αυτό το σύμπτωμα, ή μπορείτε να το δείτε μόνο μία φορά σε μια στιγμή. Αλλά η πραγματικότητα είναι ότι το σφάλμα είναι, στην πραγματικότητα, εκεί. Και είναι πραγματικά προβληματική εάν έχετε γράψει ένα πρόγραμμα που θέλετε να είναι σωστή, ότι έχετε πωληθεί το πρόγραμμα στο οποίο οι άνθρωποι χρησιμοποιούν ότι κάθε φορά σε μια στιγμή κολλάει επειδή, φυσικά, αυτό δεν είναι καλό. Στην πραγματικότητα, εάν έχετε ένα τηλέφωνο Android ή το iPhone και να κατεβάσετε εφαρμογές αυτές τις μέρες, αν είχατε ποτέ μια εφαρμογή μόλις σταματήσουν το κάπνισμα, ξαφνικά εξαφανίζεται, αυτό είναι σχεδόν πάντα το αποτέλεσμα κάποιας μνήμης που σχετίζονται με το θέμα, σύμφωνα με την οποία ο προγραμματιστής σκάτωσε και αναχθούν ένα δείκτη ότι αυτός ή αυτή δεν πρέπει να έχει, και το αποτέλεσμα του iOS ή Android είναι να σκοτώσει μόνο το πρόγραμμα συνολικά παρά τον κίνδυνο απροσδιόριστη συμπεριφορά ή κάποιου είδους συμβιβασμό της ασφάλειας. 

Υπάρχει ένα άλλο σφάλμα σε αυτό το πρόγραμμα, εκτός από αυτό. Τι άλλο έχω μαντάρα σε αυτό το πρόγραμμα; Δεν έχω ασκήσει ό, τι έχω κηρύξει. Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Καλή. Δεν έχω απελευθερωθεί η μνήμη. Έτσι, ο κανόνας του αντίχειρα σήμερα πρέπει να είναι ανά πάσα στιγμή να καλέσετε malloc, θα πρέπει να καλέσετε χωρίς χρέωση, όταν τελειώσετε με αυτή τη μνήμη. Τώρα, όταν θα θέλω να απελευθερώσετε αυτή τη μνήμη; Πιθανώς, παραδοχή αυτή η πρώτη γραμμή ήταν σωστή, θα ήθελα να το κάνω εδώ. Επειδή δεν μπορούσα, για παράδειγμα, να το κάνετε εδώ κάτω. Γιατί; Ακριβώς έξω από το πεδίο εφαρμογής. Έτσι ακόμα κι αν μιλάμε για δείκτες, αυτή την εβδομάδα είναι 2 ή 3 θέμα, όπου x είναι μόνο στο πεδίο εφαρμογής μέσα από τα άγκιστρα, όπου ανακηρύχθηκε. Έτσι, μπορείτε σίγουρα δεν μπορεί να το ελευθερώσουν. Μόνο ευκαιρία μου για να ελευθερώσετε είναι περίπου μετά την γραμμή 21. Αυτό είναι ένα αρκετά απλό πρόγραμμα? Ήταν αρκετά εύκολο μόλις το είδος του τυλιγμένο το μυαλό σας γύρω από αυτό το πρόγραμμα κάνει, όπου τα λάθη ήταν. Και ακόμα κι αν δεν το δείτε στο πρώτο, ελπίζω να είναι λίγο προφανές τώρα ότι αυτά τα λάθη αρκετά λυθεί εύκολα και πολύ εύκολο να γίνει. Αλλά όταν ένα πρόγραμμα είναι περισσότερο από 12 γραμμές καιρό, είναι 50 γραμμές μήκους 100 γραμμές καιρό, περπάτημα μέσω της γραμμής με τον κωδικό σας γραμμή, σκέφτεται λογικά μέσα από αυτό, είναι δυνατόν, αλλά δεν είναι ιδιαίτερα διασκεδαστικό να το κάνουμε, συνεχώς ψάχνει για σφάλματα, και είναι επίσης δύσκολο να γίνει, και γι 'αυτό ένα εργαλείο όπως το Valgrind υπάρχει. Επιτρέψτε μου να προχωρήσει και να το κάνετε αυτό: επιτρέψτε μου να ανοίξει παράθυρο τερματικού μου, και επιτρέψτε μου να μην τρέξει μόνο τη μνήμη, επειδή η μνήμη φαίνεται να είναι μια χαρά. Είμαι τυχερός να πάρει. Πηγαίνοντας στο εν λόγω επιπλέον byte στο τέλος της συστοιχίας δεν φαίνεται να είναι πολύ προβληματική. Αλλά επιτρέψτε μου, παρ 'όλα αυτά, κάνει έναν έλεγχο λογική, η οποία απλά σημαίνει να ελέγξετε αν αυτό δεν είναι πραγματικά σωστή. 

Ας κάνουμε valgrind-v - διαρροή-check = πλήρης, και στη συνέχεια το όνομα του προγράμματος σε αυτή την περίπτωση δεν είναι η μνήμη, a.out. Επιτρέψτε μου λοιπόν να προχωρήσει και να το κάνουμε αυτό. Πατήστε Enter. Θεέ μου. Αυτή είναι η έξοδος του, και αυτό είναι αυτό που προαναφέρθηκε. Αλλά, αν μπορείτε να μάθετε να διαβάσετε όλες τις ανοησίες εδώ, τα περισσότερα από αυτά είναι μόνο διαγνωστική έξοδος που δεν είναι τόσο ενδιαφέρουσα. Τι μάτι σας θέλει πραγματικά να είναι ψάχνει για οποιαδήποτε αναφορά σφάλματος ή άκυρο. Λέξεις που υποδηλώνουν προβλήματα. Και πράγματι, ας δούμε τι συμβαίνει λάθος εδώ κάτω. Έχω μια περίληψη κάποιου είδους, "σε χρήση στην έξοδο: 40. Bytes σε 1 μπλοκ" Δεν είμαι πραγματικά βέβαιος τι είναι ένα μπλοκ ακόμα, αλλά 40 bytes πραγματικά αισθάνεται σαν να μπορούσα να καταλάβω ότι όταν έρχεται από. 40 bytes. Γιατί είναι 40 bytes σε χρήση στην έξοδο; Και πιο συγκεκριμένα, αν μετακινηθείτε προς τα κάτω εδώ, γιατί έχω χάσει σίγουρα 40 bytes; Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Perfect. Ναι, ακριβώς. Υπήρχαν δέκα ακέραιοι, και κάθε ένα από αυτά είναι το μέγεθος των 4, ή 32 bits, έτσι έχω χάσει 40 bytes ακριβώς επειδή, όπως προτείνεται, δεν έχω που ονομάζεται δωρεάν. Αυτό είναι ένα bug, και τώρα ας δούμε τα κάτω λίγο περισσότερο και να δούμε δίπλα σε αυτό, "Άκυρο γράφουν μεγέθους 4." Τώρα, τι είναι αυτό; Αυτή η διεύθυνση εκφράζεται τι συμβολισμό βάσης, προφανώς; Αυτό είναι δεκαεξαδικό, και κάθε φορά που θα δείτε μια σειρά αρχίζοντας με 0x, αυτό σημαίνει δεκαεξαδικό, το οποίο κάναμε τον τρόπο πίσω το, νομίζω, το τμήμα 0 του PSET ερωτήσεων, η οποία ήταν μόνο για να κάνει μια άσκηση προθέρμανσης, τη μετατροπή δεκαδικό σε δεκαεξαδικό σε δυαδικό και ούτω καθεξής. Δεκαεξαδικό, μόνο από την ανθρώπινη συνθήκη, είναι συνήθως χρησιμοποιούνται για να αντιπροσωπεύσουν δείκτες ή, γενικότερα, διευθύνσεις. Είναι απλά μια σύμβαση, επειδή είναι λίγο πιο εύκολο να διαβάσει, είναι λίγο πιο συμπαγής από κάτι σαν δεκαδικό, και δυαδική είναι άχρηστο για τους περισσότερους ανθρώπους να χρησιμοποιούν. Και τώρα τι σημαίνει αυτό; Λοιπόν, φαίνεται σαν να υπάρχει μια έγκυρη εγγραφή μεγέθους 4 στη γραμμή 21 του memory.c. Ας πάμε πίσω στη γραμμή 21, και μάλιστα, εδώ είναι ότι άκυρη εγγραφή. Έτσι Valgrind δεν πρόκειται να κρατήσει εντελώς το χέρι μου και να μου πείτε ποια είναι η λύση είναι, αλλά ανιχνεύει ότι κάνω μια έγκυρη εγγραφή. Είμαι αγγίζοντας 4 byte ότι δεν θα πρέπει να είναι, και προφανώς αυτό είναι επειδή, όπως επεσήμανε, κάνω [10] αντί του [9] μέγιστη ή [0] ή κάτι στο μεταξύ. Με Valgrind, συνειδητοποιούν κάθε φορά που γράφεις τώρα ένα πρόγραμμα που χρησιμοποιεί δείκτες και χρησιμοποιεί μνήμη, και πιο συγκεκριμένα malloc, σίγουρα να πάρει τη συνήθεια να τρέχει αυτή τη μακρά αλλά πολύ εύκολα να αντιγραφεί και επικολληθεί εντολή του Valgrind για να δούμε αν υπάρχει κάποια λάθη εκεί. Και αυτό θα είναι συντριπτική κάθε φορά που θα δείτε την έξοδο, αλλά απλώς να αναλύσει μέσα από οπτικά το σύνολο της παραγωγής και να δούμε αν δείτε αναφέρει σφαλμάτων ή προειδοποιήσεις ή άκυρο ή χαθεί. Όποια από τις λέξεις που ακούγονται σαν να σκάτωσε κάπου. Έτσι αντιλαμβάνονται ότι είναι ένα νέο εργαλείο στην εργαλειοθήκη σας. 

Τώρα, τη Δευτέρα, είχαμε ένα σωρό λαοί έρχονται εδώ και αντιπροσωπεύουν την έννοια του συνδεδεμένη λίστα. Και εμείς εισήγαγε την συνδεδεμένη λίστα ως λύση σε ποιο το πρόβλημα; Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Καλή. Οι πίνακες δεν μπορούν να έχουν μνήμη προστεθούν σε αυτά. Αν ορίσουμε έναν πίνακα μεγέθους 10, αυτό είναι το μόνο που έχετε να πάρετε. Μπορείτε να καλέσετε μια συνάρτηση όπως realloc αν ονομάζεται αρχικά malloc, και ότι μπορεί να προσπαθήσει να αυξηθεί το συστοιχία αν υπάρχει χώρος προς το τέλος του ότι κανένας άλλος δεν χρησιμοποιεί, και αν δεν υπάρχει, απλά θα βρείτε ένα μεγαλύτερο κομμάτι κάπου αλλού. Αλλά τότε θα αντιγράψει όλα αυτά τα bytes στο νέο πίνακα. Αυτό ακούγεται σαν μια πολύ σωστή λύση. Γιατί είναι αυτή η ελκυστική; Θέλω να πω ότι δουλεύει, οι άνθρωποι έχουν λύσει αυτό το πρόβλημα. Γιατί πρέπει να το επιλύσουν τη Δευτέρα με συνδεδεμένες λίστες; Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Θα μπορούσε να πάρει πολύ χρόνο. Στην πραγματικότητα, κάθε φορά που καλείτε malloc ή realloc ή calloc, το οποίο είναι ένα ακόμα, κάθε φορά που το πρόγραμμα, μιλάμε για το λειτουργικό σύστημα, έχετε την τάση να επιβραδύνει το πρόγραμμα προς τα κάτω. Και αν κάνετε αυτά τα είδη των πραγμάτων σε βρόχους, είστε πραγματικά επιβράδυνση πράγματα κάτω. Δεν πρόκειται να παρατηρήσετε αυτό για την απλούστερη των "hello world" προγράμματα τύπου, αλλά σε πολύ μεγαλύτερα προγράμματα, ζητώντας από το λειτουργικό σύστημα ξανά και ξανά για τη μνήμη ή δίνοντας ξανά και ξανά δεν τείνει να είναι ένα καλό πράγμα. Πλέον, είναι ακριβώς το είδος της πνευματικά - είναι ένα πλήρες χάσιμο χρόνου. Γιατί να διαθέσουν όλο και περισσότερη μνήμη, ο κίνδυνος αντιγραφή τα πάντα στη νέα σειρά, εάν έχετε μια εναλλακτική λύση που σας επιτρέπει να διαθέτουν μόνο τόσο πολύ μνήμη, όπως μπορείτε πραγματικά ανάγκη; Έτσι, υπάρχει συν και τα πλην εδώ. Ένα από τα συν είναι ότι τώρα έχουμε δυναμισμό. Δεν έχει σημασία, όπου τα κομμάτια της μνήμης είναι ότι είναι δωρεάν, Μπορώ απλώς να ταξινομήσετε τη δημιουργία αυτών των ψίχουλα ψωμιού μέσω δείκτες να πλέκετε όλη συνδεδεμένη λίστα μου μαζί. Αλλά μπορώ να πληρώσω τουλάχιστον μία τιμή. 

Τι πρέπει να εγκαταλείψουν στην απόκτηση συνδεδεμένες λίστες; Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Καλή. Χρειάζεται περισσότερη μνήμη. Τώρα χρειάζονται χώρο για αυτούς τους δείκτες, και στην περίπτωση αυτού του σούπερ συνδέονται απλή λίστα Αυτός είναι ο μόνος που προσπαθεί να αποθηκεύουν ακέραιους αριθμούς, που είναι 4 bytes, συνεχίζουμε να λέμε καλά, ένας δείκτης είναι 4 bytes, οπότε τώρα έχω κυριολεκτικά διπλασιαστεί η ποσότητα της μνήμης που χρειάζεται μόνο για να αποθηκεύσετε αυτή τη λίστα. Αλλά και πάλι, αυτό είναι μια συνεχής συμβιβασμός στην επιστήμη των υπολογιστών μεταξύ του χρόνου και του χώρου και την ανάπτυξη, την προσπάθεια και άλλους πόρους. Τι είναι ένα άλλο μειονέκτημα του χρησιμοποιώντας μια συνδεδεμένη λίστα; Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Καλή. Δεν είναι τόσο εύκολη η πρόσβαση. Μπορούμε πλέον να μόχλευσης εβδομάδα 0 αρχές, όπως διαίρει και βασίλευε. Και πιο συγκεκριμένα, δυαδική αναζήτηση. Διότι ακόμα κι αν εμείς οι άνθρωποι μπορεί να δει περίπου όπου η μέση του καταλόγου αυτού είναι, ο υπολογιστής ξέρει μόνο ότι αυτή η συνδεδεμένη λίστα ξεκινά στη διεύθυνση που ονομάζεται πρώτη. Και αυτό είναι 0x123 ή κάτι τέτοιο. Και ο μόνος τρόπος για το πρόγραμμα μπορείτε να βρείτε το μεσαίο στοιχείο είναι να ψάξει πραγματικά όλη τη λίστα. Και ακόμα και τότε, δεν έχει κυριολεκτικά να ψάξετε ολόκληρη τη λίστα, επειδή ακόμα και τη στιγμή που θα φτάσει το μεσαίο στοιχείο, ακολουθώντας τους δείκτες, σας, το πρόγραμμα, δεν έχουν ιδέα πόσο καιρό αυτή η λίστα είναι, δυνητικά, μέχρι να χτυπήσει το τέλος του, και πώς ξέρετε προγραμματισμού ότι είστε στο τέλος μιας συνδεδεμένη λίστα; Υπάρχει ένα ειδικό δείκτη NULL, οπότε και πάλι, μια σύμβαση. Αντί να χρησιμοποιήσετε αυτό το δείκτη, εμείς σίγουρα δεν θέλουμε να είναι κάποια αξία σκουπίδια δείχνοντας εκτός σκηνής κάπου? θέλουμε να είναι το χέρι προς τα κάτω, NULL, έτσι ώστε να έχουμε αυτό το τέρμα σε αυτή τη δομή των δεδομένων έτσι ώστε να γνωρίζουν πού τελειώνει. 

Τι γίνεται αν θέλουμε να χειριστείτε αυτό; Κάναμε το μεγαλύτερο μέρος αυτής της οπτικής, και με τους ανθρώπους, αλλά τι γίνεται αν θέλουμε να κάνουμε μια εισαγωγή; Έτσι ο αρχικός κατάλογος ήταν 9, 17, 20, 22, 29, 34. Τι θα συμβεί αν έχουμε συνέχεια θέλησε να malloc χώρο για τον αριθμό 55, ένας κόμβος για αυτό, και στη συνέχεια θέλουμε να εισάγετε 55 στη λίστα ακριβώς όπως κάναμε τη Δευτέρα; Πώς θα το κάνουμε αυτό; Λοιπόν, Ανίτα ήρθε και μπήκε ουσιαστικά τη λίστα. Ξεκίνησε στο πρώτο στοιχείο, τότε το επόμενο, το επόμενο, το επόμενο, το επόμενο, το επόμενο. Τέλος, χτύπησε το αριστερό χέρι σε όλη τη διαδρομή και συνειδητοποίησα OH, αυτό είναι NULL. Έτσι, αυτό που χειραγώγησης δείκτη έπρεπε να γίνει; Το άτομο που ήταν στο τέλος, αριθμός 34, απαιτείται το αριστερό του χέρι ανέκυψαν να επισημάνω σε 55, 55 χρειάζεται το αριστερό χέρι τους προς τα κάτω για να είναι ο νέος NULL τερματισμού. Τέλος. Αρκετά εύκολο να εισάγετε 55 σε μια ταξινομημένη λίστα. Και πώς θα μπορούσε αυτή η ματιά; 

Επιτρέψτε μου να προχωρήσει και να ανοίξει κάποιο παράδειγμα κώδικα εδώ. Θα ανοίξει το gedit, και επιτρέψτε μου να ανοίξει δύο αρχεία πρώτα. Το ένα είναι list1.h, και επιτρέψτε μου να υπενθυμίσω ότι αυτό ήταν το κομμάτι του κώδικα ότι χρησιμοποιείται για να αντιπροσωπεύει έναν κόμβο. Ένας κόμβος έχει και έναν int n ονομάζεται και ένα δείκτη που ονομάζεται επόμενο ότι μόνο τα σημεία για το επόμενο πράγμα στη λίστα. Αυτό είναι τώρα σε ένα αρχείο. H. Γιατί; Υπάρχει αυτή η σύμβαση, και δεν έχουν επωφεληθεί από αυτό το τεράστιο ποσό τους εαυτούς μας, αλλά το πρόσωπο που έγραψε printf και άλλες λειτουργίες έδωσε ως δώρο στον κόσμο όλες αυτές τις λειτουργίες, γράφοντας ένα αρχείο με όνομα stdio.h. Και έπειτα υπάρχει string.h, και στη συνέχεια υπάρχει map.h, και υπάρχει όλα αυτά τα αρχεία h ότι μπορεί να έχετε δει ή να χρησιμοποιηθούν κατά τη διάρκεια γραμμένα από άλλους ανθρώπους. Συνήθως σε αυτές. H αρχεία είναι μόνο πράγματα όπως typedefs ή δηλώσεις των προσαρμοσμένων τύπων ή δηλώσεις σταθερές. Δεν τίθεται υλοποιήσεις λειτουργίες »στα αρχεία κεφαλίδας. Βάζετε, αντί απλώς πρωτοτύπων τους. Θα βάλει τα πράγματα που θέλετε να μοιραστείτε με τον κόσμο αυτό που χρειάζονται Για να υπολογίσουν τον κωδικό τους. Έτσι, μόνο και μόνο για να μπει σε αυτή τη συνήθεια, αποφασίσαμε να κάνουμε το ίδιο πράγμα. Δεν υπάρχει πολύ σε list1.h, αλλά έχουμε βάλει κάτι που θα μπορούσε να ενδιαφέρει τους ανθρώπους του κόσμου που θέλετε να χρησιμοποιήσετε την εφαρμογή συνδεδεμένη λίστα μας. Τώρα, σε list1.c, δεν θα περάσει μέσα από όλο αυτό το πράγμα επειδή είναι λίγο καιρό, αυτό το πρόγραμμα, αλλά ας τρέξει πραγματικά γρήγορα στη γραμμή εντολών. Επιτρέψτε μου να συγκεντρώνουν κατάλογο1, επιτρέψτε μου να τρέξει τότε κατάλογο1, και αυτό που θα δείτε είναι προσομοίωση έχουμε ένα απλό μικρό πρόγραμμα εδώ που πρόκειται να μου επιτρέψετε να προσθέσετε και να καταργήσετε τους αριθμούς σε μια λίστα. Επιτρέψτε μου λοιπόν να προχωρήσουμε και πληκτρολογήστε 3 για την 3 η επιλογή του μενού. Θέλω να εισαγάγετε τον αριθμό - ας κάνουμε το πρώτο νούμερο, το οποίο ήταν 9, και τώρα είμαι είπε ο κατάλογος είναι τώρα 9. Επιτρέψτε μου να προχωρήσει και να κάνει μια άλλη εισαγωγή, έτσι χτύπησα μενού 3. Τι αριθμό μπορώ να θέλετε να εισάγετε; 17. Enter. Και θα το κάνω μόνο ένα περισσότερο. Επιτρέψτε μου να εισάγετε τον αριθμό 22. Έτσι, έχουμε τις απαρχές της συνδεδεμένη λίστα που είχαμε σε μορφή διαφανειών πριν από λίγο. Πώς είναι αυτή η παρεμβολή πραγματικά συμβαίνει; Πράγματι, είναι τώρα 22 στο τέλος της λίστας. Έτσι, η ιστορία που είπε στη σκηνή τη Δευτέρα και ανακεφαλαίωσε μόλις τώρα Πρέπει πραγματικά να συμβαίνει στον κώδικα. Ας ρίξουμε μια ματιά. Επιτρέψτε μου να μετακινηθείτε προς τα κάτω σε αυτό το αρχείο. Θα gloss πάνω από ορισμένες από τις λειτουργίες, αλλά θα πάμε κάτω, ας πούμε, η λειτουργία ένθετο. 

Ας δούμε πώς θα προχωρήσουμε σχετικά με την εισαγωγή ενός νέου κόμβου σε αυτή την συνδεδεμένη λίστα. Πού είναι η λίστα δήλωσε; Λοιπόν, ας μετακινηθείτε σε όλη τη διαδρομή μέχρι την κορυφή, και παρατηρήστε ότι συνδεδεμένη λίστα μου είναι ουσιαστικά δηλώνονται ως ένα ενιαίο δείκτη που είναι αρχικά NULL. Έτσι είμαι χρησιμοποιώντας μια καθολική μεταβλητή εδώ, το οποίο σε γενικές γραμμές έχουμε κηρύξει κατά διότι καθιστά τον κωδικό σας λίγο ακατάστατη να διατηρήσει, Είναι το είδος της τεμπέλης, συνήθως, αλλά αυτό δεν είναι τεμπέλης και δεν είναι λάθος και δεν είναι κακό αν μοναδικός σκοπός του προγράμματός σας στη ζωή είναι να προσομοιώσει μία συνδεδεμένη λίστα. Ποια είναι ακριβώς αυτό που κάνουμε. Έτσι, αντί να το δηλώσει στην κύρια και στη συνέχεια πρέπει να περάσει σε κάθε λειτουργία έχουμε γράψει σε αυτό το πρόγραμμα, αντί να συνειδητοποιήσουμε OH, ας κάνει το παγκόσμιο επειδή όλος ο σκοπός του προγράμματος αυτού είναι να παρουσιάσει μία και μόνο μία συνδεδεμένη λίστα. Έτσι, αυτό αισθάνεται εντάξει. Εδώ είναι πρωτότυπα μου, και δεν θα περάσουν από όλα αυτά, αλλά έγραψα μια λειτουργία διαγραφής, μια λειτουργία της αναζήτησης, μια λειτουργία ένθετο, και μια λειτουργία τραβέρσα. Αλλά ας πάμε τώρα πίσω στη λειτουργία ένθετο και να δούμε πώς αυτό λειτουργεί εδώ. Εισαγωγή είναι on line - εδώ πάμε. Εισαγωγή. Γι 'αυτό δεν παίρνει κανένα όρισμα, επειδή θα πάμε να ρωτήσω ο χρήστης μέσα από αυτή τη λειτουργία για τον αριθμό που θέλετε να εισαγάγετε. Αλλά πρώτα, ετοιμαζόμαστε να τους δώσουμε λίγο χώρο. Αυτό είναι το είδος αντιγραφή και επικόλληση από το άλλο παράδειγμα. Σε αυτή την περίπτωση, θα όριζαν ένα int? Αυτή τη φορά είμαστε κατανομή ενός κόμβου. Πραγματικά, δεν θυμάμαι πόσα bytes είναι ένας κόμβος, αλλά αυτό είναι εντάξει. Sizeof μπορεί να καταλάβει ότι για μένα. Και γιατί είμαι ο έλεγχος για NULL στη γραμμή 120; Τι θα μπορούσε να πάει στραβά στη γραμμή 119; Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Καλή. Απλά θα μπορούσε να είναι η περίπτωση που έχω ζητήσει πάρα πολύ μνήμη ή κάτι δεν πάει καλά και το λειτουργικό σύστημα δεν έχει αρκετά bytes να μου δώσει, γι 'αυτό σηματοδοτεί τόσο από την επιστροφή NULL, και αν δεν ελέγξετε ότι και εγώ απλά τυφλά προβεί σε χρήση η διεύθυνση που επιστρέφεται, θα μπορούσε να είναι NULL. Θα μπορούσε να είναι κάποια άγνωστη τιμή? Δεν είναι ένα καλό πράγμα εάν εγώ - στην πραγματικότητα δεν θα είναι μια άγνωστη τιμή. Θα μπορούσε να είναι NULL, έτσι δεν θέλω για να την καταχραστούν και να διακινδυνεύσει εύρεση τιμών. Αν συμβεί αυτό, θα ήθελα απλώς να επιστρέψετε και θα προσποιηθώ όπως δεν είχα πάρει πίσω κάποια μνήμη καθόλου. 

Σε αντίθετη περίπτωση, λέω ο χρήστης να μου δώσει έναν αριθμό για να εισάγετε, καλώ παλιά GetInt φίλος μας, και στη συνέχεια αυτή ήταν η νέα σύνταξη εισαγάγαμε τη Δευτέρα. «Newptr-> n 'σημαίνει αναλάβει την διεύθυνση που σας δόθηκε από την malloc που αντιπροσωπεύει το πρώτο byte ενός νέου αντικειμένου κόμβο, και στη συνέχεια, μεταβείτε στο πεδίο που ονομάζεται n. Ένα μικρό trivia ερώτηση: Αυτό είναι ισοδύναμο με το τι πιο αινιγματικό γραμμή κώδικα; Πώς αλλιώς θα μπορούσα να έχω γράψει αυτό; Θέλετε να πάρετε μια μαχαιριά; [Απάντηση Φοιτητής, ακατάληπτο] Καλή. Χρησιμοποιώντας το. N, αλλά δεν είναι αρκετά τόσο απλό όσο αυτό. Τι θα πρέπει πρώτα να κάνετε; [Απάντηση Φοιτητής, ακατάληπτο] Καλή. Πρέπει να κάνω * newptr.n. Έτσι, αυτό που λέει νέο δείκτη είναι προφανώς μια διεύθυνση. Γιατί; Επειδή επέστρεψε από malloc. Η newptr * λέγοντας «πάμε εκεί», και στη συνέχεια, όταν είστε εκεί, τότε μπορείτε να χρησιμοποιήσετε την πιο οικεία. n, αλλά αυτό φαίνεται λίγο άσχημο, ειδικά αν εμείς οι άνθρωποι πρόκειται να επιστήσει δείκτες με βέλη όλη την ώρα? ο κόσμος έχει τυποποιηθεί σε αυτό το συμβολισμό βέλος, το οποίο κάνει ακριβώς το ίδιο πράγμα. Έτσι, μπορείτε να χρησιμοποιήσετε μόνο το -> συμβολισμό όταν το πράγμα στα αριστερά είναι ένας δείκτης. Διαφορετικά, αν είναι μια πραγματική struct, χρησιμοποιήστε το. N. Και τότε αυτό: Γιατί μπορώ να προετοιμαστεί newptr-> δίπλα στο NULL; Δεν θέλουμε ένα κουνάμε το αριστερό χέρι μακριά από το τέλος του σταδίου. Θέλουμε να κοιτάνε προς τα κάτω, πράγμα που σημαίνει το τέλος αυτής της λίστας θα μπορούσε ενδεχομένως να είναι σε αυτόν τον κόμβο, γι 'αυτό καλύτερα να βεβαιωθείτε ότι είναι NULL. Και, σε γενικές γραμμές, την αρχικοποίηση μεταβλητών δεδομένων σας ή τα μέλη σας και structs να είναι κάτι απλά καλή πρακτική. Απλά να αφήσει σκουπίδια υπάρχουν και συνεχίζουν να υπάρχουν γενικά σας παίρνει σε μπελάδες αν ξεχάσετε να κάνετε κάτι αργότερα. 

Εδώ είναι μερικές περιπτώσεις. Αυτό, πάλι, είναι η λειτουργία ενθέτου, και το πρώτο πράγμα που μπορώ να ελέγξω για το αν είναι μεταβλητή που ονομάζεται κατ 'αρχάς, ότι η παγκόσμια μεταβλητή είναι NULL, αυτό σημαίνει ότι δεν υπάρχει συνδεδεμένη λίστα. Δεν έχουν εισαχθεί οποιουσδήποτε αριθμούς, γι 'αυτό είναι ασήμαντο για να εισάγετε τον αριθμό αυτό το ρεύμα στον κατάλογο, διότι ανήκει ακριβώς στην αρχή της λίστας. Έτσι, αυτό ήταν όταν ήταν μόλις Anita όρθιος μόνος εδώ, προσποιούμενος κανείς άλλος δεν ήταν μέχρι εδώ πάνω στη σκηνή μέχρι να διατεθεί ένα κόμβο, τότε θα μπορούσε να σηκώσει το χέρι της για πρώτη φορά, αν όλοι οι άλλοι είχαν καταλήξει στη σκηνή μετά την Δευτέρα. Τώρα, εδώ, αυτό είναι ένα μικρό έλεγχο όπου έχω να πω αν η αξία του νέου κόμβου του n είναι <η τιμή του η στην τρέχουσα πρώτο κόμβο, αυτό σημαίνει ότι υπάρχει μία συνδεδεμένη λίστα που είναι αρχίσει. Υπάρχει τουλάχιστον ένας κόμβος στη λίστα, αλλά αυτό το νέο τύπο ανήκει πριν, έτσι πρέπει να κινηθούν τα πράγματα γύρω. Με άλλα λόγια, αν η λίστα έχει ξεκινήσει με απλά, ας πούμε, μόνο ο αριθμός 17, που είναι το - στην πραγματικότητα, μπορούμε να το κάνουμε αυτό πιο καθαρά. Αν αρχίσουμε την ιστορία μας με ένα δείκτη που ονομάζεται εδώ πρώτα, και αρχικά είναι NULL, και εισάγετε τον αριθμό 9, ο αριθμός 9 ανήκει σαφώς κατά την έναρξη της λίστας. Ας προσποιηθούμε ότι malloced απλά τη διεύθυνση ή τον αριθμό 9 και το βάζουμε εδώ. Αν το πρώτο είναι 9 από προεπιλογή, το πρώτο σενάριο που συζητήθηκε σημαίνει ακριβώς το σημείο ας αυτός ο τύπος εδώ, αφήστε αυτό ως NULL? τώρα έχουμε τον αριθμό 9. Ο επόμενος αριθμός που θέλετε να εισαγάγετε είναι 17. 17 ανήκει εδώ, έτσι θα πάμε να χρειαστεί να κάνετε κάποια λογική εντατικοποίηση μέσα από αυτό. Ας αντ 'αυτού, πριν το κάνουμε αυτό, ας προσποιηθούμε ότι θέλαμε να εισάγετε τον αριθμό 8. 

Έτσι, μόνο για λόγους ευκολίας, εγώ είμαι πρόκειται να συντάξουν εδώ. Αλλά θυμηθείτε, malloc να το βάλετε πιο οπουδήποτε. Αλλά για χάρη του σχεδίου, εγώ θα το πω εδώ. Έτσι έχω προσποιηθεί διατίθενται μόνο έναν κόμβο για τον αριθμό 8? Αυτό είναι NULL από προεπιλογή. Τι πρέπει να συμβεί τώρα; Ένα ζευγάρι από τα πράγματα. Κάναμε αυτό το λάθος στη σκηνή τη Δευτέρα, όπου θα ενημερώνεται ένα δείκτη, όπως αυτό, τότε το έκανε αυτό, και στη συνέχεια ισχυρίστηκε - ορφανά που όλοι οι άλλοι πάνω στη σκηνή. Επειδή εσείς can't - η σειρά των εργασιών είναι σημαντικό εδώ, γιατί τώρα έχουμε χάσει αυτό το κόμβο 9 που είναι ακριβώς το είδος των επιπλέουν στο διάστημα. Έτσι, αυτό δεν ήταν η σωστή προσέγγιση, τη Δευτέρα. Θα πρέπει πρώτα να κάνουμε κάτι άλλο. Η κατάσταση του κόσμου μοιάζει με αυτό. Αρχικά, 8 έχει διατεθεί. Τι θα ήταν ένας καλύτερος τρόπος για την εισαγωγή των 8; Αντί για την ενημέρωση αυτού του δείκτη πρώτα ενημερώσει μόνο αυτό το ένα εδώ αντ 'αυτού. Έτσι, χρειαζόμαστε μια γραμμή κώδικα που πρόκειται να μετατρέψει αυτό το χαρακτήρα NULL σε ένα πραγματικό δείκτη που είναι δείχνοντας στον κόμβο 9, και τότε μπορούμε με ασφάλεια να αλλάξετε πρώτα να επισημάνω σε αυτόν τον τύπο εδώ. Τώρα έχουμε μια λίστα, μια συνδεδεμένη λίστα, από δύο στοιχεία. Και τι σημαίνει αυτό πραγματικά μοιάζει εδώ; Αν κοιτάξουμε τον κώδικα, παρατηρώ ότι έχω κάνει ακριβώς αυτό. Έχω πει newptr, και σε αυτή την ιστορία, newptr έδειχνε σε αυτόν τον τύπο. 

Έτσι, επιτρέψτε μου να επιστήσω κάτι ακόμα, και θα έπρεπε να είχα μείνει λίγο περισσότερο χώρο για αυτό. Έτσι συγχωρήσει το μικροσκοπικό μικρό σχέδιο. Αυτός ο τύπος ονομάζεται newptr. Αυτή είναι η μεταβλητή που κήρυξε λίγες γραμμές νωρίτερα, στη γραμμή - λίγο πάνω από 25. Και αυτό είναι που δείχνουν προς 8. Έτσι, όταν λέω newptr-> επόμενο, αυτό σημαίνει ότι πηγαίνετε στο struct Αυτό είναι που υποδεικνύεται από newptr, έτσι είμαστε εδώ, πηγαίνετε εκεί. Στη συνέχεια, το βέλος που λέει να πάρει το επόμενο πεδίο, και στη συνέχεια το = λέει ό, τι βάλει αξία εκεί; Η τιμή αυτή ήταν το πρώτο? Τι αξία ήταν στην πρώτη; Πρώτη έδειχνε σε αυτόν τον κόμβο, έτσι αυτό σημαίνει ότι αυτό πρέπει τώρα να επισημάνω σε αυτό το κόμβο. Με άλλα λόγια, ό, τι φαίνεται όμως ένα γελοίο χάος με τη γραφή μου, τι είναι μια απλή ιδέα του απλά μετακινώντας τα βέλη γύρω από μεταφράζεται σε κώδικα με ακριβώς αυτή επένδυση ένα. Φυλάσσεται τι είναι στην πρώτη στο επόμενο πεδίο και στη συνέχεια να επικαιροποιεί τι πρώτη είναι στην πραγματικότητα. Ας πάμε μπροστά και fast-forward μέσω μερικών από αυτά, και να εξετάσουμε μόνο σε αυτό το εισαγωγή ουρά για τώρα. Ας υποθέσουμε ότι έχω φτάσει στο σημείο όπου θεωρώ ότι το επόμενο πεδίο κάποιου κόμβου είναι NULL. Και σε αυτό το σημείο στην ιστορία, μια λεπτομέρεια που είμαι συγκαλύπτουμε είναι ότι έχω εισήγαγε ένα άλλο δείκτη μέχρι εδώ στην γραμμή 142, δείκτης ο προκάτοχός. Ουσιαστικά, σε αυτό το σημείο στην ιστορία, αφού η λίστα παίρνει μεγάλη, Ι το είδος πρέπει να περπατήσει με τα δύο δάχτυλα, γιατί αν πάω πολύ μακριά, θυμάμαι σε ένα ενιαίο μήκους λίστα, δεν μπορείτε να πάτε προς τα πίσω. Έτσι, αυτή η ιδέα του predptr είναι το αριστερό μου δάχτυλο, και newptr - δεν newptr. Ένας άλλος δείκτης που είναι εδώ είναι άλλο δάχτυλο μου, και είμαι ακριβώς το είδος της τη λίστα με τα πόδια. Γι 'αυτό ότι υπάρχει. Αλλά ας αναλογιστούμε μόνο μία από τις απλούστερες περιπτώσεις εδώ. Αν επόμενο πεδίο της εν λόγω δείκτης είναι NULL, ποια είναι η λογική συνέπεια; Αν διέρχονται από αυτή τη λίστα και να χτυπήσει ένα NULL δείκτη; Είστε στο τέλος της λίστας, και έτσι ο κώδικας για να προσθέσετε τότε αυτό ένα πρόσθετο στοιχείο είναι το είδος της διαισθητικής θα λάβουν την επόμενη κόμβος των οποίων ο δείκτης είναι NULL, έτσι αυτό είναι σήμερα NULL, και να αλλάξει αυτό, όμως, να είναι η διεύθυνση του νέου κόμβου. Έτσι, είμαστε μόλις στην κατάρτιση κώδικα το βέλος που είχαμε στη σκηνή με την αύξηση αριστερό χέρι κάποιου. 

Και στην περίπτωση που θα κυματίσει τα χέρια μου σε προς το παρόν, μόνο και μόνο επειδή νομίζω ότι είναι εύκολο να χαθεί, όταν το κάνουμε σε αυτό το είδος του περιβάλλοντος, ελέγχει για εισαγωγή στο μέσο της λίστας. Αλλά μόνο διαισθητικά, τι πρέπει να συμβεί, αν θέλετε να υπολογίσετε όπου κάποιος αριθμός ανήκει στη μέση είναι εσείς πρέπει να το περπατήσετε με περισσότερα από ένα δάχτυλο, περισσότερα από ένα δείκτη, καταλάβω, όπου ανήκει από έλεγχο είναι το στοιχείο <η σημερινή, > Το σημερινό, και τη στιγμή που θα βρείτε αυτό το μέρος, τότε θα πρέπει να κάνετε αυτό το είδος του παιχνιδιού κέλυφος, όπου μπορείτε να μετακινήσετε τους δείκτες γύρω από πολύ προσεκτικά. Και η απάντηση, αν θέλετε να τον λόγο μέσα από αυτό στο σπίτι με δική σας, βράζει κάτω ακριβώς σε αυτές τις δύο γραμμές κώδικα, αλλά η σειρά αυτών των γραμμών είναι εξαιρετικά σημαντικό. Γιατί αν πέσει το χέρι κάποιου και να αυξήσει κάποιος άλλος είναι σε λάθος σειρά, και πάλι, θα μπορούσατε να καταλήξετε ορφανού τη λίστα. Για να συνοψίσουμε περισσότερο εννοιολογικά, η εισαγωγή στην ουρά είναι σχετικά απλή. Η εισαγωγή στο κεφάλι είναι επίσης σχετικά απλή, αλλά θα πρέπει να ενημερώσετε ένα πρόσθετο δείκτη αυτή τη φορά να αποσπάσουν τον αριθμό 5 στην λίστα εδώ, και στη συνέχεια την εισαγωγή στο μέσον περιλαμβάνει ακόμη μεγαλύτερη προσπάθεια, με πολύ προσεκτικά εισάγετε τον αριθμό 20 στην σωστή θέση του, η οποία είναι μεταξύ 17 και 22. Έτσι πρέπει να κάνουμε κάτι σαν να έχει το νέο σημείο κόμβο 20 έως 22, και, στη συνέχεια, δείκτης που κόμβου θα πρέπει να ενημερώνεται το τελευταίο; Είναι 17, για την εισαγωγή στην πραγματικότητα. Έτσι, και πάλι, εγώ θα αναβάλει την πραγματική κώδικα για τη συγκεκριμένη εφαρμογή. 

Με την πρώτη ματιά, είναι λίγο συντριπτική, αλλά είναι πραγματικά ακριβώς ένα άπειρο βρόχο Αυτό είναι looping, looping, looping, looping, και το σπάσιμο μόλις χτυπήσει το NULL δείκτη, σημείο στο οποίο μπορείτε να κάνετε την απαραίτητη εισαγωγή. Αυτό, λοιπόν, είναι αντιπροσωπευτική συνδέονται κώδικα εισαγωγής λίστα. Αυτό ήταν το είδος του πολύ, και αισθάνεται σαν έχουμε λύσει ένα πρόβλημα, αλλά έχουμε εισαγάγει μια ολόκληρη άλλη. Ειλικρινά, έχουμε περάσει όλο αυτό το διάστημα O στις μεγάλες και Ω και χρόνο λειτουργίας, προσπαθεί να λύσει τα προβλήματα πιο γρήγορα, και εδώ κάνουμε ένα μεγάλο βήμα προς τα πίσω, αισθάνεται. Και όμως, αν ο στόχος είναι η αποθήκευση δεδομένων, αισθάνεται σαν το Άγιο Δισκοπότηρο, όπως δήλωσε τη Δευτέρα, θα είναι πραγματικά να αποθηκεύουν τα πράγματα αμέσως. 

Στην πραγματικότητα, ας υποθέσουμε ότι κάναμε βάλει στην άκρη συνδεδεμένη λίστα για μια στιγμή και εισήγαγε την έννοια αντί ενός πίνακα. Και ας σκεφτούμε ένα τραπέζι για μια στιγμή ως μια σειρά. Αυτός ο πίνακας και η υπόθεση αυτή έχει εδώ 26 περίπου στοιχεία, από 0 έως 25, και ας υποθέσουμε ότι έχετε ανάγκη από κάποιο κομμάτι της αποθήκευσης για τα ονόματα: Alice και ο Bob και ο Τσάρλι και τα παρόμοια. Και θα πρέπει να έχετε κάποια δομή δεδομένων για την αποθήκευση αυτών των ονομάτων. Λοιπόν, μπορείτε να χρησιμοποιήσετε κάτι σαν μια συνδεδεμένη λίστα και μπορείτε να περπατήσετε τη λίστα πριν από την εισαγωγή Alice Bob και ο Τσάρλι, μετά τον Bob και ούτω καθεξής. Και, στην πραγματικότητα, αν θέλετε να δείτε τον κώδικα, όπως ότι ένα μέρος, Γνωρίζουμε ότι σε list2.h, κάνουμε ακριβώς αυτό. Εμείς δεν θα περάσει μέσα από αυτόν τον κώδικα, αλλά αυτό είναι μία παραλλαγή του πρώτου παραδείγματος που εισάγει ένα άλλο struct έχουμε ξαναδεί ονομάζεται φοιτητής, και στη συνέχεια ό, τι στην πραγματικότητα αποθηκεύει στην συνδεδεμένη λίστα είναι ένας δείκτης σε μια δομή φοιτητή μάλλον παρά μια απλή μικρή ακέραιος, n. Έτσι, συνειδητοποιούν ότι υπάρχει κώδικας εκεί που περιλαμβάνει την πραγματική χορδές, αλλά αν ο στόχος στο χέρι πραγματικά τώρα είναι να αντιμετωπιστεί το πρόβλημα της αποτελεσματικότητας, Δεν θα ήταν ωραίο αν μας δίνεται ένα αντικείμενο που ονομάζεται Alice, θέλουμε να την βάλει στη σωστή θέση σε μια δομή δεδομένων, αισθάνεται όπως θα ήθελα να είναι πραγματικά ωραίο να τεθεί μόνο Alice, του οποίου το όνομα αρχίζει με Α, στην πρώτη θέση. Και ο Μπομπ, του οποίου το όνομα αρχίζει με το Β, στην δεύτερη θέση. Με μια σειρά, ή ας αρχίσουμε καλώντας το ένα τραπέζι, ένα πίνακα κατακερματισμού στο ότι, μπορούμε να κάνουμε ακριβώς αυτό. Αν μας δίνεται ένα όνομα σαν την Αλίκη, μια σειρά σαν την Αλίκη, όπου βάζετε ένα-λ-ι-γ-ε; Χρειαζόμαστε μια hueristic. Χρειαζόμαστε μια λειτουργία για να λάβει κάποια στοιχεία σαν την Αλίκη και να επιστρέψει μια απάντηση, "Alice Βάλτε σε αυτή τη θέση." Και αυτή η λειτουργία, αυτό το μαύρο κουτί, θα πρέπει να ονομάζεται συνάρτηση κατακερματισμού. 

Μια συνάρτηση κατακερματισμού είναι κάτι που παίρνει μια είσοδο, όπως το "Alice", και επιστρέφει σε εσάς, συνήθως, η αριθμητική θέση σε κάποια δομή δεδομένων όπου ανήκει Alice. Σε αυτή την περίπτωση, συνάρτηση κατακερματισμού μας θα πρέπει να είναι σχετικά απλή. Hash λειτουργία μας πρέπει να πω, αν σας δίνεται "Alice", το οποίο χαρακτήρας θα πρέπει να με νοιάζει; Το πρώτο. Έτσι κοιτάζω [0], και στη συνέχεια να πω αν [0] χαρακτήρας είναι ένα, επιστρέφει τον αριθμό 0. Αν είναι Β, επιστρέφει 1. Αν C είναι, επιστρέφει 2, και ούτω καθεξής. Όλα δείκτη 0, και ότι θα μου επιτρέψετε να εισάγετε Alice και ο Bob, στη συνέχεια και στη συνέχεια Charlie και ούτω καθεξής σε αυτή τη δομή δεδομένων. Αλλά υπάρχει ένα πρόβλημα. Τι θα συμβεί αν Anita έρχεται και πάλι; Πού βάζουμε Anita; Το όνομά της, πάρα πολύ, αρχίζει με το γράμμα Α, και αισθάνεται σαν έχουμε κάνει ένα ακόμη μεγαλύτερο χάος από αυτό το πρόβλημα. Έχουμε τώρα άμεση εισαγωγή, συνεχή εισαγωγή του χρόνου, σε μια δομή δεδομένων παρά στη χειρότερη περίπτωση γραμμική, αλλά τι μπορούμε να κάνουμε με την Anita σε αυτή την περίπτωση; Ποιες είναι οι δύο επιλογές, πραγματικά; Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Εντάξει, έτσι θα μπορούσαμε να έχουμε μια άλλη διάσταση. Αυτό είναι καλό. Έτσι μπορούμε να οικοδομήσουμε τα πράγματα σε 3D, όπως μιλήσαμε προφορικά τη Δευτέρα. Θα μπορούσαμε να προσθέσετε μια άλλη πρόσβαση εδώ, αλλά ας υποθέσουμε ότι δεν υπάρχει, είμαι προσπαθεί να κρατήσει το απλό. Το σύνολο στόχος εδώ είναι να έχουμε άμεση σταθερό χρόνο πρόσβασης, έτσι ώστε να είναι η προσθήκη πάρα πολύ περίπλοκο. Ποιες είναι οι άλλες επιλογές, όταν προσπαθείτε να εισαγάγετε Anita σε αυτή τη δομή δεδομένων; Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Καλή. Έτσι, θα μπορούσαμε να προχωρήσουμε όλοι οι άλλοι κάτω, όπως Charlie nudges κάτω Bob και η Alice, και στη συνέχεια βάζουμε Anita όπου θέλει πραγματικά να είναι. 

Φυσικά, τώρα, υπάρχει μια παρενέργεια αυτού. Αυτή η δομή δεδομένων είναι μάλλον χρήσιμο όχι επειδή θέλουμε να εισάγετε τους ανθρώπους μια φορά αλλά επειδή θέλουμε να ελέγξετε αν είστε εκεί αργότερα αν θέλουμε να εκτυπώσετε όλα τα ονόματα στη δομή των δεδομένων. Εμείς πάμε για να κάνουμε κάτι με αυτά τα δεδομένα τελικά. Έτσι τώρα έχουμε το είδος της βιδωθεί πάνω από Alice, ο οποίος δεν είναι πλέον όπου υποτίθεται ότι είναι. Ούτε είναι ο Bob, ούτε είναι ο Τσάρλι. Έτσι, ίσως αυτό δεν είναι και τόσο καλή ιδέα. Αλλά πράγματι, αυτό είναι μια επιλογή. Θα μπορούσαν να στρέψουν όλοι κάτω, ή heck, Anita ήρθε αργά στο παιχνίδι, γιατί δεν βάζουμε μόνο Anita δεν είναι εδώ, δεν είναι εδώ, δεν είναι εδώ, ας βάλουμε της λίγο χαμηλότερα στη λίστα. Στη συνέχεια, όμως αυτό το πρόβλημα αρχίζει να περιέρχεται και πάλι. Ίσως να είναι σε θέση να βρείτε Alice αμέσως, με βάση το όνομά της. Και ο Bob αμέσως, και ο Τσάρλι. Αλλά τότε θα κοιτάξουμε για Anita, και θα δείτε, χμμ, Alice είναι στο δρόμο. Λοιπόν, επιτρέψτε μου να ελέγξετε κάτω από Alice. Bob δεν είναι Anita. Τσάρλι δεν είναι Anita. Ω, υπάρχει Ανίτα. Και αν συνεχίσετε το τρένο της λογικής σε όλη τη διαδρομή, Ποια είναι η χειρότερη περίπτωση χρόνος λειτουργίας για την εξεύρεση ή την εισαγωγή Anita σε αυτή τη νέα δομή δεδομένων; Είναι O (n), έτσι δεν είναι; Επειδή στη χειρότερη περίπτωση, υπάρχει Alice, ο Bob, ο Τσάρλι. . . σε όλη τη διαδρομή σε κάποιον που ονομάζεται "Υ", έτσι υπάρχει μόνο ένα σημείο αριστερά. Ευτυχώς, δεν έχουμε ένα ονομάζεται "Ζ", έτσι βάλαμε Anita στο κάτω μέρος. 

Εμείς δεν έχουμε λύσει πραγματικά το πρόβλημα. Έτσι, ίσως χρειάζεται να εισαγάγει αυτή την τρίτη διάσταση. Και αποδεικνύεται, αν δεν εισάγουν αυτή την τρίτη διάσταση, δεν μπορούμε να κάνουμε αυτό τέλεια, αλλά το Άγιο Δισκοπότηρο πρόκειται να πάρει σταθερής χρονική στιγμή της εισαγωγής και δυναμικές προσθήκες έτσι ώστε να δεν έχουμε στο σκληρό-κώδικα ένας πίνακας μεγέθους 26. Μπορούμε να εισάγετε ως πολλά ονόματα όπως θέλουμε, αλλά ας ρίξουμε 5-λεπτά διάλειμμα μας εδώ και στη συνέχεια, κάντε ότι σωστά. Εντάξει. Έθεσα την ιστορία μέχρι εκεί αρκετά τεχνητά επιλέγοντας Alice και ο Bob, στη συνέχεια και στη συνέχεια Charlie και στη συνέχεια, Anita, του οποίου το όνομα ήταν προφανώς πρόκειται να συγκρουστούν με την Αλίκη. Αλλά το ερώτημα που έληξε τη Δευτέρα με το πόσο είναι πιθανό να είναι ότι θα πάρει αυτά τα είδη των συγκρούσεων; Με άλλα λόγια, αν αρχίσουμε να χρησιμοποιήσετε αυτό το πίνακα δομή, η οποία είναι πραγματικά ακριβώς μια σειρά, σε αυτή την περίπτωση από 26 περιοχές, τι θα γίνει αν οι εισροές μας αντί ομοιόμορφα κατανεμημένες; Δεν είναι τεχνητά Alice και ο Bob και ο Τσάρλι και ο David και ούτω καθεξής αλφαβητικά, αυτό είναι ομοιόμορφα κατανεμημένο πάνω από το A έως το Z. 

Ίσως απλά θα πάρετε τυχεροί και εμείς δεν πρόκειται να έχει δύο Α ή δύο Β με πολύ μεγάλη πιθανότητα, αλλά όπως επεσήμανε κάποιος, αν γενικευμένη αυτό το πρόβλημα και δεν κάνουμε 0 - 25 αλλά, ας πούμε, από 0 έως 364 ή 65, συχνά ο αριθμός των ημερών σε ένα τυπικό χρόνια, και ζήτησε από την ερώτηση, "Ποια είναι η πιθανότητα ότι δύο από εμάς σε αυτό το δωμάτιο έχουν την ίδια γενέθλια;" Βάλτε έναν άλλο τρόπο, ποια είναι η πιθανότητα ότι δύο από μας έχουν ένα όνομα που αρχίζει με ένα; Το είδος της ερώτησης είναι η ίδια, αλλά αυτό το χώρο διευθύνσεων, αυτός ο χώρος αναζήτησης, είναι μεγαλύτερο στην περίπτωση της γενέθλια, γιατί έχουμε τόσες πολλές περισσότερες ημέρες του έτους από γράμματα του αλφαβήτου. Ποια είναι η πιθανότητα μιας σύγκρουσης; Λοιπόν, μπορούμε να σκεφτούμε αυτό από βγάλει τα μαθηματικά με τον αντίθετο τρόπο. Ποια είναι η πιθανότητα χωρίς συγκρούσεις; Λοιπόν, αυτή η έκφραση εδώ λέει πως ό, τι είναι η πιθανότητα αν υπάρχει μόνο ένα άτομο σε αυτή την αίθουσα, ότι έχουν μια μοναδική γενέθλια; Είναι 100%. Διότι, αν υπάρχει μόνο ένα άτομο στο δωμάτιο, του ή τα γενέθλιά της μπορεί να είναι οποιαδήποτε από τις 365 ημέρες από το χρόνο. Έτσι, 365/365 επιλογές μου δίνει την τιμή 1. Έτσι, η εν λόγω πιθανότητα αυτή τη στιγμή είναι μόλις 1. Αλλά αν υπάρχει ένα δεύτερο άτομο στο δωμάτιο, Ποια είναι η πιθανότητα ότι τα γενέθλιά τους είναι διαφορετική; Υπάρχει δυνατή μόλις 364 ημέρες, αγνοώντας τα δίσεκτα έτη, για τα γενέθλιά τους, να μην συγκρούονται με τα άλλα πρόσωπα. Έτσι, 364/365. Αν ένα τρίτο άτομο έρχεται σε, είναι 363/365, και ούτω καθεξής. Έτσι κρατάμε το γινόμενο αυτών των κλασμάτων, οι οποίες γίνονται όλο και μικρότερα, για να καταλάβουμε ποια είναι η πιθανότητα ότι όλοι μας έχουμε το μοναδικό γενέθλια; Στη συνέχεια, όμως μπορούμε, φυσικά, μόλις λάβει την απάντηση και γυρίστε το γύρω και να κάνει 1 μείον όλα αυτά, μια έκφραση που θα πάρει τελικά αν θυμάστε το πίσω μέρος των βιβλίων σας μαθηματικά, φαίνεται λίγο κάτι σαν αυτό, η οποία είναι πολύ πιο εύκολα να ερμηνευθεί γραφικά. Και αυτό το γραφικό εδώ έχει στον άξονα x τον αριθμό των γενεθλίων, ή ο αριθμός των ατόμων με γενέθλια, και στον άξονα y είναι η πιθανότητα ενός αγώνα. Και τι είναι αυτό που λέει είναι ότι αν έχετε, ας πούμε, ακόμα, Ας επιλέξουν κάτι σαν 22, 23. Αν υπάρχει 22 ή 23 άτομα σε ένα δωμάτιο, η πιθανότητα ότι δύο από αυτές τις πολύ λίγοι άνθρωποι θα έχουν την ίδια γενέθλια Είναι πραγματικά εξαιρετικά υψηλή, συνδυαστικά. 50% πιθανότητες ότι σε μια κατηγορία από μόνο 22 άτομα, ένα σεμινάριο, πρακτικά, 2 από αυτούς τους ανθρώπους θα έχουν την ίδια γενέθλια. Επειδή υπάρχει τόσο πολλοί τρόποι με τους οποίους μπορείτε να έχετε την ίδια γενέθλια. Ακόμη χειρότερα, αν δείτε στη δεξιά πλευρά του γραφήματος, από τη στιγμή που έχετε μια τάξη με 58 μαθητές σε αυτό, η πιθανότητα 2 άτομα έχουν γενέθλια είναι super, super υψηλή, σχεδόν 100%. Τώρα, αυτό είναι ένα είδος διασκέδασης γεγονός για την πραγματική ζωή. 

Αλλά οι συνέπειες, τώρα, για τις δομές δεδομένων και αποθήκευση πληροφοριών σημαίνει ότι μόνο με την προϋπόθεση να έχουν μια ωραία, καθαρή, ομοιόμορφη κατανομή των δεδομένων και έχετε μια αρκετά μεγάλη ποικιλία για να χωρέσει ένα σωρό πράγματα δεν σημαίνει ότι θα πάμε για να πάρει τους ανθρώπους σε μοναδικές τοποθεσίες. Θα πάμε να έχουν συγκρούσεις. Έτσι, η έννοια του κατακερματισμού, όπως λέγεται, λαμβάνοντας μια είσοδο σαν «Αλίκη» και το μασάζ με κάποιο τρόπο και στη συνέχεια να πάρει πίσω μια απάντηση όπως 0 ή 1 ή 2. Να πάρει πίσω κάποια έξοδο από την λειτουργία μαστίζεται από την παρούσα πιθανότητα σύγκρουσης. Λοιπόν, πώς μπορούμε να χειριστούμε αυτές τις συγκρούσεις; Λοιπόν, σε μία περίπτωση, μπορούμε να πάρουμε την ιδέα που προτάθηκε. Μπορούμε να μετατοπιστεί λίγο όλοι κάτω, ή ίσως, λίγο πιο απλά, όχι ο καθένας κίνηση άλλος, ας προχωρήσουμε λίγο Anita στο κάτω μέρος του διαθέσιμου σημείο. Έτσι, αν Alice είναι 0, ο Bob είναι σε 1, Τσάρλι είναι σε 2, θα βάλουμε απλώς Anita στη θέση 3. Και αυτό είναι μια τεχνική σε δομές δεδομένων που ονομάζεται γραμμική σχολαστικά. Γραμμική επειδή περπατάτε ακριβώς αυτή τη γραμμή, και είστε το είδος της σχολαστικά για διαθέσιμες θέσεις στη δομή δεδομένων. Φυσικά, αυτό περιέρχεται σε O (n). Αν η δομή των δεδομένων είναι πραγματικά πλήρης, υπάρχει 25 άτομα σε αυτό ήδη, και στη συνέχεια έρχεται Anita, που καταλήγει σε τι θέση θα είναι Ζ, και ότι είναι μια χαρά. Της ταιριάζει ακόμα, και μπορούμε να τη βρούμε αργότερα. 

Αλλά αυτό ήταν αντίθετο προς το στόχο της επιτάχυνση πράγματα. Τι κι αν έχουμε εισαγάγει αντί αυτή η τρίτη διάσταση; Αυτή η τεχνική ονομάζεται γενικά ξεχωριστό αλυσοποίηση, ή με αλυσίδες. Και τι ένα πίνακα κατακερματισμού είναι τώρα, αυτή η δομή πίνακα, το τραπέζι σας είναι απλώς μια σειρά από δείκτες. Αλλά ποιοί είναι αυτοί οι δείκτες δείχνουν να είναι εικασία τι; Μια συνδεδεμένη λίστα. Τι κι αν πάρουμε το καλύτερο και των δύο αυτών κόσμων; Χρησιμοποιούμε πίνακες για τις αρχικές δείκτες μέσα στην δομή δεδομένων έτσι ώστε να μπορούμε αμέσως πάμε στο [0] [1], [30], ή ούτω καθεξής, αλλά έτσι ώστε να έχουμε κάποια ευελιξία και θα μπορούν να χωρέσουν Anita και η Alice και ο Αδάμ και οποιοδήποτε άλλο Ένα όνομα, εμείς αντί να αφήσουμε το άλλο άξονα αυξάνεται αυθαίρετα. Και τελικά, από τη Δευτέρα, έχουν αυτό το εκφραστικό δυνατότητα με συνδεδεμένη λίστα. Μπορούμε να αναπτυχθεί μια δομή δεδομένων αυθαίρετα. Εναλλακτικά, θα μπορούσαμε να κάνουμε μόνο μια τεράστια 2-διάστατο πίνακα, αλλά ότι πρόκειται να είναι μια φρικτή κατάσταση, εάν μία από τις σειρές σε ένα 2-διάστατο πίνακα δεν είναι αρκετά μεγάλο για το επιπλέον άτομο το όνομα του οποίου συμβαίνει να ξεκινήσει με Α. Θεός φυλάξοι θα πρέπει να ανακατανείμει μια τεράστια 2-τρισδιάστατη δομή μόνο και μόνο επειδή υπάρχει τόσο πολλοί άνθρωποι που ονομάζεται Α, ειδικά όταν υπάρχει τόσο λίγοι άνθρωποι που ονομάζεται Z κάτι. Είναι ακριβώς πρόκειται να είναι μια πολύ αραιή δομή δεδομένων. Έτσι δεν είναι τέλειο, με οποιοδήποτε μέσο, ​​αλλά τώρα έχουμε τουλάχιστον τη δυνατότητα να βρείτε άμεσα ή όπου Alice Anita ανήκει, τουλάχιστον από την άποψη του κατακόρυφο άξονα, και στη συνέχεια εμείς απλά πρέπει να αποφασίσετε πού να βάλει Anita ή Αλίκη στη χώρα αυτή συνδεδεμένη λίστα. Αν δεν με νοιάζει για να τακτοποιήσει τα πράγματα, πόσο γρήγορα θα μπορούσαμε να εισάγετε Αλίκη σε μια δομή σαν αυτό; Είναι σταθερό χρόνο. Εμείς δείκτη σε [0], αν και δεν υπάρχει κανείς, Alice πηγαίνει κατά την έναρξη της εν λόγω συνδεδεμένη λίστα. Αλλά αυτό δεν είναι μια τεράστια συμφωνία. Γιατί αν Anita έρχεται έπειτα κατά μήκος μερικά βήματα από τον αριθμό αργότερα, όπου δεν ανήκουν Anita; Λοιπόν, [0]. OOP. Alice είναι ήδη σε αυτή συνδεδεμένη λίστα. 

Αλλά αν δεν με νοιάζει για τη διαλογή αυτά τα ονόματα, μπορούμε να προχωρήσουμε λίγο πάνω από Alice, ένθετο Anita, αλλά ακόμα και αυτό είναι σταθερό χρόνο. Ακόμα κι αν υπάρχει Αλίκη και ο Αδάμ και όλα τα άλλα ονόματα Α, δεν είναι μετατόπιση τους πραγματικά σωματικά. Γιατί; Επειδή ακριβώς έκανε εδώ με συνδεδεμένη λίστα, ποιος ξέρει ήταν οι κόμβοι αυτοί είναι ούτως ή άλλως; Το μόνο που έχετε να κάνετε είναι να μετακινήσετε τα ψίχουλα ψωμιού. Μετακινήστε τα βέλη γύρω? Δεν πρέπει να προχωρήσουμε φυσικά όλα τα δεδομένα γύρω. Έτσι μπορούμε να εισάγουμε Anita, στην περίπτωση αυτή, αμέσως. Σταθερό χρόνο. Έτσι έχουμε συνεχή χρόνο αναζήτησης, και σταθερής χρονική στιγμή της εισαγωγής του κάποιος σαν τον Ανίτα. Αλλά το είδος της υπεραπλούστευση τον κόσμο. Κι αν αργότερα θέλετε να βρείτε Alice; Κι αν αργότερα θέλετε να βρείτε Alice; Πόσα βήματα είναι ότι πρόκειται να πάρει; [Απάντηση Φοιτητής, ακατάληπτο] Ακριβώς. Ο αριθμός των ανθρώπων πριν Αλίκη στη συνδεδεμένη λίστα. Έτσι δεν είναι αρκετά τέλειος, επειδή η δομή των δεδομένων μας, πάλι, έχει αυτή την κάθετη πρόσβαση και στη συνέχεια να έχει αυτές τις συνδεδεμένες λίστες κρέμονται - στην πραγματικότητα, ας μην το τραβάμε μια μια σειρά. Έχει αυτά τα συνδεδεμένες λίστες κρέμεται μακριά από αυτό που μοιάζει λίγο κάτι σαν αυτό. Αλλά το πρόβλημα είναι αν η Alice και ο Αδάμ και όλα τα άλλα ονόματα Α καταλήγουν όλο και περισσότερο εκεί, εύρεση κάποιος θα μπορούσε να καταλήγουν να λαμβάνουν ένα μάτσο βήματα, bcause θα πρέπει να διασχίσει τη συνδεδεμένη λίστα, η οποία είναι μια γραμμική λειτουργία. Έτσι, στην πραγματικότητα, τότε, η χρονική στιγμή της εισαγωγής είναι τελικά O (n), όπου n είναι ο αριθμός των στοιχείων στη λίστα. Χωρίζεται από την, ας το ονομάσουμε αυθαίρετα m, όπου m είναι ο αριθμός των συνδεδεμένων λιστών ότι έχουμε σε αυτό το κατακόρυφο άξονα. Με άλλα λόγια, αν υποθέσουμε πραγματικά μια ομοιόμορφη κατανομή των ονομάτων, εντελώς μη ρεαλιστικό. Υπάρχει προφανώς περισσότερο από κάποιες επιστολές από τους άλλους. 

Αλλά αν υποθέσουμε για την στιγμή που μια ομοιόμορφη κατανομή, και έχουμε n συνολικά άτομα, και μ σύνολο αλυσίδες έχουμε στη διάθεσή μας, τότε το μήκος καθενός από αυτές τις αλυσίδες αρκετά απλά πρόκειται να είναι το σύνολο, n διαιρείται με τον αριθμό των αλυσίδων. Έτσι, n / m. Αλλά εδώ είναι όπου μπορούμε να είμαστε όλοι μαθηματικά έξυπνος. m είναι μια σταθερά, επειδή υπάρχει ένα σταθερό αριθμό από αυτά. Θα πάμε να δηλώσει σειρά σας στην αρχή, και δεν είμαστε αλλάζοντας το μέγεθος του κατακόρυφου άξονα. Εξ ορισμού, το οποίο παραμένει σταθερό. Είναι μόνο ο οριζόντιος άξονας, να το πω έτσι, αυτό αλλάζει. Έτσι τεχνικώς, αυτή είναι μια σταθερά. Μέχρι τώρα, η χρονική στιγμή της εισαγωγής είναι λίγο πολύ O (n). Έτσι, αυτό δεν αισθάνονται όλοι ότι πολύ καλύτερα. Αλλά ποια είναι η αλήθεια εδώ; Λοιπόν, όλο αυτό το διάστημα, για εβδομάδες, έχουμε πει O (n ²). O (n), 2 χ ν ², - n, διαιρούμενο με 2. . . ech. Είναι ακριβώς n ². Αλλά τώρα, σε αυτό το μέρος του εξαμήνου, μπορούμε να αρχίσουμε να μιλάμε για τον πραγματικό κόσμο και πάλι. Και n / m είναι απολύτως ταχύτερα από ό, τι ακριβώς n μόνο. Αν έχετε χίλια ονόματα, και να τους χωρίσει σε πολλαπλά κάδους έτσι ώστε να έχετε μόνο δέκα ονόματα σε κάθε μία από αυτές τις αλυσίδες, απολύτως αναζήτηση δέκα πράγματα θα είναι πιο γρήγορα από χίλια πράγματα. Και έτσι ένα από τα επόμενα σετ πρόβλημα δεν πρόκειται να σας προκαλέσει να σκεφτούν ακριβώς ότι ακόμα κι αν, ναι, ασυμπτωτικά και μαθηματικά, αυτό εξακολουθεί να είναι ακριβώς γραμμική, η οποία σε γενικές γραμμές είναι χάλια, όταν προσπαθούν να βρουν τα πράγματα. Στην πραγματικότητα, πρόκειται να είναι ταχύτερη από ό, τι η λόγω αυτού του διαιρέτη. Και έτσι είναι και πάλι εκεί θα είναι αυτό το trade-off και αυτή η σύγκρουση μεταξύ θεωρίας και πραγματικότητας, και ένα από τα κομβία θα αρχίσει καμπής σε αυτό το σημείο στο εξάμηνο είναι περισσότερο από το ένα ως πραγματικότητα εμείς είδος προετοιμαστούν για το τέλος του semster, όπως έχουμε εισαγάγει τον κόσμο του web προγραμματισμό, όπου πραγματικά, η απόδοση θα μετρήσει επειδή οι χρήστες σας πρόκειται να αρχίσετε να αισθάνεστε και να εκτιμήσουν κακές αποφάσεις σχεδιασμού. 

Έτσι, πώς πηγαίνετε για την εφαρμογή ενός συνδεδεμένου - έναν πίνακα κατακερματισμού με 31 στοιχεία; Και το προηγούμενο παράδειγμα ήταν αυθαίρετα για γενέθλια. Αν κάποιος έχει γενέθλια την 1η Ιανουαρίου ή 1 Φεβρουαρίου, θα τους βάλει σε αυτό το κουβά. Αν είναι 2 Ιανουαρίου, 2 Φεβρουαρίου, 2 Μαρτίου, θα τους βάλει σε αυτό το κουβά. Γι 'αυτό ήταν 31. Πώς μπορείτε να κηρύξει πίνακα κατακερματισμού; Μπορεί να είναι αρκετά απλή, κόμβος πίνακα * είναι αυθαίρετο το όνομά μου για αυτό, [31]. Αυτό μου δίνει 31 δείκτες σε κόμβους, και που μου δίνει τη δυνατότητα να έχουν 31 δείκτες σε συνδεδεμένες λίστες ακόμη και αν οι αλυσίδες είναι αρχικά NULL. Τι θέλω να βάλω αν θέλετε να αποθηκεύσετε "Alice", "βαρίδι", "Τσάρλι"; Λοιπόν, θα πρέπει να τυλίξετε αυτά τα πράγματα σε μια δομή γιατί πρέπει να επισημάνω Alice στον Bob, να επισημάνω Charlie, και ούτω καθεξής. Δεν μπορούμε να έχουμε μόνο τα ονόματα από μόνα τους, γι 'αυτό θα μπορούσε να δημιουργήσει μια νέα δομή που ονομάζεται κόμβος εδώ. 

Τι είναι ένας πραγματικός κόμβος; Τι είναι ένας κόμβος συνδέεται σε αυτό το νέο κατάλογο; Το πρώτο πράγμα, που ονομάζεται λέξη, είναι για το όνομα του ατόμου. ΜΗΚΟΣ, προφανώς, σχετίζεται με το μέγιστο μήκος του ονόματος ενός ανθρώπου, ό, τι, δηλαδή, 20, 30, 40 χαρακτήρες σε τρελή γωνία περιπτώσεις, +1 είναι και για τι; Είναι ακριβώς το επιπλέον χαρακτήρα NULL, \ 0. Έτσι, αυτός ο κόμβος είναι περιτύλιγμα "κάτι" μέσα από μόνη της, αλλά δηλώνει επίσης ένα δείκτη που ονομάζεται επόμενο έτσι ώστε να μπορούμε αλυσίδα Alice στον Bob να Τσάρλι και ούτω καθεξής. Μπορεί να είναι NULL, αλλά δεν είναι απαραίτητο να είναι. Οποιεσδήποτε ερωτήσεις σχετικά με αυτούς τους πίνακες κατακερματισμού; Ναι; [Φοιτητών ζητώντας ερώτηση, ακατάληπτο] Μια σειρά - καλή ερώτηση. Γιατί είναι αυτή η λέξη char σε μια σειρά και όχι μόνο char *; Σε αυτό το κάπως αυθαίρετη παράδειγμα, δεν ήθελα να χρειαστεί να καταφύγουν στην malloc για καθένα από τα αρχικά ονόματα. Ήθελα να δηλώσει ένα μέγιστο ποσό μνήμης για τη σειρά ώστε να μπορώ να αντιγράψετε στη δομή Alice \ 0 και δεν πρέπει να ασχοληθεί με malloc και δωρεάν και τα παρόμοια. Αλλά θα μπορούσα να κάνω ότι αν ήθελα να είναι πιο συνειδητή χρήση του χώρου. Καλή ερώτηση. Ας προσπαθήσουμε να γενικεύσουμε μακριά από αυτό και να επικεντρωθεί το υπόλοιπο του σήμερα στις δομές δεδομένων γενικότερα και άλλα προβλήματα που μπορούμε να λύσουμε με τις ίδιες βασικές αρχές ακόμη και αν οι ίδιοι δομές δεδομένων μπορεί να διαφέρουν σε στοιχεία τους. 

Έτσι αποδεικνύεται στην επιστήμη των υπολογιστών, τα δέντρα είναι πολύ συχνές. Και μπορείτε να σκεφτείτε ένα είδος δέντρου, όπως ένα οικογενειακό δέντρο, όπου υπάρχει κάποια ρίζες, κάποια γυναίκα αρχηγός φυλής ή πατριάρχης, γιαγιά ή ο παππούς ή νωρίτερα πίσω, κάτω από τις οποίες είναι η μαμά και ο μπαμπάς ή διάφορες αδέλφια ή τα παρόμοια. Έτσι, μια δομή δέντρου έχει κόμβους και έχει παιδιά, συνήθως 0 ή περισσότερα παιδιά για κάθε κόμβο. Και μερικές από την ορολογία που βλέπετε στην εικόνα εδώ Είναι κάποιο από τα μικρά παιδιά ή τα εγγόνια στις άκρες που δεν έχουν βέλη που προέρχονται από αυτά, αυτά είναι τα λεγόμενα φύλλα, και ο καθένας στο εσωτερικό είναι ένα εσωτερικό κόμβο? μπορείτε να καλέσετε το τίποτα προς αυτή την κατεύθυνση. Αλλά αυτή η δομή είναι αρκετά κοινή. Αυτό και μόνο είναι λίγο αυθαίρετο. Έχουμε ένα παιδί στα αριστερά, έχουμε τρία παιδιά στα δεξιά, δύο παιδιά κάτω αριστερά. Έτσι μπορούμε να έχουμε διαφορετικού μεγέθους δέντρα, αλλά αν αρχίσουμε να τυποποιήσουν τα πράγματα, και ίσως να θυμάστε αυτό από το βίντεο του Πάτρικ σε δυαδική αναζήτηση από μια προηγούμενη σύντομη σε απευθείας σύνδεση, δυαδική αναζήτηση δεν πρέπει να υλοποιηθεί με μια σειρά ή κομμάτια χαρτιού σε έναν πίνακα. Ας υποθέσουμε ότι θέλετε να αποθηκεύσετε αριθμούς σας σε μια πιο εξελιγμένη δομή δεδομένων. Θα μπορούσατε να δημιουργήσετε ένα δέντρο σαν αυτό. Θα μπορούσε να έχει ένα κόμβο δηλωθεί σε C, και ότι ο κόμβος μπορεί να έχει τουλάχιστον δύο στοιχεία στο εσωτερικό του. Το ένα είναι ο αριθμός που θέλετε να αποθηκεύσετε, και το άλλο είναι - καλά, χρειαζόμαστε ένα ακόμη. Η άλλη είναι τα παιδιά του. Έτσι, εδώ είναι μια άλλη δομή δεδομένων. Αυτή τη φορά, ένας κόμβος ορίζεται ως αποθήκευση ενός αριθμού n και στη συνέχεια δίποντα? αριστερό και δεξιό παιδί. Και δεν είναι αυθαίρετη. Αυτό που είναι ενδιαφέρον σχετικά με αυτό το δέντρο; 

Ποιο είναι το σχέδιο για το πώς έχουμε αυτό που έξω ή πώς ο Patrick είναι που στο βίντεο του; Είναι το είδος του είναι προφανές ότι υπάρχει κάποια διαλογή συμβαίνει εδώ, αλλά ποιο είναι το απλό κανόνα; Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Τέλεια. Αν ρίξουμε μια ματιά σε αυτό, μπορείτε να δείτε τους μικρούς αριθμούς στα αριστερά, μεγάλους αριθμούς στα αριστερά, αλλά είναι αλήθεια ότι για κάθε κόμβο. Για κάθε κόμβο, αριστερό παιδί του λιγότερο από αυτό, και το δεξί παιδί του μεγαλύτερες από αυτή. Αυτό σημαίνει ότι τώρα είναι αν θέλετε να αναζητήσετε αυτή τη δομή δεδομένων για, ας πούμε, με τον αριθμό 44, Θα πρέπει να ξεκινήσει από τη ρίζα, γιατί όπως με όλες αυτές τις πιο σύνθετες δομές δεδομένων τώρα, έχουμε μόνο ένα δείκτη σε ένα πράγμα, η αρχή. Και σε αυτή την περίπτωση, η αρχή είναι η ρίζα. Δεν είναι το αριστερό άκρο, είναι η ρίζα αυτής της δομής. Έτσι βλέπω εδώ είναι 55, και ψάχνω για 44. Ποια κατεύθυνση θέλω να πάω; Λοιπόν, θέλω να πάω προς τα αριστερά, διότι προφανώς, στα δεξιά θα είναι πάρα πολύ μεγάλο. Έτσι παρατηρούμε εδώ, είστε το είδος του εννοιολογικά κόψιμο του δέντρου στο μισό επειδή δεν πρόκειται ποτέ κάτω στην δεξιά πλευρά. Έτσι τώρα θα πάω από το 55 έως το 33. Είναι πολύ μικρός σε αριθμό. Ψάχνω για 44, αλλά τώρα ξέρω αν 44 είναι σε αυτό το δέντρο, μπορώ να πάω προφανώς προς τα δεξιά. Έτσι, και πάλι, είμαι κλάδεμα του δέντρου στο μισό. Είναι λίγο πολύ ίδια εννοιολογικά στον τηλεφωνικό κατάλογο. Είναι ίδιο με αυτό που κάναμε με τα έγγραφα σχετικά με το μαυροπίνακα, αλλά είναι μια πιο εξελιγμένη δομή που μας επιτρέπει να κάνουμε πραγματικότητα αυτό το διαίρει και βασίλευε από το σχεδιασμό του αλγορίθμου, και στην πραγματικότητα, διασχίζοντας μια δομή σαν αυτή - κραυγών. Διασχίζοντας μια δομή όπως αυτή, όπου είναι μόνο «πάει με αυτό τον τρόπο ή να πάτε με αυτόν τον τρόπο," σημαίνει ότι όλες κώδικα που λυγισμένο μυαλό σας κατά την πρώτη κατά την εφαρμογή της στο τμήμα ή περπατώντας μέσα στο σπίτι, για δυαδική αναζήτηση, χρησιμοποιώντας αναδρομή ή επανάληψη, Είναι ένας πόνος στο λαιμό. Βρείτε το μεσαίο στοιχείο, στη συνέχεια, κάντε στρογγυλοποίηση προς τα πάνω ή προς τα κάτω. 

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

Έτσι, υπάρχει μια άλλη δομή δεδομένων που μπορεί να εισάγει. Αυτό και μόνο είναι σχεδιασμένο με την πρώτη ματιά να δούμε αινιγματικά, αλλά αυτό είναι καταπληκτικό. Έτσι, αυτό είναι μια δομή δεδομένων που ονομάζεται trie, trie, η οποία κληρονόμησε από την ανάκτηση λέξη, η οποία δεν προφέρεται εκ νέου προσπάθεια-val, αλλά αυτό είναι που ο κόσμος αποκαλεί αυτά τα πράγματα. Προσπαθεί. Τ-r-ί-ε. Είναι μια δομή δέντρου κάποιου είδους, αλλά κάθε ένα από τους κόμβους σε ένα trie φαίνεται να είναι αυτό; Και αυτό είναι λίγο παραπλανητικό, διότι αυτό είναι το είδος του συντομογραφία. Αλλά μοιάζει με κάθε κόμβος σε αυτό το trie είναι στην πραγματικότητα μια σειρά. Και παρόλο που ο συγγραφέας αυτού του διαγράμματος δεν έχει δείξει ότι, σε αυτή την περίπτωση, αυτό trie είναι μια δομή δεδομένων των οποίων ο σκοπός στη ζωή είναι να αποθηκεύουν τις λέξεις σαν A-l-i-c-e ή Β-o-β. Και ο τρόπος με τον οποίο αποθηκεύει δεδομένα Alice και ο Bob και ο Τσάρλι και η Anita και ούτω καθεξής είναι αυτό που χρησιμοποιεί μια σειρά με την οποία να αποθηκεύσετε Αλίκη σε ένα trie, που ξεκινούν από τον κόμβο ρίζα που μοιάζει με έναν πίνακα, και είναι ήδη γραμμένο σε σημειογραφία στενογραφία. Ο συγγραφέας ABCDEFG παραλείπεται επειδή δεν υπήρχαν τα ονόματα με αυτό. Μπορούν έδειξε μόνο Μ και Ρ και Τ, αλλά στην περίπτωση αυτή, Ας ξεφύγουμε από την Alice και ο Bob και ο Τσάρλι σε κάποια ονόματα που είναι εδώ. Maxwell είναι πραγματικά σε αυτό το διάγραμμα. Λοιπόν, πώς έκανε το κατάστημα συγγραφέας Μ-Α-Χ-ν-ε-λ-λ; Αυτός ή αυτή που ξεκίνησε στον κόμβο ρίζα, και πήγε στο [M], έτσι περίπου 13, η 13η θέση του πίνακα. Στη συνέχεια, από εκεί, υπάρχει ένας δείκτης. Ένας δείκτης που οδηγεί σε έναν άλλο πίνακα. Από εκεί και πέρα ​​ο συγγραφέας αναπροσαρμόζονται σε αυτού του πίνακα στη θέση Α, όπως φαίνεται εκεί στην κορυφή αριστερά, και τότε αυτός ή αυτή ακολουθεί την δείκτη σε άλλο πίνακα, και πήγε στο δείκτη στη θέση X. Στη συνέχεια, στο επόμενο συστοιχία θέση W, E, L, L, και ούτω καθεξής, και, τέλος, ας προσπαθήσουμε πραγματικά να θέσει μια εικόνα σε αυτό. Τι κάνει ένας κόμβος μοιάζει στον κώδικα; Ένας κόμβος σε ένα trie περιέχει μια σειρά από δείκτες σε περισσότερους κόμβους. Αλλά υπάρχει επίσης πήρε να είναι κάποιο είδος του boolean τιμή, τουλάχιστον σε αυτή την εφαρμογή. Τυχαίνει να το ονομάσουμε is_word. Γιατί; Διότι όταν είστε εισαγωγή Maxwell, δεν είστε εισαγωγή τίποτα σε αυτή τη δομή δεδομένων. Δεν είστε γραπτώς Μ. Δεν είστε γράψει το X. Το μόνο που κάνετε είναι μετά δείκτες. Ο δείκτης που αντιπροσωπεύει M, τότε ο δείκτης που αντιπροσωπεύει Α, τότε ο δείκτης που αντιπροσωπεύει το Χ, τότε το W, E, L, L, αλλά αυτό που πρέπει να κάνετε στο τέλος είναι το είδος του πάει, ελέγχει, θα φθάσει σε αυτό το σημείο. Υπήρχε μια λέξη που τελειώνει εδώ στη δομή δεδομένων. 

Έτσι, ό, τι ένα trie είναι πραγματικά γεμάτη με και ο συγγραφέας επέλεξε να εκπροσωπήσει terminuses με αυτά τα μικρά τρίγωνα. Αυτό σημαίνει απλά ότι το γεγονός αυτό το τρίγωνο είναι εδώ, αυτή η boolean τιμή της πραγματικής σημαίνει ότι αν πάτε πίσω στο δέντρο, αυτό σημαίνει ότι μια λέξη είναι το όνομα Maxwell σε αυτό. Αλλά η λέξη foo, για παράδειγμα, δεν είναι στο δέντρο, γιατί αν αρχίσω στον κόμβο ρίζα μέχρι εδώ στην κορυφή, Δεν υπάρχει στ δείκτη, δεν δείκτη o, o δείκτης καμία. Foo δεν είναι ένα όνομα σε αυτό το λεξικό. Αλλά αντιθέτως, θρωση, ί-υ-r-ί-ν-ζ. Και πάλι, δεν είχα αποθηκεύσει t ή u ή r ή θ ή ν ή g. Αλλά έκανα κατάστημα σε αυτή τη δομή δεδομένων η αξία της αληθινής τρόπος κάτω εδώ σε αυτόν τον κόμβο - στο δέντρο θέτοντας αυτή την boolean τιμή του is_word να ισχύει. Έτσι, μια trie είναι το είδος της αυτή την πολύ ενδιαφέρουσα δομή μετα, Όπου και αν δεν είναι πραγματικά αποθήκευση των ίδιων των λέξεων για αυτό το είδος του λεξικό. Για να είμαι σαφής, είστε μόνο την αποθήκευση ναι ή όχι, υπάρχει μια λέξη που τελειώνει εδώ. 

Τώρα, ποια είναι η επίπτωση; Αν έχετε 150.000 λέξεις σε ένα λεξικό που προσπαθείτε να αποθηκεύσετε στη μνήμη χρησιμοποιώντας κάτι σαν μια συνδεδεμένη λίστα, θα έχετε την ευκαιρία να έχουν 150.000 κόμβους σε συνδεδεμένη λίστα σας. Και βρίσκοντας μία από αυτές τις λέξεις θα μπορούσε να πάρει αλφαβητικά O (n) χρόνο. Γραμμική χρόνο. Όμως, στην προκειμένη περίπτωση του trie, τι είναι ο χρόνος εκτέλεσης της εξεύρεσης μια λέξη; Βγάζει την ομορφιά εδώ είναι ότι ακόμη και αν έχετε ήδη 149.999 λέξεις σε αυτό το λεξικό, όπως εφαρμόζεται με αυτή τη δομή δεδομένων, πόσος χρόνος χρειάζεται για να βρουν ή να εισάγετε ένα ακόμη πρόσωπο σε αυτό, σαν την Αλίκη, Αλίκη; Λοιπόν, αυτό είναι μόνο 5, ίσως 6 βήματα για το χαρακτήρα τέλους. Επειδή πιθανολογείται η παρουσία άλλων ονομάτων στη δομή δεν παίρνει με τον τρόπο της εισαγωγής Alice. Επιπλέον, η εύρεση Alice φορά υπάρχουν 150.000 λέξεις σε αυτό το λεξικό δεν πάρει το δρόμο σας για την εξεύρεση Alice καθόλου, Alice επειδή είναι. . . . . εδώ, γιατί βρήκα μια boolean τιμή. Και αν δεν υπάρχει boolean αληθές, τότε Alice δεν είναι σε αυτή τη δομή δεδομένων των λέξεων. Με άλλα λόγια, ο χρόνος για την εξεύρεση πράγματα και εισάγοντας τα πράγματα σε αυτό το νέο δομή δεδομένων του trie είναι Ξ - δεν είναι n. Επειδή πιθανολογείται η παρουσία 150.000 άνθρωποι έχει καμία επίδραση στην Αλίκη, φαίνεται. Ας το ονομάσουμε k, όπου k είναι το μέγιστο μήκος μιας λέξης στα αγγλικά το οποίο είναι τυπικά όχι περισσότερο από 20-κάτι χαρακτήρες. Έτσι k είναι μια σταθερά. Έτσι, το Άγιο Δισκοπότηρο που φαίνεται να έχουν βρει τώρα είναι ότι από ένα trie, σταθερό χρόνο για ένθετα, για αναζητήσεις, για τις διαγραφές. Επειδή ο αριθμός των πραγμάτων ήδη στη δομή, η οποία δεν είναι ακόμα σωματικά εκεί. Και πάλι, από όπου και αν ακριβώς το είδος της απενεργοποιήσει, ναι ή όχι, δεν έχει καμία επίπτωση στις μελλοντικές χρόνο λειτουργίας του. 

Αλλά εκεί πήρε να είναι μια παγίδα, αλλιώς δεν θα είχαμε χάσει τόσο πολύ χρόνο σε όλες τις άλλες δομές δεδομένων μόνο για να πάρει τελικά το μυστικό για ένα που είναι καταπληκτικό. Λοιπόν, τι τιμή πληρώνουμε για την επίτευξη αυτού του μεγαλείου εδώ; Space. Αυτό το πράγμα είναι τεράστια. Και ο λόγος για τον οποίο ο συγγραφέας δεν το παρουσιάζουμε εδώ, παρατηρούμε ότι όλα αυτά τα πράγματα που μοιάζουν με πίνακες, δεν είχε επιστήσει την υπόλοιπη δέντρο, το υπόλοιπο του trie, επειδή απλά δεν έχουν σχέση με την ιστορία. Αλλά όλες αυτές οι κόμβοι είναι πολύ ευρεία, και κάθε κόμβος στο δέντρο καταλαμβάνει 26 ή στην πραγματικότητα, θα μπορούσε να είναι 27 χαρακτήρες, διότι σε αυτή την περίπτωση ήμουν συμπεριλαμβανομένων χώρο για την απόστροφο έτσι ώστε θα μπορούσαμε να έχουμε apostrophized λόγια. Σε αυτή την περίπτωση, αυτά είναι μεγάλη συστοιχίες. Έτσι, ακόμα κι αν δεν είστε picutured, αυτό καταλαμβάνει ένα τεράστιο ποσό της μνήμης RAM. Ποια θα μπορούσε να είναι μια χαρά, especilly σε σύγχρονο υλικό, αλλά αυτό είναι το δίλημμα. Έχουμε πάρει λιγότερο χρόνο από τις δαπάνες περισσότερο χώρο. Τόσο πού είναι όλα αυτά πας; Λοιπόν, ας το κάνουμε - να δούμε εδώ. Ας κάνουμε ένα άλμα προς αυτόν τον τύπο εδώ. 

Είτε το πιστεύετε είτε όχι, τόσο πολλή διασκέδαση όπως C έχει εδώ και αρκετό καιρό, είμαστε φθάσει στο σημείο στο εξάμηνο, όπου ήρθε η ώρα για τη μετάβαση σε πιο σύγχρονα πράγματα. Τα πράγματα σε ένα υψηλότερο επίπεδο. Και ακόμα κι αν για τις επόμενες δύο εβδομάδες θα εξακολουθούν να μας βυθίσει στον κόσμο των δεικτών και διαχείριση μνήμης για να πάρει ότι η άνεση με την οποία μπορούμε να οικοδομήσουμε την τότε, τέλος το παιχνίδι είναι τελικά να εισαγάγει, κατά ειρωνεία της τύχης, όχι αυτή η γλώσσα. Θα περάσουν, όπως 10 λεπτά μιλάμε για HTML. Όλα HTML είναι είναι μια γλώσσα σήμανσης, και τι είναι γλώσσα σήμανσης είναι αυτές οι σειρές των ανοικτών και κλειστών παρένθεση παρένθεση που λένε «κάνουν αυτό το τολμηρό» «Κάντε αυτό πλάγιους», «κάνουν αυτό το κέντρο». Δεν είναι όλα τα πνευματικά ενδιαφέροντα ότι, αλλά είναι εξαιρετικά χρήσιμο. Και είναι σίγουρα πανταχού παρούσα αυτές τις μέρες. Αλλά ό, τι είναι δυνατό για τον κόσμο του HTML, web προγραμματισμό και γενικότερα, χτίζει δυναμική πράγματα? γράφοντας κώδικα σε γλώσσες όπως η PHP ή Python ή Ruby ή Java ή C #. Πραγματικά, ανεξάρτητα από τη γλώσσα της επιλογής σας είναι, και παράγει δυναμικά HTML. Παραγωγή κάτι που ονομάζεται CSS δυναμικά. Cascading Style Sheets, που είναι επίσης σχετικά με την αισθητική. Και έτσι ακόμα κι αν, σήμερα, αν πάω σε κάποιο δικτυακό τόπο, όπως το γνωστό Google.com, και πάω να τη δείτε, προγραμματιστής, πηγή άποψη, που ίσως έχετε κάνει πριν, αλλά θα δείτε πηγή, αυτά τα πράγματα φαίνεται μάλλον αρκετά αινιγματικός. Αλλά αυτό είναι το υποκείμενο κώδικα που υλοποιεί Google.com. Στο μπροστινό άκρο. Και πράγματι όλα αυτά τα πράγματα είναι αφράτο αισθητική. Αυτό είναι CSS μέχρι εδώ. Αν συνεχίσετε την κύλιση κάτω θα πάρετε κάποια χρωματική κωδικοποίηση πράγματα. Αυτό είναι HTML. Κώδικα της Google μοιάζει με ένα χάος, αλλά αν μπορώ πραγματικά να ανοίξει ένα διαφορετικό παράθυρο, μπορούμε να δούμε κάποια δομή σε αυτό. Αν ανοίξω αυτό επάνω, παρατηρούμε εδώ, είναι λίγο πιο ευανάγνωστο. Εμείς πάμε να δούμε πριν από καιρό αυτήν την ετικέτα, [λέξη] είναι μια ετικέτα, HTML, το κεφάλι, το σώμα, div, σενάριο, περιοχή κειμένου, διάρκεια, στο κέντρο, div. Και αυτό είναι επίσης αινιγματικά ταξινομήσετε του εμφάνιση με την πρώτη ματιά, αλλά όλο αυτό το χάος ακολουθεί ορισμένα σχέδια, μοτίβα και επαναλαμβανόμενη, έτσι ώστε όταν θα έχουμε τα βασικά κάτω, θα είστε σε θέση να γράφουν κώδικα, όπως αυτό και στη συνέχεια να χειριστείτε κώδικα όπως αυτό χρησιμοποιώντας ακόμα μια άλλη γλώσσα, που ονομάζεται το JavaScript. Και το JavaScript είναι μια γλώσσα που τρέχει μέσα από ένα πρόγραμμα περιήγησης σήμερα που χρησιμοποιούμε για τα μαθήματα του Χάρβαρντ, για το εργαλείο ψώνια βέβαια ότι χρησιμοποιεί χάρτες Google για να σας δώσει ένα σωρό από δυναμισμό, το Facebook σας δίνει για να δείξει άμεσα ενημερώσεις κατάστασης, Twitter χρησιμοποιεί για να σας δείξω tweets αμέσως. Όλα αυτά θα αρχίσουν να εμπλακούμε μέσα Αλλά για να φτάσουμε εκεί, πρέπει να καταλάβουμε λίγο κάτι σχετικά με το Διαδίκτυο. Αυτό το κλιπ εδώ είναι μόνο ένα λεπτό μακριά, και ας υποθέσουμε ότι για τώρα αυτό είναι, στην πραγματικότητα, πώς λειτουργεί το Ίντερνετ ως ένα teaser για το τι είναι έτοιμος να έρθει. Σας δίνω "Warriors of the Net». 

[Αργή ♫ ♫ μουσική χορωδία] [Αντρας αφηγητής] Ήρθε με ένα μήνυμα. Με ένα πρωτόκολλο όλα δικά του. [♫ Ταχύτερη ηλεκτρονική μουσική ♫] Ήρθε σε ένα κόσμο δροσερό firewalls, routers αδιάφορος, και κινδύνους πολύ χειρότερη από τον θάνατο. Είναι γρήγορος. Είναι ισχυρή. Είναι το πρωτόκολλο TCP / IP, και πήρε τη διεύθυνσή σας. Πολεμιστές του Net. [Malan] Την επόμενη εβδομάδα, στη συνέχεια. Το Διαδίκτυο. Προγραμματισμού Web. Αυτό είναι CS50. [CS50.TV]