[Powered by Google Translate] [Walkthrough - 5 Set broblem] [Zamyla Chan - Harvard University] [Mae hyn yn CS50. - CS50.TV] 

Mae pob hawl. Helo, bawb, a chroeso i Walkthrough 5. 

Pset5 yn Camsillafu, y byddwn yn gwneud wirydd sillafu. Sillafu-gwirwyr yn hynod o bwysig. A yw hyn wedi digwydd i chi erioed? Byddwch yn gweithio iawn, iawn celc ar bapur ar gyfer y gem ac yna yn dal yn y pen draw cael rade glow iawn fel D neu D = a hynny oherwydd chi yw'r spoiler liverwurst yn y gair morfil eang. Ie, prawfddarllen eich pupurau yn fater o, y impotence mwyaf. Mae hon yn broblem sy'n effeithio ar manly, myfyrwyr manly. Dywedwyd wrthyf unwaith gan fy torturer gradd Sith na fyddwn byth yn mynd i mewn i gydweithiwr da. A dyna i gyd wyf erioed wedi eisiau, dyna i gyd am unrhyw blentyn yn fy oed i, dim ond i fynd i mewn i gydweithiwr da. Ac nid yn unig unrhyw gydweithiwr. Rhif Roeddwn i eisiau mynd i gydweithiwr Ivory Cyfreithiol. Felly, pe na byddwn wedi gwella, byddai mynd yn fy mreuddwydion o fynd i Harvard, Jale, neu Carchar - chi'n gwybod, yn y Carchar, New Jersey. Felly Cefais fy hun yn wirydd sillafu. Dyna darn bach o un o fy artistiaid gair llafar hoff, Taylor Mali. Beth bynnag, fel y dywed, y pwysigrwydd o gael wirydd sillafu yn bwysig iawn. 

Felly croeso i Walkthrough 5, y byddwn yn siarad am pset5: Camsillafu, y byddwn yn gwneud ein hunain gwirydd sillafu. Mae'r pecyn cymorth ar gyfer yr wythnos, y cod dosbarthu, yn mynd i fod yn bwysig edrych ar dim ond er mwyn deall y swyddogaethau gwahanol y mae eich geiriadur yn mynd i gael. Rydym yn wir yn mynd i fod yn cael ffeiliau c lluosog. Sydd gyda'i gilydd yn gwneud ein pset. Ac felly yn edrych drwy'r agweddau gwahanol, er nad ydym yn bod mewn gwirionedd yn golygu un o'r ffeiliau, speller.c, gan wybod sut y mae'n gweithio gyda perthynas â dictionary.c, y byddwn yn ei ysgrifennu, yn mynd i fod yn eithaf pwysig. Mae'r fanyleb pset hefyd yn cynnwys llawer o wybodaeth ddefnyddiol o ran pethau y gallwch eu cymryd yn ganiataol, rheolau a phethau fel 'na, felly gwnewch yn siŵr i ddarllen y fanyleb pset yn ofalus am awgrymiadau. Ac os ydynt yn ansicr o reol neu rywbeth fel 'na, yna bob amser yn cyfeirio at y fanyleb pset neu Trafodwch. Mae'r pset yn mynd i ddibynnu'n drwm ar awgrymiadau, felly rydym yn awyddus i wneud yn siŵr ein bod yn deall y gwahaniaeth rhwng y sêr ychwanegu o flaen enw y pwyntydd a ampersands, sut i'w rhyddhau, ac ati Felly, fod yn feistr o awgrymiadau yn mynd i fod yn ddefnyddiol iawn yn y set hon broblem. Rydym yn mynd i edrych i mewn rhestrau cysylltiedig ychydig yn fwy, lle mae gennym elfennau yr ydym yn galw nodau sydd wedi ddau werth yn ogystal â pwyntydd at y nod nesaf, ac felly yn ei hanfod yn cysylltu gwahanol elfennau un ar ôl y llall. Mae yna ychydig o ddewisiadau gwahanol o weithredu eich geiriadur gwirioneddol. Rydym yn mynd i edrych i mewn dau brif ddull, sy'n tablau hash ac wedyn yn ceisio. Yn y ddau o'r rheiny, maent yn cynnwys rhyw fath o syniad o restr sy'n gysylltiedig lle rydych wedi elfennau sy'n gysylltiedig â'i gilydd. Ac felly rydym ni'n mynd i edrych dros sut efallai y byddwch yn gallu gweithredu o ran rhestrau cysylltiedig, eu creu, llywio o ran sut i, er enghraifft, rhowch nod i mewn iddo neu am ddim bob un o'r nodau yn ogystal. O ran nodau rhyddhau, mae hynny'n bwysig iawn pa bryd bynnag y cof malloc, wedyn rydym yn rhyddhau ei. Felly, rydym am wneud yn siŵr nad oes unrhyw pwyntydd yn mynd unfreed, nad oes gennym unrhyw ollyngiadau cof. Rydym yn mynd i gyflwyno dull o'r enw Valgrind sy'n rhedeg eich rhaglen a gwiriadau a oedd yr holl cof eich bod yn dyrannu ei ryddhau wedyn. Eich pset yn unig gwblhau pan fydd yn gweithio ac mae ymarferoldeb llawn, ond hefyd, Valgrind yn dweud wrthych nad ydych wedi dod o hyd unrhyw ollyngiadau cof. Yn olaf, ar gyfer y pset, Rwy'n awyddus iawn i bwysleisio - Yr wyf yn golygu, fel arfer, yr wyf yn sicr yn gefnogwr o ddefnyddio pen a phapur ar gyfer eich setiau problem, ond ar gyfer yr un yma, credaf fod pen a phapur yn mynd i fod yn arbennig o bwysig pan fyddwch eisiau cael tynnu saethau i bethau a deall sut mae pethau'n gweithio. Felly, yn bendant yn ceisio defnyddio pin a phapur i dynnu pethau allan cyn i chi gael codio oherwydd gallai gael ychydig anniben. 

Yn gyntaf, gadewch i ni fynd i mewn i restrau cysylltiedig ychydig. Rhestrau cysylltiedig yn cynnwys nodau, lle mae pob nod werth sy'n gysylltiedig ag ef, yn ogystal â rhoi syniad inni am y nod nesaf ar ei ôl. Mae cwpl o bethau pwysig gyda'r rhestrau cysylltiedig y mae angen inni i gofio lle mae ein nod cyntaf yw, ac yna ar ôl i ni wybod ble y nod cyntaf yw, y ffordd y gallwn gael mynediad i'r nod fod y pwyntiau nod cyntaf i ac yna yr un ar ôl hynny ac un ar ôl hynny. Ac yna yr elfen olaf yn eich rhestr cysylltiedig yn pwyntydd y nod yn bob amser yn mynd i dynnu i NULL. Pan fydd pwyntiau nod i NULL, yna rydych yn gwybod eich bod wedi cyrraedd diwedd y rhestr, bod y nod yw'r un olaf, nad oes dim ar ôl hynny. Yma yn y sgematig, gwelwch fod y saethau yw'r awgrymiadau, a'r adran glas yn lle mae'r gwerth yn cael ei storio, ac yna y blwch coch gyda'r pwyntydd i fod yn pwyntydd y nod yn pwyntio at y nod nesaf ar ei ôl. Ac felly byddwch yn gweld yma, byddai'r nod D pwynt i nwl oherwydd ei fod yn elfen olaf yn y rhestr. 

Gadewch i ni edrych ar sut y gallem ddiffinio strwythur ar gyfer nod. Ac ers i ni am gael nodau lluosog, hyn yn mynd i ddod yn strwythur typedef lle rydym yn mynd i gael enghreifftiau gwahanol o nodau. Ac felly rydym yn ei ddiffinio fel math data newydd. Yma, mae gennym nod strwythur typedef. Yn yr enghraifft hon, rydym yn delio â nodau cyfanrif, felly mae gennym werth cyfanrif a enwir ac yna mae gennym arall pwyntydd, ac yn yr achos hwn, mae'n pwyntydd i nod, felly mae gennym nod strwythur * a elwir yn nesaf. Ac yna rydym yn galw hyn yn nod holl beth. Gwnewch yn siŵr eich bod yn dilyn y gystrawen. Hysbysiad bod nod wedi ei gyfeirio mewn gwirionedd i fyny uchod, yn ogystal fel y nodir isod y braces cyrliog. Yna i gadw cofnod o lle mae fy nod cyntaf yw yn y rhestr cysylltiedig, hynny, rwyf wedi pwyntydd cainc o'r enw pen, a gofod malloc wyf ddigon ar gyfer maint y nod. Rhybudd, fodd bynnag, bod pennaeth mewn gwirionedd yn pwyntydd nod o'i gyferbynnu â nod ei hun. Felly, y pennaeth mewn gwirionedd nid yw'n cynnwys unrhyw werth, dim ond yn cyfeirio at ba un bynnag y nod cyntaf yn fy rhestr cysylltiedig yn. 

