[Přehrávání hudby] DAVID Malan: To je CS50. A to je jak začátek a end-- jako literally-- téměř do konce týdne šest. 

Myslel jsem, že bych sdílet trochu zábavné skutečnosti. Jsem vytáhl to až z nastavit údaje minulého semestru. Možná si vzpomenete, že jsme se vás zeptat na každém p set formulář, pokud jste sledovali on-line nebo pokud jste se zúčastnili osobně. A tady je v datech. Takže dnes byl velmi předvídatelný. Ale my jsme chtěli strávit trochu času s vámi nicméně. Chtěl by někdo dohadu, proč se to graf je tak Jaggy, nahoru dolů, nahoru dolů, tak důsledně? Co každý z vrcholů a žlaby představují? 

Diváků: [neslyšitelné] DAVID Malan: Opravdu. A více zábavně, nedej bože, máme jednu přednášku v pátek na začátku semestru, že to, co vidíme, se stalo. Takže dnes jsme se zapojit do trochu Další informace o datových strukturách. A dát vám více pevné látky mentální model pro problémy, které v pěti, který je nyní ven. Pravopisné chyby, kde budeme předat vám textový soubor někteří 100.000 a anglická slova, a budete mít přijít na to, jak chytře je načíst do paměti, do paměti RAM, pomocí některé údaje Struktura vašeho výběru. 

Právě jedna taková datová struktura by mohla být, ale pravděpodobně by neměla být, poměrně zjednodušující spojový seznam, které jsme uvedli minule. A spojový seznam měl alespoň jedna výhoda oproti matici. Co je jedna z výhod spojový seznam pravděpodobně? 

Diváků: Vložení. 

DAVID Malan: Vložení. Co tím myslíš? 

Diváků: Anywhere spolu seznam [neslyšitelné]. 

DAVID Malan: Dobrý. Takže můžete vložit prvek, kdekoli Chcete uprostřed seznamu aniž by museli zamíchat cokoliv, které jsme uzavřeli v našem třídění diskuse, není nutně dobrá věc, protože to vyžaduje určitý čas, aby skutečně pohybovat všechny ty lidi vlevo nebo vpravo. A tak se spojový seznam, můžete jen přidělit s malloc, nový uzel, a pak aktualizovat pár pointers-- dva, tři operace max-- a jsme schopni slot někoho kdekoliv do seznamu. 

Co jiného bylo výhodné o propojeném seznamu? Jo? 

Diváků: [neslyšitelné] DAVID Malan: Perfect. Perfect. Je to opravdu dynamický. A že nejste spáchání, předem, do určité pevné velikosti kus paměti, jako byste mít se s pole, proinflační které je, že můžete přidělovat uzly pouze na poptávka a tím používat pouze tolik místa jak skutečně potřebujete. Na rozdíl od pole, můžete náhodně rozdělit příliš málo. A pak je to jen bude být bolest v krku přerozdělit nové větší pole, zkopírujte všechno skončí, uvolnit staré pole, a pak se přesunout o vaší firmě. Nebo ještě hůře, můžete přidělit cestu více paměti, než skutečně potřebujete, a tak budete mít velmi řídce osídlené pole, abych tak řekl. 

Takže spojový seznam vám tyto Výhody dynamiky a flexibility s inzercí a delecí. Ale určitě tam musí být zaplacená cena. Ve skutečnosti, jedním z témat prozkoumat testu nulové byl pár z kompromisů jsme viděli doposud. Takže to, co je cena, kterou zaplatil nebo Nevýhodou propojeného seznamu? Jo. 

Diváků: Ne náhodný přístup. 

DAVID Malan: No náhodný přístup. Ale koho to zajímá? Náhodný přístup nezní přesvědčivé. 

Diváků: [neslyšitelné] DAVID Malan: Přesně tak. Chcete-li mít určité algorithm-- a dovolte mi, abych ve skutečnosti navrhnout binární vyhledávání, zejména, což je ta, kterou jsme použili docela bit-- pokud nemáte náhodný přístup, můžete to udělat jednoduchou aritmetiku nalezení jako prostřední prvek a skákání na něj právo. Místo toho budete muset začít v první element a lineárně vyhledávání zleva doprava, chcete-li najít střední nebo jakýkoli jiný prvek. 

Diváků: Asi potřebuje více paměti. 

DAVID Malan: bere více paměti. Kde je ten další náklady přicházející z paměti? 

Diváků: [neslyšitelné] DAVID Malan: Přesně tak. V tomto případě je zde, měli jsme spojový seznam pro celá čísla, a přesto jsme zdvojnásobení množství paměti musíme tím, že také uložení těchto ukazatelů. Nyní méně velký problém, jak Vaše structs se zvětší a vy jste ukládání není číslo, ale Možná student nebo nějaký jiný předmět. Ale jde samozřejmě zůstává. A tak počet operací na spojových seznamů byli povoláni Byly velké-O n- lineární. Věci jako vložení nebo hledání nebo delece v případě, že prvek se stalo, že na samém konci Seznam ať už je to tříděného či nikoliv. 

Někdy můžete mít štěstí a takže spodní meze těchto operací může být také konstantní čas, pokud jste vždy při pohledu na první prvek, například. Ale nakonec jsme slíbili k dosažení svatý grál datových struktur, nebo některé aproximace této smlouvy, prostřednictvím konstantním čase. Můžeme najít prvky, nebo přidat prvky nebo odebrání prvků ze seznamu? Uvidíme již brzy. A ukázalo se, že jeden mechanismů jsme začnou používat dnes, roční spotřeba v p nastavit pět, je vlastně docela známé. Například, pokud je to banda zkoušky knih, z nichž každý má student je první Jméno a příjmení na tom, a já jsem vyzvednout z jejich na konci zkoušky, a všichni jsou dost hodně v náhodném pořadí, a chceme jít o třídění Tyto zkoušky tak, že jakmile se stupněm je to prostě mnohem jednodušší a rychleji předat je zpátky studentům abecedy. Co by vaše instinkty se na hromadu zkoušek, jako je tento? 

