1
00:00:00,000 --> 00:00:03,423
>> [Παίζει μουσική]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI PENG: Καλώς ήρθατε στην εβδομάδα 6 του τμήματος.

4
00:00:08,210 --> 00:00:11,620
Θα παρέκκλινε από το βιοτικό μας
χρόνος τμήμα της Τρίτης

5
00:00:11,620 --> 00:00:14,130
απόγευμα σε αυτό το υπέροχο την Κυριακή το πρωί.

6
00:00:14,130 --> 00:00:17,330
Σας ευχαριστώ για τον καθένα που
μαζί μου σήμερα, αλλά σοβαρά,

7
00:00:17,330 --> 00:00:18,170
ένα χειροκρότημα.

8
00:00:18,170 --> 00:00:20,600
>> Αυτό είναι μια αρκετά μεγάλη προσπάθεια.

9
00:00:20,600 --> 00:00:23,600
Εγώ σχεδόν δεν το κάνουν ακόμη
σε χρόνο, αλλά ήταν εντάξει.

10
00:00:23,600 --> 00:00:27,520
Έτσι ξέρω ότι όλοι σας
μόλις έκανε στο κουίζ.

11
00:00:27,520 --> 00:00:30,370
Πρώτα απ 'όλα, καλώς ήλθατε
η άλλη πλευρά του ότι.

12
00:00:30,370 --> 00:00:32,917
>> Δεύτερον, θα μιλήσουμε γι 'αυτό.

13
00:00:32,917 --> 00:00:34,000
Θα μιλήσουμε για το κουίζ.

14
00:00:34,000 --> 00:00:35,700
Θα μιλήσουμε για το πώς
κάνετε στην τάξη.

15
00:00:35,700 --> 00:00:36,550
Θα είσαι μια χαρά.

16
00:00:36,550 --> 00:00:39,080
Έχω κουίζ σας για
που στο τέλος της εδώ,

17
00:00:39,080 --> 00:00:42,120
Έτσι, αν εσείς θέλετε να πάρετε
μια ματιά σε αυτό, εντελώς εντάξει.

18
00:00:42,120 --> 00:00:46,590
>> Έτσι, γρήγορα, πριν ξεκινήσουμε, η
ατζέντα για σήμερα έχει ως εξής.

19
00:00:46,590 --> 00:00:48,430
Όπως μπορείτε να δείτε, είμαστε
βασικά ταχείας βολής

20
00:00:48,430 --> 00:00:52,120
μέσα από ένα σωρό δομών δεδομένων
πραγματικά, πραγματικά, πραγματικά γρήγορα.

21
00:00:52,120 --> 00:00:54,380
Έτσι ως τέτοια, δεν θα είναι
σούπερ διαδραστικά σήμερα.

22
00:00:54,380 --> 00:00:59,620
Δεν θα πρέπει ακριβώς να μου φωνάζει το είδος του
Πράγματα που, και αν μπορώ να σας μπερδέψει,

23
00:00:59,620 --> 00:01:02,680
Αν πάω πάρα πολύ γρήγορα, επιτρέψτε μου να ξέρω.

24
00:01:02,680 --> 00:01:05,200
Είναι απλά διάφορα στοιχεία
δομές, και ως μέρος

25
00:01:05,200 --> 00:01:07,070
από το chipset σας για αυτή
την ερχόμενη βδομάδα, θα

26
00:01:07,070 --> 00:01:10,340
κληθούν να εφαρμόσουν ένα από αυτά,
ίσως δύο από them-- δύο από αυτούς

27
00:01:10,340 --> 00:01:12,319
στο PSET σας.

28
00:01:12,319 --> 00:01:14,610
Εντάξει, έτσι είμαι απλώς πρόκειται να
ξεκινήσουμε με κάποιες ανακοινώσεις.

29
00:01:14,610 --> 00:01:19,070
Θα πάμε πάνω από στοίβες και ουρές περισσότερο
βάθος από ό, τι κάναμε πριν από το κουίζ.

30
00:01:19,070 --> 00:01:20,990
Θα πάμε πάνω συνδέεται
λίστα και πάλι, για μια ακόμη φορά,

31
00:01:20,990 --> 00:01:23,899
περισσότερο σε βάθος από ό, τι
είχαμε πριν από την κουίζ.

32
00:01:23,899 --> 00:01:26,440
Και τότε θα μιλήσουμε για χασίς
πίνακες, τα δέντρα και προσπαθεί, η οποία

33
00:01:26,440 --> 00:01:28,890
είναι όλα πολύ απαραίτητο για το chipset σας.

34
00:01:28,890 --> 00:01:32,925
Και τότε θα πάμε πάνω από κάποια
χρήσιμες συμβουλές για pset5.

35
00:01:32,925 --> 00:01:37,360
>> Εντάξει, έτσι κουίζ 0.

36
00:01:37,360 --> 00:01:41,090
Ο μέσος όρος ήταν 58%.

37
00:01:41,090 --> 00:01:45,370
Θα ήταν πολύ χαμηλή, και έτσι εσείς όλοι
έκανε πολύ, πολύ καλά σύμφωνα

38
00:01:45,370 --> 00:01:46,510
με αυτό.

39
00:01:46,510 --> 00:01:49,970
>> Λίγο πολύ, κανόνας είναι, αν είστε
εντός μια τυπική απόκλιση της μέσης

40
00:01:49,970 --> 00:01:52,990
δεδομένου μάλιστα ότι είμαστε σε μια λιγότερο
άνετο μέρος, είσαι μια χαρά.

41
00:01:52,990 --> 00:01:54,120
Είσαι σε καλό δρόμο.

42
00:01:54,120 --> 00:01:55,190
Η ζωή είναι ωραία.

43
00:01:55,190 --> 00:01:58,952
>> Ξέρω ότι είναι τρομακτικό να σκεφτεί κανείς ότι
Πήρα σαν ένα 40% σε αυτό το κουίζ.

44
00:01:58,952 --> 00:02:00,160
Πάω να αποτύχει αυτή την κατηγορία.

45
00:02:00,160 --> 00:02:02,243
Σας υπόσχομαι, δεν είστε
πρόκειται να αποτύχει την κατηγορία.

46
00:02:02,243 --> 00:02:03,680
Είσαι μια χαρά.

47
00:02:03,680 --> 00:02:06,850
>> Για όσους από εσάς πήρε πάνω
ο μέσος όρος, εντυπωσιακή, εντυπωσιακά,

48
00:02:06,850 --> 00:02:08,780
όπως, σοβαρά καλά κάνει.

49
00:02:08,780 --> 00:02:09,689
Τους έχω μαζί μου.

50
00:02:09,689 --> 00:02:11,730
Μη διστάσετε να έρθει να τους πάρει
στο τέλος της ενότητας.

51
00:02:11,730 --> 00:02:14,520
Επιτρέψτε μου να ξέρω αν έχετε οποιαδήποτε
θέματα, θέματα μαζί τους.

52
00:02:14,520 --> 00:02:17,204
Αν προσθέσουμε το αποτέλεσμά σας
λάθος, ενημερώστε μας.

53
00:02:17,204 --> 00:02:21,240
>> Εντάξει, έτσι pset5, αυτό είναι ένα πραγματικά
παράξενο εβδομάδα για Yale, με την έννοια

54
00:02:21,240 --> 00:02:24,240
ότι το chipset μας οφείλεται
Τετάρτη το μεσημέρι, συμπεριλαμβανομένων

55
00:02:24,240 --> 00:02:27,317
ο αείμνηστος μέρα, γι 'αυτό είναι πραγματικά
θεωρητικά οφείλεται Τρίτη το μεσημέρι.

56
00:02:27,317 --> 00:02:29,150
Μάλλον κανείς δεν τελείωσε
στις Τρίτη το μεσημέρι.

57
00:02:29,150 --> 00:02:30,830
Αυτό είναι εντελώς καλά.

58
00:02:30,830 --> 00:02:33,700
Εμείς πάμε για να έχουμε ώρες γραφείου
απόψε, καθώς το βράδυ της Δευτέρας.

59
00:02:33,700 --> 00:02:36,810
Και όλα τα τμήματα αυτής της εβδομάδας θα
πράγματι να μετατραπεί σε εργαστήρια,

60
00:02:36,810 --> 00:02:38,800
έτσι αισθάνεται ελεύθερη να σκάσει στα
κάθε ενότητα που θέλετε,

61
00:02:38,800 --> 00:02:42,810
και θα είναι είδος μίνι-PSET
εργαστήρια για βοήθεια σχετικά με αυτό.

62
00:02:42,810 --> 00:02:45,620
Έτσι ως τέτοιο, αυτό είναι το μόνο τμήμα
όπου είμαστε διδακτικό υλικό.

63
00:02:45,620 --> 00:02:49,220
Όλα τα άλλα τμήματα θα εστιάσει
αποκλειστικά στη βοήθεια για την PSET.

64
00:02:49,220 --> 00:02:50,146
Ναι;

65
00:02:50,146 --> 00:02:52,000
>> Κοινό: Πού είναι οι ώρες γραφείου;

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG: Ώρες εργασίας γραφείου
tonight-- Ω, καλή ερώτηση.

67
00:02:56,120 --> 00:03:00,580
Νομίζω ώρες γραφείου απόψε
είναι Teal ή Commons.

68
00:03:00,580 --> 00:03:02,984
Εάν ελέγχετε σε απευθείας σύνδεση CS50
και πηγαίνετε σε ώρες γραφείου,

69
00:03:02,984 --> 00:03:05,650
θα πρέπει να υπάρχει ένα πρόγραμμα που
σας όπου όλοι τους είναι λέει.

70
00:03:05,650 --> 00:03:07,954
>> Ξέρω είτε απόψε
ή αύριο είναι κιρκίρι,

71
00:03:07,954 --> 00:03:10,120
και νομίζω ότι μπορεί να έχουμε
commons για την άλλη νύχτα.

72
00:03:10,120 --> 00:03:11,020
Δεν ειμαι σιγουρος.

73
00:03:11,020 --> 00:03:11,700
Καλή ερώτηση.

74
00:03:11,700 --> 00:03:14,430
Έλεγχος CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, οποιεσδήποτε ερωτήσεις σχετικά με το
χρονοδιάγραμμα για την επόμενη σαν τρεις μέρες;

76
00:03:18,780 --> 00:03:21,690
Υπόσχομαι εσείς σαν τον Δαβίδ
είπε, αυτή είναι η κορυφή του λόφου.

77
00:03:21,690 --> 00:03:23,050
Εσείς είστε σχεδόν εκεί.

78
00:03:23,050 --> 00:03:24,644
Μόλις τρεις μέρες.

79
00:03:24,644 --> 00:03:26,310
Φύγε από εκεί, και στη συνέχεια όλοι θα κατέβει.

80
00:03:26,310 --> 00:03:28,114
Θα έχουμε ένα ωραίο CS-δωρεάν διάλειμμα.

81
00:03:28,114 --> 00:03:28,780
Καλωσόρισες πίσω.

82
00:03:28,780 --> 00:03:30,779
Θα βουτήξει διαδίκτυο
προγραμματισμός και ανάπτυξη,

83
00:03:30,779 --> 00:03:35,150
πράγματα που είναι πολύ διασκεδαστικό σύγκριση
για μερικά από τα άλλα psets.

84
00:03:35,150 --> 00:03:37,974
Και αυτό θα είναι ψύχρα, και
θα έχουν πολλή διασκέδαση.

85
00:03:37,974 --> 00:03:38,890
Θα έχουμε περισσότερες καραμέλα.

86
00:03:38,890 --> 00:03:39,730
Συγγνώμη για την καραμέλα.

87
00:03:39,730 --> 00:03:40,945
Ξέχασα καραμέλα.

88
00:03:40,945 --> 00:03:43,310
Ήταν μια πρόχειρη πρωί.

89
00:03:43,310 --> 00:03:46,340
Έτσι, εσείς είστε σχεδόν εκεί,
και είμαι πραγματικά περήφανος για σας παιδιά.

90
00:03:46,340 --> 00:03:49,570
>> Εντάξει, έτσι στοίβες.

91
00:03:49,570 --> 00:03:53,331
Που αγάπησε το ερώτημα για τον Jack
και τα ρούχα του στο κουίζ;

92
00:03:53,331 --> 00:03:53,830
Κανένας?

93
00:03:53,830 --> 00:03:56,500
Εντάξει, αυτό είναι εντάξει.

94
00:03:56,500 --> 00:04:00,200
>> Έτσι, κατ 'ουσίαν, όπως μπορείτε
εικόνα Jack, αυτός ο τύπος εδώ,

95
00:04:00,200 --> 00:04:03,350
αγαπά να πάρει τα ρούχα
από την κορυφή της στοίβας,

96
00:04:03,350 --> 00:04:05,750
και το βάζει πίσω στο
η στοίβα μετά έχει κάνει.

97
00:04:05,750 --> 00:04:07,600
Έτσι, με αυτόν τον τρόπο, ο ίδιος ποτέ
φαίνεται να παίρνει

98
00:04:07,600 --> 00:04:10,090
στο κάτω μέρος της
στοίβα στα ρούχα του.

99
00:04:10,090 --> 00:04:12,600
Έτσι, αυτό το είδος του περιγράφει
η βασική δομή δεδομένων

100
00:04:12,600 --> 00:04:16,610
του πώς υλοποιείται μια στοίβα.

101
00:04:16,610 --> 00:04:20,060
>> Ουσιαστικά, σκεφτείτε ένα
στοίβα όπως και κάθε στοίβα αντικειμένων

102
00:04:20,060 --> 00:04:24,900
όπου μπορείτε να βάλετε τα πράγματα στο επάνω μέρος, και
Στη συνέχεια μπορείτε να πεταχτεί έξω από την κορυφή.

103
00:04:24,900 --> 00:04:28,600
Έτσι LIFO είναι το ακρωνύμιο που μας αρέσουν
να use-- Τελευταία In, First Out.

104
00:04:28,600 --> 00:04:32,480
Και έτσι αντέξει στο επάνω μέρος της
στοίβα είναι το πρώτο που βγαίνει.

105
00:04:32,480 --> 00:04:34,260
Και έτσι οι δύο όροι
θα ήθελα να συμφωνήσω

106
00:04:34,260 --> 00:04:36,190
με τα οποία καλούνται ώθησης και ποπ.

107
00:04:36,190 --> 00:04:39,790
Όταν πατήσετε κάτι πάνω στο
στοίβα, και μπορείτε να επανακάμψει.

108
00:04:39,790 --> 00:04:43,422
>> Και έτσι υποθέτω ότι αυτό είναι το είδος της μια
αφηρημένη έννοια για όσους από εσάς

109
00:04:43,422 --> 00:04:45,630
οι οποίοι θέλουν να δουν, όπως ένας
πραγματική εφαρμογή της παρούσας

110
00:04:45,630 --> 00:04:46,740
στον πραγματικό κόσμο.

111
00:04:46,740 --> 00:04:50,170
Πόσοι από εσάς έχετε γράψει ένα δοκίμιο
ίσως σαν μία ώρα πριν από την οφειλόταν,

112
00:04:50,170 --> 00:04:54,510
και διαγράψατε κατά λάθος ένα τεράστιο
κομμάτι του, όπως κατά λάθος;

113
00:04:54,510 --> 00:04:58,560
Και τότε τι κάνουμε έλεγχο
που χρησιμοποιούμε για να το βάλει πίσω;

114
00:04:58,560 --> 00:05:00,030
Control-Z, ναι;

115
00:05:00,030 --> 00:05:03,640
Control-Z, έτσι ώστε το ποσό των φορές
ότι Έλεγχος-Z έχει σώσει τη ζωή μου,

116
00:05:03,640 --> 00:05:08,820
έχει σώσει τον κώλο μου, κάθε φορά
ότι υλοποιούνται μέσω των καπνοδόχου.

117
00:05:08,820 --> 00:05:13,020
>> Ουσιαστικά όλες οι πληροφορίες
ότι είναι σε έγγραφο του Word,

118
00:05:13,020 --> 00:05:15,080
παίρνει έσπρωξε και έσκασε κατά βούληση.

119
00:05:15,080 --> 00:05:19,460
Και έτσι ουσιαστικά κάθε φορά που
διαγράψετε κάτι, μπορείτε να επανακάμψει.

120
00:05:19,460 --> 00:05:22,820
Και στη συνέχεια, αν το χρειάζεστε πίσω, σας
σπρώξτε, το οποίο είναι αυτό που κάνει Control-C.

121
00:05:22,820 --> 00:05:26,770
Και κόσμου λειτουργούν τόσο πραγματική
πώς απλή δομή δεδομένων

122
00:05:26,770 --> 00:05:28,690
μπορεί να βοηθήσει με την καθημερινή ζωή σας.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Έτσι, ένα struct είναι ο τρόπος που
έχουμε δημιουργήσει πραγματικά μια στοίβα.

125
00:05:40,150 --> 00:05:44,720
Πληκτρολογούμε τον καθορισμό struct, και στη συνέχεια,
καλούμε στοίβα στο κάτω μέρος.

126
00:05:44,720 --> 00:05:47,440
Και μέσα στη στοίβα,
έχουμε δύο παραμέτρους

127
00:05:47,440 --> 00:05:51,580
ότι μπορούμε να χειριστούμε, κατ 'ουσίαν,
έτσι έχουμε χαρα ικανότητα χορδές αστέρων.

128
00:05:51,580 --> 00:05:55,150
>> Το μόνο που θα κάνει
δημιουργεί μια σειρά

129
00:05:55,150 --> 00:05:58,835
ότι μπορούμε να αποθηκεύσουμε ό, τι θέλετε
το οποίο μπορούμε να προσδιορίζει τις δυνατότητές του.

130
00:05:58,835 --> 00:06:01,990
Χωρητικότητα Είναι ακριβώς το μέγιστο ποσό της
τα στοιχεία μπορούμε να βάλουμε σε αυτόν τον πίνακα.

131
00:06:01,990 --> 00:06:05,660
μέγεθος int είναι ο μετρητής που διατηρεί
παρακολουθείτε πόσα στοιχεία είναι προς το παρόν

132
00:06:05,660 --> 00:06:07,850
στη στοίβα.

133
00:06:07,850 --> 00:06:11,860
Έτσι, τότε μπορούμε να παρακολουθείτε, Α,
τόσο το πόσο μεγάλο είναι το πραγματικό στοίβα είναι,

134
00:06:11,860 --> 00:06:14,850
και, Β, πόσα από αυτά τα στοίβας
γεμίσαμε γιατί δεν θέλουμε

135
00:06:14,850 --> 00:06:18,800
να ξεχειλίσει πάνω από ό, τι την ικανότητά μας είναι.

136
00:06:18,800 --> 00:06:24,340
>> Έτσι, για παράδειγμα, αυτό το υπέροχο
ερώτημα ήταν σε ένα κουίζ σας.

137
00:06:24,340 --> 00:06:28,160
Ουσιαστικά πώς θα ωθήσει
πάνω στην κορυφή της στοίβας.

138
00:06:28,160 --> 00:06:28,830
Πολύ απλά.

139
00:06:28,830 --> 00:06:30,621
Αν το δει κανείς,
θα περπατήσετε μέσα από αυτό.

140
00:06:30,621 --> 00:06:32,640
Εάν [δεν ακούγεται] size--
θυμηθείτε, κάθε φορά που

141
00:06:32,640 --> 00:06:35,300
θέλουν να έχουν πρόσβαση σε οποιαδήποτε
παράμετρος μέσα σε ένα struct,

142
00:06:35,300 --> 00:06:40,320
κάνετε το όνομα της struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> Σε αυτή την περίπτωση, το s είναι
το όνομα του stack μας.

144
00:06:42,720 --> 00:06:46,230
Θέλουμε να αποκτήσετε πρόσβαση στο μέγεθος
από αυτό, έτσι ώστε να κάνουμε s.size.

145
00:06:46,230 --> 00:06:50,280
Έτσι εφ 'όσον το μέγεθος δεν είναι
ισούται με την ικανότητα ή εφ '

146
00:06:50,280 --> 00:06:52,940
δεδομένου ότι είναι λιγότερο από την ικανότητα,
είτε θα μπορούσε να λειτουργήσει εδώ.

147
00:06:52,940 --> 00:06:57,180
>> Θέλετε να αποκτήσετε πρόσβαση στο εσωτερικό
του stack σας, έτσι s.strings,

148
00:06:57,180 --> 00:07:00,790
και θα πάμε για να θέσει το νέο αριθμό
ότι θέλετε να εισαγάγετε στο εκεί.

149
00:07:00,790 --> 00:07:05,030
Ας πούμε απλά ότι θα θελήσουμε να
εισάγετε int n στη στοίβα,

150
00:07:05,030 --> 00:07:08,905
θα μπορούσαμε να κάνουμε s.strings,
παρένθεση, s.size ισούται με n.

151
00:07:08,905 --> 00:07:11,030
Επειδή το μέγεθος είναι όπου είμαστε
Αυτή τη στιγμή είναι στη στοίβα

152
00:07:11,030 --> 00:07:14,590
αν θα πάμε για να ωθήσει
τον, εμείς απλά πρόσβαση

153
00:07:14,590 --> 00:07:17,370
όπου το μέγεθος είναι, η
τρέχουσα πληρότητα της στοίβας,

154
00:07:17,370 --> 00:07:21,729
και πιέστε το int n επάνω σε αυτό.

155
00:07:21,729 --> 00:07:24,770
Και μετά θέλουμε να βεβαιωθείτε ότι
είμαστε επίσης που αυξάνει το μέγεθος του n,

156
00:07:24,770 --> 00:07:27,436
έτσι ώστε να μπορείτε να παρακολουθείτε έχουμε
προστίθεται ένα επιπλέον πράγμα στη στοίβα.

157
00:07:27,436 --> 00:07:29,660
Τώρα έχουμε ένα μεγαλύτερο μέγεθος.

158
00:07:29,660 --> 00:07:33,196
Μήπως αυτό εδώ έχει νόημα να
ο καθένας, πώς λογικά λειτουργεί;

159
00:07:33,196 --> 00:07:34,160
Ήταν το είδος του γρήγορα.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
Κοινό: Μπορείτε να πάτε πάνω
οι s.stringss.strings [s.size] και πάλι;

162
00:07:42,160 --> 00:07:45,808
ANDI PENG: Σίγουρα, ναι, τι κάνει
s.size σήμερα μας δίνουν;

163
00:07:45,808 --> 00:07:47,440
Κοινό: Είναι το τρέχον μέγεθος.

164
00:07:47,440 --> 00:07:50,890
ANDI PENG: Ακριβώς, έτσι ώστε η
Ευρετήριο που το μέγεθός μας είναι,

