[Powered by Google Translate] [Ενότητα 6: Λιγότερο Άνετα] [Nate Hardison] [Πανεπιστήμιο του Χάρβαρντ] [Αυτό είναι CS50.] [CS50.TV] Εντάξει. Καλώς ήρθατε στο τμήμα 6. Αυτή την εβδομάδα, θα πάμε να μιλάμε για δομές δεδομένων στο τμήμα, κυρίως επειδή το πρόβλημα αυτής της εβδομάδας που για spellr κάνει ένα σωρό διαφορετικές εξερεύνηση δομή δεδομένων. Υπάρχουν ένα σωρό διαφορετικοί τρόποι που μπορείτε να πάτε με το σύνολο πρόβλημα, και οι περισσότερες δομές δεδομένων που γνωρίζουν, τα πιο δροσερά πράγματα που μπορείτε να κάνετε. 

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

Έτσι, αυτό που έχουμε εδώ, αυτό είναι παρόμοιο με αυτό που παρουσιάστηκε σε διάλεξη, εκτός από διάλεξη που παρουσίασε αυτό με ints, σε αντίθεση με char * s. Αυτό πρόκειται να είναι μια στοίβα που αποθηκεύει ό, τι; Daniel; Τι μπορούμε αποθήκευση σε αυτή τη στοίβα; [Daniel] χορδές; >> Είμαστε αποθήκευση χορδές σε αυτή τη στοίβα, ακριβώς. Το μόνο που πρέπει να έχετε για να δημιουργήσετε μια στοίβα είναι ένας πίνακας μιας συγκεκριμένης ικανότητας, η οποία σε αυτή την περίπτωση, χωρητικότητα θα είναι σε όλα τα καλύμματα, γιατί είναι μια σταθερά. Και στη συνέχεια, εκτός από την συστοιχία, όλα πρέπει να παρακολουθείτε είναι το τρέχον μέγεθος της συστοιχίας. Ένα πράγμα που πρέπει να σημειωθεί εδώ ότι είναι είδος δροσερό είναι ότι είμαστε δημιουργία της στοιβάζονται δομή δεδομένων στην κορυφή του άλλου δομή δεδομένων, η συστοιχία. Υπάρχουν διάφοροι τρόποι για την εφαρμογή στοίβες. Εμείς δεν θα το κάνουμε αρκετά ακόμα, αλλά ελπίζουμε ότι μετά από να κάνει τα συνδεδεμένα-λίστα προβλημάτων, θα δείτε πώς μπορείτε να εφαρμόσετε εύκολα μια στοίβα στην κορυφή ενός συνδεδεμένη λίστα, καθώς και. Αλλά για τώρα, θα τηρήσουμε τις συστοιχίες. Έτσι, και πάλι, το μόνο που χρειαζόμαστε είναι ένας πίνακας και το μόνο που χρειάζεται να παρακολουθείτε το μέγεθος του πίνακα. [Sam] Συγνώμη, γιατί είναι αυτό που σας είπε η στοίβα είναι πάνω από τις χορδές; Για μένα φαίνεται σαν οι χορδές είναι μέσα στη στοίβα. [Hardison] Ναι. Είμαστε δημιουργώντας, είμαστε λαμβάνοντας σειρά μας δομή δεδομένων - αυτό είναι ένα μεγάλο ερώτημα. Έτσι, το ερώτημα είναι γιατί, για τους ανθρώπους που παρακολουθούν αυτό το σε απευθείας σύνδεση, γιατί λέμε ότι η στοίβα είναι πάνω από τις χορδές, γιατί εδώ φαίνεται σαν οι χορδές είναι μέσα στη στοίβα; Ποια είναι εντελώς η περίπτωση. Αυτό που αναφερόταν ήταν ότι έχουμε μια δομή δεδομένων πίνακα. Έχουμε μια σειρά από char * s, αυτή η σειρά των χορδών, και πρόκειται να προσθέσει στο ότι, προκειμένου να δημιουργηθεί η δομή δεδομένων στοιβάζονται. 

Έτσι, μια στοίβα είναι ελαφρώς πιο σύνθετη από μια συστοιχία. Μπορούμε να χρησιμοποιήσουμε μια σειρά για να οικοδομήσουμε μια στοίβα. Έτσι, αυτό είναι όπου μπορούμε να πούμε ότι η στοίβα είναι χτισμένο στην κορυφή ενός πίνακα. Επίσης, όπως είπα και προηγουμένως, μπορούμε να οικοδομήσουμε μια στοίβα στην κορυφή ενός συνδεδεμένη λίστα. Αντί να χρησιμοποιεί μια σειρά για να κρατήσει τα στοιχεία μας, θα μπορούσαμε να χρησιμοποιήσουμε μια συνδεδεμένη λίστα για να κρατήσει τα στοιχεία μας και να οικοδομήσουμε τη στοίβα γύρω από αυτό. Ας δούμε μερικά παραδείγματα, κοιτάζοντας κάποιο κωδικό, για να δούμε τι πραγματικά συμβαίνει εδώ. Στα αριστερά, έχω ρίξει τι struct στοίβα θα μοιάζουν στη μνήμη αν παραγωγικής ικανότητας # ορίζεται να είναι τέσσερα. Έχουμε τέσσερις-στοιχείο char array μας *. Έχουμε χορδές [0], χορδές [1], έγχορδα [2], strings [3], και στη συνέχεια, ότι το τελευταίο διάστημα για ακέραιο μεγέθους μας. Μήπως αυτό έχει νόημα; Εντάξει. Αυτό είναι τι θα συμβεί αν αυτό που κάνω στα δεξιά, η οποία θα είναι κωδικός μου, είναι να δηλώσει μόνο ένα struct, struct μια στοίβα που ονομάζεται s. Αυτό είναι ό, τι έχουμε. Καθορίζει αυτό το αποτύπωμα στη μνήμη. Το πρώτο ερώτημα εδώ είναι ποια είναι τα περιεχόμενα αυτής της struct στοίβα; Αυτή τη στιγμή δεν είναι τίποτα, αλλά δεν είναι απολύτως τίποτα. Είναι αυτό το είδος των σκουπιδιών. Δεν έχουμε καμία ιδέα για το τι είναι σε αυτούς. Όταν δηλώνουμε s στοίβα, είμαστε ρίχνουν απλώς ότι κάτω στην κορυφή της μνήμης. Είναι κάτι σαν δήλωση int i και όχι την αρχικοποίηση. Δεν ξέρεις τι είναι εκεί. Μπορείτε να διαβάσετε τι υπάρχει εκεί μέσα, αλλά μπορεί να μην είναι σούπερ χρήσιμη. Ένα πράγμα που θέλετε να θυμάστε πάντα να κάνετε είναι να προετοιμάσει ό, τι χρειάζεται για να προετοιμαστεί. Σε αυτή την περίπτωση, θα πάμε να προετοιμαστεί το μέγεθος να είναι μηδέν, γιατί αυτό πρόκειται να αποδειχθεί ότι είναι πολύ σημαντικό για εμάς. Θα μπορούσαμε να πάμε μπροστά και να προετοιμάσει όλους τους δείκτες, όλοι οι char * s, να είναι κατανοητή κάποια αξία, κατά πάσα πιθανότητα μηδενική. Αλλά δεν είναι εντελώς απαραίτητο να το κάνουμε αυτό. 

Τώρα, είναι οι δύο κύριες πράξεις στις στοίβες; Ο καθένας θυμάται διάλεξη από ό, τι κάνετε με στοίβες; Ναι; [Στέλλα] Ώθηση και σκάει; Ακριβώς >>. Ώθηση και σκάει είναι οι δύο κύριες πράξεις στις στοίβες. Και τι δεν κάνω ώθηση; >> Θα πρέπει να θέσει κάτι στην κορυφή της στοίβας, και στη συνέχεια σκασίματος απογειώνεται. [Hardison] Ακριβώς. Έτσι πιέζει ωθεί κάτι στην κορυφή της στοίβας. Είναι σαν το προσωπικό τραπεζαρία βάζοντας ένα δίσκο τραπεζαρία κάτω από τον πάγκο. Και σκάει παίρνει ένα δίσκο φαγητού από την στοίβα. Ας δούμε μερικά παραδείγματα του τι συμβαίνει όταν πιέζουμε τα πράγματα στη στοίβα. Αν ήταν να ωθήσει τη συμβολοσειρά «γεια» σε στοίβα μας, αυτό είναι ό, τι διάγραμμα μας θα μοιάζουν τώρα. Δείτε τι συμβαίνει; Προωθήσαμε στο πρώτο στοιχείο του πίνακα χορδές μας και αύξησαν μέτρηση του μεγέθους μας να είναι 1. Έτσι, αν κοιτάξουμε τη διαφορά μεταξύ των δύο διαφάνειες, εδώ ήταν 0, είναι εδώ πριν από το πάτημα. Εδώ είναι μετά το πάτημα. Πριν από την ώθηση, μετά το πάτημα. Και τώρα έχουμε ένα στοιχείο στη στοίβα μας. Είναι η σειρά "γεια", και αυτό είναι όλο. Όλα τα υπόλοιπα στον πίνακα, σε σειρά χορδές μας, εξακολουθεί να είναι σκουπίδια. Δεν έχουν αρχικοποιηθεί. Ας πούμε ότι ωθήσει μια άλλη σειρά στο stack μας. Εμείς πάμε για να ωθήσει "κόσμο" σε αυτό το χρονικό διάστημα. Έτσι, μπορείτε να δείτε "κόσμο" εδώ πηγαίνει στην κορυφή του "γεια", και η μέτρηση μεγέθους πηγαίνει μέχρι 2. Τώρα μπορούμε να πιέσουμε "CS50", και ότι θα πάει και πάλι στην κορυφή. Αν πάμε πίσω, μπορείτε να δείτε πώς είμαστε πιέζει τα πράγματα στην κορυφή της στοίβας. Και τώρα έχουμε την ευκαιρία να σκάσει. Όταν έσκασε κάτι από την στοίβα, τι συνέβη; Ο καθένας δείτε τη διαφορά; Είναι πολύ λεπτή. [Φοιτητικό] Το μέγεθος. >> Ναι, το μέγεθος αλλάξει. 