No, pokud jste jako já, může vidět, že se jedná m, tak budu nějak dát to do, pokud je to můj stůl nebo můj patra, kde Jsem šíří věci out-- nebo moje pole really-- Mohl bych dát všechny Ms tam. Oh. Zde je A. Takže bych mohl dát jako tady. Oh. Zde je další A. jdu dát to sem. Zde je Z. Zde je další M. A tak Mohl bych začít dělat piloty, jako je tento. A pak možná bych jít později a druh velmi nitpicky-ly sort jednotlivé piloty. Ale jde o to bych se na vstupu, že jsem rukou a já bych se některé vypočítá rozhodnutí založené na tomto vstupu. Pokud se začíná, dát to tam. Pokud se začne s Z, dal ji tam, a všechno mezi tím. 

Takže to je technika, která je všeobecně známé jako hashing-- H-A-S-H- což obecně znamená, že jako vstup a pomocí tohoto vstupu pro výpočet hodnotu, obvykle číslo, a že číslo je index do skladu Nádoba, jako pole. Takže jinými slovy, mohl bych mít hash funkce, jako já v mé hlavě, že když vidím někoho to Název, který začíná, Chystám se mapa, která na nulu v mé hlavě. A když vidím někoho s Z, jsem bude mapovat, že až 25 v mé hlavě a pak to dát do poslední nejvíce hromada. 

Teď, když se nad tím zamyslíte není můj mozek ale program v jazyce C, která čísla by mohla se spolehnout na dosažení tohoto stejného výsledku? Jinými slovy, pokud máte měl ASCII znak A, Jak zjistíte, co kbelík, aby to v? Pravděpodobně nebudete chtít dát do kbelíku 65, který by bylo jako tam bez dobrého důvodu. Kde chcete dát pokud jde o jeho ASCII hodnota? Kam chceš udělat, aby jeho ASCII hodnota přijít s chytřejší kbelíku aby ji v? 

Diváků: Minus A. 

DAVID Malan: Jo. Takže minus nebo minus konkrétně 65, pokud je to kapitál A. Nebo 98, pokud je to malé. A tak, že by nám umožňují velmi jednoduše a velmi aritmeticky, dát něco do kbelíku takhle. Tak to dopadá, že jsme vlastně dělat to stejně is kvízy. 

Takže si možná pamatujete si kroužil vaše Název Výuka Kolegové se na obálce. A byly organizovány jména TF se do těchto sloupců podle abecedy, No, věřte tomu nebo ne, když všichni 80 a nás se dali dohromady v noci do platové třídy, poslední krok v našem procesu třídění, je hash kvízy do velké prostor podlahy na [neslyšitelné] a položit kvízy Každý by přesně pořadí jejich TF let jména na obálce, protože pak je to mnohem jednodušší pro nás prohledávat že pomocí lineární vyhledávání nebo nějaký chytrosti pro TF najít jeho nebo kvízy svých studentů. 

Takže tato myšlenka z hash které uvidíte, je docela silný je vlastně docela samozřejmostí a velmi intuitivní, podobně jako třeba rozdělit a dobytí bylo v týdnu nula. I rychle vpřed na Hackathon před pár lety. To byl Zamyla a pár Ostatní zaměstnanci pozdrav studenti jak přišli. A měli jsme spoustu skládání Stoly s jmenovkami. A my jsme měli jmenovky organizované se jako jak přes tu a Zs tam. A tak jedním z TFS velmi šikovně psal to jako návod na den. A v 12. týdnu semestru tohoto vše dávalo smysl a všechny věděl, co má dělat. Ale kdykoliv jsem frontě stejným způsobem, budete se provádí Stejný pojem hash. Takže pojďme formalizovat to trochu. Zde je pole. Je vypracován, aby se trochu široký jen líčit, vizuálně, že bychom mohli dát řetězce v něčem, jako je tohle. A toto pole je zjevně velikost 26 celkem. A věc se nazývá Tabulka libovolně. Ale to je jen umělce ztvárnění o tom, co by mohlo být hash tabulky. 

Takže hash tabulka nyní se chystá být vyšší strukturu dat na úrovni. Konec konců chystáme vidět, že vás mohou implementovat hash tabulku, která je podobně jako check-v souladu na Hackathon podobně jako tento Tabulka slouží k třídění zkoušku knih. Ale hash tabulka druh této vysoké úrovni koncept, který by mohl použít pole pod kryt k jeho provedení, nebo použít seznam délky, nebo dokonce možná některé další datové struktury. A teď to theme-- převzetí některé z těchto základních složek jako pole a budovy Blokovat nyní ze seznamu délky a vidět, co ještě můžeme stavět nad ty, jako přísady na recept, takže stále více a více zajímavé a užitečné konečné výsledky. 

Tak s hash tabulky můžeme ho zavést v paměti obrazově takhle, ale jak by to vlastně být kódovány up? No, možná, protože prostě je to. Pokud KAPACITA ve všech velkých písmenech, je jen někteří constant-- například 26, 26 písmen alphabet-- Mohl bych zavolat své variabilní stůl, a mohl bych tvrdit, že budu dát char hvězdy tam, nebo řetězec. Takže je to tak jednoduché, jak to, pokud chtějí zavést hash tabulky. A přesto, je to opravdu jen pole. Ale opět, hash Tabulka je nyní, co budeme zavolejte abstraktní datový typ, který je stejně druh koncepčního vrstvení na vrcholu něco více světského Nyní mi pole. 

