1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID Malan: Dobre. 3 00:00:12,250 --> 00:00:13,860 Vitajte späť CS50. 4 00:00:13,860 --> 00:00:16,190 To je začiatok 8 týždňov. 5 00:00:16,190 --> 00:00:21,320 A pripomínajú, že problém sada 5 skončila s trochou výzvu. 6 00:00:21,320 --> 00:00:25,210 Takže za predpokladu, že späť všetky svoje výučby Fellows a CA fotografie 7 00:00:25,210 --> 00:00:30,480 v súbore card.raw, máte nárok sa teraz nájsť všetkých tých ľudí, a 8 00:00:30,480 --> 00:00:34,510 jeden šťastný výherca bude chodiť domov s jedným z týchto vecí, skok pohyb 9 00:00:34,510 --> 00:00:37,450 zariadenie, ktoré môžete použiť pre konečné projekty, napríklad. 10 00:00:37,450 --> 00:00:39,860 >> To každý rok, vedie k trochu děsivost. 11 00:00:39,860 --> 00:00:43,480 A tak to, čo som myslel, že to je podiel s vami o niektoré poznámky, ktoré majú 12 00:00:43,480 --> 00:00:47,370 išiel tam a späť cez zamestnanci zoznam neskoro. 13 00:00:47,370 --> 00:00:51,110 Napríklad práve včera večer, citácie koniec citátu, z jedného z pracovníkov 14 00:00:51,110 --> 00:00:55,000 členovia, "musel som študentský klepanie na moje dvere vyfotiť so mnou. 15 00:00:55,000 --> 00:00:59,020 Stalkeri, vravím. "Zacala dosť opisná a potom sme sa presťahovali 16 00:00:59,020 --> 00:01:02,830 na, tak hodinu neskôr, "som mal Študent na mňa čaká po bode 17 00:01:02,830 --> 00:01:06,080 a mal všetky naše mená a fotografie na niektorých listov papiera. "v poriadku. 18 00:01:06,080 --> 00:01:09,230 Organizovaná tak, ale nie všetko strašidelné ešte. 19 00:01:09,230 --> 00:01:12,520 >> Tak, "ja som bol mimo mesta tento víkend, a keď som sa vrátil, bol tam jeden v 20 00:01:12,520 --> 00:01:12,630 môj 21 00:01:12,630 --> 00:01:16,740 spálne. "[smiech] 22 00:01:16,740 --> 00:01:20,410 DAVID Malan: Ďalšie citácie z pracovníkov člen "študent prišiel do môjho domu na 23 00:01:20,410 --> 00:01:25,330 Somerville pri 4 hodín ráno. "Ďalšie personál, "Dostal som do hotela v San 24 00:01:25,330 --> 00:01:30,016 Francisco a študent čakal na ma v hale s tromi DSLR. " 25 00:01:30,016 --> 00:01:31,510 Typ fotoaparátu. 26 00:01:31,510 --> 00:01:34,980 "Ja nie som ani na zamestnanca tomto semestri, ale študent sa vlámal do môjho domu tento 27 00:01:34,980 --> 00:01:40,480 ráno a zaznamenal celú vec so sklom Google. "A potom konečne, 28 00:01:40,480 --> 00:01:43,650 "Najmenej 12 ľudí bolo dychtivo čaká na mňa, keď som sa dostal z môjho 29 00:01:43,650 --> 00:01:44,800 limo, a potom som 30 00:01:44,800 --> 00:01:46,970 prebudil. "Dobre. 31 00:01:46,970 --> 00:01:57,690 Takže medzi fotografiami, ako môžete spomínam, je tento chlapík tu, kto ste 32 00:01:57,690 --> 00:02:01,850 Možno viete, ako Milo Banana, ktorý žije s Lauren Carvalho, naše hlavy 33 00:02:01,850 --> 00:02:02,905 vyučovanie Fellow. 34 00:02:02,905 --> 00:02:05,170 Milo Milo, poď sem chlapče. 35 00:02:05,170 --> 00:02:06,320 Milo. 36 00:02:06,320 --> 00:02:08,650 Milo. 37 00:02:08,650 --> 00:02:12,230 Nezabúdajme, že má na sebe Google Glass, takže my vám ukážeme všetko po ňom. 38 00:02:12,230 --> 00:02:16,190 Tak to je Milo, ak chcete vyfotografovať sa s ním neskôr. 39 00:02:16,190 --> 00:02:18,240 Ak by ste chceli dať pozor na divákov tam. 40 00:02:18,240 --> 00:02:19,430 OK. 41 00:02:19,430 --> 00:02:20,200 To je dobré zábery. 42 00:02:20,200 --> 00:02:22,556 No, Milo Banana. 43 00:02:22,556 --> 00:02:23,941 Oh, nerobte to. 44 00:02:23,941 --> 00:02:29,020 >> [Smiech] 45 00:02:29,020 --> 00:02:29,470 >> OK. 46 00:02:29,470 --> 00:02:34,550 Takže jedným slovom, potom o tom, čo je pred nami, pretože ako začneme prechodu, 47 00:02:34,550 --> 00:02:38,410 tento týždeň konkrétne z C na v prostredí príkazového riadku na PHP a 48 00:02:38,410 --> 00:02:42,720 JavaScript a SQL a HTML a CSS v web-based prostredie, budeme 49 00:02:42,720 --> 00:02:44,490 vybavenie vám všetky viac vedomostí pre 50 00:02:44,490 --> 00:02:46,010 prípadné konečné projektov. 51 00:02:46,010 --> 00:02:49,240 Za týmto účelom je ihrisko má Tradícia organizovania seminárov, ktoré 52 00:02:49,240 --> 00:02:50,950 sú na tangenciálny témy k predmetu. 53 00:02:50,950 --> 00:02:54,330 Veľmi o programovaní a vývoj aplikácií a tak ďalej, ale 54 00:02:54,330 --> 00:02:57,010 nemusí byť nutne preskúmaná Kurz vlastné osnovy. 55 00:02:57,010 --> 00:03:00,250 >> Takže ak by vás mohli zaujímať v jednom alebo viac z tohtoročných seminárov, 56 00:03:00,250 --> 00:03:02,530 zaregistrujte sa na cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 Tam sú staršie semináre na cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 A na zozname zatiaľ pre tento rok Amazing Web Apps sú s Ruby on 59 00:03:10,620 --> 00:03:13,580 Koľajnice, ktorá je alternatívou jazyk PHP. 60 00:03:13,580 --> 00:03:14,900 Matematická lingvistika. 61 00:03:14,900 --> 00:03:18,710 Úvod do IOS, ktorý je platformy, ktorá je použitá pre iPhone a 62 00:03:18,710 --> 00:03:19,850 iPad rozvoja. 63 00:03:19,850 --> 00:03:22,890 JavaScript pre Web Apps, budeme pokrývať , Ale v tomto seminári, pôjdete 64 00:03:22,890 --> 00:03:24,070 do väčších detailov. 65 00:03:24,070 --> 00:03:27,390 >> Leap Motion, takže budeme vlastne majú niektoré našich priateľov z Leap Motion, 66 00:03:27,390 --> 00:03:29,160 spoločnosť sama, pridajte sa k nám. 67 00:03:29,160 --> 00:03:31,800 Zajtra, v skutočnosti, aby praktický seminár, ak je 68 00:03:31,800 --> 00:03:33,320 vás zaujímajú. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, alternatívne metódy pre pomocou JavaScriptu nie je v prehliadači, 70 00:03:38,770 --> 00:03:39,970 ale na serveri. 71 00:03:39,970 --> 00:03:42,110 Node.js, ktorý je veľmi V tomto duchu tiež. 72 00:03:42,110 --> 00:03:43,650 Elegantný Android dizajn. 73 00:03:43,650 --> 00:03:46,990 Android je veľmi populárna alternatíva na iOS a Windows Phone 74 00:03:46,990 --> 00:03:48,790 a ďalšie mobilné platformy. 75 00:03:48,790 --> 00:03:51,180 A Web Security Aktívna obrana. 76 00:03:51,180 --> 00:03:54,590 >> Takže v skutočnosti, ak si prajete zapojiť sa do tohto, dovoľte mi, aby som 77 00:03:54,590 --> 00:03:55,840 aby na vedomie. 78 00:03:55,840 --> 00:03:57,790 Sme veľmi radi, že Naši priatelia na skok 79 00:03:57,790 --> 00:03:59,140 Pohyb, ktorý je spustenie - 80 00:03:59,140 --> 00:04:01,300 tento prístroj naozaj len prišiel pred niekoľkými mesiacmi - 81 00:04:01,300 --> 00:04:05,960 milostivo daroval 30 týchto zariadení do triedy pre čo najväčší počet študentov, je-li 82 00:04:05,960 --> 00:04:08,670 by ste chceli požičať hardvér na konci semestra a používať ho pre 83 00:04:08,670 --> 00:04:10,390 Skutočná konečná projektu. 84 00:04:10,390 --> 00:04:11,890 Oni podporujú veľké množstvo jazykov. 85 00:04:11,890 --> 00:04:16,040 Žiadny z nich C, žiadny z nich PHP, takže realizovať jeden alebo viac z týchto seminárov 86 00:04:16,040 --> 00:04:16,899 by mohlo byť zaujímavé. 87 00:04:16,899 --> 00:04:19,730 A všetky z nich bude natočený v prípade, že nie ste schopní 88 00:04:19,730 --> 00:04:21,380 zúčastniť osobne. 89 00:04:21,380 --> 00:04:25,000 Harmonogram bude oznámené prostredníctvom email ako spevniť izby. 90 00:04:25,000 --> 00:04:28,460 >> A napokon, ak idete na projects.cs.50.net, to je webová stránka 91 00:04:28,460 --> 00:04:31,450 udržiavame každý rok, pozývame ľudia z komunity, fakulty, 92 00:04:31,450 --> 00:04:36,420 odbory, zamestnanci a obaja na vonkajšej strane na CS50 93 00:04:36,420 --> 00:04:37,730 navrhnúť projektové nápady. 94 00:04:37,730 --> 00:04:39,050 Veci sú predmetom záujmu skupiny študentov. 95 00:04:39,050 --> 00:04:40,600 Veci záujmu oddelenia. 96 00:04:40,600 --> 00:04:43,990 Takže sa zase tam, ak budete bojovať s neistotou, pokiaľ ide o to, čo 97 00:04:43,990 --> 00:04:46,700 sami chceli riešiť. 98 00:04:46,700 --> 00:04:51,760 >> Takže poslednej dobe sme zaviedli pravdepodobne zložitejšie dátové štruktúry, ako my by sme 99 00:04:51,760 --> 00:04:53,300 vidieť v minulých týždňoch. 100 00:04:53,300 --> 00:04:56,550 Radi by sme sa s použitím polí dosť šťastne ako užitočná, ak 101 00:04:56,550 --> 00:04:58,160 zjednodušujúce dátové štruktúry. 102 00:04:58,160 --> 00:05:00,570 Potom sme zaviedli nich, ktoré Samozrejme sú spojené zoznamy. 103 00:05:00,570 --> 00:05:05,470 A to, čo bolo jednou z motiváciou pre zavedenie tejto dátovej štruktúry? 104 00:05:05,470 --> 00:05:06,930 Jo? 105 00:05:06,930 --> 00:05:07,250 Čo je to? 106 00:05:07,250 --> 00:05:08,080 >> Divákov: Dynamická veľkosť. 107 00:05:08,080 --> 00:05:09,040 >> DAVID Malan: Dynamická veľkosť. 108 00:05:09,040 --> 00:05:11,890 Takže zatiaľ čo v poli, musíte poznať jeho veľkosť zálohy, ak 109 00:05:11,890 --> 00:05:12,740 prideliť ju. 110 00:05:12,740 --> 00:05:14,380 V spájať zoznam, nemusíte vedieť, že. 111 00:05:14,380 --> 00:05:17,610 Môžete len malloc, alebo všeobecnejšie, prideliť ďalšie 112 00:05:17,610 --> 00:05:20,720 uzol, aby som tak povedal, kedykoľvek Chcem vložiť ďalšie dáta. 113 00:05:20,720 --> 00:05:22,670 A uzol nie je vopred význam. 114 00:05:22,670 --> 00:05:25,580 Je to len všeobecný termín, ktorý popisuje nejaký druh kontajnera, ktorý sme 115 00:05:25,580 --> 00:05:29,610 použitie v našej dátovej štruktúry pre ukladanie niektoré Predmetom záujmu, ktorý je v tomto 116 00:05:29,610 --> 00:05:31,750 prípade sa stalo, že celé čísla. 117 00:05:31,750 --> 00:05:33,160 >> Ale je tu vždy kompromisom. 118 00:05:33,160 --> 00:05:38,070 Tak sme si dynamické veľkosti dát štruktúra, ale akú cenu platíme? 119 00:05:38,070 --> 00:05:40,040 Čo je to nevýhoda previazaných zoznamov? 120 00:05:40,040 --> 00:05:41,006 Jo? 121 00:05:41,006 --> 00:05:41,980 >> DIVÁKOV: vyžaduje viac pamäte. 122 00:05:41,980 --> 00:05:44,240 >> DAVID Malan: To si vyžaduje viac pamäť, ako presne? 123 00:05:44,240 --> 00:05:46,440 >> DIVÁKOV: [nepočuteľné]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID Malan: Presne tak. 125 00:05:47,050 --> 00:05:50,460 Takže teraz sme ukazovatele nástupu do prídavné pamäti, že sme predtým 126 00:05:50,460 --> 00:05:53,040 nepotreboval, pretože výhoda z poľa, samozrejme, je to, že 127 00:05:53,040 --> 00:05:54,860 všetko je súvislé späť sa chrbtom k sebe, čo 128 00:05:54,860 --> 00:05:56,380 vám dáva náhodný prístup. 129 00:05:56,380 --> 00:06:00,710 Pretože len pomocou hranatou zátvorkou notácie, alebo viac technicky ukazovateľ 130 00:06:00,710 --> 00:06:03,580 aritmetický, veľmi jednoduché sčítanie, môžete pristupovať k akýmkoľvek 131 00:06:03,580 --> 00:06:05,700 prvky v konštantnom čase. 132 00:06:05,700 --> 00:06:08,975 A v skutočnosti, to je niečo napovedalo ďalšie cena, ktorú platíme s 133 00:06:08,975 --> 00:06:09,760 spájať zoznam. 134 00:06:09,760 --> 00:06:13,890 >> Čo sa stane s dobou chodu niečo ako hľadať, keď chcem 135 00:06:13,890 --> 00:06:17,270 nájsť nejakú hodnotu a vnútro prepojeného zoznamu? 136 00:06:17,270 --> 00:06:20,290 Čo mi beží čas stáť? 137 00:06:20,290 --> 00:06:21,560 Veľký O n 138 00:06:21,560 --> 00:06:24,060 Ak je to triedené? 139 00:06:24,060 --> 00:06:25,440 Čo v prípade, že dátová štruktúra je triediť? 140 00:06:25,440 --> 00:06:28,640 Môžem robiť lepšie ako veľké O z n pre vyhľadávanie? 141 00:06:28,640 --> 00:06:31,700 Nie, pretože v najhoršom prípade by to mohlo veľmi dobre byť triedené, ale počet 142 00:06:31,700 --> 00:06:32,950 hľadáte by mohla byť veľká. 143 00:06:32,950 --> 00:06:35,370 To by mohlo byť číslo 100, ktorá Môže sa stať, že všetky 144 00:06:35,370 --> 00:06:36,410 ako na konci. 145 00:06:36,410 --> 00:06:39,950 A pretože môžete pristupovať iba viazané Zoznam v tomto prevedení by 146 00:06:39,950 --> 00:06:42,690 spôsob jeho prvého uzla, ste ešte trochu smolu. 147 00:06:42,690 --> 00:06:47,450 Musíte prejsť celú vec od začiatku až do konca, aby bolo možné nájsť 148 00:06:47,450 --> 00:06:49,150 že veľké hodnoty ako 100. 149 00:06:49,150 --> 00:06:51,350 Alebo zistiť, či je to ani tam. 150 00:06:51,350 --> 00:06:55,960 >> Takže môžeme robiť to, čo algoritmus v dátovom štruktúra, ktorá vyzerá takto? 151 00:06:55,960 --> 00:06:59,460 Nemôžeme urobiť binárne vyhľadávanie, pretože binárne hľadanie vyžaduje, aby sme mali 152 00:06:59,460 --> 00:07:00,740 náhodný prístup. 153 00:07:00,740 --> 00:07:04,500 Mohli by sme vyskočiť z miesta na umiestnenie bez nutnosti sledovať 154 00:07:04,500 --> 00:07:07,080 Tieto strúhanka vo forme všetkých týchto ukazovateľov. 155 00:07:07,080 --> 00:07:08,300 >> Teraz, ako sme to realizovať? 156 00:07:08,300 --> 00:07:12,830 No, či pôjdeme na obrazovku tu, ak je môžeme rýchlo implementujeme tieto dáta 157 00:07:12,830 --> 00:07:13,440 štruktúra - 158 00:07:13,440 --> 00:07:15,670 môj rukopis to nie je všetko, že skvelé tu, ale skúsime to. 159 00:07:15,670 --> 00:07:22,030 Takže typedef struct, a čo som chcete volať tú vec tu? 160 00:07:22,030 --> 00:07:22,960 Uzol. 161 00:07:22,960 --> 00:07:24,580 Takže budem sa nám začalo. 162 00:07:24,580 --> 00:07:27,860 A teraz, čo je potrebné, aby sa vo vnútri dátová štruktúra pre ktoré samostatne 163 00:07:27,860 --> 00:07:28,430 komunikačné zoznam? 164 00:07:28,430 --> 00:07:29,950 Koľko pole? 165 00:07:29,950 --> 00:07:30,450 >> Tak dva. 166 00:07:30,450 --> 00:07:31,570 Jedným z nich je celkom jednoduché. 167 00:07:31,570 --> 00:07:33,050 Tak int n 168 00:07:33,050 --> 00:07:35,930 A tak by sme mohli nazývať n čo chceme, ale mal by byť int, či sme 169 00:07:35,930 --> 00:07:37,660 vykonávanie spájať zoznam pre ints. 170 00:07:37,660 --> 00:07:41,920 A teraz, čo robí druhá poľa musí byť? 171 00:07:41,920 --> 00:07:43,460 Struct node *. 172 00:07:43,460 --> 00:07:50,570 Takže keď som to struct uzol * a potom som Môžete volať aj to, čo chcem, 173 00:07:50,570 --> 00:07:53,510 ale len aby bolo jasno, zavolám je ďalší, ako sme robili. 174 00:07:53,510 --> 00:07:55,270 A potom som zavriem zložené zátvorky. 175 00:07:55,270 --> 00:08:00,700 >> A teraz, ako minule, Dal som uzol dole. 176 00:08:00,700 --> 00:08:03,830 Ale keď som dokladá, že toto je uzol, prečo som sa obťažovať, že je tak 177 00:08:03,830 --> 00:08:07,320 verbose tu deklarovať struct uzol * ďalšie, na rozdiel od 178 00:08:07,320 --> 00:08:09,210 len na uzle * ďalšie? 179 00:08:09,210 --> 00:08:09,904 Jo? 180 00:08:09,904 --> 00:08:12,810 >> DIVÁKOV: [nepočuteľné]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID Malan: Presne tak. 182 00:08:14,050 --> 00:08:14,530 Presne tak. 183 00:08:14,530 --> 00:08:18,320 Pretože C naozaj vás doslova a vidí iba definíciu uzla 184 00:08:18,320 --> 00:08:21,230 cesta sem, nemôžete odkazovať sa na to tu. 185 00:08:21,230 --> 00:08:24,760 Takže máme tento druh preemptivní Vyhlásenie tu, čo je síce 186 00:08:24,760 --> 00:08:25,390 viac verbose. 187 00:08:25,390 --> 00:08:27,810 Struct uzol, to znamená, že môžeme teraz pristupovať 188 00:08:27,810 --> 00:08:29,760 vnútri dátové štruktúry. 189 00:08:29,760 --> 00:08:33,370 >> A ako stranou, pretože to je stáva trochu subjektívne teraz, 190 00:08:33,370 --> 00:08:36,230 hviezda technicky možné ísť sem, to môže ísť sem, môže 191 00:08:36,230 --> 00:08:37,179 dokonca ísť v stredu. 192 00:08:37,179 --> 00:08:39,890 Sme prijala v štýle príručke pre Samozrejme, že konvencie uvedenie 193 00:08:39,890 --> 00:08:42,299 hviezda vedľa údajov typu, ktorý je v tomto prípade, 194 00:08:42,299 --> 00:08:43,460 by struct uzol. 195 00:08:43,460 --> 00:08:46,620 Ale realizovať v mnohých učebniciach a on-line odkazy, môžete skutočne 196 00:08:46,620 --> 00:08:48,450 vidieť, že na druhej strane. 197 00:08:48,450 --> 00:08:52,200 Ale len si uvedomiť, že ako bude v skutočnosti práce a vy by ste mali byť jednoducho 198 00:08:52,200 --> 00:08:52,970 konzistentné. 199 00:08:52,970 --> 00:08:53,580 >> Dobrá. 200 00:08:53,580 --> 00:08:55,630 Tak to bolo naše vyhlásenie of struct uzla. 201 00:08:55,630 --> 00:08:59,430 Ale potom sme začali robiť viac sofistikované veci. 202 00:08:59,430 --> 00:09:03,410 Napríklad sme sa rozhodli zaviesť niečo ako tabuľky hash. 203 00:09:03,410 --> 00:09:08,160 Takže tu je hash tabuľka veľkosti n, indexované od 0 vľavo hore na n 204 00:09:08,160 --> 00:09:09,690 mínus 1 vľavo dole. 205 00:09:09,690 --> 00:09:11,640 To by mohlo byť hash tabuľka na čokoľvek. 206 00:09:11,640 --> 00:09:15,340 Ale to, čo veľa vecí sme sa hovoriť o použitie hash tabuľku? 207 00:09:15,340 --> 00:09:18,370 Uloženie čo? 208 00:09:18,370 --> 00:09:18,800 >> Mená. 209 00:09:18,800 --> 00:09:20,870 Mohli by sme mená ako sme minule. 210 00:09:20,870 --> 00:09:22,200 A naozaj, môžete uložiť čokoľvek. 211 00:09:22,200 --> 00:09:24,640 A uvidíme to znova PHP a JavaScriptu. 212 00:09:24,640 --> 00:09:28,550 Hash tabuľky je pekný druh Swiss Armádny nôž, ktorý vám umožní ukladať 213 00:09:28,550 --> 00:09:33,690 skoro čo chcete vo vnútri je to tým, že združí kľúče s hodnotami. 214 00:09:33,690 --> 00:09:34,770 Klávesy s hodnotami. 215 00:09:34,770 --> 00:09:37,800 >> Teraz v tomto jednoduchom prípade, naše Kľúče sú len čísla. 216 00:09:37,800 --> 00:09:40,380 Sme vykonávanie hash tabuľka ako pole. 217 00:09:40,380 --> 00:09:43,500 A tak sú kľúče 0, 1, 2, a tak ďalej. 218 00:09:43,500 --> 00:09:47,200 A tak my, ako ľudia, rozhodla posledná týždeň, že viete, čo, keď sme 219 00:09:47,200 --> 00:09:50,410 bude ukladať mená, jednoducho ľubovoľne, ale celkom rozumne, 220 00:09:50,410 --> 00:09:54,680 Predpokladám, že Alice, názov, bude len byť indexované do 0. 221 00:09:54,680 --> 00:09:58,030 A Bob, názov B, budú indexované do 1, a tak ďalej. 222 00:09:58,030 --> 00:10:02,490 Takže sme museli mapovanie medzi vstupmi, ktoré sú reťazca a hash 223 00:10:02,490 --> 00:10:04,560 umiestnenia, ktoré sú čísla. 224 00:10:04,560 --> 00:10:07,740 >> Tak, že proces je všeobecne známy ako hašovacej funkcie, a môžete skutočne 225 00:10:07,740 --> 00:10:09,130 implementovať v kóde. 226 00:10:09,130 --> 00:10:12,080 Ak by som chcel implementovať funkcie hash že robí presne to, čo sme 227 00:10:12,080 --> 00:10:17,070 práve popísal, od minule, by som mohol deklarovať funkciu, ktorá berie ako 228 00:10:17,070 --> 00:10:18,330 vstup napríklad - 229 00:10:18,330 --> 00:10:22,190 a ideme na to na to Obrazovka sem. 230 00:10:22,190 --> 00:10:26,180 Ak by som chcel realizovať hash funkcie, mohol by som povedať, 231 00:10:26,180 --> 00:10:27,410 niečo také. 232 00:10:27,410 --> 00:10:29,030 >> Bude to vrátiť int. 233 00:10:29,030 --> 00:10:33,600 Bude to nazvať hash, a to bude akceptovať ako argument 234 00:10:33,600 --> 00:10:38,920 reťazec, alebo to môže byť vhodnejšie teraz, a hovoriť char *, budeme hovoriť to. 235 00:10:38,920 --> 00:10:43,840 A potom táto funkcia má čo do činenia, nakoniec sa vrátiť int. 236 00:10:43,840 --> 00:10:45,990 Teraz, ako to robí, ktoré by mohli nie je tak jasné. 237 00:10:45,990 --> 00:10:49,510 Idem na vykonanie tohto bez Forma kontroly chýb práve teraz. 238 00:10:49,510 --> 00:10:55,740 Idem len slepo hovoriť, vráti čo je na držiaku s 0, mínus, 239 00:10:55,740 --> 00:10:58,850 povedzme, kapitál bodkočiarkou. 240 00:10:58,850 --> 00:10:59,960 >> Totálne rozbité. 241 00:10:59,960 --> 00:11:02,620 Nie je to dokonalé, pretože jeden, čo keď to je null? 242 00:11:02,620 --> 00:11:04,000 Zlé veci sa bude diať. 243 00:11:04,000 --> 00:11:07,940 Po druhé, čo keď je prvé písmeno v tejto meno nie je veľké písmeno? 244 00:11:07,940 --> 00:11:09,860 To nie je dopadne z vrtov. 245 00:11:09,860 --> 00:11:11,970 To by mohlo byť malé písmeno alebo nie list vôbec. 246 00:11:11,970 --> 00:11:15,520 Takže absolútne priestor pre zlepšenie tu, ale to je základná myšlienka. 247 00:11:15,520 --> 00:11:19,010 >> Čo sme popísali v minulom týždni verbálne len proces mapovania Alicu 248 00:11:19,010 --> 00:11:23,360 0 a Bob sa 1 môže byť vyjadrená iste formulaically ako C 249 00:11:23,360 --> 00:11:24,320 funkcie tu. 250 00:11:24,320 --> 00:11:28,630 Zavolal znovu hash, vezme reťazec ako vstup, a potom nejako robí niečo 251 00:11:28,630 --> 00:11:31,020 s týmto vstup na výrobu výstupu. 252 00:11:31,020 --> 00:11:34,130 Nie na rozdiel od našej čiernej skrinky popis že sme dlho urobiť. 253 00:11:34,130 --> 00:11:36,550 Neviem, ako by to mohlo byť pracuje pod kapotou. 254 00:11:36,550 --> 00:11:40,120 >> Pre problémové sady 6, jeden z problémov, je pre vás rozhodnúť, čo 255 00:11:40,120 --> 00:11:41,920 Váš hashovacie funkcia môže byť? 256 00:11:41,920 --> 00:11:45,760 Čo bude vo vnútri, že čierna box, a pravdepodobne, bude to 257 00:11:45,760 --> 00:11:50,380 trochu zaujímavejšie než to, a rozhodne náchylnejšie k chybám 258 00:11:50,380 --> 00:11:53,180 kontroly, ako je táto konkrétna implementácia. 259 00:11:53,180 --> 00:11:54,580 >> Ale problémy môžu nastať, že jo? 260 00:11:54,580 --> 00:11:57,760 Ak máme dátová štruktúra, ako je táto jeden, čo je jedným z problémov 261 00:11:57,760 --> 00:12:01,600 môžete naraziť na priebehu času vloženie stále viac a viac mien na 262 00:12:01,600 --> 00:12:02,880 hash tabuľky? 263 00:12:02,880 --> 00:12:04,630 Získate kolízie, nie? 264 00:12:04,630 --> 00:12:07,560 Čo keď máte Alice a Árona, dvaja ľudia, ktorých mená sa stalo 265 00:12:07,560 --> 00:12:08,190 začať? 266 00:12:08,190 --> 00:12:11,660 To vyvoláva otázku, kde sa dal druhý taký názov? 267 00:12:11,660 --> 00:12:15,050 >> No, možno naivne, jednoducho dať kde Bob patrí, ale potom Bob 268 00:12:15,050 --> 00:12:17,300 druh skrutkované, ak sa pokúsite vložte svoje meno a ďalšie 269 00:12:17,300 --> 00:12:18,240 nie je miesto pre neho. 270 00:12:18,240 --> 00:12:21,400 Takže môžete dať Bob, kde Charlie je, a môžete si to predstaviť veľmi rýchlo 271 00:12:21,400 --> 00:12:23,020 prevedie do trochu neporiadok. 272 00:12:23,020 --> 00:12:25,600 Niečo lineárne na konci, kde sa stačí hľadať na celú vec 273 00:12:25,600 --> 00:12:28,190 Hľadám Alice alebo Bob alebo Aaron a Charlie. 274 00:12:28,190 --> 00:12:33,230 >> Tak namiesto toho navrhuje, namiesto toho, aby len lineárne snímanie pre priestranstva 275 00:12:33,230 --> 00:12:36,450 a plopping mená tam sme navrhla milovník prístup. 276 00:12:36,450 --> 00:12:41,740 Hash tabuľky realizované stále s rad indexov, ale dátový typ 277 00:12:41,740 --> 00:12:44,500 tieto indexy teraz boli ukazovatele. 278 00:12:44,500 --> 00:12:47,360 Ukazovatele k čomu? 279 00:12:47,360 --> 00:12:48,730 Ukazovatele na lineárnymi zoznamy. 280 00:12:48,730 --> 00:12:53,330 >> Vzhľadom k tomu, pripomínajú, že spájať zoznam je naozaj len ukazovateľ na uzol, a 281 00:12:53,330 --> 00:12:57,110 uzol má ďalšie pole, a že uzol má ďalšie pole, a tak ďalej. 282 00:12:57,110 --> 00:13:00,690 Takže teraz môžete myslieť na tomto poli na ľavá strana tabuľky hash ako 283 00:13:00,690 --> 00:13:01,820 čo vedie k prepojeného zoznamu. 284 00:13:01,820 --> 00:13:07,000 Výhodou je, ak máte kolízie medzi Alicou a Áronovi: 285 00:13:07,000 --> 00:13:09,300 Čo robíte s druhý taký človek? 286 00:13:09,300 --> 00:13:14,150 Môžete len pripojiť ho, aby koniec, alebo dokonca na začiatku 287 00:13:14,150 --> 00:13:15,490 tohto prepojeného zoznamu. 288 00:13:15,490 --> 00:13:17,340 >> A vlastne, povedzme, cez rezance že len druhý. 289 00:13:17,340 --> 00:13:18,640 Ak by najväčší zmysel? 290 00:13:18,640 --> 00:13:22,060 Ak vložím Alicu a ona končí Na prvom mieste, potom sa snažím, aby 291 00:13:22,060 --> 00:13:25,310 vložiť Aaron meno, a tam je samozrejme kolízie, mal som 292 00:13:25,310 --> 00:13:27,400 ho na začiatku prepojeného zoznamu? 293 00:13:27,400 --> 00:13:30,944 To je v tomto prvom mieste, alebo na konci? 294 00:13:30,944 --> 00:13:31,440 >> DIVÁKOV: [nepočuteľné]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID Malan: OK. 296 00:13:31,990 --> 00:13:32,490 Počul som, že na začiatku. 297 00:13:32,490 --> 00:13:33,903 Preto sa už na začiatku? 298 00:13:33,903 --> 00:13:34,750 >> DIVÁKOV: [nepočuteľné]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID Malan: OK. 300 00:13:34,940 --> 00:13:36,520 Je to podľa abecedy, tak to je pekné. 301 00:13:36,520 --> 00:13:37,330 To je dobrá vlastnosť. 302 00:13:37,330 --> 00:13:39,335 To vám ušetrí mi čas potenciálne. 303 00:13:39,335 --> 00:13:43,290 To mi nedovolí robiť binárne vyhľadávanie, ale ja by aspoň byť schopný vymaniť sa 304 00:13:43,290 --> 00:13:47,340 zo slučky, keď si uvedomujem, no, ja som cesta minulosti sa Aaron by v tomto 305 00:13:47,340 --> 00:13:48,310 radené prepojeného zoznamu. 306 00:13:48,310 --> 00:13:50,360 Nemám strácať čas hľadaním až do konca. 307 00:13:50,360 --> 00:13:51,530 Tak to je rozumné. 308 00:13:51,530 --> 00:13:54,710 Prečo inak by mohlo chcete vložiť kolízie názov na 309 00:13:54,710 --> 00:13:56,660 na začiatku zoznamu? 310 00:13:56,660 --> 00:13:57,397 Čo je to? 311 00:13:57,397 --> 00:13:58,680 >> DIVÁKOV: [nepočuteľné]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID Malan: Mohlo by to trvať dlho dostať sa na koniec zoznamu. 313 00:14:00,820 --> 00:14:02,490 A v skutočnosti, dlhšie a dlhšie. 314 00:14:02,490 --> 00:14:04,920 Čím viac mien, ktoré vložíte začiatok, dlhšia než 315 00:14:04,920 --> 00:14:06,280 reťaz dostane. 316 00:14:06,280 --> 00:14:07,890 Čím dlhšie tú, ktorá súvisí Zoznam je dostane. 317 00:14:07,890 --> 00:14:09,420 Takže ste naozaj len strácaš čas. 318 00:14:09,420 --> 00:14:14,070 Možno, že ste na tom lepšie udržiavať konštantný Čas vloženia, veľký O z 1, 319 00:14:14,070 --> 00:14:18,470 tým, že vždy dávať narážajúce na názov počiatok prepojeného zoznamu, 320 00:14:18,470 --> 00:14:21,230 a nie toľko znepokojujúce o triedení. 321 00:14:21,230 --> 00:14:22,600 >> Aký je najlepší odpoveď? 322 00:14:22,600 --> 00:14:23,320 Je to jasné. 323 00:14:23,320 --> 00:14:26,140 To druh závisí na tom, čo distribúcie je to, čo je vzor 324 00:14:26,140 --> 00:14:27,850 mená vkladáte. 325 00:14:27,850 --> 00:14:29,430 To nemusí byť nutne jasná odpoveď. 326 00:14:29,430 --> 00:14:33,100 Ale tu je opäť design príležitosť. 327 00:14:33,100 --> 00:14:37,220 >> Tak sme potom sa pozrel na tú vec, ktorá je naozaj iná veľká príležitosť 328 00:14:37,220 --> 00:14:38,180 pre p-set 6. 329 00:14:38,180 --> 00:14:41,770 A uvedomiť si, ak ste tak už neurobili, Zamyla sa ponorí do oboch z nich, hashovacie 330 00:14:41,770 --> 00:14:43,260 tabuľky a snaží sa, vo viacerých detailu. 331 00:14:43,260 --> 00:14:45,630 A video návod je vložené do p-set spec. 332 00:14:45,630 --> 00:14:46,590 To bol trie - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. A čo bolo zaujímavé, bolo to, že čas prevádzky 334 00:14:51,670 --> 00:14:59,510 Nie je potrebné hľadať mená, ako je Maxwell Minule bol veľký O čoho? 335 00:14:59,510 --> 00:15:01,040 Čo je to? 336 00:15:01,040 --> 00:15:01,920 >> Divákov: počet písmen. 337 00:15:01,920 --> 00:15:02,550 >> DAVID Malan: počet písmen. 338 00:15:02,550 --> 00:15:03,210 Počul som dve veci. 339 00:15:03,210 --> 00:15:04,630 Počet písmen a konštantnom čase. 340 00:15:04,630 --> 00:15:05,540 Takže poďme sa, že ako prvý. 341 00:15:05,540 --> 00:15:06,410 Počet písmen. 342 00:15:06,410 --> 00:15:10,195 No, to dátová štruktúra, odvolanie, je ako strom, rodokmeň, každý z 343 00:15:10,195 --> 00:15:12,860 ktorých uzly sú tvorené poli. 344 00:15:12,860 --> 00:15:16,300 A tie polia sú odkazy na iné takéto uzly, či iné podobné 345 00:15:16,300 --> 00:15:17,670 poľa vo stromu. 346 00:15:17,670 --> 00:15:22,890 >> Takže ak by sme chceli potom určujú či Maxwell je tu, mohol by som ísť 347 00:15:22,890 --> 00:15:26,890 na prvé pole, na samom vrchole strom, tzv koreň, horná časť 348 00:15:26,890 --> 00:15:30,521 trie a postupujte ukazovateľ m, potom ukazovateľ, potom x, 349 00:15:30,521 --> 00:15:31,710 w, e, l, l 350 00:15:31,710 --> 00:15:34,910 A potom, keď vidím nejaký špeciálny symbol, označený tu ako trojuholník. 351 00:15:34,910 --> 00:15:38,480 V kóde uvidíte, že navrhne, aby si implementovaný ako bool, len hovorím áno 352 00:15:38,480 --> 00:15:40,540 alebo nie, slovo, tu zastaví. 353 00:15:40,540 --> 00:15:45,270 >> No, raz sme išli do M-A-X-W-E-L-L, pocit, sedem, možno 354 00:15:45,270 --> 00:15:48,910 osem keď ideme jeden okolo nej osem kroky na nájdenie Maxwell. 355 00:15:48,910 --> 00:15:53,050 Alebo povedzme, že K. Ale spomínam posledný čas, som tvrdil, že v prípade, že je 356 00:15:53,050 --> 00:15:57,540 realisticky maximálna dĺžka na slovo, rovnako ako 40-niektoré-nepárne znaky, 357 00:15:57,540 --> 00:16:00,810 Maximálna dĺžka znamená, konštantnú hodnotu. 358 00:16:00,810 --> 00:16:05,770 Takže naozaj, áno, je to technicky veľký O 8 alebo 7, alebo naozaj veľký O K. Ale 359 00:16:05,770 --> 00:16:09,420 v prípade, že je konečný limit na to, čo K môže byť, že je konštantná. 360 00:16:09,420 --> 00:16:12,080 A tak je to veľký O z 1 na konci dňa. 361 00:16:12,080 --> 00:16:13,040 >> Nie je v reálnom svete. 362 00:16:13,040 --> 00:16:15,960 Nie, keď skutočne začať sledovať vaše hodiny, ako váš program beží. 363 00:16:15,960 --> 00:16:20,690 Je to úplne to bude trochu pomalší než skutočne konštantná 364 00:16:20,690 --> 00:16:21,840 čas na jeden krok. 365 00:16:21,840 --> 00:16:25,540 Bude to sedem alebo osem stupňov, ale stále je to oveľa, oveľa lepšie 366 00:16:25,540 --> 00:16:30,080 než algoritmu, ako je veľký O N, ktorý závisí na veľkosti, čo je v 367 00:16:30,080 --> 00:16:31,220 dátové štruktúry. 368 00:16:31,220 --> 00:16:34,970 >> Všimnite si, že tu je hore, môžeme vložiť miliónkrát viac mien do tohto 369 00:16:34,970 --> 00:16:38,170 dátová štruktúra, ale koľko krokov to bude trvať nám nájsť 370 00:16:38,170 --> 00:16:40,480 Maxwell v tomto prípade? 371 00:16:40,480 --> 00:16:40,780 Žiadne. 372 00:16:40,780 --> 00:16:41,820 On je nedotknutá. 373 00:16:41,820 --> 00:16:45,480 A k dnešnému dňu, nemyslím si, že sme videli, príklad dátovej štruktúry alebo 374 00:16:45,480 --> 00:16:48,560 algoritmus, ktorý bol úplne ovplyvnená vonkajšie 375 00:16:48,560 --> 00:16:50,040 správanie, ako je to. 376 00:16:50,040 --> 00:16:51,160 Ale to nemôže byť úžasné. 377 00:16:51,160 --> 00:16:52,900 To nemôže byť jediným riešením pre p-set 378 00:16:52,900 --> 00:16:53,570 >> A to nie. 379 00:16:53,570 --> 00:16:55,980 To nie je nevyhnutne dáta Štruktúra by ste mali tiahnuť k, 380 00:16:55,980 --> 00:16:58,220 pretože rovnako ako tabuľky hash, kompromis. 381 00:16:58,220 --> 00:17:00,500 Čo je to cena, ktorú zaplatíte tu? 382 00:17:00,500 --> 00:17:00,940 Pamäť. 383 00:17:00,940 --> 00:17:02,890 Myslím, že je to otrasné množstvo pamäti. 384 00:17:02,890 --> 00:17:05,569 A môžete tak celkom vidieť tu, pretože autor obrázku 385 00:17:05,569 --> 00:17:09,420 samozrejme skrátený všetkých polí a my nevidíme veľa a je 386 00:17:09,420 --> 00:17:12,700 Hostely a C je a Q je a Y je a Z je v týchto poliach. 387 00:17:12,700 --> 00:17:13,630 Ale sú tam. 388 00:17:13,630 --> 00:17:17,660 >> Každý z týchto uzlov je celý súbor niektorých 26 alebo viac bytov, z ktorých každá 389 00:17:17,660 --> 00:17:19,170 čo predstavuje list. 390 00:17:19,170 --> 00:17:22,920 27 V našom prípade, tak, že môže podporovať apostrofy v sade problém. 391 00:17:22,920 --> 00:17:27,030 Tak to dátová štruktúra je naozaj, naozaj hustý a široký. 392 00:17:27,030 --> 00:17:30,880 A to samo o sebe by mohlo skončiť spomaľuje veci dole, alebo aspoň vás to stálo 393 00:17:30,880 --> 00:17:32,240 oveľa viac priestoru. 394 00:17:32,240 --> 00:17:34,020 Ale znova, môžeme vyvodiť porovnanie tu. 395 00:17:34,020 --> 00:17:39,190 >> Spomínam si na chvíľu späť, sme dosiahli oveľa viac vzrušujúce doba chodu pri triedení 396 00:17:39,190 --> 00:17:42,880 keď použijeme zlúčenie druh, ale cena sme zaplatili dosiahnuť n log n o zlúčení 397 00:17:42,880 --> 00:17:46,930 druh vyžaduje, aby trávime viac aký zdroj? 398 00:17:46,930 --> 00:17:47,690 Viac priestoru. 399 00:17:47,690 --> 00:17:50,530 Potrebovali sme sekundárne maticu kopírovať ľudí do, rovnako ako 400 00:17:50,530 --> 00:17:51,620 sme tu na javisku. 401 00:17:51,620 --> 00:17:55,880 Takže znova, žiadne jasné víťaza, ale len subjektívne konštrukcie 402 00:17:55,880 --> 00:17:57,710 rozhodnutie byť robený. 403 00:17:57,710 --> 00:17:58,060 >> Dobrá. 404 00:17:58,060 --> 00:17:59,130 Takže ako na to? 405 00:17:59,130 --> 00:18:02,050 Každý, kto spoznať, ktoré D-Hall? 406 00:18:02,050 --> 00:18:02,440 OK. 407 00:18:02,440 --> 00:18:03,170 Takže tri z nás. 408 00:18:03,170 --> 00:18:03,750 Mather dom. 409 00:18:03,750 --> 00:18:05,070 Tak to je pre stolovanie Mather je. 410 00:18:05,070 --> 00:18:09,650 Stavím sa, že všetky jedálne majú hromady zásobníkov, ako je tento. 411 00:18:09,650 --> 00:18:11,950 A to je skutočne reprezentatívna o niečo, čo sme 412 00:18:11,950 --> 00:18:13,050 zrejme už videli. 413 00:18:13,050 --> 00:18:14,850 Nazvali sme ju doslova hromadu. 414 00:18:14,850 --> 00:18:18,970 A stack, pokiaľ ide o váš pamäti počítača, je miesto, kde prejde dáta 415 00:18:18,970 --> 00:18:20,460 zatiaľ čo funkcia volaná. 416 00:18:20,460 --> 00:18:23,410 >> Napríklad, aké druhy vecí ísť na zásobníku s ohľadom na 417 00:18:23,410 --> 00:18:27,420 Rozloženie pamäte sme diskutovali v týždňoch minulých? 418 00:18:27,420 --> 00:18:28,736 Čo je to? 419 00:18:28,736 --> 00:18:29,670 >> DIVÁKOV: Volanie funkcie. 420 00:18:29,670 --> 00:18:30,260 >> DAVID Malan: Ospravedlňujem sa. 421 00:18:30,260 --> 00:18:31,210 >> DIVÁKOV: Volanie funkcie. 422 00:18:31,210 --> 00:18:33,590 >> DAVID Malan: Volanie funkcie, ale konkrétne, čo je vo vnútri každého 423 00:18:33,590 --> 00:18:35,340 tie rámy? 424 00:18:35,340 --> 00:18:37,220 Aké veci? 425 00:18:37,220 --> 00:18:37,460 Jo. 426 00:18:37,460 --> 00:18:38,500 Takže lokálne premenné. 427 00:18:38,500 --> 00:18:43,080 Kedykoľvek sme potrebovali nejakú miestne úložisko, ako argument, alebo int I, alebo int 428 00:18:43,080 --> 00:18:45,940 temp, alebo čokoľvek miestnej premenná, boli sme 429 00:18:45,940 --> 00:18:47,210 uvedenie, že na zásobníku. 430 00:18:47,210 --> 00:18:49,610 A hovoríme, že stack, pretože tohto vrstvenie myšlienky. 431 00:18:49,610 --> 00:18:52,940 Len trochu zhoduje s realitou, Koncept tohto rozhodnutia. 432 00:18:52,940 --> 00:18:56,650 >> Ale ukazuje sa, že zásobník možno tiež pozerať ako na dátové štruktúry, 433 00:18:56,650 --> 00:19:00,110 Alternatívou k poľu, alternatívne do prepojeného zoznamu. 434 00:19:00,110 --> 00:19:02,770 Niečo koncepčne zaujímavejšie že môže byť stále 435 00:19:02,770 --> 00:19:06,030 realizovaný pomocou niektoré z tých, veci, ale je to iný typ 436 00:19:06,030 --> 00:19:09,140 dátová štruktúra podporu, naozaj, iba dve operácie. 437 00:19:09,140 --> 00:19:11,000 Ale môžete pridať na milovník funkcie než tie. 438 00:19:11,000 --> 00:19:12,180 Ale to sú základy - 439 00:19:12,180 --> 00:19:13,510 tlačiť a pop. 440 00:19:13,510 --> 00:19:19,240 >> A nápad s hromadou je, že keď som sú tu, s alebo bez Annenberg 441 00:19:19,240 --> 00:19:22,880 vedel, zásobník od vedľa s číslom 9 na ňom. 442 00:19:22,880 --> 00:19:23,870 Takže len int. 443 00:19:23,870 --> 00:19:26,990 A ja chcem, aby sa zasadila to na dátach štruktúra, ktorá v súčasnej dobe je prázdny. 444 00:19:26,990 --> 00:19:28,790 Zoberme si to v spodnej časti zásobníka. 445 00:19:28,790 --> 00:19:33,150 Ja by som tlačiť toto číslo 9 na stack, a teraz je to tu. 446 00:19:33,150 --> 00:19:36,040 >> Ale zaujímavá vec o zásobníku je, že keď som chcel, aby sa zasadila 447 00:19:36,040 --> 00:19:40,210 niektoré ďalšie hodnoty, ako 17, a tlačím to do zásobníka, budem robiť 448 00:19:40,210 --> 00:19:43,290 iba intuitívne vec, ja som jednoducho ísť Aby som to presne tam, kde ľudia 449 00:19:43,290 --> 00:19:45,180 by mať tendenciu dať na povrch. 450 00:19:45,180 --> 00:19:48,850 Ale čo je zaujímavé, teraz je, ako sa dostanem na 9? 451 00:19:48,850 --> 00:19:50,670 Viete, ja nie bez nejakej námahy. 452 00:19:50,670 --> 00:19:54,070 >> Takže to, čo je na tom zaujímavé zásobník, ktorý je zo svojej podstaty 453 00:19:54,070 --> 00:19:56,330 Je to štruktúra dát LIFO. 454 00:19:56,330 --> 00:19:59,680 Silly spôsob, ako popisovať posledný dnu, prvý von. 455 00:19:59,680 --> 00:20:03,280 Takže posledné číslo V tejto dobe bolo 17 rokov. 456 00:20:03,280 --> 00:20:07,540 Takže keď chcem niečo pop off zo zásobníka, môže to byť iba 17. 457 00:20:07,540 --> 00:20:11,890 Takže je povinný poriadok pôsobenia u nás, kde je posledná položka 458 00:20:11,890 --> 00:20:14,260 musí byť v prvej von. 459 00:20:14,260 --> 00:20:16,440 Preto je skratka, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Tak prečo by to mohlo byť užitočné? 461 00:20:19,160 --> 00:20:22,690 Sú ich kontexty, v ktorých by si Chcete dátovú štruktúru, ako je tento? 462 00:20:22,690 --> 00:20:24,810 No, je to určite užitočné, vnútri počítača. 463 00:20:24,810 --> 00:20:29,050 Takže operačné systémy jednoznačne použiť Druh údajovej štruktúry pre komíny. 464 00:20:29,050 --> 00:20:32,800 Budeme tiež vidieť rovnakú myšlienku pokiaľ ide o webové stránky. 465 00:20:32,800 --> 00:20:35,890 Takže tento týždeň a budúci týždeň a ďalej, a ako začať vykonávať web 466 00:20:35,890 --> 00:20:39,490 stránky v jazyku HTML s názvom, môžete vlastne používať dátovú štruktúru, ako je 467 00:20:39,490 --> 00:20:42,690 to, či stránka je v správnom formáte. 468 00:20:42,690 --> 00:20:47,170 Vzhľadom k tomu, uvidíme všetky webové stránky postupujte podľa určitá hierarchia, odsadenie 469 00:20:47,170 --> 00:20:52,030 , Že sa na konci dňa, sa stromová štruktúra pod kapotou. 470 00:20:52,030 --> 00:20:53,620 Tak o tom viac v len trochu. 471 00:20:53,620 --> 00:20:56,560 >> Ale teraz, poďme navrhnúť pre Moment, ako by sme mohli ísť o 472 00:20:56,560 --> 00:20:58,830 predstavuje to, čo je stoh? 473 00:20:58,830 --> 00:21:03,370 Dovoľte mi navrhnúť, že by sme realizovať zásobník s kódom, ako je tento. 474 00:21:03,370 --> 00:21:07,990 Takže zásobník bude mať vnútri nej dve veci, polia, tzv vaničky, 475 00:21:07,990 --> 00:21:09,510 len aby bol v súlade s demo. 476 00:21:09,510 --> 00:21:12,660 A každá z položiek v tomto poli bude typu int. 477 00:21:12,660 --> 00:21:14,740 A kapacita je pravdepodobne to, čo? 478 00:21:14,740 --> 00:21:18,796 Pretože som nepísal úplná definícia tu. 479 00:21:18,796 --> 00:21:21,535 >> Je to asi maximum Veľkosť poľa. 480 00:21:21,535 --> 00:21:25,150 A je to asi deklarovaný ako ostrý definovať v hornej časti súboru, niektoré 481 00:21:25,150 --> 00:21:28,450 druh konštantný ako vyplýva z samotná kapitalizácie. 482 00:21:28,450 --> 00:21:32,250 Takže niekde kapacita je definovaná ako maximálnu možnú veľkosť. 483 00:21:32,250 --> 00:21:35,590 Medzitým, vnútri dátové štruktúry známy ako zásobník sa bude 484 00:21:35,590 --> 00:21:38,630 byť celé číslo len známy jednoducho ako veľkosť. 485 00:21:38,630 --> 00:21:43,400 >> Takže ak by som mal reprezentovať to teraz obrazovo, predpokladajme, že tento 486 00:21:43,400 --> 00:21:48,070 Celá čierna skrinka predstavuje svoj stack. 487 00:21:48,070 --> 00:21:50,070 Vnútri nej sú dve premenné. 488 00:21:50,070 --> 00:21:54,780 Takže budem čerpať Prvý je napríklad veľkosť. 489 00:21:54,780 --> 00:21:57,420 A druhá idem kresliť ako pole. 490 00:21:57,420 --> 00:22:01,060 >> Ale len preto, aby sa veci riadne, Normálne by som nakresliť poľa ako 491 00:22:01,060 --> 00:22:04,910 , Ale je to celkom pekný ak budeme zodpovedať skutočnosti, alebo 492 00:22:04,910 --> 00:22:06,230 odpovedať mentálny model. 493 00:22:06,230 --> 00:22:12,880 Dovoľte mi teda namiesto toho vypracovať poľa vertikálne, čo je len opäť 494 00:22:12,880 --> 00:22:13,840 umelec stvárnenie. 495 00:22:13,840 --> 00:22:16,610 Nezáleží na tom, čo to je pod kapotou. 496 00:22:16,610 --> 00:22:20,350 A povieme, že v predvolenom nastavení kapacita bude tri. 497 00:22:20,350 --> 00:22:23,480 Takže to bude miesto 0, to bude namiesto 1, toto 498 00:22:23,480 --> 00:22:25,740 bude miesto 2. 499 00:22:25,740 --> 00:22:29,330 >> Keby som podplatiť s dôrazom loptou, by niekto chcel prísť a spustiť 500 00:22:29,330 --> 00:22:30,870 palubu tu na chvíľu? 501 00:22:30,870 --> 00:22:31,960 OK, videl vaša ruka ako prvý. 502 00:22:31,960 --> 00:22:33,950 Poď hore. 503 00:22:33,950 --> 00:22:36,500 Dobrá. 504 00:22:36,500 --> 00:22:38,760 Takže myslím, že je Steven. 505 00:22:38,760 --> 00:22:40,035 Poď hore. 506 00:22:40,035 --> 00:22:40,770 Dobrá. 507 00:22:40,770 --> 00:22:46,760 >> Ale predpokladajme, že teraz sme sa vrátiť a počiatočné stav sveta, kde som 508 00:22:46,760 --> 00:22:52,180 práve vyhlásil stack, a to bude mať kapacitu tri. 509 00:22:52,180 --> 00:22:54,470 Ale veľkosť nebola stanovená. 510 00:22:54,470 --> 00:22:56,100 Zásobníky nebola stanovená. 511 00:22:56,100 --> 00:22:57,300 Takže pár otázok ako prvý. 512 00:22:57,300 --> 00:23:01,310 A dovoľte mi, aby som vám mikrofón, takže môžete podieľať sa aktívnejšie na to. 513 00:23:01,310 --> 00:23:05,190 >> Takže to, čo je vnútri veľkosti v túto chvíľu včas, ak všetko, čo som urobil, je 514 00:23:05,190 --> 00:23:09,340 vyhlásený stoh jeden riadok kódu? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: Moc nie. 516 00:23:10,100 --> 00:23:12,080 >> DAVID Malan: OK, nič moc. 517 00:23:12,080 --> 00:23:14,410 Vieme, čo je vo vnútri veľkosti, vieme, čo je vo vnútri 518 00:23:14,410 --> 00:23:16,330 tohto poľa Si tu prvýkrát? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: Len náhodný kód, nie? 520 00:23:18,630 --> 00:23:20,220 Just - 521 00:23:20,220 --> 00:23:23,230 >> DAVID Malan: Jo, ja idem hovoria kód, ale náhodne - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: Veci. 523 00:23:23,820 --> 00:23:28,290 >> DAVID Malan: Veci, ako je náhodné 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: bity. 525 00:23:28,870 --> 00:23:29,530 >> DAVID Malan: Bity, že jo? 526 00:23:29,530 --> 00:23:31,190 Takže odpadky hodnoty, nie? 527 00:23:31,190 --> 00:23:33,470 Takže permutácie 0 a 1 je. 528 00:23:33,470 --> 00:23:35,920 Zvyšky predchádzajúcich zvyklostí tejto pamäte. 529 00:23:35,920 --> 00:23:38,150 A naozaj neviem, čo sa hodnoty sú, takže väčšinou je nakresliť 530 00:23:38,150 --> 00:23:38,930 ako otázniky. 531 00:23:38,930 --> 00:23:41,990 >> Takže prvá vec, že ​​sme pravdepodobne bude chcieť, aby to tu - 532 00:23:41,990 --> 00:23:46,630 a dovoľte mi, aby som toto pole vnútri odtiaľ názov - zásobníky. 533 00:23:46,630 --> 00:23:49,540 Čo by sme mali pravdepodobne inicializovať veľkostí, ak chceme 534 00:23:49,540 --> 00:23:51,040 začať používať túto stack? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Zásobník je pod 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID Malan: Tak OK. 537 00:23:53,910 --> 00:23:56,710 Aby bolo jasno, je deklarovaný výkon inde tri. 538 00:23:56,710 --> 00:23:58,570 A to je to, čo som používal alokovať pole. 539 00:23:58,570 --> 00:24:03,535 Veľkosť sa bude odkazovať na to, koľko zásobníky sú v súčasnej dobe na zásobníku. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: Zero. 541 00:24:03,880 --> 00:24:04,460 >> DAVID Malan: Tak to musí byť nula. 542 00:24:04,460 --> 00:24:07,760 Takže choďte do toho a s akýmkoľvek prstom, nakresliť nulu veľkosti. 543 00:24:07,760 --> 00:24:08,440 Dobrá. 544 00:24:08,440 --> 00:24:10,920 Takže teraz, čo je vo vnútri tohto tu, nevieme. 545 00:24:10,920 --> 00:24:12,160 Sú to naozaj len odpadky hodnoty. 546 00:24:12,160 --> 00:24:14,800 Takže by sme mohli čerpať otázniky, ale Skúsme udržať doska čistá teraz 547 00:24:14,800 --> 00:24:16,300 pretože nezáleží na tom, čo tam je. 548 00:24:16,300 --> 00:24:19,130 Nepotrebujeme k inicializácii poľa k ničomu, pretože ak vieme, že 549 00:24:19,130 --> 00:24:23,100 veľkosť zásobníka je nula, no, nesmie byť pri pohľade na niečo v 550 00:24:23,100 --> 00:24:25,590 Toto pole tak na tento bod v čase. 551 00:24:25,590 --> 00:24:29,970 >> Takže teraz, predpokladám, že tlačím číslo 9 do zásobníka. 552 00:24:29,970 --> 00:24:33,750 Ako by sme mali aktualizovať dátovú štruktúru Vnútri tejto čiernej skrinky? 553 00:24:33,750 --> 00:24:35,540 Aké hodnoty je potrebné zmeniť? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: V - 555 00:24:36,200 --> 00:24:37,400 veľkosť? 556 00:24:37,400 --> 00:24:37,650 >> DAVID Malan: OK. 557 00:24:37,650 --> 00:24:38,770 Veľkosť by mala byť čo? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Veľkosť by bol jeden. 559 00:24:39,580 --> 00:24:39,870 >> DAVID Malan: OK. 560 00:24:39,870 --> 00:24:41,110 Takže veľkosť by sa mala stať jedným. 561 00:24:41,110 --> 00:24:42,540 Takže si môžete urobiť v pár ohľadoch. 562 00:24:42,540 --> 00:24:46,920 Dovoľte mi, aby som vám teraz vaša Prst je guma. 563 00:24:46,920 --> 00:24:47,260 Dobrá. 564 00:24:47,260 --> 00:24:49,960 Tak teraz je prst kefu. 565 00:24:49,960 --> 00:24:50,330 Dobrá. 566 00:24:50,330 --> 00:24:52,820 A teraz, čo ešte sa musí zmeniť, Je zrejmé, že v dátovej štruktúre? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Ideme od zdola až 9. 568 00:24:57,060 --> 00:24:57,760 >> DAVID Malan: 9. 569 00:24:57,760 --> 00:24:58,420 OK, dobre. 570 00:24:58,420 --> 00:25:01,550 Takže ešte nezáleží, čo je v umiestnenie jeden alebo dva, pretože sú 571 00:25:01,550 --> 00:25:04,520 odpadky hodnoty, ale nemali by sme sa obťažovať hľadá tam, pretože veľkosť je 572 00:25:04,520 --> 00:25:07,540 nám hovorí, že iba prvý prvok je vlastne legitímna. 573 00:25:07,540 --> 00:25:10,400 Takže teraz tlačím 17 na zozname. 574 00:25:10,400 --> 00:25:11,830 Čo sa stane obrázku? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: Takže veľkosť sa chystá ísť na dva. 576 00:25:14,720 --> 00:25:15,300 >> DAVID Malan: OK. 577 00:25:15,300 --> 00:25:16,070 Ste guma - 578 00:25:16,070 --> 00:25:16,810 oops. 579 00:25:16,810 --> 00:25:18,026 Ste gumu. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Eraser. 581 00:25:18,840 --> 00:25:19,720 >> DAVID Malan: Si kefu. 582 00:25:19,720 --> 00:25:20,560 >> STEVEN: Brush. 583 00:25:20,560 --> 00:25:20,920 >> DAVID Malan: OK. 584 00:25:20,920 --> 00:25:21,600 A čo ešte? 585 00:25:21,600 --> 00:25:22,600 >> STEVEN: A potom sme - 586 00:25:22,600 --> 00:25:22,915 >> DAVID Malan: Usilovali sme 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Držíme 17 na vrchole, a preto - 588 00:25:24,760 --> 00:25:25,710 >> DAVID Malan: OK, dobre. 589 00:25:25,710 --> 00:25:27,040 >> STEVEN - klesnúť dole. 590 00:25:27,040 --> 00:25:27,530 >> DAVID Malan: Dobre. 591 00:25:27,530 --> 00:25:27,940 Začína to byť jednoduché. 592 00:25:27,940 --> 00:25:29,300 Nebudem, ktoré vám pomôžu tentokrát. 593 00:25:29,300 --> 00:25:30,510 Zatlačte 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: Hotovo. 595 00:25:31,720 --> 00:25:34,870 Štát gumu. 596 00:25:34,870 --> 00:25:37,340 Stávam sa štetcom. 597 00:25:37,340 --> 00:25:39,340 A potom dávam 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID Malan: 22. 599 00:25:40,100 --> 00:25:40,620 Výborný. 600 00:25:40,620 --> 00:25:41,380 Takže ešte raz. 601 00:25:41,380 --> 00:25:44,280 Ja som teraz bude tlačiť do zásobníka 26. 602 00:25:44,280 --> 00:25:46,350 >> STEVEN: Ooh. 603 00:25:46,350 --> 00:25:50,278 Ach bože. 604 00:25:50,278 --> 00:25:52,520 Naozaj ma zaskočila. 605 00:25:52,520 --> 00:25:53,703 >> DAVID Malan: To snáď nie pozri tento rok? 606 00:25:53,703 --> 00:25:55,930 >> STEVEN: Nevidel som to blíži. 607 00:25:55,930 --> 00:25:58,756 Mohli by sme znova počiatočná kapacita? 608 00:25:58,756 --> 00:25:59,790 >> DAVID Malan: To je dobrá otázka. 609 00:25:59,790 --> 00:26:02,360 Takže sme trochu maľoval seba v rohu tu. 610 00:26:02,360 --> 00:26:06,740 Tam naozaj nie je dobrý pozor Steven pretože sme pridelené toto pole 611 00:26:06,740 --> 00:26:09,130 staticky, aby som tak povedal, vnútri z dátovej štruktúry. 612 00:26:09,130 --> 00:26:12,170 A my sme v podstate pevne zakódovaný sa, že je veľkosť tri. 613 00:26:12,170 --> 00:26:14,170 Takže naozaj nemôžeme prerozdelia ju. 614 00:26:14,170 --> 00:26:20,020 >> Mohli by sme, keby sme išli naspäť, sme obnovovaný zásobníky sa ukazovateľ, ktorý 615 00:26:20,020 --> 00:26:22,300 sme potom pomocou malloc do ruky pamäti. 616 00:26:22,300 --> 00:26:25,050 Pretože ak máme pamäť, z haldy pomocou malloc, sme 617 00:26:25,050 --> 00:26:26,430 by potom uvoľniť ho. 618 00:26:26,430 --> 00:26:29,630 Ale skôr, než ju uvoľní, mohli by sme prerozdeliť väčší kus pamäti, 619 00:26:29,630 --> 00:26:31,330 aktualizovať ukazovateľ, a tak ďalej. 620 00:26:31,330 --> 00:26:33,500 Ale teraz je to naozaj najlepšie, čo môžeme urobiť. 621 00:26:33,500 --> 00:26:36,360 Stlačte a pop sa pravdepodobne bude majú uviesť niektoré chyby. 622 00:26:36,360 --> 00:26:40,270 >> Tak napríklad, naše realizácie Push by sa mohol vrátiť bool, ktorá 623 00:26:40,270 --> 00:26:42,390 predtým vrátil pravda, pravda, pravda. 624 00:26:42,390 --> 00:26:48,390 Ale štvrtý čas, bude to mať vrátiť false, napríklad. 625 00:26:48,390 --> 00:26:48,540 Dobrá. 626 00:26:48,540 --> 00:26:49,540 Veľmi dobre. 627 00:26:49,540 --> 00:26:50,060 Blahoželáme. 628 00:26:50,060 --> 00:26:52,160 Získali ste stresu loptu dnes. 629 00:26:52,160 --> 00:26:53,110 >> [APPLAUSE] 630 00:26:53,110 --> 00:26:54,382 >> STEVEN: Ďakujem. 631 00:26:54,382 --> 00:26:55,680 >> DAVID Malan: Ďakujem. 632 00:26:55,680 --> 00:26:59,740 OK, tak to sa zdá byť moc o krok vpred, nie? 633 00:26:59,740 --> 00:27:01,410 Popísali sme túto dátovú štruktúru. 634 00:27:01,410 --> 00:27:02,320 Bolo to pôsobivé, nie? 635 00:27:02,320 --> 00:27:03,200 Operačné systémy páčiť. 636 00:27:03,200 --> 00:27:06,360 Zrejme na webe môžete využívať toto, a ďalších aplikácií stále. 637 00:27:06,360 --> 00:27:10,870 Ale to, čo hlúpe obmedzenia, že sme späť na triedenie v týždni dva limity 638 00:27:10,870 --> 00:27:12,880 kde sme pevnú veľkosť poľa. 639 00:27:12,880 --> 00:27:15,010 >> Takže tam sú naozaj pár spôsoby, ako by sme mohli vyriešiť. 640 00:27:15,010 --> 00:27:18,750 Mohli by sme dynamicky alokovať pole, nie ťažké kódovanie ako som 641 00:27:18,750 --> 00:27:22,600 hotoví, ale znova, ktorým to, aby bolo jasno, ako 642 00:27:22,600 --> 00:27:23,830 niečo také. 643 00:27:23,830 --> 00:27:29,040 Int * zásobníky, nerozhoduje na objeme ešte. 644 00:27:29,040 --> 00:27:35,460 Ale keď som vyhlásil stoh inde v mojom kóde, mohol by som potom volania malloc, 645 00:27:35,460 --> 00:27:38,250 získať adresu kusom pamäť, a ja som mohol priradiť 646 00:27:38,250 --> 00:27:39,980 že adresa zásobníkov. 647 00:27:39,980 --> 00:27:43,340 >> A potom, pretože je to len kus pamäť, mohol by som aj naďalej používať námestí 648 00:27:43,340 --> 00:27:45,450 držiak zápis obvyklým spôsobom. 649 00:27:45,450 --> 00:27:49,020 Vzhľadom k tomu znova, je tu nejako to funkčným ekvivalentom polí a 650 00:27:49,020 --> 00:27:50,820 kúsky pamäti, ktoré prichádzajú späť z malloc. 651 00:27:50,820 --> 00:27:53,090 Môžeme správať ako ostatní pomocou ukazovateľa aritmetický alebo 652 00:27:53,090 --> 00:27:54,440 hranatá zátvorka notácie. 653 00:27:54,440 --> 00:27:55,660 Takže to je jeden prístup. 654 00:27:55,660 --> 00:28:00,120 >> Ale ako inak by sme mohli zaviesť tento rovnaké dátové štruktúry, prípadne? 655 00:28:00,120 --> 00:28:00,280 Je to tak? 656 00:28:00,280 --> 00:28:04,530 Mám pocit, že práve to vyriešil problém ako pred týždňom. 657 00:28:04,530 --> 00:28:08,860 Čo bolo riešenie tohto problému že Steven narazil? 658 00:28:08,860 --> 00:28:10,370 Takže spojové zoznamy, vpravo. 659 00:28:10,370 --> 00:28:13,410 >> Ak je problém, že maľujeme sami do rohu prideľovanie 660 00:28:13,410 --> 00:28:17,580 dopredu príliš málo pamäti, že potom sa nejako riešiť, no, 661 00:28:17,580 --> 00:28:19,880 prečo nie len zabrániť tomu, aby vydá dohromady? 662 00:28:19,880 --> 00:28:26,170 Prečo nie len vyhlásiť zásobníky sa ukazovateľ na uzol, ergo spájať zoznam, 663 00:28:26,170 --> 00:28:30,740 a potom jednoducho prideliť nové uzly zakaždým, keď Steven potrebné, aby sa zmestili 664 00:28:30,740 --> 00:28:32,400 číslo do dátovej štruktúry. 665 00:28:32,400 --> 00:28:34,200 >> Takže obraz by mal zmeniť. 666 00:28:34,200 --> 00:28:38,220 To nebude tak čisté a ako jednoduché, ako len polia troch ints. 667 00:28:38,220 --> 00:28:42,970 Teraz to bude ukazovateľ na struct, a to struct sa chystá 668 00:28:42,970 --> 00:28:44,830 majú int a ďalšie ukazovateľ. 669 00:28:44,830 --> 00:28:47,670 Je to povedie prostredníctvom tohto ukazovateľa iné takéto struct na 670 00:28:47,670 --> 00:28:48,600 ďalší taký struct. 671 00:28:48,600 --> 00:28:50,560 Takže fotka by v skutočnosti dostať trochu Messier. 672 00:28:50,560 --> 00:28:52,950 A boli by sme šípky viazanie všetko dohromady. 673 00:28:52,950 --> 00:28:55,280 >> Ale to je v poriadku, že jo, pretože Videli sme, ako to urobiť. 674 00:28:55,280 --> 00:28:58,180 A akonáhle sa dostanete pohodlne vykonáva niečo ako prepojený 675 00:28:58,180 --> 00:29:01,450 zoznam, ktorý budete musieť robiť, keď rozhodnete hash tabuľku s 676 00:29:01,450 --> 00:29:05,120 oddelené zreťazenie pre p-set 6, môžete ho použiť ako stavebný blok, alebo 677 00:29:05,120 --> 00:29:08,870 prísada, alebo Scratch hovoriť, postup, niečo, čo dáte, vám 678 00:29:08,870 --> 00:29:12,560 vytvorili svoj vlastný kúsok skladačky ktoré potom môžete znovu použiť. 679 00:29:12,560 --> 00:29:17,090 Takže kompromisy, ale možné riešenia že sme vlastne nevideli. 680 00:29:17,090 --> 00:29:20,560 >> Takže docela často, vidíte to každý rok alebo dva, keď Apple vydal 681 00:29:20,560 --> 00:29:23,060 niečo nové, a všetci blázni line up mimo Apple 682 00:29:23,060 --> 00:29:27,050 uložiť ku kúpe ich marginálne prejsť na hardvér. 683 00:29:27,050 --> 00:29:30,420 Hovorím to, je to v poriadku, pretože Som jeden z tých ľudí. 684 00:29:30,420 --> 00:29:35,140 Takže, aké dátové štruktúry môže predstavovať túto skutočnosť? 685 00:29:35,140 --> 00:29:36,980 >> No, povedzme, že front, linka. 686 00:29:36,980 --> 00:29:40,270 Takže Briti to nazval typicky front rovnako, takže je to pekné meno. 687 00:29:40,270 --> 00:29:44,960 A dve operácie, ktoré fronty musí podporovať budeme volať Zaradí 688 00:29:44,960 --> 00:29:48,900 prevádzka a dequeue prevádzka, ktoré sú si podobné 689 00:29:48,900 --> 00:29:50,120 duch tlačiť a pop. 690 00:29:50,120 --> 00:29:54,060 Je to len trochu líši konvencie, čo hovoríme nich. 691 00:29:54,060 --> 00:29:57,680 Ale enqueue niečo znamená pridať alebo vložiť do dátovej štruktúry. 692 00:29:57,680 --> 00:29:59,570 Dequeue znamená odstrániť. 693 00:29:59,570 --> 00:30:05,170 Ale vzhľadom k tomu, zásobník bol dátový LIFO štruktúra, fronta je prvá, 694 00:30:05,170 --> 00:30:06,740 Prvý z dátovej štruktúry. 695 00:30:06,740 --> 00:30:10,050 >> Ak ste prvý človek v rade, budete prvá osoba, ktorá sa 696 00:30:10,050 --> 00:30:12,420 z radu a kúpiť si nový prístroj. 697 00:30:12,420 --> 00:30:18,070 Predstavte si, ako naštvaný títo ľudia by ak Apple namiesto toho používal balík pre 698 00:30:18,070 --> 00:30:21,250 inštancie, na vykonanie vychystávanie do vašej novú hračku. 699 00:30:21,250 --> 00:30:24,310 Takže fronty zmysel, určite, a my môžeme myslieť na všetky druhy 700 00:30:24,310 --> 00:30:27,480 aplikácie, pravdepodobne pre front, zvlášť keď chcete spravodlivosť. 701 00:30:27,480 --> 00:30:30,040 Takže, ako môžeme realizovať tieto ako dátové štruktúry? 702 00:30:30,040 --> 00:30:33,680 >> Navrhujem, že by sme mohli musíte urobiť to takto. 703 00:30:33,680 --> 00:30:35,225 Takže budem teraz mať čísla. 704 00:30:35,225 --> 00:30:38,190 Takže budeme držať to jednoduchý, a nie nutne hovoriť, pokiaľ ide o zásobníkov. 705 00:30:38,190 --> 00:30:40,220 Len čísla, ktoré ľudia dostali. 706 00:30:40,220 --> 00:30:43,760 Kapacita bude opäť upevnite Celkový počet osôb, ktoré môžu byť v 707 00:30:43,760 --> 00:30:46,900 tento riadok ako troch alebo bez ohľadu na iná hodnota. 708 00:30:46,900 --> 00:30:50,760 >> Ale navrhujem, že musím sledovať nielen veľkosťou 709 00:30:50,760 --> 00:30:52,370 fronta, koľko vecí v ňom. 710 00:30:52,370 --> 00:30:56,310 Takže veľkosť je aktuálna veľkosť, kapacita je maximálna veľkosť. 711 00:30:56,310 --> 00:30:58,540 Len raz, nomenklatúra konvencií. 712 00:30:58,540 --> 00:31:03,680 Prečo potrebujem ďalšie int vnútri z frontu, ako sledovať, kto je v 713 00:31:03,680 --> 00:31:05,365 prednej línie? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 Prečo musím k tomu, že v tomto prípade? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> No, ako sa tento obrázok sa zmení? 718 00:31:16,190 --> 00:31:19,280 Mohol by som opätovne využiť väčšinu obrázku. 719 00:31:19,280 --> 00:31:21,480 Nechaj ma ísť napred a vymazať to, čo je tu. 720 00:31:21,480 --> 00:31:24,580 Dáme to ľahko iné meno tu. 721 00:31:24,580 --> 00:31:28,930 Poďme sa zbaviť 17, zbavme na 9, poďme sa zbaviť 3. 722 00:31:28,930 --> 00:31:30,410 A dodajme ešte jednu vec. 723 00:31:30,410 --> 00:31:34,710 Navrhujem, že musím sledovať predné zoznamu, ktorý je práve 724 00:31:34,710 --> 00:31:35,570 Bude tiež int. 725 00:31:35,570 --> 00:31:36,550 A budeme držať to jednoduchý. 726 00:31:36,550 --> 00:31:37,740 Nie spájať zoznam teraz. 727 00:31:37,740 --> 00:31:40,900 >> Budeme sa priznať, že budeme Narazí tohto limitu. 728 00:31:40,900 --> 00:31:43,720 Ale čo ja chcem vidieť sa stalo tentoraz? 729 00:31:43,720 --> 00:31:47,240 Tak, že som do toho pustite a prvý osoba je v súlade, a 730 00:31:47,240 --> 00:31:48,560 je to číslo 9.. 731 00:31:48,560 --> 00:31:49,680 Máme stres gule. 732 00:31:49,680 --> 00:31:51,330 Môžem ukradnúť, povedzme, dva alebo tri ľudí? 733 00:31:51,330 --> 00:31:52,690 Jedna, dva, tri? 734 00:31:52,690 --> 00:31:53,120 Poď hore. 735 00:31:53,120 --> 00:31:56,022 Právo spredu, pretože urobíme tohle rýchlo. 736 00:31:56,022 --> 00:31:59,415 >> Každý z vás sa teraz bude fan chalan vo fronte na Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Nebudete dostávať Apple hardvér Na konci tohto hoci. 739 00:32:06,210 --> 00:32:06,500 Dobrá. 740 00:32:06,500 --> 00:32:09,430 Takže ty si číslo 9, ty si číslo 17, číslo 22. 741 00:32:09,430 --> 00:32:12,130 Tie sú ľubovoľné čísla, ako je Študent ID alebo ktovie čo ešte. 742 00:32:12,130 --> 00:32:14,550 A za chvíľu, začnime začať pridávať veci. 743 00:32:14,550 --> 00:32:16,000 A ja budem bežať dosku tu tentoraz. 744 00:32:16,000 --> 00:32:19,570 >> Takže v tomto prípade som si inicializuje predné byť - 745 00:32:19,570 --> 00:32:22,380 Vlastne som naozaj nestarám, čo predná časť je, pretože veľkosť je nula. 746 00:32:22,380 --> 00:32:24,480 Takže to môže byť aj len byť otáznik. 747 00:32:24,480 --> 00:32:26,170 To všetko sú otázniky. 748 00:32:26,170 --> 00:32:29,880 Takže teraz začneme skutočne vidieť niektoré ľudia čakajú, až v obchode. 749 00:32:29,880 --> 00:32:33,320 >> Takže ak číslo 9, ty si prvý, tam v 5 hodín ráno, choďte do toho a line up, 750 00:32:33,320 --> 00:32:34,210 alebo v noci. 751 00:32:34,210 --> 00:32:34,580 OK. 752 00:32:34,580 --> 00:32:35,940 Takže teraz 9 je tu. 753 00:32:35,940 --> 00:32:37,940 Takže 9 je v prednej časti zoznamu. 754 00:32:37,940 --> 00:32:41,440 Takže budem pokračovať a aktualizovať Veľkosť tohto aktuálnych dát 755 00:32:41,440 --> 00:32:44,740 štruktúru, ktorá nie je už 0, ale na 1. 756 00:32:44,740 --> 00:32:47,630 Chystám sa dať na 9 Predné zoznamu. 757 00:32:47,630 --> 00:32:51,020 Nechaj ma ísť dopredu a prepínať obrazovky takže vidíme okolo nás tu. 758 00:32:51,020 --> 00:32:53,220 >> A teraz čo chcem dať na prednej strane? 759 00:32:53,220 --> 00:32:56,240 Budem sledovať, že predné fronty hneď 760 00:32:56,240 --> 00:32:58,570 je v mieste 0. 761 00:32:58,570 --> 00:33:00,510 Pretože to, čo sa bude diať nabudúce? 762 00:33:00,510 --> 00:33:03,000 No, predpokladám, teraz som enqueue 17 tiež. 763 00:33:03,000 --> 00:33:04,510 Tak hop v rade tam. 764 00:33:04,510 --> 00:33:07,060 A opäť, typ dverí Obchod sa tu bude. 765 00:33:07,060 --> 00:33:08,700 Takže teraz som pridal 17. 766 00:33:08,700 --> 00:33:10,810 A aj keď títo chlapci sú blokovania obrazovka, to je v poriadku, 767 00:33:10,810 --> 00:33:12,300 pretože vidíme to tu. 768 00:33:12,300 --> 00:33:12,910 Prepáčte. 769 00:33:12,910 --> 00:33:13,810 >> DIVÁKOV: Môžeme sa pohybovať - 770 00:33:13,810 --> 00:33:14,660 >> DAVID Malan: Nie, to je v poriadku. 771 00:33:14,660 --> 00:33:16,000 Je to obrovská tam. 772 00:33:16,000 --> 00:33:18,580 Takže 17 je teraz vo vnútri fronty. 773 00:33:18,580 --> 00:33:21,332 Musím aktualizovať, ktorá Pole teraz keď? 774 00:33:21,332 --> 00:33:23,210 OK, určite veľkosti. 775 00:33:23,210 --> 00:33:26,430 A čo predné? 776 00:33:26,430 --> 00:33:27,040 OK, no. 777 00:33:27,040 --> 00:33:30,200 Predné by sa nemalo meniť, pretože na rozdiel od zásobníka, sme 778 00:33:30,200 --> 00:33:31,370 chcete zachovať spravodlivosť. 779 00:33:31,370 --> 00:33:35,150 Takže ak 9 prišiel prvý, chceme 9 , Že je prvý z radu 780 00:33:35,150 --> 00:33:36,420 do obchodu. 781 00:33:36,420 --> 00:33:37,220 >> V skutočnosti, nech sa na to. 782 00:33:37,220 --> 00:33:42,235 Než vložíme 22, poďme choďte do toho a dequeue 9. 783 00:33:42,235 --> 00:33:42,970 Ako sa voláte? 784 00:33:42,970 --> 00:33:43,680 >> Divákov: Jake. 785 00:33:43,680 --> 00:33:45,440 >> DAVID Malan: Jake sa deje byť dequeued teraz. 786 00:33:45,440 --> 00:33:48,050 Takže ste si na prechádzku do obchodu. 787 00:33:48,050 --> 00:33:49,880 A predstierať, že obchod je tamto. 788 00:33:49,880 --> 00:33:51,970 Takže teraz, čo je potrebné - dit-dit-dit! 789 00:33:51,970 --> 00:33:53,400 Čo by sa stalo teraz? 790 00:33:53,400 --> 00:33:54,490 Návrh rozhodnutia. 791 00:33:54,490 --> 00:33:56,825 Takže nie je zlý inštinkt, ale - čo sa to voláte? 792 00:33:56,825 --> 00:33:57,090 >> DIVÁKOV: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID Malan: David. 794 00:33:57,500 --> 00:33:58,810 Takže to, čo Dávid urobil? 795 00:33:58,810 --> 00:34:02,590 Snažil sa nejako opraviť údaje štruktúra a pohyb od jeho umiestnenia 796 00:34:02,590 --> 00:34:04,100 v bývalom mieste Jake. 797 00:34:04,100 --> 00:34:06,740 A to je v poriadku, ak sme ochotní prijať, že ako 798 00:34:06,740 --> 00:34:08,199 implementačný detail. 799 00:34:08,199 --> 00:34:11,100 Ale najprv poďme aktualizovať dáta štruktúru, ako to robíme. 800 00:34:11,100 --> 00:34:14,139 Pretože som nepáčil nápad všetkých ľudia posun v tomto odbore. 801 00:34:14,139 --> 00:34:17,360 >> Nie je to veľký problém, ak David robí s jeden krok, ale opäť si spomeniem na 802 00:34:17,360 --> 00:34:20,360 keď sme mali osem dobrovoľníkov na etapa a urobili sme ako vloženie 803 00:34:20,360 --> 00:34:22,600 triedenie, kde sme museli začať pohybujúce sa všetci okolo. 804 00:34:22,600 --> 00:34:23,790 To má drahá, že jo? 805 00:34:23,790 --> 00:34:28,330 To ma krčiť sa o veľké O n, veľký O n na druhú znova. 806 00:34:28,330 --> 00:34:30,650 Nie je to pocit, ideálny výsledok. 807 00:34:30,650 --> 00:34:32,080 >> Takže povedzme, aktualizovať to. 808 00:34:32,080 --> 00:34:35,120 Takže veľkosť fronty nie je 2. 809 00:34:35,120 --> 00:34:37,090 Je to teraz jednoducho jedno. 810 00:34:37,090 --> 00:34:40,360 Ale teraz môžem aktualizovať niečo Nechcel som aktualizovať skôr, 811 00:34:40,360 --> 00:34:41,130 Predné zoznamu. 812 00:34:41,130 --> 00:34:45,420 Mohol by som povedať, je, že namiesto 1? 813 00:34:45,420 --> 00:34:49,770 Takže teraz máme odpadky hodnoty tu odpadky hodnota tu a David v 814 00:34:49,770 --> 00:34:51,469 Uprostred tohto odpadu. 815 00:34:51,469 --> 00:34:54,980 Ale štruktúra dát je stále neporušená. 816 00:34:54,980 --> 00:34:58,540 >> A v skutočnosti som ani potreba zmeniť Jake je bývalý číslo 817 00:34:58,540 --> 00:35:00,460 9, pretože koho to zaujíma. 818 00:35:00,460 --> 00:35:04,470 Mám dostatok informácií, teraz v veľkosť, že viem, je tu ešte jedna osoba 819 00:35:04,470 --> 00:35:05,030 Táto fronta. 820 00:35:05,030 --> 00:35:08,340 A viem, že táto osoba je v mieste 1, nie 0. 821 00:35:08,340 --> 00:35:09,760 Nepočítam. 822 00:35:09,760 --> 00:35:11,300 1. tak i 823 00:35:11,300 --> 00:35:13,410 Takže dátová štruktúra je ešte OK. 824 00:35:13,410 --> 00:35:14,330 >> No, čo sa stane ďalej? 825 00:35:14,330 --> 00:35:15,010 Poďme enqueue - 826 00:35:15,010 --> 00:35:15,370 Ako sa voláte? 827 00:35:15,370 --> 00:35:16,160 >> Divákov: Callen. 828 00:35:16,160 --> 00:35:16,580 >> DAVID Malan: Callen. 829 00:35:16,580 --> 00:35:20,770 Poďme si enqueue Callen a 22 je teraz vo fronte. 830 00:35:20,770 --> 00:35:22,300 Takže teraz, čo sa musí zmeniť, tu? 831 00:35:22,300 --> 00:35:24,380 Predné nebude zmeniť, samozrejme. 832 00:35:24,380 --> 00:35:27,160 Veľkosť sa zmení na 2 znova. 833 00:35:27,160 --> 00:35:31,590 A 22 skončí tu, 9 je stále prítomná, ale je to skutočne 834 00:35:31,590 --> 00:35:32,600 odpadky hodnota sa. 835 00:35:32,600 --> 00:35:35,910 Je to len pozostatok minulosti Jake. 836 00:35:35,910 --> 00:35:39,200 >> Takže teraz, čo sa stane, keď Aj dequeue Davide? 837 00:35:39,200 --> 00:35:41,560 Jedna posledná operácia, dequeue David. 838 00:35:41,560 --> 00:35:46,070 Mohli by sme sa posunúť, ale navrhujem, poďme čo najmenej práce, ako je to možné. 839 00:35:46,070 --> 00:35:50,280 Teraz môj dátová štruktúra ide späť vo veľkosti 2-1. 840 00:35:50,280 --> 00:35:53,730 Ale fronty Teraz sa 2. 841 00:35:53,730 --> 00:35:56,640 Nepotrebujem, aby tieto čísla zmeniť ešte nie, pretože sú 842 00:35:56,640 --> 00:35:58,230 len nezmyselné hodnoty. 843 00:35:58,230 --> 00:35:59,720 >> Ale teraz, čo sa stane? 844 00:35:59,720 --> 00:36:03,280 Dajme tomu, že som enqueue, 26? 845 00:36:03,280 --> 00:36:05,890 Mám pocit, že patrím sem. 846 00:36:05,890 --> 00:36:06,890 Takže som bol enqueued. 847 00:36:06,890 --> 00:36:08,760 Tak nejako som sem patrím. 848 00:36:08,760 --> 00:36:11,300 A aj keď to nie je úplne vážim vizuálne na javisku, 849 00:36:11,300 --> 00:36:15,075 pretože máme dostatok priestoru, mal by som nemožno tu stojím, prečo? 850 00:36:15,075 --> 00:36:16,290 >> DIVÁKOV: Si mimo hraciu plochu. 851 00:36:16,290 --> 00:36:16,370 >> DAVID Malan: Správne. 852 00:36:16,370 --> 00:36:16,940 Som mimo medze. 853 00:36:16,940 --> 00:36:19,330 Som indexované za hranice tohto poľa. 854 00:36:19,330 --> 00:36:23,420 Mal by som byť v jednom z tri možné lokality. 855 00:36:23,420 --> 00:36:25,150 Tak, kde je najprirodzenejší ísť? 856 00:36:25,150 --> 00:36:27,760 Navrhujem, aby sme pákové týždeň jeden trik. 857 00:36:27,760 --> 00:36:30,150 Operátor modulo, percento. 858 00:36:30,150 --> 00:36:36,850 Pretože som stál pri technicky miesto 3, ale mám 3 mod kapacity, 859 00:36:36,850 --> 00:36:40,250 takže 3, znak percenta, 3 - 860 00:36:40,250 --> 00:36:40,970 Kapacita je 3. 861 00:36:40,970 --> 00:36:41,720 Čo je to? 862 00:36:41,720 --> 00:36:43,700 Čo je to zvyšok po delíte 3 od 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Tak, že ma stavia sa Jake, čo je vlastne dobre. 865 00:36:48,140 --> 00:36:50,370 Takže teraz vykonávania z toho, čo sa deje na 866 00:36:50,370 --> 00:36:51,250 byť trochu bolí hlava. 867 00:36:51,250 --> 00:36:53,740 Je to naozaj len jeden riadok bolesti hlavy, kódu. 868 00:36:53,740 --> 00:36:56,580 Ale aspon teraz je tu odpadky hodnotu, ale je tu to dva 869 00:36:56,580 --> 00:36:57,910 legitímne ints tu. 870 00:36:57,910 --> 00:37:04,160 A tvrdím, že teraz sme urobili presne to, čo musíme urobiť, tak dlho, kým 871 00:37:04,160 --> 00:37:08,600 zmeníme to, čo Jake hodnota mala byť 26. 872 00:37:08,600 --> 00:37:12,110 >> Teraz máme dostatok informácií, stále zachovanie integrity 873 00:37:12,110 --> 00:37:13,060 tejto dátovej štruktúry. 874 00:37:13,060 --> 00:37:17,160 Sme stále trochu smolu, keď sme Chcem vložiť štyri alebo viac celkom 875 00:37:17,160 --> 00:37:20,740 prvky, ale môžem sa aspon pekne efektívne využitie tejto konštanty 876 00:37:20,740 --> 00:37:21,740 čas, v skutočnosti. 877 00:37:21,740 --> 00:37:27,150 Nechcem sa starať o radenie všetci, pretože sklon Davida bolo. 878 00:37:27,150 --> 00:37:30,816 >> Akékoľvek otázky týkajúce sa komínov alebo to front? 879 00:37:30,816 --> 00:37:32,184 >> DIVÁKOV: Je dôvod, prečo Potrebujete veľkosť, takže viete, 880 00:37:32,184 --> 00:37:34,010 kde má človek? 881 00:37:34,010 --> 00:37:34,770 >> DAVID Malan: Presne tak. 882 00:37:34,770 --> 00:37:38,230 Musím poznať veľkosť poľa pretože musím presne vedieť, ako 883 00:37:38,230 --> 00:37:41,940 mnoho z týchto hodnôt sú legitímne, a aby nájdem, kam umiestniť 884 00:37:41,940 --> 00:37:42,800 ďalšia osoba. 885 00:37:42,800 --> 00:37:43,300 Presne tak. 886 00:37:43,300 --> 00:37:44,580 Veľkosť je - 887 00:37:44,580 --> 00:37:46,360 Vlastne sme nemali aktualizovať to ešte. 888 00:37:46,360 --> 00:37:48,380 Pridal som sám na 26 rokov. 889 00:37:48,380 --> 00:37:51,760 Veľkosť je teraz, nie jeden, ale dva. 890 00:37:51,760 --> 00:37:57,780 Takže teraz to naozaj pomáha mi nájsť hlava zoznamu, ktorý nie je 0, nie je 891 00:37:57,780 --> 00:37:59,250 1, ale je 2.. 892 00:37:59,250 --> 00:38:01,665 Na prednej strane zoznamu je naozaj číslo 22. 893 00:38:01,665 --> 00:38:05,120 Vzhľadom k tomu prišiel ako prvý, a tak by povolené do obchodu predo mnou, 894 00:38:05,120 --> 00:38:08,780 aj keď vizuálne stojím bližšie k obchodu. 895 00:38:08,780 --> 00:38:09,220 >> V poriadku? 896 00:38:09,220 --> 00:38:12,410 Potlesk pre týchto ľudí a necháme ich odtiaľ. 897 00:38:12,410 --> 00:38:17,090 >> [APPLAUSE] 898 00:38:17,090 --> 00:38:18,150 >> DAVID Malan: Nemohol som nechať budete mať zásobník. 899 00:38:18,150 --> 00:38:20,760 Mohli sme vidieť, čo sa stane, keď chcete, ale možno tiež nie. 900 00:38:20,760 --> 00:38:21,590 Dobrá. 901 00:38:21,590 --> 00:38:25,380 Tak čo teraz čo z toho plynie? 902 00:38:25,380 --> 00:38:28,900 No, dovoľte mi navrhnúť, aby tam niekoľko ďalších dátových štruktúr by sme mohli 903 00:38:28,900 --> 00:38:33,810 začať pridávať do nášho náradia, ktoré v skutočnosti je úplne, úplne relevantné 904 00:38:33,810 --> 00:38:35,270 sme sa ponoriť do vecí webe. 905 00:38:35,270 --> 00:38:38,150 Čo zase má nejaké spojenie na stromy vo forme 906 00:38:38,150 --> 00:38:40,550 niečo ako DOM, dokument objektový model. 907 00:38:40,550 --> 00:38:42,370 Ale uvidíme viac že onedlho. 908 00:38:42,370 --> 00:38:46,260 >> Dovoľte mi navrhnúť, z definície, že sme zavolajte strom teraz, čo by ste mohli vedieť, ako 909 00:38:46,260 --> 00:38:48,820 viac rodokmeni, kde nejaký predok na 910 00:38:48,820 --> 00:38:49,790 Korene stromu. 911 00:38:49,790 --> 00:38:54,480 Patriarchálnej alebo matriarchát na samom vrchole stromu. 912 00:38:54,480 --> 00:38:56,700 Bez svojho manžela, v tomto prípade. 913 00:38:56,700 --> 00:39:00,940 Ale teraz máme, čo budeme nazývať Deti, ktoré sú uzly, ktoré visia 914 00:39:00,940 --> 00:39:05,480 z ľavej alebo pravej dieťa dieťa, šípky, ako je znázornené tu. 915 00:39:05,480 --> 00:39:10,490 >> Inými slovami, v stromovej štruktúre dát v počítači, strom má nulu 916 00:39:10,490 --> 00:39:11,480 alebo viac uzlov. 917 00:39:11,480 --> 00:39:13,500 Ak má aspoň jeden uzol, tomu sa hovorí koreň. 918 00:39:13,500 --> 00:39:15,700 Sú to veci, ktoré vizuálne čerpáme na vrchole. 919 00:39:15,700 --> 00:39:20,280 A to uzol, ako každý iný uzol, môže majú nulový, jeden, alebo dva, alebo tri, 920 00:39:20,280 --> 00:39:23,600 alebo ako veľa detí dátová štruktúra podporuje. 921 00:39:23,600 --> 00:39:29,150 V tomto prípade, koreň, skladovanie hodnoty jedna, má dve deti, 2 a 3, 922 00:39:29,150 --> 00:39:33,020 takže sme zvyčajne vyžadujú dva ľavej Dieťa a 3 právo dieťa. 923 00:39:33,020 --> 00:39:36,940 >> A potom, keď sa dostaneme až 5, 6, a 7, 6 by sa dalo nazvať prostredné dieťa. 924 00:39:36,940 --> 00:39:38,940 Pokiaľ máte štyri deti, to bude mätúce. 925 00:39:38,940 --> 00:39:42,260 Tak sme sa prestať používať tento druh o zástupcu ústne. 926 00:39:42,260 --> 00:39:44,580 Ale je to naozaj len rodokmeň. 927 00:39:44,580 --> 00:39:48,880 A listy sú tu uzlov, ktoré samy o sebe nemajú žiadne deti. 928 00:39:48,880 --> 00:39:52,540 Visí na dno stromu. 929 00:39:52,540 --> 00:39:56,940 >> Takže, ako môžeme realizovať strom, ktorý má len dve deti maximálne? 930 00:39:56,940 --> 00:39:58,410 Nazveme to binárny strom. 931 00:39:58,410 --> 00:40:00,960 Bi opäť znamená dva, v tomto Rovnako tak ako s binárny. 932 00:40:00,960 --> 00:40:04,830 A tak to môže mať nula, jedna, alebo maximálne dve deti. 933 00:40:04,830 --> 00:40:08,650 >> Ja navrhujem, aby sme realizovať uzol pre túto štruktúru s int n, 934 00:40:08,650 --> 00:40:11,910 a potom dva ukazovatele, jeden s názvom vľavo, jeden volal pravdu. 935 00:40:11,910 --> 00:40:14,830 Ale to sú len pekné ľubovoľné konvencie. 936 00:40:14,830 --> 00:40:18,170 A čo je pekné teraz, najmä pokiaľ druh bojoval s koncepčne 937 00:40:18,170 --> 00:40:21,300 rekurzia, alebo si myslel, že to nie je naozaj riešenie pre čokoľvek, 938 00:40:21,300 --> 00:40:23,120 najmä ak by spustiť z pamäte. 939 00:40:23,120 --> 00:40:26,600 Teraz, keď hovoríme o dátach štruktúry a algoritmy, ktoré umožňujú 940 00:40:26,600 --> 00:40:31,030 nás prejsť a manipulovať s nimi, Ukazuje sa, že rekurzia je späť 941 00:40:31,030 --> 00:40:34,240 oveľa presvedčivejšie ak nie je krásny spôsob. 942 00:40:34,240 --> 00:40:38,670 >> Takže to navrhujem, je implementácia z funkcie Hľadať. 943 00:40:38,670 --> 00:40:39,870 Vzhľadom k tomu, dva vstupy - 944 00:40:39,870 --> 00:40:41,570 tak, že ju ako čierna skrinka. 945 00:40:41,570 --> 00:40:46,560 Vzhľadom k tomu, dva vstupy, n, int a ukazovateľ na strom, ukazovateľ na 946 00:40:46,560 --> 00:40:50,020 uzol, alebo naozaj koreň stromu, som Tvrdenie, že táto funkcia môže vrátiť 947 00:40:50,020 --> 00:40:53,530 true alebo false, že hodnota n je vnútri tohto stromu. 948 00:40:53,530 --> 00:40:55,210 >> Čo je vo vnútri tejto čiernej skrinky? 949 00:40:55,210 --> 00:40:57,440 No, štyri vetvy. 950 00:40:57,440 --> 00:40:58,385 Prvá len kontroluje. 951 00:40:58,385 --> 00:41:00,490 Je-li strom je null, stačí sa vrátiť false. 952 00:41:00,490 --> 00:41:04,580 Pokiaľ nie je žiadny uzol, n nie, tam žiadne číslo, len return false. 953 00:41:04,580 --> 00:41:12,330 Ak však, n, hodnota, ktorú hľadáte pre, je menšia než stromu šípky n, a 954 00:41:12,330 --> 00:41:15,180 Len aby bolo jasno, čo to znamená, keď Píšem strom a potom kliknite na šípku 955 00:41:15,180 --> 00:41:18,150 notácie, n? 956 00:41:18,150 --> 00:41:18,690 Presne tak. 957 00:41:18,690 --> 00:41:21,970 To znamená, že dereferencia ukazovateľ tzv strom. 958 00:41:21,970 --> 00:41:26,750 Choďte tam, a potom sa vo vnútri, ktoré uzol a získať jeho pole s názvom n 959 00:41:26,750 --> 00:41:30,810 A potom porovnávajú skutočné n, ktorý bol prešiel do vyhľadávacieho proti nemu. 960 00:41:30,810 --> 00:41:35,390 >> Takže, ak n je menšia ako hodnota n v uzle stromu sám, dobre, 961 00:41:35,390 --> 00:41:36,720 čo to znamená? 962 00:41:36,720 --> 00:41:40,690 To znamená, že nič na prvý pohľad. 963 00:41:40,690 --> 00:41:40,900 Je to tak? 964 00:41:40,900 --> 00:41:45,560 Rovnako ako keď máte rad hodnoty, mali by ste chceli použiť binárne 965 00:41:45,560 --> 00:41:48,290 vyhľadávanie ako formu predelu a panuj. 966 00:41:48,290 --> 00:41:51,790 Ale to, čo sme predpoklad, je potrebné, aby pre binárne hľadanie práce vôbec 967 00:41:51,790 --> 00:41:54,510 v telefónnom zozname a skôr príklady? 968 00:41:54,510 --> 00:41:55,530 >> Ako majú byť triedené. 969 00:41:55,530 --> 00:41:59,490 Takže poďme upresniť definíciu stromu tu nesmie byť len strom, ktorý môže 970 00:41:59,490 --> 00:42:00,880 mať ľubovoľný počet detí. 971 00:42:00,880 --> 00:42:04,700 Nie je to len binárny strom, ktorý môže sú 0, 1, 2 alebo maximálne. 972 00:42:04,700 --> 00:42:09,700 Ale ako binárny vyhľadávací strom, alebo BST ktorý je len ozdobný spôsob, ako hovoriť 973 00:42:09,700 --> 00:42:15,430 binárny strom, tak, že každý uzol je vľavo dieťa, ak je prítomný, je 974 00:42:15,430 --> 00:42:16,830 menej než uzla. 975 00:42:16,830 --> 00:42:20,170 A každý uzol má pravdu dieťa ak je k dispozícii, je väčšia 976 00:42:20,170 --> 00:42:21,740 než samotný uzol. 977 00:42:21,740 --> 00:42:25,200 >> Takže inými slovami, ak vás k tomu strom sa, všetky čísla sú 978 00:42:25,200 --> 00:42:30,620 starostlivo vyvážiť, ako je to tak, že ak Máte 55 ako root, môže ísť 33 979 00:42:30,620 --> 00:42:33,090 po jeho ľavej strane, pretože to je menej ako 55 rokov. 980 00:42:33,090 --> 00:42:36,430 77 môže ísť po jeho pravej strane, pretože je to viac ako 55 rokov. 981 00:42:36,430 --> 00:42:40,750 Ale teraz nevšimol, rovnakú definíciu, Je to rekurzívne definície ústne, 982 00:42:40,750 --> 00:42:42,600 musí požiadať o 33. 983 00:42:42,600 --> 00:42:47,610 33 ľavá dieťa musí byť menšie než to, a 33 na pravej dieťa, 44, musí byť 984 00:42:47,610 --> 00:42:48,580 väčšie než to. 985 00:42:48,580 --> 00:42:51,670 >> Tak to je strom binárneho vyhľadávania, a Navrhujem, s použitím trochu 986 00:42:51,670 --> 00:42:53,910 rekurzia, môžeme teraz nájsť n 987 00:42:53,910 --> 00:42:59,160 Takže pokiaľ je n menšie ako hodnotu n, ktorá je aktuálny uzol, ja idem 988 00:42:59,160 --> 00:43:04,090 dopredu a punt, aby som tak povedal, a len vrátiť bez ohľadu na odpoveď na 989 00:43:04,090 --> 00:43:08,470 vyhľadávanie na n stromu je ľavá dieťa. 990 00:43:08,470 --> 00:43:11,370 Všimnite si, opäť, táto funkcia len očakáva uzla STAR, 991 00:43:11,370 --> 00:43:12,780 ukazovateľ na uzol. 992 00:43:12,780 --> 00:43:17,360 Tak určite som si len urobiť strom Šípka vľavo, čo povedie 993 00:43:17,360 --> 00:43:18,400 Prechod k inému uzlu. 994 00:43:18,400 --> 00:43:19,480 Ale čo je to uzol? 995 00:43:19,480 --> 00:43:22,820 >> No, podľa tohto vyhlásenia, vľavo je len ukazovateľ, takže stačí 996 00:43:22,820 --> 00:43:27,090 znamená, že som okolo na vyhľadávacie funkcie iný ukazovateľ, a to 997 00:43:27,090 --> 00:43:30,750 ktorý reprezentuje Moja ľavá dieťaťa strom. 998 00:43:30,750 --> 00:43:36,040 Takže v tomto prípade, ukazovateľ 33, ak je To je náš výber vstupu Zatiaľ, ak 999 00:43:36,040 --> 00:43:40,740 n je väčšie ako hodnotu n na aktuálny uzol v strome, potom som 1000 00:43:40,740 --> 00:43:43,370 ísť dopredu a pramice v druhej smer a len povedať, vôbec sa mi nepáči 1001 00:43:43,370 --> 00:43:47,280 vedieť, či je táto hodnota n je v stromovej štruktúre ale viem, že ak je to, že je to po mojej 1002 00:43:47,280 --> 00:43:49,090 právo vetva, aby som tak povedal. 1003 00:43:49,090 --> 00:43:53,120 Dovoľte mi teda volanie rekurzívne prehľadávať, vykonaním n znovu, ale odovzdaním 1004 00:43:53,120 --> 00:43:54,580 ukazovateľ na mojej pravej dieťa. 1005 00:43:54,580 --> 00:44:00,020 >> Inými slovami, keď som v súčasnej dobe 55 a hľadám pre 99, ja viem, že 99 1006 00:44:00,020 --> 00:44:04,270 je väčší ako 55, takže presne ako som roztrhol týždne telefónneho zoznamu rokmi a my 1007 00:44:04,270 --> 00:44:07,140 išiel doprava, podobne ako sme ísť tu. 1008 00:44:07,140 --> 00:44:11,960 A ja neviem, či je to na mojej pravici dieťa, a to nie je, 77 existuje, ale 1009 00:44:11,960 --> 00:44:13,210 Viem, že je v tomto smere. 1010 00:44:13,210 --> 00:44:18,770 Takže hovorím hľadanie na pravom dieťa, 77, a nechajte vyhľadávacie postavu z 1011 00:44:18,770 --> 00:44:24,950 ak existuje 99 v tomto ľubovoľná Príkladom je v skutočnosti tam. 1012 00:44:24,950 --> 00:44:26,900 >> Inak, čo je posledný prípad? 1013 00:44:26,900 --> 00:44:28,620 Je-li strom je null jeden prípad. 1014 00:44:28,620 --> 00:44:31,890 Ak n je menšia než je aktuálna uzol je hodnota je iný prípad. 1015 00:44:31,890 --> 00:44:35,120 Ak n je väčšie ako aktuálny uzla hodnota je tretí prípad. 1016 00:44:35,120 --> 00:44:38,250 Čo je štvrtý a posledný prípad? 1017 00:44:38,250 --> 00:44:39,480 Myslím, že sme z prípadov, nie? 1018 00:44:39,480 --> 00:44:44,690 To tak, že n je aktuálny uzol, že som na. 1019 00:44:44,690 --> 00:44:49,640 >> Takže keď som hľadal 55 v tomto bode v príbehu, že pobočka 1020 00:44:49,640 --> 00:44:51,780 strom sa vráti true. 1021 00:44:51,780 --> 00:44:55,380 Takže to, čo je zaujímavé, je, že sme v skutočnosti, na rozdiel od minulosti týždňov, sme trochu 1022 00:44:55,380 --> 00:44:56,740 na dva základné prípady. 1023 00:44:56,740 --> 00:44:58,300 A oni nemajú byť všetko v hornej časti. 1024 00:44:58,300 --> 00:45:01,390 Horný je základný prípad, pretože v prípade, že Strom je null, nič robiť. 1025 00:45:01,390 --> 00:45:03,410 Stačí sa vrátiť pevný kódované hodnota false. 1026 00:45:03,410 --> 00:45:07,400 >> Spodná vetva je trochu predvolené, pričom keď sme skontrolovať 1027 00:45:07,400 --> 00:45:11,550 null, sme skontrolovať, či má byť vľavo, ale to by nemalo byť, máme 1028 00:45:11,550 --> 00:45:14,640 kontroluje, či by mal byť správne, ale nemali by byť zrejmé, že musí byť 1029 00:45:14,640 --> 00:45:15,870 tam, kde sme. 1030 00:45:15,870 --> 00:45:16,780 To je základná vec. 1031 00:45:16,780 --> 00:45:19,920 Takže tam sú dve rekurzívne prípady obložené tam uprostred. 1032 00:45:19,920 --> 00:45:21,630 Ale ja som mohol napísať to v ľubovoľnom poradí. 1033 00:45:21,630 --> 00:45:24,520 Len som myslel, že to trochu prišlo prirodzené najprv skontrolujte, či prípadné chyby, 1034 00:45:24,520 --> 00:45:28,340 potom sa pozrite doľava, potom sa hneď, potom Predpokladám, že ste na uzle 1035 00:45:28,340 --> 00:45:30,630 ste vlastne hľadáte. 1036 00:45:30,630 --> 00:45:36,240 >> Tak prečo by to mohlo byť užitočné? 1037 00:45:36,240 --> 00:45:37,910 Tak to dopadá - 1038 00:45:37,910 --> 00:45:42,110 a dovoľte mi prejsť na ukážku tu je to na webe. 1039 00:45:42,110 --> 00:45:44,920 Chystáme sa začať používať nie programovací jazyk na prvý, ale 1040 00:45:44,920 --> 00:45:46,030 značkovací jazyk. 1041 00:45:46,030 --> 00:45:48,740 Značkovací jazyk je ten, ktorý je svojim duchom podobať programovanie 1042 00:45:48,740 --> 00:45:51,715 jazyk, ale to vám nedáva schopnosť vyjadriť sám seba logicky. 1043 00:45:51,715 --> 00:45:55,070 To vám dáva možnosť vyjadriť sám seba štrukturálne. 1044 00:45:55,070 --> 00:45:57,960 >> Kam chceš dať niečo na stránke, webová stránka? 1045 00:45:57,960 --> 00:45:59,200 Akú farbu chceš, aby sa to? 1046 00:45:59,200 --> 00:46:00,950 Aké písmo chceš, aby sa to? 1047 00:46:00,950 --> 00:46:02,970 Aké slová sa vlastne Chcete na webovej stránke? 1048 00:46:02,970 --> 00:46:04,060 Takže je to značkovací jazyk. 1049 00:46:04,060 --> 00:46:07,690 Ale potom sme si veľmi rýchlo zavádzať JavaScript, ktorý je plnohodnotným 1050 00:46:07,690 --> 00:46:08,560 programovací jazyk. 1051 00:46:08,560 --> 00:46:12,530 Veľmi podobný vo vzhľade syntakticky na C, ale bude to mať nejaký 1052 00:46:12,530 --> 00:46:15,200 pekné, silnejšie, užívateľsky prívetivé funkcie. 1053 00:46:15,200 --> 00:46:18,050 >> A jeden z frustrácie na to bod v semestri, je, že budeme 1054 00:46:18,050 --> 00:46:22,065 čoskoro realizovať pravopisu v ďaleko menej riadkov kódu pomocou iné jazyky 1055 00:46:22,065 --> 00:46:25,580 ako C sám umožňuje, ale z dôvodu ich Čoskoro budeme rozumieť. 1056 00:46:25,580 --> 00:46:27,750 Bude to prvá takáto webová stránka. 1057 00:46:27,750 --> 00:46:30,120 To bude úplne nezaujatý, Prvý robíme. 1058 00:46:30,120 --> 00:46:31,400 To sa jednoducho povedať, hello world. 1059 00:46:31,400 --> 00:46:34,010 Ale ak ste nikdy nevideli pred, to je HTML, 1060 00:46:34,010 --> 00:46:35,670 HyperText Markup Language. 1061 00:46:35,670 --> 00:46:39,310 >> Ak pôjdete do určitej menu v takmer akýkoľvek prehliadač na akejkoľvek webovej stránky, na 1062 00:46:39,310 --> 00:46:43,160 internet, môžete vidieť HTML že niektorí ľudia písali 1063 00:46:43,160 --> 00:46:44,400 vytvoriť túto webovú stránku. 1064 00:46:44,400 --> 00:46:47,850 A to asi nevyzerá ako krátky alebo čistý, pretože to. 1065 00:46:47,850 --> 00:46:51,400 Ale bude nasledovať vzor z nich otvorené zátvorky a lomítka a 1066 00:46:51,400 --> 00:46:53,660 písmená a potenciálne čísla. 1067 00:46:53,660 --> 00:46:56,770 >> Myslel som, že vám ukážku z toho, čo budete môcť robiť 1068 00:46:56,770 --> 00:46:57,950 po užití CS50. 1069 00:46:57,950 --> 00:47:02,620 Nechaj ma ísť do cs.harvard.edu / rob, našej vlastnej Roba Bowdenová domovskú stránku. 1070 00:47:02,620 --> 00:47:06,080 Urobil to pre nás. 1071 00:47:06,080 --> 00:47:07,490 Takže budete čoskoro môcť urobiť. 1072 00:47:07,490 --> 00:47:10,660 A tiež to, čo ste počuli dnes ráno - 1073 00:47:10,660 --> 00:47:12,480 to, čo si počul dnes ráno - 1074 00:47:12,480 --> 00:47:13,780 >> [HAMSTER DANCE MUSIC] 1075 00:47:13,780 --> 00:47:15,702 >> - Budeš mať možnosť, aby sa to. 1076 00:47:15,702 --> 00:47:16,790 To nás čaká v stredu. 1077 00:47:16,790 --> 00:47:17,791 Uvidíme sa potom. 1078 00:47:17,791 --> 00:47:22,950 >> [HAMSTER DANCE MUSIC] 1079 00:47:22,950 --> 00:47:24,300 DAVID Malan: Na ďalší CS50 - 1080 00:47:24,300 --> 00:47:31,670