ZAMYLA Chan: Gadewch i ni wneud gwirydd sillafu. Os ydych yn speller.c yn agor, yna byddwch yn gweld bod y rhan fwyaf o'r ymarferoldeb ar gyfer gwirio ffeil testun yn erbyn geiriadur eisoes yn cael ei wneud i chi. . / Sillafu, gan fynd heibio mewn testun geiriadur ffeil ac yna ffeil testun arall, Bydd sicrhau bod ffeil testun yn erbyn y geiriadur. 

Yn awr, bydd ffeiliau testun geiriadur gynnwys geiriau dilys, un i bob llinell. Yna bydd speller.c galw Llwytho ar y ffeil testun geiriadur. Bydd yn galw swyddogaeth o'r enw Gwirio pob gair yn y ffeil destun ei fewnbynnu, argraffu pob gair camsillafu. 

Bydd Speller.c hefyd yn galw Maint i benderfynu ar nifer y geiriau yn geiriadur a ffoniwch Dadlwytho i ryddhau cof. Bydd speller.c hefyd yn cadw golwg ar faint llawer o amser yn cael ei ddefnyddio i gynnal y rhain prosesau, ond yr ydym yn annhymerus ' gyrraedd hynny'n ddiweddarach. 

Felly, beth sydd angen i ni ei wneud? Mae angen i lenwi dictionary.c. Yn dictionary.c, mae gennym y cynorthwy-ydd Llwyth swyddogaeth, sy'n llwytho'r geiriadur. Archwiliad swyddogaeth, sy'n gwirio os gair a roddir yn y geiriadur. Maint yn dychwelyd y nifer y geiriau yn y geiriadur. Ac yn olaf, yr ydym wedi Dadlwytho, a oedd yn rhyddhau y geiriadur o'r cof. 

Felly, yn gyntaf, gadewch i ni fynd i'r afael â Llwyth. Ar gyfer pob gair yn y testun geiriadur ffeiliau, bydd Llwytho storio geiriau hynny yn y strwythur data geiriadur o'ch dewis, naill ai hash tabl neu trie. 'N annhymerus' mynd dros y ddau yn hyn yn cerdded drwy'r. 

Yn gyntaf gadewch i ni siarad am tablau hash. Dywedwch oedd gennych 10 peli biliards a 'ch wanted at storio. Efallai y byddwch yn eu rhoi i gyd mewn bwced, a phan fyddwch angen penodol pêl rhifo, byddech yn cymryd un allan o'r bwced ar y tro chwilio am y bêl. A gyda dim ond 10 peli, dylech fod yn gallu dod o hyd i'ch pêl mewn resymol faint o amser. 

Ond beth os oedd gennych 20 peli? Efallai y bydd yn cymryd ychydig yn hirach nawr. Beth am 100? 1,000? Yn awr, byddai'n llawer haws os oedd gennych bwcedi lluosog. Efallai un bwced ar gyfer peli rhifo sero drwy naw, bwced arall ar gyfer peli rhifo 10 trwy 19, ac yn y blaen. 

Nawr, pan fo angen i chi chwilio am penodol pêl, fe allech chi yn awtomatig ewch i un bwced penodol a chwilio drwy y bwced. Ac os yw pob bwced wedi tua 10 peli, yna gallech chwilio yn hawdd drwyddo. 

Yn awr, gan ein bod yn delio â geiriaduron, un bwced sengl ar gyfer holl eiriau yn y geiriadur yn yn ôl pob tebyg yn llawer rhy ychydig o bwcedi. Felly, gadewch i ni edrych ar dablau hash. 

Meddyliwch am y peth fel amrywiaeth o bwcedi. Ac yn yr achos hwn, mae'r bwcedi yw ein rhestrau cysylltiedig. A byddwn yn dosbarthu ein holl eiriau ymhlith y rhestrau hyn yn gysylltiedig lluosog mewn ffordd drefnus gan ddefnyddio swyddogaeth hash, a fydd yn dweud wrthym pa bwced allwedd a roddir, a rhoddir gair, yn perthyn i. 

