ZAMYLA Chan: ni gumawa Hayaan isang spell checker. Kung buksan mo speller.c, pagkatapos ay makakakita ka ng na karamihan sa mga pag-andar para sa check ng isang text file laban sa isang diksyunaryo ay naka-ginawa para sa iyo. . / Speller, pagpasa sa isang text diksyunaryo mag-file at pagkatapos ay isa pang file na teksto, Susuriin na tekstong file laban sa diksyunaryo. 

Ngayon, diksyunaryo ng mga tekstong file ay maglalaman wastong salita, isa sa bawat linya. Pagkatapos ay speller.c tumawag Load sa diksyunaryo text file. Ito tumawag sa isang function na tinatawag Suriin sa bawat salita sa inputted text file, pag-print ng lahat ng maling nabaybay na mga salita. 

Speller.c Tatawagan din Sukat sa malaman ang dami ng mga salita sa diksyunaryo at tawagan alisan ng bala sa libreng up ang memorya. speller.c ay magkakaroon din masubaybayan kung gaano karaming oras ay ginagamit upang magsagawa ng mga mga proseso, ngunit kami ay makapunta sa na mamaya. 

Kaya kung ano ang kailangan naming gawin? Kailangan naming i-fill in dictionary.c. Sa dictionary.c, mayroon kaming mga lingkod Mag-load ng function, na ikinarga ng diksiyunaryo. Ang pagpapaandar Check, na sumusuri kung isang ibinigay na salita ay sa diksyunaryo. Nagbabalik Ang Sukat ng function na ang bilang ng mga salita sa diksyunaryo. At sa wakas, na mag-ibis namin, na frees sa diksyunaryo mula sa memorya. 

Kaya una, pagharap sa isang bagay ni-load ipaalam. Para sa bawat salita sa teksto ng diksyunaryo file, Load mag-iimbak ang mga salitang iyon sa ang diksyunaryo ng istraktura ng data na pipiliin mo, alinman sa isang hash talahanayan o isang trie. Makikita pumunta ako sa ibabaw ng parehong sa lumakad na ito sa pamamagitan. 

Unang ipaalam-usapan natin ang tungkol sa hash table. Sabihing kayo ay nagkaroon ng 10 billiard ball at na gusto mo upang i-imbak ang mga ito. Maaari mong ilagay ang mga ito lahat sa isang bucket, at kapag kailangan mo ang isang tiyak na bulitin, nais mong gawin isa sa labas ng bucket sa isang pagkakataon hinahanap na bola. At may 10 lamang na bola, dapat ay magagawang upang mahanap ang iyong bola sa isang makatwirang tagal ng oras. 

Ngunit paano kung nagkaroon ka ng 20 bola? Maaaring tumagal ng kaunti na ngayon. Paano ang tungkol sa 100? 1,000? Ngayon, magiging mas madali kung kayo ay nagkaroon ng maramihang mga bucket. Siguro isa bucket para sa mga bola numbered zero sa pamamagitan ng siyam, isa pang bucket para sa bola may bilang 10 sa pamamagitan ng 19, at iba pa. 

Ngayon kapag kailangan mo upang tumingin para sa mga tiyak bola, awtomatikong magagawa mo pumunta sa isang tukoy na bucket at maghanap sa pamamagitan ng na bucket. At kung sa bawat bucket ay may humigit-kumulang sa 10 bola, pagkatapos ay maaari mong madaling maghanap sa pamamagitan nito. 

Ngayon, dahil kami ay pagharap sa mga diksyunaryo, isang single bucket para sa lahat ng mga salita sa diksyunaryo habilin marahil maging malayo masyadong ilang mga bucket. Kaya ipaalam sa tumagal ng isang pagtingin sa hash table. 

Isipin ito bilang isang array ng mga bucket. At sa kasong ito, ang mga bucket ang aming mga listahan ng naka-link. At muli naming ipamahagi ang lahat ng aming mga salita sa gitna ng mga maramihang mga listahan ng naka-link sa isang organisadong paraan gamit ang isang hash, na kung saan ay sabihin sa amin kung aling mga Bucket ng isang ibinigay na key, isang naibigay na salita, ay kabilang sa. 