165
00:07:50,890 --> 00:07:57,780
και έτσι θέλουμε να θέσει το νέο ακέραιο
ότι θέλουμε να εισαγάγει s.size.

166
00:07:57,780 --> 00:07:58,760
Βγάζει νόημα αυτό?

167
00:07:58,760 --> 00:08:01,110
Επειδή s.strings, όλα αυτά
είναι είναι το όνομα της συστοιχίας.

168
00:08:01,110 --> 00:08:03,510
Όλα είναι είναι η πρόσβαση
σειρά μέσα struct μας,

169
00:08:03,510 --> 00:08:06,030
και έτσι αν θέλουμε να
τοποθετήστε n σε αυτό το δείκτη,

170
00:08:06,030 --> 00:08:09,651
μπορούμε μόνο να έχει πρόσβαση
μέσα σε αγκύλες s.size.

171
00:08:09,651 --> 00:08:10,150
Δροσερός.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Εντάξει, ποπ, εγώ ο ψευδοκώδικας έξω
για σας παιδιά, αλλά παρόμοια ιδέα.

174
00:08:18,916 --> 00:08:19,790
Βγάζει νόημα αυτό?

175
00:08:19,790 --> 00:08:22,310
Εάν το μέγεθος είναι μεγαλύτερο
από το μηδέν, τότε

176
00:08:22,310 --> 00:08:25,350
Γνωρίζουμε ότι θέλετε να πάρετε κάτι
έξω, διότι αν το μέγεθος δεν είναι

177
00:08:25,350 --> 00:08:27,620
μεγαλύτερη από το μηδέν, τότε θα
δεν έχουν τίποτα στη στοίβα.

178
00:08:27,620 --> 00:08:29,840
>> Έτσι, το μόνο που θέλετε να εκτελέσει
αυτός ο κώδικας, το μόνο που μπορεί

179
00:08:29,840 --> 00:08:32,320
pop αν υπάρχει κάτι για να σκάσει.

180
00:08:32,320 --> 00:08:35,830
Έτσι, αν το μέγεθος είναι μεγαλύτερο
από 0, έχουμε μείον το μέγεθος.

181
00:08:35,830 --> 00:08:40,020
Θα μειώσετε το μέγεθος και στη συνέχεια να επιστρέψει
ό, τι είναι μέσα σε αυτό, διότι

182
00:08:40,020 --> 00:08:42,710
με το σκάσιμο, θέλουμε να
Πρόσβαση ό, τι είναι αποθηκευμένο

183
00:08:42,710 --> 00:08:45,694
στο δείκτη του στην κορυφή της στοίβας.

184
00:08:45,694 --> 00:08:46,610
Τα πάντα νόημα;

185
00:08:46,610 --> 00:08:49,693
Αν έκανα εσείς γράφετε αυτό έξω,
θα σας παιδιά να είναι σε θέση να το γράψω;

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
Εντάξει, εσείς μπορείτε να παίξετε γύρω με αυτό.

188
00:08:53,570 --> 00:08:55,252
Μην ανησυχείτε αν δεν το πάρει.

189
00:08:55,252 --> 00:08:57,460
Δεν έχουμε χρόνο για να κωδικοποιήσει
έξω σήμερα, διότι έχουμε

190
00:08:57,460 --> 00:08:59,959
πήρε πολλά από αυτές τις δομές
να περάσει, αλλά κατ 'ουσίαν

191
00:08:59,959 --> 00:09:02,214
ψευδοκώδικας, πολύ, πολύ παρόμοια με ώθηση.

192
00:09:02,214 --> 00:09:03,380
Απλά ακολουθήστε κατά μήκος της λογικής.

193
00:09:03,380 --> 00:09:06,092
Βεβαιωθείτε ότι έχετε πρόσβαση όλα τα
χαρακτηριστικά του struct σας σωστά.

194
00:09:06,092 --> 00:09:06,574
Ναι;

195
00:09:06,574 --> 00:09:09,282
>> Κοινό: Θα αυτές οι διαφάνειες και
όλο αυτό το πράγμα είναι μέχρι σήμερα-ish;

196
00:09:09,282 --> 00:09:11,586
ANDI PENG: Πάντα, Ναι.

197
00:09:11,586 --> 00:09:13,710
Πάω να προσπαθήσουμε να βάλουμε
Αυτό σαν μια ώρα μετά.

198
00:09:13,710 --> 00:09:16,626
Θα email Δαβίδ, ο Δαβίδ θα προσπαθήσει να
το βάζουμε σαν μια ώρα μετά από αυτό.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> Εντάξει, έτσι ώστε στη συνέχεια να προχωρήσουμε σε αυτή την άλλη
όμορφη δομή δεδομένων που ονομάζεται ουρά.

201
00:09:25,470 --> 00:09:30,140
Όπως εσείς μπορείτε να δείτε εδώ, μια
ουρά, για τη βρετανική ανάμεσά μας,

202
00:09:30,140 --> 00:09:32,010
όλα είναι είναι μια γραμμή.

203
00:09:32,010 --> 00:09:34,680
Έτσι, σε αντίθεση με ό, τι
νομίζετε ότι είναι μια στοίβα,

204
00:09:34,680 --> 00:09:37,750
μια ουρά είναι ακριβώς ό, τι
λογικά νομίζετε ότι είναι.

205
00:09:37,750 --> 00:09:41,914
Είναι που πραγματοποιήθηκε από τους κανόνες της FIFO,
που είναι το πρώτο In, First Out.

206
00:09:41,914 --> 00:09:43,705
Εάν είστε ο πρώτος
ένα στη γραμμή, είστε

207
00:09:43,705 --> 00:09:46,230
το πρώτο που
βγαίνει από τη γραμμή.

208
00:09:46,230 --> 00:09:49,680
>> Έτσι, αυτό που μας αρέσει να αποκαλούμε αυτό
είναι dequeueing και enqueueing.

209
00:09:49,680 --> 00:09:52,380
Αν θέλουμε να προσθέσουμε κάτι
στην ουρά μας, εμείς Τοποθέτηση στην ουρά.

210
00:09:52,380 --> 00:09:55,690
Αν θέλουμε να dequeue, ή να λάβει
κάτι μακριά, εμείς dequeue.

211
00:09:55,690 --> 00:10:03,350
>> Έτσι ίδια αίσθηση ότι είμαστε το είδος του
δημιουργώντας στοιχεία σταθερού μεγέθους ότι εμείς

212
00:10:03,350 --> 00:10:06,500
μπορούν να αποθηκεύσουν ορισμένες
πράγματα, αλλά μπορούμε επίσης

213
00:10:06,500 --> 00:10:10,100
αλλαγή, όπου είμαστε τοποθέτηση
παράμετροι στο εσωτερικό τους

214
00:10:10,100 --> 00:10:13,140
με βάση τον τύπο του
λειτουργικότητα που θέλουμε.

215
00:10:13,140 --> 00:10:16,700
Έτσι στοίβες, θέλαμε το τελευταίο
όνη, Ν να είναι ο πρώτος έξω.

216
00:10:16,700 --> 00:10:19,800
Ουρά θέλουμε είναι το πρώτο πράγμα
για να είναι το πρώτο πράγμα έξω.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Έτσι, το τύπου struct
καθορίσει, όπως μπορείτε να δείτε,

219
00:10:26,710 --> 00:10:29,470
Είναι λίγο διαφορετικό
από ό, τι ήταν η στοίβα

220
00:10:29,470 --> 00:10:33,120
γιατί όχι μόνο δεν πρέπει να έχουμε
παρακολουθείτε όπου το μέγεθος είναι επί του παρόντος,

221
00:10:33,120 --> 00:10:37,420
θέλουμε επίσης να παρακολουθείτε το κεφάλι
καθώς και πού βρισκόμαστε τώρα.

222
00:10:37,420 --> 00:10:39,580
Έτσι, νομίζω ότι είναι πιο εύκολο
αν ήθελα να επιστήσω αυτό επάνω.

223
00:10:39,580 --> 00:10:53,270
Έτσι, ας φανταστούμε ότι έχουμε μια ουρά,
Ας πούμε ότι το κεφάλι είναι ακριβώς εδώ.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
Ο επικεφαλής της γραμμής, ας
απλά να πω ότι είναι σήμερα εκεί,

226
00:10:58,310 --> 00:11:01,809
και θέλουμε να εισαγάγετε
κάτι στην ουρά.

227
00:11:01,809 --> 00:11:04,350
Πάω να καλέσω το μέγεθος ουσιαστικά
είναι το ίδιο πράγμα με την ουρά,

228
00:11:04,350 --> 00:11:06,314
το τέλος της ουράς, όπου σας είναι.

229
00:11:06,314 --> 00:11:07,730
Ας πούμε το μέγεθος είναι ακριβώς εδώ.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Έτσι, πώς μπορεί κανείς εφικτούς
εισάγετε κάτι σε μια ουρά;

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
Τι δείκτη θέλουμε να τοποθετήσετε
όπου θέλουμε να εισαγάγει.

234
00:11:24,130 --> 00:11:29,320
Αν αυτή είναι η αρχή του σας
ουρά και αυτό είναι το τέλος της

235
00:11:29,320 --> 00:11:31,860
ή το μέγεθός της, όπου εμείς
Θέλετε να προσθέσετε το επόμενο αντικείμενο;

236
00:11:31,860 --> 00:11:32,920
>> Κοινό: [δεν ακούγεται]

237
00:11:32,920 --> 00:11:35,920
ANDI PENG: Ακριβώς, που θέλετε να προσθέσετε
ανάλογα με το έχετε γράψει.

238
00:11:35,920 --> 00:11:37,840
Είτε αυτό είναι κενό ή ότι είναι κενό.

239
00:11:37,840 --> 00:11:42,630
Έτσι θέλετε να προσθέσετε πιθανώς
εδώ γιατί αν το μέγεθος is--

240
00:11:42,630 --> 00:11:50,540
αν όλα αυτά είναι πλήρη, θέλετε
να προστεθεί εδώ, σωστά;

241
00:11:50,540 --> 00:11:57,150
>> Και έτσι αυτό είναι, ενώ πολύ, πολύ
απλό, δεν είναι αρκετά πάντα σωστές

242
00:11:57,150 --> 00:12:00,690
επειδή η κύρια διαφορά
μεταξύ μια ουρά και μία στοίβα

243
00:12:00,690 --> 00:12:04,350
είναι ότι η ουρά μπορεί
πραγματικά να χειραγωγηθεί

244
00:12:04,350 --> 00:12:06,980
έτσι ώστε οι αλλαγές κεφάλι
ανάλογα με το πού θέλετε

245
00:12:06,980 --> 00:12:08,650
η αρχή της σύνθημά σας για να ξεκινήσετε.

246
00:12:08,650 --> 00:12:11,900
Και ως εκ τούτου, την ουρά σας
Επίσης, πρόκειται να αλλάξει.

247
00:12:11,900 --> 00:12:14,770
Και έτσι ρίξτε μια ματιά
ο κωδικός αυτός τώρα.

248
00:12:14,770 --> 00:12:18,620
Όπως σας παιδιά κλήθηκαν επίσης να
γράψτε στο κουίζ, Τοποθέτηση στην ουρά.

249
00:12:18,620 --> 00:12:22,580
Ίσως θα μιλήσουμε με τους οποίους
η απάντηση ήταν ό, τι ήταν.

250
00:12:22,580 --> 00:12:26,790
>> Εγώ δεν θα μπορούσε να χωρέσει αρκετά αυτή τη γραμμή σε ένα,
αλλά ουσιαστικά αυτό το κομμάτι του κώδικα

251
00:12:26,790 --> 00:12:29,030
θα πρέπει να είναι σε μία γραμμή.

252
00:12:29,030 --> 00:12:30,140
Περάστε όπως και 30 δευτερόλεπτα.

253
00:12:30,140 --> 00:12:33,000
Ρίξτε μια ματιά και δείτε γιατί
αυτός είναι ο τρόπος που είναι.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Πολύ, πολύ παρόμοια struct, πολύ, πολύ
παρόμοια δομή όπως η προηγούμενη

256
00:12:55,420 --> 00:12:58,090
στοίβα εκτός ίσως από
μία γραμμή κώδικα.

257
00:12:58,090 --> 00:13:01,190
Και ότι μία γραμμή κώδικα
καθορίζει τη λειτουργικότητα.

258
00:13:01,190 --> 00:13:03,900
Και αυτό διαφοροποιεί πραγματικά
μια ουρά από μια στοίβα.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Όποιος θέλει να λάβει μια μαχαιριά
σε εξηγώντας γιατί έχετε

261
00:13:22,010 --> 00:13:24,980
πήρε αυτό το περίπλοκο πράγμα εδώ;

262
00:13:24,980 --> 00:13:27,845
Βλέπουμε την επιστροφή μας
υπέροχο φίλο μέτρο.

263
00:13:27,845 --> 00:13:31,020
Όπως εσείς θα έρθει σύντομα
να αναγνωρίσει στον προγραμματισμό,

264
00:13:31,020 --> 00:13:34,910
σχεδόν οποιαδήποτε στιγμή χρειάζεστε κάτι
να τυλίξει γύρω από κάτι,

265
00:13:34,910 --> 00:13:36,850
συντελεστής θα είναι ο τρόπος για να το κάνουμε.

266
00:13:36,850 --> 00:13:40,510
Έτσι γνωρίζοντας ότι, δεν θέλει κανείς
να προσπαθήσουμε να τα εξηγήσουμε αυτή τη γραμμή του κώδικα;

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Ναι, όλες οι απαντήσεις είναι
αποδεκτή και ευπρόσδεκτη.

269
00:13:47,507 --> 00:13:48,840
Κοινό: Μιλάς σε μένα;

270
00:13:48,840 --> 00:13:49,506
ANDI PENG: Ναι.

271
00:13:49,506 --> 00:13:56,200
Κοινό: Ω, όχι συγγνώμη.

272
00:13:56,200 --> 00:14:00,250
ANDI PENG: ΟΚ, οπότε ας
με τα πόδια μέσα από αυτό τον κωδικό.

273
00:14:00,250 --> 00:14:03,642
Έτσι, όταν προσπαθείτε να
προσθέσει κάτι σε μια ουρά,

274
00:14:03,642 --> 00:14:08,510
στην όμορφη περίπτωση που η κεφαλή συμβαίνει
να είναι ακριβώς εδώ, είναι πολύ εύκολο για μας

275
00:14:08,510 --> 00:14:10,960
απλά να πάτε στο τέλος
εισάγετε κάτι, σωστά;

276
00:14:10,960 --> 00:14:14,690
Αλλά το νόημα του μια ουρά είναι
ότι η κεφαλή μπορεί πραγματικά δυναμικά

277
00:14:14,690 --> 00:14:17,280
αλλάζουν ανάλογα με το πού θα
θέλουν το ξεκίνημα του q μας να είναι,

278
00:14:17,280 --> 00:14:19,880
και ως εκ τούτου, την ουρά
Επίσης, πρόκειται να αλλάξει.

279
00:14:19,880 --> 00:14:31,100
>> Και έτσι φανταστείτε ότι αυτό δεν ήταν το
ουρά, αλλά αυτή ήταν η ουρά.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Ας πούμε ότι το κεφάλι είναι ακριβώς εδώ.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Ας πούμε ουρά μας έμοιαζε με αυτό.

284
00:14:56,980 --> 00:15:00,190
Αν θέλαμε να μετατοπίσει όπου
η αρχή της γραμμής είναι,

285
00:15:00,190 --> 00:15:03,400
Ας πούμε ότι μετατόπισε το κεφάλι
με αυτό τον τρόπο και τα μεγέθη εδώ.

286
00:15:03,400 --> 00:15:07,100
>> Τώρα θέλουμε να προσθέσουμε κάτι για να
Η ουρά, αλλά όπως μπορείτε να δείτε τα παιδιά,

287
00:15:07,100 --> 00:15:11,150
δεν είναι τόσο απλό όσο ακριβώς
προσθέστε ό, τι είναι μετά από το μέγεθος

288
00:15:11,150 --> 00:15:13,630
γιατί τότε θα ξεμείνει από
τα όρια των πραγματικών σειρά μας.

289
00:15:13,630 --> 00:15:16,190
Πού θέλουμε πραγματικά να προσθέσω είναι εδώ.

290
00:15:16,190 --> 00:15:18,610
Αυτή είναι η ομορφιά του μια ουρά
είναι ότι για εμάς, οπτικά

291
00:15:18,610 --> 00:15:22,380
Μοιάζει η γραμμή πηγαίνει όπως αυτό,
αλλά όταν αποθηκεύονται σε μια δομή δεδομένων,

292
00:15:22,380 --> 00:15:29,370
θα το δώσει ως σαν ένα κύκλο.

293
00:15:29,370 --> 00:15:32,360
Το είδος των τυλίγεται γύρω από
προς τα εμπρός με τον ίδιο τρόπο

294
00:15:32,360 --> 00:15:34,780
ότι μια γραμμή μπορεί επίσης να τυλίξετε
περίπου ανάλογα με όπου κι αν βρίσκεστε

295
00:15:34,780 --> 00:15:36,279
θέλουν να αρχή της γραμμής να είναι.

296
00:15:36,279 --> 00:15:38,630
Και έτσι αν πάρουμε ένα
κοιτάξτε εδώ κάτω, ας

297
00:15:38,630 --> 00:15:40,880
λένε θελήσαμε να δημιουργήσουμε ένα
λειτουργία που ονομάζεται Τοποθέτηση στην ουρά.

298
00:15:40,880 --> 00:15:43,980
Θέλαμε να προσθέσουμε int n σε εκείνο το q.

299
00:15:43,980 --> 00:15:49,250
Αν q.size q-- θα καλέσουμε ότι τα δεδομένα μας
structure-- αν queue.size μας δεν το κάνει

300
00:15:49,250 --> 00:15:52,520
ισούται με την ικανότητα ή αν
είναι μικρότερη από την ικανότητα,

301
00:15:52,520 --> 00:15:55,120
q.strings είναι η σειρά μας μέσα στο q.

302
00:15:55,120 --> 00:15:58,380
Εμείς πάμε για να ρυθμίσετε
ότι ισούται με q.heads,

303
00:15:58,380 --> 00:16:02,730
η οποία είναι ακριβώς εδώ, καθώς q.size
μέτρο από την ικανότητα, η οποία

304
00:16:02,730 --> 00:16:04,290
τυλίξτε μας πίσω εδώ γύρω.

305
00:16:04,290 --> 00:16:08,040
>> Έτσι, σε αυτό το παράδειγμα, ο δείκτης
της κεφαλής είναι 1, σωστά;

306
00:16:08,040 --> 00:16:11,480
Ο δείκτης του μέγεθος είναι 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Έτσι μπορούμε να κάνουμε 1 συν 4 συντελεστή
από την ικανότητά μας, το οποίο είναι 5.

308
00:16:19,500 --> 00:16:20,920
Τι πάει να μας δώσει;

309
00:16:20,920 --> 00:16:23,270
Τι είναι ο δείκτης που
βγαίνει από αυτό;

310
00:16:23,270 --> 00:16:24,080
>> Κοινό: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI PENG: 0, το οποίο
συμβαίνει να είναι ακριβώς εδώ,

312
00:16:27,870 --> 00:16:30,640
και έτσι θέλουμε να είναι σε θέση
να εισαγάγει εδώ.

313
00:16:30,640 --> 00:16:34,730
Και έτσι η εξίσωση αυτή εδώ είδους
του λειτουργεί ακριβώς με τυχόν αριθμούς

314
00:16:34,730 --> 00:16:36,750
ανάλογα με το πού σας
το κεφάλι και το μέγεθός σας είναι.

315
00:16:36,750 --> 00:16:38,541
Αν ξέρετε τι εκείνες
τα πράγματα είναι, ξέρετε

316
00:16:38,541 --> 00:16:43,170
ακριβώς στο σημείο όπου θέλετε να εισαγάγετε
ό, τι είναι μετά την ουρά σας.

317
00:16:43,170 --> 00:16:44,640
Μήπως αυτό έχει νόημα για όλους;

318
00:16:44,640 --> 00:16:48,560
>> Ξέρω ότι το είδος του εγκεφάλου
teaser ειδικά δεδομένου ότι αυτό

319
00:16:48,560 --> 00:16:50,512
ήρθε στον απόηχο του κουίζ σας.

320
00:16:50,512 --> 00:16:52,220
Αλλά ελπίζουμε όλοι
Τώρα μπορείτε να καταλάβετε

321
00:16:52,220 --> 00:16:57,800
γιατί αυτή η λύση ή αυτή
λειτουργία είναι ο τρόπος που είναι.

322
00:16:57,800 --> 00:16:59,840
Όποιος είναι λίγο ασαφές σχετικά με αυτό;

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
ΕΝΤΆΞΕΙ.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> Και έτσι τώρα, αν
ήθελε να dequeue, αυτό

327
00:17:09,970 --> 00:17:15,240
είναι όπου το κεφάλι μας θα είναι μετατόπιση
γιατί αν ήταν να dequeue,

328
00:17:15,240 --> 00:17:17,030
δεν παίρνουμε από το τέλος του q.

329
00:17:17,030 --> 00:17:19,130
Θέλουμε να απογειωθεί το κεφάλι, έτσι δεν είναι;

330
00:17:19,130 --> 00:17:24,260
Έτσι, ως αποτέλεσμα, το κεφάλι δεν πρόκειται να αλλάξει,
και αυτός είναι ο λόγος για τον οποίο, όταν Τοποθέτηση στην ουρά,

331
00:17:24,260 --> 00:17:26,800
έχετε να παρακολουθείτε
όπου το κεφάλι σας και το μέγεθός σας

332
00:17:26,800 --> 00:17:29,450
είναι να είναι σε θέση να εισάγει
στη σωστή θέση.

333
00:17:29,450 --> 00:17:32,740
>> Και έτσι όταν dequeue,
Μου ψευδοκώδικας επίσης.

334
00:17:32,740 --> 00:17:35,480
Μη διστάσετε να αν θέλετε
να επιχειρήσει κωδικοποίησης αυτό.

335
00:17:35,480 --> 00:17:36,980
Θέλετε να μετακινήσετε το κεφάλι, έτσι δεν είναι;

336
00:17:36,980 --> 00:17:39,320
Αν ήθελα να dequeue, Ι
θα κινηθεί το κεφάλι πάνω.

337
00:17:39,320 --> 00:17:40,800
Αυτό θα είναι το κεφάλι.

338
00:17:40,800 --> 00:17:45,617
>> Και τρέχον μέγεθος μας θα
αφαιρούμε γιατί δεν έχουμε πλέον

