1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:05,120
[Παίζει μουσική]

3
00:00:05,120 --> 00:00:12,026

4
00:00:12,026 --> 00:00:12,900
ΟΜΙΛΗΤΗΣ 1: Εντάξει.

5
00:00:12,900 --> 00:00:14,600
Όλοι καλωσορίσω πίσω στην ενότητα.

6
00:00:14,600 --> 00:00:18,660
Ελπίζω να είστε όλοι με επιτυχία
ανακτώνται από το κουίζ σας

7
00:00:18,660 --> 00:00:19,510
από την περασμένη εβδομάδα.

8
00:00:19,510 --> 00:00:22,564
Ξέρω ότι είναι λίγο τρελός μερικές φορές.

9
00:00:22,564 --> 00:00:25,230
Όπως είπα και πριν, αν είστε
στο πλαίσιο της τυπικής απόκλισης,

10
00:00:25,230 --> 00:00:28,188
Πραγματικά δεν ανησυχείτε γι 'αυτό, ιδιαίτερα
για μια λιγότερο άνετα τμήμα.

11
00:00:28,188 --> 00:00:30,230
Αυτό είναι σχετικά με το πού θα πρέπει να είναι.

12
00:00:30,230 --> 00:00:32,850
>> Αν κάνατε μεγάλη, τότε φοβερό.

13
00:00:32,850 --> 00:00:33,650
Συγχαρητήρια σε εσάς.

14
00:00:33,650 --> 00:00:36,149
Και εάν αισθάνεστε σαν να πρέπει
λίγο περισσότερη βοήθεια, παρακαλούμε

15
00:00:36,149 --> 00:00:38,140
μην διστάσετε να επικοινωνήσετε
έξω σε κάποιο από τα ΤΡ.

16
00:00:38,140 --> 00:00:40,030
Είμαστε όλοι εδώ για να βοηθήσουμε.

17
00:00:40,030 --> 00:00:40,960
>> Αυτός είναι ο λόγος για τον οποίο διδάσκουμε.

18
00:00:40,960 --> 00:00:44,550
Γι 'αυτό είμαι εδώ κάθε Δευτέρα για εσάς
παιδιά και στα γραφεία ώρες την Πέμπτη.

19
00:00:44,550 --> 00:00:48,130
Έτσι, μη διστάσετε να επιτρέψτε μου να ξέρω
αν είστε ανησυχούν για τίποτα

20
00:00:48,130 --> 00:00:52,450
ή αν υπάρχει κάτι για το κουίζ
ότι θα θέλατε πραγματικά να αντιμετωπίσει.

21
00:00:52,450 --> 00:00:56,940
>> Επομένως, η ατζέντα για σήμερα είναι
όλα τα σχετικά με τις δομές δεδομένων.

22
00:00:56,940 --> 00:01:01,520
Μερικά από αυτά είναι ακριβώς πρόκειται να είναι ακριβώς
για να έχετε εξοικειωθεί με αυτά.

23
00:01:01,520 --> 00:01:04,870
Δεν μπορεί ποτέ να εφαρμόσουν
τους σε αυτή την κατηγορία.

24
00:01:04,870 --> 00:01:08,690
Μερικά από αυτά θέλετε,
όπως για ορθογράφο το chipset σας.

25
00:01:08,690 --> 00:01:11,380
>> Θα έχετε την επιλογή σας
ανάμεσα σε πίνακες κατακερματισμού και προσπαθεί.

26
00:01:11,380 --> 00:01:13,680
Έτσι θα είμαστε σίγουρα να πηγαίνει πέρα ​​από εκείνους.

27
00:01:13,680 --> 00:01:18,690
Είναι πρόκειται να είναι σίγουρα περισσότερο από το είδος
ενός τμήματος υψηλού επιπέδου σήμερα, όμως,

28
00:01:18,690 --> 00:01:22,630
επειδή υπάρχουν πολλά από αυτά, και αν
πήγαμε σε λεπτομέρειες υλοποίησης

29
00:01:22,630 --> 00:01:26,490
για όλα αυτά, δεν θα
ακόμη και να πάρετε μέσα από συνδεδεμένες λίστες

30
00:01:26,490 --> 00:01:28,520
και ίσως ένα μικρό κομμάτι των πινάκων κατακερματισμού.

31
00:01:28,520 --> 00:01:31,200
>> Έτσι φέρει μαζί μου.

32
00:01:31,200 --> 00:01:33,530
Εμείς δεν πρόκειται να κάνουμε
όσο κωδικοποίησης αυτή τη φορά.

33
00:01:33,530 --> 00:01:36,870
Εάν έχετε οποιεσδήποτε ερωτήσεις σχετικά με αυτό
ή θέλετε να δω να υλοποιούνται

34
00:01:36,870 --> 00:01:39,260
ή να το δοκιμάσετε για τον εαυτό σας,
Θα ήθελα να συστήσω σίγουρα

35
00:01:39,260 --> 00:01:44,250
πρόκειται να study.cs50.net, η οποία
έχει παραδείγματα όλα αυτά.

36
00:01:44,250 --> 00:01:46,400
Θα έχουν Powerpoints μου
με τις σημειώσεις που έχουμε

37
00:01:46,400 --> 00:01:50,860
τείνουν να χρησιμοποιούν καθώς και λίγο προγραμματισμό
ασκήσεις, ειδικά για τα πράγματα

38
00:01:50,860 --> 00:01:55,250
όπως συνδεδεμένες λίστες και δυαδικό
δέντρα στοίβες και συνθήματα.

39
00:01:55,250 --> 00:01:59,590
Έτσι, λίγο πιο υψηλό επίπεδο, το οποίο
μπορεί να είναι καλό για σας παιδιά.

40
00:01:59,590 --> 00:02:01,320
>> Έτσι, με αυτό, θα ξεκινήσετε.

41
00:02:01,320 --> 00:02:03,060
Και επίσης, yes-- κουίζ.

42
00:02:03,060 --> 00:02:06,550
Νομίζω ότι οι περισσότεροι από εσάς που είναι σε
τμήμα μου έχουν κουίζ σας,

43
00:02:06,550 --> 00:02:12,060
αλλά ο καθένας έρχεται σε ή κάποιο λόγο
δεν κάνουν, έχουν δίκιο εδώ στο μπροστινό μέρος.

44
00:02:12,060 --> 00:02:12,740
>> Έτσι, συνδεδεμένες λίστες.

45
00:02:12,740 --> 00:02:15,650
Ξέρω ότι αυτό το είδος του πηγαίνει
στην πλάτη πριν κουίζ σας.

46
00:02:15,650 --> 00:02:17,940
Αυτή ήταν η εβδομάδα πριν
ότι μάθαμε σχετικά με αυτό.

47
00:02:17,940 --> 00:02:21,040
Αλλά σε αυτή την περίπτωση, απλά θα
πάει λίγο περισσότερο σε βάθος.

48
00:02:21,040 --> 00:02:25,900
>> Επομένως, γιατί θα μπορούσαμε να επιλέξουν ένα
συνδεδεμένη λίστα πάνω από μια σειρά;

49
00:02:25,900 --> 00:02:27,130
Αυτό που τους διακρίνει;

50
00:02:27,130 --> 00:02:27,630
Ναι;

51
00:02:27,630 --> 00:02:30,464
>> ΚΟΙΝΟ: Μπορείτε να επεκτείνετε ένα συνδεδεμένο
λίστα έναντι σταθερού μεγέθους μιας συστοιχίας.

52
00:02:30,464 --> 00:02:31,171
ΟΜΙΛΗΤΗΣ 1: Δεξιά.

53
00:02:31,171 --> 00:02:33,970
Ένας πίνακας έχει σταθερό μέγεθος, ενώ ένα
συνδεδεμένη λίστα έχει ένα μεταβλητό μέγεθος.

54
00:02:33,970 --> 00:02:36,970
Έτσι, αν δεν ξέρουμε πώς
πολύ θέλουμε να αποθηκεύσουμε,

55
00:02:36,970 --> 00:02:39,880
μια συνδεδεμένη λίστα μας δίνει μια μεγάλη
τρόπος για να το κάνουμε αυτό, διότι μπορούμε μόνο

56
00:02:39,880 --> 00:02:43,730
προσθέσετε σε έναν άλλο κόμβο και να προσθέσετε στην
άλλο κόμβο και να προσθέσετε σε ένα άλλο κόμβο.

57
00:02:43,730 --> 00:02:45,750
Αλλά τι θα μπορούσε να είναι ένα trade-off;

58
00:02:45,750 --> 00:02:49,521
Υπάρχει κάποιος που θυμάται το εμπόριο-off
μεταξύ συστοιχιών και συνδεδεμένες λίστες;

59
00:02:49,521 --> 00:02:50,020
Mmhmm;

60
00:02:50,020 --> 00:02:51,460
>> ΚΟΙΝΟ: Θα πρέπει να
περάσουν από όλα τον τρόπο

61
00:02:51,460 --> 00:02:53,738
μέσω της συνδεδεμένη λίστα
βρείτε ένα στοιχείο σε μια λίστα.

62
00:02:53,738 --> 00:02:55,570
Σε έναν πίνακα, μπορείτε να
απλά να βρείτε ένα στοιχείο.

63
00:02:55,570 --> 00:02:56,278
>> ΟΜΙΛΗΤΗΣ 1: Δεξιά.

64
00:02:56,278 --> 00:02:57,120
Έτσι, με arrays--

65
00:02:57,120 --> 00:02:58,500
>> ΚΟΙΝΟ: [δεν ακούγεται].

66
00:02:58,500 --> 00:03:01,090
>> ΟΜΙΛΗΤΗΣ 1: Με συστοιχίες, έχουμε
ό, τι λέγεται τυχαία πρόσβαση.

67
00:03:01,090 --> 00:03:04,820
Σημαίνει ότι αν θέλουμε ό, τι είναι
ποτέ το πέμπτο σημείο του καταλόγου

68
00:03:04,820 --> 00:03:07,230
ή το πέμπτο σημείο μας
σειρά, μπορούμε να το αρπάξει μόνο.

69
00:03:07,230 --> 00:03:10,440
Αν είναι μια συνδεδεμένη λίστα, έχουμε
για να μετακινηθείτε μέσα, σωστά;

70
00:03:10,440 --> 00:03:14,020
Έτσι πρόσβαση σε ένα στοιχείο σε
ένας πίνακας είναι σταθερό χρόνο,

71
00:03:14,020 --> 00:03:19,530
ενώ με μια συνδεδεμένη λίστα που θα
πιο πιθανό να είναι γραμμικό χρόνο, επειδή ίσως

72
00:03:19,530 --> 00:03:21,370
στοιχείο μας είναι όλος ο τρόπος στο τέλος.

73
00:03:21,370 --> 00:03:23,446
Πρέπει να ψάξετε μέσα από τα πάντα.

74
00:03:23,446 --> 00:03:25,320
Έτσι, με όλα αυτά τα δεδομένα
δομές θα πάμε

75
00:03:25,320 --> 00:03:29,330
να περάσετε λίγο περισσότερο χρόνο για,
ποια είναι τα συν και τα αρνητικά.

76
00:03:29,330 --> 00:03:31,480
Πότε μπορεί να θέλουμε να
χρησιμοποιήστε ένα πάνω στο άλλο;

77
00:03:31,480 --> 00:03:34,970
Και αυτό είναι το είδος του
μεγαλύτερο πράγμα που πρέπει να πάρει.

78
00:03:34,970 --> 00:03:40,140
>> Έτσι, έχουμε εδώ το
ορισμός ενός κόμβου.

79
00:03:40,140 --> 00:03:43,040
Είναι σαν ένα στοιχείο στο
συνδεδεμένη λίστα μας, σωστά;

80
00:03:43,040 --> 00:03:46,180
Έτσι, είμαστε όλοι εξοικειωμένοι
με structs typedef μας,

81
00:03:46,180 --> 00:03:47,980
το οποίο πήγαμε πάνω στην αναθεώρηση τελευταία φορά.

82
00:03:47,980 --> 00:03:53,180
Ήταν ουσιαστικά μόνο τη δημιουργία
Ένας άλλος τύπος δεδομένων που θα μπορούσαμε να χρησιμοποιήσουμε.

83
00:03:53,180 --> 00:03:57,930
>> Και σε αυτή την περίπτωση, είναι μερικά κόμβο
ότι θα κρατήσει κάποια ακέραιο.

84
00:03:57,930 --> 00:04:00,210
Και τότε ποιο είναι το δεύτερο μέρος εδώ;

85
00:04:00,210 --> 00:04:03,192

86
00:04:03,192 --> 00:04:05,677
Όποιος;

87
00:04:05,677 --> 00:04:06,680
>> ΚΟΙΝΟ: [δεν ακούγεται].

88
00:04:06,680 --> 00:04:07,020
>> ΟΜΙΛΗΤΗΣ 1: Ναι.

89
00:04:07,020 --> 00:04:08,400
Είναι ένας δείκτης στον επόμενο κόμβο.

90
00:04:08,400 --> 00:04:12,610
Έτσι, αυτό θα πρέπει πραγματικά να είναι εδώ.

91
00:04:12,610 --> 00:04:18,790
Αυτό είναι ένας δείκτης τύπου
κόμβος στο επόμενο πράγμα.

92
00:04:18,790 --> 00:04:22,410
Και αυτό είναι ό, τι
περιλαμβάνει τον κόμβο μας.

93
00:04:22,410 --> 00:04:24,060
Cool.

94
00:04:24,060 --> 00:04:29,390
>> Εντάξει, έτσι με την αναζήτηση, όπως ήμασταν
ακριβώς λέει πριν από το χέρι, εάν είστε

95
00:04:29,390 --> 00:04:31,840
πρόκειται να ψάξετε μέσα,
θα πρέπει να επαναλάβει στην πραγματικότητα

96
00:04:31,840 --> 00:04:33,660
μέσω της συνδεδεμένης λίστας σας.

97
00:04:33,660 --> 00:04:38,530
Έτσι, αν ψάχνετε για τον αριθμό
9, θα ξεκινήσει στις κεφάλι μας

98
00:04:38,530 --> 00:04:41,520
και αυτό μας δείχνει στην αρχή
της συνδεδεμένης λίστας μας, σωστά;

99
00:04:41,520 --> 00:04:44,600
Και λέμε, εντάξει, το κάνει αυτό
κόμβος περιέχει τον αριθμό 9;

100
00:04:44,600 --> 00:04:45,690
Όχι;

101
00:04:45,690 --> 00:04:47,500
>> Εντάξει, πάμε στο επόμενο.

102
00:04:47,500 --> 00:04:48,312
Ακολουθήστε αυτό.

103
00:04:48,312 --> 00:04:49,520
Μήπως αυτό περιέχει τον αριθμό 9;

104
00:04:49,520 --> 00:04:50,570
Όχι.

105
00:04:50,570 --> 00:04:51,550
Ακολουθήστε το επόμενο.

106
00:04:51,550 --> 00:04:55,490
>> Έτσι πρέπει να επαναλάβει στην πραγματικότητα
μέσω της συνδεδεμένης λίστας μας.

107
00:04:55,490 --> 00:05:00,070
Δεν μπορούμε απλά να πάμε κατευθείαν εκεί όπου 9 είναι.

108
00:05:00,070 --> 00:05:05,860
Και αν εσείς πραγματικά θέλετε να
δείτε κάποια ψευδο-κώδικα μέχρι εκεί.

109
00:05:05,860 --> 00:05:10,420
Έχουμε κάποια λειτουργία αναζήτησης εδώ
ότι παίρνει in-- τι χρειάζεται σε;

110
00:05:10,420 --> 00:05:13,110

111
00:05:13,110 --> 00:05:14,320
Τι νομίζετε;

112
00:05:14,320 --> 00:05:15,960
Τόσο εύκολο.

113
00:05:15,960 --> 00:05:17,784
Τι είναι αυτό;

114
00:05:17,784 --> 00:05:18,700
ΚΟΙΝΟ: [δεν ακούγεται].

115
00:05:18,700 --> 00:05:20,366
ΟΜΙΛΗΤΗΣ 1: Ο αριθμός που ψάχνουμε.

116
00:05:20,366 --> 00:05:20,980
Σωστά;

117
00:05:20,980 --> 00:05:22,875
Και τι θα ήταν αυτό αντιστοιχεί σε;

118
00:05:22,875 --> 00:05:25,020
Είναι ένας δείκτης για;

119
00:05:25,020 --> 00:05:26,000
>> ΚΟΙΝΟ: Ένας κόμβος.

120
00:05:26,000 --> 00:05:28,980
>> ΟΜΙΛΗΤΗΣ 1: Ένας κόμβος στη λίστα
ότι ψάχνουμε σε, σωστά;

121
00:05:28,980 --> 00:05:33,700
Έτσι έχουμε μερικές κόμβους είναι δείκτης εδώ.

122
00:05:33,700 --> 00:05:37,240
Αυτό είναι ένα σημείο που πρόκειται να
στην πραγματικότητα διέτρεξε τη λίστα μας.

123
00:05:37,240 --> 00:05:39,630
Θέτουμε το ίσο στη λίστα
γιατί αυτό είναι ακριβώς

124
00:05:39,630 --> 00:05:44,380
ότι αυτό ισούται με το
έναρξη της συνδεδεμένης λίστας μας.

125
00:05:44,380 --> 00:05:50,660
>> Και ενώ δεν είναι NULL, ενώ
εξακολουθούμε να έχουμε τα πράγματα στη λίστα μας,

126
00:05:50,660 --> 00:05:55,580
ελέγξτε για να δείτε αν ο κόμβος έχει
ο αριθμός που ψάχνουμε.

127
00:05:55,580 --> 00:05:57,740
Επιστροφή αλήθεια.

128
00:05:57,740 --> 00:06:01,070
Διαφορετικά, θα ενημερώσει, σωστά;

129
00:06:01,070 --> 00:06:04,870
>> Αν είναι NULL, βγαίνουμε μας
ενώ βρόχο και επιστρέφει false

130
00:06:04,870 --> 00:06:08,340
γιατί αυτό σημαίνει ότι δεν έχουν βρεθεί.

131
00:06:08,340 --> 00:06:11,048
Μήπως ο καθένας να πάρει το πώς αυτό λειτουργεί;

132
00:06:11,048 --> 00:06:11,548
ΟΚ.

133
00:06:11,548 --> 00:06:14,940

134
00:06:14,940 --> 00:06:20,260
>> Έτσι, με την εισαγωγή, σας
έχουν τρεις διαφορετικούς τρόπους.

135
00:06:20,260 --> 00:06:25,250
Μπορείτε να προσθέσετε το πρόθεμα, μπορείτε να προσθέσετε
και μπορείτε να τοποθετήσετε σε ανάμικτες.

136
00:06:25,250 --> 00:06:28,215
Σε αυτή την περίπτωση, είμαστε
πρόκειται να κάνει μια βάλε.

137
00:06:28,215 --> 00:06:33,380
Ξέρει κανείς πώς αυτά
τρεις περιπτώσεις ενδέχεται να διαφέρουν;

138
00:06:33,380 --> 00:06:36,920
>> Οπότε βάλε σημαίνει ότι βάζετε
αυτό στο μπροστινό μέρος της λίστας σας.

139
00:06:36,920 --> 00:06:39,770
Έτσι, αυτό θα σήμαινε ότι δεν έχει σημασία
τι κόμβος σας είναι, δεν έχει σημασία

140
00:06:39,770 --> 00:06:43,160
ποια είναι η αξία είναι, θα πάμε
για να το θέσω εδώ μπροστά, εντάξει;

141
00:06:43,160 --> 00:06:45,160
Είναι πρόκειται να είναι η πρώτη
στοιχείο στη λίστα σας.

142
00:06:45,160 --> 00:06:49,510
>> Αν προσάρτησή, πρόκειται
να πάει στο πίσω μέρος της λίστας σας.

143
00:06:49,510 --> 00:06:54,010
Και τοποθετήστε σε ανάμικτες σημαίνει ότι είστε
πρόκειται να θέσει πραγματικά σε θέση

144
00:06:54,010 --> 00:06:57,700
όπου κρατά συνδεδεμένη λίστα σας ταξινομούνται.

