1
00:00:00,000 --> 00:00:03,423
>> [Přehrávání hudby]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI PENG: Vítejte na týden 6 oddílu.

4
00:00:08,210 --> 00:00:11,620
Odklonili jsme z našeho standardu
část doba úterý

5
00:00:11,620 --> 00:00:14,130
odpoledne na této krásné nedělní ráno.

6
00:00:14,130 --> 00:00:17,330
Děkuji vám, že pro každého
připojil se mi dnes, ale vážně,

7
00:00:17,330 --> 00:00:18,170
potlesk.

8
00:00:18,170 --> 00:00:20,600
>> To je dost velký úsilí.

9
00:00:20,600 --> 00:00:23,600
Málem jsem nedostala ani
právě včas, ale to bylo v pořádku.

10
00:00:23,600 --> 00:00:27,520
Takže vím, že každý z vás
právě udělali to kvíz.

11
00:00:27,520 --> 00:00:30,370
Za prvé, vítejte
odvrácenou stranou toho.

12
00:00:30,370 --> 00:00:32,917
>> Za druhé, budeme o tom mluvit.

13
00:00:32,917 --> 00:00:34,000
Promluvíme si o kvízu.

14
00:00:34,000 --> 00:00:35,700
Promluvíme si o tom, jak
děláte ve třídě.

15
00:00:35,700 --> 00:00:36,550
Budeš v pořádku.

16
00:00:36,550 --> 00:00:39,080
Mám své kvízy pro
jste na konci zde,

17
00:00:39,080 --> 00:00:42,120
Takže pokud si kluci chtějí, aby se
Podívejte se na to, úplně v pohodě.

18
00:00:42,120 --> 00:00:46,590
>> Tak rychle, než začneme se
agenda pro dnešek je následující.

19
00:00:46,590 --> 00:00:48,430
Jak můžete vidět, že jsme
v podstatě rychlé palby

20
00:00:48,430 --> 00:00:52,120
přes spoustu datových struktur
opravdu, opravdu, opravdu rychle.

21
00:00:52,120 --> 00:00:54,380
Tak jako takový, to nebude
Super interaktivní dnes.

22
00:00:54,380 --> 00:00:59,620
Bude to jen mě trochu křik
věci, které vás, a když jsem zmást,

23
00:00:59,620 --> 00:01:02,680
pokud jdu moc rychle, dejte mi vědět.

24
00:01:02,680 --> 00:01:05,200
Jsou to prostě různé údaje
struktury, a jako součást

25
00:01:05,200 --> 00:01:07,070
vaší pset na to
nadcházející týden, budete

26
00:01:07,070 --> 00:01:10,340
vyzváni k provedení jedné z nich,
možná dvě z them-- dvou z nich

27
00:01:10,340 --> 00:01:12,319
v pset.

28
00:01:12,319 --> 00:01:14,610
OK, tak jsem jen tak
začít s některými oznámení.

29
00:01:14,610 --> 00:01:19,070
Půjdeme přes komíny a další v front
hloubka, než to, co jsme dělali před kvíz.

30
00:01:19,070 --> 00:01:20,990
Půjdeme přes spojené
Seznam znovu, ještě jednou,

31
00:01:20,990 --> 00:01:23,899
více do hloubky, než to, co
jsme měli předtím kvízu.

32
00:01:23,899 --> 00:01:26,440
A pak se budeme bavit o hash
stoly, stromy a snaží se, které

33
00:01:26,440 --> 00:01:28,890
jsou všechny pěkně nezbytné pro pset.

34
00:01:28,890 --> 00:01:32,925
A pak půjdeme přes některé
užitečné tipy pro pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, takže kvíz 0.

36
00:01:37,360 --> 00:01:41,090
Průměrná byl 58%.

37
00:01:41,090 --> 00:01:45,370
To byla velmi nízká, a tak vy všichni
dělal velmi, velmi dobře v souladu

38
00:01:45,370 --> 00:01:46,510
s tím.

39
00:01:46,510 --> 00:01:49,970
>> Docela hodně, pravidlem je, pokud jste
v rámci standardní odchylkou od průměrné hodnoty

40
00:01:49,970 --> 00:01:52,990
zejména proto, že jsme v méně
pohodlný úsek, ty jsi úplně v pohodě.

41
00:01:52,990 --> 00:01:54,120
Jste na správné cestě.

42
00:01:54,120 --> 00:01:55,190
Život je krásný.

43
00:01:55,190 --> 00:01:58,952
>> Vím, že je to děsivé si myslet, že
Dostal jsem se jako 40% na tento kvíz.

44
00:01:58,952 --> 00:02:00,160
Jdu k nezdaru této třídy.

45
00:02:00,160 --> 00:02:02,243
Slibuji vám, že nejste
bude selhání třídu.

46
00:02:02,243 --> 00:02:03,680
Jsi úplně v pohodě.

47
00:02:03,680 --> 00:02:06,850
>> Pro ty z vás, kteří dostali více než
střední, impozantní, působivý,

48
00:02:06,850 --> 00:02:08,780
jako, vážně dobře.

49
00:02:08,780 --> 00:02:09,689
Mám je s sebou.

50
00:02:09,689 --> 00:02:11,730
Neváhejte a pojďte si je
na konci sekce.

51
00:02:11,730 --> 00:02:14,520
Dejte mi vědět, pokud máte nějaké
problémy, otázky s nimi.

52
00:02:14,520 --> 00:02:17,204
Sečteme-li vaše skóre
špatně, dejte nám vědět.

53
00:02:17,204 --> 00:02:21,240
>> OK, takže pset5, to je ve skutečnosti
divný týden Yale v tom smyslu,

54
00:02:21,240 --> 00:02:24,240
že naše pset je kvůli
Ve středu v poledne, včetně

55
00:02:24,240 --> 00:02:27,317
pozdní den, takže je to vlastně
teoreticky kvůli úterý v poledne.

56
00:02:27,317 --> 00:02:29,150
Asi nikdo skončil
v úterý v poledne.

57
00:02:29,150 --> 00:02:30,830
To je naprosto v pořádku.

58
00:02:30,830 --> 00:02:33,700
Budeme mít úřední hodiny
Dnes večer stejně jako v pondělí večer.

59
00:02:33,700 --> 00:02:36,810
A to vše sekcích tento týden
ve skutečnosti být otočen do dílen,

60
00:02:36,810 --> 00:02:38,800
tak neváhejte pop
jakákoli část, kterou chcete,

61
00:02:38,800 --> 00:02:42,810
a oni budou trochu mini-pset
workshopy o pomoc na to.

62
00:02:42,810 --> 00:02:45,620
Tak jako takový, to je jediná sekce
kam máme výukový materiál.

63
00:02:45,620 --> 00:02:49,220
Všechny ostatní části budou zaměřovat
výhradně na pomoc pro pset.

64
00:02:49,220 --> 00:02:50,146
To jo?

65
00:02:50,146 --> 00:02:52,000
>> Diváků: Kde jsou úřední hodiny?

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG: Úřední hodiny
tonight-- oh, dobrá otázka.

67
00:02:56,120 --> 00:03:00,580
Myslím si, že úřední hodiny dnes večer
jsou v Teal nebo na Commons.

68
00:03:00,580 --> 00:03:02,984
Pokud zaškrtnete on-line CS50
a jdete do úředních hodinách,

69
00:03:02,984 --> 00:03:05,650
by měl být plán, který
vám řekne, kde jsou všechny z nich jsou.

70
00:03:05,650 --> 00:03:07,954
>> Vím, že buď dnes večer
nebo zítra je modrozelený,

71
00:03:07,954 --> 00:03:10,120
a myslím, že můžeme mít
commons pro druhé v noci.

72
00:03:10,120 --> 00:03:11,020
Nejsem si jist.

73
00:03:11,020 --> 00:03:11,700
Dobrá otázka.

74
00:03:11,700 --> 00:03:14,430
Podívejte se na CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, nějaké dotazy týkající se
harmonogram pro další jako tři dny?

76
00:03:18,780 --> 00:03:21,690
Slibuji, že se vám bude líbit David
řekl, to je vrchol kopce.

77
00:03:21,690 --> 00:03:23,050
Vy jste skoro tam.

78
00:03:23,050 --> 00:03:24,644
Jen tři dny.

79
00:03:24,644 --> 00:03:26,310
Se tam dostat, a pak budeme všichni sestoupí.

80
00:03:26,310 --> 00:03:28,114
Budeme mít pěkný CS-volné přestávku.

81
00:03:28,114 --> 00:03:28,780
Vítej zpět.

82
00:03:28,780 --> 00:03:30,779
Budeme ponořit do webu
programování a vývoj,

83
00:03:30,779 --> 00:03:35,150
věci, které jsou velmi zábavné srovnání
na některé z dalších psets.

84
00:03:35,150 --> 00:03:37,974
A bude to chill a
budeme mít spoustu legrace.

85
00:03:37,974 --> 00:03:38,890
Budeme mít více cukroví.

86
00:03:38,890 --> 00:03:39,730
Omlouváme se za sladkosti.

87
00:03:39,730 --> 00:03:40,945
Zapomněl jsem cukroví.

88
00:03:40,945 --> 00:03:43,310
Bylo to drsné ráno.

89
00:03:43,310 --> 00:03:46,340
Takže vy jste skoro tam,
a já jsem opravdu pyšný z vás.

90
00:03:46,340 --> 00:03:49,570
>> OK, tak komíny.

91
00:03:49,570 --> 00:03:53,331
Kdo miluje na otázku o Jackovi
a jeho oblečení na kvíz?

92
00:03:53,331 --> 00:03:53,830
Nikdo?

93
00:03:53,830 --> 00:03:56,500
OK, to je v pořádku.

94
00:03:56,500 --> 00:04:00,200
>> Takže v podstatě, jak můžete
obrázek Jacku, tenhle chlapík tady,

95
00:04:00,200 --> 00:04:03,350
miluje vzít oblečení
z vrcholu zásobníku,

96
00:04:03,350 --> 00:04:05,750
a on říká zpět na
zásobníku poté, co udělal.

97
00:04:05,750 --> 00:04:07,600
Takže tímto způsobem, nikdy
se zdá být stále

98
00:04:07,600 --> 00:04:10,090
do spodní části
zásobník v jeho oblečení.

99
00:04:10,090 --> 00:04:12,600
Takže tento druh popisuje
základní struktura dat

100
00:04:12,600 --> 00:04:16,610
o tom, jak je implementována zásobník.

101
00:04:16,610 --> 00:04:20,060
>> V podstatě, myslet na
stack jako každý stoh objektů

102
00:04:20,060 --> 00:04:24,900
kam dát věci na vrchol, a
pak vyskočí ven z vrcholu.

103
00:04:24,900 --> 00:04:28,600
Takže LIFO je zkratka máme rádi
na use-- poslední dovnitř, první ven.

104
00:04:28,600 --> 00:04:32,480
A tak poslední se do horní části
stack je první, který vyjde.

105
00:04:32,480 --> 00:04:34,260
A tak se dva termíny
chceme přiřadit

106
00:04:34,260 --> 00:04:36,190
S tím se nazývají tlak a pop.

107
00:04:36,190 --> 00:04:39,790
Když budete tlačit něco Na
stack, a ty to pop zpět nahoru.

108
00:04:39,790 --> 00:04:43,422
>> A tak myslím, že to je tak trochu
abstraktní pojem pro ty z vás,

109
00:04:43,422 --> 00:04:45,630
kteří chtějí vidět jako
skutečném provádění tohoto

110
00:04:45,630 --> 00:04:46,740
v reálném světě.

111
00:04:46,740 --> 00:04:50,170
Jak mnozí z vás psali esej
Možná jako hodiny, než to bylo způsobeno,

112
00:04:50,170 --> 00:04:54,510
a vy omylem smazané obrovský
kus z toho, jako náhodou?

113
00:04:54,510 --> 00:04:58,560
A co potom kontrola dělat
používáme, aby ji zpět?

114
00:04:58,560 --> 00:05:00,030
Řízení-Z, jo?

115
00:05:00,030 --> 00:05:03,640
Control-Z, takže množství časů
že Control-Z mi zachránil život,

116
00:05:03,640 --> 00:05:08,820
mi zachránil zadek, pokaždé
která je prováděna prostřednictvím zásobníku.

117
00:05:08,820 --> 00:05:13,020
>> V podstatě všechny informace
že je na vašem dokumentu aplikace Word,

118
00:05:13,020 --> 00:05:15,080
dostane tlačil a vyskočila na přání.

119
00:05:15,080 --> 00:05:19,460
A tak se v podstatě vždy, když vás
vymazat vše, co si jen pop zpátky nahoru.

120
00:05:19,460 --> 00:05:22,820
A pak, pokud ji budete potřebovat znovu zapnete, vás
zatlačte ji, což je to, co Control-C dělá.

121
00:05:22,820 --> 00:05:26,770
A tak skutečné funkce svět
o tom, jak jednoduché datové struktury

122
00:05:26,770 --> 00:05:28,690
mohou pomoci s vaší každodenní život.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Takže struct je cesta, která
jsme vlastně vytvořit zásobník.

125
00:05:40,150 --> 00:05:44,720
My typ definovat struct, a poté
říkáme, že zásobník na dně.

126
00:05:44,720 --> 00:05:47,440
A v rámci stohu,
máme dva parametry

127
00:05:47,440 --> 00:05:51,580
že může být v podstatě manipulovat,
takže máme char hvězdy řetězců kapacitu.

128
00:05:51,580 --> 00:05:55,150
>> Vše, co je dělá
je vytvoření pole

129
00:05:55,150 --> 00:05:58,835
že můžeme ukládat, co chcete
které můžeme určit jeho kapacitu.

130
00:05:58,835 --> 00:06:01,990
Kapacita je jen maximální množství
položky můžeme dát do tohoto pole.

131
00:06:01,990 --> 00:06:05,660
velikost int je čítač, který udržuje
Trať o tom, jak mnoha položek jsou v současné době

132
00:06:05,660 --> 00:06:07,850
ve stohu.

133
00:06:07,850 --> 00:06:11,860
Takže pak můžeme sledovat, A,
oba, jak velký skutečné stack je,

134
00:06:11,860 --> 00:06:14,850
a, B, kolik z tohoto stohu
jsme naplnili protože nechceme

135
00:06:14,850 --> 00:06:18,800
přetečení nad tím, co naše kapacita je.

136
00:06:18,800 --> 00:06:24,340
>> Tak například, tento krásný
Otázka byla na kvíz.

137
00:06:24,340 --> 00:06:28,160
V podstatě, jak máme tlačit
na horní části zásobníku.

138
00:06:28,160 --> 00:06:28,830
Docela jednoduché.

139
00:06:28,830 --> 00:06:30,621
Když se podíváte na to,
projdeme to.

140
00:06:30,621 --> 00:06:32,640
Pokud [neslyšitelných] size--
pamatujte, kdykoli budete

141
00:06:32,640 --> 00:06:35,300
chtějí přistupovat k jakýmkoli
parametr v struct,

142
00:06:35,300 --> 00:06:40,320
děláte název struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> V tomto případě, s je
jméno naší zásobníku.

144
00:06:42,720 --> 00:06:46,230
Chceme, aby přístup k velikosti
z toho, takže děláme s.size.

145
00:06:46,230 --> 00:06:50,280
Tak, pokud je velikost není
rovnající se kapacity nebo tak dlouho,

146
00:06:50,280 --> 00:06:52,940
jak je to méně než kapacita,
buď bude pracovat.

147
00:06:52,940 --> 00:06:57,180
>> Chcete-li získat přístup dovnitř
vašeho stacku, tak s.strings,

148
00:06:57,180 --> 00:07:00,790
a budete dal, že nové číslo
které chcete vložit do tam.

149
00:07:00,790 --> 00:07:05,030
Řekněme, že budeme chtít
vložit int n do zásobníku,

150
00:07:05,030 --> 00:07:08,905
bychom mohli udělat s.strings,
držáky, s.size rovná n.

151
00:07:08,905 --> 00:07:11,030
Vzhledem k tomu, velikost je místo, kde jsme
V současné době je v balíčku

152
00:07:11,030 --> 00:07:14,590
pokud budeme tlačit
to dál, jen jsme přístup

153
00:07:14,590 --> 00:07:17,370
všude tam, kde je velikost, tím
proud plnost zásobníku,

154
00:07:17,370 --> 00:07:21,729
a přesuneme int n na něj.

155
00:07:21,729 --> 00:07:24,770
A pak chceme, aby se ujistil, že
jsme také zvyšování velikosti n,

156
00:07:24,770 --> 00:07:27,436
takže můžeme sledovat máme
přidal další věc, do stohu.

157
00:07:27,436 --> 00:07:29,660
Nyní máme větší velikost.

158
00:07:29,660 --> 00:07:33,196
Znamená to tady smysl
všichni, jak logicky to funguje?

159
00:07:33,196 --> 00:07:34,160
Bylo to trochu rychle.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
Diváků: Můžeš jít přes
se s.stringss.strings [s.size] znovu?

