[MUSIK SPELA] 

ROB BOWDEN: Hej. Jag är Rob. Och låt oss denna lösning ut. Så här är vi kommer att genomföra en allmän tabell. Vi ser att struct nod i vår tabellen kommer att se ut så här. Så det kommer att ha en char ord matris med storlek LÄNGD + 1. Glöm inte + 1, eftersom den maximala ord i ordlistan är 45 tecken. Och sedan ska vi behöva en extra tecknet för backslash noll. 

Och sedan vår Hashtable i varje skopan kommer att lagra en länkad lista av noder. Vi gör inte linjär sondering här. Och så för att länka till nästa inslag i hinken, vi behöver en struct node * nästa. OK. Så det är vad en nod ser ut. 

Nu här är förklaringen av vår hashtable. Det kommer att ha 16.834 hinkar. Men den siffran spelar egentligen ingen roll. Och slutligen, kommer vi att ha globala variabeln hashtable storlek, vilket kommer att börja som noll. Och det kommer att hålla reda på hur många ord i vår ordlista. 

Så låt oss ta en titt på last. Lägg märke till att lasten, returneras en bool. Du return true om det var lyckat laddad, och i annat fall false. Och det tar en const char * ordbok, vilket är ordboken att vi vill öppna. Så det är det första vi ska göra. 

Vi ska fopen den ordlista för läsning. Och vi kommer att behöva göra Se till att det lyckades. Så om det returneras NULL, sedan gjorde vi inte framgångsrikt öppna ordlistan. Och vi måste returnera false. Men om man antar att den gjorde med framgång öppen, då vill vi att läsa ordboken. Så håll looping tills vi hittar några anledning att bryta sig ut ur denna slinga, som vi får se. Så håll looping. 

Och nu ska vi malloc en enda nod. Och naturligtvis behöver vi till luft kontrollera igen. Så om mallocing inte lyckades, sedan vi önskar att lasta av någon nod som vi hänt med malloc innan, stänger ordbok och returnera false. Men ignorera det, förutsatt att vi lyckats, då vill vi använda fscanf att läsa ett enda ord från vår dictionary i vårt nod. Så kom ihåg att posten> Ordet är rödingen ordet buffert av storlek lenghth + 1 att vi kommer att lagra ord i. 

Så fscanf kommer att återvända 1, så länge eftersom det kunde framgångsrikt läsa ett ord från filen. Om antingen ett fel inträffar, eller vi når slutet av filen, det kommer inte tillbaka 1. I vilket fall är det inte återvänder 1, vi äntligen kommer att bryta sig ur detta medan slinga. Så vi ser att när vi har lyckats läsa ett ord i entry> ord, då vi ska det ordet med vår hashfunktion. 

Låt oss ta en titt på hashfunktionen. Så du behöver egentligen inte att förstå detta. Och faktiskt vi bara drog denna hash fungera från Internet. Det enda du behöver för att känna igen är att det tar en const char * ord. Så det tar en sträng som indata, och returnera en unsigned int som produktion. Så det är allt en hash-funktion, är det tar i en ingång och ger dig en index i hashtable. 

Lägg märke till att vi Moding av NUM_BUCKETS, så att värdet som returneras faktiskt är ett index in i hashtable och inte index bortom gränserna för arrayen. Så med tanke på att funktionen ska vi att hash det ord som vi läser ordboken. Och sedan ska vi använda som hash att infoga inträde i hashtable. 

Nu hashtable hash är den aktuella lista länkad i tabellen. Och det är mycket möjligt att det bara är NULL. Vi vill sätta in vårt inträde på början av denna länkade lista. Och så ska vi ha vår nuvarande inkörsport till vad hashtable för närvarande pekar på. Och då kommer vi att lagra, i hashtable vid hash, den aktuella posten. Så dessa två linjer framgångsrikt sätt in posten i början av länkade listan vid detta index i hashtable. 

När vi är klara med det, vi vet att vi hittat ett annat ord i lexikon, och vi öka igen. Så vi fortsätter att göra det tills fscanf äntligen tillbaka något icke-1 vid vilken punkt ihåg att Vi måste frigöra posten. Så här uppe malloced vi en post. Och vi försökte läsa något från ordlistan. Och vi har inte lyckats läsa något från ordlistan, i då vi måste frigöra posten att vi aldrig tas i hashtable, och slutligen gå av. 

När vi bryter ut måste vi se, ja, vi bryta ut eftersom det var ett fel vid läsning från filen? Eller har vi bryta ut, eftersom vi nått slutet av filen? Om det fanns ett fel, då Vi vill returnera false. Eftersom lasten inte lyckades. Och i processen vi vill lasta alla de ord som vi läser in och stäng ordlistefilen. 

