[Powered by Google Translate] [Návod - Problém Set 5] [Zamyla Chan - Harvard University] [To je CS50. - CS50.TV] 

Dobrá. Ahoj, všichni, a vítejte na Walkthrough 5. 

Pset5 je Pravopisné chyby, ve kterém budeme dělat pravopisu. Spell-dáma, jsou nesmírně důležité. Má to někdy stalo? Můžete pracovat velmi, velmi hromadí na papíře pro střet a pak ještě nakonec dostat velmi záře Rade jako D nebo D = a všichni proto, že jste liverwurst spoiler v velryb širokém slova. Ano, korektury vašich papriky je věc, maximální impotence. To je problém, který postihuje mužské, mužné studenty. Byl jsem jednou řekl můj mučitel stupně Sith, že bych nikdy dostat do dobrého kolegu. A to je vše, co jsem kdy chtěl, to je všechno, každý kluk chce v mém věku, Jen dostat se do dobré kolegovi. A ne jen tak ledajaký kolega. Ne Chtěl jsem jít do slonoviny Právní kolegovi. Takže pokud jsem to zlepšení, by šel se mé sny o jít na Harvard, Jale, nebo Prison - víte, ve věznici, New Jersey. Tak jsem si sám sobě pravopisu. To je trochu výpis z jedné z mých nejoblíbenějších mluvené slovo umělců, Taylor Mali. Každopádně, jak říká, že je důležité mít pravopisu je velmi důležité. 

Takže vítejte na Walkthrough 5, ve kterém se bude hovořit o pset5: pravopisné chyby, , ve kterém budeme dělat naše vlastní pravopisu. Nástrojů pro tento týden, distribuce kód, bude důležité, aby se na jen pochopit různé funkce, které váš slovník bude mít. Jsme vlastně bude mít více. C. souborů, které dohromady tvoří naši PSet. A tak hledá prostřednictvím různých aspektech, i když jsme vlastně ne pro editaci jeden ze souborů, speller.c, věděl, jak to funguje ve vztahu k dictionary.c, které budeme psát, bude dost důležité. Spec Pset také obsahuje mnoho užitečných informací pokud jde o věci, které můžete předpokládat, pravidla a podobné věci, které, tak se určitě přečtěte PSet spec pečlivě tipy. A v případě pochybností o pravidla nebo něco takového, pak se vždy vztahují k PSet spec nebo Diskutovat. Tento Pset bude spoléhat na ukazatele, tak chceme, aby se ujistil, že jsme pochopili rozdíl mezi přidávání hvězdiček v přední části je ukazatel jméno a ampersand, jak se osvobodit a atd. Takže být mistrem ukazatelů bude velmi užitečné v tomto problému sadě. Budeme se podívat do propojené seznamy trochu víc, kde mají prvky, který nazýváme uzly, které mají jak hodnotu, stejně jako ukazatel k následujícímu uzlu, a tak v podstatě propojení různých prvků jeden po druhém. Existuje několik různých možností na realizaci své skutečné slovník. Budeme se podívat do dvou hlavních metod, které je hashovací tabulky a potom se pokusí. V obou těch, které zahrnují nějaký druh pojmu propojeného seznamu kde jste elementy navzájem propojeny. A tak budeme vypadat nad tím, jak byste měli být schopni pracovat kolem propojených seznamů, vytvořit, přecházet z hlediska jak, například, vložit uzel do něj nebo bez všechny uzly stejně. Pokud jde o uvolňovacími uzlů, to je opravdu důležité že kdykoli jsme malloc paměti, potom jsme uvolnit ji. Takže chceme, aby se ujistil, že žádný ukazatel jde unfreed, že nemáme žádné úniky paměti. Budeme zavést nástroj nazývaný Valgrind, který běží na programu a kontroluje, zda všechny paměti, že přidělené je pak osvobozený. Vaše Pset je pouze dokončit, když to funguje, a má plnou funkčnost, ale také, Valgrind vám řekne, že jste nenašli žádné úniky paměti. Konečně, pro tento PSet, opravdu chci zdůraznit - Myslím, jako obvykle, já jsem rozhodně zastáncem použití pera a papíru pro vaše problémové soubory, ale pro tento jeden, myslím, že pero a papír bude zvláště důležité pokud chcete, aby se čerpání šipky na věci a pochopení toho, jak věci fungují. Takže určitě zkuste použít tužku a papír k tomu, co před vás kódování protože by to mohlo být trochu chaotický. 

Za prvé, pojďme do propojených seznamů trochu. Propojené seznamy se skládají z uzlů, kde každý uzel má hodnotu spojenou s ním, stejně jako ukazatel na další uzel po něm. Pár věcí důležitých s lineárními seznamy je, že musíme mít na paměti kde naše první uzel je, a pak jednou víme, kde první uzel je, že způsob, jak můžeme přistupovat na uzel, který první uzel odkazuje na a pak ještě do a jeden po tom. A pak poslední prvek ve vašem propojeného seznamu je tento uzel je ukazatel je vždycky poukázat na NULL. Když uzel bodů na hodnotu NULL, pak víte, že jste na konci seznamu, že uzel je poslední, že není nic po tom. Tady v tomto schématu, uvidíte, že šipky jsou ukazatele, a modré sekce je místo, kde je uložen hodnota, a pak červené pole s ukazatel na ní je uzel je ukazatel ukazuje na další uzel po něm. A tak zde vidíte, by uzel D poukázat na NULL, protože to je poslední prvek v seznamu. 

Pojďme se podívat na to, jak bychom mohli definovat struct pro uzel. A protože chceme mít více uzlů, to se stane typedef struct , ve kterém budeme mít několik různých instancí uzlů. A tak jsme ji definují jako nový datový typ. Zde máme typedef struct uzel. V tomto příkladu, máme co do činění s celočíselnými uzly, takže máme celočíselnou názvem hodnotu a potom máme další ukazatel, a v tomto případě, je to ukazatel na uzel, takže máme struct uzel * volal další. A pak voláme celou tuto věc uzel. Ujistěte se, že budete dodržovat následující syntaxi. Všimněte si, že uzel je ve skutečnosti odkazováno nahoře stejně jako dole složených závorek. Pak sledovat, kde moje první uzel v tomto propojeném seznamu, pak jsem si uzel ukazatel s názvem hlava, a já malloc dostatek prostoru pro velikost uzlu. Poznámka, nicméně, že hlava je vlastně uzel ukazatel na rozdíl od aktuálního uzlu samotného. Takže hlava skutečně neobsahuje žádnou hodnotu, pouze poukázat na podle toho, co první uzel v mém propojeného seznamu je. 

