[Musikk spilles] 

ROB BOWDEN: Hei. Jeg er Rob. Og la oss denne løsningen ut. Så her kommer vi til å implementere en generell tabell. Vi ser at struct node av vår tabellen kommer til å se slik ut. Så det kommer til å ha en char ord matrise av størrelse LENGDE + 1. Ikke glem + 1, siden den maksimale ord i ordlisten er 45 tegn. Og så kommer vi til å trenge en ekstra tegnet for backslash null. 

Og da er vår hashtabellen i hvert bøtte kommer til å lagre en lenket liste av noder. Vi gjør ikke lineær sondering her. Og så for å koble til den neste element i bøtta, trenger vi en struct node * neste. OK. Så det er hva en node ser ut. 

Nå her er erklæringen av vår hashtabellen. Det kommer til å ha 16 834 bøtter. Men dette tallet ikke virkelig betyr noe. Og til slutt, kommer vi til å ha den global variabel hashtabellen størrelse, som kommer til å starte som null. Og det kommer til å holde oversikt over hvordan mange ord er i vår ordbok. 

Så la oss ta en titt på lasten. Legg merke til at laste, returnerer den en bool. Du return true hvis det var vellykket lastet, og falsk ellers. Og det tar en const char * ordbok, som er ordlisten at vi ønsker å åpne. Så det er den første tingen vi kommer til å gjøre. 

Vi kommer til å fopen den ordbok for lesing. Og vi er nødt til å gjøre sikker på at det lyktes. Så hvis det returneres NULL, så vi gjorde ikke hell åpne ordboken. Og vi trenger å returnere false. Men forutsatt at det gjorde med hell åpen, så vi ønsker å lese ordbok. Så hold looping til vi finner noen Grunnen til å bryte ut av denne sløyfe, som vi skal se. Så hold looping. 

Og nå skal vi malloc en enkelt node. Og selvfølgelig må vi å lufte sjekke igjen. Så hvis mallocing ikke lykkes, da vi ønsker å losse noen node som vi skjedde med malloc før, lukker ordbok og return false. Men ignorerer det, forutsatt at vi lyktes, da vi ønsker å bruke fscanf å lese et eneste ord fra vår ordlisten, i vår node. Så husk at entry> Ordet er røye Ordet buffer størrelse lenghth + 1 at vi kommer til å lagre ordet i. 

Så fscanf kommer til å returnere en, så lenge som det var i stand til å lykkes lese et ord fra filen. Hvis enten en feil skjer, eller vi kommer til slutten av filen, den vil ikke returnere en. I så fall betyr det ikke returnere en, vi endelig kommer til å bryte ut av dette mens loop. Så vi ser at når vi har lykkes lese inn et ord i entry> ord, så vi kommer til at ordet med vår hash-funksjon. 

La oss ta en titt på hash-funksjon. Så du ikke virkelig trenger å forstå dette. Og faktisk vi bare trakk denne hash fungere fra internett. Det eneste du trenger å anerkjenne er at dette tar en const char * ord. Så det tar en streng som input, og returnere en usignert int som utgang. Så det er alt en hash-funksjon er, er det tar i en inngang og gir deg en indeksen inn hashtabellen. 

Legg merke til at vi Moding av NUM_BUCKETS, slik at verdien som returneres faktisk er en indeks inn i hashtabellen og indekserer ikke utover matrisegrensen. Så gitt at funksjonen skal vi til hasj ordet som vi leser ordbok. Og så skal vi bruke at hasj for å sette inn inntreden i hashtabellen. 

Nå hashtabellen hash er gjeldende lenket liste i tabellen. Og det er meget mulig at det er bare NULL. Vi ønsker å sette vår inntreden på I begynnelsen av denne lenket liste. Og så skal vi ha vår nåværende inngangspunkt til hva hashtabellen i dag peker på. Og så kommer vi til å lagre, i hashtabellen på hash, den gjeldende oppføringen. Så disse to linjene med hell sette trer ved begynnelsen av lenket liste ved at indeksen i hashtabellen. 

