[Speel van musiek] 

ROB BOWDEN: Hi. Ek is Rob. En laat ons hierdie oplossing uit. So hier gaan ons te implementeer 'n algemene tafel. Ons sien dat die struct knoop van ons tafel gaan lyk soos hierdie. So dit gaan 'n kar woord te hê verskeidenheid van grootte lengte + 1. Moenie vergeet om die + 1, aangesien die maksimum woord in die woordeboek is 45 karakters. En dan gaan ons moet 'n ekstra karakter vir die backslash nul. 

En dan is ons hashtable in elke emmer gaan slaan 'n gekoppel lys van nodes. Ons doen nie lineêre indringende hier. En so in orde om te skakel na die volgende element in die emmer, moet ons 'n struct knoop * volgende. OK. So dit is wat 'n knoop lyk. 

Nou hier is die verklaring van ons hashtable. Dit gaan 16834 emmers te hê. Maar dat die getal nie regtig saak nie. En ten slotte, gaan ons die globale veranderlike hashtable grootte, wat gaan begin af as nul. En dit gaan die spoor van hoe om te hou baie woorde in ons woordeboek. 

So kom ons neem 'n blik op las. Let daarop dat die las is dit gee 'n Bool. Jy terugkeer waar as dit was suksesvol gelaai en valse anders. En dit neem 'n konst kar * woordeboek, wat is die woordeboek dat ons wil oopmaak. So wat is die eerste ding wat ons gaan doen. 

Ons gaan fopen die woordeboek vir lees. En ons gaan hê om te maak seker te maak dat dit daarin geslaag. So as dit terug NULL, dan is ons het nie die woordeboek suksesvol oop te maak. En ons moet valse om terug te keer. Maar die veronderstelling dat dit suksesvol gedoen oop, dan wil ons om te lees die woordeboek. So hou herhaling totdat ons 'n paar rede om te breek uit hierdie lus, wat ons sal sien. So hou herhaling. 

En nou is ons gaan malloc 'n enkele nodus. En natuurlik moet ons te lug weer na te gaan. So as mallocing nie slaag nie, dan Ons wil 'n knoop wat ons af te laai gebeur malloc voor, sluit die woordeboek en terugkeer onwaar. Maar ignoreer dat die aanvaarding van ons geslaag het, dan wil ons gebruik fscanf 'n enkele woord uit te lees ons woordeboek in ons node. So onthou dat inskrywing> woord is die kar woord buffer grootte LENGHTH + 1 dat ons gaan om die woord te stoor in 

So fscanf gaan terug 1, solank soos dit was in staat om suksesvol te lees 'n woord van die lêer. As óf 'n fout gebeur, of ons bereik die einde van die lêer, is dit sal nie terugkeer 1. In welke geval dit nie terug 1, ons uiteindelik gaan om te breek uit dit terwyl loop. So sien ons dat wanneer ons suksesvol lees 'n woord in inskrywing> woord, dan gaan ons wat woord met behulp van ons hash funksie. 

Kom ons neem 'n blik op die hash funksie. Sodat jy nie regtig nodig het nie om dit te verstaan. En eintlik het ons net hierdie hash getrek funksioneer van die internet. Die enigste ding wat jy nodig het om te erken, is dat dit neem om 'n konst kar * woord. So dit is wat 'n string as invoer, en terugkeer van 'n unsigned int as uitset. So dit is al wat 'n hash funksie is, is dit neem in 'n invoer en gee jou 'n indeks in die hashtable. 

Let daarop dat ons moding deur NUM_BUCKETS, sodat waarde wat eintlik is 'n indeks in die hashtable en nie verder as die indeks grense van die skikking. So gegee dat funksie, ons gaan die woord wat ons lees te hash die woordeboek. En dan gaan ons om te gebruik dat hash te voeg die toetrede tot die hashtable. 

Nou hashtable hash is die huidige geskakelde lys in die tabel. En dit is baie moontlik dat dit net 'NULL. Ons wil ons inskrywing aan die te voeg begin van hierdie geskakelde lys. En so gaan ons ons huidige te hê inskrywing punt wat die hashtable tans dui op. En dan gaan ons te slaan, in die hashtable by die hash, die huidige inskrywing. So het hierdie twee lyne suksesvol voeg die inskrywing aan die begin van die gekoppel lys op daardie indeks in die hashtable. 

