1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [6. týždeň, pokračovanie]

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

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

4
00:00:08,720 --> 00:00:12,970
To je CS50, a to je koniec 6. týždni.

5
00:00:12,970 --> 00:00:17,970
Takže CS50x, jeden z prvých kurzov Harvardu zapojených do EDX iniciatívy

6
00:00:17,970 --> 00:00:20,590
skutočne debutoval tento rok v pondelok.

7
00:00:20,590 --> 00:00:23,460
Ak by ste chceli, aby si pohľad na to, čo iní na internete

8
00:00:23,460 --> 00:00:27,180
sú teraz po spolu s, môžete vyraziť do x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
To vás presmeruje na príslušné miesto na edx.org,

10
00:00:30,350 --> 00:00:34,160
ktorý bol kde tento a ďalšie kurzy z MIT a Berkeley teraz žijú.

11
00:00:34,160 --> 00:00:38,140
Budete sa musieť zaregistrovať k účtu, zistíte, že materiál je veľmi rovnaký

12
00:00:38,140 --> 00:00:42,170
ako ste mali tento semester, aj keď niekoľko oneskorené týždňov, ako sme si všetko pripravené.

13
00:00:42,170 --> 00:00:46,930
Ale to, čo študenti v CS50x teraz môžete vidieť, je rozhranie úplne, ako je tento.

14
00:00:46,930 --> 00:00:50,040
Tento, napríklad, je Zamyla vedie návod k problému sady 0.

15
00:00:50,040 --> 00:00:54,230
Po prihlásení do edx.org, CS50x Študent vidí rad vecí

16
00:00:54,230 --> 00:00:57,170
by ste očakávať, že v kurze: prednášku pre pondelok,

17
00:00:57,170 --> 00:01:01,650
prednáška na stredu, rôzne šortky, problém súpravy, je priechody, PDF.

18
00:01:01,650 --> 00:01:04,459
Okrem toho, ako tu vidíte, strojové preklady

19
00:01:04,459 --> 00:01:08,390
anglických prepisov do čínština, japončina, španielčina, taliančina,

20
00:01:08,390 --> 00:01:12,810
a celá partia ďalších jazykov, ktoré budú určite nedokonalá

21
00:01:12,810 --> 00:01:15,840
ako sme ich zaviesť programovo pomocou tzv API,

22
00:01:15,840 --> 00:01:18,360
alebo rozhranie pre programovanie aplikácií, od Google

23
00:01:18,360 --> 00:01:21,360
ktoré nám umožňuje previesť z angličtiny do týchto iných jazykov.

24
00:01:21,360 --> 00:01:24,100
Ale vďaka nádhernej duchu niekoľko sto-plus dobrovoľníkov,

25
00:01:24,100 --> 00:01:26,940
Náhodní ľudia na internete, ktorí sa láskavo ponúkol, aby sa zapojili

26
00:01:26,940 --> 00:01:30,180
v rámci tohto projektu, budeme postupne zlepšovať kvalitu týchto prekladov

27
00:01:30,180 --> 00:01:35,790
tým, že ľudia napraviť chyby, ktoré naše počítače vykonali.

28
00:01:35,790 --> 00:01:42,330
>> Tak to dopadá sme niekoľko ďalších študentov ukázať v pondelok, ako sme pôvodne očakávali.

29
00:01:42,330 --> 00:01:48,980
V skutočnosti, teraz CS50x má 100.000 ľudí po doma.

30
00:01:48,980 --> 00:01:54,430
Takže uvedomíte, že ste to všetko je súčasťou tejto otváracej trieda robiť tento kurz v informatike

31
00:01:54,430 --> 00:01:57,370
vzdelávanie všeobecne, viac široko, prístupné.

32
00:01:57,370 --> 00:02:00,130
A realita je teraz, s niektorými z týchto masívnych online kurzov,

33
00:02:00,130 --> 00:02:04,070
všetci začnú s týmito veľmi vysokých čísel, ako sa zdá, urobili tu.

34
00:02:04,070 --> 00:02:08,759
Ale cieľom, nakoniec, pre CS50x je naozaj dostať toľko ľudí na cieľovú čiaru ako je to možné.

35
00:02:08,759 --> 00:02:12,000
Podľa návrhu, CS50x sa bude ponúknutá z tejto minulosti pondelok

36
00:02:12,000 --> 00:02:17,430
celú cestu cez 15 apríl 2013, tak, že ľudia, ktorí majú školské povinnosti inde,

37
00:02:17,430 --> 00:02:20,990
práca, rodina, iné konflikty a podobne, majú trochu väčšiu flexibilitu

38
00:02:20,990 --> 00:02:23,640
s ktorými sa ponoriť do tohto kurzu, ktorý, stačí povedať,

39
00:02:23,640 --> 00:02:30,540
je pomerne ambiciózne robiť, keď len v priebehu iba troch mesiacov počas obvyklého semestra.

40
00:02:30,540 --> 00:02:34,190
Ale títo študenti budú riešiť rovnaký problém sady, prezeranie rovnaký obsah,

41
00:02:34,190 --> 00:02:36,350
majú prístup k rovnakým šortky a ako.

42
00:02:36,350 --> 00:02:38,990
Takže si uvedomiť, že sme všetci naozaj v tom spoločne.

43
00:02:38,990 --> 00:02:42,360
A jeden z koncových cieľov CS50x nie je len dostať toľko ľudí

44
00:02:42,360 --> 00:02:45,720
na cieľovej čiare a dať im túto novo nájdenú chápanie informatiky

45
00:02:45,720 --> 00:02:49,000
a programovanie, ale aj nechať túto zdieľanú skúsenosť.

46
00:02:49,000 --> 00:02:52,010
Jedným z určujúcich charakteristík 50 na akademickej pôde, dúfame,

47
00:02:52,010 --> 00:02:56,260
bol tento druh komunálneho skúseností, pre lepšie alebo pre horšie, niekedy,

48
00:02:56,260 --> 00:02:59,480
ale s títo ľudia obrátiť na vľavo a vpravo,

49
00:02:59,480 --> 00:03:01,830
a úradné hodiny a hackathon a spravodlivé.

50
00:03:01,830 --> 00:03:04,560
Je to trochu ťažšie k tomu, že osobne s ľudí on-line,

51
00:03:04,560 --> 00:03:10,580
ale CS50x skončí v apríli historicky prvej CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
ktorý bude on-line adaptácia našej predstave o veľtrhu

53
00:03:13,630 --> 00:03:18,250
kde budú tieto tisíce študentov všetci vyzvaní na predloženie 1 - až 2-minútového videoklipu,

54
00:03:18,250 --> 00:03:22,480
buď screencast ich konečného projektu alebo videa z nich mával ahoj

55
00:03:22,480 --> 00:03:24,490
a hovorí o svojich projektoch a demoing to,

56
00:03:24,490 --> 00:03:27,610
rovnako ako zoznam predchodcov tu na akademickej pôde na veľtrhu,

57
00:03:27,610 --> 00:03:31,400
tak, že semester konca, je nádej, mať globálny výstavu

58
00:03:31,400 --> 00:03:37,080
z konečných CS50x študentov projektov, rovnako ako ten, ktorý na vás čaká tento rok v decembri tu na akademickej pôde.

59
00:03:37,080 --> 00:03:39,680
Takže o tom viac v nadchádzajúcich mesiacoch.

60
00:03:39,680 --> 00:03:43,640
>> S 100.000 študentov však prichádza aj potreba niekoľkých ďalších autorít.

61
00:03:43,640 --> 00:03:47,590
Vzhľadom k tomu, že chlapci sú horiace stopu tu a užívať CS50

62
00:03:47,590 --> 00:03:51,630
niekoľko týždňov vopred, tento materiál je vydanie na ľudí na EDX,

63
00:03:51,630 --> 00:03:55,330
uvedomiť, radi by sme zapojiť čo najviac našich vlastných študentov, ako je to možné v tejto iniciatíve,

64
00:03:55,330 --> 00:03:58,720
ako v priebehu semestra aj tohto zime a tento rok na jar.

65
00:03:58,720 --> 00:04:01,620
Takže ak by ste chceli, aby sa zapojili do CS50x,

66
00:04:01,620 --> 00:04:07,450
najmä spojenie v na CS50x diskutovať, verzii EDX z CS50 diskutovať,

67
00:04:07,450 --> 00:04:10,140
ktoré mnohí z vás používa na akademickej pôde, on-line bulletin board,

68
00:04:10,140 --> 00:04:13,040
vykonajte hlavu k tejto adrese URL, dajte nám vedieť, kto ste,

69
00:04:13,040 --> 00:04:16,450
pretože by sme radi vybudovať tím študentov a zamestnancov fakulty a podobne

70
00:04:16,450 --> 00:04:19,630
na akademickej pôde, ktorí sú jednoducho hrať spolu a pomáhať.

71
00:04:19,630 --> 00:04:21,720
A keď vidí otázku, ktorá je oboznámení,

72
00:04:21,720 --> 00:04:25,320
počujete študenta nehlási nejaké chyby niekde tam v nejakej krajine na internete,

73
00:04:25,320 --> 00:04:27,450
a že krúžky zvonu, pretože ste príliš mal ten rovnaký problém

74
00:04:27,450 --> 00:04:32,620
v d-haly pred časom, dúfajme, že potom môžete přizvukovat a podeľte sa o svoje vlastné skúsenosti.

75
00:04:32,620 --> 00:04:37,300
Takže prosím, podieľať sa, ak chcete.

76
00:04:37,300 --> 00:04:39,360
>> Kurzy Počítačové vedy na Harvarde majú trochu tradície,

77
00:04:39,360 --> 00:04:44,730
CS50 medzi nimi, mať nejaké oblečenie, niektoré oblečenie, ktoré môžete nosiť hrdo

78
00:04:44,730 --> 00:04:49,090
na semester konci, hovorí celkom hrdo, že ste skončil CS50

79
00:04:49,090 --> 00:04:51,830
a vzal CS50 a podobne, a vždy sa snažíme zapojiť študentov

80
00:04:51,830 --> 00:04:54,540
v tomto procese, ako je to možné, pričom pozývame,

81
00:04:54,540 --> 00:04:56,900
V tejto dobe semestra, študenti predkladať návrhy

82
00:04:56,900 --> 00:04:59,330
pomocou Photoshopu, alebo čokoľvek nástroj výberu by ste chceli použiť

83
00:04:59,330 --> 00:05:02,330
ak ste dizajnér, aby predložila návrhy na tričká a mikiny

84
00:05:02,330 --> 00:05:06,100
a slnečníky a malé šatky pre psov máme a podobne.

85
00:05:06,100 --> 00:05:09,370
A všetko je potom - víťazi každý rok sú potom vystavené

86
00:05:09,370 --> 00:05:12,700
na ihrisku internetových stránkach store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Všetko je predávaný za cenu tam, ale na internetových stránkach jednoducho beží sám

88
00:05:15,790 --> 00:05:18,330
a umožňuje ľuďom si vybrať farby a vzory, ktoré sa im páčia.

89
00:05:18,330 --> 00:05:20,420
Tak som myslel, že sme sa práve podeliť o minuloročných návrhov

90
00:05:20,420 --> 00:05:25,130
ktoré boli na internetových stránkach okrem tento tu, čo je každoročné tradíciou.

91
00:05:25,130 --> 00:05:29,410
"Každý deň som Seg Faultn" bol jeden z príspevkov v minulom roku,

92
00:05:29,410 --> 00:05:32,290
ktorý je stále k dispozícii tam pre absolventov.

93
00:05:32,290 --> 00:05:35,820
Mali sme tento, "CS50, so sídlom 1989."

94
00:05:35,820 --> 00:05:39,010
Jeden z našich Bowdeny, Rob, bol veľmi populárny v minulom roku.

95
00:05:39,010 --> 00:05:43,480
"Tím Bowden" sa narodil, bol tento dizajn predložený, medzi top predajcov.

96
00:05:43,480 --> 00:05:49,040
Ako bola táto tu. Mnoho ľudí v tej "Bowden Fever" podľa predajných protokolov.

97
00:05:49,040 --> 00:05:52,650
Uvedomte si, že teraz môže byť váš návrh je, a to až na internete.

98
00:05:52,650 --> 00:05:57,510
Ďalšie podrobnosti o tomto v ďalší problém nastaví prísť.

99
00:05:57,510 --> 00:06:00,330
>> Jeden z ďalších nástrojov: si mal nejaký prejav a dúfajme, že teraz

100
00:06:00,330 --> 00:06:02,350
niektoré hands-on skúsenosti s GDB,

101
00:06:02,350 --> 00:06:04,570
ktorý je, samozrejme, debugger a umožňuje manipulovať

102
00:06:04,570 --> 00:06:09,500
váš program na pomerne nízkej úrovni, robiť to, čo druhy vecí?

103
00:06:09,500 --> 00:06:13,030
Čo GDB nechať urobiť?

104
00:06:13,030 --> 00:06:15,030
Jo? Daj mi niečo. [Študent odpoveď, nezrozumiteľným]

105
00:06:15,030 --> 00:06:18,120
Dobre. Krok do funkcie, takže to nie je len musieť zadať spustiť

106
00:06:18,120 --> 00:06:22,310
a mať program ranu cez plnom rozsahu, tlač na veci, na štandardný výstup.

107
00:06:22,310 --> 00:06:25,190
Skôr, môžete krokovať ju riadok po riadku, a to buď zadaním ďalšie

108
00:06:25,190 --> 00:06:30,300
ísť riadok po riadku po riadku alebo krok sa ponoriť do funkcie, obvykle ten, ktorý si napísal.

109
00:06:30,300 --> 00:06:35,240
Čo iného to GDB nechať urobiť? Jo? [Študent odpoveď, nezrozumiteľným]

110
00:06:35,240 --> 00:06:38,100
Tlač premenných. Takže ak chcete urobiť trochu sebapozorovania vnútri programu

111
00:06:38,100 --> 00:06:41,500
aby bolo nutné uchýliť sa k písaniu printf vyhlásenie všade možne,

112
00:06:41,500 --> 00:06:44,600
stačí vytlačiť premennú alebo zobraziť premenné.

113
00:06:44,600 --> 00:06:46,710
Čo ešte môžete urobiť s debuggerom ako GDB?

114
00:06:46,710 --> 00:06:49,170
[Študent odpoveď, nezrozumiteľným]

115
00:06:49,170 --> 00:06:52,080
Presne tak. Môžete nastaviť zarážky, môžete povedať prerušenie výkonu

116
00:06:52,080 --> 00:06:54,020
na hlavnú funkciu alebo funkciu foo.

117
00:06:54,020 --> 00:06:56,800
Môžete povedať, že prerušenie výkonu na riadku 123.

118
00:06:56,800 --> 00:06:58,950
A zarážky sú naozaj účinný spôsob

119
00:06:58,950 --> 00:07:01,110
pretože ak máte všeobecný pocit o tom, kde váš problém

120
00:07:01,110 --> 00:07:05,360
Pravdepodobne je, nemusíte strácať čas prechádzaním programu rozsahu.

121
00:07:05,360 --> 00:07:08,250
Môžete v podstate skočiť priamo tam a potom začať písať -

122
00:07:08,250 --> 00:07:10,970
krokovanie to s krokom alebo ďalšie alebo podobne.

123
00:07:10,970 --> 00:07:14,340
Ale úlovok s niečím, ako je GDB je, že to pomôže, človek,

124
00:07:14,340 --> 00:07:16,940
nájsť svoje problémy a nájsť svoje chyby.

125
00:07:16,940 --> 00:07:19,470
To nemusí nutne nájsť im tak veľa pre teba.

126
00:07:19,470 --> 00:07:23,070
>> Takže sme zaviedli druhý deň style50, ktorý je krátky príkaz čiara

127
00:07:23,070 --> 00:07:27,500
, Ktorý sa snaží štylizovať váš kód trochu čistejšie, než vy, môže človek mať hotovo.

128
00:07:27,500 --> 00:07:29,530
Ale aj to je naozaj len estetickú záležitosť.

129
00:07:29,530 --> 00:07:34,110
Ale ukázalo sa, že je to ďalší nástroj s názvom Valgrind, že je trochu viac nejobskurnější na použitie.

130
00:07:34,110 --> 00:07:36,860
Jeho výstup je ukrutne mystický na prvý pohľad.

131
00:07:36,860 --> 00:07:39,420
Ale je to nádherne užitočné, zvlášť teraz, keď sme u tej časti funkčného obdobia

132
00:07:39,420 --> 00:07:43,080
kde začínate používať malloc a dynamického prideľovania pamäte.

133
00:07:43,080 --> 00:07:45,420
Veci môžu ísť naozaj, ale naozaj zle rýchlo.

134
00:07:45,420 --> 00:07:49,320
Pretože ak ste zabudli uvoľniť pamäť, alebo dereferencia nejaký ukazovateľ NULL,

135
00:07:49,320 --> 00:07:55,770
alebo dereferencia nejaké odpadky ukazovateľ, čo je zvyčajne príznakom, že výsledky?

136
00:07:55,770 --> 00:07:59,470
Seg poruchu. A dostanete tento základný súbor určitého počtu kilobajtov alebo megabajty

137
00:07:59,470 --> 00:08:02,990
, Ktorý predstavuje stav vášho programu do pamäte, keď havaroval,

138
00:08:02,990 --> 00:08:05,730
ale váš program nakoniec seg chyby, Segmentation fault,

139
00:08:05,730 --> 00:08:08,450
čo znamená, že sa niečo zlé stalo takmer vždy súvisí

