1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Week 6]

2
00:00:02,000 --> 00:00:04,000
[David J. Malan] [Harvard University]

3
00:00:04,000 --> 00:00:08,000
[Dit is CS50.] [CS50.TV]

4
00:00:08,000 --> 00:00:12,000
>> Dit is CS50, en dit is het begin van week 6

5
00:00:12,000 --> 00:00:16,000
dus een paar nieuwe tools zijn nu beschikbaar voor u om te profiteren van,

6
00:00:16,000 --> 00:00:19,000
waarvan de eerste wordt genoemd CS50 stijl.

7
00:00:19,000 --> 00:00:22,000
Odds zijn als je net als ik of een van de leer fellows,

8
00:00:22,000 --> 00:00:26,000
je hebt waarschijnlijk gezien een programma waarvan de stijl ziet er een beetje iets als dit.

9
00:00:26,000 --> 00:00:30,000
Misschien heb je begint te zagen sommige hoeken 's avonds laat, of je later mee omgaan,

10
00:00:30,000 --> 00:00:32,000
en dan een TF of CA komt over tijdens de kantooruren.

11
00:00:32,000 --> 00:00:34,000
Dan is het moeilijk voor ons om te lezen.

12
00:00:34,000 --> 00:00:38,000
Nou, deze code is syntactisch correct, en het compileren wordt, en het ook daadwerkelijk uit te voeren.

13
00:00:38,000 --> 00:00:40,000
Maar het is zeker geen 5 voor stijl.

14
00:00:40,000 --> 00:00:45,000
>> Maar nu, als we naar deze map hier-

15
00:00:45,000 --> 00:00:48,000
en merk dat ik conditions2.c-have

16
00:00:48,000 --> 00:00:55,000
en ik run deze nieuwe opdracht, style50, op dit bestand conditions2.c, Enter,

17
00:00:55,000 --> 00:00:57,000
merken dat het is me op de hoogte dat het gestileerde geweest.

18
00:00:57,000 --> 00:01:00,000
Gedit merkte dat het bestand is gewijzigd op de schijf,

19
00:01:00,000 --> 00:01:08,000
en als ik klik op laden, zijn al je problemen nu geautomatiseerd.

20
00:01:08,000 --> 00:01:15,000
[Applaus]

21
00:01:15,000 --> 00:01:17,000
Dat is een van de dingen die we deden dit weekend.

22
00:01:17,000 --> 00:01:20,000
Realiseer je dat het onvolmaakt is, want er zijn een aantal code

23
00:01:20,000 --> 00:01:23,000
dat het gewoon niet in staat zijn om perfect te stileren,

24
00:01:23,000 --> 00:01:26,000
realiseren, maar dit is nu een tool die u kunt profiteren van

25
00:01:26,000 --> 00:01:33,000
al was het maar op te ruimen een aantal van de meer moedwillig een verkeerde geplaatste accolades en dergelijke.

26
00:01:33,000 --> 00:01:36,000
>> Maar meer dwingende is nu CS50 Check.

27
00:01:36,000 --> 00:01:39,000
Met CS50 Check, kun je eigenlijk het uitvoeren van dezelfde juistheid testen

28
00:01:39,000 --> 00:01:42,000
op uw eigen code die de leer fellows kunnen.

29
00:01:42,000 --> 00:01:44,000
Dit is een command line utility dat nu komt in het apparaat

30
00:01:44,000 --> 00:01:46,000
zodra u een update50 per doen

31
00:01:46,000 --> 00:01:49,000
PSET 4 specificaties, en je gebruikt het in wezen als dit.

32
00:01:49,000 --> 00:01:51,000
U voert de opdracht check50.

33
00:01:51,000 --> 00:01:56,000
Dan passeert u op een opdrachtregel argument, of meer algemeen bekend als een schakelaar of een vlag.

34
00:01:56,000 --> 00:01:58,000
Over het algemeen zijn dingen die koppeltekens hebben wel een schakelaar

35
00:01:58,000 --> 00:02:02,000
om een ​​command line programma, dus-c geeft aan

36
00:02:02,000 --> 00:02:04,000
de controles die u wilt uitvoeren.

37
00:02:04,000 --> 00:02:07,000
>> De tests die u wilt uitvoeren worden geïdentificeerd uniek door deze string,

38
00:02:07,000 --> 00:02:10,000
2012/pset4/resize.

39
00:02:10,000 --> 00:02:13,000
Met andere woorden, dat is gewoon een willekeurige, maar unieke string

40
00:02:13,000 --> 00:02:18,000
die we gebruiken om uniek te identificeren PSET 4's juistheid tests.

41
00:02:18,000 --> 00:02:21,000
En dan geeft u een spatie gescheiden lijst van de bestanden die u wilt uploaden

42
00:02:21,000 --> 00:02:24,000
om CS50 Controleer voor analyse.

43
00:02:24,000 --> 00:02:29,000
Bijvoorbeeld, als ik in mijn oplossing hier voor resize.c-

44
00:02:29,000 --> 00:02:31,000
Laat me open te stellen een grotere terminal venster-

45
00:02:31,000 --> 00:02:42,000
en ik ga je gang en lopen laten we zeggen check50-c 2012/pset4/resize,

46
00:02:42,000 --> 00:02:46,000
en dan ga ik ga je gang en geef de namen van de bestanden,

47
00:02:46,000 --> 00:02:49,000
resize.c, en druk dan op Enter, het comprimeert,

48
00:02:49,000 --> 00:02:53,000
Het uploads, controleert, en ik net niet een hele hoop tests.

49
00:02:53,000 --> 00:02:59,000
De een op de rode linksboven zegt dat er resize.c en bmp.

50
00:02:59,000 --> 00:03:01,000
Dat was de test. Dat was de vraag die we stelden.

51
00:03:01,000 --> 00:03:04,000
En het is ongelukkig omdat het antwoord was vals.

52
00:03:04,000 --> 00:03:08,000
De witte tekst eronder staat naar verwachting bmp.h te bestaan, en dat is gewoon mijn schuld.

53
00:03:08,000 --> 00:03:11,000
Ik ben vergeten om het te uploaden, dus ik moet beide bestanden te uploaden,

54
00:03:11,000 --> 00:03:14,000
resize.c en bmp.h.

55
00:03:14,000 --> 00:03:17,000
Maar let nu op alle andere tests zijn in het geel, omdat ze nog niet hebt uitgevoerd,

56
00:03:17,000 --> 00:03:21,000
en zo de smiley verticaal is, want hij is noch tevreden, noch verdrietig,

57
00:03:21,000 --> 00:03:25,000
maar we moeten deze kwestie verhaal in het rood voor die andere controles worden uitgevoerd.

58
00:03:25,000 --> 00:03:27,000
>> Laat mij dit oplossen.

59
00:03:27,000 --> 00:03:30,000
Laat me uit te zoomen en herstart deze, dit keer met bmp.h ook

60
00:03:30,000 --> 00:03:34,000
op de opdrachtregel, Enter, en nu als alles goed gaat,

61
00:03:34,000 --> 00:03:38,000
het gaat om te controleren en dan terug naar aanleiding van-je adem-

62
00:03:38,000 --> 00:03:42,000
alle groene, wat betekent dat ik ben echt goed op PSET 4 tot nu toe.

63
00:03:42,000 --> 00:03:44,000
U kunt zien en afleiden uit de beschrijvende tekst hier

64
00:03:44,000 --> 00:03:47,000
precies wat het is die we hebben getest.

65
00:03:47,000 --> 00:03:49,000
We testten eerst de bestanden bestaan ​​er?

66
00:03:49,000 --> 00:03:51,000
Vervolgens hebben we getest doet resize.c compileren?

67
00:03:51,000 --> 00:03:58,000
Dan hebben we getest is het niet de grootte van een 1x1-pixel BMP als n, het formaat wijzigen factor, is 1.

68
00:03:58,000 --> 00:04:01,000
Nu, als je geen idee wat n is, zult u zodra u een duik nemen in PSET 4,

69
00:04:01,000 --> 00:04:04,000
maar dat is gewoon een controle op een gezond verstand om ervoor te zorgen dat je niet resizen

70
00:04:04,000 --> 00:04:08,000
een beeld helemaal als het formaat wijzigen factor is 1.

71
00:04:08,000 --> 00:04:14,000
Indien daarentegen het formaat van een 1x1 pixel een 1x1 pixel BMP kunnen tot 2x2

72
00:04:14,000 --> 00:04:19,000
wanneer n 2 dan evenzo mine vormt dan.

73
00:04:19,000 --> 00:04:22,000
>> Kortom, dit is bedoeld om, een, neem de oversteken van de vingers

74
00:04:22,000 --> 00:04:25,000
uit de vergelijking vlak voordat u uw PSET.

75
00:04:25,000 --> 00:04:28,000
U weet precies wat uw TF binnenkort zal weten

76
00:04:28,000 --> 00:04:30,000
als je gaat over het indienen van een aantal van deze problemen sets,

77
00:04:30,000 --> 00:04:34,000
en ook de pedagogische motivatie is echt te maken aan

78
00:04:34,000 --> 00:04:37,000
de mogelijkheid voor u, zodat wanneer u bij voorbaat weet

79
00:04:37,000 --> 00:04:39,000
dat er bugs in de code en tests die nog niet worden doorgegeven,

80
00:04:39,000 --> 00:04:43,000
u kunt in meer effectieve tijd van te voren om die problemen op te lossen

81
00:04:43,000 --> 00:04:45,000
in plaats van verliest punten, feedback te krijgen van uw TF,

82
00:04:45,000 --> 00:04:48,000
en ga dan, "Ahh," alsof ik zou hebben bedacht dat uit.

83
00:04:48,000 --> 00:04:50,000
Nu in ieder geval is er een hulpmiddel om u te helpen dat.

84
00:04:50,000 --> 00:04:52,000
Het gaat niet om erop te wijzen waar de bug is, maar het zal u vertellen

85
00:04:52,000 --> 00:04:54,000
wat is symptomatisch voor het.

86
00:04:54,000 --> 00:04:57,000
>> Nu beseffen de tests zijn niet noodzakelijkerwijs volledig.

87
00:04:57,000 --> 00:04:59,000
Alleen maar omdat je op een scherm vol met groene smiley gezichten

88
00:04:59,000 --> 00:05:02,000
betekent niet dat uw code is perfect, maar het betekent wel

89
00:05:02,000 --> 00:05:06,000
dat het voorbij is bepaalde tests voorgeschreven door de spec.

90
00:05:06,000 --> 00:05:08,000
Soms zullen we niet vrijgeven controles.

91
00:05:08,000 --> 00:05:10,000
Bijvoorbeeld whodunit een van de aspecten van PSET 4,

92
00:05:10,000 --> 00:05:15,000
is een beetje teleurstellend als we geven u

93
00:05:15,000 --> 00:05:18,000
de antwoord op de vraag wat het is, en er is een aantal manieren om te onthullen

94
00:05:18,000 --> 00:05:21,000
wie de persoon is in die rode ruis.

95
00:05:21,000 --> 00:05:24,000
De spec zal altijd aangeven in de toekomst voor PSET 5 verder

96
00:05:24,000 --> 00:05:26,000
welke controles er voor u.

97
00:05:26,000 --> 00:05:28,000
U zult merken dat er dit witte URL aan de onderkant.

98
00:05:28,000 --> 00:05:30,000
Voor nu, dit is gewoon diagnose-uitgang.

99
00:05:30,000 --> 00:05:33,000
Als u een bezoek dat URL, krijg je een hele hoop gekke, cryptische berichten

100
00:05:33,000 --> 00:05:36,000
dat u bent van harte welkom om te kijken door, maar het is vooral voor het personeel

101
00:05:36,000 --> 00:05:41,000
zodat wij kunnen diagnosticeren en debuggen bugs in check50 zelf.

102
00:05:41,000 --> 00:05:46,000
>> Zonder omhaal, laten we verder gaan waar we gebleven waren.

103
00:05:46,000 --> 00:05:48,000
CS50 bibliotheek namen we voor lief voor enkele weken,

104
00:05:48,000 --> 00:05:52,000
maar dan vorige week, zijn we begonnen met peeling terug een van de lagen van het.

105
00:05:52,000 --> 00:05:55,000
We zijn begonnen met terzijdestelling reeks ten gunste van wat in plaats daarvan?

106
00:05:55,000 --> 00:05:57,000
[Studenten] Char.

107
00:05:57,000 --> 00:05:59,000
Char *, dat is een char * al die tijd,

108
00:05:59,000 --> 00:06:03,000
maar nu hebben we niet te doen alsof dat het een feitelijke gegevenstype string.

109
00:06:03,000 --> 00:06:06,000
Integendeel, het is een synoniem van soorten voor char *,

110
00:06:06,000 --> 00:06:09,000
en een string is een reeks tekens,

111
00:06:09,000 --> 00:06:14,000
dus waarom heeft het zin om strings te vertegenwoordigen als char * s?

112
00:06:14,000 --> 00:06:20,000
Wat doet een char * vertegenwoordigen in het kader van dit concept van een string?

113
00:06:20,000 --> 00:06:23,000
Ja. >> [Student] Het eerste teken.

114
00:06:23,000 --> 00:06:25,000
Goed, het eerste teken, maar niet helemaal het eerste teken.

115
00:06:25,000 --> 00:06:27,000
Het is de-[Studenten] Adres.

116
00:06:27,000 --> 00:06:29,000
Good, het adres van het eerste teken.

117
00:06:29,000 --> 00:06:33,000
Alles wat nodig is om een ​​string te vertegenwoordigen in het geheugen van een computer

118
00:06:33,000 --> 00:06:36,000
ligt het unieke adres van de eerste byte.

119
00:06:36,000 --> 00:06:38,000
Je hoeft niet eens te weten hoe lang het is

120
00:06:38,000 --> 00:06:42,000
want hoe kun je erachter dat uit dynamisch?

121
00:06:42,000 --> 00:06:44,000
[Student] String lengte.

122
00:06:44,000 --> 00:06:48,000
U kunt bellen tekstlengte, uitstekend, maar hoe werkt string lengte werk?

123
00:06:48,000 --> 00:06:50,000
Wat doet het? Ja.

124
00:06:50,000 --> 00:06:52,000
[Student] Blijf doorgaan totdat je de nul karakter.

125
00:06:52,000 --> 00:06:54,000
Ja, precies, het herhaalt enkel met een for-lus, while-lus,

126
00:06:54,000 --> 00:06:57,000
wat van * tot het einde, en het einde is vertegenwoordigd

127
00:06:57,000 --> 00:07:01,000
door \ 0, de zogenaamde nul karakter, nul,

128
00:07:01,000 --> 00:07:05,000
niet te verwarren met null, een pointer,

129
00:07:05,000 --> 00:07:07,000
die zal wederkomen in gesprek vandaag.

130
00:07:07,000 --> 00:07:11,000
>> We geschild terug een laagje GetInt, en toen namen we een kijkje op GetString,

131
00:07:11,000 --> 00:07:14,000
en herinneren eraan dat deze beide functies, of eigenlijk,

132
00:07:14,000 --> 00:07:18,000
GetString, was het gebruik van een bepaalde functie

133
00:07:18,000 --> 00:07:21,000
om daadwerkelijk ontleden, is dat, te lezen of te analyseren, invoer van de gebruiker.

134
00:07:21,000 --> 00:07:25,000
En wat was dat nieuwe functie?

135
00:07:25,000 --> 00:07:27,000
Scanf of sscanf. Het komt eigenlijk in een paar verschillende smaken.

136
00:07:27,000 --> 00:07:31,000
Er is scanf, er is sscanf, is er fscanf.

137
00:07:31,000 --> 00:07:35,000
Voorlopig echter, laten we focussen op het meest simpele illustratie,

138
00:07:35,000 --> 00:07:38,000
en laat mij door te gaan en open te stellen in het apparaat

139
00:07:38,000 --> 00:07:41,000
een bestand als dit, scanf1.c.

140
00:07:41,000 --> 00:07:43,000
Dit is een super eenvoudig programma,