Gadewch i gynrychioli'r hyn schematically. Mae'r blychau glas yma yn cynnwys gwerthoedd a blychau coch yn tynnu sylw at werth arall pâr pwyntydd. Byddwn yn galw'r rhain yn nodau parau. Yn awr, mae pob bwced, fel y dywedais yn gynharach, mae rhestr cysylltiedig. Mewn rhestrau cysylltiedig, bob nod werth, yn ogystal â pwyntydd i'r gwerth nesaf. 

Yn awr, yn delio gyda rhestrau cysylltiedig, mae'n bwysig iawn eich bod yn nid ydynt yn colli unrhyw gysylltiadau. Ac ffaith arall i'w gofio yw bod y nod olaf, os nad yw'n cyfeirio at nod arall, yn cyfeirio at null. 

Felly sut rydym yn cynrychioli hyn yn C? Rydym yn diffinio ein strwythur yma. A gwerth yn yr achos hwn amrywiaeth torgoch o hyd. Hyd ynghyd ag 1, lle mae hyd yn uchafswm hyd o unrhyw air, ac 1 ar gyfer y terminator null. Ac yna mae gennym pwyntydd i nod arall o'r enw Nesaf. 

Felly, gadewch i ni wneud rhestr bach cysylltiedig. Yn gyntaf, youll 'angen at malloc eich nod, sy'n creu lle yng nghof y maint eich math o nod. A gwnewch yn nod arall, eto mallocing. 

Nawr, os ydych am benodi a gwerth i gair, yna efallai y byddwn yn dweud saeth node1 gair yn dychwelyd "Helo." Mae'r gweithredwr arrow dereferences y pwyntydd ac mynedfeydd newidynnau y strwythur yn. Fel hyn, nid oes rhaid inni i ddefnyddio dot a'r gweithredwr seren. 

Felly, hynny, rwyf wedi node2 gair saeth yn cyfateb "Byd." Ac yno, mae'r gwerthoedd yn boblogaeth yn fy nodau. I wneud y cysylltiadau, 'n annhymerus' pasio yn node1 arrow nesaf, cael mynediad at y seren nod, y pwyntydd nod, yn hafal i node2, pwyntio node1 i node2 dau. Ac mae gennym restr cysylltiedig. 

Felly dyna oedd un rhestr gysylltiedig yn unig, ond tabl hash yn amrywiaeth eang o rhestrau cysylltiedig. Wel, byddwn yn cael yr un nod strwythuro fel o'r blaen. Ond os ydym am gael tabl hash go iawn, yna gallwn yn unig yn gwneud pwyntydd nod amrywiaeth yma. Er enghraifft, maint 500. 

Nawr rhybudd, mae mynd i fod yn fasnach oddi rhwng y maint eich tabl hash a maint eich rhestrau cysylltiedig. Os oes gennych nifer uchel iawn o bwcedi, gan ddychmygu gorfod rhedeg yn ôl ac ymlaen mewn llinell i ddod o hyd i'ch bwced. Ond nad ydych hefyd yn dymuno cael nifer fach o bwcedi, oherwydd wedyn rydym yn ôl i y broblem gwreiddiol ni am sut gael gormod o beli yn ein bwced. 

Iawn, ond lle mae ein pêl yn mynd? Wel, mae angen inni yn gyntaf cael pêl, dde? Felly, gadewch i ni malloc yn nod ar gyfer pob gair newydd sydd gennym. nod * hafal new_node malloc (sizeof (nod)). 

Nawr bod gennym y strwythur hwn, rydym yn Gall sganio i mewn, gan ddefnyddio'r swyddogaeth fscanf, llinyn o'n ffeil, os dyna ffeil geiriadur, i new_node saeth gair, lle mae new_node gair saeth yw ein cyrchfan y gair hwnnw. 

