[Powered by Google Translate] [Walkthrough - Problemo Serio 6] [Zamyla Chan - Universitato Harvard] [Jen CS50. - CS50.TV] 

Saluton, ĉiuj, kaj bonvenon al Walkthrough 6: Huff'n Puff. En Huff'n Puff kion ni faras tuj estos kontraktanta kun Huffman kunpremita dosiero kaj tiam fumante ĝin supren, por decompressing ĝin, tiel ke ni povos traduki el la _0s_ kaj _1s_ ke la uzanto sendas al ni kaj igi ĝin denove en la originala teksto. Pset 6 tuj estos bela malvarmeta ĉar vi tuj vidos kelkajn el la iloj ke vi uzis en pset 4 kaj pset 5 kaj tipon de kombini ilin en 1 belan neta koncepto kiam vi venos por pensi pri ĝi. 

Ankaŭ, eble, pset 4 kaj 5 estis la plej defia psets ke ni devis proponi. Do de nun, ni havas ĉi ankoraŭ 1 pset en C, kaj tuj poste ni al retejo programado. Do gratulas vin por atingi super la plej malmolaj ĝibo en CS50. 

Movante on por Huff'n Puff, nia iloj por ĉi pset tuj estos Huffman arboj, tiel kompreni ne nur kiel duumaj arboj laboron sed ankaŭ specife Huffman arboj, kiom ili estas konstruita. Kaj tiam ni havos multe de dissendo kodo en ĉi pset, kaj ni venis vidi kiu vere iuj de la kodo ni eble ne povos plene kompreni ankoraux, kaj tiel tiuj estos la. c dosierojn, sed tiam la koneksa. h dosieroj donos al ni sufiĉe komprenon ke ni bezonas tiel ke ni scias, kiel tiuj funkcioj funkcii aŭ almenaŭ kion ili devus fari - iliaj enigoj kaj eligoj - eĉ se ni ne scias kio okazas en la nigra skatolo aŭ ne komprenas kio okazas en la nigra skatolo ene. Kaj poste fine, kiel kutime, ni pritraktas novajn datumstrukturoj, specifaj tipoj de nodoj kiuj indikas iujn aferojn, kaj tiel tie havi plumo kaj papero ne nur por la dezajno procezo kaj kiam vi provas diveni kiel via pset devus funkcii sed ankaŭ dum depuración. Vi povas havi GDB apud viaj plumo kaj papero dum vi prenos malsupren kion la valoroj estas, kie estas via sagoj estas montrante, kaj aferojn tiel. 

Unue ni rigardu Huffman arboj. Huffman arboj estas duumaj arboj, signifo ke ĉiu vertico havas nur 2 idoj. En Huffman arboj la karakterizo estas ke la plej ofta valoroj estas reprezentitaj de la malplej bitoj. Ni vidis en prelego ekzemploj de Morsa kodo, kiu ia solidigita iuj literoj. Se vi provas traduki la A aŭ E, ekzemple, vi tradukante ke ofte, do anstataŭ devi uzi la plena aro de bitoj asignitaj por tiu kutima datumtipo, vi kunpremi ĝin al malpli, kaj tiam tiuj literoj, kiuj estas reprezentitaj malpli ofte estas reprezentitaj per plu bitoj ĉar vi povas pagi, ke kiam vi pesas el la oftecojn ke tiuj literoj aperas. Ni havas la sama ideo tie en Huffman arboj kie ni estas farante ĉenon, speco de vojo por atingi la certaj karakteroj. Kaj tiam la karakteroj kiuj havas la plej frekvenca tuj estos reprezentita per la malplej bitoj. 

La vojo, kiun vi konstruas Huffman arbo Estas metante ĉiujn karakterojn kiuj aperas en la teksto kaj kalkuli siajn ofteco, kiom ofte aperas. Tio povus bone esti grafo de kiom fojoj tiuj literoj aperas aŭ eble procenton de el ĉiuj karakteroj kiom da ĉiu aperas. Kaj tiel tio, kion vi faras estas iam vi havas ĉiuj de tiu mapita eksteren, tiam vi serĉas la plej malalta 2 frekvencoj kaj poste kunigi ilin kiel gefratoj kie tiam la patro nodo havas oftecon kiu estas la sumo de liaj 2 infanoj. Kaj poste vi per konvencio diri ke la maldekstra nodo, vi sekvas ke sekvante la 0 branĉo, kaj tiam la plej dekstra nodo estas la 1 branĉo. Kiel ni vidis en Morsa kodo, la gotcha estis ke se vi havis nur pepi kaj la pepi estis ambigua. Ĝi povus aŭ esti 1 litero aŭ ĝi povis esti vico de 2 literoj. Kaj tiel kion Huffman arboj faras estas pro sia naturo de la karakteroj aŭ nia fina reala gravuloj esti la lasta nodoj en la branĉo - ni priparolas tiujn kiel folioj - virto de tiu tie ne povas esti ajna ambigueco en terminoj de kiuj letero vi provas kodi kun la serio de bitoj ĉar nenie kune la bitoj kiuj reprezentas 1 letero vi renkontos alian tuta letero, kaj ne estos ajna konfuzo tie. Sed ni iros en ekzemploj ke vi infanoj povas fakte vidi ke anstataŭ ni nur diras al vi, ke tio estas vera. 