141
00:07:43,000 --> 00:07:46,000
maar dat doet iets dat we nooit hebben gedaan

142
00:07:46,000 --> 00:07:48,000
zonder de hulp van de CS50 bibliotheek.

143
00:07:48,000 --> 00:07:51,000
Dit wordt een int van een gebruiker. Hoe werkt het?

144
00:07:51,000 --> 00:07:53,000
Nou, in lijn 16 daar,

145
00:07:53,000 --> 00:07:56,000
merken dat we een int genaamd x verklaren, en op dit punt in het verhaal,

146
00:07:56,000 --> 00:07:58,000
wat is de waarde van x?

147
00:07:58,000 --> 00:08:00,000
[Onverstaanbaar student reactie]

148
00:08:00,000 --> 00:08:02,000
[David M.] Rechts, wie weet, wat vuilnis waarde potentieel, dus in 17, we vertellen de gebruiker

149
00:08:02,000 --> 00:08:06,000
geef me een nummer, neem dan, en stap 18 is waar het interessant wordt.

150
00:08:06,000 --> 00:08:11,000
Scanf lijkt te lenen een idee van printf in zoverre dat het deze indeling codes gebruikt tussen aanhalingstekens.

151
00:08:11,000 --> 00:08:13,000
% D is natuurlijk een decimaal getal.

152
00:08:13,000 --> 00:08:21,000
Maar waarom ben ik passeren in en x in plaats van alleen x?

153
00:08:21,000 --> 00:08:24,000
De eerste is correct. Ja.

154
00:08:24,000 --> 00:08:26,000
[Onverstaanbaar student reactie]

155
00:08:26,000 --> 00:08:31,000
Precies, als het doel van dit programma, zoals de functie GetInt zelf,

156
00:08:31,000 --> 00:08:34,000
wordt naar een int te krijgen van de gebruiker Ik kan passeren functies

157
00:08:34,000 --> 00:08:38,000
alle variabelen ik wil, maar als ik het niet door te geven aan de hand

158
00:08:38,000 --> 00:08:41,000
of op adres of pointer, alle synoniem voor doeleinden van vandaag,

159
00:08:41,000 --> 00:08:46,000
dan die functie heeft geen mogelijkheid om de inhoud van die variabele.

160
00:08:46,000 --> 00:08:49,000
Dit zou pas in een exemplaar, net als de buggy versie van swap

161
00:08:49,000 --> 00:08:51,000
dat we hebben gesproken over een paar keer.

162
00:08:51,000 --> 00:08:54,000
>> Maar in plaats daarvan, door het doen van & x, ik ben letterlijk voorbij in wat?

163
00:08:54,000 --> 00:08:57,000
[Student] Het adres. >> Het adres van x.

164
00:08:57,000 --> 00:09:01,000
Het is als het tekenen van een kaart voor de functie genaamd scanf en zeggen hier,

165
00:09:01,000 --> 00:09:04,000
dit zijn aanwijzingen om een ​​stuk van het geheugen in de computer

166
00:09:04,000 --> 00:09:07,000
dat u kunt gaan slaan een geheel getal in

167
00:09:07,000 --> 00:09:10,000
Om sscanf te doen nu

168
00:09:10,000 --> 00:09:13,000
wat operator, is wat stuk syntaxis gaat het om het gebruik van

169
00:09:13,000 --> 00:09:19,000
ook al kunnen we het niet zien omdat iemand anders schreef deze functie?

170
00:09:19,000 --> 00:09:21,000
Met andere woorden - wat is dat?

171
00:09:21,000 --> 00:09:23,000
[Student] X te lezen.

172
00:09:23,000 --> 00:09:27,000
Er gaat wat te lezen, maar alleen met betrekking tot x hier.

173
00:09:27,000 --> 00:09:30,000
Als scanf wordt doorgegeven het adres van x,

174
00:09:30,000 --> 00:09:35,000
syntactisch, is wat operator gebonden aan ergens bestaan

175
00:09:35,000 --> 00:09:38,000
binnenkant van de uitvoering scanf's, zodat scanf

176
00:09:38,000 --> 00:09:42,000
kan een nummer 2 eigenlijk schrijven naar dat adres?

177
00:09:42,000 --> 00:09:44,000
Ja, dus de *.

178
00:09:44,000 --> 00:09:47,000
Bedenk dat het * is onze dereference operator, die in wezen betekent dat er heen gaan.

179
00:09:47,000 --> 00:09:50,000
>> Als je eenmaal hebt ingeleverd een adres, zoals hier het geval is,

180
00:09:50,000 --> 00:09:53,000
scanf is waarschijnlijk, als we echt keek om zich heen de broncode-

181
00:09:53,000 --> 00:09:59,000
doet * x of het equivalent om daadwerkelijk te gaan naar dat adres en plaats daar enige waarde.

182
00:09:59,000 --> 00:10:02,000
Nu, als voor de manier waarop scanf inbreng krijgt van het toetsenbord,

183
00:10:02,000 --> 00:10:04,000
we zwaaien onze handen uit voor vandaag.

184
00:10:04,000 --> 00:10:07,000
Gewoon aannemen dat het besturingssysteem maakt het mogelijk sscanf om te praten

185
00:10:07,000 --> 00:10:11,000
de gebruiker het toetsenbord, maar op dit punt nu in lijn 19,

186
00:10:11,000 --> 00:10:14,000
als we gewoon afdrukken x lijkt het geval

187
00:10:14,000 --> 00:10:17,000
dat scanf heeft een int in x.

188
00:10:17,000 --> 00:10:19,000
Dat is precies hoe scanf werkt, en herinneren van vorige week

189
00:10:19,000 --> 00:10:25,000
dat is precies hoe GetString en GetInt en de andere familie van functies

190
00:10:25,000 --> 00:10:28,000
uiteindelijk werkt, zij het met een lichte variatie zoals sscanf,

191
00:10:28,000 --> 00:10:31,000
wat betekent dat scannen een string in plaats van het toetsenbord.

192
00:10:31,000 --> 00:10:33,000
Maar laten we een kijkje nemen op een beetje variantie van deze.

193
00:10:33,000 --> 00:10:37,000
In scanf2, ik eigenlijk verpest.

194
00:10:37,000 --> 00:10:42,000
Wat is er mis-en ik zal verstoppen de opmerking dat zo veel-licht

195
00:10:42,000 --> 00:10:47,000
wat is er mis met dit programma, versie 2?

196
00:10:47,000 --> 00:10:55,000
Wees als technisch mogelijk deze tijd.

197
00:10:55,000 --> 00:10:57,000
Het ziet er goed uit.

198
00:10:57,000 --> 00:11:03,000
Het is mooi ingesprongen, maar-

199
00:11:03,000 --> 00:11:07,000
oke, wat dacht je van laten we snoeien het naar beneden tot kortere vragen?

200
00:11:07,000 --> 00:11:17,000
Leiding 16. Wat is lijn 16 doet in precieze, maar technisch Engels?

201
00:11:17,000 --> 00:11:20,000
Het krijgen van een beetje lastig. Ja, Michael.

202
00:11:20,000 --> 00:11:25,000
[Student] Het is te wijzen op de eerste letter van een string.

203
00:11:25,000 --> 00:11:27,000
>> Oke, in de buurt. Laat ik tweak dat een beetje.

204
00:11:27,000 --> 00:11:33,000
Wijzend op de eerste letter van een string, bent u verklaren van een variabele genaamd buffer

205
00:11:33,000 --> 00:11:36,000
dat wijst naar het eerste adres van een string,

206
00:11:36,000 --> 00:11:39,000
of liever, zal dit punt meer specifiek op een char.

207
00:11:39,000 --> 00:11:42,000
Let op het is niet echt gericht ergens omdat er geen opdracht operator.

208
00:11:42,000 --> 00:11:46,000
Er is geen gelijkteken, dus alles wat we doen is de verdeling van de variabele genaamd buffer.

209
00:11:46,000 --> 00:11:49,000
Het gebeurt te zijn 32 bits, want het is een pointer,

210
00:11:49,000 --> 00:11:52,000
en de inhoud van buffer waarschijnlijk uiteindelijk

211
00:11:52,000 --> 00:11:57,000
bevat het adres van een char, maar voor nu, wat betekent buffer bevatten?

212
00:11:57,000 --> 00:11:59,000
Zomaar wat onzin, wie weet, wat vuilnis waarde,

213
00:11:59,000 --> 00:12:03,000
want wij hebben niet expliciet geïnitialiseerd, dus moeten we er niet van uitgaan niets.

214
00:12:03,000 --> 00:12:06,000
Oke, dus nu lijn 17 is-wat doet lijn 17 doen?

215
00:12:06,000 --> 00:12:08,000
Misschien is dat zal warm deze op.

216
00:12:08,000 --> 00:12:10,000
Hij drukt een string, toch?

217
00:12:10,000 --> 00:12:12,000
Hij drukt u String.

218
00:12:12,000 --> 00:12:15,000
>> Lijn 18 is een soort van bekende nu in dat we slechts een verschil van dit zag

219
00:12:15,000 --> 00:12:18,000
maar met een andere indeling, zodat in leiding 18

220
00:12:18,000 --> 00:12:23,000
we vertellen scanf hier is het adres van een stuk van het geheugen.

221
00:12:23,000 --> 00:12:27,000
Ik wil dat je ring in een tekenreeks, zoals geïmpliceerd door% s,

222
00:12:27,000 --> 00:12:32,000
maar het probleem is dat we niet hebben een paar dingen gedaan hier.

223
00:12:32,000 --> 00:12:35,000
Wat is een van de problemen?

224
00:12:35,000 --> 00:12:38,000
[Student] Het probeert dereference een null pointer.

225
00:12:38,000 --> 00:12:41,000
Goed, null of gewoon op een andere manier bekend pointers.

226
00:12:41,000 --> 00:12:45,000
Je overhandigen scanf een adres, maar je zei het zojuist al

227
00:12:45,000 --> 00:12:49,000
dat dit hetzelfde adres is wat vuilnis waarde, omdat we niet echt toe te wijzen aan iets,

228
00:12:49,000 --> 00:12:53,000
en dus je vertelt scanf effectief gaan hier zet een string,

229
00:12:53,000 --> 00:12:56,000
maar we weten niet waar hier nog is,

230
00:12:56,000 --> 00:12:59,000
dus we hebben niet echt toegewezen geheugen voor buffer.

231
00:12:59,000 --> 00:13:03,000
Bovendien, wat zijn je ook niet eens te vertellen scanf?

232
00:13:03,000 --> 00:13:06,000
Stel dat dit was een stuk van het geheugen, en het was geen vuilnis waarde,

233
00:13:06,000 --> 00:13:09,000
maar je bent nog steeds niet vertellen scanf iets belangrijks.

234
00:13:09,000 --> 00:13:12,000
[Student] Waar het in werkelijkheid is, het en-teken.

235
00:13:12,000 --> 00:13:15,000
Ampersand, dus in dit geval, het is oke.

236
00:13:15,000 --> 00:13:18,000
Omdat buffer is al gedeclareerd als een pointer

237
00:13:18,000 --> 00:13:22,000
met de * stuk van syntax, hoeven we niet te ampersand gebruiken

238
00:13:22,000 --> 00:13:25,000
want het is al een adres, maar ik denk dat ik hoorde hier.

239
00:13:25,000 --> 00:13:27,000
[Student] Hoe groot is het?

240
00:13:27,000 --> 00:13:29,000
Goed, we zijn niet te vertellen scanf hoe groot deze buffer is,

241
00:13:29,000 --> 00:13:32,000
wat betekent dat zelfs als buffer waren pointer,

242
00:13:32,000 --> 00:13:35,000
we zeggen scanf, zet een string hier,

243
00:13:35,000 --> 00:13:38,000
maar hier kan 2 bytes, het zou kunnen zijn 10 bytes, kan het een megabyte.

244
00:13:38,000 --> 00:13:41,000
Scanf heeft geen idee, en omdat dit is een stuk van het geheugen

245
00:13:41,000 --> 00:13:43,000
vermoedelijk, het is niet een string nog niet.

246
00:13:43,000 --> 00:13:48,000
Het is slechts een string als je eenmaal schrijven tekens en een \ 0 tot dat stuk van het geheugen.

247
00:13:48,000 --> 00:13:51,000
Nu is het gewoon een stuk van het geheugen.

248
00:13:51,000 --> 00:13:55,000
Scanf zal niet weten wanneer te stoppen met schrijven naar dat adres.

249
00:13:55,000 --> 00:13:59,000
>> Misschien herinner je je een aantal voorbeelden in het verleden waar willekeurig ik getypt op het toetsenbord

250
00:13:59,000 --> 00:14:03,000
proberen om overflow een buffer, en we spraken vrijdag over precies dat.

251
00:14:03,000 --> 00:14:07,000
Als een tegenstander injecteert een of andere manier in uw programma een veel groter woord

252
00:14:07,000 --> 00:14:10,000
of zin of zin dan je verwachtte je overspoeld

253
00:14:10,000 --> 00:14:13,000
een stuk van het geheugen, die kan slechte gevolgen hebben,

254
00:14:13,000 --> 00:14:15,000
zoals de overname van het hele programma zelf.

255
00:14:15,000 --> 00:14:17,000
We moeten een of andere manier oplossen.

256
00:14:17,000 --> 00:14:20,000
Laat me uit te zoomen en gaan in versie 3 van dit programma.

257
00:14:20,000 --> 00:14:22,000
Dat is een beetje beter.

258
00:14:22,000 --> 00:14:24,000
In deze versie, het verschil merken.

259
00:14:24,000 --> 00:14:27,000
In regel 16, ben ik weer waarbij een variabele genaamd buffer,

260
00:14:27,000 --> 00:14:29,000
maar wat is het nu?

261
00:14:29,000 --> 00:14:33,000
Het is een reeks van 16 tekens.

262
00:14:33,000 --> 00:14:36,000
Dit is goed omdat dit betekent dat ik kan nu vertellen scanf

263
00:14:36,000 --> 00:14:39,000
hier is een echte brok van het geheugen.

264
00:14:39,000 --> 00:14:42,000
U kunt bijna denken van arrays als pointers nu,

265
00:14:42,000 --> 00:14:44,000
hoewel ze niet zijn eigenlijk gelijkwaardig.

266
00:14:44,000 --> 00:14:47,000
Ze zullen zich anders gedragen in verschillende contexten.

267
00:14:47,000 --> 00:14:50,000
Maar het is zeker zo dat buffer wordt verwijst

268
00:14:50,000 --> 00:14:53,000
16 aaneengesloten tekens want dat is wat een array is

269
00:14:53,000 --> 00:14:55,000
en dat is al een paar weken.

270
00:14:55,000 --> 00:14:59,000
>> Hier, ik vertel scanf hier is een stuk van het geheugen.

271
00:14:59,000 --> 00:15:01,000
Deze keer is het eigenlijk een stuk van het geheugen,

272
00:15:01,000 --> 00:15:07,000
maar waarom is dit programma nog steeds misbruikt?

273
00:15:07,000 --> 00:15:11,000
Wat is er mis nog steeds?

274
00:15:11,000 --> 00:15:14,000
Ik heb gezegd geef me 16 bytes, maar-

275
00:15:14,000 --> 00:15:16,000
[Student] Wat als ze typen in meer dan 16?

276
00:15:16,000 --> 00:15:20,000
Precies, wat als de gebruiker typt in 17 tekens of 1700 tekens?

277
00:15:20,000 --> 00:15:23,000
In feite, laten we eens kijken of we er niet over struikelen deze fout nu.

278
00:15:23,000 --> 00:15:25,000
Het is beter, maar niet perfect.

279
00:15:25,000 --> 00:15:28,000
Laat me gaan en lopen te maken scanf3 om dit programma te compileren.

280
00:15:28,000 --> 00:15:34,000
Laat me lopen scanf3, String alsjeblieft: hallo, en we lijken wel goed.

281
00:15:34,000 --> 00:15:37,000
Laat me proberen een iets langere een, hello there.