A teď, jak máme jít o řešení problémů? No, dříve jsem měl luxus mít dostatek tabulkový prostor zde tak, že bych mohl dát kvízy nikde jsem chtěl. Tak, aby mohla jít sem. Zs může jít sem. Paní může jít sem. A pak jsem měl nějaké extra prostor. Ale to je trochu cheat práva teď, protože této tabulce, jestli jsem opravdu myslel na to jako pole, je jen bude nějaké pevné velikosti. 

Takže technicky, když jsem vytáhnout do jiného studenta kvíz a vidět, oh, tato osoba je Název začíná příliš, Tak nějak jsem chtěl dát to tam. Ale jakmile jsem to tam dal, je-li tato tabulka skutečně představuje pole, Chystám se být převažující nebo přepisování kdo tento student kvíz je. Je to tak? Pokud se jedná o pole, jen jedna věc může jít v každé z těchto buněk nebo prvků. A tak nějak jsem se vybrat a zvolit. 

Teď dříve jsem tak trochu podváděl a dělal to nebo I jen tak na sebe je nad sebou. Ale to nebude létat v kódu. Tak, kde jsem mohl dát Druhý student, jehož jméno Je-li vše, co jsem měl, je to k dispozici tabulkový prostor? A já jsem použil tři sloty a to vypadá to, že je to jen několik dalších. Co jsi to mohl udělat? Diváků: [neslyšitelné] DAVID Malan: Jo. Možná, řekněme, aby to jednoduché. Je to tak? To se nehodí tam, kde chci, aby to. Takže jdu dát technicky kde by B jít. Teď, samozřejmě, já začínám malovat sám sebe do kouta. Pokud se dostanu na studenta jehož jméno je vlastně B, Nyní B bude pohybovat trochu dopředu, jak by se mohlo stát, jo, pokud je to B, teď to musí jít sem. 

A tak se velmi rychle by se mohlo stát problematickým, ale je to technika, která ve skutečnosti je označován jako lineární snímání, kdy stačí zvážit své pole, že podél čáry. A právě typ čidla, nebo zkontrolujte každou dostupné prvek hledá k dispozici na místě. A jakmile zjistíte, jedno, co si jen kapka tam. 

Nyní je cena v dnešní době věnováno pro toto řešení je to, co? Máme pevnou velikost pole, a při vložení jména do něj, alespoň zpočátku, co je doba chodu vložení pro uvedení studentů " kvízy na správných kbelíky? Big O co? 

Diváků: n. DAVID Malan: Slyšel jsem, že velký O n. To není pravda. Ale budeme dráždit sebe proč za chvíli. Co jiného by to mohlo být? 

Diváků: [neslyšitelné] DAVID Malan: A dovolte mi, abych to vizuálně. Takže předpokládám, že je to písmeno S. 

Diváků: Je to jedna. DAVID Malan: Je to jedno. Je to tak? To je pole, které znamená, že máme náhodný přístup. A pokud si myslíme, že to na nulu a to až 25, a my jsme si uvědomili, že, oh, tady je můj vstup S, Já určitě převést S, znak ASCII, do odpovídajícího počtu mezi nulou a 25 a pak se okamžitě dát tam, kam patří. 

Ale samozřejmě, jakmile se dostanu do Druhá osoba, která se jmenuje A nebo B nebo C nakonec, pokud jsem použil lineární snímání jak mé řešení, Doba chodu vložení v nejhorším případě bude skutečně přenést do čeho? A já jsem slyšel zde správně brzy. Diváků: [neslyšitelné] DAVID Malan: Tak to je opravdu n jednou máte dostatečně velký soubor dat. Tak, na jedné straně, pokud vaše pole je dostatečně velký a vaše data je řídké dost, vy si tento krásný konstantní čas. Ale jakmile začnete stále více a více prvků, a jen statisticky dostanete více lidí s písmenem Jak jejich jméno nebo písmeno B, mohlo by to potenciálně přejít na něco více lineární. Takže není úplně dokonalá. Tak bychom mohli dělat lépe? 

No, co bylo naše řešení, než když jsme se Chcete mít větší dynamiku než něco jako pole dovoleno? Diváků: [neslyšitelné] DAVID Malan: Co jsme představit? Jo. Takže spojový seznam. No, uvidíme, co souvisí Seznam může udělat pro nás místo. No, dovolte mi, abych navrhuji, abychom nakreslit obrázek takto. Nyní je to jiná obrázek z příkladu z jiného textu, ve skutečnosti, že je ve skutečnosti pomocí pole o velikosti 31. A to autor prostě rozhodl hash řetězce nejsou založeny na jména této osoby, ale na základě jejich narozeniny. Bez ohledu na měsíce, ale přišel pokud jste se narodil na první měsíc nebo 31. v měsíci, autor hash bude na základě této hodnoty, tak, aby se rozšířila jména se trochu více než jen 26 míst, by mohly umožnit. A možná je to trochu jednotnější než jít s písmeny abecedy, protože samozřejmě je to asi více lidí na celém světě se jmény které začínají než jistě některé další písmena abecedy. Takže možná je to trochu jednotnější, za předpokladu, že rovnoměrné rozložení kojenců po celé měsíce. 

Ale, samozřejmě, je to stále nedokonalé. Je to tak? Budeme mít kolize. Více lidí v této datové struktury jsou stále mají stejný datum narození nejméně jste bez ohledu na měsíc. Ale co se autor udělal? No, vypadá to, že máme celou řadu na levé straně tažené vertikálně, ale to je jen umělce ztvárnění. Nezáleží na tom, jakým směrem se vás čerpat řadu, je to ještě pole. Co je to pole zdánlivě? 