Ni kumatawan ito schematically Hayaan. Ang bughaw na mga kahon dito naglalaman ng mga halaga at pulang kahon tumuturo sa isa pang halaga pointer pares. Susubukan naming tumawag sa mga pares ng mga node. Ngayon, sa bawat bucket, tulad ng sinabi ko mas maaga, ay isang naka-link na listahan. Sa naka-link na mga listahan, ang bawat node ay may halaga, pati na rin ang isang pointer sa susunod na halaga. 

Ngayon, pagharap sa mga naka-link na mga listahan, ito ay napakahalaga na sa iyo huwag mawala ang anumang mga link. At isa pang katotohanan na dapat tandaan ay ang huling node, kung hindi ito ay tumuturo sa isa pang node, tumuturo null. 

Kaya kung paano kinakatawan namin ito sa C? Tukuyin namin ang aming struct dito. At ang mga halaga sa kasong ito ay isang pansamantalang trabaho array ng haba. Haba ng plus 1, kung saan ang haba ay ang maximum na haba ng anumang salita, plus 1 para sa ang null Terminator. At pagkatapos ay mayroon kaming isang pointer sa isa pang node na tinatawag na ang Susunod. 

Kaya hayaan ang gumawa ng isang maliit na naka-link listahan. Una, gugustuhin mong i-malloc iyong node, na lumikha ng puwang sa memorya ng ang laki ng iyong uri ng node ng. At gumawa ng isa pang node, muli mallocing. 

Ngayon kung gusto mong magtalaga ng isang halaga sa isang salita, pagkatapos ay maaari naming sabihin node1 arrow ay katumbas ng salitang "Hello." Ito arrow operator dereferences ang pointer at ina-access ng variable ang struct ni. Sa paraang ito, wala kaming gamitin kapwa ang tuldok at ang bituin na operator. 

Kaya pagkatapos Mayroon akong node2 arrow salita ay katumbas ng "Mundo." At doon, ang mga halaga ay populated sa aking mga node. Upang gumawa ng mga link, makikita ba akong magpasa sa node1 na arrow sa tabi, sa pag-access na node bituin, na node pointer, katumbas node2, pagturo node1 sa node2 dalawa. At doon ay mayroon kaming isang naka-link na listahan. 

Kaya na noon ay lamang ng isang listahan na naka-link, ngunit isang hash talahanayan ay isang buong hanay ng mga naka-link na mga listahan. Well, magpapadala kami ay may parehong node buuin tulad ng dati. Ngunit kung gusto naming ng isang aktwal na hash talahanayan, pagkatapos ay maaari naming lamang gumawa ng node pointer array dito. Halimbawa, laki ng 500. 

Ngayon notice, may pupuntahan maging isang kalakalan off sa pagitan ng laki ng iyong hash table at ang laki ng iyong mga naka-link na mga listahan. Kung mayroon kang isang talagang mataas na bilang ng mga bucket, imagining pagkakaroon upang tumakbo pabalik at nakasaad sa isang linya sa mahanap ang iyong bucket. Ngunit mo ring ayaw ng maliit na bilang ng mga bucket, dahil pagkatapos kami pabalik sa ang orihinal na problema ng kung paano nagkakaroon masyadong maraming mga bola sa aming bucket. 

OK, ngunit kung saan ang aming mga bola pumunta? Well, kailangan muna naming magkaroon ng bola, tama? Kaya hayaan malloc ng isang node para sa bawat mga bagong salita na mayroon kami. node * new_node Kapantay malloc (sizeof (node)). 

Ngayon na kami ay may istraktura na ito, kami Maaari i-scan sa, gamit ang function fscanf, isang string mula sa aming mga file, kung na ang isang file na diksyonaryo, sa new_node arrow salita, kung saan new_node arrow salita ay ang aming destinasyon ng salitang iyon. 

