DAVID Malan: Dobre. Vitajte späť CS50. To je začiatok 8 týždňov. A pripomínajú, že problém sada 5 skončila s trochou výzvu. Takže za predpokladu, že späť všetky svoje výučby Fellows a CA fotografie v súbore card.raw, máte nárok sa teraz nájsť všetkých tých ľudí, a jeden šťastný výherca bude chodiť domov s jedným z týchto vecí, skok pohyb zariadenie, ktoré môžete použiť pre konečné projekty, napríklad. 

To každý rok, vedie k trochu děsivost. A tak to, čo som myslel, že to je podiel s vami o niektoré poznámky, ktoré majú išiel tam a späť cez zamestnanci zoznam neskoro. Napríklad práve včera večer, citácie koniec citátu, z jedného z pracovníkov členovia, "musel som študentský klepanie na moje dvere vyfotiť so mnou. Stalkeri, vravím. "Zacala dosť opisná a potom sme sa presťahovali na, tak hodinu neskôr, "som mal Študent na mňa čaká po bode a mal všetky naše mená a fotografie na niektorých listov papiera. "v poriadku. Organizovaná tak, ale nie všetko strašidelné ešte. 

Tak, "ja som bol mimo mesta tento víkend, a keď som sa vrátil, bol tam jeden v môj spálne. "[smiech] DAVID Malan: Ďalšie citácie z pracovníkov člen "študent prišiel do môjho domu na Somerville pri 4 hodín ráno. "Ďalšie personál, "Dostal som do hotela v San Francisco a študent čakal na ma v hale s tromi DSLR. " Typ fotoaparátu. "Ja nie som ani na zamestnanca tomto semestri, ale študent sa vlámal do môjho domu tento ráno a zaznamenal celú vec so sklom Google. "A potom konečne, "Najmenej 12 ľudí bolo dychtivo čaká na mňa, keď som sa dostal z môjho limo, a potom som prebudil. "Dobre. Takže medzi fotografiami, ako môžete spomínam, je tento chlapík tu, kto ste Možno viete, ako Milo Banana, ktorý žije s Lauren Carvalho, naše hlavy vyučovanie Fellow. Milo Milo, poď sem chlapče. Milo. Milo. Nezabúdajme, že má na sebe Google Glass, takže my vám ukážeme všetko po ňom. Tak to je Milo, ak chcete vyfotografovať sa s ním neskôr. Ak by ste chceli dať pozor na divákov tam. OK. To je dobré zábery. No, Milo Banana. Oh, nerobte to. 

[Smiech] 

OK. Takže jedným slovom, potom o tom, čo je pred nami, pretože ako začneme prechodu, tento týždeň konkrétne z C na v prostredí príkazového riadku na PHP a JavaScript a SQL a HTML a CSS v web-based prostredie, budeme vybavenie vám všetky viac vedomostí pre prípadné konečné projektov. Za týmto účelom je ihrisko má Tradícia organizovania seminárov, ktoré sú na tangenciálny témy k predmetu. Veľmi o programovaní a vývoj aplikácií a tak ďalej, ale nemusí byť nutne preskúmaná Kurz vlastné osnovy. 

Takže ak by vás mohli zaujímať v jednom alebo viac z tohtoročných seminárov, zaregistrujte sa na cs50.net/seminar. Tam sú staršie semináre na cs50.net/seminars. A na zozname zatiaľ pre tento rok Amazing Web Apps sú s Ruby on Koľajnice, ktorá je alternatívou jazyk PHP. Matematická lingvistika. Úvod do IOS, ktorý je platformy, ktorá je použitá pre iPhone a iPad rozvoja. JavaScript pre Web Apps, budeme pokrývať , Ale v tomto seminári, pôjdete do väčších detailov. 

Leap Motion, takže budeme vlastne majú niektoré našich priateľov z Leap Motion, spoločnosť sama, pridajte sa k nám. Zajtra, v skutočnosti, aby praktický seminár, ak je vás zaujímajú. Meteor.js, alternatívne metódy pre pomocou JavaScriptu nie je v prehliadači, ale na serveri. Node.js, ktorý je veľmi V tomto duchu tiež. Elegantný Android dizajn. Android je veľmi populárna alternatíva na iOS a Windows Phone a ďalšie mobilné platformy. A Web Security Aktívna obrana. 

Takže v skutočnosti, ak si prajete zapojiť sa do tohto, dovoľte mi, aby som aby na vedomie. Sme veľmi radi, že Naši priatelia na skok Pohyb, ktorý je spustenie - tento prístroj naozaj len prišiel pred niekoľkými mesiacmi - milostivo daroval 30 týchto zariadení do triedy pre čo najväčší počet študentov, je-li by ste chceli požičať hardvér na konci semestra a používať ho pre Skutočná konečná projektu. Oni podporujú veľké množstvo jazykov. Žiadny z nich C, žiadny z nich PHP, takže realizovať jeden alebo viac z týchto seminárov by mohlo byť zaujímavé. A všetky z nich bude natočený v prípade, že nie ste schopní zúčastniť osobne. Harmonogram bude oznámené prostredníctvom email ako spevniť izby. 

A napokon, ak idete na projects.cs.50.net, to je webová stránka udržiavame každý rok, pozývame ľudia z komunity, fakulty, odbory, zamestnanci a obaja na vonkajšej strane na CS50 navrhnúť projektové nápady. Veci sú predmetom záujmu skupiny študentov. Veci záujmu oddelenia. Takže sa zase tam, ak budete bojovať s neistotou, pokiaľ ide o to, čo sami chceli riešiť. 

Takže poslednej dobe sme zaviedli pravdepodobne zložitejšie dátové štruktúry, ako my by sme vidieť v minulých týždňoch. Radi by sme sa s použitím polí dosť šťastne ako užitočná, ak zjednodušujúce dátové štruktúry. Potom sme zaviedli nich, ktoré Samozrejme sú spojené zoznamy. A to, čo bolo jednou z motiváciou pre zavedenie tejto dátovej štruktúry? Jo? Čo je to? 

Divákov: Dynamická veľkosť. 

DAVID Malan: Dynamická veľkosť. Takže zatiaľ čo v poli, musíte poznať jeho veľkosť zálohy, ak prideliť ju. V spájať zoznam, nemusíte vedieť, že. Môžete len malloc, alebo všeobecnejšie, prideliť ďalšie uzol, aby som tak povedal, kedykoľvek Chcem vložiť ďalšie dáta. A uzol nie je vopred význam. Je to len všeobecný termín, ktorý popisuje nejaký druh kontajnera, ktorý sme použitie v našej dátovej štruktúry pre ukladanie niektoré Predmetom záujmu, ktorý je v tomto prípade sa stalo, že celé čísla. 

Ale je tu vždy kompromisom. Tak sme si dynamické veľkosti dát štruktúra, ale akú cenu platíme? Čo je to nevýhoda previazaných zoznamov? Jo? 

DIVÁKOV: vyžaduje viac pamäte. 

DAVID Malan: To si vyžaduje viac pamäť, ako presne? 

DIVÁKOV: [nepočuteľné]. 

DAVID Malan: Presne tak. Takže teraz sme ukazovatele nástupu do prídavné pamäti, že sme predtým nepotreboval, pretože výhoda z poľa, samozrejme, je to, že všetko je súvislé späť sa chrbtom k sebe, čo vám dáva náhodný prístup. Pretože len pomocou hranatou zátvorkou notácie, alebo viac technicky ukazovateľ aritmetický, veľmi jednoduché sčítanie, môžete pristupovať k akýmkoľvek prvky v konštantnom čase. A v skutočnosti, to je niečo napovedalo ďalšie cena, ktorú platíme s spájať zoznam. 