339
00:17:45,617 --> 00:17:46,950
έχουν τέσσερα στοιχεία στη συστοιχία.

340
00:17:46,950 --> 00:17:51,370
Έχουμε μόνο τρεις, και στη συνέχεια θέλουμε
να επιστρέψει ό, τι είχε αποθηκευτεί στο εσωτερικό

341
00:17:51,370 --> 00:17:56,260
του κεφαλιού, γιατί θέλουμε να το λάβουν αυτό
αξία έξω τόσο πολύ παρόμοια με τη στοίβα.

342
00:17:56,260 --> 00:17:58,010
Απλά παίρνετε
από μια διαφορετική θέση,

343
00:17:58,010 --> 00:18:01,770
και θα πρέπει να εκχωρήσετε εκ νέου δείκτη σας
σε διαφορετική θέση ως αποτέλεσμα.

344
00:18:01,770 --> 00:18:03,890
Λογικά, ο καθένας ακολουθεί;

345
00:18:03,890 --> 00:18:05,690
Εξαιρετική.

346
00:18:05,690 --> 00:18:10,156
>> Εντάξει, έτσι θα πάμε να μιλήσουμε λίγο
περισσότερο σε βάθος περίπου συνδεδεμένες λίστες

347
00:18:10,156 --> 00:18:13,280
γιατί θα είναι πολύ, πολύ πολύτιμη
για σας κατά τη διάρκεια αυτής της εβδομάδας

348
00:18:13,280 --> 00:18:14,964
psets.

349
00:18:14,964 --> 00:18:17,130
Συνδεδεμένες λίστες, όπως εσείς
μπορεί να θυμηθεί, όλα αυτά είναι

350
00:18:17,130 --> 00:18:22,570
είναι κόμβοι που είναι κόμβοι ορισμένων
τιμές τόσο της αξίας και ένα δείκτη

351
00:18:22,570 --> 00:18:26,290
τα οποία συνδέονται μεταξύ τους
οι εν λόγω δείκτες.

352
00:18:26,290 --> 00:18:29,880
Και έτσι η struct σχετικά με το πώς
δημιουργούμε ένας κόμβος εδώ είναι ότι

353
00:18:29,880 --> 00:18:33,569
έχουν int n, η οποία είναι ό, τι
η τιμή σε ένα κατάστημα ή σπάγκο n

354
00:18:33,569 --> 00:18:35,610
ή όπως αλλιώς θέλετε να
αποκαλούν, ο char αστέρι n.

355
00:18:35,610 --> 00:18:41,482
Struct αστέρι κόμβος, που είναι ο δείκτης
ότι θέλετε να έχετε σε κάθε κόμβο,

356
00:18:41,482 --> 00:18:43,690
θα πάμε να έχει αυτό
Σημείο δείκτη προς το επόμενο.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Θα έχετε το κεφάλι
από μία συνδεδεμένη λίστα που είναι

359
00:18:50,040 --> 00:18:53,140
πρόκειται να επισημαίνουν το υπόλοιπο της
οι τιμές ούτω καθεξής και ούτω καθεξής

360
00:18:53,140 --> 00:18:55,290
μέχρι να φθάσουν τελικά στο τέλος.

361
00:18:55,290 --> 00:18:58,040
Και αυτό το τελευταίο κόμβος είναι απλά
πρόκειται να μην έχουν ένα δείκτη.

362
00:18:58,040 --> 00:18:59,952
Είναι πρόκειται να επισημάνω
null, και ότι όταν

363
00:18:59,952 --> 00:19:01,910
ξέρετε ότι έχετε χτυπήσει το
τέλος συνδεδεμένη λίστα σας

364
00:19:01,910 --> 00:19:04,076
είναι όταν την τελευταία δείκτη σας
δεν δείχνουν τίποτα.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Έτσι θα πάμε για να πάει λίγο περισσότερο
βάθος σχετικά με το πώς κάποιος θα ήταν, ενδεχομένως

367
00:19:10,990 --> 00:19:12,400
αναζήτηση σε μια συνδεδεμένη λίστα.

368
00:19:12,400 --> 00:19:15,460
Θυμηθείτε τι είναι μερικά από τα
μειονεκτήματα των συνδεδεμένες λίστες

369
00:19:15,460 --> 00:19:19,340
στίχοι μια σειρά σχετικά με τις αναζητήσεις.

370
00:19:19,340 --> 00:19:22,565
Μια σειρά μπορείτε δυαδική αναζήτηση, αλλά
γιατί δεν μπορείτε να το κάνετε αυτό σε μια συνδεδεμένη λίστα;

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> Κοινό: Επειδή είστε όλοι συνδεδεμένοι,
αλλά δεν γνωρίζουμε ακριβώς πού

373
00:19:30,320 --> 00:19:31,330
[ΜΗ ΑΚΟΥΣΤΌΣ].

374
00:19:31,330 --> 00:19:34,600
>> ANDI PENG: Ναι, ακριβώς έτσι ώστε να θυμάστε
ότι η λαμπρότητα μιας συστοιχίας

375
00:19:34,600 --> 00:19:37,190
ήταν το γεγονός ότι είχαμε
μνήμη τυχαίας προσπέλασης όπου

376
00:19:37,190 --> 00:19:41,580
αν ήθελα την τιμή από το δείκτη
έξι, θα μπορούσα να πω δείκτης των έξι,

377
00:19:41,580 --> 00:19:42,407
να μου δώσει αυτή την τιμή.

378
00:19:42,407 --> 00:19:45,240
Και αυτό γιατί οι συστοιχίες ταξινομούνται
σε ένα συνεχόμενο χώρο της μνήμης

379
00:19:45,240 --> 00:19:48,020
σε ένα μέρος, ενώ
το είδος των συνδεδεμένων λιστών

380
00:19:48,020 --> 00:19:52,820
είναι τυχαία διάσπαρτα σε όλο,
και ο μόνος τρόπος μπορείτε να βρείτε ένα

381
00:19:52,820 --> 00:19:56,890
είναι μέσω ενός δείκτη που σας λέει
η διεύθυνση του, όπου αυτό είναι επόμενο κόμβο.

382
00:19:56,890 --> 00:20:00,290
>> Και έτσι, ως αποτέλεσμα, ο μόνος τρόπος
για να πραγματοποιήσετε αναζήτηση από μια συνδεδεμένη λίστα

383
00:20:00,290 --> 00:20:01,560
είναι γραμμική αναζήτηση.

384
00:20:01,560 --> 00:20:05,890
Επειδή εγώ δεν ξέρω ακριβώς πού
η 12η τιμή στην συνδεδεμένη λίστα είναι,

385
00:20:05,890 --> 00:20:08,780
Έχω να διασχίσει το σύνολο
του εν λόγω συνδεδεμένη λίστα ένα

386
00:20:08,780 --> 00:20:12,450
από ένα από την κεφαλή στον πρώτο κόμβο,
στον δεύτερο κόμβο, στον τρίτο κόμβο,

387
00:20:12,450 --> 00:20:17,690
σε όλη τη διαδρομή μέχρι που τελικά να πάρει
όπου ο κόμβος που ψάχνω είναι.

388
00:20:17,690 --> 00:20:22,110
Και έτσι με αυτή την έννοια, αναζήτηση
σε συνδεδεμένη λίστα είναι πάντα n.

389
00:20:22,110 --> 00:20:23,040
Είναι πάντα ν.

390
00:20:23,040 --> 00:20:25,690
Είναι πάντα σε γραμμικό χρόνο.

391
00:20:25,690 --> 00:20:28,470
>> Και έτσι ο κώδικας στην οποία
υλοποιούμε αυτό, και αυτό

392
00:20:28,470 --> 00:20:32,620
είναι λίγο νέα για σας παιδιά από τη στιγμή που
παιδιά δεν έχουν πραγματικά μιλήσει για ή ποτέ

393
00:20:32,620 --> 00:20:35,000
δει δείκτες στο πώς να
αναζήτηση μέσω δεικτών,

394
00:20:35,000 --> 00:20:37,670
έτσι θα καθοδηγήσει
αυτό το πολύ, πολύ αργά.

395
00:20:37,670 --> 00:20:40,200
Έτσι αναζήτηση bool, δεξιά,
ας φανταστούμε θέλουμε

396
00:20:40,200 --> 00:20:42,820
για να δημιουργήσετε μια λειτουργία που ονομάζεται
αναζήτησης που επιστρέφει true

397
00:20:42,820 --> 00:20:46,820
αν βρεθεί μια τιμή μέσα στη συνδεδεμένη
λίστα, και επιστρέφει false διαφορετικά.

398
00:20:46,820 --> 00:20:50,030
Λίστα αστέρων κόμβος
σήμερα μόνο ο δείκτης

399
00:20:50,030 --> 00:20:52,960
στο πρώτο στοιχείο που συνδέεται λίστα σας.

400
00:20:52,960 --> 00:20:56,700
int n είναι η τιμή που είστε
ψάχνουν για στον εν λόγω κατάλογο.

401
00:20:56,700 --> 00:20:58,770
>> Έτσι, ο δείκτης του κόμβου αστέρων ισούται λίστα.

402
00:20:58,770 --> 00:21:00,970
Αυτό σημαίνει ότι έχουμε αρχίσει τη
και τη δημιουργία ενός δείκτη

403
00:21:00,970 --> 00:21:03,592
στο εν λόγω πρώτο κόμβο εντός της λίστας.

404
00:21:03,592 --> 00:21:04,300
Όλοι μαζί μου;

405
00:21:04,300 --> 00:21:06,530
Έτσι, αν ήμασταν να πάμε
πίσω εδώ, θα είχα

406
00:21:06,530 --> 00:21:13,850
αρχικοποιείται ένα δείκτη που δείχνει προς
ο επικεφαλής του ό, τι ο εν λόγω κατάλογος.

407
00:21:13,850 --> 00:21:18,600
>> Και στη συνέχεια, μόλις φτάσετε εδώ κάτω,
ενώ ο δείκτης δεν είναι ίσο με null,

408
00:21:18,600 --> 00:21:22,160
έτσι ώστε ο βρόχος στον οποίο είμαστε
θα είναι στη συνέχεια διέρχονται

409
00:21:22,160 --> 00:21:25,940
το υπόλοιπο του καταλόγου μας, γιατί ό, τι
συμβαίνει όταν ο δείκτης ισούται με μηδενική;

410
00:21:25,940 --> 00:21:27,550
Ξέρουμε ότι have--

411
00:21:27,550 --> 00:21:28,450
>> Κοινό: [δεν ακούγεται]

412
00:21:28,450 --> 00:21:31,491
>> ANDI PENG: Ακριβώς, έτσι ξέρουμε ότι
έχουμε φτάσει στο τέλος της λίστας, σωστά;

413
00:21:31,491 --> 00:21:34,470
Αν πάτε πίσω εδώ, κάθε κόμβος
θα πρέπει να δείχνει σε έναν άλλο κόμβο

414
00:21:34,470 --> 00:21:36,550
Και ούτω καθεξής και ούτω καθεξής
μέχρι να χτυπήσει τελικά

415
00:21:36,550 --> 00:21:41,589
η ουρά της συνδεδεμένης λίστας σας,
το οποίο έχει ένα δείκτη που απλά

416
00:21:41,589 --> 00:21:43,130
δεν δείχνει οπουδήποτε αλλού εκτός από κανένα.

417
00:21:43,130 --> 00:21:47,510
Και έτσι ουσιαστικά γνωρίζουμε ότι
λίστα σας είναι ακόμα εκεί μέχρι

418
00:21:47,510 --> 00:21:50,900
μέχρι ο δείκτης δεν ισούται
null διότι τη στιγμή που ισούται με null,

419
00:21:50,900 --> 00:21:53,310
ξέρετε ότι δεν υπάρχει περισσότερο υλικό.

420
00:21:53,310 --> 00:21:56,930
>> Αυτή είναι λοιπόν η θηλιά στην οποία είμαστε
πρόκειται να έχουν την πραγματική αναζήτηση.

421
00:21:56,930 --> 00:22:01,690
Και αν οι pointer-- βλέπετε
ότι το είδος του βέλους λειτουργία εκεί;

422
00:22:01,690 --> 00:22:06,930
Έτσι, αν τα σημεία δείκτη προς n, αν
ο δείκτης ισούται με n ισούται με n,

423
00:22:06,930 --> 00:22:09,180
έτσι ώστε σημαίνει ότι αν
ο δείκτης που είστε

424
00:22:09,180 --> 00:22:13,420
ψάχνουν για για το τέλος του κάθε
κόμβος είναι πράγματι ίση με την αξία

425
00:22:13,420 --> 00:22:15,990
ψάχνετε, τότε
θέλετε να επιστρέψετε αλήθεια.

426
00:22:15,990 --> 00:22:19,280
Έτσι, βασικά, αν είστε σε ένα κόμβο που
έχει την τιμή που ψάχνετε,

427
00:22:19,280 --> 00:22:23,550
ξέρετε ότι έχετε πάει
τη δυνατότητα να αναζητήσει με επιτυχία.

428
00:22:23,550 --> 00:22:27,150
>> Σε αντίθετη περίπτωση, θέλετε να ορίσετε
το δείκτη στον επόμενο κόμβο.

429
00:22:27,150 --> 00:22:28,850
Αυτό είναι ό, τι η γραμμή εδώ κάνει.

430
00:22:28,850 --> 00:22:31,750
Ο δείκτης ισούται με το δείκτη του επόμενου.

431
00:22:31,750 --> 00:22:33,360
Όλοι δούμε πώς αυτό λειτουργεί;

432
00:22:33,360 --> 00:22:36,580
>> Και ουσιαστικά πρόκειται για απλά
διασχίζουν το σύνολο του καταλόγου,

433
00:22:36,580 --> 00:22:41,920
επαναφορά του δείκτη σας κάθε φορά μέχρι
μπορείτε τελικά να χτυπήσει το τέλος της λίστας.

434
00:22:41,920 --> 00:22:45,030
Και ξέρετε ότι δεν υπάρχουν
περισσότερους κόμβους να ψάξετε μέσα,

435
00:22:45,030 --> 00:22:47,999
και, στη συνέχεια, μπορείτε να επιστρέψετε ψευδής
επειδή ξέρετε ότι, OH, καλά,

436
00:22:47,999 --> 00:22:50,540
αν ήμουν σε θέση να αναζητήσετε
μέσω της σύνολό της λίστας.

437
00:22:50,540 --> 00:22:54,530
Αν σε αυτό το παράδειγμα, αν ήθελα
να ψάξουν για την αξία του 10,

438
00:22:54,530 --> 00:22:57,250
και αρχίζω στο κεφάλι, και
Ψάχνω σε όλη τη διαδρομή προς τα κάτω,

439
00:22:57,250 --> 00:23:00,550
και εγώ τελικά πήρε σε αυτό, το οποίο
ένας δείκτης που δείχνει προς null,

440
00:23:00,550 --> 00:23:04,415
Ξέρω ότι, χάλια, υποθέτω 10 δεν είναι σε
Αυτή η λίστα γιατί δεν μπορούσα να το βρω.

441
00:23:04,415 --> 00:23:06,520
Και είμαι στο τέλος της λίστας.

442
00:23:06,520 --> 00:23:11,040
Και σε αυτήν την περίπτωση μπορείτε να ξέρετε
Πάω να επιστρέψει false.

443
00:23:11,040 --> 00:23:12,900
>> Αφήστε που απορροφούν το για λίγο.

444
00:23:12,900 --> 00:23:17,350
Αυτό θα είναι αρκετά
σημαντικό για το chipset σας.

445
00:23:17,350 --> 00:23:21,140
Η λογική του είναι πολύ απλή, ίσως
συντακτικά ακριβώς την εφαρμογή της.

446
00:23:21,140 --> 00:23:23,365
Εσείς θέλετε να κάνετε
βεβαιωθείτε ότι έχετε κατανοήσει.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Δροσερός.

449
00:23:27,650 --> 00:23:32,560
>> Εντάξει, έτσι πώς θα είναι
εισαγωγή κόμβων, δεξιά,

450
00:23:32,560 --> 00:23:35,380
σε μια λίστα γιατί θυμάμαι
ποια είναι η τι των παροχών

451
00:23:35,380 --> 00:23:39,230
έχουν μια συνδεδεμένη λίστα έναντι
μια συστοιχία από την άποψη της αποθήκευσης;

452
00:23:39,230 --> 00:23:41,110
>> Κοινό: Είναι δυναμική,
έτσι είναι ευκολότερο to--

453
00:23:41,110 --> 00:23:43,180
>> ANDI PENG: Ακριβώς,
έτσι ώστε να είναι δυναμική, η οποία

454
00:23:43,180 --> 00:23:46,880
σημαίνει ότι μπορεί να επεκτείνει και να συρρικνωθεί
ανάλογα με τις ανάγκες του χρήστη.

455
00:23:46,880 --> 00:23:56,570
Και έτσι, με αυτή την έννοια, δεν χρειαζόμαστε
να σπαταλούν άσκοπα το χώρο αποθήκευσης, γιατί

456
00:23:56,570 --> 00:24:00,850
αν δεν ξέρω πόσες τιμές θέλω
για την αποθήκευση, δεν έχει νόημα για μένα

457
00:24:00,850 --> 00:24:04,310
για να δημιουργήσει μια σειρά, γιατί
αν θέλω να αποθηκεύσει 10 τιμές

458
00:24:04,310 --> 00:24:08,380
και μπορώ να δημιουργήσω μια σειρά από 1.000, που είναι
μια μεγάλη σπατάλη μνήμης, που έχουν εγκριθεί.

459
00:24:08,380 --> 00:24:11,180
Γι 'αυτό θέλουμε να χρησιμοποιήσουμε ένα συνδεδεμένο
κατάλογος να είναι σε θέση να δυναμικά

460
00:24:11,180 --> 00:24:13,860
αλλάξετε ή να συρρικνωθεί το μέγεθος μας.

461
00:24:13,860 --> 00:24:17,040
>> Και έτσι ώστε να κάνει την εισαγωγή
λίγο πιο περίπλοκη.

462
00:24:17,040 --> 00:24:20,810
Επειδή δεν μπορούμε να τυχαία πρόσβαση σε στοιχεία
ο τρόπος με τον οποίο θα ενός πίνακα.

463
00:24:20,810 --> 00:24:24,270
Αν θέλω να εισάγετε ένα στοιχείο
στην έβδομη δείκτη,

464
00:24:24,270 --> 00:24:26,930
Απλά εισέρχεται
μέσα έβδομη δείκτη.

465
00:24:26,930 --> 00:24:30,020
Σε μια συνδεδεμένη λίστα, δεν το κάνει
εργάζονται αρκετά εύκολα,

466
00:24:30,020 --> 00:24:34,947
και έτσι αν θέλαμε να εισάγετε
το ένα εδώ στην συνδεδεμένη λίστα,

467
00:24:34,947 --> 00:24:36,280
οπτικά, είναι πολύ εύκολο να δει κανείς.

468
00:24:36,280 --> 00:24:39,363
Εμείς απλά θέλουμε να το τοποθετήσετε εκεί,
ακριβώς στην αρχή της λίστας,

469
00:24:39,363 --> 00:24:40,840
αμέσως μετά το κεφάλι.

470
00:24:40,840 --> 00:24:44,579
>> Αλλά ο τρόπος με τον οποίο πρέπει να εκχωρήσετε εκ νέου
οι δείκτες είναι μπερδεμένη λίγο

471
00:24:44,579 --> 00:24:47,620
ή, λογικά, είναι λογικό, αλλά
θέλετε να βεβαιωθείτε ότι το έχετε

472
00:24:47,620 --> 00:24:50,250
τελείως προς τα κάτω, διότι
το τελευταίο πράγμα που θέλετε

473
00:24:50,250 --> 00:24:52,990
είναι να εκχωρήσετε εκ νέου έναν δείκτη ο
τρόπο που κάνουμε εδώ.

474
00:24:52,990 --> 00:24:58,170
Αν η dereference
δείκτη από το κεφάλι μέχρι τα 1,

475
00:24:58,170 --> 00:25:01,086
τότε ξαφνικά η
υπόλοιπη συνδεδεμένη λίστα σας

476
00:25:01,086 --> 00:25:04,680
χάνεται επειδή δεν έχετε στην πραγματικότητα
δημιούργησε ένα προσωρινό τίποτα.

477
00:25:04,680 --> 00:25:06,220
Αυτό επεσήμανε στο 2.

478
00:25:06,220 --> 00:25:10,080
Εάν εκχωρήσετε εκ νέου το δείκτη, τότε η
υπόλοιπο της λίστας σας είναι εντελώς χαθεί.

479
00:25:10,080 --> 00:25:13,310
Έτσι θέλετε να είναι
πολύ, πολύ προσεκτικοί εδώ

480
00:25:13,310 --> 00:25:17,010
να αναθέσει την πρώτη
δείκτη από ό, τι σας

481
00:25:17,010 --> 00:25:20,150
θέλετε να εισαγάγετε στο μέτρο του
θέλετε, και στη συνέχεια να

482
00:25:20,150 --> 00:25:22,710
μπορεί να dereference το υπόλοιπο της λίστας σας.

483
00:25:22,710 --> 00:25:25,250
>> Έτσι, αυτό ισχύει για οπουδήποτε
προσπαθείτε να εισαγάγετε στο.

484
00:25:25,250 --> 00:25:27,520
Αν θέλετε να εισάγετε κατά τη
το κεφάλι, αν θέλετε να απαντήσετε εδώ,

485
00:25:27,520 --> 00:25:29,455
αν θέλετε να εισάγετε στο
το τέλος, καλά, το τέλος θα

486
00:25:29,455 --> 00:25:30,910
Υποθέτω ότι θα κάνατε μόνο
δεν έχουν δείκτη, αλλά σας

487
00:25:30,910 --> 00:25:33,830
θέλετε να βεβαιωθείτε ότι δεν έχετε
χάνουν το υπόλοιπο της λίστας σας.

488
00:25:33,830 --> 00:25:36,640
Μπορείτε πάντα θέλετε να είστε σίγουροι
νέος κόμβος σας είναι στραμμένο

489
00:25:36,640 --> 00:25:39,330
προς ό, τι
θέλετε να εισαγάγετε στο,

490
00:25:39,330 --> 00:25:42,170
και, στη συνέχεια, μπορείτε να προσθέσετε το αλυσοποίηση καθεξής.

491
00:25:42,170 --> 00:25:43,330
Όλοι σαφής;

492
00:25:43,330 --> 00:25:45,427
>> Αυτό πρόκειται να είναι
ένα από τα πραγματικά ζητήματα.