282
00:15:37,000 --> 00:15:42,000
Oke, laten we het doen hello there hoe gaat het vandaag, op Enter.

283
00:15:42,000 --> 00:15:54,000
Aan de vorm van geluk hier, laten we zeggen hello there how are you.

284
00:15:54,000 --> 00:15:56,000
Verdomme.

285
00:15:56,000 --> 00:16:03,000
Oke, dus we hadden geluk. Laten we eens kijken of we niet oplossen.

286
00:16:03,000 --> 00:16:06,000
Nee, het is niet gaan om mij te laten kopiëren.

287
00:16:06,000 --> 00:16:09,000
Laten we het opnieuw proberen.

288
00:16:09,000 --> 00:16:12,000
Oke, stand-by.

289
00:16:12,000 --> 00:16:20,000
We zullen zien hoe lang ik kan doen alsof om zich te concentreren, terwijl nog steeds om dit te doen.

290
00:16:20,000 --> 00:16:23,000
Verdomme. Dat is nogal geval, eigenlijk.

291
00:16:23,000 --> 00:16:26,000
Daar gaan we dan.

292
00:16:26,000 --> 00:16:30,000
Punt gemaakt.

293
00:16:30,000 --> 00:16:34,000
>> Dit gênant hoewel het ook is, het is ook een van de bronnen van grote verwarring

294
00:16:34,000 --> 00:16:38,000
bij het schrijven van programma's die bugs hebben, omdat zij zich manifesteren

295
00:16:38,000 --> 00:16:40,000
slechts een keer in de zoveel tijd wel eens.

296
00:16:40,000 --> 00:16:43,000
De realiteit is dat zelfs als uw code volledig is gebroken,

297
00:16:43,000 --> 00:16:46,000
het kan slechts eenmaal volledig gebroken tijd

298
00:16:46,000 --> 00:16:49,000
want soms, in wezen wat er gebeurt is het besturingssysteem wijst

299
00:16:49,000 --> 00:16:52,000
een beetje meer geheugen dan je eigenlijk nodig hebt om wat voor reden dan ook,

300
00:16:52,000 --> 00:16:57,000
en dus niemand anders gebruikt het geheugen direct na uw stuk van 16 tekens,

301
00:16:57,000 --> 00:17:01,000
dus als je naar 17, 18, 19, wat dan ook, het is niet zo'n big deal.

302
00:17:01,000 --> 00:17:04,000
Nu, de computer, zelfs als het niet crashen op dat moment,

303
00:17:04,000 --> 00:17:09,000
zou byte nummer 17 of 18 of 19 eventueel te gebruiken voor iets anders,

304
00:17:09,000 --> 00:17:14,000
op welk punt je gegevens die je daar te zetten, zij het veel te lange,

305
00:17:14,000 --> 00:17:18,000
gaat om potentieel overschreven door een andere functie.

306
00:17:18,000 --> 00:17:21,000
Het is niet per se zal intact blijven,

307
00:17:21,000 --> 00:17:23,000
maar het zal niet noodzakelijk leiden tot een seg fout.

308
00:17:23,000 --> 00:17:26,000
Maar in dit geval, heb ik eindelijk mits voldoende karakters

309
00:17:26,000 --> 00:17:29,000
dat ik in wezen overtrof mijn segment van het geheugen, en bam,

310
00:17:29,000 --> 00:17:33,000
het besturingssysteem zei: "Sorry, dat is niet goed, segmentation fault."

311
00:17:33,000 --> 00:17:38,000
>> En laten we nu zien of wat blijft hier in mijn directory-

312
00:17:38,000 --> 00:17:40,000
merk dat ik dit bestand hier hebben, kern.

313
00:17:40,000 --> 00:17:42,000
Merk op dat dit weer is een core dump genoemd.

314
00:17:42,000 --> 00:17:46,000
Het is in wezen een bestand dat de inhoud van het geheugen van uw programma's bevat

315
00:17:46,000 --> 00:17:48,000
op het punt waar het neerstortte,

316
00:17:48,000 --> 00:17:51,000
en alleen maar om een ​​klein voorbeeld hier proberen laat me gaan hier

317
00:17:51,000 --> 00:17:57,000
en uit te voeren gdb op scanf3 en geef vervolgens een derde argument genoemd kern,

318
00:17:57,000 --> 00:18:01,000
en hier opmerken dat als ik een lijst van de code,

319
00:18:01,000 --> 00:18:06,000
zullen we in staat zoals gebruikelijk met gdb om te beginnen met een wandeling door dit programma,

320
00:18:06,000 --> 00:18:10,000
en ik kan draaien en zodra ik hit-als bij de stap commando in gdb-

321
00:18:10,000 --> 00:18:13,000
zodra ik raakte de potentieel buggy lijn na het typen in een enorme reeks,

322
00:18:13,000 --> 00:18:16,000
Ik zal in staat zijn om daadwerkelijk hier identificeren.

323
00:18:16,000 --> 00:18:19,000
Meer over dit, hoewel, in rubriek in termen van core dumps

324
00:18:19,000 --> 00:18:22,000
en dergelijke, zodat je daadwerkelijk kunt binnen steken rond de core dump

325
00:18:22,000 --> 00:18:27,000
en te zien op welke lijn het programma dat u gefaald.

326
00:18:27,000 --> 00:18:32,000
Hebt u vragen dan op aanwijzingen en op adressen?

327
00:18:32,000 --> 00:18:36,000
Want vandaag op, we gaan om te beginnen met het nemen van uit dat deze dingen bestaan

328
00:18:36,000 --> 00:18:40,000
en we weten precies wat ze zijn.

329
00:18:40,000 --> 00:18:42,000
Ja.

330
00:18:42,000 --> 00:18:46,000
>> [Student] Hoe komt het dat je niet hoeft om een ​​ampersand zetten naast de part-

331
00:18:46,000 --> 00:18:48,000
Goede vraag.

332
00:18:48,000 --> 00:18:51,000
Hoe komt het dat ik niet hoefde te een ampersand zetten naast de karakter array als ik eerder

333
00:18:51,000 --> 00:18:53,000
met de meeste van onze voorbeelden?

334
00:18:53,000 --> 00:18:55,000
Het korte antwoord is arrays zijn een beetje speciaal.

335
00:18:55,000 --> 00:18:59,000
U kunt ook een buffer bijna denken als daadwerkelijk een adres,

336
00:18:59,000 --> 00:19:03,000
en het gewoon zo gebeurt het geval te zijn, dat het plein haakjesnotering

337
00:19:03,000 --> 00:19:06,000
is een gemak, zodat we kunnen gaan in de houder 0, beugel 1,

338
00:19:06,000 --> 00:19:10,000
draagconstructie 2, zonder de * notatie.

339
00:19:10,000 --> 00:19:13,000
Dat is een beetje een leugentje om bestwil, omdat arrays en pointers

340
00:19:13,000 --> 00:19:17,000
zijn in feite iets anders, maar ze kunnen vaak maar niet altijd elkaar worden gebruikt.

341
00:19:17,000 --> 00:19:21,000
Kortom, wanneer een functie wordt verwacht een pointer naar een stuk van het geheugen,

342
00:19:21,000 --> 00:19:24,000
kunt u ofwel het doorgeven van een adres dat werd geretourneerd door malloc,

343
00:19:24,000 --> 00:19:29,000
en we zullen weer te zien malloc het duurde niet lang, of u kunt doorgeven van de naam van een array.

344
00:19:29,000 --> 00:19:32,000
Je hoeft niet te ampersand maken met arrays omdat ze al

345
00:19:32,000 --> 00:19:34,000
wezen als adressen.

346
00:19:34,000 --> 00:19:36,000
Dat is de enige uitzondering.

347
00:19:36,000 --> 00:19:39,000
De vierkante haken ze speciaal.

348
00:19:39,000 --> 00:19:41,000
>> Kon je een ampersand naast de buffer?

349
00:19:41,000 --> 00:19:43,000
In dit geval niet.

350
00:19:43,000 --> 00:19:46,000
Dat zou niet werken, omdat, nogmaals, van deze hoek zaak

351
00:19:46,000 --> 00:19:49,000
waar arrays zijn niet helemaal eigenlijk adressen.

352
00:19:49,000 --> 00:19:54,000
Maar we zullen nog even op dat het duurde niet lang met andere voorbeelden.

353
00:19:54,000 --> 00:19:56,000
Laten we proberen om hier een probleem op te lossen.

354
00:19:56,000 --> 00:20:00,000
We hebben een data structuur die we hebben gebruikt voor enige tijd bekend als een array.

355
00:20:00,000 --> 00:20:02,000
Case in point, dat is wat we net hadden.

356
00:20:02,000 --> 00:20:04,000
Maar arrays hebben een aantal positieve kanten en nadelen.

357
00:20:04,000 --> 00:20:06,000
Arrays zijn leuk waarom?

358
00:20:06,000 --> 00:20:11,000
Wat is een ding dat u wilt-in de mate je arrays-over arrays?

359
00:20:11,000 --> 00:20:13,000
Wat is handig over hen? Wat is er dwingende?

360
00:20:13,000 --> 00:20:18,000
Waarom hebben we introduceren ze in de eerste plaats?

361
00:20:18,000 --> 00:20:20,000
Ja.

362
00:20:20,000 --> 00:20:27,000
[Student] Ze kunnen heel wat gegevens op te slaan, en je hoeft niet een hele ding te gebruiken.

363
00:20:27,000 --> 00:20:29,000
U kunt gebruik maken van een sectie.

364
00:20:29,000 --> 00:20:32,000
Goed, met een scala kunt u veel gegevens op te slaan,

365
00:20:32,000 --> 00:20:35,000
en je hoeft niet per se om alles te gebruiken, zodat u kunt overallocate,

366
00:20:35,000 --> 00:20:39,000
die misschien handig als je niet weet op voorhand hoeveel van iets te verwachten.

367
00:20:39,000 --> 00:20:41,000
>> GetString is een perfect voorbeeld.

368
00:20:41,000 --> 00:20:44,000
GetString, geschreven door ons, heeft geen idee hoeveel tekens te verwachten,

369
00:20:44,000 --> 00:20:48,000
dus het feit dat we kunnen stukken aaneengesloten geheugen toe te wijzen is goed.

370
00:20:48,000 --> 00:20:51,000
Arrays ook het oplossen van een probleem zagen we een paar weken geleden

371
00:20:51,000 --> 00:20:54,000
waar je begint te evolueren in iets heel slecht ontworpen.

372
00:20:54,000 --> 00:20:57,000
Bedenk dat ik een student structuur genaamd David gemaakt,

373
00:20:57,000 --> 00:21:00,000
en toen dat was eigenlijk een alternatief, hoewel,

374
00:21:00,000 --> 00:21:04,000
aan het hebben van een variabele genaamd naam en een andere variabele met de naam, denk ik, huis,

375
00:21:04,000 --> 00:21:08,000
en een andere variabele met de naam ID want in dat verhaal dat ik toen wilde iets anders te introduceren

376
00:21:08,000 --> 00:21:11,000
zoals Rob in het programma, dus toen besloot ik wacht eens even,

377
00:21:11,000 --> 00:21:13,000
Ik moet deze variabelen hernoemen.

378
00:21:13,000 --> 00:21:16,000
Laten we de mijne name1, ID1, House1.

379
00:21:16,000 --> 00:21:20,000
Laten we Rob's naam2, house2, ID2.

380
00:21:20,000 --> 00:21:22,000
Maar wacht eens even, hoe zit het met Tommy?

381
00:21:22,000 --> 00:21:24,000
Dan hebben we nog drie variabelen.

382
00:21:24,000 --> 00:21:27,000
We introduceerden iemand anders, vier sets van variabelen.

383
00:21:27,000 --> 00:21:30,000
De wereld begon te krijgen rommelig zeer snel,

384
00:21:30,000 --> 00:21:33,000
dus introduceerden we structs, en wat is meeslepend over een struct?

385
00:21:33,000 --> 00:21:39,000
Wat doet een C struct laten doen?

386
00:21:39,000 --> 00:21:42,000
Het is echt lastig vandaag.

387
00:21:42,000 --> 00:21:44,000
Wat is er? >> [Onverstaanbaar student reactie]

388
00:21:44,000 --> 00:21:47,000
Ja, in het bijzonder, typedef stelt u in staat om een ​​nieuwe data type,

389
00:21:47,000 --> 00:21:51,000
en struct, de struct trefwoord, kunt u in te kapselen om

390
00:21:51,000 --> 00:21:54,000
conceptueel gerelateerd stukjes data samen

391
00:21:54,000 --> 00:21:56,000
en daarna noemen ze zoiets als een student.

392
00:21:56,000 --> 00:21:58,000
>> Dat was goed, want nu kunnen we modelleren

393
00:21:58,000 --> 00:22:03,000
veel meer soort van conceptueel consequent de notie van een student in een variabele

394
00:22:03,000 --> 00:22:07,000
niet willekeurig met een voor een tekenreeks, een voor een ID, enzovoort.

395
00:22:07,000 --> 00:22:10,000
Arrays zijn leuk omdat ze ons in staat stellen om te beginnen met het opruimen van onze code.

396
00:22:10,000 --> 00:22:13,000
Maar wat is een nadeel nu van een array?

397
00:22:13,000 --> 00:22:15,000
Wat kun je niet doen? Ja.

398
00:22:15,000 --> 00:22:17,000
[Student] Je moet weten hoe groot het is.

399
00:22:17,000 --> 00:22:19,000
Je moet weten hoe groot het is, dus het is een beetje vervelend.

400
00:22:19,000 --> 00:22:21,000
Degenen onder jullie met voorafgaande programmeerervaring weten dat in een groot aantal talen,

401
00:22:21,000 --> 00:22:24,000
zoals Java, kunt u vragen een stuk van het geheugen, in het bijzonder een array,

402
00:22:24,000 --> 00:22:28,000
hoe groot bent u, met een lengte, onroerend goed, zo te zeggen, en dat is echt handig.

403
00:22:28,000 --> 00:22:32,000
In C kun je niet eens bellen strlen op een generieke reeks

404
00:22:32,000 --> 00:22:35,000
omdat strlen, zoals het woord al zegt, is alleen voor strijkers,

405
00:22:35,000 --> 00:22:39,000
en je kunt achterhalen van de lengte van een string als gevolg van deze menselijke conventie

406
00:22:39,000 --> 00:22:43,000
van het hebben van een \ 0, maar een array, meer in het algemeen, is slechts een deel van het geheugen.

407
00:22:43,000 --> 00:22:46,000
Als het een array van ints, is er niet van plan om een ​​aantal speciale tekens worden

408
00:22:46,000 --> 00:22:48,000
aan het eind voor u klaar.

409
00:22:48,000 --> 00:22:50,000
U de lengte van een array onthouden.

410
00:22:50,000 --> 00:22:54,000
Een ander nadeel van een array stak de kop in getString zelf.

411
00:22:54,000 --> 00:22:59,000
Wat is een ander nadeel van een array?

412
00:22:59,000 --> 00:23:01,000
Meneer, alleen jij en ik vandaag.

413
00:23:01,000 --> 00:23:04,000
[Onverstaanbaar student reactie] >> Het is wat?

414
00:23:04,000 --> 00:23:06,000
Het is verklaard op de stapel.

415
00:23:06,000 --> 00:23:09,000
Oke, verklaarde op de stapel. Waarom ga je niet zo?

416
00:23:09,000 --> 00:23:13,000
[Student] Omdat het wordt hergebruikt.

417
00:23:13,000 --> 00:23:15,000
Het wordt hergebruikt.

418
00:23:15,000 --> 00:23:18,000
Oke, als je gebruik maken van een array om geheugen toe te wijzen,

419
00:23:18,000 --> 00:23:21,000
je kunt niet, bijvoorbeeld, terug te sturen omdat het op de stapel.

420
00:23:21,000 --> 00:23:23,000
Oke, dat is een nadeel.

421
00:23:23,000 --> 00:23:25,000
En wat te denken van een ander met een array?

