[Powered by Google Translate] [Εβδομάδα 6]
[David J. Malan] [Πανεπιστήμιο του Χάρβαρντ]
[Αυτό είναι CS50.] [CS50.TV]
>> Αυτό είναι CS50, και αυτή είναι η αρχή της εβδομάδας 6,
έτσι, ένα ζευγάρι νέων εργαλείων είναι τώρα στη διάθεσή σας για να επωφεληθούν από,
η πρώτη από τις οποίες καλείται CS50 στυλ.
Οι πιθανότητες είναι, αν είστε σαν εμένα ή οποιονδήποτε από τους υποτρόφους διδασκαλίας,
έχετε δει πιθανώς ένα πρόγραμμα, του οποίου το στυλ μοιάζει λίγο κάτι σαν αυτό.
Ίσως να αρχίσετε την κοπή κάποιες γωνιές αργά το βράδυ, ή θα ασχοληθεί με το θέμα αργότερα,
και στη συνέχεια ένα TF ή CA έρχεται πάνω κατά τις ώρες γραφείου.
Στη συνέχεια, είναι δύσκολο για μας να το διαβάσετε.
Λοιπόν, αυτός ο κώδικας είναι συντακτικά σωστές, και θα συγκεντρώνει και θα τρέχουν στην πραγματικότητα.
Αλλά σίγουρα δεν είναι ένα 5 για το στυλ.
>> Αλλά τώρα, αν πάμε σε αυτόν τον κατάλογο εδώ-
και παρατηρήσετε ότι έχω conditions2.c-
και τρέχω αυτή τη νέα εντολή, style50, σε αυτό το αρχείο conditions2.c, Enter,
παρατηρήσετε ότι είναι με πληροφόρησε ότι έχει στυλιζαρισμένο.
Gedit παρατηρήσει ότι το αρχείο έχει αλλάξει στο δίσκο,
και αν κάνω κλικ reload, όλα τα προβλήματά σας τώρα αυτοματοποιημένη.
[Χειροκροτήματα]
Αυτό είναι ένα από τα πράγματα που κάναμε αυτό το Σαββατοκύριακο.
Συνειδητοποιήστε ότι είναι ατελής, διότι υπάρχουν κάποιες κώδικα
ότι απλά δεν θα είναι σε θέση να στυλιζάρω τέλεια,
αλλά συνειδητοποιούν αυτό τώρα είναι ένα εργαλείο που μπορείτε να εκμεταλλευτείτε
εάν μόνο για να βάλει τάξη σε μερικά από τα πιο errantly τοποθετούνται άγκιστρα και τα παρόμοια.
>> Αλλά το πιο συναρπαστικό είναι τώρα CS50 Έλεγχος.
Με CS50 Έλεγχος, μπορείτε να κάνετε πραγματικά τις ίδιες δοκιμές ορθότητα
για το δικό του κωδικό σας ότι οι υπότροφοι διδασκαλίας είναι σε θέση να.
Αυτό είναι ένα βοηθητικό πρόγραμμα γραμμής εντολών που έρχεται τώρα στη συσκευή
το συντομότερο κάνετε μια update50 ως ανά
PSET 4 προδιαγραφές, και μπορείτε να το χρησιμοποιήσετε κατ 'ουσίαν, όπως αυτό.
Μπορείτε να εκτελέσετε την εντολή check50.
Στη συνέχεια θα περάσει σε ένα όρισμα γραμμής εντολών, ή πιο γενικά γνωστό ως ένα διακόπτη ή μια σημαία.
Σε γενικές γραμμές, τα πράγματα που έχουν παύλες ονομάζεται διακόπτης
σε ένα πρόγραμμα γραμμής εντολών, έτσι ώστε-γ καθορίζει
οι έλεγχοι που θέλετε να εκτελέσετε.
>> Οι δοκιμές που θέλετε να εκτελέσετε με μοναδικό τρόπο από αυτή τη σειρά,
2012/pset4/resize.
Με άλλα λόγια, αυτό είναι απλώς μια αυθαίρετη, αλλά μοναδική συμβολοσειρά
που χρησιμοποιούμε για να προσδιορίσει μοναδικά δοκιμές ορθότητα PSET 4 του.
Και στη συνέχεια να ορίσετε ένα χώρο χωρίζονται λίστα με τα αρχεία που θέλετε να ανεβάσετε
να CS50 Έλεγχος για ανάλυση.
Για παράδειγμα, αν πάω σε λύση μου εδώ για resize.c-
επιτρέψτε μου να ανοίξει ένα μεγαλύτερο παράθυρο τερματικού-
και πάω μπροστά και να τρέξει ας πούμε check50-γ 2012/pset4/resize,
και τότε να προχωρήσει και να καθορίσετε τα ονόματα των αρχείων,
resize.c, και πατήστε Enter, στη συνέχεια, το συμπιέζει,
αυτό προσθήκες, ελέγχει, και εγώ απλά απέτυχε ένα σωρό εξετάσεις.
Το ένα με κόκκινα γράμματα στο πάνω αριστερά λέει ότι resize.c και bmp υπάρχουν.
Αυτή ήταν η δοκιμή. Αυτό ήταν το ερώτημα που τέθηκε.
Και είναι δυσαρεστημένοι επειδή η απάντηση ήταν ψευδείς.
Το λευκό παρακάτω κείμενο λέει bmp.h αναμένεται να υπάρχουν, και ότι είναι απλά λάθος μου.
Ξέχασα να το ανεβάσετε, γι 'αυτό πρέπει να ανεβάσετε τα αρχεία και τα δύο,
resize.c και bmp.h.
Αλλά τώρα παρατηρήσετε όλες τις άλλες δοκιμές είναι κίτρινο, επειδή δεν έχουν εκτελεστεί,
και έτσι το χαμογελαστό πρόσωπο είναι κάθετες επειδή είναι ούτε ικανοποιημένοι ούτε λυπημένος,
αλλά θα πρέπει να επανορθώσει αυτό το θέμα σε κόκκινο πριν οι λοιποί έλεγχοι που θα τρέξει.
>> Επιτρέψτε μου να το διορθώσω αυτό.
Επιτρέψτε μου σμίκρυνση και να επαναπροσδιοριστούν αυτό, αυτή τη φορά με bmp.h επίσης
στη γραμμή εντολών, Enter, και τώρα, αν όλα πάνε καλά,
πρόκειται να ελέγξει και στη συνέχεια να επιστρέψει ένα αποτέλεσμα-κρατήστε την αναπνοή σας-
όλα πράσινο, που σημαίνει κάνω πολύ καλά στις PSET 4 μέχρι τώρα.
Μπορείτε να δείτε και να συναγάγει από το περιγραφικό κείμενο εδώ
ακριβώς τι είναι αυτό που δοκιμάσαμε.
Εξετάσαμε αρχικά υπάρχουν τα αρχεία;
Στη συνέχεια δοκιμάστηκε κάνει resize.c μεταγλώττιση;
Στη συνέχεια ελέγξαμε δεν είναι το μέγεθος ενός 1x1-pixel BMP όταν n, ο συντελεστής αλλαγής μεγέθους, είναι 1.
Τώρα, αν δεν έχετε ιδέα τι είναι ν, θα τη στιγμή που θα βουτήξει PSET 4,
αλλά αυτό είναι απλά μια λογική βεβαιωθείτε ότι δεν είστε αλλαγή μεγέθους
μια εικόνα καθόλου αν ο παράγοντας αλλαγής μεγέθους είναι 1.
Εάν, αντίθετα, είναι μια αλλάζει το μέγεθος 1x1 pixel σε ένα 1x1 pixel BMP σε 2x2 σωστά
όταν το η είναι 2, τότε ομοίως, ορυχείο σχηματίζει ανάλογα.
>> Εν ολίγοις, αυτό έχει ως στόχο να, ένα, να λάβει τα διασχίζουν τα δάχτυλά
από την εξίσωση δεξιά προτού να υποβάλετε PSET σας.
Θα ξέρετε ακριβώς τι TF σας σύντομα θα γνωρίζουμε
όταν θα πάτε για την υποβολή μερικά από αυτά τα σύνολα πρόβλημα,
καθώς επίσης και το παιδαγωγικό κίνητρο είναι πραγματικά να θέσει
η ευκαιρία μπροστά σας, έτσι ώστε όταν ξέρεις εκ των προτέρων
ότι υπάρχει σφάλματα στον κώδικά σας και δοκιμές που δεν έχει μεταβιβαστεί,
μπορείτε να βάλετε σε πιο αποτελεσματική χρόνο μπροστά για να λύσει αυτά τα προβλήματα
αντί να χάσετε πόντους, να πάρει πληροφορίες από τους TF σας,
και στη συνέχεια να πάμε, "Ααα," όπως θα έπρεπε να είχα καταλάβει ότι έξω.
Τώρα τουλάχιστον υπάρχει ένα εργαλείο για να σας βοηθήσει να βρείτε αυτό.
Δεν πρόκειται να επισημάνει τα πεδία όπου το σφάλμα είναι, αλλά θα σας πω
τι είναι σύμπτωμα αυτό.
>> Τώρα συνειδητοποιούν οι δοκιμές δεν είναι κατ 'ανάγκη εξαντλητικός.
Ακριβώς επειδή μπορείτε να πάρετε μια οθόνη γεμάτη πράσινο χαμογελαστά πρόσωπα
δεν σημαίνει ότι τον κωδικό σας είναι τέλειο, αλλά αυτό δεν σημαίνει
ότι έχει περάσει ορισμένες δοκιμές που προβλέπονται από το spec.
Μερικές φορές δεν θα απελευθερώσει τους ελέγχους.
Για παράδειγμα, whodunit, μια από τις πλευρές της PSET 4,
είναι είδος απογοητευτικό αν σας δίνουμε
η απάντηση ως προς το τι είναι, και υπάρχει μια σειρά από τρόπους για να αποκαλύψει
που το άτομο είναι σε αυτό το κόκκινο θόρυβο.
Το spec θα είναι πάντα καθορίζουν στο μέλλον για PSET 5 προς τα εμπρός
τι ελέγχει υπάρχουν για εσάς.
Θα παρατηρήσετε ότι υπάρχει αυτό το λευκό URL στο κάτω μέρος.
Προς το παρόν, αυτό είναι μόνο διαγνωστική έξοδος.
Αν επισκεφθείτε το URL, θα έχετε ένα σωρό τρελοί, κρυπτογραφημένα μηνύματα
ότι είστε ευπρόσδεκτοι να κοιτάξουμε μέσα, αλλά είναι ως επί το πλείστον για το προσωπικό
έτσι ώστε να μπορούμε να διαγνώσουμε και να διορθώσετε σφάλματα σε check50 ίδια.
>> Χωρίς φασαρία, ας προχωρήσουμε εκεί που σταμάτησε.
CS50 βιβλιοθήκη πήραμε ως δεδομένο για μερικές εβδομάδες,
αλλά στη συνέχεια τελευταία εβδομάδα, αρχίσαμε ξεφλούδισμα πίσω ένα από τα στρώματα του.
Ξεκινήσαμε βάζοντας στην άκρη κορδόνι υπέρ του τι αντ 'αυτού;
[Φοιτητές] Χαρ.
Char *, η οποία έχει ένα char * όλο αυτό το διάστημα,
αλλά τώρα δεν έχουμε να προσποιούνται ότι είναι ένας πραγματικός τύπος δεδομένων συμβολοσειράς.
Μάλλον, αυτό είναι ένα συνώνυμο του είδους για char *,
και μια συμβολοσειρά είναι μια ακολουθία χαρακτήρων,
γιατί έτσι έχει νόημα να αντιπροσωπεύουν χορδές ως char * s;
Τι κάνει ένας char * εκπροσωπούν στο πλαίσιο αυτής της έννοιας της σειράς;
Ναι. >> [Φοιτητικό] Ο πρώτος χαρακτήρας.
Καλό, ο πρώτος χαρακτήρας, αλλά όχι αρκετά ο πρώτος χαρακτήρας.
Είναι οι-[Φοιτητές] Διεύθυνση.
Καλό, η διεύθυνση του πρώτου χαρακτήρα.
Το μόνο που είναι απαραίτητο για να αντιπροσωπεύουν ένα string στη μνήμη ενός υπολογιστή
είναι ακριβώς η μοναδική διεύθυνση του πρώτου byte πολύ του.
Δεν χρειάζεται καν να ξέρω πόσο καιρό είναι
γιατί πώς μπορεί κανείς να υπολογίσει ότι από δυναμικά;
[Φοιτητικό] μήκος String.
Μπορείτε να καλέσετε το μήκος συμβολοσειράς, εξαιρετική, αλλά πώς κορδόνι μήκους εργασίας;
Τι κάνει; Ναι.
[Φοιτητικό] Συνεχίστε μέχρι να φτάσετε το null χαρακτήρα.
Ναι, ακριβώς, αυτό επαναλαμβάνει απλώς με ένα βρόχο for, while loop,
όποια και αν είναι από * στο τέλος, και το άκρο εκπροσωπείται
με \ 0, το λεγόμενο nul χαρακτήρα, nul,
δεν πρέπει να συγχέεται με την μηδενική, η οποία είναι ένας δείκτης,
η οποία θα καταλήξει σε συζήτηση και πάλι σήμερα.
>> Έχουμε τη φλούδα τους πίσω από ένα στρώμα GetInt, και στη συνέχεια πήραμε μια ματιά στο GetString,
και υπενθυμίζουν ότι και οι δύο αυτές λειτουργίες, ή πραγματικά,
GetString, ήταν χρησιμοποιώντας μια συγκεκριμένη λειτουργία
πραγματικά να αναλύσει, που είναι, να διαβάσετε ή να αναλύσει, η είσοδος του χρήστη.
Και αυτό ήταν ότι η νέα λειτουργία;
Scanf ή sscanf. Έρχεται πραγματικά σε μερικές διαφορετικές γεύσεις.
Υπάρχει scanf, υπάρχει sscanf, υπάρχει fscanf.
Προς το παρόν, όμως, ας επικεντρωθεί σε αυτό που φαίνεται πιο εύκολα,
και επιτρέψτε μου να προχωρήσει και να ανοίξει στη συσκευή
ένα αρχείο σαν αυτό, scanf1.c.
Αυτό είναι ένα εξαιρετικά απλό πρόγραμμα,
αλλά αυτό κάνει κάτι που ποτέ δεν έχω κάνει
χωρίς τη βοήθεια της βιβλιοθήκης CS50.
Αυτό παίρνει ένα int από ένα χρήστη. Πώς λειτουργεί;
Λοιπόν, σε γραμμή 16 εκεί,
παρατηρήσετε ότι έχουμε κηρύξει ονομάζεται int x, και σε αυτό το σημείο στην ιστορία,
ποια είναι η τιμή του χ;
[Ακούγεται ανταπόκριση των φοιτητών]
[David M.] Δεξιά, ποιος ξέρει, κάποια αξία σκουπίδια δυνητικά, έτσι ώστε σε 17, θα πω μόνο το χρήστη
να μου δώσει έναν αριθμό, παρακαλώ, και το βήμα 18 είναι όπου παίρνει ενδιαφέρον.
Scanf φαίνεται να δανειστεί μια ιδέα από την printf στο ότι χρησιμοποιεί αυτούς τους κωδικούς μορφή σε εισαγωγικά.
Δ% είναι φυσικά ένας δεκαδικός αριθμός.
Αλλά γιατί είμαι περνώντας & x όχι μόνο x;
Το πρώτο είναι σωστή. Ναι.
[Ακούγεται ανταπόκριση των φοιτητών]
Ακριβώς, αν ο στόχος αυτού του προγράμματος, όπως και η ίδια η λειτουργία GetInt,
είναι να πάρετε μια int από το χρήστη μπορώ να περάσει λειτουργίες
όλες οι μεταβλητές που θέλω, αλλά αν δεν τα περνούν με αναφορά
ή κατά διεύθυνση ή με δείκτη, όλα συνώνυμο για τους σκοπούς του σήμερα,
τότε αυτή η λειτουργία δεν έχει τη δυνατότητα να αλλάξετε τα περιεχόμενα αυτής της μεταβλητής.
Αυτό θα περάσει σε ένα αντίγραφο ακριβώς όπως το buggy έκδοση της ανταλλαγής
ότι έχουμε μιλήσει για μερικές φορές μέχρι τώρα.
>> Αλλά αντ 'αυτού, κάνοντας & x, είμαι κυριολεκτικά περνώντας σε ό, τι;
[Φοιτητικό] Η διεύθυνση. >> Η διεύθυνση του x.
Είναι σαν την κατάρτιση ενός χάρτη για τη λειτουργία που ονομάζεται scanf και λέει εδώ,
κατευθύνσεις αυτές είναι σε ένα κομμάτι της μνήμης του υπολογιστή
ότι μπορείτε να πάτε αποθηκεύσει έναν ακέραιο μέσα
Προκειμένου για sscanf να κάνω τώρα που
τι χειριστή, τι κομμάτι της σύνταξης είναι αυτό που θα πρέπει να χρησιμοποιήσετε
ακόμα κι αν δεν μπορούμε να δούμε επειδή κάποιος άλλος έγραψε αυτή τη λειτουργία;
Με άλλα λόγια - τι είναι αυτό;
[Φοιτητικό] X διαβάσετε.
Υπάρχει πρόκειται να είναι κάποια ανάγνωση, αλλά μόνο όσον αφορά x εδώ.
Αν scanf είναι να περάσει τη διεύθυνση του x,
συντακτικά, τι χειριστής είναι βέβαιο ότι θα υπάρχουν κάπου
εσωτερικό της εφαρμογής scanf έτσι ώστε scanf
πραγματικά μπορεί να γράψει έναν αριθμό 2 της εν λόγω διεύθυνση;
Ναι, έτσι το *.
Υπενθυμίζουμε ότι ο χειριστής είναι * dereference μας, το οποίο ουσιαστικά σημαίνει εκεί.
>> Μόλις εκδοθεί μια διεύθυνση, όπως συμβαίνει εν προκειμένω,
scanf πιθανότατα-αν πραγματικά κοίταξε γύρω από την πηγή του κώδικα-
κάνει * x ή το ισοδύναμο πραγματικά να μεταβεί στη συγκεκριμένη διεύθυνση και να θέσει κάποια αξία εκεί.
Τώρα, όπως και για το πώς scanf παίρνει είσοδο από το πληκτρολόγιο,
θα κυματίσει στα χέρια μας έξω για σήμερα.
Απλά υποθέσουμε ότι το λειτουργικό σύστημα επιτρέπει sscanf να μιλήσει
στο πληκτρολόγιο του χρήστη, αλλά σε αυτό το σημείο τώρα στη γραμμή 19,
όταν απλά εκτύπωση χ, φαίνεται να είναι η περίπτωση
scanf που έχει θέσει σε int x.
Αυτό είναι ακριβώς το πώς λειτουργεί scanf, ενώ υπενθυμίζει και την περασμένη εβδομάδα
αυτό είναι ακριβώς το πώς GetString και GetInt και άλλα οικογένεια των λειτουργιών του
τελικά λειτουργεί, αν και με μικρή διακύμανση, όπως sscanf,
πράγμα που σημαίνει μια συμβολοσειρά σάρωση αντί για το πληκτρολόγιο.
Αλλά ας ρίξουμε μια ματιά σε μια μικρή διακύμανση από αυτό.
Σε scanf2, εγώ πραγματικά μαντάρα.
Ποιο είναι το πρόβλημα-και θα κρύψει το σχόλιο που εξηγεί ως πολύ-
τι είναι λάθος με αυτό το πρόγραμμα, έκδοση 2;
Να είστε όσο το δυνατόν τεχνικά αυτή τη στιγμή.
Φαίνεται αρκετά καλό.
Είναι ωραία εσοχή, αλλά-
εντάξει, σχετικά με το πώς ας το κλαδεύω τα κάτω σε μικρότερα ερωτήσεις;
Γραμμή 16. Τι είναι γραμμή 16 κάνει σε ακριβή αλλά τεχνικά αγγλικά;
Να πάρει λίγο άβολα. Ναι, Μάικλ.
[Φοιτητικό] Είναι δείχνοντας με το πρώτο γράμμα μιας συμβολοσειράς.
>> Εντάξει, κοντά. Επιτρέψτε μου να τσιμπιά ότι λίγο.
Επισημαίνοντας το πρώτο γράμμα μιας συμβολοσειράς, που κηρύσσει μια μεταβλητή που ονομάζεται ρυθμιστικό
που θα τονίζουν την πρώτη διεύθυνση της συμβολοσειράς,
ή μάλλον, αυτό θα δείξει πιο συγκεκριμένα σε ένα απανθρακώματος.
Σημειώστε ότι δεν είναι πραγματικά δείχνει οπουδήποτε, επειδή δεν υπάρχει φορέας ανάθεσης.
Δεν υπάρχει το σύμβολο της ισότητας, ώστε όλοι κάνουμε είναι την κατανομή της μεταβλητής που ονομάζεται buffer.
Συμβαίνει να είναι 32 bit επειδή είναι ένας δείκτης,
και τα περιεχόμενα του ρυθμιστικού πιθανώς τελικά
θα περιέχει τη διεύθυνση μιας char, αλλά για τώρα, ό, τι δεν περιέχει ρυθμιστικό διάλυμα;
Απλά μερικές ψεύτικες, ποιος ξέρει, κάποια αξία σκουπίδια,
επειδή δεν έχουμε προετοιμαστεί ρητά, γι 'αυτό δεν θα πρέπει να υποθέσουμε τίποτα.
Εντάξει, έτσι τώρα η γραμμή 17 είναι-τι γραμμή 17 κάνει;
Ίσως αυτό θα ζεστάνει αυτό επάνω.
Εκτυπώνει μια σειρά, έτσι δεν είναι;
Τυπώνει String παρακαλώ.
>> Η γραμμή 18 είναι το είδος των γνωστών πλέον σε ότι είδαμε μόνο μια διακύμανση αυτή
αλλά με διαφορετικό κωδικό μορφή, έτσι στη γραμμή 18,
λέμε scanf εδώ είναι η διεύθυνση του ένα κομμάτι της μνήμης.
Θέλω να τηλεφωνήσετε σε μια σειρά, όπως υπονοείται από% s,
αλλά το πρόβλημα είναι ότι δεν έχουμε κάνει μερικά πράγματα εδώ.
Τι είναι ένα από τα προβλήματα;
[Φοιτητικό] Είναι προσπαθεί να dereference ένα null δείκτη.
Καλό, μηδενική ή αλλιώς απλά άγνωστο δείκτες.
Είσαι παράδοση scanf μια διεύθυνση, αλλά το μόνο που είπε πριν από λίγο
ότι η διεύθυνση είναι κάποια αξία σκουπίδια, επειδή δεν είχαμε εκχωρήσει πραγματικά σε τίποτα,
και έτσι λέτε scanf αποτελεσματικά να θέσει μια σειρά εδώ,
αλλά δεν ξέρετε από πού είναι ακόμη εδώ,
έτσι δεν έχουμε στην πραγματικότητα διατεθεί για μνήμη buffer.
Επιπλέον, αυτό που είστε, επίσης, δεν λέει ακόμη και scanf;
Ας υποθέσουμε ότι αυτό ήταν ένα κομμάτι της μνήμης, και αυτό δεν ήταν μια αξία σκουπίδια,
αλλά είστε ακόμα δεν λέει κάτι σημαντικό scanf.
[Φοιτητικό] Όταν είναι στην πραγματικότητα, το εμπορικό.
Ampersand, οπότε σε αυτή την περίπτωση, είναι εντάξει.
Επειδή ρυθμιστικό ήδη δηλωθεί ως δείκτης
με το κομμάτι * της σύνταξης, δεν χρειάζεται να χρησιμοποιήσετε ampersand
γιατί είναι ήδη μια διεύθυνση, αλλά νομίζω ότι το άκουσα εδώ.
[Φοιτητικό] Πόσο μεγάλο είναι αυτό;
Καλό, δεν είμαστε scanf λέει πόσο μεγάλο είναι αυτό το ρυθμιστικό,
πράγμα που σημαίνει ακόμα κι αν ήταν ένα ρυθμιστικό δείκτη,
λέμε scanf, να θέσει μια σειρά εδώ,
αλλά εδώ θα μπορούσε να είναι 2 bytes, θα μπορούσε να είναι 10 bytes, θα μπορούσε να είναι ένα megabyte.
Scanf δεν έχει καμία ιδέα, γιατί και αυτό είναι ένα κομμάτι της μνήμης
προφανώς, δεν είναι μια σειρά ακόμα.
Είναι μόνο ένα string από τη στιγμή που γράφουν χαρακτήρες και μια \ 0 έως το κομμάτι της μνήμης.
Τώρα είναι μερικές μόνο κομμάτι της μνήμης.
Scanf δεν θα ξέρουν πότε να σταματήσω να γράφω σε αυτή τη διεύθυνση.
>> Αν θυμηθούμε μερικά παραδείγματα στο παρελθόν όπου τυχαία πληκτρολογηθεί
προσπαθώντας να ξεχειλίσει ένα ρυθμιστικό, και μιλήσαμε την Παρασκευή για ακριβώς αυτό.
Εάν ένας αντίπαλος εγχέει με κάποιο τρόπο στο πρόγραμμά σας μια πολύ μεγαλύτερη λέξη
ή πρόταση ή φράση τότε θα ανέμεναν μπορείτε να υπερβεί
ένα κομμάτι της μνήμης, η οποία μπορεί να έχει κακές συνέπειες,
όπως τη λήψη όλο το ίδιο το πρόγραμμα.
Πρέπει να διορθώσετε αυτό με κάποιο τρόπο.
Επιτρέψτε μου σμίκρυνση και να πάει στην έκδοση 3 του εν λόγω προγράμματος.
Αυτό είναι λίγο καλύτερα.
Σε αυτή την έκδοση, παρατηρήσετε την διαφορά.
Στη γραμμή 16, είμαι δηλώνοντας και πάλι μια μεταβλητή που ονομάζεται buffer,
αλλά τι είναι αυτό τώρα;
Είναι μια σειρά από 16 χαρακτήρες.
Αυτό είναι καλό, διότι αυτό σημαίνει ότι μπορώ να πω τώρα scanf
εδώ είναι ένα πραγματικό κομμάτι της μνήμης.
Μπορείτε να σκεφτείτε σχεδόν συστοιχίες ως δείκτες τώρα,
ακόμα κι αν δεν είστε στην πραγματικότητα ισοδύναμη.
Θα συμπεριφέρονται με διαφορετικό τρόπο σε διαφορετικά πλαίσια.
Αλλά αυτό είναι σίγουρα η περίπτωση ότι ρυθμιστικό αναφορά
16 συνεχόμενα χαρακτήρες, διότι αυτό είναι ένας πίνακας είναι
και ήταν για μερικές εβδομάδες τώρα.
>> Εδώ, λέω scanf εδώ είναι ένα κομμάτι της μνήμης.
Αυτή τη φορά, είναι πραγματικά ένα κομμάτι της μνήμης,
αλλά γιατί είναι αυτό το πρόγραμμα ακόμα εκμεταλλεύσιμο;
Τι συμβαίνει ακόμα;
Έχω πει να μου δώσει 16 byte, αλλά-
[Φοιτητικό] Τι και αν πληκτρολογήσετε σε περισσότερες από 16;
Ακριβώς, τι θα γίνει αν ο χρήστης πληκτρολογεί σε 17 χαρακτήρες ή χαρακτήρες 1700;
Στην πραγματικότητα, ας δούμε αν μπορούμε να μην μπορεί να σκοντάψει σε αυτό το λάθος τώρα.
Είναι καλύτερα, αλλά δεν είναι τέλεια.
Επιτρέψτε μου να πάμε μπροστά και να τρέξει να scanf3 για την κατάρτιση αυτού του προγράμματος.
Επιτρέψτε μου να τρέξει scanf3, παρακαλώ String: Γεια σας, και φαίνεται να είναι εντάξει.
Επιτρέψτε μου να δοκιμάσετε ένα ελαφρώς μακρύτερο, γειά σου εκεί.
Εντάξει, ας το κάνουμε hello there πώς είστε σήμερα, Enter.
Να πάρει το είδος τυχερός εδώ, ας πούμε γεια εκεί τι κάνεις.
Γαμώτο.
Εντάξει, έτσι έχουμε τύχη. Ας δούμε αν δεν μπορούμε να το διορθώσετε αυτό.
Όχι, δεν πρόκειται να με αφήσει να αντιγράψετε.
Ας δοκιμάσουμε ξανά.
Εντάξει, να σταθεί με.
Θα δούμε πόσο καιρό μπορώ να προσποιηθώ να επικεντρωθεί, ενώ κάνει ακόμη αυτό.
Γαμώτο. Αυτό είναι μάλλον σκόπιμο, στην πραγματικότητα.
Εκεί εμείς πάμε.
Σημείο έκανε.
>> Αυτό, ενοχλητικό αν και είναι επίσης, είναι επίσης μία από τις πηγές της μεγάλη σύγχυση
κατά τη σύνταξη των προγραμμάτων που έχουν σφάλματα, επειδή εκδηλώνονται
μόνο μία φορά σε ένα ενώ μερικές φορές.
Η πραγματικότητα είναι ότι, ακόμη και αν ο κωδικός σας είναι εντελώς σπασμένα,
θα μπορούσε μόνο να σπάσει τελείως κάποια στιγμή
γιατί μερικές φορές, κατ 'ουσίαν, αυτό που συμβαίνει είναι τα διαθέτει λειτουργικό σύστημα
λίγο περισσότερη μνήμη από ό, τι πραγματικά χρειάζεται, για οποιονδήποτε λόγο,
και έτσι κανένας άλλος δεν χρησιμοποιεί τη μνήμη αμέσως μετά κομμάτι σας από 16 χαρακτήρες,
έτσι αν πας σε 17, 18, 19, όποια και αν είναι, δεν είναι μια τέτοια μεγάλη υπόθεση.
Τώρα, ο υπολογιστής, ακόμη και αν δεν συντριβή σε αυτό το σημείο,
μπορεί να χρησιμοποιήσει τελικά byte αριθμό 17 ή 18 ή 19 για κάτι άλλο,
κατά την οποία τα δεδομένα σας επισημάνω ότι βάζετε εκεί, αν και υπερβολικά μακρύ,
πρόκειται να πάρει αντικατασταθεί πιθανώς από κάποια άλλη λειτουργία.
Δεν είναι κατ 'ανάγκην θα παραμείνει ανέπαφη,
αλλά δεν θα προκαλέσει αναγκαστικά seg σφάλμα.
Αλλά στην περίπτωση αυτή, θα παρέχεται τελικά αρκετά χαρακτήρες
ότι υπερέβη ουσιαστικά τμήμα της μνήμης μου, και μπαμ,
το λειτουργικό σύστημα είπε: «Συγγνώμη, αυτό δεν είναι καλό, σφάλμα κατάτμησης."
>> Και ας δούμε τώρα αν αυτό που μένει εδώ μου σε κατάλογο-
παρατηρήσετε ότι έχω αυτό το αρχείο, εδώ πυρήνα.
Σημειώστε ότι αυτό ονομάζεται και πάλι μια χωματερή πυρήνα.
Είναι ουσιαστικά ένα αρχείο που περιέχει το περιεχόμενο της μνήμης του προγράμματός σας
στο σημείο όπου συνετρίβη,
και μόνο για να δοκιμάσετε ένα μικρό παράδειγμα εδώ επιτρέψτε μου να πάω εδώ
και να τρέξει gdb για scanf3 και στη συνέχεια, καθορίστε ένα τρίτο επιχείρημα που ονομάζεται πυρήνας,
και παρατηρήσετε εδώ ότι αν λίστα τον κωδικό,
θα είμαστε σε θέση, ως συνήθως, με το gdb για να αρχίσει το περπάτημα μέσα από αυτό το πρόγραμμα,
και μπορώ να το τρέξει και το συντομότερο χτύπησα-όπως με την εντολή βήμα-gdb
μόλις χτύπησα το δυνητικά προβληματικό γραμμή μετά από την πληκτρολόγηση σε μια τεράστια σειρά,
Θα είμαι σε θέση να προσδιορίσει πραγματικά εδώ.
Περισσότερα για το θέμα αυτό, όμως, στο τμήμα από την άποψη των βασικών χωματερές
και τα παρόμοια, ώστε να μπορείτε πραγματικά να σακί γύρω στο εσωτερικό της χωματερής πυρήνα
και να δούμε ποια γραμμή για το πρόγραμμα που απέτυχε.
Οποιεσδήποτε ερωτήσεις σχετικά με δείκτες στη συνέχεια και για τις διευθύνσεις;
Διότι σήμερα, θα πάμε για να αρχίσετε να παίρνετε ως δεδομένο ότι υπάρχουν αυτά τα πράγματα
και γνωρίζουμε ακριβώς τι είναι.
Ναι.
>> [Φοιτητής] Πώς και δεν πρέπει να βάλετε ένα εμπορικό δίπλα στο μέρος-
Καλή ερώτηση.
Πώς έρχονται δεν είχα να θέσει ένα εμπορικό δίπλα στην παράταξη χαρακτήρα όπως έκανα και στο παρελθόν
με το μεγαλύτερο μέρος των παραδειγμάτων μας;
Η σύντομη απάντηση είναι συστοιχίες είναι λίγο ιδιαίτερη.
Μπορείτε να σκεφτείτε ένα ρυθμιστικό σχεδόν όπως στην πραγματικότητα είναι μια διεύθυνση,
και είναι ακριβώς έτσι συμβαίνει να είναι η υπόθεση ότι η πλατεία σημειογραφία βραχίονα
είναι μια ευκολία, έτσι ώστε να μπορούμε να πάμε σε βραχίονα 0, κατηγορία 1,
στήριγμα 2, χωρίς να χρειάζεται να χρησιμοποιήσει το συμβολισμό *.
Αυτό είναι ένα κομμάτι από ένα λευκό ψέμα, διότι πίνακες και δείκτες
είναι, στην πραγματικότητα, ένα λίγο διαφορετικό, αλλά μπορούν συχνά αλλά όχι πάντα να χρησιμοποιηθούν εναλλακτικά.
Με λίγα λόγια, όταν μια συνάρτηση περιμένει ένα δείκτη σε ένα κομμάτι της μνήμης,
μπορείτε είτε να δώσετε μια διεύθυνση που επέστρεψε από την malloc,
και θα δούμε malloc και πάλι πριν από καιρό, ή μπορείτε να δώσετε το όνομα ενός πίνακα.
Δεν έχουν να κάνουν με το εμπορικό και συστοιχίες, επειδή είναι ήδη
κατ 'ουσίαν, όπως διευθύνσεις.
Αυτή είναι η μία εξαίρεση.
Οι αγκύλες κάνει τους ειδικούς.
>> Θα μπορούσατε να βάλετε ένα εμπορικό δίπλα στο ρυθμιστικό;
Όχι σε αυτή την περίπτωση.
Αυτό δεν θα μπορούσε να λειτουργήσει, διότι, και πάλι, στην παρούσα υπόθεση γωνία
όπου συστοιχίες δεν είναι αρκετά πραγματικά διευθύνσεις.
Αλλά ίσως θα επανέλθουμε σε αυτό πριν από καιρό με άλλα παραδείγματα.
Ας προσπαθήσουμε να λύσουμε ένα πρόβλημα εδώ.
Έχουμε μια δομή δεδομένων που έχουμε χρησιμοποιήσει για κάποιο χρονικό διάστημα είναι γνωστή ως μια σειρά.
Υπόθεση στο σημείο, αυτό είναι ό, τι ακριβώς έπρεπε.
Αλλά συστοιχίες έχουν κάποια upsides και μειονεκτήματα.
Οι πίνακες είναι ωραία γιατί;
Τι είναι ένα πράγμα που σας αρέσει-στο βαθμό που σας αρέσει πίνακες-σχετικά με πίνακες;
Τι είναι βολικό γι 'αυτούς; Τι είναι συναρπαστικό;
Γιατί να τους εισαγάγει στην πρώτη θέση;
Ναι.
[Φοιτητικό] Μπορούν να αποθηκεύσει πολλά δεδομένα, και εσείς δεν χρειάζεται να χρησιμοποιήσετε ένα ολόκληρο πράγμα.
Μπορείτε να χρησιμοποιήσετε μια ενότητα.
Καλό, με μια σειρά μπορείτε να αποθηκεύσετε πολλά δεδομένα,
και δεν πρέπει κατ 'ανάγκη να χρησιμοποιήσει όλα αυτά, ώστε να μπορείτε να overallocate,
η οποία μπορεί να είναι βολικό, αν δεν ξέρετε εκ των προτέρων πόσα από κάτι να περιμένουν.
>> GetString είναι ένα τέλειο παράδειγμα.
GetString, γραμμένο από εμάς, δεν έχει καμία ιδέα για το πώς πολλοί χαρακτήρες να περιμένουν,
έτσι το γεγονός ότι μπορούμε να διαθέσουν κομμάτια της συνεχούς μνήμης είναι καλή.
Πίνακες λύσει ένα πρόβλημα, επίσης, είδαμε μερικές εβδομάδες πριν από την επιχείρηση
όπου κωδικό σας αρχίζει να περιέρχεται σε κάτι πολύ κακοσχεδιασμένα.
Υπενθυμίζουμε ότι έχω δημιουργήσει μια δομή που ονομάζεται David μαθητή,
και στη συνέχεια, αυτό ήταν πραγματικά μια εναλλακτική λύση, αν και,
να έχει μια μεταβλητή που ονομάζεται όνομα και μια άλλη μεταβλητή που ονομάζεται, νομίζω, το σπίτι,
και μια άλλη μεταβλητή που ονομάζεται ID, διότι σε αυτή την ιστορία τότε θα ήθελα να εισαγάγει κάτι άλλο
Rob αρέσει στο πρόγραμμα, έτσι αποφάσισε τότε να περιμένετε ένα λεπτό,
Πρέπει να μετονομάσετε αυτές τις μεταβλητές.
Ας το ονομάσουμε ορυχείο NAME1, ID1, House1.
Ας το ονομάσουμε του Rob όνομα2, house2, ID2.
Αλλά περιμένετε ένα λεπτό, στη συνέχεια, τι θα γίνει με τον Tommy;
Στη συνέχεια, είχαμε τρεις μεταβλητές.
Εισαγάγαμε κάποιος άλλος, τέσσερα σύνολα των μεταβλητών.
Ο κόσμος άρχισε να πάρει βρώμικο πολύ γρήγορα,
έτσι ώστε να εισαχθεί structs, και τι είναι συναρπαστικό για ένα struct;
Τι κάνει ένα struct C σας επιτρέπει να κάνετε;
Είναι πραγματικά δύσκολη σήμερα.
Τι; >> [ακούγεται ανταπόκριση των φοιτητών]
Ναι, ειδικά, typedef σας επιτρέπει να δημιουργήσετε ένα νέο τύπο δεδομένων,
και struct, η λέξη-κλειδί struct, σας δίνει τη δυνατότητα να ενσωματώσουν
εννοιολογικά συνδέονται κομμάτια των δεδομένων από κοινού
και στη συνέχεια καλέστε τους κάτι σαν φοιτητής.
>> Αυτό ήταν καλό, γιατί τώρα μπορούμε να μοντελοποιήσουμε
πολύ περισσότερο είδος εννοιολογικά συνεπής η έννοια του φοιτητή σε μια μεταβλητή
αντί να έχουν αυθαίρετα ένα για ένα συμβολοσειρά, μία για ένα ID, και ούτω καθεξής.
Οι πίνακες είναι ωραία επειδή μας επιτρέπουν να ξεκινήσετε τον καθαρισμό κωδικό μας.
Αλλά αυτό είναι ένα μειονέκτημα τώρα από μια σειρά;
Τι δεν μπορείτε να κάνετε; Ναι.
[Φοιτητικό] Θα πρέπει να ξέρετε πόσο μεγάλο είναι.
Θα πρέπει να ξέρετε πόσο μεγάλο είναι, γι 'αυτό είναι το είδος του πόνου.
Όσοι από εσάς με προηγούμενη εμπειρία στον προγραμματισμό γνωρίζουμε ότι σε πολλές γλώσσες,
όπως η Java, μπορείτε να ζητήσετε από ένα κομμάτι της μνήμης, ειδικά μια σειρά,
πόσο μεγάλη είναι σας, με το μήκος, την ιδιοκτησία, να το πω έτσι, και αυτό είναι πραγματικά βολικό.
Στην C, δεν μπορείτε να καλέσετε ακόμη και strlen σε μία γενική σειρά
strlen επειδή, όπως υποδηλώνει η λέξη, είναι μόνο για έγχορδα,
και μπορείτε να υπολογίσετε το μήκος της συμβολοσειράς, λόγω αυτής της Σύμβασης Ανθρωπίνων
να έχουν ένα \ 0, αλλά μια σειρά, πιο γενικά, είναι απλά ένα κομμάτι της μνήμης.
Αν είναι μια σειρά από ints, εκεί δεν πρόκειται να είναι κάποιος ειδικός χαρακτήρας
στο τέλος σας περιμένει.
Θα πρέπει να θυμόμαστε το μήκος ενός πίνακα.
Ένα άλλο μειονέκτημα του ενός πίνακα που εκτρέφονται στο κεφάλι του GetString ίδια.
Τι άλλο μειονέκτημα μιας σειράς;
Κύριε, μόνο εσείς και εγώ σήμερα.
[Ακούγεται ανταπόκριση των φοιτητών] >> Είναι ό, τι;
Είναι δηλωθεί στη στοίβα.
Εντάξει, δήλωσε στη στοίβα. Γιατί δεν σας αρέσει αυτό;
[Φοιτητικό] Επειδή παίρνει ξαναχρησιμοποιηθεί.
Παίρνει επαναχρησιμοποιηθούν.
Εντάξει, αν χρησιμοποιείτε έναν πίνακα για την κατανομή της μνήμης,
δεν μπορείτε, για παράδειγμα, να επιστρέψει γιατί είναι στη στοίβα.
Εντάξει, αυτό είναι ένα μειονέκτημα.
Και τι θα λέγατε για ένα άλλο με μια σειρά;
Όταν η κατανομή της, είστε το είδος του βιδωθεί αν χρειάζεστε περισσότερο χώρο
από εκείνο συστοιχία έχει.
>> Στη συνέχεια, εισάγαμε, ανάκληση, malloc, η οποία μας έδωσε τη δυνατότητα να κατανέμει δυναμικά μνήμη.
Αλλά τι γίνεται αν έχουμε δοκιμάσει ένα διαφορετικό κόσμο εντελώς;
Τι γίνεται αν θέλουμε να λύσουμε ένα ζευγάρι από αυτά τα προβλήματα
έτσι αντί-στυλό μου έχει αποκοιμηθεί εδώ-
τι θα γίνει αν εμείς αντί ήθελε να δημιουργήσει ουσιαστικά ένα κόσμο που δεν είναι πλέον σαν αυτό;
Αυτή είναι μια συστοιχία, και, φυσικά, αυτό το είδος των επιδεινώνεται μόλις χτυπήσει το άκρο της διάταξης,
και εγώ τώρα δεν έχουν πλέον χώρο για άλλο ακέραιο ή έναν άλλο χαρακτήρα.
Τι θα συμβεί αν έχουμε είδους προληπτικά λένε καλά, γιατί δεν μπορούμε να χαλαρώσετε
η απαίτηση ότι όλα αυτά τα κομμάτια της μνήμης είναι συνεχόμενες πλάτη με πλάτη,
και γιατί όχι, όταν χρειάζομαι ένα int ή char ένα,
απλά να μου δώσει χώρο για ένα από αυτά;
Και όταν χρειάζομαι ένα άλλο, να μου δώσει ένα άλλο χώρο,
και όταν χρειάζομαι ένα άλλο, να μου δώσει ένα άλλο χώρο.
Το πλεονέκτημα του οποίου τώρα είναι ότι αν κάποιος άλλος
παίρνει τη μνήμη πάνω από εδώ, δεν είναι μεγάλη υπόθεση.
Θα πάρω αυτό το επιπλέον κομμάτι της μνήμης εδώ και στη συνέχεια αυτό.
>> Τώρα, το μόνο αλιεύματα εδώ είναι ότι αυτό αισθάνεται σχεδόν σαν να έχω
ένα σωρό διαφορετικές μεταβλητές.
Αυτό μοιάζει με πέντε διαφορετικές μεταβλητές δυνητικά.
Αλλά τι εάν θα κλέψουν μια ιδέα από χορδές
σύμφωνα με την οποία έχουμε συνδέσει με κάποιο τρόπο αυτά τα πράγματα μαζί εννοιολογικά, τι και αν το έκανα αυτό;
Αυτό είναι πολύ άσχημα που βέλος μου.
Αλλά ας υποθέσουμε ότι κάθε μία από αυτές κομμάτια της μνήμης
τόνισε την άλλη, και αυτός ο τύπος, ο οποίος δεν έχει δικαίωμα να αδερφό του,
έχει καμία τέτοια βέλος.
Αυτό είναι στην πραγματικότητα αυτό που ονομάζεται μια συνδεδεμένη λίστα.
Πρόκειται για μια νέα δομή δεδομένων που μας επιτρέπει να διαθέσει ένα μεγάλο κομμάτι της μνήμης,
τότε μια άλλη, τότε μια άλλη, τότε μια άλλη, κάθε φορά που θέλουμε
κατά τη διάρκεια του προγράμματος, και θυμόμαστε ότι είμαστε όλοι με κάποιο τρόπο σχετίζονται με
κυριολεκτικά από αλυσοποίηση μαζί τους, και κάναμε ότι εικονογραφικά εδώ με ένα βέλος.
Αλλά σε κώδικα, τι θα είναι ο μηχανισμός μέσω του οποίου μπορείτε να συνδέσετε με κάποιο τρόπο,
σχεδόν σαν Scratch, ένα κομμάτι σε ένα άλλο κομμάτι;
Θα μπορούσαμε να χρησιμοποιήσουμε ένα δείκτη, έτσι δεν είναι;
Επειδή πραγματικά το βέλος που πηγαίνει από το επάνω αριστερό τετράγωνο,
αυτός ο τύπος εδώ σε αυτό το ένα, θα μπορούσε να περιέχει μέσα από αυτό το τετράγωνο
όχι μόνο μερικά ints, όχι μόνο μερικά char, αλλά τι γίνεται αν έχω πραγματικά κατανέμονται
λίγο επιπλέον χώρο, έτσι ώστε τώρα,
καθένα από τα κομμάτια της μνήμης μου, ακόμα κι αν αυτό θα μου κοστίσει,
τώρα μοιάζει λίγο πιο ορθογώνια, όπου ένα από τα κομμάτια της μνήμης
χρησιμοποιείται για έναν αριθμό, όπως ο αριθμός 1,
και στη συνέχεια, αν αυτός ο τύπος αποθηκεύει τον αριθμό 2,
αυτό το άλλο κομμάτι της μνήμης που χρησιμοποιείται για ένα βέλος,
ή πιο συγκεκριμένα, ένας δείκτης.
Και ας υποθέσουμε ότι έχω αποθηκεύσει τον αριθμό 3 πάνω από εδώ, ενώ μπορώ να χρησιμοποιήσω αυτό το σημείο σε αυτόν τον τύπο,
και τώρα αυτός ο τύπος, ας υποθέσουμε ότι θέλω μόνο τρία τέτοια κομμάτια της μνήμης.
Θα χαράξουμε μια διαχωριστική γραμμή μέσα από αυτό, δείχνοντας μηδενική.
Δεν υπάρχει καμία πρόσθετη χαρακτήρα.
>> Πράγματι, αυτό είναι το πώς μπορούμε να πάμε για την εφαρμογή
κάτι που ονομάζεται συνδεδεμένη λίστα.
Μια συνδεδεμένη λίστα είναι μια νέα δομή δεδομένων, και αυτό είναι ένα σκαλοπάτι προς την κατεύθυνση
πολύ πιό φανταχτερό δομές δεδομένων που αρχίζουν να λύσουν τα προβλήματα
κατά μήκος των γραμμών του τύπου Facebook και το Google προβλήματα τύπου προβλήματα
όπου έχετε τεράστια σύνολα δεδομένων, και πλέον δεν κόβει
για να αποθηκεύσετε τα πάντα συνεχόμενα και να χρησιμοποιήσετε κάτι σαν γραμμική αναζήτηση
ή ακόμη και κάτι σαν δυαδική αναζήτηση.
Θέλετε ακόμα καλύτερες μέρες λειτουργίας.
Στην πραγματικότητα, ένα από τα Ιερά Δισκοπότηρα θα μιλήσουμε αργότερα αυτή την εβδομάδα ή την επόμενη
είναι ένας αλγόριθμος του οποίου χρόνου λειτουργίας είναι σταθερή.
Με άλλα λόγια, λαμβάνει πάντα την ίδια ποσότητα του χρόνου δεν έχει σημασία
πόσο μεγάλη είναι η είσοδος, και ότι θα είναι πράγματι συναρπαστικό,
ακόμη περισσότερο από ό, τι κάτι λογαριθμική.
Τι είναι αυτό στην οθόνη εδώ;
Κάθε ένα από τα ορθογώνια είναι ακριβώς αυτό που μόλις έσυρε με το χέρι.
Αλλά το πράγμα σε όλη τη διαδρομή για την αριστερά είναι μια ειδική μεταβλητή.
Είναι πρόκειται να είναι ένα ενιαίο δείκτη, διότι η μία gotcha
με μια συνδεδεμένη λίστα, όπως ονομάζονται αυτές οι δραστηριότητες,
είναι ότι θα πρέπει να κολλήσει επάνω το ένα άκρο του συνδέεται με λίστα.
>> Ακριβώς όπως και με μια σειρά, θα πρέπει να γνωρίζετε τη διεύθυνση του πρώτου char.
Η ίδια συμφωνία για συνδεδεμένες λίστες.
Θα πρέπει να γνωρίζετε την διεύθυνση του πρώτου κομμάτι της μνήμης
επειδή από εκεί, μπορείτε να φτάσετε σε κάθε άλλη.
Απαισιόδοξη.
Τι τιμή πληρώνουμε γι 'αυτό ευελιξία με δυναμικά
αρκετά μεγάλη δομή δεδομένων ότι αν χρειαζόμαστε όλο και περισσότερο μνήμη, πρόστιμο,
διαθέτουν μόνο ένα ακόμη κομμάτι και σχεδιάστε ένα δείκτη από
το παλιό με το νέο ουρά της λίστας;
Ναι.
[Φοιτητικό] Χρειάζονται περίπου δύο φορές πιο πολύ χώρο.
Παίρνει το διπλάσιο χώρο, έτσι ώστε να είναι σίγουρα ένα μειονέκτημα, και έχουμε δει αυτό
tradeoff πριν από το χρόνο και το χώρο και ευελιξία
όπου από τώρα, δεν χρειαζόμαστε 32 bit για κάθε ένα από αυτούς τους αριθμούς.
Χρειαζόμαστε πραγματικά 64, 32 για τον αριθμό και το 32 για το δείκτη.
Αλλά hey, έχω 2 gigabytes μνήμης RAM.
Η προσθήκη επιπλέον 32 bit εδώ και εδώ δεν φαίνεται ότι μεγάλο ζήτημα.
Αλλά για μεγάλα σύνολα δεδομένων, προσθέτει σίγουρα μέχρι κυριολεκτικά τα διπλάσια.
Τι άλλο μειονέκτημα τώρα, ή ό, τι χαρακτηριστικό δίνουμε επάνω,
αν εμείς εκπροσωπούμε τους καταλόγους των πραγμάτων με μια συνδεδεμένη λίστα και όχι μια σειρά;
[Φοιτητικό] Δεν μπορείτε να διασχίσουν προς τα πίσω.
Δεν μπορείτε να διασχίσουν προς τα πίσω, έτσι είστε το είδος του βιδωθεί αν είστε με τα πόδια
από αριστερά προς τα δεξιά χρησιμοποιώντας ένα βρόχο for ή ένα βρόχο, ενώ
και τότε συνειδητοποιείς, «Ω, θέλω να πάω πίσω στην αρχή της λίστας."
Δεν μπορείτε, επειδή μόνο οι δείκτες πάνε από αριστερά προς τα δεξιά, όπως δείχνουν τα βέλη.
>> Τώρα, μπορείτε να θυμηθείτε την αρχή της λίστας με μια άλλη μεταβλητή,
αλλά αυτό είναι μια πολυπλοκότητα που πρέπει να θυμάστε.
Μια σειρά, δεν έχει σημασία πόσο μακριά θα πάτε, μπορείτε πάντα να κάνετε μείον, μείον, μείον, μείον
και να επιστρέψετε από όπου ήρθατε.
Τι άλλο μειονέκτημα εδώ; Ναι.
[Ακούγεται ερώτηση φοιτητή]
Θα μπορούσε, έτσι έχετε πραγματικά προτείνεται μόνο μια δομή δεδομένων που ονομάζεται μια διπλά συνδεδεμένη λίστα,
και μάλιστα, θα προσθέσει ένα άλλο δείκτη για κάθε ένα από αυτά ορθογώνια
που πηγαίνει προς την άλλη κατεύθυνση, η οποία ανάποδα
τώρα μπορείτε να διασχίσει εμπρός και πίσω,
το μειονέκτημα της οποίας είναι τώρα είστε χρησιμοποιώντας τρεις φορές το μέγεθος της μνήμης που θα χρησιμοποιείται για
και προσθέτοντας επίσης την πολυπλοκότητα όσον αφορά τον κώδικα που πρέπει να γράψετε για να το κάνετε σωστά.
Αλλά όλα αυτά είναι ίσως πολύ λογική τήρησης ισορροπιών, αν η αντιστροφή είναι πιο σημαντικό.
Ναι.
[Φοιτητικό] Μπορείτε, επίσης, δεν μπορεί να έχει ένα 2D συνδεδεμένη λίστα.
Καλό, δεν μπορείτε να έχετε πραγματικά ένα 2D συνδεδεμένη λίστα.
Θα μπορούσατε. Δεν είναι σχεδόν τόσο εύκολο όσο μια σειρά.
Όπως και μια σειρά, να κάνετε ανοιχτό βραχίονα, κλειστή γωνία, ανοιχτό βραχίονα κλειστό βραχίονα,
και μπορείτε να πάρετε κάποια 2-τρισδιάστατη δομή.
Θα μπορούσε να εφαρμόσει μια 2-διαστάσεων συνδεδεμένη λίστα
αν το κάνετε add-όπως προτείνεται-ένα τρίτο δείκτη σε κάθε ένα από αυτά τα πράγματα,
και αν νομίζετε ότι για μια άλλη λίστα που έρχονται σε 3D στυλ σας
από την οθόνη σε όλους μας, το οποίο είναι ακριβώς μια άλλη αλυσίδα κάποιου είδους.
Θα μπορούσαμε να το κάνουμε, αλλά δεν είναι τόσο απλή όσο η πληκτρολόγηση ανοιχτό βραχίονα, αγκύλη. Ναι.
[Ακούγεται ερώτηση φοιτητή]
Καλό, έτσι αυτό είναι μια πραγματική kicker.
>> Αυτοί οι αλγόριθμοι που έχουμε pined πάνω, όπως OH, δυαδική αναζήτηση,
μπορείτε να αναζητήσετε μια σειρά από αριθμούς στον πίνακα
ή ένα βιβλίο τηλέφωνο τόσο πιο γρήγορα αν χρησιμοποιείτε διαίρει και βασίλευε
και ένα δυαδικό αλγόριθμο αναζήτησης, αλλά δυαδική αναζήτηση απαιτεί δύο υποθέσεις.
Ένα, ότι τα δεδομένα ήταν ταξινομημένο.
Τώρα, μπορούμε προφανώς να κρατήσει αυτή η ταξινόμηση,
οπότε ίσως αυτό δεν είναι μια ανησυχία, αλλά δυαδική αναζήτηση και υποτίθεται
ότι είχατε τυχαία πρόσβαση στη λίστα των αριθμών,
και μια σειρά σας επιτρέπει να έχετε πρόσβαση τυχαία, και με τυχαία πρόσβαση,
Θέλω να πω, αν σας δίνεται μια σειρά, πόσο χρόνο χρειάζεται για να πάρετε
για να φτάσετε στο βραχίονα 0;
Μια λειτουργία, μπορείτε να χρησιμοποιήσετε μόνο [0] και είσαι εκεί.
Πόσα βήματα χρειάζονται για να φτάσετε στο σημείο 10;
Ένα βήμα, απλά πηγαίνετε στο [10] και είσαι εκεί.
Αντίθετα, πώς να φτάσετε στο 10ο ακέραιο σε μια συνδεδεμένη λίστα;
Θα πρέπει να ξεκινήσουμε από την αρχή, επειδή είστε μόνο να θυμόμαστε
η αρχή μιας συνδεδεμένη λίστα, ακριβώς όπως μια χορδή να θυμόμαστε
από την διεύθυνση της πρώτης char του, και να διαπιστώσετε ότι 10ης int
ή ότι 10ης χαρακτήρα σε μια σειρά, θα πρέπει να αναζητήσετε το σύνολο πράγμα βλασφημίας.
>> Και πάλι, δεν είμαστε επίλυση όλων των προβλημάτων μας.
Είμαστε εισαγωγή νέων, αλλά αυτό εξαρτάται πραγματικά από το τι προσπαθείτε να σχεδιάσει για.
Όσον αφορά την εφαρμογή της παρούσας, μπορούμε να δανειστούμε μια ιδέα από την δομή των φοιτητών.
Η σύνταξη είναι πολύ παρόμοια, εκτός από τώρα, η ιδέα είναι λίγο πιο αφηρημένη
από το σπίτι και το όνομα και ταυτότητα.
Αλλά προτείνω ότι θα μπορούσαμε να έχουμε μια δομή δεδομένων σε C
που ονομάζεται κόμβος, καθώς η τελευταία λέξη για τη διαφάνεια προτείνει,
μέσα από έναν κόμβο, και ένας κόμβος είναι απλά ένας γενικός δοχείο στην επιστήμη των υπολογιστών.
Είναι συνήθως συντάσσεται ως ένα κύκλο ή ένα τετράγωνο ή ορθογώνιο, όπως έχουμε κάνει.
Και σε αυτή τη δομή δεδομένων, έχουμε έναν int, n,
έτσι ώστε να είναι ο αριθμός που θέλετε να αποθηκεύσετε.
Αλλά τι είναι αυτή η δεύτερη γραμμή, struct node * το επόμενο βήμα;
Γιατί αυτό είναι σωστό, ή τι ρόλο έχει παίξει αυτό το πράγμα,
ακόμα κι αν είναι λίγο αινιγματικό με την πρώτη ματιά;
Ναι.
[Ακούγεται ανταπόκριση των φοιτητών]
Ακριβώς, έτσι ώστε το είδος της λάφυρα * ότι είναι ένας δείκτης κάποιου είδους.
Το όνομα αυτού του δείκτη είναι αυθαίρετα επόμενο,
αλλά θα μπορούσαμε να έχουμε κάτι που ονομάζεται το θέλουμε, αλλά τι κάνει αυτό το σημείο δείκτη;
[Φοιτητικό] Ένα άλλο κόμβο. >> Ακριβώς, επισημαίνει σε άλλο τέτοιο κόμβο.
>> Τώρα, αυτό είναι ένα είδος περιέργεια του C.
Υπενθυμίζουμε ότι η C διαβάζεται από πάνω προς τα κάτω compiler, αριστερά προς τα δεξιά,
το οποίο σημαίνει ότι αν αυτό-είναι λίγο διαφορετικό από αυτό που κάναμε με τον μαθητή.
Όταν ορίζεται ένας φοιτητής, που στην πραγματικότητα δεν έθεσε μια λέξη.
Απλώς είπε typedef.
Τότε είχαμε int id, όνομα συμβολοσειράς, string σπίτι,
και ακολούθως φοιτητής στο πυθμένα του struct.
Η δήλωση αυτή είναι λίγο διαφορετική, διότι,
πάλι, η C compiler είναι λίγο χαζή.
Είναι μόνο πρόκειται να διαβάσετε πάνω προς τα κάτω,
οπότε αν φτάσει στη 2η γραμμή εδώ
όπου δηλώνεται δίπλα και βλέπει, OH, εδώ είναι μια μεταβλητή που ονομάζεται επόμενο.
Είναι ένας δείκτης σε κόμβο struct.
Ο μεταγλωττιστής πρόκειται να συνειδητοποιήσει τι είναι ένας κόμβος struct;
Δεν έχω ακούσει για αυτό το πράγμα πριν,
επειδή ο κόμβος λέξη μπορεί να μην εμφανίζονται διαφορετικά
μέχρι τον πυθμένα, έτσι δεν υπάρχει αυτή η πλεονασμό.
Θα πρέπει να πω εδώ struct node, το οποίο μπορείτε στη συνέχεια να μειωθεί αργότερα
χάρη στην typedef εδώ κάτω, αλλά αυτό είναι επειδή
είμαστε αναφορά ίδια την δομή εσωτερικό της δομής.
Αυτό είναι το ένα gotcha εκεί.
>> Μερικά ενδιαφέροντα προβλήματα που θα προκύψουν.
Έχουμε μια λίστα των αριθμών. Πώς μπορούμε να εισάγετε σε αυτό;
Πώς μπορούμε να το ψάξει; Πώς μπορούμε να διαγράψετε από αυτό;
Ειδικά τώρα που έχουμε να διαχειριστεί όλες αυτές τις υποδείξεις.
Νομίζατε ότι ήταν δείκτες είδος της μυαλό κάμψης
όταν είχε ένα από αυτά ακριβώς που προσπαθεί να διαβάσει ένα int σε αυτό.
Τώρα έχουμε να χειραγωγήσουν αξίζει μιας ολόκληρης λίστας.
Γιατί δεν παίρνουμε 5-λεπτά διάλειμμα μας εδώ, και στη συνέχεια θα φέρει
μερικοί λαοί πάνω στη σκηνή για να κάνει ακριβώς αυτό.
>> C είναι πολύ πιο διασκεδαστικό όταν είναι ενεργήσει έξω.
Ποιος θα ήθελε κυριολεκτικά να είναι η πρώτη;
Εντάξει, έλα επάνω. Είστε πρώτα.
Ποιος θα ήθελε να είναι 9; Εντάξει, 9.
Πόσο περίπου 9; 17;
Μια μικρή κλίκα εδώ. 22 και 26 στην εν λόγω πρώτη σειρά.
Και τότε πώς για κάποιον εκεί που επισήμανε σε.
Είστε 34. Εντάξει, 34, έλα επάνω.
Πρώτη είναι εκεί πέρα. Εντάξει, και οι τέσσερις από σας παιδιά.
Και ποιος δεν λέμε για 9;
Ποιος είναι 9 μας;
Ποιος θέλει πραγματικά να είναι 9; Εντάξει, έλα, είναι 9.
Εδώ πάμε.
34, θα σας συναντήσω εκεί.
Το πρώτο μέρος είναι να κάνει τον εαυτό σας να μοιάζει με αυτό.
26, 22, 17, καλό.
Αν μπορείτε να σταθείτε στο πλάι, γιατί θα πάμε για να σας malloc σε μια στιγμή.
>> Ωραία, ωραία.
Εντάξει, εξαιρετική, οπότε ας ρωτήσω μερικές ερωτήσεις εδώ.
Και στην πραγματικότητα, αυτό που είναι το όνομά σου; >> Anita.
Anita, εντάξει, έλα εδώ.
Anita πρόκειται να μας βοηθήσει είδος επίλυση ενός αρκετά απλή ερώτηση στην πρώτη,
το οποίο είναι το πώς μπορείτε να βρείτε αν ή όχι η τιμή είναι στη λίστα;
Τώρα, παρατηρούμε ότι η πρώτη, που εκπροσωπείται εδώ από τον Lucas,
είναι λίγο διαφορετική, και έτσι κομμάτι του χαρτί είναι σκόπιμα πλάγια
επειδή δεν είναι αρκετά ψηλό, όπως και δεν λαμβάνει ως πολλά κομμάτια,
παρόλο που τεχνικά έχει το ίδιο μέγεθος χαρτιού μόνο περιστρέφεται.
Αλλά είναι λίγο διαφορετικό στο ότι αυτός είναι μόνο 32 bits για ένα δείκτη,
και όλα αυτά τα παιδιά είναι 64 bits, το ήμισυ των οποίων είναι ο αριθμός, το ήμισυ του οποίου είναι ένας δείκτης.
Αλλά ο δείκτης δεν απεικονίζεται, οπότε αν εσείς θα μπορούσε κάπως αδέξια
χρησιμοποιήστε το αριστερό σας χέρι να το σημείο στο πρόσωπο δίπλα σε σας.
Και είστε αριθμό 34. Ποιο είναι το όνομά σου;
Ari.
Ari, έτσι στην πραγματικότητα, κρατήστε το χαρτί στο δεξί σας χέρι, το αριστερό χέρι και πηγαίνει κατ 'ευθείαν προς τα κάτω.
Δηλώνετε null στα αριστερά.
>> Τώρα ανθρώπινη εικόνα μας είναι πολύ συνεπής.
Αυτό είναι στην πραγματικότητα το πώς δείκτες εργασία.
Και αν μπορείτε να τραγανίζω λίγο με αυτόν τον τρόπο, έτσι δεν είμαι στο δρόμο σας.
Anita εδώ, βρείτε μου τον αριθμό 22,
αλλά υποθέτουν έναν περιορισμό των ανθρώπων δεν κρατά ψηλά κομμάτια από χαρτί,
αλλά αυτό είναι μια λίστα, και το μόνο που πρέπει Lucas για να αρχίσει με
επειδή είναι κυριολεκτικά η πρώτη δείκτη.
Ας υποθέσουμε ότι εσείς ο ίδιος είναι ένας δείκτης, και έτσι έχετε πολύ τη δυνατότητα να επισημάνει κάτι.
Γιατί δεν ξεκινάτε δείχνοντας ακριβώς τι Lucas είναι στραμμένο προς;
Καλό, και επιτρέψτε μου να θεσπίσει αυτό από εδώ.
Απλά για χάρη της συζήτησης, επιτρέψτε μου να σηκώσει μια κενή σελίδα εδώ.
Πώς μπορείτε να πείτε το όνομά σας; >> Anita.
Εντάξει, Anita.
Ας πούμε ότι ο κόμβος * anita = Lucas.
Λοιπόν, δεν θα πρέπει να σας καλέσει lucas. Θα πρέπει να καλέσετε εσείς πρώτα.
Γιατί αυτό είναι στην πραγματικότητα συνάδει με την πραγματικότητα εδώ;
Ένα πρώτο υπάρχει ήδη.
Πρώτον έχει διατεθεί κατά πάσα πιθανότητα κάπου εδώ.
Κόμβος * πρώτα, και είναι ήδη διατεθεί μια λίστα με κάποιο τρόπο.
Δεν ξέρω πώς συνέβη αυτό. Αυτό συνέβη πριν το μάθημα ξεκινήσει.
Αυτή η συνδεδεμένη λίστα των ανθρώπων έχει δημιουργηθεί.
Και τώρα σε αυτό το σημείο στην ιστορία, αυτό είναι όλο πρόκειται στο Facebook προφανώς αργότερα-
σε αυτό το σημείο στην ιστορία, Anita έχει προετοιμαστεί για να είναι ίση με την πρώτη,
το οποίο δεν σημαίνει ότι Anita σημεία στο Lucas.
Αντίθετα, επισημαίνει σε αυτό που δείχνει στο
επειδή η ίδια διεύθυνση που είναι μέσα των 32 bits του Lucas - 1, 2, 3 -
Είναι τώρα επίσης στο εσωτερικό του 32 Ανίτας bits - 1, 2, 3.
>> Τώρα βρείτε 22. Πώς θα μπορείτε να κάνετε για αυτό;
Τι είναι αυτό; >> Point για οτιδήποτε άλλο.
Τοποθετήστε το δείκτη στο οτιδήποτε, έτσι ώστε να προχωρήσει και να ενεργούν έξω όσο καλύτερα μπορείτε εδώ.
Καλό, καλό, και τώρα είστε δείχνοντας-τι είναι το όνομά σας με 22;
Ραμόν. >> Ramon, έτσι Ramon κρατάει μέχρι 22.
Έχετε κάνει τώρα μια επιταγή.
Μήπως Ramon == 22, και αν ναι, για παράδειγμα, μπορούμε να επιστρέψουμε αλήθεια.
Επιτρέψτε μου-ενώ αυτοί οι τύποι στέκονται εδώ κάπως αδέξια-
επιτρέψτε μου να κάνω κάτι γρήγορα, όπως bool βρείτε.
Πάω να προχωρήσει και να πω (κόμβος λίστα *, int n).
Θα είμαι πίσω δεξιά με σας παιδιά. Απλώς πρέπει να γράψετε κάποιο κώδικα.
Και τώρα είμαι πρόκειται να πάει μπροστά και να το κάνετε αυτό, ο κόμβος * = anita λίστα.
Και εγώ είμαι πρόκειται να πάει μπροστά και να πει, ενώ (anita! = NULL).
>> Η μεταφορά εδώ είναι να πάρει λίγο τεντωμένα, αλλά παράλληλα (anita! = NULL), τι θέλω να κάνω;
Χρειάζομαι κάποιο τρόπο αναφορά
ο ακέραιος ότι Anita δείχνει σε.
Στο παρελθόν, όταν είχαμε δομές, το οποίο είναι ένας κόμβος,
χρησιμοποιήσαμε το συμβολισμό τελεία, και θα λέγαμε κάτι σαν
anita.n, αλλά το πρόβλημα εδώ είναι ότι δεν Anita είναι ένα struct per se.
Τι είναι;
Είναι ένας δείκτης, τόσο πραγματικά, αν θέλουμε να χρησιμοποιήσουμε αυτό το συμβολισμό dot-
και αυτό πρόκειται να δούμε σκόπιμα λίγο αινιγματικό-
πρέπει να κάνουμε κάτι για να πάνε χέρι αριστερά Anita ό, τι είναι να υποδεικνύουν
και να πάρει στη συνέχεια το πεδίο που ονομάζεται n.
Anita είναι ένας δείκτης, αλλά είναι ό, τι * anita;
Τι θα βρείτε όταν θα πάτε σε ό, τι Anita είναι στραμμένο προς;
Ένα struct, ένας κόμβος, και ένας κόμβος, ανάκληση, έχει ένα πεδίο που ονομάζεται n
γιατί έχει, θυμάμαι, αυτά τα 2 πεδία, δίπλα και n,
που είδαμε πριν από λίγο εδώ.
>> Για να μιμηθούν την πραγματικότητα αυτή σε κώδικα,
θα μπορούσαμε να το κάνουμε αυτό και να πω εάν ((* anita). == n n), το n που ψάχνω.
Σημειώστε ότι η λειτουργία ψηφίστηκε ο αριθμός νοιάζει.
Στη συνέχεια, μπορώ να πάω μπροστά και να κάνουμε κάτι σαν επιστροφή αλήθεια.
Αλλιώς, αν αυτό δεν είναι η περίπτωση, αυτό που θέλω να κάνω;
Πώς μπορώ να μεταφράσει κώδικα Τι Anita έκανε ενστικτωδώς με τα πόδια μέσα από την λίστα;
Τι πρέπει να κάνω εδώ την προσομοίωση Anita λαμβάνοντας αυτό το βήμα προς τα αριστερά, αυτό το βήμα προς τα αριστερά;
[Ακούγεται ανταπόκριση των φοιτητών] >> Τι είναι αυτό;
[Ακούγεται ανταπόκριση των φοιτητών]
Καλό, δεν είναι κακή ιδέα, αλλά και στο παρελθόν, όταν έχουμε κάνει αυτό, έχουμε κάνει anita + +
γιατί αυτό θα προσθέσετε τον αριθμό 1 έως Anita,
η οποία τυπικά θα το σημείο στο επόμενο πρόσωπο, όπως Ramon,
ή το πρόσωπο δίπλα του, ή ο δίπλα του προσώπου κάτω από τη γραμμή.
Αλλά αυτό δεν είναι αρκετά καλό, διότι εδώ τι σημαίνει αυτό το πράγμα μοιάζει στη μνήμη;
Δεν είναι αυτό. Πρέπει να την απενεργοποιήσετε.
Μοιάζει με αυτό στη μνήμη, και παρόλο που έχω σχεδιάσει 1 και 2 και 3 κοντά το ένα στο άλλο,
αν θέλουμε πραγματικά να προσομοιώνουν αυτό-μπορεί να σας παιδιά, ενώ εξακολουθούν να δείχνουν στα ίδια τα άτομα,
μπορεί κάποιοι από εσάς να λάβει ένα τυχαίο βήμα πίσω, κάποια από εσάς ένα τυχαίο βήμα προς τα εμπρός;
>> Αυτό το χάλι είναι ακόμα μια συνδεδεμένη λίστα,
αλλά αυτοί οι τύποι θα μπορούσε να είναι οπουδήποτε στη μνήμη,
έτσι anita + + δεν πρόκειται να λειτουργήσει γιατί;
Τι είναι σε θέση anita + +;
Ποιος ξέρει.
Είναι κάποια άλλη αξία ότι ακριβώς έτσι συμβαίνει να παρεμβάλλεται
μεταξύ όλων αυτών των κόμβων κατά τύχη, επειδή δεν είμαστε χρησιμοποιώντας μια σειρά.
Εμείς χορηγούνται καθένα από αυτούς τους κόμβους χωριστά.
Εντάξει, αν εσείς μπορείτε να καθαρίσετε τον εαυτό σας να δημιουργήσετε αντίγραφα ασφαλείας.
Επιτρέψτε μου να προτείνω ότι αντί του anita + +, αντί να κάνουμε anita παίρνει-
καλά, γιατί δεν πάμε σε ό, τι Anita είναι στραμμένο προς και στη συνέχεια κάντε. το επόμενο βήμα;
Με άλλα λόγια, πάμε να Ραμόν, ο οποίος κρατάει τον αριθμό 22,
και στη συνέχεια. επόμενο είναι σαν Anita θα αντιγράφοντας το αριστερό δείκτη του χεριού του.
Αλλά δεν θα πάω μακρύτερα από ό, τι Ramon επειδή βρήκαμε 22.
Αλλά αυτό θα ήταν η ιδέα. Τώρα, αυτό είναι ένας θεός-φοβερό χάος.
Ειλικρινά, κανείς δεν θα θυμάται ποτέ αυτήν τη σύνταξη, και έτσι ευτυχώς,
είναι πραγματικά λίγο σκόπιμη-OH, δεν έχετε πραγματικά να δείτε τι έγραψα.
Αυτό θα ήταν πιο συναρπαστικό, αν μπορούσε. Voila!
>> Πίσω από τις σκηνές, είχα την επίλυση του προβλήματος με αυτόν τον τρόπο.
Anita, να κάνουμε αυτό το βήμα προς τα αριστερά,
Αρχικά, πηγαίνουν στη διεύθυνση που Anita είναι στραμμένο προς
όπου και θα βρείτε όχι μόνο ν, που μόλις ελέγχονται για σκοπούς σύγκρισης,
αλλά θα βρείτε επίσης επόμενο - στην περίπτωση αυτή,
Αριστερό χέρι του Ramon δείχνοντας στον επόμενο κόμβο της λίστας.
Αλλά αυτό είναι ο θεός-φοβερό χάος στην οποία αναφέρθηκα νωρίτερα,
αλλά βγάζει C μας επιτρέπει να απλοποιήσει αυτό.
Αντί της γραφής (* anita), μπορούμε να γράψει αντί απλώς anita-> n,
και αυτό είναι ακριβώς το ίδιο πράγμα λειτουργικά, αλλά είναι πολύ πιο έξυπνο,
και είναι πολύ πιο συνεπής με την εικόνα που έχουμε την κατάρτιση
όλο αυτό το διάστημα χρησιμοποιώντας τα βέλη.
>> Τέλος, τι πρέπει να κάνουμε στο τέλος αυτού του προγράμματος;
Υπάρχει μία γραμμή κώδικα που απομένουν.
Επιστροφή τι;
Λάθος, γιατί αν έχουμε όλο το while loop
και Anita είναι, στην πραγματικότητα, μηδενική, αυτό σημαίνει ότι πήγε σε όλη τη διαδρομή μέχρι το τέλος της λίστας
όπου έδειχνε σε-τι είναι το όνομά σας και πάλι;
Ari αριστερό χέρι. >> Αρη, η οποία είναι άκυρη.
Anita είναι πλέον μηδενική, και συνειδητοποιώ είστε ακριβώς στέκεται εδώ αμήχανα στο κενό
επειδή θα πάω μακριά σε ένα μονόλογο εδώ,
αλλά θα σας συμμετοχή και πάλι σε λίγο.
Anita είναι μηδενική σε αυτό το σημείο στην ιστορία, έτσι ο βρόχος τερματίζεται, ενώ,
και θα πρέπει να επιστρέψει ψευδείς, διότι αν πήρε όλη τη διαδρομή μέχρι δείκτη null Αρη
τότε δεν υπήρχε αριθμός ότι ζήτησε από τη λίστα.
Μπορούμε να καθαρίσει αυτό πάρα πολύ, αλλά αυτό είναι μια πολύ καλή εφαρμογή τότε
από μια συνάρτηση διάσχισης, μια λειτουργία της αναζήτησης για μια συνδεδεμένη λίστα.
Είναι ακόμα γραμμική αναζήτηση, αλλά δεν είναι τόσο απλό όσο μια + + δείκτης
+ + ή μια μεταβλητή i, διότι τώρα δεν μπορούμε να μαντέψει
όπου κάθε ένα από αυτούς τους κόμβους είναι στη μνήμη.
Πρέπει να ακολουθήσει κυριολεκτικά το ίχνος της πορείες ή, πιο συγκεκριμένα,
δείκτες, για να πάρει από τον ένα κόμβο στον άλλο.
>> Τώρα ας προσπαθήσουμε ένα άλλο. Anita, θέλετε να επιστρέψετε εδώ;
Γιατί δεν πάμε μπροστά και να διαθέσει ένα άλλο πρόσωπο από το κοινό;
Malloc-τι είναι το όνομά σου; >> Rebecca.
Rebecca. Rebecca έχει malloced από το κοινό,
και αυτή είναι τώρα αποθηκεύει τον αριθμό 55.
Και ο στόχος είναι στο χέρι τώρα Anita για να εισάγετε
Rebecca στη συνδεδεμένη λίστα εδώ στην κατάλληλη θέση.
Ελάτε εδώ για μια στιγμή.
Έχω κάνει κάτι τέτοιο.
Έχω κάνει κόμβο *. Και τι είναι το όνομά σας και πάλι;
Rebecca. >> Rebecca, εντάξει.
Rebecca παίρνει malloc (sizeof (κόμβος)).
Ακριβώς όπως έχουμε διαθέσει τα πράγματα όπως τους φοιτητές και εταζέρα στο παρελθόν,
χρειαζόμαστε το μέγεθος του κόμβου, έτσι και τώρα Rebecca
δείχνει σε τι;
Rebecca έχει δύο πεδία μέσα της, ένα από τα οποία είναι 55.
Ας κάνουμε ό, τι, rebecca-> = 55.
Στη συνέχεια, όμως rebecca-> επόμενο θα πρέπει να-όπως τώρα, το χέρι της είναι το είδος του ποιος ξέρει;
Είναι δείχνοντας κάποια αξία σκουπίδια, οπότε γιατί να μην το κάνει για το καλό μέτρο
εμείς τουλάχιστον το κάνουμε αυτό, έτσι ώστε το αριστερό χέρι είναι τώρα στο πλευρό της.
Τώρα, Anita, πάρτε από εδώ.
Έχετε Rebecca έχουν διατεθεί.
Προχωρήστε και βρείτε πού θα πρέπει να βάλουμε Rebecca.
Καλό, πολύ καλό.
Εντάξει, καλά, και τώρα θα πρέπει να παρέχουν ένα κομμάτι της κατεύθυνσης,
έτσι έχετε φτάσει Ari.
Το αριστερό του χέρι είναι μηδενική, αλλά Rebecca ανήκει σαφώς στα δεξιά,
ναι, πώς πρέπει να αλλάξει αυτή συνδεδεμένη λίστα
προκειμένου να τοποθετήσετε Rebecca στην κατάλληλη θέση;
Αν μπορούσε να κινηθεί αριστερά κυριολεκτικά τα χέρια των ανθρώπων γύρω, όπως απαιτείται,
θα λύσει το πρόβλημα με αυτόν τον τρόπο.
Εντάξει, καλά, και εν τω μεταξύ, το αριστερό χέρι της Ρεβέκκας είναι τώρα από την πλευρά της.
>> Αυτό ήταν πάρα πολύ εύκολο.
Ας προσπαθήσουμε κατανομή-εργαζόμαστε σχεδόν τελειώσει, 20.
Εντάξει, έλα επάνω.
20 έχει διατεθεί, οπότε επιτρέψτε μου να προχωρήσει και να πω και πάλι εδώ
έχουμε κάνει μόνο κόμβο Saad *.
Έχουμε malloc (sizeof (κόμβος)).
Κάνουμε λοιπόν την ίδια ακριβώς σύνταξη, όπως κάναμε πριν για 20,
και εγώ θα κάνουμε στη συνέχεια NULL =, και τώρα είναι στο χέρι Anita
για την εισαγωγή σας στην συνδεδεμένη λίστα, αν θα μπορούσε να παίξει αυτό το ρόλο ακριβώς το ίδιο.
Εκτέλεση.
Εντάξει, καλά.
Τώρα σκεφτείτε προσεκτικά πριν αρχίσει να κινείται αριστερά χέρια γύρω.
Μπορείτε από τώρα πήρε την πιο δύσκολη ρόλο σήμερα.
Ποιανού το χέρι θα πρέπει να μετακινηθεί πρώτα;
Εντάξει, περιμένετε, ακούω κάποια δεν είναι.
Αν κάποιοι λαοί θα ήθελα ευγενικά να βοηθήσει στην επίλυση μια δύσκολη κατάσταση εδώ.
Ποιανού το αριστερό χέρι θα πρέπει να ενημερώνονται πρώτα ίσως; Ναι.
[Φοιτητικό] του Saad.
Εντάξει, είναι Saad, γιατί όμως;
[Ακούγεται ανταπόκριση των φοιτητών]
Καλό, γιατί αν κινηθούμε-τι είναι το όνομά σου; >> Μάρσαλ.
Marshall, αν κινούμαστε πρώτος το χέρι του κάτω σε null,
τώρα έχουμε κυριολεκτικά ορφανά τέσσερα άτομα σε αυτήν τη λίστα
επειδή ήταν το μόνο πράγμα που δείχνει στο Ραμόν και ο καθένας προς τα αριστερά,
έτσι ότι η ενημέρωση δείκτης πρώτη ήταν κακή.
Ας ανατρέψουμε.
Καλό, και τώρα να προχωρήσει και να μετακινήσετε το κατάλληλο αριστερό χέρι δείχνοντας Ραμόν.
Αυτό αισθάνεται λίγο περιττή.
Τώρα υπάρχουν δύο άνθρωποι που δείχνουν στο Ramon, αλλά ότι είναι εντάξει
γιατί τώρα πώς αλλιώς δεν θα επικαιροποιεί τον κατάλογο;
Ποια άλλη πλευρά πρέπει να κινηθεί;
Εξαιρετική, τώρα έχουμε χάσει κάθε μνήμη;
Όχι, τόσο καλά, ας δούμε αν μπορούμε να μην μπορεί να σπάσει αυτό για μια ακόμη φορά.
>> Mallocing για μια τελευταία φορά, αριθμός 5.
Όλος ο τρόπος στην πλάτη, έλα κάτω.
Είναι πολύ συναρπαστικό.
[Χειροκροτήματα]
Ποιο είναι το όνομά σου; >> Ρον.
Ron, εντάξει, σας malloced τον αριθμό 5.
Έχουμε εκτελούνται μόνο κώδικα που είναι σχεδόν ίδια με αυτά
μόνο με ένα διαφορετικό όνομα.
Εξαιρετική.
Τώρα, Anita, καλή τύχη εισάγοντας τον αριθμό 5 στην λίστα τώρα.
Καλό, και;
Εξαιρετική, έτσι αυτό είναι πραγματικά η τρίτη από τις τρεις συνολικά περιπτώσεις.
Είχαμε πρώτη φορά που κάποιος στο τέλος, Ρεβέκκα.
Είχαμε τότε κάποιος στη μέση.
Τώρα έχουμε κάποιον στην αρχή, και σε αυτό το παράδειγμα,
τώρα έπρεπε να ενημερώσει Lucas για πρώτη φορά
επειδή το πρώτο στοιχείο στη λίστα έχει τώρα με το σημείο σε ένα νέο κόμβο,
ο οποίος, με τη σειρά του, δείχνει στον κόμβο αριθμό 9.
>> Αυτή ήταν μια εξαιρετικά δύσκολη επίδειξη, είμαι βέβαιος,
έτσι ένα μεγάλο χειροκρότημα για αυτά τα παιδιά, αν μπορούσε.
Όμορφα γίνει.
Αυτό είναι όλο. Μπορείτε να κρατήσετε τα κομμάτια σας από το χαρτί ως μια μικρή μνήμη.
Αποδεικνύεται ότι το κάνουμε αυτό σε κώδικα
δεν είναι τόσο απλή όσο ακριβώς κινείται γύρω από τα χέρια
και δείχνοντας δείκτες σε διαφορετικά πράγματα.
Αλλά συνειδητοποιούν ότι όταν έρχεται η ώρα να εφαρμόσει κάτι σαν
μια συνδεδεμένη λίστα ή μια παραλλαγή του αυτό, αν επικεντρωθεί σε πραγματικά
αυτά τα βασικά μεγέθη, οι δάγκωμα-μεγέθους προβλήματα που έχω να καταλάβω,
είναι αυτό το χέρι ή το χέρι, να συνειδητοποιήσουν ότι αυτό που κατά τα άλλα είναι ένα αρκετά πολύπλοκο πρόγραμμα
μπορεί, στην πραγματικότητα, να μειωθεί σε αρκετά απλή δομικά σαν αυτό.
>> Ας πάρουμε όμως τα πράγματα σε μια πιο εξελιγμένη κατεύθυνση ακόμα.
Έχουμε τώρα την έννοια του συνδεδεμένη λίστα.
Έχουμε επίσης-χάρη στην πρόταση-πίσω υπάρχει μια διπλά συνδεδεμένη λίστα,
η οποία φαίνεται σχεδόν το ίδιο, αλλά τώρα έχουμε δύο δείκτες στο εσωτερικό του struct
αντί για ένα, και θα μπορούσαμε να καλέσετε πιθανώς οι δείκτες προηγούμενο και επόμενο
ή αριστερά ή δεξιά, αλλά εμείς, στην πραγματικότητα, χρειάζονται δύο από αυτούς.
Ο κωδικός θα είναι λίγο πιο περίπλοκη.
Anita θα έπρεπε να κάνει περισσότερη δουλειά εδώ στη σκηνή.
Αλλά θα μπορούσαμε να εφαρμόσουμε σίγουρα αυτό το είδος της δομής.
Από την άποψη της διάρκειας, όμως, τι θα ήταν ο χρόνος εκτέλεσης
Anita για την εξεύρεση αριθμό n σε μια συνδεδεμένη λίστα τώρα;
Ακόμα μεγάλη Ξ n, έτσι δεν είναι καλύτερη από ό, τι γραμμική αναζήτηση.
Δεν μπορούμε να κάνουμε δυαδική αναζήτηση, όμως, και πάλι.
Γιατί ήταν ότι η υπόθεση; Δεν μπορείτε να ρίξουν μια ματιά.
Ακόμα κι αν βλέπουμε προφανώς το σύνολο των ανθρώπων πάνω στη σκηνή,
Anita και θα μπορούσε να το eyeballed και είπε: «Εδώ είναι η μέση της λίστας,"
ότι δεν θα ξέρει ότι αν ήταν το πρόγραμμα του υπολογιστή
γιατί το μόνο πράγμα που είχε να προσδεθούμε σε κατά την έναρξη του σεναρίου
ήταν Lucas, ο οποίος ήταν ο πρώτος δείκτης.
Αυτή θα πρέπει αναγκαστικά να ακολουθήσει αυτούς τους δεσμούς,
μετρώντας τον τρόπο της μέχρι να βρεθεί περίπου στη μέση,
και ακόμα και τότε, δεν πρόκειται να ξέρει όταν έχει φτάσει στη μέση
εκτός αν πηγαίνει σε όλη τη διαδρομή μέχρι το τέλος για να καταλάβουμε πόσα υπάρχουν,
στη συνέχεια υπαναχωρεί, και ότι επίσης θα είναι δύσκολο αν δεν είχε
μια διπλά συνδεδεμένη λίστα κάποιου είδους.
>> Επίλυση κάποια προβλήματα σήμερα, αλλά την εισαγωγή τους άλλους.
Τι θα γίνει με μια διαφορετική δομή δεδομένων εντελώς;
Αυτή είναι μια φωτογραφία των δίσκων σε Mather House,
και σε αυτή την περίπτωση, έχουμε μια δομή δεδομένων που έχουμε, επίσης, το είδος των ήδη μιλάμε.
Μιλήσαμε για μια στοίβα στο πλαίσιο της μνήμης,
και ότι είναι είδος που ονομάζεται σκόπιμα επειδή μια στοίβα με τους όρους της μνήμης
είναι ουσιαστικά μια δομή δεδομένων που έχει όλο και περισσότερα πράγματα σε επίπεδα πάνω από αυτό.
Αλλά το ενδιαφέρον πράγμα για μια στοίβα, όπως είναι η περίπτωση, στην πραγματικότητα,
είναι ότι είναι ένα ιδιαίτερο είδος των δεδομένων δομής.
Είναι μια δομή δεδομένων οπότε το πρώτο στοιχείο στην
είναι το τελευταίο στοιχείο έξω.
Αν είστε ο πρώτος δίσκος να τεθεί στη στοίβα,
εσείς πρόκειται να είναι, δυστυχώς, ο τελευταίος δίσκος που πρέπει να ληφθούν από τη στοίβα,
και ότι δεν είναι απαραίτητα ένα καλό πράγμα.
Αντίθετα, μπορείτε να σκεφτείτε το αντίστροφο,
το τελευταίο είναι η πρώτη έξω.
>> Τώρα, μην τυχόν σενάρια έρχονται στο μυαλό, όπου έχει μια στοίβα
δομή δεδομένων όπου θα έχουν αυτό το ακίνητο
από την τελευταία in, first out, είναι πραγματικά συναρπαστικό;
Είναι αυτό ένα καλό πράγμα; Είναι αυτό ένα κακό πράγμα;
Είναι σίγουρα ένα κακό πράγμα, αν οι δίσκοι δεν ήταν όλα ίδια
και ήταν όλοι ειδική διαφορετικά χρώματα ή οτιδήποτε,
και το χρώμα που θέλετε είναι όλος ο τρόπος στο κάτω μέρος.
Φυσικά, δεν μπορείτε να πάρετε ότι χωρίς μεγάλη προσπάθεια.
Θα πρέπει να ξεκινήσει από την κορυφή και το έργο το δρόμο σας προς τα κάτω.
Ομοίως, τι αν ήταν ένα από αυτά τα αγόρια ανεμιστήρα
ο οποίος περιμένει μέχρι όλη τη νύχτα προσπαθώντας να πάρει ένα iPhone και γραμμές μέχρι
σε ένα μέρος όπως αυτό;
Δεν θα ήταν ωραίο αν το κατάστημα της Apple
ήταν μία δομή δεδομένων στοίβα;
Yay; Nay;
Είναι μόνο καλό για τους ανθρώπους που εμφανίζονται στην τελευταία στιγμή
και στη συνέχεια να πάρει βγαλμένα από την ουρά.
Και στην πραγματικότητα, το γεγονός ότι ήμουν τόσο την τάση να πούμε ουρά
είναι πραγματικά συνεπής με αυτό που θα ονομάζαμε αυτό το είδος των δεδομένων δομής,
ένα στην πραγματικότητα, όπου η σειρά έχει σημασία,
και θέλετε το πρώτο, για να είναι η πρώτη από
έστω και μόνο για χάρη της ανθρώπινης δικαιοσύνης.
Θα καλέσετε γενικά ότι μια δομή δεδομένων ουρά.
>> Βγάζει εκτός από συνδεδεμένες λίστες, μπορούμε να αρχίσετε να χρησιμοποιείτε τις ίδιες βασικές ιδέες
και να αρχίσει η δημιουργία νέων και διαφορετικών τύπων των λύσεων στα προβλήματα.
Για παράδειγμα, στην περίπτωση ενός σωρού, θα μπορούσαμε να αντιπροσωπεύουν μια στοίβα
χρησιμοποιώντας μια δομή δεδομένων, όπως αυτό, θα ήθελα να προτείνω.
Σε αυτή την περίπτωση, έχω δηλώσει ένα struct, και έχω πει μέσα από αυτή τη δομή
είναι μία σειρά από αριθμούς και στη συνέχεια μια μεταβλητή που ονομάζεται μέγεθος,
και εγώ είμαι πρόκειται να καλέσετε αυτό το πράγμα μια στοίβα.
Τώρα, γιατί αυτό πραγματικά εργασία;
Στην περίπτωση μιας στοίβας, θα μπορούσε να αντλήσει αποτελεσματικά αυτή την οθόνη, όπως μια σειρά.
Εδώ είναι το stack μου. Αυτοί είναι οι αριθμοί μου.
Και εμείς θα τους επιστήσει όπως αυτό, αυτό, αυτό, αυτό, αυτό.
Και τότε έχω κάποιο άλλο μέλος εδώ δεδομένων,
το οποίο ονομάζεται μέγεθος, έτσι αυτό είναι το μέγεθος, και αυτό είναι αριθμοί,
και συλλογικά, ολόκληρο το iPad εδώ αντιπροσωπεύει μια δομή στοίβας.
Τώρα, από προεπιλογή, το μέγεθος έχει κατά πάσα πιθανότητα έχεις να αρχικοποιείται σε 0,
και τι είναι μέσα από τη σειρά των αριθμών που αρχικά
όταν διαθέτουν για πρώτη φορά ένα πίνακα;
Σκουπίδια. Ποιος ξέρει; Και δεν πειράζει πραγματικά.
Δεν έχει σημασία αν αυτό είναι 1, 2, 3, 4, 5, εντελώς τυχαία
από κακή τύχη αποθηκεύονται στη δομή μου, γιατί εφ 'όσον ξέρω ότι το μέγεθος της στοίβας
είναι 0, τότε ξέρω προγραμματισμό, δεν φαίνονται σε κανένα από τα στοιχεία του πίνακα.
Δεν έχει σημασία τι υπάρχει εκεί.
Μην κοιτάτε τους, καθώς θα είναι η επίπτωση της μέγεθος 0.
>> Αλλά ας υποθέσουμε τώρα να προχωρήσει και να τοποθετήσετε κάτι στο σωρό.
Θέλω να εισαγάγετε τον αριθμό 5, έτσι έβαλα εδώ αριθμό 5,
και στη συνέχεια, τι μπορώ να τοποθετήσω εδώ κάτω;
Τώρα θα ήθελα πραγματικά βάλει κάτω 1 για το μέγεθος,
και τώρα η στοίβα έχει μέγεθος 1.
Τι θα συμβεί αν πάω μπροστά και τοποθετήστε τον αριθμό, ας πούμε, 7 επόμενη;
Αυτό στη συνέχεια παίρνει ενημερώνεται σε 2, και στη συνέχεια θα κάνουμε 9,
και στη συνέχεια αυτό παίρνει ενημερωθεί σε 3.
Αλλά το ενδιαφέρον χαρακτηριστικό τώρα αυτής της στοίβας είναι ότι
Είμαι υποτίθεται για να αφαιρέσετε το οποίο στοιχείο αν θέλω να σκάσει
κάτι μακριά από το σωρό, να το πω έτσι;
9 θα ήταν το πρώτο πράγμα που πρέπει να πάνε.
Πώς θα πρέπει η εικόνα να αλλάξει αν θέλω να σκάσει ένα στοιχείο από τη στοίβα,
Μοιάζει πολύ με ένα δίσκο στο Mather;
Ναι. >> [Φοιτητικό] Σετ για το μέγεθος 2.
Ακριβώς, το μόνο που κάνετε είναι να ρυθμίσετε το μέγεθος σε 2, και τι μπορώ να κάνω με τη σειρά;
Δεν έχω να κάνω τίποτα.
Θα μπορούσα, ακριβώς για να είναι πρωκτική, βάλτε εκεί ένα 0 ή -1 ή κάτι για να δηλώσουν
ότι αυτό δεν είναι ένα legit αξία, αλλά αυτό δεν έχει σημασία γιατί
Μπορώ να καταγράφουν εκτός του πίνακα η ίδια πόσο καιρό είναι
έτσι ώστε να ξέρω μόνο να δούμε τα δύο πρώτα στοιχεία αυτού του πίνακα.
Τώρα, αν πάω και να προσθέσετε τον αριθμό 8 του παρόντος πίνακα, πώς να αλλάξει η εικόνα το επόμενο βήμα;
Αυτό γίνεται 8, και αυτό γίνεται 3.
Είμαι κοπή μερικές γωνίες εδώ.
Τώρα έχουμε 5, 7, 8, και είμαστε πίσω σε μέγεθος 3.
Αυτό είναι αρκετά απλό στην εφαρμογή του,
αλλά όταν θα πάμε να λύπη την απόφαση αυτή του σχεδιασμού;
Πότε αρχίζουν τα πράγματα να πάνε πολύ, πολύ λάθος; Ναι.
[Ακούγεται ανταπόκριση των φοιτητών]
Όταν θέλετε να πάτε πίσω και να πάρει το πρώτο στοιχείο που βάζετε μέσα
>> Αποδεικνύεται εδώ ακόμη και αν μια στοίβα είναι ένας πίνακας κάτω από την κουκούλα,
αυτές οι δομές δεδομένων που έχουμε αρχίσει να μιλάμε για επίσης γενικά γνωστό ως
αφηρημένες δομές δεδομένων σύμφωνα με την οποία το πώς είστε εφαρμογή
είναι εντελώς εκτός από το σημείο.
Μια δομή δεδομένων, όπως μια στοίβα υποτίθεται για να προσθέσετε υποστήριξη
επιχειρήσεις όπως ωθήσεως, το οποίο ωθεί ένα δίσκο πάνω στην στοίβα,
και ποπ, που διαγράφει ένα στοιχείο από τη στοίβα, και αυτό είναι αυτό.
Εάν επρόκειτο να κατεβάσετε τον κώδικα κάποιου άλλου που ήδη εφαρμόζονται
αυτό το πράγμα που ονομάζεται μια στοίβα, το πρόσωπο αυτό θα είχε γράψει
μόνο δύο λειτουργίες για σας, πιέστε και ποπ, της οποίας μοναδικός σκοπός στη ζωή
θα ήταν να κάνει ακριβώς αυτό.
Εσείς ή αυτόν ή αυτήν που εφαρμόζεται το πρόγραμμα
θα ήταν εντελώς ο ένας να αποφασίσουν πώς θα εφαρμόσουν
η σημασιολογία του να πιέζει και να βρεθώ κάτω από την κουκούλα
ή η λειτουργικότητα του να πιέζει και σκάει.
Και έχω κάνει μια κάπως κοντόφθαλμη απόφαση εδώ
με την εφαρμογή stack μου με αυτή την απλή δομή δεδομένων για ποιο λόγο;
Όταν κάνει αυτό το διάλειμμα δομή δεδομένων;
Σε ποιο σημείο μπορώ να επιστρέψει ένα σφάλμα όταν ο χρήστης καλεί ώθηση, για παράδειγμα;
[Φοιτητικό] Εάν δεν υπάρχει περισσότερος χώρος.
Ακριβώς, αν δεν είναι κανένα περισσότερο χώρο, αν έχω υπέρβαση της ικανότητας,
που είναι όλα τα καλύμματα, γιατί δείχνει ότι είναι κάποιο είδος της παγκόσμιας σταθεράς.
Καλά, τότε είμαι απλώς πρόκειται να πρέπει να πω, "Συγγνώμη, δεν μπορώ να πιέσω άλλο αξία
στη στοίβα, "όπως και σε Mather.
>> Σε κάποιο σημείο, από όπου και αν πρόκειται να χτυπήσει το πάνω μέρος του αυτό το μικρό υπουργικό συμβούλιο.
Δεν υπάρχει περισσότερο χώρο ή χωρητικότητα στη στοίβα, σε σημείο που δεν υπάρχει κάποιο είδος του λάθους.
Θα πρέπει να θέσει το στοιχείο κάπου αλλού, ο δίσκος κάπου αλλού,
ή πουθενά καθόλου.
Τώρα, με την ουρά, θα μπορούσαμε να εφαρμόσουμε το λίγο διαφορετικά.
Μια ουρά είναι λίγο διαφορετικό από το ότι κάτω από την καλύπτρα, μπορεί να εφαρμοστεί
ως μια σειρά, αλλά γιατί, στην περίπτωση αυτή, είμαι προτείνοντας
να έχουν επίσης ένα στοιχείο κεφαλής που αντιπροσωπεύει την κεφαλή της λίστας,
το μπροστινό μέρος της λίστας, το πρώτο πρόσωπο στη γραμμή στο κατάστημα της Apple, εκτός από το μέγεθος;
Γιατί χρειάζομαι ένα επιπλέον κομμάτι των δεδομένων εδώ;
Σκεφτείτε πίσω σε ό, τι είναι οι αριθμοί
αν έχω σχεδιάσει αυτό ως εξής.
Ας υποθέσουμε ότι αυτή είναι τώρα μια ουρά αντί ενός σωρού,
η διαφορά είναι-όπως ακριβώς και το κατάστημα Apple-ουρά είναι δίκαιη.
Το πρώτο πρόσωπο στη γραμμή κατά την έναρξη της λίστας, αριθμός 5 σε αυτή την περίπτωση,
αυτός ή αυτή πρόκειται να αφήσει στο κατάστημα πρώτα.
Ας το κάνουμε αυτό.
Ας υποθέσουμε ότι αυτή είναι η κατάσταση της ουράς μου αυτή τη στιγμή, και τώρα το κατάστημα της Apple
ανοίγει και το πρώτο πρόσωπο, ο αριθμός 5, οδηγείται μέσα στο κατάστημα.
Πώς μπορώ να αλλάξω την εικόνα τώρα που έχω απο-ουρά το πρώτο πρόσωπο
στο μέτωπο της γραμμής;
Τι είναι αυτό; >> [Φοιτητικό] Αλλάξτε την ουρά.
Αλλάξτε το κεφάλι, οπότε 5 εξαφανίζεται.
Στην πραγματικότητα, είναι σαν-τον καλύτερο τρόπο για να το κάνουμε αυτό;
Στην πραγματικότητα, είναι σαν αυτός ο τύπος εξαφανίζεται.
Τι θα κάνει νούμερο 7 σε ένα πραγματικό κατάστημα;
Θα κάνουμε ένα μεγάλο βήμα προς τα εμπρός.
>> Αλλά αυτό που έχουμε έρθει να εκτιμήσουν, όταν πρόκειται για πίνακες
και κινείται γύρω από τα πράγματα;
Αυτό είναι το είδος του ένα χάσιμο του χρόνου σας, έτσι δεν είναι;
Γιατί πρέπει να είναι τόσο πρωκτική ώστε να έχουν τον πρώτο πρόσωπο
κατά την έναρξη της γραμμής στα σωματικά την έναρξη της κομμάτι της μνήμης;
Αυτό είναι εντελώς περιττό. Γιατί;
Τι θα μπορούσα να θυμάμαι μόνο αντ 'αυτού; >> [απάντηση ακούγεται φοιτητής]
Ακριβώς, θα μπορούσα απλά να θυμάστε με αυτό το πρόσθετο μέλος κεφάλι δεδομένων
ότι σήμερα ο επικεφαλής της λίστας δεν είναι πλέον 0, το οποίο ήταν μια στιγμή πριν.
Τώρα είναι στην πραγματικότητα ο αριθμός 1. Με τον τρόπο αυτό, να πάρω μια μικρή βελτιστοποίηση.
Ακριβώς επειδή έχω απο-ουρά κάποιος από τη γραμμή στην αρχή της γραμμής στο κατάστημα της Apple
δεν σημαίνει ότι ο καθένας πρέπει να αλλάξει, το οποίο ανάκληση είναι μια γραμμική λειτουργία.
Μπορώ να περάσουν αντί σταθερό χρόνο μόνο
και να επιτευχθεί στη συνέχεια μια πολύ ταχύτερη απόκριση.
Αλλά η τιμή είμαι πληρώνουν ό, τι είναι να κερδίσει αυτό το επιπλέον απόδοση
και δεν χρειάζεται να αλλάξει ο καθένας;
Ναι. >> [Ακούγεται ανταπόκριση των φοιτητών]
Μπορεί να προσθέσει περισσότερους ανθρώπους, καλά, ότι το πρόβλημα είναι ορθογώνια
για το γεγονός ότι δεν είμαστε μετατόπιση ανθρώπους γύρω.
Είναι ακόμα μια σειρά, έτσι ώστε αν ή όχι ο καθένας αλλαγή ή όχι-
OH, βλέπω τι εννοείς, εντάξει.
Στην πραγματικότητα, συμφωνώ με αυτό που λες στο ότι είναι σχεδόν σαν να
είμαστε τώρα ποτέ δεν πρόκειται να χρησιμοποιήσετε την έναρξη αυτού του πίνακα πια
γιατί αν μπορώ να αφαιρέσω 5, τότε μπορώ να αφαιρέσω 7.
Αλλά έβαλα μόνο τους ανθρώπους προς τα δεξιά.
>> Νιώθω σαν να είμαι σπατάλη χώρου, και τελικά ουρά μου διαλύεται σε τίποτα δεν σε όλα,
έτσι θα μπορούσαμε να έχουμε ακριβώς τους ανθρώπους περιτύλιξης,
και θα μπορούσαμε να σκεφτούμε αυτού του πίνακα πραγματικά ως ένα είδος κυκλικού οικοδομήματος,
αλλά χρησιμοποιούμε τον τελεστή σε C για να κάνει αυτό το είδος της περιτύλιξης;
[Ακούγεται ανταπόκριση των φοιτητών] >> Ο χειριστής modulo.
Θα ήταν λίγο ενοχλητικό να σκεφτεί μέσω πώς κάνετε το περιτύλιξης,
αλλά θα μπορούσαμε να το κάνουμε, και θα μπορούσαμε να αρχίζουν να βάζουν τους ανθρώπους σε ό, τι χρησιμοποιείται για να είναι το μέτωπο της γραμμής,
αλλά απλά να θυμάστε αυτή τη μεταβλητή με το κεφάλι ποιος είναι ο πραγματικός αρχηγός της γραμμής είναι στην πραγματικότητα.
Τι θα συμβεί αν, αντ 'αυτού, στόχος μας τελικά, αν και,
ήταν να δούμε τους αριθμούς, όπως κάναμε εδώ στη σκηνή με Anita,
αλλά θέλουμε πραγματικά το καλύτερο όλων αυτών των κόσμων;
Θέλουμε περισσότερη πολυπλοκότητα από σειρά επιτρέπει
γιατί θέλουμε την ικανότητα να αναπτύσσονται δυναμικά τη δομή των δεδομένων.
Αλλά δεν θέλουμε να χρειαστεί να καταφύγουν σε κάτι που επισημάναμε
στην πρώτη διάλεξη δεν ήταν ένας αλγόριθμος βέλτιστης,
εκείνη της γραμμικής αναζήτησης.
Αποδεικνύεται ότι μπορείτε να, στην πραγματικότητα, να επιτύχουν
ή τουλάχιστον κοντά σε σταθερό χρόνο, σύμφωνα με την οποία κάποιος σαν Anita,
αν διαμορφώνει δομή δεδομένων της να μην είναι μια συνδεδεμένη λίστα,
να μην είναι μια στοίβα, να μην είναι μια ουρά, θα μπορούσε, στην πραγματικότητα,
καταλήξουμε σε μια δομή δεδομένων η οποία της επιτρέπει να δούμε τα πράγματα,
ακόμη και οι λέξεις, όχι μόνο αριθμούς, σε ό, τι θα καλέσουμε σταθερό χρόνο.
>> Και στην πραγματικότητα, κοιτάζοντας μπροστά, μία από τις psets σε αυτή την τάξη είναι σχεδόν πάντα
μια υλοποίηση ενός ορθογράφος, οπότε
σας δίνουμε και πάλι περίπου 150.000 αγγλικές λέξεις και ο στόχος είναι να
φορτώσετε στη μνήμη εκείνων γρήγορα και να είναι σε θέση να απαντήσει στις ερωτήσεις του εντύπου
είναι αυτή η λέξη είναι γραμμένες σωστά;
Και θα ήταν πραγματικά πιπιλίζουν αν έπρεπε να επαναλάβει σε όλα τα 150.000 λέξεις για να απαντήσω σε αυτό.
Αλλά, στην πραγματικότητα, θα δούμε ότι μπορούμε να το κάνουμε σε πολύ, πολύ γρήγορο χρόνο.
Και πρόκειται να συνεπάγεται την εφαρμογή κάτι που ονομάζεται ένα πίνακα κατακερματισμού,
και παρόλο που με την πρώτη ματιά αυτό το πράγμα που ονομάζεται hash πίνακας πρόκειται να
ας την επίτευξη αυτών των σούπερ ταχεία χρόνους απόκρισης,
αποδεικνύεται ότι υπάρχει πράγματι ένα πρόβλημα.
Όταν έρχεται η ώρα να εφαρμόσει αυτό το πράγμα που ονομάζεται-και πάλι, το κάνω και πάλι.
Είμαι ο μόνος εδώ.
Όταν έρχεται η ώρα για την εφαρμογή αυτό το πράγμα που ονομάζεται hash πίνακα,
θα πάμε να πρέπει να πάρει μια απόφαση.
Πόσο μεγάλη θα πρέπει αυτό το πράγμα να είναι στην πραγματικότητα;
Και όταν θα αρχίσουμε την εισαγωγή αριθμών σε αυτό το hash πίνακα,
πώς θα πάμε να τις αποθηκεύσετε με τέτοιο τρόπο
ότι μπορούμε να τα πάρει πίσω το συντομότερο εμείς τους πήρε μέσα;
Αλλά θα δούμε πριν από καιρό ότι αυτό το θέμα
όταν τα γενέθλια του καθενός είναι στην κατηγορία θα είναι πολύ σχετικός.
Αποδεικνύεται ότι σε αυτό το δωμάτιο, έχουμε μερικές εκατοντάδες άνθρωποι,
έτσι οι πιθανότητες ότι δύο από μας έχουν τα ίδια γενέθλια είναι μάλλον αρκετά υψηλή.
Τι θα συμβεί αν υπήρχαν μόνο 40 από εμάς σε αυτή την αίθουσα;
Ποιες είναι οι πιθανότητες των δύο ανθρώπων που έχουν την ίδια γενέθλια;
[Φοιτητές] Πάνω από το 50%.
Ναι, πάνω από 50%. Στην πραγματικότητα, ακόμη και έφερα ένα γράφημα.
Αποδεικνύεται-και αυτό είναι πραγματικά ακριβώς ένα sneak preview-
εάν υπάρχει μόνο 58 από εμάς σε αυτή την αίθουσα, η πιθανότητα 2 of us
έχουν την ίδια γενέθλια είναι εξαιρετικά υψηλό, σχεδόν το 100%,
και ότι πρόκειται να προκαλέσει ένα σωρό κακό για μας την Τετάρτη.
>> Με αυτόν εν λόγω, ας αναβάλουμε εδώ. Θα σας δούμε την Τετάρτη.
[Χειροκροτήματα]
[CS50.TV]