Nesaf, byddwn yn awyddus i hash y geiriau gan ddefnyddio swyddogaeth hash. Mae swyddogaeth hash yn llinyn ac yn dychwelyd mynegai. Yn yr achos hwn, y mynegai wedi i fod yn llai na nifer y bwcedi sydd gennych. 

Yn awr, swyddogaethau hash, pan fyddwch yn ceisio i ddod o hyd i un a chreu un o eich pen eich hun, cofiwch eu bod yn rhaid iddynt fod yn benderfynedig. Mae hynny'n golygu bod angen i'r un gwerth i mapio ar draws i'r un bwced bob tro eich bod yn hash ei. 

Mae'n fath o fel llyfrgell. Pan fyddwch yn cymryd llyfr, yn seiliedig ar y awdur, chi'n gwybod pa silff y dylai yn mynd ymlaen, boed yn rhif silff un, dau, neu dri. Ac y bydd llyfr bob amser yn perthyn ar naill ai un silff, dau, neu dri. 

Felly, os saeth new_node gair gan y gair gan eich geiriadur, yna stwnsio new_node arrow gair yn rhoi y mynegai y ni bwced y tabl hash. Ac yna byddwn yn rhowch hynny i mewn i hynny rhestr gysylltiedig penodol a nodir gan y dychwelyd gwerth ein swyddogaeth hash. 

Gadewch i ni edrych ar enghraifft o mewnosod nod i mewn i'r ddechrau restr cysylltiedig. Os pen yn pwyntydd nod sy'n dangos ddechrau cysylltiedig rhestr, a new_node yn dangos y newydd nod yr ydych am i fynd i mewn i mewn, dim ond Byddai pennu pen i new_node colli y ddolen i weddill y rhestr. Felly, nid ydym am wneud hyn. 

Yn hytrach, rydym am wneud yn siŵr ein bod yn dal ar i bob un nod yn ein rhaglen. Felly, yn rhedeg saeth new_node hafal nesaf ben, ac yna pen hafal new_node Bydd cadw pob un o'r cysylltiadau ac nid yn colli unrhyw. 

Ond beth os ydych am i'ch rhestr hon fod yn didoli, oherwydd ar ôl a datrys cysylltiedig Efallai y rhestr yn haws i chwilio yn nes ymlaen? Wel, am hynny, bydd angen i chi ei wybod sut i groesi rhestrau cysylltiedig. 

Er mwyn croesi rhestr cysylltiedig, gadewch i ni gael pwyntydd nod, nod a *, i weithredu fel eich cyrchwr, nodi pa Node ydych chi yn y, gan ddechrau ar yr elfen gyntaf. Dolennu hyd nes y cyrchwr yn null, gallwn cynnal prosesau penodol ac yna symud y cyrchwr pan fydd angen ddefnyddio cyrchwr saeth gwerth. 

Cofiwch, mae hyn yn yr un peth â dweud cyrchwr seren, dereferencing cyrchwr, yna defnyddio'r gwerth gweithredwr dot. Felly diweddaru y cyrchwr drwy neilltuo y cyrchwr i saeth cyrchwr nesaf. 

Dywedwch eich bod chi benderfynu bod D yn dod yn rhwng C ac E. I fewnosod y nod, yn cael y pwynt new_node D i'r nod E, sy'n cyrchwr nesaf. Ac yna C, y cyrchwr, yna gall bwyntio i D. hynny, eich bod yn cynnal rhestr. Byddwch yn ofalus i beidio â cholli eich cysylltiadau gan symud y cyrchwr saeth nesaf i D ar unwaith. 

Mae pob hawl. Felly dyna sut y gallech mewnosod nodau, llwytho i mewn, geiriau llwyth i'r rhai nodau, a rhowch nhw yn eich tabl hash. Felly nawr gadewch i ni edrych ar gais. 

