1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Týždeň 6]

2
00:00:02,000 --> 00:00:04,000
[David J. Malan] [Harvard University]

3
00:00:04,000 --> 00:00:08,000
[To je CS50.] [CS50.TV]

4
00:00:08,000 --> 00:00:12,000
>> To je CS50, a to je začiatok týždňa 6,

5
00:00:12,000 --> 00:00:16,000
takže pár nových nástrojov sú teraz k dispozícii pre vás využiť,

6
00:00:16,000 --> 00:00:19,000
z ktorých prvá sa nazýva CS50 štýl.

7
00:00:19,000 --> 00:00:22,000
Kurzy sú, ak ste rovnako ako ja, alebo niektorý z výučbových chlapíkov,

8
00:00:22,000 --> 00:00:26,000
pravdepodobne ste videli program, ktorého štýl vyzerá trochu niečo takého.

9
00:00:26,000 --> 00:00:30,000
Možno začnete rezať niektoré rohy neskoro v noci, alebo budete riešiť neskôr,

10
00:00:30,000 --> 00:00:32,000
a potom sa TF alebo CA príde počas úradných hodín.

11
00:00:32,000 --> 00:00:34,000
Potom je to pre nás ťažké čítať.

12
00:00:34,000 --> 00:00:38,000
No, tento kód je syntakticky správny, a to bude kompilovať, a to bude skutočne spustiť.

13
00:00:38,000 --> 00:00:40,000
Ale to rozhodne nie je 5 pre štýl.

14
00:00:40,000 --> 00:00:45,000
>> Ale teraz, keď ideme do tohto adresára tu-

15
00:00:45,000 --> 00:00:48,000
a všimnite si, že mám conditions2.c-

16
00:00:48,000 --> 00:00:55,000
a ja som spustiť tento nový príkaz, style50, na tomto súbore conditions2.c, Enter,

17
00:00:55,000 --> 00:00:57,000
Všimnite si, že to ma informoval, že to bolo štylizované.

18
00:00:57,000 --> 00:01:00,000
Gedit si všimol, že súbor bol zmenený na disku,

19
00:01:00,000 --> 00:01:08,000
a keď klepnem znovu načítať, sú všetky vaše problémy teraz automatizovaný.

20
00:01:08,000 --> 00:01:15,000
[Potlesk]

21
00:01:15,000 --> 00:01:17,000
To je jedna z vecí, ktoré sme urobili tento víkend.

22
00:01:17,000 --> 00:01:20,000
Si uvedomiť, že je nedokonalé, pretože tam sú niektoré kód

23
00:01:20,000 --> 00:01:23,000
že to jednoducho nebude môcť štylizovať dokonale,

24
00:01:23,000 --> 00:01:26,000
ale uvedomte si, to je teraz nástroj, ktorý môžete využiť

25
00:01:26,000 --> 00:01:33,000
ak len upratať niektoré z chybne umiestnené zloženými zátvorkami a podobne.

26
00:01:33,000 --> 00:01:36,000
>> Ale závažnejšie je teraz CS50 Check.

27
00:01:36,000 --> 00:01:39,000
S CS50 kontroly, môžete skutočne vykonávať rovnaké korektnosť skúšky

28
00:01:39,000 --> 00:01:42,000
na vlastný kód, ktorý učebné chlapi sú schopní.

29
00:01:42,000 --> 00:01:44,000
To je nástroj príkazového riadku, ktorý je dodávaný so v spotrebiči

30
00:01:44,000 --> 00:01:46,000
akonáhle urobiť update50 ako za

31
00:01:46,000 --> 00:01:49,000
PSet 4 špecifikácie a použiť ju v podstate takhle.

32
00:01:49,000 --> 00:01:51,000
Môžete spustiť príkaz check50.

33
00:01:51,000 --> 00:01:56,000
Potom si odovzdať argument príkazového riadku, alebo viac všeobecne známy ako spínač alebo značkou.

34
00:01:56,000 --> 00:01:58,000
Všeobecne platí, že sú veci, ktoré majú pomlčky tzv switch

35
00:01:58,000 --> 00:02:02,000
k programu z príkazového riadku, tak-c určuje

36
00:02:02,000 --> 00:02:04,000
kontroly, ktoré chcete spustiť.

37
00:02:04,000 --> 00:02:07,000
>> Testy, ktoré chcete spustiť sa jednoznačne identifikujú podľa tohto reťazca,

38
00:02:07,000 --> 00:02:10,000
2012/pset4/resize.

39
00:02:10,000 --> 00:02:13,000
Inými slovami, že je to len ľubovoľný, ale jedinečný reťazec

40
00:02:13,000 --> 00:02:18,000
ktoré používame k jednoznačnej identifikácii PSet 4 je korektnosť skúšky.

41
00:02:18,000 --> 00:02:21,000
A potom určíte priestor oddelený zoznam súborov, ktoré chcete nahrať

42
00:02:21,000 --> 00:02:24,000
na CS50 Kontrola pre analýzu.

43
00:02:24,000 --> 00:02:29,000
Napríklad, keď som ísť do mojej riešenie tu pre resize.c-

44
00:02:29,000 --> 00:02:31,000
dovoľte mi, aby som otvoriť väčšie okno terminálu-

45
00:02:31,000 --> 00:02:42,000
a idem do toho a spustiť povedzme check50-c 2012/pset4/resize,

46
00:02:42,000 --> 00:02:46,000
a potom som ísť dopredu a zadať názvy súborov,

47
00:02:46,000 --> 00:02:49,000
resize.c, a potom stlačte kláves Enter, to komprimuje,

48
00:02:49,000 --> 00:02:53,000
to nahrávanie, kontroluje, a ja som nedokázal veľa testov.

49
00:02:53,000 --> 00:02:59,000
Ten v červenom hore vľavo hovorí, že resize.c a bmp existujú.

50
00:02:59,000 --> 00:03:01,000
To bol test. To bola otázka, ktorú sme požiadaní.

51
00:03:01,000 --> 00:03:04,000
A je to nešťastné, pretože odpoveď bola falošná.

52
00:03:04,000 --> 00:03:08,000
Biela Text pod ňou hovorí, že očakáva, že bmp.h existovať, a že je to jednoducho moja chyba.

53
00:03:08,000 --> 00:03:11,000
Zabudol som nahrať, tak som potrebné nahrať oba súbory,

54
00:03:11,000 --> 00:03:14,000
resize.c a bmp.h.

55
00:03:14,000 --> 00:03:17,000
Ale teraz všimnete všetkých ostatných testov sú v žltej farbe, pretože ste nespustili,

56
00:03:17,000 --> 00:03:21,000
a tak smiley tvár je zvislá, pretože to ani šťastný, ani smutný,

57
00:03:21,000 --> 00:03:25,000
ale musíme k náprave tohto problému v červenej farbe, než tie ostatné kontroly pobeží.

58
00:03:25,000 --> 00:03:27,000
>> Dovoľte mi, aby som tento problém vyriešiť.

59
00:03:27,000 --> 00:03:30,000
Dovoľte mi, aby som oddialiť a znova to, tentoraz s bmp.h tiež

60
00:03:30,000 --> 00:03:34,000
na príkazovom riadku, zadajte, a teraz, keď všetko pôjde dobre,

61
00:03:34,000 --> 00:03:38,000
to bude kontrolovať a vráti výsledok of-zadržte dych-

62
00:03:38,000 --> 00:03:42,000
celý zelený, čo znamená, že som si naozaj dobre PSet 4 tak ďaleko.

63
00:03:42,000 --> 00:03:44,000
Môžete vidieť a vyvodiť z popisného textu tu

64
00:03:44,000 --> 00:03:47,000
presne to, čo sme to my, testovaný.

65
00:03:47,000 --> 00:03:49,000
Testovali sme najprv urobiť súbory existujú?

66
00:03:49,000 --> 00:03:51,000
My potom testovaný robí resize.c kompilácie?

67
00:03:51,000 --> 00:03:58,000
Potom sme testovali to meniť veľkosť 1x1 pixel BMP, keď n, zmenu veľkosti faktor, je 1.

68
00:03:58,000 --> 00:04:01,000
Teraz, ak máte tušenie, čo n je, budete akonáhle sa ponoriť do PSet 4,

69
00:04:01,000 --> 00:04:04,000
ale že jednoducho je zdravý rozum skontrolujte, či nie ste zmenu veľkosti

70
00:04:04,000 --> 00:04:08,000
obrázok vôbec v prípade, že zmeny veľkosti činiteľ je 1.

71
00:04:08,000 --> 00:04:14,000
Ak naopak, to zmení na 1x1 pixel 1x1 pixelov BMP na 2x2 správne

72
00:04:14,000 --> 00:04:19,000
keď n je 2, potom podobne, moje tvorí zodpovedajúcim spôsobom.

73
00:04:19,000 --> 00:04:22,000
>> Stručne povedané, je to znamenalo, jeden, prijmú kríženie prstov

74
00:04:22,000 --> 00:04:25,000
z rovnice P pred vami odošlite PSet.

75
00:04:25,000 --> 00:04:28,000
Budete presne vedieť, aké sú vaše TF bude čoskoro vedieť

76
00:04:28,000 --> 00:04:30,000
keď idete o podaní niektoré z týchto problémových súborov,

77
00:04:30,000 --> 00:04:34,000
a tiež pedagogickej motivácia je naozaj dať

78
00:04:34,000 --> 00:04:37,000
možnosť pred vami tak, že keď viete, a priori

79
00:04:37,000 --> 00:04:39,000
že je chyba v kóde a testy, ktoré nie sú odovzdané,

80
00:04:39,000 --> 00:04:43,000
si môžete dať k účinnejšiemu včas do prednej strany k riešeniu týchto problémov

81
00:04:43,000 --> 00:04:45,000
skôr než stratiť body, získať spätnú väzbu od svojho TF,

82
00:04:45,000 --> 00:04:48,000
a potom ísť, "Ahh," ako by som mal to zistili.

83
00:04:48,000 --> 00:04:50,000
Teraz aspoň tú nástroj, ktorý vám pomôže zistiť, že.

84
00:04:50,000 --> 00:04:52,000
Nebude to poukázať, kde je chyba, ale to vám povie

85
00:04:52,000 --> 00:04:54,000
to, čo je príznačné to.

86
00:04:54,000 --> 00:04:57,000
>> Teraz si uvedomiť, že testy nie sú nevyhnutne vyčerpávajúce.

87
00:04:57,000 --> 00:04:59,000
Len preto, že dostanete obrazovku plnú zelenej smajlíky

88
00:04:59,000 --> 00:05:02,000
neznamená, že váš kód je perfektný, ale to neznamená,

89
00:05:02,000 --> 00:05:06,000
že prešiel niektoré testy predpísané špec.

90
00:05:06,000 --> 00:05:08,000
Niekedy sme sa neuvoľní kontroly.

91
00:05:08,000 --> 00:05:10,000
Napríklad, detektívka, jeden z aspektov PSet 4,

92
00:05:10,000 --> 00:05:15,000
je druh sklamaním, keby sme vám

93
00:05:15,000 --> 00:05:18,000
odpoveď na otázku, čo to je, a tam je niekoľko spôsobov, ako odhaliť

94
00:05:18,000 --> 00:05:21,000
kto je osobou v tej červenej hluku.

95
00:05:21,000 --> 00:05:24,000
Spec bude vždy uvedené, v budúcnosti PSet 5 dopredu

96
00:05:24,000 --> 00:05:26,000
čo kontroluje existujú pre vás.

97
00:05:26,000 --> 00:05:28,000
Určite ste si všimli, že je to biele URL dole.

98
00:05:28,000 --> 00:05:30,000
Pre túto chvíľu, je to len diagnostická výstup.

99
00:05:30,000 --> 00:05:33,000
Ak navštívite túto adresu URL, dostanete veľa bláznivých, záhadné správy

100
00:05:33,000 --> 00:05:36,000
že ste vítaní prezrieť, ale je to väčšinou pre zamestnancov

101
00:05:36,000 --> 00:05:41,000
takže môžeme diagnostikovať a ladenie chýb v check50 sám.

102
00:05:41,000 --> 00:05:46,000
>> Bez okolkov, poďme sa presunúť na miesta, kde sme skončili.

103
00:05:46,000 --> 00:05:48,000
CS50 knižnica sme považovali za samozrejmosť niekoľko týždňov,

104
00:05:48,000 --> 00:05:52,000
ale potom minulý týždeň, sme začali strhnutím jedného z vrstiev nej.

105
00:05:52,000 --> 00:05:55,000
Začali sme dávať stranou reťazec v prospech čo miesto?

106
00:05:55,000 --> 00:05:57,000
[Študenti] Char.

107
00:05:57,000 --> 00:05:59,000
Char *, ktorý bol char * po celú tú dobu,

108
00:05:59,000 --> 00:06:03,000
ale teraz nemáme predstierať, že je to skutočný dátový typ string.

109
00:06:03,000 --> 00:06:06,000
Skôr, je to už synonymom druhov pre char *,

110
00:06:06,000 --> 00:06:09,000
a reťazec je postupnosť znakov,

111
00:06:09,000 --> 00:06:14,000
tak prečo to zmysel reprezentovať reťazca ako * char s?

112
00:06:14,000 --> 00:06:20,000
Čo char * predstavujú v rámci tejto koncepcie reťazca?

113
00:06:20,000 --> 00:06:23,000
Jo. >> [Študent] Prvý znak.

114
00:06:23,000 --> 00:06:25,000
Dobrý, prvý znak, ale nie úplne prvý znak.

115
00:06:25,000 --> 00:06:27,000
Sú to-[Študenti] Address.

116
00:06:27,000 --> 00:06:29,000
Dobrý, adresa prvého znaku.

117
00:06:29,000 --> 00:06:33,000
Všetko, čo je potrebné na reprezentáciu reťazec v pamäti počítača

118
00:06:33,000 --> 00:06:36,000
je len jedinečná adresa jeho prvého bajtu.

119
00:06:36,000 --> 00:06:38,000
Nemusíte ani vedieť, ako dlho to je

120
00:06:38,000 --> 00:06:42,000
pretože ako môžete zistiť, že sa dynamicky?

121
00:06:42,000 --> 00:06:44,000
[Študent] Dĺžka reťazca.

122
00:06:44,000 --> 00:06:48,000
Môžete volať dĺžku reťazca, vynikajúci, ale ako sa dĺžky reťazca prácu?

123
00:06:48,000 --> 00:06:50,000
Čo to robí? Jo.

124
00:06:50,000 --> 00:06:52,000
[Študent] Pokračujte, kým sa dostanete na nulový znak.

125
00:06:52,000 --> 00:06:54,000
Jo, presne tak, to len opakuje s pre slučky, zatiaľ čo slučka,

126
00:06:54,000 --> 00:06:57,000
čo od * do konca, a koniec je reprezentovaný

127
00:06:57,000 --> 00:07:01,000
z \ 0, tzv znak NUL, núl,

128
00:07:01,000 --> 00:07:05,000
nesmie zamieňať s hodnotou null, čo je ukazovateľ,

129
00:07:05,000 --> 00:07:07,000
ktorý príde v rozhovore dnes znova.

130
00:07:07,000 --> 00:07:11,000
>> Sme zlúpnuť vrstvu GetInt, a potom sme sa pozreli na GetString,

131
00:07:11,000 --> 00:07:14,000
a pripomínajú, že obe tieto funkcie, alebo naozaj,

132
00:07:14,000 --> 00:07:18,000
GetString, bolo pomocou určitej funkcie

133
00:07:18,000 --> 00:07:21,000
skutočne analyzovať, to je, čítať alebo analyzovať, vstup užívateľa.

134
00:07:21,000 --> 00:07:25,000
A čo to bolo nové funkcie?

135
00:07:25,000 --> 00:07:27,000
Scanf alebo sscanf. Je to vlastne príde v niekoľkých rôznych príchutiach.

136
00:07:27,000 --> 00:07:31,000
Tam je scanf, tam sscanf, tam je fscanf.

137
00:07:31,000 --> 00:07:35,000
Pre túto chvíľu, aj keď, poďme zamerať na jeden najviac ľahko ilustrované,

138
00:07:35,000 --> 00:07:38,000
a nechaj ma ísť dopredu a otvoriť v prístroji

139
00:07:38,000 --> 00:07:41,000
súbor takto, scanf1.c.

