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

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

3
00:00:12,900 --> 00:00:16,790
Så välkommen till den första någonsin
CS50 obduktion för en frågesport.

4
00:00:16,790 --> 00:00:18,340
Vi trodde vi skulle inviga
denna tradition i år.

5
00:00:18,340 --> 00:00:20,960
Och detta kommer att bli ett tillfälle
att gå igenom

6
00:00:20,960 --> 00:00:22,220
lösningar på frågesport.

7
00:00:22,220 --> 00:00:26,160
Och vi kommer att påskynda eller sakta ner baserade
om intresse av dem här.

8
00:00:26,160 --> 00:00:29,730
>> Så du är förmodligen här för att du är
intresserad av hur du kan ha eller

9
00:00:29,730 --> 00:00:31,170
borde ha svarat något
av dessa problem.

10
00:00:31,170 --> 00:00:33,300
Så varför inte vi titta
i detta avsnitt först?

11
00:00:33,300 --> 00:00:34,450
Så få strängar.

12
00:00:34,450 --> 00:00:37,600
Detta gav dig tre olika versioner
av ett program, som var slutligen

13
00:00:37,600 --> 00:00:39,650
tänkt att få en sträng från en användare.

14
00:00:39,650 --> 00:00:42,530
Oavsett om det gjorde det var
lämnas till dig att avgöra.

15
00:00:42,530 --> 00:00:45,150
>> Och vi frågade i fråga 0,
Anta att version 1 är

16
00:00:45,150 --> 00:00:46,400
kompileras och exekveras.

17
00:00:46,400 --> 00:00:48,860
Varför skulle det program segfault?

18
00:00:48,860 --> 00:00:51,150
Vid första anblicken, några förslag
varför?

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

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

21
00:00:54,489 --> 00:00:59,260
>> PUBLIK: Jag minns att jag såg detta i
ett tidigare exempel på att titta på

22
00:00:59,260 --> 00:01:05,506
char * s och ser genomsökningen av s och
ser att det är en pekare, hur

23
00:01:05,506 --> 00:01:07,971
gjorde det påverka det du skannat in?

24
00:01:07,971 --> 00:01:10,940
Är det är eller adressen till s?

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

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

27
00:01:11,480 --> 00:01:14,830
Så i slutändan, källan till alla problem
är förmodligen kommer att minska

28
00:01:14,830 --> 00:01:16,210
till den variabeln s.

29
00:01:16,210 --> 00:01:17,280
Och det är verkligen en variabel.

30
00:01:17,280 --> 00:01:19,900
Datatypen för denna variabel är
char *, vilket innebär att det kommer att

31
00:01:19,900 --> 00:01:22,570
innehålla adressen till ett tecken.

32
00:01:22,570 --> 00:01:23,850
Och däri ligger insikten.

33
00:01:23,850 --> 00:01:28,330
Det kommer att innehålla adressen till
en art eller, mer allmänt,

34
00:01:28,330 --> 00:01:32,110
adressen för det första tecknet i
ett helt block av tecken.

35
00:01:32,110 --> 00:01:36,680
>> Men kruxet är att skanna s, syfte i
liv, ges en adress och ges

36
00:01:36,680 --> 00:01:40,960
ett format kod, som% s, läsa
en sträng i en stor bit av

37
00:01:40,960 --> 00:01:42,330
minne på den adressen.

38
00:01:42,330 --> 00:01:46,040
Men eftersom det inte finns något likhetstecken före
att semikolon på första

39
00:01:46,040 --> 00:01:49,310
kodrad, eftersom vi egentligen inte
allokera minne med

40
00:01:49,310 --> 00:01:53,020
malloc, eftersom det faktiskt inte
avsätta en matris av någon storlek, alla

41
00:01:53,020 --> 00:01:57,620
du gör är att läsa användarens
tangentbordsinmatning i en komplett

42
00:01:57,620 --> 00:02:00,490
skräp värde, vilket
är i s standard.

43
00:02:00,490 --> 00:02:04,480
Så oddsen är att du kommer att segfault om
den adressen är inte bara så råkar

44
00:02:04,480 --> 00:02:08,009
vara ett värde som du kan,
i själva verket, skriv till.

45
00:02:08,009 --> 00:02:10,889
Så dåligt att inte tilldela
ditt minne där.

46
00:02:10,889 --> 00:02:13,150
>> Så i fråga 1, frågade vi,
Anta att version 2 är

47
00:02:13,150 --> 00:02:14,230
kompileras och exekveras.

48
00:02:14,230 --> 00:02:15,900
Varför kan det här programmet segfault?

49
00:02:15,900 --> 00:02:17,990
Så den här är mindre buggig.

50
00:02:17,990 --> 00:02:21,470
Och det finns egentligen bara en
självklart sätt där du kan

51
00:02:21,470 --> 00:02:22,810
utlösa en segfault här.

52
00:02:22,810 --> 00:02:23,730
Och detta är tematiskt.

53
00:02:23,730 --> 00:02:28,180
Varje gång vi använder c i minnet, vad
kan du göra för att framkalla en segfault

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

55
00:02:30,718 --> 00:02:35,560
>> PUBLIK: Om du använder den ingången i
en sträng som är längre än 49

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

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

58
00:02:37,260 --> 00:02:41,420
Varje gång du ser något fast längd
när det kommer till en array, din

59
00:02:41,420 --> 00:02:44,650
radar ska gå av att detta kan vara
problematiskt om du inte kontrollerar

60
00:02:44,650 --> 00:02:45,810
Gränserna för en array.

61
00:02:45,810 --> 00:02:46,650
Och det är problemet här.

62
00:02:46,650 --> 00:02:47,910
Vi använder fortfarande scanf.

63
00:02:47,910 --> 00:02:52,200
Vi är fortfarande använder% s, vilket innebär att försöka
att läsa en sträng från användaren.

64
00:02:52,200 --> 00:02:56,300
Det kommer att läsas in i er, som,
vid denna punkt, är effektivt

65
00:02:56,300 --> 00:02:58,570
adressen för en bit av minnet
eller motsvarande.

66
00:02:58,570 --> 00:03:02,080
Det är namnet på en matris
tecken i minnet.

67
00:03:02,080 --> 00:03:07,610
>> Men just det, om du läser en sträng
som är längre än 49 tecken, 49

68
00:03:07,610 --> 00:03:10,440
eftersom du behöver utrymme för backslash
0, du kommer att svämma över

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

70
00:03:11,390 --> 00:03:16,410
Och du kan ha tur och kunna
skriver en 51: a karaktär, 52: a, 53: e.

71
00:03:16,410 --> 00:03:18,560
Men någon gång, OS
kommer att säga nej.

72
00:03:18,560 --> 00:03:21,270
Detta är definitivt inte minnet
du är tillåtet att röra vid.

73
00:03:21,270 --> 00:03:23,380
Och programmet kommer att segfault.

74
00:03:23,380 --> 00:03:26,650
>> Så det bör heuristik vara någon
tid du har fast längd, har du

75
00:03:26,650 --> 00:03:30,150
att se till att du kontrollerar längden
av vad det är du försöker

76
00:03:30,150 --> 00:03:31,090
att läsa in den.

77
00:03:31,090 --> 00:03:35,110
>> PUBLIK: Så för att lösa det, du kan
ha haft ett uttalande kontroll faktiskt

78
00:03:35,110 --> 00:03:37,140
är den längd som är större
eller mindre än?

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

80
00:03:37,730 --> 00:03:41,706
Du har bara ett villkor
som säger, om -

81
00:03:41,706 --> 00:03:46,080
eller snarare du inte nödvändigtvis vet
i förväg hur många tecken som den

82
00:03:46,080 --> 00:03:49,060
Användaren kommer att skriva, eftersom
du har hönan och ägget.

83
00:03:49,060 --> 00:03:51,860
Inte förrän du har läst den in med scanf
kan du räkna ut hur lång tid det är.

84
00:03:51,860 --> 00:03:54,500
Men på den punkten, det är för sent,
eftersom du redan har läst det i

85
00:03:54,500 --> 00:03:55,710
några block av minne.

86
00:03:55,710 --> 00:03:59,590
Så Inom parentes de CS50 biblioteks undviker
denna fråga helt och hållet, minns

87
00:03:59,590 --> 00:04:01,060
genom användning fgetc.

88
00:04:01,060 --> 00:04:05,390
Och den läser ett tecken i taget,
tip-toeing längs vet du att du

89
00:04:05,390 --> 00:04:08,060
kan inte spilla en karaktär om
man läser en i taget.

90
00:04:08,060 --> 00:04:11,580
>> Fångsten är med getString minns är
att vi hela tiden måste ändra storlek

91
00:04:11,580 --> 00:04:13,590
att bit av minnet, vilket
är bara en smärta.

92
00:04:13,590 --> 00:04:15,310
Det är en hel del rader
kod för att göra det.

93
00:04:15,310 --> 00:04:18,779
Så en annan lösning skulle vara att
använder faktiskt en kusin, så

94
00:04:18,779 --> 00:04:19,790
att tala, i scanf.

95
00:04:19,790 --> 00:04:22,820
Det finns varianter av en hel del av dessa
funktioner som faktiskt kontrollerar

96
00:04:22,820 --> 00:04:25,870
Längden på hur många tecken
du kan läsa maximalt.

97
00:04:25,870 --> 00:04:29,430
Och du kan ange, inte läser
mer än 50 tecken.

98
00:04:29,430 --> 00:04:34,110
Så det skulle vara ett annat tillvägagångssätt, men
mindre tillmötesgående av större ingångar.

99
00:04:34,110 --> 00:04:37,040
>> Så fråga 2 frågar, antar att version
3 kompileras och exekveras.

100
00:04:37,040 --> 00:04:39,960
Varför skulle det programmet segfault?

101
00:04:39,960 --> 00:04:42,650
Så den här är faktiskt samma
svara på, även om det

102
00:04:42,650 --> 00:04:43,590
ser lite snyggare.

103
00:04:43,590 --> 00:04:46,440
Vi använder malloc, vilket känns som
vi ger oss fler alternativ.

104
00:04:46,440 --> 00:04:48,030
Och sedan ska vi frigöra det
minne i slutet.

105
00:04:48,030 --> 00:04:49,580
Det är fortfarande bara 50 byte minne.

106
00:04:49,580 --> 00:04:53,620
Så vi kan fortfarande försöka läsa
i 51, 52, 1000 bytes.

107
00:04:53,620 --> 00:04:55,830
Det kommer att segfault för
exakt samma anledning.

108
00:04:55,830 --> 00:04:57,530
>> Men det finns en annan anledning också.

109
00:04:57,530 --> 00:05:03,890
Vad mer kan malloc avkastning förutom
adressen till en bit av minne?

110
00:05:03,890 --> 00:05:04,920
Det kan returnera null.

111
00:05:04,920 --> 00:05:07,560
Och eftersom vi inte kollar efter
det, skulle vi kunna göra något

112
00:05:07,560 --> 00:05:11,350
dumt av en annan anledning, nämligen att
Vi kan berätta scanf, läsa

113
00:05:11,350 --> 00:05:16,050
användarens input från tangentbordet
in 0 plats, AKA null.

114
00:05:16,050 --> 00:05:18,890
Och det också, kommer definitivt
utlösa en segfault.

115
00:05:18,890 --> 00:05:21,590
Så för frågesport syfte, vi skulle
har accepterat någon av dem som en

116
00:05:21,590 --> 00:05:22,740
giltigt skäl.

117
00:05:22,740 --> 00:05:23,420
En är identiska.

118
00:05:23,420 --> 00:05:25,720
Man är lite mer nyanserad.

119
00:05:25,720 --> 00:05:28,975
>> Slutligen, med avseende på programmets
användning av minne, hur gör version 2 och

120
00:05:28,975 --> 00:05:30,350
version 3 skiljer sig åt?

121
00:05:30,350 --> 00:05:35,070
Så för vad det är värt, såg vi en
till synes oändligt utbud av möjliga

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

123
00:05:35,770 --> 00:05:39,300
Och bland människors svar, vad vi var
hoppas på, men vi accepterade andra

124
00:05:39,300 --> 00:05:42,250
saker, var någon omnämnande av
faktum att version 2 använder

125
00:05:42,250 --> 00:05:44,560
den så kallade stacken.

126
00:05:44,560 --> 00:05:46,710
Version 3 använder heap.

127
00:05:46,710 --> 00:05:50,060
Och funktionellt, gör detta inte riktigt
göra så mycket av en skillnad.

128
00:05:50,060 --> 00:05:54,040
Vid slutet av dagen, vi är fortfarande
bara få 50 byte minne.

129
00:05:54,040 --> 00:05:56,640
>> Men det var en av de möjliga svaren
att vi undersöker.

130
00:05:56,640 --> 00:05:59,730
Men du ser, som du får dina frågesporter
tillbaka från TF, att vi gjorde

131
00:05:59,730 --> 00:06:04,330
acceptera andra diskussioner om deras
skilda användningar av minne också.

132
00:06:04,330 --> 00:06:08,600
Men stack och heap skulle ha varit
ett enkelt svar för att gå med.

133
00:06:08,600 --> 00:06:11,150
Några frågor?

134
00:06:11,150 --> 00:06:12,400
Jag ger dig Rob.

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

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

137
00:06:20,210 --> 00:06:21,985
Det är det där du var tvungen att fylla
av antalet bytes av alla

138
00:06:21,985 --> 00:06:23,460
dessa olika typer används.

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

140
00:06:24,830 --> 00:06:27,930
Antag en 32-bitars arkitektur,
som den här CS50 apparat.

141
00:06:27,930 --> 00:06:33,530
Så en av de grundläggande sakerna
32-bitars arkitekturer, berättar att

142
00:06:33,530 --> 00:06:37,490
exakt hur stor en pekare kommer
att vara i arkitekturen.

143
00:06:37,490 --> 00:06:43,020
>> Så omedelbart, vi vet att alla pekare
typ är 32-bits eller 4 byte.

144
00:06:43,020 --> 00:06:46,010
Så titta på denna tabell, en
nod * är en pekare typ.

145
00:06:46,010 --> 00:06:47,250
Det kommer att vara 4 byte.

146
00:06:47,250 --> 00:06:51,640
Struct node *, det är bokstavligt talat
identisk med noden stjärna.

147
00:06:51,640 --> 00:06:53,590
Och så det kommer att bli 4 byte.

148
00:06:53,590 --> 00:06:58,270
String, så det inte ser ut som en
pekaren ännu, men typedef, en

149
00:06:58,270 --> 00:07:01,590
strängen är bara en char *, som
är en pekare typ.

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

151
00:07:03,550 --> 00:07:06,150
>> Så dessa tre är alla 4 byte.

152
00:07:06,150 --> 00:07:09,350
Nu, nod och elev är
lite mer komplicerat.

153
00:07:09,350 --> 00:07:15,160
Så titta på nod och student, ser vi
noden som ett heltal och en pekare.

154
00:07:15,160 --> 00:07:18,050
Och eleven är två pekare
inne i den.

155
00:07:18,050 --> 00:07:23,340
Så åtminstone för vårt fall här, vägen
att vi hamnar beräkna storleken på

156
00:07:23,340 --> 00:07:27,020
denna struct är bara lägga upp allt
som är inne i struct.

157
00:07:27,020 --> 00:07:30,690
>> Så för nod, har vi ett heltal,
vilket är fyra byte.

158
00:07:30,690 --> 00:07:32,830
Vi har en pekare, som är fyra byte.

159
00:07:32,830 --> 00:07:35,820
Och så en nod går
att ta upp åtta byte.

160
00:07:35,820 --> 00:07:39,490
Och på samma sätt för eleven, vi har en
pekare som är 4 byte och annat

161
00:07:39,490 --> 00:07:40,770
pekare som är 4 byte.

162
00:07:40,770 --> 00:07:43,180
Så det kommer att sluta
upp att vara 8 byte.

163
00:07:43,180 --> 00:07:45,480
Så nod och elev är 8 byte.

164
00:07:45,480 --> 00:07:48,950
Och dessa tre är alla 4 byte.

165
00:07:48,950 --> 00:07:50,240
Frågor på 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
>> Publik: Är det var en 64-bitars
arkitektur, skulle det

169
00:07:58,413 --> 00:07:59,880
fördubbla dem alla?

170
00:07:59,880 --> 00:08:01,790
>> ROB BOWDEN: Det skulle inte
fördubbla dem.

171
00:08:01,790 --> 00:08:05,830
Så 64-bitars arkitektur, det, återigen,
förändringar som grundläggande sak som en

172
00:08:05,830 --> 00:08:08,910
Pekaren är nu 64 bitar.

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

174
00:08:09,290 --> 00:08:10,930
Så en pekare är 8 byte.

175
00:08:10,930 --> 00:08:15,420
Så dessa som var 4 byte
kommer att vara 8 byte.

176
00:08:15,420 --> 00:08:18,617
En student, som var två pekare,
bra, nu det kommer att

177
00:08:18,617 --> 00:08:19,800
vara 8 byte, 8 byte.

178
00:08:19,800 --> 00:08:21,980
Det kommer att göra 16 byte.

179
00:08:21,980 --> 00:08:25,710
>> Men en nod är fortfarande fyra bitgrupper.

180
00:08:25,710 --> 00:08:27,800
Så här pekaren går
vara 8 byte.

181
00:08:27,800 --> 00:08:28,930
Detta är fyra byte.

182
00:08:28,930 --> 00:08:30,870
Så en nod kommer bara
att vara 12 byte.

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

184
00:08:36,309 --> 00:08:39,280
Alla andra frågor om den?

185
00:08:39,280 --> 00:08:44,500
Så nästa, dessa är
HTTP-statuskoder.

186
00:08:44,500 --> 00:08:48,000
Och du var tvungen att beskriva omständigheter
under vilka dessa kan

187
00:08:48,000 --> 00:08:49,810
tillbaka till dig.

188
00:08:49,810 --> 00:08:56,730
ett problem som jag hörde några studenter
har är att de försökt göra

189
00:08:56,730 --> 00:08:58,950
fel att vara på kundens slut.

190
00:08:58,950 --> 00:09:02,320
Så när vi försöker göra begäran
till servern, går något

191
00:09:02,320 --> 00:09:03,820
fel på vår ände.

192
00:09:03,820 --> 00:09:07,660
Men generellt är dessa koder
som returneras av servern.

193
00:09:07,660 --> 00:09:11,720
Så vi vill ta reda på vad som händer
rätt eller fel på servern som

194
00:09:11,720 --> 00:09:14,280
orsakar dessa saker som ska returneras.

195
00:09:14,280 --> 00:09:18,670
Så varför kan en server åter
statuskod 200?

196
00:09:18,670 --> 00:09:19,920
Några tankar?

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

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

199
00:09:23,730 --> 00:09:27,850
Så något om framgång
ansökan gick igenom.

200
00:09:27,850 --> 00:09:30,260
Och de är kan återvända
vad du bad om.

201
00:09:30,260 --> 00:09:32,240
Så allt var bra.

202
00:09:32,240 --> 00:09:35,662
Vad sägs om 302 hittade?

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

204
00:09:36,618 --> 00:09:39,008
>> PUBLIK: Servern var ute
för vad du begärt.

205
00:09:39,008 --> 00:09:40,442
Men det kunde inte hitta den.

206
00:09:40,442 --> 00:09:42,850
Så det finns ett fel.

207
00:09:42,850 --> 00:09:47,720
>> ROB BOWDEN: Så servern var
letar efter vad du ville ha.

208
00:09:47,720 --> 00:09:51,682
Så bara titta här, 302 hittade,
den kunde hitta den.

209
00:09:51,682 --> 00:09:53,035
>> PUBLIK: Jag är ledsen.

210
00:09:53,035 --> 00:09:54,388
Hittade innebär att de hittade den.