140
00:08:08,450 --> 00:08:11,750
na pamäti súvisiace chyby, ktoré ste urobili niekde.

141
00:08:11,750 --> 00:08:14,100
Takže Valgrind vám pomôže nájsť veci, ako je táto.

142
00:08:14,100 --> 00:08:17,720
Je to nástroj, ktorý môžete spustiť ako GDB, potom, čo ste zostavil svoj program,

143
00:08:17,720 --> 00:08:20,330
ale skôr ako spustiť program priamo, spustiť Valgrind

144
00:08:20,330 --> 00:08:23,960
a odovzdáte jej svoj program, rovnako ako vy s GDB.

145
00:08:23,960 --> 00:08:26,220
Teraz, použitie, aby ste získali najlepší druh výstupu,

146
00:08:26,220 --> 00:08:30,410
je trochu dlhý, takže tam na vrchole obrazovky uvidíte Valgrind-V.

147
00:08:30,410 --> 00:08:35,350
"-V" takmer všeobecne rozumie výrečnosť, keď používate programy na počítači so systémom Linux.

148
00:08:35,350 --> 00:08:38,770
Takže to znamená, vypľuť viac dát, ako ste mohli v predvolenom nastavení.

149
00:08:38,770 --> 00:08:45,510
"- Únik kontrola = plná." To je len hovorí kontrolu všetkých možných únikov pamäte,

150
00:08:45,510 --> 00:08:49,430
chyby, ktoré som mohol nekoná. To je tiež obyčajný vzor s linuxovými programami.

151
00:08:49,430 --> 00:08:52,710
Všeobecne platí, že ak máte príkazového riadku argument, že je to "switch",

152
00:08:52,710 --> 00:08:55,830
že to má zmeniť správanie programu, a to jedno písmeno,

153
00:08:55,830 --> 00:09:00,310
to-v, ale ak to je zapnutý, len tým, že konštrukciu programátora,

154
00:09:00,310 --> 00:09:05,150
je na celé slovo alebo rad slov, argument príkazového riadku začína -.

155
00:09:05,150 --> 00:09:08,190
To sú len ľudské konvencie, ale budete vidieť stále.

156
00:09:08,190 --> 00:09:12,410
A potom, nakoniec, "a.out" je ľubovoľný názov pre program v tomto konkrétnom prípade.

157
00:09:12,410 --> 00:09:14,640
A tu je niekoľko zástupca výstup.

158
00:09:14,640 --> 00:09:22,890
>> Než sa pozrieme na to, čo by to mohlo znamenať, nechaj ma ísť sa k úryvok kódu sem.

159
00:09:22,890 --> 00:09:26,390
A dovoľte mi prejsť to z cesty, čoskoro,

160
00:09:26,390 --> 00:09:32,120
a poďme sa pozrieť na memory.c, čo je tento krátky príklad.

161
00:09:32,120 --> 00:09:36,290
Takže v tomto programe, dovoľte mi, aby som sa zamerať na funkcie a otázky.

162
00:09:36,290 --> 00:09:39,430
Máme funkciu hlavnej, ktorá volá funkciu, f,

163
00:09:39,430 --> 00:09:45,590
a potom to, čo sa f pokračovať robiť, mierne technické angličtiny?

164
00:09:45,590 --> 00:09:49,760
Čo f pokračovať robiť?

165
00:09:49,760 --> 00:09:53,680
Ako asi začnem s linkou 20, a na hviezdy zaradenie nezáleží,

166
00:09:53,680 --> 00:09:56,720
ale ja budem len v súlade tu s poslednej prednáške.

167
00:09:56,720 --> 00:09:59,910
Čo je to riadok 20 sa pre nás? Na ľavej strane. Budeme vyraziť ďalej.

168
00:09:59,910 --> 00:10:02,410
Int * x: čo to robí?

169
00:10:02,410 --> 00:10:04,940
Dobre. Je to prehlasuje ukazovateľ, a teraz poďme ešte technická.

170
00:10:04,940 --> 00:10:10,230
Čo to znamená, veľmi konkrétne, vyhlásiť ukazovateľ? Niekto iný?

171
00:10:10,230 --> 00:10:15,050
Jo? [Študent odpoveď, nezrozumiteľné] Príliš ďaleko.

172
00:10:15,050 --> 00:10:17,060
Takže čítate na pravej strane rovná sa.

173
00:10:17,060 --> 00:10:20,290
Zamerajme sa len na ľavej strane, len na int * x.

174
00:10:20,290 --> 00:10:24,700
To "vyhlásil" ukazovateľ, ale teraz poďme ponoriť hlbšie do tejto definície.

175
00:10:24,700 --> 00:10:28,330
Čo to konkrétne, technicky znamená? Jo?

176
00:10:28,330 --> 00:10:31,940
[Študent odpoveď, nezrozumiteľným]

177
00:10:31,940 --> 00:10:35,090
Dobre. Je to príprava na jednu adresu uložiť do pamäte.

178
00:10:35,090 --> 00:10:40,680
Dobre. A poďme ešte o krok ďalej, je to deklarovaní premennej, x, to je 32 bitov.

179
00:10:40,680 --> 00:10:44,440
A ja viem, že je to 32 bitov, pretože -?

180
00:10:44,440 --> 00:10:47,390
Nie je to preto, že je to int, pretože je to ukazovateľ v tomto prípade.

181
00:10:47,390 --> 00:10:49,650
Náhoda, že je to jedno a to isté s int,

182
00:10:49,650 --> 00:10:51,970
ale skutočnosť, že je hviezda, že znamená, že tento je ukazovateľ

183
00:10:51,970 --> 00:10:57,300
a v zariadení, ako s mnohými počítačov, ale nie všetky, ukazovatele sú 32 bitov.

184
00:10:57,300 --> 00:11:01,850
Na viac moderný hardvér, ako najnovšie Macy, najnovšie počítačov, môžete mať 64-bit ukazovatele,

185
00:11:01,850 --> 00:11:04,160
ale v zariadení, tieto veci sú 32 bitov.

186
00:11:04,160 --> 00:11:08,380
Takže budeme štandardizovať na tom. Konkrétnejšie, príbeh znie takto:

187
00:11:08,380 --> 00:11:10,820
My "vyhlásil" ukazovateľ, čo to znamená?

188
00:11:10,820 --> 00:11:12,810
Pripravíme pre uloženie adresu pamäte.

189
00:11:12,810 --> 00:11:15,530
Čo to znamená?

190
00:11:15,530 --> 00:11:19,810
My vytvoríme premennú s názvom X, ktorý zaberá 32 bitov

191
00:11:19,810 --> 00:11:23,810
že bude čoskoro uložiť adresu integer.

192
00:11:23,810 --> 00:11:26,470
A to je asi asi tak presné, ako sa môžeme dostať.

193
00:11:26,470 --> 00:11:31,810
To je v poriadku dopredu zjednodušiť svet a len povedať, deklarovať ukazovateľ s názvom x.

194
00:11:31,810 --> 00:11:35,380
Declare ukazovateľ, ale uvedomiť si a pochopiť, čo sa vlastne deje

195
00:11:35,380 --> 00:11:38,490
dokonca v niekoľkých tých niekoľkých znakov.

196
00:11:38,490 --> 00:11:42,040
>> Teraz, toto je skoro niečo jednoduchšie, aj keď je to dlhší výraz.

197
00:11:42,040 --> 00:11:48,160
Takže to, čo je to robí, že je zvýraznený teraz: "malloc (10 * sizeof (int));" Jo?

198
00:11:48,160 --> 00:11:52,350
[Študent odpoveď, nezrozumiteľným]

199
00:11:52,350 --> 00:11:58,250
Dobre. A ja si to tam. Je to pridelenie kus pamäte pre desať celých čísel.

200
00:11:58,250 --> 00:12:02,190
A teraz poďme ponoriť do mierne hlbšie, je to pridelenie kus pamäte pre desať celých čísel.

201
00:12:02,190 --> 00:12:05,390
Čo je malloc potom sa vracať?

202
00:12:05,390 --> 00:12:10,390
Adresa tohto bloku, alebo, viac konkrétne, adresa prvého bajtu tohto bloku.

203
00:12:10,390 --> 00:12:14,080
Ako potom som, programátor, vedieť, kde to kus pamäte koncoch?

204
00:12:14,080 --> 00:12:18,340
Ja viem, že je to súvislá. Malloc, podľa definície, vám súvislý kus pamäte.

205
00:12:18,340 --> 00:12:21,240
Žiadne medzery v ňom. Máte prístup ku všetkým bytu v tomto bloku,

206
00:12:21,240 --> 00:12:26,760
chrbtom k sebe k sebe, ale ako to mám vedieť, kde na konci tohto bloku pamäte je?

207
00:12:26,760 --> 00:12:28,850
Pri použití malloc? [Študent odpoveď, nezrozumiteľné] Good.

208
00:12:28,850 --> 00:12:30,670
Vy nie. Musíte si uvedomiť,.

209
00:12:30,670 --> 00:12:35,960
Musím si uvedomiť, že som použil hodnotu 10, a nemám ani Zdá sa, že urobiť to tu.

210
00:12:35,960 --> 00:12:41,000
Ale povinnosť je úplne na mňa. Strlen, ktoré sme sa mierne závislé na pre slučke,

211
00:12:41,000 --> 00:12:45,860
funguje len preto, že tohto dohovoru, že bude \ 0

212
00:12:45,860 --> 00:12:48,840
alebo tento špeciálny znak NUL, NUL, na konci reťazca.

213
00:12:48,840 --> 00:12:51,740
To však neplatí pre len ľubovoľné kúsky pamäti.

214
00:12:51,740 --> 00:12:58,590
Je to len na vás. Takže riadku 20, potom prideľuje kus pamäte

215
00:12:58,590 --> 00:13:02,590
že je možné uložiť desať celé čísla, a to uloží adresu prvého bajtu

216
00:13:02,590 --> 00:13:05,610
tohto kusu pamäti v premennej nazvanej x.

217
00:13:05,610 --> 00:13:11,140
Ergo, čo je ukazovateľom. Takže riadku 21, bohužiaľ, bola to chyba.

218
00:13:11,140 --> 00:13:16,110
Ale najprv, čo to robí? Je to hovorí obchod v mieste 10, 0 indexované,

219
00:13:16,110 --> 00:13:19,480
z bloku pamäte zvanej x hodnota 0.

220
00:13:19,480 --> 00:13:21,510
>> Takže si všimnúť pár vecí sa deje.

221
00:13:21,510 --> 00:13:25,420
Aj keď x je ukazovateľ, prevezme od pred pár týždňami

222
00:13:25,420 --> 00:13:29,440
že môžete aj naďalej používať pole-štýle hranatá zátvorka notáciu.

223
00:13:29,440 --> 00:13:36,180
Vzhľadom k tomu, že je to vlastne krátky-ruka zápis pre viac tajomné vyzerajúce ukazovateľ aritmetiky.

224
00:13:36,180 --> 00:13:40,320
kde by sme urobiť niečo takéto: Take adresu x, presuňte 10 miest po,

225
00:13:40,320 --> 00:13:44,550
potom tam na čokoľvek adresa je uložená na tomto mieste.

226
00:13:44,550 --> 00:13:48,090
Ale úprimne povedané, to je len otrasné čítať a zoznámiť sa tak s

227
00:13:48,090 --> 00:13:52,900
Takže svet sa zvyčajne používa hranaté zátvorky len preto, že je to oveľa viac človeka-friendly čítať.

228
00:13:52,900 --> 00:13:55,140
Ale to je to, čo sa naozaj deje pod kapotou;

229
00:13:55,140 --> 00:13:58,190
x je adresa, nie pole, samo o sebe.

230
00:13:58,190 --> 00:14:02,410
Tak to je ukladanie 0 na mieste 10 v x.

231
00:14:02,410 --> 00:14:06,120
Prečo je to zlé? Jo?

232
00:14:06,120 --> 00:14:17,370
[Študent odpoveď, nezrozumiteľné] Presne tak.

233
00:14:17,370 --> 00:14:21,100
Máme len pridelené desať Ints, ale počítame od 0 pri programovaní v C,

234
00:14:21,100 --> 00:14:25,690
takže máte prístup k 0 1 2 3 4 5 6 7 8 9, ale nie 10.

235
00:14:25,690 --> 00:14:30,270
Takže buď program bude seg vinou alebo to nie je.

236
00:14:30,270 --> 00:14:32,900
Ale my naozaj nevieme, to je niečo ako nedeterministického správanie.

237
00:14:32,900 --> 00:14:35,600
To naozaj záleží na tom, či budeme mať šťastie.

238
00:14:35,600 --> 00:14:40,650
Ak sa ukáže, že operačný systém nevadí, keď budem používať, že ďalší bajt,

239
00:14:40,650 --> 00:14:43,360
aj keď to nie je, rovnako mi to, možno môj program nespadne.

240
00:14:43,360 --> 00:14:46,780
Je to surové, je to buggy, ale možno nie je vidieť, že príznak,

241
00:14:46,780 --> 00:14:48,960
alebo môžete vidieť len raz za čas.

242
00:14:48,960 --> 00:14:51,230
Skutočnosť je však taká, že chyba je v skutočnosti, tam.

243
00:14:51,230 --> 00:14:54,320
A je to naozaj problematické, ak ste napísali program, ktorý chcete byť správne,

244
00:14:54,320 --> 00:14:58,840
že ste predal program, ktorý ľudia používajú, že každý raz za čas spadne

245
00:14:58,840 --> 00:15:02,450
pretože, samozrejme, to nie je dobrá. V skutočnosti, ak máte telefón so systémom Android alebo iPhone

246
00:15:02,450 --> 00:15:05,550
a sťahovať aplikácie v týchto dňoch, ak ste niekedy mali app ukončiť,

247
00:15:05,550 --> 00:15:10,040
naraz zmizne, je to takmer vždy dôsledkom nejakej pamäti otázkach súvisiacich,

248
00:15:10,040 --> 00:15:12,830
kedy programátor posral a dereferenced ukazovateľ

249
00:15:12,830 --> 00:15:18,670
že on alebo ona by nemala mať, a výsledok iOS alebo Android, je len tak zabiť program úplne

250
00:15:18,670 --> 00:15:23,080
skôr než riskovať nedefinovanej správanie alebo nejaký druh zabezpečenia kompromisu.

251
00:15:23,080 --> 00:15:25,950
>> Je tu ešte jedna chyba v tomto programe okrem tohto jedného.

252
00:15:25,950 --> 00:15:30,180
Čo iného som podelal v tomto programe?

253
00:15:30,180 --> 00:15:32,740
Ešte som cvičil, čo som kázal. Jo?

254
00:15:32,740 --> 00:15:34,760
[Študent odpoveď, nezrozumiteľné] Good.

255
00:15:34,760 --> 00:15:36,880
Som nebola uvoľnená pamäť. Takže pravidlo teraz

256
00:15:36,880 --> 00:15:43,150
musí byť kedykoľvek budete volať malloc, musíte volať zadarmo, keď ste hotoví použitie tejto pamäte.

257
00:15:43,150 --> 00:15:45,610
Teraz by keď chcem uvoľniť túto pamäť?

258
00:15:45,610 --> 00:15:49,780
Pravdepodobne, za predpokladu, že tento prvý riadok bol správny, chcel by som to robiť tu.

259
00:15:49,780 --> 00:15:55,710
Pretože som nemohla, napríklad, to tu. Prečo?

260
00:15:55,710 --> 00:15:57,860
Len mimo rozsah. Takže aj keď hovoríme o ukazovatele,

261
00:15:57,860 --> 00:16:04,830
To je týždeň 2 alebo 3 vydanie, kde x je len v rozsahu vnútornej strane zložených zátvorkách, kde bolo deklarované.

262
00:16:04,830 --> 00:16:11,000
Takže si rozhodne nemôžete uvoľniť ju tam. Moja jediná šanca, ako oslobodiť je zhruba po riadku 21.

263
00:16:11,000 --> 00:16:15,170
Jedná sa o pomerne jednoduchý program, to bolo celkom jednoduché, akonáhle tak nejako zabalené svoju myseľ

264
00:16:15,170 --> 00:16:17,870
okolo, čo program robí, kde chyby boli.

265
00:16:17,870 --> 00:16:20,500
A aj keď ste to nevidel na prvý, dúfajme, že to je trochu jasné hneď

266
00:16:20,500 --> 00:16:23,870
že tieto chyby sú celkom ľahko vyriešiť a ľahko vykonávať.

267
00:16:23,870 --> 00:16:28,720
Ale keď program je viac ako 12 liniek dlho, je to 50 riadkov dlhý, 100 riadkov dlhý,

268
00:16:28,720 --> 00:16:31,150
pešia cez riadky kódu, premýšľaní toho logicky,

269
00:16:31,150 --> 00:16:35,110
je možné, ale nijako zvlášť zábavné robiť, neustále hľadá chyby,

270
00:16:35,110 --> 00:16:38,340
a je to tiež ťažké robiť, a to je dôvod, prečo nástroj ako Valgrind existuje.

271
00:16:38,340 --> 00:16:40,900
Nechaj ma ísť ďalej a to: dovoľte mi, aby som otvorím okno terminálu,

272
00:16:40,900 --> 00:16:45,400
a nenechaj ma stačí spustiť pamäť, pretože pamäť sa zdá byť v poriadku.

273
00:16:45,400 --> 00:16:49,180
Začínam mať šťastie. Prechod na tejto dodatočnej byte na konci poľa

