1
00:00:00,000 --> 00:00:08,250

2
00:00:08,250 --> 00:00:12,680
>> JASON Hirschhorn: Vitajte všetci
k § Seven.

3
00:00:12,680 --> 00:00:15,040
Sme v týždni sedem kurze.

4
00:00:15,040 --> 00:00:18,440
A to nadchádzajúce štvrtok
je Halloween, takže som

5
00:00:18,440 --> 00:00:21,420
oblečený ako tekvica.

6
00:00:21,420 --> 00:00:23,460
Nemohol som sa ohnúť a dať na
moje topánky, takže to je dôvod, prečo som

7
00:00:23,460 --> 00:00:25,660
len v ponožkách.

8
00:00:25,660 --> 00:00:29,220
Som tiež na sebe nič pod
to, takže nemôžem dať dole, ak je to

9
00:00:29,220 --> 00:00:29,950
rušivo na vás.

10
00:00:29,950 --> 00:00:31,860
Vopred sa ospravedlňujem za to.

11
00:00:31,860 --> 00:00:33,170
Nemusíte si predstaviť,
čo sa deje.

12
00:00:33,170 --> 00:00:34,240
Mám na sebe trenírky.

13
00:00:34,240 --> 00:00:36,170
Takže je to všetko dobré.

14
00:00:36,170 --> 00:00:41,120
>> Mám dlhší príbeh o tom, prečo som
oblečený ako tekvica, ale budem

15
00:00:41,120 --> 00:00:45,110
okrem toho, že neskôr v tejto sekcii
pretože chcem, aby ste mohli začať.

16
00:00:45,110 --> 00:00:47,720
Máme veľa zaujímavých vecí
ísť na tento týždeň.

17
00:00:47,720 --> 00:00:51,810
Väčšina z nich sa priamo vzťahujú k tejto
týždeň problém set, pravopisné chyby.

18
00:00:51,810 --> 00:00:54,680
Chystáme sa ísť cez spojené
zoznamy a hash tabuľky

19
00:00:54,680 --> 00:00:57,160
za celý oddiel.

20
00:00:57,160 --> 00:01:02,490
Každý týždeň dal som tento zoznam sa, zoznam
prostriedky pre vás, aby vám pomohol s

21
00:01:02,490 --> 00:01:04,120
materiál na tomto kurze.

22
00:01:04,120 --> 00:01:07,600
Je-li na rozpakoch, alebo ak hľadáte pre niektoré
viac informácií, pozrite sa na jednu z

23
00:01:07,600 --> 00:01:09,930
Tieto zdroje.

24
00:01:09,930 --> 00:01:14,530
>> Opäť platí, že pset6 je preklepov,
tento týždeň pset.

25
00:01:14,530 --> 00:01:17,690
A to tiež povzbudzuje vás, a ja
Odporúčame vám, použiť iné

26
00:01:17,690 --> 00:01:20,320
prostriedky špeciálne pre tento pset.

27
00:01:20,320 --> 00:01:23,390
Najmä tri som
uvedené na obrazovke -

28
00:01:23,390 --> 00:01:27,160
gdb, ktorý sme boli oboznámení s
a bol s použitím na chvíľu teraz, je

29
00:01:27,160 --> 00:01:29,270
Bude veľmi užitočné tento týždeň.

30
00:01:29,270 --> 00:01:30,190
Tak som si dal, že až tu.

31
00:01:30,190 --> 00:01:32,910
Ale vždy, keď pracujete s C,
mali by ste byť vždy pomocou gdb do

32
00:01:32,910 --> 00:01:34,430
ladenie programov.

33
00:01:34,430 --> 00:01:36,660
Tento týždeň tiež Valgrind.

34
00:01:36,660 --> 00:01:38,535
Vie niekto, čo Valgrind robí?

35
00:01:38,535 --> 00:01:42,184

36
00:01:42,184 --> 00:01:43,890
>> DIVÁKOV: Kontroluje úniky pamäte?

37
00:01:43,890 --> 00:01:45,950
>> JASON Hirschhorn: Valgrind
kontroly tesnosti pamäti.

38
00:01:45,950 --> 00:01:49,970
Takže ak ste malloc niečo vo vašej
Program, sa pýtate na pamäti.

39
00:01:49,970 --> 00:01:52,920
Na konci programu, budete mať
písať zadarmo na všetko, čo ste

40
00:01:52,920 --> 00:01:54,800
malloced aby pamäti späť.

41
00:01:54,800 --> 00:01:58,420
Ak nechcete písať zadarmo na konci a
Váš program je dodávaný k záveru,

42
00:01:58,420 --> 00:02:00,000
všetko sa automaticky
byť oslobodený.

43
00:02:00,000 --> 00:02:02,340
A pre malé programy, je to
Nie je to veľký problém.

44
00:02:02,340 --> 00:02:05,250
Ale ak píšete dlhší beh
program, ktorý sa neukončí,

45
00:02:05,250 --> 00:02:09,180
nutne, za pár minút alebo
pár sekúnd, potom sa nevracia pamäť

46
00:02:09,180 --> 00:02:10,710
môže byť obrovský problém.

47
00:02:10,710 --> 00:02:14,940
>> Takže pset6, očakáva, že
budete mať nulovú pamäť úniky

48
00:02:14,940 --> 00:02:15,910
váš program.

49
00:02:15,910 --> 00:02:18,690
Ak chcete skontrolovať tesnosť pamäti, spustite Valgrind
a dám ti nejaký pekný

50
00:02:18,690 --> 00:02:21,190
výstup vám vedieť, či
alebo nie všetko bolo zadarmo.

51
00:02:21,190 --> 00:02:23,940
Budeme cvičiť s ním neskôr
dnes, dúfajme.

52
00:02:23,940 --> 00:02:25,790
>> Konečne, príkaz diff.

53
00:02:25,790 --> 00:02:28,900
Použili ste niečo podobné na to
v pset5 s Peek nástroja.

54
00:02:28,900 --> 00:02:30,780
Povolené môžete sa pozrieť dovnútra.

55
00:02:30,780 --> 00:02:33,400
Môžete tiež použiť diff, taky, za
problém nastaviť špec.

56
00:02:33,400 --> 00:02:35,950
Ale nechá vás
porovnať dva súbory.

57
00:02:35,950 --> 00:02:39,180
Dalo by sa porovnať rastrový súbor a
info hlavičky riešenia zamestnancov a

58
00:02:39,180 --> 00:02:42,200
vaše riešenie v pset5 ak
ste sa rozhodli použiť.

59
00:02:42,200 --> 00:02:44,030
Rozdiel vám umožní
to, že rovnako.

60
00:02:44,030 --> 00:02:48,620
Môžete porovnať správnu odpoveď na
tento týždeň problém nastavená na vašu odpoveď

61
00:02:48,620 --> 00:02:52,210
a sledujte, či sa zoradia alebo pozri
kde sú chyby.

62
00:02:52,210 --> 00:02:55,870
>> Tak to sú tri dobré nástroje, ktoré
by ste mali použiť pre tento týždeň, a

63
00:02:55,870 --> 00:02:58,130
určite skontrolujte svoj program
s týmito tromi nástrojmi

64
00:02:58,130 --> 00:03:00,520
než ju dovnútra

65
00:03:00,520 --> 00:03:04,650
Opäť, ako som sa už zmienil každý týždeň,
Ak máte akúkoľvek spätnú väzbu pre mňa - ako

66
00:03:04,650 --> 00:03:06,470
pozitívny a konštruktívny -

67
00:03:06,470 --> 00:03:09,930
neváhajte a zamierte na webové stránky
v spodnej časti tohto snímku

68
00:03:09,930 --> 00:03:11,270
a vstup je tam.

69
00:03:11,270 --> 00:03:13,440
Naozaj si toho vážim akékoľvek
a všetky spätnej väzby.

70
00:03:13,440 --> 00:03:17,360
A keď mi dáš konkrétne veci, ktoré
Môžem urobiť pre zlepšenie, alebo, že som

71
00:03:17,360 --> 00:03:21,350
robí dobre, že ste ma chceli
pokračovať, beriem k srdcu a

72
00:03:21,350 --> 00:03:24,040
naozaj snažiť počúvať
na Váš názor.

73
00:03:24,040 --> 00:03:27,720
Nemôžem sľúbiť, že budem robiť
všetko, aj keď, ako na sebe

74
00:03:27,720 --> 00:03:30,700
tekvica kostým každý týždeň.

75
00:03:30,700 --> 00:03:34,020
>> Takže budeme tráviť väčšinu
časť, ako som už spomenul, hovorí o

76
00:03:34,020 --> 00:03:37,240
spojové zoznamy a hashovacie tabuľky, z ktorých
budú priamo použiteľná pre

77
00:03:37,240 --> 00:03:38,780
problém nastaviť tento týždeň.

78
00:03:38,780 --> 00:03:42,580
Spojové zoznamy pôjdeme cez relatívne
rýchlo, pretože sme strávili trochu kusavou

79
00:03:42,580 --> 00:03:44,930
času, bude cez to v reze.

80
00:03:44,930 --> 00:03:48,680
A tak sa dostaneme priamo do
kódovanie problémy spojových zoznamov.

81
00:03:48,680 --> 00:03:52,740
A potom na konci budeme hovoriť o tom,
hash tabuľky a ako sa tento

82
00:03:52,740 --> 00:03:55,280
týždeň problém nastaviť.

83
00:03:55,280 --> 00:03:57,560
>> Vy ste videl tento kód.

84
00:03:57,560 --> 00:04:02,730
To je struct, a definuje
niečo nové, tzv uzol.

85
00:04:02,730 --> 00:04:10,660
A v uzle je celé číslo
tu a tam je ukazovateľ na

86
00:04:10,660 --> 00:04:11,830
iný uzol.

87
00:04:11,830 --> 00:04:12,790
Už sme videli to.

88
00:04:12,790 --> 00:04:14,830
To bolo prísť na
Pár teraz týždňov.

89
00:04:14,830 --> 00:04:18,680
To kombinuje ukazovatele, ktoré sme boli
prácu s, a štruktúr, ktoré umožňujú

90
00:04:18,680 --> 00:04:22,079
nám spojiť dva rôzne
veci do jedného dátového typu.

91
00:04:22,079 --> 00:04:24,830

92
00:04:24,830 --> 00:04:26,490
>> Je tu veľa deje na obrazovke.

93
00:04:26,490 --> 00:04:30,220
Ale to by malo byť relatívne
oboznámení s vami.

94
00:04:30,220 --> 00:04:33,810
Na prvom riadku sme
vyhlásiť nový uzol.

95
00:04:33,810 --> 00:04:41,650
A potom sa v tomto novom uzle, nastaviť
celé číslo sa tým, že k jednému uzlu.

96
00:04:41,650 --> 00:04:44,950
Vidíme na ďalšom riadku robím
printf príkaz, ale ja som sivo

97
00:04:44,950 --> 00:04:48,080
príkaz printf, pretože naozaj
Dôležitou súčasťou je táto linka tu -

98
00:04:48,080 --> 00:04:50,020
new_node.n.

99
00:04:50,020 --> 00:04:51,270
Čo bodka znamená?

100
00:04:51,270 --> 00:04:53,810

101
00:04:53,810 --> 00:04:57,240
>> DIVÁKOV: Choďte do uzla a
posúdiť n hodnotu pre neho.

102
00:04:57,240 --> 00:04:58,370
>> JASON Hirschhorn: To je
Presne tak.

103
00:04:58,370 --> 00:05:03,300
Dot znamená, že prístup k N part
tohto nového uzla.

104
00:05:03,300 --> 00:05:05,690
Tento ďalší riadok čo robí?

105
00:05:05,690 --> 00:05:16,140

106
00:05:16,140 --> 00:05:17,050
Michael.

107
00:05:17,050 --> 00:05:21,910
>> DIVÁKOV: Vytvára ďalšie uzol
ktorá bude ukazovať na nový uzol.

108
00:05:21,910 --> 00:05:24,870
>> JASON Hirschhorn: Takže to nie je
vytvoriť nový uzol.

109
00:05:24,870 --> 00:05:26,120
Vytvára čo?

110
00:05:26,120 --> 00:05:28,300

111
00:05:28,300 --> 00:05:29,300
>> DIVÁKOV: ukazovateľ.

112
00:05:29,300 --> 00:05:33,460
>> JASON Hirschhorn: ukazovateľ na uzol,
ako je uvedené v tomto uzle * tú.

113
00:05:33,460 --> 00:05:34,800
Takže to vytvára ukazovateľ na uzol.

114
00:05:34,800 --> 00:05:37,490
A ktorý uzol je smerujúca
k, Michael?

115
00:05:37,490 --> 00:05:38,440
>> DIVÁKOV: Nový uzol?

116
00:05:38,440 --> 00:05:39,240
>> JASON Hirschhorn: Nový uzol.

117
00:05:39,240 --> 00:05:43,020
A to je ukázal, že preto, že sme
vzhľadom k tomu adresu nového uzla.

118
00:05:43,020 --> 00:05:45,820
A teraz v tomto riadku vidíme
dva rôzne spôsoby

119
00:05:45,820 --> 00:05:46,910
vyjadruje rovnakú vec.

120
00:05:46,910 --> 00:05:49,650
A chcel som poukázať na to, ako tieto
dve veci sú rovnaké.

121
00:05:49,650 --> 00:05:54,740
V prvom riadku, dereferencia sme
ukazovateľ.

122
00:05:54,740 --> 00:05:55,830
Tak ideme do uzla.

123
00:05:55,830 --> 00:05:56,830
To je to, čo táto hviezda znamená.

124
00:05:56,830 --> 00:05:57,930
Videli sme, že predtým, než s ukazovateľmi.

125
00:05:57,930 --> 00:05:59,280
Prejsť na tomto uzle.

126
00:05:59,280 --> 00:06:00,370
To je v zátvorkách.

127
00:06:00,370 --> 00:06:04,610
A potom prístup cez operátora dot
n element tohto uzla.

128
00:06:04,610 --> 00:06:08,430
>> Takže to berie syntax
sme tu a teraz videl,

129
00:06:08,430 --> 00:06:09,670
použitie s ukazovateľom.

130
00:06:09,670 --> 00:06:13,730
Samozrejme, že to bude dosť práce, ak
píšete tie zátvorky -

131
00:06:13,730 --> 00:06:14,940
že hviezdy a bodka.

132
00:06:14,940 --> 00:06:16,220
To je trochu zaneprázdnený.

133
00:06:16,220 --> 00:06:18,500
Takže máme nejaký syntaktický cukor.

134
00:06:18,500 --> 00:06:19,920
A tento riadok tu -

135
00:06:19,920 --> 00:06:21,170
ptr_node-> n

136
00:06:21,170 --> 00:06:25,400

137
00:06:25,400 --> 00:06:28,000
To robí presne rovnaký vec.

138
00:06:28,000 --> 00:06:30,840
Takže tieto dva riadky kódu sú
rovnocenné, a bude robiť

139
00:06:30,840 --> 00:06:31,650
presne to isté.

140
00:06:31,650 --> 00:06:34,210
>> Ale chcel by som upozorniť tých, pred
pôjdeme ďalej, takže chápete

141
00:06:34,210 --> 00:06:39,000
že naozaj to, čo tu je
len syntaktický cukor pre dereferencing

142
00:06:39,000 --> 00:06:44,200
ukazovateľ a potom ísť na
n časť tohto struct.

143
00:06:44,200 --> 00:06:45,525
Máte otázky k tomuto snímku?

144
00:06:45,525 --> 00:06:53,020

145
00:06:53,020 --> 00:06:54,390
OK.

146
00:06:54,390 --> 00:06:58,510
>> Takže ideme prejsť pár
operácií, ktoré môžete urobiť na

147
00:06:58,510 --> 00:06:59,730
spojové zoznamy.

148
00:06:59,730 --> 00:07:05,770
Spájať zoznam, odvolanie, je rad
uzly, ktoré ukazujú na seba.

149
00:07:05,770 --> 00:07:12,470
A my sme zvyčajne začínajú s ukazovateľom
volal hlava, všeobecne, že poukazuje na

150
00:07:12,470 --> 00:07:14,040
Prvá vec, ktorú v zozname.

151
00:07:14,040 --> 00:07:18,900
Takže na prvom riadku tady sme
najprv náš pôvodný L.

152
00:07:18,900 --> 00:07:21,370
Takže to, čo si môžete myslieť - to
text, tu si môžete myslieť, ako

153
00:07:21,370 --> 00:07:23,560
len ukazovateľ máme uložené
niekde, že body

154
00:07:23,560 --> 00:07:24,670
na prvý prvok.

155
00:07:24,670 --> 00:07:27,500
A v tomto prepojenom zoznamu
máme štyri uzly.

156
00:07:27,500 --> 00:07:29,530
Každý uzol je veľký box.

157
00:07:29,530 --> 00:07:33,430
Väčší box vnútri veľkej
box je celá časť.

158
00:07:33,430 --> 00:07:37,400
A potom máme ukazovateľ časť.

159
00:07:37,400 --> 00:07:39,630
>> Tieto boxy nie sú vypracované na
mierka, pretože, ako veľký je

160
00:07:39,630 --> 00:07:42,320
celé číslo v bytoch?

161
00:07:42,320 --> 00:07:43,290
Ako teraz veľký?

162
00:07:43,290 --> 00:07:43,710
Štyri.

163
00:07:43,710 --> 00:07:45,470
A aká veľká je ukazovateľ?

164
00:07:45,470 --> 00:07:45,940
Štyri.

165
00:07:45,940 --> 00:07:48,180
Takže naozaj, keď sme sa k tomu
toto meradlo obe políčka

166
00:07:48,180 --> 00:07:49,690
by mať rovnakú veľkosť.

167
00:07:49,690 --> 00:07:52,870
V tomto prípade, chceme vložiť
niečo do prepojeného zoznamu.

168
00:07:52,870 --> 00:07:57,190
Takže môžete vidieť tu dole sme vkladanie
päť sme prejsť cez

169
00:07:57,190 --> 00:08:01,310
spájať zoznam, zistiť, kde päť
ide, a potom ju zasuňte.

170
00:08:01,310 --> 00:08:03,560
>> Poďme sa zlomiť to dole a ísť
trochu pomalšie.

171
00:08:03,560 --> 00:08:05,510
Budem poukázať na doske.

172
00:08:05,510 --> 00:08:09,930
Takže máme päť uzol, ktorý
sme vytvorili v mallocs.

173
00:08:09,930 --> 00:08:11,190
Prečo sa všetci smiať?

174
00:08:11,190 --> 00:08:12,130
Len si robím srandu.

175
00:08:12,130 --> 00:08:13,310
OK.

176
00:08:13,310 --> 00:08:14,820
Takže sme malloced päť.

177
00:08:14,820 --> 00:08:16,310
Vytvorili sme tento uzol
niekde inde.

178
00:08:16,310 --> 00:08:17,740
Musíme je pripravená ísť.

179
00:08:17,740 --> 00:08:20,130
Začneme na prednej strane
náš zoznam s dvoma.

180
00:08:20,130 --> 00:08:22,380
A chceme vložiť
na triedený móde.

181
00:08:22,380 --> 00:08:27,550
>> Takže ak vidíme dva a chceme, aby
v päť, čo budeme robiť, keď vidíme,

182
00:08:27,550 --> 00:08:28,800
niečo menej ako my?

183
00:08:28,800 --> 00:08:31,850

184
00:08:31,850 --> 00:08:33,520
Čo je?

185
00:08:33,520 --> 00:08:36,750
Chceme vložiť päť do tejto
spájať zoznam, zachovaním radené.

186
00:08:36,750 --> 00:08:37,520
Vidíme číslo dva.

187
00:08:37,520 --> 00:08:38,769
Tak čo budeme robiť?

188
00:08:38,769 --> 00:08:39,179
Marcus?

189
00:08:39,179 --> 00:08:40,679
>> DIVÁKOV: Zavolajte ukazovateľ
k ďalšiemu uzlu.

190
00:08:40,679 --> 00:08:42,530
>> JASON Hirschhorn: A prečo
ideme na ten budúci?

191
00:08:42,530 --> 00:08:45,970
>> DIVÁKOV: Vzhľadom k tomu, že je to
ďalší uzol v zozname.

192
00:08:45,970 --> 00:08:48,310
A my len vieme, že iné umiestnenie.

193
00:08:48,310 --> 00:08:50,410
>> JASON Hirschhorn: A päť je väčšia
ako dva, a to najmä.

194
00:08:50,410 --> 00:08:51,600
Pretože chceme, aby to zoradené.

195
00:08:51,600 --> 00:08:52,730
Takže päť je väčšia ako dva.

196
00:08:52,730 --> 00:08:54,460
Tak sme sa presunúť na ďalšie.

197
00:08:54,460 --> 00:08:55,240
A teraz sa dostaneme štyri.

198
00:08:55,240 --> 00:08:56,490
A čo sa stane, keď sa dostaneme štyri?

199
00:08:56,490 --> 00:08:58,920

