ZAMYLA Chan: Se pou nou fè yon yon korektè. Si ou louvri speller.c, lè sa a ou pral wè ki pi fò nan fonksyonalite a pou mwen make yon dosye tèks kont yon se diksyonè deja fè pou ou. . / Ortograf, pase nan yon tèks diksyonè ranpli ak Lè sa a, yon lòt dosye tèks, pral tcheke pou wè ke dosye tèks kont diksyonè a. 

Koulye a, diksyonè fichye tèks pral gen mo ki valab, youn pou chak liy. Lè sa a, speller.c pral rele chaj sou diksyonè dosye a tèks. Li pral rele yon fonksyon rele Tcheke sou tout pawòl nan dosye a tèks antre, enprime tout pawòl w mal ekri. 

Speller.c pral rele tou Size detèmine kantite mo nan diksyonè epi rele dechaje libere ond memwa. speller.c pral tou kenbe tras nan ki jan se anpil tan yo itilize yo ka fè nan sa yo pwosesis, men nou pwal jwenn ak sa yo ki pita. 

Se konsa, sa nou bezwen fè? Nou bezwen ranpli nan dictionary.c. Nan dictionary.c, nou gen k'ap vin ede nan chaj fonksyon, ki charj nan diksyonè. Tcheke nan fonksyon, ki chèk si yon mo bay se an nan diksyonè a. Gwosè a fonksyon retounen nimewo a nan mo an nan diksyonè a. E finalman, nou te dechaje, ki libere diksyonè a soti nan memwa. 

Se konsa, premye, se pou yo atake chaj. Pou chak mo nan tèks la diksyonè ranpli, chaj pral estoke mo sa yo nan diksyonè estrikti nan done ou chwazi ki, swa yon Hash tab oswa yon trye. Mwen pral ale sou tou de nan sa a mache nan. 

Premye kite a pale sou tab hash. Di ou te gen 10 voye boul biya ak ou te vle nan magazen yo. Ou ta ka mete yo tout nan yon bokit, ak ki lè ou bezwen yon espesifik resansman boul, ou ta pran youn soti nan bokit la nan yon moman kap chèche ke boul. Se avèk sèlman 10 voye boul, ou ta dwe kapab jwenn boul ou a nan yon rezonab kantite tan. 

Men, sa ki si ou te gen 20 voye boul? Li ta ka pran yon ti tan ankò kounye a. Ki sa ki sou 100? 1,000? Koulye a, li ta pi fasil si ou te gen plizyè bokit. Petèt yon sèl bokit pou voye boul resansman zewo atravè nèf, yon lòt bokit pou voye boul resansman 10 pou rive 19, ak sou sa. 

Koulye a, lè ou bezwen gade pou espesifik boul, ou te kapab otomatikman ale nan youn bokit espesifik ak Fouye nan ki bokit. Men, si chak bokit gen apeprè 10 voye boul, lè sa a ou te kapab fasilman rechèch atravè li. 

Koulye a, depi nou ap fè fas ak diksyonè, yon sèl bokit sèl pou tout nan mo sa yo nan diksyonè a pral pwobableman ap twò lwen kèk bokit. Se konsa, kite a pran yon gade nan tab hash. 

Panse a li kòm yon etalaj de bokit. Apre sa, nan ka sa a, bokit yo yo bay lis lye nou an. Epitou, n ap distribye tout mo nou pami sa yo miltip lis lye nan yon fason òganize lè l sèvi avèk yon fonksyon hash, ki pral di nou ki bokit yon kle yo bay yo, yon bay mo, ki dwe nan. 

Se pou yo reprezante sa a Schematics. Bwat yo ble isit la gen valè ak bwat wouj pwen a yon lòt valè konsèy pè. Nou pral rele sa yo pè nœuds. Koulye a, chak bokit, jan mwen te di pi bonè, se yon lis lye. Nan lis lye, chak ne te gen yon valè, menm jan tou yon konsèy la pwochen valè. 

Koulye a, fè fas ak lis lye, li trè enpòtan ke ou pa pèdi nenpòt lyen yo. Ak yon lòt reyalite sonje se ke an dènye ne, si li pa lonje dwèt sou yon lòt ne, lonje dwèt nan nil. 