Ni rigardu simpla ekzemplo de Huffman arbo. Mi havas ĉenon tie estas 12 signojn longa. Mi havas 4 Kiel, 6 Bs, kaj 2 Cs. Mia unua paŝo estus rakonti. Kiom da fojoj tio A aperi? Ĝi aperas 4 fojojn en la kordo. B aperas 6 fojojn, kaj C aperas 2 fojojn. Nature, mi intencis diri Mi uzas B plej ofte, do mi volas reprezenti B kun la malplej kvanto de bitoj, la malplej kvanto de _0s_ kaj _1s_. Kaj tiam mi ankaŭ tuj atendus C al postulas la plej kvanto de _0s_ kaj _1s_ tiel. Unue kion mi faris tie mi metis ilin en suprenira ordo en terminoj de ofteco. Ni vidas, ke la C kaj la A, tiuj estas niaj 2 plej malalta oftecoj. Ni kreos patro nodo, kaj ke patro nodo ne havas literon asociita kun ĝi, sed ĝi havas oftecon, kiu estas la sumo. La sumo iĝas 2 + 4, kiu estas 6. Tiam ni sekvu la maldekstra branĉo. Se ni estus en tiu 6 nodo, tiam ni devus sekvi 0 al preni al C kaj tiam 1 ĝis alveni al A. Do nun ni havas 2 nodoj. Ni havas la valoron 6 kaj poste ni ankaŭ havas alian nodon kun la valoro 6. Kaj tial tiuj 2 estas ne nur la 2 plej malalta sed ankaŭ nur la 2, kiuj restis, do ni aliĝi tiuj de alia patro, kun la sumo estante 12. Do jen ni havas niajn Huffman arbo kie akiri al B, kiu estus nur la bito 1 kaj poste por akiri al A ni havus 01 kaj tiam C havanta 00. Do jen ni vidas ke esence ni reprezentas tiuj signoj kun ĉu 1 aŭ 2 bitoj kie la B, kiel antaŭdiris, havas la malplej. Kaj poste ni atendis C havi la plej, sed ĉar ĝi estas tiel malgranda Huffman arbo, tiam la A estas ankaŭ reprezentita de 2 bitoj kiel kontraŭ ie en la mezo. 

Nur iri super alia simpla ekzemplo de la kodigo arbo, diras, ke vi havas la ĉeno "Saluton." Kion vi faras, estas unue vi dirus kiom da fojoj tio H aperas en tio? H aperas unufoje kaj poste e aperas unufoje kaj poste ni havas l'aperi dufoje kaj o aperante unufoje. Kaj tiel poste ni atendas ke letero por esti prezentita per la malplej kvanto de bitoj? [Studento] l. >> L. Yeah. l estas prava. Ni atendas l esti prezentita per la malplej kvanto de bitoj ĉar l uzas plej en la ĉeno "Saluton." Kion mi faros nun estas nudigos tiuj nodoj. Mi havas 1, kiu estas H, kaj poste alia 1, kiu estas e, kaj tiam 1, kiu estas o - nun mi metis ilin en ordo - kaj tiam 2, kiu estas l. Tiam mi diras la vojo, kiun mi konstruas Huffman arbo estas trovi la 2 nodoj kun la malplej frekvencoj kaj Mi faros ilin gefratoj kreante patro nodo. Ĉi tie ni havas 3 nodoj kun la plej malalta ofteco. Ili estas ĉiuj 1. Do jen ni elekti kiu ni iras ligi unua. Diru min elekti la H kaj la TTT. La sumo de 1 + 1 estas 2, sed ĉi nodo ne havas literon asociita kun ĝi. Ĝi simple tenas la valoro. Nun ni rigardu la sekvanta 2 plej malalta oftecoj. Tio estas 2 kaj 1. Tio povus esti iu el tiuj 2, sed mi tuj elekti ĉi tiun. La sumo estas 3. Kaj poste fine, mi nur havas 2 maldekstra, do tiam tiu igas 5. Tiam tie, kiel atendita, se mi plenigu la kodigo por tiu, 1s estas ĉiam la dekstra branĉo kaj _0s_ estas la maldekstra. Tiam ni havas l'reprezentita de nur 1 bito kaj tiam la o de 2 kaj tiam la TTT per 2 kaj poste la H falas malsupren al 3 bitoj. Do vi povas transdoni ĉi mesaĝo "Saluton" anstataŭ efektive uzante la karakteroj por nur _0s_ kaj _1s_. Tamen, memoru ke en kelkaj kazoj ni havis ligojn kun nia ofteco. Ni povis esti ĉu aliĝis al la H kaj la o unue eble. Aŭ tiam poste kiam ni havis la l reprezentita de 2 tiel kiel la aliĝis reprezentita per 2, ni povus esti ligitaj ĉu unu. 

Kaj tiel, kiam vi sendu la _0s_ kaj _1s_, ke reale ne garantias ke la ricevanto povas plene legis vian mesaĝon dekstra ekstere la batilo ĉar ili eble ne scias kion decidon vi faris. Do kiam ni pritraktas Huffman kunpremo, iel ni devas diri la ricevanto de nia mesaĝo kiom ni decidis - Ili bezonas scii ia ekstra informo krom la kunpremita mesaĝo. Ili bezonas kompreni, kion la arbo vere aspektas kiel, kiel ni fakte faris tiujn decidojn. 

Jen ni estis nur fari ekzemplojn bazita sur la reala grafo, sed kelkfoje oni povas ankaŭ havi Huffman arbo bazita sur la frekvenco en kiu literoj aperas, kaj estas la ĝusta sama procezo. Jen mi esprimas ĝin en terminoj de procentoj aŭ frakcio, kaj tiel tie la ĝusta sama afero. Mi trovas la 2 plej malalta, resumi ilin, la sekvanta 2 plej malalta, resumi ilin, ĝis mi havas plenan arbon. Eĉ kvankam ni povus fari ĝin ĉu vojo, kiam ni pritraktas procentoj, kiu signifu ni dividante aĵoj kaj kontraktanta kun glitpunktaj nombroj aŭ pli ĝuste flosas se ni pensas pri datumstrukturoj en kapo. Kion ni scias pri flosas? Kio estas komuna problemo kiam ni pritraktas flosas? [Studento] malpreciza aritmetiko. >> Jes. Imprecision. Pro glitpunktaj imprecision, por ĉi pset por ke ni certigu ke ni ne perdas ajnan valoroj, tiam ni efektive tuj estos kontraktanta kun la grafo. Do se vi estus pensi de Huffman nodo, se vi retrorigardas al la strukturo tie, se vi rigardas la verdoj havas ofteco asociita kun ĝi tiel kiel notas al nodo al lia maldekstra tiel kiel nodo al lia rajto. Kaj tiam la ruĝaj tie ankaŭ havas karakteron asociita kun ili. Ni ne intencas fari apartan bonaj por la gepatroj kaj poste la fina verticoj, kiuj ni raportas kiel folioj, sed prefere tiujn simple devos NULL valoroj. Po nodo ni havas karakteron, la simbolo kiu ke nodo reprezentas, tiam ofteco tiel kiel puntero al lia maldekstra infano kaj ankaŭ lia dekstra infano. La folioj, kiuj estas je la tre fundo, ankaŭ devus nodo punteros al lia maldekstra kaj la dekstra, sed pro tio ke tiuj valoroj ne indikante reala nodoj, kio estus ilia valoro estos? >> [Studento] NULL. >> NULL. Ekzakte. Jen ekzemplo de kiel vi eble reprezentas la ofteco en flosas, sed ni tuj estos kontraktanta kun ĝi kun entjeroj, tiel ĉiuj mi faris estas ŝanĝi la datumtipo tie. 

