[Powered by Google Translate] [Walkthrough - Probléma Set 5] [Zamyla Chan - Harvard University] [Ez CS50. - CS50.TV] 

Rendben van. Hello, mindenkinek, és üdvözöljük a Walkthrough 5. 

Pset5 a Helyesírási hibák, amiben lesz, hogy a helyesírás-ellenőrző. Helyesírás-ellenőrzők rendkívül fontos. Úgy ez valaha is történt veled? Dolgozik, nagyon felhalmoz egy könyv a összecsapás és akkor még a végén kapok egy nagyon fény vettek részt, mint a D vagy D = és mindezt azért, mert te vagy a kenőmájas spoiler a bálna széles szót. Igen, lektorálás a paprika van szó az, a legnagyobb impotencia. Ez egy olyan probléma, amely érinti férfias, férfias diákok. Én egyszer azt mondta az én sith fokozatú kínvallató, hogy én soha nem kap egy jó kolléga. És ez minden, amit valaha akartam, ez minden, minden gyerek azt akarja, az én koromban, csak azért, hogy egy jó kolléga. És nem akármilyen kolléga. Nem akartam menni egy Ivory Legal kolléga. Szóval, ha én nem javulás, ment volna az álmaim az megy Harvard, Jale, vagy Prison - tudod, a börtönben, New Jersey. Szóval magamnak egy helyesírás-ellenőrző. Ez egy kis részlet az egyik kedvenc kimondott szó művészek, Taylor Mali. Különben is, mint mondja, annak fontosságát, hogy a helyesírás-ellenőrző is nagyon fontos. 

Szóval szívesen Walkthrough 5, amiben lesz szó pset5: Helyesírási hibák, amiben lesz, hogy mi nagyon saját helyesírás-ellenőrző. Az eszköztár ezen a héten, az elosztási kód lesz fontos, hogy nézd meg csak azért, hogy megértsék a különböző funkciók, hogy a szótár fog van. Mi valóban lesz, amelynek több. C fájlokat, hogy együtt tegyük Pset. És így néz át a különböző szempontok, bár mi valójában nem szerkesztés egyik a fájlokat, speller.c, tudván, hogyan működik-vel kapcsolatos dictionary.c, amely azt fogja írni, lesz nagyon fontos. A Pset spec is tartalmaz sok hasznos információt szempontjából dolog, amit vállal, szabályok és ilyesmi, így biztos, hogy olvassa el a Pset spec gondosan tippeket. És ha kétség olyan szabály, vagy valami ilyesmi, akkor mindig a Pset spec vagy Beszéljétek meg. Ez Pset fog nagymértékben támaszkodik a mutatók, így szeretnénk, hogy győződjön meg arról, hogy megértjük a különbséget hozzá csillagos előtt a mutató neve és ampersands, hogyan lehet kiszabadítani őket, stb Tehát, hogy egy mester mutató lesz nagyon hasznos ez a probléma meg. Megyünk, hogy vizsgálja meg linkelt listák egy kicsit, ahol olyan elemei, amelyek hívjuk csomópontokat, amelyek mind egy érték, valamint egy mutatót a következő csomópont, és így lényegében összekapcsoló különböző elemei egymás után a másik. Van néhány különböző lehetőségek megvalósítása a tényleges szótárban. Fogunk nézni két fő módszer, amely hash táblák, majd megpróbálja. Az e két, az együtt jár valamiféle fogalmának a láncolt lista ahol még elemek kapcsolódnak egymáshoz. És így fogunk nézni, hogy hogyan lehet, hogy működni körül kapcsolódó listákat, létre őket, navigáljon szempontjából hogyan kell például, helyezzen be egy csomópont bele vagy mentes az összes csomópont is. Ami a felszabadítása csomópontok, ez nagyon fontos hogy amikor mi malloc memória, utána már szabad is. Ezért szeretnénk, hogy győződjön meg arról, hogy nem megy pointer unfreed, hogy mi nincs memóriavesztés. Megyünk, hogy vezessenek be egy szerszám hívott Valgrind hogy fut a program és ellenőrzi, hogy minden a memóriában, amit kiosztott, majd felszabadul. Ön Pset csak akkor fejeződik be, ha ez működik, és azt a teljes funkcionalitás, hanem Valgrind azt mondja, hogy nem talált semmilyen memóriavesztés. Végezetül, ezen Pset, én tényleg szeretnék hangsúlyozni - Úgy értem, mint mindig, én határozottan támogatója a tollat ​​és papírt a probléma készletek, de ez, azt hiszem, hogy a toll és papír lesz különösen fontos ha azt szeretné, hogy rajz nyilak dolgokat, és megérteni, hogyan működnek a dolgok. Tehát mindenképpen próbálja használni tollat ​​és papírt, hogy dolgozzon a dolgokat, mire kódoló mert ez is egy kicsit rendetlen. 

Először is, menjünk be linkelt listák egy kicsit. Csatolt listák állnak csomópontok, ahol minden csomópont értéke társítva, valamint egy mutatót a következő csomópont után. Egy pár dolog fontos a kapcsolt listák, hogy meg kell emlékezni ahol az első csomópont van, és majd egyszer tudjuk, hol az első csomópont, így tudjuk elérni a csomópontot, hogy az első csomópont pontok és azután az egymás után, hogy és az egymás után az. És akkor az utolsó elemet a láncolt lista, hogy a csomópont pointer mindig fogja mutatni NULL. Amikor egy csomópont pontot NULL, akkor tudod, hogy már a végére ért a lista, hogy ez a csomópont az utolsó, hogy nincs semmi után. Itt, ebben a vázlatos, láthatjuk, hogy a nyilak a mutatók, és a kék rész az, ahol az érték eltárolódik, majd a piros mezőben a mutató szerint ez a csomópont mutató rámutatva, hogy a következő csomópont után. És itt látható, a D csomópont emlékeztet NULL, mert ez az utolsó elem a listában. 

Nézzük meg, hogyan lehet meghatározni a struct egy csomópont. És mivel azt akarjuk, hogy több csomópont, ez fog válni a typedef struct amelyben fogunk több különböző esetben a csomópontok. És így meg úgy, mint egy új adattípust. Itt van egy typedef struct csomópont. Ebben a példában van dolgunk egész csomópontok, így már egy egész nevű értéket, és akkor van egy másik mutató, és ebben az esetben, ez a mutató egy csomópont, így van egy struct node * nevű következő. És akkor mi hív ez az egész csomópontot. Ügyeljen arra, hogy kövesse ezt a szintaxist. Figyeljük meg, hogy a csomópont valójában hivatkozik fönt, valamint alacsonyabb a kapcsos zárójelek. Ezután nyomon követni, ahol az első csomópont ebben a linkelt listán, aztán van egy node pointer nevű feje, és én malloc tér elég a mérete csomópont. Közlemény, azonban, hogy a fej valójában egy csomópont mutató szemben tényleges csomópont maga. Így a fej valójában nem tartalmaz bármilyen érték, csak mutat amelyik az első csomópont az én láncolt lista van. 