Se konsa, kouman nou reprezante sa a nan C? Nou defini konstri nou isit la. Apre sa, valè a nan ka sa a se yon etalaj Char nan longè. Longè plis 1, kote longè se la longè maksimòm de nenpòt mo, plis 1 pou Terminator a nil. Lè sa a, nou gen yon konsèy yon lòt ne rele kap vini an. 

Se konsa, kite a fè yon ti lis lye. Premyèman, ou pral vle malok ne ou a, ki kreye espas nan memwa a gwosè nan kalite ne ou. Apre sa, fè yon lòt ne, ankò mallocing. 

Koulye a, si ou vle bay yon valè nan yon mo, Lè sa a, nou ta ka di node1 flèch mo egal "Hello." Operatè flèch sa a dereferences konsèy la ak jwenn aksè varyab konstri la. Fason sa a, nou pa gen yo sèvi ak tou de dot a ak operatè a zetwal. 

Se konsa, Lè sa a, mwen gen pawòl flèch node2 egal "Nan lemonn." Epi gen, valè yo peple nan nœuds m 'yo. Pou fè lyen yo, mwen pral pase nan node1 flèch kap vini an, aksè nan ki etwal ne, ki konsèy ne, egal node2, montre node1 node2 de. Apre sa, nou gen yon lis lye. 

Se konsa, sa ki te jis yon sèl lis lye, men yon tab hash se yon etalaj antye nan lye lis. Oke, nou pral gen menm ne la estrikti tankou anvan. Men, si nou te vle yon tab hash reyèl, Lè sa a, nou ka jis fè yon konsèy ne etalaj isit la. Pou egzanp, gwosè 500. 

Koulye a, avi, gen k ap pase yo dwe yon komès nan ant gwosè a nan ou tab hash ak gwosè a nan lis lye ou. Si ou gen yon nimewo vrèman segondè nan bokit, pou yo imajine ki gen nan kouri tounen yo epi pwoklame nan yon liy jwenn bokit ou. Men, nou menm tou nou pa vle yon ti ponyen nan bokit, paske lè sa a nou ap tounen nan pwoblèm orijinal la nan ki jan li te gen voye boul twò anpil nan bokit nou an. 

OK, men ki kote boul nou an ale? Oke, nou premye bezwen gen yon boul, dwa? Se konsa, kite a malok yon ne pou chak nouvo mo ke nou gen. ne * new_node egal malok (sizof (ne)). 

Koulye a, ke nou gen estrikti sa a, nou ka analysis nan, lè l sèvi avèk fonksyon an fskanf, yon kòd nan dosye nou an, si sa a, se yon dosye diksyonè, nan new_node mo flèch, kote new_node flèch mo se nou destinasyon nan mo sa a. 

Apre sa, nou pral vle Hash ki mo lè l sèvi avèk yon fonksyon hash. Yon fonksyon hash pran yon fisèl ak retounen yon endèks. Nan ka sa a, endèks la te dwe mwens pase kantite a nan bokit ki di ou gen. 

Koulye a, fonksyon hash, lè w ap eseye w jwenn youn ak kreye youn nan pwòp ou a, sonje ke yo dwe fè detèrminist. Sa vle di ke menm valè a bezwen kat jeyografik nan menm bokit la chak fwa ke ou Hash li. 

Li nan kalite tankou yon bibliyotèk. Lè ou pran yon liv, ki baze sou la otè, ou konnen ki etajè li ta dwe ale sou, si li nan nimewo etajè yonn, de, oswa twa. Apre sa, sa vle di liv ap toujou fè pati sou youn etajè, de, oswa twa. 

Se konsa, si pawòl new_node flèch gen nan mo soti nan diksyonè ou a, Lè sa a, achin mo flèch new_node pral ban nou endèks la nan la bokit nan tablo a hash. Lè sa a, nou pral insert ki nan ki lis espesifik lye sa endike nan la retounen valè de fonksyon hash nou an. 

Se pou yo gade nan yon egzanp sou yo mete yon ne nan la kòmanse nan yon lis lye. Si tèt se yon konsèy ne ki endike nan konmansman an nan yon lye lis, ak new_node endike non nouvo nan ne ke ou vle antre nan, jis plase tèt nan new_node ta pèdi lyen ki mennen nan rès la nan lis la. Se konsa, nou pa vle fè sa a. 

