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

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

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

4
00:00:16,790 --> 00:00:18,340
Vi troede, vi ville indvie
denne tradition i år.

5
00:00:18,340 --> 00:00:20,960
Og det vil være en mulighed
at gå gennem

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

7
00:00:22,220 --> 00:00:26,160
Og vi vil fremskynde eller sinke baseret
på renter af dem her.

8
00:00:26,160 --> 00:00:29,730
>> Så er du sikkert her, fordi du er
interesseret i, hvordan du kunne have eller

9
00:00:29,730 --> 00:00:31,170
burde have besvaret nogle
af disse problemer.

10
00:00:31,170 --> 00:00:33,300
Så hvorfor gør vi ikke tage et kig
på dette afsnit først?

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

12
00:00:34,450 --> 00:00:37,600
Dette gav dig tre forskellige versioner
af et program, der var, i sidste ende,

13
00:00:37,600 --> 00:00:39,650
beregnet til at få en snor fra en bruger.

14
00:00:39,650 --> 00:00:42,530
Hvorvidt det gjorde det var
overladt til dig at afgøre.

15
00:00:42,530 --> 00:00:45,150
>> Og vi spurgte i spørgsmål 0,
antage, at version 1 er

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

17
00:00:46,400 --> 00:00:48,860
Hvorfor kunne det program segfault?

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

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

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

21
00:00:54,489 --> 00:00:59,260
>> PUBLIKUM: Så jeg kan huske at se dette i
en tidligere eksempel at se på

22
00:00:59,260 --> 00:01:05,506
char * s og se scanningen af ​​s og
se, fordi det er en pegepind, hvordan

23
00:01:05,506 --> 00:01:07,971
påvirkede det, hvad du har scannet ind?

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

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

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

27
00:01:11,480 --> 00:01:14,830
Så i sidste ende, kilden til ethvert problem
formentlig kommer til at reducere

28
00:01:14,830 --> 00:01:16,210
denne variabel 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 for denne variabel er
char *, hvilket betyder, at det kommer til at

31
00:01:19,900 --> 00:01:22,570
indeholde adressen på en karakter.

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

33
00:01:23,850 --> 00:01:28,330
Det kommer til at indeholde adressen på
en karakter eller, mere generelt,

34
00:01:28,330 --> 00:01:32,110
adressen på det første tegn i
en hel blok af karakterer.

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

36
00:01:36,680 --> 00:01:40,960
et format kode, som% s, læse
en snor i de luns af

37
00:01:40,960 --> 00:01:42,330
hukommelsen på denne adresse.

38
00:01:42,330 --> 00:01:46,040
Men fordi der er ingen lighedstegn før
at semikolon den første

39
00:01:46,040 --> 00:01:49,310
linje kode, fordi vi faktisk ikke
tildele nogen hukommelse med

40
00:01:49,310 --> 00:01:53,020
malloc, fordi det faktisk ikke
tildele et array af nogle størrelse, alle

41
00:01:53,020 --> 00:01:57,620
du laver læser brugerens
tastatur input til nogle komplet

42
00:01:57,620 --> 00:02:00,490
skrald værdi, hvilket
er i s som standard.

43
00:02:00,490 --> 00:02:04,480
Så oddsene er du vil segfault hvis
at adressen ikke bare så ske

44
00:02:04,480 --> 00:02:08,009
at være en værdi, som du kan,
i virkeligheden, så skriv til.

45
00:02:08,009 --> 00:02:10,889
Så slemt ikke at tildele
din hukommelse der.

46
00:02:10,889 --> 00:02:13,150
>> Så i spørgsmål 1, spurgte vi,
antage, at version 2 er

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

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

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

50
00:02:17,990 --> 00:02:21,470
Og der er virkelig kun én
indlysende måde, hvor du kan

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

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

53
00:02:23,730 --> 00:02:28,180
Enhver tid vi bruger c i hukommelsen, hvad
kan du gøre for at fremkalde en segfault

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

55
00:02:30,718 --> 00:02:35,560
>> PUBLIKUM: Hvis du bruger dette input i
en streng, der er længere end 49

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

57
00:02:35,975 --> 00:02:37,260
>> DAVID J. MALAN: Præcis.

58
00:02:37,260 --> 00:02:41,420
Hver gang du ser noget fast længde
når det kommer til et array, din

59
00:02:41,420 --> 00:02:44,650
radar skal gå væk fra at dette kunne være
problematisk, hvis du ikke kontrollere

60
00:02:44,650 --> 00:02:45,810
grænser for et array.

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

62
00:02:46,650 --> 00:02:47,910
Vi bruger stadig scanf.

63
00:02:47,910 --> 00:02:52,200
Vi bruger stadig% s, hvilket betyder, prøve
at læse en streng fra brugeren.

64
00:02:52,200 --> 00:02:56,300
Det kommer til at blive læst ind i s, der,
på dette punkt, er effektivt

65
00:02:56,300 --> 00:02:58,570
adressen på en luns af hukommelse
eller det er tilsvarende.

66
00:02:58,570 --> 00:03:02,080
Det er navnet på et array
karakterer hukommelse.

67
00:03:02,080 --> 00:03:07,610
>> Men præcis det, hvis du læser en streng
der er længere end 49 tegn, 49

68
00:03:07,610 --> 00:03:10,440
fordi du har brug for plads til backslash
0, du kommer til at løbe over

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

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

71
00:03:16,410 --> 00:03:18,560
Men på et tidspunkt, OS
vil sige, no.

72
00:03:18,560 --> 00:03:21,270
Dette er absolut ikke hukommelse
du får lov til at røre ved.

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

74
00:03:23,380 --> 00:03:26,650
>> Så der bør heuristik være
gang du har fået fast længde, du har

75
00:03:26,650 --> 00:03:30,150
at sikre, at du tjekker længden
af, hvad det er du prøver

76
00:03:30,150 --> 00:03:31,090
at læse i det.

77
00:03:31,090 --> 00:03:35,110
>> PUBLIKUM: Så for at løse det, kan du
have haft en erklæring tjekker faktisk

78
00:03:35,110 --> 00:03:37,140
er længden større
eller mindre end?

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

80
00:03:37,730 --> 00:03:41,706
Du skal bare have en tilstand
der siger, at hvis -

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

82
00:03:46,080 --> 00:03:49,060
brugeren kommer til at skrive, fordi
du har hønen og ægget.

83
00:03:49,060 --> 00:03:51,860
Ikke før du har læst det med scanf
kan du regne ud, hvor lang tid det er.

84
00:03:51,860 --> 00:03:54,500
Men på dette punkt, er det for sent,
fordi du allerede har læst det i

85
00:03:54,500 --> 00:03:55,710
nogle blok af hukommelse.

86
00:03:55,710 --> 00:03:59,590
Så som en sidebemærkning de CS50 bibliotekets undgår
dette spørgsmål helt, tilbagekaldelse

87
00:03:59,590 --> 00:04:01,060
ved hjælp fgetc.

88
00:04:01,060 --> 00:04:05,390
Og det lyder ét tegn ad gangen,
tip-toeing sammen, vel vidende, at du

89
00:04:05,390 --> 00:04:08,060
kan ikke løbe en karakter, hvis
læse en ad gangen.

90
00:04:08,060 --> 00:04:11,580
>> Fangsten er med getString tilbagekaldelse er
at vi er nødt til konstant at re-size

91
00:04:11,580 --> 00:04:13,590
at bid af hukommelse, som
er bare en smerte.

92
00:04:13,590 --> 00:04:15,310
Det er en masse linjer
kode til at gøre det.

93
00:04:15,310 --> 00:04:18,779
Så en anden fremgangsmåde ville være at
faktisk bruger en fætter, så

94
00:04:18,779 --> 00:04:19,790
til at tale, af scanf.

95
00:04:19,790 --> 00:04:22,820
Der er varianter af en masse af disse
funktioner, der faktisk tjekke

96
00:04:22,820 --> 00:04:25,870
Længden af ​​hvor mange tegn
kan du læse maksimalt.

97
00:04:25,870 --> 00:04:29,430
Og du kunne specificere, ikke læse
mere end 50 tegn.

98
00:04:29,430 --> 00:04:34,110
Så det ville være en anden tilgang, men
mindre imødekommende af større input.

99
00:04:34,110 --> 00:04:37,040
>> Så spørgsmål 2 spørger, formoder, at versionen
3 er kompileret og henrettet.

100
00:04:37,040 --> 00:04:39,960
Hvorfor kunne det program segfault?

101
00:04:39,960 --> 00:04:42,650
Så denne ene er faktisk det samme
answer, selvom det

102
00:04:42,650 --> 00:04:43,590
ser lidt avanceret.

103
00:04:43,590 --> 00:04:46,440
Vi bruger malloc, som føles som
vi giver os selv flere muligheder.

104
00:04:46,440 --> 00:04:48,030
Og så er vi frigør at
hukommelse i slutningen.

105
00:04:48,030 --> 00:04:49,580
Det er stadig kun 50 bytes hukommelse.

106
00:04:49,580 --> 00:04:53,620
Så vi kan stadig forsøge at læse
i 51, 52, 1000 byte.

107
00:04:53,620 --> 00:04:55,830
Det kommer til at segfault for
nøjagtig den samme grund.

108
00:04:55,830 --> 00:04:57,530
>> Men der er en anden grund også.

109
00:04:57,530 --> 00:05:03,890
Hvad andet kunne allokere afkast udover
adressen på en luns af hukommelse?

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 tjekker for
det, kan vi gøre noget

112
00:05:07,560 --> 00:05:11,350
dum anden grund, nemlig at
vi kan fortælle scanf, læse

113
00:05:11,350 --> 00:05:16,050
brugerens input fra tastaturet
i 0 placering, AKA null.

114
00:05:16,050 --> 00:05:18,890
Og det samme vil helt sikkert
udløse en segfault.

115
00:05:18,890 --> 00:05:21,590
Så for quizzen formål, vi ville
har accepteret en af ​​disse som en

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

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

118
00:05:23,420 --> 00:05:25,720
Den ene er lidt mere nuanceret.

119
00:05:25,720 --> 00:05:28,975
>> Endelig med hensyn til programmets
brug af hukommelse, hvordan gør version 2 og

120
00:05:28,975 --> 00:05:30,350
version 3 forskellige?

121
00:05:30,350 --> 00:05:35,070
Så for hvad det er værd, så vi en
tilsyneladende endeløs forsyning af mulige

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

123
00:05:35,770 --> 00:05:39,300
Og blandt folks svar, hvad vi var
håber på, men vi har accepteret andre

124
00:05:39,300 --> 00:05:42,250
ting, var nogle omtale af
kendsgerning, at version 2 bruger

125
00:05:42,250 --> 00:05:44,560
den såkaldte stak.

126
00:05:44,560 --> 00:05:46,710
Version 3 bruger bunke.

127
00:05:46,710 --> 00:05:50,060
Og funktionelt, det ikke rigtig
gøre alle, at meget af en forskel.

128
00:05:50,060 --> 00:05:54,040
I slutningen af ​​dagen, er vi stadig
bare at få 50 bytes hukommelse.

129
00:05:54,040 --> 00:05:56,640
>> Men det var et af de mulige svar
at vi ledte på.

130
00:05:56,640 --> 00:05:59,730
Men du vil se, som du får dine quizzer
tilbage fra TFS, at vi gjorde

131
00:05:59,730 --> 00:06:04,330
acceptere andre diskussioner af deres
forskellige anvendelser af hukommelse samt.

132
00:06:04,330 --> 00:06:08,600
Men stable og bunke ville have været
en let løsning til at gå med.

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

134
00:06:11,150 --> 00:06:12,400
Jeg giver dig Rob.

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

136
00:06:18,360 --> 00:06:20,210
>> ROB BOWDEN: So problem 4..

137
00:06:20,210 --> 00:06:21,985
Dette er den ene, hvor du var nødt til at fylde
i antallet af bytes ud af alle

138
00:06:21,985 --> 00:06:23,460
disse forskellige typer anvendes.

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

140
00:06:24,830 --> 00:06:27,930
Antag en 32-bit arkitektur,
som denne CS50 apparatet.

141
00:06:27,930 --> 00:06:33,530
Så en af ​​de grundlæggende ting om
32-bit arkitekturer, der fortæller os

142
00:06:33,530 --> 00:06:37,490
præcis hvor stor en pointer går
at være i arkitekturen.

143
00:06:37,490 --> 00:06:43,020
>> Så det samme, vi ved, at enhver pointer
type er 32-bit eller 4 byte.

144
00:06:43,020 --> 00:06:46,010
Så se på dette bord, en
node * er en pointer type.

145
00:06:46,010 --> 00:06:47,250
Det kommer til at være 4 bytes.

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

147
00:06:51,640 --> 00:06:53,590
Og så kommer til at være 4 bytes.

148
00:06:53,590 --> 00:06:58,270
String, så det ikke ligner en
pointer endnu, men typedef, en

149
00:06:58,270 --> 00:07:01,590
streng er bare en char *, som
er en pointer type.

150
00:07:01,590 --> 00:07:03,550
Så det kommer til at være 4 bytes.

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

152
00:07:06,150 --> 00:07:09,350
Nu node og elev er
en smule mere kompliceret.

153
00:07:09,350 --> 00:07:15,160
Så ser på node og elev, ser vi
node et heltal og en pointer.

154
00:07:15,160 --> 00:07:18,050
Og studerende er to pointere
inde i den.

155
00:07:18,050 --> 00:07:23,340
Så i det mindste for vores sag her, den måde
at vi ender beregning af størrelsen af

156
00:07:23,340 --> 00:07:27,020
denne struct er blot tilføje op alt
der er inde i struct.

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

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

159
00:07:32,830 --> 00:07:35,820
Og så en knude går
at tage op 8 byte.

160
00:07:35,820 --> 00:07:39,490
Og tilsvarende for studerende, vi har en
pointer, der er 4 bytes og en anden

161
00:07:39,490 --> 00:07:40,770
pointer, der er 4 byte.

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

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

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

165
00:07:48,950 --> 00:07:50,240
Spørgsmå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, der ville

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

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

171
00:08:01,790 --> 00:08:05,830
Så 64-bit arkitektur, er det, igen,
ændringer, som grundlæggende ting, at en

172
00:08:05,830 --> 00:08:08,910
pointer er nu 64 bits.

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

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

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

176
00:08:15,420 --> 00:08:18,617
En studerende, som var to pegepinde,
Nå, nu det kommer til at

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 at gøre 16 bytes.

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

180
00:08:25,710 --> 00:08:27,800
Så denne pointeren går
at være 8 byte.

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

182
00:08:28,930 --> 00:08:30,870
Så en node er kun vil
at være 12 byte.

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

184
00:08:36,309 --> 00:08:39,280
Alle andre spørgsmål om at den ene?

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

186
00:08:44,500 --> 00:08:48,000
Og du skulle beskrive forhold
hvorunder disse kan

187
00:08:48,000 --> 00:08:49,810
blive returneret til dig.

188
00:08:49,810 --> 00:08:56,730
et problem, som jeg hørte nogle studerende
er, at de forsøgte at gøre

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

190
00:08:58,950 --> 00:09:02,320
Så når vi forsøger at gøre anmodningen
til serveren, går noget

191
00:09:02,320 --> 00:09:03,820
forkert på vores ende.

192
00:09:03,820 --> 00:09:07,660
Men generelt er disse koder er
bliver returneret af serveren.

193
00:09:07,660 --> 00:09:11,720
Så vi ønsker at finde ud af, hvad der foregår
forkert eller højre på den server,

194
00:09:11,720 --> 00:09:14,280
forårsager disse ting, der skal returneres.

195
00:09:14,280 --> 00:09:18,670
Så hvorfor kan en server returnerer
status kode 200?

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

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

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

199
00:09:23,730 --> 00:09:27,850
Så noget om held
anmodningen gik igennem.

200
00:09:27,850 --> 00:09:30,260
Og de er i stand til at vende tilbage
uanset hvad du bad om.

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

202
00:09:32,240 --> 00:09:35,662
Hvad med 302 findes?

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

204
00:09:36,618 --> 00:09:39,008
>> PUBLIKUM: Serveren ledte
for hvad du har bedt om.

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

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

207
00:09:42,850 --> 00:09:47,720
>> ROB BOWDEN: Så serveren var
udkig efter, hvad du ville.

208
00:09:47,720 --> 00:09:51,682
Så bare at kigge her, 302 fundet,
det var i stand til at finde det.

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

210
00:09:53,035 --> 00:09:54,388
Fundet betyder, at de fandt det.

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

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

213
00:09:58,120 --> 00:10:00,160
>> ROB BOWDEN: So 302 fundet.

214
00:10:00,160 --> 00:10:02,350
Serveren er i stand til at finde
hvad 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: Forskellen mellem
dette 302 og 200 er, at den

217
00:10:08,180 --> 00:10:09,280
ved, hvad du ønsker.

218
00:10:09,280 --> 00:10:12,000
Men det er ikke præcis, hvor
du ville spørge.

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

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

221
00:10:16,510 --> 00:10:19,590
Den kender, åh, jeg vil
at returnere dig dette.

222
00:10:19,590 --> 00:10:21,070
Men det er på en anden URL.

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

224
00:10:23,534 --> 00:10:26,950
>> DAVID J. MALAN: Det er et stykke, der sagde
at vi gav jer en omdirigering

225
00:10:26,950 --> 00:10:30,830
funktion, der anvendes header funktion
, som til gengæld, udskrives placering,

226
00:10:30,830 --> 00:10:34,110
colon og derefter webadresse,
du vil afvise brugeren.

227
00:10:34,110 --> 00:10:37,480
Selvom du ikke se 302
udtrykkeligt der, det er, hvad PHP

228
00:10:37,480 --> 00:10:41,550
ville magisk Indsæt så header
sige præcis, hvad Rob sagde, at der -

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

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å hvad 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 dybest set siger, at klienten

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

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

238
00:11:03,260 --> 00:11:07,670
Tja, det typiske svar, vi var
forventer er noget lignende, de filer,

239
00:11:07,670 --> 00:11:08,920
ikke chmodded korrekt.

240
00:11:08,920 --> 00:11:11,590
Det er sandsynligvis under hvilke omstændigheder
du så dem.

241
00:11:11,590 --> 00:11:18,920
Men der er en grund til, at kunden
kunne være skyld her.

242
00:11:18,920 --> 00:11:20,440
Der er faktisk en anden status kode -

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

244
00:11:21,210 --> 00:11:22,820
Så disse er meget ens.

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

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