162
00:07:42,160 --> 00:07:45,808
ANDI PENG: Jasně, takže to, co dělá
s.size v současné době dát nám?

163
00:07:45,808 --> 00:07:47,440
Diváků: Je to aktuální velikost.

164
00:07:47,440 --> 00:07:50,890
ANDI PENG: Přesně, takže
Současný index, že naše velikost je,

165
00:07:50,890 --> 00:07:57,780
a tak chceme, aby se nové číslo
že chceme vložit do s.size.

166
00:07:57,780 --> 00:07:58,760
Dává to smysl?

167
00:07:58,760 --> 00:08:01,110
Vzhledem k tomu, s.strings, vše, co
je je název pole.

168
00:08:01,110 --> 00:08:03,510
Vše, co to je, je přístupem do
array v našem struct,

169
00:08:03,510 --> 00:08:06,030
a tak pokud chceme
místo n do tohoto indexu,

170
00:08:06,030 --> 00:08:09,651
můžeme jen přistupovat
pomocí konzoly s.size.

171
00:08:09,651 --> 00:08:10,150
Bezva.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Dobře, pop, pseudokód jsem to
pro vás, ale podobným konceptem.

174
00:08:18,916 --> 00:08:19,790
Dává to smysl?

175
00:08:19,790 --> 00:08:22,310
Pokud je velikost je větší
než nula, pak se

176
00:08:22,310 --> 00:08:25,350
víte, že chcete, aby se něco
, protože v případě, že velikost není

177
00:08:25,350 --> 00:08:27,620
větší než nula, pak se
nemá nic v zásobníku.

178
00:08:27,620 --> 00:08:29,840
>> Takže si jen chcete spustit
tento kód, jen to může

179
00:08:29,840 --> 00:08:32,320
pop pokud je něco pop.

180
00:08:32,320 --> 00:08:35,830
Takže, pokud je velikost je větší
než 0, jsme minus velikost.

181
00:08:35,830 --> 00:08:40,020
Decrement jsme velikost a pak se vrátit
co je uvnitř, protože

182
00:08:40,020 --> 00:08:42,710
praskání, chceme
Přístup, co je uloženo

183
00:08:42,710 --> 00:08:45,694
v indexu vrcholu zásobníku.

184
00:08:45,694 --> 00:08:46,610
Všechno, co smysl?

185
00:08:46,610 --> 00:08:49,693
Kdybych tě kluci psát na to,
by vy moci psát to?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
OK, vy můžete hrát si s ním.

188
00:08:53,570 --> 00:08:55,252
Žádné starosti, pokud nechcete dostat to.

189
00:08:55,252 --> 00:08:57,460
Nemáme čas na kód
it out dnes, protože máme

190
00:08:57,460 --> 00:08:59,959
mám hodně těchto struktur
projít, ale v zásadě

191
00:08:59,959 --> 00:09:02,214
pseudokód, velmi, velmi podobné, aby se zasadila.

192
00:09:02,214 --> 00:09:03,380
Stačí sledovat spolu logiky.

193
00:09:03,380 --> 00:09:06,092
Ujistěte se, že máte přístup všechny
vlastnosti vašeho struct správně.

194
00:09:06,092 --> 00:09:06,574
To jo?

195
00:09:06,574 --> 00:09:09,282
>> Diváků: budou tyto snímky a
Celá tahle věc být až dnes ish?

196
00:09:09,282 --> 00:09:11,586
ANDI PENG: Vždy, jo.

197
00:09:11,586 --> 00:09:13,710
Budu se snažit dát
toto nahoru jako hodinu poté.

198
00:09:13,710 --> 00:09:16,626
Budu email Davida, se bude snažit David
dal ji jako hodinu po této.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> OK, takže pak jsme se přestěhovat do ta druhá
půvabný datová struktura volal fronty.

201
00:09:25,470 --> 00:09:30,140
Jak vy můžete vidět zde, je
fronta, pro Brity mezi námi,

202
00:09:30,140 --> 00:09:32,010
vše, co je, je řada.

203
00:09:32,010 --> 00:09:34,680
Takže na rozdíl od toho, co
si myslíte, že zásobník je,

204
00:09:34,680 --> 00:09:37,750
fronta je přesně to, co
logicky si myslíte, že je.

205
00:09:37,750 --> 00:09:41,914
Je držen pravidel FIFO,
což je první dovnitř, první ven.

206
00:09:41,914 --> 00:09:43,705
Pokud jste první
jednou v řadě, jste

207
00:09:43,705 --> 00:09:46,230
první, který
vychází z řady.

208
00:09:46,230 --> 00:09:49,680
>> Takže to, co jsme chtěli volat toto
je dequeueing a enqueueing.

209
00:09:49,680 --> 00:09:52,380
Chceme-li přidat něco
k naší frontě, my Zařadí.

210
00:09:52,380 --> 00:09:55,690
Pokud chceme, aby dequeue, nebo se
něco pryč, my dequeue.

211
00:09:55,690 --> 00:10:03,350
>> Takže stejný pocit, že jsme trochu
vytvoření pevné velikosti prvků, které jsme

212
00:10:03,350 --> 00:10:06,500
je možné uložit jisté
věci, ale můžeme také

213
00:10:06,500 --> 00:10:10,100
změnit místo, kde jsme umístěním
Parametry uvnitř nich

214
00:10:10,100 --> 00:10:13,140
založené na tom, jaký typ
funkčnost chceme.

215
00:10:13,140 --> 00:10:16,700
Takže komíny, chtěli jsme poslední
jedním, N, že je první ven.

216
00:10:16,700 --> 00:10:19,800
Fronta je chceme první věc,
V být první věc ven.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Takže struct typu
definovat, jak můžete vidět,

219
00:10:26,710 --> 00:10:29,470
je to trochu jinak
z toho, co bylo stack

220
00:10:29,470 --> 00:10:33,120
protože nejen že se musíme držet
trať, kde v současné době je velikost,

221
00:10:33,120 --> 00:10:37,420
také chceme sledovat hlavy
stejně jako, kde jsme v současné době jsou.

222
00:10:37,420 --> 00:10:39,580
Takže si myslím, že je jednodušší
pokud kreslím to.

223
00:10:39,580 --> 00:10:53,270
Takže pojďme si představit, že máme frontu,
takže řekněme, že hlava je tady.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
V čele linky, pojďme
jen říct, že je to v současné době,

226
00:10:58,310 --> 00:11:01,809
a chceme vložit
něco, co se do fronty.

227
00:11:01,809 --> 00:11:04,350
Chystám se zavolat velikosti v podstatě
je totéž jako ocas,

228
00:11:04,350 --> 00:11:06,314
konec všude tam, kde je vaše fronta.

229
00:11:06,314 --> 00:11:07,730
Řekněme, že velikost je právě zde.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Tak jak se dá reálně
vložit něco do fronty?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
Co index chceme umístit
kam chceme vložit do.

234
00:11:24,130 --> 00:11:29,320
Pokud je to na začátku svého
fronty a to je její konec

235
00:11:29,320 --> 00:11:31,860
nebo velikost tom, kde my
chcete přidat další objekt?

236
00:11:31,860 --> 00:11:32,920
>> Diváků: [Neslyšitelné]

237
00:11:32,920 --> 00:11:35,920
ANDI PENG: Přesně tak, chcete přidat
to v závislosti na jste to napsal.

238
00:11:35,920 --> 00:11:37,840
Buď je to prázdné, nebo že je prázdná.

239
00:11:37,840 --> 00:11:42,630
Takže chcete, aby jej přidat pravděpodobně
tady, protože v případě, že velikost je--

240
00:11:42,630 --> 00:11:50,540
pokud jsou všechny plné, chcete
přidat tady, ne?

241
00:11:50,540 --> 00:11:57,150
>> A tak to je, když velmi, velmi
jednoduché, ne zcela vždy správné

242
00:11:57,150 --> 00:12:00,690
proto, že hlavní rozdíl
mezi fronty a zásobníku

243
00:12:00,690 --> 00:12:04,350
je to, že se fronta může
vlastně být vykonáván

244
00:12:04,350 --> 00:12:06,980
tak, že změny hlavové
V závislosti na tom, kde chcete

245
00:12:06,980 --> 00:12:08,650
začátek vaší povel ke startu.

246
00:12:08,650 --> 00:12:11,900
A jako výsledek, vaše ocas
je také změní.

247
00:12:11,900 --> 00:12:14,770
A tak se podívat na
Tento kód právě teď.

248
00:12:14,770 --> 00:12:18,620
Jak vy jste byli požádáni, aby
vypsat na kvíz, Enqueue.

249
00:12:18,620 --> 00:12:22,580
Možná, že budeme hovořit přes proč
odpověď byla, co to bylo.

250
00:12:22,580 --> 00:12:26,790
>> Nemohl jsem úplně fit tento řádek na jednom,
ale v podstatě tento kus kódu

251
00:12:26,790 --> 00:12:29,030
by měl být na jednom řádku.

252
00:12:29,030 --> 00:12:30,140
Strávit jako 30 sekund.

253
00:12:30,140 --> 00:12:33,000
Podívejte se, a uvidíte, proč
to je tak, že to je.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Velmi, velmi podobný struct, velmi, velmi
podobnou strukturou jako při předchozí

256
00:12:55,420 --> 00:12:58,090
stack s výjimkou snad
jeden řádek kódu.

257
00:12:58,090 --> 00:13:01,190
A že jeden řádek kódu
určuje funkce.

258
00:13:01,190 --> 00:13:03,900
A je to opravdu odlišuje
fronty z komína.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Každý, kdo chtějí, aby se stab
vysvětlit, proč nemáš

261
00:13:22,010 --> 00:13:24,980
dostal tuto komplikovanou věc tady?

262
00:13:24,980 --> 00:13:27,845
Vidíme návrat našeho
báječný kamarád modul.

263
00:13:27,845 --> 00:13:31,020
Jak vy brzy přijde
uznat v programování,

264
00:13:31,020 --> 00:13:34,910
téměř kdykoliv budete potřebovat něco
zabalit kolem cokoliv,

265
00:13:34,910 --> 00:13:36,850
modul bude způsob, jak to udělat.

266
00:13:36,850 --> 00:13:40,510
Tak s vědomím, že někdo chce
aby se pokusili vysvětlit tento řádek kódu?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Jo, jsou všechny odpovědi
přijatí a vítáni.

269
00:13:47,507 --> 00:13:48,840
Diváků: Mluvíš se mnou?

270
00:13:48,840 --> 00:13:49,506
ANDI PENG: Jo.

271
00:13:49,506 --> 00:13:56,200
Publikum: Oh, ne líto.

272
00:13:56,200 --> 00:14:00,250
ANDI PENG: OK, tak se pojďme
projít tímto kódem.

273
00:14:00,250 --> 00:14:03,642
Takže, když se snažíte
přidat něco na frontě,

274
00:14:03,642 --> 00:14:08,510
v krásném případě, že hlava se stane
být tady, je to pro nás velmi snadné

275
00:14:08,510 --> 00:14:10,960
prostě jít až do konce
vložit něco, ne?

276
00:14:10,960 --> 00:14:14,690
Ale celý bod na frontě
že hlava může skutečně dynamicky

277
00:14:14,690 --> 00:14:17,280
mění v závislosti na tom, kde jsme
Chcete začátku naší q být,

278
00:14:17,280 --> 00:14:19,880
a jako takový, ocasu
je také změní.

279
00:14:19,880 --> 00:14:31,100
>> A tak si představit, že to není
fronty, ale spíše je to fronty.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Řekněme, že hlava je tady.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Řekněme, že naše fronta vypadala takhle.

284
00:14:56,980 --> 00:15:00,190
Pokud bychom chtěli posunout kde
na začátku linky je,

285
00:15:00,190 --> 00:15:03,400
řekněme, že jsme se posunul hlavou
Tímto způsobem a tady velikosti.

286
00:15:03,400 --> 00:15:07,100
>> Nyní chceme něco přidat
Tato fronta, ale jak vy můžete vidět,

287
00:15:07,100 --> 00:15:11,150
to není tak jednoduché, jak jen
přidat to, co je za velikostí

288
00:15:11,150 --> 00:15:13,630
protože pak dojdou
meze naší aktuální pole.

289
00:15:13,630 --> 00:15:16,190
Kam chceme opravdu přidat je zde.

290
00:15:16,190 --> 00:15:18,610
To je krása fronty
je to, že pro nás, vizuálně

291
00:15:18,610 --> 00:15:22,380
vypadá jako linka jde takhle,
ale pokud jsou uloženy v datové struktuře,

292
00:15:22,380 --> 00:15:29,370
dávají to jako jako cyklus.

293
00:15:29,370 --> 00:15:32,360
Je to druh obaluje
na přední straně stejný způsobem

294
00:15:32,360 --> 00:15:34,780
že vedení může také zábal
kolem závisí na všude tam, kde vás

295
00:15:34,780 --> 00:15:36,279
chtějí začátku řádku být.

296
00:15:36,279 --> 00:15:38,630
A tak pokud budeme trvat
podívejte se sem dolů, pojďme

297
00:15:38,630 --> 00:15:40,880
že jsme chtěli vytvořit
Funkce tzv zařazení do fronty.

298
00:15:40,880 --> 00:15:43,980
Chtěli jsme přidat int n do tohoto q.

299
00:15:43,980 --> 00:15:49,250
Pokud q.size q-- budeme říkat, že naše data
structure-- když náš queue.size není

300
00:15:49,250 --> 00:15:52,520
se rovná kapacit nebo jestliže
je to méně než kapacita,

301
00:15:52,520 --> 00:15:55,120
q.strings je pole v našem q.

302
00:15:55,120 --> 00:15:58,380
Budeme nastavit
rovnající se q.heads,

303
00:15:58,380 --> 00:16:02,730
který je tady, a navíc q.size
modul kapacitou, který

304
00:16:02,730 --> 00:16:04,290
zábal nás zpátky tady.

305
00:16:04,290 --> 00:16:08,040
>> Takže v tomto příkladu, index
hlavy je 1, že jo?

306
00:16:08,040 --> 00:16:11,480
Index velikosti je 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Takže můžeme udělat 1 plus 4 modul
naší kapacity, která je 5.

308
00:16:19,500 --> 00:16:20,920
Co, že nám dá?

309
00:16:20,920 --> 00:16:23,270
Co je index, který
vychází z toho?

310
00:16:23,270 --> 00:16:24,080
>> Diváků: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI PENG: 0, což
se stane být tady,

312
00:16:27,870 --> 00:16:30,640
a tak chceme být schopni
vložit do právě zde.

313
00:16:30,640 --> 00:16:34,730
A tak tato rovnice zde druh
z právě pracuje s čísly

314
00:16:34,730 --> 00:16:36,750
V závislosti na tom, kde vaše
hlava a vaše velikost jsou.

315
00:16:36,750 --> 00:16:38,541
Pokud víte, co ty,
věci jsou, víte,

316
00:16:38,541 --> 00:16:43,170
přesně tam, kde chcete vložit
co je po vašem fronty.

317
00:16:43,170 --> 00:16:44,640
Znamená to, že smysl pro všechny?

318
00:16:44,640 --> 00:16:48,560
>> Vím, že jakýsi mozku
teaser zejména proto, že

319
00:16:48,560 --> 00:16:50,512
přišel v důsledku vašeho kvíz.

320
00:16:50,512 --> 00:16:52,220
Ale doufejme, že všichni
Nyní můžete pochopit,

321
00:16:52,220 --> 00:16:57,800
proč toto řešení, nebo to
Funkce je tak, že to je.

322
00:16:57,800 --> 00:16:59,840
Každý, kdo trochu nejasné na to?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
DOBŘE.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> A tak teď, pokud jste
chtěl dequeue, to

327
00:17:09,970 --> 00:17:15,240
je místo, kde by naše hlava se přesouvá
protože pokud bychom měli dequeue,

328
00:17:15,240 --> 00:17:17,030
nebereme z konce q.

329
00:17:17,030 --> 00:17:19,130
Chceme, aby se z hlavy, že jo?

330
00:17:19,130 --> 00:17:24,260
Takže v důsledku toho hlava se změní,
a to je důvod, proč, když se Zařadí,

331
00:17:24,260 --> 00:17:26,800
musíš sledovat
kde se vaše hlava a vaše velikost

332
00:17:26,800 --> 00:17:29,450
jsou, aby bylo možné vložit
do správné polohy.

333
00:17:29,450 --> 00:17:32,740
>> A tak když se dequeue,
Také jsem pseudokód to.

334
00:17:32,740 --> 00:17:35,480
Neváhejte a pokud chcete,
pokusit kódování to.

335
00:17:35,480 --> 00:17:36,980
Chcete přesunout hlavu, ne?

336
00:17:36,980 --> 00:17:39,320
Kdybych chtěl dequeue, I
by se posunout hlavu nad.

337
00:17:39,320 --> 00:17:40,800
To by být hlava.