I gael syniad gwell o restrau cysylltiedig, oherwydd ei fod yn bwysig iawn i gadw golwg ar wneud yn siŵr eich bod yn cynnal y gadwyn, Rwy'n hoffi meddwl ohono fel pobl mewn llinell yn dal dwylo, lle mae pob person yn dal dwylo gyda yr un nesaf. Ni allwch weld yn y llun, ond yn y bôn maent yn pwyntio at y person nesaf sydd yn eu cadwyn. Ac felly os ydych am deithio ar draws rhestr cysylltiedig lle mae'r bobl hyn - dychmygu pob un o'r bobl hynny gwerthoedd sy'n gysylltiedig â hwy a hefyd yn cyfeirio at y person nesaf yn y llinell - os ydych am i groesi'r rhestr cysylltiedig, er enghraifft, naill ai i olygu'r gwerthoedd neu chwilio am werth neu rywbeth fel 'na, yna byddwch chi eisiau i gael pwyntydd i'r person penodol. Felly, rydym yn mynd i gael data fath pwyntydd nod. Er yr achos hwn, gadewch i ni ei alw cyrchwr. Arall fyddai ffordd gyffredin i enwi hyn yn iterator neu rywbeth fel 'na oherwydd ei fod yn ailadrodd drosodd ac mewn gwirionedd yn symud y nod ei fod yn pwyntio at. Bydd hyn dyma fydd ein cyrchwr. Bydd ein cyrchwr 1 yn cyfeirio at yr elfen gyntaf yn ein rhestr. Ac felly yr hyn yr ydym am ei wneud yw y byddai yn y bôn rydym yn parhau y cyrchwr, symud o ochr i ochr. Yn yr achos hwn, rydym am symud i'r elfen nesaf yn y rhestr. Gyda arrays, beth y byddem yn ei wneud yw y byddem yn unig yn dweud ein bod yn cynyddu'r mynegai erbyn 1. Yn yr achos hwn, yr hyn y mae angen i ni ei wneud yw mewn gwirionedd yn dod o hyd i pa berson y person hwn ar hyn o bryd yn pwyntio at, ac mae hynny'n mynd i fod yn werth nesaf. Felly, os cyrchwr yn unig yw pwyntydd nod, yna beth yr ydym am ei wneud yw ein bod am i gyrraedd y gwerth y mae'r cyrchwr yn pwyntio i. Rydym yn awyddus i gyrraedd y nod, ac yna, unwaith y byddwn ni'n ar y nod, dod o hyd i ble mae'n pwyntio at. I gyrraedd y nod go iawn y mae'r cyrchwr yn pwyntio at, Fel arfer, rydym yn nodi iddo gan (* cyrchwr). Byddai hynny'n rhoi i chi y nod go iawn y mae'r cyrchwr yn pwyntio i. Ac yna ar ôl hynny, yr hyn rydym am ei wneud yw ein bod am gael mynediad beth bynnag yw gwerth nod nesaf yw. I wneud hynny, i gael mynediad i'r gwerthoedd tu mewn i'r strwythur, mae gennym y gweithredwr dot. Felly, yna byddai'n (* cyrchwr). Nesaf. Ond mae hyn yn ychydig yn flêr o ran cael y cromfachau o gwmpas y cyrchwr *, ac felly rydym yn cymryd lle'r datganiad hwn cyfan gyda cyrchwr->. Mae hwn yn dash ac yna arwydd mwy na, felly gwneud saeth. cyrchwr-> nesaf. Bydd hynny mewn gwirionedd yn mynd â chi y nôd bod y pwyntiau cyrchwr. Bod y gwerth hwnnw'n o nesaf. Felly, yn lle cael y seren a'r dot, rydych yn disodli'r gyda saeth. Byddwch yn ofalus iawn i wneud yn siŵr eich bod yn ceisio defnyddio'r gystrawen. 

Nawr ein bod wedi ein cyrchwr, os ydym am i gael mynediad i'r gwerth, o'r blaen, cawsom cyrchwr-> nesaf, ond i gael mynediad i'r gwerth ar y nod bod y cyrchwr yn pwyntio at, rydym yn unig yn syml yn dweud nod-> werth. Oddi yno, mae'n fath o ddata beth bynnag rydym wedi diffinio'r gwerthoedd a'r nodau i fod. Os yw'n nod int, yna cyrchwr-> werth yn unig yn mynd i fod yn gyfanrif. Felly gallwn wneud gweithrediadau ar hynny, gwirio cydraddoldeb, neilltuo ei werthoedd gwahanol, ac ati Felly, yna beth rydych am ei wneud os ydych am symud eich cyrchwr at y person nesaf, chi mewn gwirionedd yn newid gwerth y cyrchwr. Gan cyrchwr yn bwyntydd nod, byddwch yn newid y cyfeiriad pwyntydd gwirioneddol i gyfeiriad y nod nesaf yn eich rhestr. Mae hyn yn dim ond rhai cod lle y gallech ailadrodd. Ble alla i gael y sylw wneud rhywbeth, dyna lle mae'n debyg eich bod yn mynd i gael y gwerth neu wneud rhywbeth i wneud gyda'r nod penodol. I gychwyn i ffwrdd, yr wyf yn dweud bod fy cyrchwr i ddechrau yn mynd i gyfeirio at yr elfen gyntaf yn y rhestr cysylltiedig. Ac felly i fyny i ddod, rwy'n ddiffinio fel pennaeth y nod. 

Fel y soniais o'r blaen, gan ryddhau yn wirioneddol bwysig. Byddwch am wneud yn siŵr eich bod yn rhyddhau pob elfen yn y rhestr unwaith y byddwch wedi gorffen ag ef. Pan nad oes angen i chi gyfeirio at unrhyw un o'r awgrymiadau anymore, ydych am wneud yn siŵr eich bod yn rhyddhau pawb awgrymiadau. Ond ydych chi am fod yn ofalus iawn yma yn yr ydych am osgoi unrhyw ollyngiadau cof. Os ydych yn rhad ac am ddim un person yn rhy gynnar, yna mae'r holl arwyddion bod pwyntiau nod i yn mynd i gael eu colli. Fynd yn ôl at yr enghraifft person i'w gwneud yn ychydig yn fwy stakes uchel, gadewch i ni gael y bobl hyn, ac eithrio yn yr achos hwn y maent yn hofran dros llyn gyda anghenfil. Rydym eisiau gwneud yn siŵr bod pryd bynnag y byddwn yn rhyddhau, nad ydym yn colli a gadael i fynd o unrhyw nodau cyn i ni ryddhau mewn gwirionedd nhw. Er enghraifft, os ydych i wneud dim ond ffoniwch am ddim ar y boi yma, yna byddai'n cael ei ryddhau, ond yna byddai pob un o'r rhain guys wedyn yn cael eu colli a byddent yn drifft i ffwrdd ac yn syrthio i lawr. Felly, rydym am wneud yn siŵr bod lle hynny, rydym am gynnal cyswllt â'r gweddill. Mae ein, pwyntydd pen sy'n cyfeirio at yr elfen gyntaf yn y rhestr. Mae'n fath o fel rhaff angori y person cyntaf. Beth efallai y byddwch am ei wneud pan fyddwch yn rhyddhau rhestr yn cael - Os ydych am i ryddhau yr elfen gyntaf yn gyntaf, yna gallwch gael pwyntydd dros dro bod pwyntiau i beth bynnag yr elfen gyntaf yn. Felly, rydych yn cael eich pwyntydd dros dro pwyntio yma. Y ffordd honno, mae gennym gafael ar y nod cyntaf. Ac yna, gan ein bod yn gwybod bod y nod cyntaf yn mynd i gael eu rhyddhau, yna gallwn symud y rhaff, mae hyn yn angor, mae ein pennaeth, i mewn gwirionedd yn pwyntio i beth bynnag yr un cyntaf yn pwyntio at. Felly, mae hyn mewn gwirionedd pen yn cyfeirio at yr ail elfen yn awr. Nawr rydym yn cael i ryddhau beth bynnag yn cael ei storio mewn adeiladau dros, ac felly gallwn ddileu, heb ei beryglu pob un o'r nodau eraill yn ein rhestr. Gallai ffordd arall y gallech wneud hyn fyddai bob tro y byddwch yn unig ryddhau yr elfen olaf yn y rhestr oherwydd eu bod yn sicr o beidio gael eu hamlygu i unrhyw beth. Felly, fe allech chi jyst ryddhau yr un yma, yna ddim yr un, yna ddim yr un. Mae hynny'n bendant yn gweithio, ond ychydig yn arafach oherwydd erbyn natur y rhestrau cysylltiedig, Ni allwn yn unig yn syth neidio i'r un diwethaf. Mae'n rhaid i ni deithio ar draws pob elfen yn y rhestr sy'n gysylltiedig a gwirio a bod un yn pwyntio at null, gwirio bob tro, ac yna unwaith rydym yn cyrraedd y diwedd, yna rhad ac am ddim hynny. Pe baech yn gwneud y broses hon, byddech mewn gwirionedd yn gwirio yma, gwirio yma, yna gwirio yma, gan ryddhau ei, yna mynd yn ôl, gan wirio yma, gwirio yma, gan ryddhau ei, gwirio yma, ac yna rhyddhau ei. Mae hynny'n cymryd ychydig mwy o amser. Yeah. 