Ni iru al iom pli kompleksa ekzemplo. Sed nun, kiam ni faris la simplaj, estas nur la sama procezo. Vi trovos la 2 plej malalta frekvencoj, resumi la oftecojn kaj tio estas la nova frekvenco de via patro nodo, kiuj tiam notas al lia maldekstra kun la 0 branĉo kaj la dekstra kun la 1 branĉo. Se ni havas la ĉeno "Tio estas cs50," tiam ni kalkulu kiom da fojoj ĝi T menciis, h menciis, i, j, c, 5, 0. Tiam kion mi faris tie estas kun la ruĝa nodoj Mi nur plantis, Mi diris ke mi tuj devos tiujn karakterojn eventuale je la fundo de mia arbo. Tiuj tuj estos la tuta de la folioj. Tiam kion mi faris estas mi ordo ili ofteco en suprenira ordo, kaj ĉi tiu estas vere la vojon, ke la pset kodo faras ĝin ĉu specoj ĝin ofteco kaj tiam alfabete. Do ĝi havas la numerojn unua kaj tiam alfabete de la frekvenco. Tiam kion mi farus estas mi trovus la 2 plej malalta. Tio estas 0 kaj 5. Mi resumi ilin, kaj tio estas 2. Tiam mi daŭrigus, trovi la sekvanta 2 plej malalta. Tiuj estas la du 1s, kaj tiam tiuj fariĝis 2 kiel bone. Nun mi scias ke mia sekva paŝo tuj estos kunigi la plej malalta nombro, kiu estas la T, la 1, kaj poste elekti unu el la nodoj kiu havas 2 kiel la frekvenco. Do jen ni havas 3 eblojn. Kion mi faros por la glito nur vide reordigi ilin por vi por ke vi povas vidi kiel mi konstrui ĝin. Kion la kodon kaj vian dissendo kodo tuj faros estus kunigi la T unu kun la 0 kaj 5 nodo. Tial ke sumoj al 3, kaj poste ni daŭrigos la procezon. La 2 kaj la 2 nun estas la plej malalta, do tiam tiuj adicias 4. Cxiu sekvas ĝis nun? Okay. Tiam, post ke ni havas la 3 kaj la 3 kiu bezonas esti aldonita supren, do denove mi nur ŝanĝi ĝin tiel ke vi povas vidi vide por ke ĝi ne ricevas tro senorda. Tiam ni havas 6, kaj tiam nia fina paŝo estas nun ke ni nur havas 2 nodoj ni resumi tiujn fari la radiko de nia arbo, kiu estas 10. Kaj la nombro 10 havas sencon ĉar ĉiu vertico reprezentis, lia valoro, lia ofteco numeron, estis kiom fojoj ili aperis en la ĉeno, kaj poste ni havas 5 signojn en nia kordoj, tiel ke havas sencon. Se ni rigardas supren, kiamaniere ni vere kodi ĝi, kiel atendita, la i kaj la s, kiu prezentas la plej ofte estas reprezentitaj de la malplej kvanto de bitoj. 

Gardu tie. En Huffman arboj la kazo vere gravas. An majuskla S estas malsama ol minuskla s. Se ni havis "Tio estas CS50" kun majuskloj, do la minuskla s nur aperus duoble, Estus nodo kun 2 kiel ĝia valoro, kaj tiam majuskla S nur estus unu fojon. Do tiam via arbo ŝanĝus strukturoj ĉar vi efektive havas ekstra folio ĉi tie. Sed la sumo estus ankoraŭ 10. Tio estas kion ni reale tuj estos nomante la checksum, la aldono de ĉiuj el la grafoj. 

Nun ke ni kovris Huffman arboj, ni povas plonĝi en Huff'n Puff, la pset. Ni tuj komenci kun sekcio de demandoj, kaj ĉi tiu tuj ekiru alkutimiĝis kun binara arboj kaj kiel operacii ĉirkaŭ ke: desegni nodojn, kreante vian propran typedef struct por nodo, kaj vidi kiel vi eble enmeti en duuma arbo, tiu ke tio ordo, lauxiris ĝin, kaj tion tiel. Ke scio estas definitive tuj helpi vin, kiam vi pikita en la Huff'n Puff parto de la pset. En la normo eldono de la pset, via tasko estas realigi Puff, kaj en la hacker versio Via tasko estas realigi Huff. Kio Huff faras estas prenas teksto kaj tiam tradukas gxin en la _0s_ kaj _1s_, tiel la procezo, kiun ni faris supre, kie ni kalkulis la frekvencojn kaj poste faris la arbon kaj poste diris: "Kiel mi estas rekompenciĝita T?" T estas reprezentita de 100, aĵoj kiel tiu, kaj tiam Huff prenus la tekston kaj poste eligo ke binaraj. Sed ankaŭ ĉar ni scias ke ni volas permesi nian ricevanto de la mesaĝo amuzi la ĝusta sama arbo, ĝi inkludas ankaŭ informojn pri la ofteco grafoj. Tiam kun Puff ni estas donita duargumenta arkivon de _0s_ kaj _1s_ kaj donis ankaŭ la informon pri la frekvencoj. Ni traduki ĉiujn tiuj _0s_ kaj _1s_ dorso enen la originala mesaĝo kiu estis, do ni decompressing tio. Se vi faras la normon eldono, vi ne bezonas apliki Huff, tiel tiam vi povas simple uzi la bastonon efektivigo de Huff. Esas instrukciojn en la specifo pri kiel fari tion. Vi povas lanĉi la bastonon efektivigo de Huff sur iu teksta dosiero kaj poste uzas tiun produktadon laŭ via enigo al Puff. 

Kiel mi menciis antaŭe, ni havas multe da dissendo kodo por tiu ĉi. Mi tuj komencos tuj tra ĝi. Mi pasigos la plejparto de la tempo sur la. H dosieroj ĉar en la. c dosierojn, ĉar ni havas la. h kaj tio donas al ni la prototipoj de la funkcioj, ni ne tute bezonas kompreni ĝuste - Se vi ne komprenas kio okazas en la. C dosieroj, tiam ne tro maltrankviliĝu, sed definitive provu rigardi ĉar ĝi povus doni iujn aludoj kaj estas utila por alkutimiĝi al legado fremdajn kodo. 

