ZAMYLA CHAN: Le të bëjmë një checker magji. Nëse keni hapur Shkruaj një fjalë, atëherë ju do të shihni se shumicën e funksionalitetit për duke kontrolluar një file teksti kundër një fjalor është bërë tashmë për ju. . / Speller, duke kaluar në një tekst fjalor paraqesë dhe pastaj një tjetër skedar teksti, do të kontrollojë se file teksti kundër fjalor. 

Tani, fjalor fotografi tekst do të përmbajë Fjalët e vlefshme, një për rresht. Shkruaj një fjalë atëherë do të thërrasë Load në fjalorin skedar teksti. Ajo do të thërrasë një funksion të quajtur Kontrolloni në çdo fjalë në dosje të futura teksti, shtypje të gjitha fjalët e shkruara gabim. 

Shkruaj një fjalë do të thërrasë Size për të përcaktuar numrin e fjalëve në fjalor dhe thirrjen e zbraz të lirë deri kujtesës. Shkruaj një fjalë gjithashtu do të mbajnë gjurmët e sa sa kohë është përdorur për të kryer këto proceset, por ne do të të shkoj në atë më vonë. 

Pra, çfarë duhet të bëjmë? Ne duhet të plotësoni në dictionary.c. Në dictionary.c, ne kemi të ndihmës Load funksion, i cili ngarkon fjalor. Funksioni Kontrollo, e cila kontrollon nëse një fjalë e dhënë është në fjalor. Funksioni Size kthen numrin e fjalëve në fjalor. Dhe së fundi, ne kemi shkarkoj, i cili liron fjalor nga kujtesa. 

Pra, së pari, le të trajtuar Load. Për çdo fjale në tekst fjalor fotografi, Load do të ruajtur këto fjalë në Struktura e të dhënave fjalor që dëshironi, ose a hash tabelë ose një Trie. Unë do të shkoj për të dy në kjo ecin nëpër. 

Së pari le të flasim për tabelat hash. Thuaj keni pasur 10 topa bilardos dhe ju të kërkuar për të ruajtur ato. Ju mund të vënë të gjithë në një kovë, dhe kur ju nevojitet një specifik numëruar topin, ju do të merrni një të tillë nga kove në një kohë kërkim për këtë top. Dhe vetëm me 10 topa, ju duhet të jetë në gjendje të gjejnë topin tuaj në një të arsyeshme Sasinë e kohës. 

Por, çfarë nëse ju kishte 20 topa? Ajo mund të marrë pak më të gjatë tani. Po në lidhje me 100? 1000? Tani, do të ishte shumë më e lehtë në qoftë se keni pasur kova të shumta. Ndoshta një kovë për topa të numëruara zero përmes nëntë, një tjetër kovë për topa numëruar 10 përmes 19, dhe kështu me radhë. 

Tani kur ju nevojiten për të kërkuar të veçantë top, ju mund automatikisht shkoni në një kovë të veçantë dhe kërkoni nëpër atë kovë. Dhe në qoftë se çdo kovë ka përafërsisht 10 topa, atëherë ju mund të lehtë të kërkoni nëpërmjet saj. 

Tani, pasi ne jemi që kanë të bëjnë me fjalorë, një kovë të vetme për të gjitha fjalët në fjalor do të ndoshta të jetë shumë më tepër disa kova. Pra, le të marrin një vështrim në tabelat hash. 

Mendoni se si një grup të kova. Dhe në këtë rast, kova janë listat tona të lidhura. Dhe ne do të shpërndajë të gjitha fjalët tona në mesin e këtyre listave të shumta të lidhura në një mënyrë të organizuar duke përdorur një funksion hash, e cila do të na tregojë se cilat kovë dhënë një kyç, një të dhënë fjalë, i takon. 

Le të paraqesin këtë mënyrë skematike. Kutitë blu këtu përmbajnë vlerat dhe kuti të kuqe tregojnë për një tjetër vlerë palë akrep. Ne do të quajmë këto palë nyje. Tani, çdo kovë, siç thashë më parë, është një listë e lidhur. Në listat e lidhura, secila nyjë ka një vlerë, si dhe nje tregues te Vlera e ardhshëm. 

Tani, që kanë të bëjnë me listat e lidhura, kjo është shumë e rëndësishme që ju mos e humb çdo lidhje. Dhe një fakt tjetër për të mbajtur mend është se nyje e fundit, në qoftë se ajo nuk tregon për një tjetër nyje, tregon null. 

