>> [Predvaja glasba]
>> ROB Bowden: Hi.
Jaz sem Rob.
In kaj je to rešitev ven.
Torej, tukaj bomo izvajati Splošni pregled.
Vidimo, da struct node našega miza bo izgledala takole.
Tako se dogaja, da imajo char beseda matrika velikosti DOLŽINE + 1.
Ne pozabite + 1, saj je najvišja beseda v slovarju, je 45.
znake.
In potem bomo potrebovali eno dodatno znak za backslash nič.
>> In potem naša Hashtable v vsaki bucket se dogaja, da shranite
povezani seznam vozlišč.
Mi jim ne gre ravno sondiranje tukaj.
In tako, da se poveže na naslednji element v vedro, moramo
struct vozlišče * naslednji.
OK.
Torej, to je tisto vozlišče izgleda.
>> Zdaj tukaj je deklaracija naše Hashtable.
To se dogaja, da imajo 16.834 vedra.
Vendar pa ta številka res ni važno.
In končno, gremo, da imajo Globalna spremenljivka velikost Hashtable, ki
se dogaja, da začnete kot nič.
In to se dogaja, da bi spremljali, kako veliko besed so v našem slovarju.
>> Tako da je lahko pogled na obremenitve.
Opazili, da je obremenitev pa vrne bool.
Vam vrne true, če je bilo uspešno naložen, in false sicer.
In to traja char * slovarja ki je slovar
da želimo odpreti.
Tako da je prva stvar, ki bomo storili.
>> Bomo fopen Slovar za branje.
In bomo morali narediti prepričajte, da je uspelo.
Torej, če bi se vrnil NULL, potem nismo Uspešno odprite slovar.
In moramo vrne false.
Vendar ob predpostavki, da je to storila uspešno open, nato pa smo želeli prebrati
Slovar.
Tako da zanka, dokler ne bomo našli nekaj Razlog za prekinitev iz te zanke,
katerih bomo videli.
Tako da zanka.
>> In zdaj bomo malloc eno samo vozlišče.
In seveda moramo v zrak še enkrat preveriti.
Torej, če mallocing ni uspelo, nato pa smo želeli raztovoriti kateregakoli vozlišča, ki smo
se je zgodilo z malloc prej, zaprite slovar in vrne false.
Ampak ignoriranje, da ob predpostavki, da bomo uspelo, nato pa smo želeli uporabiti fscanf
se glasi eno samo besedo iz našega slovar v naše vozlišče.
Torej, ne pozabite, da vstop> beseda je char beseda buffer od velikosti LENGHTH + 1
da bomo za shranjevanje besedo prijavite
>> Torej fscanf se bo vrnil 1, dokler kot je bilo uspešno
prebrati besedo iz spisa.
Če katera napaka se zgodi, ali pa pridete do konca v spis,
ne bo vrnila 1.
V tem primeru se ne vrne 1, bomo na koncu bo izbruhne
to zanko, medtem ko.
Tako vidimo, da ko bomo imeli uspešno prebrati besedo v
Vpis> beseda, potem pa si bomo, da Beseda uporabo našega hash funkcijo.
>> Oglejmo si na hash funkcijo.
Tako da ne boste res potrebujejo razumeti.
In dejansko smo pravkar potegnil ta hash deluje iz interneta.
Edina stvar, morate priznati, je da to traja char * besedo.
Tako da je ob niz kot vložek, in vračanje nepodpisan int kot proizvodnja.
Tako, da je vse hash funkcija je, ali je prevzame na vhodu in vam
Indeks v Hashtable.
>> Opazimo, da smo moding jih NUM_BUCKETS, tako, da bi se vrnila vrednost
dejansko je indeks v Hashtable in ne indeks tistega
mejá matrike.
Torej, glede na to funkcijo, greva za razpršitev besedo, da smo prebrali
Slovar.
In potem bomo uporabili da hash vstaviti
vstop v Hashtable.
>> Zdaj Hashtable hash je trenutna povezani seznam v tabeli.
In to je zelo možno, da je to samo NULL.
Želimo, da vstavite svoj vstop na začetku tega povezani seznam.
In tako bomo imeli naši trenutni vstopna točka za kaj Hashtable
Trenutno kaže.
In potem bomo za shranjevanje, V Hashtable na
hash, trenutni vpis.
Torej ti dve vrstici uspešno vstavite Vpis na začetku
povezani seznam v tem indeksu v Hashtable.
>> Ko smo končali s tem, vemo, da smo našli še eno besedo
slovar, in smo spet prirastek.
Tako smo ostali storiti, dokler fscanf končno vrnil nekaj ne-1 pri
kateri točki se spomnite, da Sprostiti moramo vnos.
Torej, tukaj smo malloced vnos.
In smo se trudili, da preberete nekaj iz slovarja.
In nismo uspešno prebrati nekaj iz slovarja, v
tem primeru moramo osvoboditi vnos da ne bomo nikoli dejansko dana v
Hashtable, in končno prekinil.
>> Ko smo izbruhnejo moramo videti, dobro, smo izbruhnejo, ker tam
je bila napaka pri branju iz datoteke?
Ali pa smo izbruhnejo, ker smo dosegel konec datoteke?
Če je prišlo do napake, potem želimo, da se vrne false.
Ker obremenitev ni uspelo.
In v tem procesu želimo raztovoriti vse besede, ki jih preberejo in
zaprite datoteko slovarja.
>> Ob predpostavki, da nam ni uspelo, nato pa smo pravkar še vedno morali zapreti slovar
datoteko, in na koncu vrne true, saj smo uspešno naložen slovar.
In to je to za tovor.
Torej, zdaj preveriti, saj naložen Hashtable, bo izgledala takole.
Zato preverite, da vrne bool, ki je dogaja, da navedejo, ali opravil
V znakovnem * besedo, ali je opravil V nizu je v našem slovarju.
Torej, če je v slovarju, če je v našem Hashtable,
se bomo vrnili res.
In če ni, se bomo vrnili napačen.
>> Glede na to opravili v besedi, smo gre za razpršitev besedo.
Zdaj pomembna stvar, da priznajo, je da smo v obremenitvi vedeli, da so vsi
Besede, ki jih bomo lahko male črke.
Ampak tukaj nismo tako prepričani.
Če pogledamo našo hash funkcijo, naša hash funkcija dejansko
nižji ohišje vsak znak besede.
Torej, ne glede na kapitalizacijo beseda, naš hash funkcija je donos
istim indeksom za karkoli kapitalizacija je, kot bi imela
vrnjeni v celoti male črke različica besede.
V redu je.
To je naš indeks je v Hashtable za te besede.
>> Zdaj to zanko se bo Ponovil v povezanem seznamu
, ki je bil v tistem indeksu.
Torej opazili smo inicializacija vnos poudariti, da tega indeksa.
Bomo še naprej medtem ko vstop! = NULL.
In ne pozabite, da posodobitev kazalec V naš zapis povezave list = vnos> next.
Tako imamo trenutno dostopno točko Naslednji element v povezanem seznamu.
>> Torej, za vsak vpis v povezanem seznamu bomo uporabili strcasecmp.
To ni strcomp.
Ker še enkrat, želimo delati stvari zadevo insensitively.
Tako smo uporabili strcasecmp za primerjavo beseda, ki je predmet tega
Funkcija proti besedi da je v tej točki.
Če se ne vrne nič, kar pomeni, da ni bilo ujemanje, v tem primeru želimo
vrne true.
Uspešno smo ugotovili beseda v našem Hashtable.
>> Če ne bi bilo tekmo, nato pa smo spet bo zanke in pogled na
next entry.
In bomo še naprej loopinga medtem ko so navedbe v tej povezanem seznamu.
Kaj se zgodi, če razbijemo v to zanko?
To pomeni, da nismo našli vnos, ki ujema to besedo, v tem primeru
vrnemo false, ki označuje, da je naš Hashtable ne vsebujejo to besedo.
In to je ček.
>> Tako da je lahko pogled na velikost.
Zdaj velikost se bo zelo preprosta.
Ker se spomnim na obremenitve, za vsako besedo smo ugotovili, smo se poveča globalno
spremenljivka velikost Hashtable.
Torej funkcija velikost je le, da bo Za vrnitev globalno spremenljivko.
In to je to.
>> Zdaj končno moramo raztovoriti slovar, ko je vse končano.
Torej, kako bomo to storili?
Tukaj smo zanka preko vse vedra naši mizi.
Torej obstajajo NUM_BUCKETS vedra.
In za vsakega povezanega seznama v našem Hashtable, gremo v zanko
celota povezanega seznama, sprostitev vsak element.
>> Zdaj moramo biti previdni.
Torej, tukaj imamo začasno spremenljivko da je shranjevanje kazalec na naslednji
element v povezanem seznamu.
In potem bomo brezplačno trenutni element.
Moramo biti prepričani, da bomo to naredili, ker smo Ne moreš sprostiti trenutni element
in nato poskusite za dostop do naslednjega kazalec, ker ko smo ga osvobodili,
spomin postane neveljaven.
>> Zato moramo ohraniti okoli kazalec Naslednji element, potem bomo lahko osvobodi
Sedanji element, in potem bomo lahko posodobite Naš trenutni element, da kaže na
Naslednji element.
Bomo zanko, medtem ko obstajajo elementi V tem povezani seznam.
To bomo storili za vse povezane Seznam v Hashtable.
In ko sva končala s tem, ki smo jih celoti raztovoriti Hashtable in
končali smo.
Zato je nemogoče za razkladanje da se kdaj vrne false.
In ko bomo končali, smo pravkar vrnil res.
>> Dajmo ta rešitev poskusiti.
Torej, vzemimo si oglejte, kaj naše struct vozlišče bo izgledal.
Tukaj vidimo, da bomo imeli bool Beseda in struct node * otroci
Nosilec abecede.
Torej prva stvar, ki jo lahko sprašujete, zakaj je abeceda
ed definirana kot 27?
No, ne pozabite, da bomo potrebovali da se ravnanje opuščaj.
Tako da se dogaja, da se nekoliko Poseben primer v celotnem programu.
>> Zdaj se spominjam, kako Trie dejansko deluje.
Recimo, da smo indeksiranje besedo "mačke". Nato pa iz korena Trsta,
bomo pogled na otroke matrika, in gremo pogledati
Indeks, ki ustreza črko C. tako da bo indeksirajo 2.
Torej, glede na to, da bo nam dajejo novo vozlišče.
In potem bomo delati iz tega vozlišča.
>> Torej, glede na to vozlišče, smo še enkrat bo pogled na otroke matrike.
In bomo pogled na indeks ničelni ustrezati A v mačka.
Potem smo šli na to vozlišče, in glede na to, da je vozlišče greva
gledati na koncu je to ustreza na T. in se gibljejo na to vozlišče,
Nazadnje smo popolnoma videti skozi naša beseda "mačka". In zdaj bool
Beseda naj bi kazali, ali ta dana beseda je pravzaprav beseda.
>> Torej, zakaj potrebujemo to poseben primer?
No, kaj je beseda "katastrofa" V našem slovarju, vendar
Beseda "mačka", ne?
Tako in je videti, da vidim, če je beseda "mačka" je v našem slovarju, smo
bo uspešno odmisliti indeksi C-T v regiji vozlišče.
Ampak to je samo zato, ker katastrofa se je zgodilo, da ustvarite vozlišč na poti
iz C-A-T, vse do Konec besede.
Torej je bool beseda uporablja za označevanje, ali To posebno mesto
dejansko kaže na besedo.
>> Vse je v redu.
Torej sedaj, da vemo, kaj je Trie je bo izgledal, si oglejmo
naložiti funkcijo.
Torej obremenitev se bo vrnil bool Za ugotovitev, ali smo uspešno ali
neuspešno naložen slovar.
In to se bo slovar ki jih želimo naložiti.
>> Torej prva stvar, ki smo storiti je odprt do tega slovarja za branje.
In moramo zagotoviti, nismo uspe.
Torej, če slovarju ni bilo uspešno odprta, se bo vrnil
null, v tem primeru smo vrača false.
Vendar ob predpostavki, da je uspešno odprt, potem lahko dejansko prebral
s pomočjo slovarja.
>> Torej prva stvar, ki jo bomo želite storiti, je, moramo to
Globalna spremenljivka korenina.
Zdaj koren se bo vozlišče *.
To je vrh naše Trsta, da smo bodo ponavljanjem skozi.
Torej prva stvar, ki jo bomo bi želeli storiti, je dodeliti
pomnilnik za naše korenine.
Opazimo, da smo s pomočjo calloc funkcija, ki je v bistvu enak
kot funkcije malloc, razen, da je zagotovljeno, da se vrnete nekaj, kar je
popolnoma nulo.
Torej, če smo uporabili malloc, bi morali iti skozi vse napotke v našem
vozlišče, in poskrbite, da oni so vsi null.
Tako da bo calloc naredil za nas.
>> Zdaj pa tako kot malloc, moramo narediti prepričani, da je bila dodelitev dejansko
uspešna.
Če je ta vrnil nič, potem smo morali zapreti ali slovar
datoteko in vrne false.
Torej, ob predpostavki, da se dodelitev je bila uspešna, bomo uporabili vozlišče *
kazalec za ponovitev prek našega Trsta.
Tako da naše korenine nikoli ne bo spremenilo, ampak bomo uporabili kazalec na
dejansko šel od vozlišča do vozlišča.
>> Torej, v to zanko, smo branje skozi slovarju datoteke.
In smo z uporabo fgetc.
Fgetc se dogaja, da zgrabite single lik iz spisa.
Bomo še naprej vzbujajoči znakov, medtem ko mi ne dosežejo
konec datoteke.
>> Obstajata dva primera, moramo ravnati.
Prvič, če znak ni nova linija.
Torej vemo, če je bila nova linija, nato smo na tem, da se premaknete na novo besedo.
Vendar ob predpostavki, da ni bilo novo linijo, nato pa Tukaj smo želeli ugotoviti,
Indeks bomo indeksa v V otroški matriki, ki
smo pogledal prej.
>> Torej, kot sem rekel prej, moramo Poseben primer opuščaj.
Opazili smo, da uporabljate trojnim Operater tukaj.
Torej bomo prebrali, da je to, če lik beremo v bilo
opuščaj, potem pa gremo, da nastavite indeks = "abeceda" -1, kar bo
je indeks 26.
>> Drugega, če ne bi bilo opuščaj, obstaja bomo nastavili indeks
enak C -.
Torej, se spomnite nazaj od prejšnje p-sprejemnikov, c - se dogaja, da nam
abecedni položaj C. Torej, če C je črka, bo to
nam indeks zero.
Za črko B, bo dal us indeks 1, in tako naprej.
>> Torej, to nam daje indeksa na otroci niz, ki ga želimo.
Zdaj, če je ta indeks trenutno null leta Otroci, to pomeni, da vozlišče
trenutno ne obstaja od te poti.
Zato moramo nameniti vozlišče za to pot.
To je tisto, kar bomo storili tukaj.
>> Torej bomo ponovno uporabiti calloc funkcijo, tako da ne bi bilo treba
nič ven vse napotke.
In smo spet morali preveriti da calloc ni propadel.
Če ni calloc ne, potem moramo raztovarjanje vse, zatiskati
slovar, in vrne false.
Torej, ob predpostavki, da ne bo propadel, potem To bo ustvarilo nov otroka za nas.
In potem bomo šli na tega otroka.
Naša kazalec se bo Ponovil do tega otroka.
>> Zdaj, če to ni bilo null na začetku, Nato kazalec lahko samo Ponovil
do tega otroka, ne da bi dejansko ob dodeliti ničesar.
To je primer, ko sva se prvič zgodilo dodeli besedo "mačka". In
to pomeni, da ko gremo dodeliti "Katastrofa", nam ni treba ustvariti
vozlišča za C-A-T znova.
Že obstajajo.
>> Kaj je to drugega?
To je pogoj, kjer je c backslash n, kjer je c nova linija.
To pomeni, da smo uspešno končan besedo.
Zdaj, kaj želimo narediti, ko smo Uspešno zaključen besedo?
Bomo uporabili to besedo polje znotraj našega struct vozlišča.
Želimo, da se določi, da res.
Tako da kaže, da je ta vozel označuje uspešen
Beseda, dejanska beseda.
>> Sedaj nastavite, da res.
Želimo ponastaviti našo kazalec na točko na začetku Trsta znova.
In končno, prirastek našo zbirko velikost, saj smo našli drugo delo.
Torej bomo vztrajati početje to, branje značaja, ki ga značaja,
gradnji novih vozlišč v našem Trsta in Za vsako besedo v slovarju, dokler
smo končno dosegli C! = EOF, v katerem Primer smo iztrgajo iz spisa.
>> Zdaj obstajata dve zadeve v ki bi lahko zadeli smo EOF.
Prvi je, če je prišlo do napake branje iz datoteke.
Torej, če je prišlo do napake, smo morate storiti, tipično.
Razkladanje vsega, blizu datoteke, vrne false.
Ob predpostavki, da ni bilo napak, da samo pomeni, da smo dejansko prizadela konec
datoteka, v tem primeru smo blizu datoteko in vrne true, saj smo
uspešno naložen slovar v naši Trsta.
>> Torej, zdaj pa poglejmo ček.
Če pogledamo funkcijo check, bomo videli ta pregled bo vrnil bool.
Vrne true, če je to beseda, ki je prevalili je v našem Trsta.
Vrne false sicer.
Torej, kako ste ugotovili, ali ta beseda je v našem Trsta?
>> Vidimo tukaj, da, tako kot prej, bomo uporabili kazalec za ponovitev
preko našega Trsta.
Zdaj tukaj bomo Ponovil nad našo celotno besedo.
Torej ponavljanjem nad besedo smo preteklost, bomo ugotoviti,
Indeks v otroško matrike, ki ustreza besedo držala I. Torej je to
bo videti natanko tako kot obremenitev, če se uporablja beseda [i]
je opuščaj, nato pa smo želeli za uporabo indeksa "abeceda" - 1.
Ker smo ugotovili, da je ta je, če gremo za shranjevanje
opuščaj.
>> Sicer bomo uporabili dve manjši besedo Nosilec I. Torej, ne pozabite, da besedo lahko
ima samovoljno črk.
In zato želimo zagotoviti, da bomo uporabo z malo začetnico različico stvari.
In nato odšteje od '"enkrat nam spet daje abecednem
Položaj te značaja.
Tako, da se dogaja, da je naš indeks v otroško matrike.
>> In zdaj, če je indeks v otroke Niz je nična, to pomeni, da
ne deluje več ponavljanjem navzdol našega Trsta.
Če je temu tako, ta beseda ne more morda se v naši Trsta.
Ker če bi bila, bi to pomeni, da bi bila pot
navzdol, da te besede.
In nikoli ne bi naleteli na null.
Tako srečujejo null vrnemo false.
Besede ni v slovarju.
Če ne bi bilo nič, potem smo bo ponavljanjem naprej.
>> Torej gremo tam kazalec opozoriti na to, zlasti
vozlišče v tem indeksu.
Hranimo tem, da je po vsej celotna beseda, ob predpostavki,
ne bomo nikoli udaril null.
To pomeni, da nam je uspelo priti skozi celo besedo in najti
vozlišče v našem poskusu.
Ampak mi ni še čisto končano.
>> Mi ne želimo le vrne true.
Želimo, da se vrnete kazalec> besedo.
Ker še enkrat spomnim, je "mačka" ni v našem slovarju, in "katastrofa"
je, potem bomo uspešno pridemo z besedo "mačka". Ampak kazalec
Beseda bo napačna in ni res.
Torej se bomo vrnili kazalec besedo, ki označuje ali je to vozlišče dejansko beseda.
In da je za pregled.
>> Torej, kaj je odjaviti velikosti.
Torej velikost se bo precej enostavno saj se spomnite na obremenitve, smo
povečevanje obsega slovarja za vsaka beseda, ki jo srečamo.
Torej velikost je le, da bo vrnitev slovarja velikosti.
In to je to.
>> Torej, na koncu smo se izkrcali.
Torej, razkladanje, bomo uporabili rekurzivna funkcija dejansko storiti vse
dela za nas.
Torej, naša naloga bo se imenuje na razkladalca.
Kaj je Razkladalec storili?
Vidimo tukaj, da Razkladalec bo Ponovil skozi vse otroke na
To zlasti vozlišče.
In če vozlišče otrok ni null, potem pa gremo na
raztovoriti vozlišče otrok.
>> Torej, to je ti rekurzivno razkladanje vse naše otroke.
Ko smo prepričani, da so vsi naši otroci so raztovorili, nato pa smo
Lahko se osvobodimo, tako razkladanje sebe.
To bo delovalo rekurzivno raztovoriti celoten Trsta.
In potem, ko je to storjeno, smo lahko samo vrne true.
Raztovoriti ne more izogniti.
Mi samo sprostitev stvari.
Torej, ko smo končali sprostitev Vse, vrne true.
In to je to.
Moje ime je Rob.
In to je bil speller.
>> [Predvaja glasba]