200
00:08:58,920 --> 00:09:00,310
>> Five je väčší ako štyri.

201
00:09:00,310 --> 00:09:01,460
Tak sme ďalej.

202
00:09:01,460 --> 00:09:03,110
A teraz sme v šesť.

203
00:09:03,110 --> 00:09:04,360
A čo vidíme v šesť?

204
00:09:04,360 --> 00:09:08,672

205
00:09:08,672 --> 00:09:09,608
Áno, Carlos?

206
00:09:09,608 --> 00:09:10,544
>> DIVÁKOV: Šesť je väčšia ako päť.

207
00:09:10,544 --> 00:09:11,480
>> JASON Hirschhorn: Šesť je
väčší ako päť.

208
00:09:11,480 --> 00:09:13,660
Tak to je miesto, kde chceme
vložiť päť.

209
00:09:13,660 --> 00:09:17,320
Avšak, majte na pamäti, že ak by sme
majú iba jeden ukazovateľ tu -

210
00:09:17,320 --> 00:09:19,840
To je náš ďalší ukazovateľ, ktorý je
prechádzajúcej cez zoznamu.

211
00:09:19,840 --> 00:09:21,860
A my sme ukázal na šesť.

212
00:09:21,860 --> 00:09:25,010
Stratili sme stopu z čoho
prichádza pred šiestou.

213
00:09:25,010 --> 00:09:29,130
Takže ak chceme vložiť niečo do
tento zoznam udržiavať ju radené sme

214
00:09:29,130 --> 00:09:31,630
pravdepodobne potrebovať koľko rád?

215
00:09:31,630 --> 00:09:32,280
>> DIVÁKOV: Two.

216
00:09:32,280 --> 00:09:32,920
>> JASON HIRSCHORN: Two.

217
00:09:32,920 --> 00:09:35,720
Jeden sledovať aktuálne
jeden a sledovať

218
00:09:35,720 --> 00:09:37,050
ten predchádzajúci.

219
00:09:37,050 --> 00:09:38,450
Toto je iba jednotlivo spájať zoznam.

220
00:09:38,450 --> 00:09:39,670
Je to len ide jedným smerom.

221
00:09:39,670 --> 00:09:43,220
Keby sme mali dvojnásobne spájať zoznam, kde
všetko ukazoval na vec

222
00:09:43,220 --> 00:09:46,240
po ňom a vec pred ním, potom
nebudeme musieť robiť, že.

223
00:09:46,240 --> 00:09:49,350
Ale v tomto prípade nechceme stratiť
track z toho, čo prišli pred nami v prípade,

224
00:09:49,350 --> 00:09:53,350
musíme vložiť päť niekde
v stredu.

225
00:09:53,350 --> 00:09:55,610
Povedzme, že sme boli vkladanie deväť.

226
00:09:55,610 --> 00:09:57,260
Čo sa stane, keď
sme sa dostali na osem?

227
00:09:57,260 --> 00:10:01,860

228
00:10:01,860 --> 00:10:04,880
>> DIVÁKOV: Museli by ste
dostať, že nulový bod.

229
00:10:04,880 --> 00:10:07,820
Namiesto toho, aby nulový bod budeš mať
pridať prvok a potom

230
00:10:07,820 --> 00:10:09,216
že poukazujú na deväť.

231
00:10:09,216 --> 00:10:09,700
>> JASON HIRSCHORN: Presne tak.

232
00:10:09,700 --> 00:10:10,600
Tak dostaneme osem.

233
00:10:10,600 --> 00:10:13,140
Dostávame sa na koniec zoznamu, pretože
to ukazuje na hodnotu null.

234
00:10:13,140 --> 00:10:16,330
A teraz, namiesto toho, aby to poukázať na
null to máme poukázať na našom novom uzle.

235
00:10:16,330 --> 00:10:19,870
A nastavíme ukazovateľ
náš nový uzol na hodnotu null.

236
00:10:19,870 --> 00:10:21,445
Má niekto nejaké otázky,
o vkladanie?

237
00:10:21,445 --> 00:10:25,620

238
00:10:25,620 --> 00:10:28,100
Čo keď nemám starať o
vedenie zoznamu radené?

239
00:10:28,100 --> 00:10:31,701

240
00:10:31,701 --> 00:10:34,350
>> DIVÁKOV: Stick to na
začiatok alebo koniec.

241
00:10:34,350 --> 00:10:35,510
>> JASON HIRSCHORN: Stick to na
začiatok alebo koniec.

242
00:10:35,510 --> 00:10:37,276
Ktorý z nich by sme mali robiť?

243
00:10:37,276 --> 00:10:38,770
Bobby?

244
00:10:38,770 --> 00:10:41,020
Prečo koniec?

245
00:10:41,020 --> 00:10:43,250
>> DIVÁKOV: Vzhľadom k tomu, začiatok
je už naplnená.

246
00:10:43,250 --> 00:10:43,575
>> JASON HIRSCHORN: OK.

247
00:10:43,575 --> 00:10:44,360
Začiatok je už naplnená.

248
00:10:44,360 --> 00:10:46,090
Kto chce argumentovať proti Bobbymu.

249
00:10:46,090 --> 00:10:47,290
Marcus.

250
00:10:47,290 --> 00:10:48,910
>> DIVÁKOV: No pravdepodobne budete chcieť
držať ju na začiatku, pretože

251
00:10:48,910 --> 00:10:50,140
inak, ak si to dať na
Koniec ste museli

252
00:10:50,140 --> 00:10:51,835
prechádzať celý zoznam.

253
00:10:51,835 --> 00:10:52,990
>> JASON HIRSCHORN: Presne tak.

254
00:10:52,990 --> 00:10:57,970
Takže ak budeme premýšľať o behu,
runtime vloženie na konci

255
00:10:57,970 --> 00:11:00,110
by n, veľkosť.

256
00:11:00,110 --> 00:11:03,080
Čo je to veľký O runtime vloženie
na začiatku?

257
00:11:03,080 --> 00:11:04,170
Konštantný čas.

258
00:11:04,170 --> 00:11:07,075
Takže ak nechcete starať o udržanie
niečo ďalej, oveľa lepšie, len

259
00:11:07,075 --> 00:11:08,420
vložiť na začiatku tohto zoznamu.

260
00:11:08,420 --> 00:11:10,320
A to možno vykonať v konštantnom čase.

261
00:11:10,320 --> 00:11:13,900

262
00:11:13,900 --> 00:11:14,690
>> OK.

263
00:11:14,690 --> 00:11:18,870
Ďalšie operácie je nájsť, ktoré ďalšie -
sme formulovali to ako hľadanie.

264
00:11:18,870 --> 00:11:22,470
Ale my ideme prezrieť
spájať zoznam z nejakého objektu.

265
00:11:22,470 --> 00:11:26,000
Vy ste videli kód
hľadať ešte v prednáške.

266
00:11:26,000 --> 00:11:29,490
Ale my sme tak nejako práve urobil to s
vložiť, alebo aspoň vkladanie

267
00:11:29,490 --> 00:11:30,580
niečo ďalej.

268
00:11:30,580 --> 00:11:36,350
Môžete prezrieť, bude uzol uzla,
kým nenájdete číslo, že ste

269
00:11:36,350 --> 00:11:37,780
hľadať.

270
00:11:37,780 --> 00:11:39,670
Čo sa stane, keď sa dostanete
koniec zoznamu?

271
00:11:39,670 --> 00:11:43,020
Povedz Hľadám deväť a ja
dostať sa na koniec zoznamu.

272
00:11:43,020 --> 00:11:44,270
Čo budeme robiť?

273
00:11:44,270 --> 00:11:47,147

274
00:11:47,147 --> 00:11:48,110
>> DIVÁKOV: return false?

275
00:11:48,110 --> 00:11:48,690
>> JASON HIRSCHORN: Návrat false.

276
00:11:48,690 --> 00:11:49,960
Nenašli sme ju.

277
00:11:49,960 --> 00:11:52,010
Ak sa dostanete na koniec zoznamu a
ste nenašli číslo, ktoré ste

278
00:11:52,010 --> 00:11:54,170
hľadá, nie je to tam.

279
00:11:54,170 --> 00:11:55,420
Akékoľvek otázky týkajúce sa nájsť?

280
00:11:55,420 --> 00:11:59,530

281
00:11:59,530 --> 00:12:04,615
Ak to bolo zoradený zoznam, čo by
byť pre naše vyhľadávanie?

282
00:12:04,615 --> 00:12:07,370

283
00:12:07,370 --> 00:12:08,103
Jo.

284
00:12:08,103 --> 00:12:10,600
>> DIVÁKOV: To nájde prvú hodnotu
to je väčšia ako jedna

285
00:12:10,600 --> 00:12:12,390
hľadáte a
potom sa vrátiť false.

286
00:12:12,390 --> 00:12:13,190
>> JASON HIRSCHORN: Presne tak.

287
00:12:13,190 --> 00:12:17,310
Takže ak je to zoradený zoznam, ak sa dostaneme do
niečo, čo je väčšie ako to, čo

288
00:12:17,310 --> 00:12:20,180
sme hľadali, nepotrebujeme, aby
pokračuj na koniec zoznamu.

289
00:12:20,180 --> 00:12:24,060
Môžeme v tomto bode vráti false
pretože nebudeme ho nájsť.

290
00:12:24,060 --> 00:12:27,340
Otázkou je teraz, sme hovorili o
vedenie prepojené zoznamy radené,

291
00:12:27,340 --> 00:12:28,180
ich udržiavanie netriedený.

292
00:12:28,180 --> 00:12:30,050
To bude niečo, čo ste
pravdepodobne bude musieť premýšľať o tom,

293
00:12:30,050 --> 00:12:34,240
pri kódovaní problém nastaviť päť, ak
vybrať hash tabuľku s samostatný

294
00:12:34,240 --> 00:12:36,360
reťazenie prístup, ktorý
budeme hovoriť o neskôr.

295
00:12:36,360 --> 00:12:41,400
>> Ale je to stojí za to, aby sa zoznam
triedeného a potom budú môcť možno mať

296
00:12:41,400 --> 00:12:42,310
rýchlejšie vyhľadávanie?

297
00:12:42,310 --> 00:12:47,220
Alebo je lepšie rýchlo vloženie
niečo v neustálom behu, ale potom

298
00:12:47,220 --> 00:12:48,430
majú už hľadáte?

299
00:12:48,430 --> 00:12:52,250
To je jedna z vecí, tu, že vám
dostať sa rozhodnúť, čo je vhodnejšie,

300
00:12:52,250 --> 00:12:53,590
pre váš konkrétny problém.

301
00:12:53,590 --> 00:12:56,680
A tam to nemusí byť nutne jedným
úplne správna odpoveď.

302
00:12:56,680 --> 00:12:59,520
Ale je to určite rozhodnutie, ktoré sa
aby sa, a asi dobre brániť

303
00:12:59,520 --> 00:13:05,270
že, povedzme, komentár alebo dva, prečo
ste si vybrali jeden cez druhého.

304
00:13:05,270 --> 00:13:06,490
>> A konečne, mazanie.

305
00:13:06,490 --> 00:13:08,100
Videli sme mazanie.

306
00:13:08,100 --> 00:13:09,180
Je to podobné, ako hľadať.

307
00:13:09,180 --> 00:13:11,020
Hľadáme prvku.

308
00:13:11,020 --> 00:13:12,390
Povedzme, že sa snažíme odstrániť šesť.

309
00:13:12,390 --> 00:13:14,450
Tak nájdeme šesť tady.

310
00:13:14,450 --> 00:13:18,860
Ide o to, že sa musíme uistiť, že sme
urobiť, je, že čokoľvek sa ukazuje na

311
00:13:18,860 --> 00:13:21,220
šesť - ako vidíme v kroku
dva tu dole -

312
00:13:21,220 --> 00:13:26,500
bez ohľadu na to ukázal na šesť potreby na
preskočiť šesť teraz a byť zmenený na

313
00:13:26,500 --> 00:13:28,160
čo šesť je ukazuje.

314
00:13:28,160 --> 00:13:31,410
Nechceme, aby vôbec ojedinelé ochorenia zvyšok
náš zoznam by zabudol nastaviť, aby

315
00:13:31,410 --> 00:13:32,960
predchádzajúci ukazovateľ.

316
00:13:32,960 --> 00:13:35,960
A potom niekedy, v závislosti
na programe, ale budem len

317
00:13:35,960 --> 00:13:37,380
odstrániť úplne tento uzol.

318
00:13:37,380 --> 00:13:40,135
Niekedy sa budete chcieť vrátiť
hodnota, ktorá je v tomto uzle.

319
00:13:40,135 --> 00:13:42,490
Tak to je, ako funguje mazanie.

320
00:13:42,490 --> 00:13:44,610
Akékoľvek otázky týkajúce sa zmazať?

321
00:13:44,610 --> 00:13:51,280

322
00:13:51,280 --> 00:13:53,850
>> DIVÁKOV: Takže ak sa chystáte odstrániť
to by ste stačí použiť zadarmo, pretože

323
00:13:53,850 --> 00:13:55,655
pravdepodobne to bolo malloced?

324
00:13:55,655 --> 00:13:57,976
>> JASON HIRSCHORN: Ak chcete uvoľniť
niečo, čo je úplne v poriadku a vy

325
00:13:57,976 --> 00:13:58,540
malloced to.

326
00:13:58,540 --> 00:14:00,410
Povedzme, že sme sa chceli vrátiť túto hodnotu.

327
00:14:00,410 --> 00:14:04,010
Mohli by sme sa vrátiť šesť a potom zadarmo
tento uzol a volania zadarmo na neho.

328
00:14:04,010 --> 00:14:06,180
Alebo by sme snáď volať zadarmo prvý
a potom sa vrátiť šesť.

329
00:14:06,180 --> 00:14:11,210

330
00:14:11,210 --> 00:14:11,580
>> OK.

331
00:14:11,580 --> 00:14:14,010
Takže poďme sa presunúť na prax kódovanie.

332
00:14:14,010 --> 00:14:16,090
Budeme kódovať tri funkcie.

333
00:14:16,090 --> 00:14:18,260
Prvý z nich sa nazýva insert_node.

334
00:14:18,260 --> 00:14:22,170
Takže máte kód, ktorý som zaslané e-mailom vás, a
ak sledujete neskôr na to

335
00:14:22,170 --> 00:14:28,020
môžete pristupovať ku kódu v linked.c
na internetových stránkach CS50.

336
00:14:28,020 --> 00:14:30,880
Ale v linked.c, tam je nejaký
kostra kód, ktorý je už

337
00:14:30,880 --> 00:14:32,280
bola napísaná pre vás.

338
00:14:32,280 --> 00:14:34,560
A potom je tu pár FUNKCIE
musíte napísať.

339
00:14:34,560 --> 00:14:36,380
>> Najprv ideme do
napísať insert_node.

340
00:14:36,380 --> 00:14:39,800
A čo robí insert_node
znamená vloží číslo.

341
00:14:39,800 --> 00:14:42,440
A dávate celé číslo
do prepojeného zoznamu.

342
00:14:42,440 --> 00:14:45,470
A najmä, budete potrebovať
udržať zoznamu zoradené

343
00:14:45,470 --> 00:14:47,650
od najmenšieho po najväčšie.

344
00:14:47,650 --> 00:14:51,360
Tiež nechcete, aby
vložte všetky duplikáty.

345
00:14:51,360 --> 00:14:54,600
V neposlednom rade, ako môžete vidieť insert_node
vracia bool.

346
00:14:54,600 --> 00:14:57,140
Takže ste mal dať užívateľovi vedieť
či je alebo nie je insert

347
00:14:57,140 --> 00:15:00,800
úspešný vrátením true alebo false.

348
00:15:00,800 --> 00:15:02,580
Na konci tohto programu -

349
00:15:02,580 --> 00:15:05,750
a pre túto fázu nemusíte
sa starať o uvoľnenie čokoľvek.

350
00:15:05,750 --> 00:15:11,790
Takže všetko, čo robíte, je prijatie celé číslo
a vloženie do zoznamu.

351
00:15:11,790 --> 00:15:13,890
>> To je to, čo sa pýtam vás robiť teraz.

352
00:15:13,890 --> 00:15:17,620
Opäť platí, že v linked.c, ktoré
všetci majú, je kostra kódu.

353
00:15:17,620 --> 00:15:20,980
A mali by ste vidieť na spodnej časti
Deklarácia funkcie vzorky.

354
00:15:20,980 --> 00:15:27,390
Avšak predtým, než ísť do jeho kódovania
v C, vrelo odporúčame vám ísť

355
00:15:27,390 --> 00:15:29,330
jednotlivými krokmi sme boli
cvičiť každý týždeň.

356
00:15:29,330 --> 00:15:31,100
Už sme prešli
obraz toho.

357
00:15:31,100 --> 00:15:33,380
Takže by ste mali mať nejaké znalosti
o tom, ako to funguje.

358
00:15:33,380 --> 00:15:36,590
Ale ja by som povzbudiť vás písať
niektoré pseudokódu pred potápaním palcov

359
00:15:36,590 --> 00:15:38,640
A ideme prejsť
pseudokódu ako skupina.

360
00:15:38,640 --> 00:15:41,470
A potom, akonáhle ste napísali svoj
pseudokódu, a akonáhle ste napísali naši

361
00:15:41,470 --> 00:15:45,850
pseudokódu ako skupiny, môžete
ísť na to kódovanie v C.

362
00:15:45,850 --> 00:15:49,980
>> Ako heads up, funkcia insert_node
je pravdepodobne najkomplikovanejšie zo

363
00:15:49,980 --> 00:15:53,550
tri budeme písať, pretože som
pridal niektoré ďalšie obmedzenia na

364
00:15:53,550 --> 00:15:57,190
vaše programovania, najmä to, že
nebudete vložiť akýkoľvek

365
00:15:57,190 --> 00:15:59,880
duplikáty a že zoznam
by mala zostať triedené.

366
00:15:59,880 --> 00:16:02,660
Tak to je non-triviálne program,
že budete musieť kód.

367
00:16:02,660 --> 00:16:06,470
A prečo si nevezmeš päť-sedem
minút len ​​preto, aby sa práce na

368
00:16:06,470 --> 00:16:07,640
pseudokódu a kód.

369
00:16:07,640 --> 00:16:09,460
A potom začneme
ísť ako skupina.

370
00:16:09,460 --> 00:16:11,680
Opäť platí, že ak máte nejaké otázky stačí
zdvihnúť ruku a pôjdem okolo.

371
00:16:11,680 --> 00:16:15,258

372
00:16:15,258 --> 00:16:16,508
.

373
00:16:16,508 --> 00:18:28,370

374
00:18:28,370 --> 00:18:30,120
>> Tiež sme všeobecne robiť to -

375
00:18:30,120 --> 00:18:32,070
alebo nemám explicitne povedať vám
môže pracovať s ľuďmi.

376
00:18:32,070 --> 00:18:36,500
Ale samozrejme, vrelo vám odporúčame,
Ak máte otázky, požadovať

377
00:18:36,500 --> 00:18:39,840
sused sedí vedľa teba
alebo dokonca pracovať s niekým,

378
00:18:39,840 --> 00:18:40,510
inak, ak chcete.

379
00:18:40,510 --> 00:18:42,600
To nemusí byť individuálna
tichá činnosť.

380
00:18:42,600 --> 00:20:11,770

381
00:20:11,770 --> 00:20:16,330
>> Poďme začať s písaním niektorých
pseudokódu na palube.

382
00:20:16,330 --> 00:20:19,395
Kto mi môže dať prvý riadok
pseudokódu pre tento program?

383
00:20:19,395 --> 00:20:22,240

384
00:20:22,240 --> 00:20:23,640
Pre túto funkciu, skôr -
insert_node.

385
00:20:23,640 --> 00:20:29,960

386
00:20:29,960 --> 00:20:31,830
Alden?

387
00:20:31,830 --> 00:20:36,560
>> DIVÁKOV: Takže prvá vec, ktorú som urobil, bolo,
vytvoriť nový ukazovateľ na uzol a ja

388
00:20:36,560 --> 00:20:41,320
inicializovaný to ukazuje na rovnaký
vec, že ​​zoznam je ukazuje.

389
00:20:41,320 --> 00:20:41,550
>> JASON HIRSCHORN: OK.

390
00:20:41,550 --> 00:20:45,190
Takže budete vytvárať nový ukazovateľ
na zozname, a to k uzlu.

391
00:20:45,190 --> 00:20:45,420
>> DIVÁKOV: Správne.

392
00:20:45,420 --> 00:20:46,150
Jo.

393
00:20:46,150 --> 00:20:46,540
>> JASON HIRSCHORN: OK.

394
00:20:46,540 --> 00:20:48,221
A potom to, čo chceme robiť?

395
00:20:48,221 --> 00:20:49,163
Čo je po tom?

396
00:20:49,163 --> 00:20:50,105
Čo uzla?

397
00:20:50,105 --> 00:20:51,050
Nemáme uzol.