Sodra ons klaar is met dit, ons weet dat ons het 'n ander woord in die woordeboek, en ons inkrementeer weer. So ons hou om dit te doen totdat fscanf uiteindelik terug iets nie-1 by watter punt onthou dat Ons moet toegang te bevry. So hier is ons malloced 'n inskrywing. En ons probeer om iets te lees van die woordeboek. En ons het nie suksesvol gelees iets uit die woordeboek, in welke geval ons moet die inskrywing te bevry dat ons nooit eintlik sit in die hashtable, en uiteindelik breek. 

Sodra ons breek ons ​​nodig het om te sien, wel, het ons breek, want daar is 'n fout met die lees van die lêer? Of het ons breek, want ons bereik die einde van die lêer? As daar 'n fout is, dan ons wil vals om terug te keer. Omdat vrag nie slaag nie. En in die proses het ons wil om af te laai al die woorde wat ons lees in, en sluit die woordeboek lêer. 

Veronderstelling ons het daarin slaag, dan het ons net nog steeds nodig om die woordeboek te sluit dien, en uiteindelik terug te keer waar nie, aangesien ons die woordeboek suksesvol gelaai. En dit is dit vir vrag. So nou gaan, gegee 'n gelaaide hashtable, gaan om te kyk soos hierdie. So gaan, dit gee 'n Bool, wat gaan om aan te dui of die geslaag in kar * woord, of die geslaag in string is in ons woordeboek. So indien dit in die woordeboek, As dit is in ons hashtable, Ons sal terugkeer waar. En as dit is nie, sal ons terugkeer onwaar. 

Gegee in woord hierdie geslaag het, is ons gaan om die woord te hash. Nou 'n belangrike ding om te besef is wat in die las ons het geweet dat al die woorde ons gaan laer geval te wees. Maar hier is ons nie so seker nie. As ons neem 'n blik op ons hash funksie, ons hash funksie eintlik laer omhulsel elke karakter van die woord. So, ongeag van die kapitalisasie van woord, ons hash funksie is om die opbrengs dieselfde indeks vir wat ook al die kapitalisasie is, as dit sou hê terug vir 'n heeltemal klein weergawe van die woord. Goed. Dit is die indeks is in die hashtable vir hierdie woord. 

Nou is dit vir lus gaan Itereer oor die geskakelde lys Dit was op daardie indeks. So sien ons initializing inskrywing om aan te dui dat die indeks. Ons gaan om voort te gaan terwyl inskrywing! = NULL. En onthou dat die opdatering van die wyser in ons gekoppel lys entry = entry> volgende. So het ons huidige inskrywing punt te die volgende item in die geskakelde lys. 

So vir elke inskrywing in die geskakelde lys, ons gaan strcasecmp te gebruik. Dit is nie strcomp. Omdat weer, ons wil doen dinge geval insensitively. So gebruik ons ​​strcasecmp te vergelyk woord wat deur middel van hierdie geslaag is funksie teen die woord Dit is in hierdie inskrywing. As dit terugkeer nul, wat beteken dat daar 'n wedstryd, in welke geval ons wil terug waar. Ons het met sukses het die woord in ons hashtable. 

As daar nie 'n wedstryd, dan is ons gaan loop weer en kyk na die volgende inskrywing. En ons sal voortgaan om herhaling terwyl daar is inskrywings in hierdie verband lys. Wat gebeur as ons breek uit hierdie lus? Dit beteken dat ons nie 'n inskrywing te vind dat ooreenstem met hierdie woord, in welke geval ons terugkeer valse aan te dui dat ons hashtable het nie hierdie woord bevat. En dit is 'n tjek. 

So kom ons neem 'n blik op die grootte. Nou grootte gaan wees eenvoudig. Sedert onthou in las, vir elke woord ons gevind het, het ons geinkrementeer 'n globale veranderlike hashtable grootte. So het die grootte funksie is net gaan globale veranderlike om terug te keer. En dit is dit. 

