ZAMYLA Chan: Csináljunk a helyesírás-ellenőrző. Ha kinyitja speller.c, akkor látni fogod hogy a legtöbb funkcionalitás ellenőrzése egy szöveges fájlt ellen szótár már az Ön számára. . / Helyesírás, átadva a szótárban szövegben fájlt, majd egy másik szöveges fájl, ellenőrzi, hogy a szöveges fájl szemben a szótárban. 

Most, szótár szöveges fájlok tartalmazzák érvényes szó, soronként egyet. Ezután speller.c hívja Load A szótár szöveges fájl. Úgy hívom funkció nevű Ellenőrizze minden szót a bevitt szöveges fájl, nyomtatás minden helytelenül írt szavakat. 

Speller.c is hívni Size meghatározzák a szavak száma szótár és hívja Unload felszabadítani memóriát. speller.c is nyomon követheti, hogy sok időt használják, hogy végezzen ezen folyamatokat, de majd eljutni, hogy később. 

Mit kell tennünk? Meg kell, hogy töltse ki dictionary.c. A dictionary.c, mi van a segítő funkció betöltése, amely betölti a szótárban. A funkció Check, amely ellenőrzi, hogy egy adott szó szerepel a szótárban. A függvény Size számát adja vissza A szavak a szótárban. És végül, mi kirak, amely megszabadítja a szótárban a memóriából. 

Tehát először, hadd kezelni betöltése. Minden szó a szótárban szövegben fájl betöltése tárolja ezeket a szavakat A szótár adatstruktúra az Ön által választott, vagy a hash tábla vagy trie. Megyek, mint mind a ez a séta. 

Először is beszéljünk hash táblákat. Tegyük fel, hogy 10 biliárd golyó és akarod tárolni őket. Lehet, hogy tedd őket egy vödör, és ha szükség van egy bizonyos számozott golyó, azt hogy egy ki a vödör egy időben keresi a labdát. És csak 10 golyó, ha kell képes megtalálni a labdát ésszerű ideig. 

De mi van, ha már 20 golyót? Ez eltarthat egy kis ideig most. Mi a helyzet a 100? 1000? Nos, ez sokkal könnyebb, ha hogy volt több vödör. Talán egy vödör labda számozott nulla a kilenc, a másik vödör labdák számozott 10 és 19, és így tovább. 

Most, amikor kellett keresni bizonyos labda, akkor automatikusan menj egy adott vödör és keresni, hogy a vödör. És ha minden vödör körülbelül 10 golyó, akkor könnyen keres át rajta. 

Most, mivel van dolgunk szótárak, egyetlen vödör az összes szó a szótár valószínűleg túl kevés vödör. Szóval vessünk egy pillantást a hash táblák. 

Gondold azt, hogy egy sor vödör. És ebben az esetben, a kanalak a mi kapcsolt listák. És mi terjeszteni minden szavaink ezek közül több kapcsolt listák szervezett módon egy hash függvény, , amely megmondja, hogy melyik vödör egy adott kulcsot, egy adott szó, tartozik. 

Nézzük képviseli ezt sematikusan. A kék doboz Itt értékeket tartalmaz, és piros doboz pont egy másik értéket mutató pár. Majd hívja ezeket pár csomópontok. Most minden vödör, mint mondtam korábban, egy láncolt lista. A kapcsolt listák, minden csomópont értéke, valamint a mutató a következő érték. 

Most foglalkozó kapcsolt listák, ez nagyon fontos, hogy ne vesszenek el linkeket. És egy másik tény, hogy emlékezzen, hogy a utolsó csomópont, ha nem mutat egy másik csomópont, rámutat arra, null. 

Szóval hogyan képviseljük ezt a C? Mi határozza meg a struct itt. És az érték ebben az esetben egy char tömb hosszát. Hossz plusz 1, ahol a hossza maximális hossza minden szó, plusz 1 A null terminátor. És akkor van egy mutatót másik csomópont az úgynevezett Next. 

Szóval egy kis láncolt lista. Először is, akkor szeretné malloc a csomópont, melyek között helyet a memóriában a mérete a csomópont típusát. És hogy egy másik csomópont, ismét mallocing. 

Most, ha azt szeretnénk, hogy egy értéket, hogy a szó, akkor azt mondhatnánk Node1 nyíl szó egyenlő "Hello." Ez a nyíl operátor dereferences a mutató és a hozzáfér a struct a változókat. Így nem kell használni a két A pont és a csillag operátor. 