145
00:06:57,700 --> 00:07:00,810
Και πάλι, πώς μπορείτε να χρησιμοποιήσετε
εκείνους και όταν χρησιμοποιείτε

146
00:07:00,810 --> 00:07:02,530
τους θα ποικίλλει ανάλογα με την περίπτωσή σας.

147
00:07:02,530 --> 00:07:05,834

148
00:07:05,834 --> 00:07:07,750
Αν δεν χρειάζεται να
να ταξινομηθούν, βάλε τείνει

149
00:07:07,750 --> 00:07:10,460
να είναι αυτό που οι περισσότεροι άνθρωποι
χρησιμοποιούν γιατί δεν το κάνετε

150
00:07:10,460 --> 00:07:15,680
πρέπει να περάσουν από όλη τη λίστα
για να βρείτε το τέλος για να το προσθέσετε στο, σωστά;

151
00:07:15,680 --> 00:07:17,720
Μπορείτε να το κολλήσετε ακριβώς δεξιά μέσα.

152
00:07:17,720 --> 00:07:21,930
>> Έτσι θα πάμε μέσα από μια
εισαγωγή 1 τώρα.

153
00:07:21,930 --> 00:07:26,360
Έτσι, ένα πράγμα που θα πάω να
το συνιστώ ανεπιφύλακτα σε αυτό το chipset

154
00:07:26,360 --> 00:07:29,820
είναι να σχεδιάσετε τα πράγματα έξω, όπως πάντα.

155
00:07:29,820 --> 00:07:35,130
Είναι πολύ σημαντικό να ενημερώσετε
υποδείξεις σας με τη σωστή σειρά

156
00:07:35,130 --> 00:07:38,620
γιατί αν τους ενημερώσετε
ελαφρώς εκτός λειτουργίας,

157
00:07:38,620 --> 00:07:42,210
θα πάμε να καταλήξετε
χάνει τμήματα της λίστας σας.

158
00:07:42,210 --> 00:07:49,680
>> Έτσι, για παράδειγμα, στην περίπτωση αυτή, είμαστε
λέει το κεφάλι ακριβώς σημείο προς 1.

159
00:07:49,680 --> 00:07:56,070
Αν εμείς κάνουμε ότι
χωρίς να αποθηκεύσετε αυτό το 1,

160
00:07:56,070 --> 00:07:58,570
δεν έχουμε καμία ιδέα για το τι
1 πρέπει να επισημάνω τώρα

161
00:07:58,570 --> 00:08:02,490
γιατί έχουμε χάσει ό, τι
το κεφάλι επεσήμανε.

162
00:08:02,490 --> 00:08:05,530
Έτσι, ένα πράγμα που πρέπει να θυμάστε
όταν κάνεις μια βάλε

163
00:08:05,530 --> 00:08:09,630
είναι να σώσει ό, τι το
σημεία της κεφαλής για την πρώτη,

164
00:08:09,630 --> 00:08:15,210
τότε η επανεκχώρηση, και στη συνέχεια να ενημερώσετε
τι νέο κόμβο σας θα πρέπει να επισημάνω.

165
00:08:15,210 --> 00:08:20,870

166
00:08:20,870 --> 00:08:22,560
Σε αυτήν την περίπτωση, αυτός είναι ένας τρόπος για να το κάνουμε.

167
00:08:22,560 --> 00:08:25,440
>> Έτσι, αν είχαμε κάνει αυτό τον τρόπο
όπου εμείς απλά εκ νέου το κεφάλι,

168
00:08:25,440 --> 00:08:30,320
χάνουμε βασικά μας
ολόκληρη τη λίστα, σωστά;

169
00:08:30,320 --> 00:08:38,000
Ένας τρόπος να γίνει αυτό είναι να έχετε 1 σημείο για να
δίπλα, και στη συνέχεια να έχουν το σημείο το κεφάλι προς 1.

170
00:08:38,000 --> 00:08:42,650
Ή μπορείτε να κάνετε κάτι σαν το
προσωρινής αποθήκευσης, τα οποία μίλησα.

171
00:08:42,650 --> 00:08:45,670
>> Αλλά η ανακατανομή σας
δείκτες με τη σωστή σειρά

172
00:08:45,670 --> 00:08:48,750
πρόκειται να είναι πολύ, πολύ
σημαντικό για αυτό το chipset.

173
00:08:48,750 --> 00:08:53,140
Διαφορετικά, θα πάμε να έχουν ένα hash
πίνακα ή μια δοκιμή που είναι ακριβώς πρόκειται να είναι

174
00:08:53,140 --> 00:08:56,014
μέρος μόνο από τις λέξεις που σας
θέλετε και στη συνέχεια mmhmm you're--;

175
00:08:56,014 --> 00:08:58,930
ΚΟΙΝΟ: Ποια ήταν η προσωρινή
πράγμα αποθήκευσης μιλούσατε για;

176
00:08:58,930 --> 00:09:00,305
ΟΜΙΛΗΤΗΣ 1: Η προσωρινή αποθήκευση.

177
00:09:00,305 --> 00:09:02,760
Έτσι, βασικά άλλο
τρόπο θα μπορούσατε να κάνετε αυτό

178
00:09:02,760 --> 00:09:07,650
έχει αποθηκεύσει το κεφάλι του κάτι, όπως
αποθηκεύουν την προσωρινή μεταβλητή.

179
00:09:07,650 --> 00:09:11,250
Αναθέστε το σε 1 και
στη συνέχεια να ενημερώσετε 1 στο σημείο

180
00:09:11,250 --> 00:09:13,830
σε ό, τι το κεφάλι χρησιμοποιείται για να υποδείξει.

181
00:09:13,830 --> 00:09:16,920
Με αυτό τον τρόπο είναι προφανώς
πιο κομψό γιατί

182
00:09:16,920 --> 00:09:20,770
Δεν χρειάζεται μια προσωρινή αξία, αλλά
ακριβώς προσφέρει έναν άλλο τρόπο για να το κάνουμε.

183
00:09:20,770 --> 00:09:23,999

184
00:09:23,999 --> 00:09:25,790
Και πρέπει πραγματικά να κάνουμε έχουν
μερικά κωδικό για αυτό.

185
00:09:25,790 --> 00:09:28,080
Έτσι, για την συνδεδεμένη λίστα, εμείς
έχουν πραγματικά κάποιο κώδικα.

186
00:09:28,080 --> 00:09:31,930
Έτσι, τοποθετήστε εδώ, αυτό προσθέτοντας στην αρχή.

187
00:09:31,930 --> 00:09:34,290
Έτσι, αυτό που μπαίνει στο κεφάλι.

188
00:09:34,290 --> 00:09:38,820
>> Έτσι το πρώτο πράγμα, που πρέπει να
δημιουργήσετε νέο κόμβο σας, φυσικά,

189
00:09:38,820 --> 00:09:40,790
και ελέγξτε για NULL.

190
00:09:40,790 --> 00:09:43,250
Πάντα καλό.

191
00:09:43,250 --> 00:09:47,840
Και τότε θα πρέπει να ορίσετε τις τιμές.

192
00:09:47,840 --> 00:09:51,260
Κάθε φορά που δημιουργείτε ένα νέο κόμβο,
Δεν ξέρω τι είναι να υποδεικνύουν στην επόμενη,

193
00:09:51,260 --> 00:09:54,560
έτσι θέλετε να γίνει η προετοιμασία για την τιμή null.

194
00:09:54,560 --> 00:09:58,760
Αν δεν καταλήγουν επισημαίνοντας κάτι
αλλού, παίρνει εκ νέου και είναι μια χαρά.

195
00:09:58,760 --> 00:10:00,740
Αν αυτό είναι το πρώτο πράγμα
στη λίστα, χρειάζεται

196
00:10:00,740 --> 00:10:04,270
να επισημάνω σε μηδέν, επειδή
αυτό είναι το τέλος της λίστας.

197
00:10:04,270 --> 00:10:12,410
>> Έτσι, στη συνέχεια, να το τοποθετήσετε, βλέπουμε εδώ
Οι εκχώρηση την επόμενη τιμή του κόμβου μας

198
00:10:12,410 --> 00:10:17,380
να είναι ό, τι το κεφάλι είναι,
η οποία είναι ό, τι είχαμε εδώ.

199
00:10:17,380 --> 00:10:19,930
Αυτό είναι ό, τι ακριβώς έκανε.

200
00:10:19,930 --> 00:10:25,820
Και τότε είμαστε ανάθεση κεφάλι στο σημείο
στο νέο κόμβο μας, γιατί θυμηθείτε,

201
00:10:25,820 --> 00:10:31,090
νέα είναι μερικά δείκτη σε έναν κόμβο,
και αυτό ακριβώς είναι το κεφάλι.

202
00:10:31,090 --> 00:10:34,370
Γι 'αυτό ακριβώς είμαστε
έχουν αυτό το βέλος accessor.

203
00:10:34,370 --> 00:10:37,030

204
00:10:37,030 --> 00:10:37,530
Cool;

205
00:10:37,530 --> 00:10:38,130
Mmhmm;

206
00:10:38,130 --> 00:10:41,100
>> ΚΟΙΝΟ: Μήπως πρέπει να
προετοιμάσει νέες δίπλα σε null πρώτη,

207
00:10:41,100 --> 00:10:44,240
ή μπορούμε απλά να γίνει η προετοιμασία για το κεφάλι;

208
00:10:44,240 --> 00:10:48,210
>> ΟΜΙΛΗΤΗΣ 1: Νέα επόμενη
πρέπει να είναι NULL, για να ξεκινήσετε

209
00:10:48,210 --> 00:10:53,760
επειδή δεν ξέρετε
όπου πρόκειται να είναι.

210
00:10:53,760 --> 00:10:56,100
Επίσης, αυτό είναι το είδος του
ήθελα απλώς ένα παράδειγμα.

211
00:10:56,100 --> 00:10:59,900
Μπορείτε να ορίσετε το ίσο με NULL μόνο για να κάνουν
βεβαιωθείτε ότι όλες οι βάσεις σας καλύπτονται

212
00:10:59,900 --> 00:11:04,070
πριν κάνετε οποιαδήποτε αλλαγή, έτσι ώστε
είστε πάντα εγγυημένο ότι θα

213
00:11:04,070 --> 00:11:08,880
να δείχνουν προς μια συγκεκριμένη τιμή
έναντι σαν αξία σκουπίδια.

214
00:11:08,880 --> 00:11:12,210
Διότι, ναι, έχουμε αναθέσει
νέες επόμενη αυτόματα,

215
00:11:12,210 --> 00:11:15,420
αλλά είναι περισσότερο σαν ένα
καλή πρακτική να γίνει η προετοιμασία

216
00:11:15,420 --> 00:11:19,270
με αυτόν τον τρόπο και στη συνέχεια να εκχωρήσετε εκ νέου.

217
00:11:19,270 --> 00:11:23,420
>> Εντάξει, έτσι διπλά συνδεδεμένες λίστες τώρα.

218
00:11:23,420 --> 00:11:24,601
Τι νομίζετε;

219
00:11:24,601 --> 00:11:26,350
Αυτό που είναι διαφορετικό με
διπλά συνδεδεμένες λίστες;

220
00:11:26,350 --> 00:11:30,750

221
00:11:30,750 --> 00:11:34,300
>> Έτσι, σε συνδεδεμένες λίστες μας, μπορούμε
να κινηθούν μόνο προς μία κατεύθυνση, σωστά;

222
00:11:34,300 --> 00:11:35,270
Έχουμε μόνο την επόμενη.

223
00:11:35,270 --> 00:11:36,760
Μπορούμε μόνο να πάμε μπροστά.

224
00:11:36,760 --> 00:11:40,300
>> Με μια διπλά συνδεδεμένη λίστα,
μπορούμε επίσης να κινηθεί προς τα πίσω.

225
00:11:40,300 --> 00:11:44,810
Έτσι δεν έχουμε μόνο το
αριθμό που θέλετε να αποθηκεύσετε,

226
00:11:44,810 --> 00:11:50,110
έχουμε όταν επισημαίνει στην επόμενη
και όπου μόλις ήρθε από.

227
00:11:50,110 --> 00:11:52,865
Έτσι, αυτό επιτρέπει την
κάποια καλύτερη διάσχιση.

228
00:11:52,865 --> 00:11:56,620

229
00:11:56,620 --> 00:12:01,240
>> Έτσι, διπλά συνδεδεμένων κόμβων,
πολύ παρόμοια, σωστά;

230
00:12:01,240 --> 00:12:05,000
Μόνο η διαφορά είναι τώρα
έχουν ένα επόμενο και προηγούμενο.

231
00:12:05,000 --> 00:12:06,235
Είναι η μόνη διαφορά.

232
00:12:06,235 --> 00:12:09,570

233
00:12:09,570 --> 00:12:14,790
>> Έτσι, αν ήμασταν για να προσθέσετε το πρόθεμα ή append-- μας
δεν έχουν κανένα κώδικα για αυτό επάνω here--

234
00:12:14,790 --> 00:12:17,830
αλλά αν ήταν να προσπαθήσουμε και να
τοποθετήστε το, το σημαντικό πράγμα

235
00:12:17,830 --> 00:12:19,980
είναι που πρέπει να κάνετε
ότι είστε ανάθεση

236
00:12:19,980 --> 00:12:23,360
δύο προηγούμενες σας και σας
επόμενο δείκτη σωστά.

237
00:12:23,360 --> 00:12:29,010
Έτσι, σε αυτή την περίπτωση, τι θα κάνατε
όχι μόνο να προετοιμάσει την επόμενη,

238
00:12:29,010 --> 00:12:31,820
θα προετοιμαστεί προηγούμενο.

239
00:12:31,820 --> 00:12:36,960
Αν είμαστε στην κορυφή της λίστας, μπορούμε
θα κάνει όχι μόνο το κεφάλι ίση νέα,

240
00:12:36,960 --> 00:12:41,750
αλλά τα νέα μας τα προηγούμενα θα πρέπει να
στραμμένη προς την κεφαλή, σωστά;

241
00:12:41,750 --> 00:12:43,380
>> Αυτή είναι η μόνη διαφορά.

242
00:12:43,380 --> 00:12:47,200
Και αν θέλετε περισσότερη πρακτική με
αυτά με συνδεδεμένες λίστες, με εισαγωγής,

243
00:12:47,200 --> 00:12:49,900
με τη διαγραφή, με ένθετο
σε μια μεγάλη λίστα,

244
00:12:49,900 --> 00:12:52,670
παρακαλώ ελέγξτε έξω study.cs50.net.

245
00:12:52,670 --> 00:12:54,870
Υπάρχει ένα μάτσο μεγάλες ασκήσεις.

246
00:12:54,870 --> 00:12:55,870
Θα ήθελα να συστήσω ανεπιφύλακτα.

247
00:12:55,870 --> 00:12:59,210
Μακάρι να είχαμε χρόνο να περάσει μέσα τους
αλλά υπάρχει πολλή των δομών δεδομένων

248
00:12:59,210 --> 00:13:01,530
για να περάσει.

249
00:13:01,530 --> 00:13:02,650
>> Εντάξει, έτσι πίνακες κατακερματισμού.

250
00:13:02,650 --> 00:13:07,070
Αυτό είναι ίσως το πιο
χρήσιμο κομμάτι για το chipset σας

251
00:13:07,070 --> 00:13:11,090
εδώ επειδή θα πάμε να είναι
την εφαρμογή ενός από αυτά, ή μια δοκιμή.

252
00:13:11,090 --> 00:13:12,200
Μου αρέσει πραγματικά πίνακες κατακερματισμού.

253
00:13:12,200 --> 00:13:13,110
Είναι αρκετά δροσερό.

254
00:13:13,110 --> 00:13:17,080
>> Έτσι, βασικά, τι
που συμβαίνει είναι ένας πίνακας κατακερματισμού

255
00:13:17,080 --> 00:13:22,050
είναι όταν χρειαζόμαστε πραγματικά ταχεία
εισαγωγή, διαγραφή και αναζήτηση.

256
00:13:22,050 --> 00:13:25,010
Αυτά είναι τα πράγματα που είμαστε
δίνοντας προτεραιότητα σε ένα πίνακα κατακερματισμού.

257
00:13:25,010 --> 00:13:29,500
Μπορούν να πάρουν αρκετά μεγάλο,
αλλά όπως θα δούμε με το προσπαθεί,

258
00:13:29,500 --> 00:13:33,040
υπάρχουν πράγματα που είναι πολύ μεγαλύτερες.

259
00:13:33,040 --> 00:13:38,330
>> Αλλά βασικά, όλα ένα hash
πίνακας είναι μια συνάρτηση κατακερματισμού

260
00:13:38,330 --> 00:13:47,215
ότι σας λέει ποια κουβά για να βάλει κάθε
των δεδομένων σας, καθένα από τα στοιχεία σας σε.

261
00:13:47,215 --> 00:13:51,140
Ένας απλός τρόπος για να σκεφτώ έναν πίνακα κατακερματισμού
είναι ότι είναι απλά κουβάδες των πραγμάτων,

262
00:13:51,140 --> 00:13:51,770
σωστά;

263
00:13:51,770 --> 00:13:59,720
Έτσι, όταν είστε τακτοποιήσει τα πράγματα από
όπως και το πρώτο γράμμα του ονόματός τους,

264
00:13:59,720 --> 00:14:01,820
αυτό είναι το είδος του σαν ένα πίνακα κατακερματισμού.

265
00:14:01,820 --> 00:14:06,180
>> Έτσι, αν ήμουν στην ομάδα σας παιδιά είναι
σε ομάδες όποιος ξεκινά όνομά του

266
00:14:06,180 --> 00:14:11,670
με Α εδώ, ή όποιος είναι τα γενέθλιά
είναι τον Ιανουάριο, Φεβρουάριο, Μάρτιο,

267
00:14:11,670 --> 00:14:15,220
οτιδήποτε άλλο, ότι είναι αποτελεσματικά
δημιουργία ενός πίνακα κατακερματισμού.

268
00:14:15,220 --> 00:14:18,120
Είναι απλά δημιουργώντας κουβάδες ότι
ταξινομήσετε τα στοιχεία σας σε

269
00:14:18,120 --> 00:14:19,520
έτσι ώστε να μπορείτε να τα βρείτε ευκολότερα.

270
00:14:19,520 --> 00:14:22,300
Γι 'αυτόν τον τρόπο, όταν χρειάζομαι
για να βρείτε ένα από εσάς,

271
00:14:22,300 --> 00:14:24,680
Δεν έχω να αναζητήσετε
μέσα από κάθε ένα από τα ονόματά σας.

272
00:14:24,680 --> 00:14:29,490
Μπορώ να είμαι όπως, OH, ξέρω ότι
Γενέθλια Danielle είναι in--

273
00:14:29,490 --> 00:14:30,240
ΚΟΙΝΟ: --April.

274
00:14:30,240 --> 00:14:30,948
ΟΜΙΛΗΤΗΣ 1: Απρίλιο.

275
00:14:30,948 --> 00:14:33,120
Έτσι κοιτάζω τον Απρίλιο μου
κουβά, και με λίγη τύχη,

276
00:14:33,120 --> 00:14:38,270
αυτή θα είναι η μόνη εκεί και
ο χρόνος μου ήταν σταθερή σε αυτή την έννοια,

277
00:14:38,270 --> 00:14:41,230
ενώ αν έχω να κοιτάξουμε
μέσα από ένα σωρό ανθρώπους,

278
00:14:41,230 --> 00:14:43,090
πρόκειται να διαρκέσει πολύ περισσότερο.

279
00:14:43,090 --> 00:14:45,830
Έτσι hash πίνακες είναι πραγματικά μόνο κουβάδες.

280
00:14:45,830 --> 00:14:48,630
Εύκολος τρόπος για να σκεφτώ τους.

281
00:14:48,630 --> 00:14:52,930
>> Έτσι, ένα πολύ σημαντικό πράγμα για
ένα πίνακα κατακερματισμού είναι μια συνάρτηση κατακερματισμού.

282
00:14:52,930 --> 00:14:58,140
Έτσι τα πράγματα που μόλις μίλησα, όπως
πρώτο γράμμα της πρώτης σας όνομα