Čo sa stane s dobou chodu niečo ako hľadať, keď chcem nájsť nejakú hodnotu a vnútro prepojeného zoznamu? Čo mi beží čas stáť? Veľký O n Ak je to triedené? Čo v prípade, že dátová štruktúra je triediť? Môžem robiť lepšie ako veľké O z n pre vyhľadávanie? Nie, pretože v najhoršom prípade by to mohlo veľmi dobre byť triedené, ale počet hľadáte by mohla byť veľká. To by mohlo byť číslo 100, ktorá Môže sa stať, že všetky ako na konci. A pretože môžete pristupovať iba viazané Zoznam v tomto prevedení by spôsob jeho prvého uzla, ste ešte trochu smolu. Musíte prejsť celú vec od začiatku až do konca, aby bolo možné nájsť že veľké hodnoty ako 100. Alebo zistiť, či je to ani tam. 

Takže môžeme robiť to, čo algoritmus v dátovom štruktúra, ktorá vyzerá takto? Nemôžeme urobiť binárne vyhľadávanie, pretože binárne hľadanie vyžaduje, aby sme mali náhodný prístup. Mohli by sme vyskočiť z miesta na umiestnenie bez nutnosti sledovať Tieto strúhanka vo forme všetkých týchto ukazovateľov. 

Teraz, ako sme to realizovať? No, či pôjdeme na obrazovku tu, ak je môžeme rýchlo implementujeme tieto dáta štruktúra - môj rukopis to nie je všetko, že skvelé tu, ale skúsime to. Takže typedef struct, a čo som chcete volať tú vec tu? Uzol. Takže budem sa nám začalo. A teraz, čo je potrebné, aby sa vo vnútri dátová štruktúra pre ktoré samostatne komunikačné zoznam? Koľko pole? 

Tak dva. Jedným z nich je celkom jednoduché. Tak int n A tak by sme mohli nazývať n čo chceme, ale mal by byť int, či sme vykonávanie spájať zoznam pre ints. A teraz, čo robí druhá poľa musí byť? Struct node *. Takže keď som to struct uzol * a potom som Môžete volať aj to, čo chcem, ale len aby bolo jasno, zavolám je ďalší, ako sme robili. A potom som zavriem zložené zátvorky. 

A teraz, ako minule, Dal som uzol dole. Ale keď som dokladá, že toto je uzol, prečo som sa obťažovať, že je tak verbose tu deklarovať struct uzol * ďalšie, na rozdiel od len na uzle * ďalšie? Jo? 

DIVÁKOV: [nepočuteľné]. 

DAVID Malan: Presne tak. Presne tak. Pretože C naozaj vás doslova a vidí iba definíciu uzla cesta sem, nemôžete odkazovať sa na to tu. Takže máme tento druh preemptivní Vyhlásenie tu, čo je síce viac verbose. Struct uzol, to znamená, že môžeme teraz pristupovať vnútri dátové štruktúry. 

A ako stranou, pretože to je stáva trochu subjektívne teraz, hviezda technicky možné ísť sem, to môže ísť sem, môže dokonca ísť v stredu. Sme prijala v štýle príručke pre Samozrejme, že konvencie uvedenie hviezda vedľa údajov typu, ktorý je v tomto prípade, by struct uzol. Ale realizovať v mnohých učebniciach a on-line odkazy, môžete skutočne vidieť, že na druhej strane. Ale len si uvedomiť, že ako bude v skutočnosti práce a vy by ste mali byť jednoducho konzistentné. 

Dobrá. Tak to bolo naše vyhlásenie of struct uzla. Ale potom sme začali robiť viac sofistikované veci. Napríklad sme sa rozhodli zaviesť niečo ako tabuľky hash. Takže tu je hash tabuľka veľkosti n, indexované od 0 vľavo hore na n mínus 1 vľavo dole. To by mohlo byť hash tabuľka na čokoľvek. Ale to, čo veľa vecí sme sa hovoriť o použitie hash tabuľku? Uloženie čo? 

Mená. Mohli by sme mená ako sme minule. A naozaj, môžete uložiť čokoľvek. A uvidíme to znova PHP a JavaScriptu. Hash tabuľky je pekný druh Swiss Armádny nôž, ktorý vám umožní ukladať skoro čo chcete vo vnútri je to tým, že združí kľúče s hodnotami. Klávesy s hodnotami. 

Teraz v tomto jednoduchom prípade, naše Kľúče sú len čísla. Sme vykonávanie hash tabuľka ako pole. A tak sú kľúče 0, 1, 2, a tak ďalej. A tak my, ako ľudia, rozhodla posledná týždeň, že viete, čo, keď sme bude ukladať mená, jednoducho ľubovoľne, ale celkom rozumne, Predpokladám, že Alice, názov, bude len byť indexované do 0. A Bob, názov B, budú indexované do 1, a tak ďalej. Takže sme museli mapovanie medzi vstupmi, ktoré sú reťazca a hash umiestnenia, ktoré sú čísla. 

Tak, že proces je všeobecne známy ako hašovacej funkcie, a môžete skutočne implementovať v kóde. Ak by som chcel implementovať funkcie hash že robí presne to, čo sme práve popísal, od minule, by som mohol deklarovať funkciu, ktorá berie ako vstup napríklad - a ideme na to na to Obrazovka sem. Ak by som chcel realizovať hash funkcie, mohol by som povedať, niečo také. 

Bude to vrátiť int. Bude to nazvať hash, a to bude akceptovať ako argument reťazec, alebo to môže byť vhodnejšie teraz, a hovoriť char *, budeme hovoriť to. A potom táto funkcia má čo do činenia, nakoniec sa vrátiť int. Teraz, ako to robí, ktoré by mohli nie je tak jasné. Idem na vykonanie tohto bez Forma kontroly chýb práve teraz. Idem len slepo hovoriť, vráti čo je na držiaku s 0, mínus, povedzme, kapitál bodkočiarkou. 

Totálne rozbité. Nie je to dokonalé, pretože jeden, čo keď to je null? Zlé veci sa bude diať. Po druhé, čo keď je prvé písmeno v tejto meno nie je veľké písmeno? To nie je dopadne z vrtov. To by mohlo byť malé písmeno alebo nie list vôbec. Takže absolútne priestor pre zlepšenie tu, ale to je základná myšlienka. 

Čo sme popísali v minulom týždni verbálne len proces mapovania Alicu 0 a Bob sa 1 môže byť vyjadrená iste formulaically ako C funkcie tu. Zavolal znovu hash, vezme reťazec ako vstup, a potom nejako robí niečo s týmto vstup na výrobu výstupu. Nie na rozdiel od našej čiernej skrinky popis že sme dlho urobiť. Neviem, ako by to mohlo byť pracuje pod kapotou. 

Pre problémové sady 6, jeden z problémov, je pre vás rozhodnúť, čo Váš hashovacie funkcia môže byť? Čo bude vo vnútri, že čierna box, a pravdepodobne, bude to trochu zaujímavejšie než to, a rozhodne náchylnejšie k chybám kontroly, ako je táto konkrétna implementácia. 

Ale problémy môžu nastať, že jo? Ak máme dátová štruktúra, ako je táto jeden, čo je jedným z problémov môžete naraziť na priebehu času vloženie stále viac a viac mien na hash tabuľky? Získate kolízie, nie? Čo keď máte Alice a Árona, dvaja ľudia, ktorých mená sa stalo začať? To vyvoláva otázku, kde sa dal druhý taký názov? 

