[Prehrávanie hudby] 

ANDI PENG: Vitajte na týždeň 6 oddielu. Odklonili sme z nášho štandardu časť doba utorok popoludní na tejto krásnej nedeľné ráno. Ďakujem vám, že pre každého pripojil sa mi dnes, ale vážne, potlesk. 

To je dosť veľký úsilie. Skoro som nedostala ani práve včas, ale to bolo v poriadku. Takže viem, že každý z vás práve urobili to kvíz. Po prvé, vitajte odvrátenou stranou toho. 

Po druhé, budeme o tom hovoriť. Porozprávame sa o kvízu. Porozprávame sa o tom, ako robíte v triede. Budeš v poriadku. Mám svoje kvízy pre ste na konci tu, Takže ak si chlapci chcú, aby sa Pozrite sa na to, úplne v pohode. 

Tak rýchlo, ako začneme sa agenda pre dnešok je nasledujúci. Ako môžete vidieť, že sme v podstate rýchle paľby cez veľa dátových štruktúr naozaj, naozaj, naozaj rýchlo. Tak ako taký, to nebude Super interaktívne dnes. Bude to len ma trochu krik veci, ktoré vás, a keď som zmiasť, ak idem moc rýchlo, dajte mi vedieť. Sú to jednoducho rôzne údaje štruktúry, a ako súčasť vašej pset na to nadchádzajúci týždeň, budete vyzvaní na vykonanie jednej z nich, možno dve z them-- dvoch z nich v pset. OK, tak som len tak začať s niektorými oznámenia. Pôjdeme cez komíny a ďalšie v front hĺbka, než to, čo sme robili pred kvíz. Pôjdeme cez spojené Zoznam znova, ešte raz, viac do hĺbky, než to, čo sme mali predtým kvízu. A potom sa budeme baviť o hash stoly, stromy a snaží sa, ktoré sú všetky pekne nevyhnutné pre pset. A potom pôjdeme cez niektoré užitočné tipy pre pset5. 

OK, takže kvíz 0. Priemerná bol 58%. To bola veľmi nízka, a tak vy všetci robil veľmi, veľmi dobre v súlade s tým. 

Celkom veľa, pravidlom je, ak ste v rámci štandardnej odchýlkou ​​od priemernej hodnoty najmä preto, že sme v menej pohodlný úsek, ty si úplne v pohode. Ste na správnej ceste. Život je dobrý. 

Viem, že je to desivé si myslieť, že Dostal som sa ako 40% na tento kvíz. Idem na neúspech tejto triedy. Sľubujem vám, že nie ste bude zlyhanie triedu. Si úplne v pohode. 

Pre tých z vás, ktorí dostali viac ako stredná, impozantný, pôsobivý, ako, vážne dobre. Mám ich so sebou. Neváhajte a poďte si ich na konci sekcie. Dajte mi vedieť, ak máte nejaké problémy, otázky s nimi. Sčítame Ak vaše skóre zle, dajte nám vedieť. 

OK, takže pset5, to je v skutočnosti divný týždeň Yale v tom zmysle, že naše pset je kvôli V stredu na poludnie, vrátane neskoré deň, takže je to vlastne teoreticky kvôli utorok napoludnie. Asi nikto skončil v utorok napoludnie. To je úplne v poriadku. Budeme mať úradné hodiny Dnes večer rovnako ako v pondelok večer. A to všetko sekciách tento týždeň v skutočnosti byť otočený do dielní, tak neváhajte pop akákoľvek časť, ktorú chcete, a oni budú trochu mini-pset workshopy o pomoc na to. Tak ako taký, to je jediná sekcia kam máme výukový materiál. Všetky ostatné časti budú zameriavať výhradne na pomoc pre pset. Jo? 

Divákov: Kde sú úradné hodiny? 

ANDI PENG: Úradné hodiny tonight-- oh, dobrá otázka. Myslím si, že úradné hodiny dnes večer sú v Teal alebo na Commons. Ak zaškrtnete on-line CS50 a idete do úradných hodinách, by mal byť plán, ktorý vám povie, kde sú všetky z nich sú. 

Viem, že buď dnes večer alebo zajtra je modrozelený, a myslím, že môžeme mať commons pre druhé v noci. Nie som si istý. Dobrá otázka. Pozrite sa na CS50. 

Cool, nejaké otázky týkajúce sa harmonogram pre ďalšie ako tri dni? Sľubujem, že sa vám bude páčiť David povedal, to je vrchol kopca. Vy ste skoro tam. Len tri dni. Sa tam dostať, a potom budeme všetci zostúpi. Budeme mať pekný CS-voľné prestávku. Vrátime sa. Budeme ponoriť do webu programovanie a vývoj, veci, ktoré sú veľmi zábavné porovnanie na niektoré z ďalších psets. A bude to chill a budeme mať veľa zábavy. Budeme mať viac cukroví. Ospravedlňujeme sa za sladkosti. Zabudol som cukrovinky. Bolo to drsné ráno. Takže vy ste skoro tam, a ja som naozaj pyšný z vás. 

OK, tak komíny. Kto miluje na otázku o Jackovi a jeho oblečenie na kvíz? Nikto? OK, to je v poriadku. 

Takže v podstate, ako môžete obrázok Jack, tento chlapík tu, miluje vziať oblečenie z vrcholu zásobníku, a on hovorí späť na zásobníka potom, čo urobil. Takže týmto spôsobom, nikdy sa zdá byť stále do spodnej časti zásobník v jeho oblečení. Takže tento druh popisuje základná štruktúra dát o tom, ako je implementovaná zásobník. 

V podstate, myslieť na stack ako každý stoh objektov kam dať veci na vrchol, a potom vyskočí von z vrcholu. Takže LIFO je skratka máme radi na use-- posledný dnu, prvý von. A tak posledný sa do hornej časti stack je prvý, ktorý vyjde. A tak sa dva termíny chceme priradiť S tým sa nazývajú tlak a pop. Keď budete tlačiť niečo Na stack, a ty to pop späť hore. 

A tak myslím, že to je tak trochu abstraktný pojem pre tých z vás, ktorí chcú vidieť ako skutočnom vykonávaní tohto v reálnom svete. Ako mnohí z vás písali esej Možno ako hodiny, než to bolo spôsobené, a vy omylom zmazané obrovský kus z toho, ako náhodou? A čo potom kontrola robiť používame, aby ju späť? Riadenie-Z, jo? Control-Z, takže množstvo časov že Control-Z mi zachránil život, mi zachránil zadok, zakaždým ktorá je vykonávaná prostredníctvom zásobníka. 

V podstate všetky informácie že je na vašom dokumente programu Word, dostane tlačil a vyskočila na želanie. A tak sa v podstate vždy, keď vás vymazať všetko, čo si len pop naspäť hore. A potom, ak ju budete potrebovať znova zapnete, vás zatlačte ju, čo je to, čo Control-C robí. A tak skutočné funkcie svet o tom, ako jednoduché dátové štruktúry môžu pomôcť s vašou každodenný život. 

Takže struct je cesta, ktorá sme vlastne vytvoriť zásobník. My typ definovať struct, a potom hovoríme, že zásobník na dne. A v rámci stohu, máme dva parametre že môže byť v podstate manipulovať, takže máme char hviezdy reťazcov kapacitu. 

Všetko, čo je robí je vytvorenie poľa že môžeme ukladať, čo chcete ktoré môžeme určiť jeho kapacitu. Kapacita je len maximálne množstvo položky môžeme dať do tohto poľa. veľkosť int je čítač, ktorý udržuje Trať o tom, ako mnohých položiek sú v súčasnej dobe v stohu. Takže potom môžeme sledovať, A, oboch, ako veľký skutočné stack je, a, B, koľko z tohto stohu sme naplnili pretože nechceme pretečeniu nad tým, čo naša kapacita je. 

Tak napríklad, tento krásny Otázka bola na kvíz. V podstate, ako máme tlačiť na hornej časti zásobníka. Celkom jednoduché. Keď sa pozriete na to, prejdeme to. Ak [nepočuteľných] size-- pamätajte, kedykoľvek budete chcú pristupovať k akýmkoľvek parameter v struct, robíte názov struct.parameter. 

V tomto prípade, s je meno našej zásobníka. Chceme, aby prístup k veľkosti z toho, takže robíme s.size. Tak, ak je veľkosť nie je rovnajúcu sa kapacity alebo tak dlho, ako je to menej ako kapacita, buď bude pracovať. 

Ak chcete získať prístup dovnútra vášho stacku, tak s.strings, a budete dal, že nové číslo ktoré chcete vložiť do tam. Povedzme, že budeme chcieť vložiť int n do zásobníka, by sme mohli urobiť s.strings, držiaky, s.size rovná n. Vzhľadom k tomu, veľkosť je miesto, kde sme V súčasnej dobe je v balíčku ak budeme tlačiť to ďalej, len sme prístup všade tam, kde je veľkosť, tým prúd plnosť zásobníku, a presunieme int n na neho. A potom chceme, aby sa uistil, že sme tiež zvyšovanie veľkosti n, takže môžeme sledovať máme pridal ďalšie vec, do stohu. Teraz máme väčšiu veľkosť. Znamená to tu zmysel všetci, ako logicky to funguje? Bolo to trochu rýchlo. Divákov: Môžeš ísť cez sa s.stringss.strings [s.size] znova? ANDI PENG: Jasné, takže to, čo robí s.size v súčasnej dobe dať nám? Divákov: Je to aktuálnu veľkosť. ANDI PENG: Presne, takže Súčasný index, že naša veľkosť je, a tak chceme, aby sa nové číslo že chceme vložiť do s.size. Dáva to zmysel? Vzhľadom k tomu, s.strings, všetko, čo je je názov poľa. Všetko, čo to je, je prístupom do array v našom struct, a tak ak chceme miesto n do tohto indexu, môžeme len pristupovať pomocou konzoly s.size. Super. 

