[MIZIK jwe] 

ROB BOWDEN: Hi. Mwen se Rob. Li kite yo sa a solisyon deyò. Se konsa, isit la nou ap ale nan aplike yon tab an jeneral. Nou wè ke ne la konstri nan nou an tab ki pral gade tankou sa a. Se konsa, li la pral fè yon mo Char etalaj de gwosè Ki Souvan + 1. pa bliye + 1 a, depi kantite maksimòm la mo an nan diksyonè a se 45 karaktè. Lè sa a, nou pral bezwen yon siplemantè N. pou zewo nan antislach. 

Lè sa a, hashtable nou yo nan chak bokit ki pral estoke yon lis lye nan nœuds. Nou pa yo ap fè lineyè sonde isit la. Se konsa, yo nan lòd yo genyen lyen pwochen an eleman nan bokit la, nou bezwen yon konstri ne * kap vini an. OK. Se konsa, se sa ki yon ne sanble. 

Koulye a, isit la se deklarasyon an nan hashtable nou an. Li pral gen 16.834 bokit. Men, nimewo sa a pa reyèlman gen pwoblèm. E finalman, nou pral gen a mondyal varyab gwosè hashtable, ki ki pral kòmanse desann kòm zewo. Apre sa, li nan ale nan kenbe tras nan ki jan anpil mo yo nan diksyonè nou an. 

Se konsa, kite a pran yon gade nan chaj. Remake chaj, li retounen yon bouleen. Ou retounen vre si li te avèk siksè chaje ak fo otreman. Apre sa, li pran yon Char diksyonè CONST *, ki se diksyonè a ke nou vle louvri. Se konsa, sa a, se premye bagay la nou pral fè. 

Nou pral fopen la diksyonè pou lekti. Apre sa, nou pral gen fè asire w ke li plas. Se konsa, si li tounen NULL, lè sa a nou pa t ' avèk siksè louvri diksyonè a. Apre sa, nou bezwen retounen fo. Men, an konsideran ke li te fè avèk siksè louvri, lè sa a nou vle li a diksyonè. Se konsa, kenbe loupin jiskaske nou jwenn kèk rezon ki fè yo kraze soti nan sa a bouk, ki nou pral wè. Se konsa, kenbe loupin. 

Epi, koulye a nou pral malok yon ne sèl. Ak nan kou nou bezwen nan lè tcheke ankò. Se konsa, si mallocing pa t 'reyisi, Lè sa a, nou vle dechaje nenpòt ki ne ke nou rive malok anvan, fèmen a diksyonè epi retounen bay manti. Men, inyore ke, an konsideran nou nan plas, lè sa a nou vle sèvi ak fskanf li yon mo yon sèl soti nan nou an diksyonè nan ne nou an. Se konsa, sonje ke antre> mo a se Char la tanpon mo ki gen yon gwosè LENGHTH + 1 ke nou ap ale nan magazen pawòl Bondye a pous 

Se konsa, fskanf ki pral retounen 1, osi lontan kòm li te kapab avèk siksè li yon mo ki soti nan dosye a. Si youn nan yon erè sa yo rive, oswa nou rive nan fen an nan dosye a, li pa pral retounen 1. Nan ka sa a li pa retounen 1, nou ap finalman ale nan kraze soti nan sa a pandan y ap bouk. Se konsa, nou wè ke yon fwa nou gen avèk siksè li yon mo nan antre> mo, Lè sa a, nou pral ak sa yo ki mo lè l sèvi avèk fonksyon hash nou an. 

Se pou nou pran yon gade nan fonksyon an hash. Se konsa, ou pa reyèlman bezwen yo konprann sa a. Apre sa, aktyèlman nou jis rale hash sa a fonksyone soti nan entènèt la. Sèl bagay ou bezwen rekonèt se ke sa a pran yon mo CONST * Char. Se konsa, li pran yon fisèl kòm opinyon, ak retounen yon Int siye kòm pwodiksyon. Se konsa, ki nan tout yon fonksyon hash se, se li pran nan yon D 'ak ap ba ou yon endèks nan hashtable la. 