283
00:14:58,140 --> 00:15:01,450
ή μήνα τα γενέθλιά σας,
αυτά είναι ιδέες που

284
00:15:01,450 --> 00:15:03,070
πραγματικά συσχετίζονται με μια συνάρτηση κατακερματισμού.

285
00:15:03,070 --> 00:15:08,900
Είναι απλά ένας τρόπος για να κριθεί η οποία
Σας κάδο στοιχείο είστε πηγαίνει σε, εντάξει;

286
00:15:08,900 --> 00:15:14,850
Έτσι για αυτό το chipset, μπορείτε να αναζητήσετε
σχεδόν κάθε συνάρτηση κατακερματισμού που θέλετε.

287
00:15:14,850 --> 00:15:16,030
>> Δεν πρέπει να είναι δική σας.

288
00:15:16,030 --> 00:15:21,140
Υπάρχουν μερικά πραγματικά δροσερά αυτά έξω
εκεί που κάνει όλα τα είδη των τρελά μαθηματικά.

289
00:15:21,140 --> 00:15:25,170
Και αν θέλετε να κάνετε σας
ορθογράφος σούπερ γρήγορο,

290
00:15:25,170 --> 00:15:27,620
Θα ήθελα σίγουρα
εξετάσουμε σε ένα από αυτά.

291
00:15:27,620 --> 00:15:32,390
>> Αλλά υπάρχουν επίσης και η
απλές, όπως η υπολογιστική

292
00:15:32,390 --> 00:15:39,010
το άθροισμα των λέξεων, όπως
κάθε γράμμα έχει έναν αριθμό.

293
00:15:39,010 --> 00:15:39,940
Υπολογίστε το ποσό.

294
00:15:39,940 --> 00:15:42,230
Αυτό καθορίζει τον κάδο.

295
00:15:42,230 --> 00:15:45,430
Έχουν, επίσης, τις εύκολες αυτά που
είναι ακριβώς όπως όλα τα Α είναι εδώ,

296
00:15:45,430 --> 00:15:47,050
όλα τα Β είναι εδώ.

297
00:15:47,050 --> 00:15:48,920
Κάθε ένα από αυτά.

298
00:15:48,920 --> 00:15:55,770
>> Βασικά, αυτό σας λέει ακριβώς που
Δείκτης σειρά στοιχείων σας θα πρέπει να πάει σε.

299
00:15:55,770 --> 00:15:58,690
Απλά να αποφασίσει την bucket--
είναι όλα μια συνάρτηση κατακερματισμού είναι.

300
00:15:58,690 --> 00:16:04,180
Έτσι, εδώ έχουμε ένα παράδειγμα το οποίο είναι
μόνο το πρώτο γράμμα του string

301
00:16:04,180 --> 00:16:05,900
ότι ήμουν ακριβώς μιλάμε.

302
00:16:05,900 --> 00:16:11,900
>> Έτσι έχετε κάποια hash που είναι ακριβώς η
πρώτο γράμμα της συμβολοσειράς σας μείον Α,

303
00:16:11,900 --> 00:16:16,090
το οποίο θα σας δώσει μερικές
αριθμός μεταξύ 0 και 25.

304
00:16:16,090 --> 00:16:20,790
Και ό, τι θέλετε να κάνετε είναι να
βεβαιωθείτε ότι αυτό αντιπροσωπεύει

305
00:16:20,790 --> 00:16:24,110
το μέγεθος του κατακερματισμού σας table--
πόσοι κάδοι υπάρχουν.

306
00:16:24,110 --> 00:16:25,860
Με πολλά από αυτά
hash λειτουργίες, είναι

307
00:16:25,860 --> 00:16:31,630
πρόκειται να επιστρέφουν τιμές που θα μπορούσαν να
είναι πολύ πάνω από τον αριθμό των κάδων

308
00:16:31,630 --> 00:16:33,610
ότι έχετε πραγματικά
στον πίνακα κατακερματισμού σας,

309
00:16:33,610 --> 00:16:37,240
έτσι πρέπει να κάνετε
βέβαιος και mod από αυτούς.

310
00:16:37,240 --> 00:16:42,190
Διαφορετικά, πρόκειται να πει,
Ω, θα πρέπει να είναι σε κάδο 5.000

311
00:16:42,190 --> 00:16:46,040
αλλά έχετε μόνο 30
κουβάδες στον πίνακα κατακερματισμού σας.

312
00:16:46,040 --> 00:16:49,360
Και φυσικά, όλοι γνωρίζουμε ότι είναι
πρόκειται να οδηγήσει σε κάποια τρελά λάθη.

313
00:16:49,360 --> 00:16:52,870
Γι 'αυτό φροντίστε να mod από το
το μέγεθος του πίνακα κατακερματισμού σας.

314
00:16:52,870 --> 00:16:58,430

315
00:16:58,430 --> 00:16:58,930
Cool.

316
00:16:58,930 --> 00:17:00,506
Έτσι συγκρούσεις.

317
00:17:00,506 --> 00:17:02,620
Είναι όλοι καλά μέχρι στιγμής;

318
00:17:02,620 --> 00:17:03,120
Mmhmm;

319
00:17:03,120 --> 00:17:05,900
>> ΚΟΙΝΟ: Γιατί θα ήταν
επιστρέφει μια τέτοια μαζική τιμή;

320
00:17:05,900 --> 00:17:09,210
>> ΟΜΙΛΗΤΗΣ 1: Ανάλογα με τον αλγόριθμο
ότι η συνάρτηση κατακερματισμού σας χρησιμοποιεί.

321
00:17:09,210 --> 00:17:12,270
Μερικοί απ 'αυτούς θα κάνουμε
τρελό πολλαπλασιασμό.

322
00:17:12,270 --> 00:17:16,270
Και είναι όλα για να πάρει
μια ομοιόμορφη κατανομή,

323
00:17:16,270 --> 00:17:18,490
έτσι ώστε να κάνουν κάποια πραγματικά
τρελά πράγματα μερικές φορές.

324
00:17:18,490 --> 00:17:20,960
Αυτό είναι όλο.

325
00:17:20,960 --> 00:17:22,140
Οτιδήποτε άλλο;

326
00:17:22,140 --> 00:17:22,829
ΟΚ.

327
00:17:22,829 --> 00:17:24,480
>> Έτσι συγκρούσεις.

328
00:17:24,480 --> 00:17:29,270
Βασικά, όπως είπα και προηγουμένως,
στην καλύτερη περίπτωση,

329
00:17:29,270 --> 00:17:32,040
κάθε κάδο κοιτάζω μέσα είναι
πρόκειται να έχουν ένα πράγμα,

330
00:17:32,040 --> 00:17:34,160
οπότε δεν έχω να εξετάσουμε όλα, σωστά;

331
00:17:34,160 --> 00:17:37,040
Ι είτε ξέρουν ότι είναι εκεί ή είναι
όχι, και αυτό είναι που θέλουμε πραγματικά.

332
00:17:37,040 --> 00:17:43,960
Αλλά αν έχουμε δεκάδες χιλιάδες
σημεία δεδομένων και μικρότερη από αυτόν τον αριθμό

333
00:17:43,960 --> 00:17:48,700
κάδων, θα πάμε να έχουν
συγκρούσεις όπου τελικά κάτι

334
00:17:48,700 --> 00:17:54,210
θα πρέπει να καταλήξουν σε μια
κουβά που έχει ήδη ένα στοιχείο.

335
00:17:54,210 --> 00:17:57,390
>> Έτσι, το ερώτημα είναι, τι
μπορούμε να κάνουμε σε αυτή την περίπτωση;

336
00:17:57,390 --> 00:17:58,480
Τι πρέπει να κάνουμε;

337
00:17:58,480 --> 00:17:59,300
Έχουμε ήδη κάτι εκεί;

338
00:17:59,300 --> 00:18:00,060
Μήπως εμείς απλά το ρίξει έξω;

339
00:18:00,060 --> 00:18:00,700
>> Όχι.

340
00:18:00,700 --> 00:18:01,980
Πρέπει να κρατήσει και τους δύο.

341
00:18:01,980 --> 00:18:06,400
Έτσι ο τρόπος που εμείς
συνήθως το κάνουμε αυτό είναι ό, τι;

342
00:18:06,400 --> 00:18:08,400
Ποια είναι η δομή δεδομένων
εμείς απλά μίλησε;

343
00:18:08,400 --> 00:18:09,316
ΚΟΙΝΟ: συνδεδεμένη λίστα.

344
00:18:09,316 --> 00:18:10,500
ΟΜΙΛΗΤΗΣ 1: Μια συνδεδεμένη λίστα.

345
00:18:10,500 --> 00:18:16,640
Έτσι τώρα, αντί για κάθε ένα από αυτά
κουβάδες έχοντας μόλις ένα στοιχείο,

346
00:18:16,640 --> 00:18:24,020
πρόκειται να περιέχει μια συνδεδεμένη λίστα
τα στοιχεία που κατακερματίζεται σε αυτό.

347
00:18:24,020 --> 00:18:27,588
Εντάξει, ο καθένας έχει το είδος του να πάρει αυτή την ιδέα;

348
00:18:27,588 --> 00:18:30,546
Επειδή εμείς δεν θα μπορούσε να έχει μια σειρά
γιατί δεν ξέρουμε πόσα πράγματα

349
00:18:30,546 --> 00:18:31,730
πρόκειται να είναι εκεί.

350
00:18:31,730 --> 00:18:36,540
Μια συνδεδεμένη λίστα μας επιτρέπει να
έχουν ακριβώς τον ακριβή αριθμό στον οποίο οι

351
00:18:36,540 --> 00:18:38,465
Οι κατακερματίζεται σε αυτό το κουβά, σωστά;

352
00:18:38,465 --> 00:18:42,260

353
00:18:42,260 --> 00:18:50,500
>> Έτσι γραμμική σχολαστικά είναι
βασικά αυτό idea--

354
00:18:50,500 --> 00:18:52,300
Είναι ένας τρόπος για να ασχοληθεί με μια σύγκρουση.

355
00:18:52,300 --> 00:18:58,010
Τι μπορείτε να κάνετε είναι αν, σε αυτό το
περίπτωση, μούρο ήταν κατακερματισμένο σε 1

356
00:18:58,010 --> 00:19:01,130
και έχουμε ήδη
κάτι εκεί, απλά

357
00:19:01,130 --> 00:19:04,840
συνεχίστε προς τα κάτω έως ότου
μπορείτε να βρείτε μια κενή υποδοχή.

358
00:19:04,840 --> 00:19:06,370
Αυτός είναι ένας τρόπος για να το χειριστεί.

359
00:19:06,370 --> 00:19:09,020
Ο άλλος τρόπος για να χειριστεί
είναι με αυτό που μόλις

360
00:19:09,020 --> 00:19:12,280
called-- το συνδεδεμένο
Λίστα λέγεται αλυσιδωτή σύνδεση.

361
00:19:12,280 --> 00:19:20,510
>> Έτσι, η ιδέα αυτή λειτουργεί αν
πίνακα κατακερματισμού σας νομίζετε

362
00:19:20,510 --> 00:19:24,150
είναι πολύ μεγαλύτερο από
σύνολο των δεδομένων σας ή αν έχετε

363
00:19:24,150 --> 00:19:28,870
θέλετε να δοκιμάσετε και την ελαχιστοποίηση αλυσιδωτή σύνδεση
μέχρι να είναι απολύτως απαραίτητο.

364
00:19:28,870 --> 00:19:34,050
Έτσι, ένα πράγμα είναι γραμμική
σχολαστικά προφανώς σημαίνει

365
00:19:34,050 --> 00:19:37,290
ότι η συνάρτηση κατακερματισμού σας
δεν είναι τόσο χρήσιμα

366
00:19:37,290 --> 00:19:42,200
επειδή θα πάμε να καταλήξετε με
συνάρτηση κατακερματισμού σας, να πάρει σε ένα σημείο,

367
00:19:42,200 --> 00:19:46,400
μπορείτε γραμμικό καθετήρα προς τα κάτω για να
κάποια θέση που είναι διαθέσιμες.

368
00:19:46,400 --> 00:19:49,670
Αλλά τώρα, φυσικά, τίποτα
άλλο που καταλήγει εκεί,

369
00:19:49,670 --> 00:19:52,050
εσείς πρόκειται να πρέπει να
αναζήτηση ακόμη πιο κάτω.

370
00:19:52,050 --> 00:19:55,650
>> Και υπάρχουν πολλά περισσότερα
δαπάνη αναζήτησης που

371
00:19:55,650 --> 00:19:59,820
πηγαίνει στην εισαγωγή ενός στοιχείου
στον πίνακα κατακερματισμού σας τώρα, σωστά;

372
00:19:59,820 --> 00:20:05,640
Και τώρα, όταν θα πάτε και να προσπαθήσουμε και να βρούμε
μούρο και πάλι, θα πάμε να το hash,

373
00:20:05,640 --> 00:20:07,742
και πρόκειται να πω,
Ω, κοιτάξτε στον κάδο 1,

374
00:20:07,742 --> 00:20:09,700
και δεν πρόκειται να είναι
σε κάδο 1, ώστε να είστε

375
00:20:09,700 --> 00:20:11,970
πρόκειται να πρέπει να διασχίσει
μέσω του υπολοίπου αυτών.

376
00:20:11,970 --> 00:20:17,720
Έτσι είναι μερικές φορές χρήσιμο,
αλλά στις περισσότερες περιπτώσεις,

377
00:20:17,720 --> 00:20:22,660
θα πάμε να πούμε ότι
αλυσοποίησης είναι ό, τι θέλετε να κάνετε.

378
00:20:22,660 --> 00:20:25,520
>> Έτσι μιλήσαμε για το θέμα αυτό νωρίτερα.

379
00:20:25,520 --> 00:20:27,812
Πήρα λίγο μπροστά από τον εαυτό μου.

380
00:20:27,812 --> 00:20:33,560
Αλλά αλυσοποίησης είναι βασικά ότι
κάθε κουβά στον πίνακα κατακερματισμού σας

381
00:20:33,560 --> 00:20:36,120
είναι απλά μια συνδεδεμένη λίστα.

382
00:20:36,120 --> 00:20:39,660
>> Έτσι, ένας άλλος τρόπος, ή πιο τεχνική
τρόπο, να σκεφτούμε ένα πίνακα κατακερματισμού

383
00:20:39,660 --> 00:20:44,490
είναι ότι είναι απλά μια σειρά
από συνδεδεμένες λίστες, οι οποίες

384
00:20:44,490 --> 00:20:49,330
όταν γράφετε λεξικό σας
και προσπαθείτε να το φορτώσετε,

385
00:20:49,330 --> 00:20:52,070
σκέφτεται ως ένα
σειρά από συνδεδεμένες λίστες

386
00:20:52,070 --> 00:20:54,390
θα καταστήσει πολύ πιο εύκολο
για να προετοιμαστεί.

387
00:20:54,390 --> 00:20:57,680
>> ΚΟΙΝΟ: Έτσι πίνακα κατακερματισμού
έχει ένα προκαθορισμένο μέγεθος,

388
00:20:57,680 --> 00:20:58,980
σαν [δεν ακούγεται] κάδων;

389
00:20:58,980 --> 00:20:59,220
>> ΟΜΙΛΗΤΗΣ 1: Δεξιά.

390
00:20:59,220 --> 00:21:01,655
Γι 'αυτό έχει ένα συγκεκριμένο αριθμό
κάδων που determine--

391
00:21:01,655 --> 00:21:03,530
οποία εσείς πρέπει να
αισθανθείτε ελεύθερος να παίξει με.

392
00:21:03,530 --> 00:21:05,269
Μπορεί να είναι αρκετά δροσερό
για να δούμε τι θα συμβεί

393
00:21:05,269 --> 00:21:06,810
όπως μπορείτε να αλλάξετε τον αριθμό σας κάδων.

394
00:21:06,810 --> 00:21:09,410

395
00:21:09,410 --> 00:21:11,510
Αλλά ναι, θα έχει ένα
ορίσετε τον αριθμό των κάδων.

396
00:21:11,510 --> 00:21:15,360
Αυτό σας επιτρέπει να χωρέσει ως
πολλά στοιχεία που χρειάζεστε

397
00:21:15,360 --> 00:21:19,350
είναι αυτό Ξεχωριστές αλυσίδες, όπου μπορείτε
Οι συνδεδεμένες λίστες σε κάθε κάδο.

398
00:21:19,350 --> 00:21:22,850
Αυτό σημαίνει πίνακα κατακερματισμού σας
θα είναι ακριβώς το μέγεθος

399
00:21:22,850 --> 00:21:25,440
ότι θα πρέπει να είναι, σωστά;

400
00:21:25,440 --> 00:21:27,358
Αυτό είναι το νόημα της συνδεδεμένες λίστες.

401
00:21:27,358 --> 00:21:30,850

402
00:21:30,850 --> 00:21:32,480
Cool.

403
00:21:32,480 --> 00:21:38,780
>> Έτσι, ο καθένας ΟΚ εκεί;

404
00:21:38,780 --> 00:21:39,801
Εντάξει.

405
00:21:39,801 --> 00:21:40,300
Αχ.

406
00:21:40,300 --> 00:21:41,860
Τι ακριβώς συνέβη;

407
00:21:41,860 --> 00:21:42,960
Πραγματικά τώρα.

408
00:21:42,960 --> 00:21:45,250
Μαντέψτε κάποιος με σκοτώνει.

409
00:21:45,250 --> 00:21:52,060
>> Εντάξει θα πάμε για να πάει σε
προσπάθειες, οι οποίες είναι λίγο τρελός.

410
00:21:52,060 --> 00:21:53,140
Μου αρέσει πίνακες κατακερματισμού.

411
00:21:53,140 --> 00:21:54,460
Νομίζω ότι είναι πραγματικά δροσερό.

412
00:21:54,460 --> 00:21:56,710
Προσπαθεί είναι δροσερό, πάρα πολύ.

413
00:21:56,710 --> 00:21:59,590
>> Έτσι κάνει κάποιος που θυμάται τι μια δοκιμή είναι;

414
00:21:59,590 --> 00:22:01,740
Θα πρέπει να έχουν περάσει πάνω
εν συντομία σε διάλεξη;

415
00:22:01,740 --> 00:22:04,570

416
00:22:04,570 --> 00:22:06,377
Θυμάστε το είδος του πώς λειτουργεί;

417
00:22:06,377 --> 00:22:08,460
ΚΟΙΝΟ: Είμαι απλά κουνώντας
ότι εμείς δεν πάμε πάνω από αυτό.

418
00:22:08,460 --> 00:22:09,626
ΟΜΙΛΗΤΗΣ 1: Εμείς δεν πάει πέρα ​​από αυτό.

419
00:22:09,626 --> 00:22:13,100
Εντάξει, είμαστε πραγματικά πρόκειται να πάει
πάνω από αυτό τώρα είναι αυτό που λέμε.

420
00:22:13,100 --> 00:22:14,860
>> ΚΟΙΝΟ: Αυτό είναι ένα δέντρο ανάκτησης.

421
00:22:14,860 --> 00:22:15,280
>> ΟΜΙΛΗΤΗΣ 1: Ναι.

422
00:22:15,280 --> 00:22:16,196
Είναι ένα δέντρο ανάκτησης.

423
00:22:16,196 --> 00:22:16,960
Awesome.

424
00:22:16,960 --> 00:22:23,610
Έτσι, ένα πράγμα που πρέπει να παρατηρήσετε εδώ είναι ότι εμείς
Ψάχνουμε σε μεμονωμένους χαρακτήρες

425
00:22:23,610 --> 00:22:24,480
εδώ, σωστά;

426
00:22:24,480 --> 00:22:29,710
>> Έτσι, πριν με συνάρτηση κατακερματισμού μας,
έψαχναν τις λέξεις ως σύνολο,

427
00:22:29,710 --> 00:22:32,270
και τώρα ψάχνουμε περισσότερο
στους χαρακτήρες, σωστά;

428
00:22:32,270 --> 00:22:38,380
Έτσι έχουμε Maxwell εδώ και Μέντελ.

429
00:22:38,380 --> 00:22:47,840
Έτσι ουσιαστικά ένα try-- ένας τρόπος να σκεφτούμε
για αυτό είναι ότι κάθε επίπεδο εδώ