422
00:23:25,000 --> 00:23:28,000
Zodra u toewijzen, je bent een soort van geschroefd als u meer ruimte nodig

423
00:23:28,000 --> 00:23:30,000
dan array.

424
00:23:30,000 --> 00:23:34,000
>> Dan hebben we geïntroduceerd, recall, malloc, die gaf ons de mogelijkheid om dynamisch geheugen toewijzen.

425
00:23:34,000 --> 00:23:37,000
Maar wat als we probeerden een andere wereld bij elkaar?

426
00:23:37,000 --> 00:23:40,000
Wat als we wilden een paar van die problemen op te lossen

427
00:23:40,000 --> 00:23:45,000
dus we plaats-mijn pen is in slaap gevallen hier-

428
00:23:45,000 --> 00:23:51,000
wat als we in plaats daarvan wilden wezen een wereld die niet langer is zoals dit?

429
00:23:51,000 --> 00:23:56,000
Dit is een array, en, natuurlijk, dergelijke verslechtert wanneer we het einde van de array raken,

430
00:23:56,000 --> 00:24:00,000
en ik heb nu niet meer ruimte voor een ander geheel getal of een ander teken.

431
00:24:00,000 --> 00:24:03,000
Wat als we soort van preventief wel zeggen, waarom we niet te ontspannen

432
00:24:03,000 --> 00:24:07,000
deze eis dat al deze delen van het geheugen aaneengesloten zijn rug aan rug,

433
00:24:07,000 --> 00:24:10,000
en waarom niet, als ik moet een int of een char,

434
00:24:10,000 --> 00:24:12,000
Geef me ruimte voor een van hen?

435
00:24:12,000 --> 00:24:14,000
En als ik een andere nodig hebt, geef me nog een ruimte,

436
00:24:14,000 --> 00:24:16,000
en als ik een andere nodig hebt, geef me nog een ruimte.

437
00:24:16,000 --> 00:24:19,000
Het voordeel daarvan is nu dat als iemand

438
00:24:19,000 --> 00:24:21,000
neemt het geheugen hier, geen big deal.

439
00:24:21,000 --> 00:24:25,000
Ik neem deze extra stuk van het geheugen hier en dan is dit een.

440
00:24:25,000 --> 00:24:28,000
>> Nu, de enige vangst is dat dit bijna voelt alsof ik

441
00:24:28,000 --> 00:24:30,000
een hele hoop verschillende variabelen.

442
00:24:30,000 --> 00:24:33,000
Dit voelt als vijf verschillende variabelen mogelijk.

443
00:24:33,000 --> 00:24:36,000
Maar wat als we stelen een idee van strings

444
00:24:36,000 --> 00:24:41,000
waarbij we een of andere manier met elkaar te verbinden deze dingen conceptueel, en wat als ik dit deed?

445
00:24:41,000 --> 00:24:44,000
Dit is mijn zeer slecht opgesteld pijl.

446
00:24:44,000 --> 00:24:46,000
Maar stel dat elk van deze delen van het geheugen

447
00:24:46,000 --> 00:24:52,000
wees naar de andere, en deze kerel, die geen broer of zus aan zijn recht,

448
00:24:52,000 --> 00:24:54,000
geen dergelijke pijl.

449
00:24:54,000 --> 00:24:56,000
Dit is in feite wat heet een gelinkte lijst.

450
00:24:56,000 --> 00:25:00,000
Dit is een nieuwe datastructuur die ons in staat stelt toe te wijzen een stuk van het geheugen,

451
00:25:00,000 --> 00:25:03,000
toen nog een, en nog een, en nog een, elke keer als we willen

452
00:25:03,000 --> 00:25:07,000
tijdens een programma, en we bedenken dat ze allemaal een of andere manier verbonden

453
00:25:07,000 --> 00:25:11,000
door letterlijk chaining ze samen, en we deden dat picturaal hier met een pijl.

454
00:25:11,000 --> 00:25:15,000
Maar in code, wat zou het zijn het mechanisme via welke je zou kunnen een of andere manier aan te sluiten,

455
00:25:15,000 --> 00:25:20,000
bijna als Scratch, een brok naar de andere brok?

456
00:25:20,000 --> 00:25:22,000
We konden gebruik maken van een pointer, toch?

457
00:25:22,000 --> 00:25:25,000
Want echt op de pijl die gaat vanuit de linkerbovenhoek plein,

458
00:25:25,000 --> 00:25:31,000
deze man hier om deze, binnen kon bevatten van dit plein

459
00:25:31,000 --> 00:25:34,000
niet zomaar een ints, niet zomaar een char, maar wat als ik eigenlijk toegewezen

460
00:25:34,000 --> 00:25:37,000
een beetje extra ruimte, zodat nu,

461
00:25:37,000 --> 00:25:41,000
elk van mijn delen van het geheugen, ook al is dit gaat me kosten,

462
00:25:41,000 --> 00:25:45,000
Nu er een beetje meer rechthoekige waarbij een van de delen van het geheugen

463
00:25:45,000 --> 00:25:47,000
wordt gebruikt voor een aantal, zoals het getal 1,

464
00:25:47,000 --> 00:25:50,000
en dan als deze kerel slaat het nummer 2,

465
00:25:50,000 --> 00:25:52,000
dit andere deel van het geheugen wordt gebruikt voor een pijl,

466
00:25:52,000 --> 00:25:54,000
of meer concreet, een pointer.

467
00:25:54,000 --> 00:25:59,000
En stel dat ik de nummer 3 op te slaan hier, terwijl ik gebruik deze om te wijzen op die vent,

468
00:25:59,000 --> 00:26:02,000
en nu deze man, laten we aannemen dat ik maar drie van zulke delen van het geheugen wilt.

469
00:26:02,000 --> 00:26:05,000
Ik trek een lijn door dat aan te geven null.

470
00:26:05,000 --> 00:26:07,000
Er is geen extra karakter.

471
00:26:07,000 --> 00:26:10,000
>> Inderdaad, dit is hoe we kunnen gaan over het implementeren

472
00:26:10,000 --> 00:26:12,000
iets dat heet een gekoppelde lijst.

473
00:26:12,000 --> 00:26:18,000
Een gelinkte lijst is een nieuwe datastructuur, en het is een opstap naar

474
00:26:18,000 --> 00:26:21,000
veel liefhebber datastructuren die beginnen om problemen op te lossen

475
00:26:21,000 --> 00:26:23,000
langs de lijnen van Facebook-type problemen en Google-type problemen

476
00:26:23,000 --> 00:26:26,000
waar je enorme datasets en het niet langer snijdt het

477
00:26:26,000 --> 00:26:29,000
om aansluitend op te slaan alles en gebruiken iets als lineair zoeken

478
00:26:29,000 --> 00:26:31,000
of zelfs zoiets als binaire zoekopdracht.

479
00:26:31,000 --> 00:26:33,000
U wilt nog beter looptijden.

480
00:26:33,000 --> 00:26:37,000
In feite, een van de heilige Grails we praten over later deze week of volgende

481
00:26:37,000 --> 00:26:41,000
is een algoritme waarvan looptijd constant is.

482
00:26:41,000 --> 00:26:44,000
In andere woorden, het is altijd dezelfde hoeveelheid tijd ongeacht

483
00:26:44,000 --> 00:26:47,000
hoe groot de ingang is, en dat zou inderdaad dwingende,

484
00:26:47,000 --> 00:26:49,000
meer nog dan iets logaritmisch.

485
00:26:49,000 --> 00:26:51,000
Wat is dit op het scherm hier?

486
00:26:51,000 --> 00:26:55,000
Elk van de rechthoeken is precies wat ik net getekend met de hand.

487
00:26:55,000 --> 00:26:59,000
Maar het ding helemaal aan de linkerkant is een speciale variabele.

488
00:26:59,000 --> 00:27:02,000
Het gaat om een ​​enkele wijzer zijn, omdat het een gotcha

489
00:27:02,000 --> 00:27:04,000
met een gekoppelde lijst, als deze dingen worden genoemd,

490
00:27:04,000 --> 00:27:09,000
is dat je om op te hangen op het ene uiteinde van de gekoppelde lijst.

491
00:27:09,000 --> 00:27:13,000
>> Net als bij een string, moet u het adres van de eerste char te leren kennen.

492
00:27:13,000 --> 00:27:15,000
Dezelfde deal voor gelinkte lijsten.

493
00:27:15,000 --> 00:27:19,000
Je moet het adres van de eerste deel van het geheugen weten

494
00:27:19,000 --> 00:27:25,000
want van daaruit kunt u bij elke andere.

495
00:27:25,000 --> 00:27:27,000
Downside.

496
00:27:27,000 --> 00:27:30,000
Welke prijs betalen we voor deze veelzijdigheid van het hebben van een dynamisch

497
00:27:30,000 --> 00:27:34,000
omvangrijke data structuur dat als we ooit behoefte aan meer geheugen, fijn,

498
00:27:34,000 --> 00:27:37,000
slechts toe te wijzen nog een stuk en trek een aanwijzer van

499
00:27:37,000 --> 00:27:39,000
de oude naar de nieuwe staart van de lijst?

500
00:27:39,000 --> 00:27:41,000
Ja.

501
00:27:41,000 --> 00:27:43,000
[Student] Het duurt ongeveer twee keer zo veel ruimte.

502
00:27:43,000 --> 00:27:45,000
Het duurt twee keer zo veel ruimte, zodat zeker een nadeel, en we hebben gezien dit

503
00:27:45,000 --> 00:27:48,000
afweging voor tussen tijd en ruimte en flexibiliteit

504
00:27:48,000 --> 00:27:51,000
indien nu moeten we niet 32 ​​bits voor elk van deze nummers.

505
00:27:51,000 --> 00:27:57,000
We moeten echt 64, 32 voor het aantal en de 32 voor de aanwijzer.

506
00:27:57,000 --> 00:27:59,000
Maar hey, ik heb 2 gigabyte aan RAM-geheugen.

507
00:27:59,000 --> 00:28:02,000
Het toevoegen van een andere 32 bits hier en hier lijkt niet zo groot van een deal.

508
00:28:02,000 --> 00:28:05,000
Maar voor grote datasets, het voegt zeker tot letterlijk twee keer zo veel.

509
00:28:05,000 --> 00:28:09,000
Wat is een ander nadeel nu, of wat functie geven we op,

510
00:28:09,000 --> 00:28:12,000
Als wij vertegenwoordigen lijsten van dingen met een gekoppelde lijst en geen array?

511
00:28:12,000 --> 00:28:14,000
[Student] U kunt niet achteruit doorkruisen het.

512
00:28:14,000 --> 00:28:16,000
Je kunt het niet naar achteren doorlopen, dus je bent soort geschroefd als je loopt

513
00:28:16,000 --> 00:28:19,000
van links naar rechts met behulp van een for-lus of een while-lus

514
00:28:19,000 --> 00:28:21,000
en dan realiseer je je: "O, ik wil om terug te gaan naar het begin van de lijst."

515
00:28:21,000 --> 00:28:26,000
U niet omdat deze pointers alleen van links naar rechts de pijlen.

516
00:28:26,000 --> 00:28:29,000
>> Nu, je zou het begin van de lijst onthouden met een andere variabele,

517
00:28:29,000 --> 00:28:31,000
maar dat is een complexiteit om in gedachten te houden.

518
00:28:31,000 --> 00:28:35,000
Een array, maakt niet uit hoe ver je gaat, kun je altijd doen min, min, min, min

519
00:28:35,000 --> 00:28:37,000
en terug te gaan naar waar je vandaan komt.

520
00:28:37,000 --> 00:28:40,000
Wat is een ander nadeel hier? Ja.

521
00:28:40,000 --> 00:28:43,000
[Onverstaanbaar student vraag]

522
00:28:43,000 --> 00:28:47,000
Je kon, dus je hebt eigenlijk alleen maar voorgesteld een gegevensstructuur genaamd een dubbel gelinkte lijst,

523
00:28:47,000 --> 00:28:50,000
en inderdaad, je zou een andere aanwijzer toe te voegen aan elk van deze rechthoeken

524
00:28:50,000 --> 00:28:53,000
dat gaat de andere richting, de bovenkant waarvan

525
00:28:53,000 --> 00:28:55,000
is nu kun je doorkruisen heen en weer,

526
00:28:55,000 --> 00:28:59,000
de keerzijde van dat nu je gebruikt drie keer zoveel geheugen als we vroeger

527
00:28:59,000 --> 00:29:04,000
en ook het toevoegen van complexiteit in termen van de code die u moet schrijven om het goed te krijgen.

528
00:29:04,000 --> 00:29:08,000
Maar deze zijn misschien redelijke compromissen, indien de terugname belangrijker.

529
00:29:08,000 --> 00:29:10,000
Ja.

530
00:29:10,000 --> 00:29:12,000
[Student] U kunt niet over een 2D-gelinkte lijst.

531
00:29:12,000 --> 00:29:16,000
Goed, kun je niet echt een 2D-gelinkte lijst.

532
00:29:16,000 --> 00:29:18,000
Je zou kunnen. Het is niet zo eenvoudig als een array.

533
00:29:18,000 --> 00:29:21,000
Net als een array, je doet open beugel, gesloten beugel, open beugel, gesloten beugel,

534
00:29:21,000 --> 00:29:23,000
en je krijgt een aantal 2-dimensionale structuur.

535
00:29:23,000 --> 00:29:26,000
Je kon implementeren van een 2-dimensionale verbonden lijst

536
00:29:26,000 --> 00:29:29,000
als je add-zoals u voorgesteld-derde wijzer naar elk van deze dingen,

537
00:29:29,000 --> 00:29:34,000
en als je na te denken over een andere lijst komt op je 3D-stijl

538
00:29:34,000 --> 00:29:40,000
van het scherm voor ons allen, dat is gewoon een keten van een soort.

539
00:29:40,000 --> 00:29:45,000
We kunnen het doen, maar het is niet zo eenvoudig als het typen van open beugel, vierkant haakje. Ja.

540
00:29:45,000 --> 00:29:48,000
[Onverstaanbaar student vraag]

541
00:29:48,000 --> 00:29:50,000
Goed, dus dit is een echte kicker.

542
00:29:50,000 --> 00:29:54,000
>> Deze algoritmen die we hebben kwijnde over, net als oh, binair zoeken,

543
00:29:54,000 --> 00:29:57,000
u kunt zoeken een reeks van nummers op het bord

544
00:29:57,000 --> 00:30:01,000
of een telefoonboek zo veel sneller als u verdeel en heers

545
00:30:01,000 --> 00:30:05,000
en een binaire zoekalgoritme, maar binaire zoekopdracht vereiste twee veronderstellingen.

546
00:30:05,000 --> 00:30:09,000
Een, dat de gegevens zijn gesorteerd.

547
00:30:09,000 --> 00:30:11,000
Nu kunnen we vermoedelijk houden deze gesorteerd,

548
00:30:11,000 --> 00:30:14,000
dus misschien is dat geen probleem, maar binaire zoekopdracht ook aangenomen

549
00:30:14,000 --> 00:30:18,000
u had willekeurige toegang tot de lijst met nummers

550
00:30:18,000 --> 00:30:21,000
en een reeks kunt u over random access, en door random access,

551
00:30:21,000 --> 00:30:24,000
Ik bedoel als je een array, hoeveel tijd kost het u

552
00:30:24,000 --> 00:30:26,000
om naar beugel 0?

553
00:30:26,000 --> 00:30:29,000
Een bewerking, u gewoon gebruik maken van [0] en je bent daar.

554
00:30:29,000 --> 00:30:33,000
Hoeveel stappen duurt het om naar locatie 10?

555
00:30:33,000 --> 00:30:36,000
Een stap, je gewoon naar [10] en je daar bent.

556
00:30:36,000 --> 00:30:40,000
Daarentegen, hoe kom je aan de 10e geheel getal in een gekoppelde lijst?

557
00:30:40,000 --> 00:30:42,000
Je moet beginnen bij het begin, omdat je alleen herinneren

