[Powered by Google Translate] [Walkthrough - Problema Set 6] [Zamyla Chan - Harvard University] [Ito ay CS50. - CS50.TV] 

Hello, lahat, at maligayang pagdating sa walkthrough 6: Huff'n papamintugin. Sa Huff'n papamintugin kung ano ang ginagawa namin ay pagpunta sa pagharap sa isang Huffman compressed file at pagkatapos ay puffing ito back up, kaya decompressing ito, upang maaari naming isalin ang mula sa 0s at 1s na ang user ay nagpapadala sa amin at i-convert ito pabalik sa orihinal na teksto. Pset 6 ay medyo cool dahil ka upang makita ang ilan sa mga tool na ginamit mo sa pset 4 at pset 5 at uri ng pagsasama-sama ng mga ito sa 1 medyo kapong baka konsepto kapag dumating ka upang isipin ang tungkol dito. 

Gayundin, arguably, pset 4 at 5 ay ang pinaka-mapaghamong psets na nagkaroon kami upang mag-alok. Kaya mula ngayon, mayroon kaming ito 1 pang pset sa C, at pagkatapos ay matapos na hindi namin sa web programming. Kaya bumati sa inyong sarili para sa pagkuha sa ibabaw ng toughest umbok sa CS50. 

Paglipat sa para Huff'n papamintugin, aming toolbox para sa pset Huffman puno, kaya unawa hindi lamang kung paano binary puno ng trabaho ngunit partikular Huffman puno, kung paano sila ay binuo. At pagkatapos kami ay pagpunta sa magkaroon ng maraming ng pamamahagi code sa pset, at kami na dumating upang makita na aktwal na ilan ng code maaaring hindi namin magagawang ganap na maunawaan pa, at kaya mga ay ang. c file, ngunit ang kanilang mga kasamang. h file ay magbibigay sa amin ng sapat na pang-unawa na kailangan namin kaya na alam namin kung paano ang mga function gumagana o hindi bababa sa kung ano ang kanilang dapat gawin - kanilang mga input at output - kahit na hindi namin alam kung ano ang nangyayari sa itim na kahon o hindi maunawaan kung ano ang nangyayari sa itim na kahon sa loob. At pagkatapos ay sa wakas, gaya ng dati, kami ay pagharap sa bagong istraktura ng data, partikular na mga uri ng node na ituro sa ilang mga bagay, at kaya dito nagkakaroon ng panulat at papel hindi lamang para sa disenyo ng proseso at kapag na sinusubukan mong malaman kung paano dapat gumana ang iyong pset kundi pati na rin sa panahon ng pag-debug. Maaari kang magkaroon ng GDB sa tabi ng iyong panulat at papel habang magdadala sa iyo pababa kung ano ang mga halaga, kung saan ang iyong mga arrow na tumuturo, at mga bagay tulad na. 

Una tingnan natin sa Huffman puno. Huffman puno binary mga puno, nangangahulugan lamang na ang bawat node ay may 2 bata. Sa Huffman puno ay ang katangian na ang pinaka-madalas na halaga ay kinakatawan ng fewest bit. Nakita namin sa mga halimbawa ng panayam ng Morse code, na uri ng mga pinagsama-samang ilang mga titik. Kung ikaw ay sinusubukan upang isalin ang isang A o isang E, halimbawa, ka-translate na madalas, kaya sa halip ng pagkakaroon upang gamitin ang buong hanay ng mga bit inilaan para sa na dati uri ng data, compress ang ito sa mas kaunti, at ang mga titik na kinakatawan mas mababa madalas ay kinakatawan mas mahaba bit dahil maaari mong bayaran na kapag timbangin mo ang mga frequency na lilitaw ang mga titik. Mayroon kaming ang parehong ideya dito sa Huffman puno kung saan kami ay gumagawa ng chain, isang uri ng landas upang makakuha ng sa ilang mga character. At pagkatapos ay ang mga character na may pinaka-dalas pagpunta sa kinakatawan gamit ang fewest bit. 

Ang paraan na ikaw ay makagawa ng isang puno ng Huffman sa pamamagitan ng paglalagay ng lahat ng mga character na lumilitaw sa teksto at pagkalkula ng kanilang dalas, kung gaano kadalas lumilitaw ang mga ito. Ito ay maaaring isang bilang ng kung gaano karaming beses ang mga titik ay lilitaw o marahil ng isang porsyento ng lahat ng mga character kung gaano karaming bawat isa ay lilitaw. At kaya kung ano ang gagawin mo sa sandaling mayroon ka ng lahat ng na nai-map out, titingnan mo para sa 2 pinakamababang frequency at pagkatapos ay sumali sa kanila bilang kapatid kung saan pagkatapos ng magulang na node ay may isang dalas kung saan ay ang kabuuan ng mga 2 bata. At pagkatapos ay sa iyo sa pamamagitan ng convention natin na kaliwang node, sundin mo na sa pamamagitan ng pagsunod sa 0 sangay, at pagkatapos ay ang rightmost node ay 1 branch. Tulad ng nakita natin sa Morse code, ang isang gotcha na kung ikaw ay may lamang pugak at ang pugak ito ay hindi maliwanag. Maaaring alinman sa 1 titik o maaaring ito ay isang pagkakasunod-sunod ng mga 2 titik. At kaya kung ano Huffman puno ginagawa ay dahil sa pamamagitan ng likas na katangian ng ang mga character na o ang aming panghuling mga aktwal na character pagiging ang huling node sa branch - sumangguni namin sa mga bilang dahon - sa pamamagitan ng kabutihan ng na doon ay hindi maaaring maging anumang kalabuan sa mga tuntunin kung saan sulat na sinusubukan mong i-encode gamit ang serye ng mga bit dahil wala saanman sa kahabaan ng mga bit na kumakatawan sa 1 titik nakatagpo ka ng isa pang buong sulat, at doon ay hindi anumang pagkalito doon. Ngunit kami sa halimbawa na iyong guys ay maaaring aktwal na makita na sa halip ng sa amin lamang nagsasabi sa iyo na na totoo. 

Tingnan natin sa isang simpleng halimbawa ng isang puno ng Huffman. Mayroon akong isang string dito na 12 character ang haba. Mayroon akong 4 Bilang, 6 BS, at 2 CS. Aking unang hakbang ay upang mabilang. Kung gaano karaming beses ang A? Ito lumilitaw sa 4 na beses sa string. B lilitaw 6 beses, at C lilitaw 2 beses. Natural, ako pagpunta sa sabihin gumagamit ako ng B madalas, kaya gusto ko upang kumatawan ang B na may fewest bilang ng bits, ang fewest bilang ng 0s at 1s. At pagkatapos din ako pagpunta sa inaasahan C sa nangangailangan ang pinaka-halaga ng 0s at 1s pati na rin. Una kung ano ang ginawa ko dito inilagay ko sa kanila sa pataas na pagkakasunod-sunod sa mga tuntunin ng dalas. Nakikita namin na ang C at A, mga aming 2 pinakamababang frequency. Lumikha kami ng magulang na node, at na ang magulang na node ay hindi magkaroon ng isang sulat na nauugnay dito, ngunit ang ng dalas, kung saan ay ang kabuuan. Kabuuan ay nagiging 2 + 4, na kung saan ay 6. Pagkatapos namin sundin ang kaliwang sangay. Kung kami ay sa node na 6, pagkatapos ay namin sundin 0 upang makakuha ng sa C at pagkatapos ay 1 upang makakuha ng sa A. Kaya ngayon mayroon kaming 2 node. Mayroon kaming ang halaga 6 at pagkatapos namin ay mayroon ding isa pang node ng halagang 6. At kaya mga 2 ay hindi lamang ang 2 pinakamababang kundi pati na rin lamang ang 2 na pakaliwa, kaya namin sumali mga ng ibang magulang, sa kabuuan sa 12. Kaya dito mayroon kaming aming Huffman puno kung saan upang makakuha ng sa B, na lamang bit 1 at pagkatapos ay upang makakuha ng sa A ay mayroon kaming 01 at pagkatapos C nagkakaroon 00. Kaya dito namin makita na talaga namin ay kumakatawan sa mga karakter na may alinman sa 1 o 2 bit kung saan ang B, bilang hinulaang, ay ang hindi bababa sa. At pagkatapos namin inaasahan C sa may ang pinaka, ngunit dahil ito ay isang maliit na puno Huffman, pagkatapos ng A ay kinakatawan ng 2 bit bilang laban sa isang lugar sa gitna. 

