[Muziek] 

ROB BOWDEN: Hi. Ik ben Rob. En laten we deze oplossing uit. Dus hier gaan we implementeren een algemene tabel. We zien dat de structuur knooppunt van onze tafel gaat uitzien. Dus het gaat om een ​​char woord hebben matrix van grootte LENGTE + 1. Vergeet niet de + 1, omdat de maximale woord in het woordenboek is 45 karakters. En dan gaan we een extra nodig karakter voor de backslash nul. 

En dan is onze hash in elke emmer gaat slaan een gelinkte lijst van knooppunten. We zijn niet lineair hier indringende doen. En dus om te linken naar het volgende element in de emmer, hebben we een struct knoop * volgende. OK. Dus dat is wat een knooppunt eruit ziet. 

Nu hier is de verklaring van onze hash. Het gaat om 16.834 bakken hebben. Maar dat aantal maakt niet echt uit. En tot slot, we gaan de globale variabele hash grootte, die gaat beginnen als nul. En het gaat bij te houden hoe houden veel woorden zijn in ons woordenboek. 

Dus laten we eens een kijkje nemen op belasting. Merk op dat de belasting, retourneert een bool. U return true als het succesvol was geladen, anders false. En het duurt een const char * woordenboek, die het woordenboek dat we willen openen. Dus dat is het eerste wat we gaan doen. 

We gaan fopen de woordenboek voor het lezen. En we zullen moeten maken zeker van dat het is gelukt. Dus als het terug NULL, dan hebben we niet succes opent het woordenboek. En we moeten return false. Maar ervan uitgaande dat het met succes gedaan geopend, dan willen we lezen de woordenboek. Dus houd looping tot we enkele reden om uit te breken van deze lus, die we zullen zien. Dus houd looping. 

En nu gaan we naar malloc een enkel knooppunt. En natuurlijk moeten we aan de lucht probeert u het opnieuw. Dus als mallocing niet gelukt, dan we willen elke node die wij lossen gebeurd met malloc voor, sluit de woordenboek en return false. Maar negeren dat, uitgaande we gelukt, dan willen we fscanf gebruiken om een ​​enkel woord lezen uit onze woordenboek in onze knooppunt. Dus onthoud dat entry> woord is de char woord buffer van omvang lenghth + 1 dat we gaan om het woord op te slaan in 

Dus fscanf gaat terug 1, zolang zoals het was in staat om succesvol lees een woord uit het bestand. Als een van beide een fout gebeurt, of we bereiken het einde van het bestand, zal niet terugkeren 1. In dat geval niet terugkeert 1, we eindelijk te doorbreken dit terwijl lus. Zo zien we dat als we succes hebben lees een woord in entry> woord, dan gaan we dat woord met behulp van onze hash-functie. 

Laten we eens een kijkje nemen op de hash-functie. Zodat je niet echt nodig hebt om dit te begrijpen. En eigenlijk zijn we net trok deze hash functioneren van het internet. Het enige wat je moet erkennen is dat dit duurt een const char * woord. Dus het duurt een string als input, en retourneren van een unsigned int als output. Dus dat is al een hash-functie is, is het neemt in een input en geeft u een index in de hash. 

Merk op dat we moding door NUM_BUCKETS, zodat de waarde terug eigenlijk is een index in de hash en niet geïndexeerd dan de grenzen van de array. Zo bepaalde functie, we gaan aan het woord die we lezen hash de woordenboek. En dan gaan we gebruiken dat hash te voegen de binnenkomst in de hash. 

Nu hash hash is de huidige gekoppelde lijst in de tabel. En het is heel goed mogelijk dat het gewoon NULL. We willen onze toegang aan de voegen begin van deze gelinkte lijst. En dus gaan we onze huidige hebben toegangspoort tot wat de hash nog wijst. En dan gaan we op te slaan, in de hash op de hash, de huidige vermelding. Dus deze twee lijnen met succes te voegen de ingang aan het begin van de gelinkte lijst op die index in de hash. 