140
00:07:41,000 --> 00:07:43,000
To je super jednoduchý program,

141
00:07:43,000 --> 00:07:46,000
ale že robí niečo, čo sme ešte nikdy neurobili

142
00:07:46,000 --> 00:07:48,000
bez pomoci CS50 knižnice.

143
00:07:48,000 --> 00:07:51,000
To dostane int od užívateľa. Ako to funguje?

144
00:07:51,000 --> 00:07:53,000
No, v riadku 16 tam,

145
00:07:53,000 --> 00:07:56,000
Všimnite si, že sme deklarovať int s názvom X, a na tomto mieste v príbehu,

146
00:07:56,000 --> 00:07:58,000
to, čo je hodnota x?

147
00:07:58,000 --> 00:08:00,000
[Nepočuteľné Študent odpoveď]

148
00:08:00,000 --> 00:08:02,000
[David M.] Právo, kto vie, niektoré odpadky hodnota potenciálne, tak v 17, sme len povedať užívateľa

149
00:08:02,000 --> 00:08:06,000
daj mi číslo, prosím, a krok 18 je miesto, kde to začína byť zaujímavé.

150
00:08:06,000 --> 00:08:11,000
Scanf Zdá sa, že požičať nápad z printf v tom, že používa tieto formátovacie kódy v úvodzovkách.

151
00:08:11,000 --> 00:08:13,000
% D je samozrejme desatinné číslo.

152
00:08:13,000 --> 00:08:21,000
Ale prečo som okolo v & X miesto len x?

153
00:08:21,000 --> 00:08:24,000
Prvá z nich je správna. Jo.

154
00:08:24,000 --> 00:08:26,000
[Nepočuteľné Študent odpoveď]

155
00:08:26,000 --> 00:08:31,000
Presne, v prípade, že cieľom tohto programu, ako funkcie GetInt sám,

156
00:08:31,000 --> 00:08:34,000
je získať int od užívateľa môžem odovzdať funkcie

157
00:08:34,000 --> 00:08:38,000
všetky premenné chcem, ale keď nemám okolo nich odkazom

158
00:08:38,000 --> 00:08:41,000
alebo adresy alebo ukazovateľ, všetko synonymom pre dnešné účely,

159
00:08:41,000 --> 00:08:46,000
potom táto funkcia nemá možnosť zmeniť obsah tejto premennej.

160
00:08:46,000 --> 00:08:49,000
To by odovzdať kópiu rovnako ako buggy verzii swapu

161
00:08:49,000 --> 00:08:51,000
že sme hovorili o niekoľkých časoch teraz.

162
00:08:51,000 --> 00:08:54,000
>> Ale namiesto toho, tým, že robí a x, som doslova okolo v čom?

163
00:08:54,000 --> 00:08:57,000
[Študent] adresa. >> Adresu x.

164
00:08:57,000 --> 00:09:01,000
Je to ako kreslenie mapy pre funkciu nazvanú scanf a tú hovorí,

165
00:09:01,000 --> 00:09:04,000
sú smery na kusu pamäte v počítači

166
00:09:04,000 --> 00:09:07,000
že môžete ísť ukladať nejaké celé číslo a

167
00:09:07,000 --> 00:09:10,000
Aby sscanf do teraz robiť, že

168
00:09:10,000 --> 00:09:13,000
čo operátor, čo kus syntax ich bude musieť použiť

169
00:09:13,000 --> 00:09:19,000
aj keď nemôžeme vidieť, pretože niekto iný napísal túto funkciu?

170
00:09:19,000 --> 00:09:21,000
Inými slovami - čo to je?

171
00:09:21,000 --> 00:09:23,000
[Študent] X čítať.

172
00:09:23,000 --> 00:09:27,000
Tam to bude nejaké čítanie, ale len s ohľadom na x tu.

173
00:09:27,000 --> 00:09:30,000
Ak scanf je odovzdaná adresu x,

174
00:09:30,000 --> 00:09:35,000
syntakticky, čo je prevádzkovateľ povinný niekde existujú

175
00:09:35,000 --> 00:09:38,000
vnútri vykonávanie scanf je tak, že scanf

176
00:09:38,000 --> 00:09:42,000
môže skutočne napísať číslo 2 na túto adresu?

177
00:09:42,000 --> 00:09:44,000
Jo, takže *.

178
00:09:44,000 --> 00:09:47,000
Pripomeňme si, že * je naša dereferencia operátor, čo v podstate znamená tam.

179
00:09:47,000 --> 00:09:50,000
>> Akonáhle bola odovzdaná adresu, ako je tomu tu,

180
00:09:50,000 --> 00:09:53,000
scanf je pravdepodobne Ak sa skutočne pozrel okolo jeho zdrojový kód,

181
00:09:53,000 --> 00:09:59,000
robí * x alebo ekvivalent skutočne ísť na túto adresu a dať nejakú hodnotu tam.

182
00:09:59,000 --> 00:10:02,000
Teraz, ako na to, ako scanf dostane vstup z klávesnice,

183
00:10:02,000 --> 00:10:04,000
budeme mávať rukami von pre dnešok.

184
00:10:04,000 --> 00:10:07,000
Len predpokladať, že operačný systém umožňuje sscanf hovoriť

185
00:10:07,000 --> 00:10:11,000
na užívateľa klávesnice, ale v tomto okamihu teraz v súlade 19,

186
00:10:11,000 --> 00:10:14,000
keď sme jednoducho vytlačiť x, sa zdá byť prípad

187
00:10:14,000 --> 00:10:17,000
že scanf dal int v x.

188
00:10:17,000 --> 00:10:19,000
To je presne to, ako scanf funguje, a pripomínajú minulý týždeň

189
00:10:19,000 --> 00:10:25,000
to je presne to, ako GetString a GetInt a jej ďalšie rodina funkcií

190
00:10:25,000 --> 00:10:28,000
nakoniec funguje, aj keď s miernym rozptylu ako sscanf,

191
00:10:28,000 --> 00:10:31,000
čo znamená, že skenovanie reťazec namiesto klávesnice.

192
00:10:31,000 --> 00:10:33,000
Ale poďme sa pozrieť na malú odchýlkou ​​to.

193
00:10:33,000 --> 00:10:37,000
V scanf2, som vlastne podelal.

194
00:10:37,000 --> 00:10:42,000
Čo je zle a ja skryť komentár, ktorý vysvetľuje, ako veľa-

195
00:10:42,000 --> 00:10:47,000
Čo je zle s týmto programom, verzia 2?

196
00:10:47,000 --> 00:10:55,000
Buďte tak technické, ako je to možné dobe.

197
00:10:55,000 --> 00:10:57,000
Vyzerá to celkom dobre.

198
00:10:57,000 --> 00:11:03,000
Je to pekne odsadený, ale-

199
00:11:03,000 --> 00:11:07,000
v poriadku, ako sa o poďme strih do kratších otázky?

200
00:11:07,000 --> 00:11:17,000
Riadok 16. Čo je to linka 16 robí v presnom, ale technické angličtiny?

201
00:11:17,000 --> 00:11:20,000
Získanie trochu trápne. Áno, Michael.

202
00:11:20,000 --> 00:11:25,000
[Študent] Je to s poukazom na prvé písmeno reťazca.

203
00:11:25,000 --> 00:11:27,000
>> Dobre, úzkym. Dovoľte mi, aby som trik, že trochu.

204
00:11:27,000 --> 00:11:33,000
S poukazom na prvé písmeno reťazca, s ktorým sa premenná s názvom vyrovnávacia pamäť

205
00:11:33,000 --> 00:11:36,000
že bude smerovať k prvému adresu reťazca,

206
00:11:36,000 --> 00:11:39,000
alebo skôr, bude to ukazovať konkrétne na char.

207
00:11:39,000 --> 00:11:42,000
Všimnite si, že to nie je v skutočnosti ukazuje všade, pretože neexistuje žiadny operátor priradenia.

208
00:11:42,000 --> 00:11:46,000
Nie je znamienko rovná sa, takže všetko, čo robia, je rozdelenie premennej tzv vyrovnávacej pamäte.

209
00:11:46,000 --> 00:11:49,000
Stáva sa, že je 32 bitov, pretože je to ukazovateľ,

210
00:11:49,000 --> 00:11:52,000
a obsah pufra pravdepodobne nakoniec

211
00:11:52,000 --> 00:11:57,000
bude obsahovať adresu char, ale teraz, čo pufer obsahuje?

212
00:11:57,000 --> 00:11:59,000
To sú len niektoré falošné, kto vie, niektoré odpadky hodnota,

213
00:11:59,000 --> 00:12:03,000
pretože sme explicitne inicializovať, takže sme nemali nič predpokladať.

214
00:12:03,000 --> 00:12:06,000
Dobre, takže teraz linka 17 je-čo linka 17 robiť?

215
00:12:06,000 --> 00:12:08,000
Možno, že bude ohrievať toto hore.

216
00:12:08,000 --> 00:12:10,000
To vytlačí reťazec, nie?

217
00:12:10,000 --> 00:12:12,000
Tlačí String prosím.

218
00:12:12,000 --> 00:12:15,000
>> Linka 18 je trochu oboznámený teraz v tom, že sme práve videli, rozptyl tohto

219
00:12:15,000 --> 00:12:18,000
ale s iným formátu kódu, tak v riadku 18,

220
00:12:18,000 --> 00:12:23,000
hovoríme scanf je tu adresa bloku pamäte.

221
00:12:23,000 --> 00:12:27,000
Chcem, aby si, aby vás v reťazci, ako vyplýva z% s,

222
00:12:27,000 --> 00:12:32,000
ale problém je, že sme neurobili pár vecí tu.

223
00:12:32,000 --> 00:12:35,000
Čo je to jeden z problémov?

224
00:12:35,000 --> 00:12:38,000
[Študent] Snaží sa dereferencia ukazovatele null.

225
00:12:38,000 --> 00:12:41,000
Dobré, null, alebo len inak neznámy ukazovatele.

226
00:12:41,000 --> 00:12:45,000
Tie podal scanf adresu, ale práve si povedala pred chvíľou

227
00:12:45,000 --> 00:12:49,000
táto adresa je asi nezmyselné hodnoty, pretože sme nemali vlastne priradiť ju k ničomu,

228
00:12:49,000 --> 00:12:53,000
a tak hovoríte scanf účinne ísť dať reťazec tu,

229
00:12:53,000 --> 00:12:56,000
ale nevieme, kde tu ešte je,

230
00:12:56,000 --> 00:12:59,000
takže sme sa vlastne pridelené pamäte pre vyrovnávaciu pamäť.

231
00:12:59,000 --> 00:13:03,000
Navyše, to, čo ste tiež ani hovoriť scanf?

232
00:13:03,000 --> 00:13:06,000
Predpokladám, že to bol kus pamäte, a to nebolo odpadky hodnotu,

233
00:13:06,000 --> 00:13:09,000
ale stále nehovoríš scanf niečo dôležité.

234
00:13:09,000 --> 00:13:12,000
[Študent] Kde to vlastne je, ampersand.

235
00:13:12,000 --> 00:13:15,000
Ampersand, takže v tomto prípade, je to v poriadku.

236
00:13:15,000 --> 00:13:18,000
Vzhľadom k tomu, vyrovnávacia pamäť je už deklarovaný ako ukazovateľ

237
00:13:18,000 --> 00:13:22,000
s * kus syntaxe, nepotrebujeme použiť ampersand

238
00:13:22,000 --> 00:13:25,000
pretože je to už adresu, ale myslím, že som to počul sem.

239
00:13:25,000 --> 00:13:27,000
[Študent] Ako je to veľké?

240
00:13:27,000 --> 00:13:29,000
Dobré, my nehovoríš scanf, aký veľký tento buffer,

241
00:13:29,000 --> 00:13:32,000
čo znamená, že aj keď sa vyrovnávacia ukazovateľ,

242
00:13:32,000 --> 00:13:35,000
hovoríme scanf, dal reťazec tu,

243
00:13:35,000 --> 00:13:38,000
ale tu by mohlo byť 2 bytov, mohlo by to byť 10 bytov, mohlo by to byť megabajt.

244
00:13:38,000 --> 00:13:41,000
Scanf nemá ani potuchy, a pretože to je kus pamäte

245
00:13:41,000 --> 00:13:43,000
pravdepodobne, že to nie je reťazec doteraz.

246
00:13:43,000 --> 00:13:48,000
Je to len reťazec akonáhle písať znaky a \ 0 na tomto kuse pamäti.

247
00:13:48,000 --> 00:13:51,000
Teraz je to len nejaký kus pamäte.

248
00:13:51,000 --> 00:13:55,000
Scanf nebude vedieť, kedy prestať písať na túto adresu.

249
00:13:55,000 --> 00:13:59,000
>> Ak si spomeniete, niektoré príklady v minulosti, keď som náhodne písané na klávesnici

250
00:13:59,000 --> 00:14:03,000
sa snaží pretečeniu vyrovnávacej pamäte, a hovorili sme o tom v piatok presne to.

251
00:14:03,000 --> 00:14:07,000
Ak protivník nejako vstrekuje do svojho programu oveľa väčšie slovo

252
00:14:07,000 --> 00:14:10,000
alebo veta alebo fráza potom ste čakali, môžete prekročení

253
00:14:10,000 --> 00:14:13,000
kus pamäte, ktorý môže mať zlé následky,

254
00:14:13,000 --> 00:14:15,000
ako prevzatie celého programu samotného.

255
00:14:15,000 --> 00:14:17,000
Musíme to opraviť nejako.

256
00:14:17,000 --> 00:14:20,000
Dovoľte mi, aby som oddialiť a ísť do verzie 3 tohto programu.

257
00:14:20,000 --> 00:14:22,000
To je trochu lepšie.

258
00:14:22,000 --> 00:14:24,000
V tejto verzii, všimnete rozdielu.

259
00:14:24,000 --> 00:14:27,000
V riadku 16, som opäť deklarovať premennú s názvom vyrovnávacej pamäte,

260
00:14:27,000 --> 00:14:29,000
ale čo je to teraz?

261
00:14:29,000 --> 00:14:33,000
Je to rad 16 znakov.

262
00:14:33,000 --> 00:14:36,000
To je dobre, pretože to znamená, že môžem teraz povedať, scanf

263
00:14:36,000 --> 00:14:39,000
Tu je skutočný kus pamäte.

264
00:14:39,000 --> 00:14:42,000
Môžete takmer myslieť polí ako ukazovatele teraz,

265
00:14:42,000 --> 00:14:44,000
aj keď sú v skutočnosti ekvivalentné.

266
00:14:44,000 --> 00:14:47,000
Budú sa správajú odlišne v rôznych kontextoch.

267
00:14:47,000 --> 00:14:50,000
Ale je to určite pravda, že vyrovnávacia pamäť je odkazovanie

268
00:14:50,000 --> 00:14:53,000
16 po sebe idúcich znakov, pretože to je to, čo pole je

269
00:14:53,000 --> 00:14:55,000
a bol niekoľko týždňov teraz.

270
00:14:55,000 --> 00:14:59,000
>> Tu, hovorím scanf tu kus pamäte.

271
00:14:59,000 --> 00:15:01,000
Tentokrát, je to vlastne kus pamäte,

272
00:15:01,000 --> 00:15:07,000
ale prečo je tento program stále využiteľný?

273
00:15:07,000 --> 00:15:11,000
Čo sa deje stále?

274
00:15:11,000 --> 00:15:14,000
Ja som povedal, daj mi 16 bajtov, ale-

275
00:15:14,000 --> 00:15:16,000
[Študent] Čo keď typ vo viac ako 16?

276
00:15:16,000 --> 00:15:20,000
Presne, čo keď používateľ zadá do 17 znakov alebo 1700 znakov?

277
00:15:20,000 --> 00:15:23,000
V skutočnosti, uvidíme, či nemôžeme výlet cez túto chybu hneď.

278
00:15:23,000 --> 00:15:25,000
Je to lepšie, ale nie je dokonalý.

279
00:15:25,000 --> 00:15:28,000
Nechaj ma ísť napred a spustite make scanf3 zostaviť tento program.

280
00:15:28,000 --> 00:15:34,000
Dovoľte mi, aby som bežať scanf3, String prosím: ahoj, a zdá sa, že bude v poriadku.

281
00:15:34,000 --> 00:15:37,000
Nechaj ma to skúsiť mierne dlhšia jeden, hello there.

