1
00:00:00,000 --> 00:00:12,610

2
00:00:12,610 --> 00:00:12,900
>> DAVID J. MALAN: Greit.

3
00:00:12,900 --> 00:00:16,790
Så velkommen til den første noensinne
CS50 post mortem for en quiz.

4
00:00:16,790 --> 00:00:18,340
Vi trodde vi skulle innvie
denne tradisjonen i år.

5
00:00:18,340 --> 00:00:20,960
Og dette vil være en mulighet
å gå gjennom

6
00:00:20,960 --> 00:00:22,220
løsninger til quiz.

7
00:00:22,220 --> 00:00:26,160
Og vi vil fremskynde eller forsinke basert
på renter av dem her.

8
00:00:26,160 --> 00:00:29,730
>> Så du er sannsynligvis her fordi du er
interessert i hvordan du kan ha eller

9
00:00:29,730 --> 00:00:31,170
burde ha besvart noen
av disse problemene.

10
00:00:31,170 --> 00:00:33,300
Så hvorfor ikke vi ta en titt
på denne delen først?

11
00:00:33,300 --> 00:00:34,450
Så det å få strenger.

12
00:00:34,450 --> 00:00:37,600
Dette ga deg tre forskjellige versjoner
av et program som var, til slutt,

13
00:00:37,600 --> 00:00:39,650
ment å få en streng fra en bruker.

14
00:00:39,650 --> 00:00:42,530
Hvorvidt det gjorde det var
overlatt til deg å bestemme.

15
00:00:42,530 --> 00:00:45,150
>> Og vi spurte i Spørsmål 0,
anta at versjon 1 er

16
00:00:45,150 --> 00:00:46,400
kompilert og henrettet.

17
00:00:46,400 --> 00:00:48,860
Hvorfor kan programmet segfault?

18
00:00:48,860 --> 00:00:51,150
Ved første øyekast, noen forslag
på hvorfor?

19
00:00:51,150 --> 00:00:54,012

20
00:00:54,012 --> 00:00:54,489
Yeah.

21
00:00:54,489 --> 00:00:59,260
>> PUBLIKUM: Så jeg husker å se dette i
et tidligere eksempel på å se på

22
00:00:59,260 --> 00:01:05,506
char * s og se skanning av s og
se fordi det er en peker, hvordan

23
00:01:05,506 --> 00:01:07,971
gjorde det påvirke hva du skannet inn?

24
00:01:07,971 --> 00:01:10,940
Er det s eller adressen til s?

25
00:01:10,940 --> 00:01:11,180
>> DAVID J. MALAN: OK.

26
00:01:11,180 --> 00:01:11,480
Bra.

27
00:01:11,480 --> 00:01:14,830
Så til slutt, kilden til problemet
er antagelig kommer til å redusere

28
00:01:14,830 --> 00:01:16,210
til den variabelen s.

29
00:01:16,210 --> 00:01:17,280
Og det er faktisk en variabel.

30
00:01:17,280 --> 00:01:19,900
Datatypen til den variabelen er
char *, noe som betyr at det kommer til å

31
00:01:19,900 --> 00:01:22,570
inneholde adressen for et tegn.

32
00:01:22,570 --> 00:01:23,850
Og deri ligger innsikt.

33
00:01:23,850 --> 00:01:28,330
Det kommer til å inneholde adressen til
en art eller, mer generelt,

34
00:01:28,330 --> 00:01:32,110
Adressen til det første tegnet i
en hel blokk av tegn.

35
00:01:32,110 --> 00:01:36,680
>> Men fangsten er at skanning s, formål i
liv, blir gitt en adresse og gitt

36
00:01:36,680 --> 00:01:40,960
et format kode, som% s, lese
en streng i den del av

37
00:01:40,960 --> 00:01:42,330
minnet på denne adressen.

38
00:01:42,330 --> 00:01:46,040
Men fordi det er ingen likhetstegn før
at semikolon på den første

39
00:01:46,040 --> 00:01:49,310
linje med kode, fordi vi ikke egentlig
bevilge noe minne med

40
00:01:49,310 --> 00:01:53,020
malloc, fordi det gjorde faktisk ikke
allokere en matrise av en viss størrelse, alt

41
00:01:53,020 --> 00:01:57,620
du gjør er å lese brukerens
tastaturet innspill til noen komplett

42
00:01:57,620 --> 00:02:00,490
søppel verdi, som
er i s som standard.

43
00:02:00,490 --> 00:02:04,480
Så oddsen er at du kommer til å segfault hvis
at adressen ikke bare så skje

44
00:02:04,480 --> 00:02:08,009
å være en verdi som du kan,
faktisk, skrive til.

45
00:02:08,009 --> 00:02:10,889
Så ille ikke å tildele
hukommelsen der.

46
00:02:10,889 --> 00:02:13,150
>> Så det er snakk om en, spurte vi,
anta at versjon 2 er

47
00:02:13,150 --> 00:02:14,230
kompilert og henrettet.

48
00:02:14,230 --> 00:02:15,900
Hvorfor kan dette programmet segfault?

49
00:02:15,900 --> 00:02:17,990
Så dette er mindre buggy.

50
00:02:17,990 --> 00:02:21,470
Og det er egentlig bare ett
opplagte måten hvor du kan

51
00:02:21,470 --> 00:02:22,810
utløse en segfault her.

52
00:02:22,810 --> 00:02:23,730
Og dette er tematisk.

53
00:02:23,730 --> 00:02:28,180
Hver gang vi bruker c i minne, hva
kan du gjøre for å indusere en segfault

54
00:02:28,180 --> 00:02:30,718
med versjon 2?

55
00:02:30,718 --> 00:02:35,560
>> PUBLIKUM: Hvis du bruker som innspill i
en streng som er lengre enn 49

56
00:02:35,560 --> 00:02:35,975
tegn.

57
00:02:35,975 --> 00:02:37,260
>> DAVID J. MALAN: Nettopp.

58
00:02:37,260 --> 00:02:41,420
Hver gang du ser noe fast lengde
når det kommer til en matrise, din

59
00:02:41,420 --> 00:02:44,650
radar bør gå av at dette kan være
problematisk hvis du ikke sjekker

60
00:02:44,650 --> 00:02:45,810
grensene for en matrise.

61
00:02:45,810 --> 00:02:46,650
Og det er problemet her.

62
00:02:46,650 --> 00:02:47,910
Vi fortsatt bruker scanf.

63
00:02:47,910 --> 00:02:52,200
Vi er fortsatt bruker% s, som betyr prøve
å lese en streng fra brukeren.

64
00:02:52,200 --> 00:02:56,300
Det kommer til å bli lest inn s, som,
på dette punktet, er effektivt

65
00:02:56,300 --> 00:02:58,570
adressen til en del av minnet
eller er det tilsvarende.

66
00:02:58,570 --> 00:03:02,080
Det er navnet på en matrise
tegn i minne.

67
00:03:02,080 --> 00:03:07,610
>> Men akkurat det, hvis du leser en streng
som er lengre enn 49 tegn, 49

68
00:03:07,610 --> 00:03:10,440
fordi du trenger plass til backslash
0, kommer du til å renne over

69
00:03:10,440 --> 00:03:11,390
som buffer.

70
00:03:11,390 --> 00:03:16,410
Og du kan ha flaks og være i stand til
skrive et 51st karakter, 52., 53..

71
00:03:16,410 --> 00:03:18,560
Men på et tidspunkt, OS
kommer til å si, nei.

72
00:03:18,560 --> 00:03:21,270
Dette er definitivt ikke minne
du har lov til å røre.

73
00:03:21,270 --> 00:03:23,380
Og programmet kommer til å segfault.

74
00:03:23,380 --> 00:03:26,650
>> Derfor er det, bør de heuristikker være en hvilken som helst
gang du har fast lengde, har du

75
00:03:26,650 --> 00:03:30,150
å sørge for at du sjekker lengden
av hva det er du prøver

76
00:03:30,150 --> 00:03:31,090
for å lese inn i den.

77
00:03:31,090 --> 00:03:35,110
>> PUBLIKUM: Så for å løse det, kan du
har hatt en uttalelse sjekker faktisk

78
00:03:35,110 --> 00:03:37,140
er lengden større
eller mindre enn?

79
00:03:37,140 --> 00:03:37,730
>> DAVID J. MALAN: Absolutt.

80
00:03:37,730 --> 00:03:41,706
Du har bare en tilstand
som sier, hvis -

81
00:03:41,706 --> 00:03:46,080
eller rettere sagt du ikke nødvendigvis kjenner
på forhånd hvor mange tegn det

82
00:03:46,080 --> 00:03:49,060
brukeren kommer til å skrive, fordi
du har høna og egget.

83
00:03:49,060 --> 00:03:51,860
Ikke før du har lest det på med scanf
kan du finne ut hvor lang tid det er.

84
00:03:51,860 --> 00:03:54,500
Men på dette punktet, er det for sent,
fordi du allerede har lest det inn

85
00:03:54,500 --> 00:03:55,710
en minneblokk.

86
00:03:55,710 --> 00:03:59,590
Så som en side, CS50 bibliotek unngår
dette problemet helt, tilbakekalling

87
00:03:59,590 --> 00:04:01,060
ved hjelp fgetc.

88
00:04:01,060 --> 00:04:05,390
Og den leser ett tegn om gangen,
tip-toeing sammen, vel vitende om at du

89
00:04:05,390 --> 00:04:08,060
kan ikke overskylle en karakter hvis
du leser en om gangen.

90
00:04:08,060 --> 00:04:11,580
>> Fangsten er med getstring tilbakekalling er
at vi må stadig re-størrelse

91
00:04:11,580 --> 00:04:13,590
som del av minne, som
er bare en smerte.

92
00:04:13,590 --> 00:04:15,310
Det er en rekke linjer med
kode for å gjøre det.

93
00:04:15,310 --> 00:04:18,779
Så annen tilnærming ville være å
faktisk bruke en fetter, så

94
00:04:18,779 --> 00:04:19,790
å snakke, av scanf.

95
00:04:19,790 --> 00:04:22,820
Det finnes varianter av mange av disse
funksjoner som faktisk sjekke

96
00:04:22,820 --> 00:04:25,870
lengden på hvor mange tegn
du kan lese maksimalt.

97
00:04:25,870 --> 00:04:29,430
Og du kunne spesifisere, ikke les
mer enn 50 tegn.

98
00:04:29,430 --> 00:04:34,110
Slik det ville være en annen tilnærming, men
mindre imøtekommende av større innganger.

99
00:04:34,110 --> 00:04:37,040
>> Så spørsmål 2 spør, antar at versjon
3 er kompilert og henrettet.

100
00:04:37,040 --> 00:04:39,960
Hvorfor kan det programmet segfault?

101
00:04:39,960 --> 00:04:42,650
Så dette er faktisk den samme
svare på, selv om det

102
00:04:42,650 --> 00:04:43,590
ser litt mer avansert.

103
00:04:43,590 --> 00:04:46,440
Vi bruker malloc, som føles som
vi gir oss selv flere alternativer.

104
00:04:46,440 --> 00:04:48,030
Og så skal vi frigjøre at
hukommelse i enden.

105
00:04:48,030 --> 00:04:49,580
Det er fortsatt bare 50 byte minne.

106
00:04:49,580 --> 00:04:53,620
Så vi kan likevel prøve å lese
i 51, 52, 1000 bytes.

107
00:04:53,620 --> 00:04:55,830
Det kommer til å segfault for
nøyaktig den samme grunn.

108
00:04:55,830 --> 00:04:57,530
>> Men det er en annen grunn for.

109
00:04:57,530 --> 00:05:03,890
Hva annet kunne malloc retur foruten
adressen til en del av minnet?

110
00:05:03,890 --> 00:05:04,920
Det kunne returnere null.

111
00:05:04,920 --> 00:05:07,560
Og fordi vi ikke er sjekker for
det, kan vi gjøre noe

112
00:05:07,560 --> 00:05:11,350
dumt for en annen grunn, som er at
vi kan fortelle scanf, lese

113
00:05:11,350 --> 00:05:16,050
brukerens input fra tastaturet
inn 0 beliggenhet, AKA null.

114
00:05:16,050 --> 00:05:18,890
Og det vil også definitivt
utløse en segfault.

115
00:05:18,890 --> 00:05:21,590
Så for quiz formål, ville vi
har akseptert en av dem som en

116
00:05:21,590 --> 00:05:22,740
gyldig grunn.

117
00:05:22,740 --> 00:05:23,420
En er identiske.

118
00:05:23,420 --> 00:05:25,720
Det ene er litt mer nyansert.

119
00:05:25,720 --> 00:05:28,975
>> Til slutt, med hensyn til programmets
bruk av minne, hvordan versjon 2 og

120
00:05:28,975 --> 00:05:30,350
versjon 3 forskjellige?

121
00:05:30,350 --> 00:05:35,070
Så for hva det er verdt, så vi en
tilsynelatende endeløs forsyning av mulig

122
00:05:35,070 --> 00:05:35,770
svar på dette.

123
00:05:35,770 --> 00:05:39,300
Og blant folks svar, hva vi var
håper på, men vi aksepterte andre

124
00:05:39,300 --> 00:05:42,250
ting, var noen omtale av
faktum at versjon 2 bruker

125
00:05:42,250 --> 00:05:44,560
den såkalte stabelen.

126
00:05:44,560 --> 00:05:46,710
Versjon 3 bruker haugen.

127
00:05:46,710 --> 00:05:50,060
Og funksjonelt, gjør dette egentlig ikke
gjør alt så mye av en forskjell.

128
00:05:50,060 --> 00:05:54,040
På slutten av dagen, er vi fremdeles
bare å få 50 byte minne.

129
00:05:54,040 --> 00:05:56,640
>> Men det var en av de mulige svar
at vi var ute på.

130
00:05:56,640 --> 00:05:59,730
Men du vil se, som du får dine quizer
tilbake fra TFs, som vi gjorde

131
00:05:59,730 --> 00:06:04,330
akseptere andre diskusjoner om deres
ulike bruk av minne i tillegg.

132
00:06:04,330 --> 00:06:08,600
Men stable og heap ville ha vært
et enkelt svar å gå med.

133
00:06:08,600 --> 00:06:11,150
Eventuelle spørsmål?

134
00:06:11,150 --> 00:06:12,400
Jeg gir deg Rob.

135
00:06:12,400 --> 00:06:18,360

136
00:06:18,360 --> 00:06:20,210
>> ROB BOWDEN: Så problemet fire.

137
00:06:20,210 --> 00:06:21,985
Dette er en hvor du måtte fylle
i antall bytes av all

138
00:06:21,985 --> 00:06:23,460
disse ulike typer som brukes.

139
00:06:23,460 --> 00:06:24,830
Så første vi ser.

140
00:06:24,830 --> 00:06:27,930
Anta en 32-bits arkitektur,
som dette CS50 apparatet.

141
00:06:27,930 --> 00:06:33,530
Så en av de grunnleggende ting om
32-bits arkitekturer, forteller at oss

142
00:06:33,530 --> 00:06:37,490
nøyaktig hvor stor en peker kommer
til å være i arkitekturen.

143
00:06:37,490 --> 00:06:43,020
>> Så umiddelbart, vi vet at noen peker
typen er 32-bits eller 4 bytes.

144
00:06:43,020 --> 00:06:46,010
Så se på denne tabellen, en
node * er en peker type.

145
00:06:46,010 --> 00:06:47,250
Det kommer til å være fire byte.

146
00:06:47,250 --> 00:06:51,640
Struct node *, det er bokstavelig talt
identisk med node stjerne.

147
00:06:51,640 --> 00:06:53,590
Og så det kommer til å være fire byte.

148
00:06:53,590 --> 00:06:58,270
String, så det ser ikke ut som en
pekeren ennå, men typedef, en

149
00:06:58,270 --> 00:07:01,590
string er bare en char *, som
er en pekertypen.

150
00:07:01,590 --> 00:07:03,550
Så det kommer til å bli fire byte.

151
00:07:03,550 --> 00:07:06,150
>> Så disse tre er alle fire byte.

152
00:07:06,150 --> 00:07:09,350
Nå, node og student er
litt mer komplisert.

153
00:07:09,350 --> 00:07:15,160
Så se på node og student, ser vi
node som et heltall, og en peker.

154
00:07:15,160 --> 00:07:18,050
Og student er to pekere
på innsiden av den.

155
00:07:18,050 --> 00:07:23,340
Så i hvert fall for vår sak her, måten
som ender vi opp med å beregne størrelsen

156
00:07:23,340 --> 00:07:27,020
dette struct er bare legge opp alt
som er inne i struct.

157
00:07:27,020 --> 00:07:30,690
>> Så for node, har vi et heltall,
som er 4 byte.

158
00:07:30,690 --> 00:07:32,830
Vi har en peker, som er 4 byte.

159
00:07:32,830 --> 00:07:35,820
Og så en node går
å ta opp 8 byte.

160
00:07:35,820 --> 00:07:39,490
Og tilsvarende for student, har vi en
peker som er 4 byte og en annen

161
00:07:39,490 --> 00:07:40,770
peker som er 4 byte.

162
00:07:40,770 --> 00:07:43,180
Så det kommer til å ende
opp som 8 byte.

163
00:07:43,180 --> 00:07:45,480
Så node og student er 8 byte.

164
00:07:45,480 --> 00:07:48,950
Og disse tre er alle fire byte.

165
00:07:48,950 --> 00:07:50,240
Spørsmål om det?

166
00:07:50,240 --> 00:07:54,640

167
00:07:54,640 --> 00:07:54,990
Ja.

168
00:07:54,990 --> 00:07:58,413
>> PUBLIKUM: Er det var en 64-bit
arkitektur, ville det

169
00:07:58,413 --> 00:07:59,880
doble dem alle?

170
00:07:59,880 --> 00:08:01,790
>> ROB BOWDEN: Det ville ikke
doble dem alle.

171
00:08:01,790 --> 00:08:05,830
Så 64-bits arkitektur, det, igjen,
endringer som grunnleggende ting som en

172
00:08:05,830 --> 00:08:08,910
pekeren er nå 64 bits.

173
00:08:08,910 --> 00:08:09,290
Yeah.

174
00:08:09,290 --> 00:08:10,930
Så en peker er 8 byte.

175
00:08:10,930 --> 00:08:15,420
Så disse som var 4 byte
kommer til å være 8 byte.

176
00:08:15,420 --> 00:08:18,617
En student, som var to pekere,
vel, nå kommer det til å

177
00:08:18,617 --> 00:08:19,800
være 8 byte, 8 byte.

178
00:08:19,800 --> 00:08:21,980
Det kommer til å gjøre 16 bytes.

179
00:08:21,980 --> 00:08:25,710
>> Men en node er fortsatt fire byte.

180
00:08:25,710 --> 00:08:27,800
Så denne pekeren kommer
å være 8 byte.

181
00:08:27,800 --> 00:08:28,930
Dette er 4 byte.

182
00:08:28,930 --> 00:08:30,870
Så en node er bare kommer
å være 12 bytes.

183
00:08:30,870 --> 00:08:36,309

184
00:08:36,309 --> 00:08:39,280
Eventuelle andre spørsmål om den?

185
00:08:39,280 --> 00:08:44,500
Så den neste, disse er
HTTP statuskoder.

186
00:08:44,500 --> 00:08:48,000
Og du måtte beskrive forhold
under hvilke disse kan

187
00:08:48,000 --> 00:08:49,810
bli returnert til deg.

188
00:08:49,810 --> 00:08:56,730
ett problem som jeg hørte noen studenter
har er at de forsøkte å gjøre

189
00:08:56,730 --> 00:08:58,950
feil være på kundens slutten.

190
00:08:58,950 --> 00:09:02,320
Så når vi prøver å gjøre forespørselen
til serveren, går noe

191
00:09:02,320 --> 00:09:03,820
feil på vår side.

192
00:09:03,820 --> 00:09:07,660
Men generelt, disse kodene er
som returneres av serveren.

193
00:09:07,660 --> 00:09:11,720
Så vi ønsker å finne ut hva som skjer
galt eller rett på serveren som

194
00:09:11,720 --> 00:09:14,280
forårsaker disse tingene for å bli returnert.

195
00:09:14,280 --> 00:09:18,670
Så hvorfor kan en server avkastning
statuskode 200?

196
00:09:18,670 --> 00:09:19,920
Noen tanker?

197
00:09:19,920 --> 00:09:23,360

198
00:09:23,360 --> 00:09:23,730
>> Yeah.

199
00:09:23,730 --> 00:09:27,850
Så noe om hell
forespørselen gikk gjennom.

200
00:09:27,850 --> 00:09:30,260
Og de er i stand til å returnere
uansett hva du spurte om.

201
00:09:30,260 --> 00:09:32,240
Så alt var fint.

202
00:09:32,240 --> 00:09:35,662
Hva med 302 funnet?

203
00:09:35,662 --> 00:09:36,618
Yeah.

204
00:09:36,618 --> 00:09:39,008
>> PUBLIKUM: Serveren var ute
for det du ba om.

205
00:09:39,008 --> 00:09:40,442
Men det kunne ikke finne den.

206
00:09:40,442 --> 00:09:42,850
Så det er en feil.