Chcete-li získat lepší představu o souvisejících seznamů, protože je to velmi důležité, sledovat ujistit se, že budete udržovat řetěz, Líbí se mi myslet na to, jak se lidé v řadě se drží za ruce, , kde každá osoba je drží za ruce s další. Nemůžete vidět v tomto výkresu, ale v podstatě jsou to ukazuje na další osobu že je v jejich řetězci. A tak pokud chcete projít propojené seznam, kde tito lidé - představit všechny ty lidi mají hodnoty spojené s nimi a také poukazují na další osoby v souladu - Chcete-li přejít propojeného seznamu, například, buď upravit hodnoty nebo hledání hodnotě nebo něco takového, pak budete chtít mít ukazatel na konkrétní osobu. Takže budeme mít datový typ uzlu ukazatel. Pro tento Například, řekněme, že kurzor. Dalším běžným způsobem pojmenovat to bude iterátor, nebo něco takového protože je to iterace a vlastně dojemná, který uzel to ukazuje. Tohle bude naše kurzor. Náš kurzor se nejprve poukázat na první prvek v našem seznamu. A tak to, co chceme udělat, je, že jsme se v podstatě bude pokračovat kurzor, pohybující se ze strany na stranu. V tomto případě, chceme přesunout na další prvek v seznamu. S polem, co budeme dělat, je bychom jen říci, že jsme zvýšit index 1. V tomto případě, co musíme udělat, je skutečně zjistit, které osoby tento proud osoba směřující, a že to bude další hodnotu. Takže pokud kurzor je jen uzel ukazatel, pak to, co chceme dělat je, že se chtějí dostat na hodnotu, která je kurzor ukazuje. Chceme se dostat do tohoto uzlu a pak, až budeme v tomto uzlu, zjistit, kde to ukazuje. Chcete-li získat skutečné uzlu, který kurzor ukazuje na, obvykle označujeme ji (* kurzor). To by vám aktuální uzel, který kurzor ukazuje. A potom, co chceme udělat, je chceme přistupovat co to uzlu příští hodnota. K tomu, aby přístup k hodnoty uvnitř struct, máme operátoru tečka. Takže pak by to bylo (* kurzor). Další. Ale to je trochu chaotický, pokud jde o to, aby závorky kolem * kurzoru, a tak jsme se nahradit celou tuto prohlášení s kurzorem->. To je pomlčka a pak větší než znak, tak aby se šipkou. Kurzor-> next. To bude skutečně vám uzel, který se kurzor ukazuje. Tato hodnota je o další. Takže místo toho, aby na hvězdičku a tečku, budete nahrazovat, že se šipkou. Buďte velmi opatrní, aby se ujistil, že se pokusíte použít tuto syntaxi. 

Nyní, když máme kurzor, pokud chceme, aby přístup k hodnotě, předtím, jsme měli kurzor-> next, ale pro přístup k hodnotě na uzlu, který kurzor ukazuje na, jsme prostě říct node-> hodnota. Odtud je to na datový typ, co jsme definovali hodnoty a uzlů být. Pokud je to int uzel, pak kurzor-> hodnota je jen bude číslo. Takže můžeme udělat operace na to, podívejte se rovností, přiřadit jí různé hodnoty, atd. Takže to, co chcete dělat, když chcete přesunout kurzor na další osobu, můžete skutečně změnit hodnotu kurzoru. Vzhledem k tomu, kurzor je uzel ukazatel, můžete změnit aktuální adresu ukazatel na adresu dalšího uzlu v seznamu. To je jen nějaký kód, kde byste mohli iteraci. Kde mám komentář něco udělat, to, kde jste pravděpodobně bude přístup k hodnotě nebo něco do činění s tímto konkrétním uzlu. Chcete-li začít ho, říkám, že můj kurzor původně bude ukazovat na první prvek v propojeném seznamu. A tak se před námi, jsem definoval to jako hlava uzlu. 

Jak jsem již zmínil dříve, uvolňovat je opravdu důležité. Chcete, aby se ujistil, že jste uvolnit každý prvek v seznamu, jakmile jste skončil s ním. Když nemusíte odkazovat některé z těchto ukazatelů už, chcete, aby se ujistil, že jste osvobodit všechny tyto ukazatele. Ale vy chcete být velmi opatrní v tom, že budete chtít, aby se zabránilo nevracení paměti. Pokud si zdarma jeden člověk předčasně, pak všechny ukazatele, které tento uzel odkazuje na se bude ztracena. Vraťme se zpět k osobě příklad, aby bylo trochu víc high stakes, pojďme si tyto lidi, s výjimkou v tomto případě, že se vznášejí nad jezerem s monstrem. Chceme se ujistit, že vždy, když jsme uvolnění, abychom neztratili a pustil všechny uzly, než jsme ve skutečnosti je osvobodil. Například, pokud jste byli jednoduše volat zdarma na toho chlapa tady, pak by byla uvolněna, ale pak všechny tyto lidi by pak dojít ke ztrátě a oni by usnout a spadnout. Takže chceme, aby se ujistil, že místo, chceme zachovat odkaz na zbytek. Naše hlava ukazatel, který ukazuje na první prvek v seznamu. Je to něco jako lano kotevní první osobě. Co byste mohli chtít dělat, když jste uvolnění seznam je mít - Pokud chcete, aby se uvolnil první prvek první, pak můžete mít dočasný ukazatel že poukazuje na jakýkoliv první prvek je. Takže máte váš dočasný ukazovatel zde. Tak, máme držet prvního uzlu. A pak, protože víme, že první uzel bude osvobozen, pak můžeme přesunout lano, tento kotevní, naše hlavy, skutečně poukazují na cokoliv první ukazuje. Tak tohle hlava skutečně odkazuje na druhý prvek nyní. Nyní se mohou uvolnit, co je uloženo v teplotě, a tak se může odstranit, že bez ní ohrožení všech ostatních uzlů v našem seznamu. Dalším způsobem, že byste mohli udělat to mohlo být pokaždé, když stačí uvolnit poslední prvek v seznamu protože oni zaručeno, že se ukázal na cokoliv. Takže vy jste mohli jen uvolnit tenhle, pak volný tentokrát, pak bez tentokrát. To určitě funguje, ale je trochu pomalejší, protože podle povahy propojených seznamů, můžeme nejen okamžitě skočit do posledního. Musíme projít každý prvek v připojeném seznamu a zkontrolujte, zda že jeden ukazuje na NULL, zkontrolujte pokaždé, a pak ještě jednou dojdeme na konec, pak zdarma, které. Pokud byste měli udělat tento proces, by si skutečně být kontrola zde, kontrola tady, pak kontrola tady, uvolňovat to, pak jít zpět, kontrola tady, kontrola tady, uvolňovat to, kontrola tady, a pak uvolňovat to. To vyžaduje trochu více času. Jo. 