Pra, si ne përfaqësojmë këtë në C? Ne të përcaktojë e strukturës tonë këtu. Dhe vlera në këtë rast është një grup char e gjatësisë. Gjatësi plus 1, ku gjatësia është Gjatësia maksimale e çdo fjale, plus 1 për terminator null. Dhe pastaj ne kemi një tregues për një tjetër nyje quajtur Next. 

Pra, le të bëjmë një listë të vogël lidhur. Së pari, ju do të dëshironi të malloc nyje tuaj, të cilat krijojnë hapësirë ​​në kujtesë Madhësia e tipit tuaj node. Dhe të bëjnë një tjetër nyje, përsëri mallocing. 

Tani në qoftë se ju doni të caktojë një vlerë të një fjalë, atëherë mund të themi shigjetë node1 Fjala është e barabartë me "Hello". Ky operator shigjeta dereferences treguesin dhe accesses variablat e struct-së. Në këtë mënyrë, ne nuk duhet të përdorin të dyja dot dhe operatori yll. 

Pra, atëherë unë kam node2 shigjetë fjalë është e barabartë me "Botë." Dhe atje, vlerat janë të populluar në nyjet e mia. Për të bërë lidhjet, unë do të kalojë në node1 shigjetë tjetër, qasja në atë yll nyje, që akrep nyje, e barabartë me node2, duke treguar node1 të node2 dy. Dhe nuk kemi një listë e lidhur. 

Pra, kjo ishte vetëm një listë e lidhur, por një tabelë hash është një grup të tërë të Listat e lidhura. E pra, ne do të kemi të njëjtën nyjë strukturohet si më parë. Por nëse kemi dashur një tryezë aktuale hash, atëherë ne mund të bëjë vetëm një tregues nyje array këtu. Për shembull, madhësia 500. 

Tani njoftim, nuk do të jetë një tregti off ndërmjet madhësisë së tuaj tabelë hash dhe madhësia nga listat tuaja të lidhura. Nëse ju keni një numër të vërtetë të lartë të kova, duke imagjinuar që ka për të kandiduar përsëri dhe me radhë në një linjë me gjeni kovë tuaj. Por ju gjithashtu nuk duan një numër të vogël e kova, sepse atëherë ne jemi kthyer në problemi fillestar se si të pasurit shumë topa në kovë tonë. 

OK, por ku ka topi tonë të shkojë? E pra, ne së pari duhet të kanë një top, e drejtë? Pra, le të malloc një nyje për çdo fjalë të re që ne kemi. nyje * barabartë new_node malloc (sizeof (nyje)). 

Tani që ne kemi këtë strukturë, ne mund të skanoni në, duke përdorur funksionin fscanf, një varg nga file tonë, në qoftë se kjo është një fotografi fjalor, në new_node shigjetë fjalë, ku new_node shigjetë fjala është tonë destinacioni i asaj fjale. 

Tjetra, ne do të duan të përpunojnë që fjalë duke përdorur një funksion hash. Një funksion hash merr një varg dhe kthen një indeks. Në këtë rast, indeksi ka për të jetë më i vogël se numri i kova që ju duhet. 

Tani, funksionet hash, kur ju jeni duke u përpjekur për të gjetur një të tillë dhe për të krijuar një nga tuaj, mos harroni se ata duhet të jenë të determinist. Kjo do të thotë se të njëjtën vlerë duhet të hartë me të njëjtën kovë çdo herë që ju të hash atë. 

Kjo është lloj i si një bibliotekë. Kur të merrni një libër, bazuar në autori, ju e dini që raft sa duhet shkojnë në, nëse kjo është numër i raft një, dy, ose tre. Dhe se libri gjithmonë do të takojnë në ose një raft, dy, ose tre. 

Pra, nëse new_node shigjeta fjalë ka fjalë nga fjalori juaj, atëherë hashing new_node shigjetë fjalë do të na japin indeksin e kovë e tabelës hash. Dhe pastaj ne do të futur që në atë Lista specifik lidhur tregohet nga vlerën e funksionit tonë hash kthehen. 

Le të shikojmë një shembull të futur një nyje në fillimi i një liste të lidhura. Nëse koka është një tregues nyje që tregon fillimi i një të lidhur listë, dhe new_node tregon ri Nyja që ju dëshironi për të hyrë në, vetëm caktimin e kreu në new_node do të humbasë lidhja tek pjesa tjetër e lista. Pra, ne nuk duam për të bërë këtë. 