Remake nou ap moding pa NUM_BUCKETS, se konsa ke valè tounen aktyèlman se yon endèks nan hashtable la ak fè sa ki pa endèks pi lwen pase a limit nan etalaj la. Se konsa, bay sa fonksyon, nou pral Hash pawòl Bondye a ke nou li a diksyonè. Lè sa a, nou pral sèvi ak ki hash insert la antre nan hashtable la. 

Koulye a, hashtable hash se aktyèl la lye lis nan tablo a. Apre sa, li trè posib ke li nan jis NULL. Nou vle insert antre nou an nan la kòmanse nan lis sa a lye. Se konsa, nou pral gen kounye a nou pwen antre nan sa ki hashtable la kounye a lonje dwèt yo. Lè sa a, nou pral nan magazen, nan hashtable la nan la hash, antre aktyèl la. Se konsa, de liy sa yo avèk siksè insert antre nan nan kòmansman an nan la lis lye nan ki endèks nan hashtable la. 

Yon fwa nou ap fè ak sa, nou konnen ke nou jwenn yon lòt mo nan la diksyonè, epi nou enkreman ankò. Se konsa, nou kontinye ap fè sa jouk lè fskanf finalman tounen yon bagay ki pa 1 nan ki pwen sonje ke nou bezwen libere antre. Se konsa, moute isit la nou malloced yon antre. Apre sa, nou te eseye li yon bagay soti nan diksyonè a. Apre sa, nou pa t 'avèk siksè li yon bagay soti nan diksyonè a, nan ka sa a nou bezwen libere antre nan ke nou pa janm aktyèlman mete nan la hashtable, epi finalman kase. 

Yon fwa nou kraze soti nou bezwen wè, byen, t 'nou kraze soti paske se la te yon erè li nan dosye a? Oswa t 'nou kraze soti paske nou rive nan fen an nan dosye a? Si te gen yon erè, lè sa a nou vle tounen bay manti. Paske chay pa t 'reyisi. Apre sa, nan pwosesis la nou vle dechaje tout mo sa yo ke nou li nan, ak fèmen dosye a diksyonè. 

Si nou sipoze nou te reyisi, Lè sa a, nou jis toujou bezwen yo fèmen diksyonè a pote, epi finalman retounen vre depi nou avèk siksè chaje diksyonè a. Epi sa a, li pou chaj. Se konsa, koulye tcheke, yo bay yon hashtable chaje, ki pral gade tankou sa a. Se konsa, tcheke, li retounen yon bouleen, ki se ale nan endike si te pase nan nan Char mo *, si wi ou non te pase nan nan fil se nan diksyonè nou an. Se konsa, si li se an nan diksyonè a, si se nan hashtable nou an, nou pral retounen vre. Men, si li pa, nou pral retounen bay manti. 

Bay sa a te pase nan mo, nou ap ale nan Hash mo a. Koulye a, yon bagay enpòtan yo rekonèt se ke nan chaj nou te konnen ke tout la mo nou pral pi ba ka. Men, isit la nou pa te tèlman asire w. Si nou pran yon gade nan fonksyon hash nou an, fonksyon hash nou an aktyèlman se pi ba aman chak karaktè nan pawòl Bondye a. Se konsa, kèlkeswa lèt majiskil la nan mo, fonksyon hash nou an, se retounen nan endèks la menm pou tou sa la lèt majiskil se, menm jan li ta gen tounen pou yon konplètman miniskil vèsyon an pawòl Bondye a. Oke. Sa a endèks nou an, se nan la hashtable pou sa a mo. 

Koulye a, sa a pou bouk ki pral repňte sou lis la lye sa ki te nan moman sa Konpayi paran yo. Se konsa, remake nou ap inisyalizin antre nan pwen ak sa yo ki endèks. Nou pral kontinye pandan y ap antre! = NULL. Apre sa, sonje ke à konsèy la nan lis nou an antre lye = antre> kap vini an. Se konsa, gen nou an pwen antre aktyèl yo bay atik nan pwochen nan lis la lye. 