Susunod, kailangan namin nais na hash na salita gamit ang isang hash. Ang isang hash tumatagal ng isang string at nagbabalik ng isang index. Sa kasong ito, ang index ay sa mas kaunti kaysa sa bilang ng mga mga bucket na mayroon ka. 

Ngayon, hash function, kapag sinusubukan upang makahanap ng isa at lumikha ng isa ng ng iyong sariling, tandaan na sila kailangang maging deterministic. Iyon ay nangangahulugan na kailangan ng parehong halagang ito sa map sa parehong bucket bawat oras na hash mo ito. 

Ito ay uri ng tulad ng isang library. Kapag kumuha ka ng libro, batay sa may-akda, alam mo kung aling shelf dapat ito pumunta sa, kung ito ay ang numero ng shelf isa, dalawa, o tatlo. At aklat na laging nabibilang sa alinman sa shelf isa, dalawa, o tatlo. 

Kaya, kung new_node arrow salita ay may salita mula sa iyong diksyunaryo, pagkatapos ay hashing new_node arrow salita habilin bigyan kami ng index ng bucket ng hash table. At pagkatapos ay makikita isingit namin na sa na tiyak na naka-link listahan ipinahiwatig ng bumalik halaga ng aming hash. 

Tingnan natin ang isang halimbawa ng Hayaan pagpasok ng isang node sa simula ng isang naka-link na listahan. Kung ulo ay isang node pointer na nagpapahiwatig ang simula ng isang naka-link na listahan, at new_node nagpapahiwatig ang bagong node na gusto mong ipasok sa, lamang nagtatalaga ng ulo upang new_node gusto mawala ang link papunta sa natitirang bahagi ng listahan. Kaya hindi namin nais upang gawin ito. 

Sa halip, gusto naming makasiguro na na hawakan namin ang on sa bawat solong node sa aming programa. Kaya't ang pagpapatakbo new_node arrow sa tabi Kapantay ulo at pagkatapos ay ulo ay katumbas ng new_node mapapanatili ang lahat ng mga link at hindi mawawala ang anumang. 

Ngunit ano kung nais mo ang iyong listahan upang maging pinagsunod-sunod, dahil ang pagkakaroon ng isang pinagsunod-sunod na naka-link ay maaaring maging mas madali para sa listahan naghahanap ito mamaya sa? Well, para sa na, kailangan mong malaman kung paano i-halang naka-link listahan. 

Upang tawirin ang isang naka-link na listahan, mayroon na ipagbigay- isang node pointer, isang node *, na kumilos bilang ang iyong cursor, na nagpapahiwatig na node ikaw ay nasa, simula sa unang elemento. Looping hanggang cursor ay walang bisa, kaya namin magsagawa ng ilang mga proseso at pagkatapos ay isulong ang cursor kapag kailangan namin gamit ang cursor halaga arrow. 

Tandaan, ito ay ang parehong bagay bilang sinasabi ng mga bituin cursor, dereferencing cursor, pagkatapos gamit ang tuldok halaga operator. Kaya ina-update ang cursor ay sa pamamagitan ng pagtatalaga ng ang cursor sa cursor arrow sa tabi. 

Sabihing kang matukoy na D nagiging sa sa pagitan ng C at E. Upang ipasok ang node, mayroon ang new_node D punto sa node E, na kung saan ay cursor sa susunod. At pagkatapos ay C, ang cursor, maaari pagkatapos ay ituro ang upang D. Sa ganoong paraan, mapanatili mo ang isang listahan. Mag-ingat na huwag mawala ang iyong mga link sa pamamagitan ng gumagalaw ang cursor arrow sa tabi ng D agad-agad. 

Ayos lang. Kaya na kung paano mo maaaring magpasok ng mga nodes, load ang mga ito sa, mga salita ng pag-load sa mga nodes, at ipasok ang mga ito sa iyong talahanayan ng hash. Kaya tingnan natin ang pagsusubok na ngayon hayaan. 