398
00:20:51,050 --> 00:20:52,300
Máme len hodnotu.

399
00:20:52,300 --> 00:20:55,918

400
00:20:55,918 --> 00:20:58,890
Ak chceme vložiť uzol, čo máme
je potrebné urobiť skôr, než sa budeme môcť ešte

401
00:20:58,890 --> 00:20:59,980
premýšľať o tom, vloženie?

402
00:20:59,980 --> 00:21:00,820
>> DIVÁKOV: Oh, ospravedlňujem sa.

403
00:21:00,820 --> 00:21:02,160
musíme malloc priestor pre uzol.

404
00:21:02,160 --> 00:21:02,455
>> JASON HIRSCHORN: Výborný.

405
00:21:02,455 --> 00:21:03,210
Poďme urobiť -

406
00:21:03,210 --> 00:21:04,628
OK.

407
00:21:04,628 --> 00:21:06,065
Nemožno dosiahnuť tak vysoko.

408
00:21:06,065 --> 00:21:08,939

409
00:21:08,939 --> 00:21:09,897
OK.

410
00:21:09,897 --> 00:21:13,236
Chystáme sa ísť dole, a potom
sme pomocou dvoch stĺpcov.

411
00:21:13,236 --> 00:21:13,732
Nemôžem ísť, že -

412
00:21:13,732 --> 00:21:14,982
OK.

413
00:21:14,982 --> 00:21:23,660

414
00:21:23,660 --> 00:21:25,130
Vytvoriť nový uzol.

415
00:21:25,130 --> 00:21:29,380
Môžete vytvoriť ďalší ukazovateľ na zoznam
alebo stačí použiť zoznam, ako to existuje.

416
00:21:29,380 --> 00:21:30,720
Nemáte naozaj potrebujete urobiť, že.

417
00:21:30,720 --> 00:21:31,750
>> Tak sme sa vytvoriť nový uzol.

418
00:21:31,750 --> 00:21:32,010
Skvelé.

419
00:21:32,010 --> 00:21:32,840
To je to, čo robíme ako prvý.

420
00:21:32,840 --> 00:21:34,870
Čo bude ďalej?

421
00:21:34,870 --> 00:21:35,080
>> DIVÁKOV: Počkajte.

422
00:21:35,080 --> 00:21:38,330
Mali by sme vytvoriť nový uzol sa podnikom alebo
Mali by sme počkať, aby sa uistil, že

423
00:21:38,330 --> 00:21:42,260
tam žiadne duplikáty uzla
na zozname, ako ju vytvoriť?

424
00:21:42,260 --> 00:21:43,100
>> JASON HIRSCHORN: Dobrá otázka.

425
00:21:43,100 --> 00:21:47,770
Poďme si myslí, že na neskôr, pretože
väčšinu času budeme vytvárať

426
00:21:47,770 --> 00:21:48,220
nový uzol.

427
00:21:48,220 --> 00:21:49,110
Takže budeme držať tu.

428
00:21:49,110 --> 00:21:51,006
Ale to je dobrá otázka.

429
00:21:51,006 --> 00:21:53,250
Ak by sme ju vytvoriť a nájdeme
duplicitné, čo by

430
00:21:53,250 --> 00:21:54,490
budeme robiť, než sa vráti?

431
00:21:54,490 --> 00:21:55,190
>> DIVÁKOV: Uvoľnite sa.

432
00:21:55,190 --> 00:21:55,470
>> JASON HIRSCHORN: Jo.

433
00:21:55,470 --> 00:21:56,500
Pravdepodobne ho uvoľniť.

434
00:21:56,500 --> 00:21:56,760
OK.

435
00:21:56,760 --> 00:21:59,850
Čo budeme robiť, keď sme
vytvoriť nový uzol?

436
00:21:59,850 --> 00:22:02,260
Annie?

437
00:22:02,260 --> 00:22:04,780
>> DIVÁKOV: Dali sme
Číslo v uzle?

438
00:22:04,780 --> 00:22:05,140
>> JASON HIRSCHORN: Presne tak.

439
00:22:05,140 --> 00:22:07,190
Kladieme číslo - budeme malloc priestor.

440
00:22:07,190 --> 00:22:08,160
Chystám sa nechať, že
všetko ako jeden riadok.

441
00:22:08,160 --> 00:22:08,720
Ale máš pravdu.

442
00:22:08,720 --> 00:22:10,305
Malloc sme priestor, a potom
dáme číslo palcov

443
00:22:10,305 --> 00:22:12,585
Dokonca môžeme nastaviť ukazovateľ
časť na hodnotu null.

444
00:22:12,585 --> 00:22:13,720
To je presne to pravé.

445
00:22:13,720 --> 00:22:17,400
A potom čo po tom?

446
00:22:17,400 --> 00:22:18,490
Nakreslil sme tento obrázok na tabuli.

447
00:22:18,490 --> 00:22:21,190
Tak čo budeme robiť?

448
00:22:21,190 --> 00:22:22,680
>> DIVÁKOV: Prejdeme zoznamu.

449
00:22:22,680 --> 00:22:23,930
>> JASON HIRSCHORN: Prejdite si zoznam.

450
00:22:23,930 --> 00:22:30,620

451
00:22:30,620 --> 00:22:31,100
OK.

452
00:22:31,100 --> 00:22:34,280
A čo si budeme kontrolovať na každom uzle.

453
00:22:34,280 --> 00:22:35,955
Kurt, čo môžeme skontrolovať
pre každý uzol v?

454
00:22:35,955 --> 00:22:41,640
>> DIVÁKOV: Pozrite sa, či n hodnota
že uzol je väčšia, než je hodnota n

455
00:22:41,640 --> 00:22:43,070
nášho uzla.

456
00:22:43,070 --> 00:22:43,340
>> JASON HIRSCHORN: OK.

457
00:22:43,340 --> 00:22:44,280
Budem robiť -

458
00:22:44,280 --> 00:22:45,855
jo, OK.

459
00:22:45,855 --> 00:22:48,160
Tak to je n -

460
00:22:48,160 --> 00:22:59,040
Chystám sa povedať, či hodnota je väčšia
ako v tomto uzle, potom to, čo budeme robiť?

461
00:22:59,040 --> 00:23:07,290
>> DIVÁKOV: No, potom vložíme
přmo pred tým.

462
00:23:07,290 --> 00:23:07,970
>> JASON HIRSCHORN: OK.

463
00:23:07,970 --> 00:23:09,410
Takže ak je to väčšie ako to,
potom chceme vložiť.

464
00:23:09,410 --> 00:23:14,010
Ale chceme, tesne predtým, než ju vložiť
pretože tiež bude musieť byť

465
00:23:14,010 --> 00:23:16,070
sledovanie, a potom,
z toho, čo bolo predtým.

466
00:23:16,070 --> 00:23:22,690
Takže vložte pred.

467
00:23:22,690 --> 00:23:25,120
Takže sme asi niečo uniklo
skôr.

468
00:23:25,120 --> 00:23:27,770
Asi sme potrebné udržať
track z toho, čo sa deje.

469
00:23:27,770 --> 00:23:28,460
Ale dostaneme sa tam.

470
00:23:28,460 --> 00:23:30,160
Takže to, čo je hodnota nižšia ako?

471
00:23:30,160 --> 00:23:38,030

472
00:23:38,030 --> 00:23:39,710
Kurt, čo budeme robiť, keď
hodnota je nižšia ako?

473
00:23:39,710 --> 00:23:43,000
>> DIVÁKOV: Potom stačí ísť ďalej
ak je to posledné.

474
00:23:43,000 --> 00:23:43,550
>> JASON HIRSCHORN: Páči sa mi to.

475
00:23:43,550 --> 00:23:44,800
Tak choďte na ďalší uzol.

476
00:23:44,800 --> 00:23:47,410

477
00:23:47,410 --> 00:23:48,930
Ak to posledné -

478
00:23:48,930 --> 00:23:51,100
sme asi kontrola, ktorá
v podmienkach stave.

479
00:23:51,100 --> 00:23:54,870
Ale jo, ďalší uzol.

480
00:23:54,870 --> 00:23:58,680
A to je stále príliš nízka,
takže budeme pohybovať sem.

481
00:23:58,680 --> 00:24:02,030
Ale ak -

482
00:24:02,030 --> 00:24:03,280
môže každý vidieť?

483
00:24:03,280 --> 00:24:07,230

484
00:24:07,230 --> 00:24:11,610
Ak sme rovnaká, čo budeme robiť?

485
00:24:11,610 --> 00:24:15,740
Ak hodnota sa snažíme vložiť
sa rovná hodnote tohto uzla?

486
00:24:15,740 --> 00:24:16,320
Jo?

487
00:24:16,320 --> 00:24:18,400
>> DIVÁKOV: [nepočuteľné].

488
00:24:18,400 --> 00:24:18,850
>> JASON HIRSCHORN: Jo.

489
00:24:18,850 --> 00:24:19,290
Vzhľadom k tejto -

490
00:24:19,290 --> 00:24:20,090
Marcus je v poriadku.

491
00:24:20,090 --> 00:24:21,330
Mohli sme možno urobili
niečo iné.

492
00:24:21,330 --> 00:24:25,360
Ale vzhľadom k tomu, že sme vytvorili to, tu
by sme sa mali uvoľniť a potom sa vrátiť.

493
00:24:25,360 --> 00:24:26,774
Ach jo.

494
00:24:26,774 --> 00:24:30,080
Je to lepšie?

495
00:24:30,080 --> 00:24:31,850
Ako to?

496
00:24:31,850 --> 00:24:33,100
OK.

497
00:24:33,100 --> 00:24:35,360

498
00:24:35,360 --> 00:24:37,640
Zadarmo a potom to, čo máme
vrátiť, [nepočuteľný]?

499
00:24:37,640 --> 00:24:41,330

500
00:24:41,330 --> 00:24:44,110
OK.

501
00:24:44,110 --> 00:24:45,360
Sme niečo chýba?

502
00:24:45,360 --> 00:24:53,500

503
00:24:53,500 --> 00:24:59,650
Takže tam, kde sme sledovanie
z predchádzajúceho uzla?

504
00:24:59,650 --> 00:25:02,370
>> DIVÁKOV: Myslím, že to pôjde
Po vytvorení nového uzla.

505
00:25:02,370 --> 00:25:02,600
>> JASON HIRSCHORN: OK.

506
00:25:02,600 --> 00:25:03,940
Takže na začiatku sme sa asi -

507
00:25:03,940 --> 00:25:07,175
jo, môžeme vytvoriť ukazovateľ na nový
uzol, ako predchádzajúci ukazovateľ uzla a

508
00:25:07,175 --> 00:25:09,600
aktuálny uzol ukazovateľ.

509
00:25:09,600 --> 00:25:12,640
Takže poďme vložte tu.

510
00:25:12,640 --> 00:25:15,610

511
00:25:15,610 --> 00:25:26,900
Vytvorte aktuálne a predchádzajúce
ukazovatele na uzly.

512
00:25:26,900 --> 00:25:28,955
Ale keď budeme nastaviť tie odkazy?

513
00:25:28,955 --> 00:25:30,205
Tam, kde to urobíme v kóde?

514
00:25:30,205 --> 00:25:33,830

515
00:25:33,830 --> 00:25:34,160
Jeff?

516
00:25:34,160 --> 00:25:35,170
>> DIVÁKOV: - Podmienky hodnota?

517
00:25:35,170 --> 00:25:36,420
>> JASON HIRSCHORN: Ktoré
jeden najmä?

518
00:25:36,420 --> 00:25:39,862

519
00:25:39,862 --> 00:25:40,720
>> DIVÁKOV: Ja som len zmätená.

520
00:25:40,720 --> 00:25:44,200
Je-li hodnota je vyššia, než v tomto uzle,
Neznamená to, že chcete ísť

521
00:25:44,200 --> 00:25:45,320
na ďalší uzol?

522
00:25:45,320 --> 00:25:49,515
>> JASON Hirschhorn: Takže ak naša hodnota je
väčšia, než je hodnota tohto uzla.

523
00:25:49,515 --> 00:25:52,130
>> DIVÁKOV: Jo, potom by ste chceli, aby
ísť ďalej v rade, nie?

524
00:25:52,130 --> 00:25:52,590
>> JASON Hirschhorn: Správne.

525
00:25:52,590 --> 00:25:53,840
Takže nemáme vložte ho sem.

526
00:25:53,840 --> 00:25:58,430

527
00:25:58,430 --> 00:26:03,240
Ak je hodnota nižšia ako v tomto uzle, potom
ideme na ďalší uzol - a potom sme

528
00:26:03,240 --> 00:26:03,835
vložte pred.

529
00:26:03,835 --> 00:26:05,966
>> DIVÁKOV: Počkajte, čo je v tomto
uzol a ktorá je hodnota?

530
00:26:05,966 --> 00:26:08,510

531
00:26:08,510 --> 00:26:09,280
>> JASON Hirschhorn: Dobrá otázka.

532
00:26:09,280 --> 00:26:13,260
Hodnota za tejto definície funkcie
je to, čo sme vzhľadom.

533
00:26:13,260 --> 00:26:16,910
Takže hodnota je číslo sme vzhľadom.

534
00:26:16,910 --> 00:26:21,120
Takže v prípade, že hodnota je nižšia ako tento
uzol, potrebujeme čas na vloženie.

535
00:26:21,120 --> 00:26:24,575
Je-li hodnota je vyššia, než v tomto uzle,
ideme na ďalší uzol.

536
00:26:24,575 --> 00:26:26,790
A späť k pôvodnej otázke,
aj keď, kde -

537
00:26:26,790 --> 00:26:29,060
>> DIVÁKOV: Ak je hodnota väčšia
ako tento uzol.

538
00:26:29,060 --> 00:26:30,310
>> JASON Hirschhorn: A tak
Čo tu robíme?

539
00:26:30,310 --> 00:26:36,790

540
00:26:36,790 --> 00:26:38,160
Sladké.

541
00:26:38,160 --> 00:26:38,860
To je správne.

542
00:26:38,860 --> 00:26:41,370
Idem písať
aktualizovať ukazovatele.

543
00:26:41,370 --> 00:26:44,010
Ale áno, sa existujúce
by ste ho aktualizovať

544
00:26:44,010 --> 00:26:46,080
poukazujú na ten budúci.

545
00:26:46,080 --> 00:26:47,330
Ešte niečo nám chýba?

546
00:26:47,330 --> 00:26:52,710

547
00:26:52,710 --> 00:26:54,940
Takže budem písať tento
kód do gedit.

548
00:26:54,940 --> 00:26:58,375
A keď som to urobiť, môžete mať
pár ďalších minút k práci na kódovanie

549
00:26:58,375 --> 00:28:19,240
to v C.

550
00:28:19,240 --> 00:28:20,940
>> Takže mám Zadajte pseudokódu.

551
00:28:20,940 --> 00:28:22,940
Krátka poznámka, než začneme.

552
00:28:22,940 --> 00:28:25,560
My nemusí byť schopný úplne
dokončiť to vo všetkých

553
00:28:25,560 --> 00:28:27,300
tri z týchto funkcií.

554
00:28:27,300 --> 00:28:30,630
Tam je správne riešenie k nim
že som sa e-mailom na vás chlapci

555
00:28:30,630 --> 00:28:33,730
po bode, a to bude
byť zanechané CS50.net.

556
00:28:33,730 --> 00:28:35,640
Tak som sa ťa povzbudiť, aby
ísť pozrieť na sekciách.

557
00:28:35,640 --> 00:28:40,550
Odporúčam vám vyskúšať to na vašom
vlastné, a potom použiť v praxi

558
00:28:40,550 --> 00:28:41,760
problémy, aby sme zistili, či vaše odpovede.

559
00:28:41,760 --> 00:28:47,070
Tie boli všetky navrhnuté tak, aby úzko
týkajú, a dodržiavať to, čo

560
00:28:47,070 --> 00:28:48,400
čo musíte urobiť, na problém sade.

561
00:28:48,400 --> 00:28:53,820
Tak som sa povzbudiť vás k praxi to
na vlastnú päsť, a potom použite kód

562
00:28:53,820 --> 00:28:54,660
skontrolujte svoje odpovede.

563
00:28:54,660 --> 00:28:57,060
Pretože chcem prejsť na hash
Stoly na nejakom mieste v sekcii.

564
00:28:57,060 --> 00:28:58,150
Takže by sme mohli dostať cez to všetko.

565
00:28:58,150 --> 00:28:59,960
Ale budeme robiť teraz, ako moc môžeme.

566
00:28:59,960 --> 00:29:00,370
>> OK.

567
00:29:00,370 --> 00:29:01,960
Poďme začať.

568
00:29:01,960 --> 00:29:04,770
Asam, ako sme sa vytvoriť nový uzol?

569
00:29:04,770 --> 00:29:06,810
>> DIVÁKOV: Ty struct *.

570
00:29:06,810 --> 00:29:09,640
>> JASON Hirschhorn: Tak sme
si, že sa tu.

571
00:29:09,640 --> 00:29:10,040
Oh, ospravedlňujem sa.

572
00:29:10,040 --> 00:29:13,530
Hovoril ste struct *.

573
00:29:13,530 --> 00:29:17,260
>> DIVÁKOV: A potom [? druh?]
uzol alebo c uzol.

574
00:29:17,260 --> 00:29:17,780
>> JASON Hirschhorn: OK.

575
00:29:17,780 --> 00:29:19,740
Budem hovoriť new_node
takže môžeme zostať konzistentné.

576
00:29:19,740 --> 00:29:22,646

577
00:29:22,646 --> 00:29:33,180
>> DIVÁKOV: A chcete nastaviť, ktoré
na hlavu, prvý uzol.

578
00:29:33,180 --> 00:29:33,580
>> JASON Hirschhorn: OK.

579
00:29:33,580 --> 00:29:37,290
Takže teraz to ukazujúce na - tak to
nebol vytvorený nový uzol doteraz.

580
00:29:37,290 --> 00:29:41,380
To je len ukazuje na
prvý uzol v zozname.

581
00:29:41,380 --> 00:29:42,630
Ako môžem vytvoriť nový uzol?

582
00:29:42,630 --> 00:29:45,490

583
00:29:45,490 --> 00:29:48,070
Ak je potreba priestor pre vytvorenie nového uzla.

584
00:29:48,070 --> 00:29:49,230
Malloc.

585
00:29:49,230 --> 00:29:51,710
A ako veľký?

586
00:29:51,710 --> 00:30:00,390
>> Divákov: veľkosť struct.

587
00:30:00,390 --> 00:30:01,150
>> JASON Hirschhorn:
veľkosť struct.

588
00:30:01,150 --> 00:30:02,400
A čo struct volá?

589
00:30:02,400 --> 00:30:09,670

590
00:30:09,670 --> 00:30:09,840
>> DIVÁKOV: Uzol?

591
00:30:09,840 --> 00:30:11,640
>> JASON Hirschhorn: Node.

592
00:30:11,640 --> 00:30:17,640
Takže malloc (sizeof (node));
nám dáva priestor.

593
00:30:17,640 --> 00:30:19,740
A je to linka -

594
00:30:19,740 --> 00:30:21,740
jedna vec je nesprávne na tomto riadku.

595
00:30:21,740 --> 00:30:24,430
Je new_node ukazovateľ na struct?

596
00:30:24,430 --> 00:30:25,650
To je všeobecný názov.

597
00:30:25,650 --> 00:30:26,520
Čo je to -

598
00:30:26,520 --> 00:30:27,450
uzol, presne tak.

599
00:30:27,450 --> 00:30:29,340
Je to uzol *.

600
00:30:29,340 --> 00:30:33,010
A čo budeme robiť hneď po
sme malloc niečo, Asan?

601
00:30:33,010 --> 00:30:34,476
Čo je prvá vec, ktorú budeme robiť?

602
00:30:34,476 --> 00:30:38,850

603
00:30:38,850 --> 00:30:40,320
Čo keď to nefunguje?

604
00:30:40,320 --> 00:30:42,430
>> DIVÁKOV: Oh, skontrolujte, či je
poukazuje na uzle?

605
00:30:42,430 --> 00:30:43,310
>> JASON Hirschhorn: Presne tak.

606
00:30:43,310 --> 00:30:46,750
Takže ak ste new_node rovná rovná
null, čo budeme robiť?

607
00:30:46,750 --> 00:30:51,650

608
00:30:51,650 --> 00:30:54,820
Tento vracia bool, túto funkciu.

609
00:30:54,820 --> 00:30:57,760
Presne tak.

610
00:30:57,760 --> 00:30:58,450
Vyzerá to dobre.

611
00:30:58,450 --> 00:30:59,680
Niečo sa tam pridať?

612
00:30:59,680 --> 00:31:00,670
Budeme pridávať veci na konci.

613
00:31:00,670 --> 00:31:03,160
Ale to zatiaľ vyzerá dobre.

614
00:31:03,160 --> 00:31:06,170
Vytvorte aktuálne a predchádzajúce ukazovatele.