207
00:09:42,850 --> 00:09:47,720
>> ROB BOWDEN: Så var serveren
på jakt etter hva du ville.

208
00:09:47,720 --> 00:09:51,682
Så bare ser her, 302 funnet,
det var i stand til å finne den.

209
00:09:51,682 --> 00:09:53,035
>> PUBLIKUM: Jeg beklager.

210
00:09:53,035 --> 00:09:54,388
Funnet betyr at de fant det.

211
00:09:54,388 --> 00:09:55,638
Unnskyld.

212
00:09:55,638 --> 00:09:58,120

213
00:09:58,120 --> 00:10:00,160
>> ROB BOWDEN: Så 302 funnet.

214
00:10:00,160 --> 00:10:02,350
Tjeneren er i stand til å finne
hva du ville.

215
00:10:02,350 --> 00:10:04,640
>> PUBLIKUM: Men det er ikke å vise det?

216
00:10:04,640 --> 00:10:08,180
>> ROB BOWDEN: Forskjellen mellom
Dette 302 og 200 er at den

217
00:10:08,180 --> 00:10:09,280
vet hva du ønsker.

218
00:10:09,280 --> 00:10:12,000
Men det er ikke akkurat der
du ønsket å spørre.

219
00:10:12,000 --> 00:10:14,580
Så 302 er en typisk redirect.

220
00:10:14,580 --> 00:10:16,510
Så du har bedt om en side.

221
00:10:16,510 --> 00:10:19,590
Det vet, oh, jeg vil
å returnere deg dette.

222
00:10:19,590 --> 00:10:21,070
Men dette er på en annen nettadresse.

223
00:10:21,070 --> 00:10:23,534
Så hei, du faktisk ønsker dette.

224
00:10:23,534 --> 00:10:26,950
>> DAVID J. MALAN: Det er et stykke som sa
at vi ga dere en redirect

225
00:10:26,950 --> 00:10:30,830
funksjon som brukes overskriften funksjon
som, i sin tur, trykket ut plassering,

226
00:10:30,830 --> 00:10:34,110
kolon, og deretter webadressen
du ønsker å avvise brukeren.

227
00:10:34,110 --> 00:10:37,480
Selv om du ikke ser 302
eksplisitt der, er at hva PHP

228
00:10:37,480 --> 00:10:41,550
ville magisk sett som header
si nøyaktig hva Rob sa det -

229
00:10:41,550 --> 00:10:41,930
funnet.

230
00:10:41,930 --> 00:10:43,180
Men gå her i stedet.

231
00:10:43,180 --> 00:10:45,960

232
00:10:45,960 --> 00:10:46,160
>> ROB BOWDEN: OK.

233
00:10:46,160 --> 00:10:47,630
Så hva med 403 forbudt?

234
00:10:47,630 --> 00:10:52,240

235
00:10:52,240 --> 00:10:57,120
>> PUBLIKUM: Jeg tror det er at serveren
er i utgangspunktet si at klienten

236
00:10:57,120 --> 00:10:59,970
får ikke tilgang til hjemmesiden.

237
00:10:59,970 --> 00:11:03,260
>> ROB BOWDEN: Så ja.

238
00:11:03,260 --> 00:11:07,670
Vel, den typiske svaret vi var
forventer er noe som, filene

239
00:11:07,670 --> 00:11:08,920
ikke oppgitt korrekte rettigheter på riktig måte.

240
00:11:08,920 --> 00:11:11,590
Det er trolig under hvilke omstendigheter
du så dem.

241
00:11:11,590 --> 00:11:18,920
Men det er en grunn til at klienten
kunne være på feil her.

242
00:11:18,920 --> 00:11:20,440
Det er faktisk en annen statuskode -

243
00:11:20,440 --> 00:11:21,210
401.

244
00:11:21,210 --> 00:11:22,820
Så disse er svært like.

245
00:11:22,820 --> 00:11:24,590
>> 401 er uautorisert.

246
00:11:24,590 --> 00:11:26,130
Og 403 er forbudt.

247
00:11:26,130 --> 00:11:31,890
Og så uautorisert du utelukkende
få hvis du ikke er logget inn

248
00:11:31,890 --> 00:11:34,520
Men å logge inn kan bety
at du er autorisert.

249
00:11:34,520 --> 00:11:37,930
Men hvis du allerede er logget på, og du
fremdeles ikke har tillatelse, så

250
00:11:37,930 --> 00:11:40,140
du kan også få forbudt.

251
00:11:40,140 --> 00:11:45,320
Så hvis du er logget inn og ikke har
tillatelse, er også forbudt

252
00:11:45,320 --> 00:11:47,164
noe du kan få.

253
00:11:47,164 --> 00:11:48,900
>> DAVID J. MALAN: Og den mekanismen
som disse problemene er vanligvis

254
00:11:48,900 --> 00:11:53,100
løst på serveren er
via hvilken kommando?

255
00:11:53,100 --> 00:11:57,700
Chmod, hvis det er faktisk en tillatelser
utstede på filen eller katalogen.

256
00:11:57,700 --> 00:11:59,220
>> ROB BOWDEN: Da 404 ikke funnet.

257
00:11:59,220 --> 00:12:03,100

258
00:12:03,100 --> 00:12:03,470
Yeah.

259
00:12:03,470 --> 00:12:10,150
Så i motsetning til 302 hvor det var ikke akkurat
hvor du spør, men det vet hva

260
00:12:10,150 --> 00:12:12,710
du ønsker, dette, det bare har
ingen anelse om hva du ønsker.

261
00:12:12,710 --> 00:12:15,648
Og du ikke ber om
noe gyldig.

262
00:12:15,648 --> 00:12:18,580

263
00:12:18,580 --> 00:12:22,310
418 Jeg er en tekanne og deretter
500 interne server.

264
00:12:22,310 --> 00:12:24,870
Så hvorfor kan du få det?

265
00:12:24,870 --> 00:12:26,120
>> Så segfault -

266
00:12:26,120 --> 00:12:28,760

267
00:12:28,760 --> 00:12:30,640
Jeg faktisk ikke vet gradering
standard for dette.

268
00:12:30,640 --> 00:12:34,850
Men hvis din PHP-koden hadde noe
galt i det, i teorien, det kunne

269
00:12:34,850 --> 00:12:39,650
faktisk segfault, i så fall, dette
500 Internal Server Error, noe

270
00:12:39,650 --> 00:12:41,400
er galt med serverens
konfigurasjon.

271
00:12:41,400 --> 00:12:44,320
Eller er det en syntaksfeil
i din PHP-kode.

272
00:12:44,320 --> 00:12:46,095
Eller noe ille som skjer.

273
00:12:46,095 --> 00:12:48,320
>> DAVID J. MALAN: Vi fikk se segfault
blant noen få folks svar.

274
00:12:48,320 --> 00:12:49,490
Og teknisk sett, kunne det skje.

275
00:12:49,490 --> 00:12:53,820
Men det ville være en PHP, programmet
skrevet av andre mennesker, faktisk

276
00:12:53,820 --> 00:12:57,790
segfaulted, som bare hvis disse menneskene
skrudd opp og skrev buggy kode i

277
00:12:57,790 --> 00:13:00,680
deres tolk ville
PHP selv segfault.

278
00:13:00,680 --> 00:13:06,460
Så selv om 500 er som en segfault
i ånden, er det nesten alltid

279
00:13:06,460 --> 00:13:10,490
Resultatet av en konfigurasjonsfil problem
med webserveren eller, som Rob sa,

280
00:13:10,490 --> 00:13:13,200
en syntaksfeil, som deg
ikke lukke et tilbud.

281
00:13:13,200 --> 00:13:16,180
Eller du mistet et semikolon et sted.

282
00:13:16,180 --> 00:13:23,677
>> PUBLIKUM: Så for Shuttle PSett, jeg
tror når jeg gjorde det en gang jeg klikket

283
00:13:23,677 --> 00:13:26,300
leseren, men ingenting kom opp,
det de kalte hvit side.

284
00:13:26,300 --> 00:13:28,056
Men det var på grunn av koden.

285
00:13:28,056 --> 00:13:29,440
Jeg tror det var Javascript, ikke sant?

286
00:13:29,440 --> 00:13:29,770
>> ROB BOWDEN: Yeah.

287
00:13:29,770 --> 00:13:31,180
>> PUBLIKUM: Vil at feilen
fortsatt komme opp?

288
00:13:31,180 --> 00:13:34,290
>> ROB BOWDEN: Så du ville ikke ha fått
denne feilen fordi alt

289
00:13:34,290 --> 00:13:36,930
fra webserveren perspektiv
var helt greit.

290
00:13:36,930 --> 00:13:39,090
Men du ba index.html.

291
00:13:39,090 --> 00:13:42,000
Du har bedt om shuttle.js
og service.js.

292
00:13:42,000 --> 00:13:44,580
Og det var i stand til å vende tilbake
til dere alle disse tingene -

293
00:13:44,580 --> 00:13:44,980
200.

294
00:13:44,980 --> 00:13:45,680
OK.

295
00:13:45,680 --> 00:13:49,330
Det er bare når nettleseren forsøkte å
tolke Javascript-kode som

296
00:13:49,330 --> 00:13:51,370
Det er som, vent, dette er ikke
gyldig Javascript-feil.

297
00:13:51,370 --> 00:13:55,720

298
00:13:55,720 --> 00:13:58,210
Eventuelle andre spørsmål?

299
00:13:58,210 --> 00:14:00,750
OK.

300
00:14:00,750 --> 00:14:04,120
>> DAVID J. MALAN: Så neste
opp var nummer 11.

301
00:14:04,120 --> 00:14:07,610
Og 11 var den skumleste
for mange mennesker.

302
00:14:07,610 --> 00:14:14,620

303
00:14:14,620 --> 00:14:18,570
Så det viktigste å merke seg her
, var at dette var, ja, om

304
00:14:18,570 --> 00:14:19,840
en dobbelt lenket liste.

305
00:14:19,840 --> 00:14:23,160
Men dette var ikke det samme som fjorårets
dobbelt lenket liste problem,

306
00:14:23,160 --> 00:14:27,170
som ikke gir deg det forbeholdet at
listen kunne faktisk være usortert.

307
00:14:27,170 --> 00:14:29,640
>> Så det faktum at listen var usortert
og det faktum at det ordet var

308
00:14:29,640 --> 00:14:32,930
understreket det var ment å formidle
at dette er faktisk en forenkling

309
00:14:32,930 --> 00:14:35,430
av hva som ellers ville ha vært
en mer utfordrende problem

310
00:14:35,430 --> 00:14:36,600
og en lengre.

311
00:14:36,600 --> 00:14:40,760
Så en vanlig feil her var å ha satt
fjorårets løsning på en

312
00:14:40,760 --> 00:14:45,580
personsøker og deretter bare blindt kopiere den
ned som svar, som er den høyre

313
00:14:45,580 --> 00:14:48,520
svare på et annet spørsmål
lignende i ånden.

314
00:14:48,520 --> 00:14:51,340
Men spissfindigheter her
var som følger.

315
00:14:51,340 --> 00:14:55,200
>> Så, vi har en node erklært og
definert på vanlig måte her.

316
00:14:55,200 --> 00:14:59,230
Da vi definert liste over være en global
pekeren initialisert til null.

317
00:14:59,230 --> 00:15:02,150
Så tydeligvis er det to funksjoner
vi har prototyper for her, insert

318
00:15:02,150 --> 00:15:03,240
og fjern.

319
00:15:03,240 --> 00:15:06,600
Og så har vi noen eksempelkode her
av å gjøre en haug med innsettinger.

320
00:15:06,600 --> 00:15:09,930
Og så ber vi deg om å fullføre
gjennomføring av innsatsen under på en slik

321
00:15:09,930 --> 00:15:14,380
en slik måte at den setter n inn i listen
i konstant tid, også understreket,

322
00:15:14,380 --> 00:15:15,730
selv om allerede er til stede.

323
00:15:15,730 --> 00:15:20,600
>> Så det fine med å være i stand til å sette inn
i konstant tid er at det innebærer

324
00:15:20,600 --> 00:15:23,060
at du må sette inn
den nye noden der?

325
00:15:23,060 --> 00:15:23,690
Inn i det fram.

326
00:15:23,690 --> 00:15:27,760
Så det eliminerer, heldigvis, i hvert fall
en av de tilfeller som tidligere krevde

327
00:15:27,760 --> 00:15:30,520
enda flere linjer med kode, som det gjorde
i fjor, og selv i klassen når vi

328
00:15:30,520 --> 00:15:34,040
snakket gjennom denne type ting
med mennesker og med noen

329
00:15:34,040 --> 00:15:35,250
verbal pseudo-kode.

330
00:15:35,250 --> 00:15:39,190
Så i løsningen her, la oss hoppe over
I tillegg bare for å ha en visuell on

331
00:15:39,190 --> 00:15:40,480
skjermen.

332
00:15:40,480 --> 00:15:42,230
>> Legg merke til at vi gjør følgende.

333
00:15:42,230 --> 00:15:45,140
Og også legge merke til den andre forenkling
var at selv om det er

334
00:15:45,140 --> 00:15:48,280
allerede til stede, så dette betyr at selv om
nummeret allerede er der, du kan

335
00:15:48,280 --> 00:15:50,280
bare blindt sette inn en annen
kopi av den.

336
00:15:50,280 --> 00:15:52,560
Og det, også, var ment å være en
forenkling, slik at du kan

337
00:15:52,560 --> 00:15:54,940
fokusere på, virkelig, noen av de mer
intellektuelt interessant del og

338
00:15:54,940 --> 00:15:58,090
ikke bare noen ekstra feilkontroll
gitt begrenset tid.

339
00:15:58,090 --> 00:16:02,880
>> Så i denne prøveoppløsning, vi fordele
en peker til venstre hånd

340
00:16:02,880 --> 00:16:04,510
side her til en node.

341
00:16:04,510 --> 00:16:07,190
Nå innser at pekeren, som
Rob sa, er bare 32 bits.

342
00:16:07,190 --> 00:16:09,060
Og det gjør faktisk ikke inneholder
en adresse til deg

343
00:16:09,060 --> 00:16:09,970
tilordne den adressen.

344
00:16:09,970 --> 00:16:13,220
Og vi gjør det på høyre hånd
side via malloc.

345
00:16:13,220 --> 00:16:16,550
Som en god borger, sjekker vi at
malloc ikke er i virkeligheten null, slik at

346
00:16:16,550 --> 00:16:18,690
vi ikke tilfeldigvis lage
en segfault her.

347
00:16:18,690 --> 00:16:22,840
Og hver gang du bruker malloc i livet, du
bør sjekke for null, så

348
00:16:22,840 --> 00:16:24,090
du har en subtil feil.

349
00:16:24,090 --> 00:16:28,460
>> Da vi initial at null ved
tildele n og forrige og neste år.

350
00:16:28,460 --> 00:16:32,450
Og i dette tilfellet her, jeg initialisert
tidligere til null, fordi denne nye

351
00:16:32,450 --> 00:16:34,780
node kommer til å bli den nye
begynnelsen av listen min.

352
00:16:34,780 --> 00:16:37,050
Så det kommer til å bli
ingenting før det.

353
00:16:37,050 --> 00:16:42,010
Og jeg vil egentlig tilføye
eksisterende liste til den nye noden ved

354
00:16:42,010 --> 00:16:44,700
innstilling neste lik å liste seg selv.

355
00:16:44,700 --> 00:16:47,120
Men jeg er ikke ferdig ennå.

356
00:16:47,120 --> 00:16:51,780
Så hvis selve lista allerede eksisterte,
og det var i det minste en node

357
00:16:51,780 --> 00:16:57,070
som allerede er på plass, hvis dette er en liste
her og jeg setter inn en ny node her, jeg

358
00:16:57,070 --> 00:17:01,840
må sørge for at min tidligere node
peker bakover til min nye noden,

359
00:17:01,840 --> 00:17:04,260
fordi denne er igjen
en dobbelt lenket liste.

360
00:17:04,260 --> 00:17:05,460
>> Så vi gjør en mental helse sjekk.

361
00:17:05,460 --> 00:17:10,109
Hvis listen er ikke null, hvis det er allerede
en eller flere noder der, og deretter

362
00:17:10,109 --> 00:17:12,470
legge til at tilbake henvisning så å si.

363
00:17:12,470 --> 00:17:15,420
Og så den aller siste vi trenger
å gjøre er å faktisk oppdatere den globale

364
00:17:15,420 --> 00:17:20,329
variabelliste selv å peke
til den nye noden.

365
00:17:20,329 --> 00:17:21,790
Yeah.

366
00:17:21,790 --> 00:17:26,579
>> PUBLIKUM: I pekeren pilen
[Uhørbart] er lik null, gjør at

367
00:17:26,579 --> 00:17:30,420
forholde seg til listen fordi
listen er null?

368
00:17:30,420 --> 00:17:30,596
>> DAVID J. MALAN: Nope.

369
00:17:30,596 --> 00:17:34,500
Det er rett og slett meg å være proaktivt
forsiktig, i at dersom dette er min

370
00:17:34,500 --> 00:17:38,730
opprinnelige listen med kanskje noen flere noder
over her og jeg setter min

371
00:17:38,730 --> 00:17:42,380
ny node over her, det kommer
å være noe over her.

372
00:17:42,380 --> 00:17:44,720
Og jeg ønsker å fange den tanken
ved å sette tidligere til

373
00:17:44,720 --> 00:17:47,740
null på den nye node.

374
00:17:47,740 --> 00:17:51,410
Og antagelig, hvis min kode er korrekt
og det er ingen annen måte å sette inn

375
00:17:51,410 --> 00:17:54,970
andre enn denne funksjonen noder,
formodentlig allerede har selv om liste

376
00:17:54,970 --> 00:18:00,090
en eller flere noder i den, formodentlig
listen, den første node, ville ha en

377
00:18:00,090 --> 00:18:02,750
forrige pekeren over null selv.

378
00:18:02,750 --> 00:18:03,550
>> PUBLIKUM: Og bare en oppfølging.

379
00:18:03,550 --> 00:18:08,139
Grunnen til at du setter markøren ved siden av likhets
Listen er du gjør pekeren

380
00:18:08,139 --> 00:18:13,579
før listen i at den peker
til den neste, tror jeg -

381
00:18:13,579 --> 00:18:14,980
Vet ikke, -

382
00:18:14,980 --> 00:18:15,450
bare lister?

383
00:18:15,450 --> 00:18:16,400
>> DAVID J. MALAN: Nettopp.

384
00:18:16,400 --> 00:18:19,400
Og så la oss faktisk vurdere to tilfeller
her egentlig, selv om

385
00:18:19,400 --> 00:18:22,070
For vi vil vurdere dem er ikke
helt det samme som koden.

386
00:18:22,070 --> 00:18:26,250
Men på et høyt nivå, dersom dette representerer
liste, og dette er en 32-bit

387
00:18:26,250 --> 00:18:29,560
pekeren, er den enkleste scenariet
at dette er null som standard.

388
00:18:29,560 --> 00:18:33,010
Og antar at jeg vil sette inn
nummer 50 var det første nummeret.

389
00:18:33,010 --> 00:18:37,640
Så jeg kommer til å gå videre og fordele
en node, som kommer til å inneholde

390
00:18:37,640 --> 00:18:38,770
tre felt -

391
00:18:38,770 --> 00:18:42,070
n, forrige, og neste.

392
00:18:42,070 --> 00:18:44,580
>> Jeg kommer til å sette nummer 50
her, fordi dette vil være n.

393
00:18:44,580 --> 00:18:46,130
Dette vil være neste.

394
00:18:46,130 --> 00:18:48,530
Og dette vil være tidligere.

395
00:18:48,530 --> 00:18:50,910
Og så hva må jeg gjøre i dette tilfellet?

396
00:18:50,910 --> 00:18:53,900
Vel, jeg har nettopp gjort linje 1 her.

397
00:18:53,900 --> 00:18:55,400
Pointer n blir n.

398
00:18:55,400 --> 00:18:57,740
Jeg så å si, tidligere
bør få null.

399
00:18:57,740 --> 00:18:59,470
Så dette kommer til å være null.

400
00:18:59,470 --> 00:19:01,365
Så jeg kommer til å si neste
kommer til å få listen.

401
00:19:01,365 --> 00:19:05,150
>> Og dette fungerer bare godt ut.

402
00:19:05,150 --> 00:19:06,500
Dette er null.

403
00:19:06,500 --> 00:19:10,620
Og så jeg sier, den nye noden neste
feltet bør få hva dette er.

404
00:19:10,620 --> 00:19:12,570
Så det setter en annen null der.

405
00:19:12,570 --> 00:19:14,510
Og så det siste
Jeg er sjekke her.

406
00:19:14,510 --> 00:19:17,870
Hvis listen ikke er lik null, men det
er lik null, så vi hoppe over den

407
00:19:17,870 --> 00:19:18,470
helt.

408
00:19:18,470 --> 00:19:23,520
Og så alt jeg gjøre neste er listen blir
pekeren, som billedlig resulterer i

409
00:19:23,520 --> 00:19:25,570
et bilde sånn.