Τι άλλο θα περίμενε κανείς να αλλάξει; [Φοιτητικό] Οι χορδές, πάρα πολύ. Δικαίωμα >>. Οι χορδές πάρα πολύ. Αποδεικνύεται ότι όταν κάνετε αυτό τον τρόπο, επειδή δεν είμαστε αντιγραφή των στοιχείων σε στοίβα μας, στην πραγματικότητα δεν έχουμε να κάνουμε τίποτα? μπορούμε να χρησιμοποιήσουμε μόνο το μέγεθος να παρακολουθείτε τον αριθμό των πραγμάτων σε σειρά μας έτσι ώστε όταν θα εμφανιστεί και πάλι, και πάλι θα μειώσετε ακριβώς το μέγεθος μας κάτω προς 1. Δεν υπάρχει καμία ανάγκη να πάει στην πραγματικότητα και να αντικαταστήσετε τίποτα. Είδος funky. Αποδεικνύεται ότι συνήθως αφήνουν τα πράγματα απλά και μόνο επειδή είναι λιγότερη δουλειά να κάνουμε. Αν δεν έχουμε να πάμε πίσω και να αντικαταστήσετε κάτι, τότε γιατί το κάνουν; Έτσι, όταν θα σκάσει δύο φορές από την στοίβα, το μόνο που κάνει είναι να ελαττώσει το μέγεθος μια-δυο φορές. Και πάλι, αυτό είναι μόνο επειδή δεν είμαστε αντιγραφή πράγματα σε στοίβα μας. Ναι; Προχωρήστε. [Φοιτητών, ακατάληπτο] >> Και τότε τι θα συμβεί όταν πιέσετε πάλι κάτι; Όταν πατήσετε ξανά κάτι, πού να πάει; Πού να πάει, Βασίλειος; Σε χορδές >> [1]; Δικαίωμα >>. Γιατί δεν πάτε σε σειρές [3]; [Βασίλης] Επειδή ξέχασα ότι υπήρχε κάτι σε χορδές [1] και [2]; [Hardison] Ακριβώς. Stack μας, ουσιαστικά, "ξέχασε" ότι κρατούσε σε οτιδήποτε στις χορδές [1] ή χορδές [2], έτσι ώστε όταν πιέζουμε "woot", βάζει ακριβώς ότι μέσα στο στοιχείο σε χορδές [1]. Υπάρχουν ερωτήματα σχετικά με το πώς αυτό λειτουργεί, σε ένα βασικό επίπεδο; [Sam] Έτσι, αυτό δεν είναι δυναμική με οποιονδήποτε τρόπο, όσον αφορά το ποσό ή από την άποψη του μεγέθους της στοίβας; [Hardison] Ακριβώς. Αυτό είναι - το σημείο ήταν ότι αυτό δεν ήταν ένα δυναμικά αναπτυσόμενη στοίβα. Αυτή είναι μια στοίβα που μπορεί να κρατήσει το πολύ, τέσσερις char * s, το πολύ τέσσερα πράγματα. Αν ήταν να προσπαθήσουμε και να προωθήσει ένα πέμπτο πράγμα, τι νομίζετε ότι θα συμβεί; [Φοιτητές, ακατάληπτο] [Hardison] Ακριβώς. Υπάρχουν μια σειρά από πράγματα που θα μπορούσε να συμβεί. Θα μπορούσε ενδεχομένως να διαχωρίζονται από σφάλμα, ανάλογα με το τι ήμασταν - πώς ακριβώς είχαμε την εφαρμογή του back-end. Θα μπορούσε να αντικαταστήσει. Θα μπορούσε να έχει αυτό το υπερχείλιση του buffer για την οποία μιλήσαμε στην τάξη. Ποιο θα ήταν το πιο προφανές πράγμα που θα μπορούσε να αντικατασταθεί αν προσπαθήσαμε να ωθήσει ένα επιπλέον πράγμα στη στοίβα μας; Έτσι, αναφέρατε μια υπερχείλιση του buffer. Τι θα μπορούσε να είναι το πράγμα που θα μπορούσε να πάρει ή να γράψει πάνω σε stomped αν ξεχειλίζει κατά λάθος, προσπαθώντας να ωθήσει ένα επιπλέον πράγμα; [Daniel, ακατάληπτο] >> Πιθανές. Αλλά αρχικά, τι θα μπορούσε να συμβεί; Τι και αν προσπαθήσαμε να ωθήσει ένα τέταρτο πράγμα; Θα μπορούσε να αντικαταστήσετε το μέγεθος, τουλάχιστον με αυτό το διάγραμμα μνήμης που έχουμε. 

Στο σύνολο προδιαγραφών πρόβλημα, το οποίο είναι αυτό που θα πάμε να υλοποιούν σήμερα, τι θέλουμε να κάνουμε είναι απλά να επιστρέψετε ψευδής. Μέθοδο της προώθησης μας πρόκειται να επιστρέψει μια τιμή boolean, και ότι boolean τιμή θα ισχύει αν η ώθηση πετύχει ψευδείς και αν δεν μπορούμε να πιέζουμε τίποτα περισσότερο, επειδή η στοίβα είναι πλήρης. Ας δούμε λίγο κώδικα τώρα. Εδώ είναι η λειτουργία ώθησης μας. Λειτουργία ώθηση μας για μια στοίβα πρόκειται να λάβει σειρά του να θέσει στη στοίβα. Είναι πρόκειται να επιστρέψει true αν το string με επιτυχία ώθησε επί της στοίβας και ψευδείς διαφορετικά. Οποιεσδήποτε προτάσεις σχετικά με το τι θα μπορούσε να είναι ένα καλό πρώτο πράγμα που πρέπει να κάνουμε εδώ; [Sam] Εάν το μέγεθος ισούται με ικανότητα στη συνέχεια επιστρέφουν λάθος; [Hardison] Bingo. Καλή δουλειά. Εάν το μέγεθος είναι η ικανότητα, θα πάμε να επιστρέψει ψευδείς. Εμείς δεν μπορούμε να βάλουμε κάτι περισσότερο σε στοίβα μας. Διαφορετικά, θέλουμε να βάλουμε κάτι στην κορυφή της στοίβας. Τι είναι η «κορυφή της στοίβας," αρχικά; [Daniel] Μέγεθος 0; Μέγεθος >> 0. Ποια είναι η κορυφή της στοίβας μετά υπάρχει ένα πράγμα στη στοίβα; Missy, το ξέρεις; [Missy] One. Μέγεθος >> είναι ένα, ακριβώς. Θα συνεχίσουμε να προσθέτουμε με το μέγεθος, και κάθε φορά που βάζετε στο νέο στοιχείο στο μέγεθος δείκτη στον πίνακα. Μπορούμε να το κάνουμε με αυτό το είδος του ένα σκάφος της γραμμής, αν αυτό έχει νόημα. Έτσι έχουμε χορδές σειρά μας, θα πάμε να έχουν πρόσβαση στο μέγεθος του δείκτη, και είμαστε ακριβώς πρόκειται να αποθηκεύσετε char * μας εκεί. Παρατηρήστε πως δεν υπάρχει αντιγραφή συμβολοσειράς συμβαίνει εδώ, Δεν δυναμική κατανομή της μνήμης; Και στη συνέχεια, Missy μεγαλώσει αυτό που έχουμε τώρα να κάνουμε, επειδή έχουμε αποθηκεύσει το κορδόνι στην κατάλληλη θέση του πίνακα, και είπε ότι θα έπρεπε να αυξήσετε το μέγεθος από ένα έτσι ώστε να είμαστε έτοιμοι για την επόμενη ώθηση. Έτσι, μπορούμε να το κάνουμε αυτό με s.size + +. Σε αυτό το σημείο, έχουμε ωθούνται σε σειρά μας. Ποιο είναι το τελευταίο πράγμα που πρέπει να κάνουμε; [Φοιτητικό] Επιστροφή αλήθεια. >> Επιστροφή αλήθεια. Γι 'αυτό είναι αρκετά απλή, ένα αρκετά απλό κώδικα. Όχι πάρα πολύ. Μόλις έχετε το κεφάλι σας τυλιγμένο γύρω από το πώς λειτουργεί η στοίβα, αυτό είναι πολύ απλό στην εφαρμογή του. 

Τώρα, το επόμενο τμήμα της αυτό βρεθώ μια συμβολοσειρά από την στοίβα. Πάω να σας δώσω λίγο χρόνο για τα παιδιά να εργαστούν σε αυτό το λίγο. Είναι σχεδόν ουσιαστικά το αντίστροφο του τι έχουμε κάνει εδώ στην ώθηση. Αυτό που έχω κάνει είναι στην πραγματικότητα - ουπς. Έχω ξεκινήσει μια συσκευή μέχρι εδώ, και στη συσκευή, Έχω τράβηξε το πρόβλημα σετ 5 προδιαγραφές. Αν μεγέθυνση εδώ, μπορούμε να δούμε ότι είμαι σε cdn.cs50.net/2012/fall/psets/pset5.pdf. Έχετε εσείς κατεβάσει τον κώδικα που που βρίσκεται, εδώ section6.zip; Εντάξει. Αν δεν το έχετε κάνει αυτό, το κάνουμε αυτό τώρα, πραγματικά γρήγορα. Θα το κάνω το παράθυρο του τερματικού μου. Το έκανα πραγματικά εδώ. Ναι. Ναι, Σαμ; >> Έχω μια ερώτηση σχετικά με το γιατί είπες παρένθεση s.string 's του μεγέθους = str; Τι είναι str; Είναι ορίζεται ότι κάπου πριν, ή - ω, στην char str *; [Hardison] Ναι, ακριβώς. Αυτό ήταν το επιχείρημα. >> Ω, εντάξει. Λυπάμαι. [Hardison] Είμαστε προσδιορίζοντας το string για να ωθήσει μέσα Το άλλο ερώτημα που θα μπορούσε να καταλήξει ότι εμείς δεν μιλάμε για πραγματικά ήταν εδώ πήραμε ως δεδομένο ότι είχαμε αυτήν τη μεταβλητή που ονομάζεται s που ήταν στο πεδίο και προσιτή σε μας. Πήραμε δεδομένο ότι s ήταν αυτό struct στοίβα. Έτσι, κοιτάζοντας πίσω σε αυτό το πάτημα κώδικα, μπορείτε να δείτε ότι κάνουμε τα πράγματα με αυτή τη σειρά που πήρε πέρασε αλλά στη συνέχεια, ξαφνικά, είμαστε πρόσβαση s.size, όπως, πού προέρχονται από s; Στον κώδικα που θα πάμε να δούμε στο αρχείο τμήμα και στη συνέχεια τα πράγματα που θα κάνετε στο πρόβλημά σας θέτει, έχουμε κάνει stack μας struct μια καθολική μεταβλητή έτσι ώστε να μπορούμε να έχουμε πρόσβαση σε αυτό σε όλες τις διαφορετικές λειτουργίες μας χωρίς να χρειάζεται να περάσει το χέρι γύρω από αυτό και να περάσει από την αναφορά, κάνει όλα τέτοιου είδους πράγματα σε αυτό. Είμαστε εξαπάτηση ακριβώς λίγο, αν θέλετε, για να κάνει τα πράγματα πιο ωραίο. Και αυτό είναι κάτι που κάνουμε εδώ γιατί είναι για διασκέδαση, είναι πιο εύκολο. Συχνά, θα δείτε ανθρώπους να το κάνετε αυτό, αν έχετε μια μεγάλη δομή δεδομένων Αυτό είναι που λειτουργούν στο εσωτερικό τους πρόγραμμα. 