247
00:11:26,130 --> 00:11:31,890
Og så uautoriseret du udelukkende
få, hvis du ikke er logget ind

248
00:11:31,890 --> 00:11:34,520
Men logger ind kan betyde
at du har tilladelse.

249
00:11:34,520 --> 00:11:37,930
Men hvis du allerede er logget ind, og du
stadig ikke har tilladelse, 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 ind og ikke har
tilladelse, forbudt, er også

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

253
00:11:47,164 --> 00:11:48,900
>> DAVID J. MALAN: Og den mekanisme,
disse problemer er som regel

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 tilladelser
udsteder på filen eller mappen.

256
00:11:57,700 --> 00:11:59,220
>> ROB BOWDEN: Så 404 ikke fundet.

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

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

259
00:12:03,470 --> 00:12:10,150
Så i modsætning til 302, hvor det var ikke ligefrem
hvor du spørger, men det ved, hvad

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

261
00:12:12,710 --> 00:12:15,648
Og er du ikke anmoder om
noget gyldigt.

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

263
00:12:18,580 --> 00:12:22,310
418 Jeg er en tekande og derefter
500 intern 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 ved faktisk ikke, den klassificering
standard for denne.

268
00:12:30,640 --> 00:12:34,850
Men hvis din PHP kode havde noget
forkert i det, i teorien kunne

269
00:12:34,850 --> 00:12:39,650
faktisk segfault, i hvilket tilfælde denne
500 intern serverfejl, noget

270
00:12:39,650 --> 00:12:41,400
der er galt med din server
konfiguration.

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

272
00:12:44,320 --> 00:12:46,095
Eller noget slemt, der foregår.

273
00:12:46,095 --> 00:12:48,320
>> DAVID J. MALAN: Vi kunne se segfault
blandt nogle få folks svar.

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

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

276
00:12:53,820 --> 00:12:57,790
segfaulted, som, hvis disse mennesker
skruet op 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, det er næsten altid den

279
00:13:06,460 --> 00:13:10,490
resultat af en konfigurationsfil emne
med din webserver, eller som Rob sagde,

280
00:13:10,490 --> 00:13:13,200
en syntaksfejl, ligesom du
ikke lukke et tilbud.

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

282
00:13:16,180 --> 00:13:23,677
>> PUBLIKUM: Så for Shuttle PSET, jeg
tror da jeg gjorde det, når jeg klikkede på

283
00:13:23,677 --> 00:13:26,300
browser, men intet kom op,
hvad de kaldte hvide side.

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

285
00:13:28,056 --> 00:13:29,440
Jeg tror, ​​det var JavaScript, right?

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

287
00:13:29,770 --> 00:13:31,180
>> PUBLIKUM: Gid fejl
stadig komme op?

288
00:13:31,180 --> 00:13:34,290
>> ROB BOWDEN: Så du ville ikke have fået
denne fejl, fordi alt

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

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

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

292
00:13:42,000 --> 00:13:44,580
Og det var i stand til at vende tilbage
til jer alle disse ting -

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 kun, når din browser forsøger at
fortolke JavaScript-kode,

296
00:13:49,330 --> 00:13:51,370
Det er ligesom, vent, det er ikke
gyldigt JavaScript-fejl.

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

298
00:13:55,720 --> 00:13:58,210
Andre spørgsmål?

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

300
00:14:00,750 --> 00:14:04,120
>> DAVID J. MALAN: Så næste
op var nummer 11.

301
00:14:04,120 --> 00:14:07,610
Og 11 var den mest skræmmende
for en masse mennesker.

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

303
00:14:14,620 --> 00:14:18,570
Så det vigtigste ting at bemærke her
var, at dette var, ja, om

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

305
00:14:19,840 --> 00:14:23,160
Men det var ikke det samme som sidste år
dobbelt linkede liste problem,

306
00:14:23,160 --> 00:14:27,170
som ikke giver dig det forbehold, at
listen kunne i virkeligheden være usorteret.

307
00:14:27,170 --> 00:14:29,640
>> Så det faktum, at listen var usorteret
og det faktum, at dette ord var

308
00:14:29,640 --> 00:14:32,930
understregede der var ment til at formidle
at dette faktisk er en forenkling

309
00:14:32,930 --> 00:14:35,430
af, hvad der ellers ville have været
et mere udfordrende problem

310
00:14:35,430 --> 00:14:36,600
og en længere.

311
00:14:36,600 --> 00:14:40,760
Så en almindelig fejl her var at have sat
sidste års løsning på dit ene

312
00:14:40,760 --> 00:14:45,580
pager og så bare blindt kopiere denne
ned som svar, som er den rigtige

313
00:14:45,580 --> 00:14:48,520
svar på et andet spørgsmål
samme ånd.

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

315
00:14:51,340 --> 00:14:55,200
>> Så man har vi erklæret en node og
defineret i den sædvanlige måde her.

316
00:14:55,200 --> 00:14:59,230
Så vi definerede liste over være en global
pointer initialiseret til null.

317
00:14:59,230 --> 00:15:02,150
Så tilsyneladende er der to funktioner
vi har prototyper til her, indsætte

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

319
00:15:03,240 --> 00:15:06,600
Og så har vi nogle eksempler på kode her
for at gøre en flok indrykninger.

320
00:15:06,600 --> 00:15:09,930
Og så beder vi dig om at udfylde den
gennemførelse af indsatsen under sådan

321
00:15:09,930 --> 00:15:14,380
måde, at den indsætter n på listen
i konstant tid, også understreget,

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

323
00:15:15,730 --> 00:15:20,600
>> Så skønheden i at være i stand til at indsætte
i konstant tid, er, at det indebærer

324
00:15:20,600 --> 00:15:23,060
at du er nødt til at indsætte
det nye knudepunkt, hvor?

325
00:15:23,060 --> 00:15:23,690
I den forreste.

326
00:15:23,690 --> 00:15:27,760
Så det eliminerer heldigvis mindst
en af ​​de sager, der bruges til at kræve

327
00:15:27,760 --> 00:15:30,520
endnu flere linjer kode, ligesom det gjorde
sidste år, og selv i klassen, når vi

328
00:15:30,520 --> 00:15:34,040
talte gennem denne slags ting
med mennesker og med nogle

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

330
00:15:35,250 --> 00:15:39,190
Så i løsningen her, lad os springe over
til at bare at have en visuel på

331
00:15:39,190 --> 00:15:40,480
skærmen.

332
00:15:40,480 --> 00:15:42,230
>> Bemærk, at vi gør følgende.

333
00:15:42,230 --> 00:15:45,140
Og også bemærke den anden forenkling
var, at selv om det er

334
00:15:45,140 --> 00:15:48,280
allerede er til stede, så det betyder, at selvom
nummeret er der allerede, kan du

335
00:15:48,280 --> 00:15:50,280
bare blindt indsætte et andet
kopi af den.

336
00:15:50,280 --> 00:15:52,560
Og det blev også beregnet til at være en
forenkling, så du kunne

337
00:15:52,560 --> 00:15:54,940
fokusere på, virkelig, nogle af de mere
intellektuelt interessant del og

338
00:15:54,940 --> 00:15:58,090
ikke bare nogle ekstra fejlkontrol
betragtning af den begrænsede tid.

339
00:15:58,090 --> 00:16:02,880
>> Så i denne prøveopløsning, vi tildeler
en markør på den venstre

340
00:16:02,880 --> 00:16:04,510
side her til et knudepunkt.

341
00:16:04,510 --> 00:16:07,190
Nu indser, at pointer, som
Rob sagt, er kun 32 bits.

342
00:16:07,190 --> 00:16:09,060
Og det gør ikke rent faktisk indeholder
en adresse, indtil du

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

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

345
00:16:13,220 --> 00:16:16,550
Ligesom en god borger, kontrollerer vi, at
malloc er ikke i virkeligheden, null, således at

346
00:16:16,550 --> 00:16:18,690
vi ikke ved et uheld skaber
en segfault her.

347
00:16:18,690 --> 00:16:22,840
Og hver gang du bruger malloc i livet, du
bør være kontrol for null, lest

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

349
00:16:24,090 --> 00:16:28,460
>> Så initialisere vi, at nul ved
tildele n og tidligere og næste år.

350
00:16:28,460 --> 00:16:32,450
Og i dette tilfælde her, jeg initialiseret
tidligere til null, fordi denne nye

351
00:16:32,450 --> 00:16:34,780
node kommer til at være den nye
begyndelsen af ​​min liste.

352
00:16:34,780 --> 00:16:37,050
Så der vil være
intet før det.

353
00:16:37,050 --> 00:16:42,010
Og jeg vil i det væsentlige føje
eksisterende liste til den nye node ved

354
00:16:42,010 --> 00:16:44,700
indstilling næste lige at liste sig selv.

355
00:16:44,700 --> 00:16:47,120
Men jeg er ikke færdig endnu.

356
00:16:47,120 --> 00:16:51,780
Så hvis selve listen allerede eksisterede,
og der var mindst én node

357
00:16:51,780 --> 00:16:57,070
allerede på plads, hvis det er den liste
her, og jeg indsætte en ny node her, jeg

358
00:16:57,070 --> 00:17:01,840
nødt til at sørge for, at min tidligere node
peger bagud til min nye node,

359
00:17:01,840 --> 00:17:04,260
fordi dette er, igen,
en dobbelt linket liste.

360
00:17:04,260 --> 00:17:05,460
>> Så vi gør en sanity check.

361
00:17:05,460 --> 00:17:10,109
Hvis listen ikke er nul, hvis der er allerede
én eller flere noder der, så

362
00:17:10,109 --> 00:17:12,470
tilføje, at tilbage henvisning så at sige.

363
00:17:12,470 --> 00:17:15,420
Og så den allersidste ting, vi har brug
at gøre er faktisk opdatere den globale

364
00:17:15,420 --> 00:17:20,329
variabel liste sig til at pege
til denne nye knudepunkt.

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

366
00:17:21,790 --> 00:17:26,579
>> PUBLIKUM: I Markørpilen
[Uhørligt] er lig med nul, betyder at

367
00:17:26,579 --> 00:17:30,420
beskæftige sig med på listen, fordi
listen er nul?

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

369
00:17:30,596 --> 00:17:34,500
Det er simpelthen mig bliver proaktivt
forsigtig i at såfremt denne er min

370
00:17:34,500 --> 00:17:38,730
oprindelige liste med måske nogle flere knuder
herovre og jeg indsætte min

371
00:17:38,730 --> 00:17:42,380
ny node herovre, er der vil
at være noget herovre.

372
00:17:42,380 --> 00:17:44,720
Og jeg ønsker at fange denne idé
ved at forud for

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

374
00:17:47,740 --> 00:17:51,410
Og formentlig, hvis min kode er korrekt
og der er ingen anden måde at indsætte

375
00:17:51,410 --> 00:17:54,970
andre end denne funktion knudepunkter
formentlig, selv om listen allerede

376
00:17:54,970 --> 00:18:00,090
én eller flere noder i den, formentlig
liste, det første knudepunkt, vil have en

377
00:18:00,090 --> 00:18:02,750
foregående pointer null selv.

378
00:18:02,750 --> 00:18:03,550
>> PUBLIKUM: Og lige en opfølgning.

379
00:18:03,550 --> 00:18:08,139
Grunden til at du sætter markøren næste ligemænd
Listen er du gør markøren

380
00:18:08,139 --> 00:18:13,579
før liste, idet det peger
til den næste, jeg gætte -

381
00:18:13,579 --> 00:18:14,980
Jeg lad være -

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

383
00:18:15,450 --> 00:18:16,400
>> DAVID J. MALAN: Præcis.

384
00:18:16,400 --> 00:18:19,400
Og så lad os faktisk overveje to sager
virkelig her, selvom

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

386
00:18:22,070 --> 00:18:26,250
Men på et højt niveau, hvis denne udgør
listen og dette er et 32-bit

387
00:18:26,250 --> 00:18:29,560
markøren, simpleste scenario er
at dette er nul som standard.

388
00:18:29,560 --> 00:18:33,010
Og formoder jeg ønsker at indsætte
nummer 50 var det første nummer.

389
00:18:33,010 --> 00:18:37,640
Så jeg har tænkt mig at gå videre og tildele
en knude, som kommer til at indeholde

390
00:18:37,640 --> 00:18:38,770
tre områder -

391
00:18:38,770 --> 00:18:42,070
n, forrige, og næste år.

392
00:18:42,070 --> 00:18:44,580
>> Jeg har tænkt mig at sætte tallet 50
her, da dette vil være n..

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

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

395
00:18:48,530 --> 00:18:50,910
Og så hvad skal jeg gøre i denne sag?

396
00:18:50,910 --> 00:18:53,900
Tja, jeg har lige gjort linie 1 her.

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

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

399
00:18:57,740 --> 00:18:59,470
Så dette vil være nul.

400
00:18:59,470 --> 00:19:01,365
Så jeg har tænkt mig at sige næste
kommer til at få listen.

401
00:19:01,365 --> 00:19:05,150
>> Og det virker bare godt ud.

402
00:19:05,150 --> 00:19:06,500
Det er nul.

403
00:19:06,500 --> 00:19:10,620
Og så jeg siger, den nye node næste
område bør få, hvad det er.

404
00:19:10,620 --> 00:19:12,570
Så der sætter en anden nul der.

405
00:19:12,570 --> 00:19:14,510
Og så den sidste ting
Jeg gøre er at tjekke her.

406
00:19:14,510 --> 00:19:17,870
Hvis listen ikke er lig med nul, men det
er lig med nul, så vi springer at

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

408
00:19:18,470 --> 00:19:23,520
Og så alt jeg gøre næste er listen får
pointer, som billedligt resulterer i

409
00:19:23,520 --> 00:19:25,570
et billede som dette.

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

411
00:19:26,620 --> 00:19:30,490
>> Og den, du spurgte om
specifikt er en situation som denne,

412
00:19:30,490 --> 00:19:33,190
hvor vi allerede har en en-node listen.

413
00:19:33,190 --> 00:19:36,240
Og hvis jeg går tilbage op i den oprindelige
problemformulering, det næste vi vil

414
00:19:36,240 --> 00:19:39,320
Indsæt sige er 34, bare for
skyld diskussion.

415
00:19:39,320 --> 00:19:46,210
Så jeg har tænkt mig at bare bekvemt
trække det herovre.

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

417
00:19:47,540 --> 00:19:49,310
Lad os antage jeg tjekker for null.

418
00:19:49,310 --> 00:19:51,870
>> Nu, jeg har tænkt mig at initialisere
n være 34..

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

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

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

422
00:19:57,100 --> 00:19:59,370
Lad os sørge for jeg ikke gjorde
få dette baglæns.

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

424
00:20:01,110 --> 00:20:03,070
Lad mig ordne det.

425
00:20:03,070 --> 00:20:04,410
Det er tidligere.

426
00:20:04,410 --> 00:20:05,780
Dette er næste.

427
00:20:05,780 --> 00:20:08,620
Selvom disse er ens,
lad os holde det konsekvent.

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

429
00:20:09,450 --> 00:20:11,030
Dette er næste.

430
00:20:11,030 --> 00:20:16,310
Så jeg har bare malloced min note, kontrolleret
for null, tildelt 34 i noden.

431
00:20:16,310 --> 00:20:17,570
Forrige bliver nul.

432
00:20:17,570 --> 00:20:19,480
Så det giver mig det.

433
00:20:19,480 --> 00:20:21,010
Næste får 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 det samme nu som at tegne dette
pil, således at de peger på en

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

437
00:20:27,940 --> 00:20:30,400
Og så er jeg kontrollere, hvis liste
er ikke lig med nul.

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

439
00:20:31,740 --> 00:20:35,580
Så jeg har tænkt mig at gøre listen
tidligere får pointer.

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

441
00:20:39,700 --> 00:20:44,300
Så det har den virkning at sætte
en grafisk pil her.

442
00:20:44,300 --> 00:20:46,930
Og der er ved at blive lidt
bølget, linjerne.

443
00:20:46,930 --> 00:20:50,780
Og så, endelig, jeg opdatere
liste til at pege på pointer.

444
00:20:50,780 --> 00:20:55,560
Så nu dette peger på denne fyr.

445
00:20:55,560 --> 00:20:57,170
Og nu, lad os gøre en hurtig
tilregnelighed check.

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

447
00:20:59,470 --> 00:21:02,850
Det første knudepunkt er faktisk 34, fordi
Jeg følger denne pil.

448
00:21:02,850 --> 00:21:05,210
Og det er korrekt, fordi jeg ønsker at
indsætte i begyndelsen af ​​listen

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

450
00:21:06,070 --> 00:21:08,860
Hans næste felt fører mig til denne fyr.

451
00:21:08,860 --> 00:21:10,710
Hvis jeg holde ud, jeg ramte næste er nul.

452
00:21:10,710 --> 00:21:11,760
Så der er ikke mere på listen.

453
00:21:11,760 --> 00:21:14,460
Hvis jeg ramte tidligere, får jeg
tilbage, hvor jeg forventer.

454
00:21:14,460 --> 00:21:16,435
>> Så der er stadig et par pointers,
naturligvis at manipulere.

455
00:21:16,435 --> 00:21:19,870
Men det faktum, at du fik at vide at gøre
dette i konstant tid betyder, at du kun

456
00:21:19,870 --> 00:21:22,910
har en begrænset række ting
du lov til at gøre.

457
00:21:22,910 --> 00:21:24,290
Og hvad er det nummer?

458
00:21:24,290 --> 00:21:25,185
Det kunne være et skridt.

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

460
00:21:25,700 --> 00:21:26,820
Det kunne være 1.000 trin.

461
00:21:26,820 --> 00:21:30,500
Men det er begrænset, hvilket betyder, at du ikke kan
have nogen form for looping foregår

462
00:21:30,500 --> 00:21:32,010
her nogen rekursion ingen sløjfer.

463
00:21:32,010 --> 00:21:37,390
Det er bare nødt til at være hårdt kodede linjer
kode som vi har i denne prøve.

464
00:21:37,390 --> 00:21:42,330
>> Så det næste problem 12 bedt os om at
afslutte gennemførelsen af ​​remove

465
00:21:42,330 --> 00:21:46,740
under en sådan måde, at det fjerner
n fra listen i lineær tid.

466
00:21:46,740 --> 00:21:48,740
Så du har en lidt mere
vrikke værelse nu.

467
00:21:48,740 --> 00:21:52,380
Du kan antage, at n, hvis nuværende
på listen, vil være til stede

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