410
00:19:25,570 --> 00:19:26,620
Så det er ett scenario.

411
00:19:26,620 --> 00:19:30,490
>> Og den du ble spurt om
spesielt er en situasjon som dette,

412
00:19:30,490 --> 00:19:33,190
der vi allerede har en ett-nodelisten.

413
00:19:33,190 --> 00:19:36,240
Og hvis jeg går tilbake i den opprinnelige
problemstilling, det neste vi vil

414
00:19:36,240 --> 00:19:39,320
sette inn si er 34, bare for
skyld diskusjonen.

415
00:19:39,320 --> 00:19:46,210
Så jeg kommer til å like praktisk
tegne det over her.

416
00:19:46,210 --> 00:19:47,540
Jeg har nettopp malloced.

417
00:19:47,540 --> 00:19:49,310
La oss anta jeg sjekker for null.

418
00:19:49,310 --> 00:19:51,870
>> Nå kommer jeg til å initialisere
n å være 34.

419
00:19:51,870 --> 00:19:53,040
Og dette vil være n.

420
00:19:53,040 --> 00:19:54,670
Dette vil være neste.

421
00:19:54,670 --> 00:19:57,100
Og dette vil være tidligere.

422
00:19:57,100 --> 00:19:59,370
La oss sørge for at jeg ikke gjorde det
få dette bakover.

423
00:19:59,370 --> 00:20:01,110
Forrige kommer først
i definisjonen.

424
00:20:01,110 --> 00:20:03,070
La meg fikse dette.

425
00:20:03,070 --> 00:20:04,410
Dette er forrige.

426
00:20:04,410 --> 00:20:05,780
Dette er neste.

427
00:20:05,780 --> 00:20:08,620
Selv om disse er identiske,
la oss holde det konsekvent.

428
00:20:08,620 --> 00:20:09,450
>> Forrige.

429
00:20:09,450 --> 00:20:11,030
Dette er neste.

430
00:20:11,030 --> 00:20:16,310
Så jeg har bare malloced mitt notat, sjekket
for null, tildelt 34 inn i noden.

431
00:20:16,310 --> 00:20:17,570
Forrige får null.

432
00:20:17,570 --> 00:20:19,480
Så det gir meg det.

433
00:20:19,480 --> 00:20:21,010
Neste blir listen.

434
00:20:21,010 --> 00:20:22,370
Så listen er dette.

435
00:20:22,370 --> 00:20:26,520
Så dette er den samme nå som å tegne denne
arrow, slik at de peker til en

436
00:20:26,520 --> 00:20:27,940
i samme.

437
00:20:27,940 --> 00:20:30,400
Og så sjekker jeg om liste
er ikke lik null.

438
00:20:30,400 --> 00:20:31,740
Og det er ikke denne gangen.

439
00:20:31,740 --> 00:20:35,580
Så jeg kommer til å gjøre listen
forrige får pekeren.

440
00:20:35,580 --> 00:20:39,700
>> Så listen forrige får PTR.

441
00:20:39,700 --> 00:20:44,300
Så dette har effekten av å sette
en grafisk pil her.

442
00:20:44,300 --> 00:20:46,930
Og det begynner å bli litt
bølget, linjene.

443
00:20:46,930 --> 00:20:50,780
Og så, til slutt, kan jeg oppdatere
liste for å peke på pekeren.

444
00:20:50,780 --> 00:20:55,560
Så nå dette peker til denne fyren.

445
00:20:55,560 --> 00:20:57,170
Og nå, la oss gjøre en rask
tilregnelighet sjekk.

446
00:20:57,170 --> 00:20:59,470
>> Her er listen, som er
den globale variabelen.

447
00:20:59,470 --> 00:21:02,850
Den første noden er faktisk 34, fordi
Jeg følger at pilen.

448
00:21:02,850 --> 00:21:05,210
Og det er riktig fordi jeg ønsker å
Sett på begynnelsen av listen

449
00:21:05,210 --> 00:21:06,070
alle nye noder.

450
00:21:06,070 --> 00:21:08,860
Hans neste felt fører meg til denne fyren.

451
00:21:08,860 --> 00:21:10,710
Hvis jeg fortsetter, jeg traff neste er null.

452
00:21:10,710 --> 00:21:11,760
Så det er ikke mer listen.

453
00:21:11,760 --> 00:21:14,460
Hvis jeg traff tidligere, får jeg
tilbake der jeg forventer.

454
00:21:14,460 --> 00:21:16,435
>> Så det er fortsatt noen tips,
åpenbart, for å manipulere.

455
00:21:16,435 --> 00:21:19,870
Men det faktum at du fikk beskjed om å gjøre
dette i konstant tid betyr at du bare

456
00:21:19,870 --> 00:21:22,910
har et endelig antall ting
du har lov til å gjøre.

457
00:21:22,910 --> 00:21:24,290
Og hva er det nummeret?

458
00:21:24,290 --> 00:21:25,185
Det kan være ett skritt.

459
00:21:25,185 --> 00:21:25,700
Det kan være to.

460
00:21:25,700 --> 00:21:26,820
Det kan være tusen trinn.

461
00:21:26,820 --> 00:21:30,500
Men det er begrenset, noe som betyr at du ikke kan
har noen form for looping skjer

462
00:21:30,500 --> 00:21:32,010
her, ingen rekursjon, ingen løkker.

463
00:21:32,010 --> 00:21:37,390
Det er bare nødt til å være hardkodede linjer
av kode som vi har i dette utvalget.

464
00:21:37,390 --> 00:21:42,330
>> Så neste problem 12 ba oss om å
fullføre implementeringen av remove

465
00:21:42,330 --> 00:21:46,740
nedenfor, på en slik måte at det fjerner
n fra listen i lineær tid.

466
00:21:46,740 --> 00:21:48,740
Så har du et litt mer
slingringsmonn nå.

467
00:21:48,740 --> 00:21:52,380
Du kan anta at n, hvis det finnes
i listen, vil være til stede

468
00:21:52,380 --> 00:21:53,340
ikke mer enn én gang.

469
00:21:53,340 --> 00:21:56,770
Og som også er ment å være en quiz-baserte
forenkle antakelse, så

470
00:21:56,770 --> 00:21:59,780
at hvis du finner nummeret 50 et sted
i listen, gjør du ikke også

471
00:21:59,780 --> 00:22:02,890
trenger å bekymre deg om å fortsette å
iterere, på jakt etter alle mulige

472
00:22:02,890 --> 00:22:06,990
kopi av 50, noe som bare ville devolve
inn noen småarbeidet i begrenset tid.

473
00:22:06,990 --> 00:22:10,460
>> Så med fjerne, var dette definitivt
mer utfordrende og mer

474
00:22:10,460 --> 00:22:11,640
kode for å skrive.

475
00:22:11,640 --> 00:22:14,990
Men ved første øyekast, ærlig, det kan
ser overveldende og som noe

476
00:22:14,990 --> 00:22:17,060
det er ingen måte du kan ha
komme opp med på en quiz.

477
00:22:17,060 --> 00:22:22,450
Men hvis vi fokuserer på de enkelte trinn,
Forhåpentligvis vil det plutselig

478
00:22:22,450 --> 00:22:26,060
slå deg at hver av disse individuelle
trinn gjør åpenbart fornuftig

479
00:22:26,060 --> 00:22:27,080
i ettertid.

480
00:22:27,080 --> 00:22:28,200
Så la oss ta en titt.

481
00:22:28,200 --> 00:22:32,570
>> Så først, initial vi pekeren
å være liste selv.

482
00:22:32,570 --> 00:22:36,040
Fordi jeg ønsker lineær tid, det betyr
Jeg kommer til å ha noen sløyfe.

483
00:22:36,040 --> 00:22:39,730
Og en felles måte å iterere over
noder i en listestruktur eller en hvilken som helst form

484
00:22:39,730 --> 00:22:43,860
av struktur iterativt er å ta
en peker til forsiden av data

485
00:22:43,860 --> 00:22:46,990
struktur og så bare begynne å oppdatere
det og gå din vei

486
00:22:46,990 --> 00:22:48,650
via datastruktur.

487
00:22:48,650 --> 00:22:50,040
Så jeg kommer til å gjøre akkurat det.

488
00:22:50,040 --> 00:22:54,260
>> Mens pekeren, min midlertidig variabel,
er ikke lik null, la oss

489
00:22:54,260 --> 00:22:55,660
gå videre og sjekke.

490
00:22:55,660 --> 00:22:56,910
Fikk jeg heldig?

491
00:22:56,910 --> 00:23:01,740
Er det n-feltet i node Jeg er for tiden
ser på lik

492
00:23:01,740 --> 00:23:03,380
nummer jeg leter etter?

493
00:23:03,380 --> 00:23:05,410
Og hvis så, la oss gjøre noe.

494
00:23:05,410 --> 00:23:10,020
Nå merke dette hvis tilstanden
omgir hele

495
00:23:10,020 --> 00:23:11,520
Følgende linjer med kode.

496
00:23:11,520 --> 00:23:14,610
Dette er det eneste jeg bryr meg om -
å finne et antall aktuelle.

497
00:23:14,610 --> 00:23:18,010
Så det er ingen andre, noe som forenkler
ting konseptuelt litt.

498
00:23:18,010 --> 00:23:22,040
>> Men nå, innså jeg, og du kan ha
bare innsett dette etter å ha tenkt

499
00:23:22,040 --> 00:23:24,720
det gjennom en bit, det er
faktisk to tilfeller her.

500
00:23:24,720 --> 00:23:28,060
Den ene er hvor noden er på baks
begynnelsen av listen, som er en

501
00:23:28,060 --> 00:23:31,040
litt irriterende, fordi det er en
spesielt tilfelle, fordi du har å forholde

502
00:23:31,040 --> 00:23:33,340
med denne tingen, som
er det eneste avvik.

503
00:23:33,340 --> 00:23:35,720
Alle andre steder i listen,
det er den samme tingen.

504
00:23:35,720 --> 00:23:38,050
Det er en tidligere node og en neste
node, forrige node, neste node.

505
00:23:38,050 --> 00:23:40,940
Men denne fyren er en litt spesiell
hvis han er i begynnelsen.

506
00:23:40,940 --> 00:23:48,710
>> Så dersom pekeren er lik listen
seg selv, så hvis jeg er i begynnelsen av

507
00:23:48,710 --> 00:23:53,960
listen, og jeg har funnet n, jeg trenger
å gjøre et par ting.

508
00:23:53,960 --> 00:23:59,230
En, må jeg endre listen til
peke til neste felt, 50.

509
00:23:59,230 --> 00:24:01,270
Så antar at jeg prøver
å fjerne 34.

510
00:24:01,270 --> 00:24:03,560
Så denne fyren har å gå
bort på bare et øyeblikk.

511
00:24:03,560 --> 00:24:07,210
>> Så jeg kommer til å si, liste
blir markøren ved siden av.

512
00:24:07,210 --> 00:24:08,570
Vel, er denne pekeren.

513
00:24:08,570 --> 00:24:10,360
Neste peker over her.

514
00:24:10,360 --> 00:24:17,470
Så dette er i endring denne pilen til høyre
nå å peke på denne fyren her.

515
00:24:17,470 --> 00:24:19,580
Nå, husk at vi har
en midlertidig variabel.

516
00:24:19,580 --> 00:24:23,520
Så vi ikke har foreldreløse noen noder,
fordi jeg har også denne fyren i min

517
00:24:23,520 --> 00:24:25,010
gjennomføring av remove.

518
00:24:25,010 --> 00:24:29,600
Så nå, er hvis listen selv ikke null,
Jeg trenger å fikse litt noe.

519
00:24:29,600 --> 00:24:32,690
>> Jeg må nå sørge for at denne pilen,
som er tidligere peker

520
00:24:32,690 --> 00:24:36,830
50-34, har dette å gå bort,
fordi hvis jeg prøver å bli kvitt

521
00:24:36,830 --> 00:24:41,910
av 34, 50 hadde bedre ikke opprettholde noen
slags tilbake henvisning til det som

522
00:24:41,910 --> 00:24:42,820
pil foreslått.

523
00:24:42,820 --> 00:24:44,820
Så jeg bare gjorde denne linjen.

524
00:24:44,820 --> 00:24:46,520
Så da er jeg ferdig.

525
00:24:46,520 --> 00:24:48,040
Den saken er faktisk ganske enkelt.

526
00:24:48,040 --> 00:24:51,010
Hakking hodet av listen
er relativt ukomplisert.

527
00:24:51,010 --> 00:24:52,980
>> Dessverre, det er dette
irriterende annet blokk.

528
00:24:52,980 --> 00:24:56,170
Så nå må jeg vurdere saken
hvor det er noe i midten.

529
00:24:56,170 --> 00:24:59,880
Men det er ikke så forferdelig, med unntak
for syntaks som dette.

530
00:24:59,880 --> 00:25:03,080
Så hvis jeg ikke er i begynnelsen av
liste, jeg er et sted i midten.

531
00:25:03,080 --> 00:25:08,160
Og denne linjen her sier, start
uansett hvilken node du er på.

532
00:25:08,160 --> 00:25:11,210

533
00:25:11,210 --> 00:25:18,550
Gå til forrige node neste felt
og peker på at på pekeren.

534
00:25:18,550 --> 00:25:20,390
>> La oss gjøre dette billedlig.

535
00:25:20,390 --> 00:25:21,640
Det begynte å bli komplisert.

536
00:25:21,640 --> 00:25:30,480

537
00:25:30,480 --> 00:25:37,990
Så hvis jeg har en tidligere felt her -
la oss gjøre dette - neste felt her.

538
00:25:37,990 --> 00:25:41,200
Jeg kommer til å forenkle mine pekere heller
enn tegne en hel haug med

539
00:25:41,200 --> 00:25:45,710
ting frem og tilbake på kryss og tvers
hverandre.

540
00:25:45,710 --> 00:25:50,870
Og nå, la oss bare si at dette er en, to,
3 av hensyn til diskusjonen, selv

541
00:25:50,870 --> 00:25:53,410
selv om det ikke er på linje med
angjeldende problem.

542
00:25:53,410 --> 00:25:55,900
>> Så her er min lenket liste.

543
00:25:55,900 --> 00:25:59,300
Jeg prøver å fjerne to i denne
bestemt versjon av historien.

544
00:25:59,300 --> 00:26:01,960
Så jeg har oppdatert pekeren til
peke mot denne fyren.

545
00:26:01,960 --> 00:26:03,315
Så dette er PTR.

546
00:26:03,315 --> 00:26:04,530
Han peker her.

547
00:26:04,530 --> 00:26:07,170
Dette er listen, som eksisterer
globalt som før.

548
00:26:07,170 --> 00:26:09,200
Og han peker her uansett hva.

549
00:26:09,200 --> 00:26:10,800
Og nå, jeg prøver å fjerne to.

550
00:26:10,800 --> 00:26:13,850
>> Så hvis pilen peker her, jeg
kommer til å følge, tilsynelatende, den

551
00:26:13,850 --> 00:26:17,110
forrige pekeren, som setter meg på en.

552
00:26:17,110 --> 00:26:22,290
Jeg deretter kommer til å si at neste
feltet, noe som bringer meg over til dette

553
00:26:22,290 --> 00:26:25,410
boksen her, kommer til å
lik markøren ved siden av.

554
00:26:25,410 --> 00:26:28,400
Så hvis denne pekeren, er dette neste.

555
00:26:28,400 --> 00:26:31,840
Det betyr at denne pilen behov
å peke på denne fyren.

556
00:26:31,840 --> 00:26:35,140
>> Så hva som kodelinje har bare
gjort er en liten bit av dette.

557
00:26:35,140 --> 00:26:37,500
Og nå, dette ser ut som en
skritt i riktig retning.

558
00:26:37,500 --> 00:26:41,390
Vi egentlig ønsker å avklipt to ut
av midt i en og tre.

559
00:26:41,390 --> 00:26:44,400
Derfor er det fornuftig at vi ønsker å
rute denne pekeren rundt det.

560
00:26:44,400 --> 00:26:50,400
Så dette neste linje er å sjekke om pekeren
neste er ikke null, det er

561
00:26:50,400 --> 00:26:54,200
faktisk noen til høyre på 2,
det betyr at vi også må gjøre

562
00:26:54,200 --> 00:26:55,850
et lite klipp her.

563
00:26:55,850 --> 00:27:00,590
>> Så jeg trenger nå å følge denne pekeren
og oppdatere forrige pekeren på

564
00:27:00,590 --> 00:27:05,410
denne fyren å gjøre en liten bit av en
omgå her poenget her.

565
00:27:05,410 --> 00:27:07,100
Og nå, visuelt dette er fint.

566
00:27:07,100 --> 00:27:11,930
Det er litt rotete i at det er
ingen peker på to lenger.

567
00:27:11,930 --> 00:27:13,600
2 peker til venstre.

568
00:27:13,600 --> 00:27:14,980
Og to peker mot høyre.

569
00:27:14,980 --> 00:27:17,480
Men han kan gjøre hva han vil, fordi
han er i ferd med å bli frigjort.

570
00:27:17,480 --> 00:27:19,480
Og det spiller ingen rolle hva
disse verdiene er lenger.

571
00:27:19,480 --> 00:27:23,040
>> Det som er viktig er at de resterende
gutta er ruting ovenfor

572
00:27:23,040 --> 00:27:24,280
og under ham nå.

573
00:27:24,280 --> 00:27:25,810
Og ja, det er hva vi skal gjøre videre.

574
00:27:25,810 --> 00:27:29,360
Vi gratis pekeren, noe som betyr at vi fortelle
operativsystem, er du velkommen

575
00:27:29,360 --> 00:27:30,906
å gjenvinne denne.

576
00:27:30,906 --> 00:27:34,900
Og så til slutt, går vi tilbake.

577
00:27:34,900 --> 00:27:37,220
Else implisitt, hvis vi
har ikke kommet tilbake ennå,

578
00:27:37,220 --> 00:27:38,290
vi er nødt til å holde utkikk.

579
00:27:38,290 --> 00:27:41,485
Så pekeren tilsvarer markøren ved bare
betyr flytte denne fyren her.

580
00:27:41,485 --> 00:27:42,600
Flytt denne fyren her.

581
00:27:42,600 --> 00:27:45,400
Flytt denne fyren her hvis, faktisk,
vi fant ikke nummeret

582
00:27:45,400 --> 00:27:46,960
vi leter etter enda.

583
00:27:46,960 --> 00:27:49,630
>> Så ærlig, ser det helt
overveldende, tror jeg, i første

584
00:27:49,630 --> 00:27:52,180
øyekast, spesielt hvis du kjempet
med dette i løpet av quiz deretter se

585
00:27:52,180 --> 00:27:52,850
noe sånt som dette.

586
00:27:52,850 --> 00:27:55,050
Og du klappe deg selv på ryggen.

587
00:27:55,050 --> 00:27:57,080
Vel, det er ingen måte jeg kunne ha
komme opp med det på quiz.

588
00:27:57,080 --> 00:28:00,470
Men jeg vil hevde, du kan hvis du bryte
det ned i disse individuelle

589
00:28:00,470 --> 00:28:04,400
saker og bare gå gjennom det
nøye, riktignok, riktignok under

590
00:28:04,400 --> 00:28:06,300
stressende omstendigheter.

591
00:28:06,300 --> 00:28:09,470
>> Heldigvis, bilde laget
alt lykkeligere.

592
00:28:09,470 --> 00:28:11,050
Du kan trekke dette i
en rekke måter.

593
00:28:11,050 --> 00:28:12,760
Du trenger ikke å gjøre det crisscrossing
tingen her.

594
00:28:12,760 --> 00:28:14,520
Du kan gjøre det med rett
linjer som dette.

595
00:28:14,520 --> 00:28:18,790
Men hovedpunkt av dette problemet, i
Generelt, var til å innse at den

596
00:28:18,790 --> 00:28:22,060
Bildet til slutt skal se litt
noe sånt som dette, fordi

597
00:28:22,060 --> 00:28:25,030
konstant tid underforstått at du holder
jamming og jamming og jamming

598
00:28:25,030 --> 00:28:29,900
nye noder i begynnelsen
av listen.

599
00:28:29,900 --> 00:28:31,960
Eventuelle spørsmål?

600
00:28:31,960 --> 00:28:34,565
Sannsynligvis den mest utfordrende av
sikkert koding spørsmål.

601
00:28:34,565 --> 00:28:37,690
>> PUBLIKUM: Så er liste som ligner på
høyest i tidligere eksempler.

602
00:28:37,690 --> 00:28:39,640
>> DAVID J. MALAN: Akkurat, akkurat.

603
00:28:39,640 --> 00:28:43,130
Bare et annet navn for
en global variabel.

604
00:28:43,130 --> 00:28:44,380
World wide hva?

605
00:28:44,380 --> 00:28:48,880

606
00:28:48,880 --> 00:28:49,730
>> ROB BOWDEN: OK.

607
00:28:49,730 --> 00:28:52,020
Så dette er en hvor du
måtte skrive avsnittet.

608
00:28:52,020 --> 00:28:56,060
Noen mennesker skrev essays
for dette spørsmålet.