Lamang upang pumunta sa paglipas ng isa pang simpleng halimbawa ng Huffman tree, sabihin nating mayroon kang ang string "Hello." Ano ang gusto mong sabihin kung gaano karaming beses ang H lumitaw sa? H isang beses at pagkatapos e lumilitaw isang beses at pagkatapos ay mayroon kaming l lumilitaw dalawang beses at o lumilitaw nang isang beses. At kaya inaasahan namin kung aling mga titik na kinakatawan ng hindi bababa sa bilang ng mga bits? [Mag-aaral] l. >> L. Oo. l ay kanan. Inaasahan namin na l na kinakatawan ng hindi bababa sa bilang ng mga bits dahil l ay ginagamit pinaka sa string "Hello." Ano ako pagpunta sa gawin ngayon ay gumuhit ang mga node na ito. Mayroon akong 1, na H, at pagkatapos ay isa pang 1, na e, at pagkatapos 1, na kung saan ay o - ngayon ako paglalagay ng mga ito upang - at pagkatapos ay 2, na kung saan ay l. Pagkatapos sabihin ko ang paraan na bumuo akong Huffman puno ay upang mahanap ang 2 node na may hindi bababa sa frequency at gumawa ang mga ito ng mga kapatid sa pamamagitan ng paglikha ng isang magulang na node. Narito mayroon namin ang 3 node na may pinakamababang dalas. Ang mga ito ang lahat ng 1. Kaya dito pinili namin kung saan kami ay pagpunta sa link muna. Sabihin nating ko bang piliin ang H at ang e. Ang kabuuan ng 1 + 1 ay 2, ngunit node na ito ay hindi magkaroon ng isang sulat na nauugnay dito. Mayroon lamang hold ang halaga. Ngayon namin tumingin sa susunod na 2 pinakamababang frequency. Na ang 2 at 1. Na maaaring maging alinman ng mga 2, ngunit ako pagpunta sa pumili ng isang ito. Kabuuan ay 3. At pagkatapos ay sa wakas, ako lamang magkaroon ng 2 kaliwa, kaya't pagkatapos na magiging 5. Pagkatapos dito, tulad ng inaasahan, kung ako punan sa pag-encode para sa, 1s ay palaging ang karapatan na sangay at 0s kaliwang. Pagkatapos kami ay may l na kinakatawan ng lang 1 bit at pagkatapos ay ang o sa pamamagitan ng 2 at pagkatapos e ng 2 at pagkatapos ay ang H Nabibilang ang down sa 3 bit. Sa gayon ay maaari kang magpadala ang mensaheng ito "Kumusta" sa halip na aktwal na paggamit ng mga character sa pamamagitan lamang 0s at 1s. Gayunpaman, tandaan na sa ilang mga kaso nagkaroon kami ay gumagana sa aming dalas. Maaaring alinman namin sumali sa H at ang o unang siguro. O pagkatapos mamaya sa kapag kami ay l na kinakatawan ng 2 pati na rin ang sumali kinakatawan ng 2, maaari naming nai-link ang alinman sa isa. 

At kaya kapag nagpadala ka ng 0s at 1s, na aktwal na ay hindi ginagarantiya na ang tatanggap sa ganap na basahin ang iyong mga mensahe karapatan off ang bat dahil maaaring hindi nila alam kung saan ang desisyon na ginawa mo. Kaya kapag kami ay pagharap sa Huffman compression, sa paanuman namin upang sabihin ang tatanggap ng aming mga mensahe kung paano namin nagpasya - Kailangan nila malaman ang ilang mga uri ng karagdagang impormasyon sa karagdagan sa mensahe compressed. Kailangan nila upang maunawaan kung ano ang puno ang aktwal na kamukha, kung paano ginawa namin ang aktwal na mga desisyon. 

Narito lang namin ginagawa ng halimbawa na batay sa aktwal na bilang ng, ngunit minsan maaari mo ring magkaroon ng isang puno ng Huffman batay sa dalas na kung saan lumitaw sa mga titik, at ito ay ang eksaktong parehong proseso. Narito ako pagpapahayag ito sa mga tuntunin ng porsyento o ng isang fraction, at kaya dito ang eksaktong parehong bagay. Nakahanap ako sa 2 pinakamababang, sabihin sa ilang mga ito, sa susunod na 2 pinakamababang, sabihin sa ilang mga ito, hanggang sa mayroon akong isang buong puno. Kahit na maaari naming gawin ito alinman sa paraan, kapag kami ay pagharap sa porsyento, ito ay nangangahulugan na namin ang paghahati ng mga bagay at pagharap sa decimal o sa halip sa kamay kung kami ay iniisip tungkol sa mga data kaayusan ng isang ulo. Ano ang gagawin namin malaman tungkol sa kamay? Ano ang isang karaniwang problema kapag kami ay pagharap sa kamay? [Mag-aaral] Imprecise aritmetika. >> Oo. Imprecision. Dahil lumulutang point imprecision, para sa pset kaya na ginawa namin ba na hindi namin mawawala ang anumang mga halaga, pagkatapos ay aktwal na kami ay pagpunta sa pagharap sa ang bilang. Kaya kung ikaw ay mag-isip ng isang Huffman node, kung titingnan mo bumalik sa ang istraktura dito, kung titingnan mo ang berdeng mga ito ay may isang dalas na nauugnay dito pati na rin ang mga punto upang node sa kaliwa at pati na rin ng node sa kanyang karapatan. At pagkatapos ay ang pulang mga doon ay mayroon ding isang character na nauugnay sa mga ito. Hindi namin upang gumawa ng hiwalay na mga para sa mga magulang at pagkatapos ay ang panghuling node, kung saan namin sumangguni sa bilang mga dahon, ngunit sa halip mga ay lamang null halaga. Para sa bawat node ay makikita namin ang isang character, ang simbolo na kinakatawan ng node na, pagkatapos ng dalas pati na rin ang isang pointer sa kaliwang bata pati na rin ang kanang anak nito. Mga dahon, na kung saan ay sa ibaba, ay ring node na mga payo sa kanilang kaliwa at sa kanilang karapatan, ngunit dahil ang mga halaga ay hindi na tumuturo sa aktwal na node, kung ano ang kanilang mga halaga? >> [Mag-aaral] null. >> Null. Eksakto. Narito ang isang halimbawa ng kung paano mo maaaring kumatawan sa dalas sa kamay, ngunit kami ay pagpunta sa pagharap sa ito sa integer, kaya lahat ko ginawa ay baguhin ang uri ng data doon. 