469
00:21:53,340 --> 00:21:56,770
Og det er også ment som en quiz-baserede
forenklende antagelse, så

470
00:21:56,770 --> 00:21:59,780
at hvis du finder det nummer 50 et eller andet sted
på listen, behøver du ikke også

471
00:21:59,780 --> 00:22:02,890
at bekymre sig om fortsat at
gentage, på udkig efter alle mulige

472
00:22:02,890 --> 00:22:06,990
kopi af 50, der bare ville uddelegere
ind i nogle minutia i begrænset tid.

473
00:22:06,990 --> 00:22:10,460
>> Så med remove, dette var absolut
mere udfordrende og mere

474
00:22:10,460 --> 00:22:11,640
kode til at skrive.

475
00:22:11,640 --> 00:22:14,990
Men ved første øjekast, helt ærligt, det kan
ser overvældende og som noget

476
00:22:14,990 --> 00:22:17,060
der er ingen måde du kunne have
komme med på en quiz.

477
00:22:17,060 --> 00:22:22,450
Men hvis vi fokuserer på de enkelte trin,
Forhåbentlig vil det pludselig

478
00:22:22,450 --> 00:22:26,060
strejke dig, at hver af disse individuelle
skridt en åbenbar mening

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

480
00:22:27,080 --> 00:22:28,200
Så lad os tage et kig.

481
00:22:28,200 --> 00:22:32,570
>> Så det første, vi initialisere pointer
at være liste selv.

482
00:22:32,570 --> 00:22:36,040
Fordi jeg vil lineær tid, at midler
Jeg har tænkt mig at have nogle loop.

483
00:22:36,040 --> 00:22:39,730
Og en fælles måde at gentage over den
knudepunkter i en liste struktur eller nogen form

484
00:22:39,730 --> 00:22:43,860
struktur iterativt er at tage
en pointer til den forreste del af data

485
00:22:43,860 --> 00:22:46,990
struktur og så bare begynde at opdatere
det og gå din vej

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

487
00:22:48,650 --> 00:22:50,040
Så jeg har tænkt mig at gøre netop dette.

488
00:22:50,040 --> 00:22:54,260
>> Mens pointer, min midlertidig variabel,
er ikke lig med nul, lad os

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

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

491
00:22:56,910 --> 00:23:01,740
Er n felt i knude Jeg er i øjeblikket
ser på lig med

492
00:23:01,740 --> 00:23:03,380
nummer jeg leder efter?

493
00:23:03,380 --> 00:23:05,410
Og hvis ja, lad os gøre noget.

494
00:23:05,410 --> 00:23:10,020
Nu bemærke dette hvis betingelse
omgiver hele

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

496
00:23:11,520 --> 00:23:14,610
Det er det eneste, jeg bekymrer sig om -
finde en pågældende nummer.

497
00:23:14,610 --> 00:23:18,010
Så der er ingen andre steder, hvilket forenkler
tingene begrebsmæssigt en lille smule.

498
00:23:18,010 --> 00:23:22,040
>> Men nu, indså jeg, og du har måske
kun realiseres dette efter at have tænkt

499
00:23:22,040 --> 00:23:24,720
det gennem en bit, der er
faktisk to sager her.

500
00:23:24,720 --> 00:23:28,060
Er, hvor knuden er i
toppen af ​​listen, der er en

501
00:23:28,060 --> 00:23:31,040
lidt irriterende, fordi det er en
særtilfælde, fordi du er nødt til at beskæftige sig

502
00:23:31,040 --> 00:23:33,340
med denne ting, som
er den eneste anomali.

503
00:23:33,340 --> 00:23:35,720
Alle andre steder på listen,
det er det samme.

504
00:23:35,720 --> 00:23:38,050
Der er en tidligere node og en næste
node forudgående knudepunkt, næste knudepunkt.

505
00:23:38,050 --> 00:23:40,940
Men denne fyr er en lidt speciel
hvis han er i begyndelsen.

506
00:23:40,940 --> 00:23:48,710
>> Så hvis markøren svarer til listen
selv, så hvis jeg er i begyndelsen af

507
00:23:48,710 --> 00:23:53,960
listen, og jeg har fundet n, jeg har brug for
til at gøre et par ting.

508
00:23:53,960 --> 00:23:59,230
En, jeg nødt til at ændre listen til
peger på det næste felt 50.

509
00:23:59,230 --> 00:24:01,270
Så formoder, at jeg forsøger
at fjerne 34.

510
00:24:01,270 --> 00:24:03,560
Så denne fyr kom til at gå
væk i bare et øjeblik.

511
00:24:03,560 --> 00:24:07,210
>> Så jeg har tænkt mig at sige, liste
bliver pointer næste.

512
00:24:07,210 --> 00:24:08,570
Nå, det er pointer.

513
00:24:08,570 --> 00:24:10,360
Næste peger herovre.

514
00:24:10,360 --> 00:24:17,470
Så dette er ved at ændre denne pil til højre
nu til at pege på denne fyr her.

515
00:24:17,470 --> 00:24:19,580
Husk nu, at vi har
en midlertidig variabel.

516
00:24:19,580 --> 00:24:23,520
Så har vi ikke forældreløse nogen noder,
fordi jeg har også denne fyr i min

517
00:24:23,520 --> 00:24:25,010
implementering af fjerne.

518
00:24:25,010 --> 00:24:29,600
Så nu, hvis listen i sig selv ikke er nul,
Jeg skal lave en lille ting.

519
00:24:29,600 --> 00:24:32,690
>> Jeg har brug for nu sørge for, at denne pil,
som tidligere peger

520
00:24:32,690 --> 00:24:36,830
50-34, har dette at gå væk,
fordi hvis jeg forsøger at slippe

521
00:24:36,830 --> 00:24:41,910
34, 50 havde bedre ikke opretholde nogen
slags tilbage henvisning til det som

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

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

524
00:24:44,820 --> 00:24:46,520
Så jeg er færdig.

525
00:24:46,520 --> 00:24:48,040
Denne sag er faktisk temmelig nemt.

526
00:24:48,040 --> 00:24:51,010
Hugge hovedet af listen
er relativt ligetil.

527
00:24:51,010 --> 00:24:52,980
>> Desværre er der denne
irriterende ellers blok.

528
00:24:52,980 --> 00:24:56,170
Så nu er jeg nødt til at overveje sagen
hvor der er noget i midten.

529
00:24:56,170 --> 00:24:59,880
Men det er ikke alt for forfærdeligt, undtagen
for syntaks som dette.

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

531
00:25:03,080 --> 00:25:08,160
Og denne linje her siger, start-
uanset på hvilket node du er på.

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

533
00:25:11,210 --> 00:25:18,550
Gå til forudgående knudepunkt næste felt
og fremhæver dette ved markøren.

534
00:25:18,550 --> 00:25:20,390
>> Lad os gøre det billedligt.

535
00:25:20,390 --> 00:25:21,640
Det var ved at blive kompliceret.

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

537
00:25:30,480 --> 00:25:37,990
Så hvis jeg har en tidligere marker her -
lad os gøre det - næste områder her.

538
00:25:37,990 --> 00:25:41,200
Jeg har tænkt mig at forenkle mine pejlemærker snarere
end tegne en hel masse

539
00:25:41,200 --> 00:25:45,710
tingene frem og tilbage på kryds og tværs
hinanden.

540
00:25:45,710 --> 00:25:50,870
Og nu, lad os bare sige, det er 1, 2,
3 af hensyn til diskussion, selv

541
00:25:50,870 --> 00:25:53,410
selv om der ikke line op med
det pågældende problem.

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

543
00:25:55,900 --> 00:25:59,300
Jeg forsøger at fjerne to i dette
bestemt version af historien.

544
00:25:59,300 --> 00:26:01,960
Så jeg har opdateret pointer til
pege på denne fyr.

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

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

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

548
00:26:07,170 --> 00:26:09,200
Og han peger her uanset hvad.

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

550
00:26:10,800 --> 00:26:13,850
>> Så hvis pointer peger her, er jeg
kommer til at følge, tilsyneladende den

551
00:26:13,850 --> 00:26:17,110
tidligere pointer, der sætter mig ved 1.

552
00:26:17,110 --> 00:26:22,290
Jeg derefter vil sige, at den næste
område, hvilket bringer mig over til denne

553
00:26:22,290 --> 00:26:25,410
ramme, vil
lige pointer næste.

554
00:26:25,410 --> 00:26:28,400
Så hvis dette pointer, det er næste.

555
00:26:28,400 --> 00:26:31,840
Det betyder, at denne pil behov
at pege på denne fyr.

556
00:26:31,840 --> 00:26:35,140
>> Så hvad der linje kode har netop
gjort, er en lille smule af dette.

557
00:26:35,140 --> 00:26:37,500
Og nu, dette er at ligne en
skridt i den rigtige retning.

558
00:26:37,500 --> 00:26:41,390
Vi hovedsagelig ønsker at klippe 2 ud
i midten af ​​1 og 3.

559
00:26:41,390 --> 00:26:44,400
Så det giver mening, at vi ønsker at
rute denne pointer omkring det.

560
00:26:44,400 --> 00:26:50,400
Så denne næste linje er at kontrollere, hvis pointer
næste ikke er nul, er der

561
00:26:50,400 --> 00:26:54,200
faktisk en til højre for 2
det betyder at vi også nødt til at gøre

562
00:26:54,200 --> 00:26:55,850
lidt snip her.

563
00:26:55,850 --> 00:27:00,590
>> Så jeg nu nødt til at følge denne pointer
og ajourføring af den tidligere markøren på

564
00:27:00,590 --> 00:27:05,410
denne fyr til at gøre en lille smule af en
omgå her pointen her.

565
00:27:05,410 --> 00:27:07,100
Og nu, visuelt er det rart.

566
00:27:07,100 --> 00:27:11,930
Det er lidt rodet i, at der er
ingen peger på 2 længere.

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

568
00:27:13,600 --> 00:27:14,980
Og 2 peger til højre.

569
00:27:14,980 --> 00:27:17,480
Men han kan gøre, hvad han vil, fordi
han er ved at blive befriet.

570
00:27:17,480 --> 00:27:19,480
Og det er ligegyldigt, hvad
disse værdier er længere.

571
00:27:19,480 --> 00:27:23,040
>> Hvad der er vigtigt er, at de resterende
fyre routing over

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

573
00:27:24,280 --> 00:27:25,810
Og ja, det er hvad vi skal gøre næste.

574
00:27:25,810 --> 00:27:29,360
Vi fri pointer, hvilket betyder, at vi fortæller
operativsystem, er du velkommen

575
00:27:29,360 --> 00:27:30,906
at kræve dette.

576
00:27:30,906 --> 00:27:34,900
Og så endelig, vi vender tilbage.

577
00:27:34,900 --> 00:27:37,220
Else implicit, hvis vi
er ikke vendt tilbage endnu,

578
00:27:37,220 --> 00:27:38,290
vi har fået til at holde udkig.

579
00:27:38,290 --> 00:27:41,485
Så pointer lig pointer næste bare
betyder flytte denne fyr her.

580
00:27:41,485 --> 00:27:42,600
Flyt denne fyr her.

581
00:27:42,600 --> 00:27:45,400
Flyt denne fyr her, hvis i virkeligheden,
vi ikke finde nummeret

582
00:27:45,400 --> 00:27:46,960
vi leder efter endnu.

583
00:27:46,960 --> 00:27:49,630
>> Så ærligt, det ser helt
overvældende, tror jeg, i første omgang

584
00:27:49,630 --> 00:27:52,180
blik, især hvis du kæmpede
med dette i løbet af quizzen så se

585
00:27:52,180 --> 00:27:52,850
noget som dette.

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

587
00:27:55,050 --> 00:27:57,080
Tja, der er ingen måde, jeg kunne have
komme op med, at der på quizzen.

588
00:27:57,080 --> 00:28:00,470
Men jeg vil hævde, kan du, hvis du bryder
det ned i disse individuelle

589
00:28:00,470 --> 00:28:04,400
sager og bare gå igennem det
omhyggeligt, omend ganske vist under

590
00:28:04,400 --> 00:28:06,300
stressende omstændigheder.

591
00:28:06,300 --> 00:28:09,470
>> Heldigvis billedet lavet
alt gladere.

592
00:28:09,470 --> 00:28:11,050
Du kan tegne dette i
en række forskellige måder.

593
00:28:11,050 --> 00:28:12,760
Du behøver ikke at gøre det kryds og tværs
ting her.

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

595
00:28:14,520 --> 00:28:18,790
Men kernen i dette problem, i
Generelt var at indse, at

596
00:28:18,790 --> 00:28:22,060
billede i sidste ende skal se lidt
noget som dette, fordi

597
00:28:22,060 --> 00:28:25,030
konstant tid indebar, at du holder
jamming og jamming og tilstopper

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

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

600
00:28:31,960 --> 00:28:34,565
Sandsynligvis den mest udfordrende af
helt sikkert den kodning spørgsmål.

601
00:28:34,565 --> 00:28:37,690
>> PUBLIKUM: Så er listen ligner
hovedet i tidligere eksempler.

602
00:28:37,690 --> 00:28:39,640
>> DAVID J. MALAN: Præcis, præcis.

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

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

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 den, hvor du
skulle skrive stykket.

608
00:28:52,020 --> 00:28:56,060
Nogle mennesker skrev essays
for dette spørgsmål.

609
00:28:56,060 --> 00:29:00,230
Men du skal bare bruge disse seks betingelser
at beskrive, hvad der sker, når

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

611
00:29:02,440 --> 00:29:07,930
Så jeg vil bare snakke igennem processen
hjælp af alle disse vilkår.

612
00:29:07,930 --> 00:29:11,290
Så i vores browser, vi skriver facebook.com
og tryk på Enter.

613
00:29:11,290 --> 00:29:17,280
Så vores browser kommer til at konstruere en
HTTP anmode om, at det kommer til at sende

614
00:29:17,280 --> 00:29:22,220
gennem nogle proces til Facebook for
Facebook til at reagere på os med den

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

616
00:29:24,450 --> 00:29:28,800
>> Så hvad er den proces,
hvilken HTTP-anmodning

617
00:29:28,800 --> 00:29:30,730
rent faktisk får på Facebook?

618
00:29:30,730 --> 00:29:32,790
Så det første, vi har brug for at oversætte
Facebook.com.

619
00:29:32,790 --> 00:29:38,780
Så bare givet navnet Facebook.com,
hvor faktisk gør det HTTP-anmodning

620
00:29:38,780 --> 00:29:39,940
nødt til at gå?

621
00:29:39,940 --> 00:29:44,120
Så vi er nødt til at oversætte Facebook.com
til en IP-adresse, som entydigt

622
00:29:44,120 --> 00:29:47,620
identificerer, hvad maskine vi faktisk
ønsker at sende denne anmodning.

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
Noget der er forbundet til internettet
har en IP-adresse.

625
00:29:52,240 --> 00:29:59,030
>> Så DNS, Domain Name System, der er
hvad der kommer til at håndtere oversættelsen

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

627
00:30:03,750 --> 00:30:08,075
Så vi kontakte DNS-servere og
sige, hvad der er facebook.com?

628
00:30:08,075 --> 00:30:16,560
Den siger, åh, det er IP-adresse 190,212
noget, noget, noget.

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

630
00:30:16,900 --> 00:30:18,850
Nu ved jeg, hvad maskine
Jeg vil kontakte.

631
00:30:18,850 --> 00:30:22,360
>> Så du sende din HTTP-anmodning
over til denne maskine.

632
00:30:22,360 --> 00:30:24,140
Så hvordan det kommer til den maskine?

633
00:30:24,140 --> 00:30:27,200
Nå, anmodningen går fra
router til router hoppende.

634
00:30:27,200 --> 00:30:32,630
Husk eksempel i klassen, hvor
så vi faktisk den rute, som den

635
00:30:32,630 --> 00:30:35,340
pakker tog da vi forsøgte
at kommunikere.

636
00:30:35,340 --> 00:30:38,460
Vi oplevede det hoppe over Atlanten
Ocean på et tidspunkt eller hvad.

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

638
00:30:42,820 --> 00:30:46,520
Så dette er nu på din computer.

639
00:30:46,520 --> 00:30:49,970
Du kan have flere ting i øjeblikket
kommunikere med internettet.

640
00:30:49,970 --> 00:30:53,730
Så jeg kan køre, siger, Skype.

641
00:30:53,730 --> 00:30:55,670
Jeg kunne have en web browser åben.

642
00:30:55,670 --> 00:30:59,010
Jeg kunne have noget at
torrenting filer.

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

644
00:31:00,880 --> 00:31:02,600
internet eller anden måde.

645
00:31:02,600 --> 00:31:08,070
>> Så når din computer modtager nogle data
fra internettet, hvordan gør det

646
00:31:08,070 --> 00:31:10,130
vide, hvad ansøgning faktisk
ønsker, at de data?

647
00:31:10,130 --> 00:31:12,610
Hvordan virker det, om denne særlige
data beregnet til

648
00:31:12,610 --> 00:31:16,070
torrenting ansøgning i modsætning
til web browser?

649
00:31:16,070 --> 00:31:20,980
Så dette er formålet med havne i det
alle disse programmer har

650
00:31:20,980 --> 00:31:22,720
hævdede en port på din computer.

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

652
00:31:27,580 --> 00:31:32,240
Og din torrenting program siger,
Jeg lytter på port 3000.

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

654
00:31:34,770 --> 00:31:41,950
>> Så når du får nogle data, der hører
til et af disse programmer, de data,

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

656
00:31:45,510 --> 00:31:47,950
Så det siger, åh, jeg tilhører
til port 1000.

657
00:31:47,950 --> 00:31:50,950
Jeg ved så er jeg nødt til at sende denne
sammen til min browser.

658
00:31:50,950 --> 00:31:56,440
Så grunden til det er relevant her
er, at web-servere har tendens til at

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, jeg er
kommunikation med nogle maskinen.

661
00:32:02,420 --> 00:32:06,390
Men jeg er nødt til at sige, hvilken havn der
maskine, jeg ønsker at kommunikere med.

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

663
00:32:09,160 --> 00:32:14,010
>> Hvis de ville, kunne de sætte det
op, så det lister som på port 7000.

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

665
00:32:19,090 --> 00:32:24,600
sende anmodningen til port 7000
af Facebooks webserver.

666
00:32:24,600 --> 00:32:26,820
>> DAVID J. MALAN: Og i dette tilfælde, selv
selvom vi ikke kræve, at folk