[Myfyrwyr] A fyddai'n bosibl i wneud rhestr cysylltiedig sy'n storio yn bwyntydd allanfa i'r diwedd? Byddai hynny'n sicr yn bosibl. I ailadrodd y cwestiwn, a yw'n bosibl cael strwythur restr cysylltiedig fel bod gennych pwyntydd pwyntio at ddiwedd y rhestr sy'n gysylltiedig? Byddwn i'n dweud hynny'n bosibl, a bob tro y byddwch rhoi rhywbeth yn eich rhestr cysylltiedig byddai'n rhaid i chi ddiweddaru'r pwyntydd a phethau fel 'na. Byddai gennych gynffon * nod, er enghraifft. Ond pan fyddwch yn gweithredu'r nodwedd, rhaid i chi feddwl am y fasnach-offs, fel faint o weithiau ydw i'n mynd i gael ei ailadrodd dros hyn, pa mor anodd y mae'n mynd i fod i gadw golwg ar y gynffon yn ogystal â'r pennaeth yn ogystal â'm iterator, a phethau fel 'na. A yw hynny'n -? >> [Myfyrwyr] Yeah. Mae'n bosibl, ond o ran penderfyniadau dylunio, rhaid i chi bwyso a mesur yr opsiynau. 

Dyma sgerbwd o god a fyddai'n caniatáu i chi i ryddhau pob elfen mewn rhestr cysylltiedig. Unwaith eto, gan fy mod i'n ailadrodd dros rhestr cysylltiedig, dw i'n mynd i eisiau cael rhyw fath o cyrchwr neu iterator. Rydym yn ailadrodd nes bod y cyrchwr yn null. Nid ydych am i ailadrodd pan fydd eich cyrchwr yn null oherwydd mae hynny'n golygu nad oes unrhyw beth yn y rhestr. Felly, yna dyma wyf yn gwneud * nod dros dro dynnu sylw at yr hyn rwy'n ei ystyried yw'r cyntaf o fy rhestr, ac yna mi symud fy cyrchwr ymlaen 1 ac yna rhad ac am ddim beth bynnag yr wyf wedi'i gael yn y storfa dros dro. 

Nawr rydym yn dod i mewnosod mewn rhestrau cysylltiedig. Mae gennyf dri nodau yn fy rhestr gysylltiedig, a gadewch i ni fynd â'r achos syml lle rydym am mewnosod un arall nod ar ddiwedd ein rhestr cysylltiedig. I wneud hynny, y cyfan byddem yn ei wneud yw y byddem yn tramwyo i ddod o hyd lle y diwedd presennol y rhestr cysylltiedig yw, felly pa bynnag nod yn pwyntio at NULL - dyna yr un yma - ac yna dweud, mewn gwirionedd, nid yw'r un yn mynd i fod y nod olaf; rydym yn wir yn mynd i gael un arall. Felly, byddai gennym y cerrynt un pwynt i beth bynnag yr ydym yn gosod. Felly, yn awr, y person goch yma yn dod y nod olaf yn y rhestr cysylltiedig. Ac felly y nodwedd y nod olaf yn y rhestr cysylltiedig yw ei fod yn cyfeirio at NULL. Felly, yna beth y byddai'n rhaid inni ei wneud yw gosod pwyntydd y boi coch i NULL. Mae yna. 

Ond beth os ydym eisiau i osod nod mewn rhwng yr un ail a'r trydydd? Nad yw rhywun yn mor syml oherwydd ein bod eisiau gwneud yn siwr nad ydym yn gadael i fynd o unrhyw nod yn ein rhestr cysylltiedig. Beth byddai'n rhaid i ni ei wneud yw gwneud yn siŵr ein bod yn angori ein hunain i bob un. Er enghraifft, gadewch i ni yn galw hyn yn ail un. Os byddwch yn dweud yr ail un yn awr yn cyfeirio at yr un newydd a 'ch jyst gwneud pwyntydd yno, yna byddai hynny'n arwain at y boi yn cael ei golli oherwydd nad oes unrhyw gysylltiad ag ef. Yn lle hynny - 'N annhymerus' tynnu hyn eto. Esgusodwch fy galluoedd artistig. Rydym yn gwybod na allwn yn unig yn cysylltu'n uniongyrchol 2 i un newydd. Mae'n rhaid i ni wneud yn siŵr ein bod yn dal gafael ar yr un ddiwethaf. Yr hyn yr hoffem ei wneud yw cael pwyntydd dros dro i'r elfen sy'n mynd i gael ei atodi ar. Felly, yna mae gennym pwyntydd dros dro yno. Ers i ni yn gwybod bod yr un trydydd cael ei gadw golwg ar, 2 Mae cyswllt yn awr at ein un newydd. Ac os yw hyn yn guy coch newydd yn mynd i fod rhwng 2 a 3, yna beth yw pwyntydd y dyn yn mynd i gyfeirio at? >> [Myfyrwyr] Temp. Temp. Yeah. Felly, yna werth y boi coch nesaf yn mynd i fod dros dro. Pan fyddwch chi'n gosod mewn rhestrau cysylltiedig, gwelsom y gallem yn hawdd ychwanegu rhywbeth at y diwedd drwy greu amrywiaeth dros dro, neu os ydym am ychwanegu rhywbeth i ganol ein amrywiaeth, yna byddai'n cymryd ychydig yn fwy anghyfforddus. Os ydych chi eisiau, er enghraifft, restr datrys cysylltiedig, yna rhaid i chi math o bwyso a mesur y costau a manteision hynny oherwydd os ydych am gael amrywiaeth datrys, mae hynny'n golygu bod bob tro y rhowch i mewn iddo, mae'n mynd i gymryd ychydig mwy o amser. Fodd bynnag, os ydych am i yn nes ymlaen, gan y byddwn yn dod o hyd y byddwn yn dymuno, chwilio trwy restr gysylltiedig, yna efallai y byddai'n haws os ydych yn gwybod bod popeth mewn trefn. Felly, efallai y byddwch am bwyso a mesur costau a manteision hynny. 

Ffordd arall i fewnosod i mewn i restr cysylltiedig yw i fewnosod yn dechrau o restr. Os byddwn yn tynnu ein angor yma - mae hyn yn ein pen - ac yna wedi y bobl gysylltiedig ag ef, ac yna mae gennym nod newydd gael ei mewnosod yn y dechrau, yna efallai y hyn yr ydym eisiau ei wneud? Beth fyddai o'i le gyda dim ond dweud yr wyf am gysylltu'r goch at y glas, oherwydd dyna yr un cyntaf? Beth fyddai'n digwydd yma? Byddai pob un o'r tri yn mynd ar goll. Felly, nid ydym am wneud hynny. Unwaith eto, rydym wedi dysgu bod angen i ni gael rhyw fath o pwyntydd dros dro. Gadewch i ni ddewis cael bwynt dros dro at y boi. Yna gallwn gael y glas un pwynt dros dro ac yna y pwynt coch at y glas. Y rheswm pam yr wyf yn defnyddio pobl yma oherwydd ein bod wir eisiau i ddychmygu dal ar i bobl a sicrhau bod gennym gyswllt â hwy cyn i ni adael i fynd o llaw arall neu rywbeth fel 'na. 

Nawr bod gennym synnwyr o restrau cysylltiedig - sut y gallwn greu rhestr cysylltiedig a chreu'r strwythurau ar gyfer y cynnwys y diffiniad math ar gyfer nod ac yna gwneud yn siwr bod gennym syniad inni am y pennaeth y rhestr cysylltiedig - unwaith y byddwn wedi hynny, ac rydym yn gwybod sut i groesi drwy amrywiaeth, mynediad gwahanol elfennau, rydym yn gwybod sut i fewnosod ac rydym yn gwybod sut i'w rhyddhau, yna gallwn fynd i mewn i gamsillafu. Fel arfer, mae gennym adran o gwestiynau a fydd yn cael a ddefnyddiwyd gennych i weithredu gyda rhestrau cysylltiedig a strwythurau gwahanol fel ciwiau a staciau. Yna, gallwn symud i mewn i gamsillafu. 

Camsillafiadau wedi bod yn y cod dosbarthu ychydig o ffeiliau pwysig. Yn gyntaf rydym yn sylwi bod gennym y Makefile yma, nad ydym wedi dod ar eu traws mewn gwirionedd o'r blaen. Os ydych yn edrych y tu mewn i'r ffolder pset5, byddech yn sylwi bod gennych. Ffeil h, yna mae gennych ddau. ffeiliau c. Beth mae hyn yn Makefile yn ei wneud o'r blaen, byddem yn jyst deipio gwneud ac yna enw'r rhaglen ac yna byddem yn gweld pob un o'r dadleuon hyn a baneri pasio i mewn i'r casglwr. Beth mae'r Makefile yn ei wneud yn ein galluogi i lunio nifer o ffeiliau ar yr un pryd ac yn pasio yn y baneri yr ydym am. Yma, rydym yn unig yn gweld bod yna ffeil pennawd yma. Yna rydym mewn gwirionedd yn cael dwy ffeil ffynhonnell. Mae gennym speller.c a dictionary.c. Mae croeso i chi olygu'r Makefile os ydych yn dymuno. Sylwch mai yma os ydych yn teipio yn lân, yna beth mae'n ei wneud yw mewn gwirionedd yn cael gwared ar unrhyw beth dyna graidd. Os cawsoch wall, yn y bôn byddwch yn cael tomen craidd. Felly, bydd y ffeil bach hyll yn ymddangos yn eich cyfeiriadur o'r enw craidd. Youll 'angen i gael gwared ar y mwyn ei gwneud yn lân. Mae'n cael gwared unrhyw ffeiliau exe a. Ffeiliau o. 