493
00:25:45,427 --> 00:25:48,010
Ένα από τα πιο σημαντικά θέματα που
θα πάμε να έχει για το chipset σας

494
00:25:48,010 --> 00:25:51,340
είναι ότι θα πάμε για να προσπαθήσουμε να δημιουργήσουμε
μια συνδεδεμένη λίστα και συμπληρώστε τα πράγματα

495
00:25:51,340 --> 00:25:53,340
αλλά στη συνέχεια, μόλις χάσουν το
υπόλοιπο της συνδεδεμένης λίστας σας.

496
00:25:53,340 --> 00:25:54,900
Και θα πάμε να είναι όπως, εγώ
Δεν ξέρω γιατί συμβαίνει αυτό;

497
00:25:54,900 --> 00:25:58,040
Και είναι ένας πόνος να περάσει
και η αναζήτηση σε όλους τους δείκτες σας.

498
00:25:58,040 --> 00:26:02,100
>> Και σας εγγυώμαι σε αυτό το chipset,
γράφω και να σχεδιάζω αυτούς τους κόμβους έξω

499
00:26:02,100 --> 00:26:03,344
θα είναι πολύ, πολύ χρήσιμη.

500
00:26:03,344 --> 00:26:06,010
Έτσι, μπορείτε να κρατήσετε εντελώς παρακολουθείτε
πού είναι όλα δείκτες σας,

501
00:26:06,010 --> 00:26:08,540
τι πηγαίνει στραβά,
όπου όλοι οι κόμβοι σας,

502
00:26:08,540 --> 00:26:12,660
τι πρέπει να κάνετε για να αποκτήσετε πρόσβαση ή
εισάγετε ή να διαγράψετε ή σε οποιοδήποτε από αυτά.

503
00:26:12,660 --> 00:26:14,550
Όλοι καλό με αυτό;

504
00:26:14,550 --> 00:26:15,050
Δροσερός.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Έτσι, αν θέλουμε να δούμε τον κώδικα;

507
00:26:22,600 --> 00:26:24,470
Αχ, δεν ξέρω αν είμαστε
μπορείτε να δείτε the-- Εντάξει, έτσι

508
00:26:24,470 --> 00:26:27,940
στην κορυφή όλα είναι είναι μια συνάρτηση
ονομάστηκε ένθετο όπου θέλουμε

509
00:26:27,940 --> 00:26:31,365
για να εισάγετε int n στη συνδεδεμένη λίστα.

510
00:26:31,365 --> 00:26:32,740
Εμείς πάμε για να περπατήσει μέσα από αυτό.

511
00:26:32,740 --> 00:26:34,770
Είναι μια πολύ κώδικα, πολλά νέα σύνταξη.

512
00:26:34,770 --> 00:26:36,220
Θα είναι εντάξει.

513
00:26:36,220 --> 00:26:39,120
>> Έτσι, στην κορυφή, κάθε φορά που
θέλουμε να δημιουργήσουμε κάτι

514
00:26:39,120 --> 00:26:42,380
τι πρέπει να κάνουμε, ειδικά αν
θέλουν δεν πρέπει να αποθηκεύονται στη στοίβα

515
00:26:42,380 --> 00:26:43,920
αλλά στο σωρό;

516
00:26:43,920 --> 00:26:45,460
Εμείς πάμε για ένα malloc, σωστά;

517
00:26:45,460 --> 00:26:48,240
Έτσι θα πάμε να δημιουργήσουμε ένα δείκτη.

518
00:26:48,240 --> 00:26:52,074
Κόμβος, δείκτης, νέα ίσων
malloc το μέγεθος ενός κόμβου

519
00:26:52,074 --> 00:26:53,740
γιατί θέλουμε αυτός ο κόμβος που θα δημιουργηθεί.

520
00:26:53,740 --> 00:26:56,720
Θέλουμε το ποσό των
μνήμης που ένας κόμβος καταλαμβάνει

521
00:26:56,720 --> 00:26:59,300
πρέπει να έχει ορισθεί για την
δημιουργία του νέου κόμβου.

522
00:26:59,300 --> 00:27:02,270
>> Και μετά θα πάμε για να ελέγξετε για να
δείτε αν νέο ίσων ισούται με μηδενική.

523
00:27:02,270 --> 00:27:03,370
Θυμηθείτε τι είπαμε;

524
00:27:03,370 --> 00:27:06,470
Ό, τι malloc,
τι πρέπει να κάνετε πάντα;

525
00:27:06,470 --> 00:27:09,490
Θα πρέπει πάντοτε να ελέγχετε
έστω και αν αυτή είναι άκυρη.

526
00:27:09,490 --> 00:27:13,620
>> Για παράδειγμα, εάν το λειτουργικό σας
σύστημα ήταν εντελώς γεμάτο,

527
00:27:13,620 --> 00:27:17,060
αν δεν είχε περισσότερη μνήμη σε
όλα και προσπαθείς να malloc,

528
00:27:17,060 --> 00:27:18,410
θα επιστρέψει null για εσάς.

529
00:27:18,410 --> 00:27:21,094
Και έτσι αν προσπαθήσετε να το χρησιμοποιήσετε
όταν έδειχνε σε null,

530
00:27:21,094 --> 00:27:23,260
εσείς δεν πρόκειται να είναι σε θέση
να έχουν πρόσβαση σε αυτές τις πληροφορίες.

531
00:27:23,260 --> 00:27:27,010
Και έτσι ως εκ τούτου, θα θέλαμε να κάνουμε
βεβαιωθείτε ότι κάθε φορά που είστε mallocing,

532
00:27:27,010 --> 00:27:30,500
είστε πάντα τον έλεγχο για να δούμε αν
ότι η μνήμη που σας δίνονται είναι μηδενική.

533
00:27:30,500 --> 00:27:33,670
Και αν δεν είναι, τότε μπορούμε να προχωρήσουμε
σχετικά με το υπόλοιπο του κώδικά μας.

534
00:27:33,670 --> 00:27:36,140
>> Έτσι θα πάμε να
προετοιμάσει το νέο κόμβο.

535
00:27:36,140 --> 00:27:39,050
Εμείς πάμε να κάνουμε νέες n ισούται με n.

536
00:27:39,050 --> 00:27:42,390
Και μετά θα πάμε να κάνουμε
θέτουν νέα του δείκτη στο νέο

537
00:27:42,390 --> 00:27:46,900
με μηδενική διότι αυτή τη στιγμή δεν το κάνουμε
θέλω τίποτα γι 'αυτό να επισημάνω.

538
00:27:46,900 --> 00:27:48,755
Δεν έχουμε καμία ιδέα για το πού
πρόκειται να σας βάλει,

539
00:27:48,755 --> 00:27:50,630
και στη συνέχεια, αν θέλουμε να
τοποθετήστε το στο κεφάλι,

540
00:27:50,630 --> 00:27:53,820
τότε μπορούμε να επανεκχώρηση
ο δείκτης στο κεφάλι.

541
00:27:53,820 --> 00:27:58,530
Μήπως ο καθένας ακολουθεί τη λογική
όπου αυτό συμβαίνει;

542
00:27:58,530 --> 00:28:02,502
>> Το μόνο που κάνουμε είναι η δημιουργία ενός νέου
κόμβο, τον καθορισμό του δείκτη σε null,

543
00:28:02,502 --> 00:28:04,210
και, στη συνέχεια, η ανακατανομή
να το κεφάλι αν

544
00:28:04,210 --> 00:28:06,320
Γνωρίζουμε ότι θέλετε να το τοποθετήσετε στο κεφάλι.

545
00:28:06,320 --> 00:28:09,420
Και τότε η κεφαλή πρόκειται να
σημείο προς αυτό το νέο κόμβο.

546
00:28:09,420 --> 00:28:11,060
Όλοι εντάξει με αυτό;

547
00:28:11,060 --> 00:28:12,380
>> Γι 'αυτό είναι μια διαδικασία δύο σταδίων.

548
00:28:12,380 --> 00:28:14,760
Έχετε να εκχωρήσει πρώτα
ό, τι δημιουργείτε.

549
00:28:14,760 --> 00:28:18,260
Ορίστε αυτό το δείκτη για το
αναφοράς, και στη συνέχεια θα

550
00:28:18,260 --> 00:28:21,400
να το είδος της dereference
ο πρώτος δείκτης

551
00:28:21,400 --> 00:28:22,972
και κατευθύνεται προς το νέο κόμβο.

552
00:28:22,972 --> 00:28:25,680
Όπου κι αν θέλετε να το τοποθετήσετε,
ότι η λογική θα ισχύει.

553
00:28:25,680 --> 00:28:27,530
>> Είναι κάτι σαν την ανάθεση
προσωρινές μεταβλητές.

554
00:28:27,530 --> 00:28:28,700
Θυμηθείτε, έχετε
για να βεβαιωθείτε ότι έχετε

555
00:28:28,700 --> 00:28:30,346
Δεν χαθούν τα ίχνη του, αν είστε εναλλαγή.

556
00:28:30,346 --> 00:28:33,470
Θέλετε να βεβαιωθείτε ότι έχετε ένα
προσωρινή μεταβλητή που κρατά το είδος του

557
00:28:33,470 --> 00:28:35,620
παρακολουθείτε όπου αυτό το πράγμα
αποθηκεύονται έτσι ώστε να

558
00:28:35,620 --> 00:28:41,190
δεν χάνουν καμία αξία κατά τη διάρκεια
σαν Messing περίπου με αυτό.

559
00:28:41,190 --> 00:28:42,710
>> Εντάξει, έτσι κωδικός θα είναι εδώ.

560
00:28:42,710 --> 00:28:45,020
Εσείς ρίξτε μια ματιά μετά το τμήμα.

561
00:28:45,020 --> 00:28:48,060
Θα είναι εκεί.

562
00:28:48,060 --> 00:28:50,280
>> Έτσι υποθέτω πώς
Αυτό διαφέρει αν θέλαμε

563
00:28:50,280 --> 00:28:52,300
για να εισαγάγετε στη μέση ή στο τέλος;

564
00:28:52,300 --> 00:28:57,892
Υπάρχει κάποιος που έχει μια ιδέα για το ποια είναι η
pseudocode ως το λογικό αναφορά

565
00:28:57,892 --> 00:29:00,350
ότι θα μπορέσουμε να κάνουμε αν θέλουμε
να το τοποθετήσετε στη μέση;

566
00:29:00,350 --> 00:29:03,391
Έτσι, αν θέλαμε να το εισάγετε κατά τη
το κεφάλι, το μόνο που κάνουμε είναι να δημιουργήσουμε ένα νέο κόμβο.

567
00:29:03,391 --> 00:29:06,311
Θέτουμε το δείκτη του ότι
νέο κόμβο σε ό, τι το κεφάλι,

568
00:29:06,311 --> 00:29:08,310
και, στη συνέχεια, θέσαμε το κεφάλι
στο νέο κόμβο, έτσι δεν είναι;

569
00:29:08,310 --> 00:29:11,560
Αν θέλαμε να το τοποθετήσετε στη μέση
του καταλόγου, τι θα πρέπει να κάνουμε;

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> Κοινό: Θα ήταν ακόμα
είναι μια παρόμοια διαδικασία

572
00:29:16,110 --> 00:29:19,114
σαν την ανάθεση δείκτη και
Στη συνέχεια την ανάθεση αυτού του pointer,

573
00:29:19,114 --> 00:29:20,530
αλλά θα πρέπει να εντοπίσετε εκεί.

574
00:29:20,530 --> 00:29:23,560
>> ANDI PENG: Ακριβώς, έτσι ακριβώς
η ίδια διαδικασία, εκτός από εσάς

575
00:29:23,560 --> 00:29:27,820
πρέπει να εντοπίσετε πού ακριβώς σας
θέλουν το νέο δείκτη για να πάει σε,

576
00:29:27,820 --> 00:29:44,790
οπότε αν θέλετε να εισάγετε στο
η μέση συνδέονται list-- ΟΚ,

577
00:29:44,790 --> 00:29:46,370
Ας πούμε ότι είναι συνδεδεμένη λίστα μας.

578
00:29:46,370 --> 00:29:49,500
Αν θέλουμε να το τοποθετήσετε ακριβώς εδώ,
θα πάμε για να δημιουργήσετε ένα νέο κόμβο.

579
00:29:49,500 --> 00:29:50,520
Εμείς πάμε για να malloc.

580
00:29:50,520 --> 00:29:52,220
Εμείς πάμε για να δημιουργήσετε ένα νέο κόμβο.

581
00:29:52,220 --> 00:29:55,940
Εμείς πάμε για να ορίσετε το
δείκτη του κόμβου εδώ.

582
00:29:55,940 --> 00:29:58,335
>> Αλλά το πρόβλημα που διαφέρει
από όπου το κεφάλι είναι

583
00:29:58,335 --> 00:30:00,490
είναι ότι γνωρίζαμε ακριβώς
όπου το κεφάλι είναι.

584
00:30:00,490 --> 00:30:01,930
Ήταν ακριβώς στην πρώτη, έτσι δεν είναι;

585
00:30:01,930 --> 00:30:04,870
Αλλά εδώ έχουμε να παρακολουθείτε
όπου είμαστε το τοποθετείτε σε.

586
00:30:04,870 --> 00:30:07,930
Αν τοποθετείτε μας
κόμβος εδώ, έχουμε

587
00:30:07,930 --> 00:30:12,270
για να βεβαιωθείτε ότι ο
μια προηγούμενη προς αυτόν τον κόμβο

588
00:30:12,270 --> 00:30:14,172
είναι αυτό που εκχωρεί εκ νέου τον δείκτη.

589
00:30:14,172 --> 00:30:16,380
Έτσι, τότε θα πρέπει να το είδος του
να παρακολουθείτε δύο πράγματα.

590
00:30:16,380 --> 00:30:19,420
Αν παρακολουθείτε όπου αυτό
κόμβου επί του παρόντος είναι η εισαγωγή σε.

591
00:30:19,420 --> 00:30:23,280
Μπορείτε επίσης να παρακολουθείτε όπου
το προηγούμενο κόμβο που κοιτάτε

592
00:30:23,280 --> 00:30:24,340
ήταν επίσης εκεί.

593
00:30:24,340 --> 00:30:25,830
Όλοι καλό με αυτό;

594
00:30:25,830 --> 00:30:26,500
ΕΝΤΆΞΕΙ.

595
00:30:26,500 --> 00:30:28,000
>> Τι θα λέγατε για εισαγωγή στο τέλος;

596
00:30:28,000 --> 00:30:34,220
Αν ήθελα να το προσθέσετε here-- αν ήθελα
να προσθέσετε ένα νέο κόμβο στο τέλος του καταλόγου,

597
00:30:34,220 --> 00:30:37,009
Πως θα πάτε για να κάνει αυτό;

598
00:30:37,009 --> 00:30:39,300
Κοινό: Έτσι σήμερα, η
επισήμανε τελευταίο να null.

599
00:30:39,300 --> 00:30:40,960
ANDI PENG: Ναι.

600
00:30:40,960 --> 00:30:43,560
Ακριβώς, οπότε αυτό
σήμερα είναι στραμμένο προς γνωρίζετε,

601
00:30:43,560 --> 00:30:46,720
και έτσι υποθέτω, με αυτή την έννοια, είναι
πολύ εύκολο να προσθέσετε στο τέλος της λίστας.

602
00:30:46,720 --> 00:30:51,810
Το μόνο που έχετε να κάνετε είναι να το ρυθμίσετε
ίσο με null και, στη συνέχεια, με γρήγορους ρυθμούς.

603
00:30:51,810 --> 00:30:53,070
Ακριβώς εκεί, είναι πολύ εύκολο.

604
00:30:53,070 --> 00:30:53,960
Πολυ απλα.

605
00:30:53,960 --> 00:30:56,430
>> Πολύ παρόμοια με το
το κεφάλι, αλλά λογικά θα

606
00:30:56,430 --> 00:30:59,690
θέλετε να βεβαιωθείτε ότι τα βήματα
παίρνετε προς να κάνει οποιαδήποτε από αυτό,

607
00:30:59,690 --> 00:31:01,500
είστε μετά μαζί.

608
00:31:01,500 --> 00:31:04,420
Είναι πολύ εύκολο να, στη μέση
του κωδικού σας, να εμπλακούμε σε,

609
00:31:04,420 --> 00:31:05,671
Ω, έχω τόσες πολλές κατευθύνσεις.

610
00:31:05,671 --> 00:31:07,461
Δεν ξέρω πού
κάτι που δείχνει να.

611
00:31:07,461 --> 00:31:09,170
Εγώ δεν ξέρω καν ποια κόμβο είμαι.

612
00:31:09,170 --> 00:31:11,490
Τι συμβαίνει?

613
00:31:11,490 --> 00:31:13,620
>> Χαλαρώστε, ηρέμησε, πάρτε μια βαθιά ανάσα.

614
00:31:13,620 --> 00:31:15,530
Ισοπαλία έξω συνδεδεμένη λίστα σας.

615
00:31:15,530 --> 00:31:18,800
Εάν λέτε, ξέρω πού ακριβώς
Πρέπει να εισάγετε αυτό σε

616
00:31:18,800 --> 00:31:22,970
και ξέρω ακριβώς πώς να επανεκχώρηση μου
δείκτες, πολύ, πολύ πιο εύκολο να φανταστείτε

617
00:31:22,970 --> 00:31:27,200
out-- πολύ, πολύ εύκολο να μην
χαθείτε στα σφάλματα του κώδικα σας.

618
00:31:27,200 --> 00:31:29,410
Όλοι εντάξει με αυτό;

619
00:31:29,410 --> 00:31:31,380
ΕΝΤΆΞΕΙ.

620
00:31:31,380 --> 00:31:35,120
>> Έτσι υποθέτω ότι μια έννοια που δεν έχουμε
πραγματικά μίλησε πριν από τώρα,

621
00:31:35,120 --> 00:31:38,131
και έχω να μαντέψετε πιθανότατα
δεν θα αντιμετωπίσετε πολύ yet--

622
00:31:38,131 --> 00:31:40,880
αυτό είναι το είδος της προηγμένης concept--
είναι ότι θα έχουμε πράγματι μια δεδομένων

623
00:31:40,880 --> 00:31:43,900
δομή που ονομάζεται διπλά συνδεδεμένη λίστα.

624
00:31:43,900 --> 00:31:46,390
Έτσι, όπως μπορείτε να δείτε τα παιδιά,
το μόνο που κάνουμε είναι η δημιουργία

625
00:31:46,390 --> 00:31:50,400
μια πραγματική τιμή, ένα επιπλέον
δείκτη για κάθε ένα από τους κόμβους μας

626
00:31:50,400 --> 00:31:52,660
ότι επισημαίνει επίσης στο προηγούμενο κόμβο.

627
00:31:52,660 --> 00:31:58,170
Έτσι, όχι μόνο δεν έχουμε μας
κόμβοι επισημαίνουν το επόμενο.

628
00:31:58,170 --> 00:32:01,430
Επισημαίνουν επίσης με την προηγούμενη.

629
00:32:01,430 --> 00:32:04,310
Πάω να αγνοήσει αυτά τα δύο τώρα.

630
00:32:04,310 --> 00:32:06,740
>> Έτσι, τότε έχετε μια αλυσίδα
ότι μπορεί να κινηθεί και τους δύο τρόπους,

631
00:32:06,740 --> 00:32:09,630
και στη συνέχεια είναι λίγο πιο εύκολη
σε λογικά ακολουθήσει μαζί.

632
00:32:09,630 --> 00:32:11,896
Όπως εδώ, αντί του
την παρακολούθηση της, OH,

633
00:32:11,896 --> 00:32:14,520
Πρέπει να ξέρετε ότι αυτός ο κόμβος είναι
αυτό που έχω να εκχωρήσετε εκ νέου,

634
00:32:14,520 --> 00:32:17,532
Δεν μπορώ ακριβώς να πάτε εδώ και να
απλά τραβήξτε το προηγούμενο.

635
00:32:17,532 --> 00:32:19,490
Στη συνέχεια, ξέρω ακριβώς πού
ότι είναι, και τότε

636
00:32:19,490 --> 00:32:21,130
Δεν χρειάζεται να διασχίσει το
σύνολό της συνδεδεμένης λίστας.

637
00:32:21,130 --> 00:32:22,180
Είναι λίγο πιο εύκολη.

638
00:32:22,180 --> 00:32:24,960
>> Αλλά ως τέτοια, έχετε διπλά
η ποσότητα των δεικτών,

639
00:32:24,960 --> 00:32:26,960
αυτό είναι διπλάσιο από το ποσό της μνήμης.

640
00:32:26,960 --> 00:32:28,950
Είναι μια πολύ δείκτες για την παρακολούθηση της.

641
00:32:28,950 --> 00:32:32,140
Είναι λίγο πιο περίπλοκη, αλλά είναι
λίγο πιο φιλική προς το χρήστη, ανάλογα

642
00:32:32,140 --> 00:32:34,080
σχετικά με το τι προσπαθείτε να πετύχετε.

643
00:32:34,080 --> 00:32:36,910
>> Έτσι, αυτό το είδος των δεδομένων
δομή υπάρχει εντελώς,

644
00:32:36,910 --> 00:32:40,280
και η δομή είναι πολύ, πολύ
απλό, εκτός από όλα είστε έχοντας είναι,

645
00:32:40,280 --> 00:32:43,850
αντί απλώς ένα δείκτη στο επόμενο,
έχετε επίσης ένα δείκτη σε προηγούμενη.

646
00:32:43,850 --> 00:32:45,940
Αυτή είναι όλη η διαφορά ήταν.

647
00:32:45,940 --> 00:32:47,740
Όλοι καλό με αυτό;

648
00:32:47,740 --> 00:32:48,240
Δροσερός.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Εντάξει, έτσι τώρα είμαι
πραγματικά να περάσετε πιθανώς

651
00:32:53,280 --> 00:32:56,870
σαν 15 να 20 λεπτά ή το μεγαλύτερο μέρος
του υπόλοιπου χρόνου σε τμήμα

652
00:32:56,870 --> 00:32:58,360
μιλάμε για πίνακες κατακερματισμού.

653
00:32:58,360 --> 00:33:02,590
Πόσοι από σας παιδιά
έχουν διαβάσει pset5 spec;

654
00:33:02,590 --> 00:33:03,620
Εντάξει, καλά.

655
00:33:03,620 --> 00:33:06,160
Αυτό είναι υψηλότερο από το 50% των κανονικά.

656
00:33:06,160 --> 00:33:07,560
Είναι εντάξει.

657
00:33:07,560 --> 00:33:10,345
>> Έτσι όπως εσείς θα δείτε,
είστε πρόκληση pset5

