[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]