Natin pumunta sa kaunti higit pa sa isang kumplikadong halimbawa. Ngunit ngayon na tapos kami na ang mga simpleng mga, lamang ang parehong proseso. Mahanap mo ang 2 pinakamababang frequency, nagtutuos ang frequency at na ang bagong dalas ng iyong magulang na node, na pagkatapos POINTS sa kaliwa na may 0 sangay at kanan na may 1 branch. Kung mayroon namin ang string na "Ito ay cs50," pagkatapos namin ang bilang ng kung gaano karaming beses ay nabanggit T, h nabanggit, i, s, c, 5, 0. Pagkatapos kung ano ang ginawa ko dito gamit ang pulang nodes ko lang nakatanim, Sinabi ko ako pagpunta sa kalaunan ang mga character na ito sa ilalim ng aking puno. Yaong na ang lahat ng mga dahon. Pagkatapos sa aking ginawa ay pinagsunod-sunod ko sa kanila sa pamamagitan ng dalas sa pataas na pagkakasunod-sunod, at ito ay talagang ang paraan na ang code ng pset ginagawa ito kusa itong isinasaayos ito sa pamamagitan ng dalas at pagkatapos ay ayon sa alpabeto. Kaya ito ay ang mga numero una at pagkatapos ay ayon sa alpabeto sa pamamagitan ng ang dalas. Pagkatapos kung ano ang gusto kong gawin ay Gusto ko mahanap ang 2 pinakamababang. Iyon ay 0 at 5. Gusto ko sabihin sa ilang mga ito, at na 2. Gusto ko magpatuloy, mahanap ang susunod na 2 pinakamababang. Iyon ang mga dalawang 1s, at pagkatapos ay mga naging 2 pati na rin. Ngayon alam ko na ang aking susunod na hakbang ay pagpunta sa pagsali sa pinakamababang numero, na T, ang 1, at pagkatapos ay piliin ang isa ng node na may 2 bilang ang dalas. Kaya dito kami ay may 3 mga pagpipilian. Ano ako pagpunta sa gawin para sa slide lamang biswal muling ayusin ang mga ito para sa iyo sa gayon ay maaari mong makita kung paano ako sa pagbuo ng mga ito. Ano ang code at ang iyong code sa pamamahagi ng pagpunta sa gawin ay sumali sa T may 0 at 5 node. Kaya pagkatapos na sums sa 3, at pagkatapos ay patuloy naming ang proseso. Ang 2 at ang 2 ngayon ay ang pinakamababang, kaya ang mga kabuuan sa 4. Ang bawat tao'y ng pagsunod sa ngayon? Okay. Pagkatapos matapos na namin ang 3 at sa 3 na kailangang idagdag, kaya muli ako lumipat ito sa gayon maaari mong makita ang biswal sa gayon na ito ay hindi masyadong magulo. Pagkatapos kami ay may 6, at pagkatapos ay ang aming huling hakbang ay ngayon na lamang namin may 2 node namin sabihin sa ilang mga upang gawin ang root ng aming puno, na kung saan ay 10. At ang bilang 10 saysay dahil ang node bawat kinakatawan, ang kanilang mga halaga, ang kanilang dalas numero, kung gaano karaming beses sila lumitaw sa string, at pagkatapos ay mayroon kaming 5 character sa aming string, kaya na saysay. Kung titingnan namin sa kung paano namin ang aktwal na-encode ang mga ito, tulad ng inaasahan, ang i at s, na lumitaw nang mas madalas ay kinakatawan ng fewest bilang ng mga bits. 

Mag-ingat dito. Sa Huffman puno kaso aktwal na mahalaga. Isang uppercase S naiiba kaysa isang lowercase s. Kung nagkaroon kami ng "Ito ay CS50" na may mga malalaking titik, pagkatapos ay lowercase s lamang lumitaw nang dalawang beses, node na may 2 dahil ang mga halaga, at pagkatapos ay uppercase S ay isang beses lamang na. Kaya ang iyong puno ay baguhin ang istraktura dahil iyong aktwal na may dagdag na dahon dito. Ngunit ang kabuuan pa rin 10. Na kung ano ang aktwal na kami ay pagpunta sa pagtawag sa checksum, ang pagdaragdag ng lahat ng mga bilang. 

Ngayon na namin ang saklaw ng mga puno Huffman, maaari naming sumisid sa Huff'n papamintugin, ang pset. Kami ay pagpunta sa magsimula sa isang seksyon ng mga katanungan, at ito ay pagpunta upang makakuha ka sanay sa binary mga puno at kung paano upang mapatakbo sa buong: pagguhit node, ang paglikha ng iyong sariling typedef struct para sa isang node, at nakikita kung paano maaari mong ipasok sa isang binary puno, isa na pinagsunod-sunod, traversing ito, at mga bagay tulad na. Na kaalaman ay tiyak pagpunta upang makatulong sa iyo kapag nag-dive sa bahagi ng Huff'n papamintugin ng ang pset. Sa standard edition ng pset, ang iyong mga gawain ay ipatupad ang papamintugin, at sa bersyon Hacker ang iyong gawain ay ipatupad ang pagtatampo. Ano magtampo ang ay tumatagal ng teksto at pagkatapos ito isinasalin ito sa 0s at 1s, kaya ang proseso na ginawa namin sa itaas kung saan binibilang namin ang frequency at pagkatapos ay gumawa ng tree at pagkatapos sinabi, "Paano ako makakakuha ng T?" T ay kinakatawan ng 100, ang mga bagay tulad na, at pagkatapos magtampo ang teksto at pagkatapos ay ang output na binary. Ngunit din dahil alam namin na gusto naming payagan ang aming tatanggap ng mensahe upang muling likhain ang eksaktong parehong puno, kabilang ang impormasyon tungkol sa bilang ng dalas. Pagkatapos may papamintugin namin ay bibigyan ng isang binary file ng 0s at 1s at ibinigay rin ang impormasyon tungkol sa mga frequency. Tina-translate namin ang lahat ng mga 0s at 1s likod sa orihinal na mensahe na, kaya kami ay decompressing na. Kung ginagawa mo ang standard edition, hindi mo na kailangang ipatupad sa sumpong, kaya maaari mo lamang gamitin ang pagpapatupad ng kawani ng magtampo. Mayroong mga tagubilin sa spec sa kung paano gawin iyon. Maaari kang magpatakbo sa mga tauhan ng pagpapatupad ng pagtatampo sa isang tiyak na file ng teksto at pagkatapos ay gamitin na output bilang iyong input sa papamintugin. 

Tulad ng nabanggit ko bago, mayroon kaming maraming pamamahagi code para sa isang ito. Ako pagpunta upang simulan ang pagpunta sa pamamagitan nito. Ako pagpunta sa paggastos karamihan ng oras sa h file dahil sa file c, dahil mayroon kaming. h at na nagbibigay sa amin sa mga modelo ng mga pag-andar, hindi namin ganap na kailangan upang maunawaan nang eksakto - Kung hindi mo maunawaan kung ano ang nangyayari sa file c, pagkatapos huwag mag-alala masyadong maraming, ngunit tiyak na subukan upang tingnan dahil maaaring magbigay ng ilang mga pahiwatig at ito ay kapaki-pakinabang upang magamit sa pagbabasa ng ibang tao code. 