211
00:09:54,388 --> 00:09:55,638
Ursäkta.

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

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

214
00:10:00,160 --> 00:10:02,350
Servern kan hitta
vad du ville.

215
00:10:02,350 --> 00:10:04,640
>> PUBLIK: Men det är inte att visa det?

216
00:10:04,640 --> 00:10:08,180
>> ROB BOWDEN: Skillnaden mellan
denna 302 och 200 är att det

217
00:10:08,180 --> 00:10:09,280
vet vad du vill.

218
00:10:09,280 --> 00:10:12,000
Men det är inte precis där
du ville fråga.

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

220
00:10:14,580 --> 00:10:16,510
Så du begärt en sida.

221
00:10:16,510 --> 00:10:19,590
Den vet, åh, jag vill ha
att återvända dig här.

222
00:10:19,590 --> 00:10:21,070
Men det är på en annan webbadress.

223
00:10:21,070 --> 00:10:23,534
Så hey, du verkligen vill detta.

224
00:10:23,534 --> 00:10:26,950
>> DAVID J. MALAN: Det är en pjäs som sagt
att vi gav er en omdirigering

225
00:10:26,950 --> 00:10:30,830
funktion som används rubrik funktion
som i sin tur skrivas ut plats,

226
00:10:30,830 --> 00:10:34,110
kolon, och sedan den URL som
du vill avvisa användaren.

227
00:10:34,110 --> 00:10:37,480
Även om du inte såg 302
uttryckligen det, är det vad PHP

228
00:10:37,480 --> 00:10:41,550
skulle magiskt sätt in som rubrik
att säga exakt vad Rob sade att det -

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

230
00:10:41,930 --> 00:10:43,180
Men gå här istället.

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å hur är 403 förbjudna?

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

235
00:10:52,240 --> 00:10:57,120
>> PUBLIK: Jag tycker det är att servern
är i princip säger att klienten

236
00:10:57,120 --> 00:10:59,970
kan inte komma åt hemsidan.

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

238
00:11:03,260 --> 00:11:07,670
Tja, det typiska svaret var vi
förväntar sig något liknande, filerna

239
00:11:07,670 --> 00:11:08,920
inte chmodded lämpligt sätt.

240
00:11:08,920 --> 00:11:11,590
Det är antagligen under vilka omständigheter
du såg dem.

241
00:11:11,590 --> 00:11:18,920
Men det finns en anledning till att kunden
kan vara fel här.

242
00:11:18,920 --> 00:11:20,440
Det finns faktiskt en annan statuskod -

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

244
00:11:21,210 --> 00:11:22,820
Så dessa är mycket lika.

245
00:11:22,820 --> 00:11:24,590
>> 401 är otillåten.

246
00:11:24,590 --> 00:11:26,130
Och 403 är förbjudet.

247
00:11:26,130 --> 00:11:31,890
Och så obehöriga att du enbart
få om du inte är inloggad i.

248
00:11:31,890 --> 00:11:34,520
Men att logga in kan betyda
att du är behörig.

249
00:11:34,520 --> 00:11:37,930
Men om du redan är inloggad och du
fortfarande har inte behörighet, sedan

250
00:11:37,930 --> 00:11:40,140
du kan också få förbjudna.

251
00:11:40,140 --> 00:11:45,320
Så om du är inloggad och inte har
tillåtelse, är förbjudet också

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

253
00:11:47,164 --> 00:11:48,900
>> DAVID J. MALAN: Och den mekanism genom
vilket dessa problem är vanligtvis

254
00:11:48,900 --> 00:11:53,100
löst på servern är
via vilken kommando?

255
00:11:53,100 --> 00:11:57,700
Chmod, om det är verkligen en behörigheter
utfärda på filen eller katalogen.

256
00:11:57,700 --> 00:11:59,220
>> ROB BOWDEN: Sedan 404 hittades inte.

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

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

259
00:12:03,470 --> 00:12:10,150
Så till skillnad från 302 där det var inte precis
där du frågar, men det vet vad

260
00:12:10,150 --> 00:12:12,710
du vill, det här, bara har det
ingen aning om vad du vill.

261
00:12:12,710 --> 00:12:15,648
Och du inte begär
något giltigt.

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

263
00:12:18,580 --> 00:12:22,310
418 Jag är en tekanna och sedan
500 intern server.

264
00:12:22,310 --> 00:12:24,870
Så varför skulle du 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
Jag vet faktiskt inte graderingen
standard för detta.

268
00:12:30,640 --> 00:12:34,850
Men om din PHP-kod hade något
fel i det, i teorin, kan det

269
00:12:34,850 --> 00:12:39,650
faktiskt segfault, i vilket fall detta
500 internt serverfel, något

270
00:12:39,650 --> 00:12:41,400
är fel med din servers
konfiguration.

271
00:12:41,400 --> 00:12:44,320
Eller det finns ett syntaxfel
i din PHP-kod.

272
00:12:44,320 --> 00:12:46,095
Eller något hemskt är på gång.

273
00:12:46,095 --> 00:12:48,320
>> DAVID J. MALAN: Vi såg segfault
bland några människors svar.

274
00:12:48,320 --> 00:12:49,490
Och tekniskt sett, kan det hända.

275
00:12:49,490 --> 00:12:53,820
Men det skulle vara ett PHP, programmet
skrivna av andra människor, faktiskt

276
00:12:53,820 --> 00:12:57,790
segfaulted, vilket endast om dessa personer
skruvas upp och skrev buggig kod i

277
00:12:57,790 --> 00:13:00,680
deras tolk skulle
PHP i sig segfault.

278
00:13:00,680 --> 00:13:06,460
Så även om 500 är som en segfault
i anden, är det nästan alltid den

279
00:13:06,460 --> 00:13:10,490
Resultatet av en konfigurationsfil fråga
med din webbserver eller, som Rob sa,

280
00:13:10,490 --> 00:13:13,200
ett syntaxfel, som du
inte stänga en offert.

281
00:13:13,200 --> 00:13:16,180
Eller du förlorat ett semikolon någonstans.

282
00:13:16,180 --> 00:13:23,677
>> PUBLIK: Så för Shuttle pset, jag
tänker när jag gjorde det när jag klickade på

283
00:13:23,677 --> 00:13:26,300
browser, men ingenting kom upp,
vad de kallade vit sida.

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

285
00:13:28,056 --> 00:13:29,440
Jag tror att det var JavaScript, eller hur?

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

287
00:13:29,770 --> 00:13:31,180
>> PUBLIK: Skulle felet
fortfarande komma upp?

288
00:13:31,180 --> 00:13:34,290
>> ROB BOWDEN: Så du skulle inte ha fått
detta fel eftersom allt

289
00:13:34,290 --> 00:13:36,930
från webbservern perspektiv
var helt bra.

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

291
00:13:39,090 --> 00:13:42,000
Du begärde shuttle.js
och service.js.

292
00:13:42,000 --> 00:13:44,580
Och det kunde framgångsrikt återvända
till er alla dessa saker -

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 är bara när webbläsaren försökte
tolka JavaScript-kod som

296
00:13:49,330 --> 00:13:51,370
det är som att, vänta, det är inte
giltiga JavaScript-fel.

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

298
00:13:55,720 --> 00:13:58,210
Fler frågor?

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

300
00:14:00,750 --> 00:14:04,120
>> DAVID J. MALAN: Så nästa
upp var nummer 11.

301
00:14:04,120 --> 00:14:07,610
Och 11 var den mest skrämmande
för många människor.

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

303
00:14:14,620 --> 00:14:18,570
Så det viktigaste att notera här
var att detta var, sannerligen, om

304
00:14:18,570 --> 00:14:19,840
en dubbelt länkad lista.

305
00:14:19,840 --> 00:14:23,160
Men det var inte samma som förra årets
dubbelt länkad lista problem,

306
00:14:23,160 --> 00:14:27,170
vilket inte gav dig det förbehållet att
listan kan faktiskt vara osorterat.

307
00:14:27,170 --> 00:14:29,640
>> Så det faktum att listan var osorterat
och det faktum att det ordet var

308
00:14:29,640 --> 00:14:32,930
struken det var tänkt att förmedla
att detta faktiskt är en förenkling

309
00:14:32,930 --> 00:14:35,430
av vad som annars skulle ha varit
en mer utmanande problem

310
00:14:35,430 --> 00:14:36,600
och en längre.

311
00:14:36,600 --> 00:14:40,760
Så ett vanligt misstag här var att ha lagt
förra årets lösning på en

312
00:14:40,760 --> 00:14:45,580
personsökare och sedan bara blint kopiera den
ner som svar, vilket är rätt

313
00:14:45,580 --> 00:14:48,520
svara på en annan fråga
liknande anda.

314
00:14:48,520 --> 00:14:51,340
Men subtiliteter här
var följande.

315
00:14:51,340 --> 00:14:55,200
>> Så en, vi har en nod deklarerat och
definieras på det vanliga sättet här.

316
00:14:55,200 --> 00:14:59,230
Sedan definierade vi listan med en global
pekare initieras till null.

317
00:14:59,230 --> 00:15:02,150
Sen tydligen finns det två funktioner
Vi har prototyper till här, insats

318
00:15:02,150 --> 00:15:03,240
och ta bort.

319
00:15:03,240 --> 00:15:06,600
Och sedan har vi några exempelkod här
att göra en massa insättningar.

320
00:15:06,600 --> 00:15:09,930
Och så ber vi dig att fylla i
genomförande av insatsen nedan i sådan

321
00:15:09,930 --> 00:15:14,380
sätt att den infogar n in i listan
i konstant tid, underströk också,

322
00:15:14,380 --> 00:15:15,730
även om den redan är närvarande.

323
00:15:15,730 --> 00:15:20,600
>> Så skönheten i att kunna sätta in
i konstant tid är att det innebär

324
00:15:20,600 --> 00:15:23,060
att du måste sätta in
den nya noden där?

325
00:15:23,060 --> 00:15:23,690
Into the front.

326
00:15:23,690 --> 00:15:27,760
Så det eliminerar, tack och lov, åtminstone
en av de ärenden som tidigare krävde

327
00:15:27,760 --> 00:15:30,520
ännu fler rader kod, som det gjorde
förra året och även i klassen när vi

328
00:15:30,520 --> 00:15:34,040
pratat igenom sånt
med människor och med viss

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

330
00:15:35,250 --> 00:15:39,190
Så i lösningen här, låt oss hoppa över
till att bara ha en visuellt på

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

332
00:15:40,480 --> 00:15:42,230
>> Lägg märke till att vi gör följande.

333
00:15:42,230 --> 00:15:45,140
Och också att märka den andra förenklingar
var att även om det är

334
00:15:45,140 --> 00:15:48,280
redan finns, så det betyder även om
numret är redan där, du kan

335
00:15:48,280 --> 00:15:50,280
bara blint sätta in en annan
kopia av den.

336
00:15:50,280 --> 00:15:52,560
Och det också var tänkt att vara en
förenkling, så att du kan

337
00:15:52,560 --> 00:15:54,940
fokusera på, egentligen, några av de mer
intellektuellt intressant del och

338
00:15:54,940 --> 00:15:58,090
inte bara några extra felkontroll
med tanke på den begränsade tid.

339
00:15:58,090 --> 00:16:02,880
>> Så i denna provlösning, vi fördela
en pekare på vänster

340
00:16:02,880 --> 00:16:04,510
sida här till en nod.

341
00:16:04,510 --> 00:16:07,190
Nu, inser att pekare, som
Rob säger, är bara 32 bitar.

342
00:16:07,190 --> 00:16:09,060
Och det behöver inte faktiskt innehåller
en adress tills du

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

344
00:16:09,970 --> 00:16:13,220
Och vi gör det på den högra
sida via malloc.

345
00:16:13,220 --> 00:16:16,550
Som en god medborgare, kontrollerar vi att
malloc inte, i själva verket, null, så att

346
00:16:16,550 --> 00:16:18,690
vi inte av misstag skapa
en segfault här.

347
00:16:18,690 --> 00:16:22,840
Och varje gång du använder malloc i livet, du
ska kolla efter null, lest

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

349
00:16:24,090 --> 00:16:28,460
>> Då initiera vi att noll genom
tilldela n och tidigare och nästa.

350
00:16:28,460 --> 00:16:32,450
Och i det här fallet, jag initieras
tidigare till noll, eftersom det nya

351
00:16:32,450 --> 00:16:34,780
nod kommer att bli den nya
början på min lista.

352
00:16:34,780 --> 00:16:37,050
Så det kommer att bli
ingenting innan.

353
00:16:37,050 --> 00:16:42,010
Och jag vill i huvudsak bifoga
befintlig lista till den nya noden med

354
00:16:42,010 --> 00:16:44,700
inställningen nästa lika att lista sig.

355
00:16:44,700 --> 00:16:47,120
Men jag är inte klar ännu.

356
00:16:47,120 --> 00:16:51,780
Så om själva listan redan fanns,
och det fanns minst en nod

357
00:16:51,780 --> 00:16:57,070
redan finns på plats, om detta är den lista
här och jag sätter in en ny nod här, jag

358
00:16:57,070 --> 00:17:01,840
måste se till att min tidigare nod
pekar bakåt till min nya noden,

359
00:17:01,840 --> 00:17:04,260
eftersom detta är, återigen,
en dubbelt länkad lista.

360
00:17:04,260 --> 00:17:05,460
>> Så vi gör en sundhetskontroll.

361
00:17:05,460 --> 00:17:10,109
Om listan inte är noll, om det finns redan
en eller flera noder där, då

362
00:17:10,109 --> 00:17:12,470
tillägga att tillbaka referens så att säga.

363
00:17:12,470 --> 00:17:15,420
Och sedan det allra sista vi behöver
göra är att faktiskt uppdatera den globala

364
00:17:15,420 --> 00:17:20,329
variabel lista sig till punkt
till den nya noden.

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

366
00:17:21,790 --> 00:17:26,579
>> PUBLIK: I Pilpekaren
[OHÖRBAR] är lika med noll, gör att

367
00:17:26,579 --> 00:17:30,420
hantera listan eftersom
listan är noll?

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

369
00:17:30,596 --> 00:17:34,500
Det är helt enkelt att jag är proaktivt
försiktig, i det att om detta är mitt

370
00:17:34,500 --> 00:17:38,730
ursprungliga listan med kanske några fler noder
hit och jag sätter i mitt

371
00:17:38,730 --> 00:17:42,380
nya noden över här, har det gå
att vara något över här.

372
00:17:42,380 --> 00:17:44,720
Och jag vill fånga den idén
genom att ställa in tidigare till

373
00:17:44,720 --> 00:17:47,740
null om den nya noden.

374
00:17:47,740 --> 00:17:51,410
Och förmodligen, om min kod är korrekt
och det finns inget annat sätt att infoga

375
00:17:51,410 --> 00:17:54,970
andra än denna funktion noder,
förmodligen, redan har, även om listan

376
00:17:54,970 --> 00:18:00,090
en eller flera noder i det, förmodligen den
lista, den första noden, skulle ha en

377
00:18:00,090 --> 00:18:02,750
tidigare pekare av null själv.

378
00:18:02,750 --> 00:18:03,550
>> PUBLIK: Och bara en uppföljning.

379
00:18:03,550 --> 00:18:08,139
Anledningen till att du sätter pekaren nästa jämlikar
Listan är du gör pekaren

380
00:18:08,139 --> 00:18:13,579
innan listan i att den pekar
till nästa, antar jag -

381
00:18:13,579 --> 00:18:14,980
Jag inte -

382
00:18:14,980 --> 00:18:15,450
bara listar?

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

384
00:18:16,400 --> 00:18:19,400
Och så låt oss faktiskt överväga två fall
här egentligen, även om

385
00:18:19,400 --> 00:18:22,070
För vi ska betrakta dem är inte
riktigt samma som koden.

386
00:18:22,070 --> 00:18:26,250
Men på en hög nivå, om detta utgör
listan och detta är en 32-bitars

387
00:18:26,250 --> 00:18:29,560
pekare, är det enklaste scenariot
att detta är null som standard.

388
00:18:29,560 --> 00:18:33,010
Och antar att jag vill infoga
nummer 50 var det första numret.

389
00:18:33,010 --> 00:18:37,640
Så jag ska gå vidare och fördela
en nod, som kommer att innehålla

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

391
00:18:38,770 --> 00:18:42,070
n tidigare, och nästa.

392
00:18:42,070 --> 00:18:44,580
>> Jag kommer att sätta nummer 50
här, eftersom detta kommer att bli n.

393
00:18:44,580 --> 00:18:46,130
Detta kommer att bli nästa.

394
00:18:46,130 --> 00:18:48,530
Och detta kommer att bli tidigare.

395
00:18:48,530 --> 00:18:50,910
Och så vad gör jag i det här fallet?

396
00:18:50,910 --> 00:18:53,900
Tja, jag har precis gjort linje 1 här.

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

398
00:18:55,400 --> 00:18:57,740
Jag då säger, tidigare
borde bli null.

399
00:18:57,740 --> 00:18:59,470
Så det här kommer att bli noll.

400
00:18:59,470 --> 00:19:01,365
Då ska jag säga nästa
kommer att få listan.

401
00:19:01,365 --> 00:19:05,150
>> Och detta bara fungerar bra.

402
00:19:05,150 --> 00:19:06,500
Detta är null.

403
00:19:06,500 --> 00:19:10,620
Och så jag säger, den nya noden nästa
område bör få vad detta är.

404
00:19:10,620 --> 00:19:12,570
Så det sätter en annan null där.

405
00:19:12,570 --> 00:19:14,510
Och sedan det sista
Jag är kolla här.

406
00:19:14,510 --> 00:19:17,870
Om listan inte är lika med noll, men det
är lika med noll, så vi hoppar över att

407
00:19:17,870 --> 00:19:18,470
helt och hållet.

408
00:19:18,470 --> 00:19:23,520
Och så allt jag gör härnäst är listan blir
pekare, som bildmässigt resulterar i

409
00:19:23,520 --> 00:19:25,570
en bild så.

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

411
00:19:26,620 --> 00:19:30,490
>> Och det som du frågade om
specifikt är en situation som denna,

412
00:19:30,490 --> 00:19:33,190
där vi redan har en en-nod lista.

413
00:19:33,190 --> 00:19:36,240
Och om jag går tillbaka upp i den ursprungliga
problemformuleringen, nästa vi kommer

414
00:19:36,240 --> 00:19:39,320
infoga säga är 34, bara för
skull diskussionen.

415
00:19:39,320 --> 00:19:46,210
Så jag ska bara bekvämt
rita det här borta.

416
00:19:46,210 --> 00:19:47,540
Jag har precis malloced.

417
00:19:47,540 --> 00:19:49,310
Låt oss anta att jag kollar på null.

418
00:19:49,310 --> 00:19:51,870
>> Nu ska jag initiera
n att vara 34.

419
00:19:51,870 --> 00:19:53,040
Och detta kommer att bli n.

420
00:19:53,040 --> 00:19:54,670
Detta kommer att bli nästa.

421
00:19:54,670 --> 00:19:57,100
Och detta kommer att bli tidigare.

422
00:19:57,100 --> 00:19:59,370
Låt oss se till att jag inte gjorde det
få detta bakåt.

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

424
00:20:01,110 --> 00:20:03,070
Jag löser det här.

425
00:20:03,070 --> 00:20:04,410
Detta är tidigare.

426
00:20:04,410 --> 00:20:05,780
Det här är nästa.

427
00:20:05,780 --> 00:20:08,620
Även om dessa är identiska,
låt oss hålla det konsekvent.

428
00:20:08,620 --> 00:20:09,450
>> Föregående.

429
00:20:09,450 --> 00:20:11,030
Det här är nästa.