338
00:17:40,800 --> 00:17:45,617
>> A náš současný velikost by
odčítání, protože již není

339
00:17:45,617 --> 00:17:46,950
mají čtyři prvky v poli.

340
00:17:46,950 --> 00:17:51,370
Máme jen tři, a pak chceme
vrátit, co byl uložen uvnitř

341
00:17:51,370 --> 00:17:56,260
hlavy, protože chceme, aby se tento
hodnota se tak velmi podobný zásobníku.

342
00:17:56,260 --> 00:17:58,010
Jen jste při
z jiného místa,

343
00:17:58,010 --> 00:18:01,770
a vy budete muset přiřadit svou ukazatel
na jiném místě jako výsledek.

344
00:18:01,770 --> 00:18:03,890
Logicky, každý následovat?

345
00:18:03,890 --> 00:18:05,690
Skvělý.

346
00:18:05,690 --> 00:18:10,156
>> OK, takže budeme mluvit trochu
více do hloubky asi spojových seznamech

347
00:18:10,156 --> 00:18:13,280
protože bude velmi, velmi cenná
pro vás v průběhu roku tento týden

348
00:18:13,280 --> 00:18:14,964
psets.

349
00:18:14,964 --> 00:18:17,130
Spojové seznamy, jak jste kluci
Pamatuji si, všechno, co jsou

350
00:18:17,130 --> 00:18:22,570
jsou uzly, které jsou uzly jisté
Hodnoty obou hodnotu a ukazatel

351
00:18:22,570 --> 00:18:26,290
, které jsou spojeny dohromady
těmito ukazateli.

352
00:18:26,290 --> 00:18:29,880
A tak se na to, jak struct
jsme se vytvořit uzel tady je, že jsme

353
00:18:29,880 --> 00:18:33,569
mají int n, což je cokoliv
hodnota v obchodě nebo řetězce n

354
00:18:33,569 --> 00:18:35,610
nebo co chcete
říkají, char hvězda n.

355
00:18:35,610 --> 00:18:41,482
Uzel struct hvězda, což je ukazatel
které chcete mít v každém uzlu,

356
00:18:41,482 --> 00:18:43,690
budete mít, že
Ukazatel bod k další.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Budete mít hlavu
propojeného seznamu, který je

359
00:18:50,040 --> 00:18:53,140
bude poukázat na zbytku
hodnoty tak dále a tak dále

360
00:18:53,140 --> 00:18:55,290
dokud se nakonec dostanete na konec.

361
00:18:55,290 --> 00:18:58,040
A to je jen poslední uzel
bude to mít ukazatel.

362
00:18:58,040 --> 00:18:59,952
Bude to poukázat na
null, a to je, když

363
00:18:59,952 --> 00:19:01,910
víte, že jste hit
konec vašeho seznamu Google

364
00:19:01,910 --> 00:19:04,076
je, když vaše poslední ukazatel
neukazuje na nic.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Tak jsme se chystáte jít trochu více do
hloubka ohledně toho, jak by člověk možná

367
00:19:10,990 --> 00:19:12,400
vyhledávat propojeného seznamu.

368
00:19:12,400 --> 00:19:15,460
Pamatujte si, jaké jsou některé z
nevýhody propojených seznamů

369
00:19:15,460 --> 00:19:19,340
verše pole o vyhledávání.

370
00:19:19,340 --> 00:19:22,565
Pole můžete binární vyhledávání, ale
proč nemůžete udělat, že v Google seznamu?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> Diváků: Vzhledem k tomu, že jsou všichni připojeni,
ale nemáte dost vědět, kde

373
00:19:30,320 --> 00:19:31,330
[NESLYŠITELNÝ].

374
00:19:31,330 --> 00:19:34,600
>> ANDI PENG: Jo, přesně tak si pamatujte:
že brilance pole

375
00:19:34,600 --> 00:19:37,190
byla skutečnost, že jsme měli
paměť s přímým přístupem, kde

376
00:19:37,190 --> 00:19:41,580
kdybych chtěl hodnotu z indexu
šest, mohl bych jen říct index šest,

377
00:19:41,580 --> 00:19:42,407
dej mi tuto hodnotu.

378
00:19:42,407 --> 00:19:45,240
A to proto, že pole jsou řazeny
v souvislém prostoru paměti

379
00:19:45,240 --> 00:19:48,020
na jednom místě, vzhledem k tomu,
druh spojových seznamů

380
00:19:48,020 --> 00:19:52,820
jsou náhodně střídají všude kolem,
a jediný způsob, jak můžete najít jeden

381
00:19:52,820 --> 00:19:56,890
je přes ukazatel, který vám řekne,
adresa, kde, že příští uzel je.

382
00:19:56,890 --> 00:20:00,290
>> A tak jako výsledek, jediný způsob, jak
prohledávat propojeném seznamu

383
00:20:00,290 --> 00:20:01,560
je lineární hledání.

384
00:20:01,560 --> 00:20:05,890
Protože já přesně nevím, kde
12. hodnota v Google seznamu je,

385
00:20:05,890 --> 00:20:08,780
Musím projít celistvost
tohoto propojeného seznamu jeden

386
00:20:08,780 --> 00:20:12,450
jeden z hlavy do prvního uzlu,
do druhého uzlu, na třetí uzlu,

387
00:20:12,450 --> 00:20:17,690
celou cestu dolů, až jsem se konečně dostanu
kde uzel Sháním je.

388
00:20:17,690 --> 00:20:22,110
A tak v tomto smyslu, hledání
v Google seznamu je vždy n.

389
00:20:22,110 --> 00:20:23,040
Je to vždycky n.

390
00:20:23,040 --> 00:20:25,690
Je to vždycky v lineárním čase.

391
00:20:25,690 --> 00:20:28,470
>> A tak se kód, ve kterém
realizujeme to, a to

392
00:20:28,470 --> 00:20:32,620
je trochu nový pro vás, protože jste
kluci se opravdu mluvili, nebo vůbec

393
00:20:32,620 --> 00:20:35,000
ukazatele vidět v tom, jak se
prohledávat ukazatelů,

394
00:20:35,000 --> 00:20:37,670
takže budeme procházet
tato velmi, velmi pomalu.

395
00:20:37,670 --> 00:20:40,200
Takže bool vyhledávání, vpravo,
pojďme si představit, chceme

396
00:20:40,200 --> 00:20:42,820
vytvořit funkci nazvanou
Hledání, který vrací true

397
00:20:42,820 --> 00:20:46,820
pokud jste našli hodnotě uvnitř spojené
vypsat, a vrací false jinak.

398
00:20:46,820 --> 00:20:50,030
Uzel hvězda seznam je
V současné době jen ukazatel

399
00:20:50,030 --> 00:20:52,960
na první položku ve vašem Google seznamu.

400
00:20:52,960 --> 00:20:56,700
int n je hodnota, kterou jste
hledání v tomto seznamu.

401
00:20:56,700 --> 00:20:58,770
>> Takže uzel hvězda ukazatel rovná seznam.

402
00:20:58,770 --> 00:21:00,970
To znamená, že jsme nastavení
a vytvoření ukazatele

403
00:21:00,970 --> 00:21:03,592
do tohoto prvního uzlu uvnitř seznamu.

404
00:21:03,592 --> 00:21:04,300
Každý, kdo se mnou?

405
00:21:04,300 --> 00:21:06,530
Takže pokud bychom měli jít
zpátky, musel bych

406
00:21:06,530 --> 00:21:13,850
inicializovat ukazatel, který odkazuje na
hlava, co tento seznam.

407
00:21:13,850 --> 00:21:18,600
>> A pak, jakmile se dostanete sem,
zatímco ukazatel nerovná null,

408
00:21:18,600 --> 00:21:22,160
tak, že je smyčka, ve které jsou
bude následně křížení

409
00:21:22,160 --> 00:21:25,940
zbytek našeho seznamu protože to, co
se stane, když ukazatel rovná null?

410
00:21:25,940 --> 00:21:27,550
Víme, že jsme have--

411
00:21:27,550 --> 00:21:28,450
>> Diváků: [Neslyšitelné]

412
00:21:28,450 --> 00:21:31,491
>> ANDI PENG: Přesně, takže víme, že
jsme došli na konec seznamu, je to tak?

413
00:21:31,491 --> 00:21:34,470
Vydáte-li se zpátky, každý uzel
musí směřovat do jiného uzlu

414
00:21:34,470 --> 00:21:36,550
a tak dále a tak dále
dokud nenarazíte nakonec

415
00:21:36,550 --> 00:21:41,589
ocas vašeho Google seznamu,
který má ukazatel, který právě

416
00:21:41,589 --> 00:21:43,130
neukazuje jinde než žádný.

417
00:21:43,130 --> 00:21:47,510
A tak jste v podstatě víte, že
váš seznam je zde stále nahoře

418
00:21:47,510 --> 00:21:50,900
dokud ukazatel není rovno
null, protože jakmile se rovná null,

419
00:21:50,900 --> 00:21:53,310
víte, že není více věcí.

420
00:21:53,310 --> 00:21:56,930
>> Tak, že je smyčka, ve které jsme
bude mít aktuální vyhledávání.

421
00:21:56,930 --> 00:22:01,690
A v případě, že pointer-- vidíš
že druh šipky tam funkce?

422
00:22:01,690 --> 00:22:06,930
Takže pokud ukazatel ukazuje na n, pokud
ukazatel v n rovná se rovná n,

423
00:22:06,930 --> 00:22:09,180
tak, že znamená, že pokud
ukazatel, že jste

424
00:22:09,180 --> 00:22:13,420
vyhledávání na konci každého
Uzel je vlastně rovná hodnotě

425
00:22:13,420 --> 00:22:15,990
hledáte, pak
se chcete vrátit hodnotu true.

426
00:22:15,990 --> 00:22:19,280
Takže v podstatě, pokud jste na uzlu, který
má hodnotu, kterou hledáte,

427
00:22:19,280 --> 00:22:23,550
víte, že jste byli
schopni úspěšně vyhledávat.

428
00:22:23,550 --> 00:22:27,150
>> V opačném případě, že chcete nastavit
ukazatel na další uzel.

429
00:22:27,150 --> 00:22:28,850
To je to, co tento řádek je zde dělá.

430
00:22:28,850 --> 00:22:31,750
Ukazatel se rovná ukazatel další.

431
00:22:31,750 --> 00:22:33,360
Všichni vidět, jak to funguje?

432
00:22:33,360 --> 00:22:36,580
>> A v podstatě budete jen
přejít celistvost seznamu,

433
00:22:36,580 --> 00:22:41,920
resetování ukazatel pokaždé, dokud
budete nakonec narazí na konec seznamu.

434
00:22:41,920 --> 00:22:45,030
A víte, že neexistují žádné
více uzlů prohledávat,

435
00:22:45,030 --> 00:22:47,999
a pak můžete return false
protože víte, že, oh, no,

436
00:22:47,999 --> 00:22:50,540
pokud jsem byl schopen vyhledávat
přes celé seznamu.

437
00:22:50,540 --> 00:22:54,530
Pokud by v tomto příkladu, kdybych chtěl
hledat na hodnotu 10,

438
00:22:54,530 --> 00:22:57,250
I a začít v čele, a
I hledání celou cestu dolů,

439
00:22:57,250 --> 00:23:00,550
a nakonec jsem se dostal k tomu, který
ukazatel, který poukazuje na hodnotu null,

440
00:23:00,550 --> 00:23:04,415
Vím, že, blbost, myslím, že 10 není v
Tento seznam proto, že jsem nemohl najít.

441
00:23:04,415 --> 00:23:06,520
A já jsem se na konci seznamu.

442
00:23:06,520 --> 00:23:11,040
A v takovém případě víte,
Chystám se vrátit false.

443
00:23:11,040 --> 00:23:12,900
>> Ať že máčet v pro trochu.

444
00:23:12,900 --> 00:23:17,350
To bude dost
důležité pro vaši pset.

445
00:23:17,350 --> 00:23:21,140
Logika je to velmi jednoduché, snad
syntakticky jen jejím provádění.

446
00:23:21,140 --> 00:23:23,365
Vy chcete, aby
Ujistěte se, že rozumíte.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Bezva.

449
00:23:27,650 --> 00:23:32,560
>> OK, tak jak bychom byli
vkládání uzlů, vpravo,

450
00:23:32,560 --> 00:23:35,380
do seznamu, protože pamatovat
jaké jsou to, co výhod

451
00:23:35,380 --> 00:23:39,230
mít propojeného seznamu oproti
pole, pokud jde o skladování?

452
00:23:39,230 --> 00:23:41,110
>> Diváků: Je to dynamický,
takže je to jednodušší, to--

453
00:23:41,110 --> 00:23:43,180
>> ANDI PENG: Přesně tak,
tak je to dynamický, který

454
00:23:43,180 --> 00:23:46,880
znamená, že se může rozšířit a zmenšit
V závislosti na potřebách uživatele.

455
00:23:46,880 --> 00:23:56,570
A tak, v tomto smyslu, nepotřebujeme
ztrácet zbytečně paměť, protože jsem

456
00:23:56,570 --> 00:24:00,850
když nevím, kolik hodnot Chci
skladovat, to nemá smysl pro mě

457
00:24:00,850 --> 00:24:04,310
vytvořit pole z následujících důvodů
když chci uložit 10 hodnot

458
00:24:04,310 --> 00:24:08,380
a já se vytvořit řadu 1000, to je
hodně nevyužité paměti, přiděleny.

459
00:24:08,380 --> 00:24:11,180
To je důvod, proč chceme použít propojený
seznam, aby bylo možné dynamicky

460
00:24:11,180 --> 00:24:13,860
změnit nebo zmenšit naši velikost.

461
00:24:13,860 --> 00:24:17,040
>> A tak to dělá vkládání
trochu složitější.

462
00:24:17,040 --> 00:24:20,810
Vzhledem k tomu, nemůžeme náhodně přístup k prvkům
tak, že bychom z pole.

463
00:24:20,810 --> 00:24:24,270
Pokud chci vložit prvek
do sedmé indexu

464
00:24:24,270 --> 00:24:26,930
Jen jsem si ji vložit
do sedmé indexu.

465
00:24:26,930 --> 00:24:30,020
V propojeném seznamu, to není
poměrně pracovat tak snadno,

466
00:24:30,020 --> 00:24:34,947
a tak pokud bychom chtěli vložit
ten tady v Google seznamu,

467
00:24:34,947 --> 00:24:36,280
vizuálně, je to velmi dobře vidět.

468
00:24:36,280 --> 00:24:39,363
Chceme jen, aby ho vložit přímo tam,
hned na začátku seznamu,

469
00:24:39,363 --> 00:24:40,840
hned po hlavě.

470
00:24:40,840 --> 00:24:44,579
>> Ale způsob, jakým musíme přeřadit
Ukazatele se trochu spletitý

471
00:24:44,579 --> 00:24:47,620
nebo, logicky, to dává smysl, ale
chcete, aby se ujistil, že to máte

472
00:24:47,620 --> 00:24:50,250
úplně dolů, protože
to poslední, co chcete,

473
00:24:50,250 --> 00:24:52,990
je přiřadit ukazovátka
tak, že tady děláme.

474
00:24:52,990 --> 00:24:58,170
Pokud vás dereference
ukazatel od hlavy až k 1,

475
00:24:58,170 --> 00:25:01,086
pak najednou The
zbytek vašeho Google seznamu

476
00:25:01,086 --> 00:25:04,680
je ztraceno, protože jste není vlastně
vytvořili dočasný cokoliv.

477
00:25:04,680 --> 00:25:06,220
To ukázal na 2.

478
00:25:06,220 --> 00:25:10,080
Pokud přiřazení ukazatel, pak se
zbytek vašeho seznamu je zcela ztracen.

479
00:25:10,080 --> 00:25:13,310
Takže vy chcete být
velmi, velmi opatrný zde

480
00:25:13,310 --> 00:25:17,010
nejprve přiřadit
ukazatel z jakéhokoli vás

481
00:25:17,010 --> 00:25:20,150
chcete vložit do kamkoli
chceš, a pak vás

482
00:25:20,150 --> 00:25:22,710
může dereference zbytek vašeho seznamu.

483
00:25:22,710 --> 00:25:25,250
>> Tak to platí pro kdekoli
snažíte vložit do.

484
00:25:25,250 --> 00:25:27,520
Chcete-li vložit u
hlava, chcete-li odpovědět na tu,

485
00:25:27,520 --> 00:25:29,455
pokud chcete vložit na
konec, no, nakonec jsem se

486
00:25:29,455 --> 00:25:30,910
Asi byste právě
nemají žádný ukazatel, ale vy

487
00:25:30,910 --> 00:25:33,830
chcete, aby se ujistil, že nemáte
ztratit zbytek seznamu.

488
00:25:33,830 --> 00:25:36,640
Vždycky chcete ujistit,
Váš nový uzel směřuje

489
00:25:36,640 --> 00:25:39,330
směrem k co
chcete vložit do,

