ZAMYLA CHAN: Kom ons maak 'n speltoetser. As jy speller.c oop te maak, dan sal jy sien dat die meeste van die funksies vir kontrolering van 'n teks lêer teen 'n woordeboek is reeds vir jou gemaak. . / Speller, verby in 'n woordeboek teks lêer en dan nog 'n teks lêer, sal seker maak dat die teks lêer teen die woordeboek. 

Nou sal woordeboek teks lêers bevat geldige woorde, een per lyn. Dan sal speller.c load noem op die woordeboek teks lêer. Dit sal noem 'n funksie genoem Check op elke woord in die teks ingevoer lêer, druk al verkeerd gespelde woorde. 

Speller.c sal ook 'n beroep Grootte bepaal die aantal woorde in woordeboek en noem los om vry te maak geheue. speller.c sal ook hou van hoe hou veel tyd word gebruik om uit te voer van hierdie prosesse, maar ons sal kry om dit later. 

So, wat moet ons doen? Ons moet in dictionary.c te vul. In dictionary.c, ons het die hulp funksie laai nie, wat laai die woordeboek. Die funksie Check, wat tjeks as 'n gegewe woord in die woordeboek. Die funksie Grootte gee die aantal woorde in die woordeboek. En uiteindelik het ons los, wat bevry die woordeboek uit die geheue. 

So die eerste, laat se pak laai. Vir elke woord in die woordeboek teks lêer, sal laai die woorde in die winkel die woordeboek data struktuur van jou keuse, óf 'n hash tafel of 'n Trie. Ek gaan oor beide in hierdie loop deur. 

Eerste laat ons praat oor hash tabelle. Sê jy het 10 biljart balle en jy wou om dit te stoor. Jy kan hulle almal sit in 'n emmer, en wanneer jy 'n spesifieke nodig genommerde bal, sal jy een neem uit die emmer op 'n tyd soek na die bal. En met net 10 balle, moet jy staat is om jou bal te kry in 'n redelike bedrag van die tyd. 

Maar wat as jy het 20 balle? Dit mag dalk 'n bietjie langer neem nou. Wat van 100? 1000? Nou, sou dit baie makliker wees as jy het verskeie emmers. Miskien een emmer vir balle genommer nul deur nege ander emmer vir balle genommer 10 deur 19, en so aan. 

Nou wanneer jy nodig het om te kyk vir 'n spesifieke bal, kan jy outomaties gaan na een spesifieke emmer en soek deur die emmer. En as elke emmer het ongeveer 10 balle, dan kan jy maklik soek deur dit. 

Nou, aangesien ons te doen het met woordeboeke, 'n enkele emmer vir al die woorde in die woordeboek sal waarskynlik hopeloos te min emmers. So kom ons neem 'n blik op hash tabelle. 

Dink aan dit as 'n verskeidenheid van emmers. En in hierdie geval, die emmers is ons verbind lyste. En ons sal versprei al ons woorde Onder hierdie verskeie gekoppel lyste in 'n georganiseerde manier met behulp van 'n hash funksie, wat sal ons vertel wat emmer 'n gegewe sleutel, 'n gegewe woord, behoort. 

Kom ons stel dit skematies voor. Die blou bokse hier bevat waardes en rooi bokse punt na die ander waarde wyser paar. Ons sal noem hierdie pare nodes. Nou, elke emmer, soos ek gesê het vroeër, is 'n geskakelde lys. In geskakelde lyste, elke knoop 'n waarde, sowel as 'n verwysing na die volgende waarde. 

Nou, die hantering van geskakelde lyste, dit is baie belangrik dat jy nie enige skakels verloor. En 'n ander feit om te onthou, is dat die laaste knoop, indien dit nie verwys na 'n ander knoop, wys na nul. 

So hoe kan ons stel dit in C? Ons definieer ons struct hier. En die waarde in hierdie geval is 'n kar verskeidenheid van lengte. Lengte plus 1, waar die lengte is die maksimum lengte van 'n woord, plus 1 vir die nul terminator. En dan het ons 'n verwysing na 'n ander knoop genoem Volgende. 

So laat ons 'n klein gekoppel lys. Eerstens, sal jy jou knoop te malloc, wat ruimte skep in die geheue van die grootte van jou node tipe. En 'n ander knoop, weer mallocing. 

Nou as jy 'n waarde aan 'n te ken woord, dan kan ons Node 1 pyl sê woord gelyk "Hello." Hierdie pyl operateur dereferences die wyser en toegang tot die struct se veranderlikes. Op hierdie manier, ons het nie beide te gebruik die kol en die ster-operateur. 

