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