Diváků: spojový seznam. 

DAVID Malan: Jo. Vypadá to, jako by to pole propojeného seznamu. Takže znovu, do tohoto bodu druhu použití těchto datových struktur nyní jako přísady do více zajímavé řešení, můžete mít naprosto Základní, stejně jako pole, a pak něco víc zajímavé jako spojový seznam a dokonce spojit je do ještě zajímavější datové struktury. A skutečně, taky by to se nazývá hash tabulky, přičemž pole je opravdu hash tabulka, ale to hash tabulka řetězy, abych tak řekl, že může růst nebo zmenšit na základě počet prvků, který chcete vložit. 

Nyní tedy, co je doba chodu teď? Pokud chci vložit někoho jehož narozeniny 31. října, kde se on nebo ona jít? Dobrá. Na samém dně, kde se říká, že 31. A to je perfektní. To bylo konstantní čas. Ale co když najdeme někoho jiného jehož narozeniny, pojďme se podívat, Říjen, listopad k 31? Pokud se on nebo ona jít? Totéž. Dvoustupňová ačkoli. To je konstantní i když je to tak? Dobrá. V současné době to je. Ale v obecném případě, čím více lidí přidáme, pravděpodobnostně, jdeme aby se více a více ke kolizím. 

Teď je to trochu lepší, protože technicky teď moje řetězy mohou být v v nejhorším případě, jak dlouho? Mám-li vložit n lidi do toho více sofistikované datové struktury, n lidí, V nejhorším případě to bude n. Proč? 

Diváků: Protože kdyby každý má narozeniny ve stejný den, že budeš jeden řádek. DAVID Malan: Perfect. To by mohlo být trochu nepřirozený, ale skutečně v nejhorším případě, pokud každý má narozeniny ve stejný den, s ohledem na vstupy máte, budete mít masivně dlouhým řetězcem. A ano, můžete ho hovoru hash tabulky, ale ve skutečnosti je to jen masivní spojový seznam s spousta nevyužitého místa. Ale obecně, pokud budeme předpokládat, že alespoň narozeniny jsou uniform-- a to asi není. Dělám, že až. Ale pokud budeme předpokládat, pro Z důvodu diskuse že jsou, pak teoreticky, pokud To je vertikální reprezentace matice, no a pak doufejme, že jste dostane řetězců, které jsou, jak víte, zhruba stejnou délku, kde každý z to představuje den v měsíci. 

Nyní, když je tam 31 dnů v měsíci, to znamená, že moje doba chodu opravdu je velký O n více než 31, což cítí lépe než lineární. Ale to, co byl jeden z našich Závazky pár týdnů Před když to přišlo k vyjadřování doba chodu algoritmu? Stačí jen podívat na vysokou objednávky termínu. Je to tak? 31 je určitě užitečné. Ale je to stále velký O n. Ale jedním z témat o problém nastavit pět bude na na vědomí, že absolutně, asymptoticky, teoreticky Tato datová struktura není o nic lepší, než jen jeden masivní spojový seznam. A skutečně, v nejhorším případě to hash tabulka může přejít do toho. 

Ale v reálném světě, s námi lidé že vlastní Macintoshe nebo PC, nebo cokoliv a běží v reálném světě software z reálných dat, které algoritmus budete preferovat? Ten, který má koncové kroky nebo ten, který trvá n děleno 31 stupňů najít nějakou část dat nebo vyhledat nějaké informace? Myslím, že absolutně 31 značek rozdíl v reálném světě. To je 31 krát rychlejší. A my lidé jsou jistě jít si uvědomit, že. 

Takže si uvědomit rozpor tam mezi skutečně mluví o tom, co teoreticky a asymptoticky, které rozhodně má hodnotu, jak jsme viděli, ale v reálném světě, pokud vám záleží jen dělat člověk šťastný pro obecné vstupy, můžete velmi dobře chcete přijmout skutečnost, že ano, je to lineární, ale to je 31 krát rychlejší než může být lineární. A ještě lépe, nebudeme muset něco libovolného jako datum narození, bychom mohli strávit trochu více času a chytrost a přemýšlet o tom, co bychom mohli udělat, křestní jméno člověka, a možná Jejich datum narození kombinovat ty, složky na něco vymyslíme je to opravdu více jednotná a méně Jaggy, abych tak řekl, než tento obrázek V současné době naznačuje, že by mohlo být. Jak bychom mohli realizovat to v kódu? No, dovolte mi, abych navrhuji, abychom jen půjčit nějaké syntaxi jsme použitý párkrát tak daleko. A já budu definovat uzel, který opět je obecný termín pro jen některé Kontejner pro některé datové struktury. Chystám se navrhnout, aby řetězec se děje tam. Ale budeme začnete těch koleček off teď. 

Žádné další CS50 knihovna Opravdu, pokud budete chtít jej použít pro finále Projekt, který je v pořádku, ale teď budeme táhnout zpět záclony a říkají, že je to jen znak hvězda. Takže slovo se bude jméno osoby v otázce. A teď mám odkaz zde k dalšímu uzlu tak, že tyto představují Každý z uzlů v řetězci, případně, propojeného seznamu. 

A teď jak se Prohlašuji hash tabulka sám? Jak mohu prohlásit celou tuto strukturu? No, opravdu, stejně jako jsem použila ukazatel se pouze první prvek seznamu předtím, podobně mohu jen říci, Prostě potřebuju spoustu ukazatelů realizovat celý tento hash tabulky. Budu mít celou řadu volal tabulka hash tabulky. Bude to mít velikost kapacity. To je to, kolik prvků se vejde do něj. A každý z těchto prvků v tomto pole bude uzel hvězda. Proč? No, na obrázku je to, co jsem provádění hash tabulku jako účinně na začátku je jen Toto pole, které jsme vypracován ve svislém směru, každý z jehož náměstí představuje ukazatel. Že ty, které mají lomítka mezi nimi jsou jen null. A ty, které mají šipky jdou doprava jsou skutečné ukazatele na skutečných uzlů, ergo začátek spojového seznamu. 