Naghahanap sa huffile.h, sa comments declares isang layer ng abstraction para sa Huffman-code na mga file. Kung pumunta kami, nakita namin na may isang maximum na 256 simbolo na maaari naming kailanganin ang mga code para sa. Kabilang dito ang lahat ang mga titik ng alpabeto - uppercase at lowercase - at pagkatapos ay simbolo at numero, atbp. Pagkatapos dito mayroon kaming isang magic bilang pagkilala Huffman-code file. Sa loob ng code ng Huffman sila ay pagpunta sa magkaroon ng isang tiyak na bilang ng magic na nauugnay sa header. Ito ay maaaring magmukhang lamang ng random na numero ng magic, ngunit kung aktwal mong isalin ito sa ASCII, pagkatapos ito aktwal na spells ang pagtatampo. Narito mayroon kami ng struct para Huffman-encode na file. Mayroong ang lahat ng mga katangian na nauugnay sa isang file magtampo. Pagkatapos pababa dito namin ang header para sa isang file ng magtampo, kaya tinatawag naming Huffeader sa halip na sa pagdaragdag ng dagdag na h dahil ito tunog ang parehong pa rin. Cute. Mayroon kaming isang magic numero na nauugnay dito. Kung ito ay isang aktwal na file ng magtampo, ito na ang numero sa itaas, ito magic. At pagkatapos ay ito ay isang array. Kaya para sa bawat simbolo, na kung saan may mga 256, ito ilista kung ano ang dalas ng mga simbolo sa loob ng file magtampo. At pagkatapos ay sa wakas, mayroon kaming isang checksum para sa frequency, na dapat ay ang kabuuan ng mga frequency. Kaya iyon ang Huffeader ng. Pagkatapos kami ay may ilang mga function na ibalik ang susunod na kaunti sa file ng magtampo pati na rin ang nagsusulat ng kaunti upang magtampo ang file, at pagkatapos ay ang function na dito, hfclose, na aktwal na isinasara ang magtampo file. Bago, kami ay pakikitungo na may tuwid lamang fclose, ngunit kapag mayroon ka ng isang file sa pagtatampo, sa halip na fclosing ito kung ano ang aktwal na gawin ay hfclose at hfopen ito. Iyon ang tiyak na mga function sa ang mga file magtampo na kami ay pagpunta sa pagharap sa. Pagkatapos dito namin basahin sa header at pagkatapos ay isulat ang header. 

Sa pamamagitan lamang ng pagbabasa ang file na. H maaari namin ang uri ng makakuha ng ideya ng kung ano ng magtampo file ay maaaring, kung ano ang mga katangian ito ay may, nang hindi aktwal na pagpunta sa huffile.c, kung saan, kung namin sumisid sa, pagpunta sa isang bit mas kumplikado. Mayroon ito ng lahat ng file I / O dito pagharap sa mga payo. Narito makita namin na kapag tinatawag naming hfread, halimbawa, pa rin ito pagharap sa fread. Hindi namin inaalis ng mga function ganap na, ngunit ipinapadala namin sa mga na kinuha pag-aalaga ng sa loob ng magtampo file sa halip ng paggawa ng lahat ng ito ating sarili. Maaari mong huwag mag-atubiling i-scan sa pamamagitan ng kung gusto mong malaman at pumunta at alisan ng balat layer likod ng kaunti. 

Ang susunod na file na kami ay pagpunta upang tumingin sa tree.h. Bago sa ang mga slide na walkthrough sinabi namin inaasahan namin Huffman node at nagsagawa kami ng typedef struct node. Inaasahan namin na ito sa isang simbolo, kadalasan, at ang 2 node bituin. Sa kasong ito kung anong ginagawa namin ito ay mahalagang parehong maliban sa halip ng node namin na tumawag sa kanila puno. Mayroon kaming isang function na kapag tumawag ka gumawa ng puno ito nagbabalik ka ng isang puno pointer. Back sa Speller, kapag ikaw ay paggawa ng isang bagong node sinabi mo node * bagong salita = malloc (sizeof) at mga bagay tulad na. Talaga, mktree ay pagpunta sa pagharap sa para sa iyo. Katulad nito, kapag gusto mong alisin ang isang puno, kaya na mahalagang pagbabakante tree kapag tapos ka na dito, sa halip ng tahasang pagtawag libreng on na, aktwal ka lamang gamitin ang function na rmtree kung saan pumasa ka sa pointer sa puno na iyon at pagkatapos ay tree.c-aalaga ng na para sa iyo. 

Inaasahan naming sa tree.c. Inaasahan namin ang parehong mga function maliban upang makita ang pagpapatupad pati na rin. Tulad ng inaasahan namin, kapag tumawag ka mktree mallocs ang laki ng isang puno sa isang pointer, ay initializes sa lahat ng ang mga halaga sa null halaga, kaya 0s o NULLs, at pagkatapos ay bumalik sa pointer na puno mo lang malloc'd sa iyo. Dito kapag tumawag ka alisin puno muna ito tinitiyak na hindi ka double pagbabakante. Tinitiyak na iyong aktwal na magkaroon ng isang puno na gusto mong alisin. Dito dahil puno Kasama rin sa mga bata nito, kung ano ang ginagawa ito recursively tawag-alis ng puno sa kaliwa node ng puno pati na rin ang karapatan node. Bago pinakakawalan nito isang magulang, kailangang magbakante ang mga bata at pati na rin. Magulang din mapagpapalit may ugat. Ang unang kailanman magulang, kaya tulad ng ang dakilang-dakilang-dakilang-dakilang sa tuhod o lola puno, muna namin magbakante pababa sa antas ng unang. Kaya pagbagtas sa ibaba, libreng iyon, at pagkatapos ay bumalik up, libreng mga, atbp. Kaya na puno. 

Ngayon tinitingnan namin sa kagubatan. Kagubatan kung saan inilagay mo ang lahat ng iyong mga puno sa Huffman. Ito ay nagsasabi na kami ay pagpunta sa magkaroon ng tinatawag na isang lagay ng lupa na naglalaman ng pointer sa isang puno pati na rin ang isang pointer sa isang lagay ng lupa na tinatawag na susunod. Ano ang istraktura ng ito uri ng itsura? Ito uri ng sabi ni banda roon. Mag-right sa paglipas dito. Ang isang naka-link na listahan. Nakikita namin na kapag mayroon kami ng isang lagay ng lupa ito ay tulad ng isang naka-link na listahan ng mga plots. Kagubatan ay tinukoy bilang isang naka-link na listahan ng mga plots, at kaya ang istraktura ng kagubatan lang kami pagpunta sa magkaroon ng isang pointer sa aming unang balangkas at isang lagay ng lupa na may puno sa loob nito o sa halip na mga punto sa isang puno at pagkatapos ay mga punto sa susunod na isang lagay ng lupa, kaya sa at iba pa. Upang gumawa ng isang gubat na tinatawag naming mkforest. Pagkatapos mayroon kaming ilang mga medyo kapaki-pakinabang function dito. Mayroon kaming pumili kung saan pumasa ka sa kagubatan at pagkatapos ang return halaga ay isang Tree *, isang pointer sa isang puno. Ano ang pick ay gawin ito pumunta sa gubat ka na tumuturo sa pagkatapos ay alisin ang isang puno na may pinakamababang dalas mula sa na kagubatan at pagkatapos ay magbibigay sa iyo ang pointer sa puno na. Kapag tumawag ka pumili, ang puno ay hindi umiiral sa gubat na ito, ngunit ang return halaga ay ang pointer na puno. Pagkatapos mayroon kang halaman. Ibinigay na pumasa ka sa isang pointer sa isang puno na may non-0 dalas, kung ano ang halaman ay gawin ito ay tumagal ng kagubatan, ang tree, at halaman na puno sa loob ng kagubatan. Narito mayroon namin rmforest. Katulad sa alisin ang tree, na isa lamang napalaya ang lahat ng aming mga puno para sa amin, alisin ang kagubatan ay libre na ang lahat ng nilalaman sa kagubatan na. 