Gadewch i ni edrych i mewn i dictionary.h. Mae hwn yn dweud ei fod yn datgan ymarferoldeb geiriadur yn. Mae gennym hyd ar y mwyaf am unrhyw air yn y geiriadur. Rydym yn dweud bod hyn yn mynd i fod y gair hiraf posibl. Mae o hyd 45. Felly nid ydym yn mynd i gael unrhyw eiriau sy'n rhagori ar y darn hwnnw. Yma, rydym yn unig yn cael y prototeipiau swyddogaeth. Nid oes gennym y gweithredu gwirioneddol oherwydd dyna beth y byddwn yn ei wneud ar gyfer y pset. Ond beth mae hyn yn ei wneud yw gan ein bod yn delio gyda ffeiliau mawr yma ac ymarferoldeb ar raddfa fwy, mae'n ddefnyddiol i gael. ffeil h fel y gall rhywun arall ddarllen neu ddefnyddio eich cod yn deall beth sy'n mynd ymlaen. Ac efallai y maent am ei weithredu yn ceisio pe baech yn gwneud tablau hash neu i'r gwrthwyneb. Yna byddent yn dweud fy swyddogaeth llwyth, gweithredu gwirioneddol yn mynd i anghytuno, ond ni fydd hyn yn prototeip yn newid. Yma, rydym wedi gwirio, sy'n dychwelyd wir os gair a roddir yn y geiriadur. Yna, mae gennym lwyth, sydd yn y bôn yn cymryd mewn ffeil geiriadur ac yna yn llwytho'r i mewn rhywfaint o strwythur data. Mae gennym maint, a fydd, pan elwir, yn dychwelyd y maint eich geiriadur, faint o eiriau yn cael eu storio ynddo, ac yna dadlwytho, sy'n rhyddhau pob cof y gallech fod wedi cymryd wrth wneud eich geiriadur. 

Gadewch i ni edrych ar dictionary.c. Rydym yn gweld ei bod yn edrych yn debyg iawn i dictionary.h, ac eithrio nawr mae'n mae pob un o'r rhain TODOs ynddo. Ac felly dyna yw eich swydd. Yn y pen draw, byddwch yn llenwi allan speller.c gyda phob un o'r cod hwn. Dictionary.c, pan yn rhedeg, yn cael ei wir yn mynd i wneud unrhyw beth, felly rydym yn edrych tuag at speller.c weld gweithredu gwirioneddol y gwirydd sillafu. Hyd yn oed os nad ydych chi'n mynd i fod yn golygu unrhyw un o'r cod hwn, mae'n bwysig i ddarllen, deall pryd mae llwyth alw, pan ydw i'n galw siec, dim ond er mwyn deall, fapio allan, gweld sut mae'r swyddogaeth yn gweithio. Rydym yn gweld ei fod yn gwirio ar gyfer y defnydd cywir. Yn y bôn, pan fydd rhywun yn rhedeg sillafu, mae hyn yn dangos ei fod yn ddewisol iddynt basio mewn ffeil geiriadur oherwydd mae mynd i fod yn ddiofyn ffeil geiriadur. Ac yna mae'n rhaid iddynt basio yn y testun i fod yn sillafu gwirio. yn delio rusage gydag amser oherwydd bod rhan o'r pset y byddwn yn delio â ddiweddarach nid yn unig yn cael gweithredu gywiriadur gweithio ond mewn gwirionedd yn cael i fod yn gyflym. Ac felly, yna dyna lle rusage yn mynd i ddod i mewn Yma, rydym yn gweld y galwad cyntaf i un o'n ffeiliau dictionary.c, sef llwyth. Llwyth yn dychwelyd gwir neu ffug - yn wir ar lwyddiant, ffug ar fethiant. Felly, os nad yw'r geiriadur yn cael ei lwytho yn gywir, yna bydd y speller.c yn dychwelyd 1 a rhoi'r gorau iddi. Ond os bydd yn gwneud llwyth yn gywir, yna mae'n mynd i barhau. Rydym yn parhau, ac rydym yn gweld rhywfaint o ffeil gallaf / O yma, lle mae'n mynd i fod yn delio ag agor y ffeil testun. Yma, beth mae hyn yn ei wneud yn sillafu profion bob un gair yn y testun. Felly beth speller.c yn ei wneud yn iawn yma yn ailadrodd dros bob un o'r geiriau yn y ffeil testun ac yna eu gwirio yn y geiriadur. Yma, mae gennym Boolean gamsillafu a fydd yn gweld os gwiriad yn dychwelyd wir neu beidio. Os ydy'r gair yn mewn gwirionedd yn y geiriadur, yna bydd gwiriad yn dychwelyd yn wir. Mae hynny'n golygu nad yw'r gair yn cael ei gamsillafu. Byddai gamsillafu Felly fod yn ffug, a dyna pam mae gennym y bang yno, yr arwydd. Rydym yn dal i fynd, ac yna mae'n cadw golwg ar faint o gamsillafu geiriau sydd yn y ffeil. Mae'n parhau a ddaw i ben ar y ffeil. Yna dyma, mae'n adrodd faint o eiriau wedi'u camsillafu a gawsoch. Mae'n cyfrifo faint o amser a gymerwyd i lwytho'r geiriadur, faint o amser a gymerwyd i wirio ei fod, faint o amser a gymerwyd i gyfrifo maint, y dylai, gan y byddwn yn mynd ymlaen, fod yn fach iawn, ac yna faint o amser a gymerwyd i ddadlwytho'r geiriadur. Yma i fyny uchod rydym yn gweld yr alwad i ddadlwytho yma. Os byddwn yn gwirio ar gyfer maint yma, yna rydym yn gweld bod yma yr alwad i faint pan fydd yn penderfynu maint y geiriadur. Awesome. 

Ein tasg ar gyfer y pset yw gweithredu llwyth, a fydd yn llwytho'r geiriadur strwythur data - pa un bynnag a ddewiswch, boed yn dabl hash neu roi cynnig ar - gyda geiriau o'r ffeil geiriadur. Yna byddwch yn cael faint, a fydd yn dychwelyd y nifer o eiriau yn y geiriadur. Ac os ydych yn gweithredu llwyth mewn ffordd smart, yna dylai maint fod yn eithaf hawdd. Yna, rydych wedi gwirio, a fydd yn gwirio os yw gair a roddir yn y geiriadur. Felly speller.c pasio mewn llinyn, ac yna rhaid i chi wirio a yw'r llinyn wedi'i gynnwys o fewn eich geiriadur. Hysbysiad bod gennym gyffredinol, mae geiriaduron safonol, ond yn yr pset, yn y bôn unrhyw eiriadur a basiwyd yn mewn unrhyw iaith. Felly, ni allwn gymryd yn ganiataol bod y gair Y tu mewn. Gallai'r Foobar gair yn cael ei ddiffinio mewn geiriadur penodol yr ydym yn pasio i mewn Ac yna rydym wedi dadlwytho, sy'n rhyddhau y geiriadur ar y cof. 

Yn gyntaf, hoffwn i fynd dros y dull tabl hash ynghylch sut y gallem weithredu pob un o'r rhai pedair swyddogaeth, ac yna byddaf yn mynd dros y ceisio dull, sut rydym yn gweithredu'r rhai pedair swyddogaeth, ac ar ddiwedd y sgwrs am rai awgrymiadau cyffredinol pan fyddwch yn gwneud y pset a hefyd sut y byddwch yn gallu defnyddio Valgrind i wirio am ollyngiadau cof. 