Dobre, pop, pseudokód som to pre vás, ale podobným konceptom. Dáva to zmysel? Ak je veľkosť je väčšia ako nula, potom sa viete, že chcete, aby sa niečo , Pretože v prípade, že veľkosť nie je väčšie ako nula, potom sa nemá nič v zásobníku. 

Takže si len chcete spustiť tento kód, len to môže pop ak je niečo pop. Takže, ak je veľkosť je väčšia ako 0, sme mínus veľkosť. Decrement sme veľkosť a potom sa vrátiť čo je vo vnútri, pretože praskanie, chceme Prístup, čo je uložené v indexe vrcholu zásobníku. Všetko, čo zmysel? Keby som ťa chlapci písať na to, by vy môcť písať to? OK, vy môžete hrať sa s ním. Žiadne starosti, ak nechcete dostať to. Nemáme čas na kód it out dnes, pretože máme mám veľa týchto štruktúr prejsť, ale v zásade pseudokód, veľmi, veľmi podobné, aby sa zasadila. Stačí sledovať spolu logiky. Uistite sa, že máte prístup všetky vlastnosti vášho struct správne. Jo? 

Divákov: budú tieto snímky a Celá táto vec byť až dnes ish? ANDI PENG: Vždy, jo. Budem sa snažiť dať toto hore ako hodinu potom. Budem email Davida, sa bude snažiť David dal ju ako hodinu po tejto. 

OK, takže potom sme sa presťahovať do tá druhá pôvabný dátová štruktúra volal fronty. Ako vy môžete vidieť tu, je front, pre Britov medzi nami, všetko, čo je, je rad. Takže na rozdiel od toho, čo si myslíte, že zásobník je, front je presne to, čo logicky si myslíte, že je. Je držaný pravidiel FIFO, čo je prvý dovnútra, prvý von. Ak ste prvý raz v rade, ste prvý, ktorý vychádza z rady. 

Takže to, čo sme chceli volať toto je dequeueing a enqueueing. Ak chceme pridať niečo k našej fronte, my Zaradí. Ak chceme, aby dequeue, alebo sa niečo preč, my dequeue. 

Takže rovnaký pocit, že sme trochu vytvorenie pevnej veľkosti prvkov, ktoré sme je možné uložiť isté veci, ale môžeme tiež zmeniť miesto, kde sme umiestnením Parametre vnútri nich založené na tom, aký typ funkčnosť chceme. Takže komíny, chceli sme posledný jedným, N, že je prvý von. Fronta je chceme prvá vec, V byť prvá vec von. 

Takže struct typu definovať, ako môžete vidieť, je to trochu inak z toho, čo bolo stack pretože nielen že sa musíme držať trať, kde v súčasnosti je veľkosť, tiež chceme sledovať hlavy rovnako ako, kde sme v súčasnej dobe sú. Takže si myslím, že je jednoduchšie ak kreslím to. Takže poďme si predstaviť, že máme front, takže povedzme, že hlava je tu. V čele linky, poďme len povedať, že je to v súčasnej dobe, a chceme vložiť niečo, čo sa do fronty. Chystám sa zavolať veľkosti v podstate je to isté ako chvost, koniec všade tam, kde je vaša front. Povedzme, že veľkosť je práve tu. 

Tak ako sa dá reálne vložiť niečo do fronty? Čo index chceme umiestniť kam chceme vložiť do. Ak je to na začiatku svojho fronty a to je jej koniec alebo veľkosť tom, kde my chcete pridať ďalší objekt? 

Divákov: [Nepočuteľné] ANDI PENG: Presne tak, chcete pridať to v závislosti na ste to napísal. Buď je to prázdne, alebo že je prázdna. Takže chcete, aby ho pridať pravdepodobne tu, pretože v prípade, že veľkosť je-- ak sú všetky plné, chcete pridať tu, nie? 

A tak to je, keď veľmi, veľmi jednoduché, nie celkom vždy správne preto, že hlavný rozdiel medzi fronty a zásobníka je to, že sa front môže vlastne byť vykonávaný tak, že zmeny hlavové V závislosti na tom, kde chcete začiatok vašej povel k štartu. A ako výsledok, vaše chvost je tiež zmení. A tak sa pozrieť na Tento kód práve teraz. Ako vy ste boli požiadaní, aby vypísať na kvíz, Enqueue. Možno, že budeme hovoriť cez prečo odpoveď bola, čo to bolo. 

Nemohol som úplne fit tento riadok na jednom, ale v podstate tento kus kódu by mal byť na jednom riadku. Stráviť ako 30 sekúnd. Pozrite sa, a uvidíte, prečo to je tak, že to je. 

Veľmi, veľmi podobný struct, veľmi, veľmi podobnej štruktúre ako pri predchádzajúcej stack s výnimkou snáď jeden riadok kódu. A že jeden riadok kódu určuje funkcie. A je to naozaj odlišuje fronty z komína. 

Každý, kto chcú, aby sa stab vysvetliť, prečo nemáš dostal túto komplikovanú vec tu? Vidíme návrat nášho báječný kamarát modul. Ako vy čoskoro príde uznať v programovaní, takmer kedykoľvek budete potrebovať niečo zabaliť okolo čokoľvek, modul bude spôsob, ako to urobiť. Tak s vedomím, že niekto chce aby sa pokúsili vysvetliť tento riadok kódu? Jo, sú všetky odpovede prijatí a vítaní. Divákov: Hovoríš so mnou? ANDI PENG: Jo. Publikum: Oh, nie ľúto. ANDI PENG: OK, tak sa poďme prejsť týmto kódom. Takže, keď sa snažíte pridať niečo na fronte, v krásnom prípade, že hlava sa stane byť tu, je to pre nás veľmi ľahké jednoducho ísť až do konca vložiť niečo, nie? Ale celý bod na fronte že hlava môže skutočne dynamicky mení v závislosti na tom, kde sme Chcete začiatku našej q byť, a ako taký, chvosta je tiež zmení. 

A tak si predstaviť, že to nie je fronty, ale skôr je to frontu. Povedzme, že hlava je tu. Povedzme, že naše front vyzerala takto. Ak by sme chceli posunúť kde na začiatku linky je, povedzme, že sme sa posunul hlavou Týmto spôsobom a tu veľkosti. 

Teraz chceme niečo pridať Táto fronta, ale ako vy môžete vidieť, to nie je tak jednoduché, ako len pridať to, čo je za veľkosťou pretože potom dôjdu medze našej aktuálnej poľa. Kam chceme naozaj pridať je tu. To je krása fronty je to, že pre nás, vizuálne vyzerá ako linka ide takto, ale ak sú uložené v dátovej štruktúre, dávajú to ako ako cyklus. Je to druh obaľuje na prednej strane rovnaký spôsobom že vedenie môže tiež zábal okolo závisí na všade tam, kde vás chcú začiatku riadku byť. A tak ak budeme trvať pozrite sa sem dole, poďme že sme chceli vytvoriť Funkcia tzv čakací. Chceli sme pridať int n do tohto q. Ak q.size q-- budeme hovoriť, že naše dáta structure-- keď náš queue.size nie je sa rovná kapacity, alebo ak je to menej ako kapacita, q.strings je pole v našom q. Budeme nastaviť rovnajúcu sa q.heads, ktorý je tu, a navyše q.size modul kapacitou, ktorý zábal nás naspäť tu. 

Takže v tomto príklade, index hlavy je 1, že jo? Index veľkosti je 0, 1, 2, 3, 4. Takže môžeme urobiť 1 plus 4 modul našej kapacity, ktorá je 5. Čo, že nám dá? Čo je index, ktorý vychádza z toho? 

Divákov: 0. 

ANDI PENG: 0, čo sa stane byť tu, a tak chceme byť schopní vložiť do práve tu. A tak táto rovnica tu druh z práve pracuje s číslami V závislosti na tom, kde vaše hlava a vaše veľkosť sú. Ak viete, čo tie, veci sú, viete, presne tam, kde chcete vložiť čo je po vašom frontu. Znamená to, že zmysel pre všetkých? 

Viem, že akýsi mozgu teaser najmä preto, že prišiel v dôsledku vášho kvíz. Ale dúfajme, že všetci Teraz môžete pochopiť, prečo toto riešenie, alebo to Funkcia je tak, že to je. Každý, kto trochu nejasné na to? OK. 

A tak teraz, ak ste chcel dequeue, to je miesto, kde by naša hlava sa presúva pretože ak by sme mali dequeue, neberieme z konca q. Chceme, aby sa z hlavy, že jo? Takže v dôsledku toho hlava sa zmení, a to je dôvod, prečo, keď sa Zaradí, musíš sledovať kde sa vaša hlava a vaše veľkosť sú, aby bolo možné vložiť do správnej polohy. 

