1
00:00:00,000 --> 00:00:11,460

2
00:00:11,460 --> 00:00:12,250
>> DAVID Malan: Dobře.

3
00:00:12,250 --> 00:00:13,860
Vítejte zpět CS50.

4
00:00:13,860 --> 00:00:16,190
To je začátek 8 týdnů.

5
00:00:16,190 --> 00:00:21,320
A připomínají, že problém sada 5 skončila
s trochou výzvu.

6
00:00:21,320 --> 00:00:25,210
Takže za předpokladu, že zpět všechny své
výuky Fellows a CA fotografie

7
00:00:25,210 --> 00:00:30,480
v souboru card.raw, máte nárok
se nyní najít všechny ty lidi, a

8
00:00:30,480 --> 00:00:34,510
jeden šťastný výherce bude chodit domů s jedním
z těchto věcí, skok pohyb

9
00:00:34,510 --> 00:00:37,450
zařízení, které můžete použít pro konečné
projekty, například.

10
00:00:37,450 --> 00:00:39,860
>> To každý rok, vede k
trochu děsivost.

11
00:00:39,860 --> 00:00:43,480
A tak to, co jsem myslel, že to je podíl
s vámi o některé poznámky, které mají

12
00:00:43,480 --> 00:00:47,370
šel tam a zpět přes
zaměstnanci seznam pozdě.

13
00:00:47,370 --> 00:00:51,110
Například právě včera večer, citace
konec citátu, z jednoho z pracovníků

14
00:00:51,110 --> 00:00:55,000
členové, "musel jsem studentský klepání
na mé dveře vyfotit se mnou.

15
00:00:55,000 --> 00:00:59,020
Stalkeři, povídám. "Zacala
dosti popisná a pak jsme se přestěhovali

16
00:00:59,020 --> 00:01:02,830
na, tak hodinu později, "jsem měl
Student na mě čeká po bodu

17
00:01:02,830 --> 00:01:06,080
a měl všechny naše jména a fotografie
na některých listů papíru. "v pořádku.

18
00:01:06,080 --> 00:01:09,230
Organizována tak, ale ne
vše strašidelné ještě.

19
00:01:09,230 --> 00:01:12,520
>> Tak, "já jsem byl mimo město tento víkend,
a když jsem se vrátil, byl tam jeden v

20
00:01:12,520 --> 00:01:12,630
můj

21
00:01:12,630 --> 00:01:16,740
ložnice. "[smích]

22
00:01:16,740 --> 00:01:20,410
DAVID Malan: Další citace z pracovníků
člen "student přišel do mého domu na

23
00:01:20,410 --> 00:01:25,330
Somerville při 4 hodin ráno. "Další
personál, "Dostal jsem do hotelu v San

24
00:01:25,330 --> 00:01:30,016
Francisco a student čekal na
mě v hale se třemi DSLR. "

25
00:01:30,016 --> 00:01:31,510
Typ fotoaparátu.

26
00:01:31,510 --> 00:01:34,980
"Já nejsem ani na zaměstnance tomto semestru,
ale student se vloupal do mého domu tento

27
00:01:34,980 --> 00:01:40,480
ráno a zaznamenal celou věc
se sklem Google. "A pak konečně,

28
00:01:40,480 --> 00:01:43,650
"Nejméně 12 lidí bylo dychtivě
čeká na mě, když jsem se dostal z mého

29
00:01:43,650 --> 00:01:44,800
limo, a pak jsem

30
00:01:44,800 --> 00:01:46,970
probudil. "Dobře.

31
00:01:46,970 --> 00:01:57,690
Takže mezi fotografiemi, jak můžete
vzpomínám, je tenhle chlapík tady, kdo jste

32
00:01:57,690 --> 00:02:01,850
Možná víte, jak Milo Banana, který žije
s Lauren Carvalho, naše hlavy

33
00:02:01,850 --> 00:02:02,905
vyučování Fellow.

34
00:02:02,905 --> 00:02:05,170
Milo Milo, pojď sem chlapče.

35
00:02:05,170 --> 00:02:06,320
Milo.

36
00:02:06,320 --> 00:02:08,650
Milo.

37
00:02:08,650 --> 00:02:12,230
Nezapomínejme, že má na sobě Google Glass, takže
my vám ukážeme všechno po něm.

38
00:02:12,230 --> 00:02:16,190
Tak to je Milo, pokud chcete
vyfotografovat se s ním později.

39
00:02:16,190 --> 00:02:18,240
Pokud byste chtěli dát pozor
na diváky tam.

40
00:02:18,240 --> 00:02:19,430
OK.

41
00:02:19,430 --> 00:02:20,200
To je dobré záběry.

42
00:02:20,200 --> 00:02:22,556
No, Milo Banana.

43
00:02:22,556 --> 00:02:23,941
Oh, nedělejte to.

44
00:02:23,941 --> 00:02:29,020
>> [Smích]

45
00:02:29,020 --> 00:02:29,470
>> OK.

46
00:02:29,470 --> 00:02:34,550
Takže jedním slovem, pak o tom, co je před námi,
protože jak začneme přechodu,

47
00:02:34,550 --> 00:02:38,410
tento týden konkrétně z C na
v prostředí příkazového řádku na PHP a

48
00:02:38,410 --> 00:02:42,720
JavaScript a SQL a HTML a CSS v
web-based prostředí, budeme

49
00:02:42,720 --> 00:02:44,490
vybavení vám všechny
více znalostí pro

50
00:02:44,490 --> 00:02:46,010
případné konečné projektů.

51
00:02:46,010 --> 00:02:49,240
Za tímto účelem je hřiště má
Tradice pořádání seminářů, které

52
00:02:49,240 --> 00:02:50,950
jsou na tangenciální témata
k předmětu.

53
00:02:50,950 --> 00:02:54,330
Velmi o programování a
vývoj aplikací a tak dále, ale

54
00:02:54,330 --> 00:02:57,010
nemusí být nutně prozkoumána
Kurz vlastní osnovy.

55
00:02:57,010 --> 00:03:00,250
>> Takže pokud by vás mohly zajímat v jednom
nebo více z letošních seminářů,

56
00:03:00,250 --> 00:03:02,530
zaregistrujte se na cs50.net/seminar.

57
00:03:02,530 --> 00:03:06,170
Tam jsou starší semináře
na cs50.net/seminars.

58
00:03:06,170 --> 00:03:10,620
A na seznamu dosud pro letošní rok
Amazing Web Apps jsou s Ruby on

59
00:03:10,620 --> 00:03:13,580
Kolejnice, která je alternativou
jazyk PHP.

60
00:03:13,580 --> 00:03:14,900
Matematická lingvistika.

61
00:03:14,900 --> 00:03:18,710
Úvod do IOS, který je
platformy, která je použita pro iPhone a

62
00:03:18,710 --> 00:03:19,850
iPad rozvoje.

63
00:03:19,850 --> 00:03:22,890
JavaScript pro Web Apps, budeme pokrývat
, ale v tomto semináři, půjdete

64
00:03:22,890 --> 00:03:24,070
do větších detailů.

65
00:03:24,070 --> 00:03:27,390
>> Leap Motion, takže budeme vlastně mají některé
našich přátel z Leap Motion,

66
00:03:27,390 --> 00:03:29,160
společnost sama, přidejte se k nám.

67
00:03:29,160 --> 00:03:31,800
Zítra, ve skutečnosti, aby
praktický seminář, je-li

68
00:03:31,800 --> 00:03:33,320
vás zajímají.

69
00:03:33,320 --> 00:03:38,770
Meteor.js, alternativní metody pro
pomocí JavaScriptu není v prohlížeči,

70
00:03:38,770 --> 00:03:39,970
ale na serveru.

71
00:03:39,970 --> 00:03:42,110
Node.js, který je velmi
V tomto duchu také.

72
00:03:42,110 --> 00:03:43,650
Elegantní Android design.

73
00:03:43,650 --> 00:03:46,990
Android je velmi populární alternativa
na iOS a Windows Phone

74
00:03:46,990 --> 00:03:48,790
a další mobilní platformy.

75
00:03:48,790 --> 00:03:51,180
A Web Security Aktivní obrana.

76
00:03:51,180 --> 00:03:54,590
>> Takže ve skutečnosti, pokud si přejete
zapojit se do tohoto, dovolte mi, abych

77
00:03:54,590 --> 00:03:55,840
aby na vědomí.

78
00:03:55,840 --> 00:03:57,790
Jsme velmi rádi, že
Naši přátelé na skok

79
00:03:57,790 --> 00:03:59,140
Pohyb, který je spuštění -

80
00:03:59,140 --> 00:04:01,300
tento přístroj opravdu jen přišel
před několika měsíci -

81
00:04:01,300 --> 00:04:05,960
milostivě daroval 30 těchto zařízení
do třídy pro co největší počet studentů, je-li

82
00:04:05,960 --> 00:04:08,670
byste chtěli půjčit hardware
na konci semestru a používat jej pro

83
00:04:08,670 --> 00:04:10,390
Skutečná konečná projektu.

84
00:04:10,390 --> 00:04:11,890
Oni podporují celou řadu jazyků.

85
00:04:11,890 --> 00:04:16,040
Žádný z nich C, žádný z nich PHP, takže
realizovat jeden nebo více z těchto seminářů

86
00:04:16,040 --> 00:04:16,899
by mohlo být zajímavé.

87
00:04:16,899 --> 00:04:19,730
A všechny z nich bude natočen v
případě, že nejste schopni

88
00:04:19,730 --> 00:04:21,380
zúčastnit osobně.

89
00:04:21,380 --> 00:04:25,000
Harmonogram bude oznámeno prostřednictvím
email jak zpevnit pokoje.

90
00:04:25,000 --> 00:04:28,460
>> A konečně, pokud jdete na
projects.cs.50.net, to je webová stránka

91
00:04:28,460 --> 00:04:31,450
udržujeme každý rok, zveme
lidé z komunity, fakulty,

92
00:04:31,450 --> 00:04:36,420
odbory, zaměstnanci a oba
na vnější straně na CS50

93
00:04:36,420 --> 00:04:37,730
navrhnout projektové nápady.

94
00:04:37,730 --> 00:04:39,050
Věci jsou předmětem zájmu skupiny studentů.

95
00:04:39,050 --> 00:04:40,600
Věci zájmu oddělení.

96
00:04:40,600 --> 00:04:43,990
Takže se zase tam, pokud budete bojovat
s nejistotou, pokud jde o to, co

97
00:04:43,990 --> 00:04:46,700
sami chtěli řešit.

98
00:04:46,700 --> 00:04:51,760
>> Takže poslední době jsme zavedli pravděpodobně
složitější datové struktury, než my bychom

99
00:04:51,760 --> 00:04:53,300
vidět v minulých týdnech.

100
00:04:53,300 --> 00:04:56,550
Rádi bychom se s použitím polí dost
šťastně jako užitečná, pokud

101
00:04:56,550 --> 00:04:58,160
zjednodušující datové struktury.

102
00:04:58,160 --> 00:05:00,570
Pak jsme zavedli nich, které
Samozřejmě jsou spojeny seznamy.

103
00:05:00,570 --> 00:05:05,470
A to, co bylo jednou z motivací pro
zavedení této datové struktury?

104
00:05:05,470 --> 00:05:06,930
Jo?

105
00:05:06,930 --> 00:05:07,250
Co je to?

106
00:05:07,250 --> 00:05:08,080
>> Diváků: Dynamická velikost.

107
00:05:08,080 --> 00:05:09,040
>> DAVID Malan: Dynamická velikost.

108
00:05:09,040 --> 00:05:11,890
Takže zatímco v poli, musíte
znát jeho velikost zálohy, pokud

109
00:05:11,890 --> 00:05:12,740
přidělit ji.

110
00:05:12,740 --> 00:05:14,380
V spojový seznam, nemusíte
vědět, že.

111
00:05:14,380 --> 00:05:17,610
Můžete jen malloc, nebo obecněji,
přidělit další

112
00:05:17,610 --> 00:05:20,720
uzel, abych tak řekl, kdykoliv
Chci vložit další data.

113
00:05:20,720 --> 00:05:22,670
A uzel není předem význam.

114
00:05:22,670 --> 00:05:25,580
Je to jen obecný termín, který popisuje
nějaký druh kontejneru, který jsme

115
00:05:25,580 --> 00:05:29,610
použití v naší datové struktury pro ukládání
některé Předmětem zájmu, který je v tomto

116
00:05:29,610 --> 00:05:31,750
případě se stalo, že celá čísla.

117
00:05:31,750 --> 00:05:33,160
>> Ale je tu vždy kompromisem.

118
00:05:33,160 --> 00:05:38,070
Tak jsme si dynamické velikosti dat
struktura, ale jakou cenu platíme?

119
00:05:38,070 --> 00:05:40,040
Co je to nevýhoda provázaných seznamů?

120
00:05:40,040 --> 00:05:41,006
Jo?

121
00:05:41,006 --> 00:05:41,980
>> DIVÁKŮ: vyžaduje více paměti.

122
00:05:41,980 --> 00:05:44,240
>> DAVID Malan: To vyžaduje více
paměť, jak přesně?

123
00:05:44,240 --> 00:05:46,440
>> DIVÁKŮ: [neslyšitelné].

124
00:05:46,440 --> 00:05:47,050
>> DAVID Malan: Přesně tak.

125
00:05:47,050 --> 00:05:50,460
Takže teď jsme ukazatele nástupu do
přídavné paměti, že jsme předtím

126
00:05:50,460 --> 00:05:53,040
nepotřeboval, protože výhoda
z pole, samozřejmě, je to, že

127
00:05:53,040 --> 00:05:54,860
všechno je souvislé zpět
se zády k sobě, což

128
00:05:54,860 --> 00:05:56,380
vám dává náhodný přístup.

129
00:05:56,380 --> 00:06:00,710
Protože jen pomocí hranatou závorkou
notace, nebo více technicky ukazatel

130
00:06:00,710 --> 00:06:03,580
aritmetický, velmi jednoduché sčítání,
můžete přistupovat k jakýmkoli

131
00:06:03,580 --> 00:06:05,700
prvky v konstantním čase.

132
00:06:05,700 --> 00:06:08,975
A ve skutečnosti, to je něco napovídalo
další cena, kterou platíme s

133
00:06:08,975 --> 00:06:09,760
spojový seznam.

134
00:06:09,760 --> 00:06:13,890
>> Co se stane s dobou chodu
něco jako hledat, když chci