615
00:31:06,170 --> 00:31:08,650
Michael, ako to mám urobiť?

616
00:31:08,650 --> 00:31:12,810
>> DIVÁKOV: Budete musieť
urobiť uzol *.

617
00:31:12,810 --> 00:31:21,800

618
00:31:21,800 --> 00:31:25,502
Musel by si urobiť jednu nie
pre new_node ale

619
00:31:25,502 --> 00:31:26,905
uzly už máme.

620
00:31:26,905 --> 00:31:27,230
>> JASON Hirschhorn: OK.

621
00:31:27,230 --> 00:31:29,255
Takže aktuálny uzol sme ďalej.

622
00:31:29,255 --> 00:31:30,505
Zavolám, že curry.

623
00:31:30,505 --> 00:31:39,650

624
00:31:39,650 --> 00:31:39,770
Dobrá.

625
00:31:39,770 --> 00:31:41,620
Rozhodli sme sa chceme udržať
dva, pretože potrebujeme vedieť,

626
00:31:41,620 --> 00:31:42,870
to, čo je pred ním.

627
00:31:42,870 --> 00:31:45,770

628
00:31:45,770 --> 00:31:47,020
Čo oni si inicializovaný?

629
00:31:47,020 --> 00:31:49,874

630
00:31:49,874 --> 00:31:54,180
>> DIVÁKOV: Ich hodnota v našom zozname.

631
00:31:54,180 --> 00:31:58,090
>> JASON Hirschhorn: Takže to, čo je
Prvá vec, ktorú na našom zozname?

632
00:31:58,090 --> 00:32:04,050
Alebo ako vieme, kde
začiatok nášho zoznamu je?

633
00:32:04,050 --> 00:32:08,015
>> DIVÁKOV: Nie je to prešlo
do funkcie?

634
00:32:08,015 --> 00:32:08,466
>> JASON Hirschhorn: Správne.

635
00:32:08,466 --> 00:32:09,716
To bol schválený v roku tady.

636
00:32:09,716 --> 00:32:15,910

637
00:32:15,910 --> 00:32:18,980
Takže ak je to prešiel do funkcie,
začiatok zoznamu, čo by sme mali

638
00:32:18,980 --> 00:32:21,270
nastaviť prúd rovný?

639
00:32:21,270 --> 00:32:22,110
>> DIVÁKOV: List.

640
00:32:22,110 --> 00:32:22,900
>> JASON Hirschhorn: List.

641
00:32:22,900 --> 00:32:24,090
To je presne to pravé.

642
00:32:24,090 --> 00:32:26,290
Teraz má adresu
začiatok nášho zoznamu.

643
00:32:26,290 --> 00:32:28,450
A čo predchádzajúce?

644
00:32:28,450 --> 00:32:31,920
>> DIVÁKOV: Zoznam mínus jedna?

645
00:32:31,920 --> 00:32:32,690
>> JASON Hirschhorn: tu
nič pred ním.

646
00:32:32,690 --> 00:32:34,580
Čo teda môžeme urobiť pre to, znamenať nič?

647
00:32:34,580 --> 00:32:35,050
>> DIVÁKOV: Null.

648
00:32:35,050 --> 00:32:35,450
>> JASON Hirschhorn: Jo.

649
00:32:35,450 --> 00:32:37,950
To znie ako dobrý nápad.

650
00:32:37,950 --> 00:32:38,360
Perfect.

651
00:32:38,360 --> 00:32:39,630
Ďakujem.

652
00:32:39,630 --> 00:32:42,850
Prejdite si zoznam.

653
00:32:42,850 --> 00:32:45,490
Constantine, ako dlho sa budeme
prejsť zoznamu?

654
00:32:45,490 --> 00:32:49,010
>> DIVÁKOV: až sa dostaneme null.

655
00:32:49,010 --> 00:32:49,390
>> JASON Hirschhorn: OK.

656
00:32:49,390 --> 00:32:50,430
Takže v prípade, zatiaľ čo pre slučku.

657
00:32:50,430 --> 00:32:52,200
Čo budeme robiť?

658
00:32:52,200 --> 00:32:53,320
>> DIVÁKOV: Možno, že pre sláčiky?

659
00:32:53,320 --> 00:32:53,910
>> JASON Hirschhorn: Poďme urobiť pre sláčiky.

660
00:32:53,910 --> 00:32:55,870
OK.

661
00:32:55,870 --> 00:33:02,465
>> DIVÁKOV: A my hovoríme na -

662
00:33:02,465 --> 00:33:09,764

663
00:33:09,764 --> 00:33:13,390
až do súčasnej ukazovateľ
nie je rovné null.

664
00:33:13,390 --> 00:33:19,160
>> JASON Hirschhorn: Takže ak vieme,
stav, ako môžeme napísať slučku

665
00:33:19,160 --> 00:33:21,740
vychádza z tohto stavu.

666
00:33:21,740 --> 00:33:24,380
Aký druh slučky by sme mali používať?

667
00:33:24,380 --> 00:33:25,260
>> DIVÁKOV: Kým.

668
00:33:25,260 --> 00:33:25,590
>> JASON Hirschhorn: Jo.

669
00:33:25,590 --> 00:33:27,130
To dáva väčší zmysel na základe
off z toho, čo ste povedal.

670
00:33:27,130 --> 00:33:29,430
Ak chceme len ísť do sme, že
Len viem, že vec, bolo by

671
00:33:29,430 --> 00:33:31,680
zmysel robiť while.

672
00:33:31,680 --> 00:33:39,880
Kým súčasná nie je rovné null,
ak hodnota je nižšia ako tento uzol.

673
00:33:39,880 --> 00:33:41,650
Akshar, daj mi tento riadok.

674
00:33:41,650 --> 00:33:48,810

675
00:33:48,810 --> 00:33:56,955
>> DIVÁKOV: Ak je aktuálna-> n
n menšia ako hodnota.

676
00:33:56,955 --> 00:34:00,170

677
00:34:00,170 --> 00:34:03,260
Alebo zvrátiť to.

678
00:34:03,260 --> 00:34:06,140
Spínač, ktorý držiak.

679
00:34:06,140 --> 00:34:06,620
>> JASON Hirschhorn: Ospravedlňujem sa.

680
00:34:06,620 --> 00:34:08,760
>> DIVÁKOV: Zmeňte držiak.

681
00:34:08,760 --> 00:34:10,914
>> JASON Hirschhorn: Takže ak je to
vyššia ako hodnota.

682
00:34:10,914 --> 00:34:18,719

683
00:34:18,719 --> 00:34:22,120
Vzhľadom k tomu, že je to mätúce
komentár vyššie, budem robiť, že.

684
00:34:22,120 --> 00:34:22,480
Ale áno.

685
00:34:22,480 --> 00:34:25,125
Ak je naša hodnota je nižšia ako tento
uzol, čo budeme robiť?

686
00:34:25,125 --> 00:34:25,540
Oh.

687
00:34:25,540 --> 00:34:26,710
Mám ho tu.

688
00:34:26,710 --> 00:34:27,960
Vložte predtým.

689
00:34:27,960 --> 00:34:32,080

690
00:34:32,080 --> 00:34:32,370
OK.

691
00:34:32,370 --> 00:34:33,933
Ako to urobíme?

692
00:34:33,933 --> 00:34:34,900
>> DIVÁKOV: Je to ešte ja?

693
00:34:34,900 --> 00:34:36,150
>> JASON Hirschhorn: Jo.

694
00:34:36,150 --> 00:34:38,520

695
00:34:38,520 --> 00:34:39,770
>> DIVÁKOV: Vy -

696
00:34:39,770 --> 00:34:42,909

697
00:34:42,909 --> 00:34:44,159
new_node-> ďalšie.

698
00:34:44,159 --> 00:34:46,770

699
00:34:46,770 --> 00:34:50,163
>> JASON Hirschhorn: Takže to, čo je
že bude rovnať?

700
00:34:50,163 --> 00:34:52,070
>> DIVÁKOV: Bude to rovnaké prúdu.

701
00:34:52,070 --> 00:34:53,889
>> JASON Hirschhorn: Presne tak.

702
00:34:53,889 --> 00:34:55,730
A tak ďalšie -

703
00:34:55,730 --> 00:34:56,730
čo ešte musíme aktualizovať?

704
00:34:56,730 --> 00:34:59,982
>> DIVÁKOV: Skontrolujte, či minulosť rovná null.

705
00:34:59,982 --> 00:35:01,870
>> JASON Hirschhorn: Ak prev -

706
00:35:01,870 --> 00:35:03,730
takže ak predchádzajúci rovná null.

707
00:35:03,730 --> 00:35:05,990
>> DIVÁKOV: To znamená, že sa deje
aby sa stal hlavou.

708
00:35:05,990 --> 00:35:06,780
>> JASON Hirschhorn: To znamená
je to stáť hlavy.

709
00:35:06,780 --> 00:35:07,620
Tak čo budeme robiť?

710
00:35:07,620 --> 00:35:12,510
>> DIVÁKOV: Robíme hlava rovná new_node.

711
00:35:12,510 --> 00:35:16,690
>> JASON Hirschhorn: Head
rovná new_node.

712
00:35:16,690 --> 00:35:20,540
A prečo hlava tu, nie zoznam?

713
00:35:20,540 --> 00:35:24,940
>> DIVÁKOV: Vzhľadom k tomu, hlava je globálna
variabilný, čo je východiskové miesto.

714
00:35:24,940 --> 00:35:26,190
>> JASON Hirschhorn: Sladký.

715
00:35:26,190 --> 00:35:33,750

716
00:35:33,750 --> 00:35:34,170
OK.

717
00:35:34,170 --> 00:35:36,150
A -

718
00:35:36,150 --> 00:35:53,796
>> DIVÁKOV: Potom si ešte prev->
Ďalšie rovná new_node.

719
00:35:53,796 --> 00:35:55,080
A potom sa vrátiť true.

720
00:35:55,080 --> 00:35:59,560

721
00:35:59,560 --> 00:36:02,700
>> JASON Hirschhorn: Kam
sme sa vydali new_node koniec?

722
00:36:02,700 --> 00:36:04,850
>> DIVÁKOV: Ja by som -

723
00:36:04,850 --> 00:36:06,180
Nastaviť, že na začiatku.

724
00:36:06,180 --> 00:36:07,430
>> JASON Hirschhorn: Tak čo linka?

725
00:36:07,430 --> 00:36:10,000

726
00:36:10,000 --> 00:36:12,598
>> DIVÁKOV: Po if
kontrolovať, či je známe.

727
00:36:12,598 --> 00:36:13,057
>> JASON Hirschhorn: Tu?

728
00:36:13,057 --> 00:36:18,335
>> DIVÁKOV: ja by som to new_node-> n
sa rovná hodnote.

729
00:36:18,335 --> 00:36:19,585
>> JASON Hirschhorn: To znie dobre.

730
00:36:19,585 --> 00:36:21,740

731
00:36:21,740 --> 00:36:25,090
Pravdepodobne to dáva zmysel - my nie
Potrebujeme vedieť, čo zoznam sme na

732
00:36:25,090 --> 00:36:26,280
preto, že sme len do činenia
s jedného zoznamu.

733
00:36:26,280 --> 00:36:29,560
Takže lepšie funkcie vyhlásenie o
je to len, ako sa zbaviť tohto

734
00:36:29,560 --> 00:36:34,360
úplne a len vložiť
hodnota do hlavy.

735
00:36:34,360 --> 00:36:35,930
My ani nemusíte vedieť
čo zoznam sme dovnútra

736
00:36:35,930 --> 00:36:39,140
Ale nechám to teraz a
potom ho zmeniť na aktualizáciu

737
00:36:39,140 --> 00:36:42,590
sklíčka a kód.

738
00:36:42,590 --> 00:36:44,980
Takže to vyzerá dobre teraz.

739
00:36:44,980 --> 00:36:46,560
Je-li hodnota - kto môže robiť tento riadok?

740
00:36:46,560 --> 00:36:47,810
Ak -

741
00:36:47,810 --> 00:36:52,240

742
00:36:52,240 --> 00:36:53,840
Čo budeme robiť tu, Noah.

743
00:36:53,840 --> 00:36:57,890

744
00:36:57,890 --> 00:37:07,100
>> DIVÁKOV: Ak je hodnota väčšia
ako akt-> n -

745
00:37:07,100 --> 00:37:16,830

746
00:37:16,830 --> 00:37:18,240
>> JASON Hirschhorn: Ako
ideme na ďalší uzol?

747
00:37:18,240 --> 00:37:27,760

748
00:37:27,760 --> 00:37:30,530
>> DIVÁKOV: Mena-> n je
rovná new_node.

749
00:37:30,530 --> 00:37:37,630

750
00:37:37,630 --> 00:37:39,195
>> JASON Hirschhorn: Tak n je
aká časť struct?

751
00:37:39,195 --> 00:37:43,065

752
00:37:43,065 --> 00:37:46,020
Celé číslo.

753
00:37:46,020 --> 00:37:50,420
A new_node je ukazovateľ na uzol.

754
00:37:50,420 --> 00:37:51,880
Takže to, čo časť Curr by sme mali aktualizovať?

755
00:37:51,880 --> 00:38:03,900

756
00:38:03,900 --> 00:38:05,400
Ak n nie, potom to, čo je tá druhá časť?

757
00:38:05,400 --> 00:38:21,680

758
00:38:21,680 --> 00:38:22,810
Noah, čo je tá druhá časť.

759
00:38:22,810 --> 00:38:23,570
>> DIVÁKOV: Oh, ďalšie.

760
00:38:23,570 --> 00:38:25,645
>> JASON Hirschhorn: Ďalšie, presne tak.

761
00:38:25,645 --> 00:38:26,410
Presne tak.

762
00:38:26,410 --> 00:38:28,770
Ďalšia je správna.

763
00:38:28,770 --> 00:38:31,540
A čo ešte potrebujeme
aktualizovať, Noe?

764
00:38:31,540 --> 00:38:32,840
>> DIVÁKOV: Ukazovatele.

765
00:38:32,840 --> 00:38:34,840
>> JASON Hirschhorn: Tak
Aktualizovali sme prúd.

766
00:38:34,840 --> 00:38:36,090
>> DIVÁKOV: Prev-> ďalšie.

767
00:38:36,090 --> 00:38:48,160

768
00:38:48,160 --> 00:38:49,410
>> JASON Hirschhorn: Jo.

769
00:38:49,410 --> 00:38:57,465

770
00:38:57,465 --> 00:38:58,370
OK, budeme pozastaviť.

771
00:38:58,370 --> 00:39:02,200
Kto nám môže pomôcť tu?

772
00:39:02,200 --> 00:39:03,385
Manu, čo by sme mali robiť?

773
00:39:03,385 --> 00:39:05,615
>> DIVÁKOV: Musíš nastaviť
je rovná akt-> ďalšie.

774
00:39:05,615 --> 00:39:09,110

775
00:39:09,110 --> 00:39:11,630
Ale to, že skôr, než v predchádzajúcom riadku.

776
00:39:11,630 --> 00:39:12,880
>> JASON Hirschhorn: OK.

777
00:39:12,880 --> 00:39:16,590

778
00:39:16,590 --> 00:39:18,260
Ešte niečo?

779
00:39:18,260 --> 00:39:19,170
Akshar.

780
00:39:19,170 --> 00:39:22,680
>> DIVÁKOV: Nemyslím si, že si
chcel zmeniť akt-> ďalšie.

781
00:39:22,680 --> 00:39:29,270
Myslím, že si chcel robiť Mena rovná
akt-> ďalšie prejsť na ďalší uzol.

782
00:39:29,270 --> 00:39:30,500
>> JASON Hirschhorn: Je mi ľúto, kam?

783
00:39:30,500 --> 00:39:32,680
Na čo linka?

784
00:39:32,680 --> 00:39:33,420
Táto linka?

785
00:39:33,420 --> 00:39:33,750
>> DIVÁKOV: Jo.

786
00:39:33,750 --> 00:39:35,745
Uistite sa curry rovná akt-> ďalšie.

787
00:39:35,745 --> 00:39:39,690

788
00:39:39,690 --> 00:39:43,360
>> JASON Hirschhorn: Tak to je pravda
pretože prúd je

789
00:39:43,360 --> 00:39:45,220
ukazovateľ na uzol.

790
00:39:45,220 --> 00:39:48,550
A my chceme, aby to poukázať na ďalšie
uzol, čo sa dostáva v súčasnej dobe

791
00:39:48,550 --> 00:39:49,930
ukázal.

792
00:39:49,930 --> 00:39:54,410
Curry sama o sebe má ďalšie.

793
00:39:54,410 --> 00:39:58,620
Ale ak by sme mali aktualizovať curr.next sme
by sa aktualizácia aktuálnej poznámku

794
00:39:58,620 --> 00:40:01,430
sama o sebe, nie tam, kde to
ukazovateľ ukazoval.

795
00:40:01,430 --> 00:40:02,680
Čo o tejto línii, hoci.

796
00:40:02,680 --> 00:40:05,160

797
00:40:05,160 --> 00:40:07,330
Avi?

798
00:40:07,330 --> 00:40:09,590
>> DIVÁKOV: Prev-> Ďalšie rovná curry.

799
00:40:09,590 --> 00:40:12,500

800
00:40:12,500 --> 00:40:19,440
>> JASON Hirschhorn: Takže znova, ak predchádzajúci je
ukazovateľ na uzol, náhľad-> ďalšie je

801
00:40:19,440 --> 00:40:23,020
aktuálny ukazovateľ v uzle.

802
00:40:23,020 --> 00:40:27,190
Takže by to byť aktualizácia
ukazovateľ na uzol Curr.

803
00:40:27,190 --> 00:40:28,570
Nechceme aktualizovať
ukazovateľ v uzle.

804
00:40:28,570 --> 00:40:30,570
Chceme aktualizovať predchádzajúce.

805
00:40:30,570 --> 00:40:31,850
Tak ako to urobíme?

806
00:40:31,850 --> 00:40:34,250
>> DIVÁKOV: Bolo by to byť prev.

807
00:40:34,250 --> 00:40:34,565
>> JASON Hirschhorn: Správne.

808
00:40:34,565 --> 00:40:35,560
Predchádzajúce je ukazovateľ na uzol.

809
00:40:35,560 --> 00:40:38,750
Teraz meníme ju
nový ukazovateľ na uzol.

810
00:40:38,750 --> 00:40:40,830
OK Poďme dole.

811
00:40:40,830 --> 00:40:41,940
A konečne, tento posledný podmienka.

812
00:40:41,940 --> 00:40:44,896
Jeff, čo budeme robiť tu?

813
00:40:44,896 --> 00:40:47,515
>> DIVÁKOV: Ak je hodnota
rovnajúcu sa akt-> n

814
00:40:47,515 --> 00:40:51,030

815
00:40:51,030 --> 00:40:51,300
>> JASON Hirschhorn: Ospravedlňujem sa.

816
00:40:51,300 --> 00:40:52,372
Ach môj bože.

817
00:40:52,372 --> 00:40:54,330
Čo je?

818
00:40:54,330 --> 00:40:55,580
Hodnota == akt-> n

819
00:40:55,580 --> 00:41:01,050

820
00:41:01,050 --> 00:41:02,300
Čo budeme robiť?

821
00:41:02,300 --> 00:41:04,760

822
00:41:04,760 --> 00:41:10,950
>> DIVÁKOV: Ty by si oslobodiť našu new_node,
a potom by ste sa vrátiť false.

823
00:41:10,950 --> 00:41:21,410

824
00:41:21,410 --> 00:41:23,460
>> JASON Hirschhorn: To je to, čo
sme písali tak ďaleko.

825
00:41:23,460 --> 00:41:25,710
Má niekto niečo
pridať skôr, než urobíme?

826
00:41:25,710 --> 00:41:35,460

827
00:41:35,460 --> 00:41:35,710
OK.

828
00:41:35,710 --> 00:41:36,960
Poďme to skúsiť.

829
00:41:36,960 --> 00:41:44,180

830
00:41:44,180 --> 00:41:46,110
Kontrola môže dostať na koniec
z non-void funkcie.

831
00:41:46,110 --> 00:41:48,310
Avi, čo sa deje?

832
00:41:48,310 --> 00:41:51,380
>> DIVÁKOV: Ste mal dať návrate
platí mimo while?

833
00:41:51,380 --> 00:41:53,900

834
00:41:53,900 --> 00:41:54,400
>> JASON Hirschhorn: Ja neviem.

835
00:41:54,400 --> 00:41:54,780
Máte ma chcete?

836
00:41:54,780 --> 00:41:55,520
>> DIVÁKOV: Nevadí.

837
00:41:55,520 --> 00:41:56,350
Nie.

838
00:41:56,350 --> 00:41:57,180
>> JASON Hirschhorn: Akshar?

839
00:41:57,180 --> 00:41:59,460
>> DIVÁKOV: Myslím, že ste mal na mysli, aby
dať return false na konci