Kung titingnan namin sa forest.c, makikita naming asahan na makita ang hindi bababa sa 1 rmtree utos sa doon, dahil sa libreng memorya sa kagubatan kung ang isang kagubatan ay puno sa, pagkatapos kalaunan mo ay upang alisin ang mga puno. Kung titingnan namin sa forest.c, mayroon kaming aming mkforest, na tulad ng iyong inaasahan namin. Namin malloc bagay. Namin initialize ang unang balangkas sa kagubatan bilang null dahil ito ay walang laman upang magsimula sa, pagkatapos namin makita ang pick, na magbabalik ng mga puno na may pinakamababang timbang, ang pinakamababang dalas, at pagkatapos ay nakakakuha mapupuksa ng na partikular na node na ang mga puntos sa puno na iyon at sa susunod, kaya ito ay tumatagal na ng mga naka-link na listahan ng mga gubat. At pagkatapos dito mayroon kaming planta, kung saan pagsingit ng puno sa naka-link na listahan. Ano kagubatan ay mabuti ito mapigil ang ito pinagsunod-sunod para sa amin. At pagkatapos ay sa wakas, mayroon kaming rmforest at, tulad ng inaasahan, mayroon kaming rmtree tinatawag doon. 

Pagtingin sa pamamahagi ng code sa ngayon, huffile.c ay marahil sa pamamagitan ng malayo ang hardest upang maunawaan, habang ang iba pang mga file ang kanilang mga sarili ay medyo simple sa sundin. Gamit ang aming kaalaman ng payo at ng mga naka-link na listahan at tulad, nagawa naming sundin medyo. Subalit ang lahat ng kailangan namin talagang tiyakin na namin ganap na maunawaan ang. H file dahil kailangan mo na pagtawag ng mga function na iyon, pagharap sa mga halagang iyon return, kaya tiyakin na ganap mong nauunawaan kung ano pagkilos ay pagpunta upang maisagawa ang tuwing tawagan ka ng isa sa mga function. Ngunit aktwal na pag-unawa sa loob nito ay hindi pa kinakailangan dahil mayroon kaming mga h file. Mayroon kaming 2 higit pang mga file na naiwan sa aming pamamahagi ng code. 

Hayaan ang mga tumingin sa dump. Dump sa pamamagitan ng komento dito tumatagal ng isang Huffman-compressed file at pagkatapos ay ibig sabihin at lungkot lahat ng nilalaman nito ang. Narito namin makita na ang pagtawag ng hfopen. Ito ay uri ng mirror file * input = fopen, at pagkatapos ay pumasa ka sa impormasyon. Ito ay halos katulad maliban sa halip ng isang file * ka pagpasa sa isang Huffile; sa halip na fopen ka pagpasa sa hfopen. Narito namin basahin sa unang header, na kung saan ay uri ng katulad sa kung paano namin basahin sa header para sa bitmap na file. Kung anong ginagawa namin dito ang check upang makita kung ang impormasyon ng header naglalaman ng tamang bilang ng magic na nagpapahiwatig na ito ay isang aktwal na file magtampo, pagkatapos ang lahat ng mga tseke upang matiyak na ang mga file na bukas namin ay isang aktwal na huffed file o hindi. Kung ano ang ginagawa ng output ang mga frequency ng lahat ng mga simbolo na maaari naming makita sa loob ng isang terminal sa isang graphical table. Ang bahagi na ito ay maging kapaki-pakinabang. Ito ay isang bit at bumabasa bit sa pamamagitan ng bit sa variable bit at pagkatapos ng mga Kopya ito. Kaya kung ako ay upang tawagan ang dump sa hth.bin, kung saan ay ang resulta ng huffing ng isang file gamit ang solusyon ng kawani, Gusto ko makakuha ng ito. Ito ay outputting ang lahat ng mga character na ito at pagkatapos paglalagay ng dalas sa kung saan lumilitaw ang mga ito. Kung titingnan namin, karamihan sa kanila ay 0s maliban para sa: H, na lumilitaw dalawang beses, at pagkatapos ay T, na lumilitaw sa sandaling. At pagkatapos dito mayroon kaming ang aktwal na mensahe sa 0s at 1s. Kung titingnan namin sa hth.txt, na siguro ang orihinal na mensahe na huffed, inaasahan namin upang makita ang ilang Hs at TS sa doon. Sa partikular, inaasahan namin upang makita ang 1 T at 2 Hs. Narito ang namin sa hth.txt. Ito sa katunayan ay may HTH. Kasama sa doon, bagaman hindi namin makita ito, ay isang newline character. Ang magtampo file hth.bin din page-encode ang newline character pati na rin. Dito dahil alam namin na ang order ay HTH at pagkatapos newline, maaari naming makita na marahil H ay kinakatawan ng isang solong 1 at pagkatapos T ay marahil 01 at pagkatapos ay sa susunod na H ay 1 pati na rin at pagkatapos ay mayroon kaming isang newline na ipinahiwatig sa pamamagitan ng dalawang 0s. Cool. 

At pagkatapos ay sa wakas, dahil kami ay pagharap sa maramihang mga. C at. H file, kami ay isang medyo kumplikadong argumento sa tagatala, at kaya dito mayroon kaming Makefile na gumagawa ng dump para sa iyo. Pero sa totoo, mayroon kang upang pumunta tungkol sa paggawa ng iyong sariling puff.c file. Makefile ang na aktwal na ay hindi humarap sa na puff.c para sa iyo. Aalis Kami ay na hanggang sa iyo upang i-edit ang Makefile. Kapag nagpasok ka ng isang utos tulad gawin ang lahat, halimbawa, ito ay gumawa ng lahat ng mga ito para sa iyo. Huwag mag-atubiling upang tumingin sa mga halimbawa ng mga Makefile mula sa nakaraang pset pati na rin ang pagpunta off ng isang ito upang makita kung paano mo maaaring magagawang upang gawin ang iyong file sa papamintugin sa pamamagitan ng pag-edit na ito Makefile. Na ang tungkol dito para sa aming code ng pamamahagi. 

