[Přehrávání hudby] ANDI PENG: Vítejte na týden 6 oddílu. Odklonili jsme z našeho standardu část doba úterý odpoledne na této krásné nedělní ráno. Děkuji vám, že pro každého připojil se mi dnes, ale vážně, potlesk. To je dost velký úsilí. Málem jsem nedostala ani právě včas, ale to bylo v pořádku. Takže vím, že každý z vás právě udělali to kvíz. Za prvé, vítejte odvrácenou stranou toho. Za druhé, budeme o tom mluvit. Promluvíme si o kvízu. Promluvíme si o tom, jak děláte ve třídě. Budeš v pořádku. Mám své kvízy pro jste na konci zde, Takže pokud si kluci chtějí, aby se Podívejte se na to, úplně v pohodě. Tak rychle, než začneme se agenda pro dnešek je následující. Jak můžete vidět, že jsme v podstatě rychlé palby přes spoustu datových struktur opravdu, opravdu, opravdu rychle. Tak jako takový, to nebude Super interaktivní dnes. Bude to jen mě trochu křik věci, které vás, a když jsem zmást, pokud jdu moc rychle, dejte mi vědět. Jsou to prostě různé údaje struktury, a jako součást vaší pset na to nadcházející týden, budete vyzváni k provedení jedné z nich, možná dvě z them-- dvou z nich v pset. OK, tak jsem jen tak začít s některými oznámení. Půjdeme přes komíny a další v front hloubka, než to, co jsme dělali před kvíz. Půjdeme přes spojené Seznam znovu, ještě jednou, více do hloubky, než to, co jsme měli předtím kvízu. A pak se budeme bavit o hash stoly, stromy a snaží se, které jsou všechny pěkně nezbytné pro pset. A pak půjdeme přes některé užitečné tipy pro pset5. OK, takže kvíz 0. Průměrná byl 58%. To byla velmi nízká, a tak vy všichni dělal velmi, velmi dobře v souladu s tím. Docela hodně, pravidlem je, pokud jste v rámci standardní odchylkou od průměrné hodnoty zejména proto, že jsme v méně pohodlný úsek, ty jsi úplně v pohodě. Jste na správné cestě. Život je krásný. Vím, že je to děsivé si myslet, že Dostal jsem se jako 40% na tento kvíz. Jdu k nezdaru této třídy. Slibuji vám, že nejste bude selhání třídu. Jsi úplně v pohodě. Pro ty z vás, kteří dostali více než střední, impozantní, působivý, jako, vážně dobře. Mám je s sebou. Neváhejte a pojďte si je na konci sekce. Dejte mi vědět, pokud máte nějaké problémy, otázky s nimi. Sečteme-li vaše skóre špatně, dejte nám vědět. OK, takže pset5, to je ve skutečnosti divný týden Yale v tom smyslu, že naše pset je kvůli Ve středu v poledne, včetně pozdní den, takže je to vlastně teoreticky kvůli úterý v poledne. Asi nikdo skončil v úterý v poledne. To je naprosto v pořádku. Budeme mít úřední hodiny Dnes večer stejně jako v pondělí večer. A to vše sekcích tento týden ve skutečnosti být otočen do dílen, tak neváhejte pop jakákoli část, kterou chcete, a oni budou trochu mini-pset workshopy o pomoc na to. Tak jako takový, to je jediná sekce kam máme výukový materiál. Všechny ostatní části budou zaměřovat výhradně na pomoc pro pset. To jo? Diváků: Kde jsou úřední hodiny? ANDI PENG: Úřední hodiny tonight-- oh, dobrá otázka. Myslím si, že úřední hodiny dnes večer jsou v Teal nebo na Commons. Pokud zaškrtnete on-line CS50 a jdete do úředních hodinách, by měl být plán, který vám řekne, kde jsou všechny z nich jsou. Vím, že buď dnes večer nebo zítra je modrozelený, a myslím, že můžeme mít commons pro druhé v noci. Nejsem si jist. Dobrá otázka. Podívejte se na CS50. Cool, nějaké dotazy týkající se harmonogram pro další jako tři dny? Slibuji, že se vám bude líbit David řekl, to je vrchol kopce. Vy jste skoro tam. Jen tři dny. Se tam dostat, a pak budeme všichni sestoupí. Budeme mít pěkný CS-volné přestávku. Vítej zpět. Budeme ponořit do webu programování a vývoj, věci, které jsou velmi zábavné srovnání na některé z dalších psets. A bude to chill a budeme mít spoustu legrace. Budeme mít více cukroví. Omlouváme se za sladkosti. Zapomněl jsem cukroví. Bylo to drsné ráno. Takže vy jste skoro tam, a já jsem opravdu pyšný z vás. OK, tak komíny. Kdo miluje na otázku o Jackovi a jeho oblečení na kvíz? Nikdo? OK, to je v pořádku. Takže v podstatě, jak můžete obrázek Jacku, tenhle chlapík tady, miluje vzít oblečení z vrcholu zásobníku, a on říká zpět na zásobníku poté, co udělal. Takže tímto způsobem, nikdy se zdá být stále do spodní části zásobník v jeho oblečení. Takže tento druh popisuje základní struktura dat o tom, jak je implementována zásobník. V podstatě, myslet na stack jako každý stoh objektů kam dát věci na vrchol, a pak vyskočí ven z vrcholu. Takže LIFO je zkratka máme rádi na use-- poslední dovnitř, první ven. A tak poslední se do horní části stack je první, který vyjde. A tak se dva termíny chceme přiřadit S tím se nazývají tlak a pop. Když budete tlačit něco Na stack, a ty to pop zpět nahoru. A tak myslím, že to je tak trochu abstraktní pojem pro ty z vás, kteří chtějí vidět jako skutečném provádění tohoto v reálném světě. Jak mnozí z vás psali esej Možná jako hodiny, než to bylo způsobeno, a vy omylem smazané obrovský kus z toho, jako náhodou? A co potom kontrola dělat používáme, aby ji zpět? Řízení-Z, jo? Control-Z, takže množství časů že Control-Z mi zachránil život, mi zachránil zadek, pokaždé která je prováděna prostřednictvím zásobníku. V podstatě všechny informace že je na vašem dokumentu aplikace Word, dostane tlačil a vyskočila na přání. A tak se v podstatě vždy, když vás vymazat vše, co si jen pop zpátky nahoru. A pak, pokud ji budete potřebovat znovu zapnete, vás zatlačte ji, což je to, co Control-C dělá. A tak skutečné funkce svět o tom, jak jednoduché datové struktury mohou pomoci s vaší každodenní život. Takže struct je cesta, která jsme vlastně vytvořit zásobník. My typ definovat struct, a poté říkáme, že zásobník na dně. A v rámci stohu, máme dva parametry že může být v podstatě manipulovat, takže máme char hvězdy řetězců kapacitu. Vše, co je dělá je vytvoření pole že můžeme ukládat, co chcete které můžeme určit jeho kapacitu. Kapacita je jen maximální množství položky můžeme dát do tohoto pole. velikost int je čítač, který udržuje Trať o tom, jak mnoha položek jsou v současné době ve stohu. Takže pak můžeme sledovat, A, oba, jak velký skutečné stack je, a, B, kolik z tohoto stohu jsme naplnili protože nechceme přetečení nad tím, co naše kapacita je. Tak například, tento krásný Otázka byla na kvíz. V podstatě, jak máme tlačit na horní části zásobníku. Docela jednoduché. Když se podíváte na to, projdeme to. Pokud [neslyšitelných] size-- pamatujte, kdykoli budete chtějí přistupovat k jakýmkoli parametr v struct, děláte název struct.parameter. V tomto případě, s je jméno naší zásobníku. Chceme, aby přístup k velikosti z toho, takže děláme s.size. Tak, pokud je velikost není rovnající se kapacity nebo tak dlouho, jak je to méně než kapacita, buď bude pracovat. Chcete-li získat přístup dovnitř vašeho stacku, tak s.strings, a budete dal, že nové číslo které chcete vložit do tam. Řekněme, že budeme chtít vložit int n do zásobníku, bychom mohli udělat s.strings, držáky, s.size rovná n. Vzhledem k tomu, velikost je místo, kde jsme V současné době je v balíčku pokud budeme tlačit to dál, jen jsme přístup všude tam, kde je velikost, tím proud plnost zásobníku, a přesuneme int n na něj. A pak chceme, aby se ujistil, že jsme také zvyšování velikosti n, takže můžeme sledovat máme přidal další věc, do stohu. Nyní máme větší velikost. Znamená to tady smysl všichni, jak logicky to funguje? Bylo to trochu rychle. Diváků: Můžeš jít přes se s.stringss.strings [s.size] znovu? ANDI PENG: Jasně, takže to, co dělá s.size v současné době dát nám? Diváků: Je to aktuální velikost. ANDI PENG: Přesně, takže Současný index, že naše velikost je, a tak chceme, aby se nové číslo že chceme vložit do s.size. Dává to smysl? Vzhledem k tomu, s.strings, vše, co je je název pole. Vše, co to je, je přístupem do array v našem struct, a tak pokud chceme místo n do tohoto indexu, můžeme jen přistupovat pomocí konzoly s.size. Bezva. Dobře, pop, pseudokód jsem to pro vás, ale podobným konceptem. Dává to smysl? Pokud je velikost je větší než nula, pak se víte, že chcete, aby se něco , protože v případě, že velikost není větší než nula, pak se nemá nic v zásobníku. Takže si jen chcete spustit tento kód, jen to může pop pokud je něco pop. Takže, pokud je velikost je větší než 0, jsme minus velikost. Decrement jsme velikost a pak se vrátit co je uvnitř, protože praskání, chceme Přístup, co je uloženo v indexu vrcholu zásobníku. Všechno, co smysl? Kdybych tě kluci psát na to, by vy moci psát to? OK, vy můžete hrát si s ním. Žádné starosti, pokud nechcete dostat to. Nemáme čas na kód it out dnes, protože máme mám hodně těchto struktur projít, ale v zásadě pseudokód, velmi, velmi podobné, aby se zasadila. Stačí sledovat spolu logiky. Ujistěte se, že máte přístup všechny vlastnosti vašeho struct správně. To jo? Diváků: budou tyto snímky a Celá tahle věc být až dnes ish? ANDI PENG: Vždy, jo. Budu se snažit dát toto nahoru jako hodinu poté. Budu email Davida, se bude snažit David dal ji jako hodinu po této. OK, takže pak jsme se přestěhovat do ta druhá půvabný datová struktura volal fronty. Jak vy můžete vidět zde, je fronta, pro Brity mezi námi, vše, co je, je řada. Takže na rozdíl od toho, co si myslíte, že zásobník je, fronta je přesně to, co logicky si myslíte, že je. Je držen pravidel FIFO, což je první dovnitř, první ven. Pokud jste první jednou v řadě, jste první, který vychází z řady. Takže to, co jsme chtěli volat toto je dequeueing a enqueueing. Chceme-li přidat něco k naší frontě, my Zařadí. Pokud chceme, aby dequeue, nebo se něco pryč, my dequeue. Takže stejný pocit, že jsme trochu vytvoření pevné velikosti prvků, které jsme je možné uložit jisté věci, ale můžeme také změnit místo, kde jsme umístěním Parametry uvnitř nich založené na tom, jaký typ funkčnost chceme. Takže komíny, chtěli jsme poslední jedním, N, že je první ven. Fronta je chceme první věc, V být první věc ven. Takže struct typu definovat, jak můžete vidět, je to trochu jinak z toho, co bylo stack protože nejen že se musíme držet trať, kde v současné době je velikost, také chceme sledovat hlavy stejně jako, kde jsme v současné době jsou. Takže si myslím, že je jednodušší pokud kreslím to. Takže pojďme si představit, že máme frontu, takže řekněme, že hlava je tady. V čele linky, pojďme jen říct, že je to v současné době, a chceme vložit něco, co se do fronty. Chystám se zavolat velikosti v podstatě je totéž jako ocas, konec všude tam, kde je vaše fronta. Řekněme, že velikost je právě zde. Tak jak se dá reálně vložit něco do fronty? Co index chceme umístit kam chceme vložit do. Pokud je to na začátku svého fronty a to je její konec nebo velikost tom, kde my chcete přidat další objekt? Diváků: [Neslyšitelné] ANDI PENG: Přesně tak, chcete přidat to v závislosti na jste to napsal. Buď je to prázdné, nebo že je prázdná. Takže chcete, aby jej přidat pravděpodobně tady, protože v případě, že velikost je-- pokud jsou všechny plné, chcete přidat tady, ne? A tak to je, když velmi, velmi jednoduché, ne zcela vždy správné proto, že hlavní rozdíl mezi fronty a zásobníku je to, že se fronta může vlastně být vykonáván tak, že změny hlavové V závislosti na tom, kde chcete začátek vaší povel ke startu. A jako výsledek, vaše ocas je také změní. A tak se podívat na Tento kód právě teď. Jak vy jste byli požádáni, aby vypsat na kvíz, Enqueue. Možná, že budeme hovořit přes proč odpověď byla, co to bylo. Nemohl jsem úplně fit tento řádek na jednom, ale v podstatě tento kus kódu by měl být na jednom řádku. Strávit jako 30 sekund. Podívejte se, a uvidíte, proč to je tak, že to je. Velmi, velmi podobný struct, velmi, velmi podobnou strukturou jako při předchozí stack s výjimkou snad jeden řádek kódu. A že jeden řádek kódu určuje funkce. A je to opravdu odlišuje fronty z komína. Každý, kdo chtějí, aby se stab vysvětlit, proč nemáš dostal tuto komplikovanou věc tady? Vidíme návrat našeho báječný kamarád modul. Jak vy brzy přijde uznat v programování, téměř kdykoliv budete potřebovat něco zabalit kolem cokoliv, modul bude způsob, jak to udělat. Tak s vědomím, že někdo chce aby se pokusili vysvětlit tento řádek kódu? Jo, jsou všechny odpovědi přijatí a vítáni. Diváků: Mluvíš se mnou? ANDI PENG: Jo. Publikum: Oh, ne líto. ANDI PENG: OK, tak se pojďme projít tímto kódem. Takže, když se snažíte přidat něco na frontě, v krásném případě, že hlava se stane být tady, je to pro nás velmi snadné prostě jít až do konce vložit něco, ne? Ale celý bod na frontě že hlava může skutečně dynamicky mění v závislosti na tom, kde jsme Chcete začátku naší q být, a jako takový, ocasu je také změní. A tak si představit, že to není fronty, ale spíše je to fronty. Řekněme, že hlava je tady. Řekněme, že naše fronta vypadala takhle. Pokud bychom chtěli posunout kde na začátku linky je, řekněme, že jsme se posunul hlavou Tímto způsobem a tady velikosti. Nyní chceme něco přidat Tato fronta, ale jak vy můžete vidět, to není tak jednoduché, jak jen přidat to, co je za velikostí protože pak dojdou meze naší aktuální pole. Kam chceme opravdu přidat je zde. To je krása fronty je to, že pro nás, vizuálně vypadá jako linka jde takhle, ale pokud jsou uloženy v datové struktuře, dávají to jako jako cyklus. Je to druh obaluje na přední straně stejný způsobem že vedení může také zábal kolem závisí na všude tam, kde vás chtějí začátku řádku být. A tak pokud budeme trvat podívejte se sem dolů, pojďme že jsme chtěli vytvořit Funkce tzv zařazení do fronty. Chtěli jsme přidat int n do tohoto q. Pokud q.size q-- budeme říkat, že naše data structure-- když náš queue.size není se rovná kapacit nebo jestliže je to méně než kapacita, q.strings je pole v našem q. Budeme nastavit rovnající se q.heads, který je tady, a navíc q.size modul kapacitou, který zábal nás zpátky tady. Takže v tomto příkladu, index hlavy je 1, že jo? Index velikosti je 0, 1, 2, 3, 4. Takže můžeme udělat 1 plus 4 modul naší kapacity, která je 5. Co, že nám dá? Co je index, který vychází z toho? Diváků: 0. ANDI PENG: 0, což se stane být tady, a tak chceme být schopni vložit do právě zde. A tak tato rovnice zde druh z právě pracuje s čísly V závislosti na tom, kde vaše hlava a vaše velikost jsou. Pokud víte, co ty, věci jsou, víte, přesně tam, kde chcete vložit co je po vašem fronty. Znamená to, že smysl pro všechny? Vím, že jakýsi mozku teaser zejména proto, že přišel v důsledku vašeho kvíz. Ale doufejme, že všichni Nyní můžete pochopit, proč toto řešení, nebo to Funkce je tak, že to je. Každý, kdo trochu nejasné na to? DOBŘE. A tak teď, pokud jste chtěl dequeue, to je místo, kde by naše hlava se přesouvá protože pokud bychom měli dequeue, nebereme z konce q. Chceme, aby se z hlavy, že jo? Takže v důsledku toho hlava se změní, a to je důvod, proč, když se Zařadí, musíš sledovat kde se vaše hlava a vaše velikost jsou, aby bylo možné vložit do správné polohy. A tak když se dequeue, Také jsem pseudokód to. Neváhejte a pokud chcete, pokusit kódování to. Chcete přesunout hlavu, ne? Kdybych chtěl dequeue, I by se posunout hlavu nad. To by být hlava. A náš současný velikost by odčítání, protože již není mají čtyři prvky v poli. Máme jen tři, a pak chceme vrátit, co byl uložen uvnitř hlavy, protože chceme, aby se tento hodnota se tak velmi podobný zásobníku. Jen jste při z jiného místa, a vy budete muset přiřadit svou ukazatel na jiném místě jako výsledek. Logicky, každý následovat? Skvělý. OK, takže budeme mluvit trochu více do hloubky asi spojových seznamech protože bude velmi, velmi cenná pro vás v průběhu roku tento týden psets. Spojové seznamy, jak jste kluci Pamatuji si, všechno, co jsou jsou uzly, které jsou uzly jisté Hodnoty obou hodnotu a ukazatel , které jsou spojeny dohromady těmito ukazateli. A tak se na to, jak struct jsme se vytvořit uzel tady je, že jsme mají int n, což je cokoliv hodnota v obchodě nebo řetězce n nebo co chcete říkají, char hvězda n. Uzel struct hvězda, což je ukazatel které chcete mít v každém uzlu, budete mít, že Ukazatel bod k další. Budete mít hlavu propojeného seznamu, který je bude poukázat na zbytku hodnoty tak dále a tak dále dokud se nakonec dostanete na konec. A to je jen poslední uzel bude to mít ukazatel. Bude to poukázat na null, a to je, když víte, že jste hit konec vašeho seznamu Google je, když vaše poslední ukazatel neukazuje na nic. Tak jsme se chystáte jít trochu více do hloubka ohledně toho, jak by člověk možná vyhledávat propojeného seznamu. Pamatujte si, jaké jsou některé z nevýhody propojených seznamů verše pole o vyhledávání. Pole můžete binární vyhledávání, ale proč nemůžete udělat, že v Google seznamu? Diváků: Vzhledem k tomu, že jsou všichni připojeni, ale nemáte dost vědět, kde [NESLYŠITELNÝ]. ANDI PENG: Jo, přesně tak si pamatujte: že brilance pole byla skutečnost, že jsme měli paměť s přímým přístupem, kde kdybych chtěl hodnotu z indexu šest, mohl bych jen říct index šest, dej mi tuto hodnotu. A to proto, že pole jsou řazeny v souvislém prostoru paměti na jednom místě, vzhledem k tomu, druh spojových seznamů jsou náhodně střídají všude kolem, a jediný způsob, jak můžete najít jeden je přes ukazatel, který vám řekne, adresa, kde, že příští uzel je. A tak jako výsledek, jediný způsob, jak prohledávat propojeném seznamu je lineární hledání. Protože já přesně nevím, kde 12. hodnota v Google seznamu je, Musím projít celistvost tohoto propojeného seznamu jeden jeden z hlavy do prvního uzlu, do druhého uzlu, na třetí uzlu, celou cestu dolů, až jsem se konečně dostanu kde uzel Sháním je. A tak v tomto smyslu, hledání v Google seznamu je vždy n. Je to vždycky n. Je to vždycky v lineárním čase. A tak se kód, ve kterém realizujeme to, a to je trochu nový pro vás, protože jste kluci se opravdu mluvili, nebo vůbec ukazatele vidět v tom, jak se prohledávat ukazatelů, takže budeme procházet tato velmi, velmi pomalu. Takže bool vyhledávání, vpravo, pojďme si představit, chceme vytvořit funkci nazvanou Hledání, který vrací true pokud jste našli hodnotě uvnitř spojené vypsat, a vrací false jinak. Uzel hvězda seznam je V současné době jen ukazatel na první položku ve vašem Google seznamu. int n je hodnota, kterou jste hledání v tomto seznamu. Takže uzel hvězda ukazatel rovná seznam. To znamená, že jsme nastavení a vytvoření ukazatele do tohoto prvního uzlu uvnitř seznamu. Každý, kdo se mnou? Takže pokud bychom měli jít zpátky, musel bych inicializovat ukazatel, který odkazuje na hlava, co tento seznam. A pak, jakmile se dostanete sem, zatímco ukazatel nerovná null, tak, že je smyčka, ve které jsou bude následně křížení zbytek našeho seznamu protože to, co se stane, když ukazatel rovná null? Víme, že jsme have-- Diváků: [Neslyšitelné] ANDI PENG: Přesně, takže víme, že jsme došli na konec seznamu, je to tak? Vydáte-li se zpátky, každý uzel musí směřovat do jiného uzlu a tak dále a tak dále dokud nenarazíte nakonec ocas vašeho Google seznamu, který má ukazatel, který právě neukazuje jinde než žádný. A tak jste v podstatě víte, že váš seznam je zde stále nahoře dokud ukazatel není rovno null, protože jakmile se rovná null, víte, že není více věcí. Tak, že je smyčka, ve které jsme bude mít aktuální vyhledávání. A v případě, že pointer-- vidíš že druh šipky tam funkce? Takže pokud ukazatel ukazuje na n, pokud ukazatel v n rovná se rovná n, tak, že znamená, že pokud ukazatel, že jste vyhledávání na konci každého Uzel je vlastně rovná hodnotě hledáte, pak se chcete vrátit hodnotu true. Takže v podstatě, pokud jste na uzlu, který má hodnotu, kterou hledáte, víte, že jste byli schopni úspěšně vyhledávat. V opačném případě, že chcete nastavit ukazatel na další uzel. To je to, co tento řádek je zde dělá. Ukazatel se rovná ukazatel další. Všichni vidět, jak to funguje? A v podstatě budete jen přejít celistvost seznamu, resetování ukazatel pokaždé, dokud budete nakonec narazí na konec seznamu. A víte, že neexistují žádné více uzlů prohledávat, a pak můžete return false protože víte, že, oh, no, pokud jsem byl schopen vyhledávat přes celé seznamu. Pokud by v tomto příkladu, kdybych chtěl hledat na hodnotu 10, I a začít v čele, a I hledání celou cestu dolů, a nakonec jsem se dostal k tomu, který ukazatel, který poukazuje na hodnotu null, Vím, že, blbost, myslím, že 10 není v Tento seznam proto, že jsem nemohl najít. A já jsem se na konci seznamu. A v takovém případě víte, Chystám se vrátit false. Ať že máčet v pro trochu. To bude dost důležité pro vaši pset. Logika je to velmi jednoduché, snad syntakticky jen jejím provádění. Vy chcete, aby Ujistěte se, že rozumíte. Bezva. OK, tak jak bychom byli vkládání uzlů, vpravo, do seznamu, protože pamatovat jaké jsou to, co výhod mít propojeného seznamu oproti pole, pokud jde o skladování? Diváků: Je to dynamický, takže je to jednodušší, to-- ANDI PENG: Přesně tak, tak je to dynamický, který znamená, že se může rozšířit a zmenšit V závislosti na potřebách uživatele. A tak, v tomto smyslu, nepotřebujeme ztrácet zbytečně paměť, protože jsem když nevím, kolik hodnot Chci skladovat, to nemá smysl pro mě vytvořit pole z následujících důvodů když chci uložit 10 hodnot a já se vytvořit řadu 1000, to je hodně nevyužité paměti, přiděleny. To je důvod, proč chceme použít propojený seznam, aby bylo možné dynamicky změnit nebo zmenšit naši velikost. A tak to dělá vkládání trochu složitější. Vzhledem k tomu, nemůžeme náhodně přístup k prvkům tak, že bychom z pole. Pokud chci vložit prvek do sedmé indexu Jen jsem si ji vložit do sedmé indexu. V propojeném seznamu, to není poměrně pracovat tak snadno, a tak pokud bychom chtěli vložit ten tady v Google seznamu, vizuálně, je to velmi dobře vidět. Chceme jen, aby ho vložit přímo tam, hned na začátku seznamu, hned po hlavě. Ale způsob, jakým musíme přeřadit Ukazatele se trochu spletitý nebo, logicky, to dává smysl, ale chcete, aby se ujistil, že to máte úplně dolů, protože to poslední, co chcete, je přiřadit ukazovátka tak, že tady děláme. Pokud vás dereference ukazatel od hlavy až k 1, pak najednou The zbytek vašeho Google seznamu je ztraceno, protože jste není vlastně vytvořili dočasný cokoliv. To ukázal na 2. Pokud přiřazení ukazatel, pak se zbytek vašeho seznamu je zcela ztracen. Takže vy chcete být velmi, velmi opatrný zde nejprve přiřadit ukazatel z jakéhokoli vás chcete vložit do kamkoli chceš, a pak vás může dereference zbytek vašeho seznamu. Tak to platí pro kdekoli snažíte vložit do. Chcete-li vložit u hlava, chcete-li odpovědět na tu, pokud chcete vložit na konec, no, nakonec jsem se Asi byste právě nemají žádný ukazatel, ale vy chcete, aby se ujistil, že nemáte ztratit zbytek seznamu. Vždycky chcete ujistit, Váš nový uzel směřuje směrem k co chcete vložit do, a pak můžete přidat zřetězení dál. Všichni jasné? To bude jeden ze skutečných problémů. Jedním z nejvíce hlavních problémů budete mít na svém pset je to, že budete snažit vytvořit propojený seznam a vložit věci ale pak jen ztratit zbytek svého Google seznamu. A ty budeš rád, já Nevím, proč se to děje? A je to bolest projít a hledat všechny vaše ukazatelů. A já vám zaručit, na tomto pset, psaní a kreslení těchto uzlů out bude velmi, velmi užitečné. Takže si můžete zcela sledovat kde všechny vaše ukazatele jsou, co se děje špatně, kde se všechny vaše uzly jsou, to, co musíte udělat, aby přístup nebo vložit nebo odstranit, nebo některý z nich. Všichni dobře s tím? Bezva. Takže pokud jsme chtěli podívat na kód? Oh, já nevím, jestli my můžete vidět the-- OK, tak V horní řadě je to je funkce jmenoval vložka tam, kde chceme vložit int n do propojeného seznamu. Chystáme se projít to. Je to hodně kódu, spousta novou syntaxí. Budeme v pořádku. Tak se v horní části, pokud je to chceme vytvořit něco co musíme udělat, zvláště pokud jste chcete, aby to nemělo být uložen v zásobníku ale v haldě? Jdeme do malloc, že ​​jo? Takže budeme vytvořit ukazatel. Uzel, ukazatel, nové rovná malloc velikost uzlu protože chceme, aby uzel, který bude vytvořen. Chceme, aby množství paměť, která uzel zabírá mají být přiděleny pro vytvoření nového uzlu. A pak budeme zkontrolovat, uvidíme, jestli nová rovná se rovná null. Vzpomeňte si, co jsme si řekli? Ať už vás malloc, Co musíte vždy udělat? Vždy musíte zkontrolovat, zda to je null. Například, pokud váš operační Systém byl úplně plný, pokud jste měli na ne více paměti všechny a zkuste malloc, že se vrátí null pro vás. A tak pokud se pokusíte použít když to bylo ukázal na null, vy nebudete schopni na přístup k těmto informacím. A tak jako takový, chtěli jsme, aby se jisti, že vždy, když jste mallocing, jste vždy zkontrolovat, zda že paměť daný pro vás je null. A pokud tomu tak není, pak se můžeme přesunout se zbytkem našeho kódu. Takže budeme inicializovat nový uzel. Chystáme se udělat nový n se rovná n. A pak budeme dělat nastavit nový ukazatel na nové na NULL, protože právě teď my ne chtějí něco pro to, aby ukazoval na. Nemáme tušení, kde to bude, aby vám, a pokud chceme vložte jej v čele, pak můžeme přiřadit ukazatel na hlavě. Má každý sledovat logiku kde že se to děje? Vše, co děláte, je vytvoření nového uzel, nastavení ukazatel na null, a pak přiřazení to do hlavy, kdybychom víte, chceme vložit do čela. A pak hlava se chystá ukazovat směrem k tomuto novému uzlu. Každý, kdo s tím OK? Takže je to dvoustupňový proces. Musíš Nejprve přiřaďte co budete vytvářet. Nastavit že ukazatel odkazovat, a pak vás může druh dereference první ukazatel a přejděte na nový uzel. Všude tam, kde ji chcete vložit, že logika bude platit. Je to něco jako přiřazení dočasné proměnné. Pamatujte si, že máte aby se ujistil, že vás neztrácejí přehled o pokud jste swapování. Chcete, aby se ujistil, že máte dočasná proměnná, která druh udržuje sledovat, kde té věci je uložena tak, že neztratili žádnou hodnotu v průběhu jako se pohráváte s ním. OK, takže tady bude kód. Vy se podívat po bodu. Bude to tam. Takže si myslím, jak se to se liší, pokud bychom chtěli vložit do středu nebo na konci? Má někdo má představu o tom, co je to pseudokód jako logické reference že bychom trvat, pokud bychom chtěli jej vložit do středu? Takže pokud bychom chtěli vložit u hlava, vše, co udělat, je vytvořit nový uzel. Nastavili jsme ukazatel, který Nový uzel se to bez ohledu na hlavě, a pak jsme se nastavit hlavu do nového uzlu, že jo? Pokud bychom chtěli vložit do středu seznamu, co by se musíme udělat? Diváků: To by ještě být podobný proces jako se přiřazení ukazatele, pak přiřadí tento ukazatel, ale museli bychom tam najít. ANDI PENG: Přesně tak, přesně stejný proces kromě vás muset najít, kde přesně jste chcete, aby nový ukazatel jít do, takže pokud chci vložit do uprostřed spojeny list-- OK, řekněme, že je to naše provázaný seznam. Chceme-li jej vložit přímo tady, budeme vytvořit nový uzel. Jedeme do malloc. Chystáme se vytvořit nový uzel. Budeme přiřadit ukazatel tohoto uzlu zde. Avšak problémem, který se liší od místa, kde je hlava je, že jsme přesně věděli, kde je hlava. To bylo hned na počátku, že jo? Ale tady musíme sledovat kde jsme vložením do. Jsme-li vložit naše uzel tady, máme aby se ujistil, že člověk předchozí do tohoto uzlu je ten, který přiřazuje ukazatel. Takže pak budete muset trochu sledovat dvě věci. Máte-li sledovat, kde to uzel je v současné době vložení do. Musíte také sledovat, kde předchozí uzel, který se díváte byl také tam. Všichni dobře s tím? DOBŘE. Jak se o vložení do konce? Kdybych chtěl přidat here-- kdybych chtěl přidat nový uzel na konec seznamu, Jak bych mohl jít o tom, že? Publikum: Takže v současné době je poslední, kdo se ukázal na null. ANDI PENG: Jo. Přesně, takže tento jednou V současné době je orientováno na vědět, a tak myslím, že v tomto smyslu, že je to velmi snadno přidat na konec seznamu. Jediné, co musíte udělat, je nastavit rovná null a pak boom. Přesně tam, velmi snadné. Velmi jednoduché. Velmi podobné hlava, ale logicky vás chcete, aby se ujistil, že kroky užíváte k dělá něco z toho, jste po podél. Je to velmi snadné, ve středu vašeho kódu, uvíznou na, oh, mám tolik ukazatelů. Já nevím, kde něco ukazuje. Já ani nevím, který uzel, že jsem dál. Co se děje? Relax, uklidni se, zhluboka se nadechnout. Nakreslete si své propojeného seznamu. Pokud řeknete, já vím, kde přesně Musím vložit to do a vím přesně, jak změnit přiřazení my ukazatele, mnohem, mnohem jednodušší na obrázek out-- mnohem, mnohem jednodušší, že nebude ztratit v chybách v kódu. Každý, kdo s tím OK? DOBŘE. Takže si myslím, koncept, že jsme se opravdu mluvil o dřív, a myslím, že vás nejspíš není dojde mnohem yet-- je to docela pokročilé concept-- je to, že jsme vlastně mají údaje struktura volal dvojnásob propojeného seznamu. Tak jako vy můžete vidět, vše, co děláte, je vytvoření skutečné hodnoty, navíc Ukazatel na každé z našich uzlů která také poukazuje na předchozí uzlu. Takže nejen že máme své uzly poukazují na ten příští. Poukazují rovněž na předchozí. Budu ignorovat tyhle dva právě teď. Takže máte řetěz které se mohou pohybovat oběma směry, a pak je to trochu jednodušší logicky následovat. Stejně jako tady, místo sledování z, oh, já musí vědět, že tento uzel ten, který mám k přeřazení, Můžu prostě jít sem a stačí vytáhnout předchozí. Pak jsem přesně vědět, kde že je, a pak vás Nemusíte se přejít celistvost Google seznamu. Je to trochu jednodušší. Ale jako takový, budete mít dvojnásob množství ukazatelů, To je dvojnásobek paměti. Je to hodně ukazatelů sledovat. Je to trochu složitější, ale je to trochu více uživatelsky přívětivé závislosti na to, co se snažíte dosáhnout. Takže tento druh údajů Struktura zcela existuje, a struktura je velmi, velmi jednoduché, s výjimkou vše máte, je, namísto pouze ukazatel na další, máte také ukazatel na předchozí. To je vše, byl rozdíl. Všichni dobře s tím? Bezva. Dobře, takže teď jsem opravdu strávit pravděpodobně jako je 15 až 20 minut nebo objemu zbytku času v sekci mluví o hash tabulek. Kolik z vás Přečetl pset5 spec? Dobře, dobře. To je vyšší než 50% za normálních okolností. Je to v pohodě. Tak jako vy uvidíte, jste výzvou pset5 bude provádění slovník kde si nahrát přes 140.000 slov že jsme vám kontrolu pravopisu to proti všem textu. Dáme vám náhodné kusy literatury. Dáme vám Odyssea. Dáme vám Ilias. Dáme vám Austin Powers. A vaše výzva bude kontrolu pravopisu každé slovo ve všech z těchto slovníků v podstatě s naší kontrolou pravopisu. A tak je tu několik dílů vytvoření tohoto pset, První chcete být schopný skutečně načíst všechna slova do vašeho slovník, a pak vás chtějí být schopni pravopisu zkontrolovat všechny z nich. A tak jako takový, budete požadovat datová struktura, která může dělat to rychle a efektivně a dynamicky. Takže myslím, že nejjednodušší způsob, jak to provést, by pravděpodobně vytvoření pole, ne? Nejjednodušší způsob skladování je vám může vytvořit řadu 140,000 slov a jen je všechny umístit tam a pak přejít jim binární vyhledávání nebo výběrů či ne-- Omlouvám se, že se třídění. Můžete je třídit a pak přejít je binární vyhledávání, nebo jen lineární hledání a jen závěrečná slova, ale že bere obrovské množství paměti, a to není příliš efektivní. A tak jsme se chystáte začít mluví o způsobech, kterými se Naše doba chodu efektivnější. A naším cílem je dostat konstantní doba, kdy je to skoro jako pole, kde máte okamžitý přístup. Kdybych chtěl hledat cokoliv, Chci být schopen jen, boom, najít přesně to, a vytáhněte ji ven. A tak se struktura, v níž budeme stále velmi blízko aby bylo možné získat přístup konstantní čas, tento svatý grál v programování konstanty Čas se nazývá hash tabulky. A tak David již dříve zmínil o [Neslyšitelný] trochu v přednášce, ale budeme skutečně ponor v hluboké tento týden na kus, který je, pokud jde o jak hash tabulky funguje. Tak tak, že hash tabulka práce, například, kdybych chtěl uložit spoustu slovy, banda slov v anglickém jazyce, Mohl bych teoreticky dát banán, jablko, kiwi, mango, pár, a cantaloupe vše jen na matici. Všechny by mohly zapadnout a bude najít. Bylo by druh bolesti prohledávat a přístupu, ale jednodušší způsob, jak toho dosáhnout, je že můžeme vytvořit vlastně struktura nazývá hash tabulky, kde jsme hash. Vedeme všechny naše klíčů prostřednictvím funkce hash, rovnice, že změní je všechny do nějaký hodnotu že pak můžeme ukládat na v podstatě pole propojeného seznamu. A tak tady, pokud bychom chtěli ukládat anglická slova, jsme mohli potenciálně prostě, já ne Víte, vypněte všechny první písmena do nějakého druhu čísla. A tak například, když jsem chtěl A být synonymem apple-- nebo s indexem 0, a B synonymem s 1, můžeme mít 26 záznamů který může jen uložit všechna písmena abeceda, že začneme s. A pak můžeme mít apple v indexu od 0. Můžeme mít banán na indexu 1, ananasový meloun na indexu 2, a tak dále a tak dále. A tak, když jsem se chtěl vyhledávat můj hash stůl a přístup jablko, Vím, že jablko začíná à, a vím přesně, že to musí být a hash Tabulka na indexu 0 Protože je funkce dříve přiřazena. Takže já nevím, my jsme uživatelský program, kde budete obviněn arbitrarily-- nebylo svévolně, se snaží zamyšleně myslet na dobré rovnic aby bylo možné rozšířit mimo všechny své hodnoty takovým způsobem, že mohou snadno získat přístup to později se jako rovnice že vy, sami, víš. Takže v tom smyslu, jestli bych chtěl jít do mango, já vím, oh, začíná m. To musí být v indexu 12. Nemám prohledávat cokoliv. Vím, že exactly-- jsem mohl jen jít do index 12 a vytáhněte to ven. Každý jasně o tom, jak hashovací funkce tabulky funguje? Je to tak trochu jen složitější pole. To je vše, co je. DOBŘE. Takže myslím, že narazíme tato otázka toho, co se stane, když máte více věcí že vám stejný index? Tak říkají naši funkci, všichni to udělal, bylo, přijmout, že první písmeno a měnit na Příslušná 0 až 25 index. To je naprosto v pořádku, pokud máte pouze jeden z každého z nich. Ale druhá začnete které mají více, že jste bude mít, co se nazývá kolize. Takže když se snažím vložit pohřbít do hash tabulka, která již má banán na tom, co se stane, když pokusu o vložení, že? Zlé věci proto, že banán Již v rámci indexu existuje že chcete uložit jej do. Berry druh je jako, ehm, co mám dělat? Nevím, kam jít. Jak mohu vyřešit? A tak si kluci bude druh viz děláme této choulostivé věci kde můžeme trochu vlastně Vytvoření propojeného seznamu v našich polích. A tak nejjednodušší způsob přemýšlet o tom, všechny hash tabulka je řada spojových seznamů. A tak, v tomto smyslu, máte toto krásné pole ukazatelů, a pak každý ukazatel v že hodnota tohoto indexu, může skutečně ukazovat na jiné věci. A tak budete mít všechny tyto oddělené řetězy spadnutí jednoho velkého pole. A tak tady, když jsem chtěl vložit bobule, Já vím, v pořádku, budu vstup to přes můj hash funkce. Chystám se skončit s indexem 1, a pak budu mít možnost jen menší podmnožina toto obří 140000-slovo slovníku. A pak jsem si jen dívat prostřednictvím 1/26 toho. A tak jsem si jen vložit bobule buď před nebo po banány v tomto případě? Po, že jo? A tak budete chtít vložit tento uzel po banán, a tak budete vkládat na ocasu tohoto propojeného seznamu. Chystám se vrátit zpět k tomuto předchozímu snímku, tak vy můžete vidět, jak hash funkce pracuje. Takže hash funkce je tato rovnice že vedete druh váš vstup až se dostat co index Chcete-li ji přiřadit k. A tak, v tomto případě všechno, co jsme chtěli udělat, bylo vzít první písmeno, obrátit, že do indexu, pak jsme lze uložit, že v našem hash funkce. Vše, co tu děláme, je, že jsme konverzi první písmeno. Takže keykey [0] je jen první písmeno jakéhokoli string budeme mít, jsme předáním. Jsme konverzi, že pro horní, a jsme se odečte od velkými písmeny A, takže vše, co dělá nám dává číslo v němž můžeme hash naše hodnoty na. A pak budeme návrat hash modulu velikosti. Buďte velmi, velmi opatrní proto, že teoreticky, zde Váš hash hodnota mohla být nekonečná. Mohlo by to prostě jít dál a dál a dál. Mohlo by to být nějaké opravdu, Opravdu velké hodnoty, ale proto, že vaše hash tabulky, které jste vytvořili má pouze 26 indexy, chcete ujistěte se, že modulusing takže ne run-- je to to samé věc jako queue-- takže nemusíte spouštět off Spodní část vašeho hash funkce. Chcete zabalit zpět kolem stejným způsobem v [neslyšitelných], když jste měl jako velmi, velmi velké písmeno, vy nechtěl, aby stačí spustit až na konec. To samé tady, chcete ujistit, neběží z konce obalem kolem horní části tabulky. Tak to je jen velmi jednoduchá funkce hash. Vše, co udělala, bylo vzít jako první Dopis z jakéhokoli našeho vstupu byla a měnit na index, který jsme mohli dát do naší tabulky hash. Jo, a tak jak jsem řekl dříve, tak, že jsme se vyřešit kolizí v naší hash tabulek mají, To, čemu říkáme, řetězení. Takže pokud se pokusíte vložit více slova, která začínají stejnou věc, budete mít jednu hodnotu hash. Avokádo a jablko, pokud jste spusťte jej přes naše hash funkce, Chystáte se vám dát Stejné číslo, počet 0. A tak způsob, jak vyřešit to je že můžeme vlastně trochu propojit společně prostřednictvím spojových seznamů. A tak v tomto smyslu, vy můžete vidět druh o tom, jak datové struktury, které jsme se nastavit dříve jako rozinkami spojen se seznamem druhu z může přijít společně do jednoho. A pak si můžete vytvořit daleko účinnější datové struktury který zvládne větší množství Data, která dynamicky měnit velikost v závislosti na vašich potřebách. Všichni jasné? Každý druh clear o tom, co se zde děje? Kdybych chtěl insert-- co je to ovoce, které začíná, já nevím, B, jiné než Berry, banán. Diváků: Blackberry. ANDI PENG: Blackberry, Blackberry. Kam blackberry jít sem? No, my vlastně nejsou tříděny to ještě, ale teoreticky Pokud bychom chtěli mít tuto v abecedním pořadí, kam by měl jít BlackBerry? Diváků: [Neslyšitelné] ANDI PENG: Přesně, po tu, že jo? Ale protože je to velmi obtížné reorder-- Myslím, že je to na vás kluci. Vy můžete zcela implementovat, co chcete. Čím více účinný způsob jak to udělat snad by bylo seřadit spojené vypsat do abecedním pořadí, a tak, když jste vkládání věcí, budete chtít si být jisti, o jejich zařazení do abecedním pořadí takže pak, když jste snaží se je hledat, nemusíte projít všechno. Víte přesně, kde to je, a je to jednodušší. Ale pokud máte trochu věci proložené náhodně, jste stále bude mít to procházet tak jako tak. A tak, když jsem se chtěl jen vložit blackberry zde a já jsem chtěl hledat to, já vím, oh, ostružina musí začínat s indexem 1, a tak jsem vím, okamžitě stačí hledat na 1. A pak jsem si trochu procházet propojeného seznamu dokud se na BlackBerry, a then-- jo? Diváků: Pokud se snažíte create-- Myslím, že takhle je to velmi jednoduchý hash funkce. A pokud bychom chtěli dělat více vrstev, kteří rádi, OK, chceme rozdělit na stejně jako všechny znaky abecedy a pak zase rád jiný soubor abecedních písmen v rámci, který, jsme uvedení jako hash Tabulka v hash tabulky, nebo jako funkce v rámci funkce? Nebo je that-- ANDI PENG: Takže vaše hash function-- vaše hash tabulky může být tak velký, jak chcete, aby to. Takže v tomto smyslu, myslel jsem, to bylo velmi jednoduché, velmi jednoduché pro mě prostě tak nějak na bázi dopisů z první slovo. A tak je tu jen 26 možností. Mohu jen dostat 26 z možností 0 až 25, protože se může pouze začít od A do Z. Ale Pokud byste chtěli přidat, možná více složitosti nebo rychlejší běh času, aby svůj hash tabulky, si absolutně můžete dělat všechny druhy věcí. Můžete si vytvořit svůj vlastní rovnice, která vám dává více rozdělení ve vašem slova, pak při vyhledávání, že to bude rychlejší. Je to zcela na vás kluci jak chcete implementovat to. Myslete na to, jak jen kbelíky. Pokud bych chtěl mít 26 kbelíky, jdu třídit věci do těchto kbelíky. Ale já budu mít spoustu věcí v každém kbelíku, takže pokud chcete, aby to rychlejší a efektivnější, dovolte mi, abych sto kbelíky. Ale pak budete muset přijít na to, způsob, nechte tak, aby byly ve správném kbelíku, které by měly být v. Ale pak, když jste vlastně Chcete se podívat na tom kbelík, je to mnohem rychlejší, protože tam je méně věci v každém segmentu. A tak, jo, to je vlastně trik pro vás v pset5 je to, že budete vyzváni, aby jen vytvořit co je nejúčinnější funkce si můžete myslet, že je schopna ukládat a kontrolovat tyto hodnoty. Zcela na vás kluci však budete chtít dělat to, ale to je opravdu dobrý bod. Že druh logiky vy chtějí začít přemýšlet o Je dobře, tak proč ne já dělat více kbelíky. A pak jsem musel hledat méně věcí, a pak možná já mají jiný hash funkce. Jo, je tu mnoho způsobů, jak toho dosáhnout pset, některé jsou rychleji než ostatní. Já naprosto bude jen vidět, jak rychlá byl nejrychlejší kluci budou být schopni dostat své funkce do práce. OK, všichni dobře na PROPOJENÍ ZÁSOB a hashovací tabulky? Je to vlastně jako velmi jednoduchý koncept, pokud si myslíte o tom. Vše, co to je, je oddělování cokoliv vaše vstupy jsou do kbelíků, jejich třídění, a pak vyhledávání ve uvádí, že je spojován s. Bezva. Dobře, teď máme jiný druh datové struktury, které se říká strom. Pojďme dál a hovoří o pokusech , které jsou zřetelně odlišné, ale ve stejné kategorii. V podstatě, všichni strom je místo organizování dat v lineárně že hash tabulka vám does-- vím, je to má horní a spodní část a pak tak nějak propojit pryč to-- na Strom má horní který nazýváte kořen, a pak to má listy všechno kolem něj. A tak vše, co zde je jen na nejvyšší uzel , který odkazuje na jiných uzlů, které body na více uzlů, a tak dále a tak dále. A tak stačí štípání větví. Je to jen jiný způsob organizace dat, a protože jsme to strom volání, vy jen-- je to jen modelován ven vypadat jako strom. To je důvod, proč říkáme, že stromy. Hash tabulka vypadá jako tabulky. Strom jen vypadá jako strom. Vše, co to je, je samostatná způsob organizace uzlů V závislosti na jaké jsou vaše potřeby. Takže máte kořen a pak máte listy. Způsob, jakým můžeme zvláště přemýšlet o tom, že je to binární strom, binární strom je jen Specifickým typem stromu kde každý uzel pouze body k, při max, další dva uzly. A tak tady máte odlišný symetrie ve vašem stromě že usnadňuje druh vypadat na jaké hodnoty jste, protože pak vás mají vždy levý nebo pravý. Tam je nikdy jako levé třetinu levá nebo čtvrtiny z levé strany. Je to jen máte doleva a právo a můžete vyhledávat buď z těchto dvou. A proč je to užitečné? Způsob, jakým je užitečné, je pokud hledáte prohledávat hodnotám, že jo? Spíše než se provádí binární hledat v chybové poli, pokud byste chtěli mít možnost vložit uzly a odnést uzly na vůli a také zachovat vyhledávání kapacity binární vyhledávání. Takže tímto způsobem, jsme trochu Pamatuji si, když jsme tricking-- řekl spojové seznamy nemohou binární hledání? Jsme trochu vytvoření datové struktury že triky, které do práce. A to proto, spojové seznamy jsou lineární, oni jen propojit jeden po druhém. Můžeme mít trochu jiný druh ukazatelů tento bod na různé uzly že nám může pomoci s vyhledáváním. A tak tady, kdybych chtěl mají strom binárního vyhledávání, Vím, že moje druhé, jestliže 55. Já jsem prostě jít k vytvoření, že jako můj středu, jako můj kořen, a pak budu mít Hodnoty spin off z toho. Tak tady, pokud budu hledat hodnotu 66, mohu začít na 55 let. To je 66 vyšší než 55? Ano, je to, takže vím, že mus hledat i n pravý ukazatel tohoto stromu. Chodím do 77. OK, je menší než 66 nebo větší než 77? To je méně než, takže víte, oh, , který má být na levé straně uzlu. A tak tady máme trochu konzervování všechny z velkých věcí, o poli, tak jako dynamickou změnu velikosti objektů, přičemž moci vkládat a mazat na vůli, aniž by se museli starat o fixní množství prostoru. Stále jsme zachovat všechny ty úžasné věci a zároveň je schopen se zachovala log a hledání času binární vyhledávání že jsme pouze dříve možnost získat frázi. Pohodě datová struktura, druh provádění složité, uzel. Jak můžete vidět, všechny to je struct uzlu je to, že máte vlevo a pravý ukazatel. To je vše, co je. Takže spíše než jen mající x nebo předchozí. Máte doleva nebo doprava a můžete trochu propojit dohromady Nicméně se tak rozhodnete. OK, jsme vlastně bude jen trvat několik minut. Takže budeme vrátit se sem. Jak už jsem řekl dříve, Tak nějak jsem vysvětlil, logika, jak by se hledat přes to. Budeme se snažit pseudocoding na to vidět, pokud můžeme trochu použije Stejná logika binárního vyhledávání na jiný typ datové struktury. Pokud si kluci chtějí, aby se jako pár minut, jen přemýšlet o tom. DOBŘE. Dobře, budu vlastně jen aby vám the-- ne, budeme mluvit o pseudocode jako první. Takže to někdo chtěl dát stab na to, co První věc, kterou chcete dělat, když začínáte z vyhledávání? Pokud hledáme hodnota 66, co je První věc, kterou chceme dělat, když chceme binární vyhledávání tento strom? Diváků: Chcete vypadat správně a podívat se vlevo a podívejte [neslyšitelný] větší počet. ANDI PENG: Jo, přesně tak. Takže budete podívat se na svůj kořen. Je tu spousta způsobů, jak můžete volat to, vaši rodič uzel lidé říkají. Líbí se mi říci, protože kořen to je jako kořen stromu. Budeš se dívat na kořenový uzel, a vy jste jde vidět, je 66 vyšší nebo menší než 55. A pokud je to větší než, no, to je větší než tam, kde chceme vypadat? Kde chceme hledat, ne? Chceme prohledat Pravá polovina tohoto stromu. Takže máme, pohodlně, je ukazatel, který ukazuje na pravé straně. A tak pak můžeme nastavit náš nový kořen být 77. Můžeme prostě jít kamkoli pointer ukazuje. No, oh, tady začínáme na 77, a můžeme jen to rekurzivně znovu a znovu. Tímto způsobem, tak nějak o mají funkci. Máte způsob vyhledávání, které vás stačí opakovat znovu a znovu a znovu, podle toho, kde se chcete podívat až se nakonec dostal na hodnotu které hledáte. Dávat smysl? Chystám se vám ukázat skutečný kódu, a je to hodně kódu. Není třeba šílet. Promluvíme si přes to. Ve skutečnosti, no. To byl jen pseudokód. OK, to byl jen pseudokód, který je trochu složitější, ale je to naprosto v pořádku. Každý, kdo po podél tady? Je-li kořen je null, návrat false protože to znamená vy ani nemusíte nic tam. Je-li kořen n je hodnota, takže pokud je se stane být ten, že jste při pohledu na, pak budete vrátí hodnotu true protože víte, že jste ji našli. Ale pokud je tato hodnota nižší než root n, ty jsi bude hledat levý dítě nebo levé křídlo, co chcete říkat. A pokud je hodnota vyšší než root, budete hledat ten správný strom, pak stačí spustit funkci pomocí vyhledávání znovu. A jestliže kořen je null, že znamená, že jste došli na konec? To znamená, že nemáte Více odchází hledat, pak víte, oh, já Asi to není v tu protože po Díval jsem se přes celá věc a není to tady, to prostě nemusí být tady. Znamená to, že smysl pro všechny? Takže je to jako binární vyhledávání konzervačním Schopnosti propojených seznamů. Cool, a tak druhý typ datové struktury vy kluci mohou vyzkoušet provádění na pset, máte jen vybrat jednu metodu. Ale možná alternativní metodou hash tabulka je to, co nazýváme trie. Vše, Trie je je Specifickým typem stromu má hodnoty, které jdou na jiné hodnoty. A tak místo toho, binární strom v tom smyslu, že pouze jedna věc může poukázat na dva, můžete mít jedna věc, přejděte na mnoho, mnoho věcí. Ty mají v zásadě pole uvnitř které ukládáte ukazatele, které ukazují na jiné pole. Takže uzel, jak by definoval trie je chceme mít Boolean, c slovo, že jo? Takže uzel je Boolean jako pravdivé či nepravdivé, v první řadě v čele že pole, je to slovo? Za druhé, chcete mít ukazatele se bez ohledu na ostatní z nich jsou. Trochu složitější, trochu abstraktní, ale Budu vysvětlovat, co to všechny prostředky. Tak tady, na vrcholu, pokud jste mají celou řadu deklaroval již, uzel, kde máte Boolean hodnota uložena na přední straně který vám řekne, je to slovo? Není to slovo? A pak máte zbytek vašeho pole, které ve skutečnosti ukládá všechny možnosti toho, co by to mohlo být. Tak, například, jako je nahoře máte První věc, která říká, že pravda nebo false, ano nebo ne, to je slovo. A pak máte 0 až 26 písmena, které můžete uložit. Pokud bych chtěl hledat zde pro bat, jdu na vrchol a já se pro B. najdu B v mém pole, a tak vím, v pořádku, je B slovo? B není slovo, takže se tak Musím pokračovat v hledání. Jdu z B, a já se k ukazatel, který ukazuje na B a vidím jiný řadu informací, stejnou strukturu, které jsme předtím. A here-- oh, další Dopis v [neslyšitelný] je A. Takže se podíváme v tomto poli. Najdeme osmý hodnotu, a pak se podíváme vidět, oh, hej, je to jedním slovem, je B-A slovo? Nejedná se o slovo. Musíme hledat dál. A tak pak se podíváme na místo, kde ukazatel z A bodů, a odkazuje na jiný způsob v který máme větší hodnotu uloží do paměti. A nakonec jsme se dostat do B-A-T, což je slovo. A tak se příště vypadáš, budete mít tento kontrolu, ano, tato Boolean funkce je pravda. A tak se v tom smyslu, že jsme trochu mít strom s poli. Takže můžete trochu hledat dolů. Spíše než hash funkce a přiřazení hodnot Google seznamu můžete jen implementovat Trie, který prohledává downwords. Opravdu, opravdu složité věci. Není snadné si myslet, o, protože jsem rád plivat tolik datových struktur out na vás, ale dělá každý druh pochopit, jak logika to funguje? OK v pohodě. A tak B-A-T, a pak se budete hledat. Příště jdeš vidět, oh, hej, to je pravda, Vím, že to tak musí být slovo. Totéž pro zoo. Tak tady je to právě teď, když jsme chtěl hledat zoo, právě teď, V současné době zoo není slovo v našem slovníku protože, jak vy můžete vidět, První místo, které máme Boolean vrátí pravda, je na konci zoom. Máme Z-O-O-M. A tak tady, nemáme vlastně mít Slovo, zoo, v našem slovníku proto, že toto políčko není zaškrtnuto. Takže počítač není vědí, že zoo je slovo, protože tak, že máme uložil to, jen zoom zde ve skutečnosti má logickou hodnotu , která byla obrátil pravda. Takže pokud chceme vložit slovo, zoo, do našeho slovníku, jak bychom jít o tom, že? Co musíme udělat, aby se ujistil, naše počítač ví, že Z-O-O je slovo a ne první slovo je Z-O-O-M? Diváků: [Neslyšitelné] ANDI PENG: Přesně tak, my chcete, aby se ujistil, že tento tady, že logická hodnota je odškrtnout, že je to pravda. Z-O-O, pak budeme kontrolovat, zda, takže přesně víme, hej, zoo je slovo. Chystám se říct, Počítač, který je to slovo tak že když je počítač kontroly, ví, že zoo je slovo. Vzhledem k tomu, vzpomenout na všechny tyto údaje struktury, je to pro nás velmi snadné říci, oh, netopýr je to slovo. Zoo je to slovo. Přiblížit to slovo. Ale když jste ho staví, počítač nemá ani ponětí. Takže musíte to říct přesně na jakém místě je to slovo? V jakém okamžiku není to slovo? A na jakém místě dělat já je třeba hledat věci, a na jakém místě se musím jít dál? Každý jasné, že? Bezva. A tak pak přijde Problém, jak by jsme se jít o vložení něco že to vlastně není? Takže řekněme, že chceme vložit Slovo, lázně, do našeho trie. Jak vy můžete vidět, jako v současné době všechno, co máme teď, je B-A-T, a tato nová struktura dat tam měl půllitr, který poukázal na hodnotu null, protože předpokládáme, že, oh, je tu po B-A-T žádná slova, proč potřebujeme zachovat mají věci po tomto T. Problém však nastává, když budeme dělat vás chtějí mít slovo, které přichází po T je. Pokud máte vanu, jste bude chtít H právo. A tak způsob, jakým budeme k tomu, že je budeme vytvořit samostatný uzel. Nejsme přidělit bez ohledu na částku, paměti pro toto nové pole, a budeme přiřadit ukazatele. Budeme přiřadit H, Za prvé, to null, budeme zbavit. Budeme mít Bod H směrem dolů. Pokud vidíme H, chceme ho jít někam jinam. Tady, pak můžeme odškrtnout ano. Pokud bychom hit H po T, oh, pak víme, že se jedná o slovo. Boolean se chystá vrátit true. Všichni jasné, o tom, jak se to stalo? DOBŘE. Takže v podstatě všechny Tyto datové struktury že jsme přešli dnes, jsem opravdu, ale opravdu rychle pryč nad nimi a ne v mnohem detail, a to je v pořádku. Jakmile začnete umazávání s tím, budete sledování, kde Všechny ukazatele jsou, co se děje ve vašem datové struktury, a tak dále. Budou velmi užitečné, a je jen na vás, kluci úplně zjistit, jak Chcete-li implementovat věci. A tak pset4, z 5-- oh, to je špatné. Pset5 je překlepy. Jak jsem již řekl dříve, budete, jakmile Znovu, stáhněte zdrojový kód od nás. Tam to bude Tři hlavní věci, které budete stahovat. Budete stáhnout slovníky, KERS, a texty. Všechny tyto věci jsou, jsou buď slovníky slov že chceme, abyste zkontrolovat nebo test informací že chceme, abyste kontrolu pravopisu. A tak se slovníky dáme jdete aby vám aktuální slova, které chceme ukládat nějak způsobem, který je účinnější než pole. A pak texty jsou Bude to, co jsme s žádostí o kontrolu pravopisu, aby se ujistil všechna slova existují skutečné slova. A tak tři bloky programy, které dáme vám se nazývají dictionary.c, dictionary.h, a speller.c. A tak všichni dictionary.c dělá, je co jste vyzváni k realizaci. To načte slova. To kouzlo je zkontroluje, a to je jistý, že vše je správně vložen. diction.h je jen soubor knihovny že deklaruje všechny tyto funkce. A speller.c, budeme dát. Nemusíte měnit nic z toho. Všechny speller.c dělá, je vzít to, Zatížení to, kontroluje rychlost na to, testuje měřítko jako jak rychle jste schopni dělat věci. Je to speller. Prostě to není nepořádek s ním, ale udělat se, že jste pochopili, co to dělá. Používáme funkci nazvanou getrusage že testuje výkon svého kouzla checker. Vše, co to dělá, je v podstatě otestování Čas všechno ve vašem slovníku, takže se ujistěte, jste to pochopili. Buďte opatrní, aby nepořádek s ním, nebo jinde se věci nebude fungovat správně. A Převážná část tohoto problému je pro vy opravdu změnit dictionary.c. Budeme vám 140.000 slov ve slovníku. Budeme vám textu soubor, který má tato slova, a chceme, abyste byli schopni zorganizovat je do tabulky hash nebo trie protože když vás žádáme, aby bylo patrné check-- představte si, že jste kouzlo kontrola jako Homerovi Odysseia. Je to jako obrovský, obrovský tento test. Představte si, že každý slovo, které se musel podívat prostřednictvím řady 140.000 hodnot. To by trvalo věčnost pro váš počítač spustit. To je důvod, proč chceme organizujeme data do efektivnějších datových struktur jako je například hashovací tabulky nebo trie. A pak vy můžete druh o při hledání přístupu věci snadněji a rychleji. A tak buďte opatrní na řešení kolizí. Budeš mít spoustu ze slov, která začínají A. Budeš mít spoustu slov že začít s B. Až do vás chlapi, jak chcete ho řešit. Možná, že tam je víc efektivní funkce hash než jen prvním písmenem něco, a tak to je jen na vás kluci druh dělat, co chcete. Možná chcete přidat všechny dopisy dohromady. Možná chcete líbit dělat divné věci na účet počtu písmen, cokoliv. Až vás kluci, jak chcete dělat. Pokud si chcete udělat hash tabulky, pokud jste chcete pokusit o Trie, zcela na vás. Budu vás varovat předem, že Trie je obvykle o něco složitější jen proto, že je tu spousta další ukazatele sledovat. Ale zcela na vás kluci. Je to mnohem efektivnější ve většině případů. Chcete-li být opravdu schopna udržet přehled o všech vašich ukazatelů. Jako udělat totéž že jsem tady. Když se snažíte vložit Hodnoty do tabulky hash nebo odstranit, ujistěte se, že jste Opravdu sledování kde je vše proto, je to pro jestli jsem rychlé pokoušíte vložit rád slovo, Andy. Řekněme, že je to skutečné slovo, slovo, andy, do obří seznamu A slov. Kdybych náhodou přeřadit ukazatel špatně, oops, tam jede celistvost zbytek mého Google seznamu. Teď jediné slovo, které jsem mají, je Andy, a teď všechny ostatní slova v Slovník byly ztraceny. A tak se chcete ujistit, že sledovat všechny vaše ukazatelů jinak budete mít obrovské problémy v kódu. Remíza věci pečlivě krok za krokem. To dělá to mnohem jednodušší myslet. A konečně, chcete být schopni otestovat výkon vašeho programu na velké desce. Jestliže vy trvat podívejte se na CS50 právě teď, máme to, co se nazývá velký deska. Je to skóre list nejrychlejší kouzlo časů kontrolní napříč všemi CS50 právě teď, myslím, že na vrchol jako 10 Časy Myslím si, že osm z nich jsou zaměstnanci. Opravdu chceme vy, aby nás porazil. Každý z nás se snaží realizovat nejrychlejší kód jak je to možné. Chceme, aby si kluci, aby se pokusili napadnout nás a realizovat rychleji, než my všichni plechovka. A tak to je opravdu to poprvé, co jsme dotazem vám kluci udělat pset který si můžete opravdu dělat v jakékoliv metodě chceš. Vždycky říkám, to je více podobný do reálného života řešení, ne? Já říkám, hej, musíš to udělat. Postavit program, který dělá to pro mě. Udělej to však budete chtít. Já jen vím, že chci, aby rychle. To je vaše výzva pro tento týden. Vy chlapi, jdeme aby vám úkol. Budeme vám výzvu. A pak je to na vás kluci úplně jen přijít na to, co je nejrychlejší a nejvíce účinný způsob, jak realizovat to. To jo? Diváků: Jsme dovoleno, pokud chtěl vyhledejte rychlejší způsoby dělat hash tabulky on-line, můžeme to udělat že a citují kód někoho jiného? ANDI PENG: Jo, úplně v pohodě. Takže pokud vy přečíst spec, je tu řada v spec, který říká, že kluci jsou zcela zdarma a vyhledejte hash funkce na jaké jsou některé z rychlejší hash funkce běžet věci skrze as dlouho, jak vám citovat, že kód. Takže někteří lidé již přišel na to, rychlé postupy dělání překlepů, rychlého způsoby ukládání informací. Zcela na vás kluci, pokud vás chtějí jen brát, že jo? Ujistěte se, že jste s odvoláním. Výzvou zde opravdu že se snažíme testovat je ujistit se, že víte, svou cestu kolem ukazatele. Tak daleko, jak se provádí skutečné funkce hash a přichází s podobně matematika k tomu, že, vy můžete výzkum cokoliv metody on-line kluci chtějí. To jo? Diváků: Můžeme uvést jen pomocí [neslyšitelných]? ANDI PENG: Jo. Stačí si jen, ve váš komentář, můžete citovat jako, oh, převzato z Yada, bla, bla, hashovací funkce. Každý, kdo má nějaké otázky? Vlastně jsme breezed úsekem dnes. Budu se sem odpovědět na otázky stejně. Také, jak jsem řekl, kancelářské hodin dnes večer a zítra. Spec tento týden je vlastně super snadné a super krátký číst. Navrhoval bych, že pohled, jen pročíst celé to. A Zamyla vás vlastně procházky přes každou z funkcí budete muset implementovat, a tak je to velmi, velmi jasné, jak to udělat všechno. Jen aby se ujistil, že jste sledování ukazatelů. Jedná se o velmi náročný pset. Není to náročné, protože rád, oh, pojmy jsou tak mnohem více obtížné, musíte se naučit tak mnoho nového syntaxe cesta že jste na poslední pset. To pset je obtížné, protože existuje tolik ukazatele, a pak je to velmi, velmi snadné, jakmile máte chybu v kódu nebudou moci zjistit, kde, že chyba je. A tak naprostý víru ve vás chlapi, aby mohli porazit naše [neslyšitelných] hláskování. Já vlastně nemám žádný písemný důl ještě, ale já jsem to psal já. Takže zatímco píšete vaše, budu psát moje. Budu se snažit, aby moje rychleji než vaše. Uvidíme, kdo má nejrychlejší jeden. A jo, budu vidět všechny vy tady v úterý. Budu spustit jakýsi se jako pset dílně. Všechny sekcích tohoto týden jsou pset dílny, takže si kluci mají spoustu možností o pomoc, úřední hodiny jako vždy, a já se opravdu těším na čtení všichni kódu vašich kluci. Mám vyslýchá tady, pokud vás kluci chtějí jít dostat ty. To je vše.