282
00:15:37,000 --> 00:15:42,000
Dobre, poďme si hello there ako sa dnes máte, Enter.

283
00:15:42,000 --> 00:15:54,000
Získanie druh šťastie tu, povedzme, hello there ako sa máš.

284
00:15:54,000 --> 00:15:56,000
Sakra.

285
00:15:56,000 --> 00:16:03,000
Dobre, takže máme šťastie. Poďme sa pozrieť, či nemôžeme napraviť.

286
00:16:03,000 --> 00:16:06,000
Nie, to nebude, aby som kopírovať.

287
00:16:06,000 --> 00:16:09,000
Skúsme to znovu.

288
00:16:09,000 --> 00:16:12,000
Dobre, pripravte sa.

289
00:16:12,000 --> 00:16:20,000
Uvidíme, ako dlho môžem predstierať, že sa sústrediť a pritom robí.

290
00:16:20,000 --> 00:16:23,000
Sakra. To je dosť vhodné, v skutočnosti.

291
00:16:23,000 --> 00:16:26,000
Tam ideme.

292
00:16:26,000 --> 00:16:30,000
Point vykonaná.

293
00:16:30,000 --> 00:16:34,000
>> To nepríjemné keď to tiež je, že je tiež jeden zo zdrojov veľkom zmätku

294
00:16:34,000 --> 00:16:38,000
pri písaní programov, ktoré majú chyby, pretože sa prejavujú

295
00:16:38,000 --> 00:16:40,000
len raz za čas niekedy.

296
00:16:40,000 --> 00:16:43,000
Skutočnosť je taká, že aj keď váš kód je úplne rozbité,

297
00:16:43,000 --> 00:16:46,000
to by mohlo byť úplne rozbité raz za čas

298
00:16:46,000 --> 00:16:49,000
pretože niekedy, v podstate, čo sa stane, je, že operačný systém prideľuje

299
00:16:49,000 --> 00:16:52,000
trochu viac pamäte, než je skutočne nutné z akéhokoľvek dôvodu,

300
00:16:52,000 --> 00:16:57,000
a tak nikto iný využitie pamäte bezprostredne po kuse 16 znakov,

301
00:16:57,000 --> 00:17:01,000
takže ak idete na 17, 18, 19, bez ohľadu na, že to nie je tak veľký problém.

302
00:17:01,000 --> 00:17:04,000
Teraz, počítač, aj keď to nie je zlyhanie v tomto bode,

303
00:17:04,000 --> 00:17:09,000
môže v konečnom dôsledku používať byte číslo 17, 18, alebo 19 pre niečo iné,

304
00:17:09,000 --> 00:17:14,000
na ktorom mieste si údaje, ktoré ste tam dal, aj keď príliš dlho,

305
00:17:14,000 --> 00:17:18,000
dostane prepísané potenciálne iným funkcií.

306
00:17:18,000 --> 00:17:21,000
Nie je to nutne ísť zostať neporušený,

307
00:17:21,000 --> 00:17:23,000
ale to nemusí nutne spôsobiť seg poruchu.

308
00:17:23,000 --> 00:17:26,000
Ale v tomto prípade, som konečne poskytol dostatok znakov

309
00:17:26,000 --> 00:17:29,000
že som v podstate prekročila svoj segment pamäte, a bum,

310
00:17:29,000 --> 00:17:33,000
operačný systém povedal, "Je mi ľúto, že to nie je dobré, Segmentation fault."

311
00:17:33,000 --> 00:17:38,000
>> A uvidíme, či to, čo teraz zostane tu v mojom adresári,

312
00:17:38,000 --> 00:17:40,000
Všimnite si, že som tento súbor tu, jadro.

313
00:17:40,000 --> 00:17:42,000
Všimnite si, že toto je opäť nazýva core dump.

314
00:17:42,000 --> 00:17:46,000
Je to v podstate súbor, ktorý obsahuje obsah vášho programu do pamäti

315
00:17:46,000 --> 00:17:48,000
v mieste, v ktorom je havaroval,

316
00:17:48,000 --> 00:17:51,000
a len skúsiť malý príklad tu nechaj ma ísť sem

317
00:17:51,000 --> 00:17:57,000
a spustiť gdb na scanf3 a potom zadať tretí argument s názvom core,

318
00:17:57,000 --> 00:18:01,000
a všimnite si, že keď som tu vypísať kód,

319
00:18:01,000 --> 00:18:06,000
budeme môcť ako zvyčajne s gdb, kto prechádzal tohto programu,

320
00:18:06,000 --> 00:18:10,000
a môžem spustiť, a akonáhle som narazila-ako s krokom príkaz do gdb-

321
00:18:10,000 --> 00:18:13,000
akonáhle som narazila na potenciálne buggy riadok po zadaní v obrovskej reťazca,

322
00:18:13,000 --> 00:18:16,000
Budem schopný skutočne identifikovať ho sem.

323
00:18:16,000 --> 00:18:19,000
Viac informácií o tomto, keď v sekcii, pokiaľ ide o core dump

324
00:18:19,000 --> 00:18:22,000
a podobným spôsobom, ktorý je možné skutočne hrabať okolo vnútri jadra skládky

325
00:18:22,000 --> 00:18:27,000
a vidieť, čo riadok programu sklamal.

326
00:18:27,000 --> 00:18:32,000
Akékoľvek otázky potom na ukazovateli a adresy?

327
00:18:32,000 --> 00:18:36,000
Pretože dnes, budeme začať užívať za samozrejmé, že tieto veci existujú

328
00:18:36,000 --> 00:18:40,000
a presne vieme, čo sú zač.

329
00:18:40,000 --> 00:18:42,000
Áno.

330
00:18:42,000 --> 00:18:46,000
>> [Študent] Ako to, že nemusel dať ampersand vedľa časti-

331
00:18:46,000 --> 00:18:48,000
Dobrá otázka.

332
00:18:48,000 --> 00:18:51,000
Ako to, že som nemal dať ampersand vedľa poľa znakov, ako som to urobil skôr

333
00:18:51,000 --> 00:18:53,000
s väčšinou z našich príkladov?

334
00:18:53,000 --> 00:18:55,000
Stručná odpoveď je polia sú trochu zvláštne.

335
00:18:55,000 --> 00:18:59,000
Môžete takmer premýšľať vyrovnávacej pamäte ako by v skutočnosti bol adresu,

336
00:18:59,000 --> 00:19:03,000
a to len tak sa stane, že je pravda, že hranatá zátvorka notácie

337
00:19:03,000 --> 00:19:06,000
je pohodlie, takže môžeme ísť do držiaka 0, držiakom 1,

338
00:19:06,000 --> 00:19:10,000
držiak 2, bez toho aby museli používať * zápis.

339
00:19:10,000 --> 00:19:13,000
To je trochu lož, pretože pole a ukazovatele

340
00:19:13,000 --> 00:19:17,000
sú v skutočnosti, trochu iná, ale oni môžu často, ale nie vždy používajú zameniteľné.

341
00:19:17,000 --> 00:19:21,000
Stručne povedané, ak funkcia očakáva ukazovateľ na kus pamäti,

342
00:19:21,000 --> 00:19:24,000
môžete buď odovzdať adresu, ktorá bola vrátená malloc,

343
00:19:24,000 --> 00:19:29,000
a uvidíme, malloc zase netrvalo dlho, alebo môžete odovzdať názov poľa.

344
00:19:29,000 --> 00:19:32,000
Nemusíte robiť ampersand s poľami, pretože sú už

345
00:19:32,000 --> 00:19:34,000
v podstate ako adresy.

346
00:19:34,000 --> 00:19:36,000
To je jedna výnimka.

347
00:19:36,000 --> 00:19:39,000
Hranaté zátvorky, aby boli zvláštne.

348
00:19:39,000 --> 00:19:41,000
>> Mohli by ste dať ampersand vedľa vyrovnávacej pamäte?

349
00:19:41,000 --> 00:19:43,000
Nie v tomto prípade.

350
00:19:43,000 --> 00:19:46,000
To nebude fungovať, pretože, opäť, z tohto rohu veci

351
00:19:46,000 --> 00:19:49,000
kde pole nie sú tak vlastne adries.

352
00:19:49,000 --> 00:19:54,000
Ale my snáď vrátiť k tomu onedlho s ďalšími príkladmi.

353
00:19:54,000 --> 00:19:56,000
Poďme sa snaží vyriešiť problém tu.

354
00:19:56,000 --> 00:20:00,000
Máme štruktúru dát, ktoré sme sa pomocou dlhšiu dobu známe ako pole.

355
00:20:00,000 --> 00:20:02,000
Vec v bode, že je to to, čo sme práve mali.

356
00:20:02,000 --> 00:20:04,000
Ale polia majú nejaký upsides a tienisté stránky.

357
00:20:04,000 --> 00:20:06,000
Polia sú pekné, prečo?

358
00:20:06,000 --> 00:20:11,000
Čo je jedna vec, ktorá sa vám páči, a to v rozsahu vám páči pole-o pole?

359
00:20:11,000 --> 00:20:13,000
Čo je vhodné o nich? Čo je to presvedčivý?

360
00:20:13,000 --> 00:20:18,000
Prečo sme sa predstaviť je na prvom mieste?

361
00:20:18,000 --> 00:20:20,000
Jo.

362
00:20:20,000 --> 00:20:27,000
[Študent] Môžu uložiť veľké množstvo dát, a nemusíte používať celú vec.

363
00:20:27,000 --> 00:20:29,000
Môžete použiť časť.

364
00:20:29,000 --> 00:20:32,000
Dobré, s radom môžete uložiť veľké množstvo dát,

365
00:20:32,000 --> 00:20:35,000
a nemusíte nutne používať všetko, takže môžete overallocate,

366
00:20:35,000 --> 00:20:39,000
ktoré by mohli byť užitočné, ak nemáte vopred vedieť, koľko niečo očakávať.

367
00:20:39,000 --> 00:20:41,000
>> GetString je dokonalým príkladom.

368
00:20:41,000 --> 00:20:44,000
GetString, napísal nám, nemá ani potuchy, koľko znakov sa očakávať,

369
00:20:44,000 --> 00:20:48,000
takže skutočnosť, že môžeme prideliť kusy súvislej pamäte je dobrá.

370
00:20:48,000 --> 00:20:51,000
Pole tiež vyriešiť problém, čo sme videli pred pár týždňami dnes

371
00:20:51,000 --> 00:20:54,000
kde váš kód začína prešla do niečoho veľmi zle navrhnutý.

372
00:20:54,000 --> 00:20:57,000
Pripomeňme si, že som vytvoril študent štruktúru nazvanú David,

373
00:20:57,000 --> 00:21:00,000
a potom, že bol vlastne alternatíva, aj keď,

374
00:21:00,000 --> 00:21:04,000
, Aby s premennou s názvom meno a ďalšie premenné s názvom, myslím, dom,

375
00:21:04,000 --> 00:21:08,000
a ďalšie premenné volal ID, pretože v tomto príbehu, ktorý som potom chcel predstaviť niečo iné

376
00:21:08,000 --> 00:21:11,000
Páči Roberta do programu, tak som sa rozhodol počkať,

377
00:21:11,000 --> 00:21:13,000
Musím premenovať tieto premenné.

378
00:21:13,000 --> 00:21:16,000
Hovorme moja NAME1, ID1, house1.

379
00:21:16,000 --> 00:21:20,000
Hovorme Robova name2, house2, ID2.

380
00:21:20,000 --> 00:21:22,000
Ale potom počkať, čo o Tommym?

381
00:21:22,000 --> 00:21:24,000
Potom sme mali ďalšie tri premenné.

382
00:21:24,000 --> 00:21:27,000
Zaviedli sme niekoho iného, ​​štyri sady premenných.

383
00:21:27,000 --> 00:21:30,000
Svet začal dostať chaotický veľmi rýchlo,

384
00:21:30,000 --> 00:21:33,000
tak sme zaviedli structs, a čo je presvedčivá struct?

385
00:21:33,000 --> 00:21:39,000
Čo struct C nechať urobiť?

386
00:21:39,000 --> 00:21:42,000
Je to naozaj trápne dnes.

387
00:21:42,000 --> 00:21:44,000
Čo? >> [Nepočuteľné Študent odpoveď]

388
00:21:44,000 --> 00:21:47,000
Jo, konkrétne typedef umožňuje vytvoriť nový dátový typ,

389
00:21:47,000 --> 00:21:51,000
a struct, že struct kľúčové slovo, umožňuje zapouzdřit

390
00:21:51,000 --> 00:21:54,000
koncepčne súvisiace kúsky dát dohromady

391
00:21:54,000 --> 00:21:56,000
a potom im hovoria niečo ako študenta.

392
00:21:56,000 --> 00:21:58,000
>> To bolo dobre, pretože teraz môžeme modelovať

393
00:21:58,000 --> 00:22:03,000
oveľa viac druh koncepčne konzistentné pojem študenta v premennej

394
00:22:03,000 --> 00:22:07,000
skôr než svojvoľne mať jeden pre reťazec, jeden identifikátor, a tak ďalej.

395
00:22:07,000 --> 00:22:10,000
Polia sú pekné, pretože nám umožní začať upratovať náš kód.

396
00:22:10,000 --> 00:22:13,000
Ale čo je nevýhoda teraz z poľa?

397
00:22:13,000 --> 00:22:15,000
Čo môžete to urobiť? Jo.

398
00:22:15,000 --> 00:22:17,000
[Študent] Musíte vedieť, ako je veľký.

399
00:22:17,000 --> 00:22:19,000
Musíte vedieť, ako je to veľké, takže je to trochu bolesti.

400
00:22:19,000 --> 00:22:21,000
Tí z vás, s predchádzajúcim programovacím skúsenosti vieme, že v mnohých jazykoch,

401
00:22:21,000 --> 00:22:24,000
ako Java, môžete požiadať kus pamäte, konkrétne pole,

402
00:22:24,000 --> 00:22:28,000
aký veľký ste, s dĺžkou, majetku, tak povediac, a to je naozaj pohodlné.

403
00:22:28,000 --> 00:22:32,000
V jazyku C, nemôžete ani volať strlen na generické pole

404
00:22:32,000 --> 00:22:35,000
pretože strlen, ako slovo znamená, je len pre reťazce,

405
00:22:35,000 --> 00:22:39,000
a je možné zistiť dĺžku reťazca, pretože v tomto ľudskej konvencie

406
00:22:39,000 --> 00:22:43,000
mať na \ 0, ale celú škálu, viac druhovo, je len kus pamäte.

407
00:22:43,000 --> 00:22:46,000
Ak je to pole ints, že to nebude mať nejaký špeciálny znak

408
00:22:46,000 --> 00:22:48,000
Na konci na vás čaká.

409
00:22:48,000 --> 00:22:50,000
Musíte si uvedomiť, dĺžku poľa.

410
00:22:50,000 --> 00:22:54,000
Ďalšou nevýhodou pole dvíha hlavu v GetString sám.

411
00:22:54,000 --> 00:22:59,000
Čo je ďalší nevýhoda pole?

412
00:22:59,000 --> 00:23:01,000
Pane, len ty a ja dnes.

413
00:23:01,000 --> 00:23:04,000
[Nepočuteľné Študent odpoveď] >> To je to, čo?

414
00:23:04,000 --> 00:23:06,000
Je to vyhlásil na zásobníku.

415
00:23:06,000 --> 00:23:09,000
Dobre, vyhlásil na zásobníku. Prečo nemáš rád, že?

416
00:23:09,000 --> 00:23:13,000
[Študent] Vzhľadom k tomu, že dostane znova.

417
00:23:13,000 --> 00:23:15,000
To dostane znova.

418
00:23:15,000 --> 00:23:18,000
Dobre, ak používate pole alokovať pamäť,

419
00:23:18,000 --> 00:23:21,000
nemôžete, napríklad, vrátiť, pretože je to na zásobníku.

420
00:23:21,000 --> 00:23:23,000
Dobre, že je to nevýhoda.

421
00:23:23,000 --> 00:23:25,000
A čo takto jeden ďalší s radom?

422
00:23:25,000 --> 00:23:28,000
Akonáhle prideliť ju, si trochu skrutkované, ak potrebujete viac miesta

423
00:23:28,000 --> 00:23:30,000
ako pole má.

