>> ZAMYLA CHAN: Let's make een spellingscontrole.
Als je speller.c opent, dan zie je dat de meeste functionaliteit
het controleren van een tekst bestand tegen een woordenboek is al voor u gemaakt.
. / Speller, passeren in een woordenboek tekst bestand en dan nog een tekstbestand,
zal dat tekstbestand controleren tegen het woordenboek.
>> Nu zal woordenboek tekstbestanden bevatten geldige woorden, een per regel.
Dan zal speller.c Load bellen op het woordenboek tekstbestand.
Het zal noemen een functie genaamd Controle op elk woord in de ingevoerde tekst bestand,
het afdrukken van alle verkeerd gespelde woorden.
>> Speller.c zal ook Grootte bellen om bepalen het aantal woorden in
woordenboek en bel Unload om geheugen vrij te maken.
speller.c zal ook bijhouden hoe houden veel tijd wordt gebruikt voor het uitvoeren van deze
processen, maar we zullen krijgen om dat later.
>> Dus wat moeten we doen?
We moeten in dictionary.c te vullen.
In dictionary.c, hebben we de helper Load-functie, die de geladen
woordenboek.
De functie Controle, die controleert of een bepaald woord in het woordenboek.
De functie Size geeft het aantal van woorden in het woordenboek.
En tot slot, we hebben ontlasten, die bevrijdt het woordenboek uit het geheugen.
>> Dus laten we eerst eens aan te pakken Load.
Voor elk woord in het woordenboek tekst bestand, zal de belasting die woorden op te slaan in
het woordenboek datastructuur van uw keuze, ofwel een
hash table of een Trie.
Ik ga over zowel in deze lopen door.
>> Laten we het eerst hebben over hash tables.
Zeggen dat je had 10 biljartballen en je wilde ze op te slaan.
Je zou ze allemaal in een emmer, en als je een specifiek nodig
genummerde bal, zou je een te nemen uit de emmer op een moment
op zoek naar die bal.
En met slechts 10 ballen, moet u in staat om je bal te vinden in een redelijke
tijd.
>> Maar wat als je 20 ballen gehad?
Het is misschien een beetje langer nu nemen.
Hoe zit het met 100?
1000?
Nu, zou het veel gemakkelijker zijn als je had meerdere emmers.
Misschien een emmer voor ballen genummerd nul tot en met negen, een andere emmer voor
genummerd van 10 tot en met 19, enzovoort.
>> Als u nu nodig om te zoeken naar specifieke bal, kon je automatisch
gaan naar een specifieke emmer en zoeken door die emmer.
En als elke emmer heeft ongeveer 10 ballen, dan kun je gemakkelijk zoeken
doorheen.
>> Nu, aangezien we te maken hebben met woordenboeken, een enkele emmer voor
alle woorden in het woordenboek zal waarschijnlijk veel te weinig emmers.
Dus laten we eens een kijkje nemen op hash tables.
>> Zie het als een array van emmers.
En in dit geval, de emmers zijn onze gelinkte lijsten.
En we zullen al onze woorden te verdelen onder deze meerdere gekoppelde lijsten in
een georganiseerde manier met behulp van een hash-functie, die ons zal vertellen welke
emmer een bepaalde sleutel, een gegeven woord, behoort.
>> Laten we vertegenwoordigen dit schematisch.
De blauwe dozen hier bevatten waarden en rode dozen wijzen op een andere waarde
pointer paar.
We zullen deze paren knopen noemen.
Nu, elke emmer, zoals ik al zei eerder, is een gelinkte lijst.
In gekoppelde lijsten, elk knooppunt een waarde alsmede een pointer naar de
volgende waarde.
>> Nu, het omgaan met gelinkte lijsten, het is erg belangrijk dat u
verliest geen koppelingen.
En een ander feit om te onthouden is dat de laatste knoop, als het niet wijzen op
ander knooppunt, wijst op null.
>> Dus hoe kunnen we deze vertegenwoordigen in C?
We definiëren hier onze structuur.
En de waarde is in dit geval een char array met lengte.
Lengte plus 1, waarbij de lengte maximale lengte van een woord, plus 1 voor
de null-terminator.
En dan hebben we een pointer naar ander knooppunt genaamd Next.
>> Dus laten we een klein gelinkte lijst.
Ten eerste, zult u wilt uw knooppunt malloc, die ruimte in het geheugen van de
grootte van uw knooppunt type.
En maak een ander knooppunt, weer mallocing.
>> Nu als je wilt om een ​​waarde toe te kennen aan een woord, dan zouden we kunnen zeggen node1 pijl
woord is gelijk aan "Hallo." Deze pijl operator dereferences de aanwijzer en
toegang tot variabelen van de struct's.
Op deze manier hoeven we niet te gebruiken beide de stip en de ster operator.
>> Dus dan heb ik clustnode2 pijl woord gelijk "Wereld." En daar de waarden
bevolkt in mijn knooppunten.
Om de links te maken, zal ik pas in node1 pijl naast, de toegang die knoop ster,
dat knooppunt wijzer, gelijk clustnode2, wijzend node1 te clustnode2 twee.
En daar hebben we een gelinkte lijst.
>> Dus dat was slechts een gelinkte lijst, maar een hash table is een hele reeks van
gelinkte lijsten.
Nou, zullen we dezelfde knoop hebben structuur als voorheen.
Maar als we wilden een echte hash table, dan kunnen we gewoon een knooppunt aanwijzer
serie hier.
Bijvoorbeeld, maat 500.
>> Nu mededeling, er gaat een handel zijn off tussen de grootte van uw
hash table en de grootte van uw gelinkte lijsten.
Als je een echt hoge aantal emmers, verbeelden hoeven terug te draaien
en weer in een lijn vind je emmer.
Maar je wilt ook niet een klein aantal emmers, want dan zijn we terug naar
het oorspronkelijke probleem van hoe het hebben te veel ballen in onze emmer.
>> OK, maar waar komt onze bal heen?
Nou, moeten we eerst een bal hebben, toch?
Dus laten we malloc een knooppunt voor elke nieuw woord dat we hebben.
knooppunt * new_node gelijken malloc (sizeof (node)).
>> Nu we deze structuur, we kan scannen in, met behulp van de functie
fscanf, een string uit ons bestand, indien dat is een woordenboek bestand, in
new_node pijl woord, waar new_node pijl woord is onze
bestemming van dat woord.
>> Vervolgens zullen we willen hash dat woord met behulp van een hash-functie.
Een hash-functie neemt een string en geeft een index.
In dit geval, de index moet minder dan het aantal
emmers die je hebt.
>> Nu, hash functies, als je probeert er een te vinden en creëren een van
uw eigen, vergeet niet dat ze moet deterministisch zijn.
Dit betekent dat dezelfde waarde moet toewijzen aan dezelfde emmer elke keer
dat je hash het.
>> Het is net zoiets als een bibliotheek.
Wanneer u een boek, op basis van de te nemen auteur, weet u welke plank het zou moeten
gaan, of het nu plaatsnummer een, twee of drie.
En dat boek zal altijd thuis op ofwel plank een, twee, of drie.
>> Dus, als new_node pijl woord heeft de Het woord van uw woordenboek, dan
hashing new_node pijl woord zal geven ons de index van de
emmer van de hash table.
En dan zullen we voegen dat in die specifieke gelinkte lijst wordt aangegeven door de
waarde van onze hash-functie terug te keren.
>> Laten we eens kijken naar een voorbeeld van inbrengen van een knooppunt in de
het begin van een gelinkte lijst.
Als hoofd is een knooppunt aanwijzer die aangeeft het begin van een gekoppelde
lijst en new_node geeft de nieuwe knooppunt dat u wilt in te gaan, maar
toewijzen van kop tot new_node zou verliezen de link naar de rest van de lijst.
Zodat we niet willen doen.
>> Integendeel, we willen ervoor zorgen dat dat we vasthouden aan elke
enkele knoop in ons programma.
Dus loopt new_node pijl naast gelijken hoofd en vervolgens hoofd gelijk new_node
zullen alle van de te behouden koppelingen en verliest geen.
>> Maar wat als u wilt dat uw lijst te zijn gesorteerd, omdat het hebben van een gesorteerde gekoppeld
lijst is misschien makkelijker voor zoek het later?
Nou, voor dat, moet u weten hoe gelinkte lijsten doorkruisen.
>> Om een ​​gekoppelde lijst doorkruisen, laten we een knooppunt pointer, een knooppunt *, om als
uw cursor, die aangeeft welke knooppunt je toch bezig bent, te beginnen
in het eerste element.
Looping tot cursor nul is, kunnen we voeren bepaalde processen en vervolgens
vooraf de cursor wanneer we het nodig gebruik cursor pijl waarde.
>> Vergeet niet, dit is hetzelfde als zeggende ster cursor, dereferentie
cursor, vervolgens met behulp van de operator punt waarde.
Dus bijwerken van de cursor door het toewijzen de cursor naar cursor pijl naast.
>> Zeggen u hebt vastgesteld dat D wordt in tussen C en E. De knoop voegen,
hebben de new_node D wijzen op de knooppunt E, dat is cursor naast.
En dan C, de cursor, kan wijs D. Op die manier behoudt u een lijst.
Wees voorzichtig niet om uw links te verliezen door het verplaatsen van de cursor naast D
meteen.
>> Oke.
Dus dat is hoe je nodes zouden kunnen opnemen, plaats ze in, belasting woorden in die
knooppunten, en plaats ze in uw hash table.
Dus laten we nu eens kijken naar pogingen.
>> In een Trie, zal elk knooppunt een bevatten reeks knooppunt pointers, een voor elke
letter in het alfabet plus een apostrof.
En elk element in de array zal wijzen naar een ander knooppunt.
Als dat knooppunt nul is, dan is dat brief is niet van plan om de volgende letter van zijn
een woord in een reeks, omdat elke woord geeft aan of het is de laatste
karakter van een woord of niet.
>> Laten we eens kijken naar een diagram.
Hopelijk zal een beetje duidelijker.
In dit diagram zien we dat alleen bepaalde letters en bepaalde substrings
worden vermeld uit.
Zo kunt u bepaalde paden te volgen, en al die paden zal u leiden tot
verschillende woorden.
>> Dus hoe kunnen we deze vertegenwoordigen in C?
Nou, elke knoop nu zal hebben een Booleaanse waarde die aangeeft of
dat knooppunt eind een bepaald woord of niet.
En dan zal het ook hebben een scala aan knooppunt pointers genaamd kinderen, en
er zullen zijn 27 van hen.
En vergeet niet, je zult ook willen bijhouden van uw eerste knooppunt.
We gaan die wortel noemen.
>> Dat is de structuur van een trie.
Hoe gaan we deze vertegenwoordigen als een woordenboek?
Nou, om woorden te laden in, voor elke woord uit het woordenboek, je gaat te willen
te doorlopen de Trie.
En elk element in de kinderen komt overeen met een andere letter.
>> Dus het controleren van de waarde bij kinderen index i, waarbij i de
specifieke index van de brief die je probeert in te voegen.
Nou, als het null, dan zult u wilt malloc een nieuw knooppunt en kinderen
ik wijzen op dat knooppunt.
>> Als het niet null, dan betekent dat dat dat bepaalde tak van dat gegeven
substring, al bestaat.
Dus dan zul je gewoon naar die nieuwe knooppunt en doorgaan.
Als je aan het eind van het woord dat je probeert te laden in de
woordenboek, dan kunt u instellen dat huidige knooppunt dat je op true.
>> Dus laten we eens kijken naar een voorbeeld van het plaatsen van het woord "vos" in onze
woordenboek.
Doen alsof we beginnen met een leeg woordenboek.
De eerste brief, F, zal worden gevestigd bij kinderen index vijf van de wortels
kinderen array.
Zodat voegen we binnen
>> De letter O wordt dan bij kinderen index 15, na dat F. En dan X
zal zelfs daaronder vertakking off van de kinderen van de O's.
En dan, omdat X is de laatste letter van het woord "vos", dan ga ik
kleur groen wanneer het is het einde van het woord.
In C, zou dat zijn instelling de Is Woord Boolean om de waarde true.
>> Nu, wat als het volgende woord dat je laden in het woord "foo"?
Nou, je hoeft niet meer hoeft te malloc ruimte voor F of voor O, omdat
deze bestaan.
Maar de laatste O in foo?
Die ene, dan moet je malloc.
Maak een nieuw knooppunt voor dat, het instellen Is het Woord Boolean true.
>> Dus laten we nu invoegen "hond." Hond zal beginnen met index drie wortels
kinderen, want D heeft niet nog niet gemaakt.
En we zullen een soortgelijk proces als volgt voor, het creëren van de substring hond,
Waar is de G is groen gekleurd, omdat dit is het einde van een woord.
>> Nu, wat als we willen invoegen "doen"?
Nou, dit is een substring van de hond, dus we hoeven niet meer te malloc.
Maar we moeten wel aangeven waar we hebben aan het einde van dat woord.
Dus de O zal groen gekleurd.
Voortzetting van dat proces voor elke woord in uw woordenboek, je hebt
geladen ze in in ofwel uw hash table of uw trie.
>> speller.c passeert in strings voor dictionary.c om ze te controleren.
Nu, de Check-functie moet opereren onder geval ongevoeligheid.
Dat betekent dat hoofdletters en kleine letters en een mix van beide
moeten alle gelijk om waar eventueel combinatie daarvan is in de
woordenboek.
U kunt ook aannemen dat strings alleen maar alfabetisch te bevatten
tekens of apostrof.
>> Dus laten we eens kijken hoe je zou controleren met een hash table structuur.
Nou, als het woord bestaat, dan is het kan worden gevonden in de hash tabel.
Dus dan kun je proberen te vinden dat woord in de desbetreffende bak.
>> Dus welke emmer zou dat woord in?
Nou, je zou het nummer, die index te krijgen van de bak, door hashing dat woord
en dan zoeken in die gelinkte lijst, doorkruist door de gehele
gelinkte lijst, met behulp van de String Vergelijk functie.
>> Als het uiteinde van de gekoppelde lijst bereikt, wat betekent dat uw cursor
bereikt null, dan is het woord niet te vinden in het woordenboek.
Het zal niet in een andere bak.
Dus hier, zou je zien hoe er misschien is een trade-off tussen het hebben van een van beide
gesorteerd gelinkte lijsten of ongesorteerde degenen.
Ofwel zal meer tijd in beslag nemen tijdens laden of meer tijd bij het inchecken.
>> Hoe zou u incheckt een trie-structuur?
We gaan naar beneden te reizen in trie.
Voor elke letter in het ingevoerde woord dat we het controleren, gaan we naar dat
overeenkomstige element in de kinderen.
>> Als dat element nul is, dan is dat middelen dat er geen substrings
met onze inbreng woord, dus het woord verkeerd is gespeld.
Als het niet null is, kunnen we overgaan tot de volgende letter van het woord dat we
controleren en blijven dit proces totdat we het einde bereiken
van de ingang woord.
En dan kunnen we controleren Als Is Woord waar is.
Zo ja, dan groot.
Het woord klopt.
Maar zo niet, ook al is dat substring bestaat in de trie, het woord is
verkeerd gespeld.
>> Wanneer de functie Grootte wordt genoemd, de grootte moet het aantal woorden terug die
zijn in uw gegeven woordenboek gegevensstructuur.
Dus als u een hash table, u kan ofwel gaan door elke
gelinkte lijst in elk emmer tellen van het aantal
woorden zijn er.
Als u gebruik maakt van een Trie, kunt u gaan door elke niet-null
pad in uw trie.
Of terwijl je het laden van het woordenboek in, misschien kun je bijhouden hoe
veel woorden je laden inch
>> Zodra speller.c eindigt het controleren van de tekstbestand tegen het woordenboek, dan
het is gedaan en dus het roept Unload, waar uw taak is om iets te bevrijden
dat u malloced.
Dus als je een hash tabel gebruiken, dan moet je moeten extra voorzichtig om te voorkomen dat zijn
geheugenlekken door niets te bevrijden voortijdig en het bedrijf op elke
single link voordat u gratis.
>> Dus voor elk element in de hash-tabel en voor elke knooppunt in de gekoppelde lijst
wil je bevrijden dat knooppunt.
Hoe ga je over het vrijmaken een gekoppelde lijst?
Uw knooppunt pointer cursor naar het instellen de kop, aan het begin van de
gelinkte lijst, dan terwijl je cursor is niet nul, kunt u een tijdelijke set
knooppunt pointer naar de cursor.
Vooruit dan de cursor.
En dan kun je bevrijden dat tijdelijke waarde, terwijl nog steeds vast aan
alles achteraf.
>> Wat als u een trie?
Dan is de beste manier om dit te doen te lossen vanaf het
beneden naar boven.
Door het reizen de laagst mogelijke knooppunt, kunt u alle pointers bevrijden
dat kinderen en dan backtrack omhoog vrijmaken alle elementen in alle
van de kinderen doeken, tot u raakt uw top root node.
Hier is waar Recursion zal van pas komen.
>> Om ervoor te zorgen dat je waarschijnlijk al bevrijd alles wat je hebt malloced,
u kunt Valgrind gebruiken.
Hardlopen Valgrind zal uw programma uit te voeren tellen hoeveel bytes van het geheugen
u gebruikt en ervoor te zorgen dat je hebt bevrijd ze allemaal, je vertellen
waar je zou kunnen hebben vergeten om gratis.
Zo lopen dat en zodra Valgrind vertelt u en geeft u het doorgaan, dan
u klaar bent met uitladen.
>> Nu, een paar tips voordat je gaat uit en beginnen met de uitvoering van uw
woordenboek.
Ik zou aanraden te gaan in een kleinere woordenboek als je probeert om te testen
dingen uit en debuggen met het BBP.
Het gebruik van speller is. / Speller, een optioneel woordenboek, en dan een tekst.
>> Standaard laadt in het grote woordenboek.
Dus je zou willen gaan in de kleine woordenboek, of misschien zelfs uw
eigen, het aanpassen van uw woordenboek en uw tekstbestand.
>> En dan eindelijk, Ik zou ook een pen en papier te nemen en te tekenen
dingen uit voor, tijdens en na je hebt al je code geschreven.
Maar zorg ervoor dat je hebt die aanwijzingen precies goed.
>> Ik wens u veel succes.
En als je eenmaal klaar bent, als je wilt aan het grote bord en uitdaging
zien hoe snel je programma wordt vergeleken met je klasgenoten ', dan nodigen ik
u te controleren dat uit.
>> Met dat u klaar bent met de speller Pset.
Mijn naam is Zamyla, en dit is CS50.