Përkundrazi, ne duam të sigurohemi që ne të mbajë në të çdo nyje e vetme në programin tonë. Pra, duke new_node shigjetë barabartë ardhshme kokë dhe më pas kreu barabartë new_node do të ruajë të gjitha të lidhjet dhe nuk humbasin asnjë. 

Por, çfarë nëse ju doni listën tuaj të jenë të renditura, sepse ka një të renditura lidhur Lista mund të jetë më e lehtë për kërkoni atë më vonë? E pra, për këtë, ju do të duhet të dini se si të kaloj nëpër listat e lidhura. 

Për të kaloj nëpër një listë e lidhur, le të kemi një tregues nyje, një nyje *, për të vepruar si kursori juaj, duke treguar cili Nyja ju jeni në të, duke filluar në të elementit të parë. Looping deri kursorit është null, ne mund të kryejnë disa procese dhe pastaj avancojë kursorin kur ne kemi nevojë duke përdorur shigjetë vlerën e kursorit. 

Mos harroni, kjo është e njëjta gjë si duke thënë kursorin yll, dereferencing kursorin, pastaj duke përdorur Vlera dot operatori. Pra përditësimin kursorin është duke caktuar kursorin për të kursorit shigjetë e ardhshëm. 

Thuaj ju të përcaktojë se D të bëhet në ndërmjet C dhe E. Për të futur nyje, kanë të D pikë new_node të nyjen E, e cila është kursori tej. Dhe pastaj C, kursori, mund pastaj pikë D. në këtë mënyrë, ju të mbajë një listë. Kini kujdes të mos për të humbur lidhjet tuaja nga lëvizur kursorin shigjetë tjetër për D menjëherë. 

Dakord. Pra, kjo është se si ju mund të futni nyje, ngarkesën e tyre në, fjalët e ngarkesës në ato nyjet, dhe futur ato në tryezën tuaj të hash. Pra, tani le të shohim përpiqet. 

Në një Trie, çdo nyje do të përmbajë një grup i nyjeve pointers, një për çdo letër në alfabetin plus një apostrof. Dhe çdo element në rrjet do të tregojnë për një tjetër nyje. Nëse kjo nyje është null, atëherë kjo letër nuk do të jetë shkronja tjetër i çdo fjalë në një sekuencë, sepse çdo Fjala tregon nëse kjo është e fundit Karakteri i një fjalë apo jo. 

Le të shikojmë në një diagram. Shpresojmë se gjërat do të të jetë pak më të qartë. Në këtë diagram, ne shohim se vetëm letra të caktuara dhe nënvargjet caktuara janë duke u renditur nga. Kështu që ju mund të ndjekë rrugë të caktuara, dhe të gjitha këto shtigje do të të çojë në fjalë të ndryshme. 

Pra, si ne përfaqësojmë këtë në C? E pra, çdo nyje tani do të ketë një vlerë Boolean që tregon nëse se nyja është fundi i një fjalë e dhënë apo jo. Dhe atëherë ajo do të ketë një rrjet të nyje pointers quajtur fëmijë e atje do të jetë 27 prej tyre. Dhe mbani mend, ju do të dëshironi të mbajnë gjurmët e nyjeve tuaj të parë. Ne jemi duke shkuar për të thirrur atë rrënjë. 

Pra, kjo është struktura e një Trie. Si mund të përfaqësojnë këtë si një fjalor? E pra, për të ngarkuar në fjalë, për çdo fjalë fjalor, ju jeni do të duan te iterate nëpërmjet Trie. Dhe secili element në fëmijët korrespondon me një letër tjetër. 

Pra kontrolluar vlerën në fëmijët Indeksi i, ku i paraqet Indeksi specifike e letrës që jeni duke u përpjekur për të futur. E pra, në qoftë se është i pavlefshëm, atëherë ju do të dëshironi të malloc një nyje të re dhe të ketë fëmijë i tregojnë për atë nyje. 

Nëse nuk është i pavlefshëm, atëherë kjo do të thotë se se dega duke pasur parasysh, se duke pasur parasysh nën-string, tashmë ekziston. Pra, atëherë ju do të lëvizin vetëm me atë nyja e re dhe të vazhdojë. Nëse ju jeni në fund të fjalës që jeni duke u përpjekur për të ngarkuar në fjalor, atëherë ju mund të vendosni se nyje e tanishme që ju jeni në të vërtetë. 