No, možno naivne, jednoducho dať kde Bob patrí, ale potom Bob druh skrutkované, ak sa pokúsite vložte svoje meno a ďalšie nie je miesto pre neho. Takže môžete dať Bob, kde Charlie je, a môžete si to predstaviť veľmi rýchlo prevedie do trochu neporiadok. Niečo lineárne na konci, kde sa stačí hľadať na celú vec Hľadám Alice alebo Bob alebo Aaron a Charlie. 

Tak namiesto toho navrhuje, namiesto toho, aby len lineárne snímanie pre priestranstva a plopping mená tam sme navrhla milovník prístup. Hash tabuľky realizované stále s rad indexov, ale dátový typ tieto indexy teraz boli ukazovatele. Ukazovatele k čomu? Ukazovatele na lineárnymi zoznamy. 

Vzhľadom k tomu, pripomínajú, že spájať zoznam je naozaj len ukazovateľ na uzol, a uzol má ďalšie pole, a že uzol má ďalšie pole, a tak ďalej. Takže teraz môžete myslieť na tomto poli na ľavá strana tabuľky hash ako čo vedie k prepojeného zoznamu. Výhodou je, ak máte kolízie medzi Alicou a Áronovi: Čo robíte s druhý taký človek? Môžete len pripojiť ho, aby koniec, alebo dokonca na začiatku tohto prepojeného zoznamu. 

A vlastne, povedzme, cez rezance že len druhý. Ak by najväčší zmysel? Ak vložím Alicu a ona končí Na prvom mieste, potom sa snažím, aby vložiť Aaron meno, a tam je samozrejme kolízie, mal som ho na začiatku prepojeného zoznamu? To je v tomto prvom mieste, alebo na konci? 

DIVÁKOV: [nepočuteľné]. 

DAVID Malan: OK. Počul som, že na začiatku. Preto sa už na začiatku? 

DIVÁKOV: [nepočuteľné]. 

DAVID Malan: OK. Je to podľa abecedy, tak to je pekné. To je dobrá vlastnosť. To vám ušetrí mi čas potenciálne. To mi nedovolí robiť binárne vyhľadávanie, ale ja by aspoň byť schopný vymaniť sa zo slučky, keď si uvedomujem, no, ja som cesta minulosti sa Aaron by v tomto radené prepojeného zoznamu. Nemám strácať čas hľadaním až do konca. Tak to je rozumné. Prečo inak by mohlo chcete vložiť kolízie názov na na začiatku zoznamu? Čo je to? 

DIVÁKOV: [nepočuteľné]. 

DAVID Malan: Mohlo by to trvať dlho dostať sa na koniec zoznamu. A v skutočnosti, dlhšie a dlhšie. Čím viac mien, ktoré vložíte začiatok, dlhšia než reťaz dostane. Čím dlhšie tú, ktorá súvisí Zoznam je dostane. Takže ste naozaj len strácaš čas. Možno, že ste na tom lepšie udržiavať konštantný Čas vloženia, veľký O z 1, tým, že vždy dávať narážajúce na názov počiatok prepojeného zoznamu, a nie toľko znepokojujúce o triedení. 

Aký je najlepší odpoveď? Je to jasné. To druh závisí na tom, čo distribúcie je to, čo je vzor mená vkladáte. To nemusí byť nutne jasná odpoveď. Ale tu je opäť design príležitosť. 

Tak sme potom sa pozrel na tú vec, ktorá je naozaj iná veľká príležitosť pre p-set 6. A uvedomiť si, ak ste tak už neurobili, Zamyla sa ponorí do oboch z nich, hashovacie tabuľky a snaží sa, vo viacerých detailu. A video návod je vložené do p-set spec. To bol trie - T-R-I-E. A čo bolo zaujímavé, bolo to, že čas prevádzky Nie je potrebné hľadať mená, ako je Maxwell Minule bol veľký O čoho? Čo je to? 

Divákov: počet písmen. 

DAVID Malan: počet písmen. Počul som dve veci. Počet písmen a konštantnom čase. Takže poďme sa, že ako prvý. Počet písmen. No, to dátová štruktúra, odvolanie, je ako strom, rodokmeň, každý z ktorých uzly sú tvorené poli. A tie polia sú odkazy na iné takéto uzly, či iné podobné poľa vo stromu. 

Takže ak by sme chceli potom určujú či Maxwell je tu, mohol by som ísť na prvé pole, na samom vrchole strom, tzv koreň, horná časť trie a postupujte ukazovateľ m, potom ukazovateľ, potom x, w, e, l, l A potom, keď vidím nejaký špeciálny symbol, označený tu ako trojuholník. V kóde uvidíte, že navrhne, aby si implementovaný ako bool, len hovorím áno alebo nie, slovo, tu zastaví. 

No, raz sme išli do M-A-X-W-E-L-L, pocit, sedem, možno osem keď ideme jeden okolo nej osem kroky na nájdenie Maxwell. Alebo povedzme, že K. Ale spomínam posledný čas, som tvrdil, že v prípade, že je realisticky maximálna dĺžka na slovo, rovnako ako 40-niektoré-nepárne znaky, Maximálna dĺžka znamená, konštantnú hodnotu. Takže naozaj, áno, je to technicky veľký O 8 alebo 7, alebo naozaj veľký O K. Ale v prípade, že je konečný limit na to, čo K môže byť, že je konštantná. A tak je to veľký O z 1 na konci dňa. 

Nie je v reálnom svete. Nie, keď skutočne začať sledovať vaše hodiny, ako váš program beží. Je to úplne to bude trochu pomalší než skutočne konštantná čas na jeden krok. Bude to sedem alebo osem stupňov, ale stále je to oveľa, oveľa lepšie než algoritmu, ako je veľký O N, ktorý závisí na veľkosti, čo je v dátové štruktúry. 

Všimnite si, že tu je hore, môžeme vložiť miliónkrát viac mien do tohto dátová štruktúra, ale koľko krokov to bude trvať nám nájsť Maxwell v tomto prípade? Žiadne. On je nedotknutá. A k dnešnému dňu, nemyslím si, že sme videli, príklad dátovej štruktúry alebo algoritmus, ktorý bol úplne ovplyvnená vonkajšie správanie, ako je to. Ale to nemôže byť úžasné. To nemôže byť jediným riešením pre p-set 

A to nie. To nie je nevyhnutne dáta Štruktúra by ste mali tiahnuť k, pretože rovnako ako tabuľky hash, kompromis. Čo je to cena, ktorú zaplatíte tu? Pamäť. Myslím, že je to otrasné množstvo pamäti. A môžete tak celkom vidieť tu, pretože autor obrázku samozrejme skrátený všetkých polí a my nevidíme veľa a je Hostely a C je a Q je a Y je a Z je v týchto poliach. Ale sú tam. 

Každý z týchto uzlov je celý súbor niektorých 26 alebo viac bytov, z ktorých každá čo predstavuje list. 27 V našom prípade, tak, že môže podporovať apostrofy v sade problém. Tak to dátová štruktúra je naozaj, naozaj hustý a široký. A to samo o sebe by mohlo skončiť spomaľuje veci dole, alebo aspoň vás to stálo oveľa viac priestoru. Ale znova, môžeme vyvodiť porovnanie tu. 

Spomínam si na chvíľu späť, sme dosiahli oveľa viac vzrušujúce doba chodu pri triedení keď použijeme zlúčenie druh, ale cena sme zaplatili dosiahnuť n log n o zlúčení druh vyžaduje, aby trávime viac aký zdroj? Viac priestoru. Potrebovali sme sekundárne maticu kopírovať ľudí do, rovnako ako sme tu na javisku. Takže znova, žiadne jasné víťaza, ale len subjektívne konštrukcie rozhodnutie byť robený. 