Így aztán van node2 nyíl szó értéke "A világ." És ott, az értékek lakott az én csomópontok. Ahhoz, hogy a linkeket, majd át a Node1 mutató nyilat, hozzáférés a csomópont csillag, hogy a csomópont mutató, egyenlő node2, rámutatva Node1 a node2 kettő. És ott van egy láncolt lista. 

Szóval ez csak egy láncolt lista, de a hash tábla egy egész sor kapcsolt listák. Nos, akkor ugyanaz a csomópont szerkezet, mint korábban. De ha volna egy valódi hash tábla, akkor csak egy csomópontot mutató array itt. Például, méret 500. 

Figyeljük, ott lesz a kereskedelmi le a méretét, a hash tábla és a méret a kapcsolt listák. Ha van egy nagyon nagy számú vödrök, elképzeli, hogy fuss vissza -oda, hogy egy sorban megtalálja a vödör. De akkor is, nem akar egy kis számú vödrök, mert akkor vagyunk vissza Az eredeti probléma az, hogy miután Túl sok golyókat a vödör. 

OK, de hol a labda megy? Nos, először meg kell van a labda, nem igaz? Szóval malloc csomópont minden új szó, hogy mi van. node * new_node egyenlő malloc (sizeof (node)). 

Most, hogy ezt a struktúrát, akkor képes beolvasni, a funkció fscanf egy stringet a fájlt, ha ez a szótár fájlt, a new_node nyíl szó, ahol new_node nyíl szó a mi rendeltetési ezt a szót. 

Ezután, akkor szeretnénk kódot, ami szót a hash függvényt. A hash függvény a karakterlánc , és visszatér az index. Ebben az esetben, az index kell lehet kevesebb, mint ahány vödör, hogy van. 

Most, hash függvények, amikor akarsz megtalálni az egyik, és hozzon létre egy saját, ne feledje, hogy kell determinisztikus. Ez azt jelenti, hogy ugyanazt az értéket kell ugyanarra az vödör minden alkalommal hogy hash azt. 

Ez olyan, mint egy könyvtár. Ha veszel egy könyvet, amely a szerző, tudja, melyik polcon kellene megy, legyen szó akár polc számot egy, kettő, vagy három. És ez a könyv mindig tartozik a polc vagy egy, két, vagy három. 

Tehát, ha new_node nyíl szónak a szót a szótárban, akkor hashing new_node nyíl Word nekünk az index a vödör a hash tábla. És akkor majd be, hogy az ebbe a speciális láncolt lista jelzi, vissza értéket a hash függvény. 

Nézzünk egy példát behelyezése csomópont a elején egy láncolt lista. Ha a feje egy csomópont mutató, amely jelzi az elején egy kapcsolt listára, new_node jelzi az új csomópont, amely meg szeretné adni a csak hozzárendelése fej new_node veszít a kapcsolatot a többi a listán. Tehát nem akarom ezt csinálni. 

Inkább azt szeretnénk, hogy győződjön meg arról, hogy ragaszkodnak a minden single node a programunkban. Így fut new_node nyílra egyenlő fejét, majd fej egyenlő new_node megőrzi az összes kapcsolatokat, és nem vesztett. 

De mi van, ha azt szeretné, hogy dől, hogy sorrendje, mert miután a sorrendje kötött lista talán könnyebb keres, hogy a későbbiekben? Nos, az, hogy akkor kell tudni hogyan áthalad láncolt listák. 

Áthalad a láncolt lista, vessünk egy csomópont mutató, egy csomópont *, hogy jár a kurzort, hogy mely csomópont te vagy, kezdve az első elem. Hurok amíg kurzor null, tudjuk magatartás bizonyos folyamatokat, majd a előre a kurzor, amikor szükségünk a kurzor nyíl értéket. 

Ne feledje, hogy ez ugyanaz, mint a mondván csillag kurzor, dereferencing kurzorral, majd a dot operátor értéke. Így frissíti a kurzor hozzárendelésével a kurzort a kurzor nyílra. 

Mondja el, hogy határozza meg, hogy a D válik a a C és E behelyezéséhez a csomópont, van new_node D pont a node E, amely a kurzor mellett. És akkor a C, a kurzor, aztán pont D. Így, ha fenntartja a listát. Ügyeljen arra, hogy ne veszítse el a linkeket mozog a kurzor nyílra D azonnal. 

Rendben van. Szóval így lehet beszúrni csomópontok, töltse be őket, terhelés szavak ezek csomópontok, és helyezze őket be a hash tábla. Most nézzük meg próbál. 