430
00:22:47,840 --> 00:22:49,000
Είναι μια σειρά από γράμματα.

431
00:22:49,000 --> 00:22:53,310

432
00:22:53,310 --> 00:22:55,790
Έτσι, αυτή είναι η ρίζα του κόμβου σας εδώ, σωστά;

433
00:22:55,790 --> 00:23:01,980
Αυτό έχει όλους τους χαρακτήρες του
αλφάβητο για την έναρξη της κάθε λέξης.

434
00:23:01,980 --> 00:23:06,480
>> Και ό, τι θέλετε να κάνετε είναι να
ας πούμε, εντάξει, έχουμε κάποια λέξη Μ.

435
00:23:06,480 --> 00:23:10,590
Εμείς πάμε να δούμε για Maxwell, έτσι
πάμε στο Μ Και Μ σημεία σε όλη την

436
00:23:10,590 --> 00:23:14,800
άλλα ένας πίνακας όπου κάθε
λέξη, εφ 'όσον υπάρχει

437
00:23:14,800 --> 00:23:17,044
Είναι μια λέξη που έχει ένα
ως τη δεύτερη επιστολή,

438
00:23:17,044 --> 00:23:19,460
εφ 'όσον υπάρχει μια λέξη που
Β έχει ως δεύτερη επιστολή,

439
00:23:19,460 --> 00:23:24,630
θα έχει ένα δείκτη
πηγαίνει σε κάποιο επόμενο πίνακα.

440
00:23:24,630 --> 00:23:29,290
>> Μάλλον δεν υπάρχει μια
λέξη που MP κάτι,

441
00:23:29,290 --> 00:23:32,980
έτσι ώστε στη θέση Ρ σε αυτό
σειρά, θα ήταν απλώς να NULL.

442
00:23:32,980 --> 00:23:38,840
Θα πω, εντάξει, δεν υπάρχει λέξη
ότι έχει Μ ακολουθούμενη από μια P, εντάξει;

443
00:23:38,840 --> 00:23:43,100
Έτσι, αν το σκεφτούμε, κάθε
ένα από αυτά τα μικρότερα πράγματα

444
00:23:43,100 --> 00:23:47,990
είναι στην πραγματικότητα μία από αυτές
μεγάλες συστοιχίες από το Α έως το Z.

445
00:23:47,990 --> 00:23:55,064
Λοιπόν, τι θα μπορούσε να είναι ένα από τα πράγματα
αυτό είναι το είδος της ένα μειονέκτημα μια δοκιμή;

446
00:23:55,064 --> 00:23:56,500
>> ΚΟΙΝΟ: Μια πολλή μνήμη.

447
00:23:56,500 --> 00:23:59,940
>> ΟΜΙΛΗΤΗΣ 1: Είναι ένας τόνος της μνήμης, σωστά;

448
00:23:59,940 --> 00:24:08,750
Κάθε ένα από αυτά τα μπλοκ εδώ
αντιπροσωπεύει 26 θέσεις, 26 στοιχείο του πίνακα.

449
00:24:08,750 --> 00:24:13,680
Έτσι, προσπαθεί να πάρει απίστευτα χώρο βαρύ.

450
00:24:13,680 --> 00:24:17,100
>> Αλλά είναι πολύ γρήγορη.

451
00:24:17,100 --> 00:24:22,540
Έτσι απίστευτα γρήγορα, αλλά
Πραγματικά χώρο αναποτελεσματική.

452
00:24:22,540 --> 00:24:24,810
Είδος πρέπει να υπολογίσετε
από τα οποία το ένα που θέλετε.

453
00:24:24,810 --> 00:24:29,470
Αυτά είναι πραγματικά δροσερό για το chipset σας,
αλλά καταλαμβάνουν πολλή μνήμη,

454
00:24:29,470 --> 00:24:30,290
έτσι ώστε να ανταλλάξει.

455
00:24:30,290 --> 00:24:31,480
Ναι;

456
00:24:31,480 --> 00:24:34,300
>> ΚΟΙΝΟ: Θα ήταν δυνατόν
να δημιουργήσει μια δοκιμή και στη συνέχεια

457
00:24:34,300 --> 00:24:37,967
Μόλις έχετε όλα τα
δεδομένα σε αυτό που σας need--

458
00:24:37,967 --> 00:24:39,550
Δεν ξέρω αν αυτό θα είχε νόημα.

459
00:24:39,550 --> 00:24:42,200
Ήμουν να απαλλαγούμε από όλα τα
NULL χαρακτήρες, αλλά στη συνέχεια,

460
00:24:42,200 --> 00:24:42,910
δεν θα είναι σε θέση να δείκτη them--

461
00:24:42,910 --> 00:24:43,275
>> ΟΜΙΛΗΤΗΣ 1: Μπορείτε ακόμα να τους χρειάζονται.

462
00:24:43,275 --> 00:24:44,854
>> ΚΟΙΝΟ: - με τον ίδιο τρόπο κάθε φορά.

463
00:24:44,854 --> 00:24:45,520
ΟΜΙΛΗΤΗΣ 1: Ναι.

464
00:24:45,520 --> 00:24:50,460
Χρειάζεται η μηδενική χαρακτήρες για να αφήσει
ξέρετε αν δεν υπάρχει μια λέξη.

465
00:24:50,460 --> 00:24:52,040
Ben είχατε κάτι που θέλετε;

466
00:24:52,040 --> 00:24:52,540
ΟΚ.

467
00:24:52,540 --> 00:24:54,581
Εντάξει, έτσι θα πάμε
για να πάει λίγο πιο

468
00:24:54,581 --> 00:24:58,920
σε τεχνικές λεπτομέρειες πίσω
μια δοκιμή και να εργαστούν μέσα από ένα παράδειγμα.

469
00:24:58,920 --> 00:25:01,490
>> Εντάξει, έτσι αυτό είναι το ίδιο πράγμα.

470
00:25:01,490 --> 00:25:06,290
Ενώ σε μια συνδεδεμένη λίστα, κύρια μας
είδος of-- ποια είναι η λέξη που θέλω; -

471
00:25:06,290 --> 00:25:08,350
όπως η κατασκευή μπλοκ ήταν ένας κόμβος.

472
00:25:08,350 --> 00:25:12,280
Σε μια δοκιμή, έχουμε επίσης ένα κόμβο,
αλλά είναι ορίζεται διαφορετικά.

473
00:25:12,280 --> 00:25:17,000
>> Έτσι έχουμε κάποια bool ότι
αντιπροσωπεύει το αν μια λέξη στην πραγματικότητα

474
00:25:17,000 --> 00:25:23,530
υφίσταται σε αυτή τη θέση, και στη συνέχεια
έχουμε κάποια σειρά here-- ή μάλλον,

475
00:25:23,530 --> 00:25:27,840
Αυτό είναι ένας δείκτης σε μια
σειρά 27 χαρακτήρων.

476
00:25:27,840 --> 00:25:33,339
Και αυτό είναι, στην περίπτωση αυτή, αυτό
27-- Είμαι βέβαιος ότι όλοι σας είστε όπως, περιμένετε,

477
00:25:33,339 --> 00:25:34,880
υπάρχουν 26 γράμματα του αλφαβήτου.

478
00:25:34,880 --> 00:25:36,010
Γιατί έχουμε 27;

479
00:25:36,010 --> 00:25:37,870
>> Έτσι, ανάλογα με το
τρόπο που εφαρμόζουν αυτό,

480
00:25:37,870 --> 00:25:43,240
Αυτό είναι από ένα PSET ότι
επιτρέπεται για αποστρόφους.

481
00:25:43,240 --> 00:25:46,010
Έτσι, γι 'αυτό η επιπλέον μία.

482
00:25:46,010 --> 00:25:50,500
Θα πρέπει, επίσης, σε ορισμένες
περιπτώσεις η μηδενική τερματισμού

483
00:25:50,500 --> 00:25:53,230
περιλαμβάνεται ως ένα από τα
χαρακτήρων που του επιτρέπεται να είναι,

484
00:25:53,230 --> 00:25:56,120
και αυτό είναι το πώς να ελέγχετε
να δούμε αν είναι το τέλος της λέξης.

485
00:25:56,120 --> 00:26:01,340
Αν σας ενδιαφέρει, ελέγξτε
Βίντεο του Kevin για study.cs50,

486
00:26:01,340 --> 00:26:04,790
καθώς και η Wikipedia έχει
μερικές καλές πόρους εκεί.

487
00:26:04,790 --> 00:26:09,000
>> Αλλά θα πάμε να περάσουν ακριβώς το είδος
για το πώς θα μπορούσε να λειτουργήσει μέσα από μια δοκιμή

488
00:26:09,000 --> 00:26:11,010
αν σας δίνεται μία.

489
00:26:11,010 --> 00:26:16,230
Έτσι έχουμε ένα σούπερ απλό εδώ ότι
έχει την ένδειξη "νυχτερίδα" και "ζουμ" σε αυτά.

490
00:26:16,230 --> 00:26:18,920
Και όπως βλέπουμε εδώ,
αυτό το μικρό χώρο εδώ

491
00:26:18,920 --> 00:26:22,560
αντιπροσωπεύει bool μας ότι
λέει, ναι, αυτό είναι μια λέξη.

492
00:26:22,560 --> 00:26:27,060
Και τότε αυτό έχει μας
συστοιχίες των χαρακτήρων, σωστά;

493
00:26:27,060 --> 00:26:33,480
>> Γι 'αυτό και πρόκειται να περάσουν από
εύρεση "νυχτερίδα" σε αυτή την προσπάθεια.

494
00:26:33,480 --> 00:26:38,340
Έτσι αρχίζουν στην κορυφή, δεξιά;

495
00:26:38,340 --> 00:26:46,290
Και γνωρίζουμε ότι η Β αντιστοιχεί στο
ο δεύτερος δείκτης, το δεύτερο στοιχείο

496
00:26:46,290 --> 00:26:47,840
σε αυτή την συστοιχία, διότι a και b.

497
00:26:47,840 --> 00:26:51,340
Έτσι, περίπου το δεύτερο.

498
00:26:51,340 --> 00:26:58,820
>> Και λέει, εντάξει, δροσερό, έπεται ότι σε
η επόμενη σειρά, γιατί αν θυμόμαστε,

499
00:26:58,820 --> 00:27:02,160
δεν είναι ότι κάθε ένα από αυτά
πράγματι περιέχει το στοιχείο.

500
00:27:02,160 --> 00:27:07,110
Κάθε μία από αυτές τις συστοιχίες
περιέχει ένα δείκτη, σωστά;

501
00:27:07,110 --> 00:27:10,030
Είναι μια σημαντική διάκριση να κάνει.

502
00:27:10,030 --> 00:27:13,450
>> Ξέρω ότι αυτό πρόκειται να be-- προσπαθεί είναι
πραγματικά σκληρά για να πάρει την πρώτη φορά,

503
00:27:13,450 --> 00:27:15,241
έτσι ώστε ακόμη και αν αυτή είναι η
δεύτερη ή τρίτη φορά

504
00:27:15,241 --> 00:27:18,370
και εξακολουθεί να είναι το είδος
της φαινομενικά δύσκολο,

505
00:27:18,370 --> 00:27:21,199
Υπόσχομαι αν πάτε ρολόι
η σύντομη και πάλι αύριο,

506
00:27:21,199 --> 00:27:22,740
αυτό θα κάνει πιθανότατα πολύ πιο λογικό.

507
00:27:22,740 --> 00:27:23,890
Χρειάζονται πολλά για να χωνέψει.

508
00:27:23,890 --> 00:27:27,800
Έχω ακόμα μερικές φορές είμαι
όπως, περιμένετε, τι είναι μια δοκιμή;

509
00:27:27,800 --> 00:27:29,080
Πώς μπορώ να χρησιμοποιήσω αυτό;

510
00:27:29,080 --> 00:27:33,880
>> Έτσι, έχουμε Β σε αυτή την περίπτωση,
το οποίο είναι το δεύτερο δείκτη μας.

511
00:27:33,880 --> 00:27:40,240
Αν είχαμε, ας πούμε, γ ή
δ ή οποιοδήποτε άλλο έγγραφο,

512
00:27:40,240 --> 00:27:45,810
θα πρέπει να χάρτη που πίσω στο ευρετήριο
της σειρά μας ότι αντιστοιχεί σε.

513
00:27:45,810 --> 00:27:56,930
Έτσι, θα μπορέσουμε να κάνουμε σαν rchar και εμείς απλά
αφαιρούμε ένα για να χαρτογραφήσει σε 0 έως 25.

514
00:27:56,930 --> 00:27:58,728
Όλοι καλά πώς μπορούμε
χάρτης χαρακτήρες μας;

515
00:27:58,728 --> 00:28:00,440
ΟΚ.

516
00:28:00,440 --> 00:28:05,980
>> Έτσι πάμε στο δεύτερο και εμείς
βλέπουμε ότι, ναι, δεν είναι σε NULL.

517
00:28:05,980 --> 00:28:07,780
Μπορούμε να προχωρήσουμε σε αυτή την επόμενη σειρά.

518
00:28:07,780 --> 00:28:12,300
Έτσι, πάμε στην επόμενη αυτή σειρά εδώ.

519
00:28:12,300 --> 00:28:15,500
>> Και λέμε, εντάξει, τώρα είμαστε
Πρέπει να δούμε αν ένας είναι εδώ.

520
00:28:15,500 --> 00:28:18,590
Είναι μια μηδενική ή μήπως
πραγματικά να προχωρήσουμε;

521
00:28:18,590 --> 00:28:21,880
Έτσι, μια πραγματικότητα κινείται
διαβιβάζει σε αυτήν την σειρά.

522
00:28:21,880 --> 00:28:24,570
Και λέμε, εντάξει, t είναι η τελευταία επιστολή μας.

523
00:28:24,570 --> 00:28:27,580
Έτσι πάμε στο t στο δείκτη.

524
00:28:27,580 --> 00:28:30,120
Και τότε θα προχωρήσουμε
επειδή υπάρχει ένα άλλο.

525
00:28:30,120 --> 00:28:38,340
Και αυτό λέει βασικά ότι, ναι,
λέει ότι υπάρχει μια λέξη here--

526
00:28:38,340 --> 00:28:41,750
ότι αν ακολουθήσετε αυτό
μονοπάτι, που έχουν φθάσει

527
00:28:41,750 --> 00:28:43,210
σε μια λέξη, η οποία γνωρίζουμε ότι είναι "νυχτερίδα".

528
00:28:43,210 --> 00:28:43,800
Ναι;

529
00:28:43,800 --> 00:28:46,770
>> ΚΟΙΝΟ: Είναι πρότυπο για να έχει ότι
ως δείκτη 0 και στη συνέχεια να έχουν ένα είδος σε 1

530
00:28:46,770 --> 00:28:47,660
ή να έχουν στο τέλος;

531
00:28:47,660 --> 00:28:48,243
>> ΟΜΙΛΗΤΗΣ 1: Όχι.

532
00:28:48,243 --> 00:28:55,360
Έτσι, αν κοιτάξουμε πίσω σε μας
δήλωση εδώ, είναι μια bool,

533
00:28:55,360 --> 00:28:59,490
γι 'αυτό είναι δική του στοιχείο στον κόμβο σας.

534
00:28:59,490 --> 00:29:03,331
Έτσι δεν είναι μέρος της συστοιχίας.

535
00:29:03,331 --> 00:29:03,830
Cool.

536
00:29:03,830 --> 00:29:08,370
Έτσι, όταν θα τελειώσει το λόγο μας και είμαστε
σε αυτή τη σειρά, αυτό που θέλουμε να κάνουμε

537
00:29:08,370 --> 00:29:12,807
είναι να κάνει έναν έλεγχο για αυτό είναι μια λέξη.

538
00:29:12,807 --> 00:29:14,390
Και σε αυτή την περίπτωση, θα επιστρέψει ναι.

539
00:29:14,390 --> 00:29:17,220

540
00:29:17,220 --> 00:29:24,090
>> Έτσι, σε αυτό το σημείωμα, γνωρίζουμε ότι "ζωολογικός κήπος" -
γνωρίζουμε ως άνθρωποι ότι "ζωολογικός κήπος" είναι μια λέξη,

541
00:29:24,090 --> 00:29:24,820
σωστά;

542
00:29:24,820 --> 00:29:28,990
Αλλά προσπαθήστε εδώ θα
λένε, όχι, δεν είναι.

543
00:29:28,990 --> 00:29:33,980
Και θα έλεγα ότι επειδή εμείς
Δεν έχουν οριστεί ως μια λέξη εδώ.

544
00:29:33,980 --> 00:29:40,440
Ακόμα κι αν μπορούμε να διασχίζουν
μέσα σε αυτό το φάσμα,

545
00:29:40,440 --> 00:29:43,890
Αυτή η δοκιμή θα έλεγα ότι, όχι,
ζωολογικός κήπος δεν είναι στο λεξικό σας

546
00:29:43,890 --> 00:29:47,070
γιατί δεν έχουμε
ορίζεται ως τέτοια.

547
00:29:47,070 --> 00:29:52,870
>> Έτσι, ένας τρόπος για να γίνει that--
Ω, συγγνώμη, αυτό το ένα.

548
00:29:52,870 --> 00:29:59,450
Έτσι, σε αυτή την περίπτωση, "ζωολογικός κήπος" δεν είναι
μια λέξη, αλλά είναι στην προσπάθεια μας.

549
00:29:59,450 --> 00:30:05,690
Αλλά σε αυτό το ένα, ας πούμε θέλουμε
εισάγει τη λέξη "μπάνιο," τι συμβαίνει

550
00:30:05,690 --> 00:30:08,260
Είναι ακολουθούμε through-- β, Α, Τ.

551
00:30:08,260 --> 00:30:11,820
Είμαστε σε αυτή τη σειρά, και
πάμε για να αναζητήσετε h.

552
00:30:11,820 --> 00:30:15,220
>> Στην περίπτωση αυτή, όταν
εξετάσουμε το δείκτη σε ώρα,

553
00:30:15,220 --> 00:30:17,890
αυτό είναι που δείχνουν προς NULL, εντάξει;

554
00:30:17,890 --> 00:30:20,780
Έτσι, αν δεν είναι ρητά
επισημαίνοντας μια άλλη σειρά,

555
00:30:20,780 --> 00:30:25,000
θα υποθέσουμε ότι όλοι οι δείκτες
σε αυτήν την σειρά είναι στραμμένες σε null.

556
00:30:25,000 --> 00:30:28,270
Έτσι, στην περίπτωση αυτή, h είναι στραμμένη
σε null έτσι δεν μπορούμε να κάνουμε τίποτα,

557
00:30:28,270 --> 00:30:31,540
έτσι θα επιστρέψει επίσης
ψευδείς, "λουτρό" δεν είναι εδώ.

558
00:30:31,540 --> 00:30:34,102

559
00:30:34,102 --> 00:30:35,810
Έτσι τώρα είμαστε στην πραγματικότητα
πρόκειται να περάσουν από

560
00:30:35,810 --> 00:30:39,790
πώς θα μπορούμε πραγματικά να πω
ότι «ζωολογικός κήπος» είναι στην προσπάθεια μας.

561
00:30:39,790 --> 00:30:42,920
Πώς εισάγουμε "ζωολογικό κήπο" σε προσπάθεια μας;

562
00:30:42,920 --> 00:30:47,810
Έτσι, με τον ίδιο τρόπο που ξεκινήσαμε με
συνδεδεμένη λίστα μας, ξεκινάμε από τη ρίζα.

563
00:30:47,810 --> 00:30:50,600
Σε περίπτωση αμφιβολίας, ξεκινούν από
η ρίζα αυτών των πραγμάτων.

564
00:30:50,600 --> 00:30:53,330
>> Και εμείς θα πούμε, εντάξει, z.

565
00:30:53,330 --> 00:30:55,650
z υπάρχει σε αυτό, και να το κάνει.

566
00:30:55,650 --> 00:30:58,370
Έτσι είστε κινείται προς
επόμενη σειρά σας, εντάξει;

567
00:30:58,370 --> 00:31:01,482
Και στη συνέχεια στο επόμενο,
λέμε, εντάξει, δεν υπάρχει o;