Dobrá. Takže ako na to? Každý, kto spoznať, ktoré D-Hall? OK. Takže tri z nás. Mather dom. Tak to je pre stolovanie Mather je. Stavím sa, že všetky jedálne majú hromady zásobníkov, ako je tento. A to je skutočne reprezentatívna o niečo, čo sme zrejme už videli. Nazvali sme ju doslova hromadu. A stack, pokiaľ ide o váš pamäti počítača, je miesto, kde prejde dáta zatiaľ čo funkcia volaná. 

Napríklad, aké druhy vecí ísť na zásobníku s ohľadom na Rozloženie pamäte sme diskutovali v týždňoch minulých? Čo je to? 

DIVÁKOV: Volanie funkcie. 

DAVID Malan: Ospravedlňujem sa. 

DIVÁKOV: Volanie funkcie. 

DAVID Malan: Volanie funkcie, ale konkrétne, čo je vo vnútri každého tie rámy? Aké veci? Jo. Takže lokálne premenné. Kedykoľvek sme potrebovali nejakú miestne úložisko, ako argument, alebo int I, alebo int temp, alebo čokoľvek miestnej premenná, boli sme uvedenie, že na zásobníku. A hovoríme, že stack, pretože tohto vrstvenie myšlienky. Len trochu zhoduje s realitou, Koncept tohto rozhodnutia. 

Ale ukazuje sa, že zásobník možno tiež pozerať ako na dátové štruktúry, Alternatívou k poľu, alternatívne do prepojeného zoznamu. Niečo koncepčne zaujímavejšie že môže byť stále realizovaný pomocou niektoré z tých, veci, ale je to iný typ dátová štruktúra podporu, naozaj, iba dve operácie. Ale môžete pridať na milovník funkcie než tie. Ale to sú základy - tlačiť a pop. 

A nápad s hromadou je, že keď som sú tu, s alebo bez Annenberg vedel, zásobník od vedľa s číslom 9 na ňom. Takže len int. A ja chcem, aby sa zasadila to na dátach štruktúra, ktorá v súčasnej dobe je prázdny. Zoberme si to v spodnej časti zásobníka. Ja by som tlačiť toto číslo 9 na stack, a teraz je to tu. 

Ale zaujímavá vec o zásobníku je, že keď som chcel, aby sa zasadila niektoré ďalšie hodnoty, ako 17, a tlačím to do zásobníka, budem robiť iba intuitívne vec, ja som jednoducho ísť Aby som to presne tam, kde ľudia by mať tendenciu dať na povrch. Ale čo je zaujímavé, teraz je, ako sa dostanem na 9? Viete, ja nie bez nejakej námahy. 

Takže to, čo je na tom zaujímavé zásobník, ktorý je zo svojej podstaty Je to štruktúra dát LIFO. Silly spôsob, ako popisovať posledný dnu, prvý von. Takže posledné číslo V tejto dobe bolo 17 rokov. Takže keď chcem niečo pop off zo zásobníka, môže to byť iba 17. Takže je povinný poriadok pôsobenia u nás, kde je posledná položka musí byť v prvej von. Preto je skratka, LIFO. 

Tak prečo by to mohlo byť užitočné? Sú ich kontexty, v ktorých by si Chcete dátovú štruktúru, ako je tento? No, je to určite užitočné, vnútri počítača. Takže operačné systémy jednoznačne použiť Druh údajovej štruktúry pre komíny. Budeme tiež vidieť rovnakú myšlienku pokiaľ ide o webové stránky. Takže tento týždeň a budúci týždeň a ďalej, a ako začať vykonávať web stránky v jazyku HTML s názvom, môžete vlastne používať dátovú štruktúru, ako je to, či stránka je v správnom formáte. Vzhľadom k tomu, uvidíme všetky webové stránky postupujte podľa určitá hierarchia, odsadenie , Že sa na konci dňa, sa stromová štruktúra pod kapotou. Tak o tom viac v len trochu. 

Ale teraz, poďme navrhnúť pre Moment, ako by sme mohli ísť o predstavuje to, čo je stoh? Dovoľte mi navrhnúť, že by sme realizovať zásobník s kódom, ako je tento. Takže zásobník bude mať vnútri nej dve veci, polia, tzv vaničky, len aby bol v súlade s demo. A každá z položiek v tomto poli bude typu int. A kapacita je pravdepodobne to, čo? Pretože som nepísal úplná definícia tu. 

Je to asi maximum Veľkosť poľa. A je to asi deklarovaný ako ostrý definovať v hornej časti súboru, niektoré druh konštantný ako vyplýva z samotná kapitalizácie. Takže niekde kapacita je definovaná ako maximálnu možnú veľkosť. Medzitým, vnútri dátové štruktúry známy ako zásobník sa bude byť celé číslo len známy jednoducho ako veľkosť. 

Takže ak by som mal reprezentovať to teraz obrazovo, predpokladajme, že tento Celá čierna skrinka predstavuje svoj stack. Vnútri nej sú dve premenné. Takže budem čerpať Prvý je napríklad veľkosť. A druhá idem kresliť ako pole. 

Ale len preto, aby sa veci riadne, Normálne by som nakresliť poľa ako , Ale je to celkom pekný ak budeme zodpovedať skutočnosti, alebo odpovedať mentálny model. Dovoľte mi teda namiesto toho vypracovať poľa vertikálne, čo je len opäť umelec stvárnenie. Nezáleží na tom, čo to je pod kapotou. A povieme, že v predvolenom nastavení kapacita bude tri. Takže to bude miesto 0, to bude namiesto 1, toto bude miesto 2. 

Keby som podplatiť s dôrazom loptou, by niekto chcel prísť a spustiť palubu tu na chvíľu? OK, videl vaša ruka ako prvý. Poď hore. Dobrá. Takže myslím, že je Steven. Poď hore. Dobrá. 

Ale predpokladajme, že teraz sme sa vrátiť a počiatočné stav sveta, kde som práve vyhlásil stack, a to bude mať kapacitu tri. Ale veľkosť nebola stanovená. Zásobníky nebola stanovená. Takže pár otázok ako prvý. A dovoľte mi, aby som vám mikrofón, takže môžete podieľať sa aktívnejšie na to. 

Takže to, čo je vnútri veľkosti v túto chvíľu včas, ak všetko, čo som urobil, je vyhlásený stoh jeden riadok kódu? 

STEVEN: Moc nie. 

DAVID Malan: OK, nič moc. Vieme, čo je vo vnútri veľkosti, vieme, čo je vo vnútri tohto poľa Si tu prvýkrát? 

STEVEN: Len náhodný kód, nie? Just - 

DAVID Malan: Jo, ja idem hovoria kód, ale náhodne - 

STEVEN: Veci. 

DAVID Malan: Veci, ako je náhodné 

STEVEN: bity. 

DAVID Malan: Bity, že jo? Takže odpadky hodnoty, nie? Takže permutácie 0 a 1 je. Zvyšky predchádzajúcich zvyklostí tejto pamäte. A naozaj neviem, čo sa hodnoty sú, takže väčšinou je nakresliť ako otázniky. 

Takže prvá vec, že ​​sme pravdepodobne bude chcieť, aby to tu - a dovoľte mi, aby som toto pole vnútri odtiaľ názov - zásobníky. Čo by sme mali pravdepodobne inicializovať veľkostí, ak chceme začať používať túto stack? 