Tak tady tedy je, jak bychom mohli realizovat hash tabulku, která implementuje samostatný řetězení. Nyní můžeme dělat lépe? V pořádku jsem slíbil minule, že bychom mohli dosáhnout konstantní čas. A nějak jsem ti dal konstantní čas tady, ale pak řekl, že opravdu konstantní čas, protože je to stále v závislosti na celkové počet prvků jste vklad do datová struktura. Ale předpokládejme, že jsme to udělali. Dovolte mi, abych se vrátit na obrazovku sem. Dovolte mi, abych také promítat to tady, jasné, obrazovky, a předpokládám, že jsem to udělal. Dejme tomu, že jsem chtěl vložit jméno Daven v do mé datové struktury. 

Tak jsem chtěl vložit řetězec Daven do datové struktury. Co když nemám používat hash tabulky, ale já používám něco, co je víc stromová jako rodokmen, kde máte nějaké kořeny na Horní a pak uzly a listy které jdou dolů a ven. Předpokládejme tedy, že já chcete vložit Daven je na to, co je v současné době prázdný seznam. Chystám se provést následující kroky: Já jsem bude vytvářet uzel v této rodině stromová datová struktura, která vypadá trochu jako je tento, z nichž každý obdélníky se, řekněme, Pro tuto chvíli 26 prvků v něm. A každý z buněk V tomto poli se děje reprezentovat písmeno abecedy. 

Konkrétně se budu léčit to je, pak B, pak C, pak D, tohle tady. Takže to bude účinně představují písmeno D. Ale vložit všechny Daven je jméno musím udělat trochu víc. Takže jsem poprvé bude hash, abych tak řekl. Jdu se podívat na první písmeno v Daven je, což je zřejmě D, a budu přidělit uzel, který vypadá jako tohle-- velký obdélník velký tak, aby se vešly na celou abecedu. 

Nyní D je hotovo. Nyní A. D-A-E-V-N je cíl. Takže co teď budu dělat, je to. Jakmile jsem začal D oznámení Je tam žádný ukazatel. Je to nesmyslné hodnoty v okamžiku, nebo bych mohl inicializovat na hodnotu null. Ale dovolte mi, abych dál s Tato myšlenka vybudování stromu. Dovolte mi, abych přidělit další z nich uzly, které má 26 prvků v ní. 

A víte co? Pokud je to jen uzel v paměti, že Vytvořil jsem s malloc pomocí struct jak brzy uvidíte, Chystám se dělat tohle-- Budu čerpat šipku z to, co reprezentoval D dolů do tohoto nového uzlu. A nyní, nejprve další písmeno Daven jménem, V- D-A-V- Chystám se jít dopředu a čerpat další uzel takhle, přičemž jsou zde prvky V, které budeme čerpat pro instance-- Ups. Nebudeme tam kreslit. Bude to naleznete zde. 

Pak jedeme do Považujeme to za V. A pak tady budeme indexu dolů z V na to, co budeme považovat E. A pak zde budeme jít jeden z těchto uzlů zde. A teď tu máme otázku odpovědět. Musím nějak vyplývá, že jsme na konci řetězce Daven. Takže jsem mohl jen nechat null. 

Ale co když máme Daven je celé jméno také, což je, jak jsme řekli, Davenport? Takže co když je Daven vlastně podřetězec, prefix mnohem delší řetězec? Nemůžeme jen trvale říkají, nic se děje tam jít, protože jsme mohli Nikdy nevkládejte slovo jako Davenport do této datové struktury 

Takže to, co bychom mohli udělat, místo toho je zacházet s každým z těchto prvků jako možná mít dva prvky uvnitř nich. Jedním z nich je ukazatel, opravdu, jak jsem dělal. Takže každá z těchto krabic není jen jedna buňka. Ale co v případě, že horní one-- spodní něčí bude nulový, protože není Davenport ještě ne. Co v případě, že jeden vrchol je nějaký zvláštní hodnota? A to bude trochu obtížné stanovit, že tato velikost. Ale předpokládám, že je to jen značka zaškrtnutí. Podívejte se. D-E-V-N-je řetězec V této datové struktury. 

Mezitím, kdybych měl více prostoru tady jsem mohl dělat P-O-R-T, a já jsem mohl dát šek v uzlu který má na písmeno T na samém konci. Tak tohle je masivně komplexní vypadající strukturu dat. A můj rukopis rozhodně nepomůže. Ale když jsem chtěl vložit něco jiný, zvažte, co budeme dělat. Pokud bychom chtěli, aby Davida, bychom následovat stejnou logiku, D-A-V, ale teď bych upozornit na další prvek, který z E, ale od I do D. Takže tam to bude více uzly tohoto stromu. Budeme mít volání malloc více. Ale já nechci, aby se naprostý zmatek obrázku. Takže pojďme se podívat na místo jednoho která byla předem formulována takhle se není tečka, tečka, tečky, ale jen zkráceně pole. Avšak každý z uzlů v tomto zde stromu nahoru představuje stejný thing-- pole Ray velikosti 26. 

Nebo chceme-li být opravdu správné teď, co pokud někdo název, apostrof, pojďme Předpokládejme, že každý uzel má ve skutečnosti jako 27 indexy v něm, ne jen 26 let. Tak to teď bude dat Struktura nazývá trie-- T-R-I-E. Trie, která je údajně historicky chytrý název pro dřevo , který je optimalizován pro vyhledávání, což samozřejmě, se píše s I-E, takže je to trie. Ale to je historie trie. 