Ας πάμε πίσω πάνω στη συσκευή. Μήπως όλοι πάρει με επιτυχία την section6.zip; Όλοι το αποσυμπιέσετε χρησιμοποιώντας unzip section6.zip; Αν πάτε στο τμήμα 6 κατάλογο - Ααα, σε όλη τη χώρα - και θα απαριθμήσει τι είναι εδώ, θα δείτε ότι έχετε τρία διαφορετικά αρχεία. c. Έχεις μια ουρά, ένα SLL, η οποία είναι μεμονωμένα-συνδεδεμένη λίστα, και μια στοίβα. Αν ανοίξει stack.c, μπορείτε να δείτε ότι έχουμε αυτό το struct που ορίζονται για μας, η ακριβής struct που μόλις μίλησε για τις διαφάνειες. Έχουμε παγκόσμια μεταβλητή μας για τη στοίβα, έχουμε λειτουργία ώθησης μας, και στη συνέχεια έχουμε ποπ λειτουργία μας. Θα βάλω τον κωδικό για το σπρώξετε προς τα πίσω επάνω στη διαφάνεια εδώ, αλλά αυτό που θα ήθελα εσείς να κάνετε είναι, με τον καλύτερο την ικανότητά σας, πάνε και να εφαρμόσουν το ποπ λειτουργία. Μόλις έθεσε σε εφαρμογή, μπορείτε να συγκεντρώσετε αυτό με κάνει στοίβα, και στη συνέχεια, εκτελέστε το εκτελέσιμο που προκύπτει στοίβα, και ότι θα τρέξει όλες της παρούσας δοκιμής εδώ κάτω αυτό είναι το κύριο. Και κυρίως φροντίζει πραγματικά κάνει την ώθηση και ποπ κλήσεις και να διασφαλίσουμε ότι όλα θα πάνε όλα δεξιά μέσα. Είναι, επίσης αρχικοποιεί τη στοίβα μέγεθος εδώ έτσι δεν έχετε να ανησυχείτε για την αρχικοποίηση αυτό. Μπορείτε να υποθέσετε ότι είναι ήδη προετοιμαστεί σωστά από τη στιγμή που έχετε πρόσβαση σε αυτό το ποπ λειτουργία. Μήπως αυτό έχει νόημα; Έτσι, εδώ πηγαίνουμε. Υπάρχει η ώθηση κώδικα. Θα σας δώσω παιδιά 5 ή 10 λεπτά. Και αν έχετε οποιαδήποτε απορία στο μεσοδιάστημα ενώ είστε κωδικοποίησης, ρωτήστε τους δυνατά. Έτσι, αν φτάσουμε σε ένα κρίσιμο σημείο, απλά ρωτήστε. Επιτρέψτε μου να ξέρω, ας γνωρίζουν όλοι οι άλλοι. Εργασία με τον γείτονά σας πάρα πολύ. [Daniel] Είμαστε μόλις ποπ εφαρμογή αυτή τη στιγμή; >> Απλά pop. Αν και μπορείτε να αντιγράψετε την εφαρμογή της πίεσης, αν θέλετε έτσι ώστε η δοκιμή θα λειτουργήσει. Επειδή είναι δύσκολο να δοκιμάσουν να μπουν τα πράγματα - ή, είναι δύσκολο να βρεθώ δοκιμάσουν τα πράγματα από μια στοίβα, αν δεν υπάρχει τίποτα στη στοίβα για να αρχίσει με. 

Ποια είναι η ποπ έπρεπε να επιστρέψει; Το στοιχείο από την κορυφή της στοίβας. Είναι υποτίθεται για να πάρει το στοιχείο μακριά από την κορυφή της στοίβας στη συνέχεια και θα ελαττώσει το μέγεθος της στοίβας, και τώρα έχετε χάσει το στοιχείο στην κορυφή. Και τότε θα επιστρέψει το στοιχείο στην κορυφή. [Φοιτητών, ακατάληπτο] [Hardison] Λοιπόν, τι θα συμβεί αν το κάνετε αυτό; [Φοιτητών, ακατάληπτο] Τι συμβαίνει καταλήγει είναι έχετε πρόσβαση πιθανώς είτε Ένα στοιχείο που δεν έχει αρχικοποιηθεί ακόμα, έτσι υπολογισμό σας από όπου το τελευταίο στοιχείο είναι είναι απενεργοποιημένη. Μέχρι εδώ, αν παρατηρήσετε, σε ώθηση, είμαστε πρόσβαση χορδές στο στοιχείο s.size επειδή είναι ένα νέο δείκτη. Είναι η νέα κορυφή της στοίβας. Ότι, ποπ, s.size πρόκειται να είναι το επόμενο διάστημα, ο χώρος που είναι πάνω από όλα τα στοιχεία στη στοίβα σας. Έτσι, το top-πλέον στοιχείο δεν είναι σε s.size, αλλά μάλλον, είναι κάτω από αυτό. 

Το άλλο πράγμα που πρέπει να κάνετε όταν - σε ποπ, είναι που χρειάζεται να μειώσετε το μέγεθος. Αν θυμάστε λίγο πίσω στο διάγραμμα μας εδώ, Πραγματικά, το μόνο πράγμα που είδαμε να συμβαίνει όταν καλέσαμε ποπ ήταν ότι αυτό το μέγεθος μειώθηκε, πρώτη έως 2, στη συνέχεια με 1. Στη συνέχεια, όταν έσπρωξε ένα νέο στοιχείο σε, θα συνεχιστεί στη σωστή θέση. [Βασίλης] Αν η s.size είναι 2, τότε δεν θα το πάει στο στοιχείο 2, και στη συνέχεια θα θέλατε να εμφανιστεί αυτό το στοιχείο μακριά; Έτσι, αν πήγαμε στο - >> Ας ρίξουμε μια ματιά σε αυτό και πάλι. Αν αυτή είναι η στοίβα μας σε αυτό το σημείο και καλούμε ποπ, κατά την οποία ο δείκτης είναι το top-πλέον στοιχείο; [Βασίλης] Στις 2, αλλά πρόκειται να σκάσει 3. Δικαίωμα >>. Έτσι, αυτό είναι όπου το μέγεθος μας είναι 3, αλλά θέλουμε να εμφανιστεί το στοιχείο στο δείκτη 2. Είναι χαρακτηριστικό ότι το είδος της μακριά από αυτό που έχετε με το μηδέν τιμαριθμικής αναπροσαρμογής των συστοιχιών. Έτσι θέλετε να σκάσει το τρίτο στοιχείο, αλλά το τρίτο στοιχείο δεν είναι στο δείκτη 3. Και ο λόγος που δεν έχουμε να κάνουμε αυτό το μείον 1 όταν είμαστε πιέζει οφείλεται στο γεγονός ότι αυτή τη στιγμή, θα παρατηρήσετε ότι το top-πλέον στοιχείο, εάν επρόκειτο να ωθήσει κάτι άλλο στην στοίβα στο σημείο αυτό, θα θέλαμε να την προωθήσουν στο δείκτη 3. Και είναι ακριβώς έτσι συμβαίνει ότι το μέγεθος και οι δείκτες παρατάξει όταν πιέζει. 

Ποιος πήρε μια στοίβα εκτέλεσης εργασίας; Έχεις ένα σωρό εργασίας ένα. Μήπως έχετε ποπ εργάζονται ακόμα; [Δανιήλ] Ναι. Νομίζω πως ναι. Πρόγραμμα >> τρέχει και δεν διαχωρίζονται από ρήγματα, αυτό είναι εκτύπωση; Μήπως να το εκτυπώσετε "επιτυχία" όταν το τρέξετε; Ναι. Κάντε στοίβα, τρέχει, αν εκτυπώνει "επιτυχία" και δεν πηγαίνετε έκρηξη, τότε όλα είναι καλά. Εντάξει. Ας πάει πάνω στη συσκευή πολύ γρήγορα, και θα περπατήσετε μέσα από αυτό. Αν κοιτάξουμε τι συμβαίνει εδώ με pop, Daniel, τι ήταν το πρώτο πράγμα που έκανε; [Daniel] Αν s.size είναι μεγαλύτερη από 0. [Hardison] Εντάξει. Και γιατί το έκανες αυτό; [Daniel] Για να βεβαιωθείτε ότι δεν υπήρχε κάτι μέσα στο σωρό. [Hardison] Δεξιά. Θέλετε να δοκιμάσετε για να βεβαιωθείτε ότι s.size είναι μεγαλύτερη από 0? αλλιώς, ό, τι θέλετε να συμβεί; [Daniel] Επιστροφή null; Επιστροφή >> null, ακριβώς. Έτσι, αν s.size είναι μεγαλύτερη από μηδέν. Τότε τι θα κάνουμε; Τι θα κάνουμε αν η στοίβα δεν είναι κενή; [Στέλλα] Θα μειώσετε το μέγεθος; >> Θα μειώσετε το μέγεθος, εντάξει. Λοιπόν, πώς το έκανες αυτό; >> S.size--. [Hardison] Μεγάλη. Και τότε τι έκανες; [Στέλλα] Και τότε είπα επιστροφή s.string [s.size]. [Hardison] Μεγάλη. Διαφορετικά, θα επιστρέψει null. Ναι, Σαμ; [Sam] Γιατί δεν θα πρέπει να είναι s.size + 1; [Hardison] Plus 1; Ναι >>. >> Το 'πιασα. [Sam] σκέφτηκα γιατί παίρνετε 1 από, τότε θα πάμε για να επιστρέψει δεν αυτό που ζήτησαν. [Hardison] Και αυτό ήταν ακριβώς ό, τι πράγμα μιλάμε με αυτό το όλο θέμα από 0 δείκτες. Έτσι, αν μεγεθύνετε εδώ. Αν κοιτάξουμε αυτόν τον τύπο εδώ, μπορείτε να δείτε ότι όταν σκάσει, είμαστε σκάει το στοιχείο στο δείκτη 2. 

Γι 'αυτό και μειώνουν το μέγεθος μας πρώτα, τότε το μέγεθος μας ταιριάζει δείκτη μας. Αν δεν μειώσετε το μέγεθος πρώτο, τότε έχουμε να κάνουμε μέγεθος -1 και στη συνέχεια μείωση. Μεγάλη. Όλα καλά; Οποιεσδήποτε ερωτήσεις σχετικά με αυτό; Υπάρχουν αρκετοί διαφορετικοί τρόποι για να γράψει αυτό επίσης. Στην πραγματικότητα, μπορούμε να κάνουμε κάτι ακόμη - μπορούμε να κάνουμε μια one-liner. Μπορούμε να κάνουμε μια γραμμή επιστροφής. Γι 'αυτό και μπορεί πραγματικά να μειώσετε πριν επιστρέψει με τον τρόπο αυτό. Έτσι, τη θέση του - πριν από την s.size. Αυτό κάνει η γραμμή πραγματικά πυκνή. Σε περίπτωση που η διαφορά μεταξύ του -. Το μέγεθος και s.size-- είναι ότι αυτό το postfix - καλούν το postfix επειδή η - μετά έρχεται η s.size-- σημαίνει ότι s.size αξιολογείται για τους σκοπούς της εύρεση του δείκτη όπως είναι σήμερα όταν η γραμμή αυτή εκτελείται, και στη συνέχεια αυτό - συμβαίνει μετά η γραμμή εκτελείται. Μετά το στοιχείο στο ευρετήριο s.size είναι προσβάσιμες. Και αυτό δεν είναι ό, τι θέλουμε, γιατί θέλουμε η μείωση να συμβεί πρώτα. Othewise, θα πάμε να την πρόσβαση στο φάσμα, ουσιαστικά, εκτός ορίων. Εμείς πάμε για να έχουν πρόσβαση στο στοιχείο πάνω από αυτό που πραγματικά θέλουμε να έχουν πρόσβαση. Ναι, Σαμ; >> Είναι πιο γρήγορα ή να χρησιμοποιήσετε λιγότερη μνήμη RAM για να κάνει σε μία γραμμή ή όχι; [Hardison] Ειλικρινά, αυτό εξαρτάται πραγματικά. [Sam, ακατάληπτο] >> Ναι, αυτό εξαρτάται. Μπορείτε να κάνετε κόλπα μεταγλωττιστή για να πάρει το μεταγλωττιστή να αναγνωρίσει ότι, συνήθως, φαντάζομαι. 

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

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