274
00:16:49,180 --> 00:16:51,060
nezdá byť príliš problematické.

275
00:16:51,060 --> 00:16:56,370
Ale dovoľte mi, aby som napriek tomu, urobiť zdravý rozum kontrolu, ktorá sa práve znamená pre kontrolu

276
00:16:56,370 --> 00:16:58,320
či alebo nie toto je vlastne správne.

277
00:16:58,320 --> 00:17:04,690
>> Tak poďme urobiť Valgrind-V - leak-check = full,

278
00:17:04,690 --> 00:17:07,520
a potom názov programu v tomto prípade je pamäť, nie je a.out.

279
00:17:07,520 --> 00:17:10,760
Tak nechaj ma ísť ďalej a robiť to. Stlačte Enter.

280
00:17:10,760 --> 00:17:14,109
Vážení Boh. To je jeho výkon, a to je to, čo som spomenul skôr.

281
00:17:14,109 --> 00:17:17,550
Ale, ak sa naučíte čítať cez všetky nezmysly tu,

282
00:17:17,550 --> 00:17:20,760
väčšina z toho je len diagnostických výstup, že to nie je tak zaujímavé.

283
00:17:20,760 --> 00:17:24,829
Aký je váš oko naozaj chce, že sa pozerá, je akákoľvek zmienka o chybe alebo neplatné.

284
00:17:24,829 --> 00:17:26,800
Slová, ktoré naznačujú problémy.

285
00:17:26,800 --> 00:17:29,340
A skutočne, pozrieme sa, čo sa deje zle tu.

286
00:17:29,340 --> 00:17:35,230
Mám prehľad o akési ", v použití na výjazde:. 40 bytov v 1 blokov"

287
00:17:35,230 --> 00:17:38,750
Nie som si istý, čo blok je ešte, ale 40 bytov

288
00:17:38,750 --> 00:17:41,260
skutočne cíti, že by som mohol prísť na to, kde to prichádza z

289
00:17:41,260 --> 00:17:45,030
40 bytov. Prečo sú 40 bytov v použití na výjazde?

290
00:17:45,030 --> 00:17:48,780
A konkrétne, ak budeme prechádzať sem,

291
00:17:48,780 --> 00:17:54,520
Preto som definitívne stratil 40 bajtov? Jo?

292
00:17:54,520 --> 00:17:59,520
[Študent odpoveď, nezrozumiteľné] Perfect. Jo, presne tak.

293
00:17:59,520 --> 00:18:03,540
Tam bolo desať celé čísla, a každý z nich je veľkosť 4, alebo 32 bitov,

294
00:18:03,540 --> 00:18:08,300
takže som stratil presne 40 bajtov, pretože, ako ste navrhoval, som nevolal zadarmo.

295
00:18:08,300 --> 00:18:13,460
To je jedna chyba, a teraz sa poďme pozrieť dole trochu ďalej a vidieť vedľa tohto,

296
00:18:13,460 --> 00:18:16,900
"Neplatný písať veľkosti 4". Teraz, čo je to?

297
00:18:16,900 --> 00:18:21,150
Táto adresa je vyjadrené to, čo základný zápis, zrejme?

298
00:18:21,150 --> 00:18:23,640
To je hexadecimálny, a kedykoľvek uvidíte číslo začínajúce 0x,

299
00:18:23,640 --> 00:18:29,410
to znamená hexadecimálne, ktoré sme už v roku, myslím, oddielu PSet 0 zo otázok,

300
00:18:29,410 --> 00:18:34,090
ktorý bol len urobiť zahrievacie cvičenia, prevod desiatkovej na hexadecimálne do binárnej a tak ďalej.

301
00:18:34,090 --> 00:18:39,220
Hexadecimálne, len ľudskú konvencií, je zvyčajne používaný reprezentovať ukazovatele

302
00:18:39,220 --> 00:18:41,570
alebo, všeobecnejšie, rieši. Je to len konvencie,

303
00:18:41,570 --> 00:18:45,340
pretože je to trochu jednoduchšie čítať, je to trochu kompaktnejšie, než niečo ako desiatkové,

304
00:18:45,340 --> 00:18:47,720
a binárne je k ničomu pre väčšinu ľudí používať.

305
00:18:47,720 --> 00:18:50,840
Takže teraz, čo to znamená? No, to vyzerá, že je neplatný zápis

306
00:18:50,840 --> 00:18:54,480
o veľkosti 4 na riadku 21 v memory.c.

307
00:18:54,480 --> 00:18:59,180
Takže sa vráťme k riadku 21, a naozaj, je to, že neplatný zápis.

308
00:18:59,180 --> 00:19:02,640
Takže Valgrind nebude úplne ma držal za ruku a povedz mi, čo je oprava,

309
00:19:02,640 --> 00:19:05,520
ale to je zistenie, že robím neplatný zápis.

310
00:19:05,520 --> 00:19:08,800
Ja dotýkať 4 bajty, že by som nemal byť, a zrejme to preto, že,

311
00:19:08,800 --> 00:19:13,960
ako ste zdôraznil, robím [10] namiesto [9] maximálne

312
00:19:13,960 --> 00:19:16,660
alebo [0] alebo niečo medzi tým.

313
00:19:16,660 --> 00:19:19,690
S Valgrind uvedomiť, kedykoľvek budete teraz písanie programu

314
00:19:19,690 --> 00:19:24,190
ktorý používa ukazovatele a využíva pamäť, a malloc konkrétnejšie,

315
00:19:24,190 --> 00:19:27,080
určite si do zvyku beží tak dlho

316
00:19:27,080 --> 00:19:30,890
ale veľmi ľahko kopírovať a vložiť velenie Valgrind

317
00:19:30,890 --> 00:19:32,650
vidieť, či je nejaké chyby tam.

318
00:19:32,650 --> 00:19:34,820
A bude to ohromujúci zakaždým, keď vidíte výstup,

319
00:19:34,820 --> 00:19:39,430
ale len analyzovať prostredníctvom vizuálne všetok výstup a uvidíme, či vidíte zmieni chýb

320
00:19:39,430 --> 00:19:43,190
alebo varovanie alebo neplatný alebo strate.

321
00:19:43,190 --> 00:19:46,200
Akékoľvek slovo, ktoré znie, ako ste vy podelal niekde.

322
00:19:46,200 --> 00:19:48,580
Takže si uvedomiť, že je to nový nástroj v toolkit.

323
00:19:48,580 --> 00:19:51,270
>> Teraz v pondelok, sme mali veľa ľudí prísť sem

324
00:19:51,270 --> 00:19:53,150
a predstavujú pojem prepojeného zoznamu.

325
00:19:53,150 --> 00:20:00,970
A sme predstavili prepojený zoznam ako riešenie toho, čo problém?

326
00:20:00,970 --> 00:20:04,590
Jo? [Študent odpoveď, nezrozumiteľné] Good.

327
00:20:04,590 --> 00:20:06,530
Pole nemôže mať pamäť a pribudli k nim.

328
00:20:06,530 --> 00:20:09,440
Ak pridelíte pole o veľkosti 10, to je všetko, čo dostanete.

329
00:20:09,440 --> 00:20:13,690
Môžete volať funkcie ako realloc, ak ste pôvodne volal malloc,

330
00:20:13,690 --> 00:20:17,580
a že môže pokúsiť pestovať pole v prípade, že je priestor na jeho konci

331
00:20:17,580 --> 00:20:21,610
že nikto iný používa, a ak nie, bude to len ti nájsť väčší kus niekde inde.

332
00:20:21,610 --> 00:20:25,040
Ale potom to bude kopírovať všetky tie bajtov do nového poľa.

333
00:20:25,040 --> 00:20:28,310
To znie ako veľmi správne riešenie.

334
00:20:28,310 --> 00:20:34,790
Prečo je to neatraktívne?

335
00:20:34,790 --> 00:20:36,940
Myslím, že funguje, ľudia tento problém vyriešil.

336
00:20:36,940 --> 00:20:40,710
Prečo musíme vyriešiť to v pondelok s lineárnymi zoznamy? Jo?

337
00:20:40,710 --> 00:20:44,060
[Študent odpoveď, nezrozumiteľné] To by mohlo trvať dlho.

338
00:20:44,060 --> 00:20:49,260
V skutočnosti, zakaždým, keď voláte malloc alebo realloc alebo calloc, čo je ešte ďalší,

339
00:20:49,260 --> 00:20:52,470
kedykoľvek, program, hovorí do operačného systému,

340
00:20:52,470 --> 00:20:54,310
Máte tendenciu spomaľovať program.

341
00:20:54,310 --> 00:20:57,470
A ak robíte tieto druhy vecí slučiek, ste naozaj spomaľuje veci nadol.

342
00:20:57,470 --> 00:21:00,740
Nebudete si všimnúť to pre najjednoduchšie "Hello World" programy typu,

343
00:21:00,740 --> 00:21:04,300
ale v oveľa väčších programov, požiadal operačný systém znovu a znovu pre pamäte

344
00:21:04,300 --> 00:21:07,520
alebo to, že ho znova a znova nebýva dobrá vec.

345
00:21:07,520 --> 00:21:11,210
Plus, je to len trochu intelektuálne - je to úplná strata času.

346
00:21:11,210 --> 00:21:16,490
Prečo prideliť viac a viac pamäte, riziko kopírovanie všetko do nového poľa,

347
00:21:16,490 --> 00:21:21,980
Ak máte alternatívu, ktorá vám umožní prideliť len toľko pamäte, ako budete skutočne potrebovať?

348
00:21:21,980 --> 00:21:24,130
Takže je tu plusy a mínusy v tu.

349
00:21:24,130 --> 00:21:26,730
Jeden z plusy teraz je, že máme dynamiku.

350
00:21:26,730 --> 00:21:29,100
Nezáleží na tom, kde sa kusy pamäti je, že sú zadarmo,

351
00:21:29,100 --> 00:21:32,070
Môžem len trochu vytvoriť tieto strúhanky cez ukazovatele

352
00:21:32,070 --> 00:21:34,470
na reťazec celú svoju spájať zoznam spoločne.

353
00:21:34,470 --> 00:21:36,470
Ja ale aspoň jednu cenu.

354
00:21:36,470 --> 00:21:40,060
>> Čo mám dať do získavania prepojených zoznamov?

355
00:21:40,060 --> 00:21:42,470
Jo? [Študent odpoveď, nezrozumiteľné] Good.

356
00:21:42,470 --> 00:21:45,650
Potrebujete viac pamäte. Teraz som potrebné priestor pre tieto ukazovatele,

357
00:21:45,650 --> 00:21:47,900
a v prípade, že tento super jednoduchý prepojenom zoznamu

358
00:21:47,900 --> 00:21:51,410
, Ktorý je len pokusu o uložení celočíselné hodnoty, ktoré sú 4 byty, sme stále hovoríš

359
00:21:51,410 --> 00:21:54,240
dobre, ukazovateľ je 4 bajty, takže teraz som doslova zdvojnásobil

360
00:21:54,240 --> 00:21:57,290
množstvo pamäte som potreboval uložiť tento zoznam.

361
00:21:57,290 --> 00:21:59,680
Ale znova, to je konštanta kompromis v informatike

362
00:21:59,680 --> 00:22:03,440
medzi časom a priestorom a vývoj, úsilia a iných zdrojov.

363
00:22:03,440 --> 00:22:06,630
Čo je ďalšia nevýhoda použitia prepojeného zoznamu? Jo?

364
00:22:06,630 --> 00:22:10,150
[Študent odpoveď, nezrozumiteľným]

365
00:22:10,150 --> 00:22:12,600
Dobre. Nie je to tak ľahký prístup. Môžeme už využiť

366
00:22:12,600 --> 00:22:15,530
týždeň 0 zásady ako rozdeľuj a panuj.

367
00:22:15,530 --> 00:22:18,220
A konkrétne, binárne vyhľadávanie. Vzhľadom k tomu, aj keď my ľudia

368
00:22:18,220 --> 00:22:20,400
vidieť hrubo kde uprostred tohto zoznamu je,

369
00:22:20,400 --> 00:22:25,840
počítač iba vie, že to súvisí Zoznam začína na adrese volal ako prvý.

370
00:22:25,840 --> 00:22:28,250
A to je 0x123 alebo niečo také.

371
00:22:28,250 --> 00:22:30,990
A jediný spôsob, ako môže program nájsť strednú prvok

372
00:22:30,990 --> 00:22:33,350
je skutočne hľadať celý zoznam.

373
00:22:33,350 --> 00:22:35,500
A aj potom, doslova sa musí snažiť nájsť celý zoznam, pretože

374
00:22:35,500 --> 00:22:38,950
dokonca akonáhle sa dostanete na strednej prvok podľa nasledujúcich ukazovateľov,

375
00:22:38,950 --> 00:22:42,380
vy, program, nemám potuchy, ako dlho tento zoznam je, prípadne,

376
00:22:42,380 --> 00:22:45,250
kým nenarazíte na koniec toho, a ako viete, programovo

377
00:22:45,250 --> 00:22:48,600
že ste na konci prepojeného zoznamu?

378
00:22:48,600 --> 00:22:51,120
Je tu špeciálna NULL pointer, takže opäť, konvencie.

379
00:22:51,120 --> 00:22:53,870
Skôr než používať tento ukazovateľ, my rozhodne nechceme, aby to bolo nejaké smeti hodnota

380
00:22:53,870 --> 00:22:57,750
smerujúce z pódia niekam, chceme, aby to bolo rúk dole, NULL,

381
00:22:57,750 --> 00:23:01,530
tak, že máme túto terminus v tejto dátovej štruktúre, takže vieme, kde končí.

382
00:23:01,530 --> 00:23:03,410
>> Čo keď budeme chcieť manipulovať toto?

383
00:23:03,410 --> 00:23:05,980
Robili sme väčšinu z tejto vizuálne, a s ľuďmi,

384
00:23:05,980 --> 00:23:07,630
ale čo keď chceme urobiť vkladanie?

385
00:23:07,630 --> 00:23:12,360
Takže pôvodný zoznam bol 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Čo keď sme potom chceli malloc priestoru pre číslo 55, uzol pre to,

387
00:23:16,730 --> 00:23:20,730
a potom chceme vložiť 55 do zoznamu, rovnako ako sme to urobili v pondelok?

388
00:23:20,730 --> 00:23:23,690
Ako to urobíme? No, Anita prišiel a ona v podstate išla zoznam.

389
00:23:23,690 --> 00:23:27,500
Začala na prvý prvok, potom ďalší, ďalší, ďalší, ďalší, ďalší.

390
00:23:27,500 --> 00:23:29,500
Nakoniec zasiahla ľavý celú cestu dole

391
00:23:29,500 --> 00:23:34,480
a uvedomil si, oh, to je NULL. Takže to, čo ukazovateľ manipulácie je potrebné urobiť?

392
00:23:34,480 --> 00:23:37,980
Osoba, ktorá bola na konci, číslo 34, treba jeho ľavá ruka zvýšená

393
00:23:37,980 --> 00:23:46,220
poukázať na 55, 55 potreba ich ľavú ruku smerom dole, že je nový NULL zakončenie. Hotovo.

394
00:23:46,220 --> 00:23:49,540
Celkom ľahko vložiť 55 do triedeného zoznamu.

395
00:23:49,540 --> 00:23:51,800
A ako by to mohlo vyzerať?

396
00:23:51,800 --> 00:23:55,690
>> Nechaj ma ísť napred a otvoriť nejaké príklad kódu tu.

397
00:23:55,690 --> 00:23:58,120
Otvorím sa gedit, a dovoľte mi, aby som otvoriť dva súbory ako prvý.

398
00:23:58,120 --> 00:24:02,050
Jedným z nich je list1.h, a dovoľte mi pripomenúť, že to bol kus kódu

399
00:24:02,050 --> 00:24:04,920
že sme použili pre reprezentáciu uzla.

400
00:24:04,920 --> 00:24:13,040
Uzol má oba int s názvom n a ukazovateľ s názvom ďalší, že len poukazuje na ďalšie veci v zozname.

401
00:24:13,040 --> 00:24:15,450
To je teraz v súbore. H.. Prečo?

402
00:24:15,450 --> 00:24:19,090
Tam je to konvencie, a my sme nevyužili tejto obrovské množstvo sami,

403
00:24:19,090 --> 00:24:22,220
ale ten, kto písal printf a ďalšie funkcie

404
00:24:22,220 --> 00:24:27,150
dal ako darček k svetu všetky tieto funkcie písomne ​​súbor s názvom stdio.h.

405
00:24:27,150 --> 00:24:30,950
A potom je tu string.h, a potom je tu map.h, a tam je všetky tieto h súbory

406
00:24:30,950 --> 00:24:34,410
ktoré ste mohli vidieť alebo používa počas doby napísali inými ľuďmi.

407
00:24:34,410 --> 00:24:38,470
Typicky v tých. H súbory sú len veci, ako typedefs

408
00:24:38,470 --> 00:24:42,310
alebo vyhlásenie užívateľských typov, alebo vyhlásenie konštánt.

409
00:24:42,310 --> 00:24:47,890
Nemusíte dať implementácia funkcie "v hlavičkových súboroch.

410
00:24:47,890 --> 00:24:50,570
Tie, že miesto, len ich prototypy.

411
00:24:50,570 --> 00:24:53,050
Môžete dať veci, ktoré chcete zdieľať s celým svetom, čo potrebujú

412
00:24:53,050 --> 00:24:55,640
na zostavovanie kódu. Takže len sa dostať do tohto zvyku,