Ahhoz, hogy egy jobb értelemben kapcsolt listák, mert ez nagyon fontos nyomon követni, hogy arról, hogy fenntartsák a lánc, Szeretném azt gondolni, hogy az emberek egy sorban egymás kezét, ahol minden egyes személy kezét a következőt. Nem lehet látni ezt a rajzot, de alapvetően ők mutatnak, hogy a következő személy hogy az ő láncban. És ha azt szeretnénk, hogy áthalad a láncolt lista, ahol ezek az emberek - képzelni az összes ilyen ember értékek velük és az is rámutatnak, hogy a következő ember a sorban - ha azt szeretné, hogy áthalad a linkelt listán, például, hogy, módosítsa az értékeket vagy keressen meg egy értéket, vagy valami ilyesmi, akkor akarja, hogy a mutató az adott személy. Szóval megy, hogy egy adattípus csomópont mutató. A jelen esetben, nevezzük kurzort. Másik gyakori módja, hogy nevet ez lenne iterator vagy valami ilyesmi mert ez iterációjával át, és ténylegesen mozgó amelyek node ez mutat. Ez itt lesz a kurzor. A kurzor először mutatni az első eleme a listában. És amit akarok, mi lenne alapvetően továbbra is a kurzort, mozog egyik oldalról a másikra. Ebben az esetben azt akarjuk mozgatni azt a következő elem a listában. A tömbök, mit tennénk, ha a mi lenne, csak mondjuk növelni az index 1-gyel. Ebben az esetben mit kell tennie, hogy ténylegesen melyik személy találta ezt az áramot személyt mutat, és ez lesz a következő érték. Tehát, ha kurzor csak egy csomópont mutató, akkor mit akarunk csinálni nem szeretnénk, hogy az érték a kurzor mutat. Azt akarjuk, hogy az adott csomópont és aztán, ha már itt tartunk, hogy a csomópont, találni, ahol ez mutat. Ahhoz, hogy a tényleges csomópont a kurzor mutat, általában azt jelzi, hogy a (* kurzor). Ez lenne Önnek az aktuális csomópont a kurzor mutat. És majd azt követően, hogy amit akarok, azt akarjuk elérni függetlenül, hogy a csomópont melletti érték. Ehhez eléréséhez értékek belsejében a struct, mi van a pont operátor. Akkor lenne (* kurzor). Következő. De ez egy kicsit koszos tekintetében, amelyek a zárójelek * kurzor, és így helyettesíteni ezt az egész nyilatkozatot a kurzor->. Ez egy kötőjel, majd egy nagyobb jel, s így egy nyíl. kurzor-> next. Ez valóban kapni a csomópontot, hogy a kurzor mutat. Ez az érték a következő. Tehát ahelyett, hogy a csillag és a pont, akkor a helyébe lépő egy nyíllal. Legyen nagyon óvatos, hogy győződjön meg arról, hogy megpróbálja ezt a szintaxist. 

Most, hogy megvan a kurzor, ha azt akarjuk elérni az értéket, előtt, volt kurzor-> next, de elérni a érték a csomópont, hogy a kurzor mutat, csak egyszerűen azt mondja node-> érték. Onnan, ez az adattípus bármilyen általunk meghatározott értékek és a csomópontok is. Ha ez egy int csomópontot, majd a kurzor-> érték csak lesz egy egész. Így tehetünk műveleteket, hogy ellenőrizze, esélyegyenlőségi, rendelje hozzá a különböző értékek, stb Akkor mit akarsz csinálni, ha azt szeretné mozgatni a kurzort a következő személy, valóban módosítsa az értéket a kurzor. Mivel a kurzor egy csomópont mutató, megváltoztatja a tényleges mutató címet a címe a következő csomópont a listán. Ez csak egy kódot, ahol meg lehet navigálhat. Hol van a megjegyzést tenni valamit, ez az, ahol akkor valószínűleg fog elérni az érték vagy valami köze az adott csomópont. Először le, azt mondom, hogy az én kurzor kezdetben fog mutatni az első eleme a láncolt lista. És így előttünk, úgy határozta meg, mint a feje a csomópontot. 

Ahogy már korábban említettem, megszabadítva nagyon fontos. Azt szeretnénk, hogy győződjön meg arról, hogy szabadon minden elem a listában, ha már elkészült vele. Ha nem kell hivatkozni bármely olyan mutatók már, azt szeretnénk, hogy győződjön meg arról, hogy szabad az összes ilyen mutató. De azt szeretnénk, hogy legyen nagyon óvatos, itt kívánt elkerülése memóriavesztés. Ha szabad egy ember idő előtt, akkor az összes mutató, hogy ez a csomópont mutat fog veszni. Visszatérve a fő példa, hogy ez egy kicsit több high stakes, vessünk ezeket az embereket, kivéve a jelen esetben ezek lebeg egy tó, egy szörnyeteg. Azt szeretnénk, hogy győződjön meg arról, hogy amikor mi szabadon, ne veszítsük el és elengedte minden csomópont előtt mi már tulajdonképpen felszabadította őket. Például, ha úgy döntesz, hogy egyszerűen hívja ingyenes ez a fickó itt, akkor ő is felszabadul, de akkor az összes ilyen fickók aztán veszni és ők sodródás ki, és esik le. Tehát szeretnénk, hogy győződjön meg arról, hogy ahelyett, hogy szeretnénk fenntartani a linket a többit. Fejünk mutató, amely rámutat, hogy az első elemet a listában. Ez olyan, mint egy kötél rögzítése az első ember. Mit érdemes csinálni, ha szabad egy lista van - Ha azt szeretnénk felszabadítani az első elemet az első, akkor egy ideiglenes pointer amely rámutat arra, hogy függetlenül az első elem. Szóval az ideiglenes pointer mutat itt. Így van a hold az első csomópontot. És aztán, mivel tudjuk, hogy az első csomópont fog felszabadulni, akkor tudjuk mozgatni ezt a kötelet, ez a horgony, a fejünk, ténylegesen mutasson függetlenül elsőt mutat. Szóval ez a fej valóban rámutat a második elem most. Most hagyjuk szabadon bármit tárolt temp, és így tudjuk törölni, hogy anélkül, hogy veszélyeztetné az összes többi csomópontja a listában. Egy másik módja, hogy meg tudná csinálni ez lehet minden alkalommal, amikor csak kiszabadítani az utolsó elem a lista mert ők garantáltan nem kell mutatott semmit. Szóval, akkor csak ez az egy szabad, akkor szabad ezt, akkor szabad ezt. Ez biztosan működik, de egy kicsit lassabb, mert a természet a kapcsolt listák nem tudjuk, csak azonnal ugrik az utolsó. Meg kell bejárására minden elem a láncolt lista és ellenőrizze, hogy ez az egyik mutató NULL, ellenőrizze minden alkalommal, majd ha egyszer elérjük a végét, majd szabad ezt. Ha úgy döntesz, hogy nem ezt a folyamatot, akkor ténylegesen ellenőrző itt, ellenőrzés itt, majd ellenőrzés itt, felszabadítva azt, akkor megy vissza, ellenőrzés itt, ellenőrzés itt, megszabadítva azt, ellenőrzés ide, majd felszabadítja azt. Ez tart egy kicsit több időt. Igen. 