558
00:30:42,000 --> 00:30:45,000
het begin van een gekoppelde lijst, net als een string wordt herinnerd

559
00:30:45,000 --> 00:30:48,000
door het adres van de eerste char, en vinden dat 10e int

560
00:30:48,000 --> 00:30:53,000
of dat 10e teken in een string, moet je de hele verdomde ding te zoeken.

561
00:30:53,000 --> 00:30:55,000
>> Nogmaals, we zijn niet het oplossen van al onze problemen.

562
00:30:55,000 --> 00:31:00,000
Introduceren we nieuwe, maar het is echt afhankelijk van wat je probeert te ontwerpen voor.

563
00:31:00,000 --> 00:31:04,000
In termen van de uitvoering van deze, kunnen we een idee lenen van die student structuur.

564
00:31:04,000 --> 00:31:07,000
De syntax is zeer vergelijkbaar, behalve nu, het idee is een beetje meer abstracte

565
00:31:07,000 --> 00:31:09,000
dan huis en naam en ID.

566
00:31:09,000 --> 00:31:13,000
Maar ik stel voor dat we een datastructuur in C hebben

567
00:31:13,000 --> 00:31:17,000
dat heet knooppunt, als het laatste woord op de dia al doet vermoeden,

568
00:31:17,000 --> 00:31:21,000
binnenkant van een knooppunt, en een knooppunt is gewoon een generieke container in de informatica.

569
00:31:21,000 --> 00:31:25,000
Het wordt meestal getekend als een cirkel of een vierkant of rechthoek als we hebben gedaan.

570
00:31:25,000 --> 00:31:27,000
En in deze gegevensstructuur hebben we een int, n,

571
00:31:27,000 --> 00:31:29,000
dus dat is het nummer dat ik wil opslaan.

572
00:31:29,000 --> 00:31:36,000
Maar wat is deze tweede lijn, struct knoop * volgende?

573
00:31:36,000 --> 00:31:40,000
Waarom is dit juist is, of welke rol speelt dit ding te spelen,

574
00:31:40,000 --> 00:31:42,000
ook al is het een beetje cryptisch op het eerste gezicht?

575
00:31:42,000 --> 00:31:44,000
Ja.

576
00:31:44,000 --> 00:31:46,000
[Onverstaanbaar student reactie]

577
00:31:46,000 --> 00:31:50,000
Precies, dus de * soort buit dat het een pointer van een soort.

578
00:31:50,000 --> 00:31:53,000
De naam van deze wijzer is willekeurig volgende,

579
00:31:53,000 --> 00:32:00,000
maar we konden noemen het alles wat we willen, maar wat betekent dit pointer wijst u?

580
00:32:00,000 --> 00:32:03,000
[Student] Een andere node. >> Precies, het wijst op nog zo'n knooppunt.

581
00:32:03,000 --> 00:32:05,000
>> Nu, dit is een soort nieuwsgierigheid van C.

582
00:32:05,000 --> 00:32:09,000
Bedenk dat C wordt gelezen door een compiler boven naar beneden, links naar rechts,

583
00:32:09,000 --> 00:32:13,000
wat betekent dat als-dit is een weinig verschillend van wat we hebben gedaan met de student.

584
00:32:13,000 --> 00:32:16,000
Wanneer we een student gedefinieerd, hebben we eigenlijk niet daar legde een woord.

585
00:32:16,000 --> 00:32:18,000
Het is gewoon gezegd typedef.

586
00:32:18,000 --> 00:32:20,000
Dan hadden we int id, string naam, string huis,

587
00:32:20,000 --> 00:32:23,000
en student onderaan de struct.

588
00:32:23,000 --> 00:32:26,000
Deze verklaring is een beetje anders, omdat,

589
00:32:26,000 --> 00:32:28,000
nogmaals, de C-compiler is een beetje dom.

590
00:32:28,000 --> 00:32:30,000
Het wordt alleen maar om te lezen van boven naar beneden,

591
00:32:30,000 --> 00:32:33,000
dus als het bereiken van de 2e lijn hier

592
00:32:33,000 --> 00:32:37,000
waar naast wordt verklaard en het ziet, oh, hier is een variabele genaamd volgende.

593
00:32:37,000 --> 00:32:39,000
Het is een pointer naar een struct node.

594
00:32:39,000 --> 00:32:42,000
De compiler gaat beseffen wat is een struct knoop?

595
00:32:42,000 --> 00:32:44,000
Ik heb nog nooit gehoord van deze zaak voor,

596
00:32:44,000 --> 00:32:47,000
omdat het woord knooppunt anders niet zouden worden weergegeven

597
00:32:47,000 --> 00:32:49,000
tot de bodem, zodat er deze redundantie.

598
00:32:49,000 --> 00:32:53,000
Je moet struct knoop hier zeggen, die u vervolgens kunt verkorten later

599
00:32:53,000 --> 00:32:56,000
dankzij typedef hier beneden, maar dit komt doordat

600
00:32:56,000 --> 00:33:02,000
we verwijzen naar de structuur zelf binnenzijde van de constructie.

601
00:33:02,000 --> 00:33:05,000
Dat is de enige gotcha daar.

602
00:33:05,000 --> 00:33:07,000
>> Een aantal interessante problemen zullen ontstaan.

603
00:33:07,000 --> 00:33:09,000
We hebben een lijst met getallen. Hoe kunnen we in te voegen in het?

604
00:33:09,000 --> 00:33:11,000
Hoe zoeken we het? Hoe kunnen we verwijderen van?

605
00:33:11,000 --> 00:33:13,000
Zeker nu dat we al deze pointers te beheren.

606
00:33:13,000 --> 00:33:15,000
Je dacht dat pointers waren soort van mind-bending

607
00:33:15,000 --> 00:33:17,000
als je had een van hen alleen maar proberen om een ​​int lezen om het te.

608
00:33:17,000 --> 00:33:20,000
Nu moeten we een hele lijst is de moeite waard te manipuleren.

609
00:33:20,000 --> 00:33:22,000
Waarom gaan we niet hier nemen onze 5-minuten pauze, en dan zullen we brengen

610
00:33:22,000 --> 00:33:34,000
sommige mensen op het podium om precies dat te doen.

611
00:33:34,000 --> 00:33:36,000
>> C is veel leuker als het nagespeeld.

612
00:33:36,000 --> 00:33:39,000
Wie zou letterlijk graag eerst?

613
00:33:39,000 --> 00:33:41,000
Oke, komen op. Je bent eerst.

614
00:33:41,000 --> 00:33:44,000
Wie zou willen zijn 9? Oke, 9.

615
00:33:44,000 --> 00:33:46,000
Hoe zit het met 9? 17?

616
00:33:46,000 --> 00:33:51,000
Een beetje kliek hier. 22 en 26 in die eerste rij.

617
00:33:51,000 --> 00:33:53,000
En dan wat te denken van iemand die daar worden gewezen.

618
00:33:53,000 --> 00:33:57,000
Je bent 34. Oke, kom 34, op maximaal.

619
00:33:57,000 --> 00:33:59,000
Ten eerste is daar. Oke, alle vier van jullie.

620
00:33:59,000 --> 00:34:01,000
En wie hebben we zeggen voor 9?

621
00:34:01,000 --> 00:34:04,000
Wie is onze 9?

622
00:34:04,000 --> 00:34:07,000
Wie wil zo graag 9? Oke, kom op, wees 9.

623
00:34:07,000 --> 00:34:10,000
Daar gaan we.

624
00:34:10,000 --> 00:34:13,000
34, zullen we ontmoeten u daar.

625
00:34:13,000 --> 00:34:17,000
Het eerste deel is het maken van jezelf lijken.

626
00:34:17,000 --> 00:34:21,000
26, 22, 17, goed.

627
00:34:21,000 --> 00:34:25,000
Als je af staan ​​aan de kant, want we gaan je malloc in een moment.

628
00:34:25,000 --> 00:34:29,000
>> Goed, goed.

629
00:34:29,000 --> 00:34:32,000
Oke, prima, dus laten we hier vragen een paar vragen.

630
00:34:32,000 --> 00:34:34,000
En eigenlijk, wat is je naam? >> Anita.

631
00:34:34,000 --> 00:34:37,000
Anita, okay, kom hier.

632
00:34:37,000 --> 00:34:41,000
Anita gaat om ons te helpen soort van het oplossen van een vrij eenvoudige vraag in de eerste,

633
00:34:41,000 --> 00:34:44,000
dat is hoe vind je al dan niet een waarde in de lijst voorkomt?

634
00:34:44,000 --> 00:34:48,000
Let nu op die eerste, hier vertegenwoordigd door Lucas,

635
00:34:48,000 --> 00:34:52,000
is een beetje anders, en dus zijn stuk papier is bewust opzij

636
00:34:52,000 --> 00:34:55,000
want het is niet zo groot en niet in beslag nemen zo veel bits,

637
00:34:55,000 --> 00:34:58,000
hoewel technisch heeft hij het papier van hetzelfde formaat gewoon gedraaid.

638
00:34:58,000 --> 00:35:01,000
Maar hij is een beetje anders in dat hij slechts 32 bits voor een pointer,

639
00:35:01,000 --> 00:35:05,000
en al deze jongens zijn 64 bits, waarvan de helft van het aantal, waarvan de helft een pointer.

640
00:35:05,000 --> 00:35:08,000
Maar de aanwijzer wordt niet weergegeven, dus als jullie kunnen een beetje onhandig

641
00:35:08,000 --> 00:35:12,000
gebruik uw linkerhand om te wijzen naar de persoon naast je.

642
00:35:12,000 --> 00:35:14,000
En je bent nummer 34. Wat is je naam?

643
00:35:14,000 --> 00:35:16,000
Ari.

644
00:35:16,000 --> 00:35:19,000
Ari, dus eigenlijk, houdt het papier in uw rechterhand en linkerhand gaat recht naar beneden.

645
00:35:19,000 --> 00:35:21,000
U vertegenwoordigt null aan de linkerkant.

646
00:35:21,000 --> 00:35:24,000
>> Nu onze menselijke beeld is zeer consistent.

647
00:35:24,000 --> 00:35:26,000
Dit is eigenlijk hoe pointers werken.

648
00:35:26,000 --> 00:35:29,000
En als je een beetje op deze manier samenperst, dus ik ben niet in de weg.

649
00:35:29,000 --> 00:35:34,000
Anita hier, vind ik het nummer 22,

650
00:35:34,000 --> 00:35:40,000
maar gaan uit van een beperking van het niet mensen houden tot stukjes papier,

651
00:35:40,000 --> 00:35:43,000
maar dit is een lijst, en heb je alleen Lucas om te beginnen met

652
00:35:43,000 --> 00:35:46,000
want hij is letterlijk de eerste pointer.

653
00:35:46,000 --> 00:35:51,000
Stel, je bent zelf een pointer, en dus moet je ook de mogelijkheid om te wijzen op iets.

654
00:35:51,000 --> 00:35:56,000
Waarom ga je niet beginnen door te wijzen op wat Lucas wijst op?

655
00:35:56,000 --> 00:35:58,000
Goed, en laat mij dit uit te vaardigen hier.

656
00:35:58,000 --> 00:36:04,000
Net omwille van de discussie, laat me trek hier een lege pagina.

657
00:36:04,000 --> 00:36:06,000
Hoe schrijf je je naam? >> Anita.

658
00:36:06,000 --> 00:36:08,000
Oke, Anita.

659
00:36:08,000 --> 00:36:18,000
Laten we zeggen dat knooppunt * anita = lucas.

660
00:36:18,000 --> 00:36:22,000
Nou, moeten we niet bellen u lucas. We moeten bellen u voor het eerst.

661
00:36:22,000 --> 00:36:25,000
Waarom is dit in feite overeen met de werkelijkheid hier?

662
00:36:25,000 --> 00:36:27,000
Een, eerst al bestaat.

663
00:36:27,000 --> 00:36:30,000
Eerste is vermoedelijk ergens hier toegewezen.

664
00:36:30,000 --> 00:36:35,000
Node * eerste, en het is al toegewezen een lijst een of andere manier.

665
00:36:35,000 --> 00:36:37,000
Ik weet niet hoe dat gebeurd is. Dat gebeurde voor de les begon.

666
00:36:37,000 --> 00:36:40,000
Deze gelinkte lijst van mensen is gemaakt.

667
00:36:40,000 --> 00:36:44,000
En nu op dit punt in het verhaal, dit is allemaal op Facebook blijkbaar later-

668
00:36:44,000 --> 00:36:49,000
op dit punt in het verhaal, Anita geïnitialiseerd gelijk aan eerste,

669
00:36:49,000 --> 00:36:51,000
wat niet betekent dat Anita wijst naar Lucas.

670
00:36:51,000 --> 00:36:53,000
Integendeel, zij wijst naar wat hij wijst naar

671
00:36:53,000 --> 00:36:57,000
omdat hetzelfde adres dat binnen is van Lucas 32 bits - 1, 2, 3 -

672
00:36:57,000 --> 00:37:01,000
nu ook binnenkant van Anita's 32 bits - 1, 2, 3.

673
00:37:01,000 --> 00:37:05,000
>> Kijk nu 22. Hoe zou je dat doen?

674
00:37:05,000 --> 00:37:07,000
Wat is dat? >> Point to wat dan ook.

675
00:37:07,000 --> 00:37:11,000
Wijs wat dan ook, dus ga je gang en doen het uit zo goed mogelijk hier.

676
00:37:11,000 --> 00:37:15,000
Goed, goed, en nu ben je te wijzen op-hoe heet je met 22?

677
00:37:15,000 --> 00:37:18,000
Ramon. >> Ramon, dus Ramon houdt met 22.

678
00:37:18,000 --> 00:37:20,000
U heeft nu gedaan een cheque.

679
00:37:20,000 --> 00:37:24,000
Heeft Ramon == 22, en zo ja, bijvoorbeeld, kunnen we return true.

680
00:37:24,000 --> 00:37:26,000
Laat me-terwijl deze jongens sta hier een beetje onhandig-

681
00:37:26,000 --> 00:37:32,000
laat me snel iets doen als bool te vinden.

682
00:37:32,000 --> 00:37:37,000
Ik ga om verder te gaan en te zeggen (knooppunt * lijst, int n).

683
00:37:37,000 --> 00:37:39,000
Ik ben zo terug met jullie. Ik moet gewoon wat code te schrijven.

684
00:37:39,000 --> 00:37:45,000
En nu ga ik verder te gaan en dit, knoop * anita = do list.

685
00:37:45,000 --> 00:37:51,000
En ik ga om verder te gaan en te zeggen, terwijl (anita! = NULL).

686
00:37:51,000 --> 00:37:57,000
>> De metafoor is hier een beetje uitgerekt, maar terwijl (anita! = NULL), wat wil ik doen?

687
00:37:57,000 --> 00:38:03,000
Ik moet een manier verwijzen naar

688
00:38:03,000 --> 00:38:05,000
het gehele getal dat Anita wijst op.

689
00:38:05,000 --> 00:38:08,000
In het verleden, wanneer we structuren hadden, die een knooppunt,

690
00:38:08,000 --> 00:38:11,000
gebruikten we de punt-notatie, en we zouden iets zeggen

691
00:38:11,000 --> 00:38:15,000
anita.n, maar het probleem hier is dat Anita niet een struct als zodanig.

692
00:38:15,000 --> 00:38:17,000
Wat is ze?

693
00:38:17,000 --> 00:38:21,000
Ze is een pointer, dus echt, als we willen dit punt te gebruiken notatie-

694
00:38:21,000 --> 00:38:23,000
en dit eruit komt te zien met opzet een beetje cryptisch-

695
00:38:23,000 --> 00:38:28,000
we moeten iets doen, zoals naar de linkerhand wat Anita's wijst op

696
00:38:28,000 --> 00:38:31,000
en krijgen dan het veld met de naam n.

697
00:38:31,000 --> 00:38:35,000
Anita is een pointer, maar wat is * anita?

698
00:38:35,000 --> 00:38:38,000
Wat vind je als je naar wat Anita wijst op?