Se konsa, pou chak antre nan lis la lye, nou pral sèvi ak strcasecmp. Li pa strcomp. Paske yon lòt fwa ankò, nou vle fè bagay sa yo ka insensitively. Se konsa, nou sèvi ak strcasecmp yo konpare a pawòl ki te pase nan sa a fonksyon kont pawòl Bondye a se sa ki nan sa a antre. Si li retounen zewo, sa vle di te gen yon match, nan ka sa nou vle retounen vre. Nou jwenn avèk siksè nan mo nan hashtable nou an. 

Si pa t 'gen yon match, lè sa a nou ap ale nan bouk ankò, li gade nan la pwochen antre. Epitou, n ap kontinye loupin pandan y ap gen yo antre nan lis sa a lye. Kisa k ap pase si nou kraze soti nan sa a pou bouk? Sa vle di nou pa t 'jwenn yon antre ki matche mo sa a, nan ki ka nou retounen fo ke yo endike ke nou hashtable pa t 'gen mo sa a. Epi sa a, yon chèk. 

Se konsa, kite a pran yon gade nan gwosè. Gwosè Koulye a, a pwal trè senp. Depi sonje nan chaj, pou chak mo nou te jwenn, nou enkremante yon mondyal varyab hashtable gwosè. Se konsa, fonksyon an gwosè se jis ale retounen varyab mondyal la. Epi sa a, li. 

Koulye a, finalman, nou bezwen dechaje la diksyonè yon fwa tout bagay nan fè. Se konsa, kouman nou pral fè sa? Dwa isit la nou ap loupin sou tout bokit nan tablo nou an. Se konsa, gen NUM_BUCKETS bokit. Epi pou chak lis lye nan nou an hashtable, nou ap ale nan bouk sou antye nan lis la lye, libere chak eleman. 

Koulye a, nou bezwen dwe fè atansyon. Se konsa, isit la nou gen yon varyab pou yon ti tan ki nan estoke konsèy la pwochen an eleman nan lis la lye. Lè sa a, nou pral gratis eleman aktyèl la. Nou bezwen asire w ke nou fè sa depi nou pa ka jis gratis eleman aktyèl la ak Lè sa a, eseye jwenn aksè nan konsèy kap vini an, depi yon fwa nou te libere li, memwa a vin valab. 

Se konsa, nou bezwen kenbe otou yon konsèy eleman kap vini an, Lè sa a, nou ka libere nan eleman kounye a, ak Lè sa a, nou ka mete eleman aktyèl nou yo lonje dwèt sou eleman nan pwochen an. Nou pral bouk pandan y ap gen eleman nan lis sa a lye. Nou pral fè sa pou tout lye lis nan hashtable la. Apre sa, yon fwa nou ap fè ak sa, nou te konplètman chaje hashtable la, ak nou ap fè. Se konsa, li enposib pou debake janm retounen bay manti. Lè nou ap fè, nou jis retounen vre. 

Se pou yo bay sa a solisyon yon eseye. Se konsa, kite a pran yon gade nan sa ki nou konstri ne ap gade tankou. Isit la nou wè nou pral gen yon bouleen mo ak yon ne konstri * timoun bracket alfabè a. Se konsa, premye bagay la ou ka mande, poukisa se ALPHABET ed defini kòm 27? Oke, sonje ke nou ap ale nan bezwen yo dwe manyen apostwòf la. Se konsa, ki k ap pase yo dwe yon ti jan nan yon ka espesyal nan tout pwogram sa a. 

Koulye a, sonje ki jan yon trye aktyèlman ap travay. Se pou nou di nou ap Indexing pawòl Bondye a "Chat." Lè sa a, soti nan rasin lan nan trye, nou pral gade nan timoun yo etalaj, e nou pral fè yon gade nan la endèks ki koresponn ak lèt ​​la C. Se konsa, ke yo pral Catalogue 2. Se konsa, bay sa, ki pral ban nou yon nouvo ne. Lè sa a, nou pral travay nan ki ne. 