609
00:28:56,060 --> 00:29:00,230
Men du trenger bare å bruke disse seks vilkår
å beskrive hva som skjer når

610
00:29:00,230 --> 00:29:02,440
du prøver å kontakte facebook.com.

611
00:29:02,440 --> 00:29:07,930
Så jeg vil bare snakke gjennom prosessen
ved hjelp av alle disse begrepene.

612
00:29:07,930 --> 00:29:11,290
Så i nettleseren vår, vi skriver facebook.com
og trykk Enter.

613
00:29:11,290 --> 00:29:17,280
Så leseren vår kommer til å konstruere en
HTTP be om at det kommer til å sende

614
00:29:17,280 --> 00:29:22,220
gjennom noen prosess på Facebook for
Facebook til å svare på oss med

615
00:29:22,220 --> 00:29:24,450
HTML sin side.

616
00:29:24,450 --> 00:29:28,800
>> Så hva er den prosessen
som HTTP-forespørsel

617
00:29:28,800 --> 00:29:30,730
faktisk kommer til Facebook?

618
00:29:30,730 --> 00:29:32,790
Så først må vi oversette
Facebook.com.

619
00:29:32,790 --> 00:29:38,780
Så bare gitt navnet Facebook.com,
der faktisk gjør HTTP-forespørsel

620
00:29:38,780 --> 00:29:39,940
trenger å gå?

621
00:29:39,940 --> 00:29:44,120
Så vi trenger å oversette Facebook.com
til en IP-adresse, som unikt

622
00:29:44,120 --> 00:29:47,620
identifiserer hvilken maskin vi egentlig
ønsker å sende denne forespørselen til.

623
00:29:47,620 --> 00:29:49,310
Din bærbare har en IP-adresse.

624
00:29:49,310 --> 00:29:52,240
Alt som er koblet til internett
har en IP-adresse.

625
00:29:52,240 --> 00:29:59,030
>> Så DNS, Domain Name System, er at
hva som kommer til å håndtere oversettelse

626
00:29:59,030 --> 00:30:03,750
fra facebook.com til en IP-adresse som
du faktisk ønsker å kontakte.

627
00:30:03,750 --> 00:30:08,075
Så vi kontakte DNS-serverne og
si, hva er facebook.com?

628
00:30:08,075 --> 00:30:16,560
Den sier, oh, er det IP-adressen 190,212
noe, noe, noe.

629
00:30:16,560 --> 00:30:16,900
OK.

630
00:30:16,900 --> 00:30:18,850
Nå, jeg vet hva maskin
Jeg ønsker å ta kontakt.

631
00:30:18,850 --> 00:30:22,360
>> Så da du sende HTTP-forespørsel
over til den maskinen.

632
00:30:22,360 --> 00:30:24,140
Så hvordan få det til at maskinen?

633
00:30:24,140 --> 00:30:27,200
Vel, går forespørselen fra
ruter til ruter retur.

634
00:30:27,200 --> 00:30:32,630
Husk eksemplet i klassen, der
vi faktisk så den ruten som

635
00:30:32,630 --> 00:30:35,340
pakker tok da vi prøvde
å kommunisere.

636
00:30:35,340 --> 00:30:38,460
Vi så det hopper over Atlanterhavet
Ocean på ett punkt eller hva.

637
00:30:38,460 --> 00:30:42,820
>> Så det siste leddet port.

638
00:30:42,820 --> 00:30:46,520
Så dette er nå på datamaskinen.

639
00:30:46,520 --> 00:30:49,970
Du kan ha flere ting i dag
kommunisere med internett.

640
00:30:49,970 --> 00:30:53,730
Så jeg kan være i gang, sier Skype.

641
00:30:53,730 --> 00:30:55,670
Jeg kan ha en nettleser åpen.

642
00:30:55,670 --> 00:30:59,010
Jeg kan ha noe som
torren filer.

643
00:30:59,010 --> 00:31:00,880
Så alle disse tingene er
kommuniserer med

644
00:31:00,880 --> 00:31:02,600
Internett på noen måte.

645
00:31:02,600 --> 00:31:08,070
>> Så når datamaskinen mottar noen data
fra internett, hvordan det

646
00:31:08,070 --> 00:31:10,130
vet hvilket program faktisk
ønsker dataene?

647
00:31:10,130 --> 00:31:12,610
Hvordan det vet om denne spesielle
data er ment for

648
00:31:12,610 --> 00:31:16,070
torren søknad i motsetning
til nettleseren?

649
00:31:16,070 --> 00:31:20,980
Så dette er hensikten med porter i det
alle disse programmene har

650
00:31:20,980 --> 00:31:22,720
hevdet en port på datamaskinen.

651
00:31:22,720 --> 00:31:27,580
Så din nettleser sier, hey,
Jeg lytter på port 1000.

652
00:31:27,580 --> 00:31:32,240
Og din torren programmet sier,
Jeg lytter på port 3000.

653
00:31:32,240 --> 00:31:34,770
Og Skype sier, jeg bruker port 4000.

654
00:31:34,770 --> 00:31:41,950
>> Så når du får noen data som hører
til en av disse programmer, data

655
00:31:41,950 --> 00:31:45,510
er merket med hvilken port det faktisk
skal sendes med til.

656
00:31:45,510 --> 00:31:47,950
Så dette sier, oh, hører jeg
til port 1000.

657
00:31:47,950 --> 00:31:50,950
Jeg vet da trenger jeg å videresende dette
sammen til min nettleser.

658
00:31:50,950 --> 00:31:56,440
Så grunnen til det er relevant her
er at webservere tendens til

659
00:31:56,440 --> 00:31:58,240
lytte på port 80.

660
00:31:58,240 --> 00:32:02,420
Så når jeg kontakter Facebook.com, er jeg
kommunisere med noen maskin.

661
00:32:02,420 --> 00:32:06,390
Men jeg trenger å si hvilken port av at
maskin jeg ønsker å kommunisere med.

662
00:32:06,390 --> 00:32:09,160
Og webservere pleier å være
lytter på port 80.

663
00:32:09,160 --> 00:32:14,010
>> Hvis de ville, kunne de sette den
opp slik at den lister som på port 7000.

664
00:32:14,010 --> 00:32:19,090
Og så i en nettleser, jeg kunne
manuelt skrive Facebook.com: 7000 til

665
00:32:19,090 --> 00:32:24,600
sende forespørsel til port 7000
av Facebook webserver.

666
00:32:24,600 --> 00:32:26,820
>> DAVID J. MALAN: Og i dette tilfellet, selv
selv om vi ikke kreve at folk

667
00:32:26,820 --> 00:32:30,000
nevner dette, i dette tilfellet, hvilken port
ville forespørselen faktisk gå til?

668
00:32:30,000 --> 00:32:36,630

669
00:32:36,630 --> 00:32:37,880
Prøv på nytt.

670
00:32:37,880 --> 00:32:42,810

671
00:32:42,810 --> 00:32:44,300
Nettopp.

672
00:32:44,300 --> 00:32:47,960
Ikke ute etter det, men en subtilitet
det er det ingen de siste.

673
00:32:47,960 --> 00:32:51,770
>> ROB BOWDEN: Så HTTPS, siden det er
lytter spesielt for den

674
00:32:51,770 --> 00:32:55,180
kryptert, er det på port 4430.

675
00:32:55,180 --> 00:32:57,680
>> Målgruppe: og e-poster er 25, ikke sant?

676
00:32:57,680 --> 00:33:00,670
>> DAVID J. MALAN: Outbound
e-post, 25, yep.

677
00:33:00,670 --> 00:33:03,760
>> ROB BOWDEN: Jeg vet ikke engang de fleste av
det - alle de nederste pleier å være

678
00:33:03,760 --> 00:33:06,310
reservert for ting.

679
00:33:06,310 --> 00:33:09,260
Jeg tror alt under
1024 er reservert.

680
00:33:09,260 --> 00:33:13,450
>> PUBLIKUM: Hvorfor sa du
3 var feil nummer?

681
00:33:13,450 --> 00:33:18,820
>> ROB BOWDEN: Fordi i en IP-adresse,
det er fire grupperinger av sifre.

682
00:33:18,820 --> 00:33:21,090
Og de er fra 0 til 255..

683
00:33:21,090 --> 00:33:28,060
Så 192.168.2.1 er en vanlig
lokale IP-adressen for nettverket.

684
00:33:28,060 --> 00:33:30,840
Legg merke til alle de som er mindre enn 255.

685
00:33:30,840 --> 00:33:33,570
Så når jeg begynte med 300, som
kunne umulig ha

686
00:33:33,570 --> 00:33:35,210
vært ett av numrene.

687
00:33:35,210 --> 00:33:38,170
>> DAVID J. MALAN: Men det dumme klipp
fra - var det CSI, hvor de hadde en

688
00:33:38,170 --> 00:33:39,970
tall som var for stor
for IP-adressen.

689
00:33:39,970 --> 00:33:42,940

690
00:33:42,940 --> 00:33:46,110
>> ROB BOWDEN: Eventuelle spørsmål om dette?

691
00:33:46,110 --> 00:33:51,710
Den neste, slik at fullstendig endring i
tema, men vi har denne PHP array for

692
00:33:51,710 --> 00:33:53,270
husene i quad.

693
00:33:53,270 --> 00:33:56,360
Og vi har en ikke-sorterte liste.

694
00:33:56,360 --> 00:33:59,550
Og vi ønsker å skrive ut hvert listepunkt
bare inneholder huset navn.

695
00:33:59,550 --> 00:34:09,090

696
00:34:09,090 --> 00:34:11,870
Så vi har en foreach loop.

697
00:34:11,870 --> 00:34:17,540
Så husk, syntaksen er foreach
matrise som element i matrisen.

698
00:34:17,540 --> 00:34:22,360
Så gjennom hver iterasjon av sløyfen,
Huset kommer til å ta på en av de

699
00:34:22,360 --> 00:34:24,060
verdier inne i matrisen.

700
00:34:24,060 --> 00:34:26,530
>> På den første iterasjon, hus
vil være Cabot House.

701
00:34:26,530 --> 00:34:30,370
På en andre iterasjon, huset vil
være Courier hus og så videre.

702
00:34:30,370 --> 00:34:34,370
Så for hver quad som huset, er vi
bare kommer til å skrive ut -

703
00:34:34,370 --> 00:34:37,250
du også kunne ha gjentatt -

704
00:34:37,250 --> 00:34:42,199
listeelementet, og deretter huset navn
og deretter lukke listeelementet.

705
00:34:42,199 --> 00:34:45,210
Klammeparentes er valgfritt her.

706
00:34:45,210 --> 00:34:49,480
>> Og da vi sa også i spørsmålet
seg selv, husk å lukke

707
00:34:49,480 --> 00:34:50,770
sorterte liste tag.

708
00:34:50,770 --> 00:34:53,949
Så må vi gå ut PHP-modus
for å gjøre dette.

709
00:34:53,949 --> 00:35:00,280
Eller vi kunne ha gjentatt den
lukke sorterte liste tag.

710
00:35:00,280 --> 00:35:02,380
>> DAVID J. MALAN: Også fint her ville
har vært å bruke en gammel skole for

711
00:35:02,380 --> 00:35:07,340
sløyfe med en $ i = 0 0 og bruker teller til
regne ut lengden av strålen.

712
00:35:07,340 --> 00:35:09,240
Helt greit også, bare
litt wordier.

713
00:35:09,240 --> 00:35:12,170

714
00:35:12,170 --> 00:35:14,742
>> PUBLIKUM: Så hvis du skulle
[Uhørbart], ville du gjøre -

715
00:35:14,742 --> 00:35:16,734
Jeg glemmer hva loopen [uhørbart] er.

716
00:35:16,734 --> 00:35:21,380
Vil du $ quad brakett jeg?

717
00:35:21,380 --> 00:35:21,850
>> DAVID J. MALAN: Nettopp.

718
00:35:21,850 --> 00:35:23,100
Ja, akkurat.

719
00:35:23,100 --> 00:35:26,650

720
00:35:26,650 --> 00:35:27,900
>> ROB BOWDEN: Noe annet?

721
00:35:27,900 --> 00:35:31,350

722
00:35:31,350 --> 00:35:32,010
>> DAVID J. MALAN: Greit.

723
00:35:32,010 --> 00:35:32,300
Avveininger.

724
00:35:32,300 --> 00:35:38,290
Så var det bunter av svar
mulig for hver av disse.

725
00:35:38,290 --> 00:35:40,510
Vi var egentlig bare ute etter
noe overbevisende for en oppside og

726
00:35:40,510 --> 00:35:41,100
en ulempe.

727
00:35:41,100 --> 00:35:44,830
Og nummer 16 spurte, validere brukere '
innspill klientsiden, som med Javascript,

728
00:35:44,830 --> 00:35:47,280
i stedet for server-side, som med PHP.

729
00:35:47,280 --> 00:35:49,450
Så hva er en oppside på
gjør klientsiden?

730
00:35:49,450 --> 00:35:53,780
>> Vel, er en av de tingene vi foreslo
at du reduserer ventetid, fordi du

731
00:35:53,780 --> 00:35:56,750
trenger ikke å bry kontakte
server, noe som kan ta noen

732
00:35:56,750 --> 00:36:00,390
millisekunder eller enda et par sekunder
ved å unngå det og bare

733
00:36:00,390 --> 00:36:04,670
validere brukernes innspill på klientsiden ved
utløser en on-sender handler og

734
00:36:04,670 --> 00:36:06,650
bare sjekke, fikk de skriver
noe for navn?

735
00:36:06,650 --> 00:36:08,080
Visste de skriver noe
i for e-postadresse?

736
00:36:08,080 --> 00:36:10,950
Visste de velger en dorm fra
rullegardinmenyen?

737
00:36:10,950 --> 00:36:14,360
>> Du kan gi dem umiddelbar tilbakemelding
bruker gigahertz datamaskin

738
00:36:14,360 --> 00:36:16,770
eller hva de har som er
faktisk på sitt skrivebord.

739
00:36:16,770 --> 00:36:19,310
Så det er bare en bedre brukeropplevelse
oppleve typisk.

740
00:36:19,310 --> 00:36:24,460
Men en Ulempen med å gjøre klientsiden
validering, hvis du gjør det uten også

741
00:36:24,460 --> 00:36:29,860
gjøre server-side validering er at
mest alle som kommer ut av CS50 vet

742
00:36:29,860 --> 00:36:33,980
at du kan bare sende alle data du vil
til en server som en rekke måter.

743
00:36:33,980 --> 00:36:37,030
Oppriktig, i de fleste hvilken som helst nettleser, kan du
Klikk rundt i innstillingene og bare

744
00:36:37,030 --> 00:36:40,110
slå av Javascript, noe som ville,
derfor deaktivere noen form for

745
00:36:40,110 --> 00:36:41,080
validering.

746
00:36:41,080 --> 00:36:44,460
>> Men du også kanskje husker at selv jeg
gjorde noen uforståelige ting i klassen ved hjelp

747
00:36:44,460 --> 00:36:47,790
telnet og faktisk late som
være en nettleser ved å sende get

748
00:36:47,790 --> 00:36:49,240
forespørsler til en server.

749
00:36:49,240 --> 00:36:51,030
Og det er absolutt ikke
bruker noen Script.

750
00:36:51,030 --> 00:36:53,290
Det er bare meg å skrive kommandoer
på et tastatur.

751
00:36:53,290 --> 00:36:57,410
Så egentlig, enhver programmerer innenfor nok
komfort med nettet og HTTP

752
00:36:57,410 --> 00:37:01,690
kunne sende uansett data han eller hun ønsker
til en server uten validering.

753
00:37:01,690 --> 00:37:05,470
Og hvis serveren ikke er også sjekker,
gjorde de gi meg et navn, er

754
00:37:05,470 --> 00:37:08,930
dette faktisk en gyldig e-postadresse, gjorde
de velger en sovesal, kan du ende

755
00:37:08,930 --> 00:37:12,800
opp å sette inn falske eller bare blank data
inn i databasen, noe som trolig

756
00:37:12,800 --> 00:37:15,450
ikke kommer til å være en god ting hvis
du var forutsatt at det var der.

757
00:37:15,450 --> 00:37:16,770
>> Så dette er en irriterende virkelighet.

758
00:37:16,770 --> 00:37:19,890
Men generelt, klient-side
validering er stor.

759
00:37:19,890 --> 00:37:21,810
Men det betyr dobbelt så mye arbeid.

760
00:37:21,810 --> 00:37:25,970
Selv om det ikke eksisterer ulike
biblioteker, Javascript-biblioteker for

761
00:37:25,970 --> 00:37:28,830
eksempel, som gjør dette mye,
mye mindre av en hodepine.

762
00:37:28,830 --> 00:37:31,940
Og du kan bruke noen av koden
server-side, klientsiden.

763
00:37:31,940 --> 00:37:35,980
Men innser at det er typisk
merarbeid.

764
00:37:35,980 --> 00:37:36,415
Yeah.

765
00:37:36,415 --> 00:37:37,792
>> PUBLIKUM: Så hvis vi bare
sa mindre sikker -

766
00:37:37,792 --> 00:37:39,205
>> DAVID J. MALAN: [ler]

767
00:37:39,205 --> 00:37:39,680
Ugh.

768
00:37:39,680 --> 00:37:43,105
De er alltid vanskeligere
seg til å avgjøre.

769
00:37:43,105 --> 00:37:44,480
>> ROB BOWDEN: Det ville
har blitt akseptert.

770
00:37:44,480 --> 00:37:44,810
>> DAVID J. MALAN: Hva?

771
00:37:44,810 --> 00:37:45,810
>> ROB BOWDEN: Jeg skapte dette problemet.

772
00:37:45,810 --> 00:37:46,735
Det ville ha blitt akseptert.

773
00:37:46,735 --> 00:37:47,220
>> DAVID J. MALAN: Yeah.

774
00:37:47,220 --> 00:37:47,830
>> PUBLIKUM: Cool.

775
00:37:47,830 --> 00:37:51,770
>> ROB BOWDEN: Men vi ikke akseptere
for den første -

776
00:37:51,770 --> 00:37:53,630
vel, hva vi var ute etter er
noe som du ikke trenger å

777
00:37:53,630 --> 00:37:55,270
kommunisere med serveren.

778
00:37:55,270 --> 00:37:58,355
Vi aksepterte ikke bare raskere.

779
00:37:58,355 --> 00:38:00,080
>> PUBLIKUM: Hva om
ikke laste siden?

780
00:38:00,080 --> 00:38:00,430
>> ROB BOWDEN: Ja.

781
00:38:00,430 --> 00:38:03,000
Det var en akseptert svar.

782
00:38:03,000 --> 00:38:06,300
>> DAVID J. MALAN: alt hvor vi følte
det var mer sannsynlig enn ikke sannsynlig

783
00:38:06,300 --> 00:38:09,780
at du visste hva du var
si, som er en hard

784
00:38:09,780 --> 00:38:13,500
linje for å trekke noen ganger.

785
00:38:13,500 --> 00:38:16,000
Ved hjelp av en lenket liste i stedet
i en matrise for å opprettholde en

786
00:38:16,000 --> 00:38:17,590
sortert liste av heltall.

787
00:38:17,590 --> 00:38:21,000
Så en oppside vi ofte sitere med koblede
lister som motiverte deres hele

788
00:38:21,000 --> 00:38:22,370
Innføringen var du får dynamikk.

789
00:38:22,370 --> 00:38:23,030
De kan vokse.

790
00:38:23,030 --> 00:38:23,950
De kan krympe.

791
00:38:23,950 --> 00:38:27,370
Så du trenger ikke å hoppe gjennom ringer
å faktisk skape mer minne

792
00:38:27,370 --> 00:38:28,140
med en matrise.

793
00:38:28,140 --> 00:38:30,310
Eller du trenger ikke å bare
si, beklager, bruker.

794
00:38:30,310 --> 00:38:31,410
Matrisen er fylt.

795
00:38:31,410 --> 00:38:35,850
Så dynamisk vekst av listen.

796
00:38:35,850 --> 00:38:37,210
En ulempe skjønt av lenkede lister?

797
00:38:37,210 --> 00:38:40,916

798
00:38:40,916 --> 00:38:43,356
>> PUBLIKUM: Det er lineær.

799
00:38:43,356 --> 00:38:45,800
Søke på lenket liste er lineær
i stedet for det du logge inn

800
00:38:45,800 --> 00:38:46,360
>> DAVID J. MALAN: Nettopp.

801
00:38:46,360 --> 00:38:50,160
Søke på en lenket liste er lineær,
selv om det er i orden, fordi du kan

802
00:38:50,160 --> 00:38:53,170
bare følg disse brødsmuler, disse
pekere, fra starten av listen

803
00:38:53,170 --> 00:38:53,570
til enden.

804
00:38:53,570 --> 00:38:57,970
Du kan ikke utnytte random access og,
dermed, binære søk, selv om det er

805
00:38:57,970 --> 00:39:00,740
sorteres, at du kunne
gjøre med en matrise.

806
00:39:00,740 --> 00:39:02,390
Og det er også en annen kostnad.

807
00:39:02,390 --> 00:39:02,966
Yeah.

808
00:39:02,966 --> 00:39:03,800
>> PUBLIKUM: Minne ineffektiv?