430
00:20:11,030 --> 00:20:16,310
Så jag har bara malloced min anmärkning, kontrolleras
för null, tilldelade 34 in i noden.

431
00:20:16,310 --> 00:20:17,570
Föregående blir null.

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

433
00:20:19,480 --> 00:20:21,010
Nästa blir listan.

434
00:20:21,010 --> 00:20:22,370
Så listan är detta.

435
00:20:22,370 --> 00:20:26,520
Så det är samma nu som att dra detta
arrow, så att de pekar på en

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

437
00:20:27,940 --> 00:20:30,400
Och sedan jag kontrollera om listan
inte är lika med noll.

438
00:20:30,400 --> 00:20:31,740
Och det är inte den här gången.

439
00:20:31,740 --> 00:20:35,580
Sen kommer jag att göra-lista
tidigare får pekaren.

440
00:20:35,580 --> 00:20:39,700
>> Så lista tidigare blir PTR.

441
00:20:39,700 --> 00:20:44,300
Så det här har effekten av att lägga
en grafisk pil här.

442
00:20:44,300 --> 00:20:46,930
Och det börjar bli lite
vågig, raderna.

443
00:20:46,930 --> 00:20:50,780
Och sedan, slutligen, uppdatera jag
lista för att peka på pekare.

444
00:20:50,780 --> 00:20:55,560
Så nu detta pekar på den här killen.

445
00:20:55,560 --> 00:20:57,170
Och nu, låt oss göra en snabb
sundhetskontroll.

446
00:20:57,170 --> 00:20:59,470
>> Här är listan, vilket är
den globala variabeln.

447
00:20:59,470 --> 00:21:02,850
Den första noden är, faktiskt, 34, eftersom
Jag följer den pilen.

448
00:21:02,850 --> 00:21:05,210
Och det är rätt att jag vill
sätt in i början av listan

449
00:21:05,210 --> 00:21:06,070
alla nya noder.

450
00:21:06,070 --> 00:21:08,860
Hans nästa fält leder mig till den här killen.

451
00:21:08,860 --> 00:21:10,710
Om jag fortsätter att gå, jag slog nästa är null.

452
00:21:10,710 --> 00:21:11,760
Så det finns ingen mer lista.

453
00:21:11,760 --> 00:21:14,460
Om jag träffade tidigare, får jag
tillbaka där jag förväntar mig.

454
00:21:14,460 --> 00:21:16,435
>> Så det finns fortfarande några tips,
uppenbarligen, att manipulera.

455
00:21:16,435 --> 00:21:19,870
Men det faktum att du fick höra att göra
detta i konstant tid innebär att du bara

456
00:21:19,870 --> 00:21:22,910
har ett ändligt antal saker
du är tillåtet att göra.

457
00:21:22,910 --> 00:21:24,290
Och vad är det numret?

458
00:21:24,290 --> 00:21:25,185
Det kan vara ett steg.

459
00:21:25,185 --> 00:21:25,700
Det kan vara två.

460
00:21:25,700 --> 00:21:26,820
Det kan vara 1.000 steg.

461
00:21:26,820 --> 00:21:30,500
Men det är ändlig, vilket innebär att du inte kan
har någon form av looping pågår

462
00:21:30,500 --> 00:21:32,010
här, ingen rekursion, inga loopar.

463
00:21:32,010 --> 00:21:37,390
Det bara måste vara hårdkodade linjer
av kod som vi har i detta prov.

464
00:21:37,390 --> 00:21:42,330
>> Så nästa problem 12 bad oss
slutföra genomförandet av remove

465
00:21:42,330 --> 00:21:46,740
nedan på ett sådant sätt att den tar bort
n från listan i linjär tid.

466
00:21:46,740 --> 00:21:48,740
Så du har lite mer
wigglerum nu.

467
00:21:48,740 --> 00:21:52,380
Du kan anta att n, om den finns
i listan, kommer att närvara

468
00:21:52,380 --> 00:21:53,340
inte mer än en gång.

469
00:21:53,340 --> 00:21:56,770
Och som också är tänkt att vara en frågesport-baserad
förenklande antagandet, så

470
00:21:56,770 --> 00:21:59,780
att om du hittar nummer 50 någonstans
i listan, behöver du inte också

471
00:21:59,780 --> 00:22:02,890
behöver oroa sig för att fortsätta
iterera, letar efter alla möjliga

472
00:22:02,890 --> 00:22:06,990
kopia av 50, vilket bara skulle överlåta
i någon minutiae i begränsad tid.

473
00:22:06,990 --> 00:22:10,460
>> Så med ta bort, den här var definitivt
mer utmanande och mer

474
00:22:10,460 --> 00:22:11,640
kod för att skriva.

475
00:22:11,640 --> 00:22:14,990
Men vid första anblicken, ärligt talat, kan det
ser överväldigande och som något

476
00:22:14,990 --> 00:22:17,060
det finns inget sätt du kan få
komma med på en frågesport.

477
00:22:17,060 --> 00:22:22,450
Men om vi fokuserar på de enskilda stegen,
Förhoppningsvis kommer det plötsligt

478
00:22:22,450 --> 00:22:26,060
slå dig om att var och en av dessa individuella
steg gör uppenbara mening

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

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

481
00:22:28,200 --> 00:22:32,570
>> Så först, initiera vi pekare
vara själva listan.

482
00:22:32,570 --> 00:22:36,040
Eftersom jag vill ha linjär tid, det betyder
Jag kommer att ha en viss slinga.

483
00:22:36,040 --> 00:22:39,730
Och ett vanligt sätt att iterera över
noder i en liststruktur eller någon form

484
00:22:39,730 --> 00:22:43,860
med strukturen iterativt är att ta
en pekare till den främre delen av den registrerade

485
00:22:43,860 --> 00:22:46,990
struktur och sedan bara börja uppdatera
det och gå din väg

486
00:22:46,990 --> 00:22:48,650
genom datastrukturen.

487
00:22:48,650 --> 00:22:50,040
Så jag kommer att göra just det.

488
00:22:50,040 --> 00:22:54,260
>> Medan pekare, min tillfälliga variabel,
inte är lika med noll, låt oss

489
00:22:54,260 --> 00:22:55,660
gå vidare och kolla.

490
00:22:55,660 --> 00:22:56,910
Fick jag lycklig?

491
00:22:56,910 --> 00:23:01,740
Är det n fältet i noden är jag idag
tittar på lika med

492
00:23:01,740 --> 00:23:03,380
nummer jag letar efter?

493
00:23:03,380 --> 00:23:05,410
Och i så fall, låt oss göra något.

494
00:23:05,410 --> 00:23:10,020
Nu märker detta om villkor
omger hela

495
00:23:10,020 --> 00:23:11,520
Följande kodrader.

496
00:23:11,520 --> 00:23:14,610
Detta är det enda jag bryr mig om -
att hitta en rad i fråga.

497
00:23:14,610 --> 00:23:18,010
Så det finns ingen annanstans, vilket förenklar
saker begrepps lite.

498
00:23:18,010 --> 00:23:22,040
>> Men nu insåg jag, och du kan ha
bara insåg detta efter att ha tänkt

499
00:23:22,040 --> 00:23:24,720
det genom en bit, det finns
faktiskt två fall här.

500
00:23:24,720 --> 00:23:28,060
En är där noden är vid
början av listan, vilket är en

501
00:23:28,060 --> 00:23:31,040
lite irriterande, eftersom det är en
specialfall, eftersom du måste ta itu

502
00:23:31,040 --> 00:23:33,340
med denna sak, som
är den enda anomali.

503
00:23:33,340 --> 00:23:35,720
Överallt annars i listan,
det är samma sak.

504
00:23:35,720 --> 00:23:38,050
Det finns en tidigare nod och ett nästa
nod, tidigare nod, nästa nod.

505
00:23:38,050 --> 00:23:40,940
Men den här killen är lite speciell
om han är i början.

506
00:23:40,940 --> 00:23:48,710
>> Så om pekaren är lika listan
sig själv, så om jag är i början av

507
00:23:48,710 --> 00:23:53,960
listan och jag har hittat n, jag behöver
att göra ett par saker.

508
00:23:53,960 --> 00:23:59,230
Man, jag behöver ändra listan till
pekar på det nästkommande fältet, 50.

509
00:23:59,230 --> 00:24:01,270
Så antar att jag försöker
för att ta bort 34.

510
00:24:01,270 --> 00:24:03,560
Så den här killen fick gå
bort på bara ett ögonblick.

511
00:24:03,560 --> 00:24:07,210
>> Så jag ska säga, lista
blir pekaren nästa.

512
00:24:07,210 --> 00:24:08,570
Nåväl, detta är pekare.

513
00:24:08,570 --> 00:24:10,360
Nästa pekar hit.

514
00:24:10,360 --> 00:24:17,470
Så detta förändras denna pil höger
nu för att peka på den här killen här.

515
00:24:17,470 --> 00:24:19,580
Nu, kom ihåg, vi har
en temporär variabel.

516
00:24:19,580 --> 00:24:23,520
Så vi har inte föräldralösa några noder,
eftersom jag också har den här killen i min

517
00:24:23,520 --> 00:24:25,010
genomförandet av remove.

518
00:24:25,010 --> 00:24:29,600
Så nu, är om listan i sig inte är noll,
Jag behöver rätta till en liten sak.

519
00:24:29,600 --> 00:24:32,690
>> Jag måste nu se till att den här pilen,
som tidigare pekar

520
00:24:32,690 --> 00:24:36,830
50-34, har detta att gå bort,
för om jag försöker bli

521
00:24:36,830 --> 00:24:41,910
av 34, 50 hade bättre inte behålla någon
typ av tillbaka referens till det som

522
00:24:41,910 --> 00:24:42,820
pil föreslog.

523
00:24:42,820 --> 00:24:44,820
Så jag gjorde just denna linje.

524
00:24:44,820 --> 00:24:46,520
Så då jag är klar.

525
00:24:46,520 --> 00:24:48,040
Detta mål är faktiskt ganska lätt.

526
00:24:48,040 --> 00:24:51,010
Hugga av huvudet av listan
är relativt rättfram.

527
00:24:51,010 --> 00:24:52,980
>> Tyvärr, det är det här
irriterande annat block.

528
00:24:52,980 --> 00:24:56,170
Så nu har jag att behandla ärendet
där det finns något i mitten.

529
00:24:56,170 --> 00:24:59,880
Men det är inte så hemskt, utom
för syntax som denna.

530
00:24:59,880 --> 00:25:03,080
Så om jag inte är i början av den
lista, jag är någonstans i mitten.

531
00:25:03,080 --> 00:25:08,160
Och denna linje här säger, start
oavsett på vilken nod som du är på.

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

533
00:25:11,210 --> 00:25:18,550
Gå till föregående nodens nästa fält
och pekar att vid pekaren.

534
00:25:18,550 --> 00:25:20,390
>> Nu gör vi det bildmässigt.

535
00:25:20,390 --> 00:25:21,640
Det började bli komplicerad.

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

537
00:25:30,480 --> 00:25:37,990
Så om jag har ett tidigare fält här -
låt oss göra detta - nästa fält här.

538
00:25:37,990 --> 00:25:41,200
Jag kommer att förenkla mina pekare snarare
än dra en hel massa

539
00:25:41,200 --> 00:25:45,710
saker fram och tillbaka kors och tvärs
varandra.

540
00:25:45,710 --> 00:25:50,870
Och nu, låt oss bara säga att det är 1, 2,
3 av hänsyn till diskussionen, och med

541
00:25:50,870 --> 00:25:53,410
men som inte stämmer med
problemet i fråga.

542
00:25:53,410 --> 00:25:55,900
>> Så här är min länkad lista.

543
00:25:55,900 --> 00:25:59,300
Jag försöker att ta bort två i detta
särskild version av berättelsen.

544
00:25:59,300 --> 00:26:01,960
Så jag har uppdaterat pekare till
peka på den här killen.

545
00:26:01,960 --> 00:26:03,315
Så det här är PTR.

546
00:26:03,315 --> 00:26:04,530
Han pekar här.

547
00:26:04,530 --> 00:26:07,170
Detta är listan, som föreligger
globalt som tidigare.

548
00:26:07,170 --> 00:26:09,200
Och han pekar här oavsett vad.

549
00:26:09,200 --> 00:26:10,800
Och nu, jag försöker att ta bort två.

550
00:26:10,800 --> 00:26:13,850
>> Så om pekaren pekar här, jag är
kommer att följa, som synes, den

551
00:26:13,850 --> 00:26:17,110
föregående pekare, som sätter mig på 1.

552
00:26:17,110 --> 00:26:22,290
Jag sedan kommer att säga att nästa
område, vilket leder mig över till detta

553
00:26:22,290 --> 00:26:25,410
rutan här, kommer att
lika pekare intill.

554
00:26:25,410 --> 00:26:28,400
Så om detta pekare, är detta nästa.

555
00:26:28,400 --> 00:26:31,840
Det innebär att denna pil behov
att peka på den här killen.

556
00:26:31,840 --> 00:26:35,140
>> Så vad som kodrad har bara
gjort är lite av detta.

557
00:26:35,140 --> 00:26:37,500
Och nu, det ser ut som en
steg i rätt riktning.

558
00:26:37,500 --> 00:26:41,390
Vi vill i huvudsak att klippa två ut
i mitten av ett och tre.

559
00:26:41,390 --> 00:26:44,400
Så det är logiskt att vi vill
drar denna pekare runt den.

560
00:26:44,400 --> 00:26:50,400
Så här nästa rad kontrollerar om pekare
Nästa är inte noll, det finns

561
00:26:50,400 --> 00:26:54,200
indeed någon till höger om två,
det innebär att vi också måste göra

562
00:26:54,200 --> 00:26:55,850
lite snip här.

563
00:26:55,850 --> 00:27:00,590
>> Så jag måste nu följa detta pekare
och uppdatera den tidigare pekaren på

564
00:27:00,590 --> 00:27:05,410
den här killen för att göra lite av en
komma runt här poängen här.

565
00:27:05,410 --> 00:27:07,100
Och nu, det är visuellt trevligt.

566
00:27:07,100 --> 00:27:11,930
Det är lite rörigt i att det finns
ingen en pekar på två längre.

567
00:27:11,930 --> 00:27:13,600
2 pekar åt vänster.

568
00:27:13,600 --> 00:27:14,980
Och 2 pekar åt höger.

569
00:27:14,980 --> 00:27:17,480
Men han kan göra vad han vill, eftersom
han är på väg att bli befriad.

570
00:27:17,480 --> 00:27:19,480
Och det spelar ingen roll vad
dessa värden är längre.

571
00:27:19,480 --> 00:27:23,040
>> Det som är viktigt är att den återstående
killar routing ovan

572
00:27:23,040 --> 00:27:24,280
och under honom nu.

573
00:27:24,280 --> 00:27:25,810
Och faktiskt, det är vad vi ska göra härnäst.

574
00:27:25,810 --> 00:27:29,360
Vi fri pekare, vilket innebär att vi berättar
operativsystem, är du välkommen

575
00:27:29,360 --> 00:27:30,906
att återta detta.

576
00:27:30,906 --> 00:27:34,900
Och så slutligen återvänder vi.

577
00:27:34,900 --> 00:27:37,220
Else förstått, om vi
har inte kommit tillbaka ännu,

578
00:27:37,220 --> 00:27:38,290
vi måste fortsätta leta.

579
00:27:38,290 --> 00:27:41,485
Så pekaren är lika med pekaren intill bara
innebär att flytta den här killen här.

580
00:27:41,485 --> 00:27:42,600
Flytta den här killen här.

581
00:27:42,600 --> 00:27:45,400
Flytta den här killen här om, i själva verket
vi hittade inte numret

582
00:27:45,400 --> 00:27:46,960
vi söker ännu.

583
00:27:46,960 --> 00:27:49,630
>> Så ärligt talat, det ser helt
överväldigande, tror jag, i första

584
00:27:49,630 --> 00:27:52,180
blick, särskilt om du kämpade
med detta under testet sedan se

585
00:27:52,180 --> 00:27:52,850
ungefär så här.

586
00:27:52,850 --> 00:27:55,050
Och du klappa dig själv på ryggen.

587
00:27:55,050 --> 00:27:57,080
Tja, det finns inget sätt jag kunde ha
komma med det på frågesport.

588
00:27:57,080 --> 00:28:00,470
Men jag skulle vilja hävda, du kan om du bryter
det i dessa individuella

589
00:28:00,470 --> 00:28:04,400
fall och bara gå igenom det
omsorgsfullt, om än visserligen under

590
00:28:04,400 --> 00:28:06,300
stressande förhållanden.

591
00:28:06,300 --> 00:28:09,470
>> Tack och lov, den bild som skapas
allt lyckligare.

592
00:28:09,470 --> 00:28:11,050
Du kan dra det här i
ett antal olika sätt.

593
00:28:11,050 --> 00:28:12,760
Du behöver inte göra det kors och tvärs
sak här.

594
00:28:12,760 --> 00:28:14,520
Du kan göra det med rak
linjer som denna.

595
00:28:14,520 --> 00:28:18,790
Men kontentan av detta problem, i
allmänhet var att inse att den

596
00:28:18,790 --> 00:28:22,060
Bilden till slut skulle se lite
ungefär så här, eftersom

597
00:28:22,060 --> 00:28:25,030
konstant tid innebar att du håller
fastnar och fastnar och störa ut

598
00:28:25,030 --> 00:28:29,900
nya noder i början
i listan.

599
00:28:29,900 --> 00:28:31,960
Några frågor?

600
00:28:31,960 --> 00:28:34,565
Förmodligen den mest utmanande av
förvisso de kodande frågor.

601
00:28:34,565 --> 00:28:37,690
>> PUBLIK: Så är listan liknar
huvudet i tidigare exempel.

602
00:28:37,690 --> 00:28:39,640
>> DAVID J. MALAN: Exakt, exakt.

603
00:28:39,640 --> 00:28:43,130
Bara ett annat namn för
en global variabel.

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

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å det här är den där du
var tvungen att skriva punkt.

608
00:28:52,020 --> 00:28:56,060
Vissa människor skrev essäer
för denna fråga.

609
00:28:56,060 --> 00:29:00,230
Men du behöver bara använda dessa sex villkor
att beskriva vad som händer när

610
00:29:00,230 --> 00:29:02,440
du försöker kontakta facebook.com.

611
00:29:02,440 --> 00:29:07,930
Så jag ska bara prata igenom processen
genom att använda alla dessa villkor.

612
00:29:07,930 --> 00:29:11,290
Så i vår läsar skriver vi facebook.com
och tryck på Retur.

613
00:29:11,290 --> 00:29:17,280
Så vår webbläsare kommer att konstruera en
HTTP begära att det kommer att skicka

614
00:29:17,280 --> 00:29:22,220
genom någon process till Facebook för
Facebook att reagera på oss med

615
00:29:22,220 --> 00:29:24,450
HTML på sin sida.

616
00:29:24,450 --> 00:29:28,800
>> Så vad är den process genom
vilken HTTP-begäran

617
00:29:28,800 --> 00:29:30,730
faktiskt kommer till Facebook?

618
00:29:30,730 --> 00:29:32,790
Så först måste vi översätta
Facebook.com.

619
00:29:32,790 --> 00:29:38,780
Så bara fick namnet Facebook.com,
där faktiskt gör HTTP-begäran

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

621
00:29:39,940 --> 00:29:44,120
Så vi behöver översätta Facebook.com
till en IP-adress, som unikt

622
00:29:44,120 --> 00:29:47,620
identifierar vilken maskin vi faktiskt
vill skicka förfrågan till.

623
00:29:47,620 --> 00:29:49,310
Din bärbara dator har en IP-adress.

