ZAMYLA Chan: Ejja jagħmlu jespliċitaw kontrollur. Jekk inti tiftaħ speller.c, allura tkun taf tara li ħafna mill-funzjonalità għal verifika fajl test kontra dizzjunarju diġà magħmula ghalik. . / Speller, li jgħaddi minn test dizzjunarju fajl u mbagħad fajl ieħor it-test, ser jiċċekkja li fajl test kontra l-dizzjunarju. 

Issa, fajls test dizzjunarju se jkun fih kliem validi, wieħed għal kull linja. Imbagħad speller.c se sejħa Load fuq il-fajl test dizzjunarju. Hija ser sejħa funzjoni msejħa Iċċekkja fuq kull kelma fil-fajl test inputted, istampar kollha kliem misspelled. 

Speller.c Jitolbu ukoll Daqs biex jiddetermina n-numru ta 'kliem fil- dizzjunarju u sejħa jħottu biex tilliberalizza l-memorja. speller.c se żżomm ukoll rekord ta 'kif ħafna ħin jintuża għat-tmexxija ta 'dawn proċessi, iżda aħna ser jiksbu għal dak aktar tard. 

Allura dak li għandna bżonn tagħmel? Għandna bżonn timla dictionary.c. Fl dictionary.c, aħna għandna l-helper Tagħbija funzjoni, li jgħabbi l- dizzjunarju. Il-Kontroll funzjoni, li tiċċekkja jekk kelma partikolari huwa fid-dizzjunarju. L-Daqs funzjoni lura l-għadd ta 'kliem fid-dizzjunarju. U fl-aħħarnett, aħna għandna jħottu, li jillibera l dizzjunarju mill-memorja. 

Allura l-ewwel, ejja tindirizza Tagħbija. Għal kull kelma fit-test dizzjunarju file, tat-Tagħbija ser taħżen dawn il-kliem fil- l-istruttura tad-data dizzjunarju ta 'għażla tiegħek, jew hash tabella jew trie. I ser imorru fuq kemm fil- dan jimxu permezz. 

Ewwel ejja nitkellmu dwar tabelli hash. Tgħid li inti kellhom 10 blalen tal-biljard u int riedu jaħżinhom. Inti tista 'tpoġġi lilhom kollha fil-barmil, u meta inti meħtieġ speċifiku nnumerati ball, youd tieħu waħda barra mill-barmil fi żmien tfittex għal dak ball. U ma biss 10 blalen, inti għandek tkun jistgħu jsibu ballun tiegħek b'mod raġjonevoli ammont ta 'ħin. 

Imma dak jekk kellek 20 blalen? Huwa jista 'jieħu ftit itwal issa. What about 100? 1,000? Issa, ikun ħafna aktar faċli jekk kellek bramel multipli. Forsi barmil wieħed għal blalen numerati zero permezz ta 'disa, barmil ieħor għal blalen nnumerati 10 permezz 19, u l-bqija. 

Issa meta inti meħtieġ biex tfittex speċifiku ball, inti tista 'awtomatikament mur barmil speċifiku wieħed u tfittxija permezz ta 'dak barmil. U jekk kull barmil għandha madwar 10 blalen, allura inti tista 'faċilment tfittxija permezz tiegħu. 

Issa, peress li aħna qed jittrattaw ma dizzjunarji, wieħed barmil uniku għall- kollha tal-kliem fil-dizzjunarju se probabbilment ikun wisq ftit bramel. Mela ejja tagħti ħarsa lejn tabelli hash. 

Jaħsbu li bħala firxa ta 'bramel. U f'dan il-każ, il-bramel huma listi marbuta tagħna. U aħna ser jiddistribwixxi kollha ta 'kliem tagħna fost dawn il-listi konnessi multipli mod organizzat jużaw funzjoni hash, li se jgħidulna li barmil ewlieni partikolari, partikolari kelma, jappartjeni. 

Ejja jirrappreżenta dan skematikament. Il-kaxxi blu hawn jkun fihom valuri u kaxxi aħmar punt valur ieħor par pointer. Aħna ser sejħa dawn lymph pari. Issa, kull barmil, kif għidt qabel, hija lista marbuta. Fil-listi relatati, kull node għandha valur, kif ukoll pointer għall- valur li jmiss. 

Issa, li jittrattaw listi marbuta, huwa importanti ħafna li inti ma jitilfux xi links. U ta 'fatt ieħor li tiftakar li l- aħħar node, jekk ma punt għal node ieħor, il-punti li null. 