490
00:25:39,330 --> 00:25:42,170
a pak můžete přidat zřetězení dál.

491
00:25:42,170 --> 00:25:43,330
Všichni jasné?

492
00:25:43,330 --> 00:25:45,427
>> To bude
jeden ze skutečných problémů.

493
00:25:45,427 --> 00:25:48,010
Jedním z nejvíce hlavních problémů
budete mít na svém pset

494
00:25:48,010 --> 00:25:51,340
je to, že budete snažit vytvořit
propojený seznam a vložit věci

495
00:25:51,340 --> 00:25:53,340
ale pak jen ztratit
zbytek svého Google seznamu.

496
00:25:53,340 --> 00:25:54,900
A ty budeš rád, já
Nevím, proč se to děje?

497
00:25:54,900 --> 00:25:58,040
A je to bolest projít
a hledat všechny vaše ukazatelů.

498
00:25:58,040 --> 00:26:02,100
>> A já vám zaručit, na tomto pset,
psaní a kreslení těchto uzlů out

499
00:26:02,100 --> 00:26:03,344
bude velmi, velmi užitečné.

500
00:26:03,344 --> 00:26:06,010
Takže si můžete zcela sledovat
kde všechny vaše ukazatele jsou,

501
00:26:06,010 --> 00:26:08,540
co se děje špatně,
kde se všechny vaše uzly jsou,

502
00:26:08,540 --> 00:26:12,660
to, co musíte udělat, aby přístup nebo
vložit nebo odstranit, nebo některý z nich.

503
00:26:12,660 --> 00:26:14,550
Všichni dobře s tím?

504
00:26:14,550 --> 00:26:15,050
Bezva.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Takže pokud jsme chtěli podívat na kód?

507
00:26:22,600 --> 00:26:24,470
Oh, já nevím, jestli my
můžete vidět the-- OK, tak

508
00:26:24,470 --> 00:26:27,940
V horní řadě je to je funkce
jmenoval vložka tam, kde chceme

509
00:26:27,940 --> 00:26:31,365
vložit int n do propojeného seznamu.

510
00:26:31,365 --> 00:26:32,740
Chystáme se projít to.

511
00:26:32,740 --> 00:26:34,770
Je to hodně kódu, spousta novou syntaxí.

512
00:26:34,770 --> 00:26:36,220
Budeme v pořádku.

513
00:26:36,220 --> 00:26:39,120
>> Tak se v horní části, pokud je to
chceme vytvořit něco

514
00:26:39,120 --> 00:26:42,380
co musíme udělat, zvláště pokud jste
chcete, aby to nemělo být uložen v zásobníku

515
00:26:42,380 --> 00:26:43,920
ale v haldě?

516
00:26:43,920 --> 00:26:45,460
Jdeme do malloc, že ​​jo?

517
00:26:45,460 --> 00:26:48,240
Takže budeme vytvořit ukazatel.

518
00:26:48,240 --> 00:26:52,074
Uzel, ukazatel, nové rovná
malloc velikost uzlu

519
00:26:52,074 --> 00:26:53,740
protože chceme, aby uzel, který bude vytvořen.

520
00:26:53,740 --> 00:26:56,720
Chceme, aby množství
paměť, která uzel zabírá

521
00:26:56,720 --> 00:26:59,300
mají být přiděleny pro
vytvoření nového uzlu.

522
00:26:59,300 --> 00:27:02,270
>> A pak budeme zkontrolovat,
uvidíme, jestli nová rovná se rovná null.

523
00:27:02,270 --> 00:27:03,370
Vzpomeňte si, co jsme si řekli?

524
00:27:03,370 --> 00:27:06,470
Ať už vás malloc,
Co musíte vždy udělat?

525
00:27:06,470 --> 00:27:09,490
Vždy musíte zkontrolovat,
zda to je null.

526
00:27:09,490 --> 00:27:13,620
>> Například, pokud váš operační
Systém byl úplně plný,

527
00:27:13,620 --> 00:27:17,060
pokud jste měli na ne více paměti
všechny a zkuste malloc,

528
00:27:17,060 --> 00:27:18,410
že se vrátí null pro vás.

529
00:27:18,410 --> 00:27:21,094
A tak pokud se pokusíte použít
když to bylo ukázal na null,

530
00:27:21,094 --> 00:27:23,260
vy nebudete schopni
na přístup k těmto informacím.

531
00:27:23,260 --> 00:27:27,010
A tak jako takový, chtěli jsme, aby se
jisti, že vždy, když jste mallocing,

532
00:27:27,010 --> 00:27:30,500
jste vždy zkontrolovat, zda
že paměť daný pro vás je null.

533
00:27:30,500 --> 00:27:33,670
A pokud tomu tak není, pak se můžeme přesunout
se zbytkem našeho kódu.

534
00:27:33,670 --> 00:27:36,140
>> Takže budeme
inicializovat nový uzel.

535
00:27:36,140 --> 00:27:39,050
Chystáme se udělat nový n se rovná n.

536
00:27:39,050 --> 00:27:42,390
A pak budeme dělat
nastavit nový ukazatel na nové

537
00:27:42,390 --> 00:27:46,900
na NULL, protože právě teď my ne
chtějí něco pro to, aby ukazoval na.

538
00:27:46,900 --> 00:27:48,755
Nemáme tušení, kde
to bude, aby vám,

539
00:27:48,755 --> 00:27:50,630
a pokud chceme
vložte jej v čele,

540
00:27:50,630 --> 00:27:53,820
pak můžeme přiřadit
ukazatel na hlavě.

541
00:27:53,820 --> 00:27:58,530
Má každý sledovat logiku
kde že se to děje?

542
00:27:58,530 --> 00:28:02,502
>> Vše, co děláte, je vytvoření nového
uzel, nastavení ukazatel na null,

543
00:28:02,502 --> 00:28:04,210
a pak přiřazení
to do hlavy, kdybychom

544
00:28:04,210 --> 00:28:06,320
víte, chceme vložit do čela.

545
00:28:06,320 --> 00:28:09,420
A pak hlava se chystá
ukazovat směrem k tomuto novému uzlu.

546
00:28:09,420 --> 00:28:11,060
Každý, kdo s tím OK?

547
00:28:11,060 --> 00:28:12,380
>> Takže je to dvoustupňový proces.

548
00:28:12,380 --> 00:28:14,760
Musíš Nejprve přiřaďte
co budete vytvářet.

549
00:28:14,760 --> 00:28:18,260
Nastavit že ukazatel
odkazovat, a pak vás

550
00:28:18,260 --> 00:28:21,400
může druh dereference
první ukazatel

551
00:28:21,400 --> 00:28:22,972
a přejděte na nový uzel.

552
00:28:22,972 --> 00:28:25,680
Všude tam, kde ji chcete vložit,
že logika bude platit.

553
00:28:25,680 --> 00:28:27,530
>> Je to něco jako přiřazení
dočasné proměnné.

554
00:28:27,530 --> 00:28:28,700
Pamatujte si, že máte
aby se ujistil, že vás

555
00:28:28,700 --> 00:28:30,346
neztrácejí přehled o pokud jste swapování.

556
00:28:30,346 --> 00:28:33,470
Chcete, aby se ujistil, že máte
dočasná proměnná, která druh udržuje

557
00:28:33,470 --> 00:28:35,620
sledovat, kde té věci
je uložena tak, že

558
00:28:35,620 --> 00:28:41,190
neztratili žádnou hodnotu v průběhu
jako se pohráváte s ním.

559
00:28:41,190 --> 00:28:42,710
>> OK, takže tady bude kód.

560
00:28:42,710 --> 00:28:45,020
Vy se podívat po bodu.

561
00:28:45,020 --> 00:28:48,060
Bude to tam.

562
00:28:48,060 --> 00:28:50,280
>> Takže si myslím, jak se
to se liší, pokud bychom chtěli

563
00:28:50,280 --> 00:28:52,300
vložit do středu nebo na konci?

564
00:28:52,300 --> 00:28:57,892
Má někdo má představu o tom, co je to
pseudokód jako logické reference

565
00:28:57,892 --> 00:29:00,350
že bychom trvat, pokud bychom chtěli
jej vložit do středu?

566
00:29:00,350 --> 00:29:03,391
Takže pokud bychom chtěli vložit u
hlava, vše, co udělat, je vytvořit nový uzel.

567
00:29:03,391 --> 00:29:06,311
Nastavili jsme ukazatel, který
Nový uzel se to bez ohledu na hlavě,

568
00:29:06,311 --> 00:29:08,310
a pak jsme se nastavit hlavu
do nového uzlu, že jo?

569
00:29:08,310 --> 00:29:11,560
Pokud bychom chtěli vložit do středu
seznamu, co by se musíme udělat?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> Diváků: To by ještě
být podobný proces

572
00:29:16,110 --> 00:29:19,114
jako se přiřazení ukazatele,
pak přiřadí tento ukazatel,

573
00:29:19,114 --> 00:29:20,530
ale museli bychom tam najít.

574
00:29:20,530 --> 00:29:23,560
>> ANDI PENG: Přesně tak, přesně
stejný proces kromě vás

575
00:29:23,560 --> 00:29:27,820
muset najít, kde přesně jste
chcete, aby nový ukazatel jít do,

576
00:29:27,820 --> 00:29:44,790
takže pokud chci vložit do
uprostřed spojeny list-- OK,

577
00:29:44,790 --> 00:29:46,370
řekněme, že je to naše provázaný seznam.

578
00:29:46,370 --> 00:29:49,500
Chceme-li jej vložit přímo tady,
budeme vytvořit nový uzel.

579
00:29:49,500 --> 00:29:50,520
Jedeme do malloc.

580
00:29:50,520 --> 00:29:52,220
Chystáme se vytvořit nový uzel.

581
00:29:52,220 --> 00:29:55,940
Budeme přiřadit
ukazatel tohoto uzlu zde.

582
00:29:55,940 --> 00:29:58,335
>> Avšak problémem, který se liší
od místa, kde je hlava

583
00:29:58,335 --> 00:30:00,490
je, že jsme přesně věděli,
kde je hlava.

584
00:30:00,490 --> 00:30:01,930
To bylo hned na počátku, že jo?

585
00:30:01,930 --> 00:30:04,870
Ale tady musíme sledovat
kde jsme vložením do.

586
00:30:04,870 --> 00:30:07,930
Jsme-li vložit naše
uzel tady, máme

587
00:30:07,930 --> 00:30:12,270
aby se ujistil, že
člověk předchozí do tohoto uzlu

588
00:30:12,270 --> 00:30:14,172
je ten, který přiřazuje ukazatel.

589
00:30:14,172 --> 00:30:16,380
Takže pak budete muset trochu
sledovat dvě věci.

590
00:30:16,380 --> 00:30:19,420
Máte-li sledovat, kde to
uzel je v současné době vložení do.

591
00:30:19,420 --> 00:30:23,280
Musíte také sledovat, kde
předchozí uzel, který se díváte

592
00:30:23,280 --> 00:30:24,340
byl také tam.

593
00:30:24,340 --> 00:30:25,830
Všichni dobře s tím?

594
00:30:25,830 --> 00:30:26,500
DOBŘE.

595
00:30:26,500 --> 00:30:28,000
>> Jak se o vložení do konce?

596
00:30:28,000 --> 00:30:34,220
Kdybych chtěl přidat here-- kdybych chtěl
přidat nový uzel na konec seznamu,

597
00:30:34,220 --> 00:30:37,009
Jak bych mohl jít o tom, že?

598
00:30:37,009 --> 00:30:39,300
Publikum: Takže v současné době je
poslední, kdo se ukázal na null.

599
00:30:39,300 --> 00:30:40,960
ANDI PENG: Jo.

600
00:30:40,960 --> 00:30:43,560
Přesně, takže tento jednou
V současné době je orientováno na vědět,

601
00:30:43,560 --> 00:30:46,720
a tak myslím, že v tomto smyslu, že je to
velmi snadno přidat na konec seznamu.

602
00:30:46,720 --> 00:30:51,810
Jediné, co musíte udělat, je nastavit
rovná null a pak boom.

603
00:30:51,810 --> 00:30:53,070
Přesně tam, velmi snadné.

604
00:30:53,070 --> 00:30:53,960
Velmi jednoduché.

605
00:30:53,960 --> 00:30:56,430
>> Velmi podobné
hlava, ale logicky vás

606
00:30:56,430 --> 00:30:59,690
chcete, aby se ujistil, že kroky
užíváte k dělá něco z toho,

607
00:30:59,690 --> 00:31:01,500
jste po podél.

608
00:31:01,500 --> 00:31:04,420
Je to velmi snadné, ve středu
vašeho kódu, uvíznou na,

609
00:31:04,420 --> 00:31:05,671
oh, mám tolik ukazatelů.

610
00:31:05,671 --> 00:31:07,461
Já nevím, kde
něco ukazuje.

611
00:31:07,461 --> 00:31:09,170
Já ani nevím, který uzel, že jsem dál.

612
00:31:09,170 --> 00:31:11,490
Co se děje?

613
00:31:11,490 --> 00:31:13,620
>> Relax, uklidni se, zhluboka se nadechnout.

614
00:31:13,620 --> 00:31:15,530
Nakreslete si své propojeného seznamu.

615
00:31:15,530 --> 00:31:18,800
Pokud řeknete, já vím, kde přesně
Musím vložit to do

616
00:31:18,800 --> 00:31:22,970
a vím přesně, jak změnit přiřazení my
ukazatele, mnohem, mnohem jednodušší na obrázek

617
00:31:22,970 --> 00:31:27,200
out-- mnohem, mnohem jednodušší, že nebude
ztratit v chybách v kódu.

618
00:31:27,200 --> 00:31:29,410
Každý, kdo s tím OK?

619
00:31:29,410 --> 00:31:31,380
DOBŘE.

620
00:31:31,380 --> 00:31:35,120
>> Takže si myslím, koncept, že jsme se
opravdu mluvil o dřív,

621
00:31:35,120 --> 00:31:38,131
a myslím, že vás nejspíš
není dojde mnohem yet--

622
00:31:38,131 --> 00:31:40,880
je to docela pokročilé concept--
je to, že jsme vlastně mají údaje

623
00:31:40,880 --> 00:31:43,900
struktura volal dvojnásob propojeného seznamu.

624
00:31:43,900 --> 00:31:46,390
Tak jako vy můžete vidět,
vše, co děláte, je vytvoření

625
00:31:46,390 --> 00:31:50,400
skutečné hodnoty, navíc
Ukazatel na každé z našich uzlů

626
00:31:50,400 --> 00:31:52,660
která také poukazuje na předchozí uzlu.

627
00:31:52,660 --> 00:31:58,170
Takže nejen že máme své
uzly poukazují na ten příští.

628
00:31:58,170 --> 00:32:01,430
Poukazují rovněž na předchozí.

629
00:32:01,430 --> 00:32:04,310
Budu ignorovat tyhle dva právě teď.

630
00:32:04,310 --> 00:32:06,740
>> Takže máte řetěz
které se mohou pohybovat oběma směry,

631
00:32:06,740 --> 00:32:09,630
a pak je to trochu jednodušší
logicky následovat.

632
00:32:09,630 --> 00:32:11,896
Stejně jako tady, místo
sledování z, oh, já

633
00:32:11,896 --> 00:32:14,520
musí vědět, že tento uzel
ten, který mám k přeřazení,

634
00:32:14,520 --> 00:32:17,532
Můžu prostě jít sem a
stačí vytáhnout předchozí.

635
00:32:17,532 --> 00:32:19,490
Pak jsem přesně vědět, kde
že je, a pak vás

636
00:32:19,490 --> 00:32:21,130
Nemusíte se přejít
celistvost Google seznamu.

637
00:32:21,130 --> 00:32:22,180
Je to trochu jednodušší.

638
00:32:22,180 --> 00:32:24,960
>> Ale jako takový, budete mít dvojnásob
množství ukazatelů,

639
00:32:24,960 --> 00:32:26,960
To je dvojnásobek paměti.

640
00:32:26,960 --> 00:32:28,950
Je to hodně ukazatelů sledovat.

641
00:32:28,950 --> 00:32:32,140
Je to trochu složitější, ale je to
trochu více uživatelsky přívětivé závislosti

642
00:32:32,140 --> 00:32:34,080
na to, co se snažíte dosáhnout.

643
00:32:34,080 --> 00:32:36,910
>> Takže tento druh údajů
Struktura zcela existuje,

644
00:32:36,910 --> 00:32:40,280
a struktura je velmi, velmi
jednoduché, s výjimkou vše máte, je,

645
00:32:40,280 --> 00:32:43,850
namísto pouze ukazatel na další,
máte také ukazatel na předchozí.

646
00:32:43,850 --> 00:32:45,940
To je vše, byl rozdíl.

647
00:32:45,940 --> 00:32:47,740
Všichni dobře s tím?

648
00:32:47,740 --> 00:32:48,240
Bezva.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Dobře, takže teď jsem
opravdu strávit pravděpodobně