Olye de sa, nou vle asire w ke ke nou kenbe fèm nan fè chak yon sèl ne nan pwogram nou an. Se konsa, kouri flèch new_node egal pwochen tèt li ak Lè sa a, tèt egal new_node ap konsève tout la lyen epi yo pa pèdi nenpòt. 

Men, sa ki si ou vle lis ou a yo dwe Ranje, paske te gen yon Ranje lye lis ta ka pi fasil pou chache li pita sou? Oke, pou sa, ou pral bezwen konnen ki jan yo Traverse lis lye. 

Traverse yon lis lye, se pou yo gen yon konsèy ne, yon * ne, yo aji kòm kursor ou, ki endike ki ne ou nan, kòmanse nan eleman a an premye. Loupin jouk kurseur se nil, nou ka fè pwosesis ak sèten Lè sa a, avanse kurseur nan lè nou bezwen lè l sèvi avèk kurseur valè flèch. 

Sonje, sa a se menm bagay la kòm li di zetwal kurseur, dereferencing kurseur, lè sa a lè l sèvi avèk la dot operatè valè. Se konsa, à kurseur an ki pa plase kurseur nan kurseur flèch kap vini an. 

Di ou detèmine ke D vin nan ant C ak E. Pou insert ne la, gen D pwen an new_node la ne E, ki se kurseur kap vini an. Lè sa a, C, kurseur la, yo ka Lè sa a, pwen D. Nan fason sa a, ou kenbe yon lis. Fè atansyon pa pèdi lyen ou pa k ap deplase flèch la kurseur akote D touswit. 

Tout dwa. Se konsa, sa a, se ki jan ou ta ka insert nœuds, chaje yo nan, mo chaj nan sa yo nœuds, ak insert yo nan tab hash ou. Se konsa, koulye a kite pou yo gade nan ap eseye. 

Nan yon trye, chak ne a pral gen yon etalaj de pwent ne, yonn pou chak lèt nan alfabè a plis yon apostwòf. Apre sa, chak eleman nan etalaj la pral pwen a yon lòt ne. Si sa ne se nil, lè sa a ke lèt se pa pral fè lèt nan pwochen nan nenpòt ki pawòl nan yon sekans, paske chak mo endike si li nan dènye a N. nan yon mo oswa ou pa. 

Se pou yo gade nan yon dyagram. Nou swete ke bagay sa yo pral gen yon ti jan pi klè. Nan dyagram sa a, nou wè ke se sèlman sèten lèt ak sèten chèn yo te ki nan lis soti. Se konsa, ou ka swiv sèten chemen, ak tout nan chemen sa yo ap mennen ou nan diferan mo yo. 

Se konsa, kouman nou reprezante sa a nan C? Oke, chak ne koulye a, se pral fè yon valè Boolean endike si ki ne se nan fen yon mo bay oswa ou pa. Lè sa a, li pral gen tou yon etalaj de endikasyon ne rele timoun yo, epi gen yo ale nan gen 27 nan yo. Epi sonje, ou pral vle tou kenbe tras nan premye ne ou. Nou pral rele ke rasin. 

Se konsa, sa a, se estrikti a nan yon trye. Ki jan nou reprezante sa a kòm yon diksyonè? Oke, chaj mo nan, pou chak diksyonè mo, w ap ale nan vle repňte nan trye la. Apre sa, chak eleman nan timoun yo koresponn ak yon lèt diferan. 

Se konsa, tcheke valè a nan timoun yo mwen endèks, kote mwen reprezante a endèks espesifik nan lèt ki w ap eseye insert. Bon, si li nan nil, lè sa a ou pral vle malok yon nouvo ne epi fè timoun mwen lonje dwèt sou ki ne. 

Si li pa nil, lè sa a sa vle di ki branch yo bay yo, ki bay chèn, ki deja egziste. Se konsa, Lè sa a, ou pral jis deplase ak sa yo ki nouvo ne yo e yo kontinye. Si w ap nan fen pawòl Bondye a ki w ap eseye chaje nan la diksyonè, Lè sa a, ou ka mete ki ne kounye a ke w ap sou yo vre. 