A trie minden csomópont tartalmaz tömb csomópont mutatók, egy minden betű az ábécé plusz egy aposztróf. És minden egyes elem a tömbben fog mutatni egy másik csomópont. Ha ez a csomópont null, akkor a levél nem lesz, hogy a következő levél bármilyen szót egymás után, mert minden szó jelzi, hogy ez az utolsó karakter egy szó, vagy sem. 

Nézzük meg a diagram. Remélhetőleg a dolgok egy kicsit világosabb. Ezen az ábrán azt látjuk, hogy csak a Egyes betűk és bizonyos stringek kerülnek felsorolt ​​ki. Így a bizonyos utak és az összes ilyen út fog vezetni, hogy más szavakkal. 

Szóval hogyan képviseljük ezt a C? Nos, minden csomópont most már megy, hogy egy logikai érték azt jelzi, hogy csomópont, hogy a vége a egy adott szó vagy sem. És akkor lesz is egy sor node mutatók nevű gyermekeket, és ott lesznek a 27-et. És ne feledd, akkor is szeretnénk nyomon követheti az első csomópont. Fogjuk hívni, hogy a gyökér. 

Szóval ez a szerkezet egy trie. Hogyan képviselik ezt a szótárban? Nos, betölteni szavak, minden szótári szót, fogsz akar hogy halad végig a trie. És minden egyes eleme a gyerekek felel meg egy másik levelet. 

Így ellenőrzi az értéket gyerekek i indexet, ahol i a specifikus indexet a levélnek, akarsz beilleszteni. Nos, ha ez nulla, akkor szeretné majd malloc egy új csomópont, és a gyermekek Én pont a csomópont. 

Ha ez nem nulla, akkor ez azt jelenti, hogy az hogy az adott ágazatban, hogy az adott substring, már létezik. Tehát akkor csak költözni, hogy új csomópont és tovább. Ha a végén a szó, hogy próbál betölteni a szótárt, akkor beállíthatja, hogy a jelenlegi csomópont, hogy te vagy az igazi. 

Tehát nézzük meg egy példát beillesztése a "róka" a mi szótárban. Tegyen úgy, mintha kezdjük egy üres szótárban. Az első betű, N, lesz található gyermekeknél indexe öt a gyökerek gyerekek tömb. Tehát be, hogy be 

Az O betű ezután a gyermekek index 15, azt követően, hogy F. És akkor X lesz még elmarad, elágazás ki az O gyermekei. És akkor azért, mert az X az utolsó betű A szó "róka", akkor megyek hogy a zöld szín jelzi, hogy ez a végén a szó. A C-ben, hogy a beállítás lenne az Is A Word Boolean értékre igaz. 

Most mi van, ha a következő szó, hogy te Betöltés a "valami"? Nos, akkor nem kell malloc többé hely a F vagy O, mert a már léteznek. De az utolsó O foo? Az az egy, akkor meg kell malloc. Készíts egy új csomópont számára, hogy a beállítás A szájról logikai igaz. 

Tehát most menjünk be "kutya". Kutya indexe három kezdeni a gyökerek gyermekek, mert D nem hozták létre, mégis. És mi követik hasonló folyamat előtt, ami a substring kutya, hol van a G zöld színű, mivel ez a végén egy szót sem. 

Nos, mi van, ha azt akarjuk, hogy be "csinálni"? Nos, ez egy substring kutya, így a nem kell malloc többé. De el kell, hogy jelezze, hol voltunk végére ért a szót. Így az O lesz zöld színű. Folytatva ezt a folyamatot minden egyes szó a szótárban, akkor már betöltött őket be akár a hash tábla, vagy a trie. 

speller.c fog múlni a húrok dictionary.c, hogy ellenőrizze őket. Most, a Check funkció működik alatt érzékenységet. Ez azt jelenti, hogy a nagybetűk és a kisbetűk és a kettő keveréke kell minden egyenértékű a igaz, ha minden kombinációja, ami a szótárban. Azt is feltételezik, hogy a húrok csak akkor fog tartalmaznia ábécé karakterek vagy aposztrófok. 

Tehát nézzük meg, hogyan lehet ellenőrizni egy hash tábla szerkezetét. Nos, ha a szó létezik, akkor megtalálható a hash táblában. Szóval, akkor próbálja meg, hogy szó a megfelelő kukába. 

Tehát melyik vödör lenne szó legyen? Nos, azt a számot, hogy az index a kanál, a Wget szó , majd a keresés az, hogy láncolt lista, áthaladó az egész láncolt lista, a karakterlánc Hasonlítsa össze a funkciót. 