[Hallgató] lenne lehetséges, hogy a csatolt lista, amely tárolja a kilépési mutató a vége? Ez biztosan lehetséges. Ahhoz, hogy ismételje meg a kérdést, lehetséges, hogy egy láncolt lista szerkezete úgy, hogy van egy mutató mutat a végén a láncolt lista? Azt mondanám, hogy ez lehetséges, és minden alkalommal, amikor be valamit a csatolt lista meg kellett volna frissíteni, hogy a mutató és ilyesmik. Ha lenne egy csomópont * farok, például. De ha te végrehajtása ezt a funkciót, meg kell gondolni a kompromisszumok, mint hányszor fogok, hogy iterációjával át ezt, Mennyire nehéz lesz nyomon követni a farok, valamint a fej csakúgy, mint az én iterator, és ilyesmik. Van, hogy a -? >> [Hallgató] Igen. Ez lehetséges, de tekintve a tervezési döntések, meg kell mérlegelni a lehetőségeket. 

Itt van egy csontváz a kódot, amely lehetővé teszi, hogy szabadon minden elem egy láncolt lista. Ismét, mivel én vagyok iterációjával egy láncolt lista, megyek, hogy szeretne valamilyen kurzor vagy iterator. Mi iterációjával amíg a kurzor a NULL. Nem akarja megismételni, ha a kurzor NULL mert ez azt jelenti, hogy nincs semmi a listán. Szóval akkor itt vagyok, hogy egy ideiglenes csomópont * mutat, amit én figyelembe véve az első a listámon, aztán mozgatni a kurzort előre 1, majd szabadon bármi volt az ideiglenes tárolására. 

Most jön illesztették linkelt listákat. Van három csomópont az én linkelt listán, és menjünk az egyszerű esetet ha azt akarjuk, hogy helyezzen be egy másik csomópont a végén a láncolt lista. Ehhez minden tennénk is szeretnénk áthalad megtalálni ahol a jelenlegi vége kapcsolódó lista, így bármelyik csomópont mutat NULL - hogy ez egy - majd azt mondják, valóban, ez nem lesz az utolsó csomópont; mi tényleg megy, hogy egy másik. Szóval mi lenne ez a jelenlegi két pont között, amit mi behelyezése. Tehát most ez a vörös ember itt lesz az utolsó csomópont a láncolt lista. És így a jellemző az utolsó csomópont a láncolt lista, hogy mutat NULL. Akkor mit kellene tennie, hogy állítsa vörös fickót mutatót NULL. Tessék. 

De mi van, ha azt akartuk, hogy helyezzen be egy csomópont között, a második és a harmadik? Ez az ember nem olyan egyszerű, mert azt szeretnénk, hogy győződjön meg arról, hogy nem elengedni bármelyik csomópont a mi láncolt lista. Amit kellett volna tennie, hogy győződjön meg arról, hogy mi lehorgonyozni magunkat mindegyik. Például, hívjuk ezt a második. Ha azt mondta, a második most mutat ez az új és csak tett egy mutatót ott, akkor az azt eredményezné, hogy ez a fickó, hogy vereség mert nincs olyan a linket neki. Ehelyett - Majd felhívni újra. Elnézést a művészi képességeit. Tudjuk, hogy nem csak a közvetlen kapcsolatot a 2 az újat. Meg kell bizonyosodnunk arról, hogy mi tartsa be az utolsó. Amit érdemes tennie, hogy egy ideiglenes pointer Az elem fog csatolják be. Akkor van egy ideiglenes pointer ott. Mivel tudjuk, hogy ez a harmadik egy tartják számon, 2 most összekapcsoljuk a újat. És ha ez az új vörös fickó lesz a 2 és 3 közötti, akkor mi az, hogy a srác mutató fog mutatni? >> [Hallgató] Temp. Temp. Igen. Tehát ez a vörös fickó következő érték lesz hőm. Amikor illesztették linkelt listákat, láttuk, hogy tudnánk könnyen hozzá valamit a végén létrehoz egy ideiglenes tömb, vagy ha azt akartuk, hogy adjunk valamit a közepén a tömb, akkor ez, hogy egy kicsit több csoszogó körül. Ha szeretné, például, van egy rendezett láncolt lista, akkor meg kell, hogy milyen mérjük a költségeit és előnyeit, hogy a mert ha azt szeretnénk, hogy a rendezett tömbben, ami azt jelenti, hogy minden alkalommal, amikor be bele, ez megy, hogy egy kicsit több időt. Azonban, ha azt szeretnénk, hogy később, ahogy meg fogjuk találni mi szeretnénk, keresés egy láncolt lista, akkor lehet, hogy könnyebb, ha tudod, hogy minden rendben van. Tehát érdemes mérlegelni a költség-haszon e. 

Egy másik módja annak beilleszteni a csatolt lista szúrni a legelején egy listát. Ha döntetlen a horgonyt itt - ez a mi fej - majd még ezek az emberek kapcsolódnak, és akkor van egy új csomópontot kell illeszteni a elején, akkor mi is akarunk csinálni? Mi lenne a baj, csak azt akarom, hogy összekapcsolja a piros a kék, mert ez az első? Mi lenne itt? Mind a három fog eltévedni. Tehát nem akarok csinálni. Ismét megtanultuk, hogy mi szükség van valamilyen ideiglenes pointer. Nézzük úgy dönt, hogy egy átmeneti pont ezt a fickót. Akkor mi lehet a kék egy pontot az ideiglenes , majd a piros pont a kék. Az ok, amiért én vagyok a nép itt, mert tényleg meg akarjuk megjeleníteni gazdaságot, hogy az emberek, és gondoskodjanak arról, hogy van egy linket nekik mielőtt elengedjük a másik kezét, vagy valami ilyesmi. 

Most, hogy van értelme a kapcsolt listák - hogyan lehet létrehozni egy láncolt lista és létrehozza a struktúrákat hogy álló a típus definíció egy csomóponthoz majd ügyelve arra, hogy van egy mutatót a fejét, hogy a csatolt lista - ha már van, hogy, és tudjuk, hogyan kell bejárására át egy tömb, eléréséhez különböző elemek, tudjuk, hogyan kell beszúrni, és tudjuk, hogyan kell kiszabadítani őket, akkor kerülhet helyesírási hibák. Mint mindig, van egy szakasza a kérdés, hogy kap amivel működő kapcsolt listák és a különböző struktúrák, mint a sorok és a halom. Akkor beköltözni helyesírási hibák. 

Helyesírási hibák vannak a terjesztési kódját pár fájlok fontos. Először észre, hogy itt van ez a Makefile itt, amit nem igazán találkozott korábban. Ha benézett a pset5 mappában, azt veszi észre, hogy van egy. H fájl, akkor két. c fájlokat. Mi ez a Makefile csinál előtt van, mi lenne csak írja teszi majd a program nevét és akkor látnánk mindezen érveket és zászlók telt el a fordító. Mi a Makefile tesz, lehetővé teszi számunkra, összeállítása több fájl egyszerre és add meg a zászlókat, hogy szeretnénk. Itt csak látni, hogy van egy header file itt. Akkor tulajdonképpen két forrás fájlokat. Van speller.c és dictionary.c. Azt várjuk, hogy a Makefile, ha akarod. Figyeljük meg, hogy itt, ha adja a tiszta, akkor mit csinál valójában eltávolít valamit ez a mag. Ha van egy szegmentációs hiba, alapvetően kapsz egy core dump. Tehát ez a csúnya kis fájl jelenik meg a könyvtárban az úgynevezett mag. Azt akarja, hogy távolítsa el, hogy annak érdekében, hogy tiszta. Ez eltávolít minden exe fájlokat és. O fájlokat. 