Gadewch i ni fynd i mewn i'r dull tabl hash. Mae tabl hash yn cynnwys rhestr o fwcedi. Mae pob gwerth, pob gair, yn mynd i fynd i mewn i un o'r rhain bwcedi. Mae tabl hash yn ddelfrydol gyfartal yn dosbarthu pob un o'r gwerthoedd hyn eich bod yn pasio yn ac yna poblogi'r yn y bwced fel bod pob bwced Mae am nifer gyfartal o werthoedd ynddo. Mae'r strwythur ar gyfer tabl hash, mae gennym amrywiaeth o rhestrau cysylltiedig. Beth rydym yn ei wneud yw pan fyddwn yn pasio mewn gwerth, byddwn yn gwirio ble y dylai'r gwerth perthyn, sy'n bwced mae'n perthyn iddo, ac yna ei ddodi yn y rhestr cysylltiedig sy'n gysylltiedig â'r bwced. Yma, yr hyn sydd gennyf yn swyddogaeth hash. Mae'n tabl hash int. Felly, ar gyfer y bwced cyntaf, unrhyw gyfanrifau llai na 10 yn mynd i mewn i'r bwced cyntaf. Unrhyw gyfanrifau yn uwch na 10 ond islaw 20 yn mynd i mewn i'r ail, ac yna yn y blaen ac yn y blaen. I mi, mae pob bwced yn cynrychioli rhifau hyn. Fodd bynnag, yn dweud bawn yn pasio yn 50, er enghraifft. Mae'n ymddangos fel pe y tri cyntaf yn cynnwys ystod o deg rhif. Ond yr wyf am ganiatáu fy tabl hash i'w cymryd mewn unrhyw fath o gyfanrifau, felly, yna byddai'n rhaid i mi hidlo allan yr holl rifau uwch na 30 i mewn i'r bwced diwethaf. Ac felly, yna a fyddai'n arwain at fath o dabl anghytbwys hash. I ailadrodd, tabl hash yn unig yw amrywiaeth o bwcedi lle mae pob bwced yn rhestr cysylltiedig. Ac felly i benderfynu lle mae pob gwerth yn mynd, a bwced yn mynd i mewn i, ydych yn mynd i eisiau hyn a elwir yn swyddogaeth hash sy'n cymryd gwerth ac yna'n dweud bod hyn yn cyfateb i werth bwced penodol. Felly, uwchben yn yr enghraifft hon, fy swyddogaeth hash yn cymryd pob gwerth. Mae'n wirio a oedd yn llai na 10. Os oedd, byddai'n ei roi yn y bwced cyntaf. Mae'n gwirio p'un a yw'n llai na 20, yn rhoi i mewn yr ail, os yw'n wir, gwiriadau os yw'n llai na 30, ac yna'n rhoi i mewn i'r bwced trydydd, ac yna popeth arall yn unig yn disgyn i'r bwced pedwerydd. Felly, pryd bynnag y byddwch yn cael gwerth, eich swyddogaeth hash Bydd yn gosod y gwerth i mewn i'r bwced priodol. Mae'r swyddogaeth hash y bôn mae angen i wybod faint o fwcedi gennych. Eich maint y tabl hash, mae nifer o bwcedi sydd gennych, mae hynny'n mynd i fod yn nifer penodedig sydd hyd i chi, er mwyn i chi benderfynu, ond mae'n mynd i fod yn nifer penodedig. Felly eich swyddogaeth hash byddan nhw'n dibynnu ar hynny i benderfynu pa bwced i bob allweddol yn mynd i mewn i o'r fath fod yn cael ei dosbarthu'n gyfartal. Yn debyg i ein gweithrediad rhestrau cysylltiedig, yn awr bob nod yn y tabl hash mewn gwirionedd yn mynd i gael torgoch fath. Felly mae gennym amrywiaeth torgoch o'r enw gair ac yna un arall pwyntydd i'r nod nesaf, sy'n gwneud synnwyr oherwydd mae'n mynd i fod yn rhestr cysylltiedig. Cofiwch pan fyddwn wedi cysylltu rhestrau, fe wnes i * nod a elwir yn bennaeth oedd yn pwyntio at y nod cyntaf yn y rhestr cysylltiedig. Ond ar gyfer ein bwrdd hash, oherwydd mae gennym restrau cysylltiedig lluosog, hyn yr ydym ei eisiau yw rydym am i'n tabl hash i fod fel, "Beth yw fwced?" Bwced yn unig yw rhestr o awgrymiadau nod, ac felly mae pob elfen yn y bwced mewn gwirionedd yn pwyntio at ei restr cysylltiedig cyfatebol. I fynd yn ôl at y sgematig, gwelwch fod y bwcedi eu hunain yn y saethau, Nid yw nodau gwirioneddol. Un eiddo hanfodol o swyddogaethau hash yw eu bod yn benderfynedig. Mae hynny'n golygu bod pryd bynnag y byddwch hash y rhif 2, dylai bob amser yn dychwelyd yr un bwced. Mae pob gwerth unigol sy'n mynd i mewn i'r swyddogaeth hash, os dro ar ôl tro, rhaid iddo gael y mynegai un. Felly eich swyddogaeth hash yn dychwelyd y mynegai y rhesi lle mae'r gwerth yn perthyn. Fel y soniais o'r blaen, mae nifer o bwcedi yn sefydlog, ac felly eich mynegai eich bod yn dychwelyd wedi i fod yn llai na nifer y bwcedi ond yn fwy na 0. Y rheswm pam y mae gennym swyddogaethau hash hytrach na dim ond un rhestr cysylltiedig sengl neu un amrywiaeth sengl yw ein bod eisiau gallu i neidio i adran benodol yn hawdd y rhan fwyaf o os ydym yn gwybod y nodweddiadol o werth - yn hytrach na gorfod chwilio drwy'r geiriadur cyfan cyfan, gallu i neidio i adran benodol ohono. Dylai eich swyddogaeth hash yn cymryd i ystyriaeth yn ddelfrydol, pob bwced Mae tua yr un nifer o allweddi. Ers y tabl hash yn gyfres o restrau cysylltiedig, yna bydd y rhestrau cysylltiedig eu hunain yn mynd i gael mwy nag un nod. Yn yr enghraifft flaenorol, dau rif gwahanol, er nad oeddent yn gyfartal, pan stwnsio, yn dychwelyd y mynegai un. Felly, pan fyddwch yn delio â geiriau, un gair wrth stwnsio byddai gwerth hash un gair arall. Dyna beth yr ydym yn galw wrthdrawiad, pan fydd gennym nod, pan stwnsio, nid yw'r rhestr yn gysylltiedig yn y bwced yn wag. Mae'r dechneg yr ydym yn galw yno yn llinol holi, ble rydych yn mynd i mewn i'r rhestr cysylltiedig ac yna dod o hyd lle rydych chi eisiau i fewnosod y nod oherwydd bod gennych gwrthdrawiad. Gallwch weld y gallai fod yn fasnach-off yma, dde? Os oes gennych chi bwrdd bach iawn hash, mae nifer fach iawn o bwcedi, yna rydych chi'n mynd i gael llawer o wrthdrawiadau. Ond wedyn, os byddwch yn gwneud tabl mawr iawn hash, mae'n debyg eich bod yn mynd i leihau gwrthdrawiadau, ond mae'n mynd i fod yn strwythur data mawr iawn. Mae mynd i fod yn fasnach-offs â hynny. Felly, pan fyddwch yn gwneud eich pset, ceisiwch i chwarae o gwmpas rhwng efallai yn gwneud tabl llai hash ond wedyn gwybod ei fod yn mynd i gymryd ychydig mwy o amser i deithio ar draws y gwahanol elfennau y rhestrau hynny cysylltiedig. 

Pa llwyth yn mynd i wneud yw ailadrodd dros bob gair yn y geiriadur. Mae'n mynd yn arwydd o'r ffeil geiriadur. Felly, rydych yn mynd i fanteisio ar y ffeil I / O swyddogaethau yr ydych yn meistroli yn pset4 ac yn ailadrodd dros bob gair yn y geiriadur. Rydych am bob gair yn y geiriadur i ddod yn nod newydd, a ydych yn mynd i roi pob un o'r nodau tu mewn i'ch data geiriadur strwythur. Pryd bynnag y byddwch yn cael gair newydd, byddwch yn gwybod ei fod yn mynd i fod yn nod. Felly, gallwch fynd yn syth ac yn malloc pwyntydd nod ar gyfer pob gair newydd sydd gennych. Yma Rwy'n galw fy nod new_node pwyntydd ac rwy'n mallocing beth? Mae maint y nod. Yna i ddarllen y llinyn gwirioneddol o ffeil, oherwydd bod y geiriadur yn cael ei storio mewn gwirionedd gan gair ac yna llinell newydd, yr hyn y gallwn fanteisio ar yw'r fscanf swyddogaeth, lle ffeil yn y ffeil geiriadur ein bod yn pasio i mewn, felly mae'n sganiau y ffeil ar gyfer llinyn a lleoedd sy'n llinyn i mewn i'r ddadl ddiwethaf. Os ydych yn cofio yn ôl i un o'r darlithoedd, pan fyddwn yn mynd dros a math o blicio yr haenau yn ôl ar y llyfrgell CS50, gwelsom gweithredu fscanf yno. I fynd yn ôl i fscanf, mae gennym y ffeil ein bod yn darllen, rydym yn chwilio am llinyn yn y ffeil, ac yna rydym yn gosod i mewn i yma rwyf wedi new_node-> gair oherwydd new_node yn pwyntydd nod, nid nod gwirioneddol. Felly, yna i ddim yn dweud new_node, Dw i eisiau mynd at y nod ei fod yn pwyntio at ac yna pennu bod gwerth i air. Rydym yn awyddus i yna cymerwch y gair a rhowch i mewn i'r tabl hash. Sylweddoli bod wnaethom new_node pwyntydd nod oherwydd ein bod yn mynd i eisiau gwybod beth yw cyfeiriad y nod yn pan fyddwn yn mewnosod yn oherwydd bod y strwythur y nodau eu hunain, y strwythur, yw eu bod yn cael pwyntydd i nod newydd. Felly, yna beth yw cyfeiriad y nod yn mynd i gyfeirio at? Sy'n mynd i'r afael yn mynd i fod new_node. Ydy hynny'n gwneud synnwyr, pam ein bod yn gwneud new_node a * nod yn hytrach na nod? Iawn. Mae gennym air. Bod y gwerth hwnnw'n new_node-> gair. Sy'n cynnwys y gair o'r geiriadur yr ydym am eu mewnbwn. Felly, yr hyn rydym am ei wneud yw ein bod am alw ein swyddogaeth hash ar y llinyn oherwydd bod ein swyddogaeth hash cymryd mewn llinyn ac yna dychwelyd i ni cyfanrif, os yw'r cyfanrif yw'r mynegai lle hashtable ar y mynegai yn cynrychioli y bwced. Rydym yn awyddus i gymryd y mynegai ac yna mynd i'r mynegai y tabl hash ac yna ddefnyddio'r rhestr gysylltiedig i osod y nod yn y new_node. Cofiwch fod bynnag y byddwch yn penderfynu i fewnosod eich nod, boed hynny yn y canol os ydych am i ddatrys y broblem neu ar ddechrau neu ar y diwedd, dim ond gwneud yn siwr bod eich nod olaf bob amser yn cyfeirio at NULL oherwydd dyna'r unig ffordd yr ydym yn gwybod lle mae'r elfen olaf ein rhestr cysylltiedig yn. 