Takže trie je to stromová údaje struktura jako rodinný strom že nakonec se chová takhle. A tady je jen dalším příkladem toho, celá parta jmen jiných lidí. Ale otázka nyní na dosah ruky je to, co mají jsme získali zavedením pravděpodobně více složitá struktura dat, a jeden, upřímně, že používá hodně paměti. 

Vzhledem k tomu, i když, v tuto chvíli, já jsem jen pomocí D je ukazatel a A V a Es a Ns, Jsem plýtvání sakra hodně paměti. Ale tam, kde jsem strávil jeden zdroj, Mám ve zvyku se získat zpět další. Takže když jsem trávit více prostoru, co je asi naděje? Že jsem strávil méně co? Diváků: Méně času. DAVID Malan: Čas. A proč by to mohlo být? No, a co je vložení čas, pokud jde o velký O nyní, jména, jako je Daven nebo Davenport nebo David? No, Daven byl pět kroků. Davenport by devět kroků, tak to by bylo ještě několik kroků. David by byl pět kroků stejně. To jsou konkrétní čísla, ale jistě je tu horní mez Délka něčí jméno. A skutečně, v problému sady pěti specifikace, budeme navrhovat že je to něco, to je 40-některé-liché znaky. 

Realisticky, nikdo nemá nekonečně dlouhý název, což znamená, že délka jméno nebo délka řetězce bychom mohli mají určitý stav Struktura je pravděpodobně to, co? Je to konstantní. Je to tak? Mohlo by to být velký jako konstantní 40-něco, ale to je konstantní. A to nemá závislosti na tom, kolik Ostatní názvy v této datové struktuře. Jinými slovy, když jsem chtěl nyní vložit Colton nebo Gabriel nebo Rob nebo Zamyla nebo Alison nebo Belinda nebo jiné názvy z řad zaměstnanců do těchto údajů struktura, je doba chodu vložení další jména bude vůbec ovlivněny podle toho, jak mnoho dalších prvků, jsou v datové struktuře již? To ne. Je to tak? Vzhledem k tomu, že jsme efektivně používat Tento multi-layer hash tabulky. A běží čas některé z těchto operací nezávisí na počtu prvky, které jsou v datové struktuře nebo že se nakonec bude být v datové struktuře, ale na délce co konkrétně? 

Řetězec je vložena, který přece dělá tento asymptoticky konstantní time-- velký O jedné. A upřímně řečeno, právě v reálném světě, to znamená vložení Daven jméno se jako pěti krocích, nebo Davenport devět kroky, nebo David pět kroků. To je zatraceně malá provozní doby. A opravdu, je to velmi dobrá věc, zvláště když to není závislé na celkové počet prvků v tam. Tak jak můžeme realizovat tento druh struktury v kódu? Je to trochu víc složité, ale přesto je to jen aplikace základní stavební kameny. Chystám se znovu definovat nás uzel takto: bool volal word--, a to by se dalo nazvat cokoliv. Ale bool představuje to, co jsem nakreslil jako zaškrtnutí. Ano. To je konec řetězce V této datové struktury. 

A samozřejmě, uzel hvězda se odkazuje na děti. A opravdu, stejně jako rodokmen, budete by zvážit uzly které visí dna některých rodiče element být děti. A tak se děti se chystá být pole 27, 27. jedna být jen pro apostrof. Budeme třídit o zvláštní případ, že. Takže můžete mít jisté jména s apostrofy. Možná i pomlčkou musí tam jít, ale budete viz str sadě 5 my jen péče o dopisů a apostrofy. 

A pak jak si představují datová struktura sama o sobě? Jak si představují kořen tohoto trie, abych tak řekl? No, stejně jako s propojeného seznamu, vždy jej potřebují ukazatel na první prvek. S trie stačí jeden ukazatel na kořen tohoto trie. A odtud můžete hash vaše cesta dolů hlouběji a hlouběji pro každý uzel ve struktuře. Tak jednoduše se to může představujeme, že struct. 

Nyní Meanwhile-- Oh, otázku. 

Diváků: Co je bool slovo? 

DAVID Malan: BOOL slovo právě tato inkarnace C z toho, co jsem popsal V tomto boxu tady, když Začal jsem rozdělení každého z prvky pole do dvou částí. Jedním z nich je ukazatel na další uzel. Jiný musí být něco jako zaškrtávací políčko říct, že ano, je tu Slovo Daven, že zde končí, protože nechceme, v okamžiku, Dave. 

I když Dave bude legitimní slovo, že to není v trie ještě. A D není ani slovo. A D-není slovo nebo jméno. Takže zaškrtnutí označuje pouze jednou vás hit tento uzel předchozí cesta znaků vlastně řetězec, který jste vložili. Tak to je vše bool tam dělá pro nás. 

Jakékoliv další dotazy týkající se pokusů? Jo. 

Diváků: Co je přesah? Co když máte Dave a Daven? DAVID Malan: Perfect. Co když máte Dave a Daven? Pokud tedy vložíte, řekněme přezdívku, pro David-- Dave-- D-A-V-E? To je vlastně super jednoduché. Takže jsme jen bude trvat čtyři kroky. D-A-V-E. A co mám dělat, až jsem narazila, že čtvrtý uzel? Jen tak pro kontrolu. Už jsme dobré jít. Hotovo. Čtyři kroky. Konstantní čas asymptoticky. A teď jsme ukázaly, že oba Dave a Daven jsou řetězce ve struktuře. Takže není problém. A všimněte si, jak přítomnost z Daven to nezvládli mít více času, nebo méně čas pro Dave a naopak. 