Zodra we klaar zijn met dat, we weten dat vonden we een ander woord in de woordenboek, en we verhogen opnieuw. Dus houden we dat doen totdat fscanf teruggegaan iets non-1 bij welk punt herinneren dat we moeten gratis toegang. Dus hier malloced we een vermelding. En we hebben geprobeerd om iets te lezen uit het woordenboek. En we hebben niet met succes gelezen iets uit het woordenboek, in dat geval moeten we de toegang gratis dat we nooit daadwerkelijk in de zetten hash, en uiteindelijk breken. 

Zodra we breken we moeten zien, nou ja, hebben we breken omdat er was een fout bij het lezen van het dossier? Of hebben we breken omdat we aan het einde van het bestand? Als er een fout, waarna we willen valse terugkeren. Omdat de lading niet gelukt. En in het proces dat we willen lossen alle woorden die we lezen in, en sluit het woordenboek bestand. 

Ervan uitgaande dat we niet slagen, dan kunnen we gewoon nog steeds nodig om het woordenboek te sluiten bestand, en tenslotte return true omdat we met succes geladen het woordenboek. En dat is het voor de belasting. Dus nu controleren, gegeven een geladen hash, gaat er zo uitzien. Dus check, het een bool terug, dat is zal aangeven of de verstreken in char * woord, of de doorgegeven in string is in ons woordenboek. Dus als het in het woordenboek als het in onze hash, we zullen terugkeren waar. En als het niet, we zullen valse terugkeren. 

Gezien deze gepasseerd in woord, we zijn gaan naar het woord hash. Nu een belangrijk ding te herkennen is dat in de belasting we wisten dat alle woorden we gaan naar kleine letters. Maar hier zijn we niet zo zeker van. Als we een kijkje nemen op onze hash-functie, onze hash-functie eigenlijk lager behuizing elk karakter van het woord. Dus ongeacht de kapitalisatie van woord, onze hash-functie is de terugkeer dezelfde index om welke activering, zoals zou terug voor een volledig kleine versie van het woord. Alright. Dat is onze index moet in de hash voor dit woord. 

Nu is deze lus gaat itereren over de gelinkte lijst dat was die index. Zo merken we initialiseren binnenkomst te wijzen die index. We gaan blijven terwijl entry! = NULL. En vergeet niet dat het bijwerken van de aanwijzer in onze gelinkte lijst entry = entry> volgende. Dus hebben onze huidige toegangspoort tot het volgende item in de gelinkte lijst. 

Dus voor elk item in de gelinkte lijst, we gaan strcasecmp gebruiken. Het is niet StrComp. Want nogmaals, we willen dingen doen geval ongevoelig. We gebruiken dus strcasecmp te vergelijken woord, dat door dit functie tegen het woord dat in deze ingang. Als deze nul terugkeert, dat betekent dat er een wedstrijd, waarbij we willen return true. Wij hebben met succes vonden de woord in onze hash. 

Als er geen match, dan zijn we gaat lus opnieuw en kijk naar de volgende item. En we gaan terwijl er verder looping zijn items in deze gelinkte lijst. Wat gebeurt er als we breken uit deze lus? Dat betekent dat we een ingang niet vinden dat paste dit woord, in welk geval we return false aangeven dat onze hashtable heeft dit woord niet bevatten. En dat is een cheque. 

Dus laten we eens een kijkje nemen op grootte. Nu grootte gaat vrij eenvoudig te zijn. Sinds herinneren in de belasting, voor elk woord we vonden, we schuiven een globale variabele grootte hash. Zodat de grootte functie wordt gewoon om globale variabele terug te keren. En dat is het. 

Nu eindelijk, moeten we lossen het woordenboek als alles klaar is. Dus hoe gaan we dat doen? Hier zijn we looping boven alle emmers van onze tafel. Dus er zijn NUM_BUCKETS emmers. En voor elke gekoppelde lijst in onze hash, gaan we lus over het geheel van de gekoppelde lijst, vrijmaken van elk element. 