Αλλά προς το παρόν, ας προχωρήσουμε και ας μιλήσουμε για ουρές. Κύλιση εδώ. Η ουρά είναι μια στενή αδελφό της στοίβας. Έτσι, στη στοίβα, πράγματα που είχαν τεθεί στην τελευταία ήταν τα πρώτα πράγματα που πρέπει να ανακτηθεί. Έχουμε αυτή την τελευταία in, first out, ή LIFO, παραγγελία. Ενώ στην ουρά, όπως θα περιμένατε από όταν στέκεται στην ουρά, το πρώτο πρόσωπο για να πάρει στη γραμμή, το πρώτο πράγμα που πρέπει να μπει στην ουρά, είναι το πρώτο πράγμα που παίρνει ανακτώνται από την ουρά. Ουρές επίσης συχνά χρησιμοποιείται όταν έχουμε να κάνουμε με γραφήματα, όπως μιλήσαμε για λίγο με στοίβες, και οι ουρές είναι επίσης βολικό για ένα σωρό άλλα πράγματα. Ένα πράγμα που έρχεται συχνά προσπαθεί να διατηρήσει, για παράδειγμα, μια ταξινομημένη λίστα των στοιχείων. Και μπορείτε να το κάνετε αυτό με μια σειρά. Μπορείτε να διατηρήσει μια ταξινομημένη λίστα των πραγμάτων σε μια σειρά, αλλά όπου αυτό είναι δύσκολο παίρνει τότε μπορείτε πάντα να βρείτε το κατάλληλο μέρος για να εισάγετε το επόμενο πράγμα. Έτσι, εάν έχετε μια σειρά από αριθμούς, από 1 έως 10, και στη συνέχεια θέλετε να επεκτείνετε ότι σε όλους τους αριθμούς από 1 έως 100, και παίρνετε αυτούς τους αριθμούς σε τυχαία σειρά και προσπαθεί να κρατήσει τα πάντα ταξινομημένο ως περνάτε, θα καταλήξετε να χρειάζεται να κάνει πολλά από τη μετατόπιση. Με ορισμένους τύπους των ουρών και ορισμένους τύπους των υποκείμενων δομών δεδομένων, μπορείτε πραγματικά να κρατήσει αρκετά απλή. Δεν χρειάζεται να προσθέσω κάτι και στη συνέχεια να ανακατανείμει το όλο θέμα κάθε φορά. Επίσης, δεν έχετε να κάνετε πολλά μετατόπιση των εσωτερικών στοιχείων γύρω. Όταν κοιτάζουμε σε μια ουρά, θα δείτε ότι - επίσης σε queue.c στο τμήμα κώδικα - το struct που σας έχουμε δώσει είναι πραγματικά παρόμοιο με το struct που σας δώσαμε για μια στοίβα. 

Υπάρχει μια εξαίρεση σε αυτό, και ότι μία εξαίρεση είναι ότι έχουμε αυτό που ονομάζεται επιπλέον ακέραιο το κεφάλι, και το κεφάλι είναι εδώ για την παρακολούθηση του επικεφαλής της ουράς, ή το πρώτο στοιχείο στην ουρά. Με μια στοίβα, ήμασταν σε θέση να παρακολουθεί το στοιχείο ότι ήμασταν έτοιμοι για την ανάκτηση, ή την κορυφή της στοίβας, χρησιμοποιώντας μόνο το μέγεθος, ενώ με μια ουρά, είμαστε υποχρεωμένοι να ασχοληθούμε με αντίθετα άκρα. Προσπαθούμε να αναστρέψει τα πράγματα για το τέλος, αλλά στη συνέχεια τα πράγματα επιστρέφουν από το μέτωπο. Τόσο αποτελεσματικά, με το κεφάλι, έχουμε το δείκτη στην αρχή της ουράς, και το μέγεθος μας δίνει το δείκτη του άκρου της ουράς έτσι ώστε να μπορούμε να ανακτήσετε τα πράγματα από το κεφάλι και να προσθέσετε τα πράγματα για την ουρά. Ότι με τη στοίβα, ήμασταν πάντα μόνο ασχολείται με την κορυφή της στοίβας. Δεν είχαμε ποτέ για πρόσβαση στο κάτω μέρος της στοίβας. Προσθέσαμε τα πράγματα μόνο στην κορυφή και πήρε τα πράγματα μακριά από την κορυφή έτσι δεν χρειάζεται το επιπλέον πεδίο στο εσωτερικό struct μας. Μήπως αυτό κάνει αίσθηση γενικά; Εντάξει. Ναι, Charlotte; [Charlotte, ακατάληπτο] [Hardison] Αυτό είναι ένα μεγάλο θέμα, και αυτό ήταν ένα που ήρθε στη διάλεξη. Ίσως το περπάτημα μέσα σε λίγα παραδείγματα επεξηγούν γιατί δεν θέλουμε να χρησιμοποιήσει χορδές [0] ως επικεφαλής της ουράς. 

Φανταστείτε λοιπόν ότι έχουμε ουρά μας, θα πάμε να το ονομάσουμε ουρά. Στην αρχή, όταν έχουμε αρχικοποιείται απλά, όταν έχουμε δηλώσει ακριβώς, δεν έχουμε προετοιμαστεί τίποτα. Είναι όλα σκουπίδια. Έτσι, φυσικά, θέλουμε να είμαστε σίγουροι ότι η προετοιμασία τόσο το μέγεθος και τα πεδία της κεφαλής να είναι μηδέν, κάτι το λογικό. Θα μπορούσαμε, επίσης, να προχωρήσει και να null τα στοιχεία στην ουρά μας. Και για να κάνουν αυτό το κατάλληλο διάγραμμα, παρατηρούμε ότι τώρα ουρά μας μπορεί να κρατήσει μόνο τρία στοιχεία? λαμβάνοντας υπόψη ότι η στοίβα μας θα μπορούσε να κρατήσει τέσσερα, ουρά μας μπορεί να κρατήσει μόνο τρεις. Και αυτό είναι μόνο για να κάνει την τακτοποίηση διάγραμμα. Το πρώτο πράγμα που συμβαίνει εδώ είναι ότι enqueue το string "γεια". Και ακριβώς όπως κάναμε και με τη στοίβα, τίποτα τρομερά διαφορετικό εδώ, ρίχνουμε το string με χορδές σε [0] και αυξήσετε το μέγεθος μας 1. Εμείς enqueue "αντίο", παίρνει θέσει σε. Έτσι, αυτό μοιάζει με μια στοίβα για το μεγαλύτερο μέρος. Ξεκινήσαμε, εδώ νέο στοιχείο, νέο στοιχείο, το μέγεθος συνεχίζει να ανεβαίνει. Τι θα συμβεί σε αυτό το σημείο, όταν θέλουμε να dequeue κάτι; Όταν θέλουμε να dequeue, το οποίο είναι το στοιχείο που θέλουμε να dequeue; [Βασίλης] Χορδές [0]. >> Zero. Ακριβώς δεξιά, ο Βασίλειος. Θέλουμε να απαλλαγούμε από την πρώτη σειρά, αυτή τη φορά, "γεια". Έτσι, ό, τι ήταν το άλλο πράγμα που άλλαξε; Προσέξτε όταν έσκασε κάτι από την στοίβα, αλλάξαμε μόνο το μέγεθος, αλλά εδώ, έχουμε ένα ζευγάρι από τα πράγματα που αλλάζουν. Δεν είναι μόνο η αλλαγή μεγέθους, αλλά οι αλλαγές κεφάλι. Αυτό πηγαίνει πίσω στο σημείο του Σαρλόττα νωρίτερα: γιατί έχουμε αυτό το κεφάλι, καθώς; Έχει νόημα, τώρα Charlotte; Είδος >>. [Hardison] Είδος; Έτσι, ό, τι συνέβη όταν dequeued; Τι έκανε ο επικεφαλής γίνει αυτό τώρα είναι ενδιαφέρον; [Charlotte] Ω, γιατί άλλαξε - εντάξει. Μάλιστα. Επειδή το κεφάλι - όπου το κεφάλι είναι στραμμένο στις αλλαγές σε σχέση με την τοποθεσία. Δεν είναι πλέον πάντα το μηδέν ένα δείκτη. >> Ναι, ακριβώς. Αυτό που συνέβη ήταν αν dequeueing το υψηλό στοιχείο έγινε και δεν είχαμε αυτό το πεδίο κεφάλι γιατί ζητούσαν πάντα αυτό το κορδόνι σε 0 δείκτης ο επικεφαλής της ουράς μας, τότε θα είχαμε να μετατοπίσει το υπόλοιπο της ουράς προς τα κάτω. Εμείς θα πρέπει να στρέψουμε "αντίο" από χορδές από [1] με τις χορδές [0]. Και χορδές [2] κάτω από τις χορδές [1]. Και εμείς θα πρέπει να το κάνετε αυτό για ολόκληρη την λίστα των στοιχείων, η όλη διάταξη των στοιχείων. Και όταν κάνουμε αυτό με μια σειρά, που παίρνει πραγματικά δαπανηρή. Μέχρι εδώ, δεν είναι μια μεγάλη υπόθεση. Έχουμε μόλις τρία στοιχεία σε σειρά μας. Αλλά αν είχαμε μια ουρά από χίλια στοιχεία ή ένα εκατομμύριο στοιχεία, και στη συνέχεια, ξαφνικά, θα αρχίσουμε να κάνουμε ένα μάτσο dequeue καλεί όλους σε έναν βρόχο, τα πράγματα είναι πραγματικά πρόκειται να επιβραδυνθεί, καθώς μετατοπίζει τα πάντα συνεχώς. Ξέρετε, μετατόπιση κατά 1, μετατόπιση κατά 1, μετατόπιση κατά 1, μετατόπιση από 1. Αντ 'αυτού, χρησιμοποιούν αυτό το κεφάλι, θα το ονομάσουμε ένα "δείκτη" ακόμα κι αν δεν είναι πραγματικά ένας δείκτης με την αυστηρή έννοια του όρου? δεν είναι ένα είδος δείκτη. Δεν είναι ένα int * ή char * ή κάτι τέτοιο. Αλλά αυτό είναι που δείχνει ή που δείχνει το κεφάλι του ουρά μας. Ναι; 