568
00:31:01,482 --> 00:31:03,000
Κάνει.

569
00:31:03,000 --> 00:31:04,330
Αυτό πάλι.

570
00:31:04,330 --> 00:31:08,670
>> Και ούτω καθεξής επόμενο μας, έχουμε πει,
Εντάξει, "ζωολογικό κήπο" υπάρχει ήδη εδώ.

571
00:31:08,670 --> 00:31:12,440
Όλα πρέπει να κάνετε είναι να ορίσετε αυτή την ίση
στην αλήθεια, ότι υπάρχει μια λέξη.

572
00:31:12,440 --> 00:31:15,260
Αν είχε ακολουθήσει τα πάντα
μέχρι και πριν από εκείνο το σημείο,

573
00:31:15,260 --> 00:31:17,030
είναι μια λέξη, τόσο απλά
που είναι ίση με τέτοια.

574
00:31:17,030 --> 00:31:17,530
Ναι;

575
00:31:17,530 --> 00:31:22,550
>> ΚΟΙΝΟ: Μέχρι τότε κάνει ότι
σημαίνει ότι «BA» είναι μια λέξη που επίσης;

576
00:31:22,550 --> 00:31:24,120
>> ΟΜΙΛΗΤΗΣ 1: Όχι.

577
00:31:24,120 --> 00:31:28,870
Έτσι, σε αυτή την περίπτωση, "βα" θα πάρει
Εδώ, θα λέγαμε είναι μια λέξη,

578
00:31:28,870 --> 00:31:31,590
και θα εξακολουθεί να υπάρχει.

579
00:31:31,590 --> 00:31:32,822
Εντάξει;

580
00:31:32,822 --> 00:31:33,740
Mmhmm;

581
00:31:33,740 --> 00:31:36,360
>> ΚΟΙΝΟ: Μέχρι τη στιγμή που θα είναι ένα
λέξη και λέτε ναι, τότε

582
00:31:36,360 --> 00:31:38,380
θα περιέχει να πάει να μ?

583
00:31:38,380 --> 00:31:42,260
>> ΟΜΙΛΗΤΗΣ 1: Έτσι, αυτό έχει να κάνει
with-- είστε φόρτωση αυτό.

584
00:31:42,260 --> 00:31:43,640
Λέτε "ζωολογικός κήπος" είναι μια λέξη.

585
00:31:43,640 --> 00:31:47,020
Όταν πηγαίνετε να check--
όπως, ας πούμε ότι θέλετε να πείτε,

586
00:31:47,020 --> 00:31:49,400
δεν "ζωολογικός κήπος" υπάρχουν σε αυτό το λεξικό;

587
00:31:49,400 --> 00:31:54,200
Είστε μόνο πρόκειται να ψάξετε για "ζωολογικό κήπο"
και, στη συνέχεια, ελέγξτε για να δείτε αν είναι μια λέξη.

588
00:31:54,200 --> 00:31:57,291
Ποτέ δεν πρόκειται να κινηθεί
μέσα σε m, διότι αυτό δεν είναι

589
00:31:57,291 --> 00:31:58,290
αυτό που ψάχνετε.

590
00:31:58,290 --> 00:32:02,690

591
00:32:02,690 --> 00:32:08,070
>> Έτσι, αν πραγματικά θέλαμε να
προσθέστε το «λουτρό» σε αυτή την προσπάθεια,

592
00:32:08,070 --> 00:32:11,390
εμείς θα κάνουμε το ίδιο πράγμα
όπως κάναμε με την «ζωολογικό κήπο»,

593
00:32:11,390 --> 00:32:15,380
εκτός θα δούμε ότι, όταν εμείς
να προσπαθήσουμε και να πάρει ώρες, δεν υπάρχει.

594
00:32:15,380 --> 00:32:20,090
Έτσι, μπορείτε να σκεφτείτε αυτό ως προσπαθεί
για να προσθέσετε ένα νέο κόμβο σε μια συνδεδεμένη λίστα,

595
00:32:20,090 --> 00:32:27,210
γι 'αυτό θα πρέπει να προσθέσετε ένα άλλο
μία από αυτές τις συστοιχίες, όπως έτσι.

596
00:32:27,210 --> 00:32:35,670
Και τότε αυτό που κάνουμε είναι να οριστεί ακριβώς το h
στοιχείο αυτού του πίνακα δείχνουν προς αυτό.

597
00:32:35,670 --> 00:32:39,430
>> Και τότε τι θα θέλουμε να κάνουμε εδώ;

598
00:32:39,430 --> 00:32:43,110
Προσθέστε την ισότιμη αλήθεια
γιατί είναι μια λέξη.

599
00:32:43,110 --> 00:32:46,350

600
00:32:46,350 --> 00:32:48,150
Cool.

601
00:32:48,150 --> 00:32:48,700
Το ξέρω.

602
00:32:48,700 --> 00:32:51,170
Προσπαθεί να μην είναι η πιο συναρπαστική.

603
00:32:51,170 --> 00:32:54,250
Πίστεψέ με, το ξέρω.

604
00:32:54,250 --> 00:32:58,040
>> Έτσι, ένα πράγμα που πρέπει να συνειδητοποιήσουμε με προσπάθειες,
Είπα, ότι είναι πολύ αποδοτικό.

605
00:32:58,040 --> 00:33:00,080
Έτσι έχουμε τους δει
καταλαμβάνουν έναν τόνο του χώρου.

606
00:33:00,080 --> 00:33:01,370
Θα είστε το είδος της σύγχυσης.

607
00:33:01,370 --> 00:33:03,367
Επομένως, γιατί θα έχουμε ποτέ χρησιμοποιήσει αυτά;

608
00:33:03,367 --> 00:33:05,450
Χρησιμοποιούμε αυτά επειδή είναι
απίστευτα αποτελεσματική.

609
00:33:05,450 --> 00:33:08,130
>> Έτσι, εάν είστε ποτέ ψάχνουν
μέχρι μια λέξη, είστε μόνο

610
00:33:08,130 --> 00:33:10,450
που οριοθετείται από το μήκος της λέξης.

611
00:33:10,450 --> 00:33:15,210
Έτσι, αν ψάχνετε για ένα
λέξη που είναι μήκους πέντε,

612
00:33:15,210 --> 00:33:20,940
είστε μόνο πρόκειται ποτέ να πρέπει να
κάνει το πολύ πέντε συγκρίσεις, εντάξει;

613
00:33:20,940 --> 00:33:25,780
Έτσι καθιστά ουσιαστικά σταθερή.

614
00:33:25,780 --> 00:33:29,150
Όπως εισαγωγή και αναζήτηση
είναι βασικά σταθερό χρόνο.

615
00:33:29,150 --> 00:33:33,750
>> Έτσι, αν ποτέ να πάρετε
κάτι σε συνεχή χρόνο,

616
00:33:33,750 --> 00:33:35,150
αυτό είναι τόσο καλό όσο παίρνει.

617
00:33:35,150 --> 00:33:37,990
Δεν μπορείτε να πάρετε καλύτερα από ό, τι
σταθερό χρόνο για αυτά τα πράγματα.

618
00:33:37,990 --> 00:33:43,150
Έτσι, αυτό είναι ένα από τα
τεράστιο συν του προσπαθεί.

619
00:33:43,150 --> 00:33:46,780
>> Αλλά αυτό είναι ένα πολύ χώρο.

620
00:33:46,780 --> 00:33:50,380
Έτσι, κατά κάποιο τρόπο πρέπει να αποφασίσει
τι είναι πιο σημαντικό για εσάς.

621
00:33:50,380 --> 00:33:54,700
Και για τους σημερινούς υπολογιστές, η
χώρο ότι μια δοκιμή μπορεί να διαρκέσει έως

622
00:33:54,700 --> 00:33:57,740
ίσως δεν επηρεάζει
σας τόσο πολύ, αλλά ίσως

623
00:33:57,740 --> 00:34:01,350
έχουμε να κάνουμε με κάτι
ότι έχει πολύ, πολύ περισσότερα πράγματα,

624
00:34:01,350 --> 00:34:02,810
και μια δοκιμή απλά δεν είναι λογικό.

625
00:34:02,810 --> 00:34:03,000
Ναι;

626
00:34:03,000 --> 00:34:05,610
>> ΚΟΙΝΟ: Περιμένετε, έτσι έχετε 26
επιστολές σε κάθε μία;

627
00:34:05,610 --> 00:34:07,440
>> ΟΜΙΛΗΤΗΣ 1: Mmhmm.

628
00:34:07,440 --> 00:34:08,570
Ναι, έχετε 26.

629
00:34:08,570 --> 00:34:16,984
Έχετε κάποια είναι δείκτης λέξη και, στη συνέχεια,
έχετε 26 δείκτες σε κάθε μία.

630
00:34:16,984 --> 00:34:17,775
Και όπου και αν point--

631
00:34:17,775 --> 00:34:20,280
>> ΚΟΙΝΟ: Και κάθε 26,
δεν το καθένα έχει 26;

632
00:34:20,280 --> 00:34:21,500
>> ΟΜΙΛΗΤΗΣ 1: Ναι.

633
00:34:21,500 --> 00:34:27,460
Και γι 'αυτό, όπως μπορείτε
δείτε, διαστέλλεται αρκετά γρήγορα.

634
00:34:27,460 --> 00:34:28,130
Εντάξει.

635
00:34:28,130 --> 00:34:32,524
Έτσι θα πάμε να μπει σε δέντρα, τα οποία
Νιώθω σαν να είναι ευκολότερος και μάλλον θα

636
00:34:32,524 --> 00:34:36,150
είναι μια ωραία μικρή ανάπαυλα
από προσπαθεί εκεί.

637
00:34:36,150 --> 00:34:39,620
Έτσι, ελπίζουμε ότι οι περισσότεροι από εσάς
έχουν δει ένα δέντρο πριν.

638
00:34:39,620 --> 00:34:41,820
Δεν αρέσει το όμορφο
αυτοί έξω, που εγώ

639
00:34:41,820 --> 00:34:44,340
Δεν ξέρω αν κάποιος
πήγε σε εξωτερικούς χώρους πρόσφατα.

640
00:34:44,340 --> 00:34:49,230
Πήγα μήλο να πάρει αυτό το Σαββατοκύριακο,
και Θεέ μου, ήταν όμορφη.

641
00:34:49,230 --> 00:34:52,250
Δεν ήξερα φύλλα
θα μπορούσε να εξετάσει αυτό αρκετά.

642
00:34:52,250 --> 00:34:53,610
>> Έτσι, αυτό είναι μόνο ένα δέντρο, σωστά;

643
00:34:53,610 --> 00:34:56,790
Είναι μερικά μόνο κόμβο, και
επισημαίνει σε μια δέσμη των άλλων κόμβων.

644
00:34:56,790 --> 00:34:59,570
Όπως μπορείτε να δείτε εδώ, αυτό είναι
το είδος της ένα επαναλαμβανόμενο θέμα.

645
00:34:59,570 --> 00:35:03,720
Κόμβοι κατάδειξης σε κόμβους είναι το είδος του
η ουσία πολλών δομών δεδομένων.

646
00:35:03,720 --> 00:35:06,670
Δεν εξαρτάται μόνο από το πώς εμείς
πρέπει να επισημάνω σε κάθε άλλη

647
00:35:06,670 --> 00:35:08,600
και πώς θα διασχίσει
μέσα από αυτά και πώς μπορούμε

648
00:35:08,600 --> 00:35:14,500
εισάγετε Πράγματα που καθορίζει
διαφορετικά χαρακτηριστικά τους.

649
00:35:14,500 --> 00:35:17,600
>> Έτσι, μερικά μόνο ορολογία,
το οποίο έχω χρησιμοποιήσει πριν.

650
00:35:17,600 --> 00:35:20,010
Έτσι ρίζα είναι ό, τι είναι στην κορυφή.

651
00:35:20,010 --> 00:35:21,200
αυτό είναι όπου μπορούμε πάντα να ξεκινήσετε.

652
00:35:21,200 --> 00:35:23,610
Μπορείτε να σκεφτείτε από το ως το κεφάλι επίσης.

653
00:35:23,610 --> 00:35:28,750
Αλλά για τα δέντρα, έχουμε την τάση να
αναφέρονται σε αυτήν ως τη ρίζα.

654
00:35:28,750 --> 00:35:32,820
>> Οτιδήποτε στο κάτω μέρος here--
στο πολύ, πολύ bottom--

655
00:35:32,820 --> 00:35:34,500
Δεν θεωρούνται φύλλα.

656
00:35:34,500 --> 00:35:37,210
Έτσι, πηγαίνει μαζί με το
όλο θέμα δέντρο, σωστά;

657
00:35:37,210 --> 00:35:39,860
Τα φύλλα είναι στα άκρα του δέντρου σας.

658
00:35:39,860 --> 00:35:45,820
>> Και στη συνέχεια, έχουμε επίσης ένα ζευγάρι των
όρους για να μιλήσουμε για τους κόμβους σε σχέση

659
00:35:45,820 --> 00:35:46,680
ο ένας στον άλλο.

660
00:35:46,680 --> 00:35:49,700
Έτσι έχουμε γονέα,
τα παιδιά, και τα αδέλφια.

661
00:35:49,700 --> 00:35:56,260
Έτσι, στην περίπτωση αυτή, 3 είναι η
γονέας 5, 6, και 7.

662
00:35:56,260 --> 00:36:00,370
Έτσι, ο γονέας είναι ό, τι είναι
ένα βήμα πάνω από ό, τι είστε

663
00:36:00,370 --> 00:36:02,940
αναφέρεστε, έτσι απλά
σαν ένα οικογενειακό δέντρο.

664
00:36:02,940 --> 00:36:07,090
Ας ελπίσουμε ότι όλα αυτά είναι λίγο
λίγο πιο έξυπνο από ό, τι τις προσπάθειες.

665
00:36:07,090 --> 00:36:10,970
>> Τα αδέλφια είναι κάποια που έχουν
την ίδια μητρική, σωστά;

666
00:36:10,970 --> 00:36:13,470
Είναι στο ίδιο επίπεδο εδώ.

667
00:36:13,470 --> 00:36:16,960
Και τότε, όπως ήμουν
λένε, τα παιδιά είναι απλώς

668
00:36:16,960 --> 00:36:22,630
ό, τι είναι ένα βήμα παρακάτω
το συγκεκριμένο κόμβο, εντάξει;

669
00:36:22,630 --> 00:36:23,470
Cool.

670
00:36:23,470 --> 00:36:25,610
Έτσι, ένα δυαδικό δένδρο.

671
00:36:25,610 --> 00:36:31,450
Μπορεί κανείς να τολμούσα να πω σε έναν από τους
τα χαρακτηριστικά του δυαδικού δένδρου;

672
00:36:31,450 --> 00:36:32,770
>> ΚΟΙΝΟ: Max δύο φύλλα.

673
00:36:32,770 --> 00:36:33,478
>> ΟΜΙΛΗΤΗΣ 1: Δεξιά.

674
00:36:33,478 --> 00:36:34,640
Έτσι, το μέγιστο όριο των δύο φύλλων.

675
00:36:34,640 --> 00:36:39,730
Έτσι, σε αυτό το ένα πριν, είχαμε αυτό το ένα
ότι είχε τρεις, αλλά σε ένα δυαδικό δέντρο,

676
00:36:39,730 --> 00:36:45,000
έχετε ένα μέγιστο των δύο
παιδιά ανά γονέα, σωστά;

677
00:36:45,000 --> 00:36:46,970
Υπάρχει ένα άλλο
ενδιαφέρον χαρακτηριστικό.

678
00:36:46,970 --> 00:36:51,550
Ξέρει κανείς αυτό;

679
00:36:51,550 --> 00:36:52,620
Δυαδικό δέντρο.

680
00:36:52,620 --> 00:37:00,350
>> Έτσι, ένα δυαδικό δέντρο θα έχει τα πάντα
για the-- αυτό δεν είναι sorted--

681
00:37:00,350 --> 00:37:05,320
αλλά σε ένα ταξινομημένο δυαδικό δέντρο,
τα πάντα σχετικά με το δικαίωμα

682
00:37:05,320 --> 00:37:08,530
είναι μεγαλύτερη από την μητρική,
και τα πάντα για την αριστερά

683
00:37:08,530 --> 00:37:10,035
είναι μικρότερο από το γονέα.

684
00:37:10,035 --> 00:37:15,690
Και αυτό ήταν ένα κουίζ
ερώτηση πριν, οπότε καλό να γνωρίζουμε.

685
00:37:15,690 --> 00:37:19,500
Έτσι, ο τρόπος που ορίζουμε αυτό,
και πάλι, έχουμε ένα άλλο κόμβο.

686
00:37:19,500 --> 00:37:21,880
Αυτό μοιάζει πολύ με αυτό;

687
00:37:21,880 --> 00:37:28,336

688
00:37:28,336 --> 00:37:28,836
Διπλάσια

689
00:37:28,836 --> 00:37:29,320
>> ΚΟΙΝΟ: Συνδεδεμένες λίστες

690
00:37:29,320 --> 00:37:31,100
>> ΟΜΙΛΗΤΗΣ 1: Ένα διπλό συνδεδεμένη λίστα, σωστά;

691
00:37:31,100 --> 00:37:33,690
Έτσι, αν αντικαταστήσουμε αυτό
με την προηγούμενη και την επόμενη,

692
00:37:33,690 --> 00:37:35,670
Αυτό θα ήταν μια διπλά συνδεδεμένη λίστα.

693
00:37:35,670 --> 00:37:40,125
Αλλά σε αυτή την περίπτωση, εμείς στην πραγματικότητα
έχουν αριστερά και δεξιά και αυτό είναι όλο.

694
00:37:40,125 --> 00:37:41,500
Διαφορετικά, είναι ακριβώς το ίδιο.

695
00:37:41,500 --> 00:37:43,374
Έχουμε ακόμα το στοιχείο
ψάχνετε για,

696
00:37:43,374 --> 00:37:45,988
και έχετε μόνο δύο δείκτες
πρόκειται για ό, τι γίνεται στη συνέχεια.

697
00:37:45,988 --> 00:37:49,210

698
00:37:49,210 --> 00:37:51,870
Ναι, έτσι δυαδικό δέντρο αναζήτησης.

699
00:37:51,870 --> 00:37:57,665
Αν παρατηρήσετε, τα πάντα σχετικά με το
εδώ είναι μεγαλύτερη than--

700
00:37:57,665 --> 00:37:59,850
ή ό, τι αμέσως
προς τα δεξιά εδώ

701
00:37:59,850 --> 00:38:02,840
είναι μεγαλύτερο από ό, τι
εδώ είναι μικρότερη.

702
00:38:02,840 --> 00:38:06,980

703
00:38:06,980 --> 00:38:14,000
>> Έτσι, αν ήμασταν για να αναζητήσετε μέσα από αυτό,
πρέπει να εξετάσουμε πολύ κοντά σε δυαδική αναζήτηση

704
00:38:14,000 --> 00:38:14,910
εδώ, σωστά;

705
00:38:14,910 --> 00:38:17,640
Εκτός αντί να ψάχνει
στο μισό της συστοιχίας,

706
00:38:17,640 --> 00:38:21,720
είμαστε απλά κοιτάζοντας είτε αριστερά
πλευρά ή η δεξιά πλευρά του δένδρου.

707
00:38:21,720 --> 00:38:24,850
Γι 'αυτό παίρνει λίγο πιο απλό, νομίζω.

708
00:38:24,850 --> 00:38:29,300
>> Έτσι, αν ρίζα σας είναι NULL,
προφανώς είναι απλά ψευδής.

709
00:38:29,300 --> 00:38:33,470
Και αν είναι εκεί, προφανώς αυτό είναι αλήθεια.

710
00:38:33,470 --> 00:38:35,320
Αν είναι λιγότερο από ό, τι, ψάχνουμε το αριστερό.

711
00:38:35,320 --> 00:38:37,070
Αν είναι μεγαλύτερη από ό, τι,
ψάχνουμε το δικαίωμα.

712
00:38:37,070 --> 00:38:39,890
Είναι ακριβώς σαν δυαδική αναζήτηση,
απλά μια διαφορετική δομή δεδομένων