135
00:06:13,890 --> 00:06:17,270
najít nějakou hodnotu a vnitřek
propojeného seznamu?

136
00:06:17,270 --> 00:06:20,290
Co mi běží čas stát?

137
00:06:20,290 --> 00:06:21,560
Velký O n.

138
00:06:21,560 --> 00:06:24,060
Pokud je to tříděny?

139
00:06:24,060 --> 00:06:25,440
Co v případě, že datová struktura je třídit?

140
00:06:25,440 --> 00:06:28,640
Mohu dělat lépe než velké
O z n pro vyhledávání?

141
00:06:28,640 --> 00:06:31,700
Ne, protože v nejhorším případě by to mohlo
velmi dobře být tříděny, ale počet

142
00:06:31,700 --> 00:06:32,950
hledáte by mohla být velká.

143
00:06:32,950 --> 00:06:35,370
To by mohlo být číslo 100, která
Může se stát, že všechny

144
00:06:35,370 --> 00:06:36,410
jak na konci.

145
00:06:36,410 --> 00:06:39,950
A protože můžete přistupovat pouze vázané
Seznam v tomto provedení by

146
00:06:39,950 --> 00:06:42,690
způsob jeho prvního uzlu, jste
ještě trochu smůlu.

147
00:06:42,690 --> 00:06:47,450
Musíte projít celou věc
od začátku až do konce, aby bylo možné nalézt

148
00:06:47,450 --> 00:06:49,150
že velké hodnoty jako 100.

149
00:06:49,150 --> 00:06:51,350
Nebo zjistit, zda je to
ani tam.

150
00:06:51,350 --> 00:06:55,960
>> Takže můžeme dělat to, co algoritmus v datovém
struktura, která vypadá takhle?

151
00:06:55,960 --> 00:06:59,460
Nemůžeme udělat binární vyhledávání, protože
binární hledání vyžaduje, aby jsme měli

152
00:06:59,460 --> 00:07:00,740
náhodný přístup.

153
00:07:00,740 --> 00:07:04,500
Mohli bychom vyskočit z místa na
umístění bez nutnosti sledovat

154
00:07:04,500 --> 00:07:07,080
Tyto strouhanka ve formě
všech těchto ukazatelů.

155
00:07:07,080 --> 00:07:08,300
>> Teď, jak jsme to realizovat?

156
00:07:08,300 --> 00:07:12,830
No, jestli půjdeme na obrazovku zde, je-li
můžeme rychle implementujeme tato data

157
00:07:12,830 --> 00:07:13,440
struktura -

158
00:07:13,440 --> 00:07:15,670
můj rukopis to není všechno, že
skvělé tady, ale zkusíme to.

159
00:07:15,670 --> 00:07:22,030
Takže typedef struct, a co jsem
chcete volat tu věc tady?

160
00:07:22,030 --> 00:07:22,960
Uzel.

161
00:07:22,960 --> 00:07:24,580
Takže budu se nám začalo.

162
00:07:24,580 --> 00:07:27,860
A teď, co je potřeba, aby se uvnitř
datová struktura pro které jednotlivě

163
00:07:27,860 --> 00:07:28,430
spojový seznam?

164
00:07:28,430 --> 00:07:29,950
Kolik pole?

165
00:07:29,950 --> 00:07:30,450
>> Tak dva.

166
00:07:30,450 --> 00:07:31,570
Jedním z nich je docela snadné.

167
00:07:31,570 --> 00:07:33,050
Tak int n.

168
00:07:33,050 --> 00:07:35,930
A tak bychom mohli nazývat n co chceme,
ale měl by být int, jestli jsme

169
00:07:35,930 --> 00:07:37,660
provádění spojový seznam pro ints.

170
00:07:37,660 --> 00:07:41,920
A teď, co dělá druhá
pole musí být?

171
00:07:41,920 --> 00:07:43,460
Struct node *.

172
00:07:43,460 --> 00:07:50,570
Takže když jsem to struct uzel * a pak jsem
Můžete volat i to, co chci,

173
00:07:50,570 --> 00:07:53,510
ale jen aby bylo jasno, zavolám
je další, jak jsme dělali.

174
00:07:53,510 --> 00:07:55,270
A pak jsem zavřu složené závorky.

175
00:07:55,270 --> 00:08:00,700
>> A teď, jako minule,
Dal jsem uzel dole.

176
00:08:00,700 --> 00:08:03,830
Ale když jsem dokládá, že toto je
uzel, proč jsem se obtěžovat, že je tak

177
00:08:03,830 --> 00:08:07,320
verbose zde deklarovat struct
uzel * další, na rozdíl od

178
00:08:07,320 --> 00:08:09,210
jen na uzlu * další?

179
00:08:09,210 --> 00:08:09,904
Jo?

180
00:08:09,904 --> 00:08:12,810
>> DIVÁKŮ: [neslyšitelné].

181
00:08:12,810 --> 00:08:14,050
>> DAVID Malan: Přesně tak.

182
00:08:14,050 --> 00:08:14,530
Přesně tak.

183
00:08:14,530 --> 00:08:18,320
Protože C opravdu vás doslova a
vidí pouze definici uzlu

184
00:08:18,320 --> 00:08:21,230
cesta sem, nemůžete
odkazovat se na to tady.

185
00:08:21,230 --> 00:08:24,760
Takže máme tento druh preemptivní
Prohlášení tady, což je sice

186
00:08:24,760 --> 00:08:25,390
více verbose.

187
00:08:25,390 --> 00:08:27,810
Struct uzel, to znamená, že
můžeme nyní přistupovat

188
00:08:27,810 --> 00:08:29,760
uvnitř datové struktury.

189
00:08:29,760 --> 00:08:33,370
>> A jako stranou, protože to je
stává trochu subjektivní teď,

190
00:08:33,370 --> 00:08:36,230
hvězda technicky možné jít sem,
to může jít sem, může

191
00:08:36,230 --> 00:08:37,179
dokonce jít ve středu.

192
00:08:37,179 --> 00:08:39,890
Jsme přijala ve stylu příručce pro
Samozřejmě, že konvence uvedení

193
00:08:39,890 --> 00:08:42,299
hvězda vedle údajů
typu, který je v tomto případě,

194
00:08:42,299 --> 00:08:43,460
by struct uzel.

195
00:08:43,460 --> 00:08:46,620
Ale realizovat v mnoha učebnicích a
on-line odkazy, můžete skutečně

196
00:08:46,620 --> 00:08:48,450
vidět, že na druhé straně.

197
00:08:48,450 --> 00:08:52,200
Ale jen si uvědomit, že jak bude ve skutečnosti
práce a vy byste měli být jednoduše

198
00:08:52,200 --> 00:08:52,970
konzistentní.

199
00:08:52,970 --> 00:08:53,580
>> Dobrá.

200
00:08:53,580 --> 00:08:55,630
Tak to bylo naše prohlášení
of struct uzlu.

201
00:08:55,630 --> 00:08:59,430
Ale pak jsme začali dělat více
sofistikované věci.

202
00:08:59,430 --> 00:09:03,410
Například jsme se rozhodli zavést
něco jako tabulky hash.

203
00:09:03,410 --> 00:09:08,160
Takže tady je hash tabulka velikosti n,
indexovány od 0 vlevo nahoře na n

204
00:09:08,160 --> 00:09:09,690
minus 1 vlevo dole.

205
00:09:09,690 --> 00:09:11,640
To by mohlo být hash
tabulka na cokoliv.

206
00:09:11,640 --> 00:09:15,340
Ale to, co spoustu věcí jsme se mluvit
o použití hash tabulku?

207
00:09:15,340 --> 00:09:18,370
Uložení co?

208
00:09:18,370 --> 00:09:18,800
>> Jména.

209
00:09:18,800 --> 00:09:20,870
Mohli bychom jména jako
jsme minule.

210
00:09:20,870 --> 00:09:22,200
A opravdu, můžete uložit cokoli.

211
00:09:22,200 --> 00:09:24,640
A uvidíme to znovu
PHP a JavaScriptu.

212
00:09:24,640 --> 00:09:28,550
Hash tabulky je pěkný druh Swiss
Armádní nůž, který vám umožní ukládat

213
00:09:28,550 --> 00:09:33,690
skoro co chcete uvnitř
je to tím, že sdruží klíče s hodnotami.

214
00:09:33,690 --> 00:09:34,770
Klávesy s hodnotami.

215
00:09:34,770 --> 00:09:37,800
>> Nyní v tomto jednoduchém případě, naše
Klíče jsou jen čísla.

216
00:09:37,800 --> 00:09:40,380
Jsme provádění hash
tabulka jako pole.

217
00:09:40,380 --> 00:09:43,500
A tak jsou klíče 0,
1, 2, a tak dále.

218
00:09:43,500 --> 00:09:47,200
A tak my, jako lidé, rozhodla poslední
týden, že víte, co, když jsme

219
00:09:47,200 --> 00:09:50,410
bude ukládat jména, prostě
libovolně, ale docela rozumně,

220
00:09:50,410 --> 00:09:54,680
Předpokládám, že Alice, název,
bude jen být indexovány do 0.

221
00:09:54,680 --> 00:09:58,030
A Bob, název B, budou indexovány
do 1, a tak dále.

222
00:09:58,030 --> 00:10:02,490
Takže jsme museli mapování mezi vstupy,
které jsou řetězce a hash

223
00:10:02,490 --> 00:10:04,560
umístění, které jsou čísla.

224
00:10:04,560 --> 00:10:07,740
>> Tak, že proces je obecně znám jako
hašovací funkce, a můžete skutečně

225
00:10:07,740 --> 00:10:09,130
implementovat v kódu.

226
00:10:09,130 --> 00:10:12,080
Pokud bych chtěl implementovat funkce hash
že dělá přesně to, co jsme

227
00:10:12,080 --> 00:10:17,070
právě popsal, od minule, bych mohl
deklarovat funkci, která bere jako

228
00:10:17,070 --> 00:10:18,330
vstup například -

229
00:10:18,330 --> 00:10:22,190
a jdem na to na to
Obrazovka sem.

230
00:10:22,190 --> 00:10:26,180
Pokud bych chtěl realizovat hash
funkce, mohl bych říct,

231
00:10:26,180 --> 00:10:27,410
něco takového.

232
00:10:27,410 --> 00:10:29,030
>> Bude to vrátit int.

233
00:10:29,030 --> 00:10:33,600
Bude to nazvat hash, a to
bude akceptovat jako argument

234
00:10:33,600 --> 00:10:38,920
řetězec, nebo to může být vhodnější teď,
a říkat char *, budeme říkat to.

235
00:10:38,920 --> 00:10:43,840
A pak tato funkce má co do činění,
nakonec se vrátit int.

236
00:10:43,840 --> 00:10:45,990
Teď, jak to dělá, které by mohly
není tak jasné.

237
00:10:45,990 --> 00:10:49,510
Jdu k provedení tohoto bez
Forma kontroly chyb právě teď.

238
00:10:49,510 --> 00:10:55,740
Jdu jen slepě říkat, vrátí
co je na držáku s 0, minus,

239
00:10:55,740 --> 00:10:58,850
řekněme, kapitál středníkem.

240
00:10:58,850 --> 00:10:59,960
>> Totálně rozbité.

241
00:10:59,960 --> 00:11:02,620
Není to dokonalé, protože
jeden, co když to je null?

242
00:11:02,620 --> 00:11:04,000
Špatné věci se bude dít.

243
00:11:04,000 --> 00:11:07,940
Za druhé, co když je první písmeno v této
jméno není velké písmeno?

244
00:11:07,940 --> 00:11:09,860
To není dopadne
z vrtů.

245
00:11:09,860 --> 00:11:11,970
To by mohlo být malé písmeno
nebo ne dopis vůbec.

246
00:11:11,970 --> 00:11:15,520
Takže naprosto prostor pro zlepšení tu,
ale to je základní myšlenka.

247
00:11:15,520 --> 00:11:19,010
>> Co jsme popsali v minulém týdnu verbálně
jen proces mapování Alici

248
00:11:19,010 --> 00:11:23,360
0 a Bob se 1 může být vyjádřena
jistě formulaically jako C

249
00:11:23,360 --> 00:11:24,320
funkce zde.

250
00:11:24,320 --> 00:11:28,630
Zavolal znovu hash, vezme řetězec jako
vstup, a pak nějak dělá něco

251
00:11:28,630 --> 00:11:31,020
s tímto vstup k výrobě výstupu.

252
00:11:31,020 --> 00:11:34,130
Ne na rozdíl od naší černé skříňky popis
že jsme dlouho udělat.

253
00:11:34,130 --> 00:11:36,550
Nevím, jak by to mohlo být
pracuje pod kapotou.

254
00:11:36,550 --> 00:11:40,120
>> Pro problémové sady 6, jeden z problémů,
je pro vás rozhodnout, co

255
00:11:40,120 --> 00:11:41,920
Váš hashovací funkce může být?

256
00:11:41,920 --> 00:11:45,760
Co bude uvnitř, že černá
box, a pravděpodobně, bude to

257
00:11:45,760 --> 00:11:50,380
trochu zajímavější než to, a
rozhodně náchylnější k chybám

258
00:11:50,380 --> 00:11:53,180
kontroly, než je tato konkrétní
implementace.

259
00:11:53,180 --> 00:11:54,580
>> Ale problémy mohou nastat, že jo?

260
00:11:54,580 --> 00:11:57,760
Máme-li datová struktura, jako je tato
jeden, co je jedním z problémů

261
00:11:57,760 --> 00:12:01,600
můžete narazit na průběhu času vložení
stále více a více jmen na

262
00:12:01,600 --> 00:12:02,880
hash tabulky?

263
00:12:02,880 --> 00:12:04,630
Získáte kolize, ne?

264
00:12:04,630 --> 00:12:07,560
Co když máte Alice a Árona,
dva lidé, jejichž jména se stalo

265
00:12:07,560 --> 00:12:08,190
začít?

266
00:12:08,190 --> 00:12:11,660
To vyvolává otázku, kde se
dal druhý takový název?

267
00:12:11,660 --> 00:12:15,050
>> No, možná naivně, prostě dát
kde Bob patří, ale pak Bob

268
00:12:15,050 --> 00:12:17,300
druh šroubované, pokud se pokusíte
vložte své jméno a další

269
00:12:17,300 --> 00:12:18,240
není místo pro něj.