424
00:23:30,000 --> 00:23:34,000
>> Potom sme zaviedli, obnovu, malloc, ktorý nám dal schopnosť dynamicky alokovať pamäť.

425
00:23:34,000 --> 00:23:37,000
Ale čo keď sme sa snažili iný svet dohromady?

426
00:23:37,000 --> 00:23:40,000
Čo keď budeme chcieť riešiť niekoľko týchto problémov

427
00:23:40,000 --> 00:23:45,000
tak sme namiesto toho, moje pero zaspal tu-

428
00:23:45,000 --> 00:23:51,000
čo keby sme namiesto toho chceli v podstate vytvoriť svet, ktorý je už takto?

429
00:23:51,000 --> 00:23:56,000
To je pole, a, samozrejme, tento druh zhoršuje, akonáhle sa dostaneme na koniec poľa,

430
00:23:56,000 --> 00:24:00,000
a teraz už majú priestor pre ďalšie celé číslo alebo iný znak.

431
00:24:00,000 --> 00:24:03,000
Čo keď sme trochu preventívne povedať dobre, prečo nie my relaxovať

432
00:24:03,000 --> 00:24:07,000
túto požiadavku, že všetky tieto kúsky pamäte byť súvislé chrbtom k sebe,

433
00:24:07,000 --> 00:24:10,000
a prečo nie, keď som potrebné int alebo char,

434
00:24:10,000 --> 00:24:12,000
Daj mi priestor pre jedného z nich?

435
00:24:12,000 --> 00:24:14,000
A keď som potrebovať ďalšie, daj mi ďalší priestor,

436
00:24:14,000 --> 00:24:16,000
a keď som potrebovať ďalšie, daj mi ďalší priestor.

437
00:24:16,000 --> 00:24:19,000
Výhodou, ktorá teraz je, že ak niekto iný

438
00:24:19,000 --> 00:24:21,000
berie pamäť tu, žiadny veľký problém.

439
00:24:21,000 --> 00:24:25,000
Chcel by som tento ďalší kus pamäte tu a potom toto.

440
00:24:25,000 --> 00:24:28,000
>> Teraz, len úlovok je, že to takmer pocit, ako by som sa

441
00:24:28,000 --> 00:24:30,000
celá partia rôznych premenných.

442
00:24:30,000 --> 00:24:33,000
Tento pocit piatich rôznych premenných potenciálne.

443
00:24:33,000 --> 00:24:36,000
Ale čo keby sme ukradol nápad z reťazcov

444
00:24:36,000 --> 00:24:41,000
kedy sme nejako prepojiť tieto veci dohromady koncepčne, a čo keď som to urobil?

445
00:24:41,000 --> 00:24:44,000
To je môj veľmi zle vypracovaný arrow.

446
00:24:44,000 --> 00:24:46,000
Predpokladajme však, že každý z týchto blokov z pamäte

447
00:24:46,000 --> 00:24:52,000
ukázal na druhý, a ten chlap, ktorý nemá súrodencov na jeho pravej,

448
00:24:52,000 --> 00:24:54,000
nemá takú šípku.

449
00:24:54,000 --> 00:24:56,000
To je v skutočnosti to, čo sa nazýva prepojený zoznam.

450
00:24:56,000 --> 00:25:00,000
To je nová dátová štruktúra, ktorá nám umožňuje prideliť kus pamäte,

451
00:25:00,000 --> 00:25:03,000
potom ďalší, potom ďalší, potom ďalšie, kedykoľvek chceme

452
00:25:03,000 --> 00:25:07,000
počas programu, a my sme si, že sú všetci nejako súvisiace

453
00:25:07,000 --> 00:25:11,000
doslova priviazať je dohromady, a to sme urobili, že obrazovo sem s šípkou.

454
00:25:11,000 --> 00:25:15,000
Ale v kóde, čo by ich mechanizmus, cez ktorý by ste sa mohli nejako spojiť,

455
00:25:15,000 --> 00:25:20,000
skoro ako Scratch, jeden kus na iný kus?

456
00:25:20,000 --> 00:25:22,000
Mohli by sme použiť ukazovateľ, nie?

457
00:25:22,000 --> 00:25:25,000
Vzhľadom k tomu, naozaj šípka, ktorá sa deje v ľavom hornom námestí,

458
00:25:25,000 --> 00:25:31,000
ten chlap tu k tomuto, by mohli obsahovať vnútri tohto štvorca

459
00:25:31,000 --> 00:25:34,000
nie len niektoré ints, nie len niektoré char, ale čo keď som vlastne pridelené

460
00:25:34,000 --> 00:25:37,000
niečo naviac priestor tak, že teraz,

461
00:25:37,000 --> 00:25:41,000
Každý z mojich kúsky pamäti, aj keď to bude stáť mňa,

462
00:25:41,000 --> 00:25:45,000
teraz vyzerá trochu obdĺžnikový, kde jeden z kúskov pamäte

463
00:25:45,000 --> 00:25:47,000
sa používa pre množstvo, ako je číslo 1,

464
00:25:47,000 --> 00:25:50,000
a potom, ak ten chlap ukladá počet 2,

465
00:25:50,000 --> 00:25:52,000
Tento ďalší kus pamäte sa používa pre šípkou,

466
00:25:52,000 --> 00:25:54,000
alebo konkrétnejšie, ukazovateľ.

467
00:25:54,000 --> 00:25:59,000
A že som chcete uložiť číslo 3 tu, keď som použiť to ukázať na toho chlapca,

468
00:25:59,000 --> 00:26:02,000
a teraz ten chlap, predpokladajme, že chcem len tri takéto kúsky pamäti.

469
00:26:02,000 --> 00:26:05,000
Budem čiaru cez to, že uvedením null.

470
00:26:05,000 --> 00:26:07,000
Neexistuje žiadny ďalší znak.

471
00:26:07,000 --> 00:26:10,000
>> Naozaj, je to, ako môžeme ísť o implementácii

472
00:26:10,000 --> 00:26:12,000
niečo, čo sa nazýva prepojený zoznam.

473
00:26:12,000 --> 00:26:18,000
Spájať zoznam je nová dátová štruktúra, a to odrazový mostík k

474
00:26:18,000 --> 00:26:21,000
oveľa obsiahlejší dátové štruktúry, ktoré začnú riešiť problémy

475
00:26:21,000 --> 00:26:23,000
po vzore Facebook typu problémov a Google typu problémov

476
00:26:23,000 --> 00:26:26,000
kde máte veľké dátové súbory, a to už seká ju

477
00:26:26,000 --> 00:26:29,000
uložiť všetko súvisle a použiť niečo ako lineárny hľadanie

478
00:26:29,000 --> 00:26:31,000
alebo dokonca niečo ako binárne vyhľadávanie.

479
00:26:31,000 --> 00:26:33,000
Ak ešte lepšie jazdné doby.

480
00:26:33,000 --> 00:26:37,000
V skutočnosti, jeden z svätých Grails budeme hovoriť o ešte tento týždeň, alebo budúci

481
00:26:37,000 --> 00:26:41,000
je algoritmus, ktorého hrací čas je konštanta.

482
00:26:41,000 --> 00:26:44,000
Inými slovami, to je vždy na rovnakú dobu bez ohľadu na to

483
00:26:44,000 --> 00:26:47,000
aký veľký je vstup, a že by bolo naozaj presvedčivé,

484
00:26:47,000 --> 00:26:49,000
dokonca viac tak ako niečo logaritmickej.

485
00:26:49,000 --> 00:26:51,000
Čo je to na obrazovke tu?

486
00:26:51,000 --> 00:26:55,000
Každý z obdĺžnikov je presne to, čo som práve nakreslil rúk.

487
00:26:55,000 --> 00:26:59,000
Ale to, čo celú cestu na ľavej strane je špeciálna premenná.

488
00:26:59,000 --> 00:27:02,000
Je to bude jediný ukazovateľ, pretože ten Gotcha

489
00:27:02,000 --> 00:27:04,000
s prepojeného zoznamu, pretože tieto veci sú nazývané,

490
00:27:04,000 --> 00:27:09,000
je to, že budete musieť zavesiť na jednom konci prepojeného zoznamu.

491
00:27:09,000 --> 00:27:13,000
>> Rovnako ako s reťazcom, musíte poznať adresu prvého char.

492
00:27:13,000 --> 00:27:15,000
Rovnaké riešenie pre prepojených zoznamov.

493
00:27:15,000 --> 00:27:19,000
Musíte poznať adresu prvého bloku pamäte

494
00:27:19,000 --> 00:27:25,000
pretože odtiaľ sa môžete dostať každý iný.

495
00:27:25,000 --> 00:27:27,000
Nevýhodou.

496
00:27:27,000 --> 00:27:30,000
Akú cenu sme platiť za túto univerzálnosť s dynamicky

497
00:27:30,000 --> 00:27:34,000
značná dátová štruktúra, ktorá ak budeme niekedy potrebovať viac pamäte, jemné,

498
00:27:34,000 --> 00:27:37,000
Len prideliť jednu blok a nakresliť ukazovateľ z

499
00:27:37,000 --> 00:27:39,000
starého k novému chvosta zoznamu?

500
00:27:39,000 --> 00:27:41,000
Jo.

501
00:27:41,000 --> 00:27:43,000
[Študent] To trvá asi dvakrát tak veľký priestor.

502
00:27:43,000 --> 00:27:45,000
To trvá dvakrát toľko miesta, takže je to určite nevýhoda, a my sme videli to

503
00:27:45,000 --> 00:27:48,000
kompromis pred medzi časom a priestorom a flexibilitou

504
00:27:48,000 --> 00:27:51,000
kde teraz, nemusíme 32 bitov pre každý z týchto čísel.

505
00:27:51,000 --> 00:27:57,000
My naozaj potrebujeme 64, 32 v závislosti od počtu a 32 pre ukazovatele.

506
00:27:57,000 --> 00:27:59,000
Ale hej, mám 2 GB pamäte RAM.

507
00:27:59,000 --> 00:28:02,000
Pridanie ďalších 32 bitov tu a tu sa nezdá, že veľký problém.

508
00:28:02,000 --> 00:28:05,000
Ale pre veľké súbory dát, to určite pridá až doslova dvakrát toľko.

509
00:28:05,000 --> 00:28:09,000
Čo je ďalšia nevýhoda teraz, alebo čo funkcií budeme vzdať,

510
00:28:09,000 --> 00:28:12,000
ak budeme zastupovať zoznam vecí s prepojeného zoznamu a nie pole?

511
00:28:12,000 --> 00:28:14,000
[Študent] Nemôžete prechádzať dozadu.

512
00:28:14,000 --> 00:28:16,000
Nemôžete prechádzať dozadu, takže tak trochu skrutkované, ak idete

513
00:28:16,000 --> 00:28:19,000
zľava doprava pomocou slučky for alebo while cyklu

514
00:28:19,000 --> 00:28:21,000
a potom si uvedomíte, "Oh, chcem sa vrátiť na začiatok zoznamu."

515
00:28:21,000 --> 00:28:26,000
Nemôžete, pretože tieto ukazovatele len ísť zľava doprava ako šípky ukazujú.

516
00:28:26,000 --> 00:28:29,000
>> Teraz môžete spomenúť na začiatok zoznamu s inou premennou,

517
00:28:29,000 --> 00:28:31,000
ale to je zložitosť mať na pamäti.

518
00:28:31,000 --> 00:28:35,000
Pole, bez ohľadu na to, ako ďaleko ísť, vždy môžete urobiť mínus, mínus, mínus, mínus

519
00:28:35,000 --> 00:28:37,000
a vrátiť sa, odkiaľ si prišiel.

520
00:28:37,000 --> 00:28:40,000
Čo je ďalší nevýhoda tu? Jo.

521
00:28:40,000 --> 00:28:43,000
[Nepočuteľné Študent otázka]

522
00:28:43,000 --> 00:28:47,000
Dalo by sa, tak ste vlastne len navrhnutej dátovej štruktúry zvané dvojnásobne spájať zoznam,

523
00:28:47,000 --> 00:28:50,000
a naozaj, mali by ste pridať ďalší ukazovateľ pre každý z týchto obdĺžnikov

524
00:28:50,000 --> 00:28:53,000
že ide opačným smerom, je hore, ktoré

525
00:28:53,000 --> 00:28:55,000
Teraz ich môžete prechádzať tam a späť,

526
00:28:55,000 --> 00:28:59,000
Nevýhodou, ktorá je teraz používate trikrát toľko pamäte, ako sme zvyknutí

527
00:28:59,000 --> 00:29:04,000
a tiež zvyšovanie zložitosti z hľadiska kódu musíte napísať, aby si to pravé.

528
00:29:04,000 --> 00:29:08,000
To sú však všetky možno veľmi rozumné kompromisy, v prípade, že obrátenie je dôležitejšie.

529
00:29:08,000 --> 00:29:10,000
Jo.

530
00:29:10,000 --> 00:29:12,000
[Študent] tiež nemožno mať 2D prepojeného zoznamu.

531
00:29:12,000 --> 00:29:16,000
Dobré, nemôžete mať naozaj 2D spájať zoznam.

532
00:29:16,000 --> 00:29:18,000
Dalo by sa. Nie je to zďaleka tak jednoduché, ako pole.

533
00:29:18,000 --> 00:29:21,000
Rovnako ako maticu, robíte otvorený držiak, uzavretý držiak, otvorený držiak, uzavretý držiak,

534
00:29:21,000 --> 00:29:23,000
a máte nejaké 2-dimenzionální štruktúru.

535
00:29:23,000 --> 00:29:26,000
Dalo by sa vykonávať 2-rozmerný spájať zoznam

536
00:29:26,000 --> 00:29:29,000
ak si add-ako ste navrhoval-tretina ukazovateľ na každú z týchto vecí,

537
00:29:29,000 --> 00:29:34,000
a ak si myslíte, že o inom zozname, prichádza na vás 3D štýl

538
00:29:34,000 --> 00:29:40,000
z obrazovky nám všetkým, čo je len iný reťazec nejakého druhu.

539
00:29:40,000 --> 00:29:45,000
Mohli by sme to urobiť, ale nie je to tak jednoduché ako písanie otvorený držiak, hranatá zátvorka. Jo.

540
00:29:45,000 --> 00:29:48,000
[Nepočuteľné Študent otázka]

541
00:29:48,000 --> 00:29:50,000
Dobré, takže to je skutočný kicker.

542
00:29:50,000 --> 00:29:54,000
>> Tieto algoritmy, ktoré sme túžila po, rovnako ako oh, binárne vyhľadávanie,

543
00:29:54,000 --> 00:29:57,000
môžete vyhľadávať rad čísel na palube

544
00:29:57,000 --> 00:30:01,000
alebo telefónne kniha tak oveľa rýchlejšie, ak budete používať rozdeľ a panuj

545
00:30:01,000 --> 00:30:05,000
a binárne vyhľadávacie algoritmus, ale binárny vyhľadávací potrebné dva predpoklady.

546
00:30:05,000 --> 00:30:09,000
Jeden, že dáta boli zoradené.

547
00:30:09,000 --> 00:30:11,000
Teraz môžeme pravdepodobne si to zoradená,

548
00:30:11,000 --> 00:30:14,000
takže možno to nie je starosť, ale binárny vyhľadávací tiež predpokladá

549
00:30:14,000 --> 00:30:18,000
že ste mali náhodný prístup k zoznamu čísel,

550
00:30:18,000 --> 00:30:21,000
a pole vám umožní mať náhodný prístup, a náhodným prístupom,

551
00:30:21,000 --> 00:30:24,000
Chcem povedať, ak ste rovnako pole, koľko času zaberie vám

552
00:30:24,000 --> 00:30:26,000
dostať sa do držiaka 0?

553
00:30:26,000 --> 00:30:29,000
Jedna operácia, stačí použiť [0] a máš pravdu tam.

554
00:30:29,000 --> 00:30:33,000
Koľko krokov je potrebné, aby sa na miesto 10?

555
00:30:33,000 --> 00:30:36,000
Jeden krok, stačí ísť na [10], a ste tam.

556
00:30:36,000 --> 00:30:40,000
Naproti tomu, ako sa dostať na 10. integer v prepojenom zozname?

557
00:30:40,000 --> 00:30:42,000
Musíte začať od začiatku, pretože ste len spomínanie

558
00:30:42,000 --> 00:30:45,000
začiatok prepojeného zoznamu, rovnako ako reťazec je pamätal