Sa isang trie, ang bawat node ay maglalaman ng isang array ng node na pointer, isa para sa bawat sulat sa alpabeto plus isang kudlit. At sa bawat elemento sa array ituturo sa isa pang node. Kung na node ay walang bisa, pagkatapos ay i-sulat na ay hindi pagpunta sa maging ang susunod na titik ng anumang mga salita sa isang pagkakasunod-sunod, dahil bawat salita ay nagpapahiwatig ito man ang huling katangian ng isang salita o hindi. 

Tingnan natin ang isang diagram Hayaan. Sana bagay habilin maging isang bit mas malinaw. Sa diagram na ito, nakita namin na lamang ilang mga titik at ilang substrings Sini nakalista out. Kaya maaari mong sundin ang ilang mga path, at lahat ng mga path ay humantong sa iyo upang iba't ibang salita. 

Kaya kung paano kinakatawan namin ito sa C? Well, ang bawat node ngayon ay pagpunta sa may isang Boolean halaga nagpapahiwatig kung na node ay ang katapusan ng isang ibinigay na salita o hindi. At pagkatapos ay magkakaroon ito din ay may isang array ng node na pointer tinatawag na mga bata, at doon ay pagpunta sa maging 27 sa mga ito. At tandaan, makikita mo ring isaalang- subaybayan ang iyong unang node. Kami ay pagpunta sa tumawag sa ugat na. 

Kaya iyon ang istraktura ng isang trie. Paano ko kakatawanin namin ito bilang isang diksyunaryo? Well, i-load ang mga salita sa, para sa bawat salita sa diksyunaryo, ikaw ay pagpunta sa nais upang umulit sa pamamagitan ng trie. At sa bawat elemento sa mga bata tumutugon sa isang iba't ibang mga letra. 

Kaya check sa mga halaga sa mga bata index i, kung saan i kumakatawan sa tiyak na index ng sulat na na sinusubukan mong ipasok. Well, kung ito ay walang bisa, pagkatapos mo makikita nais na malloc isang bagong node at may mga anak ituro ang i upang na node. 

Kung ito ay hindi null, pagkatapos ay nangangahulugan na na na ibinigay ng sangay, na ibinigay na substring, ay umiiral na. Kaya pagkatapos ay makikita mo lamang ilipat sa na bagong node at magpatuloy. Kung ikaw ay sa dulo ng mga salita na na sinusubukan mong i-load sa diksyonaryo, pagkatapos ay maaari mong itakda na kasalukuyang node na ikaw ay nasa sa true. 

Kaya tingnan natin ang isang halimbawa ng pagpasok ipaalam ang salitang "soro" sa aming diksiyunaryo. Magpanggap simulan namin gamit ang isang walang laman na diksiyunaryo. Ang unang titik, F, ay ilalagay sa mga bata index ng limang ng Roots mga anak ng array. Kaya isingit namin na in 

Ang titik O ay pagkatapos ay maging sa mga bata index 15, pagkatapos na F. At pagkatapos X Magiging kahit ibaba na, sumasanga off ng mga bata ang mga O ni. At pagkatapos ay dahil ang X ay ang huling titik ng salitang "soro," pagkatapos ay pupuntahan ko kulayan berde na upang isaad na ito ang dulo ng salita. Sa C, na ay pagtatakda ng ay Salita boolean sa halaga totoo. 

Ngayon ano kung ang susunod na salita na ikaw ay sa paglo-load sa ay ang salitang "foo"? Well, hindi mo kailangang mag-malloc anumang higit pang mga espasyo para sa F o para sa mga O, dahil mga umiiral na. Subalit ang huling O sa foo? Isa na iyon, kailangan mong mag-malloc. Gumawa ng isang bagong node para sa na, ang pagtatakda ang Salita ay Boolean sa true. 

Kaya ni isingit ngayon hayaan "aso." Dog habilin magsimula sa index ng tatlong ng Roots mga anak, dahil D ay may hindi pa nagawa na. At muli naming sundin ang isang kaparehong proseso bilang bago, na lumilikha ng substring aso, kung saan ay ang G ay kulay berde dahil iyon ang katapusan ng isang salita. 