Nu moeten we voorzichtig zijn. Dus hier hebben we een tijdelijke variabele dat is het opslaan van de pointer naar de volgende element in de gelinkte lijst. En dan gaan we gratis het huidige element. We moeten zorgen dat we dit doen omdat we kan niet alleen gratis de huidige element en dan proberen om naar de volgende wijzer, want zodra we het hebben bevrijd, het geheugen wordt ongeldig. 

Dus moeten we houden rond een pointer naar het volgende element, dan kunnen we gratis de huidige element, en dan kunnen we updaten het actuele element wijzen het volgende element. We zullen lus terwijl er elementen in deze gelinkte lijst. We zullen dat doen voor alle gekoppelde lijsten in de hash. En als we klaar zijn met dat, we hebben volledig gelost de hash, en we klaar zijn. Dus het is onmogelijk voor lossen ooit return false. En als we klaar zijn, we gewoon terug waar. 

Laten we deze oplossing proberen. Dus laten we eens kijken naar wat onze struct knoop eruit zal zien. Hier zien we dat we gaan een bool hebben woord en een struct knoop * kinderen beugel alfabet. Dus het eerste wat je zou kunnen zijn afvragen, waarom is ALFABET ed gedefinieerd als 27? Nou, vergeet niet dat we gaan nodig hebben te hanteren van de apostrof. Dus dat gaat iets van een speciaal geval in dit programma. 

Nu herinneren hoe een Trie eigenlijk werkt. Laten we zeggen dat we het indexeren van het woord "Katten." Dan wordt uit de wortel van Trie, we gaan kijken naar de kinderen array, en we gaan kijken naar de index die overeenkomt met de letter C. Dus die zullen worden geïndexeerd 2. Zo bepaalde, dat wil geven ons een nieuw knooppunt. En dan zullen we werken vanuit dat knooppunt. 

Zo bepaalde knooppunt, we zijn weer gaan kijken naar de kinderen array. En we gaan kijken naar index nul overeenkomen met de A cat. Dus dan gaan we naar dat knooppunt, en gezien het feit dat knooppunt we gaan om te kijken naar het einde is het een overeen T. En de overgang naar dat knooppunt, Tenslotte hebben we volledig gekeken door ons woord "cat". En nu bool woord moet geven of dit gegeven woord is eigenlijk een woord. 

Dus waarom doen we dat speciaal geval nodig? Tja, wat van het woord "catastrofe" in ons woordenboek, maar de woord "cat" is niet? Zo en op zoek om te zien of het woord "kat" wordt in ons woordenboek, we zijn gaan om succesvol te kijken door de indices C-A-T in regio node. Maar dat is alleen omdat catastrofe gebeurd met knooppunten op de weg te creëren van C-A-T, helemaal naar het einde van het woord. Dus bool woord wordt gebruikt om aan te geven of deze bijzondere locatie eigenlijk wijst op een woord. 

Oke. Dus nu dat we weten wat het trie is eruit komt te zien, laten we eens kijken naar de laden functie. Dus belasting gaat een bool terug voor de vraag of we met succes of tevergeefs geladen het woordenboek. En dit gaat om het woordenboek te zijn dat we willen laden. 

Dus eerste wat we doen is geopend up die woordenboek voor het lezen. En we moeten ervoor zorgen we niet falen. Als het woordenboek niet succesvol geopend is, zal het terug null, in welk geval we gaan return false. Maar ervan uitgaande dat het met succes geopend, dan kunnen we echt gelezen door het woordenboek. 

Dus eerste wat we gaan wilt doen is hebben we dit globale variabele root. Nu wortel gaat om een ​​knooppunt te zijn *. Het is de top van onze trie dat we zal worden itereren door. Dus het eerste wat we gaan te willen doen is toe te wijzen geheugen voor onze root. Merk op dat we met behulp van de calloc functie, die is in principe hetzelfde als malloc-functie, behalve dat het gegarandeerd iets dat terug volledig op nul gezet. Dus als we gebruikt malloc, zouden we moeten gaan door alle van de wijzers in onze knooppunt, en zorg ervoor dat ze zijn allemaal null. Dus calloc doet dat voor ons. 