Allura kif nistgħu jirrappreżenta dan fis-C? Aħna jiddefinixxu Struct tagħna hawn. U l-valur f'dan il-każ firxa char ta 'tul. Tul plus 1, fejn it-tul hija l- tul massimu ta 'kull kelma, plus 1 għal terminatur null. U allura għandna pointer biex node oħra msejħa jmiss. 

Mela ejja jagħmlu lista żgħira marbuta. L-ewwel, tixtieq tkun taf biex malloc node tiegħek, li jinħoloq spazju fil-memorja tal- daqs tat-tip node tiegħek. U jagħmlu node ieħor, darb'oħra mallocing. 

Issa jekk inti tixtieq li tassenja valur għal kelma, allura nistgħu ngħidu vleġġa node1 kelma ugwali "Hello." Dan l-operatur arrow dereferences l-pointer u aċċessi varjabbli tal-Struct tal. Dan il-mod, aħna ma jkollhom jużaw kemm l-dot u l-operatur star. 

Mela allura għandi kelma vleġġa Node2 ugwali "Dinja." U hemm, il-valuri huma popolati fil-lymph tiegħi. Biex tagħmel l-links, jien ser jgħaddu node1 vleġġa li jmiss, aċċess li star node, li pointer node, ugwali Node2, tipponta node1 li Node2 tnejn. U hemm aħna għandna lista marbuta. 

Allura li kien biss lista marbuta wieħed, iżda tabella hash huwa firxa sħiħa ta ' listi marbuta. Well, aħna ser ikollhom l-istess node istruttura bħal qabel. Imma jekk ridna tabella hash attwali, allura nistgħu biss tagħmel pointer node array hawn. Per eżempju, id-daqs 500. 

Issa avviż, hemm għaddej li jkun kummerċ off bejn id-daqs tal tiegħek tabella hash u d-daqs ta 'listi marbutin tiegħek. Jekk għandek numru tassew għoli ta ' bramel, imagining li jiddekorri lura u lura fil-linja li ssib barmil tiegħek. Iżda inti wkoll ma tridx numru żgħir ta 'bramel, għaliex allura aħna qed lura biex il-problema oriġinali ta 'kif li wisq blalen fil-barmil tagħna. 

OK, iżda fejn ma ball tagħna tmur? Well, aħna l-ewwel jeħtieġ li jkollhom ballun, right? Mela ejja malloc node għal kull kelma ġdida li għandna. node * ugwali new_node malloc (sizeof (node)). 

Issa li għandna din l-istruttura, aħna tista 'scan fi, tuża l-funzjoni fscanf, string minn fajl tagħna, jekk li l-fajl dizzjunarju, fis new_node kelma vleġġa, fejn new_node kelma arrow huwa tagħna destinazzjoni ta 'din il-kelma. 

Sussegwentement, aħna ser trid issir hash li kelma li jużaw funzjoni hash. A funzjoni hash tieħu string u jirritorna l-indiċi. F'dan il-każ, l-indiċi għandu jkun inqas min-numru ta ' Bramel li għandek. 

Issa, il-funzjonijiet hash, meta inti qed tipprova isibu waħda u toħloq waħda ta ' tiegħek, ftakar li dawn għandhom ikunu deterministic. Dan ifisser li l-istess valur jeħtieġ li mappa għall-istess barmil kull darba li inti hash dan. 

Huwa tip ta 'bħal librerija. Meta tieħu ktieb, ibbażata fuq l- awtur, tkun taf liema ixkaffa suppost tmur fuq, jekk huwa numru ixkaffa wieħed, tnejn, jew tlieta. U dak il-ktieb dejjem se jappartjenu fuq jew ixkaffa wieħed, tnejn, jew tlieta. 

Għalhekk, jekk kelma vleġġa new_node għandha l- kelma minn dizzjunarju tiegħek, allura hashing kelma vleġġa new_node se agħtina l-indiċi tal- barmil tat-tabella hash. U allura aħna ser daħħal dan in li lista speċifika marbuta indikat mill- ritorn valur ta 'funzjoni hash tagħna. 

Ejja nħarsu lejn eżempju ta ' ddaħħal node fil- bidu ta 'lista marbuta. Jekk ras huwa pointer node li jindika il-bidu ta 'marbuta lista, u new_node jindika l-ġdid node li inti tixtieq li tidħol fi, biss assenjazzjoni ras għal new_node jitilfu il-link għall-bqija tal-lista. Allura aħna ma jridux jagħmlu dan. 