Rigardante huffile.h, en la komentoj deklaras mantelo de abstraktado por Huffman-kodita dosierojn. Se ni iras malsupren, oni vidas ke estas maksimumo de 256 simboloj kiuj ni povus bezoni kodojn por. Tio inkluzivas ĉiujn literojn de la alfabeto - majuskle kaj minuskle - kaj tiam simboloj kaj numeroj, ktp Tiam tie ni havas magian nombron identiganta Huffman-kodita dosiero. Ene de Huffman kodo ili tuj havi iun magia nombro asociita kun la kaploko. Tio povas aspekti simple hazarda magia nombro, sed se vi efektive traduki al ASCII, do ĝi reale hechizos el Huff. Jen ni havas struct por Huffman-kodita dosiero. Jen ĉiuj el tiuj karakterizaĵoj asociita kun Huff dosiero. Tiam cxi tie ni havas la kaplinio por Huff dosieron, do ni nomas ĝin Huffeader anstataŭ aldonante la ekstran h ĉar ĝi sonas la sama ĉiuokaze. Cute. Ni havas magian nombron asociita kun ĝi. Se temas pri efektiva Huff dosiero, ĝi tuj estos la nombro super, ĉi magio unu. Kaj tiam ĝi havos tabelo. Do por ĉiu simbolo, de kiuj estas 256, ĝi tuj printi kion la ofteco de tiuj simboloj estas ene de la Huff dosiero. Kaj poste fine, ni havas checksum por la frekvencoj, kiuj devus esti la sumo de tiuj frekvencoj. Do, tio estas kion oni Huffeader estas. Tiam ni havas iujn funkciojn kiuj revenos la venonta bito en la Huff dosieron tiel kiel skribas iom al la Huff dosiero, kaj tiam ĉi tiu funkcio ĉi tie, hfclose, ke efektive fermas la Huff dosiero. Antaŭe, ni pritraktas rekte nur fclose, sed kiam vi havas Huff dosiero, anstataŭ fclosing ĝin kion vi vere volas fari estas hfclose kaj hfopen ĝin. Tiuj estas specifaj funkcioj al la Huff dosierojn kiuj ni tuj estos pritraktas. Tiam tie ni legas en la kaplinio kaj poste skribi la kaploko. 

Nur legante la. H dosieron ni povas ia akiri senton de kia Huff dosiero povus esti, kio karakterizaj havas, sen reale iras en la huffile.c, kiu, se ni plonĝi en, tuj estos iom pli kompleksa. Ĝi havas ĉiujn de la dosiero en / el tie pritraktas punteros. Jen ni vidas ke kiam ni nomas hfread, ekzemple, ĝi estas ankoraŭ pritraktas fread. Ni ne liveri de tiuj funkcioj tute, sed ni sendas tiujn esti zorgo ene la Huff dosiero anstataŭ fari ĉiuj ĝin. Vi povas bonvolu skani tra ĉi se vi estas scivola kaj iru, kaj senŝeligi la mantelo reen iomete. 

La venonta dosiero por ke ni tuj rigardi estas tree.h. Antaŭe en la Walkthrough glitas ni diris nin atendas Huffman nodo kaj ni faris typedef struct nodo. Ni atendas havi simbolon, ofteco, kaj poste 2 nodo steloj. En ĉi tiu kazo kion ni faras estas ĉi estas esence la sama krom anstataŭ nodo ni iras por voki ilin arboj. Ni havas funkcion, ke kiam vi nomas fari arbo denove vi arbo puntero. Back al Speller, kiam vi estis farante novan nodon vi diris nodo * nova vorto = malloc (sizeof) kaj aĵoj tiel. Esence, mktree tuj estos pritraktas ke por vi. Simile, kiam oni volas forigi arbo, tiel ke tio esence liberigante la arbo, kiam vi faris per ĝi, anstataŭ eksplicite nomi liberaj sur tiu, vi vere nur tuj uzos la funkcio rmtree kie pasas en la puntero al tiu arbo kaj tiam tree.c prizorgos, ke por vi. 

Ni rigardas tree.c. Ni atendas la samajn funkciojn krom vidi la efektivigo tiel. Kiel ni atendis, kiam vi nomas mktree ĝin mallocs la grandeco de arbo en pointer, inicializa ĉiuj valoroj al la NULL valoron, do _0s_ aŭ NULLs, kaj poste redonas la puntero al tiu arbo, kiun vi ĵus malloc'd al vi. Jen kiam vi nomas forigi arbo ĝin unue certigas ke vi ne duobla liberigi. Ĝi certigas ke vi efektive havas arbo, kiun vi volas forigi. Ĉi tie, ĉar arbo inkludas ankaŭ liaj filoj, kion ĉi tio estas rekursie nomas forigi arbo sur la maldekstra vertico de la arbo tiel kiel la dekstra nodo. Antaŭ ol ĝi liberigas la patro, kiun ĝi bezonas por liberigi la infanojn tiel. Patro ankaŭ estas interŝanĝeblaj kun radiko. La unua patro, tiel kiel la granda-granda-granda-praavo aŭ avino arbo, unue ni devas liberigi laŭ la niveloj unua. Do trairi al la fundo, la libera tiuj, kaj tiam revenu supren, libera tiuj, ktp Do jen arbo. 

Nun ni rigardu arbaro. Arbaro estas kie vi metas ĉiujn viajn Huffman arboj. Oni diras, ke ni tuj havos iun nomita komploto kiu enhavas puntero al arbo tiel kiel puntero al komploto nomas proksima. Kio strukturo faras tian rigardon kiel? Ĉio diras ĝin tie. Ĝuste super tie. Al ligitaj listo. Ni vidas, ke kiam ni havas intrigo estas kiel ligitaj listo de intrigoj. Al arbaro estas difinita kiel ligitaj listo de bedoj, kaj tiel la strukturo de arbaro estas ni nur havos puntero al nia unua intrigo kaj ke intrigo havas arbo en ĝi aŭ pli ĝuste notas al arbo kaj poste notas al la sekvanta intrigo, tiel plu kaj tiel plu. Por fari arbaron ni nomas mkforest. Tiam ni havas vere utilaj funkcioj tie. Ni havas repreni kie pasas en arbaro kaj tiam la reveno valoro estas Arbo *, puntero al arbo. Kio fosilo faros estas ĝi iros en la arbaron, ke vi indikante tiam forpreni arbo kun la plej malalta ofteco de tiu arbaro kaj poste doni al vi la puntero al tiu arbo. Iam vi nomas repreni, la arbo ne ekzistas en la arbaro plu, sed la reveno valoro estas la puntero al tiu arbo. Tiam vi havas planton. Kondiĉe ke vi pasas en puntero al arbo kiu havas ne-0 ofteco, kio planto faros estas ĝi prenos la arbaro, prenu la arbo, kaj planto kiu arbo interne de la arbaro. Jen ni havas rmforest. Similaj forigi arbo, kiu esence liberigis ĉiuj niaj arboj por ni, forigi arbaro volo liberaj ĉio enhavis en tiu arbaro. 