Os maint yn gyfanrif sy'n cynrychioli nifer y geiriau mewn geiriadur, yna un ffordd o wneud hyn yw bod pryd bynnag y maint ei alw'n rydym yn mynd trwy bob elfen yn ein tabl hash ac yna ailadrodd drwy bob rhestr gysylltiedig o fewn y tabl hash ac yna cyfrifwch hyd hynny, gynyddu ein cownter gan 1 1. Ond bob tro y maint ei alw, mae hynny'n mynd i gymryd amser hir oherwydd ein bod yn mynd i fod yn llinol holi pob un rhestr cysylltiedig. Yn hytrach, mae'n mynd i fod yn llawer haws os ydych yn cadw golwg ar faint o eiriau yn cael eu trosglwyddo i mewn Felly, yna os ydych yn cynnwys y cownter o fewn eich swyddogaeth llwyth bod diweddariadau yn ôl yr angen, yna cownter, os ydych yn gosod i newidyn byd-eang, yn gallu cael mynediad yn ôl maint. Felly, beth yw maint y gallai ei wneud yw yn syml mewn un llinell, dim ond dychwelyd y gwerth cownter, maint y geiriadur, yr ydych eisoes yn delio â hwy yn llwyth. Dyna beth yr wyf yn golygu pan fyddaf yn dweud os ydych yn gweithredu llwyth mewn ffordd ddefnyddiol, Yna maint yn mynd i fod yn eithaf hawdd. 

Felly, yn awr rydym yn cael i wirio. Nawr rydym yn delio â geiriau o'r testun mewnbwn ffeil, ac felly rydym yn mynd i fod yn gwirio a yw pob un o'r geiriau hynny mewnbwn mewn gwirionedd yn y geiriadur neu beidio. Yn debyg i Scramble, rydym am i ganiatáu ar gyfer ansensitifrwydd achos. Byddwch am wneud yn siŵr bod yr holl eiriau pasio, hyd yn oed er eu bod yn achos cymysg, pan elwir gyda cymharu llinyn, yn cyfateb. Mae'r geiriau yn y ffeiliau geiriadur testun mewn gwirionedd i gyd llythrennau bach. Peth arall yw y gallwch gymryd yn ganiataol bod pob gair basiwyd yn, bob llinyn, yn mynd i fod naill ai yn yr wyddor neu gynnwys collnodau. Collnodau yn mynd i fod yn eiriau dilys yn ein geiriadur. Felly, os oes gennych air gyda collnod S, dyna gair dilys go iawn yn eich geiriadur mae hynny'n mynd i fod yn un o'r nodau yn eich tabl hash. Gwiriwch yn gweithredu gyda os yw'r gair yn bodoli, yna mae'n rhaid i fod yn ein tabl hash. Os yw'r gair yn y geiriadur, yna mae'r holl eiriau yn y geiriadur yn y tabl hash, felly gadewch i ni edrych am y gair yn y tabl hash. Rydym yn gwybod bod ers i ni weithredu ein swyddogaeth hash fel bod pob gair unigryw yn cael ei stwnsio bob amser i'r un gwerth, yna rydym yn gwybod, yn hytrach na chwilio drwy ein tabl hash cyfanwaith i gyd, gallwn mewn gwirionedd ddod o hyd i'r rhestr cysylltiedig y dylai'r gair yn perthyn iddo. Os yn y geiriadur, yna byddai'n fod yn y bwced. Beth allwn ni ei wneud, os gair yn enw ein llinyn basio i mewn, gallwn dim ond hash y gair ac edrych ar y rhestr sy'n gysylltiedig ar werth hashtable [hash (word)]. Oddi yno, yr hyn y gallwn ei wneud yw ein bod wedi is-set lai o nodau i chwilio am y gair hwn, ac felly gallwn groesi'r rhestr cysylltiedig, gan ddefnyddio enghraifft o gyfnod cynharach yn y walkthrough, ac yna galw llinyn cymharu ar y gair lle bynnag y cyrchwr yn pwyntio at, y gair, a gweld a yw'r cymharu. Yn dibynnu ar y ffordd yr ydych yn trefnu eich swyddogaeth hash, os caiff ei datrys, efallai y byddwch yn gallu dychwelyd ffug ychydig yn gynharach, ond os yw'n heb eu didoli, yna rydych eisiau parhau croesi drwy eich rhestr cysylltiedig nes i chi ddod o hyd i'r elfen olaf y rhestr. Ac os nad ydych wedi dod o hyd i'r gair gan yr adeg y byddwch wedi cyrraedd diwedd y rhestr cysylltiedig, hynny'n golygu nad yw eich gair yn bodoli yn y geiriadur, ac fel y gair yn annilys, a dylid gwirio dychwelyd ffug. 

Nawr rydym yn dod i ddadlwytho, lle rydym eisiau i ryddhau yr holl nodau yr ydym wedi malloc'd, mor rhad ac am ddim pob un o'r nodau y tu mewn ein tabl hash. Rydym yn mynd i eisiau i ailadrodd dros yr holl rhestrau cysylltiedig ac yn rhydd pob un o'r nodau yn hynny. Os edrychwch uchod yn y walkthrough at yr enghraifft lle rydym yn rhyddhau rhestr cysylltiedig, yna byddwch am ailadrodd y broses ar gyfer pob elfen yn y tabl hash. A byddaf yn mynd dros hyn tuag at ddiwedd y walkthrough, ond Valgrind yn offeryn lle gallwch weld os ydych wedi rhyddhau yn briodol pob nod eich bod wedi malloc'd neu unrhyw beth arall yr ydych wedi malloc'd, unrhyw pwyntydd arall. Felly dyna tablau hash, lle mae gennym nifer cyfyngedig o bwcedi a swyddogaeth hash a fydd yn cymryd gwerth ac yna pennu bod gwerth i fwced penodol. 

Nawr rydym yn dod i gais. Ceisiau fath o edrych fel hyn, a byddaf hefyd yn tynnu allan enghraifft. Yn y bôn, mae gennych amrywiaeth gyfan o lythyrau posibl, ac yna pryd bynnag y byddwch chi'n adeiladu gair, gall llythyr yn cael ei gysylltu am eiriadur i ystod eang o bosibiliadau. Rhai o eiriau yn dechrau gyda C ond wedyn yn parhau gyda A, ond mae eraill yn parhau gyda O, er enghraifft. Mae trie yn ffordd o ddychmygu holl gyfuniadau posibl o'r geiriau hynny. Mae trie yn mynd i gadw golwg ar y dilyniant o lythrennau sy'n cynnwys geiriau, fforchio pan fo angen, pryd y gall un llythyr yn cael ei ddilyn gan lluosog o lythyrau, ac ar y diwedd yn nodi ar bob pwynt a yw'r gair yn ddilys neu beidio oherwydd os ydych yn sillafu y gair MAT, MA Nid wyf yn credu yn air ddilys, ond MAT yw. Ac felly yn eich trie, byddai'n dangos bod ar ôl MAT sydd mewn gwirionedd gair dilys. Mae pob nod yn ein trie mewn gwirionedd yn mynd i gynnwys amrywiaeth o awgrymiadau nod, ac rydym yn mynd i gael, yn benodol, 27 o'r rhai awgrymiadau nod, un ar gyfer pob llythyren yn y wyddor yn ogystal â chymeriad collnod. Mae pob elfen yn y casgliad yn cael ei hun yn mynd i dynnu i un arall nod. Felly, os yw'r nod yn NULL, os nad oes unrhyw ôl hynny, yna rydym yn gwybod nad oes unrhyw lythyrau pellach yn y dilyniant gair. Ond os nad yw nod yw NULL, sy'n golygu bod mwy o lythyrau yn y dilyniant llythyr. Ac yna ar ben hynny, mae pob nod yn nodi a fydd y cymeriad olaf gair neu beidio. 