840
00:41:59,460 --> 00:42:02,230
z cyklu while.

841
00:42:02,230 --> 00:42:03,270
>> JASON Hirschhorn: Tak kde
chceš, aby to šlo?

842
00:42:03,270 --> 00:42:05,270
>> DIVÁKOV: Rovnako ako u cyklu while.

843
00:42:05,270 --> 00:42:08,800
Takže ak opustíte while to znamená, že
že ste prišli na koniec a

844
00:42:08,800 --> 00:42:09,980
nič sa nestalo.

845
00:42:09,980 --> 00:42:10,410
>> JASON Hirschhorn: OK.

846
00:42:10,410 --> 00:42:12,340
Tak čo budeme robiť tu?

847
00:42:12,340 --> 00:42:13,702
>> DIVÁKOV: Vrátite false
aj tam.

848
00:42:13,702 --> 00:42:15,040
>> JASON Hirschhorn: Oh, my
to na oboch miestach?

849
00:42:15,040 --> 00:42:15,650
>> DIVÁKOV: Jo.

850
00:42:15,650 --> 00:42:16,900
>> JASON Hirschhorn: OK.

851
00:42:16,900 --> 00:42:24,840

852
00:42:24,840 --> 00:42:26,160
Mali by sme ísť?

853
00:42:26,160 --> 00:42:26,980
Ach môj bože.

854
00:42:26,980 --> 00:42:27,290
Je mi to ľúto.

855
00:42:27,290 --> 00:42:28,480
Ospravedlňujem sa za obrazovku.

856
00:42:28,480 --> 00:42:30,530
Je to trochu desí nás.

857
00:42:30,530 --> 00:42:31,520
Tak si vyberte jednu z možností.

858
00:42:31,520 --> 00:42:35,260
Zero, podľa kódu, ukončí program.

859
00:42:35,260 --> 00:42:36,700
Jeden vloží niečo.

860
00:42:36,700 --> 00:42:37,990
Poďme vložte tri.

861
00:42:37,990 --> 00:42:42,900

862
00:42:42,900 --> 00:42:45,380
Vložka nebol úspešný.

863
00:42:45,380 --> 00:42:46,500
Idem vytlačiť.

864
00:42:46,500 --> 00:42:48,050
Nemám nič.

865
00:42:48,050 --> 00:42:48,450
OK.

866
00:42:48,450 --> 00:42:50,250
Možno, že to bola len náhoda.

867
00:42:50,250 --> 00:42:52,810
Vložte jeden.

868
00:42:52,810 --> 00:42:55,770
Nie je úspešná.

869
00:42:55,770 --> 00:42:57,470
OK.

870
00:42:57,470 --> 00:43:02,400
Poďme si prejsť GDB veľmi rýchlo
zistiť, čo sa deje.

871
00:43:02,400 --> 00:43:06,055
>> Nezabudnite gdb. / Názov vášho
Program nás dostane do GDB.

872
00:43:06,055 --> 00:43:07,610
Je to veľa zvládnuť?

873
00:43:07,610 --> 00:43:08,560
Bliká?

874
00:43:08,560 --> 00:43:10,400
Pravdepodobne.

875
00:43:10,400 --> 00:43:12,760
Zavrite oči a vziať nejaké hlboké
dýcha, ak vás omrzí

876
00:43:12,760 --> 00:43:13,580
z pohľadu na neho.

877
00:43:13,580 --> 00:43:14,200
Som v GDB.

878
00:43:14,200 --> 00:43:15,830
Čo je prvá vec, ktorú robím v GDB?

879
00:43:15,830 --> 00:43:17,050
Musíme prísť na to,
to, čo sa tu deje.

880
00:43:17,050 --> 00:43:17,310
Poďme sa pozrieť.

881
00:43:17,310 --> 00:43:21,650
Máme šesť minút na obrázku
čo sa deje.

882
00:43:21,650 --> 00:43:22,900
Prestávka hlavné.

883
00:43:22,900 --> 00:43:25,950

884
00:43:25,950 --> 00:43:28,130
A potom to, čo mám robiť?

885
00:43:28,130 --> 00:43:29,180
Carlos?

886
00:43:29,180 --> 00:43:31,060
Spustiť.

887
00:43:31,060 --> 00:43:32,250
OK.

888
00:43:32,250 --> 00:43:34,160
Poďme možnosť.

889
00:43:34,160 --> 00:43:36,330
A čo N robiť?

890
00:43:36,330 --> 00:43:38,480
Ďalšie.

891
00:43:38,480 --> 00:43:38,950
Jo.

892
00:43:38,950 --> 00:43:39,740
>> DIVÁKOV: Vari ste spomenul -

893
00:43:39,740 --> 00:43:45,230
ste to nepovedal, že hlava, to bolo
inicializovaná na hodnotu NULL na začiatku.

894
00:43:45,230 --> 00:43:47,140
Ale myslel som, že si povedal, že je v poriadku.

895
00:43:47,140 --> 00:43:50,040

896
00:43:50,040 --> 00:43:52,640
>> JASON Hirschhorn: Poďme - poďme sa pozrieť
v GDB, a potom pôjdeme späť.

897
00:43:52,640 --> 00:43:54,910
Ale vyzerá to, že už máte
niektoré myšlienky o tom, čo sa deje.

898
00:43:54,910 --> 00:43:58,340
Takže chceme vložiť niečo.

899
00:43:58,340 --> 00:43:59,390
OK.

900
00:43:59,390 --> 00:44:00,150
Máme vložiť.

901
00:44:00,150 --> 00:44:00,770
Prosím, zadajte int.

902
00:44:00,770 --> 00:44:01,990
Budeme vložte tri.

903
00:44:01,990 --> 00:44:03,000
A potom som na tejto trati.

904
00:44:03,000 --> 00:44:07,030
Ako mám ísť spustiť ladenie
vložka známe funkcie?

905
00:44:07,030 --> 00:44:08,280
Ach môj bože.

906
00:44:08,280 --> 00:44:10,990

907
00:44:10,990 --> 00:44:12,240
To je veľa.

908
00:44:12,240 --> 00:44:14,372

909
00:44:14,372 --> 00:44:16,445
Je to vyšilovat veľa?

910
00:44:16,445 --> 00:44:19,696

911
00:44:19,696 --> 00:44:21,680
>> DIVÁKOV: Oh, to zomrel.

912
00:44:21,680 --> 00:44:22,930
>> JASON Hirschhorn: som
vytiahol ho von.

913
00:44:22,930 --> 00:44:27,364

914
00:44:27,364 --> 00:44:28,310
OK.

915
00:44:28,310 --> 00:44:29,560
>> DIVÁKOV: Možno, že je to
druhý koniec drôtu.

916
00:44:29,560 --> 00:44:37,000

917
00:44:37,000 --> 00:44:39,470
>> JASON Hirschhorn: Wow.

918
00:44:39,470 --> 00:44:42,330
Takže spodnom riadku -

919
00:44:42,330 --> 00:44:43,470
Čo si hovoril?

920
00:44:43,470 --> 00:44:46,040
>> DIVÁKOV: Povedal som, že irónia technické
ťažkosti v tejto triede.

921
00:44:46,040 --> 00:44:46,410
>> JASON Hirschhorn: Ja viem.

922
00:44:46,410 --> 00:44:48,660
Kiež by som mal kontrolu nad tou časťou.

923
00:44:48,660 --> 00:44:49,910
[Nepočuteľný]

924
00:44:49,910 --> 00:44:54,430

925
00:44:54,430 --> 00:44:55,400
To znie skvele.

926
00:44:55,400 --> 00:44:58,680
Prečo nie vy začať premýšľať o tom,
to, čo sme mohli urobiť zle,

927
00:44:58,680 --> 00:45:01,140
a budeme späť za 90 sekúnd.

928
00:45:01,140 --> 00:46:18,160

929
00:46:18,160 --> 00:46:23,010
>> AVIC, budem sa vás opýtať, ako to chodí
vnútri insert_node ladiť.

930
00:46:23,010 --> 00:46:28,940

931
00:46:28,940 --> 00:46:31,460
Tak toto je miesto, kde sme naposledy skončili.

932
00:46:31,460 --> 00:46:35,110
Ako môžem ísť dovnútra insert_node, AVIC,
skúmať, čo sa deje?

933
00:46:35,110 --> 00:46:36,360
Čo GDB príkazu?

934
00:46:36,360 --> 00:46:41,050

935
00:46:41,050 --> 00:46:42,390
Prestávka by ma vziať dovnútra.

936
00:46:42,390 --> 00:46:46,200

937
00:46:46,200 --> 00:46:47,130
Má Marquise vedieť?

938
00:46:47,130 --> 00:46:48,240
>> DIVÁKOV: Čo?

939
00:46:48,240 --> 00:46:51,780
>> JASON Hirschhorn: Aký príkaz GDB
Používam ísť dovnútra tejto funkcie?

940
00:46:51,780 --> 00:46:52,070
>> DIVÁKOV: krok?

941
00:46:52,070 --> 00:46:55,140
>> JASON Hirschhorn: Krok cez
S. To ma berie dovnútra.

942
00:46:55,140 --> 00:46:55,476
OK.

943
00:46:55,476 --> 00:46:58,040
New_node mallocing nejaký priestor.

944
00:46:58,040 --> 00:46:59,120
To všetko vyzerá ako jeho bude.

945
00:46:59,120 --> 00:47:00,370
Poďme preskúmať new_node.

946
00:47:00,370 --> 00:47:03,270

947
00:47:03,270 --> 00:47:05,410
To má nejakú adresu v pamäti.

948
00:47:05,410 --> 00:47:07,440
Poďme sa pozrieť -

949
00:47:07,440 --> 00:47:08,500
že je všetko v poriadku.

950
00:47:08,500 --> 00:47:12,220
Takže všetko tu zdá sa,
pracovať správne.

951
00:47:12,220 --> 00:47:14,530
>> DIVÁKOV: Aký je rozdiel
medzi P a displej?

952
00:47:14,530 --> 00:47:16,160
>> JASON Hirschhorn: P je skratka pre tlač.

953
00:47:16,160 --> 00:47:19,310
A tak sa pýtate, čo je
Rozdiel medzi týmto a to?

954
00:47:19,310 --> 00:47:22,330
V tomto prípade nič.

955
00:47:22,330 --> 00:47:26,960
Ale všeobecne sú
niektoré rozdiely.

956
00:47:26,960 --> 00:47:28,220
A mali by ste sa pozrieť do manuálu GDB.

957
00:47:28,220 --> 00:47:29,560
Ale v tomto prípade nič.

958
00:47:29,560 --> 00:47:31,460
Máme tendenciu používať tlač, hoci, pretože
nepotrebujeme robiť oveľa viac, než

959
00:47:31,460 --> 00:47:33,960
vytlačiť jednu hodnotu.

960
00:47:33,960 --> 00:47:34,640
>> OK.

961
00:47:34,640 --> 00:47:40,300
Takže sme na riadku 80 nášho kódu,
nastavenie uzla * curry rovnajúcu sa zoznamu.

962
00:47:40,300 --> 00:47:42,500
Poďme vytlačiť curry.

963
00:47:42,500 --> 00:47:45,260

964
00:47:45,260 --> 00:47:46,840
To sa rovná zoznamu.

965
00:47:46,840 --> 00:47:48,850
Sladké.

966
00:47:48,850 --> 00:47:49,340
Počkajte.

967
00:47:49,340 --> 00:47:50,590
To sa rovná niečo.

968
00:47:50,590 --> 00:47:53,680

969
00:47:53,680 --> 00:47:56,190
To sa nezdá byť v poriadku.

970
00:47:56,190 --> 00:47:56,840
Tam ideme.

971
00:47:56,840 --> 00:47:59,470
Je to preto, že v GDB, vpravo, ak
je to čiara, že ste na to

972
00:47:59,470 --> 00:48:00,330
nebol vykonaný ešte.

973
00:48:00,330 --> 00:48:03,100
Takže je potrebné, aby skutočne písať
Vedľa prevedenie linky

974
00:48:03,100 --> 00:48:05,230
ako vidieť svoje výsledky.

975
00:48:05,230 --> 00:48:06,680
Tak sme tu.

976
00:48:06,680 --> 00:48:09,490
Len sme vykonali tento riadok,
predchádzajúce rovná null.

977
00:48:09,490 --> 00:48:13,590
Takže znova, ak tlačíme predchádzajúce
nebudeme vidieť nič divného.

978
00:48:13,590 --> 00:48:18,680
Ale ak sme skutočne spustiť, že
linka, potom uvidíme

979
00:48:18,680 --> 00:48:20,380
že linka funguje.

980
00:48:20,380 --> 00:48:21,060
>> Takže máme curry.

981
00:48:21,060 --> 00:48:23,180
Tí, ktorí sú obaja dobré.

982
00:48:23,180 --> 00:48:24,010
Je to tak?

983
00:48:24,010 --> 00:48:28,130
Teraz sme na tejto trati tu.

984
00:48:28,130 --> 00:48:29,310
Kým Mena nie je rovné null.

985
00:48:29,310 --> 00:48:31,110
No, čo robí bc rovnaké?

986
00:48:31,110 --> 00:48:32,450
Práve sme videli, že sa rovnal null.

987
00:48:32,450 --> 00:48:33,210
Vytlačiť sme to.

988
00:48:33,210 --> 00:48:35,110
Budem ju vytlačiť znova.

989
00:48:35,110 --> 00:48:36,720
Tak je to, že zatiaľ čo slučka
bude vykonávať?

990
00:48:36,720 --> 00:48:37,270
>> Divákov: Nie

991
00:48:37,270 --> 00:48:39,790
>> JASON Hirschhorn: Takže, keď som napísal, že
linka, vidíte, sme skočili po celú cestu

992
00:48:39,790 --> 00:48:41,390
až na dno, vráti false.

993
00:48:41,390 --> 00:48:44,520
A potom sa budeme vracať false
a vrátiť sa do nášho programu a

994
00:48:44,520 --> 00:48:48,020
nakoniec vytlačiť, ako sme videli,
vložka nebola úspešná.

995
00:48:48,020 --> 00:48:51,010
Takže, niekto nejaké nápady na to, čo
musíme urobiť, aby tento problém vyriešiť?

996
00:48:51,010 --> 00:48:54,200

997
00:48:54,200 --> 00:48:57,570
Budem čakať, kým neuvidím
pár rúk nahor.

998
00:48:57,570 --> 00:48:58,830
Nechceli sme spustiť tento.

999
00:48:58,830 --> 00:49:01,660
Majte na pamäti, to bol prvý
čo sme robili.

1000
00:49:01,660 --> 00:49:02,430
Nebudem robiť pár.

1001
00:49:02,430 --> 00:49:03,670
Budem robiť len málo.

1002
00:49:03,670 --> 00:49:04,830
Vzhľadom k tomu pár znamená dva.

1003
00:49:04,830 --> 00:49:07,620
Počkám na viac ako dva.

1004
00:49:07,620 --> 00:49:10,690
>> Prvý vloženie, bc,
v predvolenom nastavení sa rovná null.

1005
00:49:10,690 --> 00:49:14,050
A táto slučka vykonáva iba
ak bc nie je null.

1006
00:49:14,050 --> 00:49:18,740
Tak ako môžem získať okolo tohto?

1007
00:49:18,740 --> 00:49:19,990
Vidím tri ruky.

1008
00:49:19,990 --> 00:49:28,490

1009
00:49:28,490 --> 00:49:29,780
Počkám na viac ako tri.

1010
00:49:29,780 --> 00:49:33,460

1011
00:49:33,460 --> 00:49:35,940
Marcus, čo si o tom myslíte?

1012
00:49:35,940 --> 00:49:37,730
>> DIVÁKOV: No, ak to budete potrebovať, aby
vykonať viac ako raz, stačí

1013
00:49:37,730 --> 00:49:39,948
zmeniť ho na do-while.

1014
00:49:39,948 --> 00:49:41,250
>> JASON Hirschhorn: OK.

1015
00:49:41,250 --> 00:49:44,240
Bude to vyriešiť náš problém, nie?

1016
00:49:44,240 --> 00:49:47,750
>> DIVÁKOV: V tomto prípade nie je, pretože
Skutočnosť, že zoznam je prázdny.

1017
00:49:47,750 --> 00:49:52,150
Takže potom ste pravdepodobne stačí pridať
vyhlásenie, že v prípade, že slučka ukončí

1018
00:49:52,150 --> 00:49:55,312
potom musíte byť na konci roka
list, na ktorom mieste sa vám

1019
00:49:55,312 --> 00:49:56,562
stačí vložiť ju.

1020
00:49:56,562 --> 00:49:58,920

1021
00:49:58,920 --> 00:49:59,680
>> JASON Hirschhorn: Páči sa mi to.

1022
00:49:59,680 --> 00:50:00,500
To dáva zmysel.

1023
00:50:00,500 --> 00:50:03,390
Je-li slučka ukončí -

1024
00:50:03,390 --> 00:50:04,800
preto, že sa vrátim false tu.

1025
00:50:04,800 --> 00:50:08,220
Takže ak slučky východov, potom sme na
koniec zoznamu, alebo možno

1026
00:50:08,220 --> 00:50:10,690
začiatok zoznamu, ak tam nič nie je
je to, ktoré je rovnaké ako na konci.

1027
00:50:10,690 --> 00:50:12,770
Takže teraz chceme vložiť
niečo tu.

1028
00:50:12,770 --> 00:50:17,380
Tak ako to, že kód vyzerať, Marcus?

1029
00:50:17,380 --> 00:50:21,600
>> DIVÁKOV: Ak ste už dostal uzol
malloced, mohol by si povedať,

1030
00:50:21,600 --> 00:50:25,400
new_node-> ďalšie rovný null, pretože
, Že musí byť na konci.

1031
00:50:25,400 --> 00:50:27,510
Alebo new_node-> Ďalšie rovná null.

1032
00:50:27,510 --> 00:50:27,765
>> JASON Hirschhorn: OK.

1033
00:50:27,765 --> 00:50:28,190
Prepáčte.

1034
00:50:28,190 --> 00:50:35,760
New_node-> ďalšie rovný null
preto, že sme na konci.

1035
00:50:35,760 --> 00:50:36,460
To nie je dať dovnútra

1036
00:50:36,460 --> 00:50:37,710
Ako môžeme dať je na zozname?

1037
00:50:37,710 --> 00:50:46,130

1038
00:50:46,130 --> 00:50:46,460
Správne.

1039
00:50:46,460 --> 00:50:47,750
To je len nastavením rovná.

1040
00:50:47,750 --> 00:50:50,940
No, ako to vlastne
vložte ho do zoznamu?

1041
00:50:50,940 --> 00:50:54,170
Čo ukazuje na
koniec zoznamu?

1042
00:50:54,170 --> 00:50:56,090
>> DIVÁKOV: Head.

1043
00:50:56,090 --> 00:50:57,566
>> JASON Hirschhorn: Je nám ľúto?

1044
00:50:57,566 --> 00:50:59,440
>> DIVÁKOV: Hlava smeruje
na koniec zoznamu.

1045
00:50:59,440 --> 00:51:01,480
>> JASON Hirschhorn: Ak nie je nič v
zoznam, hlava smeruje k

1046
00:51:01,480 --> 00:51:04,170
koniec zoznamu.

1047
00:51:04,170 --> 00:51:06,920
Takže to bude fungovať pre
prvý vloženie.

1048
00:51:06,920 --> 00:51:09,810
A čo v prípade, že sú pár
veci na zozname?

1049
00:51:09,810 --> 00:51:12,470
Ako nechceme nastaviť
hlava rovná new_node.

1050
00:51:12,470 --> 00:51:13,790
Čo chceme, aby tam robiť?

1051
00:51:13,790 --> 00:51:15,610
Jo?

1052
00:51:15,610 --> 00:51:16,860
Pravdepodobne predchádzajúce.

1053
00:51:16,860 --> 00:51:23,560

1054
00:51:23,560 --> 00:51:24,810
Bude to fungovať?

1055
00:51:24,810 --> 00:51:28,950

1056
00:51:28,950 --> 00:51:33,050
Pripomeňme, že predchádzajúce je len
ukazovateľ na uzol.

1057
00:51:33,050 --> 00:51:34,770
A predchádzajúce je lokálna premenná.

1058
00:51:34,770 --> 00:51:38,080
Takže tento riadok bude nastavený lokálne premenné,
predchádzajúcej, ktorá sa rovná alebo

1059
00:51:38,080 --> 00:51:39,380
smerovať k tomuto novému uzla.

1060
00:51:39,380 --> 00:51:41,500
To nebude v skutočnosti dať
v našom zozname, hoci.

1061
00:51:41,500 --> 00:51:44,330
Ako sme dali, že v našom zozname?

1062
00:51:44,330 --> 00:51:45,620
Akchar?

1063
00:51:45,620 --> 00:51:46,870
>> DIVÁKOV: Myslím, že vám
to aktuálne-> ďalšie.

1064
00:51:46,870 --> 00:51:50,186