809
00:39:03,800 --> 00:39:04,130
>> DAVID J. MALAN: Yeah.

810
00:39:04,130 --> 00:39:06,940
Vel, det ville jeg ikke nødvendigvis
si ineffektiv.

811
00:39:06,940 --> 00:39:10,110
Men det koster deg mer minne,
fordi du trenger 32 bits for hver

812
00:39:10,110 --> 00:39:13,400
node for den ekstra pekeren, på
minste for en enkeltvis lenket liste.

813
00:39:13,400 --> 00:39:16,660
Nå, hvis du bare lagrer heltall og
du legger pekeren, er at

814
00:39:16,660 --> 00:39:17,830
faktisk slags ikke-triviell.

815
00:39:17,830 --> 00:39:19,340
Det er en dobling av mengden minne.

816
00:39:19,340 --> 00:39:22,330
Men i virkeligheten, hvis du lagrer en
lenket liste av structs som kan ha

817
00:39:22,330 --> 00:39:25,540
8 byte, 16 bytes, enda mer
enn det, kanskje det er mindre

818
00:39:25,540 --> 00:39:26,500
av en marginal kostnad.

819
00:39:26,500 --> 00:39:28,320
Men det er en kostnad likevel.

820
00:39:28,320 --> 00:39:31,880
Så noen av disse ville har
vært fint som ulempene.

821
00:39:31,880 --> 00:39:32,110
>> 18.

822
00:39:32,110 --> 00:39:36,100
Ved hjelp av PHP i stedet for C for å skrive
et kommandolinjeprogrammet.

823
00:39:36,100 --> 00:39:41,890
Så her er det ofte raskere å bruke en
språk som PHP eller Ruby eller Python.

824
00:39:41,890 --> 00:39:43,700
Du bare raskt åpne
opp en tekst editor.

825
00:39:43,700 --> 00:39:45,900
Du har mange flere funksjoner
tilgjengelig for deg.

826
00:39:45,900 --> 00:39:49,325
PHP har kjøkkenvasken av funksjoner,
mens i C, du

827
00:39:49,325 --> 00:39:50,420
har veldig, veldig lite.

828
00:39:50,420 --> 00:39:53,820
Faktisk, gutta kjenner den harde måten
at du ikke har hash tabeller.

829
00:39:53,820 --> 00:39:55,000
Du trenger ikke ha koblet lister.

830
00:39:55,000 --> 00:39:57,470
Hvis du vil ha dem, må du
implementere dem selv.

831
00:39:57,470 --> 00:40:00,950
>> Så en oppside på PHP eller egentlig noen
tolket språk er hurtighet

832
00:40:00,950 --> 00:40:02,920
som du kan skrive kode.

833
00:40:02,920 --> 00:40:06,660
Men en ulempe, så vi dette når jeg
raskt pisket opp en misspeller

834
00:40:06,660 --> 00:40:11,780
implementering i foredrag ved hjelp av PHP, er
at det å bruke et tolket språk

835
00:40:11,780 --> 00:40:13,570
vanligvis går tregere.

836
00:40:13,570 --> 00:40:18,420
Og vi så at beviselig med en
økning i tid fra 0,3 sekunder til 3

837
00:40:18,420 --> 00:40:24,440
sekund, på grunn av tolkningen
som faktisk skjer.

838
00:40:24,440 --> 00:40:27,060
>> En annen opp var at du
trenger ikke å kompilere.

839
00:40:27,060 --> 00:40:30,130
Så det også raskere utvikling
forresten, fordi dere ikke har

840
00:40:30,130 --> 00:40:31,360
to trinn til å kjøre et program.

841
00:40:31,360 --> 00:40:32,140
Du har bare ett.

842
00:40:32,140 --> 00:40:35,260
Og så det er ganske
overbevisende også.

843
00:40:35,260 --> 00:40:38,450
Ved hjelp av en SQL database i stedet for
en CSV-fil til å lagre data.

844
00:40:38,450 --> 00:40:40,230
Så SQL database brukes for pset7.

845
00:40:40,230 --> 00:40:42,060
CSV-filer du ikke bruker mye.

846
00:40:42,060 --> 00:40:45,960
Men du brukte det indirekte i pset7 som
vel ved å snakke med Yahoo Finance.

847
00:40:45,960 --> 00:40:49,330
>> Men CSV er akkurat som en Excel-fil, men
super enkelt, hvor kolonnene er

848
00:40:49,330 --> 00:40:54,010
bare demarked med komma inne
av en ellers tekstfil.

849
00:40:54,010 --> 00:40:56,740
Og ved hjelp av en SQL-database er
en litt mer overbevisende.

850
00:40:56,740 --> 00:41:00,060
Det er en oppside, fordi du får ting
som velge og sette inn og slette.

851
00:41:00,060 --> 00:41:03,790
Og du får, formodentlig, indekser som
MySQL og andre databaser, som

852
00:41:03,790 --> 00:41:07,510
Oracle, bygge for deg i minne, som
betyr at velger er trolig ikke

853
00:41:07,510 --> 00:41:09,000
kommer til å være lineær topp til bunn.

854
00:41:09,000 --> 00:41:11,300
Det er faktisk kommer til å være noe
som binære søk eller noe

855
00:41:11,300 --> 00:41:12,520
lignende i ånden.

856
00:41:12,520 --> 00:41:13,930
Så de er generelt raskere.

857
00:41:13,930 --> 00:41:16,040
>> Men en ulempe er at
det er bare mer arbeid.

858
00:41:16,040 --> 00:41:16,730
Det er mer innsats.

859
00:41:16,730 --> 00:41:18,140
Du må forstå databaser.

860
00:41:18,140 --> 00:41:18,940
Du må sette det opp.

861
00:41:18,940 --> 00:41:20,840
Du trenger en server for å kjøre
at databasen på.

862
00:41:20,840 --> 00:41:22,750
Du må forstå
hvordan du konfigurerer den.

863
00:41:22,750 --> 00:41:24,930
Så dette er bare disse
typer avveininger.

864
00:41:24,930 --> 00:41:27,860
Mens en CSV-fil, kan du
lage den med gedit.

865
00:41:27,860 --> 00:41:28,770
Og du er flink til å gå.

866
00:41:28,770 --> 00:41:31,550
Det er ingen kompleksitet utover det.

867
00:41:31,550 --> 00:41:34,870
>> Ved hjelp av en trie i stedet for en hash table
med separat kjeding til å lagre en

868
00:41:34,870 --> 00:41:37,490
ordbok over ord som minner
av pset5.

869
00:41:37,490 --> 00:41:42,480
Så en prøver oppside, i teorien
minst, er hva?

870
00:41:42,480 --> 00:41:46,380
Konstant tid, i hvert fall hvis du er
hashing på hver av de enkelte

871
00:41:46,380 --> 00:41:48,990
bokstavene i et ord, som deg
kan ha for pset5.

872
00:41:48,990 --> 00:41:52,720
Det kan være fem hashes, seks
hashes om det er fem eller seks

873
00:41:52,720 --> 00:41:53,900
bokstavene i ordet.

874
00:41:53,900 --> 00:41:54,580
Og det er ganske bra.

875
00:41:54,580 --> 00:41:56,910
Og hvis det er en øvre grense for hvor
lenge dine ord kan være, er at

876
00:41:56,910 --> 00:41:59,320
faktisk asymptotisk konstant tid.

877
00:41:59,320 --> 00:42:05,180
>> Mens en hash tabell med separat
chaining, problemet der med at

878
00:42:05,180 --> 00:42:09,070
type datastruktur er at
ytelsen til algoritmer som regel

879
00:42:09,070 --> 00:42:12,700
avhenger av flere ting
allerede i datastrukturen.

880
00:42:12,700 --> 00:42:15,660
Og det er definitivt tilfellet med
kjeder, der flere ting du putter

881
00:42:15,660 --> 00:42:18,800
inn i en nøkkeltabell, jo lengre disse
kjeder gå, noe som betyr at i verste

882
00:42:18,800 --> 00:42:21,960
tilfelle, er det ting du kan være ute etter
er helt ved enden av en

883
00:42:21,960 --> 00:42:26,000
av disse kjeder, som effektivt
tilfaller til noe lineær.

884
00:42:26,000 --> 00:42:29,450
>> Nå, i praksis, kan det helt
være slik at en nøkkeltabell med

885
00:42:29,450 --> 00:42:32,820
kjedene er raskere enn en tilsvar
trie gjennomføring.

886
00:42:32,820 --> 00:42:35,570
Men det er ulike årsaker, blant
som prøver å bruke en hel masse

887
00:42:35,570 --> 00:42:39,240
minne som kan, faktisk, langsomme ting
ned, fordi du ikke får fin

888
00:42:39,240 --> 00:42:42,410
fordelene av noe som kalles caching,
hvor ting som er nær hverandre

889
00:42:42,410 --> 00:42:45,420
i minnet kan nås
ofte raskere.

890
00:42:45,420 --> 00:42:48,180
Og noen ganger kan du komme opp med
en virkelig god hash-funksjon.

891
00:42:48,180 --> 00:42:51,060
Selv om du må kaste bort en bit av
minne, kan du faktisk være i stand til å

892
00:42:51,060 --> 00:42:54,430
finne ting fort og ikke
like ille som lineært.

893
00:42:54,430 --> 00:42:58,410
>> Så kort sagt, det var ikke nødvendigvis
med en hvilken som helst av disse en eller to

894
00:42:58,410 --> 00:43:00,050
spesifikke ting vi var ute etter.

895
00:43:00,050 --> 00:43:03,080
Virkelig noe overbevisende
som en oppside og nedside

896
00:43:03,080 --> 00:43:04,800
generelt fanget vår øyet.

897
00:43:04,800 --> 00:43:11,840
>> ROB BOWDEN: Så for oppsiden, vi gjorde
ikke akseptere på sin egen "raskere." Du

898
00:43:11,840 --> 00:43:14,540
hadde å si noe om det.

899
00:43:14,540 --> 00:43:17,910
Selv om du sa teoretisk raskere,
Vi visste at du slags forstått

900
00:43:17,910 --> 00:43:19,470
at det er 0 av 1.

901
00:43:19,470 --> 00:43:22,820
Og hash table, i teorien,
er ikke 0 på en.

902
00:43:22,820 --> 00:43:26,550
Nevne noe om runtime
generelt fikk du poeng.

903
00:43:26,550 --> 00:43:32,640
Men "raskere", de fleste av løsningene på
den store bord som ble forsøk var

904
00:43:32,640 --> 00:43:34,990
objektivt tregere enn løsninger
som var hash tabeller.

905
00:43:34,990 --> 00:43:37,250
Så raskere i seg selv
er egentlig ikke sant.

906
00:43:37,250 --> 00:43:41,550

907
00:43:41,550 --> 00:43:44,380
>> DAVID J. MALAN: Dom de dom dom.

908
00:43:44,380 --> 00:43:46,686
Jeg er trolig den eneste som innser
det er sånn som er ment å

909
00:43:46,686 --> 00:43:47,500
skal uttales, ikke sant?

910
00:43:47,500 --> 00:43:50,400
>> ROB BOWDEN: Jeg hadde faktisk ingen anelse.

911
00:43:50,400 --> 00:43:51,650
>> DAVID J. MALAN: Det gjorde
følelse i hodet mitt.

912
00:43:51,650 --> 00:43:53,830

913
00:43:53,830 --> 00:43:57,580
>> ROB BOWDEN: Jeg gjør dette.

914
00:43:57,580 --> 00:43:58,020
OK.

915
00:43:58,020 --> 00:44:04,243
Så dette er en hvor du måtte trekke
diagrammet ligner du kanskje

916
00:44:04,243 --> 00:44:06,040
har sett på tidligere eksamener.

917
00:44:06,040 --> 00:44:12,200
Så la oss bare se på dette.

918
00:44:12,200 --> 00:44:18,170
Så fra HTML node, har vi to
barn, hodet og kroppen.

919
00:44:18,170 --> 00:44:20,570
Så vi gren - hode og kropp.

920
00:44:20,570 --> 00:44:22,280
Hodet har en tittel tag.

921
00:44:22,280 --> 00:44:23,710
Så vi har en tittel.

922
00:44:23,710 --> 00:44:28,450
>> Nå er det én ting mange mennesker
glemte er at disse tekstnoder er

923
00:44:28,450 --> 00:44:30,430
elementer innenfor dette treet.

924
00:44:30,430 --> 00:44:36,260
Så her er vi tilfeldigvis trekke dem som ovaler
å skille dem fra disse

925
00:44:36,260 --> 00:44:37,380
typer noder.

926
00:44:37,380 --> 00:44:41,450
Men legg merke til også her har vi toppen,
midten, og nederst vil ende opp med å bli

927
00:44:41,450 --> 00:44:42,560
tekstnoder.

928
00:44:42,560 --> 00:44:46,250
Så glemmer de som var noe
av en vanlig feil.

929
00:44:46,250 --> 00:44:48,770
>> Kroppen har tre barn -
disse tre divs.

930
00:44:48,770 --> 00:44:53,340
Så div, div, div og deretter teksten
node barn av disse divs.

931
00:44:53,340 --> 00:44:55,900
Det er ganske mye det
for at spørsmålene.

932
00:44:55,900 --> 00:44:57,860
>> DAVID J. MALAN: Og det er verdt å merke seg,
selv om vi ikke dvele ved disse

933
00:44:57,860 --> 00:45:01,040
detaljer i den tiden vi bruker på
Javascript, at rekkefølgen gjør, i

934
00:45:01,040 --> 00:45:02,290
Faktisk, uansett teknisk.

935
00:45:02,290 --> 00:45:06,330
Så hvis hodet kommer før kroppen i
HTML, så det skal vises til

936
00:45:06,330 --> 00:45:08,860
igjen av kroppen i selve DOM.

937
00:45:08,860 --> 00:45:12,265
At hans er, generelt, bare så dere vet det,
noe som kalles dokumentorden der

938
00:45:12,265 --> 00:45:13,260
det spiller ingen rolle.

939
00:45:13,260 --> 00:45:17,470
Og hvis du var å implementere en parser,
et program som leser HTML i bygningen

940
00:45:17,470 --> 00:45:20,960
opp treet i minnet, for å være ærlig,
det er intuitivt nok det du

941
00:45:20,960 --> 00:45:24,720
gjøre uansett - topp til bunn,
venstre til høyre.

942
00:45:24,720 --> 00:45:26,116
>> ROB BOWDEN: Spørsmål om det?

943
00:45:26,116 --> 00:45:29,080

944
00:45:29,080 --> 00:45:30,000
Bør jeg gjøre det neste?

945
00:45:30,000 --> 00:45:32,380
>> DAVID J. MALAN: Sure.

946
00:45:32,380 --> 00:45:33,810
>> ROB BOWDEN: OK.

947
00:45:33,810 --> 00:45:39,320
Så dette er buffer overkjørt
angrep spørsmål.

948
00:45:39,320 --> 00:45:43,740
Det viktigste å gjenkjenne her er,
vel, hvordan kan en motstander triks

949
00:45:43,740 --> 00:45:46,170
dette programmet til å utføre
vilkårlig kode?

950
00:45:46,170 --> 00:45:51,860
Så argv1, den første kommandolinjen
argumentet til dette programmet, kan det være

951
00:45:51,860 --> 00:45:53,920
vilkårlig lang.

952
00:45:53,920 --> 00:45:59,160
Men her vi bruker memcpy å kopiere
argv1, som her er bar.

953
00:45:59,160 --> 00:46:00,165
Vi passerer det som argument.

954
00:46:00,165 --> 00:46:02,050
Og så det er å ta på navnet bar.

955
00:46:02,050 --> 00:46:08,040
>> Så vi memcpying bar
inn i denne bufferen c.

956
00:46:08,040 --> 00:46:09,400
Hvor mange byte er vi kopierer?

957
00:46:09,400 --> 00:46:14,040
Vel men mange bytes bar skjer med
skal bruke, lengden på det argumentet.

958
00:46:14,040 --> 00:46:17,930
Men c er bare 12 bytes bred.

959
00:46:17,930 --> 00:46:22,280
Så hvis vi skriver en kommandolinje argument
som er lengre enn 12 byte, er vi

960
00:46:22,280 --> 00:46:25,470
kommer til å renne over dette
Spesielt buffer.

961
00:46:25,470 --> 00:46:31,000
Nå, hvordan kan en motstander lure
programmere inn utføring vilkårlig kode?

962
00:46:31,000 --> 00:46:34,910
>> Så husk at her
Hoved kaller foo.

963
00:46:34,910 --> 00:46:37,340
Og så da hoved samtaler foo.

964
00:46:37,340 --> 00:46:40,408
La oss trekke dette.

965
00:46:40,408 --> 00:46:44,720

966
00:46:44,720 --> 00:46:46,990
Så vi har vår stabelen.

967
00:46:46,990 --> 00:46:49,090
Og hoved har en stabel ramme
på bunnen.

968
00:46:49,090 --> 00:46:51,860

969
00:46:51,860 --> 00:46:53,250
På et tidspunkt, hoved samtaler foo.

970
00:46:53,250 --> 00:46:55,390
Vel, umiddelbart, hoved samtaler foo.

971
00:46:55,390 --> 00:46:57,130
Og så foo får sin egen stack ramme.

972
00:46:57,130 --> 00:46:59,650

973
00:46:59,650 --> 00:47:02,220
>> Nå, på et tidspunkt, foo
kommer til å gå tilbake.

974
00:47:02,220 --> 00:47:06,810
Og gikk foo avkastning, må vi vite på
hva kodelinje innsiden av hoved vi

975
00:47:06,810 --> 00:47:10,610
var for å vite hvor
vi bør fortsette i hoved.

976
00:47:10,610 --> 00:47:13,100
Vi kan kalle foo fra en hel
haug med forskjellige steder.

977
00:47:13,100 --> 00:47:14,620
Hvordan vet vi hvor du skal gå tilbake?

978
00:47:14,620 --> 00:47:16,460
Vel, vi trenger å lagre det et sted.

979
00:47:16,460 --> 00:47:23,010
>> Så et sted rett rundt her, vi lagrer
hvor vi bør gå tilbake til en gang

980
00:47:23,010 --> 00:47:24,070
foo avkastning.

981
00:47:24,070 --> 00:47:26,350
Og dette er returadressen.

982
00:47:26,350 --> 00:47:30,490
Så hvordan en motstander kan dra nytte
på dette er det faktum at

983
00:47:30,490 --> 00:47:37,550
denne bufferen c er lagret, la oss
si, her er c..

984
00:47:37,550 --> 00:47:39,690
Så vi har fått 12 byte for c..

985
00:47:39,690 --> 00:47:40,540
Dette er ca.

986
00:47:40,540 --> 00:47:43,030
Og dette er foo stack ring.

987
00:47:43,030 --> 00:47:49,970
Så hvis den ondsinnede brukeren angir mer
byte enn 12 eller de inn i en kommando

988
00:47:49,970 --> 00:47:54,570
Argumentet som er lengre enn 12
tegn, så vi kommer til å

989
00:47:54,570 --> 00:47:57,540
renne over denne bufferen.

990
00:47:57,540 --> 00:47:59,910
>> Vi kan holde det gående.

991
00:47:59,910 --> 00:48:02,220
Og på et tidspunkt, går vi langt
nok at vi begynner

992
00:48:02,220 --> 00:48:05,120
skrive denne returadresse.

993
00:48:05,120 --> 00:48:08,310
Så når vi overskrive returadresse,
Dette betyr at når foo

994
00:48:08,310 --> 00:48:14,220
avkastning, er vi tilbake til der den
ondsinnet bruker er å fortelle det til etter

995
00:48:14,220 --> 00:48:19,490
uansett verdi det inn, etter hva
tegn brukeren angitt.

996
00:48:19,490 --> 00:48:24,320
Og så hvis den ondsinnede brukeren blir
spesielt flink, kan han ha denne

997
00:48:24,320 --> 00:48:29,255
tilbake til et sted i printDef
funksjon eller et sted i malloc

998
00:48:29,255 --> 00:48:31,830
funksjon, bare noe vilkårlig.

999
00:48:31,830 --> 00:48:38,420
>> Men enda mer smart er hva om han har
brukeren tilbake til akkurat her.

1000
00:48:38,420 --> 00:48:41,920
Og så begynner du å utføre
disse som linjer med kode.

1001
00:48:41,920 --> 00:48:46,610
Så på det punktet, kan brukeren angi
hva han vil i denne regionen.

1002
00:48:46,610 --> 00:48:52,210
Og han har full kontroll
over programmet.

1003
00:48:52,210 --> 00:48:53,460
Spørsmål om det?

1004
00:48:53,460 --> 00:48:56,380

1005
00:48:56,380 --> 00:49:00,970
Så det neste spørsmålet er fullført
reimplementation av foo på en slik måte

1006
00:49:00,970 --> 00:49:02,620
at det ikke lenger er sårbart.

1007
00:49:02,620 --> 00:49:03,870
>> Så det er et par måter
du kunne ha gjort dette.

1008
00:49:03,870 --> 00:49:10,900

1009
00:49:10,900 --> 00:49:13,330
Vi har fortsatt c bare
å være av lengde 12.