[Φοιτητής] Πώς dequeue ξέρει μόνο να σκάσει από ό, τι είναι στο κεφάλι; [Hardison] Πώς dequeue ξέρουν πώς να σκάσει από ό, τι είναι στο κεφάλι; Δικαίωμα >>, ναι. >> Τι ψάχνει σε ό, τι ακριβώς είναι το πεδίο της κεφαλής έχει οριστεί. Έτσι, σε αυτή την πρώτη περίπτωση, αν κοιτάξουμε δεξιά εδώ, κεφάλι μας είναι 0, 0 δείκτη. Δικαίωμα >>. [Hardison] Γι 'αυτό ακριβώς λέει εντάξει, καλά, το στοιχείο στο δείκτη 0, η σειρά "γεια", είναι το στοιχείο στην κεφαλή της ουράς μας. Έτσι θα πάμε να dequeue αυτόν τον τύπο. Και αυτό θα είναι το στοιχείο που παίρνει επιστρέφεται στον καλούντα. Ναι, Saad; >> Έτσι, το κεφάλι θέτει ουσιαστικά το - όπου θα πάμε με τον δείκτη αυτό; Αυτό είναι η αρχή του; Ναι >>. Εντάξει >>. [Hardison] Αυτό είναι να γίνει το νέο ξεκίνημα για την παράταξη μας. Έτσι, όταν dequeue κάτι, το μόνο που έχετε να κάνετε είναι να αποκτήσετε πρόσβαση στο στοιχείο στο δείκτη q.head, και ότι θα είναι το στοιχείο που θέλετε να dequeue. Μπορείτε επίσης να μειώσετε το μέγεθος. Θα δούμε σε λίγο όπου τα πράγματα παίρνουν λίγο δύσκολο με αυτό. Εμείς dequeue, και τώρα, αν Τοποθέτηση στην ουρά και πάλι, πού Τοποθέτηση στην ουρά; Σε περίπτωση που δεν το επόμενο στοιχείο που πάει στην ουρά μας; Πείτε θέλουμε να enqueue το string "CS". Σε ποια δείκτης θα πάει; [Φοιτητές] Χορδές [2]. Δύο >>. Γιατί 2 και όχι 0; [Βασίλης] Επειδή τώρα το κεφάλι είναι 1, έτσι ώστε να είναι σαν την αρχή της λίστας; [Hardison] Δεξιά. Και τι σημαίνει το τέλος της λίστας; Αυτό ήταν που χρησιμοποιείτε για να δηλώσει το τέλος της ουράς μας; Το κεφάλι είναι ο επικεφαλής της ουράς μας, η αρχή της ουράς μας. Ποιο είναι το τέλος της ουράς μας; [Φοιτητές] Μέγεθος. Μέγεθος >>, ακριβώς. Έτσι, τα νέα στοιχεία μας πάνε σε σε μέγεθος, και τα στοιχεία που παίρνουμε από βγει στο κεφάλι. Όταν enqueue το επόμενο στοιχείο, είμαστε σε θέση να σε μέγεθος. [Φοιτητικό] Πριν βάλετε σε ότι και αν, διαστάσεων ήταν το 1, έτσι δεν είναι; [Hardison] Δεξιά. Έτσι, δεν είναι αρκετά σε μέγεθος. + Μέγεθος, όχι +1, αλλά το κεφάλι +. Επειδή τα πάντα μετατοπιστεί από το ποσό κεφάλι. Έτσι, εδώ, τώρα έχουμε μια ουρά του μεγέθους 1 που ξεκινά σε δείκτη 1. Η ουρά είναι δείκτης 2. Ναι; 

[Φοιτητικό] Τι συμβαίνει όταν dequeue χορδές [0], και οι χορδές »στη μνήμη υποδοχές απλά να αδειάσει, ουσιαστικά, ή απλά να ξεχάσει; [Hardison] Ναι. Με αυτή την έννοια, είμαστε απλά ξέχασέ το. Αν είχαμε την αποθήκευση αντιγράφων για τους - πολλές δομές δεδομένων θα αποθηκεύσει συχνά δικά τους αντίγραφα των στοιχείων έτσι ώστε το πρόσωπο που διαχειρίζεται τη δομή των δεδομένων δεν χρειάζεται να ανησυχείτε σχετικά με το πού όλοι αυτοί οι δείκτες πρόκειται. Η δομή δεδομένων που κρατά για να τα πάντα, για να έχει όλα τα αντίγραφα, για να βεβαιωθείτε ότι τα πάντα επιμένει κατάλληλα. Ωστόσο, στην περίπτωση αυτή, αυτές οι δομές δεδομένων μόνο, για λόγους απλότητας, δεν κάνουν τίποτα αντίγραφα του ότι είμαστε αποθήκευση σε αυτά. [Φοιτητικό] Έτσι είναι αυτή η συνεχής σειρά από -; Ναι >>. Αν κοιτάξουμε πίσω σε αυτό που ήταν ο ορισμός της δομής αυτής, είναι. Είναι απλά μια τυπική σειρά, όπως έχετε δει, μια σειρά από char * s. Μήπως ότι -; >> Ναι, απλά αναρωτιόμουν αν τελικά θα ξεμείνει από μνήμη, ως ένα βαθμό, αν έχετε όλα αυτά τα κενά σημεία σε σειρά σας; [Hardison] Ναι, αυτό είναι ένα καλό σημείο. 

Αν κοιτάξουμε τι έχει συμβεί τώρα σε αυτό το σημείο, έχουμε γεμίσει ουρά μας, μοιάζει. Αλλά δεν έχουμε πραγματικά γεμίσει ουρά μας επειδή έχουμε μια ουρά που είναι το μέγεθος 2, αλλά αρχίζει στο δείκτη 1, επειδή αυτό είναι όπου ο δείκτης είναι το κεφάλι μας. Όπως είπατε, ότι το στοιχείο στο χορδές [0], στο δείκτη 0, δεν είναι πραγματικά εκεί. Δεν είναι στην ουρά μας πια. Εμείς απλά δεν μπαίνουν στον κόπο να πάτε και να αντικαταστήσετε όταν το dequeued. Έτσι ακόμα κι αν αυτό μοιάζει έχουμε ξεμείνει από μνήμη, έχουμε πραγματικά δεν έχουν. Αυτό το σημείο είναι διαθέσιμα για μας να χρησιμοποιήσει. Η κατάλληλη συμπεριφορά, αν ήταν να προσπαθήσουμε και το πρώτο dequeue κάτι όπως το "αντίο", που θα σκάσει αντίο μακριά. Τώρα ουρά μας ξεκινά στο δείκτη 2 και έχει μέγεθος 1. Και τώρα αν προσπαθήσουμε και πάλι enqueue κάτι, ας πούμε 50, 50 θα πρέπει να πάνε σε αυτό το σημείο στο δείκτη 0 γιατί είναι ακόμα διαθέσιμες για μας. Ναι, Saad; [Saad] Μήπως αυτό γίνεται αυτόματα; [Hardison] Αυτό δεν συμβαίνει σχεδόν αυτόματα. Θα πρέπει να κάνετε τα μαθηματικά να την κάνουμε να λειτουργήσει, αλλά ουσιαστικά αυτό που έχουμε κάνει είναι ότι έχουμε μόλις τυλιγμένο γύρω. [Saad] Και είναι εντάξει, αν αυτό έχει μια τρύπα στη μέση του; [Hardison] είναι αν μπορούμε να κάνουμε τα μαθηματικά λειτουργούν σωστά. 

Και αποδεικνύεται ότι αυτό δεν είναι πραγματικά ότι σκληρά για να κάνει με το χειριστή mod. Έτσι ακριβώς όπως κάναμε με Καίσαρα και το υλικό κρυπτογράφησης, χρησιμοποιώντας mod, μπορούμε να πάρουμε τα πράγματα για να τυλίξει γύρω και συνεχίζω γύρω και γύρω γύρω και με την ουρά μας, κρατώντας ότι ο δείκτης κινείται γύρω από το κεφάλι. Παρατηρήστε ότι το μέγεθος είναι πάντα σέβεται τον αριθμό των πραγματικά στοιχεία κατά την ουρά. Και είναι ακριβώς ο δείκτης της κεφαλής που κρατά το ποδήλατο μέσα. Αν κοιτάξουμε τι συνέβη εδώ, αν πάμε πίσω στην αρχή, και μπορείτε απλά να παρακολουθήσετε τι συμβαίνει στο κεφάλι Τοποθέτηση στην ουρά όταν κάτι, δεν έγινε τίποτα στο κεφάλι. Όταν enqueued κάτι άλλο, δεν έγινε τίποτα στο κεφάλι. Σύντομα όπως dequeued κάτι, το κεφάλι ανεβαίνει κατά ένα. Εμείς enqueued κάτι, δεν συμβαίνει τίποτα στο κεφάλι. Όταν dequeue κάτι, ξαφνικά το κεφάλι παίρνει αυξάνεται. Όταν enqueue κάτι, δεν συμβαίνει τίποτα στο κεφάλι. 

Τι θα συμβεί σε αυτό το σημείο, αν επρόκειτο να dequeue κάτι πάλι; Οποιεσδήποτε σκέψεις; Τι θα συμβεί στο κεφάλι; Τι πρέπει να συμβεί για να το κεφάλι αν ήταν να dequeue κάτι άλλο; Το κεφάλι είναι τώρα στο δείκτη 2, πράγμα που σημαίνει ότι η κεφαλή της ουράς είναι χορδές [2]. [Φοιτητικό] η οποία επιστρέφει 0; >> Θα πρέπει να επανέλθει στο 0. Θα πρέπει να τυλίξετε γύρω από πίσω, ακριβώς. Μέχρι τώρα, κάθε φορά που καλείται dequeue, έχουμε την προσθήκη ενός στο κεφάλι, προσθέστε ένα στο κεφάλι, προσθέστε ένα στο κεφάλι, προσθέστε ένα στο κεφάλι. Μόλις ότι ο δείκτης παίρνει κεφάλι στο τελευταίο δείκτη σε σειρά μας, τότε θα πρέπει να το τυλίξετε γύρω από πίσω στην αρχή, πηγαίνετε πίσω στο 0. [Charlotte] Τι καθορίζει την ικανότητα της ουράς σε μια στοίβα; [Hardison] Σε αυτήν την περίπτωση, έχουμε μόλις χρησιμοποιώντας ένα # ορίζεται σταθερή. Εντάξει >>. [Hardison] Στην πραγματική. Αρχείο c, μπορείτε να πάτε σε απορρίματα και με το λίγο και κάνει τόσο μεγάλη ή τόσο λίγα όπως θέλετε. [Charlotte] Έτσι, όταν θέλετε να κάνετε αυτό μια ουρά, πώς κάνετε τον υπολογιστή γνωρίζουν πόσο μεγάλο θέλετε η στοίβα να είναι; [Hardison] Αυτό είναι ένα μεγάλο ερώτημα. Υπάρχουν δύο τρόποι. Ο ένας είναι να καθορίσει ακριβώς μπροστά και λένε ότι αυτό πρόκειται να είναι μια ουρά που έχει 4 στοιχεία ή 50 ή 10.000 στοιχεία. Ο άλλος τρόπος είναι να κάνουμε ό, τι οι λαοί έκδοση χάκερ κάνουν και να δημιουργήσει λειτουργίες να έχουν ουρά σας αναπτύσσεται δυναμικά, όπως να πάρει περισσότερα πράγματα μέσα προστίθενται 

[Charlotte] Έτσι, για να πάει με την πρώτη επιλογή, ποια σύνταξη χρησιμοποιείτε να πει το πρόγραμμα ποιο είναι το μέγεθος της ουράς; [Hardison] Αχ. Ας βγούμε από αυτό. Είμαι ακόμα σε stack.c εδώ, οπότε είμαι απλώς πρόκειται να μετακινηθείτε προς τα πάνω στην κορυφή εδώ. Μπορείτε να δείτε αυτό το δικαίωμα εδώ; Αυτό είναι το # define χωρητικότητα 10. Και αυτό είναι σχεδόν η ίδια ακριβώς σύνταξη που έχουμε για την ουρά. Εκτός ουρά, έχουμε αυτό το επιπλέον πεδίο struct εδώ. [Charlotte] Ω, νόμιζα ότι η ικανότητα σημαίνει την ικανότητα για τη σειρά. [Hardison] Αχ. >> Αυτό είναι το μέγιστο μήκος της λέξης. >> Το 'πιασα. Ναι. Η χωρητικότητα εδώ - αυτό είναι ένα μεγάλο σημείο. Και αυτό είναι κάτι που είναι δύσκολο διότι αυτό που έχουμε δηλώσει εδώ είναι μια σειρά από char * s. Μια σειρά από δείκτες. Αυτή είναι μια σειρά από χαρακτήρες. Αυτό είναι ίσως ό, τι έχετε δει όταν έχετε δηλώνοντας προσκρουστήρες σας για αυτό το αρχείο I / O, όταν έχετε δημιουργήσει χορδές χέρι στη στοίβα. Ωστόσο, αυτό που έχουμε εδώ είναι μια σειρά από char * s. Γι 'αυτό είναι μια σειρά από δείκτες. Στην πραγματικότητα, αν μεγεθύνετε και να κοιτάξουμε τι συμβαίνει εδώ στην παρουσίαση, θα δείτε ότι τα πραγματικά στοιχεία, τα στοιχεία του χαρακτήρα δεν αποθηκεύεται μέσα στη συστοιχία ίδια. Τι είναι αποθηκευμένο μέσα στον πίνακα μας εδώ είναι δείκτες για τα δεδομένα χαρακτήρων. Εντάξει. Έτσι, έχουμε δει πώς το μέγεθος της ουράς είναι ακριβώς όπως με τη στοίβα, το μέγεθος τηρεί πάντα τον αριθμό των στοιχείων επί του παρόντος στην ουρά. Μετά την υποβολή της 2 enqueues, το μέγεθος είναι 2. Μετά από να κάνει ένα dequeue το μέγεθος είναι τώρα 1. Μετά από να κάνει ένα άλλο enqueue το μέγεθος είναι πίσω μέχρι και 2. Έτσι, το μέγεθος σίγουρα σέβεται τον αριθμό των στοιχείων στην ουρά, και στη συνέχεια το κεφάλι κρατά μόνο το ποδήλατο. Στη συνέχεια, από το 0-1-2, 0-1-2, 0-1-2. Και κάθε φορά που λέμε dequeue, ο δείκτης παίρνει κεφάλι αυξάνεται στο επόμενο δείκτη. Και αν το κεφάλι είναι για να πάει πάνω, αυτό γυρίζει πίσω γύρω στο 0. Έτσι, με αυτό, μπορούμε να γράψουμε την dequeue λειτουργία. Και θα πάμε να εγκαταλείψουν τη λειτουργία enqueue για σας παιδιά να εφαρμόσει αντ 'αυτού. 

