>> LUIDSPREKER 1: Laten we deze oplossing proberen.
Dus laten we eens kijken naar wat onze Struct knooppunt eruit zal zien.
Hier zien we we gaan een Bool Word en een Struct knooppunt ster
Kinderen beugel alfabet.
Dus eerste wat je misschien af, waarom is alfabet hash gedefinieerd als 27?
Nou, vergeet niet dat we gaan nodig hebben te hanteren van de apostrof, dus
dat gaat wat te zijn van een bijzondere geval in dit programma.
>> OK, nu, herinner me hoe een Trie eigenlijk werkt.
Laten we zeggen dat we het indexeren van het woord katten, vervolgens uit de wortel van onze Trie,
we gaan kijken naar de kinderen array, en we gaan kijken naar de
index die overeenkomt met de letter C. Dat zou indexeren twee.
Zo bepaalde, zal dat ons een nieuw knooppunt, en dan gaan 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
te kijken naar de index die overeenkomt T. En de overgang naar dat knooppunt,
Tenslotte hebben we volledig gekeken door ons woord kat, en nu Bool
Woord wordt verondersteld te geven of dit gegeven woord is eigenlijk een woord.
>> Dus waarom doen we dat speciaal geval nodig?
Nou, wat als het woord catastrofe in ons woordenboek, maar
het woord kat is niet?
Dus op zoek om te zien of het woord kat in ons woordenboek, gaan we
succes kijken via de indices C-A-T en bereiken een knooppunt, maar dat is
alleen omdat ramp gebeurd met creëren knooppunten op de weg van C-A-T Alle
tot aan het einde van het woord.
Dus Bool Word wordt gebruikt aangeven of deze bijzondere locatie daadwerkelijk
duidt op een woord.
>> Oke, dus nu dat we weten wat een Trie gaat uitzien, laten we eens kijken
op de Load functie.
Dus Load gaat een Bool terug voor de vraag of we met succes of
tevergeefs geladen woordenboek en dit gaat om het woordenboek te zijn
dat we willen laden.
Dus eerste wat we gaan doen is het openen up die woordenboek voor het lezen.
We moeten ervoor zorgen dat we niet falen, dus als het woordenboek niet
succesvol geopend is, zal het terug Nee, in dat geval gaan we
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 een knooppunt ster.
Het is de top van onze Trie dat we zal worden itereren door.
Dus eerste wat we gaan willen doen is geheugen toewijzen 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 is eigenlijk
succesvol.
Als dit terug null, dan kunnen we moeten ons woordenboek sluiten
file en terug False.
Dus uitgaande van de toewijzing werd succesvol is, gaan we een knooppunt gebruiken
ster Cursor te herhalen via onze Trie.
Dus onze wortel gaat nooit veranderen, maar we gaan Cursor gebruiken om
daadwerkelijk te gaan van knooppunt naar knooppunt.
>> Oke, dus in dit For-lus, we zijn lezen door het woordenboek bestand,
en we gebruiken bij fgetc.
Dus fgetc gaat een pak karakter van het bestand.
We gaan blijven grijpen personages terwijl we niet bereikt de
einde van het bestand, dus er zijn twee gevallen moeten we hanteren.
De eerste, indien het teken niet een nieuwe lijn, dus we weten of het een nieuwe
lijn, dan zijn we op het punt om 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 the Children array die
we gekeken naar eerder.
>> Dus zoals ik al eerder zei, we moeten speciaal geval de apostrof.
Let op dat we met behulp van de ternaire operator hier, dus we gaan om te lezen
dit alsof het personage lezen we in was een apostrof, dan gaan we naar
ingesteld index gelijk aan alfabet minus 1, die de index 26 is.
Anders, als het niet een apostrof, dan gaan we naar de index-set
c gelijk aan minus een.
Dus vergeet niet terug van eerdere p sets, c minus een gaat ons het geven
alfabetische positie van c, dus als c is de letter A, dit wil
geven ons index nul.
Voor de letter B, zou 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 the Children array, dat betekent dat
een knooppunt nog niet bestaat uit dat pad, dus we moeten kennen een
knooppunt voor dat pad.
Dat is wat we hier doen.
Dus we gaan, nogmaals, gebruik de calloc functie zodat we niet hoeven
tot nul uit alle van de pointers, en wij, weer, moet dat calloc controleren
faalde niet.
Als calloc deed mislukken, dan moeten we om alles uit te laden, sluit onze
woordenboek, en terug False.
>> Dus de veronderstelling dat het niet mislukt, dan dit zal een nieuw kind voor ons te creëren,
en dan gaan we naar dat kind.
Onze cursor zal herhalen neer aan dat kind.
Nu, als dit niet nul te beginnen, 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 om het woord kat toewijzen en
dat betekent dat wanneer we naar toe te wijzen catastrofe, hoeven we niet te maken
knooppunten C-A-T weer.
Ze bestaan ​​reeds.
>> OK, dus 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 instellen die op True, zodat geeft aan dat knooppunt aangeeft een
succesvolle woord een echte woord.
Nu, stel dat op True.
We willen onze cursor terug te zetten naar punt aan het begin van de Trie weer.
En tenslotte, verhogen ons woordenboek maat omdat we vonden een ander woord.
>> Oke, dus we gaan blijven doen dat het lezen van karakter door
karakter, de aanleg van nieuwe knooppunten in onze Trie en voor elk woord in de
woordenboek, tot we uiteindelijk c bereiken gelijk EOF, in welk geval we breken
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, moeten we de typische doen lossen alles, sluit u 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 file en terug True aangezien we
met succes geladen het woordenboek in onze Trie.
>> Oke, dus nu laten we check out Check.
Kijkend naar de Check-functie, zien we Controleer dat gaat een Bool terugkeren.
Het geeft Waar als dit woord dat het wordt doorgegeven is in onze Trie.
Het geeft Onwaar anders.
>> Dus hoe gaan we om te 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, we gaan herhalen meer dan onze hele woord.
Dus itereren over het woord dat we zijn gepasseerd, gaan we bepalen de
index in de Kinderen array die komt overeen met woord beugel i.
Dus dit gaat precies hetzelfde uitzien als Belasting, waar als woord beugel i een
apostrof, dan willen we index te gebruiken alfabet minus 1 omdat we bepaald
dat is waar we heen gaan apostrofs slaan.
>> Anders gaan we gebruiken tolower woord beugel i.
Dus onthoud dat woord kan hebben willekeurige kapitalisatie, en dus hebben we
willen ervoor zorgen dat we gebruiken een kleine versie van de dingen.
En dan aftrekken van die kleine letters a. opnieuw ons het
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
werden, dat zou betekenen dat er zou een zijn pad naar dat woord, en je zou
nooit null tegenkomen.
Dus ontmoeten null, we terugkeren False.
Het woord niet in het woordenboek.
Als het niet null is, dan gaan we naar blijven itereren, dus we gaan
onze cursor updaten naar wijzen dat bepaald knooppunt op die index.
>> Dus houden we dat overal doen het hele woord.
Ervan uitgaande dat we nooit geraakt null, dat betekent we waren in staat om door het hele te krijgen
wereld en het vinden van een knooppunt in onze Trie, maar we zijn nog niet klaar.
We willen niet gewoon terug True.
We willen cursor fout woord terug sinds, herinner nogmaals, als kat is niet
in ons woordenboek en catastrofe is, dan zullen we met succes doorheen
het woord kat, maar cursor woord Valse en niet True zal 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 Grootte gaat vrij gemakkelijk te zijn sinds, gedenken in Load, we zijn
incrementing woordenboek maat voor elk woord dat we tegenkomen.
Dus maat is gewoon om terug te keren woordenboekgrootte, en dat is het.
>> Oke, ten slotte, hebben wij Unload.
Dus Unload, gaan we gebruik maken van een recursieve functie om daadwerkelijk alles te doen
van het werk voor ons, zodat onze functie is gaan heten Unloader.
Wat is Unloader gaan doen?
We zien hier dat Unloader gaat itereren over alle kinderen op
dit knooppunt en het kind knooppunt is niet nul, dan gaan we naar
lossen de onderliggende node.
>> Dus dit gaat recursief lossen al onze kinderen.
Zodra we zeker weten dat al onze kinderen zijn gelost, dan kunnen we
kunnen onszelf bevrijden, zo lossen onszelf.
Dus dit zal recursief lossen van de hele Trie, en dan een keer is dat
gedaan, kunnen we gewoon terug 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 [onverstaanbaar].