Se ni rigardas forest.c, ni atendis vidi almenaŭ 1 rmtree komandon en tie, ĉar al libera memoro en la arbaro, se arbaro havas arbojn en ĝi, tiam eventuale vi tuj devos forigi tiujn arbojn tro. Se ni rigardas forest.c, ni havas niajn mkforest, kiu estas kiel ni atendis. Ni malloc aĵoj. Ni pravalorizi la unua argumento en la arbaro kiel NULL ĉar ĝi estas malplena por komenci, tiam ni vidos fosilo, kiu revenas al la arbo kun la plej malalta pezo, la plej malalta ofteco, kaj poste liveras de tiu aparta nodo ke poentojn al tiu arbo kaj la sekva, tial ĝi prenas tiun el la ligitaj listo de la arbaro. Kaj tiam tie ni havas planton, kiu enmetas arbo en la ligitaj listo. Kio arbaro ne estas bele subtenas ĝin ordo por ni. Kaj poste fine, ni havas rmforest kaj, kiel atendis, ni havas rmtree pregxis tie. 

Rigardante la dissendo kodo ĝis nun, huffile.c estis probable per malproksime la plej malfacila por kompreni, dum la aliaj dosieroj mem estis sufiĉe simpla sekvi. Kun nia kono de punteros kaj kunligita lertaj kaj tia, ni povis sekvi sufiĉe bone. Sed ĉiuj ni bezonas vere certigi ke ni plene komprenas estas la. H dosieroj ĉar vi bezonas esti nomante tiuj funkcioj, traktante kun tiuj reveno valoroj, tiel certigi ke vi plene komprenis kion ago tuj por ludado kiam ajn vi nomas unu el tiuj funkcioj. Sed reale kompreni ene de ĝi ne estas sufiĉe necesa ĉar ni havas tiujn. H dosierojn. Ni havas 2 pli dosierojn lasis en nia dissendo-kodo. 

Ni rigardu dump. Enjxetos por lia komento tie prenas Huffman-kunpremita dosiero kaj tiam tradukas kaj renversas ĉiuj ties enhavo eksteren. Jen ni vidas ke ĝi estas nomante hfopen. Tio estas speco de spegulon al dosieron * enigo = fopen, kaj tiam vi pasos en la informo. Estas preskaŭ identa escepte anstataŭ dosieron * vi pasante en Huffile; anstataŭ fopen vi pasante en hfopen. Ĉi tie ni legas en la kaplinio unua, kiu estas speco de simila al kiel ni legas en la kaplinio por bitmap dosiero. Kion ni faras ĉi tie estas kontrolanta vidi ĉu la kaplinion informoj enhavas la dekstra magia nombro kiu indikas ke temas pri efektiva Huff dosiero, tiam ĉiuj el ĉi tiuj kontroloj por certigi ke la dosiero kiun ni malfermitaj estas reala huffed dosiero aŭ ne. Kion ĉi tio estas eligas la oftecojn de ĉiuj el la simboloj kiuj povas vidi ene de terminalo en grafika tablo. Ĉi tiu parto tuj estos utila. Ĝi havas iom kaj legas iom post iom en la variablo iom kaj poste presas ĝin. Do se mi estus nomi dump sur hth.bin, kiu estas la rezulto de huffing dosieron uzante la bastonon solvo, mi akirus ĉi. Ĝi estas elirigi ĉiuj tiuj signoj kaj poste meti la ofteco je kiu ili aperas. Se ni rigardas, la plejparto de ili estas _0s_ krom por tio: H, kiu aperas dufoje, kaj tiam T, kiu aperas unufoje. Kaj tiam tie ni havas la reala mesaĝo en _0s_ kaj _1s_. Se ni rigardas hth.txt, kiu estas supozeble la originala mesaĝo kiu huffed, ni atendas vidi iujn Hs kaj Ts tie. Specife, ni atendas por vidi nur 1 T kaj 2 Hs. Jen ni estas en hth.txt. Ĝi ja havas HTH. Inkluzivita en tie, kvankam ni ne povas vidi gxin, estas linion karaktero. La Huff dosieron hth.bin ankaŭ kodi la linion karakteron tiel. Ĉi tie, ĉar ni scias ke la ordo estas HTH kaj poste linion, ni povas vidi ke probable la H estas reprezentita de nur sola 1 kaj tiam la T estas probable 01 kaj tiam la sekvanta H estas 1, tiel kaj poste ni havas linion indikita de du _0s_. Cool. 

Kaj poste fine, ĉar ni pritraktas multnombraj. C kaj. H dosieroj, ni havos belan kompleksa argumento al la tradukilo, kaj tiel tie ni havas Makefile kiu faras dump por vi. Sed reale, vi devas iri farante vian propran puff.c dosiero. La Makefile reale ne traktas farante puff.c por vi. Ni lasante ke ĝis vi redakti la Makefile. Kiam vi eniros en komando kiel fari ĉiuj, ekzemple, ĝi faros cxion por vi. Bonvolu rigardi la ekzemplojn de Makefile el la pasinteco pset tiel kiel pafante de ĉi tiu por vidi kiel vi eble povos fari vian Puff dosieron per redaktado ĉi Makefile. Tio pri ĝi por nia dissendo-kodo. 