270
00:12:18,240 --> 00:12:21,400
Takže můžete dát Bobe, kde Charlie je,
a můžete si to představit velmi rychle

271
00:12:21,400 --> 00:12:23,020
převede do trochu nepořádek.

272
00:12:23,020 --> 00:12:25,600
Něco lineární na konci, kde se
stačí hledat na celou věc

273
00:12:25,600 --> 00:12:28,190
Hledám Alice nebo Bob
nebo Aaron a Charlie.

274
00:12:28,190 --> 00:12:33,230
>> Tak místo toho navrhuje, místo toho, aby jen
lineárně snímání pro prostranství

275
00:12:33,230 --> 00:12:36,450
a plopping jména tam jsme
navrhla milovník přístup.

276
00:12:36,450 --> 00:12:41,740
Hash tabulky realizovány stále s
řada indexů, ale datový typ

277
00:12:41,740 --> 00:12:44,500
tyto indexy nyní byly ukazatele.

278
00:12:44,500 --> 00:12:47,360
Ukazatele k čemu?

279
00:12:47,360 --> 00:12:48,730
Ukazatele na lineárními seznamy.

280
00:12:48,730 --> 00:12:53,330
>> Vzhledem k tomu, připomínají, že spojový seznam je
opravdu jen ukazatel na uzel, a

281
00:12:53,330 --> 00:12:57,110
uzel má další pole, a že uzel
má další pole, a tak dále.

282
00:12:57,110 --> 00:13:00,690
Takže nyní můžete myslet na tomto poli na
levá strana tabulky hash jako

283
00:13:00,690 --> 00:13:01,820
což vede k propojeného seznamu.

284
00:13:01,820 --> 00:13:07,000
Výhodou je, pokud máte
kolize mezi Alicí a Áronovi:

285
00:13:07,000 --> 00:13:09,300
Co děláte s
druhý takový člověk?

286
00:13:09,300 --> 00:13:14,150
Můžete jen připojit ho, aby
konec, nebo dokonce na začátku

287
00:13:14,150 --> 00:13:15,490
tohoto propojeného seznamu.

288
00:13:15,490 --> 00:13:17,340
>> A vlastně, řekněme, přes nudle
že jen druhý.

289
00:13:17,340 --> 00:13:18,640
Pokud by největší smysl?

290
00:13:18,640 --> 00:13:22,060
Pokud vložím Alici a ona končí
Na prvním místě, pak se snažím, aby

291
00:13:22,060 --> 00:13:25,310
vložit Aaron jméno, a tam je
samozřejmě kolize, měl jsem

292
00:13:25,310 --> 00:13:27,400
ho na začátku
propojeného seznamu?

293
00:13:27,400 --> 00:13:30,944
To je v tomto prvním místě,
nebo na konci?

294
00:13:30,944 --> 00:13:31,440
>> DIVÁKŮ: [neslyšitelné].

295
00:13:31,440 --> 00:13:31,990
>> DAVID Malan: OK.

296
00:13:31,990 --> 00:13:32,490
Slyšel jsem, že na začátku.

297
00:13:32,490 --> 00:13:33,903
Proto se již na začátku?

298
00:13:33,903 --> 00:13:34,750
>> DIVÁKŮ: [neslyšitelné].

299
00:13:34,750 --> 00:13:34,940
>> DAVID Malan: OK.

300
00:13:34,940 --> 00:13:36,520
Je to podle abecedy, tak to je hezké.

301
00:13:36,520 --> 00:13:37,330
To je dobrá vlastnost.

302
00:13:37,330 --> 00:13:39,335
To vám ušetří mi čas potenciálně.

303
00:13:39,335 --> 00:13:43,290
To mi nedovolí dělat binární vyhledávání, ale já
by alespoň být schopen vymanit se

304
00:13:43,290 --> 00:13:47,340
ze smyčky, pokud si uvědomuji, no, já jsem cesta
minulosti se Aaron by v tomto

305
00:13:47,340 --> 00:13:48,310
řazeny propojeného seznamu.

306
00:13:48,310 --> 00:13:50,360
Nemám ztrácet čas hledáním
až do konce.

307
00:13:50,360 --> 00:13:51,530
Tak to je rozumné.

308
00:13:51,530 --> 00:13:54,710
Proč jinak by mohlo chcete vložit
kolize název na

309
00:13:54,710 --> 00:13:56,660
na začátku seznamu?

310
00:13:56,660 --> 00:13:57,397
Co je to?

311
00:13:57,397 --> 00:13:58,680
>> DIVÁKŮ: [neslyšitelné].

312
00:13:58,680 --> 00:14:00,820
>> DAVID Malan: Mohlo by to trvat dlouho
dostat se na konec seznamu.

313
00:14:00,820 --> 00:14:02,490
A ve skutečnosti, déle a déle.

314
00:14:02,490 --> 00:14:04,920
Čím více jmen, které vložíte
začátek, delší než

315
00:14:04,920 --> 00:14:06,280
řetěz dostane.

316
00:14:06,280 --> 00:14:07,890
Čím déle tu, která souvisí
Seznam je dostane.

317
00:14:07,890 --> 00:14:09,420
Takže jste opravdu jen
ztrácíš čas.

318
00:14:09,420 --> 00:14:14,070
Možná, že jste na tom lépe udržovat
konstantní Čas vložení, velký O z 1,

319
00:14:14,070 --> 00:14:18,470
tím, že vždy dávat na sebe narážející na název
počátek propojeného seznamu,

320
00:14:18,470 --> 00:14:21,230
a ne tolik znepokojující
o třídění.

321
00:14:21,230 --> 00:14:22,600
>> Jaký je nejlepší odpověď?

322
00:14:22,600 --> 00:14:23,320
Je to jasné.

323
00:14:23,320 --> 00:14:26,140
To druh závisí na tom, co
distribuce je to, co je vzor

324
00:14:26,140 --> 00:14:27,850
jména vkládáte.

325
00:14:27,850 --> 00:14:29,430
To nemusí být nutně
jasná odpověď.

326
00:14:29,430 --> 00:14:33,100
Ale zde je opět
design příležitost.

327
00:14:33,100 --> 00:14:37,220
>> Tak jsme pak se podíval na tu věc, která
je opravdu jiná velká příležitost

328
00:14:37,220 --> 00:14:38,180
pro p-set 6.

329
00:14:38,180 --> 00:14:41,770
A uvědomit si, pokud jste tak již neučinili,
Zamyla se ponoří do obou z nich, hashovací

330
00:14:41,770 --> 00:14:43,260
tabulky a snaží se, ve více detailu.

331
00:14:43,260 --> 00:14:45,630
A video návod je
vložené do p-set spec.

332
00:14:45,630 --> 00:14:46,590
To byl trie -

333
00:14:46,590 --> 00:14:51,670
T-R-I-E. A co bylo zajímavé,
bylo to, že doba provozu

334
00:14:51,670 --> 00:14:59,510
Není třeba hledat jména, jako je Maxwell
Minule byl velký O čeho?

335
00:14:59,510 --> 00:15:01,040
Co je to?

336
00:15:01,040 --> 00:15:01,920
>> Diváků: počet písmen.

337
00:15:01,920 --> 00:15:02,550
>> DAVID Malan: počet písmen.

338
00:15:02,550 --> 00:15:03,210
Slyšel jsem dvě věci.

339
00:15:03,210 --> 00:15:04,630
Počet písmen a konstantním čase.

340
00:15:04,630 --> 00:15:05,540
Takže pojďme se, že jako první.

341
00:15:05,540 --> 00:15:06,410
Počet písmen.

342
00:15:06,410 --> 00:15:10,195
No, to datová struktura, odvolání, je
jako strom, rodokmen, každý z

343
00:15:10,195 --> 00:15:12,860
jejichž uzly jsou tvořeny poli.

344
00:15:12,860 --> 00:15:16,300
A ty pole jsou odkazy na
jiné takové uzly, či jiné podobné

345
00:15:16,300 --> 00:15:17,670
pole ve stromu.

346
00:15:17,670 --> 00:15:22,890
>> Takže pokud bychom chtěli pak určují
zda Maxwell je tady, mohl bych jít

347
00:15:22,890 --> 00:15:26,890
na první pole, na samém vrcholu
strom, tzv. kořen, horní část

348
00:15:26,890 --> 00:15:30,521
trie a postupujte ukazatel m,
pak ukazatel, pak x,

349
00:15:30,521 --> 00:15:31,710
w, e, l, l.

350
00:15:31,710 --> 00:15:34,910
A pak, když vidím nějaký speciální symbol,
označený zde jako trojúhelník.

351
00:15:34,910 --> 00:15:38,480
V kódu uvidíte, že navrhne, aby si
implementován jako bool, jen říkám ano

352
00:15:38,480 --> 00:15:40,540
nebo ne, slovo, zde zastaví.

353
00:15:40,540 --> 00:15:45,270
>> No, jednou jsme šli do M-A-X-W-E-L-L,
pocit, sedm, možná

354
00:15:45,270 --> 00:15:48,910
osm když jdeme jeden kolem ní osm
kroky k nalezení Maxwell.

355
00:15:48,910 --> 00:15:53,050
Nebo řekněme, že K. Ale vzpomínám poslední
čas, jsem tvrdil, že v případě, že je

356
00:15:53,050 --> 00:15:57,540
realisticky maximální délka na
slovo, stejně jako 40-některé-liché znaky,

357
00:15:57,540 --> 00:16:00,810
Maximální délka znamená,
konstantní hodnotu.

358
00:16:00,810 --> 00:16:05,770
Takže opravdu, ano, je to technicky velký O
8 nebo 7, nebo opravdu velký O K. Ale

359
00:16:05,770 --> 00:16:09,420
v případě, že je konečný limit na to, co
K může být, že je konstantní.

360
00:16:09,420 --> 00:16:12,080
A tak je to velký O z 1 na
konci dne.

361
00:16:12,080 --> 00:16:13,040
>> Není v reálném světě.

362
00:16:13,040 --> 00:16:15,960
Ne, když skutečně začít sledovat
vaše hodiny, jak váš program běží.

363
00:16:15,960 --> 00:16:20,690
Je to naprosto to bude trochu
pomalejší než skutečně konstantní

364
00:16:20,690 --> 00:16:21,840
čas na jeden krok.

365
00:16:21,840 --> 00:16:25,540
Bude to sedm nebo osm stupňů,
ale stále je to mnohem, mnohem lepší

366
00:16:25,540 --> 00:16:30,080
než algoritmu, jako je velký O N, který
závisí na velikosti, co je v

367
00:16:30,080 --> 00:16:31,220
datové struktury.

368
00:16:31,220 --> 00:16:34,970
>> Všimněte si, že zde je vzhůru, můžeme vložit
milionkrát více jmen do tohoto

369
00:16:34,970 --> 00:16:38,170
datová struktura, ale kolik kroků
to bude trvat nám najít

370
00:16:38,170 --> 00:16:40,480
Maxwell v tomto případě?

371
00:16:40,480 --> 00:16:40,780
Žádné.

372
00:16:40,780 --> 00:16:41,820
On je nedotčena.

373
00:16:41,820 --> 00:16:45,480
A k dnešnímu dni, nemyslím si, že jsme viděli,
příklad datové struktury nebo

374
00:16:45,480 --> 00:16:48,560
algoritmus, který byl zcela
ovlivněna vnější

375
00:16:48,560 --> 00:16:50,040
chování, jako je to.

376
00:16:50,040 --> 00:16:51,160
Ale to nemůže být úžasné.

377
00:16:51,160 --> 00:16:52,900
To nemůže být jediným řešením
pro p-set

378
00:16:52,900 --> 00:16:53,570
>> A to ne.

379
00:16:53,570 --> 00:16:55,980
To není nutně data
Struktura byste měli tíhnout k,

380
00:16:55,980 --> 00:16:58,220
protože stejně jako tabulky hash, kompromis.

381
00:16:58,220 --> 00:17:00,500
Co je to cena, kterou zaplatíte tady?

382
00:17:00,500 --> 00:17:00,940
Paměť.

383
00:17:00,940 --> 00:17:02,890
Myslím, že je to otřesné
množství paměti.

384
00:17:02,890 --> 00:17:05,569
A můžete tak docela vidět tady, protože
autor obrázku

385
00:17:05,569 --> 00:17:09,420
samozřejmě zkrácen všech polí
a my nevidíme mnoho a je

386
00:17:09,420 --> 00:17:12,700
Hostely a C je a Q je a Y je
a Z je v těchto polích.

387
00:17:12,700 --> 00:17:13,630
Ale jsou tam.

388
00:17:13,630 --> 00:17:17,660
>> Každý z těchto uzlů je celý soubor
některých 26 nebo více bytů, z nichž každá

389
00:17:17,660 --> 00:17:19,170
což představuje dopis.

390
00:17:19,170 --> 00:17:22,920
27 V našem případě, tak, že může podporovat
apostrofy v sadě problém.

391
00:17:22,920 --> 00:17:27,030
Tak to datová struktura je opravdu,
opravdu hustý a široký.

392
00:17:27,030 --> 00:17:30,880
A to samo o sobě by mohlo skončit zpomaluje
věci dolů, nebo alespoň vás to stálo

393
00:17:30,880 --> 00:17:32,240
mnohem více prostoru.

394
00:17:32,240 --> 00:17:34,020
Ale znovu, můžeme vyvodit
srovnání zde.

395
00:17:34,020 --> 00:17:39,190
>> Vzpomínám si na chvíli zpět, jsme dosáhli mnohem
více vzrušující doba chodu při třídění

396
00:17:39,190 --> 00:17:42,880
když použijeme sloučení druh, ale cena
jsme zaplatili dosáhnout n log n o sloučení

397
00:17:42,880 --> 00:17:46,930
druh vyžaduje, aby trávíme
více jaký zdroj?

398
00:17:46,930 --> 00:17:47,690
Více prostoru.

399
00:17:47,690 --> 00:17:50,530
Potřebovali jsme sekundární matici
kopírovat lidi do, stejně jako

400
00:17:50,530 --> 00:17:51,620
jsme tady na jevišti.

401
00:17:51,620 --> 00:17:55,880
Takže znovu, žádné jasné vítěze,
ale jen subjektivní konstrukce

402
00:17:55,880 --> 00:17:57,710
rozhodnutí být dělán.

403
00:17:57,710 --> 00:17:58,060
>> Dobrá.

404
00:17:58,060 --> 00:17:59,130
Takže jak na to?