Nou uiteindelik, moet ons los die woordeboek sodra alles is gedoen. So hoe gaan ons dit doen? Right hier is ons herhaling oor al emmers ons tafel. So is daar NUM_BUCKETS emmers. En vir elke gekoppel lys in ons hashtable, gaan ons lus oor die geheel van die geskakelde lys, bevry elke element. 

Nou moet ons versigtig wees. So hier het ons 'n tydelike veranderlike dit is die stoor van die wyser na die volgende element in die geskakelde lys. En dan gaan ons vry Die huidige element. Ons moet seker maak ons ​​doen dit omdat ons wees kan nie net vry om die huidige element en probeer dan die volgende wyser om toegang te verkry, sedert wanneer het ons bevry het, die geheue ongeldig. 

Dus moet ons om 'n wyser te hou die volgende element, dan kan ons bevry van die huidige element, en dan kan ons werk ons huidige element om aan te dui die volgende element. Ons sal loop, terwyl daar is elemente in hierdie verband lys. Ons sal doen wat vir alle gekoppelde lyste in die hashtable. En sodra ons klaar is met wat ons het heeltemal gelaai is die hashtable, en ons gedoen het. Dus is dit onmoontlik vir, aflaai ooit vals terugkeer. En wanneer ons klaar is, het ons net terug waar. 

Kom ons gee hierdie oplossing 'n drie. So laat ons 'n blik op wat ons struct knoop sal lyk. Hier sien ons ons gaan 'n Bool te hê woord en 'n struct knoop * kinders bracket alfabet is. Dus is die eerste ding wat jy kan wees wonder, hoekom is ALPHABET ed gedefinieer as 27? Wel, onthou dat ons gaan nodig word die hantering van die toespraak. So wat gaan 'n bietjie van 'n spesiale geval in hierdie program. 

Onthou nou hoe 'n tydstip waarop eintlik werk. Kom ons sê dat ons die woord is kruip "Katte." Dan uit die wortel van die Trie, ons gaan om te kyk na die kinders skikking, en ons gaan om te kyk na die indeks wat ooreenstem met die letter C. So wat geïndekseer sal word 2. So gegee dat, dit sal gee ons 'n nuwe knoop. En dan sal ons die werk van die knoop. 

So gegee dat knoop, ons is weer gaan om te kyk na die kinders skikking. En ons gaan om te kyk na indeks nul ooreenstem met die A in kat. So dan gaan ons na daardie knoop, en gegee dat node ons gaan om te kyk na die ou end is dit 'n ooreenstem T. en beweeg na die knoop, Ten slotte, ons het heeltemal gelyk deur middel van ons woord "kat." En nou Bool woord is veronderstel om aan te dui of hierdie gegewe woord is eintlik 'n woord. 

So hoekom moet ons daardie spesiale geval? Wel, wat van die woord "katastrofe" is in ons woordeboek, maar die woord "kat" is nie? So en soek om te sien of die woord "kat" is in ons woordeboek, ons is gaan om suksesvol te kyk deur die indekse C-A-T in streek-knoop. Maar dit is net omdat katastrofe gebeur nodes op die pad te skep van C-A-T, al die pad na die einde van die woord. So Bool woord word gebruik om aan te dui of hierdie spesifieke plek eintlik dui op 'n woord. 

Alle regte. So nou dat ons weet wat dit is Trie gaan lyk, laat ons kyk na die laai funksie. So vrag gaan 'n Bool om terug te keer Want as ons suksesvol of onsuksesvol gelaai die woordeboek. En dit gaan die woordeboek te wees wat ons wil om te laai. 

So die eerste ding wat ons moet doen, is om oop up dat woordeboek vir lees. En ons het om seker te maak ons het nie misluk nie. So as die woordeboek was nie suksesvol oopgemaak word, sal dit terugkeer nul, in welke geval ons is gaan valse om terug te keer. Maar die veronderstelling dat dit suksesvol oopgemaak het, dan kan ons eintlik lees deur die woordeboek. 