413
00:24:55,640 --> 00:24:59,110
sme sa rozhodli urobiť to isté. Nie je toho veľa, v list1.h,

414
00:24:59,110 --> 00:25:02,070
ale my sme dali niečo, čo by vás mohlo zaujímať ľuďom vo svete

415
00:25:02,070 --> 00:25:05,030
ktorí chcú využiť náš spájať zoznam implementáciu.

416
00:25:05,030 --> 00:25:08,040
Teraz, v list1.c, nešiel by som celú túto vec

417
00:25:08,040 --> 00:25:11,390
pretože je to trochu dlhý, tento program, ale poďme spustiť ju v reálnom rýchlo na riadku.

418
00:25:11,390 --> 00:25:15,720
Dovoľte mi, aby som zostaviť Hárok1, dovoľte mi, aby som potom spustiť Hárok1, a to, čo uvidíte je

419
00:25:15,720 --> 00:25:18,070
máme simulované jednoduchý malý program tu

420
00:25:18,070 --> 00:25:20,990
, Čo sa deje, aby mi k pridávanie a odoberanie čísel do zoznamu.

421
00:25:20,990 --> 00:25:24,310
Tak nechaj ma ísť napred a zadajte 3 pre 3 položku menu.

422
00:25:24,310 --> 00:25:27,880
Chcem vložiť číslo - poďme urobiť prvé číslo, ktoré bolo 9,

423
00:25:27,880 --> 00:25:30,550
a teraz som povedal, že zoznam je teraz 9.

424
00:25:30,550 --> 00:25:33,760
Nechaj ma ísť ďalej a urobiť ďalšie vkladanie, takže som narazila menu 3.

425
00:25:33,760 --> 00:25:36,760
Aké číslo si chcem vložiť? 17.

426
00:25:36,760 --> 00:25:39,220
Enter. A ja urobím len jeden.

427
00:25:39,220 --> 00:25:41,720
Dovoľte mi, aby som vložiť číslo 22.

428
00:25:41,720 --> 00:25:45,850
Takže máme začiatky prepojeného zoznamu, ktorý sme mali v prezentácii formou pred chvíľou.

429
00:25:45,850 --> 00:25:48,740
Ako je táto vloženie vlastne deje?

430
00:25:48,740 --> 00:25:52,000
Vskutku, 22 je teraz na konci zoznamu.

431
00:25:52,000 --> 00:25:55,050
Takže príbeh sme si povedali na pódiu v pondelok a zhrňme teraz

432
00:25:55,050 --> 00:25:57,460
musí byť skutočne deje v kóde.

433
00:25:57,460 --> 00:25:59,700
Poďme sa pozrieť. Dovoľte mi, aby som posunúť nadol v tomto súbore.

434
00:25:59,700 --> 00:26:01,720
Budeme zakrývať niektoré z funkcií,

435
00:26:01,720 --> 00:26:05,630
ale pôjdeme dole, povedzme, vložka funkcie.

436
00:26:05,630 --> 00:26:11,720
>> Poďme sa pozrieť, ako ísť o vloženie nového uzla do tohto prepojeného zoznamu.

437
00:26:11,720 --> 00:26:14,550
Ak je zoznam vyhlásil? Dobre, poďme posunúť celú cestu až na vrchol,

438
00:26:14,550 --> 00:26:19,970
a všimnite si, že moja spájať zoznam je v podstate deklarovaný ako jediný ukazovateľ, ktorý je pôvodne NULL.

439
00:26:19,970 --> 00:26:23,180
Takže som pomocou globálne premenné, ktorá sem všeobecne sme hlásali proti

440
00:26:23,180 --> 00:26:25,280
pretože to robí váš kód trochu chaotický zachovať,

441
00:26:25,280 --> 00:26:29,080
je to trochu lenivý, zvyčajne, ale to nie je lenivý, a to nie je nič zlého, a to nie je zlé

442
00:26:29,080 --> 00:26:33,660
Ak váš program je jediným cieľom v živote je simulovať jeden z prepojených zoznam.

443
00:26:33,660 --> 00:26:35,460
Čo je presne to, čo robíme.

444
00:26:35,460 --> 00:26:39,100
Takže skôr ako toto uviesť v hlavnej a potom ju odovzdať každému funkciu

445
00:26:39,100 --> 00:26:42,640
písali sme v tomto programe, sa namiesto toho si uvedomiť, oh, poďme robiť to globálny

446
00:26:42,640 --> 00:26:47,060
pretože celý účel tohto programu je demonštrovať jeden a iba jeden spájať zoznam.

447
00:26:47,060 --> 00:26:50,700
Tak, že sa cíti v poriadku. Tu sú moje prototypy, a nebudeme prejsť všetky z nich,

448
00:26:50,700 --> 00:26:55,800
ale napísal som funkciu odstránenie, a nájsť funkciu, insert funkcie, a funkcie pojazdu.

449
00:26:55,800 --> 00:26:59,080
Ale poďme sa teraz vrátiť dole do vložky funkciu

450
00:26:59,080 --> 00:27:01,490
a uvidíte, ako to funguje tu.

451
00:27:01,490 --> 00:27:09,940
Vložiť je on-line - ideme na to.

452
00:27:09,940 --> 00:27:12,850
Vložiť. Takže to neberie žiadne argumenty, pretože sme sa opýtať,

453
00:27:12,850 --> 00:27:15,930
užívateľ vnútri tejto funkcie vzhľadom k počtu chcú vložiť.

454
00:27:15,930 --> 00:27:19,410
Ale najprv musíme pripraviť dať im nejaký priestor.

455
00:27:19,410 --> 00:27:22,050
To je druh kopírovanie a vkladanie z iných príklade.

456
00:27:22,050 --> 00:27:25,110
V tomto prípade sme boli pridelení int, tentoraz sme pridelenie uzol.

457
00:27:25,110 --> 00:27:27,910
Naozaj neviem, koľko som ich bytov uzol je, ale to je v poriadku.

458
00:27:27,910 --> 00:27:30,460
Sizeof môže prísť, že pre mňa.

459
00:27:30,460 --> 00:27:33,340
A prečo som kontrolu na NULL v súlade 120?

460
00:27:33,340 --> 00:27:37,530
Čo sa môže pokaziť v súlade 119? Jo?

461
00:27:37,530 --> 00:27:40,530
[Študent odpoveď, nezrozumiteľným]

462
00:27:40,530 --> 00:27:43,440
Dobre. Len by mohol byť prípad, že som požiadal o príliš veľa pamäte

463
00:27:43,440 --> 00:27:47,020
alebo tak niečo nie je v poriadku, a operačný systém nemá dostatok bytov, ktoré by zabezpečili ma,

464
00:27:47,020 --> 00:27:50,640
tak to signalizuje, ako moc tým, že vráti NULL, a keď nemám kontrolu, že

465
00:27:50,640 --> 00:27:54,710
a ja len slepo pokračovať používať adresy, ktorú vráti, mohlo by to byť NULL.

466
00:27:54,710 --> 00:27:58,400
Mohlo by to byť nejaký neznámy hodnota, nie je dobrá vec, ak I -

467
00:27:58,400 --> 00:28:00,590
vlastne nebude neznáma hodnota. Mohlo by to byť NULL, takže nechcem

468
00:28:00,590 --> 00:28:02,550
zneužívať ju a riskovať dereferencing ju.

469
00:28:02,550 --> 00:28:07,410
Ak sa to stane, len som sa vrátiť a my vám predstierať, že som sa nedostal staré nejakú spomienku vôbec.

470
00:28:07,410 --> 00:28:12,270
>> Inak, poviem užívateľ mi číslo vložiť, hovorím náš starý priateľ GetInt,

471
00:28:12,270 --> 00:28:15,530
a potom to bolo nové syntaxe sme predstavili v pondelok.

472
00:28:15,530 --> 00:28:20,320
"Newptr-> n" znamená mať adresu, ktorú ste dostali od malloc

473
00:28:20,320 --> 00:28:23,490
ktorá predstavuje prvý bajt nového uzla objektu,

474
00:28:23,490 --> 00:28:26,860
a potom ísť na pole s názvom n

475
00:28:26,860 --> 00:28:35,270
Trochu Trivia Otázka: Jedná sa o ekvivalent toho, čo viac kryptické riadok kódu?

476
00:28:35,270 --> 00:28:38,110
Ako inak by som napísal toto? Chcete, aby sa bodnúť?

477
00:28:38,110 --> 00:28:41,480
[Študent odpoveď, nezrozumiteľným]

478
00:28:41,480 --> 00:28:44,870
Dobre. Pomocou. N, ale nie je to tak jednoduché, ako to.

479
00:28:44,870 --> 00:28:47,090
Čo som sa po prvýkrát robiť? [Študent odpoveď, nezrozumiteľným]

480
00:28:47,090 --> 00:28:52,730
Dobre. Musím urobiť * newptr.n.

481
00:28:52,730 --> 00:28:55,610
Tak to hovorí nový ukazovateľ je samozrejme adresa. Prečo?

482
00:28:55,610 --> 00:28:59,520
Vzhľadom k tomu, že bola vrátená malloc. * Newptr hovoriť "tam,"

483
00:28:59,520 --> 00:29:02,970
a potom raz si tam, potom môžete použiť na viac známou. n,

484
00:29:02,970 --> 00:29:05,730
ale to len vyzerá trochu škaredá, najmä ak my ľudia budú

485
00:29:05,730 --> 00:29:10,360
kresliť ukazovatele s šípkami po celú dobu, svet má normalizované na tomto arrow zápisu,

486
00:29:10,360 --> 00:29:12,320
ktorý robí presne to isté.

487
00:29:12,320 --> 00:29:16,070
Takže môžete používať iba -> notáciu, kedy vec na ľavej strane je ukazovateľ.

488
00:29:16,070 --> 00:29:18,790
V opačnom prípade, ak je to skutočný struct, použite. N.

489
00:29:18,790 --> 00:29:25,800
A potom: Prečo som inicializovať newptr-> vedľa NULL?

490
00:29:25,800 --> 00:29:28,610
Nechceme sa klátící ľavú ruku preč konca etapy.

491
00:29:28,610 --> 00:29:31,630
Chceme, aby to smeruje priamo nadol, čo znamená koniec tohto zoznamu

492
00:29:31,630 --> 00:29:34,980
by mohla byť v tomto uzle, takže lepšie sa uistite, že je NULL.

493
00:29:34,980 --> 00:29:38,460
A všeobecne, inicializácia svoje premenné alebo dátové členmi a structs

494
00:29:38,460 --> 00:29:40,470
na niečo je jednoducho dobré praxe.

495
00:29:40,470 --> 00:29:45,170
Len nájom odpadky existujú a naďalej trvajú zvyčajne dostane do problémov

496
00:29:45,170 --> 00:29:48,650
ak ste zabudli niečo neskôr.

497
00:29:48,650 --> 00:29:51,590
>> Tu je niekoľko prípadov. To je opäť vložka funkcie,

498
00:29:51,590 --> 00:29:54,930
a prvá vec, ktorú som skontrolovať, ak je premenná najskôr zavolať,

499
00:29:54,930 --> 00:29:58,240
že globálna premenná NULL, to znamená, že nie je spájať zoznam.

500
00:29:58,240 --> 00:30:02,460
Sme nie je vložená žiadna čísla, takže je to triviálne vložiť toto aktuálne číslo

501
00:30:02,460 --> 00:30:05,240
do zoznamu, pretože to jednoducho patrí na začiatku zoznamu.

502
00:30:05,240 --> 00:30:08,100
Takže to bolo, keď Anita práve stál tu sám, predstierať

503
00:30:08,100 --> 00:30:11,390
nikto iný tu na javisku, kým sme pridelené uzol,

504
00:30:11,390 --> 00:30:13,940
potom mohla zdvihnúť ruku prvýkrát,

505
00:30:13,940 --> 00:30:17,420
ak všetci ostatní prišli na pódium za ňou v pondelok.

506
00:30:17,420 --> 00:30:22,900
Teraz je tu, je to trochu šek, kde musím povedať, či nový uzol je hodnota n

507
00:30:22,900 --> 00:30:27,370
je <hodnotu n v aktuálnej prvom uzla,

508
00:30:27,370 --> 00:30:29,930
to znamená, že je prepojený zoznam, ktorý ich začal.

509
00:30:29,930 --> 00:30:32,330
Tam je aspoň jeden uzol v zozname, ale tento nový chlap

510
00:30:32,330 --> 00:30:37,230
patrí pred, takže musíme presunúť veci okolo.

511
00:30:37,230 --> 00:30:43,450
Inými slovami, v prípade, že zoznam bol zahájený len s, povedzme,

512
00:30:43,450 --> 00:30:48,100
len číslo 17, to je - vlastne, môžeme to urobiť jasnejšie.

513
00:30:48,100 --> 00:30:56,010
Ak začneme náš príbeh s ukazovateľom tu volal ako prvý,

514
00:30:56,010 --> 00:30:59,870
a spočiatku je to NULL, a vložíme číslo 9,

515
00:30:59,870 --> 00:31:02,510
číslo 9 jasne patrí na začiatku zoznamu.

516
00:31:02,510 --> 00:31:07,400
Takže poďme predstierať, že sme len malloced adresu alebo číslo 9 a dať ho sem.

517
00:31:07,400 --> 00:31:13,170
Ak prvá je 9 štandardne, prvý scenár diskutovalo sa rozumie Poďme bod ten chlap tu,

518
00:31:13,170 --> 00:31:15,790
nechajte to ako NULL, teraz máme číslo 9.

519
00:31:15,790 --> 00:31:18,280
Ďalšie číslo chceme vložiť, je 17.

520
00:31:18,280 --> 00:31:22,420
17 patrí sem, takže budeme musieť urobiť nejaký logický krokovanie cez to.

521
00:31:22,420 --> 00:31:26,060
Takže poďme miesto, ako to urobíme, poďme predstierať, že sme chceli vložiť číslo 8.

522
00:31:26,060 --> 00:31:28,650
>> Tak práve pre pohodlie boží, budem kresliť tu.

523
00:31:28,650 --> 00:31:30,760
Ale nezabudnite, že malloc dá to najviac kdekoľvek.

524
00:31:30,760 --> 00:31:33,460
Ale pre výkresu záujmu, dám to sem.

525
00:31:33,460 --> 00:31:38,440
Takže predstierať, že som práve pridelené uzol pre číslo 8, je to NULL v predvolenom nastavení.

526
00:31:38,440 --> 00:31:42,800
Čo teraz musí stať? Pár vecí.

527
00:31:42,800 --> 00:31:47,090
Urobili sme túto chybu na javisku v pondelok, kedy sme aktualizovali ukazovateľ, ako je tento,

528
00:31:47,090 --> 00:31:51,890
potom to urobil, a potom sme tvrdili - sme osamotené všetky ostatné na javisku.

529
00:31:51,890 --> 00:31:54,350
Pretože ste nemôžeš - poradie operácií tu je dôležité,

530
00:31:54,350 --> 00:31:58,760
pretože teraz sme stratili túto uzla 9, ktorý je len trochu vznáša v priestore.

531
00:31:58,760 --> 00:32:01,150
Takže to nie je správny prístup v pondelok.

532
00:32:01,150 --> 00:32:03,330
Musíme najprv urobiť niečo iné.

533
00:32:03,330 --> 00:32:06,280
Stav sveta vyzerá. Pôvodne sa 8 bola pridelená.

534
00:32:06,280 --> 00:32:10,550
Čo by to bolo lepší spôsob, ako vkladanie 8?

535
00:32:10,550 --> 00:32:14,720
Namiesto aktualizácia tento ukazovateľ ako prvý, len aktualizovať túto tu miesto.

536
00:32:14,720 --> 00:32:17,720
Takže potrebujeme riadok kódu, ktorý sa deje, aby túto NULL znak

537
00:32:17,720 --> 00:32:22,020
do skutočného ukazovateľ, ktorý sa ukazuje na uzol 9,

538
00:32:22,020 --> 00:32:27,970
a potom môžeme bezpečne meniť najprv poukázať na toho chlapa tu.

539
00:32:27,970 --> 00:32:31,330
Teraz máme zoznam, súvisí zoznam, z dvoch prvkov.

540
00:32:31,330 --> 00:32:33,580
A čo to vlastne vyzerá tu?

541
00:32:33,580 --> 00:32:36,900
Ak sa pozrieme na kód, zistíte, že som urobil presne to.

542
00:32:36,900 --> 00:32:41,970
Povedal som newptr, a v tomto príbehu, newptr mieril na toho chalana.

543
00:32:41,970 --> 00:32:45,520
>> Dovoľte mi teda čerpať ešte jednu vec, a ja som mal nechať trochu väčší priestor pre to.

544
00:32:45,520 --> 00:32:48,540
Takže odpustiť malinkú výkresu.

545
00:32:48,540 --> 00:32:52,140
Ten chlap sa volá newptr.

546
00:32:52,140 --> 00:32:57,940
To je premenná je deklarovaná niekoľko riadkov predtým, v súlade - tesne nad 25 rokov.

547
00:32:57,940 --> 00:33:03,430
A to ukazuje na 8. Takže keď hovorím newptr-> next, to znamená, že ísť do struct

548
00:33:03,430 --> 00:33:07,910
, Ktorá je momentálne ukázal na o newptr, takže sme tu, tam.

549
00:33:07,910 --> 00:33:13,990
Potom šípka hovorí získať ďalšie pole, a potom = hovorí kladený aké hodnoty tam?

550
00:33:13,990 --> 00:33:17,280
Hodnota, ktorá bola v prvej, čo hodnota bola prvá?