405
00:17:59,130 --> 00:18:02,050
Každý, kdo poznat, které D-Hall?

406
00:18:02,050 --> 00:18:02,440
OK.

407
00:18:02,440 --> 00:18:03,170
Takže tři z nás.

408
00:18:03,170 --> 00:18:03,750
Mather dům.

409
00:18:03,750 --> 00:18:05,070
Tak to je pro stolování Mather je.

410
00:18:05,070 --> 00:18:09,650
Vsadím se, že všechny jídelny mají
hromady zásobníků, jako je tento.

411
00:18:09,650 --> 00:18:11,950
A to je skutečně reprezentativní
o něco, co jsme

412
00:18:11,950 --> 00:18:13,050
zřejmě již viděli.

413
00:18:13,050 --> 00:18:14,850
Nazvali jsme ji doslova hromadu.

414
00:18:14,850 --> 00:18:18,970
A stack, pokud jde o váš
paměti počítače, je místo, kde přejde data

415
00:18:18,970 --> 00:18:20,460
zatímco funkce volána.

416
00:18:20,460 --> 00:18:23,410
>> Například, jaké druhy věcí jít
na zásobníku s ohledem na

417
00:18:23,410 --> 00:18:27,420
Rozvržení paměti jsme diskutovali
v týdnech minulých?

418
00:18:27,420 --> 00:18:28,736
Co je to?

419
00:18:28,736 --> 00:18:29,670
>> DIVÁKŮ: Volání funkce.

420
00:18:29,670 --> 00:18:30,260
>> DAVID Malan: Omlouvám se.

421
00:18:30,260 --> 00:18:31,210
>> DIVÁKŮ: Volání funkce.

422
00:18:31,210 --> 00:18:33,590
>> DAVID Malan: Volání funkce, ale
konkrétně, co je uvnitř každého

423
00:18:33,590 --> 00:18:35,340
ty rámy?

424
00:18:35,340 --> 00:18:37,220
Jaké věci?

425
00:18:37,220 --> 00:18:37,460
Jo.

426
00:18:37,460 --> 00:18:38,500
Takže lokální proměnné.

427
00:18:38,500 --> 00:18:43,080
Kdykoliv jsme potřebovali nějakou místní úložiště,
jako argument, nebo int I, nebo int

428
00:18:43,080 --> 00:18:45,940
temp, nebo cokoliv místní
proměnná, byli jsme

429
00:18:45,940 --> 00:18:47,210
uvedení, že na zásobníku.

430
00:18:47,210 --> 00:18:49,610
A říkáme, že stack, protože
tohoto vrstvení myšlenky.

431
00:18:49,610 --> 00:18:52,940
Jen trochu shoduje s realitou,
Koncept tohoto rozhodnutí.

432
00:18:52,940 --> 00:18:56,650
>> Ale ukazuje se, že zásobník lze také
pohlížet jako na datové struktury,

433
00:18:56,650 --> 00:19:00,110
Alternativou k poli, alternativní
do propojeného seznamu.

434
00:19:00,110 --> 00:19:02,770
Něco koncepčně zajímavější
že může být stále

435
00:19:02,770 --> 00:19:06,030
realizován pomocí některé z těch,
věci, ale je to jiný typ

436
00:19:06,030 --> 00:19:09,140
datová struktura podporu, opravdu,
pouze dvě operace.

437
00:19:09,140 --> 00:19:11,000
Ale můžete přidat na milovník
funkce než ty.

438
00:19:11,000 --> 00:19:12,180
Ale to jsou základy -

439
00:19:12,180 --> 00:19:13,510
tlačit a pop.

440
00:19:13,510 --> 00:19:19,240
>> A nápad s hromadou je, že když jsem
jsou tady, s nebo bez Annenberg

441
00:19:19,240 --> 00:19:22,880
věděl, zásobník od vedle
s číslem 9 na něm.

442
00:19:22,880 --> 00:19:23,870
Takže jen int.

443
00:19:23,870 --> 00:19:26,990
A já chci, aby se zasadila to na datech
struktura, která v současné době je prázdný.

444
00:19:26,990 --> 00:19:28,790
Vezměme si to ve spodní části zásobníku.

445
00:19:28,790 --> 00:19:33,150
Já bych tlačit toto číslo 9 na
stack, a teď je to tady.

446
00:19:33,150 --> 00:19:36,040
>> Ale zajímavá věc o zásobníku
je, že když jsem chtěl, aby se zasadila

447
00:19:36,040 --> 00:19:40,210
některé další hodnoty, jako 17, a tlačím
to do zásobníku, budu dělat

448
00:19:40,210 --> 00:19:43,290
pouze intuitivní věc, já jsem prostě jít
Abych to přesně tam, kde lidé

449
00:19:43,290 --> 00:19:45,180
by mít tendenci dát na povrch.

450
00:19:45,180 --> 00:19:48,850
Ale co je zajímavé, teď
je, jak se dostanu na 9?

451
00:19:48,850 --> 00:19:50,670
Víte, já ne bez nějaké námahy.

452
00:19:50,670 --> 00:19:54,070
>> Takže to, co je na tom zajímavé
zásobník, který je ze své podstaty

453
00:19:54,070 --> 00:19:56,330
Je to struktura dat LIFO.

454
00:19:56,330 --> 00:19:59,680
Silly způsob, jak popisovat
poslední dovnitř, první ven.

455
00:19:59,680 --> 00:20:03,280
Takže poslední číslo
V této době bylo 17 let.

456
00:20:03,280 --> 00:20:07,540
Takže když chci něco pop off
ze zásobníku, může to být pouze 17.

457
00:20:07,540 --> 00:20:11,890
Takže je povinný řád
působení u nás, kde je poslední položka

458
00:20:11,890 --> 00:20:14,260
musí být v první ven.

459
00:20:14,260 --> 00:20:16,440
Proto je zkratka, LIFO.

460
00:20:16,440 --> 00:20:19,160
>> Tak proč by to mohlo být užitečné?

461
00:20:19,160 --> 00:20:22,690
Jsou jejich kontexty, ve kterých bys
Chcete datovou strukturu, jako je tento?

462
00:20:22,690 --> 00:20:24,810
No, je to jistě užitečné,
uvnitř počítače.

463
00:20:24,810 --> 00:20:29,050
Takže operační systémy jednoznačně použít
Druh datové struktury pro komíny.

464
00:20:29,050 --> 00:20:32,800
Budeme také vidět stejnou myšlenku
pokud jde o webové stránky.

465
00:20:32,800 --> 00:20:35,890
Takže tento týden a příští týden a dále,
a jak začít provádět web

466
00:20:35,890 --> 00:20:39,490
stránky v jazyce HTML s názvem, můžete
vlastně používat datovou strukturu, jako je

467
00:20:39,490 --> 00:20:42,690
to, zda stránka
je ve správném formátu.

468
00:20:42,690 --> 00:20:47,170
Vzhledem k tomu, uvidíme všechny webové stránky postupujte podle
určitá hierarchie, odsazení

469
00:20:47,170 --> 00:20:52,030
, že se na konci dne, se
stromová struktura pod kapotou.

470
00:20:52,030 --> 00:20:53,620
Tak o tom více v jen trochu.

471
00:20:53,620 --> 00:20:56,560
>> Ale teď, pojďme navrhnout pro
Moment, jak bychom mohli jít o

472
00:20:56,560 --> 00:20:58,830
představuje to, co je stoh?

473
00:20:58,830 --> 00:21:03,370
Dovolte mi navrhnout, že bychom realizovat
zásobník s kódem, jako je tento.

474
00:21:03,370 --> 00:21:07,990
Takže zásobník bude mít uvnitř ní
dvě věci, pole, tzv. vaničky,

475
00:21:07,990 --> 00:21:09,510
jen aby byl v souladu s demo.

476
00:21:09,510 --> 00:21:12,660
A každá z položek v tomto poli
bude typu int.

477
00:21:12,660 --> 00:21:14,740
A kapacita je pravděpodobně to, co?

478
00:21:14,740 --> 00:21:18,796
Protože jsem nepsal
úplná definice zde.

479
00:21:18,796 --> 00:21:21,535
>> Je to asi maximum
Velikost pole.

480
00:21:21,535 --> 00:21:25,150
A je to asi deklarován jako ostrý
definovat v horní části souboru, některé

481
00:21:25,150 --> 00:21:28,450
druh konstantní jak vyplývá z
pouhá kapitalizace.

482
00:21:28,450 --> 00:21:32,250
Takže někde kapacita je definována
jako maximální možnou velikost.

483
00:21:32,250 --> 00:21:35,590
Mezitím, uvnitř datové struktury
známý jako zásobník se bude

484
00:21:35,590 --> 00:21:38,630
být celé číslo jen známý
jednoduše jako velikost.

485
00:21:38,630 --> 00:21:43,400
>> Takže pokud bych měl reprezentovat to teď
obrazově, předpokládejme, že tento

486
00:21:43,400 --> 00:21:48,070
Celá černá skříňka představuje svůj stack.

487
00:21:48,070 --> 00:21:50,070
Uvnitř ní jsou dvě proměnné.

488
00:21:50,070 --> 00:21:54,780
Takže budu čerpat
První je například velikost.

489
00:21:54,780 --> 00:21:57,420
A druhá jdu
kreslit jako pole.

490
00:21:57,420 --> 00:22:01,060
>> Ale jen proto, aby se věci řádné,
Normálně bych nakreslit pole jako

491
00:22:01,060 --> 00:22:04,910
, ale je to docela hezký
pokud budeme odpovídat skutečnosti, nebo

492
00:22:04,910 --> 00:22:06,230
odpovídat mentální model.

493
00:22:06,230 --> 00:22:12,880
Dovolte mi tedy namísto toho vypracovat pole
vertikálně, což je jen opět

494
00:22:12,880 --> 00:22:13,840
umělec ztvárnění.

495
00:22:13,840 --> 00:22:16,610
Nezáleží na tom, co to
je pod kapotou.

496
00:22:16,610 --> 00:22:20,350
A řekneme, že ve výchozím nastavení
kapacita bude tři.

497
00:22:20,350 --> 00:22:23,480
Takže to bude místo 0, to
bude místo 1, toto

498
00:22:23,480 --> 00:22:25,740
bude místo 2.

499
00:22:25,740 --> 00:22:29,330
>> Kdybych podplatit s důrazem míčem, by
někdo chtěl přijít a spustit

500
00:22:29,330 --> 00:22:30,870
palubu zde na chvíli?

501
00:22:30,870 --> 00:22:31,960
OK, viděl vaše ruka jako první.

502
00:22:31,960 --> 00:22:33,950
Pojď nahoru.

503
00:22:33,950 --> 00:22:36,500
Dobrá.

504
00:22:36,500 --> 00:22:38,760
Takže myslím, že je Steven.

505
00:22:38,760 --> 00:22:40,035
Pojď nahoru.

506
00:22:40,035 --> 00:22:40,770
Dobrá.

507
00:22:40,770 --> 00:22:46,760
>> Ale předpokládejme, že teď jsme se vrátit a počáteční
stav světa, kde jsem

508
00:22:46,760 --> 00:22:52,180
právě vyhlásil stack, a to
bude mít kapacitu tři.

509
00:22:52,180 --> 00:22:54,470
Ale velikost nebyla dosud stanovena.

510
00:22:54,470 --> 00:22:56,100
Zásobníky nebyla dosud stanovena.

511
00:22:56,100 --> 00:22:57,300
Takže pár otázek jako první.

512
00:22:57,300 --> 00:23:01,310
A dovolte mi, abych vám mikrofon, takže můžete
podílet se aktivněji na to.

513
00:23:01,310 --> 00:23:05,190
>> Takže to, co je uvnitř velikosti v tuto chvíli
včas, jestliže všechno, co jsem udělal, je

514
00:23:05,190 --> 00:23:09,340
prohlášen stoh
jeden řádek kódu?

515
00:23:09,340 --> 00:23:10,100
>> STEVEN: Moc ne.

516
00:23:10,100 --> 00:23:12,080
>> DAVID Malan: OK, nic moc.

517
00:23:12,080 --> 00:23:14,410
Víme, co je uvnitř velikosti,
víme, co je uvnitř

518
00:23:14,410 --> 00:23:16,330
tohoto pole Jsi zde poprvé?

519
00:23:16,330 --> 00:23:18,630
>> STEVEN: Jen náhodný kód, ne?

520
00:23:18,630 --> 00:23:20,220
Just -

521
00:23:20,220 --> 00:23:23,230
>> DAVID Malan: Jo, já jdu
říkají kód, ale náhodně -

522
00:23:23,230 --> 00:23:23,820
>> STEVEN: Věci.

523
00:23:23,820 --> 00:23:28,290
>> DAVID Malan: Věci, jako je náhodné

524
00:23:28,290 --> 00:23:28,870
>> STEVEN: bity.

525
00:23:28,870 --> 00:23:29,530
>> DAVID Malan: Bity, že jo?

526
00:23:29,530 --> 00:23:31,190
Takže odpadky hodnoty, ne?

527
00:23:31,190 --> 00:23:33,470
Takže permutace 0 a 1 je.

528
00:23:33,470 --> 00:23:35,920
Zbytky předchozích zvyklostí
této paměti.

529
00:23:35,920 --> 00:23:38,150
A opravdu nevím, co se hodnoty
jsou, takže většinou je nakreslit

530
00:23:38,150 --> 00:23:38,930
jako otazníky.

531
00:23:38,930 --> 00:23:41,990
>> Takže první věc, že ​​jsme pravděpodobně
bude chtít, aby to tady -

532
00:23:41,990 --> 00:23:46,630
a dovolte mi, abych toto pole uvnitř
odtud název - zásobníky.

533
00:23:46,630 --> 00:23:49,540
Co bychom měli pravděpodobně inicializovat
velikostí, chceme-li

534
00:23:49,540 --> 00:23:51,040
začít používat tuto stack?

535
00:23:51,040 --> 00:23:53,070
>> STEVEN: Zásobník je pod 3.

536
00:23:53,070 --> 00:23:53,910
>> DAVID Malan: Tak OK.

537
00:23:53,910 --> 00:23:56,710
Aby bylo jasno, je deklarovaný výkon
jinde tři.

538
00:23:56,710 --> 00:23:58,570
A to je to, co jsem používal
alokovat pole.