Förutsatt att vi lyckades, då vi bara ändå måste stänga i ordlistan fil, och slutligen återvänder sant eftersom vi lästs in i ordlistan. Och det är det för last. Så nu kontrollera, med tanke på en laddad hashtable, kommer att se ut så här. Så kolla, den returnerar en bool, som är kommer att ange om det gått i char * ord, om det gått i strängen är i vår ordlista. Så om det är i ordlistan, om det är i vår hashtable, vi återkommer sant. Och om det inte är, kommer vi att returnera false. 

Med tanke på detta gick i ord, vi är kommer att hash ordet. Nu en viktig sak att inse är att vi i lasten visste, att alla av ord vi kommer att vara gemener. Men här är vi inte så säker. Om vi ​​tar en titt på hash-funktion, vår hashfunktion faktiskt är lägre hölje varje tecken av ordet. Så oavsett kapitalisering av ord, är vår hashfunktion retur samma index för oavsett den aktivering är, eftersom det skulle ha returneras för en helt gement version av ordet. Alright. Det är vårt index är i Hashtable för detta ord. 

Nu är detta för slinga kommer att iterera över den länkade listan Det var vid detta index. Så märker vi att initiera inresa att peka på detta index. Vi kommer att fortsätta medan posten! = NULL. Och kom ihåg att uppdatera pekaren i vår länkad lista posten = entry> nästa. Så har vår nuvarande ingång till nästa objekt i den länkade listan. 

Så för varje post i den länkade listan, vi kommer att använda strcasecmp. Det är inte strcomp. Därför att en gång, vill vi göra saker fallet okänsligt. Så vi använder strcasecmp att jämföra ord som fick passera genom denna funktion mot ordet det är i denna post. Om den returnerar noll, betyder att det inte var en match, i vilket fall vi vill return true. Vi fann framgångsrikt ordet i vår hashtable. 

Om det fanns inte en match, då är vi gå till loop igen och titta på nästa post. Och vi kommer att fortsätta looping medan det är poster i detta länkad lista. Vad händer om vi bryter ur detta för loop? Det betyder att vi inte hittade en post som matchas detta ord, i vilket fall vi returnera false för att ange att vår hashtable inte innehöll detta ord. Och det är en check. 

Så låt oss ta en titt på storlek. Nu storlek kommer att vara ganska enkelt. Sedan minns i lasten, för varje ord vi hittade, vi ökas en global variabel hashtable storlek. Så storleksfunktionen är bara att gå att återvända globala variabeln. Och det är det. 

Nu äntligen, måste vi lasta av dictionary när allt är gjort. Så hur ska vi göra det? Just här vi looping över alla segment av vårt bord. Så det finns NUM_BUCKETS hinkar. Och för varje länkad lista i vår hashtable, vi ska slinga över helheten av den länkade listan, frigöra varje element. 

Nu måste vi vara försiktiga. Så här har vi en temporär variabel som är lagra pekaren till nästa elementet i den länkade listan. Och sedan ska vi gratis det aktuella elementet. Vi måste vara säkra på att vi gör detta eftersom vi kan inte bara befria det aktuella elementet och sedan försöka komma till nästa pekare, sedan när vi har befriat det, minnet blir ogiltig. 

Så vi måste hålla runt en pekare till nästa element, då vi kan frigöra aktuellt element, och då kan vi uppdatera vår nuvarande elementet att peka på nästa element. Vi ska slinga medan det finns inslag i detta länkad lista. Vi ska göra det för alla länkade listor i hashtable. Och när vi är klara med det, vi har helt lossas hashtable, och vi är klara. Så det är omöjligt att lossa att någonsin returnera false. Och när vi är klara, vi bara return true. 

Låt oss ge denna lösning ett försök. Så låt oss ta en titt på vad vår struct node kommer att se ut. Här ser vi att vi kommer att ha en bool ord och en struct node * barn fäste alfabetet. Så det första du kan vara undrar, varför är ALFABETET ed definierad som 27? Tja, kom ihåg att vi kommer att behöva att hantera apostrof. Så det kommer att bli något av en specialfall under hela detta program. 

Nu minns hur en trie faktiskt fungerar. Låt oss säga att vi indexera ordet "katter". Sedan från roten av trie, vi kommer att titta på barnen samling, och vi kommer att titta på index som motsvarar den bokstav C. Så det kommer att indexeras 2. Så med tanke på att, som kommer ge oss en ny nod. Och så kommer vi arbeta utifrån den noden. 