Se konsa, bay yo ke ne, nou yon lòt fwa ankò ale nan gade nan etalaj la timoun yo. Apre sa, nou pral gade nan endèks zewo koresponn ak yon an nan chat. Se konsa, Lè sa a, nou pral pou yo ale nan ki ne, ak bay sa ne nou pral fè yon gade nan fen a li nan yon korespondan T. Apre sa, deplase sou ak sa yo ki ne, finalman, nou te konplètman gade nan pawòl Bondye nou an "chat." Epi, koulye a bouleen se pawòl Bondye sipoze endike si mo sa a bay se aktyèlman yon mo. 

Se konsa, poukisa nou bezwen ki ka espesyal? Oke sa ki nan pawòl Bondye a "katastwòf" se nan diksyonè nou an, men nan Mo "chat" se pa? Se konsa, ak je l 'nan wè si pawòl Bondye a "chat" se nan diksyonè nou an, nou ale nan avèk siksè gade nan endis yo C-A-T nan rejyon ne. Men, sa a sèlman paske katastwòf te rive yo kreye nœuds sou wout la soti nan C-A-T yo, tout wout ki mennen nan nan fen mo a. Se konsa, bouleen mo itilize yo endike si kote sa a an patikilye aktyèlman endike yon mo. 

Tout dwa. Se konsa, kounye a ke nou konnen ki sa li trye se ale nan gade tankou, se pou yo gade nan la chaje fonksyon. Se konsa, chay ki pral retounen yon bouleen pou si nou avèk siksè oswa san siksè chaje diksyonè a. Lè sa a a pwal diksyonè a ke nou vle chaje. 

Se konsa, premye bagay nou ap fè se louvri sa ki diksyonè pou lekti. Epi nou gen a asire w nou pa t 'febli. Se konsa, si diksyonè a pa t ' avèk siksè louvri, li pral retounen nil, nan ki ka nou ap ale nan retounen bay manti. Men, an konsideran ke li avèk siksè louvri, lè sa a nou ka aktyèlman li nan diksyonè a. 

Se konsa, premye bagay nou pral vle fè se nou gen sa a mondyal rasin varyab. Koulye a, rasin a pwal yon ne *. Li nan tèt la nan trye nou an ke nou ap yo pral iteration nan. Se konsa, premye bagay la ke nou ap ale vle fè se asiyen memwa pou rasin nou an. Remake nou ap lè l sèvi avèk calloc la fonksyon, ki se fondamantalman menm bagay la tou kòm fonksyon an malok, eksepte li a garanti yo retounen yon bagay ki konplètman zero deyò. Se konsa, si nou itilize malok, nou ta bezwen ale nan tout nan pwent yo nan nou an ne, ak asire w ke yo ap tout nil. Se konsa, calloc pral fè sa pou nou. 

Koulye a, jis tankou malok, nou bezwen fè asire w ke alokasyon an te aktyèlman siksè. Si sa a tounen nil, lè sa a nou ap oblije fèmen pòt oswa diksyonè ranpli epi retounen bay manti. Se konsa, an konsideran alokasyon ki te siksè, nou pral sèvi ak yon ne * kurseur repňte nan trye nou an. Se konsa, rasin nou pa janm ale nan chanje, men nou ap ale nan sèvi ak kurseur aktyèlman ale nan ne ne. 

Se konsa, nan sa a pou bouk nou ap li nan dosye a diksyonè. Apre sa, n ap lè l sèvi avèk fgetc. Fgetc ki pral gen tan pwan yon sèl N. nan dosye a. Nou pral kontinye arachman karaktè pandan ke nou pa rive nan fen nan dosye a. 

Gen de ka nou bezwen okipe. Premye a, si karaktè a pa t 'yon liy nouvo. Se konsa, nou konnen si se te yon liy nouvo, Lè sa a, nou ap sou pou avanse pou sou yon nouvo mo. Men, an konsideran li pa t 'yon liy nouvo, Lè sa a, isit la nou vle konnen nan endèks nou pral endèks nan nan etalaj la timoun ki nou te etidye anvan. 