Vessünk egy pillantást a dictionary.h. Ez azt mondja, hogy kinyilvánítja a szótár működését. Van egy maximális hossza minden szót a szótárban. Azt mondják, hogy ez lesz a lehető leghosszabb szót. Ez a hossz 45. Szóval nem megy, hogy olyan szavakat, amelyek meghaladják azt hosszát. Itt már csak a funkciót prototípusok. Nekünk nem kell a tényleges megvalósításához, mert ez az, amit mi csinál erre Pset. De mi ez nem az, mivel van dolgunk nagyobb fájlokat ide és funkcionalitás nagyobb léptékben, akkor hasznos lehet egy. h fájlban annak érdekében, hogy valaki olvassa vagy használja a kód is érti, mi folyik itt. És talán akarnak végrehajtani megpróbálja, ha nem hash táblák, vagy fordítva. Akkor azt mondanám, a terhelés függvényében, a tényleges megvalósítás fog különbözni, de ez prototípus nem fog változni. Itt van ellenőrizni, amely igazat ad vissza, ha az adott szó szerepel a szótárban. Aztán ott van teher, amely lényegében vesz a szótár fájl és utána tölti be néhány adat struktúra. Van mérete, amely, ha hívják, visszatér a méret a szótár, hány szavak benne tárolt, majd kirak, amely felszabadítja az összes memóriát lehet, hogy felvesszük miközben a szótárban. 

Vessünk egy pillantást dictionary.c. Látjuk, hogy úgy néz ki, nagyon hasonlít a dictionary.h, kivéve most már csak az összes ilyen Todos benne. És ez a munkád. Végül, akkor meg kell kitöltésével speller.c az összes ezt a kódot. Dictionary.c, futás közben, nem igazán fog csinálni semmit, így néz felé speller.c hogy a tényleges megvalósítás a helyesírás-ellenőrző. Annak ellenére, hogy nem lesz semmilyen szerkesztési ezt a kódot, ezért fontos, hogy olvasni, megérteni, ha a terhelés nevezzük, amikor hívom ellenőrzés, Csak megérteni, feltérképezni ki, látom, hogy a funkció. Látjuk, hogy ez ellenőrzi a helyes használat. Lényegében, ha valaki fut helyesírás, ez azt jelzi, hogy ez nem kötelező nekik átadni a szótárban fájlt, mert ott lesz az alapértelmezett szótár fájlt. És akkor át kell adni a szövegben, hogy a helyesírás-ellenőrizni. rusage foglalkozik időben, mert egy része a Pset amelyhez elintézem később nem csak kapok egy működő helyesírás-ellenőrző munka de valójában egyre, hogy gyors lesz. És akkor ez az, ahol rusage fog bejönni Itt látjuk az első hívást az egyik dictionary.c fájlokat, ami terhelést. Load vissza, igaz vagy hamis - igaz upon siker, hamis meghibásodása. Tehát, ha a szótár nincs betöltve, akkor a speller.c vissza fog térni az 1. és kilép. De ha ez nem teher helyesen, akkor ez lesz a folytatáshoz. Folytatjuk, és látunk néhány fájl I / O itt hová megy, hogy foglalkozik megnyitja a szöveges fájl. Tessék, hogy ez mire jó a helyesírás-ellenőrzések minden egyes szó a szövegben. Tehát mi speller.c csinál itt van iterációjával felett minden egyes szava a szöveges fájl majd ellenőrzi őket a szótárban. Itt van egy logikai hibásan írt, hogy látni fogja, ha ellenőrzést visszaadja igaz-e vagy sem. Ha a szó valóban a szótárban, akkor ellenőrzést vissza igaz. Ez azt jelenti, hogy a szó nem hibásan. Szóval elírt hamis lenne, és ezért mi a bumm ott a jelzés. Mi folyamatosan megy, és akkor nyomon követi, hogy hány elgépelt szavakat vannak a fájlban. Ez folytatódik, és bezárja a fájlt. Aztán itt, Tára hány elgépelt szavak voltak. Ez kiszámítja, hogy mennyi idő telt betölteni a szótárba, , hogy mennyi idő telt, hogy ellenőrizze azt, , hogy mennyi idő telt számítani a méret, amely, mint megyünk tovább, legyen nagyon kicsi, majd, hogy mennyi idő telt, hogy kirak a szótárba. Itt fönt látjuk a hívás, hogy kirak itt. Ha ellenőrizze a méret itt, akkor azt látjuk, hogy itt az a hívás, ha a méret határozza meg a méretét a szótár. Félelmetes. 

A mi feladatunk ezen Pset hogy végrehajtsa terhelés, amely betölti a szótár adatstruktúra - Bármelyiket is választja, legyen az egy hash tábla vagy egy próbát - A szavak a szótárban fájlt. Akkor mérete, amely visszaadja a szavak száma a szótárban. És ha végre terhelés olyan intelligens módon, akkor a mérete legyen elég egyszerű. Akkor is ellenőrizni, amely ellenőrizni fogja, hogy az adott szó szerepel a szótárban. Tehát speller.c halad egy string, és akkor kell ellenőrizni, hogy ez a húr belül található a szótárban. Figyeljük meg, hogy mi általában szabványos szótárak, de ebben Pset alapvetően bármely szótár telt bármilyen nyelven. Tehát nem csak feltételezhetjük, hogy a szó THE belül van. A szó FOOBAR lehetne meghatározni egy bizonyos szótárban, hogy mi megy be És akkor már ürítő, amely megszabadítja a szótár a memóriából. 

Először is, szeretném, hogy menjen át a hash tábla módszer arról, hogyan lehet végrehajtani mind a négy funkció, aztán megyek át a módszerrel próbálkozik, hogy hogyan hajtsák végre a négy funkció, és a végén beszélni néhány általános tipp, ha követsz a Pset , és azt is, hogyan lehet, hogy képes legyen használni az Valgrind, hogy ellenőrizze a memóriavesztés. 