A tak keď sa dequeue, Tiež som pseudokód to. Neváhajte a ak chcete, pokúsiť kódovanie to. Chcete presunúť hlavu, nie? Keby som chcel dequeue, I by sa posunúť hlavu nad. To by byť hlava. 

A náš súčasný veľkosť by odčítanie, pretože už nie je majú štyri prvky v poli. Máme len tri, a potom chceme vrátiť, čo bol uložený vo vnútri hlavy, pretože chceme, aby sa tento hodnota sa tak veľmi podobný zásobníku. Len ste pri z iného miesta, a vy budete musieť priradiť svoju ukazovateľ na inom mieste ako výsledok. Logicky, každý nasledovať? Skvelé. 

OK, takže budeme hovoriť trochu viac do hĺbky asi spojových zoznamoch pretože bude veľmi, veľmi cenná pre vás v priebehu roka tento týždeň psets. Spojové zoznamy, ako ste chlapci Pamätám si, všetko, čo sú sú uzly, ktoré sú uzly isté Hodnoty oboch hodnotu a ukazovateľ , Ktoré sú spojené dohromady týmito ukazovateľmi. A tak sa na to, ako struct sme sa vytvoriť uzol tu je, že sme majú int n, čo je čokoľvek hodnota v obchode alebo reťazca n alebo čo chcete hovoria, char hviezda n. Uzol struct hviezda, čo je ukazovateľ ktoré chcete mať v každom uzle, budete mať, že Ukazovateľ bod k ďalšej. Budete mať hlavu prepojeného zoznamu, ktorý je bude poukázať na zvyšku hodnoty tak ďalej a tak ďalej kým sa nakoniec dostanete na koniec. A to je len posledný uzol bude to mať ukazovateľ. Bude to poukázať na null, a to je, keď viete, že ste hit koniec vášho zoznamu Google je, keď vaše posledný ukazovateľ neukazuje na nič. 

Tak sme sa chystáte ísť trochu viac do hĺbka ohľadom toho, ako by človek možná vyhľadávať prepojeného zoznamu. Pamätajte si, aké sú niektoré z nevýhody prepojených zoznamov verše pole o vyhľadávanie. Pole môžete binárne vyhľadávanie, ale prečo nemôžete urobiť, že v Google zozname? 

Divákov: Vzhľadom na to, že sú všetci pripojení, ale nemáte dosť vedieť, kde [Nepočuteľný]. 

ANDI PENG: Jo, presne tak si pamätajte: že brilancie pole bola skutočnosť, že sme mali pamäť s priamym prístupom, kde keby som chcel hodnotu z indexu šesť, mohol by som len povedať index šesť, daj mi túto hodnotu. A to preto, že pole sú radené v súvislom priestore pamäti na jednom mieste, vzhľadom k tomu, druh spojových zoznamov sú náhodne striedajú všade okolo, a jediný spôsob, ako môžete nájsť jeden je cez ukazovateľ, ktorý vám povie, adresa, kde, že budúci uzol je. 

A tak ako výsledok, jediný spôsob, ako prehľadávať prepojenom zoznamu je lineárna hľadanie. Pretože ja presne neviem, kde 12. hodnota v Google zozname je, Musím prejsť celistvosť tohto prepojeného zoznamu jeden jeden z hlavy do prvého uzla, do druhého uzla, na tretiu uzla, celú cestu dole, až som sa konečne dostanem kde uzol Zháňam je. A tak v tomto zmysle, hľadanie v Google zozname je vždy n. Je to vždy n. Je to vždy v lineárnom čase. 

A tak sa kód, v ktorom realizujeme to, a to je trochu nový pre vás, pretože ste chlapci sa naozaj hovorili, alebo vôbec ukazovatele vidieť v tom, ako sa prehľadávať ukazovateľov, takže budeme prechádzať táto veľmi, veľmi pomaly. Takže bool vyhľadávania, vpravo, poďme si predstaviť, chceme vytvoriť funkciu nazvanú Hľadania, ktorý vracia true ak ste našli hodnote vnútri spojené vypísať, a vracia false inak. Uzol hviezda zoznam je V súčasnej dobe len ukazovateľ na prvú položku vo vašom Google zozname. int n je hodnota, ktorú ste hľadanie v tomto zozname. 

Takže uzol hviezda ukazovateľ rovná zoznam. To znamená, že sme nastavenie a vytvorenie ukazovatele do tohto prvého uzla vnútri zoznamu. Každý, kto so mnou? Takže ak by sme mali ísť späť, musel by som inicializovať ukazovateľ, ktorý odkazuje na hlava, čo tento zoznam. 

A potom, akonáhle sa dostanete tu zatiaľ čo ukazovateľ nerovná null, tak, že je slučka, v ktorej sú bude následne kríženie zvyšok nášho zoznamu pretože to, čo sa stane, keď ukazovateľ rovná null? Vieme, že sme have-- 

Divákov: [Nepočuteľné] 

ANDI PENG: Presne, takže vieme, že sme došli na koniec zoznamu, je to tak? Ak sa vydáte späť, každý uzol musí smerovať do iného uzla a tak ďalej a tak ďalej kým nenarazíte nakoniec chvost vášho Google zoznamu, ktorý má ukazovateľ, ktorý práve neukazuje inde ako žiadny. A tak ste v podstate viete, že váš zoznam je tu stále hore kým ukazovateľ nerovná null, pretože akonáhle sa rovná null, viete, že nie je viac vecí. 

Tak, že je slučka, v ktorej sme bude mať aktuálne vyhľadávania. A v prípade, že pointer-- vidíš že druh šípky tam funkcie? Takže ak ukazovateľ ukazuje na n, ak ukazovateľ v n rovná sa rovná n, tak, že znamená, že pokiaľ ukazovateľ, že ste vyhľadávanie na konci každého Uzol je vlastne rovná hodnote hľadáte, potom sa chcete vrátiť hodnotu true. Takže v podstate, ak ste na uzle, ktorý má hodnotu, ktorú hľadáte, viete, že ste boli schopní úspešne vyhľadávať. 

V opačnom prípade, že chcete nastaviť ukazovateľ na ďalšie uzol. To je to, čo tento riadok je tu robí. Ukazovateľ sa rovná ukazovateľ ďalšie. Všetci vidieť, ako to funguje? 

A v podstate budete len prejsť celistvosť zoznamu, resetovanie ukazovateľ zakaždým, kým budete nakoniec narazí na koniec zoznamu. A viete, že neexistujú žiadne viac uzlov prehľadávať, a potom môžete return false pretože viete, že, oh, no, ak som bol schopný vyhľadávať cez celé zoznamu. Ak by v tomto príklade, keby som chcel hľadať na hodnotu 10, I a začať v čele, a Aj hľadanie celú cestu dole, a nakoniec som sa dostal k tomu, ktorý ukazovateľ, ktorý poukazuje na hodnotu null, Viem, že, blbosť, myslím, že 10 nie je v Tento zoznam preto, že som nemohol nájsť. A ja som sa na konci zoznamu. A v takom prípade viete, Chystám sa vrátiť false. 

Nech že máčať v pre trochu. To bude dosť dôležité pre vašu pset. Logika je to veľmi jednoduché, snáď syntakticky len jej vykonávaní. Vy chcete, aby Uistite sa, že rozumiete. Super. 

OK, tak ako by sme boli vkladanie uzlov, vpravo, do zoznamu, pretože pamätať aké sú to, čo výhod mať prepojeného zoznamu oproti poľa, pokiaľ ide o skladovanie? 

Divákov: Je to dynamický, takže je to jednoduchšie, to-- 

ANDI PENG: Presne tak, tak je to dynamický, ktorý znamená, že sa môže rozšíriť a zmenšiť V závislosti na potrebách užívateľa. A tak, v tomto zmysle, nepotrebujeme strácať zbytočne pamäť, pretože som keď neviem, koľko hodnôt Chcem skladovať, to nemá zmysel pre mňa vytvoriť pole z nasledujúcich dôvodov keď chcem uložiť 10 hodnôt a ja sa vytvoriť rad 1000, to je veľa nevyužité pamäte, pridelené. To je dôvod, prečo chceme použiť prepojený zoznam, aby bolo možné dynamicky zmeniť alebo zmenšiť našu veľkosť. 

A tak to robí vkladanie trochu zložitejšie. Vzhľadom k tomu, nemôžeme náhodne prístup k prvkom tak, že by sme z poľa. Ak chcem vložiť prvok do siedmej indexu Len som si ju vložiť do siedmej indexu. V prepojenom zozname, to nie je pomerne pracovať tak ľahko, a tak ak by sme chceli vložiť ten tu v Google zozname, vizuálne, je to veľmi dobre vidieť. Chceme len, aby ho vložiť priamo tam, hneď na začiatku zoznamu, hneď po hlave. 

Ale spôsob, akým musíme preradiť Ukazovatele sa trochu spletitý alebo, logicky, to dáva zmysel, ale chcete, aby sa ubezpečil, že to máte úplne dole, pretože to posledné, čo chcete, je priradiť ukazovátka tak, že tu robíme. Ak vás dereferencia ukazovateľ od hlavy až k 1, potom zrazu The zvyšok vášho Google zoznamu je stratené, pretože ste nie je vlastne vytvorili dočasný čokoľvek. To ukázal na 2. Ak priradenie ukazovateľ, potom sa zvyšok vášho zoznamu je úplne stratený. Takže vy chcete byť veľmi, veľmi opatrný tu najprv priradiť ukazovateľ z akéhokoľvek vás chcete vložiť do kamkoľvek chceš, a potom vás môže dereferencia zvyšok vášho zoznamu. 