651
00:32:53,280 --> 00:32:56,870
jako je 15 až 20 minut nebo objemu
zbytku času v sekci

652
00:32:56,870 --> 00:32:58,360
mluví o hash tabulek.

653
00:32:58,360 --> 00:33:02,590
Kolik z vás
Přečetl pset5 spec?

654
00:33:02,590 --> 00:33:03,620
Dobře, dobře.

655
00:33:03,620 --> 00:33:06,160
To je vyšší než 50% za normálních okolností.

656
00:33:06,160 --> 00:33:07,560
Je to v pohodě.

657
00:33:07,560 --> 00:33:10,345
>> Tak jako vy uvidíte,
jste výzvou pset5

658
00:33:10,345 --> 00:33:16,790
bude provádění slovník
kde si nahrát přes 140.000 slov

659
00:33:16,790 --> 00:33:20,610
že jsme vám kontrolu pravopisu
to proti všem textu.

660
00:33:20,610 --> 00:33:22,580
Dáme vám náhodné
kusy literatury.

661
00:33:22,580 --> 00:33:23,520
Dáme vám Odyssea.

662
00:33:23,520 --> 00:33:24,561
Dáme vám Ilias.

663
00:33:24,561 --> 00:33:26,350
Dáme vám Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> A vaše výzva
bude kontrolu pravopisu

665
00:33:28,220 --> 00:33:31,760
každé slovo ve všech
z těchto slovníků

666
00:33:31,760 --> 00:33:34,960
v podstatě s naší kontrolou pravopisu.

667
00:33:34,960 --> 00:33:38,620
A tak je tu několik dílů
vytvoření tohoto pset,

668
00:33:38,620 --> 00:33:41,970
První chcete být
schopný skutečně načíst

669
00:33:41,970 --> 00:33:43,970
všechna slova do vašeho
slovník, a pak vás

670
00:33:43,970 --> 00:33:45,530
chtějí být schopni
pravopisu zkontrolovat všechny z nich.

671
00:33:45,530 --> 00:33:48,780
A tak jako takový, budete požadovat
datová struktura, která může dělat to rychle

672
00:33:48,780 --> 00:33:50,790
a efektivně a dynamicky.

673
00:33:50,790 --> 00:33:52,900
>> Takže myslím, že nejjednodušší
způsob, jak to provést,

674
00:33:52,900 --> 00:33:55,010
by pravděpodobně vytvoření pole, ne?

675
00:33:55,010 --> 00:33:58,910
Nejjednodušší způsob skladování je vám
může vytvořit řadu 140,000 slov

676
00:33:58,910 --> 00:34:03,400
a jen je všechny umístit tam a
pak přejít jim binární vyhledávání

677
00:34:03,400 --> 00:34:06,780
nebo výběrů či ne--
Omlouvám se, že se třídění.

678
00:34:06,780 --> 00:34:10,729
Můžete je třídit a pak přejít je
binární vyhledávání, nebo jen lineární hledání

679
00:34:10,729 --> 00:34:13,730
a jen závěrečná slova, ale že
bere obrovské množství paměti,

680
00:34:13,730 --> 00:34:15,190
a to není příliš efektivní.

681
00:34:15,190 --> 00:34:18,350
>> A tak jsme se chystáte začít
mluví o způsobech, kterými se

682
00:34:18,350 --> 00:34:20,110
Naše doba chodu efektivnější.

683
00:34:20,110 --> 00:34:23,190
A naším cílem je dostat
konstantní doba, kdy

684
00:34:23,190 --> 00:34:25,810
je to skoro jako pole, kde
máte okamžitý přístup.

685
00:34:25,810 --> 00:34:28,560
Kdybych chtěl hledat cokoliv,
Chci být schopen jen,

686
00:34:28,560 --> 00:34:30,810
boom, najít přesně to, a vytáhněte ji ven.

687
00:34:30,810 --> 00:34:34,100
A tak se struktura, v níž
budeme stále velmi blízko

688
00:34:34,100 --> 00:34:37,569
aby bylo možné získat přístup konstantní
čas, tento svatý grál

689
00:34:37,569 --> 00:34:41,370
v programování konstanty
Čas se nazývá hash tabulky.

690
00:34:41,370 --> 00:34:45,370
A tak David již dříve zmínil o
[Neslyšitelný] trochu v přednášce,

691
00:34:45,370 --> 00:34:49,100
ale budeme skutečně
ponor v hluboké tento týden

692
00:34:49,100 --> 00:34:51,780
na kus, který je, pokud jde o
jak hash tabulky funguje.

693
00:34:51,780 --> 00:34:53,949
>> Tak tak, že hash
tabulka práce, například,

694
00:34:53,949 --> 00:35:00,230
kdybych chtěl uložit spoustu slovy,
banda slov v anglickém jazyce,

695
00:35:00,230 --> 00:35:02,940
Mohl bych teoreticky dát
banán, jablko, kiwi, mango, pár,

696
00:35:02,940 --> 00:35:04,980
a cantaloupe vše jen na matici.

697
00:35:04,980 --> 00:35:07,044
Všechny by mohly zapadnout a bude najít.

698
00:35:07,044 --> 00:35:09,210
Bylo by druh bolesti
prohledávat a přístupu,

699
00:35:09,210 --> 00:35:12,920
ale jednodušší způsob, jak toho dosáhnout, je
že můžeme vytvořit vlastně struktura

700
00:35:12,920 --> 00:35:15,680
nazývá hash tabulky, kde jsme hash.

701
00:35:15,680 --> 00:35:19,880
Vedeme všechny naše klíčů prostřednictvím
funkce hash, rovnice,

702
00:35:19,880 --> 00:35:22,600
že změní je všechny do
nějaký hodnotu

703
00:35:22,600 --> 00:35:28,740
že pak můžeme ukládat na
v podstatě pole propojeného seznamu.

704
00:35:28,740 --> 00:35:32,570
>> A tak tady, pokud bychom chtěli
ukládat anglická slova,

705
00:35:32,570 --> 00:35:37,250
jsme mohli potenciálně prostě, já ne
Víte, vypněte všechny první písmena

706
00:35:37,250 --> 00:35:39,630
do nějakého druhu čísla.

707
00:35:39,630 --> 00:35:43,140
A tak například, když jsem chtěl
A být synonymem apple--

708
00:35:43,140 --> 00:35:47,460
nebo s indexem 0, a
B synonymem s 1,

709
00:35:47,460 --> 00:35:51,030
můžeme mít 26 záznamů
který může jen uložit

710
00:35:51,030 --> 00:35:53,610
všechna písmena
abeceda, že začneme s.

711
00:35:53,610 --> 00:35:56,130
A pak můžeme mít
apple v indexu od 0.

712
00:35:56,130 --> 00:35:59,160
Můžeme mít banán na indexu
1, ananasový meloun na indexu 2,

713
00:35:59,160 --> 00:36:00,540
a tak dále a tak dále.

714
00:36:00,540 --> 00:36:04,460
A tak, když jsem se chtěl vyhledávat
můj hash stůl a přístup jablko,

715
00:36:04,460 --> 00:36:07,560
Vím, že jablko začíná
à, a vím přesně,

716
00:36:07,560 --> 00:36:10,860
že to musí být a hash
Tabulka na indexu 0 Protože je

717
00:36:10,860 --> 00:36:13,620
funkce dříve přiřazena.

718
00:36:13,620 --> 00:36:16,572
>> Takže já nevím, my jsme
uživatelský program, kde

719
00:36:16,572 --> 00:36:18,780
budete obviněn
arbitrarily-- nebylo svévolně,

720
00:36:18,780 --> 00:36:22,530
se snaží zamyšleně
myslet na dobré rovnic

721
00:36:22,530 --> 00:36:25,460
aby bylo možné rozšířit
mimo všechny své hodnoty

722
00:36:25,460 --> 00:36:29,370
takovým způsobem, že mohou snadno získat přístup
to později se jako rovnice

723
00:36:29,370 --> 00:36:31,130
že vy, sami, víš.

724
00:36:31,130 --> 00:36:35,210
Takže v tom smyslu, jestli bych chtěl jít do
mango, já vím, oh, začíná m.

725
00:36:35,210 --> 00:36:37,134
To musí být v indexu 12.

726
00:36:37,134 --> 00:36:38,800
Nemám prohledávat cokoliv.

727
00:36:38,800 --> 00:36:42,080
Vím, že exactly-- jsem mohl jen jít do
index 12 a vytáhněte to ven.

728
00:36:42,080 --> 00:36:45,520
>> Každý jasně o tom, jak
hashovací funkce tabulky funguje?

729
00:36:45,520 --> 00:36:48,380
Je to tak trochu jen složitější pole.

730
00:36:48,380 --> 00:36:50,010
To je vše, co je.

731
00:36:50,010 --> 00:36:51,630
DOBŘE.

732
00:36:51,630 --> 00:36:57,690
>> Takže myslím, že narazíme
tato otázka toho, co

733
00:36:57,690 --> 00:37:06,390
se stane, když máte více věcí
že vám stejný index?

734
00:37:06,390 --> 00:37:10,570
Tak říkají naši funkci, všichni to
udělal, bylo, přijmout, že první písmeno

735
00:37:10,570 --> 00:37:14,490
a měnit na
Příslušná 0 až 25 index.

736
00:37:14,490 --> 00:37:17,137
To je naprosto v pořádku, pokud
máte pouze jeden z každého z nich.

737
00:37:17,137 --> 00:37:18,970
Ale druhá začnete
které mají více, že jste

738
00:37:18,970 --> 00:37:20,910
bude mít, co se nazývá kolize.

739
00:37:20,910 --> 00:37:25,580
>> Takže když se snažím vložit pohřbít do hash
tabulka, která již má banán na tom,

740
00:37:25,580 --> 00:37:27,870
co se stane, když
pokusu o vložení, že?

741
00:37:27,870 --> 00:37:30,930
Zlé věci proto, že banán
Již v rámci indexu existuje

742
00:37:30,930 --> 00:37:33,800
že chcete uložit jej do.

743
00:37:33,800 --> 00:37:35,560
Berry druh je jako, ehm, co mám dělat?

744
00:37:35,560 --> 00:37:37,080
Nevím, kam jít.

745
00:37:37,080 --> 00:37:38,410
Jak mohu vyřešit?

746
00:37:38,410 --> 00:37:41,150
>> A tak si kluci bude druh
viz děláme této choulostivé věci

747
00:37:41,150 --> 00:37:44,810
kde můžeme trochu vlastně
Vytvoření propojeného seznamu v našich polích.

748
00:37:44,810 --> 00:37:46,840
A tak nejjednodušší způsob
přemýšlet o tom,

749
00:37:46,840 --> 00:37:50,830
všechny hash tabulka je
řada spojových seznamů.

750
00:37:50,830 --> 00:37:55,670
A tak, v tomto smyslu, máte
toto krásné pole ukazatelů,

751
00:37:55,670 --> 00:37:58,740
a pak každý ukazatel v
že hodnota tohoto indexu,

752
00:37:58,740 --> 00:38:00,740
může skutečně ukazovat na jiné věci.

753
00:38:00,740 --> 00:38:05,720
A tak budete mít všechny tyto oddělené
řetězy spadnutí jednoho velkého pole.

754
00:38:05,720 --> 00:38:07,960
>> A tak tady, když jsem
chtěl vložit bobule,

755
00:38:07,960 --> 00:38:11,220
Já vím, v pořádku, budu vstup
to přes můj hash funkce.

756
00:38:11,220 --> 00:38:15,070
Chystám se skončit s indexem
1, a pak budu mít možnost

757
00:38:15,070 --> 00:38:20,410
jen menší podmnožina toto
obří 140000-slovo slovníku.

758
00:38:20,410 --> 00:38:24,220
A pak jsem si jen dívat
prostřednictvím 1/26 toho.

759
00:38:24,220 --> 00:38:27,910
>> A tak jsem si jen vložit
bobule buď před nebo po banány

760
00:38:27,910 --> 00:38:28,820
v tomto případě?

761
00:38:28,820 --> 00:38:29,700
Po, že jo?

762
00:38:29,700 --> 00:38:33,920
A tak budete chtít
vložit tento uzel po banán,

763
00:38:33,920 --> 00:38:36,667
a tak budete vkládat
na ocasu tohoto propojeného seznamu.

764
00:38:36,667 --> 00:38:38,500
Chystám se vrátit zpět
k tomuto předchozímu snímku,

765
00:38:38,500 --> 00:38:40,680
tak vy můžete vidět, jak
hash funkce pracuje.

766
00:38:40,680 --> 00:38:43,980
>> Takže hash funkce je tato rovnice
že vedete druh váš vstup

767
00:38:43,980 --> 00:38:46,940
až se dostat co index
Chcete-li ji přiřadit k.

768
00:38:46,940 --> 00:38:51,130
A tak, v tomto případě všechno, co jsme chtěli
udělat, bylo vzít první písmeno,

769
00:38:51,130 --> 00:38:55,890
obrátit, že do indexu, pak jsme
lze uložit, že v našem hash funkce.

770
00:38:55,890 --> 00:39:00,160
Vše, co tu děláme, je, že jsme
konverzi první písmeno.

771
00:39:00,160 --> 00:39:04,770
Takže keykey [0] je jen první písmeno
jakéhokoli string budeme mít,

772
00:39:04,770 --> 00:39:05,720
jsme předáním.

773
00:39:05,720 --> 00:39:09,740
Jsme konverzi, že pro horní, a
jsme se odečte od velkými písmeny A,

774
00:39:09,740 --> 00:39:11,740
takže vše, co dělá
nám dává číslo

775
00:39:11,740 --> 00:39:13,670
v němž můžeme hash naše hodnoty na.

776
00:39:13,670 --> 00:39:16,550
>> A pak budeme
návrat hash modulu velikosti.

777
00:39:16,550 --> 00:39:19,340
Buďte velmi, velmi opatrní
proto, že teoreticky, zde

778
00:39:19,340 --> 00:39:21,870
Váš hash hodnota mohla být nekonečná.

779
00:39:21,870 --> 00:39:23,660
Mohlo by to prostě jít dál a dál a dál.

780
00:39:23,660 --> 00:39:26,080
Mohlo by to být nějaké opravdu,
Opravdu velké hodnoty,

781
00:39:26,080 --> 00:39:29,849
ale proto, že vaše hash tabulky, které
jste vytvořili má pouze 26 indexy,

782
00:39:29,849 --> 00:39:31,890
chcete ujistěte se, že
modulusing takže

783
00:39:31,890 --> 00:39:33,848
ne run-- je to to samé
věc jako queue--

784
00:39:33,848 --> 00:39:36,320
takže nemusíte spouštět off
Spodní část vašeho hash funkce.

785
00:39:36,320 --> 00:39:39,210
>> Chcete zabalit zpět kolem
stejným způsobem v [neslyšitelných], když

786
00:39:39,210 --> 00:39:41,750
jste měl jako velmi,
velmi velké písmeno, vy

787
00:39:41,750 --> 00:39:43,740
nechtěl, aby
stačí spustit až na konec.

788
00:39:43,740 --> 00:39:46,948
To samé tady, chcete ujistit,
neběží z konce obalem

789
00:39:46,948 --> 00:39:48,330
kolem horní části tabulky.

790
00:39:48,330 --> 00:39:50,530
Tak to je jen velmi
jednoduchá funkce hash.

791
00:39:50,530 --> 00:39:56,570
Vše, co udělala, bylo vzít jako první
Dopis z jakéhokoli našeho vstupu byla

792
00:39:56,570 --> 00:40:01,660
a měnit na index, který
jsme mohli dát do naší tabulky hash.

793
00:40:01,660 --> 00:40:05,450
>> Jo, a tak jak jsem řekl dříve,
tak, že jsme se vyřešit kolizí

794
00:40:05,450 --> 00:40:09,330
v naší hash tabulek mají,
To, čemu říkáme, řetězení.

795
00:40:09,330 --> 00:40:13,860
Takže pokud se pokusíte vložit více
slova, která začínají stejnou věc,

796
00:40:13,860 --> 00:40:16,145
budete mít jednu hodnotu hash.

797
00:40:16,145 --> 00:40:18,770
Avokádo a jablko, pokud jste
spusťte jej přes naše hash funkce,

798
00:40:18,770 --> 00:40:21,450
Chystáte se vám dát
Stejné číslo, počet 0.

799
00:40:21,450 --> 00:40:24,550
A tak způsob, jak vyřešit to je
že můžeme vlastně trochu propojit

800
00:40:24,550 --> 00:40:27,010
společně prostřednictvím spojových seznamů.

801
00:40:27,010 --> 00:40:29,600
>> A tak v tomto smyslu,
vy můžete vidět druh

802
00:40:29,600 --> 00:40:32,640
o tom, jak datové struktury, které
jsme se nastavit dříve

803
00:40:32,640 --> 00:40:35,870
jako rozinkami spojen se seznamem druhu
z může přijít společně do jednoho.

804
00:40:35,870 --> 00:40:38,860
A pak si můžete vytvořit daleko
účinnější datové struktury