So dan het ek node2 pyl woord gelyk "Wêreld." En daar, is die waardes bevolk in my knope. Die skakels te maak, sal ek in Node 1 slaag pyltjie langs, toegang tot hierdie knoop ster, dat node wyser, gelyk node2, wys Node 1 tot node2 twee. En daar het ons 'n geskakelde lys. 

So dit was net een gekoppel lys nie, maar 'n gemors tabel is 'n hele verskeidenheid van geskakelde lyste. Wel, ons sal dieselfde knoop het struktuur voor. Maar as ons wou 'n werklike hash tafel, dan kan ons net 'n knoop wyser skikking hier. Byvoorbeeld, grootte 500. 

Nou kennisgewing, daar gaan 'n handels-wees off tussen die grootte van jou hash tafel en die grootte van jou geskakelde lyste. As jy het 'n baie hoë aantal emmers, verbeel om terug te hardloop en weer in 'n lyn te vind jou emmer. Maar jy wil ook nie 'n klein aantal emmers, want dan is ons terug na die oorspronklike probleem van hoe om te veel balle in ons emmer. 

OK, maar waar kom ons bal gaan? Wel, moet ons eers 'n bal, reg? So laat malloc 'n knoop vir elke nuwe woord wat ons het. knoop * new_node gelykes malloc (sizeof (nodig)). 

Nou dat ons hierdie struktuur, ons kan in scan, met behulp van die funksie fscanf, 'n string van ons lêer, as dit is 'n woordeboek leer, in new_node pyl woord, waar new_node pyl woord is ons bestemming van die woord. 

Volgende, sal ons dit wil hash woord deur 'n hash funksie. 'N hash funksie neem 'n string en gee 'n indeks. In hierdie geval, die indeks het tot minder as die aantal emmers wat jy het. 

Nou, hash funksies, wanneer jy probeer om een ​​te vind en die skep van een van jou eie, onthou dat hulle het tot deterministiese wees. Dit beteken dat dieselfde waarde moet kaart na die dieselfde emmer elke keer dat jy hash dit. 

Dit is soort van soos 'n biblioteek. Wanneer jy 'n boek, wat gebaseer is op die skrywer, jy weet wat dit moet rak gaan, of dit nou raknommer een, twee, of drie. En die boek sal altyd behoort op óf rak een, twee, of drie. 

Dus, as new_node pyl woord het die woord uit jou woordeboek, dan hashing new_node pyl Woord gee ons die indeks van die emmer van die hash tafel. En dan sal ons voeg dat in daardie spesifieke gekoppel lys aangedui deur die terugkeer waarde van ons hash funksie. 

Kom ons kyk na 'n voorbeeld van invoeging van 'n knoop in die begin van 'n geskakelde lys. As hoof is 'n knoop wyser wat aandui die begin van 'n gekoppelde lys, en new_node dui op die nuwe knoop wat jy wil in te voer in, net toeken kop new_node sou verloor die skakel na die res van die lys. So ons wil dit nie te doen nie. 

Inteendeel, ons wil om seker te maak dat ons vashou aan elke enkele knoop in ons program. So loop new_node pyltjie langs gelykes kop en dan kop gelyk new_node al die sal bewaar links en geen verloor. 

Maar wat as jy wil om jou lys te wees gesorteer, want met 'n gesorteer gekoppel lys kan wees makliker vir soek dit later op? Wel, vir wat, sal jy nodig het om te weet hoe geskakelde lyste te deurkruis. 

'N geskakelde lys te deurkruis, laat ons' 'n knoop wyser, 'n knoop *, soos om op te tree jou wyser, wat aandui wat node jy op, begin op die eerste element. Herhaling totdat wyser is nul, ons kan voer sekere prosesse en dan bevorder die wyser wanneer ons dit nodig gebruik wyser waarde. 

Onthou, dit is dieselfde as sê star wyser, ontwysing wyser, dan met behulp van die dot operateur waarde. So afhangende van die wyser deur die toeken die wyser na wyser volgende. 

Sê jy bepaal dat D word in tussen C en E. die knoop te voeg, het die new_node D punt aan die knoop E, wat is wyser volgende. En dan C, die wyser, kan dan wys D. Op dié manier, in stand te hou 'n lys. Wees versigtig om nie jou links te verloor deur beweeg die wyser langs D dadelik. 

Alle regte. So dit is hoe jy kan nodes, laai hulle in, laai woorde in dié nodes, en plaas dit in jou hash tafel. So nou laat ons kyk na drieë gedruk. 

