>> [Muusika mängib]
>> ROB BOWDEN: Hi.
Olen Rob.
Ja olgem seda lahendust.
Nii et siin me läheme rakendada üldine tabel.
Me näeme, et struct tipp meie tabel läheb välja nägema selline.
Nii et see saab olema char sõna massiivi suurus pikkus + 1.
Ära unusta + 1, sest maksimaalne sõna sõnastikus on 45
tähemärki.
Ja siis me peame ühe pildi hieroglüüf kurakriips null.
>> Ja siis meie Hashtable igas kopp läheb salvestada
seotud nimekirja sõlmed.
Me ei tee lineaarse katsetamine siin.
Ja nii, et siduda järgmise element ämbrisse, peame
struct tipp * järgmine.
OK.
Nii see on, mida sõlme välja näeb.
>> Nüüd siin on avaldus meie Hashtable.
See saab olema 16834 ämbrid.
Aga see number ei ole tegelikult küsimus.
Ja lõpuks, me ei kavatse olla globaalse muutuja Hashtable suurus, mis
läheb alustad null.
Ja see saab jälgida, kuidas paljud sõnad on meie sõnastik.
>> Võtame pilk koormus.
Pange tähele, et koormus, tagastatakse tõeväärtus.
Sa tagasi true, kui see oli edukalt koormatud, ja vale teisiti.
Ja see võtab const char * sõnastikku mis on sõnastik
et tahame avada.
Nii et esimene asi, me teeme.
>> Me läheme fopen sõnastik lugemiseks.
Ja me peame tegema kindel, et see õnnestus.
Nii et kui see tagastatakse NULL, siis me ei edukalt avada sõnaraamatut.
Ja me peame tagasi false.
Kuid kui eeldada, et ta seda tegi edukalt avatud, siis tahame, et lugeda
sõnastik.
Nii et hoidke silmusega kuni leiame mõned põhjus välja murda see ahel,
mida me näeme.
Nii et hoidke silmusega.
>> Ja nüüd me läheme malloc ühe sõlme.
Ja muidugi me vajame õhku kontrollige uuesti.
Nii et kui mallocing ei õnnestu, siis tahame lossida ühtegi sõlme, et me
juhtus malloc enne, sulgege sõnastik ja tagastab false.
Aga tähelepanuta asjaolu, eeldades, et me õnnestunud, siis tahame kasutada fscanf
loe sõnagi meie sõnastik meie sõlme.
Seega pidage meeles, et entry> sõna on char sõna puhverala suurus lenghth + 1
et me salvestada sõna sisse
>> Nii fscanf läheb tagasi 1, kui kui see oli võimalik edukalt
loe sõna failist.
Kui üks viga juhtub, või me jõuda lõpuks fail,
ei naase 1.
Sel juhul ei pöördu 1, lõpuks ometi oleme välja murda
see samas silmus.
Nii me näeme, et kui meil on edukalt loe sõna võtta
entry> sõna, siis me läheme, et sõna meie hash funktsiooni.
>> Võtame pilk hash funktsiooni.
Nii et sa tõesti ei pea sellest aru saama.
Ja tegelikult me ​​lihtsalt tõmmatakse see hash toimida internetist.
Ainuke asi, sa pead tunnistama, on et see võtab const char * sõna.
Nii et see võtab stringi sisendiks ja tagastamise allkirjastamata int toodanguna.
Nii et kõik on hash funktsiooni, on see võtab sisendiks ja annab teile
indeks Hashtable.
>> Pange tähele, et me moding poolt NUM_BUCKETS, et raha tagasi
tegelikult on indeks Hashtable ja ei indeks üle
piire massiiv.
Seega, arvestades, et funktsioon, me hash sõna, et me lugeda
sõnastik.
Ja siis me ei kavatse kasutada et hash sisestada
sisenemise Hashtable.
>> Nüüd Hashtable hash on praegune seotud nimekirja tabelis.
Ja see on väga võimalik, et see on lihtsalt NULL.
Me tahame, et lisada oma sisenemise alguses see seotud nimekirja.
Ja nii me lähed on meie praegune sisenemispunkti mida Hashtable
Praegu osutab.
Ja siis me lähme salvestada, aastal Hashtable juures
hash praegune kanne.
Nii et need kaks rida edukalt sisestada kande alguses
seotud nimekirja sel indeks aastal Hashtable.
>> Kui me teinud, et me teame et me leidsime teise sõna
sõnastikku ning me juurdekasvu uuesti.
Nii me edasi teha kuni fscanf lõpuks tagasi millegi mitte-1 juures
mis punkt meeles pidada, et peame sissepääs tasuta.
Nii siin me malloced kanne.
Ja me proovisime midagi lugeda sõnaraamatust.
Ja me ei ole suutnud lugeda midagi sõnaraamatu
mille puhul me peame vabastama kanne et me ei ole kunagi tegelikult ellu
Hashtable ja lõpuks murda.
>> Kui me välja murda on vaja näha, noh, me välja murda, sest seal
oli viga lugemisel failist?
Või kas me välja murda, sest me jõudnud faili?
Kui seal oli viga, siis tahame tagasi false.
Kuna koormus ei õnnestunud.
Ja selles protsessis me tahame maha laadima kõik sõnad, et me lugeda, ja
sulgeda sõnastik faili.
>> Eeldades, et me ei õnnestu, siis me lihtsalt ikka on vaja sulgeda sõnastik
fail ning lõpuks tagasi true, sest me edukalt laaditud sõnastik.
Ja see on see koormus.
Nüüd vaadake, arvestades koormatud Hashtable, läheb välja nägema selline.
Nii et vaadata, tagastatakse tõeväärtus, mis on läheb, et näidata, kas möödunud
Char * sõna, kas möödunud string on meie sõnastik.
Nii et kui see on sõnastikku kui see on meie Hashtable,
me tagasi tõsi.
Ja kui see ei ole, siis me tagastame false.
>> Arvestades seda möödus sõna, me oleme läheb räsi sõna.
Nüüd tähtsam tunnustada on et koormuse teadsime et kõik
sõnad me olema väiketähtedega.
Aga siin me ei ole nii kindel.
Kui me võtame pilk meie räsifunktsiooni, meie räsifunktsiooni tegelikult
on väiksem korpuse iga märk sõna.
Seega sõltumata kapitaliseerimine Ühesõnaga, meie räsifunktsiooni jõutakse tagasi
sama indeksit mingil kapitalisatsioon on, nagu oleks ta
tagastatud täielikult väiketähti versioon sõna.
Olgu.
See on meie indeks on arvesse Hashtable selle sõna.
>> Nüüd on see loop läheb Käi seotud nimekirja
mis oli sel indeks.
Nii märkate oleme algväärtustamisel kanne osutada, et indeks.
Me kavatseme jätkata kui kanne! = NULL.
Ja pidage meeles, et ajakohastada pointer Meie seotud nimekirja kandmise = entry> kõrval.
Nii on meie praegune sisendkoht Järgmine punkt on seotud nimekirja.
>> Nii iga kande seotud nimekirja, Me ei kavatse kasutada strcasecmp.
See ei ole strcomp.
Sest taas tahame asju juhul hoolimatult.
Nii et me kasutame strcasecmp võrrelda Sõna, mis läbis selle
funktsiooni vastu sõna mis on see kanne.
Kui ta naaseb null, mis tähendab, et seal oli mängu, mille puhul me tahame
tagasi true.
Oleme edukalt leitud sõna meie Hashtable.
>> Kui ei sobi, siis me oleme läheb loop uuesti ja vaadata
järgmine kanne.
Ja me jätkame silmukoiminen samas on sissekanded Selle seotud nimekirja.
Mis juhtub, kui me murda sellest loop?
See tähendab, et me ei leia kirje, sobitada see sõna, mille puhul
me tagasi false näitab, et meie Hashtable ei sisalda seda sõna.
Ja see on kontrolli all.
>> Võtame pilk suurus.
Nüüd suurus saab olema üsna lihtne.
Kuna mäleta koormus, iga sõna leidsime me suurendatakse globaalset
muutuja Hashtable suurus.
Nii suuruse funktsioon on lihtsalt läheb tagasi globaalse muutuja.
Ja ongi kõik.
>> Nüüd lõpuks on meil vaja maha laadida sõnastik Kui kõik on tehtud.
Niisiis, kuidas me saame seda teha?
Siin me silmusega üle kõik ämbrid meie lauale.
Seega on NUM_BUCKETS ämbrid.
Ja iga seotud nimekirja meie Hashtable, me silmus üle
kogu seotud nimekirja, vabastades iga element.
>> Nüüd me peame olema ettevaatlikud.
Nii et siin on meil ajutise muutuja mis on hoidmiseks kursor järgmisele
element, mis on seotud nimekirja.
Ja siis me tasuta praegune element.
Me peame olema kindlad, et me teeme seda, sest me ei saa lihtsalt vaba praegune element
ja seejärel üritada pääsu järgmise pointer, sest kui oleme vabanenud see,
mälu muutub kehtetuks.
>> Seega on meil vaja, et hoida umbes viit Järgmine element, siis saab tasuta
praegune element, ja siis saame uuendada meie praegune element osutada
Järgmine element.
Me loop kui ilmnevad asjaolud, Selles seotud nimekirja.
Me teeme, et kõik, mis on seotud nimekirjade Hashtable.
Ja kui me oleme teinud, et me oleme täielikult maha laadida Hashtable ja
me oleme valmis.
Nii et see on võimatu unload kunagi tagasi false.
Ja kui me oleme valmis, me lihtsalt tagasi tõsi.
>> Anname sellele lahendus proovida.
Võtame pilk meie struct sõlme välja näeb.
Siin näeme me lähed on bool sõna ja struct tipp * lapsed
sulg tähestikku.
Nii et esimene asi, mida võiks tea, miks on tähestik
väljaanne defineeritud 27?
Noh, pea meeles, et me peame tuleb käitlemise ülakoma.
Nii et see saab olema mõnevõrra erijuhtum kogu programmi.
>> Pea meeles, kui Prefiksipuu tegelikult toimib.
Oletame, et me indekseerimise sõna "Kassid". Siis juur Prefiksipuu,
me vaatame lapsed massiiv, ja me ei kavatse vaadata
indeks, mis vastab kirjale C. Nii et indekseeritakse 2.
Seega, arvestades, et see tahe anna meile uus sõlm.
Ja siis me tööd, et sõlme.
>> Seega, arvestades, et sõlm, me oleme taas lähen vaatama laste massiivi.
Ja me ei kavatse vaadata indeks nulli vastama kassi.
Siis me läheme selle sõlme ning arvestades, et sõlm me
pilk lõpuks see vastab T. ja liigub edasi, et sõlm,
Lõpuks oleme täiesti vaadanud läbi meie sõna "kass". Ja nüüd bool
sõna peaks näitama, kas see antud sõna on tegelikult sõna.
>> Nii et miks meil seda vaja on erijuhtum?
Noh, mida sõna "katastroof" on meie sõnastik, kuid
sõna "kass" ei ole?
Nii ja vaadates, kui sõna "kass" on meie sõnastik, me oleme
läheb edukalt läbi vaatama indeksite C-A-T piirkonnas sõlme.
Aga see on ainult sellepärast, et katastroofi juhtus luua sõlmede tee
C--T, kõik viis lõpuks sõna.
Nii bool sõna kasutatakse, et näidata, kas see konkreetne asukoht
tegelikult näitab sõna.
>> Hea küll.
Nüüd, et me teame, mida see Prefiksipuu on hakkab välja nägema, vaatame
avada funktsiooni.
Nii koormus läheb tagasi bool jaoks kas õnnestus või
edutult koormatud sõnastik.
Ja see saab olema sõnastik et me tahame last.
>> Nii et esimene asi, mida me teha, on avatud up, et sõnastik lugemiseks.
Ja me peame tagama, me ei suuda.
Nii et kui sõnastik ei olnud avasid, siis pöördutakse
null, mille puhul me oleme läheb tagasi false.
Kuid kui eeldada, et see edukalt avatud, siis võib tegelikult lugeda
läbi sõnastik.
>> Nii et esimene asi, mida me ei kavatse tahame teha, on meil see
globaalse muutuja root.
Nüüd root saab olema node *.
See on top meie Prefiksipuu et me oleme kavatse iterating kaudu.
Nii et esimene asi, mida me ei kavatse et tahad teha, on eraldada
mälu meie juure.
Pange tähele, et me kasutame calloc funktsioon, mis on põhimõtteliselt sama
kui malloc funktsioon, välja arvatud see tagatud tagasi midagi, mis on
täiesti nullida välja.
Nii et kui me kasutasime malloc, meil oleks vaja läbima kõik suunanäitajaks meie
sõlme, ja veenduge, et nad on kõik null.
Nii calloc teeb seda meie eest.
>> Nüüd nagu malloc, peame Veenduge, et jaotus oli tegelikult
edukas.
Kui see tagastatakse null, siis vaja sulgeda või sõnastik
faili ja tagastab false.
Seega eeldades, et eraldist edukas, me ei kavatse kasutada sõlme *
kursor itereerima meie Prefiksipuu.
Nii et meie juured ei muutu, kuid me ei kavatse kasutada kursori
tegelikult lähevad sõlme sõlme.
>> Nii et selles silmus me loevad läbi sõnastik faili.
Ja me kasutame fgetc.
Fgetc läheb haarata ühe tegelasele faili.
Me läheme edasi haarates märki, kui me ei jõua
Faili lõpus.
>> Kahel juhul peame hakkama.
Esimene, kui märk ei olnud uus liin.
Seega me teame, kui see oli uus rida, siis me parasjagu liikuda edasi uue sõna.
Aga isegi kui see ei olnud uue raudteeliini, siis siin me tahame teada,
index me indeks aastal laste massiivi
me vaatasime enne.
>> Nii, nagu ma enne ütlesin, on meil vaja erijuhtum ülakoma.
Pange tähele, me kasutame ternaarse operaator siin.
Nii et me ei kavatse lugeda seda, kui iseloomu loeme oli
ülakomaga, siis me läheme, et seada index = "tähestik" -1, mis
olema indeks 26.
>> Sest kui ta ei ülakoma olemas me seada indeks
võrdne c -.
Seega pidage meeles, tagasi varem p-komplektid, c - läheb meile
tähestiku positsiooni C. Seega, kui C on kirjas, see
meile indeks null.
Tähe B, see annab us indeks 1, ja nii edasi.
>> Nii et see annab meile indeks lapsed massiivi tahame.
Nüüd, kui see indeks on praegu null sisse lastele, see tähendab, et sõlm
Praegu ei eksisteeri selle tee.
Nii et me peame eraldama sõlm, mis teed.
See on see, mida me teeme siin.
>> Nii et me läheme uuesti kasutada calloc funktsioon, nii et me ei pea
null välja kõik suunanäitajaks.
Ja me jälle vaja vaadata et calloc ei õnnestu.
Kui calloc ei suuda, siis on meil vaja lossimiseks kõike, sulgeda
sõnastikku ning tagastab false.
Seega eeldades, et ta ei ole, siis see loob uue lapse juures.
Ja siis me läheme, et laps.
Meie kursor itereerib alla, et laps.
>> Nüüd, kui see ei ole null alustada, siis kursori lihtsalt kinnitada,
alla, et laps ilma tegelikult võttes eraldada midagi.
Seda juhul, kui me esimest korda juhtus eraldab sõna "kass". Ja
see tähendab, et kui me läheme eraldada "Katastroof", siis me ei pea looma
sõlmpunktid C--T uuesti.
Nad on juba olemas.
>> Mis on see teine?
See on seisund, kus c on kurakriips n, kus c on uus liin.
See tähendab, et meil on edukalt lõpule sõna.
Nüüd, mida me tahame teha, kui me edukalt lõpule sõna?
Me ei kavatse kasutada seda sõna valdkonnas sees meie struct sõlme.
Me tahame kehtestada, et tõsi.
Niisiis, mis näitab, et see sõlm näitab edukas
Ühesõnaga, tegelik sõna.
>> Nüüd sätestatud, et tõsi.
Me tahame taastada oma kursor punkti Lisa alguses Prefiksipuu uuesti.
Ja lõpuks, juurdekasvu meie sõnastik suurus, kuna me leidsime veel tööd.
Nii et me ei kavatse seda enam teha, et lugedes tähemärgi haaval
ehitamise uue tippe meie Prefiksipuu ja iga sõna sõnaraamatust, kuni
me lõpuks jõuda C! = EOF, kus juhul me välja murda faili.
>> Nüüd on kaks juhtumit all mis meil oleks tabanud EOF.
Esimene neist on, kui seal oli viga lugemine failist.
Nii et kui seal oli viga, me vaja teha, tüüpiline.
Laadige kõik lähedal fail, tagastab false.
Eeldades, ei olnud viga, et lihtsalt tähendab, et me tegelikult tabas lõpuks
fail, mille puhul me sulgeda faili ja tagastab tõsi, sest me
edukalt laaditud sõnastik meie Prefiksipuu.
>> Nüüd vaatame läbi vaadata.
Vaadates kontrolli funktsioon, näeme et kontroll läheb tagasi bool.
Ta naaseb tõsi, kui see sõna, mis ta on möödutakse on meie Prefiksipuu.
Ta naaseb vale teisiti.
Niisiis, kuidas sa otsustada, kas see sõna on meie Prefiksipuu?
>> Me näeme siin, et nagu varem, Me ei kavatse kasutada kursori itereerima
meie Prefiksipuu.
Nüüd siin me kinnitada, üle kogu meie sõna.
Nii iterating üle sõna oleme minevikus me kindlaks
indeks laste massiivi vastab sõna sulg I. Nii et see
läheb välja täpselt nagu koormus, kus siis, kui sõna [i]
on ülakomaga, siis me tahame kasutada index "tähestik" - 1.
Sest me kindlaks, et on koht, kus me salvestada
ülakomad.
>> Else me kasutame kaks alumist sõna sulg I. Seega pidage meeles, et sõna saab
on meelevaldne kapitaliseeritust.
Ja nii me tahame veenduda, et me oleme kasutades väiketähti versiooni asju.
Ja siis lahutama, et "" üks kord jälle meile tähestikulises
seisukohta, et märk.
Nii et see saab olema meie indeks arvesse laste massiivi.
>> Ja nüüd, kui see indeks lapsed massiiv on null, mis tähendab, et me
ei saa enam jätkata iterating alla meie Prefiksipuu.
Kui see on nii, see sõna ei saa võib-olla on meie Prefiksipuu.
Kuna see oleks, et oleks tähenda, et oleks tee
alla, et sõna.
Ja sa ei oleks kunagi tekib null.
Nii tekib null, siis tagastab false.
Sõna ei ole sõnastikus.
Kui see ei oleks null, siis me oleme jätkub iterating.
>> Nii me seal kursori osutada erilist
sõlm, et indeks.
Hoiame teed, et kogu Kogu sõna eeldades
me kunagi tabanud null.
See tähendab, et me saime läbi kogu sõna ning leida
sõlme meie proovida.
Aga me ei ole päris valmis veel.
>> Me ei taha lihtsalt tagasi tõsi.
Tahame tagasi kursor> sõna.
Kuna mäletan veel, on "kass" ei ole meie sõnastikku ja "katastroof"
on, siis me edukalt saame läbi sõna "kass". Aga kursor
sõna on vale ja ei vasta tõele.
Nii me tagasi kursor tähistavat sõna kas see sõlm on tegelikult sõna.
Ja see on seda kontrollida.
>> Nii Vaatame suurus.
Nii suurus saab olema üsna lihtne sest mäletan koormus, me oleme
incrementing sõnastik suurus Iga sõna, mida me kohtame.
Nii suurus on lihtsalt läheb tagasi sõnastik suurus.
Ja ongi kõik.
>> Nii lõpuks oleme maha laadida.
Nii lossimiseks, me ei kavatse kasutada rekursiivne funktsioon tegelikult teha kõik
töö meile.
Nii et meie ülesanne läheb kutsutakse unloader.
Mida Tühjenduse teha kavatsed?
Me näeme siin, et Tühjenduse läheb Käi kõik lapsed
selle konkreetse sõlme.
Ja kui laps sõlme ei null, siis me läheme
lossimiseks laps sõlme.
>> Nii et see on teile rekursiivselt mahalaadimiseks kõik meie lapsed.
Kui oleme kindlad, et kõik meie lapsed on maha laaditud, siis me
saab tasuta ise, nii lossimiseks ise.
See toimib rekursiivselt lossida kogu Prefiksipuu.
Ja siis, kui see on tehtud, saame lihtsalt tagasi tõsi.
Sulgeda ei saa jätta.
Me lihtsalt vabastades asju.
Nii et kui me teinud vabastades kõik, tagastab true.
Ja ongi kõik.
Minu nimi on Rob.
Ja see oli speller.
>> [Muusika mängib]