Tak to platí pre kdekoľvek snažíte vložiť do. Ak chcete vložiť u hlava, ak chcete odpovedať na tú, ak chcete vložiť na koniec, no, nakoniec som sa Asi by ste práve nemajú žiadny ukazovateľ, ale vy chcete, aby sa ubezpečil, že nemáte stratiť zvyšok zoznamu. Vždycky chcete byť istý, Váš nový uzol smeruje smerom k čo chcete vložiť do, a potom môžete pridať zreťazenie ďalej. Všetci jasné? 

To bude jeden zo skutočných problémov. Jedným z najviac hlavných problémov budete mať na svojom pset je to, že budete snažiť vytvoriť prepojený zoznam a vložiť veci ale potom len stratiť zvyšok svojho Google zoznamu. A ty budeš rád, ja Neviem, prečo sa to deje? A je to bolesť prejsť a hľadať všetky vaše ukazovateľov. 

A ja vám zaručiť, na tomto pset, písanie a kreslenie týchto uzlov out bude veľmi, veľmi užitočné. Takže si môžete úplne sledovať kde všetky vaše ukazovatele sú, čo sa deje zle, kde sa všetky vaše uzly sú, to, čo musíte urobiť, aby prístup alebo vložiť alebo odstrániť, alebo niektorý z nich. Všetci dobre s tým? Super. 

Takže ak sme chceli pozrieť na kód? Oh, ja neviem, či my môžete vidieť the-- OK, tak V hornej rade je to je funkcia menoval vložka tam, kde chceme vložiť int n do prepojeného zoznamu. Chystáme sa prejsť to. Je to veľa kódu, veľa novú syntaxou. Budeme v poriadku. 

Tak sa v hornej časti, ak je to chceme vytvoriť niečo čo musíme urobiť, najmä ak ste chcete, aby to nemalo byť uložený v zásobníku ale v halde? Ideme do malloc, že ​​jo? Takže budeme vytvoriť ukazovateľ. Uzol, ukazovateľ, nové rovná malloc veľkosť uzla pretože chceme, aby uzol, ktorý bude vytvorený. Chceme, aby množstvo pamäť, ktorá uzol zaberá majú byť pridelené pre vytvorenie nového uzla. 

A potom budeme skontrolovať, uvidíme, či nová rovná sa rovná null. Spomeňte si, čo sme si povedali? Či už vás malloc, Čo musíte vždy urobiť? Vždy musíte skontrolovať, či to je null. 

Napríklad, ak váš operačný Systém bol úplne plný, ak ste mali na nie viac pamäte všetky a skúste malloc, že sa vráti null pre vás. A tak ak sa pokúsite použiť keď to bolo ukázal na null, vy nebudete schopní na prístup k týmto informáciám. A tak ako taký, chceli sme, aby sa istí, že vždy, keď ste mallocing, ste vždy skontrolovať, či že pamäť daný pre vás je null. A ak to tak nie je, potom sa môžeme presunúť so zvyškom nášho kódu. 

Takže budeme inicializovať nový uzol. Chystáme sa urobiť nový n sa rovná n. A potom budeme robiť nastaviť nový ukazovateľ na nové na NULL, pretože práve teraz my nie chcú niečo pre to, aby ukazoval na. Nemáme tušenie, kde to bude, aby vám, a ak chceme vložte ho v čele, potom môžeme priradiť ukazovateľ na hlave. Má každý sledovať logiku kde že sa to deje? 

Všetko, čo robíte, je vytvorenie nového uzol, nastavenie ukazovateľ na null, a potom priradenie to do hlavy, keby sme viete, chceme vložiť do čela. A potom hlava sa chystá ukazovať smerom k tomuto novému uzla. Každý, kto s tým OK? 

Takže je to dvojstupňový proces. Musíš Najprv priraďte čo budete vytvárať. Nastaviť že ukazovateľ odkazovať, a potom vás môže druh dereferencia prvý ukazovateľ a prejdite na nový uzol. Všade tam, kde ju chcete vložiť, že logika bude platiť. 

Je to niečo ako priradenie dočasné premenné. Pamätajte si, že máte aby sa uistil, že vás nestrácajú prehľad o ak ste swapovanie. Chcete, aby sa uistil, že máte dočasná premenná, ktorá druh udržuje sledovať, kde tej veci je uložená tak, že nestratili žiadnu hodnotu v priebehu ako sa pohrávate s ním. 

OK, takže tu bude kód. Vy sa pozrieť po bode. Bude to tam. 

Takže si myslím, ako sa to sa líši, ak by sme chceli vložiť do stredu alebo na konci? Má niekto má predstavu o tom, čo je to pseudokód ako logické referencie že by sme trvať, ak by sme chceli ho vložiť do stredu? Takže ak by sme chceli vložiť u hlava, všetko, čo urobiť, je vytvoriť nový uzol. Nastavili sme ukazovateľ, ktorý Nový uzol sa to bez ohľadu na hlave, a potom sme sa nastaviť hlavu do nového uzla, že jo? Ak by sme chceli vložiť do stredu zoznamu, čo by sa musíme urobiť? 

Divákov: To by ešte byť podobný proces ako sa priradenie ukazovatele, potom priradí tento ukazovateľ, ale museli by sme tam nájsť. 

ANDI PENG: Presne tak, presne rovnaký proces okrem vás musieť nájsť, kde presne ste chcete, aby nový ukazovateľ ísť do, takže ak chcem vložiť do uprostred spojené list-- OK, povedzme, že je to naša previazaný zoznam. Ak chceme ho vložiť priamo tu, budeme vytvoriť nový uzol. Ideme do malloc. Chystáme sa vytvoriť nový uzol. Budeme priradiť ukazovateľ tohto uzla tu. 

Avšak problémom, ktorý sa líši od miesta, kde je hlava je, že sme presne vedeli, kde je hlava. To bolo hneď na začiatku, že jo? Ale tu musíme sledovať kde sme vložením do. Sme chcete vložiť naše uzol tu, máme aby sa uistil, že človek predchádzajúce do tohto uzla je ten, ktorý priraďuje ukazovateľ. Takže potom budete musieť trochu sledovať dve veci. Ak máte sledovať, kde to uzol je v súčasnej dobe vloženie do. Musíte tiež sledovať, kde predchádzajúci uzol, ktorý sa pozeráte bol tiež tam. Všetci dobre s tým? OK. 

Ako sa o vložení do konca? Keby som chcel pridať here-- keby som chcel pridať nový uzol na koniec zoznamu, Ako by som mohol ísť o tom, že? Publikum: Takže v súčasnej dobe je posledný, kto sa ukázal na null. ANDI PENG: Jo. Presne, takže tento raz V súčasnej dobe je orientované na vedieť, a tak myslím, že v tomto zmysle, že je to veľmi ľahko pridať na koniec zoznamu. Jediné, čo musíte urobiť, je nastaviť rovná null a potom boom. Presne tam, veľmi jednoduché. Veľmi jednoduché. 

Veľmi podobné hlava, ale logicky vás chcete, aby sa ubezpečil, že kroky užívate k robí niečo z toho, ste po pozdĺž. Je to veľmi jednoduché, v stredu vášho kódu, uviaznu na, oh, mám toľko ukazovateľov. Ja neviem, kde niečo ukazuje. Ja ani neviem, ktorý uzol, že som ďalej. Čo sa deje? 

Relax, upokoj sa, zhlboka sa nadýchnuť. Nakreslite si svoje prepojeného zoznamu. Ak poviete, ja viem, kde presne Musím vložiť to do a viem presne, ako zmeniť priradenie my ukazovatele, oveľa, oveľa jednoduchšie na obrázok out-- oveľa, oveľa jednoduchšie, že nebude stratiť v chybách v kóde. Každý, kto s tým OK? OK. 

Takže si myslím, koncept, že sme sa naozaj hovoril o skôr, a myslím, že vás najskôr nie je dôjde oveľa yet-- je to celkom pokročilé concept-- je to, že sme vlastne majú údaje štruktúra volal dvojnásobne prepojeného zoznamu. Tak ako vy môžete vidieť, všetko, čo robíte, je vytvorenie skutočné hodnoty, navyše Ukazovateľ na každej z našich uzlov ktorá tiež poukazuje na predchádzajúcu uzla. Takže nielen že máme svoje uzly poukazujú na ten budúci. Poukazujú tiež na predchádzajúce. Budem ignorovať aj týchto dvoch práve teraz. 

Takže máte reťaz ktoré sa môžu pohybovať oboma smermi, a potom je to trochu jednoduchšie logicky nasledovať. Rovnako ako tu, miesto sledovanie z, oh, ja musí vedieť, že tento uzol ten, ktorý mám k preradeniu, Môžem jednoducho ísť sem a stačí vytiahnuť predchádzajúce. Potom som presne vedieť, kde že je, a potom vás Nemusíte sa prejsť celistvosť Google zoznamu. Je to trochu jednoduchšie. 

Ale ako taký, budete mať dvojnásobne množstvo ukazovateľov, To je dvojnásobok pamäte. Je to veľa ukazovateľov sledovať. Je to trochu zložitejšie, ale je to trochu viac užívateľsky prívetivé závislosti na to, čo sa snažíte dosiahnuť. 

