>> 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.
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 -