658
00:33:10,345 --> 00:33:16,790
θα είναι να εφαρμόσει ένα λεξικό
όπου μπορείτε να φορτώσετε πάνω από 140.000 λέξεις

659
00:33:16,790 --> 00:33:20,610
ότι θα σας δώσει και ο ορθογραφικός έλεγχος
ενάντια σε όλο το κείμενο.

660
00:33:20,610 --> 00:33:22,580
Θα σας δώσουμε τυχαία
κομμάτια της λογοτεχνίας.

661
00:33:22,580 --> 00:33:23,520
Θα σας δώσει την Οδύσσεια.

662
00:33:23,520 --> 00:33:24,561
Θα σας δώσει την Ιλιάδα.

663
00:33:24,561 --> 00:33:26,350
Θα σας δώσω Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> Και η πρόκλησή σας
θα πρέπει να είναι ο ορθογραφικός έλεγχος

665
00:33:28,220 --> 00:33:31,760
κάθε λέξη σε όλες τις
αυτών των λεξικών

666
00:33:31,760 --> 00:33:34,960
ουσιαστικά με ορθογράφο μας.

667
00:33:34,960 --> 00:33:38,620
Και έτσι υπάρχουν μερικά μέρη
της δημιουργίας αυτού το chipset,

668
00:33:38,620 --> 00:33:41,970
πρώτη θέλετε να
είναι σε θέση να φορτώσει στην πραγματικότητα

669
00:33:41,970 --> 00:33:43,970
όλες οι λέξεις σε σας
λεξικό, και στη συνέχεια θα

670
00:33:43,970 --> 00:33:45,530
θέλουν να είναι σε θέση να
ορθογραφικό έλεγχο όλα αυτά.

671
00:33:45,530 --> 00:33:48,780
Και έτσι ως τέτοια, θα πάμε να απαιτήσει
μια δομή δεδομένων που μπορεί να κάνει αυτό το γρήγορο

672
00:33:48,780 --> 00:33:50,790
και αποτελεσματικά και δυναμικά.

673
00:33:50,790 --> 00:33:52,900
>> Έτσι υποθέτω ότι ο ευκολότερος
τρόπος για να το κάνετε αυτό,

674
00:33:52,900 --> 00:33:55,010
θα δημιουργήσει πιθανώς μια σειρά, έτσι δεν είναι;

675
00:33:55,010 --> 00:33:58,910
Ο ευκολότερος τρόπος αποθήκευσης είναι εσείς
μπορεί να δημιουργήσει μια σειρά από 140,000 λέξεις

676
00:33:58,910 --> 00:34:03,400
και απλά τοποθετήστε τους όλους εκεί και
στη συνέχεια να τα διασχίζουν με δυαδική αναζήτηση

677
00:34:03,400 --> 00:34:06,780
ή από τις επιλογές ή not--
λυπηρό το γεγονός ότι διαλογής.

678
00:34:06,780 --> 00:34:10,729
Μπορείτε να τα ταξινομήσετε και στη συνέχεια να διασχίσει τους
μέσω της δυαδικής αναζήτησης ή απλά γραμμική αναζήτηση

679
00:34:10,729 --> 00:34:13,730
και μόνο τελικό οι λέξεις, αλλά ότι
παίρνει ένα τεράστιο ποσό της μνήμης,

680
00:34:13,730 --> 00:34:15,190
και δεν είναι πολύ αποτελεσματική.

681
00:34:15,190 --> 00:34:18,350
>> Και έτσι θα πάμε για να ξεκινήσετε
μιλάμε για τρόπους για να κάνει

682
00:34:18,350 --> 00:34:20,110
χρόνου λειτουργίας μας πιο αποτελεσματική.

683
00:34:20,110 --> 00:34:23,190
Και στόχος μας είναι να πάρει
σταθερά χρόνου όπου

684
00:34:23,190 --> 00:34:25,810
Είναι σχεδόν σαν πίνακες, όπου
έχετε στιγμιαία πρόσβαση.

685
00:34:25,810 --> 00:34:28,560
Αν ήθελα να αναζητήσετε οτιδήποτε,
Θέλω να είναι σε θέση να απλά,

686
00:34:28,560 --> 00:34:30,810
έκρηξη, να το βρείτε ακριβώς, και τραβήξτε την έξω.

687
00:34:30,810 --> 00:34:34,100
Και έτσι μια δομή στην οποία
θα πρέπει να γίνει πολύ κοντά

688
00:34:34,100 --> 00:34:37,569
να είναι σε θέση να έχουν πρόσβαση σε σταθερή
ώρα, αυτό το ιερό δισκοπότηρο

689
00:34:37,569 --> 00:34:41,370
στον προγραμματισμό της συνεχούς
στιγμή ονομάζεται hash πίνακα.

690
00:34:41,370 --> 00:34:45,370
Και έτσι ο David αναφέρθηκε προηγουμένως η
[Δεν ακούγεται] λίγο σε διάλεξη,

691
00:34:45,370 --> 00:34:49,100
αλλά θα πάμε να πραγματικά
βουτιά σε βαθιά αυτή την εβδομάδα

692
00:34:49,100 --> 00:34:51,780
σε ένα κομμάτι που είναι σχετικά
πώς ένα πίνακα κατακερματισμού λειτουργεί.

693
00:34:51,780 --> 00:34:53,949
>> Έτσι, με τον τρόπο αυτό ένα hash
τραπέζι έργα, για παράδειγμα,

694
00:34:53,949 --> 00:35:00,230
αν ήθελα να αποθηκεύσετε ένα σωρό λόγια,
μάτσο λέξεις στην αγγλική γλώσσα,

695
00:35:00,230 --> 00:35:02,940
Θα μπορούσε θεωρητικά να θέσει
μπανάνα, μήλο, ακτινίδιο, μάνγκο, ζεύγος,

696
00:35:02,940 --> 00:35:04,980
και πεπόνι όλα σε μόλις μια σειρά.

697
00:35:04,980 --> 00:35:07,044
Θα μπορούσαν όλα ταιριάξει και να βρουν.

698
00:35:07,044 --> 00:35:09,210
Θα ήθελα να είναι το είδος του πόνου σε
αναζήτηση μέσω και της πρόσβασης,

699
00:35:09,210 --> 00:35:12,920
αλλά ο ευκολότερος τρόπος να γίνει αυτό είναι
ότι μπορούμε να δημιουργήσουμε πραγματικά μια δομή

700
00:35:12,920 --> 00:35:15,680
ονομάζεται πίνακας κατακερματισμού όπου hash.

701
00:35:15,680 --> 00:35:19,880
Τρέχουμε όλοι μας μέσα από τα πλήκτρα
μια συνάρτηση κατακερματισμού, μια εξίσωση,

702
00:35:19,880 --> 00:35:22,600
ότι όλα αυτά μετατρέπεται σε
κάποιο είδος αξίας

703
00:35:22,600 --> 00:35:28,740
ότι τότε μπορούμε να αποθηκεύσουμε πάνω
ουσιαστικά μια σειρά από συνδεδεμένη λίστα.

704
00:35:28,740 --> 00:35:32,570
>> Και έτσι εδώ, αν θέλαμε
για την αποθήκευση αγγλικές λέξεις,

705
00:35:32,570 --> 00:35:37,250
θα μπορούσαμε δυνητικά απλά, δεν το κάνω
Ξέρετε, γυρίστε όλα τα πρώτα γράμματα

706
00:35:37,250 --> 00:35:39,630
σε κάποιο είδος ενός αριθμού.

707
00:35:39,630 --> 00:35:43,140
Και έτσι, για παράδειγμα, αν ήθελα
Μια ότι είναι συνώνυμη με apple--

708
00:35:43,140 --> 00:35:47,460
ή με το δείκτη 0, και
Β να είναι συνώνυμη με 1,

709
00:35:47,460 --> 00:35:51,030
μπορούμε να έχουμε 26 μεταφράσεις
που μπορεί να αποθηκεύσει μόνο

710
00:35:51,030 --> 00:35:53,610
όλα τα γράμματα της
αλφάβητο που θα αρχίσει με.

711
00:35:53,610 --> 00:35:56,130
Και τότε μπορούμε να έχουμε
μήλο στο δείκτη 0.

712
00:35:56,130 --> 00:35:59,160
Μπορούμε να έχουμε μπανάνα στο δείκτη
1, το πεπόνι στο δείκτη 2,

713
00:35:59,160 --> 00:36:00,540
Και ούτω καθεξής και ούτω καθεξής.

714
00:36:00,540 --> 00:36:04,460
Και έτσι αν ήθελα να αναζητήσετε
κατακερματισμού μου τραπέζι και πρόσβαση μήλο,

715
00:36:04,460 --> 00:36:07,560
Ξέρω μήλο ξεκινά με
Α, και ξέρω ακριβώς

716
00:36:07,560 --> 00:36:10,860
ότι πρέπει να είναι και ο hash
πίνακα στο δείκτη 0, διότι

717
00:36:10,860 --> 00:36:13,620
της λειτουργίας που έχει ανατεθεί.

718
00:36:13,620 --> 00:36:16,572
>> Έτσι, δεν ξέρω, είμαστε
ένα πρόγραμμα χρήστη, όπου

719
00:36:16,572 --> 00:36:18,780
θα χρεωθείτε με
Δεν arbitrarily-- αυθαίρετα,

720
00:36:18,780 --> 00:36:22,530
με την προσπάθεια να σκεπτικά
σκεφτείτε καλά εξισώσεων

721
00:36:22,530 --> 00:36:25,460
να είναι σε θέση να εξαπλωθεί
από το σύνολο των αξιών σας

722
00:36:25,460 --> 00:36:29,370
κατά τρόπο που να μπορούν εύκολα να έχουν πρόσβαση
αυτό αργότερα με σαν μια εξίσωση

723
00:36:29,370 --> 00:36:31,130
ότι εσείς οι ίδιοι, ξέρετε.

724
00:36:31,130 --> 00:36:35,210
Έτσι, με την έννοια αν ήθελα να πάω να
μάνγκο, το ξέρω, OH, ξεκινά με το m.

725
00:36:35,210 --> 00:36:37,134
Πρέπει να είναι στο δείκτη 12.

726
00:36:37,134 --> 00:36:38,800
Δεν χρειάζεται να ψάξει μέσω τίποτα.

727
00:36:38,800 --> 00:36:42,080
Ξέρω exactly-- θα μπορούσα απλά πηγαίνετε στο
ο δείκτης των 12 και τραβήξτε ότι έξω.

728
00:36:42,080 --> 00:36:45,520
>> Όλοι σαφής σχετικά με το πώς μια
συνάρτηση hash πίνακα δουλεύει;

729
00:36:45,520 --> 00:36:48,380
Είναι το είδος του απλά μια πιο περίπλοκη σειρά.

730
00:36:48,380 --> 00:36:50,010
Αυτό είναι όλο αυτό είναι.

731
00:36:50,010 --> 00:36:51,630
ΕΝΤΆΞΕΙ.

732
00:36:51,630 --> 00:36:57,690
>> Έτσι υποθέτω ότι θα τρέξει σε
Αυτό το ζήτημα του τι

733
00:36:57,690 --> 00:37:06,390
θα συμβεί αν έχετε πολλά πράγματα
ότι θα δώσει τον ίδιο δείκτη;

734
00:37:06,390 --> 00:37:10,570
Έτσι λένε λειτουργία μας, το μόνο που
έκανε ήταν να πάρουμε το πρώτο γράμμα

735
00:37:10,570 --> 00:37:14,490
και να μετατρέψει αυτό σε μια
αντίστοιχες 0 έως 25 δείκτη.

736
00:37:14,490 --> 00:37:17,137
Αυτό είναι εντελώς καλά, αν
έχετε μόνο ένα από το καθένα.

737
00:37:17,137 --> 00:37:18,970
Αλλά το δεύτερο ξεκινήσετε
που έχουν περισσότερα, είστε

738
00:37:18,970 --> 00:37:20,910
πρόκειται να έχουν αυτό που λέμε μια σύγκρουση.

739
00:37:20,910 --> 00:37:25,580
>> Έτσι, αν προσπαθώ να εισάγετε θάψουν σε ένα hash
πίνακα που έχει ήδη μπανάνα σε αυτό,

740
00:37:25,580 --> 00:37:27,870
τι πρόκειται να συμβεί όταν
να προσπαθήσετε να τοποθετήσετε αυτό;

741
00:37:27,870 --> 00:37:30,930
Άσχημα τα πράγματα γιατί μπανάνας
υπάρχει ήδη εντός του δείκτη

742
00:37:30,930 --> 00:37:33,800
ότι θέλετε να το αποθηκεύσετε σε.

743
00:37:33,800 --> 00:37:35,560
Berry είδος είναι σαν, αχ, τι μπορώ να κάνω;

744
00:37:35,560 --> 00:37:37,080
Δεν ξέρω πού να πάω.

745
00:37:37,080 --> 00:37:38,410
Πώς μπορώ να επιλύσω αυτό;

746
00:37:38,410 --> 00:37:41,150
>> Και έτσι εσείς θα το είδος του
δείτε το κάνουμε αυτό το δύσκολο πράγμα

747
00:37:41,150 --> 00:37:44,810
όπου μπορούμε πραγματικά το είδος του
δημιουργήσετε συνδεδεμένη λίστα σε συστοιχίες μας.

748
00:37:44,810 --> 00:37:46,840
Και έτσι ο ευκολότερος τρόπος
να το σκεφτούμε αυτό,

749
00:37:46,840 --> 00:37:50,830
όλες πίνακα κατακερματισμού είναι μια
σειρά από συνδεδεμένες λίστες.

750
00:37:50,830 --> 00:37:55,670
Και έτσι, με αυτή την έννοια, θα πρέπει
Αυτή η όμορφη σειρά από δείκτες,

751
00:37:55,670 --> 00:37:58,740
και στη συνέχεια κάθε δείκτη στη
ότι η αξία, του εν λόγω δείκτη,

752
00:37:58,740 --> 00:38:00,740
μπορεί πραγματικά να δείχνουν άλλα πράγματα.

753
00:38:00,740 --> 00:38:05,720
Και έτσι έχετε όλες αυτές τις ξεχωριστές
αλυσίδες έρχεται από μια μεγάλη ποικιλία.

754
00:38:05,720 --> 00:38:07,960
>> Και έτσι εδώ, αν μου
ήθελε να εισαγάγετε μούρο,

755
00:38:07,960 --> 00:38:11,220
Το ξέρω, εντάξει, θα πάω στην είσοδο
μέσω της λειτουργίας κατακερματισμού μου.

756
00:38:11,220 --> 00:38:15,070
Πάω να καταλήξετε με το δείκτη
1, και στη συνέχεια, Πάω να είναι σε θέση να έχουν

757
00:38:15,070 --> 00:38:20,410
μόνο ένα μικρότερο υποσύνολο αυτό
γίγαντας 140.000 λέξη λεξικό.

758
00:38:20,410 --> 00:38:24,220
Και τότε μπορώ να εξετάσουμε μόνο
μέσω 1/26 από αυτό.

759
00:38:24,220 --> 00:38:27,910
>> Και έτσι τότε μπορώ να εισαγάγετε μόνο
μούρο είτε πριν είτε μετά μπανάνα

760
00:38:27,910 --> 00:38:28,820
σε αυτήν την περίπτωση?

761
00:38:28,820 --> 00:38:29,700
Μετά, σωστά;

762
00:38:29,700 --> 00:38:33,920
Και έτσι θα πάμε να θέλουν να
εισάγετε τον κόμβο αυτό μετά από μπανάνα,

763
00:38:33,920 --> 00:38:36,667
και έτσι θα πάμε να εισάγετε
στην ουρά της συνδεδεμένης λίστας.

764
00:38:36,667 --> 00:38:38,500
Πάω να πάω πίσω
σε αυτήν την προηγούμενη διαφάνεια,

765
00:38:38,500 --> 00:38:40,680
έτσι ώστε εσείς να δείτε πώς
hash λειτουργία του εργοστασίου.

766
00:38:40,680 --> 00:38:43,980
>> Έτσι hash λειτουργία είναι αυτή η εξίσωση
ότι τρέχετε το είδος της εισόδου σας

767
00:38:43,980 --> 00:38:46,940
μέσα για να πάρει ό, τι του δείκτη
Θέλετε να αναθέσει προς την κατεύθυνση.

768
00:38:46,940 --> 00:38:51,130
Και έτσι, σε αυτό το παράδειγμα, όλοι θέλαμε
να κάνει ήταν να πάρει το πρώτο γράμμα,

769
00:38:51,130 --> 00:38:55,890
τη σειρά του ότι σε ένα δείκτη, τότε
μπορεί να αποθηκεύσει ότι σε συνάρτηση κατακερματισμού μας.

770
00:38:55,890 --> 00:39:00,160
Όλα που κάνουμε εδώ είναι ότι είμαστε
μετατρέποντας το πρώτο γράμμα.

771
00:39:00,160 --> 00:39:04,770
Έτσι keykey [0] είναι μόνο το πρώτο γράμμα
από ό, τι εγχόρδων είμαστε έχοντας,

772
00:39:04,770 --> 00:39:05,720
είμαστε περνώντας.

773
00:39:05,720 --> 00:39:09,740
Είμαστε το μετατρέπει σε κεφαλαία, και
είμαστε αφαιρώντας από κεφαλαίο A,

774
00:39:09,740 --> 00:39:11,740
οπότε το μόνο που κάνει
μας δίνει έναν αριθμό

775
00:39:11,740 --> 00:39:13,670
στο οποίο μπορούμε να κατακερματίσει τις αξίες μας πάνω.

776
00:39:13,670 --> 00:39:16,550
>> Και μετά θα πάμε να
επιστρέψετε hash μέτρο ΜΕΓΕΘΟΣ.

777
00:39:16,550 --> 00:39:19,340
Να είστε πολύ, πολύ προσεκτικοί
διότι, θεωρητικά, εδώ

778
00:39:19,340 --> 00:39:21,870
hash αξία σας θα μπορούσε να είναι άπειρη.

779
00:39:21,870 --> 00:39:23,660
Θα μπορούσε απλά να συνεχίσω και επάνω και επάνω.

780
00:39:23,660 --> 00:39:26,080
Θα μπορούσε να είναι κάποια πραγματικά,
πραγματικά μεγάλη αξία,

781
00:39:26,080 --> 00:39:29,849
αλλά επειδή πίνακα κατακερματισμού σας που
έχετε δημιουργήσει έχει μόνο 26 δείκτες,

782
00:39:29,849 --> 00:39:31,890
θέλετε να βεβαιωθείτε ότι σας
modulusing έτσι ώστε να

783
00:39:31,890 --> 00:39:33,848
Δεν run-- είναι το ίδιο
πράγμα όπως queue-- σας

784
00:39:33,848 --> 00:39:36,320
έτσι ώστε να μην τρέξει το
κάτω μέρος της συνάρτησης κατακερματισμού σας.

785
00:39:36,320 --> 00:39:39,210
>> Θέλετε να το τυλίξετε γύρω από πίσω
με τον ίδιο τρόπο σε [δεν ακούγεται] όταν

786
00:39:39,210 --> 00:39:41,750
είχατε σαν μια πολύ,
πολύ μεγάλο γράμμα, θα

787
00:39:41,750 --> 00:39:43,740
δεν θέλουμε να
μόλις βγουν από το τέλος.

788
00:39:43,740 --> 00:39:46,948
Ίδιο πράγμα εδώ, θέλετε να είστε σίγουροι
δεν τρέχει από το τέλος του περιτυλίγματος

789
00:39:46,948 --> 00:39:48,330
γύρω από την κορυφή του πίνακα.

790
00:39:48,330 --> 00:39:50,530
Έτσι, αυτό είναι μόνο ένα πολύ
απλή συνάρτηση κατακερματισμού.

791
00:39:50,530 --> 00:39:56,570
Το μόνο που έκανε ήταν να λάβει το πρώτο
επιστολή του, ανεξάρτητα από τη συμβολή μας ήταν

792
00:39:56,570 --> 00:40:01,660
και να μετατρέψει αυτό σε ένα ευρετήριο που
θα μπορούσε να θέσει σε πίνακα κατακερματισμού μας.

793
00:40:01,660 --> 00:40:05,450
>> Ναι, και έτσι όπως είπα πριν,
Ο τρόπος που την επίλυση των συγκρούσεων

794
00:40:05,450 --> 00:40:09,330
στο hash μας πίνακες που έχουν,
αυτό που λέμε, αλυσοποίηση.

795
00:40:09,330 --> 00:40:13,860
Έτσι, αν προσπαθήσετε να εισάγετε πολλαπλές
λέξεις που αρχίζουν με το ίδιο πράγμα,

796
00:40:13,860 --> 00:40:16,145
θα πάμε να έχουν ένα hash αξία.

797
00:40:16,145 --> 00:40:18,770
Τα αβοκάντο και μήλο, αν έχετε
εκτελέσετε μέσω hash λειτουργία μας,

798
00:40:18,770 --> 00:40:21,450
πρόκειται να σας δώσει το
ίδιο αριθμό, ο αριθμός των 0.

799
00:40:21,450 --> 00:40:24,550
Και έτσι ο τρόπος να λύσουμε αυτό είναι
ότι μπορούμε πραγματικά να το είδος της σχέσης τους

800
00:40:24,550 --> 00:40:27,010
μαζί με συνδεδεμένες λίστες.

801
00:40:27,010 --> 00:40:29,600
>> Και έτσι με αυτή την έννοια,
εσείς μπορείτε να δείτε το είδος

802
00:40:29,600 --> 00:40:32,640
πώς δομών δεδομένων τα οποία
έχουμε τη παλαιότερα

803
00:40:32,640 --> 00:40:35,870
σαν σταφίδα συνδεδεμένη λίστα είδος
της μπορεί να έρθει μαζί σε ένα.

804
00:40:35,870 --> 00:40:38,860
Και τότε μπορείτε να δημιουργήσετε τώρα
πιο αποδοτικές δομές δεδομένων

805
00:40:38,860 --> 00:40:43,350
ότι μπορεί να χειριστεί μεγαλύτερες ποσότητες
δεδομένα, ότι το μέγεθος δυναμικά ανάλογα

806
00:40:43,350 --> 00:40:44,870
με τις ανάγκες σας.

807
00:40:44,870 --> 00:40:45,620
Όλοι σαφής;

808
00:40:45,620 --> 00:40:47,580
Ο καθένας το είδος των σαφών
σχετικά με το τι συμβαίνει εδώ;

809
00:40:47,580 --> 00:40:52,110
>> Αν ήθελα να insert-- τι είναι ένα
φρούτα που ξεκινά με, δεν ξέρω,