Takže tento druh údajov Štruktúra úplne existuje, a štruktúra je veľmi, veľmi jednoduché, s výnimkou všetko máte, je, namiesto iba ukazovateľ na ďalšie, máte tiež ukazovateľ na predchádzajúcu. To je všetko, bol rozdiel. Všetci dobre s tým? Super. 

Dobre, takže teraz som naozaj stráviť pravdepodobne ako je 15 až 20 minút alebo objemu zvyšku času v sekcii hovorí o hash tabuliek. Koľko z vás Prečítal pset5 spec? Dobre, dobre. To je vyššia ako 50% za normálnych okolností. Je to v poriadku. 

Tak ako vy uvidíte, ste výzvou pset5 bude vykonávanie slovník kde si nahrať cez 140.000 slov že sme vám kontrolu pravopisu to proti všetkým textu. Dáme vám náhodné kusy literatúry. 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 vo všetkých z týchto slovníkov v podstate s našou kontrolou pravopisu. A tak je tu niekoľko dielov vytvorenie tohto pset, Prvý chcete byť schopný skutočne načítať všetky slová do vášho slovník, a potom vás chcú byť schopní pravopisu skontrolovať všetky z nich. A tak ako taký, budete požadovať dátová štruktúra, ktorá môže robiť to rýchlo a efektívne a dynamicky. 

Takže myslím, že najjednoduchšie spôsob, ako to urobiť, by pravdepodobne vytvorenie poľa, nie? Najjednoduchší spôsob skladovania je vám môže vytvoriť rad 140,000 slov a len ich všetky umiestniť tam a potom prejsť im binárne vyhľadávanie alebo výberov či ne-- Ospravedlňujem sa, že sa triedenie. Môžete ich triediť a potom prejsť je binárne vyhľadávanie, alebo len lineárne hľadanie a len záverečné slová, ale že berie obrovské množstvo pamäte, a to nie je príliš efektívne. 

A tak sme sa chystáte začať hovorí o spôsoboch, ktorými sa Naša doba chodu efektívnejšie. A naším cieľom je dostať konštantný doba, kedy je to skoro ako pole, kde máte okamžitý prístup. Keby som chcel hľadať čokoľvek, Chcem byť schopný len, boom, nájsť presne to, a vytiahnite ju von. A tak sa štruktúra, v ktorej budeme stále veľmi blízko aby bolo možné získať prístup konštantný čas, tento svätý grál v programovaní konštanty Čas sa nazýva hash tabuľky. A tak Dávid už skôr zmienil o [Nepočuteľný] trochu v prednáške, ale budeme skutočne ponor v hlbokej tento týždeň na kus, ktorý je, ak ide o ako hash tabuľky funguje. 

Tak tak, že hash tabuľka práce, napríklad, keby som chcel uložiť množstvo slovami, banda slov v anglickom jazyku, Mohol by som teoreticky dať banán, jablko, kivi, mango, pár, a cantaloupe všetko len na maticu. Všetky by mohli zapadnúť a bude nájsť. Bolo by druh bolesti prehľadávať a prístupu, ale jednoduchší spôsob, ako to dosiahnuť, je že môžeme vytvoriť vlastne štruktúra nazýva hash tabuľky, kde sme hash. Vedieme všetky naše kľúčov prostredníctvom funkcia hash, rovnice, že zmení ich všetky do nejaký hodnotu že potom môžeme ukladať na v podstate pole prepojeného zoznamu. 

A tak tu, ak by sme chceli ukladať anglické slová, sme mohli potenciálne jednoducho, ja nie Viete, vypnite všetky prvé písmená do nejakého druhu čísla. A tak napríklad, keď som chcel A byť synonymom apple-- alebo s indexom 0, a B synonymom s 1, môžeme mať 26 záznamov ktorý môže len uložiť všetky písmená abeceda, že začneme s. A potom môžeme mať apple v indexe od 0. Môžeme mať banán na indexe 1, ananásový melón na indexe 2, a tak ďalej a tak ďalej. A tak, keď som sa chcel vyhľadávať môj hash stôl a prístup jablko, Viem, že jablko začína à, a viem presne, že to musí byť a hash Tabuľka na indexe 0 Pretože je funkcie skôr priradená. 

Takže ja neviem, my sme užívateľský program, kde budete obvinený arbitrarily-- nebolo svojvoľne, sa snaží zamyslene myslieť na dobré rovníc aby bolo možné rozšíriť mimo všetky svoje hodnoty takým spôsobom, že môžu ľahko získať prístup to neskôr sa ako rovnica že vy, sami, vieš. Takže v tom zmysle, či by som chcel ísť do mango, ja viem, oh, začína m. To musí byť v indexe 12. Nemám prehľadávať čokoľvek. Viem, že exactly-- som mohol len ísť do index 12 a vytiahnite to von. 

Každý jasne o tom, ako hashovacie funkcie tabuľky funguje? Je to tak trochu len zložitejšie poľa. To je všetko, čo je. OK. 

Takže myslím, že narazíme táto otázka toho, čo sa stane, keď máte viac vecí že vám rovnaký index? Tak hovoria naši funkciu, všetci to urobil, bolo, prijať, že prvé písmeno a meniť na Príslušná 0 až 25 index. To je úplne v poriadku, ak máte iba jeden z každého z nich. Ale druhá začnete ktoré majú viac, že ​​ste bude mať, čo sa nazýva kolízie. 

Takže keď sa snažím vložiť pochovať do hash tabuľka, ktorá už má banán na tom, čo sa stane, keď pokusu o vloženie, že? Zlé veci preto, že banán Už v rámci indexu existuje že chcete uložiť ho do. Berry druh je ako, ehm, čo mám robiť? Neviem, kam ísť. Ako môžem vyriešiť? 

A tak si chlapci bude druh pozri robíme tejto chúlostivej veci kde môžeme trochu vlastne Vytvorenie prepojeného zoznamu v našich poliach. A tak najjednoduchší spôsob premýšľať o tom, všetky hash tabuľka je rad spojových zoznamov. A tak, v tomto zmysle, máte toto krásne pole ukazovateľov, a potom každý ukazovateľ v že hodnota tohto indexu, môže skutočne ukazovať na iné veci. A tak budete mať všetky tieto oddelené reťaze spadnutie jedného veľkého poľa. 

A tak tu, keď som chcel vložiť bobule, Ja viem, v poriadku, budem vstup to cez môj hash funkcie. Chystám sa skončiť s indexom 1, a potom budem mať možnosť len menšie podmnožina toto obrie 140000-slovo slovníka. A potom som si len pozerať prostredníctvom 1/26 toho. 

A tak som si len vložiť bobule buď pred alebo po banány v tomto prípade? Po, že jo? A tak budete chcieť vložiť tento uzol po banán, a tak budete vkladať na chvoste tohto prepojeného zoznamu. Chystám sa vrátiť späť k tomuto predchádzajúcemu snímky, tak vy môžete vidieť, ako hash funkcia pracuje. 

Takže hash funkcia je táto rovnica že vediete druh váš vstup až sa dostať čo index Ak chcete ju priradiť k. A tak, v tomto prípade všetko, čo sme chceli urobiť, bolo vziať prvé písmeno, obrátiť, že do indexu, potom sme možno uložiť, že v našom hash funkcie. Všetko, čo tu robíme, je, že sme konverziu prvé písmeno. Takže keykey [0] je len prvé písmeno akéhokoľvek string budeme mať, sme odovzdaním. Sme konverziu, že pre horný, a sme sa odpočíta od veľkými písmenami A, takže všetko, čo robí nám dáva číslo v ktorom môžeme hash naše hodnoty na. 

A potom budeme návrat hash modulu veľkosti. Buďte veľmi, veľmi opatrní preto, že teoreticky, tu Váš hash hodnota mohla byť nekonečná. Mohlo by to jednoducho ísť ďalej a ďalej a ďalej. Mohlo by to byť nejaké naozaj, Naozaj veľké hodnoty, ale preto, že vaše hash tabuľky, ktoré ste vytvorili má iba 26 indexy, chcete uistite sa, že modulusing takže nie run-- je to to isté vec ako queue-- takže nemusíte spúšťať off Spodná časť vášho hash funkcie. 

Chcete zabaliť späť okolo rovnakým spôsobom v [nepočuteľných], keď ste mal ako veľmi, veľmi veľké písmeno, vy nechcel, aby stačí spustiť až na koniec. To isté tu, chcete byť istý, nebeží z konca obalom okolo hornej časti tabuľky. Tak to je len veľmi jednoduchá funkcie hash. Všetko, čo urobila, bolo vziať ako prvý List z akéhokoľvek nášho vstupu bola a meniť na index, ktorý sme mohli dať do našej tabuľky hash. 

Jo, a tak ako som povedal predtým, tak, že sme sa vyriešiť kolízií v našej hash tabuliek majú, To, čomu hovoríme, reťazenie. Takže ak sa pokúsite vložiť viac slová, ktoré začínajú rovnakú vec, budete mať jednu hodnotu hash. Avokádo a jablko, ak ste spustite ho cez naše hash funkcie, Chystáte sa vám dať Rovnaké číslo, počet 0. A tak spôsob, ako vyriešiť to je že môžeme vlastne trochu prepojiť spoločne prostredníctvom spojových zoznamov. 