Ngayon, paano kung gusto naming isingit "gawin"? Well, ito ay isang substring ng aso, kaya hindi namin kailangan upang malloc na ngayon. Ngunit huwag naming kailangan upang ipahiwatig kung saan kami nai Naabot ang dulo ng salitang iyon. Kaya ang O ay kulay berde. Ang pagpatuloy proseso na para sa bawat solong salita sa iyong diksiyonaryo, ikaw load ang mga ito sa sa alinman sa iyong hash talahanayan o ang iyong trie. 

speller.c ay pumasa sa mga string para sa dictionary.c upang masuri ang mga ito. Ngayon, ang Suriin ang function na ay may upang mapatakbo sa ilalim kasong kawalan ng damdamin. Ay nangangahulugan na na ang mga malalaking titik at maliliit na mga titik at isang halo ng mga parehong Dapat lahat equate sa totoo kung mayroon man kumbinasyon ng mga iyon ay nasa diksiyunaryo. Maaari mo ring ipagpalagay na ang mga string ay pagpunta lamang upang maglaman ng alpabetikong character o apostrophes. 

Kaya tingnan natin kung paano mo maaaring tingnan ipaalam may isang istraktura ng hash table. Well, kung umiiral ang salita, kung gayon ito maaaring matagpuan sa hash table. Kaya pagkatapos ay maaari mong subukan na makita na ang salita sa may-katuturang mga bucket. 

Kaya kung aling mga bucket ay magiging na salita in? Well, gusto mo makuha ang numero, index na ng mga bucket, sa pamamagitan ng hashing na salita at pagkatapos ay naghahanap sa na naka-link listahan, traversing sa pamamagitan ng buong naka-link na listahan, gamit ang String Ihambing ang function. 

Kung sa dulo ng naka-link na listahan ay Naabot, ibig sabihin na ang iyong cursor umabot null, pagkatapos ay ang salita ay hindi na matagpuan sa diksyunaryo. Hindi ito ay magiging sa anumang iba pang mga bucket. Kaya dito, maaari mong makita kung paano doon lakas maging isang kalakalan-off sa pagitan ng pagkakaroon ng alinman sa pinagsunod-sunod ng mga listahan na naka-link o unsorted bago. Alinman ay magdadala sa mas maraming oras sa panahon ng load o higit pang mga oras sa panahon ng tseke. 

Paano maaari kang mag-check in isang istraktura trie? Kami ay pagpunta sa paglalakbay pababa sa trie. Para sa bawat titik sa inputted salita na aming pagsusuri, magpapadala kami pumunta sa na nakaayon sangkap sa mga bata. 

Kung elemento na null, pagkatapos ay nangangahulugan na na walang mga substrings na naglalaman ng aming input salita, kaya ang salita ay maling. Kung ito ay hindi null, maaari naming lumipat sa susunod na titik ng salita na hindi namin pagsusuri at patuloy ang proseso na ito hanggang sa maabot namin ang pagtatapos ng input na salita. At pagkatapos ay maaari naming suriin kung maganda ang Salita ay totoo. Kung ito ay, pagkatapos ay mahusay. Ang salitang ay tama. Ngunit kung hindi, kahit na substring umiiral sa trie, ang salita ay maling nabaybay. 

Kapag ang Sukat ng function ay tinatawag na, laki dapat ibalik ang bilang ng mga salitang iyon ang nasa iyong ibinigay na diksyunaryo istraktura ng data. Kaya kung gumagamit ka ng isang hash talahanayan, mo Maaari alinman pumunta sa pamamagitan ng bawat solong naka-link na listahan sa bawat solong bucket ng pagbibilang sa bilang ng mga salita ang naroon. Kung gumagamit ka ng isang trie, maaari mong pumunta sa pamamagitan ng bawat non null landas sa iyong trie. O kaya habang naka-load ng diksyunaryo sa, marahil maaari mong subaybayan kung gaano maraming mga salita ka sa paglo-load in 