Gadewch i ni fynd i mewn i enghraifft o trie. Cyntaf i mi le ar gyfer 27 o nodau yn y casgliad. Os byddaf yn cael y gair BAR - Os byddaf yn cael y BAR geiriau a wyf i am osod mewn, y llythyr cyntaf yn B, felly os yw fy trie yn wag, B yw'r ail lythyr y wyddor, felly dwi'n mynd i ddewis i roi hyn yma yn y mynegai hwn. Rydw i'n mynd i gael B yma. B yn mynd i fod yn nod sy'n cyfeirio at un arall amrywiaeth o holl gymeriadau posibl a all ddilyn ar ôl y llythyr B. Yn yr achos hwn, rwy'n delio â'r BAR gair, fel y bydd yn mynd yma. Ar ôl A, Mae'r llythyr gennyf R, felly, yna pwyntiau bryd i'r cyfuniad eich hun, ac yna bydd R fod yma. BAR yn air gyflawn, felly, yna yr wyf i'n mynd i gael R pwynt i'r llall nod sy'n dweud bod y gair hwnnw yn ddilys. Bod nod hefyd yn mynd i gael amrywiaeth o nodau, ond gallai'r rhai sydd yn null. Ond yn y bôn, gall barhau fel hynny. Bydd hyn yn dod yn ychydig yn fwy eglur pan fyddwn yn mynd at enghraifft wahanol, felly dim ond yn amyneddgar gyda mi yno. Nawr mae gennym BAR tu mewn ein geiriadur. Nawr yn dweud ein bod yn cael y gair Baz. Rydym yn dechrau gyda B, ac mae gennym eisoes B fel un o'r llythyrau a anfonwyd sydd yn ein geiriadur. Dyna dilyn gyda A. Mae gennym A eisoes. Ond yna yn lle hynny, rydym wedi Z canlynol. Felly, yna elfen yn ein amrywiaeth yn mynd i fod Z, ac felly, yna bod un yn mynd i dynnu i un arall ar ddiwedd dilys o'r gair. Felly, rydym yn gweld bod pan fyddwn yn parhau trwy B ac yna A, mae dau opsiwn gwahanol ar hyn o bryd yn ein geiriadur am eiriau sy'n dechrau gyda B ac A. Dweud roeddem yn awyddus i mewnosoder y gair Foobar. Yna byddem yn gwneud cofnod yn F. F yn nod sy'n cyfeirio at amrywiaeth gyfan. Byddem yn dod o hyd i O, ewch i O, O yna gysylltiadau â rhestr gyfan. Byddai gennym B ac yna parhau, byddem wedi A ac yna R. Felly, yna croesi Foobar yr holl ffordd i lawr nes Foobar yn air cywir. Ac felly, yna byddai hyn fod yn air dilys. Yn awr yn dweud ein gair nesaf yn y geiriadur mewn gwirionedd y FOO gair. Byddem yn dweud F. Yr hyn sy'n dilyn F? Fi 'n weithredol eisoes â lle ar gyfer O, felly dwi'n mynd i barhau. Nid oes angen i mi wneud un newydd. Parhau. FOO yn air dilys yn y geiriadur, felly, yna yr wyf i'n mynd i ddangos bod hynny'n ddilys. Os byddaf yn rhoi'r gorau i fy dilyniant yno, byddai hynny'n gywir. Ond os ydym yn parhau â'n cyfres o FOO i lawr i B a dim ond wedi FOOB, nid FOOB yn air, ac nad yw wedi nodi fel un dilys. Mewn trie, rydych yn cael pob nod nodi a yw'n gair dilys neu beidio, ac yna bob nod hefyd amrywiaeth o 27 o arwyddion nod wedyn pwynt i nodau eu hunain. 

Dyma ffordd o sut efallai y byddwch am i ddiffinio'r hyn. Fodd bynnag, yn union fel yn yr enghraifft tabl hash, lle cawsom pen * nod i nodi dechrau ein rhestr cysylltiedig, rydym hefyd yn mynd i eisiau rhyw ffordd o wybod lle mae dechrau ein trie yw. Mae rhai pobl yn galw yn ceisio coed, a dyna lle gwraidd yn dod. Felly, rydym am wraidd ein coeden i wneud yn siŵr ein bod yn aros yn seilio i ble bynnag mae ein trie yn. Rydym eisoes yn fath o fynd dros y ffordd y gallech chi feddwl am lwytho pob gair yn y geiriadur. Yn y bôn, ar gyfer pob gair rydych yn mynd i eisiau i ailadrodd drwy eich trie a gwybod bod pob elfen yn y plant - byddem ni'n ei alw plant yn yr achos hwn - yn cyfateb i lythyr wahanol, rydych yn mynd i eisiau i wirio y rhai gwerthoedd ar y mynegai penodol sy'n cyfateb i'r llythyren. Felly meddwl yr holl ffordd yn ôl i Cesar a Vigenere, gan wybod bod pob llythyr gallwch fath o fap yn ôl i mynegai yn nhrefn yr wyddor, bendant A drwy'r Z yn mynd i fod yn eithaf hawdd i fapio i lythyr yr wyddor, ond yn anffodus, collnod hefyd yn gymeriad dderbyniol mewn geiriau. Dydw i ddim hyd yn oed yn siŵr beth yw gwerth ASCII yw, felly ar gyfer, os ydych am ddod o hyd i mynegai i benderfynu a ydych am iddo fod naill ai yr un cyntaf neu yr un diwethaf, bydd rhaid i chi wneud siec godio caled ar gyfer y a rhoi at ei bod yn fynegai 26, er enghraifft. Felly, yna rydych yn gwirio gwerth at blant [i] lle mae [i] yn cyfateb i beth bynnag lythyr rydych chi wedi'i gyrraedd. Os yw hynny'n NULL, mae hynny'n golygu nad oes ar hyn o bryd unrhyw lythyrau posibl yn deillio o hynny dilyniant blaenorol, felly rydych yn mynd i eisiau i malloc ac yn gwneud nod newydd a chael bod plant pwynt [i] iddo fel eich bod yn creu - pan fyddwn yn mewnosod lythyr i mewn i'r petryal - sicrhau bod plant nad ydynt yn null a phwynt i mewn i'r nod newydd. Ond os nad yw hynny'n NULL, fel yn ein hachos ni o FOO pan fyddwn eisoes wedi cael Foobar, rydym yn parhau, ac nid ydym yn byth yn gwneud nod newydd ond yn hytrach dim ond gosod i gwir is_word ar ddiwedd y gair. 

Felly, yna fel o'r blaen, oherwydd dyma eich bod yn delio gyda phob llythyren ar y tro, mae'n mynd i fod yn haws i chi ar gyfer maint, yn hytrach na gorfod gyfrifo ac ewch drwy'r goeden gyfan ac yn cyfrifo faint o blant sy'n rhaid i mi ac yna fforchio, gan gofio faint sydd ar yr ochr chwith ac ar yr ochr dde a phethau fel 'na, mae'n mynd i fod yn llawer haws i chi os ydych yn unig yn cadw golwg ar faint o eiriau rydych yn ychwanegu pan fyddwch yn delio â llwyth. Ac felly, yna gall maint ffordd dim ond dychwelyd newidyn byd-eang o faint. 

Nawr rydym yn dod i wirio. Un safonau fel o'r blaen, lle rydym eisiau i ganiatáu ar gyfer ansensitifrwydd achos. Yn ogystal, rydym yn tybio bod y tannau yn gymeriadau yn unig yr wyddor neu y collnodau oherwydd bod plant yn amrywiaeth o 27 o hyd, felly yr holl lythrennau'r wyddor yn ogystal â'r collnod. Am weld pa youll 'angen at gwna ydy youll' angen at ddechrau yn y gwraidd oherwydd bydd y gwraidd bwyntio at amrywiaeth sy'n cynnwys holl lythyrau posibl gan ddechrau o air. Rydych chi'n mynd i ddechrau yno, ac yna rydych chi'n mynd i wirio a yw hyn NULL werth neu beidio, oherwydd os bydd y gwerth yn NULL, sy'n golygu nad yw'r geiriadur oes unrhyw werthoedd sy'n cynnwys y llythyr hwnnw yn y drefn benodol. Os yw'n NULL, yna mae hynny'n golygu bod y gair yn cael ei gamsillafu ar unwaith. Ond os nad yw'n NULL, yna gallwch barhau, dweud bod llythyren gyntaf yn llythyren gyntaf posibl mewn gair, felly nawr rwyf am i wirio a yw'r ail lythyr, bod dilyniant, o fewn fy ngeiriadur. Felly, rydych chi'n mynd i fynd at y mynegai plant y nod 1 a gwirio a yw'r ail lythyr yn bodoli. Yna byddwch yn ailadrodd y broses honno i wirio a yw'r dilyniant yn ddilys neu beidio o fewn eich trie. Pryd bynnag y plant nod ar y pwyntiau mynegai i NULL, eich bod yn gwybod nad yw'r dilyniant yn bodoli, ond yna os byddwch yn cyrraedd diwedd y gair yr ydych wedi mewnbynnu, yna rydych am wirio nawr fy mod wedi cwblhau dilyniant hwn a dod o hyd o fewn fy trie, yw bod gair ddilys ai peidio? Ac felly, os ydych am wirio hynny, a dyna pryd os ydych wedi gweld bod dilyniant, yna rydych am wirio a yw'r gair yn ddilys neu beidio oherwydd cofio yn ôl yn yr achos blaenorol y tynnais lle cawsom FOOB, a oedd yn ddilyniant dilys a welsom ond nad oedd yn air dilys ei hun. 