Takže co jiného můžeme nyní dělat? Použili jsme tuto metaforu před zásobníků představuje něco. Ale ukazuje se, že sloupec podložek je vlastně demonstrativní jiného abstraktní údajů type-- vyšší datovou strukturu úrovně že na konci dne je jen jako pole nebo spojového seznamu nebo něco prozaičtější. Ale je to mnohem zajímavější koncepční pojetí. Stack, jako jsou tyto žlaby tady v Mather, se obecně nazývají jen that-- stoh. 

A v tomto typu datové struktury Máte dvě operations-- máte jednu s názvem Push pro přidat něco do zásobníku, jako dávat jiný zásobník Zpět na vrchol zásobníku. A pak pop, který vás znamená vzít nejvrchnější zásobníku off. Ale to, co je klíčem k stack je, že to dostal tuto kuriózní vlastnost. Jako zaměstnanci jídelny jsou přeskupit zásobníky na další jídlo, co se bude pravda o tom, jak studenti interagují s touto datovou strukturou? Diváků: Chystají se pop jednorázové. DAVID Malan: Chystají se pop jednorázové, doufejme, že na vrchol. V opačném případě je to jen trochu hloupý jít celou cestu až na dno. Je to tak? Datová struktura není ve skutečnosti umožňuje uchopit spodní zásobník alespoň snadno. Takže tam je to zvědavý vlastnost stohu že poslední položka je bude první ven. A počítačoví odborníci říkají tento LIFO-- poslední dovnitř, první ven. A to ve skutečnosti nemá mít zajímavé aplikace. To není nutně tak zřejmé, jak někteří jiní, ale může skutečně být užitečné, a může skutečně být provedena v několika různými způsoby. 

Takže člověk, a ve skutečnosti, ať mě ne se ponořit do toho. Jdeme na to místo. Pojďme se podívat na ten, který je téměř Stejný nápad, ale je to trochu spravedlivější. Je to tak? Pokud jste některý z těchto ventilátorů chlapecké nebo dívky, které opravdu rád Apple produkty a probudil ve 3:00 se seřadí v nějakém obchodě získat nejnovější iPhone, budete mohl frontě takhle. 

Nyní fronta je velmi záměrně jmenován. Je to čára, protože tam je některé spravedlnost k němu. Je to tak? Bylo by trochu nasává, pokud jste tam dostal nejprve na Apple Store ale vy jste skutečně nejspodnější zásobník, protože zaměstnanci Apple pak pop poslední osoba, která vlastně dostal do vedení. Tak komíny a fronty, i když funkčně jsou druh na same-- je to právě tato kolekce zdrojů, které je tam bude růst a shrink-- se Tato spravedlnost aspekt k tomu, alespoň v reálném světě, kde tyto operace cvičíte jsou zásadně odlišné. Stack-- fronta rather-- je řekl, aby měl dvě operace: n fronty a d fronty. Nebo je můžete volat libovolný počet věcí. Ale jen chcete zachytit Představa, že člověk je přidání a jeden je nakonec odečtením. 

Nyní pod pokličku, jak stack a fronta by mohla být prováděna jak na to? Nebudeme zacházet do kódu to proto, že vyšší úroveň nápad je trochu více zřejmé. Chci říct, co lidé dělají? Pokud jsem první člověk na Apple Uložte a to je přední dveře, víš, já budu stát tady. A další osoby bude tady stát. A další osoby bude tady stát. Takže to, co datová struktura lze uplatnit na frontě? 

Diváků: fronta. DAVID Malan: No, fronta. Jistě. Co ještě? 

Diváků: spojový seznam. 

DAVID Malan: souvisí seznam, který by mohl realizovat. A spojový seznam je pěkné, protože pak může růst libovolně dlouho, na rozdíl se mít nějaký pevný počet lidí v obchodě. Ale možná, že pevně stanovený počet míst je legitimní. Vzhledem k tomu, pokud mají jen jako 20 iPhone první den, možná oni jen potřebují řadu velikostí 20 představují, že frontu, která je pouze říci teď, jakmile začneme mluvit o těchto problémech vyšší úrovni, můžete ji implementovat v mnoha různými způsoby. A je to asi jen tak být kompromis v prostoru a čase nebo jen ve svém vlastním kódu složitosti. 

Co stohu? No, zásobník, jsme viděli příliš může být jen tyto zásobníky. A ty by mohly realizovat toto pole. Ale v určitém okamžiku, pokud používáte pole, co se bude dít na zásobníky se snažíte dát dolů? Dobrá. Budeš jen moci jít tak vysoko. A myslím, že v Mather, že jsou skutečně zapuštěné v tomto otvoru. Takže ve skutečnosti, to je téměř jako Mather používá pole pevné velikosti, protože můžete jen vejde tolik zásobníky v tomto otvoru v stěny dolů pod kolena lidí. A tak, aby mohla být říká, že je pole, ale mohli bychom jistě realizovat, že obecněji s propojeného seznamu. 

No, co jiného datové struktury? Dovolte mi, abych vytáhnout jeden jiný vizuální zde. Něco jako, jak o tomhle tady? Proč by mohlo být užitečné mít ne něco tak nóbl jako trie, která viděli jsme měli tyto velmi široké uzly, z nichž každý je v poli? Ale co když uděláme něco víc jednoduše, jako staré školy rodokmenu, jejichž jednotlivé uzly zde právě ukládání čísel. Místo názvu nebo potomka právě ukládání čísel, jako je tento. 