Når vi er ferdig med det, vi vet at vi fant et annet ord i ordboken, og vi øke igjen. Så vi fortsette med det inntil fscanf endelig tilbake noe ikke-1 i som peker huske at vi trenger å frigjøre oppføring. Så her oppe vi malloced en oppføring. Og vi prøvde å lese noe fra ordboken. Og om vi ikke lykkes lese noe fra ordboken, i hvilket tilfelle vi trenger å frigjøre oppføring at vi aldri faktisk satt i hashtabellen, og til slutt bryte. 

Når vi bryter ut vi trenger å se, vel, gjorde vi bryte ut fordi det ble en feil ved lesing fra filen? Eller gjorde vi bryte ut fordi vi nådd slutten av filen? Hvis det var en feil, så vi ønsker å returnere false. Fordi belastningen ikke lyktes. Og i den prosessen vi ønsker å losse alle ordene som vi leser i, og lukke ordlistefilen. 

Antar vi lykkes, så vi bare fortsatt trenger å lukke ordlisten fil, og til slutt returnere sant siden vi lastet ordlisten. Og det er det for last. Så nå sjekke, gitt en ladd hashtabellen, kommer til å se slik ut. Så sjekk, den returnerer en bool, som er kommer til å indikere hvorvidt passert i char * ord, om bestått i strengen er i vår ordbok. Så hvis det er i ordboken, hvis det er i vår hashtabellen, vi vil returnere true. Og hvis det ikke er det, vil vi returnere false. 

Gitt dette vedtatt i ord, er vi kommer til hasj ordet. Nå er en viktig ting å gjenkjenne er at belastningen vi visste at alle de ord vi skal være små bokstaver. Men her er vi ikke så sikker. Hvis vi tar en titt på vår hash-funksjon, vår hash-funksjon faktisk er lavere casing hvert tegn av ordet. Så uavhengig av kapitalisering av ord, er vår hash-funksjon retur den samme indeksen for uansett kapitalisering er, som det ville ha returneres for et helt små bokstaver versjon av ordet. Alright. Det er vår indeks er ned i Hashtabellen for dette ordet. 

Nå er dette for loop kommer til å iterere over lenket liste som var på den indeksen. Så oppdager vi initialisering oppføring å peke på at indeksen. Vi kommer til å fortsette mens oppføringen! = NULL. Og husk at å oppdatere pekeren i vår lenket liste entry = entry> neste. Så har vår nåværende inngangspunkt til det neste elementet i lenket liste. 

Så for hver oppføring i lenket liste, vi kommer til å bruke strcasecmp. Det er ikke strcomp. Fordi en gang, vi ønsker å gjøre ting tilfelle insensitively. Så vi bruker strcasecmp å sammenligne ord som ble ført gjennom denne funksjon mot ordet som er i dette innlegget. Hvis den gir null, som betyr at det var en kamp, ​​og da ønsker vi å returnere true. Vi vellykket funnet ord i vår hashtabellen. 

Hvis det ikke var en kamp, ​​så vi er kommer til å sløyfe igjen og se på neste oppføring. Og vi vil fortsette looping mens det er oppføringer i denne lenket liste. Hva skjer hvis vi bryter ut av dette for løkke? Det betyr at vi ikke finner en oppføring som matchet dette ordet, i så fall vi return false for å vise at vår hashtabellen inneholdt ikke dette ordet. Og det er en sjekk. 

Så la oss ta en titt på størrelse. Nå størrelse kommer til å være ganske enkel. Siden husker i lasten, for hvert ord Vi fant, vi økes en global variable hashtabellen størrelse. Så størrelsen funksjonen er bare kommer å returnere global variabel. Og det er det. 