In 'n Trie, sal elke node bevat 'n verskeidenheid van node wysers, een vir elke letter in die alfabet plus 'n toespraak. En elke element in die skikking sal wys na ander rekenaars. As dit knoop is van nul is, dan het die brief is nie van plan om die volgende letter te wees enige woord in 'n ry, want elke woord dui aan of dit is die laaste karakter van 'n woord of nie. 

Kom ons kyk na 'n diagram. Hopelik sal dinge 'n bietjie duideliker. In hierdie diagram, sien ons dat slegs sekere letters en sekere substrings word gelys is. So jy kan volg om sekere paaie en al daardie paaie sal jou lei tot verskillende woorde. 

So hoe kan ons stel dit in C? Wel, elke knoop nou gaan hê 'n Boolese waarde wat aandui of dat knoop is die einde van 'n gegewe woord is of nie. En dan sal dit ook 'n verskeidenheid van knoop wysers genoem kinders, en daar gaan wees 27 van hulle. En onthou, jy sal ook wil hou van jou eerste knoop. Ons gaan dat die wortel te bel. 

So wat is die struktuur van 'n Trie. Hoe kan ons verteenwoordig hierdie as 'n woordeboek? Wel, om woorde te laai in, vir elke woord uit die woordeboek, jy gaan te hê om Itereer deur die Trie. En elke element in die kinders ooreenstem met 'n ander brief. 

So die nagaan van die waarde op kinders indeks i, waar ek verteenwoordig die spesifieke indeks van die brief wat jy probeer te voeg. Wel, as dit is van nul, dan sal jy wil malloc 'n nuwe knoop en kinders Ek het daarop gewys knoop. 

As dit nie null, dan beteken dit dat gegee dat die tak, wat gegee substring, bestaan ​​reeds. So dan sal jy net skuif na daardie nuwe knoop en voort te gaan. As jy aan die einde van die woord wat jy probeer te laai in die woordeboek, dan kan jy dit knoop wat jy op te ware. 

So laat ons kyk na 'n voorbeeld van die inbring die woord "jakkals" in ons woordeboek. Voorgee begin ons met 'n leë woordeboek. Die eerste brief, F, geleë sal wees in kinders indeks vyf van die wortels kinders skikking. So het ons voeg dat in 

Die letter O sal dan in kinders indeks 15, nadat F. En dan X sal selfs onder die wat, vertakking af van die O se kinders. En dan, omdat X is die laaste brief van die woord "jakkals", dan gaan ek kleur wat groen aan te dui dat dit is die einde van die woord. In C, wil hê dat die opstel word die IS Word Boole ter waarde waar. 

Nou wat as die volgende woord wat jy laai in die woord "cat"? Wel, jy hoef nie meer te malloc ruimte vir F of O, omdat diegene wat reeds bestaan ​​nie. Maar die laaste O in cat? Dat 'n mens, sal jy moet malloc. Maak 'n nuwe node vir wat, die opstel Is die Woord Boolean waar. 

So nou laat ons plaas "hond." Hond sal begin met indeks drie van die wortels kinders, omdat D het nie is nog geskep. En ons sal 'n soortgelyke proses as volg voor, die skep van die substring hond, Waar is die G is groen gekleur omdat dit is die einde van 'n woord. 

Nou, wat as ons wil voeg "doen"? Wel, dit is 'n substring van die hond, so Ons het nie meer nodig om malloc. Maar ons hoef aan te dui waar ons bereik die einde van die woord. So het die O groen sal gekleur word. Voortgesette dat die proses vir elke enkele woord in jou woordeboek, jy het gelaai hulle in in een van jou Hutstabel of jou Trie. 

speller.c sal slaag in stringe vir dictionary.c om hulle te gaan. Nou, die Check funksie te bedryf onder geval onsensitiwiteit. Dit beteken dat hoofletters en kleinletters en 'n mengsel van beide moet almal gelyk aan ware indien enige kombinasie van wat in die woordeboek. Jy kan ook aanvaar dat snare is gaan net te bevat alfabetiese karakters of apostrofes. 

So laat ons kyk na hoe jy kan check met 'n hash tafel struktuur. Wel, as die woord bestaan, dan is dit kan gevind word in die hash tafel. So dan kan jy probeer om uit te vind wat woord in die betrokke emmer. 

So wat emmer sou daardie woord wees? Wel, jy sal die getal, die indeks kry van die emmer, deur hashing dat die woord en dan soek in wat gekoppel lys dwars deur die hele gekoppel lys, met behulp van die String Vergelyk funksie. 