667
00:32:26,820 --> 00:32:30,000
nævner dette, i dette tilfælde, hvad port
ville anmodningen faktisk gå til?

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

669
00:32:36,630 --> 00:32:37,880
Prøv igen.

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

671
00:32:42,810 --> 00:32:44,300
Præcis.

672
00:32:44,300 --> 00:32:47,960
Ikke på udkig efter det, men en underfundighed
det er der ingen det sidste.

673
00:32:47,960 --> 00:32:51,770
>> ROB BOWDEN: Så HTTPS, da det er
lytter specifikt til

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

675
00:32:55,180 --> 00:32:57,680
>> Publikum: og e-mails er 25, ikke?

676
00:32:57,680 --> 00:33:00,670
>> DAVID J. MALAN: Udgående
emails, 25, jep.

677
00:33:00,670 --> 00:33:03,760
>> ROB BOWDEN: Jeg ved ikke engang kender de fleste af
den - alle de lavere tendens til at være

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

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

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

681
00:33:13,450 --> 00:33:18,820
>> ROB BOWDEN: Fordi i en IP-adresse,
Der er fire grupperinger af cifre.

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 fælles
lokale netværk IP-adresse.

684
00:33:28,060 --> 00:33:30,840
Bemærk alle af dem er mindre end 255..

685
00:33:30,840 --> 00:33:33,570
Så da jeg startede med 300, at
ikke kunne muligvis have

686
00:33:33,570 --> 00:33:35,210
været et af numrene.

687
00:33:35,210 --> 00:33:38,170
>> DAVID J. MALAN: Men det fjollet klip
fra - var det CSI, hvor de havde en

688
00:33:38,170 --> 00:33:39,970
nummer, der 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ørgsmål vedrørende denne?

691
00:33:46,110 --> 00:33:51,710
Den næste, så fuldstændig ændring i
emne, 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 uordnet liste.

694
00:33:56,360 --> 00:33:59,550
Og vi ønsker at udskrive et punkt på listen
bare indeholder 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 løkke.

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

698
00:34:17,540 --> 00:34:22,360
Så gennem hver iteration af løkken,
Huset kommer til at tage på en af ​​de

699
00:34:22,360 --> 00:34:24,060
værdier indeni array.

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

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

702
00:34:30,370 --> 00:34:34,370
Så for hver quad som hus, er vi
lige til at printe -

703
00:34:34,370 --> 00:34:37,250
du også kunne have gentaget -

704
00:34:37,250 --> 00:34:42,199
listen element og derefter husets navn
og derefter lukke listeelement.

705
00:34:42,199 --> 00:34:45,210
De krøllede parenteser er valgfri her.

706
00:34:45,210 --> 00:34:49,480
>> Og så har vi også sagt i spørgsmålet
selv, så husk at lukke

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

708
00:34:50,770 --> 00:34:53,949
Så vi er nødt til at afslutte PHP mode
For at gøre dette.

709
00:34:53,949 --> 00:35:00,280
Eller vi kunne have gentaget den
luk uordnet liste tag.

710
00:35:00,280 --> 00:35:02,380
>> DAVID J. MALAN: Også fint her ville
have været at bruge en gammel skole for

711
00:35:02,380 --> 00:35:07,340
loop med en $ i = 0 0 og ved hjælp af tællinger
finde ud af længden af ​​stråle.

712
00:35:07,340 --> 00:35:09,240
Helt fint, bare
lidt 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ørligt], du ville gøre -

715
00:35:14,742 --> 00:35:16,734
Jeg glemmer, hvad løkken [uhørligt] er.

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

717
00:35:21,380 --> 00:35:21,850
>> DAVID J. MALAN: Præcis.

718
00:35:21,850 --> 00:35:23,100
Ja, præcis.

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

720
00:35:26,650 --> 00:35:27,900
>> ROB BOWDEN: Noget andet?

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

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

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

724
00:35:32,300 --> 00:35:38,290
Så der var bundter af svarene
muligt for hver af disse.

725
00:35:38,290 --> 00:35:40,510
Vi var egentlig bare på udkig efter
noget overbevisende for en upside og

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

727
00:35:41,100 --> 00:35:44,830
Og nummer 16 spurgte, validering brugere '
input 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å hvad er en upside på
laver client-side?

730
00:35:49,450 --> 00:35:53,780
>> Tja, en af ​​de ting, vi har foreslået, er
at du reducerer ventetid, fordi du

731
00:35:53,780 --> 00:35:56,750
behøver ikke at bekymre kontakte
server, hvilket kan tage et par

732
00:35:56,750 --> 00:36:00,390
millisekunder eller endda et par sekunder
ved at undgå det, og lige

733
00:36:00,390 --> 00:36:04,670
validere brugernes input client-side ved
udløser en on-indsende handler og

734
00:36:04,670 --> 00:36:06,650
bare kontrol, de skriver
noget i for navn?

735
00:36:06,650 --> 00:36:08,080
Har de skriver noget
i til email-adresse?

736
00:36:08,080 --> 00:36:10,950
Har de vælger et kollegieværelse fra
drop-down menu?

737
00:36:10,950 --> 00:36:14,360
>> Du kan give dem øjeblikkelig tilbagemelding
hjælp gigahertz computer

738
00:36:14,360 --> 00:36:16,770
eller hvad de har, det er
faktisk på deres skrivebord.

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

740
00:36:19,310 --> 00:36:24,460
Men bagsiden af ​​medaljen at client-side
validering, hvis du gør det uden også

741
00:36:24,460 --> 00:36:29,860
laver validering server-side er, at
mest nogen kommer ud af CS50 kender

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

743
00:36:33,980 --> 00:36:37,030
Helt ærligt, i de fleste enhver browser, kan du
klikke rundt i indstillingerne og bare

744
00:36:37,030 --> 00:36:40,110
slukke JavaScript, der ville,
derfor deaktivere enhver form for

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

746
00:36:41,080 --> 00:36:44,460
>> Men du måske også huske, at selv jeg
gjorde nogle mystiske ting i klassen ved hjælp af

747
00:36:44,460 --> 00:36:47,790
telnet og faktisk foregiver at
være en browser ved at sende get

748
00:36:47,790 --> 00:36:49,240
anmodninger til en server.

749
00:36:49,240 --> 00:36:51,030
Og det er bestemt ikke
ved hjælp af en JavaScript.

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

751
00:36:53,290 --> 00:36:57,410
Så virkelig, enhver programmør indenfor nok
komfort med internettet og HTTP

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

753
00:37:01,690 --> 00:37:05,470
Og hvis din server ikke også kontrol,
de gav mig et navn, er

754
00:37:05,470 --> 00:37:08,930
dette faktisk en gyldig e-mail-adresse, gjorde
de vælger et kollegieværelse, kan du ende

755
00:37:08,930 --> 00:37:12,800
op indsætte falske eller bare blank data
ind i din database, som sandsynligvis

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

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

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

759
00:37:19,890 --> 00:37:21,810
Men det betyder dobbelt så meget arbejde.

760
00:37:21,810 --> 00:37:25,970
Selv om der eksisterer forskellige
biblioteker, JavaScript-biblioteker for

761
00:37:25,970 --> 00:37:28,830
eksempel, at gøre det meget,
meget mindre af en hovedpine.

762
00:37:28,830 --> 00:37:31,940
Og du kan genbruge noget af koden
server-side, client-side.

763
00:37:31,940 --> 00:37:35,980
Men indser, at det typisk
ekstra arbejde.

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

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

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

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

768
00:37:39,680 --> 00:37:43,105
Det er altid sværere
dem til at træffe afgørelse i sagen.

769
00:37:43,105 --> 00:37:44,480
>> ROB BOWDEN Det ville
er blevet godkendt.

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

771
00:37:44,810 --> 00:37:45,810
>> ROB BOWDEN: Jeg har oprettet dette problem.

772
00:37:45,810 --> 00:37:46,735
Det ville have været accepteret.

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

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

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

776
00:37:51,770 --> 00:37:53,630
godt, hvad vi leder efter, er
noget som du ikke behøver at

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

778
00:37:55,270 --> 00:37:58,355
Vi acceptere ikke bare hurtigere.

779
00:37:58,355 --> 00:38:00,080
>> PUBLIKUM: Hvad
ikke genindlæse siden?

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

781
00:38:00,430 --> 00:38:03,000
Det var et accepteret svar.

782
00:38:03,000 --> 00:38:06,300
>> DAVID J. MALAN: Alt hvor vi følte
det var mere sandsynligt end ikke sandsynligt

783
00:38:06,300 --> 00:38:09,780
at du vidste, hvad du var
siger, der er en hård

784
00:38:09,780 --> 00:38:13,500
line til at trække nogle gange.

785
00:38:13,500 --> 00:38:16,000
Ved hjælp af en sammenkædet liste i stedet
i et array til at opretholde en

786
00:38:16,000 --> 00:38:17,590
sorteret liste af heltal.

787
00:38:17,590 --> 00:38:21,000
Så en upside vi ofte citerer med tilknytning
lister, der motiverede deres helhed

788
00:38:21,000 --> 00:38:22,370
introduktion var du får dynamik.

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 behøver ikke at hoppe igennem tøndebånd
til rent faktisk at skabe mere hukommelse

792
00:38:27,370 --> 00:38:28,140
med et array.

793
00:38:28,140 --> 00:38:30,310
Eller du behøver ikke at bare
sige, undskyld, bruger.

794
00:38:30,310 --> 00:38:31,410
Matrixen er fyldt.

795
00:38:31,410 --> 00:38:35,850
Så dynamisk vækst på listen.

796
00:38:35,850 --> 00:38:37,210
En ulempe dog af hægtede 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øgning på linket liste er lineær
i stedet for hvad du logger ind

800
00:38:45,800 --> 00:38:46,360
>> DAVID J. MALAN: Præcis.

801
00:38:46,360 --> 00:38:50,160
Søgning på en linket liste er lineær,
selv om det er sorteret, fordi du kan

802
00:38:50,160 --> 00:38:53,170
kun følge disse brødkrummer, disse
pegepinde, fra starten af ​​listen

803
00:38:53,170 --> 00:38:53,570
til enden.

804
00:38:53,570 --> 00:38:57,970
Du kan ikke udnytte random access og
således binær søgning, selv om det er

805
00:38:57,970 --> 00:39:00,740
sorteret, som du kunne
gøre med et array.

806
00:39:00,740 --> 00:39:02,390
Og der er også en anden pris.

807
00:39:02,390 --> 00:39:02,966
Ja.

808
00:39:02,966 --> 00:39:03,800
>> PUBLIKUM: Hukommelse ineffektiv?

809
00:39:03,800 --> 00:39:04,130
>> DAVID J. MALAN: Ja.

810
00:39:04,130 --> 00:39:06,940
Tja, jeg ville ikke nødvendigvis
sige ineffektive.

811
00:39:06,940 --> 00:39:10,110
Men det koster dig mere hukommelse,
fordi du har brug for 32 bit for hver

812
00:39:10,110 --> 00:39:13,400
node for yderligere pointer, på
mindste for en enkelt bundet listen.

813
00:39:13,400 --> 00:39:16,660
Nu, hvis du kun opbevare heltal og
du tilføjer den pointer, der er

814
00:39:16,660 --> 00:39:17,830
faktisk slags ikke-triviel.

815
00:39:17,830 --> 00:39:19,340
Det er en fordobling af mængden af ​​hukommelse.

816
00:39:19,340 --> 00:39:22,330
Men i virkeligheden, hvis du opbevarer et
hægtet liste af structs, der kan have

817
00:39:22,330 --> 00:39:25,540
8 byte, 16 bytes, endnu mere
end det, det er måske mindre

818
00:39:25,540 --> 00:39:26,500
af en marginal omkostning.

819
00:39:26,500 --> 00:39:28,320
Men det er en pris alligevel.

820
00:39:28,320 --> 00:39:31,880
Så enten af ​​dem ville have
været fint som ulemper.

821
00:39:31,880 --> 00:39:32,110
>> 18..

822
00:39:32,110 --> 00:39:36,100
Brug af PHP i stedet for C at skrive
en kommando-linje-program.

823
00:39:36,100 --> 00:39:41,890
Så her er det ofte hurtigere at bruge en
sprog som PHP eller Ruby eller Python.

824
00:39:41,890 --> 00:39:43,700
Du skal bare hurtigt at åbne
en tekst editor.

825
00:39:43,700 --> 00:39:45,900
Du har mange flere funktioner
til rådighed for dig.

826
00:39:45,900 --> 00:39:49,325
PHP har køkkenvask funktioner,
hvorimod i C, du

827
00:39:49,325 --> 00:39:50,420
har meget, meget lidt.

828
00:39:50,420 --> 00:39:53,820
Faktisk fyre kender den hårde måde
at du ikke har hash-tabeller.

829
00:39:53,820 --> 00:39:55,000
Du har ikke knyttet lister.

830
00:39:55,000 --> 00:39:57,470
Hvis du vil have dem, skal du
gennemføre dem selv.

831
00:39:57,470 --> 00:40:00,950
>> Så en upside på PHP eller virkelig nogen
fortolket sprog er den hurtighed

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, vi så dette, da jeg
hurtigt pisket op en misspeller

834
00:40:06,660 --> 00:40:11,780
implementering i foredrag ved hjælp af PHP, er
at ved hjælp af et fortolket sprog

835
00:40:11,780 --> 00:40:13,570
er normalt langsommere.

836
00:40:13,570 --> 00:40:18,420
Og vi så, at beviseligt med en
stigning i tid fra 0,3 sekunder til 3

837
00:40:18,420 --> 00:40:24,440
sekunder, på grund af den fortolkning,
der rent faktisk sker.

838
00:40:24,440 --> 00:40:27,060
>> Anden opadrettede var, at du
ikke behøver at kompilere.

839
00:40:27,060 --> 00:40:30,130
Så det også fremskynder udvikling
øvrigt, fordi du ikke har

840
00:40:30,130 --> 00:40:31,360
to trin til at køre et program.

841
00:40:31,360 --> 00:40:32,140
Du skal bare have en.

842
00:40:32,140 --> 00:40:35,260
Og så det er temmelig
overbevisende som godt.

843
00:40:35,260 --> 00:40:38,450
Ved hjælp af en SQL-database i stedet for
en CSV-fil til at gemme data.

844
00:40:38,450 --> 00:40:40,230
Så SQL database bruges til pset7.

845
00:40:40,230 --> 00:40:42,060
CSV-filer, du ikke bruger meget.

846
00:40:42,060 --> 00:40:45,960
Men du har brugt det indirekte i pset7 som
godt ved at tale med Yahoo Finance.

847
00:40:45,960 --> 00:40:49,330
>> Men CSV er ligesom en Excel-fil, men
super enkel, hvor søjlerne er

848
00:40:49,330 --> 00:40:54,010
bare demarked af kommaer inde
i en ellers tekstfil.

849
00:40:54,010 --> 00:40:56,740
Og ved hjælp af en SQL-database er
lidt mere overbevisende.

850
00:40:56,740 --> 00:41:00,060
Det er en upside, fordi du får tingene
ligesom vælge og indsætte og slette.

851
00:41:00,060 --> 00:41:03,790
Og du får, formentlig, indekser,
MySQL og andre databaser, som

852
00:41:03,790 --> 00:41:07,510
Oracle, bygge for dig i hukommelsen, hvilket
betyder, at din vælger, er sandsynligvis ikke

853
00:41:07,510 --> 00:41:09,000
vil være lineær top til bund.

854
00:41:09,000 --> 00:41:11,300
Det er faktisk kommer til at være noget
ligesom binær søgning eller noget

855
00:41:11,300 --> 00:41:12,520
samme ånd.

856
00:41:12,520 --> 00:41:13,930
Så de er generelt hurtigere.

857
00:41:13,930 --> 00:41:16,040
>> Men en ulempe er, at
det er bare mere arbejde.

858
00:41:16,040 --> 00:41:16,730
Det er mere indsats.

859
00:41:16,730 --> 00:41:18,140
Du er nødt til at forstå databaser.

860
00:41:18,140 --> 00:41:18,940
Du er nødt til at sætte det op.

861
00:41:18,940 --> 00:41:20,840
Du har brug for en server til at køre
denne database den.

862
00:41:20,840 --> 00:41:22,750
Du er nødt til at forstå
hvordan den konfigureres.

863
00:41:22,750 --> 00:41:24,930
Så disse er blot disse
former for kompromisser.

864
00:41:24,930 --> 00:41:27,860
Mens en CSV-fil, kan du
oprette den med gedit.

865
00:41:27,860 --> 00:41:28,770
Og du er god til at gå.

866
00:41:28,770 --> 00:41:31,550
Der er ingen kompleksitet ud over dette.

867
00:41:31,550 --> 00:41:34,870
>> Ved hjælp af en trie stedet for en hash tabel
med separat kæde til at gemme et

868
00:41:34,870 --> 00:41:37,490
ordbog af ord minder
af pset5.

869
00:41:37,490 --> 00:41:42,480
Så en forsøger upside i teorien
i det mindste, er hvad?

870
00:41:42,480 --> 00:41:46,380
Konstant tid, i hvert fald hvis du er
hashing på hver af de enkelte

871
00:41:46,380 --> 00:41:48,990
bogstaver i et ord, ligesom du
kunne få for pset5.

872
00:41:48,990 --> 00:41:52,720
Det kunne være fem hashes, seks
hashes hvis der er fem eller seks

873
00:41:52,720 --> 00:41:53,900
bogstaver i ordet.

874
00:41:53,900 --> 00:41:54,580
Og det er temmelig godt.

875
00:41:54,580 --> 00:41:56,910
Og hvis der er en øvre grænse for, hvordan
længe dine ord kan være, det er

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 tabel med separat
kæde, problemet er der med det

878
00:42:05,180 --> 00:42:09,070
type datastruktur er, at
effektiviteten af ​​dine algoritmer normalt

879
00:42:09,070 --> 00:42:12,700
afhænger af antallet af ting
allerede i datastrukturen.

880
00:42:12,700 --> 00:42:15,660
Og det er helt sikkert tilfældet med
kæder, hvorved flere ting du sætter

881
00:42:15,660 --> 00:42:18,800
i en hash tabel, jo længere de
kæder gå, hvilket betyder i værste

882
00:42:18,800 --> 00:42:21,960
tilfælde, de ting, du måske være på udkig efter
er hele vejen i slutningen af ​​en