Όταν έχουμε ένα στοιχείο dequeue έξω από ουρά μας, ποιο ήταν το πρώτο πράγμα που έκανε ο Daniel όταν ξεκινήσαμε να γράφουμε το αναδυόμενο λειτουργία για σωρούς; Επιτρέψτε μου να ακούσω από κάποιον που δεν έχει μιλήσει ακόμη. Ας δούμε, Saad, θυμάστε τι έκανε ο Daniel ως το πρώτο πράγμα όταν έγραψε ποπ; [Saad] Υπήρχε, ήταν - >> Έχει δοκιμαστεί για κάτι. [Saad] Αν το μέγεθος είναι μεγαλύτερο από 0. Ακριβώς >>. Και τι ήταν αυτό για τον έλεγχο; [Saad] Αυτό ήταν δοκιμή για να δούμε αν υπάρχει κάτι στο εσωτερικό του πίνακα. [Hardison] Ναι. Ακριβώς. Έτσι δεν μπορείτε να ποπ τίποτα έξω από τη στοίβα και αν είναι άδειο. Ομοίως, δεν μπορείτε να dequeue τίποτα από μια ουρά αν είναι άδειο. Ποιο είναι το πρώτο πράγμα που πρέπει να κάνουμε σε λειτουργία dequeue μας εδώ, νομίζεις; [Saad] Αν το μέγεθος είναι μεγαλύτερο από 0; Ναι >>. Σε αυτή την περίπτωση, έχω δοκιμαστεί στην πραγματικότητα απλώς για να δούμε αν είναι 0. Αν είναι 0, μπορούμε να επιστρέψουμε μηδενική. Αλλά ακριβώς ίδια λογική. Και ας συνεχίσουμε με αυτό. Εάν το μέγεθος δεν είναι 0, όπου είναι το στοιχείο που θέλουμε να dequeue; [Saad] Στο κεφάλι; Ακριβώς >>. Μπορούμε απλά τραβήξτε προς τα έξω το πρώτο στοιχείο στην ουρά μας από την πρόσβαση του στοιχείου στο κεφάλι. Τίποτα τρελό. Μετά από αυτό, τι πρέπει να κάνουμε; Τι πρέπει να γίνει; Ποιο ήταν το άλλο πράγμα που μιλήσαμε για το dequeue; Δύο πράγματα πρέπει να συμβεί, επειδή ουρά μας έχει αλλάξει. [Δανιήλ] Μειώστε το μέγεθος. >> Πρέπει να μειώσουμε το μέγεθος, και να αυξήσει το κεφάλι; Ακριβώς. Για να αυξήσετε το κεφάλι, δεν μπορούμε απλά να αυξήσει τυφλά το κεφάλι, θυμάται. Εμείς απλά δεν μπορούμε να κάνουμε queue.head + +. Πρέπει να περιλαμβάνουν επίσης αυτό το mod από την ικανότητα. Και γιατί mod από την ικανότητα, Στέλλα; [Στέλλα] Γιατί πρέπει να τυλίξετε γύρω. Ακριβώς >>. Εμείς mod από την ικανότητα, διότι πρέπει να γυρίσει πίσω γύρω στο 0. Μέχρι τώρα, σε αυτό το σημείο, μπορούμε να κάνουμε ό, τι είπε ο Ντάνιελ. Μπορούμε να ελαττώσει το μέγεθος. Και τότε μπορούμε να επιστρέψει μόνο το στοιχείο που ήταν στην κορυφή της ουράς. Φαίνεται ότι το είδος του οζώδης από την πρώτη. Μπορεί να έχετε μια ερώτηση. Συγνώμη; 

[Sam] Γιατί η πρώτη στην κορυφή της ουράς; Πού πηγαίνουν ότι; [Hardison] Προέρχεται από την τέταρτη γραμμή από τον πυθμένα. Αφού ελέγξετε για να βεβαιωθείτε ότι η ουρά μας δεν είναι άδειο, έχουμε βγάλει char * Αρχικά, τραβήξτε προς τα έξω το στοιχείο που κάθεται στο κεφάλι του δείκτη από σειρά μας, του χορδές σειρά μας, >> και ότι η πρώτη κλήση; [Hardison] Και εμείς ονομάζουμε πρώτα. Ναι. Ακριβώς για να δώσει συνέχεια σε αυτό, γιατί νομίζετε ότι θα έπρεπε να το κάνουμε αυτό; [Sam] Κάθε πρώτο επιστρέφει μόλις q.strings [q.head]; Ναι >>. >> Γιατί κάνουμε αυτή την αλλαγή της q.head με τη λειτουργία mod, και δεν υπάρχει τρόπος να το κάνουμε αυτό μέσα σε αγωγό επιστροφής επίσης. [Hardison] Ακριβώς. Είστε σωστοί. Sam είναι απόλυτα σωστοί. Ο λόγος για τον οποίο έπρεπε να βγάλει το πρώτο στοιχείο στην ουρά μας και να το αποθηκεύσετε σε μια μεταβλητή οφείλεται στο γεγονός ότι αυτή τη γραμμή, όπου είχαμε μόλις q.head, υπάρχει ο χειριστής mod εκεί δεν είναι κάτι που μπορούμε να κάνουμε και έχουν τεθεί σε ισχύ στο κεφάλι χωρίς - σε μία γραμμή. Γι 'αυτό και πραγματικά πρέπει να βγάλει το πρώτο στοιχείο, και στη συνέχεια ρυθμίστε το κεφάλι, προσαρμόσετε το μέγεθος, και στη συνέχεια να επιστρέψετε το στοιχείο που έβγαλε. Και αυτό είναι κάτι που θα δούμε αργότερα καταλήξουμε με συνδεδεμένες λίστες, καθώς παίζουν μαζί τους. Συχνά, όταν είστε απελευθέρωση ή τη διάθεση των συνδεδεμένες λίστες θα πρέπει να θυμάστε το επόμενο στοιχείο, το επόμενο δείκτη του συνδεδεμένη λίστα πριν από τη διάθεση της τρέχουσας. Διότι διαφορετικά θα πετάξετε τις πληροφορίες για το τι έχει απομείνει από τη λίστα. Τώρα, αν πας στη συσκευή σας, θα ανοίξει queue.c--x από αυτό. Έτσι, αν ανοίξει queue.c, επιτρέψτε μου μεγέθυνση εδώ, θα δείτε ότι έχετε μια παρόμοια εμφάνιση αρχείο. Παρόμοια εμφάνιση αρχείο με ό, τι είχαμε νωρίτερα με stack.c. Έχουμε struct μας για την ουρά που ορίζεται ακριβώς όπως είδαμε στις διαφάνειες. 

Έχουμε enqueue λειτουργία μας, η οποία είναι για σας να το κάνετε. Και έχουμε την dequeue λειτουργία εδώ. Η dequeue λειτουργία του αρχείου είναι ανεφάρμοστοι, αλλά εγώ θα το θέσω back up για το PowerPoint, έτσι ώστε να μπορείτε να πληκτρολογήσετε, αν θέλετε. Έτσι, για τα επόμενα 5 λεπτά ή έτσι, εσείς εργασίες για enqueue που είναι σχεδόν ακριβώς το αντίθετο από dequeue. Δεν χρειάζεται να ρυθμίσετε το κεφάλι όταν enqueueing, αλλά τι έχετε να ρυθμίσετε; Μέγεθος. Έτσι, όταν enqueue, το κεφάλι παραμένει ανέπαφο, το μέγεθος παίρνει αλλάξει. Αλλά χρειάζεται να είναι κανείς λίγο - θα πρέπει να παίζουν με αυτό το mod για να καταλάβω ακριβώς τι δείκτη το νέο στοιχείο θα πρέπει να εισαχθεί σε. Γι 'αυτό και θα δώσει εσείς λίγο, βάλτε dequeue back up στη διαφάνεια, όπως και εσείς έχετε ερωτήσεις, τους φωνάζουν έξω ώστε να μπορούμε να όλοι μιλούν γι 'αυτούς σαν μια ομάδα. Επίσης, με το μέγεθος σας μην τα - όταν ρυθμίζετε το μέγεθος, μπορείτε πάντα απλά - έχετε να mod το μέγεθος ποτέ; [Daniel] Όχι >> Δεν χρειάζεται να mod το μέγεθος, δεξιά. Επειδή το μέγεθος θα είναι πάντα, αν Μπορείτε πλέον - υποθέτοντας είστε διαχειρίζονται τα πράγματα σωστά, το μέγεθος θα είναι πάντα μεταξύ 0 και 3. Σε περίπτωση που έχετε να mod όταν κάνετε enqueue; [Φοιτητών] Μόνο για το κεφάλι. >> Μόνο για το κεφάλι, ακριβώς. Και γιατί θα πρέπει να mod καθόλου σε enqueue; Όταν είναι μια κατάσταση κατά την οποία θα έπρεπε να mod; [Φοιτητικό] Αν έχετε πράγματα σε χώρους, όπως σε χώρους 1 και 2, και τότε θα έπρεπε να προσθέσω κάτι σε 0. [Hardison] Ναι, ακριβώς. Έτσι, αν ο δείκτης κεφάλι σας είναι στο τέλος-τέλος, ή αν το μέγεθος σας συν το κεφάλι σας είναι μεγαλύτερο, ή μάλλον, πρόκειται να τυλίξει γύρω από την ουρά. 