Sandaling namin na nakuha sa pamamagitan ng na, pagkatapos ay narito ang isa pang paalala lamang ng kung paano namin ay pagpunta sa pagharap sa node Huffman. Hindi Kami ay pagpunta sa ay ang pagtawag sa kanila node ito; kami ay pagpunta sa ay pagtawag sa kanila ng mga puno kung saan kami ay pagpunta sa ay kumakatawan sa kanilang simbolo na may isang pansamantalang trabaho, kanilang dalas, ang bilang ng mga pangyayari, na may isang integer. Ginagamit namin na dahil ito ay mas tumpak na kaysa sa isang Float. At pagkatapos kami ay may isa pang pointer sa kaliwa anak pati na rin ang karapatan na bata. Kagubatan A, tulad ng nakita natin, ay isang naka-link na listahan ng mga puno. Sa huli, kapag kami ay pagbuo ng aming magtampo file, nais namin na ang aming kagubatan na naglalaman ng 1 puno lang - 1 tree, 1 root na may maraming mga bata. Mas maaga sa kapag lamang namin ay paggawa ng aming mga puno Huffman, nagsimula kaming pamamagitan ng paglalagay ng lahat ng node papunta sa aming screen at sinasabi namin ay pagpunta sa mga node, kalaunan sila ay pagpunta sa mga dahon, at ito ang kanilang mga simbolo, ito ang kanilang dalas. Sa aming kagubatan kung lang namin 3 titik, na ng kagubatan ng 3 puno. At pagkatapos ay bilang pumunta kami sa, kapag idinagdag namin ang unang magulang, ginawa namin ng kagubatan ng 2 puno. Inalis namin 2 ng mga bata mula sa aming kagubatan at pagkatapos ay pinalitan ito na may isang pangunahing node na may mga 2 node bilang bata. At pagkatapos ay sa wakas, ang aming huling hakbang sa paggawa ng aming halimbawa sa mga Bilang, BS, at CS ay gawin ang panghuling magulang, at kaya pagkatapos na dalhin ang sa aming kabuuang bilang ng mga puno sa gubat sa 1. Ba ang lahat makita kung paano simulan mo na may maraming mga puno sa iyong kagubatan at nagtatapos na may 1? Okay. Cool. 

Ano ang gagawin namin kailangan gawin para papamintugin? Ano ang kailangan naming gawin ay matiyak na, gaya ng lagi, bigyan sila sa amin ang tamang uri ng input upang maaari naming aktwal na patakbuhin ang program. Sa kasong ito sila ay pagpunta sa pagbigay sa amin pagkatapos ng kanilang unang command-line na argumento 2 higit pa: ang mga file na gusto naming upang magbawas ng bigat at ang output ng decompressed file. Ngunit sa sandaling sigurado kami na pumasa sila sa amin sa tamang halaga ng mga halaga, nais naming matiyak na ang input ay isang magtampo file o hindi. At pagkatapos ay sa sandaling gina-garantiya namin na ang isang file magtampo, gusto naming upang bumuo ang aming puno, bumuo ng tree tulad na tumutugma sa puno na ang taong nagpadala sa mensahe binuo. Pagkatapos pagkatapos bumuo kami ng tree, pagkatapos ay maaari naming harapin ang 0s at 1s na sila nakapasa sa, sundin ang mga kahabaan ng aming puno dahil ito ay magkakahawig, at pagkatapos ay isulat na mensahe, bigyang-kahulugan ang mga bits pabalik sa char. At pagkatapos ay sa dulo dahil kami ay pagharap sa mga payo dito, nais naming tiyakin na hindi namin anumang mga paglabas ng memory at na namin libreng lahat. 

Pagtiyak ng tamang paggamit ng lumang sumbrero para sa amin sa pamamagitan ng ngayon. Namin sa isang input, na ang pangalan ng file sa papamintugin, at pagkatapos naming tukuyin ang isang output, kaya ang pangalan ng file para sa puffed output, na text file. Na ang paggamit. At ngayon nais naming matiyak na input ay huffed o hindi. Iniisip pabalik, ay Mayroon bang anumang sa pamamahagi ng code na maaaring makatulong sa amin sa pag-unawa kung ang isang file ay huffed o hindi? Nagkaroon ng impormasyon sa huffile.c tungkol sa Huffeader. Alam namin na ang bawat pagtatampo file ay may Huffeader nauugnay dito na may magic numero pati na rin ang isang hanay ng mga frequency para sa bawat simbolo pati na rin bilang isang checksum. Alam namin na, ngunit din namin kinuha ng isang silip sa dump.c, kung saan ito ay pagbabasa sa isang file ng magtampo. At iba pa upang gawin iyon, ay upang suriin kung ito ay talagang ay huffed o hindi. Kaya marahil maaari naming gamitin ang dump.c bilang isang istraktura para sa aming puff.c. Bumalik sa pset 4 kapag nagkaroon kami file copy.c na kinopya sa RGB triple at kahulugan namin na para sa sinong may kagagawan at Baguhin ang laki, katulad, kung ano ang maaari mong gawin ay lamang patakbuhin ang command na tulad ng cp dump.c puff.c at gamitin ang ilan ng code doon. Gayunpaman, hindi ito ay pagpunta sa tapat ng isang proseso sa para sa pagsalin ng iyong dump.c sa puff.c, ngunit hindi bababa sa ito ay nagbibigay sa iyo ng isang lugar upang simulan ang kung paano upang matiyak na ang input ay talagang huffed o hindi pati na rin ng ilang mga iba pang mga bagay. Natiyak namin ang tamang paggamit at natiyak na input ay huffed. Bawat oras na ginawa namin na namin ginawa ang aming tamang error checking, kaya bumabalik at sa pagtigil sa pag-andar kung ang ilang pagkabigo nangyayari, kung may problema. 

Ngayon kung ano ang gusto naming gawin ay bumuo ng ang aktwal na puno. Kung titingnan namin sa Forest, may 2 pangunahing function na kami ay pagpunta sa nais upang maging napaka-pamilyar sa. Ang Boolean function na halaman na non-0 tree dalas sa loob ng aming kagubatan halaman. At kaya pumasa ka sa isang pointer sa isang gubat at ng pointer sa isang puno. Quick tanong: Gaano karaming mga kagubatan ay mayroon ka kapag ikaw ay pagbuo ng isang puno Huffman? Aming kagubatan ay tulad ng ating canvas, tama? Kaya lamang namin ang 1 kagubatan, ngunit kami ay pagpunta sa magkaroon ng maramihang mga puno. Kaya bago tumawag ka ng halaman, baka ka pagpunta sa gusto mong gawin ang iyong mga kagubatan. May isang utos para sa kung tiningnan mo sa forest.h sa kung paano maaari mong gumawa ng kagubatan. Maaari mong planta ng isang puno. Alam namin kung paano gawin iyon. At pagkatapos maaari ka ring pumili ng isang puno mula sa kagubatan, pag-aalis ng isang puno na may pinakamababang timbang at nagbibigay sa iyo ng ang pointer iyon. Iniisip pabalik sa kapag kami ay paggawa ng mga halimbawa na ating sarili, kapag kami ay pagguhit ito, lamang namin lamang na idinagdag ang link. Ngunit dito sa halip ng pagdaragdag ng mga link, -isip ng mas habang ikaw ay alisin ang 2 ng mga node at pagkatapos ay palitan ito ng ibang. Upang ipahayag na sa mga tuntunin ng pagpili at planting, ka pagpili ng 2 puno at pagkatapos planting isa pang puno na may mga 2 puno na iyong pinili bilang mga bata. Upang bumuo ng puno Huffman, maaari mong basahin sa mga simbolo at mga frequency upang dahil Huffeader ang nagbibigay na sa iyo, nagbibigay sa iyo ng isang array ng mga frequency. Sa gayon maaari mong magpatuloy at huwag pansinin ang anumang bagay na may 0 sa ito dahil hindi namin nais 256 dahon sa dulo nito. Nais lamang namin ang bilang ng mga dahon na character na aktwal na ginagamit sa file. Maaari mong basahin sa mga simbolo, at ang bawat isa sa mga simbolo na may non-0 frequency, mga pagpunta sa maging ang mga puno. Ano ang maaari mong gawin sa bawat oras na basahin sa isang non-0 simbolo ng dalas, maaari mong planta na puno sa kagubatan. Sandaling planta mo ang mga puno sa gubat, maaari mong sumali sa mga puno bilang mga kapatid, kaya bumalik sa planting at pagpili kung saan pumili ka 2 at pagkatapos ay planta 1, kung saan na 1 na halaman mo ang magulang ng 2 bata na pinili mo. Kaya ang iyong pagtatapos resulta ng isang puno sa iyong kagubatan. Kung paano buuin mo ang iyong puno. 