805
00:40:38,860 --> 00:40:43,350
který zvládne větší množství
Data, která dynamicky měnit velikost v závislosti

806
00:40:43,350 --> 00:40:44,870
na vašich potřebách.

807
00:40:44,870 --> 00:40:45,620
Všichni jasné?

808
00:40:45,620 --> 00:40:47,580
Každý druh clear
o tom, co se zde děje?

809
00:40:47,580 --> 00:40:52,110
>> Kdybych chtěl insert-- co je to
ovoce, které začíná, já nevím,

810
00:40:52,110 --> 00:40:54,726
B, jiné než Berry, banán.

811
00:40:54,726 --> 00:40:55,710
>> Diváků: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI PENG: Blackberry, Blackberry.

813
00:40:57,910 --> 00:41:00,530
Kam blackberry jít sem?

814
00:41:00,530 --> 00:41:04,251
No, my vlastně nejsou tříděny
to ještě, ale teoreticky

815
00:41:04,251 --> 00:41:06,250
Pokud bychom chtěli mít tuto
v abecedním pořadí,

816
00:41:06,250 --> 00:41:07,944
kam by měl jít BlackBerry?

817
00:41:07,944 --> 00:41:09,210
>> Diváků: [Neslyšitelné]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG: Přesně, po tu, že jo?

819
00:41:11,100 --> 00:41:14,950
Ale protože je to velmi obtížné
reorder-- Myslím, že je to na vás kluci.

820
00:41:14,950 --> 00:41:17,920
Vy můžete zcela
implementovat, co chcete.

821
00:41:17,920 --> 00:41:20,730
Čím více účinný způsob
jak to udělat snad

822
00:41:20,730 --> 00:41:24,570
by bylo seřadit spojené
vypsat do abecedním pořadí,

823
00:41:24,570 --> 00:41:26,520
a tak, když jste
vkládání věcí, budete chtít

824
00:41:26,520 --> 00:41:28,632
si být jisti, o jejich zařazení
do abecedním pořadí

825
00:41:28,632 --> 00:41:30,590
takže pak, když jste
snaží se je hledat,

826
00:41:30,590 --> 00:41:32,410
nemusíte projít všechno.

827
00:41:32,410 --> 00:41:35,290
Víte přesně, kde
to je, a je to jednodušší.

828
00:41:35,290 --> 00:41:39,100
>> Ale pokud máte trochu
věci proložené náhodně,

829
00:41:39,100 --> 00:41:41,420
jste stále bude mít
to procházet tak jako tak.

830
00:41:41,420 --> 00:41:44,990
A tak, když jsem se chtěl jen
vložit blackberry zde

831
00:41:44,990 --> 00:41:47,470
a já jsem chtěl hledat
to, já vím, oh, ostružina

832
00:41:47,470 --> 00:41:52,012
musí začínat s indexem 1, a tak jsem
vím, okamžitě stačí hledat na 1.

833
00:41:52,012 --> 00:41:53,970
A pak jsem si trochu
procházet propojeného seznamu

834
00:41:53,970 --> 00:41:56,120
dokud se na BlackBerry,
a then-- jo?

835
00:41:56,120 --> 00:41:59,550
>> Diváků: Pokud se snažíte create--
Myslím, že takhle je to velmi jednoduchý hash

836
00:41:59,550 --> 00:42:00,050
funkce.

837
00:42:00,050 --> 00:42:02,835
A pokud bychom chtěli dělat
více vrstev, kteří rádi,

838
00:42:02,835 --> 00:42:05,870
OK, chceme rozdělit na
stejně jako všechny znaky abecedy

839
00:42:05,870 --> 00:42:09,040
a pak zase rád jiný soubor
abecedních písmen v rámci, který,

840
00:42:09,040 --> 00:42:11,715
jsme uvedení jako hash
Tabulka v hash tabulky,

841
00:42:11,715 --> 00:42:13,256
nebo jako funkce v rámci funkce?

842
00:42:13,256 --> 00:42:14,880
Nebo je that--

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG: Takže vaše hash
function-- vaše hash tabulky

844
00:42:17,510 --> 00:42:19,360
může být tak velký, jak chcete, aby to.

845
00:42:19,360 --> 00:42:21,930
Takže v tomto smyslu, myslel jsem,
to bylo velmi jednoduché, velmi

846
00:42:21,930 --> 00:42:25,320
jednoduché pro mě prostě tak nějak na bázi
dopisů z první slovo.

847
00:42:25,320 --> 00:42:28,690
A tak je tu jen 26 možností.

848
00:42:28,690 --> 00:42:32,650
Mohu jen dostat 26 z možností
0 až 25, protože se může pouze

849
00:42:32,650 --> 00:42:36,510
začít od A do Z. Ale Pokud byste chtěli
přidat, možná více složitosti

850
00:42:36,510 --> 00:42:39,260
nebo rychlejší běh času, aby svůj
hash tabulky, si absolutně

851
00:42:39,260 --> 00:42:40,760
můžete dělat všechny druhy věcí.

852
00:42:40,760 --> 00:42:43,330
Můžete si vytvořit svůj vlastní
rovnice, která vám dává

853
00:42:43,330 --> 00:42:48,000
více rozdělení ve vašem
slova, pak při vyhledávání,

854
00:42:48,000 --> 00:42:49,300
že to bude rychlejší.

855
00:42:49,300 --> 00:42:52,100
>> Je to zcela na vás kluci
jak chcete implementovat to.

856
00:42:52,100 --> 00:42:55,140
Myslete na to, jak jen kbelíky.

857
00:42:55,140 --> 00:42:57,376
Pokud bych chtěl mít
26 kbelíky, jdu

858
00:42:57,376 --> 00:42:59,420
třídit věci do těchto kbelíky.

859
00:42:59,420 --> 00:43:02,980
Ale já budu mít spoustu
věcí v každém kbelíku,

860
00:43:02,980 --> 00:43:05,890
takže pokud chcete, aby to
rychlejší a efektivnější,

861
00:43:05,890 --> 00:43:07,190
dovolte mi, abych sto kbelíky.

862
00:43:07,190 --> 00:43:09,290
>> Ale pak budete muset přijít na to,
způsob, nechte tak, aby byly

863
00:43:09,290 --> 00:43:11,040
ve správném kbelíku, které by měly být v.

864
00:43:11,040 --> 00:43:13,331
Ale pak, když jste vlastně
Chcete se podívat na tom kbelík,

865
00:43:13,331 --> 00:43:16,410
je to mnohem rychlejší, protože tam je
méně věci v každém segmentu.

866
00:43:16,410 --> 00:43:20,250
A tak, jo, to je vlastně
trik pro vás v pset5

867
00:43:20,250 --> 00:43:22,360
je to, že budete
vyzváni, aby jen vytvořit

868
00:43:22,360 --> 00:43:26,170
co je nejúčinnější
funkce si můžete myslet, že je

869
00:43:26,170 --> 00:43:28,520
schopna ukládat a kontrolovat tyto hodnoty.

870
00:43:28,520 --> 00:43:30,840
>> Zcela na vás kluci
však budete chtít dělat to,

871
00:43:30,840 --> 00:43:32,229
ale to je opravdu dobrý bod.

872
00:43:32,229 --> 00:43:34,520
Že druh logiky vy
chtějí začít přemýšlet o

873
00:43:34,520 --> 00:43:37,236
Je dobře, tak proč ne já dělat více kbelíky.

874
00:43:37,236 --> 00:43:39,527
A pak jsem musel hledat
méně věcí, a pak možná já

875
00:43:39,527 --> 00:43:41,640
mají jiný hash funkce.

876
00:43:41,640 --> 00:43:45,500
>> Jo, je tu mnoho způsobů, jak toho dosáhnout
pset, některé jsou rychleji než ostatní.

877
00:43:45,500 --> 00:43:50,630
Já naprosto bude jen vidět, jak
rychlá byl nejrychlejší kluci budou

878
00:43:50,630 --> 00:43:55,170
být schopni dostat své funkce do práce.

879
00:43:55,170 --> 00:43:58,176
OK, všichni dobře na
PROPOJENÍ ZÁSOB a hashovací tabulky?

880
00:43:58,176 --> 00:44:00,800
Je to vlastně jako velmi jednoduchý
koncept, pokud si myslíte o tom.

881
00:44:00,800 --> 00:44:05,160
Vše, co to je, je oddělování cokoliv
vaše vstupy jsou do kbelíků,

882
00:44:05,160 --> 00:44:10,670
jejich třídění, a pak vyhledávání ve
uvádí, že je spojován s.

883
00:44:10,670 --> 00:44:11,852
>> Bezva.

884
00:44:11,852 --> 00:44:18,160
Dobře, teď máme jiný druh
datové struktury, které se říká strom.

885
00:44:18,160 --> 00:44:20,850
Pojďme dál a hovoří o pokusech
, které jsou zřetelně odlišné,

886
00:44:20,850 --> 00:44:22,330
ale ve stejné kategorii.

887
00:44:22,330 --> 00:44:29,010
V podstatě, všichni strom je místo
organizování dat v lineárně

888
00:44:29,010 --> 00:44:32,560
že hash tabulka vám does--
vím, je to má horní a spodní část

889
00:44:32,560 --> 00:44:37,900
a pak tak nějak propojit pryč to-- na
Strom má horní který nazýváte kořen,

890
00:44:37,900 --> 00:44:40,220
a pak to má listy všechno kolem něj.

891
00:44:40,220 --> 00:44:42,390
>> A tak vše, co zde
je jen na nejvyšší uzel

892
00:44:42,390 --> 00:44:45,980
, který odkazuje na jiných uzlů, které body
na více uzlů, a tak dále a tak dále.

893
00:44:45,980 --> 00:44:48,130
A tak stačí štípání větví.

894
00:44:48,130 --> 00:44:53,255
Je to jen jiný způsob organizace
dat, a protože jsme to strom volání,

895
00:44:53,255 --> 00:44:56,270
vy jen-- je to jen
modelován ven vypadat jako strom.

896
00:44:56,270 --> 00:44:57,670
To je důvod, proč říkáme, že stromy.

897
00:44:57,670 --> 00:44:59,370
>> Hash tabulka vypadá jako tabulky.

898
00:44:59,370 --> 00:45:01,310
Strom jen vypadá jako strom.

899
00:45:01,310 --> 00:45:03,300
Vše, co to je, je samostatná
způsob organizace uzlů

900
00:45:03,300 --> 00:45:06,020
V závislosti na jaké jsou vaše potřeby.

901
00:45:06,020 --> 00:45:11,810
>> Takže máte kořen a
pak máte listy.

902
00:45:11,810 --> 00:45:15,380
Způsob, jakým můžeme zvláště
přemýšlet o tom, že je to binární strom,

903
00:45:15,380 --> 00:45:18,150
binární strom je jen
Specifickým typem stromu

904
00:45:18,150 --> 00:45:22,450
kde každý uzel pouze body
k, při max, další dva uzly.

905
00:45:22,450 --> 00:45:25,434
A tak tady máte odlišný
symetrie ve vašem stromě

906
00:45:25,434 --> 00:45:28,600
že usnadňuje druh vypadat
na jaké hodnoty jste, protože pak vás

907
00:45:28,600 --> 00:45:30,150
mají vždy levý nebo pravý.

908
00:45:30,150 --> 00:45:33,150
Tam je nikdy jako levé třetinu
levá nebo čtvrtiny z levé strany.

909
00:45:33,150 --> 00:45:36,358
Je to jen máte doleva a právo
a můžete vyhledávat buď z těchto dvou.

910
00:45:36,358 --> 00:45:38,980
A proč je to užitečné?

911
00:45:38,980 --> 00:45:40,980
Způsob, jakým je
užitečné, je pokud hledáte

912
00:45:40,980 --> 00:45:42,890
prohledávat hodnotám, že jo?

913
00:45:42,890 --> 00:45:45,640
Spíše než se provádí binární
hledat v chybové poli,

914
00:45:45,640 --> 00:45:49,260
pokud byste chtěli mít možnost vložit uzly
a odnést uzly na vůli a také

915
00:45:49,260 --> 00:45:52,185
zachovat vyhledávání
kapacity binární vyhledávání.

916
00:45:52,185 --> 00:45:54,560
Takže tímto způsobem, jsme trochu
Pamatuji si, když jsme tricking--

917
00:45:54,560 --> 00:45:56,530
řekl spojové seznamy nemohou binární hledání?

918
00:45:56,530 --> 00:46:01,700
Jsme trochu vytvoření datové struktury
že triky, které do práce.

919
00:46:01,700 --> 00:46:05,034
>> A to proto, spojové seznamy jsou lineární,
oni jen propojit jeden po druhém.

920
00:46:05,034 --> 00:46:06,950
Můžeme mít trochu
jiný druh ukazatelů

921
00:46:06,950 --> 00:46:09,408
tento bod na různé uzly
že nám může pomoci s vyhledáváním.

922
00:46:09,408 --> 00:46:12,590
A tak tady, kdybych chtěl
mají strom binárního vyhledávání,

923
00:46:12,590 --> 00:46:14,090
Vím, že moje druhé, jestliže 55.

924
00:46:14,090 --> 00:46:18,280
Já jsem prostě jít k vytvoření, že
jako můj středu, jako můj kořen,

925
00:46:18,280 --> 00:46:20,770
a pak budu mít
Hodnoty spin off z toho.

926
00:46:20,770 --> 00:46:25,610
>> Tak tady, pokud budu hledat
hodnotu 66, mohu začít na 55 let.

927
00:46:25,610 --> 00:46:27,310
To je 66 vyšší než 55?

928
00:46:27,310 --> 00:46:30,970
Ano, je to, takže vím, že mus hledat
i n pravý ukazatel tohoto stromu.

929
00:46:30,970 --> 00:46:32,440
Chodím do 77.

930
00:46:32,440 --> 00:46:35,367
OK, je menší než 66 nebo větší než 77?

931
00:46:35,367 --> 00:46:37,950
To je méně než, takže víte, oh,
, který má být na levé straně uzlu.

932
00:46:37,950 --> 00:46:41,410
>> A tak tady máme trochu konzervování
všechny z velkých věcí, o poli,

933
00:46:41,410 --> 00:46:44,420
tak jako dynamickou změnu velikosti
objektů, přičemž

934
00:46:44,420 --> 00:46:49,530
moci vkládat a mazat na vůli,
aniž by se museli starat o fixní

935
00:46:49,530 --> 00:46:50,370
množství prostoru.

936
00:46:50,370 --> 00:46:52,820
Stále jsme zachovat všechny
ty úžasné věci

937
00:46:52,820 --> 00:46:57,140
a zároveň je schopen se zachovala
log a hledání času binární vyhledávání

938
00:46:57,140 --> 00:47:00,450
že jsme pouze dříve
možnost získat frázi.

939
00:47:00,450 --> 00:47:06,310
>> Pohodě datová struktura, druh
provádění složité, uzel.

940
00:47:06,310 --> 00:47:08,311
Jak můžete vidět, všechny to
je struct uzlu

941
00:47:08,311 --> 00:47:10,143
je to, že máte vlevo
a pravý ukazatel.

942
00:47:10,143 --> 00:47:11,044
To je vše, co je.

943
00:47:11,044 --> 00:47:12,960
Takže spíše než jen
mající x nebo předchozí.

944
00:47:12,960 --> 00:47:15,920
Máte doleva nebo doprava a
můžete trochu propojit dohromady

945
00:47:15,920 --> 00:47:16,836
Nicméně se tak rozhodnete.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, jsme vlastně bude
jen trvat několik minut.

948
00:47:24,270 --> 00:47:25,790
Takže budeme vrátit se sem.

949
00:47:25,790 --> 00:47:28,270
Jak už jsem řekl dříve,
Tak nějak jsem vysvětlil,

950
00:47:28,270 --> 00:47:31,520
logika, jak
by se hledat přes to.

951
00:47:31,520 --> 00:47:33,860
Budeme se snažit
pseudocoding na to vidět,

952
00:47:33,860 --> 00:47:38,000
pokud můžeme trochu použije
Stejná logika binárního vyhledávání

953
00:47:38,000 --> 00:47:40,055
na jiný typ datové struktury.

954
00:47:40,055 --> 00:47:45,049
Pokud si kluci chtějí, aby se jako pár
minut, jen přemýšlet o tom.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
DOBŘE.

957
00:48:46,925 --> 00:48:51,407
Dobře, budu
vlastně jen aby vám the-- ne,

958
00:48:51,407 --> 00:48:52,990
budeme mluvit o pseudocode jako první.

959
00:48:52,990 --> 00:48:56,580
Takže to někdo chtěl
dát stab na to, co

960
00:48:56,580 --> 00:49:02,100
První věc, kterou chcete dělat, když
začínáte z vyhledávání?

961
00:49:02,100 --> 00:49:04,460
Pokud hledáme
hodnota 66, co je

962
00:49:04,460 --> 00:49:07,940
První věc, kterou chceme dělat, když
chceme binární vyhledávání tento strom?