1010
00:49:13,330 --> 00:49:16,480
Du kunne ha endret dette
som en del av løsningen.

1011
00:49:16,480 --> 00:49:18,930
Vi har også lagt til en sjekk for å gjøre
at linjen ikke var null.

1012
00:49:18,930 --> 00:49:24,460
Selv om du ikke trenger
som for full kreditt.

1013
00:49:24,460 --> 00:49:27,690
Så vi sjekker først
hyssinglengde på bar.

1014
00:49:27,690 --> 00:49:31,650
Hvis den er større enn 12, så
ikke faktisk gjøre kopien.

1015
00:49:31,650 --> 00:49:33,010
Så det er en måte å fikse det.

1016
00:49:33,010 --> 00:49:36,750
>> En annen måte å feste det istedenfor
ha c bare være av lengde 12, har det

1017
00:49:36,750 --> 00:49:39,310
være av lengde strlen (bar).

1018
00:49:39,310 --> 00:49:43,370
En annen måte å feste den er
å faktisk bare tilbake.

1019
00:49:43,370 --> 00:49:46,690
Så hvis du nettopp hadde blitt kvitt alle
dette, hvis du nettopp hadde slettet alt

1020
00:49:46,690 --> 00:49:51,830
linjer med kode, ville du ha fått
full kreditt, siden denne funksjonen

1021
00:49:51,830 --> 00:49:54,150
den trenger ikke å utrette noe.

1022
00:49:54,150 --> 00:49:57,650
Det kopiere kommandolinjen
argument i noen array i

1023
00:49:57,650 --> 00:49:59,960
sin lokale stack ramme.

1024
00:49:59,960 --> 00:50:01,310
Og så ting er på vei tilbake.

1025
00:50:01,310 --> 00:50:04,020
Og uansett hva det dyktig er borte.

1026
00:50:04,020 --> 00:50:09,740
Så tilbake var også en tilstrekkelig
måte å få full kreditt.

1027
00:50:09,740 --> 00:50:13,425
>> DAVID J. MALAN: Ikke helt ånd
spørsmålet, men akseptabelt per den

1028
00:50:13,425 --> 00:50:15,580
spec likevel.

1029
00:50:15,580 --> 00:50:18,260
>> ROB BOWDEN: Spørsmål om noe av det?

1030
00:50:18,260 --> 00:50:22,270
Den ene tingen som du minst
nødvendig å ha kompilere kode.

1031
00:50:22,270 --> 00:50:24,810
Så selv om teknisk du er ikke
sårbare hvis koden ikke

1032
00:50:24,810 --> 00:50:29,130
kompilere, gjorde vi ikke akseptere det.

1033
00:50:29,130 --> 00:50:31,350
Ingen spørsmål?

1034
00:50:31,350 --> 00:50:33,320
OK.

1035
00:50:33,320 --> 00:50:34,580
>> DAVID J. MALAN: Vil du ha
å si denne tittelen?

1036
00:50:34,580 --> 00:50:37,230
>> ROB BOWDEN: Nei.

1037
00:50:37,230 --> 00:50:40,470
>> DAVID J. MALAN: Så i denne, dette
var enten gode nyheter eller dårlige nyheter.

1038
00:50:40,470 --> 00:50:43,870
Dette er bokstavelig talt det samme problemet
som den første quiz.

1039
00:50:43,870 --> 00:50:46,140
Og det er nesten det samme
problem som pset1.

1040
00:50:46,140 --> 00:50:49,980
Men det var bevisst forenklet å være
en enklere pyramide, en som kan bli

1041
00:50:49,980 --> 00:50:52,330
løses med en litt
enklere iterasjon.

1042
00:50:52,330 --> 00:50:55,680
Og egentlig, hva vi får til
her ikke var så mye logikken,

1043
00:50:55,680 --> 00:50:58,100
fordi sannsynligvis, etter dette punkt, er du
mer komfortable enn du var

1044
00:50:58,100 --> 00:51:01,850
i uke én med for sløyfer eller hvorfor løkker,
men virkelig å erte hverandre at

1045
00:51:01,850 --> 00:51:04,790
du er litt komfortabel med
forestillingen om at PHP er ikke bare om hva

1046
00:51:04,790 --> 00:51:05,290
programmering.

1047
00:51:05,290 --> 00:51:07,820
Det kan faktisk brukes som et språk
å skrive kommandolinjeprogrammer.

1048
00:51:07,820 --> 00:51:10,060
>> Og ja, det er det vi prøver
å trekke oppmerksomheten din til.

1049
00:51:10,060 --> 00:51:12,060
Dette er en kommandolinje PHP program.

1050
00:51:12,060 --> 00:51:16,690
Så C-kode her, mens korrekt
i C, ikke korrigere for PHP.

1051
00:51:16,690 --> 00:51:17,940
Men koden virkelig er den samme.

1052
00:51:17,940 --> 00:51:21,720
Hvis du sammenligner løsninger for Quiz
0 mot Quiz 1, vil du finne at

1053
00:51:21,720 --> 00:51:25,630
det er nesten identiske, bortsett
noen dollartegn og for

1054
00:51:25,630 --> 00:51:27,250
Fravær av en datatype.

1055
00:51:27,250 --> 00:51:31,720
Spesielt hvis vi tar en titt her,
vil du se at vi reagere, i dette

1056
00:51:31,720 --> 00:51:33,730
fall fra en opp gjennom syv.

1057
00:51:33,730 --> 00:51:34,910
>> Vi kunne ha gjort det 0-indeksen.

1058
00:51:34,910 --> 00:51:37,320
Men noen ganger, jeg tror det er bare
mentalt lettere å tenke på ting

1059
00:51:37,320 --> 00:51:38,200
1-7.

1060
00:51:38,200 --> 00:51:40,300
Hvis du vil ha en blokk, og deretter to
blokker, og deretter tre, deretter

1061
00:51:40,300 --> 00:51:41,770
prikk, prikk, prikk syv.

1062
00:51:41,770 --> 00:51:45,960
Vi har j blir initialisert til en
og deretter telling på opp til i.

1063
00:51:45,960 --> 00:51:48,150
Og alt her er
på annen måte identiske.

1064
00:51:48,150 --> 00:51:49,790
Men verdt å merke er
et par ting.

1065
00:51:49,790 --> 00:51:53,230
Vi gir deg disse to linjene, denne første
en, goofily navngitt som en shebang

1066
00:51:53,230 --> 00:51:54,560
for skarpe smell.

1067
00:51:54,560 --> 00:51:58,770
Og det bare angir banen, den
mappen, der et program som kan være

1068
00:51:58,770 --> 00:52:02,160
funnet ut at du vil bruke
å tolke denne filen.

1069
00:52:02,160 --> 00:52:04,710
>> Og deretter linjen etter det, av
Selvfølgelig betyr inn PHP-modus.

1070
00:52:04,710 --> 00:52:07,740
Og linjen helt nederst
betyr exit PHP-modus.

1071
00:52:07,740 --> 00:52:09,740
Og dette fungerer, generelt, med
tolket språk.

1072
00:52:09,740 --> 00:52:14,370
Det er litt irriterende hvis du skriver en
programmet i en fil som heter foo.php.

1073
00:52:14,370 --> 00:52:17,320
Og så brukerne må bare
husk, OK, for å kjøre dette programmet, jeg

1074
00:52:17,320 --> 00:52:22,320
nødt til å skrive "php plass foo.php." Kind
av irriterende hvis ingenting annet.

1075
00:52:22,320 --> 00:52:25,270
Og det avslører også at programmet
er skrevet i PHP, som ikke er alt

1076
00:52:25,270 --> 00:52:27,060
som opplysende for brukeren.

1077
00:52:27,060 --> 00:52:30,100
>> Så du kan fjerne den. Php helt
husker fra forelesning.

1078
00:52:30,100 --> 00:52:35,690
Og du kan faktisk gjøre. / Foo hvis
du har oppgitt korrekte rettigheter det ved å gjøre det

1079
00:52:35,690 --> 00:52:36,500
kjørbar.

1080
00:52:36,500 --> 00:52:39,630
Så chmod a + x foo ville ha gjort det.

1081
00:52:39,630 --> 00:52:41,460
Og hvis du også legge til shebang her.

1082
00:52:41,460 --> 00:52:45,320
Men egentlig, problemet var å komme på
skrive ut noe sånt som dette.

1083
00:52:45,320 --> 00:52:51,100
Ingen HTML, ingen C-kode sikkert,
bare litt PHP.

1084
00:52:51,100 --> 00:52:54,100
Så Milo deretter tilbake i problemet 25.

1085
00:52:54,100 --> 00:52:58,050
Og i 25, ble du gitt følgende
skjelett-kode, som var en

1086
00:52:58,050 --> 00:52:59,730
ganske enkel web-side.

1087
00:52:59,730 --> 00:53:04,230
Og saftig del HTML-messig var ned
her, hvor vi har inne i kroppen

1088
00:53:04,230 --> 00:53:09,160
en form som har en unik ID av innganger
innsiden av som var to innganger, en

1089
00:53:09,160 --> 00:53:11,950
med en idé om navn, en
med en idé om knappen.

1090
00:53:11,950 --> 00:53:14,240
>> Den første var å skrive inn tekst, den
andre av type sender.

1091
00:53:14,240 --> 00:53:16,930
Og så vi ga deg, faktisk, mer
ingredienser enn du trengte, bare så

1092
00:53:16,930 --> 00:53:19,230
dere hadde alternativer som
å løse dette problemet.

1093
00:53:19,230 --> 00:53:21,130
Du trenger strengt tatt ikke trenger
alle disse ID-ene.

1094
00:53:21,130 --> 00:53:23,580
Men det tillater deg å løse
det på forskjellige måter.

1095
00:53:23,580 --> 00:53:27,050
Og opp på toppen, legge merke til at
målet var å utløse

1096
00:53:27,050 --> 00:53:27,960
et vindu som dette -

1097
00:53:27,960 --> 00:53:28,780
Hei, Milo! -

1098
00:53:28,780 --> 00:53:31,270
å dukke opp i nettleseren ved hjelp
super enkelt, hvis

1099
00:53:31,270 --> 00:53:33,190
ikke stygg, varslingsfunksjonen.

1100
00:53:33,190 --> 00:53:37,480
Og så, til slutt, koker dette ned
konseptuelt å liksom lytter etter

1101
00:53:37,480 --> 00:53:41,290
innleveringer av skjemaet klientsiden
, Ikke på serversiden, liksom

1102
00:53:41,290 --> 00:53:45,640
reagerer på at innlevering av
gripe den verdien som brukeren har skrevet

1103
00:53:45,640 --> 00:53:50,120
på navnefeltet, og deretter
vise det i kroppen av et varsel.

1104
00:53:50,120 --> 00:53:53,460
>> Så en måte du kan gjøre dette på er med
jQuery, som ser litt

1105
00:53:53,460 --> 00:53:56,880
syntaktisk forvirrende i starten.

1106
00:53:56,880 --> 00:54:00,760
Du kan gjøre dette med ren DOM kode -
document.getelement etter ID.

1107
00:54:00,760 --> 00:54:02,530
Men la oss ta en titt på denne versjonen.

1108
00:54:02,530 --> 00:54:05,110
Jeg har et par viktige
linjer først.

1109
00:54:05,110 --> 00:54:09,460
Så ett, har vi denne linjen, som er
identisk med hva du kanskje har sett

1110
00:54:09,460 --> 00:54:13,830
i, tror jeg, form2.html
fra klassen i uke ni.

1111
00:54:13,830 --> 00:54:16,960
Og dette er bare å si, utføre
følgende kode når

1112
00:54:16,960 --> 00:54:18,430
dokumentet er klar.

1113
00:54:18,430 --> 00:54:21,770
Dette blir viktig bare fordi
HTML-sider leses ovenfra og

1114
00:54:21,770 --> 00:54:23,280
bunn, venstre til høyre.

1115
00:54:23,280 --> 00:54:27,910
>> Og derfor, hvis du prøver å gjøre
noe i kode her oppe til noen DOM

1116
00:54:27,910 --> 00:54:31,560
element, noen HTML-kode, som er ned
her, du gjør det for tidlig,

1117
00:54:31,560 --> 00:54:34,220
fordi dette har ikke engang
blitt lest inn i minnet.

1118
00:54:34,220 --> 00:54:37,740
Så ved å si dette document.ready
linjen, vi sier,

1119
00:54:37,740 --> 00:54:39,040
her er noen kode, browser.

1120
00:54:39,040 --> 00:54:42,440
Men ikke utføre dette før hele
Dokumentet er klar, er at DOM

1121
00:54:42,440 --> 00:54:44,320
tre finnes i minnet.

1122
00:54:44,320 --> 00:54:47,110
Dette er en litt mer
grei, hvis syntaktisk en

1123
00:54:47,110 --> 00:54:51,890
litt annerledes, hvor jeg sier, grip
HTML-elementet hvis unike

1124
00:54:51,890 --> 00:54:53,560
identifikator er innganger.

1125
00:54:53,560 --> 00:54:56,220
Det er det hash tag
betegner den unike ID.

1126
00:54:56,220 --> 00:54:58,070
Og da jeg ringer. Sende.

1127
00:54:58,070 --> 00:55:01,660
>> Så. Sende inn her er en funksjon, ellers
kjent som en metode, er at

1128
00:55:01,660 --> 00:55:05,850
innsiden av objektet på venstre hånd
siden er det at jeg ikke markere.

1129
00:55:05,850 --> 00:55:08,990
Så hvis du tenker på innganger som et objekt
i minnet - og faktisk er det.

1130
00:55:08,990 --> 00:55:10,440
Det er en node i et tre -

1131
00:55:10,440 --> 00:55:16,580
. Sende hjelp når dette skjemaet med
denne ID er sendt inn, utføre

1132
00:55:16,580 --> 00:55:17,700
følgende kode.

1133
00:55:17,700 --> 00:55:20,290
Jeg bryr meg ikke om hva navnet på den
Funksjonen er jeg utfører.

1134
00:55:20,290 --> 00:55:23,760
Så her jeg bruker, som før, hva er
kalt lambda funksjon eller en

1135
00:55:23,760 --> 00:55:24,720
anonym funksjon.

1136
00:55:24,720 --> 00:55:27,640
Det er ikke i det hele tatt intellektuelt
interessant annet enn det har ikke noe navn,

1137
00:55:27,640 --> 00:55:30,220
som er greit hvis du er bare
noen gang kommer til å kalle det en gang.

1138
00:55:30,220 --> 00:55:34,490
Og inni der jeg faktisk håndtere
innsending av skjemaet.

1139
00:55:34,490 --> 00:55:36,810
Jeg først erklære en variabel
kalt verdi.

1140
00:55:36,810 --> 00:55:40,610
Og hva er da effekten av dette
uthevet del her nå?

1141
00:55:40,610 --> 00:55:44,755
Hva gjør det på en
høyt nivå for meg?

1142
00:55:44,755 --> 00:55:48,539
>> PUBLIKUM: Det blir verdien som
brukeren ikke i HTML-koden nedenfor.

1143
00:55:48,539 --> 00:55:50,920
Det blir som ID og deretter
finner verdien av den.

1144
00:55:50,920 --> 00:55:51,590
>> DAVID J. MALAN: Nettopp.

1145
00:55:51,590 --> 00:55:54,300
Det griper node, hvis unike
identifikator er navnet.

1146
00:55:54,300 --> 00:55:56,900
Det blir verdien i dette, noe som
er, formodentlig, hva brukeren

1147
00:55:56,900 --> 00:55:58,190
skrev ham eller henne selv.

1148
00:55:58,190 --> 00:56:01,020
Og så den lagrer det i
variabel kalt verdi.

1149
00:56:01,020 --> 00:56:03,720
Som en side, kan du også
gjort dette litt annerledes.

1150
00:56:03,720 --> 00:56:09,250
Helt akseptabelt ved å gjøre noe
løgn Var verdi får

1151
00:56:09,250 --> 00:56:10,500
document.getElementById.

1152
00:56:10,500 --> 00:56:12,860

1153
00:56:12,860 --> 00:56:15,460
Og dette er grunnen til at det er litt
kjedelig å ikke bruke jQuery.

1154
00:56:15,460 --> 00:56:16,710
"Navn". Verdi.

1155
00:56:16,710 --> 00:56:18,330

1156
00:56:18,330 --> 00:56:19,620
Så helt akseptabelt.

1157
00:56:19,620 --> 00:56:22,770
Ulike måter å gjøre dette. jQuery bare
har en tendens til å være litt mer konsis og

1158
00:56:22,770 --> 00:56:25,230
definitivt mer populært
blant programmerere.

1159
00:56:25,230 --> 00:56:27,590
>> Nå, jeg gjør litt av en mental helse
sjekk, fordi i problemet

1160
00:56:27,590 --> 00:56:30,820
utsagn vi eksplisitt sa, hvis
brukeren har ennå ikke skrevet hans eller hennes

1161
00:56:30,820 --> 00:56:32,580
navn, viser ikke en varsler.

1162
00:56:32,580 --> 00:56:35,390
Men du kan se etter det, bare ved å
sjekker for den tomme strengen for en

1163
00:56:35,390 --> 00:56:37,850
quote-unquote hvis det er
ingenting faktisk det.

1164
00:56:37,850 --> 00:56:40,880
Men hvis det ikke er lik quote-unquote,
Jeg vil ringe varsler.

1165
00:56:40,880 --> 00:56:45,610
Og det interessante her er at
vi bruker pluss operatør, som

1166
00:56:45,610 --> 00:56:48,130
gjør hva i Javascript?

1167
00:56:48,130 --> 00:56:48,740
Sette sammen.

1168
00:56:48,740 --> 00:56:50,690
Så det er som Phps dot operatør.

1169
00:56:50,690 --> 00:56:52,820
Samme idé, litt annen syntaks.

1170
00:56:52,820 --> 00:56:55,280
Og jeg bare lage strengen som
du så på skjermbildet -

1171
00:56:55,280 --> 00:56:57,750
Hei, så og så.

1172
00:56:57,750 --> 00:56:59,200
>> Og så den siste detalj er dette.

1173
00:56:59,200 --> 00:57:04,970
Hvorfor jeg return false inne
av denne anonym funksjon?

1174
00:57:04,970 --> 00:57:07,420
>> PUBLIKUM: Det er ingen verdi.

1175
00:57:07,420 --> 00:57:09,380
Du setter den i formen.

1176
00:57:09,380 --> 00:57:12,320

1177
00:57:12,320 --> 00:57:16,730
Den sier bare, hvis verdi er ikke
lik blank, så gjør det.

1178
00:57:16,730 --> 00:57:20,040

1179
00:57:20,040 --> 00:57:20,940
Det var en blank i at innlevering.

1180
00:57:20,940 --> 00:57:21,170
>> DAVID J. MALAN: OK.

1181
00:57:21,170 --> 00:57:21,640
Forsiktig om.

1182
00:57:21,640 --> 00:57:22,830
Det er ingen andre her.

1183
00:57:22,830 --> 00:57:25,510
Og at return false er utenfor
av hvis forholdene.

1184
00:57:25,510 --> 00:57:29,470
Så dette markerte linjen, return false,
utfører uansett hva når

1185
00:57:29,470 --> 00:57:32,310
skjemaet er sendt.

1186
00:57:32,310 --> 00:57:36,810
Hva retur falsk innsiden av denne
hendelseshåndterer, som det heter,

1187
00:57:36,810 --> 00:57:38,450
hendelsen i spørsmålet
være innlevering?

1188
00:57:38,450 --> 00:57:42,350

1189
00:57:42,350 --> 00:57:44,470
>> PUBLIKUM: Fordi det
bare skjer én gang.

1190
00:57:44,470 --> 00:57:45,320
>> DAVID J. MALAN: Kun skjer én gang.

1191
00:57:45,320 --> 00:57:46,821
Ikke helt.

1192
00:57:46,821 --> 00:57:47,292
Yeah?

1193
00:57:47,292 --> 00:57:50,589
>> PUBLIKUM: Det forhindrer form fra
innsending til standard oppførsel,

1194
00:57:50,589 --> 00:57:52,480
noe som ville gjøre det siden reload.

1195
00:57:52,480 --> 00:57:53,110
>> DAVID J. MALAN: Nettopp.

1196
00:57:53,110 --> 00:57:56,490
Så jeg overbelastning begrepet sende inn her,
fordi jeg sier, er den formen

1197
00:57:56,490 --> 00:57:57,670
blir sendt inn.

1198
00:57:57,670 --> 00:58:02,240
Men som du foreslår, det er faktisk ikke
blitt sendt i den sanne HTTP måte.

1199
00:58:02,240 --> 00:58:06,870
Når du klikker Send, på grunn av vår
onsubmit handler, vi avskjær

1200
00:58:06,870 --> 00:58:09,040
at innsending av skjemaet så å si.

1201
00:58:09,040 --> 00:58:11,290
Vi deretter gjøre våre ting
med Javascript-kode.

1202
00:58:11,290 --> 00:58:14,070
Men jeg er bevisst retur falsk,
fordi det jeg ikke vil skje en