Mewn trie, bydd pob nod yn cynnwys amrywiaeth o awgrymiadau nod, un ar gyfer pob llythyr yn yr wyddor yn ogystal â collnod. Ac mae pob elfen yn yr arae Bydd cyfeirio at nod arall. Os mai nod yn null, yna y llythyr hwnnw nid yw'n mynd i fod yn y llythyr nesaf unrhyw air mewn dilyniant, gan fod pob gair yn nodi boed yn yr olaf cymeriad gair neu beidio. 

Gadewch i ni edrych ar ddiagram. Gobeithio y bydd pethau fod ychydig yn gliriach. Yn y diagram hwn, rydym yn gweld mai dim ond llythyrau penodol a rhai substrings yn cael eu rhestru allan. Felly, gallwch chi ddilyn llwybrau penodol, a Bydd pob un o'r llwybrau hynny yn eich arwain at geiriau gwahanol. 

Felly sut rydym yn cynrychioli hyn yn C? Wel, pob nod yn awr yn mynd i gael gwerth Boole nodi a y nod yw diwedd gair a roddir neu beidio. Ac yna bydd yn hefyd yn cael amrywiaeth o awgrymiadau nod a elwir yn blant, a mae mynd i fod yn 27 ohonynt. A chofiwch, byddwch hefyd yn awyddus i cadw golwg ar eich nod cyntaf. Rydym yn mynd i alw y gwraidd. 

Felly dyna strwythur trie. Sut yr ydym yn cynrychioli hon fel geiriadur? Wel, i lwytho geiriau i mewn, ar gyfer pob gair geiriadur, rydych chi'n mynd i fod eisiau i ailadrodd drwy'r trie. Ac mae pob elfen yn y plant cyfateb i lythyr gwahanol. 

Felly, gwirio gwerth at blant ff mynegai, lle i cynrychioli'r mynegai penodol y llythyr a ydych yn ceisio i fewnosod. Wel, os yw'n null, yna byddwch eisiau malloc yn nod newydd ac yn cael plant i dynnu sylw at y nod. 

Os nad yw'n null, yna mae hynny'n golygu bod y gangen a roddwyd, o ystyried is-linyn, eisoes yn bodoli. Felly, yna byddwch yn unig yn symud i'r nod newydd ac yn parhau. Os ydych chi ar ddiwedd y gair ydych yn ceisio llwytho yn y geiriadur, yna gallwch osod y nod ar hyn o bryd eich bod ar i gwir. 

Felly, gadewch i ni edrych ar enghraifft o mewnosod y gair "llwynog" yn ein geiriadur. Esgus i ni ddechrau gyda geiriadur wag. Bydd y llythyr cyntaf, F, yn cael eu lleoli yn y mynegai plant pump o'r gwreiddiau plant amrywiaeth. Felly, rydym yn mewnosod hynny mewn 

Bydd y llythyr O wedyn mewn plant mynegai 15, ar ôl hynny F. Ac yna X hyd yn oed yn is na hynny, canghennog i ffwrdd o blant y O i. Ac yna oherwydd X yw'r llythyren olaf y gair "llwynog," yna dwi'n mynd i lliw y gwyrdd i ddangos bod 'i' ddiwedd y gair. Yn C, a fyddai'n cael ei osod y Is Word Boole at y gwir werth. 

Nawr, beth os bydd y gair nesaf eich bod yn llwytho i mewn yn y gair "foo"? Wel, nid oes angen i chi malloc unrhyw mwy lle ar gyfer F neu am O, oherwydd hynny eisoes yn bodoli. Ond mae'r O olaf yn foo? Mae hynny'n un, bydd yn rhaid i malloc chi. Gwnewch nod newydd ar gyfer hynny, gan osod y Is Word Boole i gwir. 