A tak v tomto zmysle, vy môžete vidieť druh o tom, ako dátové štruktúry, ktoré sme sa nastaviť skôr ako hrozienkami spojený so zoznamom druhu z môže prísť spoločne do jedného. A potom si môžete vytvoriť ďaleko účinnejšie dátové štruktúry ktorý zvládne väčšie množstvo Dáta, ktoré dynamicky meniť veľkosť v závislosti na vašich potrebách. Všetci jasné? Každý druh clear o tom, čo sa tu deje? 

Keby som chcel insert-- čo je to ovocie, ktoré začína, ja neviem, B, iné ako Berry, banán. 

Divákov: Blackberry. 

ANDI PENG: Blackberry, Blackberry. Kam blackberry ísť sem? No, my vlastne nie sú triedené to ešte, ale teoreticky Ak by sme chceli mať túto v abecednom poradí, kam by mal ísť BlackBerry? 

Divákov: [Nepočuteľné] 

ANDI PENG: Presne, po tú, že jo? Ale pretože je to veľmi ťažké reorder-- Myslím, že je to na vás chlapci. Vy môžete úplne implementovať, čo chcete. Čím viac účinný spôsob ako to urobiť snáď by bolo zoradiť spojené vypísať do abecednom poradí, a tak, keď ste vkladanie vecí, budete chcieť si byť istí, o ich zaradenie do abecednom poradí takže potom, keď ste snažia sa ich hľadať, nemusíte prejsť všetko. Viete presne, kde to je, a je to jednoduchšie. 

Ale ak máte trochu veci poprekladané náhodne, ste stále bude mať to prechádzať tak ako tak. A tak, keď som sa chcel len vložiť blackberry tu a ja som chcel hľadať to, ja viem, oh, ostružina musí začínať s indexom 1, a tak som viem, okamžite stačí hľadať na 1. A potom som si trochu prechádzať prepojeného zoznamu kým sa na BlackBerry, a then-- jo? 

Divákov: Ak sa snažíte create-- Myslím, že takto je to veľmi jednoduchý hash funkcie. A ak by sme chceli robiť viac vrstiev, ktorí radi, OK, chceme rozdeliť na rovnako ako všetky znaky abecedy a potom zase rád iný súbor abecedných písmen v rámci, ktorý, sme uvedenie ako hash Tabuľka v hash tabuľky, alebo ako funkcia v rámci funkcie? Alebo je that-- 

ANDI PENG: Takže vaše hash function-- vaše hash tabuľky môže byť tak veľký, ako chcete, aby to. Takže v tomto zmysle, myslel som, to bolo veľmi jednoduché, veľmi jednoduché pre mňa proste tak nejako na báze listov z prvé slovo. A tak je tu len 26 možností. Môžem len dostať 26 z možností 0 až 25, pretože sa môže iba začať od A do Z. Ale Ak by ste chceli pridať, možno viac zložitosti alebo rýchlejší beh času, aby svoj hash tabuľky, si absolútne môžete robiť všetky druhy vecí. Môžete si vytvoriť svoj vlastný rovnice, ktorá vám dáva viac rozdelenie vo vašom slová, potom pri vyhľadávaní, že to bude rýchlejšie. 

Je to úplne na vás chlapci ako chcete implementovať to. Myslite na to, ako len vedierka. Ak by som chcel mať 26 vedierka, idem triediť veci do týchto vedierka. Ale ja budem mať veľa vecí v každom vedre, takže ak chcete, aby to rýchlejšie a efektívnejšie, dovoľte mi, aby som sto vedierka. 

Ale potom budete musieť prísť na to, spôsob, nechajte tak, aby boli v správnom vedra, ktoré by mali byť v. Ale potom, keď ste vlastne Chcete sa pozrieť na tom vedierko, je to oveľa rýchlejšie, pretože tam je menej veci v každom segmente. A tak, jo, to je vlastne trik pre vás v pset5 je to, že budete vyzvaní, aby len vytvoriť čo je najúčinnejší funkcie si môžete myslieť, že je schopná ukladať a kontrolovať tieto hodnoty. 

Úplne na vás chlapci však budete chcieť robiť to, ale to je naozaj dobrý bod. Že druh logiky vy chcú začať premýšľať o Je dobre, tak prečo nie ja robiť viac vedierka. A potom som musel hľadať menej vecí, a potom možno ja majú iný hash funkcie. 

Jo, je tu mnoho spôsobov, ako to dosiahnuť pset, niektoré sú rýchlejšie ako ostatné. Ja úplne bude len vidieť, ako rýchla bol najrýchlejší chlapci budú byť schopní dostať svoje funkcie do práce. OK, všetci dobre na PREPOJENIE ZÁSOB a hashovacie tabuľky? Je to vlastne ako veľmi jednoduchý koncept, ak si myslíte o tom. Všetko, čo to je, je oddeľovanie čokoľvek vaše vstupy sú do vedier, ich triedenie, a potom vyhľadávanie vo uvádza, že je spájaný s. 

Super. Dobre, teraz máme iný druh dátové štruktúry, ktoré sa hovorí strom. Poďme ďalej a hovorí o pokusoch , Ktoré sú zreteľne odlišné, ale v rovnakej kategórii. V podstate, všetci strom je miesto organizovanie dát v lineárne že hash tabuľka vám does-- viem, je to má hornú a spodnú časť a potom tak nejako prepojiť preč to-- na Strom má hornú ktorý nazývate koreň, a potom to má listy všetko okolo neho. 

A tak všetko, čo tu je len na najvyššej uzol , Ktorý odkazuje na iných uzlov, ktoré body na viac uzlov, a tak ďalej a tak ďalej. A tak stačí štiepanie vetiev. Je to len iný spôsob organizácie dát, a pretože sme to strom volanie, vy jen-- je to len modelovaný von vyzerať ako strom. To je dôvod, prečo hovoríme, že stromy. 

Hash tabuľka vyzerá ako tabuľky. Strom len vyzerá ako strom. Všetko, čo to je, je samostatná spôsob organizácie uzlov V závislosti na aké sú vaše potreby. 

Takže máte koreň a potom máte listy. Spôsob, akým môžeme obzvlášť premýšľať o tom, že je to binárny strom, binárny strom je len Špecifickým typom stromu kde každý uzol len body k, pri max, ďalšie dva uzly. A tak tu máte odlišný symetria vo vašom strome že uľahčuje druh vyzerať na aké hodnoty ste, pretože potom vás majú vždy ľavý alebo pravý. Tam je nikdy ako ľavé tretinu ľavá alebo štvrtiny z ľavej strany. Je to len máte doľava a právo a môžete vyhľadávať buď z týchto dvoch. A prečo je to užitočné? Spôsob, akým je užitočné, je ak hľadáte prehľadávať hodnotám, že jo? Skôr než sa vykonáva binárne hľadať v chybovej poli, ak by ste chceli mať možnosť vložiť uzly a odniesť uzly na vôli a tiež zachovať vyhľadávanie kapacity binárne vyhľadávanie. Takže týmto spôsobom, sme trochu Pamätám si, keď sme tricking-- povedal spojové zoznamy nemôžu binárne hľadanie? Sme trochu vytvorenie dátovej štruktúry že triky, ktoré do práce. 

A to preto, spojové zoznamy sú lineárne, oni len prepojiť jeden po druhom. Môžeme mať trochu iný druh ukazovateľov tento bod na rôzne uzly že nám môže pomôcť s vyhľadávaním. A tak tu, keby som chcel majú strom binárneho vyhľadávania, Viem, že moje druhé, ak 55. Ja som jednoducho ísť k vytvoreniu, že ako môj stredu, ako môj koreň, a potom budem mať Hodnoty spin off z toho. 

Tak tu, ak budem hľadať hodnotu 66, môžem začať na 55 rokov. To je 66 vyšší ako 55? Áno, je to, takže viem, že mus hľadať i n pravý ukazovateľ tohto stromu. Chodím do 77. OK, je menšia ako 66 alebo väčší ako 77? To je menej ako, takže viete, oh, , Ktorý má byť na ľavej strane uzla. 

A tak tu máme trochu konzervovanie všetky z veľkých vecí, o poli, tak ako dynamickú zmenu veľkosti objektov, pričom môcť vkladať a mazať na vôli, bez toho aby sa museli starať o fixné množstvo priestoru. Stále sme zachovať všetky tie úžasné veci a zároveň je schopný sa zachovala log a hľadanie času binárne vyhľadávanie že sme iba skôr možnosť získať frázu. 

Pohode dátová štruktúra, druh vykonávaní zložité, uzol. Ako môžete vidieť, všetky to je struct uzla je to, že máte vľavo a pravý ukazovateľ. To je všetko, čo je. Takže skôr než len majúci x alebo predchádzajúci. Máte doľava alebo doprava a môžete trochu prepojiť dohromady Avšak sa tak rozhodnete. 

OK, sme vlastne bude len trvať niekoľko minút. Takže budeme vrátiť sa sem. Ako som už povedal skôr, Tak nejako som vysvetlil, logika, ako by sa hľadať cez to. Budeme sa snažiť pseudocoding na to vidieť, ak môžeme trochu použije Rovnaká logika binárneho vyhľadávania na iný typ dátové štruktúry. Ak si chlapci chcú, aby sa ako pár minút, len premýšľať o tom. OK. Dobre, budem vlastne len aby vám the-- nie, budeme hovoriť o pseudocode ako prvý. Takže to niekto chcel dať stab na to, čo Prvá vec, ktorú chcete robiť, keď začínate z vyhľadávania? Ak hľadáme hodnota 66, čo je Prvá vec, ktorú chceme robiť, keď chceme binárne vyhľadávanie tento strom? 