Menjünk be a hash tábla módszer. A hash tábla tartalmaz egy listát a vödörben. Minden érték, minden szó, fog belemenni egy ilyen vödörben. A hash tábla ideális egyenletesen osztja el az összes ezeket az értékeket, hogy te vagy halad és majd feltölti azokat a vödörbe, hogy minden markolókanál mintegy azonos számú érték benne. A szerkezet egy hash tábla, van egy sor kapcsolódó listák. Mit csinálunk, amikor elmegyünk egy érték, akkor ellenőrizze, ha ez az érték tartozik, amely markolókanál tartozik, majd helyezze be a linkelt lista társított vödör. Tessék, mi van egy hash függvény. Ez egy int hash táblában. Így az első vödör, minden egész 10 alá megy az első kukába. Bármely egészek 10 feletti, de 20 alatti tovább a második, és majd így tovább és így tovább. Számomra minden vödör képviseli ezeket a számokat. Azonban, mondom volt átadni 50, például. Úgy tűnik, hogy az első három tartalmaz egy sor tíz számok. De azt akarom, hogy a hash tábla, hogy minden fajta egészek, így aztán azt is, hogy kiszűrje az összes szám meghaladta a 30 az utolsó vödör. És így akkor az azt eredményezné, hogy egyfajta aszimmetrikus hash tábla. Ismét hangsúlyozzuk, a hash tábla csak egy tömb kanalak ahol minden vödör a linkelt lista. És így, hogy meghatározza, ahol minden érték megy, ami vödör megy bele, fogsz szeretnénk mi úgynevezett hash függvény hogy vesz egy értéket, majd azt mondja, ez az érték felel meg egy bizonyos vödör. Szóval fel a fenti példában a hash függvény vett minden értéket. Azt ellenőrizte, hogy ez kevesebb, mint 10. Ha ez, akkor helyezze be az első kukába. Ez ellenőrzi, hogy ez kevesebb, mint 20, mondja a második, ha igaz, ellenőrzéseket, ha ez kevesebb, mint 30, és mondja a harmadik vödör, majd minden más, csak esik a negyedik vödröt. Szóval, ha van értéke, akkor a hash függvény helyezi ezt az értéket a megfelelő kukába. A hash függvény alapvetően meg kell tudni, hogy hány vödör van. A hash tábla mérete, száma vödrök van, ez lesz a fix szám csak rajtad áll, a te döntésed, de ez lesz a rögzített szám. Tehát a hash funkció támaszkodva azt, hogy melyik markolókanál minden kulcsfontosságú megy oly módon, hogy ez egyenletesen elosztva. Hasonló a mi végrehajtásához kapcsolódó listák, most minden csomópont a hash tábla valóban lesz egy char típusú. Tehát van egy char tömb nevű szót, és majd egy másik mutatót a következő csomópont, ami teljesen érthető, mert ez lesz a csatolt lista. Emlékszel, amikor már kapcsolódik listákat, csináltam egy node * nevű fej amit mutat az első csomópont a láncolt lista. De mi hash tábla, mert több kapcsolódó listákat, amit mi akarunk, az azt akarjuk, hash tábla, mint a "Mi az a vödör?" A vödör csak egy lista csomópont mutatók, és így minden elem a vödörben ténylegesen mutat a megfelelő láncolt lista. Ha vissza kíván térni a sematikus, akkor láthatjuk, hogy a vödröket maguk a nyilakat, nem tényleges csomópont. Az egyik lényeges tulajdonsága hash függvények, hogy ők determinisztikus. Ez azt jelenti, hogy amikor Ön hash a 2-es szám, az mindig vissza ugyanazt vödröt. Minden egyetlen érték, hogy bemegy a hash függvényt, ha járunk el, van, hogy az azonos index. Tehát a hash függvény az index a tömb ha ez az érték tartozik. Ahogy már korábban említettem, a számos vödrök rögzített, és így az index, hogy vissza kell, hogy legyen kevesebb, mint a vödrök de nagyobb mint 0. Az ok, amiért van hash függvények helyett csak egyetlen láncolt lista vagy egy egységes tömb, hogy azt akarjuk, hogy képes ugrani, hogy egy bizonyos szakasz legegyszerűbben ha tudjuk, hogy a jellemző érték - ahelyett, hogy kereshet a teljes egész szótárt, hogy képes ugrani egy bizonyos részét is. A hash függvény figyelembe kell venni, hogy ideális esetben Minden vödör körülbelül azonos számú kulcs. Mivel a hash tábla egy sor kapcsolódó listák akkor a kapcsolt listák maguk megy, hogy több mint egy csomópont. Az előző példában, két különböző szám, annak ellenére, hogy nem voltak azonos, amikor hashelt, azt vissza ugyanazt az index. Tehát, ha van dolgunk szavakkal, egy szóval, ha hashelt lenne azonos hash értékét egy másik szót. Ezt hívjuk mi az ütközés, ha van egy csomópont, hogy amikor hashelt, a csatolt lista, hogy a vödör nem üres. A technika, amit hívni van lineáris szondázás, ahová bemegy a kapcsolódó listát, majd találni, ahol be szeretné szúrni, hogy a csomópont mert van egy ütközés. Láthatjuk, hogy lehet egy trade-off itt, ugye? Ha van egy nagyon kis hash tábla, egy nagyon kis számú vödröket, akkor fogsz sok ütközések. De aztán, ha csinál egy nagyon nagy hash tábla, akkor valószínűleg megy minimalizálása ütközések, de ez lesz egy nagyon nagy adatszerkezet. Ott lesz trade-off vele. Tehát, ha csinálsz a Pset, próbáld meg lejátszani körül között lehet, hogy egy kisebb hash tábla de tudta, hogy ez fog tartani egy kicsit tovább, hogy keresztezik a különböző elemek E linkelt listák. 

Mi terhelést fog tenni a iterációkhoz minden szót a szótárban. Ez halad egy mutatót a szótár fájlt. Szóval megy, hogy kihasználják a fájl I / O funkciókat, amelyekhez elsajátítani pset4 és iterációkhoz minden szót a szótárban. Azt akarom, hogy minden szót a szótárban, hogy legyen egy új csomópontot, és fogsz helyezni mindenki azon csomópontok belsejét a szótár adatszerkezet. Ha kapsz egy új szó, tudod, hogy ez fog válni a csomópont. Szóval lehet menni rögtön malloc csomópont pointer minden új szót, hogy van. Itt hívom én node pointer new_node és én mallocing mi? Akkora, mint egy csomópont. Aztán, hogy olvassa el a tényleges szöveg fájlból, mert a szótárt ténylegesen tárolt egy szót, majd egy új sort, amit kihasználhatják a függvény fscanf, amely fájl a szótárban fájlt, hogy mi telt el, így megkeresi a fájlt a húr, és helyek, húr az utolsó érv. Ha visszaemlékeznek vissza az egyik előadások, amikor átmentünk és milyen hámozott rétegek vissza a CS50 könyvtár, láttunk végrehajtásának fscanf ott. Való visszatéréshez fscanf, megvan a fájl, hogy mi olvasása, keresünk egy string, hogy a fájl, majd mi helyezze be Itt van new_node-> szót, mert new_node egy csomópont mutató, nem tényleges csomópont. Akkor mondok new_node, szeretnék menni a csomópont, hogy ez mutat majd rendelnie az adott értéket szót. Azt akarjuk, hogy vigye ezt a szót, és helyezze be a hash tábla. Ismerd fel, hogy mi történik new_node egy csomópont pointer mert megyünk akarom tudni, hogy mi a címe, hogy a csomópont amikor helyezze be, mert a szerkezet a csomópontok maguk az a struct, hogy van egy mutató egy új csomópontot. Szóval akkor mi a címe, hogy a csomópont fog mutatni? Ez a cím lesz new_node. Van ennek értelme, miért tesszük new_node csomópont * szemben a csomópont? Oké. Van egy szó. Ez az érték new_node-> szó. Ez tartalmazza a szót a szótárban, hogy szeretnénk bemenet. Szóval, amit akarok, azt akarjuk, hogy hívja a hash függvényt e húr mert a hash függvény egy string, majd visszaadja nekünk egy egész szám, amennyiben az egész az index, ha hash tábla az adott index jelzi, hogy vödör. Azt akarjuk, hogy ezt a index és aztán megy, hogy az index a hash tábla majd, hogy a láncolt lista, hogy helyezze be a csomópont a new_node. Ne feledje, hogy viszont úgy dönt, hogy tegye be a csomópont, hogy ez a közepén, ha szeretné rendezni, hogy vagy az elején vagy a végén, csak győződjön meg róla, hogy az utolsó csomópont mindig mutat NULL mert ez az egyetlen módja, hogy tudjuk, hol az utolsó eleme a kapcsolt lista. 