Se konsa, tankou mwen te di anvan, nou bezwen ka espesyal apostwòf la. Avi nou ap lè l sèvi avèk tèrsyèr la operatè isit la. Se konsa, nou ap ale nan li sa a kòm, si karaktè a nou li nan te gen yon apostwòf, lè sa a nou pral mete endèks = "ALPHABET" -1, ki pral gen endèks la 26. 

Lòt Bagay, si li pa t 'yon apostwòf, gen nou pral mete endèks la egal a c - yon. Se konsa, sonje tounen soti nan deja p-kouche, c - yon ki pral ban nou an alfabetik pozisyon nan C. Se konsa, si C se lèt A a, sa a pral ban nou endèks zewo. Pou lèt la B, li pral ba nou endèks la 1, ak sou sa. 

Se konsa, sa a ba nou endèks la nan la timoun etalaj ke nou vle. Koulye a, si sa a endèks se kounye a nil nan timoun yo, sa vle di ke yon ne pa ki egziste kounye a soti nan ki chemen. Se konsa, nou bezwen asiyen yon ne pou sa chemen. Sa a ki sa nou pral fè isit la. 

Se konsa, nou ap ale nan ankò sèvi ak calloc la fonksyon, se konsa ke nou pa oblije zewo soti tout endikasyon yo. Epi nou ankò bezwen tcheke ki calloc pa t 'febli. Si calloc t rate, lè sa a nou bezwen dechaje tout bagay, fèmen nou an diksyonè, epi retounen bay manti. Se konsa, an konsideran ke li pa t 'echwe, Lè sa a, sa a pral kreye yon timoun nouvo pou nou. Lè sa a, nou pral ale nan ke pitit. Kurseur nou yo ap repňte desann nan sa timoun nan. 

Koulye a, si sa a pa t 'nil yo kòmanse avèk yo, Lè sa a, kurseur nan ka jis repňte desann nan ke pitit san yo pa aktyèlman li te gen asiyen anyen. Sa a se ka a kote nou te rive premye asiyen pawòl Bondye a "chat." Apre sa, sa vle di lè nou ale nan asiyen "Katastwòf," nou pa bezwen yo kreye nœuds pou C-A-T ankò. Yo deja egziste. 

Ki sa ki se sa a lòt moun? Sa a se kondisyon an kote c te antislach n, kote c te yon liy nouvo. Sa vle di ke nou gen avèk siksè ranpli yon mo. Kounye a ki sa nou vle fè lè nou konplete avèk siksè yon mo? Nou pral itilize sa a jaden mo andedan nan ne konstri nou an. Nou vle mete ke yo vre. Se konsa, ki endike ke ne sa a ki endike ke yon siksè mo, yon mo vrè. 

Koulye a, ke yo vre. Nou vle Reyajiste kurseur nou an nan pwen nan konmansman an nan trye la ankò. E finalman, enkreman diksyonè nou an gwosè, depi nou te jwenn yon lòt travay. Se konsa, nou ap ale nan kontinye ap fè sa, lekti nan karaktè pa karaktè, konstwi nouvo nœuds nan trye nou yo ak pou chak mo nan diksyonè a, jouk nou finalman rive nan C! = èof, nan ki ka nou kraze soti nan dosye a. 

Koulye a, gen de ka ki poko gen ki nou ka gen frape èof. Premye a se si te gen yon erè li nan dosye a. Se konsa, si te gen yon erè, nou bezwen fè tipik la. Dechaje tout bagay, fèmen dosye a, retounen fo. Si nou sipoze gen pa t 'yon erè, ki jis vle di nou aktyèlman frape nan fen dosye a, nan ki ka, nou fèmen a ranpli epi retounen vre depi nou diksyonè avèk siksè chaje nan trye nou an. 

Se konsa, kounye a kite a tcheke deyò chèk la. Gade nan fonksyon an chèk, nou wè ki chèk ki pral retounen yon bouleen. Li retounen vre si mo sa a ke li nan ke yo te pase se nan trye nou an. Li retounen fo otreman. Se konsa, kouman ou menm ki detèmine si mo sa a se nan trye nou an? 