Iam ni alvenas tra tiu, tiam tie estas nur alia memorigo pri kiel ni tuj estos pritraktanta la Huffman nodoj. Ni ne tuj estos nomante ilin nodoj plu; ni tuj estos nomante ilin arboj kie ni tuj estos reprezenti liajn simbolo kun char, ilia ofteco, la nombro de okazajxoj, kun entjero. Ni uzas tion ĉar ĝi estas pli preciza ol kaleŝego. Kaj tiam ni havas alian sagon al la maldekstra infano kaj ankaŭ la dekstra infano. Al arbaro, kiel ni vidis, estas nur ligillisto de arboj. Fine, kiam ni konstruas nian Huff dosiero, ni volas nian arbaro enhavi nur 1 arbo - 1 arbo, 1 radikon kun multnombraj infanoj. Antaŭe kiam ni nur faras nian Huffman arboj, ni komencis metante ĉiujn nodojn sur nia ekrano kaj dirante ni havos tiujn nodojn, eventuale ili tuj estos la folioj, kaj ĉi tiu estas lia simbolo, jen ilia ofteco. En nia arbaro, se ni nur havas 3 literoj, kiuj estas arbaraj de 3 arboj. Kaj poste kiam ni iru plu, kiam ni aldonas la unua patro, ni faris arbaro de 2 arboj. Ni forigis 2 el tiuj infanoj de nia arbaro kaj tiam anstataŭis ĝin per patro nodo kiu havis la 2 nodoj kiel infanoj. Kaj poste fine, nia lasta paŝo kun fari nian ekzemplon kun la mezuro, Bs, kaj C estus fari la fino patro, kaj tiel tiam kiu alportus nia tuta grafo de arboj en la arbaro al 1. Ĉu ĉiuj vidas, kiel vi starti evi multnombraj arboj en via arbaro kaj fini kun 1? Okay. Cool. 

Kion ni bezonas fari por Puff? Kion ni bezonas fari estas certiĝi ke, kiel ĉiam, ili donas al ni la rajton tipo de enigo por ke ni povas efektive uzi la programon. En ĉi tiu kazo tuj esti donante nin post ilia unua komando-linia argumento 2 pli: la dosiero kiu ni volas malkompaktigi kaj la eliro de la decompressed dosiero. Sed iam ni certigu ke ili pasas ni en la dekstra kvanton de valoroj, ni volas certigi ke la enigo estas Huff dosiero aŭ ne. Kaj poste iam ni garantias ke ĝi estas Huff dosiero, tiam ni volas konstrui nian arbon, konstrui la arbo tia, ke ĝi kongruas la arbo, ke la persono kiu sendis la mesaĝon konstruitaj. Tiam, post ni konstruas la arbo, tiam ni povas trakti la _0s_ kaj _1s_ ke ili pasis en, sekvi tiujn kune nian arbon ĉar ĝi estas identa, kaj poste skribu tiun mesaĝon ekstere, interpreti la bitoj denove en signoj. Kaj poste fine ĉar ni pritraktas punteros tie, ni volas certigi ke ni ne havas ajnan memoro fugoj kaj ke ni liberan ĉion. 

Certigante taŭga uzo estas malnova ĉapelo por ni nun. Ni prenu en enigo, kiu tuj estos la nomo de la dosiero al Puff, kaj poste ni specifi eligo, tial la nomo de la dosiero por la plenblovis eligo, kiu estos la teksta dosiero. Tio estas uzado. Kaj nun ni volas certigi ke la enmeto huffed aŭ ne. Pensante dorso, estis io en la dissendo kodo kiu povus helpi nin kun kompreni ĉu dosiero estas huffed aŭ ne? Estis informo en huffile.c pri la Huffeader. Ni scias ke ĉiu Huff dosiero havas Huffeader asociita kun ĝi kun magia nombro tiel kiel tabelo de la frekvencoj por ĉiu simbolo tiel kiel kontrolsumon. Ni scias tion, sed ni ankaŭ prenis travidi en dump.c, en kiu legis en Huff dosiero. Kaj tiel fari tion, ĝi devis kontroli ĉu ĝi vere estis huffed aŭ ne. Do eble ni povus uzi dump.c kiel strukturon por nia puff.c. Reen al pset 4 kiam ni havis la dosiero copy.c ke kopiita en RGB triopoj kaj ni interpretis ke por Whodunit kaj Regrandigi, simile, kion vi povus fari estas simple kuras la komandon kiel cp dump.c puff.c kaj uzi iun el la kodo tie. Tamen, ĝi ne tuj estos tiel rekta de procezo por traduki vian dump.c en puff.c, sed almenaŭ donas vin ie komenci pri kiel certigi ke la enigo estas reale huffed aŭ ne tiel kiel kelkaj aliaj aĵoj. Ni certigis ĝusta uzo kaj certigis ke la enmeto huffed. Ĉiufoje ke ni faris kion ni faris nia propra eraro kontrolanta, tiel reveni kaj lasi la funkcio se iu fiasko okazas, se estas problemo. 

Nun kion ni volas fari estas konstrui la reala arbo. Se ni rigardas en Arbaro, estas 2 ĉefaj funkcioj ke ni tuj volas fariĝi tre konanta. Jen la Bulea funkcio planto kiu plantoj ne-0 ofteco arbo interne nia arbaro. Kaj do vi pasas en puntero al arbaro kaj puntero al arbo. Rapida demando: Kiom da arbaroj vi havas kiam vi konstruas Huffman arbo? Nia arbaro estas kiel niaj tolo, ĉu ne? Do ni nur havos 1 arbaro, sed ni tuj havos multnombraj arboj. Do antaŭ ol vi nomas planto, vi supozeble tuj volas fari vian arbaron. Tie estas komando por ke, se vi rigardas en forest.h pri kiel vi povas fari arbaro. Vi povas planti arbon. Ni scias kiel fari tion. Kaj tiam vi ankaŭ povas elekti arbon el la arbaro, forigo arbo kun la plej malalta pezo kaj donas al vi la puntero al tio. Pensante reen al kiam ni faris la ekzemploj ni mem, kiam ni desegni gxin, ni simple nur aldonis la ligilon. Sed tie anstataŭ nur aldonante la ligiloj, pensi pri tio pli kiel vi forigo 2 el tiuj nodoj kaj tiam anstataŭante ĝin per alia. Por esprimi, ke en terminoj de pluki kaj planti, vi pluki 2 arboj kaj tiam plantante alia arbo kiu havas tiujn 2 arboj kiujn vi elektis kiel infanoj. Konstrui Huffman la arbo, vi povas legi en la simboloj kaj frekvencoj por ĉar la Huffeader donas ke al vi, donas tabelo de la frekvencoj. Do vi povas antaŭeniri kaj simple ignoras nenion kun la 0 en ĝi ĉar ni ne volas 256 folioj ĉe la fino de ĝi. Ni nur volas ke la nombro de folioj, kiuj estas gravuloj kiuj efektive uzata en la dosiero. Vi povas legi en tiuj simboloj, kaj ĉiu el tiuj simboloj, kiuj havas ne-0 frekvencoj, tiuj tuj estos arboj. Kion vi povas fari estas ĉiufoje kiam vi legis en ne-0 ofteco simbolo, vi povas planti tiu arbo en la arbaro. Kiam vi plantos la arbojn en la arbaro, vi povas aliĝi tiuj arboj kiel gefratoj, do tuj revenis al planti kaj pluki kie vi prenas 2 kaj tiam planto 1, kie tiu 1 kiu vi planto estas la patro de la 2 infanoj, kiun vi prenis. Do tiam via fina rezulto estas tuj estos sola arbo en via arbaro. Tiel estas kiel vi konstruos viajn arbo. 