551
00:33:17,280 --> 00:33:21,930
Prvý ukazoval na tento uzol, tak to znamená, že by to malo teraz ukazujú v tomto uzle.

552
00:33:21,930 --> 00:33:25,660
Inými slovami, to, čo vyzerá hoci smiešne si s mojím rukopisom,

553
00:33:25,660 --> 00:33:28,620
Čo je jednoduchý nápad len pohybujúce sa tieto šípky okolo

554
00:33:28,620 --> 00:33:31,560
prekladá kód s len tento jeden vložky.

555
00:33:31,560 --> 00:33:38,110
Skladujte čo je v prvý v ďalšom poli a potom aktualizovať, čo najprv vlastne je.

556
00:33:38,110 --> 00:33:40,900
Poďme ďalej a rýchlo prechádzať niektoré z týchto,

557
00:33:40,900 --> 00:33:44,220
a pozrieť sa len na tomto chvosta vloženie do teraz.

558
00:33:44,220 --> 00:33:51,210
Predpokladám, že som sa dostať do bodu, kedy som nájsť, že budúci poľa nejakého uzla je NULL.

559
00:33:51,210 --> 00:33:53,410
A v tomto okamihu v príbehu, detail, že som úmyselne cez

560
00:33:53,410 --> 00:33:58,170
je, že som zaviedla ďalšie ukazovateľ sa tu v súlade 142, predchodca ukazovatele.

561
00:33:58,170 --> 00:34:01,320
V podstate, v tomto bode v príbehu, akonáhle zoznam dostane dlhý,

562
00:34:01,320 --> 00:34:04,800
Tak nejako som potrebné chodiť s dvoma prstami, pretože keď som ísť príliš ďaleko,

563
00:34:04,800 --> 00:34:08,219
pamätať v single-dĺžka zoznamu, nemôžete ísť späť.

564
00:34:08,219 --> 00:34:13,659
Takže táto predstava predptr je môj ľavý prst, a newptr - nie newptr.

565
00:34:13,659 --> 00:34:17,199
Ďalšie ukazovateľ, ktorý je tu, je môj druhý prst, a ja som to jednoducho chôdzu zoznamu.

566
00:34:17,199 --> 00:34:22,179
To je dôvod, prečo, že existuje. Ale poďme brať do úvahy len jeden z jednoduchších prípadoch tu.

567
00:34:22,179 --> 00:34:26,620
Ak tento ukazovateľ je ďalšie pole NULL, čo je logické dôsledky?

568
00:34:26,620 --> 00:34:30,840
Ak sa prekračovať tento zoznam a stlačíte ukazovateľ NULL?

569
00:34:30,840 --> 00:34:35,780
Ste na konci zoznamu, a tak kód sa potom pripojí tento jeden ďalší prvok

570
00:34:35,780 --> 00:34:41,230
je druh intuitívne bude tento uzol, ktorého ďalší ukazovateľ je NULL,

571
00:34:41,230 --> 00:34:46,120
tak to je v súčasnej dobe NULL, a zmeniť to, hoci, byť adresa nového uzla.

572
00:34:46,120 --> 00:34:52,260
Takže my sme len kreslenie v kóde na šípku, ktorá sme vychádzali na javisku zvýšenie niečí ľavú ruku.

573
00:34:52,260 --> 00:34:54,070
>> A v prípade, že budem mávať rukami na teraz,

574
00:34:54,070 --> 00:34:58,020
len preto, že si myslím, že je to ľahké sa stratiť, keď to robíme v tomto druhu prostredia,

575
00:34:58,020 --> 00:35:00,600
je kontrola vkladania do zoznamu je uprostred.

576
00:35:00,600 --> 00:35:03,220
Ale len intuitívne, čo sa musí stať, ak chcete zistiť,

577
00:35:03,220 --> 00:35:06,600
kde nejaké číslo patrí v stredu, je to, chodiť ho

578
00:35:06,600 --> 00:35:09,510
s viac ako jedným prstom, viac ako jeden ukazovateľ,

579
00:35:09,510 --> 00:35:12,920
zistiť, kam patrí podľa kontroly je element <prúd jeden,

580
00:35:12,920 --> 00:35:15,450
> Aktuálne jeden, a akonáhle zistíte, že miesto,

581
00:35:15,450 --> 00:35:20,400
potom budete musieť urobiť tento druh hazardnú hru, kde si presunúť ukazovatele okolo veľmi starostlivo.

582
00:35:20,400 --> 00:35:23,850
A tá odpoveď, ak by ste chceli, aby z dôvodu cez to doma na vlastnú päsť,

583
00:35:23,850 --> 00:35:28,340
scvrkáva len na tieto dva riadky kódu, ale poradie týchto riadkov je super dôležité.

584
00:35:28,340 --> 00:35:31,390
Pretože ak pustíte niekoho za ruku a zvýšiť niekoho iného v nesprávnom poradí,

585
00:35:31,390 --> 00:35:34,580
znova, môžete skončiť orphaning zoznam.

586
00:35:34,580 --> 00:35:39,500
Aby sme to zhrnuli viac koncepčne, vloženie na chvoste je pomerne jednoduché.

587
00:35:39,500 --> 00:35:42,940
Vloženie v čele je tiež pomerne jednoduché,

588
00:35:42,940 --> 00:35:45,580
ale budete musieť aktualizovať dodatočnú kurzora tentoraz

589
00:35:45,580 --> 00:35:47,930
stlačiť číslo 5 do zoznamu tu,

590
00:35:47,930 --> 00:35:51,560
a potom vloženie do stredu zahŕňa ešte viac úsilia,

591
00:35:51,560 --> 00:35:56,130
veľmi opatrne vložte číslo 20 vo svojom správnom mieste,

592
00:35:56,130 --> 00:35:58,350
ktorý je medzi 17 a 22.

593
00:35:58,350 --> 00:36:02,700
Takže budete musieť urobiť niečo ako majú nový uzol 20 bod 22,

594
00:36:02,700 --> 00:36:08,470
a potom, ktorý uzol je ukazovateľ musí byť naposledy aktualizovaný?

595
00:36:08,470 --> 00:36:10,630
Je to 17, skutočne vložiť ju.

596
00:36:10,630 --> 00:36:14,080
Takže znovu, budem odložiť skutočný kód pre túto konkrétnu implementáciu.

597
00:36:14,080 --> 00:36:17,280
>> Na prvý pohľad je to trochu ohromujúci, ale je to naozaj len nekonečné slučky

598
00:36:17,280 --> 00:36:21,770
že je opakovanie, opakovanie, opakovanie, opakovanie, a lámaniu akonáhle narazí na ukazovateľ NULL,

599
00:36:21,770 --> 00:36:24,590
na ktorom mieste si môžete urobiť potrebné vloženie.

600
00:36:24,590 --> 00:36:30,960
To je teda reprezentatívna spájať zoznam vloženie kódu.

601
00:36:30,960 --> 00:36:34,590
To bolo celkom veľa, a je to ako sme vyriešili jeden problém,

602
00:36:34,590 --> 00:36:36,940
ale sme zaviedli celú druhú. Úprimne povedané, sme strávili celý čas

603
00:36:36,940 --> 00:36:40,540
na veľké O a Ω a beží čas, snažia sa riešiť problémy rýchlejšie,

604
00:36:40,540 --> 00:36:43,270
a tu sme urobili veľký krok späť, je to pocit.

605
00:36:43,270 --> 00:36:45,380
A ešte, v prípade, že cieľom je ukladanie dát,

606
00:36:45,380 --> 00:36:48,010
to je ako svätý grál, ako sme povedali v pondelok, by bolo naozaj

607
00:36:48,010 --> 00:36:50,470
uložiť veci okamžite.

608
00:36:50,470 --> 00:36:53,930
>> V skutočnosti, predpokladám, že sme dať stranou spájať zoznam na chvíľu

609
00:36:53,930 --> 00:36:56,000
a my sme namiesto toho zaviedol pojem tabuľky.

610
00:36:56,000 --> 00:36:59,110
A povedzme, že z tabuľky na chvíľu ako pole.

611
00:36:59,110 --> 00:37:03,790
Toto pole a tento prípad tu má asi 26 prvkov, 0 až 25,

612
00:37:03,790 --> 00:37:07,940
a predpokladám, že ste potreboval nejakú kus pamäte pre názvy:

613
00:37:07,940 --> 00:37:10,350
Alice a Bob a Charlie a podobne.

614
00:37:10,350 --> 00:37:12,880
A budete potrebovať nejaké dátové štruktúry pre uloženie týchto mien.

615
00:37:12,880 --> 00:37:15,000
No, môžete použiť niečo ako prepojeného zoznamu

616
00:37:15,000 --> 00:37:20,260
a môžete ísť na zoznam vkladanie Alicu pred Bobom a Charlie po Bobovi a tak ďalej.

617
00:37:20,260 --> 00:37:23,850
A v skutočnosti, ak chcete vidieť kód, ako že stranou,

618
00:37:23,850 --> 00:37:27,230
vedieť, že v list2.h, robíme presne to.

619
00:37:27,230 --> 00:37:30,610
Nebudeme ísť cez tento kód, ale to je varianta prvý príklad

620
00:37:30,610 --> 00:37:34,640
, Ktorá zavádza jednu ďalšiu struct sme videli pred tzv študenta,

621
00:37:34,640 --> 00:37:40,330
a potom to, čo skutočne ukladá v prepojenom zozname je ukazovateľ na štruktúru študentov

622
00:37:40,330 --> 00:37:44,520
skôr než jednoduchý malý celé číslo, n

623
00:37:44,520 --> 00:37:46,900
Takže si uvedomujem, že je kód tam, že sa týka skutočnej reťazca,

624
00:37:46,900 --> 00:37:49,940
ale ak cieľ po ruke naozaj je teraz riešiť účinnosť problém,

625
00:37:49,940 --> 00:37:53,380
Nebolo by pekné, keby sme rovnako objekt nazvaný Alice,

626
00:37:53,380 --> 00:37:56,020
chceme, aby ju do správnej polohy v dátovej štruktúry,

627
00:37:56,020 --> 00:37:58,860
to cítia sa ako, že by bolo naozaj pekné len dať Alicu,

628
00:37:58,860 --> 00:38:01,180
ktorého meno začína v prvom mieste.

629
00:38:01,180 --> 00:38:05,270
A Bob, ktorého meno začína B, v druhom mieste.

630
00:38:05,270 --> 00:38:09,580
S radom, alebo začnime nazývať to tabuľku, hash tabuľka na to,

631
00:38:09,580 --> 00:38:13,650
môžeme robiť presne to. Ak sme dostali meno ako Alice,

632
00:38:13,650 --> 00:38:16,700
reťazec ako Alenka, kde si môžete dať-l-i-c-e?

633
00:38:16,700 --> 00:38:20,540
Potrebujeme hueristic. Musíme funkciu, aby sa nejaký vstup, ako Alice

634
00:38:20,540 --> 00:38:24,610
a vráti odpoveď, "Put Alicu na tomto mieste."

635
00:38:24,610 --> 00:38:28,720
A táto funkcia, to čierna skrinka, sa bude nazývaný hašovacia funkcia.

636
00:38:28,720 --> 00:38:32,330
>> Hash funkcia je niečo, čo sa vstup, rovnako ako "Alice",

637
00:38:32,330 --> 00:38:38,080
a vráti sa do teba, zvyčajne číselná umiestnenie v nejakom dátové štruktúry, kde Alice patrí.

638
00:38:38,080 --> 00:38:40,830
V tomto prípade by mal náš hashovacie funkcie bude pomerne jednoduché.

639
00:38:40,830 --> 00:38:47,510
Naša hash funkcia by mala povedať, ak ste rovnako "Alice", ktorý znak mám starať o?

640
00:38:47,510 --> 00:38:55,660
Prvý z nich. Tak som sa pozrieť na [0], a potom som povedal, ak [0] znak, vráti číslo 0.

641
00:38:55,660 --> 00:39:01,130
Ak je to B, vráti 1. Ak je to C, vráti 2, a tak ďalej.

642
00:39:01,130 --> 00:39:05,940
Všetko 0 index, a že by mi umožnilo vložiť Alicu a potom Bob a potom Charlie a tak ďalej

643
00:39:05,940 --> 00:39:10,960
do tejto dátovej štruktúry. Ale je tu problém.

644
00:39:10,960 --> 00:39:13,060
Čo keď Anita príde znova?

645
00:39:13,060 --> 00:39:17,510
Kam dáme Anita? Jej meno, tiež začína písmenom A,

646
00:39:17,510 --> 00:39:20,330
a to pocit, ako by sme urobili ešte väčší neporiadok tohto problému.

647
00:39:20,330 --> 00:39:24,380
V súčasnej dobe máme okamžitý vloženie, konštantný čas vloženia, do dátovej štruktúry

648
00:39:24,380 --> 00:39:27,100
skôr než horšom prípadu lineárne,

649
00:39:27,100 --> 00:39:29,510
ale čo môžeme robiť s Anitou v tomto prípade?

650
00:39:29,510 --> 00:39:34,110
Aké sú dve možnosti, naozaj? Jo?

651
00:39:34,110 --> 00:39:37,410
[Študent odpoveď, nezrozumiteľné] Dobre, takže sme mohli mať ďalší rozmer.

652
00:39:37,410 --> 00:39:42,320
To je dobre. Takže môžeme stavať veci v 3D, ako sme hovorili o slovne v pondelok.

653
00:39:42,320 --> 00:39:46,700
Mohli by sme pridať ďalší prístup sem, ale predpokladám, že nie, ja sa snažím, aby to jednoduché.

654
00:39:46,700 --> 00:39:50,160
Celá cieľom je mať okamžitý konštantný-time prístup,

655
00:39:50,160 --> 00:39:52,170
tak, aby sa pridaním príliš veľa zložitosť.

656
00:39:52,170 --> 00:39:55,970
Aké sú ďalšie možnosti, keď sa snaží vložiť Anitu do tejto dátovej štruktúry? Jo?

657
00:39:55,970 --> 00:39:58,610
[Študent odpoveď, nezrozumiteľné] Good. Takže sme mohli pohybovať všetci ostatní dole,

658
00:39:58,610 --> 00:40:03,040
ako Charlie štuchanec dole Bob a Alice, a potom sme dali Anita, kde naozaj chce byť.

659
00:40:03,040 --> 00:40:05,660
>> Samozrejme, teraz, tu vedľajší efekt tohto.

660
00:40:05,660 --> 00:40:09,000
Táto dátová štruktúra je pravdepodobne užitočné nie preto, že chceme vložiť ľudí raz

661
00:40:09,000 --> 00:40:11,250
ale preto, že chceme, aby zistili, či v prípade, že to tam neskôr

662
00:40:11,250 --> 00:40:13,600
Ak chceme vytlačiť všetky názvy v dátovej štruktúre.

663
00:40:13,600 --> 00:40:15,850
Budeme robiť niečo s týmito dátami nakoniec.

664
00:40:15,850 --> 00:40:20,810
Takže teraz máme takú zoskrutkované cez Alice, ktorý je už tam, kde je jej má byť.

665
00:40:20,810 --> 00:40:23,880
Ani je Bob, ani Charlie.

666
00:40:23,880 --> 00:40:26,060
Takže možno to nie je tak dobrý nápad.

667
00:40:26,060 --> 00:40:28,830
Ale naozaj, to je jedna možnosť. Mohli by sme posunúť všetky dole,

668
00:40:28,830 --> 00:40:32,240
alebo sakra, Anita prišiel neskoro do hry, prečo nie my len dať Anita

669
00:40:32,240 --> 00:40:35,870
nie tu, nie tu, nie tu, poďme dať ju trochu nižšie v zozname.

670
00:40:35,870 --> 00:40:38,680
Ale potom tento problém začne preniesť znova.

671
00:40:38,680 --> 00:40:41,630
Môžete byť schopní nájsť Alice okamžite, na základe jej krstného mena.

672
00:40:41,630 --> 00:40:44,320
A Bob okamžite, a Charlie. Ale potom sa pozriete na Anita,

673
00:40:44,320 --> 00:40:46,360
a uvidíte, hmm, Alice stojí v ceste.

674
00:40:46,360 --> 00:40:48,770
No, dovoľte mi, aby som skontrolovať nižšie Alice. Bob nie je Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie nie je Anita. Oh, tam je Anita.

676
00:40:51,850 --> 00:40:54,720
A ak budete pokračovať, že vlak logiky celú cestu,

677
00:40:54,720 --> 00:41:00,690
čo je najhoršie doba chodu nájsť alebo vložením Anitu do tejto novej dátovej štruktúry?

678
00:41:00,690 --> 00:41:03,280
Je to O (n), že jo?

679
00:41:03,280 --> 00:41:06,280
Vzhľadom k tomu, v najhoršom prípade je to Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
celú cestu dole do niekoho menom "Y", takže je tu len jedno miesto doľava.

681
00:41:10,150 --> 00:41:13,950
Našťastie, nemáme s názvom "Z", takže dáme Anitu na samom dne.

682
00:41:13,950 --> 00:41:16,040
>> My sa naozaj vyriešiť tento problém.

683
00:41:16,040 --> 00:41:19,890
Takže možno naozaj musíme zaviesť tento tretí rozmer.

684
00:41:19,890 --> 00:41:22,230
A ukázalo sa, ak sa nám predstaví tento tretí rozmer,

685
00:41:22,230 --> 00:41:25,240
môžeme to urobiť dokonale, ale svätý grál sa bude stále