Ha a méret egy egész szám, amely képviseli a szavak száma a szótárban, majd az egyik módja ennek az, hogy amikor Méret hívják megyünk keresztül minden eleme a hash tábla majd halad végig az összes láncolt lista a hash tábla majd kiszámítja a hosszát, hogy növeljük a számláló 1 1-gyel. De minden alkalommal, hogy a méret a neve, ez fog hosszú időt vesz igénybe mert mi lesz lineárisan tapintási minden egyes láncolt lista. Ehelyett lesz sokkal könnyebb, ha nyomon követheti, hogy hány szavak telt be Tehát, ha tartalmazza a számlálót belül a terhelés függvényében , hogy a frissítések amennyiben szükséges, akkor számláló, ha meg azt, hogy egy globális változó, képes lesz elérhető a méret. Szóval, milyen méretű egyszerűen tennie egy sorban, csak vissza a számláló értéke, a méret a szótár, amit már foglalkozott a terhelés. Ez az, amit gondoltam, amikor azt mondtam, ha végre terhelést segítőkész módon, akkor Méret lesz elég egyszerű. 

Tehát most jutunk, hogy ellenőrizze. Most dolgunk szavakat a bemeneti szöveges fájl, és így fogunk is ellenőrzi, hogy az összes ilyen input szavak valójában a szótárban vagy nem. Hasonló a tülekedés, azt akarjuk, hogy a kis-nagybetű érzékenységet. Azt szeretnénk, hogy győződjön meg arról, hogy minden szót telt el, annak ellenére, hogy kis-és nagybetűket, ha hívják zsinórral összehasonlítás, egyenértékűek. A szavak a szótárban szöveges fájlokat valójában csupa kisbetűvel. A másik dolog, hogy meg lehet feltételezni, hogy minden szót telt el, minden húr, lesz alfabetikus vagy aposztrófok tartalmaznak. Aposztrófok lesznek érvényesek szava a szótárban. Tehát, ha egy szót aposztróf S, ez egy valódi legitim szót a szótárban ez lesz az egyik a csomópontok a hash táblában. Ellenőrizze, működik, ha a szó létezik, akkor van, hogy a mi hash táblában. Ha a szó szerepel a szótárban, akkor minden a szavak a szótárban van a hash tábla, úgyhogy keressük ezt a szót a hash táblában. Tudjuk, hogy mivel mi végre a hash függvény oly módon, hogy minden egyes egyedi szót mindig hashelt, hogy ugyanazt az értéket, akkor tudjuk, hogy ahelyett, hogy a kereső segítségével a teljes egész hash tábla, tudjuk ténylegesen megtalálja a láncolt lista, hogy ez a szó kell tartoznia. Ha ez a szótárban, akkor ez az, hogy a vödör. Mit tehetünk, ha a szó a neve a string telt el, tudjuk csak hash ezt a szót, és nézd meg a láncolt lista az érték hash tábla [hash (szó)]. Onnan, hogy mit tehetünk, hogy van egy kisebb részhalmaza csomópontok keresni ezt a szót, és így tud elmozdulni a linkelt lista segítségével például a korábban a walkthrough, majd hívja húr összehasonlítani fel a szót, ahol a kurzor mutat, ezt a szót, és meglátjuk, hogy ezeket összehasonlítani. Attól függően, hogy az út, hogy megszervezi a hash függvény, ha ez válogatni, akkor lehet, hogy return false egy kicsit korábban, de ha ez rendezetlen, akkor szeretné, hogy továbbra is áthaladó át a láncolt lista amíg meg nem találja az utolsó elem a lista. És ha még mindig nem találta meg a szót, mire elérte a végén a láncolt lista, azt jelenti, hogy a szó nem szerepel a szótárban, és hogy szó érvénytelen, és az ellenőrzést vissza kell hamis. 

Most jön, hogy kirak, ahol szeretnénk felszabadítani az összes csomópont általunk malloc'd, így mentes minden csomópont belsejében a hash tábla. Fogunk szeretnénk iterációkhoz összes kapcsolódó listák és mentes minden csomópont ebben. Ha megnézzük a fenti, walkthrough, hogy a példát, ahol szabad a láncolt lista, akkor majd szeretnénk megismételni ezt a folyamatot minden egyes eleme a hash táblában. És én megyek át ezt a vége felé a walkthrough, de Valgrind olyan eszköz, ahol láthatjuk, ha helyesen felszabadult minden csomópont, amit malloc'd vagy bármi mást, amit malloc'd, bármely más mutató. Szóval ez hash táblák, ahol van egy véges számú vödrök és egy hash függvény, hogy lesz egy értéket, majd ezt az értéket rendelni egy bizonyos vödör. 

Elérkeztünk próbál. Megpróbálja a fajta néz ki, és én akkor is kihúz egy példát. Alapvetően, ha egy egész sor lehetséges betűket, majd amikor te építése egy szót, E levél köthető a szótár a lehetőségek széles körét. Néhány szó kezdeni C, de majd folytassa A, de mások folytatódik O, például. A Trie egy módja láthatóvá az összes lehetséges kombinációját ezeket a szavakat. A Trie lesz nyomon követni a betűkből alkotó szavak, leágazás le, amikor szükséges, amikor az egyik betű követheti egy többszörös a betűk, és a végén azt mutatják, minden ponton, hogy ez a szó érvényes-e vagy sem mert ha helyesírás szó MAT, MA nem hiszem, egy érvényes szó, de MAT van. És így a Trie, ez jelzi, hogy miután MAT hogy ez valójában egy érvényes szó. Minden node a mi Trie ténylegesen megy tartalmaznak egy sor csomópont mutatók, és fogunk is, különösen, 27 e csomópont mutatók, 1 minden betű az ábécé, valamint az aposztróf karakter. Minden elem, hogy a tömb maga fog mutatni egy másik csomópont. Tehát, ha a csomópont NULL, ha nincs semmi után, akkor tudjuk, hogy nincs további betű ezt a szót sorrendben. De ha a csomópont nem NULL, az azt jelenti, hogy több betű e levélben sorrendben. És akkor emellett minden csomópont jelzi, hogy ez az utolsó karakter egy szó, vagy sem. 