Nå endelig, trenger vi å losse ordbok når alt er ferdig. Så hvordan skal vi gjøre det? Akkurat her vi looping løpet alle bøtter av bordet vårt. Så det er NUM_BUCKETS bøtter. Og for hver lenket liste i vår hashtabellen, vi skal til løkken over helheten av lenket liste, frigjør hvert element. 

Nå må vi være forsiktige. Så her har vi en midlertidig variabel som er lagring pekeren til neste element i lenket liste. Og så skal vi gratis det aktuelle elementet. Vi må være sikker på at vi gjør dette fordi vi kan ikke bare frigjøre det aktuelle elementet og deretter prøve å få tilgang til neste pekeren, siden når vi har befridd det, minnet blir ugyldig. 

Så vi trenger å holde rundt en peker til neste element, så vi kan frigjøre gjeldende element, og da kan vi oppdatere vår nåværende element for å peke på det neste element. Vi vil sløyfe mens det er elementer i dette lenket liste. Vi vil gjøre det for alle knyttet lister i hashtabellen. Og når vi er ferdig med det, vi har helt losset hashtabellen, og vi er ferdige. Så det er umulig for losse å stadig return false. Og når vi er ferdige, vi bare returnere true. 

La oss gi denne løsningen en prøve. Så la oss ta en titt på hva våre struct node vil se ut. Her ser vi at vi kommer til å ha en bool ord og en struct node * barn brakett alfabetet. Så det første du kan være lurer på, hvorfor er ALFABET ed definert som 27? Vel, husk at vi kommer til å trenge å være håndtering apostrof. Så det kommer til å bli litt av en spesialtilfelle gjennom dette programmet. 

Nå husker hvordan en trie faktisk fungerer. La oss si at vi indekserer ordet "katter." Deretter fra roten av trie, vi kommer til å se på barna matrise, og vi kommer til å se på indeks som tilsvarer bokstaven C. Så det vil bli indeksert to. Så gitt at, som vil gi oss en ny node. Og så får vi jobbe fra den noden. 

Så gitt at node, er vi nok en gang kommer til å se på barn array. Og vi kommer til å se på indeksen null for å svare til en på katten. Så da skal vi gå til den noden, og gitt at noden vi kommer å se på slutten er det en svarer til T. Og går videre til den noden, endelig, har vi helt sett gjennom vår ordet "katt". Og nå bool Ordet er ment å indikere om dette gitt ord er faktisk et ord. 

Så hvorfor trenger vi den spesielle saken? Vel hva med ordet "katastrofe" er i vår ordboken, men ordet "katt" er ikke det? Så og ønsker å se om ordet "katt" er i vår ordbok, er vi kommer til å lykkes se gjennom indeksene C-A-T i området node. Men det er bare fordi katastrofe skjedde for å skape noder på den måten fra C-A-T, helt til slutten av ordet. Så bool ordet brukes til å indikere om denne spesielle beliggenheten faktisk indikerer et ord. 

OK. Så nå som vi vet hva det trie er kommer til å se ut, la oss se på laste funksjon. Så last kommer til å returnere en bool for om vi lykkes eller uten hell lastet ordlisten. Og dette kommer til å være ordlisten at vi ønsker å laste. 

Så første vi skal gjøre er å åpne opp at ordboken for lesing. Og vi må sørge for at vi ikke mislykkes. Så hvis ordboken var ikke hell åpnet, vil den returnere null, og da er vi kommer til å returnere false. Men forutsatt at det med hell åpnet, så kan vi faktisk lese gjennom ordlisten. 

Så det første vi kommer til å ønsker å gjøre er vi har dette global variabel rot. Nå root kommer til å være en node *. Det er toppen av vår trie at vi er kommer til å bli itera gjennom. Så det første at vi skal å ønske å gjøre er å fordele minne for vår rot. Legg merke til at vi bruker den calloc funksjon, som er utgangspunktet det samme som malloc funksjon, bortsett fra det er garantert å returnere noe som er helt nullet ut. Så hvis vi brukte malloc, ville vi trenger å gå gjennom alle pekere i vår node, og sørge for at de er alle null. Så calloc vil gjøre det for oss. 

