[Powered by Google Translate] [Walkthrough - Problema Itakda 5]
[Zamyla Chan - Harvard University]
[Ito ay CS50. - CS50.TV]
>> Ayos lang. Hello, lahat, at maligayang pagdating sa walkthrough 5.
>> Pset5 ay mga maling spelling, kung saan kami gumagawa ng spell-checker.
-Spell-pamato ay lubos na mahalaga.
Ay ito kailanman nangyari sa iyo?
Makipagtulungan ka napaka, napaka magtipon sa isang papel para sa isang pagkakagalit
at pagkatapos pa rin ng isang napaka-rade ng glow tulad ng D o D =
at lahat ng dahil ikaw ang liverwurst spoiler sa salitang whale malawak.
Oo, pagwawasto iyong peppers ay isang bagay ng, ang sukdulan kawalan ng lakas.
Ito ay isang problema na nakakaapekto sa tunay na lalaki, tunay na lalaki mag-aaral.
Isang beses ako ay sinabi sa pamamagitan ng aking sith grado tagapagpapasakit na hindi ko nais na makakuha ng sa isang mahusay na kasamahan.
At na ang lahat ko kailanman nais, na ang lahat ng kid anumang nais sa aking edad,
lamang upang makakuha ng sa isang mahusay na kasamahan.
At hindi lamang anumang kasamahan. Hindi. Nais kong pumunta sa isang kasamahan sa Ivory Legal.
Kaya kung ako ay hindi pagpapabuti, nawala ang aking mga pangarap ng pagpunta sa Harvard,
Jale, o Bilangguan - alam mo, sa Bilangguan, New Jersey.
Kaya nakuha ko sa aking sarili ng spell-checker.
Na ang isang maliit na sipi mula sa isa sa aking paboritong pasalitang salita artist, Taylor Mali.
Pa rin, sabi niya, ang kahalagahan ng pagkakaroon ng spell-checker ay napakahalaga.
>> Kaya Malugod sa walkthrough 5, na kung saan kami ay pakikipag-usap tungkol sa pset5: mga maling spelling,
kung saan namin ang aming sariling spell-checker.
Ang toolbox para sa linggong ito, ang code ng pamamahagi, ay mahalaga upang tumingin sa
lamang upang maunawaan ang ibang mga function na ang iyong diksyunaryo ay pagpunta sa may.
Aktwal Kami ay pagpunta sa ay ang pagkakaroon ng maramihang mga. File c na gumawa ng sama-sama ang aming pset.
At kaya hinahanap sa pamamagitan ng iba't ibang aspeto, kahit na aktwal na kami ay hindi nag-e-edit
isa sa mga file, speller.c, alam kung paano ito gumagana na may kaugnayan sa dictionary.c,
na namin ang pagsusulat, ay medyo mahalaga.
Ang pset spec din ay naglalaman ng maraming mga kapaki-pakinabang na impormasyon
sa mga tuntunin ng mga bagay na maaari mong ipagpalagay, mga patakaran at mga bagay tulad na,
kaya siguraduhin na basahin ang spec ng pset mabuti para sa mga tip.
At kapag pagdududa ng isang panuntunan o isang bagay tulad na, pagkatapos ay palaging sumangguni sa spec ang pset
o Talakayin.
Ito ay pagpunta ang pset umasa mabigat sa payo,
kaya gusto naming upang matiyak na naiintindihan namin ang pagkakaiba sa pagitan ng pagdaragdag ng mga bituin
sa harap ng pangalan ng pointer at ampersand, kung paano magbakante ang mga ito, atbp.
Kaya isang master ng mga payo upang maging lubhang kapaki-pakinabang sa set na ito ng problema.
Kami ay pagpunta sa tumingin sa naka-link na listahan ng kaunti pang,
kung saan mayroon kaming ang mga elemento na tinatawag naming node na may parehong halaga pati na rin ang pointer
sa susunod na node, at iba pa mahalagang pag-link iba't ibang mga elemento isa pagkatapos ng isa.
Mayroong ilang iba't ibang mga pagpipilian ng pagpapatupad ng iyong aktwal na diksyunaryo.
Kami ay pagpunta sa tumingin sa dalawang pangunahing pamamaraan, na hash talahanayan at pagkatapos ay sinusubukan.
Sa parehong ng mga sangkot na nila ang ilang uri ng paniwala ng isang naka-link na listahan
kung saan mo elemento na naka-link sa isa't isa.
At sa gayon kami ay pagpunta upang tumingin sa kung paano mo maaaring magagawang upang gumana sa paligid ng mga naka-link na listahan,
likhain ang mga ito, mag-navigate sa mga tuntunin ng kung paano, halimbawa, magpasok ng isang node ito
o libreng lahat ng node pati na rin.
Sa mga tuntunin ng pagbabakante node, na talagang mahalaga
tuwing namin malloc memory, pagkatapos magbakante namin ito.
Kaya gusto namin upang matiyak na ang pointer walang pupunta unfreed, na hindi namin anumang mga paglabas ng memory.
Kami ay pagpunta upang ipakilala ang isang tool na tinatawag na Valgrind na tumatakbo ang iyong programa
at mga tseke kung ang lahat ng memory na iyong inilalaan ay pagkatapos ay napalaya.
Lamang ang iyong pset ay makumpleto kapag ito gumagana at ito ay may ganap na pag-andar,
ngunit din, Valgrind ay nagsasabi sa iyo na hindi mo pa nahanap ang anumang mga paglabas memory.
Panghuli, para sa pset, ko talagang gusto Stress -
Ibig kong sabihin, gaya ng dati, Ako ay talagang isang tagataguyod ng paggamit ng panulat at papel para sa iyong mga set ng problema,
ngunit para sa isa, tingin ko na pen at papel ay lalong mahalaga
kung kailan mo nais na pagguhit ng mga arrow sa mga bagay at pag-unawa kung paano bagay gumagana.
Kaya talagang subukang gamitin ang pen at papel upang gumuhit ng mga bagay bago ka makapag-coding
dahil maaaring makakuha ng bit ng magulo.
>> Una, sabihin pumunta sa naka-link na mga listahan ng kaunti.
Naka-link na listahan ay binubuo ng node, kung saan ang bawat node ay may halaga na nauugnay dito,
pati na rin ang isang pointer sa susunod na node matapos itong.
Ang ilang mga bagay na mahalaga sa mga naka-link na listahan na kailangan namin upang alalahanin
kung saan ang aming unang node, at pagkatapos ay sa sandaling matapos namin alam kung saan ang unang node ay,
na paraan na maaari naming ma-access ang node na ang unang node punto upang
at pagkatapos ay matapos na at ang isa matapos na.
At pagkatapos ay ang huling elemento sa iyong listahan ng naka-link pointer na node
ay palaging pagpunta upang tumuro sa null.
Kapag ang isang puntos ng node sa null, pagkatapos ay alam mo na naabot mo na ang dulo ng listahan,
na node ay ang huling isa, na may walang matapos na.
Dito sa eskematiko na ito, makikita mo na ang mga arrow ay ang mga payo,
at ang mga asul na seksyon na kung saan ang halaga ay naka-imbak,
at pagkatapos ay ang pulang kahon na may ang pointer dito pointer sa node
na tumuturo sa susunod na node matapos itong.
At kaya makikita mo dito, ang D node ay tumuturo sa null sapagkat ito ay ang huling elemento sa listahan.
>> Tingnan natin sa kung paano namin tukuyin ang isang struct para sa isang node.
At dahil gusto naming magkaroon ng maramihang mga node,
ito ay pagpunta sa maging isang typedef struct
kung saan kami ay pagpunta sa magkaroon ng ilang iba't-ibang mga kaso ng node.
At kaya namin tukuyin ang mga ito bilang isang bagong uri ng data.
Dito, mayroon kaming isang typedef struct node.
Sa halimbawang ito, kami ay pagharap sa integer node,
kaya kami ay may isang integer na may pangalang halaga at pagkatapos namin ng isa pang pointer,
at sa kasong ito, ito ay isang pointer sa isang node, kaya kami ay may isang struct node * tinatawag susunod.
At pagkatapos kami ay pagtawag sa buong node bagay na ito.
Tiyakin na sundin mo ang syntax na ito.
Pansinin na node ay aktwal-reference up sa itaas pati na rin sa ibaba ang kulot tirante.
Pagkatapos upang subaybayan kung saan ang aking unang node sa naka-link na listahan,
Mayroon akong isang node pointer na tinatawag na ulo, at ako malloc espasyo sapat para sa laki ng isang node.
Paunawa, gayunpaman, ang ulo na ay talagang isang node pointer bilang kabaligtaran sa isang aktwal na node mismo.
Kaya ulo aktwal na ay hindi naglalaman ng anumang halaga,
POINTS lamang ito sa alinman ang unang node sa aking listahan ng naka-link.
>> Upang makakuha ng isang mas mahusay na pakiramdam ng mga naka-link na listahan, dahil ito ay napakahalaga
subaybayan ng siguraduhin na mapanatili mo ang chain,
Gusto ko sa tingin ng ito ng mga tao sa isang linya na may hawak kamay,
kung saan ang bawat tao ay may hawak kamay sa susunod na.
Hindi mo maaaring makita sa guhit na ito, ngunit isa lamang sila nagtuturo sa susunod na tao
na sa kanilang chain.
At kaya kung gusto mong pagbagtas isang naka-link na listahan kung saan ang mga taong ito -
isipin ang lahat ng mga taong iyon ay may halaga na nauugnay sa kanila
at ituro din sa susunod na tao sa linya -
kung gusto mong pagbagtas sa naka-link na listahan, halimbawa, upang i-edit ang mga halaga
o paghahanap para sa isang halaga o isang bagay tulad na,
makikita mo nais upang magkaroon ng isang pointer sa partikular na tao.
Kaya kami ay pagpunta sa magkaroon ng data uri ng node pointer.
Para sa halimbawang ito, sabihin tumawag ito cursor.
Isa pang karaniwang paraan upang pangalanan ito ay iterator o isang bagay tulad na
dahil ito iterating at aktwal na paglipat kung aling node ito na tumuturo sa.
Dito ay ang aming cursor.
Aming cursor ay unang ituro sa unang elemento sa aming listahan.
At kaya kung ano ang gusto naming gawin ay gusto namin talaga ay magpatuloy ang cursor,
gumagalaw ito mula sa gilid sa gilid.
Sa kasong ito, nais naming upang ilipat ang mga ito sa susunod na elemento sa listahan.
Sa mga array, kung ano ang gusto naming gawin ay gusto lang namin sabihin namin dagdagan ang index ng 1.
Sa kasong ito, kung ano ang kailangan namin upang gawin ang aktwal na mahanap kung saan ang tao ang kasalukuyang tao ay tumuturo sa,
at na na ang susunod na halaga.
Kaya kung cursor lamang node pointer, pagkatapos kung ano ang gusto naming gawin
nais namin upang makakuha ng sa ang halaga na ang cursor ay tumuturo sa.
Gusto naming upang makakuha ng sa node na iyon at pagkatapos, kapag hindi namin na node, hanapin kung saan ito na tumuturo sa.
Upang makapunta sa aktwal na node na ang cursor ay tumuturo sa,
karaniwang ipahiwatig namin ito sa pamamagitan ng (* cursor).
Na ay magbibigay sa iyo ang aktwal na node na cursor ay tumuturo sa.
At pagkatapos ay matapos na, kung ano ang gusto naming gawin ay gusto naming i-access
anumang na ang susunod na halaga ng node ay.
Upang gawin na, upang ma-access ang mga halaga sa loob ng struct, mayroon kaming ang tuldok operator.
Kaya pagkatapos ay ito ay (* cursor). Susunod.
Ngunit ito ay isang bit magulo sa mga tuntunin ng pagkakaroon ng mga bracket sa paligid ng cursor *,
at kaya namin palitan ang buong pahayag na may cursor->.
Ito ay isang gitling at pagkatapos ay mas malaki kaysa sa pag-sign, kaya paggawa ng isang arrow.
cursor-> susunod.
Na ang aktwal na makakuha mo ang node na ang cursor puntos. Na ang halaga ng susunod na.
Kaya sa halip ng pagkakaroon ng star at ang tuldok, ikaw ay pinapalitan na may isang arrow.
Maging maingat upang tiyakin na sinusubukan mong gamitin ang syntax na ito.
>> Ngayon na kami ay may aming cursor, kung gusto naming i-access ang halaga,
bago, nagkaroon kami cursor-> susunod,
ngunit upang ma-access ang halaga sa node na ang cursor ay tumuturo sa, namin lamang lamang sabihin
node-> halaga.
Mula doon, ito ay ng uri ng data anumang tinukoy kami ang mga halaga at ang mga node upang maging.
Kung ito ay isang int node, cursor-> halaga lamang pagpunta sa maging isang integer.
Upang maaari naming gawin ang mga pagpapatakbo sa na, i-check ang equalities, italaga ito ng mga iba't ibang mga halaga, atbp.
Kaya pagkatapos kung ano ang gusto mong gawin kung gusto mong ilipat ang iyong cursor sa susunod na tao,
iyong aktwal na baguhin ang halaga ng cursor.
Dahil ang cursor ay isang node pointer, baguhin mo ang aktwal na address ng pointer
sa address ng susunod na node sa iyong listahan.
Ito ay ilang mga code na kung saan maaari mong umulit.
Kung saan mayroon akong komento sa gawin ang isang bagay,
na kung saan marahil ka upang ma-access ang halaga
o gawin ang isang bagay na gawin sa partikular na node.
Upang simulan-off ito, sinasabi ko na ang aking cursor sa simula
ay upang tumuro sa unang elemento sa naka-link na listahan.
At kaya hanggang magpatuloy, na tinukoy ko ito bilang ang ulo ng node.
>> Tulad ng aking nabanggit bago, pagbabakante ay talagang mahalaga.
Nais mong tiyakin na magbakante bawat elemento sa listahan kapag natapos mo na dito.
Kapag hindi mo na kailangang upang isangguni ang anumang ng mga payo,
nais mong tiyakin na magbakante mo ang lahat ng mga payo.
Ngunit nais mong maging maingat dito sa na nais mong upang maiwasan ang anumang mga paglabas ng memorya.
Kung ang ka ng libreng isang tao maaga, pagkatapos ang lahat ng payo na na node puntos upang
pagpunta sa mawawala.
Pagpunta pabalik sa halimbawa sa tao upang gumawa ito ng kaunti mas mataas na pusta,
sabihin may mga taong ito, maliban sa kasong ito sila ay pagpasada sa isang lawa na may halimaw.
Nais naming tiyakin na tuwing magbakante namin, hindi namin mawala
at bitawan ng anumang node bago aktwal namin ang napalaya sa kanila.
Halimbawa, kung ikaw ay lamang tumawag ng libre sa tao na ito dito,
siya ay napalaya, ngunit pagkatapos ang lahat ng mga guys ay pagkatapos ay mawawala
at gusto nila sumama sa agos off at matumba.
Kaya gusto namin upang matiyak na sa halip, gusto namin upang mapanatili ang isang link sa natitirang.
Aming pointer sa ulo, na mga punto sa unang elemento sa listahan.
Ito ay uri ng tulad ng isang lubid angkora ang unang tao.
Ano ang maaaring gusto mong gawin kapag magbakante listahan ng may -
Kung nais mong magbakante muna sa unang elemento, pagkatapos ay maaari kang magkaroon ng isang pansamantalang pointer
na tumuturo sa anumang sa unang elemento.
Kaya mayroon ka sa iyong pansamantalang pointer pagturo dito.
Sa ganoong paraan, mayroon kaming isang hold ng unang node.
At pagkatapos, dahil alam namin na ang unang node ay pagpunta sa ay napalaya,
pagkatapos ay maaari naming ilipat ang lubid, ang anchor, ang aming ulo,
sa aktwal na tumuturo sa anumang unang na tumuturo sa.
Kaya ang ulo na ito ay aktwal na mga punto sa pangalawang elemento sa ngayon.
Ngayon kami ay pinapayagan upang magbakante anumang ay naka-imbak sa Temp,
at upang maaari naming burahin na hindi ito mapanganib ang lahat ng iba pang mga node sa aming listahan.
Ang isa pang paraan na maaari mong gawin ito ay maaaring
tuwing magbakante lamang ang huling elemento sa listahan
dahil sila ay hindi katiyakan sa tulis sa anumang bagay.
Kaya maaari mong magbakante ito, pagkatapos libreng ang isang ito, ang libreng ang isang ito.
Na talagang gumagana ngunit ng kaunti mas mabagal dahil sa pamamagitan ng likas na katangian ng naka-link na listahan,
hindi lamang namin ay maaaring agad na lumipat sa huling.
Mayroon kaming pagbagtas bawat elemento sa naka-link na listahan
at suriin kung ang isa na ay tumuturo sa null, suriin ang bawat oras na,
at pagkatapos ay sa sandaling matapos namin maabot ang pagtatapos, pagkatapos libreng na.
Kung ikaw ay upang gawin ang prosesong ito, nais mong aktwal na check dito,
check dito, pagkatapos check dito, pagbabakante ito,
pagkatapos balik, check dito, check dito, pagbabakante ito,
check dito, at pagkatapos ay pagbabakante ito.
Na tumatagal ng kaunti pang oras. Oo.
>> [Mag-aaral] Gusto ito ay posible na gumawa ng isang naka-link na listahan na nag-iimbak ng isang exit pointer sa dulo?
Na tiyak na panahon.
Upang ulitin ang tanong, ay posibleng magkaroon ng naka-link na istraktura ng listahan
tulad na mayroon kang isang pointer na tumuturo sa dulo ng naka-link na listahan?
Gusto kong sabihin na posible, at ang bawat oras na magpasok ng isang bagay sa iyong listahan ng naka-link
nais mong i-update ang na pointer at mga bagay tulad na.
Mayroon kang isang node * buntot, halimbawa.
Ngunit kapag ikaw ay pagpapatupad ng ang tampok na ito, mayroon kang mag-isip ng kalakalan-offs,
bang kung gaano karaming beses ako pagpunta sa ay iterating sa paglipas ng ito,
kung paano mahirap ito upang subaybayan ng buntot pati na rin ang ulo
pati na rin ang aking iterator, at mga bagay tulad na.
Sinusuportahan ba na -? >> [Mag-aaral] Oo.
Posible, ngunit sa mga tuntunin ng mga desisyon ng disenyo, mayroon kang sa timbangin ang mga pagpipilian.
>> Narito ang isang balangkas ng code na ay magbibigay-daan sa iyo upang magbakante bawat elemento sa isang naka-link na listahan.
Muli, dahil ako iterating sa loob ng isang naka-link na listahan, ako pagpunta sa nais na magkaroon ng ilang mga uri ng cursor
o iterator.
Namin ay iterating hanggang ang cursor ay null.
Hindi mo nais upang umulit kapag ang iyong cursor ay null
dahil na ay nangangahulugan na walang anuman sa listahan.
Kaya pagkatapos dito gumawa ako ng isang pansamantalang node *
na tumuturo sa kung ano ang isinasaalang-alang ako ay ang unang ng aking listahan,
at pagkatapos ko bang ilipat ang aking cursor magpatuloy 1 at pagkatapos libreng anumang ko nagkaroon sa pansamantalang imbakan.
>> Na namin ngayon sa pagpasok sa naka-link na listahan.
Mayroon akong tatlong node sa aking naka-link na listahan, at sabihin pumunta sa mga simpleng kaso
kung saan nais namin upang magpasok ng isa pang node sa dulo ng aming mga listahan ng naka-link.
Upang gawin na, ang lahat ng gusto naming gawin ay na namin pagbagtas
upang mahanap kung saan ang kasalukuyang dulo ng naka-link na listahan ay, kaya alinmang node ay tumuturo sa Null -
na ang isang ito -
at pagkatapos ay sabihin, aktwal na, ang isang ito ay hindi na ang huling node;
aktwal na kami ay pagpunta sa isa pa.
Kaya gusto namin ito kasalukuyang isang punto sa anumang namin ang pagpasok.
Kaya ngayon ito pulang tao dito naging ang huling node sa naka-link na listahan.
At kaya ang katangian ng huling node sa naka-link na listahan ay na punto upang null.
Kaya pagkatapos ay kung ano ang gusto naming gawin ay itakda ang pointer ito pulang tao sa null. Doon.
>> Ngunit ano kung gusto namin upang magpasok ng isang node in sa pagitan ng pangalawa at pangatlong?
Na ang isa ay hindi lubos na simple dahil gusto naming matiyak na
na hindi namin ipaalam sa pumunta ng anumang node sa aming listahan ng naka-link.
Ano ang gusto naming gawin tiyakin na namin anchor sa ating sarili sa bawat isa.
Halimbawa, sabihin tinatawag ito ang pangalawang.
Kung sinabi mo ang pangalawang ngayon punto upang ang bagong
at mo lamang ginawa ng isang pointer doon, na magreresulta sa tao na ito na nawala
dahil doon ay hindi anumang link sa kanya.
Sa halip - ako gumuhit ito muli. Mawalang ang aking mga artistikong kakayahan.
Alam namin na hindi lamang namin maaaring direktang link 2 sa bagong.
Mayroon kaming upang matiyak na hawakan namin sa huling.
Ano ang maaari naming nais gawin ay magkaroon ng isang pansamantalang pointer
sa elemento na pagpunta sa ikinakabit sa.
Kaya pagkatapos namin magkaroon ng pansamantalang pointer doon.
Dahil alam namin na ang ikatlong isa ay pinananatiling track ng,
2 maaari na ngayong mag-link sa aming bagong isa.
At kung ito bagong pulang tao ay magiging sa pagitan ng 2 at 3,
pagkatapos kung ano ang pointer na tao upang tumuro sa? >> [Mag-aaral] Temp.
Temp. Oo.
Kaya ang susunod na halaga ng ito pulang tao ay pagpunta sa Temp.
Kapag ikaw ay pagpasok sa naka-link na listahan, nakita namin na maaari naming
madaling magdagdag ng isang bagay sa dulo sa pamamagitan ng paglikha ng isang pansamantalang array,
o kung gusto naming upang magdagdag ng isang bagay sa gitna ng aming mga array,
tumagal ng kaunti pang shuffling sa paligid.
Kung nais mong, halimbawa, isang pinagsunod-sunod na naka-link na listahan,
pagkatapos ay mayroon kang uri ng timbangin ang mga gastos at mga benepisyo ng na
dahil kung gusto mong magkaroon ng isang pinagsunod-sunod na array, na nangangahulugan na ang bawat oras mong ipasok ito,
ito ay pagpunta sa tumagal ng kaunti pang oras.
Gayunpaman, kung gusto mong mamaya sa, dahil kakailanganin namin mahanap namin nais na,
paghahanap sa pamamagitan ng isang naka-link na listahan, pagkatapos ay maaari itong maging mas madali kung alam mo na ang lahat ng bagay ay upang.
Kaya baka gusto mong timbangin ang mga gastos at mga benepisyo ng na.
>> Ang isa pang paraan upang ipasok sa isang naka-link na listahan ay upang ipasok sa simula ng isang listahan.
Kung gumuhit namin ang aming anchor dito - ito ay ang aming ulo -
at pagkatapos na ang mga taong ito na naka-link dito,
at pagkatapos kami ay may isang bagong node na ipinasok sa simula,
pagkatapos kung ano ang maaari naming nais gawin?
Ano ang mali na may lamang sinasabi na gusto kong i-link ang pula sa asul,
dahil na ang unang isa?
Kung ano ang mangyayari dito?
Ang lahat ng mga tatlong ay mawawala.
Kaya hindi namin nais upang gawin iyon.
Muli, natutunan namin na kailangan namin upang magkaroon ng ilang mga uri ng pansamantalang pointer.
Natin pumili upang magkaroon ng isang pansamantalang nagtuturo sa tao na ito.
Pagkatapos ay maaari kaming magkaroon ng asul isang punto sa pansamantalang
at pagkatapos ay ang pulang point sa asul.
Ang dahilan kung bakit gumagamit ako ng mga tao dito ay dahil gusto talaga namin upang mailarawan ang
may hawak na sa mga tao at tinitiyak na kami ay may isang link sa kanila
bago namin ipaalam sa pumunta ng isa pang kamay o isang bagay tulad na.
>> Ngayon na kami ay may isang pakiramdam ng mga naka-link na listahan - kung paano maaari naming lumikha ng isang naka-link na listahan
at lumikha ang mga kaayusan para sa na binubuo ng ang kahulugan ng uri para sa isang node
at pagkatapos ay siguraduhin na mayroon kami ng pointer sa ulo ng na naka-link na listahan -
sa sandaling mayroon kaming na at alam namin kung paano pagbagtas sa pamamagitan ng isang array,
ma-access ang iba't ibang mga elemento, alam namin kung paano upang ipasok at alam namin kung paano magbakante ang mga ito,
maaari naming makakuha ng sa mga maling spelling.
Gaya ng dati, mayroon kaming isang seksyon ng mga tanong na makapag ginamit mo sa operating na may mga naka-link na listahan
at iba't-ibang kaayusan tulad ng mga queues at stack.
Pagkatapos ay maaari naming ilipat sa maling spelling.
>> Mga maling pagbabaybay ay may sa code ng pamamahagi ng ilang mga file ng kahalagahan.
Unang napansin namin na mayroon namin ito Makefile dito,
kung saan hindi namin talagang nakatagpo ng bago.
Kung ikaw ay tumingin sa loob ng pset5 folder, gusto mong mapansin na mayroon ka ng isang file na. H,
pagkatapos ay mayroon kang dalawang. file c.
Ano Makefile ito ginagawa ay bago, gusto naming i-type lamang gumawa at pagkatapos ay ang pangalan ng programa
at pagkatapos ay namin makita ang lahat ng mga argumento at flag na nakapasa sa sa tagatala.
Ano ang Makefile ginagawa ay nagbibigay-daan sa amin upang ipunin ang ilang mga file nang sabay-sabay
at pumasa sa flag na gusto namin.
Narito lang namin kung may isang header na file dito.
Pagkatapos namin ang aktwal na may dalawang source file.
Mayroon kaming speller.c at dictionary.c.
Maligayang pagdating sa i-edit ang Makefile kung nais mo.
Pansinin na dito kung nagta-type ka malinis, at pagkatapos ay kung ano ang ginagawa nito ay talagang aalis ng anumang
na ang core.
Kung ikaw Mayroon segmentation fault, talaga kang makakuha ng core dump.
Kaya ito pangit maliit na file ay lilitaw sa iyong direktoryo ng tinatawag na core.
Makikita mo nais na alisin na upang gawin itong linisin.
Ito aalis ng anumang mga file ng exe at o file.
>> Natin tingnan sa dictionary.h.
Ito sabi ni na ito declares-andar ng diksyunaryo.
Mayroon kaming isang maximum na haba para sa anumang salita sa diksyunaryo.
Sinasabi namin na ito ay ang pinakamahabang posibleng salita. Ng haba 45.
Kaya hindi namin ay pagpunta sa anumang mga salita na lumampas na haba.
Narito lang namin ang modelo ng function na.
Hindi namin ang aktwal na pagpapatupad dahil na kung ano ang makikita namin ginagawa para sa pset.
Ngunit ano ito ginagawa ay dahil kami ay pagharap sa mas malaking file dito
at pag-andar sa isang mas malaking scale, ito ay kapaki-pakinabang upang magkaroon ng isang file na. h
sa gayon na ang ibang tao pagbabasa o paggamit ng iyong code ay maaaring maunawaan kung ano ang nangyayari sa.
At maaaring gusto nilang ipatupad sinusubukan kung ginawa mo hash na mga talahanayan o vice versa.
Pagkatapos ay sila sabihin sa aking ng pagkarga function na,
ang aktwal na pagpapatupad ay pagpunta sa-iba, ngunit ang prototype na ito ay hindi magbabago.
Narito namin na suriin, na nagbabalik ng tunay na kung ang isang ibinigay na salita sa diksyunaryo.
Pagkatapos kami ay may load, na isa lamang tumatagal sa isang file ng diksyunaryo
at pagkatapos ay ikinarga ito sa ilang mga istraktura ng data.
Mayroon kaming mga laki, kung saan, kapag tinatawag, nagbabalik ang laki ng iyong diksyunaryo,
kung gaano karaming mga salita ay naka-imbak sa loob nito,
at pagkatapos ay mag-ibis maglapag, na frees ang lahat ng memory na iyong kinuha up
habang paggawa ng iyong diksyunaryo.
>> Natin tingnan sa dictionary.c.
Nakikita namin na ito ay mukhang katulad na katulad sa dictionary.h, maliban ngayon ito lang ay may lahat ng ng mga TODOs sa ito.
At kaya na ang iyong trabaho. Sa paglaon, makikita mo na pagpuno sa speller.c sa lahat ng ang code na ito.
Dictionary.c, kapag nagpatakbo, ay hindi talagang pagpunta sa gawin,
kaya tinitingnan namin patungo speller.c upang makita ang aktwal na pagpapatupad ng spell-checker.
Kahit na hindi ka pagpunta sa pag-edit ng anumang ng ang code na ito,
mahalaga ito upang mabasa, maunawaan kapag tinatawag ay ng pagkarga, kapag ako pagtawag ng tseke,
lamang upang maunawaan, imapa ito, tingnan kung paano gumagana ang ang function.
Nakita namin na ito ay check para sa tamang paggamit.
Mahalaga, kapag ang isang tao na tumatakbo ang speller, ito ay nagpapahiwatig na ito ay opsyonal
para sa kanila upang pumasa sa isang diksyunaryo file dahil mayroong isang default na diksyunaryo file.
At pagkatapos ay mayroon silang upang pumasa sa teksto ng spell-check.
deal rusage sa oras dahil isang bahagi ng ito pset na magpapadala kami makitungo sa ibang pagkakataon
ay hindi lamang sa pagkuha ng isang nagtatrabaho ng paggana ng spell-checker
pero sa totoo ay pagkuha ng ito upang maging mabilis.
At kaya pagkatapos na kung saan rusage ay pagpunta sa darating.
Dito, tingnan namin ang unang tawag sa isa sa aming mga dictionary.c file, na ng pagkarga.
Ng pag-load nagbabalik true o false - totoo sa tagumpay, maling kapag pagkabigo.
Kaya kung diksyunaryo ay hindi na-load nang maayos, pagkatapos speller.c ay magbabalik 1 at mag-quit.
Ngunit kung ito ng pagkarga maayos, pagkatapos ito upang magpatuloy.
Patuloy namin, at nakita namin ang ilang file I / O dito,
kung saan ito ay pagpunta sa pagharap sa pagbubukas ng text file.
Dito, kung ano ang ginagawa ng spell-nagsusuri ang bawat solong salita sa teksto.
Kaya kung ano ang speller.c ay ginagawa dito mismo iterating sa paglipas ng bawat isa sa ang mga salita sa text file
at pagkatapos ay check ito sa diksyunaryo.
Dito, mayroon kaming isang Boolean maling nabaybay na makita kung check nagbabalik totoo o hindi.
Kung ang salita ay aktwal na sa diksyunaryo, pagkatapos ay i-check ang nagbabalik ng tunay na.
Iyon ay nangangahulugang ang salitang iyon ay hindi tamang spelling.
Kaya maling nabaybay ay maling, at na ang dahilan kung bakit mayroon kaming doon ang putok, ang pahiwatig.
Panatilihin namin sa pagpunta, at pagkatapos ay iniingatan nito ang track kung gaano karaming mga maling nabaybay salita
may sa file.
Patuloy ito sa at isinasara ang file.
Pagkatapos dito, nag-uulat ito kung gaano karaming mga maling nabaybay salita na mayroon kang.
Kinakalkula kung gaano karaming oras na ito kinuha load ang diksyunaryo,
kung gaano karaming oras na ito kinuha upang suriin ito,
kung gaano karaming oras na ito kinuha upang makalkula ang laki,
kung saan, bilang ipagpapatuloy namin, dapat ay napakaliit,
at pagkatapos ay kung gaano karaming oras na ito kinuha upang tanggalin sa diksyunaryo.
Dito hanggang sa itaas nakita namin ang tawag sa mag-ibis maglapag dito.
Kung namin suriin para sa laki dito,
pagkatapos naming makita na dito ang tawag sa laki kung saan tumutukoy sa laki ng diksyunaryo.
Kahanga-hanga.
>> Aming gawain para sa pset ipatupad load, na-load ang diksyunaryo
data istraktura - alinman mong piliin, na ito ng hash table o subukan -
may mga salita mula sa diksyunaryo file.
Pagkatapos mayroon kang laki, na ibalik ang bilang ng mga salita sa diksyunaryo.
At kung ikaw ipatupad ng load sa isang smart paraan, pagkatapos laki ay dapat na medyo madali.
Pagkatapos mo na check, na suriin kung ang isang ibinigay na salita sa diksyunaryo.
Kaya speller.c pass sa isang string, at pagkatapos ay mayroon kang upang suriin kung na string
ay nilalaman sa loob ng iyong diksyunaryo.
Pansinin na namin pangkalahatang standard na mga diksyunaryo,
ngunit sa ang pset na ito, isa lamang diksyunaryo anumang ang pumasa sa sa anumang wika.
Kaya hindi lang namin ipinapalagay na ang salitang ANG ay sa loob.
Ang salitang FOOBAR maaaring tinukoy sa isang tiyak na diksyunaryo na pumasa kami.
At pagkatapos namin mag-ibis maglapag, na frees sa diksyunaryo mula sa memorya.
>> Una, gusto kong pumunta sa ibabaw ng hash paraan ng talahanayan
tungkol sa kung paano namin ipatupad ang lahat ng mga apat na function,
at pagkatapos ay kukunin ko na pumunta sa ibabaw ng sinusubukan paraan ng, kung paano namin ipatupad ang mga apat na function,
at sa dulo talk tungkol sa ilang pangkalahatang mga tip kapag nagsasagawa ka sa pset
at din kung paano mo magagamit ang Valgrind mag-check para sa mga paglabas ng memorya.
>> Makakuha natin sa hash paraan ng talahanayan.
Isang hash na talahanayan ay binubuo ng isang listahan ng mga bucket.
Bawat halaga, bawat salita, ay pagpunta sa pumunta sa isa sa mga bucket.
Isang hash talahanayan perpektong pantay-pantay namamahagi ng lahat ng mga halagang ito na kayo ay pagpasa sa
at pagkatapos populates ito sa bucket na bawat bucket
may tungkol sa isang patas na bilang ng mga halaga sa loob nito.
Ang istraktura para sa isang hash table, mayroon kaming isang array ng mga naka-link na listahan.
Ano ang ginagawa namin kapag pumasa kami sa isang halaga, namin suriin kung saan ang halaga na dapat nabibilang,
kung saan bucket ito ay kabilang sa, at pagkatapos ay ilagay ito sa naka-link na listahan na nauugnay sa na bucket.
Dito, kung ano ang mayroon akong ay isang hash.
Ang isang int hash talahanayan.
Kaya para sa unang bucket, anumang integer sa ibaba 10 ay pumunta sa unang bucket.
Anumang integer sa itaas 10 ngunit sa ibaba 20 go sa segundo,
at pagkatapos ay iba pa at iba pa.
Para sa akin, ang bawat bucket ay kumakatawan sa mga numerong ito.
Gayunpaman, sinasabi ko upang pumasa sa 50, halimbawa.
Lumilitaw na kung ang unang tatlong naglalaman ng isang hanay ng mga sampung numero.
Ngunit nais ko upang payagan ang aking hash table upang tumagal sa anumang uri ng integer,
kaya Gusto ko upang i-filter ang lahat ng mga numero sa itaas 30 sa huling bucket.
At kaya pagkatapos na maaaring magresulta sa isang uri ng hindi balanseng hash talahanayan.
Upang mag-ulit, ng hash table ay lamang ng isang hanay ng mga bucket
kung saan ang bawat bucket ay isang naka-link na listahan.
At iba pa upang matukoy kung saan napupunta ang bawat halaga, kung saan bucket ito napupunta sa,
ka pagpunta sa nais kung ano ang tinatawag na hash
na tumatagal ng isang halaga at pagkatapos ay sabi ni Ang halagang ito ay tumutugma sa isang tiyak na bucket.
Kaya sa itaas hanggang sa halimbawang ito, ang aking hash kinuha bawat halaga.
Ito ay naka-check kung ito ay mas mababa sa 10.
Kung ito ay, ilagay ang mga ito sa unang bucket.
Sumusuri kung ito ay mas mababa sa 20, Binibigyan ito sa ang pangalawang kung totoo,
tseke kung ito ay mas mababa sa 30, at pagkatapos ay Binibigyan ito sa sa ikatlong bucket,
at pagkatapos ang lahat ng ibang tao na Nabibilang ang ang ika-apat na bucket.
Kaya kapag mayroon kang isang halaga, ang iyong mga hash
maglalagay na halaga sa naaangkop na bucket.
Ang hash talaga kailangang malaman kung gaano karaming mga bucket mayroon kang.
Iyong hash laki ng talahanayan, ang bilang ng mga bucket na mayroon ka,
na pagpunta sa isang nakapirming numero na ay nasa sa iyo, para sa iyo upang magpasya,
ngunit ito ay pagpunta sa isang nakapirming numero.
Kaya iyong hash ay umasa sa na upang matukoy kung saan bucket key tuwing pupunta sa
tulad na pantay-pantay ito ay ibinahagi sa.
Katulad sa aming pagpapatupad ng mga naka-link na listahan, ngayon ang bawat node sa hash table
ay aktwal na pagpunta sa magkaroon ng isang uri ng pansamantalang trabaho.
Kaya mayroon kaming magpasinda array na tinatawag na salita at pagkatapos ng isa pang pointer sa susunod na node,
na saysay dahil ito pagpunta sa isang naka-link na listahan.
Tandaan kapag kami ay naka-link listahan, ginawa ko ang isang node * na tinatawag na ulo
na nagtuturo sa unang node sa naka-link na listahan.
Ngunit para sa aming hash talahanayan, dahil mayroon kaming maraming naka-link listahan,
kung ano ang gusto namin ay gusto naming ang aming hash table upang maging tulad ng, "Ano ang isang bucket?"
Bucket ay isang listahan ng mga node payo,
at sa gayon ang bawat elemento sa bucket ay aktwal na nagtuturo sa kaukulang naka-link na listahan.
Upang bumalik sa eskematiko, makikita mo na ang bucket mismo ang mga arrow,
hindi aktwal na node.
Isa mahahalagang ari-arian ng hash function ay na hindi sila deterministic.
Iyon ay nangangahulugan na tuwing nag-hash ang bilang 2,
dapat itong palaging bumalik sa parehong bucket.
Bawat solong halaga na napupunta sa hash, kung paulit-ulit,
ay may upang makuha ang parehong index.
Kaya ang iyong hash nagbabalik ang index ng array
kung saan ang halaga na nabibilang.
Tulad ng aking nabanggit bago, ang numero ng mga bucket ay maayos,
at sa gayon ang iyong index na bumalik ka na mas mababa kaysa sa numero ng mga bucket
ngunit mas malaki kaysa sa 0.
Ang dahilan kung bakit mayroon kaming hash function sa halip na isa lamang sa iisang naka-link na listahan
o isang single array ay na gusto naming upang lumipat sa isang tiyak na seksyon pinaka madaling
kung alam namin ang mga katangian ng isang halaga -
sa halip ng pagkakaroon upang maghanap sa pamamagitan ng buong buong diksyunaryo,
upang lumipat sa isang tiyak na seksyon ng.
Iyong hash ay dapat isinasaalang-alang na may perpektong,
bucket ang bawat isa ay humigit-kumulang ang parehong bilang ng mga susi.
Dahil ang hash talahanayan ay isang serye ng mga naka-link na listahan,
pagkatapos ang mga naka-link na listahan ang kanilang mga sarili upang magkaroon ng higit sa isang node.
Sa nakaraang halimbawa, ang dalawang magkaibang mga numero, kahit na sila ay hindi katumbas,
kapag hash, ay ibalik ang parehong index.
Kaya kapag ikaw ay pagharap sa mga salita, isang salita kapag hash
ay ang parehong halaga ng hash ng isa pang salita.
Iyon ay kung ano ang tinatawag naming isang banggaan, kapag mayroon kaming isang node na, kapag hash,
ang naka-link na listahan sa bucket na ay hindi walang laman.
Ang diskarteng na tinatawag naming may linear probing,
kung saan ka pumunta sa naka-link na listahan at pagkatapos ay hanapin kung saan mo gustong ipasok na node
dahil mayroon kang isang banggaan.
Maaari mong makita na may maaaring ng trade-off dito, i-right?
Kung mayroon kang isang napakaliit na hash table, isang maliit na bilang ng mga bucket,
ka pagpunta sa magkaroon ng maraming mga banggaan.
Ngunit pagkatapos ay kung gumawa ka ng isang napakalaking hash talahanayan,
marahil ka upang i-minimize ang mga banggaan,
ngunit ito ay pagpunta sa isang napakalaking istraktura ng data.
May pagpunta sa kalakalan-offs na iyon.
Kaya kapag nagsasagawa ka ng iyong pset, subukan upang i-play sa paligid
sa pagitan ng maaaring paggawa ng isang mas maliit na hash talahanayan
ngunit pagkatapos ay alam na ito bit na pagbagtas sa iba't ibang mga elemento
ng mga naka-link na listahan.
>> Ano ng pagkarga ay pagpunta sa gawin ay umulit sa paglipas ng bawat salita sa diksyunaryo.
Pass sa isang pointer sa file ng diksyunaryo.
Kaya ka pagpunta sa samantalahin ng file I / O function na pinagkadalubhasaan mo sa pset4
at umulit sa paglipas ng bawat salita sa diksyunaryo.
Gusto mong bawat salita sa diksyunaryo upang maging isang bagong node,
at ikaw ay pagpunta sa ilagay ang bawat isa sa mga node sa loob ng iyong istraktura ng data ng diksyunaryo.
Sa tuwing makakakuha ka ng isang bagong salita, alam mo na ito ay pagpunta sa maging isang node.
Sa gayon ay maaari kang pumunta kagayat at malloc isang node pointer para sa bawat bagong salita na mayroon kang.
Narito ako pagtawag sa aking node pointer new_node at ako mallocing kung ano? Ang laki ng isang node.
Pagkatapos basahin ang aktwal na string mula sa isang file, dahil ang diksyunaryo ay aktwal na naka-imbak
sa pamamagitan ng isang salita at pagkatapos ng isang bagong linya, kung ano ang maaari naming samantalahin
ay-andar ng fscanf,
kung saan ang file ay sa diksyunaryo file na kami ay nakapasa sa,
kaya scan ng kahera ang file para sa isang string at mga lugar na string sa huling argumento.
Kung manariwa sa diwa mo sa isa sa mga aralin, kapag nagpunta kami sa paglipas ng
at uri ng peeled ang mga layer sa library CS50,
nakita natin ang isang pagpapatupad ng fscanf doon.
Upang bumalik sa fscanf, mayroon kaming ang file na kami ay binabasa mula sa,
kaming naghahanap para sa isang string sa file na iyon, at pagkatapos ay namin ang paglalagay nito sa
dito mayroon akong new_node-> salita dahil new_node ay isang node pointer,
hindi isang aktwal na node.
Kaya ako sinasabi new_node, gusto kong pumunta sa node na ito na tumuturo sa
at pagkatapos ay italaga na halaga sa salita.
Gusto naming pagkatapos na salita at ipasok ito sa hash table.
Napagtanto na aming ginawa new_node node pointer
dahil kami ay pagpunta sa gusto mong malaman kung ano ang address ng node na
kapag namin ipasok ito sa dahil ang istraktura ng node mismo, ng struct,
na mayroon silang isang pointer sa isang bagong node.
Kaya pagkatapos ay kung ano ang address ng na node pagpunta upang tumuro sa?
Address na iyon ay pagpunta sa new_node.
Ba na may kabuluhan, bakit ginagawa namin new_node node * bilang laban sa isang node?
Okay.
Mayroon kaming isang salita. Ang halaga na iyon ay new_node-> salita.
Na naglalaman ng salita mula sa diksyunaryo na gusto naming input.
Kaya kung ano ang gusto naming gawin ay gusto naming tawagan ang aming hash na string
dahil ang aming hash tumatagal sa isang string at pagkatapos ay bumalik sa amin ng isang integer,
kung saan ang integer na ang index kung saan hashtable sa index na kumakatawan na bucket.
Gusto naming na-index at pagkatapos ay pumunta na index ng hash table
at pagkatapos ay gamitin na nag-link na listahan upang ipasok ang node sa new_node.
Tandaan na gayunpaman magpasya sa iyo upang ipasok ang iyong node,
maging ito man ay sa gitna kung nais mong upang pag-uri-uriin ang mga ito
o sa simula o sa katapusan, tiyakin lamang na ang iyong huling node laging punto upang null
dahil iyon ang tanging paraan na alam namin kung saan ang huling elemento ng aming mga listahan ng naka-link.
>> Kung ang laki ay isang integer na kumakatawan sa bilang ng mga salita sa diksyunaryo,
pagkatapos ay isang paraan upang gawin ito ay tuwing laki ay tinatawag na
pumunta kami sa pamamagitan ng bawat elemento sa aming hash talahanayan
at pagkatapos ay umulit sa pamamagitan ng bawat naka-link na listahan sa loob ng hash table
at pagkatapos ay kalkulahin ang haba ng na, pagtaas ng aming counter 1 ng 1.
Ngunit sa bawat oras na ang laki ay tinatawag na, na pagpunta sa isang mahabang panahon
dahil kami ay pagpunta sa linearly probing ang bawat solong-link listahan.
Sa halip, ito ng maraming mas madali kung patuloy mong pagsubaybay ng kung gaano karaming mga salita ay lumipas.
Kaya pagkatapos kung isinama mo ang isang counter sa loob ng iyong ng pagkarga function na
na update kung kinakailangan, pagkatapos ay counter, kung itinakda mo ito sa isang global variable,
ay magagawang ma-access sa pamamagitan ng laki.
Kaya kung ano ang laki ay maaaring lamang gawin ay sa isang linya, ibalik ang counter halaga,
ang laki ng diksyunaryo, kung saan ikaw ay Aaksyunan sa ng pagkarga.
Na kung ano ang ko nilalayong kapag sinabi ko kung ipatupad mo ng load sa isang kapaki-pakinabang na paraan,
pagkatapos ay ang laki ay medyo madali.
>> Kaya ngayon namin upang suriin.
Ngayon kami ay pagharap sa mga salita mula sa file ng input ng teksto,
at sa gayon kami ay pagpunta sa ma-check kung ang lahat ng mga salita ng input
ay talagang sa diksyunaryo o hindi.
Katulad sa mang-uayabit, gusto naming upang payagan para sa kawalan ng damdamin ng kaso.
Nais mong tiyakin na ang lahat ng salita nakapasa sa, kahit na nasa magkahalong case,
kapag tinawag gamit ang string Ihambing ang, katumbas.
Ang mga salita sa file ng teksto ng diksyunaryo ay talagang lahat ng maliit na.
Isa pang bagay ay na maaari mong ipagpalagay na ang bawat salita nakapasa sa, bawat string,
pagpunta sa alinman sa alpabetikong o naglalaman apostrophes.
Apostrophes wastong salita sa aming diksyunaryo.
Kaya kung mayroon kang isang salita na may kudlit S, na isang aktwal na lehitimong salita sa iyong diksyunaryo
na pagpunta sa isa sa mga node sa iyong hash talahanayan.
Suriin ay nagpapatakbo ng kung umiiral ang salita, pagkatapos ito ay nakuha sa aming hash talahanayan.
Kung ang salita sa diksyunaryo, pagkatapos ang lahat ng mga salita sa diksyunaryo sa hash table,
kaya tingnan natin para sa salita sa hash table.
Alam namin na mula noong ipinatupad namin ang aming hash
tulad ang bawat natatanging salita ay palaging hash sa parehong halaga,
pagkatapos ay alam namin na sa halip ng paghahanap sa pamamagitan ng aming buong buong hash talahanayan,
maaari naming aktwal na mahanap ang naka-link na listahan na salita na dapat kabilang sa.
Kung ito ay sa diksyunaryo, pagkatapos ay sa bucket na.
Ano ang maaari naming gawin, kung ang salita ay ang pangalan ng aming mga string na nakapasa sa,
maaari lang namin hash na ang salita at hitsura sa naka-link na listahan
sa ang halaga ng hashtable [hash (salita)].
Mula doon, kung ano ang maaari naming gawin ay kami ay may isang mas maliit na subset ng mga node upang maghanap para sa salita,
at sa gayon ay maaari naming pagbagtas sa naka-link na listahan, gamit ang isang halimbawa mula sa mas maaga sa walkthrough,
at pagkatapos ay tumawag ng string ihambing sa mga salita saanman ang cursor ay tumuturo sa,
na salita, at makita kung ang mga ihambing.
Depende sa paraan na kang ayusin ang iyong hash,
kung ito ay pinagsunod-sunod, na maaaring magawa upang bumalik maling maaga nang kaunti,
ngunit kung ito ay unsorted, pagkatapos ay nais mong magpatuloy traversing sa pamamagitan ng iyong listahan ng naka-link
hanggang sa mahanap mo ang huling elemento ng listahan.
At kung hindi mo pa rin natagpuan ang salita ng oras na naabot mo na ang dulo ng naka-link na listahan,
na nangangahulugan na ang iyong salita ay hindi umiiral sa diksyunaryo,
at kaya ang salita na ay hindi wasto,
at check dapat bumalik false.
>> Ngayon dumating namin upang mag-ibis maglapag, kung saan nais namin upang magbakante ang lahat ng node na namin malloc'd,
kaya libreng lahat ng node sa loob ng aming hash talahanayan.
Kami ay pagpunta sa nais upang umulit sa lahat ng naka-link na listahan at libreng lahat ng node sa na.
Kung tumingin ka sa itaas sa walkthrough sa halimbawa kung saan magbakante kami ng isang naka-link na listahan,
gugustuhin mong ulitin ang prosesong iyon para sa bawat elemento sa hash table.
At makikita ko pumunta sa paglipas ng ito patungo sa dulo ng walkthrough,
ngunit Valgrind ay isang tool na kung saan maaari mong makita kung maayos mo na napalaya
bawat node na iyong malloc'd o anumang bagay na iyong malloc'd, anumang iba pang pointer.
Kaya na ang hash table, kung saan mayroon kaming isang tiyak na numero ng mga bucket
at ng hash na halaga at pagkatapos ay italaga na halaga sa isang tiyak na bucket.
>> Na namin ngayon sa mga pagsusubok na.
Sinusubukan ng uri ng hitsura tulad nito, at ko rin gumuhit ang isang halimbawa.
Talaga, mayroon kang isang buong array ng mga potensyal na mga titik,
at pagkatapos ay tuwing ka bumuo ng isang salita,
sulat na naka-link para sa isang diksyunaryo sa isang malawak na hanay ng mga posibilidad.
Simulan ang ilan sa mga salita sa C ngunit pagkatapos ay magpatuloy sa A,
ngunit iba patuloy sa O, halimbawa.
Trie ay isang paraan ng pagtingin ng lahat ng posibleng mga kumbinasyon ng mga salitang iyon.
Trie ay upang masubaybayan ang pagkakasunud-sunod ng mga titik na bumubuo ng mga salita,
sumasanga off kapag kinakailangan, kapag ang isang titik ay maaaring sinundan sa pamamagitan ng maramihang mga ng mga titik,
at sa dulo ay nagpapahiwatig sa bawat punto kung wasto o hindi ang salita na
dahil kung ikaw ay pagbaybay ng salita Mat, MA palagay ko ay hindi isang wastong salita, ngunit Mat ay.
At iba pa sa iyong trie, ito ay magdudulot ng magpahiwatig na pagkatapos Mat na talagang isang wastong salita.
Ang bawat node sa aming trie talagang pagpunta upang maglaman ng isang hanay ng mga node payo,
at kami ay pagpunta sa may, partikular, 27 ng mga node na payo,
isa para sa bawat titik sa alpabeto pati na rin ang mga kudlit character.
Bawat elemento sa array na mismo upang ituro sa ibang node.
Kaya kung ang node na ay null, kung may walang matapos iyon,
alam namin na walang karagdagang titik sa na pagkakasunud-sunod ng salita.
Ngunit kung ang node na ay hindi null, na nangangahulugan na may higit pang mga titik sa na pagkakasunud-sunod ng titik.
At pagkatapos ay tangi sa roon, ang bawat node ay nagpapahiwatig ito man ang huling character ng isang salita o hindi.
>> Natin pumunta sa isang halimbawa ng isang trie.
Una mayroon akong room para sa 27 node sa array.
Kung mayroon ko ang salitang Bar -
Kung mayroon ko ang salitang bar at gusto ko upang ipasok na sa,
ang unang titik ay B, kaya kung walang laman ang aking trie ay,
B ay ang ikalawang titik ng alpabeto, kaya ako pagpunta upang piliin upang ilagay ito dito sa index na ito.
Ako pagpunta sa may B dito.
B ay pagpunta sa isang node na mga punto sa isa pang hanay ng lahat ng posibleng mga character
na maaaring sundin pagkatapos ng sulat ng B.
Sa kasong ito, ako pagharap sa bar ng salita, kaya ay pupunta dito.
Pagkatapos A, mayroon akong ang sulat R, kaya pagkatapos ngayon puntos sa sarili nitong kumbinasyon,
at pagkatapos R ay dito.
Bar ay isang kumpletong salita, kaya pagkatapos ako na magkaroon ng ng R punto sa isa pang node
na sinasabi na ang salitang iyon ay wastong.
Na node ay din pagpunta sa magkaroon ng isang hanay ng mga node,
ngunit ang mga maaaring maging null.
Ngunit isa lamang, maaari itong magpatuloy tulad na.
Iyon ay magiging isang bit mas malinaw kapag pumunta kami sa isang iba't ibang mga halimbawa,
kaya lang makisama sa akin doon.
Ngayon kami ay may bar sa loob ng aming diksyunaryo.
Ngayon sinasabi namin ang salitang BAZ.
Sisimulan namin sa B, at kami ay mayroon B bilang isa sa mga titik na sa aming diksyunaryo.
Na sinusundan may A. Mayroon kaming A na.
Ngunit sa halip, mayroon kaming Z sumusunod.
Kaya ang isang elemento sa aming array ay pagpunta sa Z,
at kaya pagkatapos na ang isa ay upang tumuro sa isa pang wastong dulo ng salita.
Kaya nakita namin na kapag patuloy naming sa pamamagitan ng B at pagkatapos A,
mayroong dalawang iba't ibang mga pagpipilian na kasalukuyang nasa aming diksyunaryo para sa mga salita na nagsisimula sa B at A.
Sabihin nating gusto naming ipasok ang salita FOOBAR.
Pagkatapos naming gumawa ng isang entry sa F.
F ay isang node na mga punto sa isang buong array.
Gusto namin mahanap ang O, pumunta sa O, O pagkatapos ay naka-link sa isang buong listahan.
Gusto namin magkaroon ng B at pagkatapos ay magpatuloy, nais naming magkaroon ng A at pagkatapos R.
Kaya pagkatapos FOOBAR traverses ang lahat ng mga paraan pababa hanggang FOOBAR ay isang tamang salita.
At kaya pagkatapos na ito ay isang wastong salita.
Ngayon sinasabi aming susunod na salita sa diksyunaryo ay talagang ang salitang FOO.
Gusto namin sabihin F. Ano sumusunod F?
Ako aktwal na magkaroon ng espasyo para sa O, kaya ako pagpunta upang magpatuloy.
Hindi ko kailangan upang gumawa ng bagong. Magpatuloy.
FOO isang wastong salita sa diksyunaryo, kaya ako pagpunta upang isaad
na na wasto.
Kung ko bang itigil ang aking pagkakasunud-sunod doon, na tama.
Ngunit kung patuloy namin ang aming pagkakasunud-sunod mula FOO down sa B
at nagkaroon FOOB, FOOB ay hindi isang salita, at hindi na ipinahiwatig bilang isang balidong.
Trie, na iyong node bawat nagpapahiwatig kung ito ay isang wastong salita o hindi,
at pagkatapos node bawat ay mayroon ding isang array ng 27 na node payo
na pagkatapos ay tumuturo sa node kanilang sarili.
>> Narito ang isang paraan kung paano mo nais na tukuyin ito.
Gayunpaman, tulad sa hash Halimbawa ng talahanayan, kung saan nagkaroon kami ng node ulo *
upang ipahiwatig ang simula ng aming mga listahan ng naka-link, din kami ay pagpunta sa gusto
ilang mga paraan ng pag-alam kung saan ang simula ng aming trie.
Ang ilang mga tao tawag ay sinusubukan ng mga puno, at na kung saan ugat ay mula.
Kaya gusto namin ang root ng aming puno upang matiyak na manatili namin grawnded
saanman ay ang aming trie.
Namin na uri ng nagpunta sa paglipas ng
ang paraan maaari mong isipin ang tungkol sa paglo-load ng bawat salita sa diksyunaryo.
Mahalaga, para sa bawat salita ka pagpunta sa nais upang umulit sa pamamagitan ng iyong trie
at alam na ang bawat elemento sa mga bata - tinatawag namin itong bata sa kasong ito -
tumutugon sa ibang sulat, ikaw ay pagpunta sa gusto mong tingnan ang mga halagang iyon
sa partikular na index na tumutugma sa sulat.
Kaya iniisip ang lahat ng mga paraan pabalik sa Caesar at Vigenere,
alam na ang bawat titik na maaari mong uri ng mapa sa isang alpabetikong index,
talagang A sa pamamagitan ng Z ay medyo madali upang i-map sa isang alpabetikong sulat,
ngunit sa kasamaang palad, apostrophes din ang isang tanggap na character sa mga salita.
Hindi ako kahit sigurado kung ano ang ASCII halaga ay,
ito para sa kung gusto mong mahanap ang isang index upang magpasya kung nais mong ito sa alinman ang unang
o ang huling isa, makikita mo upang gumawa ng isang hard code na tseke para sa
at pagkatapos ay ilagay na sa index 26, halimbawa.
Kaya ikaw ay check ang halaga sa mga bata [i]
kung saan ang [i] ay tumutugon sa anumang sulat ikaw ay nasa.
Kung na null, na nangangahulugan na may kasalukuyang hindi anumang posibleng mga titik
stemming mula sa nakaraang sequence, kaya ka pagpunta sa gusto sa malloc
at gumawa ng isang bagong node at na ang mga bata [i] tumuturo dito
sa gayon ay lumikha ka ng - kapag ipinasok namin ng sulat sa parihaba -
paggawa ng mga bata na di-null at punto sa node na bagong.
Ngunit kung iyon ay hindi null, gusto sa aming halimbawa ng FOO
kapag namin na nagkaroon FOOBAR, patuloy namin,
at hindi namin kailanman paggawa ng isang bagong node ngunit lamang sa halip ng pagtatakda ng is_word sa true
sa dulo ng salitang iyon.
>> Kaya pagkatapos tulad ng dati, dahil dito ka pagharap sa bawat titik sa isang pagkakataon,
ito upang maging mas madali para sa iyo para sa laki, sa halip ng pagkakaroon upang makalkula
at pumunta sa pamamagitan ng buong puno at kalkulahin kung gaano karaming mga bata ay mayroon akong
at pagkatapos ay sumasanga off, na-alala kung gaano karaming sa kaliwang bahagi at sa kanang bahagi
at mga bagay tulad na, ito ng maraming mas madali para sa iyo
kung ikaw subaybayan kung gaano karaming mga salita nagdaragdag ka sa
kapag ikaw ay pagharap sa ng pagkarga.
At kaya pagkatapos na paraan laki lang ibalik isang pandaigdigang variable ng laki.
>> Ngayon dumating namin upang suriin.
Parehong mga pamantayan tulad ng dati, kung saan nais namin upang payagan para sa kawalan ng damdamin ng kaso.
Pati na rin, ipinapalagay namin na ang mga string lamang alpabetikong character o ang mga apostrophes
dahil ang bata ay isang hanay ng mga 27 ang haba,
sa gayon ang lahat ng mga titik ng alpabeto kasama ang kudlit.
Para tingnan kung ano ang gusto mong gawin ay makikita mo nais na magsimula sa root
dahil ang root ng magtuturo sa isang array na naglalaman
lahat ng mga posibleng nagsisimula sa mga titik ng isang salita.
Ka pagpunta upang simulan doon,
at pagkatapos ka upang suriin ang halaga null o hindi,
dahil kung ang halaga ay null, na nangangahulugan na diksyunaryo ay hindi magkaroon ng anumang mga halaga
na naglalaman na titik sa partikular na pagkakasunud-sunod.
Kung ito ay null, pagkatapos na nangangahulugan na ang salita ay maling kaagad.
Ngunit kung ito ay hindi null, maaari kang magpatuloy,
sabihin na ang unang titik ay isang posibleng unang letra sa isang salita,
kaya ngayon gusto ko upang suriin kung ang pangalawang sulat, na pagkakasunud-sunod, sa loob ng aking diksyunaryo.
Kaya ka pumunta sa index ng mga bata ng unang node
at suriin kung umiiral na pangalawang sulat.
Pagkatapos mong ulitin na proseso upang suriin kung ang pagkakasunod-sunod na ay wasto o hindi
sa loob ng iyong trie.
Tuwing ang node bata sa na puntos ng index sa null,
alam mo na ang pagkakasunod-sunod na hindi umiiral,
ngunit pagkatapos kung naabot mo na ang dulo ng mga salita na iyong inputted,
gusto mong mag-check ngayon Nakumpleto ko na ang pagkakasunod-sunod na ito
at natagpuan ito sa loob ng aking trie, ang salitang iyon wasto o hindi?
At kaya pagkatapos na nais mong upang suriin na, at na kapag kung natagpuan na pagkakasunod-sunod,
nais mong upang suriin kung wasto o hindi ang salita na
dahil tandaan bumalik sa nakaraang kaso na iginuhit ko kung saan nagkaroon kami FOOB,
na isang wastong pagkakasunud-sunod na nakita namin ngunit ay hindi isang aktwal na wastong salita mismo.
>> Gayundin, para sa mga mag-ibis maglapag sa pagsusubok na gusto mong mag-ibis maglapag ang lahat ng node sa iyong trie.
Sorry. Katulad sa ang hash na mga talahanayan kung saan sa mag-ibis maglapag namin napalaya ang lahat ng mga node,
sa pagsusubok na gusto naming din magbakante lahat ng node.
Mag-ibis maglapag ang talagang gumagana ang pinakamadaling mula sa ibaba sa itaas
dahil ito ay mahalagang-link listahan.
Kaya gusto namin upang matiyak na hawakan namin sa lahat ng mga halaga
at libreng lahat ng mga ito tahasang.
Kung ano ang iyong pagpunta sa nais na gawin kung nagtatrabaho ka na may trie
maglakbay sa ibaba at libre ang posibleng pinakamababang node unang
at pagkatapos ay pumunta sa lahat ng mga bata at pagkatapos ay libre sa lahat ng mga,
pumunta up at pagkatapos ay libre, atbp.
Uri ng tulad ng pagharap sa ibabang layer ng trie unang
at pagkatapos ay pagpunta up itaas sa sandaling napalaya ang lahat.
Ito ay isang mahusay na halimbawa ng kung saan ang recursive function na ay maaaring dumating sa madaling-gamiting.
Sa sandaling na-napalaya ang layer sa ilalim ng iyong trie,
pagkatapos ay tumawag kang tanggalin sa natitirang,
bang na magbakante bawat mini -
Maaari mong uri ng maisalarawan ito bilang mini sinusubukan ng.
Kaya iyong root dito.
Ako Pinasisimple ito kaya hindi ko upang gumuhit ng 26 sa kanila.
Kaya mayroon kang mga ito, at pagkatapos ay ito kumakatawan pagkakasunud-sunod ng mga salita
kung saan ang lahat ng mga maliit na lupon ang mga titik na wastong pagkakasunud-sunod ng mga titik.
Natin magpatuloy lamang ng kaunti pang.
Kung ano ang iyong pagpunta sa nais na gawin ang libreng ibaba dito at pagkatapos ay libre ang isang ito
at pagkatapos libreng ito isa sa ibaba bago magbakante sa tuktok hanggang dito
dahil kung ikaw ay libreng isang bagay sa ikalawang antas dito,
iyong aktwal na mawala ang halagang ito dito.
Iyon ang dahilan kung bakit ito ay mahalaga sa mag-ibis maglapag para sa isang trie upang matiyak na magbakante mo sa ibaba sa unang.
Ano ang maaari mong nais na gawin ay sabihin para sa bawat node
Gusto kong mag-ibis maglapag ang lahat ng mga bata.
>> Ngayon na kami nawala sa mag-ibis maglapag para sa hash paraan ng talahanayan pati na rin ang trie paraan ng,
kami ay pagpunta sa gusto upang tumingin sa Valgrind.
Valgrind mong tumakbo gamit ang mga sumusunod na utos.
Mayroon kang valgrind-v.
Sinusuri para sa lahat ng paglabas kapag nagpatakbo ka speller na ibinigay na ang ilang teksto na ito
dahil speller ay kailangang gawin sa isang text file.
Kaya Valgrind tatakbo iyong programa, sabihin sa iyo kung gaano karaming mga byte inilaan mo,
kung gaano karaming mga byte napalaya mo, at ito ay magsasabi sa iyo kung napalaya mo lang sapat na
o kung hindi libreng sapat,
o minsan kahit over-free, tulad ng libreng isang node na na-napalaya
at sa gayon ito ay bumalik ka ng mga error.
Kung gumagamit ka ng Valgrind, ito ay magbibigay sa iyo ng ilang mga mensahe
nagpapahiwatig kung napalaya mo ang alinman sa mas mababa kaysa sa sapat, lang sapat,
o higit pa kaysa sa sapat na beses.
>> Isang bahagi ng ito pset, opsyonal hamunin ang Big Board.
Ngunit kapag kami ay pagharap sa mga istraktura ng data na ito
uri ng masaya upang makita kung gaano kabilis at kung paano mahusay na ang iyong data ng istraktura ay maaaring.
Gumagana ba ang iyong hash resulta sa maraming ng banggaan?
O ang iyong data sa laki talagang malaking?
Aabutin ng maraming oras pagbagtas?
Sa log ng speller, output kung gaano karaming oras na gamitin mo upang i-load,
upang suriin, upang magsagawa ng laki, at mag-ibis maglapag,
at kaya ang mga ay nai-post sa Ang Big Board,
kung saan maaari kang makipagkumpetensya laban sa iyong mga kaklase
at ilang mga miyembro ng kawani upang makita kung sino ay ang pinakamabilis na spell-checker.
Ang isang bagay na Gusto ko upang tandaan tungkol sa hash na mga talahanayan
na mayroong ilang mga medyo simpleng hash function na maaaring sa tingin namin ng.
Halimbawa, mayroon kang 26 bucket, at kaya bawat bucket
tumutugon sa ang unang titik sa isang salita,
ngunit na magresulta sa medyo hindi balanseng hash talahanayan
dahil may mga ng maraming ng mas kaunting mga salita na nagsisimula sa X kaysa sa panimula sa M, halimbawa.
Ang isang paraan upang pumunta tungkol sa speller kung nais mong makakuha ng lahat ng iba pang mga pag-andar pababa,
pagkatapos lamang gamitin ang isang simpleng hash upang makuha ang iyong code sa pagtakbo
at pagkatapos ay bumalik at baguhin ang laki ng iyong hash table at ang kahulugan.
May ng maraming mga mapagkukunan sa Internet para sa hash function,
at ito para sa pset ka pinapayagang upang saliksikin ang mga hash function sa Internet
para sa ilang mga pahiwatig at inspirasyon hangga't gumawa ka bang banggitin kung saan mo nakuha ito mula sa.
Maaari kang upang tingnan at bigyang-kahulugan ang ilang hash na mahanap ka sa Internet.
Bumalik sa na, maaari mong upang makita kung may isang taong gumamit ng isang trie
kung ang kanilang pagpapatupad ay mas mabilis kaysa sa iyong hash talahanayan o hindi.
Maaari kang magsumite sa Ang Big Board maraming beses.
Ito ay record ang iyong pinaka-kamakailang mga entry.
Kaya maaaring mong baguhin ang iyong hash at pagkatapos ay mapagtanto na ito ay talagang ng maraming mas mabilis
o ng maraming mas mabagal kaysa dati.
Na ang isang bit ng isang paraan ng masaya.
Mayroon laging 1 o 2 mga miyembro ng kawani na subukan ang pinakamabagal na posibleng diksyunaryo,
kaya na palaging masaya upang tumingin sa.
>> Ang paggamit para sa pset kang magpatakbo ng speller sa isang opsyonal na diksyunaryo
at pagkatapos ng ipinag-uutos na file ng teksto.
Sa pamamagitan ng default kapag nagpatakbo ka speller sa pamamagitan lamang ng isang text file at hindi tukuyin ang isang diksyunaryo,
ito upang gamitin ang diksyunaryo file ng teksto, malaking
sa folder ng mga cs50/pset5/dictionaries.
Na may higit sa 100,000 salita.
Mayroon ding isang maliit na diksyunaryo na lubha mas salita
na CS50 ay ginawa para sa iyo.
Gayunpaman, maaari mong napaka madaling lang gawin ang iyong sariling diksyunaryo
kung gusto mo lang na nagtatrabaho sa mga maliliit na mga halimbawa -
halimbawa, kung nais mong gamitin ang gdb at alam mo ang tiyak na halaga
na nais mo ang iyong hash talahanayan upang i-map sa.
Kaya lamang ka maaaring gumawa ng iyong sariling text file na may bar, BAZ, FOO, at FOOBAR,
gumawa na sa isang file ng teksto, paghiwalayin ang mga bawat isa ay may 1 linya,
at pagkatapos ay gawin ang iyong sariling teksto file na literal ay naglalaman lamang ng mga siguro 1 o 2 salita
kaya na alam mo kung ano mismo ang output dapat.
Ang ilan sa ang mga file ng halimbawang teksto na Ang Big Board na kapag nagpatakbo ka ng hamon ay suriin
Digmaan at Kapayapaan at isang nobelang ng Jane Austen o isang bagay tulad na.
Kaya kapag ikaw ay nagsisimula out, ito ng maraming mas madali upang gumawa ng iyong sariling mga file ng teksto
na naglalaman lamang ng ilang mga salita o maaaring 10
sa gayon ay maaari mong hulaan kung ano ang kalalabasan ay dapat na
at pagkatapos ay suriin ito kumpara na, kaya higit pa ng isang kinokontrol na halimbawa.
At kaya dahil kami ay pagharap sa predicting at pagguhit ng mga bagay sa paligid,
muli gusto ko hinihikayat ka upang gamitin ang pen at papel
dahil talagang ito ay pagpunta upang makatulong sa iyo sa isang ito -
pagguhit ang mga arrow, kung paano ang hash table o kung paano ang iyong trie mukhang,
kapag ikaw ay pagbabakante ng isang bagay na kung saan ang mga arrow ay pumunta sa,
mo na may hawak na sa sapat, huwag mong makita ang anumang mga link mawala
at bumabagsak sa kailaliman ng leaked memory.
Kaya mangyaring, mangyaring subukan upang gumuhit ng mga bagay kahit bago makakuha ng sa iyo sa pagsulat ng code pababa.
Gumuhit ng mga bagay na ang upang maunawaan mo kung paano ang mga bagay ay pagpunta sa trabaho
dahil pagkatapos ko magagarantiya makikita mo tumakbo sa mas muddles pointer doon.
>> Ayos lang.
Gusto kong nais mong ang pinakamahusay na ng luck sa ito pset.
Ito ay marahil ang hardest isa.
Kaya subukang agahan, gumuhit ng mga bagay ang, gumuhit ng mga bagay ang, at good luck.
Ito walkthrough 5.
>> [CS50.TV]