Menjünk bele egy példa Trie. Először is van hely a 27 csomópontok ezt a tömböt. Ha van a szó BAR - Ha van a szó BAR és szeretném beszúrni, hogy az, Az első levél B, tehát ha a Trie üres, B a második betű az ábécé, így fogom választani, hogy ezt itt most ezt index. Megyek, hogy B itt. B lesz egy csomópont, amely kijelöli egy másik tömb összes lehetséges karakter ami után következik a levél B. Ebben az esetben, én foglalkozik a szó BAR, így megy itt. Után egy, már az R betű, így aztán most egy pontot saját kombináció, majd R itt lesz. BAR egy teljes szó, így aztán megyek a K pont egy másik csomópont azt mondja, hogy ez a szó érvényes. Ez a csomópont is megy, hogy egy sor csomópontok, de ezek lehetnek NULL. De alapvetően, akkor továbbra is így. Ez lesz egy kicsit világossá, ha elmegyünk egy másik példát, tehát csak medve velem van. Most már BAR belül a szótárban. Most azt mondom, hogy a szó BAZ. Kezdjük a B, és már van B, mint az egyik betű, ami a mi szótárban. Ez követte A. Van A már. De aztán ehelyett, van Z következő. Tehát egy elem a tömbben lesz Z, így aztán, hogy az egyik fog mutatni egy másik érvényes végére a szó. Látjuk tehát, hogy ha folytatódik a B, majd az A, két különböző lehetőségek jelenleg van a szótárban a szavakat, hogy kezdődik a B és A. Mondja el akartuk hogy beillessze a szót FOOBAR. Akkor mi lenne, hogy egy beléptetés F. F egy olyan csomópont, amely arra utal, hogy az egész tömb. Meg fogja találni O, menj O, O majd összekapcsolja egy egész listát. Szeretnénk, hogy a B, majd folytassa, mi volna egy majd R. Akkor FOOBAR halad egészen addig, amíg FOOBAR a helyes szót. És akkor ez lenne érvényes szó. Most mondjuk a következő szó a szótárban valójában a szó FOO. Azt mondanám, F. Mi következik F? Igazából már van egy hely O, így fogom folytatni. Nem kell, hogy egy újat. Tovább. FOO egy érvényes szó ebben a szótárban, így aztán megyek tüntetni hogy ez érvényes. Ha abbahagyom a sorozatot ott lenne helyes. De ha továbbra is a szekvenciát FOO le a B és most volt FOOB, FOOB nem egy szó, és ez nem tüntette fel érvényes. Egy Trie, akkor minden csomópont jelzi, hogy ez egy érvényes szó vagy sem, és azután minden csomópont is van egy sor 27-csomópont mutatók hogy akkor pont a csomópontokra magukat. 

Itt van egy módja annak, hogyan kívánja meg ezt. Azonban, csakúgy, mint a hash tábla például, ha volt egy node * fej jelzi a kezdetét a láncolt lista, mi is szeretne majd valamilyen módon tudni, ha az elején a mi Trie van. Egyesek megpróbálja fák, és ez az, ahol gyökér származik. Így szeretnénk a gyökér a fa, hogy győződjön meg arról, hogy mi maradjon földelt hogy ahol a mi Trie van. Már a fajta odament ahogy tudott gondolni betöltődik minden szót a szótárba. Lényegében minden szót fogsz szeretné navigálhat keresztül Trie és annak tudatában, hogy minden eleme a gyerekek - mi neveztük gyerekek ebben az esetben - felel meg egy másik levelet, fogsz kívánja ellenőrizni ezeket az értékeket meg, hogy az adott index, amely megfelel a levelet. Szóval gondoltam egészen vissza Caesar és Vigenère, tudva azt, hogy minden egyes levél tudsz ilyen térképet egy betűrendes index, határozottan A-Z-ig lesz elég könnyű leképezni egy betűrendes levél de sajnos, aposztrófok is elfogadott karaktert szavakat. Nem vagyok még biztos benne, mi az ASCII érték, így, hogy ha meg akarja találni az index eldönteni, hogy azt akarja, hogy lehet akár az első vagy az utolsó, akkor van, hogy egy kemény kódolt csekket, hogy majd fel, hogy az index 26, például. Szóval akkor ellenőrzik az értéket gyermekeknek [i] ahol [i] megfelel bármit írni ha már itt vagy. Ha ez NULL, ami azt jelenti, hogy jelenleg nem lehetséges betű ebből a korábbi sorozat, így fogsz akar malloc és egy új csomópont, és hogy a gyerekek [i] pont azt így létre - amikor ki egy levelet a téglalap - hogy a gyermekek nem NULL és pont abba az új csomópontot. De ha ez nem NULL, mint a mi példányban FOO amikor már FOOBAR, továbbra is, és mi soha nem, hogy egy új csomópont, hanem csak a beállítás is_word true a végén ezt a szót. 

Tehát, mint korábban, mert itt van dolgunk, minden betű egy időben, ez lesz könnyebb az Ön számára a méret, ahelyett kiszámításához és megy az egész fát, és kiszámítja, hogy hány gyermek nem tudom majd ágazik le, eszébe jutott, milyen sokan vannak a bal oldalon és a jobb oldalon és a dolgok, mint, hogy ez lesz sokkal könnyebb az Ön számára ha csak nyomon követheti, hogy hány szót te kiegészítve ha dolgunk terhelést. És akkor így mérete csak vissza egy globális változó méretben. 

Most jön, hogy ellenőrizze. Ugyanaz a szabványok, mint korábban, ha azt akarjuk, hogy lehetővé teszi a kis-nagybetű érzékenységet. Valamint, azt feltételezzük, hogy a húrok csak betűk, vagy a aposztróf mert a gyerekek egy tömb 27-hosszú, így minden az ábécé betűit és az idézőjel. Mert ellenőrizze, milyen akar majd tennie, hogy akar majd kezdeni a gyökér mert a gyökér fog mutatni egy tömb, amely tartalmazza az összes lehetséges kezdő betűit egy szót sem. Fogsz kezdeni ott, és akkor megy, hogy ellenőrizze ezt az értéket NULL vagy nem, mert ha az érték NULL, hogy azt jelenti, hogy a szótár nincs meg értékek tartalmazó e levél az adott sorrendben. Ha ez NULL, akkor ez azt jelenti, hogy a szó el van írva, azonnal. De ha ez nem NULL, akkor lehet folytatni, azt mondják, hogy az első betű egy lehetséges első betűjét egy szó, így most szeretném, hogy ellenőrizze, a második levél, hogy a sorozatot, ez az én szótárban. Szóval megyek, hogy az index a gyermekek az első csomópont és ellenőrizze, hogy a második levél létezik. Akkor ismételje meg ezt a folyamatot, hogy ellenőrizze, hogy a sorrend érvényes-e vagy sem az Ön Trie. Ha a csomópont gyermek abban indexpont NULL, tudod, hogy ez a sorozat nem létezik, de ha elérjük a végét, a szó, amit viszünk, akkor ellenőrizni kívánt most, hogy befejeződött ez a sorozat és megállapította, hogy az én Trie az, hogy a szó érvényes, vagy nem? És akkor azt szeretnénk, hogy ellenőrizze, hogy, és ez az, amikor, ha már megállapította, hogy egymás után, akkor szeretné ellenőrizni, hogy ez a szó érvényes-e vagy sem mert emlékezz vissza az előző esetben, hogy én rajzoltam, ahol volt FOOB, hogy érvényes volt szekvenciát találtunk, de nem volt tényleges érvényes szót magát. 