Nå akkurat som malloc, trenger vi å gjøre sikker på at tildeling var faktisk vellykket. Hvis dette returneres null, så vi må lukke eller ordbok fil og returnere false. Så anta at allokering ble vellykket, kommer vi til å bruke en node * markøren til reagere gjennom vår trie. Så våre røtter aldri kommer til å forandre seg, men vi kommer til å bruke markøren til faktisk gå fra node til node. 

Så i dette for loop vi leser gjennom ordboken filen. Og vi bruker fgetc. Fgetc kommer til å ta en enkelt karakter fra filen. Vi kommer til å fortsette å gripe tegn, mens vi ikke når slutten av filen. 

Det er to tilfeller vi trenger for å håndtere. Den første, hvis tegnet var ikke en ny linje. Så vi vet ikke om det var en ny linje, deretter vi er i ferd med å flytte til et nytt ord. Men forutsatt at det ikke var en ny linje, deretter her vi ønsker å finne ut av indeksen vi kommer til å indeksere inn i barn array som vi så på før. 

Så, som jeg sa før, må vi spesielt tilfelle apostrof. Legg merke til at vi bruker trefoldig operatør her. Så vi kommer til å lese dette som, hvis tegnet vi leste i var en apostrof, så vi kommer til å sette index = "Alphabet" -1, noe som vil være indeksen 26. 

Else, hvis det ikke var en apostrof, det vi kommer til å sette indeksen lik c - en. Så husker tilbake fra tidligere p-sett, c - en kommer til å gi oss alfabetisk stilling C. Så hvis C er bokstaven A, dette vil gi oss indeks null. For bokstaven B, vil det gi oss indeksen 1, og så videre. 

Så dette gir oss indeksen inn i barn array som vi ønsker. Nå hvis denne indeksen er for tiden null i barn, som betyr at en node øyeblikket ikke eksisterer fra denne banen. Så vi trenger å fordele en node for denne banen. Det er det vi skal gjøre her. 

Så vi kommer til å igjen bruke calloc funksjon, slik at vi ikke trenger å null ut alle pekere. Og vi igjen må sjekke at calloc ikke mislykkes. Hvis calloc gjorde mislykkes, så vi trenger å lesse alt, lukke våre ordbok, og return false. Så forutsatt at det ikke mislykkes, da Dette vil skape et nytt barn for oss. Og da vil vi gå til det barnet. Vår markøren vil iterere ned til at barnet. 

Nå hvis dette ikke var null til å begynne med, deretter markøren kan bare iterere ned til at barnet uten å faktisk å måtte fordele noe. Dette er tilfelle hvor vi først skjedd allokere ordet "kat." Og det betyr at når vi går å tildele "Katastrofe", vi trenger ikke å skape noder for C-A-T på nytt. De som allerede eksisterer. 

Hva er dette annet? Dette er den tilstand hvor c var backslash n, der c var en ny linje. Dette betyr at vi har lykkes gjennomført et ord. Nå hva vi vil gjøre når vi fullført et ord? Vi kommer til å bruke dette ordet feltet innsiden av våre struct node. Vi ønsker å sette det til sann. So som indikerer at denne noden indikerer en vellykket ord, en faktisk ord. 

Nå satt det til sann. Vi ønsker å tilbakestille vår markøren til punkt til begynnelsen av den trie nytt. Og til slutt, øke vår ordbok størrelse, siden vi fant en annen jobb. Så vi kommer til å fortsette med det, lesing i tegn for tegn, bygging av nye noder i vår trie og for hvert ord i ordlisten, inntil vi endelig kommer C! = EOF, der tilfelle vi bryte ut av filen. 