686
00:41:25,240 --> 00:41:28,370
konštantný čas vloženie a dynamické vložky tak, aby

687
00:41:28,370 --> 00:41:30,960
nemáme na pevný kód poľa veľkosti 26.

688
00:41:30,960 --> 00:41:34,400
Môžeme vložiť toľko mien, ako chceme, ale poďme sa náš 5-minút prestávku tu

689
00:41:34,400 --> 00:41:38,790
a potom to, že správne.

690
00:41:38,790 --> 00:41:46,020
Dobrá. Nastavil som ten príbeh pekne umelo tam

691
00:41:46,020 --> 00:41:48,670
výberom Alicu a potom Bob a potom Charlie a potom Anita,

692
00:41:48,670 --> 00:41:51,000
ktorého meno bolo zrejme bude kolidovat s Alicou.

693
00:41:51,000 --> 00:41:54,120
Ale otázka, ktorú sme skončila v pondelok, je, ako pravdepodobné je, že

694
00:41:54,120 --> 00:41:56,370
že by ste si tieto druhy kolízií? Inými slovami,

695
00:41:56,370 --> 00:42:00,490
ak začneme používať tento tabuľkový štruktúru, ktorá je naozaj len pole,

696
00:42:00,490 --> 00:42:02,460
v tomto prípade z 26 miest,

697
00:42:02,460 --> 00:42:05,740
čo keď naše vstupy miesto rovnomerne rozložené?

698
00:42:05,740 --> 00:42:09,620
Nie je to umelo Alice a Bob a Charlie a David, a tak ďalej abecedne,

699
00:42:09,620 --> 00:42:12,380
to rovnomerne rozložených do Z.

700
00:42:12,380 --> 00:42:15,220
>> Možno budeme mať šťastie a jednoducho nebudeme mať dva takéto alebo dve dvojky

701
00:42:15,220 --> 00:42:17,640
s veľmi vysokou pravdepodobnosťou, ale ako niekto poukázal,

702
00:42:17,640 --> 00:42:20,730
ak by sme generalizované tento problém a čo nerobiť 0-25

703
00:42:20,730 --> 00:42:26,060
ale, povedať, 0 až 364 alebo 65, často sa počet dní v typickom roku

704
00:42:26,060 --> 00:42:31,170
a pýtal sa: "Čo je to pravdepodobnosť, že dvaja z nás v tejto miestnosti majú narodeniny v rovnaký deň?"

705
00:42:31,170 --> 00:42:34,600
Inak povedané, to, čo je pravdepodobnosť, že dvaja z nás má meno začínajúce?

706
00:42:34,600 --> 00:42:37,190
Radenie otázky je rovnaká, ale tento adresný priestor,

707
00:42:37,190 --> 00:42:39,940
Tento priestor hľadanie, je väčšie v prípade narodenín,

708
00:42:39,940 --> 00:42:42,820
pretože máme toľko viac dní v roku, než písmen v abecede.

709
00:42:42,820 --> 00:42:44,910
Čo je pravdepodobnosť kolízie?

710
00:42:44,910 --> 00:42:48,410
No, môžeme myslieť na to by prísť na matematiku na opačnú stranu.

711
00:42:48,410 --> 00:42:50,580
Čo je pravdepodobnosť žiadne kolízie?

712
00:42:50,580 --> 00:42:53,970
No, tento výraz tu hovorí, že to, čo je pravdepodobnosť

713
00:42:53,970 --> 00:42:58,770
ak tam je len jedna osoba v tejto miestnosti, že majú jedinečnú narodeniny?

714
00:42:58,770 --> 00:43:01,190
Je to 100%. Pretože v prípade, že je len jedna osoba v izbe,

715
00:43:01,190 --> 00:43:03,940
jeho alebo jej narodeniny môže byť ktorýkoľvek z 365 dní z roka.

716
00:43:03,940 --> 00:43:08,650
Takže 365/365 Možnosti mi dáva hodnotu 1.

717
00:43:08,650 --> 00:43:11,250
Takže pravdepodobnosť ide v súčasnej dobe je len 1.

718
00:43:11,250 --> 00:43:13,270
Ale v prípade, že je druhá osoba v izbe,

719
00:43:13,270 --> 00:43:16,490
Čo je pravdepodobnosť, že ich narodeniny sa líšia?

720
00:43:16,490 --> 00:43:20,680
Je tu len 364 možných dni, ignorovanie prestupných rokov,

721
00:43:20,680 --> 00:43:23,580
k narodeninám, aby sa zrazí s inými osobami.

722
00:43:23,580 --> 00:43:31,920
Takže 364/365. Ak tretia osoba príde, že je to 363/365, a tak ďalej.

723
00:43:31,920 --> 00:43:35,790
Takže budeme držať súčinu týchto kúskov, ktoré sú stále menšie a menšie,

724
00:43:35,790 --> 00:43:40,720
prísť na to, aká je pravdepodobnosť, že každý z nás má unikátnu narodeniny?

725
00:43:40,720 --> 00:43:43,570
Ale potom môžeme, samozrejme, len sa, že odpoveď a otočte okolo

726
00:43:43,570 --> 00:43:47,210
a to 1 mínus všetko, výraz budeme nakoniec dostať

727
00:43:47,210 --> 00:43:51,250
ak si spomeniete na zadnej strane matematických kníh, vyzerá to trochu niečo také,

728
00:43:51,250 --> 00:43:54,590
, Ktorý je oveľa ľahšie interpretovať graficky.

729
00:43:54,590 --> 00:43:57,820
A to grafický tu má na osi x počet narodenín,

730
00:43:57,820 --> 00:44:02,030
alebo počet ľudí s narodenín, a na osi y je pravdepodobnosť zápasu.

731
00:44:02,030 --> 00:44:06,060
A čo to hovorí, je, že ak máte, povedzme, aj,

732
00:44:06,060 --> 00:44:10,860
Poďme si niečo ako 22, 23.

733
00:44:10,860 --> 00:44:13,160
Ak je 22 alebo 23 ľudí v miestnosti,

734
00:44:13,160 --> 00:44:17,100
pravdepodobnosť, že dva z týchto veľmi málo ľudí bude mať narodeniny v rovnaký deň

735
00:44:17,100 --> 00:44:19,560
je vlastne veľmi vysokým, combinatorially.

736
00:44:19,560 --> 00:44:23,450
50% šanca, že v triede len 22 ľudí, semináre, prakticky,

737
00:44:23,450 --> 00:44:25,790
2 z týchto ľudí bude mať narodeniny v rovnaký deň.

738
00:44:25,790 --> 00:44:28,520
Vzhľadom k tomu, že je tak veľa spôsobov, ako môžete mať narodeniny v rovnaký deň.

739
00:44:28,520 --> 00:44:31,110
Ešte horšie je, keď sa pozriete na pravej strane grafu,

740
00:44:31,110 --> 00:44:34,040
v čase, keď budete mať triedu s 58 žiakmi v tom,

741
00:44:34,040 --> 00:44:39,270
pravdepodobnosť 2 osoby, ktoré majú narodeniny je super, veľmi vysokým, takmer 100%.

742
00:44:39,270 --> 00:44:41,880
No, to je niečo ako zábavný fakt o skutočnom živote.

743
00:44:41,880 --> 00:44:45,850
>> Ale dôsledky, teraz, dátových štruktúr a ukladanie informácií

744
00:44:45,850 --> 00:44:51,100
Znamená to, že len za predpokladu, že máte pekný, čistý, rovnomerné rozloženie dát

745
00:44:51,100 --> 00:44:53,650
a máte dosť veľký pole, aby sa zmestili na veľa vecí,

746
00:44:53,650 --> 00:44:59,360
neznamená, že budete, aby si ľudia v unikátnych lokalitách.

747
00:44:59,360 --> 00:45:03,810
Budeš mať kolízie. Takže tento pojem hašovanie, ako sa to volá,

748
00:45:03,810 --> 00:45:07,450
pričom vstup ako "Alice" a masírovať ju nejakým spôsobom

749
00:45:07,450 --> 00:45:10,190
a potom sa dostať späť odpoveď ako 0 alebo 1 alebo 2.

750
00:45:10,190 --> 00:45:17,500
Dostať sa späť nejaký výstup z tejto funkcie je sužovaný tejto pravdepodobnosti kolízie.

751
00:45:17,500 --> 00:45:19,530
Takže, ako môžeme zvládnuť tieto kolízie?

752
00:45:19,530 --> 00:45:21,940
No, na jednom prípade, môžeme myšlienku, že bolo navrhnuté.

753
00:45:21,940 --> 00:45:25,100
Môžeme len posunúť všetky dolu, alebo možno, trochu jednoduchšie,

754
00:45:25,100 --> 00:45:29,870
skôr než pohyb všetci ostatní, poďme presunúť Anitu na spodnej časti je k dispozícii mieste.

755
00:45:29,870 --> 00:45:32,810
Takže ak Alice je 0, Bob je v 1, Charlie je 2,

756
00:45:32,810 --> 00:45:35,260
budeme len dať Anitu na mieste 3.

757
00:45:35,260 --> 00:45:38,860
A to je technika v dátových štruktúrach tzv lineárne snímanie.

758
00:45:38,860 --> 00:45:41,310
Lineárne preto, že ste len pešia tento riadok, a ty si nejako snímanie

759
00:45:41,310 --> 00:45:43,640
dostupných miestach v dátovej štruktúre.

760
00:45:43,640 --> 00:45:46,210
Samozrejme, že to prejde do O (n).

761
00:45:46,210 --> 00:45:49,590
Ak dátová štruktúra je naozaj plná, je tu 25 ľudí v ňom už,

762
00:45:49,590 --> 00:45:54,120
a potom Anita príde, ona skončí na to, čo by bolo zaradenie Z, a to je v poriadku.

763
00:45:54,120 --> 00:45:56,540
Stále sedí, a nájdeme ju neskôr.

764
00:45:56,540 --> 00:46:00,100
>> Ale to bolo v rozpore s cieľmi urýchlenie veci.

765
00:46:00,100 --> 00:46:02,530
Takže čo keby sme miesto zaviedla tento tretí rozmer?

766
00:46:02,530 --> 00:46:06,400
Táto technika sa všeobecne nazýva oddelené zreťazenie, alebo s reťazami.

767
00:46:06,400 --> 00:46:10,030
A čo hash tabuľka je teraz, to tabuľkové štruktúry,

768
00:46:10,030 --> 00:46:13,450
Váš stôl je len pole ukazovateľov.

769
00:46:13,450 --> 00:46:18,230
Ale čo tie ukazovatele poukazujú, je odhad, čo?

770
00:46:18,230 --> 00:46:21,970
Spájať zoznam. Takže čo keby sme vziať to najlepšie z oboch týchto svetov?

771
00:46:21,970 --> 00:46:26,500
Používame pole pre počiatočné indexy

772
00:46:26,500 --> 00:46:32,070
do dátovej štruktúry, takže môžeme okamžite prejsť na [0] [1], [30], alebo tak podobne,

773
00:46:32,070 --> 00:46:36,480
ale tak, že máme určitú flexibilitu a my sa zmestí Anitu a Alice a Adam

774
00:46:36,480 --> 00:46:38,630
a iné meno,

775
00:46:38,630 --> 00:46:43,470
sme namiesto toho nechať druhej osi rast ľubovoľne.

776
00:46:43,470 --> 00:46:47,340
A nakoniec sme sa, v pondelok, má to výrazný schopnosť s prepojeného zoznamu.

777
00:46:47,340 --> 00:46:49,530
Môžeme pestovať dátovú štruktúru ľubovoľne.

778
00:46:49,530 --> 00:46:52,450
Prípadne môžeme len urobiť veľký 2-rozmerné pole,

779
00:46:52,450 --> 00:46:57,190
ale že to bude hrozné situácie, ak jeden z riadkov v 2-rozmerné pole

780
00:46:57,190 --> 00:47:01,280
nie je dostatočne veľké pre ďalšie osobe, ktorej meno sa stane začať s A.

781
00:47:01,280 --> 00:47:04,200
Boh chráň, musíme prerozdeliť obrovský 2-dimenzionální štruktúra

782
00:47:04,200 --> 00:47:06,600
len preto, že je tu toľko ľudí s názvom,

783
00:47:06,600 --> 00:47:09,480
zvlášť keď je tu tak málo ľudí s názvom Z niečo.

784
00:47:09,480 --> 00:47:12,170
Je to len bude veľmi riedke dátová štruktúra.

785
00:47:12,170 --> 00:47:15,400
Takže to nie je dokonalé v žiadnom prípade, ale teraz máme mať aspoň možnosť

786
00:47:15,400 --> 00:47:19,090
okamžite zistiť, kde Alice alebo Anita patrí,

787
00:47:19,090 --> 00:47:21,090
aspoň pokiaľ ide o zvislej osi,

788
00:47:21,090 --> 00:47:25,850
a potom sme sa len rozhodnúť, kam Anitu alebo Alice v tomto prepojenom zozname.

789
00:47:25,850 --> 00:47:32,480
Ak sa nezaujíma radenie veci, ako by rýchlo vložíme Alicu do štruktúry, ako je tento?

790
00:47:32,480 --> 00:47:35,370
Je to konštantný čas. My index do [0], a ak nie je niečí tam,

791
00:47:35,370 --> 00:47:37,550
Alice pokračuje na začiatku tohto prepojeného zoznamu.

792
00:47:37,550 --> 00:47:40,000
Ale to nie je veľký problém. Pretože ak Anita potom príde

793
00:47:40,000 --> 00:47:42,160
nejaké číslo z krokov neskôr, kedy sa Anita patrí?

794
00:47:42,160 --> 00:47:45,140
No, [0]. OOP. Alice je už v tomto prepojenom zozname.

795
00:47:45,140 --> 00:47:47,760
>> Ale ak nebudeme starať o radenie tieto mená,

796
00:47:47,760 --> 00:47:53,580
môžeme len presunúť Alice cez, vložka Anita, ale aj to je konštantný čas.

797
00:47:53,580 --> 00:47:57,010
Aj v prípade, že je Alice a Adam a všetko ostatné A mená,

798
00:47:57,010 --> 00:47:59,410
to nie je naozaj posun je fyzicky. Prečo?

799
00:47:59,410 --> 00:48:04,090
Pretože sme práve urobili tu s prepojeného zoznamu, ktorý vie, boli tieto uzly sú vlastne je?

800
00:48:04,090 --> 00:48:06,550
Jediné, čo musíte urobiť, je presunúť strúhanky.

801
00:48:06,550 --> 00:48:10,930
Presuňte šípkami okolo, nemusíte fyzicky presunúť všetky dáta okolo.

802
00:48:10,930 --> 00:48:14,610
Takže môžeme vložiť Anita, v tomto prípade, okamžite. Konštantný čas.

803
00:48:14,610 --> 00:48:20,250
Takže máme konštantný čas vyhľadávania a konštantný čase vkladanie niekoho ako Anita.

804
00:48:20,250 --> 00:48:22,740
Ale trochu zjednodušujúce svet.

805
00:48:22,740 --> 00:48:28,510
Čo keď sme neskôr chcete nájsť Alicu?

806
00:48:28,510 --> 00:48:31,050
Čo keď sme neskôr chcete nájsť Alicu?

807
00:48:31,050 --> 00:48:35,690
Koľko krokov je to, že bude trvať?

808
00:48:35,690 --> 00:48:37,850
[Študent odpoveď, nezrozumiteľným]

809
00:48:37,850 --> 00:48:40,950
Presne tak. Počet ľudí, ako Alice v pripojenom zozname.

810
00:48:40,950 --> 00:48:45,420
Takže to nie je úplne dokonalý, pretože naše dátová štruktúra, znovu, má túto vertikálny prístup

811
00:48:45,420 --> 00:48:50,240
a potom má tieto prepojené zoznamy visiace - vlastne, nech to nie je nakresliť poľa.

812
00:48:50,240 --> 00:48:56,020
Je táto spojené zoznamy visiace z nej, že vyzerá trochu niečo takého.

813
00:48:56,020 --> 00:48:59,110
Ale problém je, ak Alice a Adam a všetko ostatné A mená

814
00:48:59,110 --> 00:49:01,720
nakoniec viac a viac tam,

815
00:49:01,720 --> 00:49:04,810
nájsť niekoho, kto by mohol skončiť brať veľa krokov,

816
00:49:04,810 --> 00:49:06,670
bcause budete musieť prechádzať prepojeného zoznamu,

817
00:49:06,670 --> 00:49:08,090
ktorý je lineárna operácia.

818
00:49:08,090 --> 00:49:14,270
Takže naozaj, potom, vloženie času nakoniec je O (n), kde n je počet prvkov v zozname.

819
00:49:14,270 --> 00:49:21,780
Delené, nech je ľubovoľne nazvať m, kde m je počet prepojených zoznamov

820
00:49:21,780 --> 00:49:24,500
že majú v tomto zvislej osi.

821
00:49:24,500 --> 00:49:27,180
Inými slovami, ak sa skutočne predpokladať rovnomerné rozloženie mien,

822
00:49:27,180 --> 00:49:30,150
úplne nereálne. Je tu samozrejme viac niektorých písmen než ostatní.

823
00:49:30,150 --> 00:49:32,580
>> Ale ak budeme predpokladať pre túto chvíľu jednotný distribučné,

824
00:49:32,580 --> 00:49:37,350
a my sme n celkovej ľudí, a m celkom reťaze

825
00:49:37,350 --> 00:49:40,630
K dispozícii nám, potom dĺžka každej z týchto reťazcov