963
00:49:07,940 --> 00:49:10,760
>> Diváků: Chcete vypadat správně
a podívat se vlevo a podívejte [neslyšitelný]

964
00:49:10,760 --> 00:49:11,230
větší počet.

965
00:49:11,230 --> 00:49:12,271
>> ANDI PENG: Jo, přesně tak.

966
00:49:12,271 --> 00:49:15,350
Takže budete podívat se na svůj kořen.

967
00:49:15,350 --> 00:49:18,180
Je tu spousta způsobů, jak můžete volat
to, vaši rodič uzel lidé říkají.

968
00:49:18,180 --> 00:49:21,317
Líbí se mi říci, protože kořen
to je jako kořen stromu.

969
00:49:21,317 --> 00:49:23,400
Budeš se dívat na
kořenový uzel, a vy jste

970
00:49:23,400 --> 00:49:26,940
jde vidět, je 66 vyšší
nebo menší než 55.

971
00:49:26,940 --> 00:49:30,360
A pokud je to větší než, no, to je
větší než tam, kde chceme vypadat?

972
00:49:30,360 --> 00:49:32,000
Kde chceme hledat, ne?

973
00:49:32,000 --> 00:49:34,340
Chceme prohledat
Pravá polovina tohoto stromu.

974
00:49:34,340 --> 00:49:38,390
>> Takže máme, pohodlně, je
ukazatel, který ukazuje na pravé straně.

975
00:49:38,390 --> 00:49:44,325
A tak pak můžeme nastavit
náš nový kořen být 77.

976
00:49:44,325 --> 00:49:46,450
Můžeme prostě jít kamkoli
pointer ukazuje.

977
00:49:46,450 --> 00:49:49,100
No, oh, tady začínáme
na 77, a můžeme jen

978
00:49:49,100 --> 00:49:51,172
to rekurzivně znovu a znovu.

979
00:49:51,172 --> 00:49:52,880
Tímto způsobem, tak nějak
o mají funkci.

980
00:49:52,880 --> 00:49:57,430
Máte způsob vyhledávání, které vás
stačí opakovat znovu a znovu a znovu,

981
00:49:57,430 --> 00:50:02,720
podle toho, kde se chcete podívat
až se nakonec dostal na hodnotu

982
00:50:02,720 --> 00:50:04,730
které hledáte.

983
00:50:04,730 --> 00:50:05,230
Dávat smysl?

984
00:50:05,230 --> 00:50:07,800
>> Chystám se vám ukázat skutečný
kódu, a je to hodně kódu.

985
00:50:07,800 --> 00:50:08,674
Není třeba šílet.

986
00:50:08,674 --> 00:50:09,910
Promluvíme si přes to.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Ve skutečnosti, no.

989
00:50:14,020 --> 00:50:15,061
To byl jen pseudokód.

990
00:50:15,061 --> 00:50:17,860
OK, to byl jen pseudokód,
který je trochu složitější,

991
00:50:17,860 --> 00:50:19,751
ale je to naprosto v pořádku.

992
00:50:19,751 --> 00:50:21,000
Každý, kdo po podél tady?

993
00:50:21,000 --> 00:50:24,260
Je-li kořen je null, návrat
false protože to znamená

994
00:50:24,260 --> 00:50:26,850
vy ani nemusíte nic tam.

995
00:50:26,850 --> 00:50:31,376
>> Je-li kořen n je hodnota, takže pokud je
se stane být ten, že jste při pohledu na,

996
00:50:31,376 --> 00:50:34,000
pak budete vrátí hodnotu true
protože víte, že jste ji našli.

997
00:50:34,000 --> 00:50:36,250
Ale pokud je tato hodnota nižší
než root n, ty jsi

998
00:50:36,250 --> 00:50:38,332
bude hledat levý
dítě nebo levé křídlo,

999
00:50:38,332 --> 00:50:39,540
co chcete říkat.

1000
00:50:39,540 --> 00:50:41,750
A pokud je hodnota vyšší než root,
budete hledat ten správný strom,

1001
00:50:41,750 --> 00:50:44,610
pak stačí spustit funkci
pomocí vyhledávání znovu.

1002
00:50:44,610 --> 00:50:48,037
>> A jestliže kořen je null, že
znamená, že jste došli na konec?

1003
00:50:48,037 --> 00:50:50,120
To znamená, že nemáte
Více odchází hledat,

1004
00:50:50,120 --> 00:50:52,230
pak víte, oh, já
Asi to není v tu

1005
00:50:52,230 --> 00:50:55,063
protože po Díval jsem se přes
celá věc a není to tady,

1006
00:50:55,063 --> 00:50:56,930
to prostě nemusí být tady.

1007
00:50:56,930 --> 00:50:58,350
>> Znamená to, že smysl pro všechny?

1008
00:50:58,350 --> 00:51:03,230
Takže je to jako binární vyhledávání konzervačním
Schopnosti propojených seznamů.

1009
00:51:03,230 --> 00:51:09,200
Cool, a tak druhý typ
datové struktury vy kluci

1010
00:51:09,200 --> 00:51:13,180
mohou vyzkoušet provádění na pset,
máte jen vybrat jednu metodu.

1011
00:51:13,180 --> 00:51:19,430
Ale možná alternativní metodou
hash tabulka je to, co nazýváme trie.

1012
00:51:19,430 --> 00:51:24,080
>> Vše, Trie je je
Specifickým typem stromu

1013
00:51:24,080 --> 00:51:28,600
má hodnoty, které jdou na jiné hodnoty.

1014
00:51:28,600 --> 00:51:31,450
A tak místo toho, binární
strom v tom smyslu, že pouze jedna

1015
00:51:31,450 --> 00:51:35,940
věc může poukázat na dva, můžete mít
jedna věc, přejděte na mnoho, mnoho věcí.

1016
00:51:35,940 --> 00:51:39,450
Ty mají v zásadě pole
uvnitř které ukládáte

1017
00:51:39,450 --> 00:51:41,790
ukazatele, které ukazují na jiné pole.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Takže uzel, jak
by definoval trie

1020
00:51:49,460 --> 00:51:52,590
je chceme mít
Boolean, c slovo, že jo?

1021
00:51:52,590 --> 00:51:54,920
Takže uzel je Boolean
jako pravdivé či nepravdivé,

1022
00:51:54,920 --> 00:51:58,490
v první řadě v čele
že pole, je to slovo?

1023
00:51:58,490 --> 00:52:03,620
Za druhé, chcete mít ukazatele
se bez ohledu na ostatní z nich jsou.

1024
00:52:03,620 --> 00:52:07,470
Trochu složitější, trochu abstraktní, ale
Budu vysvětlovat, co to všechny prostředky.

1025
00:52:07,470 --> 00:52:13,800
>> Tak tady, na vrcholu, pokud jste
mají celou řadu deklaroval již,

1026
00:52:13,800 --> 00:52:17,040
uzel, kde máte Boolean
hodnota uložena na přední straně

1027
00:52:17,040 --> 00:52:19,490
který vám řekne, je to slovo?

1028
00:52:19,490 --> 00:52:20,520
Není to slovo?

1029
00:52:20,520 --> 00:52:23,240
A pak máte
zbytek vašeho pole, které

1030
00:52:23,240 --> 00:52:26,040
ve skutečnosti ukládá všechny
možnosti toho, co by to mohlo být.

1031
00:52:26,040 --> 00:52:28,660
Tak, například, jako je
nahoře máte

1032
00:52:28,660 --> 00:52:32,140
První věc, která říká, že pravda nebo
false, ano nebo ne, to je slovo.

1033
00:52:32,140 --> 00:52:38,130
>> A pak máte 0 až 26
písmena, které můžete uložit.

1034
00:52:38,130 --> 00:52:42,790
Pokud bych chtěl hledat zde
pro bat, jdu na vrchol

1035
00:52:42,790 --> 00:52:49,200
a já se pro B. najdu B v mém
pole, a tak vím, v pořádku, je B slovo?

1036
00:52:49,200 --> 00:52:53,010
B není slovo, takže se tak
Musím pokračovat v hledání.

1037
00:52:53,010 --> 00:52:56,410
Jdu z B, a já se k
ukazatel, který ukazuje na B

1038
00:52:56,410 --> 00:53:00,900
a vidím jiný řadu informací,
stejnou strukturu, které jsme předtím.

1039
00:53:00,900 --> 00:53:05,240
>> A here-- oh, další
Dopis v [neslyšitelný] je A.

1040
00:53:05,240 --> 00:53:07,210
Takže se podíváme v tomto poli.

1041
00:53:07,210 --> 00:53:10,860
Najdeme osmý hodnotu,
a pak se podíváme vidět, oh,

1042
00:53:10,860 --> 00:53:12,840
hej, je to jedním slovem, je B-A slovo?

1043
00:53:12,840 --> 00:53:13,807
Nejedná se o slovo.

1044
00:53:13,807 --> 00:53:14,890
Musíme hledat dál.

1045
00:53:14,890 --> 00:53:17,850
>> A tak pak se podíváme na místo, kde
ukazatel z A bodů,

1046
00:53:17,850 --> 00:53:21,130
a odkazuje na jiný způsob v
který máme větší hodnotu uloží do paměti.

1047
00:53:21,130 --> 00:53:24,150
A nakonec jsme se dostat do
B-A-T, což je slovo.

1048
00:53:24,150 --> 00:53:25,970
A tak se příště
vypadáš, budete

1049
00:53:25,970 --> 00:53:30,850
mít tento kontrolu, ano,
tato Boolean funkce je pravda.

1050
00:53:30,850 --> 00:53:35,450
A tak se v tom smyslu, že jsme trochu
mít strom s poli.

1051
00:53:35,450 --> 00:53:39,890
>> Takže můžete trochu hledat dolů.

1052
00:53:39,890 --> 00:53:43,650
Spíše než hash funkce a
přiřazení hodnot Google seznamu

1053
00:53:43,650 --> 00:53:49,190
můžete jen implementovat
Trie, který prohledává downwords.

1054
00:53:49,190 --> 00:53:50,850
Opravdu, opravdu složité věci.

1055
00:53:50,850 --> 00:53:54,060
Není snadné si myslet, o, protože jsem rád
plivat tolik datových struktur out

1056
00:53:54,060 --> 00:53:58,710
na vás, ale dělá každý druh
pochopit, jak logika to funguje?

1057
00:53:58,710 --> 00:54:01,920
>> OK v pohodě.

1058
00:54:01,920 --> 00:54:05,600
A tak B-A-T, a pak se
budete hledat.

1059
00:54:05,600 --> 00:54:07,940
Příště jdeš
vidět, oh, hej, to je pravda,

1060
00:54:07,940 --> 00:54:09,273
Vím, že to tak musí být slovo.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Totéž pro zoo.

1063
00:54:13,770 --> 00:54:17,960
Tak tady je to právě teď, když jsme
chtěl hledat zoo, právě teď,

1064
00:54:17,960 --> 00:54:20,780
V současné době zoo není
slovo v našem slovníku

1065
00:54:20,780 --> 00:54:25,300
protože, jak vy můžete vidět,
První místo, které máme Boolean

1066
00:54:25,300 --> 00:54:28,590
vrátí pravda, je na konci zoom.

1067
00:54:28,590 --> 00:54:30,430
Máme Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> A tak tady, nemáme vlastně mít
Slovo, zoo, v našem slovníku

1069
00:54:33,900 --> 00:54:36,070
proto, že toto políčko není zaškrtnuto.

1070
00:54:36,070 --> 00:54:39,540
Takže počítač není
vědí, že zoo je slovo,

1071
00:54:39,540 --> 00:54:42,430
protože tak, že máme
uložil to, jen zoom zde

1072
00:54:42,430 --> 00:54:44,920
ve skutečnosti má logickou hodnotu
, která byla obrátil pravda.

1073
00:54:44,920 --> 00:54:49,380
Takže pokud chceme vložit
slovo, zoo, do našeho slovníku,

1074
00:54:49,380 --> 00:54:51,770
jak bychom jít o tom, že?

1075
00:54:51,770 --> 00:54:55,960
Co musíme udělat, aby se ujistil, naše
počítač ví, že Z-O-O je slovo

1076
00:54:55,960 --> 00:54:58,130
a ne první slovo je Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> Diváků: [Neslyšitelné]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI PENG: Přesně tak, my
chcete, aby se ujistil, že tento

1079
00:55:01,450 --> 00:55:07,890
tady, že logická hodnota je
odškrtnout, že je to pravda.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, pak budeme kontrolovat, zda,
takže přesně víme, hej, zoo je slovo.

1081
00:55:13,297 --> 00:55:15,380
Chystám se říct,
Počítač, který je to slovo tak

1082
00:55:15,380 --> 00:55:18,000
že když je počítač kontroly,
ví, že zoo je slovo.

1083
00:55:18,000 --> 00:55:21,269
>> Vzhledem k tomu, vzpomenout na všechny tyto údaje
struktury, je to pro nás velmi snadné

1084
00:55:21,269 --> 00:55:22,310
říci, oh, netopýr je to slovo.

1085
00:55:22,310 --> 00:55:22,851
Zoo je to slovo.

1086
00:55:22,851 --> 00:55:23,611
Přiblížit to slovo.

1087
00:55:23,611 --> 00:55:25,860
Ale když jste ho staví,
počítač nemá ani ponětí.

1088
00:55:25,860 --> 00:55:28,619
>> Takže musíte to říct přesně
na jakém místě je to slovo?

1089
00:55:28,619 --> 00:55:29,910
V jakém okamžiku není to slovo?

1090
00:55:29,910 --> 00:55:31,784
A na jakém místě dělat já
je třeba hledat věci,

1091
00:55:31,784 --> 00:55:34,000
a na jakém místě se musím jít dál?

1092
00:55:34,000 --> 00:55:37,010
Každý jasné, že?

1093
00:55:37,010 --> 00:55:39,540
Bezva.

1094
00:55:39,540 --> 00:55:42,530
>> A tak pak přijde
Problém, jak by jsme se

1095
00:55:42,530 --> 00:55:45,560
jít o vložení něco
že to vlastně není?

1096
00:55:45,560 --> 00:55:49,090
Takže řekněme, že chceme vložit
Slovo, lázně, do našeho trie.

1097
00:55:49,090 --> 00:55:53,589
Jak vy můžete vidět, jako v současné době
všechno, co máme teď, je B-A-T,

1098
00:55:53,589 --> 00:55:55,630
a tato nová struktura dat
tam měl půllitr, který

1099
00:55:55,630 --> 00:55:59,740
poukázal na hodnotu null, protože předpokládáme,
že, oh, je tu po B-A-T žádná slova,

1100
00:55:59,740 --> 00:56:02,530
proč potřebujeme zachovat
mají věci po tomto T.

1101
00:56:02,530 --> 00:56:06,581
>> Problém však nastává, když budeme dělat vás
chtějí mít slovo, které přichází po

1102
00:56:06,581 --> 00:56:07,080
T je.

1103
00:56:07,080 --> 00:56:09,500
Pokud máte vanu, jste
bude chtít H právo.

1104
00:56:09,500 --> 00:56:13,290
A tak způsob, jakým budeme k tomu, že je
budeme vytvořit samostatný uzel.

1105
00:56:13,290 --> 00:56:16,840
Nejsme přidělit bez ohledu na částku,
paměti pro toto nové pole,

1106
00:56:16,840 --> 00:56:20,720
a budeme přiřadit ukazatele.

1107
00:56:20,720 --> 00:56:22,947
>> Budeme přiřadit
H, Za prvé, to null,

1108
00:56:22,947 --> 00:56:24,030
budeme zbavit.

1109
00:56:24,030 --> 00:56:26,590
Budeme mít
Bod H směrem dolů.

1110
00:56:26,590 --> 00:56:30,600
Pokud vidíme H, chceme ho
jít někam jinam.

1111
00:56:30,600 --> 00:56:33,910
>> Tady, pak můžeme odškrtnout ano.

1112
00:56:33,910 --> 00:56:38,170
Pokud bychom hit H po T, oh,
pak víme, že se jedná o slovo.

1113
00:56:38,170 --> 00:56:41,110
Boolean se chystá vrátit true.

1114
00:56:41,110 --> 00:56:42,950
Všichni jasné, o tom, jak se to stalo?

1115
00:56:42,950 --> 00:56:45,110
DOBŘE.

1116
00:56:45,110 --> 00:56:47,214
>> Takže v podstatě všechny
Tyto datové struktury

1117
00:56:47,214 --> 00:56:50,130
že jsme přešli dnes, jsem
opravdu, ale opravdu rychle pryč nad nimi

1118
00:56:50,130 --> 00:56:52,192
a ne v mnohem
detail, a to je v pořádku.

1119
00:56:52,192 --> 00:56:53,900
Jakmile začnete umazávání
s tím, budete

1120
00:56:53,900 --> 00:56:55,733
sledování, kde
Všechny ukazatele jsou,

1121
00:56:55,733 --> 00:56:58,060
co se děje ve vašem
datové struktury, a tak dále.