[Student] Bylo by možné, aby se spojový seznam, který ukládá návratový ukazatel na konec? To by určitě bylo možné. Chcete-li zopakovat otázku, je možné mít propojenou seznam strukturu tak, že si mít ukazatel směřující do konce propojeného seznamu? Řekl bych, že je to možné, a pokaždé, když vložíte něco do propojeného seznamu budete muset aktualizovat tento ukazatel a podobné věci. Ty by měly uzlu * ocas, například. Ale když jste provádění této funkci, musíte myslet na kompromisů, Líbí kolikrát budu se iterace nad tím, jak těžké je bude sledovat z ocasu, stejně jako hlava stejně jako můj iterátor, a podobné věci. Znamená to, že -? >> [Student] Jo. Je to možné, ale pokud jde o návrhu rozhodnutí, budete muset zvážit možnosti. 

Zde je kostra kódu, který by vám umožní uvolnit každý prvek propojeného seznamu. Opět, protože jsem iterace provázaném seznamu, budu chtít mít nějaký kurzoru nebo iterátor. Jsme iterací, dokud kurzor NULL. Nechcete, aby iteraci, kdy je kurzor na NULL protože to znamená, že není nic v seznamu. Takže tady jsem vytvořit dočasnou uzlu * poukazuje na to, co jsem za zvážení, je první z mého seznamu, a pak jsem pohnout kurzorem dopředu 1 a pak volný, co jsem měl v režimu dočasného uskladnění. 

Nyní se dostáváme k vložení do propojených seznamů. Mám tři uzly v mé propojeného seznamu, a pojďme se jednoduchém případě tam, kde chceme vložit další uzel na konci našeho propojeného seznamu. K tomu, vše, co bude dělat je, že jsme se projít zjistit, kde proud konec propojeného seznamu je, tak podle toho, uzel ukazuje na NULL - že je to jedno - a pak říci, vlastně, tohle je nebude poslední uzel; jsme vlastně bude mít jinou. Takže budeme mít tento současný jeden bod k tomu, co jsme vkládání. Takže teď to červené osoba zde stává poslední uzel v propojeném seznamu. A tak charakteristický posledního uzlu v propojeném seznamu je, že se poukazuje na NULL. Takže to, co bychom měli udělat, je nastavit tuto červenou chlapa ukazatel na NULL. Tam. 

Ale co když chceme vložit uzel mezi druhým a třetím jeden? To člověk není tak jednoduché, protože chceme, aby se ujistil že nepouštěj žádného uzlu v naší propojeného seznamu. Co bychom měli udělat, je ujistit, že jsme ukotvit, abychom se každé z nich. Například, řekněme tuto druhou možnost. Pokud jste řekl druhý nyní ukazuje na tuto novou a jste právě udělal ukazatel tam, pak by to bylo za následek ten chlap ztrátě protože tam není žádný odkaz na něj. Místo toho - budu kreslit to znovu. Omluvte mé umělecké schopnosti. Víme, že nemůžeme jen tak přímo připojit 2 do nového. Musíme se ujistit, že jsme se držet na poslední. Co bychom mohli chtít udělat, je mít dočasný ukazatel na prvek, který je bude připojena na. Takže máme dočasný ukazatel tam. Protože víme, že to třetí je držen sledovat, 2 může nyní propojit do našeho nového. A pokud tato nová červená chlap bude mezi 2 a 3, pak to, co je ten chlap je ukazatel bude ukazovat na? >> [Student] Temp. Temp. Jo. Takže tahle červená chlap další hodnota bude tepl. Když jste vložením do propojených seznamů, viděli jsme, že bychom mohli snadno přidat něco do konce vytvořením dočasné pole, nebo pokud jsme chtěli přidat něco do středu našeho pole, pak by to trvat trochu více přešlapuje. Pokud chcete, například, mají seřazena propojeného seznamu, pak se budete muset trochu zvažovat náklady a přínosy, které protože pokud chcete mít seřazena pole, to znamená, že pokaždé, když vložíte do něj, to bude trvat trochu déle. Nicméně, pokud chcete, aby později, až najdeme budeme chtít, Hledání pomocí propojeného seznamu, pak to může být snadnější, pokud budete vědět, že je vše v pořádku. Takže možná budete chtít zvážit náklady a přínosy, které. 

Dalším způsobem, jak vložit do propojeného seznamu je vložit do začátku seznamu. Pokud čerpáme kotvu zde - to je naše hlava - a pak tito lidé s ní souvisí, a pak máme nový uzel má být vložena do začátku, pak to, co bychom mohli chtít udělat? Jaký by měl být v pořádku s jen říkám chci propojit červené k modré, protože to je první? Co by se stalo tady? Všechny z těchto tří by ztratit. Takže nechceme udělat. Opět jsme se dozvěděli, že musíme mít nějaký druh dočasného ukazatele. Pojďme si vybrat na dočasnou dobu bod na toho chlapa. Pak můžeme mít modrou jeden bod k tomu dočasné a pak červený bod na modré. Důvodem, proč jsem využívala lidi tady je, protože my opravdu chceme vizualizovat drží na lidi a ujistit se, že máme odkaz na ně před pustíme jiného ruky nebo něco takového. 

Nyní, když máme pocit lineárními seznamy - jak bychom je mohli vytvořit odkazovaný seznam a vytvořit struktury pro které se skládá z definice typu pro uzel a pak ujistit se, že máme ukazatel na hlavě toho propojeného seznamu - jakmile budeme mít to a víme, jak přejít přes pole, přístup k jednotlivým prvkům, víme, jak vložit a my víme, jak se osvobodit, pak se můžeme dostat do překlepy. Jako obvykle, máme část otázek, na které se vám slouží k provozu s propojenými seznamy a různé struktury jako jsou například fronty a komínů. Pak se můžeme přesunout do překlepy. 

Pravopisné chyby se v distribuční kódu několik souborů významu. Nejprve jsme si všimli, že máme tuto Makefile tady, které jsme opravdu nesetkal. Pokud jste se podívali dovnitř pset5 složky, tak zjistíte, že máte. H soubor, pak máte dvě. C soubory. Co to dělá, je Makefile předtím, bychom stačí napsat make a pak název programu a pak bychom viděli všechny tyto argumenty a vlajek předány do kompilátoru. Co Makefile dělá, je nám umožňuje sestavit několik souborů najednou a předat vlajek, které chceme. Tady jsme jen vidět, že je soubor záhlaví zde. Pak jsme vlastně dva zdrojové soubory. Máme speller.c a dictionary.c. Jste vítáni upravit Makefile pokud si budete přát. Všimněte si, že zde, pokud zadáte čistý, pak to, co dělá, je ve skutečnosti odstraňuje něco že je jádro. Pokud máš segmentation fault, v podstatě máte core dump. Tak to ošklivý malý soubor se zobrazí ve vašem adresáři s názvem core. Budete chtít odebrat, že aby bylo čištění. To odstraní všechny spustitelné soubory a. Soubory o. 

