>> [Παίζει μουσική]
>> [ΑΝΑΠΑΡΑΓΩΓΗ]
>> -Αυτός Είναι ψέματα.
>> -Σχετικά Με τι;
>> -Δεν γνωρίζω.
>> -Γι 'Ό, τι ξέρουμε;
>> -ότι Στις 9:15, Ray Santoya ήταν στο ΑΤΜ.
-Ναι.
Έτσι, το ερώτημα είναι, τι κάνει αυτός στο 9:16;
>> -Shooting Το 9 χιλιοστών σε κάτι.
Ίσως είδε τον ελεύθερο σκοπευτή.
>> -Ή Δούλευε μαζί του.
>> -Wait.
Πήγαινε πίσω ένα.
>> -Τι βλεπεις?
>> -Φέρτε Το πρόσωπό του επάνω σε πλήρη οθόνη.
>> -His Γυαλιά.
>> -Υπάρχει Είναι μια αντανάκλαση.
>> -Είναι Η ομάδα μπέιζμπολ Nuevitas.
Αυτό είναι το λογότυπό τους.
>> -Και Μιλάει για την όποιος φοράει αυτό το σακάκι.
>> [Σταματήσετε την αναπαραγωγή]
>> DAVID Malan: Εντάξει.
Αυτό είναι CS50 και αυτό είναι λίγο πιο της [δεν ακούγεται] με το οποίο είστε
απρόσεκτος με το πρόβλημα που τέσσερις.
Σήμερα αρχίζουμε να κοιτάξουμε λίγο πιο βαθιά σε αυτά τα πράγματα που ονομάζεται δείκτες,
το οποίο ακόμα κι αν είναι μια όμορφη απόκρυφες θέμα,
αποδεικνύεται ότι πρόκειται να είναι τα μέσα με τα οποία θα
μπορεί να ξεκινήσει την κατασκευή και τη συναρμολόγηση πολύ πιο εξελιγμένα προγράμματα.
Αλλά το κάναμε για την περασμένη Τετάρτη μέσω κάποιας πλαστελίνης πρώτα.
Έτσι αυτό, ανάκληση, είναι Binky και τον χρησιμοποίησε
να ρίξετε μια ματιά σε ένα πρόγραμμα που στην πραγματικότητα δεν κάνει τίποτα ενδιαφέρον,
αλλά αποκάλυψε μερικά προβλήματα.
Έτσι για να αρχίσει σήμερα, γιατί δεν περπατάμε γρήγορα μέσα από μερικά από αυτά τα βήματα,
προσπαθήστε να αποστάξει σε όρους ανθρώπου ακριβώς τι συμβαίνει εδώ
και γιατί αυτό είναι κακό, και στη συνέχεια να προχωρήσουμε και πραγματικά να αρχίσει την οικοδόμηση κάτι
με αυτήν την τεχνική;
Έτσι, αυτές ήταν οι πρώτες δύο γραμμές σε αυτό το πρόγραμμα
και σε απλή γλώσσα, αυτό κάνουν αυτοί οι δύο γραμμές;
Κάποιος που είναι αρκετά άνετο με ό, τι δηλώνεται στην οθόνη;
Ποιες είναι αυτές οι δύο γραμμές να κάνει;
Δεν είναι ό, τι διαφορετικό από μία εβδομάδα,
αλλά υπάρχει κάποια νέα ειδική σύμβολο.
Ναι;
Πίσω εκεί.
>> Κοινό: Δηλώνοντας δείκτες;
DAVID Malan: Πείτε ξανά;
Κοινό: Δηλώνοντας δείκτες;
DAVID Malan: Δηλώνοντας δείκτες και ας το περιορίσετε λίγο περισσότερο.
Κοινό: [δεν ακούγεται] διεύθυνση x και, στη συνέχεια, y.
DAVID Malan: Και να τα αντιμετωπίσει.
Έτσι, συγκεκριμένα, τι κάνουμε είναι που δηλώνει δύο μεταβλητές.
Αυτές οι μεταβλητές, όμως, πρόκειται να είναι του τύπου int αστέρων, το οποίο
πιο συγκεκριμένα σημαίνει πρόκειται για την αποθήκευση
Η διεύθυνση ενός int, αντίστοιχα, Χ και Υ.
Τώρα είναι οποιεσδήποτε τιμές υπάρχουν;
Υπάρχουν πραγματικές διευθύνσεις σε αυτές υπάρχει δύο μεταβλητές σε αυτό το χρονικό σημείο;
Κανένα.
Είναι ακριβώς το λεγόμενο τιμές σκουπίδια.
Αν δεν ορίσετε μια πραγματικότητα μεταβλητή, ό, τι ήταν στη μνήμη RAM
προηγουμένως δεν πρόκειται να γεμίσει με μηδενικά και αυτοί οι δύο από αυτές τις μεταβλητές.
Αλλά εμείς δεν γνωρίζουμε ακόμη τι είναι και ότι είναι
πρόκειται να είναι το κλειδί για τους οποίους Binky έχασε το κεφάλι του την περασμένη εβδομάδα.
>> Έτσι, αυτό ήταν το πλαστελίνης ενσάρκωση αυτής της
σύμφωνα με την οποία έχετε μόνο δύο μεταβλητές, λίγο κυκλική κομμάτια από πηλό,
ότι μπορεί να αποθηκεύσει τις μεταβλητές, αλλά ως οι τυλιγμένη βέλη δείχνουν,
δεν είστε πραγματικά δείχνει οπουδήποτε γνωστές per se.
Μέχρι τότε είχαμε αυτή τη γραμμή, και αυτό Ήταν νέα την περασμένη εβδομάδα, malloc για τη μνήμη
κατανομής, το οποίο είναι μόνο ένα φανταχτερό τρόπο του λέει το λειτουργικό σύστημα, το Linux
ή Mac OS ή Windows, hey, να μου δώσει κάποια μνήμη,
και το μόνο που έχετε να πείτε το λειτουργικό σύστημα
είναι ό, τι όταν ζητούν τη μνήμη.
Δεν πρόκειται να με νοιάζει τι θα πάμε να κάνει με αυτό,
αλλά εσείς πρέπει να πει το λειτουργικό το σύστημα αυτό μέσω της malloc.
Ναι;
>> Κοινό: Πόσο;
DAVID Malan: Πόσο;
Πόσο σε bytes, και έτσι, αυτό, και πάλι, μια σκηνοθετημένη παράδειγμα, είναι ακριβώς λέει,
να μου δώσει το μέγεθος ενός int.
Τώρα, το μέγεθος ενός int είναι τέσσερα byte ή 32 bit.
Έτσι, αυτό είναι απλώς ένας τρόπος λέγοντας, hey, το λειτουργικό σύστημα,
δώστε μου τέσσερα bytes της μνήμης που μπορώ να χρησιμοποιήσω στη διάθεσή μου,
και συγκεκριμένα, τι κάνει malloc επιστροφή με σεβασμό
σε αυτό το κομμάτι των τεσσάρων bytes;
Κοινό: Διεύθυνση;
DAVID Malan: Η διεύθυνση.
Η διεύθυνση του εν λόγω κομμάτι των τεσσάρων bytes.
Ακριβώς.
Και έτσι αυτό είναι που αποθηκεύονται τελικά στο x και γι 'αυτό δεν το κάνουμε πραγματικότητα
με νοιάζει τι ο αριθμός των ότι διεύθυνση είναι, είτε πρόκειται για ΟΧ1 ή ΟΧ2
ή κάποια αινιγματικά διεύθυνση δεκαεξαδική.
Εμείς απλά ενδιαφέρονται εικαστικά ότι η μεταβλητή x είναι τώρα
που δείχνουν προς αυτή κομμάτι της μνήμης.
Έτσι, το βέλος αντιπροσωπεύει ένα δείκτη, ή πιο συγκεκριμένα, μια διεύθυνση μνήμης.
Αλλά και πάλι, δεν με νοιάζει συνήθως ποιοί είναι αυτοί οι πραγματικές διευθύνσεις.
Τώρα, αυτή η γραμμή λέει ό, τι σε απλή γλώσσα;
Αστέρι x παίρνει 42 ερωτηματικό.
Τι σημαινει αυτο?
Θες να πάμε;
Μην ξύνετε το λαιμό σας.
>> ΚΟΙΝΟ: Η διεύθυνση του x είναι στο 42.
>> DAVID Malan: Η διεύθυνση του x είναι 42.
Όχι αρκετά.
Τόσο κοντά, αλλά όχι αρκετά, γιατί δεν υπάρχει το αστέρι που είναι το πρόθεμα αυτό το x.
Πρέπει λοιπόν να προσαρμόσεις λίγο.
Ναι;
>> ΚΟΙΝΟ: Η τιμή που το δείκτης χ δείχνει να είναι 42.
DAVID Malan: OK.
Η αξία ότι ο δείκτης χ είναι επισημαίνοντας, ας πούμε, θα είναι 42,
ή με άλλα λόγια, το αστέρι x λέει, πάμε για οποιαδήποτε διεύθυνση
είναι στο x, αν είναι 1 Οξφόρδη Οδός ή 33 Oxford Street
ή OX1 ή ox33, ανεξαρτήτως ότι η αριθμητική διεύθυνση είναι,
αστέρων x είναι η εύρεση τιμών του x.
Έτσι πάει σε αυτή τη διεύθυνση και στη συνέχεια, τοποθετήστε τον αριθμό 42 εκεί.
Έτσι, αυτό θα ήταν ένα ισοδύναμο τρόπος για να πούμε ότι.
Έτσι ώστε να είναι όλα ωραία και, στη συνέχεια, θα αντιπροσωπεύει την εικόνα
ως εξής: όπου έχουμε προσθέσει το 42 σε αυτό το κομμάτι των τεσσάρων
bytes στην δεξιά πλευρά, αλλά αυτή η γραμμή ήταν όταν πήγαν στραβά τα πράγματα
και το κεφάλι του Binky έσκασε off σε αυτό το σημείο,
επειδή κακά πράγματα συμβαίνουν όταν Σας dereference τιμές σκουπίδια
ή μπορείτε dereference άκυρο δείκτες, και το λέω άκυρο
επειδή σε αυτό το σημείο η ιστορία, τι είναι μέσα στην ομάδα;
Ποια είναι η τιμή του y με βάση για τα τελευταία βήματα;
Ναι;
Τι είναι αυτό?
>> Κοινό: Μια διεύθυνση.
DAVID Malan: Μια διεύθυνση.
Θα πρέπει να είναι μια διεύθυνση αλλά την έχω προετοιμαστεί;
Έτσι, δεν έχω ακόμα.
Έτσι, αυτό που είναι γνωστό ότι είναι εκεί μέσα;
Είναι απλά κάποια αξία σκουπίδια.
Θα μπορούσε να είναι οποιαδήποτε διεύθυνση από μηδέν έως 2 δισεκατομμύρια, αν έχετε δύο συναυλίες της μνήμης RAM,
ή μηδέν έως 4 δισ αν έχετε πήρε τέσσερα gigabytes μνήμης RAM.
Είναι κάποια αξία σκουπίδια, αλλά το πρόβλημα είναι
ότι το λειτουργικό σύστημα, αν δεν σας έχει δώσει
ότι κομμάτι της μνήμης ειδικά ότι προσπαθείτε να πάνε,
είναι γενικά πρόκειται να προκαλέσουν προβλήματα που έχουμε δει ως σφάλμα κατάτμησης.
Έτσι, στην πραγματικότητα, καμία από εσάς που έχετε αγωνίστηκε σε προβλήματα σε ώρες γραφείου
ή σε προβλήματα που είναι πιο γενικά με την προσπάθεια να καταλάβω
ένα σφάλμα κατάτμησης, αυτό σημαίνει ότι σε γενικές γραμμές
είστε σε επαφή με ένα τμήμα του μνήμη που δεν πρέπει να είναι.
Είσαι μνήμης που αγγίζουν το λειτουργικό σύστημα δεν έχει
επιτρέπεται να αγγίξει, αν είναι πηγαίνοντας πολύ μακριά σειρά σας
ή που αρχίζει τώρα, αν είναι επειδή είστε σε επαφή με
μνήμη που είναι μόνο κάποια αξία σκουπίδια.
>> Έτσι κάνει αστέρων x εδώ είδος απροσδιόριστη συμπεριφορά.
Δεν πρέπει ποτέ να το κάνω γιατί αποδόσεις Οι, το πρόγραμμα είναι ακριβώς πρόκειται να συντρίψει,
γιατί λέτε, πηγαίνετε σε αυτή τη διεύθυνση
και δεν έχετε καμία ιδέα για το πού ότι η διεύθυνση είναι στην πραγματικότητα.
Έτσι, το λειτουργικό σύστημα είναι πιθανό πρόκειται να συντρίψει το πρόγραμμά σας
ως αποτέλεσμα και μάλιστα, αυτό είναι τι συνέβη εκεί για να Binky.
Έτσι, τελικά, Binky σταθερό Το πρόβλημα με αυτό.
Έτσι, αυτό το ίδιο το πρόγραμμα ήταν λανθασμένη.
Αλλά αν το είδος προχωρήσουμε και να εκτελέσει αυτή τη γραμμή αντ 'αυτού,
y ισούται με x ακριβώς σημαίνει ανεξαρτήτως διεύθυνση είναι x, το έβαλε επίσης στην ομάδα.
>> Και έτσι με εικόνες, έχουμε εκπροσωπούμενη αυτό με δύο βέλη
από το x και y από κατάδειξης στο ίδιο μέρος.
Έτσι σημασιολογικά, x είναι ίσο για y γιατί και τα δύο
αποθηκεύετε τον ίδιο διεύθυνση, ergo δείχνοντας 42,
και τώρα, όταν λέτε αστέρων y, μεταβείτε στη διεύθυνση y,
αυτό έχει μια ενδιαφέρουσα παρενέργεια.
Έτσι, η διεύθυνση του y είναι η ίδιο πράγμα όπως η διεύθυνση x.
Έτσι, αν σας πω πηγαίνετε στη διεύθυνση στο y και αλλάξτε την τιμή σε 13,
Ποιος άλλος επηρεάζεται;
Χ, το σημείο Δ, να το πω έτσι, θα πρέπει επίσης να επηρεαστούν.
>> Και πράγματι, πώς ο Nick επέστησε αυτή την εικόνα σε πλαστελίνης ήταν ακριβώς αυτό.
Ακόμα κι αν ακολουθούμε το δείκτη y, καταλήξαμε στο ίδιο μέρος,
και έτσι αν ήμασταν για να εκτυπώσετε έξω x ή y pointee του,
Στη συνέχεια θα δούμε την αξία του 13.
Τώρα, λέω να pointee συνεπής με το βίντεο.
Προγραμματιστές, για να μου γνώση, στην πραγματικότητα ποτέ δεν
πω τη λέξη pointee, αυτό που είναι μυτερό
σε, αλλά για λόγους συνέπειας με το βίντεο, να συνειδητοποιήσουν
αυτό είναι όλο που ήταν εννοείται σε αυτή την κατάσταση.
Έτσι, οποιεσδήποτε ερωτήσεις σχετικά με πλαστελίνης ή δείκτες ή malloc ακριβώς ακόμα;
Κανένα?
Εντάξει.
>> Έτσι, χωρίς περαιτέρω φασαρία, ας ρίξουμε μια ματιά
πού αυτό έχει πράγματι έχουν χρησιμοποιηθεί για κάποιο χρονικό διάστημα.
Έτσι είχαμε αυτή τη βιβλιοθήκη CS50 ότι πήρε όλες αυτές τις λειτουργίες.
Έχουμε χρησιμοποιήσει GetInt πολλά, GetString, πιθανώς GetLongLong νωρίτερα
σε PSET μου μία ή έτσι, αλλά τι πραγματικά συμβαίνει;
Λοιπόν, ας ρίξουμε μια γρήγορη ματιά κάτω από την κουκούλα σε ένα πρόγραμμα που
εμπνέει γιατί θα σας δώσει το CS50 βιβλιοθήκη, και μάλιστα από την περασμένη εβδομάδα,
αρχίσαμε να παίρνουμε εκείνες ρόδες μακριά.
Έτσι, αυτό είναι τώρα ταξινομημένο του μετά θάνατον για το τι
έχει ξεκινήσει στο εσωτερικό της βιβλιοθήκης CS50,
παρόλο που τώρα θα αρχίσει να κινείται μακριά από αυτό για τα περισσότερα προγράμματα.
>> Έτσι, αυτό είναι ένα πρόγραμμα που ονομάζεται scanf 0.
Είναι εξαιρετικά σύντομη.
Έχει ακριβώς αυτές τις γραμμές, αλλά εισάγει μια λειτουργία που ονομάζεται scanf
ότι είμαστε πραγματικά πρόκειται να δούμε σε μια στιγμή στο εσωτερικό της βιβλιοθήκης CS50,
αν και με ελαφρώς διαφορετική μορφή.
Έτσι, αυτό το πρόγραμμα στη γραμμή 16 η οποία μια μεταβλητή x.
Έτσι δώστε μου τέσσερα byte για έναν int.
Είναι πει χρήστη, αριθμό παρακαλώ, και στη συνέχεια,
Αυτή είναι μια ενδιαφέρουσα γραμμή ότι στην πραγματικότητα ενώνει την περασμένη εβδομάδα
και αυτό.
Scanf, και στη συνέχεια παρατηρήσετε ότι παίρνει ένα συμβολοσειρά μορφοποίησης, όπως printf,
% i σημαίνει int, και στη συνέχεια να παίρνει ένα Το δεύτερο επιχείρημα το οποίο φαίνεται λίγο
funky.
Είναι ampersand x, και να θυμηθούμε, είδαμε μόνο μια φορά την περασμένη εβδομάδα.
Τι εμπορικό και χ αντιπροσωπεύουν;
Τι κάνουμε σε εμπορικό και C;
Ναι;
>> ΚΟΙΝΟ: Η διεύθυνση της.
DAVID Malan: Η διεύθυνση της.
Έτσι είναι το αντίθετο του φορέα αστέρων,
ενώ ο χειριστής αστέρι λέει, πηγαίνετε στο Αυτή η διεύθυνση, το εμπορικό και χειριστή
λέει, να καταλάβω το διεύθυνση αυτής της μεταβλητής,
και έτσι αυτό είναι το κλειδί, επειδή Σκοπός scanf στη ζωή
είναι να σαρώσει το χρήστη είσοδο από το πληκτρολόγιο,
ανάλογα με ό, τι αυτός ή αυτή τύπων, και στη συνέχεια να διαβάσουμε είσοδο του χρήστη
σε μια μεταβλητή, αλλά εμείς είδε στις τελευταίες δύο εβδομάδες
ότι η λειτουργία εναλλαγής που θα Προσπάθησα αβίαστα να εφαρμόσουν
ήταν απλά σπασμένα.
Υπενθυμίζεται ότι με τη λειτουργία εναλλαγής, αν δηλώσαμε απλά Α και Β όπως ints,
κάναμε με επιτυχία το ανταλλάξετε δύο μεταβλητές μέσα της ανταλλαγής
ακριβώς όπως με το γάλα και ΕΕ, αλλά μόλις επέστρεψε ανταλλαγής,
ποιο ήταν το αποτέλεσμα σε σχέση με στο x και y, οι αρχικές τιμές;
Τίποτα.
Ναι.
Τίποτα δεν συνέβη εκείνη την εποχή, επειδή swaps αλλάξετε μόνο τοπικά αντίγραφα της,
που είναι να πω, όλα αυτή τη φορά, κάθε φορά που έχουμε
έχουν περνώντας επιχειρήματα τις λειτουργίες, είμαστε
απλά περνώντας τα αντίγραφα αυτών των επιχειρημάτων.
Μπορείτε να το κάνετε με αυτό ό, τι θέλετε με αυτά,
αλλά πρόκειται να έχει καμία επίδραση επί των αρχικών τιμών.
Έτσι, αυτό είναι προβληματικό, αν θέλουν να έχουν μια λειτουργία όπως scanf
στη ζωή, σκοπός του οποίου είναι να σαρώσει εισόδου του χρήστη από το πληκτρολόγιο
και στη συνέχεια να συμπληρώσετε τα κενά, έτσι ώστε να μιλούν, δηλαδή, να δώσει μια μεταβλητή, όπως x
μια τιμή, γιατί αν ήμουν για να περάσει ακριβώς x για να scanf,
αν σκεφτεί κανείς τη λογική της τελευταίας εβδομάδα, scanf μπορεί να κάνει ό, τι θέλει
με ένα αντίγραφο του x, αλλά δεν μπορούσε για να αλλάξετε μόνιμα χ, εάν δεν δώσουμε
Scanf ένα χάρτη θησαυρού, να το πω έτσι, όπου x σηματοδοτεί το σημείο, σύμφωνα με την οποία
περνάμε στη διεύθυνση του x ώστε scanf μπορεί να πάει εκεί και πραγματικά αλλαγή
η τιμή του x.
Και έτσι πράγματι, όλα ότι το πρόγραμμα αυτό δεν
αν κάνω scanf 0, στην πηγή μου Κατάλογο 5m, κάνουν scanf 0,
dot κάθετος scanf, αριθμός 50 παρακαλώ, ευχαριστώ για το 50.
>> Έτσι δεν είναι όλα αυτά ενδιαφέροντα, αλλά τι πραγματικά συμβαίνει
είναι ότι το συντομότερο Καλώ scanf εδώ, η τιμή του x
είναι να αλλάξει μόνιμα.
Τώρα, αυτό φαίνεται ωραίο και καλό, και στην πραγματικότητα,
Φαίνεται σαν να μην χρειάζεται πραγματικά η βιβλιοθήκη CS50 καθόλου πια.
Για παράδειγμα, ας τρέξει Αυτό για άλλη μια φορά εδώ.
Επιτρέψτε μου να το επαναλάβει για ένα δευτερόλεπτο.
Ας δοκιμάσουμε μια σειρά παρακαλώ και αντί να λέει 50 όπως πριν,
ας πούμε όχι.
Εντάξει, αυτό είναι λίγο περίεργο.
ΕΝΤΆΞΕΙ.
Και μόνο μερικές ανοησίες εδώ.
Έτσι δεν φαίνεται να χειριστεί λανθασμένες καταστάσεις.
Γι 'αυτό και πρέπει να ελάχιστα αρχή προσθέτοντας κάποιο λάθος ελέγχου
για να βεβαιωθείτε ότι ο χρήστης έχει δακτυλογραφημένες σε ένα πραγματικό αριθμό, όπως το 50,
επειδή προφανώς πληκτρολογώντας λέξεις δεν αναγνωρίζεται ως προβληματική,
αλλά μάλλον θα πρέπει να είναι.
>> Ας ρίξουμε μια ματιά σε αυτή την έκδοση τώρα που είναι προσπάθειά μου να reimplement GetString.
Αν scanf έχει όλα αυτά λειτουργικότητα χτίστηκε το,
γιατί έχουμε απρόσεκτος με αυτούς ρόδες όπως GetString;
Λοιπόν, εδώ είναι ίσως το δικό μου απλή έκδοση του GetString
όπου πριν από μία εβδομάδα, μπορεί να έχω πει, να μου δώσει μια σειρά και να το ονομάσουμε buffer.
Σήμερα, είμαι πρόκειται να ξεκινήσει μόνο λέγοντας αστέρων char, η οποία, ανάκληση,
είναι ακριβώς συνώνυμες.
Φαίνεται πιο τρομακτικός αλλά είναι ακριβώς το ίδιο πράγμα.
Έτσι, δώστε μου μια μεταβλητή που ονομάζεται ρυθμιστικό ότι πρόκειται να αποθηκεύσετε ένα string,
πείτε το string χρήστης παρακαλούμε, και, στη συνέχεια, ακριβώς όπως πριν,
ας προσπαθήσουμε να δανειστεί αυτό το μάθημα scanf % s αυτή τη φορά και στη συνέχεια να περάσει σε ρυθμιστικό διάλυμα.
Τώρα, ένα γρήγορο έλεγχο λογικότητας.
Γιατί δεν λέμε εμπορικό και ρυθμιστικό αυτή τη φορά;
Συναγάγει από το προηγούμενο παράδειγμα.
Κοινό: Χαρ αστέρι είναι ένας δείκτης.
DAVID Malan: Ακριβώς, γιατί αυτή τη φορά, char
αστέρων είναι ήδη ένας δείκτης, μια διεύθυνση, εξ ορισμού αυτής της αστέρι είναι εκεί.
Και αν scanf αναμένει μια διεύθυνση, αρκεί μόνο να περάσει στο ρυθμιστικό.
Δεν χρειάζεται να πω ρυθμιστικό Ampersand.
Για τους περίεργους, θα μπορούσατε κάνει κάτι τέτοιο.
Θα έχουν διαφορετικό νόημα.
Αυτό θα σας δώσει ένα δείκτη σε ένα δείκτη, το οποίο είναι πραγματικά
μια έγκυρη πράγμα σε C, αλλά για τώρα, ας το κρατήσουμε απλό
και να κρατήσει την ιστορία συνεπής.
Είμαι ακριβώς πρόκειται να περάσει σε buffer και αυτό είναι σωστό.
Το πρόβλημα είναι όμως αυτό.
Επιτρέψτε μου να πάει μπροστά και να τρέξει αυτό προγράμματος μετά τη μεταγλώττιση.
Κάντε scanf 1.
Γαμώτο, compiler μου πιάσει λάθος μου.
Δώσε μου ένα δευτερόλεπτο.
Κλαγγή.
Ας πούμε scanf-1.γ.
ΕΝΤΆΞΕΙ.
Εκεί πάμε.
Το χρειάζομαι.
CS50 ID έχει διάφορες ρυθμίσεις διαμόρφωσης
ότι προστατεύουν από τον εαυτό σας.
Έπρεπε να απενεργοποιήσετε εκείνα από τρέχει κλαγγή το χέρι αυτή τη φορά.
Έτσι κορδόνι παρακαλώ.
Πάω να πάει μπροστά και πληκτρολογήστε στην αγαπημένη μου γεια κόσμο.
Εντάξει, null.
Αυτό δεν είναι αυτό που πληκτρολογήσατε.
Γι 'αυτό είναι ενδεικτικό της κάτι που είναι λάθος.
Επιτρέψτε μου να πάω μπροστά και πληκτρολογήστε σε μια πολύ μακρά σειρά.
Ευχαριστώ για τη μηδενική και δεν ξέρω αν Πάω να είναι σε θέση να συντρίψει.
Ας δοκιμάσουμε ένα μικρό αντίγραφο επικόλληση και να δούμε αν αυτό βοηθάει.
Απλά επικολλήστε σε πολλά από αυτά.
Είναι σίγουρα ένα μεγαλύτερο κορδόνι από το συνηθισμένο.
Ας πραγματικά να το γράψει.
Κανένα.
Ανάθεμα.
Δεν βρέθηκε εντολή.
Έτσι, αυτό είναι άσχετο.
Αυτό συμβαίνει γιατί επικολληθεί κάποια κακά χαρακτήρες,
αλλά που αυτό δεν πρόκειται να λειτουργήσει.
>> Ας προσπαθήσουμε άλλη μία φορά, γιατί Είναι πιο διασκεδαστικό αν το συντριβή πραγματικότητα.
Ας το είδος αυτό και τώρα, είμαι πρόκειται να αντιγράψετε ένα πραγματικά μεγάλο κορδόνι
και τώρα ας δούμε αν μπορούμε μπορεί να διακοπεί η λειτουργία του αυτό το πράγμα.
Ανακοίνωση παρέλειψα χώρους και νέες γραμμές και ερωτηματικά
και όλα τα funky χαρακτήρες.
Enter.
Και τώρα το δίκτυο είναι ακριβώς να είναι αργή.
Κράτησα πατημένο το πλήκτρο Command-V πάρα πολύ καιρό, σαφώς.
Ανάθεμα!
Δεν βρέθηκε εντολή.
>> ΕΝΤΆΞΕΙ.
Λοιπόν, το θέμα είναι παρ 'όλα αυτά η ακόλουθη.
Έτσι, αυτό που πραγματικά συμβαίνει σχετικά με την παρούσα δήλωση
ρυθμιστικού char αστέρι στη γραμμή 16;
Έτσι, αυτό που θέλω να πω όταν δηλώνουμε έναν pointer;
Όλα τα παίρνω είναι μια τιμή τεσσάρων byte που ονομάζεται ρυθμιστικό, αλλά αυτό που είναι μέσα από αυτό
αυτή τη στιγμή?
Είναι απλά κάποια αξία σκουπίδια.
Επειδή κάθε φορά που θα δηλώσετε μια μεταβλητή σε C, είναι μερικά μόνο από τα σκουπίδια αξίας,
και αρχίζουμε να ταξίδι πάνω από αυτή την πραγματικότητα.
Τώρα, όταν λέω scanf, πηγαίνετε σε αυτή τη διεύθυνση
και βάλετε ό, τι πληκτρολογεί ο χρήστης.
Αν ο χρήστης πληκτρολογήσει σε ένα γεια κόσμο, και, όπου μπορώ να το πω;
Ρυθμιστικό είναι ένα τιμή σκουπίδια.
>> Έτσι, αυτό είναι το είδος του σαν ένα βέλος αυτό είναι που δείχνουν ποιος ξέρει πού.
Ίσως αυτό είναι που δείχνουν εδώ στη μνήμη μου.
Και έτσι όταν ο χρήστης τύποι στο hello world,
Το πρόγραμμα προσπαθεί να βάλει το κορδόνι hello world ανάποδη 0
σε αυτό το κομμάτι της μνήμης.
Αλλά με μεγάλη πιθανότητα, αλλά σαφώς δεν είναι 100% πιθανότητα,
ο υπολογιστής θα συντριβή στη συνέχεια το πρόγραμμα, διότι αυτό δεν είναι
μνήμη μου θα πρέπει να επιτρέπεται να αγγίξει.
Έτσι, με λίγα λόγια, αυτό το πρόγραμμα είναι ελαττωματική ακριβώς για αυτόν τον λόγο.
Είμαι ουσιαστικά δεν κάνει τι;
Ποια μέτρα έχουν παρέλειψα, όπως ακριβώς θα παραλειφθεί με πρώτο παράδειγμα Binky του;
Ναι;
>> Κοινό: κατανομή μνήμης;
>> DAVID Malan: κατανομή μνήμης.
Δεν έχω πραγματικά διατεθεί οποιαδήποτε μνήμη αυτής της πετονιάς.
Έτσι μπορούμε να το διορθώσω αυτό σε μια-δυο τρόπους.
Ένα, μπορούμε να το κρατήσετε απλό και στην πραγματικότητα, τώρα είστε
Θα αρχίσουμε να βλέπουμε είναι δυσδιάκριτα των γραμμών ανάμεσα στο τι
ένας πίνακας είναι, ό, τι είναι ένα string, τι char αστέρων είναι, ό, τι μια σειρά από χαρακτήρες
είναι.
Εδώ είναι ένα δεύτερο παράδειγμα που αφορούν χορδές και ειδοποίηση
όλα τα έχω κάνει on line 16 είναι, αντί να λέει
ότι το ρυθμιστικό θα είναι μια χαρα αστέρι, ένας δείκτης σε ένα κομμάτι της μνήμης,
Πάω να δώσει πολύ δυναμικά τον εαυτό μου ένα ρυθμιστικό για 16 χαρακτήρες,
και στην πραγματικότητα, εάν είστε εξοικειωμένοι με τον όρο buffering,
πιθανότατα από τον κόσμο του βίντεο, Όταν ένα βίντεο είναι ρυθμιστικό, ρυθμιστικό,
buffering.
Λοιπόν, ποια είναι η σύνδεση εδώ;
Λοιπόν, Μέσα από το YouTube και στο εσωτερικό των παικτών βίντεο
γενικά είναι ένας πίνακας αυτό είναι μεγαλύτερο από 16.
Θα μπορούσε να είναι ένας πίνακας μεγέθους ενός megabyte, ίσως 10 ΜΒ,
και σε αυτή την σειρά κάνει το πρόγραμμα περιήγησής σας κατεβάσετε ένα σωρό bytes,
ένα σωρό ΜΒ βίντεο, και το video player,
YouTube ή όποιος είναι, ξεκινά ανάγνωση του bytes από την εν λόγω διάταξη,
και κάθε φορά που θα δείτε το λέξη buffering, buffering,
αυτό σημαίνει ότι ο παίκτης έχει φτάσει στο τέλος της εν λόγω διάταξης.
Το δίκτυο είναι τόσο αργός που δεν έχει ξαναγέμισε την σειρά με περισσότερα byte
και έτσι είστε έξω από bits να εμφανιστεί στο χρήστη.
>> Έτσι ρυθμιστικό είναι μια ικανή όρος εδώ στο ότι είναι απλά ένας πίνακας, ένα μεγάλο κομμάτι της μνήμης.
Και αυτό θα το φτιάξω επειδή αποδεικνύεται
ότι μπορείτε να προσφέρετε σαν συστοιχίες είναι διευθύνσεις, παρόλο ρυθμιστικού
είναι απλώς ένα σύμβολο, είναι ένα ακολουθία χαρακτήρων, ρυθμιστικό,
ότι είναι χρήσιμο για μένα, ο προγραμματιστής, μπορείτε να περάσετε γύρω από το όνομά του
σαν να ήταν ένα δείκτη, σαν να
ήταν η διεύθυνση της κομμάτι μνήμη για 16 χαρακτήρες.
Έτσι, αυτό είναι να πω, μπορώ να περάσω η scanf ακριβώς αυτή η λέξη
και έτσι τώρα, αν κάνω αυτό το πρόγραμμα, κάνουν scanf 2, κουκίδα κάθετος scanf 2,
και πληκτρολογήστε hello world, Εισάγετε, ότι time--
>> Χμμ, τι συνέβη;
String παρακαλώ.
Τι έκανα λάθος;
Γεια σας κόσμο, ρυθμιστικό.
Γειά σου Κόσμε.
Αχ, ξέρω τι κάνει.
ΕΝΤΆΞΕΙ.
Έτσι είναι μέχρι και την ανάγνωση μέχρι την πρώτη χώρου.
Ας εξαπατήσει για μια στιγμή και πω Ήθελα απλώς να πληκτρολογήσετε κάτι
πραγματικά μεγάλο, όπως αυτό είναι μια μεγάλη πρόταση αυτό είναι ένα, δύο, τρία, τέσσερα, πέντε,
έξι, επτά, οκτώ, εννέα, 10, 11, 12, 13, 14, 15, 16.
ΕΝΤΆΞΕΙ.
Είναι πράγματι μια μεγάλη πρόταση.
Έτσι, αυτή η πρόταση είναι περισσότερο από 16 χαρακτήρες
και έτσι όταν πατήσω το enter, τι πρόκειται να συμβεί;
Λοιπόν, σε αυτή την περίπτωση η ιστορία, είχα δηλώσει ρυθμιστικό
να είναι στην πραγματικότητα μια σειρά με 16 χαρακτήρες είναι έτοιμα να ξεκινήσουν.
Έτσι, ένα, δύο, τρία, τέσσερα, πέντε, έξι, επτά, οκτώ, εννέα, 10, 11, 12, 13, 14,
15, 16.
Έτσι 16 χαρακτήρες, και τώρα, όταν read in κάτι τέτοιο είναι μια μακρά
φράση, τι πρόκειται να συμβεί είναι ότι Πάω να διαβάσω σε αυτό είναι μια μακρά
S-E-Ν-Τ-Ε-Ν-Ο-Ε, πρόταση.
>> Έτσι, αυτό είναι σκόπιμα ένα κακό πράγμα που μπορώ
συνεχίσουν να γράφουν πέραν της τα όρια του πίνακα μου,
πέρα από τα όρια του ρυθμιστικού μου.
Θα μπορούσα να πάρετε τυχεροί και το πρόγραμμα θα συνεχίσει να τρέχει και δεν με νοιάζει,
αλλά μιλώντας γενικά, αυτό Θα διακοπεί η λειτουργία πράγματι το πρόγραμμά μου,
και είναι ένα σφάλμα το οποίο μου κωδικοποιήσει τη στιγμή που μπαίνω
πέρα από τα όρια της εν λόγω διάταξης, γιατί
Δεν ξέρω αν είναι κατ 'ανάγκη θα συντριβή
ή αν είμαι απλώς πρόκειται να πάρετε τυχεροί.
Έτσι, αυτό είναι προβληματικό, διότι σε Στην περίπτωση αυτή, δεν φαίνεται να εργαστούν
και ας βάλει στον πειρασμό τη μοίρα εδώ, έστω και αν η IDE φαίνεται να ανεχθεί αρκετά
of--
>> Εκεί πάμε.
Τέλος.
Έτσι είμαι η μόνη που μπορεί να δει αυτό.
Γι 'αυτό μόλις είχε πολλή διασκέδαση πληκτρολόγηση από ένα πραγματικά μεγάλο χρονικό πραγματική φράση
ότι σίγουρα υπέρβαση 16 bytes, γιατί
δακτυλογραφημένες σε αυτό το τρελό καιρό πολλαπλών γραμμών φράση, και στη συνέχεια να παρατηρήσετε τι συνέβη.
Το πρόγραμμα προσπάθησε να το εκτυπώσετε και στη συνέχεια πήρε ένα σφάλμα κατάτμησης
και τα ελαττώματα τμηματοποίησης είναι όταν κάτι σαν αυτό που συμβαίνει
και το λειτουργικό σύστημα, λέει ο Όχι, δεν μπορεί να αγγίξει τις μνήμες.
Εμείς πάμε για να σκοτώσει το πρόγραμμα συνολικά.
>> Έτσι, αυτό φαίνεται προβληματικό.
Έχω βελτιωθεί το πρόγραμμα με το οποίο τουλάχιστον έχουν κάποια μνήμη,
αλλά αυτό φαίνεται να περιορίζεται η GetString λειτουργία για να πάρει
χορδές κάποιου πεπερασμένου μήκους 16.
Έτσι, αν θέλετε να υποστηρίξετε περισσότερο ποινές από 16 χαρακτήρες,
τι κάνεις?
Λοιπόν, μπορείτε να αυξήσετε το μέγεθος αυτού του ρυθμιστικού για 32
ή ότι φαίνεται το είδος της μικρής.
Γιατί δεν μπορούμε απλά να το 1000 αλλά σπρώξετε προς τα πίσω.
Ποια είναι η απάντηση της διαισθητικά μόλις αποφυγή αυτού του προβλήματος, κάνοντας
ρυθμιστικό μου μεγαλύτερο, όπως και 1.000 χαρακτήρες;
Με την εφαρμογή GetString με αυτόν τον τρόπο.
Τι είναι καλό ή κακό εδώ;
Ναι;
Κοινό: Αν δέσουμε πολύ του χώρου και δεν το χρησιμοποιείτε,
τότε δεν μπορεί να ανακατανείμει αυτό το χώρο.
DAVID Malan: Απολύτως.
Είναι σπατάλη στο βαθμό που, αν δεν το κάνετε πραγματικά χρειάζονται 900 αυτών των bytes
και όμως ρωτάτε για 1.000 συνολικά ούτως ή άλλως,
είστε ακριβώς καταναλώνουν περισσότερη μνήμη υπολογιστή του χρήστη από ό, τι χρειάζεστε,
Και μετά από όλα, μερικά από τα έχετε αντιμετωπίσει ήδη
στη ζωή, όταν είσαι τρέχουν πολλά προγράμματα
και από όπου και αν τρώει πολλή μνήμη, αυτό μπορεί πραγματικά να επηρεάσει την απόδοση
και την εμπειρία του χρήστη στον υπολογιστη.
Έτσι, αυτό είναι το είδος του ένα χαλαρό λύση, στα σίγουρα, και αντιστρόφως,
δεν είναι μόνο περιττή, τι πρόβλημα εξακολουθεί να παραμένει, ακόμη και αν κάνω ρυθμιστικού μου
1.000;
Ναι;
>> Κοινό: Το string είναι μήκους 1.001.
DAVID Malan: Ακριβώς.
Αν χορδών σας είναι μήκους 1.001, έχετε ακριβώς το ίδιο πρόβλημα,
και από το επιχείρημά μου, θα ήθελα μόνο τότε θα κάνει 2000,
αλλά δεν ξέρετε σε εκ των προτέρων πόσο μεγάλο πρέπει να είναι,
και όμως, έχω να καταρτίσει το πρόγραμμά μου πριν αφήσει οι άνθρωποι χρησιμοποιούν και να κατεβάσετε
αυτό.
Έτσι, αυτό είναι ακριβώς το είδος του ουσία ότι η βιβλιοθήκη προσπαθεί CS50
για να μας βοηθήσει με και θα είμαστε μόνο ματιά σε μερικά από τα πίσω από την εφαρμογή
εδώ, αλλά αυτό είναι CS50 dot C. Αυτό είναι το αρχείο που είναι ήδη σε CS50 IDE
όλες αυτές οι εβδομάδες που έχετε χρησιμοποιήσει.
Είναι προ-μεταγλωττισμένα και έχετε το χρησιμοποιεί αυτόματα
από τη φύση του έχει την παύλα L σημαία CS50 με κλαγγή,
αλλά αν μετακινηθείτε προς τα κάτω μέσα από το σύνολο των Αυτές οι λειτουργίες, εδώ είναι GetString,
και μόνο για να σας δώσει μια γεύση του τι συμβαίνει,
Ας ρίξουμε μια γρήγορη ματιά σε η σχετική πολυπλοκότητα.
Δεν είναι μια πολύ μεγάλη λειτουργία, αλλά δεν το κάναμε
Πρέπει να σκεφτούμε όλοι σκληρά για πώς να πάει για να πάρει χορδές.
>> Τόσο εδώ είναι ρυθμιστικό μου και εγώ προφανώς η προετοιμασία σε null.
Αυτό, φυσικά, είναι η ίδιο πράγμα όπως char αστέρων,
αλλά αποφάσισα για την εφαρμογή της βιβλιοθήκης CS50
ότι αν πρόκειται να είναι απολύτως δυναμική,
Δεν ξέρω εκ των προτέρων πόσο μεγάλη είναι η Οι χρήστες κορδόνι πρόκειται να θέλουν να πάρουν.
Έτσι, Πάω να ξεκινήσετε με μόνο μια κενή συμβολοσειρά
και θα πάω να δημιουργήσει τόσο πολύ μνήμη όπως έχω ανάγκη να χωρέσει το string χρήστη
και αν δεν έχω αρκετά, Πάω να ρωτήσω
το λειτουργικό σύστημα για περισσότερη μνήμη.
Πάω να κινηθεί εγχόρδων τους σε ένα μεγαλύτερο κομμάτι της μνήμης
και θα πάω να απελευθερώσει ή να απελευθερώσει το επαρκώς μεγάλο κομμάτι της μνήμης
και είμαστε ακριβώς πρόκειται για να γίνει αυτό επαναληπτικά.
>> Έτσι, μια γρήγορη ματιά, εδώ είναι απλά μια μεταβλητή
με την οποία Πάω να παρακολουθείτε της ικανότητας του ρυθμιστικού μου.
Πόσα bytes μπορώ να ταιριάζει;
Εδώ είναι μια μεταβλητή n και που Πάω να κρατήσει
παρακολουθείτε πόσα bytes είναι πραγματικά σε το ρυθμιστικό ή ότι ο χρήστης έχει πληκτρολογήσει.
Αν δεν έχετε δει πριν από αυτό, μπορείτε να καθορίσετε ότι μια μεταβλητή σαν int
είναι ανυπόγραφο, η οποία, όπως υποδηλώνει το όνομα, σημαίνει ότι είναι μη αρνητική, και γιατί θα
Ποτέ θέλετε να ασχοληθείτε προσδιορίζοντας ότι ένας int δεν είναι απλώς ένας int,
αλλά είναι ένα ανυπόγραφο int;
Είναι ένας μη αρνητικός int.
Τι σημαίνει η [δεν ακούγεται] σημαίνει;
>> Κοινό: Είναι περιγράφει ένα ποσό της μνήμης που μπορεί να είναι [δεν ακούγεται].
>> DAVID Malan: Ναι.
Έτσι, αν λέω ανυπόγραφο, αυτό είναι πραγματικά δίνοντάς σας ένα κομμάτι της επιπλέον μνήμη
και φαίνεται ότι το είδος ανόητο, αλλά αν έχουν ένα κομμάτι της επιπλέον μνήμη, ότι
σημαίνει ότι έχετε διπλάσιες τιμές που μπορεί να αντιπροσωπεύει,
επειδή μπορεί να είναι ένα μηδέν ή ένα 1.
Έτσι, από προεπιλογή, ένας int μπορεί να είναι περίπου αρνητικό 2.000.000.000 σε όλη τη διαδρομή
μέχρι θετική 2000000000.
Αυτές είναι μεγάλες κλίμακες, αλλά εξακολουθεί να είναι το είδος της σπατάλης
αν το μόνο που νοιάζονται μεγέθη, τα οποία απλά διαισθητικά
θα πρέπει να είναι μη αρνητικές ή θετική ή 0, και τότε,
γιατί εσείς σπαταλάτε 2000000000 πιθανές τιμές για τους αρνητικούς αριθμούς
αν δεν πρόκειται ποτέ να τα χρησιμοποιούν;
Έτσι, λέγοντας ανυπόγραφα, τώρα μπορείτε int μου να είναι μεταξύ 0 και περίπου 4 δισεκατομμύρια.
>> Τόσο εδώ είναι απλά ένας int C για λόγους δεν θα μπει μόλις τώρα ως
γιατί είναι ένας int αντί του κάρβουνου, αλλά εδώ είναι
η ουσία του τι συμβαίνει σχετικά, και κάποιοι από εσάς
ενδέχεται να χρησιμοποιούν, για παράδειγμα, η fgetc λειτουργία ακόμη και σε τέσσερις PSET
ή, εν συνεχεία, θα το δείτε και πάλι στο πρόβλημα που πέντε,
fgetc είναι ωραία γιατί με το όνομα του είδος, το είδος της arcanely προτείνει,
είναι μια λειτουργία που παίρνει ένα χαρακτήρα και έτσι,
τι είναι θεμελιωδώς διαφορετικό σχετικά με το τι κάνουμε στο GetString
είναι ότι δεν χρησιμοποιείτε scanf με τον ίδιο τρόπο.
Είμαστε μόνο σέρνεται μαζί βήμα-βήμα πάνω από ό, τι ο χρήστης έχει πληκτρολογήσει,
γιατί μπορεί να διαθέσει πάντα ένα char, και έτσι μπορούμε πάντα με ασφάλεια
ματιά σε ένα char σε έναν χρόνο, και η μαγεία αρχίζει να συμβεί εδώ.
Πάω να μετακινηθείτε προς τα κάτω για να η μέση αυτής της λειτουργίας
απλά να εισαγάγει εν συντομία αυτή τη λειτουργία.
Μεγάλο σαν να υπάρχει μια συνάρτηση malloc, υπάρχει
μια λειτουργία realloc όπου realloc σας επιτρέπει να ανακατανέμουν ένα κομμάτι της μνήμης
και να είναι μεγαλύτερο ή μικρότερο.
Έτσι μακρά ιστορία σύντομη και με ένα κύμα το χέρι μου για σήμερα,
γνωρίζουμε ότι αυτό GetString κάνει είναι ότι είναι είδος
της αυξανόμενης μαγικά ή συρρίκνωση του ρυθμιστικού διαλύματος καθώς ο χρήστης
τύποι στο κορδόνι του ή της.
>> Έτσι, αν ο χρήστης πληκτρολογήσει μια μικρή κλωστή, αυτός ο κώδικας
μόνο διαθέτει αρκετές μνήμη για να χωρέσει το string.
Εάν ο χρήστης κρατά πληκτρολόγηση όπως το έκανα ξανά και ξανά
και ξανά, καλά, εάν το ρυθμιστικό του αρχικά αυτό το μεγάλο
και το πρόγραμμα αντιλαμβάνεται, να περιμένετε ένα λεπτό, είμαι από το διάστημα,
πρόκειται να διπλασιαστεί το μέγεθος του buffer
και στη συνέχεια το διπλάσιο του μεγέθους του buffer και ο κώδικας που κάνει το διπλασιασμό,
αν το δούμε εδώ, είναι μόνο αυτό το έξυπνο ένα-liner.
Μπορεί να μην έχετε δει αυτήν τη σύνταξη πριν, αλλά αν λέτε αστέρων ισούται με,
αυτό είναι το ίδιο πράγμα με λέγοντας φορές χωρητικότητας 2.
Γι 'αυτό κρατά μόνο διπλασιάζοντας η ικανότητα του ρυθμιστικού
και, στη συνέχεια, λέγοντας realloc να δώσει η ίδια ότι πολύ περισσότερη μνήμη.
>> Τώρα, ως ένα μέρος, εκεί είναι άλλες λειτουργίες εδώ
ότι δεν θα εξετάσει λεπτομερώς εκτός από το να δείξει σε GetInt,
χρησιμοποιούμε GetString σε GetInt.
Θα βεβαιωθείτε ότι δεν είναι null, η οποία, ανάκληση,
είναι η ιδιαίτερη αξία που σημαίνει κάτι πήγε στραβά.
Είμαστε έξω από τη μνήμη.
Καλύτερα ελέγξτε για αυτό.
Και έχουμε επιστρέψει μια τιμή φρουρού.
Αλλά θα αναβάλει τα σχόλια ως προς το γιατί και στη συνέχεια να χρησιμοποιήσουμε αυτό τον ξάδελφό της scanf
ονομάζεται sscanf και αποδεικνύεται ότι scanf sscanf, ή κορδόνι,
σας επιτρέπει να ρίξετε μια ματιά στη γραμμή της ο χρήστης έχει πληκτρολογήσει και θα σας
αναλύσει την ουσία και τι είμαι κάνουμε εδώ είναι που λέω sscanf,
αναλύσει ό, τι ο χρήστης έχει πληκτρολογήσει στο και βεβαιωθείτε% i,
υπάρχει ένας ακέραιος σε αυτό, και δεν θα μπει σήμερα ακριβώς γιατί υπάρχει, επίσης,
α% c εδώ, αλλά με λίγα λόγια επιτρέπει μας για να ανιχνεύσει αν ο χρήστης έχει δακτυλογραφήσει
σε κάτι ψεύτικο μετά τον αριθμό.
Έτσι, ο λόγος για τον οποίο GetInt και GetString να σας πω για να ξαναπροσπαθήσετε, ξανά, δοκιμάστε ξανά
οφείλεται στο γεγονός ότι το σύνολο των ότι ο κώδικας που έχω γράψει,
Είναι το είδος του κοιτάζοντας είσοδο του χρήστη στο να διασφαλίσει ότι είναι απόλυτα αριθμητικά
ή είναι μια πραγματική Πλωτό Σημείο αξία ή τα παρόμοια,
ανάλογα με το ποια τιμή λειτουργία που χρησιμοποιείτε.
>> Μπά.
ΕΝΤΆΞΕΙ.
Αυτό ήταν μια μπουκιά αλλά το σημείο εδώ είναι
ότι ο λόγος που είχαμε αυτές οι βοηθητικές ρόδες για
οφείλεται στο γεγονός ότι στο χαμηλότερο επίπεδο, υπάρχει μόνο τόσα πολλά πράγματα που
μπορεί να πάει στραβά ότι θέλαμε να χειριστεί προληπτικά
αυτά τα πράγματα σίγουρα στο πρώτες εβδομάδες της κατηγορίας,
αλλά τώρα με το chipset τέσσερα και πέντε και PSET πέρα θα δείτε ότι είναι πιο εις
σας αλλά και είστε πιο ικανοί επίλυσης αυτών των ειδών προβλήματα
τον εαυτό σας.
Οποιεσδήποτε ερωτήσεις σχετικά με GetString ή GetInt;
Ναι;
>> Κοινό: Γιατί θα διπλασιαστεί η ικανότητα του ρυθμιστικού
όχι απλώς στην αύξηση ότι κατά το ακριβές ποσό;
>> DAVID Malan: Καλή ερώτηση.
Γιατί θα διπλασιάσει την ικανότητα του ρυθμιστικού σε αντίθεση
με απλά αυξάνοντας από κάποια σταθερή τιμή;
Ήταν μια απόφαση σχεδιασμού.
Εμείς απλά αποφάσισε ότι, επειδή τείνει να είναι λίγο ακριβό χρόνο σοφό να ρωτήσετε
το λειτουργικό σύστημα για τη μνήμη, δεν το κάναμε
θέλετε να καταλήξετε σε μια κατάσταση για μεγάλες χορδές
ότι θα ζητούσαν το λειτουργικό σύστημα ξανά και ξανά
και ξανά και ξανά σε γρήγορη διαδοχή για τη μνήμη.
Γι 'αυτό ακριβώς αποφασίσαμε, κάπως αυθαίρετα, αλλά ελπίζουμε λογικά,
ότι, ξέρετε τι, ας προσπαθήσει να πάρει μπροστά από τον εαυτό μας
και να κρατήσει μόνο διπλασιάζοντας έτσι ώστε θα ελαχιστοποιηθεί το ποσό των φορές
θα πρέπει να καλέσετε ή malloc realloc, αλλά μια συνολική κρίση
καλούν απουσία γνωρίζοντας τι οι χρήστες μπορεί να θέλουν να πληκτρολογήσετε.
Και οι δύο τρόποι θα μπορούσαν να είναι συζητήσιμο.
Αναμφισβήτητα καλό.
>> Έτσι, ας ρίξουμε μια ματιά σε ένα ζευγάρι από άλλες παρενέργειες της μνήμης,
πράγματα που μπορεί να πάει στραβά και εργαλεία που μπορείτε να
χρησιμοποιήσετε για να πιάσουν αυτά τα είδη των λαθών.
Βγάζει όλους εσάς, ακόμη και αν check50 δεν σας έχει πει τόσο πολύ,
έχουν εγγράφως λάθη Κωδικός δεδομένου εβδομάδα ένα,
ακόμη και αν όλες οι δοκιμές είναι check50 πέρασαν, και ακόμα κι αν και TF σας
είναι εξαιρετικά σίγουροι ότι κωδικό σας λειτουργεί όπως θα έπρεπε.
Ο κωδικός σας έχει λάθη ή πλημμελής ότι όλοι σας,
στη χρήση της βιβλιοθήκης CS50, έχουν διαρροή μνήμης.
Έχετε ήδη ζητήσει το λειτουργικό σύστημα για τη μνήμη στα περισσότερα από τα προγράμματα
έχετε γράψει, αλλά έχετε στην πραγματικότητα ποτέ δεν έδωσε πίσω.
Έχετε ονομάζεται GetString και GetInt και GetFloat,
αλλά με GetString, έχετε Ποτέ δεν ζήτησε unGetString ή δώστε
String Επιστροφή ή τα παρόμοια, αλλά έχουμε δει ότι GetString κάνει εκχωρήσει μνήμη
μέσω της malloc ή αυτό realloc λειτουργία, η οποία είναι μόλις
πολύ παρόμοια στο πνεύμα, και όμως, έχουμε ήδη
ζητώντας από το λειτουργικό σύστημα για μνήμη και μνήμη ξανά και ξανά
αλλά ποτέ δεν δίνουν πίσω.
>> Τώρα, ως ένα μέρος, αποδεικνύεται ότι όταν ένα πρόγραμμα τερματίζεται, όλες της μνήμης
αυτόματα απελευθερωθεί.
Έτσι δεν είναι μια τεράστια συμφωνία.
Δεν πρόκειται να σπάσει το IDE ή αργά τα πράγματα κάτω,
αλλά όταν κάνουμε προγράμματα γενικά διαρροή μνήμης
και τρέχετε για μεγάλο χρονικό διάστημα.
Αν έχετε δει ποτέ το ηλίθιο μικρό μπάλα παραλία σε Mac OS ή την κλεψύδρα
για Windows όπου είναι το είδος του επιβραδύνοντας ή σκέψης ή σκέψης
ή μόλις αρχίζει πραγματικά να επιβραδύνει σε ένα crawl,
πολύ πιθανόν θα μπορούσε να είναι το αποτέλεσμα μιας διαρροής μνήμης.
Οι προγραμματιστές που έγραψαν το λογισμικό που χρησιμοποιείτε
να ζητήσει από το λειτουργικό σύστημα για τη μνήμη κάθε λίγα λεπτά, κάθε ώρα.
Αλλά αν τρέχετε το λογισμικό, ακόμη και αν είναι
ελαχιστοποιούνται στον υπολογιστή σας για τις ώρες ή τις ημέρες στο τέλος,
ίσως να ζητά όλο και περισσότερο μνήμη και στην πραγματικότητα ποτέ δεν το χρησιμοποιεί
και έτσι τον κωδικό σας μπορεί να είναι, ή προγράμματα μπορεί να έχει διαρροή μνήμης,
και αν ξεκινήσετε να προκαλέσει απώλεια μνήμης, υπάρχει λιγότερη μνήμη για άλλα προγράμματα,
και το αποτέλεσμα είναι να επιβραδύνει τα πάντα.
>> Τώρα, αυτό είναι κατά πολύ ένα από Οι πιο αποτρόπαιες προγράμματα
θα έχετε ευκαιρίες ώστε να εκτελείται σε βαθμό CS50
όπως η παραγωγή της είναι ακόμη πιο απόκρυφα από κλαγγή ή να κάνετε ή οποιαδήποτε της εντολής
προγράμματα γραμμή που έχουμε κάνει στο παρελθόν, αλλά Ευτυχώς, που είναι ενταγμένα στην παραγωγή της
είναι μερικές χρήσιμες συμβουλές σούπερ ότι θα είναι χρήσιμο είτε για το chipset τέσσερις
ή σίγουρα το chipset πέντε.
Έτσι valgrind είναι ένα εργαλείο που μπορούν να χρησιμοποιηθούν για να δούμε
για διαρροές μνήμης στο πρόγραμμά σας.
Είναι σχετικά εύκολο να τρέξει.
Μπορείτε να εκτελέσετε valgrind και, στη συνέχεια, ακόμη και αν και είναι λίγο φλύαρο,
παύλα έλεγχο διαρροής παύλα ίσον πλήρης, και στη συνέχεια dot
κάθετο και το όνομα του προγράμματός σας.
Έτσι valgrind θα τρέξει, τότε το πρόγραμμα σας και στο τέλος του προγράμματός σας
τρέχει πριν από την παραίτησή του και σας δίνει μια άλλη γραμμή,
πρόκειται να αναλύσουμε σας πρόγραμμα, ενώ είναι ήδη σε λειτουργία
και να σας πω δεν θα διαρρεύσει κάθε μνήμη και ακόμα καλύτερα,
δεν αγγίζετε μνήμης που δεν ανήκει σε σας;
Δεν μπορεί να πιάσει τα πάντα, αλλά είναι αρκετά καλή στο να πιάσει περισσότερα πράγματα.
>> Έτσι, εδώ είναι ένα παράδειγμα που έχει τρέξιμό μου αυτό το πρόγραμμα, τα οποία έχουν διανύσει valgrind,
σε ένα πρόγραμμα που ονομάζεται μνήμη, και θα πάω
να τονίσει τις γραμμές που είναι τελικά που μας ενδιαφέρει.
Έτσι, υπάρχει ακόμη πιο περισπασμούς ότι έχω διαγραφεί από το κλείστρο.
Αλλά ας δούμε τι είναι αυτό πρόγραμμα είναι σε θέση να μας πει.
Είναι σε θέση να μας πουν τα πράγματα όπως άκυρο εγγραφής μεγέθους 4.
Με άλλα λόγια, αν αγγίξετε τη μνήμη, Ειδικότερα 4 bytes της μνήμης
ότι δεν πρέπει να έχετε, valgrind να σας πω ότι.
Άκυρη εγγραφής μεγέθους 4.
Μπορείτε άγγιξε τέσσερα bytes ότι δεν πρέπει να έχετε.
Πού το έκανες αυτό;
Αυτή είναι η ομορφιά.
Dot μνήμης γ γραμμή 21 είναι όπου μπορείτε να σκάτωσε και γι 'αυτό είναι χρήσιμο.
Μοιάζει πολύ με GDB, μπορεί να βοηθήσει το σημείο σας στο πραγματικό σφάλμα.
>> Τώρα, αυτό είναι λίγο πιο φλύαρη, αν όχι σύγχυση.
40 bytes σε 1 μπλοκ είναι σίγουρα έχασε στο αρχείο απώλειας 1 από 1.
Τι σημαίνει αυτό?
Λοιπόν, αυτό σημαίνει απλώς ζητήσατε 40 bytes και ποτέ δεν το έδωσε πίσω.
Θα ονομάζεται malloc ή καλέσατε GetString και το λειτουργικό σύστημα
σας 40 bytes, αλλά ποτέ δεν έδωσε ελευθερωθούν ή να κυκλοφορήσει ότι η μνήμη,
και για να είμαστε δίκαιοι, ποτέ δεν έχουμε δείξει πώς να δώσει πίσω τη μνήμη.
Βγάζει υπάρχει ένα σούπερ απλή λειτουργία που ονομάζεται δωρεάν.
Παίρνει ένα επιχείρημα, το πράγμα Θέλετε να απελευθερώσει ή να δώσει πίσω,
αλλά 40 bytes, προφανώς, σε αυτό το πρόγραμμα
έχουν χαθεί στη γραμμή 20 της μνήμης dot γ.
>> Ας δούμε λοιπόν αυτό το πρόγραμμα.
Είναι σούπερ άχρηστο.
Δείχνει μόνο αυτό το συγκεκριμένο σφάλμα.
Έτσι, ας ρίξουμε μια ματιά.
Εδώ είναι η κύρια και κύρια, ανακοίνωση, κλήσεις μια λειτουργία που ονομάζεται f και στη συνέχεια επιστρέφει.
Έτσι, δεν είναι όλα αυτά ενδιαφέροντα.
Τι σημαίνει στ κάνω;
Παρατηρήστε ότι δεν έκαναν τον κόπο με ένα πρωτότυπο.
Ήθελα να κρατήσει τον κωδικό όσο το δυνατό λιγότερο.
Έτσι έβαλα στ πάνω από την κύρια και ότι είναι εντάξει, σίγουρα,
για συντομία προγράμματα όπως αυτό.
Έτσι f δεν επιστρέφει τίποτα και κάνει δεν λαμβάνουν τίποτα, αλλά το κάνει αυτό.
Δηλώνει, σαν στο παράδειγμα Binky,
Ένας δείκτης που ονομάζεται x ότι πρόκειται για να αποθηκεύσετε τη διεύθυνση ενός int.
Έτσι, αυτή είναι η αριστερή πλευρά.
Στην αγγλική γλώσσα, ποια είναι η δεξιά πλευρά κάνει;
Όποιος;
Τι είναι αυτό που κάνει για μας;
Ναι;
>> Κοινό: [δεν ακούγεται] φορές το μέγεθος ενός int
η οποία είναι 10 φορές ότι [δεν ακούγεται]
DAVID Malan: Καλό και επιτρέψτε μου να συνοψίσω.
Έτσι διαθέσουν αρκετό χώρο για 10 ακέραιοι ή 10, ποιο είναι το μέγεθος ενός int,
είναι τέσσερα bytes, έτσι 10 φορές 4 40, έτσι ώστε στη δεξιά πλευρά που έχω
τονισμένο είναι να μου δώσει 40 bytes και αποθηκεύσετε τη διεύθυνση του πρώτου byte
μέσα στο x.
Και τώρα, τέλος, και εδώ είναι όπου Το πρόγραμμα αυτό είναι προβληματικό, τι είναι
λάθος με τη γραμμή 21 με βάση αυτή τη λογική;
Ποιο είναι το πρόβλημα με τη γραμμή 21;
Ναι;
Κοινό: Δεν μπορείτε δείκτη μέσα στο x [δεν ακούγεται].
DAVID Malan: Ναι.
Δεν θα πρέπει δείκτη μέσα στο x έτσι.
Έτσι συντακτικά, αυτό είναι εντάξει.
Τι ωραίο είναι, σαν σας μπορεί να θεραπεύσει το όνομα ενός πίνακα
σαν να είναι ένας δείκτης, ομοίως μπορεί να σας κεράσω ένα δείκτη, όπως κι αν είναι
μια σειρά, και έτσι μπορώ συντακτικά έστωχ βραχίονα κάτι, χ βραχίονα I,
αλλά το 10 είναι προβληματική.
Γιατί;
>> Κοινό: Επειδή δεν είναι μέσα.
>> DAVID Malan: Δεν είναι μέσα σε αυτό το κομμάτι της μνήμης.
Ποια είναι η μεγαλύτερη τιμή που θα πρέπει να πρέπει να θέτει σε αυτές τις αγκύλες;
9, 0 έως 9.
Λόγω της μηδενικής ευρετηρίασης.
Έτσι, 0 έως 9 θα ήταν μια χαρά.
Στήριγμα 10 δεν είναι καλή και αλλά, αν θυμηθούμε, κάθε φορά
Μου φαίνεται να προσπαθήσει να κάνει CS50 IDE συντριβή πληκτρολογώντας σε ψεύτικες αξίες,
δεν είναι πάντα συνεργάζονται, και μάλιστα, συχνά
πάρετε τυχεροί ακριβώς επειδή το το λειτουργικό σύστημα δεν
παρατηρήσετε ότι ποτέ τόσο ελαφρά περάσει κάποιο κομμάτι της μνήμης,
γιατί έμεινε εντός τεχνικά το τμήμα σας, αλλά περισσότερα για αυτό
Σε ένα μάθημα λειτουργικών συστημάτων, και έτσι κάτι σαν αυτό
θα μπορούσε πολύ εύκολα να περάσουν απαρατήρητα.
Το πρόγραμμά σας ποτέ δεν πρόκειται να διακοπεί η λειτουργία του σταθερά αλλά ίσως φορά σε λίγο.
>> Και γι 'αυτό ας προσπαθήσουμε valgrind για το θέμα αυτό, και εδώ είναι
όπου θα πάρουμε συγκλονισμένοι από την έξοδο στιγμιαία.
Έτσι κάνουν μνήμη ελέγχου διαρροών valgrind ίσον πλήρης μνήμη dot κάθετος.
Και είναι εδώ γιατί υπόσχομαι αυτό θα συντρίψει.
Εδώ είναι τι valgrind, εδώ είναι ό, τι προγραμματιστής, μερικά χρόνια ago-
αποφάσισε ότι θα ήταν μια καλή ιδέα Για την έξοδο για να μοιάσει.
Ας βγάλουμε νόημα από αυτό.
Έτσι, σε όλη τη διαδρομή στο αριστερό χέρι πλευρά για κανέναν καλό λόγο
είναι το ID της διεργασίας του προγράμματος εμείς απλά τρέχει, το μοναδικό αναγνωριστικό
για το πρόγραμμα που μόλις έτρεξε.
Θα διαγραφεί από ότι η διαφάνεια, αλλά υπάρχει
είναι μερικές χρήσιμες πληροφορίες εδώ.
>> Ας μετακινηθείτε προς τα επάνω στην κορυφή.
Εδώ είναι όπου ξεκινήσαμε.
Έτσι, δεν είναι όλα τόσο πολύ εξόδου.
Εδώ είναι άκυρη ότι γράφουν του μεγέθους 4 στη γραμμή 21.
Λοιπόν, τι ήταν γραμμής 21;
Γραμμή 21 ήταν ακριβώς αυτό και είναι λογικό
ότι είμαι σε έγκυρα γραπτώς 4 bytes επειδή είμαι
προσπαθεί να βάλει αυτό το ακέραιο, η οποία θα μπορούσε να είναι οτιδήποτε,
αυτό συμβαίνει ακριβώς να είναι το μηδέν, αλλά εγώ προσπαθώ
για να το θέσω σε μια θέση ότι δεν ανήκει σε μένα.
Επιπλέον, εδώ κάτω, 40 bytes σε ένα μπλοκ χάσει οριστικά στο αρχείο 1.
Αυτό συμβαίνει γιατί όταν καλώ malloc εδώ, εγώ ποτέ δεν είναι δωρεάν πραγματικά τη μνήμη.
>> Λοιπόν, πώς μπορούμε να το διορθώσω αυτό;
Επιτρέψτε μου να προχωρήσει και να είναι λίγο πιο ασφαλείς και να κάνει 9 εκεί και επιτρέψτε μου εδώ δωρεάν x.
Αυτή είναι η νέα λειτουργία για σήμερα.
Αν μου τώρα να επαναληφθεί τελεία μνήμη κάθετος, ας τρέξει valgrind σε αυτό και πάλι,
μεγιστοποιηθεί το παράθυρό μου και πατήστε Enter.
Τώρα, αυτό είναι καλό.
Θάβουν τα καλά νέα σε όλη αυτήν την έξοδο.
Όλα τα μπλοκ σωρού ήταν δωρεάν.
Θα επανέλθω σε αυτό το σωρό είναι, αλλά δεν υπάρχουν διαρροές είναι δυνατές.
Έτσι, αυτό είναι ακριβώς μια άλλη εργαλείο για την εργαλειοθήκη σας
με το οποίο μπορείτε να αρχίσετε να βρείτε τώρα τα λάθη όπως αυτό.
>> Αλλά ας δούμε τι περισσότερο μπορεί να πάει στραβά εδώ.
Ας μετάβασης τώρα πραγματικά την επίλυση ενός προβλήματος.
Παρεμπιπτόντως, αν αυτό θα ανακουφίσει την λίγο σύγχυση ή ένταση,
Αυτό είναι πλέον αστείο.
Ναι.
Αυτό είναι πολύ καλό.
Επειδή δείκτες είναι διευθύνσεις και διευθύνσεις
είναι γενικά κατά συνθήκη γραμμένο με δεκαεξαδικό.
Χα, χα, αυτό είναι αστείο πλέον.
Εν πάση περιπτώσει, ας τώρα πραγματικά να λύσει ένα πρόβλημα.
Αυτό ήταν σούπερ, σούπερ χαμηλό επίπεδο μέχρι σήμερα,
και μπορούμε πραγματικά να κάνουμε χρήσιμα τα πράγματα με αυτές τις χαμηλού επιπέδου λεπτομέρειες.
>> Γι 'αυτό και εισήγαγε μερικές εβδομάδες Πριν από την ιδέα ενός πίνακα.
Μια σειρά ήταν ωραία γιατί είναι δύσκολο να καθαρίσει τον κωδικό μας
γιατί αν ήθελε να γράψει ένα πρόγραμμα με πολλαπλά τους μαθητές
ή πολλαπλά ονόματα και τα σπίτια και κοιτώνες και κολέγια και όλα αυτά,
θα μπορούσαμε να αποθηκεύουν τα πάντα πιο καθαρά μέσα από μία συστοιχία.
Αλλά προτείνω ένα μειονέκτημα μιας συστοιχίας μέχρι στιγμής.
Ακόμα κι αν δεν έχετε υπέστη τον εαυτό σας σε ένα πρόγραμμα, απλά ενστικτωδώς,
τι είναι κακό πράγμα σχετικά με μια σειρά, ίσως;
Ακούω κάποιους μουρμουρίζει.
Κοινό: Είναι δύσκολο να αλλάξετε το μέγεθος.
DAVID Malan: Είναι δύσκολο να αλλάξετε το μέγεθος.
Δεν μπορείτε να αλλάξετε το μέγεθος μίας συστοιχίας, στην πραγματικότητα, per se
σε C. Μπορείτε να διαθέσει άλλη σειρά, μετακινήσετε τα πάντα από την παλιά
στο νέο, και τώρα έχουν κάποια επιπλέον χώρο,
αλλά δεν είναι σαν ένα γλώσσα όπως η Java ή Python
ή οποιοδήποτε αριθμό άλλων γλώσσες με τις οποίες ορισμένα από σας
μπορεί να είναι εξοικειωμένοι όπου μπορείτε μπορεί απλά να συνεχίσουμε να προσθέτουμε πράγματα
κατά κόρον στο τέλος του πίνακα.
Όταν έχετε μια σειρά από μέγεθος 6, η οποία είναι το μέγεθός του,
και τόσο πολύ όπως και η ιδέα νωρίτερα που έχει ένα ρυθμιστικό διάλυμα από ένα ορισμένο μέγεθος,
θα πρέπει να μαντέψει την πύλη τι μέγεθος θέλετε να είναι;
Αν μαντέψετε πάρα πολύ μεγάλο, σπαταλάτε χώρο.
Αν μαντέψετε πολύ μικρό, μπορείτε δεν μπορεί να αποθηκεύσει τα δεδομένα, τουλάχιστον
χωρίς πολλή περισσότερη δουλειά.
>> Έτσι, σήμερα, χάρη σε δείκτες, μπορούμε ξεκινήσετε το ράψιμο μαζί το δικό μας έθιμο
δομές δεδομένων, και Πράγματι, εδώ είναι κάτι
ότι φαίνεται λίγο περισσότερο αινιγματικά με την πρώτη ματιά,
αλλά αυτό είναι αυτό που θα ονομάσουμε ένα συνδεδεμένο λίστα και το όνομα του είδους του συνοψίζει
αυτό.
Είναι μια λίστα με τους αριθμούς, ή σε Στην περίπτωση αυτή, μια λίστα των αριθμών,
αλλά θα μπορούσε να είναι μια λίστα με τίποτα, αλλά αυτό είναι συνδέονται μεταξύ τους με τον τρόπο των βελών,
και απλά ρίξτε μια εικασία με ποια τεχνική
θα πάμε να είναι σε θέση να ενωθούν,
είδος σαν ποπ-κορν με ένα νήμα, ένα συνδεδεμένες λίστες ορθογώνια εδώ;
Αριθμούς του;
Ποιο είναι το χαρακτηριστικό υποκείμενη γλώσσα;
>> Κοινό: Ένας δείκτης.
>> DAVID Malan: Ένας δείκτης.
Έτσι, κάθε ένα από αυτά τα βέλη εδώ αντιπροσωπεύει ένα δείκτη ή απλώς μια διεύθυνση.
Έτσι με άλλα λόγια, αν θέλω για να αποθηκεύσετε μια λίστα με αριθμούς,
Δεν μπορώ να το αποθηκεύσετε αν θέλω η ικανότητα να αναπτύσσονται και να συρρικνωθεί
δομή δεδομένων μου σε μια σειρά.
Γι 'αυτό και πρέπει να έχουν μια μικρή περισσότερα επιτήδευση,
αλλά παρατηρήσετε ότι αυτό εικόνα δείχνει το είδος του
ότι αν έχετε μόνο λίγο τα θέματα που συνδέει τα πάντα μαζί,
κατά πάσα πιθανότητα δεν είναι ότι σκληρά για να κάνουν χώρο ανάμεσα σε δύο από αυτά τα ορθογώνια
ή δύο από τους κόμβους αυτούς, όπως θα αρχίσουμε αποκαλώντας τους, βάλτε σε ένα νέο κόμβο,
και στη συνέχεια με κάποιο νέο νήμα, απλά χαντάκι τις τρεις κόμβους μαζί,
η πρώτη, η τελευταία, και το ένα ότι το μόνο που παρεμβάλλεται στη μέση.
>> Και πράγματι μια συνδεδεμένη λίστα, σε αντίθεση με μια σειρά, είναι δυναμική.
Μπορεί να αναπτυχθούν και να συρρικνώνονται και δεν το κάνετε
πρέπει να γνωρίζουν ή να φροντίσει εκ των προτέρων πώς όγκο των δεδομένων που πρόκειται να αποθήκευση,
αλλά αποδεικνύεται ότι πρέπει να είμαστε λίγο προσεκτικοί για το πώς να εφαρμόσουν αυτό.
Έτσι, πρώτα ας εξετάσουμε πώς μπορούμε να εφαρμόσουν ένα από αυτά τα μικρά ορθογώνια.
Είναι εύκολο να εφαρμόσει ένα int.
Μπορείτε απλώς να πω int n και, στη συνέχεια, μπορείτε να πάρετε 4 byte για έναν int,
αλλά πώς μπορώ να πάρω έναν int, το αποκαλούν n, και στη συνέχεια ένας δείκτης, ας το ονομάσουμε επόμενο.
Θα μπορούσαμε να ονομάσουμε αυτά πράγματα οτιδήποτε θέλουμε
αλλά χρειάζομαι μια δομή προσαρμοσμένη δεδομένων.
Ναι;
>> Κοινό: Ampersand [δεν ακούγεται].
>> DAVID Malan: Έτσι εμπορικό και θα χρησιμοποιήσουμε για να λάβετε τη διεύθυνση ενός κόμβου δυνητικά.
Αλλά χρειαζόμαστε άλλο χαρακτηριστικό της C για
να μου δώσει τη δυνατότητα να δημιουργήσουν Το έθιμο αυτό ορθογώνιο, το έθιμο αυτό
μεταβλητή αν θέλετε, στη μνήμη.
Κοινό: Μια struct.
DAVID Malan: Α struct.
Ανάκληση από την περασμένη εβδομάδα, εισαγάγαμε struct, αυτή η σχετικά απλή λέξη-κλειδί
ότι μας επιτρέπει να κάνουμε τα πράγματα όπως αυτό.
C δεν ήρθε με τα δεδομένα δομή που ονομάζεται μαθητή.
Έρχεται με int και float και άνθρακας και όπως, αλλά δεν έρχεται με τον φοιτητή,
αλλά μπορούμε να δημιουργήσουμε έναν τύπο δεδομένων των μαθητών, μια δομή φοιτητής, με αυτή τη σύνταξη
εδώ.
Και θα το δείτε ξανά και ξανά.
Γι 'αυτό μην ανησυχείτε για απομνημόνευση τις λέξεις-κλειδιά,
αλλά η λέξη-κλειδί που είναι σημαντικό είναι μόνο το γεγονός ότι είπαμε struct
και στη συνέχεια κάλεσε μαθητή και μέσα του μαθητή ήταν ένα όνομα και ένα σπίτι
ή ένα dorm ή τα παρόμοια.
>> Και έτσι τώρα σήμερα, ας προτείνει κάτι τέτοιο.
Έχω προσθέσει μερικές λέξεις, αλλά αν θέλω για την εφαρμογή αυτού του ορθογωνίου που είναι
και οι δύο πήραν έναν int και ένα δείκτη, ξέρετε τι, είμαι
θα κηρύξει ένα struct που ονομάζεται κόμβος.
Είμαι, επίσης, μέσα από αυτό, πρόκειται να πω ότι ένας κόμβος, αυτό ορθογώνιο, έχει μια int
και εμείς θα το ονομάσουμε n και έχει ένα επόμενο δείκτη.
Και αυτό είναι λίγο φλύαρο, αλλά αν το σκεφτείτε,
τα βέλη που ήταν στην εικόνα πριν από λίγο είναι τι είδους δεδομένα;
Όπου κάθε μία από αυτές βέλη είναι στραμμένο σε τι είδους δομή δεδομένων;
Δεν είναι μόνο που δείχνουν προς έναν int per se.
Είναι δείχνουν προς το ολόκληρο το ορθογώνιο πράγμα
και ότι ορθογώνια πράγμα, είπαμε, ονομάζεται κόμβος.
Και γι 'αυτό το είδος πρέπει να αναδρομικά αυτής ορίζονται όπως
ότι ένα κόμβο, θα πούμε, θα περιέχει μια int που ονομάζεται n
και ένα δείκτη που ονομάζεται επόμενη και η τύπος δομής δεδομένων στην οποία
ότι τα σημεία δείκτης είναι προφανώς πρόκειται να είναι struct node.
>> Έτσι, αυτό είναι ενοχλητικά φλύαρη και ακριβώς για να είναι σχολαστικός,
ο λόγος για τον οποίο δεν μπορούμε να απλά λέω αυτό, το οποίο ειλικρινά
φαίνεται πολύ πιο ευανάγνωστη, είναι γιατί ανάκληση ότι η C διαβάσετε
πράγματα πάνω προς τα κάτω, αριστερά προς τα δεξιά.
Δεν είναι μέχρι να πάρει το ερωτηματικό ότι υπάρχει πραγματικά η λέξη-κλειδί του κόμβου.
Έτσι, αν θέλουμε να έχουμε αυτό το είδος του κυκλική αναφορά εσωτερικό των δεδομένων
δομή, πρέπει να το κάνουμε αυτό, όταν λέμε struct node στην κορυφή, η οποία
μας δίνει ένα μεγαλύτερο τρόπος περιγραφής αυτό πράγμα που, στη συνέχεια, μέσα λέμε struct node,
και στη συνέχεια στο πολύ τελευταία γραμμή ας πούμε, εντάξει, C, από τον τρόπο,
απλά καλέστε ολόκληρο αυτό το καταραμένο πράγμα που ένας κόμβος και να σταματήσει
χρησιμοποιώντας εντελώς τη λέξη-κλειδί struct.
Έτσι, αυτό είναι ακριβώς το είδος της μια συντακτική τέχνασμα που τελικά μας επιτρέπει να δημιουργήσουμε
κάτι που μοιάζει ακριβώς με αυτό.
>> Έτσι, αν υποθέσουμε τώρα μπορούμε εφαρμόσει αυτό το πράγμα C,
πώς μπορούμε πραγματικά ξεκινήστε διέρχονται αυτό;
Λοιπόν, στην πραγματικότητα, το μόνο που έχουμε να κάνουμε είναι να επαναλάβει από αριστερά προς τα δεξιά και μόλις
το είδος των κόμβων εισάγετε ή να διαγράψετε κόμβους ή αναζητήστε τα πράγματα όπου θέλουμε,
αλλά για να γίνει αυτό, ας πάει μπροστά και να κάνουν τα πράγματα λίγο πιο πραγματικό, γιατί αυτό
υπήρξε εξαιρετικά χαμηλό επίπεδο μέχρι σήμερα.
Θα μπορούσε κάποιος ήθελε κυριολεκτικά να είναι η πρώτη;
ΕΝΤΆΞΕΙ.
Έλα επάνω.
Ποιο είναι το όνομά σου?
>> DAVID: David.
DAVID Malan: David.
Χάρηκα για τη γνωριμία.
Κι εγώ.
Εντάξει.
Και χρειαζόμαστε έναν αριθμό 9.
Δεν είναι τόσο καλό όσο το πρώτο, ίσως.
Εντάξει, τον αριθμό 9.
Ένας αριθμός 17, παρακαλώ.
Επιτρέψτε μου να επιστρέψω λίγο μακρύτερα.
Αριθμός 22, παρακαλώ, και σχετικά με το πώς πιο πίσω
αν μπορώ να δω κάποιο από τα χέρια με όλο το φως ή όχι.
Κάποιος που εθελοντικά εκεί.
Θέλετε να καταλήξει;
Αντιβράχιο σας δεν θα εξαναγκάζεται να ανεβαίνει.
Εντάξει, 17.
22.
26 έρχεται προς τα κάτω.
Θα μπορούσε κάποιος άλλος ήθελε να forcefully-- Έλα επάνω.
Ένα πραγματικό εθελοντή.
>> Έτσι πολύ γρήγορα, εάν εσείς θα μπορούσε να οργανώσει
τον εαυτό σας όπως ακριβώς οι κόμβοι στην οθόνη.
Ευχαριστώ.
Και θα είναι 26.
Όλα τα δεξιά και γρήγορη εισαγωγή.
Έτσι, είμαι ο Δαβίδ και είστε επίσης;
DAVID: David.
DAVID Malan: Και είσαι;
JAKE: Τζέικ.
SUE: Sue.
ΑΛΕΞ: Αλεξ.
ΡΑΦΑΗΛ: Ραφαήλ.
TAYLOR: Taylor.
DAVID Malan: Taylor.
Εξαιρετική.
Έτσι, αυτές είναι οι εθελοντές μας για το σήμερα και να προχωρήσει
και στροφή λίγο με αυτό τον τρόπο, και απλά να προχωρήσει και να κρατήσει
κρατώντας τους αριθμούς σας καθώς είστε ή σας πρώτο σημάδι και με το αριστερό χέρι σας,
να προχωρήσει και να εφαρμόσει μόνο Αυτά τα βέλη, μόλις
έτσι ώστε το αριστερό χέρι σας είναι κυριολεκτικά δείχνει σε ό, τι πρέπει να επισημάνω
σε, και δώστε στον εαυτό σας κάποια περιθώρια έτσι ώστε μπορούμε να δούμε οπτικά τα χέρια σας πραγματικότητα
κατάδειξης, και μπορείτε να το σημείο ακριβώς είδος στο έδαφος είναι μια χαρά.
>> Έτσι, εδώ έχουμε μια συνδεδεμένη λίστα του ενός, δύο, τρεις, τέσσερις, πέντε κόμβους αρχικά,
και να παρατηρήσετε έχουμε αυτή την ειδική δείκτη στην αρχή που είναι
βασικά επειδή έχουμε να παρακολουθείτε όλη τη λίστα μήκος κάπως.
Αυτά τα παιδιά, ακόμα κι αν είστε αριστερά προς τα δεξιά, πλάτη με πλάτη στη μνήμη,
μπορούν στην πραγματικότητα να είναι οπουδήποτε στη μνήμη του υπολογιστή.
Έτσι, αυτοί οι τύποι θα μπορούσαν να είναι στέκεται οπουδήποτε στη σκηνή
και ότι είναι εντάξει, εφ 'όσον είναι στην πραγματικότητα δείχνει σε ένα άλλο,
αλλά για να κρατήσει τα πράγματα καθαρό και απλό, θα
απλά να τους επιστήσει αριστερά προς τα δεξιά, όπως αυτό, αλλά θα μπορούσαν να υπάρξουν τεράστιες ελλείψεις
μεταξύ αυτών των κόμβων.
>> Τώρα, αν θέλετε να εισάγετε στην πραγματικότητα κάποια νέα τιμή, ας πάμε μπροστά και να το κάνουμε αυτό.
Έχουμε μια ευκαιρία τώρα να επιλέξει ένα άλλο κόμβο.
Πείτε ας ξεκινήσουμε με mallocing 55.
Θα με πείραζε να είναι κάποιος malloc;
Εντάξει, έλα επάνω.
Ποιο είναι το όνομά σου?
RAINBOW: Rainbow.
DAVID Malan: Rainbow;
Εντάξει.
Malloc Rainbow.
Έλα επάνω.
Έτσι τώρα έχουμε να αναρωτηθούμε αλγοριθμικά όπου μπορούμε να βάλουμε 55.
Έτσι, όλοι μας γνωρίζουμε, Προφανώς, όπου κατά πάσα πιθανότητα
Ανήκει αν προσπαθούμε για να κρατήσει αυτό το ταξινομημένο
και αν εσείς μπορούσε να πάρει μία βήμα προς τα πίσω έτσι ώστε να μην πέσουν
το στάδιο, αυτό θα ήταν μεγάλη.
Έτσι, στην πραγματικότητα, το Rainbow, ξεκινήσει εδώ μαζί μου,
γιατί με τον υπολογιστή μπορεί τώρα δει μόνο μία μεταβλητή κάθε φορά.
Έτσι, αν αυτή είναι η πρώτη κόμβο.
Παρατηρήστε ότι δεν είναι ένας κόμβος, αυτός είναι απλά ένας δείκτης,
και αυτός είναι ο λόγος αυτός είναι που να είναι μόνο το μέγεθος ενός δείκτη, δεν
ένα από αυτά τα πλήρους ορθογώνια.
Έτσι θα πάμε για να ελέγξετε σε κάθε επανάληψη είναι μικρότερη από 55 9;
Κανένα.
Είναι μικρότερη από 55 17;
Κανένα.
Λιγότερο από 22;
Λιγότερο από 26;
Λιγότερο από 34;
Και έτσι τώρα, προφανώς Rainbow ανήκει στο τέλος.
Έτσι για να είναι σαφής, και τι ήταν το όνομά σου, Τέιλορ;
>> TAYLOR: Taylor.
DAVID Malan: Έτσι μεταξύ του Taylor το αριστερό χέρι και τα χέρια της Rainbow εδώ,
του οποίου το χέρι πρέπει να σημειωθεί σε ό, τι στην Για να εισάγετε 55 σε αυτή τη λίστα;
Τι πρέπει να κάνουμε;
Ναι;
>> Κοινό: το χέρι του Taylor Πρέπει να επισημάνω αριστερά.
>> DAVID Malan: Ακριβώς.
Έτσι, την εισαγωγή ενός κόμβου στο τέλος της λίστας
Είναι αρκετά απλό, επειδή ακριβώς Taylor πρέπει να επισημάνω, αντί στο έδαφος
ή θα το ονομάσουμε μηδενική, null είναι το είδος της απουσίας
ενός δείκτη ή ένα ειδικό μηδενικό δείκτη, είστε
πρόκειται να επισημάνω με το αριστερό σας χέρι στο Rainbow και, στη συνέχεια, Rainbow,
όπου θα πρέπει να αφήνεται σας χέρι, πιθανώς δείχνουν;
Down.
Δεν είναι καλό, αν το χέρι είναι είδος του δείχνει off εδώ ή οποιοδήποτε είδος της
προς ποια κατεύθυνση.
Αυτό θα μπορούσε να θεωρηθεί μια τιμή σκουπίδια,
αλλά εάν δείχνει κάποια γνωστή τιμή, θα
καλέστε το μηδέν ή μηδενική, αυτό είναι εντάξει γιατί έχουμε έναν όρο αυτό
και ξέρουμε ότι ο κατάλογος τώρα είναι πλήρης.
>> Έτσι τι είναι ένα άλλο σχετικά απλή υπόθεση;
Θα μπορούσαμε να malloc 5;
Έλα επάνω.
Ποιο είναι το όνομά σου?
TIFFANY: Tiffany.
DAVID Malan: Λυπάμαι;
TIFFANY: Tiffany.
DAVID Malan: Tiffany.
Εντάξει.
Tiffany έχει malloced με την τιμή 5.
Έλα επάνω.
Αυτό και μόνο είναι σχετικά εύκολο πάρα πολύ, αλλά ας εξετάσει σειρά των πράξεων τώρα.
Ήταν αρκετά εύκολο με Taylor στο τέλος.
Αριθμός 5 είναι φυσικά μικρότερη από 9, και έτσι έχουμε Ντέιβιντ, έχουμε Tiffany,
και ποιο ήταν το όνομά σας;
>> JAKE: Τζέικ.
>> DAVID Malan: Τζέικ.
Tiffany, Τζέικ, και ο David.
Του οποίου το χέρι θα πρέπει να ενημερωθεί πρώτα;
Τι θέλετε να κάνετε εδώ;
Υπάρχει ένα ζευγάρι δυνατούς τρόπους, αλλά υπάρχει επίσης ένα ή περισσότερα λάθος τρόπους.
>> Κοινό: Ξεκινήστε με αριστερότερα.
>> DAVID Malan: Ξεκινήστε με το αριστερότερο.
Ποιος είναι το αριστερότερο εδώ τότε;
Κοινό: Πρώτον.
>> DAVID Malan: OK.
Έτσι, ξεκινούν με την πρώτη και πού να κάνετε Θέλετε να ενημερώσετε τα χέρια του Δαβίδ για να είναι;
Κοινό: Προς το 5.
DAVID Malan: OK.
Έτσι ο Δαβίδ, σημείο σε πέντε ή Tiffany εδώ και τώρα;
>> Κοινό: Tiffany επισημαίνει το 9;
DAVID Malan: Τέλεια, εκτός του Binky το κεφάλι ακριβώς το είδος του έπεσε, έτσι δεν είναι;
Διότι τι είναι λάθος με Αυτή η εικόνα στην κυριολεξία;
Κοινό: Τίποτα δεν δείχνει.
DAVID Malan: Τίποτα δεν είναι επισημαίνοντας Τζέικ τώρα.
Έχουμε κυριολεκτικά ορφανά 9 και 17, και έχουμε κυριολεκτικά
διαρρεύσει όλη αυτή τη μνήμη, επειδή με ενημερώνοντας το χέρι του Δαβίδ πρώτον, ότι είναι
πρόστιμο στον βαθμό που αυτό είναι σωστά δείχνοντας Tiffany τώρα,
αλλά αν κανείς δεν είχε το προνοητικότητα να επισημάνει Τζέικ,
τότε έχουμε χάσει το όλα τα μέρη του εν λόγω καταλόγου.
Ας αναιρέσετε.
Έτσι, αυτό ήταν ένα καλό πράγμα για να σκοντάψετε αλλά ας διορθώσουμε τώρα.
Τι πρέπει να κάνουμε πρώτα αντ 'αυτού;
Ναι;
>> Κοινό: Tiffany θα πρέπει να επισημανθεί το 9;
DAVID Malan: Δεν μπορώ να να πάρει ότι κοντά σας.
Ποιος θα πρέπει να επισημανθεί το 9;
>> Κοινό: Tiffany.
>> DAVID Malan: Εντάξει.
Έτσι, θα πρέπει Tiffany πρώτο σημείο στο 9.
Έτσι θα πρέπει να λαμβάνει Tiffany στον ίδιο αξίας
με τον David, ο οποίος φαίνεται περιττή για μια στιγμή,
αλλά αυτό είναι εντάξει, επειδή τώρα, δεύτερο βήμα, να μπορέσουμε να ενημερώσουμε το χέρι του Δαβίδ
στο σημείο στο Tiffany, και στη συνέχεια, αν έχουμε ακριβώς το είδος της καθαρά τα πράγματα
όπως και αν αυτό είναι το είδος του σαν ελατήριο, τώρα αυτό είναι μια σωστή εισαγωγή.
Έτσι εξαιρετική.
Έτσι τώρα είμαστε σχεδόν εκεί.
Ας προστεθεί ένα τελικό αξίας, όπως την τιμή 20.
Αν μπορούσαμε να malloc ένα τελικό εθελοντής;
Έλα επάνω.
Έτσι, αυτό είναι λίγο πιο δύσκολο.
Αλλά πραγματικά, ο κώδικας είμαστε γραπτώς, έστω και προφορικά,
Είναι ακριβώς σαν να έχεις ένα μάτσο του αν οι συνθήκες τώρα, έτσι δεν είναι;
Είχαμε μια κατάσταση ελέγχοντας αν ανήκει
στο τέλος, ίσως στην αρχή.
Χρειαζόμαστε κάποιο είδος βρόχου να βρείτε το σημείο στη μέση.
Ας το κάνουμε αυτό με το τι είναι το όνομά σας;
>> ERIC: Eric.
>> DAVID Malan: Eric;
Έρικ.
Χάρηκα για τη γνωριμία.
Έτσι έχουμε 20.
Λιγότερο από πέντε;
Κανένα.
Λιγότερο από εννέα;
Κανένα.
Λιγότερο από 17;
Κανένα.
ΕΝΤΆΞΕΙ.
Ανήκει εδώ και τα ονόματά σας και πάλι είναι;
SUE: Sue.
DAVID Malan: Sue.
ΑΛΕΞ: Αλεξ.
DAVID Malan: Sue, Άλεξ, και;
ERIC: Eric.
DAVID Malan: Eric.
Ποιανού τα χέρια πρέπει να ενημερωθούν πρώτα;
>> Κοινό: Eric.
ΕΝΤΆΞΕΙ.
Έτσι, ο Eric θα πρέπει να επισημάνει πού;
Στα 22.
Καλή.
Και τώρα τι γίνεται στη συνέχεια;
Sue μπορεί να επισημάνει στο Eric και τώρα, αν εσείς απλά
κάνει κάποια αίθουσα, η οποία είναι μια χαρά οπτικά, τώρα έχουμε κάνει την εισαγωγή.
Ας εξετάσουμε τώρα ένα ερώτημα, αλλά σας ευχαριστώ πολύ για τους εθελοντές μας.
Πολύ καλά κάνει.
Μπορείτε να διατηρήσουμε αυτά, αν θέλετε.
Και έχουμε ένα υπέροχο δώρο χωρίστρα, αν θέλετε κάθε θέλατε να ρίξετε μια μπάλα για το άγχος.
Επιτρέψτε μου να περάσει αυτό κάτω.
Έτσι, ποιο είναι το πακέτο αυτό;
Αυτό φαίνεται να είναι καταπληκτικό στο βαθμό που έχουμε τώρα
εισήγαγε μια εναλλακτική λύση για μια συστοιχία που δεν περιορίζεται έτσι
σε μια σειρά κάποιου σταθερού μεγέθους.
Μπορούν να αναπτυχθούν δυναμικά.
>> Αλλά μοιάζει πολύ έχουμε δει σε εβδομάδες παρελθόν, δεν μπορούμε ποτέ να πάρει κάτι δωρεάν,
όπως σίγουρα υπάρχει ένα trade-off εδώ.
Έτσι, με ένα ανάποδο ενός συνδεδεμένου λίστα, είναι ο δυναμισμός;
Αυτή η ικανότητα να αναπτύσσονται και ειλικρινά, θα μπορούσαμε να είχαμε κάνει delete
και θα μπορούσαμε να συρρικνωθεί, όπως απαιτείται.
Τι τιμή πληρώνουμε;
Διπλάσιο χώρο, πρώτα απ 'όλα.
Αν κοιτάξετε την εικόνα, δεν είναι πλέον είμαι αποθήκευση ενός πίνακα ακεραίων.
Είμαι αποθήκευση μια λίστα ακέραιοι συν δείκτες.
Έτσι είμαι διπλασιάζοντας την ποσότητα του χώρου.
Τώρα, ίσως αυτό δεν είναι τέτοια ένα big deal 4 bytes, 8 bytes,
αλλά θα μπορούσε σίγουρα να προσθέσετε για μεγάλα σύνολα δεδομένων.
Τι είναι ένα άλλο μειονέκτημα;
Ναι;
>> Κοινό: Πρέπει να διασχίζουν τα ένα-ένα.
DAVID Malan: Ναι.
Πρέπει να τους διασχίσει ένα-ένα.
Ξέρεις τι, δώσαμε αυτό το σούπερ βολικό χαρακτηριστικό της αγκύλη
σημειογραφία, πιο σωστά γνωστή ως τυχαία πρόσβαση,
όπου μπορούμε να πηδήσει μόνο σε ένα επιμέρους στοιχείο
αλλά τώρα αν είχα ακόμα εθελοντές μου εδώ,
αν ήθελα να βρουν το αριθμός 22, δεν μπορώ απλά
άλμα για στήριγμα κάτι κάτι.
Θα πρέπει να κοιτάξω πάνω από τη λίστα, πολύ σαν παραδείγματα αναζήτηση μας γραμμικά,
για να βρείτε τον αριθμό 22.
Γι 'αυτό και φαίνεται να έχουν πληρώσει ένα τίμημα εκεί.
Αλλά μπορούμε ωστόσο να επίλυση άλλων προβλημάτων.
>> Στην πραγματικότητα, επιτρέψτε μου να εισαγάγει μόνο ένα ζευγάρι των visuals.
Έτσι, εάν έχετε πάει κάτω για να Mather αίθουσα του δείπνου πρόσφατα,
θα θυμάστε ότι τους στοίβες των δίσκων όπως αυτό,
έχουμε δανειστεί από αυτά Annenberg πριν το μάθημα.
Έτσι, αυτό στοίβα των δίσκων, όμως, είναι αντιπροσωπευτική πραγματικότητα
μιας δομής δεδομένων της επιστήμης των υπολογιστών.
Υπάρχει μια δομή δεδομένων στην επιστήμη των υπολογιστών
γνωστή ως μια στοίβα η οποία είναι πολύ ωραία προσφέρεται για αυτό ακριβώς το οπτικό.
Έτσι, αν κάθε ένα από αυτούς τους δίσκους δεν είναι δίσκος αλλά σαν μια σειρά και θα ήθελα
για να αποθηκεύσετε αριθμούς, Ι θα μπορούσε να θέσει ένα εδώ κάτω,
και θα μπορούσα να βάλω άλλο ένα εδώ κάτω, και να συνεχίσει στοίβαγμα αριθμούς
πάνω από το ένα το άλλο, και τι είναι δυνητικά χρήσιμο γι 'αυτό
είναι ότι ό, τι είναι η επίπτωση αυτής της δομής δεδομένων;
Ποια αριθμός μπορεί να βγάζω πρώτη πιο εύκολα;
Ο πιο πρόσφατα ένας θέσει εκεί.
>> Έτσι, αυτό είναι αυτό που θα λέγαμε σε επιστήμη των υπολογιστών μια δομή δεδομένων LIFO.
Τελευταία in, first out.
Και θα δούμε σε λίγο γιατί ότι μπορεί να είναι χρήσιμο, αλλά για τώρα,
Για σκέψου το ακίνητο.
Και είναι κάπως ανόητο αν νομίζετε σχετικά με το πώς η τραπεζαρία που κάνει.
Κάθε φορά που οι δίσκοι και τα καθαρά βάλτε τα πιο φρέσκα αυτά στην κορυφή,
θα μπορούσατε να έχετε ένα καθαρό παρελθόν αλλά τελικά είναι πολύ βρώμικο και σκονισμένο
δίσκο στο κάτω μέρος αν ποτέ πραγματικά
πάτε στο κάτω μέρος της ότι στοίβα, γιατί απλά
κρατήσει τη θέση του νέου και Τα καθαρά αυτά που πάνω του.
Το ίδιο πράγμα μπορεί να συμβεί σε ένα σούπερ μάρκετ πολύ.
Αν έχετε μια περίπτωση επίδειξης του γάλακτος και κάθε φορά που το CVS
ή όποιος παίρνει περισσότερο γάλα, μπορείτε απλά να χώσουν τα γάλατα
έχετε ήδη προς τα πίσω και βάζετε τα καινούργια μπροστά,
θα πάμε να έχουν κάποια πολύ άσχημη γάλα στο τέλος της δομής των δεδομένων,
επειδή είναι πάντα στο κάτω μέρος ή ισοδύναμα είναι πάντα στο πίσω μέρος.
>> Αλλά υπάρχει ένας άλλος τρόπος για να σκεφτούμε παράταξη δεδομένων και, για παράδειγμα, αυτό.
Αν είστε ένας από εκείνους τους ανθρώπους που του αρέσει να παρατάξει έξω από καταστήματα της Apple
όταν ένα νέο προϊόν έρχεται έξω, είστε πιθανώς
Δεν χρησιμοποιώντας μια στοίβα δεδομένων δομή γιατί
θα αποξενώσει όλοι οι άλλοι που είναι επένδυση μέχρι να αγοράσουν κάποιο νέο παιχνίδι.
Μάλλον, είστε πιθανώς χρησιμοποιώντας τι είδους δομή δεδομένων
ή τι είδους σύστημα στον πραγματικό κόσμο;
Ας ελπίσουμε ότι αυτό είναι μια γραμμή, ή περισσότερο σωστά ή περισσότεροι Βρετανοί-όπως, μια ουρά.
Και αποδεικνύεται μια ουρά είναι επίσης ένα δομή δεδομένων στην επιστήμη των υπολογιστών,
αλλά μια ουρά έχει μια πολύ διαφορετική ιδιότητα.
Δεν είναι LIFO.
Τελευταία in, first out.
Θεός φυλάξοι.
Είναι αντ 'αυτού FIFO.
First in, first out.
Και αυτό είναι ένα καλό πράγμα για τη δικαιοσύνη του Θεού,
Σίγουρα όταν είστε επένδυση up σούπερ νωρίς το πρωί.
Αν φτάσετε εκεί πρώτα, θα θέλουν να βγούμε από την πρώτη, καθώς και.
>> Και έτσι όλα αυτά τα δεδομένα δομές, ουρές και στοίβες
και τσαμπιά των άλλων, αποδεικνύεται ότι σας μπορώ να σκεφτώ αυτή, όπως ακριβώς μια σειρά.
Αυτή είναι μια συστοιχία, ίσως ένα σταθερό μέγεθος 4, αλλά θα έπαιρνα
είναι το είδος της ωραίο αν θα μπορούσαμε απλά να συσσωρεύονται δίσκους σχεδόν απείρως ψηλό αν
έχουν πολλούς δίσκους ότι ή αριθμούς.
Έτσι ίσως θέλουμε να χρησιμοποιήστε μια συνδεδεμένη λίστα εδώ,
αλλά το εμπόριο-off θα είναι ενδεχομένως ότι χρειαζόμαστε περισσότερη μνήμη,
παίρνει λίγο περισσότερο χρόνο, αλλά εμείς δεν περιορίζουν το ύψος της στοίβας,
σαν προθήκη του Mather θα μπορούσε να περιορίσει το μέγεθος της στοίβας,
και έτσι αυτά είναι αποφάσεις σχεδιασμού ή επιλογές στη διάθεσή μας τελικά.
Έτσι, με αυτά τα δεδομένα δομές, έχουμε αρχίσει
βλέπουμε νέες άνω φράγματα δυνητικά Σε ό, τι στο παρελθόν ήταν πολύ γρήγορη
και πού θα φύγουν off, όπου και σήμερα
θα ελπίζουμε να φτάσουμε είναι την Τετάρτη, θα
να αρχίσουμε να εξετάζουμε σε δεδομένα δομή που μας επιτρέπει να αναζητήσετε
μέσω των δεδομένων στο ημερολόγιο τέλος του χρόνου πάλι.
Και είδαμε ότι, υπενθυμίζουν, στο μηδέν εβδομάδα και ένα με δυαδική αναζήτηση ή συνθλίβεται
και βασίλευε.
Έρχεται πίσω και ακόμα καλύτερα, το Άγιο Δισκοπότηρο για αυτή την Τετάρτη
θα είναι να καταλήξουμε με το δομή δεδομένων που τρέχει πραγματικά
ή θεωρητικά σταθερά χρόνου, οπότε
δεν έχει σημασία πόσες εκατομμύρια ή δισεκατομμύρια των πραγμάτων
έχουμε στη δομή δεδομένων, θα να μας σταθερά χρόνου, ίσως ένα βήμα
ή δύο βήματα ή 10 βήματα, αλλά σταθερή αριθμοί των βημάτων
να αναζητήσετε μέσα από αυτή τη δομή δεδομένων.
Αυτό πράγματι θα είναι το Ιερό Δισκοπότηρο αλλά περισσότερα για αυτό την Τετάρτη.
Τα λέμε τότε.
>> [Παίζει μουσική]