Nou wè isit la ke, jis tankou anvan, nou pral sèvi ak kurseur repňte nan trye nou an. Koulye a, isit la nou ap ale nan repňte sou tout pawòl nou yo. Se konsa, iteration sou pawòl Bondye a nou se sot pase yo, nou pral detèmine a endèks nan etalaj la timoun ki koresponn ak mo bracket I. Se konsa, sa a ki pral gade egzakteman tankou chaj, kote si mo [mwen] se yon apostwòf, lè sa a nou vle yo sèvi ak endèks "ALPHABET" - 1. Paske nou detèmine ke sa se kote nou pral nan magazen apostrof. 

Lòt Bagay nou pral sèvi ak de mo pi ba bracket I. Se konsa, sonje mo sa a kapab gen abitrè lèt majiskil. Se konsa, nou vle asire nou ke nou ap lè l sèvi avèk yon vèsyon miniskil de bagay sa yo. Lè sa a, fè soustraksyon soti nan ke 'yon' yo yon fwa ankò ban nou alfabetik la pozisyon nan ki karaktè. Se konsa, ki k ap pase yo dwe endèks nou nan etalaj la timoun yo. 

Epi, koulye a si sa endèks nan timoun yo etalaj se nil, sa vle di nou pa kapab kontinye iteration desann trye nou an. Si sa a, se ka a, mo sa a pa kapab petèt dwe nan trye nou an. Depi si li te, ki ta vle di ta gen yon chemen desann nan mo sa a. Epi ou pa ta janm rankontre nil. Se konsa, rankontre nil, nou retounen fo. Pawòl Bondye a se pa an nan diksyonè a. Si se pa t nil, lè sa a nou ap pral kontinye iteration. 

Se konsa, nou pral soti la kurseur nan pwen ak sa yo ki an patikilye ne nan ki Konpayi paran yo. Nou kontinye ap fè sa nan tout pawòl Bondye a tout antye, an konsideran nou pa janm frape nil. Sa vle di nou te kapab jwenn nan pawòl Bondye a tout antye epi jwenn yon ne nan eseye nou an. Men, nou pa ap byen fè ankò. 

Nou pa vle jis retounen vre. Nou vle retounen kurseur> mo. Depi sonje ankò, se "chat" se pa nan diksyonè nou an, ak "katastwòf" se, Lè sa a, nou pral avèk siksè nou jwenn nan pawòl Bondye a "chat." Men, kurseur mo yo pral fo ak pa vre. Se konsa, nou retounen mo kurseur yo endike si wi ou non ne sa a se aktyèlman yon mo. Epi sa a, li pou chèk la. 

Se konsa, kite a tcheke deyò gwosè. Se konsa, gwosè a pwal trè fasil depi, sonje nan chaj, nou incrementing diksyonè gwosè pou chak mo ke nou rankontre. Se konsa, gwosè se jis ale nan retounen diksyonè gwosè. Epi sa a, li. 

Se konsa, Finalman nou te dechaje. Se konsa, dechaje, nou ap ale nan sèvi ak yon fonksyon repetitif ki aktyèlman fè tout nan travay la pou nou. Se konsa, fonksyon nou an, se ale nan y'a rele l 'sou decharjeur. Ki sa ki decharjeur pral fè? Nou wè isit la ke decharjeur ki pral repňte sou tout timoun yo nan ne patikilye sa a. Men, si ne nan pitit se pa nil, lè sa a nou pral dechaje ne nan timoun. 

Se konsa, sa a se ou recursive dechaje tout pitit nou yo. Yon fwa nou ap asire w ke tout timoun nou yo yo te chaje, lè sa a nou ka nou libere tèt nou, se konsa dechaje tèt nou. Sa a pral travay recursive dechaje trye a tout antye. Lè sa a, yon fwa ki nan fè, nou ka jis retounen vre. Debake pa ka febli. Nou jis ap libere bagay sa yo. Se konsa, yon fwa nou ap fè libere tout bagay, retounen vre. Epi sa a, li. Non mwen se Rob. Lè sa a te ortograf. 

[MIZIK jwe]