559
00:30:45,000 --> 00:30:48,000
adresou jeho prvý znak, a zistiť, že 10. int

560
00:30:48,000 --> 00:30:53,000
alebo že 10. znak v reťazci, budete musieť hľadať celú tú stratenú vec.

561
00:30:53,000 --> 00:30:55,000
>> Opäť, nie sme riešenie všetkých našich problémov.

562
00:30:55,000 --> 00:31:00,000
Sme zavádzanie nových, ale je to naozaj záleží na tom, čo sa snažíte navrhnúť pre.

563
00:31:00,000 --> 00:31:04,000
Pokiaľ ide o vykonávanie, môžeme požičať nápad z tohto študentského štruktúry.

564
00:31:04,000 --> 00:31:07,000
Syntax je veľmi podobná, s výnimkou teraz, nápad je trochu abstraktná

565
00:31:07,000 --> 00:31:09,000
ako dom a meno a číslo.

566
00:31:09,000 --> 00:31:13,000
Ale ja navrhujem, že by sme mohli mať dátovú štruktúru v C

567
00:31:13,000 --> 00:31:17,000
, Ktorá sa nazýva uzol, ako posledné slovo na snímke naznačuje,

568
00:31:17,000 --> 00:31:21,000
vnútri uzla, a uzol je len všeobecný kontajner v informatike.

569
00:31:21,000 --> 00:31:25,000
Je to zvyčajne kreslený ako kruh alebo štvorec alebo obdĺžnik, ako sme kedy urobili.

570
00:31:25,000 --> 00:31:27,000
A v tejto dátovej štruktúre, máme int, n,

571
00:31:27,000 --> 00:31:29,000
tak to je číslo chcem uložiť.

572
00:31:29,000 --> 00:31:36,000
Ale čo je to druhý riadok, struct node * next?

573
00:31:36,000 --> 00:31:40,000
Prečo je to správne, alebo akú úlohu táto vec hra,

574
00:31:40,000 --> 00:31:42,000
aj keď je to trochu záhadný na prvý pohľad?

575
00:31:42,000 --> 00:31:44,000
Jo.

576
00:31:44,000 --> 00:31:46,000
[Nepočuteľné Študent odpoveď]

577
00:31:46,000 --> 00:31:50,000
Presne, takže * druh koristi, že je to ukazovateľ nejakého druhu.

578
00:31:50,000 --> 00:31:53,000
Názov tohto ukazovateľa je ľubovoľne ďalšie,

579
00:31:53,000 --> 00:32:00,000
ale mohli sme to nazval, čo chceme, ale to, čo robí tento ukazovateľ prejdite na?

580
00:32:00,000 --> 00:32:03,000
[Študent] Ďalšie uzol. >> Presne tak, to ukazuje na iné takéto uzla.

581
00:32:03,000 --> 00:32:05,000
>> Teraz, to je niečo ako zvedavosti C.

582
00:32:05,000 --> 00:32:09,000
Pripomeňme si, že C je čítať kompilátora zhora nadol, zľava doprava,

583
00:32:09,000 --> 00:32:13,000
čo znamená, že ak-je to trochu odlišné od toho, čo sme robili so študentom.

584
00:32:13,000 --> 00:32:16,000
Keď sme definovali študenta, sme vlastne nedal slovo tam.

585
00:32:16,000 --> 00:32:18,000
To práve povedal typedef.

586
00:32:18,000 --> 00:32:20,000
Potom sme mali int id, názov reťazca, reťazec dom,

587
00:32:20,000 --> 00:32:23,000
a potom sa študuje na spodnej časti struct.

588
00:32:23,000 --> 00:32:26,000
Toto vyhlásenie je trochu iný, pretože,

589
00:32:26,000 --> 00:32:28,000
znovu, C prekladač je trochu hlúpy.

590
00:32:28,000 --> 00:32:30,000
Je to len bude čítať zhora nadol,

591
00:32:30,000 --> 00:32:33,000
tak ak sa dosiahne 2. riadok tu

592
00:32:33,000 --> 00:32:37,000
kde je ďalší deklarovaný a vidí, oh, tu je premenná názvom ďalšie.

593
00:32:37,000 --> 00:32:39,000
Je to ukazovateľ na struct uzol.

594
00:32:39,000 --> 00:32:42,000
Kompilátor bude uvedomiť si, čo je struct uzol?

595
00:32:42,000 --> 00:32:44,000
Nikdy som nepočul o tejto veci skôr,

596
00:32:44,000 --> 00:32:47,000
pretože slovo uzol by inak objaviť

597
00:32:47,000 --> 00:32:49,000
až do dna, takže je táto nadbytočnosť.

598
00:32:49,000 --> 00:32:53,000
Musíš povedať struct uzol tu, ktoré potom môžete skrátiť neskôr

599
00:32:53,000 --> 00:32:56,000
vďaka typedef tu dole, ale to je preto, že

600
00:32:56,000 --> 00:33:02,000
my odkazujete štruktúru sám vnútri konštrukcie.

601
00:33:02,000 --> 00:33:05,000
To je ten mám ťa tam.

602
00:33:05,000 --> 00:33:07,000
>> Niektoré zaujímavé problémy budú vznikať.

603
00:33:07,000 --> 00:33:09,000
Máme zoznam čísel. Ako vložíme do nej?

604
00:33:09,000 --> 00:33:11,000
Ako sme hľadať to? Ako sme odstrániť z neho?

605
00:33:11,000 --> 00:33:13,000
Zvlášť teraz, že musíme zvládnuť všetky tieto ukazovatele.

606
00:33:13,000 --> 00:33:15,000
Myslel si si, že ukazovatele sú trochu myseľ-ohýbanie

607
00:33:15,000 --> 00:33:17,000
keď mal jeden z nich sa len snažím čítať int na neho.

608
00:33:17,000 --> 00:33:20,000
Teraz musíme manipulovať celý zoznam stojí za to.

609
00:33:20,000 --> 00:33:22,000
Prečo berieme 5 minút prestávku tu, a potom budeme prinášať

610
00:33:22,000 --> 00:33:34,000
niektorí ľudia až na javisku robiť presne to.

611
00:33:34,000 --> 00:33:36,000
>> C je oveľa zábavnejšie, keď je to predvádzal.

612
00:33:36,000 --> 00:33:39,000
Kto by doslova chcel byť prvý?

613
00:33:39,000 --> 00:33:41,000
Dobre, poď hore. Ste prvý.

614
00:33:41,000 --> 00:33:44,000
Kto by chcel byť 9? Dobre, 9.

615
00:33:44,000 --> 00:33:46,000
Ako asi 9? 17?

616
00:33:46,000 --> 00:33:51,000
Trochu kľučka tu. 22 a 26 v tomto prednej rade.

617
00:33:51,000 --> 00:33:53,000
A potom, ako na niekoho tam je zameraný.

618
00:33:53,000 --> 00:33:57,000
Ste 34. Dobre, 34, poď hore.

619
00:33:57,000 --> 00:33:59,000
Prvá z nich je tam. Dobre, všetci štyria z vás.

620
00:33:59,000 --> 00:34:01,000
A kto sme povedať 9?

621
00:34:01,000 --> 00:34:04,000
Kto je náš 9?

622
00:34:04,000 --> 00:34:07,000
Kto chce byť skutočne 9? Dobre, poď, byť 9.

623
00:34:07,000 --> 00:34:10,000
Ideme na to.

624
00:34:10,000 --> 00:34:13,000
34, stretneme sa tam.

625
00:34:13,000 --> 00:34:17,000
Prvá časť je, aby sami vyzerať takto.

626
00:34:17,000 --> 00:34:21,000
26, 22, 17, dobrý.

627
00:34:21,000 --> 00:34:25,000
Ak môžete stať stranou, pretože budeme malloc vás za chvíľu.

628
00:34:25,000 --> 00:34:29,000
>> Dobre, dobre.

629
00:34:29,000 --> 00:34:32,000
Dobre, vynikajúce, takže poďme položiť pár otázok tu.

630
00:34:32,000 --> 00:34:34,000
A vlastne, Ako sa voláte? >> Anita.

631
00:34:34,000 --> 00:34:37,000
Anita, v poriadku, poď sem.

632
00:34:37,000 --> 00:34:41,000
Anita je nám pomôže trochu vyriešiť jeden celkom jednoduchú otázku v prvej,

633
00:34:41,000 --> 00:34:44,000
ktoré je, ako si zistiť, či je alebo nie je hodnota je v zozname?

634
00:34:44,000 --> 00:34:48,000
Teraz si všimnite, že prvý, zastúpená tu Lucas,

635
00:34:48,000 --> 00:34:52,000
je trochu iný, a tak sa jeho kus papiera je zámerne stranou

636
00:34:52,000 --> 00:34:55,000
pretože to nie je zas až tak vysoká a nezaberá toľko bitov,

637
00:34:55,000 --> 00:34:58,000
aj keď technicky má rovnakú veľkosť papiera len otáčať.

638
00:34:58,000 --> 00:35:01,000
Ale je to trochu iný v tom, že je to iba 32 bitov pre ukazovateľ,

639
00:35:01,000 --> 00:35:05,000
a všetky tieto chlapci sú 64 bitov, z ktorých polovica je počet, z ktorých polovica je ukazovateľ.

640
00:35:05,000 --> 00:35:08,000
Ale ukazovateľ nie je zobrazený, takže ak ste mohol trochu rozpačito

641
00:35:08,000 --> 00:35:12,000
používať ľavú ruku k bodu na osobu vedľa vás.

642
00:35:12,000 --> 00:35:14,000
A ty si číslo 34. Ako sa voláte?

643
00:35:14,000 --> 00:35:16,000
Ari.

644
00:35:16,000 --> 00:35:19,000
Ari, tak vlastne, držte papier v pravej ruke, a ľavá ruka ide dole.

645
00:35:19,000 --> 00:35:21,000
Nachádzate predstavujú null vľavo.

646
00:35:21,000 --> 00:35:24,000
>> Teraz náš obraz človeka je veľmi konzistentné.

647
00:35:24,000 --> 00:35:26,000
To je vlastne, ako ukazovatele fungujú.

648
00:35:26,000 --> 00:35:29,000
A ak môžete zmotať trochu takhle, takže nie som v ceste.

649
00:35:29,000 --> 00:35:34,000
Anita tu, aby sme mi číslo 22,

650
00:35:34,000 --> 00:35:40,000
ale predpokladajú obmedzenia, ktoré nie je človek drží kúsky papiera,

651
00:35:40,000 --> 00:35:43,000
ale to je zoznam, a máte len Lucas začať

652
00:35:43,000 --> 00:35:46,000
pretože on je doslova prvý ukazovateľ.

653
00:35:46,000 --> 00:35:51,000
Predpokladajme, že vy sami ste ukazovateľ, a tak aj vy máte možnosť poukázať na niečo.

654
00:35:51,000 --> 00:35:56,000
Prečo si začať tým, že na to, čo Lucas mieri na?

655
00:35:56,000 --> 00:35:58,000
Dobrá, a dovoľte mi, aby som prijať toto sem.

656
00:35:58,000 --> 00:36:04,000
Len pre diskusie, dovoľte mi, aby som vytiahnuť prázdnu stránku tu.

657
00:36:04,000 --> 00:36:06,000
Ako sa píše vaše meno? >> Anita.

658
00:36:06,000 --> 00:36:08,000
Dobre, Anita.

659
00:36:08,000 --> 00:36:18,000
Povedzme, že uzol * Anita = Lucas.

660
00:36:18,000 --> 00:36:22,000
No, nemali by sme hovoriť lucas. Mali by sme hovoriť ako prvý.

661
00:36:22,000 --> 00:36:25,000
Prečo je tomu v skutočnosti je v súlade s realitou?

662
00:36:25,000 --> 00:36:27,000
Jeden, prvý už existuje.

663
00:36:27,000 --> 00:36:30,000
Prvé bolo pridelené pravdepodobne niekde tu.

664
00:36:30,000 --> 00:36:35,000
Uzol * prvý, a to bolo pridelené zoznam nejako.

665
00:36:35,000 --> 00:36:37,000
Neviem, ako sa to stalo. To sa stalo pred trieda začala.

666
00:36:37,000 --> 00:36:40,000
Tento spájať zoznam ľudí bola vytvorená.

667
00:36:40,000 --> 00:36:44,000
A teraz v tomto okamihu v príbehu-je to všetko deje na Facebooku zrejme neskôr,

668
00:36:44,000 --> 00:36:49,000
V tejto fáze príbehu, ktorý Anita bol inicializovaný musí rovnať prvej,

669
00:36:49,000 --> 00:36:51,000
čo neznamená, že body Anita na Lucasa.

670
00:36:51,000 --> 00:36:53,000
Skôr poukazuje na to, čo ukazuje na

671
00:36:53,000 --> 00:36:57,000
pretože rovnaká adresa, ktorá je vo vnútri 32 bitov Lucas je - 1, 2, 3 -

672
00:36:57,000 --> 00:37:01,000
Teraz je tiež v 32-bitovej Anita tieto - 1, 2, 3.

673
00:37:01,000 --> 00:37:05,000
>> Teraz nájsť 22. Ako by ste ísť asi robí?

674
00:37:05,000 --> 00:37:07,000
Čo je to? >> Point na čokoľvek.

675
00:37:07,000 --> 00:37:11,000
Prejdite na čokoľvek, tak choďte do toho a konať to, ako najlepšie môžete tu.

676
00:37:11,000 --> 00:37:15,000
Dobre, dobre, a teraz si ukázal na-to, čo je vaše meno s 22?

677
00:37:15,000 --> 00:37:18,000
Ramon. >> Ramon, takže Ramon sa drží 22.

678
00:37:18,000 --> 00:37:20,000
Teraz ste urobil kontrolu.

679
00:37:20,000 --> 00:37:24,000
Má Ramon == 22, a ak je to tak, napríklad, môžeme vrátiť pravda.

680
00:37:24,000 --> 00:37:26,000
Dovoľte mi, aby som pri-títo chalani tu stáť trochu nemotorne-

681
00:37:26,000 --> 00:37:32,000
dovoľte mi, aby som niečo rýchlo ako bool nájsť.

682
00:37:32,000 --> 00:37:37,000
Chystám sa ísť dopredu a povedať (uzol * list, int n).

683
00:37:37,000 --> 00:37:39,000
Budem hneď späť s vami. Len musím napísať nejaký kód.

684
00:37:39,000 --> 00:37:45,000
A teraz budem pokračovať a urobiť, uzol * Anita = zoznam.

685
00:37:45,000 --> 00:37:51,000
A ja idem ďalej a povedať, while (anita! = NULL).

686
00:37:51,000 --> 00:37:57,000
>> Metafora je tu stále trochu pretiahol, ale zároveň (anita! = NULL), čo chcem robiť?

687
00:37:57,000 --> 00:38:03,000
Potrebujem nejaký spôsob odkazovanie

688
00:38:03,000 --> 00:38:05,000
celé číslo, ktoré Anita ukazuje na.

689
00:38:05,000 --> 00:38:08,000
V minulosti, keď sme mali štruktúry, čo je uzol,

690
00:38:08,000 --> 00:38:11,000
sme použili bodkovaný notáciu, a povedali by sme niečo ako

691
00:38:11,000 --> 00:38:15,000
anita.n, ale problém je, že Anita nie je struct sebe.

692
00:38:15,000 --> 00:38:17,000
Čo je to?

693
00:38:17,000 --> 00:38:21,000
Je to ukazovateľ, takže naozaj, ak chceme použiť tento bodkovaný notácie,

694
00:38:21,000 --> 00:38:23,000
a to bude vyzerať zámerne trochu záhadný,

695
00:38:23,000 --> 00:38:28,000
musíme urobiť niečo ako ísť do ľavej ruky bez ohľadu na Anita je ukazuje na

696
00:38:28,000 --> 00:38:31,000
a potom sa pole s názvom n

697
00:38:31,000 --> 00:38:35,000
Anita je ukazovateľ, ale to, čo je * anita?

698
00:38:35,000 --> 00:38:38,000
Čo pre vás, keď idete na to, čo Anita mieri na?

699
00:38:38,000 --> 00:38:42,000
Struct, uzol, uzol, odvolanie, má pole s názvom n

700
00:38:42,000 --> 00:38:47,000
pretože, spomínam, táto 2 polia, ďalšie a n,