539
00:23:58,570 --> 00:24:03,535
Velikost se bude odkazovat na to, kolik
zásobníky jsou v současné době na zásobníku.

540
00:24:03,535 --> 00:24:03,880
>> STEVEN: Zero.

541
00:24:03,880 --> 00:24:04,460
>> DAVID Malan: Tak to musí být nula.

542
00:24:04,460 --> 00:24:07,760
Takže jděte do toho a s jakýmkoliv prstem,
nakreslit nulu velikosti.

543
00:24:07,760 --> 00:24:08,440
Dobrá.

544
00:24:08,440 --> 00:24:10,920
Takže teď, co je uvnitř tohoto
tady, nevíme.

545
00:24:10,920 --> 00:24:12,160
Jsou to opravdu jen odpadky hodnoty.

546
00:24:12,160 --> 00:24:14,800
Takže bychom mohli čerpat otazníky, ale
Zkusme udržet deska čistá teď

547
00:24:14,800 --> 00:24:16,300
protože nezáleží na tom,
co tam je.

548
00:24:16,300 --> 00:24:19,130
Nepotřebujeme k inicializaci pole
k ničemu, protože pokud víme, že

549
00:24:19,130 --> 00:24:23,100
velikost zásobníku je nula, no,
nesmí být při pohledu na něco v

550
00:24:23,100 --> 00:24:25,590
Toto pole tak na
tento bod v čase.

551
00:24:25,590 --> 00:24:29,970
>> Takže teď, předpokládám, že tlačím
číslo 9 do zásobníku.

552
00:24:29,970 --> 00:24:33,750
Jak bychom měli aktualizovat datovou strukturu
Uvnitř této černé skříňky?

553
00:24:33,750 --> 00:24:35,540
Jaké hodnoty je třeba změnit?

554
00:24:35,540 --> 00:24:36,200
>> STEVEN: V -

555
00:24:36,200 --> 00:24:37,400
velikost?

556
00:24:37,400 --> 00:24:37,650
>> DAVID Malan: OK.

557
00:24:37,650 --> 00:24:38,770
Velikost by měla být co?

558
00:24:38,770 --> 00:24:39,580
>> STEVEN: Velikost by byl jeden.

559
00:24:39,580 --> 00:24:39,870
>> DAVID Malan: OK.

560
00:24:39,870 --> 00:24:41,110
Takže velikost by se měla stát jedním.

561
00:24:41,110 --> 00:24:42,540
Takže si můžete udělat v pár ohledech.

562
00:24:42,540 --> 00:24:46,920
Dovolte mi, abych vám nyní vaše
Prst je guma.

563
00:24:46,920 --> 00:24:47,260
Dobrá.

564
00:24:47,260 --> 00:24:49,960
Tak teď je prst kartáč.

565
00:24:49,960 --> 00:24:50,330
Dobrá.

566
00:24:50,330 --> 00:24:52,820
A teď, co ještě se musí změnit,
Je zřejmé, že v datové struktuře?

567
00:24:52,820 --> 00:24:57,060
>> STEVEN: Jdeme od
zdola až 9.

568
00:24:57,060 --> 00:24:57,760
>> DAVID Malan: 9.

569
00:24:57,760 --> 00:24:58,420
OK, dobře.

570
00:24:58,420 --> 00:25:01,550
Takže ještě nezáleží, co je v
umístění jeden nebo dva, protože jsou

571
00:25:01,550 --> 00:25:04,520
odpadky hodnoty, ale neměli bychom se obtěžovat
hledá tam, protože velikost je

572
00:25:04,520 --> 00:25:07,540
nám říká, že pouze první prvek
je vlastně legitimní.

573
00:25:07,540 --> 00:25:10,400
Takže teď tlačím 17 na seznamu.

574
00:25:10,400 --> 00:25:11,830
Co se stane obrázku?

575
00:25:11,830 --> 00:25:14,720
>> STEVEN: Takže velikost se chystá jít na dva.

576
00:25:14,720 --> 00:25:15,300
>> DAVID Malan: OK.

577
00:25:15,300 --> 00:25:16,070
Jste guma -

578
00:25:16,070 --> 00:25:16,810
oops.

579
00:25:16,810 --> 00:25:18,026
Jste gumu.

580
00:25:18,026 --> 00:25:18,840
>> STEVEN: Eraser.

581
00:25:18,840 --> 00:25:19,720
>> DAVID Malan: Jsi kartáč.

582
00:25:19,720 --> 00:25:20,560
>> STEVEN: Brush.

583
00:25:20,560 --> 00:25:20,920
>> DAVID Malan: OK.

584
00:25:20,920 --> 00:25:21,600
A co ještě?

585
00:25:21,600 --> 00:25:22,600
>> STEVEN: A pak jsme -

586
00:25:22,600 --> 00:25:22,915
>> DAVID Malan: Usilovali jsme 17.

587
00:25:22,915 --> 00:25:24,760
>> STEVEN: Držíme 17 na vrcholu, a proto -

588
00:25:24,760 --> 00:25:25,710
>> DAVID Malan: OK, dobře.

589
00:25:25,710 --> 00:25:27,040
>> STEVEN - klesnout dolů.

590
00:25:27,040 --> 00:25:27,530
>> DAVID Malan: Dobře.

591
00:25:27,530 --> 00:25:27,940
Začíná to být snadné.

592
00:25:27,940 --> 00:25:29,300
Nebudu, které vám pomohou tentokrát.

593
00:25:29,300 --> 00:25:30,510
Zatlačte 22.

594
00:25:30,510 --> 00:25:31,720
>> STEVEN: Hotovo.

595
00:25:31,720 --> 00:25:34,870
Stát gumu.

596
00:25:34,870 --> 00:25:37,340
Stávám se štětcem.

597
00:25:37,340 --> 00:25:39,340
A pak dávám 22.

598
00:25:39,340 --> 00:25:40,100
>> DAVID Malan: 22.

599
00:25:40,100 --> 00:25:40,620
Výborný.

600
00:25:40,620 --> 00:25:41,380
Takže ještě jednou.

601
00:25:41,380 --> 00:25:44,280
Já jsem teď bude tlačit
do zásobníku 26.

602
00:25:44,280 --> 00:25:46,350
>> STEVEN: Ooh.

603
00:25:46,350 --> 00:25:50,278
Ach bože.

604
00:25:50,278 --> 00:25:52,520
Opravdu mě zaskočila.

605
00:25:52,520 --> 00:25:53,703
>> DAVID Malan: To snad ne
viz letos?

606
00:25:53,703 --> 00:25:55,930
>> STEVEN: Neviděl jsem to blíží.

607
00:25:55,930 --> 00:25:58,756
Mohli bychom znovu počáteční kapacita?

608
00:25:58,756 --> 00:25:59,790
>> DAVID Malan: To je dobrá otázka.

609
00:25:59,790 --> 00:26:02,360
Takže jsme trochu maloval sebe
v rohu zde.

610
00:26:02,360 --> 00:26:06,740
Tam opravdu není dobrý pozor Steven
protože jsme přiděleno toto pole

611
00:26:06,740 --> 00:26:09,130
staticky, abych tak řekl, uvnitř
z datové struktury.

612
00:26:09,130 --> 00:26:12,170
A my jsme v podstatě pevně zakódován
se, že je velikost tři.

613
00:26:12,170 --> 00:26:14,170
Takže opravdu nemůžeme přerozdělí ji.

614
00:26:14,170 --> 00:26:20,020
>> Mohli bychom, kdybychom šli zpátky, jsme
obnovován zásobníky se ukazatel, který

615
00:26:20,020 --> 00:26:22,300
jsme pak pomocí malloc do ruky paměti.

616
00:26:22,300 --> 00:26:25,050
Protože pokud máme paměť, z
haldy pomocí malloc, jsme

617
00:26:25,050 --> 00:26:26,430
by pak uvolnit jej.

618
00:26:26,430 --> 00:26:29,630
Ale dříve, než ji uvolní, mohli bychom
přerozdělit větší kus paměti,

619
00:26:29,630 --> 00:26:31,330
aktualizovat ukazatel, a tak dále.

620
00:26:31,330 --> 00:26:33,500
Ale teď je to opravdu
nejlepší, co můžeme udělat.

621
00:26:33,500 --> 00:26:36,360
Stiskněte a pop se pravděpodobně bude
mají uvést některé chyby.

622
00:26:36,360 --> 00:26:40,270
>> Tak například, naše realizace
Push by se mohl vrátit bool, která

623
00:26:40,270 --> 00:26:42,390
předtím vrátil pravda, pravda, pravda.

624
00:26:42,390 --> 00:26:48,390
Ale čtvrtý čas, bude to mít
vrátit false, například.

625
00:26:48,390 --> 00:26:48,540
Dobrá.

626
00:26:48,540 --> 00:26:49,540
Velmi dobře.

627
00:26:49,540 --> 00:26:50,060
Blahopřejeme.

628
00:26:50,060 --> 00:26:52,160
Získali jste stresu míč dnes.

629
00:26:52,160 --> 00:26:53,110
>> [APPLAUSE]

630
00:26:53,110 --> 00:26:54,382
>> STEVEN: Děkuji.

631
00:26:54,382 --> 00:26:55,680
>> DAVID Malan: Děkuji.

632
00:26:55,680 --> 00:26:59,740
OK, tak to se zdá být moc
o krok vpřed, ne?

633
00:26:59,740 --> 00:27:01,410
Popsali jsme tuto datovou strukturu.

634
00:27:01,410 --> 00:27:02,320
Bylo to působivé, ne?

635
00:27:02,320 --> 00:27:03,200
Operační systémy líbit.

636
00:27:03,200 --> 00:27:06,360
Zřejmě na webu můžete využívat toto,
a dalších aplikací stále.

637
00:27:06,360 --> 00:27:10,870
Ale to, co hloupé omezení, že jsme
zpět na třídění v týdnu dva limity

638
00:27:10,870 --> 00:27:12,880
kde jsme pevnou velikost pole.

639
00:27:12,880 --> 00:27:15,010
>> Takže tam jsou opravdu pár
způsoby, jak bychom mohli vyřešit.

640
00:27:15,010 --> 00:27:18,750
Mohli bychom dynamicky alokovat pole,
ne těžké kódování jako jsem

641
00:27:18,750 --> 00:27:22,600
hotoví, ale znovu, kterým
to, aby bylo jasno, jak

642
00:27:22,600 --> 00:27:23,830
něco takového.

643
00:27:23,830 --> 00:27:29,040
Int * zásobníky, nerozhoduje
na objemu ještě.

644
00:27:29,040 --> 00:27:35,460
Ale když jsem prohlásil stoh jinde
v mém kódu, mohl bych pak volání malloc,

645
00:27:35,460 --> 00:27:38,250
získat adresu kusem
paměť, a já jsem mohl přiřadit

646
00:27:38,250 --> 00:27:39,980
že adresa zásobníků.

647
00:27:39,980 --> 00:27:43,340
>> A pak, protože je to jen kus
paměť, mohl bych i nadále používat náměstí

648
00:27:43,340 --> 00:27:45,450
držák zápis obvyklým způsobem.

649
00:27:45,450 --> 00:27:49,020
Vzhledem k tomu znovu, je tu nějak to
funkčním ekvivalentem polí a

650
00:27:49,020 --> 00:27:50,820
kousky paměti, které přicházejí
zpět z malloc.

651
00:27:50,820 --> 00:27:53,090
Můžeme chovat jako ostatní
pomocí ukazatele aritmetický nebo

652
00:27:53,090 --> 00:27:54,440
hranatá závorka notace.

653
00:27:54,440 --> 00:27:55,660
Takže to je jeden přístup.

654
00:27:55,660 --> 00:28:00,120
>> Ale jak jinak bychom mohli zavést tento
stejné datové struktury, případně?

655
00:28:00,120 --> 00:28:00,280
Je to tak?

656
00:28:00,280 --> 00:28:04,530
Mám pocit, že právě to vyřešil
problém jako před týdnem.

657
00:28:04,530 --> 00:28:08,860
Co bylo řešení tohoto problému
že Steven narazil?

658
00:28:08,860 --> 00:28:10,370
Takže spojové seznamy, vpravo.

659
00:28:10,370 --> 00:28:13,410
>> Pokud je problém, že malujeme
sami do rohu přidělování

660
00:28:13,410 --> 00:28:17,580
předem příliš málo paměti, že
pak se nějak řešit, no,

661
00:28:17,580 --> 00:28:19,880
proč ne jen zabránit tomu, aby
vydá dohromady?

662
00:28:19,880 --> 00:28:26,170
Proč ne jen prohlásit zásobníky se
ukazatel na uzel, ergo spojový seznam,

663
00:28:26,170 --> 00:28:30,740
a pak jednoduše přidělit nové uzly
pokaždé, když Steven třeba, aby se vešly

664
00:28:30,740 --> 00:28:32,400
číslo do datové struktury.

665
00:28:32,400 --> 00:28:34,200
>> Takže obraz by měl změnit.

666
00:28:34,200 --> 00:28:38,220
To nebude tak čisté a jako
jednoduché, jak jen pole tří ints.

667
00:28:38,220 --> 00:28:42,970
Teď to bude ukazatel na
struct, a to struct se chystá

668
00:28:42,970 --> 00:28:44,830
mají int a další ukazatel.

669
00:28:44,830 --> 00:28:47,670
Je to povede prostřednictvím tohoto ukazatele
jiné takové struct na

670
00:28:47,670 --> 00:28:48,600
další takový struct.

671
00:28:48,600 --> 00:28:50,560
Takže obrázek by tak ve skutečnosti
dostat trochu Messier.

672
00:28:50,560 --> 00:28:52,950
A byli bychom šipky vázání
všechno dohromady.

673
00:28:52,950 --> 00:28:55,280
>> Ale to je v pořádku, že jo, protože
Viděli jsme, jak to udělat.

674
00:28:55,280 --> 00:28:58,180
A jakmile se dostanete pohodlně
provádí něco jako propojený

675
00:28:58,180 --> 00:29:01,450
seznam, který budete muset dělat, když
rozhodnete hash tabulku s

676
00:29:01,450 --> 00:29:05,120
oddělené zřetězení pro p-set 6, můžete
jej použít jako stavební blok, nebo

677
00:29:05,120 --> 00:29:08,870
přísada, nebo Scratch mluvit,
postup, něco, co dáte, vám

678
00:29:08,870 --> 00:29:12,560
vytvořili svůj vlastní kousek skládačky
které pak můžete znovu použít.