Yn yr un modd, ar gyfer dadlwytho yn y ceisiau ydych am i ddadlwytho pob un o'r nodau yn eich trie. Mae'n ddrwg gennym. Yn debyg i'r tablau hash lle yn dadlwytho rydym yn rhyddhau yr holl nodau, yn y cais ydym am hefyd yn rhyddhau pob un o'r nodau. Bydd Dadlwytho yn gweithio mewn gwirionedd hawsaf o'r gwaelod i'r brig oherwydd bod y rhain yn rhestrau cysylltiedig yn y bôn. Felly, rydym am wneud yn siŵr ein bod yn dal gafael ar yr holl werthoedd ac yn rhydd pob un ohonynt yn benodol. Beth ydych chi'n mynd i eisiau i'w wneud os ydych chi'n gweithio gyda trie yn teithio i'r gwaelod a rhad ac am ddim y nod isaf posibl cyntaf ac yna mynd i fyny i bob un o'r plant hynny ac yna rhad ac am ddim pob un o'r rheiny, mynd i fyny ac yna rhad ac am ddim, ac ati Math o fel delio â haen waelod y cyntaf trie ac yna mynd i fyny ben unwaith y byddwch wedi rhyddhau popeth. Mae hon yn enghraifft dda o ble y gallai swyddogaeth recursive dod yn ddefnyddiol. Unwaith y byddwch wedi rhyddhau yr haen waelod eich trie, yna byddwch yn ffonio dadlwytho ar y gweddill ohono, gwneud yn siŵr eich bod yn rhyddhau pob mini - Gallwch fath o yn gweld hynny fel cais mini. Felly, rydych yn cael eich gwraidd fan hyn. Im 'jyst yn symleiddio felly nid oes gennyf i dynnu 26 ohonynt. Felly, mae gennych y rhain, ac yna y rhain yn cynrychioli dilyniant o eiriau lle mae pob un o'r cylchoedd bach yn llythrennau y gellir eu dilyniannau dilys o lythyrau. Gadewch i ni barhau dim ond ychydig yn fwy. Beth ydych chi'n mynd i eisiau ei wneud yw rhad ac am ddim y gwaelod yma ac yna rhad ac am ddim yr un yma ac yna ddim yr un ar y gwaelod cyn i chi ryddhau'r un gorau hyd yma oherwydd os ydych yn rhywbeth rhad ac am ddim yn yr ail lefel yma, yna rydych fyddai mewn gwirionedd yn colli gwerth hwn yma. Dyna pam ei bod yn bwysig yn dadlwytho i trie i wneud yn siŵr eich bod yn rhyddhau'r ben ôl yn gyntaf. Beth efallai y byddwch am ei wneud yw dweud ar gyfer pob nod Rwyf am i ddadlwytho pob un o'r plant. 

Nawr ein bod wedi mynd dros dadlwytho ar gyfer y dull tabl hash yn ogystal â'r dull trie, rydym yn mynd i eisiau i edrych ar Valgrind. Valgrind ydych yn rhedeg gyda gorchmynion canlynol. Mae gennych valgrind-v. Rydych yn gwirio ar gyfer yr holl ollyngiadau pan fyddwch yn rhedeg sillafu rhoddir y testun penodol oherwydd sillafu angen eu cymryd mewn ffeil testun. Felly, bydd Valgrind yn rhedeg eich rhaglen, yn dweud wrthych faint o bytes ydych wedi ei glustnodi, faint o bytes rhyddhau chi, a bydd yn dweud wrthych a ydych yn rhyddhau dim ond digon ynteu a ydych yn gwneud ddigon rhydd, neu weithiau gallwch hyd yn oed dros-rhad ac am ddim, fel rhad ac am ddim yn nod sydd eisoes wedi rhyddhau ac felly bydd yn dychwelyd i chi gwallau. Os ydych yn defnyddio Valgrind, bydd yn rhoi i chi rai negeseuon nodi a ydych chi wedi rhyddhau naill ai yn llai na digon, dim ond digon, neu fwy na ddigon o weithiau. 

Mae rhan o'r pset, mae'n ddewisol i herio y Bwrdd Big. Ond pan fyddwn ni'n delio â'r strwythurau data mae'n fath o hwyl i weld pa mor gyflym a pha mor effeithlon a allai eich strwythurau data fod. A yw eich canlyniad swyddogaeth hash mewn llawer o wrthdrawiadau? Neu a yw eich data maint mawr iawn? A yw'n cymryd llawer o amser i deithio ar draws? Yn y log o sillafu, mae'n allbynnau faint o amser rydych yn ei ddefnyddio i lwytho, i wirio, i gynnal maint, ac i ddadlwytho, ac felly rhain yn cael eu postio yn y Bwrdd Fawr, lle gallwch chi gystadlu yn erbyn eich ffrindiau yn y dosbarth a rhai aelodau o'r staff i weld pwy sydd â'r cyflymaf gwirydd sillafu. Un peth y byddwn i'n hoffi i'w nodi am y tablau hash yw bod rhai swyddogaethau eithaf syml hash y gallem feddwl. Er enghraifft, mae gennych 26 bwcedi, ac felly bob bwced cyfateb i'r llythyren gyntaf mewn gair, ond mae hynny'n mynd i arwain mewn tabl 'n bert anghytbwys hash oherwydd mae geiriau llawer llai sy'n dechrau â X na dechrau gyda M, er enghraifft. Un ffordd i fynd ati i sillafu yw os ydych am gael yr holl swyddogaethau eraill i lawr, yna dim ond yn defnyddio swyddogaeth hash syml i fod yn gallu cael eich cod rhedeg ac yna mynd yn ôl a newid maint eich tabl hash a'r diffiniad. Mae yna lawer o adnoddau ar y Rhyngrwyd ar gyfer swyddogaethau hash, ac felly ar gyfer y pset caniateir i chi ymchwilio i swyddogaethau hash ar y Rhyngrwyd ar gyfer rhai awgrymiadau ac ysbrydoliaeth cyn belled ag y byddwch yn gwneud yn siwr i ddyfynnu ble y cawsoch rhag. Mae croeso i chi edrych a dehongli rhywfaint o swyddogaeth hash eich bod yn dod o hyd ar y Rhyngrwyd. Yn ôl i hynny, efallai y byddwch yn gallu gweld os bydd rhywun yn defnyddio trie a yw eu rhoi ar waith yn gyflymach nag eich bwrdd hash neu beidio. Gallwch gyflwyno i Fwrdd Big sawl gwaith. Bydd yn cofnodi eich cofnod mwyaf diweddar. Felly, efallai byddwch yn newid eich swyddogaeth hash ac yna sylweddoli ei fod mewn gwirionedd yn llawer cyflymach neu lawer arafach nag o'r blaen. Mae hynny'n dipyn o ffordd hwyliog. Mae bob amser yn 1 neu 2 aelod staff sy'n ceisio gwneud y geiriadur arafaf posibl, fel bod bob amser yn hwyl i edrych ar. 

Mae'r defnydd ar gyfer y pset yw ydych yn rhedeg sillafu gyda geiriadur dewisol ac yna ffeil destun gorfodol. Erbyn ddiofyn pan fyddwch yn rhedeg sillafu gyda dim ond ffeil destun ac nid ydynt yn pennu geiriadur, mae'n mynd i ddefnyddio'r geiriadur, ffeil testun yr un mawr yn y ffolder cs50/pset5/dictionaries. Bod un dros 100,000 o eiriau. Mae ganddynt hefyd geiriadur bach sydd â geiriau gryn dipyn yn llai bod CS50 wedi gwneud i chi. Fodd bynnag, gallwch yn hawdd iawn yn unig yn gwneud eich geiriadur eich hun os ydych am fod yn gweithio mewn enghreifftiau bach - er enghraifft, os ydych chi am ddefnyddio gdb a ydych yn gwybod y gwerthoedd penodol eich bod am i'ch bwrdd hash i fapio allan i. Felly, dim ond y gallwch chi wneud eich ffeil testun eich hun yn unig gyda BAR, Baz, FOO, a Foobar, gwneud hynny mewn ffeil testun, gwahanu'r rheiny pob un ag 1 llinell, ac yna gwneud eich ffeil destun hun sy'n llythrennol yn unig yn cynnwys efallai 1 neu 2 o eiriau fel eich bod yn gwybod yn union beth y dylai'r allbwn. Mae rhai o'r ffeiliau sampl testun y bydd y Bwrdd Big pan fyddwch yn rhedeg her gwirio yn Rhyfel a Heddwch a nofel Austen Jane neu rywbeth fel 'na. Felly, pan fyddwch yn dechrau allan, mae'n llawer haws i wneud eich ffeiliau testun eich hun sy'n cynnwys dim ond ychydig o eiriau neu efallai 10 fel y gallwch ragweld beth ddylai'r canlyniad fod ac yna ei wirio yn erbyn hynny, felly mae mwy o enghraifft a reolir. Ac felly ers i ni yn delio â rhagweld a thynnu pethau o gwmpas, eto yr wyf yn awyddus i annog chi i ddefnyddio pin a phapur oherwydd ei fod yn wir yn mynd i helpu chi gyda hyn - tynnu y saethau, sut y tabl hash neu sut mae eich trie yn edrych, pan fyddwch yn rhyddhau rhywbeth lle mae'r saethau yn mynd, a ydych yn cynnal ar i ddigon, a ydych yn gweld unrhyw gysylltiadau ddiflannu a disgyn i'r dibyn o gof a ddatgelwyd. Felly, os gwelwch yn dda, os gwelwch yn dda ceisio tynnu pethau allan hyd yn oed cyn i chi fynd i ysgrifennu cod i lawr. Tynnwch bethau fel eich bod yn deall sut mae pethau'n mynd i weithio oherwydd wedyn wyf yn gwarantu y byddwch yn rhedeg i mewn i Muddles pwyntydd yn llai yno. 

Mae pob hawl. Rwyf am ddymuno i chi y gorau o lwc gyda'r pset. Mae'n debyg yr un anoddaf. Felly ceisiwch i ddechrau yn gynnar, tynnu pethau allan, tynnu pethau allan, a phob lwc. Roedd hyn yn Walkthrough 5. 

[CS50.TV]