[MUSIC Playing] 

ROB BOWDEN: Szia. Én Rob. És nézzük ezt a megoldást ki. Tehát itt fogunk végrehajtani általános asztalra. Látjuk, hogy a struktúra csomópont a mi táblázat fog kinézni, mint ez. Ezért van, hogy a char szót tömb mérete hossz + 1. Ne felejtsd el a + 1, mivel a maximális szó a szótárban 45 karaktereket. És akkor mi lesz, hogy szükség van egy extra karakter a backslash nulla. 

És akkor a hash tábla minden vödör fog tárolni a láncolt lista csomópontok. Nem tesszük lineáris szondázás itt. Így annak érdekében, hogy link a következő elem a vödör, szükségünk van egy struct node * mellett. OK. Szóval, ez az, amit a csomópont néz ki. 

Most itt van a nyilatkozat a mi hash tábla. Úgy megy, hogy 16.834 vödör. De ez a szám nem igazán számít. És végül, mi lesz, hogy a globális változó hash tábla mérete, ami fog elindul, mint nulla. És ez lesz nyomon követni, hogyan sok szó van a szótár. 

Szóval vessünk egy pillantást a terhelés. Figyeljük meg, hogy terhelés, visszatér a bool. Visszatér igaz, ha sikeresen betöltött, és hamis egyébként. És ez tart a const char * szótár, amely a szótárban hogy meg akarjuk nyitni. Tehát ez az első dolog, fogunk csinálni. 

Megyünk fopen a szótár az olvasáshoz. És mi lesz, hogy, hogy a arról, hogy ez sikerült. Tehát, ha vissza NULL, akkor nem sikeresen nyitott a szótárban. És meg kell, hogy visszatérjen hamis. De feltételezve, hogy nem sikerült nyitva van, akkor szeretnénk olvasni a szótárban. Maradjatok hurok amíg nem találunk valami ok, hogy kitörjön erre a ciklusra, amely majd meglátjuk. Maradjatok hurok. 

És most mi lesz malloc egy csomópont. És természetesen szükségünk van a levegő ellenőrizze újra. Tehát, ha mallocing nem sikerült, akkor azt akarjuk, hogy kirak olyan csomópont, hogy mi történt malloc előtt, zárja be a szótárt, és vissza hamis. De figyelmen kívül hagyva, hogy feltételezve, hogy sikerült, akkor szeretnénk használni fscanf olvasni egy szót a szótárt a mi csomópontot. Úgy emlékszem, hogy a bejegyzés> szó a char szó buffer méret lenghth + 1 hogy fogjuk tárolni a szó be 

Tehát fscanf fog visszatérni 1., amennyiben mint volt képes sikeresen olvasni egy szót a fájlt. Ha bármelyik hiba történik, vagy mi éri el a végén a fájl, akkor nem tér vissza 1. Ebben az esetben nem tér vissza 1, mi végre fog kitörni ez a while ciklus. Tehát azt látjuk, hogy ha már sikeresen olvasni egy szót entry> szó, akkor fogjuk, hogy szót a hash függvényt. 

Vessünk egy pillantást a hash függvényt. Szóval nem igazán kell megérteni ezt. És valójában mi csak húzta ezt a hash működik az interneten. Az egyetlen dolog, amit meg kell, hogy ismerje el, hogy ez eltart egy const char * szót. Szóval ez, hogy egy string bemenet, és vissza az unsigned int a kibocsátás. Szóval ez az egész egy hash funkció, ez vesz egy bemeneti és ad egy index a hash tábla. 

Figyeljük meg, hogy mi Moding által NUM_BUCKETS, úgy, hogy a visszaadott érték valójában egy index a hash tábla és nem indexeli túl határait a tömb. Tehát, mivel ezt a funkciót, megyünk a hash a szót, hogy olvassa el a szótárban. És akkor fogjuk használni hogy a hash beszúrni a belépés a hash tábla. 

Most hash tábla hash az aktuális láncolt lista a táblázatban. És ez nagyon is lehetséges hogy ez csak NULL. Azt szeretné szúrni a belépést a elején ez a láncolt lista. És mi lesz, hogy a jelenlegi belépési pont, amit a hash tábla Jelenleg mutat. Aztán megyünk tárolni, a hash tábla, a hash, az aktuális bejegyzést. Tehát ez a két vonal sikeresen be belépési elején a láncolt lista az adott index a hash tábla. 