No, žargon používáme v datové struktury je oba snaží a stromy, kde Trie, opět, je jen ten, jehož uzly jsou pole, je stále to, co by mohlo používat od základní škole když jste se rodina tree-- listy a kořen stromu a děti mateřská a jejich sourozenci. A my bychom mohli realizovat strom, například, jak jednoduše jako to. Strom, pokud to jako uzel, jeden z Tyto kruhy, které má číslo, že to nebude mít jeden ukazatel, ale dva. A jakmile přidáte Druhý ukazatel, můžete nyní mohou skutečně udělat trochu dvourozměrného údajů struktury v paměti. Stejně jako dvojrozměrný pole, můžete mít takovou dvou-dimenzionální spojové seznamy, ale ty že následovat vzor tam, kde je žádné cykly. Je to opravdu strom s jedním prarodič až sem a pak někteří rodiče a děti a vnoučata a pravnoučata. a tak dále. 

Ale co je opravdu hezké o tom taky, jen proto, aby tě škádlit s trochou kódu, odvolání rekurze od chvíli zpět, přičemž můžete napsat funkci, která volá sama sebe. To je krásná příležitost provádět něco jako rekurze, protože to považují. 

Jedná se o strom. A byl jsem trochu anální s tím, jak Dal jsem celá čísla na ulici. Natolik, že to má zvláštní name-- binární vyhledávací strom. Nyní jsme slyšeli o binární hledat, ale můžete pozpátku ze jména ta věc je? Co je vzor, ​​jak jsem vložena celá čísla do tohoto stromu? To není libovolná. Tam je nějaký vzor. Jo. 

Diváků: menší na levé straně. 

DAVID Malan: Jo. Menší jsou na levé straně. Ty větší jsou na pravé straně. Tak, že pravdivé tvrzení je rodič je větší než jeho levé dítě, ale méně než pravém dítě. A to samo o sobě je ještě rekurzivní slovní definice protože můžete použít, že Stejná logika se ke každému uzlu a to jen dna out, referenční případ, pokud vás bude, když narazí jeden z listy, abych tak řekl, kde dovolená má žádné děti dál. 

Nyní, jak můžete najít číslo 44? Ty by začít u kořene a říct, hm. 55 není 44 Tak to já chci jít právo nebo nechci jít doleva? No, samozřejmě budete chtít jít doleva. A tak je to stejně jako telefon Kniha příklad v binární vyhledávání obecněji. Ale my jsme jeho provádění Nyní trochu více dynamicky než pole může dovolit. A ve skutečnosti, pokud se chcete podívat na kód, na první pohled jistě. Vypadá to, že spoustu linek. Ale je to krásně jednoduché. Chcete-li implementovat funkci volal hledání, jehož smysl života je hledat hodnotu jako je N, celé číslo, a ty jsi prošel v jednom pointer-- ukazatel na uzel kořenů, spíše z toho stromu, z něhož můžete přistupovat všechno ostatní, Všimněte si, jak přímočaře můžete implementovat logiku. Pokud je strom je null, samozřejmě, že to tam není. Řekněme, vrátí false. Je to tak? Pokud to ruce nic, tam nic není. 

Jinak, jestliže n je menší než strom šipka n- nyní šipka n, vzpomínám jsme zavedli Super Krátce na druhý den, a to jen znamená, že de-reference ukazatel a podívejte se na pole s názvem n. Takže to znamená, tam a podívejte se na pole s názvem n. Takže pokud n, hodnota, kterou jste daný, je méně než hodnota v korunách stromů číslo, kam chcete jít? Doleva. 

Takže si všimnout rekurzi. Já returning-- není pravda. Ne false. Vracím se bez ohledu na odpověď je z volání sebe, kolem opět n, která je nadbytečná, ale to, co je teď trochu jinak? Jak mám dělat problém menší? Jsem předáním jako druhý Argument není kořen stromu, ale levá dítě v tomto případě. Takže jsem kolem v levém dítěte. 

Mezitím, pokud n je větší než uzel Jsem v současné době při pohledu na, Jsem hledat na pravé straně. Jinak, v případě, že strom není null, a V případě, že prvek není doleva a není to na pravé straně, co je nádherně případ? Jsme skutečně našli uzel v otázka, a tak jsme se vrátit true. 

Tak jsme právě poškrábaný povrch nyní některé z těchto datových struktur. V problém nastavit pět budete prozkoumat tyto ještě dále, a budete mít váš návrh Volba, jak jít o to. Co bych chtěl na závěr o je jen 30 sekund teaser o tom, co čeká příští týden a mimo ni. 

Jak jsme begin-- naštěstí byste mohli think-- náš přechod pomalu ze světa C a nižší detaily implementace na úrovni, do světa, v němž si můžeme pro samozřejmé, že někdo jiný má konečně realizovány tyto údaje struktury pro nás, a začneme chápat reálný svět prostřednictvím prováděcích web-based programy a Webové stránky obecně a také velmi bezpečnostní důsledky, které jsme jen začal poškrábat povrch. Zde je to, co nás čeká v příštích dnech. 

[VIDEO PŘEHRÁVÁNÍ] 

-Je Přišel se zprávou, s protokolem všichni jeho vlastní. Přišel na svět krutý firewally, routery, bezcitný a nebezpečí daleko horší než smrt. Je rychlý. On je silný. Je to TCP / IP, a on má svou adresu. "Válečníci sítě." [END VIDEOPŘEHRÁVÁNÍ] DAVID Malan: Již příští týden. Uvidíme se pak. [VIDEO PŘEHRÁVÁNÍ] -A Teď, "hluboké myšlenky" od Daven Farnham. -David Vždy začíná přednášky se, "v pořádku." Proč ne, "Tady je řešení na tento týden problém set " nebo "Dáváme všechny z vás?" [Smích] [END VIDEOPŘEHRÁVÁNÍ]