826
00:49:40,630 --> 00:49:44,380
pomerne jednoducho bude celkový, n delí počtom reťazcov.

827
00:49:44,380 --> 00:49:48,900
Takže n / m Ale tu je miesto, kde môžeme byť všetci matematicky šikovný.

828
00:49:48,900 --> 00:49:53,030
m je konštanta, pretože tam je pevne stanovený počet z nich.

829
00:49:53,030 --> 00:49:54,620
Budeš deklarovať svoju ponuku na začiatku,

830
00:49:54,620 --> 00:49:58,450
a my nie sme zmeny veľkosti zvislú os. Podľa definície, ktorá zostáva pevná.

831
00:49:58,450 --> 00:50:01,220
Je to len na vodorovnej osi, aby som tak povedal, že to mení.

832
00:50:01,220 --> 00:50:04,760
Takže technicky, to je konštanta. Takže teraz, vloženie času

833
00:50:04,760 --> 00:50:09,700
je do značnej miery O (n).

834
00:50:09,700 --> 00:50:12,410
Takže nie je pocit, že všetci, že oveľa lepšie.

835
00:50:12,410 --> 00:50:14,940
Ale čo je pravda tu? No, tentoraz, celé týždne,

836
00:50:14,940 --> 00:50:20,640
sme hovorili O (n ²). O (n), 2 x n?, - N, deleno 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
Je to len n ². Ale teraz, v tejto časti semestra,

838
00:50:23,580 --> 00:50:25,560
môžeme začať hovoriť o reálnom svete znovu.

839
00:50:25,560 --> 00:50:31,520
A n / m, je úplne rýchlejší než len n sám.

840
00:50:31,520 --> 00:50:35,170
Ak máte tisíce mien, a rozdeľujú ich do viacerých segmentov

841
00:50:35,170 --> 00:50:37,820
takže majú len desať mien v každej z týchto reťazcov,

842
00:50:37,820 --> 00:50:41,670
úplne vyhľadávania desať vecí bude rýchlejší než tisíc vecí.

843
00:50:41,670 --> 00:50:43,740
A tak jeden z nasledujúcich problémových súborov sa chystá vyzvať vás

844
00:50:43,740 --> 00:50:46,100
premýšľať o tom, presne, že aj keď, jo,

845
00:50:46,100 --> 00:50:49,520
asymptoticky a matematicky, to je stále len lineárne,

846
00:50:49,520 --> 00:50:51,700
ktorý nasáva všeobecne, keď sa snažia nájsť veci.

847
00:50:51,700 --> 00:50:54,530
V skutočnosti, to bude rýchlejšie, než že

848
00:50:54,530 --> 00:50:56,520
pretože toto deliteľ.

849
00:50:56,520 --> 00:50:58,310
A tak tam je zase bude tento trade-off

850
00:50:58,310 --> 00:51:01,390
a tento konflikt medzi teóriou a realitou,

851
00:51:01,390 --> 00:51:03,550
a jeden z gombíkov začne otáčať v tomto bode v semestri

852
00:51:03,550 --> 00:51:07,510
je viac v realite s tým, ako sme trochu pripraviť na koniec semster je,

853
00:51:07,510 --> 00:51:09,280
ako sme predstaviť svet programovanie pre web,

854
00:51:09,280 --> 00:51:11,530
kde naozaj, výkon bude počítať, pretože používatelia budú

855
00:51:11,530 --> 00:51:14,880
začať cítiť a oceniť chudobné návrhárska rozhodnutia.

856
00:51:14,880 --> 00:51:19,950
>> Tak ako sa vám ísť o realizáciu prepojené - hash tabuľku s 31 prvkami?

857
00:51:19,950 --> 00:51:22,600
A predchádzajúci príklad bol ľubovoľne o narodeniny.

858
00:51:22,600 --> 00:51:26,190
Ak má niekto narodeniny k 1. januári alebo vo februári 1, dáme ich do tejto vedra.

859
00:51:26,190 --> 00:51:28,960
Ak je to 2. januára 2. februára 2. marca dáme im v tomto vedre.

860
00:51:28,960 --> 00:51:32,220
To je dôvod, prečo to bolo 31. Ako deklarovať hash tabuľky?

861
00:51:32,220 --> 00:51:37,480
To môže byť celkom jednoduché, uzol * stôl je moja ľubovoľný názov pre to, [31].

862
00:51:37,480 --> 00:51:42,400
To mi dáva 31 ukazovatele na uzly,

863
00:51:42,400 --> 00:51:45,370
a to mi umožňuje mať 31 ukazovatele na súvisiace zoznamy

864
00:51:45,370 --> 00:51:48,800
aj keď tieto reťazce sú spočiatku NULL.

865
00:51:48,800 --> 00:51:54,860
Čo chcem, aby, keď chcem uložiť "Alice," "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
No, musíme baliť tie veci v štruktúre

867
00:51:57,010 --> 00:52:00,530
pretože musíme Alice bodu k Bobovi, aby ukazoval na Charliem, a tak ďalej.

868
00:52:00,530 --> 00:52:04,940
Nemôžeme len tak mať mená sám, takže som mohol vytvoriť novú štruktúru s názvom uzla tu.

869
00:52:04,940 --> 00:52:08,310
>> Čo je skutočná uzol? Čo je uzol v tomto novom prepojeného zoznamu?

870
00:52:08,310 --> 00:52:11,840
Prvá vec, hovorí slovo, je pre meno osoby.

871
00:52:11,840 --> 00:52:14,340
DĹŽKA, pravdepodobne, sa týka maximálnej dĺžky ľudského mená,

872
00:52:14,340 --> 00:52:18,210
čo to je, 20, 30, 40 znakov v bláznivých rohových prípadoch,

873
00:52:18,210 --> 00:52:22,680
a 1 je pre čo? Je to len ďalší znak NULL, \ 0.

874
00:52:22,680 --> 00:52:27,410
Tak to je uzol balenia "niečo" vo vnútri seba samého,

875
00:52:27,410 --> 00:52:29,640
ale tiež deklaruje ukazovateľ s názvom ďalšie

876
00:52:29,640 --> 00:52:32,580
takže môžeme reťazec Alice k Bobovi s Charliem, a tak ďalej.

877
00:52:32,580 --> 00:52:36,700
Môže byť NULL, ale nemusí byť.

878
00:52:36,700 --> 00:52:40,110
Akékoľvek otázky týkajúce sa týchto hash tabuľky? Jo?

879
00:52:40,110 --> 00:52:46,190
[Študent pýtať otázku, nezrozumiteľné] Pole - dobrá otázka.

880
00:52:46,190 --> 00:52:50,120
Prečo je tento char slovo v poli skôr než len char *?

881
00:52:50,120 --> 00:52:53,830
V tomto trochu svojvoľné príklade, nechcel som, aby sa uchýliť

882
00:52:53,830 --> 00:52:56,190
malloc pre každú z pôvodných názvov.

883
00:52:56,190 --> 00:52:59,530
Chcel som, aby určil maximálne množstvo pamäte pre reťazec

884
00:52:59,530 --> 00:53:06,020
tak, že by som mohol skopírovať do štruktúry Alice \ 0 a nebudú sa musieť vysporiadať s malloc a slobodné a podobne.

885
00:53:06,020 --> 00:53:11,710
Ale čo som mohol urobiť, že keď som chcel byť viac vedomí využitie priestoru. Dobrá otázka.

886
00:53:11,710 --> 00:53:14,780
Takže poďme sa pokúsiť zovšeobecniť od tohto

887
00:53:14,780 --> 00:53:18,350
a zamerať sa na zvyšok dnešného dňa dátových štruktúr všeobecne

888
00:53:18,350 --> 00:53:21,170
a iné problémy, ktoré môžeme vyriešiť použitím rovnakých základy

889
00:53:21,170 --> 00:53:24,590
aj keď dátové štruktúry samy sa môžu líšiť vo svojich údajov.

890
00:53:24,590 --> 00:53:27,910
>> Tak to dopadá vo vede o počítačoch, stromy sú veľmi časté.

891
00:53:27,910 --> 00:53:29,760
A vy môžete myslieť stromu druhu ako rodinný strom,

892
00:53:29,760 --> 00:53:31,830
tam, kde je nejaké korene, niektoré matriarchát alebo patriarcha,

893
00:53:31,830 --> 00:53:34,540
babička alebo dedko alebo starší späť,

894
00:53:34,540 --> 00:53:38,880
, Pod ktorým sú mama a otec, alebo rôzne súrodenci alebo podobne.

895
00:53:38,880 --> 00:53:42,500
Takže stromová štruktúra má uzly a má deti,

896
00:53:42,500 --> 00:53:45,260
zvyčajne 0 alebo viac detí pre každý uzol.

897
00:53:45,260 --> 00:53:47,320
A niektoré z žargónu, ktorý vidíte na obrázku tu

898
00:53:47,320 --> 00:53:50,630
je niektorý z malé deti alebo vnúčatá na okrajoch

899
00:53:50,630 --> 00:53:52,330
ktorí nemajú žiadne šípky vychádzajúce z nich,

900
00:53:52,330 --> 00:53:55,070
to sú tzv listy, a niekto na vnútornej strane

901
00:53:55,070 --> 00:53:58,790
je vnútorný uzol, môžete tomu hovoriť čokoľvek na týchto tratiach.

902
00:53:58,790 --> 00:54:01,430
Ale táto štruktúra je celkom bežné. To je trochu svojvoľný.

903
00:54:01,430 --> 00:54:04,930
Máme jedno dieťa na ľavej strane, máme tri deti na pravej strane,

904
00:54:04,930 --> 00:54:06,830
dve deti na ľavej dolnej časti.

905
00:54:06,830 --> 00:54:10,740
Takže môžeme mať rôzne veľkosti stromy, ale ak začneme štandardizovať veci,

906
00:54:10,740 --> 00:54:15,330
a môžete pripomenúť to z videa Patrika na binárne vyhľadávanie z predchádzajúcej krátkej

907
00:54:15,330 --> 00:54:19,490
on-line, binárne vyhľadávanie nemusí byť realizované s radom

908
00:54:19,490 --> 00:54:21,410
alebo kúsky papiera na tabuľu.

909
00:54:21,410 --> 00:54:25,490
Predpokladajme, že ste chceli uložiť čísla v sofistikovanejšie dátové štruktúry.

910
00:54:25,490 --> 00:54:27,680
Môžete vytvoriť strom, ako je tento.

911
00:54:27,680 --> 00:54:35,290
Tie by mohli mať uzol deklarované v C, a že uzol môže mať najmenej dva prvky vnútri nej.

912
00:54:35,290 --> 00:54:39,470
Jedným z nich je číslo, ktoré chcete uložiť, a druhý je - dobre, potrebujeme ešte jeden.

913
00:54:39,470 --> 00:54:41,540
Na druhej strane je jeho deti.

914
00:54:41,540 --> 00:54:45,150
Tak tu je ďalšie dátové štruktúry. Tento čas je uzol definovaný ako ukladanie čísla n

915
00:54:45,150 --> 00:54:49,060
a potom dva ukazovatele, ľavá dieťaťa a právo dieťaťa.

916
00:54:49,060 --> 00:54:52,100
A sú to nebolo svojvoľné. Čo je na tom zaujímavé tohto stromu?

917
00:54:52,100 --> 00:55:00,550
>> Čo je vzor v tom, ako sme podľa tohto, alebo ako Patrick položil ju vo svojom videu?

918
00:55:00,550 --> 00:55:02,790
Je to trochu zrejmé, že tam je nejaký triedenie deje,

919
00:55:02,790 --> 00:55:04,460
ale to, čo je jednoduché pravidlo? Jo?

920
00:55:04,460 --> 00:55:08,350
[Študent odpoveď, nezrozumiteľným]

921
00:55:08,350 --> 00:55:12,040
Perfect. Ak sa pozrel na to, uvidíte malé množstvo na ľavej strane,

922
00:55:12,040 --> 00:55:14,690
veľké čísla na ľavej strane, ale to je pravda pre každého uzla.

923
00:55:14,690 --> 00:55:20,370
Pre každý uzol, jeho ľavý dieťa menej než to, a jej právo dieťa väčšie než to.

924
00:55:20,370 --> 00:55:25,210
Čo to znamená, je teraz, keď chcem hľadať túto dátovú štruktúru pre, povedzme, číslo 44,

925
00:55:25,210 --> 00:55:29,320
Musím začať pri koreni, pretože podobne ako u všetkých týchto zložitejších dátových štruktúr teraz,

926
00:55:29,320 --> 00:55:31,910
máme len ukazovateľ na jednu vec, na začiatku.

927
00:55:31,910 --> 00:55:35,010
A v tomto prípade, je začiatok koreňový. Nie je to ľavý koniec,

928
00:55:35,010 --> 00:55:39,530
to je koreň tejto štruktúry. Tak vidím, tu je 55, a ja hľadám 44.

929
00:55:39,530 --> 00:55:41,430
Ktorým smerom sa chcem ísť?

930
00:55:41,430 --> 00:55:45,680
No, ja chcem ísť doľava, pretože samozrejme, doprava bude príliš veľký.

931
00:55:45,680 --> 00:55:49,050
Tak zistíte tu, že ste trochu koncepčne sekanie strom v polovici

932
00:55:49,050 --> 00:55:51,700
preto, že ste nikdy ísť dole na pravej strane.

933
00:55:51,700 --> 00:55:55,410
Takže teraz idem od 55 do 33. Je to príliš malá čísla.

934
00:55:55,410 --> 00:56:01,590
Hľadám 44, ale teraz viem, že ak 44 je v tejto vetve, môžem ísť samozrejme doprava.

935
00:56:01,590 --> 00:56:04,460
Takže znova, ja som prerezávanie stromu na polovicu.

936
00:56:04,460 --> 00:56:06,780
Je to celkom veľa totožné koncepčne do telefónneho zoznamu.

937
00:56:06,780 --> 00:56:09,510
Je to rovnaké ako to, čo sme robili s papiermi na tabuľu,

938
00:56:09,510 --> 00:56:13,940
ale je to zložitejšie štruktúra, ktorá nám umožňuje skutočne robiť

939
00:56:13,940 --> 00:56:16,880
Tento rozdeľ a panuj podľa návrhu algoritmu,

940
00:56:16,880 --> 00:56:19,420
a v skutočnosti, posuvné konštrukcie, ako je tento - POZOR.

941
00:56:19,420 --> 00:56:22,870
Pojazdová štruktúru, ako je tento, kde je to len "ísť tade alebo tade,"

942
00:56:22,870 --> 00:56:26,870
znamená, všetky tie kód, ktorý sklonil svoju myseľ ako prvé, keď jeho zavedenie do oddielu

943
00:56:26,870 --> 00:56:31,270
alebo pri chôdzi cez to doma, pre binárne vyhľadávanie, pomocou rekurzie alebo iterácie,

944
00:56:31,270 --> 00:56:35,060
je to bolesť v krku. Nájsť prostredný prvok, potom urobiť si zaokrúhlenie nahor alebo nadol.

945
00:56:35,060 --> 00:56:39,230
>> Je tu krásu, pretože môžeme teraz používať rekurziu znovu,

946
00:56:39,230 --> 00:56:43,760
ale oveľa čistejšie. Naozaj, ak ste sa na číslo 55 a chcete nájsť 44,

947
00:56:43,760 --> 00:56:48,450
môžete ísť doľava v tomto prípade, potom to, čo robíte? Spustenie presne rovnaký algoritmus.

948
00:56:48,450 --> 00:56:51,560
Skontrolovať hodnotu uzla, potom ísť doľava alebo doprava.

949
00:56:51,560 --> 00:56:53,670
Potom si zistiť hodnotu uzla, prejdite vľavo alebo vpravo.

950
00:56:53,670 --> 00:56:56,710
Toto sa dokonale hodí pre rekurzie.

951
00:56:56,710 --> 00:57:00,920
Takže aj keď v minulosti sme urobili niektoré docela ľubovoľné príklady zahŕňajúce rekurzia

952
00:57:00,920 --> 00:57:03,430
že sa nemusí byť rekurzívne, s dátovými stuctures,

953
00:57:03,430 --> 00:57:07,820
najmä stromy, je to perfektné aplikácie tejto myšlienky brať problém,

954
00:57:07,820 --> 00:57:12,920
zmršťovanie, a potom riešiť rovnaký typ, ale menšie, program.

955
00:57:12,920 --> 00:57:14,590
>> Takže je tu ďalšia dátová štruktúra, ktorá môžeme predstaviť.

956
00:57:14,590 --> 00:57:18,760
Ten je určený na prvý pohľad vyzerať záhadné, ale toto je úžasné.

957
00:57:18,760 --> 00:57:25,090
Tak to je dátová štruktúra volal trie, trie, ktorá sa dedí od slova vyhľadávania,

958
00:57:25,090 --> 00:57:30,210
ktoré sa nevyslovuje re-try-Val, ale to je to, čo svet nazýva tieto veci. Skúsi. T-r-i-e.

959
00:57:30,210 --> 00:57:35,190
Je to strom štruktúra nejaký, ale každá z uzlov v trie

960
00:57:35,190 --> 00:57:41,280
Zdá sa, že to, čo? A to je trochu zavádzajúce, pretože je to trochu skrátený.

961
00:57:41,280 --> 00:57:45,960
Ale vyzerá to, že každý uzol v tomto trie je vlastne pole.

962
00:57:45,960 --> 00:57:48,840
A aj keď autor tohto diagramu nepreukázala to,