Έτσι, σε αυτήν την κατάσταση που έχουμε εδώ στη διαφάνεια αυτή τη στιγμή, αν θέλω να enqueue κάτι αυτή τη στιγμή, θέλουμε να enqueue κάτι στο δείκτη 0. Έτσι, αν κοιτάξετε, όπου το 50 πηγαίνει, και καλώ enqueue 50, πηγαίνει εκεί κάτω στο κάτω μέρος. Πηγαίνει στο δείκτη 0. Αντικαθιστά το «γεια» που είχε ήδη dequeued. [Δανιήλ] Μην παίρνετε τη φροντίδα του ότι σε dequeue ήδη; Γιατί δεν το κάνει τίποτα με το κεφάλι σε enqueue; [Hardison] Ω, έτσι δεν είστε τροποποιώντας το κεφάλι, συγνώμη. Αλλά θα πρέπει να χρησιμοποιήσετε τον τελεστή mod όταν έχετε πρόσβαση το στοιχείο που θέλετε να enqueue όταν έχετε πρόσβαση το επόμενο στοιχείο στην ουρά σας. [Βασίλης] Εγώ δεν το κάνουμε αυτό, και πήρα "επιτυχία" εκεί. [Daniel] Ω, καταλαβαίνω τι λέτε. [Hardison] Έτσι didn't - απλά έκανε στο q.size; [Βασίλης] Ναι. Έχω αλλάξει μόνο πλευρές, δεν έκανα τίποτα με το κεφάλι. [Hardison] Μπορείτε στην πραγματικότητα, δεν πρέπει να επαναφέρετε το κεφάλι να είναι οτιδήποτε, αλλά όταν δείκτη μέσα στον πίνακα χορδές, που πραγματικά πρέπει να πάμε μπροστά και να υπολογίσει όπου το επόμενο στοιχείο είναι, βέργα επειδή η στοίβα, το επόμενο στοιχείο στη στοίβα σας ήταν πάντα κατά τον δείκτη που αντιστοιχεί στο μέγεθος. Αν κοιτάξουμε πίσω επάνω σε λειτουργία πάτημα stack μας, θα μπορούσαμε πάντα να τραβώ σε νέο στοιχείο μας το δικαίωμα στο μέγεθος του δείκτη. Ότι, με την ουρά, δεν μπορούμε να το κάνουμε αυτό γιατί αν είμαστε σε αυτή την κατάσταση, αν enqueued 50 νέα σειρά μας θα πάει δεξιά σε χορδές [1] το οποίο δεν θέλουμε να κάνουμε. Θέλουμε να έχουμε τη νέα σειρά πηγαίνουν στο δείκτη 0. 

Μήπως κάποιος - ναι; [Φοιτητικό] Έχω μια ερώτηση, αλλά δεν είναι πραγματικά σχετίζονται. Τι σημαίνει όταν κάποιος ζητά κάτι σαν προβλ δείκτη; Τι είναι αυτό το όνομα για σύντομο; Ξέρω ότι είναι απλά ένα όνομα. [Hardison] Pred δείκτη; Ας δούμε. Σε ποιο πλαίσιο; [Φοιτητικό] Ήταν για το ένθετο. Μπορώ να σας ρωτήσω αργότερα, αν θέλετε επειδή δεν είναι πραγματικά σχετίζονται, αλλά εγώ απλά - [Hardison] Από κωδικός ένθετο του Δαβίδ από την διάλεξη; Μπορούμε να τραβήξει ότι μέχρι και να μιλήσουμε γι 'αυτό. Θα μιλήσουμε για το επόμενο, όταν έχουμε την ευκαιρία να συνδεδεμένες λίστες. 

Ας πολύ γρήγορα να δούμε τι η λειτουργία enqueue μοιάζει. Ποιο ήταν το πρώτο πράγμα που οι άνθρωποι προσπάθησαν να κάνουν σε enqueue γραμμή σας; Σε αυτήν την ουρά; Παρόμοιο με αυτό που έκανες για στοίβα πιέζει. Τι έκανες, Στέλλα; [Στέλλα, ακατάληπτο] [Hardison] Ακριβώς. Αν (q.size == ΙΚΑΝΟΤΗΤΑ) - Πρέπει να βάλει σιδεράκια μου στο σωστό μέρος - επιστροφή ψευδείς. Ζουμ σε λίγο. Εντάξει. Τώρα ποιο είναι το επόμενο πράγμα που έπρεπε να κάνουμε; Ακριβώς όπως και με τη στοίβα, και εισάγεται στο σωστό μέρος. Και ναι, ποιο ήταν το σωστό μέρος για να τοποθετήσετε αυτό; Με τη στοίβα ήταν το μέγεθος του δείκτη, με αυτό είναι ότι δεν είναι αρκετά. [Daniel] Έχω q.head--ή - q.strings >>; Ναι >>. q.strings [+ q.head q.size mod ΧΩΡΗΤΙΚΟΤΗΤΑ]; [Hardison] Εμείς μάλλον θα θέλετε να βάλετε παρενθέσεις γύρω από αυτό έτσι ώστε να παίρνουμε την κατάλληλη προτεραιότητα και έτσι αυτό είναι cleart σε όλους. Και που να ισούται; >> Για να str; >> Για να str. Μεγάλη. Και τώρα τι είναι το τελευταίο πράγμα που πρέπει να κάνουμε; Ακριβώς όπως κάναμε στη στοίβα. >> Αύξησε το μέγεθος; >> Αύξησε το μέγεθος. Boom. Και στη συνέχεια, από την μίζα κώδικα μόλις επέστρεψε ψευδείς από προεπιλογή, θέλουμε να αλλάξουμε αυτό να ισχύει και αν όλα πάνε μέσα και όλα πάνε καλά. Εντάξει. Αυτό είναι πολλές πληροφορίες για το τμήμα. Δεν είμαστε αρκετά πάνω. Θέλουμε να μιλήσουμε πραγματικά γρήγορα για μεμονωμένα-συνδεδεμένες λίστες. Θα βάλω αυτό επάνω ώστε να μπορέσουμε να επιστρέψουμε σε αυτό αργότερα. Αλλά ας επιστρέψουμε στην παρουσίασή μας για μερικές περισσότερες διαφάνειες. Έτσι enqueue είναι TODO, τώρα έχουμε κάνει. 

Τώρα, ας ρίξουμε μια ματιά σε μεμονωμένα-συνδεδεμένες λίστες. Μιλήσαμε για αυτά λίγο περισσότερο σε διάλεξη. Πόσοι από σας είδε το demo όπου είχαμε ανθρώπους αδέξια δείχνουν ο ένας στον άλλο και εκμετάλλευση αριθμούς; >> Ήμουν σε αυτό. >> Τι νομίζετε εσείς; Μήπως ότι, ελπίζουμε αυτά τα απομυθοποιήσει λίγο; Με μια λίστα, αποδεικνύεται ότι έχουμε να κάνουμε με αυτόν τον τύπο ότι θα πάμε για να καλέσετε έναν κόμβο. Ότι, με την ουρά και η στοίβα είχαμε structs ότι είχαμε καλέσει ουρά σε στοίβα, είχαμε αυτά τα νέα είδη ουρά σε στοίβα, εδώ μια λίστα είναι πραγματικά ακριβώς αποτελείται από μια δέσμη των κόμβων. Με τον ίδιο τρόπο ότι οι χορδές είναι απλώς ένα μάτσο χαρακτήρες όλα παρατάσσονται το ένα δίπλα στο άλλο. Μια συνδεδεμένη λίστα είναι απλά ένας κόμβος και ένα άλλο κόμβο και ένα άλλο κόμβο και ένα άλλο κόμβο. Και παρά τη συντριβή όλων των κόμβων μαζί και την αποθήκευση τους συνεχόμενα όλα δίπλα στο άλλο στη μνήμη, με αυτό το επόμενο δείκτη μας επιτρέπει να αποθηκεύετε τους κόμβους όπου, τυχαία. Και στη συνέχεια το είδος του σύρματος όλα μαζί με το σημείο από το ένα στο επόμενο. 

Και αυτό ήταν το μεγάλο πλεονέκτημα ότι αυτό είχε πάνω από μια σειρά; Πάνω από όλα αποθήκευση συνεχόμενα μόλις κολλήσει ένα δίπλα στο άλλο; Θυμάσαι; Ναι; >> Δυναμική κατανομή μνήμης; >> Δυναμική κατανομή μνήμης σε ποια έννοια; [Φοιτητικό] Σε αυτό μπορείτε να κρατήσετε το καθιστά μεγαλύτερο και δεν χρειάζεται να μετακινήσετε ολόκληρη την σειρά σας; [Hardison] Ακριβώς. Έτσι, με μια σειρά, όταν θέλετε να βάλετε ένα νέο στοιχείο στη μέση του, θα πρέπει να στραφούν τα πάντα για να κάνει χώρο. Και όπως μιλήσαμε με την ουρά, αυτός είναι ο λόγος που διατηρούν το δείκτη κεφάλι, έτσι ώστε δεν είμαστε μετατοπίζεται συνεχώς πράγματα. Επειδή αυτό παίρνει ακριβά αν έχετε μια μεγάλη σειρά και κάνεις συνεχώς αυτές τις τυχαίες παρεμβολές. Ότι, με μια λίστα, το μόνο που έχετε να κάνετε είναι να ρίξει σε ένα νέο κόμβο, προσαρμόσει τους δείκτες, και είστε έτοιμοι. Τι χάλια γι 'αυτό; Εκτός από το γεγονός ότι δεν είναι τόσο εύκολο να εργαστεί με ως πίνακα; Ναι; [Daniel] Λοιπόν, υποθέτω ότι είναι πολύ πιο δύσκολο να αποκτήσει πρόσβαση σε ένα συγκεκριμένο στοιχείο στη συνδεδεμένη λίστα; [Hardison] Δεν μπορείτε απλά να μεταβείτε σε ένα αυθαίρετο στοιχείο στη μέση συνδεδεμένη λίστα σας. Πώς θα πρέπει να το κάνει αντ 'αυτού; >> Θα πρέπει να το βήμα σε όλο το πράγμα. [Hardison] Ναι. Θα πρέπει να περάσουν από ένα κάθε φορά, ένα κάθε φορά. Είναι ένα τεράστιο - είναι ένας πόνος. Ποια είναι η άλλη - υπάρχει μια άλλη πτώση σε αυτό. [Βασίλης] Δεν μπορείτε να πάτε προς τα εμπρός και προς τα πίσω; Θα πρέπει να πάμε προς μία κατεύθυνση; [Hardison] Ναι. Επομένως, πώς θα λύσουμε ότι, μερικές φορές; [Βασίλης] διπλά συνδεδεμένες λίστες; Ακριβώς >>. Υπάρχουν διπλά συνδεδεμένες λίστες. Υπάρχουν επίσης - συγνώμη; 

[Sam] Είναι το ίδιο όπως με το πράγμα που προβλ - Μόλις θυμήθηκα, δεν είναι ότι αυτό το πράγμα είναι προβλ για; Δεν είναι ότι στο μεταξύ διπλή και μονή; Ματιά [Hardison] Ας τι ακριβώς έκανε. Έτσι, εδώ πηγαίνουμε. Εδώ είναι ο κώδικας λίστα. Εδώ έχουμε predptr, εδώ. Είναι αυτό που ήταν λες; Έτσι, αυτό ήταν - αυτός είναι απελευθερώνοντας μια λίστα και προσπαθεί να αποθηκεύσει ένα δείκτη σε αυτό. Αυτό δεν είναι τα διπλά, μεμονωμένα συνδέονται-λίστες. Μπορούμε να μιλήσουμε περισσότερο για αυτό αργότερα, δεδομένου ότι αυτό μιλά για την απελευθέρωση του καταλόγου και θέλω να δείξω κάποια άλλα πράγματα πρώτα. αλλά είναι ακριβώς - είναι να θυμηθούμε την αξία του ptr [Φοιτητικό] Ω, είναι δείκτης προηγούμενο; Ναι >>. Έτσι ώστε να μπορούμε να αυξήσετε τότε ptr ίδια πριν τότε δωρεάν predptr τι είναι. Επειδή δεν μπορούμε να ptr δωρεάν και στη συνέχεια να καλέσετε ptr = ptr επόμενη, έτσι δεν είναι; Αυτό θα ήταν κακό. Ας δούμε λοιπόν, πίσω σε αυτόν τον τύπο. 

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