Felly nawr gadewch i mewnosoder "ci." Bydd Cŵn yn dechrau gyda mynegai thri o'r gwreiddiau plant, gan nad yw D wedi eu creu eto. A byddwn yn dilyn proses debyg fel o'r blaen, gan greu y ci is-linyn, Ble mae'r G wedi ei lliwio'n wyrdd oherwydd dyna ddiwedd gair. 

Nawr, beth os ydym am i fewnosod "gwneud"? Wel, mae hyn yn is-linyn o gi, felly Nid oes angen i ni malloc anymore. Ond mae angen i ni i ddangos lle rydym wedi cyrraedd diwedd y gair. Felly bydd y O fod o liw gwyrdd. Parhau broses honno ar gyfer pob un gair yn eich geiriadur, eich bod wedi llwytho nhw yn naill ai eich hash bwrdd neu eich trie. 

Bydd speller.c pasio yn y llinynnau ar gyfer dictionary.c eu gwirio. Yn awr, y swyddogaeth Gwirio wedi i weithredu dan ansensitifrwydd achos. Mae hynny'n golygu bod llythyrau cyfalaf a llythrennau bach a chymysgedd o'r ddau dylai pob cyfateb i gwir os o gwbl cyfuniad o hynny yn y geiriadur. Gallwch hefyd gymryd yn ganiataol bod llinynnau yn unig yn mynd i gynnwys yn nhrefn yr wyddor cymeriadau neu gollnod. 

Felly, gadewch i ni edrych ar sut y gallwch wirio gyda strwythur bwrdd hash. Wel, os bydd y gair yn bodoli, yna mae'n i'w gweld yn y tabl hash. Felly, yna gallwch geisio dod o hyd bod gair yn y bwced perthnasol. 

Felly, pa bwced byddai y gair hwnnw mewn? Wel, byddech yn cael y nifer, y mynegai y bwced, trwy stwnsio gair hwnnw ac yna chwilio yn y rhestr honno cysylltiedig, croesi drwy'r cyfan rhestr gysylltiedig, gan ddefnyddio'r Llinynnol Cymharu swyddogaeth. 

Os yw diwedd y rhestr gysylltiedig yn gyrraedd, sy'n golygu bod eich cyrchwr cyrraedd null, yna nid y gair yn i'w cael yn y geiriadur. Ni fydd yn mewn unrhyw bwced arall. Felly yma, efallai y byddwch yn gweld sut y mae gallai fod yn fasnach-off rhwng cael naill ai rhestrau cysylltiedig didoli neu rai heb eu didoli. Bydd naill ai gymryd mwy o amser yn ystod llwytho na mwy o amser yn ystod y siec. 

Sut y gallai chi wirio yn strwythur trie? Rydym yn mynd i deithio i lawr yn y trie. Ar gyfer pob llythyren yn y gair ei fewnbynnu ein bod yn gwirio, byddwn yn mynd i'r elfen yn y plant cyfatebol. 

Os yr elfen honno yn null, yna mae hynny'n ei olygu nad oes unrhyw substrings cynnwys ein gair mewnbwn, felly y gair yn cael ei gamsillafu. Os nad yw'n null, gallwn symud at y llythyr nesaf y gair ein bod ni'n gwirio a pharhau broses hon nes i ni gyrraedd y diwedd y gair mewnbwn. Ac yna gallwn wirio os Is Word yn wir. Os ydyw, yna gwych. Mae'r gair yn gywir. Ond os nad yw, er bod y is-linyn yn bodoli yn y trie, bod y gair yn gamsillafu. 

Pan elwir y Maint swyddogaeth, maint ddychwelyd y nifer o eiriau sy'n yn eich geiriadur roddir strwythur data. Felly, os ydych yn defnyddio tabl hash, rydych yn naill ai fynd drwy bob un rhestr gysylltiedig ym mhob un bwced gyfrif y nifer o eiriau yno. Os ydych yn defnyddio trie, gallwch fynd drwy bob nad ydynt yn null llwybr yn eich trie. Neu wrth i chi lwytho'r geiriadur i mewn, efallai y gallwch gadw golwg ar faint llawer o eiriau rydych yn llwytho i mewn 