Miután végeztünk, hogy mi tudjuk, hogy talált egy másik szót a szótár, és növelni újra. Így csinálom, hogy amíg fscanf Végre visszatért valami non-1-es amely pont ne feledje, hogy meg kell a belépés ingyenes. Tehát itt van malloced egy bejegyzést. És próbált olvasni valamit a szótárban. És nem sikerült elolvasni valamit a szótárban, a az esetben fel kell szabadítanunk a bejegyzést hogy soha nem tesz a hash tábla, és végül megtörni. 

Amint kitörni meg kell látni, nos, tudtunk kitörni, mert volt olvasási hiba a fájl? Vagy mi kitörni, mert végére ért a fájl? Ha volt egy hiba, akkor szeretnénk visszatérni hamis. Mivel a terhelés nem sikerült. És ebben a folyamatban szeretnénk, hogy kirak minden szót, amit olvasott, és zárja be a szótárban fájlt. 

Feltéve, hogy nem sikerül, akkor már csak továbbra is szükség van, hogy lezárja a szótárban fájlt, és végül visszatér igaz, mert mi sikeresen betöltötte a szótárban. És ez a terhelés. Tehát most ellenőrizni, mivel a betöltött hash tábla, fog kinézni. Így ellenőrizni, visszatér a bool, amely majd arra vonatkozóan, hogy az átadott A char * szó, hogy az átadott a string-ben a szótár. Tehát, ha a szótárban, ha az a hash tábla, akkor vissza igaz. És ha nem, akkor vissza hamis. 

Mivel ez a telt szót, vagyunk fogja hash szó. Most egy fontos dolog, hogy ismerje el, hogy terhelés tudtuk, hogy az összes szóval mi lesz kisbetűs. De itt nem vagyunk olyan biztos. Ha veszünk egy pillantást a hash függvény a hash függvény valójában alacsonyabb burkolat minden karakter a szó. Tehát függetlenül attól, hogy a kapitalizációja szó, a hash függvény visszatérési azonos index bármilyen tőkésítés, mivel ez van visszatért egy teljesen kisbetűs változata a szó. Rendben. Ez az index is a Hash tábla ezt a szót. 

Most ez a for ciklus fog végighaladni a láncolt lista hogy abban az index. Így észre vagyunk inicializálás bejegyzés hogy pont, hogy az index. Megyünk tovább míg a belépés! = NULL. És ne feledjük, hogy frissíti a mutató a mi láncolt lista entry = bejegyzés> mellett. Tehát van a jelenlegi belépési pont A következő elem a láncolt lista. 

Tehát minden bejegyzést a láncolt lista, fogunk használni strcasecmp. Ez nem StrComp. Mert még egyszer, azt akarjuk, hogy dolgok esetében érzéketlenül. Így használjuk strcasecmp összehasonlítani a szó, amit át ezt a funkció ellen szót , ami ezt a bejegyzést. Ha visszatér a nulla, ami azt jelenti, nem volt a meccs, ebben az esetben szeretnénk vissza igaz. Sikeresen megtaláltuk a szó a mi hash tábla. 

Ha nem egyezik, akkor vagyunk fog loop újra, és nézd meg a következő bejegyzés. És mi is loop míg vannak bejegyzések ebben a láncolt lista. Mi történik, ha szünet ki ez a for ciklus? Ez azt jelenti, hogy nem találtunk olyan bejegyzést, amely párosított ezt a szót, amely esetben visszatérünk a hamis, jelezve, hogy a hash tábla nem tartalmazza ezt a szót. És ez a csekk. 

Szóval vessünk egy pillantást méretben. Most méret lesz nagyon egyszerű. Mivel emlékszem terhelés, minden egyes szó azt találtuk, hogy növekszik a globális változó hash tábla méretét. Tehát a méret funkció csak megy vissza globális változót. És ennyi. 