Se konsa, kite yo gade nan yon egzanp sou yo mete pawòl Bondye a "rena" nan nou an diksyonè. Pran pòz nou kòmanse ak yon diksyonè vid. Lèt nan premye, F, sa yo pral lokalize nan timoun endèks senk nan rasin yo timoun etalaj. Se konsa, nou insert ki pous 

Lè sa a, lèt O a pral nan timoun endèks 15, apre sa F. Lè sa a, X yo pral menm anba a ki, branch koupe nan timoun O la. Lè sa a, paske X se dènye lèt la nan pawòl Bondye "rena a," Lè sa a, mwen pral koulè ki vèt yo endike ke li nan nan fen mo a. Nan C, ki ta ka mete a se Pawòl Boolean a valè a vre. 

Kounye a ki sa si pwochen mo a ke w ap chaje nan se pawòl Bondye a "foo"? Oke, ou pa bezwen malok nenpòt ki plis espas pou F oubyen pou O, paske moun ki deja egziste. Men, nou menm ki sot pase a nan foo? Sa yon sèl, ou pral gen malok. Fè yon nouvo ne pou sa, mete se pawòl Bondye Boolean a vre. 

Se konsa, kounye a kite a insert "chen." Chen pral kòmanse ak endèks twa nan rasin yo timoun yo, paske D pa gen yo te kreye ankò. Epitou, n ap swiv yon pwosesis menm jan an kòm anvan, sa ki kreye chen an chèn, kote nan G an ki gen koulè pal vèt paske sa a, se nan fen yon mo. 

Koulye a, sa ki si nou vle insert "fè"? Oke, sa a se yon chèn nan chen, se konsa nou pa bezwen malok ankò. Men, nou bezwen endike kote nou te rive jwenn nan fen mo sa a. Se konsa, ap O a dwe gen koulè vèt. Kontinye pwosesis ki pou chak yon sèl mo an nan diksyonè ou a, ou te chaje yo nan nan swa ou Hash tab oswa trye ou. 

speller.c ap pase nan strings pou dictionary.c yo tcheke yo. Koulye a, fonksyon an Tcheke gen yo opere anba ka ensansibilite. Sa vle di ke lèt majiskil ak lèt miniskil ak yon melanj de tou de yo ta dwe tout egalize a vre, si yon konbinezon de sa ki nan la diksyonè. Ou kapab tou asime ke strings yo sèlman ale nan gen alfabetik karaktè oswa apostrof. 

Se konsa, kite yo gade nan ki jan ou ta ka tcheke ak yon estrikti tab hash. Bon, si pawòl Bondye a ki egziste, lè sa a li Ou ka jwenn nan tablo a hash. Se konsa, Lè sa a, ou ka eseye jwenn ke mo nan bokit la ki enpòtan. 

Se konsa, ki bokit ta mo sa a dwe nan? Oke, ou ta jwenn nimewo a, ki endèks nan bokit la, pa achin mo sa a ak Lè sa a, chache nan ke lis lye, Travelers nan tout la lye lis, lè l sèvi avèk fisèl la Konpare fonksyon. 

Si nan fen lis la lye se rive jwenn, sa vle di kursor ou rive nan nil, lè sa a pawòl Bondye a se pa te kapab jwenn nan diksyonè a. Li pa pral nan nenpòt ki lòt bokit. Se konsa, isit la, ou ta ka al wè ki jan gen ta ka gen yon komès-off ant li te gen swa Ranje lis lye oswa moun ki triye. Swa pral pran plis tan pandan anbake oswa plis tan pandan chèk la. 

Ki jan ou ta ka tcheke nan yon estrikti trye? Nou pral vwayaje ba nan trye la. Pou chak lèt ​​nan pawòl Bondye a antre ke nou ap tcheke, nou pral ale nan ki ki koresponn eleman nan timoun yo. 