1065
00:51:50,186 --> 00:51:52,550
>> JASON Hirschhorn: OK.

1066
00:51:52,550 --> 00:51:54,010
akt-> ďalšie.

1067
00:51:54,010 --> 00:51:58,768
Takže znova, jediný dôvod, prečo sme sa
Tu je to, čo robí prúd rovný?

1068
00:51:58,768 --> 00:51:59,760
>> DIVÁKOV: Rovná null.

1069
00:51:59,760 --> 00:52:01,790
>> JASON Hirschhorn: A tak čo
sa stane, keď budeme robiť null-> ďalšie?

1070
00:52:01,790 --> 00:52:02,810
Čo dostaneme?

1071
00:52:02,810 --> 00:52:04,060
Dostaneme segmentation fault.

1072
00:52:04,060 --> 00:52:06,600

1073
00:52:06,600 --> 00:52:08,880
>> DIVÁKOV: Do bc rovná null.

1074
00:52:08,880 --> 00:52:10,760
>> JASON Hirschhorn: To je to isté
ako prev, hoci, pretože tam je

1075
00:52:10,760 --> 00:52:12,820
lokálne premenná sme nastavenie
rovnajúce sa tejto novej uzla.

1076
00:52:12,820 --> 00:52:16,680

1077
00:52:16,680 --> 00:52:20,920
Vráťme sa k nášmu obrazu
vkladanie niečo.

1078
00:52:20,920 --> 00:52:25,500
Povedzme, že sme vkladanie na koniec
zoznamu, tak tu.

1079
00:52:25,500 --> 00:52:30,010
Máme aktuálne ukazovateľ, ktorý je
ukazuje na null a predchádzajúci bod

1080
00:52:30,010 --> 00:52:32,800
že je ukazuje na 8..

1081
00:52:32,800 --> 00:52:35,330
Takže to, čo potrebujeme aktualizovať, Avi?

1082
00:52:35,330 --> 00:52:36,680
>> DIVÁKOV: Predchádzajúca-> ďalej?

1083
00:52:36,680 --> 00:52:41,980
>> JASON Hirschhorn: Predchádzajúca-> ďalšie je to, čo
chceme aktualizovať, pretože to

1084
00:52:41,980 --> 00:52:44,960
bude skutočne vložte ho na
koniec zoznamu.

1085
00:52:44,960 --> 00:52:47,220
Máme ešte jednu chybu, aj keď,
že budeme bežať do.

1086
00:52:47,220 --> 00:52:50,090
Čo je to chyba?

1087
00:52:50,090 --> 00:52:50,790
Jo?

1088
00:52:50,790 --> 00:52:53,860
>> DIVÁKOV: Bude to návrat
false v tomto prípade?

1089
00:52:53,860 --> 00:52:56,380
>> JASON Hirschhorn: Oh, je sa
chystá sa vrátiť false.

1090
00:52:56,380 --> 00:52:57,430
Ale je tu ďalší problém.

1091
00:52:57,430 --> 00:52:58,930
Takže budeme musieť dať na oplátku skutočné.

1092
00:52:58,930 --> 00:53:01,370
>> DIVÁKOV: Moja predchádzajúca stále rovnaká
null v hornej časti zoznamu?

1093
00:53:01,370 --> 00:53:03,645
>> JASON Hirschhorn: Tak ešte predchádzajúca
rovná null na samom začiatku.

1094
00:53:03,645 --> 00:53:07,480

1095
00:53:07,480 --> 00:53:10,440
Takže, ako môžeme dostať cez to?

1096
00:53:10,440 --> 00:53:10,950
Jo?

1097
00:53:10,950 --> 00:53:15,280
>> DIVÁKOV: Myslím, že môžete urobiť kontrolu
pred while, aby zistil, či je to

1098
00:53:15,280 --> 00:53:16,610
prázdny zoznam.

1099
00:53:16,610 --> 00:53:17,000
>> JASON Hirschhorn: OK.

1100
00:53:17,000 --> 00:53:17,710
Takže poďme tu.

1101
00:53:17,710 --> 00:53:18,530
Vykonajte kontrolu.

1102
00:53:18,530 --> 00:53:19,380
Ak -

1103
00:53:19,380 --> 00:53:20,770
>> DIVÁKOV: Takže ak hlava
rovná sa rovná null.

1104
00:53:20,770 --> 00:53:24,300

1105
00:53:24,300 --> 00:53:26,320
>> JASON Hirschhorn: Keď je hlava
rovná sa rovná null -

1106
00:53:26,320 --> 00:53:27,790
že nám povie, či je to prázdny zoznam.

1107
00:53:27,790 --> 00:53:31,090
>> DIVÁKOV: A potom ste
to hlava rovná nové.

1108
00:53:31,090 --> 00:53:34,740
>> JASON Hirschhorn: Head
rovná new_node?

1109
00:53:34,740 --> 00:53:35,730
A čo ešte musíme urobiť?

1110
00:53:35,730 --> 00:53:37,020
>> DIVÁKOV: A potom sa vrátiť true.

1111
00:53:37,020 --> 00:53:37,535
>> JASON Hirschhorn: Nie tak celkom.

1112
00:53:37,535 --> 00:53:38,785
Chýba nám jeden krok.

1113
00:53:38,785 --> 00:53:41,590

1114
00:53:41,590 --> 00:53:43,710
>> DIVÁKOV: New_node ďalšie
má upozorniť na hodnotu null.

1115
00:53:43,710 --> 00:53:44,570
>> JASON Hirschhorn: Presne tak, Alden.

1116
00:53:44,570 --> 00:53:46,600
A potom sa môžeme vrátiť true.

1117
00:53:46,600 --> 00:53:47,560
OK.

1118
00:53:47,560 --> 00:53:51,630
Ale je to stále dobrý nápad urobiť veci
na konci zoznamu, nie?

1119
00:53:51,630 --> 00:53:51,950
Dobrá.

1120
00:53:51,950 --> 00:53:54,450
Stále by v skutočnosti mohli dostať
na koniec zoznamu.

1121
00:53:54,450 --> 00:53:57,870
Tak je tento kód v poriadku, ak sme na
koniec zoznamu, a tam sú niektoré

1122
00:53:57,870 --> 00:53:59,120
veci na zozname?

1123
00:53:59,120 --> 00:54:01,830

1124
00:54:01,830 --> 00:54:02,040
Je to tak?

1125
00:54:02,040 --> 00:54:03,540
Vzhľadom k tomu máme ešte Marcusov nápad.

1126
00:54:03,540 --> 00:54:06,870
Mohli by sme opustiť túto slučku, pretože
sme na konci zoznamu.

1127
00:54:06,870 --> 00:54:09,308
Takže sme stále chcú to
kód tu dole?

1128
00:54:09,308 --> 00:54:10,520
>> DIVÁKOV: Áno.

1129
00:54:10,520 --> 00:54:11,000
>> JASON Hirschhorn: Jo.

1130
00:54:11,000 --> 00:54:14,190
A čo musíme zmeniť to?

1131
00:54:14,190 --> 00:54:15,440
Pravda.

1132
00:54:15,440 --> 00:54:19,580

1133
00:54:19,580 --> 00:54:21,640
Znie to dobre
všetkým tak ďaleko?

1134
00:54:21,640 --> 00:54:22,420
Niekto nejaké -

1135
00:54:22,420 --> 00:54:23,480
Avi, máte niečo dodať?

1136
00:54:23,480 --> 00:54:23,920
>> Divákov: Nie

1137
00:54:23,920 --> 00:54:25,276
>> JASON Hirschhorn: OK.

1138
00:54:25,276 --> 00:54:27,010
Takže sme urobili pár zmien.

1139
00:54:27,010 --> 00:54:29,540
Urobili sme túto kontrolu, než sme
šiel na prázdny zoznam.

1140
00:54:29,540 --> 00:54:31,790
Takže sme sa postarali o prázdneho zoznamu.

1141
00:54:31,790 --> 00:54:35,500
A tu sme sa starali o vkladaní
niečo na koniec zoznamu.

1142
00:54:35,500 --> 00:54:38,930
Takže to vyzerá, že tento zatiaľ čo slučka odberu
starostlivosť o veci medzi tým,

1143
00:54:38,930 --> 00:54:41,920
niekde v zozname, ak
sú veci, ktoré v zozname.

1144
00:54:41,920 --> 00:54:42,280
>> OK.

1145
00:54:42,280 --> 00:54:44,310
Poďme tento program spustiť znova.

1146
00:54:44,310 --> 00:54:50,170

1147
00:54:50,170 --> 00:54:50,755
Nie je úspešná.

1148
00:54:50,755 --> 00:54:52,190
>> DIVÁKOV: Vy ste to.

1149
00:54:52,190 --> 00:54:53,940
>> JASON Hirschhorn: Oh,
Neurobil som to.

1150
00:54:53,940 --> 00:54:56,250
Dobrý postreh, Michael.

1151
00:54:56,250 --> 00:54:57,500
Poďme pridať značku spojenú.

1152
00:54:57,500 --> 00:55:01,590

1153
00:55:01,590 --> 00:55:04,830
Linka 87 je tam chyba.

1154
00:55:04,830 --> 00:55:05,420
Linka 87.

1155
00:55:05,420 --> 00:55:06,600
Alden, to bol linku, ktorú mi dal.

1156
00:55:06,600 --> 00:55:08,962
Čo sa deje?

1157
00:55:08,962 --> 00:55:10,710
>> DIVÁKOV: Musí to byť null.

1158
00:55:10,710 --> 00:55:11,000
>> JASON Hirschhorn: Výborný.

1159
00:55:11,000 --> 00:55:11,630
Presne tak.

1160
00:55:11,630 --> 00:55:13,290
Malo by to byť null.

1161
00:55:13,290 --> 00:55:15,210
Poďme urobiť znovu.

1162
00:55:15,210 --> 00:55:17,220
Kompilácie.

1163
00:55:17,220 --> 00:55:17,890
OK.

1164
00:55:17,890 --> 00:55:19,400
Poďme vložte tri.

1165
00:55:19,400 --> 00:55:20,570
Vložka bola úspešná.

1166
00:55:20,570 --> 00:55:21,660
Poďme ju vytlačiť.

1167
00:55:21,660 --> 00:55:23,590
Ach, keby len mohli skontrolovať.

1168
00:55:23,590 --> 00:55:25,500
Ale my sme neurobili
tlač ešte funkciu.

1169
00:55:25,500 --> 00:55:27,840
Poďme zadať niečo iné.

1170
00:55:27,840 --> 00:55:29,090
Čo by sme mali vstúpiť?

1171
00:55:29,090 --> 00:55:31,120

1172
00:55:31,120 --> 00:55:31,940
>> DIVÁKOV: Sedem.

1173
00:55:31,940 --> 00:55:33,340
>> JASON Hirschhorn: Seven?

1174
00:55:33,340 --> 00:55:34,590
>> DIVÁKOV: Áno.

1175
00:55:34,590 --> 00:55:38,680

1176
00:55:38,680 --> 00:55:39,780
>> JASON Hirschhorn: Máme poruchu seg.

1177
00:55:39,780 --> 00:55:43,760
Takže máme jednu, ale jasne
nemôže dostať dva.

1178
00:55:43,760 --> 00:55:45,690
Je 5:07.

1179
00:55:45,690 --> 00:55:48,370
Takže by sme to mohli ladiť
po dobu troch minút.

1180
00:55:48,370 --> 00:55:51,240
Ale ja idem na nás tu nechať
a prejsť na hash tabuľky.

1181
00:55:51,240 --> 00:55:54,290
Ale opäť, odpovede tohto kódu
Budem poslať e-mailom na vás trochu.

1182
00:55:54,290 --> 00:55:55,440
Sme veľmi blízko k nej.

1183
00:55:55,440 --> 00:55:58,300
Vrelo odporúčame vám zistiť,
čo sa deje tu a opraviť ju.

1184
00:55:58,300 --> 00:56:02,400
Tak som vám pošleme tento kód ako
dobre a riešenia -

1185
00:56:02,400 --> 00:56:03,670
pravdepodobne riešenie neskôr.

1186
00:56:03,670 --> 00:56:05,110
Najprv tento kód.

1187
00:56:05,110 --> 00:56:08,290
>> Ďalšia vec, ktorú chcem urobiť, ako my
Povrchová úprava je nám nie je uvoľnené nič.

1188
00:56:08,290 --> 00:56:10,370
Takže chcem vám ukázať, čo
Valgrind vyzerá.

1189
00:56:10,370 --> 00:56:14,310
Ak narazíme Valgrind hranice
na našom programe,. / spojené.

1190
00:56:14,310 --> 00:56:22,540
Opäť platí, že podľa tohto snímku, sa
by mal bežať Valgrind s nejakým typom

1191
00:56:22,540 --> 00:56:26,410
možnosť, v tomto prípade
- Únik kontrola = plná.

1192
00:56:26,410 --> 00:56:27,660
Takže poďme napísať Valgrind
- Únik kontrola = plná.

1193
00:56:27,660 --> 00:56:31,910

1194
00:56:31,910 --> 00:56:35,080
Takže to bude bežať Valgrind
na našom programe.

1195
00:56:35,080 --> 00:56:37,000
A teraz sa program vlastne beží.

1196
00:56:37,000 --> 00:56:40,190
Takže ideme na to bežať rovnako ako
pred, dať niečo dovnútra

1197
00:56:40,190 --> 00:56:40,830
Chystám sa dať v troch.

1198
00:56:40,830 --> 00:56:41,790
To funguje.

1199
00:56:41,790 --> 00:56:43,202
Nebudem sa snažiť dať do niečoho
iného, ​​pretože budeme

1200
00:56:43,202 --> 00:56:44,710
dostať seg false v tomto prípade.

1201
00:56:44,710 --> 00:56:46,700
Tak som len tak odísť.

1202
00:56:46,700 --> 00:56:50,160
>> A teraz vidíte, tu dole
úniku a zhrnutie haldy.

1203
00:56:50,160 --> 00:56:52,310
To sú dobré veci, ktoré
Ak chcete vyskúšať.

1204
00:56:52,310 --> 00:56:56,780
Takže zhrnutie haldy - to hovorí, v prevádzke
na výstupe - osem bajtov v jednom bloku.

1205
00:56:56,780 --> 00:56:58,370
To jeden blok
uzol sme malloced.

1206
00:56:58,370 --> 00:57:02,230
Michael, si hovoril pred uzol je osem
uhryznutie, pretože má celé číslo

1207
00:57:02,230 --> 00:57:02,680
a ukazovateľ.

1208
00:57:02,680 --> 00:57:04,550
Tak to je náš uzol.

1209
00:57:04,550 --> 00:57:08,170
A potom sa hovorí, že sme použili malloc
sedemkrát a budeme oslobodení

1210
00:57:08,170 --> 00:57:08,940
niečo šesťkrát.

1211
00:57:08,940 --> 00:57:13,680
Ale my sme nikdy volal zadarmo, takže nemám
tušenie, čo je to hovoríš.

1212
00:57:13,680 --> 00:57:18,490
>> Ale stačí, keď poviem, že keď si
program beží, malloc je nazývaný

1213
00:57:18,490 --> 00:57:20,330
v niektorých iných miestach, kde sa
Nemusíte sa obávať.

1214
00:57:20,330 --> 00:57:22,460
Takže malloc bol pravdepodobne nazvaný
v niektorých miestach.

1215
00:57:22,460 --> 00:57:24,480
Nepotrebujeme robiť starosti, kde.

1216
00:57:24,480 --> 00:57:26,240
Ale je to naozaj my.

1217
00:57:26,240 --> 00:57:27,380
Prvý riadok je nám.

1218
00:57:27,380 --> 00:57:28,320
Opustili sme tento blok.

1219
00:57:28,320 --> 00:57:30,330
A vidíte, že tu
v súhrne úniku.

1220
00:57:30,330 --> 00:57:31,950
Ešte dosiahnuteľný -

1221
00:57:31,950 --> 00:57:32,930
osem bajtov v jednom bloku.

1222
00:57:32,930 --> 00:57:34,100
To znamená, že pamäť -

1223
00:57:34,100 --> 00:57:35,730
sme unikli, že pamäť.

1224
00:57:35,730 --> 00:57:37,570
Definitívne stratil -

1225
00:57:37,570 --> 00:57:38,770
niečo, čo sa stratil nadobro.

1226
00:57:38,770 --> 00:57:40,590
Všeobecne platí, že nebudete
nič vidieť tu.

1227
00:57:40,590 --> 00:57:44,780
Napriek tomu je všeobecne dostupný, ak
budete vidieť veci, kde budete chcieť

1228
00:57:44,780 --> 00:57:48,900
sa pozrieť, čo kód, ktorý by mal
sa oslobodil, ale ste zabudli oslobodiť.

1229
00:57:48,900 --> 00:57:53,170
>> A potom, ak to nie je tento prípad,
pokiaľ sme urobili všetko zadarmo,

1230
00:57:53,170 --> 00:57:54,360
môžeme zistiť, že.

1231
00:57:54,360 --> 00:57:57,330
Povedzme, spustite program
nie je uvedenie v ničom.

1232
00:57:57,330 --> 00:57:59,800
Uvidíte tu v použití na výstupe -

1233
00:57:59,800 --> 00:58:01,310
nula bajtov nulových blokov.

1234
00:58:01,310 --> 00:58:06,310
To znamená, že skoro nič neopustila
ak tento program ukončený.

1235
00:58:06,310 --> 00:58:12,090
Takže pred zapnutím v pset6, spustite Valgrind
a uistite sa, že nemáte

1236
00:58:12,090 --> 00:58:15,310
uvoľňovanie každej pamäte vo vašom programe.

1237
00:58:15,310 --> 00:58:17,910
Ak máte akékoľvek otázky s Valgrind,
neváhajte osloviť.

1238
00:58:17,910 --> 00:58:18,700
Ale to je, ako ho použiť.

1239
00:58:18,700 --> 00:58:20,890
Veľmi jednoduchá - zistiť, či ste
majú v užívaní na výstupe -

1240
00:58:20,890 --> 00:58:22,270
žiadne bytov v akýchkoľvek blokov.

1241
00:58:22,270 --> 00:58:27,890

1242
00:58:27,890 --> 00:58:29,580
>> Takže sme pracovali na vloženie uzla.

1243
00:58:29,580 --> 00:58:33,840
Mal som dve ďalšie funkcie tu -
tlačiť uzly a uzly zadarmo.

1244
00:58:33,840 --> 00:58:37,780
Opäť platí, že sa jedná o funkcie, ktoré sú
bude pre vás dobré praxe

1245
00:58:37,780 --> 00:58:40,990
pretože vám pomôže nielen s
tieto cvičenia vzorky, ale tiež

1246
00:58:40,990 --> 00:58:42,180
na problém nastaviť.

1247
00:58:42,180 --> 00:58:44,230
Oni máp na celkom blízko k veciam
budete musieť urobiť v

1248
00:58:44,230 --> 00:58:45,010
problém nastaviť.

1249
00:58:45,010 --> 00:58:47,640
Ale ja chcem, aby sa ubezpečil,
sa dotkneme na všetko.

1250
00:58:47,640 --> 00:58:50,400
A hash tabuľky sú tiež veľmi dôležité, aby
čo robíme v časti tejto

1251
00:58:50,400 --> 00:58:51,980
týždeň - alebo v sade problém.

1252
00:58:51,980 --> 00:58:55,200
>> Takže ideme dokončiť časť
hovorí o hash tabuľky.

1253
00:58:55,200 --> 00:58:58,140
Ak zistíte, že som
malý hash tabuľky.

1254
00:58:58,140 --> 00:59:00,020
To nie je to, čo hovoríme
o, však.

1255
00:59:00,020 --> 00:59:03,540
Hovoríme o iný
typ hash tabuľky.

1256
00:59:03,540 --> 00:59:07,300
A v jeho jadre, hash tabuľky
nie je nič viac než

1257
00:59:07,300 --> 00:59:08,860
pole a haš funkcie.

1258
00:59:08,860 --> 00:59:11,150
Budeme hovoriť na chvíľu len
uistite sa, že každý chápe, čo je to

1259
00:59:11,150 --> 00:59:12,110
hash funkcie.

1260
00:59:12,110 --> 00:59:15,420
A ja vám hovorím teraz, že je
nič viac než dve veci -

1261
00:59:15,420 --> 00:59:18,590
pole a haš funkcie.

1262
00:59:18,590 --> 00:59:20,716
A tu sú kroky, prostredníctvom
ktoré toto funguje.

1263
00:59:20,716 --> 00:59:31,560

1264
00:59:31,560 --> 00:59:32,810
>> Tu je náš poľa.

1265
00:59:32,810 --> 00:59:38,460

1266
00:59:38,460 --> 00:59:39,460
Tu je naša funkcia.

1267
00:59:39,460 --> 00:59:43,180
Najmä, hashovacie funkcie je potrebné
urobiť pár vecí s tým.