713
00:38:39,890 --> 00:38:40,600
ότι είμαστε χρησιμοποιούν.

714
00:38:40,600 --> 00:38:42,790
Αντί μίας συστοιχίας,
είναι ακριβώς ένα δυαδικό δέντρο.

715
00:38:42,790 --> 00:38:45,820

716
00:38:45,820 --> 00:38:48,090
>> ΟΚ, στοίβες.

717
00:38:48,090 --> 00:38:51,550
Και, επίσης, φαίνεται σαν να
θα μπορούσαν να έχουν λίγο χρόνο.

718
00:38:51,550 --> 00:38:54,460
Αν το κάνουμε, είμαι στην ευχάριστη θέση να πάει
πάνω από οποιοδήποτε από αυτό και πάλι.

719
00:38:54,460 --> 00:38:56,856
Εντάξει, έτσι στοίβες.

720
00:38:56,856 --> 00:39:02,695
Υπάρχει κάποιος που θυμάται τι stacks--
οποιαδήποτε χαρακτηριστικά μιας στοίβας;

721
00:39:02,695 --> 00:39:05,550

722
00:39:05,550 --> 00:39:10,400
>> Εντάξει, έτσι οι περισσότεροι από εμάς, νομίζω,
τρώνε στην τραπεζαρία halls--

723
00:39:10,400 --> 00:39:13,100
όσο εμείς μπορεί να μην αρέσει σε.

724
00:39:13,100 --> 00:39:16,900
Αλλά, προφανώς, μπορείτε να σκεφτείτε μια στοίβα
κυριολεκτικά ακριβώς όπως μια στοίβα δίσκων

725
00:39:16,900 --> 00:39:18,460
ή ένα σωρό από πράγματα.

726
00:39:18,460 --> 00:39:21,820
Και τι είναι σημαντικό
να συνειδητοποιήσουμε είναι ότι είναι

727
00:39:21,820 --> 00:39:26,850
something-- το χαρακτηριστικό
ότι καλούμε by-- είναι LIFO.

728
00:39:26,850 --> 00:39:28,450
Ξέρει κανείς τι σημαίνει;

729
00:39:28,450 --> 00:39:29,070
Mmhmm;

730
00:39:29,070 --> 00:39:30,650
>> ΚΟΙΝΟ: Τελευταία in, first out.

731
00:39:30,650 --> 00:39:32,250
>> ΟΜΙΛΗΤΗΣ 1: Δεξιά, διαρκούν in, first out.

732
00:39:32,250 --> 00:39:36,585
Έτσι, αν γνωρίζουμε, αν είμαστε στοίβαγμα πράγματα
up, το πιο εύκολο πράγμα να αρπάξει off--

733
00:39:36,585 --> 00:39:39,570
και ίσως το μόνο πράγμα που μπορούμε να αρπάξει
εκτός αν στοίβα μας είναι μεγάλη enough--

734
00:39:39,570 --> 00:39:40,850
είναι ότι η κορυφαία στοιχείο.

735
00:39:40,850 --> 00:39:43,460
Έτσι, ό, τέθηκε σε
last-- όπως βλέπουμε εδώ,

736
00:39:43,460 --> 00:39:46,370
ό, τι ωθήθηκε
στις περισσότερες recently-- είναι

737
00:39:46,370 --> 00:39:51,160
πρόκειται να είναι η πρώτη
πράγμα που θα σκάσει μακριά, εντάξει;

738
00:39:51,160 --> 00:39:56,324
>> Έτσι, αυτό που έχουμε εδώ είναι
άλλο struct typedef.

739
00:39:56,324 --> 00:39:58,740
Αυτό είναι πραγματικά ακριβώς όπως ένα
Crash Course στη δομή δεδομένων,

740
00:39:58,740 --> 00:40:01,650
οπότε δεν υπάρχουν πολλά που ρίχνονται σε σας παιδιά.

741
00:40:01,650 --> 00:40:02,540
Το ξέρω.

742
00:40:02,540 --> 00:40:04,970
Έτσι, ένα ακόμη struct.

743
00:40:04,970 --> 00:40:06,740
Yay για δομές.

744
00:40:06,740 --> 00:40:16,660
>> Και σε αυτή την περίπτωση, είναι μερικά δείκτη
σε μία συστοιχία που έχει κάποια ικανότητα.

745
00:40:16,660 --> 00:40:20,830
Έτσι, αυτό αντιπροσωπεύει το stack μας
Εδώ, όπως και την πραγματική σειρά μας

746
00:40:20,830 --> 00:40:22,520
ότι κρατά τα στοιχεία μας.

747
00:40:22,520 --> 00:40:24,850
Και τότε εδώ έχουμε κάποιο μέγεθος.

748
00:40:24,850 --> 00:40:31,170
>> Και συνήθως, θέλετε να κρατήσετε
κομμάτι του πόσο μεγάλο stack σας είναι

749
00:40:31,170 --> 00:40:36,180
γιατί ό, τι πρόκειται να επιτρέψει
μπορείτε να κάνετε είναι εάν ξέρετε το μέγεθος,

750
00:40:36,180 --> 00:40:39,170
σας επιτρέπει να πω,
Εντάξει, είμαι σε ικανότητα;

751
00:40:39,170 --> 00:40:40,570
Μπορώ να προσθέσω τίποτα περισσότερο;

752
00:40:40,570 --> 00:40:44,650
Και αυτό σας λέει επίσης
όπου η κορυφή της στοίβας σας

753
00:40:44,650 --> 00:40:48,180
είναι έτσι ώστε να ξέρετε τι σας
μπορεί πραγματικά να απογειωθεί.

754
00:40:48,180 --> 00:40:51,760
Και αυτό είναι πραγματικά πρόκειται να
να είναι λίγο πιο σαφής εδώ.

755
00:40:51,760 --> 00:40:57,350
>> Έτσι, για την ώθηση, ένα πράγμα, αν
ήταν ποτέ να εφαρμόσει ώθηση,

756
00:40:57,350 --> 00:41:01,330
όπως ήμουν ακριβώς λέει, σας
στοίβα έχει περιορισμένο μέγεθος, σωστά;

757
00:41:01,330 --> 00:41:03,990
Σειρά μας είχε κάποια ικανότητα.

758
00:41:03,990 --> 00:41:04,910
Είναι μια σειρά.

759
00:41:04,910 --> 00:41:08,930
Είναι ένα σταθερό μέγεθος, γι 'αυτό πρέπει να
βεβαιωθείτε ότι δεν είμαστε βάζοντας περισσότερα

760
00:41:08,930 --> 00:41:11,950
σε σειρά μας από ό, τι εμείς
στην πραγματικότητα έχουν χώρο για.

761
00:41:11,950 --> 00:41:16,900
>> Έτσι, όταν είστε δημιουργώντας μια ώθηση
λειτουργία, το πρώτο πράγμα που κάνετε είναι να πούμε, εντάξει,

762
00:41:16,900 --> 00:41:18,570
έχω χώρο στη στοίβα μου;

763
00:41:18,570 --> 00:41:23,330
Διότι, αν δεν το κάνω, συγγνώμη,
Δεν μπορώ να αποθηκεύσετε το στοιχείο σας.

764
00:41:23,330 --> 00:41:28,980
Αν το κάνω, τότε θέλετε να αποθηκεύσετε
αυτό στην κορυφή της στοίβας, έτσι;

765
00:41:28,980 --> 00:41:31,325
>> Και αυτός είναι ο λόγος που έχουμε
να παρακολουθείτε το μέγεθος μας.

766
00:41:31,325 --> 00:41:35,290
Αν δεν παρακολουθείτε το μέγεθος μας,
δεν ξέρουμε πού να το θέσω.

767
00:41:35,290 --> 00:41:39,035
Δεν ξέρουμε πόσα πράγματα
βρίσκονται σε συστοιχία μας ήδη.

768
00:41:39,035 --> 00:41:41,410
Όπως προφανώς υπάρχουν τρόποι
ότι ίσως θα μπορούσα να το κάνω.

769
00:41:41,410 --> 00:41:44,610
Θα μπορούσε να προετοιμάσει τα πάντα για να NULL
και, στη συνέχεια, ελέγξτε για την τελευταία NULL,

770
00:41:44,610 --> 00:41:47,950
αλλά ένα πολύ πιο εύκολο πράγμα είναι απλά
να πω, εντάξει, να παρακολουθείτε το μέγεθος.

771
00:41:47,950 --> 00:41:51,840
Όπως ξέρω ότι έχω τέσσερα στοιχεία
σε σειρά μου, έτσι το επόμενο πράγμα

772
00:41:51,840 --> 00:41:55,930
ότι βάζουμε σε, είμαστε
πρόκειται να αποθηκεύσετε στο ευρετήριο 4.

773
00:41:55,930 --> 00:42:00,940
Και τότε, φυσικά, αυτό σημαίνει ότι
έχετε πίεσε επιτυχώς κάτι

774
00:42:00,940 --> 00:42:03,320
σε στοίβα σας,
θέλουν να αυξήσουν το μέγεθος

775
00:42:03,320 --> 00:42:08,880
έτσι ώστε να γνωρίζουν πού είστε, ώστε
ότι μπορείτε να ωθήσει περισσότερα πράγματα σχετικά.

776
00:42:08,880 --> 00:42:12,730
>> Έτσι, αν προσπαθούμε να σκάσει
κάτι από τη στοίβα,

777
00:42:12,730 --> 00:42:16,072
τι θα μπορούσε να είναι το πρώτο πράγμα
ότι θέλουμε να ελέγξουμε για;

778
00:42:16,072 --> 00:42:18,030
Προσπαθείς να λάβει
κάτι από το stack σας.

779
00:42:18,030 --> 00:42:21,710

780
00:42:21,710 --> 00:42:24,781
Είσαι σίγουρος ότι υπάρχει
κάτι το stack σας;

781
00:42:24,781 --> 00:42:25,280
Όχι.

782
00:42:25,280 --> 00:42:26,894
Λοιπόν, τι θα μπορούσαμε να θέλετε να ελέγξετε;

783
00:42:26,894 --> 00:42:27,810
>> ΚΟΙΝΟ: [δεν ακούγεται].

784
00:42:27,810 --> 00:42:29,880
ΟΜΙΛΗΤΗΣ 1: Αναχώρηση για το μέγεθος;

785
00:42:29,880 --> 00:42:31,840
Μέγεθος.

786
00:42:31,840 --> 00:42:38,520
Θέλουμε, λοιπόν, να ελέγξετε για να δείτε αν
μέγεθος μας είναι μεγαλύτερη από 0, εντάξει;

787
00:42:38,520 --> 00:42:44,970
Και αν είναι, τότε θέλουμε να μειώσετε
μέγεθος μας από το 0 και να επιστρέψετε αυτό.

788
00:42:44,970 --> 00:42:45,840
Γιατί;

789
00:42:45,840 --> 00:42:49,950
>> Στο πρώτο ήμασταν
πιέζει, εμείς έσπρωξε

790
00:42:49,950 --> 00:42:52,460
στο μέγεθος και στη συνέχεια ενημερώνεται το μέγεθος.

791
00:42:52,460 --> 00:42:57,850
Σε αυτή την περίπτωση, είμαστε Decrementing μέγεθος
και στη συνέχεια, λαμβάνοντας μακριά, εκρίζωση

792
00:42:57,850 --> 00:42:58,952
από σειρά μας.

793
00:42:58,952 --> 00:42:59,826
Γιατί θα μπορούσαμε να το κάνουμε αυτό;

794
00:42:59,826 --> 00:43:04,800

795
00:43:04,800 --> 00:43:11,811
Έτσι, αν έχω ένα πράγμα για το stack μου,
τι θα είναι το μέγεθος μου σε εκείνο το σημείο;

796
00:43:11,811 --> 00:43:13,140
1.

797
00:43:13,140 --> 00:43:15,180
>> Και πού είναι το στοιχείο 1 αποθηκεύεται;

798
00:43:15,180 --> 00:43:17,621
Σε ό, τι δείκτη;

799
00:43:17,621 --> 00:43:18,120
ΚΟΙΝΟ: 0.

800
00:43:18,120 --> 00:43:19,060
ΟΜΙΛΗΤΗΣ 1: 0.

801
00:43:19,060 --> 00:43:22,800
Έτσι, σε αυτή την περίπτωση, έχουμε
πρέπει πάντα να κάνουν sure--

802
00:43:22,800 --> 00:43:27,630
αντί να επιστρέψει
μέγεθος μείον 1, γιατί εμείς

803
00:43:27,630 --> 00:43:31,730
γνωρίζουν ότι το στοιχείο μας είναι
πρόκειται να αποθηκεύονται στους μείον 1

804
00:43:31,730 --> 00:43:34,705
ανεξάρτητα από το μέγεθός μας είναι, αυτό
απλά φροντίζει για αυτό.

805
00:43:34,705 --> 00:43:36,080
Είναι μια ελαφρώς πιο κομψό τρόπο.

806
00:43:36,080 --> 00:43:41,220
Και εμείς απλά θα ελαττωθεί μας
μέγεθος και, στη συνέχεια, το μέγεθος επιστρέψουν.

807
00:43:41,220 --> 00:43:42,330
Mmhmm;

808
00:43:42,330 --> 00:43:45,300
>> ΚΟΙΝΟ: Υποθέτω ότι μόνο σε γενικές γραμμές,
γιατί θα ήταν αυτή η δομή δεδομένων

809
00:43:45,300 --> 00:43:47,800
είναι επωφελής;

810
00:43:47,800 --> 00:43:50,660
>> ΟΜΙΛΗΤΗΣ 1: Εξαρτάται από το πλαίσιο σας.

811
00:43:50,660 --> 00:43:57,420
Έτσι, για ορισμένα από τη θεωρία,
αν εργάζεστε with-- ΟΚ,

812
00:43:57,420 --> 00:44:02,750
επιτρέψτε μου να δούμε αν υπάρχει μια ευεργετική
ότι είναι ευεργετικό για περισσότερο από έξω

813
00:44:02,750 --> 00:44:05,420
της CS.

814
00:44:05,420 --> 00:44:15,780
Με στοίβες, κάθε φορά που θα χρειαστεί
να παρακολουθείτε κάτι που

815
00:44:15,780 --> 00:44:20,456
είναι η πιο πρόσφατη που προστίθεται είναι όταν
θα πάμε να θέλετε να χρησιμοποιήσετε μια στοίβα.

816
00:44:20,456 --> 00:44:24,770
>> Και δεν μπορώ να σκεφτώ ένα καλό
παράδειγμα του ότι αυτή τη στιγμή.

817
00:44:24,770 --> 00:44:29,955
Αλλά κάθε φορά που το πιο πρόσφατο
πράγμα που είναι πιο σημαντικό για εσάς,

818
00:44:29,955 --> 00:44:31,705
ότι όταν μια στοίβα
πρόκειται να είναι χρήσιμη.

819
00:44:31,705 --> 00:44:35,797

820
00:44:35,797 --> 00:44:39,330
Προσπαθώ να σκεφτώ αν
υπάρχει μια καλή χρονιά για αυτό.

821
00:44:39,330 --> 00:44:43,720
Αν νομίζω ότι ένα καλό παράδειγμα στην επόμενη
20 λεπτά, εγώ θα σας πω σίγουρα.

822
00:44:43,720 --> 00:44:49,455
>> Αλλά συνολικά, αν υπάρχει κάτι,
όπως είπα οι περισσότεροι, όπου οι πιο πρόσφατες

823
00:44:49,455 --> 00:44:52,470
είναι το πιο σημαντικό, ότι είναι
όπου μια στοίβα μπαίνει στο παιχνίδι.

824
00:44:52,470 --> 00:44:58,860
Ότι οι ουρές είναι είδος για το αντίθετο.

825
00:44:58,860 --> 00:44:59,870
Και όλα τα μικρά σκυλιά.

826
00:44:59,870 --> 00:45:00,890
Δεν είναι αυτό το μεγάλο, σωστά;

827
00:45:00,890 --> 00:45:03,299
Νιώθω σαν να πρέπει να
απλά έχουν ένα βίντεο λαγουδάκι

828
00:45:03,299 --> 00:45:05,090
ακριβώς στη μέση του
ενότητα για σας παιδιά

829
00:45:05,090 --> 00:45:08,870
επειδή αυτό είναι ένα έντονο τομή.

830
00:45:08,870 --> 00:45:10,480
>> Έτσι, μια ουρά.

831
00:45:10,480 --> 00:45:12,710
Βασικά μια ουρά είναι σαν μια γραμμή.

832
00:45:12,710 --> 00:45:15,780
Εσείς Είμαι βέβαιος ότι αυτή η καθημερινή χρήση,
ακριβώς όπως σε αίθουσες τραπεζαρία μας.

833
00:45:15,780 --> 00:45:18,160
Έτσι πρέπει να πάμε σε
και να πάρει τους δίσκους μας, είμαι

834
00:45:18,160 --> 00:45:21,260
βεβαιωθείτε ότι έχετε να περιμένουν στην ουρά
να σύρετε ή να πάρετε το φαγητό σας.

835
00:45:21,260 --> 00:45:24,650
>> Έτσι, η διαφορά εδώ
είναι ότι αυτό είναι FIFO.

836
00:45:24,650 --> 00:45:30,090
Έτσι, αν LIFO ήταν τελευταία στην πρώτη
έξω, FIFO είναι first in, first out.

837
00:45:30,090 --> 00:45:33,400
Έτσι, αυτό είναι όπου ό, τι βάζετε
την πρώτη είναι το πιο σημαντικό σας.

838
00:45:33,400 --> 00:45:35,540
Έτσι, αν ήταν σε αναμονή
σε line-- μπορεί να σας

839
00:45:35,540 --> 00:45:39,130
φανταστείτε αν πήγε να
πάει να πάρει το νέο iPhone

840
00:45:39,130 --> 00:45:42,800
και ήταν μια στοίβα όπου ο
τελευταίο άτομο στη γραμμή πήρε την πρώτη,

841
00:45:42,800 --> 00:45:44,160
οι άνθρωποι θα σκοτώσουν ο ένας τον άλλον.

842
00:45:44,160 --> 00:45:49,800
>> Έτσι FIFO, είμαστε όλοι πολύ εξοικειωμένοι
με το πραγματικό κόσμο εδώ,

843
00:45:49,800 --> 00:45:54,930
και αυτό έχει να κάνει με πραγματικά
το είδος της αναδημιουργώντας όλη αυτή την γραμμή

844
00:45:54,930 --> 00:45:56,900
και οι ουρές δομή.

845
00:45:56,900 --> 00:46:02,390
Έτσι, ενώ με τη στοίβα,
έχουμε ώθηση και ποπ.

846
00:46:02,390 --> 00:46:06,440
Με μια ουρά, έχουμε
Τοποθέτηση στην ουρά και dequeue.

847
00:46:06,440 --> 00:46:10,910
Έτσι Τοποθέτηση στην ουρά σημαίνει βασικά
το βάζουμε πάνω στο πίσω μέρος,

848
00:46:10,910 --> 00:46:13,680
και dequeue μέσα λάβουν
μακριά από το μέτωπο.

849
00:46:13,680 --> 00:46:18,680
Έτσι δομή δεδομένων μας είναι ένα
λίγο πιο περίπλοκη.

850
00:46:18,680 --> 00:46:21,060
Έχουμε ένα δεύτερο πράγμα που πρέπει να παρακολουθείτε.

851
00:46:21,060 --> 00:46:25,950
>> Έτσι, χωρίς το κεφάλι, αυτό
είναι ακριβώς μια στοίβα, σωστά;

852
00:46:25,950 --> 00:46:27,900
Αυτή είναι η ίδια δομή ως μια στοίβα.

853
00:46:27,900 --> 00:46:32,480
Το μόνο πράγμα διαφορετικό τώρα είναι εμείς
έχουν αυτό το κεφάλι, το οποίο ό, τι νομίζετε

854
00:46:32,480 --> 00:46:34,272
πρόκειται να παρακολουθείτε;

855
00:46:34,272 --> 00:46:35,510
>> ΚΟΙΝΟ: Η πρώτη.

