>> ZAMYLA CHAN: Udělejme pravopisu.
Pokud otevřete speller.c, pak uvidíte, že většinu funkcí pro
kontrola textového souboru proti Slovník je již na vás.
. / Kontrola pravopisu, procházející ve slovníku textu souboru a pak další textový soubor,
bude kontrolovat, že textový soubor proti slovníku.
>> Nyní se slovníkem textové soubory obsahují platí slova, na každý řádek jednu.
Pak speller.c bude volat zatížení na slovníku textového souboru.
Je to volání funkce s názvem Podívejte se na každé slovo v zadaném textovém souboru,
tisk všech slov s chybným pravopisem.
>> Speller.c bude také volat Size určení počtu slov v
slovník a zavolejte Uvolnit uvolnit paměť.
speller.c bude také sledovat, jak hodně času se používá k provedení těchto
procesy, ale budeme se k tomu později.
>> Takže to, co musíme udělat?
Musíme vyplnit dictionary.c.
V dictionary.c, máme pomocníka Funkce Load, který načte
slovník.
Funkce Kontrola, která zkontroluje, zda dané slovo je ve slovníku.
Funkce vrací číslo Size slov ve slovníku.
A nakonec jsme Uvolnit, které osvobozuje slovník z paměti.
>> Tak za prvé, pojďme řešit zatížení.
Pro každé slovo ve slovníku textu soubor, zatížení bude ukládat tato slova
slovník datová struktura dle vašeho výběru, a to buď
hash tabulky nebo trie.
Půjdu na to jak v to projít.
>> Nejprve pojďme mluvit o hash tabulky.
Řekněme, že máte 10 kulečníkové koule a byste chtěli, aby jim uložit.
Ty by mohly dát je všechny do kbelíku, a když si potřeboval specifické
číslované koule, měli byste vzít jednu z nádoby v době
hledá pro tuto kouli.
A pouze 10 míčů, měli byste být schopni najít si míč v přiměřené
množství času.
>> Ale co když jste měli 20 koule?
To může trvat trochu déle, teď.
Co je 100?
1000?
Nyní by bylo mnohem jednodušší, pokud jste měli více kbelíky.
Možná, že jeden kbelík na míčky očíslovány nulu přes devět, další kbelík pro
koule číslovány 10 až 19, a tak dále.
>> Nyní, když jste potřebovali podívat se na konkrétní míč, mohl automaticky
jít na jednu konkrétní kbelíku a hledat prostřednictvím tohoto kbelíku.
A pokud každý kbelík má přibližně 10 koule, pak byste mohli snadno vyhledávat
přes něj.
>> Nyní, protože máme co do činění s slovníky, jediný kbelík pro
všechna slova ve slovníku bude pravděpodobně příliš málo kbelíky.
Takže pojďme se podívat na tabulky hash.
>> Ber to jako pole kbelíky.
A v tomto případě, kbelíky jsou naše spojové seznamy.
A budeme distribuovat všechny naše slova mezi těmito několika propojených seznamů v
organizovaný způsob, jak pomocí funkce hash, který nám řekne, které
lžíce daný klíč, vzhledem slovo, patří.
>> Pojďme představují to schematicky.
Modrá krabice zde obsahují hodnoty a červené krabičky poukazují na jinou hodnotu
ukazatel pár.
Zavoláme těchto dvojic uzlů.
Nyní, každý kbelík, jak jsem řekl, dříve, je spojový seznam.
V propojené seznamy, každý uzel má hodnotu, stejně jako ukazatel
další hodnota.
>> Nyní, zabývající se spojových seznamů, to je velmi důležité, aby vám
neztrácejí žádné odkazy.
A další je uvědomit si fakt, že poslední uzel, je-li to neukazuje na
jiný uzel, ukazuje na null.
>> Tak jak jsme se reprezentovat to v C?
Jsme zde definovat naši struct.
A hodnota je v tomto případě char pole délky.
Délka plus 1, kde délka je Maximální délka každého slova, plus 1 za
null terminátor.
A pak máme ukazatel na jiný uzel s názvem Next.
>> Takže pojďme udělat malou propojeného seznamu.
Za prvé, budete chtít, aby malloc váš uzel, které vytvářejí prostor v paměti
velikost vašeho typu uzlu.
A provést další uzel, znovu mallocing.
>> Nyní, pokud chcete přiřadit hodnotu slovo, pak bychom mohli říci, UZEL1 šipku
slovo rovno "Dobrý den." Tento operátor šipka dereferences ukazatel a
přistupuje proměnné struct je.
Tímto způsobem, nemusíme používat jak tečka a provozovatel hvězda.
>> Tak jsem si node2 šipka slovo rovno "Svět." A tam, hodnoty jsou
naplněna v mých uzlů.
Chcete-li odkazy, předám v node1 šipku, přístup uzel hvězdu,
že ukazatel uzel, rovná node2, ukázal node1 node2 dva.
A tady máme propojeného seznamu.
>> Takže to byl jen jeden spojový seznam, ale hash tabulka je celá řada
spojové seznamy.
No, budeme mít stejný uzel strukturu jako předtím.
Ale pokud jsme chtěli skutečnou hash tabulky, pak můžeme jen aby ukazatel uzlu
array zde.
Například, velikost 500.
>> Nyní oznámení, že to bude obchod off mezi velikostí svého
hash tabulky a velikost vaše spojových seznamů.
Pokud máte opravdu velký počet kbelíky, představoval si museli běžet zpátky
a dále v souladu s najít svůj kbelík.
Ale také nechci malý počet lopat, protože pak jsme zpátky
původní problém, jak s příliš mnoho míčů v naší kbelíku.
>> OK, ale tam, kde se naše míč jít?
No, musíme nejprve mít míč, ne?
Takže pojďme malloc uzel pro každý nové slovo, které máme.
uzel * new_node rovná malloc (sizeof (node)).
>> Nyní, když máme tuto strukturu, jsme můžete skenovat pomocí funkce
fscanf, řetězec z našeho souboru, pokud to je soubor slovníku, do
new_node šipka slovo, kde new_node arrow slovo je naše
cílem tohoto slova.
>> Dále budeme chtít hash, že Slovo pomocí hash funkce.
Hašovací funkce má řetězec a vrátí index.
V tomto případě, má index být menší, než je počet
kbelíky, které máte.
>> Nyní, hashovací funkce, když se snažíte najít jeden a vytvořit jednu z
vlastní, pamatujte, že musí být deterministický.
To znamená, že stejná hodnota musí Pro na stejnou nádobu pokaždé
že jste to hash.
>> Je to něco jako knihovna.
Když budete mít knihu, založenou na autor, víte, které police by měla
dál, ať už je to číslo police jeden, dva, nebo tři.
A že kniha bude vždy patřit na buď police jeden, dva, nebo tři.
>> Takže, pokud new_node šipka Slovo má Slovo z vašeho slovníku, pak
hash new_node šipka slovo bude nám index
kbelík tabulky hash.
A pak budeme vkládat, že do toho specifické spojový seznam indikována
vrátí hodnotu naší hash funkce.
>> Podívejme se na příklad vložení uzlu do
začátek propojeného seznamu.
Je-li hlava je uzel ukazatel, který naznačuje, počátek souvisí
seznam, a new_node indikuje nové uzel, který chcete zadat v, jen
přiřazení hlavu, aby new_node ztratí odkaz na zbytku seznamu.
Takže nechceme to dělat.
>> Spíše chceme, aby se ujistil, že máme na každý
jeden uzel v našem programu.
Takže běh new_node šipku vedle rovná hlava a pak hlava rovná new_node
zachová všechny odkazy a neztratily nic.
>> Ale co když chcete, aby váš seznam být dále, protože když řazeny spojené
Seznam by mohl být jednodušší hledání na později?
No, na to, že budete potřebovat vědět, jak přejít propojené seznamy.
>> Chcete-li procházet spojový seznam, pojďme se uzel ukazatel, uzel *, působit jako
kurzor, označující, do kterého uzlu jste na, počínaje
na první prvek.
Opakování, dokud kurzor je null, můžeme provádět určité procesy a pak
posuňte kurzor, když potřebujeme pomocí kurzoru šipky hodnoty.
>> Pamatujte si, že to je totéž jako říká hvězda kurzor, dereferencing
kurzor, poté pomocí dot hodnota operátor.
Tak aktualizace kurzor je přiřazením kurzor na šipku vedle kurzoru.
>> Řekněme, že zjistíte, že D se v mezi C a E. Pro vložení uzlu,
mají new_node D přejděte na uzel E, což je další kurzor.
A pak C, kurzor, pak může ukázat až D. Tímto způsobem můžete udržovat seznam.
Dávejte pozor, abyste neztratili své odkazy podle pohybem kurzoru šipku vedle D
hned.
>> Dobrá.
Tak to je, jak byste mohli vložit uzly, vkládejte do, zatížení slova do těch
uzly, a vložte je do hash tabulky.
Takže teď se pojďme podívat na pokusech.
>> V trie, bude každý uzel obsahovat pole uzlu ukazatelů, jeden pro každý
písmeno v abecedě a apostrof.
A každý prvek v poli bude ukazovat na jiný uzel.
Je-li, že uzel je null, pak ten dopis se nebude příští dopis
nějaké slovo v pořadí, protože každá Slovo označuje, zda je to poslední
znak slova, nebo ne.
>> Pojďme se podívat na diagramu.
Doufejme, že to bude být trochu jasnější.
V tomto diagramu vidíme, že pouze některé dopisy a některé podřetězce
jsou uvedeny ven.
Takže můžete sledovat určité cesty, a všech těchto cest vás dovede k
různá slova.
>> Tak jak jsme se reprezentovat to v C?
No, každý uzel je nyní bude mít Logická hodnota označující, zda
že uzel je konec dané slovo, nebo ne.
A pak to bude mít také řadu ukazatele uzlu pojmenovaném děti, a
tam se bude 27 z nich.
A pamatujte, budete také chtít, aby sledovat svého prvního uzlu.
Budeme říkat, že kořen.
>> Tak to je struktura trie.
Jak můžeme reprezentovat tento jako slovník?
No, načítání slova, pro každý slovník slovo, budete chtít
iterovat trie.
A každý prvek u dětí odpovídá jiné písmeno.
>> Takže kontrola hodnoty na děti index i, kde i představuje
specifický index dopisu, který se snažíte vložit.
No, pokud je to null, pak budete chtít malloc nový uzel a mít děti
i poukazují na tomto uzlu.
>> Pokud to není null, pak to znamená, že že vzhledem k tomu větev, že vzhledem
podřetězec, již existuje.
Takže pak budete jen přesunout do které nový uzel a pokračovat.
Pokud jste na konci slova, které se snažíte načíst do
slovník, pak si můžete nastavit, aby aktuální uzel, který jste na true.
>> Takže pojďme se podívat na příklad vložení slovo "fox" do našich
slovník.
Předstírat, že začneme s prázdný slovník.
První písmeno, F, budou umístěny u dětí indexu pět z kořenů
děti pole.
Takže vložíme že palců
>> Písmeno O se pak u dětí index 15, po tomto F. A pak X
bude ještě nižší, větvení off dětí Õ je.
A pak, protože X je poslední písmeno slova "liška", pak budu
barva, která zeleně na znamení, že to je konec slova.
V jazyce C, který by nastavení je Word Boolean hodnoty skutečné.
>> Teď co když další slovo, které jste načítá se je slovo "foo"?
No, nemusíte se malloc víc prostor pro F nebo O, protože
těch, které již existují.
Ale poslední O v foo?
To je jeden, budete muset malloc.
Vytvořte nový uzel pro to, že nastavení je slovo, Boolean true.
>> Takže teď pojďme vložit "psa." Pes bude začít s indexem tři z kořenů
děti, protože D nemá nebyly vytvořeny.
A budeme sledovat podobný proces jako před, vytváření podřetězec psa,
kde je G je v zelené barvě, protože to je konec slova.
>> A teď, co když chceme vložit "dělat"?
No, to je podřetězec psa, tak nepotřebujeme k malloc už.
Ale my potřebujeme ukázat, kde máme došli na konec tohoto slova.
Takže O bude v zelené barvě.
Pokračování tohoto procesu pro každý slovo ve slovníku, jste
naložili je do do buď do hash tabulky nebo na trie.
>> speller.c přejdou v řetězcích pro dictionary.c pro kontrolu.
Nyní, Kontrola funkce musí pracovat v případě necitlivosti.
To znamená, že velká písmena a malá písmena a mix obou
všichni měli rovnat true, pokud některý Kombinace, které je v
slovník.
Můžete se také předpokládat, že řetězce jsou jen bude obsahovat abecední
znaky nebo apostrofy.
>> Tak se pojďme podívat na to, jak byste mohli zkontrolovat, se strukturou hash tabulky.
No, pokud existuje slovo, pak to jsou uvedeny v tabulce hash.
Takže pak se můžete pokusit zjistit, že slovo v daném bloku.
>> Tak který kbelík by to slovo bylo v?
No, měli byste dostat číslo, že index z kbelíku, hešováním toto slovo
a pak vyhledávání v tomto provázaném seznamu, procházející přes celý
spojový seznam, pomocí String Porovnání funkci.
>> Pokud konec spojového seznamu je dosaženo, což znamená, že kurzor
dosáhne null, pak slovo není lze nalézt ve slovníku.
Nebude to v žádném jiném kbelíku.
Tak tady můžete vidět, jak by mohlo být kompromis mezi tím, a to buď
seřazeno spojové seznamy nebo ty netříděné.
Buď bude mít více času během při kontrole zatížení nebo více času.
>> Jak můžete zkontrolovat v struktura trie?
Budeme se pohybovat směrem dolů v trie.
Pro každé písmeno v zadaném slově že budeme kontrolovat, půjdeme na to
odpovídající prvek dětí.
>> Je-li tento prvek je null, pak to znamená, že neexistují žádné substrings
obsahující naší vstupní slovo, tak slovo je chybně.
Pokud to není null, můžeme přesunout do další písmeno slova, které jsme
kontrolu a pokračovat v tomto procesu až se dostaneme na konec
vstupního slova.
A pak můžeme zkontrolovat Je-li slovo je pravda.
Pokud ano, pak skvělé.
Slovo je pravda.
Ale i kdyby ne, i přesto, že podřetězec existuje v trie, slovo je
chybně.
>> Je-li funkce volána velikost, velikost by měl vrátit počet slov, která
jsou v daném slovníku datová struktura.
Takže pokud používáte hash tabulky, můžete Můžete buď projít každý
spojový seznam se každý kbelík počítání počtu
slov jsou tam.
Pokud používáte trie, můžete projít všechny non null
Cesta v trie.
Nebo když jste načítání slovníku v, možná můžete sledovat, jak
mnoho slov jste nahrává palců
>> Jakmile speller.c dokončí kontrolu textový soubor proti slovníku, pak
to udělat, a tak to volá Uvolnit, kde Vaším úkolem je osvobodit nic
že jste malloced.
Takže pokud používáte hash tabulku, pak se musí být obzvláště opatrní, aby se zabránilo
paměťové úniky informací ze strany není uvolnění nic předčasně a drží na každém
single link Před zdarma.
>> Takže pro každý prvek v tabulce hash a pro každý uzel v propojeném seznamu
budete chtít osvobodit, aby uzel.
Jak se vám jít o uvolnění spojový seznam?
Nastavení vašeho uzlu ukazatel myši na hlavy, na začátku roku
spojový seznam, a pak, když kurzor není null, můžete nastavit dočasný
uzel ukazatel kurzoru.
Potom posuňte kurzor.
A pak se můžete uvolnit, že dočasný hodnotu, zatímco stále drží na
vše později.
>> Co když používáte trie?
Pak je nejlepší způsob, jak to udělat je vyložit z velmi
zdola nahoru.
Tím, že cestuje na nejnižší možné uzel, můžete uvolnit všechny ukazatele v
že děti a pak s návratem nahoru, uvolní všechny prvky ve všech
z dětských pole, do můžete trefit horní kořenový uzel.
Zde je místo, kde Rekurze přijde vhod.
>> Abyste se ujistili, že jste pravděpodobně uvolněno vše, co jste malloced,
můžete použít Valgrind.
Spuštění Valgrind poběží program počítání, kolik bajtů paměti
používáte, a ujistěte se, že jste osvobodil všechny, říkám
kde byste mohli mít zapomněli zdarma.
Tak běžte, že i po Valgrind vám řekne, a dává vám do toho, pak
jste skončil vyložit.
>> Nyní, pár tipů před odjezdem off a začít provádět svůj
slovník.
Já bych doporučil projít v menší slovník, když se snažíte testovat
věci a ladění s HDP.
Použití pravopisu je. / Pravopisu, volitelný slovník, a pak text.
>> Ve výchozím nastavení se nahraje do velký slovník.
Takže možná budete chtít projít v malých slovník, nebo dokonce vytvořit svůj
vlastní, přizpůsobení váš slovník a váš textový soubor.
>> A nakonec bych také doporučit vzít si tužku a papír a nakreslete
věci před, v průběhu a po jste napsali všechny vaše kódu.
Jen se ujistěte, že máte tyto ukazatele akorát.
>> Přeji Vám hodně štěstí.
A jakmile jste hotovi, pokud byste chtěli napadnout velkou tabuli a
vidět, jak rychle se váš program ve srovnání s svými spolužáky ", pak doporučuji
zkontrolovat, že ven.
>> Díky, že jsi skončil pravopisu PSet.
Jmenuji se Zamyla, a to je CS50.