Most végre, meg kell, hogy kirak az szótár Amint minden kész. Szóval, hogyan fogjuk csinálni? Itt vagyunk loop vége minden vödör asztalunk. Tehát vannak NUM_BUCKETS vödör. És minden egyes láncolt lista a mi hash tábla, fogunk hurkot A teljes egészében a láncolt lista, felszabadítása minden elem. 

Most arra van szükség, hogy legyen óvatos. Tehát itt van egy átmeneti változó ez tárolja a mutató a következő elem a láncolt lista. És akkor mi lesz ingyenes Az aktuális elem. Meg kell bizonyosodni arról, hogy ezt mivel Nem lehet csak kiszabadítani az aktuális elem , majd próbálja meg elérni a következő mutató, mert egyszer már megszabadította, A memória érvénytelenné válik. 

Tehát meg kell tartani körül egy mutatót A következő elem, akkor mi is szabad a aktuális elem, és akkor frissíteni a jelenlegi elem, hogy pont A következő elem. Majd loop, míg vannak olyan elemei ebben a láncolt lista. Majd, hogy minden kapcsolt listák a hash tábla. És ha végeztünk vele, most már teljesen lemerülni a hash tábla, és a végeztünk. Tehát lehetetlen kirak , hogy valaha is visszatér hamis. És amikor kész, akkor csak vissza igaz. 

Adjunk ez a megoldás egy próbát. Szóval vessünk egy pillantást, amit a struct csomópont fog kinézni. Itt látni fogunk egy bool szó és egy struct csomópont * gyermekek konzol ábécét. Tehát az első dolog, amit lehet, kíváncsi, miért ALPHABET ed definíció szerint 27? Nos, ne feledjük, hogy mi lesz szüksége hogy kezelése az aposztróf. Annak érdekében, hogy lesz egyfajta speciális eset az egész program. 

Ne feledd, hogy a trie tényleg működik. Mondjuk mi indexelés szót "Macskák". Ezután a gyökér trie, fogunk nézni a gyerekek tömb, és meg fogjuk nézni a index, amely megfelel a levél C. Hogy lesz indexelve 2.. Így tekintettel arra, hogy az akarat nekünk egy új csomópontot. És akkor fogunk dolgozni a csomópont. 

Tehát, mivel a csomópont vagyunk ismét majd nézd meg a gyerekek tömb. És meg fogjuk nézni index nulla hogy megfelelnek az A a macska. Akkor fogunk menni, hogy a csomópont, és mivel a csomópont megyünk hogy nézd meg a végén, hogy ez egy megfelel T. és áttérnek az, hogy a csomópont, Végül, már teljesen úgy nézett a mi szó "cat". És most bool szó állítólag, hogy jelezze, ez adott szó valójában egy szót sem. 

Akkor miért van szükségünk, hogy a különleges eset? Nos, mi a helyzet a "katasztrófa" van a szótár, de a szó "cat", nem? Így, és keresi, hogy ha a "macska" van a szótár, vagyunk majd sikeresen nézze át Az indexek a C-A-T-csomópont a régióban. De ez csak azért, mert katasztrófa történt létrehozása csomópontok az úton : C-A-T, egészen a a végén a szót. Tehát bool szót használják annak jelzésére, hogy ez adott helyen valójában azt a szót. 

Rendben van. Most, hogy tudjuk, mi az trie az fog kinézni, nézzük meg a betölteni funkcióját. Tehát terhelést fog visszatérni a bool mert akár sikeresen vagy sikertelenül betöltött a szótárban. És ez lesz a szótárban hogy szeretnénk betölteni. 

Tehát az első dolog, amit mi a teendő nyitva fel, hogy a szótár az olvasáshoz. És meg kell, hogy megbizonyosodjon arról, nem buktunk. Tehát, ha a szótár nem sikeresen kinyitotta, hogy vissza fog térni null, ebben az esetben mi vagyunk majd vissza hamis. De feltételezve, hogy sikeresen nyitott, akkor lehet olvasni a szótárban. 