Nu net als malloc, moeten we ervoor ervoor dat de toewijzing was eigenlijk succesvol. Als dit terug null, dan kunnen we moeten woordenboek sluiten of bestand en return false. Dus de veronderstelling dat de toewijzing werd succesvol is, gaan we een knooppunt te gebruiken * cursor naar doorloopt onze trie. Dus onze roots nooit veranderen, maar we gaan cursor om daadwerkelijk te gaan van knooppunt naar knooppunt. 

Dus in deze lus we lezen door het woordenboek bestand. En we gebruiken fgetc. Fgetc gaat om een ​​enkel te grijpen karakter van het bestand. We gaan blijven grijpen personages terwijl we niet bereikt de einde van het bestand. 

Er zijn twee gevallen moeten we hanteren. De eerste, indien het teken was niet een nieuwe regel. Dus we weten of het een nieuwe regel, dan we staan ​​op het punt om over te gaan naar een nieuw woord. Maar ervan uitgaande dat het was niet een nieuwe regel, dan hier willen we achterhalen van de index gaan we index in in de kinderen array we gekeken naar eerder. 

Dus, zoals ik al eerder zei, we moeten speciaal geval de apostrof. Merken we gebruiken het ternaire operator hier. Dus we gaan om dit te lezen als, indien het karakter lezen we in was een apostrof, dan gaan we in te stellen index = "alphabet" -1, die zal als index 26. 

Anders, als het niet een apostrof, er we gaan naar de index-set gelijk aan c - een. Dus vergeet niet terug van eerder p-sets, c - een gaat ons het geven alfabetische positie van C. Dus als C de letter A, zal dit geven ons index nul. Voor de letter B, zal het geven ons de index 1, en ga zo maar door. 

Dus dit geeft ons de index in de kinderen array die we willen. Nu, als deze index is momenteel null in kinderen, dat betekent dat een knooppunt nog niet bestaat van dat pad. Dus we moeten wijzen een knooppunt voor dat pad. Dat is wat we hier gaan doen. 

Dus we gaan weer gebruik maken van de calloc functie, zodat we niet hoeven te nul uit alle pointers. En we weer moeten controleren dat calloc faalde niet. Als calloc deed mislukken, dan moeten we om alles uit te laden, sluit onze woordenboek, en return false. Dus de veronderstelling dat het niet mislukt, dan dit zal een nieuw kind te maken voor ons. En dan gaan we naar dat kind. Onze cursor zal herhalen neer aan dat kind. 

Nu als dit niet nul te beginnen met, vervolgens de cursor kan slechts herhalen neer dat kind zonder daadwerkelijk iets te hoeven toe te wijzen. Dit is het geval wanneer we eerst gebeurd wijzen het woord "kat." En dat betekent dat wanneer we naar toe te wijzen "Catastrofe," we hoeven niet te maken knooppunten C-A-T weer. Ze bestaan ​​reeds. 

Wat is dit anders? Dit is de toestand waarin c was backslash n, waarbij c was een nieuwe regel. Dit betekent dat we met succes hebben voltooide een woord. Nu, wat willen we doen als we een woord met succes afgerond? We gaan dit woord veld gebruiken binnenkant van ons struct knooppunt. We willen stellen dat dit waar. Dat geeft aan dat knooppunt wijst op een succesvolle woord, een echte woord. 

Stellen nu dat dit waar. We willen onze cursor terug te zetten naar punt aan het begin van de Trie weer. En tenslotte, verhogen ons woordenboek grootte, omdat we vonden een ander werk. Dus gaan we dat blijven doen, lezen in het teken voor teken, de aanleg van nieuwe knooppunten in onze trie en voor elk woord in de woordenlijst, tot we eindelijk bereiken C! = EOF, waarin geval breken we uit het bestand. 