STEVEN: Zásobník je pod 3. 

DAVID Malan: Tak OK. Aby bolo jasno, je deklarovaný výkon inde tri. A to je to, čo som používal alokovať pole. Veľkosť sa bude odkazovať na to, koľko zásobníky sú v súčasnej dobe na zásobníku. 

STEVEN: Zero. 

DAVID Malan: Tak to musí byť nula. Takže choďte do toho a s akýmkoľvek prstom, nakresliť nulu veľkosti. Dobrá. Takže teraz, čo je vo vnútri tohto tu, nevieme. Sú to naozaj len odpadky hodnoty. Takže by sme mohli čerpať otázniky, ale Skúsme udržať doska čistá teraz pretože nezáleží na tom, čo tam je. Nepotrebujeme k inicializácii poľa k ničomu, pretože ak vieme, že veľkosť zásobníka je nula, no, nesmie byť pri pohľade na niečo v Toto pole tak na tento bod v čase. 

Takže teraz, predpokladám, že tlačím číslo 9 do zásobníka. Ako by sme mali aktualizovať dátovú štruktúru Vnútri tejto čiernej skrinky? Aké hodnoty je potrebné zmeniť? 

STEVEN: V - veľkosť? 

DAVID Malan: OK. Veľkosť by mala byť čo? 

STEVEN: Veľkosť by bol jeden. 

DAVID Malan: OK. Takže veľkosť by sa mala stať jedným. Takže si môžete urobiť v pár ohľadoch. Dovoľte mi, aby som vám teraz vaša Prst je guma. Dobrá. Tak teraz je prst kefu. Dobrá. A teraz, čo ešte sa musí zmeniť, Je zrejmé, že v dátovej štruktúre? 

STEVEN: Ideme od zdola až 9. 

DAVID Malan: 9. OK, dobre. Takže ešte nezáleží, čo je v umiestnenie jeden alebo dva, pretože sú odpadky hodnoty, ale nemali by sme sa obťažovať hľadá tam, pretože veľkosť je nám hovorí, že iba prvý prvok je vlastne legitímna. Takže teraz tlačím 17 na zozname. Čo sa stane obrázku? 

STEVEN: Takže veľkosť sa chystá ísť na dva. 

DAVID Malan: OK. Ste guma - oops. Ste gumu. 

STEVEN: Eraser. 

DAVID Malan: Si kefu. 

STEVEN: Brush. 

DAVID Malan: OK. A čo ešte? 

STEVEN: A potom sme - 

DAVID Malan: Usilovali sme 17. 

STEVEN: Držíme 17 na vrchole, a preto - 

DAVID Malan: OK, dobre. 

STEVEN - klesnúť dole. 

DAVID Malan: Dobre. Začína to byť jednoduché. Nebudem, ktoré vám pomôžu tentokrát. Zatlačte 22. 

STEVEN: Hotovo. Štát gumu. Stávam sa štetcom. A potom dávam 22. 

DAVID Malan: 22. Výborný. Takže ešte raz. Ja som teraz bude tlačiť do zásobníka 26. 

STEVEN: Ooh. Ach bože. Naozaj ma zaskočila. 

DAVID Malan: To snáď nie pozri tento rok? 

STEVEN: Nevidel som to blíži. Mohli by sme znova počiatočná kapacita? 

DAVID Malan: To je dobrá otázka. Takže sme trochu maľoval seba v rohu tu. Tam naozaj nie je dobrý pozor Steven pretože sme pridelené toto pole staticky, aby som tak povedal, vnútri z dátovej štruktúry. A my sme v podstate pevne zakódovaný sa, že je veľkosť tri. Takže naozaj nemôžeme prerozdelia ju. 

Mohli by sme, keby sme išli naspäť, sme obnovovaný zásobníky sa ukazovateľ, ktorý sme potom pomocou malloc do ruky pamäti. Pretože ak máme pamäť, z haldy pomocou malloc, sme by potom uvoľniť ho. Ale skôr, než ju uvoľní, mohli by sme prerozdeliť väčší kus pamäti, aktualizovať ukazovateľ, a tak ďalej. Ale teraz je to naozaj najlepšie, čo môžeme urobiť. Stlačte a pop sa pravdepodobne bude majú uviesť niektoré chyby. 

Tak napríklad, naše realizácie Push by sa mohol vrátiť bool, ktorá predtým vrátil pravda, pravda, pravda. Ale štvrtý čas, bude to mať vrátiť false, napríklad. Dobrá. Veľmi dobre. Blahoželáme. Získali ste stresu loptu dnes. 

[APPLAUSE] 

STEVEN: Ďakujem. 

DAVID Malan: Ďakujem. OK, tak to sa zdá byť moc o krok vpred, nie? Popísali sme túto dátovú štruktúru. Bolo to pôsobivé, nie? Operačné systémy páčiť. Zrejme na webe môžete využívať toto, a ďalších aplikácií stále. Ale to, čo hlúpe obmedzenia, že sme späť na triedenie v týždni dva limity kde sme pevnú veľkosť poľa. 

Takže tam sú naozaj pár spôsoby, ako by sme mohli vyriešiť. Mohli by sme dynamicky alokovať pole, nie ťažké kódovanie ako som hotoví, ale znova, ktorým to, aby bolo jasno, ako niečo také. Int * zásobníky, nerozhoduje na objeme ešte. Ale keď som vyhlásil stoh inde v mojom kóde, mohol by som potom volania malloc, získať adresu kusom pamäť, a ja som mohol priradiť že adresa zásobníkov. 

A potom, pretože je to len kus pamäť, mohol by som aj naďalej používať námestí držiak zápis obvyklým spôsobom. Vzhľadom k tomu znova, je tu nejako to funkčným ekvivalentom polí a kúsky pamäti, ktoré prichádzajú späť z malloc. Môžeme správať ako ostatní pomocou ukazovateľa aritmetický alebo hranatá zátvorka notácie. Takže to je jeden prístup. 

Ale ako inak by sme mohli zaviesť tento rovnaké dátové štruktúry, prípadne? Je to tak? Mám pocit, že práve to vyriešil problém ako pred týždňom. Čo bolo riešenie tohto problému že Steven narazil? Takže spojové zoznamy, vpravo. 

Ak je problém, že maľujeme sami do rohu prideľovanie dopredu príliš málo pamäti, že potom sa nejako riešiť, no, prečo nie len zabrániť tomu, aby vydá dohromady? Prečo nie len vyhlásiť zásobníky sa ukazovateľ na uzol, ergo spájať zoznam, a potom jednoducho prideliť nové uzly zakaždým, keď Steven potrebné, aby sa zmestili číslo do dátovej štruktúry. 

Takže obraz by mal zmeniť. To nebude tak čisté a ako jednoduché, ako len polia troch ints. Teraz to bude ukazovateľ na struct, a to struct sa chystá majú int a ďalšie ukazovateľ. Je to povedie prostredníctvom tohto ukazovateľa iné takéto struct na ďalší taký struct. Takže fotka by v skutočnosti dostať trochu Messier. A boli by sme šípky viazanie všetko dohromady. 

Ale to je v poriadku, že jo, pretože Videli sme, ako to urobiť. A akonáhle sa dostanete pohodlne vykonáva niečo ako prepojený zoznam, ktorý budete musieť robiť, keď rozhodnete hash tabuľku s oddelené zreťazenie pre p-set 6, môžete ho použiť ako stavebný blok, alebo prísada, alebo Scratch hovoriť, postup, niečo, čo dáte, vám vytvorili svoj vlastný kúsok skladačky ktoré potom môžete znovu použiť. Takže kompromisy, ale možné riešenia že sme vlastne nevideli. 