883
00:42:21,960 --> 00:42:26,000
af disse kæder, som effektivt
overdrages til noget lineært.

884
00:42:26,000 --> 00:42:29,450
>> Nu, i praksis kunne det absolut
være tilfældet, at en hash tabel med

885
00:42:29,450 --> 00:42:32,820
kæder er hurtigere end en tilsvarende
trie gennemførelse.

886
00:42:32,820 --> 00:42:35,570
Men det er af forskellige årsager, blandt
der forsøger at bruge en hel masse

887
00:42:35,570 --> 00:42:39,240
hukommelse, der kan i virkeligheden, langsom ting
ned, fordi du ikke får god

888
00:42:39,240 --> 00:42:42,410
fordele af noget, der hedder caching,
hvor ting, der er tæt på hinanden

889
00:42:42,410 --> 00:42:45,420
i hukommelsen kan tilgås
ofte hurtigere.

890
00:42:45,420 --> 00:42:48,180
Og nogle gange kan du komme op med
en rigtig god hash funktion.

891
00:42:48,180 --> 00:42:51,060
Selv hvis du er nødt til at spilde en smule
hukommelse, kan du faktisk være i stand til

892
00:42:51,060 --> 00:42:54,430
finde ting hurtigt og ikke
så slemt som lineært.

893
00:42:54,430 --> 00:42:58,410
>> Så kort sagt, var der ikke nødvendigvis
med nogen af ​​disse en eller endda to

894
00:42:58,410 --> 00:43:00,050
specifikke ting, vi ledte efter.

895
00:43:00,050 --> 00:43:03,080
Virkelig noget overbevisende
som en upside og downside

896
00:43:03,080 --> 00:43:04,800
generelt fanget vores øje.

897
00:43:04,800 --> 00:43:11,840
>> ROB BOWDEN: Så for opadrettede, vi gjorde
accepterer ikke på sin egen "hurtigere". Du

898
00:43:11,840 --> 00:43:14,540
havde at sige noget om det.

899
00:43:14,540 --> 00:43:17,910
Selv hvis du sagde teoretisk hurtigere,
vi vidste, at du slags forstået

900
00:43:17,910 --> 00:43:19,470
at det er 0 af 1.

901
00:43:19,470 --> 00:43:22,820
Og hash tabel i teorien
ikke er 0 1.

902
00:43:22,820 --> 00:43:26,550
Nævne noget om runtime
generelt fik du point.

903
00:43:26,550 --> 00:43:32,640
Men "hurtigere", de fleste løsninger på
den store bestyrelse, der blev forsøger var

904
00:43:32,640 --> 00:43:34,990
objektivt langsommere end løsninger
der var hash-tabeller.

905
00:43:34,990 --> 00:43:37,250
Så hurtigere i sig selv
er ikke sandt.

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 nok den eneste, der realiserer
det er, hvordan det er meningen at

909
00:43:46,686 --> 00:43:47,500
udtales, right?

910
00:43:47,500 --> 00:43:50,400
>> ROB BOWDEN: Jeg havde faktisk ingen idé.

911
00:43:50,400 --> 00:43:51,650
>> DAVID J. MALAN: Det gjorde
mening i mit hoved.

912
00:43:51,650 --> 00:43:53,830

913
00:43:53,830 --> 00:43:57,580
>> ROB BOWDEN: Jeg gør det ene.

914
00:43:57,580 --> 00:43:58,020
OK.

915
00:43:58,020 --> 00:44:04,243
Så dette er den ene, hvor du var nødt til at tegne
diagrammet ligner du måske

916
00:44:04,243 --> 00:44:06,040
har set på tidligere eksamener.

917
00:44:06,040 --> 00:44:12,200
Så lad os bare se på dette.

918
00:44:12,200 --> 00:44:18,170
Så fra HTML node, vi har to
børn, hovedet og kroppen.

919
00:44:18,170 --> 00:44:20,570
Så vi forgrener - hoved og krop.

920
00:44:20,570 --> 00:44:22,280
Hovedet har en titel tag.

921
00:44:22,280 --> 00:44:23,710
Så vi har en titel.

922
00:44:23,710 --> 00:44:28,450
>> Nu er den ene ting, en masse mennesker
glemte er, at disse tekst noder er

923
00:44:28,450 --> 00:44:30,430
elementer inden for dette træ.

924
00:44:30,430 --> 00:44:36,260
Så her er vi tilfældigvis til at trække dem som ovaler
at adskille dem fra disse

925
00:44:36,260 --> 00:44:37,380
typer knudepunkter.

926
00:44:37,380 --> 00:44:41,450
Men meddelelsen også her har vi top,
midten og bunden vil ende med at blive

927
00:44:41,450 --> 00:44:42,560
tekst noder.

928
00:44:42,560 --> 00:44:46,250
Så glemmer de var noget
af en almindelig fejl.

929
00:44:46,250 --> 00:44:48,770
>> Kroppen har tre børn -
disse tre divs.

930
00:44:48,770 --> 00:44:53,340
Så div, div, div og derefter teksten
node børn af disse divs.

931
00:44:53,340 --> 00:44:55,900
Det er temmelig meget det
for, at spørgsmål.

932
00:44:55,900 --> 00:44:57,860
>> DAVID J. MALAN: Og det er værd at bemærke,
selv om vi ikke dvæle ved disse

933
00:44:57,860 --> 00:45:01,040
detaljer i den tid, vi bruger på
JavaScript, at ordren gør, i

934
00:45:01,040 --> 00:45:02,290
Faktisk stof teknisk.

935
00:45:02,290 --> 00:45:06,330
Så hvis hoved kommer før kroppen i
HTML, så det skal vises på

936
00:45:06,330 --> 00:45:08,860
til venstre for kroppen i selve DOM.

937
00:45:08,860 --> 00:45:12,265
At hans er generelt bare FYI,
noget, der hedder dokument orden, hvor

938
00:45:12,265 --> 00:45:13,260
det betyder noget.

939
00:45:13,260 --> 00:45:17,470
Og hvis du var at gennemføre en parser,
et program, der læser HTML i bygning

940
00:45:17,470 --> 00:45:20,960
op i træet i hukommelsen, for at være ærlig,
det er intuitivt sandsynligvis, hvad du

941
00:45:20,960 --> 00:45:24,720
gøre alligevel - top til bund,
venstre til højre.

942
00:45:24,720 --> 00:45:26,116
>> ROB BOWDEN: Spørgsmål om det?

943
00:45:26,116 --> 00:45:29,080

944
00:45:29,080 --> 00:45:30,000
Skal jeg gøre det næste?

945
00:45:30,000 --> 00:45:32,380
>> DAVID J. MALAN: Selvfølgelig.

946
00:45:32,380 --> 00:45:33,810
>> ROB BOWDEN: OK.

947
00:45:33,810 --> 00:45:39,320
Så dette er bufferoverløb
angreb spørgsmål.

948
00:45:39,320 --> 00:45:43,740
Den vigtigste ting at genkende her er,
godt, hvordan kunne en modstander trick

949
00:45:43,740 --> 00:45:46,170
dette program til udførelse
vilkårlig kode?

950
00:45:46,170 --> 00:45:51,860
Så argv1, den første kommandolinjen
Argumentet for dette program, der kan være

951
00:45:51,860 --> 00:45:53,920
vilkårligt lang.

952
00:45:53,920 --> 00:45:59,160
Men her bruger vi memcpy til at 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 tager på navnet baren.

955
00:46:02,050 --> 00:46:08,040
>> Så vi memcpying bar
i denne buffer ca.

956
00:46:08,040 --> 00:46:09,400
Hvor mange bytes vi kopierer?

957
00:46:09,400 --> 00:46:14,040
Nå men mange bytes bar sker
bruge, længden af ​​dette argument.

958
00:46:14,040 --> 00:46:17,930
Men C er kun 12 bytes bred.

959
00:46:17,930 --> 00:46:22,280
Så hvis vi skriver en kommandolinjeargument
der er længere end 12 byte, er vi

960
00:46:22,280 --> 00:46:25,470
kommer til at løbe over dette
særlig puffer.

961
00:46:25,470 --> 00:46:31,000
Nu, hvordan kan en modstander narre
programmere i udførelse af vilkårlig kode?

962
00:46:31,000 --> 00:46:34,910
>> Så husk, at her
main kalder foo.

963
00:46:34,910 --> 00:46:37,340
Og så så de vigtigste opkald foo.

964
00:46:37,340 --> 00:46:40,408
Lad os trække dette.

965
00:46:40,408 --> 00:46:44,720

966
00:46:44,720 --> 00:46:46,990
Så vi har vores stak.

967
00:46:46,990 --> 00:46:49,090
Og vigtigste har en stakrammen
nederst.

968
00:46:49,090 --> 00:46:51,860

969
00:46:51,860 --> 00:46:53,250
På et tidspunkt, de vigtigste opkald foo.

970
00:46:53,250 --> 00:46:55,390
Nå, det samme, de vigtigste opkald foo.

971
00:46:55,390 --> 00:46:57,130
Og så foo får sin egen stak ramme.

972
00:46:57,130 --> 00:46:59,650

973
00:46:59,650 --> 00:47:02,220
>> Nu på et tidspunkt, foo
kommer til at vende tilbage.

974
00:47:02,220 --> 00:47:06,810
Og gik foo afkast, vi har brug for at vide på
hvad linje kode inde i hoved, vi

975
00:47:06,810 --> 00:47:10,610
var i orden at vide, hvor
vi bør genoptages i main.

976
00:47:10,610 --> 00:47:13,100
Vi kan kalde foo fra en hel
masse forskellige steder.

977
00:47:13,100 --> 00:47:14,620
Hvordan kan vi vide, hvor at vende tilbage?

978
00:47:14,620 --> 00:47:16,460
Nå, vi er nødt til at gemme det et eller andet sted.

979
00:47:16,460 --> 00:47:23,010
>> Så et eller andet sted lige her omkring, vi opbevarer
hvor vi bør vende tilbage til en gang

980
00:47:23,010 --> 00:47:24,070
foo afkast.

981
00:47:24,070 --> 00:47:26,350
Og dette er afsenderadressen.

982
00:47:26,350 --> 00:47:30,490
Så hvordan en modstander kan tage fordel
på dette er det faktum, at

983
00:47:30,490 --> 00:47:37,550
denne buffer C er gemt, lad os
sige, lige her er c.

984
00:47:37,550 --> 00:47:39,690
Så vi har fået 12 byte til ca.

985
00:47:39,690 --> 00:47:40,540
Dette er ca.

986
00:47:40,540 --> 00:47:43,030
Og det er foo stak ringen.

987
00:47:43,030 --> 00:47:49,970
Så hvis ondsindet bruger indtaster mere
bytes end 12 eller de indtaster en kommando

988
00:47:49,970 --> 00:47:54,570
line argument, der er længere end 12
tegn, så vi kommer til at

989
00:47:54,570 --> 00:47:57,540
overflow denne buffer.

990
00:47:57,540 --> 00:47:59,910
>> Vi kan holde ud.

991
00:47:59,910 --> 00:48:02,220
Og på et tidspunkt, går vi langt
nok, at vi starter

992
00:48:02,220 --> 00:48:05,120
overskrive denne returadresse.

993
00:48:05,120 --> 00:48:08,310
Så når vi overskrive den returadresse,
dette betyder, at når foo

994
00:48:08,310 --> 00:48:14,220
afkast, vi vender tilbage til, hvor den
ondsindet bruger fortæller det til ved

995
00:48:14,220 --> 00:48:19,490
uanset værdi den trådte, uanset hvorledes
tegn brugeren har indtastet.

996
00:48:19,490 --> 00:48:24,320
Og så hvis ondsindet bruger bliver
specielt smart, kan han have denne

997
00:48:24,320 --> 00:48:29,255
vende tilbage til et sted i printDef
funktion eller andet sted i allokere

998
00:48:29,255 --> 00:48:31,830
funktion, lige som helst vilkårlig.

999
00:48:31,830 --> 00:48:38,420
>> Men endnu mere smart er, hvad hvis han har
brugeren tilbage til lige her.

1000
00:48:38,420 --> 00:48:41,920
Og så skal du begynde at udføre
disse som linjer kode.

1001
00:48:41,920 --> 00:48:46,610
Så på dette punkt, kan brugeren indtaste
hvad han vil ind i denne region.

1002
00:48:46,610 --> 00:48:52,210
Og han har fuldstændig kontrol
over dit program.

1003
00:48:52,210 --> 00:48:53,460
Spørgsmål om det?

1004
00:48:53,460 --> 00:48:56,380

1005
00:48:56,380 --> 00:49:00,970
Det næste spørgsmål er fuldført
reimplementation af foo på en sådan måde

1006
00:49:00,970 --> 00:49:02,620
at det ikke længere er sårbar.

1007
00:49:02,620 --> 00:49:03,870
>> Så der er et par måder
du kunne have gjort dette.

1008
00:49:03,870 --> 00:49:10,900

1009
00:49:10,900 --> 00:49:13,330
Vi har stadig kun C
er af længde 12.

1010
00:49:13,330 --> 00:49:16,480
Du kunne have ændret denne
som en del af din løsning.

1011
00:49:16,480 --> 00:49:18,930
Vi har også tilføjet en check til at gøre
sikker bar ikke var nul.

1012
00:49:18,930 --> 00:49:24,460
Selvom du ikke har brug for
at for fuld kredit.

1013
00:49:24,460 --> 00:49:27,690
Så vi tjekker først
snorlængde på baren.

1014
00:49:27,690 --> 00:49:31,650
Hvis det er større end 12, så
faktisk ikke gøre kopien.

1015
00:49:31,650 --> 00:49:33,010
Så det er en måde at løse det.

1016
00:49:33,010 --> 00:49:36,750
>> En anden måde at løse det er i stedet for
der c kun en længde 12, har det

1017
00:49:36,750 --> 00:49:39,310
være af en længde strlen (bar).

1018
00:49:39,310 --> 00:49:43,370
En anden måde at løse det er
til rent faktisk bare vende tilbage.

1019
00:49:43,370 --> 00:49:46,690
Så hvis du lige havde fået fjernet alle
dette, hvis du bare havde slettet alle

1020
00:49:46,690 --> 00:49:51,830
linjer kode, ville du have fået
fuld kredit, da denne funktion

1021
00:49:51,830 --> 00:49:54,150
faktisk ikke udrette noget.

1022
00:49:54,150 --> 00:49:57,650
Det kopierer kommandolinjen
argument ind i nogle array i

1023
00:49:57,650 --> 00:49:59,960
dens lokale stakrammen.

1024
00:49:59,960 --> 00:50:01,310
Og så de ting er tilbage.

1025
00:50:01,310 --> 00:50:04,020
Og hvad det dygtig er væk.

1026
00:50:04,020 --> 00:50:09,740
Så var afkastet også en tilstrækkelig
måde at få fuld kredit.

1027
00:50:09,740 --> 00:50:13,425
>> DAVID J. MALAN: Ikke helt ånd
spørgsmålet men acceptabel pr

1028
00:50:13,425 --> 00:50:15,580
spec alligevel.

1029
00:50:15,580 --> 00:50:18,260
>> ROB BOWDEN: Spørgsmål om noget af det?

1030
00:50:18,260 --> 00:50:22,270
Den ene ting, at du i det mindste
nødvendigt at have kompilere kode.

1031
00:50:22,270 --> 00:50:24,810
Så selvom teknisk du ikke er
sårbare, hvis din kode ikke

1032
00:50:24,810 --> 00:50:29,130
kompilere, vi ikke acceptere.

1033
00:50:29,130 --> 00:50:31,350
Ingen spørgsmål?

1034
00:50:31,350 --> 00:50:33,320
OK.

1035
00:50:33,320 --> 00:50:34,580
>> DAVID J. MALAN: Ønsker du
at sige denne titel?

1036
00:50:34,580 --> 00:50:37,230
>> ROB BOWDEN: Nej.

1037
00:50:37,230 --> 00:50:40,470
>> DAVID J. MALAN: Så i dette ene, dette
var enten gode nyheder eller dårlige nyheder.

1038
00:50:40,470 --> 00:50:43,870
Det er bogstaveligt talt det samme problem
som den første quiz.

1039
00:50:43,870 --> 00:50:46,140
Og det er næsten det samme
problem som pset1.

1040
00:50:46,140 --> 00:50:49,980
Men det var med vilje forenklet for at være
en enklere pyramide, en, der kan være

1041
00:50:49,980 --> 00:50:52,330
løst med en lidt
enklere iteration.

1042
00:50:52,330 --> 00:50:55,680
Og virkelig, hvad vi fik på
her var ikke så meget logik,

1043
00:50:55,680 --> 00:50:58,100
fordi formentlig, ved dette punkt, er du
mere komfortabel end du var

1044
00:50:58,100 --> 00:51:01,850
i uge ét med for løkker eller hvorfor loops,
men virkelig at drille hinanden, at

1045
00:51:01,850 --> 00:51:04,790
du er lidt fortrolig med
forestilling om, at PHP er ikke kun om, hvad

1046
00:51:04,790 --> 00:51:05,290
programmering.

1047
00:51:05,290 --> 00:51:07,820
Det kan faktisk bruges som et sprog
at skrive kommandolinjeprogrammer.

1048
00:51:07,820 --> 00:51:10,060
>> Og ja, det er hvad vi forsøgte
at henlede Deres opmærksomhed på.

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, 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 de løsninger til Quiz
0 imod Quiz 1, vil du opdage, at

1053
00:51:21,720 --> 00:51:25,630
det er næsten identiske, bortset
nogle dollartegn og for

1054
00:51:25,630 --> 00:51:27,250
fraværet af en datatype.

1055
00:51:27,250 --> 00:51:31,720
Især hvis vi tager et kig her,
vil du se, at vi gentage i denne

1056
00:51:31,720 --> 00:51:33,730
fald fra 1 op til 7.

1057
00:51:33,730 --> 00:51:34,910
>> Vi kunne have gjort det 0-indekset.

1058
00:51:34,910 --> 00:51:37,320
Men nogle gange tror jeg, det er bare
mentalt lettere at tænke over tingene

1059
00:51:37,320 --> 00:51:38,200
fra 1 til 7.

1060
00:51:38,200 --> 00:51:40,300
Hvis du vil have en blok, så to
blokke, så tre, så

1061
00:51:40,300 --> 00:51:41,770
prik, prik, prik syv.

1062
00:51:41,770 --> 00:51:45,960
Vi har j initialiseres til 1
og derefter regner med op til i.