Pjuttost, irridu niżguraw li aħna żżomm fuq kull node wieħed fil-programm tagħna. Allura running vleġġa new_node ugwali jmiss ras u mbagħad ras ugwali new_node se tippreserva kollha ta 'l- links u ma jitlef l-ebda. 

Imma x'jiġri jekk inti tixtieq lista tiegħek li tkun magħżula, minħabba li a magħżula marbuta lista tista 'tkun aktar faċli għall- tiftix aktar tard fuq? Ukoll, għal dan, ikollok bzonn li tkun taf kif travers listi marbuta. 

Travers lista marbuta, ejja jkollhom pointer node, node *, li jaġixxu bħala cursor tiegħek, tindika li node int fuq, li jibda fl-ewwel element. Looping sakemm cursor huwa null, nistgħu twettaq ċerti proċessi u mbagħad tavvanza l-cursor meta rridu użu tal-valur vleġġa cursor. 

Ftakar, dan huwa l-istess ħaġa bħat qal cursor stilla, dereferencing cursor, imbagħad bl-użu tal- valur operatur dot. Allura taġġorna l-cursor huwa billi assenja il-cursor biex vleġġa cursor li jmiss. 

Tgħid li inti jiddeterminaw li D isir fl bejn Ċ u E. Biex daħħal il-node, jkollhom l D punt new_node għall- node E, li huwa cursor li jmiss. U mbagħad C, il-cursor, jista 'imbagħad il-punt li D. B'dan il-mod, inti żżomm lista. Oqgħod attent li ma jitilfu links tiegħek billi li jiċċaqalqu il-cursor vleġġa li jmiss D dritt bogħod. 

Kull dritt. Allura li kif inti tista 'daħħal nodes, jitgħabbew, kliem tagħbija f'dawk lymph, u daħħal minnhom fis tabella hash tiegħek. Allura issa ejja nħarsu lejn jipprova. 

Fil trie, kull node se jkun fiha firxa ta 'glandoli pointers, waħda għal kull ittra fl-alfabett flimkien ma 'apostrophe. U kull element fil-firxa se jindika node ieħor. Jekk dik node huwa null, allura din l-ittra mhix se tkun l-ittra li jmiss ta ' xi kelma f'sekwenza, għaliex kull kelma tindika jekk huwa l-aħħar karattru ta 'kelma jew le. 

Ejja nħarsu lejn dijagramma. Nisperaw affarijiet se jkun daqsxejn aktar ċara. F'din l-istampa, naraw li biss ċerti ittri u ċerti substrings qed jiġu elenkati out. Allura inti tista 'ssegwi ċerti mogħdijiet, u kollha ta 'dawk mogħdijiet inti se twassal għal kliem differenti. 

Allura kif nistgħu jirrappreżenta dan fis-C? Ukoll, kull node issa huwa se jkollu valur Boolean tindika jekk li node hija t-tmiem ta ' kelma partikolari jew le. U allura ser ikollok wkoll firxa ta ' pointers node imsejħa tfal, u hemm ser tkun 27 minnhom. U ftakar, tkun taf ukoll tixtieq jżommu rekord ta 'l-ewwel node tiegħek. Aħna ser sejħa dan għerq. 

Allura dak hu l-istruttura ta 'trie. Kif nistgħu jirrappreżenta dan bħala dizzjunarju? Well, tagħbija kliem, għal kull dizzjunarju kelma, int ser jridu li jtenni permezz tal-trie. U kull element fil-tfal tikkorrispondi għal ittra differenti. 

Allura verifika tal-valur lejn it-tfal i indiċi, fejn i jirrappreżenta l- indiċi speċifiku tal-ittra li int tipprova li daħħal. Ukoll, jekk huwa null, allura tkun taf tixtieq li malloc node ġdid u jkollhom it-tfal I punt għal dak node. 

Jekk mhuwiex null, allura dan ifisser li dik il-fergħa partikolari, li minħabba substring, diġà jeżisti. Mela allura inti taf biss timxi ma 'dik node ġdid u jkomplu. Jekk int fl-aħħar tal-kelma li inti qed tipprova tagħbija fil- dizzjunarju, allura inti tista 'tistabbilixxi li node attwali li int fuq li veru. 