Sa sandaling tatapusin speller.c ng pagsuri sa text file laban sa diksyunaryo, pagkatapos ay tapos na ito at kaya tawag ito alisan ng bala, kung saan ang iyong trabaho ay upang palayain ang anumang bagay na iyong malloced. Kaya't kung ikaw ay gumagamit ng hash talahanayan, pagkatapos mo kailangan upang maging lalo na maingat upang maiwasan ang memorya ng paglabas sa pamamagitan ng hindi pagbabakante ng kahit ano maaga at may hawak na sa bawat single link bago mo libre. 

Kaya para sa bawat elemento sa hash talahanayan at para sa bawat node sa naka-link na listahan, makikita mo nais na palayain na node. Paano pumunta ka tungkol sa pagbabakante naka-link na listahan? Pagse-set ang iyong mga node pointer cursor sa ang ulo, sa simula ng naka-link na listahan, pagkatapos ay habang ang iyong cursor ay hindi null, maaari kang magtakda ng isang pansamantalang node pointer sa iyong cursor. Pagkatapos isulong ang cursor. At pagkatapos ay maaari mong palayain na pansamantalang halaga habang may hawak na sa pa rin sa lahat pagkatapos. 

Paano kung gumagamit ka ng isang trie? Pagkatapos ay ang pinakamahusay na paraan upang gawin ito ay upang alisan ng bala mula sa pinakadulo ibaba sa itaas. Sa pamamagitan ng paglalakbay sa posibleng pinakamababang node, maaari mong palayain ang lahat ng mga payo sa na ang mga bata at pagkatapos ay pag-urong paitaas, pagbabakante lahat ng elemento sa lahat ng mga bata array, hanggang sa maabot ang iyong tuktok na root node. Narito kung saan Recursion ay darating sa madaling-gamiting. 

Upang matiyak na marahil na iyong napalaya ang lahat ng bagay na iyong malloced, maaari mong gamitin ang Valgrind. Pagpapatakbo Valgrind tatakbo ang iyong mga programa pagbibilang kung gaano karaming mga byte ng memorya ginagamit mo at tinitiyak na ikaw ay napalaya ang mga ito sa lahat, na nagsasabi sa iyo kung saan maaaring mayroon ka nakalimutan upang libre. Kaya tumakbo na at isang beses ay nagsasabi sa iyo Valgrind at nagbibigay sa iyo ng sige, pagkatapos ay tapos ka na mag-ibis. 

Ngayon, isang pares ng mga tip bago ka pumunta off at simulan ang pagpapatupad ng iyong diksiyunaryo. Gusto ko inirerekumenda upang pumasa sa isang mas maliit kapag diksyunaryo na sinusubukan mong subukin out at mga bagay na pag-debug na may GDP. Ang paggamit ng speller ay. / Speller, isang opsyonal diksyonaryo, at pagkatapos ng text. 

Sa pamamagitan ng default, ito ikinarga sa ang malaking diksiyunaryo. Kaya baka gusto mong pumasa sa maliit na diksyonaryo, o marahil kahit na gawin ang iyong mga sarili, pag-customize ang iyong diksyunaryo at ang iyong mga tekstong file. 

At pagkatapos ay sa wakas, ako gusto rin namin upang kumuha ng panulat at papel at gumuhit out mga bagay bago, habang, at pagkatapos ng na naisulat sa lahat ng iyong code. Tiyakin na mayroon ka lamang lamang kanan mga payo. 

Nais ko sa iyo ang suwertehin ka sana. At kapag natapos mo na, kung gusto mo upang hamunin ang malaking board at makita kung paano mabilis ang iyong programa ay kumpara sa ang iyong mga kaklase ', pagkatapos ay Hinihikayat ko sa iyo na suriin na ang out. 

Gamit na, tapos ka na ang speller PSet. Ang pangalan ko ay Zamyla, at ito ay CS50.