856
00:46:35,510 --> 00:46:38,685
>> ΟΜΙΛΗΤΗΣ 1: Δεξιά, η
το πρώτο πράγμα που βάλαμε στο.

857
00:46:38,685 --> 00:46:41,130
Ο επικεφαλής της ουράς μας.

858
00:46:41,130 --> 00:46:42,240
Όποιος είναι πρώτος στη γραμμή.

859
00:46:42,240 --> 00:46:45,300

860
00:46:45,300 --> 00:46:49,420
Εντάξει, οπότε αν κάνουμε Τοποθέτηση στην ουρά.

861
00:46:49,420 --> 00:46:52,720

862
00:46:52,720 --> 00:46:55,920
Πάλι, με οποιοδήποτε από
Αυτές οι δομές δεδομένων,

863
00:46:55,920 --> 00:46:59,760
δεδομένου ότι έχουμε να κάνουμε με μια σειρά,
θα πρέπει να ελέγξετε αν έχουμε χώρο.

864
00:46:59,760 --> 00:47:03,290
>> Αυτό είναι το είδος του σαν να μου λέει
σας παιδιά, αν ανοίξετε ένα αρχείο,

865
00:47:03,290 --> 00:47:04,760
θα πρέπει να ελέγξετε για μηδενική.

866
00:47:04,760 --> 00:47:08,330
Με οποιαδήποτε από αυτές τις στοίβες
και ουρές, θα πρέπει να έχετε

867
00:47:08,330 --> 00:47:13,420
για να δούμε αν υπάρχει χώρος, γιατί είμαστε
που ασχολούνται με τα σταθερά συστήματα μεγέθους,

868
00:47:13,420 --> 00:47:16,030
όπως βλέπουμε here-- 0, 1, όλα έως 5.

869
00:47:16,030 --> 00:47:20,690
Λοιπόν, τι κάνουμε σε αυτή την περίπτωση είναι επιταγή
για να δούμε αν έχουμε ακόμα χώρο.

870
00:47:20,690 --> 00:47:23,110
Είναι το μέγεθος μας λιγότερο από την ικανότητα;

871
00:47:23,110 --> 00:47:28,480
>> Αν ναι, θα πρέπει να το αποθηκεύσετε σε
η ουρά και ανανεώνουμε το μέγεθος μας.

872
00:47:28,480 --> 00:47:30,250
Λοιπόν, τι θα μπορούσε να είναι η ουρά σε αυτή την περίπτωση;

873
00:47:30,250 --> 00:47:32,360
Δεν είναι γραμμένο ρητά.

874
00:47:32,360 --> 00:47:33,380
Πώς θα μπορούμε να το αποθηκεύσετε;

875
00:47:33,380 --> 00:47:34,928
Ποια θα ήταν η ουρά είναι;

876
00:47:34,928 --> 00:47:38,600

877
00:47:38,600 --> 00:47:40,190
>> Ας περπατήσει μέσα από αυτό το παράδειγμα.

878
00:47:40,190 --> 00:47:44,590
Έτσι, αυτό είναι μια σειρά από μέγεθος 6, σωστά;

879
00:47:44,590 --> 00:47:49,220
Και έχουμε τώρα, το μέγεθος μας είναι 5.

880
00:47:49,220 --> 00:47:55,240
Και όταν βάζουμε μέσα, αυτό συμβαίνει
να πάει στο πέμπτο δείκτη, σωστά;

881
00:47:55,240 --> 00:47:57,030
Έτσι αποθηκεύετε σε ουρά.

882
00:47:57,030 --> 00:48:05,600
>> Ένας άλλος τρόπος για να γράψει ουρά θα ήταν απλά
είναι σειρά μας στο δείκτη του μεγέθους, σωστά;

883
00:48:05,600 --> 00:48:07,560
Αυτό είναι το μέγεθος 5.

884
00:48:07,560 --> 00:48:11,490
Το επόμενο πράγμα που πρόκειται να πάει σε 5.

885
00:48:11,490 --> 00:48:12,296
Cool;

886
00:48:12,296 --> 00:48:13,290
ΟΚ.

887
00:48:13,290 --> 00:48:16,350
Παίρνει λίγο πιο περίπλοκη
όταν αρχίζουμε μπέρδεμα με το κεφάλι.

888
00:48:16,350 --> 00:48:17,060
Ναι;

889
00:48:17,060 --> 00:48:20,090
>> ΚΟΙΝΟ: Μήπως αυτό σημαίνει ότι εμείς
θα έχουν δηλώσει έναν πίνακα που

890
00:48:20,090 --> 00:48:23,880
Ήταν μεγάλη πέντε στοιχεία και
Στη συνέχεια προσθέτουμε σε αυτό;

891
00:48:23,880 --> 00:48:24,730
>> ΟΜΙΛΗΤΗΣ 1: Όχι.

892
00:48:24,730 --> 00:48:27,560
Έτσι, σε αυτή την περίπτωση, αυτό είναι μια στοίβα.

893
00:48:27,560 --> 00:48:31,760
Αυτό θα πρέπει να δηλώνονται
ως μια σειρά από μέγεθος 6.

894
00:48:31,760 --> 00:48:37,120
Και σε αυτή την περίπτωση, έχουμε
απλά έχουν ένα χώρο αριστερά.

895
00:48:37,120 --> 00:48:42,720
>> Εντάξει, έτσι ένα πράγμα είναι αυτό
περίπτωση, εάν το κεφάλι μας είναι στο 0,

896
00:48:42,720 --> 00:48:45,270
τότε μπορούμε απλά να το προσθέσετε στο μέγεθος.

897
00:48:45,270 --> 00:48:51,020
Αλλά παίρνει μια λίγο πιο περίπλοκη
επειδή στην πραγματικότητα, αυτοί

898
00:48:51,020 --> 00:48:52,840
δεν έχουν μια διαφάνεια
για αυτό, έτσι Πάω

899
00:48:52,840 --> 00:48:56,670
να συντάξει μία, διότι δεν είναι
είναι ότι αρκετά απλό μόλις

900
00:48:56,670 --> 00:48:59,230
αρχίσετε να απαλλαγούμε από τα πράγματα.

901
00:48:59,230 --> 00:49:03,920
Έτσι, ενώ με μια στοίβα
το μόνο που έχετε ποτέ

902
00:49:03,920 --> 00:49:08,920
να ανησυχείτε για το τι είναι το μέγεθος
όταν θέλετε να προσθέσετε κάτι σε,

903
00:49:08,920 --> 00:49:15,710
με μια ουρά θα πρέπει επίσης να
βεβαιωθείτε ότι το κεφάλι σας είναι λογιστικά,

904
00:49:15,710 --> 00:49:20,760
επειδή ένα δροσερό πράγμα για ουρές
είναι ότι, αν δεν είστε σε χωρητικότητα,

905
00:49:20,760 --> 00:49:23,040
μπορείτε πραγματικά να κάνετε το τυλίξετε γύρω.

906
00:49:23,040 --> 00:49:28,810
>> Εντάξει, έτσι ένα thing-- OH,
Αυτό είναι τρομερό κιμωλία.

907
00:49:28,810 --> 00:49:31,815
Ένα πράγμα που πρέπει να εξεταστεί είναι η περίπτωση.

908
00:49:31,815 --> 00:49:35,514

909
00:49:35,514 --> 00:49:37,140
Θα κάνουμε ακριβώς πέντε.

910
00:49:37,140 --> 00:49:41,810
Εντάξει, έτσι θα πάμε να
λένε ότι το κεφάλι είναι εδώ.

911
00:49:41,810 --> 00:49:46,140
Αυτό είναι 0, 1, 2, 3, 4.

912
00:49:46,140 --> 00:49:54,210
>> Το κεφάλι είναι εκεί, και
παρακαλώ να έχετε τα πράγματα σε αυτά.

913
00:49:54,210 --> 00:49:58,340
Και θέλουμε να προσθέσουμε κάτι σε, σωστά;

914
00:49:58,340 --> 00:50:01,170
Έτσι, το πράγμα που πρέπει να
γνωρίζουμε είναι ότι το κεφάλι είναι πάντα

915
00:50:01,170 --> 00:50:05,620
πρόκειται να κινηθεί με αυτό τον τρόπο και
τότε βρόχο πίσω γύρω, εντάξει;

916
00:50:05,620 --> 00:50:10,190
>> Έτσι, αυτή η ουρά έχει χώρο, σωστά;

917
00:50:10,190 --> 00:50:13,950
Έχει χώρο στην αρχή,
είδος του αντίθετου αυτό.

918
00:50:13,950 --> 00:50:17,920
Έτσι, αυτό που πρέπει να κάνουμε είναι να
πρέπει να υπολογίσει την ουρά.

919
00:50:17,920 --> 00:50:20,530
Αν ξέρετε ότι σας
το κεφάλι δεν έχει μετακινηθεί, ουρά

920
00:50:20,530 --> 00:50:24,630
είναι ακριβώς σειρά σας σε
ο δείκτης του μεγέθους.

921
00:50:24,630 --> 00:50:30,000
>> Αλλά στην πραγματικότητα, αν χρησιμοποιείτε μια ουρά,
το κεφάλι σου είναι πιθανόν να ενημερώνεται.

922
00:50:30,000 --> 00:50:33,890
Έτσι, αυτό που χρειάζεται να κάνετε είναι να
πράγματι υπολογίσει την ουρά.

923
00:50:33,890 --> 00:50:39,990
Έτσι, αυτό που κάνουμε είναι αυτός ο τύπος
εδώ, η οποία Πάω να σας αποκαλύψω

924
00:50:39,990 --> 00:50:42,680
παιδιά σκέφτομαι, και
Στη συνέχεια θα μιλήσουμε γι 'αυτό.

925
00:50:42,680 --> 00:50:49,567

926
00:50:49,567 --> 00:50:50,400
Έτσι, αυτό είναι ικανότητα.

927
00:50:50,400 --> 00:50:55,890

928
00:50:55,890 --> 00:50:59,660
>> Έτσι, αυτό θα είναι πράγματι
να σας δώσει έναν τρόπο να το κάνουμε.

929
00:50:59,660 --> 00:51:03,205

930
00:51:03,205 --> 00:51:04,330
Επειδή σε αυτή την περίπτωση, τι;

931
00:51:04,330 --> 00:51:09,205
Το κεφάλι μας είναι στο 1, το μέγεθος μας είναι 4.

932
00:51:09,205 --> 00:51:11,760

933
00:51:11,760 --> 00:51:18,490
Αν mod ότι από 5, παίρνουμε 0,
η οποία είναι όπου θα πρέπει να εισάγετε.

934
00:51:18,490 --> 00:51:23,320

935
00:51:23,320 --> 00:51:26,080
>> Έτσι, στη συνέχεια, στην επόμενη περίπτωση,
αν ήταν να το κάνετε αυτό,

936
00:51:26,080 --> 00:51:33,390
λέμε, εντάξει, ας dequeue κάτι.

937
00:51:33,390 --> 00:51:34,390
Εμείς dequeue αυτό.

938
00:51:34,390 --> 00:51:37,740
Βγάζουμε το στοιχείο αυτό, σωστά;

939
00:51:37,740 --> 00:51:47,930
>> Και τώρα το κεφάλι μας προς τα εδώ,
και θέλουμε να προσθέσουμε σε ένα άλλο πράγμα.

940
00:51:47,930 --> 00:51:52,470
Αυτή είναι βασικά η
πίσω από τη γραμμή μας, σωστά;

941
00:51:52,470 --> 00:51:55,450
Ουρές να τυλίξετε γύρω από τη συστοιχία.

942
00:51:55,450 --> 00:51:57,310
Αυτή είναι μία από τις κύριες διαφορές.

943
00:51:57,310 --> 00:51:58,780
Στοίβες, δεν μπορείτε να το κάνετε αυτό.

944
00:51:58,780 --> 00:52:01,140
>> Με ουρές, μπορείτε να
γιατί όλα αυτά τα θέματα

945
00:52:01,140 --> 00:52:03,940
είναι ότι ξέρετε τι
ήταν πιο πρόσφατα πρόσθεσε.

946
00:52:03,940 --> 00:52:10,650
Από ό, τι πρόκειται να προστεθεί στην
Αυτή η αριστερά κατεύθυνση, σε αυτή την περίπτωση,

947
00:52:10,650 --> 00:52:16,480
και, στη συνέχεια, τυλίξτε γύρω, μπορείτε να
να συνεχίσει βάζοντας σε νέα στοιχεία

948
00:52:16,480 --> 00:52:18,830
στο μπροστινό μέρος της συστοιχίας
γιατί δεν είναι πραγματικά

949
00:52:18,830 --> 00:52:20,640
το μπροστινό μέρος του πίνακα πια.

950
00:52:20,640 --> 00:52:26,320
Μπορείτε να σκεφτείτε από την αρχή του
συστοιχία ως όπου το κεφάλι σας πραγματικά είναι.

951
00:52:26,320 --> 00:52:29,710
>> Έτσι, αυτός ο τύπος είναι το πώς
να υπολογίσετε την ουρά σου.

952
00:52:29,710 --> 00:52:32,780

953
00:52:32,780 --> 00:52:35,610
Μήπως αυτό έχει νόημα;

954
00:52:35,610 --> 00:52:36,110
ΟΚ.

955
00:52:36,110 --> 00:52:39,400

956
00:52:39,400 --> 00:52:44,040
Εντάξει, dequeue, και στη συνέχεια,
εσείς έχετε 10 λεπτά

957
00:52:44,040 --> 00:52:48,840
να μου υποβάλετε οποιεσδήποτε ερωτήσεις διευκρινιστική
θέλετε, γιατί ξέρω ότι είναι τρελό.

958
00:52:48,840 --> 00:52:51,980
>> Εντάξει, έτσι με τον ίδιο τρόπο--
Δεν ξέρω αν εσείς παρατηρήσει,

959
00:52:51,980 --> 00:52:53,450
αλλά CS είναι όλα σχετικά με τα πρότυπα.

960
00:52:53,450 --> 00:52:57,370
Τα πράγματα είναι λίγο πολύ το
ίδιο, μόνο με μικροσκοπικά τσιμπήματα.

961
00:52:57,370 --> 00:52:58,950
Έτσι ίδιο πράγμα εδώ.

962
00:52:58,950 --> 00:53:04,040
Θα πρέπει να ελέγξετε για να δείτε αν όντως
έχουν κάτι στην ουρά μας, σωστά;

963
00:53:04,040 --> 00:53:05,960
Ας πούμε, εντάξει, είναι το μέγεθός μας είναι μεγαλύτερη από 0;

964
00:53:05,960 --> 00:53:06,730
Cool.

965
00:53:06,730 --> 00:53:10,690
>> Αν το κάνουμε, τότε μπορούμε να μετακινήσετε το κεφάλι μας, η οποία
είναι αυτό που μόλις αποδειχθεί εδώ.

966
00:53:10,690 --> 00:53:13,870
Ενημερώνουμε το κεφάλι μας να είναι ένα ακόμη.

967
00:53:13,870 --> 00:53:18,390
Και τότε θα ελαττώσει μας
μεγέθους και να επιστρέψετε το στοιχείο.

968
00:53:18,390 --> 00:53:21,000

969
00:53:21,000 --> 00:53:26,250
>> Υπάρχει πολύ πιο συγκεκριμένη
κώδικα για study.cs50.net,

970
00:53:26,250 --> 00:53:29,440
και συστήνω ανεπιφύλακτα να πάτε
μέσα από αυτό, αν έχετε χρόνο,

971
00:53:29,440 --> 00:53:30,980
ακόμα κι αν είναι απλά ένα ψευδο-κώδικα.

972
00:53:30,980 --> 00:53:35,980
Και αν εσείς θέλετε να μιλήσετε μέσω
ότι μαζί μου ένας προς έναν, παρακαλώ επιτρέψτε μου

973
00:53:35,980 --> 00:53:37,500
γνωρίζει.

974
00:53:37,500 --> 00:53:38,770
Θα ήμουν ευτυχής να.

975
00:53:38,770 --> 00:53:42,720
Δομές δεδομένων, εάν
παίρνετε CS 124, θα

976
00:53:42,720 --> 00:53:47,830
γνωρίζουμε ότι οι δομές δεδομένων πάρει πολύ
διασκέδαση και αυτό είναι μόνο η αρχή.

977
00:53:47,830 --> 00:53:50,350
>> Έτσι, ξέρω ότι είναι δύσκολο.

978
00:53:50,350 --> 00:53:51,300
Είναι εντάξει.

979
00:53:51,300 --> 00:53:52,410
Παλεύουμε.

980
00:53:52,410 --> 00:53:53,630
Εξακολουθώ να κάνω.

981
00:53:53,630 --> 00:53:56,660
Γι 'αυτό μην ανησυχείτε πάρα πολύ για αυτό.

982
00:53:56,660 --> 00:54:02,390
>> Αλλά αυτό είναι βασικά σας
Crash Course σε δομές δεδομένων.

983
00:54:02,390 --> 00:54:03,400
Ξέρω ότι είναι πολλά.

984
00:54:03,400 --> 00:54:06,860
Υπάρχει κάτι που μπορούμε
Θα ήθελα να πάμε ξανά;

985
00:54:06,860 --> 00:54:09,400
Οτιδήποτε θέλουμε να μιλήσουμε μέσα;

986
00:54:09,400 --> 00:54:10,060
Ναι;

987
00:54:10,060 --> 00:54:16,525
>> ΚΟΙΝΟ: Για αυτό το παράδειγμα, έτσι
η νέα ουρά είναι στο 0 πάνω από αυτό;

988
00:54:16,525 --> 00:54:17,150
ΟΜΙΛΗΤΗΣ 1: Ναι.

989
00:54:17,150 --> 00:54:18,230
ΚΟΙΝΟ: Εντάξει.

990
00:54:18,230 --> 00:54:24,220
Έτσι, στη συνέχεια, περνάει,
θα είχατε 1 συν 4 or--

991
00:54:24,220 --> 00:54:27,671
>> ΟΜΙΛΗΤΗΣ 1: Έτσι θα έλεγαν,
όταν θέλουμε να πάει να κάνει αυτό ξανά;

992
00:54:27,671 --> 00:54:28,296
Κοινό: Ναι.

993
00:54:28,296 --> 00:54:38,290
Έτσι, αν ήταν υπολογίζοντας out-- όπου είναι
να υπολογίσετε την ουρά από το γεγονός ότι;

994
00:54:38,290 --> 00:54:44,260
>> ΟΜΙΛΗΤΗΣ 1: Έτσι, η ουρά
ήταν in-- Έχω αλλάξει αυτό.

995
00:54:44,260 --> 00:54:52,010
Έτσι, σε αυτό το παράδειγμα εδώ, αυτό ήταν
η συστοιχία ψάχνουμε, εντάξει;

996
00:54:52,010 --> 00:54:54,670
Έτσι έχουμε τα πράγματα σε 1, 2, 3, και 4.

997
00:54:54,670 --> 00:55:05,850
Έτσι έχουμε το κεφάλι μας είναι ίση με 1 σε
αυτό το σημείο, και το μέγεθος μας είναι ίση με 4

998
00:55:05,850 --> 00:55:07,050
σε αυτό το σημείο, σωστά;

999
00:55:07,050 --> 00:55:08,960
>> Θα συμφωνήσουμε όλοι ότι είναι η περίπτωση;

1000
00:55:08,960 --> 00:55:14,620
Έτσι κάνουμε το κεφάλι συν το μέγεθος, το οποίο
μας δίνει 5, και στη συνέχεια εμείς mod από 5.

1001
00:55:14,620 --> 00:55:20,690
Παίρνουμε 0, η οποία μας λέει ότι είναι 0
όπου είναι η ουρά μας, όπου έχουμε χώρο.

1002
00:55:20,690 --> 00:55:22,010
>> ΚΟΙΝΟ: Τι είναι ένα καπάκι;

1003
00:55:22,010 --> 00:55:23,520
>> ΟΜΙΛΗΤΗΣ 1: Η ικανότητα.

1004
00:55:23,520 --> 00:55:24,020
Λυπάμαι.

1005
00:55:24,020 --> 00:55:29,640
Έτσι, αυτό είναι το μέγεθος του πίνακα σας.