Mela ejja nħarsu lejn eżempju ta 'ddaħħal il-kelma "volpi" fis tagħna dizzjunarju. Nippretendu nibdew il dizzjunarju vojt. L-ewwel ittra, F, se tkun tinsab fl-indiċi tfal ħamsa mill-għeruq tfal array. Allura aħna daħħal dik pulzieri 

L-ittra O mbagħad tkun fit-tfal indiċi 15, wara li F. U mbagħad X se jkun saħansitra taħt dak, fergħat off tat-tfal tal-O. U allura għaliex X hija l-aħħar ittra tal-kelma "volpi," allura jien ser kulur li aħdar li jindika li huwa l-aħħar tal-kelma. Fl C, li jkun jistabbilixxi l-IS Word Boolean mal-valur veru. 

Issa dak li jekk il-kelma li jmiss li int tagħbija fil hija l-kelma "foo"? Ukoll, inti m'għandekx bżonn li malloc aktar spazju għall-F jew O, għaliex dawk diġà jeżistu. Iżda l-aħħar O fl foo? Li wieħed, inti ser ikollok malloc. Agħmel node ġdid għal dan, jistabbilixxu il-kelma Boolean li veru. 

Allura issa ejja daħħal "kelb." Dog se tibda bil indiċi tlieta mill-għeruq tfal, minħabba D għandu ma ġew maħluqa s'issa. U aħna ser isegwu proċess simili qabel, toħloq il-kelb substring, Fejn hi l-G hija kkulurita aħdar minħabba dak l-aħħar ta 'kelma. 

Issa, dak li jekk irridu li daħħal "jagħmlu"? Ukoll, dan huwa substring ta 'kelb, hekk ma kellniex bżonn li malloc aktar. Iżda jeħtiġilna li jindika fejn konna laħqu t-tmiem ta 'din il-kelma. Allura l-O se tkun ta 'kulur aħdar. Tkompli dan il-proċess għal kull wieħed kelma fil-dizzjunarju tiegħek, inti ħadthom mgħobbija fil f'waħda tiegħek hash tabella jew trie tiegħek. 

speller.c se jgħaddu f'qatet twal għal dictionary.c li jiġu verifikati. Issa, il-funzjoni Check ikollu jopera taħt il-każ insensittività. Dan ifisser li l-ittri kapitali u zghar ittri u taħlita tat-tnejn kollha għandu jkun daqs veru jekk xi kombinazzjoni ta 'dan huwa fil- dizzjunarju. Tista 'wkoll jassumi li kordi huma biss ser ikollhom alfabetiku karattri jew apostrophes. 

Mela ejja nħarsu lejn kif inti tista 'tiċċekkja bi struttura tabella hash. Ukoll, jekk teżisti l-kelma, allura jistgħu jinstabu fit-tabella hash. Mela allura inti tista 'tipprova ssib dak kelma fil-barmil rilevanti. 

Allura liema barmil kieku din il-kelma tkun? Well, youd tikseb in-numru, l-indiċi tal-barmil, bil hashing din il-kelma u mbagħad tiftix f'dik il-lista marbuta, traversat permezz kollu lista marbuta, bl-użu String Qabbel funzjoni. 

Jekk l-aħħar tal-lista marbuta hija jintlaħaq, li jfisser li cursor tiegħek jilħaq null, allura l-kelma mhix li jinstabu fid-dizzjunarju. Dan mhux se jkunu fi kwalunkwe barmil oħra. Allura hawn, inti tista 'tara kif hemm tista' jkun kompromess bejn li jkollhom jew listi marbuta magħżula jew dawk mhux magħżula. Jew se tieħu aktar żmien matul tagħbija jew aktar ħin waqt il-verifiki. 

Kif tista 'inti tiċċekkja fil- struttura trie? Aħna ser jivvjaġġaw isfel fil-trie. Għal kull ittra fil-kelma inputted li aħna qed iċċekkjar, aħna ser tmur f'dak il- element fit-tfal korrispondenti. 

Jekk dak l-element huwa null, allura li l-mezzi li ma jkunx hemm substrings fihom kelma input tagħna, sabiex il-kelma hija misspelled. Jekk mhuwiex null, nistgħu jimxu lejn il- ittra li jmiss tal-kelma li aħna qed verifika u tkompli dan il-proċess sakemm aħna jilħqu t-tmiem tal-kelma input. U allura aħna tista 'tivverifika Jekk tiġi Word huwa veru. Jekk huwa, imbagħad kbira. Il-kelma l-korretta. Imma jekk le, anki jekk din substring teżisti fil-trie, il-kelma hija misspelled. 