So die eerste ding wat ons gaan wil doen, is ons hierdie globale veranderlike wortel. Nou wortel gaan 'n knoop te wees *. Dit is die top van ons Trie dat ons gaan word iterating deur. Dus is die eerste ding wat ons gaan te wil doen, is die toekenning geheue vir ons wortel. Let daarop dat ons met behulp van die calloc funksie, wat is basies dieselfde as die malloc funksie nie, behalwe dit is gewaarborg iets wat om terug te keer heeltemal zeroed uit. So as ons gebruik malloc, sou ons nodig het om te gaan deur al die verwysings in ons knoop, en maak seker dat hulle is almal null. So calloc sal dit doen vir ons. 

Nou net soos malloc, het ons nodig het om te maak seker te maak dat die toekenning was eintlik suksesvol. As dit teruggekeer null, dan het ons nodig het om te sluit of 'n woordeboek lêer en terugkeer onwaar. So die veronderstelling dat die toekenning is suksesvol is, gaan ons 'n knoop te gebruik * wyser na Itereer deur ons Trie. So ons wortels gaan nooit verander nie, maar ons gaan wyser te gebruik om te eintlik gaan van knoop tot knoop. 

So in hierdie lus vir ons lees deur die woordeboek lêer. En ons gebruik fgetc. Fgetc gaan 'n enkele te gryp karakter van die lêer. Ons gaan om voort te gaan gryp karakters terwyl ons bereik nie die einde van die lêer. 

Daar is twee gevalle het ons nodig het om te hanteer. Die eerste, as die karakter was nie 'n nuwe reël. So ons weet of dit 'n nuwe lyn, dan ons is oor te skuif na 'n nuwe woord. Maar die veronderstelling dat dit was nie 'n nuwe lyn, dan Hier wil ons om uit te vind die indeks gaan ons na die indeks in in die kinders skikking wat Ons kyk na voor. 

So, soos ek gesê het, moet ons spesiale geval die toespraak. Let ons die gebruik van die drieledige operateur hier. So ons gaan om dit te lees as, indien die karakter lees ons in was 'n toespraak, dan gaan ons te stel indeks = "ALPHABET" -1, wat sal wees om die indeks 26. 

Anders, as dit nie was 'n toespraak, is daar ons gaan die indeks op te stel gelyk aan c - a. So onthou terug uit voorheen p-stelle, c - a gaan ons die te gee alfabetiese posisie van C. So as C is die letter A, dit sal gee ons indeks nul. Vir die letter B, sal dit gee ons die indeks 1, en so aan. 

So dit gee ons die indeks in die kinders skikking wat ons wil hê. Nou as die indeks is tans nul in die kinders, wat beteken dat 'n knoop nie tans bestaan uit daardie pad. So het ons nodig het om te ken 'n knoop vir die pad. Dit is wat ons hier sal doen. 

So ons gaan weer die calloc funksie, sodat ons nie hoef te nul al die wysers. En ons weer moet kyk dat calloc het nie misluk nie. As calloc het misluk, dan moet ons om alles te los, sluit ons woordeboek, en terug onwaar. So die veronderstelling dat dit nie slaag nie, dan dit sal 'n nuwe kind skep vir ons. En dan gaan ons na die kind. Ons wyser sal Itereer af aan daardie kind. 

Nou as dit was nie null met om te begin, dan die wyser kan net Itereer af aan daardie kind sonder om werklik om iets te ken. Dit is die geval waar ons die eerste keer gebeur het ken die woord "kat." En Dit beteken dat wanneer ons gaan te ken "Katastrofe," het ons nie nodig om te skep nodes vir C-A-T weer. Hulle het reeds bestaan. 

Wat is dit anders? Dit is die toestand waar c was backslash n, waar c 'n nuwe lyn. Dit beteken dat ons suksesvol voltooi 'n woord. Nou wat wil ons doen wanneer ons 'n woord suksesvol voltooi? Ons gaan hierdie woord veld te gebruik binnekant van ons struct knoop. Ons wil om dit te stel waar. So wat daarop dui dat hierdie knoop dui op 'n suksesvolle woord, 'n werklike woord. 

Stel nou dat waar. Ons wil ons wyser te herstel na punt aan die begin van die Trie weer. En uiteindelik, inkrementeer ons woordeboek grootte, aangesien ons het 'n ander werk. So ons gaan hou om dit te doen, lees in karakter deur karakter, die bou van nuwe nodes in ons Trie en vir elke woord in die woordeboek, totdat het ons uiteindelik bereik C! = EOF, waarin geval ons breek van die lêer. 