1122
00:56:58,060 --> 00:56:59,810
Budou velmi užitečné,
a je jen na vás,

1123
00:56:59,810 --> 00:57:03,890
kluci úplně zjistit, jak
Chcete-li implementovat věci.

1124
00:57:03,890 --> 00:57:07,650
>> A tak pset4, z 5-- oh, to je špatné.

1125
00:57:07,650 --> 00:57:10,140
Pset5 je překlepy.

1126
00:57:10,140 --> 00:57:13,710
Jak jsem již řekl dříve, budete, jakmile
Znovu, stáhněte zdrojový kód od nás.

1127
00:57:13,710 --> 00:57:16,210
Tam to bude Tři hlavní
věci, které budete stahovat.

1128
00:57:16,210 --> 00:57:18,470
Budete stáhnout slovníky,
KERS, a texty.

1129
00:57:18,470 --> 00:57:21,660
>> Všechny tyto věci jsou, jsou
buď slovníky slov

1130
00:57:21,660 --> 00:57:25,190
že chceme, abyste zkontrolovat
nebo test informací

1131
00:57:25,190 --> 00:57:26,930
že chceme, abyste kontrolu pravopisu.

1132
00:57:26,930 --> 00:57:29,670
A tak se slovníky
dáme jdete

1133
00:57:29,670 --> 00:57:34,870
aby vám aktuální slova, které chceme
ukládat nějak způsobem, který je

1134
00:57:34,870 --> 00:57:36,530
účinnější než pole.

1135
00:57:36,530 --> 00:57:38,470
A pak texty jsou
Bude to, co jsme

1136
00:57:38,470 --> 00:57:43,900
s žádostí o kontrolu pravopisu, aby se ujistil
všechna slova existují skutečné slova.

1137
00:57:43,900 --> 00:57:47,970
>> A tak tři bloky
programy, které dáme vám

1138
00:57:47,970 --> 00:57:51,130
se nazývají dictionary.c,
dictionary.h, a speller.c.

1139
00:57:51,130 --> 00:57:56,500
A tak všichni dictionary.c dělá, je
co jste vyzváni k realizaci.

1140
00:57:56,500 --> 00:57:57,880
To načte slova.

1141
00:57:57,880 --> 00:58:02,000
To kouzlo je zkontroluje, a to je jistý,
že vše je správně vložen.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h je jen soubor knihovny
že deklaruje všechny tyto funkce.

1143
00:58:05,180 --> 00:58:07,650
A speller.c, budeme dát.

1144
00:58:07,650 --> 00:58:09,290
Nemusíte měnit nic z toho.

1145
00:58:09,290 --> 00:58:14,290
Všechny speller.c dělá, je vzít to,
Zatížení to, kontroluje rychlost na to,

1146
00:58:14,290 --> 00:58:19,190
testuje měřítko jako jak
rychle jste schopni dělat věci.

1147
00:58:19,190 --> 00:58:20,410
>> Je to speller.

1148
00:58:20,410 --> 00:58:23,920
Prostě to není nepořádek s ním, ale udělat
se, že jste pochopili, co to dělá.

1149
00:58:23,920 --> 00:58:28,090
Používáme funkci nazvanou getrusage že
testuje výkon svého kouzla

1150
00:58:28,090 --> 00:58:28,590
checker.

1151
00:58:28,590 --> 00:58:32,200
Vše, co to dělá, je v podstatě otestování
Čas všechno ve vašem slovníku,

1152
00:58:32,200 --> 00:58:33,680
takže se ujistěte, jste to pochopili.

1153
00:58:33,680 --> 00:58:36,660
Buďte opatrní, aby nepořádek s ním, nebo
jinde se věci nebude fungovat správně.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> A Převážná část tohoto problému je pro
vy opravdu změnit dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Budeme vám
140.000 slov ve slovníku.

1157
00:58:48,526 --> 00:58:50,900
Budeme vám textu
soubor, který má tato slova,

1158
00:58:50,900 --> 00:58:54,840
a chceme, abyste byli schopni zorganizovat
je do tabulky hash nebo trie

1159
00:58:54,840 --> 00:58:58,140
protože když vás žádáme, aby bylo patrné
check-- představte si, že jste kouzlo

1160
00:58:58,140 --> 00:59:00,690
kontrola jako Homerovi Odysseia.

1161
00:59:00,690 --> 00:59:03,010
Je to jako obrovský, obrovský tento test.

1162
00:59:03,010 --> 00:59:05,190
>> Představte si, že každý
slovo, které se musel podívat

1163
00:59:05,190 --> 00:59:08,100
prostřednictvím řady 140.000 hodnot.

1164
00:59:08,100 --> 00:59:10,350
To by trvalo věčnost
pro váš počítač spustit.

1165
00:59:10,350 --> 00:59:14,490
To je důvod, proč chceme organizujeme
data do efektivnějších datových struktur

1166
00:59:14,490 --> 00:59:17,270
jako je například hashovací tabulky nebo trie.

1167
00:59:17,270 --> 00:59:20,700
A pak vy můžete druh
o při hledání přístupu

1168
00:59:20,700 --> 00:59:22,570
věci snadněji a rychleji.

1169
00:59:22,570 --> 00:59:24,934
>> A tak buďte opatrní na řešení kolizí.

1170
00:59:24,934 --> 00:59:27,350
Budeš mít spoustu
ze slov, která začínají A.

1171
00:59:27,350 --> 00:59:29,957
Budeš mít spoustu slov
že začít s B. Až do vás

1172
00:59:29,957 --> 00:59:31,290
chlapi, jak chcete ho řešit.

1173
00:59:31,290 --> 00:59:34,144
Možná, že tam je víc
efektivní funkce hash

1174
00:59:34,144 --> 00:59:36,810
než jen prvním písmenem
něco, a tak to je jen na vás

1175
00:59:36,810 --> 00:59:38,190
kluci druh dělat, co chcete.

1176
00:59:38,190 --> 00:59:40,148
>> Možná chcete přidat
všechny dopisy dohromady.

1177
00:59:40,148 --> 00:59:43,410
Možná chcete líbit dělat divné věci
na účet počtu písmen,

1178
00:59:43,410 --> 00:59:43,970
cokoliv.

1179
00:59:43,970 --> 00:59:45,386
Až vás kluci, jak chcete dělat.

1180
00:59:45,386 --> 00:59:49,262
Pokud si chcete udělat hash tabulky, pokud jste
chcete pokusit o Trie, zcela na vás.

1181
00:59:49,262 --> 00:59:52,470
Budu vás varovat předem, že
Trie je obvykle o něco složitější

1182
00:59:52,470 --> 00:59:54,520
jen proto, že je tu spousta
další ukazatele sledovat.

1183
00:59:54,520 --> 00:59:55,645
Ale zcela na vás kluci.

1184
00:59:55,645 --> 00:59:58,742
Je to mnohem efektivnější
ve většině případů.

1185
00:59:58,742 --> 01:00:01,450
Chcete-li být opravdu schopna udržet
přehled o všech vašich ukazatelů.

1186
01:00:01,450 --> 01:00:03,850
Jako udělat totéž
že jsem tady.

1187
01:00:03,850 --> 01:00:06,871
Když se snažíte vložit
Hodnoty do tabulky hash nebo odstranit,

1188
01:00:06,871 --> 01:00:08,620
ujistěte se, že jste
Opravdu sledování

1189
01:00:08,620 --> 01:00:11,860
kde je vše proto,
je to pro jestli jsem rychlé

1190
01:00:11,860 --> 01:00:14,727
pokoušíte vložit rád slovo, Andy.

1191
01:00:14,727 --> 01:00:16,810
Řekněme, že je to
skutečné slovo, slovo, andy,

1192
01:00:16,810 --> 01:00:19,640
do obří seznamu A slov.

1193
01:00:19,640 --> 01:00:22,450
>> Kdybych náhodou přeřadit
ukazatel špatně, oops,

1194
01:00:22,450 --> 01:00:24,940
tam jede celistvost
zbytek mého Google seznamu.

1195
01:00:24,940 --> 01:00:26,897
Teď jediné slovo, které jsem
mají, je Andy, a teď

1196
01:00:26,897 --> 01:00:29,230
všechny ostatní slova v
Slovník byly ztraceny.

1197
01:00:29,230 --> 01:00:31,370
A tak se chcete ujistit, že
sledovat všechny vaše ukazatelů

1198
01:00:31,370 --> 01:00:33,661
jinak budete mít
obrovské problémy v kódu.

1199
01:00:33,661 --> 01:00:35,840
Remíza věci pečlivě krok za krokem.

1200
01:00:35,840 --> 01:00:37,870
To dělá to mnohem jednodušší myslet.

1201
01:00:37,870 --> 01:00:40,910
>> A konečně, chcete být schopni
otestovat výkon vašeho programu

1202
01:00:40,910 --> 01:00:41,618
na velké desce.

1203
01:00:41,618 --> 01:00:43,710
Jestliže vy trvat
podívejte se na CS50 právě teď,

1204
01:00:43,710 --> 01:00:45,210
máme to, co se nazývá velký deska.

1205
01:00:45,210 --> 01:00:50,200
Je to skóre list nejrychlejší
kouzlo časů kontrolní napříč všemi CS50

1206
01:00:50,200 --> 01:00:55,720
právě teď, myslím, že na vrchol jako 10
Časy Myslím si, že osm z nich jsou zaměstnanci.

1207
01:00:55,720 --> 01:00:57,960
Opravdu chceme vy, aby nás porazil.

1208
01:00:57,960 --> 01:01:00,870
>> Každý z nás se snaží realizovat
nejrychlejší kód jak je to možné.

1209
01:01:00,870 --> 01:01:04,880
Chceme, aby si kluci, aby se pokusili napadnout
nás a realizovat rychleji, než my všichni

1210
01:01:04,880 --> 01:01:05,550
plechovka.

1211
01:01:05,550 --> 01:01:07,970
A tak to je opravdu
to poprvé, co jsme

1212
01:01:07,970 --> 01:01:12,680
dotazem vám kluci udělat pset který
si můžete opravdu dělat v jakékoliv metodě

1213
01:01:12,680 --> 01:01:13,760
chceš.

1214
01:01:13,760 --> 01:01:17,730
>> Vždycky říkám, to je více podobný
do reálného života řešení, ne?

1215
01:01:17,730 --> 01:01:19,550
Já říkám, hej, musíš to udělat.

1216
01:01:19,550 --> 01:01:21,380
Postavit program, který dělá to pro mě.

1217
01:01:21,380 --> 01:01:22,630
Udělej to však budete chtít.

1218
01:01:22,630 --> 01:01:24,271
Já jen vím, že chci, aby rychle.

1219
01:01:24,271 --> 01:01:25,770
To je vaše výzva pro tento týden.

1220
01:01:25,770 --> 01:01:27,531
Vy chlapi, jdeme
aby vám úkol.

1221
01:01:27,531 --> 01:01:29,030
Budeme vám výzvu.

1222
01:01:29,030 --> 01:01:31,559
A pak je to na vás kluci
úplně jen přijít na to,

1223
01:01:31,559 --> 01:01:34,100
co je nejrychlejší a nejvíce
účinný způsob, jak realizovat to.

1224
01:01:34,100 --> 01:01:34,600
To jo?

1225
01:01:34,600 --> 01:01:37,476
>> Diváků: Jsme dovoleno, pokud
chtěl vyhledejte rychlejší způsoby

1226
01:01:37,476 --> 01:01:40,821
dělat hash tabulky on-line, můžeme to udělat
že a citují kód někoho jiného?

1227
01:01:40,821 --> 01:01:42,070
ANDI PENG: Jo, úplně v pohodě.

1228
01:01:42,070 --> 01:01:44,320
Takže pokud vy přečíst
spec, je tu řada

1229
01:01:44,320 --> 01:01:48,310
v spec, který říká, že kluci
jsou zcela zdarma a vyhledejte hash

1230
01:01:48,310 --> 01:01:51,070
funkce na jaké jsou některé
z rychlejší hash funkce

1231
01:01:51,070 --> 01:01:54,720
běžet věci skrze as
dlouho, jak vám citovat, že kód.

1232
01:01:54,720 --> 01:01:57,220
Takže někteří lidé již
přišel na to, rychlé postupy

1233
01:01:57,220 --> 01:02:00,250
dělání překlepů, rychlého
způsoby ukládání informací.

1234
01:02:00,250 --> 01:02:02,750
Zcela na vás kluci, pokud vás
chtějí jen brát, že jo?

1235
01:02:02,750 --> 01:02:04,045
Ujistěte se, že jste s odvoláním.

1236
01:02:04,045 --> 01:02:06,170
Výzvou zde opravdu
že se snažíme testovat

1237
01:02:06,170 --> 01:02:09,750
je ujistit se, že víte,
svou cestu kolem ukazatele.

1238
01:02:09,750 --> 01:02:12,700
Tak daleko, jak se provádí
skutečné funkce hash

1239
01:02:12,700 --> 01:02:15,070
a přichází s podobně
matematika k tomu, že,

1240
01:02:15,070 --> 01:02:17,570
vy můžete výzkum cokoliv
metody on-line kluci chtějí.

1241
01:02:17,570 --> 01:02:17,996
To jo?

1242
01:02:17,996 --> 01:02:19,700
>> Diváků: Můžeme uvést jen
pomocí [neslyšitelných]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI PENG: Jo.

1244
01:02:20,120 --> 01:02:22,328
Stačí si jen, ve váš komentář,
můžete citovat jako, oh,

1245
01:02:22,328 --> 01:02:26,127
převzato z Yada, bla,
bla, hashovací funkce.

1246
01:02:26,127 --> 01:02:27,210
Každý, kdo má nějaké otázky?

1247
01:02:27,210 --> 01:02:29,694
Vlastně jsme breezed
úsekem dnes.

1248
01:02:29,694 --> 01:02:31,610
Budu se sem
odpovědět na otázky stejně.

1249
01:02:31,610 --> 01:02:36,570
>> Také, jak jsem řekl, kancelářské
hodin dnes večer a zítra.

1250
01:02:36,570 --> 01:02:40,307
Spec tento týden je vlastně
super snadné a super krátký číst.

1251
01:02:40,307 --> 01:02:43,140
Navrhoval bych, že pohled, jen
pročíst celé to.

1252
01:02:43,140 --> 01:02:45,730
>> A Zamyla vás vlastně procházky
přes každou z funkcí

1253
01:02:45,730 --> 01:02:49,796
budete muset implementovat, a tak je to
velmi, velmi jasné, jak to udělat všechno.

1254
01:02:49,796 --> 01:02:51,920
Jen aby se ujistil, že jste
sledování ukazatelů.

1255
01:02:51,920 --> 01:02:53,650
Jedná se o velmi náročný pset.

1256
01:02:53,650 --> 01:02:56,744
>> Není to náročné, protože rád,
oh, pojmy jsou tak mnohem více

1257
01:02:56,744 --> 01:02:59,160
obtížné, musíte se naučit
tak mnoho nového syntaxe cesta

1258
01:02:59,160 --> 01:03:00,650
že jste na poslední pset.

1259
01:03:00,650 --> 01:03:03,320
To pset je obtížné, protože
existuje tolik ukazatele,

1260
01:03:03,320 --> 01:03:06,980
a pak je to velmi, velmi snadné, jakmile
máte chybu v kódu nebudou moci

1261
01:03:06,980 --> 01:03:08,315
zjistit, kde, že chyba je.

1262
01:03:08,315 --> 01:03:13,200
>> A tak naprostý víru ve vás
chlapi, aby mohli porazit naše [neslyšitelných]

1263
01:03:13,200 --> 01:03:13,700
hláskování.

1264
01:03:13,700 --> 01:03:16,640
Já vlastně nemám žádný písemný důl
ještě, ale já jsem to psal já.

1265
01:03:16,640 --> 01:03:19,070
Takže zatímco píšete
vaše, budu psát moje.

1266
01:03:19,070 --> 01:03:21,070
Budu se snažit, aby
moje rychleji než vaše.

1267
01:03:21,070 --> 01:03:23,940
Uvidíme, kdo má nejrychlejší jeden.

1268
01:03:23,940 --> 01:03:27,340
>> A jo, budu vidět všechny
vy tady v úterý.

1269
01:03:27,340 --> 01:03:29,510
Budu spustit jakýsi se jako pset dílně.

1270
01:03:29,510 --> 01:03:32,640
Všechny sekcích tohoto
týden jsou pset dílny,

1271
01:03:32,640 --> 01:03:36,690
takže si kluci mají spoustu možností
o pomoc, úřední hodiny jako vždy,

1272
01:03:36,690 --> 01:03:41,330
a já se opravdu těším na
čtení všichni kódu vašich kluci.

1273
01:03:41,330 --> 01:03:44,160
Mám vyslýchá tady, pokud vás
kluci chtějí jít dostat ty.

1274
01:03:44,160 --> 01:03:45,880
To je vše.

1275
01:03:45,880 --> 01:03:48,180