679
00:29:12,560 --> 00:29:17,090
Takže kompromisy, ale možná řešení
že jsme vlastně neviděli.

680
00:29:17,090 --> 00:29:20,560
>> Takže docela často, vidíte to každý
rok nebo dva, když Apple vydal

681
00:29:20,560 --> 00:29:23,060
něco nového, a všichni blázni
line up mimo Apple

682
00:29:23,060 --> 00:29:27,050
uložit ke koupi jejich marginální
přejít na hardware.

683
00:29:27,050 --> 00:29:30,420
Říkám to, je to v pořádku, protože
Jsem jeden z těch lidí.

684
00:29:30,420 --> 00:29:35,140
Takže, jaké datové struktury
může představovat tuto skutečnost?

685
00:29:35,140 --> 00:29:36,980
>> No, řekněme, že fronta, linka.

686
00:29:36,980 --> 00:29:40,270
Takže Britové to nazval typicky
fronta stejně, takže je to hezké jméno.

687
00:29:40,270 --> 00:29:44,960
A dvě operace, které fronty
musí podporovat budeme volat Zařadí

688
00:29:44,960 --> 00:29:48,900
provoz a dequeue provoz,
které jsou si podobné

689
00:29:48,900 --> 00:29:50,120
duch tlačit a pop.

690
00:29:50,120 --> 00:29:54,060
Je to jen trochu liší
konvence, co říkáme nich.

691
00:29:54,060 --> 00:29:57,680
Ale enqueue něco znamená přidat
nebo vložit do datové struktury.

692
00:29:57,680 --> 00:29:59,570
Dequeue znamená odstranit.

693
00:29:59,570 --> 00:30:05,170
Ale vzhledem k tomu, zásobník byl datový LIFO
struktura, fronta je první,

694
00:30:05,170 --> 00:30:06,740
První z datové struktury.

695
00:30:06,740 --> 00:30:10,050
>> Pokud jste první člověk v řadě,
budete první osoba, která se

696
00:30:10,050 --> 00:30:12,420
z řady a koupit si nový přístroj.

697
00:30:12,420 --> 00:30:18,070
Představte si, jak naštvaný tito lidé by
pokud Apple místo toho používal balík pro

698
00:30:18,070 --> 00:30:21,250
instance, k provedení vychystávání
do vaší novou hračku.

699
00:30:21,250 --> 00:30:24,310
Takže fronty smysl, určitě, a
my můžeme myslet na všechny druhy

700
00:30:24,310 --> 00:30:27,480
aplikace, pravděpodobně pro front,
zvláště když chcete spravedlnost.

701
00:30:27,480 --> 00:30:30,040
Takže, jak můžeme realizovat tyto
jako datové struktury?

702
00:30:30,040 --> 00:30:33,680
>> Navrhuji, že bychom mohli
musíte udělat to takhle.

703
00:30:33,680 --> 00:30:35,225
Takže budu teď mít čísla.

704
00:30:35,225 --> 00:30:38,190
Takže budeme držet to jednoduchý, a ne
nutně mluvit, pokud jde o zásobníků.

705
00:30:38,190 --> 00:30:40,220
Jen čísla, která lidé dostali.

706
00:30:40,220 --> 00:30:43,760
Kapacita bude opět upevněte
Celkový počet osob, které mohou být v

707
00:30:43,760 --> 00:30:46,900
tento řádek jako tří nebo
bez ohledu na jiná hodnota.

708
00:30:46,900 --> 00:30:50,760
>> Ale navrhuji, že musím sledovat
nejen velikostí

709
00:30:50,760 --> 00:30:52,370
fronta, kolik věcí v něm.

710
00:30:52,370 --> 00:30:56,310
Takže velikost je aktuální velikost, kapacita
je maximální velikost.

711
00:30:56,310 --> 00:30:58,540
Jen jednou, nomenklatura
konvencí.

712
00:30:58,540 --> 00:31:03,680
Proč potřebuji další int uvnitř
z fronty, jak sledovat, kdo je v

713
00:31:03,680 --> 00:31:05,365
přední linie?

714
00:31:05,365 --> 00:31:07,930

715
00:31:07,930 --> 00:31:10,910
Proč musím k tomu, že v tomto případě?

716
00:31:10,910 --> 00:31:14,750

717
00:31:14,750 --> 00:31:16,190
>> No, jak se tento obrázek
se změní?

718
00:31:16,190 --> 00:31:19,280
Mohl bych opětovně využít většinu
obrázku.

719
00:31:19,280 --> 00:31:21,480
Nech mě jít napřed a vymazat to, co je tady.

720
00:31:21,480 --> 00:31:24,580
Dáme to lehce
jiné jméno tady.

721
00:31:24,580 --> 00:31:28,930
Pojďme se zbavit 17, zbavme
na 9, pojďme se zbavit 3.

722
00:31:28,930 --> 00:31:30,410
A dodejme ještě jednu věc.

723
00:31:30,410 --> 00:31:34,710
Navrhuji, že musím sledovat
přední seznamu, který je právě

724
00:31:34,710 --> 00:31:35,570
Bude také int.

725
00:31:35,570 --> 00:31:36,550
A budeme držet to jednoduchý.

726
00:31:36,550 --> 00:31:37,740
Ne spojový seznam nyní.

727
00:31:37,740 --> 00:31:40,900
>> Budeme se přiznat, že budeme
Narazí tohoto limitu.

728
00:31:40,900 --> 00:31:43,720
Ale co já chci vidět
se stalo tentokrát?

729
00:31:43,720 --> 00:31:47,240
Tak, že jsem do toho pusťte a první
osoba je v souladu, a

730
00:31:47,240 --> 00:31:48,560
je to číslo 9..

731
00:31:48,560 --> 00:31:49,680
Máme stres koule.

732
00:31:49,680 --> 00:31:51,330
Můžu ukrást, řekněme, dva nebo tři lidi?

733
00:31:51,330 --> 00:31:52,690
Jedna, dva, tři?

734
00:31:52,690 --> 00:31:53,120
Pojď nahoru.

735
00:31:53,120 --> 00:31:56,022
Právo zepředu, protože
uděláme tohle rychle.

736
00:31:56,022 --> 00:31:59,415
>> Každý z vás se nyní bude
fan kluk ve frontě na Apple.

737
00:31:59,415 --> 00:32:03,970

738
00:32:03,970 --> 00:32:06,210
Nebudete dostávat Apple hardware
Na konci tohoto ačkoli.

739
00:32:06,210 --> 00:32:06,500
Dobrá.

740
00:32:06,500 --> 00:32:09,430
Takže ty jsi číslo 9, ty jsi
číslo 17, číslo 22.

741
00:32:09,430 --> 00:32:12,130
Ty jsou libovolná čísla, jako je
Student ID nebo kdoví co ještě.

742
00:32:12,130 --> 00:32:14,550
A za chvíli, začněme
začít přidávat věci.

743
00:32:14,550 --> 00:32:16,000
A já budu běžet desku zde tentokrát.

744
00:32:16,000 --> 00:32:19,570
>> Takže v tomto případě jsem si inicializuje
přední být -

745
00:32:19,570 --> 00:32:22,380
Vlastně jsem opravdu nestarám, co
přední část je, protože velikost je nula.

746
00:32:22,380 --> 00:32:24,480
Takže to může být i jen
být otazník.

747
00:32:24,480 --> 00:32:26,170
To všechno jsou otazníky.

748
00:32:26,170 --> 00:32:29,880
Takže teď začneme skutečně vidět některé
lidé čekají, až v obchodě.

749
00:32:29,880 --> 00:32:33,320
>> Takže pokud číslo 9, ty jsi první,
tam v 5 hodin ráno, jděte do toho a line up,

750
00:32:33,320 --> 00:32:34,210
nebo v noci.

751
00:32:34,210 --> 00:32:34,580
OK.

752
00:32:34,580 --> 00:32:35,940
Takže teď 9 je tady.

753
00:32:35,940 --> 00:32:37,940
Takže 9 je v přední části seznamu.

754
00:32:37,940 --> 00:32:41,440
Takže budu pokračovat a aktualizovat
Velikost tohoto aktuálních dat

755
00:32:41,440 --> 00:32:44,740
strukturu, která není už 0,
ale na 1.

756
00:32:44,740 --> 00:32:47,630
Chystám se dát na 9
Přední seznamu.

757
00:32:47,630 --> 00:32:51,020
Nech mě jít dopředu a přepínat obrazovky
takže vidíme kolem nás zde.

758
00:32:51,020 --> 00:32:53,220
>> A teď co chci
dát na přední straně?

759
00:32:53,220 --> 00:32:56,240
Budu sledovat, že
přední fronty hned

760
00:32:56,240 --> 00:32:58,570
je v místě 0.

761
00:32:58,570 --> 00:33:00,510
Protože to, co se bude dít příště?

762
00:33:00,510 --> 00:33:03,000
No, předpokládám, teď jsem enqueue
17 také.

763
00:33:03,000 --> 00:33:04,510
Tak hop v řadě tam.

764
00:33:04,510 --> 00:33:07,060
A opět, typ dveří
Obchod se tu bude.

765
00:33:07,060 --> 00:33:08,700
Takže teď jsem přidal 17.

766
00:33:08,700 --> 00:33:10,810
A i když tihle kluci jsou blokování
obrazovka, to je v pořádku,

767
00:33:10,810 --> 00:33:12,300
protože vidíme to tady.

768
00:33:12,300 --> 00:33:12,910
Promiňte.

769
00:33:12,910 --> 00:33:13,810
>> DIVÁKŮ: Můžeme se pohybovat -

770
00:33:13,810 --> 00:33:14,660
>> DAVID Malan: Ne, to je v pořádku.

771
00:33:14,660 --> 00:33:16,000
Je to obrovská tam.

772
00:33:16,000 --> 00:33:18,580
Takže 17 je nyní uvnitř fronty.

773
00:33:18,580 --> 00:33:21,332
Musím aktualizovat, která
Pole teď když?

774
00:33:21,332 --> 00:33:23,210
OK, určitě velikosti.

775
00:33:23,210 --> 00:33:26,430
A co přední?

776
00:33:26,430 --> 00:33:27,040
OK, no.

777
00:33:27,040 --> 00:33:30,200
Přední by se nemělo měnit, protože
na rozdíl od zásobníku, jsme

778
00:33:30,200 --> 00:33:31,370
chcete zachovat spravedlnost.

779
00:33:31,370 --> 00:33:35,150
Takže pokud 9 přišel první, chceme 9
, že je první z řady

780
00:33:35,150 --> 00:33:36,420
do obchodu.

781
00:33:36,420 --> 00:33:37,220
>> Ve skutečnosti, ať se na to.

782
00:33:37,220 --> 00:33:42,235
Než vložíme 22, pojďme
jděte do toho a dequeue 9.

783
00:33:42,235 --> 00:33:42,970
Jak se jmenujete?

784
00:33:42,970 --> 00:33:43,680
>> Diváků: Jake.

785
00:33:43,680 --> 00:33:45,440
>> DAVID Malan: Jake se děje
být dequeued teď.

786
00:33:45,440 --> 00:33:48,050
Takže jste si na procházku do obchodu.

787
00:33:48,050 --> 00:33:49,880
A předstírat, že obchod
je támhle.

788
00:33:49,880 --> 00:33:51,970
Takže teď, co je potřeba - dit-dit-dit!

789
00:33:51,970 --> 00:33:53,400
Co by se stalo teď?

790
00:33:53,400 --> 00:33:54,490
Návrh rozhodnutí.

791
00:33:54,490 --> 00:33:56,825
Takže není špatný instinkt, ale -
co se to jmenujete?

792
00:33:56,825 --> 00:33:57,090
>> DIVÁKŮ: David.

793
00:33:57,090 --> 00:33:57,500
>> DAVID Malan: David.

794
00:33:57,500 --> 00:33:58,810
Takže to, co David udělal?

795
00:33:58,810 --> 00:34:02,590
Snažil se nějak opravit údaje
struktura a pohyb od jeho umístění

796
00:34:02,590 --> 00:34:04,100
v bývalém místě Jake.

797
00:34:04,100 --> 00:34:06,740
A to je v pořádku, pokud jsme ochotni
přijmout, že jako

798
00:34:06,740 --> 00:34:08,199
implementační detail.

799
00:34:08,199 --> 00:34:11,100
Ale nejprve pojďme aktualizovat data
strukturu, než to děláme.

800
00:34:11,100 --> 00:34:14,139
Protože jsem nelíbil nápad všech
lidé posun v tomto oboru.

801
00:34:14,139 --> 00:34:17,360
>> Není to velký problém, pokud David dělá s
jeden krok, ale opět si vzpomenu na

802
00:34:17,360 --> 00:34:20,360
když jsme měli osm dobrovolníků na
etapa a udělali jsme jako vložení

803
00:34:20,360 --> 00:34:22,600
třídění, kde jsme museli začít
pohybující se všichni kolem.

804
00:34:22,600 --> 00:34:23,790
To má drahá, že jo?

805
00:34:23,790 --> 00:34:28,330
To mě krčit se o velké O
n, velký O n na druhou znovu.

806
00:34:28,330 --> 00:34:30,650
Není to pocit,
ideální výsledek.

807
00:34:30,650 --> 00:34:32,080
>> Takže řekněme, aktualizovat to.

808
00:34:32,080 --> 00:34:35,120
Takže velikost fronty
není 2.

809
00:34:35,120 --> 00:34:37,090
Je to teď prostě jedno.

810
00:34:37,090 --> 00:34:40,360
Ale nyní mohu aktualizovat něco
Nechtěl jsem aktualizovat dříve,

811
00:34:40,360 --> 00:34:41,130
Přední seznamu.

812
00:34:41,130 --> 00:34:45,420
Mohl bych říct, je, že místo 1?

813
00:34:45,420 --> 00:34:49,770
Takže teď máme odpadky hodnoty zde
odpadky hodnota zde a David v

814
00:34:49,770 --> 00:34:51,469
Uprostřed tohoto odpadu.

815
00:34:51,469 --> 00:34:54,980
Ale struktura dat
je stále neporušená.

816
00:34:54,980 --> 00:34:58,540
>> A ve skutečnosti jsem ani potřeba
změnit Jake je bývalý číslo

817
00:34:58,540 --> 00:35:00,460
9, protože koho to zajímá.