699
00:38:38,000 --> 00:38:42,000
Een struct, een knooppunt en een knooppunt, recall, heeft een veld n

700
00:38:42,000 --> 00:38:47,000
omdat het, herinneren, deze 2 velden, naast en n,

701
00:38:47,000 --> 00:38:50,000
dat zagen we een ogenblik geleden hier.

702
00:38:50,000 --> 00:38:53,000
>> Om daadwerkelijk na te bootsen dit in de code,

703
00:38:53,000 --> 00:39:02,000
we konden doen en zeggen if ((* anita). n == n), de n dat ik ben op zoek naar.

704
00:39:02,000 --> 00:39:04,000
Merk op dat de functie werd in het aantal waar ik om geef.

705
00:39:04,000 --> 00:39:10,000
Dan kan ik verder gaan en doen iets als return true.

706
00:39:10,000 --> 00:39:12,000
Anders, als dat niet het geval is, wat ik wil doen?

707
00:39:12,000 --> 00:39:19,000
Hoe vertaal ik naar blauwdruk van wat Anita deed dat intuïtief door een wandeling door de lijst?

708
00:39:19,000 --> 00:39:26,000
Wat moet ik hier doen tot simuleren Anita het nemen van die stap naar links, die stap naar links?

709
00:39:26,000 --> 00:39:28,000
[Onverstaanbaar student reactie] >> Wat is dat?

710
00:39:28,000 --> 00:39:30,000
[Onverstaanbaar student reactie]

711
00:39:30,000 --> 00:39:34,000
Goed, geen slecht idee, maar in het verleden, toen we dit hebt gedaan, hebben we gedaan anita + +

712
00:39:34,000 --> 00:39:37,000
want dat zou de nummer 1 toe te voegen aan Anita,

713
00:39:37,000 --> 00:39:40,000
die typisch zou wijzen op de volgende persoon, zoals Ramon,

714
00:39:40,000 --> 00:39:44,000
of de persoon naast hem, of de naast hem iemand langs de lijn.

715
00:39:44,000 --> 00:39:49,000
Maar dat is niet helemaal goed hier want wat doet dit ding eruit in het geheugen?

716
00:39:49,000 --> 00:39:54,000
Niet dat. We moeten die schakelen.

717
00:39:54,000 --> 00:40:00,000
Het lijkt erop dat deze in het geheugen, en ook al heb ik 1 en 2 en 3 dicht bij elkaar getrokken,

718
00:40:00,000 --> 00:40:03,000
als we echt simuleren-can jullie, terwijl nog steeds wijst naar dezelfde mensen,

719
00:40:03,000 --> 00:40:07,000
kunnen sommige van u een willekeurige stap terug, sommigen van jullie een willekeurige stap voorwaarts?

720
00:40:07,000 --> 00:40:10,000
>> Deze puinhoop is nog steeds een gelinkte lijst,

721
00:40:10,000 --> 00:40:13,000
maar deze jongens kan overal in het geheugen zijn,

722
00:40:13,000 --> 00:40:15,000
dus anita + + is niet van plan om te werken waarom?

723
00:40:15,000 --> 00:40:19,000
Wat is op de locatie van anita + +?

724
00:40:19,000 --> 00:40:21,000
Wie weet.

725
00:40:21,000 --> 00:40:24,000
Het is een andere waarde die net zo gebeurt te worden tussengevoegd

726
00:40:24,000 --> 00:40:28,000
tussen al deze knooppunten bij toeval omdat we niet met behulp van een array.

727
00:40:28,000 --> 00:40:30,000
We toegewezen elk van deze knooppunten afzonderlijk.

728
00:40:30,000 --> 00:40:32,000
Oke, als jullie kunnen schoonmaken jezelf een back-up.

729
00:40:32,000 --> 00:40:37,000
Laat me voorstellen dat in plaats van anita + +, we doen in plaats anita gets-

730
00:40:37,000 --> 00:40:42,000
goed, waarom gaan we niet naar wat Anita wijst op en dan doen. volgende stap?

731
00:40:42,000 --> 00:40:45,000
Met andere woorden, we gaan naar Ramon, wie houdt het nummer 22,

732
00:40:45,000 --> 00:40:51,000
en dan. volgende is alsof Anita zou het kopiëren van zijn linkerhand pointer.

733
00:40:51,000 --> 00:40:54,000
Maar ze zou niet verder gaan dan Ramon, omdat we vinden 22.

734
00:40:54,000 --> 00:40:56,000
Maar dat zou het idee zijn. Nu, dit is een god-awful puinhoop.

735
00:40:56,000 --> 00:40:59,000
Eerlijk gezegd, zal niemand ooit vergeet deze syntaxis, en zo gelukkig,

736
00:40:59,000 --> 00:41:04,000
het is eigenlijk een beetje bewust-oh, je niet echt zien wat ik schreef.

737
00:41:04,000 --> 00:41:08,000
Dit zou meer overtuigend als je kon. Voila!

738
00:41:08,000 --> 00:41:10,000
>> Achter de schermen, was ik het oplossen van het probleem op deze manier.

739
00:41:10,000 --> 00:41:14,000
Anita, dat stap opzij nemen,

740
00:41:14,000 --> 00:41:18,000
eerst, gaan we naar het adres dat Anita wijst op

741
00:41:18,000 --> 00:41:23,000
en waar ze vinden niet alleen n, die we gewoon gecontroleerd ter vergelijking,

742
00:41:23,000 --> 00:41:25,000
maar je vindt er ook volgende - in dit geval,

743
00:41:25,000 --> 00:41:28,000
Linkerhand Ramon wijst naar het volgende knooppunt in de lijst.

744
00:41:28,000 --> 00:41:32,000
Maar dit is de god-awful puinhoop waar ik het eerder,

745
00:41:32,000 --> 00:41:34,000
maar het blijkt dat C laat ons vereenvoudigen dit.

746
00:41:34,000 --> 00:41:40,000
In plaats van het schrijven (* anita), kunnen we in plaats daarvan gewoon schrijven anita-> n,

747
00:41:40,000 --> 00:41:45,000
en het is precies hetzelfde functioneel, maar het is veel meer intuïtief,

748
00:41:45,000 --> 00:41:48,000
en het is nog veel meer in overeenstemming is met het beeld dat we al tekenen

749
00:41:48,000 --> 00:41:50,000
al die tijd met behulp van pijlen.

750
00:41:50,000 --> 00:41:57,000
>> Tot slot, wat we moeten doen aan het eind van dit programma?

751
00:41:57,000 --> 00:42:00,000
Er is een regel code over.

752
00:42:00,000 --> 00:42:02,000
Keer terug wat?

753
00:42:02,000 --> 00:42:05,000
False, want als we door het hele while loop

754
00:42:05,000 --> 00:42:10,000
Anita en is in feite null, dat betekent dat ze ging helemaal naar het einde van de lijst

755
00:42:10,000 --> 00:42:12,000
waar ze wees naar-hoe heet je ook alweer?

756
00:42:12,000 --> 00:42:15,000
Linkerhand Ari. >> Ari, die is null.

757
00:42:15,000 --> 00:42:18,000
Anita is nu nul, en ik realiseer me dat je alleen hier staan ​​onhandig in het ongewisse

758
00:42:18,000 --> 00:42:21,000
want ik ga af op een monoloog hier,

759
00:42:21,000 --> 00:42:23,000
maar we zullen weer betrekken u in slechts een moment.

760
00:42:23,000 --> 00:42:27,000
Anita null is op dat punt in het verhaal, zodat de while-lus wordt beëindigd,

761
00:42:27,000 --> 00:42:30,000
en we hebben om terug te keren vals, want als ze kreeg helemaal naar null pointer Ari's

762
00:42:30,000 --> 00:42:34,000
er was geen nummer dat ze gezocht in de lijst.

763
00:42:34,000 --> 00:42:39,000
We kunnen ruimen dit ook, maar dit is een vrij goede uitvoering dan

764
00:42:39,000 --> 00:42:43,000
van een traversal functie, een zoekfunctie voor een gelinkte lijst.

765
00:42:43,000 --> 00:42:48,000
Het is nog steeds lineair zoeken, maar het is niet zo eenvoudig als + + een pointer

766
00:42:48,000 --> 00:42:52,000
of + + Een i variabele, want nu kunnen we niet raden

767
00:42:52,000 --> 00:42:54,000
waarbij elk van deze knooppunten in het geheugen.

768
00:42:54,000 --> 00:42:57,000
We moeten letterlijk volgen het spoor van broodkruimels of, meer specifiek,

769
00:42:57,000 --> 00:43:00,000
pointers, om van de ene knooppunt naar het andere.

770
00:43:00,000 --> 00:43:02,000
>> Nu gaan we proberen een andere. Anita, wil je hier terug te komen?

771
00:43:02,000 --> 00:43:06,000
Waarom gaan we niet verder te gaan en toe te wijzen een andere persoon uit het publiek?

772
00:43:06,000 --> 00:43:08,000
Malloc-wat is je naam? >> Rebecca.

773
00:43:08,000 --> 00:43:10,000
Rebecca. Rebecca is malloced van het publiek,

774
00:43:10,000 --> 00:43:13,000
en ze is nu het opslaan van het nummer 55.

775
00:43:13,000 --> 00:43:17,000
En het doel bij de hand is nu voor Anita te plaatsen om

776
00:43:17,000 --> 00:43:22,000
Rebecca in de gelinkte lijst hier in zijn juiste plaats.

777
00:43:22,000 --> 00:43:24,000
Kom hier voor een moment.

778
00:43:24,000 --> 00:43:28,000
Ik heb gedaan iets als dit.

779
00:43:28,000 --> 00:43:32,000
Ik heb gedaan knooppunt *. En hoe heet je ook alweer?

780
00:43:32,000 --> 00:43:34,000
Rebecca. >> Rebecca, oke.

781
00:43:34,000 --> 00:43:41,000
Rebecca krijgt malloc (sizeof (node)).

782
00:43:41,000 --> 00:43:44,000
Net zoals we hebben toegewezen zaken als studenten en wat al niet in het verleden,

783
00:43:44,000 --> 00:43:46,000
moeten we de grootte van de knoop, dus nu Rebecca

784
00:43:46,000 --> 00:43:49,000
wijst op wat?

785
00:43:49,000 --> 00:43:52,000
Rebecca heeft twee velden binnenkant van haar, waarvan er 55.

786
00:43:52,000 --> 00:43:55,000
Laten we doen wat, rebecca-> = 55.

787
00:43:55,000 --> 00:44:00,000
Maar dan rebecca-> volgende moet-worden wil op dit moment, haar hand is een soort van wie weet?

788
00:44:00,000 --> 00:44:03,000
Het is te wijzen op een aantal vuilnis waarde, dus waarom niet voor een goede maatregel

789
00:44:03,000 --> 00:44:07,000
we op zijn minst doen dit zodat linkerhand is nu aan haar zijde.

790
00:44:07,000 --> 00:44:09,000
Nu Anita, neem het van hier.

791
00:44:09,000 --> 00:44:11,000
Je hebt Rebecca te zijn toegewezen.

792
00:44:11,000 --> 00:44:20,000
Ga je gang en vinden waar we moeten zetten Rebecca.

793
00:44:20,000 --> 00:44:25,000
Goed, heel goed.

794
00:44:25,000 --> 00:44:28,000
Oke, goed, en nu moeten we je een beetje van richting te geven,

795
00:44:28,000 --> 00:44:30,000
dus je hebt bereikt Ari.

796
00:44:30,000 --> 00:44:33,000
Zijn linkerhand is null, maar Rebecca duidelijk behoort tot de juiste,

797
00:44:33,000 --> 00:44:36,000
dus hoe moeten we deze gelinkte lijst wijzigen

798
00:44:36,000 --> 00:44:38,000
om Rebecca te voegen in de juiste plaats?

799
00:44:38,000 --> 00:44:42,000
Als je zou kunnen letterlijk mensen linker handen bewegen als dat nodig is,

800
00:44:42,000 --> 00:44:48,000
zullen we het probleem oplossen op die manier.

801
00:44:48,000 --> 00:44:52,000
Oke, goed, en ondertussen, linkerhand Rebecca's is nu aan haar zijde.

802
00:44:52,000 --> 00:44:54,000
>> Dat was te gemakkelijk.

803
00:44:54,000 --> 00:44:57,000
Laten we proberen de toewijzing-We zijn bijna klaar, 20.

804
00:44:57,000 --> 00:44:59,000
Oke, komen op.

805
00:44:59,000 --> 00:45:04,000
20 is toegekend, dus laat me ga je gang en hier nog een keer zeggen

806
00:45:04,000 --> 00:45:07,000
we hebben net gedaan knooppunt * Saad.

807
00:45:07,000 --> 00:45:11,000
We hebben malloc (sizeof (node)).

808
00:45:11,000 --> 00:45:16,000
We dan doen precies dezelfde syntax als voorheen voor 20,

809
00:45:16,000 --> 00:45:20,000
en ik doe next = NULL, en nu is het aan Anita

810
00:45:20,000 --> 00:45:23,000
om u in te voegen in de gelinkte lijst, als je zou kunnen dat exact dezelfde rol spelen.

811
00:45:23,000 --> 00:45:30,000
Uitvoeren.

812
00:45:30,000 --> 00:45:32,000
Oke, goed.

813
00:45:32,000 --> 00:45:38,000
Nu goed nadenken alvorens te beginnen met bewegen linker handen rond.

814
00:45:38,000 --> 00:45:46,000
Je veruit kreeg de meeste lastige rol vandaag.

815
00:45:46,000 --> 00:45:59,000
Wiens hand moet eerst worden verplaatst?

816
00:45:59,000 --> 00:46:02,000
Oke, wacht, ik ben een aantal no's horen.

817
00:46:02,000 --> 00:46:07,000
Als sommige mensen zou beleefd willen helpen hier op te lossen een lastige situatie.

818
00:46:07,000 --> 00:46:11,000
Wiens linkerhand moet eerst misschien worden bijgewerkt? Ja.

819
00:46:11,000 --> 00:46:13,000
[Student] Saad's.

820
00:46:13,000 --> 00:46:15,000
Oke, Saad, waarom, hoewel?

821
00:46:15,000 --> 00:46:17,000
[Onverstaanbaar student reactie]

822
00:46:17,000 --> 00:46:19,000
Goed, want als we verhuizen-wat is je naam? >> Marshall.

823
00:46:19,000 --> 00:46:22,000
Marshall, als we verhuizen zijn hand first down op null,

824
00:46:22,000 --> 00:46:25,000
nu hebben we letterlijk wees vier mensen in deze lijst

825
00:46:25,000 --> 00:46:29,000
want hij was het enige wat wijst op Ramon en iedereen naar links,

826
00:46:29,000 --> 00:46:31,000
zodat bijwerken van die wijzer eerste was slecht.

827
00:46:31,000 --> 00:46:33,000
Laten we ongedaan te maken dat.

828
00:46:33,000 --> 00:46:37,000
Goed, en nu ga je gang en zet de juiste linkerhand wijst naar Ramon.

829
00:46:37,000 --> 00:46:39,000
Dit voelt een beetje overbodig.

830
00:46:39,000 --> 00:46:41,000
Nu is er twee mensen te wijzen op Ramon, maar dat is prima

831
00:46:41,000 --> 00:46:43,000
want nu hoe anders kunnen we het actualiseren van de lijst?

832
00:46:43,000 --> 00:46:48,000
Welke andere kant heeft te bewegen?

833
00:46:48,000 --> 00:46:53,000
Uitstekend, nu we verloren geen geheugen?

834
00:46:53,000 --> 00:46:57,000
Nee, zo goed, laten we eens kijken of we niet breken dit nogmaals.

835
00:46:57,000 --> 00:47:00,000
>> Mallocing een laatste keer, nummer 5.

836
00:47:00,000 --> 00:47:04,000
Helemaal in de rug, kom naar beneden.

837
00:47:04,000 --> 00:47:08,000
Het is heel spannend.