810
00:40:52,110 --> 00:40:54,726
Β, εκτός από μούρο, μπανάνα.

811
00:40:54,726 --> 00:40:55,710
>> Κοινό: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI PENG: Blackberry, βατόμουρο.

813
00:40:57,910 --> 00:41:00,530
Πού βατόμουρο πάει εδώ;

814
00:41:00,530 --> 00:41:04,251
Λοιπόν, στην πραγματικότητα δεν έχουν ταξινομηθεί
αυτό ακόμα, αλλά θεωρητικά

815
00:41:04,251 --> 00:41:06,250
αν θέλαμε να έχουμε αυτό
με αλφαβητική σειρά,

816
00:41:06,250 --> 00:41:07,944
όπου θα πρέπει BlackBerry πάει;

817
00:41:07,944 --> 00:41:09,210
>> Κοινό: [δεν ακούγεται]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG: Ακριβώς, αφού εδώ, σωστά;

819
00:41:11,100 --> 00:41:14,950
Αλλά δεδομένου ότι είναι πολύ δύσκολο να
reorder-- Υποθέτω ότι είναι στο χέρι σας παιδιά.

820
00:41:14,950 --> 00:41:17,920
Εσείς μπορείτε εντελώς
να εφαρμόσουν ό, τι θέλετε.

821
00:41:17,920 --> 00:41:20,730
Ο πιο αποτελεσματικός τρόπος
για να γίνει αυτό ίσως

822
00:41:20,730 --> 00:41:24,570
θα ήταν να ταξινομήσετε τα συνδεδεμένα σας
λίστα σε αλφαβητική σειρά,

823
00:41:24,570 --> 00:41:26,520
και έτσι όταν είστε
εισάγοντας τα πράγματα, θέλετε

824
00:41:26,520 --> 00:41:28,632
να είναι σίγουρος για την εισαγωγή τους
σε αλφαβητική σειρά

825
00:41:28,632 --> 00:41:30,590
έτσι ώστε στη συνέχεια, όταν είστε
προσπαθούν να τα αναζητήσετε,

826
00:41:30,590 --> 00:41:32,410
δεν χρειάζεται να διασχίσει τα πάντα.

827
00:41:32,410 --> 00:41:35,290
Ξέρετε πού ακριβώς
είναι, και είναι ευκολότερο.

828
00:41:35,290 --> 00:41:39,100
>> Αλλά αν έχετε το είδος του
πράγματα που διανθίζονται τυχαία,

829
00:41:39,100 --> 00:41:41,420
πρόκειται ακόμα να έχουν
να το διασχίσει ούτως ή άλλως.

830
00:41:41,420 --> 00:41:44,990
Και έτσι αν ήθελα απλά να
εισάγετε εδώ βατόμουρο

831
00:41:44,990 --> 00:41:47,470
και θα ήθελα να αναζητήσετε
αυτό, το ξέρω, OH, βατόμουρο

832
00:41:47,470 --> 00:41:52,012
πρέπει να ξεκινήσει με το δείκτη 1, γι 'αυτό
ξέρω ακαριαία μόλις αναζήτηση στο 1.

833
00:41:52,012 --> 00:41:53,970
Και τότε μπορώ να το είδος του
διασχίζουν τη συνδεδεμένη λίστα

834
00:41:53,970 --> 00:41:56,120
μέχρι να φτάσω στο BlackBerry,
και then-- ναι;

835
00:41:56,120 --> 00:41:59,550
>> Κοινό: Εάν προσπαθείτε να create--
Υποθέτω ότι όπως αυτό είναι ένα πολύ απλό κατακερματισμού

836
00:41:59,550 --> 00:42:00,050
λειτουργία.

837
00:42:00,050 --> 00:42:02,835
Και αν θέλαμε να κάνουμε
πολλαπλά στρώματα της εν λόγω παρόμοια,

838
00:42:02,835 --> 00:42:05,870
Εντάξει, θέλουμε να διαχωριστούν σε
όπως και όλα τα γράμματα του αλφαβήτου

839
00:42:05,870 --> 00:42:09,040
και στη συνέχεια και πάλι να αρέσει ένα άλλο σύνολο
από γράμματα του αλφαβήτου μέσα σε αυτό,

840
00:42:09,040 --> 00:42:11,715
είμαστε βάζοντας σαν ένα hash
πίνακα μέσα σε έναν πίνακα κατακερματισμού,

841
00:42:11,715 --> 00:42:13,256
ή σαν μια συνάρτηση μέσα σε μια συνάρτηση;

842
00:42:13,256 --> 00:42:14,880
Ή είναι that--

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG: Έτσι κατακερματισμού σας
function-- πίνακα κατακερματισμού σας

844
00:42:17,510 --> 00:42:19,360
μπορεί να είναι τόσο μεγάλη όσο θέλετε να.

845
00:42:19,360 --> 00:42:21,930
Έτσι, με αυτή την έννοια, σκέφτηκα
ήταν πολύ εύκολη, πολύ

846
00:42:21,930 --> 00:42:25,320
απλό για μένα να βασίζεται ακριβώς το είδος
σχετικά με τις επιστολές της πρώτης λέξης.

847
00:42:25,320 --> 00:42:28,690
Και έτσι υπάρχει μόνο 26 επιλογές.

848
00:42:28,690 --> 00:42:32,650
Μπορώ να πάρω μόνο 26 από τις επιλογές
0-25 επειδή μπορούν μόνο

849
00:42:32,650 --> 00:42:36,510
ξεκινήστε από το Α ως το Ω, αλλά αν ήθελες
για να προσθέσετε, ίσως, μεγαλύτερη πολυπλοκότητα

850
00:42:36,510 --> 00:42:39,260
ή να τρέξει πιο γρήγορα η ώρα να σας
hash πίνακα, θα πρέπει οπωσδήποτε

851
00:42:39,260 --> 00:42:40,760
μπορεί να κάνει όλα τα είδη των πραγμάτων.

852
00:42:40,760 --> 00:42:43,330
Μπορείτε να φτιάξετε το δικό σας
εξίσωση που σας δίνει

853
00:42:43,330 --> 00:42:48,000
πιο διανομή σε σας
Δηλαδή, στη συνέχεια, όταν κάνετε αναζήτηση,

854
00:42:48,000 --> 00:42:49,300
πρόκειται να είναι ταχύτερη.

855
00:42:49,300 --> 00:42:52,100
>> Είναι εντελώς μέχρι σας παιδιά
πώς θέλετε να υλοποιήσετε αυτό.

856
00:42:52,100 --> 00:42:55,140
Σκεφτείτε το σαν απλά κουβάδες.

857
00:42:55,140 --> 00:42:57,376
Αν ήθελα να έχω
26 κουβάδες, Πάω

858
00:42:57,376 --> 00:42:59,420
να τακτοποιήσει τα πράγματα σε αυτές τις κάδους.

859
00:42:59,420 --> 00:43:02,980
Αλλά Πάω να έχουν μια δέσμη
πράγματα σε κάθε κάδο,

860
00:43:02,980 --> 00:43:05,890
οπότε αν θέλετε να το κάνει
ταχύτερη και πιο αποτελεσματική,

861
00:43:05,890 --> 00:43:07,190
επιτρέψτε μου να έχουν εκατό κουβάδες.

862
00:43:07,190 --> 00:43:09,290
>> Αλλά τότε θα πρέπει να υπολογίσετε ένα
τρόπος για να τακτοποιήσει τα πράγματα, έτσι ώστε να είναι

863
00:43:09,290 --> 00:43:11,040
στη σωστή κάδο θα πρέπει να είναι σε.

864
00:43:11,040 --> 00:43:13,331
Στη συνέχεια, όμως, όταν στην πραγματικότητα
θέλουμε να εξετάσουμε αυτό το κουβά,

865
00:43:13,331 --> 00:43:16,410
Είναι πολύ πιο γρήγορα, γιατί υπάρχει
λιγότερα πράγματα σε κάθε κάδο.

866
00:43:16,410 --> 00:43:20,250
Και έτσι, ναι, αυτό είναι πραγματικότητα
το τέχνασμα για σας παιδιά σε pset5

867
00:43:20,250 --> 00:43:22,360
είναι ότι θα είναι
την πρόκληση να δημιουργήσει μόνο

868
00:43:22,360 --> 00:43:26,170
ό, τι είναι η πιο αποτελεσματική
τη λειτουργία μπορείτε να σκεφτείτε ότι είναι

869
00:43:26,170 --> 00:43:28,520
είναι σε θέση να αποθηκεύουν και να ελέγξετε τις τιμές αυτές.

870
00:43:28,520 --> 00:43:30,840
>> Συνολικά μέχρι σας παιδιά
Ωστόσο, θέλετε να το κάνετε,

871
00:43:30,840 --> 00:43:32,229
αλλά αυτό είναι ένα πολύ καλό σημείο.

872
00:43:32,229 --> 00:43:34,520
Αυτό το είδος της λογικής σας
Θέλετε να αρχίσουμε να σκεφτόμαστε

873
00:43:34,520 --> 00:43:37,236
Είναι, επίσης, λόγος για τον οποίο δεν μπορώ να κάνω περισσότερα κουβάδες.

874
00:43:37,236 --> 00:43:39,527
Και τότε θα πρέπει να αναζητήσετε
λιγότερα πράγματα, και τότε ίσως θα

875
00:43:39,527 --> 00:43:41,640
έχουν μια διαφορετική συνάρτηση κατακερματισμού.

876
00:43:41,640 --> 00:43:45,500
>> Ναι, υπάρχει πολλοί τρόποι για να γίνει αυτό
το chipset, μερικά είναι πιο γρήγορα από τους άλλους.

877
00:43:45,500 --> 00:43:50,630
Είμαι εντελώς πρόκειται να δούμε πόσο
γρήγορη ήταν η ταχύτερα εσείς θα

878
00:43:50,630 --> 00:43:55,170
να είναι σε θέση να πάρει τις λειτουργίες σας να εργαστείτε.

879
00:43:55,170 --> 00:43:58,176
Εντάξει, ο καθένας για καλό
αλύσωσης και hash πίνακες;

880
00:43:58,176 --> 00:44:00,800
Είναι πραγματικά σαν ένα πολύ απλό
ιδέα, αν το σκεφτείς.

881
00:44:00,800 --> 00:44:05,160
Όλα είναι διαχωρισμού είναι ανεξάρτητα
εισόδους σας σε κάδους,

882
00:44:05,160 --> 00:44:10,670
τη διαλογή τους, και στη συνέχεια η αναζήτηση
αναφέρει ότι εκεί που σχετίζονται με.

883
00:44:10,670 --> 00:44:11,852
>> Δροσερός.

884
00:44:11,852 --> 00:44:18,160
Εντάξει, τώρα έχουμε ένα διαφορετικό είδος
δομή δεδομένων που ονομάζεται ένα δέντρο.

885
00:44:18,160 --> 00:44:20,850
Ας προχωρήσουμε και να μιλήσουμε για προσπαθεί
τα οποία είναι σαφώς διαφορετική,

886
00:44:20,850 --> 00:44:22,330
αλλά στην ίδια κατηγορία.

887
00:44:22,330 --> 00:44:29,010
Ουσιαστικά, όλα είναι ένα δέντρο αντί
της οργάνωσης των δεδομένων στο γραμμικό τρόπο

888
00:44:29,010 --> 00:44:32,560
ότι ένας πίνακας κατακερματισμού που does--
Ξέρεις, είναι πήρε μια κορυφή και πυθμένα

889
00:44:32,560 --> 00:44:37,900
και τότε το είδος του συνδέσμου εκτός από ένα it--
δέντρο έχει μια κορυφή, το οποίο μπορείτε να καλέσετε τη ρίζα,

890
00:44:37,900 --> 00:44:40,220
και στη συνέχεια να έχει φύλλα όλα γύρω από αυτό.

891
00:44:40,220 --> 00:44:42,390
>> Και έτσι το μόνο που έχετε εδώ
είναι μόνο η κορυφή του κόμβου

892
00:44:42,390 --> 00:44:45,980
ότι παρατηρεί με άλλους κόμβους, ότι τα σημεία
να περισσότερους κόμβους, και ούτω καθεξής και ούτω καθεξής.

893
00:44:45,980 --> 00:44:48,130
Και έτσι απλά πρέπει διαχωρισμό υποκαταστήματα.

894
00:44:48,130 --> 00:44:53,255
Είναι απλά ένας διαφορετικός τρόπος οργάνωσης
δεδομένων, και επειδή το ένα δέντρο αποκαλούν,

895
00:44:53,255 --> 00:44:56,270
εσείς just-- είναι ακριβώς
πρότυπο έξω για να μοιάσει με ένα δέντρο.

896
00:44:56,270 --> 00:44:57,670
Αυτός είναι ο λόγος που εμείς αποκαλούμε δέντρα.

897
00:44:57,670 --> 00:44:59,370
>> Πίνακας κατακερματισμού μοιάζει με ένα τραπέζι.

898
00:44:59,370 --> 00:45:01,310
Ένα δέντρο μοιάζει ακριβώς όπως ένα δέντρο.

899
00:45:01,310 --> 00:45:03,300
Όλα είναι είναι ένα ξεχωριστό
τρόπος οργάνωσης των κόμβων

900
00:45:03,300 --> 00:45:06,020
ανάλογα με το ποιες είναι οι ανάγκες σας.

901
00:45:06,020 --> 00:45:11,810
>> Έτσι έχετε μια ρίζα και
τότε έχετε φύλλα.

902
00:45:11,810 --> 00:45:15,380
Ο τρόπος που μπορούμε να ιδιαίτερα
σκέφτομαι είναι ένα δυαδικό δέντρο,

903
00:45:15,380 --> 00:45:18,150
ένα δυαδικό δέντρο είναι απλά μια
συγκεκριμένο τύπο ενός δένδρου

904
00:45:18,150 --> 00:45:22,450
όπου κάθε κόμβος μόνο σημεία
να, στο μέγιστο, δύο άλλοι κόμβοι.

905
00:45:22,450 --> 00:45:25,434
Και έτσι εδώ έχετε διακριτές
συμμετρία στο δέντρο σας

906
00:45:25,434 --> 00:45:28,600
ότι είναι πιο εύκολο να δούμε το είδος του
σε ποιες τιμές θα είναι, γιατί τότε θα

907
00:45:28,600 --> 00:45:30,150
έχουν πάντα ένα αριστερό ή το δικαίωμα.

908
00:45:30,150 --> 00:45:33,150
Δεν υπάρχει ποτέ σαν αριστερό τρίτο από
το αριστερό ή ένα τέταρτο από τα αριστερά.

909
00:45:33,150 --> 00:45:36,358
Είναι απλά έχετε ένα αριστερό και ένα δεξί
και μπορείτε να αναζητήσετε κάποιο από αυτά τα δύο.

910
00:45:36,358 --> 00:45:38,980
Και γιατί είναι αυτό χρήσιμο;

911
00:45:38,980 --> 00:45:40,980
Ο τρόπος ότι αυτό είναι
χρήσιμο είναι αν ψάχνετε

912
00:45:40,980 --> 00:45:42,890
να αναζητήσετε μέσα από τις αξίες, σωστά;

913
00:45:42,890 --> 00:45:45,640
Αντί εφαρμογή δυαδικό
αναζήτηση σε μια σειρά σφαλμάτων,

914
00:45:45,640 --> 00:45:49,260
αν θέλετε να είστε σε θέση να τοποθετήσετε κόμβους
και να πάρει τους κόμβους κατά βούληση και, επίσης,

915
00:45:49,260 --> 00:45:52,185
τη διατήρηση της αναζήτησης
ικανότητες της δυαδικής αναζήτησης.

916
00:45:52,185 --> 00:45:54,560
Έτσι, με αυτόν τον τρόπο, είμαστε το είδος του
tricking-- θυμάστε όταν

917
00:45:54,560 --> 00:45:56,530
είπε συνδεδεμένες λίστες δεν μπορεί δυαδική αναζήτηση;

918
00:45:56,530 --> 00:46:01,700
Είμαστε το είδος της δημιουργίας μιας δομής δεδομένων
ότι κόλπα που εργάζονται σε.

919
00:46:01,700 --> 00:46:05,034
>> Και έτσι επειδή συνδεδεμένες λίστες είναι γραμμική,
συνδέουν μόνο το ένα μετά το άλλο.

920
00:46:05,034 --> 00:46:06,950
Είμαστε είδος μπορεί να έχει
διαφορετικό είδος των δεικτών

921
00:46:06,950 --> 00:46:09,408
ότι το σημείο σε διαφορετικούς κόμβους
ότι μπορεί να μας βοηθήσει με την αναζήτηση.

922
00:46:09,408 --> 00:46:12,590
Και έτσι εδώ, αν ήθελα να
έχουν ένα δυαδικό δένδρο αναζήτησης,

923
00:46:12,590 --> 00:46:14,090
Ξέρω ότι από τη μέση μου, αν 55.

924
00:46:14,090 --> 00:46:18,280
Είμαι ακριβώς πρόκειται να δημιουργήσει η
ως μέση μου, όπως ρίζα μου,

925
00:46:18,280 --> 00:46:20,770
και, στη συνέχεια, Πάω να έχουν
τιμές spin off του.

926
00:46:20,770 --> 00:46:25,610
>> Έτσι, εδώ, αν Πάω να αναζητήσετε
η αξία των 66, θα μπορεί να αρχίσει σε 55.

927
00:46:25,610 --> 00:46:27,310
Είναι μεγαλύτερη από 66 55;

928
00:46:27,310 --> 00:46:30,970
Ναι είναι, έτσι ξέρω mus αναζήτηση
i n το δικαίωμα δείκτη του δέντρου.

929
00:46:30,970 --> 00:46:32,440
Έχω πάει σε 77.

930
00:46:32,440 --> 00:46:35,367
Εντάξει, είναι μικρότερη από 66 ή μεγαλύτερο από 77;

931
00:46:35,367 --> 00:46:37,950
Είναι λιγότερο από ό, τι, έτσι ξέρετε, OH,
ότι πρέπει να είναι η αριστερά κόμβο.

932
00:46:37,950 --> 00:46:41,410
>> Και έτσι εδώ είμαστε το είδος της συντήρησης
όλα τα σπουδαία πράγματα σχετικά με συστοιχίες,

933
00:46:41,410 --> 00:46:44,420
έτσι όπως δυναμική μεταβολή του μεγέθους
των αντικειμένων, που είναι

934
00:46:44,420 --> 00:46:49,530
είναι σε θέση να εισάγετε και να διαγράψετε κατά βούληση,
χωρίς να χρειάζεται να ανησυχείτε για το σταθερό

935
00:46:49,530 --> 00:46:50,370
ποσό του χώρου.

936
00:46:50,370 --> 00:46:52,820
Εξακολουθούμε να διατηρήσουμε όλα
αυτά τα υπέροχα πράγματα

937
00:46:52,820 --> 00:46:57,140
ενώ επίσης είναι σε θέση να διατηρήσει το
καταγραφής και την ώρα της δυαδικής αναζήτησης αναζήτηση

938
00:46:57,140 --> 00:47:00,450
ότι ήμασταν μόνο στο παρελθόν
σε θέση να πάρετε μια φράση.

939
00:47:00,450 --> 00:47:06,310
>> Cool δομή δεδομένων, το είδος του
περίπλοκο να εφαρμοστεί, τον κόμβο.

940
00:47:06,310 --> 00:47:08,311
Όπως μπορείτε να δείτε, όλα είναι
είναι η struct του κόμβου

941
00:47:08,311 --> 00:47:10,143
είναι ότι έχετε μια αριστερά
και το δικαίωμα δείκτη.

942
00:47:10,143 --> 00:47:11,044
Αυτό είναι όλο αυτό είναι.

943
00:47:11,044 --> 00:47:12,960
Έτσι, όχι μόνο
που έχει μια X ή προηγούμενο.

944
00:47:12,960 --> 00:47:15,920
Έχετε μια αριστερή ή δεξιά, και στη συνέχεια,
μπορείτε να το είδος της διασύνδεσης τους

945
00:47:15,920 --> 00:47:16,836
Ωστόσο, μπορείτε να το επιλέξετε.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> Εντάξει, είμαστε στην πραγματικότητα θα
μόλις πάρει μερικά λεπτά.

948
00:47:24,270 --> 00:47:25,790
Έτσι θα πάμε να επιστρέψουμε εδώ.

949
00:47:25,790 --> 00:47:28,270
Όπως είπα και προηγουμένως,
Ι το είδος του εξήγησε

950
00:47:28,270 --> 00:47:31,520
η λογική πίσω από το πώς εμείς
θα αναζητήσετε μέσα από αυτό.

951
00:47:31,520 --> 00:47:33,860
Εμείς πάμε για να προσπαθήσουμε
pseudocoding αυτό για να δείτε

952
00:47:33,860 --> 00:47:38,000
αν μπορούμε να το είδος του να εφαρμοστεί η
ίδια λογική της δυαδικής αναζήτησης

953
00:47:38,000 --> 00:47:40,055
σε ένα διαφορετικό είδος δομής δεδομένων.

954
00:47:40,055 --> 00:47:45,049
Αν εσείς θέλετε να πάρετε σαν ένα ζευγάρι
λεπτά για να σκεφτείτε ακριβώς για αυτό.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
ΕΝΤΆΞΕΙ.

957
00:48:46,925 --> 00:48:51,407
Εντάξει, Πάω να
στην πραγματικότητα μόνο να σας δώσει the-- όχι,

958
00:48:51,407 --> 00:48:52,990
θα μιλήσουμε για την πρώτη ψευδοκώδικα.

959
00:48:52,990 --> 00:48:56,580
Έτσι δεν θέλει κανείς
για να δώσει ένα πλήγμα σε ό, τι

960
00:48:56,580 --> 00:49:02,100
το πρώτο πράγμα που θέλετε να κάνετε όταν
είστε ξεκινάμε αναζήτηση είναι;

961
00:49:02,100 --> 00:49:04,460
Αν ψάχνετε
η αξία των 66, τι είναι

962
00:49:04,460 --> 00:49:07,940
Το πρώτο πράγμα που θέλουμε να κάνουμε, αν
θέλουμε να δυαδική αναζήτηση αυτό το δέντρο;

963
00:49:07,940 --> 00:49:10,760
>> Κοινό: Θέλετε να δείτε σωστά
και κοιτάξτε αριστερά και δείτε [δεν ακούγεται]

964
00:49:10,760 --> 00:49:11,230
μεγαλύτερο αριθμό.

965
00:49:11,230 --> 00:49:12,271
>> ANDI PENG: Ναι, ακριβώς.

966
00:49:12,271 --> 00:49:15,350
Έτσι θα πάμε να δούμε στη ρίζα σας.