Απλά πολύ γρήγορα, όταν διάγραμμα από αυτές τις λίστες, συνήθως έχουμε στην κατοχή μας για να το κεφάλι της λίστας ή του πρώτου δείκτη της λίστας και σημειώστε ότι αυτό είναι ένα πραγματικό δείκτη. Είναι μόλις 4 bytes. Δεν είναι ένα πραγματικό κόμβο ίδια. Βλέπετε λοιπόν ότι δεν έχει int αξία σε αυτό, δεν υπάρχει επόμενη δείκτη σε αυτό. Είναι κυριολεκτικά μόνο ένα δείκτη. Είναι πρόκειται να επισημάνω κάτι που είναι μια πραγματική struct node. [Sam] Ένας δείκτης που ονομάζεται κόμβος; >> Αυτό είναι - όχι. Αυτός είναι ένας δείκτης για κάτι τύπου του κόμβου. Πρόκειται για ένα δείκτη σε struct node. >> Ω, εντάξει. Διάγραμμα για την αριστερά, κωδικό στα δεξιά. Μπορούμε να ρυθμιστεί σε null, η οποία είναι ένας καλός τρόπος για να ξεκινήσει. Όταν το διάγραμμα, μπορείτε είτε να το γράψετε ως άκυρη ή να βάλετε μια γραμμή έτσι. 

Ένας από τους ευκολότερους τρόπους για να συνεργαστεί με τους καταλόγους, και σας ζητάμε να κάνετε και τα δύο και βάλε προσαρτήσει για να δείτε τις διαφορές μεταξύ των δύο, προσθέτοντας στην αρχή, αλλά είναι σίγουρα πιο εύκολη. Όταν βάζετε μπροστά, αυτό είναι όπου μπορείτε - όταν βάλε (7), να πάτε και να δημιουργήσετε το struct node και θα ορίσετε πρώτα να επισημάνω σε αυτό, γιατί τώρα, από τότε που το προταχθεί, πρόκειται να είναι στην αρχή της λίστας. Αν βάλε (3), που δημιουργεί ένα άλλο κόμβο, αλλά τώρα 3 έρχεται πριν από 7. Έτσι, είμαστε ουσιαστικά ωθεί τα πράγματα σε λίστα μας. Τώρα, μπορείτε να δείτε ότι βάλε, μερικές φορές οι άνθρωποι αποκαλούν ωθεί, επειδή είστε πιέζει ένα νέο στοιχείο σε λίστα σας. Είναι επίσης εύκολο να διαγραφεί στο μπροστινό μέρος του καταλόγου. Έτσι οι άνθρωποι θα καλέσει συχνά ότι η ποπ. Και με αυτόν τον τρόπο, μπορείτε να μιμηθεί μια στοίβα χρησιμοποιώντας μια συνδεδεμένη λίστα. Ουπς. Λυπούμαστε, αλλά τώρα μπαίνουμε σε προσάρτησης. Έτσι, εδώ θα προταχθεί (7), τώρα βάλε το (3). Αν προταχθεί κάτι άλλο πάνω σε αυτή τη λίστα, αν προταχθεί (4), τότε θα είχαμε 4 και στη συνέχεια 3 και στη συνέχεια 7. Έτσι λοιπόν θα μπορούσαμε να σκάσει και να αφαιρέσετε 4, αφαίρεση 3, αφαιρέστε 7. Συχνά, το πιο έξυπνο τρόπο για να σκεφτεί για αυτό είναι με προσάρτησης. Έτσι έχω διαγραμματικά τι θα μοιάζουν με προσθέσετε εδώ. Εδώ, το οποίο επισυνάπτεται (7) δεν φαίνεται διαφορετικό επειδή υπάρχει μόνο ένα στοιχείο στη λίστα. Και προσάρτηση (3) θέτει στο τέλος. Ίσως μπορείτε να δείτε τώρα το κόλπο με προσάρτησης είναι ότι από τη στιγμή που γνωρίζουν μόνο όταν η αρχή της λίστας είναι, να προσθέσετε σε μια λίστα που έχετε να περπατήσετε σε όλη τη διαδρομή μέσα από τη λίστα για να φτάσουμε στο τέλος, να σταματήσει, να χτίσουν τότε ο κόμβος σας και ό, τι τραβώ. Συνδέστε όλα τα πράγματα επάνω. Έτσι, με βάλε, όπως μόλις άρπαξαν μέσα από αυτό πολύ γρήγορα, όταν βάζετε μπροστά σε μια λίστα, είναι αρκετά απλό. 

Μπορείτε να κάνετε νέος κόμβος σας, περιλαμβάνουν κάποια δυναμική κατανομή μνήμης. Έτσι, εδώ είμαστε κάνοντας μια struct node χρησιμοποιώντας malloc. Έτσι malloc που χρησιμοποιούμε γιατί αυτό θα αναιρέσει τη μνήμη μας για αργότερα γιατί δεν θέλουμε αυτό - θέλουμε αυτή η μνήμη να διατηρηθεί για μεγάλο χρονικό διάστημα. Και έχουμε ένα δείκτη προς το χώρο στη μνήμη που μόλις διατεθεί. Χρησιμοποιούμε το μέγεθος του κόμβου, δεν αθροίζουν τα πεδία. Εμείς δεν παράγουν αυτόματα τον αριθμό των bytes, αντί να χρησιμοποιούμε sizeof ώστε να ξέρουμε παίρνουμε τον κατάλληλο αριθμό των bytes. Φροντίζουμε να ελέγξετε ότι η κλήση malloc μας πέτυχε. Αυτό είναι κάτι που θέλετε να κάνετε σε γενικές γραμμές. Με σύγχρονα μηχανήματα, που τρέχει από μνήμη δεν είναι κάτι που είναι εύκολο εκτός και αν είστε κατανομή έναν τόνο πράγματα και κάνοντας μια τεράστια λίστα, αλλά αν χτίζετε τα πράγματα για την, ας πούμε, σαν ένα iPhone ή Android, που έχουν περιορισμένους πόρους μνήμης, ειδικά αν κάνετε κάτι έντονο. Γι 'αυτό είναι καλό να μπει σε πράξη. 

Σημειώστε ότι έχω χρησιμοποιήσει ένα ζευγάρι διαφορετικές λειτουργίες εδώ ότι έχετε δει ότι είναι το είδος των νέων. Έτσι fprintf είναι ακριβώς όπως printf εκτός από το πρώτο επιχείρημά της είναι το ρεύμα στο οποίο θέλετε να εκτυπώσετε. Σε αυτή την περίπτωση, θέλουμε να εκτυπώσετε με το πρότυπο σφάλμα σειρά το οποίο είναι διαφορετικό από το πρότυπο outstream. Εξ ορισμού εμφανίζεται στην ίδια θέση. Τυπώνει επίσης στον τερματικό σταθμό, αλλά μπορείτε - χρησιμοποιώντας αυτές τις εντολές μάθατε για, τις τεχνικές ανακατεύθυνση μάθατε σχετικά με το βίντεο του Tommy για σετ πρόβλημα 4, μπορείτε να το κατευθύνει σε διαφορετικές περιοχές? στη συνέχεια, βγείτε, ακριβώς εδώ, βγαίνει από το πρόγραμμά σας. Είναι ουσιαστικά σαν επιστροφή από την κύρια, εκτός από την έξοδο χρησιμοποιούμε εδώ επειδή επιστροφή δεν θα κάνει τίποτα. Δεν είμαστε σε γενικές γραμμές, έτσι ώστε επιστρέφοντας δεν βγείτε από το πρόγραμμα, όπως θέλουμε. Γι 'αυτό και χρησιμοποιούν τη λειτουργία εξόδου και να της δώσει έναν κωδικό σφάλματος. Στη συνέχεια, εδώ έχουμε δημιουργήσει τομέα αξία του νέου κόμβου, στον τομέα του i να είναι ίση με i, και τότε το σύρμα μέχρι. Είμαστε δίπλα δείκτη του νέου κόμβου στο σημείο από την πρώτη, και τότε η πρώτη θα είναι πλέον το σημείο στο νέο κόμβο. Αυτές οι πρώτες γραμμές κώδικα, χτίζουμε στην πραγματικότητα το νέο κόμβο. Δεν είναι οι δύο τελευταίες γραμμές αυτής της λειτουργίας, αλλά οι πρώτοι. Μπορείτε πραγματικά τραβήξει έξω σε μια λειτουργία, σε μια συνάρτηση βοηθητικού. Αυτό είναι συχνά αυτό που κάνω είναι, εγώ το τραβήξει έξω σε λειτουργία, Καλώ κάτι σαν κόμβος κατασκευής, και ότι κρατά η λειτουργία βάλε αρκετά μικρό, είναι μόλις 3 γραμμές τότε. Κάνω μια έκκληση να οικοδομήσουμε λειτουργία κόμβο μου, και τότε τα πάντα σύρμα επάνω. 

Το τελευταίο πράγμα που θέλω να σας δείξω, και εγώ θα σας αφήσει να κάνει append και όλα αυτά με δική σας, είναι το πώς να επαναλάβει πάνω από μια λίστα. Υπάρχουν ένα σωρό διαφορετικούς τρόπους για να επαναλάβει πάνω από μια λίστα. Σε αυτή την περίπτωση, θα πάμε να βρείτε το μήκος μιας λίστας. Έτσι ξεκινάμε με μήκος = 0. Αυτό είναι πολύ παρόμοιο με strlen γραπτώς για μια σειρά. Αυτό είναι ό, τι θέλω να σου δείξω, το δικαίωμα για βρόχο εδώ. Φαίνεται κάπως funky? Δεν είναι η συνήθης int i = 0, i <οτιδήποτε άλλο, i + +. Αντ 'αυτού, είναι αρχικοποίηση μεταβλητής n μας να είναι η αρχή της λίστας. Και στη συνέχεια, ενώ iterator μεταβλητή μας δεν είναι μηδενική, θα συνεχίσω. Αυτό οφείλεται στο γεγονός ότι, κατά συνθήκη, το τέλος του καταλόγου μας θα είναι μηδενική. Και στη συνέχεια, για να αυξήσετε, αντί να κάνει + +, το συνδεδεμένο ισοδύναμο κατάλογος των + + είναι η = n-> επόμενη. 

Θα σας αφήσω να καλύψει τα κενά εδώ επειδή είμαστε έξω από το χρόνο. Αλλά να έχετε κατά νου αυτό που εργάζεστε για psets spellr σας. Συνδέεται λίστες, εάν είστε εφαρμογή ενός πίνακα κατακερματισμού, σίγουρα θα έρθει πολύ σε πρακτικό. Και έχοντας αυτό το ιδίωμα για looping πάνω από πράγματα που θα κάνουν τη ζωή πολύ πιο εύκολο, ελπίζω. Οποιεσδήποτε ερωτήσεις, γρήγορα; [Sam] Θα σας στείλει το συμπληρωμένο SLL και sc; [Hardison] Ναι. Θα στείλει ολοκληρωθεί διαφάνειες και ολοκληρώθηκε στοίβα SLL και queue.cs. [CS50.TV]