838
00:47:08,000 --> 00:47:15,000
[Applaus]

839
00:47:15,000 --> 00:47:17,000
Wat is je naam? >> Ron.

840
00:47:17,000 --> 00:47:19,000
Ron, oke, je malloced als nummer 5.

841
00:47:19,000 --> 00:47:23,000
We hebben net uitgevoerde code die bijna identiek is aan deze

842
00:47:23,000 --> 00:47:26,000
met alleen een andere naam.

843
00:47:26,000 --> 00:47:28,000
Uitstekend.

844
00:47:28,000 --> 00:47:38,000
Nu, Anita, veel succes het plaatsen van nummer 5 in de lijst nu.

845
00:47:38,000 --> 00:47:43,000
Goed, en?

846
00:47:43,000 --> 00:47:47,000
Uitstekend, dus dit is echt de derde van drie totale gevallen.

847
00:47:47,000 --> 00:47:49,000
We moesten eerst iemand aan het eind, Rebecca.

848
00:47:49,000 --> 00:47:51,000
We hadden iemand in het midden.

849
00:47:51,000 --> 00:47:53,000
Nu hebben we iemand bij het begin, en in dit voorbeeld

850
00:47:53,000 --> 00:47:56,000
we nu moesten Lucas werken voor de eerste keer

851
00:47:56,000 --> 00:48:00,000
omdat de eerste element in de lijst nu te wijzen op een nieuwe node,

852
00:48:00,000 --> 00:48:03,000
die op zijn beurt wijst naar knooppunt nummer 9.

853
00:48:03,000 --> 00:48:06,000
>> Dit was een enorm lastige demonstratie, ik ben er zeker van,

854
00:48:06,000 --> 00:48:08,000
dus een groot applaus voor deze jongens als je kon.

855
00:48:08,000 --> 00:48:11,000
Mooi gedaan.

856
00:48:11,000 --> 00:48:17,000
Dat is alles. U kunt u uw stukjes papier als een kleine herinnering.

857
00:48:17,000 --> 00:48:22,000
Het blijkt dat dit te doen in de code

858
00:48:22,000 --> 00:48:26,000
is niet zo eenvoudig als gewoon bewegen handen rond

859
00:48:26,000 --> 00:48:28,000
en wees pointers op verschillende dingen.

860
00:48:28,000 --> 00:48:31,000
Maar beseffen dat wanneer het tijd is om iets als te implementeren

861
00:48:31,000 --> 00:48:34,000
een gekoppelde lijst of een variant ervan als je je richt op echt

862
00:48:34,000 --> 00:48:38,000
deze fundamentele grondslagen, de hapklare problemen die ik moet uitzoeken,

863
00:48:38,000 --> 00:48:43,000
is het deze hand of deze hand, beseffen dat wat anders is een vrij complex programma

864
00:48:43,000 --> 00:48:47,000
kan in feite worden gereduceerd tot vrij eenvoudige bouwstenen zoals deze.

865
00:48:47,000 --> 00:48:51,000
>> Laten we dingen nog te nemen aan een meer verfijnde richting.

866
00:48:51,000 --> 00:48:53,000
We hebben nu het idee van de gekoppelde lijst.

867
00:48:53,000 --> 00:48:57,000
We hebben ook-dankzij de suggestie daar-een dubbel gelinkte lijst,

868
00:48:57,000 --> 00:49:01,000
die ziet er bijna hetzelfde, maar nu hebben we twee pointers binnenkant van de struct

869
00:49:01,000 --> 00:49:05,000
in plaats van een, en we kunnen waarschijnlijk noemen die pointers vorige en volgende

870
00:49:05,000 --> 00:49:08,000
of naar links of rechts, maar wij, in feite, hebben twee van hen.

871
00:49:08,000 --> 00:49:10,000
De code zou een beetje meer betrokken.

872
00:49:10,000 --> 00:49:12,000
Anita had moeten meer werk doen hier op het podium.

873
00:49:12,000 --> 00:49:15,000
Maar we kunnen zeker implementeren dat soort structuur.

874
00:49:15,000 --> 00:49:19,000
In termen van looptijd, hoewel, Wat zou de looptijd

875
00:49:19,000 --> 00:49:24,000
voor Anita van het vinden van een getal n in een gekoppelde lijst nu?

876
00:49:24,000 --> 00:49:27,000
Nog steeds grote O van n, dus het is niet beter dan lineair zoeken.

877
00:49:27,000 --> 00:49:29,000
We kunnen niet binair zoeken, maar, nogmaals.

878
00:49:29,000 --> 00:49:34,000
Waarom was dat zo? Je kunt niet rond te springen.

879
00:49:34,000 --> 00:49:36,000
Hoewel we natuurlijk bekijk alle mensen op het podium,

880
00:49:36,000 --> 00:49:39,000
en Anita had kunnen eyeballed het en zei: "Hier is het midden van de lijst,"

881
00:49:39,000 --> 00:49:42,000
ze zou niet weten dat als zij het computerprogramma

882
00:49:42,000 --> 00:49:47,000
omdat het enige wat ze hadden aan te haken bij het begin van het scenario

883
00:49:47,000 --> 00:49:50,000
was Lucas, die de eerste pointer.

884
00:49:50,000 --> 00:49:53,000
Ze zou per se om die links te volgen,

885
00:49:53,000 --> 00:49:56,000
tellen haar weg tot ze ongeveer het midden,

886
00:49:56,000 --> 00:49:58,000
en zelfs dan, ze niet van plan om te weten wanneer ze bereikte het midden

887
00:49:58,000 --> 00:50:01,000
tenzij ze gaat helemaal naar het eind om erachter te komen hoeveel het er zijn,

888
00:50:01,000 --> 00:50:05,000
dan Backtracks, en ook dat zou moeilijk zijn, tenzij je had

889
00:50:05,000 --> 00:50:07,000
een dubbel gelinkte lijst van een soort.

890
00:50:07,000 --> 00:50:10,000
>> Het oplossen van een aantal problemen van vandaag, maar de invoering van anderen.

891
00:50:10,000 --> 00:50:12,000
Hoe zit het met een andere datastructuur bij elkaar?

892
00:50:12,000 --> 00:50:15,000
Dit is een foto van de trays in Mather House,

893
00:50:15,000 --> 00:50:19,000
en in dit geval hebben we een datastructuur hebben we ook een soort van al het over had.

894
00:50:19,000 --> 00:50:22,000
We spraken over een stapel in het kader van het geheugen,

895
00:50:22,000 --> 00:50:26,000
en dat is soort van bewust genoemd omdat een stapel in de termen van het geheugen

896
00:50:26,000 --> 00:50:31,000
daadwerkelijk een datastructuur die meer materiaal gelaagd bovenop heeft.

897
00:50:31,000 --> 00:50:35,000
Maar het interessante ding over een stapel, zoals het geval is in de werkelijkheid,

898
00:50:35,000 --> 00:50:38,000
is dat het een speciaal soort datastructuur.

899
00:50:38,000 --> 00:50:42,000
Het is een datastructuur waarbij het eerste element in

900
00:50:42,000 --> 00:50:46,000
is het laatste element uit.

901
00:50:46,000 --> 00:50:50,000
Als je de eerste lade worden geplaatst op de stack,

902
00:50:50,000 --> 00:50:53,000
je gaat helaas de laatste lade te nemen van de stapel,

903
00:50:53,000 --> 00:50:55,000
en dat is niet per se een goede zaak.

904
00:50:55,000 --> 00:50:58,000
Omgekeerd kunt u denken andersom,

905
00:50:58,000 --> 00:51:02,000
de laatste in het eerste uit.

906
00:51:02,000 --> 00:51:05,000
>> Nu, geen enkele scenario's komen te letten op waar het hebben van een stapel

907
00:51:05,000 --> 00:51:08,000
datastructuur waar je die eigenschap

908
00:51:08,000 --> 00:51:13,000
van de last in, first out, is eigenlijk dwingend?

909
00:51:13,000 --> 00:51:16,000
Is dat een goede zaak? Is dat een slechte zaak?

910
00:51:16,000 --> 00:51:19,000
Het is zeker een slechte zaak als de lades waren niet allemaal identiek

911
00:51:19,000 --> 00:51:21,000
en ze waren allemaal speciale kleuren of wat al niet,

912
00:51:21,000 --> 00:51:24,000
en de kleur die je wilt is helemaal aan de onderkant.

913
00:51:24,000 --> 00:51:26,000
Natuurlijk kun je niet krijgen dat zonder veel moeite.

914
00:51:26,000 --> 00:51:28,000
Je moet beginnen vanaf de bovenkant en werk je weg naar beneden.

915
00:51:28,000 --> 00:51:31,000
Ook wat als je een van deze ventilator jongens

916
00:51:31,000 --> 00:51:34,000
die wacht de hele nacht proberen om een ​​iPhone en lijnen op te staan

917
00:51:34,000 --> 00:51:36,000
op een plek als deze?

918
00:51:36,000 --> 00:51:40,000
Zou het niet mooi zijn als de Apple Store

919
00:51:40,000 --> 00:51:42,000
waren stack datastructuur?

920
00:51:42,000 --> 00:51:44,000
Yay? Neen?

921
00:51:44,000 --> 00:51:47,000
Het is alleen maar goed voor de mensen die opdagen op de laatste minuut

922
00:51:47,000 --> 00:51:50,000
en dan krijg geplukt uit de wachtrij.

923
00:51:50,000 --> 00:51:52,000
En in feite, om het feit dat ik zo was geneigd te zeggen wachtrij

924
00:51:52,000 --> 00:51:56,000
is eigenlijk overeen met wat we zouden dit soort data structuur noemen,

925
00:51:56,000 --> 00:51:59,000
een in werkelijkheid waar de bestelling er wel toe doet,

926
00:51:59,000 --> 00:52:02,000
en u wilt dat de eerste in om als eerste een op

927
00:52:02,000 --> 00:52:04,000
al was het maar omwille van de menselijke rechtvaardigheid.

928
00:52:04,000 --> 00:52:07,000
We zullen over het algemeen noemen dat een wachtrij datastructuur.

929
00:52:07,000 --> 00:52:11,000
>> Het blijkt bovendien gelinkte lijsten, kunnen we beginnen met het gebruik van deze dezelfde basisideeën

930
00:52:11,000 --> 00:52:15,000
en beginnen nieuwe en verschillende oplossingen voor problemen.

931
00:52:15,000 --> 00:52:19,000
Bijvoorbeeld in het geval van een stapel kunnen we vormen een stapel

932
00:52:19,000 --> 00:52:22,000
met behulp van een data structuur als dit, zou ik voorstellen.

933
00:52:22,000 --> 00:52:26,000
In dit geval heb ik uitgeroepen tot een struct, en ik heb gezegd binnenkant van deze structuur

934
00:52:26,000 --> 00:52:30,000
is een reeks getallen en een variabele genaamd omvang

935
00:52:30,000 --> 00:52:33,000
en ik ga dit ding noemen een stapel.

936
00:52:33,000 --> 00:52:35,000
Nu, waarom dit eigenlijk?

937
00:52:35,000 --> 00:52:43,000
In het geval van een stapel, kon dit effectief tekenen op het scherm als een array.

938
00:52:43,000 --> 00:52:47,000
Hier is mijn stack. Dat zijn mijn nummers.

939
00:52:47,000 --> 00:52:50,000
En we trekken ze als dit, dit, dit, dit, dit.

940
00:52:50,000 --> 00:52:53,000
En dan heb ik een aantal andere gegevens-lid hier,

941
00:52:53,000 --> 00:52:58,000
die heet grootte, zodat dit formaat, en dit is nummers

942
00:52:58,000 --> 00:53:02,000
en gezamenlijk de gehele iPad hier vertegenwoordigt een stapel structuur.

943
00:53:02,000 --> 00:53:07,000
Nu, bij verstek, heeft grootte vermoedelijk moet worden geïnitialiseerd op 0,

944
00:53:07,000 --> 00:53:11,000
en wat er in de reeks van getallen in eerste instantie

945
00:53:11,000 --> 00:53:14,000
toen ik voor het eerst een array toe te wijzen?

946
00:53:14,000 --> 00:53:16,000
Garbage. Wie weet? En het maakt niet echt uit.

947
00:53:16,000 --> 00:53:20,000
Het maakt niet uit of dit 1, 2, 3, 4, 5, volledig willekeurig

948
00:53:20,000 --> 00:53:25,000
door pech opgeslagen in mijn structuur, want zolang ik weet dat de grootte van de stack

949
00:53:25,000 --> 00:53:29,000
0 is, dan weet ik programmatisch, niet kijken naar een van de elementen in de array.

950
00:53:29,000 --> 00:53:31,000
Het maakt niet uit wat er staat.

951
00:53:31,000 --> 00:53:34,000
Kijk niet naar hen, zoals zou de implicatie van een grootte van 0.

952
00:53:34,000 --> 00:53:38,000
>> Maar stel nu ik ga je gang en steek iets in de stapel.

953
00:53:38,000 --> 00:53:42,000
Ik wil de nummer 5 invoegen, dus heb ik nummer 5 hier,

954
00:53:42,000 --> 00:53:45,000
en wat doe ik hier neer te zetten?

955
00:53:45,000 --> 00:53:48,000
Nu zou ik eigenlijk neergezet 1 voor de grootte,

956
00:53:48,000 --> 00:53:50,000
en nu de stapel moet van grootte 1.

957
00:53:50,000 --> 00:53:53,000
Wat als ik ga je gang en nummer, laten we zeggen, 7 next?

958
00:53:53,000 --> 00:53:57,000
Deze krijgt dan bijgewerkt tot en met 2, en dan zullen we doen 9,

959
00:53:57,000 --> 00:54:02,000
en dit wordt bijgewerkt tot 3.

960
00:54:02,000 --> 00:54:05,000
Maar het interessante functie nu van deze stapel is dat

961
00:54:05,000 --> 00:54:09,000
Ik moet welk element te verwijderen als ik wil knallen

962
00:54:09,000 --> 00:54:12,000
iets af van de stapel, om zo te zeggen?

963
00:54:12,000 --> 00:54:14,000
9 zou het eerste ding om te gaan.

964
00:54:14,000 --> 00:54:18,000
Hoe moet de afbeelding veranderen als ik wil een element pop uit de stapel,

965
00:54:18,000 --> 00:54:20,000
Net als een lade in Mather?

966
00:54:20,000 --> 00:54:22,000
Ja. >> [Student] Setformaat naar 2.

967
00:54:22,000 --> 00:54:27,000
Precies, is alles wat ik doe ingesteld grootte tot 2, en wat moet ik doen met de array?

968
00:54:27,000 --> 00:54:29,000
Ik heb niets te doen.

969
00:54:29,000 --> 00:54:32,000
Ik kon, alleen maar om anaal, zet een 0 is er of een -1 of iets te betekenen

970
00:54:32,000 --> 00:54:34,000
dat dit niet een legit waarde, maar het maakt niet uit, omdat

971
00:54:34,000 --> 00:54:37,000
Ik kan opnemen buiten de array zelf hoelang deze

972
00:54:37,000 --> 00:54:41,000
zodat ik weet alleen kijken naar de eerste twee elementen in deze array.

973
00:54:41,000 --> 00:54:47,000
Nu, als ik ga en voeg de nummer 8 van deze array, maakt het plaatje hoe te veranderen nu?

974
00:54:47,000 --> 00:54:50,000
Dit wordt 8 en wordt dit 3.

975
00:54:50,000 --> 00:54:52,000
Ik ben het snijden van een paar bochten hier.

976
00:54:52,000 --> 00:54:56,000
Nu hebben we 5, 7, 8, en we zijn terug naar een grootte van 3.

977
00:54:56,000 --> 00:54:58,000
Dit is vrij eenvoudig te implementeren,

978
00:54:58,000 --> 00:55:06,000
maar wanneer gaan we dit ontwerp beslissing spijt van?

979
00:55:06,000 --> 00:55:09,000
Wanneer dingen beginnen te gaan heel erg mis? Ja.