Pojďme se podívat do dictionary.h. To říká, že to deklaruje slovníku funkčnost. Máme maximální délku pro libovolné slovo ve slovníku. Řekneme, že je to bude nejdelší slovo. Je to délky 45. Takže my nebudeme mít žádné slovo, které přesahují tuto délku. Zde musíme jen funkční prototypy. Nemáme vlastní realizaci, protože to je to, co budeme dělat v tomto PSet. Ale co to dělá, je, protože máme co do činění s většími soubory zde a funkčnost ve větším měřítku, je užitečné mít. h soubor tak, že někdo jiný číst, nebo pomocí kódu nemůže pochopit, co se děje. A možná, že chtějí zavést pokusí, pokud jste hash tabulky nebo naopak. Pak by řekli mi zatížení funkce, Vlastní realizace bude lišit, ale tento prototyp nebude měnit. Zde jsme zjistit, která vrací true, pokud dané slovo ve slovníku. Pak máme zátěž, která v podstatě trvá do slovníku souboru a potom načte do nějaké datové struktury. Máme velikost, která, je-li volána, vrací velikost vašeho slovníku, kolik slov jsou uloženy v ní, a potom uvolněte, které uvolní veškerou paměť, kterou lze vzít do a přitom svůj slovník. 

Pojďme se podívat na dictionary.c. Je vidět, že to vypadá velmi podobně jako dictionary.h, s výjimkou nyní to prostě má všechny tyto todos v něm. A tak to je vaše práce. Nakonec, budete vyplňovat speller.c se všemi tohoto kódu. Dictionary.c, při spuštění, není opravdu nic dělat, takže se podíváme na speller.c vidět skutečné provádění kontroly pravopisu. I když nejste bude editovat žádnou z tohoto kódu, je důležité přečíst, pochopit, když je zatížení nazývá, když jsem volat kontrolu, jen pochopit, zmapovat to, jak funkce pracuje. Vidíme, že je to kontrola správné použití. V podstatě, když někdo běží pravopisu, znamená to, že je to volitelný pro ně projít do slovníku souboru, protože tam to bude výchozí slovník souboru. A pak se musí projít v textu být spell-zkontrolovat. rusage zabývá času, protože část tohoto PSet které budeme zabývat později není jen dostat fungující spell-checker pracovní ale ve skutečnosti dostat, aby to bylo rychle. A tak pak to je místo, kde rusage se přijde dovnitř Zde vidíme první hovor s jedním z našich dictionary.c souborů, který je zatížení. Load vrací true nebo false - true na úspěch, false při výpadku. Takže pokud slovníku není vložen správně, pak speller.c vrátí 1 a ukončete. Ale pokud to dělá zátěž správně, pak to bude pokračovat. Budeme pokračovat, a my vidíme nějaký soubor I / O zde, kde to bude jednání s otevřením textového souboru. Zde, co to dělá, je kouzlo-kontroluje každé slovo v textu. Takže to, co speller.c dělá tady je iterace každého slova v textovém souboru a pak kontrola je ve slovníku. Zde máme logickou chybně, že uvidíme, jestli kontrola vrátí pravda nebo ne. Pokud slovo je vlastně ve slovníku, pak kontrola vrátí true. To znamená, že slovo není chybně. Takže chybně by bylo falešné, a to je důvod, proč máme bang tam, indikace. Držíme dál, a pak to sleduje, kolik slov s chybným pravopisem jsou v souboru. To pokračuje dál a zavře soubor. Pak tady, hlásí, kolik chybně napsaná slova, která měl. To počítá, jak dlouho to trvalo načíst slovník, Jak dlouho to trvalo podívat se na to, Jak dlouho to trvalo vypočítat velikost, která, jak budeme pokračovat, by mělo být velmi malé, a pak jak dlouho to trvalo vyložit slovník. Zde nahoře vidíme výzvu, abyste si vyložili zde. Pokud bychom zkontrolovat velikost zde, pak vidíme, že je zde výzva k velikosti, kde se určuje velikost slovníku. Awesome. 

Naším úkolem pro tuto PSet je implementovat zátěž, která načte slovník Datová struktura - podle toho, co si vyberete, ať už je to hash tabulka nebo zkusit - se slovy ze slovníku souboru. Pak máte velikost, která vrátí počet slov ve slovníku. A pokud se rozhodnete zatížení v inteligentním způsobem, pak velikost by měla být docela snadné. Pak jste zjistit, který bude zda dané slovo ve slovníku. Takže speller.c přechází v řetězci, a pak se budete muset zkontrolovat, zda řetězec je obsažen ve vaší slovníku. Všimněte si, že obecně mají standardní slovníky, ale v tomto Pset, v podstatě jakékoliv slovník prošel v kterémkoliv jazyce. Takže nemůžeme jen předpokládat, že slovo je uvnitř. Slovo foobar mohla být definována v jistém slovníku, který míjíme dovnitř A pak jsme vyložit, která osvobozuje slovník z paměti. 

Nejprve bych chtěl jít přes hash tabulky metody o tom, jak bychom mohli implementovat všechny z těchto čtyř funkcí, a pak půjdu přes snaží metody, jak provádět tyto čtyři funkce, a na konci rozhovoru o některých obecných tipů, když jste dělat PSet a také, jak byste měli být schopni používat Valgrind pro kontrolu úniků paměti. 