Så med tanke på den noden, vi är återigen kommer att titta på barnen arrayen. Och vi kommer att titta på index noll att motsvara A i katt. Så då ska vi gå till den noden, och med tanke på att noden ska vi att titta på slutet är det en motsvarar till T. Och går vidare till den noden, Slutligen har vi helt tittat genom vårt ord "cat". Och nu bool Ordet är tänkt att indikera om Detta givet ord är faktiskt ett ord. 

Så varför behöver vi den där speciella fall? Väl vad ordet "katastrof" är enligt vår ordbok, men den ordet "katt" är inte? Så och titta för att se om ordet "katt" är i vår ordlista, vi är kommer att lyckas titta igenom indexen C-A-T i regionen nod. Men det är bara för katastrof råkade skapa noder på vägen från C-A-T, hela vägen till i slutet av ordet. Så bool ordet används för att indikera huruvida denna särskilda plats faktiskt visar ett ord. 

Okej. Så nu när vi vet vad det trie är kommer att se ut, låt oss titta på det ladda funktion. Så belastningen kommer att returnera en bool för om vi lyckas eller utan framgång laddat ordlistan. Och det kommer att bli i ordlistan att vi vill läsa. 

Så första vi ska göra är att öppna up som lexikon för läsning. Och vi måste se till vi inte misslyckas. Så om ordlistan var inte öppnat, återgår null, i vilket fall vi är kommer att returnera false. Men om man antar att det framgångsrikt öppnas, då kan vi faktiskt läsa genom ordboken. 

Så första vi tänker vill göra är att vi har den här globala variabeln rot. Nu root kommer att bli en nod *. Det är högst upp på vår trie att vi är kommer att iterera igenom. Så det första som vi ska att vilja göra är att fördela minne för vår rot. Lägg märke till att vi använder calloc funktion, vilket är i stort sett samma som malloc funktion, förutom att det är garanterat att återvända något som är helt nollställd ut. Så om vi använt malloc, skulle vi behöva gå igenom alla tips i vår nod, och se till att de är alla null. Så calloc kommer att göra det åt oss. 

Nu precis som malloc, vi måste göra Se till att tilldelningen var faktiskt framgångsrik. Om detta återvände null, då vi behöva stänga eller ordbok filen och returnera false. Så antar att fördelningen var framgångsrik, vi kommer att använda en nod * markören för att iterera genom vår trie. Så våra rötter aldrig kommer att förändras, men vi kommer att använda markören till faktiskt gå från nod till nod. 

Så i detta för slinga vi läser genom ordlistefilen. Och vi använder fgetc. Fgetc kommer att ta en enda tecken från filen. Vi kommer att fortsätta att ta tag tecken när vi inte når slutet av filen. 

Det finns två fall som vi måste hantera. Den första, om karaktären var inte en ny rad. Så vi vet om det var en ny linje, då vi håller på att gå vidare till ett nytt ord. Men om det nu inte var en ny linje, då Här vill vi ta reda på index vi ska index i i barn array som vi tittat på tidigare. 

Så, som jag sa tidigare, vi måste specialfall apostrof. Lägg märke till att vi med hjälp av ternära operatör här. Så vi kommer att läsa detta som, om karaktären läser vi i var en apostrof, då ska vi ställa index = "Alfabet" -1, vilket kommer vara indexet 26. 

Annars, om det inte var en apostrof, finns vi ska ställa in index lika med c - en. Så minns tillbaka från tidigare p-apparater, c - a kommer att ge oss alfabetisk position C. Så om C är bokstaven A, detta kommer ge oss index noll. För bokstaven B, kommer det att ge oss index 1, och så vidare. 

Så detta ger oss indexet i barn array som vi vill ha. Nu, om detta index är närvarande null barnen, det betyder att en nod för närvarande inte finns från den vägen. Så vi måste avsätta en nod för den vägen. Det är vad vi gör här. 

Så vi kommer att åter använda calloc funktion, så att vi inte behöver nollställa alla pekare. Och vi återigen måste kontrollera att calloc inte misslyckas. Om calloc gjorde misslyckas, då behöver vi att lasta av allt, stänga vår lexikon, och returnera false. Så antar att det inte misslyckas, då detta kommer att skapa ett nytt barn för oss. Och då kommer vi till det barnet. Vår Markören iterera ner till det barnet. 

Nu, om detta inte var noll till att börja med, sedan markören kan bara iterera ner till barnet utan att behöva fördela någonting. Detta är fallet när vi först hände fördela ordet "katt". Och det betyder när vi går för att fördela "Katastrof" vi inte behöver skapa noder för C-A-T igen. De finns redan. 