1268
00:59:43,180 --> 00:59:45,040
Ja budem hovoriť konkrétne
o tento problém nastaviť.

1269
00:59:45,040 --> 00:59:46,450
Je to pravdepodobne bude
sa v reťazci.

1270
00:59:46,450 --> 00:59:50,570

1271
00:59:50,570 --> 00:59:51,770
A čo to ide vrátiť?

1272
00:59:51,770 --> 00:59:52,640
Aký typ dát?

1273
00:59:52,640 --> 00:59:54,260
Alden?

1274
00:59:54,260 --> 00:59:55,760
Váš hash funkcie vrátiť?

1275
00:59:55,760 --> 00:59:58,760
Číslo.

1276
00:59:58,760 --> 01:00:01,700
Tak toto je to, čo hash
Tabuľka sa skladá z -

1277
01:00:01,700 --> 01:00:05,430
tabuľka vo forme poľa
a haš funkcie.

1278
01:00:05,430 --> 01:00:06,010
Ako to funguje?

1279
01:00:06,010 --> 01:00:07,300
Pracuje v troch krokoch.

1280
01:00:07,300 --> 01:00:08,740
Dávame mu kľúč.

1281
01:00:08,740 --> 01:00:11,470
V tomto prípade, dáme to reťazec.

1282
01:00:11,470 --> 01:00:18,140
Hovoríme funkcia hash za prvý krok
na kľúč a dostaneme hodnotu.

1283
01:00:18,140 --> 01:00:20,310
>> Konkrétne budeme hovoriť
dostaneme číslo.

1284
01:00:20,310 --> 01:00:25,630
To celé číslo, sú veľmi špecifické
hranice toho, čo môže byť, že celé číslo.

1285
01:00:25,630 --> 01:00:28,880
V tomto príklade, naše pole
o veľkosti tri.

1286
01:00:28,880 --> 01:00:32,330
Takže to, čo čísla možno, že číslo je.

1287
01:00:32,330 --> 01:00:35,970
Aký je rozsah platných hodnôt pre
že celé číslo, návratový typ tejto

1288
01:00:35,970 --> 01:00:37,220
hash funkcie?

1289
01:00:37,220 --> 01:00:40,440

1290
01:00:40,440 --> 01:00:42,110
Nula, jedna a dve.

1291
01:00:42,110 --> 01:00:46,060
Bod hašovacej funkcie je
prísť na miesto v poli

1292
01:00:46,060 --> 01:00:47,790
kde je naším kľúčovým deje.

1293
01:00:47,790 --> 01:00:51,290
Existujú iba tri možné
miesta tu -

1294
01:00:51,290 --> 01:00:52,130
nula, jeden, alebo dva.

1295
01:00:52,130 --> 01:00:55,360
Takže táto funkcia lepšiu návratnosť
nula, jeden, alebo dva.

1296
01:00:55,360 --> 01:00:58,740
Niektoré platný Index v tomto poli.

1297
01:00:58,740 --> 01:01:02,770
>> A potom v závislosti na tom, kde sa vráti,
môžete vidieť, že pole otvorené

1298
01:01:02,770 --> 01:01:03,730
uholník hodnotu.

1299
01:01:03,730 --> 01:01:05,800
To je miesto, kde sme dali kľúč.

1300
01:01:05,800 --> 01:01:11,280
Tak sme hodiť do tekvice,
dostaneme von nulu.

1301
01:01:11,280 --> 01:01:15,540
Na poli držiaku 0, dáme tekvicu.

1302
01:01:15,540 --> 01:01:21,070
Hodíme u mačiek, dostaneme sa na jednu.

1303
01:01:21,070 --> 01:01:24,110
Dali sme mačku v jednom.

1304
01:01:24,110 --> 01:01:25,480
Dali sme do pavúka.

1305
01:01:25,480 --> 01:01:26,710
Vystupujeme dva.

1306
01:01:26,710 --> 01:01:30,200
Dali sme pavúka na pole držiaku dvoch.

1307
01:01:30,200 --> 01:01:32,300
Bolo by to pekné, keby
to fungovalo takto.

1308
01:01:32,300 --> 01:01:35,570
Ale bohužiaľ, ako uvidíme,
je to trochu zložitejšie.

1309
01:01:35,570 --> 01:01:37,570
>> Ako sa tam dostaneme, Akékoľvek otázky
o tento základný

1310
01:01:37,570 --> 01:01:38,820
set-up z hash tabuľky?

1311
01:01:38,820 --> 01:01:49,050

1312
01:01:49,050 --> 01:01:51,940
To je obraz presne
čo nakreslil na tabuľu.

1313
01:01:51,940 --> 01:01:55,420
Ale od tej doby sme ju nakreslil na tabuľu, som
Nehodlám ísť do toho ďalej.

1314
01:01:55,420 --> 01:02:00,430
V podstate kľúče, mágia čierna skrinka -
alebo v tomto prípade, teal box - z

1315
01:02:00,430 --> 01:02:02,410
hash funkcia je stavia do vedier.

1316
01:02:02,410 --> 01:02:04,690
A v tomto prípade sme
nie je uvedenie názvu.

1317
01:02:04,690 --> 01:02:07,880
Dávame tým spojené telefónu
číslo meno vo vedre.

1318
01:02:07,880 --> 01:02:10,430
Ale vy ste mohol veľmi dobre len
dať meno do vedra.

1319
01:02:10,430 --> 01:02:12,950
>> To je len obraz toho, čo
sme vychádzali z hracej plochy.

1320
01:02:12,950 --> 01:02:14,460
Máme potenciálne úskalia, hoci.

1321
01:02:14,460 --> 01:02:17,470
A tam sú dva a to najmä
šmykľavky, že chcem ísť preč.

1322
01:02:17,470 --> 01:02:20,230
Prvý z nich je o
funkcia hash.

1323
01:02:20,230 --> 01:02:22,620
Tak som sa spýtal na otázku, čo
robí dobrý hash funkcie?

1324
01:02:22,620 --> 01:02:24,220
Dávam dve odpovede.

1325
01:02:24,220 --> 01:02:26,630
Prvá je, že je deterministický.

1326
01:02:26,630 --> 01:02:29,660
V súvislosti s hašovacej funkcií,
Čo to znamená?

1327
01:02:29,660 --> 01:02:37,840

1328
01:02:37,840 --> 01:02:39,282
Áno?

1329
01:02:39,282 --> 01:02:42,850
>> DIVÁKOV: Je možné nájsť
Obsah v konštantnom čase?

1330
01:02:42,850 --> 01:02:43,810
>> JASON Hirschhorn: To
nie je to, čo to znamená.

1331
01:02:43,810 --> 01:02:44,725
Ale to je dobrý odhad.

1332
01:02:44,725 --> 01:02:46,100
Niekto iný má hádať
na to, čo to znamená?

1333
01:02:46,100 --> 01:02:47,780
To je dobrá funkcia hash
je deterministický?

1334
01:02:47,780 --> 01:02:48,280
Annie?

1335
01:02:48,280 --> 01:02:51,680
>> DIVÁKOV: To kľúč môže byť mapovaný iba
na jedno miesto v tabuľke hash.

1336
01:02:51,680 --> 01:02:53,070
>> JASON Hirschhorn: To je
Presne tak.

1337
01:02:53,070 --> 01:02:57,430
Zakaždým, keď dáte do tekvice,
vždy vráti nulu.

1338
01:02:57,430 --> 01:03:01,660
Ak dáte do tekvice a vaše hash
Funkcia vracia nulu, ale má

1339
01:03:01,660 --> 01:03:06,060
pravdepodobnosť vrátenia niečo
inak väčšia ako nula -

1340
01:03:06,060 --> 01:03:09,280
takže možno to môže vrátiť jednu niekedy
alebo dva iné časy -

1341
01:03:09,280 --> 01:03:11,100
že nie je dobré funkcie hash.

1342
01:03:11,100 --> 01:03:11,800
Ty si úplnú pravdu.

1343
01:03:11,800 --> 01:03:15,680
Váš hash funkcia by mala vrátiť
Rovnaký presné číslo, v tomto prípade pre

1344
01:03:15,680 --> 01:03:17,780
rovnaký presný reťazec.

1345
01:03:17,780 --> 01:03:22,210
>> Možno, že sa vráti presne rovnakou číslo
pre rovnaký reťazec presné

1346
01:03:22,210 --> 01:03:24,430
bez ohľadu na kapitalizáciu.

1347
01:03:24,430 --> 01:03:27,980
Ale v tomto prípade je to ešte
deterministický, pretože viac vecí

1348
01:03:27,980 --> 01:03:29,350
sú mapované na rovnakú hodnotu.

1349
01:03:29,350 --> 01:03:30,170
To je v poriadku.

1350
01:03:30,170 --> 01:03:32,615
Ako dlho ako tam je len jeden
výstup pre daný vstup.

1351
01:03:32,615 --> 01:03:35,630

1352
01:03:35,630 --> 01:03:36,350
>> OK.

1353
01:03:36,350 --> 01:03:38,340
Druhá vec je, že
vráti platné indexy.

1354
01:03:38,340 --> 01:03:40,220
Priviezli sme si, že skôr.

1355
01:03:40,220 --> 01:03:41,860
Tento hash funkcie -

1356
01:03:41,860 --> 01:03:43,710
oh boy -

1357
01:03:43,710 --> 01:03:46,840
hašovacej funkcie by
návrat platné indexy.

1358
01:03:46,840 --> 01:03:47,740
Takže povedať -

1359
01:03:47,740 --> 01:03:48,990
vráťme sa k tomuto príkladu.

1360
01:03:48,990 --> 01:03:52,580

1361
01:03:52,580 --> 01:03:57,540
Môj hash funkcie počíta až
písmená v slove.

1362
01:03:57,540 --> 01:03:58,380
To je funkcia hash.

1363
01:03:58,380 --> 01:03:59,740
A vráti, že celé číslo.

1364
01:03:59,740 --> 01:04:04,280
Takže keď mám slovo A, je to
chystá sa vrátiť jeden.

1365
01:04:04,280 --> 01:04:06,900
A to bude dať tu.

1366
01:04:06,900 --> 01:04:09,430
Čo keď som dal slovo bat?

1367
01:04:09,430 --> 01:04:11,310
Bude to vrátiť tri.

1368
01:04:11,310 --> 01:04:12,560
Kde sa bat ísť?

1369
01:04:12,560 --> 01:04:18,730

1370
01:04:18,730 --> 01:04:19,750
>> To sa nehodí.

1371
01:04:19,750 --> 01:04:21,000
Ale je potrebné niekam ísť.

1372
01:04:21,000 --> 01:04:23,340
To je môj hash tabuľka po tom všetkom, a
všetko, čo je potrebné niekam ísť.

1373
01:04:23,340 --> 01:04:24,590
Takže tam, kde by sa bat ísť?

1374
01:04:24,590 --> 01:04:28,020

1375
01:04:28,020 --> 01:04:28,710
Akékoľvek myšlienky?

1376
01:04:28,710 --> 01:04:29,450
Háda?

1377
01:04:29,450 --> 01:04:30,280
Dobré odhady?

1378
01:04:30,280 --> 01:04:31,220
>> DIVÁKOV: Zero.

1379
01:04:31,220 --> 01:04:32,120
>> JASON Hirschhorn: Prečo nula?

1380
01:04:32,120 --> 01:04:35,990
>> DIVÁKOV: Vzhľadom k tomu, tri
modulo tri je nula?

1381
01:04:35,990 --> 01:04:38,620
>> JASON Hirschhorn: Three
modulo tri je nula.

1382
01:04:38,620 --> 01:04:40,810
To je skvelý odhad,
a to je správne.

1383
01:04:40,810 --> 01:04:43,870
Takže v tomto prípade by mal
asi ísť na nulu.

1384
01:04:43,870 --> 01:04:51,080
Takže dobrý spôsob, ako zabezpečiť, aby tento hash
Funkcia vracia iba platné indexy sa

1385
01:04:51,080 --> 01:04:54,580
na modulo to podľa veľkosti tabuľky.

1386
01:04:54,580 --> 01:04:57,360
Ak modulo Čokoľvek priznania podľa
tri, ste vždy dostane

1387
01:04:57,360 --> 01:05:00,930
niečo medzi nulou, jeden a dva.

1388
01:05:00,930 --> 01:05:05,160
A ak sa to vždy vracia sedem, a
vždy modulo tri, ty si

1389
01:05:05,160 --> 01:05:06,030
Vždy dostane to isté.

1390
01:05:06,030 --> 01:05:09,270
>> Takže je to stále deterministický
ak modulo.

1391
01:05:09,270 --> 01:05:11,420
Ale, že zabezpečí, že vám
Nikdy si niečo -

1392
01:05:11,420 --> 01:05:12,940
neplatný priemyslu.

1393
01:05:12,940 --> 01:05:16,840
Všeobecne platí, že modulo by sa malo stať
vnútri hash funkcie.

1394
01:05:16,840 --> 01:05:18,240
Takže nemusíte sa starať o to.

1395
01:05:18,240 --> 01:05:20,555
Ty jednoducho nemôže zabezpečiť, že
to je platný Index.

1396
01:05:20,555 --> 01:05:23,700

1397
01:05:23,700 --> 01:05:26,700
Akékoľvek otázky týkajúce sa tejto
potenciálne úskalia?

1398
01:05:26,700 --> 01:05:36,590

1399
01:05:36,590 --> 01:05:39,060
>> OK.

1400
01:05:39,060 --> 01:05:40,290
A tam ideme.

1401
01:05:40,290 --> 01:05:42,890
Ďalšie potenciálne úskalia, a
To je veľký.

1402
01:05:42,890 --> 01:05:46,880
Čo keď mapa dva kľúče
na rovnakú hodnotu?

1403
01:05:46,880 --> 01:05:49,350
Takže existujú dva spôsoby, ako zvládnuť to.

1404
01:05:49,350 --> 01:05:53,140

1405
01:05:53,140 --> 01:05:56,020
Prvý z nich sa nazýva lineárny
snímanie, ktoré som

1406
01:05:56,020 --> 01:05:57,300
nie ísť preč.

1407
01:05:57,300 --> 01:06:01,120
Ale mali by ste byť oboznámení s tým, ako
že funguje a čo to je.

1408
01:06:01,120 --> 01:06:05,610
>> Druhý Chystám sa ísť cez
pretože to je ten, že mnoho

1409
01:06:05,610 --> 01:06:08,290
ľudia budú pravdepodobne skončí rozhodovanie o tom,
používať v ich problému sade.

1410
01:06:08,290 --> 01:06:09,820
Samozrejme, že nemusíte.

1411
01:06:09,820 --> 01:06:15,280
Ale pre problémové sady, mnoho ľudí
majú sklon vyberať si vytvoriť hash tabuľky

1412
01:06:15,280 --> 01:06:17,950
s oddelenou reťazenie prevedení
ich slovníka.

1413
01:06:17,950 --> 01:06:21,390
Takže sme ísť nad tým, čo to znamená,
na vytvorenie hash tabuľky sa

1414
01:06:21,390 --> 01:06:23,890
oddelené zreťazenie.

1415
01:06:23,890 --> 01:06:26,260
>> Tak som sa dal do tekvice.

1416
01:06:26,260 --> 01:06:29,560
Je to vráti nulu.

1417
01:06:29,560 --> 01:06:31,410
A dal som tekvica tu.

1418
01:06:31,410 --> 01:06:35,880

1419
01:06:35,880 --> 01:06:37,930
Potom som sa dal do -

1420
01:06:37,930 --> 01:06:39,922
čo je ďalší Halloween-themed vec?

1421
01:06:39,922 --> 01:06:42,200
>> DIVÁKOV: Candy.

1422
01:06:42,200 --> 01:06:42,770
>> JASON Hirschhorn: Candy!

1423
01:06:42,770 --> 01:06:43,910
To je skvelá jedna.

1424
01:06:43,910 --> 01:06:47,760
Dal som do cukroviniek a sladkosti
tiež mi dáva nulu.

1425
01:06:47,760 --> 01:06:49,350
Čo mám robiť?

1426
01:06:49,350 --> 01:06:51,940
Nejaké nápady?

1427
01:06:51,940 --> 01:06:53,940
Pretože ste všetci tak nejako viem,
čo oddelený reťazenie je.

1428
01:06:53,940 --> 01:06:55,190
Takže nejaké nápady, čo robiť?

1429
01:06:55,190 --> 01:06:58,170

1430
01:06:58,170 --> 01:06:59,110
Jo.

1431
01:06:59,110 --> 01:07:03,810
>> DIVÁKOV: Uvedenie reťazec
v skutočnosti v tabuľke hash.

1432
01:07:03,810 --> 01:07:08,910
>> JASON Hirschhorn: Tak ideme na
nakresliť dobrý nápad sem.

1433
01:07:08,910 --> 01:07:09,340
OK.

1434
01:07:09,340 --> 01:07:12,290
>> DIVÁKOV: Už Hashtable
[Nepočuteľný]

1435
01:07:12,290 --> 01:07:16,640
ukazovateľ, ktorý ukazuje na
začiatok zoznamu.

1436
01:07:16,640 --> 01:07:20,930
A potom si tekvica byť prvá hodnota
v tomto prepojenom zoznamu a sladkosti sa

1437
01:07:20,930 --> 01:07:22,800
druhá hodnota v tomto prepojenom zozname.

1438
01:07:22,800 --> 01:07:23,420
>> JASON Hirschhorn: OK.

1439
01:07:23,420 --> 01:07:24,670
Marcus, že bol vynikajúci.

1440
01:07:24,670 --> 01:07:26,160
Chystám sa zlomiť dole.

1441
01:07:26,160 --> 01:07:28,890
Marcus hovorí nie
prepísať tekvica.

1442
01:07:28,890 --> 01:07:30,660
To by bolo zlé.

1443
01:07:30,660 --> 01:07:33,640
Nedávajte cukroví niekde inde.

1444
01:07:33,640 --> 01:07:35,390
Chystáme sa dať obaja na nule.

1445
01:07:35,390 --> 01:07:37,770
Ale budeme sa zaoberať
ich uvádzanie na nulu

1446
01:07:37,770 --> 01:07:39,395
vytvorenie zoznamu na nulu.

1447
01:07:39,395 --> 01:07:42,430
A budeme chcete vytvoriť zoznam
všetko, mapované na nulu.

1448
01:07:42,430 --> 01:07:47,960
A najlepší spôsob, ako sme sa naučili vytvárať
Zoznam, ktorý môže rásť a zmenšovať

1449
01:07:47,960 --> 01:07:49,840
dynamicky nie je v
ďalšie pole.

1450
01:07:49,840 --> 01:07:51,510
Takže nie multi-dimenzionální pole.

1451
01:07:51,510 --> 01:07:54,080
Ale len vytvorenie prepojeného zoznamu.

1452
01:07:54,080 --> 01:07:55,330
>> Takže to, čo navrhol -

1453
01:07:55,330 --> 01:07:57,950

1454
01:07:57,950 --> 01:07:59,200
Idem si nový -

1455
01:07:59,200 --> 01:08:15,380

1456
01:08:15,380 --> 01:08:19,689
je vytvoriť pole s ukazovateľmi,
pole ukazovateľov.

1457
01:08:19,689 --> 01:08:20,580
OK.

1458
01:08:20,580 --> 01:08:24,180
Nejaký nápad, alebo náznak toho, čo typ
z týchto ukazovateľov by mali byť?

1459
01:08:24,180 --> 01:08:26,290
Marcus?

1460
01:08:26,290 --> 01:08:27,250
>> DIVÁKOV: Ukazovatele na -

1461
01:08:27,250 --> 01:08:28,609
>> JASON Hirschhorn: Pretože vám
povedal spájať zoznam, takže -

1462
01:08:28,609 --> 01:08:29,520
>> DIVÁKOV: ukazovatele uzla?

1463
01:08:29,520 --> 01:08:30,670
>> JASON Hirschhorn: ukazovatele uzla.

1464
01:08:30,670 --> 01:08:32,830
Ak sa veci v našom spojené
Zoznam sú uzly potom

1465
01:08:32,830 --> 01:08:34,370
by mala byť uzol ukazovatele.

1466
01:08:34,370 --> 01:08:35,939
A to, čo sa im rovnajú pôvodne?

1467
01:08:35,939 --> 01:08:36,990
>> DIVÁKOV: Null.

1468
01:08:36,990 --> 01:08:38,240
>> JASON Hirschhorn: Null.

1469
01:08:38,240 --> 01:08:44,540

1470
01:08:44,540 --> 01:08:46,080
Takže je tu náš prázdna vec.

1471
01:08:46,080 --> 01:08:47,170
Tekvicové vráti nulu.

1472
01:08:47,170 --> 01:08:48,569
Čo budeme robiť?

1473
01:08:48,569 --> 01:08:49,609
Prechádzka ma cez neho?

1474
01:08:49,609 --> 01:08:50,810
Vlastne, Marcus už mi dal.

1475
01:08:50,810 --> 01:08:52,439
Niekto chodí ma cez neho.