Tehát az első dolog, amit meg fogunk akarok, hogy itt van ez a globális változó gyökér. Most gyökér lesz egy csomópont *. Ez a tetején a trie, hogy mi vagyunk fog iterációjával keresztül. Tehát az első dolog, hogy megyünk hogy akarok a kiosztani memória a gyökér. Figyeljük meg, hogy mi a calloc funkció, ami lényegében ugyanaz a malloc függvény, kivéve, hogy biztos, hogy vissza valamit, ami teljesen nullázni ki. Tehát, ha használják malloc, meg kellene megy át a mutató a mi csomópont, és győződjön meg arról, hogy ők mind null. Így calloc fog tenni, hogy a számunkra. 

Most, mint malloc, meg kell, hogy arról, hogy a kiosztás valójában sikeres. Ha ez vissza null, akkor kell zárni vagy szótár fájlt, és vissza hamis. Tehát, feltételezve, hogy a kiosztás volt sikeres, fogunk egy node * kurzor halad végig a trie. Így a gyökerei soha nem fog változni, de fogunk használni kurzort valóban megy csomópontok közötti. 

Tehát ez a for ciklus olvasunk a szótár fájlt. És mi használ fgetc. Fgetc fog megragad egy karaktert a fájlból. Megyünk is megragadta karakter, amíg nem éri el a a fájl végén. 

Két esetben kell kezelni. Az első, ha a karakter nem volt egy új sort. Tehát tudjuk, hogy ez egy új sort, majd a vagyunk arról, hogy lépni egy új szót. De feltételezve, hogy ez nem egy új sort, majd a Itt szeretnénk kitalálni, hogy a index fogunk index a A gyerekek tömb néztük korábban. 

Szóval, mint már mondtam, meg kell speciális eset az aposztróf. Figyeljük meg, mi a hármas operátor itt. Így fogjuk olvasni ezt, ha a a karakter olvassuk volt aposztróf, akkor megyünk be index = "ABC" -1, ami az index 26. 

Különben, ha ez nem egy aposztróf, ott megyünk be az index egyenlő c - a. Így emlékszik vissza a korábban p-készletek, c - a fog adni nekünk a abc helyzete C. Tehát, ha C a betű, így nehezebb nekünk index nulla. A B betű, ez ad nekünk az 1-es index, és így tovább. 

Szóval ez ad nekünk az index a gyerekek tömb, amit akarunk. Nos, ha ez a mutató jelenleg null a gyerekeket, hogy az azt jelenti, hogy egy csomópont jelenleg nem létezik erről az útról. Tehát meg kell kiosztani a csomópont az úton. Ez az, amit mi itt csinálni. 

Így fogjuk újra használni a calloc funkciót, így nem kell nulla ki az összes mutató. És ismét ellenőrizni kell hogy calloc nem sikerül. Ha calloc nem sikerül, akkor meg kell kirak mindent, zárja be a szótár és a return false. Tehát, feltételezve, hogy nem sikerül, akkor Ez létrehoz egy új gyerek számunkra. És akkor majd megy, hogy a gyermek számára. A kurzor iterációkhoz le, hogy a gyermek számára. 

Nos, ha ez nem null kezdődik, akkor a kurzor is csak iterációkhoz le, hogy az a gyerek, anélkül, hogy kellene kiosztani semmit. Ez az eset áll fenn, amikor először történt osztja a "macska". És azt jelenti, hogy mikor megyünk kiosztani "Katasztrófa", nem kell létrehozni csomópontok a C-A-T-újra. Már léteznek. 

Mi ez a valami? Ez az az állapot, ahol c volt backslash n, ahol c egy új sort. Ez azt jelenti, hogy sikeresen elkészült egy szót sem. Most mit akarunk csinálni, amikor sikeresen befejezte egy szó? Fogjuk használni ezt a szót, a területen belsejében a struct csomópont. Azt szeretnénk beállítani, hogy igaz. Tehát, azt jelzi, hogy ez a csomópont jelzi a sikeres szó, a tényleges szó. 

Ezután állítsa be, hogy az igaz. Azt akarjuk állítani a kurzort a pont hogy az elején a trie újra. És végül, növelni a szótár méret, hiszen talált egy másik munkát. Így fogjuk tartani csinálja, olvasás karakterenként, építése az új csomópont a trie és minden szót a szótárban, amíg végül elérjük C! = EOF, amelyben esetben kitörni a fájlt. 