624
00:29:49,310 --> 00:29:52,240
Något som är ansluten till Internet
har en IP-adress.

625
00:29:52,240 --> 00:29:59,030
>> Så DNS, Domain Name System, är det
vad som kommer att hantera översättning

626
00:29:59,030 --> 00:30:03,750
från facebook.com till en IP-adress som
du verkligen vill kontakta.

627
00:30:03,750 --> 00:30:08,075
Så vi kontakta DNS-servrar och
säg, vad är facebook.com?

628
00:30:08,075 --> 00:30:16,560
Den säger, åh, det är IP-adress 190,212
något, något, något.

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

630
00:30:16,900 --> 00:30:18,850
Nu vet jag vad maskin
Jag vill kontakta.

631
00:30:18,850 --> 00:30:22,360
>> Så då du skickar din HTTP-begäran
över till den maskinen.

632
00:30:22,360 --> 00:30:24,140
Så hur det blir med den maskinen?

633
00:30:24,140 --> 00:30:27,200
Tja, går en begäran från
router till router studsande.

634
00:30:27,200 --> 00:30:32,630
Minns exemplet i klassen, där
vi faktiskt såg den väg som den

635
00:30:32,630 --> 00:30:35,340
paket tog när vi försökte
att kommunicera.

636
00:30:35,340 --> 00:30:38,460
Vi såg den hoppa över Atlanten
Ocean på en punkt eller vad som helst.

637
00:30:38,460 --> 00:30:42,820
>> Så den sista termen porten.

638
00:30:42,820 --> 00:30:46,520
Så detta är nu på din dator.

639
00:30:46,520 --> 00:30:49,970
Du kan ha flera saker idag
kommunicerar med Internet.

640
00:30:49,970 --> 00:30:53,730
Så jag kan köra, säg, Skype.

641
00:30:53,730 --> 00:30:55,670
Jag kanske har en webbläsare öppen.

642
00:30:55,670 --> 00:30:59,010
Jag kanske har något som
torrenta filer.

643
00:30:59,010 --> 00:31:00,880
Så alla dessa saker är
som kommunicerar med den

644
00:31:00,880 --> 00:31:02,600
internet på något sätt.

645
00:31:02,600 --> 00:31:08,070
>> Så när din dator tar emot en del data
från internet, hur fungerar det

646
00:31:08,070 --> 00:31:10,130
vet vad programmet faktiskt
vill ha uppgifterna?

647
00:31:10,130 --> 00:31:12,610
Hur vet den om detta
uppgifter är avsedd för

648
00:31:12,610 --> 00:31:16,070
torrenta tillämpning i motsats
till webbläsaren?

649
00:31:16,070 --> 00:31:20,980
Så detta är syftet med hamnar i det
alla dessa program har

650
00:31:20,980 --> 00:31:22,720
hävdade en port på datorn.

651
00:31:22,720 --> 00:31:27,580
Så din webbläsare säger, hej,
Jag lyssnar på port 1000.

652
00:31:27,580 --> 00:31:32,240
Och din torrenta programmet säger,
Jag lyssnar på port 3000.

653
00:31:32,240 --> 00:31:34,770
Och Skype säger, jag använder port 4000.

654
00:31:34,770 --> 00:31:41,950
>> Så när du får lite uppgifter som hör
till en av dessa tillämpningar, data

655
00:31:41,950 --> 00:31:45,510
är märkt med vilken port det faktiskt
ska skickas med till.

656
00:31:45,510 --> 00:31:47,950
Så här säger, åh, jag tillhör
till port 1000.

657
00:31:47,950 --> 00:31:50,950
Jag vet då jag måste vidarebefordra denna
tillsammans med min webbläsare.

658
00:31:50,950 --> 00:31:56,440
Så anledningen till att det är relevant här
är att webbservrar brukar

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

660
00:31:58,240 --> 00:32:02,420
Så när jag kontaktar Facebook.com, jag är
kommunicerar med vissa maskin.

661
00:32:02,420 --> 00:32:06,390
Men jag måste säga vilken hamn som
maskin som jag vill kommunicera med.

662
00:32:06,390 --> 00:32:09,160
Och webbservrar brukar vara
lyssnar på port 80.

663
00:32:09,160 --> 00:32:14,010
>> Om de ville, de kunde ställa in den
upp så att den listar som på port 7000.

664
00:32:14,010 --> 00:32:19,090
Och sedan i en webbläsare, jag kunde
manuellt skriva Facebook.com: 7000 till

665
00:32:19,090 --> 00:32:24,600
skicka förfrågan till port 7000
av Facebooks webbserver.

666
00:32:24,600 --> 00:32:26,820
>> DAVID J. MALAN: Och i detta fall, till och med
även om vi inte kräver att människor

667
00:32:26,820 --> 00:32:30,000
nämner detta, i det här fallet, vilken port
skulle begäran faktiskt gå till?

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

669
00:32:36,630 --> 00:32:37,880
Försök igen.

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

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

672
00:32:44,300 --> 00:32:47,960
Inte ute efter det, men en finess
det är det ingen sista.

673
00:32:47,960 --> 00:32:51,770
>> ROB BOWDEN: Så HTTPS, eftersom det är
lyssnar specifikt för

674
00:32:51,770 --> 00:32:55,180
krypterad, det är på port 4430.

675
00:32:55,180 --> 00:32:57,680
>> Publik: Och e-post är 25, eller hur?

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

677
00:33:00,670 --> 00:33:03,760
>> ROB BOWDEN: Jag vet inte ens de flesta av
den - som alla de lägre tenderar att vara

678
00:33:03,760 --> 00:33:06,310
reserverade för saker.

679
00:33:06,310 --> 00:33:09,260
Jag tror att allt under
1024 är reserverad.

680
00:33:09,260 --> 00:33:13,450
>> PUBLIK: Varför sa du
3 var fel nummer?

681
00:33:13,450 --> 00:33:18,820
>> ROB BOWDEN: För i en IP-adress,
Det finns fyra grupper av siffror.

682
00:33:18,820 --> 00:33:21,090
Och de är från 0 till 255.

683
00:33:21,090 --> 00:33:28,060
Så 192.168.2.1 är en vanlig
lokalt nätverk IP-adress.

684
00:33:28,060 --> 00:33:30,840
Lägg märke till alla de som är mindre än 255.

685
00:33:30,840 --> 00:33:33,570
Så när jag började med 300, att
kunde omöjligen ha

686
00:33:33,570 --> 00:33:35,210
varit ett av numren.

687
00:33:35,210 --> 00:33:38,170
>> DAVID J. MALAN: Men det dumma klipp
från - var det CSI, där de hade en

688
00:33:38,170 --> 00:33:39,970
nummer som var för stor
för IP-adressen.

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

690
00:33:42,940 --> 00:33:46,110
>> ROB BOWDEN: Har du frågor om detta?

691
00:33:46,110 --> 00:33:51,710
Den nästa, så fullständig förändring i
ämne, men vi har denna PHP-array för

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

693
00:33:53,270 --> 00:33:56,360
Och vi har en oordnad lista.

694
00:33:56,360 --> 00:33:59,550
Och vi vill skriva ut varje post i listan
bara innehåller huset namnet.

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

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

697
00:34:11,870 --> 00:34:17,540
Så kom ihåg, syntaxen är foreach
array som objekt i arrayen.

698
00:34:17,540 --> 00:34:22,360
Så genom varje iteration av slingan,
Huset kommer att ta på en av de

699
00:34:22,360 --> 00:34:24,060
värden inne i matrisen.

700
00:34:24,060 --> 00:34:26,530
>> På den första iterationen, hus
blir Cabot House.

701
00:34:26,530 --> 00:34:30,370
På en andra iteration, hus kommer
vara Courier hus och så vidare.

702
00:34:30,370 --> 00:34:34,370
Så för varje quad som hus, vi är
bara att skriva ut -

703
00:34:34,370 --> 00:34:37,250
du kan också ha ekade -

704
00:34:37,250 --> 00:34:42,199
listobjektet och sedan husets namn
och stäng sedan listobjektet.

705
00:34:42,199 --> 00:34:45,210
Klammer hängslen är valfria här.

706
00:34:45,210 --> 00:34:49,480
>> Och då sa vi också i fråga
sig själv, kom ihåg att stänga

707
00:34:49,480 --> 00:34:50,770
oordnad lista tag.

708
00:34:50,770 --> 00:34:53,949
Så vi måste gå ur PHP-läge
för att göra detta.

709
00:34:53,949 --> 00:35:00,280
Eller vi kunde ha ekade
stäng oordnad lista tag.

710
00:35:00,280 --> 00:35:02,380
>> DAVID J. MALAN: Också bra här skulle
har varit att använda en gammal skola för

711
00:35:02,380 --> 00:35:07,340
slinga med en $ i = 0 0 och använda räknas till
räkna ut längden på strålen.

712
00:35:07,340 --> 00:35:09,240
Helt bra också, precis
lite wordier.

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

714
00:35:12,170 --> 00:35:14,742
>> PUBLIK: Så om ni skulle
[OHÖRBAR], skulle du göra -

715
00:35:14,742 --> 00:35:16,734
Jag glömmer vad slingan [OHÖRBAR] är.

716
00:35:16,734 --> 00:35:21,380
Skulle du $ quad fäste jag?

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

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

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

720
00:35:26,650 --> 00:35:27,900
>> ROB BOWDEN: Något annat?

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

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

723
00:35:32,010 --> 00:35:32,300
Avvägningar.

724
00:35:32,300 --> 00:35:38,290
Så det fanns knippen av svaren
möjligt för var och en av dessa.

725
00:35:38,290 --> 00:35:40,510
Vi var egentligen bara ute efter
något övertygande för en upp-och

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

727
00:35:41,100 --> 00:35:44,830
Och nummer 16 frågade, validera användare "
ingång på klientsidan, som med JavaScript

728
00:35:44,830 --> 00:35:47,280
istället för serversidan, som med PHP.

729
00:35:47,280 --> 00:35:49,450
Så vad är en uppsida på
gör klientsidan?

730
00:35:49,450 --> 00:35:53,780
>> Tja, är en av de saker som vi föreslagit
att du minskar latensen, eftersom du

731
00:35:53,780 --> 00:35:56,750
behöver inte bry kontakta
server, vilket kan ta några

732
00:35:56,750 --> 00:36:00,390
millisekunder eller ens ett par sekunder
genom att undvika det och bara

733
00:36:00,390 --> 00:36:04,670
validering av användarnas input klientsidan genom
utlöser en på-lämna handler och

734
00:36:04,670 --> 00:36:06,650
bara kolla, de skriver
något för namn?

735
00:36:06,650 --> 00:36:08,080
Har de skriver något
in för e-postadress?

736
00:36:08,080 --> 00:36:10,950
Har de väljer en sovsal från
rullgardinsmenyn?

737
00:36:10,950 --> 00:36:14,360
>> Du kan ge dem omedelbar respons
använder gigahertz dator

738
00:36:14,360 --> 00:36:16,770
eller vad de har som är
faktiskt på sitt skrivbord.

739
00:36:16,770 --> 00:36:19,310
Så det är bara en bättre användar
typiskt erfarenhet.

740
00:36:19,310 --> 00:36:24,460
Men en nackdel med att göra på klientsidan
validering, om du gör det utan att också

741
00:36:24,460 --> 00:36:29,860
göra validering på serversidan är att
de flesta någon som kommer ut av CS50 vet

742
00:36:29,860 --> 00:36:33,980
att du bara kan skicka alla data som du vill
till en server som helst antal sätt.

743
00:36:33,980 --> 00:36:37,030
Ärligt talat, de flesta alla webbläsare kan du
klicka runt i inställningarna och bara

744
00:36:37,030 --> 00:36:40,110
stänga av JavaScript, som,
Därför inaktivera alla former av

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

746
00:36:41,080 --> 00:36:44,460
>> Men du också kanske kommer ihåg att även jag
gjorde några mystiska saker i klass med hjälp av

747
00:36:44,460 --> 00:36:47,790
telnet och faktiskt låtsas
vara en webbläsare genom att skicka get

748
00:36:47,790 --> 00:36:49,240
förfrågningar till en server.

749
00:36:49,240 --> 00:36:51,030
Och det är verkligen inte
med användning av någon JavaScript.

750
00:36:51,030 --> 00:36:53,290
Det är bara jag skriva kommandon
vid ett tangentbord.

751
00:36:53,290 --> 00:36:57,410
Så egentligen, någon programmerare inom tillräckligt
komfort med webben och HTTP

752
00:36:57,410 --> 00:37:01,690
kunde skicka de data som han eller hon vill
till en server utan validering.

753
00:37:01,690 --> 00:37:05,470
Och om din server inte också kontroll,
gav de mig ett namn, är

754
00:37:05,470 --> 00:37:08,930
detta faktiskt en giltig e-postadress, gjorde
de väljer en sovsal, kan du sluta

755
00:37:08,930 --> 00:37:12,800
upp sätta in falska eller bara tom uppgifter
in i din databas, vilket troligen

756
00:37:12,800 --> 00:37:15,450
kommer inte att vara bra om
du räknade med att det var där.

757
00:37:15,450 --> 00:37:16,770
>> Så detta är en irriterande verklighet.

758
00:37:16,770 --> 00:37:19,890
Men i allmänhet, klientsidan
validering är stor.

759
00:37:19,890 --> 00:37:21,810
Men det betyder dubbelt så mycket arbete.

760
00:37:21,810 --> 00:37:25,970
Även om det existerar olika
bibliotek, JavaScript-bibliotek för

761
00:37:25,970 --> 00:37:28,830
exempel att göra detta mycket,
mycket mindre av en huvudvärk.

762
00:37:28,830 --> 00:37:31,940
Och du kan återanvända en del av koden
serversidan, klientsidan.

763
00:37:31,940 --> 00:37:35,980
Men inser att det är normalt
merarbete.

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

765
00:37:36,415 --> 00:37:37,792
>> PUBLIK: Så om vi bara
sa mindre säker -

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

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

768
00:37:39,680 --> 00:37:43,105
De är alltid svårare
som ska döma.

769
00:37:43,105 --> 00:37:44,480
>> ROB BOWDEN: Det skulle
har godkänts.

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

771
00:37:44,810 --> 00:37:45,810
>> ROB BOWDEN: Jag skapade det här problemet.

772
00:37:45,810 --> 00:37:46,735
Det skulle ha godkänts.

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

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

775
00:37:47,830 --> 00:37:51,770
>> ROB BOWDEN: Men vi accepterade inte
för det första en -

776
00:37:51,770 --> 00:37:53,630
bra, det vi söker efter är
något som du inte behöver

777
00:37:53,630 --> 00:37:55,270
kommunicera med servern.

778
00:37:55,270 --> 00:37:58,355
Vi accepterade inte bara snabbare.

779
00:37:58,355 --> 00:38:00,080
>> PUBLIK: Hur är
inte ladda om sidan?

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

781
00:38:00,430 --> 00:38:03,000
Det var ett accepterat svar.

782
00:38:03,000 --> 00:38:06,300
>> DAVID J. MALAN: Allt där vi kände
det var mer troligt än inte troligt

783
00:38:06,300 --> 00:38:09,780
att du visste vad du var
säger, vilket är en tuff

784
00:38:09,780 --> 00:38:13,500
linje för att rita ibland.

785
00:38:13,500 --> 00:38:16,000
Med hjälp av en länkad lista istället
i en matris för att upprätthålla en

786
00:38:16,000 --> 00:38:17,590
sorterad lista med heltal.

787
00:38:17,590 --> 00:38:21,000
Så en upp och vi ofta citera med länkade
listor som motiverade sin helhet

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

789
00:38:22,370 --> 00:38:23,030
De kan växa.

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

791
00:38:23,950 --> 00:38:27,370
Så du behöver inte hoppa genom fälgar
att faktiskt skapa mer minne

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

793
00:38:28,140 --> 00:38:30,310
Eller du behöver inte bara
säga, förlåt, användare.

794
00:38:30,310 --> 00:38:31,410
Matrisen är fylld.

795
00:38:31,410 --> 00:38:35,850
Så dynamisk tillväxt av listan.

796
00:38:35,850 --> 00:38:37,210
En nackdel dock av länkade listor?

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

798
00:38:40,916 --> 00:38:43,356
>> PUBLIK: Det är linjär.

799
00:38:43,356 --> 00:38:45,800
Sökning på länkad lista är linjär
istället för vad du loggar in

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

801
00:38:46,360 --> 00:38:50,160
Söka på en länkad lista är linjär,
även om den är sorterad, eftersom du kan

802
00:38:50,160 --> 00:38:53,170
bara följa dessa brödsmulor, dessa
pekare, från början av listan

803
00:38:53,170 --> 00:38:53,570
till slutet.

804
00:38:53,570 --> 00:38:57,970
Du kan inte utnyttja random access och,
sålunda, binär sökning, även om det är

805
00:38:57,970 --> 00:39:00,740
sorteras, att du kunde
göra med en array.

806
00:39:00,740 --> 00:39:02,390
Och det finns också en annan kostnad.

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

808
00:39:02,966 --> 00:39:03,800
>> PUBLIK: Minne ineffektiv?

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

810
00:39:04,130 --> 00:39:06,940
Tja, jag skulle inte nödvändigtvis
säga ineffektivt.

811
00:39:06,940 --> 00:39:10,110
Men det kostar dig mer minne,
eftersom du behöver 32 bitar för varje

812
00:39:10,110 --> 00:39:13,400
nod för den ytterligare pekare, vid
stone för en enskilt länkad lista.

813
00:39:13,400 --> 00:39:16,660
Nu, om du bara vill lagra heltal och
du lägger pekaren, det är

814
00:39:16,660 --> 00:39:17,830
faktiskt slags icke-trivial.

815
00:39:17,830 --> 00:39:19,340
Det är en fördubbling av mängden minne.

816
00:39:19,340 --> 00:39:22,330
Men i verkligheten, om du lagrar en
länkad lista av structs som kan ha

817
00:39:22,330 --> 00:39:25,540
8 byte, 16 byte, ännu mer
än så, kanske är mindre

818
00:39:25,540 --> 00:39:26,500
av en marginalkostnad.

819
00:39:26,500 --> 00:39:28,320
Men det är en kostnad ändå.

820
00:39:28,320 --> 00:39:31,880
Så någon av dem skulle har
varit bra som nackdelar.

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

822
00:39:32,110 --> 00:39:36,100
Använda PHP istället för C att skriva
en kommandorad program.

823
00:39:36,100 --> 00:39:41,890
Så här är det ofta snabbare att använda en
språk som PHP eller Ruby eller Python.

824
00:39:41,890 --> 00:39:43,700
Du bara snabbt öppna
upp en textredigerare.

825
00:39:43,700 --> 00:39:45,900
Du har många fler funktioner
tillgängliga för dig.

826
00:39:45,900 --> 00:39:49,325
PHP har diskbänken av funktioner,
medan i C, du

827
00:39:49,325 --> 00:39:50,420
har mycket, mycket lite.

828
00:39:50,420 --> 00:39:53,820
Faktum är killar det vet den hårda vägen
att du inte har hashtabeller.

829
00:39:53,820 --> 00:39:55,000
Du behöver inte ha länkade listor.

830
00:39:55,000 --> 00:39:57,470
Om du vill ha dem, måste du
genomföra dem själv.

831
00:39:57,470 --> 00:40:00,950
>> Så en uppåt av PHP eller egentligen något
tolkat språk är snabbheten

832
00:40:00,950 --> 00:40:02,920
med vilken du kan skriva kod.

833
00:40:02,920 --> 00:40:06,660
Men en nackdel, vi såg detta när jag
snabbt piskade upp en misspeller

834
00:40:06,660 --> 00:40:11,780
genomförande i föreläsning med PHP, är
att med hjälp av ett tolkat språk