Takže docela často, vidíte to každý rok alebo dva, keď Apple vydal niečo nové, a všetci blázni line up mimo Apple uložiť ku kúpe ich marginálne prejsť na hardvér. Hovorím to, je to v poriadku, pretože Som jeden z tých ľudí. Takže, aké dátové štruktúry môže predstavovať túto skutočnosť? 

No, povedzme, že front, linka. Takže Briti to nazval typicky front rovnako, takže je to pekné meno. A dve operácie, ktoré fronty musí podporovať budeme volať Zaradí prevádzka a dequeue prevádzka, ktoré sú si podobné duch tlačiť a pop. Je to len trochu líši konvencie, čo hovoríme nich. Ale enqueue niečo znamená pridať alebo vložiť do dátovej štruktúry. Dequeue znamená odstrániť. Ale vzhľadom k tomu, zásobník bol dátový LIFO štruktúra, fronta je prvá, Prvý z dátovej štruktúry. 

Ak ste prvý človek v rade, budete prvá osoba, ktorá sa z radu a kúpiť si nový prístroj. Predstavte si, ako naštvaný títo ľudia by ak Apple namiesto toho používal balík pre inštancie, na vykonanie vychystávanie do vašej novú hračku. Takže fronty zmysel, určite, a my môžeme myslieť na všetky druhy aplikácie, pravdepodobne pre front, zvlášť keď chcete spravodlivosť. Takže, ako môžeme realizovať tieto ako dátové štruktúry? 

Navrhujem, že by sme mohli musíte urobiť to takto. Takže budem teraz mať čísla. Takže budeme držať to jednoduchý, a nie nutne hovoriť, pokiaľ ide o zásobníkov. Len čísla, ktoré ľudia dostali. Kapacita bude opäť upevnite Celkový počet osôb, ktoré môžu byť v tento riadok ako troch alebo bez ohľadu na iná hodnota. 

Ale navrhujem, že musím sledovať nielen veľkosťou fronta, koľko vecí v ňom. Takže veľkosť je aktuálna veľkosť, kapacita je maximálna veľkosť. Len raz, nomenklatúra konvencií. Prečo potrebujem ďalšie int vnútri z frontu, ako sledovať, kto je v prednej línie? Prečo musím k tomu, že v tomto prípade? 

No, ako sa tento obrázok sa zmení? Mohol by som opätovne využiť väčšinu obrázku. Nechaj ma ísť napred a vymazať to, čo je tu. Dáme to ľahko iné meno tu. Poďme sa zbaviť 17, zbavme na 9, poďme sa zbaviť 3. A dodajme ešte jednu vec. Navrhujem, že musím sledovať predné zoznamu, ktorý je práve Bude tiež int. A budeme držať to jednoduchý. Nie spájať zoznam teraz. 

Budeme sa priznať, že budeme Narazí tohto limitu. Ale čo ja chcem vidieť sa stalo tentoraz? Tak, že som do toho pustite a prvý osoba je v súlade, a je to číslo 9.. Máme stres gule. Môžem ukradnúť, povedzme, dva alebo tri ľudí? Jedna, dva, tri? Poď hore. Právo spredu, pretože urobíme tohle rýchlo. 

Každý z vás sa teraz bude fan chalan vo fronte na Apple. Nebudete dostávať Apple hardvér Na konci tohto hoci. Dobrá. Takže ty si číslo 9, ty si číslo 17, číslo 22. Tie sú ľubovoľné čísla, ako je Študent ID alebo ktovie čo ešte. A za chvíľu, začnime začať pridávať veci. A ja budem bežať dosku tu tentoraz. 

Takže v tomto prípade som si inicializuje predné byť - Vlastne som naozaj nestarám, čo predná časť je, pretože veľkosť je nula. Takže to môže byť aj len byť otáznik. To všetko sú otázniky. Takže teraz začneme skutočne vidieť niektoré ľudia čakajú, až v obchode. 

Takže ak číslo 9, ty si prvý, tam v 5 hodín ráno, choďte do toho a line up, alebo v noci. OK. Takže teraz 9 je tu. Takže 9 je v prednej časti zoznamu. Takže budem pokračovať a aktualizovať Veľkosť tohto aktuálnych dát štruktúru, ktorá nie je už 0, ale na 1. Chystám sa dať na 9 Predné zoznamu. Nechaj ma ísť dopredu a prepínať obrazovky takže vidíme okolo nás tu. 

A teraz čo chcem dať na prednej strane? Budem sledovať, že predné fronty hneď je v mieste 0. Pretože to, čo sa bude diať nabudúce? No, predpokladám, teraz som enqueue 17 tiež. Tak hop v rade tam. A opäť, typ dverí Obchod sa tu bude. Takže teraz som pridal 17. A aj keď títo chlapci sú blokovania obrazovka, to je v poriadku, pretože vidíme to tu. Prepáčte. 

DIVÁKOV: Môžeme sa pohybovať - 

DAVID Malan: Nie, to je v poriadku. Je to obrovská tam. Takže 17 je teraz vo vnútri fronty. Musím aktualizovať, ktorá Pole teraz keď? OK, určite veľkosti. A čo predné? OK, no. Predné by sa nemalo meniť, pretože na rozdiel od zásobníka, sme chcete zachovať spravodlivosť. Takže ak 9 prišiel prvý, chceme 9 , Že je prvý z radu do obchodu. 

V skutočnosti, nech sa na to. Než vložíme 22, poďme choďte do toho a dequeue 9. Ako sa voláte? 

Divákov: Jake. 

DAVID Malan: Jake sa deje byť dequeued teraz. Takže ste si na prechádzku do obchodu. A predstierať, že obchod je tamto. Takže teraz, čo je potrebné - dit-dit-dit! Čo by sa stalo teraz? Návrh rozhodnutia. Takže nie je zlý inštinkt, ale - čo sa to voláte? 

DIVÁKOV: David. 

DAVID Malan: David. Takže to, čo Dávid urobil? Snažil sa nejako opraviť údaje štruktúra a pohyb od jeho umiestnenia v bývalom mieste Jake. A to je v poriadku, ak sme ochotní prijať, že ako implementačný detail. Ale najprv poďme aktualizovať dáta štruktúru, ako to robíme. Pretože som nepáčil nápad všetkých ľudia posun v tomto odbore. 

Nie je to veľký problém, ak David robí s jeden krok, ale opäť si spomeniem na keď sme mali osem dobrovoľníkov na etapa a urobili sme ako vloženie triedenie, kde sme museli začať pohybujúce sa všetci okolo. To má drahá, že jo? To ma krčiť sa o veľké O n, veľký O n na druhú znova. Nie je to pocit, ideálny výsledok. 

Takže povedzme, aktualizovať to. Takže veľkosť fronty nie je 2. Je to teraz jednoducho jedno. Ale teraz môžem aktualizovať niečo Nechcel som aktualizovať skôr, Predné zoznamu. Mohol by som povedať, je, že namiesto 1? Takže teraz máme odpadky hodnoty tu odpadky hodnota tu a David v Uprostred tohto odpadu. Ale štruktúra dát je stále neporušená. 

A v skutočnosti som ani potreba zmeniť Jake je bývalý číslo 9, pretože koho to zaujíma. Mám dostatok informácií, teraz v veľkosť, že viem, je tu ešte jedna osoba Táto fronta. A viem, že táto osoba je v mieste 1, nie 0. Nepočítam. 1. tak i Takže dátová štruktúra je ešte OK. 

No, čo sa stane ďalej? Poďme enqueue - Ako sa voláte? 