1063
00:51:45,960 --> 00:51:48,150
Og alt her er
ellers identisk.

1064
00:51:48,150 --> 00:51:49,790
Men værd at bemærke er
et par ting.

1065
00:51:49,790 --> 00:51:53,230
Vi giver dig disse to linjer, denne første
en, goofily navngivet som en molevitten

1066
00:51:53,230 --> 00:51:54,560
for skarp brag.

1067
00:51:54,560 --> 00:51:58,770
Og at netop angiver stien,
mappe, hvor et program kan være

1068
00:51:58,770 --> 00:52:02,160
fandt, at du ønsker at bruge
at fortolke denne fil.

1069
00:52:02,160 --> 00:52:04,710
>> Og så den linje efter, at af
Selvfølgelig betyder indtaste PHP mode.

1070
00:52:04,710 --> 00:52:07,740
Og den linje allernederst
betyder exit PHP mode.

1071
00:52:07,740 --> 00:52:09,740
Og det virker i almindelighed med
fortolket sprog.

1072
00:52:09,740 --> 00:52:14,370
Det er lidt irriterende, hvis du skriver en
program i en fil kaldet foo.php.

1073
00:52:14,370 --> 00:52:17,320
Og så dine brugere skal bare
Husk, OK, at køre dette program, jeg

1074
00:52:17,320 --> 00:52:22,320
nødt til at skrive "php plads foo.php". Kind
irriterende, hvis intet andet.

1075
00:52:22,320 --> 00:52:25,270
Og det afslører også, at dit program
er skrevet i PHP, hvilket ikke er alle

1076
00:52:25,270 --> 00:52:27,060
at lysende for brugeren.

1077
00:52:27,060 --> 00:52:30,100
>> Så du kan fjerne det. Php helt
huske fra foredraget.

1078
00:52:30,100 --> 00:52:35,690
Og du kan faktisk gøre. / Foo hvis
du har chmodded det ved at gøre det

1079
00:52:35,690 --> 00:52:36,500
eksekverbare.

1080
00:52:36,500 --> 00:52:39,630
Så chmod a + x foo ville have gjort.

1081
00:52:39,630 --> 00:52:41,460
Og hvis du også tilføje molevitten her.

1082
00:52:41,460 --> 00:52:45,320
Men virkelig, problemet var at komme på
udskrivning ud noget som dette.

1083
00:52:45,320 --> 00:52:51,100
Ingen HTML, ingen C-kode sikkert,
blot nogle PHP.

1084
00:52:51,100 --> 00:52:54,100
Så Milo vendte derefter tilbage i problemet 25.

1085
00:52:54,100 --> 00:52:58,050
Og i 25, var du givet følgende
skelet kode, som var en

1086
00:52:58,050 --> 00:52:59,730
temmelig simpel webside.

1087
00:52:59,730 --> 00:53:04,230
Og den saftige del HTML-wise var nede
her, hvor vi har indersiden af ​​kroppen

1088
00:53:04,230 --> 00:53:09,160
en form, der har unikke id af input
inderside, som var to indgange, den ene

1089
00:53:09,160 --> 00:53:11,950
med en idé om navn, en
med en idé om knap.

1090
00:53:11,950 --> 00:53:14,240
>> Den første var typen tekst, den
sekund af typen indsende.

1091
00:53:14,240 --> 00:53:16,930
Og så vi gav dig, faktisk, mere
ingredienser, end du har brug for, lige så

1092
00:53:16,930 --> 00:53:19,230
du fyre havde muligheder, som
at løse dette problem.

1093
00:53:19,230 --> 00:53:21,130
Du behøver ikke strengt nødvendigt
alle disse ID'er.

1094
00:53:21,130 --> 00:53:23,580
Men det giver dig mulighed for at løse
det på forskellige måder.

1095
00:53:23,580 --> 00:53:27,050
Og op i toppen, bemærke, at
målet var at udløse

1096
00:53:27,050 --> 00:53:27,960
et vindue som dette -

1097
00:53:27,960 --> 00:53:28,780
Hej, Milo! -

1098
00:53:28,780 --> 00:53:31,270
at dukke op i browseren ved hjælp af
super simpelt, hvis

1099
00:53:31,270 --> 00:53:33,190
ikke grim, alarm funktion.

1100
00:53:33,190 --> 00:53:37,480
Og så i sidste ende, det koges ned
begrebsmæssigt en eller anden måde at lytte til

1101
00:53:37,480 --> 00:53:41,290
indsendelser af formen client-side
, Ikke server-side, en eller anden måde

1102
00:53:41,290 --> 00:53:45,640
reagere på denne indsendelse af
snuppe den værdi, som brugeren har indtastet

1103
00:53:45,640 --> 00:53:50,120
på feltnavnet og derefter
vise det i kroppen af ​​en indberetning.

1104
00:53:50,120 --> 00:53:53,460
>> Så en måde du kan gøre dette på er med
jQuery, der ser lidt

1105
00:53:53,460 --> 00:53:56,880
syntaktisk forvirrende ved første.

1106
00:53:56,880 --> 00:54:00,760
Du kan gøre dette med ren DOM kode -
document.getelement med id.

1107
00:54:00,760 --> 00:54:02,530
Men lad os tage et kig på denne version.

1108
00:54:02,530 --> 00:54:05,110
Jeg har et par vigtige
linjer først.

1109
00:54:05,110 --> 00:54:09,460
Så man har vi denne linje, der er
identisk med det, du måske har set

1110
00:54:09,460 --> 00:54:13,830
i, tror jeg, form2.html
fra klasse i uge 9..

1111
00:54:13,830 --> 00:54:16,960
Og det er bare at sige, udfø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
Det er vigtigt kun fordi
HTML-sider læses fra top til

1114
00:54:21,770 --> 00:54:23,280
bund, venstre mod højre.

1115
00:54:23,280 --> 00:54:27,910
>> Og derfor, hvis du forsøger at gøre
noget i kode op her til nogle DOM

1116
00:54:27,910 --> 00:54:31,560
element, nogle HTML-tag, der er ned
her, du gør det for hurtigt,

1117
00:54:31,560 --> 00:54:34,220
fordi det har ikke engang
er indlæst i hukommelsen.

1118
00:54:34,220 --> 00:54:37,740
Så ved at sige dette document.ready
linje, vi siger,

1119
00:54:37,740 --> 00:54:39,040
her er noget kode, browser.

1120
00:54:39,040 --> 00:54:42,440
Men du behøver ikke udføre dette, før hele
dokumentet er klar, dvs DOM

1121
00:54:42,440 --> 00:54:44,320
findes træ i hukommelsen.

1122
00:54:44,320 --> 00:54:47,110
Denne ene er lidt mere
ligetil, hvis syntaktisk en

1123
00:54:47,110 --> 00:54:51,890
lidt anderledes, hvor jeg siger, grab
HTML-element, hvis unikke

1124
00:54:51,890 --> 00:54:53,560
id er indgange.

1125
00:54:53,560 --> 00:54:56,220
Det er, hvad hash tag
betegner den unikke id.

1126
00:54:56,220 --> 00:54:58,070
Og så jeg ringer. Indsende.

1127
00:54:58,070 --> 00:55:01,660
>> So. Indsende her er en funktion, ellers
kendt som en fremgangsmåde, der er

1128
00:55:01,660 --> 00:55:05,850
indersiden af ​​objektet på venstre hånd
side er der, at jeg ikke fremhæve.

1129
00:55:05,850 --> 00:55:08,990
Så hvis du tænker på input som et objekt
i hukommelsen - og det er faktisk.

1130
00:55:08,990 --> 00:55:10,440
Det er en knude i et træ -

1131
00:55:10,440 --> 00:55:16,580
. Indsende midler, når denne formular med
dette id er forelagt, udføre

1132
00:55:16,580 --> 00:55:17,700
følgende kode.

1133
00:55:17,700 --> 00:55:20,290
Jeg er ligeglad, hvad navnet på den
Funktionen er jeg udfører.

1134
00:55:20,290 --> 00:55:23,760
Så her jeg bruger, som før, hvad er
kaldt lambda funktion eller en

1135
00:55:23,760 --> 00:55:24,720
anonym funktion.

1136
00:55:24,720 --> 00:55:27,640
Det er slet ikke intellektuelt
interessant andet end det ikke har noget navn,

1137
00:55:27,640 --> 00:55:30,220
hvilket er fint, hvis du kun
nogensinde kommer til at kalde det en gang.

1138
00:55:30,220 --> 00:55:34,490
Og derinde jeg faktisk håndtere
indsendelse af formularen.

1139
00:55:34,490 --> 00:55:36,810
Jeg først erklære en variabel
kaldet værdi.

1140
00:55:36,810 --> 00:55:40,610
Og hvad er effekten af ​​denne
fremhævet del her nu?

1141
00:55:40,610 --> 00:55:44,755
Hvad betyder det gøre på en
højt til mig?

1142
00:55:44,755 --> 00:55:48,539
>> PUBLIKUM: Det bliver den værdi, som
brugeren ikke gjorde i HTML nedenfor.

1143
00:55:48,539 --> 00:55:50,920
Det bliver at id og derefter
finder værdien af ​​det.

1144
00:55:50,920 --> 00:55:51,590
>> DAVID J. MALAN: Præcis.

1145
00:55:51,590 --> 00:55:54,300
Det griber node, hvis unikke
id er navnet.

1146
00:55:54,300 --> 00:55:56,900
Det får den værdi, deri, som
er formentlig, hvad brugeren

1147
00:55:56,900 --> 00:55:58,190
indtastet ham eller hende selv.

1148
00:55:58,190 --> 00:56:01,020
Og så gemmer der i
variabel kaldet værdi.

1149
00:56:01,020 --> 00:56:03,720
Som en sidebemærkning, kan du også have
gjort dette lidt anderledes.

1150
00:56:03,720 --> 00:56:09,250
Helt acceptabelt ved at gøre noget
løgn var værdi 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 det er derfor, det er lidt
trættende ikke at bruge jQuery.

1154
00:56:15,460 --> 00:56:16,710
"Navn". Værdi.

1155
00:56:16,710 --> 00:56:18,330

1156
00:56:18,330 --> 00:56:19,620
Så helt acceptabelt.

1157
00:56:19,620 --> 00:56:22,770
Forskellige måder at gøre dette. jQuery bare
tendens til at være lidt mere kortfattet og

1158
00:56:22,770 --> 00:56:25,230
klart mere populær
blandt programmører.

1159
00:56:25,230 --> 00:56:27,590
>> Nu, jeg laver lidt af en tilregnelighed
check, fordi problemet

1160
00:56:27,590 --> 00:56:30,820
erklæring, vi udtrykkeligt sagt, hvis det
bruger har endnu ikke indtastet hans eller hendes

1161
00:56:30,820 --> 00:56:32,580
navn, viser ikke en indberetninger.

1162
00:56:32,580 --> 00:56:35,390
Men du kan tjekke for, at ved blot
kontrol af den tomme streng for en

1163
00:56:35,390 --> 00:56:37,850
quote-citat slut, hvis der er
intet faktisk er der.

1164
00:56:37,850 --> 00:56:40,880
Men hvis det er ikke lig med citat-citat slut,
Jeg vil ringe til advarsler.

1165
00:56:40,880 --> 00:56:45,610
Og det interessante del er, at
vi bruger plus operatør, som

1166
00:56:45,610 --> 00:56:48,130
gør hvad i JavaScript?

1167
00:56:48,130 --> 00:56:48,740
Sammenkæde.

1168
00:56:48,740 --> 00:56:50,690
Så det er ligesom PHPs dot operatør.

1169
00:56:50,690 --> 00:56:52,820
Samme idé, lidt anderledes syntaks.

1170
00:56:52,820 --> 00:56:55,280
Og jeg blot at skabe den streng,
du så på skærmen skud -

1171
00:56:55,280 --> 00:56:57,750
Hej, så og så.

1172
00:56:57,750 --> 00:56:59,200
>> Og så den sidste detalje er dette.

1173
00:56:59,200 --> 00:57:04,970
Hvorfor jeg tilbage falsk indeni
af denne anonyme funktion?

1174
00:57:04,970 --> 00:57:07,420
>> PUBLIKUM: Der er ingen værdi.

1175
00:57:07,420 --> 00:57:09,380
Du sætter det i formularen.

1176
00:57:09,380 --> 00:57:12,320

1177
00:57:12,320 --> 00:57:16,730
Det bare siger, hvis værdi ikke
svarende til tomme, så gør det.

1178
00:57:16,730 --> 00:57:20,040

1179
00:57:20,040 --> 00:57:20,940
Der var en blank i denne underkastelse.

1180
00:57:20,940 --> 00:57:21,170
>> DAVID J. MALAN: OK.

1181
00:57:21,170 --> 00:57:21,640
Vær dog forsigtig.

1182
00:57:21,640 --> 00:57:22,830
Der er ingen andre her.

1183
00:57:22,830 --> 00:57:25,510
Og at return false er udenfor
af hvis forholdene.

1184
00:57:25,510 --> 00:57:29,470
Så dette fremhævede linje, return false,
udfører ikke hvad når stof

1185
00:57:29,470 --> 00:57:32,310
formularen er sendt.

1186
00:57:32,310 --> 00:57:36,810
Hvad tilbage falsk Indersiden af
event handleren, som det hedder,

1187
00:57:36,810 --> 00:57:38,450
den pågældende begivenhed
være indsendelse?

1188
00:57:38,450 --> 00:57:42,350

1189
00:57:42,350 --> 00:57:44,470
>> PUBLIKUM: Fordi det
kun sker én gang.

1190
00:57:44,470 --> 00:57:45,320
>> DAVID J. MALAN: Kun sker en gang.

1191
00:57:45,320 --> 00:57:46,821
Ikke helt.

1192
00:57:46,821 --> 00:57:47,292
Ja?

1193
00:57:47,292 --> 00:57:50,589
>> PUBLIKUM: Det forhindrer form fra
indsendelse til standard opførsel,

1194
00:57:50,589 --> 00:57:52,480
hvilket ville gøre siden reload.

1195
00:57:52,480 --> 00:57:53,110
>> DAVID J. MALAN: Præcis.

1196
00:57:53,110 --> 00:57:56,490
Så jeg overbelastning udtrykket indsende her,
fordi jeg siger, formen er

1197
00:57:56,490 --> 00:57:57,670
at blive sendt.

1198
00:57:57,670 --> 00:58:02,240
Men som du antyder, er det faktisk ikke
blevet forelagt i den sande HTTP måde.

1199
00:58:02,240 --> 00:58:06,870
Når du klikker på Send, på grund af vores
onSubmit handleren, vi opsnappe

1200
00:58:06,870 --> 00:58:09,040
at formularafsendelse så at sige.

1201
00:58:09,040 --> 00:58:11,290
Vi derefter gøre vores ting
med JavaScript-kode.

1202
00:58:11,290 --> 00:58:14,070
Men jeg bevidst returnere falsk,
fordi det, jeg ikke ønsker at ske en

1203
00:58:14,070 --> 00:58:18,430
splitsekund senere er for hele formular
selv, der skal forelægges på nettet

1204
00:58:18,430 --> 00:58:22,800
server med centrale værdipar ved at ændre
URL til at være noget lignende

1205
00:58:22,800 --> 00:58:26,180
q = katte eller hvad vi gjorde,
for eksempel i klassen.

1206
00:58:26,180 --> 00:58:29,640
Jeg ønsker ikke, at det sker, fordi
Der er ingen server lytte til dette

1207
00:58:29,640 --> 00:58:30,690
danne indsendelse.

1208
00:58:30,690 --> 00:58:32,320
Det er udelukkende gjort i JavaScript-kode.

1209
00:58:32,320 --> 00:58:35,760
Og det er derfor jeg ikke engang har en
handling attribut på min form, fordi jeg

1210
00:58:35,760 --> 00:58:38,870
agter ikke for at dette kan
nogensinde gå til serveren.

1211
00:58:38,870 --> 00:58:40,780
>> Så det er at blive sendt.

1212
00:58:40,780 --> 00:58:44,340
Men vi opsnappe denne formular
indsendelse og forhindre standard

1213
00:58:44,340 --> 00:58:47,477
adfærd, som er rent faktisk
gå hele vejen til serveren.

1214
00:58:47,477 --> 00:58:48,730
>> PUBLIKUM: Så holder det client-side.

1215
00:58:48,730 --> 00:58:49,780
>> DAVID J. MALAN: Hold
det client-side.

1216
00:58:49,780 --> 00:58:51,030
Præcis højre.

1217
00:58:51,030 --> 00:58:53,240

1218
00:58:53,240 --> 00:58:55,757
Næste op 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å det første spørgsmål var generelt
uslebne for mennesker.

1222
00:59:04,990 --> 00:59:07,270
Selvom senere dem gik bedre.

1223
00:59:07,270 --> 00:59:12,260
Så du skulle vælge de korrekte data
typer for begge disse kolonner.

1224
00:59:12,260 --> 00:59:17,750
Og begge disse har nogle
ting om dem, at

1225
00:59:17,750 --> 00:59:20,620
gøre valget svært.

1226
00:59:20,620 --> 00:59:24,430
Så int ikke var et gyldigt
skriv for nummer.

1227
00:59:24,430 --> 00:59:29,410
Årsagen er en 12-cifret konto
nummer, en int er ikke stor nok til at

1228
00:59:29,410 --> 00:59:31,070
gemme samlede cifre.

1229
00:59:31,070 --> 00:59:36,570
Så et gyldigt valg ville have været en stor
int hvis du tilfældigvis kender det.

1230
00:59:36,570 --> 00:59:42,090
Et andet valg kunne have været
en char på længde 12.

1231
00:59:42,090 --> 00:59:44,560
Så enten af ​​dem ville have fungeret.

1232
00:59:44,560 --> 00:59:46,100
Int. ville ikke.

1233
00:59:46,100 --> 00:59:50,170
>> Nu, balance, tænke tilbage på pset7.

1234
00:59:50,170 --> 00:59:59,540
Så vi specifikt anvendes decimal til
gemme værdien af ​​aktier eller -

1235
00:59:59,540 --> 01:00:00,550
>> DAVID J. MALAN: Kontant.

1236
01:00:00,550 --> 01:00:01,060
>> ROB BOWDEN: Kontant.

1237
01:00:01,060 --> 01:00:05,710
Vi brugte decimal til at lagre den mængde
kontanter, som brugeren har i øjeblikket.

1238
01:00:05,710 --> 01:00:10,950
Så årsagen til at vi gør det er
fordi huske, flåd.