835
00:40:11,780 --> 00:40:13,570
är oftast långsammare.

836
00:40:13,570 --> 00:40:18,420
Och vi såg att bevisligen med en
öka i tid från 0,3 sekunder till 3

837
00:40:18,420 --> 00:40:24,440
sekunder, på grund av tolkningen
som faktiskt händer.

838
00:40:24,440 --> 00:40:27,060
>> En annan uppåtsidan var att du
behöver inte kompilera.

839
00:40:27,060 --> 00:40:30,130
Så det snabbar också upp utvecklingen
för övrigt, eftersom du inte har

840
00:40:30,130 --> 00:40:31,360
två steg för att köra ett program.

841
00:40:31,360 --> 00:40:32,140
Du har bara en.

842
00:40:32,140 --> 00:40:35,260
Och så det är ganska
övertygande också.

843
00:40:35,260 --> 00:40:38,450
Genom att använda en SQL-databas istället för att
en CSV-fil för att lagra data.

844
00:40:38,450 --> 00:40:40,230
Så SQL databas används för pset7.

845
00:40:40,230 --> 00:40:42,060
CSV-filer som du inte använder mycket.

846
00:40:42,060 --> 00:40:45,960
Men du använde det indirekt i pset7 som
väl genom att tala med Yahoo Finance.

847
00:40:45,960 --> 00:40:49,330
>> Men CSV är precis som en Excel-fil, men
super enkelt, där kolumnerna är

848
00:40:49,330 --> 00:40:54,010
bara demarked med kommatecken inne
av en annars textfil.

849
00:40:54,010 --> 00:40:56,740
Och med hjälp av en SQL-databas är
lite mer övertygande.

850
00:40:56,740 --> 00:41:00,060
Det är en upp, eftersom du får saker
liksom välja och infoga och ta bort.

851
00:41:00,060 --> 00:41:03,790
Och du får, förmodligen, index som
MySQL och andra databaser, t.ex.

852
00:41:03,790 --> 00:41:07,510
Oracle, bygga för dig i minnet, vilket
innebär att din select är förmodligen inte

853
00:41:07,510 --> 00:41:09,000
kommer att vara linjär topp till botten.

854
00:41:09,000 --> 00:41:11,300
Det är faktiskt kommer att bli något
som binär sökning eller något

855
00:41:11,300 --> 00:41:12,520
liknande anda.

856
00:41:12,520 --> 00:41:13,930
Så de är i allmänhet snabbare.

857
00:41:13,930 --> 00:41:16,040
>> Men en nackdel är att
det är bara mer arbete.

858
00:41:16,040 --> 00:41:16,730
Det är mer ansträngning.

859
00:41:16,730 --> 00:41:18,140
Du måste förstå databaser.

860
00:41:18,140 --> 00:41:18,940
Du måste ställa in den.

861
00:41:18,940 --> 00:41:20,840
Du behöver en server för att köra
databasen på.

862
00:41:20,840 --> 00:41:22,750
Du måste förstå
hur man konfigurerar den.

863
00:41:22,750 --> 00:41:24,930
Så det är bara dessa
typer av kompromisser.

864
00:41:24,930 --> 00:41:27,860
En CSV-fil, kan du
skapa den med gedit.

865
00:41:27,860 --> 00:41:28,770
Och du är bra att gå.

866
00:41:28,770 --> 00:41:31,550
Det är ingen komplicerad än så.

867
00:41:31,550 --> 00:41:34,870
>> Med hjälp av en trie stället för en hashtabell
med separat kedja för att lagra en

868
00:41:34,870 --> 00:41:37,490
lexikon över ord som påminner
av pset5.

869
00:41:37,490 --> 00:41:42,480
Så en försöker upp i teorin
åtminstone, är vad?

870
00:41:42,480 --> 00:41:46,380
Konstant tid, åtminstone om du är
hashing på var och en av de enskilda

871
00:41:46,380 --> 00:41:48,990
bokstäver i ett ord, som du
kan ha för pset5.

872
00:41:48,990 --> 00:41:52,720
Det kan vara fem hash, sex
hashar om det finns fem eller sex

873
00:41:52,720 --> 00:41:53,900
bokstäverna i ordet.

874
00:41:53,900 --> 00:41:54,580
Och det är ganska bra.

875
00:41:54,580 --> 00:41:56,910
Och om det finns en övre gräns för hur
länge dina ord kan vara, det är

876
00:41:56,910 --> 00:41:59,320
indeed asymptotiskt konstant tid.

877
00:41:59,320 --> 00:42:05,180
>> En hash-tabell med separat
kedja, problemet där med att

878
00:42:05,180 --> 00:42:09,070
typ av datastruktur är att den
resultatet av dina algoritmer vanligtvis

879
00:42:09,070 --> 00:42:12,700
beror på flera saker
redan i datastrukturen.

880
00:42:12,700 --> 00:42:15,660
Och det är definitivt fallet med
kedjor, varvid mer grejer du sätter

881
00:42:15,660 --> 00:42:18,800
in i en hash-tabell, ju längre de
kedjor gå, vilket innebär i värsta

882
00:42:18,800 --> 00:42:21,960
fall, det du kanske letar efter
är hela vägen vid slutet av en

883
00:42:21,960 --> 00:42:26,000
av dessa kedjor, som effektivt
ankommer till något linjär.

884
00:42:26,000 --> 00:42:29,450
>> Nu, i praktiken kan det absolut
vara så att en hash-tabell med

885
00:42:29,450 --> 00:42:32,820
kedjorna är snabbare än en motsvarande
trie genomförande.

886
00:42:32,820 --> 00:42:35,570
Men det är av olika skäl, bland
som försöker använda en hel del

887
00:42:35,570 --> 00:42:39,240
minne som kan, i själva verket, långsamt saker
ner, eftersom du inte får bra

888
00:42:39,240 --> 00:42:42,410
fördelarna med något som kallas caching,
där saker som är nära varandra

889
00:42:42,410 --> 00:42:45,420
i minnet kan nås
ofta snabbare.

890
00:42:45,420 --> 00:42:48,180
Och ibland kan man komma med
en riktigt bra hashfunktion.

891
00:42:48,180 --> 00:42:51,060
Även om du har att slösa bort lite av
minne, du kanske faktiskt kunna

892
00:42:51,060 --> 00:42:54,430
hitta saker snabbt och inte
så illa som linjärt.

893
00:42:54,430 --> 00:42:58,410
>> Så kort sagt, det var inte nödvändigtvis
med någon av dessa en eller till och med två

894
00:42:58,410 --> 00:43:00,050
specifika saker som vi sökte.

895
00:43:00,050 --> 00:43:03,080
Verkligen något övertygande
som en upp-och nedsidan

896
00:43:03,080 --> 00:43:04,800
allmänhet fångade vårt öga.

897
00:43:04,800 --> 00:43:11,840
>> ROB BOWDEN: Så för uppåtsidan, vi gjorde
inte acceptera på egen hand "snabbare." Ni

898
00:43:11,840 --> 00:43:14,540
hade att säga något om det.

899
00:43:14,540 --> 00:43:17,910
Även om du sa teoretiskt snabbare,
Vi visste att du slags förstått

900
00:43:17,910 --> 00:43:19,470
att det är 0 av 1.

901
00:43:19,470 --> 00:43:22,820
Och hashtabell, i teorin,
är inte 0 av 1.

902
00:43:22,820 --> 00:43:26,550
Att nämna något om körtid
allmänhet fick du poäng.

903
00:43:26,550 --> 00:43:32,640
Men "snabbare," de flesta av lösningarna på
den stora styrelsen som försöker var

904
00:43:32,640 --> 00:43:34,990
objektivt långsammare än lösningar
det var hashtabeller.

905
00:43:34,990 --> 00:43:37,250
Så snabbare i och för sig
är inte riktigt sant.

906
00:43:37,250 --> 00:43:41,550

907
00:43:41,550 --> 00:43:44,380
>> DAVID J. MALAN: Dom de dom dom.

908
00:43:44,380 --> 00:43:46,686
Jag är nog den enda som inser
det är hur det är tänkt att

909
00:43:46,686 --> 00:43:47,500
uttalas, eller hur?

910
00:43:47,500 --> 00:43:50,400
>> ROB BOWDEN: Jag hade faktiskt ingen aning.

911
00:43:50,400 --> 00:43:51,650
>> DAVID J. MALAN: Det gjorde
känsla i mitt huvud.

912
00:43:51,650 --> 00:43:53,830

913
00:43:53,830 --> 00:43:57,580
>> ROB BOWDEN: Jag gör det här.

914
00:43:57,580 --> 00:43:58,020
OK.

915
00:43:58,020 --> 00:44:04,243
Så det här är den där du var tvungen att dra
diagrammet liknar du kanske

916
00:44:04,243 --> 00:44:06,040
har sett på tidigare tentor.

917
00:44:06,040 --> 00:44:12,200
Så låt oss titta bara på det här.

918
00:44:12,200 --> 00:44:18,170
Så från HTML-nod, vi har två
barn, huvudet och kroppen.

919
00:44:18,170 --> 00:44:20,570
Så vi gren - huvud och kropp.

920
00:44:20,570 --> 00:44:22,280
Huvudet har en titel tagg.

921
00:44:22,280 --> 00:44:23,710
Så vi har en titel.

922
00:44:23,710 --> 00:44:28,450
>> Nu, en sak en massa människor
glömt är att dessa textnoder är

923
00:44:28,450 --> 00:44:30,430
element inom detta träd.

924
00:44:30,430 --> 00:44:36,260
Så här råkar vi att dra dem som ovaler
för att skilja dem från dessa

925
00:44:36,260 --> 00:44:37,380
typer av noder.

926
00:44:37,380 --> 00:44:41,450
Men varsel även här har vi toppen,
mitten och botten kommer att hamna

927
00:44:41,450 --> 00:44:42,560
textnoder.

928
00:44:42,560 --> 00:44:46,250
Så glömmer dem var något
av ett vanligt misstag.

929
00:44:46,250 --> 00:44:48,770
>> Kroppen har tre barn -
dessa tre divs.

930
00:44:48,770 --> 00:44:53,340
Så div, div, div och sedan texten
nod barn i dessa divar.

931
00:44:53,340 --> 00:44:55,900
Det är ganska mycket det
för att frågor.

932
00:44:55,900 --> 00:44:57,860
>> DAVID J. MALAN: Och det är värt att notera,
även om vi inte uppehålla mig vid dessa

933
00:44:57,860 --> 00:45:01,040
detaljer i den tid vi spenderar på
JavaScript, som ordern gör, i

934
00:45:01,040 --> 00:45:02,290
Faktum är, oavsett tekniskt.

935
00:45:02,290 --> 00:45:06,330
Så om huvudet kommer före kropp i
HTML, då det ska visas att den

936
00:45:06,330 --> 00:45:08,860
kvar i kroppen i själva DOM.

937
00:45:08,860 --> 00:45:12,265
Att hans är, i allmänhet, bara FYI,
något som kallas dokument ordning, där

938
00:45:12,265 --> 00:45:13,260
det spelar roll.

939
00:45:13,260 --> 00:45:17,470
Och om du genomföra en parser,
ett program som läser HTML i byggnad

940
00:45:17,470 --> 00:45:20,960
upp i trädet i minnet, för att vara ärlig,
det är intuitivt nog vad du

941
00:45:20,960 --> 00:45:24,720
göra ändå - uppifrån och ned,
vänster till höger.

942
00:45:24,720 --> 00:45:26,116
>> ROB BOWDEN: Frågor på det?

943
00:45:26,116 --> 00:45:29,080

944
00:45:29,080 --> 00:45:30,000
Ska jag göra nästa?

945
00:45:30,000 --> 00:45:32,380
>> DAVID J. MALAN: Visst.

946
00:45:32,380 --> 00:45:33,810
>> ROB BOWDEN: OK.

947
00:45:33,810 --> 00:45:39,320
Så detta är den buffertöverskridning
attack fråga.

948
00:45:39,320 --> 00:45:43,740
Det viktigaste att inse här är,
väl, hur kan en motståndare trick

949
00:45:43,740 --> 00:45:46,170
detta program till att köra
godtycklig kod?

950
00:45:46,170 --> 00:45:51,860
Så argv1, den första kommandoraden
Argumentet för detta program, kan det vara

951
00:45:51,860 --> 00:45:53,920
godtyckligt lång.

952
00:45:53,920 --> 00:45:59,160
Men här vi använder memcpy att kopiera
argv1, vilket här är bar.

953
00:45:59,160 --> 00:46:00,165
Vi passerar det som argument.

954
00:46:00,165 --> 00:46:02,050
Och så det tar på namnfältet.

955
00:46:02,050 --> 00:46:08,040
>> Så vi memcpying bar
i denna buffert c..

956
00:46:08,040 --> 00:46:09,400
Hur många bytes vi kopierar?

957
00:46:09,400 --> 00:46:14,040
Jo men många byte bar händer
använder, längden på detta argument.

958
00:46:14,040 --> 00:46:17,930
Men c är bara 12 byte bred.

959
00:46:17,930 --> 00:46:22,280
Så om vi skriver en kommandorad argument
som är längre än 12 byte, vi är

960
00:46:22,280 --> 00:46:25,470
kommer att svämma över detta
speciella buffert.

961
00:46:25,470 --> 00:46:31,000
Nu, hur kan en motståndare lura
programmera in att köra godtycklig kod?

962
00:46:31,000 --> 00:46:34,910
>> Så kom ihåg att här
Huvud ringer foo.

963
00:46:34,910 --> 00:46:37,340
Och så då huvud samtal foo.

964
00:46:37,340 --> 00:46:40,408
Låt oss göra detta.

965
00:46:40,408 --> 00:46:44,720

966
00:46:44,720 --> 00:46:46,990
Så vi har vår stack.

967
00:46:46,990 --> 00:46:49,090
Och huvud har en stack ram
vid bottnen.

968
00:46:49,090 --> 00:46:51,860

969
00:46:51,860 --> 00:46:53,250
Vid något tillfälle, huvud samtal foo.

970
00:46:53,250 --> 00:46:55,390
Tja, omedelbart, huvud samtal foo.

971
00:46:55,390 --> 00:46:57,130
Och så foo får sin egen stack ram.

972
00:46:57,130 --> 00:46:59,650

973
00:46:59,650 --> 00:47:02,220
>> Nu, någon gång, foo
kommer att återvända.

974
00:47:02,220 --> 00:47:06,810
Och gick foo avkastning, måste vi veta på
vilken kodrad inuti huvud vi

975
00:47:06,810 --> 00:47:10,610
var för att veta var
Vi bör återupptas i main.

976
00:47:10,610 --> 00:47:13,100
Vi kan kalla foo från helhet
massa olika ställen.

977
00:47:13,100 --> 00:47:14,620
Hur vet vi var de ska återvända?

978
00:47:14,620 --> 00:47:16,460
Tja, vi måste lagra det någonstans.

979
00:47:16,460 --> 00:47:23,010
>> Så någonstans runt här, vi lagrar
där vi bör återgå till en gång

980
00:47:23,010 --> 00:47:24,070
foo avkastning.

981
00:47:24,070 --> 00:47:26,350
Och detta är den returadress.

982
00:47:26,350 --> 00:47:30,490
Så hur en motståndare kan utnyttja
av detta är det faktum att

983
00:47:30,490 --> 00:47:37,550
denna buffert c lagras, låt oss
säga, här är c..

984
00:47:37,550 --> 00:47:39,690
Så vi har 12 byte för c..

985
00:47:39,690 --> 00:47:40,540
Det här är c..

986
00:47:40,540 --> 00:47:43,030
Och detta är foo stack ring.

987
00:47:43,030 --> 00:47:49,970
Så om det skadliga användaren anger mer
byte än 12 eller så anger ett kommando

988
00:47:49,970 --> 00:47:54,570
line argument som är längre än 12
tecken, då vi kommer att

989
00:47:54,570 --> 00:47:57,540
flöda över denna buffert.

990
00:47:57,540 --> 00:47:59,910
>> Vi kan hålla igång.

991
00:47:59,910 --> 00:48:02,220
Och någon gång, vi går långt
nog att vi börjar

992
00:48:02,220 --> 00:48:05,120
skriva över denna returadress.

993
00:48:05,120 --> 00:48:08,310
Så när vi skriver över avsändaradressen,
detta innebär att när foo

994
00:48:08,310 --> 00:48:14,220
avkastning, vi återvänder till varhelst
angripare säger till den att genom

995
00:48:14,220 --> 00:48:19,490
oavsett värde det in, oberoende av hur
tecken användaren angett.

996
00:48:19,490 --> 00:48:24,320
Och så om den angripare är att
särskilt smart, kan han ha denna

997
00:48:24,320 --> 00:48:29,255
återvända till någonstans i printDef
funktion eller någonstans i malloc

998
00:48:29,255 --> 00:48:31,830
funktion, var som helst godtycklig.

999
00:48:31,830 --> 00:48:38,420
>> Men ännu mer smart är det som om han har
användaren återvända till just här.

1000
00:48:38,420 --> 00:48:41,920
Och då du börjar köra
dessa som rader kod.

1001
00:48:41,920 --> 00:48:46,610
Så på den punkten, kan användaren ange
vad han vill in i denna region.

1002
00:48:46,610 --> 00:48:52,210
Och han har fullständig kontroll
över ditt program.

1003
00:48:52,210 --> 00:48:53,460
Frågor på det?

1004
00:48:53,460 --> 00:48:56,380

1005
00:48:56,380 --> 00:49:00,970
Så nästa fråga är klar
reimplementation av foo på ett sådant sätt

1006
00:49:00,970 --> 00:49:02,620
att det inte längre är utsatta.

1007
00:49:02,620 --> 00:49:03,870
>> Så det finns ett par sätt
du kunde ha gjort det här.

1008
00:49:03,870 --> 00:49:10,900

1009
00:49:10,900 --> 00:49:13,330
Vi har fortfarande c endast
vara av längden 12.

1010
00:49:13,330 --> 00:49:16,480
Du kan ha ändrat detta
som en del av lösningen.

1011
00:49:16,480 --> 00:49:18,930
Vi har också lagt till en kontroll att göra
säkert bar var inte noll.

1012
00:49:18,930 --> 00:49:24,460
Även om du inte behöver
att för full poäng.

1013
00:49:24,460 --> 00:49:27,690
Så vi kollar först
stränglängd bar.

1014
00:49:27,690 --> 00:49:31,650
Om det är större än 12, då
faktiskt inte göra kopian.

1015
00:49:31,650 --> 00:49:33,010
Så det är ett sätt att fastställa det.

1016
00:49:33,010 --> 00:49:36,750
>> Ett annat sätt att fastställa att det är i stället för
har c bara ha längden 12, har det

1017
00:49:36,750 --> 00:49:39,310
ha längden strlen (bar).

1018
00:49:39,310 --> 00:49:43,370
Ett annat sätt att fastställa att det är
att faktiskt bara tillbaka.

1019
00:49:43,370 --> 00:49:46,690
Så om du hade just fått bort alla
detta, om du bara hade tagit bort alla

1020
00:49:46,690 --> 00:49:51,830
rader kod, skulle du ha fått
full kredit, eftersom denna funktion

1021
00:49:51,830 --> 00:49:54,150
egentligen inte uträtta något.

1022
00:49:54,150 --> 00:49:57,650
Den kopierar kommandoraden
argument i någon samling i

1023
00:49:57,650 --> 00:49:59,960
dess lokala stacken ramen.

1024
00:49:59,960 --> 00:50:01,310
Och sedan den saken återvänder.

1025
00:50:01,310 --> 00:50:04,020
Och vad det åstadkommit är borta.

1026
00:50:04,020 --> 00:50:09,740
Så avkastningen var också en tillräcklig
sätt att få full kredit.