818
00:35:00,460 --> 00:35:04,470
Mám dostatek informací, nyní v
velikost, že vím, je tu ještě jedna osoba

819
00:35:04,470 --> 00:35:05,030
Tato fronta.

820
00:35:05,030 --> 00:35:08,340
A vím, že tato osoba
je v místě 1, ne 0.

821
00:35:08,340 --> 00:35:09,760
Nepočítám.

822
00:35:09,760 --> 00:35:11,300
1. tak i.

823
00:35:11,300 --> 00:35:13,410
Takže datová struktura je ještě OK.

824
00:35:13,410 --> 00:35:14,330
>> No, co se stane dál?

825
00:35:14,330 --> 00:35:15,010
Pojďme enqueue -

826
00:35:15,010 --> 00:35:15,370
Jak se jmenujete?

827
00:35:15,370 --> 00:35:16,160
>> Diváků: Callen.

828
00:35:16,160 --> 00:35:16,580
>> DAVID Malan: Callen.

829
00:35:16,580 --> 00:35:20,770
Pojďme si enqueue Callen a
22 je nyní ve frontě.

830
00:35:20,770 --> 00:35:22,300
Takže teď, co se musí změnit, tady?

831
00:35:22,300 --> 00:35:24,380
Přední nebude
změnit, samozřejmě.

832
00:35:24,380 --> 00:35:27,160
Velikost se změní na 2 znovu.

833
00:35:27,160 --> 00:35:31,590
A 22 skončí tady, 9 je stále přítomna,
ale je to skutečně

834
00:35:31,590 --> 00:35:32,600
odpadky hodnota se.

835
00:35:32,600 --> 00:35:35,910
Je to jen pozůstatek minulosti Jake.

836
00:35:35,910 --> 00:35:39,200
>> Takže teď, co se stane, když
I dequeue Davide?

837
00:35:39,200 --> 00:35:41,560
Jedna poslední operace, dequeue David.

838
00:35:41,560 --> 00:35:46,070
Mohli bychom se posunout, ale navrhuji, pojďme
co nejméně práce, jak je to možné.

839
00:35:46,070 --> 00:35:50,280
Teď můj datová struktura jde
zpět ve velikosti 2-1.

840
00:35:50,280 --> 00:35:53,730
Ale fronty
Nyní se 2.

841
00:35:53,730 --> 00:35:56,640
Nepotřebuji, aby tato čísla změnit
ještě ne, protože jsou

842
00:35:56,640 --> 00:35:58,230
jen nesmyslné hodnoty.

843
00:35:58,230 --> 00:35:59,720
>> Ale teď, co se stane?

844
00:35:59,720 --> 00:36:03,280
Dejme tomu, že jsem enqueue, 26?

845
00:36:03,280 --> 00:36:05,890
Mám pocit, že patřím sem.

846
00:36:05,890 --> 00:36:06,890
Takže jsem byl enqueued.

847
00:36:06,890 --> 00:36:08,760
Tak nějak jsem sem patřím.

848
00:36:08,760 --> 00:36:11,300
A i když to není zcela
vážím vizuálně na jevišti,

849
00:36:11,300 --> 00:36:15,075
protože máme dostatek prostoru, měl bych
nelze tady stojím, proč?

850
00:36:15,075 --> 00:36:16,290
>> DIVÁKŮ: Jsi mimo hrací plochu.

851
00:36:16,290 --> 00:36:16,370
>> DAVID Malan: Správně.

852
00:36:16,370 --> 00:36:16,940
Jsem mimo meze.

853
00:36:16,940 --> 00:36:19,330
Jsem indexovány za
hranice tohoto pole.

854
00:36:19,330 --> 00:36:23,420
Měl bych být v jednom z
tři možné lokality.

855
00:36:23,420 --> 00:36:25,150
Tak, kde je nejpřirozenější jít?

856
00:36:25,150 --> 00:36:27,760
Navrhuji, abychom pákové
týden jeden trik.

857
00:36:27,760 --> 00:36:30,150
Operátor modulo, procento.

858
00:36:30,150 --> 00:36:36,850
Protože jsem stál u technicky
místo 3, ale mám 3 mod kapacity,

859
00:36:36,850 --> 00:36:40,250
takže 3, znak procenta, 3 -

860
00:36:40,250 --> 00:36:40,970
Kapacita je 3.

861
00:36:40,970 --> 00:36:41,720
Co je to?

862
00:36:41,720 --> 00:36:43,700
Co je to zbytek po
dělíte 3 od 3?

863
00:36:43,700 --> 00:36:44,070
0.

864
00:36:44,070 --> 00:36:48,140
>> Tak, že mě staví se Jake,
což je vlastně dobře.

865
00:36:48,140 --> 00:36:50,370
Takže teď provádění
z toho, co se děje na

866
00:36:50,370 --> 00:36:51,250
být trochu bolí hlava.

867
00:36:51,250 --> 00:36:53,740
Je to opravdu jen jeden řádek
bolesti hlavy, kódu.

868
00:36:53,740 --> 00:36:56,580
Ale aspoň teď je tu odpadky
hodnotu, ale je tu to dva

869
00:36:56,580 --> 00:36:57,910
legitimní ints zde.

870
00:36:57,910 --> 00:37:04,160
A tvrdím, že teď jsme udělali
přesně to, co musíme udělat, tak dlouho, dokud

871
00:37:04,160 --> 00:37:08,600
změníme to, co Jake
hodnota měla být 26.

872
00:37:08,600 --> 00:37:12,110
>> Nyní máme dostatek informací, stále
zachování integrity

873
00:37:12,110 --> 00:37:13,060
této datové struktury.

874
00:37:13,060 --> 00:37:17,160
Jsme stále trochu smůlu, když jsme
Chci vložit čtyři nebo více celkem

875
00:37:17,160 --> 00:37:20,740
prvky, ale můžu se aspoň pěkně
efektivní využití této konstanty

876
00:37:20,740 --> 00:37:21,740
čas, ve skutečnosti.

877
00:37:21,740 --> 00:37:27,150
Nechci se starat o řazení
všichni, protože sklon Davida bylo.

878
00:37:27,150 --> 00:37:30,816
>> Jakékoliv dotazy týkající se komínů
nebo to fronta?

879
00:37:30,816 --> 00:37:32,184
>> DIVÁKŮ: Je důvod, proč
Potřebujete velikost, takže víte,

880
00:37:32,184 --> 00:37:34,010
kde má člověk?

881
00:37:34,010 --> 00:37:34,770
>> DAVID Malan: Přesně tak.

882
00:37:34,770 --> 00:37:38,230
Musím znát velikost pole
protože musím přesně vědět, jak

883
00:37:38,230 --> 00:37:41,940
mnoho z těchto hodnot jsou legitimní,
a aby najdu, kam umístit

884
00:37:41,940 --> 00:37:42,800
další osoba.

885
00:37:42,800 --> 00:37:43,300
Přesně tak.

886
00:37:43,300 --> 00:37:44,580
Velikost je -

887
00:37:44,580 --> 00:37:46,360
Vlastně jsme neměli aktualizovat to ještě.

888
00:37:46,360 --> 00:37:48,380
Přidal jsem sám na 26 let.

889
00:37:48,380 --> 00:37:51,760
Velikost je teď, ne jeden, ale dva.

890
00:37:51,760 --> 00:37:57,780
Takže teď to opravdu pomáhá mi najít
hlava seznamu, který není 0, není

891
00:37:57,780 --> 00:37:59,250
1, ale je 2..

892
00:37:59,250 --> 00:38:01,665
Na přední straně seznamu
je opravdu číslo 22.

893
00:38:01,665 --> 00:38:05,120
Vzhledem k tomu přišel jako první, a tak by
povoleno do obchodu přede mnou,

894
00:38:05,120 --> 00:38:08,780
i když vizuálně stojím
blíže k obchodu.

895
00:38:08,780 --> 00:38:09,220
>> V pořádku?

896
00:38:09,220 --> 00:38:12,410
Potlesk pro tyto lidi
a necháme je odtamtud.

897
00:38:12,410 --> 00:38:17,090
>> [APPLAUSE]

898
00:38:17,090 --> 00:38:18,150
>> DAVID Malan: Nemohl jsem nechat
budete mít zásobník.

899
00:38:18,150 --> 00:38:20,760
Mohli jsme vidět, co se stane, když
chcete, ale možná taky ne.

900
00:38:20,760 --> 00:38:21,590
Dobrá.

901
00:38:21,590 --> 00:38:25,380
Tak co teď co z toho plyne?

902
00:38:25,380 --> 00:38:28,900
No, dovolte mi navrhnout, aby tam
několik dalších datových struktur bychom mohli

903
00:38:28,900 --> 00:38:33,810
začít přidávat do našeho nářadí, které
ve skutečnosti je zcela, zcela relevantní

904
00:38:33,810 --> 00:38:35,270
jsme se ponořit do věcí webu.

905
00:38:35,270 --> 00:38:38,150
Což zase má nějaké spojení
na stromy ve formě

906
00:38:38,150 --> 00:38:40,550
něco jako DOM, dokument
objektový model.

907
00:38:40,550 --> 00:38:42,370
Ale uvidíme více
že zanedlouho.

908
00:38:42,370 --> 00:38:46,260
>> Dovolte mi navrhnout, z definice, že jsme
zavolejte strom teď, co byste mohli vědět, jak

909
00:38:46,260 --> 00:38:48,820
více rodokmenu, kde
nějaký předek na

910
00:38:48,820 --> 00:38:49,790
Kořeny stromu.

911
00:38:49,790 --> 00:38:54,480
Patriarchální nebo matriarcha na
samém vrcholu stromu.

912
00:38:54,480 --> 00:38:56,700
Bez svého manžela, v tomto případě.

913
00:38:56,700 --> 00:39:00,940
Ale nyní máme, co budeme nazývat
Děti, které jsou uzly, které visí

914
00:39:00,940 --> 00:39:05,480
z levé nebo pravé dítě dítě,
šipky, jak je znázorněno zde.

915
00:39:05,480 --> 00:39:10,490
>> Jinými slovy, ve stromové struktuře dat
v počítači, strom má nulu

916
00:39:10,490 --> 00:39:11,480
nebo více uzlů.

917
00:39:11,480 --> 00:39:13,500
Pokud má alespoň jeden uzel,
tomu se říká kořen.

918
00:39:13,500 --> 00:39:15,700
Jsou to věci, které vizuálně
čerpáme na vrcholu.

919
00:39:15,700 --> 00:39:20,280
A to uzel, jako každý jiný uzel, může
mají nulový, jeden, nebo dva, nebo tři,

920
00:39:20,280 --> 00:39:23,600
nebo jak mnoho dětí
datová struktura podporuje.

921
00:39:23,600 --> 00:39:29,150
V tomto případě, kořen, skladování
hodnoty jedna, má dvě děti, 2 a 3,

922
00:39:29,150 --> 00:39:33,020
takže jsme obvykle vyžadují dva levé
Dítě a 3 právo dítě.

923
00:39:33,020 --> 00:39:36,940
>> A pak, když se dostaneme až 5, 6, a
7, 6 by se dalo nazvat prostřední dítě.

924
00:39:36,940 --> 00:39:38,940
Pokud máte čtyři děti,
to bude matoucí.

925
00:39:38,940 --> 00:39:42,260
Tak jsme se přestat používat tento druh
o zástupce ústně.

926
00:39:42,260 --> 00:39:44,580
Ale je to opravdu jen rodokmen.

927
00:39:44,580 --> 00:39:48,880
A listy jsou zde uzlů, které
samy o sobě nemají žádné děti.

928
00:39:48,880 --> 00:39:52,540
Visí na dno stromu.

929
00:39:52,540 --> 00:39:56,940
>> Takže, jak můžeme realizovat strom, který
má jen dvě děti maximálně?

930
00:39:56,940 --> 00:39:58,410
Nazveme to binární strom.

931
00:39:58,410 --> 00:40:00,960
Bi opět znamená dva, v tomto
Stejně tak jako s binární.

932
00:40:00,960 --> 00:40:04,830
A tak to může mít nula, jedna,
nebo maximálně dvě děti.

933
00:40:04,830 --> 00:40:08,650
>> Já navrhuji, abychom realizovat uzel
pro tuto strukturu s int n,

934
00:40:08,650 --> 00:40:11,910
a pak dva ukazatele, jeden s názvem
vlevo, jeden volal pravdu.

935
00:40:11,910 --> 00:40:14,830
Ale to jsou jen pěkné
libovolné konvence.

936
00:40:14,830 --> 00:40:18,170
A co je hezké teď, zejména pokud
druh bojoval s koncepčně

937
00:40:18,170 --> 00:40:21,300
rekurze, nebo si myslel, že to není
opravdu řešení pro cokoliv,

938
00:40:21,300 --> 00:40:23,120
zejména pokud by
spustit z paměti.

939
00:40:23,120 --> 00:40:26,600
Teď, když mluvíme o datech
struktury a algoritmy, které umožňují

940
00:40:26,600 --> 00:40:31,030
nás projít a manipulovat s nimi,
Ukazuje se, že rekurze je zpět

941
00:40:31,030 --> 00:40:34,240
mnohem přesvědčivější
není-li krásný způsob.

942
00:40:34,240 --> 00:40:38,670
>> Takže to navrhuji, je implementace
z funkce Hledat.

943
00:40:38,670 --> 00:40:39,870
Vzhledem k tomu, dva vstupy -

944
00:40:39,870 --> 00:40:41,570
tak, že ji jako černá skříňka.

945
00:40:41,570 --> 00:40:46,560
Vzhledem k tomu, dva vstupy, n, int a
ukazatel na strom, ukazatel na

946
00:40:46,560 --> 00:40:50,020
uzel, nebo opravdu kořen stromu, jsem
Tvrzení, že tato funkce může vrátit

947
00:40:50,020 --> 00:40:53,530
true nebo false, že hodnota n
je uvnitř tohoto stromu.

948
00:40:53,530 --> 00:40:55,210
>> Co je uvnitř této černé skříňky?

949
00:40:55,210 --> 00:40:57,440
No, čtyři větve.

950
00:40:57,440 --> 00:40:58,385
První jen kontroluje.

951
00:40:58,385 --> 00:41:00,490
Je-li strom je null, stačí se vrátit false.

952
00:41:00,490 --> 00:41:04,580
Pokud není žádný uzel, není n,
tam žádné číslo, jen return false.

953
00:41:04,580 --> 00:41:12,330
Pokud však, n, hodnota, kterou hledáte
pro, je menší než stromu šipky n, a