Vad är det annars? Detta är det tillstånd där c var snedstreck n, där c var en ny rad. Det innebär att vi har lyckats avslutade ett ord. Nu vad vi vill göra när vi framgångsrikt slutfört ett ord? Vi kommer att använda detta ord fält insidan av vår struct nod. Vi vill ställa den till true. Så som tyder på att denna nod indikerar en framgångsrik ord, en verklig ord. 

Nu satt det till true. Vi vill återställa vår markören till punkt till början av trie igen. Och slutligen, öka vår ordlista storlek, eftersom vi hittat ett annat arbete. Så vi kommer att fortsätta göra det, läsa in tecken för tecken, bygga nya noder i vår trie och för varje ord i ordlistan, tills vi äntligen når C! = EOF, där fall bryter vi ut filen. 

Nu finns det två ärenden enligt som vi kanske har drabbat EOF. Den första är om det fanns ett fel läsning från filen. Så om det var ett misstag, vi måste göra den typiska. Lasta allt, nära filen, returnera false. Förutsatt att det inte var ett misstag, att bara innebär att vi faktiskt träffade i slutet av filen, i vilket fall, vi stänger filen och returnera sant eftersom vi laddats lexikon in i vår trie. 

Så nu ska vi kolla check. Om man tittar på funktionskontrollen, ser vi att kontrollen kommer att returnera en bool. Den returnerar sant om detta ord att det är överförs är i vår trie. Den returnerar false annars. Så hur ska du avgöra om detta ord är i vår trie? 

Vi ser här att, precis som tidigare, vi kommer att använda markören för att iterera genom vår trie. Nu här vi kommer att iterera över hela vårt ord. Så iteration över ordet vi är förbi, vi kommer att bestämma index till barn array som motsvarar ordet fäste I. Så detta kommer att se ut exakt som belastning, där om ord [i] är en apostrof, då vi vill ha att använda index "ALPHABET" - 1. Eftersom vi fastställt att det är där vi kommer att lagra apostrofer. 

Annars ska vi använda två nedre ord fäste I. Så kom ihåg det ordet kan ha godtycklig kapitalisering. Och så vill vi se till att vi är med hjälp av en gemen version av saker. Och sedan dra ifrån att "en" att en gång återigen ge oss den alfabetiska ställning av denna karaktär. Så det kommer att bli vårt index till barn array. 

Och nu om detta index till barnen matris är noll, innebär att vi inte längre kan fortsätta iteration ner vår trie. Om så är fallet, detta ord kan inte möjligen vara i vår trie. Sedan om det var, skulle det innebära att det skulle finnas en bana ner till det ordet. Och du skulle aldrig stöta på null. Så möter null, återvänder vi falskt. Ordet finns inte i ordlistan. Om det inte var noll, då är vi kommer att fortsätta iteration. 

Så vi ska ut där markören för att peka på den särskilda nod vid detta index. Vi fortsätter att göra det hela hela ordet, förutsatt Vi slog aldrig noll. Det betyder att vi skulle kunna få igenom hela ordet och hitta en nod i våra försök. Men vi är inte riktigt klar ännu. 

Vi vill inte bara return true. Vi vill återvända markören> ord. Sedan minns igen, är "katten" är inte i vår ordlista och "katastrof" är, då kommer vi att lyckas får vi genom ordet "katt". Men markören Ordet är falsk och inte sant. Så vi återvänder markören ord för att indikera huruvida denna nod är faktiskt ett ord. Och det är den för kontroll. 

Så låt oss kolla storlek. Så storlek kommer att bli ganska lätt sedan, minns i lasten, vi är uppräkning ordbok storlek för varje ord som vi stöter på. Så storleken är bara att tillbaka ordboken storlek. Och det är det. 

Så slutligen har vi lasta. Så lasta, kommer vi att använda en rekursiv funktion för att verkligen göra allt av arbetet åt oss. Så vår funktion kommer att kallas på avlastnings. Vad avlastnings göra? Vi ser här att avlastnings kommer att iterera över alla barnen på just denna nod. Och om barnet noden inte null, då vi kommer att lossa barnet oden. 

Så det här är du rekursivt lasta alla våra barn. När vi är säkra på att alla våra barn har lossats, då vi kan frigöra oss, så lasta av oss själva. Detta fungerar rekursivt lasta hela trie. Och när det är gjort, Vi kan bara return true. Lasta kan inte misslyckas. Vi bara frigöra saker. Så när vi är klara frigöra allt, return true. Och det är det. Mitt namn är Rob. Och detta var speller. 

[MUSIK SPELA]