Hasonlóképpen, kirak a próbálkozás szeretné, hogy kirak az összes csomópont a Trie. Bocsánat. Hasonló a hash táblák, ahol ürítő is megszabadult az összes csomópont, A próbálkozás szeretnénk is ingyenes az összes csomópont. Eltávolítása ténylegesen működni legkönnyebben alulról felfelé mert ezek alapvetően kapcsolódó listákat. Tehát szeretnénk, hogy győződjön meg arról, hogy ragaszkodnak az összes értékek és szabad mindegyikük kifejezetten. Mit fogsz akarsz csinálni ha dolgozik egy Trie az, hogy utazni az aljára, és szabad a lehető legalacsonyabb csomópont 1. majd menj fel az összes ilyen gyerek, majd szabad az összes ilyen, menj fel, majd ingyen, stb Olyan, mint foglalkozó alsó réteg az Trie 1. majd megy fel top miután felszabadította mindent. Ez egy jó példa arra, amikor rekurzív függvény jól jöhet. Miután kiszabadította az alsó réteg a Trie, akkor hívja kirak a többit, ügyelve arra, hogy minden szabad mini - Tudod milyen elképzelni, mint mini próbál. Szóval van a root itt. Én csak egyszerűsítse úgyhogy nem kell felhívni 26 őket. Szóval van ilyen, és akkor ezek képviselik szekvenciák szavak ahol ilyen kis körök betűk, amelyek érvényesek sorozatok leveleket. Folytassuk csak egy kicsit. Mit fogsz akarom ingyenes az alsó ide, majd szabad ezt majd szabad ez az alján, mielőtt szabad a felső egy ide mert ha szabad valamit a második szinten van, akkor tényleg megszűnne ez az érték itt. Ezért fontos az ürítő irányuló Trie, hogy győződjön meg arról, hogy szabad az alsó első. Mit érdemes tennie, azaz minden csomópont Azt akarom, hogy kirak az összes gyerek. 

Most, hogy ment át kirak a hash tábla módszer, valamint a Trie módszer, fogunk szeretnénk nézni Valgrind. Valgrind futtatja a következő parancsokat. Van valgrind-v. Te ellenőrzése minden szivárgást futtatásakor helyesírás adott a bizonyos szöveg mert Speller kell tennie egy szöveges fájl. Szóval Valgrind fut a program, megmondja, hogy hány bájt te kiosztott, hány bájt Ön felszabadult, és azt fogja mondani, hogy Ön felszabadította éppen elég vagy hogy nem elég szabad, vagy néha akkor is át-mentes, mint például az ingyenes egy csomópont, ami már felszabadult és így visszatér hibákat. Ha használja Valgrind, akkor kapsz néhány üzenetet azt jelzi, hogy már megszabadult vagy kevesebb, mint elég, éppen elég, vagy több, mint elégszer. 

Ennek részét képezi Pset, ez opcionális megtámadni The Big Board. De amikor dolgunk ezen adatszerkezetek ez a fajta szórakozás, hogy milyen gyorsan és mennyire hatékony az adatszerkezeteket lehet. Az Ön hash függvény eredménye a sok ütközés? Vagy adatok Méret igazán nagy? Vajon, hogy egy csomó időt, hogy áthalad? A napló helyesírás, kiadja mennyi időt használja betölteni, hogy ellenőrizze, hogy végezzen méret és kirakodásához, és így azokat a beírás a The Big Board, ahol versenyeznek az osztálytársaival és a személyzet egyes tagjait, hogy ki a leggyorsabb helyesírás-ellenőrző. Az egyik dolog, amit szeretnék megjegyezni, ami a hash táblák az, hogy van néhány nagyon egyszerű hash függvények, hogy mi lehetett gondolni. Például, ha van 26 vödröket, és így minden vödör megfelel az első betű egy szó, de ez fog eredményezni egy szép kiegyensúlyozatlan hash tábla mert van egy sokkal kevesebb szó, kezdődik az X-nél kezdődik, M, például. Az egyik módja annak, hogy megy a helyesírás is, ha azt szeretnénk, hogy az összes többi funkció le, akkor csak egy egyszerű hash függvény, hogy tudja, hogy a kód fut majd menj vissza, és változtassa meg a mérete a hash tábla és a meghatározás. Van egy csomó források az interneten hash függvények, és így ezen Pset Ön lehet, hogy a kutatás hash függvények az interneten néhány tippeket és ötleteket, amíg győződjön meg arról, hogy idézni, ahol kaptad. Szívesen nézni és értelmezni néhány hash függvényt, hogy megtalálja az interneten. Visszalépés az, hogy lehet látni, ha valaki használt Trie függetlenül attól, hogy végrehajtása gyorsabb, mint a hash tábla vagy sem. Küldheti a The Big Board többször. Ez rögzíti a legutóbbi bejegyzést. Szóval talán változtatni a hash függvényt, majd rájönnek, hogy ez valójában egy sokkal gyorsabb vagy sokkal lassabban, mint korábban. Ez egy kicsit szórakoztató módon. Mindig van 1 vagy 2 alkalmazottaknak, akik megpróbálják a lehető leglassabb szótár, annak érdekében, hogy mindig szórakoztató nézni. 

A forgalmi Pset is futtat helyesírás opcionális szótár majd a kötelező szöveges fájl. Alapértelmezésben futtatásakor helyesírás csak egy szöveges fájl, és nem adja meg a szótár, ez lesz használni a szótár szöveges fájl, a nagy 1 A cs50/pset5/dictionaries mappában. Ez az egyik, több mint 100.000 szó. Ők is egy kis szótár, amely jóval kevesebb szó hogy CS50 tett az Ön számára. Azonban, akkor nagyon könnyen, csak hogy a saját szótárba ha csak azt, hogy működik a kis példák - például, ha szeretné használni gdb, és tudod, hogy a specifikus értékek azt szeretné, hogy a hash tábla, hogy feltérképezzék a. Szóval lehet, hogy csak a saját szöveges fájl csak BAR, BAZ, FOO és FOOBAR, teszi, hogy egy szöveges fájl, elkülöníteni azokat egyenként 1 vonal, majd a saját szöveges fájl, a szó szoros értelmében csak olyan talán 1 vagy 2 szó úgy, hogy pontosan tudja, mi a kimenet legyen. Néhány minta szöveges fájlokat, hogy a The Big Board futtatásakor kihívást ellenőrizni fogja a Háború és béke, valamint a Jane Austen regény, vagy valami ilyesmi. Szóval, amikor kezdő, ez egy sokkal könnyebb, hogy a saját szöveges fájlok , amelyek csak egy pár szót vagy talán 10 így megjósolni, hogy mi az eredmény legyen majd ellenőrizze ellen, hogy így több ellenőrzött példát. És mivel mi dolgunk előrejelzésére és rajz dolgokat, Ismét szeretnék ösztönözni, hogy használja tollat ​​és papírt mert ez tényleg megy, hogy segítsen ez - rajz a nyilakat, hogy a hash tábla vagy hogyan Trie néz ki, amikor szabaddá valamit, ha a nyilak megy, Ön gazdaságot, hogy elég, látod a linkek eltűnnek alá tartozó, és a szakadékba a kiszivárgott memória. Ezért kérjük, próbálja meg felhívni a dolgokat, még mielőtt eljut kódot írni le. Döntetlen a dolgokat, úgy, hogy megértsék, hogyan mennek a dolgok a munka mert akkor én garantálom, hogy belefutsz kevesebb pointer muddles ott. 

Rendben van. Azt akarom, hogy szeretném, ha nagyon sok szerencsét ezzel Pset. Ez talán a legnehezebb. Így próbálja elindítani korán felhívni a dolgokat, rajzol dolgokat, és sok szerencsét. Ez volt Walkthrough 5. 

[CS50.TV]