954
00:41:12,330 --> 00:41:15,180
Jen aby bylo jasno, co to znamená, když
Píšu strom a pak klepněte na šipku

955
00:41:15,180 --> 00:41:18,150
notace, n?

956
00:41:18,150 --> 00:41:18,690
Přesně tak.

957
00:41:18,690 --> 00:41:21,970
To znamená, že Dereference
ukazatel tzv. strom.

958
00:41:21,970 --> 00:41:26,750
Jděte tam, a pak se uvnitř, které
uzel a získat jeho pole s názvem n.

959
00:41:26,750 --> 00:41:30,810
A pak porovnávat skutečné n, který byl
přešel do vyhledávacího proti němu.

960
00:41:30,810 --> 00:41:35,390
>> Takže, pokud n je menší než hodnota n
v uzlu stromu sám, dobře,

961
00:41:35,390 --> 00:41:36,720
co to znamená?

962
00:41:36,720 --> 00:41:40,690
To znamená, že nic na první pohled.

963
00:41:40,690 --> 00:41:40,900
Je to tak?

964
00:41:40,900 --> 00:41:45,560
Stejně jako když máte řadu
hodnoty, měli byste chtěli použít binární

965
00:41:45,560 --> 00:41:48,290
vyhledávání jako formu předělu
a panuj.

966
00:41:48,290 --> 00:41:51,790
Ale to, co jsme předpoklad, je třeba, aby
pro binární hledání práce vůbec

967
00:41:51,790 --> 00:41:54,510
v telefonním seznamu a
dříve příklady?

968
00:41:54,510 --> 00:41:55,530
>> Jak mají být tříděny.

969
00:41:55,530 --> 00:41:59,490
Takže pojďme upřesnit definici stromu
zde nesmí být jen strom, který může

970
00:41:59,490 --> 00:42:00,880
mít libovolný počet dětí.

971
00:42:00,880 --> 00:42:04,700
Není to jen binární strom, který může
jsou 0, 1, 2 nebo maximálně.

972
00:42:04,700 --> 00:42:09,700
Ale jako binární vyhledávací strom, nebo BST
který je jen ozdobný způsob, jak říkat

973
00:42:09,700 --> 00:42:15,430
binární strom, tak, že každý uzel je
vlevo dítě, pokud je přítomen, je

974
00:42:15,430 --> 00:42:16,830
méně než uzlu.

975
00:42:16,830 --> 00:42:20,170
A každý uzel má pravdu dítě
pokud je k dispozici, je větší

976
00:42:20,170 --> 00:42:21,740
než samotný uzel.

977
00:42:21,740 --> 00:42:25,200
>> Takže jinými slovy, pokud jste k tomu
strom se, všechna čísla jsou

978
00:42:25,200 --> 00:42:30,620
pečlivě vyvážit, jako je to tak, že pokud
Máte 55 jako root, může jít 33

979
00:42:30,620 --> 00:42:33,090
po jeho levé straně, protože to je méně než 55 let.

980
00:42:33,090 --> 00:42:36,430
77 může jít po jeho pravé straně, protože
je to více než 55 let.

981
00:42:36,430 --> 00:42:40,750
Ale teď nevšiml, stejnou definici,
Je to rekurzivní definice ústně,

982
00:42:40,750 --> 00:42:42,600
musí požádat o 33.

983
00:42:42,600 --> 00:42:47,610
33 levá dítě musí být menší než to,
a 33 na pravé dítě, 44, musí být

984
00:42:47,610 --> 00:42:48,580
větší než to.

985
00:42:48,580 --> 00:42:51,670
>> Tak to je strom binárního vyhledávání, a
Navrhuji, s použitím trochu

986
00:42:51,670 --> 00:42:53,910
rekurze, můžeme nyní najít n.

987
00:42:53,910 --> 00:42:59,160
Takže pokud je n menší než hodnotu n, která je
aktuální uzel, já jdu

988
00:42:59,160 --> 00:43:04,090
dopředu a punt, abych tak řekl, a jen
vrátit bez ohledu na odpověď na

989
00:43:04,090 --> 00:43:08,470
vyhledávání na n
stromu je levá dítě.

990
00:43:08,470 --> 00:43:11,370
Všimněte si, opět, tato funkce jen
očekává uzlu STAR,

991
00:43:11,370 --> 00:43:12,780
ukazatel na uzel.

992
00:43:12,780 --> 00:43:17,360
Tak určitě jsem si jen udělat strom
Šipka vlevo, což povede

993
00:43:17,360 --> 00:43:18,400
Přechod k jinému uzlu.

994
00:43:18,400 --> 00:43:19,480
Ale co je to uzel?

995
00:43:19,480 --> 00:43:22,820
>> No, podle tohoto prohlášení,
vlevo je jen ukazatel, takže stačí

996
00:43:22,820 --> 00:43:27,090
znamená, že jsem kolem na vyhledávací funkce
jiný ukazatel, a to

997
00:43:27,090 --> 00:43:30,750
který reprezentuje
Moje levá dítěte strom.

998
00:43:30,750 --> 00:43:36,040
Takže v tomto případě, ukazatel 33, je-li
To je náš výběr vstupu Zatím, pokud

999
00:43:36,040 --> 00:43:40,740
n je větší než hodnotu n na
aktuální uzel ve stromu, pak jsem

1000
00:43:40,740 --> 00:43:43,370
jít dopředu a pramice v druhé
směr a jen říct, vůbec se mi nelíbí

1001
00:43:43,370 --> 00:43:47,280
vědět, zda je tato hodnota n je ve stromové struktuře
ale vím, že pokud je to, že je to po mé

1002
00:43:47,280 --> 00:43:49,090
právo větev, abych tak řekl.

1003
00:43:49,090 --> 00:43:53,120
Dovolte mi tedy volání rekurzivně prohledávat,
vykonáním n znovu, ale předáním

1004
00:43:53,120 --> 00:43:54,580
ukazatel na mé pravé dítě.

1005
00:43:54,580 --> 00:44:00,020
>> Jinými slovy, když jsem v současné době 55
a hledám pro 99, já vím, že 99

1006
00:44:00,020 --> 00:44:04,270
je větší než 55, takže přesně jak jsem roztrhl
týdny telefonního seznamu lety a my

1007
00:44:04,270 --> 00:44:07,140
šel doprava, podobně jako jsme
jít tady.

1008
00:44:07,140 --> 00:44:11,960
A já nevím, jestli je to na mé pravici
dítě, a to není, 77 existuje, ale

1009
00:44:11,960 --> 00:44:13,210
Vím, že je v tomto směru.

1010
00:44:13,210 --> 00:44:18,770
Takže říkám hledání na pravém dítě,
77, a nechte vyhledávací postavu z

1011
00:44:18,770 --> 00:44:24,950
existuje-li 99 v tomto libovolná
Příkladem je ve skutečnosti tam.

1012
00:44:24,950 --> 00:44:26,900
>> Jinak, co je poslední případ?

1013
00:44:26,900 --> 00:44:28,620
Je-li strom je null jeden případ.

1014
00:44:28,620 --> 00:44:31,890
Pokud n je menší než je aktuální uzel je
hodnota je jiný případ.

1015
00:44:31,890 --> 00:44:35,120
Pokud n je větší než aktuální
uzlu hodnota je třetí případ.

1016
00:44:35,120 --> 00:44:38,250
Co je čtvrtý a poslední případ?

1017
00:44:38,250 --> 00:44:39,480
Myslím, že jsme z případů, ne?

1018
00:44:39,480 --> 00:44:44,690
To tak, že n je
aktuální uzel, že jsem na.

1019
00:44:44,690 --> 00:44:49,640
>> Takže když jsem hledal 55 v tomto bodě
v příběhu, že pobočka

1020
00:44:49,640 --> 00:44:51,780
strom se vrátí true.

1021
00:44:51,780 --> 00:44:55,380
Takže to, co je zajímavé, je, že jsme
ve skutečnosti, na rozdíl od minulosti týdnů, jsme trochu

1022
00:44:55,380 --> 00:44:56,740
na dva základní případy.

1023
00:44:56,740 --> 00:44:58,300
A oni nemají
být vše v horní části.

1024
00:44:58,300 --> 00:45:01,390
Horní je základní případ, protože v případě, že
Strom je null, nic dělat.

1025
00:45:01,390 --> 00:45:03,410
Stačí se vrátit pevný kódované
hodnota false.

1026
00:45:03,410 --> 00:45:07,400
>> Spodní větev je trochu
výchozí, přičemž když jsme zkontrolovat

1027
00:45:07,400 --> 00:45:11,550
null, jsme zkontrolovat, zda má být
vlevo, ale to by nemělo být, máme

1028
00:45:11,550 --> 00:45:14,640
kontroluje, zda by měl být správně, ale
neměly by být zřejmé, že musí být

1029
00:45:14,640 --> 00:45:15,870
tam, kde jsme.

1030
00:45:15,870 --> 00:45:16,780
To je základní věc.

1031
00:45:16,780 --> 00:45:19,920
Takže tam jsou dvě rekurzivní případy
obložené tam uprostřed.

1032
00:45:19,920 --> 00:45:21,630
Ale já jsem mohl napsat
to v libovolném pořadí.

1033
00:45:21,630 --> 00:45:24,520
Jen jsem myslel, že to trochu přišlo přirozené
nejprve zkontrolujte, zda případné chyby,

1034
00:45:24,520 --> 00:45:28,340
pak se podívejte doleva, pak se hned, pak
Předpokládám, že jste na uzlu

1035
00:45:28,340 --> 00:45:30,630
jste vlastně hledáte.

1036
00:45:30,630 --> 00:45:36,240
>> Tak proč by to mohlo být užitečné?

1037
00:45:36,240 --> 00:45:37,910
Tak to dopadá -

1038
00:45:37,910 --> 00:45:42,110
a dovolte mi přejít na ukázku
tady je to na webu.

1039
00:45:42,110 --> 00:45:44,920
Chystáme se začít používat ne
programovací jazyk na první, ale

1040
00:45:44,920 --> 00:45:46,030
značkovací jazyk.

1041
00:45:46,030 --> 00:45:48,740
Značkovací jazyk je ten, který je
svým duchem podobat programování

1042
00:45:48,740 --> 00:45:51,715
jazyk, ale to vám nedává
schopnost vyjádřit sám sebe logicky.

1043
00:45:51,715 --> 00:45:55,070
To vám dává možnost
vyjádřit sám sebe strukturálně.

1044
00:45:55,070 --> 00:45:57,960
>> Kam chceš dát něco
na stránce, webová stránka?

1045
00:45:57,960 --> 00:45:59,200
Jakou barvu chceš, aby se to?

1046
00:45:59,200 --> 00:46:00,950
Jaké písmo chceš, aby se to?

1047
00:46:00,950 --> 00:46:02,970
Jaká slova se vlastně
Chcete na webové stránce?

1048
00:46:02,970 --> 00:46:04,060
Takže je to značkovací jazyk.

1049
00:46:04,060 --> 00:46:07,690
Ale pak jsme si velmi rychle zavádět
JavaScript, který je plnohodnotným

1050
00:46:07,690 --> 00:46:08,560
programovací jazyk.

1051
00:46:08,560 --> 00:46:12,530
Velmi podobný ve vzhledu syntakticky
na C, ale bude to mít nějaký

1052
00:46:12,530 --> 00:46:15,200
pěkné, silnější,
uživatelsky přívětivé funkce.

1053
00:46:15,200 --> 00:46:18,050
>> A jeden z frustrace na to
bod v semestru, je, že budeme

1054
00:46:18,050 --> 00:46:22,065
brzy realizovat pravopisu v daleko méně
řádků kódu pomocí jiné jazyky

1055
00:46:22,065 --> 00:46:25,580
než C sám umožňuje, ale z důvodu je
Brzy budeme rozumět.

1056
00:46:25,580 --> 00:46:27,750
Bude to první taková webová stránka.

1057
00:46:27,750 --> 00:46:30,120
To bude zcela nezaujatý,
První děláme.

1058
00:46:30,120 --> 00:46:31,400
To se jednoduše říci, hello world.

1059
00:46:31,400 --> 00:46:34,010
Ale pokud jste nikdy neviděli
před, to je HTML,

1060
00:46:34,010 --> 00:46:35,670
HyperText Markup Language.

1061
00:46:35,670 --> 00:46:39,310
>> Pokud půjdete do určité menu v
téměř jakýkoli prohlížeč na jakékoliv webové stránky, na

1062
00:46:39,310 --> 00:46:43,160
internet, můžete vidět HTML
že někteří lidé psali

1063
00:46:43,160 --> 00:46:44,400
vytvořit tuto webovou stránku.

1064
00:46:44,400 --> 00:46:47,850
A to asi nevypadá jako
krátký nebo čistý, protože to.

1065
00:46:47,850 --> 00:46:51,400
Ale bude následovat vzor z nich
otevřené závorky a lomítka a

1066
00:46:51,400 --> 00:46:53,660
písmena a potenciálně čísla.

1067
00:46:53,660 --> 00:46:56,770
>> Myslel jsem, že vám ukázku
z toho, co budete moci dělat

1068
00:46:56,770 --> 00:46:57,950
po užití CS50.

1069
00:46:57,950 --> 00:47:02,620
Nech mě jít do cs.harvard.edu / rob,
naší vlastní Roba Bowdenovo domovskou stránku.

1070
00:47:02,620 --> 00:47:06,080
Udělal to pro nás.

1071
00:47:06,080 --> 00:47:07,490
Takže budete brzy moci udělat.

1072
00:47:07,490 --> 00:47:10,660
A také to, co jste slyšeli
dnes ráno -

1073
00:47:10,660 --> 00:47:12,480
to, co jsi slyšel dnes ráno -

1074
00:47:12,480 --> 00:47:13,780
>> [HAMSTER DANCE MUSIC]

1075
00:47:13,780 --> 00:47:15,702
>> - Budeš mít možnost, aby se to.

1076
00:47:15,702 --> 00:47:16,790
To nás čeká ve středu.

1077
00:47:16,790 --> 00:47:17,791
Uvidíme se potom.

1078
00:47:17,791 --> 00:47:22,950
>> [HAMSTER DANCE MUSIC]

1079
00:47:22,950 --> 00:47:24,300
DAVID Malan: Na další CS50 -

1080
00:47:24,300 --> 00:47:31,670