Estas pluraj aferoj kiuj povus erari ĉi tie ĉar ni pritraktas fari novajn arbojn kaj pritraktas punteros kaj aĵoj tiel. Antaŭ kiam ni pritraktas punteros, ĉiufoje kiam ni malloc'd ni volis certigi ke ĝi ne revenos al ni NULL puntero valoro. Do en pluraj paŝoj ene de ĉi tiu procezo ne tuj estos pluraj kazoj kie estas via programo povus maltrafi. Kion vi volas fari estas vi volas certigi ke vi manipuli tiujn erarojn, kaj en la spec diras manipuli ilin gracie, tiel kiel presi mesaĝon al la uzanto diris al ili kial la programo devas quit kaj poste rapide forlasis ĝin. Por fari tion eraro uzado, memoru, ke vi volas kontroli ĝin ĉiun solan fojon ke povus esti fiasko. Ĉiu sola fojo ke vi faras nova puntero vi volas certigi ke tio sukcesis. Antaŭ kio ni uzas por fari estas fari novan puntero kaj malloc ĝin, kaj tiam ni devus kontroli ĉu tiu puntero estas NULL. Do tuj estos iuj kazoj, kie vi povas simple fari tion, sed kelkfoje vi fakte nomi funkcio kaj ene de tiu funkcio, tio estas la ke tio faras la mallocing. En tiu kazo, se ni retrorigardas al kelkaj el la funkcioj ene de la kodo, kelkaj el ili estas Bulea funkcioj. En la abstrakta kazo se ni havas Bulea funkcio nomita foo, esence, ni povas supozi ke, krom fari kion ajn foo faras, ĉar ĝi estas Bulea funkcio, ĝi revenas vera aŭ malvera - vera se sukcesa, malvera se ne. Do ni volas kontroli ĉu la reveno valoro de foo estas vera aŭ malvera. Se ĝi estas falsa, tio signifas ke ni tuj volas presi ian mesaĝon kaj tiam lasis la programo. Kion ni volas fari estas kontroli la reveno valoro de foo. Se foo revenas malvera, tiam ni scios, ke ni renkontis ian eraron kaj ni bezonas quit nia programo. Maniero por fari ĉi estas havi kondiĉo kie la reala funkcio mem estas via stato. Diru foo prenas en x. Ni povas havi kiel kondiĉon se (foo (x)). Esence, tio signifas, se fine de ekzekuti foo ĝi revenas vera, tiam ni povas fari ĉi tion ĉar la funkcio devas taksi foo por taksi la tuta kondiĉo. Tial jen kiel vi povas fari ion se la funkcio redonas vera kaj estas sukcesa. Sed kiam vi estas eraro kontrolanta, vi nur volas lasi se via funkcio redonas falsaj. Kion vi povus fari estas simple aldoni == malvera aŭ nur aldoni bang antaŭ ĝin kaj tiam vi havos if (! foo). Ene de tiu korpo de tiu kondiĉo vi havus ĉiujn eraro uzado, tiel kiel, "Ne povis krei tiun arbon" kaj tiam revenu 1 aŭ io kiel tio. Kion tio faras, tamen, estas ke kvankam foo revenis falsaj - Diru foo revenas vera. Tiam vi ne devas nomi foo denove. Tio estas komuna eraro. Ĉar estis en via kondiĉo, ĝi estas jam taksis, tiel vi jam havas la rezulton, se vi uzas fari arbo aŭ iu simila aŭ planto aŭ fosilo aŭ iu. Ĝi jam havas tiun valoron. Ĝi estas jam ekzekutita. Do ĝi estas utila por uzi Bulea funkcioj kiel la kondiĉo ĉar ĉu vi vere ekzekuti la korpon de la ciklo, ekzekutas la funkcio ĉiuokaze. 

Nia dua lasta paŝo estas skribi la mesaĝon al la dosiero. Iam ni konstruu la Huffman arbo, tiam skribi la mesaĝon al la dosiero estas bela simpla. Estas bela simpla nun nur sekvi la _0s_ kaj _1s_. Kaj tiel per konvencio ni scias ke en Huffman arbo la _0s_ indikas forlasis kaj la 1s indiki pravas. Se do vi legis en iom post iom, ĉiufoje ke vi ricevas 0 vi sekvu la maldekstra branĉo, kaj tiam ĉiu tempo vi legis en 1 vi tuj sekvu la dekstra branĉo. Kaj tiam vi tuj pluiri ĝis ili batis folio ĉar la folioj tuj estos fine de la branĉoj. Kiel ni povas distingi, ĉu ni batis folio aŭ ne? Ni diris ĝin antaŭe. [Studento] Se la punteros estas NULL. >> Jes. Ni povas diri se ni batis folio se la punteros al ambaŭ la maldekstra kaj dekstra arboj estas NULL. Perfekta. Ni scias, ke ni volas legi en iom post iom en niajn Huff dosiero. Kiel ni vidis antaŭe en dump.c, kion ili faris estas ili legis en iom post iom en la Huff dosieron kaj nur presas el kio tiuj bitoj estis. Ni ne tuj estos fari tion. Ni tuj faros iun kiu estas iom pli kompleksa. Sed kion ni povas fari estas ni povas preni ke iom da kodo kiu legas en la bito. Jen ni havas la entjera iom reprezentantaj la nuna iom, ke ni estas en. Tiu prizorgas ripetanta ĉiuj bitoj en la dosieron ĝis vi batis la fino de la dosiero. Bazita sur tiu, tiam vi tuj volas havi ian iterator tra viaj arbo. Kaj poste bazita sur ĉu la bito estas 0 aŭ 1, vi tuj volas ĉu movi ke iterator al la maldekstra aŭ movi ĝin al la dekstra tuta vojo ĝis vi batis folio, do la tuta vojo ĝis tiu nodo, ke vi estas en ne indikas plu nodoj. Kial ni povas fari tio kun Huffman dosiero sed ne Morsa kodo? Ĉar en Morsa kodo ekzistas iom da ambigueco. Ni povis esti kiel, oh atendas, ni batis leteron kune la vojon, do eble tio estas nia letero, dum se ni daŭre nur iom pli longe, tiam ni estus batis alia litero. Sed tio ne estas okazos en Huffman kodigo, do ni povas ripozi certigis, ke la sola maniero por ke ni tuj batis gravulo estas se tiu nodo la maldekstra kaj dekstra infanoj estas NULL. 