963
00:57:48,840 --> 00:57:54,130
v tomto prípade, to trie je dátová štruktúra, ktorej cieľom v živote je ukladať slová

964
00:57:54,130 --> 00:57:57,330
ako A-l-i-c-e alebo B-o-b.

965
00:57:57,330 --> 00:58:02,480
A spôsob, akým tieto dáta ukladá Alice a Bob a Charlie a Anita a tak ďalej

966
00:58:02,480 --> 00:58:06,970
je používa pole, kedy k ukladaniu Alice v trie,

967
00:58:06,970 --> 00:58:09,820
začíname na koreňový uzol, ktorý vyzerá ako pole,

968
00:58:09,820 --> 00:58:12,080
a to bolo napísané v rýchlopisný záznam.

969
00:58:12,080 --> 00:58:15,070
Autor vynechať abcdefg pretože tam neboli žiadne názvy s tým.

970
00:58:15,070 --> 00:58:19,150
Oni len ukázal, M a P a T, ale v tomto prípade,

971
00:58:19,150 --> 00:58:22,780
poďme od Alice a Bob a Charlie niektorých názvov, ktoré sú tu.

972
00:58:22,780 --> 00:58:25,670
Maxwell je vlastne v tomto diagrame.

973
00:58:25,670 --> 00:58:29,570
Tak ako ste s autorom obchod M - x-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
On alebo ona začala na koreňový uzol, a šiel do [M], tak zhruba 13, 13. miesto v poli.

975
00:58:36,990 --> 00:58:40,750
Potom odtiaľ, tam je ukazovateľ.

976
00:58:40,750 --> 00:58:42,760
Ukazovateľ vedie k ďalšie pole.

977
00:58:42,760 --> 00:58:47,880
Odtiaľ autor indexované do tohto poľa v mieste A, ako je znázornené tu vľavo hore,

978
00:58:47,880 --> 00:58:52,250
a potom on alebo ona nasledovala tento ukazovateľ do iného poľa,

979
00:58:52,250 --> 00:58:55,460
a šiel na ukazovateľ na umiestnenie X.

980
00:58:55,460 --> 00:58:59,840
Potom v ďalšom poli umiestnenie W, E, L, L, a tak ďalej,

981
00:58:59,840 --> 00:59:03,090
a konečne, poďme sa skutočne snaží, aby obraz na to.

982
00:59:03,090 --> 00:59:05,380
Čo uzol vyzerá v kóde?

983
00:59:05,380 --> 00:59:11,820
Uzol v trie obsahuje pole ukazovateľov na viac uzlov.

984
00:59:11,820 --> 00:59:16,090
Ale tam je tiež to byť nejaký druh Logické hodnota, aspoň v tomto prevedení.

985
00:59:16,090 --> 00:59:18,770
A stalo sa, hovorím is_word. Prečo?

986
00:59:18,770 --> 00:59:22,670
Pretože keď ste vkladanie Maxwella, nie ste vkladanie

987
00:59:22,670 --> 00:59:25,300
niečo do tejto dátovej štruktúry.

988
00:59:25,300 --> 00:59:27,480
Nie ste písanie M. Nie ste písanie X.

989
00:59:27,480 --> 00:59:30,240
Všetko, čo robíte, je po ukazovateľov.

990
00:59:30,240 --> 00:59:33,360
Ukazovateľ, ktorý predstavuje M, potom ukazovateľ, ktorý predstavuje,

991
00:59:33,360 --> 00:59:36,310
potom ukazovateľ, ktorý predstavuje X, potom W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
ale to, čo musíte urobiť, na konci je trochu ísť, skontrolujte, som dosiahol tohto umiestnenia.

993
00:59:41,950 --> 00:59:45,560
Tam bolo slovo, ktoré tu končí v dátovej štruktúre.

994
00:59:45,560 --> 00:59:48,190
>> Takže to, čo trie je naozaj plný a autor sa rozhodol reprezentovať

995
00:59:48,190 --> 00:59:51,880
Tieto medzníky s malými trojuholníkmi.

996
00:59:51,880 --> 00:59:56,470
To jednoducho znamená, že skutočnosť, tento trojuholník je tu, táto boolean hodnotu true

997
00:59:56,470 --> 00:59:59,200
znamená, že ak pôjdete späť do stromu,

998
00:59:59,200 --> 01:00:02,420
to znamená, že slovo s názvom Maxwell je v tomto.

999
01:00:02,420 --> 01:00:04,870
Ale slovo foo, napríklad,

1000
01:00:04,870 --> 01:00:07,970
nie je v strome, pretože keď som sa začať v koreňovom uzle tu hore,

1001
01:00:07,970 --> 01:00:14,030
Nie je f ukazovateľ, nie ukazovateľ o, nie ukazovateľ o Foo nie je meno v tomto slovníku.

1002
01:00:14,030 --> 01:00:22,460
Ale naopak, Turing, t-u-r-i-n-g. Opäť platí, že nebudú ukladať t alebo u alebo r alebo aj alebo n alebo g

1003
01:00:22,460 --> 01:00:29,820
Ale som obchod v tejto dátovej štruktúre hodnota skutočného tu dole v tomto uzle - na strome

1004
01:00:29,820 --> 01:00:33,030
Nastavením tejto boolovská is_word na true.

1005
01:00:33,030 --> 01:00:35,740
Takže trie je druh tejto veľmi zaujímavej meta štruktúry,

1006
01:00:35,740 --> 01:00:39,810
kam naozaj ukladanie slov sám pre tento druh slovníka.

1007
01:00:39,810 --> 01:00:45,100
Aby bolo jasno, ste len ukladanie áno alebo nie, tam je slovo, ktoré tu končí.

1008
01:00:45,100 --> 01:00:46,430
>> Teraz, čo je dôsledok?

1009
01:00:46,430 --> 01:00:51,120
Ak máte 150.000 slov v slovníku, že sa snažíte uložiť do pamäte

1010
01:00:51,120 --> 01:00:53,400
používať niečo ako prepojeného zoznamu,

1011
01:00:53,400 --> 01:00:56,870
budete mať 150.000 uzly vo vašom prepojeného zoznamu.

1012
01:00:56,870 --> 01:01:00,250
A nájsť jednu z tých slov abecedne môže trvať O (n) čas.

1013
01:01:00,250 --> 01:01:04,370
Lineárne čas. Avšak v prípade tu o trie,

1014
01:01:04,370 --> 01:01:09,210
čo je doba chodu nájsť slovo?

1015
01:01:09,210 --> 01:01:17,390
Ukazuje sa, že krásu je, že aj keď máte 149999 slov už v tomto slovníku,

1016
01:01:17,390 --> 01:01:20,170
ako bol vykonaný s touto dátovou štruktúrou,

1017
01:01:20,170 --> 01:01:25,560
koľko času zaberie nájsť alebo vložiť jednu osobu do toho, ako Alenka, Alice?

1018
01:01:25,560 --> 01:01:30,640
No, je to len 5, možno 6 krokov pre koncových znak.

1019
01:01:30,640 --> 01:01:32,880
Vzhľadom k tomu, presense ďalších mien v štruktúre

1020
01:01:32,880 --> 01:01:35,340
nie je v ceste vkladanie Alice.

1021
01:01:35,340 --> 01:01:39,640
Navyše, hľadanie Alice akonáhle tam sú 150.000 slov v tomto slovníku

1022
01:01:39,640 --> 01:01:41,960
nedostane v ceste nájsť Alicu vôbec,

1023
01:01:41,960 --> 01:01:46,880
pretože Alice je. . . . . tu, pretože som našiel logickú hodnotu.

1024
01:01:46,880 --> 01:01:50,920
A v prípade, že nie je boolean true, potom Alice nie je v tejto dátovej štruktúre slov.

1025
01:01:50,920 --> 01:01:56,220
Inými slovami, doba chodu zistiť veci a vkladanie vecí do tohto nového

1026
01:01:56,220 --> 01:02:01,920
dátová štruktúra trie je O z - nie je to n

1027
01:02:01,920 --> 01:02:05,730
Vzhľadom k tomu, presense zo 150.000 ľudí, nemá žiadny vplyv na Alicu, ako sa zdá.

1028
01:02:05,730 --> 01:02:11,560
Takže povedzme, že k, kde k je maximálna dĺžka slova v angličtine

1029
01:02:11,560 --> 01:02:14,050
ktorý je typicky nie viac ako 20-niečo znaky.

1030
01:02:14,050 --> 01:02:17,940
Takže k je konštanta. Takže Svätý Grál sa zdá, že sme našli hneď

1031
01:02:17,940 --> 01:02:26,000
je to, že z trie, konštantnom čase pre vložiek, pre vyhľadávanie, pre vymazanie.

1032
01:02:26,000 --> 01:02:29,170
Vzhľadom k tomu, mnoho vecí už v štruktúre,

1033
01:02:29,170 --> 01:02:32,600
ktoré nie sú ani fyzicky tam. Opäť platí, že sú to len nejako odškrtnúť, áno alebo nie,

1034
01:02:32,600 --> 01:02:35,050
nemá žiadny vplyv na jej budúcu dobu prevádzky.

1035
01:02:35,050 --> 01:02:37,940
>> Ale tam to musí byť nejaký háčik, inak by sme nemali plytvať toľko času

1036
01:02:37,940 --> 01:02:41,460
na všetkých týchto ostatných dátových štruktúr, len aby konečne dostať do tajnej ten, ktorý je úžasný.

1037
01:02:41,460 --> 01:02:46,410
Takže akú cenu sú platíme, aby dosiahnutie tohto veľkosť tu? Space.

1038
01:02:46,410 --> 01:02:49,010
Táto vec je masívny. A dôvod, prečo autor

1039
01:02:49,010 --> 01:02:52,400
nepredložila to tu, všimnite si, že všetky tieto veci, ktoré vyzerajú ako pole,

1040
01:02:52,400 --> 01:02:55,400
nemal čerpať zvyšok stromu, zvyšok z trie,

1041
01:02:55,400 --> 01:02:58,060
pretože to jednoducho nie je relevantné k príbehu.

1042
01:02:58,060 --> 01:03:01,870
Všetky tieto uzly sú super široký, a každý uzol v strome zaberá

1043
01:03:01,870 --> 01:03:07,780
26 alebo vlastne, môže byť 27 znakov, pretože v tomto prípade som bol, vrátane priestoru pre apostrof

1044
01:03:07,780 --> 01:03:09,980
tak, že by sme mohli mať apostrophized slová.

1045
01:03:09,980 --> 01:03:14,450
V tomto prípade sa jedná o široké pole. Takže aj keď to nie sú picutured,

1046
01:03:14,450 --> 01:03:18,190
to zaberá obrovské množstvo pamäte RAM.

1047
01:03:18,190 --> 01:03:20,670
Ktorý by mohol byť v poriadku, especilly v modernom hardvéri,

1048
01:03:20,670 --> 01:03:25,650
ale to je kompromis. Dostávame menej času tým, že míňa viac priestoru.

1049
01:03:25,650 --> 01:03:28,580
Takže tam, kde sa to všetko deje?

1050
01:03:28,580 --> 01:03:32,640
Dobre, poďme robiť - uvidíme tu.

1051
01:03:32,640 --> 01:03:39,510
Poďme urobiť skok s tymto chlapom tu.

1052
01:03:39,510 --> 01:03:43,450
>> Verte tomu alebo nie, taká zábava ako C už dlhšiu dobu,

1053
01:03:43,450 --> 01:03:48,130
sme dosiahnutí bodu v semestri, kedy je čas na prechod k veciam viac moderné.

1054
01:03:48,130 --> 01:03:50,950
Veci na vyššej úrovni. A aj keď pre najbližších pár týždňov

1055
01:03:50,950 --> 01:03:54,580
budeme aj naďalej pokračovať v ponoriť do sveta ukazovateľov a správa pamäte

1056
01:03:54,580 --> 01:03:57,210
sa dostať, že pohodlie, s ktorými sa potom môžeme stavať na,

1057
01:03:57,210 --> 01:04:01,270
Koniec hry je nakoniec zaviesť, ironicky, nie tento jazyk.

1058
01:04:01,270 --> 01:04:03,330
Strávime, rovnako ako 10 minút hovoriť o HTML.

1059
01:04:03,330 --> 01:04:05,950
Všetko HTML je je značkovací jazyk, a to, čo značkovací jazyk je

1060
01:04:05,950 --> 01:04:10,220
je, že tieto série otvorených zátvoriek a uzavretých hranatých zátvoriek, ktoré hovoria, že "aby to tučne"

1061
01:04:10,220 --> 01:04:12,000
", Aby to kurzívou" "túto stredu."

1062
01:04:12,000 --> 01:04:14,250
To nie je všetko, že intelektuálne zaujímavé, ale je to super užitočné.

1063
01:04:14,250 --> 01:04:16,650
A rozhodne to všadeprítomný v týchto dňoch.

1064
01:04:16,650 --> 01:04:19,450
Ale čo je najlepšie o svete HTML, a webové programovanie všeobecne,

1065
01:04:19,450 --> 01:04:25,910
je vytváranie dynamických veci, písanie kódu v jazykoch ako PHP alebo Python alebo Ruby alebo Java alebo C #.

1066
01:04:25,910 --> 01:04:30,360
Naozaj, aký je váš jazyk výberu je, a generovanie HTML dynamicky.

1067
01:04:30,360 --> 01:04:32,960
Generovanie niečo ako CSS dynamicky.

1068
01:04:32,960 --> 01:04:35,810
Kaskádové štýly, čo je tiež o estetike.

1069
01:04:35,810 --> 01:04:41,360
A tak aj keď dnes, keď som ísť do nejakej webovej stránky, ako známe Google.com,

1070
01:04:41,360 --> 01:04:46,100
a ja idem na prezeranie, developer, pohľad zdroj, ktorý možno ste nevyskúšali,

1071
01:04:46,100 --> 01:04:49,800
ale ak bude zobraziť zdroj, toto asi vyzerá dosť záhadné.

1072
01:04:49,800 --> 01:04:55,320
Ale to je zdrojový kód, ktorý implementuje Google.com.

1073
01:04:55,320 --> 01:04:57,940
Na prednej strane. A vlastne to všetko je nadýchaná estetika veci.

1074
01:04:57,940 --> 01:05:01,740
To je CSS tu. Keby som posúvanie bude pokračovať, sa budeme trochu farebne veci.

1075
01:05:01,740 --> 01:05:06,890
To je HTML. Google kód vyzerá neporiadok, ale keď som v skutočnosti otvoriť iné okno,

1076
01:05:06,890 --> 01:05:09,380
môžeme vidieť nejakú štruktúru, aby to.

1077
01:05:09,380 --> 01:05:12,640
Ak otvorím toto hore, všimnite si, tu je to trochu zrozumiteľnejšie.

1078
01:05:12,640 --> 01:05:16,850
Budeme vidieť, ako dlhé túto značku, [word] je tag,

1079
01:05:16,850 --> 01:05:23,520
HTML, hlava, telo, div, skript, text area, span, stred, div.

1080
01:05:23,520 --> 01:05:26,770
A to je tiež nejako tajomné vyzerajúce na prvý pohľad,

1081
01:05:26,770 --> 01:05:30,890
ale všetky z tejto šlamastiky riadi určitými vzormi, a opakovateľné vzory,

1082
01:05:30,890 --> 01:05:33,850
tak, že akonáhle sa dostaneme základy dole, budete môcť písať kód, ako je tento

1083
01:05:33,850 --> 01:05:37,550
a potom manipulovať kód, ako to pomocou ešte ďalší jazyk, s názvom JavaScript.

1084
01:05:37,550 --> 01:05:40,440
A JavaScript je jazyk, ktorý beží vnútri webového prehliadača

1085
01:05:40,440 --> 01:05:44,380
dnes používame na Harvard kurzov, pre nástroj predmetu nákupné že Google maps používa

1086
01:05:44,380 --> 01:05:48,660
aby vám veľa dynamiky, Facebook vám dáva pre zobrazenie okamžitej aktualizácie stavu,

1087
01:05:48,660 --> 01:05:51,430
Twitter používa to, aby vám ukázať tweety okamžite.

1088
01:05:51,430 --> 01:05:53,820
To všetko začneme ponoriť dovnútra

1089
01:05:53,820 --> 01:05:57,190
Ale aby sa tam dostať, musíme pochopiť, niečo málo o internete.

1090
01:05:57,190 --> 01:06:01,130
Tento klip je tu len minútu dlhé, a predpokladajme, že pre túto chvíľu je to v skutočnosti,

1091
01:06:01,130 --> 01:06:08,380
ako internet funguje ako upútavka na to, čo je asi príde. Dám vám "Warriors of internete."

1092
01:06:08,380 --> 01:06:14,720
>> [♫ Slow chorus music ♫]

1093
01:06:14,720 --> 01:06:20,450
[Muž rozprávač] Prišiel so správou.

1094
01:06:20,450 --> 01:06:23,770
S protokolom všetky jeho vlastné.

1095
01:06:23,770 --> 01:06:37,270
[♫ Rýchlejšie electronic music ♫]

1096
01:06:37,270 --> 01:06:41,330
Prišiel na svet v pohode firewallov, bezcitný smerovača,

1097
01:06:41,330 --> 01:06:45,690
a nebezpečenstvo ďaleko horšie ako smrť.

1098
01:06:45,690 --> 01:06:55,400
Je rýchly. Je to silný. Je to TCP / IP, a on má svoju adresu.

1099
01:06:55,400 --> 01:06:59,250
Warriors siete.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Budúci týždeň, a potom. Internet. Web programovanie. To je CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]