1239
01:00:10,950 --> 01:00:12,480
Der er floating point i præcision.

1240
01:00:12,480 --> 01:00:18,200
Det kan ikke præcist gemme kontanter
værdier som vi ønsker her.

1241
01:00:18,200 --> 01:00:23,630
Så decimal er i stand til præcist butik
noget til, sige, to decimaler.

1242
01:00:23,630 --> 01:00:27,630
Det er derfor, balance, vi ønsker det
være decimal og ikke flyde.

1243
01:00:27,630 --> 01:00:30,230
>> DAVID J. MALAN: Og også, også selvom
det kunne have været smart i andre

1244
01:00:30,230 --> 01:00:32,760
sammenhænge til at tænke, måske denne
er en chance for en int.

1245
01:00:32,760 --> 01:00:34,420
Jeg vil bare holde styr på
ting i øre.

1246
01:00:34,420 --> 01:00:38,670
Fordi vi udtrykkeligt viste standard
værdien af ​​at være 100,00, at

1247
01:00:38,670 --> 01:00:40,380
betyder, at det kunne bare være en int.

1248
01:00:40,380 --> 01:00:45,310
Og en anden underfundighed også med nummer
var, at det ikke var ment

1249
01:00:45,310 --> 01:00:46,180
at være et trick spørgsmål.

1250
01:00:46,180 --> 01:00:49,860
Men husker at en int i MySQL,
som i C, i det mindste i

1251
01:00:49,860 --> 01:00:51,440
apparat, er 32-bit.

1252
01:00:51,440 --> 01:00:53,960
Og selvom vi ikke forventer, at du
vide præcis, hvor mange cifre der

1253
01:00:53,960 --> 01:00:56,910
midler, må minde om, at det største antal
du kan repræsentere potentielt

1254
01:00:56,910 --> 01:01:00,710
med en 32-bit tal er omtrent, hvad?

1255
01:01:00,710 --> 01:01:02,760
>> Hvilket nummer har vi altid siger?

1256
01:01:02,760 --> 01:01:04,530
2 til 32, hvilket er det groft?

1257
01:01:04,530 --> 01:01:07,492

1258
01:01:07,492 --> 01:01:08,780
Du behøver ikke at vide præcist.

1259
01:01:08,780 --> 01:01:10,580
Men groft er nyttigt i livet.

1260
01:01:10,580 --> 01:01:12,200
Det er omtrent 4 mia.

1261
01:01:12,200 --> 01:01:14,430
Så vi har sagt, at et par gange.

1262
01:01:14,430 --> 01:01:16,360
Jeg ved, jeg har sagt, at et par gange.

1263
01:01:16,360 --> 01:01:17,670
Og det er omtrent 4 mia.

1264
01:01:17,670 --> 01:01:19,710
Og det er en god regel
tommelfinger til at vide.

1265
01:01:19,710 --> 01:01:21,880
Hvis du har 8 bit, 256
er det magiske tal.

1266
01:01:21,880 --> 01:01:24,160
Hvis du har 32 bit, 4
milliarder give eller tage.

1267
01:01:24,160 --> 01:01:27,140
Så hvis du bare skrive ned 4 milliarder,
du vil se, at det er færre cifre end

1268
01:01:27,140 --> 01:01:30,970
12, hvilket betyder, at der er helt klart ikke
nok udtryksfuldhed til at fange en

1269
01:01:30,970 --> 01:01:34,220
12-cifret 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 gik bedre.

1272
01:01:38,520 --> 01:01:40,900
Så antage, at banken
pålægger en $ 20 månedligt

1273
01:01:40,900 --> 01:01:42,400
vedligeholdelse gebyr på alle konti.

1274
01:01:42,400 --> 01:01:45,506
Med hvad SQL-forespørgsel kunne banken
fratrække 20 dollar fra hver tæller, også selvom

1275
01:01:45,506 --> 01:01:47,520
det resulterer i nogle negative saldi?

1276
01:01:47,520 --> 01:01:50,380
Så dybest set er der fire
hovedtyper af forespørgsler -

1277
01:01:50,380 --> 01:01:52,840
indsætte, skal du vælge, opdatere og slette.

1278
01:01:52,840 --> 01:01:56,080
Så hvad gør vi tror, ​​vi er
kommer til at bruge her?

1279
01:01:56,080 --> 01:01:57,000
Opdater.

1280
01:01:57,000 --> 01:01:58,260
>> Så lad os tage et kig.

1281
01:01:58,260 --> 01:02:04,290

1282
01:02:04,290 --> 01:02:05,870
Så her er vi opdaterer.

1283
01:02:05,870 --> 01:02:09,900
Hvad tabellen er vi opdatere konti?

1284
01:02:09,900 --> 01:02:11,670
Så opdatere konti.

1285
01:02:11,670 --> 01:02:15,390
Og så syntaksen siger, hvad
i regnskabet er vi opdatere?

1286
01:02:15,390 --> 01:02:19,520
Nå, vi sætte balance svarende til
aktuelle værdi af balance minus 20.

1287
01:02:19,520 --> 01:02:22,860
Så dette vil opdatere alle rækker
af regnskaber, subtraktion

1288
01:02:22,860 --> 01:02:26,250
$ 20 fra saldoen.

1289
01:02:26,250 --> 01:02:29,260
>> DAVID J. MALAN: En almindelig fejl her,
selv om vi undertiden tilgav det,

1290
01:02:29,260 --> 01:02:32,990
var faktisk have PHP kode her
kalde forespørgslen funktion eller lægge

1291
01:02:32,990 --> 01:02:35,460
anførselstegn omkring alt, hvad der
behøvede ikke at være der.

1292
01:02:35,460 --> 01:02:39,780
>> ROB BOWDEN: Husk, at MySQL er
et separat sprog fra PHP.

1293
01:02:39,780 --> 01:02:42,410
Vi tilfældigvis skal skrive MySQL i PHP.

1294
01:02:42,410 --> 01:02:46,180
Og PHP er derefter sende det
over til MySQL-serveren.

1295
01:02:46,180 --> 01:02:51,120
Men du behøver ikke PHP for at
kommunikere med en MySQL-serveren.

1296
01:02:51,120 --> 01:02:51,730
>> DAVID J. MALAN: Præcis.

1297
01:02:51,730 --> 01:02:54,240
Så ingen variabler med dollartegn
bør i denne sammenhæng.

1298
01:02:54,240 --> 01:02:59,550
Det kan bare gøre alle de matematik
inden 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 næste.

1301
01:03:01,300 --> 01:03:02,731
Er dette den næste?

1302
01:03:02,731 --> 01:03:03,210
Ja.

1303
01:03:03,210 --> 01:03:06,570
Så med hvad SQL-forespørgsel kunne banken
hente kontonumre dens

1304
01:03:06,570 --> 01:03:09,300
rigeste kunder, dem med
saldi større end 1.000?

1305
01:03:09,300 --> 01:03:13,280
Så hvilken af ​​de fire hovedtyper
skal vi have her?

1306
01:03:13,280 --> 01:03:14,430
Vælg.

1307
01:03:14,430 --> 01:03:16,650
Så vi ønsker at markere.

1308
01:03:16,650 --> 01:03:17,610
Hvad ønsker vi at markere?

1309
01:03:17,610 --> 01:03:19,380
Hvad kolonne ønsker vi at markere?

1310
01:03:19,380 --> 01:03:20,970
Vi vil specifikt ønsker
at vælge nummeret.

1311
01:03:20,970 --> 01:03:23,910
Men hvis du sagde stjerne, vi
også accepteret det.

1312
01:03:23,910 --> 01:03:25,820
>> Så vælg et nummer fra hvad bordet?

1313
01:03:25,820 --> 01:03:26,640
Konti.

1314
01:03:26,640 --> 01:03:28,370
Og så den tilstand, vi ønsker?

1315
01:03:28,370 --> 01:03:30,140
Når saldo større end 1.000.

1316
01:03:30,140 --> 01:03:31,720
Vi accepterede også større
end eller lig.

1317
01:03:31,720 --> 01:03:35,230

1318
01:03:35,230 --> 01:03:36,190
Sidste.

1319
01:03:36,190 --> 01:03:42,940
Med hvad SQL-forespørgsel kunne banken
tæt, dvs slette enhver konto, der

1320
01:03:42,940 --> 01:03:44,480
har en balance på $ 0?

1321
01:03:44,480 --> 01:03:47,620
Så hvilken af ​​de fire er vi
lyst til at bruge?

1322
01:03:47,620 --> 01:03:48,320
Slet.

1323
01:03:48,320 --> 01:03:50,180
Så syntaksen for det?

1324
01:03:50,180 --> 01:03:51,890
Slet fra hvad bordet?

1325
01:03:51,890 --> 01:03:53,550
Konti.

1326
01:03:53,550 --> 01:03:55,790
Og så betingelsen for,
vi ønsker at slette -

1327
01:03:55,790 --> 01:03:57,280
hvor balancen er lig med nul.

1328
01:03:57,280 --> 01:04:03,050
Så sletter alle rækker fra konti
hvor balancen er nul.

1329
01:04:03,050 --> 01:04:04,300
Spørgsmål om nogen af ​​disse?

1330
01:04:04,300 --> 01:04:08,840

1331
01:04:08,840 --> 01:04:10,260
Ønsker du at stå i kø?

1332
01:04:10,260 --> 01:04:11,200
>> DAVID J. MALAN: Kø vejledning.

1333
01:04:11,200 --> 01:04:17,110
Så i denne ene, vi gav dig en noget
velkendt struktur, vi udforskede

1334
01:04:17,110 --> 01:04:20,450
bit i klassen ved siden af ​​structs,
som var en data

1335
01:04:20,450 --> 01:04:21,910
struktur relateret på ånd.

1336
01:04:21,910 --> 01:04:24,670
Forskellen dog med en køen
at vi havde en eller anden måde huske, hvem

1337
01:04:24,670 --> 01:04:27,900
var forrest i køen i vid
del, så vi kunne gøre mere

1338
01:04:27,900 --> 01:04:30,530
effektiv udnyttelse af hukommelse, mindst
hvis vi bruger et array.

1339
01:04:30,530 --> 01:04:35,460
>> Fordi huske, hvis vi har et array, hvis
for eksempel er den forreste del af

1340
01:04:35,460 --> 01:04:38,470
køen, hvis jeg kommer ind i køen her,
og så nogen får på linje

1341
01:04:38,470 --> 01:04:42,710
bag mig, bag mig, bag mig, og
én person træder ud af linje, du

1342
01:04:42,710 --> 01:04:45,930
kunne, da vi så nogle af vores menneskelige
frivillige i klassen, har alle

1343
01:04:45,930 --> 01:04:47,100
flytte denne måde.

1344
01:04:47,100 --> 01:04:50,880
Men generelt har alle gøre
noget er ikke den bedste brug af tid

1345
01:04:50,880 --> 01:04:54,600
i et program, fordi det betyder, at din
algoritmen løber i det

1346
01:04:54,600 --> 01:04:56,520
asymptotiske kø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 der er slags dumt.

1349
01:04:59,600 --> 01:05:02,890
Hvis den næste person på linje er den næste
person, der er meningen at gå ind i

1350
01:05:02,890 --> 01:05:04,660
butikken, behøver de ikke alle har
til at bevæge sig sammen.

1351
01:05:04,660 --> 01:05:08,200
Bare lad som person plukkede
når den tid kommer, for eksempel.

1352
01:05:08,200 --> 01:05:09,870
Så vi kan spare lidt tid der.

1353
01:05:09,870 --> 01:05:14,840
Og så for at gøre det selv, det betyder
at lederen af ​​køen eller

1354
01:05:14,840 --> 01:05:18,060
forrest i køen, vil
gradvist bevæger sig dybere og dybere

1355
01:05:18,060 --> 01:05:23,340
i rækken, og i sidste ende kan
faktisk wrap rundt, hvis vi bruger en

1356
01:05:23,340 --> 01:05:25,790
array til at gemme de mennesker
i denne kø.

1357
01:05:25,790 --> 01:05:28,390
Så du kan næsten tænke på
array som en cirkulæ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 en eller anden måde nødt til at holde styr på
størrelsen af ​​det eller virkelig i slutningen af ​​det

1360
01:05:33,970 --> 01:05:36,250
og derefter, hvor begyndelsen af ​​det er.

1361
01:05:36,250 --> 01:05:39,490
Så vi foreslår, at du erklærer
en sådan kø, kald

1362
01:05:39,490 --> 01:05:41,330
det q, blot ét bogstav.

1363
01:05:41,330 --> 01:05:44,570
Så foreslår vi, at den forreste være
initialiseres til nul, og at størrelsen

1364
01:05:44,570 --> 01:05:45,470
initialiseres til nul.

1365
01:05:45,470 --> 01:05:47,770
>> Så lige nu, er der intet
inde i køen.

1366
01:05:47,770 --> 01:05:50,910
Og vi beder dig om at fuldføre
gennemførelse af enqueue nedenfor

1367
01:05:50,910 --> 01:05:55,250
en sådan måde, at funktionen tilføjer n
udgangen af ​​q og derefter returnerer sandt.

1368
01:05:55,250 --> 01:05:58,690
Men hvis q er fuld eller negativ,
funktionen skal i stedet returnere falsk.

1369
01:05:58,690 --> 01:06:01,060
Og vi gav dig et par
antagelser.

1370
01:06:01,060 --> 01:06:04,320
Men de er ikke rigtig funktionelt
relevant, findes netop bool,

1371
01:06:04,320 --> 01:06:06,690
fordi, teknisk bool ikke
findes i C, medmindre du inkluderer en

1372
01:06:06,690 --> 01:06:07,310
vis header fil.

1373
01:06:07,310 --> 01:06:09,350
Så det var bare sørg for at der
blev ingen er dette et trick

1374
01:06:09,350 --> 01:06:10,940
Spørgsmålet slags ting.

1375
01:06:10,940 --> 01:06:16,280
>> Så enqueue, vi foreslog i prøven
løsninger til at gennemføre som følger.

1376
01:06:16,280 --> 01:06:20,420
Én, vi først kontrollere den lethed,
de lavthængende frugter.

1377
01:06:20,420 --> 01:06:23,820
Hvis køen er fuld, eller det antal,
du forsøger at indsætte, er mindre

1378
01:06:23,820 --> 01:06:26,380
end nul, som vi sagde i
specifikation af burde problemet

1379
01:06:26,380 --> 01:06:30,320
ikke tilladt, fordi vi kun ønsker
ikke-negative værdier, så skal du

1380
01:06:30,320 --> 01:06:31,640
bare return false straks.

1381
01:06:31,640 --> 01:06:33,820
Så nogle forholdsvis let
fejlkontrol.

1382
01:06:33,820 --> 01:06:38,720
Hvis om du ønsker at tilføje, at den faktiske
nummer, du havde at gøre en smule

1383
01:06:38,720 --> 01:06:39,440
tænker her.

1384
01:06:39,440 --> 01:06:41,330
Og det er, hvor det er lidt irriterende
mentalt, fordi du er nødt til at

1385
01:06:41,330 --> 01:06:43,000
regne ud, hvordan man håndterer wraparound.

1386
01:06:43,000 --> 01:06:46,870
>> Men kimen til ideen her, der er af
interesse for os er, at wraparound

1387
01:06:46,870 --> 01:06:51,480
indebærer ofte modulær aritmetik og
MOD operatøren, procent side,

1388
01:06:51,480 --> 01:06:55,140
hvor man kan gå fra en større værdi
tilbage til nul og derefter et og to og

1389
01:06:55,140 --> 01:06:58,650
tre og derefter tilbage rundt til nul,
en og to og tre og så videre

1390
01:06:58,650 --> 01:06:59,380
igen og igen.

1391
01:06:59,380 --> 01:07:02,880
Så den måde, vi foreslår at gøre dette er
at vi ønsker at indekset i den

1392
01:07:02,880 --> 01:07:05,850
vifte kaldet numre,
vores heltal lyve.

1393
01:07:05,850 --> 01:07:10,740
Men for at komme der, vi først ønsker at gøre
uanset størrelsen af ​​køen, men

1394
01:07:10,740 --> 01:07:14,080
derefter føje til, at uanset
foran listen.

1395
01:07:14,080 --> 01:07:17,880
Og effekten af ​​det er at sætte os på
den rigtige position i køen og

1396
01:07:17,880 --> 01:07:20,970
ikke antage, at den første person på linje
er i begyndelsen, som han eller

1397
01:07:20,970 --> 01:07:24,130
hun absolut kunne være, hvis vi
også flytte alle.

1398
01:07:24,130 --> 01:07:26,710
Men vi er blot at skabe arbejde
for os selv, hvis vi tog

1399
01:07:26,710 --> 01:07:27,800
denne særlige vej.

1400
01:07:27,800 --> 01:07:29,330
>> Så vi kan holde det relativt simpelt.

1401
01:07:29,330 --> 01:07:32,180
Vi er nødt til at huske på, at vi bare
tilføjet en int til køen.

1402
01:07:32,180 --> 01:07:35,850
Og så har vi bare returnere sandt.

1403
01:07:35,850 --> 01:07:38,560
I mellemtiden, i dequeue, bad vi
dig til at gøre følgende.

1404
01:07:38,560 --> 01:07:42,260
Gennemføre det på en sådan måde, at det
dequeues, der er Fjerner og returnerer,

1405
01:07:42,260 --> 01:07:44,190
int på forsiden af ​​køen.

1406
01:07:44,190 --> 01:07:46,410
For at fjerne int, er det tilstrækkeligt
at glemme det.

1407
01:07:46,410 --> 01:07:47,650
Du behøver ikke at tilsidesætte sin bit.

1408
01:07:47,650 --> 01:07:48,820
Så det er stadig faktisk er der.

1409
01:07:48,820 --> 01:07:51,930
Ligesom data på en harddisk,
vi bare ignorerer det faktum,

1410
01:07:51,930 --> 01:07:52,970
at det nu er der.

1411
01:07:52,970 --> 01:07:55,520
Og hvis q er tom, skal vi
i stedet returnere negativ 1.

1412
01:07:55,520 --> 01:07:56,750
Så det føles vilkårlig.

1413
01:07:56,750 --> 01:08:01,640
Hvorfor returnerer negativ 1
i stedet for falsk?

1414
01:08:01,640 --> 01:08:02,620
Ja.

1415
01:08:02,620 --> 01:08:05,070
>> PUBLIKUM: Q er lagring
positive værdier.