Nå er det to saker under som vi kan ha truffet EOF. Den første er om det var en feil lesing fra filen. Så hvis det var en feil, vi trenger å gjøre den typiske. Losse alt, tett filen, return false. Antar det ikke var en feil, at betyr bare at vi faktisk traff slutten av filen, og i så fall, vi lukker fil og returnere sant siden vi lastet ordbok inn i vår trie. 

Så nå la oss sjekke ut sjekken. Ser på sjekken funksjon, ser vi at sjekken kommer til å returnere en bool. Det returnerer true hvis dette ordet at det er blir vedtatt er i vår trie. Den returnerer false ellers. Så hvordan skal du finne ut om dette ordet er i vår trie? 

Vi ser her at, akkurat som før, vi kommer til å bruke markøren til å reagere gjennom vår trie. Nå her kommer vi til å reagere over vår hele ord. Så itera over ordet vi er forbi, vi kommer til å bestemme indeksen inn i barn array som tilsvarer ordet brakett I. Så dette kommer til å se ut akkurat som belastning, der hvis ordet [i] er en apostrof, da vi ønsker å bruke indeksen "Alphabet" - en. Fordi vi fastslått at det er der vi kommer til å lagre apostrofer. 

Else vi kommer til å bruke to lavere ordet brakett I. Så husk at ordet kan har vilkårlig kapitalisering. Og så ønsker vi å sørge for at vi er ved hjelp av en liten bokstav versjon av ting. Og deretter trekke fra det 'a' til en gang igjen gi oss den alfabetiske stilling av det tegnet. Så det kommer til å bli vår hovedside inn i barn array. 

Og nå om at indeksen inn barna matrise er null, betyr det at vi kan ikke lenger fortsette itera ned vår trie. Hvis det er tilfelle, dette ordet kan ikke muligens være i vår trie. Siden hvis det var, ville det mener det ville være en bane ned til det ordet. Og du vil aldri møte null. Så møter null, returnerer vi false. Ordet er ikke i ordboken. Hvis det ikke var null, så vi er kommer til å fortsette itera. 

Så vi går ut der markøren å peke på den aktuelle node på at indeksen. Vi fortsetter å gjøre det hele hele ordet, forutsatt vi aldri truffet null. Det betyr at vi var i stand til å komme gjennom hele ord og finne en node i våre forsøk. Men vi er ikke helt ferdig ennå. 

Vi ønsker ikke å bare returnere true. Vi ønsker å returnere markøren> ord. Siden huske igjen, er "cat" er ikke i vår ordbok, og "katastrofe" er, så vi vil lykkes får vi gjennom ordet "kat." Men markør Ordet vil være falske og ikke sant. Så vi tilbake markøren ord for å indikere vidt denne noden er faktisk et ord. Og det er det for sjekk. 

Så la oss sjekke ut størrelse. Så størrelsen kommer til å være ganske lett siden, husker i lasten, er vi økes ordbok størrelse for hvert ord som vi møter. Så størrelsen er bare kommer til å returnere ordbok størrelse. Og det er det. 

Så til slutt har vi losse. Så losse, kommer vi til å bruke en rekursiv funksjon å faktisk gjøre alt av jobben for oss. Så vår funksjon skal bli kalt på losser. Hva er losser kommer til å gjøre? Vi ser her at unloader kommer til å iterere over alle barna på denne noden. Og hvis barnet noden er ikke null, så vi kommer til å losse barnet node. 

Så dette er du rekursivt losse alle våre barn. Når vi er sikker på at alle våre barn har blitt losset, så vi kan frigjøre oss, så losse oss selv. Dette vil fungere rekursivt losse hele trie. Og så når det er gjort, vi kan bare returnere true. Losse kan ikke mislykkes. Vi bare frigjøre ting. Så når vi er ferdig å frigjøre alt, returnere true. Og det er det. Mitt navn er Rob. Og dette var stavekontroll. 

[Musikk spilles]