980
00:55:09,000 --> 00:55:11,000
[Onverstaanbaar student reactie]

981
00:55:11,000 --> 00:55:13,000
Als u terug wilt gaan en het eerste element dat u zetten inch te krijgen

982
00:55:13,000 --> 00:55:18,000
>> Het blijkt hier ook al een stapel is een array onder de motorkap,

983
00:55:18,000 --> 00:55:21,000
deze data structuren die we hebben begonnen te praten over zijn ook algemeen bekend als

984
00:55:21,000 --> 00:55:25,000
abstracte gegevensstructuren, waarbij de manier waarop ze geïmplementeerd

985
00:55:25,000 --> 00:55:27,000
geheel terzijde.

986
00:55:27,000 --> 00:55:31,000
Een gegevensstructuur, zoals een stapel wordt verondersteld te ondersteuning toe te voegen

987
00:55:31,000 --> 00:55:35,000
operaties zoals push, die een lade duwt op de stack,

988
00:55:35,000 --> 00:55:39,000
en pop, die een element verwijdert uit de stapel, en dat is het.

989
00:55:39,000 --> 00:55:43,000
Als je aan iemand anders code die reeds geïmplementeerd downloaden

990
00:55:43,000 --> 00:55:46,000
dit ding heet een stapel, zou die persoon hebben geschreven

991
00:55:46,000 --> 00:55:49,000
slechts twee functies voor u, push en pop, wiens enige doel in het leven

992
00:55:49,000 --> 00:55:51,000
zou zijn om precies dat te doen.

993
00:55:51,000 --> 00:55:54,000
U of hem of haar, die geïmplementeerd dat programma

994
00:55:54,000 --> 00:55:58,000
zou zijn geweest volledig de een om te beslissen hoe te implementeren

995
00:55:58,000 --> 00:56:00,000
de semantiek van duwen en popping onder de motorkap

996
00:56:00,000 --> 00:56:03,000
of de functionaliteit van het duwen en popping.

997
00:56:03,000 --> 00:56:07,000
En ik heb een wat kortzichtige beslissing hier

998
00:56:07,000 --> 00:56:10,000
door het implementeren van mijn stack met deze eenvoudige datastructuur waarom?

999
00:56:10,000 --> 00:56:12,000
Wanneer gaat deze datastructuur pauze?

1000
00:56:12,000 --> 00:56:18,000
Op welk punt moet ik een foutmelding wanneer de gebruiker vraagt ​​push, bijvoorbeeld?

1001
00:56:18,000 --> 00:56:20,000
[Student] Als er geen ruimte meer.

1002
00:56:20,000 --> 00:56:23,000
Precies, als er geen ruimte meer, als ik de capaciteit overschreden,

1003
00:56:23,000 --> 00:56:27,000
die alle doppen omdat het suggereert dat het een soort van globale constante.

1004
00:56:27,000 --> 00:56:30,000
Nou, dan ga ik gewoon te hebben om te zeggen: "Sorry, ik kan niet een andere waarde te duwen

1005
00:56:30,000 --> 00:56:32,000
op de stapel, "net als in Mather.

1006
00:56:32,000 --> 00:56:36,000
>> Op een gegeven moment, ze gaan om het bovenste deel van dat kastje te raken.

1007
00:56:36,000 --> 00:56:39,000
Er is geen ruimte meer of capaciteit in de stapel, op welk punt er een soort van fout.

1008
00:56:39,000 --> 00:56:42,000
Ze moeten het element zetten ergens anders, de lade ergens anders,

1009
00:56:42,000 --> 00:56:44,000
of helemaal nergens.

1010
00:56:44,000 --> 00:56:47,000
Nu, met een wachtrij, konden we implementeren een beetje anders.

1011
00:56:47,000 --> 00:56:50,000
Een wachtrij is een beetje anders in dat er onder de motorkap, het kan worden toegepast

1012
00:56:50,000 --> 00:56:54,000
als een array, maar waarom, in dit geval, stel ik voor

1013
00:56:54,000 --> 00:56:59,000
om ook een hoofd element dat staat voor de kop van de lijst,

1014
00:56:59,000 --> 00:57:06,000
de voorkant van de lijst, de eerste persoon in de rij bij de Apple Store, in aanvulling op maat?

1015
00:57:06,000 --> 00:57:14,000
Waarom heb ik hier behoefte aan een extra stuk van de gegevens?

1016
00:57:14,000 --> 00:57:16,000
Denk eens terug aan wat getallen is

1017
00:57:16,000 --> 00:57:18,000
als ik getekend heb het als volgt.

1018
00:57:18,000 --> 00:57:21,000
Stel dat dit is nu een wachtrij in plaats van een stapel,

1019
00:57:21,000 --> 00:57:24,000
het verschil is-net als de Apple Store-wachtrij is eerlijk.

1020
00:57:24,000 --> 00:57:27,000
De eerste lijn in het begin van de lijst, nummer 5 in dit geval

1021
00:57:27,000 --> 00:57:30,000
hij of zij er eerst laten worden in de winkel.

1022
00:57:30,000 --> 00:57:32,000
Laten we dat doen.

1023
00:57:32,000 --> 00:57:35,000
Stel dat dit de toestand van mijn rij op dit moment in de tijd, nu en de Apple Store

1024
00:57:35,000 --> 00:57:39,000
wordt geopend en de eerste persoon, nummer 5, wordt geleid in de winkel.

1025
00:57:39,000 --> 00:57:43,000
Hoe kan ik nu de foto dat ik de eerste persoon afgemeld wachtrij

1026
00:57:43,000 --> 00:57:47,000
aan de voorkant van de lijn?

1027
00:57:47,000 --> 00:57:50,000
Wat is dat? >> [Student] Verander de wachtrij.

1028
00:57:50,000 --> 00:57:52,000
Wijzig de kop, dus 5 verdwijnt.

1029
00:57:52,000 --> 00:57:56,000
In werkelijkheid, het is alsof-de beste manier om dit te doen?

1030
00:57:56,000 --> 00:58:00,000
In werkelijkheid, is het net alsof deze man verdwijnt.

1031
00:58:00,000 --> 00:58:03,000
Wat zou nummer 7 doen in een echte winkel?

1032
00:58:03,000 --> 00:58:05,000
Ze zou een grote stap voorwaarts.

1033
00:58:05,000 --> 00:58:08,000
>> Maar wat hebben we weten te waarderen als het gaat om arrays

1034
00:58:08,000 --> 00:58:10,000
en verplaatsen van dingen rond?

1035
00:58:10,000 --> 00:58:12,000
Dat is een soort van een verspilling van je tijd, toch?

1036
00:58:12,000 --> 00:58:16,000
Waarom doe je nou zo anaal als de eerste persoon zijn

1037
00:58:16,000 --> 00:58:21,000
aan het begin van de lijn op fysiek het begin van het deel van geheugen?

1038
00:58:21,000 --> 00:58:23,000
Dat is helemaal niet nodig. Waarom?

1039
00:58:23,000 --> 00:58:26,000
Wat kon ik gewoon in plaats weet je nog? >> [Onverstaanbaar student reactie]

1040
00:58:26,000 --> 00:58:30,000
Precies, kon ik alleen niet vergeten met deze aanvullende gegevens lid hoofd

1041
00:58:30,000 --> 00:58:34,000
die nu de kop van de lijst is niet meer 0, wat was het een moment geleden.

1042
00:58:34,000 --> 00:58:39,000
Nu is het eigenlijk de nummer 1. Op deze manier krijg ik een lichte optimalisatie.

1043
00:58:39,000 --> 00:58:44,000
Gewoon omdat ik heb afgemeld wachtrij iemand van lijn aan het begin van de lijn bij de Apple Store

1044
00:58:44,000 --> 00:58:47,000
betekent niet dat iedereen moet verschuiven, wat recall is een lineaire werking.

1045
00:58:47,000 --> 00:58:50,000
Ik kan in plaats daarvan besteden constante tijd alleen

1046
00:58:50,000 --> 00:58:53,000
en dan het bereiken van een veel snellere respons.

1047
00:58:53,000 --> 00:58:56,000
Maar de prijs ik betaal is wat te winnen die extra prestaties

1048
00:58:56,000 --> 00:58:58,000
en niet met iedereen te verschuiven?

1049
00:58:58,000 --> 00:59:01,000
Ja. >> [Onverstaanbaar student reactie]

1050
00:59:01,000 --> 00:59:04,000
Kunnen meer mensen, nou ja, dat probleem is orthogonaal

1051
00:59:04,000 --> 00:59:07,000
aan het feit dat we niet mensen verschuiven rond.

1052
00:59:07,000 --> 00:59:11,000
Het is nog steeds een array, dus of we iedereen verschuiven of niet-

1053
00:59:11,000 --> 00:59:13,000
oh, ik zie wat je bedoelt, oke.

1054
00:59:13,000 --> 00:59:16,000
Eigenlijk ben ik het eens met wat je zegt in dat het bijna alsof

1055
00:59:16,000 --> 00:59:19,000
we nu nooit naar het begin van deze array meer gebruiken

1056
00:59:19,000 --> 00:59:22,000
want als ik verwijderen 5, dan verwijder ik 7.

1057
00:59:22,000 --> 00:59:24,000
Maar ik alleen zet mensen aan de rechterkant.

1058
00:59:24,000 --> 00:59:28,000
>> Het voelt alsof ik verspilling van ruimte, en uiteindelijk mijn wachtrij uiteen in helemaal niets,

1059
00:59:28,000 --> 00:59:31,000
dus we konden gewoon mensen wraparound,

1060
00:59:31,000 --> 00:59:35,000
en we konden echt denken van deze array als een soort cirkelvormige structuur,

1061
00:59:35,000 --> 00:59:38,000
maar we gebruiken wat operator in C om dat soort omhullend doen?

1062
00:59:38,000 --> 00:59:40,000
[Onverstaanbaar student response] >> De modulo operator.

1063
00:59:40,000 --> 00:59:43,000
Het zou een beetje vervelend om na te denken door middel van hoe doe je het wraparound doen,

1064
00:59:43,000 --> 00:59:46,000
maar we konden doen, en we konden beginnen met het zetten van mensen op wat vroeger de voorkant van de lijn,

1065
00:59:46,000 --> 00:59:52,000
maar we herinneren met deze kop variabele die het feitelijke hoofd van de lijn eigenlijk is.

1066
00:59:52,000 --> 00:59:57,000
Wat als, in plaats daarvan, ons doel uiteindelijk, hoewel,

1067
00:59:57,000 --> 01:00:00,000
was om nummers opzoeken, zoals we hier op het podium maakte met Anita,

1068
01:00:00,000 --> 01:00:02,000
maar we willen echt het beste van al deze werelden?

1069
01:00:02,000 --> 01:00:05,000
We willen meer verfijning dan array kunt

1070
01:00:05,000 --> 01:00:09,000
omdat we de mogelijkheid om dynamisch te groeien de datastructuur willen.

1071
01:00:09,000 --> 01:00:12,000
Maar we willen niet hun toevlucht moeten nemen tot iets dat we erop gewezen

1072
01:00:12,000 --> 01:00:15,000
in de eerste lezing was niet optimaal algoritme,

1073
01:00:15,000 --> 01:00:17,000
die van lineair zoeken.

1074
01:00:17,000 --> 01:00:21,000
Het blijkt dat je in feite te bereiken,

1075
01:00:21,000 --> 01:00:24,000
of in ieder geval dicht bij constante tijd, waarbij iemand als Anita,

1076
01:00:24,000 --> 01:00:27,000
als ze configureert haar gegevens structuur niet aan een gekoppelde lijst te zijn,

1077
01:00:27,000 --> 01:00:30,000
niet een stapel, niet aan een wachtrij, zou in feite

1078
01:00:30,000 --> 01:00:33,000
komen met een datastructuur die het mogelijk maakt haar te zoeken dingen,

1079
01:00:33,000 --> 01:00:37,000
zelfs woorden, niet alleen getallen, in wat we noemen constante tijd.

1080
01:00:37,000 --> 01:00:40,000
>> En in feite vooruitkijken een van de psets in deze klasse is bijna altijd

1081
01:00:40,000 --> 01:00:43,000
een implementatie van een spellingscontrole, waarbij

1082
01:00:43,000 --> 01:00:46,000
geven wij u weer zo'n 150.000 woorden Engels en het doel is om

1083
01:00:46,000 --> 01:00:51,000
laden die in het geheugen en snel in staat zijn om vragen van het formulier te beantwoorden

1084
01:00:51,000 --> 01:00:54,000
wordt dit woord juist gespeld?

1085
01:00:54,000 --> 01:00:58,000
En het zou echt slecht als je moest doorlopen alle 150.000 woorden om die te beantwoorden.

1086
01:00:58,000 --> 01:01:02,000
Maar in feite, zullen we zien dat we dit kunnen doen in zeer, zeer snelle tijd.

1087
01:01:02,000 --> 01:01:06,000
En het gaat om de uitvoering zoiets als een hash-tabel te betrekken,

1088
01:01:06,000 --> 01:01:09,000
en hoewel op het eerste gezicht dit ding heet een hash-tabel gaat

1089
01:01:09,000 --> 01:01:12,000
Laten we het bereiken van deze super snelle reactietijden,

1090
01:01:12,000 --> 01:01:18,000
blijkt dat er in feite een probleem.

1091
01:01:18,000 --> 01:01:23,000
Toen het tijd om dit ding-weer gebeld te implementeren komt, ik doe het nog eens.

1092
01:01:23,000 --> 01:01:25,000
Ik ben de enige hier.

1093
01:01:25,000 --> 01:01:28,000
Als het tijd is om de uitvoering van dit ding heet een hash table,

1094
01:01:28,000 --> 01:01:30,000
We gaan te hebben om een ​​beslissing te nemen.

1095
01:01:30,000 --> 01:01:32,000
Hoe groot moet dit ding eigenlijk?

1096
01:01:32,000 --> 01:01:36,000
En als we beginnen met het plaatsen van getallen in deze hash-tabel,

1097
01:01:36,000 --> 01:01:38,000
hoe gaan we om ze op te slaan op een zodanige wijze

1098
01:01:38,000 --> 01:01:42,000
dat we ze terug te krijgen zo snel hebben we ze in?

1099
01:01:42,000 --> 01:01:45,000
Maar we zullen zien het duurde niet lang dat deze vraag van

1100
01:01:45,000 --> 01:01:48,000
wanneer iedereen jarig is in de klas zal heel germane.

1101
01:01:48,000 --> 01:01:51,000
Het blijkt dat in deze kamer, we hebben een paar honderd mensen kregen,

1102
01:01:51,000 --> 01:01:56,000
zodat de kans dat twee van ons hebben op dezelfde dag jarig is waarschijnlijk behoorlijk hoog.

1103
01:01:56,000 --> 01:01:58,000
Wat als er slechts 40 van ons in deze kamer?

1104
01:01:58,000 --> 01:02:02,000
Wat zijn de kansen van twee mensen die op dezelfde dag jarig?

1105
01:02:02,000 --> 01:02:04,000
[Studenten] Meer dan 50%.

1106
01:02:04,000 --> 01:02:06,000
Ja, meer dan 50%. Sterker nog, ik bracht zelfs een grafiek.

1107
01:02:06,000 --> 01:02:08,000
Het blijkt-en dit is eigenlijk gewoon een sneak preview-

1108
01:02:08,000 --> 01:02:12,000
als er slechts 58 van ons in deze kamer, de waarschijnlijkheid van ons 2

1109
01:02:12,000 --> 01:02:16,000
met op dezelfde dag jarig is enorm hoog, bijna 100%,

1110
01:02:16,000 --> 01:02:20,000
en dat gaat een hele hoop pijn voor ons veroorzaken op woensdag.

1111
01:02:20,000 --> 01:02:24,000
>> Met dat gezegd, laten we hier verdagen. We zien je op woensdag.

1112
01:02:24,000 --> 01:02:28,000
[Applaus]

1113
01:02:28,000 --> 01:02:30,000
[CS50.TV]