1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Ενότητα 6: Λιγότερο Άνετα]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Πανεπιστήμιο του Χάρβαρντ]

3
00:00:05,040 --> 00:00:07,320
[Αυτό είναι CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Εντάξει. Καλώς ήρθατε στο τμήμα 6.

5
00:00:11,840 --> 00:00:14,690
Αυτή την εβδομάδα, θα πάμε να μιλάμε για δομές δεδομένων στο τμήμα,

6
00:00:14,690 --> 00:00:19,780
κυρίως επειδή το πρόβλημα αυτής της εβδομάδας που για spellr

7
00:00:19,780 --> 00:00:24,410
κάνει ένα σωρό διαφορετικές εξερεύνηση δομή δεδομένων.

8
00:00:24,410 --> 00:00:26,520
Υπάρχουν ένα σωρό διαφορετικοί τρόποι που μπορείτε να πάτε με το σύνολο πρόβλημα,

9
00:00:26,520 --> 00:00:31,570
και οι περισσότερες δομές δεδομένων που γνωρίζουν, τα πιο δροσερά πράγματα που μπορείτε να κάνετε.

10
00:00:31,570 --> 00:00:34,990
>> Οπότε ας ξεκινήσουμε. Πρώτα θα πάμε να μιλήσουμε για στοίβες,

11
00:00:34,990 --> 00:00:37,530
τα δεδομένα στοίβα και ουρά δομές που θα πάμε να μιλήσουμε για.

12
00:00:37,530 --> 00:00:40,560
Στοίβες και ουρές είναι πραγματικά χρήσιμη όταν αρχίσουμε να μιλάμε για γραφικές παραστάσεις,

13
00:00:40,560 --> 00:00:44,390
το οποίο δεν πρόκειται να κάνει τόσο πολύ από τώρα.

14
00:00:44,390 --> 00:00:52,820
Αλλά είναι πραγματικά καλό για να καταλάβει μια από τις μεγάλες θεμελιώδεις δομές δεδομένων του CS.

15
00:00:52,820 --> 00:00:54,880
Η περιγραφή στην προδιαγραφή σετ προβλήματος,

16
00:00:54,880 --> 00:00:59,260
αν το σηκώσει, μιλά για στοίβες ως παρόμοια με

17
00:00:59,260 --> 00:01:05,239
ο σωρός των δίσκων φαγητού που έχετε στην καφετέρια στις αίθουσες φαγητού

18
00:01:05,239 --> 00:01:09,680
όπου όταν το προσωπικό φαγητό έρχεται και βάζει τους δίσκους φαγητού έξω αφού έχουν καθαριστεί τους,

19
00:01:09,680 --> 00:01:12,000
συσσωρεύουν τους το ένα πάνω από το άλλο.

20
00:01:12,000 --> 00:01:15,050
Και στη συνέχεια, όταν τα παιδιά έρχονται για να πάρει τα τρόφιμα,

21
00:01:15,050 --> 00:01:19,490
τραβούν τους δίσκους, πρώτα η κορυφή ενός, τότε το ένα κάτω από αυτό, τότε το ένα κάτω από αυτό.

22
00:01:19,490 --> 00:01:25,190
Έτσι, στην πραγματικότητα, ο πρώτος δίσκος ότι το προσωπικό τραπεζαρία καταθέσει είναι η τελευταία που παίρνει απογειωθεί.

23
00:01:25,190 --> 00:01:32,330
Το τελευταίο ότι το προσωπικό που διατίθενται στην τραπεζαρία είναι η πρώτη που παίρνει απογειωθεί για δείπνο.

24
00:01:32,330 --> 00:01:38,100
Σε spec του συνόλου του προβλήματος, το οποίο μπορείτε να κατεβάσετε αν δεν έχετε ήδη,

25
00:01:38,100 --> 00:01:46,730
μιλάμε για μοντελοποίηση μια δομή δεδομένων στοίβας με τη χρήση αυτού του είδους του struct.

26
00:01:46,730 --> 00:01:51,070
>> Έτσι, αυτό που έχουμε εδώ, αυτό είναι παρόμοιο με αυτό που παρουσιάστηκε σε διάλεξη,

27
00:01:51,070 --> 00:01:58,120
εκτός από διάλεξη που παρουσίασε αυτό με ints, σε αντίθεση με char * s.

28
00:01:58,120 --> 00:02:06,250
Αυτό πρόκειται να είναι μια στοίβα που αποθηκεύει ό, τι;

29
00:02:06,250 --> 00:02:09,009
Daniel; Τι μπορούμε αποθήκευση σε αυτή τη στοίβα;

30
00:02:09,009 --> 00:02:15,260
[Daniel] χορδές; >> Είμαστε αποθήκευση χορδές σε αυτή τη στοίβα, ακριβώς.

31
00:02:15,260 --> 00:02:20,950
Το μόνο που πρέπει να έχετε για να δημιουργήσετε μια στοίβα είναι ένας πίνακας

32
00:02:20,950 --> 00:02:23,920
μιας συγκεκριμένης ικανότητας, η οποία σε αυτή την περίπτωση,

33
00:02:23,920 --> 00:02:28,020
χωρητικότητα θα είναι σε όλα τα καλύμματα, γιατί είναι μια σταθερά.

34
00:02:28,020 --> 00:02:36,340
Και στη συνέχεια, εκτός από την συστοιχία, όλα πρέπει να παρακολουθείτε είναι το τρέχον μέγεθος της συστοιχίας.

35
00:02:36,340 --> 00:02:38,980
Ένα πράγμα που πρέπει να σημειωθεί εδώ ότι είναι είδος δροσερό

36
00:02:38,980 --> 00:02:47,060
είναι ότι είμαστε δημιουργία της στοιβάζονται δομή δεδομένων στην κορυφή του άλλου δομή δεδομένων, η συστοιχία.

37
00:02:47,060 --> 00:02:50,110
Υπάρχουν διάφοροι τρόποι για την εφαρμογή στοίβες.

38
00:02:50,110 --> 00:02:54,250
Εμείς δεν θα το κάνουμε αρκετά ακόμα, αλλά ελπίζουμε ότι μετά από να κάνει τα συνδεδεμένα-λίστα προβλημάτων,

39
00:02:54,250 --> 00:03:00,520
θα δείτε πώς μπορείτε να εφαρμόσετε εύκολα μια στοίβα στην κορυφή ενός συνδεδεμένη λίστα, καθώς και.

40
00:03:00,520 --> 00:03:02,640
Αλλά για τώρα, θα τηρήσουμε τις συστοιχίες.

41
00:03:02,640 --> 00:03:06,350
Έτσι, και πάλι, το μόνο που χρειαζόμαστε είναι ένας πίνακας και το μόνο που χρειάζεται να παρακολουθείτε το μέγεθος του πίνακα.

42
00:03:06,350 --> 00:03:09,850
[Sam] Συγνώμη, γιατί είναι αυτό που σας είπε η στοίβα είναι πάνω από τις χορδές;

43
00:03:09,850 --> 00:03:13,440
Για μένα φαίνεται σαν οι χορδές είναι μέσα στη στοίβα.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Ναι. Είμαστε δημιουργώντας, είμαστε λαμβάνοντας σειρά μας δομή δεδομένων -

45
00:03:16,790 --> 00:03:22,130
αυτό είναι ένα μεγάλο ερώτημα. Έτσι, το ερώτημα είναι γιατί, για τους ανθρώπους που παρακολουθούν αυτό το σε απευθείας σύνδεση,

46
00:03:22,130 --> 00:03:24,140
γιατί λέμε ότι η στοίβα είναι πάνω από τις χορδές,

47
00:03:24,140 --> 00:03:27,990
γιατί εδώ φαίνεται σαν οι χορδές είναι μέσα στη στοίβα;

48
00:03:27,990 --> 00:03:31,050
Ποια είναι εντελώς η περίπτωση.

49
00:03:31,050 --> 00:03:34,660
Αυτό που αναφερόταν ήταν ότι έχουμε μια δομή δεδομένων πίνακα.

50
00:03:34,660 --> 00:03:39,290
Έχουμε μια σειρά από char * s, αυτή η σειρά των χορδών,

51
00:03:39,290 --> 00:03:45,300
και πρόκειται να προσθέσει στο ότι, προκειμένου να δημιουργηθεί η δομή δεδομένων στοιβάζονται.

52
00:03:45,300 --> 00:03:48,620
>> Έτσι, μια στοίβα είναι ελαφρώς πιο σύνθετη από μια συστοιχία.

53
00:03:48,620 --> 00:03:51,890
Μπορούμε να χρησιμοποιήσουμε μια σειρά για να οικοδομήσουμε μια στοίβα.

54
00:03:51,890 --> 00:03:55,810
Έτσι, αυτό είναι όπου μπορούμε να πούμε ότι η στοίβα είναι χτισμένο στην κορυφή ενός πίνακα.

55
00:03:55,810 --> 00:04:02,510
Επίσης, όπως είπα και προηγουμένως, μπορούμε να οικοδομήσουμε μια στοίβα στην κορυφή ενός συνδεδεμένη λίστα.

56
00:04:02,510 --> 00:04:04,960
Αντί να χρησιμοποιεί μια σειρά για να κρατήσει τα στοιχεία μας,

57
00:04:04,960 --> 00:04:10,070
θα μπορούσαμε να χρησιμοποιήσουμε μια συνδεδεμένη λίστα για να κρατήσει τα στοιχεία μας και να οικοδομήσουμε τη στοίβα γύρω από αυτό.

58
00:04:10,070 --> 00:04:12,420
Ας δούμε μερικά παραδείγματα, κοιτάζοντας κάποιο κωδικό,

59
00:04:12,420 --> 00:04:14,960
για να δούμε τι πραγματικά συμβαίνει εδώ.

60
00:04:14,960 --> 00:04:23,400
Στα αριστερά, έχω ρίξει τι struct στοίβα θα μοιάζουν στη μνήμη

61
00:04:23,400 --> 00:04:28,330
αν παραγωγικής ικανότητας # ορίζεται να είναι τέσσερα.

62
00:04:28,330 --> 00:04:33,490
Έχουμε τέσσερις-στοιχείο char array μας *.

63
00:04:33,490 --> 00:04:38,110
Έχουμε χορδές [0], χορδές [1], έγχορδα [2], strings [3],

64
00:04:38,110 --> 00:04:43,800
και στη συνέχεια, ότι το τελευταίο διάστημα για ακέραιο μεγέθους μας.

65
00:04:43,800 --> 00:04:46,270
Μήπως αυτό έχει νόημα; Εντάξει.

66
00:04:46,270 --> 00:04:48,790
Αυτό είναι τι θα συμβεί αν αυτό που κάνω στα δεξιά,

67
00:04:48,790 --> 00:04:55,790
η οποία θα είναι κωδικός μου, είναι να δηλώσει μόνο ένα struct, struct μια στοίβα που ονομάζεται s.

68
00:04:55,790 --> 00:05:01,270
Αυτό είναι ό, τι έχουμε. Καθορίζει αυτό το αποτύπωμα στη μνήμη.

69
00:05:01,270 --> 00:05:05,590
Το πρώτο ερώτημα εδώ είναι ποια είναι τα περιεχόμενα αυτής της struct στοίβα;

70
00:05:05,590 --> 00:05:09,250
Αυτή τη στιγμή δεν είναι τίποτα, αλλά δεν είναι απολύτως τίποτα.

71
00:05:09,250 --> 00:05:13,300
Είναι αυτό το είδος των σκουπιδιών. Δεν έχουμε καμία ιδέα για το τι είναι σε αυτούς.

72
00:05:13,300 --> 00:05:17,000
Όταν δηλώνουμε s στοίβα, είμαστε ρίχνουν απλώς ότι κάτω στην κορυφή της μνήμης.

73
00:05:17,000 --> 00:05:19,840
Είναι κάτι σαν δήλωση int i και όχι την αρχικοποίηση.

74
00:05:19,840 --> 00:05:21,730
Δεν ξέρεις τι είναι εκεί. Μπορείτε να διαβάσετε τι υπάρχει εκεί μέσα,

75
00:05:21,730 --> 00:05:27,690
αλλά μπορεί να μην είναι σούπερ χρήσιμη.

76
00:05:27,690 --> 00:05:32,680
Ένα πράγμα που θέλετε να θυμάστε πάντα να κάνετε είναι να προετοιμάσει ό, τι χρειάζεται για να προετοιμαστεί.

77
00:05:32,680 --> 00:05:35,820
Σε αυτή την περίπτωση, θα πάμε να προετοιμαστεί το μέγεθος να είναι μηδέν,

78
00:05:35,820 --> 00:05:39,960
γιατί αυτό πρόκειται να αποδειχθεί ότι είναι πολύ σημαντικό για εμάς.

79
00:05:39,960 --> 00:05:43,450
Θα μπορούσαμε να πάμε μπροστά και να προετοιμάσει όλους τους δείκτες, όλοι οι char * s,

80
00:05:43,450 --> 00:05:49,670
να είναι κατανοητή κάποια αξία, κατά πάσα πιθανότητα μηδενική.

81
00:05:49,670 --> 00:05:58,270
Αλλά δεν είναι εντελώς απαραίτητο να το κάνουμε αυτό.

82
00:05:58,270 --> 00:06:04,200
>> Τώρα, είναι οι δύο κύριες πράξεις στις στοίβες;

83
00:06:04,200 --> 00:06:07,610
Ο καθένας θυμάται διάλεξη από ό, τι κάνετε με στοίβες; Ναι;

84
00:06:07,610 --> 00:06:09,700
[Στέλλα] Ώθηση και σκάει; Ακριβώς >>.

85
00:06:09,700 --> 00:06:13,810
Ώθηση και σκάει είναι οι δύο κύριες πράξεις στις στοίβες.

86
00:06:13,810 --> 00:06:17,060
Και τι δεν κάνω ώθηση; >> Θα πρέπει να θέσει κάτι στην κορυφή

87
00:06:17,060 --> 00:06:19,300
της στοίβας, και στη συνέχεια σκασίματος απογειώνεται.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Ακριβώς. Έτσι πιέζει ωθεί κάτι στην κορυφή της στοίβας.

89
00:06:23,150 --> 00:06:27,700
Είναι σαν το προσωπικό τραπεζαρία βάζοντας ένα δίσκο τραπεζαρία κάτω από τον πάγκο.

90
00:06:27,700 --> 00:06:33,630
Και σκάει παίρνει ένα δίσκο φαγητού από την στοίβα.

91
00:06:33,630 --> 00:06:36,460
Ας δούμε μερικά παραδείγματα του τι συμβαίνει

92
00:06:36,460 --> 00:06:39,720
όταν πιέζουμε τα πράγματα στη στοίβα.

93
00:06:39,720 --> 00:06:45,110
Αν ήταν να ωθήσει τη συμβολοσειρά «γεια» σε στοίβα μας,

94
00:06:45,110 --> 00:06:49,760
αυτό είναι ό, τι διάγραμμα μας θα μοιάζουν τώρα.

95
00:06:49,760 --> 00:06:53,410
Δείτε τι συμβαίνει;

96
00:06:53,410 --> 00:06:56,530
Προωθήσαμε στο πρώτο στοιχείο του πίνακα χορδές μας

97
00:06:56,530 --> 00:07:01,420
και αύξησαν μέτρηση του μεγέθους μας να είναι 1.

98
00:07:01,420 --> 00:07:05,340
Έτσι, αν κοιτάξουμε τη διαφορά μεταξύ των δύο διαφάνειες, εδώ ήταν 0, είναι εδώ πριν από το πάτημα.

99
00:07:05,340 --> 00:07:08,690
Εδώ είναι μετά το πάτημα.

100
00:07:08,690 --> 00:07:13,460
Πριν από την ώθηση, μετά το πάτημα.

101
00:07:13,460 --> 00:07:16,860
Και τώρα έχουμε ένα στοιχείο στη στοίβα μας.

102
00:07:16,860 --> 00:07:20,970
Είναι η σειρά "γεια", και αυτό είναι όλο.

103
00:07:20,970 --> 00:07:24,440
Όλα τα υπόλοιπα στον πίνακα, σε σειρά χορδές μας, εξακολουθεί να είναι σκουπίδια.

104
00:07:24,440 --> 00:07:27,070
Δεν έχουν αρχικοποιηθεί.

105
00:07:27,070 --> 00:07:29,410
Ας πούμε ότι ωθήσει μια άλλη σειρά στο stack μας.

106
00:07:29,410 --> 00:07:32,210
Εμείς πάμε για να ωθήσει "κόσμο" σε αυτό το χρονικό διάστημα.

107
00:07:32,210 --> 00:07:35,160
Έτσι, μπορείτε να δείτε "κόσμο" εδώ πηγαίνει στην κορυφή του "γεια",

108
00:07:35,160 --> 00:07:40,040
και η μέτρηση μεγέθους πηγαίνει μέχρι 2.

109
00:07:40,040 --> 00:07:44,520
Τώρα μπορούμε να πιέσουμε "CS50", και ότι θα πάει και πάλι στην κορυφή.

110
00:07:44,520 --> 00:07:51,110
Αν πάμε πίσω, μπορείτε να δείτε πώς είμαστε πιέζει τα πράγματα στην κορυφή της στοίβας.

111
00:07:51,110 --> 00:07:53,320
Και τώρα έχουμε την ευκαιρία να σκάσει.

112
00:07:53,320 --> 00:07:58,910
Όταν έσκασε κάτι από την στοίβα, τι συνέβη;

113
00:07:58,910 --> 00:08:01,540
Ο καθένας δείτε τη διαφορά; Είναι πολύ λεπτή.

114
00:08:01,540 --> 00:08:05,810
[Φοιτητικό] Το μέγεθος. >> Ναι, το μέγεθος αλλάξει.

115
00:08:05,810 --> 00:08:09,040
>> Τι άλλο θα περίμενε κανείς να αλλάξει;

116
00:08:09,040 --> 00:08:14,280
[Φοιτητικό] Οι χορδές, πάρα πολύ. Δικαίωμα >>. Οι χορδές πάρα πολύ.

117
00:08:14,280 --> 00:08:17,110
Αποδεικνύεται ότι όταν κάνετε αυτό τον τρόπο,

118
00:08:17,110 --> 00:08:21,960
επειδή δεν είμαστε αντιγραφή των στοιχείων σε στοίβα μας,

119
00:08:21,960 --> 00:08:24,670
στην πραγματικότητα δεν έχουμε να κάνουμε τίποτα? μπορούμε να χρησιμοποιήσουμε μόνο το μέγεθος

120
00:08:24,670 --> 00:08:28,630
να παρακολουθείτε τον αριθμό των πραγμάτων σε σειρά μας

121
00:08:28,630 --> 00:08:33,780
έτσι ώστε όταν θα εμφανιστεί και πάλι, και πάλι θα μειώσετε ακριβώς το μέγεθος μας κάτω προς 1.

122
00:08:33,780 --> 00:08:39,440
Δεν υπάρχει καμία ανάγκη να πάει στην πραγματικότητα και να αντικαταστήσετε τίποτα.

123
00:08:39,440 --> 00:08:41,710
Είδος funky.

124
00:08:41,710 --> 00:08:46,520
Αποδεικνύεται ότι συνήθως αφήνουν τα πράγματα απλά και μόνο επειδή είναι λιγότερη δουλειά να κάνουμε.

125
00:08:46,520 --> 00:08:50,060
Αν δεν έχουμε να πάμε πίσω και να αντικαταστήσετε κάτι, τότε γιατί το κάνουν;

126
00:08:50,060 --> 00:08:54,150
Έτσι, όταν θα σκάσει δύο φορές από την στοίβα, το μόνο που κάνει είναι να ελαττώσει το μέγεθος μια-δυο φορές.

127
00:08:54,150 --> 00:08:59,120
Και πάλι, αυτό είναι μόνο επειδή δεν είμαστε αντιγραφή πράγματα σε στοίβα μας.

128
00:08:59,120 --> 00:09:01,320
Ναι; Προχωρήστε.

129
00:09:01,320 --> 00:09:04,460
[Φοιτητών, ακατάληπτο] >> Και τότε τι θα συμβεί όταν πιέσετε πάλι κάτι;

130
00:09:04,460 --> 00:09:08,570
Όταν πατήσετε ξανά κάτι, πού να πάει;

131
00:09:08,570 --> 00:09:12,390
Πού να πάει, Βασίλειος; Σε χορδές >> [1]; Δικαίωμα >>.

132
00:09:12,390 --> 00:09:14,530
Γιατί δεν πάτε σε σειρές [3];

133
00:09:14,530 --> 00:09:19,410
[Βασίλης] Επειδή ξέχασα ότι υπήρχε κάτι σε χορδές [1] και [2];

134
00:09:19,410 --> 00:09:24,040
[Hardison] Ακριβώς. Stack μας, ουσιαστικά, "ξέχασε" ότι κρατούσε σε οτιδήποτε

135
00:09:24,040 --> 00:09:29,480
στις χορδές [1] ή χορδές [2], έτσι ώστε όταν πιέζουμε "woot",

136
00:09:29,480 --> 00:09:36,670
βάζει ακριβώς ότι μέσα στο στοιχείο σε χορδές [1].

137
00:09:36,670 --> 00:09:41,590
Υπάρχουν ερωτήματα σχετικά με το πώς αυτό λειτουργεί, σε ένα βασικό επίπεδο;

138
00:09:41,590 --> 00:09:45,160
[Sam] Έτσι, αυτό δεν είναι δυναμική με οποιονδήποτε τρόπο, όσον αφορά το ποσό

139
00:09:45,160 --> 00:09:47,620
ή από την άποψη του μεγέθους της στοίβας;

140
00:09:47,620 --> 00:09:56,750
[Hardison] Ακριβώς. Αυτό είναι - το σημείο ήταν ότι αυτό δεν ήταν ένα δυναμικά αναπτυσόμενη στοίβα.

141
00:09:56,750 --> 00:10:02,850
Αυτή είναι μια στοίβα που μπορεί να κρατήσει το πολύ, τέσσερις char * s, το πολύ τέσσερα πράγματα.

142
00:10:02,850 --> 00:10:07,580
Αν ήταν να προσπαθήσουμε και να προωθήσει ένα πέμπτο πράγμα, τι νομίζετε ότι θα συμβεί;

143
00:10:07,580 --> 00:10:11,870
[Φοιτητές, ακατάληπτο]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Ακριβώς. Υπάρχουν μια σειρά από πράγματα που θα μπορούσε να συμβεί.

145
00:10:14,600 --> 00:10:19,330
Θα μπορούσε ενδεχομένως να διαχωρίζονται από σφάλμα, ανάλογα με το τι ήμασταν -

146
00:10:19,330 --> 00:10:22,530
πώς ακριβώς είχαμε την εφαρμογή του back-end.

147
00:10:22,530 --> 00:10:31,740
Θα μπορούσε να αντικαταστήσει. Θα μπορούσε να έχει αυτό το υπερχείλιση του buffer για την οποία μιλήσαμε στην τάξη.

148
00:10:31,740 --> 00:10:35,240
Ποιο θα ήταν το πιο προφανές πράγμα που θα μπορούσε να αντικατασταθεί

149
00:10:35,240 --> 00:10:42,370
αν προσπαθήσαμε να ωθήσει ένα επιπλέον πράγμα στη στοίβα μας;

150
00:10:42,370 --> 00:10:44,550
Έτσι, αναφέρατε μια υπερχείλιση του buffer.

151
00:10:44,550 --> 00:10:47,870
Τι θα μπορούσε να είναι το πράγμα που θα μπορούσε να πάρει ή να γράψει πάνω σε stomped

152
00:10:47,870 --> 00:10:52,320
αν ξεχειλίζει κατά λάθος, προσπαθώντας να ωθήσει ένα επιπλέον πράγμα;

153
00:10:52,320 --> 00:10:54,730
[Daniel, ακατάληπτο] >> Πιθανές.

154
00:10:54,730 --> 00:10:58,440
Αλλά αρχικά, τι θα μπορούσε να συμβεί; Τι και αν προσπαθήσαμε να ωθήσει ένα τέταρτο πράγμα;

155
00:10:58,440 --> 00:11:06,220
Θα μπορούσε να αντικαταστήσετε το μέγεθος, τουλάχιστον με αυτό το διάγραμμα μνήμης που έχουμε.

156
00:11:06,220 --> 00:11:10,880
>> Στο σύνολο προδιαγραφών πρόβλημα, το οποίο είναι αυτό που θα πάμε να υλοποιούν σήμερα,

157
00:11:10,880 --> 00:11:16,030
τι θέλουμε να κάνουμε είναι απλά να επιστρέψετε ψευδής.

158
00:11:16,030 --> 00:11:20,030
Μέθοδο της προώθησης μας πρόκειται να επιστρέψει μια τιμή boolean,

159
00:11:20,030 --> 00:11:22,920
και ότι boolean τιμή θα ισχύει αν η ώθηση πετύχει

160
00:11:22,920 --> 00:11:29,730
ψευδείς και αν δεν μπορούμε να πιέζουμε τίποτα περισσότερο, επειδή η στοίβα είναι πλήρης.

161
00:11:29,730 --> 00:11:33,620
Ας δούμε λίγο κώδικα τώρα.

162
00:11:33,620 --> 00:11:36,400
Εδώ είναι η λειτουργία ώθησης μας.

163
00:11:36,400 --> 00:11:40,380
Λειτουργία ώθηση μας για μια στοίβα πρόκειται να λάβει σειρά του να θέσει στη στοίβα.

164
00:11:40,380 --> 00:11:45,820
Είναι πρόκειται να επιστρέψει true αν το string με επιτυχία ώθησε

165
00:11:45,820 --> 00:11:51,820
επί της στοίβας και ψευδείς διαφορετικά.

166
00:11:51,820 --> 00:11:59,740
Οποιεσδήποτε προτάσεις σχετικά με το τι θα μπορούσε να είναι ένα καλό πρώτο πράγμα που πρέπει να κάνουμε εδώ;

167
00:11:59,740 --> 00:12:20,630
[Sam] Εάν το μέγεθος ισούται με ικανότητα στη συνέχεια επιστρέφουν λάθος;

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Καλή δουλειά.

169
00:12:23,320 --> 00:12:26,310
Εάν το μέγεθος είναι η ικανότητα, θα πάμε να επιστρέψει ψευδείς.

170
00:12:26,310 --> 00:12:29,270
Εμείς δεν μπορούμε να βάλουμε κάτι περισσότερο σε στοίβα μας.

171
00:12:29,270 --> 00:12:36,900
Διαφορετικά, θέλουμε να βάλουμε κάτι στην κορυφή της στοίβας.

172
00:12:36,900 --> 00:12:41,670
Τι είναι η «κορυφή της στοίβας," αρχικά;

173
00:12:41,670 --> 00:12:43,650
[Daniel] Μέγεθος 0; Μέγεθος >> 0.

174
00:12:43,650 --> 00:12:49,990
Ποια είναι η κορυφή της στοίβας μετά υπάρχει ένα πράγμα στη στοίβα; Missy, το ξέρεις;

175
00:12:49,990 --> 00:12:52,720
[Missy] One. Μέγεθος >> είναι ένα, ακριβώς. Θα συνεχίσουμε να προσθέτουμε με το μέγεθος,

176
00:12:52,720 --> 00:13:01,690
και κάθε φορά που βάζετε στο νέο στοιχείο στο μέγεθος δείκτη στον πίνακα.

177
00:13:01,690 --> 00:13:05,470
Μπορούμε να το κάνουμε με αυτό το είδος του ένα σκάφος της γραμμής, αν αυτό έχει νόημα.

178
00:13:05,470 --> 00:13:11,910
Έτσι έχουμε χορδές σειρά μας, θα πάμε να έχουν πρόσβαση στο μέγεθος του δείκτη,

179
00:13:11,910 --> 00:13:14,780
και είμαστε ακριβώς πρόκειται να αποθηκεύσετε char * μας εκεί.

180
00:13:14,780 --> 00:13:19,340
Παρατηρήστε πως δεν υπάρχει αντιγραφή συμβολοσειράς συμβαίνει εδώ,

181
00:13:19,340 --> 00:13:29,680
Δεν δυναμική κατανομή της μνήμης;

182
00:13:29,680 --> 00:13:34,440
Και στη συνέχεια, Missy μεγαλώσει αυτό που έχουμε τώρα να κάνουμε,

183
00:13:34,440 --> 00:13:40,570
επειδή έχουμε αποθηκεύσει το κορδόνι στην κατάλληλη θέση του πίνακα,

184
00:13:40,570 --> 00:13:49,230
και είπε ότι θα έπρεπε να αυξήσετε το μέγεθος από ένα έτσι ώστε να είμαστε έτοιμοι για την επόμενη ώθηση.

185
00:13:49,230 --> 00:13:53,950
Έτσι, μπορούμε να το κάνουμε αυτό με s.size + +.

186
00:13:53,950 --> 00:13:59,330
Σε αυτό το σημείο, έχουμε ωθούνται σε σειρά μας. Ποιο είναι το τελευταίο πράγμα που πρέπει να κάνουμε;

187
00:13:59,330 --> 00:14:10,110
[Φοιτητικό] Επιστροφή αλήθεια. >> Επιστροφή αλήθεια.

188
00:14:10,110 --> 00:14:14,690
Γι 'αυτό είναι αρκετά απλή, ένα αρκετά απλό κώδικα. Όχι πάρα πολύ.

189
00:14:14,690 --> 00:14:17,070
Μόλις έχετε το κεφάλι σας τυλιγμένο γύρω από το πώς λειτουργεί η στοίβα,

190
00:14:17,070 --> 00:14:21,910
αυτό είναι πολύ απλό στην εφαρμογή του.

191
00:14:21,910 --> 00:14:26,390
>> Τώρα, το επόμενο τμήμα της αυτό βρεθώ μια συμβολοσειρά από την στοίβα.

192
00:14:26,390 --> 00:14:29,410
Πάω να σας δώσω λίγο χρόνο για τα παιδιά να εργαστούν σε αυτό το λίγο.

193
00:14:29,410 --> 00:14:34,320
Είναι σχεδόν ουσιαστικά το αντίστροφο του τι έχουμε κάνει εδώ στην ώθηση.

194
00:14:34,320 --> 00:14:38,510
Αυτό που έχω κάνει είναι στην πραγματικότητα - ουπς.

195
00:14:38,510 --> 00:14:48,160
Έχω ξεκινήσει μια συσκευή μέχρι εδώ, και στη συσκευή,

196
00:14:48,160 --> 00:14:53,600
Έχω τράβηξε το πρόβλημα σετ 5 προδιαγραφές.

197
00:14:53,600 --> 00:15:02,560
Αν μεγέθυνση εδώ, μπορούμε να δούμε ότι είμαι σε cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Έχετε εσείς κατεβάσει τον κώδικα που που βρίσκεται, εδώ section6.zip;

199
00:15:08,590 --> 00:15:15,030
Εντάξει. Αν δεν το έχετε κάνει αυτό, το κάνουμε αυτό τώρα, πραγματικά γρήγορα.

200
00:15:15,030 --> 00:15:22,130
Θα το κάνω το παράθυρο του τερματικού μου.

201
00:15:22,130 --> 00:15:25,090
Το έκανα πραγματικά εδώ. Ναι.

202
00:15:25,090 --> 00:15:34,730
Ναι, Σαμ; >> Έχω μια ερώτηση σχετικά με το γιατί είπες παρένθεση s.string 's του μεγέθους = str;

203
00:15:34,730 --> 00:15:42,910
Τι είναι str; Είναι ορίζεται ότι κάπου πριν, ή - ω, στην char str *;

204
00:15:42,910 --> 00:15:47,160
[Hardison] Ναι, ακριβώς. Αυτό ήταν το επιχείρημα. >> Ω, εντάξει. Λυπάμαι.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Είμαστε προσδιορίζοντας το string για να ωθήσει μέσα

206
00:15:49,470 --> 00:15:55,220
Το άλλο ερώτημα που θα μπορούσε να καταλήξει ότι εμείς δεν μιλάμε για πραγματικά ήταν εδώ

207
00:15:55,220 --> 00:15:58,810
πήραμε ως δεδομένο ότι είχαμε αυτήν τη μεταβλητή που ονομάζεται s

208
00:15:58,810 --> 00:16:02,710
που ήταν στο πεδίο και προσιτή σε μας.

209
00:16:02,710 --> 00:16:06,960
Πήραμε δεδομένο ότι s ήταν αυτό struct στοίβα.

210
00:16:06,960 --> 00:16:08,930
Έτσι, κοιτάζοντας πίσω σε αυτό το πάτημα κώδικα,

211
00:16:08,930 --> 00:16:13,450
μπορείτε να δείτε ότι κάνουμε τα πράγματα με αυτή τη σειρά που πήρε πέρασε

212
00:16:13,450 --> 00:16:19,210
αλλά στη συνέχεια, ξαφνικά, είμαστε πρόσβαση s.size, όπως, πού προέρχονται από s;

213
00:16:19,210 --> 00:16:23,020
Στον κώδικα που θα πάμε να δούμε στο αρχείο τμήμα

214
00:16:23,020 --> 00:16:27,100
και στη συνέχεια τα πράγματα που θα κάνετε στο πρόβλημά σας θέτει,

215
00:16:27,100 --> 00:16:32,440
έχουμε κάνει stack μας struct μια καθολική μεταβλητή

216
00:16:32,440 --> 00:16:36,380
έτσι ώστε να μπορούμε να έχουμε πρόσβαση σε αυτό σε όλες τις διαφορετικές λειτουργίες μας

217
00:16:36,380 --> 00:16:40,630
χωρίς να χρειάζεται να περάσει το χέρι γύρω από αυτό και να περάσει από την αναφορά,

218
00:16:40,630 --> 00:16:44,870
κάνει όλα τέτοιου είδους πράγματα σε αυτό.

219
00:16:44,870 --> 00:16:52,280
Είμαστε εξαπάτηση ακριβώς λίγο, αν θέλετε, για να κάνει τα πράγματα πιο ωραίο.

220
00:16:52,280 --> 00:16:57,430
Και αυτό είναι κάτι που κάνουμε εδώ γιατί είναι για διασκέδαση, είναι πιο εύκολο.

221
00:16:57,430 --> 00:17:02,800
Συχνά, θα δείτε ανθρώπους να το κάνετε αυτό, αν έχετε μια μεγάλη δομή δεδομένων

222
00:17:02,800 --> 00:17:07,750
Αυτό είναι που λειτουργούν στο εσωτερικό τους πρόγραμμα.

223
00:17:07,750 --> 00:17:09,560
>> Ας πάμε πίσω πάνω στη συσκευή.

224
00:17:09,560 --> 00:17:15,240
Μήπως όλοι πάρει με επιτυχία την section6.zip;

225
00:17:15,240 --> 00:17:20,440
Όλοι το αποσυμπιέσετε χρησιμοποιώντας unzip section6.zip;

226
00:17:20,440 --> 00:17:27,200
Αν πάτε στο τμήμα 6 κατάλογο -

227
00:17:27,200 --> 00:17:29,220
Ααα, σε όλη τη χώρα -

228
00:17:29,220 --> 00:17:32,840
και θα απαριθμήσει τι είναι εδώ, θα δείτε ότι έχετε τρία διαφορετικά αρχεία. c.

229
00:17:32,840 --> 00:17:38,350
Έχεις μια ουρά, ένα SLL, η οποία είναι μεμονωμένα-συνδεδεμένη λίστα, και μια στοίβα.

230
00:17:38,350 --> 00:17:44,600
Αν ανοίξει stack.c,

231
00:17:44,600 --> 00:17:47,330
μπορείτε να δείτε ότι έχουμε αυτό το struct που ορίζονται για μας,

232
00:17:47,330 --> 00:17:51,330
η ακριβής struct που μόλις μίλησε για τις διαφάνειες.

233
00:17:51,330 --> 00:17:56,340
Έχουμε παγκόσμια μεταβλητή μας για τη στοίβα,

234
00:17:56,340 --> 00:18:00,110
έχουμε λειτουργία ώθησης μας,

235
00:18:00,110 --> 00:18:04,230
και στη συνέχεια έχουμε ποπ λειτουργία μας.

236
00:18:04,230 --> 00:18:08,320
Θα βάλω τον κωδικό για το σπρώξετε προς τα πίσω επάνω στη διαφάνεια εδώ,

237
00:18:08,320 --> 00:18:10,660
αλλά αυτό που θα ήθελα εσείς να κάνετε είναι, με τον καλύτερο την ικανότητά σας,

238
00:18:10,660 --> 00:18:13,790
πάνε και να εφαρμόσουν το ποπ λειτουργία.

239
00:18:13,790 --> 00:18:18,480
Μόλις έθεσε σε εφαρμογή, μπορείτε να συγκεντρώσετε αυτό με κάνει στοίβα,

240
00:18:18,480 --> 00:18:22,540
και στη συνέχεια, εκτελέστε το εκτελέσιμο που προκύπτει στοίβα,

241
00:18:22,540 --> 00:18:28,390
και ότι θα τρέξει όλες της παρούσας δοκιμής εδώ κάτω αυτό είναι το κύριο.

242
00:18:28,390 --> 00:18:31,060
Και κυρίως φροντίζει πραγματικά κάνει την ώθηση και ποπ κλήσεις

243
00:18:31,060 --> 00:18:33,220
και να διασφαλίσουμε ότι όλα θα πάνε όλα δεξιά μέσα.

244
00:18:33,220 --> 00:18:36,820
Είναι, επίσης αρχικοποιεί τη στοίβα μέγεθος εδώ

245
00:18:36,820 --> 00:18:39,780
έτσι δεν έχετε να ανησυχείτε για την αρχικοποίηση αυτό.

246
00:18:39,780 --> 00:18:42,310
Μπορείτε να υποθέσετε ότι είναι ήδη προετοιμαστεί σωστά

247
00:18:42,310 --> 00:18:48,000
από τη στιγμή που έχετε πρόσβαση σε αυτό το ποπ λειτουργία.

248
00:18:48,000 --> 00:18:53,530
Μήπως αυτό έχει νόημα;

249
00:18:53,530 --> 00:19:00,100
Έτσι, εδώ πηγαίνουμε. Υπάρχει η ώθηση κώδικα.

250
00:19:00,100 --> 00:19:13,210
Θα σας δώσω παιδιά 5 ή 10 λεπτά.

251
00:19:13,210 --> 00:19:15,690
Και αν έχετε οποιαδήποτε απορία στο μεσοδιάστημα ενώ είστε κωδικοποίησης,

252
00:19:15,690 --> 00:19:17,710
ρωτήστε τους δυνατά.

253
00:19:17,710 --> 00:19:23,080
Έτσι, αν φτάσουμε σε ένα κρίσιμο σημείο, απλά ρωτήστε.

254
00:19:23,080 --> 00:19:26,030
Επιτρέψτε μου να ξέρω, ας γνωρίζουν όλοι οι άλλοι.

255
00:19:26,030 --> 00:19:28,160
Εργασία με τον γείτονά σας πάρα πολύ.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Είμαστε μόλις ποπ εφαρμογή αυτή τη στιγμή; >> Απλά pop.

257
00:19:30,360 --> 00:19:34,200
Αν και μπορείτε να αντιγράψετε την εφαρμογή της πίεσης, αν θέλετε

258
00:19:34,200 --> 00:19:37,780
έτσι ώστε η δοκιμή θα λειτουργήσει.

259
00:19:37,780 --> 00:19:41,940
Επειδή είναι δύσκολο να δοκιμάσουν να μπουν τα πράγματα -

260
00:19:41,940 --> 00:19:49,030
ή, είναι δύσκολο να βρεθώ δοκιμάσουν τα πράγματα από μια στοίβα, αν δεν υπάρχει τίποτα στη στοίβα για να αρχίσει με.

261
00:19:49,030 --> 00:19:55,250
>> Ποια είναι η ποπ έπρεπε να επιστρέψει; Το στοιχείο από την κορυφή της στοίβας.

262
00:19:55,250 --> 00:20:01,260
Είναι υποτίθεται για να πάρει το στοιχείο μακριά από την κορυφή της στοίβας

263
00:20:01,260 --> 00:20:05,780
στη συνέχεια και θα ελαττώσει το μέγεθος της στοίβας,

264
00:20:05,780 --> 00:20:07,810
και τώρα έχετε χάσει το στοιχείο στην κορυφή.

265
00:20:07,810 --> 00:20:11,420
Και τότε θα επιστρέψει το στοιχείο στην κορυφή.

266
00:20:11,420 --> 00:20:20,080
[Φοιτητών, ακατάληπτο]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Λοιπόν, τι θα συμβεί αν το κάνετε αυτό; [Φοιτητών, ακατάληπτο]

268
00:20:28,810 --> 00:20:34,000
Τι συμβαίνει καταλήγει είναι έχετε πρόσβαση πιθανώς είτε

269
00:20:34,000 --> 00:20:37,350
Ένα στοιχείο που δεν έχει αρχικοποιηθεί ακόμα, έτσι υπολογισμό σας

270
00:20:37,350 --> 00:20:39,990
από όπου το τελευταίο στοιχείο είναι είναι απενεργοποιημένη.

271
00:20:39,990 --> 00:20:46,260
Μέχρι εδώ, αν παρατηρήσετε, σε ώθηση, είμαστε πρόσβαση χορδές στο στοιχείο s.size

272
00:20:46,260 --> 00:20:48,560
επειδή είναι ένα νέο δείκτη.

273
00:20:48,560 --> 00:20:51,460
Είναι η νέα κορυφή της στοίβας.

274
00:20:51,460 --> 00:21:01,100
Ότι, ποπ, s.size πρόκειται να είναι το επόμενο διάστημα,

275
00:21:01,100 --> 00:21:05,210
ο χώρος που είναι πάνω από όλα τα στοιχεία στη στοίβα σας.

276
00:21:05,210 --> 00:21:10,050
Έτσι, το top-πλέον στοιχείο δεν είναι σε s.size,

277
00:21:10,050 --> 00:21:14,930
αλλά μάλλον, είναι κάτω από αυτό.

278
00:21:14,930 --> 00:21:19,640
>> Το άλλο πράγμα που πρέπει να κάνετε όταν - σε ποπ,

279
00:21:19,640 --> 00:21:22,030
είναι που χρειάζεται να μειώσετε το μέγεθος.

280
00:21:22,030 --> 00:21:28,750
Αν θυμάστε λίγο πίσω στο διάγραμμα μας εδώ,

281
00:21:28,750 --> 00:21:30,980
Πραγματικά, το μόνο πράγμα που είδαμε να συμβαίνει όταν καλέσαμε ποπ

282
00:21:30,980 --> 00:21:36,150
ήταν ότι αυτό το μέγεθος μειώθηκε, πρώτη έως 2, στη συνέχεια με 1.

283
00:21:36,150 --> 00:21:42,620
Στη συνέχεια, όταν έσπρωξε ένα νέο στοιχείο σε, θα συνεχιστεί στη σωστή θέση.

284
00:21:42,620 --> 00:21:49,610
[Βασίλης] Αν η s.size είναι 2, τότε δεν θα το πάει στο στοιχείο 2,

285
00:21:49,610 --> 00:21:54,400
και στη συνέχεια θα θέλατε να εμφανιστεί αυτό το στοιχείο μακριά;

286
00:21:54,400 --> 00:21:59,510
Έτσι, αν πήγαμε στο - >> Ας ρίξουμε μια ματιά σε αυτό και πάλι.

287
00:21:59,510 --> 00:22:07,730
Αν αυτή είναι η στοίβα μας σε αυτό το σημείο

288
00:22:07,730 --> 00:22:12,130
και καλούμε ποπ,

289
00:22:12,130 --> 00:22:16,150
κατά την οποία ο δείκτης είναι το top-πλέον στοιχείο;

290
00:22:16,150 --> 00:22:19,300
[Βασίλης] Στις 2, αλλά πρόκειται να σκάσει 3. Δικαίωμα >>.

291
00:22:19,300 --> 00:22:24,220
Έτσι, αυτό είναι όπου το μέγεθος μας είναι 3, αλλά θέλουμε να εμφανιστεί το στοιχείο στο δείκτη 2.

292
00:22:24,220 --> 00:22:29,900
Είναι χαρακτηριστικό ότι το είδος της μακριά από αυτό που έχετε με το μηδέν τιμαριθμικής αναπροσαρμογής των συστοιχιών.

293
00:22:29,900 --> 00:22:36,430
Έτσι θέλετε να σκάσει το τρίτο στοιχείο, αλλά το τρίτο στοιχείο δεν είναι στο δείκτη 3.

294
00:22:36,430 --> 00:22:39,430
Και ο λόγος που δεν έχουμε να κάνουμε αυτό το μείον 1 όταν είμαστε πιέζει

295
00:22:39,430 --> 00:22:44,120
οφείλεται στο γεγονός ότι αυτή τη στιγμή, θα παρατηρήσετε ότι το top-πλέον στοιχείο,

296
00:22:44,120 --> 00:22:47,600
εάν επρόκειτο να ωθήσει κάτι άλλο στην στοίβα στο σημείο αυτό,

297
00:22:47,600 --> 00:22:50,360
θα θέλαμε να την προωθήσουν στο δείκτη 3.

298
00:22:50,360 --> 00:23:03,550
Και είναι ακριβώς έτσι συμβαίνει ότι το μέγεθος και οι δείκτες παρατάξει όταν πιέζει.

299
00:23:03,550 --> 00:23:06,960
>> Ποιος πήρε μια στοίβα εκτέλεσης εργασίας;

300
00:23:06,960 --> 00:23:09,690
Έχεις ένα σωρό εργασίας ένα. Μήπως έχετε ποπ εργάζονται ακόμα;

301
00:23:09,690 --> 00:23:11,890
[Δανιήλ] Ναι. Νομίζω πως ναι.

302
00:23:11,890 --> 00:23:14,610
Πρόγραμμα >> τρέχει και δεν διαχωρίζονται από ρήγματα, αυτό είναι εκτύπωση;

303
00:23:14,610 --> 00:23:17,520
Μήπως να το εκτυπώσετε "επιτυχία" όταν το τρέξετε;

304
00:23:17,520 --> 00:23:22,630
Ναι. Κάντε στοίβα, τρέχει, αν εκτυπώνει "επιτυχία" και δεν πηγαίνετε έκρηξη,

305
00:23:22,630 --> 00:23:26,000
τότε όλα είναι καλά.

306
00:23:26,000 --> 00:23:34,070
Εντάξει. Ας πάει πάνω στη συσκευή πολύ γρήγορα,

307
00:23:34,070 --> 00:23:46,100
και θα περπατήσετε μέσα από αυτό.

308
00:23:46,100 --> 00:23:51,110
Αν κοιτάξουμε τι συμβαίνει εδώ με pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, τι ήταν το πρώτο πράγμα που έκανε;

310
00:23:55,220 --> 00:23:58,850
[Daniel] Αν s.size είναι μεγαλύτερη από 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Εντάξει. Και γιατί το έκανες αυτό;

312
00:24:03,120 --> 00:24:05,610
[Daniel] Για να βεβαιωθείτε ότι δεν υπήρχε κάτι μέσα στο σωρό.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Δεξιά. Θέλετε να δοκιμάσετε για να βεβαιωθείτε ότι s.size είναι μεγαλύτερη από 0?

314
00:24:10,950 --> 00:24:13,280
αλλιώς, ό, τι θέλετε να συμβεί;

315
00:24:13,280 --> 00:24:16,630
[Daniel] Επιστροφή null; Επιστροφή >> null, ακριβώς.

316
00:24:16,630 --> 00:24:20,740
Έτσι, αν s.size είναι μεγαλύτερη από μηδέν. Τότε τι θα κάνουμε;

317
00:24:20,740 --> 00:24:25,890
Τι θα κάνουμε αν η στοίβα δεν είναι κενή;

318
00:24:25,890 --> 00:24:31,210
[Στέλλα] Θα μειώσετε το μέγεθος; >> Θα μειώσετε το μέγεθος, εντάξει.

319
00:24:31,210 --> 00:24:34,440
Λοιπόν, πώς το έκανες αυτό; >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Μεγάλη. Και τότε τι έκανες;

321
00:24:37,030 --> 00:24:44,140
[Στέλλα] Και τότε είπα επιστροφή s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Μεγάλη.

323
00:24:48,560 --> 00:24:51,940
Διαφορετικά, θα επιστρέψει null. Ναι, Σαμ;

324
00:24:51,940 --> 00:24:55,510
[Sam] Γιατί δεν θα πρέπει να είναι s.size + 1;

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1; Ναι >>. >> Το 'πιασα.

326
00:24:58,430 --> 00:25:00,980
[Sam] σκέφτηκα γιατί παίρνετε 1 από,

327
00:25:00,980 --> 00:25:04,290
τότε θα πάμε για να επιστρέψει δεν αυτό που ζήτησαν.

328
00:25:04,290 --> 00:25:09,400
[Hardison] Και αυτό ήταν ακριβώς ό, τι πράγμα μιλάμε με αυτό το όλο θέμα από 0 δείκτες.

329
00:25:09,400 --> 00:25:11,380
Έτσι, αν μεγεθύνετε εδώ.

330
00:25:11,380 --> 00:25:15,650
Αν κοιτάξουμε αυτόν τον τύπο εδώ, μπορείτε να δείτε ότι όταν σκάσει,

331
00:25:15,650 --> 00:25:19,340
είμαστε σκάει το στοιχείο στο δείκτη 2.

332
00:25:19,340 --> 00:25:25,200
>> Γι 'αυτό και μειώνουν το μέγεθος μας πρώτα, τότε το μέγεθος μας ταιριάζει δείκτη μας.

333
00:25:25,200 --> 00:25:39,650
Αν δεν μειώσετε το μέγεθος πρώτο, τότε έχουμε να κάνουμε μέγεθος -1 και στη συνέχεια μείωση.

334
00:25:39,650 --> 00:25:45,270
Μεγάλη. Όλα καλά;

335
00:25:45,270 --> 00:25:47,530
Οποιεσδήποτε ερωτήσεις σχετικά με αυτό;

336
00:25:47,530 --> 00:25:54,050
Υπάρχουν αρκετοί διαφορετικοί τρόποι για να γράψει αυτό επίσης.

337
00:25:54,050 --> 00:26:03,290
Στην πραγματικότητα, μπορούμε να κάνουμε κάτι ακόμη - μπορούμε να κάνουμε μια one-liner.

338
00:26:03,290 --> 00:26:05,770
Μπορούμε να κάνουμε μια γραμμή επιστροφής.

339
00:26:05,770 --> 00:26:12,980
Γι 'αυτό και μπορεί πραγματικά να μειώσετε πριν επιστρέψει με τον τρόπο αυτό.

340
00:26:12,980 --> 00:26:18,320
Έτσι, τη θέση του - πριν από την s.size.

341
00:26:18,320 --> 00:26:22,060
Αυτό κάνει η γραμμή πραγματικά πυκνή.

342
00:26:22,060 --> 00:26:30,940
Σε περίπτωση που η διαφορά μεταξύ του -. Το μέγεθος και s.size--

343
00:26:30,940 --> 00:26:40,130
είναι ότι αυτό το postfix - καλούν το postfix επειδή η - μετά έρχεται η s.size--

344
00:26:40,130 --> 00:26:47,430
σημαίνει ότι s.size αξιολογείται για τους σκοπούς της εύρεση του δείκτη

345
00:26:47,430 --> 00:26:50,410
όπως είναι σήμερα όταν η γραμμή αυτή εκτελείται,

346
00:26:50,410 --> 00:26:54,290
και στη συνέχεια αυτό - συμβαίνει μετά η γραμμή εκτελείται.

347
00:26:54,290 --> 00:27:00,340
Μετά το στοιχείο στο ευρετήριο s.size είναι προσβάσιμες.

348
00:27:00,340 --> 00:27:07,260
Και αυτό δεν είναι ό, τι θέλουμε, γιατί θέλουμε η μείωση να συμβεί πρώτα.

349
00:27:07,260 --> 00:27:10,990
Othewise, θα πάμε να την πρόσβαση στο φάσμα, ουσιαστικά, εκτός ορίων.

350
00:27:10,990 --> 00:27:16,850
Εμείς πάμε για να έχουν πρόσβαση στο στοιχείο πάνω από αυτό που πραγματικά θέλουμε να έχουν πρόσβαση.

351
00:27:16,850 --> 00:27:23,840
Ναι, Σαμ; >> Είναι πιο γρήγορα ή να χρησιμοποιήσετε λιγότερη μνήμη RAM για να κάνει σε μία γραμμή ή όχι;

352
00:27:23,840 --> 00:27:29,620
[Hardison] Ειλικρινά, αυτό εξαρτάται πραγματικά.

353
00:27:29,620 --> 00:27:34,220
[Sam, ακατάληπτο] >> Ναι, αυτό εξαρτάται. Μπορείτε να κάνετε κόλπα μεταγλωττιστή

354
00:27:34,220 --> 00:27:41,580
για να πάρει το μεταγλωττιστή να αναγνωρίσει ότι, συνήθως, φαντάζομαι.

355
00:27:41,580 --> 00:27:44,840
>> Έτσι έχουμε αναφέρει λίγο για αυτά τα πράγματα βελτιστοποίησης μεταγλωττιστή

356
00:27:44,840 --> 00:27:47,400
που μπορείτε να κάνετε στην κατάρτιση,

357
00:27:47,400 --> 00:27:50,580
και αυτό είναι το είδος των πράγμα που ένας μεταγλωττιστής μπορεί να είναι σε θέση να καταλάβω,

358
00:27:50,580 --> 00:27:54,710
όπως oh, hey, ίσως μπορώ να το κάνω αυτό, όλα σε μία λειτουργία,

359
00:27:54,710 --> 00:27:59,420
σε αντίθεση με την φόρτωση του μεταβλητού μεγέθους από τη RAM,

360
00:27:59,420 --> 00:28:03,770
Μειώσης αυτό, αποθήκευση πίσω έξω, και στη συνέχεια πίσω στην φόρτωση και πάλι

361
00:28:03,770 --> 00:28:08,000
να επεξεργαστεί το υπόλοιπο αυτής της λειτουργίας.

362
00:28:08,000 --> 00:28:10,710
Αλλά συνήθως, όχι, αυτό δεν είναι το είδος του πράγματος

363
00:28:10,710 --> 00:28:20,770
που πρόκειται να κάνει το πρόγραμμά σας πολύ πιο γρήγορα.

364
00:28:20,770 --> 00:28:26,000
Οι περισσότερες ερωτήσεις σχετικά με στοίβες;

365
00:28:26,000 --> 00:28:31,360
>> Έτσι πιέζει και σκάει. Αν εσείς θέλετε να δοκιμάσετε την έκδοση χάκερ,

366
00:28:31,360 --> 00:28:33,660
ό, τι έχουμε κάνει στην έκδοση του χάκερ είναι πραγματικά φύγει

367
00:28:33,660 --> 00:28:37,670
και έκανε αυτό στοίβα αναπτύσσεται δυναμικά.

368
00:28:37,670 --> 00:28:43,190
Η πρόκληση είναι κατά κύριο λόγο εδώ στην ώθηση λειτουργία,

369
00:28:43,190 --> 00:28:48,820
να καταλάβω πώς να κάνει αυτού του πίνακα αυξάνονται

370
00:28:48,820 --> 00:28:52,450
όπως θα συνεχίσουμε να πιέζουμε όλο και περισσότερα στοιχεία σχετικά με τη στοίβα.

371
00:28:52,450 --> 00:28:56,000
Είναι πραγματικά δεν είναι πάρα πολύ πρόσθετος κωδικός.

372
00:28:56,000 --> 00:29:00,080
Ακριβώς μια κλήση για να - θα πρέπει να θυμηθείτε να πάρετε τις κλήσεις προς malloc εκεί σωστά,

373
00:29:00,080 --> 00:29:03,310
και στη συνέχεια να καταλάβω πότε θα πάμε να καλέσετε realloc.

374
00:29:03,310 --> 00:29:06,090
Αυτό είναι ένα διασκεδαστικό πρόκληση, αν σας ενδιαφέρει.

375
00:29:06,090 --> 00:29:11,550
>> Αλλά προς το παρόν, ας προχωρήσουμε και ας μιλήσουμε για ουρές.

376
00:29:11,550 --> 00:29:15,680
Κύλιση εδώ.

377
00:29:15,680 --> 00:29:19,340
Η ουρά είναι μια στενή αδελφό της στοίβας.

378
00:29:19,340 --> 00:29:25,380
Έτσι, στη στοίβα, πράγματα που είχαν τεθεί στην τελευταία

379
00:29:25,380 --> 00:29:28,810
ήταν τα πρώτα πράγματα που πρέπει να ανακτηθεί.

380
00:29:28,810 --> 00:29:33,600
Έχουμε αυτή την τελευταία in, first out, ή LIFO, παραγγελία.

381
00:29:33,600 --> 00:29:38,390
Ενώ στην ουρά, όπως θα περιμένατε από όταν στέκεται στην ουρά,

382
00:29:38,390 --> 00:29:41,980
το πρώτο πρόσωπο για να πάρει στη γραμμή, το πρώτο πράγμα που πρέπει να μπει στην ουρά,

383
00:29:41,980 --> 00:29:47,630
είναι το πρώτο πράγμα που παίρνει ανακτώνται από την ουρά.

384
00:29:47,630 --> 00:29:51,490
Ουρές επίσης συχνά χρησιμοποιείται όταν έχουμε να κάνουμε με γραφήματα,

385
00:29:51,490 --> 00:29:55,560
όπως μιλήσαμε για λίγο με στοίβες,

386
00:29:55,560 --> 00:30:00,260
και οι ουρές είναι επίσης βολικό για ένα σωρό άλλα πράγματα.

387
00:30:00,260 --> 00:30:06,180
Ένα πράγμα που έρχεται συχνά προσπαθεί να διατηρήσει, για παράδειγμα,

388
00:30:06,180 --> 00:30:12,310
μια ταξινομημένη λίστα των στοιχείων.

389
00:30:12,310 --> 00:30:17,650
Και μπορείτε να το κάνετε αυτό με μια σειρά. Μπορείτε να διατηρήσει μια ταξινομημένη λίστα των πραγμάτων σε μια σειρά,

390
00:30:17,650 --> 00:30:20,650
αλλά όπου αυτό είναι δύσκολο παίρνει τότε μπορείτε πάντα να βρείτε

391
00:30:20,650 --> 00:30:26,160
το κατάλληλο μέρος για να εισάγετε το επόμενο πράγμα.

392
00:30:26,160 --> 00:30:28,250
Έτσι, εάν έχετε μια σειρά από αριθμούς, από 1 έως 10,

393
00:30:28,250 --> 00:30:31,630
και στη συνέχεια θέλετε να επεκτείνετε ότι σε όλους τους αριθμούς από 1 έως 100,

394
00:30:31,630 --> 00:30:33,670
και παίρνετε αυτούς τους αριθμούς σε τυχαία σειρά και προσπαθεί να κρατήσει τα πάντα

395
00:30:33,670 --> 00:30:40,650
ταξινομημένο ως περνάτε, θα καταλήξετε να χρειάζεται να κάνει πολλά από τη μετατόπιση.

396
00:30:40,650 --> 00:30:43,910
Με ορισμένους τύπους των ουρών και ορισμένους τύπους των υποκείμενων δομών δεδομένων,

397
00:30:43,910 --> 00:30:46,670
μπορείτε πραγματικά να κρατήσει αρκετά απλή.

398
00:30:46,670 --> 00:30:50,640
Δεν χρειάζεται να προσθέσω κάτι και στη συνέχεια να ανακατανείμει το όλο θέμα κάθε φορά.

399
00:30:50,640 --> 00:30:56,770
Επίσης, δεν έχετε να κάνετε πολλά μετατόπιση των εσωτερικών στοιχείων γύρω.

400
00:30:56,770 --> 00:31:02,990
Όταν κοιτάζουμε σε μια ουρά, θα δείτε ότι - επίσης σε queue.c στο τμήμα κώδικα -

401
00:31:02,990 --> 00:31:10,950
το struct που σας έχουμε δώσει είναι πραγματικά παρόμοιο με το struct που σας δώσαμε για μια στοίβα.

402
00:31:10,950 --> 00:31:13,770
>> Υπάρχει μια εξαίρεση σε αυτό, και ότι μία εξαίρεση

403
00:31:13,770 --> 00:31:21,700
είναι ότι έχουμε αυτό που ονομάζεται επιπλέον ακέραιο το κεφάλι,

404
00:31:21,700 --> 00:31:28,120
και το κεφάλι είναι εδώ για την παρακολούθηση του επικεφαλής της ουράς,

405
00:31:28,120 --> 00:31:32,160
ή το πρώτο στοιχείο στην ουρά.

406
00:31:32,160 --> 00:31:37,470
Με μια στοίβα, ήμασταν σε θέση να παρακολουθεί το στοιχείο ότι ήμασταν έτοιμοι για την ανάκτηση,

407
00:31:37,470 --> 00:31:40,800
ή την κορυφή της στοίβας, χρησιμοποιώντας μόνο το μέγεθος,

408
00:31:40,800 --> 00:31:44,220
ενώ με μια ουρά, είμαστε υποχρεωμένοι να ασχοληθούμε με αντίθετα άκρα.

409
00:31:44,220 --> 00:31:49,000
Προσπαθούμε να αναστρέψει τα πράγματα για το τέλος, αλλά στη συνέχεια τα πράγματα επιστρέφουν από το μέτωπο.

410
00:31:49,000 --> 00:31:54,640
Τόσο αποτελεσματικά, με το κεφάλι, έχουμε το δείκτη στην αρχή της ουράς,

411
00:31:54,640 --> 00:31:58,920
και το μέγεθος μας δίνει το δείκτη του άκρου της ουράς

412
00:31:58,920 --> 00:32:03,730
έτσι ώστε να μπορούμε να ανακτήσετε τα πράγματα από το κεφάλι και να προσθέσετε τα πράγματα για την ουρά.

413
00:32:03,730 --> 00:32:06,890
Ότι με τη στοίβα, ήμασταν πάντα μόνο ασχολείται με την κορυφή της στοίβας.

414
00:32:06,890 --> 00:32:08,900
Δεν είχαμε ποτέ για πρόσβαση στο κάτω μέρος της στοίβας.

415
00:32:08,900 --> 00:32:12,220
Προσθέσαμε τα πράγματα μόνο στην κορυφή και πήρε τα πράγματα μακριά από την κορυφή

416
00:32:12,220 --> 00:32:17,470
έτσι δεν χρειάζεται το επιπλέον πεδίο στο εσωτερικό struct μας.

417
00:32:17,470 --> 00:32:20,590
Μήπως αυτό κάνει αίσθηση γενικά;

418
00:32:20,590 --> 00:32:27,670
Εντάξει. Ναι, Charlotte; [Charlotte, ακατάληπτο]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Αυτό είναι ένα μεγάλο θέμα, και αυτό ήταν ένα που ήρθε στη διάλεξη.

420
00:32:32,660 --> 00:32:36,290
Ίσως το περπάτημα μέσα σε λίγα παραδείγματα επεξηγούν γιατί

421
00:32:36,290 --> 00:32:41,400
δεν θέλουμε να χρησιμοποιήσει χορδές [0] ως επικεφαλής της ουράς.

422
00:32:41,400 --> 00:32:46,770
>> Φανταστείτε λοιπόν ότι έχουμε ουρά μας, θα πάμε να το ονομάσουμε ουρά.

423
00:32:46,770 --> 00:32:49,210
Στην αρχή, όταν έχουμε αρχικοποιείται απλά,

424
00:32:49,210 --> 00:32:53,330
όταν έχουμε δηλώσει ακριβώς, δεν έχουμε προετοιμαστεί τίποτα.

425
00:32:53,330 --> 00:32:56,790
Είναι όλα σκουπίδια. Έτσι, φυσικά, θέλουμε να είμαστε σίγουροι ότι η προετοιμασία

426
00:32:56,790 --> 00:33:00,950
τόσο το μέγεθος και τα πεδία της κεφαλής να είναι μηδέν, κάτι το λογικό.

427
00:33:00,950 --> 00:33:05,770
Θα μπορούσαμε, επίσης, να προχωρήσει και να null τα στοιχεία στην ουρά μας.

428
00:33:05,770 --> 00:33:09,930
Και για να κάνουν αυτό το κατάλληλο διάγραμμα, παρατηρούμε ότι τώρα ουρά μας μπορεί να κρατήσει μόνο τρία στοιχεία?

429
00:33:09,930 --> 00:33:13,150
λαμβάνοντας υπόψη ότι η στοίβα μας θα μπορούσε να κρατήσει τέσσερα, ουρά μας μπορεί να κρατήσει μόνο τρεις.

430
00:33:13,150 --> 00:33:18,680
Και αυτό είναι μόνο για να κάνει την τακτοποίηση διάγραμμα.

431
00:33:18,680 --> 00:33:26,150
Το πρώτο πράγμα που συμβαίνει εδώ είναι ότι enqueue το string "γεια".

432
00:33:26,150 --> 00:33:30,380
Και ακριβώς όπως κάναμε και με τη στοίβα, τίποτα τρομερά διαφορετικό εδώ,

433
00:33:30,380 --> 00:33:39,230
ρίχνουμε το string με χορδές σε [0] και αυξήσετε το μέγεθος μας 1.

434
00:33:39,230 --> 00:33:42,720
Εμείς enqueue "αντίο", παίρνει θέσει σε.

435
00:33:42,720 --> 00:33:45,870
Έτσι, αυτό μοιάζει με μια στοίβα για το μεγαλύτερο μέρος.

436
00:33:45,870 --> 00:33:53,230
Ξεκινήσαμε, εδώ νέο στοιχείο, νέο στοιχείο, το μέγεθος συνεχίζει να ανεβαίνει.

437
00:33:53,230 --> 00:33:56,330
Τι θα συμβεί σε αυτό το σημείο, όταν θέλουμε να dequeue κάτι;

438
00:33:56,330 --> 00:34:01,280
Όταν θέλουμε να dequeue, το οποίο είναι το στοιχείο που θέλουμε να dequeue;

439
00:34:01,280 --> 00:34:04,110
[Βασίλης] Χορδές [0]. >> Zero. Ακριβώς δεξιά, ο Βασίλειος.

440
00:34:04,110 --> 00:34:10,960
Θέλουμε να απαλλαγούμε από την πρώτη σειρά, αυτή τη φορά, "γεια".

441
00:34:10,960 --> 00:34:13,170
Έτσι, ό, τι ήταν το άλλο πράγμα που άλλαξε;

442
00:34:13,170 --> 00:34:17,010
Προσέξτε όταν έσκασε κάτι από την στοίβα, αλλάξαμε μόνο το μέγεθος,

443
00:34:17,010 --> 00:34:22,080
αλλά εδώ, έχουμε ένα ζευγάρι από τα πράγματα που αλλάζουν.

444
00:34:22,080 --> 00:34:27,440
Δεν είναι μόνο η αλλαγή μεγέθους, αλλά οι αλλαγές κεφάλι.

445
00:34:27,440 --> 00:34:31,020
Αυτό πηγαίνει πίσω στο σημείο του Σαρλόττα νωρίτερα:

446
00:34:31,020 --> 00:34:38,699
γιατί έχουμε αυτό το κεφάλι, καθώς;

447
00:34:38,699 --> 00:34:42,110
Έχει νόημα, τώρα Charlotte; Είδος >>.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Είδος; Έτσι, ό, τι συνέβη όταν dequeued;

449
00:34:47,500 --> 00:34:54,340
Τι έκανε ο επικεφαλής γίνει αυτό τώρα είναι ενδιαφέρον;

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Ω, γιατί άλλαξε - εντάξει. Μάλιστα.

451
00:34:56,449 --> 00:35:02,090
Επειδή το κεφάλι - όπου το κεφάλι είναι στραμμένο στις αλλαγές σε σχέση με την τοποθεσία.

452
00:35:02,090 --> 00:35:07,200
Δεν είναι πλέον πάντα το μηδέν ένα δείκτη. >> Ναι, ακριβώς.

453
00:35:07,200 --> 00:35:17,660
Αυτό που συνέβη ήταν αν dequeueing το υψηλό στοιχείο

454
00:35:17,660 --> 00:35:20,590
έγινε και δεν είχαμε αυτό το πεδίο κεφάλι

455
00:35:20,590 --> 00:35:26,880
γιατί ζητούσαν πάντα αυτό το κορδόνι σε 0 δείκτης ο επικεφαλής της ουράς μας,

456
00:35:26,880 --> 00:35:30,170
τότε θα είχαμε να μετατοπίσει το υπόλοιπο της ουράς προς τα κάτω.

457
00:35:30,170 --> 00:35:36,010
Εμείς θα πρέπει να στρέψουμε "αντίο" από χορδές από [1] με τις χορδές [0].

458
00:35:36,010 --> 00:35:38,760
Και χορδές [2] κάτω από τις χορδές [1].

459
00:35:38,760 --> 00:35:43,050
Και εμείς θα πρέπει να το κάνετε αυτό για ολόκληρη την λίστα των στοιχείων,

460
00:35:43,050 --> 00:35:45,110
η όλη διάταξη των στοιχείων.

461
00:35:45,110 --> 00:35:50,490
Και όταν κάνουμε αυτό με μια σειρά, που παίρνει πραγματικά δαπανηρή.

462
00:35:50,490 --> 00:35:53,340
Μέχρι εδώ, δεν είναι μια μεγάλη υπόθεση. Έχουμε μόλις τρία στοιχεία σε σειρά μας.

463
00:35:53,340 --> 00:35:57,230
Αλλά αν είχαμε μια ουρά από χίλια στοιχεία ή ένα εκατομμύριο στοιχεία,

464
00:35:57,230 --> 00:36:00,060
και στη συνέχεια, ξαφνικά, θα αρχίσουμε να κάνουμε ένα μάτσο dequeue καλεί όλους σε έναν βρόχο,

465
00:36:00,060 --> 00:36:03,930
τα πράγματα είναι πραγματικά πρόκειται να επιβραδυνθεί, καθώς μετατοπίζει τα πάντα συνεχώς.

466
00:36:03,930 --> 00:36:07,320
Ξέρετε, μετατόπιση κατά 1, μετατόπιση κατά 1, μετατόπιση κατά 1, μετατόπιση από 1.

467
00:36:07,320 --> 00:36:13,650
Αντ 'αυτού, χρησιμοποιούν αυτό το κεφάλι, θα το ονομάσουμε ένα "δείκτη" ακόμα κι αν δεν είναι πραγματικά ένας δείκτης

468
00:36:13,650 --> 00:36:16,430
με την αυστηρή έννοια του όρου? δεν είναι ένα είδος δείκτη.

469
00:36:16,430 --> 00:36:19,410
Δεν είναι ένα int * ή char * ή κάτι τέτοιο.

470
00:36:19,410 --> 00:36:28,930
Αλλά αυτό είναι που δείχνει ή που δείχνει το κεφάλι του ουρά μας. Ναι;

471
00:36:28,930 --> 00:36:38,800
>> [Φοιτητής] Πώς dequeue ξέρει μόνο να σκάσει από ό, τι είναι στο κεφάλι;

472
00:36:38,800 --> 00:36:43,620
[Hardison] Πώς dequeue ξέρουν πώς να σκάσει από ό, τι είναι στο κεφάλι; Δικαίωμα >>, ναι.

473
00:36:43,620 --> 00:36:49,050
>> Τι ψάχνει σε ό, τι ακριβώς είναι το πεδίο της κεφαλής έχει οριστεί.

474
00:36:49,050 --> 00:36:52,710
Έτσι, σε αυτή την πρώτη περίπτωση, αν κοιτάξουμε δεξιά εδώ,

475
00:36:52,710 --> 00:36:55,690
κεφάλι μας είναι 0, 0 δείκτη. Δικαίωμα >>.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Γι 'αυτό ακριβώς λέει εντάξει, καλά, το στοιχείο στο δείκτη 0, η σειρά "γεια",

477
00:37:00,500 --> 00:37:03,050
είναι το στοιχείο στην κεφαλή της ουράς μας.

478
00:37:03,050 --> 00:37:05,570
Έτσι θα πάμε να dequeue αυτόν τον τύπο.

479
00:37:05,570 --> 00:37:09,800
Και αυτό θα είναι το στοιχείο που παίρνει επιστρέφεται στον καλούντα.

480
00:37:09,800 --> 00:37:14,540
Ναι, Saad; >> Έτσι, το κεφάλι θέτει ουσιαστικά το - όπου θα πάμε με τον δείκτη αυτό;

481
00:37:14,540 --> 00:37:17,750
Αυτό είναι η αρχή του; Ναι >>. Εντάξει >>.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Αυτό είναι να γίνει το νέο ξεκίνημα για την παράταξη μας.

483
00:37:22,900 --> 00:37:28,930
Έτσι, όταν dequeue κάτι, το μόνο που έχετε να κάνετε είναι να αποκτήσετε πρόσβαση στο στοιχείο στο δείκτη q.head,

484
00:37:28,930 --> 00:37:32,240
και ότι θα είναι το στοιχείο που θέλετε να dequeue.

485
00:37:32,240 --> 00:37:34,930
Μπορείτε επίσης να μειώσετε το μέγεθος.

486
00:37:34,930 --> 00:37:39,430
Θα δούμε σε λίγο όπου τα πράγματα παίρνουν λίγο δύσκολο με αυτό.

487
00:37:39,430 --> 00:37:46,520
Εμείς dequeue, και τώρα, αν Τοποθέτηση στην ουρά και πάλι,

488
00:37:46,520 --> 00:37:51,300
πού Τοποθέτηση στην ουρά;

489
00:37:51,300 --> 00:37:55,000
Σε περίπτωση που δεν το επόμενο στοιχείο που πάει στην ουρά μας;

490
00:37:55,000 --> 00:37:57,980
Πείτε θέλουμε να enqueue το string "CS".

491
00:37:57,980 --> 00:38:02,240
Σε ποια δείκτης θα πάει; [Φοιτητές] Χορδές [2]. Δύο >>.

492
00:38:02,240 --> 00:38:04,980
Γιατί 2 και όχι 0;

493
00:38:04,980 --> 00:38:13,570
[Βασίλης] Επειδή τώρα το κεφάλι είναι 1, έτσι ώστε να είναι σαν την αρχή της λίστας;

494
00:38:13,570 --> 00:38:21,220
[Hardison] Δεξιά. Και τι σημαίνει το τέλος της λίστας;

495
00:38:21,220 --> 00:38:23,290
Αυτό ήταν που χρησιμοποιείτε για να δηλώσει το τέλος της ουράς μας;

496
00:38:23,290 --> 00:38:25,970
Το κεφάλι είναι ο επικεφαλής της ουράς μας, η αρχή της ουράς μας.

497
00:38:25,970 --> 00:38:29,530
Ποιο είναι το τέλος της ουράς μας; [Φοιτητές] Μέγεθος. Μέγεθος >>, ακριβώς.

498
00:38:29,530 --> 00:38:36,360
Έτσι, τα νέα στοιχεία μας πάνε σε σε μέγεθος, και τα στοιχεία που παίρνουμε από βγει στο κεφάλι.

499
00:38:36,360 --> 00:38:45,390
Όταν enqueue το επόμενο στοιχείο, είμαστε σε θέση να σε μέγεθος.

500
00:38:45,390 --> 00:38:48,530
[Φοιτητικό] Πριν βάλετε σε ότι και αν, διαστάσεων ήταν το 1, έτσι δεν είναι;

501
00:38:48,530 --> 00:38:55,690
[Hardison] Δεξιά. Έτσι, δεν είναι αρκετά σε μέγεθος. + Μέγεθος, όχι +1, αλλά το κεφάλι +.

502
00:38:55,690 --> 00:38:59,990
Επειδή τα πάντα μετατοπιστεί από το ποσό κεφάλι.

503
00:38:59,990 --> 00:39:14,270
Έτσι, εδώ, τώρα έχουμε μια ουρά του μεγέθους 1 που ξεκινά σε δείκτη 1.

504
00:39:14,270 --> 00:39:20,730
Η ουρά είναι δείκτης 2. Ναι;

505
00:39:20,730 --> 00:39:25,780
>> [Φοιτητικό] Τι συμβαίνει όταν dequeue χορδές [0], και οι χορδές »στη μνήμη υποδοχές

506
00:39:25,780 --> 00:39:29,420
απλά να αδειάσει, ουσιαστικά, ή απλά να ξεχάσει;

507
00:39:29,420 --> 00:39:34,700
[Hardison] Ναι. Με αυτή την έννοια, είμαστε απλά ξέχασέ το.

508
00:39:34,700 --> 00:39:42,640
Αν είχαμε την αποθήκευση αντιγράφων για τους -

509
00:39:42,640 --> 00:39:46,310
πολλές δομές δεδομένων θα αποθηκεύσει συχνά δικά τους αντίγραφα των στοιχείων

510
00:39:46,310 --> 00:39:51,760
έτσι ώστε το πρόσωπο που διαχειρίζεται τη δομή των δεδομένων δεν χρειάζεται να ανησυχείτε

511
00:39:51,760 --> 00:39:53,650
σχετικά με το πού όλοι αυτοί οι δείκτες πρόκειται.

512
00:39:53,650 --> 00:39:56,000
Η δομή δεδομένων που κρατά για να τα πάντα, για να έχει όλα τα αντίγραφα,

513
00:39:56,000 --> 00:39:59,580
για να βεβαιωθείτε ότι τα πάντα επιμένει κατάλληλα.

514
00:39:59,580 --> 00:40:03,140
Ωστόσο, στην περίπτωση αυτή, αυτές οι δομές δεδομένων μόνο, για λόγους απλότητας,

515
00:40:03,140 --> 00:40:05,580
δεν κάνουν τίποτα αντίγραφα του ότι είμαστε αποθήκευση σε αυτά.

516
00:40:05,580 --> 00:40:08,630
[Φοιτητικό] Έτσι είναι αυτή η συνεχής σειρά από -; Ναι >>.

517
00:40:08,630 --> 00:40:14,350
Αν κοιτάξουμε πίσω σε αυτό που ήταν ο ορισμός της δομής αυτής, είναι.

518
00:40:14,350 --> 00:40:19,110
Είναι απλά μια τυπική σειρά, όπως έχετε δει,

519
00:40:19,110 --> 00:40:24,280
μια σειρά από char * s.

520
00:40:24,280 --> 00:40:26,340
Μήπως ότι -; >> Ναι, απλά αναρωτιόμουν

521
00:40:26,340 --> 00:40:29,130
αν τελικά θα ξεμείνει από μνήμη, ως ένα βαθμό,

522
00:40:29,130 --> 00:40:32,330
αν έχετε όλα αυτά τα κενά σημεία σε σειρά σας;

523
00:40:32,330 --> 00:40:36,390
[Hardison] Ναι, αυτό είναι ένα καλό σημείο.

524
00:40:36,390 --> 00:40:41,530
>> Αν κοιτάξουμε τι έχει συμβεί τώρα σε αυτό το σημείο,

525
00:40:41,530 --> 00:40:46,350
έχουμε γεμίσει ουρά μας, μοιάζει.

526
00:40:46,350 --> 00:40:50,390
Αλλά δεν έχουμε πραγματικά γεμίσει ουρά μας

527
00:40:50,390 --> 00:40:57,710
επειδή έχουμε μια ουρά που είναι το μέγεθος 2, αλλά αρχίζει στο δείκτη 1,

528
00:40:57,710 --> 00:41:02,160
επειδή αυτό είναι όπου ο δείκτης είναι το κεφάλι μας.

529
00:41:02,160 --> 00:41:08,400
Όπως είπατε, ότι το στοιχείο στο χορδές [0], στο δείκτη 0, δεν είναι πραγματικά εκεί.

530
00:41:08,400 --> 00:41:10,450
Δεν είναι στην ουρά μας πια.

531
00:41:10,450 --> 00:41:16,460
Εμείς απλά δεν μπαίνουν στον κόπο να πάτε και να αντικαταστήσετε όταν το dequeued.

532
00:41:16,460 --> 00:41:18,700
Έτσι ακόμα κι αν αυτό μοιάζει έχουμε ξεμείνει από μνήμη, έχουμε πραγματικά δεν έχουν.

533
00:41:18,700 --> 00:41:23,270
Αυτό το σημείο είναι διαθέσιμα για μας να χρησιμοποιήσει.

534
00:41:23,270 --> 00:41:29,310
Η κατάλληλη συμπεριφορά, αν ήταν να προσπαθήσουμε και το πρώτο dequeue κάτι

535
00:41:29,310 --> 00:41:34,420
όπως το "αντίο", που θα σκάσει αντίο μακριά.

536
00:41:34,420 --> 00:41:38,460
Τώρα ουρά μας ξεκινά στο δείκτη 2 και έχει μέγεθος 1.

537
00:41:38,460 --> 00:41:42,240
Και τώρα αν προσπαθήσουμε και πάλι enqueue κάτι, ας πούμε 50,

538
00:41:42,240 --> 00:41:47,880
50 θα πρέπει να πάνε σε αυτό το σημείο στο δείκτη 0

539
00:41:47,880 --> 00:41:51,270
γιατί είναι ακόμα διαθέσιμες για μας. Ναι, Saad;

540
00:41:51,270 --> 00:41:53,630
[Saad] Μήπως αυτό γίνεται αυτόματα;

541
00:41:53,630 --> 00:41:56,150
[Hardison] Αυτό δεν συμβαίνει σχεδόν αυτόματα. Θα πρέπει να κάνετε τα μαθηματικά

542
00:41:56,150 --> 00:42:00,380
να την κάνουμε να λειτουργήσει, αλλά ουσιαστικά αυτό που έχουμε κάνει είναι ότι έχουμε μόλις τυλιγμένο γύρω.

543
00:42:00,380 --> 00:42:04,070
[Saad] Και είναι εντάξει, αν αυτό έχει μια τρύπα στη μέση του;

544
00:42:04,070 --> 00:42:08,720
[Hardison] είναι αν μπορούμε να κάνουμε τα μαθηματικά λειτουργούν σωστά.

545
00:42:08,720 --> 00:42:15,470
>> Και αποδεικνύεται ότι αυτό δεν είναι πραγματικά ότι σκληρά για να κάνει με το χειριστή mod.

546
00:42:15,470 --> 00:42:20,040
Έτσι ακριβώς όπως κάναμε με Καίσαρα και το υλικό κρυπτογράφησης,

547
00:42:20,040 --> 00:42:25,190
χρησιμοποιώντας mod, μπορούμε να πάρουμε τα πράγματα για να τυλίξει γύρω και συνεχίζω

548
00:42:25,190 --> 00:42:28,090
γύρω και γύρω γύρω και με την ουρά μας,

549
00:42:28,090 --> 00:42:32,180
κρατώντας ότι ο δείκτης κινείται γύρω από το κεφάλι.

550
00:42:32,180 --> 00:42:38,840
Παρατηρήστε ότι το μέγεθος είναι πάντα σέβεται τον αριθμό των πραγματικά στοιχεία κατά την ουρά.

551
00:42:38,840 --> 00:42:43,110
Και είναι ακριβώς ο δείκτης της κεφαλής που κρατά το ποδήλατο μέσα.

552
00:42:43,110 --> 00:42:49,660
Αν κοιτάξουμε τι συνέβη εδώ, αν πάμε πίσω στην αρχή,

553
00:42:49,660 --> 00:42:55,020
και μπορείτε απλά να παρακολουθήσετε τι συμβαίνει στο κεφάλι

554
00:42:55,020 --> 00:42:58,240
Τοποθέτηση στην ουρά όταν κάτι, δεν έγινε τίποτα στο κεφάλι.

555
00:42:58,240 --> 00:43:00,970
Όταν enqueued κάτι άλλο, δεν έγινε τίποτα στο κεφάλι.

556
00:43:00,970 --> 00:43:04,130
Σύντομα όπως dequeued κάτι, το κεφάλι ανεβαίνει κατά ένα.

557
00:43:04,130 --> 00:43:06,600
Εμείς enqueued κάτι, δεν συμβαίνει τίποτα στο κεφάλι.

558
00:43:06,600 --> 00:43:11,060
Όταν dequeue κάτι, ξαφνικά το κεφάλι παίρνει αυξάνεται.

559
00:43:11,060 --> 00:43:14,660
Όταν enqueue κάτι, δεν συμβαίνει τίποτα στο κεφάλι.

560
00:43:14,660 --> 00:43:20,240
>> Τι θα συμβεί σε αυτό το σημείο, αν επρόκειτο να dequeue κάτι πάλι;

561
00:43:20,240 --> 00:43:23,240
Οποιεσδήποτε σκέψεις; Τι θα συμβεί στο κεφάλι;

562
00:43:23,240 --> 00:43:27,190
Τι πρέπει να συμβεί για να το κεφάλι

563
00:43:27,190 --> 00:43:32,990
αν ήταν να dequeue κάτι άλλο;

564
00:43:32,990 --> 00:43:35,400
Το κεφάλι είναι τώρα στο δείκτη 2,

565
00:43:35,400 --> 00:43:38,920
πράγμα που σημαίνει ότι η κεφαλή της ουράς είναι χορδές [2].

566
00:43:38,920 --> 00:43:44,280
[Φοιτητικό] η οποία επιστρέφει 0; >> Θα πρέπει να επανέλθει στο 0. Θα πρέπει να τυλίξετε γύρω από πίσω, ακριβώς.

567
00:43:44,280 --> 00:43:48,440
Μέχρι τώρα, κάθε φορά που καλείται dequeue, έχουμε την προσθήκη ενός στο κεφάλι,

568
00:43:48,440 --> 00:43:50,960
προσθέστε ένα στο κεφάλι, προσθέστε ένα στο κεφάλι, προσθέστε ένα στο κεφάλι.

569
00:43:50,960 --> 00:43:58,400
Μόλις ότι ο δείκτης παίρνει κεφάλι στο τελευταίο δείκτη σε σειρά μας,

570
00:43:58,400 --> 00:44:05,650
τότε θα πρέπει να το τυλίξετε γύρω από πίσω στην αρχή, πηγαίνετε πίσω στο 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Τι καθορίζει την ικανότητα της ουράς σε μια στοίβα;

572
00:44:09,900 --> 00:44:13,120
[Hardison] Σε αυτήν την περίπτωση, έχουμε μόλις χρησιμοποιώντας ένα # ορίζεται σταθερή. Εντάξει >>.

573
00:44:13,120 --> 00:44:19,590
[Hardison] Στην πραγματική. Αρχείο c, μπορείτε να πάτε σε απορρίματα και με το λίγο

574
00:44:19,590 --> 00:44:21,710
και κάνει τόσο μεγάλη ή τόσο λίγα όπως θέλετε.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Έτσι, όταν θέλετε να κάνετε αυτό μια ουρά, πώς κάνετε τον υπολογιστή γνωρίζουν

576
00:44:25,310 --> 00:44:29,120
πόσο μεγάλο θέλετε η στοίβα να είναι;

577
00:44:29,120 --> 00:44:31,700
[Hardison] Αυτό είναι ένα μεγάλο ερώτημα.

578
00:44:31,700 --> 00:44:34,800
Υπάρχουν δύο τρόποι. Ο ένας είναι να καθορίσει ακριβώς μπροστά

579
00:44:34,800 --> 00:44:42,050
και λένε ότι αυτό πρόκειται να είναι μια ουρά που έχει 4 στοιχεία ή 50 ή 10.000 στοιχεία.

580
00:44:42,050 --> 00:44:45,430
Ο άλλος τρόπος είναι να κάνουμε ό, τι οι λαοί έκδοση χάκερ κάνουν

581
00:44:45,430 --> 00:44:52,310
και να δημιουργήσει λειτουργίες να έχουν ουρά σας αναπτύσσεται δυναμικά, όπως να πάρει περισσότερα πράγματα μέσα προστίθενται

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Έτσι, για να πάει με την πρώτη επιλογή, ποια σύνταξη χρησιμοποιείτε

583
00:44:54,740 --> 00:44:57,830
να πει το πρόγραμμα ποιο είναι το μέγεθος της ουράς;

584
00:44:57,830 --> 00:45:04,780
[Hardison] Αχ. Ας βγούμε από αυτό.

585
00:45:04,780 --> 00:45:12,650
Είμαι ακόμα σε stack.c εδώ, οπότε είμαι απλώς πρόκειται να μετακινηθείτε προς τα πάνω στην κορυφή εδώ.

586
00:45:12,650 --> 00:45:17,920
Μπορείτε να δείτε αυτό το δικαίωμα εδώ; Αυτό είναι το # define χωρητικότητα 10.

587
00:45:17,920 --> 00:45:24,600
Και αυτό είναι σχεδόν η ίδια ακριβώς σύνταξη που έχουμε για την ουρά.

588
00:45:24,600 --> 00:45:28,390
Εκτός ουρά, έχουμε αυτό το επιπλέον πεδίο struct εδώ.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Ω, νόμιζα ότι η ικανότητα σημαίνει την ικανότητα για τη σειρά.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Αχ. >> Αυτό είναι το μέγιστο μήκος της λέξης. >> Το 'πιασα.

591
00:45:36,770 --> 00:45:41,180
Ναι. Η χωρητικότητα εδώ - αυτό είναι ένα μεγάλο σημείο.

592
00:45:41,180 --> 00:45:44,000
Και αυτό είναι κάτι που είναι δύσκολο

593
00:45:44,000 --> 00:45:49,480
διότι αυτό που έχουμε δηλώσει εδώ είναι μια σειρά από char * s.

594
00:45:49,480 --> 00:45:52,770
Μια σειρά από δείκτες.

595
00:45:52,770 --> 00:45:56,690
Αυτή είναι μια σειρά από χαρακτήρες.

596
00:45:56,690 --> 00:46:01,690
Αυτό είναι ίσως ό, τι έχετε δει όταν έχετε δηλώνοντας προσκρουστήρες σας για αυτό το αρχείο I / O,

597
00:46:01,690 --> 00:46:06,840
όταν έχετε δημιουργήσει χορδές χέρι στη στοίβα.

598
00:46:06,840 --> 00:46:09,090
Ωστόσο, αυτό που έχουμε εδώ είναι μια σειρά από char * s.

599
00:46:09,090 --> 00:46:13,400
Γι 'αυτό είναι μια σειρά από δείκτες.

600
00:46:13,400 --> 00:46:18,350
Στην πραγματικότητα, αν μεγεθύνετε και να κοιτάξουμε τι συμβαίνει εδώ

601
00:46:18,350 --> 00:46:23,140
στην παρουσίαση, θα δείτε ότι τα πραγματικά στοιχεία, τα στοιχεία του χαρακτήρα

602
00:46:23,140 --> 00:46:26,180
δεν αποθηκεύεται μέσα στη συστοιχία ίδια.

603
00:46:26,180 --> 00:46:42,690
Τι είναι αποθηκευμένο μέσα στον πίνακα μας εδώ είναι δείκτες για τα δεδομένα χαρακτήρων.

604
00:46:42,690 --> 00:46:52,560
Εντάξει. Έτσι, έχουμε δει πώς το μέγεθος της ουράς είναι ακριβώς όπως με τη στοίβα,

605
00:46:52,560 --> 00:46:58,670
το μέγεθος τηρεί πάντα τον αριθμό των στοιχείων επί του παρόντος στην ουρά.

606
00:46:58,670 --> 00:47:02,720
Μετά την υποβολή της 2 enqueues, το μέγεθος είναι 2.

607
00:47:02,720 --> 00:47:07,110
Μετά από να κάνει ένα dequeue το μέγεθος είναι τώρα 1.

608
00:47:07,110 --> 00:47:09,330
Μετά από να κάνει ένα άλλο enqueue το μέγεθος είναι πίσω μέχρι και 2.

609
00:47:09,330 --> 00:47:12,340
Έτσι, το μέγεθος σίγουρα σέβεται τον αριθμό των στοιχείων στην ουρά,

610
00:47:12,340 --> 00:47:15,580
και στη συνέχεια το κεφάλι κρατά μόνο το ποδήλατο.

611
00:47:15,580 --> 00:47:20,210
Στη συνέχεια, από το 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
Και κάθε φορά που λέμε dequeue, ο δείκτης παίρνει κεφάλι αυξάνεται στο επόμενο δείκτη.

613
00:47:25,620 --> 00:47:29,930
Και αν το κεφάλι είναι για να πάει πάνω, αυτό γυρίζει πίσω γύρω στο 0.

614
00:47:29,930 --> 00:47:34,870
Έτσι, με αυτό, μπορούμε να γράψουμε την dequeue λειτουργία.

615
00:47:34,870 --> 00:47:40,200
Και θα πάμε να εγκαταλείψουν τη λειτουργία enqueue για σας παιδιά να εφαρμόσει αντ 'αυτού.

616
00:47:40,200 --> 00:47:45,880
>> Όταν έχουμε ένα στοιχείο dequeue έξω από ουρά μας,

617
00:47:45,880 --> 00:47:55,490
ποιο ήταν το πρώτο πράγμα που έκανε ο Daniel όταν ξεκινήσαμε να γράφουμε το αναδυόμενο λειτουργία για σωρούς;

618
00:47:55,490 --> 00:48:00,490
Επιτρέψτε μου να ακούσω από κάποιον που δεν έχει μιλήσει ακόμη.

619
00:48:00,490 --> 00:48:06,710
Ας δούμε, Saad, θυμάστε τι έκανε ο Daniel ως το πρώτο πράγμα όταν έγραψε ποπ;

620
00:48:06,710 --> 00:48:08,860
[Saad] Υπήρχε, ήταν - >> Έχει δοκιμαστεί για κάτι.

621
00:48:08,860 --> 00:48:12,140
[Saad] Αν το μέγεθος είναι μεγαλύτερο από 0. Ακριβώς >>.

622
00:48:12,140 --> 00:48:14,390
Και τι ήταν αυτό για τον έλεγχο;

623
00:48:14,390 --> 00:48:19,090
[Saad] Αυτό ήταν δοκιμή για να δούμε αν υπάρχει κάτι στο εσωτερικό του πίνακα.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Ναι. Ακριβώς. Έτσι δεν μπορείτε να ποπ τίποτα έξω από τη στοίβα και αν είναι άδειο.

625
00:48:23,210 --> 00:48:26,510
Ομοίως, δεν μπορείτε να dequeue τίποτα από μια ουρά αν είναι άδειο.

626
00:48:26,510 --> 00:48:30,420
Ποιο είναι το πρώτο πράγμα που πρέπει να κάνουμε σε λειτουργία dequeue μας εδώ, νομίζεις;

627
00:48:30,420 --> 00:48:33,860
[Saad] Αν το μέγεθος είναι μεγαλύτερο από 0; Ναι >>.

628
00:48:33,860 --> 00:48:37,710
Σε αυτή την περίπτωση, έχω δοκιμαστεί στην πραγματικότητα απλώς για να δούμε αν είναι 0.

629
00:48:37,710 --> 00:48:42,240
Αν είναι 0, μπορούμε να επιστρέψουμε μηδενική.

630
00:48:42,240 --> 00:48:45,280
Αλλά ακριβώς ίδια λογική.

631
00:48:45,280 --> 00:48:49,110
Και ας συνεχίσουμε με αυτό.

632
00:48:49,110 --> 00:48:54,600
Εάν το μέγεθος δεν είναι 0, όπου είναι το στοιχείο που θέλουμε να dequeue;

633
00:48:54,600 --> 00:48:58,550
[Saad] Στο κεφάλι; Ακριβώς >>.

634
00:48:58,550 --> 00:49:01,720
Μπορούμε απλά τραβήξτε προς τα έξω το πρώτο στοιχείο στην ουρά μας

635
00:49:01,720 --> 00:49:07,040
από την πρόσβαση του στοιχείου στο κεφάλι.

636
00:49:07,040 --> 00:49:14,630
Τίποτα τρελό.

637
00:49:14,630 --> 00:49:19,620
Μετά από αυτό, τι πρέπει να κάνουμε; Τι πρέπει να γίνει;

638
00:49:19,620 --> 00:49:23,740
Ποιο ήταν το άλλο πράγμα που μιλήσαμε για το dequeue;

639
00:49:23,740 --> 00:49:28,130
Δύο πράγματα πρέπει να συμβεί, επειδή ουρά μας έχει αλλάξει.

640
00:49:28,130 --> 00:49:35,640
[Δανιήλ] Μειώστε το μέγεθος. >> Πρέπει να μειώσουμε το μέγεθος, και να αυξήσει το κεφάλι; Ακριβώς.

641
00:49:35,640 --> 00:49:40,600
Για να αυξήσετε το κεφάλι, δεν μπορούμε απλά να αυξήσει τυφλά το κεφάλι, θυμάται.

642
00:49:40,600 --> 00:49:45,080
Εμείς απλά δεν μπορούμε να κάνουμε queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Πρέπει να περιλαμβάνουν επίσης αυτό το mod από την ικανότητα.

644
00:49:51,630 --> 00:49:54,740
Και γιατί mod από την ικανότητα, Στέλλα;

645
00:49:54,740 --> 00:49:58,680
[Στέλλα] Γιατί πρέπει να τυλίξετε γύρω. Ακριβώς >>.

646
00:49:58,680 --> 00:50:04,750
Εμείς mod από την ικανότητα, διότι πρέπει να γυρίσει πίσω γύρω στο 0.

647
00:50:04,750 --> 00:50:07,400
Μέχρι τώρα, σε αυτό το σημείο, μπορούμε να κάνουμε ό, τι είπε ο Ντάνιελ.

648
00:50:07,400 --> 00:50:12,700
Μπορούμε να ελαττώσει το μέγεθος.

649
00:50:12,700 --> 00:50:29,170
Και τότε μπορούμε να επιστρέψει μόνο το στοιχείο που ήταν στην κορυφή της ουράς.

650
00:50:29,170 --> 00:50:34,000
Φαίνεται ότι το είδος του οζώδης από την πρώτη. Μπορεί να έχετε μια ερώτηση. Συγνώμη;

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Γιατί η πρώτη στην κορυφή της ουράς; Πού πηγαίνουν ότι;

652
00:50:37,260 --> 00:50:42,480
[Hardison] Προέρχεται από την τέταρτη γραμμή από τον πυθμένα.

653
00:50:42,480 --> 00:50:46,060
Αφού ελέγξετε για να βεβαιωθείτε ότι η ουρά μας δεν είναι άδειο,

654
00:50:46,060 --> 00:50:54,100
έχουμε βγάλει char * Αρχικά, τραβήξτε προς τα έξω το στοιχείο που κάθεται στο κεφάλι του δείκτη

655
00:50:54,100 --> 00:50:58,680
από σειρά μας, του χορδές σειρά μας, >> και ότι η πρώτη κλήση;

656
00:50:58,680 --> 00:51:04,500
[Hardison] Και εμείς ονομάζουμε πρώτα. Ναι.

657
00:51:04,500 --> 00:51:09,850
Ακριβώς για να δώσει συνέχεια σε αυτό, γιατί νομίζετε ότι θα έπρεπε να το κάνουμε αυτό;

658
00:51:09,850 --> 00:51:18,270
[Sam] Κάθε πρώτο επιστρέφει μόλις q.strings [q.head]; Ναι >>.

659
00:51:18,270 --> 00:51:23,830
>> Γιατί κάνουμε αυτή την αλλαγή της q.head με τη λειτουργία mod,

660
00:51:23,830 --> 00:51:27,810
και δεν υπάρχει τρόπος να το κάνουμε αυτό μέσα σε αγωγό επιστροφής επίσης.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Ακριβώς. Είστε σωστοί. Sam είναι απόλυτα σωστοί.

662
00:51:31,640 --> 00:51:36,800
Ο λόγος για τον οποίο έπρεπε να βγάλει το πρώτο στοιχείο στην ουρά μας και να το αποθηκεύσετε σε μια μεταβλητή

663
00:51:36,800 --> 00:51:43,030
οφείλεται στο γεγονός ότι αυτή τη γραμμή, όπου είχαμε μόλις q.head,

664
00:51:43,030 --> 00:51:47,030
υπάρχει ο χειριστής mod εκεί δεν είναι κάτι που μπορούμε να κάνουμε

665
00:51:47,030 --> 00:51:51,230
και έχουν τεθεί σε ισχύ στο κεφάλι χωρίς - σε μία γραμμή.

666
00:51:51,230 --> 00:51:54,480
Γι 'αυτό και πραγματικά πρέπει να βγάλει το πρώτο στοιχείο, και στη συνέχεια ρυθμίστε το κεφάλι,

667
00:51:54,480 --> 00:52:00,430
προσαρμόσετε το μέγεθος, και στη συνέχεια να επιστρέψετε το στοιχείο που έβγαλε.

668
00:52:00,430 --> 00:52:02,680
Και αυτό είναι κάτι που θα δούμε αργότερα καταλήξουμε με

669
00:52:02,680 --> 00:52:04,920
συνδεδεμένες λίστες, καθώς παίζουν μαζί τους.

670
00:52:04,920 --> 00:52:08,410
Συχνά, όταν είστε απελευθέρωση ή τη διάθεση των συνδεδεμένες λίστες

671
00:52:08,410 --> 00:52:13,500
θα πρέπει να θυμάστε το επόμενο στοιχείο, το επόμενο δείκτη του συνδεδεμένη λίστα

672
00:52:13,500 --> 00:52:16,330
πριν από τη διάθεση της τρέχουσας.

673
00:52:16,330 --> 00:52:23,580
Διότι διαφορετικά θα πετάξετε τις πληροφορίες για το τι έχει απομείνει από τη λίστα.

674
00:52:23,580 --> 00:52:34,160
Τώρα, αν πας στη συσκευή σας, θα ανοίξει queue.c--x από αυτό.

675
00:52:34,160 --> 00:52:39,390
Έτσι, αν ανοίξει queue.c, επιτρέψτε μου μεγέθυνση εδώ,

676
00:52:39,390 --> 00:52:44,970
θα δείτε ότι έχετε μια παρόμοια εμφάνιση αρχείο.

677
00:52:44,970 --> 00:52:49,200
Παρόμοια εμφάνιση αρχείο με ό, τι είχαμε νωρίτερα με stack.c.

678
00:52:49,200 --> 00:52:54,690
Έχουμε struct μας για την ουρά που ορίζεται ακριβώς όπως είδαμε στις διαφάνειες.

679
00:52:54,690 --> 00:52:59,870
>> Έχουμε enqueue λειτουργία μας, η οποία είναι για σας να το κάνετε.

680
00:52:59,870 --> 00:53:04,340
Και έχουμε την dequeue λειτουργία εδώ.

681
00:53:04,340 --> 00:53:06,870
Η dequeue λειτουργία του αρχείου είναι ανεφάρμοστοι,

682
00:53:06,870 --> 00:53:13,230
αλλά εγώ θα το θέσω back up για το PowerPoint, έτσι ώστε να μπορείτε να πληκτρολογήσετε, αν θέλετε.

683
00:53:13,230 --> 00:53:16,690
Έτσι, για τα επόμενα 5 λεπτά ή έτσι, εσείς εργασίες για enqueue

684
00:53:16,690 --> 00:53:22,570
που είναι σχεδόν ακριβώς το αντίθετο από dequeue.

685
00:53:22,570 --> 00:53:29,560
Δεν χρειάζεται να ρυθμίσετε το κεφάλι όταν enqueueing, αλλά τι έχετε να ρυθμίσετε;

686
00:53:29,560 --> 00:53:38,920
Μέγεθος. Έτσι, όταν enqueue, το κεφάλι παραμένει ανέπαφο, το μέγεθος παίρνει αλλάξει.

687
00:53:38,920 --> 00:53:46,920
Αλλά χρειάζεται να είναι κανείς λίγο - θα πρέπει να παίζουν με αυτό το mod

688
00:53:46,920 --> 00:53:57,560
για να καταλάβω ακριβώς τι δείκτη το νέο στοιχείο θα πρέπει να εισαχθεί σε.

689
00:53:57,560 --> 00:54:03,080
Γι 'αυτό και θα δώσει εσείς λίγο, βάλτε dequeue back up στη διαφάνεια,

690
00:54:03,080 --> 00:54:05,200
όπως και εσείς έχετε ερωτήσεις, τους φωνάζουν έξω ώστε να μπορούμε να

691
00:54:05,200 --> 00:54:09,220
όλοι μιλούν γι 'αυτούς σαν μια ομάδα.

692
00:54:09,220 --> 00:54:13,960
Επίσης, με το μέγεθος σας μην τα - όταν ρυθμίζετε το μέγεθος, μπορείτε πάντα απλά -

693
00:54:13,960 --> 00:54:18,720
έχετε να mod το μέγεθος ποτέ; [Daniel] Όχι >> Δεν χρειάζεται να mod το μέγεθος, δεξιά.

694
00:54:18,720 --> 00:54:24,260
Επειδή το μέγεθος θα είναι πάντα, αν Μπορείτε πλέον - υποθέτοντας είστε διαχειρίζονται τα πράγματα σωστά,

695
00:54:24,260 --> 00:54:30,840
το μέγεθος θα είναι πάντα μεταξύ 0 και 3.

696
00:54:30,840 --> 00:54:38,680
Σε περίπτωση που έχετε να mod όταν κάνετε enqueue;

697
00:54:38,680 --> 00:54:41,060
[Φοιτητών] Μόνο για το κεφάλι. >> Μόνο για το κεφάλι, ακριβώς.

698
00:54:41,060 --> 00:54:44,620
Και γιατί θα πρέπει να mod καθόλου σε enqueue;

699
00:54:44,620 --> 00:54:48,830
Όταν είναι μια κατάσταση κατά την οποία θα έπρεπε να mod;

700
00:54:48,830 --> 00:54:53,630
[Φοιτητικό] Αν έχετε πράγματα σε χώρους, όπως σε χώρους 1 και 2,

701
00:54:53,630 --> 00:54:55,950
και τότε θα έπρεπε να προσθέσω κάτι σε 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Ναι, ακριβώς. Έτσι, αν ο δείκτης κεφάλι σας είναι στο τέλος-τέλος,

703
00:55:02,570 --> 00:55:14,210
ή αν το μέγεθος σας συν το κεφάλι σας είναι μεγαλύτερο, ή μάλλον, πρόκειται να τυλίξει γύρω από την ουρά.

704
00:55:14,210 --> 00:55:17,830
>> Έτσι, σε αυτήν την κατάσταση που έχουμε εδώ στη διαφάνεια αυτή τη στιγμή,

705
00:55:17,830 --> 00:55:24,370
αν θέλω να enqueue κάτι αυτή τη στιγμή,

706
00:55:24,370 --> 00:55:31,110
θέλουμε να enqueue κάτι στο δείκτη 0.

707
00:55:31,110 --> 00:55:35,450
Έτσι, αν κοιτάξετε, όπου το 50 πηγαίνει, και καλώ enqueue 50,

708
00:55:35,450 --> 00:55:40,840
πηγαίνει εκεί κάτω στο κάτω μέρος. Πηγαίνει στο δείκτη 0.

709
00:55:40,840 --> 00:55:44,160
Αντικαθιστά το «γεια» που είχε ήδη dequeued.

710
00:55:44,160 --> 00:55:46,210
[Δανιήλ] Μην παίρνετε τη φροντίδα του ότι σε dequeue ήδη;

711
00:55:46,210 --> 00:55:50,550
Γιατί δεν το κάνει τίποτα με το κεφάλι σε enqueue;

712
00:55:50,550 --> 00:55:55,770
[Hardison] Ω, έτσι δεν είστε τροποποιώντας το κεφάλι, συγνώμη.

713
00:55:55,770 --> 00:56:02,310
Αλλά θα πρέπει να χρησιμοποιήσετε τον τελεστή mod όταν έχετε πρόσβαση

714
00:56:02,310 --> 00:56:04,250
το στοιχείο που θέλετε να enqueue όταν έχετε πρόσβαση

715
00:56:04,250 --> 00:56:06,960
το επόμενο στοιχείο στην ουρά σας.

716
00:56:06,960 --> 00:56:10,960
[Βασίλης] Εγώ δεν το κάνουμε αυτό, και πήρα "επιτυχία" εκεί.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Ω, καταλαβαίνω τι λέτε.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Έτσι didn't - απλά έκανε στο q.size;

719
00:56:16,240 --> 00:56:20,670
[Βασίλης] Ναι. Έχω αλλάξει μόνο πλευρές, δεν έκανα τίποτα με το κεφάλι.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Μπορείτε στην πραγματικότητα, δεν πρέπει να επαναφέρετε το κεφάλι να είναι οτιδήποτε,

721
00:56:24,300 --> 00:56:31,650
αλλά όταν δείκτη μέσα στον πίνακα χορδές,

722
00:56:31,650 --> 00:56:39,500
που πραγματικά πρέπει να πάμε μπροστά και να υπολογίσει όπου το επόμενο στοιχείο είναι,

723
00:56:39,500 --> 00:56:44,230
βέργα επειδή η στοίβα, το επόμενο στοιχείο στη στοίβα σας ήταν πάντα

724
00:56:44,230 --> 00:56:48,740
κατά τον δείκτη που αντιστοιχεί στο μέγεθος.

725
00:56:48,740 --> 00:56:55,850
Αν κοιτάξουμε πίσω επάνω σε λειτουργία πάτημα stack μας,

726
00:56:55,850 --> 00:57:03,100
θα μπορούσαμε πάντα να τραβώ σε νέο στοιχείο μας το δικαίωμα στο μέγεθος του δείκτη.

727
00:57:03,100 --> 00:57:06,710
Ότι, με την ουρά, δεν μπορούμε να το κάνουμε αυτό

728
00:57:06,710 --> 00:57:10,340
γιατί αν είμαστε σε αυτή την κατάσταση,

729
00:57:10,340 --> 00:57:18,130
αν enqueued 50 νέα σειρά μας θα πάει δεξιά σε χορδές [1]

730
00:57:18,130 --> 00:57:20,540
το οποίο δεν θέλουμε να κάνουμε.

731
00:57:20,540 --> 00:57:41,200
Θέλουμε να έχουμε τη νέα σειρά πηγαίνουν στο δείκτη 0.

732
00:57:41,200 --> 00:57:44,320
>> Μήπως κάποιος - ναι; [Φοιτητικό] Έχω μια ερώτηση, αλλά δεν είναι πραγματικά σχετίζονται.

733
00:57:44,320 --> 00:57:48,160
Τι σημαίνει όταν κάποιος ζητά κάτι σαν προβλ δείκτη;

734
00:57:48,160 --> 00:57:51,260
Τι είναι αυτό το όνομα για σύντομο; Ξέρω ότι είναι απλά ένα όνομα.

735
00:57:51,260 --> 00:57:59,110
[Hardison] Pred δείκτη; Ας δούμε. Σε ποιο πλαίσιο;

736
00:57:59,110 --> 00:58:01,790
[Φοιτητικό] Ήταν για το ένθετο. Μπορώ να σας ρωτήσω αργότερα, αν θέλετε

737
00:58:01,790 --> 00:58:03,920
επειδή δεν είναι πραγματικά σχετίζονται, αλλά εγώ απλά -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Από κωδικός ένθετο του Δαβίδ από την διάλεξη;

739
00:58:07,300 --> 00:58:10,860
Μπορούμε να τραβήξει ότι μέχρι και να μιλήσουμε γι 'αυτό.

740
00:58:10,860 --> 00:58:15,550
Θα μιλήσουμε για το επόμενο, όταν έχουμε την ευκαιρία να συνδεδεμένες λίστες.

741
00:58:15,550 --> 00:58:21,440
>> Ας πολύ γρήγορα να δούμε τι η λειτουργία enqueue μοιάζει.

742
00:58:21,440 --> 00:58:26,530
Ποιο ήταν το πρώτο πράγμα που οι άνθρωποι προσπάθησαν να κάνουν σε enqueue γραμμή σας; Σε αυτήν την ουρά;

743
00:58:26,530 --> 00:58:29,960
Παρόμοιο με αυτό που έκανες για στοίβα πιέζει.

744
00:58:29,960 --> 00:58:32,080
Τι έκανες, Στέλλα;

745
00:58:32,080 --> 00:58:35,050
[Στέλλα, ακατάληπτο]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Ακριβώς. Αν (q.size == ΙΚΑΝΟΤΗΤΑ) -

747
00:58:45,700 --> 00:58:54,720
Πρέπει να βάλει σιδεράκια μου στο σωστό μέρος - επιστροφή ψευδείς.

748
00:58:54,720 --> 00:59:01,370
Ζουμ σε λίγο. Εντάξει.

749
00:59:01,370 --> 00:59:03,800
Τώρα ποιο είναι το επόμενο πράγμα που έπρεπε να κάνουμε;

750
00:59:03,800 --> 00:59:11,370
Ακριβώς όπως και με τη στοίβα, και εισάγεται στο σωστό μέρος.

751
00:59:11,370 --> 00:59:16,010
Και ναι, ποιο ήταν το σωστό μέρος για να τοποθετήσετε αυτό;

752
00:59:16,010 --> 00:59:23,170
Με τη στοίβα ήταν το μέγεθος του δείκτη, με αυτό είναι ότι δεν είναι αρκετά.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Έχω q.head--ή - q.strings >>; Ναι >>.

754
00:59:30,210 --> 00:59:40,470
q.strings [+ q.head q.size mod ΧΩΡΗΤΙΚΟΤΗΤΑ];

755
00:59:40,470 --> 00:59:42,740
[Hardison] Εμείς μάλλον θα θέλετε να βάλετε παρενθέσεις γύρω από αυτό

756
00:59:42,740 --> 00:59:48,830
έτσι ώστε να παίρνουμε την κατάλληλη προτεραιότητα και έτσι αυτό είναι cleart σε όλους.

757
00:59:48,830 --> 00:59:55,800
Και που να ισούται; >> Για να str; >> Για να str. Μεγάλη.

758
00:59:55,800 --> 01:00:00,160
Και τώρα τι είναι το τελευταίο πράγμα που πρέπει να κάνουμε;

759
01:00:00,160 --> 01:00:06,780
Ακριβώς όπως κάναμε στη στοίβα. >> Αύξησε το μέγεθος; >> Αύξησε το μέγεθος.

760
01:00:06,780 --> 01:00:13,830
Boom. Και στη συνέχεια, από την μίζα κώδικα μόλις επέστρεψε ψευδείς από προεπιλογή,

761
01:00:13,830 --> 01:00:27,460
θέλουμε να αλλάξουμε αυτό να ισχύει και αν όλα πάνε μέσα και όλα πάνε καλά.

762
01:00:27,460 --> 01:00:33,050
Εντάξει. Αυτό είναι πολλές πληροφορίες για το τμήμα.

763
01:00:33,050 --> 01:00:39,480
Δεν είμαστε αρκετά πάνω. Θέλουμε να μιλήσουμε πραγματικά γρήγορα για μεμονωμένα-συνδεδεμένες λίστες.

764
01:00:39,480 --> 01:00:44,010
Θα βάλω αυτό επάνω ώστε να μπορέσουμε να επιστρέψουμε σε αυτό αργότερα.

765
01:00:44,010 --> 01:00:50,850
Αλλά ας επιστρέψουμε στην παρουσίασή μας για μερικές περισσότερες διαφάνειες.

766
01:00:50,850 --> 01:00:53,790
Έτσι enqueue είναι TODO, τώρα έχουμε κάνει.

767
01:00:53,790 --> 01:00:57,430
>> Τώρα, ας ρίξουμε μια ματιά σε μεμονωμένα-συνδεδεμένες λίστες.

768
01:00:57,430 --> 01:01:00,040
Μιλήσαμε για αυτά λίγο περισσότερο σε διάλεξη.

769
01:01:00,040 --> 01:01:02,540
Πόσοι από σας είδε το demo όπου είχαμε ανθρώπους

770
01:01:02,540 --> 01:01:08,220
αδέξια δείχνουν ο ένας στον άλλο και εκμετάλλευση αριθμούς; >> Ήμουν σε αυτό.

771
01:01:08,220 --> 01:01:16,620
>> Τι νομίζετε εσείς; Μήπως ότι, ελπίζουμε αυτά τα απομυθοποιήσει λίγο;

772
01:01:16,620 --> 01:01:25,990
Με μια λίστα, αποδεικνύεται ότι έχουμε να κάνουμε με αυτόν τον τύπο ότι θα πάμε για να καλέσετε έναν κόμβο.

773
01:01:25,990 --> 01:01:32,520
Ότι, με την ουρά και η στοίβα είχαμε structs ότι είχαμε καλέσει ουρά σε στοίβα,

774
01:01:32,520 --> 01:01:34,860
είχαμε αυτά τα νέα είδη ουρά σε στοίβα,

775
01:01:34,860 --> 01:01:39,240
εδώ μια λίστα είναι πραγματικά ακριβώς αποτελείται από μια δέσμη των κόμβων.

776
01:01:39,240 --> 01:01:45,920
Με τον ίδιο τρόπο ότι οι χορδές είναι απλώς ένα μάτσο χαρακτήρες όλα παρατάσσονται το ένα δίπλα στο άλλο.

777
01:01:45,920 --> 01:01:50,650
Μια συνδεδεμένη λίστα είναι απλά ένας κόμβος και ένα άλλο κόμβο και ένα άλλο κόμβο και ένα άλλο κόμβο.

778
01:01:50,650 --> 01:01:55,080
Και παρά τη συντριβή όλων των κόμβων μαζί και την αποθήκευση τους συνεχόμενα

779
01:01:55,080 --> 01:01:58,090
όλα δίπλα στο άλλο στη μνήμη,

780
01:01:58,090 --> 01:02:04,470
με αυτό το επόμενο δείκτη μας επιτρέπει να αποθηκεύετε τους κόμβους όπου, τυχαία.

781
01:02:04,470 --> 01:02:10,500
Και στη συνέχεια το είδος του σύρματος όλα μαζί με το σημείο από το ένα στο επόμενο.

782
01:02:10,500 --> 01:02:15,850
>> Και αυτό ήταν το μεγάλο πλεονέκτημα ότι αυτό είχε πάνω από μια σειρά;

783
01:02:15,850 --> 01:02:21,680
Πάνω από όλα αποθήκευση συνεχόμενα μόλις κολλήσει ένα δίπλα στο άλλο;

784
01:02:21,680 --> 01:02:24,190
Θυμάσαι; Ναι; >> Δυναμική κατανομή μνήμης;

785
01:02:24,190 --> 01:02:27,220
>> Δυναμική κατανομή μνήμης σε ποια έννοια;

786
01:02:27,220 --> 01:02:31,780
[Φοιτητικό] Σε αυτό μπορείτε να κρατήσετε το καθιστά μεγαλύτερο και δεν χρειάζεται να μετακινήσετε ολόκληρη την σειρά σας;

787
01:02:31,780 --> 01:02:40,940
[Hardison] Ακριβώς. Έτσι, με μια σειρά, όταν θέλετε να βάλετε ένα νέο στοιχείο στη μέση του,

788
01:02:40,940 --> 01:02:45,320
θα πρέπει να στραφούν τα πάντα για να κάνει χώρο.

789
01:02:45,320 --> 01:02:47,880
Και όπως μιλήσαμε με την ουρά,

790
01:02:47,880 --> 01:02:50,080
αυτός είναι ο λόγος που διατηρούν το δείκτη κεφάλι,

791
01:02:50,080 --> 01:02:52,050
έτσι ώστε δεν είμαστε μετατοπίζεται συνεχώς πράγματα.

792
01:02:52,050 --> 01:02:54,520
Επειδή αυτό παίρνει ακριβά αν έχετε μια μεγάλη σειρά

793
01:02:54,520 --> 01:02:57,130
και κάνεις συνεχώς αυτές τις τυχαίες παρεμβολές.

794
01:02:57,130 --> 01:03:00,820
Ότι, με μια λίστα, το μόνο που έχετε να κάνετε είναι να ρίξει σε ένα νέο κόμβο,

795
01:03:00,820 --> 01:03:06,330
προσαρμόσει τους δείκτες, και είστε έτοιμοι.

796
01:03:06,330 --> 01:03:10,940
Τι χάλια γι 'αυτό;

797
01:03:10,940 --> 01:03:16,830
Εκτός από το γεγονός ότι δεν είναι τόσο εύκολο να εργαστεί με ως πίνακα; Ναι;

798
01:03:16,830 --> 01:03:22,980
[Daniel] Λοιπόν, υποθέτω ότι είναι πολύ πιο δύσκολο να αποκτήσει πρόσβαση σε ένα συγκεκριμένο στοιχείο στη συνδεδεμένη λίστα;

799
01:03:22,980 --> 01:03:30,470
[Hardison] Δεν μπορείτε απλά να μεταβείτε σε ένα αυθαίρετο στοιχείο στη μέση συνδεδεμένη λίστα σας.

800
01:03:30,470 --> 01:03:33,800
Πώς θα πρέπει να το κάνει αντ 'αυτού; >> Θα πρέπει να το βήμα σε όλο το πράγμα.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Ναι. Θα πρέπει να περάσουν από ένα κάθε φορά, ένα κάθε φορά.

802
01:03:35,660 --> 01:03:38,480
Είναι ένα τεράστιο - είναι ένας πόνος.

803
01:03:38,480 --> 01:03:41,550
Ποια είναι η άλλη - υπάρχει μια άλλη πτώση σε αυτό.

804
01:03:41,550 --> 01:03:45,340
[Βασίλης] Δεν μπορείτε να πάτε προς τα εμπρός και προς τα πίσω; Θα πρέπει να πάμε προς μία κατεύθυνση;

805
01:03:45,340 --> 01:03:48,570
[Hardison] Ναι. Επομένως, πώς θα λύσουμε ότι, μερικές φορές;

806
01:03:48,570 --> 01:03:53,370
[Βασίλης] διπλά συνδεδεμένες λίστες; Ακριβώς >>. Υπάρχουν διπλά συνδεδεμένες λίστες.

807
01:03:53,370 --> 01:03:55,540
Υπάρχουν επίσης - συγνώμη;

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Είναι το ίδιο όπως με το πράγμα που προβλ -

809
01:03:57,620 --> 01:04:01,090
Μόλις θυμήθηκα, δεν είναι ότι αυτό το πράγμα είναι προβλ για;

810
01:04:01,090 --> 01:04:05,850
Δεν είναι ότι στο μεταξύ διπλή και μονή;

811
01:04:05,850 --> 01:04:10,020
Ματιά [Hardison] Ας τι ακριβώς έκανε.

812
01:04:10,020 --> 01:04:15,760
Έτσι, εδώ πηγαίνουμε. Εδώ είναι ο κώδικας λίστα.

813
01:04:15,760 --> 01:04:25,620
Εδώ έχουμε predptr, εδώ. Είναι αυτό που ήταν λες;

814
01:04:25,620 --> 01:04:30,750
Έτσι, αυτό ήταν - αυτός είναι απελευθερώνοντας μια λίστα και προσπαθεί να αποθηκεύσει ένα δείκτη σε αυτό.

815
01:04:30,750 --> 01:04:35,000
Αυτό δεν είναι τα διπλά, μεμονωμένα συνδέονται-λίστες.

816
01:04:35,000 --> 01:04:40,090
Μπορούμε να μιλήσουμε περισσότερο για αυτό αργότερα, δεδομένου ότι αυτό μιλά για την απελευθέρωση του καταλόγου

817
01:04:40,090 --> 01:04:42,900
και θέλω να δείξω κάποια άλλα πράγματα πρώτα.

818
01:04:42,900 --> 01:04:51,480
αλλά είναι ακριβώς - είναι να θυμηθούμε την αξία του ptr

819
01:04:51,480 --> 01:04:54,170
[Φοιτητικό] Ω, είναι δείκτης προηγούμενο; Ναι >>.

820
01:04:54,170 --> 01:05:04,070
Έτσι ώστε να μπορούμε να αυξήσετε τότε ptr ίδια πριν τότε δωρεάν predptr τι είναι.

821
01:05:04,070 --> 01:05:09,130
Επειδή δεν μπορούμε να ptr δωρεάν και στη συνέχεια να καλέσετε ptr = ptr επόμενη, έτσι δεν είναι;

822
01:05:09,130 --> 01:05:11,260
Αυτό θα ήταν κακό.

823
01:05:11,260 --> 01:05:20,940
Ας δούμε λοιπόν, πίσω σε αυτόν τον τύπο.

824
01:05:20,940 --> 01:05:23,900
>> Το άλλο κακό πράγμα σχετικά με τις λίστες είναι ότι ενώ με μια σειρά

825
01:05:23,900 --> 01:05:26,520
έχουμε ακριβώς όλα τα στοιχεία οι ίδιοι στοιβάζονται το ένα δίπλα στο άλλο,

826
01:05:26,520 --> 01:05:29,050
εδώ έχουμε επίσης εισήγαγε αυτό το δείκτη.

827
01:05:29,050 --> 01:05:34,060
Έτσι, υπάρχει ένα επιπλέον κομμάτι της μνήμης που είμαστε να χρειάζεται να χρησιμοποιούν

828
01:05:34,060 --> 01:05:37,910
για κάθε στοιχείο ότι είμαστε αποθήκευση στην λίστα μας.

829
01:05:37,910 --> 01:05:40,030
Παίρνουμε την ευελιξία, αλλά έρχεται με ένα κόστος.

830
01:05:40,030 --> 01:05:42,230
Έρχεται με αυτό το κόστος του χρόνου,

831
01:05:42,230 --> 01:05:45,270
και έρχεται με αυτό το κόστος πάρα πολύ μνήμη.

832
01:05:45,270 --> 01:05:47,800
Ώρα με την έννοια ότι τώρα πρέπει να περάσει μέσα από κάθε στοιχείο του πίνακα

833
01:05:47,800 --> 01:05:58,670
για να βρείτε το ένα στο δείκτη 10, ή ότι θα είχε δείκτη 10 σε μια σειρά.

834
01:05:58,670 --> 01:06:01,230
>> Απλά πολύ γρήγορα, όταν διάγραμμα από αυτές τις λίστες,

835
01:06:01,230 --> 01:06:05,980
συνήθως έχουμε στην κατοχή μας για να το κεφάλι της λίστας ή του πρώτου δείκτη της λίστας

836
01:06:05,980 --> 01:06:08,010
και σημειώστε ότι αυτό είναι ένα πραγματικό δείκτη.

837
01:06:08,010 --> 01:06:11,100
Είναι μόλις 4 bytes. Δεν είναι ένα πραγματικό κόμβο ίδια.

838
01:06:11,100 --> 01:06:17,120
Βλέπετε λοιπόν ότι δεν έχει int αξία σε αυτό, δεν υπάρχει επόμενη δείκτη σε αυτό.

839
01:06:17,120 --> 01:06:20,790
Είναι κυριολεκτικά μόνο ένα δείκτη.

840
01:06:20,790 --> 01:06:23,550
Είναι πρόκειται να επισημάνω κάτι που είναι μια πραγματική struct node.

841
01:06:23,550 --> 01:06:28,480
[Sam] Ένας δείκτης που ονομάζεται κόμβος; >> Αυτό είναι - όχι. Αυτός είναι ένας δείκτης για κάτι τύπου του κόμβου.

842
01:06:28,480 --> 01:06:32,540
Πρόκειται για ένα δείκτη σε struct node. >> Ω, εντάξει.

843
01:06:32,540 --> 01:06:36,870
Διάγραμμα για την αριστερά, κωδικό στα δεξιά.

844
01:06:36,870 --> 01:06:42,190
Μπορούμε να ρυθμιστεί σε null, η οποία είναι ένας καλός τρόπος για να ξεκινήσει.

845
01:06:42,190 --> 01:06:49,850
Όταν το διάγραμμα, μπορείτε είτε να το γράψετε ως άκυρη ή να βάλετε μια γραμμή έτσι.

846
01:06:49,850 --> 01:06:53,910
>> Ένας από τους ευκολότερους τρόπους για να συνεργαστεί με τους καταλόγους,

847
01:06:53,910 --> 01:06:57,430
και σας ζητάμε να κάνετε και τα δύο και βάλε προσαρτήσει για να δείτε τις διαφορές μεταξύ των δύο,

848
01:06:57,430 --> 01:07:01,320
προσθέτοντας στην αρχή, αλλά είναι σίγουρα πιο εύκολη.

849
01:07:01,320 --> 01:07:05,790
Όταν βάζετε μπροστά, αυτό είναι όπου μπορείτε - όταν βάλε (7),

850
01:07:05,790 --> 01:07:10,050
να πάτε και να δημιουργήσετε το struct node

851
01:07:10,050 --> 01:07:13,870
και θα ορίσετε πρώτα να επισημάνω σε αυτό, γιατί τώρα, από τότε που το προταχθεί,

852
01:07:13,870 --> 01:07:17,240
πρόκειται να είναι στην αρχή της λίστας.

853
01:07:17,240 --> 01:07:22,540
Αν βάλε (3), που δημιουργεί ένα άλλο κόμβο, αλλά τώρα 3 έρχεται πριν από 7.

854
01:07:22,540 --> 01:07:31,130
Έτσι, είμαστε ουσιαστικά ωθεί τα πράγματα σε λίστα μας.

855
01:07:31,130 --> 01:07:34,720
Τώρα, μπορείτε να δείτε ότι βάλε, μερικές φορές οι άνθρωποι αποκαλούν ωθεί,

856
01:07:34,720 --> 01:07:39,600
επειδή είστε πιέζει ένα νέο στοιχείο σε λίστα σας.

857
01:07:39,600 --> 01:07:43,270
Είναι επίσης εύκολο να διαγραφεί στο μπροστινό μέρος του καταλόγου.

858
01:07:43,270 --> 01:07:45,650
Έτσι οι άνθρωποι θα καλέσει συχνά ότι η ποπ.

859
01:07:45,650 --> 01:07:52,200
Και με αυτόν τον τρόπο, μπορείτε να μιμηθεί μια στοίβα χρησιμοποιώντας μια συνδεδεμένη λίστα.

860
01:07:52,200 --> 01:07:57,880
Ουπς. Λυπούμαστε, αλλά τώρα μπαίνουμε σε προσάρτησης. Έτσι, εδώ θα προταχθεί (7), τώρα βάλε το (3).

861
01:07:57,880 --> 01:08:02,600
Αν προταχθεί κάτι άλλο πάνω σε αυτή τη λίστα, αν προταχθεί (4),

862
01:08:02,600 --> 01:08:06,540
τότε θα είχαμε 4 και στη συνέχεια 3 και στη συνέχεια 7.

863
01:08:06,540 --> 01:08:14,220
Έτσι λοιπόν θα μπορούσαμε να σκάσει και να αφαιρέσετε 4, αφαίρεση 3, αφαιρέστε 7.

864
01:08:14,220 --> 01:08:16,500
Συχνά, το πιο έξυπνο τρόπο για να σκεφτεί για αυτό είναι με προσάρτησης.

865
01:08:16,500 --> 01:08:20,310
Έτσι έχω διαγραμματικά τι θα μοιάζουν με προσθέσετε εδώ.

866
01:08:20,310 --> 01:08:23,380
Εδώ, το οποίο επισυνάπτεται (7) δεν φαίνεται διαφορετικό

867
01:08:23,380 --> 01:08:25,160
επειδή υπάρχει μόνο ένα στοιχείο στη λίστα.

868
01:08:25,160 --> 01:08:28,620
Και προσάρτηση (3) θέτει στο τέλος.

869
01:08:28,620 --> 01:08:31,020
Ίσως μπορείτε να δείτε τώρα το κόλπο με προσάρτησης

870
01:08:31,020 --> 01:08:36,600
είναι ότι από τη στιγμή που γνωρίζουν μόνο όταν η αρχή της λίστας είναι,

871
01:08:36,600 --> 01:08:39,450
να προσθέσετε σε μια λίστα που έχετε να περπατήσετε σε όλη τη διαδρομή μέσα από τη λίστα

872
01:08:39,450 --> 01:08:46,500
για να φτάσουμε στο τέλος, να σταματήσει, να χτίσουν τότε ο κόμβος σας και ό, τι τραβώ.

873
01:08:46,500 --> 01:08:50,590
Συνδέστε όλα τα πράγματα επάνω.

874
01:08:50,590 --> 01:08:55,170
Έτσι, με βάλε, όπως μόλις άρπαξαν μέσα από αυτό πολύ γρήγορα,

875
01:08:55,170 --> 01:08:58,170
όταν βάζετε μπροστά σε μια λίστα, είναι αρκετά απλό.

876
01:08:58,170 --> 01:09:02,960
>> Μπορείτε να κάνετε νέος κόμβος σας, περιλαμβάνουν κάποια δυναμική κατανομή μνήμης.

877
01:09:02,960 --> 01:09:09,830
Έτσι, εδώ είμαστε κάνοντας μια struct node χρησιμοποιώντας malloc.

878
01:09:09,830 --> 01:09:14,710
Έτσι malloc που χρησιμοποιούμε γιατί αυτό θα αναιρέσει τη μνήμη μας για αργότερα

879
01:09:14,710 --> 01:09:20,350
γιατί δεν θέλουμε αυτό - θέλουμε αυτή η μνήμη να διατηρηθεί για μεγάλο χρονικό διάστημα.

880
01:09:20,350 --> 01:09:25,350
Και έχουμε ένα δείκτη προς το χώρο στη μνήμη που μόλις διατεθεί.

881
01:09:25,350 --> 01:09:29,260
Χρησιμοποιούμε το μέγεθος του κόμβου, δεν αθροίζουν τα πεδία.

882
01:09:29,260 --> 01:09:31,899
Εμείς δεν παράγουν αυτόματα τον αριθμό των bytes,

883
01:09:31,899 --> 01:09:39,750
αντί να χρησιμοποιούμε sizeof ώστε να ξέρουμε παίρνουμε τον κατάλληλο αριθμό των bytes.

884
01:09:39,750 --> 01:09:43,660
Φροντίζουμε να ελέγξετε ότι η κλήση malloc μας πέτυχε.

885
01:09:43,660 --> 01:09:47,939
Αυτό είναι κάτι που θέλετε να κάνετε σε γενικές γραμμές.

886
01:09:47,939 --> 01:09:52,590
Με σύγχρονα μηχανήματα, που τρέχει από μνήμη δεν είναι κάτι που είναι εύκολο

887
01:09:52,590 --> 01:09:56,610
εκτός και αν είστε κατανομή έναν τόνο πράγματα και κάνοντας μια τεράστια λίστα,

888
01:09:56,610 --> 01:10:02,220
αλλά αν χτίζετε τα πράγματα για την, ας πούμε, σαν ένα iPhone ή Android,

889
01:10:02,220 --> 01:10:05,230
που έχουν περιορισμένους πόρους μνήμης, ειδικά αν κάνετε κάτι έντονο.

890
01:10:05,230 --> 01:10:08,300
Γι 'αυτό είναι καλό να μπει σε πράξη.

891
01:10:08,300 --> 01:10:10,510
>> Σημειώστε ότι έχω χρησιμοποιήσει ένα ζευγάρι διαφορετικές λειτουργίες εδώ

892
01:10:10,510 --> 01:10:12,880
ότι έχετε δει ότι είναι το είδος των νέων.

893
01:10:12,880 --> 01:10:15,870
Έτσι fprintf είναι ακριβώς όπως printf

894
01:10:15,870 --> 01:10:21,320
εκτός από το πρώτο επιχείρημά της είναι το ρεύμα στο οποίο θέλετε να εκτυπώσετε.

895
01:10:21,320 --> 01:10:23,900
Σε αυτή την περίπτωση, θέλουμε να εκτυπώσετε με το πρότυπο σφάλμα σειρά

896
01:10:23,900 --> 01:10:29,410
το οποίο είναι διαφορετικό από το πρότυπο outstream.

897
01:10:29,410 --> 01:10:31,620
Εξ ορισμού εμφανίζεται στην ίδια θέση.

898
01:10:31,620 --> 01:10:34,600
Τυπώνει επίσης στον τερματικό σταθμό, αλλά μπορείτε -

899
01:10:34,600 --> 01:10:38,790
χρησιμοποιώντας αυτές τις εντολές μάθατε για, τις τεχνικές ανακατεύθυνση

900
01:10:38,790 --> 01:10:42,290
μάθατε σχετικά με το βίντεο του Tommy για σετ πρόβλημα 4, μπορείτε να το κατευθύνει

901
01:10:42,290 --> 01:10:47,900
σε διαφορετικές περιοχές? στη συνέχεια, βγείτε, ακριβώς εδώ, βγαίνει από το πρόγραμμά σας.

902
01:10:47,900 --> 01:10:50,440
Είναι ουσιαστικά σαν επιστροφή από την κύρια,

903
01:10:50,440 --> 01:10:53,600
εκτός από την έξοδο χρησιμοποιούμε εδώ επειδή επιστροφή δεν θα κάνει τίποτα.

904
01:10:53,600 --> 01:10:57,140
Δεν είμαστε σε γενικές γραμμές, έτσι ώστε επιστρέφοντας δεν βγείτε από το πρόγραμμα, όπως θέλουμε.

905
01:10:57,140 --> 01:11:03,020
Γι 'αυτό και χρησιμοποιούν τη λειτουργία εξόδου και να της δώσει έναν κωδικό σφάλματος.

906
01:11:03,020 --> 01:11:11,890
Στη συνέχεια, εδώ έχουμε δημιουργήσει τομέα αξία του νέου κόμβου, στον τομέα του i να είναι ίση με i, και τότε το σύρμα μέχρι.

907
01:11:11,890 --> 01:11:15,530
Είμαστε δίπλα δείκτη του νέου κόμβου στο σημείο από την πρώτη,

908
01:11:15,530 --> 01:11:20,460
και τότε η πρώτη θα είναι πλέον το σημείο στο νέο κόμβο.

909
01:11:20,460 --> 01:11:25,120
Αυτές οι πρώτες γραμμές κώδικα, χτίζουμε στην πραγματικότητα το νέο κόμβο.

910
01:11:25,120 --> 01:11:27,280
Δεν είναι οι δύο τελευταίες γραμμές αυτής της λειτουργίας, αλλά οι πρώτοι.

911
01:11:27,280 --> 01:11:30,290
Μπορείτε πραγματικά τραβήξει έξω σε μια λειτουργία, σε μια συνάρτηση βοηθητικού.

912
01:11:30,290 --> 01:11:32,560
Αυτό είναι συχνά αυτό που κάνω είναι, εγώ το τραβήξει έξω σε λειτουργία,

913
01:11:32,560 --> 01:11:36,040
Καλώ κάτι σαν κόμβος κατασκευής,

914
01:11:36,040 --> 01:11:40,410
και ότι κρατά η λειτουργία βάλε αρκετά μικρό, είναι μόλις 3 γραμμές τότε.

915
01:11:40,410 --> 01:11:48,710
Κάνω μια έκκληση να οικοδομήσουμε λειτουργία κόμβο μου, και τότε τα πάντα σύρμα επάνω.

916
01:11:48,710 --> 01:11:51,970
>> Το τελευταίο πράγμα που θέλω να σας δείξω,

917
01:11:51,970 --> 01:11:54,030
και εγώ θα σας αφήσει να κάνει append και όλα αυτά με δική σας,

918
01:11:54,030 --> 01:11:57,500
είναι το πώς να επαναλάβει πάνω από μια λίστα.

919
01:11:57,500 --> 01:12:00,780
Υπάρχουν ένα σωρό διαφορετικούς τρόπους για να επαναλάβει πάνω από μια λίστα.

920
01:12:00,780 --> 01:12:03,140
Σε αυτή την περίπτωση, θα πάμε να βρείτε το μήκος μιας λίστας.

921
01:12:03,140 --> 01:12:06,570
Έτσι ξεκινάμε με μήκος = 0.

922
01:12:06,570 --> 01:12:11,580
Αυτό είναι πολύ παρόμοιο με strlen γραπτώς για μια σειρά.

923
01:12:11,580 --> 01:12:17,780
Αυτό είναι ό, τι θέλω να σου δείξω, το δικαίωμα για βρόχο εδώ.

924
01:12:17,780 --> 01:12:23,530
Φαίνεται κάπως funky? Δεν είναι η συνήθης int i = 0, i <οτιδήποτε άλλο, i + +.

925
01:12:23,530 --> 01:12:34,920
Αντ 'αυτού, είναι αρχικοποίηση μεταβλητής n μας να είναι η αρχή της λίστας.

926
01:12:34,920 --> 01:12:40,620
Και στη συνέχεια, ενώ iterator μεταβλητή μας δεν είναι μηδενική, θα συνεχίσω.

927
01:12:40,620 --> 01:12:46,340
Αυτό οφείλεται στο γεγονός ότι, κατά συνθήκη, το τέλος του καταλόγου μας θα είναι μηδενική.

928
01:12:46,340 --> 01:12:48,770
Και στη συνέχεια, για να αυξήσετε, αντί να κάνει + +,

929
01:12:48,770 --> 01:12:57,010
το συνδεδεμένο ισοδύναμο κατάλογος των + + είναι η = n-> επόμενη.

930
01:12:57,010 --> 01:13:00,410
>> Θα σας αφήσω να καλύψει τα κενά εδώ επειδή είμαστε έξω από το χρόνο.

931
01:13:00,410 --> 01:13:09,300
Αλλά να έχετε κατά νου αυτό που εργάζεστε για psets spellr σας.

932
01:13:09,300 --> 01:13:11,650
Συνδέεται λίστες, εάν είστε εφαρμογή ενός πίνακα κατακερματισμού,

933
01:13:11,650 --> 01:13:14,010
σίγουρα θα έρθει πολύ σε πρακτικό.

934
01:13:14,010 --> 01:13:21,780
Και έχοντας αυτό το ιδίωμα για looping πάνω από πράγματα που θα κάνουν τη ζωή πολύ πιο εύκολο, ελπίζω.

935
01:13:21,780 --> 01:13:25,910
Οποιεσδήποτε ερωτήσεις, γρήγορα;

936
01:13:25,910 --> 01:13:28,920
[Sam] Θα σας στείλει το συμπληρωμένο SLL και sc;

937
01:13:28,920 --> 01:13:38,360
[Hardison] Ναι. Θα στείλει ολοκληρωθεί διαφάνειες και ολοκληρώθηκε στοίβα SLL και queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]