Pra, le të shohim një shembull të futur fjala "dhelpra" në tonë fjalor. Pretendon se të fillojmë me një fjalor bosh. Letra e parë, F, do të jetë e vendosur në indeksin e fëmijëve pesë nga rrënjët fëmijët array. Pra, ne të futur që in 

Letra O më pas do të jetë në fëmijët indeksi 15, pas asaj F. Dhe pastaj X do të jetë edhe më poshtë se, bronkial off e fëmijëve të o-së. Dhe pastaj për shkak se X është shkronja e fundit i fjalës "dhelpra," atëherë unë jam duke shkuar për të ngjyra se gjelbër për të treguar se kjo është fundi i fjalës. Në C, që do të jetë caktimi është i Fjala boolean me vlerën e vërtetë. 

Tani çfarë nëse fjala tjetër që ju jeni ngarkimit në është fjala "foo"? E pra, ju nuk keni nevojë që të malloc ndonjë më shumë hapësirë ​​për F ose për O, sepse ato që tashmë ekzistojnë. Por O fundit në foo? Se një, ju do të duhet të malloc. Bëni një nyje të re për atë, duke vendosur Is Fjala Boolean për të vërtetë. 

Pra, tani le të futur "qen." Dog do të të fillojë me indeksin tre të rrënjëve fëmijët, sepse nuk ka D është krijuar ende. Dhe ne do të ndjekë një proces të ngjashëm si para, duke krijuar qen nën-string, ku është G është me ngjyrë të gjelbër për shkak se kjo është në fund të një fjale. 

Tani, ajo që në qoftë se ne duam të futur "të bërë"? E pra, kjo është një nën-string e qenit, në mënyrë ne nuk kemi nevojë të malloc më. Por ne kemi nevojë për të treguar se ku ne kemi arritur në fund të asaj fjale. Pra, o do të jetë me ngjyrë të gjelbër. Duke vazhduar këtë proces për çdo të vetme fjalë në fjalorin tuaj, ju keni ngarkuar ato në ose në tuaj hash tabelë apo Trie tuaj. 

Shkruaj një fjalë do të kalojë në vargjet për dictionary.c për të kontrolluar ato. Tani, funksioni Kontrollo ka për të vepruar në rast të paepur. Kjo do të thotë se shkronja kapitale dhe vogle shkronja dhe një përzierje e të dy të gjithë duhet të vë shenjën e barazimit të vërtetë në qoftë se ndonjë Kombinimi i që është në fjalor. Ju gjithashtu mund të supozojmë se vargjet janë të vetëm do të përmbajë alfabetik karaktere ose apostrofat. 

Pra, le të shohim se si ju mund të kontrolloni me një strukturë tavolinë hash. E pra, në qoftë se ekziston fjala, atëherë ajo mund të gjenden në tabelën hash. Pra, atëherë ju mund të përpiquni të gjeni se Fjala në kovë përkatës. 

Pra cila kovë do të ishte që në fjalë? E pra, ju do të merrni numrin, se indeksi e kovë, duke hashing se fjala dhe pastaj të kërkoni në atë listën e lidhur, traversing nëpër të gjithë lista e lidhur, duke përdorur String Krahaso funksion. 

Nëse në fund të listës është lidhur arritur, do të thotë që kursori juaj arrin null, atëherë nuk është fjala të gjendet në fjalor. Kjo nuk do të jetë në çdo kovë tjetër. Kështu që këtu, ju mund të shihni se si ka mund të jetë një tregti-off mes të pasurit ose lista të renditura të lidhura ose ato Unsorted. Ose do të marrë më shumë kohë gjatë ngarkesës ose më shumë kohë në kontroll. 

Si mund ta kontrolloni në një strukturë Trie? Ne jemi duke shkuar për të udhëtuar poshtë në Trie. Për çdo letër në fjalë të futura se ne jemi duke kontrolluar, ne do të shkojnë në atë element të fëmijëve përkatëse. 

Në qoftë se element është null, atëherë kjo do të thotë se nuk ka nënvargjet që përmban fjalën tonë input, kështu fjala është misspelled. Nëse nuk është null, ne mund të lëvizin për të shkronja tjetër i fjalës se ne jemi të kontrolluar dhe për të vazhduar këtë proces derisa të arrijë në fund të fjalës input. Dhe atëherë ne mund të kontrolloni në qoftë se Is Fjala është e vërtetë. Nëse është, atëherë e madhe. Fjala është e saktë. Por në qoftë se jo, edhe pse se nën-string ekziston në Trie, fjala është misspelled. 