Pojďme do hash tabulky metodou. Hash tabulka se skládá ze seznamu segmentů. Každá hodnota, každé slovo, je jít do jednoho z těchto segmentů. Hash table ideálně rovnoměrně distribuuje všechny tyto hodnoty, které jste mimochodem v a pak vyplní je do kbelíku tak, že každá lopata má asi stejný počet hodnot v něm. Struktura tabulky hash, máme řadu propojených seznamů. Co máme udělat, je, když jsme se projít v hodnotě, můžeme zkontrolovat, kde tato hodnota by měla patřit, které vědro patří, a umístěte jej do propojeného seznamu spojené s tímto lopatou. Tady, co mám, je hash funkce. Je to int hash tabulky. Takže pro prvního segmentu, všechny celá čísla pod 10 jít do prvního segmentu. Jakékoliv celá čísla nad 10, ale nižší než 20 zacházejí do druhé, a pak se tak dále a tak dále. Pro mě, každý kbelík zastupuje tato čísla. Nicméně, říct, že jsem byl projít v 50, například. Zdá se, že první tři obsahují řadu deseti čísel. Ale já chci, aby moje hash tabulky, aby se v nějakém druhu celých čísel, tak pak budu muset odfiltrovat všechny čísla nad 30 do posledního segmentu. A tak pak by to mít za následek jakési nevyvážené hash tabulky. Chcete-li zopakovat, hash tabulka je jen řada lopat kde každý kbelík je provázaný seznam. A tak se určit, kde každá hodnota jde, což vědro to jde do, budete chtít, co se nazývá hash funkce že vezme hodnotu a pak říká tato hodnota odpovídá určité nádoby. Takže nahoře v tomto příkladu, moje hashovací funkce se každou hodnotu. Je kontrolováno, zda to bylo méně než 10. Pokud to bylo, to by dát do prvního segmentu. Zkontroluje, zda je to méně než 20, dá to do druhého, pokud platí, kontroluje, zda je to méně než 30, a potom ji umístí do třetího kbelíku, a pak všichni ostatní jen spadá do čtvrté kbelíku. Takže pokaždé, když mají hodnotu, vaše hashovací funkce bude klást tuto hodnotu do příslušného kbelíku. Hashovací funkce v podstatě potřebuje vědět, kolik kbelíky máte. Vaše velikost hash tabulky, počet segmentů, které máte, že to bude pevné číslo, které je na vás, pro vás se rozhodnout, ale to bude stanovený počet. Takže vaše hash funkce bude spoléhat na to určit, který lžíce každý klíč jde do takové, že je to rovnoměrně. Podobně jako naše provádění souvisejících seznamů, nyní každý uzel v hash tabulce bude skutečně mít typu char. Takže máme char pole s názvem Slovo a pak ještě ukazatel na další uzel, což dává smysl, protože to bude spojový seznam. Pamatuješ, když jsme se spojil seznamy, udělal jsem uzlu * s názvem hlava , který byl s poukazem na prvním uzlu v propojeném seznamu. Ale pro naše hash tabulky, protože máme několik propojených seznamů, to, co chceme, je chceme, aby náš hash table být jako, "Co je to kbelík?" Lopata je jen seznam uzlů ukazatelů, a tak každý prvek v segmentu je vlastně ukazuje na jeho odpovídající propojeného seznamu. Chcete-li se vrátit k tomuto schématu, uvidíte, že kbelíky samotné jsou šipky, ne skutečné uzly. Jednou ze základních vlastností hašovacích funkcí je, že jsou deterministické. To znamená, že pokud jste hash číslo 2, by měl vždy vrátit stejný kbelík. Každý hodnota, která jde do hash funkce, pokud by se opakovaly, musí dostat stejný index. Takže vaše hash funkce vrací index pole kde tato hodnota patří. Jak jsem již zmínil dříve, je stanovena počet segmentů, a tak si index, který se vrátit musí být menší, než je počet segmentů ale větší než 0. Důvodem, proč jsme hašovacích funkcí místo jen jedné propojeného seznamu nebo jeden jediný pole je to, že chceme být schopen skočit do určité části nejsnadněji pokud známe charakteristiku hodnoty - místo toho, aby museli prohledávat celého slovníku, budou moci přejít na určité části ní. Váš hash funkce by měla brát v úvahu, že v ideálním případě, Každý kbelík má přibližně stejný počet klíčů. Vzhledem k tomu, hash tabulka je série spojených seznamů, pak spojené seznamy sami budou mít více než jeden uzel. V předchozím příkladu, dvě různá čísla, i když nebyly stejné, když rozházeny, vrátí stejný index. Takže když máte co do činění se slovy, jedno slovo, když zatříděna by být stejná hodnota mřížky jako jiné slovo. To je to, co nazýváme kolizi, když máme uzel, který, když rozházeny, spojový seznam v tomto segmentu není prázdný. Technika, která nazýváme je lineární snímání, kde jdete do propojeného seznamu a pak najít místo, kde chcete vložit tento uzel protože máte kolizi. Můžete vidět, že tam by mohlo být trade-off, že jo? Pokud máte velmi malou hash tabulky, velmi malý počet segmentů, pak budete mít spoustu kolizí. Ale pak, pokud uděláte velkou hash tabulky, budete pravděpodobně k minimalizaci kolizí, ale to bude velmi velké datové struktury. Tam to bude kompromisy s tím. Takže když jste provedli PSet, zkuste si pohrát mezi možná dělat menší hash tabulky ale pak s vědomím, že to bude trvat trochu déle procházet jednotlivé prvky z těchto propojených seznamů. 

Co zatížení se chystá udělat, je iteraci každé slovo ve slovníku. To projde ukazatel na soubor slovníku. Takže budete využívat souboru I / O funkcí, které ovládají v pset4 a iteraci každé slovo ve slovníku. Chcete-každé slovo ve slovníku, aby se stal nový uzel, a budete umístit každý z těchto uzlů uvnitř vašeho slovníku datové struktury. Kdykoliv dostanete nové slovo, víte, že to bude stát uzel. Takže můžete jít hned a malloc uzlu ukazatel pro každou novou slovo, které jste. Tady jsem volá mé uzlu ukazatel new_node a já mallocing co? Velikost uzlu. Pak si přečíst aktuální řetězec ze souboru, protože slovník je ve skutečnosti uložena slovem a pak nový řádek, co můžeme využít je funkce fscanf, přičemž soubor je slovník soubor, který jsme prošel v roce, tak to skenuje soubor pro řetězce a místa, která řetězec do posledního argumentu. Pokud si vzpomenete, zpět k jednomu z přednášek, když jsme šli přes a druh loupané vrstvy zpět na knihovně CS50, Viděli jsme implementaci fscanf tam. Chcete-li se vrátit do fscanf, máme soubor, který jsme čtení z, hledáme pro řetězec v tomto souboru, a pak jsme uvedení do tady mám new_node-> slovo, protože new_node je uzel ukazatel, není aktuální uzel. Takže říkám new_node, chci jít do uzlu, že to ukazuje na a pak přiřadit tuto hodnotu na slovo. Chceme, aby pak toto slovo a vložte jej do hash tabulky. Uvědomte si, že jsme udělali new_node uzlu ukazatel protože budeme chtít vědět, co adresa tohoto uzlu je když se vložit do proto, že struktura uzlů samotných, v struct, je to, že mají ukazatel na nový uzel. Takže to, co je adresa tohoto uzlu jít poukázat na? Tato adresa bude new_node. Dává to smysl, proč děláme new_node uzlu * na rozdíl od uzlu? Dobře. Máme slovo. Tato hodnota je new_node-> slovo. , Který obsahuje slovo ze slovníku, které chceme na vstup. Takže to, co chceme udělat, je chceme nazývat naši hash funkce na tomto řetězci protože naše hash funkce má v řetězci a vrátí nám celé číslo, kde, že číslo je index, kde Hashtable v tomto indexu představuje tento kbelík. Chceme, aby se tento index a pak jít do toho indexu hash tabulky a pak použít tento spojový seznam pro vložení uzlu na new_node. Pamatujte si, že se však se rozhodnete vložit své uzel, ať už je to ve středu, pokud chcete řadit jej nebo na začátku nebo na konci, jen se ujistěte, že vaše poslední uzel vždy ukazuje na NULL protože to je jediný způsob, jak víme, kde poslední prvek našeho propojeného seznamu je. 