1027
00:50:09,740 --> 00:50:13,425
>> DAVID J. MALAN: Inte riktigt anda
frågan men acceptabelt per den

1028
00:50:13,425 --> 00:50:15,580
spec ändå.

1029
00:50:15,580 --> 00:50:18,260
>> ROB BOWDEN: Frågor om något av detta?

1030
00:50:18,260 --> 00:50:22,270
En sak som man åtminstone
behövs för att ha kompilera kod.

1031
00:50:22,270 --> 00:50:24,810
Så även om du tekniskt sett inte är
sårbara om din kod inte

1032
00:50:24,810 --> 00:50:29,130
sammanställa, vi inte acceptera det.

1033
00:50:29,130 --> 00:50:31,350
Inga frågor?

1034
00:50:31,350 --> 00:50:33,320
OK.

1035
00:50:33,320 --> 00:50:34,580
>> DAVID J. MALAN: Vill du ha
att säga denna 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 den här, det här
var antingen bra eller dåliga nyheter.

1038
00:50:40,470 --> 00:50:43,870
Detta är bokstavligen samma problem
som den första frågesporten.

1039
00:50:43,870 --> 00:50:46,140
Och det är nästan samma
problem som pset1.

1040
00:50:46,140 --> 00:50:49,980
Men det var avsiktligt förenklats för att vara
en enklare pyramid, en som kan vara

1041
00:50:49,980 --> 00:50:52,330
lösas med en något
enklare iteration.

1042
00:50:52,330 --> 00:50:55,680
Och egentligen, vad vi fick på
här var inte så mycket logik,

1043
00:50:55,680 --> 00:50:58,100
därför sannolikt, vid det här laget, du
bekvämare än du var

1044
00:50:58,100 --> 00:51:01,850
i veckan en med för slingor eller varför loopar,
men egentligen för att reta ifrån varandra att

1045
00:51:01,850 --> 00:51:04,790
du är lite bekväm med
uppfattningen att PHP är inte bara om vad

1046
00:51:04,790 --> 00:51:05,290
programmering.

1047
00:51:05,290 --> 00:51:07,820
Den kan faktiskt användas som ett språk
att skriva kommandoraden program.

1048
00:51:07,820 --> 00:51:10,060
>> Och faktiskt, det är vad vi försökte
för att uppmärksamma er på.

1049
00:51:10,060 --> 00:51:12,060
Detta är en kommandorad PHP-program.

1050
00:51:12,060 --> 00:51:16,690
Så C-kod här, medan korrekt
i C, inte korrigera för PHP.

1051
00:51:16,690 --> 00:51:17,940
Men koden är egentligen samma.

1052
00:51:17,940 --> 00:51:21,720
Om du jämför de lösningar för Quiz
0 mot Quiz 1, ser du att

1053
00:51:21,720 --> 00:51:25,630
det är nästan identiska, med undantag för
några dollartecken och för

1054
00:51:25,630 --> 00:51:27,250
frånvaron av en datatyp.

1055
00:51:27,250 --> 00:51:31,720
I synnerhet om vi tar en titt här,
ser du att vi iterera, i detta

1056
00:51:31,720 --> 00:51:33,730
fall, från 1 upp till 7.

1057
00:51:33,730 --> 00:51:34,910
>> Vi kunde ha gjort det 0 index.

1058
00:51:34,910 --> 00:51:37,320
Men ibland, jag tror att det bara
mentalt lättare att tänka på saker

1059
00:51:37,320 --> 00:51:38,200
från 1 till 7.

1060
00:51:38,200 --> 00:51:40,300
Om du vill ha ett kvarter, sedan två
block, sedan tre, sedan

1061
00:51:40,300 --> 00:51:41,770
prick, prick, prick sju.

1062
00:51:41,770 --> 00:51:45,960
Vi har j initieras till 1
och sedan räknar upp till mig.

1063
00:51:45,960 --> 00:51:48,150
Och allting här är
i övrigt identisk.

1064
00:51:48,150 --> 00:51:49,790
Men värt att notera är
ett par saker.

1065
00:51:49,790 --> 00:51:53,230
Vi ger dig dessa två linjer, denna första
en, goofily namnges som ett shebang

1066
00:51:53,230 --> 00:51:54,560
för kraftig smäll.

1067
00:51:54,560 --> 00:51:58,770
Och som bara anger sökvägen, den
mapp, i vilken ett program kan vara

1068
00:51:58,770 --> 00:52:02,160
fann att du vill använda
att tolka den här filen.

1069
00:52:02,160 --> 00:52:04,710
>> Och sedan raden efter att av
Naturligtvis innebär skriva PHP-läge.

1070
00:52:04,710 --> 00:52:07,740
Och linjen längst ner
innebär exit PHP-läge.

1071
00:52:07,740 --> 00:52:09,740
Och detta fungerar i allmänhet med
tolkade språk.

1072
00:52:09,740 --> 00:52:14,370
Det är ganska irriterande om du skriver ett
program i en fil som heter foo.php.

1073
00:52:14,370 --> 00:52:17,320
Och då användarna måste bara
minns, OK, för att köra det här programmet, jag

1074
00:52:17,320 --> 00:52:22,320
måste skriva "php utrymme foo.php." Kind
av irriterande om inte annat.

1075
00:52:22,320 --> 00:52:25,270
Och det också avslöjar att ditt program
är skriven i PHP, vilket är inte allt

1076
00:52:25,270 --> 00:52:27,060
att belysa för användaren.

1077
00:52:27,060 --> 00:52:30,100
>> Så du kan ta bort. Php helt och hållet
minns från föreläsningen.

1078
00:52:30,100 --> 00:52:35,690
Och du kan faktiskt göra. / Foo om
du har chmodded det genom att göra det

1079
00:52:35,690 --> 00:52:36,500
körbar.

1080
00:52:36,500 --> 00:52:39,630
Så chmod a + x foo skulle ha gjort det.

1081
00:52:39,630 --> 00:52:41,460
Och om du också lägga till Shebang här.

1082
00:52:41,460 --> 00:52:45,320
Men egentligen var det problem att få på
skriva ut ungefär så här.

1083
00:52:45,320 --> 00:52:51,100
Ingen HTML, ingen C-kod säkert,
bara några PHP.

1084
00:52:51,100 --> 00:52:54,100
Så Milo återvände sedan i problem 25.

1085
00:52:54,100 --> 00:52:58,050
Och i 25, du fick följande
skelett-kod, som var en

1086
00:52:58,050 --> 00:52:59,730
ganska enkel webbsida.

1087
00:52:59,730 --> 00:53:04,230
Och den saftiga delen HTML-wise var nere
här, där vi har insidan av kroppen

1088
00:53:04,230 --> 00:53:09,160
en form som har en unik ID-ingångar
inuti vilken var två ingångar, en

1089
00:53:09,160 --> 00:53:11,950
med en idé om namn, en
med en idé om knappen.

1090
00:53:11,950 --> 00:53:14,240
>> Den första var typ text, den
andra av typen in.

1091
00:53:14,240 --> 00:53:16,930
Och så vi gav dig, faktiskt, mer
ingredienser än vad du behövde, bara så

1092
00:53:16,930 --> 00:53:19,230
ni hade alternativ med vilka
att lösa detta problem.

1093
00:53:19,230 --> 00:53:21,130
Du behöver inte strikt behöver
alla dessa ID.

1094
00:53:21,130 --> 00:53:23,580
Men det tillåter dig att lösa
det på olika sätt.

1095
00:53:23,580 --> 00:53:27,050
Och uppe i toppen, märker att
målet var att utlösa

1096
00:53:27,050 --> 00:53:27,960
ett fönster så här -

1097
00:53:27,960 --> 00:53:28,780
Hej, Milo! -

1098
00:53:28,780 --> 00:53:31,270
att dyka upp i webbläsaren med hjälp av
super enkelt, om

1099
00:53:31,270 --> 00:53:33,190
inte ful, varningsfunktion.

1100
00:53:33,190 --> 00:53:37,480
Och så, i slutändan leder detta
begreppsmässigt på något sätt lyssna efter

1101
00:53:37,480 --> 00:53:41,290
inlagor i form klientsidan
, Inte på serversidan, på något sätt

1102
00:53:41,290 --> 00:53:45,640
svara på detta påstående genom
ta tag i värde som användaren skrivit

1103
00:53:45,640 --> 00:53:50,120
in till namnfältet, och sedan
visar det i kroppen av en varning.

1104
00:53:50,120 --> 00:53:53,460
>> Så ett sätt du kan göra detta är med
jQuery, som ser lite

1105
00:53:53,460 --> 00:53:56,880
syntaktiskt förvirrande i början.

1106
00:53:56,880 --> 00:54:00,760
Du kan göra detta med ren DOM-kod -
document.getelement med ID.

1107
00:54:00,760 --> 00:54:02,530
Men låt oss ta en titt på denna version.

1108
00:54:02,530 --> 00:54:05,110
Jag har ett par viktiga
linjer först.

1109
00:54:05,110 --> 00:54:09,460
Så en, har vi denna linje, vilket är
identiskt med det som du kanske har sett

1110
00:54:09,460 --> 00:54:13,830
i, tror jag, form2.html
från klass i vecka 9.

1111
00:54:13,830 --> 00:54:16,960
Och detta är bara säga, exekvera
följande kod när

1112
00:54:16,960 --> 00:54:18,430
dokumentet är färdigt.

1113
00:54:18,430 --> 00:54:21,770
Detta är viktigt bara för att
HTML-sidor läses uppifrån och

1114
00:54:21,770 --> 00:54:23,280
botten, vänster till höger.

1115
00:54:23,280 --> 00:54:27,910
>> Och därför, om du försöker att göra
något i koden här uppe till viss DOM

1116
00:54:27,910 --> 00:54:31,560
element, en del HTML-tagg, det är ner
Här, du gör det för tidigt,

1117
00:54:31,560 --> 00:54:34,220
eftersom detta har inte ens
lästs in i minnet.

1118
00:54:34,220 --> 00:54:37,740
Så genom att säga detta document.ready
linje, vi säger,

1119
00:54:37,740 --> 00:54:39,040
här är lite kod, webbläsare.

1120
00:54:39,040 --> 00:54:42,440
Men inte utföra detta tills hela
dokumentet är färdigt, är att DOM

1121
00:54:42,440 --> 00:54:44,320
träd förekommer i minnet.

1122
00:54:44,320 --> 00:54:47,110
Den här är lite mer
okomplicerad, om syntaktiskt en

1123
00:54:47,110 --> 00:54:51,890
lite annorlunda, då jag säger, grab
HTML-element vars unika

1124
00:54:51,890 --> 00:54:53,560
Identifieraren är ingångar.

1125
00:54:53,560 --> 00:54:56,220
Det är vad det hash-taggen
betecknar den unika ID.

1126
00:54:56,220 --> 00:54:58,070
Och då jag ringer. Skicka.

1127
00:54:58,070 --> 00:55:01,660
>> So. Inkomma här är en funktion, annars
känd som en metod, som är

1128
00:55:01,660 --> 00:55:05,850
insidan av objekt på vänster
sida där som jag inte lyfta.

1129
00:55:05,850 --> 00:55:08,990
Så om du tänker på insatsvaror som ett objekt
i minnet - och faktiskt är det.

1130
00:55:08,990 --> 00:55:10,440
Det är en nod i ett träd -

1131
00:55:10,440 --> 00:55:16,580
. In medel när denna form med
detta ID lämnas in, exekvera

1132
00:55:16,580 --> 00:55:17,700
följande kod.

1133
00:55:17,700 --> 00:55:20,290
Jag bryr mig inte vad namnet på den
Funktionen är att jag utför.

1134
00:55:20,290 --> 00:55:23,760
Så här jag använder, som tidigare, vad är
kallas lambda funktion eller

1135
00:55:23,760 --> 00:55:24,720
anonym funktion.

1136
00:55:24,720 --> 00:55:27,640
Det är inte alls intellektuellt
intressant än den har inget namn,

1137
00:55:27,640 --> 00:55:30,220
vilket är bra om du bara
någonsin kommer att kalla det en gång.

1138
00:55:30,220 --> 00:55:34,490
Och inne där jag faktiskt hantera
inlämnandet av formuläret.

1139
00:55:34,490 --> 00:55:36,810
Jag förklarar först en variabel
kallas värde.

1140
00:55:36,810 --> 00:55:40,610
Och vad är då effekten av detta
markerad del här nu?

1141
00:55:40,610 --> 00:55:44,755
Vad gör det på ett
hög nivå för mig?

1142
00:55:44,755 --> 00:55:48,539
>> Publik: Det blir det värde som
användaren inte i HTML-koden nedan.

1143
00:55:48,539 --> 00:55:50,920
Det blir detta ID och sedan
finner värdet av det.

1144
00:55:50,920 --> 00:55:51,590
>> DAVID J. MALAN: Exakt.

1145
00:55:51,590 --> 00:55:54,300
Det tar tag i noden, vars unika
Identifieraren är känt.

1146
00:55:54,300 --> 00:55:56,900
Det blir det värde i den och som
är förmodligen det som användaren

1147
00:55:56,900 --> 00:55:58,190
skrev sig själv.

1148
00:55:58,190 --> 00:56:01,020
Och då den lagrar det i
variabel som heter värde.

1149
00:56:01,020 --> 00:56:03,720
Inom parentes kan man också ha
gjort det lite annorlunda.

1150
00:56:03,720 --> 00:56:09,250
Helt acceptabelt genom att göra något
lögn var värdet 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
Och det är därför det är lite
jobbigt att inte använda jQuery.

1154
00:56:15,460 --> 00:56:16,710
"Namn". Värde.

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
Olika sätt att göra detta. jQuery bara
tenderar att vara lite mer kortfattad och

1158
00:56:22,770 --> 00:56:25,230
definitivt mer populärt
bland programmerare.

1159
00:56:25,230 --> 00:56:27,590
>> Nu, jag gör lite av en sanity
ta, eftersom det i det problemet

1160
00:56:27,590 --> 00:56:30,820
uttalande vi uttryckligen sagt, om
Användaren har ännu inte skrivit sin

1161
00:56:30,820 --> 00:56:32,580
namn, visar inte ett larm.

1162
00:56:32,580 --> 00:56:35,390
Men du kan kontrollera om det, genom att bara
kontroll för den tomma strängen för en

1163
00:56:35,390 --> 00:56:37,850
quote-unquote om det finns
ingenting faktiskt där.

1164
00:56:37,850 --> 00:56:40,880
Men om det inte är lika med citat-unquote,
Jag vill ringa varningar.

1165
00:56:40,880 --> 00:56:45,610
Och det intressanta här är att
vi använder plus aktör och som

1166
00:56:45,610 --> 00:56:48,130
gör vad i JavaScript?

1167
00:56:48,130 --> 00:56:48,740
Sammanfoga.

1168
00:56:48,740 --> 00:56:50,690
Så det är som phps prick operatör.

1169
00:56:50,690 --> 00:56:52,820
Samma idé, något annorlunda syntax.

1170
00:56:52,820 --> 00:56:55,280
Och jag bara skapa den sträng som
du såg på skärmen skott -

1171
00:56:55,280 --> 00:56:57,750
Hej, så och så.

1172
00:56:57,750 --> 00:56:59,200
>> Och sedan i minsta detalj är det.

1173
00:56:59,200 --> 00:57:04,970
Varför jag returnera false insida
av denna anonyma funktion?

1174
00:57:04,970 --> 00:57:07,420
>> PUBLIK: Det finns inget värde.

1175
00:57:07,420 --> 00:57:09,380
Du sätter den i formen.

1176
00:57:09,380 --> 00:57:12,320

1177
00:57:12,320 --> 00:57:16,730
Den säger bara, om värdet inte
lika tomt, så gör det.

1178
00:57:16,730 --> 00:57:20,040

1179
00:57:20,040 --> 00:57:20,940
Det fanns en tomt i detta påstående.

1180
00:57:20,940 --> 00:57:21,170
>> David J. MALAN: OK.

1181
00:57:21,170 --> 00:57:21,640
Försiktig.

1182
00:57:21,640 --> 00:57:22,830
Det finns ingen annan här.

1183
00:57:22,830 --> 00:57:25,510
Och det retur falskt är utanför
av om förhållandena.

1184
00:57:25,510 --> 00:57:29,470
Så detta markerade linjen, returnera false,
utför oavsett vad när

1185
00:57:29,470 --> 00:57:32,310
formuläret skickas.

1186
00:57:32,310 --> 00:57:36,810
Vad åter falsk insidan av denna
händelsehanterare, som det kallas,

1187
00:57:36,810 --> 00:57:38,450
den aktuella händelsen
vara underkastelse?

1188
00:57:38,450 --> 00:57:42,350

1189
00:57:42,350 --> 00:57:44,470
>> PUBLIK: Eftersom det
bara händer en gång.

1190
00:57:44,470 --> 00:57:45,320
>> DAVID J. MALAN: händer bara en gång.

1191
00:57:45,320 --> 00:57:46,821
Inte riktigt.

1192
00:57:46,821 --> 00:57:47,292
Yeah?

1193
00:57:47,292 --> 00:57:50,589
>> PUBLIK: Det hindrar formen från
lämna in till standardbeteendet,

1194
00:57:50,589 --> 00:57:52,480
vilket skulle göra sidan omladdning.

1195
00:57:52,480 --> 00:57:53,110
>> DAVID J. MALAN: Exakt.

1196
00:57:53,110 --> 00:57:56,490
Så jag överbelasta termen in här,
eftersom jag säger, är den form

1197
00:57:56,490 --> 00:57:57,670
lämnas in.

1198
00:57:57,670 --> 00:58:02,240
Men som du föreslår, det är faktiskt inte
lämnats in i den sanna HTTP vägen.

1199
00:58:02,240 --> 00:58:06,870
När du klickar på Skicka, på grund av vår
onSubmit handler, vi avlyssning

1200
00:58:06,870 --> 00:58:09,040
det formulär så att säga.

1201
00:58:09,040 --> 00:58:11,290
Vi ska sedan göra vår grej
med JavaScript-kod.

1202
00:58:11,290 --> 00:58:14,070
Men jag medvetet åter falskt,
eftersom det som jag inte vill ska hända en

1203
00:58:14,070 --> 00:58:18,430
ögonblick senare är för hela formen
själv som ska lämnas in till webben

1204
00:58:18,430 --> 00:58:22,800
server med Nyckelvärdesparen genom att ändra
URL för att vara något liknande

1205
00:58:22,800 --> 00:58:26,180
q = katter eller vad vi gjorde,
till exempel, i klassen.

1206
00:58:26,180 --> 00:58:29,640
Jag vill inte att det ska ske, eftersom
det finns ingen server lyssnar för detta

1207
00:58:29,640 --> 00:58:30,690
bilda underkastelse.

1208
00:58:30,690 --> 00:58:32,320
Det är helt gjort i JavaScript-kod.

1209
00:58:32,320 --> 00:58:35,760
Och det är därför jag inte ens har en
åtgärder attribut på min blankett, eftersom jag

1210
00:58:35,760 --> 00:58:38,870
har inte för avsikt att detta skall
någonsin gå till servern.

1211
00:58:38,870 --> 00:58:40,780
>> Så det lämnas in.

1212
00:58:40,780 --> 00:58:44,340
Men vi avlyssnar formuläret
underkastelse och förhindra den förvalda

1213
00:58:44,340 --> 00:58:47,477
beteende, vilket är att faktiskt
gå hela vägen till servern.

1214
00:58:47,477 --> 00:58:48,730
>> PUBLIK: Så håller det på klientsidan.

1215
00:58:48,730 --> 00:58:49,780
>> DAVID J. MALAN: Hålla
det klientsidan.