1416
01:08:05,070 --> 01:08:10,950
Da du kun gemmer positive værdier
i q, negativ er en fejl.

1417
01:08:10,950 --> 01:08:11,510
>> DAVID J. MALAN: OK, sandt.

1418
01:08:11,510 --> 01:08:14,850
Så fordi vi kun er opbevaring af positiv
værdier eller nul, så er det fint at

1419
01:08:14,850 --> 01:08:18,050
returnere en negativ værdi som en skildvagt
værdi, et særligt symbol.

1420
01:08:18,050 --> 01:08:21,630
Men du omskrive historien der,
fordi grunden til at vi er kun

1421
01:08:21,630 --> 01:08:25,890
returnere ikke-negative værdier
er, fordi vi ønsker at

1422
01:08:25,890 --> 01:08:27,670
har en skildvagt værdi.

1423
01:08:27,670 --> 01:08:32,617
Så mere specifikt, hvorfor ikke bare
return false i tilfælde af fejl?

1424
01:08:32,617 --> 01:08:33,099
Ja.

1425
01:08:33,099 --> 01:08:35,510
>> PUBLIKUM: Du har fejlet
at returnere et heltal.

1426
01:08:35,510 --> 01:08:36,630
>> DAVID J. MALAN: Præcis.

1427
01:08:36,630 --> 01:08:38,569
Og det er her C får
temmelig begrænsende.

1428
01:08:38,569 --> 01:08:40,590
Hvis du siger du vil
til at returnere en int, har du

1429
01:08:40,590 --> 01:08:41,279
til at returnere en int.

1430
01:08:41,279 --> 01:08:43,689
Du kan ikke få fancy og begynde at vende tilbage
en bool eller en flyder eller en

1431
01:08:43,689 --> 01:08:45,040
snor eller noget lignende.

1432
01:08:45,040 --> 01:08:49,370
Nu, i mellemtiden, JavaScript og PHP og
nogle andre sprog kan faktisk,

1433
01:08:49,370 --> 01:08:51,310
har du returnere anderledes
typer af værdier.

1434
01:08:51,310 --> 01:08:54,819
Og det kan faktisk være nyttigt, hvor
du kunne returnere positive Ints, nuller,

1435
01:08:54,819 --> 01:08:59,439
negative int'er, eller falske eller null
selv at betyde fejl.

1436
01:08:59,439 --> 01:09:01,890
Men vi behøver ikke at
alsidighed i C.

1437
01:09:01,890 --> 01:09:04,569
>> Så med dequeue, hvad vi
foreslår at gøre, er -

1438
01:09:04,569 --> 01:09:07,350

1439
01:09:07,350 --> 01:09:09,830
>> ROB BOWDEN: Du kan vende tilbage falsk.

1440
01:09:09,830 --> 01:09:13,189
Det er bare, at falsk er hash
definere falsk til nul.

1441
01:09:13,189 --> 01:09:16,000
Så hvis du vender tilbage falsk,
du returnere nul.

1442
01:09:16,000 --> 01:09:25,470
Og nul er en gyldig ting i vores kø,
henviser negativ 1 er ikke hvis

1443
01:09:25,470 --> 01:09:27,000
falsk skete for at være negativ 1..

1444
01:09:27,000 --> 01:09:29,972
Men du bør ikke engang
brug for at vide det.

1445
01:09:29,972 --> 01:09:32,399
>> DAVID J. MALAN: Det er
hvorfor jeg ikke sige det.

1446
01:09:32,399 --> 01:09:36,450
>> ROB BOWDEN: Men det var ikke sandt
at du ikke kan returnere falsk.

1447
01:09:36,450 --> 01:09:37,700
>> DAVID J. MALAN: Selvfølgelig.

1448
01:09:37,700 --> 01:09:40,920

1449
01:09:40,920 --> 01:09:44,240
Så dequeue, mærke vi accepterer
ugyldig som sit argument.

1450
01:09:44,240 --> 01:09:45,479
Og det er, fordi vi ikke er
passerer noget i.

1451
01:09:45,479 --> 01:09:48,359
Vi ønsker blot at fjerne elementet
forrest i køen.

1452
01:09:48,359 --> 01:09:49,819
Så hvordan kan vi gå om at gøre dette?

1453
01:09:49,819 --> 01:09:51,290
Nå, det første, lad os gøre det
hurtig tilregnelighed check.

1454
01:09:51,290 --> 01:09:53,350
Hvis køstørrelsen er 0, er der
intet arbejde, der skal gøres.

1455
01:09:53,350 --> 01:09:54,210
Retur negativ 1.

1456
01:09:54,210 --> 01:09:54,800
Udført.

1457
01:09:54,800 --> 01:09:56,340
Så det er et par linjer af mit program.

1458
01:09:56,340 --> 01:09:58,180
Så kun fire linjer tilbage.

1459
01:09:58,180 --> 01:10:01,310
>> Så her jeg beslutter at formindske
størrelse.

1460
01:10:01,310 --> 01:10:04,620
Og decrementing størrelse effektivt
betyder, at jeg glemmer

1461
01:10:04,620 --> 01:10:06,010
noget er derinde.

1462
01:10:06,010 --> 01:10:09,910
Men jeg er også nødt til at opdatere, hvor
forsiden af ​​tallene.

1463
01:10:09,910 --> 01:10:11,620
Så for at gøre det, jeg har brug for
at gøre to ting.

1464
01:10:11,620 --> 01:10:16,390
Jeg har brug for først at huske, hvad nummeret
er forrest i køen,

1465
01:10:16,390 --> 01:10:17,860
fordi jeg har brug for at returnere den ting.

1466
01:10:17,860 --> 01:10:20,910
Så jeg ønsker ikke at uheld glemmer
om det, og derefter overskrive den.

1467
01:10:20,910 --> 01:10:22,840
Jeg skal bare huske på en int.

1468
01:10:22,840 --> 01:10:27,310
>> Og nu, jeg ønsker at opdatere
q.front skal q.front +1.

1469
01:10:27,310 --> 01:10:30,070
Så hvis dette var den første person i
linje nu, jeg ønsker at gøre plus 1 til

1470
01:10:30,070 --> 01:10:31,930
pege på den næste person i linje.

1471
01:10:31,930 --> 01:10:33,420
Men jeg er nødt til at håndtere det wraparound.

1472
01:10:33,420 --> 01:10:37,270
Og hvis kapacitet er en global konstant,
der kommer til at tillade mig at sørge

1473
01:10:37,270 --> 01:10:41,140
da jeg pege på den allersidste person
strækning, modulo operation bringe

1474
01:10:41,140 --> 01:10:43,840
mig tilbage til nul ved
forrest i køen.

1475
01:10:43,840 --> 01:10:46,050
Og der håndterer wraparound her.

1476
01:10:46,050 --> 01:10:48,950
Og så vil jeg gå videre til at vende tilbage n..

1477
01:10:48,950 --> 01:10:51,530
>> Nu, strengt taget, det gjorde jeg ikke
nødt til at erklære n..

1478
01:10:51,530 --> 01:10:53,880
Jeg behøvede ikke at få fat i det og gemme det
midlertidigt, fordi værdien er

1479
01:10:53,880 --> 01:10:54,740
der stadig.

1480
01:10:54,740 --> 01:10:57,490
Så jeg kunne bare gøre det rigtige aritmetiske
til at returnere den tidligere leder

1481
01:10:57,490 --> 01:10:58,450
i køen.

1482
01:10:58,450 --> 01:11:01,850
Men jeg følte bare, at det var mere klar
til rent faktisk at få fat i int, sætte det

1483
01:11:01,850 --> 01:11:04,320
i n, og derefter vende tilbage som
for klarhedens skyld, men

1484
01:11:04,320 --> 01:11:05,735
ikke strengt nødvendigt.

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 udtales i mit hoved.

1488
01:11:13,410 --> 01:11:15,940

1489
01:11:15,940 --> 01:11:19,110
>> ROB BOWDEN: So første spørgsmål
er binært træ problem.

1490
01:11:19,110 --> 01:11:22,140
Så første spørgsmål er, at vi
givet disse numre.

1491
01:11:22,140 --> 01:11:27,160
Og vi ønsker at en eller anden måde indsætte dem i
disse knudepunkter, således at det er en

1492
01:11:27,160 --> 01:11:30,110
gyldig binær søgning træ.

1493
01:11:30,110 --> 01:11:36,260
Så én ting at huske om
binære søgetræer er, at det ikke er

1494
01:11:36,260 --> 01:11:39,800
bare, at de ting til venstre
er mindre, og ting at

1495
01:11:39,800 --> 01:11:41,120
højre er større.

1496
01:11:41,120 --> 01:11:44,580
Det skal være, at hele træet til
venstre er mindre, og hele træet

1497
01:11:44,580 --> 01:11:45,740
til højre er større.

1498
01:11:45,740 --> 01:11:55,260
>> Så hvis jeg sætter 34 her i toppen, og derefter
Jeg sætter 20 her, så det er gyldigt, så

1499
01:11:55,260 --> 01:11:56,970
langt, fordi 34 heroppe.

1500
01:11:56,970 --> 01:11:57,920
20 går til 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 ikke derefter sætte 59 her, fordi
selv om 59 er på højre side af 20

1503
01:12:03,640 --> 01:12:06,140
det er stadig til venstre 34.

1504
01:12:06,140 --> 01:12:10,760
Så med denne begrænsning i tankerne,
nemmeste måde nok at løse dette

1505
01:12:10,760 --> 01:12:14,330
Problemet er bare at sortere
af disse numre -

1506
01:12:14,330 --> 01:12:18,720
så 20, 34, 36, 52, 59, 106.

1507
01:12:18,720 --> 01:12:21,640
Og derefter indsætte dem
fra venstre til højre.

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 have regnet ud med
nogle tilslutte og realisere,

1513
01:12:34,730 --> 01:12:38,830
Åh, vent, jeg har ikke nok numre
at udfylde dette i herovre.

1514
01:12:38,830 --> 01:12:42,170
Så jeg har brug for at reshift hvad min
rute note bliver.

1515
01:12:42,170 --> 01:12:47,490
Men bemærk, at der i de sidste tre, hvis
du læser fra venstre mod højre, er det i

1516
01:12:47,490 --> 01:12:48,740
stigende orden.

1517
01:12:48,740 --> 01:12:52,150

1518
01:12:52,150 --> 01:12:56,540
>> Så nu ønsker vi at erklære, hvad
struct vil være for

1519
01:12:56,540 --> 01:12:58,300
knudepunkter i dette træ.

1520
01:12:58,300 --> 01:13:02,720
Så hvad har vi brug for i et binært træ?

1521
01:13:02,720 --> 01:13:05,830
Så vi har en værdi af typen
int, så nogle int værdi.

1522
01:13:05,830 --> 01:13:07,220
Jeg ved ikke, hvad vi kaldte
det i opløsningen -

1523
01:13:07,220 --> 01:13:08,500
int n.

1524
01:13:08,500 --> 01:13:13,570
Vi har brug for en pointer til venstre barn
og en pointer til den rigtige barn.

1525
01:13:13,570 --> 01:13:17,540
Så det kommer til at se sådan ud.

1526
01:13:17,540 --> 01:13:20,510
Og det vil faktisk se, før
hvornår har den 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 har tænkt mig at skulle rulle hele
vej tilbage ned til problem 11.

1529
01:13:27,860 --> 01:13:30,980

1530
01:13:30,980 --> 01:13:36,390
>> Så bemærker det ser identisk med dette,
medmindre vi bare tilfældigvis kalde disse

1531
01:13:36,390 --> 01:13:38,590
forskellige navne.

1532
01:13:38,590 --> 01:13:41,440
Vi har stadig et heltal
værdi og to pointere.

1533
01:13:41,440 --> 01:13:44,850
Det er bare at i stedet for at behandle
pejlemærker, som peger på den næste ting

1534
01:13:44,850 --> 01:13:47,955
og den tidligere ting, vi behandler
markørerne til at pege på en venstre barn

1535
01:13:47,955 --> 01:13:49,205
og højre 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 vores struct node.

1539
01:13:59,650 --> 01:14:03,920
Og nu er den eneste funktion, vi er nødt til at
redskab til dette er travers, som

1540
01:14:03,920 --> 01:14:08,320
vi ønsker at gå over træet, trykning
de værdier af træet i rækkefølge.

1541
01:14:08,320 --> 01:14:15,241
>> Så ser her, ville vi ønsker at udskrive
ud 20, 34, 36, 52, 59, og 106.

1542
01:14:15,241 --> 01:14:17,970
Hvordan kan vi opnå det?

1543
01:14:17,970 --> 01:14:18,890
Så det er temmelig ens.

1544
01:14:18,890 --> 01:14:22,910
Hvis du har set i fortiden eksamen problemet
at man ønskede at udskrive

1545
01:14:22,910 --> 01:14:25,940
hele træet med kommaer i mellem
alt, det var faktisk endnu

1546
01:14:25,940 --> 01:14:27,320
lettere end 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 betydeligt lettere
hvis du gjorde det rekursivt.

1549
01:14:33,110 --> 01:14:36,650
Jeg ved ikke, om nogen har forsøgt
at gøre det iterativt.

1550
01:14:36,650 --> 01:14:38,340
>> Men først har vi vores base case.

1551
01:14:38,340 --> 01:14:39,660
Hvad hvis roden er nul?

1552
01:14:39,660 --> 01:14:40,610
Så vil vi bare at vende tilbage.

1553
01:14:40,610 --> 01:14:42,300
Vi ønsker ikke at udskrive noget.

1554
01:14:42,300 --> 01:14:45,940
Else vi kommer til at krydse
rekursivt ned.

1555
01:14:45,940 --> 01:14:48,140
Udskriv hele venstre undertræ.

1556
01:14:48,140 --> 01:14:51,440
Så udskrive alt mindre
end min nuværende værdi.

1557
01:14:51,440 --> 01:14:53,930
Og så har jeg tænkt mig at printe selv.

1558
01:14:53,930 --> 01:14:57,310
Og så har jeg tænkt mig at recurse ned min
hele højre undertræ, så alt

1559
01:14:57,310 --> 01:14:58,810
større end min værdi.

1560
01:14:58,810 --> 01:15:03,870
Og det kommer til at udskrive
ud af alt i orden.

1561
01:15:03,870 --> 01:15:05,860
Spørgsmål om, hvordan det rent faktisk
udretter det?

1562
01:15:05,860 --> 01:15:09,892

1563
01:15:09,892 --> 01:15:12,545
>> PUBLIKUM: Jeg har et spørgsmål
på [uhørligt].

1564
01:15:12,545 --> 01:15:15,090

1565
01:15:15,090 --> 01:15:23,550
>> ROB BOWDEN: Så en måde at nærme
enhver rekursive problem er bare at tænke

1566
01:15:23,550 --> 01:15:26,275
om det, som du nødt til at tænke
om alle de sager Corner.

1567
01:15:26,275 --> 01:15:32,150

1568
01:15:32,150 --> 01:15:38,110
Så mener, at vi ønsker at
udskrive hele dette træ.

1569
01:15:38,110 --> 01:15:42,030
Så alt vi kommer til at fokusere på
er netop denne node -

1570
01:15:42,030 --> 01:15:43,740
36..

1571
01:15:43,740 --> 01:15:47,420
De rekursive kald, vi lader
de bare arbejde.

1572
01:15:47,420 --> 01:15:54,000
Så her, denne rekursivt kald til
travers, vi uden at tænke

1573
01:15:54,000 --> 01:15:58,640
om det, bare gennemkører venstre
tre, forestille sig, at der allerede udskriver 20

1574
01:15:58,640 --> 01:16:00,730
og 34 for os.

1575
01:16:00,730 --> 01:16:03,350
Og så når vi til sidst rekursivt
call travers på

1576
01:16:03,350 --> 01:16:07,890
rigtigt, vil det korrekt udskrive
52, 59, og 106 for os.

1577
01:16:07,890 --> 01:16:13,620
>> Så da dette kan udskrive 20, 34, og
den anden kan udskrive 52, 59, 108,

1578
01:16:13,620 --> 01:16:17,180
alt, hvad vi nødt til at være i stand til at gøre, er at udskrive
os selv i midten af ​​det.

1579
01:16:17,180 --> 01:16:21,250
Så udskrive alt før os.

1580
01:16:21,250 --> 01:16:27,710
Print os selv, så den aktuelle node print
36, regelmæssig printf og derefter

1581
01:16:27,710 --> 01:16:31,170
udskrive alt efter os.

1582
01:16:31,170 --> 01:16:32,730
>> DAVID J. MALAN: Her rekursion
bliver virkelig smukke.

1583
01:16:32,730 --> 01:16:36,270
Det er denne fantastiske spring af tro, hvor
du gør den mindste smule arbejde.

1584
01:16:36,270 --> 01:16:38,460
Og så skal du lade en
ellers gøre resten.

1585
01:16:38,460 --> 01:16:40,180
Og at en anden
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 brownies punkter, hvis
du rulle op på spørgsmålene -

1588
01:16:48,360 --> 01:16:50,530
>> ROB BOWDEN: På spørgsmål?

1589
01:16:50,530 --> 01:16:53,490
>> DAVID J. MALAN: Og lidt ned for
tallene, er der nogen vide, hvor

1590
01:16:53,490 --> 01:16:55,190
disse tal kommer fra?

1591
01:16:55,190 --> 01:16:56,610
>> ROB BOWDEN: Jeg har bogstaveligt talt ingen idé.

1592
01:16:56,610 --> 01:16:59,794
>> DAVID J. MALAN: De vises
hele quizzen.

1593
01:16:59,794 --> 01:17:01,150
>> PUBLIKUM: Er de de samme numre?

1594
01:17:01,150 --> 01:17:01,910
>> DAVID J. MALAN: Disse tal.

1595
01:17:01,910 --> 01:17:03,260
En lille påskeæg.

1596
01:17:03,260 --> 01:17:08,100
Så for dem af jer ser online på
hjem, hvis du kan fortælle os via e-mail til

1597
01:17:08,100 --> 01:17:12,680
heads@CS50.net hvilken betydning
af disse tilbagevendende seks numre er

1598
01:17:12,680 --> 01:17:18,560
hele Quiz 1 vil vi bad dig
med forbløffende opmærksomhed på det sidste

1599
01:17:18,560 --> 01:17:21,610
foredrag og en stress bold.

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: Nogle sidste spørgsmål
om noget på quiz?

1603
01:17:29,570 --> 01:17:32,608