Pokud je velikost celé číslo, které představuje počet slov ve slovníku, pak jeden způsob, jak to udělat, je to, že vždy, když se nazývá velikost projdeme každý prvek v naší hašovací tabulce a pak iterovat každého propojeného seznamu v hash tabulce a potom vypočítat délku, že zvýšení naší čítač 1 do 1. Ale pokaždé, když velikost se nazývá, že to bude trvat dlouho protože budeme mít lineárně snímání každý spojový seznam. Místo toho, to bude mnohem jednodušší, pokud budete mít přehled o tom, kolik slov jsou předávány palců Takže pokud jste například počítadlo přímo ve Vašem zatížení funkce to, že aktualizace je to nutné, pak čítač, pokud ji nastavit na globální proměnné, budou moci být přístupné velikosti. Takže to, co velikost by prostě udělat, je v jedné linii, stačí se vrátit hodnotu čítače, velikost slovníku, který jste již zabýval v zatížení. To je to, co jsem měl na mysli, když jsem říkal, že když se rozhodnete zatížení v užitečné způsobem, pak velikost bude docela snadné. 

Takže teď jsme si to ověřit. Nyní máme co do činění se slovy ze souboru vstupního textu, a tak budeme měly ověřovat, zda všechny ty vstupních slov jsou vlastně ve slovníku, nebo ne. Podobně jako Scramble, chceme, aby pro případ necitlivosti. Chcete, aby se ujistil, že všechna slova prošel v roce, i když jsou smíšený případ, při volání se smyčcovým porovnání, jsou rovnocenné. Slova v souborech slovníku textového jsou vlastně všichni malá. Další věc je, že můžete předpokládat, že každé slovo prošel v roce, každý řetězec, se bude buď v abecedním nebo obsahují apostrofy. Apostrofy se bude platné slova v našem slovníku. Takže pokud máte slovo s apostrof S, to je skutečný legitimní slovo ve vašem slovníku že to bude jeden z uzlů ve vašem tabulky hash. Kontrola pracuje s pokud slovo existuje, pak to musí být v naší hašovací tabulce. Je-li slovo ve slovníku, pak všechna slova ve slovníku, jsou v hash tabulce, tak se pojďme podívat na tohoto slova v hash tabulce. Víme, že od té doby jsme realizovali náš hash funkce tak, že každá jedinečná slovo vždy zatříděna na stejnou hodnotu, pak víme, že místo prohledávání našeho celého hash tabulky, můžeme skutečně najít propojený seznam, který toto slovo by mělo patřit k. Pokud to bylo ve slovníku, pak by to bylo v tomto bloku. Co můžeme dělat, když slovo je název našeho řetězce prošel v, můžeme jen hash, že slovo a pohled na propojeném seznamu při hodnotě Hashtable [hash (slovo)]. Odtud, co můžeme udělat, je, že jsme menší podmnožinu uzlů pro vyhledávání tohoto slova, a tak můžeme přejít propojeného seznamu, na příkladu z dříve v návodu, a pak volat řetězec porovnání na slovo všude tam, kde je kurzor ukazuje na, to slovo, a zjistit, zda jsou tyto. V závislosti na způsobu, jakým jste organizovat svůj hash funkce, pokud je to seřazena, měli byste být schopni vrátit false něco dříve, ale pokud je to netříděný, pak budete chtít pokračovat křížení přes propojeného seznamu dokud nenajdete poslední prvek seznamu. A pokud jste ještě nenašli slovo v době, kdy jste dosáhli konce propojeného seznamu, to znamená, že vaše slovo neexistuje ve slovníku, a tak to slovo je neplatný, a kontrola by měl vrátit false. 

Nyní se dostáváme k uvolnění, kde chceme osvobodit všechny uzly, které jsme malloc'd, tak bez všech uzlů uvnitř našeho stolu mřížky. Budeme chtít, aby iteraci přes všechny propojených seznamů a zdarma všechny uzly v tom. Podíváte-li se výše v návodu k příkladu, kde jsme uvolnit propojeného seznamu, pak budete chtít zopakovat tento proces pro každý prvek v hash tabulce. A já budu jít přes tento na konci návodu, ale Valgrind je nástroj, kde můžete vidět, pokud jste správně osvobodil každý uzel, který jste malloc'd nebo cokoliv jiného, ​​co jste malloc'd, jiné ukazatel. Tak to je hashovací tabulky, kde máme konečný počet segmentů a hash funkce, která bude mít hodnotu a pak přiřadit tuto hodnotu do určité kbelíku. 

Nyní se dostáváme k pokusech. Pokusí druh vypadají takto, a já také čerpat z příkladu. V podstatě, máte celou řadu potenciálních dopisů, a pak kdykoli budete budovat slovo, že dopis může být spojeno za slovníku na širokou škálu možností. Některá slova začít s C, ale pak pokračovat s, ale jiní pokračují s O, například. Trie je způsob vizualizace všech možných kombinací těchto slov. Trie se bude sledovat sledu písmen, které tvoří slova, odbočení pokud je to nutné, když je jedno písmeno následovat násobek písmen, a na konci uvést v každém bodě, zda tento výraz je platná nebo ne protože pokud jste hláskovat slovo MAT, MA nemyslím si, že je platný slovo, ale MAT je. A tak v trie, by to znamenat, že po MAT, že je to vlastně platné slovo. Každý uzel v našem trie je vlastně bude obsahovat řadu uzlů ukazatelů, a budeme mít, konkrétně 27 z těchto uzlů ukazatelů, jeden pro každé písmeno v abecedě, stejně jako Apostrof. Každý prvek v tomto poli je samo o sobě bude ukazovat do jiného uzlu. Takže, pokud tento uzel je NULL, v případě, že je to nic po tom, pak víme, že tam žádné další písmena v tomto slově pořadí. Ale pokud tento uzel není NULL, znamená to, že existuje více písmen v tomto dopise pořadí. A pak dále, každý uzel označuje, zda je to poslední znak slova, nebo ne. 