1203
00:58:14,070 --> 00:58:18,430
brøkdels sekund senere er for hele skjemaet
seg til å bli sendt til nettet

1204
00:58:18,430 --> 00:58:22,800
server med sentrale verdi-par ved å endre
URL til å være noe sånt

1205
00:58:22,800 --> 00:58:26,180
q = katter eller hva vi gjorde,
for eksempel i klassen.

1206
00:58:26,180 --> 00:58:29,640
Jeg ønsker ikke at det skal skje, fordi
det er ingen server lytting for denne

1207
00:58:29,640 --> 00:58:30,690
danne innsending.

1208
00:58:30,690 --> 00:58:32,320
Det er utelukkende gjort i Javascript-kode.

1209
00:58:32,320 --> 00:58:35,760
Og det er derfor jeg ikke engang har en
handling attributt på formen min, fordi jeg

1210
00:58:35,760 --> 00:58:38,870
har tenkt ikke for at dette skal
noen gang gå til serveren.

1211
00:58:38,870 --> 00:58:40,780
>> Så det blir sendt inn.

1212
00:58:40,780 --> 00:58:44,340
Men vi avskjære at skjema
innlevering og hindre standard

1213
00:58:44,340 --> 00:58:47,477
oppførsel, noe som er å faktisk
gå hele veien til serveren.

1214
00:58:47,477 --> 00:58:48,730
>> PUBLIKUM: Så å holde det på klientsiden.

1215
00:58:48,730 --> 00:58:49,780
>> DAVID J. MALAN: Keeping
det klientsiden.

1216
00:58:49,780 --> 00:58:51,030
Helt riktig.

1217
00:58:51,030 --> 00:58:53,240

1218
00:58:53,240 --> 00:58:55,757
Neste opp var min oh MySQL.

1219
00:58:55,757 --> 00:59:00,000

1220
00:59:00,000 --> 00:59:00,430
>> ROB BOWDEN: OK.

1221
00:59:00,430 --> 00:59:04,990
Så dette første spørsmålet var generelt
grov for folk.

1222
00:59:04,990 --> 00:59:07,270
Selv om de senere meldinger gikk bedre.

1223
00:59:07,270 --> 00:59:12,260
Så du måtte velge den riktige data
typer for begge disse kolonnene.

1224
00:59:12,260 --> 00:59:17,750
Og begge disse har noen
ting om dem som

1225
00:59:17,750 --> 00:59:20,620
gjøre valget vanskelig.

1226
00:59:20,620 --> 00:59:24,430
Så int var ikke en gyldig
skriver for nummer.

1227
00:59:24,430 --> 00:59:29,410
Årsaken til at en 12-sifret konto
nummer, er ikke stor nok til en int

1228
00:59:29,410 --> 00:59:31,070
lagre totalt sifre.

1229
00:59:31,070 --> 00:59:36,570
Så et gyldig valg ville ha vært en stor
int hvis du vet det.

1230
00:59:36,570 --> 00:59:42,090
Et annet valg kan ha vært
en røye felt av lengde 12.

1231
00:59:42,090 --> 00:59:44,560
Så noen av disse ville ha fungert.

1232
00:59:44,560 --> 00:59:46,100
Int. ville ikke.

1233
00:59:46,100 --> 00:59:50,170
>> Nå, balanse, tenker tilbake til pset7.

1234
00:59:50,170 --> 00:59:59,540
Så vi spesielt brukt desimal til
lagre verdien av aksjer eller -

1235
00:59:59,540 --> 01:00:00,550
>> DAVID J. MALAN: Cash.

1236
01:00:00,550 --> 01:00:01,060
>> ROB BOWDEN: Cash.

1237
01:00:01,060 --> 01:00:05,710
Vi brukte desimal å lagre mengden
kontanter som brukeren har i dag.

1238
01:00:05,710 --> 01:00:10,950
Så grunnen til at vi gjør det er
fordi, husk, flyter.

1239
01:00:10,950 --> 01:00:12,480
Det er flyttall i presisjon.

1240
01:00:12,480 --> 01:00:18,200
Det kan ikke presist lagre kontanter
verdier som vi ønsker her.

1241
01:00:18,200 --> 01:00:23,630
Så desimal er i stand til nettopp butikken
noe å, si, to desimaler.

1242
01:00:23,630 --> 01:00:27,630
Det er derfor balansen, vi vil ha det
å være desimal og ikke flyte.

1243
01:00:27,630 --> 01:00:30,230
>> DAVID J. MALAN: Og også, også, selv om
det kan ha vært flink i andre

1244
01:00:30,230 --> 01:00:32,760
sammenhenger å tenke, kanskje dette
er en sjanse for en int.

1245
01:00:32,760 --> 01:00:34,420
Jeg vil bare holde styr på
ting i pennies.

1246
01:00:34,420 --> 01:00:38,670
Fordi vi eksplisitt viste standard
Verdien av å være 100,00, som

1247
01:00:38,670 --> 01:00:40,380
betyr at det kan bare være en int.

1248
01:00:40,380 --> 01:00:45,310
Og en annen finesse også med tall
var at det ikke var ment

1249
01:00:45,310 --> 01:00:46,180
å være et lurespørsmål.

1250
01:00:46,180 --> 01:00:49,860
Men husker at en int i MySQL,
som i C, i det minste i

1251
01:00:49,860 --> 01:00:51,440
apparatet, er 32-bit.

1252
01:00:51,440 --> 01:00:53,960
Og selv om vi ikke forventer at du skal
vet nøyaktig hvor mange sifre som

1253
01:00:53,960 --> 01:00:56,910
middel, husker at det største antallet
du kan representere potensielt

1254
01:00:56,910 --> 01:01:00,710
med et 32-biters tall er omtrent hva?

1255
01:01:00,710 --> 01:01:02,760
>> Hvilket nummer skal vi alltid si?

1256
01:01:02,760 --> 01:01:04,530
2 til 32, som er det lag?

1257
01:01:04,530 --> 01:01:07,492

1258
01:01:07,492 --> 01:01:08,780
Du trenger ikke å vite nøyaktig.

1259
01:01:08,780 --> 01:01:10,580
Men er omtrent nyttig i livet.

1260
01:01:10,580 --> 01:01:12,200
Det er omtrent 4 milliarder.

1261
01:01:12,200 --> 01:01:14,430
Så vi har sagt at et par ganger.

1262
01:01:14,430 --> 01:01:16,360
Jeg vet jeg har sagt det et par ganger.

1263
01:01:16,360 --> 01:01:17,670
Og det er omtrent 4 milliarder.

1264
01:01:17,670 --> 01:01:19,710
Og det er en god regel
Tommelfinger å vite.

1265
01:01:19,710 --> 01:01:21,880
Hvis du har 8 bits, 256
er det magiske tallet.

1266
01:01:21,880 --> 01:01:24,160
Hvis du har 32 bits, 4
milliarder gi eller ta.

1267
01:01:24,160 --> 01:01:27,140
Så hvis du bare skrive ned 4 milliarder kroner,
vil du se at det er færre sifre enn

1268
01:01:27,140 --> 01:01:30,970
12, noe som betyr at det er helt klart ikke
nok uttrykksfullhet å fange en

1269
01:01:30,970 --> 01:01:34,220
12-sifret kontonummer.

1270
01:01:34,220 --> 01:01:34,940
>> ROB BOWDEN: OK.

1271
01:01:34,940 --> 01:01:38,520
Så de andre som gikk bedre.

1272
01:01:38,520 --> 01:01:40,900
Så antar at banken
pålegger en $ 20 månedlig

1273
01:01:40,900 --> 01:01:42,400
vedlikehold avgift på alle kontoer.

1274
01:01:42,400 --> 01:01:45,506
Med hva SQL-spørring kunne banken
trekke $ 20 fra hver teller, selv om

1275
01:01:45,506 --> 01:01:47,520
det resulterer i noen negative saldoer?

1276
01:01:47,520 --> 01:01:50,380
Så i utgangspunktet er det fire
hovedtyper av spørsmål -

1277
01:01:50,380 --> 01:01:52,840
sette inn, velge, oppdatere og slette.

1278
01:01:52,840 --> 01:01:56,080
Så hva gjør vi tror vi er
kommer til å bruke her?

1279
01:01:56,080 --> 01:01:57,000
Oppdater.

1280
01:01:57,000 --> 01:01:58,260
>> Så la oss ta en titt.

1281
01:01:58,260 --> 01:02:04,290

1282
01:02:04,290 --> 01:02:05,870
Så her er vi oppdaterer.

1283
01:02:05,870 --> 01:02:09,900
Hva bordet er vi oppdaterer kontoene?

1284
01:02:09,900 --> 01:02:11,670
Så oppdaterer kontoene.

1285
01:02:11,670 --> 01:02:15,390
Og da syntaksen sier, hva
i regnskapet er vi oppdaterer?

1286
01:02:15,390 --> 01:02:19,520
Vel, vi sette balanse lik
Nåverdien av balanse minus 20.

1287
01:02:19,520 --> 01:02:22,860
Så dette vil oppdatere alle rader
kontoer, subtrahere

1288
01:02:22,860 --> 01:02:26,250
$ 20 fra balansen.

1289
01:02:26,250 --> 01:02:29,260
>> DAVID J. MALAN: En vanlig feil her,
selv om vi noen ganger tilga det,

1290
01:02:29,260 --> 01:02:32,990
var å faktisk ha PHP-kode her
ringer spørringen funksjonen eller sette

1291
01:02:32,990 --> 01:02:35,460
anførselstegn rundt alt som
ikke trenger å være der.

1292
01:02:35,460 --> 01:02:39,780
>> ROB BOWDEN: Husk at MySQL er
et eget språk fra PHP.

1293
01:02:39,780 --> 01:02:42,410
Vi måtte skrive MySQL i PHP.

1294
01:02:42,410 --> 01:02:46,180
Og PHP er da å sende det
over til MySQL server.

1295
01:02:46,180 --> 01:02:51,120
Men du trenger ikke PHP for å
kommunisere med en MySQL server.

1296
01:02:51,120 --> 01:02:51,730
>> DAVID J. MALAN: Nettopp.

1297
01:02:51,730 --> 01:02:54,240
Så ingen variabler med dollartegn
skal i denne sammenheng.

1298
01:02:54,240 --> 01:02:59,550
Det kan bare gjøre alt regnestykket
innenfor selve databasen.

1299
01:02:59,550 --> 01:03:00,080
>> ROB BOWDEN: OK.

1300
01:03:00,080 --> 01:03:01,300
Så den neste.

1301
01:03:01,300 --> 01:03:02,731
Er dette den neste?

1302
01:03:02,731 --> 01:03:03,210
Yeah.

1303
01:03:03,210 --> 01:03:06,570
Så med hva SQL-spørring kunne banken
hente kontonumrene til dens

1304
01:03:06,570 --> 01:03:09,300
rikeste kundene, de med
balanserer større enn 1000?

1305
01:03:09,300 --> 01:03:13,280
Så hvilke av de fire hovedtyper
skal vi ønsker her?

1306
01:03:13,280 --> 01:03:14,430
Velg.

1307
01:03:14,430 --> 01:03:16,650
Så vi ønsker å velge.

1308
01:03:16,650 --> 01:03:17,610
Hva ønsker vi å velge?

1309
01:03:17,610 --> 01:03:19,380
Hva kolonnen vi ønsker å velge?

1310
01:03:19,380 --> 01:03:20,970
Vi vil spesielt ønske
for å velge nummer.

1311
01:03:20,970 --> 01:03:23,910
Men hvis du sa stjerner, vi
også akseptert det.

1312
01:03:23,910 --> 01:03:25,820
>> Så velger du nummeret fra hva tabellen?

1313
01:03:25,820 --> 01:03:26,640
Kontoer.

1314
01:03:26,640 --> 01:03:28,370
Og da tilstanden vi ønsker?

1315
01:03:28,370 --> 01:03:30,140
Der hvor balansen er større enn 1,000.

1316
01:03:30,140 --> 01:03:31,720
Vi har også akseptert større
enn eller lik.

1317
01:03:31,720 --> 01:03:35,230

1318
01:03:35,230 --> 01:03:36,190
Siste.

1319
01:03:36,190 --> 01:03:42,940
Med hva SQL-spørring kunne banken
tett, dvs. slette hver konto som

1320
01:03:42,940 --> 01:03:44,480
har en balanse på $ 0?

1321
01:03:44,480 --> 01:03:47,620
Så hvilken av de fire vi
kommer til å ønske å bruke?

1322
01:03:47,620 --> 01:03:48,320
Slett.

1323
01:03:48,320 --> 01:03:50,180
Så syntaksen for det?

1324
01:03:50,180 --> 01:03:51,890
Slett fra hva tabellen?

1325
01:03:51,890 --> 01:03:53,550
Kontoer.

1326
01:03:53,550 --> 01:03:55,790
Og da tilstanden som
vi ønsker å slette -

1327
01:03:55,790 --> 01:03:57,280
hvor balanse er lik null.

1328
01:03:57,280 --> 01:04:03,050
Så slette alle rader fra kontoer
der balansen er null.

1329
01:04:03,050 --> 01:04:04,300
Spørsmål om noen av disse?

1330
01:04:04,300 --> 01:04:08,840

1331
01:04:08,840 --> 01:04:10,260
Lyst til å stå i kø?

1332
01:04:10,260 --> 01:04:11,200
>> DAVID J. MALAN: Kø guide.

1333
01:04:11,200 --> 01:04:17,110
Så i denne, ga vi deg en noe
kjent struktur som vi utforsket en

1334
01:04:17,110 --> 01:04:20,450
bit i klasse sammen av structs,
som var en data

1335
01:04:20,450 --> 01:04:21,910
struktur relatert i ånden.

1336
01:04:21,910 --> 01:04:24,670
Forskjellen dog med en kø er
at vi måtte liksom huske hvem

1337
01:04:24,670 --> 01:04:27,900
var på forsiden av kø i stor
del, slik at vi kunne gjøre mer

1338
01:04:27,900 --> 01:04:30,530
effektiv bruk av minnet, minst
hvis vi bruker en matrise.

1339
01:04:30,530 --> 01:04:35,460
>> Fordi tilbakekalling, hvis vi har en matrise, hvis,
for eksempel, er dette den foran

1340
01:04:35,460 --> 01:04:38,470
køen, hvis jeg kommer inn i køen her,
og deretter noen får i kø

1341
01:04:38,470 --> 01:04:42,710
bak meg, bak meg, bak meg, og
en person går ut av linjen, du

1342
01:04:42,710 --> 01:04:45,930
kunne, som vi så noen av vår menneskelige
frivillige i klassen, har alle

1343
01:04:45,930 --> 01:04:47,100
skifte denne måten.

1344
01:04:47,100 --> 01:04:50,880
Men generelt, har alle gjøre
noe er ikke den beste bruken av tid

1345
01:04:50,880 --> 01:04:54,600
i et program, fordi det betyr at
algoritmen kjører i hva

1346
01:04:54,600 --> 01:04:56,520
asymptotisk kjøretid?

1347
01:04:56,520 --> 01:04:57,420
Det er lineær.

1348
01:04:57,420 --> 01:04:59,600
>> Og jeg føler at det er litt dumt.

1349
01:04:59,600 --> 01:05:02,890
Dersom den neste person i linje er neste
person som er ment å gå inn i

1350
01:05:02,890 --> 01:05:04,660
butikken, har de ikke alle har
til å bevege seg sammen.

1351
01:05:04,660 --> 01:05:08,200
Bare la vedkommende bli plukket ut
når den tid kommer, for eksempel.

1352
01:05:08,200 --> 01:05:09,870
Så vi kan spare litt tid der.

1353
01:05:09,870 --> 01:05:14,840
Og så for å gjøre det selv, det betyr
at leder på køen, eller

1354
01:05:14,840 --> 01:05:18,060
foran i køen skal
gradvis bevege seg dypere og dypere

1355
01:05:18,060 --> 01:05:23,340
inn i en array og til slutt kanskje
faktisk vikle rundt hvis vi bruker en

1356
01:05:23,340 --> 01:05:25,790
array til å lagre folket
i denne kø.

1357
01:05:25,790 --> 01:05:28,390
Så du kan nesten tenke på
matrise som en sirkulær data

1358
01:05:28,390 --> 01:05:29,880
struktur i den forstand.

1359
01:05:29,880 --> 01:05:33,970
>> Så du liksom har å holde styr på
størrelsen på det eller virkelig slutten av det

1360
01:05:33,970 --> 01:05:36,250
og hvor begynnelsen av det er.

1361
01:05:36,250 --> 01:05:39,490
Så vi foreslår at du erklærer
en slik kø, kall

1362
01:05:39,490 --> 01:05:41,330
det q, bare én bokstav.

1363
01:05:41,330 --> 01:05:44,570
Da foreslår vi at fronten være
initialisert til null og at størrelsen

1364
01:05:44,570 --> 01:05:45,470
initialiseres til null.

1365
01:05:45,470 --> 01:05:47,770
>> Så akkurat nå, er det ingenting
innsiden av det køen.

1366
01:05:47,770 --> 01:05:50,910
Og vi ber deg om å fullføre
gjennomføring av enqueue nedenfor i

1367
01:05:50,910 --> 01:05:55,250
en slik måte at funksjonen legger n i
slutten av q, og deretter returnerer sant.

1368
01:05:55,250 --> 01:05:58,690
Men hvis q er full eller negativ,
Funksjonen skal i stedet return false.

1369
01:05:58,690 --> 01:06:01,060
Og vi ga deg et par
forutsetninger.

1370
01:06:01,060 --> 01:06:04,320
Men de er egentlig ikke funksjonelt
relevant, finnes bare som bool,

1371
01:06:04,320 --> 01:06:06,690
fordi, teknisk sett, ikke bool
eksisterer i C med mindre du inkluderer en

1372
01:06:06,690 --> 01:06:07,310
viss header-fil.

1373
01:06:07,310 --> 01:06:09,350
Så det var bare å sørge for at det
ble ingen er dette et triks

1374
01:06:09,350 --> 01:06:10,940
Spørsmålet type ting.

1375
01:06:10,940 --> 01:06:16,280
>> Så enqueue, vi foreslo i utvalget
løsninger for å gjennomføre på følgende måte.

1376
01:06:16,280 --> 01:06:20,420
One, må vi først sjekke den enkle,
de lavthengende frukt.

1377
01:06:20,420 --> 01:06:23,820
Dersom køen er full, eller det antall som
du prøver å sette inn er mindre

1378
01:06:23,820 --> 01:06:26,380
enn null, som vi sa i
spesifikasjon av problemet bør

1379
01:06:26,380 --> 01:06:30,320
ikke være tillatt, fordi vi bare vil
ikke-negative verdier, så bør du

1380
01:06:30,320 --> 01:06:31,640
bare return false umiddelbart.

1381
01:06:31,640 --> 01:06:33,820
Så noen relativt lett
feilkontroll.

1382
01:06:33,820 --> 01:06:38,720
Dersom om du ønsker å legge til at faktiske
nummer, måtte du gjøre litt av

1383
01:06:38,720 --> 01:06:39,440
tenker her.

1384
01:06:39,440 --> 01:06:41,330
Og det er her det er litt irriterende
mentalt, fordi du må

1385
01:06:41,330 --> 01:06:43,000
finne ut hvordan de skal håndtere wraparound.

1386
01:06:43,000 --> 01:06:46,870
>> Men kimen til ideen her som er av
interesse for oss er at wraparound

1387
01:06:46,870 --> 01:06:51,480
ofte innebærer modulær aritmetikk og
mod operatør, den prosentvise side,

1388
01:06:51,480 --> 01:06:55,140
hvor du kan gå fra en større verdi
tilbake til null, og deretter en og to, og

1389
01:06:55,140 --> 01:06:58,650
tre, og deretter tilbake rundt null,
en og to og tre, og så videre

1390
01:06:58,650 --> 01:06:59,380
igjen og igjen.

1391
01:06:59,380 --> 01:07:02,880
Så måten vi foreslår å gjøre dette er
at vi ønsker å indeksere inn i

1392
01:07:02,880 --> 01:07:05,850
matrise kalt tall der
våre heltall ligge.

1393
01:07:05,850 --> 01:07:10,740
Men for å komme dit, vi først ønsker å gjøre
uansett størrelsen av køen er, men

1394
01:07:10,740 --> 01:07:14,080
deretter legge til at uansett
foran på listen er.

1395
01:07:14,080 --> 01:07:17,880
Og effekten av det er å sette oss på
den riktige posisjon i køen og

1396
01:07:17,880 --> 01:07:20,970
ikke anta at den første personen i kø
er i begynnelsen, noe som han eller

1397
01:07:20,970 --> 01:07:24,130
hun absolutt kunne være hvis vi
ble også skiftende alle.

1398
01:07:24,130 --> 01:07:26,710
Men vi er bare å skape arbeid
for oss selv om vi tok

1399
01:07:26,710 --> 01:07:27,800
den aktuelle banen.

1400
01:07:27,800 --> 01:07:29,330
>> Så vi kan holde det relativt enkelt.

1401
01:07:29,330 --> 01:07:32,180
Vi må huske at vi bare
lagt en int i køen.