Divákov: Callen. 

DAVID Malan: Callen. Poďme si enqueue Callen a 22 je teraz vo fronte. Takže teraz, čo sa musí zmeniť, tu? Predné nebude zmeniť, samozrejme. Veľkosť sa zmení na 2 znova. A 22 skončí tu, 9 je stále prítomná, ale je to skutočne odpadky hodnota sa. Je to len pozostatok minulosti Jake. 

Takže teraz, čo sa stane, keď Aj dequeue Davide? Jedna posledná operácia, dequeue David. Mohli by sme sa posunúť, ale navrhujem, poďme čo najmenej práce, ako je to možné. Teraz môj dátová štruktúra ide späť vo veľkosti 2-1. Ale fronty Teraz sa 2. Nepotrebujem, aby tieto čísla zmeniť ešte nie, pretože sú len nezmyselné hodnoty. 

Ale teraz, čo sa stane? Dajme tomu, že som enqueue, 26? Mám pocit, že patrím sem. Takže som bol enqueued. Tak nejako som sem patrím. A aj keď to nie je úplne vážim vizuálne na javisku, pretože máme dostatok priestoru, mal by som nemožno tu stojím, prečo? 

DIVÁKOV: Si mimo hraciu plochu. 

DAVID Malan: Správne. Som mimo medze. Som indexované za hranice tohto poľa. Mal by som byť v jednom z tri možné lokality. Tak, kde je najprirodzenejší ísť? Navrhujem, aby sme pákové týždeň jeden trik. Operátor modulo, percento. Pretože som stál pri technicky miesto 3, ale mám 3 mod kapacity, takže 3, znak percenta, 3 - Kapacita je 3. Čo je to? Čo je to zvyšok po delíte 3 od 3? 0. 

Tak, že ma stavia sa Jake, čo je vlastne dobre. Takže teraz vykonávania z toho, čo sa deje na byť trochu bolí hlava. Je to naozaj len jeden riadok bolesti hlavy, kódu. Ale aspon teraz je tu odpadky hodnotu, ale je tu to dva legitímne ints tu. A tvrdím, že teraz sme urobili presne to, čo musíme urobiť, tak dlho, kým zmeníme to, čo Jake hodnota mala byť 26. 

Teraz máme dostatok informácií, stále zachovanie integrity tejto dátovej štruktúry. Sme stále trochu smolu, keď sme Chcem vložiť štyri alebo viac celkom prvky, ale môžem sa aspon pekne efektívne využitie tejto konštanty čas, v skutočnosti. Nechcem sa starať o radenie všetci, pretože sklon Davida bolo. 

Akékoľvek otázky týkajúce sa komínov alebo to front? 

DIVÁKOV: Je dôvod, prečo Potrebujete veľkosť, takže viete, kde má človek? 

DAVID Malan: Presne tak. Musím poznať veľkosť poľa pretože musím presne vedieť, ako mnoho z týchto hodnôt sú legitímne, a aby nájdem, kam umiestniť ďalšia osoba. Presne tak. Veľkosť je - Vlastne sme nemali aktualizovať to ešte. Pridal som sám na 26 rokov. Veľkosť je teraz, nie jeden, ale dva. Takže teraz to naozaj pomáha mi nájsť hlava zoznamu, ktorý nie je 0, nie je 1, ale je 2.. Na prednej strane zoznamu je naozaj číslo 22. Vzhľadom k tomu prišiel ako prvý, a tak by povolené do obchodu predo mnou, aj keď vizuálne stojím bližšie k obchodu. 

V poriadku? Potlesk pre týchto ľudí a necháme ich odtiaľ. 

[APPLAUSE] 

DAVID Malan: Nemohol som nechať budete mať zásobník. Mohli sme vidieť, čo sa stane, keď chcete, ale možno tiež nie. Dobrá. Tak čo teraz čo z toho plynie? No, dovoľte mi navrhnúť, aby tam niekoľko ďalších dátových štruktúr by sme mohli začať pridávať do nášho náradia, ktoré v skutočnosti je úplne, úplne relevantné sme sa ponoriť do vecí webe. Čo zase má nejaké spojenie na stromy vo forme niečo ako DOM, dokument objektový model. Ale uvidíme viac že onedlho. 

Dovoľte mi navrhnúť, z definície, že sme zavolajte strom teraz, čo by ste mohli vedieť, ako viac rodokmeni, kde nejaký predok na Korene stromu. Patriarchálnej alebo matriarchát na samom vrchole stromu. Bez svojho manžela, v tomto prípade. Ale teraz máme, čo budeme nazývať Deti, ktoré sú uzly, ktoré visia z ľavej alebo pravej dieťa dieťa, šípky, ako je znázornené tu. 

Inými slovami, v stromovej štruktúre dát v počítači, strom má nulu alebo viac uzlov. Ak má aspoň jeden uzol, tomu sa hovorí koreň. Sú to veci, ktoré vizuálne čerpáme na vrchole. A to uzol, ako každý iný uzol, môže majú nulový, jeden, alebo dva, alebo tri, alebo ako veľa detí dátová štruktúra podporuje. V tomto prípade, koreň, skladovanie hodnoty jedna, má dve deti, 2 a 3, takže sme zvyčajne vyžadujú dva ľavej Dieťa a 3 právo dieťa. 

A potom, keď sa dostaneme až 5, 6, a 7, 6 by sa dalo nazvať prostredné dieťa. Pokiaľ máte štyri deti, to bude mätúce. Tak sme sa prestať používať tento druh o zástupcu ústne. Ale je to naozaj len rodokmeň. A listy sú tu uzlov, ktoré samy o sebe nemajú žiadne deti. Visí na dno stromu. 

Takže, ako môžeme realizovať strom, ktorý má len dve deti maximálne? Nazveme to binárny strom. Bi opäť znamená dva, v tomto Rovnako tak ako s binárny. A tak to môže mať nula, jedna, alebo maximálne dve deti. 

Ja navrhujem, aby sme realizovať uzol pre túto štruktúru s int n, a potom dva ukazovatele, jeden s názvom vľavo, jeden volal pravdu. Ale to sú len pekné ľubovoľné konvencie. A čo je pekné teraz, najmä pokiaľ druh bojoval s koncepčne rekurzia, alebo si myslel, že to nie je naozaj riešenie pre čokoľvek, najmä ak by spustiť z pamäte. Teraz, keď hovoríme o dátach štruktúry a algoritmy, ktoré umožňujú nás prejsť a manipulovať s nimi, Ukazuje sa, že rekurzia je späť oveľa presvedčivejšie ak nie je krásny spôsob. 

Takže to navrhujem, je implementácia z funkcie Hľadať. Vzhľadom k tomu, dva vstupy - tak, že ju ako čierna skrinka. Vzhľadom k tomu, dva vstupy, n, int a ukazovateľ na strom, ukazovateľ na uzol, alebo naozaj koreň stromu, som Tvrdenie, že táto funkcia môže vrátiť true alebo false, že hodnota n je vnútri tohto stromu. 

Čo je vo vnútri tejto čiernej skrinky? No, štyri vetvy. Prvá len kontroluje. Je-li strom je null, stačí sa vrátiť false. Pokiaľ nie je žiadny uzol, n nie, tam žiadne číslo, len return false. Ak však, n, hodnota, ktorú hľadáte pre, je menšia než stromu šípky n, a Len aby bolo jasno, čo to znamená, keď Píšem strom a potom kliknite na šípku notácie, n? Presne tak. To znamená, že dereferencia ukazovateľ tzv strom. Choďte tam, a potom sa vo vnútri, ktoré uzol a získať jeho pole s názvom n A potom porovnávajú skutočné n, ktorý bol prešiel do vyhľadávacieho proti nemu. 

