>> [Muzikavimo]
>> ROB BOWDEN: Sveiki.
Aš Rob.
Ir tegul šį sprendimą iš.
Taigi čia mes ketiname įgyvendinti bendras stalas.
Mes matome, kad struct mazgas mūsų lentelė atrodys tai.
Taigi jis ketina turėti char žodį masyvo dydis ilgis + 1.
Nepamirškite + 1, nes maksimalus žodis žodyne yra 45
simbolių.
Ir tada mes ketiname reikia vieną papildomą personažas pasvirąjį nulio.
>> Ir tada mūsų Hashtable kiekvienoje kibiras ketina saugoti
susijęs sąrašas mazgų.
Mes nedarome linijinė zondavimo čia.
Ir todėl, kad rodo į kitą elementas kibirą, mes turime
struct mazgas * šalia.
Gerai.
Štai ką mazgas atrodo.
>> Dabar čia yra deklaracija mūsų Hashtable.
Ji ketina turėti 16.834 kibirus.
Tačiau šis skaičius nėra iš tikrųjų klausimas.
Ir pagaliau, mes ketiname turėti pasaulinį kintamąjį Hashtable dydis, kuris
ketina pradėti nuo nulio.
Ir jis ketina stebėti, kaip daug žodžių yra mūsų žodyną.
>> Taigi galime pažvelgti apkrovos išvaizdą.
Atkreipkite dėmesį, kad apkrovos, jis grįžta bool.
Jūs grąžina true, jei ji buvo sėkmingai pakrautas, ir false kitaip.
Ir tai trunka const char * žodyną, kuris yra žodynas
kad mes norime atidaryti.
Štai pirmas dalykas, mes ketiname daryti.
>> Mes ketiname fopen žodynas skaityti.
Ir mes turėsime padaryti įsitikinkite, kad ji pavyko.
Taigi, jei jis grįžo NULL, tada mes ne sėkmingai atidaryti žodyną.
Ir mes turime grįžti klaidinga.
Tačiau darant prielaidą, kad jis sėkmingai padarė atidaryti, tada mes norime skaityti
žodynas.
Taigi neišmeskite apsisukimo kol mes radote priežastis išeiti iš šio ciklo,
kurį matysime.
Taigi neišmeskite apsisukimo.
>> Ir dabar mes ketiname malloc vieną mazgą.
Ir, žinoma, mes turime į orą vėl patikrinkite.
Taigi, jei mallocing nepavyko, tada norime iškrauti bet kokį mazgą, kad mes
atsitiko malloc prieš, uždarykite žodynas ir return false.
Tačiau ignoruojant, kad, darant prielaidą, mes pavyko, tada mes norite naudoti fscanf
skaityti vieną žodį iš mūsų žodyną į mūsų mazgas.
Taigi nepamirškite, kad įrašas> žodis yra char Žodis buferio dydis LENGHTH + 1
kad mes ketiname saugoti žodį in
>> Taigi fscanf ketina grįžti 1, kol kaip ji galėjo sėkmingai
skaityti žodį iš failo.
Jei kuri nors klaida įvyksta, ar mes pasiekti failo pabaigą, jis
negrįš 1.
Tokiu atveju jis negrįžta 1, mes pagaliau ketina išeiti iš
tai, o kilpos.
Taigi matome, kad kai mes sėkmingai skaityti žodis į
įrašas> žodis, tada mes ketiname kad Žodis naudojant mūsų maišos funkciją.
>> Paimkime pažvelgti maišos funkcija.
Taigi jums nereikia tikrai reikia tai suprasti.
Ir iš tikrųjų mes tiesiog ištraukė šį maišos veikti iš interneto.
Vienintelis dalykas, kurį reikia pripažinti, kad tai mano const char * žodį.
Taigi, tai, atsižvelgiant eilutę kaip įvesties ir grąžinant unsigned int kaip produkcija.
Taigi, kad viskas maišos funkcija, tai trunka įvesties ir suteikia jums
rodyklė į Hashtable.
>> Atkreipkite dėmesį, kad mes Moding pagal NUM_BUCKETS, kad grąžinta reikšmė
iš tikrųjų yra į Hashtable puslapis ir neindeksuoja už
Ribas masyvo.
Taigi, turint omenyje, kad funkcija, mes ketiname maišos žodį, kad mes skaityti
žodynas.
Ir tada mes ketiname naudoti kad maišos įterpti
įrašas į Hashtable.
>> Dabar Hashtable maišos yra dabartinė susijęs sąrašą lentelėje.
Ir tai labai įmanoma, kad tai tik NULL.
Mes norime įterpti mūsų bendrovėms patekti į rinką pradžioje šio susijęs sąrašą.
Ir todėl mes ketiname turėti mūsų srovę įvažiavimo į ką Hashtable
Šiuo metu nurodo.
Ir tada mes ketiname saugoti, ir tuo Hashtable
maišos, dabartinis įrašas.
Taigi šios dvi linijos sėkmingai įterpti prie pradžios įrašas
susijęs sąrašas tuo indeksą į Hashtable.
>> Kai baigsime su tuo, mes žinome, kad mes rasti kitą žodį
žodyną, ir mes prieaugio dar kartą.
Taigi, mes nuolat tai daryti, kad iki fscanf pagaliau grįžo kažką ne 1 metu
kuris taškas prisiminti, kad turime įėjimas nemokamas.
Taigi čia mes malloced įrašą.
Ir mes bandėme skaityti kažką iš žodyno.
Ir mes ne sėkmingai skaityti kažkas iš žodyno, į
tokiu atveju mes turime išlaisvinti įrašą kad mes niekada iš tikrųjų išleisti į
Hashtable ir galiausiai lūžta.
>> Kai mes išeiti, mes turime pamatyti, gerai, Ar mes išeiti, nes
buvo klaida skaitant iš failo?
O gal mes išeiti, nes mes pasiektas failo galas?
Jei ten buvo klaida, tada mes norime grįžti klaidinga.
Kadangi krovinys nebuvo sėkmingas.
Ir į šį procesą mes norime iškrauti visus žodžius, kuriuos mes skaitome, ir
uždaryti žodyno failą.
>> Darant prielaidą, kad mes iš tikrųjų pavyko, tada mes tiesiog vis dar reikia uždaryti žodyną
failą, ir galiausiai grąžina true, nes mes sėkmingai įkeltas žodynas.
Štai ir viskas kroviniu.
Taigi, dabar patikrinti, nes pakrautas Hashtable, ketina atrodyti taip.
Taigi patikrinti, jis grįžta bool, kuris yra ketina nurodyti, ar perduota
į char * žodžiu, ar praėjo į eilutės yra mūsų žodyną.
Taigi, jei tai yra žodyne, jei tai yra mūsų Hashtable,
grįšime tiesa.
Ir jei tai nėra, mes return false.
>> Atsižvelgiant į tai praėjo žodžiu, mes ketina koduoti žodį.
Dabar svarbiausias dalykas pripažinti, kad apkrovos mes žinojome, kad visi
žodžiai mes ketiname būti mažosiomis raidėmis.
Bet čia mes ne tokie tikri.
Jei mes atsižvelgti į mūsų maišos funkcija atrodo, mūsų maišos funkcija faktiškai
yra mažesnis korpusas kiekvienas simbolis žodžio.
Taigi, nepriklausomai nuo kapitalizacijos žodis, mūsų maišos funkcija grąžinimas
pats indeksas kokia kapitalizacija, kaip ji turėtų
grąžinama visiškai mažosiomis raidėmis portalo žodį.
Gerai.
Tai mūsų indeksas yra į Hashtable šio žodžio.
>> Dabar tai už linijos ketina pakartoti per susietą sąrašą
kad buvo tuo indeksu.
Taigi pastebėsite mes Inicijuojama įrašą atkreipti dėmesį į šio indekso.
Mes ketiname tęsti o įrašas! = NULL.
Ir atminkite, kad atnaujinus žymiklį Mūsų susijęs sąrašas įrašas = įrašas> šalia.
Taigi turime esamą prieigos tašką prie Kitas darbotvarkės punktas susijusioje sąrašą.
>> Taigi kiekvieno susieto sąrašo įrašą, mes ketiname naudoti strcasecmp.
Tai ne strcomp.
Nes dar kartą, mes norime daryti tai, ko bylą insensitively.
Taigi mes naudojame strcasecmp palyginti Žodis, kuris buvo priimtas per šį
funkcija prieš žodį kad yra šio įrašo.
Jei ji grąžina nulį, tai reiškia, kad buvo rungtynės, tokiu atveju mes norime
return true.
Mes sėkmingai surado žodis mūsų Hashtable.
>> Jei ten buvo ne rungtynės, tada mes ketina kilpos ir vėl pažvelgti
Kitas įrašas.
Ir mes ir toliau Looping nors yra Įrašų šiame susijęs sąrašą.
Kas atsitiks, jei mes pertrauka iš čia už linijos?
Tai reiškia, kad mes ne rasti įrašą, atitiko šį žodį, tokiu atveju
mes return false nurodyti, kad mūsų Hashtable nebuvo šį žodį.
Ir tai patikrinti.
>> Taigi galime pažvelgti dydžio išvaizdą.
Dabar dydis bus gana paprasta.
Nuo Prisimenu apkrova, už kiekvieną žodį mes nustatėme, mes padidinamas pasaulio
kintamasis Hashtable dydis.
Taigi dydis funkcija tiesiog vyksta grįžti pasaulinį kintamąjį.
Štai ir viskas.
>> Dabar pagaliau turime iškrauti žodynas kartą viskas daroma.
Taigi, kaip mes ketiname daryti?
Štai čia mes apsisukimo per visi mūsų stalo kibirai.
Taigi yra NUM_BUCKETS kibirai.
Ir kiekvieną susietą sąrašą mūsų Hashtable, mes ketiname kilpa per
susieto sąrašo visuma, išlaisvina kiekvieną elementą.
>> Dabar mes turime būti atsargūs.
Taigi čia mes turime laikiną kintamąjį tai saugoti žymiklį į kitą
elementas susijęs sąrašą.
Ir tada mes ketiname nemokamai dabartinis elementas.
Mes turime būti tikri, kad mes darome tai, nes mes gali ne tik atlaisvinti einamųjų elemento
ir tada bandykite ir atidarykite kitą žymeklį, nes kai mes išlaisvino jį,
atmintis tampa negaliojančiu.
>> Taigi, mes turime išlaikyti aplink rodyklę į Kitas elementas, tada mes galime nemokamai
dabartinis elementas, ir tada mes galime atnaujinti mūsų dabartinis elementas rodo
kitas elementas.
Mes kilpa nors yra elementai Šiame susijęs sąrašą.
Mes padarysime, kad visi susiję sąrašus Hashtable.
Ir kai mes baigsite, kad mes visiškai iškraunamas į Hashtable ir
baigsime.
Todėl neįmanoma iškrauti kada nors grįžti klaidinga.
Ir kai mes baigsime mes tiesiog grąžina true.
>> Leiskite duoti šis sprendimas pabandyti.
Taigi galime pažvelgti, kas mūsų išvaizdą struct mazgas atrodys.
Čia mes matome, mes ketiname turėti bool žodis ir struct mazgas * vaikai
laikiklis abėcėlė.
Taigi pirmas dalykas, kurį gali būti įdomu, kodėl ALPHABET
ED apibrėžiamas kaip 27?
Na, nepamirškite, kad mes ketiname reikia reikia tvarkyti kabutes.
Taigi, tai bus šiek tiek Ypatingas atvejis per šią programą.
>> Dabar prisimenu, kaip trie iš tiesų veikia.
Tarkime, mes indeksavimo žodį "katės." Tada iš TRIE šaknis,
mes ketiname pažvelgti į vaikų masyvas, ir mes ketiname pažvelgti į
indeksas, kuris atitinka raide C. Taigi, kad bus indeksuojamos 2.
Taigi, atsižvelgiant į tai, kad bus suteikia mums naują mazgas.
Ir tada mes dirbame nuo to mazgo.
>> Taigi, atsižvelgiant į tai, mazgas, mes dar kartą ketiname pažvelgti į vaikų masyvo.
Ir mes ketiname pažvelgti į nulinę indekso atitikti kačių A.
Taigi mes ketiname eiti į tą mazgą, ir atsižvelgiant į tai, kad mazgas mes ketiname
ieškoti pabaigoje tai atitinka į T. juda į tą mazgą,
pagaliau, mes turime visiškai atrodė per mūsų žodis "katė". Ir dabar bool
žodis turėtų nurodyti, ar turint mintyje tai žodis iš tikrųjų žodis.
>> Tad kodėl mes turime tą ypatingą bylą?
Na, ką žodis "katastrofa" yra mūsų žodyne, tačiau
žodis "katė" nėra?
Taigi, ir nori pamatyti, jei žodis "katė" yra mūsų žodyną, mes
vyksta sėkmingai ieškoti per indeksai C-T regiono mazgas.
Bet tai tik dėl to, katastrofa atsitiko sukurti mazgų kelyje
iš C-A-T, visi būdas Žodžio pabaiga.
Taigi bool žodis yra naudojamas nurodyti, ar tai pirma vieta
iš tikrųjų rodo žodį.
>> Gerai.
Taigi dabar, kad mes žinome, ką jis trie yra atrodys, pažvelkime
įkelti funkciją.
Taigi apkrova ketina grįžti bool Dėl klausimo, ar mes sėkmingai arba
nesėkmingai pakrautas žodynas.
Ir tai bus žodynas kad mes norime įkelti.
>> Taigi pirmas dalykas, mes padaryti, tai atidaryti iki to žodyne svarstymą.
Ir mes turime įsitikinti, mes nepamiršo.
Taigi, jei žodynas nebuvo sėkmingai atidarytas, jis sugrįš
null, tokiu atveju mes ketina grįžti klaidinga.
Tačiau darant prielaidą, kad jis sėkmingai atidarytas, tada mes iš tiesų gali skaityti
per žodyną.
>> Taigi pirmas dalykas, kurį mes ketiname norite padaryti, tai turime tai
pasaulinį kintamąjį šaknis.
Dabar šaknis bus mazgas *.
Tai mūsų TRIE viršų, kad mes bus iteravimu per.
Taigi pirmas dalykas, kad mes ketiname nori padaryti, tai skirti
atminties mūsų šaknis.
Atkreipkite dėmesį, kad mes naudojame calloc funkcija, kuri yra iš esmės tas pats
kaip malloc funkcijos, išskyrus tai garantuoja, kad grįžti kažką, kad yra
visiškai nulis iš.
Taigi, jei mes naudojome malloc, mums reikia eiti per visus iš rodyklės mūsų
mazgas, ir įsitikinkite, kad jie visi null.
Taigi calloc bus tai padaryti už mus.
>> Dabar kaip malloc, mes turime padaryti įsitikinkite, kad paskirstymas iš tikrųjų buvo
sėkmingas.
Jei tai grąžinami null, tada mes reikia uždaryti arba žodynas
failą ir return false.
Taigi, darant prielaidą, kad paskirstymas buvo sėkmingas, mes ketiname naudoti mazgas *
žymeklį pakartoti mūsų TRIE.
Taigi mūsų šaknys niekada pakeisti, bet mes ketiname naudoti žymeklį į
faktiškai eiti iš mazgo į mazgą.
>> Taigi, tai už linijos mes skaityti per žodyno failą.
Ir mes naudojame fgetc.
Fgetc ketina patraukti vieną simbolį iš failo.
Mes ketiname tęsti greiferiniai ženklai, o mes nepasiekia
failo pabaiga.
>> Yra du atvejai, turime dirbti.
Pirma, jei simbolis nebuvo nauja linija.
Taigi mes žinome, jeigu tai buvo nauja eilutė, tada mes ruošiamės pereiti į naują žodį.
Tačiau darant prielaidą, kad tai buvo ne nauja eilutė, tada čia mes norime išsiaiškinti,
rodiklis mes ketiname indeksą į į vaikų matrica,
mes pažvelgė anksčiau.
>> Taigi, kaip ir minėjau anksčiau, mes turime Ypatingas atvejis kabutes.
Atkreipkite dėmesį, mes naudojame trijų komponentų operatorius čia.
Taigi, mes ketiname skaityti tai kaip, jei simbolių skaitome buvo
Apostrofa, tada mes ketiname nustatyti puslapis = "ALPHABET" -1, kuris bus
būti 26 indeksas.
>> Kitur, jei tai buvo ne Apostrofa, yra mes ketiname sukurti indeksą
lygi c -.
Taigi nepamirškite atgal nuo ankstesnio p rinkinių, c - ketina duoti mums
Abėcėlinis pozicija C. Taigi, jei C raidė, tai bus
mums nulinį indeksą.
Dėl raide B, jis duos mums indeksas 1, ir pan.
>> Taigi, tai suteikia mums rodyklę į vaikai masyvas, kad mes norime.
Dabar, jei šis rodiklis šiuo metu yra niekinis ir vaikai, tai reiškia, kad mazgas
šiuo metu nėra iš to kelio.
Taigi turime skirti tuo keliu mazgas.
Štai ką mes čia darome.
>> Taigi, mes ketiname vėl naudoti calloc funkciją, todėl, kad mes neturime
nulis iš visų patarimų.
Ir mes vėl reikia patikrinti kad calloc nepamiršo.
Jei calloc dar nepavyksta, tada mes turime iškrauti viską, užmerkti
žodyną, ir return false.
Taigi, darant prielaidą, kad jis nepavyktų, tada tai sukurs naują vaiką mums.
Ir tada mes galėsime eiti į tą vaiką.
Mūsų žymeklis bus pakartoti iki to vaiko.
>> Dabar, jei tai buvo ne null prasideda, tada žymeklį galite tiesiog kartoti
žemyn į tą vaiką faktiškai turintys skirti nieko.
Tai atvejis, kai mes pirmą kartą atsitiko skirti žodį "katė". Ir
tai reiškia, kad, kai mes einame skirti "Katastrofa", mums nereikia kurti
mazgai C-A-T dar kartą.
Jie jau egzistuoja.
>> Kas tai yra dar?
Tai būklė, kai c buvo Backslash n, kur c buvo nauja linija.
Tai reiškia, kad mes sėkmingai baigė žodį.
Dabar, ką mes norime daryti, kai mes sėkmingai baigė žodį?
Mes ketiname naudoti šį žodį lauką viduje mūsų struct mazgas.
Mes norime nustatyti, kad būtų tiesa.
Taigi, kad rodo, kad šis mazgas rodo sėkmingas
žodis, tikrasis žodis.
>> Dabar nustatyta, kad "true".
Mes norime, kad naujo mūsų žymeklį į tašką į TRIE pradžioje dar kartą.
Ir, pagaliau, prieaugio mūsų žodyną dydis, nes mes radome kitą darbą.
Taigi, mes ketiname toliau daryti, kad skaityti pobūdį, charakterį,
statant naujus mazgus mūsų TRIE ir kiekvieno žodžio žodyne, kol
mes pagaliau pasieks C! = EOF, kurioje atveju mes išeiti iš failo.
>> Dabar yra du atvejai, dėl kurių kurios mes galime nukentėjo EOF.
Pirma, jei ten buvo klaida skaitant iš failo.
Taigi, jei ten buvo klaida, mes reikia padaryti tipiškas.
Iškrauti viską, netoli failas, return false.
Darant prielaidą, kad nebuvo klaida, kad tiesiog reiškia, kad mes iš tikrųjų pateko į pabaigą
failas, tokiu atveju, mes uždaryti failą ir grąžina true, nes mes
sėkmingai įkeltas žodynas į mūsų TRIE.
>> Taigi dabar galime patikrinti patikrinimą.
Pažvelgus žymės funkcija, matome kad patikrinimas vyksta grįžti bool.
Ji grąžina true, jei šis žodis, kad tai bus perduotas yra mūsų TRIE.
Ji grąžina false kitaip.
Taigi, kaip jūs nustatyti, ar šis žodis yra mūsų TRIE?
>> Čia mes matome, kad, kaip ir anksčiau, mes ketiname naudoti žymeklį pakartoti
per mūsų TRIE.
Dabar čia mes ketiname pakartoti per visą mūsų žodį.
Taigi Iteracja virš žodžio mes esame praeities, mes ketiname nustatyti
rodyklė į vaikų matrica, atitinka žodžio kronšteino I. Taigi tai
ketina atrodo kaip apkrova, kur, jei žodis [i]
yra Apostrofa, tada mes norime naudoti indeksas "Alfabetas" - 1.
Nes mes nustatėme, kad šis kur mes ketiname saugoti
kabutes.
>> Dar mes ketiname naudoti dvi mažesnes žodį laikiklis I. Taigi nepamirškite, kad žodis gali
turi savavališkai kapitalizaciją.
Ir taip mes norime įsitikinti, kad mes naudojant mažąją versiją dalykų.
Ir tada atimkite nuo "a" iki vieno karto vėl suteikti mums abėcėlinis
pozicija šiuo simboliu.
Taigi, tai bus mūsų puslapis į vaikų masyvo.
>> Ir dabar, jei tai puslapis į vaikų masyvas yra tuščias, tai reiškia, kad mes
nebegali Iteracja žemyn mūsų TRIE.
Jei tai toks atvejis, šis žodis negali galbūt bus mūsų TRIE.
Nes jei taip būtų, kad būtų tai ten bus kelias
žemyn į tą žodį.
Ir jūs niekada susidurti null.
Taigi iškyla null mes return false.
Žodžio nėra žodyne.
Jei tai buvo ne nulis, tada mes ketina toliau Iteracja.
>> Taigi, mes ketiname ten žymeklį atkreipti dėmesį į tai ypač
mazgas tuo indeksu.
Mes nuolat tai daryti, kad per Visas žodis, darant prielaidą,
mes niekada hit null.
Tai reiškia, kad mes galime gauti per Visas žodis ir rasite
mūsų bandymas mazgas.
Bet mes ne visai padaryta dar.
>> Mes nenorime tiesiog grąžina true.
Mes norime grįžti žymeklį> žodį.
Nuo prisiminti vėl yra "katė" nėra mūsų žodyną, ir "katastrofa"
yra, tada mes sėkmingai mes per žodis "katė". Bet žymeklis
Žodis bus klaidingas, o ne tiesa.
Taigi, mes grįžtame žymeklio žodį rodo ar šis mazgas yra iš tikrųjų žodis.
Štai ir viskas registruotis.
>> Taigi galime patikrinti dydį.
Taigi dydis bus gana lengva nes prisiminti, kroviniu, mes
incrementing žodyno dydį kiekvienas žodis, kad mes susiduriame.
Taigi dydis yra tik ketina grįžti žodyno dydį.
Štai ir viskas.
>> Taigi galiausiai mes iškrauti.
Taigi, iškrauti, mes ketiname naudoti grįžtamojo funkcija iš tiesų visi
iš mums darbo.
Taigi, mūsų funkcija ketina būti paprašyta unloader.
Kas yra Kėlimo ketinate daryti?
Čia mes matome, kad Kėlimo ketina kartoti per visas vaikams
tai ypač mazgas.
Ir jei vaikas mazgas nėra null, tada mes ketiname
iškrauti vaikų mazgas.
>> Taigi tai jums rekursyviai iškrauti visus mūsų vaikus.
Kai mes esame tikri, kad visi mūsų vaikai buvo iškrauti, tada mes
gali išsivaduoti, todėl iškrauti save.
Ši funkcija veiks rekursyviai iškrauti visą TRIE.
Ir tada, kai tai daroma, mes galime tiesiog grąžina true.
Iškelti negali nepavykti.
Mes tiesiog išlaisvina dalykų.
Taigi, kai mes baigsime išlaisvinant viskas, grąžina true.
Štai ir viskas.
Mano vardas yra Rob.
Ir tai buvo Speller.
>> [Muzikavimo]