DAVID Malan: Dobře. Vítejte zpět CS50. To je začátek 8 týdnů. A připomínají, že problém sada 5 skončila s trochou výzvu. Takže za předpokladu, že zpět všechny své výuky Fellows a CA fotografie v souboru card.raw, máte nárok se nyní najít všechny ty lidi, a jeden šťastný výherce bude chodit domů s jedním z těchto věcí, skok pohyb zařízení, které můžete použít pro konečné projekty, například. To každý rok, vede k trochu děsivost. A tak to, co jsem myslel, že to je podíl s vámi o některé poznámky, které mají šel tam a zpět přes zaměstnanci seznam pozdě. Například právě včera večer, citace konec citátu, z jednoho z pracovníků členové, "musel jsem studentský klepání na mé dveře vyfotit se mnou. Stalkeři, povídám. "Zacala dosti popisná a pak jsme se přestěhovali na, tak hodinu později, "jsem měl Student na mě čeká po bodu a měl všechny naše jména a fotografie na některých listů papíru. "v pořádku. Organizována tak, ale ne vše strašidelné ještě. Tak, "já jsem byl mimo město tento víkend, a když jsem se vrátil, byl tam jeden v můj ložnice. "[smích] DAVID Malan: Další citace z pracovníků člen "student přišel do mého domu na Somerville při 4 hodin ráno. "Další personál, "Dostal jsem do hotelu v San Francisco a student čekal na mě v hale se třemi DSLR. " Typ fotoaparátu. "Já nejsem ani na zaměstnance tomto semestru, ale student se vloupal do mého domu tento ráno a zaznamenal celou věc se sklem Google. "A pak konečně, "Nejméně 12 lidí bylo dychtivě čeká na mě, když jsem se dostal z mého limo, a pak jsem probudil. "Dobře. Takže mezi fotografiemi, jak můžete vzpomínám, je tenhle chlapík tady, kdo jste Možná víte, jak Milo Banana, který žije s Lauren Carvalho, naše hlavy vyučování Fellow. Milo Milo, pojď sem chlapče. Milo. Milo. Nezapomínejme, že má na sobě Google Glass, takže my vám ukážeme všechno po něm. Tak to je Milo, pokud chcete vyfotografovat se s ním později. Pokud byste chtěli dát pozor na diváky tam. OK. To je dobré záběry. No, Milo Banana. Oh, nedělejte to. [Smích] OK. Takže jedním slovem, pak o tom, co je před námi, protože jak začneme přechodu, tento týden konkrétně z C na v prostředí příkazového řádku na PHP a JavaScript a SQL a HTML a CSS v web-based prostředí, budeme vybavení vám všechny více znalostí pro případné konečné projektů. Za tímto účelem je hřiště má Tradice pořádání seminářů, které jsou na tangenciální témata k předmětu. Velmi o programování a vývoj aplikací a tak dále, ale nemusí být nutně prozkoumána Kurz vlastní osnovy. Takže pokud by vás mohly zajímat v jednom nebo více z letošních seminářů, zaregistrujte se na cs50.net/seminar. Tam jsou starší semináře na cs50.net/seminars. A na seznamu dosud pro letošní rok Amazing Web Apps jsou s Ruby on Kolejnice, která je alternativou jazyk PHP. Matematická lingvistika. Úvod do IOS, který je platformy, která je použita pro iPhone a iPad rozvoje. JavaScript pro Web Apps, budeme pokrývat , ale v tomto semináři, půjdete do větších detailů. Leap Motion, takže budeme vlastně mají některé našich přátel z Leap Motion, společnost sama, přidejte se k nám. Zítra, ve skutečnosti, aby praktický seminář, je-li vás zajímají. Meteor.js, alternativní metody pro pomocí JavaScriptu není v prohlížeči, ale na serveru. Node.js, který je velmi V tomto duchu také. Elegantní Android design. Android je velmi populární alternativa na iOS a Windows Phone a další mobilní platformy. A Web Security Aktivní obrana. Takže ve skutečnosti, pokud si přejete zapojit se do tohoto, dovolte mi, abych aby na vědomí. Jsme velmi rádi, že Naši přátelé na skok Pohyb, který je spuštění - tento přístroj opravdu jen přišel před několika měsíci - milostivě daroval 30 těchto zařízení do třídy pro co největší počet studentů, je-li byste chtěli půjčit hardware na konci semestru a používat jej pro Skutečná konečná projektu. Oni podporují celou řadu jazyků. Žádný z nich C, žádný z nich PHP, takže realizovat jeden nebo více z těchto seminářů by mohlo být zajímavé. A všechny z nich bude natočen v případě, že nejste schopni zúčastnit osobně. Harmonogram bude oznámeno prostřednictvím email jak zpevnit pokoje. A konečně, pokud jdete na projects.cs.50.net, to je webová stránka udržujeme každý rok, zveme lidé z komunity, fakulty, odbory, zaměstnanci a oba na vnější straně na CS50 navrhnout projektové nápady. Věci jsou předmětem zájmu skupiny studentů. Věci zájmu oddělení. Takže se zase tam, pokud budete bojovat s nejistotou, pokud jde o to, co sami chtěli řešit. Takže poslední době jsme zavedli pravděpodobně složitější datové struktury, než my bychom vidět v minulých týdnech. Rádi bychom se s použitím polí dost šťastně jako užitečná, pokud zjednodušující datové struktury. Pak jsme zavedli nich, které Samozřejmě jsou spojeny seznamy. A to, co bylo jednou z motivací pro zavedení této datové struktury? Jo? Co je to? Diváků: Dynamická velikost. DAVID Malan: Dynamická velikost. Takže zatímco v poli, musíte znát jeho velikost zálohy, pokud přidělit ji. V spojový seznam, nemusíte vědět, že. Můžete jen malloc, nebo obecněji, přidělit další uzel, abych tak řekl, kdykoliv Chci vložit další data. A uzel není předem význam. Je to jen obecný termín, který popisuje nějaký druh kontejneru, který jsme použití v naší datové struktury pro ukládání některé Předmětem zájmu, který je v tomto případě se stalo, že celá čísla. Ale je tu vždy kompromisem. Tak jsme si dynamické velikosti dat struktura, ale jakou cenu platíme? Co je to nevýhoda provázaných seznamů? Jo? DIVÁKŮ: vyžaduje více paměti. DAVID Malan: To vyžaduje více paměť, jak přesně? DIVÁKŮ: [neslyšitelné]. DAVID Malan: Přesně tak. Takže teď jsme ukazatele nástupu do přídavné paměti, že jsme předtím nepotřeboval, protože výhoda z pole, samozřejmě, je to, že všechno je souvislé zpět se zády k sobě, což vám dává náhodný přístup. Protože jen pomocí hranatou závorkou notace, nebo více technicky ukazatel aritmetický, velmi jednoduché sčítání, můžete přistupovat k jakýmkoli prvky v konstantním čase. A ve skutečnosti, to je něco napovídalo další cena, kterou platíme s spojový seznam. Co se stane s dobou chodu něco jako hledat, když chci najít nějakou hodnotu a vnitřek propojeného seznamu? Co mi běží čas stát? Velký O n. Pokud je to tříděny? Co v případě, že datová struktura je třídit? Mohu dělat lépe než velké O z n pro vyhledávání? Ne, protože v nejhorším případě by to mohlo velmi dobře být tříděny, ale počet hledáte by mohla být velká. To by mohlo být číslo 100, která Může se stát, že všechny jak na konci. A protože můžete přistupovat pouze vázané Seznam v tomto provedení by způsob jeho prvního uzlu, jste ještě trochu smůlu. Musíte projít celou věc od začátku až do konce, aby bylo možné nalézt že velké hodnoty jako 100. Nebo zjistit, zda je to ani tam. Takže můžeme dělat to, co algoritmus v datovém struktura, která vypadá takhle? Nemůžeme udělat binární vyhledávání, protože binární hledání vyžaduje, aby jsme měli náhodný přístup. Mohli bychom vyskočit z místa na umístění bez nutnosti sledovat Tyto strouhanka ve formě všech těchto ukazatelů. Teď, jak jsme to realizovat? No, jestli půjdeme na obrazovku zde, je-li můžeme rychle implementujeme tato data struktura - můj rukopis to není všechno, že skvělé tady, ale zkusíme to. Takže typedef struct, a co jsem chcete volat tu věc tady? Uzel. Takže budu se nám začalo. A teď, co je potřeba, aby se uvnitř datová struktura pro které jednotlivě spojový seznam? Kolik pole? Tak dva. Jedním z nich je docela snadné. Tak int n. A tak bychom mohli nazývat n co chceme, ale měl by být int, jestli jsme provádění spojový seznam pro ints. A teď, co dělá druhá pole musí být? Struct node *. Takže když jsem to struct uzel * a pak jsem Můžete volat i to, co chci, ale jen aby bylo jasno, zavolám je další, jak jsme dělali. A pak jsem zavřu složené závorky. A teď, jako minule, Dal jsem uzel dole. Ale když jsem dokládá, že toto je uzel, proč jsem se obtěžovat, že je tak verbose zde deklarovat struct uzel * další, na rozdíl od jen na uzlu * další? Jo? DIVÁKŮ: [neslyšitelné]. DAVID Malan: Přesně tak. Přesně tak. Protože C opravdu vás doslova a vidí pouze definici uzlu cesta sem, nemůžete odkazovat se na to tady. Takže máme tento druh preemptivní Prohlášení tady, což je sice více verbose. Struct uzel, to znamená, že můžeme nyní přistupovat uvnitř datové struktury. A jako stranou, protože to je stává trochu subjektivní teď, hvězda technicky možné jít sem, to může jít sem, může dokonce jít ve středu. Jsme přijala ve stylu příručce pro Samozřejmě, že konvence uvedení hvězda vedle údajů typu, který je v tomto případě, by struct uzel. Ale realizovat v mnoha učebnicích a on-line odkazy, můžete skutečně vidět, že na druhé straně. Ale jen si uvědomit, že jak bude ve skutečnosti práce a vy byste měli být jednoduše konzistentní. Dobrá. Tak to bylo naše prohlášení of struct uzlu. Ale pak jsme začali dělat více sofistikované věci. Například jsme se rozhodli zavést něco jako tabulky hash. Takže tady je hash tabulka velikosti n, indexovány od 0 vlevo nahoře na n minus 1 vlevo dole. To by mohlo být hash tabulka na cokoliv. Ale to, co spoustu věcí jsme se mluvit o použití hash tabulku? Uložení co? Jména. Mohli bychom jména jako jsme minule. A opravdu, můžete uložit cokoli. A uvidíme to znovu PHP a JavaScriptu. Hash tabulky je pěkný druh Swiss Armádní nůž, který vám umožní ukládat skoro co chcete uvnitř je to tím, že sdruží klíče s hodnotami. Klávesy s hodnotami. Nyní v tomto jednoduchém případě, naše Klíče jsou jen čísla. Jsme provádění hash tabulka jako pole. A tak jsou klíče 0, 1, 2, a tak dále. A tak my, jako lidé, rozhodla poslední týden, že víte, co, když jsme bude ukládat jména, prostě libovolně, ale docela rozumně, Předpokládám, že Alice, název, bude jen být indexovány do 0. A Bob, název B, budou indexovány do 1, a tak dále. Takže jsme museli mapování mezi vstupy, které jsou řetězce a hash umístění, které jsou čísla. Tak, že proces je obecně znám jako hašovací funkce, a můžete skutečně implementovat v kódu. Pokud bych chtěl implementovat funkce hash že dělá přesně to, co jsme právě popsal, od minule, bych mohl deklarovat funkci, která bere jako vstup například - a jdem na to na to Obrazovka sem. Pokud bych chtěl realizovat hash funkce, mohl bych říct, něco takového. Bude to vrátit int. Bude to nazvat hash, a to bude akceptovat jako argument řetězec, nebo to může být vhodnější teď, a říkat char *, budeme říkat to. A pak tato funkce má co do činění, nakonec se vrátit int. Teď, jak to dělá, které by mohly není tak jasné. Jdu k provedení tohoto bez Forma kontroly chyb právě teď. Jdu jen slepě říkat, vrátí co je na držáku s 0, minus, řekněme, kapitál středníkem. Totálně rozbité. Není to dokonalé, protože jeden, co když to je null? Špatné věci se bude dít. Za druhé, co když je první písmeno v této jméno není velké písmeno? To není dopadne z vrtů. To by mohlo být malé písmeno nebo ne dopis vůbec. Takže naprosto prostor pro zlepšení tu, ale to je základní myšlenka. Co jsme popsali v minulém týdnu verbálně jen proces mapování Alici 0 a Bob se 1 může být vyjádřena jistě formulaically jako C funkce zde. Zavolal znovu hash, vezme řetězec jako vstup, a pak nějak dělá něco s tímto vstup k výrobě výstupu. Ne na rozdíl od naší černé skříňky popis že jsme dlouho udělat. Nevím, jak by to mohlo být pracuje pod kapotou. Pro problémové sady 6, jeden z problémů, je pro vás rozhodnout, co Váš hashovací funkce může být? Co bude uvnitř, že černá box, a pravděpodobně, bude to trochu zajímavější než to, a rozhodně náchylnější k chybám kontroly, než je tato konkrétní implementace. Ale problémy mohou nastat, že jo? Máme-li datová struktura, jako je tato jeden, co je jedním z problémů můžete narazit na průběhu času vložení stále více a více jmen na hash tabulky? Získáte kolize, ne? Co když máte Alice a Árona, dva lidé, jejichž jména se stalo začít? To vyvolává otázku, kde se dal druhý takový název? No, možná naivně, prostě dát kde Bob patří, ale pak Bob druh šroubované, pokud se pokusíte vložte své jméno a další není místo pro něj. Takže můžete dát Bobe, kde Charlie je, a můžete si to představit velmi rychle převede do trochu nepořádek. Něco lineární na konci, kde se stačí hledat na celou věc Hledám Alice nebo Bob nebo Aaron a Charlie. Tak místo toho navrhuje, místo toho, aby jen lineárně snímání pro prostranství a plopping jména tam jsme navrhla milovník přístup. Hash tabulky realizovány stále s řada indexů, ale datový typ tyto indexy nyní byly ukazatele. Ukazatele k čemu? Ukazatele na lineárními seznamy. Vzhledem k tomu, připomínají, že spojový seznam je opravdu jen ukazatel na uzel, a uzel má další pole, a že uzel má další pole, a tak dále. Takže nyní můžete myslet na tomto poli na levá strana tabulky hash jako což vede k propojeného seznamu. Výhodou je, pokud máte kolize mezi Alicí a Áronovi: Co děláte s druhý takový člověk? Můžete jen připojit ho, aby konec, nebo dokonce na začátku tohoto propojeného seznamu. A vlastně, řekněme, přes nudle že jen druhý. Pokud by největší smysl? Pokud vložím Alici a ona končí Na prvním místě, pak se snažím, aby vložit Aaron jméno, a tam je samozřejmě kolize, měl jsem ho na začátku propojeného seznamu? To je v tomto prvním místě, nebo na konci? DIVÁKŮ: [neslyšitelné]. DAVID Malan: OK. Slyšel jsem, že na začátku. Proto se již na začátku? DIVÁKŮ: [neslyšitelné]. DAVID Malan: OK. Je to podle abecedy, tak to je hezké. To je dobrá vlastnost. To vám ušetří mi čas potenciálně. To mi nedovolí dělat binární vyhledávání, ale já by alespoň být schopen vymanit se ze smyčky, pokud si uvědomuji, no, já jsem cesta minulosti se Aaron by v tomto řazeny propojeného seznamu. Nemám ztrácet čas hledáním až do konce. Tak to je rozumné. Proč jinak by mohlo chcete vložit kolize název na na začátku seznamu? Co je to? DIVÁKŮ: [neslyšitelné]. DAVID Malan: Mohlo by to trvat dlouho dostat se na konec seznamu. A ve skutečnosti, déle a déle. Čím více jmen, které vložíte začátek, delší než řetěz dostane. Čím déle tu, která souvisí Seznam je dostane. Takže jste opravdu jen ztrácíš čas. Možná, že jste na tom lépe udržovat konstantní Čas vložení, velký O z 1, tím, že vždy dávat na sebe narážející na název počátek propojeného seznamu, a ne tolik znepokojující o třídění. Jaký je nejlepší odpověď? Je to jasné. To druh závisí na tom, co distribuce je to, co je vzor jména vkládáte. To nemusí být nutně jasná odpověď. Ale zde je opět design příležitost. Tak jsme pak se podíval na tu věc, která je opravdu jiná velká příležitost pro p-set 6. A uvědomit si, pokud jste tak již neučinili, Zamyla se ponoří do obou z nich, hashovací tabulky a snaží se, ve více detailu. A video návod je vložené do p-set spec. To byl trie - T-R-I-E. A co bylo zajímavé, bylo to, že doba provozu Není třeba hledat jména, jako je Maxwell Minule byl velký O čeho? Co je to? Diváků: počet písmen. DAVID Malan: počet písmen. Slyšel jsem dvě věci. Počet písmen a konstantním čase. Takže pojďme se, že jako první. Počet písmen. No, to datová struktura, odvolání, je jako strom, rodokmen, každý z jejichž uzly jsou tvořeny poli. A ty pole jsou odkazy na jiné takové uzly, či jiné podobné pole ve stromu. Takže pokud bychom chtěli pak určují zda Maxwell je tady, mohl bych jít na první pole, na samém vrcholu strom, tzv. kořen, horní část trie a postupujte ukazatel m, pak ukazatel, pak x, w, e, l, l. A pak, když vidím nějaký speciální symbol, označený zde jako trojúhelník. V kódu uvidíte, že navrhne, aby si implementován jako bool, jen říkám ano nebo ne, slovo, zde zastaví. No, jednou jsme šli do M-A-X-W-E-L-L, pocit, sedm, možná osm když jdeme jeden kolem ní osm kroky k nalezení Maxwell. Nebo řekněme, že K. Ale vzpomínám poslední čas, jsem tvrdil, že v případě, že je realisticky maximální délka na slovo, stejně jako 40-některé-liché znaky, Maximální délka znamená, konstantní hodnotu. Takže opravdu, ano, je to technicky velký O 8 nebo 7, nebo opravdu velký O K. Ale v případě, že je konečný limit na to, co K může být, že je konstantní. A tak je to velký O z 1 na konci dne. Není v reálném světě. Ne, když skutečně začít sledovat vaše hodiny, jak váš program běží. Je to naprosto to bude trochu pomalejší než skutečně konstantní čas na jeden krok. Bude to sedm nebo osm stupňů, ale stále je to mnohem, mnohem lepší než algoritmu, jako je velký O N, který závisí na velikosti, co je v datové struktury. Všimněte si, že zde je vzhůru, můžeme vložit milionkrát více jmen do tohoto datová struktura, ale kolik kroků to bude trvat nám najít Maxwell v tomto případě? Žádné. On je nedotčena. A k dnešnímu dni, nemyslím si, že jsme viděli, příklad datové struktury nebo algoritmus, který byl zcela ovlivněna vnější chování, jako je to. Ale to nemůže být úžasné. To nemůže být jediným řešením pro p-set A to ne. To není nutně data Struktura byste měli tíhnout k, protože stejně jako tabulky hash, kompromis. Co je to cena, kterou zaplatíte tady? Paměť. Myslím, že je to otřesné množství paměti. A můžete tak docela vidět tady, protože autor obrázku samozřejmě zkrácen všech polí a my nevidíme mnoho a je Hostely a C je a Q je a Y je a Z je v těchto polích. Ale jsou tam. Každý z těchto uzlů je celý soubor některých 26 nebo více bytů, z nichž každá což představuje dopis. 27 V našem případě, tak, že může podporovat apostrofy v sadě problém. Tak to datová struktura je opravdu, opravdu hustý a široký. A to samo o sobě by mohlo skončit zpomaluje věci dolů, nebo alespoň vás to stálo mnohem více prostoru. Ale znovu, můžeme vyvodit srovnání zde. Vzpomínám si na chvíli zpět, jsme dosáhli mnohem více vzrušující doba chodu při třídění když použijeme sloučení druh, ale cena jsme zaplatili dosáhnout n log n o sloučení druh vyžaduje, aby trávíme více jaký zdroj? Více prostoru. Potřebovali jsme sekundární matici kopírovat lidi do, stejně jako jsme tady na jevišti. Takže znovu, žádné jasné vítěze, ale jen subjektivní konstrukce rozhodnutí být dělán. Dobrá. Takže jak na to? Každý, kdo poznat, které D-Hall? OK. Takže tři z nás. Mather dům. Tak to je pro stolování Mather je. Vsadím se, že všechny jídelny mají hromady zásobníků, jako je tento. A to je skutečně reprezentativní o něco, co jsme zřejmě již viděli. Nazvali jsme ji doslova hromadu. A stack, pokud jde o váš paměti počítače, je místo, kde přejde data zatímco funkce volána. Například, jaké druhy věcí jít na zásobníku s ohledem na Rozvržení paměti jsme diskutovali v týdnech minulých? Co je to? DIVÁKŮ: Volání funkce. DAVID Malan: Omlouvám se. DIVÁKŮ: Volání funkce. DAVID Malan: Volání funkce, ale konkrétně, co je uvnitř každého ty rámy? Jaké věci? Jo. Takže lokální proměnné. Kdykoliv jsme potřebovali nějakou místní úložiště, jako argument, nebo int I, nebo int temp, nebo cokoliv místní proměnná, byli jsme uvedení, že na zásobníku. A říkáme, že stack, protože tohoto vrstvení myšlenky. Jen trochu shoduje s realitou, Koncept tohoto rozhodnutí. Ale ukazuje se, že zásobník lze také pohlížet jako na datové struktury, Alternativou k poli, alternativní do propojeného seznamu. Něco koncepčně zajímavější že může být stále realizován pomocí některé z těch, věci, ale je to jiný typ datová struktura podporu, opravdu, pouze dvě operace. Ale můžete přidat na milovník funkce než ty. Ale to jsou základy - tlačit a pop. A nápad s hromadou je, že když jsem jsou tady, s nebo bez Annenberg věděl, zásobník od vedle s číslem 9 na něm. Takže jen int. A já chci, aby se zasadila to na datech struktura, která v současné době je prázdný. Vezměme si to ve spodní části zásobníku. Já bych tlačit toto číslo 9 na stack, a teď je to tady. Ale zajímavá věc o zásobníku je, že když jsem chtěl, aby se zasadila některé další hodnoty, jako 17, a tlačím to do zásobníku, budu dělat pouze intuitivní věc, já jsem prostě jít Abych to přesně tam, kde lidé by mít tendenci dát na povrch. Ale co je zajímavé, teď je, jak se dostanu na 9? Víte, já ne bez nějaké námahy. Takže to, co je na tom zajímavé zásobník, který je ze své podstaty Je to struktura dat LIFO. Silly způsob, jak popisovat poslední dovnitř, první ven. Takže poslední číslo V této době bylo 17 let. Takže když chci něco pop off ze zásobníku, může to být pouze 17. Takže je povinný řád působení u nás, kde je poslední položka musí být v první ven. Proto je zkratka, LIFO. Tak proč by to mohlo být užitečné? Jsou jejich kontexty, ve kterých bys Chcete datovou strukturu, jako je tento? No, je to jistě užitečné, uvnitř počítače. Takže operační systémy jednoznačně použít Druh datové struktury pro komíny. Budeme také vidět stejnou myšlenku pokud jde o webové stránky. Takže tento týden a příští týden a dále, a jak začít provádět web stránky v jazyce HTML s názvem, můžete vlastně používat datovou strukturu, jako je to, zda stránka je ve správném formátu. Vzhledem k tomu, uvidíme všechny webové stránky postupujte podle určitá hierarchie, odsazení , že se na konci dne, se stromová struktura pod kapotou. Tak o tom více v jen trochu. Ale teď, pojďme navrhnout pro Moment, jak bychom mohli jít o představuje to, co je stoh? Dovolte mi navrhnout, že bychom realizovat zásobník s kódem, jako je tento. Takže zásobník bude mít uvnitř ní dvě věci, pole, tzv. vaničky, jen aby byl v souladu s demo. A každá z položek v tomto poli bude typu int. A kapacita je pravděpodobně to, co? Protože jsem nepsal úplná definice zde. Je to asi maximum Velikost pole. A je to asi deklarován jako ostrý definovat v horní části souboru, některé druh konstantní jak vyplývá z pouhá kapitalizace. Takže někde kapacita je definována jako maximální možnou velikost. Mezitím, uvnitř datové struktury známý jako zásobník se bude být celé číslo jen známý jednoduše jako velikost. Takže pokud bych měl reprezentovat to teď obrazově, předpokládejme, že tento Celá černá skříňka představuje svůj stack. Uvnitř ní jsou dvě proměnné. Takže budu čerpat První je například velikost. A druhá jdu kreslit jako pole. Ale jen proto, aby se věci řádné, Normálně bych nakreslit pole jako , ale je to docela hezký pokud budeme odpovídat skutečnosti, nebo odpovídat mentální model. Dovolte mi tedy namísto toho vypracovat pole vertikálně, což je jen opět umělec ztvárnění. Nezáleží na tom, co to je pod kapotou. A řekneme, že ve výchozím nastavení kapacita bude tři. Takže to bude místo 0, to bude místo 1, toto bude místo 2. Kdybych podplatit s důrazem míčem, by někdo chtěl přijít a spustit palubu zde na chvíli? OK, viděl vaše ruka jako první. Pojď nahoru. Dobrá. Takže myslím, že je Steven. Pojď nahoru. Dobrá. Ale předpokládejme, že teď jsme se vrátit a počáteční stav světa, kde jsem právě vyhlásil stack, a to bude mít kapacitu tři. Ale velikost nebyla dosud stanovena. Zásobníky nebyla dosud stanovena. Takže pár otázek jako první. A dovolte mi, abych vám mikrofon, takže můžete podílet se aktivněji na to. Takže to, co je uvnitř velikosti v tuto chvíli včas, jestliže všechno, co jsem udělal, je prohlášen stoh jeden řádek kódu? STEVEN: Moc ne. DAVID Malan: OK, nic moc. Víme, co je uvnitř velikosti, víme, co je uvnitř tohoto pole Jsi zde poprvé? STEVEN: Jen náhodný kód, ne? Just - DAVID Malan: Jo, já jdu říkají kód, ale náhodně - STEVEN: Věci. DAVID Malan: Věci, jako je náhodné STEVEN: bity. DAVID Malan: Bity, že jo? Takže odpadky hodnoty, ne? Takže permutace 0 a 1 je. Zbytky předchozích zvyklostí této paměti. A opravdu nevím, co se hodnoty jsou, takže většinou je nakreslit jako otazníky. Takže první věc, že ​​jsme pravděpodobně bude chtít, aby to tady - a dovolte mi, abych toto pole uvnitř odtud název - zásobníky. Co bychom měli pravděpodobně inicializovat velikostí, chceme-li začít používat tuto stack? STEVEN: Zásobník je pod 3. DAVID Malan: Tak OK. Aby bylo jasno, je deklarovaný výkon jinde tři. A to je to, co jsem používal alokovat pole. Velikost se bude odkazovat na to, kolik zásobníky jsou v současné době na zásobníku. STEVEN: Zero. DAVID Malan: Tak to musí být nula. Takže jděte do toho a s jakýmkoliv prstem, nakreslit nulu velikosti. Dobrá. Takže teď, co je uvnitř tohoto tady, nevíme. Jsou to opravdu jen odpadky hodnoty. Takže bychom mohli čerpat otazníky, ale Zkusme udržet deska čistá teď protože nezáleží na tom, co tam je. Nepotřebujeme k inicializaci pole k ničemu, protože pokud víme, že velikost zásobníku je nula, no, nesmí být při pohledu na něco v Toto pole tak na tento bod v čase. Takže teď, předpokládám, že tlačím číslo 9 do zásobníku. Jak bychom měli aktualizovat datovou strukturu Uvnitř této černé skříňky? Jaké hodnoty je třeba změnit? STEVEN: V - velikost? DAVID Malan: OK. Velikost by měla být co? STEVEN: Velikost by byl jeden. DAVID Malan: OK. Takže velikost by se měla stát jedním. Takže si můžete udělat v pár ohledech. Dovolte mi, abych vám nyní vaše Prst je guma. Dobrá. Tak teď je prst kartáč. Dobrá. A teď, co ještě se musí změnit, Je zřejmé, že v datové struktuře? STEVEN: Jdeme od zdola až 9. DAVID Malan: 9. OK, dobře. Takže ještě nezáleží, co je v umístění jeden nebo dva, protože jsou odpadky hodnoty, ale neměli bychom se obtěžovat hledá tam, protože velikost je nám říká, že pouze první prvek je vlastně legitimní. Takže teď tlačím 17 na seznamu. Co se stane obrázku? STEVEN: Takže velikost se chystá jít na dva. DAVID Malan: OK. Jste guma - oops. Jste gumu. STEVEN: Eraser. DAVID Malan: Jsi kartáč. STEVEN: Brush. DAVID Malan: OK. A co ještě? STEVEN: A pak jsme - DAVID Malan: Usilovali jsme 17. STEVEN: Držíme 17 na vrcholu, a proto - DAVID Malan: OK, dobře. STEVEN - klesnout dolů. DAVID Malan: Dobře. Začíná to být snadné. Nebudu, které vám pomohou tentokrát. Zatlačte 22. STEVEN: Hotovo. Stát gumu. Stávám se štětcem. A pak dávám 22. DAVID Malan: 22. Výborný. Takže ještě jednou. Já jsem teď bude tlačit do zásobníku 26. STEVEN: Ooh. Ach bože. Opravdu mě zaskočila. DAVID Malan: To snad ne viz letos? STEVEN: Neviděl jsem to blíží. Mohli bychom znovu počáteční kapacita? DAVID Malan: To je dobrá otázka. Takže jsme trochu maloval sebe v rohu zde. Tam opravdu není dobrý pozor Steven protože jsme přiděleno toto pole staticky, abych tak řekl, uvnitř z datové struktury. A my jsme v podstatě pevně zakódován se, že je velikost tři. Takže opravdu nemůžeme přerozdělí ji. Mohli bychom, kdybychom šli zpátky, jsme obnovován zásobníky se ukazatel, který jsme pak pomocí malloc do ruky paměti. Protože pokud máme paměť, z haldy pomocí malloc, jsme by pak uvolnit jej. Ale dříve, než ji uvolní, mohli bychom přerozdělit větší kus paměti, aktualizovat ukazatel, a tak dále. Ale teď je to opravdu nejlepší, co můžeme udělat. Stiskněte a pop se pravděpodobně bude mají uvést některé chyby. Tak například, naše realizace Push by se mohl vrátit bool, která předtím vrátil pravda, pravda, pravda. Ale čtvrtý čas, bude to mít vrátit false, například. Dobrá. Velmi dobře. Blahopřejeme. Získali jste stresu míč dnes. [APPLAUSE] STEVEN: Děkuji. DAVID Malan: Děkuji. OK, tak to se zdá být moc o krok vpřed, ne? Popsali jsme tuto datovou strukturu. Bylo to působivé, ne? Operační systémy líbit. Zřejmě na webu můžete využívat toto, a dalších aplikací stále. Ale to, co hloupé omezení, že jsme zpět na třídění v týdnu dva limity kde jsme pevnou velikost pole. Takže tam jsou opravdu pár způsoby, jak bychom mohli vyřešit. Mohli bychom dynamicky alokovat pole, ne těžké kódování jako jsem hotoví, ale znovu, kterým to, aby bylo jasno, jak něco takového. Int * zásobníky, nerozhoduje na objemu ještě. Ale když jsem prohlásil stoh jinde v mém kódu, mohl bych pak volání malloc, získat adresu kusem paměť, a já jsem mohl přiřadit že adresa zásobníků. A pak, protože je to jen kus paměť, mohl bych i nadále používat náměstí držák zápis obvyklým způsobem. Vzhledem k tomu znovu, je tu nějak to funkčním ekvivalentem polí a kousky paměti, které přicházejí zpět z malloc. Můžeme chovat jako ostatní pomocí ukazatele aritmetický nebo hranatá závorka notace. Takže to je jeden přístup. Ale jak jinak bychom mohli zavést tento stejné datové struktury, případně? Je to tak? Mám pocit, že právě to vyřešil problém jako před týdnem. Co bylo řešení tohoto problému že Steven narazil? Takže spojové seznamy, vpravo. Pokud je problém, že malujeme sami do rohu přidělování předem příliš málo paměti, že pak se nějak řešit, no, proč ne jen zabránit tomu, aby vydá dohromady? Proč ne jen prohlásit zásobníky se ukazatel na uzel, ergo spojový seznam, a pak jednoduše přidělit nové uzly pokaždé, když Steven třeba, aby se vešly číslo do datové struktury. Takže obraz by měl změnit. To nebude tak čisté a jako jednoduché, jak jen pole tří ints. Teď to bude ukazatel na struct, a to struct se chystá mají int a další ukazatel. Je to povede prostřednictvím tohoto ukazatele jiné takové struct na další takový struct. Takže obrázek by tak ve skutečnosti dostat trochu Messier. A byli bychom šipky vázání všechno dohromady. Ale to je v pořádku, že jo, protože Viděli jsme, jak to udělat. A jakmile se dostanete pohodlně provádí něco jako propojený seznam, který budete muset dělat, když rozhodnete hash tabulku s oddělené zřetězení pro p-set 6, můžete jej použít jako stavební blok, nebo přísada, nebo Scratch mluvit, postup, něco, co dáte, vám vytvořili svůj vlastní kousek skládačky které pak můžete znovu použít. Takže kompromisy, ale možná řešení že jsme vlastně neviděli. Takže docela často, vidíte to každý rok nebo dva, když Apple vydal něco nového, a všichni blázni line up mimo Apple uložit ke koupi jejich marginální přejít na hardware. Říkám to, je to v pořádku, protože Jsem jeden z těch lidí. Takže, jaké datové struktury může představovat tuto skutečnost? No, řekněme, že fronta, linka. Takže Britové to nazval typicky fronta stejně, takže je to hezké jméno. A dvě operace, které fronty musí podporovat budeme volat Zařadí provoz a dequeue provoz, které jsou si podobné duch tlačit a pop. Je to jen trochu liší konvence, co říkáme nich. Ale enqueue něco znamená přidat nebo vložit do datové struktury. Dequeue znamená odstranit. Ale vzhledem k tomu, zásobník byl datový LIFO struktura, fronta je první, První z datové struktury. Pokud jste první člověk v řadě, budete první osoba, která se z řady a koupit si nový přístroj. Představte si, jak naštvaný tito lidé by pokud Apple místo toho používal balík pro instance, k provedení vychystávání do vaší novou hračku. Takže fronty smysl, určitě, a my můžeme myslet na všechny druhy aplikace, pravděpodobně pro front, zvláště když chcete spravedlnost. Takže, jak můžeme realizovat tyto jako datové struktury? Navrhuji, že bychom mohli musíte udělat to takhle. Takže budu teď mít čísla. Takže budeme držet to jednoduchý, a ne nutně mluvit, pokud jde o zásobníků. Jen čísla, která lidé dostali. Kapacita bude opět upevněte Celkový počet osob, které mohou být v tento řádek jako tří nebo bez ohledu na jiná hodnota. Ale navrhuji, že musím sledovat nejen velikostí fronta, kolik věcí v něm. Takže velikost je aktuální velikost, kapacita je maximální velikost. Jen jednou, nomenklatura konvencí. Proč potřebuji další int uvnitř z fronty, jak sledovat, kdo je v přední linie? Proč musím k tomu, že v tomto případě? No, jak se tento obrázek se změní? Mohl bych opětovně využít většinu obrázku. Nech mě jít napřed a vymazat to, co je tady. Dáme to lehce jiné jméno tady. Pojďme se zbavit 17, zbavme na 9, pojďme se zbavit 3. A dodejme ještě jednu věc. Navrhuji, že musím sledovat přední seznamu, který je právě Bude také int. A budeme držet to jednoduchý. Ne spojový seznam nyní. Budeme se přiznat, že budeme Narazí tohoto limitu. Ale co já chci vidět se stalo tentokrát? Tak, že jsem do toho pusťte a první osoba je v souladu, a je to číslo 9.. Máme stres koule. Můžu ukrást, řekněme, dva nebo tři lidi? Jedna, dva, tři? Pojď nahoru. Právo zepředu, protože uděláme tohle rychle. Každý z vás se nyní bude fan kluk ve frontě na Apple. Nebudete dostávat Apple hardware Na konci tohoto ačkoli. Dobrá. Takže ty jsi číslo 9, ty jsi číslo 17, číslo 22. Ty jsou libovolná čísla, jako je Student ID nebo kdoví co ještě. A za chvíli, začněme začít přidávat věci. A já budu běžet desku zde tentokrát. Takže v tomto případě jsem si inicializuje přední být - Vlastně jsem opravdu nestarám, co přední část je, protože velikost je nula. Takže to může být i jen být otazník. To všechno jsou otazníky. Takže teď začneme skutečně vidět některé lidé čekají, až v obchodě. Takže pokud číslo 9, ty jsi první, tam v 5 hodin ráno, jděte do toho a line up, nebo v noci. OK. Takže teď 9 je tady. Takže 9 je v přední části seznamu. Takže budu pokračovat a aktualizovat Velikost tohoto aktuálních dat strukturu, která není už 0, ale na 1. Chystám se dát na 9 Přední seznamu. Nech mě jít dopředu a přepínat obrazovky takže vidíme kolem nás zde. A teď co chci dát na přední straně? Budu sledovat, že přední fronty hned je v místě 0. Protože to, co se bude dít příště? No, předpokládám, teď jsem enqueue 17 také. Tak hop v řadě tam. A opět, typ dveří Obchod se tu bude. Takže teď jsem přidal 17. A i když tihle kluci jsou blokování obrazovka, to je v pořádku, protože vidíme to tady. Promiňte. DIVÁKŮ: Můžeme se pohybovat - DAVID Malan: Ne, to je v pořádku. Je to obrovská tam. Takže 17 je nyní uvnitř fronty. Musím aktualizovat, která Pole teď když? OK, určitě velikosti. A co přední? OK, no. Přední by se nemělo měnit, protože na rozdíl od zásobníku, jsme chcete zachovat spravedlnost. Takže pokud 9 přišel první, chceme 9 , že je první z řady do obchodu. Ve skutečnosti, ať se na to. Než vložíme 22, pojďme jděte do toho a dequeue 9. Jak se jmenujete? Diváků: Jake. DAVID Malan: Jake se děje být dequeued teď. Takže jste si na procházku do obchodu. A předstírat, že obchod je támhle. Takže teď, co je potřeba - dit-dit-dit! Co by se stalo teď? Návrh rozhodnutí. Takže není špatný instinkt, ale - co se to jmenujete? DIVÁKŮ: David. DAVID Malan: David. Takže to, co David udělal? Snažil se nějak opravit údaje struktura a pohyb od jeho umístění v bývalém místě Jake. A to je v pořádku, pokud jsme ochotni přijmout, že jako implementační detail. Ale nejprve pojďme aktualizovat data strukturu, než to děláme. Protože jsem nelíbil nápad všech lidé posun v tomto oboru. Není to velký problém, pokud David dělá s jeden krok, ale opět si vzpomenu na když jsme měli osm dobrovolníků na etapa a udělali jsme jako vložení třídění, kde jsme museli začít pohybující se všichni kolem. To má drahá, že jo? To mě krčit se o velké O n, velký O n na druhou znovu. Není to pocit, ideální výsledek. Takže řekněme, aktualizovat to. Takže velikost fronty není 2. Je to teď prostě jedno. Ale nyní mohu aktualizovat něco Nechtěl jsem aktualizovat dříve, Přední seznamu. Mohl bych říct, je, že místo 1? Takže teď máme odpadky hodnoty zde odpadky hodnota zde a David v Uprostřed tohoto odpadu. Ale struktura dat je stále neporušená. A ve skutečnosti jsem ani potřeba změnit Jake je bývalý číslo 9, protože koho to zajímá. Mám dostatek informací, nyní v velikost, že vím, je tu ještě jedna osoba Tato fronta. A vím, že tato osoba je v místě 1, ne 0. Nepočítám. 1. tak i. Takže datová struktura je ještě OK. No, co se stane dál? Pojďme enqueue - Jak se jmenujete? Diváků: Callen. DAVID Malan: Callen. Pojďme si enqueue Callen a 22 je nyní ve frontě. Takže teď, co se musí změnit, tady? Přední nebude změnit, samozřejmě. Velikost se změní na 2 znovu. A 22 skončí tady, 9 je stále přítomna, ale je to skutečně odpadky hodnota se. Je to jen pozůstatek minulosti Jake. Takže teď, co se stane, když I dequeue Davide? Jedna poslední operace, dequeue David. Mohli bychom se posunout, ale navrhuji, pojďme co nejméně práce, jak je to možné. Teď můj datová struktura jde zpět ve velikosti 2-1. Ale fronty Nyní se 2. Nepotřebuji, aby tato čísla změnit ještě ne, protože jsou jen nesmyslné hodnoty. Ale teď, co se stane? Dejme tomu, že jsem enqueue, 26? Mám pocit, že patřím sem. Takže jsem byl enqueued. Tak nějak jsem sem patřím. A i když to není zcela vážím vizuálně na jevišti, protože máme dostatek prostoru, měl bych nelze tady stojím, proč? DIVÁKŮ: Jsi mimo hrací plochu. DAVID Malan: Správně. Jsem mimo meze. Jsem indexovány za hranice tohoto pole. Měl bych být v jednom z tři možné lokality. Tak, kde je nejpřirozenější jít? Navrhuji, abychom pákové týden jeden trik. Operátor modulo, procento. Protože jsem stál u technicky místo 3, ale mám 3 mod kapacity, takže 3, znak procenta, 3 - Kapacita je 3. Co je to? Co je to zbytek po dělíte 3 od 3? 0. Tak, že mě staví se Jake, což je vlastně dobře. Takže teď provádění z toho, co se děje na být trochu bolí hlava. Je to opravdu jen jeden řádek bolesti hlavy, kódu. Ale aspoň teď je tu odpadky hodnotu, ale je tu to dva legitimní ints zde. A tvrdím, že teď jsme udělali přesně to, co musíme udělat, tak dlouho, dokud změníme to, co Jake hodnota měla být 26. Nyní máme dostatek informací, stále zachování integrity této datové struktury. Jsme stále trochu smůlu, když jsme Chci vložit čtyři nebo více celkem prvky, ale můžu se aspoň pěkně efektivní využití této konstanty čas, ve skutečnosti. Nechci se starat o řazení všichni, protože sklon Davida bylo. Jakékoliv dotazy týkající se komínů nebo to fronta? DIVÁKŮ: Je důvod, proč Potřebujete velikost, takže víte, kde má člověk? DAVID Malan: Přesně tak. Musím znát velikost pole protože musím přesně vědět, jak mnoho z těchto hodnot jsou legitimní, a aby najdu, kam umístit další osoba. Přesně tak. Velikost je - Vlastně jsme neměli aktualizovat to ještě. Přidal jsem sám na 26 let. Velikost je teď, ne jeden, ale dva. Takže teď to opravdu pomáhá mi najít hlava seznamu, který není 0, není 1, ale je 2.. Na přední straně seznamu je opravdu číslo 22. Vzhledem k tomu přišel jako první, a tak by povoleno do obchodu přede mnou, i když vizuálně stojím blíže k obchodu. V pořádku? Potlesk pro tyto lidi a necháme je odtamtud. [APPLAUSE] DAVID Malan: Nemohl jsem nechat budete mít zásobník. Mohli jsme vidět, co se stane, když chcete, ale možná taky ne. Dobrá. Tak co teď co z toho plyne? No, dovolte mi navrhnout, aby tam několik dalších datových struktur bychom mohli začít přidávat do našeho nářadí, které ve skutečnosti je zcela, zcela relevantní jsme se ponořit do věcí webu. Což zase má nějaké spojení na stromy ve formě něco jako DOM, dokument objektový model. Ale uvidíme více že zanedlouho. Dovolte mi navrhnout, z definice, že jsme zavolejte strom teď, co byste mohli vědět, jak více rodokmenu, kde nějaký předek na Kořeny stromu. Patriarchální nebo matriarcha na samém vrcholu stromu. Bez svého manžela, v tomto případě. Ale nyní máme, co budeme nazývat Děti, které jsou uzly, které visí z levé nebo pravé dítě dítě, šipky, jak je znázorněno zde. Jinými slovy, ve stromové struktuře dat v počítači, strom má nulu nebo více uzlů. Pokud má alespoň jeden uzel, tomu se říká kořen. Jsou to věci, které vizuálně čerpáme na vrcholu. A to uzel, jako každý jiný uzel, může mají nulový, jeden, nebo dva, nebo tři, nebo jak mnoho dětí datová struktura podporuje. V tomto případě, kořen, skladování hodnoty jedna, má dvě děti, 2 a 3, takže jsme obvykle vyžadují dva levé Dítě a 3 právo dítě. A pak, když se dostaneme až 5, 6, a 7, 6 by se dalo nazvat prostřední dítě. Pokud máte čtyři děti, to bude matoucí. Tak jsme se přestat používat tento druh o zástupce ústně. Ale je to opravdu jen rodokmen. A listy jsou zde uzlů, které samy o sobě nemají žádné děti. Visí na dno stromu. Takže, jak můžeme realizovat strom, který má jen dvě děti maximálně? Nazveme to binární strom. Bi opět znamená dva, v tomto Stejně tak jako s binární. A tak to může mít nula, jedna, nebo maximálně dvě děti. Já navrhuji, abychom realizovat uzel pro tuto strukturu s int n, a pak dva ukazatele, jeden s názvem vlevo, jeden volal pravdu. Ale to jsou jen pěkné libovolné konvence. A co je hezké teď, zejména pokud druh bojoval s koncepčně rekurze, nebo si myslel, že to není opravdu řešení pro cokoliv, zejména pokud by spustit z paměti. Teď, když mluvíme o datech struktury a algoritmy, které umožňují nás projít a manipulovat s nimi, Ukazuje se, že rekurze je zpět mnohem přesvědčivější není-li krásný způsob. Takže to navrhuji, je implementace z funkce Hledat. Vzhledem k tomu, dva vstupy - tak, že ji jako černá skříňka. Vzhledem k tomu, dva vstupy, n, int a ukazatel na strom, ukazatel na uzel, nebo opravdu kořen stromu, jsem Tvrzení, že tato funkce může vrátit true nebo false, že hodnota n je uvnitř tohoto stromu. Co je uvnitř této černé skříňky? No, čtyři větve. První jen kontroluje. Je-li strom je null, stačí se vrátit false. Pokud není žádný uzel, není n, tam žádné číslo, jen return false. Pokud však, n, hodnota, kterou hledáte pro, je menší než stromu šipky n, a Jen aby bylo jasno, co to znamená, když Píšu strom a pak klepněte na šipku notace, n? Přesně tak. To znamená, že Dereference ukazatel tzv. strom. Jděte tam, a pak se uvnitř, které uzel a získat jeho pole s názvem n. A pak porovnávat skutečné n, který byl přešel do vyhledávacího proti němu. Takže, pokud n je menší než hodnota n v uzlu stromu sám, dobře, co to znamená? To znamená, že nic na první pohled. Je to tak? Stejně jako když máte řadu hodnoty, měli byste chtěli použít binární vyhledávání jako formu předělu a panuj. Ale to, co jsme předpoklad, je třeba, aby pro binární hledání práce vůbec v telefonním seznamu a dříve příklady? Jak mají být tříděny. Takže pojďme upřesnit definici stromu zde nesmí být jen strom, který může mít libovolný počet dětí. Není to jen binární strom, který může jsou 0, 1, 2 nebo maximálně. Ale jako binární vyhledávací strom, nebo BST který je jen ozdobný způsob, jak říkat binární strom, tak, že každý uzel je vlevo dítě, pokud je přítomen, je méně než uzlu. A každý uzel má pravdu dítě pokud je k dispozici, je větší než samotný uzel. Takže jinými slovy, pokud jste k tomu strom se, všechna čísla jsou pečlivě vyvážit, jako je to tak, že pokud Máte 55 jako root, může jít 33 po jeho levé straně, protože to je méně než 55 let. 77 může jít po jeho pravé straně, protože je to více než 55 let. Ale teď nevšiml, stejnou definici, Je to rekurzivní definice ústně, musí požádat o 33. 33 levá dítě musí být menší než to, a 33 na pravé dítě, 44, musí být větší než to. Tak to je strom binárního vyhledávání, a Navrhuji, s použitím trochu rekurze, můžeme nyní najít n. Takže pokud je n menší než hodnotu n, která je aktuální uzel, já jdu dopředu a punt, abych tak řekl, a jen vrátit bez ohledu na odpověď na vyhledávání na n stromu je levá dítě. Všimněte si, opět, tato funkce jen očekává uzlu STAR, ukazatel na uzel. Tak určitě jsem si jen udělat strom Šipka vlevo, což povede Přechod k jinému uzlu. Ale co je to uzel? No, podle tohoto prohlášení, vlevo je jen ukazatel, takže stačí znamená, že jsem kolem na vyhledávací funkce jiný ukazatel, a to který reprezentuje Moje levá dítěte strom. Takže v tomto případě, ukazatel 33, je-li To je náš výběr vstupu Zatím, pokud n je větší než hodnotu n na aktuální uzel ve stromu, pak jsem jít dopředu a pramice v druhé směr a jen říct, vůbec se mi nelíbí vědět, zda je tato hodnota n je ve stromové struktuře ale vím, že pokud je to, že je to po mé právo větev, abych tak řekl. Dovolte mi tedy volání rekurzivně prohledávat, vykonáním n znovu, ale předáním ukazatel na mé pravé dítě. Jinými slovy, když jsem v současné době 55 a hledám pro 99, já vím, že 99 je větší než 55, takže přesně jak jsem roztrhl týdny telefonního seznamu lety a my šel doprava, podobně jako jsme jít tady. A já nevím, jestli je to na mé pravici dítě, a to není, 77 existuje, ale Vím, že je v tomto směru. Takže říkám hledání na pravém dítě, 77, a nechte vyhledávací postavu z existuje-li 99 v tomto libovolná Příkladem je ve skutečnosti tam. Jinak, co je poslední případ? Je-li strom je null jeden případ. Pokud n je menší než je aktuální uzel je hodnota je jiný případ. Pokud n je větší než aktuální uzlu hodnota je třetí případ. Co je čtvrtý a poslední případ? Myslím, že jsme z případů, ne? To tak, že n je aktuální uzel, že jsem na. Takže když jsem hledal 55 v tomto bodě v příběhu, že pobočka strom se vrátí true. Takže to, co je zajímavé, je, že jsme ve skutečnosti, na rozdíl od minulosti týdnů, jsme trochu na dva základní případy. A oni nemají být vše v horní části. Horní je základní případ, protože v případě, že Strom je null, nic dělat. Stačí se vrátit pevný kódované hodnota false. Spodní větev je trochu výchozí, přičemž když jsme zkontrolovat null, jsme zkontrolovat, zda má být vlevo, ale to by nemělo být, máme kontroluje, zda by měl být správně, ale neměly by být zřejmé, že musí být tam, kde jsme. To je základní věc. Takže tam jsou dvě rekurzivní případy obložené tam uprostřed. Ale já jsem mohl napsat to v libovolném pořadí. Jen jsem myslel, že to trochu přišlo přirozené nejprve zkontrolujte, zda případné chyby, pak se podívejte doleva, pak se hned, pak Předpokládám, že jste na uzlu jste vlastně hledáte. Tak proč by to mohlo být užitečné? Tak to dopadá - a dovolte mi přejít na ukázku tady je to na webu. Chystáme se začít používat ne programovací jazyk na první, ale značkovací jazyk. Značkovací jazyk je ten, který je svým duchem podobat programování jazyk, ale to vám nedává schopnost vyjádřit sám sebe logicky. To vám dává možnost vyjádřit sám sebe strukturálně. Kam chceš dát něco na stránce, webová stránka? Jakou barvu chceš, aby se to? Jaké písmo chceš, aby se to? Jaká slova se vlastně Chcete na webové stránce? Takže je to značkovací jazyk. Ale pak jsme si velmi rychle zavádět JavaScript, který je plnohodnotným programovací jazyk. Velmi podobný ve vzhledu syntakticky na C, ale bude to mít nějaký pěkné, silnější, uživatelsky přívětivé funkce. A jeden z frustrace na to bod v semestru, je, že budeme brzy realizovat pravopisu v daleko méně řádků kódu pomocí jiné jazyky než C sám umožňuje, ale z důvodu je Brzy budeme rozumět. Bude to první taková webová stránka. To bude zcela nezaujatý, První děláme. To se jednoduše říci, hello world. Ale pokud jste nikdy neviděli před, to je HTML, HyperText Markup Language. Pokud půjdete do určité menu v téměř jakýkoli prohlížeč na jakékoliv webové stránky, na internet, můžete vidět HTML že někteří lidé psali vytvořit tuto webovou stránku. A to asi nevypadá jako krátký nebo čistý, protože to. Ale bude následovat vzor z nich otevřené závorky a lomítka a písmena a potenciálně čísla. Myslel jsem, že vám ukázku z toho, co budete moci dělat po užití CS50. Nech mě jít do cs.harvard.edu / rob, naší vlastní Roba Bowdenovo domovskou stránku. Udělal to pro nás. Takže budete brzy moci udělat. A také to, co jste slyšeli dnes ráno - to, co jsi slyšel dnes ráno - [HAMSTER DANCE MUSIC] - Budeš mít možnost, aby se to. To nás čeká ve středu. Uvidíme se potom. [HAMSTER DANCE MUSIC] DAVID Malan: Na další CS50 -