1216
00:58:49,780 --> 00:58:51,030
Exakt rätt.

1217
00:58:51,030 --> 00:58:53,240

1218
00:58:53,240 --> 00:58:55,757
Nästa upp 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å denna första fråga var allmänt
grov för människor.

1222
00:59:04,990 --> 00:59:07,270
Även om de senare gick bättre.

1223
00:59:07,270 --> 00:59:12,260
Så du var tvungen att välja rätt uppgifter
typer för båda dessa kolumner.

1224
00:59:12,260 --> 00:59:17,750
Och båda dessa har någon
saker om dem som

1225
00:59:17,750 --> 00:59:20,620
göra valet svårt.

1226
00:59:20,620 --> 00:59:24,430
Så int var inte ett giltigt
skriver för numret.

1227
00:59:24,430 --> 00:59:29,410
Orsaken är en 12-siffrig konto
nummer, är inte tillräckligt stor för att en int

1228
00:59:29,410 --> 00:59:31,070
lagra totala siffror.

1229
00:59:31,070 --> 00:59:36,570
Så ett giltigt val skulle ha varit en stor
int om du råkar veta att.

1230
00:59:36,570 --> 00:59:42,090
Ett annat val skulle ha varit
en röding gäller längd 12.

1231
00:59:42,090 --> 00:59:44,560
Så någon av dem skulle ha fungerat.

1232
00:59:44,560 --> 00:59:46,100
Int skulle inte.

1233
00:59:46,100 --> 00:59:50,170
>> Nu, balans, tänker tillbaka på pset7.

1234
00:59:50,170 --> 00:59:59,540
Så vi använde specifikt decimaltal till
lagra värdet av aktier eller -

1235
00:59:59,540 --> 01:00:00,550
>> DAVID J. MALAN: Cash.

1236
01:00:00,550 --> 01:00:01,060
>> ROB BOWDEN: Cash.

1237
01:00:01,060 --> 01:00:05,710
Vi använde decimal för att lagra den mängd
pengar som användaren har för tillfället.

1238
01:00:05,710 --> 01:00:10,950
Så anledningen till att vi gör det är
eftersom, kom ihåg, flyter.

1239
01:00:10,950 --> 01:00:12,480
Det finns flyttal i precision.

1240
01:00:12,480 --> 01:00:18,200
Det kan inte exakt förvara kontanter
värden som vi vill ha här.

1241
01:00:18,200 --> 01:00:23,630
Så decimal kan exakt butik
något att, säga, två decimaler.

1242
01:00:23,630 --> 01:00:27,630
Därför balans, vi vill ha det
vara decimala och inte flyta.

1243
01:00:27,630 --> 01:00:30,230
>> DAVID J. MALAN: Och dessutom, också, fast
det kanske varit smart i andra

1244
01:00:30,230 --> 01:00:32,760
sammanhang att tänka, kanske detta
är en chans för en int.

1245
01:00:32,760 --> 01:00:34,420
Jag ska bara hålla reda på
saker i småpengar.

1246
01:00:34,420 --> 01:00:38,670
Eftersom vi visade tydligt standard
Värdet av att vara 100,00, att

1247
01:00:38,670 --> 01:00:40,380
betyder att det kan bara vara en int.

1248
01:00:40,380 --> 01:00:45,310
Och en annan finess också med nummer
var att det inte var tänkt

1249
01:00:45,310 --> 01:00:46,180
att vara en kuggfråga.

1250
01:00:46,180 --> 01:00:49,860
Men minns att en int i MySQL,
i C, åtminstone på liknande

1251
01:00:49,860 --> 01:00:51,440
apparat, är 32-bitars.

1252
01:00:51,440 --> 01:00:53,960
Och även om vi förväntar oss inte att du
vet exakt hur många siffror som

1253
01:00:53,960 --> 01:00:56,910
medel, kommer ihåg att det största antalet
du kan representera potentiellt

1254
01:00:56,910 --> 01:01:00,710
med ett 32-bitars nummer är ungefär vad?

1255
01:01:00,710 --> 01:01:02,760
>> Vilket nummer har vi alltid säger?

1256
01:01:02,760 --> 01:01:04,530
2 till 32, vilket är vad ungefär?

1257
01:01:04,530 --> 01:01:07,492

1258
01:01:07,492 --> 01:01:08,780
Du behöver inte veta exakt.

1259
01:01:08,780 --> 01:01:10,580
Men i stort sett är bra i livet.

1260
01:01:10,580 --> 01:01:12,200
Det är ungefär 4 miljarder.

1261
01:01:12,200 --> 01:01:14,430
Så vi har sagt att ett par gånger.

1262
01:01:14,430 --> 01:01:16,360
Jag vet att jag har sagt att ett par gånger.

1263
01:01:16,360 --> 01:01:17,670
Och det är ungefär 4 miljarder.

1264
01:01:17,670 --> 01:01:19,710
Och det är en bra regel
av tummen för att veta.

1265
01:01:19,710 --> 01:01:21,880
Om du har 8 bitar, 256
är det magiska numret.

1266
01:01:21,880 --> 01:01:24,160
Om du har 32 bitar, 4
miljard ge eller ta.

1267
01:01:24,160 --> 01:01:27,140
Så om du bara skriver ner 4 miljarder,
ser du att det är färre siffror än

1268
01:01:27,140 --> 01:01:30,970
12, vilket innebär att det är helt klart inte
tillräckligt uttrycksfullhet för att fånga en

1269
01:01:30,970 --> 01:01:34,220
12-siffriga kontonummer.

1270
01:01:34,220 --> 01:01:34,940
>> ROB BOWDEN: OK.

1271
01:01:34,940 --> 01:01:38,520
Så de andra som gick bättre.

1272
01:01:38,520 --> 01:01:40,900
Så antar att banken
medför en $ 20 per månad

1273
01:01:40,900 --> 01:01:42,400
underhållsavgift på alla konton.

1274
01:01:42,400 --> 01:01:45,506
Med vilken SQL-fråga kan banken
dra av $ 20 från varje greve, även om

1275
01:01:45,506 --> 01:01:47,520
det resulterar i en del negativa saldon?

1276
01:01:47,520 --> 01:01:50,380
Så i princip finns det fyra
huvudsakliga typer av frågor -

1277
01:01:50,380 --> 01:01:52,840
infoga, markera, uppdatera och ta bort.

1278
01:01:52,840 --> 01:01:56,080
Så vad gör vi tror att vi är
kommer att använda här?

1279
01:01:56,080 --> 01:01:57,000
Uppdatera.

1280
01:01:57,000 --> 01:01:58,260
>> Så låt oss ta en titt.

1281
01:01:58,260 --> 01:02:04,290

1282
01:02:04,290 --> 01:02:05,870
Så här är vi uppdaterar.

1283
01:02:05,870 --> 01:02:09,900
Vad tabellen vi uppdaterar konton?

1284
01:02:09,900 --> 01:02:11,670
Så uppdatera konton.

1285
01:02:11,670 --> 01:02:15,390
Och sedan syntaxen säger, vad
i konton vi uppdaterar?

1286
01:02:15,390 --> 01:02:19,520
Tja, vi ställer balans lika med
nuvärdet av balans minus 20.

1287
01:02:19,520 --> 01:02:22,860
Så det här kommer att uppdatera alla rader
konton, subtrahera

1288
01:02:22,860 --> 01:02:26,250
$ 20 från balansen.

1289
01:02:26,250 --> 01:02:29,260
>> DAVID J. MALAN: Ett vanligt misstag här,
även om vi ibland förlät det,

1290
01:02:29,260 --> 01:02:32,990
var att faktiskt ha PHP-kod här
anropa frågefunktionen eller sätta

1291
01:02:32,990 --> 01:02:35,460
citattecken runt allt som
behövde inte vara där.

1292
01:02:35,460 --> 01:02:39,780
>> ROB BOWDEN: Kom ihåg att MySQL är
ett separat språk från PHP.

1293
01:02:39,780 --> 01:02:42,410
Vi råkar skriva MySQL i PHP.

1294
01:02:42,410 --> 01:02:46,180
Och PHP är sedan skicka det
över till MySQL-servern.

1295
01:02:46,180 --> 01:02:51,120
Men du behöver inte PHP för att
kommunicera med en MySQL-server.

1296
01:02:51,120 --> 01:02:51,730
>> DAVID J. MALAN: Exakt.

1297
01:02:51,730 --> 01:02:54,240
Så inga variabler med dollartecken
bör i detta sammanhang.

1298
01:02:54,240 --> 01:02:59,550
Det kan bara göra allt matten
i själva databasen.

1299
01:02:59,550 --> 01:03:00,080
>> ROB BOWDEN: OK.

1300
01:03:00,080 --> 01:03:01,300
Så nästa.

1301
01:03:01,300 --> 01:03:02,731
Är det nästa?

1302
01:03:02,731 --> 01:03:03,210
Yeah.

1303
01:03:03,210 --> 01:03:06,570
Så med vilken SQL-fråga kan banken
hämta kontonumren i sin

1304
01:03:06,570 --> 01:03:09,300
rikaste kunderna, de med
saldon som överstiger 1.000?

1305
01:03:09,300 --> 01:03:13,280
Så vilken av de fyra huvudtyperna
ska vi vill ha här?

1306
01:03:13,280 --> 01:03:14,430
Välj.

1307
01:03:14,430 --> 01:03:16,650
Så vi vill markera.

1308
01:03:16,650 --> 01:03:17,610
Vad vill vi välja?

1309
01:03:17,610 --> 01:03:19,380
Vilken kolumn vill vi välja?

1310
01:03:19,380 --> 01:03:20,970
Vi kommer specifikt vill
för att välja nummer.

1311
01:03:20,970 --> 01:03:23,910
Men om du sa stjärna, vi
också accepterat att.

1312
01:03:23,910 --> 01:03:25,820
>> Så välj nummer från vilken tabell?

1313
01:03:25,820 --> 01:03:26,640
Konton.

1314
01:03:26,640 --> 01:03:28,370
Och då det tillstånd vi vill ha?

1315
01:03:28,370 --> 01:03:30,140
När balans som är större än 1000.

1316
01:03:30,140 --> 01:03:31,720
Vi accepterade också större
än eller lika.

1317
01:03:31,720 --> 01:03:35,230

1318
01:03:35,230 --> 01:03:36,190
Sista.

1319
01:03:36,190 --> 01:03:42,940
Med vilken SQL-fråga kan banken
nära, dvs ta bort varje konto som

1320
01:03:42,940 --> 01:03:44,480
har ett saldo på $ 0?

1321
01:03:44,480 --> 01:03:47,620
Så vilken av de fyra är vi
kommer att vilja använda?

1322
01:03:47,620 --> 01:03:48,320
Ta bort.

1323
01:03:48,320 --> 01:03:50,180
Så syntaxen för det?

1324
01:03:50,180 --> 01:03:51,890
Radera från vilken tabell?

1325
01:03:51,890 --> 01:03:53,550
Konton.

1326
01:03:53,550 --> 01:03:55,790
Och då det tillstånd som
Vi vill ta bort -

1327
01:03:55,790 --> 01:03:57,280
där balansen är lika med noll.

1328
01:03:57,280 --> 01:04:03,050
Så ta bort alla rader från konton
där saldot är noll.

1329
01:04:03,050 --> 01:04:04,300
Frågor om någon av dessa?

1330
01:04:04,300 --> 01:04:08,840

1331
01:04:08,840 --> 01:04:10,260
Vill du köa?

1332
01:04:10,260 --> 01:04:11,200
>> DAVID J. MALAN: Kö guide.

1333
01:04:11,200 --> 01:04:17,110
Så i den här, vi gav dig en något
välbekant struktur som vi utforskade en

1334
01:04:17,110 --> 01:04:20,450
bit i klass jämsides av structs,
vilket var en data

1335
01:04:20,450 --> 01:04:21,910
struktur relaterade till innebörden.

1336
01:04:21,910 --> 01:04:24,670
Skillnaden dock med en kö är
att vi var tvungna att på något sätt komma ihåg vem

1337
01:04:24,670 --> 01:04:27,900
var längst fram i kön, i stor
del så att vi kunde göra mer

1338
01:04:27,900 --> 01:04:30,530
effektiv användning av minnet, åtminstone
om vi med hjälp av en matris.

1339
01:04:30,530 --> 01:04:35,460
>> Därför minns, om vi har en array, om,
till exempel, är det på framsidan av

1340
01:04:35,460 --> 01:04:38,470
kön, om jag kommer in i kö här,
och sedan någon får i linje

1341
01:04:38,470 --> 01:04:42,710
bakom mig, bakom mig, bakom mig, och
en person kliver över gränsen, du

1342
01:04:42,710 --> 01:04:45,930
kunde, som vi såg några av våra mänskliga
frivilliga i klassen, har alla

1343
01:04:45,930 --> 01:04:47,100
flytta detta sätt.

1344
01:04:47,100 --> 01:04:50,880
Men i allmänhet, att ha alla göra
något som inte är den bästa användningen av tid

1345
01:04:50,880 --> 01:04:54,600
i ett program, eftersom det innebär att din
algoritmen körs i vad

1346
01:04:54,600 --> 01:04:56,520
asymptotisk gångtid?

1347
01:04:56,520 --> 01:04:57,420
Den är linjär.

1348
01:04:57,420 --> 01:04:59,600
>> Och jag känner att det är ganska dumt.

1349
01:04:59,600 --> 01:05:02,890
Om nästa person i raden är nästa
Den som har tänkt att gå in i

1350
01:05:02,890 --> 01:05:04,660
store, behöver de inte alla har
att röra sig tillsammans.

1351
01:05:04,660 --> 01:05:08,200
Bara låta den personen ska plockas bort
när tiden är inne, till exempel.

1352
01:05:08,200 --> 01:05:09,870
Så vi kan spara lite tid där.

1353
01:05:09,870 --> 01:05:14,840
Och så för att göra det ändå, innebär att
att chefen för kön eller

1354
01:05:14,840 --> 01:05:18,060
fram i kön kommer att
successivt gå djupare och djupare

1355
01:05:18,060 --> 01:05:23,340
i arrayen och så småningom kanske
faktiskt linda runt om vi använder en

1356
01:05:23,340 --> 01:05:25,790
array för att lagra människor
i denna kö.

1357
01:05:25,790 --> 01:05:28,390
Så du kan nästan tänka på
array som en cirkulär uppgifter

1358
01:05:28,390 --> 01:05:29,880
struktur i den meningen.

1359
01:05:29,880 --> 01:05:33,970
>> Så du på något sätt har att hålla reda på
storleken på det eller egentligen slutet på den

1360
01:05:33,970 --> 01:05:36,250
och sedan var början på den är.

1361
01:05:36,250 --> 01:05:39,490
Så föreslår vi att du deklarerar
en sådan kö, kallelse

1362
01:05:39,490 --> 01:05:41,330
det q, bara en bokstav.

1363
01:05:41,330 --> 01:05:44,570
Därefter föreslår vi att den främre vara
initialiseras till noll och att storleken

1364
01:05:44,570 --> 01:05:45,470
initialiseras till noll.

1365
01:05:45,470 --> 01:05:47,770
>> Så just nu, det finns inget
insidan av den kön.

1366
01:05:47,770 --> 01:05:50,910
Och vi ber dig att fylla i
genomförande av enqueue nedan i

1367
01:05:50,910 --> 01:05:55,250
sådant sätt att den funktionen lägger n till
slutet av q och sedan returnerar true.

1368
01:05:55,250 --> 01:05:58,690
Men om q är full eller negativt, det
Funktionen ska istället returnera false.

1369
01:05:58,690 --> 01:06:01,060
Och vi gav er ett par
antaganden.

1370
01:06:01,060 --> 01:06:04,320
Men de är inte riktigt funktionellt
relevant, finns just det bool,

1371
01:06:04,320 --> 01:06:06,690
eftersom tekniskt sett inte bool
finns i C om du inte har en

1372
01:06:06,690 --> 01:06:07,310
visst header-fil.

1373
01:06:07,310 --> 01:06:09,350
Så det var bara till att det inte
var inte det här ett trick

1374
01:06:09,350 --> 01:06:10,940
fråga sånt.

1375
01:06:10,940 --> 01:06:16,280
>> Så enqueue föreslog vi i urvalet
lösningar för att genomföra följande.

1376
01:06:16,280 --> 01:06:20,420
Man kontrollerar vi först den lätthet,
de lågt hängande frukter.

1377
01:06:20,420 --> 01:06:23,820
Om kön är full eller det nummer som
du försöker sätta in är mindre

1378
01:06:23,820 --> 01:06:26,380
än noll, som vi sade i
specifikation av problemet bör

1379
01:06:26,380 --> 01:06:30,320
inte tillåtas, eftersom vi bara är intresserad av
icke-negativa värden, så ska du

1380
01:06:30,320 --> 01:06:31,640
bara returnera false omedelbart.

1381
01:06:31,640 --> 01:06:33,820
Så några relativt enkla
felkontroll.

1382
01:06:33,820 --> 01:06:38,720
Om om du vill lägga till det faktiska
nummer, var du tvungen att göra lite

1383
01:06:38,720 --> 01:06:39,440
tänker här.

1384
01:06:39,440 --> 01:06:41,330
Och det är där det är lite irriterande
mentalt, eftersom du måste

1385
01:06:41,330 --> 01:06:43,000
räkna ut hur man hanterar wraparound.

1386
01:06:43,000 --> 01:06:46,870
>> Men fröet till idén här att det är av
intresse för oss är att wraparound

1387
01:06:46,870 --> 01:06:51,480
ofta innebär modulär aritmetik och
mod operatör, procentsidan,

1388
01:06:51,480 --> 01:06:55,140
där du kan gå från ett större värde
tillbaka till noll och sedan ett och två och

1389
01:06:55,140 --> 01:06:58,650
tre och sedan tillbaka runt till noll,
ett och två och tre och så vidare

1390
01:06:58,650 --> 01:06:59,380
igen och igen.

1391
01:06:59,380 --> 01:07:02,880
Så hur vi föreslår att göra detta är
att vi vill index till

1392
01:07:02,880 --> 01:07:05,850
array kallas tal där
våra heltal ljuga.

1393
01:07:05,850 --> 01:07:10,740
Men för att komma dit, vi först vill göra
oavsett storleken på kön är utan

1394
01:07:10,740 --> 01:07:14,080
Lägg sedan till att oavsett
framför listan är.

1395
01:07:14,080 --> 01:07:17,880
Och effekten av det är att sätta oss på
rätt position i kön och

1396
01:07:17,880 --> 01:07:20,970
inte utgå från att den första personen i raden
är i början, som han eller

1397
01:07:20,970 --> 01:07:24,130
hon absolut skulle vara om vi
också skiftande alla.

1398
01:07:24,130 --> 01:07:26,710
Men vi bara skapar arbete
för oss själva om vi tog

1399
01:07:26,710 --> 01:07:27,800
denna speciella väg.

1400
01:07:27,800 --> 01:07:29,330
>> Så vi kan hålla det relativt enkelt.

1401
01:07:29,330 --> 01:07:32,180
Vi måste komma ihåg att vi bara
lagt en int till kön.

1402
01:07:32,180 --> 01:07:35,850
Och då är vi tillbaka bara sant.

1403
01:07:35,850 --> 01:07:38,560
Under tiden, i dequeue, frågade vi
du göra följande.

1404
01:07:38,560 --> 01:07:42,260
Genomföra den på ett sådant sätt att det
dequeues, är som tar bort och avkastning,

1405
01:07:42,260 --> 01:07:44,190
int längst fram i kön.

1406
01:07:44,190 --> 01:07:46,410
För att ta bort int räcker det
att glömma det.

1407
01:07:46,410 --> 01:07:47,650
Du behöver inte åsidosätta sin bit.