1006
00:55:29,640 --> 00:55:35,210

1007
00:55:35,210 --> 00:55:36,047
Ναι;

1008
00:55:36,047 --> 00:55:39,210
>> ΚΟΙΝΟ: [δεν ακούγεται] πριν
θα επιστρέψει το στοιχείο;

1009
00:55:39,210 --> 00:55:46,270
>> ΟΜΙΛΗΤΗΣ 1: Προχωρούμε λοιπόν η
το κεφάλι ή να επιστρέψετε τη στιγμή;

1010
00:55:46,270 --> 00:55:52,680
Έτσι, αν προχωρήσουμε ένα, να ελαττώσει το μέγεθος;

1011
00:55:52,680 --> 00:55:54,150
Περίμενε.

1012
00:55:54,150 --> 00:55:55,770
Σίγουρα ξέχασα άλλο.

1013
00:55:55,770 --> 00:56:00,646

1014
00:56:00,646 --> 00:56:01,990
Δεν πειράζει.

1015
00:56:01,990 --> 00:56:04,980
Δεν υπάρχει άλλο τύπο.

1016
00:56:04,980 --> 00:56:09,980
Ναι, θα θέλετε να επιστρέψετε
το κεφάλι και στη συνέχεια, μετακινηθείτε προς τα πίσω.

1017
00:56:09,980 --> 00:56:13,270
>> ΚΟΙΝΟ: Εντάξει, γιατί σε αυτό το
σημείο, το κεφάλι ήταν στο 0,

1018
00:56:13,270 --> 00:56:18,452
και στη συνέχεια θέλετε να επιστρέψετε
δείκτης 0 και στη συνέχεια να κάνουν το κεφάλι 1;

1019
00:56:18,452 --> 00:56:19,870
>> ΟΜΙΛΗΤΗΣ 1: Δεξιά.

1020
00:56:19,870 --> 00:56:22,820
Νομίζω ότι υπάρχει μια άλλη
τύπο κάτι σαν αυτό.

1021
00:56:22,820 --> 00:56:26,970
Εγώ δεν το έχουν στην κορυφή της κεφαλής μου ως
Δεν θέλω να σας δώσει το λάθος.

1022
00:56:26,970 --> 00:56:35,470
Αλλά νομίζω ότι είναι απόλυτα έγκυρο να
ας πούμε, εντάξει, να αποθηκεύσετε αυτή element-- ανεξαρτήτως

1023
00:56:35,470 --> 00:56:40,759
στοιχείο το κεφάλι του is-- ελαττώσει σας
μέγεθος, μετακινήστε το κεφάλι σας πάνω και επιστροφή

1024
00:56:40,759 --> 00:56:41,800
ό, τι το στοιχείο αυτό είναι.

1025
00:56:41,800 --> 00:56:44,760
Αυτό είναι απολύτως έγκυρη.

1026
00:56:44,760 --> 00:56:45,260
ΟΚ.

1027
00:56:45,260 --> 00:56:48,360

1028
00:56:48,360 --> 00:56:53,560
Νιώθω σαν αυτό δεν είναι
όπως το most-- δεν είστε

1029
00:56:53,560 --> 00:56:55,740
πρόκειται να περπατήσει από εδώ
όπως, ναι, ξέρω ότι προσπαθεί.

1030
00:56:55,740 --> 00:56:56,880
Μου πήρε όλα.

1031
00:56:56,880 --> 00:56:57,670
Αυτό είναι ΟΚ.

1032
00:56:57,670 --> 00:57:00,200
Υπόσχομαι.

1033
00:57:00,200 --> 00:57:05,240
Αλλά δομές δεδομένων είναι κάτι που
παίρνει πολύ χρόνο για να το συνηθίσετε.

1034
00:57:05,240 --> 00:57:10,010
Πιθανώς ένα από τα δυσκολότερα
τα πράγματα, νομίζω, κατά τη διάρκεια.

1035
00:57:10,010 --> 00:57:15,330
>> Γι 'αυτό παίρνει σίγουρα
επανάληψη και αναζητούν at-- μου

1036
00:57:15,330 --> 00:57:20,050
Δεν ήξερα πραγματικά συνδεδεμένες λίστες
έως ότου έκανα πάρα πολύ μαζί τους,

1037
00:57:20,050 --> 00:57:22,550
με τον ίδιο τρόπο που δεν το έκανα
πραγματικά καταλαβαίνω δείκτες

1038
00:57:22,550 --> 00:57:27,040
μέχρι Είχα να το διδάξει για δύο
χρόνια και να κάνω τη δική μου psets με αυτό.

1039
00:57:27,040 --> 00:57:28,990
Χρειάζεται πολλή επανάληψη και χρόνο.

1040
00:57:28,990 --> 00:57:32,600
Και τελικά, αυτό θα το είδος κάντε κλικ.

1041
00:57:32,600 --> 00:57:36,320
>> Αλλά εν τω μεταξύ, αν έχετε το είδος
ενός υψηλού επιπέδου κατανόηση του τι

1042
00:57:36,320 --> 00:57:39,321
Αυτά τα κάνουν, τα πλεονεκτήματα τους
και cons-- το οποίο είναι ό, τι

1043
00:57:39,321 --> 00:57:41,820
είμαστε πραγματικά τείνουν να δώσουν έμφαση,
ειδικά κατά τη διάρκεια intro.

1044
00:57:41,820 --> 00:57:45,511
Όπως, γιατί θα χρησιμοποιήσουμε
δοκιμάστε πάνω από μια σειρά;

1045
00:57:45,511 --> 00:57:48,010
Όπως, ποια είναι τα θετικά
και αρνητικά καθενός από αυτά;

1046
00:57:48,010 --> 00:57:51,610
>> Και η κατανόηση τους συμβιβασμούς
μεταξύ κάθε μία από αυτές τις δομές

1047
00:57:51,610 --> 00:57:54,910
είναι αυτό που είναι πολύ πιο σημαντικό αυτή τη στιγμή.

1048
00:57:54,910 --> 00:57:58,140
Μπορεί να υπάρχει ένας τρελός
ερώτηση ή δύο που είναι

1049
00:57:58,140 --> 00:58:03,710
πρόκειται να σας ζητήσω να εφαρμόσουν push ή
εφαρμογή ποπ ή Τοποθέτηση στην ουρά και dequeue.

1050
00:58:03,710 --> 00:58:07,340
Αλλά για το μεγαλύτερο μέρος, έχοντας ότι
υψηλότερο επίπεδο κατανόησης και περισσότερα

1051
00:58:07,340 --> 00:58:09,710
από μια διαισθητική κατανόηση είναι
πιο σημαντική από ό, τι στην πραγματικότητα

1052
00:58:09,710 --> 00:58:11,250
να είναι σε θέση να την εφαρμόσουν.

1053
00:58:11,250 --> 00:58:14,880
>> Θα ήταν πραγματικά φοβερό εάν όλοι σας
θα μπορούσε να πάει έξω και να πάει να εφαρμόσουν μια δοκιμή,

1054
00:58:14,880 --> 00:58:19,720
αλλά καταλαβαίνουμε ότι δεν είναι κατ 'ανάγκην
το πιο λογικό πράγμα τώρα.

1055
00:58:19,720 --> 00:58:23,370
Αλλά μπορείτε να το chipset σε σας, αν θέλετε
σε, και στη συνέχεια θα έχετε την πρακτική,

1056
00:58:23,370 --> 00:58:27,200
και, στη συνέχεια, ίσως θα
πραγματικά καταλαβαίνουν.

1057
00:58:27,200 --> 00:58:27,940
Ναι;

1058
00:58:27,940 --> 00:58:30,440
>> ΚΟΙΝΟ: Εντάξει, έτσι ποια είναι
εννοούσαμε να χρησιμοποιήσετε το το chipset;

1059
00:58:30,440 --> 00:58:31,916
Χρειάζεται να χρησιμοποιήσετε ένα από αυτά;

1060
00:58:31,916 --> 00:58:32,540
ΟΜΙΛΗΤΗΣ 1: Ναι.

1061
00:58:32,540 --> 00:58:34,199
Έτσι, έχετε την επιλογή σας.

1062
00:58:34,199 --> 00:58:36,740
Υποθέτω ότι σε αυτή την περίπτωση, μπορούμε
μιλήσουμε για το το chipset λίγο

1063
00:58:36,740 --> 00:58:40,480
γιατί έτρεξα μέσω αυτών.

1064
00:58:40,480 --> 00:58:47,779
Έτσι, στο το chipset σας, έχετε σας
επιλογή του προσπαθεί ή πίνακες κατακερματισμού.

1065
00:58:47,779 --> 00:58:49,570
Μερικοί άνθρωποι θα προσπαθήσουν
και χρησιμοποιήστε τα φίλτρα άνθιση,

1066
00:58:49,570 --> 00:58:51,840
αλλά εκείνοι τεχνικά δεν είναι σωστό.

1067
00:58:51,840 --> 00:58:55,804
Λόγω της πιθανολογική φύση τους,
δίνουν ψευδώς θετικά αποτελέσματα μερικές φορές.

1068
00:58:55,804 --> 00:58:57,095
Είναι δροσερή ματιά σε, όμως.

1069
00:58:57,095 --> 00:58:59,030
Το συνιστώ ανεπιφύλακτα ψάχνετε
σε αυτούς τουλάχιστον.

1070
00:58:59,030 --> 00:59:03,260
Αλλά έχετε την επιλογή σας
μεταξύ ενός πίνακα κατακερματισμού και μια δοκιμή.

1071
00:59:03,260 --> 00:59:06,660
Και αυτό πρόκειται να είναι, όπου
φορτώνετε στο λεξικό σας.

1072
00:59:06,660 --> 00:59:09,230
>> Και θα πρέπει να επιλέξετε
συνάρτηση κατακερματισμού σας,

1073
00:59:09,230 --> 00:59:13,420
θα πρέπει να επιλέξετε πόσες
Κάδοι έχετε, και θα ποικίλλουν.

1074
00:59:13,420 --> 00:59:17,440
Όπως και αν έχετε περισσότερους κάδους,
ίσως θα τρέξει πιο γρήγορα.

1075
00:59:17,440 --> 00:59:22,790
Αλλά ίσως να σπαταλάτε ένα
πολύ χώρο με αυτόν τον τρόπο, όμως.

1076
00:59:22,790 --> 00:59:26,320
Θα πρέπει να το καταλάβω.

1077
00:59:26,320 --> 00:59:27,140
Mmhmm;

1078
00:59:27,140 --> 00:59:29,875
>> ΚΟΙΝΟ: Είπατε πριν ότι
μπορούμε να χρησιμοποιήσουμε άλλες συναρτήσεις κατακερματισμού,

1079
00:59:29,875 --> 00:59:31,750
ότι δεν έχουμε να
δημιουργήσετε μια συνάρτηση κατακερματισμού;

1080
00:59:31,750 --> 00:59:32,666
>> ΟΜΙΛΗΤΗΣ 1: Ναι, σωστά.

1081
00:59:32,666 --> 00:59:38,150
Έτσι, κυριολεκτικά για την συνάρτηση κατακερματισμού σας,
όπως το google "συνάρτηση κατακερματισμού"

1082
00:59:38,150 --> 00:59:40,770
και να ψάξουν για μερικά δροσερά αυτά.

1083
00:59:40,770 --> 00:59:43,250
Δεν αναμένεται να οικοδομήσουμε
τις δικές σας συναρτήσεις κατακερματισμού.

1084
00:59:43,250 --> 00:59:46,100
Οι άνθρωποι ξοδεύουν τους
Θέσεις για αυτά τα πράγματα.

1085
00:59:46,100 --> 00:59:50,250
>> Γι 'αυτό μην ανησυχείτε για την οικοδόμηση δική σας.

1086
00:59:50,250 --> 00:59:53,350
Βρείτε ένα σε απευθείας σύνδεση για να αρχίσει με.

1087
00:59:53,350 --> 00:59:56,120
Μερικά από αυτά θα πρέπει να
χειριστείτε λίγο

1088
00:59:56,120 --> 00:59:59,430
για να βεβαιωθείτε ότι οι τύποι επιστροφής ταιριάζουν
και εταζέρα, έτσι στην αρχή,

1089
00:59:59,430 --> 01:00:02,420
Θα ήθελα να συστήσω χρησιμοποιώντας κάτι
πραγματικά εύκολο που ίσως μόνο

1090
01:00:02,420 --> 01:00:04,680
hashes για το πρώτο γράμμα.

1091
01:00:04,680 --> 01:00:08,760
Και στη συνέχεια, αφού έχετε αυτή την εργασία,
ενσωματώνει ένα ψύκτη συνάρτηση κατακερματισμού.

1092
01:00:08,760 --> 01:00:09,260
Mmhmm;

1093
01:00:09,260 --> 01:00:13,020
>> ΚΟΙΝΟ: Θα προσπαθήσουμε να είναι ή
αποτελεσματική, αλλά μόνο πιο δύσκολο να, like--

1094
01:00:13,020 --> 01:00:15,880
>> ΟΜΙΛΗΤΗΣ 1: Έτσι μια δοκιμή, νομίζω,
είναι διαισθητικά δύσκολο να εφαρμοστούν

1095
01:00:15,880 --> 01:00:18,310
αλλά είναι πολύ γρήγορη.

1096
01:00:18,310 --> 01:00:20,620
Ωστόσο, καταλαμβάνει περισσότερο χώρο.

1097
01:00:20,620 --> 01:00:25,270
Και πάλι, μπορείτε να βελτιστοποιήσετε τις δύο αυτές
διαφορετικούς τρόπους και υπάρχουν τρόποι to--

1098
01:00:25,270 --> 01:00:26,770
ΚΟΙΝΟ: Πώς θα βαθμολογούνται σε αυτό;

1099
01:00:26,770 --> 01:00:27,540
Μήπως matter--

1100
01:00:27,540 --> 01:00:29,164
>> ΟΜΙΛΗΤΗΣ 1: Έτσι είστε βαθμολογούνται κανονικό τρόπο.

1101
01:00:29,164 --> 01:00:31,330
Θα πάμε για να βαθμολογηθούν για το σχεδιασμό.

1102
01:00:31,330 --> 01:00:36,020
Όποιον τρόπο κι αν κάνετε, θέλετε να
βεβαιωθείτε ότι είναι τόσο κομψό όπως μπορεί να είναι

1103
01:00:36,020 --> 01:00:38,610
και τόσο αποτελεσματικές όσο μπορεί να είναι.

1104
01:00:38,610 --> 01:00:41,950
Αλλά αν επιλέξετε μια δοκιμή ή κατακερματισμού
τραπέζι, εφ 'όσον αυτό λειτουργεί,

1105
01:00:41,950 --> 01:00:45,350
είμαστε ευχαριστημένοι με αυτό.

1106
01:00:45,350 --> 01:00:48,370
Και αν μπορείτε να χρησιμοποιήσετε κάτι που hashes
για το πρώτο γράμμα, ότι είναι εντάξει,

1107
01:00:48,370 --> 01:00:51,410
όπως ίσως όπως ο σχεδιασμός-σοφός.

1108
01:00:51,410 --> 01:00:53,410
Είμαστε, επίσης, φθάνοντας το
σημείο σε αυτό το semester--

1109
01:00:53,410 --> 01:00:55,340
Δεν ξέρω αν σας
παιδιά noticed-- αν είστε

1110
01:00:55,340 --> 01:00:58,780
βαθμούς το chipset μειωθεί λίγο
λόγω του σχεδιασμού και εταζέρα,

1111
01:00:58,780 --> 01:00:59,900
ότι είναι απολύτως εντάξει.

1112
01:00:59,900 --> 01:01:02,960
Είναι να πάρει σε ένα σημείο όπου σας
προγράμματα γίνονται όλο και πιο περίπλοκη.

1113
01:01:02,960 --> 01:01:04,830
Υπάρχουν περισσότερες θέσεις
μπορείτε να βελτιώσετε.

1114
01:01:04,830 --> 01:01:06,370
>> Γι 'αυτό είναι απόλυτα φυσιολογικό.

1115
01:01:06,370 --> 01:01:08,810
Δεν είναι ότι είστε
κάνει χειρότερα για το chipset σας.

1116
01:01:08,810 --> 01:01:11,885
Είναι ακριβώς θέλουμε να είμαστε πιο δύσκολο για σας τώρα.

1117
01:01:11,885 --> 01:01:13,732
Έτσι, ο καθένας έχει το συναίσθημα.

1118
01:01:13,732 --> 01:01:14,940
Απλώς βαθμολογούνται όλα psets σας.

1119
01:01:14,940 --> 01:01:16,490
Ξέρω ότι ο καθένας έχει το συναίσθημα.

1120
01:01:16,490 --> 01:01:19,600
>> Έτσι, δεν πρέπει να ανησυχούν γι 'αυτό.

1121
01:01:19,600 --> 01:01:23,580
Και εάν έχετε οποιεσδήποτε ερωτήσεις σχετικά με
πριν psets ή τρόπους μπορείτε να βελτιώσετε,

1122
01:01:23,580 --> 01:01:27,760
Προσπαθώ και να σχολιάσει το συγκεκριμένο
θέσεις, αλλά μερικές φορές είναι αργά

1123
01:01:27,760 --> 01:01:30,840
και έχω κουραστεί.

1124
01:01:30,840 --> 01:01:34,885
Υπάρχουν άλλα πράγματα εκεί
σχετικά με τις δομές δεδομένων;

1125
01:01:34,885 --> 01:01:37,510
Είμαι βέβαιος ότι εσείς δεν κάνετε πραγματικά
θέλω να μιλήσω γι 'αυτούς πια,

1126
01:01:37,510 --> 01:01:42,650
αλλά αν υπάρχουν, είμαι στην ευχάριστη θέση να
πάει πάνω τους, καθώς και οτιδήποτε

1127
01:01:42,650 --> 01:01:45,580
από διάλεξη αυτό το παρελθόν
εβδομάδα ή την περασμένη εβδομάδα.

1128
01:01:45,580 --> 01:01:51,580
>> Ξέρω ότι την περασμένη εβδομάδα ήταν όλα επανεξέτασης, έτσι
μπορεί να έχουμε υπερπηδηθούν κάποια αναθεώρηση

1129
01:01:51,580 --> 01:01:54,190
από τη διάλεξη.

1130
01:01:54,190 --> 01:01:58,230
Οποιεσδήποτε άλλες ερωτήσεις μπορώ να απαντήσω;

1131
01:01:58,230 --> 01:01:59,350
Εντάξει, εντάξει.

1132
01:01:59,350 --> 01:02:02,400
Λοιπόν, εσείς να πάρετε πίσω 15 λεπτά νωρίτερα.

1133
01:02:02,400 --> 01:02:08,370
>> Ελπίζω ότι αυτό ήταν ημι-χρήσιμο, τουλάχιστον,
και εγώ θα σας δούμε παιδιά την επόμενη εβδομάδα,

1134
01:02:08,370 --> 01:02:12,150
ή την Πέμπτη τις ώρες γραφείου.

1135
01:02:12,150 --> 01:02:15,285
Οι αιτήσεις εκεί για σνακ
για την επόμενη εβδομάδα, αυτό είναι το πράγμα;

1136
01:02:15,285 --> 01:02:17,459
Επειδή ξέχασα καραμέλα σήμερα.

1137
01:02:17,459 --> 01:02:19,750
Και έφερα καραμέλα τελευταία
εβδομάδα, αλλά ήταν Ημέρα του Κολόμβου,

1138
01:02:19,750 --> 01:02:25,400
έτσι υπήρχαν όπως και έξι άτομα που
είχε τέσσερις σακούλες των καραμέλα για τους εαυτούς τους.

1139
01:02:25,400 --> 01:02:28,820
Μπορώ να φέρω αστρικές εκρήξεις
και πάλι, αν σας αρέσει.

1140
01:02:28,820 --> 01:02:29,580
Αστρικές εκρήξεις;

1141
01:02:29,580 --> 01:02:32,250
Εντάξει, ακούγεται καλό.

1142
01:02:32,250 --> 01:02:35,050
Έχετε μια μεγάλη μέρα, παιδιά.

1143
01:02:35,050 --> 01:02:39,510