May ilang mga bagay na maaaring magkamali dito dahil kami ay pagharap sa paggawa ng mga bagong puno at pagharap sa mga payo at mga bagay tulad na. Bago kapag kami ay pagharap sa mga payo, tuwing malloc'd namin namin nais upang matiyak na hindi ito bumalik sa amin ng Null pointer halaga. Kaya sa ilang mga hakbang sa loob ng prosesong ito pagpunta sa ilang mga kaso kung saan ang iyong programa ay maaaring mabigo. Ano ang gusto mong gawin ay nais mong tiyakin mong pangasiwaan ang mga error, at sa spec sinasabi nito upang mahawakan ang mga ito maganda, kaya bang i-print ang isang mensahe sa user na nagsasabi sa kanila kung bakit ang programa ay may na umalis at pagkatapos ay agad na mag-quit ito. Upang gawin ito error handling, tandaan na nais mong upang suriin ito bawat solong oras na may isang pagkabigo. Bawat solong oras na nagsasagawa ka ng isang bagong pointer nais mong upang matiyak na na matagumpay. Bago kung ano ang ginamit namin gawin ay gumawa ng isang bagong pointer at malloc ito, at pagkatapos ay naming suriin kung ang pointer na null. Kaya pagpunta sa ilang mga pagkakataon kung saan mo lang gawin na, ngunit minsan aktwal ka pagtawag ng isang function at sa loob ng function na iyon, na ang isa na ginagawa ang mallocing. Sa kasong iyon, kung tiningnan namin pabalik sa ilang mga pag-andar sa loob ng code, Ang ilan sa kanila ay Boolean function. Sa abstract kaso kung kami ay may isang Boolean function na tinatawag foo, talaga, maaari naming ipagpalagay na sa karagdagan sa paggawa ng anumang foo ginagawa, dahil ito ay isang Boolean function na ito, nagbalik tama o mali - totoo kung matagumpay, maling kung hindi. Kaya gusto namin upang suriin kung ang return halaga ng foo ay totoo o hindi. Kung ito ang maling, na nangangahulugan na kami ay pagpunta sa gusto upang i-print ang ilang mga uri ng mensahe at pagkatapos ay mag-quit sa programa. Ano ang gusto naming gawin ay suriin ang return halaga ng foo. Kung nagbabalik ng foo maling, alam namin na namin na nakaranas kami ng ilang mga uri ng error at kailangan namin na umalis ang aming programa. Ang isang paraan upang gawin ito ay isang kalagayan kung saan ang aktwal na function na mismo ang iyong kundisyon. Sabihing foo tumatagal sa x. Maaari naming bilang isang kondisyon kung (foo (x)). Talaga, na nangangahulugan kung sa dulo ng pag-execute foo ito nagbabalik totoo, maaari naming gawin ito dahil ang function ay upang suriin foo upang suriin ang buong kondisyon. Kaya pagkatapos na kung paano mo maaaring gawin ang isang bagay kung ang function ay nagbabalik ng tunay at matagumpay ang. Ngunit kapag hindi mo ang error checking, gusto mo lamang na umalis kung ang iyong function na ay nagbabalik ng maling. Ano ang maaari mong gawin ay idagdag lamang ng == mali o idagdag lamang ang isang putok sa unahan nito at pagkatapos ay mayroon kang kung (! foo). Sa loob ng katawan ng kondisyon na mayroon ka ng lahat ng handling ng error, kaya i, "Hindi malikha ang puno na ito" at pagkatapos ay bumalik sa 1 o isang bagay tulad na. Ano na, bagaman, na kahit foo ibinalik maling - Sabihing foo nagbabalik totoo. Pagkatapos hindi mo na kailangang tumawag muli ang foo. Na ang isang karaniwang maling kuru-kuro. Dahil ito ay sa iyong kondisyon, na ito sinusuri, kaya mo na ang resulta kung gumagamit ka ng puno o isang bagay tulad na o halaman o pick o isang bagay. Ito ay mayroon ng halagang iyon. Na ito ay pinaandar. Kaya ito ay kapaki-pakinabang na gumamit ng Boolean function bilang ang kundisyon dahil mo man o hindi aktwal na isagawa ang katawan ng loop, executes-andar pa rin. 

Ang aming ikalawang sa huling hakbang ay sumusulat ang mensahe sa file. Sa sandaling namin buuin ang Huffman puno, pagkatapos pagsulat ang mensahe sa file ay medyo direkta. Medyo direkta ngayon upang sundin lamang ang mga 0s at 1s. At ito sa pamamagitan ng convention na alam namin na sa isang puno ng Huffman 0s ipahiwatig ang natitira at 1s ipahiwatig karapatan. Kaya pagkatapos kung ikaw basahin unti-unti, sa bawat oras na makakakuha ka ng 0 makikita mo sundin ang kaliwang sangay, at bawat oras na basahin mo sa 1 ka pagpunta sa sundin ang mga karapatan sangay. At pagkatapos ka pagpunta upang magpatuloy hanggang maabot ang isang dahon dahil ang mga dahon sa dulo ng sanga. Paano maaari naming sabihin kung kami ay pindutin ang isang dahon o hindi? Sinabi namin ito dati. [Mag-aaral] Kung ang mga payo ay null. >> Oo. Maaari naming sabihin kung namin pindutin ang dahon kung ang mga payo sa parehong kaliwa at kanang mga puno null. Perpekto. Alam namin na gusto namin na basahin ang unti-unti sa aming pagtatampo file. Tulad ng nakita natin bago sa dump.c, kung ano ang kanilang ginawa nila basahin sa unti-unti sa file magtampo at naka-print kung ano ang mga bits ay. Hindi Kami ay pagpunta sa paggawa na. Kami ay pagpunta sa paggawa ng isang bagay na mas kumplikado ang ng kaunti. Ngunit kung ano ang maaari naming gawin ay maaari namin na bit ng code na bumabasa in sa bit. Narito mayroon namin ang integer bit na kumakatawan sa kasalukuyang bit na hindi namin sa. Ito ay tumatagal ng pag-aalaga ng iterating ang lahat ng mga piraso sa file hanggang maabot ang dulo ng file. Batay sa na, pagkatapos ikaw ay pagpunta sa nais na magkaroon ng ilang mga uri ng iterator sa pagbagtas ang iyong puno. At pagkatapos ay batay sa kung ang bit sa 0 o 1, ka pagpunta sa nais na ilipat na iterator sa kaliwa o ilipat ito sa kanan ang lahat ng paraan hanggang maabot ang isang dahon, kaya ang lahat ng mga paraan hanggang sa na node na ikaw ay nasa ay hindi tumuturo sa anumang higit pang mga node. Bakit maaari naming gawin ito sa Huffman file ngunit hindi Morse code? Dahil sa Morse code ng kaunting kalabuan. Maaaring namin na tulad ng, oh paghihintay, kami pindutin ang isang sulat sa kahabaan ng paraan, kaya maaaring ito ay ang aming sulat, samantalang kung patuloy namin ng kaunti lamang na, pagkatapos ay namin ang pindutin ang sulat ng isa pang. Ngunit na hindi pagpunta sa mangyayari sa Huffman pag-encode, upang maaari naming magpahinga panatag na ang tanging paraan na kami ay pagpunta upang maabot ang isang character kung ang kaliwa at kanang mga bata na node null. 