1408
01:07:47,650 --> 01:07:48,820
Så det är fortfarande faktiskt där.

1409
01:07:48,820 --> 01:07:51,930
Precis som data på en hårddisk,
vi bara ignorera det faktum

1410
01:07:51,930 --> 01:07:52,970
att det nu finns.

1411
01:07:52,970 --> 01:07:55,520
Och om q är tomt, bör vi
istället tillbaka negativt 1.

1412
01:07:55,520 --> 01:07:56,750
Så det här känns godtyckliga.

1413
01:07:56,750 --> 01:08:01,640
Varför åter negativ 1
istället för falskt?

1414
01:08:01,640 --> 01:08:02,620
Yeah.

1415
01:08:02,620 --> 01:08:05,070
>> PUBLIK: Q lagrar
positiva värden.

1416
01:08:05,070 --> 01:08:10,950
Eftersom du bara lagra positiva värden
i k, är negativ ett fel.

1417
01:08:10,950 --> 01:08:11,510
>> DAVID J. MALAN: OK, sant.

1418
01:08:11,510 --> 01:08:14,850
Så eftersom vi bara lagra positiva
värden eller noll, då är det bra att

1419
01:08:14,850 --> 01:08:18,050
returnera ett negativt värde som en vaktpost
värde, en speciell symbol.

1420
01:08:18,050 --> 01:08:21,630
Men du skriva om historien där,
eftersom anledningen till att vi är bara

1421
01:08:21,630 --> 01:08:25,890
åter icke-negativa värden
är att vi vill

1422
01:08:25,890 --> 01:08:27,670
har en sentinel värde.

1423
01:08:27,670 --> 01:08:32,617
Så mer specifikt, varför inte bara
return false i fall av fel?

1424
01:08:32,617 --> 01:08:33,099
Yeah.

1425
01:08:33,099 --> 01:08:35,510
>> PUBLIK: Du har misslyckats
att returnera ett heltal.

1426
01:08:35,510 --> 01:08:36,630
>> DAVID J. MALAN: Exakt.

1427
01:08:36,630 --> 01:08:38,569
Och det är här C får
ganska begränsande.

1428
01:08:38,569 --> 01:08:40,590
Om du säger att du ska
att returnera en int, har du

1429
01:08:40,590 --> 01:08:41,279
returnera en int.

1430
01:08:41,279 --> 01:08:43,689
Du kan inte få lust och börja återvända
en bool eller en flottör eller en

1431
01:08:43,689 --> 01:08:45,040
sträng eller något liknande.

1432
01:08:45,040 --> 01:08:49,370
Nu, under tiden, JavaScript och PHP och
några andra språk kan, i själva verket,

1433
01:08:49,370 --> 01:08:51,310
har du åter olika
typer av värden.

1434
01:08:51,310 --> 01:08:54,819
Och det kan faktiskt vara till nytta, om
du kunde återvända positiva Ints, nollor,

1435
01:08:54,819 --> 01:08:59,439
negativa Ints, eller falskt eller null
även för att beteckna felet.

1436
01:08:59,439 --> 01:09:01,890
Men vi har inte så
mångsidighet i C.

1437
01:09:01,890 --> 01:09:04,569
>> Så med dequeue, vad vi
föreslå att göra är -

1438
01:09:04,569 --> 01:09:07,350

1439
01:09:07,350 --> 01:09:09,830
>> ROB BOWDEN: Du kan returnera false.

1440
01:09:09,830 --> 01:09:13,189
Det är bara det falska är hash
definiera falskt till noll.

1441
01:09:13,189 --> 01:09:16,000
Så om du returnera false,
du återvänder noll.

1442
01:09:16,000 --> 01:09:25,470
Och noll är en giltig sak i vår kö,
medan negativ 1 inte om

1443
01:09:25,470 --> 01:09:27,000
falska råkade vara negativ 1.

1444
01:09:27,000 --> 01:09:29,972
Men du borde inte ens
behöver veta det.

1445
01:09:29,972 --> 01:09:32,399
>> DAVID J. MALAN: Det är
varför jag inte säga det.

1446
01:09:32,399 --> 01:09:36,450
>> ROB BOWDEN: Men det var inte sant
att du inte kan returnera false.

1447
01:09:36,450 --> 01:09:37,700
>> DAVID J. MALAN: Visst.

1448
01:09:37,700 --> 01:09:40,920

1449
01:09:40,920 --> 01:09:44,240
Så dequeue, märker vi accepterar
ogiltig som dess argument.

1450
01:09:44,240 --> 01:09:45,479
Och det beror på att vi inte är
passerar något i.

1451
01:09:45,479 --> 01:09:48,359
Vi vill bara ta bort elementet
längst fram i kön.

1452
01:09:48,359 --> 01:09:49,819
Så hur kan vi gå om att göra detta?

1453
01:09:49,819 --> 01:09:51,290
Tja, först, låt oss göra detta
snabb sanity check.

1454
01:09:51,290 --> 01:09:53,350
Om köstorleken är 0, det finns
inget arbete att göra.

1455
01:09:53,350 --> 01:09:54,210
Avkastning negativ 1.

1456
01:09:54,210 --> 01:09:54,800
Klar.

1457
01:09:54,800 --> 01:09:56,340
Så det är några rader i mitt program.

1458
01:09:56,340 --> 01:09:58,180
Så bara fyra rader kvar.

1459
01:09:58,180 --> 01:10:01,310
>> Så här jag väljer att dekrementera
storleken.

1460
01:10:01,310 --> 01:10:04,620
Och nedräkning av storleken på ett effektivt sätt
betyder att jag glömmer

1461
01:10:04,620 --> 01:10:06,010
något är där inne.

1462
01:10:06,010 --> 01:10:09,910
Men jag måste också uppdatera där
framsida är siffrorna.

1463
01:10:09,910 --> 01:10:11,620
Så för att göra det, jag behöver
att göra två saker.

1464
01:10:11,620 --> 01:10:16,390
Måste jag först komma ihåg vad numret
är längst fram i kön,

1465
01:10:16,390 --> 01:10:17,860
eftersom jag behöver gå tillbaka det där.

1466
01:10:17,860 --> 01:10:20,910
Så jag vill inte av misstag glömmer
om det och sedan skriva över den.

1467
01:10:20,910 --> 01:10:22,840
Jag kommer bara att komma ihåg i en int.

1468
01:10:22,840 --> 01:10:27,310
>> Och nu, jag vill uppdatera
q.front skall q.front 1.

1469
01:10:27,310 --> 01:10:30,070
Så om detta var den första personen i
linje, nu, jag vill göra plus 1 till

1470
01:10:30,070 --> 01:10:31,930
peka på nästa person i kön.

1471
01:10:31,930 --> 01:10:33,420
Men jag måste hantera det omslutande.

1472
01:10:33,420 --> 01:10:37,270
Och om kapaciteten är en global konstant,
som kommer att tillåta mig att se till att

1473
01:10:37,270 --> 01:10:41,140
som jag pekar på den allra sista personen i
linje, kommer modulooperationen föra

1474
01:10:41,140 --> 01:10:43,840
mig tillbaka till noll vid
fram i kön.

1475
01:10:43,840 --> 01:10:46,050
Och som hanterar wraparound här.

1476
01:10:46,050 --> 01:10:48,950
Och då jag fortsätter att återvända n.

1477
01:10:48,950 --> 01:10:51,530
>> Nu, strängt taget, det gjorde jag inte
måste deklarera n.

1478
01:10:51,530 --> 01:10:53,880
Jag behövde inte ta tag i den och förvara den
temporärt, eftersom värdet är

1479
01:10:53,880 --> 01:10:54,740
fortfarande där.

1480
01:10:54,740 --> 01:10:57,490
Så jag kunde bara göra det rätta aritmetiska
att returnera den förre chefen

1481
01:10:57,490 --> 01:10:58,450
i kön.

1482
01:10:58,450 --> 01:11:01,850
Men jag kände bara att det var mer tydlig
att faktiskt ta tag i int, uttryckte det

1483
01:11:01,850 --> 01:11:04,320
i n, och sedan tillbaka till att
för tydlighetens skull, men

1484
01:11:04,320 --> 01:11:05,735
inte är absolut nödvändigt.

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 är alla uttalas på mitt huvud.

1488
01:11:13,410 --> 01:11:15,940

1489
01:11:15,940 --> 01:11:19,110
>> ROB BOWDEN: Så första frågan
Detta är ett binärt träd problem.

1490
01:11:19,110 --> 01:11:22,140
Så första frågan är, vi är
med tanke på dessa siffror.

1491
01:11:22,140 --> 01:11:27,160
Och vi vill på något sätt infoga dem i
dessa noder så att det är en

1492
01:11:27,160 --> 01:11:30,110
giltigt binärt sökträd.

1493
01:11:30,110 --> 01:11:36,260
Så en sak att komma ihåg om
binära sökträd är att det inte är

1494
01:11:36,260 --> 01:11:39,800
bara det att den sak till vänster
är mindre och man kan

1495
01:11:39,800 --> 01:11:41,120
höger är större.

1496
01:11:41,120 --> 01:11:44,580
Det måste vara att hela träd till
vänster är mindre, och hela trädet

1497
01:11:44,580 --> 01:11:45,740
till höger är större.

1498
01:11:45,740 --> 01:11:55,260
>> Så om jag satte 34 här i toppen, och sedan
Jag satte 20 här, så det är giltigt så

1499
01:11:55,260 --> 01:11:56,970
långt, eftersom 34 upp här.

1500
01:11:56,970 --> 01:11:57,920
20 går till vänster.

1501
01:11:57,920 --> 01:11:58,950
Så det är mindre.

1502
01:11:58,950 --> 01:12:03,640
Men jag kan inte sedan lägga 59 här, eftersom
även om 59 är till höger om 20,

1503
01:12:03,640 --> 01:12:06,140
det är fortfarande till vänster 34.

1504
01:12:06,140 --> 01:12:10,760
Så med denna begränsning i åtanke,
enklaste sättet troligen lösa detta

1505
01:12:10,760 --> 01:12:14,330
Problemet är att bara typ
av dessa nummer -

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
Och sedan in dem
från vänster till höger.

1508
01:12:21,640 --> 01:12:23,390
>> Så 20 går här.

1509
01:12:23,390 --> 01:12:24,630
34 går här.

1510
01:12:24,630 --> 01:12:25,830
36 går här.

1511
01:12:25,830 --> 01:12:29,360
52, 59, 106.

1512
01:12:29,360 --> 01:12:34,730
Och ni också kunde ha räknat ut med
några koppla in och inse,

1513
01:12:34,730 --> 01:12:38,830
oh, vänta, jag har inte tillräckligt med siffror
att fylla i det här borta.

1514
01:12:38,830 --> 01:12:42,170
Så jag måste reshift vad min
rutt anmärkning kommer att bli.

1515
01:12:42,170 --> 01:12:47,490
Men märker att i de tre sista, om
du läser från vänster till höger, är det i

1516
01:12:47,490 --> 01:12:48,740
stigande ordning.

1517
01:12:48,740 --> 01:12:52,150

1518
01:12:52,150 --> 01:12:56,540
>> Så nu vill vi förklara vad det
struct kommer att vara för

1519
01:12:56,540 --> 01:12:58,300
noder i trädet.

1520
01:12:58,300 --> 01:13:02,720
Så vad vi behöver i ett binärt träd?

1521
01:13:02,720 --> 01:13:05,830
Så vi har ett värde av typen
int, så vissa int värde.

1522
01:13:05,830 --> 01:13:07,220
Jag vet inte vad vi kallade
det i lösningen -

1523
01:13:07,220 --> 01:13:08,500
int n.

1524
01:13:08,500 --> 01:13:13,570
Vi behöver en pekare till den vänstra underordnade
och en pekare till det rätta barnet.

1525
01:13:13,570 --> 01:13:17,540
Så det kommer att se ut så här.

1526
01:13:17,540 --> 01:13:20,510
Och det kommer faktiskt se ut innan
när gjorde den dubbelt bundna

1527
01:13:20,510 --> 01:13:25,090
lista grejer, så varsel -

1528
01:13:25,090 --> 01:13:27,860
Jag kommer att behöva rulla hela
vägen tillbaka ner till problem 11.

1529
01:13:27,860 --> 01:13:30,980

1530
01:13:30,980 --> 01:13:36,390
>> Så märker det ser identisk med detta,
utom vi råkar bara kalla dessa

1531
01:13:36,390 --> 01:13:38,590
olika namn.

1532
01:13:38,590 --> 01:13:41,440
Vi har fortfarande ett heltal
värde och två pekare.

1533
01:13:41,440 --> 01:13:44,850
Det är bara det att i stället för att behandla
pekare som pekar på nästa sak

1534
01:13:44,850 --> 01:13:47,955
och den tidigare sak, vi behandlar
pekare att peka på ett vänster barn

1535
01:13:47,955 --> 01:13:49,205
och högra underordnade.

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 är vår struct node.

1539
01:13:59,650 --> 01:14:03,920
Och nu, den enda funktionen måste vi
genomföra detta är travers, som

1540
01:14:03,920 --> 01:14:08,320
vi vill gå över trädet, tryckning
ut värdena för trädet i ordning.

1541
01:14:08,320 --> 01:14:15,241
>> Så ser här, skulle vi vill skriva ut
ut 20, 34, 36, 52, 59, och 106.

1542
01:14:15,241 --> 01:14:17,970
Hur kan vi åstadkomma det?

1543
01:14:17,970 --> 01:14:18,890
Så det är ganska likartad.

1544
01:14:18,890 --> 01:14:22,910
Om du såg tidigare examen problemet
att du ville skriva ut

1545
01:14:22,910 --> 01:14:25,940
hela träd med kommatecken emellan
allt, var det faktiskt ännu

1546
01:14:25,940 --> 01:14:27,320
enklare än så.

1547
01:14:27,320 --> 01:14:30,950
Så här är lösningen.

1548
01:14:30,950 --> 01:14:33,110
Det var betydligt enklare
om du gjorde det rekursivt.

1549
01:14:33,110 --> 01:14:36,650
Jag vet inte om någon försökt
att göra det iterativt.

1550
01:14:36,650 --> 01:14:38,340
>> Men först, har vi vår bas fallet.

1551
01:14:38,340 --> 01:14:39,660
Tänk om roten är noll?

1552
01:14:39,660 --> 01:14:40,610
Då vi bara kommer att återvända.

1553
01:14:40,610 --> 01:14:42,300
Vi vill inte skriva ut någonting.

1554
01:14:42,300 --> 01:14:45,940
Annars kommer vi att korsa
rekursivt ned.

1555
01:14:45,940 --> 01:14:48,140
Skriv ut hela vänstra underträd.

1556
01:14:48,140 --> 01:14:51,440
Så skriver du ut allt mindre
än min nuvarande värde.

1557
01:14:51,440 --> 01:14:53,930
Och då kommer jag att skriva ut själv.

1558
01:14:53,930 --> 01:14:57,310
Och sedan ska jag recurse ner min
Hela högra delträd, så allt

1559
01:14:57,310 --> 01:14:58,810
större än mitt värde.

1560
01:14:58,810 --> 01:15:03,870
Och detta kommer att skriva ut
ut allt i ordning.

1561
01:15:03,870 --> 01:15:05,860
Frågor om hur det faktiskt
åstadkommer det?

1562
01:15:05,860 --> 01:15:09,892

1563
01:15:09,892 --> 01:15:12,545
>> PUBLIK: Jag har en fråga
på [OHÖRBAR].

1564
01:15:12,545 --> 01:15:15,090

1565
01:15:15,090 --> 01:15:23,550
>> ROB BOWDEN: Så ett sätt att närma sig
någon rekursiv problem är att bara tänka

1566
01:15:23,550 --> 01:15:26,275
om det som du måste tänka
om alla hörnfall.

1567
01:15:26,275 --> 01:15:32,150

1568
01:15:32,150 --> 01:15:38,110
Så anser att vi vill
skriva ut hela trädet.

1569
01:15:38,110 --> 01:15:42,030
Så allt vi kommer att fokusera på
är denna speciella nod -

1570
01:15:42,030 --> 01:15:43,740
36.

1571
01:15:43,740 --> 01:15:47,420
De rekursiva anrop, vi låtsas
de fungerar bara.

1572
01:15:47,420 --> 01:15:54,000
Så här, detta rekursivt anrop till
travers, vi utan att ens tänka

1573
01:15:54,000 --> 01:15:58,640
om det, bara traversera vänster
tre, tänka sig att redan skriver ut 20

1574
01:15:58,640 --> 01:16:00,730
och 34 för oss.

1575
01:16:00,730 --> 01:16:03,350
Och sedan när vi så småningom rekursivt
ringa travers på

1576
01:16:03,350 --> 01:16:07,890
rätt, som kommer att korrekt ut
52, 59 och 106 för oss.

1577
01:16:07,890 --> 01:16:13,620
>> Så med tanke på att detta kan skriva ut 20, 34, och
den andra kan skriva ut 52, 59, 108,

1578
01:16:13,620 --> 01:16:17,180
allt vi behöver för att kunna göra är att skriva ut
själv i mitten av det.

1579
01:16:17,180 --> 01:16:21,250
Så skriva ut allting framför oss.

1580
01:16:21,250 --> 01:16:27,710
Skriv själv, så den aktuella noden print
36, regelbunden printf och sedan

1581
01:16:27,710 --> 01:16:31,170
skriva ut allt efter oss.

1582
01:16:31,170 --> 01:16:32,730
>> DAVID J. MALAN: Det är där rekursion
blir riktigt vacker.

1583
01:16:32,730 --> 01:16:36,270
Det är denna fantastiska steg i tro där
du gör det minsta lite arbete.

1584
01:16:36,270 --> 01:16:38,460
Och sedan låta någon
annan göra resten.

1585
01:16:38,460 --> 01:16:40,180
Och att någon annan
är, ironiskt nog, du.

1586
01:16:40,180 --> 01:16:44,260

1587
01:16:44,260 --> 01:16:48,360
Så för allvarliga tomte poäng, om
du rullar upp på frågorna -

1588
01:16:48,360 --> 01:16:50,530
>> ROB BOWDEN: På frågorna?

1589
01:16:50,530 --> 01:16:53,490
>> DAVID J. MALAN: Och ner lite till
siffrorna, är det någon som vet var

1590
01:16:53,490 --> 01:16:55,190
dessa siffror ifrån?

1591
01:16:55,190 --> 01:16:56,610
>> ROB BOWDEN: Jag har bokstavligt talat ingen aning.

1592
01:16:56,610 --> 01:16:59,794
>> David J. MALAN: De visas
genom hela testet.

1593
01:16:59,794 --> 01:17:01,150
>> PUBLIK: Är de samma siffror?

1594
01:17:01,150 --> 01:17:01,910
>> DAVID J. MALAN: Dessa siffror.

1595
01:17:01,910 --> 01:17:03,260
Lite påskägg.

1596
01:17:03,260 --> 01:17:08,100
Så för de av er tittar på nätet på
hem, om du kan berätta för oss via e-post till

1597
01:17:08,100 --> 01:17:12,680
heads@CS50.net vilken betydelse
av dessa återkommande sex nummer är

1598
01:17:12,680 --> 01:17:18,560
hela Quiz 1 kommer vi duscha dig
med fantastisk uppmärksamhet vid den slutliga

1599
01:17:18,560 --> 01:17:21,610
föreläsning och en stressboll.

1600
01:17:21,610 --> 01:17:25,460

1601
01:17:25,460 --> 01:17:27,790
Trevligt, subtilt.

1602
01:17:27,790 --> 01:17:29,570
>> ROB Bowden: Några sista frågor
vad som helst på frågesport?

1603
01:17:29,570 --> 01:17:32,608