1476
01:08:52,439 --> 01:08:54,760
Čo budeme robiť, keď -

1477
01:08:54,760 --> 01:08:56,609
to vyzerá veľmi podobne ako
to, čo sme práve robí.

1478
01:08:56,609 --> 01:08:57,396
Avi.

1479
01:08:57,396 --> 01:08:59,090
>> DIVÁKOV: Budem hádať.

1480
01:08:59,090 --> 01:09:01,250
Takže keď sa dostanete cukríky.

1481
01:09:01,250 --> 01:09:01,640
>> JASON Hirschhorn: Jo.

1482
01:09:01,640 --> 01:09:03,120
No, máme tekvica.

1483
01:09:03,120 --> 01:09:03,870
Poďme si našu prvú.

1484
01:09:03,870 --> 01:09:04,324
Máme tekvica.

1485
01:09:04,324 --> 01:09:04,779
>> DIVÁKOV: OK.

1486
01:09:04,779 --> 01:09:05,880
Tekvicové vráti nulu.

1487
01:09:05,880 --> 01:09:08,770
Takže ste to v tom.

1488
01:09:08,770 --> 01:09:10,810
Alebo vlastne, to si dal
v prepojenom zozname.

1489
01:09:10,810 --> 01:09:13,550
>> JASON Hirschhorn: Ako sme
vložte ho do prepojeného zoznamu?

1490
01:09:13,550 --> 01:09:15,479
>> DIVÁKOV: Oh, je vlastný syntax?

1491
01:09:15,479 --> 01:09:16,240
>> JASON Hirschhorn: Len chodiť -

1492
01:09:16,240 --> 01:09:16,740
povedať viac.

1493
01:09:16,740 --> 01:09:19,310
Čo budeme robiť?

1494
01:09:19,310 --> 01:09:22,100
>> DIVÁKOV: Len vložiť
že ako prvý uzol.

1495
01:09:22,100 --> 01:09:22,675
>> JASON Hirschhorn: OK.

1496
01:09:22,675 --> 01:09:29,069
Takže máme uzol, tekvica.

1497
01:09:29,069 --> 01:09:31,560
A teraz, ako mám vložiť to?

1498
01:09:31,560 --> 01:09:34,590

1499
01:09:34,590 --> 01:09:37,090
>> DIVÁKOV: Môžete priradiť
to ukazovateľ.

1500
01:09:37,090 --> 01:09:37,970
>> JASON Hirschhorn: Aké ukazovatele?

1501
01:09:37,970 --> 01:09:39,620
>> Divákov: ukazovateľ na nule.

1502
01:09:39,620 --> 01:09:41,420
>> JASON Hirschhorn: Tak kde
robí tento bod?

1503
01:09:41,420 --> 01:09:42,810
>> DIVÁKOV: Ak chcete null práve teraz.

1504
01:09:42,810 --> 01:09:43,529
>> JASON Hirschhorn: No,
to ukazuje na hodnotu null.

1505
01:09:43,529 --> 01:09:44,499
Ale dávam do tekvice.

1506
01:09:44,499 --> 01:09:46,053
Takže tam, kde by to ukazovať?

1507
01:09:46,053 --> 01:09:46,880
>> DIVÁKOV: Ak chcete tekvica.

1508
01:09:46,880 --> 01:09:47,399
>> JASON Hirschhorn: Ak chcete tekvica.

1509
01:09:47,399 --> 01:09:48,760
Presne tak.

1510
01:09:48,760 --> 01:09:50,010
Takže to ukazuje na tekvice.

1511
01:09:50,010 --> 01:09:52,500

1512
01:09:52,500 --> 01:09:54,250
A kde sa to robí ukazovateľ
v tekvica bode?

1513
01:09:54,250 --> 01:09:57,986

1514
01:09:57,986 --> 01:09:58,340
Na

1515
01:09:58,340 --> 01:09:58,590
>> DIVÁKOV: Null.

1516
01:09:58,590 --> 01:09:59,210
>> JASON Hirschhorn: Ak chcete hodnotu null.

1517
01:09:59,210 --> 01:10:00,460
Presne tak.

1518
01:10:00,460 --> 01:10:03,570

1519
01:10:03,570 --> 01:10:05,140
Takže sme jednoducho vloží niečo
do prepojeného zoznamu.

1520
01:10:05,140 --> 01:10:07,210
Práve sme napísal tento kód, ako to urobiť.

1521
01:10:07,210 --> 01:10:09,520
Takmer sme skoro mám
úplne popraskané.

1522
01:10:09,520 --> 01:10:10,790
Teraz vložíme cukríky.

1523
01:10:10,790 --> 01:10:13,480
Naše cukroví tiež klesne na nulu.

1524
01:10:13,480 --> 01:10:16,100
Tak čo budeme robiť cukroví?

1525
01:10:16,100 --> 01:10:18,790
>> DIVÁKOV: Záleží na tom, či
Nie je sa snažíme triediť.

1526
01:10:18,790 --> 01:10:19,640
>> JASON Hirschhorn: To je
Presne tak.

1527
01:10:19,640 --> 01:10:21,070
Záleží na tom, či
snažíme sa ho vyriešiť.

1528
01:10:21,070 --> 01:10:22,660
Predpokladajme, že nie sme
bude triediť.

1529
01:10:22,660 --> 01:10:24,880
>> DIVÁKOV: Tak, ako sme sa bavili
pred, je to najjednoduchšie len aby to

1530
01:10:24,880 --> 01:10:28,590
hneď na začiatku, aby ukazovateľ
od nulových bodov, do cukroviniek.

1531
01:10:28,590 --> 01:10:29,020
>> JASON Hirschhorn: OK.

1532
01:10:29,020 --> 01:10:29,380
Vydrž.

1533
01:10:29,380 --> 01:10:30,630
Dovoľte mi, aby som vytvoriť cukroví práve tu.

1534
01:10:30,630 --> 01:10:34,030

1535
01:10:34,030 --> 01:10:35,150
Takže tento ukazovateľ -

1536
01:10:35,150 --> 01:10:37,590
>> DIVÁKOV: Jo, mal by sa
sa ukázal na cukrovinky.

1537
01:10:37,590 --> 01:10:40,580
Potom sa ukazovateľ od
candy prejdite na tekvica.

1538
01:10:40,580 --> 01:10:43,140

1539
01:10:43,140 --> 01:10:44,560
>> JASON Hirschhorn: Ako, že?

1540
01:10:44,560 --> 01:10:47,380
A povedať, že sme dostali ďalšie
vec máp na nulu?

1541
01:10:47,380 --> 01:10:48,660
>> DIVÁKOV: No, práve
robiť to isté?

1542
01:10:48,660 --> 01:10:50,290
>> JASON Hirschhorn: Vykonajte to isté.

1543
01:10:50,290 --> 01:10:53,700
Takže v tomto prípade, keď to neurobíme
chcete, aby ju udržali radené ju

1544
01:10:53,700 --> 01:10:55,270
Znie to pomerne jednoduché.

1545
01:10:55,270 --> 01:10:59,920
Berieme ukazovateľ na Index
vzhľadom k našej hash funkcie.

1546
01:10:59,920 --> 01:11:03,830
Musíme tento bod do nášho nového uzla.

1547
01:11:03,830 --> 01:11:07,830
A potom, čo to bolo ukázal
skôr -

1548
01:11:07,830 --> 01:11:10,620
v tomto prípade hodnotu null, v
Druhý prípad tekvice -

1549
01:11:10,620 --> 01:11:15,310
že, ako sa to ukazuje na
skôr, pridáme do najbližšieho

1550
01:11:15,310 --> 01:11:17,810
náš nový uzol.

1551
01:11:17,810 --> 01:11:19,650
Sme vkladanie niečo
na začiatku.

1552
01:11:19,650 --> 01:11:22,900
V skutočnosti je to oveľa jednoduchšie, než
sa snaží udržať zoznamu zoradené.

1553
01:11:22,900 --> 01:11:25,340
Ale opäť, vyhľadávanie bude
viac komplikované tu.

1554
01:11:25,340 --> 01:11:28,300
Budeme mať vždy ísť až do konca.

1555
01:11:28,300 --> 01:11:29,650
>> OK.

1556
01:11:29,650 --> 01:11:32,750
Máte otázky k samostatnej reťazenie?

1557
01:11:32,750 --> 01:11:34,690
Ako to funguje?

1558
01:11:34,690 --> 01:11:35,820
Prosím, spýtajte sa ich teraz.

1559
01:11:35,820 --> 01:11:39,260
Naozaj chcem, aby sa ubezpečil všetky
pochopiť, ako sme vyraziť.

1560
01:11:39,260 --> 01:11:48,410

1561
01:11:48,410 --> 01:11:52,060
>> DIVÁKOV: Prečo si dať tekvicu
a cukrovinky do rovnakej

1562
01:11:52,060 --> 01:11:54,108
časť tabuľky hash?

1563
01:11:54,108 --> 01:11:55,860
>> JASON Hirschhorn: Dobrá otázka.

1564
01:11:55,860 --> 01:11:59,140
Prečo dať ich do rovnakej
časť tabuľky hash?

1565
01:11:59,140 --> 01:12:03,200
No, v tomto prípade naše hash funkcie
vráti nulu pre obe z nich.

1566
01:12:03,200 --> 01:12:05,310
Takže je potrebné ísť na Index nule
pretože to je miesto, kde budeme

1567
01:12:05,310 --> 01:12:07,420
pozrite sa na ne, ak sa niekedy
Chcete ich vyhľadať.

1568
01:12:07,420 --> 01:12:11,750
Opäť platí, že sa lineárne snímanie prístupu
by sme im dať obaja na nule.

1569
01:12:11,750 --> 01:12:13,900
Ale v samostatnom prístupe reťazca,
ideme dať obaja na nule

1570
01:12:13,900 --> 01:12:16,620
a potom vytvoriť zoznam off nulu.

1571
01:12:16,620 --> 01:12:20,140
>> A my nechceme prepísať tekvica
len pre to, pretože potom budeme

1572
01:12:20,140 --> 01:12:21,860
Predpokladám, že tekvica sa
nikdy vložená.

1573
01:12:21,860 --> 01:12:25,230
Ak budeme len držať jednu vec
miesto, ktoré by bolo zlé.

1574
01:12:25,230 --> 01:12:28,590
Potom by tam byť žiadny
šanca na nás vôbec -

1575
01:12:28,590 --> 01:12:31,660
ak sme kedy mali duplikát, potom sme
by len vymazať našu počiatočnú hodnotu.

1576
01:12:31,660 --> 01:12:34,090
Takže to je dôvod, prečo robíme tento prístup.

1577
01:12:34,090 --> 01:12:36,580
Alebo, že je dôvod, prečo sme sa rozhodli - ale opäť, my
zvolil samostatný zreťazenie prístup,

1578
01:12:36,580 --> 01:12:39,670
, Ktoré je tu mnoho ďalších prístupov
by sa dalo vybrať.

1579
01:12:39,670 --> 01:12:41,185
Znamená to, že odpoveď na vašu otázku?

1580
01:12:41,185 --> 01:12:41,660
>> OK.

1581
01:12:41,660 --> 01:12:42,910
Carlos.

1582
01:12:42,910 --> 01:12:46,130

1583
01:12:46,130 --> 01:12:47,720
Lineárne snímanie by znamenalo -

1584
01:12:47,720 --> 01:12:51,913
ak by sme našli kolízii na nule, sme
bude vyzerať v ďalšom mieste, aby zistili, či

1585
01:12:51,913 --> 01:12:54,310
to bolo otvorené a dať to tam.

1586
01:12:54,310 --> 01:12:57,320
A potom sa pozrieme v ďalšom športe a
uvidíme, či to bolo otvorené a dať to tam.

1587
01:12:57,320 --> 01:12:59,780
Tak sme sa nájsť ďalšie dostupné
otvorené miesto a dať to tam.

1588
01:12:59,780 --> 01:13:02,580

1589
01:13:02,580 --> 01:13:03,890
Nejaké ďalšie otázky?

1590
01:13:03,890 --> 01:13:05,370
Jo, Avi.

1591
01:13:05,370 --> 01:13:07,490
>> DIVÁKOV: V nadväznosti na to,
Čo myslíš tým ďalšom mieste?

1592
01:13:07,490 --> 01:13:10,250
V tabuľke hash alebo prepojeného zoznamu.

1593
01:13:10,250 --> 01:13:12,100
>> JASON Hirschhorn: Pre lineárne
programovanie, žiadne spojové zoznamy.

1594
01:13:12,100 --> 01:13:13,400
Ďalšie miesto na stole hash.

1595
01:13:13,400 --> 01:13:13,820
>> DIVÁKOV: OK.

1596
01:13:13,820 --> 01:13:17,570
Takže hash tabuľka bude
inicializovaný veľkosti -

1597
01:13:17,570 --> 01:13:19,560
ako je počet reťazcov
že ste boli vkladanie?

1598
01:13:19,560 --> 01:13:22,170
>> JASON Hirschhorn: Tie by
Chcem, aby to bolo naozaj veľké.

1599
01:13:22,170 --> 01:13:23,910
Áno.

1600
01:13:23,910 --> 01:13:27,900
Tu je obrázok toho, čo sme
len kreslil na tabuľu.

1601
01:13:27,900 --> 01:13:29,470
Opäť máme kolízii tu.

1602
01:13:29,470 --> 01:13:30,710
152.

1603
01:13:30,710 --> 01:13:33,570
A uvidíte, sme vytvorili
spájať zoznam z nej.

1604
01:13:33,570 --> 01:13:38,200

1605
01:13:38,200 --> 01:13:41,850
Opäť platí, že hash tabuľky oddelené zreťazenie
prístup nie je ten, ktorý

1606
01:13:41,850 --> 01:13:45,590
musí brať v nastavení problémy
šesť, ale je jedno, že veľa

1607
01:13:45,590 --> 01:13:47,100
študenti majú tendenciu brať.

1608
01:13:47,100 --> 01:13:51,140
Tak v takom prípade, poďme krátko pohovoril
predtým, než sme vyraziť o probléme šesť,

1609
01:13:51,140 --> 01:13:52,160
a potom budem zdieľať svoj príbeh sa s vami.

1610
01:13:52,160 --> 01:13:55,120
Máme tri minúty.

1611
01:13:55,120 --> 01:13:55,750
>> Problém set šesť.

1612
01:13:55,750 --> 01:13:57,790
Máte štyri funkcie -

1613
01:13:57,790 --> 01:14:02,430
zaťaženie, skontrolujte, veľkosť, a vyložiť.

1614
01:14:02,430 --> 01:14:03,380
Load -

1615
01:14:03,380 --> 01:14:07,120
dobre, že sme sa deje
po záťaži práve teraz.

1616
01:14:07,120 --> 01:14:09,330
Kreslil sme zaťažení na palube.

1617
01:14:09,330 --> 01:14:13,230
A dokonca sme začali kódovanie veľa
vloženie do prepojeného zoznamu.

1618
01:14:13,230 --> 01:14:18,020
Takže zaťaženie nie je o moc väčšie ako
to, čo sme práve robili.

1619
01:14:18,020 --> 01:14:21,070
>> Kontrola je raz budete mať
niečo načítať.

1620
01:14:21,070 --> 01:14:22,580
Je to rovnaký proces, ako je tento.

1621
01:14:22,580 --> 01:14:26,845
Rovnaké prvé dve časti, kde sa hodiť
niečo, čo do funkcie hash

1622
01:14:26,845 --> 01:14:29,190
a získať jeho hodnotu.

1623
01:14:29,190 --> 01:14:30,700
Ale teraz nie sme vloženie.

1624
01:14:30,700 --> 01:14:33,350
Teraz hľadáme pre neho.

1625
01:14:33,350 --> 01:14:37,130
Som ukážkový kód napísaný pre vyhľadávanie
niečo v prepojenom zozname.

1626
01:14:37,130 --> 01:14:38,250
Chcel by som vyzvať vás k praxi, že.

1627
01:14:38,250 --> 01:14:43,000
Ale intuitívne nájsť niečo, čo je
celkom podobný vkladanie niečo.

1628
01:14:43,000 --> 01:14:46,540
Naozaj sme nakreslil obrázok nájsť
niečo v prepojenom zozname, pohybujúce sa

1629
01:14:46,540 --> 01:14:48,910
až kým sa dostal až do konca.

1630
01:14:48,910 --> 01:14:52,430
A ak ste sa dostali na koniec a nemohol
nájsť, potom to tam nie je.

1631
01:14:52,430 --> 01:14:55,400
Tak to je kontrola, v podstate.

1632
01:14:55,400 --> 01:14:57,030
>> Ďalšie je veľkosť.

1633
01:14:57,030 --> 01:14:57,910
Poďme preskočiť veľkosti.

1634
01:14:57,910 --> 01:15:00,040
Konečne ste sa uvoľniť.

1635
01:15:00,040 --> 01:15:02,890
Uvoľniť je tá, ktorú sme doteraz vypracované
na palube alebo ešte kódované.

1636
01:15:02,890 --> 01:15:05,990
Ale ja Odporúčame vám vyskúšať kódovanie
v našom vzorke Google napríklad zoznam.

1637
01:15:05,990 --> 01:15:11,440
Ale vyložiť intuitívne
je podobný zadarmo -

1638
01:15:11,440 --> 01:15:14,010
alebo som na mysli, je podobný skontrolovať.

1639
01:15:14,010 --> 01:15:17,350
S výnimkou teraz zakaždým, keď vy budete
vďaka, že ste jednoducho kontroluje,

1640
01:15:17,350 --> 01:15:19,090
zistiť, či máte hodnotu tam.

1641
01:15:19,090 --> 01:15:22,490
Ale ty berieš ten uzol a
uvoľňovať to, v podstate.

1642
01:15:22,490 --> 01:15:23,610
To je to, čo vyložiť vás spýta na to.

1643
01:15:23,610 --> 01:15:24,670
Zadarmo všetko, čo ste malloced.

1644
01:15:24,670 --> 01:15:27,480
Takže idete cez celý zoznam
opäť prechádza celý hash

1645
01:15:27,480 --> 01:15:27,760
opäť tabuľka.

1646
01:15:27,760 --> 01:15:29,240
Tentoraz sa nekontrolujú
vidieť, čo tam je.

1647
01:15:29,240 --> 01:15:31,080
Stačí uvoľniť to, čo tam je.

1648
01:15:31,080 --> 01:15:33,260
>> A konečne veľkosti.

1649
01:15:33,260 --> 01:15:34,350
Veľkosť by mala byť vykonaná.

1650
01:15:34,350 --> 01:15:35,590
Ak nechcete vykonávať veľkosť -

1651
01:15:35,590 --> 01:15:36,250
Poviem to takto.

1652
01:15:36,250 --> 01:15:39,740
Ak nechcete vykonávať veľkosť v presne
jeden riadok kódu, vrátane

1653
01:15:39,740 --> 01:15:43,760
vrátiť vyhlásenie, ste
robí veľkosť nesprávne.

1654
01:15:43,760 --> 01:15:47,170
Takže uistite sa, že veľkosť, pre úplné vykonanie
body, robíte to presne jeden

1655
01:15:47,170 --> 01:15:49,970
riadok kódu, vrátane
return.

1656
01:15:49,970 --> 01:15:52,450
>> A to zabaliť ešte, Akchar.

1657
01:15:52,450 --> 01:15:53,700
Snaživec.

1658
01:15:53,700 --> 01:15:55,820

1659
01:15:55,820 --> 01:16:01,300
Chcel som povedať, ďakujem chlapci
prišiel do sekcie.

1660
01:16:01,300 --> 01:16:02,550
Majú Happy Halloween.

1661
01:16:02,550 --> 01:16:05,300

1662
01:16:05,300 --> 01:16:05,960
To je môj kostým.

1663
01:16:05,960 --> 01:16:08,850
Budem mať na sebe tento štvrtok
keď som ťa vidieť na úradné hodiny.

1664
01:16:08,850 --> 01:16:14,640
A ak ste zvedaví, niektorí viac
pozadia, ako k tomuto kostýmu, cítite

1665
01:16:14,640 --> 01:16:19,135
zadarmo vyskúšať 2.011 sekcie
pre príbeh o tom, prečo som

1666
01:16:19,135 --> 01:16:20,900
na sebe kostým tekvice.

1667
01:16:20,900 --> 01:16:23,680
A to je smutný príbeh.

1668
01:16:23,680 --> 01:16:27,050
Takže uistite sa, že máte
Niektoré tkanivá v okolí.

1669
01:16:27,050 --> 01:16:28,680
Ale na to, že ak máte nejaké
otázky, budem držať okolo

1670
01:16:28,680 --> 01:16:29,960
mimo po bode.

1671
01:16:29,960 --> 01:16:31,510
Veľa šťastia na problém nastaviť šesť.

1672
01:16:31,510 --> 01:16:33,540
A ako vždy, ak máte nejaké
otázky, dajte mi vedieť.

1673
01:16:33,540 --> 01:16:35,584