Divákov: Chcete vyzerať správne a pozrieť sa vľavo a pozrite [nepočuteľný] väčší počet. 

ANDI PENG: Jo, presne tak. Takže budete pozrieť sa na svoj koreň. Je tu veľa spôsobov, ako môžete volať to, vaši rodič uzol ľudia hovoria. Páči sa mi povedať, pretože koreň to je ako koreň stromu. Budeš sa pozerať na koreňový uzol, a vy ste ide vidieť, je 66 vyšší alebo menšie ako 55. A ak je to väčšie ako, no, to je väčší než tam, kde chceme vyzerať? Kde chceme hľadať, nie? Chceme prehľadať Pravá polovica tohto stromu. 

Takže máme, pohodlne, je ukazovateľ, ktorý ukazuje na pravej strane. A tak potom môžeme nastaviť náš nový koreň byť 77. Môžeme jednoducho ísť kamkoľvek pointer ukazuje. No, oh, tu začíname na 77, a môžeme len to rekurzívne znova a znova. Týmto spôsobom, tak nejako o majú funkciu. Máte spôsob vyhľadávania, ktoré vás stačí opakovať znovu a znovu a znovu, podľa toho, kde sa chcete pozrieť až sa nakoniec dostal na hodnotu ktoré hľadáte. Dáva zmysel? 

Chystám sa vám ukázať skutočný kódu, a je to veľa kódu. Nie je potrebné šalieť. Porozprávame sa cez to. 

V skutočnosti, no. To bol len pseudokód. OK, to bol len pseudokód, ktorý je trochu zložitejšie, ale je to úplne v poriadku. Každý, kto po pozdĺž tu? Ak je koreň je null, návrat false pretože to znamená vy ani nemusíte nič tam. 

Ak je koreň n je hodnota, takže ak je sa stane byť ten, že ste pri pohľade na, potom budete vráti hodnotu true pretože viete, že ste ju našli. Ale ak je táto hodnota nižšia než root n, ty si bude hľadať ľavý dieťa alebo ľavé krídlo, čo chcete hovoriť. A ak je hodnota vyššia ako root, budete hľadať ten správny strom, potom stačí spustiť funkciu pomocou vyhľadávania znova. 

A ak koreň je null, že znamená, že ste prišli na koniec? To znamená, že nemáte Viac odchádza hľadať, potom viete, oh, ja Asi to nie je v tú pretože po Díval som sa cez celá vec a nie je to tu, to jednoducho nemusí byť tu. 

Znamená to, že zmysel pre všetkých? Takže je to ako binárny vyhľadávanie konzervačným Schopnosti prepojených zoznamov. Cool, a tak druhý typ dátové štruktúry vy chlapci môžu vyskúšať vykonávanie na pset, máte len vybrať jednu metódu. Ale možno alternatívnou metódou hash tabuľka je to, čo nazývame trie. 

Všetko, Trie je je Špecifickým typom stromu má hodnoty, ktoré idú na iné hodnoty. A tak namiesto toho, binárne strom v tom zmysle, že iba jedna vec môže poukázať na dva, môžete mať jedna vec, prejdite na mnoho, mnoho vecí. Tie majú v zásade pole vnútri ktoré ukladáte ukazovatele, ktoré ukazujú na iné pole. 

Takže uzol, ako by definoval trie ich chceme mať Boolean, c slovo, že jo? Takže uzol je Boolean ako pravdivé alebo nepravdivé, v prvom rade na čele že pole, je to slovo? Po druhé, chcete mať ukazovatele sa bez ohľadu na ostatné z nich sú. Trochu zložitejšie, trochu abstraktné, ale Budem vysvetľovať, čo to všetky prostriedky. 

Tak tu, na vrchole, ak ste majú celý rad deklaroval už, uzol, kde máte Boolean hodnota uložená na prednej strane ktorý vám povie, je to slovo? Nie je to slovo? A potom máte zvyšok vášho pole, ktoré v skutočnosti ukladá všetky možnosti toho, čo by to mohlo byť. Tak, napríklad, ako je hore máte Prvá vec, ktorá hovorí, že pravda alebo false, áno alebo nie, to je slovo. 

A potom máte 0 až 26 písmená, ktoré môžete uložiť. Ak by som chcel hľadať tu pre bat, idem na vrchol a ja sa pre B. nájdem B v mojom poľa, a tak viem, v poriadku, je B slovo? B nie je slovo, takže sa tak Musím pokračovať v hľadaní. Idem z B, a ja sa k ukazovateľ, ktorý ukazuje na B a vidím iný rad informácií, rovnakú štruktúru, ktoré sme predtým. 

A here-- oh, ďalšie List v [nepočuteľný] je A. Takže sa pozrieme v tomto poli. Nájdeme ôsmy hodnotu, a potom sa pozrieme vidieť, oh, hej, je to jedným slovom, je B-A slovo? Nejedná sa o slovo. Musíme hľadať ďalej. 

A tak potom sa pozrieme na miesto, kde ukazovateľ z A bodov, a odkazuje na iný spôsob v ktorý máme väčšiu hodnotu uloží do pamäte. A nakoniec sme sa dostať do B-A-T, čo je slovo. A tak sa nabudúce vyzeráš, budete mať tento kontrolu, áno, táto Boolean funkcie je pravda. A tak sa v tom zmysle, že sme trochu mať strom s poli. 

Takže môžete trochu hľadať nadol. Skôr než hash funkcie a priradenie hodnôt Google zoznamu môžete len implementovať Trie, ktorý prehľadáva downwords. Naozaj, naozaj zložité veci. Nie je ľahké si myslieť, o, pretože som rád pľuvať toľko dátových štruktúr out na vás, ale robí každý druh pochopiť, ako logika to funguje? 

OK v pohode. A tak B-A-T, a potom sa budete hľadať. Nabudúce ideš vidieť, oh, hej, to je pravda, Viem, že to tak musí byť slovo. 

To isté pre zoo. Tak tu je to práve teraz, keď sme chcel hľadať zoo, práve teraz, V súčasnej dobe zoo nie je slovo v našom slovníku pretože, ako vy môžete vidieť, Prvé miesto, ktoré máme Boolean vráti pravda, je na konci zoom. Máme Z-O-O-M. 

A tak tu, nemáme vlastne mať Slovo, zoo, v našom slovníku preto, že toto políčko nie je začiarknuté. Takže počítač nie je vedia, že zoo je slovo, pretože tak, že máme uložil to, len zoom tu v skutočnosti má logickú hodnotu , Ktorá bola obrátil pravda. Takže ak chceme vložiť slovo, zoo, do nášho slovníka, ako by sme ísť o tom, že? Čo musíme urobiť, aby sa ubezpečil, naša počítač vie, že Z-O-O je slovo a nie prvý slovo je Z-O-O-M? 

Divákov: [Nepočuteľné] 

ANDI PENG: Presne tak, my chcete, aby sa ubezpečil, že tento tu, že logická hodnota odškrtnúť, že je to pravda. Z-O-O, potom budeme kontrolovať, či, takže presne vieme, hej, zoo je slovo. Chystám sa povedať, Počítač, ktorý je to slovo tak že keď je počítač kontroly, vie, že zoo je slovo. 

Vzhľadom k tomu, spomenúť na všetky tieto údaje štruktúry, je to pre nás veľmi ľahké povedať, oh, netopier je to slovo. Zoo je to slovo. Priblížiť to slovo. Ale keď ste ho stavia, počítač nemá ani poňatia. 

Takže musíte to povedať presne na akom mieste je to slovo? V akom okamihu nie je to slovo? A na akom mieste robiť ja je potrebné hľadať veci, a na akom mieste sa musím ísť ďalej? Každý jasné, že? Super. 

A tak potom príde Problém, ako by sme sa ísť o vloženie niečo že to vlastne nie je? Takže povedzme, že chceme vložiť Slovo, kúpele, do nášho trie. Ako vy môžete vidieť, ako v súčasnej dobe všetko, čo máme teraz, je B-A-T, a táto nová štruktúra dát tam mal polliter, ktorý poukázal na hodnotu null, pretože predpokladáme, že, oh, je tu po B-A-T žiadne slová, prečo potrebujeme zachovať majú veci po tomto T. 

Problém však nastáva, keď budeme robiť vás chcú mať slovo, ktoré prichádza po T je. Ak máte vaňu, ste bude chcieť H právo. A tak spôsob, akým budeme k tomu, že je budeme vytvoriť samostatný uzol. Nie sme prideliť bez ohľadu na čiastku, pamäte pre toto nové pole, a budeme priradiť ukazovatele. 

Budeme priradiť H, Po prvé, to null, budeme zbaviť. Budeme mať Bod H smerom nadol. Ak vidíme H, chceme ho ísť niekam inam. 

Tu, potom môžeme odškrtnúť áno. Ak by sme hit H po T, oh, potom vieme, že sa jedná o slovo. Boolean sa chystá vrátiť true. Všetci jasné, o tom, ako sa to stalo? OK. 