701
00:38:47,000 --> 00:38:50,000
že sme videli pred chvíľou tu.

702
00:38:50,000 --> 00:38:53,000
>> Ak chcete skutočne napodobniť to v kóde,

703
00:38:53,000 --> 00:39:02,000
by sme mohli urobiť to a povedať if ((* anita). n == n), n, že som hľadal.

704
00:39:02,000 --> 00:39:04,000
Všimnite si, že funkcia bola odovzdaná v počte Aj záleží.

705
00:39:04,000 --> 00:39:10,000
Potom môžem ísť ďalej a robiť niečo ako návrat skutočný.

706
00:39:10,000 --> 00:39:12,000
Else, ak to nie je tento prípad, čo chcem robiť?

707
00:39:12,000 --> 00:39:19,000
Ako môžem preložiť do kódu, čo Anita robil tak intuitívne prechádzky v zozname?

708
00:39:19,000 --> 00:39:26,000
Čo mám robiť, až tu simulovať Anita aby takýto krok doľava, tento krok doľava?

709
00:39:26,000 --> 00:39:28,000
[Nepočuteľné Študent odpoveď] >> Čo je to?

710
00:39:28,000 --> 00:39:30,000
[Nepočuteľné Študent odpoveď]

711
00:39:30,000 --> 00:39:34,000
Dobré, nie je zlý nápad, ale v minulosti, kedy sme urobili to, čo sme urobili anita + +

712
00:39:34,000 --> 00:39:37,000
pretože to by pridať číslo 1 Anita,

713
00:39:37,000 --> 00:39:40,000
ktoré by obvykle poukazujú na ďalšie osoby, ako Ramon,

714
00:39:40,000 --> 00:39:44,000
alebo osoba vedľa neho, alebo vedľa neho človek po línii.

715
00:39:44,000 --> 00:39:49,000
Ale to nie je tak celkom sa tu dobre, pretože to, čo to, čo vyzerá v pamäti?

716
00:39:49,000 --> 00:39:54,000
Nie, že. Musíme zakázať to.

717
00:39:54,000 --> 00:40:00,000
Vyzerá to, že to v pamäti, a to aj keď som vypracované 1 a 2 a 3 blízko seba,

718
00:40:00,000 --> 00:40:03,000
ak chceme skutočne simulovať, môžete chlapci, zatiaľ čo ešte ukázal na rovnakými ľuďmi,

719
00:40:03,000 --> 00:40:07,000
môžu niektorí z vás sa náhodný krok späť, niektorí z vás náhodná krok vpred?

720
00:40:07,000 --> 00:40:10,000
>> Tento neporiadok je stále prepojený zoznam,

721
00:40:10,000 --> 00:40:13,000
ale títo chlapci môže byť kdekoľvek v pamäti,

722
00:40:13,000 --> 00:40:15,000
tak anita + + nebude fungovať prečo?

723
00:40:15,000 --> 00:40:19,000
Čo je v mieste Anita + +?

724
00:40:19,000 --> 00:40:21,000
Kto vie.

725
00:40:21,000 --> 00:40:24,000
Je to nejaká iná hodnota, ktorá len tak náhodou sa prerušil

726
00:40:24,000 --> 00:40:28,000
medzi všetkými týmito uzlami náhodou, pretože sme nepoužívate poľa.

727
00:40:28,000 --> 00:40:30,000
My pridelené každej z týchto uzlov jednotlivo.

728
00:40:30,000 --> 00:40:32,000
Dobre, ak vy môžete vyčistiť sami zálohovať.

729
00:40:32,000 --> 00:40:37,000
Dovoľte mi, aby som navrhla, že namiesto toho, aby anita + +, sme namiesto toho Anita začne-

730
00:40:37,000 --> 00:40:42,000
dobre, prečo nejdeme na čokoľvek Anita ukazuje na a potom vykonajte. ďalej?

731
00:40:42,000 --> 00:40:45,000
Inými slovami, sme šli do Ramon, ktorý je drží číslo 22,

732
00:40:45,000 --> 00:40:51,000
a potom. ďalšie, ako by Anita by byť kopírovanie jeho ľavý ukazovateľ.

733
00:40:51,000 --> 00:40:54,000
Ale nechcel ísť ďalej, než Ramon, pretože sme našli 22.

734
00:40:54,000 --> 00:40:56,000
Ale to by bolo nápad. Teraz, to je strašný neporiadok.

735
00:40:56,000 --> 00:40:59,000
Úprimne povedané, nikto nikdy zapamätať si túto syntax, a tak našťastie,

736
00:40:59,000 --> 00:41:04,000
je to vlastne trochu úmyselné-oh, ty si skutočne vidieť, čo som napísal.

737
00:41:04,000 --> 00:41:08,000
To by bolo presvedčivejšie, keby ste mohol. Voila!

738
00:41:08,000 --> 00:41:10,000
>> V zákulisí, bol som riešenie problému týmto spôsobom.

739
00:41:10,000 --> 00:41:14,000
Anita, aby tento krok doľava,

740
00:41:14,000 --> 00:41:18,000
Najskôr sme sa ísť na adresu, ktorú Anita ukazuje na

741
00:41:18,000 --> 00:41:23,000
a kde nájdete nielen n, čo sme práve čítal z dôvodu porovnanie,

742
00:41:23,000 --> 00:41:25,000
ale tiež nájdete ďalšie - v tomto prípade,

743
00:41:25,000 --> 00:41:28,000
Ramon ľavá ruka ukazuje na ďalší uzol v zozname.

744
00:41:28,000 --> 00:41:32,000
Ale to je strašný neporiadok, ktorý som spomínal skôr,

745
00:41:32,000 --> 00:41:34,000
ale to dopadá C nám umožňuje zjednodušiť tým.

746
00:41:34,000 --> 00:41:40,000
Miesto písania (* anita), môžeme namiesto toho len napísať Anita-> n,

747
00:41:40,000 --> 00:41:45,000
a je to presne to isté funkčne, ale je to oveľa viac intuitívne,

748
00:41:45,000 --> 00:41:48,000
a je to oveľa viac v súlade s obrázkom, ktorý sme už kreslíš

749
00:41:48,000 --> 00:41:50,000
celú tú dobu pomocou šípok.

750
00:41:50,000 --> 00:41:57,000
>> Napokon, čo musíme urobiť, na konci tohto programu?

751
00:41:57,000 --> 00:42:00,000
Je tu jeden riadok kódu zostávajúce.

752
00:42:00,000 --> 00:42:02,000
Návrat čo?

753
00:42:02,000 --> 00:42:05,000
False, pretože ak dostaneme cez celú while

754
00:42:05,000 --> 00:42:10,000
a Anita je, v skutočnosti, nulový, to znamená, že išiel celá cesta na koniec zoznamu

755
00:42:10,000 --> 00:42:12,000
kde ukazoval na-aké je vaše meno?

756
00:42:12,000 --> 00:42:15,000
Ari. >> Ariho ľavá ruka, ktorá je null.

757
00:42:15,000 --> 00:42:18,000
Anita je teraz null, a Uvedomujem si, že ste práve stojím nešikovne v limbu

758
00:42:18,000 --> 00:42:21,000
pretože budem preč na monológu tu,

759
00:42:21,000 --> 00:42:23,000
ale budeme zapojiť sa znovu za chvíľu.

760
00:42:23,000 --> 00:42:27,000
Anita je null v tomto bode v príbehu, takže zatiaľ čo slučka končí,

761
00:42:27,000 --> 00:42:30,000
a musíme vrátiť false, pretože keby dostala až k nulovej ukazovateľ Ariho

762
00:42:30,000 --> 00:42:34,000
potom tam bol žiadne číslo, ktoré ona hľadala v zozname.

763
00:42:34,000 --> 00:42:39,000
Môžeme vyčistiť to až príliš, ale to je celkom dobrý vykonávanie potom

764
00:42:39,000 --> 00:42:43,000
z funkcie traversal, nájsť funkciu prepojeného zoznamu.

765
00:42:43,000 --> 00:42:48,000
Je to stále lineárne vyhľadávanie, ale nie je to tak jednoduché, ako + + ukazovateľ

766
00:42:48,000 --> 00:42:52,000
alebo + + premenná i, pretože teraz nemôžeme odhadnúť

767
00:42:52,000 --> 00:42:54,000
, Kde každý z týchto uzlov sú v pamäti.

768
00:42:54,000 --> 00:42:57,000
Musíme doslova sledovať stopu strúhanky, alebo viac špecificky,

769
00:42:57,000 --> 00:43:00,000
ukazovatele, ako získať z jedného uzla do druhého.

770
00:43:00,000 --> 00:43:02,000
>> Teraz sa poďme skúsiť iný. Anita, chceš vrátiť sa sem?

771
00:43:02,000 --> 00:43:06,000
Prečo by sme pokračovať a prideliť jednu ďalšiu osobu z publika?

772
00:43:06,000 --> 00:43:08,000
Malloc-Ako sa voláte? >> Rebecca.

773
00:43:08,000 --> 00:43:10,000
Rebecca. Rebecca bola malloced z publika,

774
00:43:10,000 --> 00:43:13,000
a ona je teraz uloženie čísla 55.

775
00:43:13,000 --> 00:43:17,000
A cieľ na dosah ruky je teraz pre Anita vložiť

776
00:43:17,000 --> 00:43:22,000
Rebecca do prepojeného zoznamu tu v správne miesto.

777
00:43:22,000 --> 00:43:24,000
Poď sem na chvíľu.

778
00:43:24,000 --> 00:43:28,000
Urobil som niečo také.

779
00:43:28,000 --> 00:43:32,000
Urobil som uzla *. A čo že sa to voláš?

780
00:43:32,000 --> 00:43:34,000
Rebecca. >> Rebecca, v poriadku.

781
00:43:34,000 --> 00:43:41,000
Rebecca sa dostane malloc (sizeof (uzol)).

782
00:43:41,000 --> 00:43:44,000
Rovnako ako sme pridelené veci ako študentov a ktovie čo ešte v minulosti,

783
00:43:44,000 --> 00:43:46,000
potrebujeme veľkosť uzla, tak sa Rebecca

784
00:43:46,000 --> 00:43:49,000
ukazuje na to, čo?

785
00:43:49,000 --> 00:43:52,000
Rebecca má dve polia vo vnútri nej, z ktorých jeden je 55.

786
00:43:52,000 --> 00:43:55,000
Poďme urobiť to, čo, rebecca-> = 55.

787
00:43:55,000 --> 00:44:00,000
Ale potom rebecca-> next by mal byť-teraz páči, jej ruka je tak trochu kto vie?

788
00:44:00,000 --> 00:44:03,000
Je to ukazuje na určité uvoľnenie hodnote, tak prečo nie pre správnu mieru

789
00:44:03,000 --> 00:44:07,000
by sme aspoň to tak, že ľavá ruka je teraz na jej strane.

790
00:44:07,000 --> 00:44:09,000
Teraz Anita, vezmite si ju odtiaľ.

791
00:44:09,000 --> 00:44:11,000
Máte Rebecca ktoré boli pôvodne pridelené.

792
00:44:11,000 --> 00:44:20,000
Nehanbite sa a nájsť miesto, kde by sme mali dať Rebeccu.

793
00:44:20,000 --> 00:44:25,000
Dobré, veľmi dobré.

794
00:44:25,000 --> 00:44:28,000
Dobre, dobre, a teraz musíme si zaistiť trochu smer,

795
00:44:28,000 --> 00:44:30,000
tak ste dosiahli Ari.

796
00:44:30,000 --> 00:44:33,000
Jeho ľavá ruka je null, ale Rebecca jednoznačne patrí doprava,

797
00:44:33,000 --> 00:44:36,000
tak ako sa máme zmeniť tento spájať zoznam

798
00:44:36,000 --> 00:44:38,000
aby vložiť Rebeccu na príslušné miesto?

799
00:44:38,000 --> 00:44:42,000
Ak by ste mohli doslova pohybovať doľava ľudí okolo seba rukami, podľa potreby,

800
00:44:42,000 --> 00:44:48,000
budeme problém vyriešiť týmto spôsobom.

801
00:44:48,000 --> 00:44:52,000
Dobre, dobre, a medzitým, Rebecca ľavá ruka je teraz po jej boku.

802
00:44:52,000 --> 00:44:54,000
>> To bolo príliš jednoduché.

803
00:44:54,000 --> 00:44:57,000
Skúsme pridelenie-Sme takmer hotoví, 20.

804
00:44:57,000 --> 00:44:59,000
Dobre, poď hore.

805
00:44:59,000 --> 00:45:04,000
20 bolo pridelené, tak nechajte ma ísť napred a povedal opäť tu

806
00:45:04,000 --> 00:45:07,000
sme práve urobili uzol * Saad.

807
00:45:07,000 --> 00:45:11,000
Máme malloc (sizeof (uzol)).

808
00:45:11,000 --> 00:45:16,000
Potom sme urobiť rovnakú presnú syntax, ako sme to urobili pred pre 20,

809
00:45:16,000 --> 00:45:20,000
a ja budem robiť budúci = NULL, a teraz je to na Anita

810
00:45:20,000 --> 00:45:23,000
vložiť si do prepojeného zoznamu, ak si mohol hrať, že presne rovnakú úlohu.

811
00:45:23,000 --> 00:45:30,000
Execute.

812
00:45:30,000 --> 00:45:32,000
Dobre, dobre.

813
00:45:32,000 --> 00:45:38,000
Teraz si pozorne skôr, ako začnete pohybu ľavej ruky okolo.

814
00:45:38,000 --> 00:45:46,000
Tie zďaleka dostal najviac nepríjemnú úlohu dnes.

815
00:45:46,000 --> 00:45:59,000
Čí ruka by mala byť presunutá ako prvý?

816
00:45:59,000 --> 00:46:02,000
Dobre, počkaj, ja počujem niektoré nie je.

817
00:46:02,000 --> 00:46:07,000
Ak niektorí ľudia by zdvorilo rád pomohol vyriešiť nepríjemnú situáciu.

818
00:46:07,000 --> 00:46:11,000
Čí ľavá ruka by mala byť aktualizovaná prvého snáď? Jo.

819
00:46:11,000 --> 00:46:13,000
[Študent] Saad je.

820
00:46:13,000 --> 00:46:15,000
Dobre, Saad je, prečo, aj keď?

821
00:46:15,000 --> 00:46:17,000
[Nepočuteľné Študent odpoveď]

822
00:46:17,000 --> 00:46:19,000
Dobré, pretože ak my sa pohybujeme-Ako sa voláte? >> Marshall.

823
00:46:19,000 --> 00:46:22,000
Marshall, ak my sa pohybujeme ruku prvý down na hodnotu null,

824
00:46:22,000 --> 00:46:25,000
Teraz sme doslova osamotené štyroch ľudí v tomto zozname

825
00:46:25,000 --> 00:46:29,000
pretože on bol jediná vec, ukazuje na Ramon a všetci na ľavici,

826
00:46:29,000 --> 00:46:31,000
takže aktualizácia tento ukazovateľ Prvý bol zlý.

827
00:46:31,000 --> 00:46:33,000
Poďme späť, že.

828
00:46:33,000 --> 00:46:37,000
Dobrá, a teraz choďte do toho a presuňte príslušnú ľavú ruku ukazuje na Ramon.

829
00:46:37,000 --> 00:46:39,000
To cíti trochu nadbytočný.

830
00:46:39,000 --> 00:46:41,000
Teraz je tu dvaja ľudia ukazuje na Ramon, ale to je v poriadku

831
00:46:41,000 --> 00:46:43,000
pretože teraz, ako inak máme aktualizovať zoznam?

832
00:46:43,000 --> 00:46:48,000
Čo na druhej strane sa musí pohybovať?

833
00:46:48,000 --> 00:46:53,000
Skvelé, teraz máme stratila pamäť?

834
00:46:53,000 --> 00:46:57,000
Nie, tak dobre, uvidíme, či nemôžeme ti to ešte raz.

835
00:46:57,000 --> 00:47:00,000
>> Mallocing jeden posledný čas, číslo 5.

836
00:47:00,000 --> 00:47:04,000
Celú cestu v chrbte, poď dole.

837
00:47:04,000 --> 00:47:08,000
Je to veľmi vzrušujúce.

838
00:47:08,000 --> 00:47:15,000
[Potlesk]

839
00:47:15,000 --> 00:47:17,000
Ako sa voláte? >> Ron.