Unwaith y speller.c yn gorffen gwirio ffeil testun yn erbyn y geiriadur, yna mae'n ei wneud ac felly mae'n galw Dadlwytho, lle eich swydd yw unrhyw beth am ddim eich bod wedi malloced. Felly, os ydych yn defnyddio tabl hash, yna rydych Mae angen i fod yn arbennig o ofalus i osgoi gollwng cof drwy beidio ryddhau unrhyw beth gynamserol ac yn dal ar bob ddolen yn unig cyn i chi am ddim. 

Felly, ar gyfer pob elfen yn y tabl hash ac ar gyfer pob nod yn y rhestr cysylltiedig, byddwch chi eisiau i ryddhau y nod. Sut ydych chi'n mynd ati i ryddhau rhestr cysylltiedig? Gosod eich nod pwyntydd cyrchwr i y pennaeth, i gychwyn y rhestr gysylltiedig, yna pan fydd eich cyrchwr Nid yn null, gallwch chi osod dros dro nod pwyntydd at eich cyrchwr. Yna ymlaen llaw y cyrchwr. Ac yna gallwch rhad ac am ddim bod dros dro gwerth tra'n dal i gynnal ar popeth wedyn. 

Beth os ydych yn defnyddio trie? Yna y ffordd orau o wneud hyn yw i ddadlwytho o'r iawn gwaelod i'r brig. Drwy deithio i'r isaf posibl nod, gallwch rhad ac am ddim yr holl awgrymiadau yn bod plant ac yna mynd yn ôl i fyny, gan ryddhau holl elfennau ym mhob o'r araeau plant, hyd nes y byddwch yn taro eich nod gwraidd uchaf. Dyma lle recursion yn dod mewn 'n hylaw. 

I wneud yn siŵr ei bod yn debygol eich bod wedi rhyddhau popeth yr ydych wedi malloced, gallwch ddefnyddio Valgrind. Bydd Rhedeg Valgrind rhedeg eich rhaglen cyfrif faint o beit o gof ydych yn defnyddio a gwneud yn siŵr eich bod wedi rhyddhau nhw i gyd, yn dweud wrthych lle y gallech gael anghofio am ddim. Felly, yn cynnal y ac unwaith Valgrind yn dweud wrthych ac yn rhoi i chi y mynd yn ei flaen, yna eich bod wedi gorffen dadlwytho. 

Yn awr, mae ychydig o awgrymiadau cyn i chi fynd i ffwrdd a dechrau gweithredu eich geiriadur. Byddwn yn argymell i basio yn llai geiriadur pan fyddwch yn ceisio i brofi pethau a debugging gyda CMC. Y defnydd o sillafu yw. / Sillafu, mae geiriadur dewisol, ac yna testun. 

Yn ddiofyn, mae llwythi yn y geiriadur mawr. Felly, efallai y byddwch am i basio yn y bach geiriadur, neu efallai hyd yn oed wneud eich eu hunain, addasu eich geiriadur ac eich ffeil testun. 

Ac yna yn olaf, yr wyf byddwn hefyd yn argymell i gymryd beiro a phapur a thynnu pethau cyn, yn ystod, ac ar ôl eich bod wedi ysgrifennu eich holl cod. Jyst gwnewch yn siŵr eich bod wedi cael awgrymiadau hynny yn iawn. 

Hoffwn i chi y gorau o lwc. Ac unwaith y byddwch wedi gorffen, os hoffech i herio'r bwrdd mawr a weld pa mor gyflym eich rhaglen ei gymharu â eich cyd-ddisgyblion ', yna yr wyf yn annog i chi wirio hynny. 

Gyda hynny, rydych chi wedi gorffen y PSet sillafu. Fy enw i yw Zamyla, ac mae hyn yn CS50.