1402
01:07:32,180 --> 01:07:35,850
Og da har vi bare returnere true.

1403
01:07:35,850 --> 01:07:38,560
I mellomtiden, i dequeue, vi spurte
du gjøre følgende.

1404
01:07:38,560 --> 01:07:42,260
Implementere den på en slik måte at den
dequeues, som er fjerner og avkastning,

1405
01:07:42,260 --> 01:07:44,190
int foran i køen.

1406
01:07:44,190 --> 01:07:46,410
For å fjerne int, er det nok
å glemme det.

1407
01:07:46,410 --> 01:07:47,650
Du trenger ikke å overstyre sin bit.

1408
01:07:47,650 --> 01:07:48,820
Så det er fortsatt faktisk det.

1409
01:07:48,820 --> 01:07:51,930
Akkurat som data på en harddisk,
vi bare ignorerer det faktum

1410
01:07:51,930 --> 01:07:52,970
at det er nå der.

1411
01:07:52,970 --> 01:07:55,520
Og hvis q er tom, bør vi
i stedet returnere negativ en.

1412
01:07:55,520 --> 01:07:56,750
Så dette føles vilkårlig.

1413
01:07:56,750 --> 01:08:01,640
Hvorfor gå tilbake negative 1
i stedet for falsk?

1414
01:08:01,640 --> 01:08:02,620
Yeah.

1415
01:08:02,620 --> 01:08:05,070
>> PUBLIKUM: Q er lagring
positive verdier.

1416
01:08:05,070 --> 01:08:10,950
Siden du bare lagre positive verdier
i q, er negativ en feil.

1417
01:08:10,950 --> 01:08:11,510
>> DAVID J. MALAN: OK, sant.

1418
01:08:11,510 --> 01:08:14,850
Så fordi vi bare lagrer positive
verdier eller null, så det er greit å

1419
01:08:14,850 --> 01:08:18,050
returnere en negativ verdi som en sentinel
verdi, et spesielt symbol.

1420
01:08:18,050 --> 01:08:21,630
Men du omskriving historie der,
fordi årsaken til at vi er bare

1421
01:08:21,630 --> 01:08:25,890
retur ikke-negative verdier
er fordi vi ønsker å

1422
01:08:25,890 --> 01:08:27,670
har en sentinel verdi.

1423
01:08:27,670 --> 01:08:32,617
Så mer spesifikt, hvorfor ikke bare
tilbake falsk i tilfeller med feil?

1424
01:08:32,617 --> 01:08:33,099
Yeah.

1425
01:08:33,099 --> 01:08:35,510
>> PUBLIKUM: Du har sviktet
å returnere et heltall.

1426
01:08:35,510 --> 01:08:36,630
>> DAVID J. MALAN: Nettopp.

1427
01:08:36,630 --> 01:08:38,569
Og det er her C blir
ganske begrensende.

1428
01:08:38,569 --> 01:08:40,590
Hvis du sier at du kommer
å returnere en int, har du

1429
01:08:40,590 --> 01:08:41,279
å returnere en int.

1430
01:08:41,279 --> 01:08:43,689
Du kan ikke få fancy og begynne retur
en bool eller en flåte eller en

1431
01:08:43,689 --> 01:08:45,040
streng eller noe sånt.

1432
01:08:45,040 --> 01:08:49,370
Nå, i mellomtiden, Javascript og PHP og
noen andre språk kan faktisk

1433
01:08:49,370 --> 01:08:51,310
har du retur annerledes
typer verdier.

1434
01:08:51,310 --> 01:08:54,819
Og det kan faktisk være nyttig, der
du kan returnere positive Ints, nuller,

1435
01:08:54,819 --> 01:08:59,439
negative ints, eller usann eller null
selv å betegne feil.

1436
01:08:59,439 --> 01:09:01,890
Men vi har ikke det
allsidighet i C.

1437
01:09:01,890 --> 01:09:04,569
>> Så med dequeue, hva vi
foreslår å gjøre er -

1438
01:09:04,569 --> 01:09:07,350

1439
01:09:07,350 --> 01:09:09,830
>> ROB BOWDEN: Du kan returnere false.

1440
01:09:09,830 --> 01:09:13,189
Det er bare den falske er hasj
definere falsk null.

1441
01:09:13,189 --> 01:09:16,000
Så hvis du return false,
du returnerer null.

1442
01:09:16,000 --> 01:09:25,470
Og null er en gyldig ting i vår kø,
mens negative 1 er ikke dersom

1443
01:09:25,470 --> 01:09:27,000
falsk skjedde til å være negativ en.

1444
01:09:27,000 --> 01:09:29,972
Men du bør ikke engang
trenger å vite det.

1445
01:09:29,972 --> 01:09:32,399
>> DAVID J. MALAN: Det er
hvorfor jeg ikke si det.

1446
01:09:32,399 --> 01:09:36,450
>> ROB BOWDEN: Men det var ikke sant
at du ikke kan returnere false.

1447
01:09:36,450 --> 01:09:37,700
>> DAVID J. MALAN: Sure.

1448
01:09:37,700 --> 01:09:40,920

1449
01:09:40,920 --> 01:09:44,240
Så dequeue, merker vi aksepterer
ugyldig som sin argument.

1450
01:09:44,240 --> 01:09:45,479
Og det er fordi vi ikke er
passerer noe i.

1451
01:09:45,479 --> 01:09:48,359
Vi ønsker bare å fjerne elementet
foran i køen.

1452
01:09:48,359 --> 01:09:49,819
Så hvordan kan vi gå om du gjør dette?

1453
01:09:49,819 --> 01:09:51,290
Vel, først, la oss gjøre dette
rask tilregnelighet sjekk.

1454
01:09:51,290 --> 01:09:53,350
Hvis køen størrelse er 0, er det
noe arbeid som må gjøres.

1455
01:09:53,350 --> 01:09:54,210
Returnere negativ en.

1456
01:09:54,210 --> 01:09:54,800
Ferdig.

1457
01:09:54,800 --> 01:09:56,340
Så det er noen få linjer av mitt program.

1458
01:09:56,340 --> 01:09:58,180
Så bare fire linjer forbli.

1459
01:09:58,180 --> 01:10:01,310
>> Så her jeg velger å minske
størrelse.

1460
01:10:01,310 --> 01:10:04,620
Og minskning av størrelsen effektivt
betyr at jeg glemmer

1461
01:10:04,620 --> 01:10:06,010
noe er der inne.

1462
01:10:06,010 --> 01:10:09,910
Men jeg må også oppdatere der
forsiden av tallene er.

1463
01:10:09,910 --> 01:10:11,620
Så for å gjøre det, trenger jeg
å gjøre to ting.

1464
01:10:11,620 --> 01:10:16,390
Trenger jeg først å huske hva nummeret
er på forsiden av køen,

1465
01:10:16,390 --> 01:10:17,860
fordi jeg trenger å returnere den tingen.

1466
01:10:17,860 --> 01:10:20,910
Så jeg ønsker ikke å tilfeldigvis glemmer
om det og deretter overskrive den.

1467
01:10:20,910 --> 01:10:22,840
Jeg bare kommer til å huske i en int.

1468
01:10:22,840 --> 01:10:27,310
>> Og nå, jeg ønsker å oppdatere
q.front å bli q.front en.

1469
01:10:27,310 --> 01:10:30,070
Så hvis dette var den første personen i
linje, nå, ønsker jeg å gjøre pluss en til

1470
01:10:30,070 --> 01:10:31,930
peke på den neste person i linje.

1471
01:10:31,930 --> 01:10:33,420
Men jeg må håndtere at wraparound.

1472
01:10:33,420 --> 01:10:37,270
Og hvis kapasiteten er en global konstant,
som kommer til å tillate meg å sørge for at

1473
01:10:37,270 --> 01:10:41,140
som jeg peker på den aller siste personen i
linje, vil modul-handling bringe

1474
01:10:41,140 --> 01:10:43,840
me tilbake til null ved
foran i køen.

1475
01:10:43,840 --> 01:10:46,050
Og som håndterer wraparound her.

1476
01:10:46,050 --> 01:10:48,950
Og så fortsetter jeg å gå tilbake n.

1477
01:10:48,950 --> 01:10:51,530
>> Nå, strengt tatt, det gjorde jeg ikke
nødt til å erklære n.

1478
01:10:51,530 --> 01:10:53,880
Jeg trengte ikke å ta tak i det og lagre det
midlertidig, fordi verdien ligger

1479
01:10:53,880 --> 01:10:54,740
det fortsatt.

1480
01:10:54,740 --> 01:10:57,490
Så jeg kunne bare gjøre det rette aritmetikk
å returnere tidligere leder

1481
01:10:57,490 --> 01:10:58,450
av køen.

1482
01:10:58,450 --> 01:11:01,850
Men jeg følte bare at dette var mer klar
å faktisk ta tak i int, legg den

1483
01:11:01,850 --> 01:11:04,320
i n, og deretter tilbake som
for klarhet skyld, men

1484
01:11:04,320 --> 01:11:05,735
ikke strengt nødvendig.

1485
01:11:05,735 --> 01:11:09,313

1486
01:11:09,313 --> 01:11:12,130
Psst.

1487
01:11:12,130 --> 01:11:13,410
De er alle pronounceable i hodet mitt.

1488
01:11:13,410 --> 01:11:15,940

1489
01:11:15,940 --> 01:11:19,110
>> ROB BOWDEN: Så første spørsmål
er den binært tre problem.

1490
01:11:19,110 --> 01:11:22,140
Så første spørsmål er, vi er
gitt disse tallene.

1491
01:11:22,140 --> 01:11:27,160
Og vi ønsker å liksom sette dem inn
disse nodene slik at det er en

1492
01:11:27,160 --> 01:11:30,110
gyldig binært søketre.

1493
01:11:30,110 --> 01:11:36,260
Så en ting å huske om
binære søketrær er at det ikke er

1494
01:11:36,260 --> 01:11:39,800
bare at den tingen til venstre
er mindre og det å

1495
01:11:39,800 --> 01:11:41,120
høyre er større.

1496
01:11:41,120 --> 01:11:44,580
Det må være at hele treet til
til venstre er mindre, og hele treet

1497
01:11:44,580 --> 01:11:45,740
til høyre er større.

1498
01:11:45,740 --> 01:11:55,260
>> Så hvis jeg legger 34 her på toppen, og deretter
Jeg satt 20 her, så det er gyldig så

1499
01:11:55,260 --> 01:11:56,970
langt, fordi her 34 opp.

1500
01:11:56,970 --> 01:11:57,920
20 går mot venstre.

1501
01:11:57,920 --> 01:11:58,950
Så det er mindre.

1502
01:11:58,950 --> 01:12:03,640
Men jeg kan da ikke sette 59 her, fordi
selv om 59 er på høyre side av 20,

1503
01:12:03,640 --> 01:12:06,140
det er fortsatt til venstre på 34..

1504
01:12:06,140 --> 01:12:10,760
Så med denne begrensningen i tankene,
enkleste måten sannsynligvis løse dette

1505
01:12:10,760 --> 01:12:14,330
Problemet er å bare sortere
av disse tallene -

1506
01:12:14,330 --> 01:12:18,720
slik at 20, 34, 36, 52, 59, 106..

1507
01:12:18,720 --> 01:12:21,640
Og så setter de
fra venstre til høyre.

1508
01:12:21,640 --> 01:12:23,390
>> Så 20 går her.

1509
01:12:23,390 --> 01:12:24,630
34 går her.

1510
01:12:24,630 --> 01:12:25,830
36 går her.

1511
01:12:25,830 --> 01:12:29,360
52, 59, 106..

1512
01:12:29,360 --> 01:12:34,730
Og du også kunne ha funnet ut med
noen plugge inn og realisere,

1513
01:12:34,730 --> 01:12:38,830
oh, vent, jeg har ikke nok tall
å fylle dette inn over her.

1514
01:12:38,830 --> 01:12:42,170
Så jeg trenger å reshift hva min
rute notat kommer til å være.

1515
01:12:42,170 --> 01:12:47,490
Men legge merke til at i den endelige tre, hvis
du leser fra venstre til høyre, er det i

1516
01:12:47,490 --> 01:12:48,740
stigende rekkefølge.

1517
01:12:48,740 --> 01:12:52,150

1518
01:12:52,150 --> 01:12:56,540
>> Så nå ønsker vi å erklære hva
struct kommer til å være for

1519
01:12:56,540 --> 01:12:58,300
noder i dette treet.

1520
01:12:58,300 --> 01:13:02,720
Så hva trenger vi i et binært tre?

1521
01:13:02,720 --> 01:13:05,830
Så vi har en verdi av typen
int, så noen int verdi.

1522
01:13:05,830 --> 01:13:07,220
Jeg vet ikke hva vi kalte
det i oppløsningen -

1523
01:13:07,220 --> 01:13:08,500
int n.

1524
01:13:08,500 --> 01:13:13,570
Vi trenger en peker til venstre barn
og en peker til høyre for barnet.

1525
01:13:13,570 --> 01:13:17,540
Så det kommer til å se slik ut.

1526
01:13:17,540 --> 01:13:20,510
Og det vil faktisk se før
når ble det dobbelt-linked

1527
01:13:20,510 --> 01:13:25,090
liste ting, så varsel -

1528
01:13:25,090 --> 01:13:27,860
Jeg er nødt til å bla alle
vei ned igjen til problemet 11.

1529
01:13:27,860 --> 01:13:30,980

1530
01:13:30,980 --> 01:13:36,390
>> Så merker det ser identisk med denne,
bortsett fra at vi bare måtte ringe disse

1531
01:13:36,390 --> 01:13:38,590
forskjellige navn.

1532
01:13:38,590 --> 01:13:41,440
Vi har fortsatt et heltall
verdi og to pekere.

1533
01:13:41,440 --> 01:13:44,850
Det er bare det at i stedet for å behandle
pekere som peker til neste ting

1534
01:13:44,850 --> 01:13:47,955
og den forrige ting, vi behandler
pekere til å peke på et venstre barn

1535
01:13:47,955 --> 01:13:49,205
og høyre barn.

1536
01:13:49,205 --> 01:13:57,372

1537
01:13:57,372 --> 01:13:57,860
OK.

1538
01:13:57,860 --> 01:13:59,650
Så det er vårt struct node.

1539
01:13:59,650 --> 01:14:03,920
Og nå, den eneste funksjon vi trenger å
implementere til dette er traversen, hvilken

1540
01:14:03,920 --> 01:14:08,320
vi ønsker å gå over treet, trykking
ut verdiene av de tre i rekkefølge.

1541
01:14:08,320 --> 01:14:15,241
>> Så ser her, ville vi ønsker å skrive ut
med 20, 34, 36, 52, 59, og 106.

1542
01:14:15,241 --> 01:14:17,970
Hvordan kan vi oppnå det?

1543
01:14:17,970 --> 01:14:18,890
Så det er ganske lik.

1544
01:14:18,890 --> 01:14:22,910
Hvis du så i det siste eksamen problemet
at du ønsket å skrive ut

1545
01:14:22,910 --> 01:14:25,940
hele treet med komma i mellom
alt, var det faktisk enda

1546
01:14:25,940 --> 01:14:27,320
enklere enn det.

1547
01:14:27,320 --> 01:14:30,950
Så her er løsningen.

1548
01:14:30,950 --> 01:14:33,110
Dette var betydelig enklere
hvis du gjorde det rekursivt.

1549
01:14:33,110 --> 01:14:36,650
Jeg vet ikke om noen forsøkte
å gjøre det iterativt.

1550
01:14:36,650 --> 01:14:38,340
>> Men først må vi vår base case.

1551
01:14:38,340 --> 01:14:39,660
Hva om roten er null?

1552
01:14:39,660 --> 01:14:40,610
Så vi bare kommer til å gå tilbake.

1553
01:14:40,610 --> 01:14:42,300
Vi ønsker ikke å skrive noe.

1554
01:14:42,300 --> 01:14:45,940
Else vi kommer til å traversere
rekursivt ned.

1555
01:14:45,940 --> 01:14:48,140
Skriv ut hele venstre subtre.

1556
01:14:48,140 --> 01:14:51,440
Så ut alt mindre
enn min nåværende verdi.

1557
01:14:51,440 --> 01:14:53,930
Og så kommer jeg til å skrive meg selv.

1558
01:14:53,930 --> 01:14:57,310
Og så kommer jeg til å recurse ned min
hele høyre subtre, så alt

1559
01:14:57,310 --> 01:14:58,810
større enn min verdi.

1560
01:14:58,810 --> 01:15:03,870
Og dette kommer til å skrive ut
ut alt i orden.

1561
01:15:03,870 --> 01:15:05,860
Spørsmål om hvordan dette faktisk
oppnår det?

1562
01:15:05,860 --> 01:15:09,892

1563
01:15:09,892 --> 01:15:12,545
>> PUBLIKUM: Jeg har et spørsmål
på [uhørbart].

1564
01:15:12,545 --> 01:15:15,090

1565
01:15:15,090 --> 01:15:23,550
>> ROB BOWDEN: Så en måte å tilnærme
noen rekursive problemet er å bare tenke

1566
01:15:23,550 --> 01:15:26,275
om det som du må tenke
om alle hjørne tilfeller.

1567
01:15:26,275 --> 01:15:32,150

1568
01:15:32,150 --> 01:15:38,110
Så tenk på at vi ønsker å
skrive ut hele dette treet.

1569
01:15:38,110 --> 01:15:42,030
Så alt vi kommer til å fokusere på
er dette bestemt node -

1570
01:15:42,030 --> 01:15:43,740
36.

1571
01:15:43,740 --> 01:15:47,420
De rekursive samtaler, vi later
de bare fungere.

1572
01:15:47,420 --> 01:15:54,000
Så her, dette rekursive kall til
travers, vi uten å tenke

1573
01:15:54,000 --> 01:15:58,640
om det, bare krysser venstre
tre, forestille seg at allerede skriver ut 20

1574
01:15:58,640 --> 01:16:00,730
og 34 for oss.

1575
01:16:00,730 --> 01:16:03,350
Og så når vi til slutt rekursivt
kaller traversen på

1576
01:16:03,350 --> 01:16:07,890
rett, vil det riktig ut
52, 59 og 106 for oss.

1577
01:16:07,890 --> 01:16:13,620
>> Så gitt at dette kan skrive ut 20, 34, og
den andre kan skrive ut 52, 59, 108,

1578
01:16:13,620 --> 01:16:17,180
alt vi trenger for å være i stand til å gjøre er å skrive ut
oss selv i midten av det.

1579
01:16:17,180 --> 01:16:21,250
Så skrive ut alt før oss.

1580
01:16:21,250 --> 01:16:27,710
Skriv ut oss selv, slik at den aktuelle noden print
36, vanlig printf, og deretter

1581
01:16:27,710 --> 01:16:31,170
skrive ut alt etter oss.

1582
01:16:31,170 --> 01:16:32,730
>> DAVID J. MALAN: Dette er hvor rekursjon
blir virkelig vakker.

1583
01:16:32,730 --> 01:16:36,270
Det er denne fantastiske porsjon tro hvor
du gjør den minste bit av arbeid.

1584
01:16:36,270 --> 01:16:38,460
Og så la noen
andre gjøre resten.

1585
01:16:38,460 --> 01:16:40,180
Og at noen andre
er, ironisk nok, du.

1586
01:16:40,180 --> 01:16:44,260

1587
01:16:44,260 --> 01:16:48,360
Så for alvorlige brownie poeng, hvis
du blar opp på spørsmålene -

1588
01:16:48,360 --> 01:16:50,530
>> ROB BOWDEN: På spørsmål?

1589
01:16:50,530 --> 01:16:53,490
>> DAVID J. MALAN: Og ned litt til
tallene, er det noen som vet hvor

1590
01:16:53,490 --> 01:16:55,190
disse tallene kommer fra?

1591
01:16:55,190 --> 01:16:56,610
>> ROB BOWDEN: Jeg har bokstavelig talt ingen anelse om.

1592
01:16:56,610 --> 01:16:59,794
>> DAVID J. MALAN: De vises
hele quizen.

1593
01:16:59,794 --> 01:17:01,150
>> PUBLIKUM: Er de de samme tallene?

1594
01:17:01,150 --> 01:17:01,910
>> DAVID J. MALAN: Disse tallene.

1595
01:17:01,910 --> 01:17:03,260
Et lite påskeegg.

1596
01:17:03,260 --> 01:17:08,100
Så for de av dere ser på nettet på
hjemme, hvis du kan fortelle oss via e-post til

1597
01:17:08,100 --> 01:17:12,680
heads@CS50.net hvilken betydning
av disse tilbakevendende seks tallene er

1598
01:17:12,680 --> 01:17:18,560
hele Quiz 1, vil vi dusje deg
med fantastisk oppmerksomhet på finale

1599
01:17:18,560 --> 01:17:21,610
foredrag og en stress ball.

1600
01:17:21,610 --> 01:17:25,460

1601
01:17:25,460 --> 01:17:27,790
Nice, subtil.

1602
01:17:27,790 --> 01:17:29,570
>> ROB Bowden: Noen siste spørsmål
om noe på quiz?

1603
01:17:29,570 --> 01:17:32,608