>> 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.