Ha a végén a kapcsolódó lista érte el, ami azt jelenti, hogy a kurzor eléri null, akkor a szó nem megtalálható a szótárban. Nem lesz más vödör. Tehát itt, akkor lehet látni, hogy ott lehet egy kompromisszumot, amelyek rendelkeznek sorrendje kapcsolt listák vagy válogatás nélkül is. Vagy több időre lesz szükség idején betölteni vagy több idő alatt ellenőrzés. 

Hogy lehet, hogy ellenőrizze a a trie szerkezet? Fogunk utazni lefelé A trie. Minden egyes levél a bevitt szó hogy mi ellenőrzés, akkor megy, hogy megfelelő elem a gyerekek. 

Ha ez az elem nulla, az azt jelenti, hogy nincsenek részkarakterláncok amely a bemeneti szó, így a a szó el van írva. Ha ez nem nulla, akkor menjen a következő betű, a szó, hogy mi vagyunk ellenőrzése és továbbra is ezt a folyamatot amíg el nem érjük a végét a bemeneti szó. És akkor tudjuk ellenőrizni ha szájról igaz. Ha igen, akkor jó. A szó helyes. De ha nem, annak ellenére, hogy a substring létezik a trie, a szó hibásan. 

A funkció Méret neve, mérete vissza kell adnia a szavak száma, amely vannak a adott szótárban adatstruktúra. Tehát, ha egy hash tábla, akkor sem megy keresztül minden egyes láncolt lista minden egyes vödör számítva a szám szavak vannak. Ha használ trie, akkor megy keresztül minden nem null utat az trie. Vagy amíg töltöd a szótárban ben, talán te is nyomon követheti, hogyan sok szót töltöd be 

Ha speller.c befejezi ellenőrzése szöveges fájlt szemben a szótárban, akkor ez történt, és ezért kéri, kirak, ahol a feladata, hogy szabad semmit hogy már malloced. Tehát, ha egy hash táblát, akkor kell, hogy legyen különösen óvatos, hogy ne memóriavesztés, hogy nem szabaddá semmit idő előtt és kapaszkodott minden Single Link előtt ingyenes. 

Így minden eleme a hash tábla és minden csomópont a láncolt lista, akkor szeretnénk felszabadítani a csomópont. Hogy megy a szabaddá A láncolt lista? Beállítása csomópont egérmutatót a a fejet, hogy az elején a láncolt lista, majd miközben a kurzor nem null, akkor meg egy átmeneti node mutató a kurzort. Ezután előre a kurzort. És akkor szabad, hogy az ideiglenes érték miközben folyamatosan tovább Mindent utána. 

Mi van, ha egy trie? Akkor a legjobb módja annak, hogy ezt hogy kirak a nagyon lentről felfelé. Az utazás a lehető legalacsonyabb csomópont, akkor szabad az összes mutatókat hogy a gyerekek majd visszalép felfelé, felszabadítja az összes elemet minden a gyerekek tömbök, amíg bejön a felső gyökér csomópont. Itt, ahol rekurzió jól jöhet. 

Annak érdekében, hogy már valószínűleg felszabadult Mindent, amit malloced, használhatja Valgrind. Running Valgrind fog futni a programot számítva hány bájt memóriával amit használ, és ügyelve arra, hogy már kiszabadította őket, mondom ahol lehet, hogy elfelejtett ingyenes. Úgy fussatok, hogy az, és ha Valgrind megmondja és adja meg a zöld utat, akkor befejezte a memóriából. 

Most, néhány tipp, mielőtt elmész off és start végrehajtásának a szótárban. Én azt javasolnám, hogy adja át egy kisebb szótár, ha akarsz tesztelni a dolgokat, és a hibakeresés a GDP. A használata helyesírás is. / Helyesírás, egy opcionális szótár, majd a szöveget. 

Alapértelmezésben betölti a nagy szótár. Tehát érdemes átadni a kis szótár, vagy akár, hogy a saját, testre szótár és a szöveges fájl. 

És végül, én is ajánlom hogy egy tollat ​​és papírt, és felhívni dolgokat előtt, alatt és után írtál az összes kódot. Csak győződjön meg arról, hogy van ezek a mutatók csak jobb. 

Kívánok sok szerencsét. És ha egyszer már elkészült, ha szeretné kihívást jelent a nagy táblára, és milyen gyors a program, mint a az osztálytársaival ", akkor azt javasoljuk, , hogy ellenőrizze, hogy ki. 

Ezzel befejezte A helyesírás Pset. A nevem Zamyla, és ez CS50.