Most van két eset alatt amely talán megüt EOF. Az első az, ha nem volt hiba olvasni a fájlból. Tehát, ha nem volt hiba, akkor kell tennie a tipikus. Vegye ki mindent, közel A fájl, return false. Feltételezve, hogy nem volt hiba, hogy a csak azt jelenti, hogy valóban elérje a végén a fájlt, amely esetben zárjuk a fájlt, és vissza igaz, mivel sikeresen betöltve szótár a mi trie. 

Most nézzük meg ellenőrzést. Keresi a check funkció látjuk hogy ellenőrzés lesz, hogy visszatérjen a bool. Az igazat ad vissza, ha az a szó, hogy ez az hogy telt a mi trie. A HAMIS egyébként. Szóval, hogy van meghatározni, hogy ez a szó a mi trie? 

Látjuk, hogy itt, csakúgy, mint korábban, fogunk használni kurzor iterációkhoz keresztül trie. Most itt fogunk iterációkhoz mint a teljes szót. Így az iterációt szót túl vagyunk, megyünk, hogy meghatározzák a index a gyerekek tömb megfelel a szó zárójel I. Tehát ez fog úgy nézzen ki, mint a terhelés, ahol, ha szó [i] van egy aposztróf, akkor szeretnénk használata index "ABC" - 1. Mivel megállapítottuk, hogy ez ahol megyünk tárolni aposztrófok. 

Else fogjuk használni a két alsó szó konzol I. úgy emlékszem, hogy szó tetszőleges nagybetűk. És így azt szeretnénk, hogy győződjön meg arról, hogy mi egy kisbetűs változatát dolgokat. És akkor a kivonást, hogy az "a", hogy egyszer Ismét nekünk az alfabetikus helyzetben, hogy a karakter. Szóval ez lesz az index a gyerekek tömbben. 

És most, ha az index a gyerekek tömb null, ez azt jelenti, már nem is iterációjával le a trie. Ha ez a helyzet, ez a szó nem esetleg a mi trie. Mivel ha ez, amely azt jelenti, van egy út lenne le ezt a szót. És soha nem találkozik null. Így találkozik null, visszatérünk hamis. A szó nem szerepel a szótárban. Ha ez nem nulla, akkor vagyunk folytatjuk iterációjával. 

Így fogunk ott kurzor mutatni, hogy az adott node abban az index. Azt csinálom, hogy az egész a teljes szót, feltételezve, hogy mi soha nem sújtotta null. Ez azt jelenti, hogy sikerült átvészelni a teljes szót és megtalálni a csomópont a próbát. De nem egészen kész még. 

Nem akarjuk, hogy csak vissza igaz. Azt akarjuk, hogy visszatérjen kurzor> szót. Mivel emlékszem ismét a "macska" nem az a szótár, a "katasztrófa" van, akkor sikeresen kapunk keresztül a "macska". De a kurzor szó lesz, hamis és nem igaz. Így visszatérünk kurzort jelző szót hogy ez a csomópont valójában egy szót. És ez a csekk. 

Szóval nézd meg méretét. Tehát méretű lesz elég könnyű mivel emlékszem terhelés, vagyunk megnő szótár mérete Minden szó, hogy találkozunk. Tehát mérete csak fog vissza szótár méretét. És ennyi. 

Így végül már a memóriából. Tehát kirak, fogunk használni rekurzív függvény, hogy ténylegesen minden A munka számunkra. Így a funkció fog nevezhetjük a unloader. Mi unloader fog csinálni? Látjuk, hogy az ürítés fog végighaladni mind a gyerekek az adott csomópont. És ha a gyermek csomópont nem null, akkor megyünk kirak a gyermek csomópont. 

Tehát ez akkor rekurzív kirak Minden gyermek. Ha nem vagyunk biztosak, hogy gyermekeink kirakodását, akkor is szabad magunkat, így kirak magunkat. Ez a munka rekurzívan kirak az egész trie. És ha egyszer ez megtörtént, mi csak vissza igaz. Unload nem teheti meg. Mi csak felszabadítja a dolgokat. Tehát, ha már kész szabaddá Mindent vissza igaz. És ennyi. A nevem Rob. És ez volt a helyesírás. 

[MUSIC Playing]