Meta d-daqs funzjoni tissejjaħ, id-daqs għandu jirritorna l-għadd ta 'kliem li huma fil-dizzjunarju partikolari tiegħek struttura tad-data. Mela jekk inti qed tuża tabella hash, inti tista 'jew tmur permezz ta' kull wieħed lista marbuta f'kull wieħed barmil għadd tan-numru ta 'kliem huma hemmhekk. Jekk inti qed tuża trie, inti tista ' jgħaddu kull null non triq fil trie tiegħek. Jew waqt li int tagħbija-dizzjunarju fil, forsi inti tista 'żżomm rekord ta' kif ħafna kliem int tagħbija pulzieri 

Ladarba speller.c finituri iċċekkjar tal- fajl test kontra l-dizzjunarju, imbagħad dan isir u għalhekk jitlob jħottu, fejn xogħol tiegħek huwa li jeħles xejn li ħadthom malloced. Mela jekk inti tuża tabella hash, allura inti jeħtieġ li tkun partikolarment attenta li tevita tnixxijiet memorja billi ma ħelsien xejn prematur u azjenda fuq kull link waħda qabel inti liberu. 

Allura għal kull element fit-tabella hash u għal kull node fil-lista marbuta, tixtieq tkun taf biex ħielsa li node. Kif inti tmur dwar ħelsien lista marbuta? Twaqqif node pointer cursor tiegħek biex ir-ras, il-bidu tal- lista marbuta, allura filwaqt cursor tiegħek mhux null, inti tista 'tistabbilixxi temporanju node pointer biex cursor tiegħek. Imbagħad tavvanza l-cursor. U allura inti tista ħielsa li temporanju valur filwaqt li xorta azjenda fuq kollox wara. 

X'jiġri jekk inti qed tuża trie? Allura l-aħjar mod biex isir dan huwa li jħottu mill-ħafna qiegħ għall-quċċata. Billi jivvjaġġaw lejn l-aktar baxx possibbli node, inti tista ħielsa pointers kollha li t-tfal u mbagħad imur lura fuq, ħelsien elementi kollha fil kollha ta 'l-arrays tfal, sakemm inti hit node tiegħek għerq top. Hawn fejn Recursion se jidħlu fil handy. 

Biex tkun żgur li int ħadthom probabbilment meħlusa dak kollu li inti stajt malloced, inti tista 'tuża Valgrind. Running Valgrind se jimxu program tiegħek għadd kemm bytes ta 'memorja inti qed tuża u jagħmlu ċert li inti ħadthom meħlusa lilhom kollha, tghidlek fejn inti jista 'jkollok insejt ħielsa. Allura run dan u ladarba Valgrind jgħidlek u jagħtik l-jimxi 'l quddiem, imbagħad inti stajt lest jħottu. 

Issa, ftit tips qabel ma tmur off u tibda titwettaq tiegħek dizzjunarju. I d jirrakkomandaw li jgħaddu fi iżgħar dizzjunarju meta inti qed tipprova li jittestjaw affarijiet out u debugging bi PGD. L-użu ta 'speller huwa. / Speller, l- dizzjunarju fakultattiv, u mbagħad test. 

Konvenzjonalment, tagħbijiet fil- -dizzjunarju kbir. Allura inti tista 'tixtieq li jgħaddu fil-żgħar dizzjunarju, jew forsi anke tagħmel tiegħek stess, customizing tiegħek dizzjunarju u l-fajl test tiegħek. 

U mbagħad finalment, I d jirrakkomandaw ukoll li tieħu pinna u l-karta u jiġbed affarijiet qabel, matul, u wara inti stajt bil-miktub kollha tal-kodiċi tiegħek. Just kun żgur li inti ħadthom ltqajna dawk pointers biss id-dritt. 

Nixtieq inti l-isbaħ xewqat. U ladarba inti stajt lest, jekk tixtieq li jikkontestaw il-bord kbar u tara kif malajr program tiegħek huwa mqabbel ma ' klassi tiegħek, imbagħad I tħeġġeġ inti biex jiċċekkjaw li l-. 

Ma 'dan, inti ħadthom lest l PSet speller. Jisimni Zamyla, u dan huwa CS50.