967
00:49:15,350 --> 00:49:18,180
Υπάρχουν πολλοί τρόποι που μπορείτε να καλέσετε
αυτό, οι άνθρωποι κόμβο γονέα σας πω.

968
00:49:18,180 --> 00:49:21,317
Θα ήθελα να πω, επειδή ρίζα
αυτό είναι σαν την ρίζα του δέντρου.

969
00:49:21,317 --> 00:49:23,400
Θα πάμε να δούμε
κόμβο-ρίζα σας, και να είστε

970
00:49:23,400 --> 00:49:26,940
πρόκειται να δούμε είναι μεγαλύτερη 66
ή μικρότερο από 55.

971
00:49:26,940 --> 00:49:30,360
Και αν αυτό είναι μεγαλύτερο από ό, τι, καλά, αυτό είναι
μεγαλύτερη από ό, τι, πού θέλουμε να δούμε;

972
00:49:30,360 --> 00:49:32,000
Πού θέλουμε να αναζητήσετε τώρα, έτσι δεν είναι;

973
00:49:32,000 --> 00:49:34,340
Θέλουμε να αναζητήσετε το
δεξιό μισό αυτού του δέντρου.

974
00:49:34,340 --> 00:49:38,390
>> Έτσι έχουμε, εύκολα,
δείκτης που δείχνει προς τα δεξιά.

975
00:49:38,390 --> 00:49:44,325
Και έτσι τότε μπορούμε να θέσουμε
νέα ρίζα μας να είναι 77.

976
00:49:44,325 --> 00:49:46,450
Μπορούμε απλά να πάμε οπουδήποτε
ο δείκτης δείχνει.

977
00:49:46,450 --> 00:49:49,100
Λοιπόν, OH, εδώ αρχίζουμε
σε 77, και μπορούμε μόνο

978
00:49:49,100 --> 00:49:51,172
κάνετε αυτό αναδρομικά ξανά και ξανά.

979
00:49:51,172 --> 00:49:52,880
Με αυτόν τον τρόπο, μπορείτε είδος
της έχουν μια λειτουργία.

980
00:49:52,880 --> 00:49:57,430
Έχετε έναν τρόπο για την αναζήτηση ώστε να
μπορεί απλώς να επαναλάβω ξανά και ξανά και ξανά,

981
00:49:57,430 --> 00:50:02,720
ανάλογα με το πού θέλετε να αναζητήσετε
μέχρι να φτάσετε τελικά στην τιμή

982
00:50:02,720 --> 00:50:04,730
ότι ψάχνετε για.

983
00:50:04,730 --> 00:50:05,230
Βγάζει νόημα?

984
00:50:05,230 --> 00:50:07,800
>> Είμαι έτοιμος να σας δείξει την πραγματική
κώδικα, και αυτό είναι ένα πολύ κώδικα.

985
00:50:07,800 --> 00:50:08,674
Δεν χρειάζεται να φρικάρεις.

986
00:50:08,674 --> 00:50:09,910
Θα μιλήσουμε μέσα από αυτό.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Στην πραγματικότητα, όχι.

989
00:50:14,020 --> 00:50:15,061
Αυτό ήταν απλά ψευδοκώδικα.

990
00:50:15,061 --> 00:50:17,860
Εντάξει, αυτό ήταν μόνο η ψευδοκώδικα,
το οποίο είναι ένα σύνθετο κομμάτι,

991
00:50:17,860 --> 00:50:19,751
αλλά είναι εντελώς καλά.

992
00:50:19,751 --> 00:50:21,000
Ο καθένας μετά μαζί εδώ;

993
00:50:21,000 --> 00:50:24,260
Αν η ρίζα είναι μηδενική, επιστροφή
ψευδείς διότι αυτό σημαίνει ότι

994
00:50:24,260 --> 00:50:26,850
δεν έχετε ακόμη τίποτα εκεί.

995
00:50:26,850 --> 00:50:31,376
>> Αν η ρίζα n είναι η τιμή, οπότε αν
συμβαίνει να είναι η μία κοιτάζετε,

996
00:50:31,376 --> 00:50:34,000
Στη συνέχεια θα πάμε να επιστρέψει αλήθεια
γιατί ξέρετε ότι το βρήκατε.

997
00:50:34,000 --> 00:50:36,250
Αλλά εάν η τιμή είναι μικρότερη
από ρίζα του n, είστε

998
00:50:36,250 --> 00:50:38,332
πρόκειται να αναζητήσετε το αριστερό
το παιδί ή το αριστερό φύλλο,

999
00:50:38,332 --> 00:50:39,540
ό, τι θέλετε να το ονομάσετε.

1000
00:50:39,540 --> 00:50:41,750
Και αν η τιμή είναι μεγαλύτερη από ρίζα,
θα πάμε για να αναζητήσετε το δικαίωμα δέντρο,

1001
00:50:41,750 --> 00:50:44,610
τότε απλά εκτελέστε την λειτουργία
μέσω της αναζήτησης πάλι.

1002
00:50:44,610 --> 00:50:48,037
>> Και αν ρίζα είναι μηδενική, ότι
σημαίνει ότι έχετε φτάσει στο τέλος;

1003
00:50:48,037 --> 00:50:50,120
Αυτό σημαίνει ότι δεν έχετε
περισσότερα περισσότερα φύλλα για να αναζητήσετε,

1004
00:50:50,120 --> 00:50:52,230
τότε ξέρεις, OH,
Υποθέτω ότι δεν είναι εδώ

1005
00:50:52,230 --> 00:50:55,063
γιατί μετά έχω κοίταξε μέσα
το όλο θέμα και δεν είναι εδώ,

1006
00:50:55,063 --> 00:50:56,930
απλά δεν θα μπορούσε να είναι εδώ.

1007
00:50:56,930 --> 00:50:58,350
>> Μήπως αυτό έχει νόημα για όλους;

1008
00:50:58,350 --> 00:51:03,230
Έτσι είναι σαν δυαδική αναζήτηση διατήρηση
οι δυνατότητες της συνδεδεμένες λίστες.

1009
00:51:03,230 --> 00:51:09,200
Cool, και έτσι ο δεύτερος τύπος
της δομής των δεδομένων σας παιδιά

1010
00:51:09,200 --> 00:51:13,180
μπορείτε να δοκιμάσετε την εφαρμογή για το chipset σας,
δεν έχετε παρά να επιλέξετε μία μέθοδο.

1011
00:51:13,180 --> 00:51:19,430
Αλλά ίσως μια εναλλακτική μέθοδο για να
ο πίνακας κατακερματισμού είναι αυτό που αποκαλούμε trie.

1012
00:51:19,430 --> 00:51:24,080
>> Όλα είναι μια trie είναι
συγκεκριμένο είδος δέντρου που

1013
00:51:24,080 --> 00:51:28,600
έχει τιμές που πηγαίνουν σε άλλες αξίες.

1014
00:51:28,600 --> 00:51:31,450
Έτσι, αντί να έχουν ένα δυαδικό
δέντρο με την έννοια ότι μόνο ένα

1015
00:51:31,450 --> 00:51:35,940
πράγμα που μπορεί να δείξει σε δύο, μπορείτε να έχετε
σημείο ένα πράγμα σε πολλά, πολλά πράγματα.

1016
00:51:35,940 --> 00:51:39,450
Έχετε ουσιαστικά συστοιχίες
μέσα από τα οποία μπορείτε να αποθηκεύσετε

1017
00:51:39,450 --> 00:51:41,790
δείκτες που παραπέμπουν σε άλλες σειρές.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Έτσι, ο κόμβος του πώς
θα καθορίσει μια trie

1020
00:51:49,460 --> 00:51:52,590
Είναι θέλουμε να έχουμε μια
Boolean, γ λέξη, έτσι δεν είναι;

1021
00:51:52,590 --> 00:51:54,920
Έτσι ο κόμβος είναι Boolean
όπως αληθείς ή ψευδείς,

1022
00:51:54,920 --> 00:51:58,490
πρώτα απ 'όλα στο κεφάλι της
ότι η διάταξη, είναι αυτή η λέξη;

1023
00:51:58,490 --> 00:52:03,620
Δεύτερον, θέλετε να έχετε δείκτες
σε ό, τι οι υπόλοιποι είναι.

1024
00:52:03,620 --> 00:52:07,470
Ένα σύνθετο κομμάτι, μια αφηρημένη λίγο, αλλά
Θα εξηγήσω τι όλα τα μέσα.

1025
00:52:07,470 --> 00:52:13,800
>> Εδώ λοιπόν, στην κορυφή, αν
έχουν μια σειρά δηλώσει ήδη,

1026
00:52:13,800 --> 00:52:17,040
ένας κόμβος όπου έχετε μια Boolean
τιμή αποθηκεύεται στο μπροστινό

1027
00:52:17,040 --> 00:52:19,490
ότι σας λέει αυτό είναι μια λέξη;

1028
00:52:19,490 --> 00:52:20,520
Δεν είναι αυτό μια λέξη;

1029
00:52:20,520 --> 00:52:23,240
Και τότε θα πρέπει η
υπόλοιπο της συστοιχίας σας που

1030
00:52:23,240 --> 00:52:26,040
στην πραγματικότητα αποθηκεύει όλα τα
δυνατότητες τι θα μπορούσε να είναι.

1031
00:52:26,040 --> 00:52:28,660
Έτσι, για παράδειγμα, όπως
στην κορυφή έχετε

1032
00:52:28,660 --> 00:52:32,140
Το πρώτο πράγμα που λέει αλήθεια ή
ψευδείς, ναι ή όχι, αυτό είναι μια λέξη.

1033
00:52:32,140 --> 00:52:38,130
>> Και τότε έχετε 0 έως 26 της
τα γράμματα που μπορείτε να αποθηκεύσετε.

1034
00:52:38,130 --> 00:52:42,790
Αν ήθελα να ψάξετε εδώ
για νυχτερίδα, πάω στην κορυφή

1035
00:52:42,790 --> 00:52:49,200
και ψάχνω να βρω Β Β μου
συστοιχία, και έτσι ξέρω, εντάξει, είναι Β μια λέξη;

1036
00:52:49,200 --> 00:52:53,010
Β δεν είναι μια λέξη, οπότε έτσι
Πρέπει να συνεχιστεί η αναζήτηση.

1037
00:52:53,010 --> 00:52:56,410
Πάω από το Β, και ελπίζω να το
δείκτη ο οποίος δείχνει προς την κατεύθυνση Β

1038
00:52:56,410 --> 00:53:00,900
και βλέπω μια άλλη σειρά από πληροφορίες,
η ίδια δομή που είχαμε πριν.

1039
00:53:00,900 --> 00:53:05,240
>> Και here-- OH, το επόμενο
e-mail στο [δεν ακούγεται] είναι Α

1040
00:53:05,240 --> 00:53:07,210
Έτσι θα δούμε σε αυτό το φάσμα.

1041
00:53:07,210 --> 00:53:10,860
Θα βρείτε την όγδοη αξία,
και στη συνέχεια να κοιτάξουμε να δούμε, OH,

1042
00:53:10,860 --> 00:53:12,840
hey, είναι ότι μια λέξη, είναι Β-Α μια λέξη;

1043
00:53:12,840 --> 00:53:13,807
Είναι μια λέξη που δεν είναι.

1044
00:53:13,807 --> 00:53:14,890
Έχουμε να συνεχίσετε να ψάχνετε.

1045
00:53:14,890 --> 00:53:17,850
>> Και έτσι τότε θα δούμε πού
ο δείκτης των σημείων Α,

1046
00:53:17,850 --> 00:53:21,130
και επισημαίνει σε έναν άλλο τρόπο με τον
το οποίο έχουμε περισσότερη αποθηκευμένη αξία.

1047
00:53:21,130 --> 00:53:24,150
Και τελικά, έχουμε την ευκαιρία να
Β-Α-Τ, το οποίο είναι μια λέξη.

1048
00:53:24,150 --> 00:53:25,970
Και έτσι την επόμενη φορά
αν κοιτάξουμε, θα πάμε

1049
00:53:25,970 --> 00:53:30,850
να έχουν τη σχετική επιταγή του, ναι,
Αυτό Boolean λειτουργία είναι αλήθεια.

1050
00:53:30,850 --> 00:53:35,450
Και έτσι, με την έννοια είμαστε είδος
της ύπαρξης ενός δέντρου με συστοιχίες.

1051
00:53:35,450 --> 00:53:39,890
>> Έτσι, τότε μπορείτε να το είδος της αναζήτησης προς τα κάτω.

1052
00:53:39,890 --> 00:53:43,650
Αντί hashing λειτουργία και
αποδίδοντας τιμές από συνδεδεμένη λίστα,

1053
00:53:43,650 --> 00:53:49,190
μπορείτε να εφαρμόσετε μόνο ένα
trie που αναζητά downwords.

1054
00:53:49,190 --> 00:53:50,850
Πραγματικά, πραγματικά περίπλοκα πράγματα.

1055
00:53:50,850 --> 00:53:54,060
Δεν είναι εύκολο να σκεφτούμε γιατί είμαι σαν
φτύσιμο τόσες πολλές δομές δεδομένων έξω

1056
00:53:54,060 --> 00:53:58,710
σε σας, αλλά κάνει ο καθένας το είδος του
κατανοήσουν πώς αυτή η λογική λειτουργεί;

1057
00:53:58,710 --> 00:54:01,920
>> ΟΚ κομπλε.

1058
00:54:01,920 --> 00:54:05,600
Έτσι Β-Α-Τ, και στη συνέχεια
θα πάμε να αναζητήσετε.

1059
00:54:05,600 --> 00:54:07,940
Την επόμενη φορά που θα πάμε
για να δείτε, ω, hey, είναι αλήθεια,

1060
00:54:07,940 --> 00:54:09,273
έτσι Ξέρω ότι αυτό πρέπει να είναι μια λέξη.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Ίδιο πράγμα για ζωολογικό κήπο.

1063
00:54:13,770 --> 00:54:17,960
Έτσι, εδώ είναι το πράγμα τώρα, αν θέλουμε
ήθελε να ψάξετε ζωολογικό κήπο, αυτή τη στιγμή,

1064
00:54:17,960 --> 00:54:20,780
σήμερα ζωολογικός κήπος δεν είναι μια
λέξη στο λεξικό μας

1065
00:54:20,780 --> 00:54:25,300
επειδή, όπως εσείς να δείτε, η
πρώτον, ότι έχουμε μια Boolean

1066
00:54:25,300 --> 00:54:28,590
return true βρίσκεται στο τέλος του ζουμ.

1067
00:54:28,590 --> 00:54:30,430
Έχουμε Ζ-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> Και έτσι και εδώ, δεν έχουμε στην πραγματικότητα
η λέξη, ζωολογικό κήπο, στο λεξικό μας

1069
00:54:33,900 --> 00:54:36,070
επειδή αυτό το πλαίσιο ελέγχου δεν είναι επιλεγμένο.

1070
00:54:36,070 --> 00:54:39,540
Έτσι, ο υπολογιστής δεν
Γνωρίζουμε ότι ζωολογικός κήπος είναι μια λέξη

1071
00:54:39,540 --> 00:54:42,430
επειδή ο τρόπος που έχουμε
αποθηκεύονται αυτό, μόνο ένα ζουμ εδώ

1072
00:54:42,430 --> 00:54:44,920
στην πραγματικότητα έχει μια τιμή Boolean
που είναι ήδη μετατραπεί αλήθεια.

1073
00:54:44,920 --> 00:54:49,380
Έτσι, αν θέλουμε να εισαχθεί η
λέξη, ζωολογικό κήπο, στο λεξικό μας,

1074
00:54:49,380 --> 00:54:51,770
πώς θα πάει για να κάνει αυτό;

1075
00:54:51,770 --> 00:54:55,960
Τι πρέπει να κάνουμε για να βεβαιωθείτε ότι μας
υπολογιστή γνωρίζει ότι η Ζ-Ο-Ο είναι μια λέξη

1076
00:54:55,960 --> 00:54:58,130
και δεν είναι η πρώτη λέξη είναι Ζ-O-O-M;

1077
00:54:58,130 --> 00:54:59,360
>> Κοινό: [δεν ακούγεται]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI PENG: Ακριβώς, έχουμε
θέλετε να βεβαιωθείτε ότι αυτό το

1079
00:55:01,450 --> 00:55:07,890
εδώ, ότι η τιμή είναι Boolean
ελέγχεται καλά ότι αυτό είναι αλήθεια.

1080
00:55:07,890 --> 00:55:13,297
Ζ-Ο-Ο, τότε θα πάμε για να ελέγξει ότι,
έτσι ώστε να γνωρίζουμε ακριβώς, hey, ζωολογικός κήπος είναι μια λέξη.

1081
00:55:13,297 --> 00:55:15,380
Πάω να πω το
υπολογιστή που είναι μια λέξη έτσι

1082
00:55:15,380 --> 00:55:18,000
ότι όταν οι έλεγχοι του υπολογιστή,
γνωρίζει ότι ζωολογικός κήπος είναι μια λέξη.

1083
00:55:18,000 --> 00:55:21,269
>> Επειδή θυμάμαι όλα αυτά τα δεδομένα
δομές, είναι πολύ εύκολο για μας

1084
00:55:21,269 --> 00:55:22,310
να πει, OH, νυχτερίδα είναι μια λέξη.

1085
00:55:22,310 --> 00:55:22,851
Ο ζωολογικός κήπος είναι μια λέξη.

1086
00:55:22,851 --> 00:55:23,611
Ζουμ είναι μια λέξη.

1087
00:55:23,611 --> 00:55:25,860
Αλλά όταν το κτίριο,
ο υπολογιστής δεν έχει ιδέα.

1088
00:55:25,860 --> 00:55:28,619
>> Έτσι θα πρέπει να το πω ακριβώς
σε ποιο σημείο βρίσκεται αυτή η λέξη;

1089
00:55:28,619 --> 00:55:29,910
Σε ποιο σημείο είναι ότι δεν είναι μια λέξη;

1090
00:55:29,910 --> 00:55:31,784
Και σε ποιο σημείο μπορώ να κάνω
Πρέπει να κάνετε τα πράγματα,

1091
00:55:31,784 --> 00:55:34,000
και σε ποιο σημείο πρέπει να κάνω για να πάω στη συνέχεια;

1092
00:55:34,000 --> 00:55:37,010
Ο καθένας μακριά από αυτό;

1093
00:55:37,010 --> 00:55:39,540
Δροσερός.

1094
00:55:39,540 --> 00:55:42,530
>> Και έτσι στη συνέχεια έρχεται η
πρόβλημα του πώς θα

1095
00:55:42,530 --> 00:55:45,560
πάει κάτι σχετικά με την τοποθέτηση
ότι δεν είναι πραγματικά εκεί;

1096
00:55:45,560 --> 00:55:49,090
Έτσι, ας πούμε ότι θέλετε να εισαγάγετε
η λέξη, μπάνιο, σε Trie μας.

1097
00:55:49,090 --> 00:55:53,589
Όπως εσείς μπορεί να δει όπως σήμερα
το μόνο που έχουμε τώρα είναι Β-Α-Τ,

1098
00:55:53,589 --> 00:55:55,630
και αυτή η νέα δομή δεδομένων
έπρεπε να υπάρχει μια πίντα ότι

1099
00:55:55,630 --> 00:55:59,740
επεσήμανε null επειδή θεωρούμε
ότι, OH, δεν υπάρχει καμία ένδειξη μετά από Β-Α-Τ,

1100
00:55:59,740 --> 00:56:02,530
γιατί χρειαζόμαστε για να κρατήσει
έχοντας τα πράγματα μετά από αυτή την Τ

1101
00:56:02,530 --> 00:56:06,581
>> Αλλά το πρόβλημα προκύπτει αν κάνετε
θέλουν να έχουν μια λέξη που έρχεται μετά

1102
00:56:06,581 --> 00:56:07,080
ο Τ.

1103
00:56:07,080 --> 00:56:09,500
Εάν έχετε μπάνιο, είστε
πρόκειται να θέλουν μια σωστή H.

1104
00:56:09,500 --> 00:56:13,290
Και έτσι ο τρόπος που θα πάμε να το κάνουμε αυτό είναι
θα πάμε για να δημιουργήσετε μια ξεχωριστή κόμβο.

1105
00:56:13,290 --> 00:56:16,840
Δεν είμαστε κατανείμει ανεξάρτητα από το ύψος
μνήμης για αυτή τη νέα σειρά,

1106
00:56:16,840 --> 00:56:20,720
και θα πάμε να εκχωρήσετε εκ νέου δείκτες.

1107
00:56:20,720 --> 00:56:22,947
>> Εμείς πάμε για να ορίσετε το
Η, Πρώτα απ 'όλα, αυτό το null,

1108
00:56:22,947 --> 00:56:24,030
θα πάμε για να απαλλαγούμε από.

1109
00:56:24,030 --> 00:56:26,590
Εμείς πάμε για να έχουν
οι προς τα κάτω το σημείο Η.

1110
00:56:26,590 --> 00:56:30,600
Αν δείτε ένα H, το θέλουμε
για να πάει κάπου αλλού.

1111
00:56:30,600 --> 00:56:33,910
>> Εδώ, μπορούμε στη συνέχεια να ελέγξετε μακριά ναι.

1112
00:56:33,910 --> 00:56:38,170
Αν χτυπήσει ένα H μετά την T, ω,
τότε ξέρουμε ότι αυτό είναι μια λέξη.

1113
00:56:38,170 --> 00:56:41,110
Η Boolean πρόκειται να επιστρέψει αλήθεια.

1114
00:56:41,110 --> 00:56:42,950
Όλοι σαφής σχετικά με το πώς συνέβη αυτό;

1115
00:56:42,950 --> 00:56:45,110
ΕΝΤΆΞΕΙ.

1116
00:56:45,110 --> 00:56:47,214
>> Έτσι, κατ 'ουσίαν, το σύνολο των
Αυτές οι δομές δεδομένων

1117
00:56:47,214 --> 00:56:50,130
ότι έχουμε περάσει πάνω από σήμερα, έχω
πάει πάνω από τους πραγματικά, πραγματικά γρήγορα

1118
00:56:50,130 --> 00:56:52,192
και όχι σε πολύ
λεπτομέρεια, και αυτό είναι εντάξει.

1119
00:56:52,192 --> 00:56:53,900
Μόλις αρχίσετε να πειράξουν
με αυτό, θα είστε

1120
00:56:53,900 --> 00:56:55,733
την παρακολούθηση του πού
όλοι οι δείκτες είναι,

1121
00:56:55,733 --> 00:56:58,060
τι συμβαίνει σε σας
δομές δεδομένων, κ.λπ..