Takže v podstate všetky Tieto dátové štruktúry že sme prešli dnes, som naozaj, ale naozaj rýchlo preč nad nimi a nie v oveľa detail, a to je v poriadku. Akonáhle začnete umazávání s tým, budete sledovanie, kde Všetky ukazovatele sú, čo sa deje vo vašom dátové štruktúry, a tak ďalej. Budú veľmi užitočné, a je len na vás, chlapci úplne zistiť, ako Ak chcete implementovať veci. 

A tak pset4, z 5-- oh, to je zlé. Pset5 je preklepy. Ako som už povedal skôr, budete, akonáhle Znova, stiahnite zdrojový kód od nás. Tam to bude Tri hlavné veci, ktoré budete sťahovať. Budete stiahnuť slovníky, KERS, a texty. 

Všetky tieto veci sú, sú buď slovníky slov že chceme, aby ste skontrolovať alebo test informácií že chceme, aby ste kontrolu pravopisu. A tak sa slovníky dáme idete aby vám aktuálne slová, ktoré chceme ukladať nejako spôsobom, ktorý je účinnejší ako pole. A potom texty sú Bude to, čo sme so žiadosťou o kontrolu pravopisu, aby sa uistil všetky slová existujú skutočné slová. 

A tak tri bloky programy, ktoré dáme vám sa nazývajú dictionary.c, dictionary.h, a speller.c. A tak všetci dictionary.c robí, je čo ste vyzvaní k realizácii. To načíta slová. To kúzlo je skontroluje, a to je istý, že všetko je správne vložený. 

diction.h je len súbor knižnice že deklaruje všetky tieto funkcie. A speller.c, budeme dať. Nemusíte meniť nič z toho. Všetky speller.c robí, je vziať to, Zaťaženie to, kontroluje rýchlosť na to, testuje meradlo ako ako rýchlo ste schopní robiť veci. 

Je to Speller. Jednoducho to nie je neporiadok s ním, ale urobiť sa, že ste pochopili, čo to robí. Používame funkciu nazvanú getrusage že testuje výkon svojho kúzla checker. Všetko, čo to robí, je v podstate otestovanie Čas všetko vo vašom slovníku, takže sa uistite, ste to pochopili. Buďte opatrní, aby neporiadok s ním, alebo inde sa veci nebude fungovať správne. 

A Prevažná časť tohto problému je pre vy naozaj zmeniť dictionary.c. Budeme vám 140.000 slov v slovníku. Budeme vám textu súbor, ktorý má tieto slová, a chceme, aby ste boli schopní zorganizovať je do tabuľky hash alebo trie pretože keď vás žiadame, aby bolo zrejmé check-- predstavte si, že ste kúzlo kontrola ako Homerovi Odysseia. Je to ako obrovský, obrovský tento test. 

Predstavte si, že každý slovo, ktoré sa musel pozrieť prostredníctvom série 140.000 hodnôt. To by trvalo večnosť pre váš počítač spustiť. To je dôvod, prečo chceme organizujeme dáta do efektívnejších dátových štruktúr ako je napríklad hashovacie tabuľky alebo trie. A potom vy môžete druh o pri hľadaní prístupe veci ľahšie a rýchlejšie. 

A tak buďte opatrní na riešenie kolízií. Budeš mať veľa zo slov, ktoré začínajú A. Budeš mať veľa slov že začať s B. Až do vás chlapi, ako chcete ho riešiť. Možno, že tam je viac efektívne funkcie hash než len prvým písmenom niečo, a tak to je len na vás chlapci druh robiť, čo chcete. 

Možno chcete pridať všetky listy dohromady. Možno chcete páčiť robiť divné veci na účet počtu písmen, Hocičo. Až vás chalani, ako chcete robiť. Ak si chcete urobiť hash tabuľky, ak ste chcete pokúsiť o Trie, úplne na vás. Budem vás varovať vopred, že Trie je zvyčajne o niečo zložitejšie len preto, že je tu veľa ďalšie ukazovatele sledovať. Ale úplne na vás chlapci. Je to oveľa efektívnejšie vo väčšine prípadov. Ak chcete byť naozaj schopná udržať prehľad o všetkých vašich ukazovateľov. Ako urobiť to isté že som tu. Keď sa snažíte vložiť Hodnoty do tabuľky hash alebo odstrániť, uistite sa, že ste Naozaj sledovanie kde je všetko preto, je to pre či som rýchle pokúšate vložiť rád slovo, Andy. Povedzme, že je to skutočné slovo, slovo, andy, do obrie zozname A slov. 

Keby som náhodou preradiť ukazovateľ zle, oops, tam jede celistvosť zvyšok môjho Google zoznamu. Teraz jediné slovo, ktoré som majú, je Andy, a teraz všetky ostatné slová v Slovník boli stratené. A tak sa chcete uistiť, že sledovať všetky vaše ukazovateľov inak budete mať obrovské problémy v kóde. Remíza veci starostlivo krok za krokom. To robí to oveľa jednoduchšie myslieť. 

A konečne, chcete byť schopní otestovať výkon vášho programu na veľké doske. Ak vy trvať pozrite sa na CS50 práve teraz, máme to, čo sa nazýva veľký doska. Je to skóre list najrýchlejší kúzlo časov kontrolné naprieč všetkými CS50 práve teraz, myslím, že na vrchol ako 10 Časy Myslím si, že osem z nich sú zamestnancami. Naozaj chceme vy, aby nás porazil. 

Každý z nás sa snaží realizovať najrýchlejší kód ako je to možné. Chceme, aby si chlapci, aby sa pokúsili napadnúť nás a realizovať rýchlejšie, ako my všetci môcť. A tak to je naozaj to prvýkrát, čo sme dotazom vám chalani urobiť pset ktorý si môžete naozaj robiť v akejkoľvek metóde chceš. 

Vždy hovorím, to je viac podobný do reálneho života riešenia, nie? Ja hovorím, hej, musíš to urobiť. Postaviť program, ktorý robí to pre mňa. Urob to však budete chcieť. Ja len viem, že chcem, aby rýchlo. To je vaša výzva pre tento týždeň. Vy chlapi, ideme aby vám úloha. Budeme vám výzvu. A potom je to na vás chlapci úplne len prísť na to, čo je najrýchlejší a najviac účinný spôsob, ako realizovať to. Jo? 

Divákov: Sme dovolené, pokiaľ chcel vyhľadajte rýchlejšie spôsoby robiť hash tabuľky on-line, môžeme to urobiť že a citujú kód niekoho iného? ANDI PENG: Jo, úplne v pohode. Takže ak vy prečítať spec, je tu rad v spec, ktorý hovorí, že chlapci sú úplne zadarmo a vyhľadajte hash funkcie na aké sú niektoré z rýchlejší hash funkcie bežať veci skrze as dlho, ako vám citovať, že kód. Takže niektorí ľudia už prišiel na to, rýchle postupy robenie preklepov, rýchleho spôsoby ukladania informácií. Úplne na vás chlapci, ak vás chcú len brať, že jo? Uistite sa, že ste s odvolaním. Výzvou tu naozaj že sa snažíme testovať je uistiť sa, že viete, svoju cestu okolo ukazovatele. Tak ďaleko, ako sa robí skutočné funkcie hash a prichádza s podobne matematika k tomu, že, vy môžete výskum čokoľvek metódy on-line chlapci chcú. Jo? 

Divákov: Môžeme uviesť len pomocou [nepočuteľných]? 

ANDI PENG: Jo. Stačí si len, vo váš komentár, môžete citovať ako, oh, prevzaté z Yada, bla, bla, hashovacie funkcie. Každý, kto má nejaké otázky? Vlastne sme breezed úsekom dnes. Budem sa sem odpovedať na otázky rovnako. 

Tiež, ako som povedal, kancelárske hodín dnes večer a zajtra. Spec tento týždeň je vlastne super ľahké a super krátky čítať. Navrhoval by som, že pohľad, len prečítať celé to. 

A Zamyla vás vlastne prechádzky cez každú z funkcií budete musieť implementovať, a tak je to veľmi, veľmi jasné, ako to urobiť všetko. Len aby sa ubezpečil, že ste sledovanie ukazovateľov. Jedná sa o veľmi náročný pset. 

Nie je to náročné, pretože rád, oh, pojmy sú tak oveľa viac ťažké, musíte sa naučiť tak veľa nového syntaxe cesta že ste na poslednú pset. To pset je ťažké, pretože existuje toľko ukazovatele, a potom je to veľmi, veľmi jednoduché, akonáhle máte chybu v kóde nebudú môcť zistiť, kde, že chyba je. 

A tak naprostý vieru vo vás chlapi, aby mohli poraziť našich [nepočuteľných] hláskovanie. Ja vlastne nemám žiadny písomný baňa ešte, ale ja som to písal ja. Takže zatiaľ čo píšete vaše, budem písať moje. Budem sa snažiť, aby moja rýchlejšie ako vaše. Uvidíme, kto má najrýchlejší jeden. 

A jo, budem vidieť všetky vy tu v utorok. Budem spustiť akýsi sa ako pset dielni. Všetky sekciách tohto týždeň sú pset dielne, takže si chlapci majú veľa možností o pomoc, úradné hodiny ako vždy, a ja sa naozaj teším na čítanie všetci kódu vašich chlapci. Mám vypočúva tu, ak vás chlapci chcú ísť dostať tie. To je všetko.