Kur funksioni Madhësia quhet, madhësia duhet të kthehen numrin e fjalëve që janë në fjalorin tuaj të caktuar Struktura e të dhënave. Pra, nëse ju jeni duke përdorur një tabelë hash, ju ose mund të shkoni nëpër çdo të vetme lista e lidhur në çdo të vetme kovë numëruar numrin e fjalëve janë atje. Nëse jeni duke përdorur një Trie, ju mund të kalojnë nëpër çdo jo null rrugë në Trie tuaj. Apo ndërkohë që jeni ngarkimit fjalorin në, ndoshta ju mund të ruaj gjurmët e se si shumë fjalë ju jeni në ngarkim in 

Pasi Shkruaj një fjalë përfundon kontrolluar skedar teksti kundër fjalorit, atëherë është bërë dhe kështu që e quan shkarkoj, ku puna juaj është për të ndonjë gjë të lirë që e keni malloced. Pra, në qoftë se ju përdorni një tabelë hash, atëherë ju duhet të jenë veçanërisht të kujdesshëm për të shmangur rrjedhjet e kujtesës duke mos liruar asgjë para kohe dhe të mbajnë mbi çdo Lidhje të vetme para se të lirë. 

Pra, për çdo element në tabelë hash dhe për çdo nyje në listën e lidhur, ju do të dëshironi të atë nyje lirë. Si ju shkoni në lidhje me çlirimin e një listë e lidhur? Vendosja treguesin tuaj nyje kursorin në Drejtuesi, me fillimin e lista e lidhur, atëherë ndërsa kursori juaj nuk është null, ju mund të vendosni një të përkohshme nyje tregues për kursorin. Pastaj përparojnë kursorin. Dhe pastaj ju mund të lirë që të përkohshme ndërsa vlera ende mbajtjen e çdo gjë më pas. 

Çfarë ndodh nëse ju jeni duke përdorur një Trie? Atëherë mënyra më e mirë për të bërë këtë është që të shkarkoj nga shumë poshtë lart. Duke udhëtuar të ulët të mundshme nyje, ju mund të lirë të gjitha pointers në që fëmijët dhe pastaj backtrack lart, duke çliruar të gjitha elementet në të gjitha i fëmijëve vargjeve, deri ju goditi nyje tuaj të lartë rrënjë. Ja ku Recursion do të jetë në dispozicion. 

Për të bërë të sigurtë që ju keni liruar ndoshta çdo gjë që ju keni malloced, ju mund të përdorni Valgrind. Drejtimin e Valgrind do të drejtuar programin tuaj duke numëruar se sa shumë byte memorje ju jeni duke përdorur dhe duke e bërë të sigurtë që ju keni liruar ata të gjithë, ju thënë ku ju mund të keni harruar të lirë. Vraponi në mënyrë që dhe një herë Valgrind ju tregon dhe ju jep të shkojnë përpara, atëherë ju keni përfunduar shkarkoj. 

Tani, disa këshilla para se të shkoni jashtë dhe të fillojnë zbatimin tuaj fjalor. Unë do të rekomandojë për të kaluar në një më të vogël fjalor kur jeni duke u përpjekur për të provuar gjërat nga dhe debugging me PBB. Përdorimi i speller është. / Speller, një opsional fjalor, dhe më pas një tekst. 

By default, ajo ngarkesa në fjalor i madh. Kështu që ju mund të dëshironi për të kaluar në të vogla fjalor, apo ndoshta edhe të bëjë tuaj vet, customizing fjalor juaj dhe dosjen tuaj tekst. 

Dhe pastaj në fund, unë do të rekomandojë për të marrë një stilolaps dhe letër dhe të nxjerrë gjëra nga para, gjatë, dhe pas ju keni shkruar të gjitha të kodit tuaj. Vetëm sigurohuni që ju keni marrë këto pointers vetëm e drejtë. 

Ju uroj të mirë e fat. Dhe një herë ju keni mbaruar, në qoftë se ju dëshironi për të sfiduar të bordit të madh dhe shikoni se sa shpejt programi juaj është i krahasuar me shokët e klasës tuaj, atëherë unë inkurajoj ju për të kontrolluar atë jashtë. 

Me këtë, ju keni përfunduar PSet speller. Emri im është Zamyla, dhe kjo është CS50.