Si sa eleman se nil, lè sa a sa vle di ke pa gen okenn chèn ki gen mo D 'nou an, pou pawòl la se w mal ekri. Si li pa nil, nou ka deplase al nan nan lèt pwochen nan pawòl Bondye a ke nou ap tcheke yo e yo kontinye pwosesis sa a jiskaske nou rive nan fen an nan pawòl Bondye a D '. Lè sa a, nou ka tcheke si se pawòl Bondye a vre. Si li se, Lè sa a, gwo. Pawòl Bondye a nan kòrèk. Men, si se pa, menm si ke chèn egziste nan trye a, mo a se w mal ekri. 

Lè yo rele Size fonksyon an, gwosè dwe retounen ki kantite mo ki yo se an nan diksyonè ou bay done estrikti. Se konsa, si w ap itilize yon tab hash, ou ka swa ale nan tout yon sèl lis lye nan chak yon sèl bokit konte kantite ki nan mo ki genyen. Si w ap sèvi ak yon trye, ou ka ale nan tout nil ki chemen an trye ou. Oswa pandan w ap chaje diksyonè a nan, petèt ou ka kenbe tras nan ki jan anpil mo w ap chaje pous 

Yon fwa speller.c fini tcheke nan dosye tèks kont diksyonè a, lè sa a li fè ak se konsa li rele dechaje, kote travay ou se yo gratis anyen ke ou te malloced. Se konsa, si ou itilize yon tab hash, lè sa a ou bezwen yo dwe espesyalman fè atansyon pou fè pou evite fwit memwa pa pa libere anyen prematireman e kenbe sou chak yon sèl lyen anvan ou gratis. 

Se konsa, pou chak eleman nan tablo a hash ak pou chak ne nan lis la lye, ou pral vle gratis ki ne. Ki jan ou fè ale sou libere yon lis lye? Anviwònman ne ou konsèy kurseur tèt la, nan konmansman an nan la lis lye, Lè sa a, pandan y ap kursor ou se pa nil, ou ka mete yon ti tan ne konsèy kursor ou. Lè sa a, avanse kurseur la. Lè sa a, ou ka gratis ke pou yon ti tan valè pandan y ap toujou kenbe sou li nan yon tout bagay apre sa. 

E si w ap itilize yon trye? Lè sa a, pi bon fason a fè sa se yo dechaje soti nan anpil nan anba nan tèt la. Pa vwayaje nan posib ki pi ba a ne, ou ka libere tout endikasyon nan pou timoun ak Lè sa a, rvnir egal, li delivre tout eleman nan tout nan timoun yo ranje yo, jouk ou frape ne tèt rasin ou. Isit la nan kote rkursyon ap vini an sou la men. 

Pou fè sèten ke ou te pwobableman te libere tout bagay ke ou te malloced, ou ka sèvi ak Valgrind. Kouri Valgrind pral kouri pwogram ou an konte bytes ki jan anpil nan memwa w ap itilize ak fè si ke ou te libere yo tout, di ou ki kote ou ta ka genyen bliye gratis. Se konsa, kouri ki ak yon fwa Valgrind di ou epi li ba ou ale nan devan ou, Lè sa a, ou te fin debake. 

Koulye a, yon koup la konsèy anvan ou ale koupe epi yo kòmanse mete ann aplikasyon ou diksyonè. Mwen ta rekòmande pou yo pase nan yon pi piti diksyonè lè w ap eseye teste bagay sa yo soti ak debogaj ak GDP. L 'a ortograf se. / Ortograf, yon diksyonè si ou vle, ak Lè sa a, yon tèks. 

Pa default, li charj nan diksyonè a gwo. Se konsa, ou ta ka vle pase nan ti a diksyonè, oswa petèt menm fè ou pwòp, Pèrsonalizasyon diksyonè ou ak dosye tèks ou a. 

Lè sa a, finalman, mwen ta rekòmande tou pou pran yon plim ak papye epi trase bagay sa yo soti anvan, pandan, epi apre ou te ekri tout nan kòd ou a. Jis asire w ke ou te gen sa yo endikasyon jis dwat. 

Mwen swete w pi bon an nan chans. Apre sa, yon fwa ou te fini, si ou ta renmen bay defi tablo a ak gwo wè ki jan vit se pwogram ou an konpare ak kamarad klas ou a, lè sa a mwen ankouraje ou yo tcheke ki soti. 

Ak sa, ou te fini PSet a ortograf. Non mwen se Zamyla, e sa se CS50.