Pojďme do příkladu trie. Nejprve jsem mít prostor pro 27 uzlů v tomto poli. Mám-li slovo BAR - Mám-li slovo BAR a chci vložit, že v, první písmeno je B, takže pokud má trie je prázdný, B je druhé písmeno v abecedě, takže budu volit, aby to tady v tomto indexu. Budu mít B zde. B bude uzel, který ukazuje na jiného pole všech možných znaků že může následovat po písmenem B. V tomto případě, se zabývám slovem BAR, takže půjdou sem. Po, mám dopis R, tak pak nyní ukazuje na vlastní kombinaci, a pak R bude tady. BAR je úplné slovo, takže pak budu mít R bod do jiného uzlu , který říká, že toto slovo je platné. To je uzel také bude mít řadu uzlů, ale ty by mohly být NULL. Ale v podstatě, může pokračovat takhle. To bude trochu jasnější, když jsme šli do jiného příkladu, takže stačí mít s sebou tam. Nyní máme BAR uvnitř našeho slovníku. Nyní, že máme slovo Baz. Začneme s B, a už máme B jako jeden z dopisů, které v našem ceníku. To je následoval s A. Máme už. Ale pak místo, máme Z následující. Takže prvkem v našem poli se bude Z, a tak, že jeden pak bude poukázat na jinou platnou konec slova. Takže vidíme, že když budeme pokračovat přes B a pak, existují dvě různé možnosti v současné době v našem slovníku pro slova, která začínají B a A. Řekněme, že bychom chtěli vložit slovo foobar. Pak bychom udělat vstup na F. F je uzel, který ukazuje na celou řadu. Rádi bychom vás O, jděte na O, O a pak spojuje do celého seznamu. Měli bychom B a pak pokračovat, měli bychom a pak R. Takže foobar prochází celou cestu dolů, dokud foobar je správné slovo. A tak pak by to bylo platné slovo. Teď říkají, naše další slovo ve slovníku je vlastně slovo FOO. Měli bychom říci, F. Co bude následovat, F? Vlastně jsem již prostor pro O, takže budu pokračovat. Nepotřebuju, aby se nový. Pokračovat. FOO je platná slovo v tomto slovníku, tak pak budu uvádět že je platná. Kdybych přestala jsem sekvenci tam, to by bylo správné. Ale pokud jsme pokračovali v pořadí od FOO až B a prostě musel FOOB, FOOB není slovo, a to není uvedeno jako platnou. V trie, jste každý uzel označující, zda je to platné slovo, nebo ne, a pak každý uzel má také řadu 27 uzlu ukazatelů , které pak přejděte na uzly samotných. 

Zde je způsob, jak na to, jak budete chtít definovat to. Nicméně, stejně jako v hash tabulce příkladu, kde jsme měli uzlu * hlavu k označení začátku našeho propojeného seznamu, budeme také chtít nějaký způsob, jak vědět, kde je počátek našeho trie je. Někteří lidé říkají, se snaží stromy, a to je místo, kde kořen pochází. Takže chceme kořen našeho stromu, aby se ujistil, že jsme zůstat uzemněný tam, kam naše trie je. Už jsme trochu přešel jak byste mohli přemýšlet o nakládání každé slovo do slovníku. V podstatě, pro každé slovo budete chtít iterovat svého trie a věděl, že každý prvek u dětí - říkali jsme, že děti v tomto případě - odpovídá jiným písmenem, budete chtít zkontrolovat tyto hodnoty v tomto konkrétním indexu, který odpovídá písmeno. Takže myslet celou cestu zpátky k Caesarovi a Vigenère, s vědomím, že každý dopis si můžete druh mapy zpět na index abecedy, Rozhodně až Z bude docela snadné mapovat abecední dopis, ale bohužel, apostrofy jsou také přijímaný znak ve slovech. Nejsem si ani jistý, co ASCII hodnota je, tak na to, pokud chcete najít index rozhodnout, zda chcete, aby to bylo buď první nebo poslední, budete muset pevný kódované šek na které a pak dát, že v indexu 26, například. Takže pak jste kontrolou hodnoty u dětí [i] kde [i] odpovídá na cokoliv písmeno jste na. Pokud je to NULL, to znamená, že není v současné době případné dopisy vyplývající z předchozího sekvence, takže budete chtít malloc a vytvořit nový uzel a mít děti, že [i] přejděte na ni takže můžete vytvořit - když jsme vložili dopis do obdélníku - Díky dětem non-NULL a bod do tohoto nového uzlu. Ale pokud to není NULL, jako v našem případě z FOO když už jsme měli foobar, budeme pokračovat, a my se nikdy dělat nový uzel, ale jen nastavit is_word na hodnotu true Na konci tohoto slova. 

Takže stejně jako předtím, protože zde máte co do činění s každým dopisem v době, to bude pro vás jednodušší pro velikost, místo toho, aby výpočet a projít celý strom a vypočítat, kolik dětí mám a pak odbočení, vzpomněl kolik jsou na levé straně a na pravé straně a podobné věci, to bude mnohem jednodušší pro vás pokud jste právě sledovat, kolik slov jste tím, že do když máte co do činění s nákladem. A pak se to tak velikost může jen návrat globální proměnné velikosti. 

Nyní se dostáváme k zkontrolovat. Stejných standardů jako dříve, kde chceme, aby pro případ necitlivosti. Stejně, my předpokládáme, že řetězce jsou jen abecední znaky nebo apostrofy protože děti je pole 27 dlouhé, takže všechny písmena abecedy plus apostrof. Pro kontrolu toho, co budete chtít udělat, je, že budete chtít začít u kořene protože kořen bude ukazovat na pole, které obsahuje všech možných výchozích písmen slova. Budeš začít tam, a pak budete kontrolovat, je tato hodnota NULL nebo ne, protože pokud je hodnota NULL, to znamená, že ve slovníku nemá žádné hodnoty které obsahují ten dopis v tomto konkrétním pořadí. Pokud je to NULL, pak to znamená, že toto slovo je chybně hned. Ale pokud to není NULL, pak můžete pokračovat, říci, že první písmeno je možné první písmeno ve slově, tak teď chci zkontrolovat, zda druhý dopis, že sekvence, je v mém slovníku. Takže se chystáte jít do indexu děti na prvním uzlu a zkontrolujte, zda druhý dopis existuje. Pak si opakovat, že proces zkontrolovat, zda posloupnost je platná nebo ne ve vaší trie. Kdykoliv uzel děti na to, že indexových bodů na hodnotu NULL, Víte, že posloupnost neexistuje, ale pak, když se dostanete na konec slova, které jste vloženy, pak chcete zkontrolovat teď, že jsem dokončil tuto sekvenci a zjistil, že je v mém trie, je to, že slovo platí, nebo ne? A pak se budete chtít zkontrolovat, zda, a to je, když, pokud jste zjistili, že posloupnost, pak chcete zkontrolovat, zda slovo je platná nebo ne protože Vzpomínám si v předchozím případě, že jsem nakreslil, kde jsme měli FOOB, , který byl platný sekvence, které jsme našli, ale nebyla skutečná platné slovo samo o sobě. 