Panghuli, nais naming upang magbakante ang lahat ng aming memory. Nais naming sa parehong malapit sa pagtatampo file na namin ang pagharap sa pati na rin alisin ang lahat ng mga puno sa ating kagubatan. Batay sa iyong pagpapatupad, marahil ka pagpunta sa nais upang tumawag alisin kagubatan sa halip ng mga aktwal na pagpunta sa pamamagitan ng lahat ng mga puno sa iyong sarili. Ngunit kung gumawa ka ng anumang pansamantalang puno, makikita mo nais na magbakante na. Alam mo pinakamahusay na ang iyong code, kaya alam mo kung saan ka paglaan ng memorya. At kaya kung pumunta ka sa, magsimula sa pamamagitan ng kahit Control F'ing para sa malloc, nakikita tuwing malloc at siguraduhin na magbakante mo ang lahat ng na ngunit pagkatapos lamang ng pagpunta sa pamamagitan ng iyong code, unawa kung saan maaari mong inilalaan memory. Karaniwan maaari mong lang sabihin, "Sa dulo ng isang file lamang ako upang alisin ang kagubatan sa aking kagubatan," kaya talaga i-clear na memorya, libreng, "At pagkatapos din ako pagpunta upang isara ang file at pagkatapos ay ang aking programa ay na umalis." Ngunit na lamang ang oras na tabla ng iyong programa? Hindi, dahil minsan may maaaring isang error na nangyari. Siguro hindi namin ma-buksan ang isang file o hindi namin maaaring gumawa ng isa pang tree o ilang mga uri ng error na nangyari sa proseso ng paglalaan ng memorya at kaya ibinalik null. May error na nangyari at pagkatapos ay ibinalik namin at huminto. Kaya nais mong upang matiyak na ang anumang posibleng pagkakataon na ang iyong programa ay maaaring mag-quit, gusto mong magbakante lahat ng iyong memory doon. Hindi ito lamang sa pinakadulo ng pangunahing function na lumabas mula sa iyong code. Nais mong upang tumingin pabalik sa bawat pagkakataon na ang iyong code potensyal na maaaring bumalik nang maaga at pagkatapos libreng anumang memory saysay. Sinasabi mo ay tinatawag na gumawa ng kagubatan at ibinalik maling. Pagkatapos ay malamang na hindi ka kailangang alisin ang iyong kagubatan dahil hindi mo pa ng kagubatan. Ngunit sa bawat punto sa code kung saan maaari kang bumalik maaga nais mong tiyakin na magbakante kang anumang mga posibleng memory. 

Kaya kapag kami ay pagharap sa pagbabakante memory at pagkakaroon ng mga potensyal na paglabas, gusto naming upang hindi lamang gamitin ang aming paghatol at ang aming logic ngunit ring gamitin Valgrind upang matukoy kung namin ang napalaya ang lahat ng aming mga memory maayos o hindi. Maaari mong patakbuhin ang Valgrind sa papamintugin at pagkatapos ay mayroon kang ring magpasa ang tamang bilang ng mga command-line argumento sa Valgrind. Maaari kang magpatakbo ng na, ngunit ang output bit misteriyoso. Namin na nakuha ng isang bit na ginamit sa ito sa Speller, ngunit kailangan pa rin namin ng kaunti pang tulong, kaya pagkatapos tumatakbo ito na may ilang higit pang mga flag tulad ng sa mahayag-check = buong, na malamang na bigyan kami ng ilang mga mas kapaki-pakinabang na output sa Valgrind. 

Pagkatapos ay isa pang kapaki-pakinabang na tip kapag ikaw ay pag-debug ay ang diff utos. Maaari mong ma-access ang pagpapatupad sa mga tauhan ng magtampo, patakbuhin na sa isang text file, at pagkatapos output ito sa isang binary file, isang binary file ng magtampo, maging tukoy. Pagkatapos kung nagpapatakbo ka ang iyong sariling papamintugin sa binary file na iyon, pagkatapos perpektong, iyong outputted text file ay pagpunta sa magkakahawig sa orihinal na ang pumasa ka. Narito ako gumagamit ng hth.txt bilang halimbawa, at na uusapang tungkol sa iyong spec. Iyon ay literal lamang HTH at pagkatapos ay isang newline. Ngunit talagang huwag mag-atubiling at tiyak na ikaw ay hinihikayat na gumamit ng mas mahabang halimbawa para sa iyong text file. 

Maaari ka ring kumuha ng shot siguro pigain at pagkatapos decompressing ilan sa ang mga file na ginamit mo sa Speller tulad ng Digmaan at Kapayapaan o Jane Austen o isang bagay tulad na - na uri ng mga cool na - o Austin Powers, uri ng pakikitungo na may mas malaking mga file dahil hindi namin ay bumaba ito kung ginamit namin sa susunod na tool dito, ls-l. Kami ay ginagamit sa ls, kung saan talaga ay naglilista ng lahat ng mga nilalaman sa aming kasalukuyang direktoryo. Pagpasa sa bandila-l na aktwal na ipinapakita ang laki ng mga file. Kung pupunta ka sa pamamagitan ng spec pset, aktwal na ito ay nagtuturo sa iyo sa pamamagitan ng paglikha ng binary file, ng huffing ito, at nakikita mo na para sa napakaliit na file ang gastos ng espasyo ng pigain ito at nagta-translate ang lahat ng impormasyon na iyon ng lahat ng mga frequency at mga bagay tulad na outweighs ang aktwal na benepisyo ng pigain ang file sa unang lugar. Ngunit kung nagpapatakbo ka sa ilang mga mas mahabang mga tekstong file, pagkatapos ay maaari mong makita na simulan mo upang makakuha ng ilang mga pakinabang sa pigain ng mga file. 

At pagkatapos ay sa wakas, mayroon namin ang aming lumang pal GDB, na kung saan ay tiyak na darating sa madaling-gamiting. 

Namin may anumang mga katanungan sa mga puno ng pagtatampo o ang proseso marahil ng paggawa ng mga puno o anumang iba pang mga mga tanong sa Huff'n papamintugin? Okay. Magtatagal ako sa paligid para sa isang bit. 

Salamat, sa lahat. Ito walkthrough 6. At good luck. 

[CS50.TV]