Fine, ni volas liberigi nian tutan memoron. Ni volas ambaŭ fermi la Huff dosiero ni estis kontraktanta kun tiel kiel forigi ĉiujn arbojn en nia arbaro. Bazita sur via efektivigo, vi probable tuj volas nomi forigi arbaro anstataŭ reale iras tra ĉiu el la arboj mem. Sed se vi faris neniun temporal arboj, vi volas liberigi tion. Vi konas vian kodo bona, do vi scias, kie vi atribuante memoro. Kaj do se vi eniros, starti per eĉ Kontrolo F'ing por malloc, vidante kiam vi malloc kaj certigante ke vi liberigi ĉiujn, ke sed tiam nur irante tra via kodo, kompreni, kie vi povus esti atribuitaj memoro. Kutime vi povus simple diri: "Je la fino de dosiero Mi nur tuj eltiros arbaro sur mia arbaro", do esence certe ke memoro, libera, ke, "Kaj tiam mi ankaŭ tuj fermi la dosieron kaj tiam mia programo tuj forlasis." Sed estas ke la sola tempo kiun via programo fermas? Ne, ĉar kelkfoje povus esti eraro, ke okazis. Eble ni ne povis malfermi dosieron aŭ ni ne povis fari alian arbon aŭ ia eraro okazis en la memoro atribuo procezo kaj tiel revenis NULL. Eraro okazis kaj tiam ni revenis kaj quit. Do tiam vi volas certigi ke iu ajn ebla tempo ke via programo povas quit, vi volas liberigi ĉiujn via memoro tie. Ĝi estas ne nur tuj estos en la fino de la ĉefa funkcio kiu vi quit vian kodon. Vi volas retrorigardas al ĉiu okazo, ke via kodo potenciale povus reveni antaŭtempe kaj poste liberaj ajn memoro havas sencon. Say vi vokis fari arbaro kaj kiu revenis falsaj. Tiam vi verŝajne ne bezonos forigi vian arbaro ĉar vi ne havas arbaro ankoraŭ. Sed ĉe ĉiu punkto en la kodo, kie vi povus reveni antaŭtempe vi volas certigi ke vi liberigi ajna ebla memoro. 

Do kiam ni pritraktas liberigi memoron kaj havante potencial fugoj, ni volas ne nur uzi nian juĝon kaj nia logiko sed ankaŭ uzi Valgrind por determini ĉu ni liberigxis ĉiuj niaj memoro adekvate aŭ ne. Vi povas aŭ kuri Valgrind sur Puff kaj tiam vi devas ankaŭ pasi ĝin dekstre numero de komand-linio argumentoj por Valgrind. Vi povas ruli tion, sed la eligo estas iom enigmaj. Ni alvenas iom uzata por ĝin per Speller, sed ni ankoraŭ bezonas iom pli da helpo, do tiam kurante ĝin kun kelkaj pli flagoj kiel la fugo-check = plena, ke verŝajne al ni iun pli helpema eligo sur Valgrind. 

Tiam alia utila tip kiam vi elpurigante estas la malsamoj komando. Vi povas aliri la bastonon de efektivigo de Huff, kuri, ke sur teksto-dosiero, kaj tiam Eligo ĝin al duuma dosiero, duuma Huff dosiero, por esti specifa. Tiam se vi kuros vian propran nubeto en tiu duuma dosiero, tiam ideale, via outputted teksta dosiero tuj estos identa al la originalo, kiun vi pasis in Jen Mi uzas hth.txt kiel la ekzemplo, kaj tio estas la raportis en via spec. Tio laŭvorte nur HTH kaj poste novan linion. Sed definitive sentas senpagaj kaj vi certe kuraĝigis uzi plu ekzemploj por via teksta dosiero. 

Vi povas eĉ preni ŝancon eble kunpremante kaj poste decompressing kelkaj el la dosieroj kiujn vi uzis en Speller kiel Milito kaj Paco aŭ Jane Austen aŭ io simila - kiu estus speco de cool - aŭ Austin Powers, speco de kontraktanta kun pli grandaj dosieroj ĉar ni ne malsupreniru, por ĝin se ni uzas la sekvanta ilo tie, ls-l. Ni uzis por LS, kiu esence listas ĉiuj enhavoj en nia aktuala dosierujo. Pasante en la flago-l reale montras la grandecon de tiuj dosieroj. Se vi iras tra la pset spec, ĝi reale marŝas vin tra kreante la duuma dosiero, de huffing ĝin, kaj vi vidos ke por tre malgrandaj dosieroj la spaco kosto de kunpremante ĝin kaj traduki ĉiujn tiun informon de ĉiuj frekvencoj kaj aliaj similaj ke kompensas la reala profito de kunpremante la dosieron en la unua loko. Sed se vi kuros ĝin sur iun plu tekstaj dosieroj, tiam vi eble vidas, ke vi komencu akiri profiton en kunpremante tiujn dosierojn. 

Kaj poste fine, ni havas niajn malnovajn pal GDB, kiu definitive tuj venos en oportuna ankaŭ. 

Ĉu ni havas demandojn sur Huff arboj aŭ la procezo eble de farante la arboj aŭ ajna alia demandojn sur Huff'n Puff? Okay. Mi restos ĉirkaŭrigardis por iom. 

Dankon, al ĉiuj. Tio estis Walkthrough 6. Kaj bona sorto. 

[CS50.TV]