Nou is daar twee gevalle onder wat ons kan EOF getref het. Die eerste is as daar 'n fout die lees van die lêer. So as daar was 'n fout, ons moet die tipiese te doen. Los alles, naby die lêer, terugkeer onwaar. Veronderstelling daar was nie 'n fout, wat beteken net ons eintlik getref die einde van die lêer, in watter geval, ons sluit die lêer en terugkeer waar nie, aangesien ons suksesvol gelaai woordeboek in ons Trie. 

So nou, laat ons gaan uit check. Kyk na die tjek funksie, sien ons daardie tjek gaan 'n Bool om terug te keer. Dit gee waar as hierdie woord wat dit is oorgedra is in ons Trie. Dit gee valse anders. So hoe gaan jy bepaal of hierdie woord is in ons Trie? 

Ons sien hier dat, net soos tevore, ons gaan wyser te gebruik om Itereer deur ons Trie. Nou hier gaan ons Itereer oor ons hele woord. So iterating oor die woord wat ons is verby, ons gaan om te bepaal die indeks in die kinders skikking wat ooreenstem met woord bracket I. So hierdie gaan lyk presies soos vrag, waar as woord [i] is 'n toespraak, dan wil ons indeks "ALPHABET" te gebruik - 1. Omdat ons bepaal dat is waar ons gaan te stoor apostrofes. 

Anders gaan ons twee onderste woord te gebruik bracket I. So onthou dat die woord kan het arbitrêre kapitalisasie. En so het ons wil om seker te maak dat ons maak gebruik van 'n klein weergawe van die dinge. En dan trek uit daardie 'n "een keer weer gee ons die alfabetiese posisie van die karakter. So wat gaan ons indeks te wees in die kinders skikking. 

En nou, as die indeks in die kinders skikking is nul, wat beteken dat ons kan nie meer voortgaan iterating down ons Trie. As dit die geval is, is hierdie woord kan nie moontlik wees in ons Trie. Want as dit was, sou dit beteken dat daar 'n pad wees af te wat die woord. En jy sal nooit ontmoet null. So stuit nul, keer ons terug onwaar. Die woord is nie in die woordeboek. As dit nie was nul, dan is ons gaan iterating om voort te gaan. 

So ons gaan daar wyser om te wys op die besondere knoop op die indeks. Ons hou doen wat dwarsdeur die hele woord, in die veronderstelling ons nooit getref null. Dit beteken dat ons in staat was om deur te kom die hele woord en kry 'n knoop in ons probeer. Maar ons is nog nie heeltemal klaar nie. 

Ons wil nie net terug waar. Ons wil wyser> woord om terug te keer. Sedert onthou weer, is "kat" is nie in ons woordeboek, en "katastrofe" is, sal ons suksesvol ons deur die woord "kat." Maar wyser woord sal vals en nie waar wees nie. So ons terugkeer wyser woord aan te dui of hierdie knoop is eintlik 'n woord. En dit is dit vir check. 

So laat ons kyk na die grootte. So grootte gaan wees redelik maklik sedert, onthou in vrag, ons is die verhoog woordeboek grootte vir elke woord wat ons teëkom. So grootte is net gaan om te terug woordeboek grootte. En dit is dit. 

So laastens ons los. So los, gaan ons gebruik om 'n rekursiewe funksie te eintlik al van die werk vir ons. So ons funksie gaan word 'n beroep op losser. Wat is losser gaan doen? Ons sien hier dat losser gaan Itereer oor al die kinders wat by hierdie spesifieke knoop. En as die kind knoop is nie nul, dan gaan ons los die kind knoop. 

So dit is wat jy herhaaldelik los almal van ons kinders. Sodra ons is seker dat al ons kinders is afgelaai het, dan het ons kan bevry onsself, so los onsself. Dit sal rekursief te werk los die hele Trie. En dan sodra dit gedoen is, ons kan net terug waar. Los nie kan misluk nie. Ons is net bevry dinge. So wanneer ons klaar is bevry alles terug waar. En dit is dit. My naam is Rob. En dit was speller. 

[Speel van musiek]