840
00:47:17,000 --> 00:47:19,000
Ron, v poriadku, ste malloced ako číslo 5.

841
00:47:19,000 --> 00:47:23,000
Práve sme vykonaný kód, ktorý je takmer totožný s týchto

842
00:47:23,000 --> 00:47:26,000
len s iným názvom.

843
00:47:26,000 --> 00:47:28,000
Výborný.

844
00:47:28,000 --> 00:47:38,000
Teraz, Anita, veľa šťastia vkladanie číslo 5 do zoznamu teraz.

845
00:47:38,000 --> 00:47:43,000
Dobrá, a?

846
00:47:43,000 --> 00:47:47,000
Skvelé, takže to je naozaj tretia z troch celkového počtu prípadov.

847
00:47:47,000 --> 00:47:49,000
Najprv sme mali niekoho na konci, Rebecca.

848
00:47:49,000 --> 00:47:51,000
Potom sme mali niekoho v stredu.

849
00:47:51,000 --> 00:47:53,000
Teraz máme niekoho na začiatku, a v tomto príklade,

850
00:47:53,000 --> 00:47:56,000
Teraz sme mali aktualizovať Lucas prvýkrát

851
00:47:56,000 --> 00:48:00,000
pretože prvý prvok zoznamu má teraz poukazujú na nový uzol,

852
00:48:00,000 --> 00:48:03,000
kto, podľa poradia, ukazuje na číslo uzla 9.

853
00:48:03,000 --> 00:48:06,000
>> To bolo veľmi trápne demonštrácie, som si istý,

854
00:48:06,000 --> 00:48:08,000
tak veľký potlesk pre týchto ľudí, ak by ste mohli.

855
00:48:08,000 --> 00:48:11,000
Skvele.

856
00:48:11,000 --> 00:48:17,000
To je všetko. Môžeš si nechať svoje kúsky papiera ako malý pamäte.

857
00:48:17,000 --> 00:48:22,000
Ukazuje sa, že robí v kóde

858
00:48:22,000 --> 00:48:26,000
nie je tak jednoduché, ako len pohybujúce sa okolo seba rukami,

859
00:48:26,000 --> 00:48:28,000
a ukázal ukazovatele na rôznych veciach.

860
00:48:28,000 --> 00:48:31,000
Ale uvedomte si, že keď príde čas na vykonanie niečo ako

861
00:48:31,000 --> 00:48:34,000
spájať zoznam alebo variant to, ak sa zameriate na naozaj

862
00:48:34,000 --> 00:48:38,000
tieto základné základy, na bite-size problémov, ktoré som sa prísť na to,,

863
00:48:38,000 --> 00:48:43,000
je to to ručne alebo to ruka, si uvedomiť, že to, čo je inak pomerne komplexný program

864
00:48:43,000 --> 00:48:47,000
môže byť v skutočnosti znížená na pomerne jednoduchých stavebných blokov, ako je tento.

865
00:48:47,000 --> 00:48:51,000
>> Poďme sa veci vo viac sofistikované smere stále.

866
00:48:51,000 --> 00:48:53,000
Teraz máme predstavu prepojeného zoznamu.

867
00:48:53,000 --> 00:48:57,000
Máme tiež-vďaka návrh späť tam, dvojnásobne spojené zoznam,

868
00:48:57,000 --> 00:49:01,000
ktorý vyzerá takmer rovnako, ale teraz máme dva ukazovatele vnútri struct

869
00:49:01,000 --> 00:49:05,000
miesto jedného, ​​a by sme pravdepodobne mohli zavolať tie ukazovatele predchádzajúce a nasledujúce

870
00:49:05,000 --> 00:49:08,000
doprava alebo doľava, ale my, v skutočnosti, je treba dva z nich.

871
00:49:08,000 --> 00:49:10,000
Tento kód by byť trochu viac zapojiť.

872
00:49:10,000 --> 00:49:12,000
Anita by musel robiť viac práce tu na javisku.

873
00:49:12,000 --> 00:49:15,000
Ale my sme mohli určite realizovať tento druh konštrukcie.

874
00:49:15,000 --> 00:49:19,000
Z hľadiska prevádzkového času, aj keď, čo by byť doba chodu

875
00:49:19,000 --> 00:49:24,000
pre Anita nájdenie číslo N v prepojenom zozname teraz?

876
00:49:24,000 --> 00:49:27,000
Stále veľký O n, takže je to o nič lepšie ako lineárne vyhľadávanie.

877
00:49:27,000 --> 00:49:29,000
Nemôžeme urobiť binárne vyhľadávanie, aj keď, znovu.

878
00:49:29,000 --> 00:49:34,000
Prečo tomu tak bolo v prípade? Nemôžete skákať okolo.

879
00:49:34,000 --> 00:49:36,000
Aj keď sme samozrejme vidieť všetkých tých ľudí na javisku,

880
00:49:36,000 --> 00:49:39,000
a Anita mohol eyeballed ho a povedal: "Tu je stred zoznamu,"

881
00:49:39,000 --> 00:49:42,000
by nevedela, že keby to bola ona, počítačový program

882
00:49:42,000 --> 00:49:47,000
pretože jediné, čo sa musela západky na na začiatku scenára

883
00:49:47,000 --> 00:49:50,000
bol Lucas, ktorý bol ako prvý ukazovateľ.

884
00:49:50,000 --> 00:49:53,000
Ona by nutne musel nasledovať tieto odkazy,

885
00:49:53,000 --> 00:49:56,000
počítanie si cestu až našla zhruba uprostred,

886
00:49:56,000 --> 00:49:58,000
a dokonca aj vtedy, keď to nebude vedieť, kedy je ona dostal do stredu

887
00:49:58,000 --> 00:50:01,000
pokiaľ ona ide celú cestu až do konca zistiť, koľko ich je,

888
00:50:01,000 --> 00:50:05,000
potom ustúpi, a to aj bude ťažké, ak ste mali

889
00:50:05,000 --> 00:50:07,000
dvojnásobne spájať zoznam nejakého druhu.

890
00:50:07,000 --> 00:50:10,000
>> Riešenie niektorých problémov dnes, ale zavedenie ostatné.

891
00:50:10,000 --> 00:50:12,000
Čo inú dátovú štruktúru dohromady?

892
00:50:12,000 --> 00:50:15,000
Toto je fotografia zo zásobníkov v Mather dom,

893
00:50:15,000 --> 00:50:19,000
a v tomto prípade, máme štruktúru dát sme tiež trochu už hovorí.

894
00:50:19,000 --> 00:50:22,000
Hovorili sme o zásobníka v súvislosti s pamäťou,

895
00:50:22,000 --> 00:50:26,000
a to je druh zámerne pomenovaný pretože stack v podmienkach pamäti

896
00:50:26,000 --> 00:50:31,000
je účinne dátová štruktúra, ktorá má viac a viac vecí navrstvené na neho.

897
00:50:31,000 --> 00:50:35,000
Ale zaujímavé na tom hromadu, ako je tomu v skutočnosti,

898
00:50:35,000 --> 00:50:38,000
je to, že je to zvláštny druh dátové štruktúry.

899
00:50:38,000 --> 00:50:42,000
Je to dátová štruktúra, kedy prvý prvok v

900
00:50:42,000 --> 00:50:46,000
je posledný prvok von.

901
00:50:46,000 --> 00:50:50,000
Ak ste prvý zásobník na uvedenie do fronty,

902
00:50:50,000 --> 00:50:53,000
budete mať bohužiaľ posledný zásobník ktoré majú byť prijaté mimo zásobník,

903
00:50:53,000 --> 00:50:55,000
a to nie je nevyhnutne dobrá vec.

904
00:50:55,000 --> 00:50:58,000
Naopak, môžete premýšľať o tom opačne,

905
00:50:58,000 --> 00:51:02,000
posledný v je prvý von.

906
00:51:02,000 --> 00:51:05,000
>> Teraz, sa všetky scenáre príde na myseľ, kde majú hromadu

907
00:51:05,000 --> 00:51:08,000
dátová štruktúra, kde budete mať túto vlastnosť

908
00:51:08,000 --> 00:51:13,000
z poslednej dovnútra, prvý von, je vlastne presvedčivé?

909
00:51:13,000 --> 00:51:16,000
Je to dobrá vec? Je to zlá vec?

910
00:51:16,000 --> 00:51:19,000
Je to určite zlá vec, ak zásobníky neboli všetky rovnaké

911
00:51:19,000 --> 00:51:21,000
a oni boli všetci mimoriadne rôzne farby alebo ktovie čo ešte,

912
00:51:21,000 --> 00:51:24,000
a farbu, ktorú chcete, je úplne na dne.

913
00:51:24,000 --> 00:51:26,000
Samozrejme, môžete sa dostať, že bez veľkej námahy.

914
00:51:26,000 --> 00:51:28,000
Musíte začať od vrcholu a prácu si cestu dole.

915
00:51:28,000 --> 00:51:31,000
Podobne, čo keď ste bol jedným z týchto ventilátorov chlapcov

916
00:51:31,000 --> 00:51:34,000
ktorý čaká celú noc snaží dostať iPhone a zoradia

917
00:51:34,000 --> 00:51:36,000
na mieste ako je toto?

918
00:51:36,000 --> 00:51:40,000
Nebolo by pekné, keby v obchode Apple

919
00:51:40,000 --> 00:51:42,000
boli stack štruktúra dát?

920
00:51:42,000 --> 00:51:44,000
Yay? Nay?

921
00:51:44,000 --> 00:51:47,000
Je to len dobre pre ľudí, ktorí sa ukážu na poslednú chvíľu

922
00:51:47,000 --> 00:51:50,000
a potom si trhal frontu.

923
00:51:50,000 --> 00:51:52,000
A v skutočnosti, že som bol tak naklonený povedať fronty

924
00:51:52,000 --> 00:51:56,000
je vlastne v súlade s tým, čo by sme mohli nazvať tento druh dátové štruktúry,

925
00:51:56,000 --> 00:51:59,000
jeden v realite, kde poradí záleží,

926
00:51:59,000 --> 00:52:02,000
a chcete prvý v byť prvý z

927
00:52:02,000 --> 00:52:04,000
ak len kvôli ľudskej spravodlivosti.

928
00:52:04,000 --> 00:52:07,000
Budeme obvykle vyžadujú, aby fronta dátová štruktúra.

929
00:52:07,000 --> 00:52:11,000
>> Ukázalo sa, že okrem prepojených zoznamov, môžeme začať používať tieto rovnaké základné myšlienky

930
00:52:11,000 --> 00:52:15,000
a začať vytvárať nové a odlišné typy riešení problémov.

931
00:52:15,000 --> 00:52:19,000
Napríklad, v prípade, že v zásobníku, môžeme predstavovať zásobník

932
00:52:19,000 --> 00:52:22,000
pomocou dátovej štruktúry, ako je tento, by navrhujem.

933
00:52:22,000 --> 00:52:26,000
V tomto prípade, som vyhlásil struct, a ja som povedal, vo vnútri tejto štruktúry

934
00:52:26,000 --> 00:52:30,000
je rad čísel a potom premenná nazýva veľkosť,

935
00:52:30,000 --> 00:52:33,000
a budem nazývať túto vec stack.

936
00:52:33,000 --> 00:52:35,000
A teraz, prečo to vlastne funguje?

937
00:52:35,000 --> 00:52:43,000
V prípade zásobníka, mohol som čerpať túto efektívne na obrazovke ako pole.

938
00:52:43,000 --> 00:52:47,000
Tu je môj stack. To sú moje čísla.

939
00:52:47,000 --> 00:52:50,000
A budeme kresliť ako toto, toto, toto, toto, toto.

940
00:52:50,000 --> 00:52:53,000
A potom som mať nejaký iný dátový člen tu,

941
00:52:53,000 --> 00:52:58,000
ktorá sa nazýva veľkosť, takže je veľkosť, a to je číslo,

942
00:52:58,000 --> 00:53:02,000
a kolektívne, celá iPad tu predstavuje jednu zásobníka štruktúru.

943
00:53:02,000 --> 00:53:07,000
Teraz, v predvolenom nastavení, veľkosť sa pravdepodobne dostala byť inicializovaná na 0,

944
00:53:07,000 --> 00:53:11,000
a to, čo je vo vnútri poľa čísel spočiatku

945
00:53:11,000 --> 00:53:14,000
keď som prvýkrát prideliť poľa?

946
00:53:14,000 --> 00:53:16,000
Garbage. Kto vie? A to nie je v skutočnosti nezáleží.

947
00:53:16,000 --> 00:53:20,000
Nezáleží na tom, v prípade, že je 1, 2, 3, 4, 5, úplne náhodne

948
00:53:20,000 --> 00:53:25,000
smola uložené v mojom štruktúre, pretože tak dlho, ako viem, že veľkosť zásobníku

949
00:53:25,000 --> 00:53:29,000
je 0, potom viem, že programovo, nepozerajte sa na niektorý z prvkov v poli.

950
00:53:29,000 --> 00:53:31,000
Nezáleží na tom, čo tam je.

951
00:53:31,000 --> 00:53:34,000
Nepozerajte sa na ne, ako by dôsledky pre veľkosti 0.

952
00:53:34,000 --> 00:53:38,000
>> Predpokladajme však, že teraz som do toho pustite a vložte niečo do zásobníka.

953
00:53:38,000 --> 00:53:42,000
Chcem vložiť číslo 5, a tak som dal číslo 5 tu,

954
00:53:42,000 --> 00:53:45,000
a potom čo som dal sem dole?

955
00:53:45,000 --> 00:53:48,000
Teraz by som vlastne dal dole 1 pre veľkosť,

956
00:53:48,000 --> 00:53:50,000
a teraz je zásobník veľkosti 1.

957
00:53:50,000 --> 00:53:53,000
Čo keď som do toho pustite a vložte číslo, povedzme, 7 ďalší?

958
00:53:53,000 --> 00:53:57,000
To potom dostane aktualizovaný na 2, a potom budeme robiť 9,

959
00:53:57,000 --> 00:54:02,000
a potom to dostane aktualizovaný na 3.

960
00:54:02,000 --> 00:54:05,000
Ale zaujímavý rys teraz tohto zásobníka je, že

961
00:54:05,000 --> 00:54:09,000
Mám na odstránenie, ktorý prvok, keď chcem, aby pop

962
00:54:09,000 --> 00:54:12,000
niečo z frontu, tak hovoriť?

963
00:54:12,000 --> 00:54:14,000
9 bude prvá vec, ktorú ísť.

964
00:54:14,000 --> 00:54:18,000
Ako by mala obraz zmeniť, ak chcem pop prvok zo zásobníka,

965
00:54:18,000 --> 00:54:20,000
veľa ako zásobník v Mather?

966
00:54:20,000 --> 00:54:22,000
Jo. >> [Študent] Nastavte veľkosť na 2.

967
00:54:22,000 --> 00:54:27,000
Presne tak, je všetko, čo som urobiť, nastaviť veľkosť 2, a čo mám robiť s poli?

968
00:54:27,000 --> 00:54:29,000
Nemám nič robiť.

969
00:54:29,000 --> 00:54:32,000
Mohol by som, len aby bol anal, dať tam 0 alebo -1, alebo niečo znamenať

970
00:54:32,000 --> 00:54:34,000
, Že sa nejedná dôveryhodne hodnota, ale to nevadí, pretože

971
00:54:34,000 --> 00:54:37,000
Aj možno zaznamenať mimo ARR ako dlho je

972
00:54:37,000 --> 00:54:41,000
takže viem, len sa pozrieť na prvé dva prvky v tomto poli.

973
00:54:41,000 --> 00:54:47,000
Teraz, keď odídem a pridať číslo 8 na toto pole, ako sa obraz zmeniť budúci?

974
00:54:47,000 --> 00:54:50,000
To sa stáva 8, a to sa stáva 3.

975
00:54:50,000 --> 00:54:52,000
Ja rezanie pár rohov tu.

976
00:54:52,000 --> 00:54:56,000
Teraz máme 5, 7, 8, a sme späť do veľkosti 3.

977
00:54:56,000 --> 00:54:58,000
To je celkom jednoduché realizovať,

978
00:54:58,000 --> 00:55:06,000
ale keď sa budeme ľutovať tohto návrhu rozhodnutia?

979
00:55:06,000 --> 00:55:09,000
Keď sa veci začnú ísť veľmi, veľmi zle? Jo.