Podobně, pro vyložit v pokusech, které chcete uvolnit všechny uzly ve vašem trie. Promiňte. Podobně jako hash tabulky, kde v vyložit jsme osvobodil všechny uzly, v pokusech, které chceme také uvolnit všechny uzly. Uvolnit bude skutečně fungovat nejjednodušší zdola nahoru protože tyto jsou v podstatě spojené seznamy. Takže chceme se ujistit, že máme na všechny hodnoty a bez všechny z nich výslovně. Co budete chtít dělat, když pracujete s trie je cestovat až na dno a volný nejnižší možnou uzel první a pak se do všech těchto dětí a pak bez všech těch, nahoru a pak zdarma, atd. Něco jako zabývající se spodní vrstvou trie první a pak jít až nahoru, jakmile jste osvobodil všechno. Toto je dobrý příklad, kde rekurzivní funkce může hodit. Jakmile osvobodil spodní vrstvu vašeho trie, pak volat vyložit na to ostatní, Ujistěte se, že jste uvolnit každý mini - Můžete trochu představit, že jako mini pokusů. Takže máte kořen zde. Já jen zjednodušit tak, nemám k tomu 26 z nich. Takže budete mít tyto, a pak tito reprezentují sekvence slov kde všechny tyto malé kruhy jsou dopisy, které jsou platné posloupnosti písmen. Pojďme pokračovat jen trochu víc. Co budete chtít udělat, je zdarma spodní tady a pak zdarma tento a pak zdarma to jeden na dně před uvolnit horní jeden až sem protože pokud vás zcela zdarma, něco, co v druhé úrovni zde, pak skutečně přijdou tuto hodnotu zde. To je důvod, proč je to důležité v uvolnění pro trie, aby se ujistil, že jste uvolnit dno jako první. Co budete chtít udělat, je říct, pro každý uzel Chci vyložit všechny děti. 

Teď, když jsme pryč přes vyložit na hash tabulky metody, jakož i způsobu trie, budeme chtít podívat na Valgrind. Valgrind spustit s následujícími příkazy. Máte Valgrind-V. Jste kontrola všech netěsností při spuštění pravopisu, stejně to určitý text protože speller třeba, aby v textovém souboru. Takže Valgrind bude spusťte program, říct, kolik bytů si přiděleno, kolik bytů si osvobozen, a to vám řekne, zda jste osvobozen jen dost nebo zda jste to již dost, nebo někdy dokonce můžete přes-free, jako je volný uzel, který již byl osvobozen a tak se vrátíte chyby. Pokud používáte Valgrind, bude vám některé zprávy uvede, zda jste osvobozeni buď méně než dost, jen dost, nebo více než dost časů. 

Součástí této PSet, je to volitelná napadnout velkou tabuli. Ale když máme co do činění s těmito datovými strukturami je to docela zábavné vidět, jak rychle a jak efektivní vaše datové struktury může být. Má vaše hash funkce mají za následek hodně kolizí? Nebo je vaše velikost dat opravdu velký? Má to trvat hodně času projít? V protokolu o speller, že výstupy, kolik času budete používat pro načtení, kontrolovat, provádět velikosti, a vyložit, a tak ty jsou uloženy v The Big radě, kde můžete soutěžit proti svým spolužákům a někteří zaměstnanci se vidět, kdo má nejrychlejší pravopisu. Jedna věc, že ​​bych chtěl poznamenat, o hash tabulky je to, že tam jsou některé docela jednoduché hashovací funkce, které bychom mohli myslet. Například, máte 26 vědra, a tak každý kbelík odpovídá na první písmeno ve slově, ale že to bude mít za následek docela nevyvážené hash tabulky protože tam jsou hodně méně slov, které začínají s X než startu se M, například. Jeden způsob, jak jít o speller je, pokud chcete získat všechny ostatní funkce dolů, pak stačí použít jednoduchý hash funkce, aby mohli dostat váš kód běží a pak se vrátit zpět a změnit velikost vaší hash tabulky a definice. Existuje mnoho zdrojů na internetu pro hašovacích funkcí, a tak pro tento PSet je povoleno výzkum hash funkce na internetu o nějaké rady a inspiraci tak dlouho, jak se ujistit, citovat, kde jste získali. Rádo se stalo se podívat a interpretovat některé hash funkce, které najdete na internetu. Zpět na to, že můžete být schopni zjistit, jestli někdo použil trie zda je jejich realizace je rychlejší než váš hašovací tabulky nebo ne. Můžete odeslat The Big radě vícekrát. To bude zaznamenávat vaše poslední položku. Takže možná změníte funkci hash a pak si uvědomí, že je to vlastně mnohem rychleji nebo mnohem pomalejší než dříve. To je trochu zábavnou formou. Tam je vždy 1 nebo 2 zaměstnanci, kteří se snaží, aby se nejpomalejší možnou slovník, tak to je vždycky zábavné se dívat na. 

Použití pro PSet je spustit pravopisu s volitelným slovníku a pak povinný textový soubor. Ve výchozím nastavení při spuštění pravopisu se jen textového souboru a neurčíte slovník, to bude používat slovník textový soubor, toho velkého v cs50/pset5/dictionaries složce. Že jeden má více než 100.000 slov. Mají také malý slovník, který má podstatně méně slov že CS50 učinil pro vás. Nicméně, můžete velmi snadno stačí si jen vlastní slovník pokud si jen chcete pracovat v malých příkladech - Například, pokud chcete použít gdb a víte, že konkrétní hodnoty že chcete, aby vaše hash tabulka mapuje na. Takže stačí vytvořit svůj vlastní textový soubor jen s barem, Bazi, foo, a foobar, aby to v textovém souboru, oddělit ty, každý s 1 řádek, a pak vytvořit svůj vlastní textový soubor, který doslova obsahuje pouze možná 1 nebo 2 slova takže přesně víte, co výstup by měl být. Některé z ukázkových souborů textových, že Big Board při spuštění úkolu bude kontrolovat jsou Válka a mír a Jane Austen román nebo něco takového. Takže, když jste začínal, je to mnohem jednodušší, aby vaše vlastní textové soubory které obsahují jen pár slov nebo možná 10 takže můžete předvídat, co výsledek by měl být a ověřit si to proti tomu, aby více kontrolované příklad. A tak od té doby máme co do činění s předpovídání a kreslení věci kolem, jednou chci povzbudit, abyste se používat tužku a papír protože je to opravdu ti pomůže s tímhle - kreslení šipek, jak hash tabulka nebo jak se vaše trie vypadá, když jste uvolnění něco, kde se šipky jedete, se držíš na dost, vidíte nějaké odkazy mizí a pádu do propasti unikly paměti. Takže, prosím, zkuste nakreslit věci ještě předtím, než se dostanete k psaní kódu dolů. Nakreslete věci tak, že jste pochopili, jak se věci chodit do práce protože pak jsem zaručit, že budete spouštět do méně ukazatel muddles tam. 

Dobrá. Chci vám popřát hodně štěstí s tímto PSet. Je to asi nejtěžší. Tak zkuste začít brzy, kreslit věci, kreslit věci, a hodně štěstí. To bylo Návod 5. 

[CS50.TV]