Takže, ak n je menšia ako hodnota n v uzle stromu sám, dobre, čo to znamená? To znamená, že nič na prvý pohľad. Je to tak? Rovnako ako keď máte rad hodnoty, mali by ste chceli použiť binárne vyhľadávanie ako formu predelu a panuj. Ale to, čo sme predpoklad, je potrebné, aby pre binárne hľadanie práce vôbec v telefónnom zozname a skôr príklady? 

Ako majú byť triedené. Takže poďme upresniť definíciu stromu tu nesmie byť len strom, ktorý môže mať ľubovoľný počet detí. Nie je to len binárny strom, ktorý môže sú 0, 1, 2 alebo maximálne. Ale ako binárny vyhľadávací strom, alebo BST ktorý je len ozdobný spôsob, ako hovoriť binárny strom, tak, že každý uzol je vľavo dieťa, ak je prítomný, je menej než uzla. A každý uzol má pravdu dieťa ak je k dispozícii, je väčšia než samotný uzol. 

Takže inými slovami, ak vás k tomu strom sa, všetky čísla sú starostlivo vyvážiť, ako je to tak, že ak Máte 55 ako root, môže ísť 33 po jeho ľavej strane, pretože to je menej ako 55 rokov. 77 môže ísť po jeho pravej strane, pretože je to viac ako 55 rokov. Ale teraz nevšimol, rovnakú definíciu, Je to rekurzívne definície ústne, musí požiadať o 33. 33 ľavá dieťa musí byť menšie než to, a 33 na pravej dieťa, 44, musí byť väčšie než to. 

Tak to je strom binárneho vyhľadávania, a Navrhujem, s použitím trochu rekurzia, môžeme teraz nájsť n Takže pokiaľ je n menšie ako hodnotu n, ktorá je aktuálny uzol, ja idem dopredu a punt, aby som tak povedal, a len vrátiť bez ohľadu na odpoveď na vyhľadávanie na n stromu je ľavá dieťa. Všimnite si, opäť, táto funkcia len očakáva uzla STAR, ukazovateľ na uzol. Tak určite som si len urobiť strom Šípka vľavo, čo povedie Prechod k inému uzlu. Ale čo je to uzol? 

No, podľa tohto vyhlásenia, vľavo je len ukazovateľ, takže stačí znamená, že som okolo na vyhľadávacie funkcie iný ukazovateľ, a to ktorý reprezentuje Moja ľavá dieťaťa strom. Takže v tomto prípade, ukazovateľ 33, ak je To je náš výber vstupu Zatiaľ, ak n je väčšie ako hodnotu n na aktuálny uzol v strome, potom som ísť dopredu a pramice v druhej smer a len povedať, vôbec sa mi nepáči vedieť, či je táto hodnota n je v stromovej štruktúre ale viem, že ak je to, že je to po mojej právo vetva, aby som tak povedal. Dovoľte mi teda volanie rekurzívne prehľadávať, vykonaním n znovu, ale odovzdaním ukazovateľ na mojej pravej dieťa. 

Inými slovami, keď som v súčasnej dobe 55 a hľadám pre 99, ja viem, že 99 je väčší ako 55, takže presne ako som roztrhol týždne telefónneho zoznamu rokmi a my išiel doprava, podobne ako sme ísť tu. A ja neviem, či je to na mojej pravici dieťa, a to nie je, 77 existuje, ale Viem, že je v tomto smere. Takže hovorím hľadanie na pravom dieťa, 77, a nechajte vyhľadávacie postavu z ak existuje 99 v tomto ľubovoľná Príkladom je v skutočnosti tam. 

Inak, čo je posledný prípad? Je-li strom je null jeden prípad. Ak n je menšia než je aktuálna uzol je hodnota je iný prípad. Ak n je väčšie ako aktuálny uzla hodnota je tretí prípad. Čo je štvrtý a posledný prípad? Myslím, že sme z prípadov, nie? To tak, že n je aktuálny uzol, že som na. 

Takže keď som hľadal 55 v tomto bode v príbehu, že pobočka strom sa vráti true. Takže to, čo je zaujímavé, je, že sme v skutočnosti, na rozdiel od minulosti týždňov, sme trochu na dva základné prípady. A oni nemajú byť všetko v hornej časti. Horný je základný prípad, pretože v prípade, že Strom je null, nič robiť. Stačí sa vrátiť pevný kódované hodnota false. 

Spodná vetva je trochu predvolené, pričom keď sme skontrolovať null, sme skontrolovať, či má byť vľavo, ale to by nemalo byť, máme kontroluje, či by mal byť správne, ale nemali by byť zrejmé, že musí byť tam, kde sme. To je základná vec. Takže tam sú dve rekurzívne prípady obložené tam uprostred. Ale ja som mohol napísať to v ľubovoľnom poradí. Len som myslel, že to trochu prišlo prirodzené najprv skontrolujte, či prípadné chyby, potom sa pozrite doľava, potom sa hneď, potom Predpokladám, že ste na uzle ste vlastne hľadáte. 

Tak prečo by to mohlo byť užitočné? Tak to dopadá - a dovoľte mi prejsť na ukážku tu je to na webe. Chystáme sa začať používať nie programovací jazyk na prvý, ale značkovací jazyk. Značkovací jazyk je ten, ktorý je svojim duchom podobať programovanie jazyk, ale to vám nedáva schopnosť vyjadriť sám seba logicky. To vám dáva možnosť vyjadriť sám seba štrukturálne. 

Kam chceš dať niečo na stránke, webová stránka? Akú farbu chceš, aby sa to? Aké písmo chceš, aby sa to? Aké slová sa vlastne Chcete na webovej stránke? Takže je to značkovací jazyk. Ale potom sme si veľmi rýchlo zavádzať JavaScript, ktorý je plnohodnotným programovací jazyk. Veľmi podobný vo vzhľade syntakticky na C, ale bude to mať nejaký pekné, silnejšie, užívateľsky prívetivé funkcie. 

A jeden z frustrácie na to bod v semestri, je, že budeme čoskoro realizovať pravopisu v ďaleko menej riadkov kódu pomocou iné jazyky ako C sám umožňuje, ale z dôvodu ich Čoskoro budeme rozumieť. Bude to prvá takáto webová stránka. To bude úplne nezaujatý, Prvý robíme. To sa jednoducho povedať, hello world. Ale ak ste nikdy nevideli pred, to je HTML, HyperText Markup Language. 

Ak pôjdete do určitej menu v takmer akýkoľvek prehliadač na akejkoľvek webovej stránky, na internet, môžete vidieť HTML že niektorí ľudia písali vytvoriť túto webovú stránku. A to asi nevyzerá ako krátky alebo čistý, pretože to. Ale bude nasledovať vzor z nich otvorené zátvorky a lomítka a písmená a potenciálne čísla. 

Myslel som, že vám ukážku z toho, čo budete môcť robiť po užití CS50. Nechaj ma ísť do cs.harvard.edu / rob, našej vlastnej Roba Bowdenová domovskú stránku. Urobil to pre nás. Takže budete čoskoro môcť urobiť. A tiež to, čo ste počuli dnes ráno - to, čo si počul dnes ráno - 

[HAMSTER DANCE MUSIC] 

- Budeš mať možnosť, aby sa to. To nás čaká v stredu. Uvidíme sa potom. 

[HAMSTER DANCE MUSIC] DAVID Malan: Na ďalší CS50 -