1122
00:56:58,060 --> 00:56:59,810
Θα είναι πολύ χρήσιμο,
και είναι στο χέρι σας

1123
00:56:59,810 --> 00:57:03,890
παιδιά να καταλάβω απόλυτα πώς
Θέλετε να εφαρμόσουν τα πράγματα.

1124
00:57:03,890 --> 00:57:07,650
>> Και έτσι pset4, της 5-- Ω, αυτό είναι λάθος.

1125
00:57:07,650 --> 00:57:10,140
Pset5 είναι ορθογραφικά λάθη.

1126
00:57:10,140 --> 00:57:13,710
Όπως είπα και πριν, θα πάμε να, μια φορά
και πάλι, να κατεβάσετε τον πηγαίο κώδικα από εμάς.

1127
00:57:13,710 --> 00:57:16,210
Εκεί πρόκειται να είναι τρία κύρια
πράγματα που θα πρέπει να κατεβάσετε.

1128
00:57:16,210 --> 00:57:18,470
Θα κατεβάσετε λεξικά,
KERS, και τα κείμενα.

1129
00:57:18,470 --> 00:57:21,660
>> Όλα αυτά τα πράγματα είναι οι
είτε λεξικά λέξεων

1130
00:57:21,660 --> 00:57:25,190
ότι θέλουμε να ελέγξουμε
ή δοκιμή πληροφοριών

1131
00:57:25,190 --> 00:57:26,930
ότι θέλουμε να ορθογραφικός έλεγχος.

1132
00:57:26,930 --> 00:57:29,670
Και έτσι τα λεξικά
σας δίνουμε την ευκαιρία

1133
00:57:29,670 --> 00:57:34,870
για να σας δώσει πραγματικές λέξεις που θέλουμε
μπορείτε να αποθηκεύσετε κάπως με έναν τρόπο που είναι

1134
00:57:34,870 --> 00:57:36,530
πιο αποτελεσματική από μια συστοιχία.

1135
00:57:36,530 --> 00:57:38,470
Και τότε τα κείμενα αυτά είναι
πρόκειται να είναι ό, τι είμαστε

1136
00:57:38,470 --> 00:57:43,900
ζητώντας σας να ορθογραφικό έλεγχο για να βεβαιωθείτε ότι
όλες τις λέξεις υπάρχουν πραγματικές λέξεις.

1137
00:57:43,900 --> 00:57:47,970
>> Και έτσι οι τρεις συστάδες
προγράμματα που θα σας δώσουμε

1138
00:57:47,970 --> 00:57:51,130
καλούνται dictionary.c,
dictionary.h, και speller.c.

1139
00:57:51,130 --> 00:57:56,500
Και έτσι όλα dictionary.c κάνει είναι να
τι θα σας ζητηθεί να εφαρμόσουν.

1140
00:57:56,500 --> 00:57:57,880
Φορτώνει λέξεις.

1141
00:57:57,880 --> 00:58:02,000
Θα σημάνει ελέγχους αυτούς, και να σιγουρεύεται
ότι όλα είναι σωστά τοποθετημένη.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h είναι απλά ένα αρχείο βιβλιοθήκης
ότι δηλώνει όλες αυτές τις λειτουργίες.

1143
00:58:05,180 --> 00:58:07,650
Και speller.c, θα πάμε να σας δώσω.

1144
00:58:07,650 --> 00:58:09,290
Δεν χρειάζεται να τροποποιήσετε οποιαδήποτε από αυτό.

1145
00:58:09,290 --> 00:58:14,290
Όλα speller.c δεν είναι ότι λαμβάνει,
φορτώνει, ελέγχει την ταχύτητα του,

1146
00:58:14,290 --> 00:58:19,190
ελέγχει το σημείο αναφοράς του, όπως το πώς
γρήγορα θα είστε σε θέση να κάνουμε τα πράγματα.

1147
00:58:19,190 --> 00:58:20,410
>> Είναι ένας ορθογράφος.

1148
00:58:20,410 --> 00:58:23,920
Απλά δεν με αυτό το χάλι, αλλά κάνει
βεβαιωθείτε ότι έχετε κατανοήσει τι κάνει.

1149
00:58:23,920 --> 00:58:28,090
Χρησιμοποιούμε μια συνάρτηση που ονομάζεται getrusage ότι
ελέγχει την απόδοση των περίοδό σας

1150
00:58:28,090 --> 00:58:28,590
ντάμα.

1151
00:58:28,590 --> 00:58:32,200
Το μόνο που κάνει είναι βασικά η δοκιμή
χρόνος για τα πάντα στο λεξικό σας,

1152
00:58:32,200 --> 00:58:33,680
οπότε φροντίστε να το καταλάβουν.

1153
00:58:33,680 --> 00:58:36,660
Να είστε προσεκτικοί για να μην το χάος με αυτό ή
αλλιώς τα πράγματα δεν θα λειτουργήσει σωστά.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> Και το μεγαλύτερο μέρος αυτής της πρόκλησης είναι για
εσείς να τροποποιήσετε πραγματικά dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Εμείς πάμε για να σας δώσω
140.000 λέξεις σε ένα λεξικό.

1157
00:58:48,526 --> 00:58:50,900
Εμείς πάμε για να σας δώσω ένα κείμενο
αρχείο που έχει αυτά τα λόγια,

1158
00:58:50,900 --> 00:58:54,840
και θέλουμε να είστε σε θέση να οργανώσει
τους σε ένα πίνακα κατακερματισμού ή trie

1159
00:58:54,840 --> 00:58:58,140
γιατί όταν σας ζητάμε να σημάνει
check-- φανταστείτε εάν είστε ξόρκι

1160
00:58:58,140 --> 00:59:00,690
τον έλεγχο, όπως Οδύσσεια του Ομήρου.

1161
00:59:00,690 --> 00:59:03,010
Είναι σαν αυτό το τεράστιο, τεράστια δοκιμασία.

1162
00:59:03,010 --> 00:59:05,190
>> Φανταστείτε αν κάθε
λέξη που έπρεπε να κοιτάξουμε

1163
00:59:05,190 --> 00:59:08,100
μέσω μιας σειράς από 140.000 αξιών.

1164
00:59:08,100 --> 00:59:10,350
Αυτό θα πάρει για πάντα
για το μηχάνημά σας να τρέξει.

1165
00:59:10,350 --> 00:59:14,490
Αυτός είναι ο λόγος για τον οποίο θέλουμε να οργανώσουμε μας
δεδομένα σε πιο αποδοτικές δομές δεδομένων

1166
00:59:14,490 --> 00:59:17,270
όπως ένα πίνακα κατακερματισμού ή trie.

1167
00:59:17,270 --> 00:59:20,700
Και τότε εσείς να το είδος
του κατά την αναζήτηση πρόσβασης

1168
00:59:20,700 --> 00:59:22,570
τα πράγματα πιο εύκολα και πιο γρήγορα.

1169
00:59:22,570 --> 00:59:24,934
>> Και έτσι πρέπει να είστε προσεκτικοί για την επίλυση συγκρούσεων.

1170
00:59:24,934 --> 00:59:27,350
Θα πάμε για να πάρει μια δέσμη
των λέξεων που αρχίζουν με Α

1171
00:59:27,350 --> 00:59:29,957
Θα πάμε για να πάρει ένα σωρό λέξεις
που να αρχίζουν από Β Έως σας

1172
00:59:29,957 --> 00:59:31,290
παιδιά πώς θέλετε να το λύσουμε.

1173
00:59:31,290 --> 00:59:34,144
Ίσως υπάρχουν και άλλα
αποδοτική λειτουργία hash

1174
00:59:34,144 --> 00:59:36,810
όχι μόνο το πρώτο γράμμα του
κάτι, και έτσι αυτό είναι στο χέρι σας

1175
00:59:36,810 --> 00:59:38,190
παιδιά με το είδος του κάνει ό, τι θέλετε.

1176
00:59:38,190 --> 00:59:40,148
>> Ίσως θέλετε να προσθέσετε
Όλα τα γράμματα μαζί.

1177
00:59:40,148 --> 00:59:43,410
Ίσως θέλετε να αρέσει να κάνει περίεργα πράγματα
για λογαριασμό του αριθμού των γραμμάτων,

1178
00:59:43,410 --> 00:59:43,970
οτιδήποτε.

1179
00:59:43,970 --> 00:59:45,386
Μέχρι εσείς πώς θέλετε να κάνετε.

1180
00:59:45,386 --> 00:59:49,262
Αν θέλετε να κάνετε ένα πίνακα κατακερματισμού, εάν
θέλετε να δοκιμάσετε ένα trie, συνολικά μέχρι σας.

1181
00:59:49,262 --> 00:59:52,470
Θα σας προειδοποιήσω εκ των προτέρων ότι η
trie είναι συνήθως λίγο πιο δύσκολο

1182
00:59:52,470 --> 00:59:54,520
μόνο και μόνο επειδή υπάρχει πολύς
περισσότερους δείκτες να παρακολουθείτε.

1183
00:59:54,520 --> 00:59:55,645
Αλλά συνολικά μέχρι σας παιδιά.

1184
00:59:55,645 --> 00:59:58,742
Είναι πολύ πιο αποτελεσματική
στις περισσότερες περιπτώσεις.

1185
00:59:58,742 --> 01:00:01,450
Θέλετε πραγματικά να είναι σε θέση να κρατήσει
παρακολουθεί όλους τους δείκτες σας.

1186
01:00:01,450 --> 01:00:03,850
Όπως και να κάνει το ίδιο πράγμα
ότι έκανα εδώ.

1187
01:00:03,850 --> 01:00:06,871
Όταν προσπαθείτε να εισαγάγετε
τιμές σε έναν πίνακα κατακερματισμού ή διαγραφή,

1188
01:00:06,871 --> 01:00:08,620
βεβαιωθείτε ότι είστε
πραγματικά την παρακολούθηση

1189
01:00:08,620 --> 01:00:11,860
όπου τα πάντα είναι επειδή
Είναι πολύ εύκολο για αν είμαι

1190
01:00:11,860 --> 01:00:14,727
προσπαθώντας να εισαγάγετε όπως τη λέξη, Andy.

1191
01:00:14,727 --> 01:00:16,810
Ας πούμε ότι είναι ένα
πραγματική λέξη, η λέξη, Andy,

1192
01:00:16,810 --> 01:00:19,640
σε ένα τεράστιο λίστα με λέξεις.

1193
01:00:19,640 --> 01:00:22,450
>> Αν εγώ απλώς τυχαίνει να επανεκχώρηση
ένας δείκτης λάθος, ουπς,

1194
01:00:22,450 --> 01:00:24,940
πηγαίνει εκεί το σύνολο των
το υπόλοιπο της συνδεδεμένης λίστας μου.

1195
01:00:24,940 --> 01:00:26,897
Τώρα η μόνη λέξη που μπορώ
έχουν είναι Andy, και τώρα

1196
01:00:26,897 --> 01:00:29,230
όλα τα άλλα λόγια στην
Λεξικό έχουν χαθεί.

1197
01:00:29,230 --> 01:00:31,370
Και έτσι θέλετε να βεβαιωθείτε ότι έχετε
να παρακολουθείτε όλους τους δείκτες σας

1198
01:00:31,370 --> 01:00:33,661
ή αλλιώς θα πάμε να πάρετε
τεράστια προβλήματα στον κώδικά σας.

1199
01:00:33,661 --> 01:00:35,840
Σχεδιάστε τα πράγματα προσεκτικά βήμα προς βήμα.

1200
01:00:35,840 --> 01:00:37,870
Κάνει πολύ πιο εύκολο να σκεφτώ.

1201
01:00:37,870 --> 01:00:40,910
>> Και τέλος, θέλετε να είναι σε θέση να
δοκιμάσετε τις επιδόσεις σας το πρόγραμμά σας

1202
01:00:40,910 --> 01:00:41,618
στη μεγάλη πλακέτα.

1203
01:00:41,618 --> 01:00:43,710
Εάν πάρετε εσείς μια
κοιτάξουμε CS50 τώρα,

1204
01:00:43,710 --> 01:00:45,210
έχουμε αυτό που ονομάζεται η μεγάλη πλακέτα.

1205
01:00:45,210 --> 01:00:50,200
Είναι το φύλλο αγώνα της ταχύτερης
ορθογραφικός έλεγχος φορές σε όλες τις CS50

1206
01:00:50,200 --> 01:00:55,720
τώρα, πιστεύω και στην κορυφή, όπως 10
φορές νομίζω ότι οκτώ από αυτά είναι το προσωπικό.

1207
01:00:55,720 --> 01:00:57,960
Θέλουμε πραγματικά εσείς να μας νικήσει.

1208
01:00:57,960 --> 01:01:00,870
>> Όλοι μας προσπαθούσαμε να εφαρμόσουν
το γρηγορότερο δυνατό κωδικός.

1209
01:01:00,870 --> 01:01:04,880
Θέλουμε εσείς να προσπαθήσει να αμφισβητήσει
μας και να υλοποιήσει ταχύτερα από όλους μας

1210
01:01:04,880 --> 01:01:05,550
κουτί.

1211
01:01:05,550 --> 01:01:07,970
Και έτσι αυτό είναι πραγματικά
η πρώτη φορά που είμαστε

1212
01:01:07,970 --> 01:01:12,680
ζητώντας εσείς να κάνετε μια PSET ότι
μπορείτε να το κάνετε πραγματικά σε οποιαδήποτε μέθοδο

1213
01:01:12,680 --> 01:01:13,760
θέλεις.

1214
01:01:13,760 --> 01:01:17,730
>> Λέω πάντα, αυτό μοιάζει περισσότερο
σε ένα διάλυμα πραγματική ζωή, έτσι δεν είναι;

1215
01:01:17,730 --> 01:01:19,550
Λέω, hey, πρέπει να το κάνετε αυτό.

1216
01:01:19,550 --> 01:01:21,380
Φτιάξτε ένα πρόγραμμα που το κάνει αυτό για μένα.

1217
01:01:21,380 --> 01:01:22,630
Κάν 'το όπως θέλετε.

1218
01:01:22,630 --> 01:01:24,271
Απλά ξέρω ότι θέλω να νηστεύουν.

1219
01:01:24,271 --> 01:01:25,770
Αυτή είναι η πρόκλησή σας για αυτή την εβδομάδα.

1220
01:01:25,770 --> 01:01:27,531
Εσείς, θα πάμε
για να σας δώσει μια εργασία.

1221
01:01:27,531 --> 01:01:29,030
Εμείς πάμε για να σας δώσει μια πρόκληση.

1222
01:01:29,030 --> 01:01:31,559
Και τότε είναι στο χέρι σας παιδιά
σε εντελώς μόλις καταλάβω

1223
01:01:31,559 --> 01:01:34,100
Ποια είναι η πιο γρήγορος και πιο
αποτελεσματικός τρόπος για την εφαρμογή αυτή.

1224
01:01:34,100 --> 01:01:34,600
Ναι;

1225
01:01:34,600 --> 01:01:37,476
>> Κοινό: μας επιτρέπεται να αν
ήθελε να ερευνήσει ταχύτερους τρόπους

1226
01:01:37,476 --> 01:01:40,821
να κάνει πίνακες κατακερματισμού σε απευθείας σύνδεση, μπορούμε να κάνουμε
ότι και αναφέρουν κώδικα κάποιου άλλου;

1227
01:01:40,821 --> 01:01:42,070
ANDI PENG: Ναι, μια χαρά.

1228
01:01:42,070 --> 01:01:44,320
Έτσι, αν εσείς διαβάζετε το
spec, υπάρχει μια γραμμή

1229
01:01:44,320 --> 01:01:48,310
στο spec που λέει σας παιδιά
είναι εντελώς δωρεάν για την έρευνα hash

1230
01:01:48,310 --> 01:01:51,070
λειτουργίες για το τι είναι μερικά
από τους πιο γρήγορους συναρτήσεις κατακερματισμού

1231
01:01:51,070 --> 01:01:54,720
να τρέξει τα πράγματα από μέσα, όπως
Εφ 'όσον αναφέρω εν λόγω κώδικα.

1232
01:01:54,720 --> 01:01:57,220
Έτσι, μερικοί άνθρωποι έχουν ήδη
κατάλαβα γρήγορα τρόπους

1233
01:01:57,220 --> 01:02:00,250
για να γίνει ξόρκι πούλια, του γρήγορου
τρόποι αποθήκευση πληροφοριών.

1234
01:02:00,250 --> 01:02:02,750
Συνολικά μέχρι σας παιδιά, αν
θέλουν να πάρουν ακριβώς αυτό, έτσι δεν είναι;

1235
01:02:02,750 --> 01:02:04,045
Βεβαιωθείτε ότι είστε επικαλούμενη.

1236
01:02:04,045 --> 01:02:06,170
Η πρόκληση εδώ πραγματικά
ότι προσπαθούμε να δοκιμάσει

1237
01:02:06,170 --> 01:02:09,750
είναι να διασφαλίσουμε ότι γνωρίζετε
το δρόμο σας γύρω από δείκτες.

1238
01:02:09,750 --> 01:02:12,700
Όσον αφορά την εφαρμογή σας
η πραγματική συνάρτηση κατακερματισμού

1239
01:02:12,700 --> 01:02:15,070
και έρχονται με παρόμοια
τα μαθηματικά για να το κάνουμε αυτό,

1240
01:02:15,070 --> 01:02:17,570
εσείς μπορείτε να ερευνήσετε ανεξαρτήτως
μεθόδους σε απευθείας σύνδεση εσείς θέλετε.

1241
01:02:17,570 --> 01:02:17,996
Ναι;

1242
01:02:17,996 --> 01:02:19,700
>> Κοινό: Μπορούμε να αναφέρω μόνο
με τη χρήση του [δεν ακούγεται];

1243
01:02:19,700 --> 01:02:20,120
>> ANDI PENG: Ναι.

1244
01:02:20,120 --> 01:02:22,328
Μπορείτε απλά, στο σχόλιό σας,
μπορείτε να αναφέρω, όπως, OH,

1245
01:02:22,328 --> 01:02:26,127
που λαμβάνονται από μπλα, μπλα,
μπλα, συνάρτηση κατακερματισμού.

1246
01:02:26,127 --> 01:02:27,210
Όποιος έχει οποιαδήποτε απορία;

1247
01:02:27,210 --> 01:02:29,694
Είμαστε πραγματικά breezed
μέσα από το τμήμα σήμερα.

1248
01:02:29,694 --> 01:02:31,610
Θα είμαι εδώ για να
απαντήσει σε ερωτήσεις, καθώς και.

1249
01:02:31,610 --> 01:02:36,570
>> Επίσης, όπως είπα, το γραφείο
ώρες απόψε και αύριο.

1250
01:02:36,570 --> 01:02:40,307
Το spec αυτή την εβδομάδα είναι στην πραγματικότητα
εξαιρετικά εύκολο και σούπερ σύντομη για να διαβάσετε.

1251
01:02:40,307 --> 01:02:43,140
Θα ήθελα να προτείνω να ρίξουμε μια ματιά, απλά
διαβάστε το σύνολο της.

1252
01:02:43,140 --> 01:02:45,730
>> Και Zamyla βόλτες σας στην πραγματικότητα
μέσω καθεμία από τις λειτουργίες

1253
01:02:45,730 --> 01:02:49,796
θα πρέπει να εφαρμόσουν, και γι 'αυτό είναι
πολύ, πολύ σαφές το πώς να κάνει τα πάντα.

1254
01:02:49,796 --> 01:02:51,920
Ακριβώς για να βεβαιωθείτε ότι είστε
την παρακολούθηση των δεικτών.

1255
01:02:51,920 --> 01:02:53,650
Αυτό είναι ένα πολύ δύσκολο το chipset.

1256
01:02:53,650 --> 01:02:56,744
>> Δεν είναι δύσκολο, διότι, όπως,
OH, οι έννοιες είναι πολύ πιο

1257
01:02:56,744 --> 01:02:59,160
δύσκολο, ή θα πρέπει να μάθετε
τόσα πολλά νέα σύνταξη ο τρόπος

1258
01:02:59,160 --> 01:03:00,650
ότι κάνατε για τελευταία το chipset.

1259
01:03:00,650 --> 01:03:03,320
Αυτό το chipset είναι δύσκολο, διότι
υπάρχουν τόσοι πολλοί δείκτες,

1260
01:03:03,320 --> 01:03:06,980
και τότε είναι πολύ, πολύ εύκολο να φορά
έχεις ένα σφάλμα στον κώδικα σας δεν είναι σε θέση

1261
01:03:06,980 --> 01:03:08,315
για να βρείτε όπου αυτό είναι σφάλμα.

1262
01:03:08,315 --> 01:03:13,200
>> Και έτσι πλήρης και απόλυτη πίστη σε σας
παιδιά να είναι σε θέση να νικήσει μας [δεν ακούγεται]

1263
01:03:13,200 --> 01:03:13,700
ορθογραφίες.

1264
01:03:13,700 --> 01:03:16,640
Εγώ πραγματικά δεν έχουν καμία γραπτή ορυχείο
ακόμα, αλλά είμαι έτοιμος να γράψω τη δική μου.

1265
01:03:16,640 --> 01:03:19,070
Έτσι, ενώ είστε γραπτώς
δικό σου, θα είμαι εγγράφως ορυχείου.

1266
01:03:19,070 --> 01:03:21,070
Πάω να προσπαθήσουμε να κάνουμε
ορυχείο πιο γρήγορα από τη δική σας.

1267
01:03:21,070 --> 01:03:23,940
Θα δούμε ποιος έχει την γρηγορότερη.

1268
01:03:23,940 --> 01:03:27,340
>> Και ναι, εγώ θα τα δείτε όλα
εσείς εδώ την Τρίτη.

1269
01:03:27,340 --> 01:03:29,510
Θα τρέξει ένα είδος σαν ένα εργαστήριο το chipset.

1270
01:03:29,510 --> 01:03:32,640
Όλα τα τμήματα αυτού
εβδομάδα είναι το chipset εργαστήρια,

1271
01:03:32,640 --> 01:03:36,690
έτσι ώστε εσείς έχετε πολλές ευκαιρίες
για βοήθεια, ώρες γραφείου, όπως πάντα,

1272
01:03:36,690 --> 01:03:41,330
και πραγματικά ανυπομονώ να
ανάγνωση όλων των κωδικό παιδιά σας ».

1273
01:03:41,330 --> 01:03:44,160
Έχω κουίζ εδώ αν
παιδιά θέλουν να έρθουν να πάρει εκείνα.

1274
01:03:44,160 --> 01:03:45,880
Αυτά.

1275
01:03:45,880 --> 01:03:48,180