As die einde van die lys is gekoppel bereik, wat beteken dat jou wyser bereik van nul is, dan is die woord nie gevind kan word in die woordeboek. Dit sal nie in enige ander emmer. So hier is, kan jy sien hoe daar dalk 'n trade-off tussen wat óf gesorteer gekoppel lyste of ongesorteerde kinders. Óf meer tyd sal neem tydens laai of meer tyd tydens check. 

Hoe kan jy so 'n tydstip waarop struktuur? Ons gaan afwaarts reis in die Trie. Vir elke letter in die woord ingevoer dat ons nagaan, sal ons gaan na daardie ooreenstemmende element in die kinders. 

As daardie element is van nul, dan beteken dit dat dat daar geen substrings wat ons insette woord, so die woord verkeerd gespel. As dit nie null, kan ons skuif na die volgende letter van die woord wat ons is nagaan en voortgaan om hierdie proses totdat ons aan die einde van die insette woord. En dan kan ons seker As deur die Woord is waar. As dit is, dan is groot. Die woord is korrek. Maar indien nie, selfs al is dit substring bestaan ​​in die Trie, is die woord verkeerd gespel. 

Wanneer die funksie grootte is geroep, grootte moet die aantal woorde wat terugkeer in jou gegee woordeboek data struktuur. So as jy 'n hash tafel, jy kan óf gaan deur elke enkele geskakelde lys in elke enkele emmer die tel van die aantal woorde is daar. As jy met behulp van 'n Trie, kan jy gaan deur elke nie null pad in jou Trie. Of terwyl jy die woordeboek laai in, miskien kan jy track hou van hoe baie woorde jy laai in 

Sodra speller.c eindig die beheer van die tekslêer teen die woordeboek, dan dit gedoen en daarom is dit 'n beroep los, waar jou werk is om iets te bevry wat jy malloced. So as jy 'n hash tafel, dan is jy moet veral versigtig om te verhoed dat te wees geheue lekkasies deur nie bevry enigiets vroeg en hou op elke enkele skakel voordat jy gratis. 

So vir elke element in die hash tafel en vir elke node in die geskakelde lys, jy sal wil hê dat die knoop te bevry. Hoe gaan jy te bevry 'n geskakelde lys? Die opstel van jou node wyser wyser te die hoof, aan die begin van die gekoppel lys, dan terwyl jou wyser is nie null, kan jy 'n tydelike knoop wyser na jou wyser. Dan bevorder die wyser. En dan kan jy bevry wat tydelike waarde, terwyl hy nog vashou aan alles daarna. 

Wat as jy met 'n Trie? Dan is die beste manier om dit te doen is om af te laai vanaf die onderste na die top. Deur te reis na die laagste moontlike knoop, kan jy gratis alle verwysings in dat kinders en dan terugry opwaarts, bevry al die elemente in alle van die kinders skikkings, totdat jy getref jou top wortel node. Hier is waar Rekursie sal handig te pas kom. 

Om seker te maak dat jy het waarskynlik bevry alles wat jy het malloced, jy kan gebruik om Valgrind. Hardloop Valgrind sal jou program loop tel hoeveel grepe van die geheue jy gebruik en om seker te maak dat jy ' bevry hulle almal, jy vertel waar jy kan hê vergeet gratis. Hardloop sodat en sodra Valgrind vertel en gee jou die voort te gaan, dan jy, aflaai klaar is. 

Nou, 'n paar wenke voor jy gaan af en begin met die implementering van jou woordeboek. Ek sou aanbeveel in 'n kleiner te slaag woordeboek wanneer jy probeer om te toets dinge uit en ontfouting met die BBP. Die gebruik van speller is. / Speller, 'n opsionele woordeboek, en dan 'n teks. 

By verstek, is dit vragte in die groot woordeboek. So wil jy dalk in die klein te slaag woordeboek, of dalk selfs jou eie, die opstel van jou woordeboek en jou teks lêer. 

En dan uiteindelik, ek wil ook aanbeveel 'n pen en papier te neem en te teken dinge uit voor, gedurende en na jy al jou kode het geskryf. Net seker maak dat jy ' diegene wysers net reg. 

Ek wens jou die beste van geluk. En as jy klaar is, as jy wil die groot raad en uit te daag sien hoe vinnig jou program is in vergelyking met jou klasmaats ", dan moedig ek julle wat te sien. 

Met dit, het jy klaar die speller PSet. My naam is Zamyla, en dit is CS50.