Nu zijn er twee gevallen onder die wij EOF zou hebben geraakt. De eerste is of er een fout het lezen van het bestand. Dus als er een fout, we moeten de typische doen. Lossen alles, dicht het bestand, return false. Ervan uitgaande dat er was geen fout, dat betekent gewoon dat we eigenlijk raakte eind het bestand, waarbij sluiten we de bestand en return true omdat we succes geladen woordenboek in onze trie. 

Dus nu laten we eens kijken check. Kijkend naar de check-functie, zien we Het inchecken gaat een bool terug. Het geeft true als dit woord dat het wordt doorgegeven is in onze trie. Het geeft anders false. Dus hoe ga je bepalen of dit woord is in onze trie? 

We zien hier dat, net als vroeger, we gaan cursor gebruiken om te schakelen via onze trie. Nu hier gaan we herhalen meer dan onze hele woord. Dus itereren over het woord dat we zijn verleden, we gaan bepalen index in de array kinderen komt overeen met woord beugel I. Dus dit gaat precies hetzelfde uitzien als belasting, waar als woord [i] is een apostrof, dan willen we naar index "alphabet" gebruiken - 1. Omdat we vastgesteld dat is waar we heen gaan om op te slaan apostrof. 

Anders gaan we twee onderste woord te gebruiken beugel I. Dus onthoud dat woord kan hebben willekeurige kapitalisatie. En dus we willen ervoor zorgen dat we met behulp van een kleine versie van de dingen. En dan aftrekken van dat 'a' om een ​​keer weer geven ons de alfabetische positie van dat personage. Dus dat gaat onze index zijn in de kinderen array. 

En nu als die index in de kinderen array is null, dat betekent dat we kan niet langer blijven itereren beneden onze trie. Als dat het geval is, dit woord kan niet eventueel in onze trie. Want als het ware, dat zou betekenen dat er zou een pad zijn neer aan dat woord. En je zou nooit null tegenkomen. Dus ontmoeten null, we return false. Het woord niet in het woordenboek. Als het niet null is, dan zijn we zal itereren gaan. 

Dus we gaan er cursor te wijzen dat specifieke knooppunt op die index. We houden dat in heel het doen het hele woord, in de veronderstelling we nooit geraakt null. Dat betekent dat we in staat waren om door te komen het hele woord en vind een knooppunt in onze poging. Maar we zijn nog niet klaar. 

We willen niet alleen return true. We willen cursor> woord terug. Ondertussen weer herinner, is "cat" is niet in ons woordenboek, en "catastrofe" wordt, dan zullen we met succes krijgen we door het woord "cat". Maar cursor woord zal vals en niet waar zijn. Dus keren we cursor woord om aan te geven of dit knooppunt is eigenlijk een woord. En dat is het voor controle. 

Dus laten we eens kijken grootte. Dus maat gaat vrij gemakkelijk te zijn sinds, gedenken in belasting, we zijn incrementing woordenboek maat voor elk woord dat we tegenkomen. Dus maat is gewoon gaan terug woordenboekgrootte. En dat is het. 

Dus slotte hebben uitladen. Dus lossen, gaan we gebruik maken van een recursieve functie om daadwerkelijk alles te doen van het werk voor ons. Dus onze functie gaat worden opgeroepen losser. Wat is losser gaan doen? We zien hier dat losser gaat itereren over alle kinderen op dit knooppunt. En als het kind knooppunt is niet null, dan gaan we naar lossen de onderliggende node. 

Dus dit is je recursief lossen al onze kinderen. Zodra we zeker weten dat al onze kinderen zijn gelost, dan kunnen we kunnen onszelf bevrijden, zodat onszelf lossen. Dit recursief werken lossen de hele trie. En dan zodra dat is gedaan, kunnen we gewoon return true. Lossen kan niet falen. We zijn net bevrijden dingen. Dus zodra we klaar bevrijden alles, return true. En dat is het. Mijn naam is Rob. En dit was speller. 

[Muziek]