980
00:55:09,000 --> 00:55:11,000
[Nepočuteľné Študent odpoveď]

981
00:55:11,000 --> 00:55:13,000
Ak chcete vrátiť späť a získať prvý prvok vložíte dovnútra

982
00:55:13,000 --> 00:55:18,000
>> Ukázalo sa, že tu, aj keď je stoh poľa pod kapotou,

983
00:55:18,000 --> 00:55:21,000
Tieto dátové štruktúry sme začali hovoriť o sú tiež všeobecne známe ako

984
00:55:21,000 --> 00:55:25,000
abstraktné dátové štruktúry, kedy, ako už implementované

985
00:55:25,000 --> 00:55:27,000
je úplne okrem bodu.

986
00:55:27,000 --> 00:55:31,000
Dátová štruktúra ako hromada má pridať podporu

987
00:55:31,000 --> 00:55:35,000
operácie, ako Push, ktorá tlačí zásobník na zásobníku,

988
00:55:35,000 --> 00:55:39,000
a pop, ktorý odstráni prvok zo zásobníka, a to je všetko.

989
00:55:39,000 --> 00:55:43,000
Ak by ste mali stiahnuť niekto iný kód, ktorý už zavedených

990
00:55:43,000 --> 00:55:46,000
to, čomu sa hovorí hromadu, by táto osoba písali

991
00:55:46,000 --> 00:55:49,000
iba dve funkcie pre vás, tlačiť a pop, ktorého jediným zmyslom života

992
00:55:49,000 --> 00:55:51,000
by bolo robiť presne to.

993
00:55:51,000 --> 00:55:54,000
Vy alebo on alebo ona, kto ju vykonáva tento program

994
00:55:54,000 --> 00:55:58,000
by boli úplne ten, kto rozhodne, ako implementovať

995
00:55:58,000 --> 00:56:00,000
sémantika tlačí a praskanie pod pokrievku

996
00:56:00,000 --> 00:56:03,000
alebo funkčnosť tlačenie a praskanie.

997
00:56:03,000 --> 00:56:07,000
A ja som urobil niečo krátkozrakú rozhodnutie tu

998
00:56:07,000 --> 00:56:10,000
vykonávacie môj stack s týmto jednoduchým dátové štruktúry prečo?

999
00:56:10,000 --> 00:56:12,000
Kedy Táto dátová štruktúra prestávku?

1000
00:56:12,000 --> 00:56:18,000
V akom momente musím vrátiť chybu, keď používateľ volá tlak, napríklad?

1001
00:56:18,000 --> 00:56:20,000
[Študent] Ak to nie je miesto.

1002
00:56:20,000 --> 00:56:23,000
Presne tak, ak to nie je viac miesta, keď som prekročil kapacitu,

1003
00:56:23,000 --> 00:56:27,000
ktorý je všetky čiapky, pretože to naznačuje, že je to nejaký globálny konštanty.

1004
00:56:27,000 --> 00:56:30,000
No, potom som len tak povedať, "Je mi ľúto, nemôžem tlačiť ďalšiu hodnotu

1005
00:56:30,000 --> 00:56:32,000
do zásobníka, "veľa ako v Mather.

1006
00:56:32,000 --> 00:56:36,000
>> Na nejakom mieste, idú zasiahnuť hornú časť tohto malého kabinetu.

1007
00:56:36,000 --> 00:56:39,000
Tam to nie je miesto, alebo kapacita v zásobníku, na ktorom mieste je tu nejaká chyba.

1008
00:56:39,000 --> 00:56:42,000
Majú dať prvok niekde inde, zásobník niekde inde,

1009
00:56:42,000 --> 00:56:44,000
alebo nikde vôbec.

1010
00:56:44,000 --> 00:56:47,000
Teraz, s fronty, mohli by sme realizovať to trochu inak.

1011
00:56:47,000 --> 00:56:50,000
Fronta sa trochu líši v tom, že pod kapotou, môže byť vykonaná

1012
00:56:50,000 --> 00:56:54,000
ako pole, ale prečo, v tomto prípade, som navrhuje

1013
00:56:54,000 --> 00:56:59,000
tiež mať hlavu prvok predstavujúci hlavu zoznamu,

1014
00:56:59,000 --> 00:57:06,000
predné zoznamu, prvá osoba v súlade v obchode Apple, okrem veľkosti?

1015
00:57:06,000 --> 00:57:14,000
Prečo potrebujem ďalšiu časť dát sem?

1016
00:57:14,000 --> 00:57:16,000
Spomeňte si na to, čo čísla je

1017
00:57:16,000 --> 00:57:18,000
keď som čerpané takto.

1018
00:57:18,000 --> 00:57:21,000
Predpokladajme, že toto je teraz fronta miesto zásobníka,

1019
00:57:21,000 --> 00:57:24,000
Rozdiel je, rovnako ako Apple store-queue je spravodlivé.

1020
00:57:24,000 --> 00:57:27,000
Prvá osoba v súlade na začiatku zoznamu, číslo 5 je v tomto prípade,

1021
00:57:27,000 --> 00:57:30,000
on alebo ona sa bude nechať do obchodu ako prvý.

1022
00:57:30,000 --> 00:57:32,000
Poďme urobiť.

1023
00:57:32,000 --> 00:57:35,000
Predpokladajme, že je to stav môjho frontu v túto chvíľu v čase, a teraz obchod Apple

1024
00:57:35,000 --> 00:57:39,000
otvorí a prvá osoba, číslo 5, je vedený do skladu.

1025
00:57:39,000 --> 00:57:43,000
Ako môžem zmeniť obrázok teraz, keď som odpojený fronte prvej osobe

1026
00:57:43,000 --> 00:57:47,000
na začiatku riadku?

1027
00:57:47,000 --> 00:57:50,000
Čo je to? >> [Študent] Zmena frontu.

1028
00:57:50,000 --> 00:57:52,000
Zmena hlavu, takže 5 zmizne.

1029
00:57:52,000 --> 00:57:56,000
V skutočnosti, je to, ako by-ako najlepšie to urobiť?

1030
00:57:56,000 --> 00:58:00,000
V skutočnosti, je to, ako by ten chlap zmizne.

1031
00:58:00,000 --> 00:58:03,000
Čo by číslo 7 robiť v skutočnom obchode?

1032
00:58:03,000 --> 00:58:05,000
Oni by urobiť veľký krok vpred.

1033
00:58:05,000 --> 00:58:08,000
>> Ale to, čo sme prišli oceniť, pokiaľ ide o pole

1034
00:58:08,000 --> 00:58:10,000
a pohybujúce sa veci okolo?

1035
00:58:10,000 --> 00:58:12,000
To je trochu strata času, že jo?

1036
00:58:12,000 --> 00:58:16,000
Prečo musíš byť tak análny, ako mať prvú osobu

1037
00:58:16,000 --> 00:58:21,000
na začiatku riadku na fyzicky začiatku kus pamäte?

1038
00:58:21,000 --> 00:58:23,000
To je úplne zbytočné. Prečo?

1039
00:58:23,000 --> 00:58:26,000
Čo som mohol len spomenúť miesto? >> [Nepočuteľné Študent odpoveď]

1040
00:58:26,000 --> 00:58:30,000
Presne, mohol Pamätám si s touto ďalšie dátového členovi hlavy

1041
00:58:30,000 --> 00:58:34,000
že teraz vedúci zozname nie je 0, čo bolo pred chvíľou.

1042
00:58:34,000 --> 00:58:39,000
Teraz je to vlastne číslo 1. Týmto spôsobom, získam mierny optimalizáciu.

1043
00:58:39,000 --> 00:58:44,000
Len preto, že som odpojený fronte niekoho z riadku na začiatku riadku v Apple obchode

1044
00:58:44,000 --> 00:58:47,000
neznamená každý má posunúť, čo vyvolanie je lineárna operácia.

1045
00:58:47,000 --> 00:58:50,000
Môžem miesto tráviť konštantný čas iba

1046
00:58:50,000 --> 00:58:53,000
a dosiahnuť potom oveľa rýchlejšiu reakciu.

1047
00:58:53,000 --> 00:58:56,000
Ale cena platím, je to, čo získať, že ďalší výkon

1048
00:58:56,000 --> 00:58:58,000
a nemajú presunúť všetky?

1049
00:58:58,000 --> 00:59:01,000
Jo. >> [Nepočuteľné Študent odpoveď]

1050
00:59:01,000 --> 00:59:04,000
Môže pridať viac ľudí, dobre, že problém je ortogonálne

1051
00:59:04,000 --> 00:59:07,000
k tomu, že nie sme radenie ľudí okolo.

1052
00:59:07,000 --> 00:59:11,000
Je to stále pole, takže tiež posunieme všetky, alebo nie-

1053
00:59:11,000 --> 00:59:13,000
oh, vidím, čo máte na mysli, v poriadku.

1054
00:59:13,000 --> 00:59:16,000
Vlastne, súhlasím s tým, čo hovoríte, v tom, že je to skoro, ako by

1055
00:59:16,000 --> 00:59:19,000
sme teraz nikdy používať začiatku tohto poľa už

1056
00:59:19,000 --> 00:59:22,000
pretože keď som odstrániť 5, potom som odstrániť 7.

1057
00:59:22,000 --> 00:59:24,000
Ale ja som len dať ľuďom doprava.

1058
00:59:24,000 --> 00:59:28,000
>> Je to pocit, ako by som plytváte diskovým priestorom, a nakoniec moja fronta rozpadá do ničoho vôbec,

1059
00:59:28,000 --> 00:59:31,000
takže sme mohli len mať ľudia wraparound,

1060
00:59:31,000 --> 00:59:35,000
a my sme mohli myslieť na tohto poľa naozaj ako akési kruhové štruktúry,

1061
00:59:35,000 --> 00:59:38,000
ale my používame to, čo operátor v C k tomu, že druh wraparound?

1062
00:59:38,000 --> 00:59:40,000
[Nepočuteľné Študent odpoveď] >> operátor modulo.

1063
00:59:40,000 --> 00:59:43,000
Bolo by trochu nepríjemné premyslieť, ako si urobiť wraparound,

1064
00:59:43,000 --> 00:59:46,000
ale my sme mohli urobiť, a my sme mohli začať dávať ľudí na to, čo bývala prednej línie,

1065
00:59:46,000 --> 00:59:52,000
ale my jednoducho zapamätať, s touto hlavou premenné, kto je skutočným vedúci línia vlastne je.

1066
00:59:52,000 --> 00:59:57,000
Čo keď miesto, naším cieľom nakoniec, aj keď,

1067
00:59:57,000 --> 01:00:00,000
Bol sa pozrieť do čísel, ako sme to urobili tu na javisku s Anita,

1068
01:00:00,000 --> 01:00:02,000
ale naozaj chceme to najlepšie zo všetkých týchto svetov?

1069
01:00:02,000 --> 01:00:05,000
Chceme sofistikovanejším, ako pole umožňuje

1070
01:00:05,000 --> 01:00:09,000
pretože chceme schopnosť dynamicky rast dátovú štruktúru.

1071
01:00:09,000 --> 01:00:12,000
Ale my nechceme musieť uchýliť k niečomu, čo sme poukázali

1072
01:00:12,000 --> 01:00:15,000
v prvom prednáške nebol optimálny algoritmus,

1073
01:00:15,000 --> 01:00:17,000
že lineárne hľadanie.

1074
01:00:17,000 --> 01:00:21,000
Ukazuje sa, že je to možné, v skutočnosti, dosiahnuť

1075
01:00:21,000 --> 01:00:24,000
alebo aspoň v blízkosti konštantnom čase, kedy niekto ako Anita,

1076
01:00:24,000 --> 01:00:27,000
keď konfiguruje jej štruktúru dát nesmie byť prepojený zoznam,

1077
01:00:27,000 --> 01:00:30,000
že sa nejedná o zásobník, že sa nejedná o fronty, mohol, v skutočnosti,

1078
01:00:30,000 --> 01:00:33,000
prísť s dátovou štruktúru, ktorá mu umožňuje sa pozrieť do vecí,

1079
01:00:33,000 --> 01:00:37,000
dokonca aj slová, nie len čísla, v čom budeme hovoriť konštantný čas.

1080
01:00:37,000 --> 01:00:40,000
>> A v skutočnosti, s výhľadom do budúcnosti, jeden z psets v tejto triede je takmer vždy

1081
01:00:40,000 --> 01:00:43,000
implementácia pravopisu, pričom

1082
01:00:43,000 --> 01:00:46,000
sme vám zase nejaké 150.000 anglických slov a cieľom je

1083
01:00:46,000 --> 01:00:51,000
nahrať tie do pamäte a rýchlo byť schopní odpovedať na otázky formulára

1084
01:00:51,000 --> 01:00:54,000
je toto slovo napísané správne?

1085
01:00:54,000 --> 01:00:58,000
A to by bolo naozaj sať, ak ste mali určiť iteráciou cez všetky 150.000 slov odpovedať.

1086
01:00:58,000 --> 01:01:02,000
Ale v skutočnosti, uvidíme, že to môžeme urobiť veľmi, veľmi rýchlom čase.

1087
01:01:02,000 --> 01:01:06,000
A to bude zahŕňať realizáciu niečo, čo nazýva hash tabuľky,

1088
01:01:06,000 --> 01:01:09,000
a to aj keď na prvý pohľad to, čomu sa hovorí hash tabuľky bude

1089
01:01:09,000 --> 01:01:12,000
dovoľte nám dosiahnuť tieto super rýchle odozvy,

1090
01:01:12,000 --> 01:01:18,000
ukazuje sa, že je v podstate problém.

1091
01:01:18,000 --> 01:01:23,000
Keď príde čas na prevedenie túto vec s názvom-zase robím to znova.

1092
01:01:23,000 --> 01:01:25,000
Som tu jediný.

1093
01:01:25,000 --> 01:01:28,000
Keď príde čas na vykonávanie tejto veci tzv hash tabuľky,

1094
01:01:28,000 --> 01:01:30,000
budeme musieť urobiť rozhodnutie.

1095
01:01:30,000 --> 01:01:32,000
Ako veľká by tá vec vlastne je?

1096
01:01:32,000 --> 01:01:36,000
A keď začneme vkladanie čísel do tohto hash tabuľky,

1097
01:01:36,000 --> 01:01:38,000
ako budeme ukladať takým spôsobom,

1098
01:01:38,000 --> 01:01:42,000
že sa môžeme dostať je späť tak rýchlo, ako sme sa dostali dovnútra?

1099
01:01:42,000 --> 01:01:45,000
Ale uvidíme onedlho, že táto otázka

1100
01:01:45,000 --> 01:01:48,000
Keď sa všetci narodeniny, je v triede bude celkom Germáni.

1101
01:01:48,000 --> 01:01:51,000
Ukazuje sa, že v tejto miestnosti, máme niekoľko stoviek ľudí,

1102
01:01:51,000 --> 01:01:56,000
takže pravdepodobnosť, že dvaja z nás majú rovnaké narodeniny je asi dosť vysoká.

1103
01:01:56,000 --> 01:01:58,000
Čo keby tam bol len 40 z nás v tejto miestnosti?

1104
01:01:58,000 --> 01:02:02,000
Aké sú šance dvoch ľudí, ktorí majú narodeniny v rovnaký deň?

1105
01:02:02,000 --> 01:02:04,000
[Študenti] Viac ako 50%.

1106
01:02:04,000 --> 01:02:06,000
Jo, viac ako 50%. V skutočnosti, dokonca som priniesol graf.

1107
01:02:06,000 --> 01:02:08,000
Ukazuje sa, a to je naozaj len plížiť preview-

1108
01:02:08,000 --> 01:02:12,000
v prípade, že je len 58 z nás v tejto miestnosti, pravdepodobnosť 2 z nás

1109
01:02:12,000 --> 01:02:16,000
majú narodeniny v rovnaký deň, je veľmi vysoká, takmer 100%,

1110
01:02:16,000 --> 01:02:20,000
a že to bude spôsobovať veľa zranenie pre nás v stredu.

1111
01:02:20,000 --> 01:02:24,000
>> Vďaka, že povedal, poďme odročenie tu. Uvidíme v stredu.

1112
01:02:24,000 --> 01:02:28,000
[Potlesk]

1113
01:02:28,000 --> 01:02:30,000
[CS50.TV]