[Powered by Google Translate] [Walkthrough - Problem Set 6] [Zamyla Chan - Harvard University] [To je CS50. - CS50.TV] 

Pozdravljeni, vsi, in dobrodošli potopis 6: Huff'n dim. V Puff Huff'n kar počnemo se bo ukvarja z datoteko Huffman stisnjenega in ga nato puhala nazaj, tako da simbolne, tako da bomo lahko prevesti iz 0s in 1s, da si nam pošilja in ga spremeniti nazaj v izvirno besedilo. Pset 6 se bo zelo kul, ker boste videli nekaj orodij , ki ste jih uporabili v pset 4 in 5 pset in vrsta jih združile v 1 zelo čeden koncept Ko pomislim na to. 

Prav tako verjetno, pset 4 in 5 sta najbolj zahtevna psets ki smo jih imeli v ponudbi. Torej od zdaj imamo to za več pset 1 v C-ju in nato po tem, da smo na spletnem programiranju. Torej sami čestitam za pridobivanje več najtežjih grba v CS50. 

Gremo naprej, za puff Huff'n, naše orodje za to pset se bodo Huffman drevesa, Tako razumevanje, ne samo, kako dvojiška drevesa delo, ampak tudi posebej Huffman drevesa, kako si izdelani ti. In potem bomo imeli veliko kode distribucije v tem pset, in bomo prišli pogledat, ki dejansko nekaj kode morda ne bomo mogli v celoti razumejo še, in tako bodo tisti, se je C slik., nato pa njihovih spremljevalcev h datoteke. nam bo dala dovolj razumevanja, da moramo tako, da vemo, kako te funkcije delujejo ali vsaj tisto, kar naj bi storil - njihovi vhodi in izhodi - tudi če ne vemo, kaj se dogaja v črni škatli ali ne razumejo, kaj se dogaja v črni škatli znotraj. In potem na koncu, kot ponavadi, smo se ukvarjajo z novimi podatkovnih struktur, Posebne vrste vozlišč, ki opozarjajo na nekatere stvari, in tako sem ob svinčnik in papir ne samo za proces oblikovanja in ko ste poskuša ugotoviti, kako bi morala delovati pset ampak tudi med razhroščevanje. Lahko imaš GDB poleg vaše pero in papir, medtem ko ste vzeli dol, kaj so vrednote, če vaše puščice obrnjene, in take stvari. 

Najprej si oglejmo dreves Huffman. Huffman drevesa so dvojiška drevesa, kar pomeni, da je vsako vozlišče ima le 2 otroka. V dreves Huffman značilnost je, da so najpogostejše vrednosti predstavljajo čim manj bitov. Videli smo v predavalnicah primerov Morse kode, ki je nekakšno konsolidiranih nekatere črke. Če ste poskušali prevesti A ali E, na primer, ste prevajanje, ki se pogosto, tako da namesto ob uporabi celoten sklop bitov dodeli za to običajno vrsto podatkov, ko jo stisnemo do manj, in potem te črke, ki jih zastopa, redkeje zastopane z več bitov ker si lahko privoščijo, da ko odtehta frekvenc, ki te črke na zaslonu. Imamo isto idejo tukaj na drevesih Huffman kjer smo se kar verige, vrste poti priti do nekaterih znakov. In potem so znaki, ki imajo največjo frekvenco se bodo zastopane s čim manj bitov. 

Tako, da si zgradi drevo Huffman je z dajanjem vseh znakov, ki se pojavljajo v besedilu in pogostost izračuna, kolikokrat se pojavijo. To je lahko bodisi število, kolikokrat ti črki sta ali morda odstotek od vseh likov, koliko vsak od pojavi. In kaj morate storiti, je, ko imaš vso to zarisano, potem poglej za 2 najnižjih frekvenc in potem se jim pridružijo kot bratje in sestre če pa starši vozlišče ima frekvenco, ki je vsota njegovih 2 otroka. In potem pravijo, da je po dogovoru levo vozlišče, sledite ki jih po 0 podružnico, in potem skrajno desno vozlišče je 1 podružnica. Kot smo videli v Morsejevi kodi, ena kavelj je, da če bi imeli samo piska in pisk je bil dvoumen. To bi lahko bil bodisi 1 črka ali pa bi se zaporedje 2 črk. In kaj Huffman drevesa pa je zato, ker po naravi znakov ali naši končni dejanska znakov kot zadnjega vozlišča na veji - smo se nanašajo na takšne, kot so listi - na podlagi, da ne more biti vse nejasnosti glede katerih črka, ki jo poskušate kodiranje s serijo bitov ker nikjer po bitov, ki predstavljajo 1 črko boste naleteli na še eno celo pismo, in da ne bo zmede obstaja. Ampak bomo šli v primerih, da lahko fantje videli, da dejansko namesto da bi nas samo povedal, da je to res. 

Oglejmo si preprost primer drevesa Huffman. Imam niz tukaj, ki je 12 znakov. Imam 4 Ker 6 BS in 2-jev. Moj prvi korak je, da računajo. Kolikokrat se pojavijo? Zdi se 4-krat v nizu. B se zdi, 6-krat in C se pojavi 2 krat. Seveda bom rekel, da sem z B najpogosteje zato želim, da zastopa B z najmanjšim številom bitov, najmanj pa število 0s in 1s. In potem sem tudi dogaja, da pričakujejo, C in zahtevajo največ znesek 0s in 1s, kot dobro. Prvo, kar sem storil tu sem jih dali v naraščajočem vrstnem redu glede na frekvence. Vidimo, da je C, in tistih, ki so naša 2 Najnižje frekvence. Ustvarjamo nadrejeno vozlišče, in da staršev vozlišče nima pismo, povezane z njo, vendar pa ima frekvenco, ki je vsota. Vsota postane 2 + 4, ki je 6. Nato sledimo levo vejo. Če smo bili v tistem 6 vozlišča, potem bi morali slediti 0 priti do C in nato 1 priti do A. Torej, zdaj imamo 2 vozlišč. Imamo vrednost 6 in potem imamo tudi eno vozlišče z vrednostjo 6. In tako so 2 niso le 2 najnižja pa tudi samo 2, ki so odšli, zato smo se pridružili tistim, ki jih drugi od staršev, pri čemer je vsota 12. Torej, tukaj imamo Huffman drevo če bi dobili na B, bi to samo se bit 1 in potem priti do ne bi imeli 01 C in nato ob 00. Torej, tukaj vidimo, da smo v bistvu kar te znakov z 1 ali 2 bitov kjer je B, kot je napovedano, ima najmanj. In potem smo se pričakuje, C so najbolj, ampak ker je tako majhno drevo Huffman, potem je tudi zastopnik 2 bitov za razliko nekje v sredini. 

Samo, da gredo na drugo preprost primer drevesa Huffman, da imate niz "Hello". Kaj morate storiti, je prvo, kar bi rekel, koliko krat se pojavi H v to? H pojavi enkrat in potem se pojavi, ko e in potem jaz ne pojavljajo dvakrat in o pojavlja enkrat. In tako potem pričakujemo, da bo pismo, ki naj bi ga najmanjšim številom bitov? [Študent] l. >> L. Ja. l je prav. Pričakujemo, da sem, da je zastopana z najmanjšim številom bitov ker sem se največ uporablja v nizu "Hello". Kaj sem storil sedaj se črpa iz teh vozlišč. Imam 1, ki je H in nato še 1, ki je e, nato pa je 1, ki je o - zdaj sem jih postavi v redu - in potem 2, ki je l. Potem sem rekel, da sem tako graditi drevo Huffman je najti 2 vozlišča z manj frekvencah in da jim bratje in sestre, ki jih ustvarja nadrejeno vozlišče. Tukaj imamo 3 vozlišč z najnižjo frekvenco. Oni so vsi 1. Torej, tukaj smo se odločili, katero bomo najprej povezati. Recimo, da izberejo H in e. Vsota 1 + 1 je 2, vendar to vozlišče nima pismo z njo povezana. Prav tako ima vrednost. Zdaj gledamo na naslednjih 2 najnižjih frekvenc. To je 2 in 1. To bi lahko bil eden od tistih, 2, vendar bom, da izberejo to. Vsota je 3. In potem končno, imam samo 2 levo, tako da potem postane 5. Potem pa sem, kot se pričakuje, če izpolnite kodiranje za to, 1s vedno pravico, podružnice in 0s sta leva. Potem imamo l, ki jo predstavlja le 1 bit in nato Õ 2 in potem e z 2 in nato H pade na 3 kose. Torej si lahko pošlje to sporočilo "Hello", namesto da dejansko uporabljate znake s samo 0 in 1s. Vendar ne pozabite, da v več primerih smo imeli stike z našo frekvenco. Lahko bi bodisi pridružil h in o, 1. morda. Ali pa kasneje, ko smo imeli l zastopa 2 kot tudi pridružil 1 2 zastopa, bi lahko povezan niti ena. 

In tako, ko pošljete 0s in 1s, ki dejansko ne zagotavlja da jo lahko prejemnik v celoti preberete sporočilo pravico off kij zato, ker ne bi vedeli, katere odločitev, ki ste jih naredili. Torej, ko imamo opravka s stiskanjem Huffman, Nekako moramo povedati prejemniku našega sporočila, kako smo se odločili - Morajo vedeti, kakšno dodatne informacije poleg sporočila stisnjen. Morajo razumeti, kaj drevo dejansko izgleda, kako dejansko so te odločitve. 

Tukaj smo samo delaš primere, ki se nanašajo na dejansko število, včasih pa lahko imate tudi drevo Huffman glede na frekvenco, pri kateri črki zdi se, da je popolnoma enak proces. Tukaj sem ga izrazil v zvezi z odstotki ali frakcij, in tako sem točno isto stvar. Se mi zdi 2 najnižja, ki jih povzamemo, naslednji 2 najnižja, ki jih povzamemo, dokler ne bom imel polno drevo. Čeprav smo lahko to storite tako ali tako, ko imamo opravka z odstotki, to pomeni, da smo tako stvari, ki se ukvarjajo z decimalk ali ne plava če razmišljate o podatkovnih strukturah glavo. Kaj vemo o plovci? Kaj je pogost problem, ko imamo opravka s plovci? [Študent] nenatančno aritmetično. >> Ja. Nenatančnost. Zaradi nenatančnosti plavajoče točke, za to pset, da poskrbimo, da da ne bomo izgubili nobene vrednosti, potem bomo dejansko dogaja, da se ukvarjajo s štetjem. Torej, če ste bili, da razmišljajo o vozlišča Huffman, če pogledaš nazaj v strukturi tukaj, če pogledaš na tiste zelene ima frekvenco povezano z njim kot tudi to kaže na vozlišče na njegovi levi, kot tudi vozlišče v njegovo pravico. In potem tisti rdeči pa tudi znak, povezane z njimi. Ne bomo narediti ločene tiste, za starše in nato končnih vozlišč, ki jo označujemo z listi, ampak bo samo še tiste vrednosti NULL. Za vsako vozlišče bomo imeli znak, simbol, da predstavlja vozlišče, nato frekvenco, kot tudi kazalec na njegovi levi otroka, kot tudi njegovo pravico otroka. Listi, ki so na samem dnu, bi tudi vozlišče napotke na svoji levi in ​​njihove pravice, ampak ker te vrednosti se ne kaže dejanskih vozlišč, Kaj bi njihova vrednost? >> [Študent] NULL. >> NULL. Točno tako. Tukaj je primer, kako lahko predstavlja frekvenco v plovci, ampak se bomo morali ukvarjati z njim s števil, tako da vse, kar sem storil, je spremeniti podatkovni tip tam. 

Gremo na bolj malo zapleteno primer. Toda zdaj, ko smo naredili preproste tiste, to je samo isti postopek. Boste našli 2 najnižje frekvence, povzamemo frekvenc in da je nova frekvenca vašega nadrejenega vozlišča, ki se potem kaže na njegovo levo z 0 vejo in pravice z 1 podružnice. Če imamo niz "To je cs50", potem pa preštejte, koliko krat je T omenjeno, h omenjeno, i, s, c, 5, 0. Torej, kaj sem naredil tukaj, je z rdečimi vozlišč sem zasajene, Rekel sem, da bom imel te znake sčasoma na dnu mojega drevesa. Tisti, ki se bodo vsi listi. Torej, kaj sem naredil je, da sem jih razporejene po pogostosti v naraščajočem vrstnem redu, in to je pravzaprav način, da to stori pset koda je jo razvrsti po pogostnosti in nato po abecedi. Torej ima številke in šele nato po abecedi glede na frekvenco. Torej, kaj želim storiti, je, jaz bi našli 2 najnižja. To je 0 in 5. Jaz bi jih sešteje, in to je 2. Potem sem nadaljeval, je bil naslednji 2 najnižja. To sta dve 1s, nato pa so postali 2, kot dobro. Zdaj vem, da je moj naslednji korak se bo pridružil najnižjo številko, ki je T, 1 in nato izberete eno od vozlišč, ki ima 2 s pogostnostjo. Torej, tukaj imamo 3 možnosti. Kaj bom naredil za diapozitiv je samo vizualno preurediti za vas tako da lahko vidite, kako sem ga izgradnji. Kaj je koda in vaša distribucija koda je storil, bi se pridružili T 1 z 0 in 5 vozlišče. Torej, da zneski do 3, nato pa bomo nadaljevali postopek. Cilj 2 in 2 zdaj so najnižje, tako da potem tisti znesek, do 4. Vsakdo po do sedaj? Ok. Potem, ko da imamo 3 in 3, ki jih je treba sešteti, zato še enkrat sem samo prehod, tako da lahko vidite vizualno, tako da ne preveč grdo. Potem imamo 6, nato pa naš končni korak je ta, da zdaj imamo samo 2 vozlišč povzamemo, da so bistva našega drevesa, kar je 10. In številka 10 je smiseln, saj vsako vozlišče predstavljeno, njihova vrednost, njihova pogostost število, je kolikokrat se je pojavil v nizu, in potem imamo 5 znakov v našem nizu, tako da ima smisel. Če si pa poglej kako bi se ga dejansko kodiranje, kot je bilo pričakovano, i in y, ki se pojavljajo najpogosteje so zastopane z najmanjšim številom bitov. 

Bodite previdni tukaj. V dreves Huffman primeru dejansko pomembno. Velika črka S se razlikuje od malimi črkami je. Če bi imeli "To je CS50" z velikimi črkami, potem male črke y bo prikazana samo dvakrat, bi bilo vozlišče z 2 kot svojo vrednost, potem pa velika črka S samo enkrat. Tako bo vaša drevesa spremeniti strukture, ker ste dejansko imajo dodatno krilo tukaj. Vendar bi vsota še vedno 10. To je tisto, kar smo dejansko dogaja, da se sklic checksum, dodajanje vseh pogledih. 

Zdaj, ko smo iz Huffman dreves, smo lahko potopite v Puff Huff'n je pset. Bomo začeli z delom vprašanj, in to se dogaja, da boste dobili navajeni, z binarnih dreves in kako deluje približno tako: risanje vozlišč, ustvarjanju lastne typedef struct za vozlišče, in videli, kako lahko vstavite v binarno drevo, tisti, ki je urejen, vozijo ga, in stvari, kot je ta. To znanje bo zagotovo vam pomaga, ko se potopite v delu Puff Huff'n v pset. V standardni izdaji pset, vaša naloga je izvajanje Puff, in v različici hacker vaša naloga je izvajanje Huff. Kaj Huff pa je potrebno besedilo in nato jo z drugimi besedami pomeni 0s in 1s, tako da je proces, ki smo to naredili zgoraj, kjer smo našteli frekvenc nato pa je drevo, nato pa je rekel: "Kako dobim T?" T predstavlja 100, take stvari, in potem bi Huff se besedilo, nato pa izhod, ki binarno. Pa tudi zato, ker vemo, da želimo, da bi naše prejemnika sporočila da ponovno natančno isto drevo, vključuje tudi podatke o pogostosti razlogov. Nato s Puff smo dobili binarno datoteko 0s in 1s in glede na to tudi podatke o frekvencah. Prevajamo vse tiste 0s in 1s nazaj v izvirno sporočilo, da je bil, tako da smo simbolne to. Če delaš Standard Edition, vam ni treba izvajati Huff, tako, potem lahko preprosto uporabite kadrovske izvajanje Huff. Obstajajo navodila v določilu o tem, kako to storiti. Lahko zaženete zaposlenih izvajanje Huff o posameznem besedilno datoteko in nato uporabite, da izhod v vaš prispevek k Puff. 

Kot sem že omenil, imamo veliko kode distribucije za to. Jaz bom za začetek šel skozi to. Jaz grem, da preživijo večino časa na. H datoteke saj v datotekah. C, ker imamo. H in da nam daje s prototipi funkcij, ne bomo v celoti treba natančno razumeti - Če ne razumete, kaj se dogaja v datotekah. C, potem ne skrbi preveč, ampak definitivno poskusil, da si ogledate, saj lahko to daje nekaj namigov in to je koristno, da se privadite branje kodo drugih ljudi. 

Če pogledamo huffile.h, v komentarjih razglasi plast abstrakcije za Huffman kodiranimi datotekami. Če gremo, smo videli, da je največ 256 znakov, ki bi jih potrebovali kode za. To vključuje vse črke abecede - velikih in malih - in potem simboli in številke, itd Potem imamo tukaj magično številko je navedla Huffman označenih datoteko. V kodeksu Huffman, da boš imela določeno število čarobno povezano z glavo. To bi izgledal zgolj naključno magično številko, če pa dejansko prevesti v ASCII, nato pa je dejansko opredeljuje Huff. Tukaj imamo struct za Huffman kodirani datoteki. Tam je vse te značilnosti, povezane z datoteko Huff. Potem tukaj imamo glavo datoteke Huff, zato pravimo, da Huffeader namesto da bi dodali dodatno h, ker zveni nekako enako. Lepe. Imamo magično število, povezano z njim. Če je dejanska slika Huff, da se bo število tam zgoraj, to čarobno 1. In potem bo dobil niz. Torej za vsak znak, ki je 256, da se bo seznam, kaj je pogostost teh simbolov so v datoteki Huff. In potem končno, imamo checksum za frekvencah, ki bi morala biti vsota teh frekvencah. Tako da je tisto, kar je Huffeader. Potem imamo nekaj funkcij, ki vrnejo naslednji bit v datoteki Huff kot piše malo jezen na datoteko, nato pa ta funkcija tukaj, hfclose, ki dejansko arhivira Huff. Pred tem smo imeli opravka z ravno prav fclose, ko pa imate datoteko Huff, namesto da bi jo fclosing kaj ste dejansko storili, je hfclose in ga hfopen. Tisti, ki so določene naloge do datotek Huff, da bomo v stiku s. Potem tukaj beremo v glavo, nato pa pisati glavo. 

Samo z branjem h datoteko. Bomo lahko nekako dobili občutek, kaj bi lahko bilo datoteka Huff, katere lastnosti ima, ne da bi se dejansko dogaja v huffile.c, ki bo, če bomo potopili, se bo malo bolj zapletena. Ima vse datoteke I / O obravnavamo kazalca. Tukaj vidimo, da ko smo klic hfread, na primer, je še vedno ukvarjajo z fread. Ne bomo znebili teh funkcij v celoti, vendar vam pošiljamo tistim, ki so poskrbeli znotraj datoteke Huff, namesto da delaš vse to mi sami. Lahko vas prosimo, da skandirati skozi to, če ste radovedni in pojdi in olupite plasti nazaj malo. 

Naslednja slika, da bomo gledati, je tree.h. Preden v Walkthrough vodili smo rekli, pričakujemo Huffman vozlišče in smo se typedef struct vozlišče. Pričakujemo, da ima simbol, se pogostost in nato 2 vozlišča zvezde. V tem primeru, kar počnemo, je to v bistvu enak razen namesto vozlišča bomo jim pravimo drevesa. Imamo funkcijo, ko pokličeš, da je drevo vrne vam drevo kazalec. Nazaj na speller, ko ste bili kar novo vozlišče si rekel vozlišče * Nova beseda = malloc (sizeof) in take stvari. V bistvu, mktree se bo obravnava za vas. Podobno, če želite odstraniti drevo, tako da je v bistvu sprostitev drevo, ko ste storili z njim, Namesto izrecno poziva brezplačno, da ste dejansko šele tekoč, da uporabite funkcijo rmtree če se boste peljali v kazalec na tisto drevo, nato pa se bo tree.c poskrbel za to za vas. 

Upamo, da bomo v tree.c. Pričakujemo, da bodo iste funkcije, razen za ogled izvajanja, kot tudi. Kot smo pričakovali, ko ste klic mktree je mallocs velikost drevesa v kazalcem inicializira vse vrednosti na NULL vrednosti, tako da 0s ali ničel, in nato vrne kazalec na tisto drevo, ki ste jo pravkar malloc'd za vas. Tukaj, ko pokličete odstraniti drevo najprej poskrbi, da ne boš dvojno osvoboditev. To zagotavlja, da ste dejansko imajo drevo, ki ga želite odstraniti. Tukaj ker drevo tudi svoje otroke, kaj pa je to rekurzivno zahteva odstranitev drevesa na levem vozlišču drevesa kot pravi vozlišča. Preden se osvobaja od staršev, je potrebno sprostiti otroke, kot tudi. Matično tudi zamenljiv z root. Prvo od staršev, tako kot pra-pra-pra-pradedek ali babica drevo, moramo najprej osvoboditi določitvi stopnje najprej. Torej prečkala do dna, brez tistih, potem pa pridi nazaj gor, brez tistih, itd Torej, to je drevo. 

Zdaj gledamo na gozd. Gozd je, če jih postavite vse vaše dreves Huffman. To je rekel, da bomo imeli nekaj pozval plot , ki vsebuje kazalec na drevo, kot tudi kazalec na parceli, imenovano drugo. Kaj struktura pa takšno videti? Nekako piše tam. Tukaj. Povezani seznam. Vidimo, da je, ko imamo parcelo je kot povezan seznam parcel. Gozdov je opredeljena kot povezan seznam parcel, in tako je struktura gozda smo le, da bo imel kazalec na prvo parcelo in da je parcela ima drevo v njej ali ne kaže na drevesu in nato opozarja na naslednje parcele, tako naprej in tako naprej. Če želite gozd pravimo mkforest. Potem imamo nekaj zelo uporabnih funkcij tukaj. Imamo izbrati, če se boste peljali v gozd in se nato vrne vrednost je drevo * kazalec na drevo. Kaj izbor bo naredil, je, da bo šel v gozd, da ste kar kaže na nato odstranite drevo z najnižjo frekvenco od tega gozda in potem vam kazalec na drevesu. Ko kličete kramp, drevo ne bo, v gozdu več, vendar je donosnost vrednost je kazalec na drevesu. Potem imate napravo. Pod pogojem, da se boste peljali v kazalec na drevo, ki ima non-0 frekvenco, kaj bo naredil obrat je bo v gozd, da drevo, in rastlin, da drevo v notranjosti gozda. Tukaj imamo rmforest. Podobno odstraniti drevo, ki v bistvu osvobodite vseh naših dreves za nas, odstrani gozd bo osvobodil vse vsebuje ta gozd. 

Če se ozremo v forest.c, bomo pričakujemo, da bo vsaj 1 rmtree ukaz tam, ker prostega pomnilnika v gozdu, če ima gozd drevesa v njem, nato pa na koncu boste morali odstraniti drevesa, preveč. Če se ozremo v forest.c, imamo mkforest, ki je, kot smo pričakovali. Mi malloc stvari. Mi inicializirati 1. parcelo v gozdu za nično, ker je prazen na začetku, potem vidimo, kramp, ki vrne drevo z najmanjšo težo, kar je najnižja pogostost, in potem znebil tega določenega vozlišča, ki kaže na to drevo in naslednji 1, zato meni, da je iz povezanega seznama gozda. In tukaj imamo tovarno, ki dodaja drevesa v povezanem seznamu. Kaj gozd pa je lepo ohranja razporejene za nas. In potem končno, imamo rmforest in, kot se pričakuje, imamo rmtree pozval tam. 

Če pogledamo na distribucijskem kodo tako daleč, huffile.c je verjetno daleč najtežje razumeti, ker druge datoteke, sami so bili zelo enostavno slediti. Z našim znanjem in povezanih kazalcev seznamov in take, smo lahko spremljali zelo dobro. Toda vse, kar potrebujete, da bo res poskrbeti, da bomo popolnoma razumeli je H datotek. ker je treba kliče tiste funkcije, ki se ukvarjajo s temi izračunani vrednosti zato poskrbite, da boste popolnoma razumeli, kakšne ukrepe bo treba opraviti ko pokličete eno od teh funkcij. Ampak dejansko razumevanje znotraj njega ni ravno potrebno, ker smo jih. H datotek. Imamo še 2 datotek ostane v našem distribucijskem kodo. 

Oglejmo si smetišču. Smetišče s svojim komentarjem sem vzame Huffman stisnjen datoteko in nato prevaja in stresa vse njene vsebine ven. Tukaj vidimo, da kliče hfopen. To je nekako zrcali v datoteko * vhodne = fopen, in potem preide v vednost. To je skoraj enaki, razen namesto datoteke * ti, ki poteka v Huffile; namesto fopen ste potujejo hfopen. Tukaj smo brali v glavo prvi, ki je nekako podobno, kako beremo v glavi za datoteke bitnih. Kaj delamo tukaj se preverjali, ali so informacije v glavi vsebuje pravo magično številko, ki nakazuje, da je dejanska slika Huff, Nato vse te preglede, da se prepriča, da je dokumentacija, ki smo odprti, je dejanska huffed datoteke ali ne. Kaj to je oddaja frekvence vseh simbolov, ki jih lahko vidimo v terminalu v grafični tabeli. Ta del se bo koristen. To je malo in se glasi bit by bit v spremenljivki bit in ga natisne. Torej, če sem bil, da pokličete na smetišče hth.bin, ki je posledica huffing datoteko s pomočjo kadrovske rešitve, bi to dobil. To je prikazovanje vseh teh znakov in nato dajanje frekvenco, pri kateri se pojavi. Če pogledamo, večina od njih so 0s, razen to: H, ki se pojavi dvakrat, in nato T, ki se pojavi enkrat. In tukaj imamo dejansko sporočilo v 0s in 1s. Če pogledamo hth.txt, ki je menda izvirno sporočilo, da je bil huffed, pričakujemo, da bomo videli nekaj HS in TS tam. Natančneje, pričakujemo, da bomo videli samo 1 in 2 T HS. Tu smo v hth.txt. V resnici se je HTH. Gostje imajo tam, čeprav ne moremo videti, je znak za novo vrstico. Datoteka Huff hth.bin tudi kodiranje znak za novo vrstico, kot dobro. Tukaj, saj vemo, da je za HTH in nato v novo vrstico, lahko vidimo, da verjetno predstavlja H z enim samim 1 in potem je verjetno T 01 in potem naslednji H 1, kakor tudi in potem imamo novo vrstico navede z dvema 0s. Kul. 

In končno, ker imamo opravka z več c. In. H datoteke, da bomo imeli precej kompleksen argument prevajalnik, in zato imamo tukaj Makefile, ki omogoča smetišče za vas. Toda v resnici, boste morali iti na izdelavo lastne puff.c datoteko. Datoteka Makefile dejansko ne ukvarja z izdelavo puff.c za vas. Odhajamo, da je do vas, da uredite Makefile. Ko vnesete ukaz, kot da bi vse, na primer, se bo vse od njih za vas. Vas prosimo, da pogled na primere Makefile iz preteklih pset kot tudi zletel tega eno, kako boste morda lahko, da bo vaše Puff datoteko z urejanjem tega Makefile. To je vse za našo distribucijsko kode. 

Ko smo gotten skozi vse to, potem tukaj je samo še en opomin o tem, kako se bomo morali ukvarjati z vozlišči Huffman. Ne bomo se jim kliče vozlov več, da bomo lahko kličem jim drevesa kjer bomo predstavljali svoj simbol s char, njihova pogostost, število dogodkov, s celo število. Mi smo z uporabo, ker je bolj natančna kot likvidna sredstva. In potem imamo še eno kazalec na levi otrok, kot tudi pravico otroka. Gozdov, kot smo videli, je le povezani seznam dreves. Konec koncev, če bomo izgradnji naše Huff datoteko želimo, da naši gozdovi, da vsebuje samo 1 drevo - 1 drevo, 1 koren z več otroki. Prej, ko sva samo, da naše Huffman dreves, smo začeli s postavitvijo vseh vozlišč na našem zaslonu in pravi, da bomo imeli teh vozlišč, na koncu so si bo listi, in to je njihova simbol, to je njihova pogostost. V našem gozdu, če imamo samo 3 črke, da je gozd 3 dreves. In potem, ko gremo naprej, ko smo dodali prvo staršev, smo naredili gozd 2 dreves. Odstranili smo 2 teh otrok iz našega gozda in jo nadomestiti z matično vozlišču da je imela ta 2 vozlišč, kot otrok. In potem končno, naš zadnji korak z izdelavo naš primer z AS, BS in Cs bi bilo, da bi končno staršev, in tako potem bi to lahko naša skupna števila dreves v gozdu v 1. Ali vsi videli, kako ste začeli z več dreves v svojem gozdu in na koncu z 1? Ok. Kul. 

Kaj moramo storiti za Puff? Kaj moramo storiti, je zagotoviti, da se, tako kot vedno, so nam pravo vrsto vnosa tako da bomo lahko dejansko zagnati program. V tem primeru se bomo, da se nam daje po prvi argument v ukazni vrstici Še 2: slika, da želimo raztezanje in proizvodnja raztegne datoteko. Toda, ko bomo poskrbeli, da so nas prehaja v pravo mero vrednosti, želimo zagotoviti, da bo vnos je datoteka Huff ali ne. In potem, ko bomo zagotovili, da je datoteka Huff, nato pa želimo zgraditi naše drevo, zgraditi drevo tako, da se ujema z drevesa, da oseba, ki je poslal sporočilo zgrajena. Potem, ko smo zgradili drevo, potem lahko imamo opravka z 0 in 1s, da sta se srečala na, ravnajo po našem drevesu, ker je enaka, nato pa napisali, da je sporočilo jasno, razlagajo bitov nazaj v znakov. In potem na koncu, ker imamo opravka z kazalci tukaj želimo zagotoviti, da nimamo nobenih spomin razpoka in da smo brez vsega. 

Zagotavljanje pravilne uporabe je star klobuk za nas do sedaj. Mi v vložek, ki se bo ime datoteke za napihniti, nato pa določite izhod, tako ime datoteke za proizvodnjo škroba v prahu, ki bo besedilna datoteka. To je navada. In zdaj smo želeli zagotoviti, da se vnos huffed ali ne. Thinking nazaj, je bilo še kaj v distribucijski kodo, da bi nam pomagali z razumevanjem, ali je datoteka huffed ali ne? Ni bilo informacij v huffile.c o Huffeader. Vemo, da ima vsaka datoteka Huff je Huffeader z njim povezan s čarobno številko kot tudi niz frekvenc za vsak znak kot tudi vsote. Vemo, da je, ampak tako je pokukati v dump.c, , v katerem je bilo branje v datoteko Huff. In so za to, da se je morala preveriti, ali je bilo res huffed ali ne. Torej, morda bi lahko uporabili dump.c kot strukturo za naše puff.c. Nazaj na pset 4, ko smo imeli datoteke copy.c da kopirali v trojic RGB in mi razlaga, da je za Whodunit in velikost, Podobno je, kaj lahko narediš, samo zaženite ukaz cp, kot dump.c puff.c in uporabi nekaterih kodeksa tam. Vendar pa to ne bo tako enostavno procesa za prevajanje vašega dump.c v puff.c, ampak vsaj vam daje nekje začeti o tem, kako zagotoviti, da se vnos dejansko huffed ali ne kot tudi nekaj drugih stvari. Smo zagotoviti pravilno uporabo in zagotoviti, da se huffed vnos. Vsakič, ko smo naredili, da smo naredili našo pravilno preverjanje napak, Tako vračanje in zapustil funkcijo, če pride do izpada nekaterih, če je to problem. 

Zdaj, kaj želimo storiti, je graditi dejanski drevo. Če se ozremo v gozdu, so 2 glavne naloge da bomo želeli postati zelo pozna. Tam je logično funkcijo rastlin, da rastline, ki niso 0 frekvenca dreves v naših gozdov. In tako se podaš v kazalec v gozd in je kazalec na drevo. Hitro vprašanje: Koliko gozdovi boste imeli, ko ste izgradnjo drevo Huffman? Naš gozd je kot naša platna, kajne? Torej smo le, da bo še 1 gozd, pa bomo imeli več dreves. Torej, preden pokličete napravo, ste verjetno boš želel, da bi svoj gozd. Tukaj je ukaz za to, če pogledaš na forest.h o tem, kako si lahko gozd. Lahko posadi drevo. Vemo, kako to storiti. In potem si lahko tudi izberete drevo od gozda, odstranitev drevesa z najmanjšo težo in vam daje kazalec na to. Thinking nazaj, ko smo delali od primerov sebe, Ko smo jo črpa, preprosto le dodal povezav. Ampak tukaj, namesto da bi ga zgolj dodajanje povezav si o njej mislijo več, kot ste odstraniti 2 teh vozlišč in jo zamenjati z drugo. Če želite izraziti, da je glede na obiranje in sajenje boš pobiral 2 dreves in nato sajenje drugo drevo da ima ta 2 drevesa, ki ste ga izbrali kot otroci. Za izgradnjo drevo Huffman, si lahko preberete v simbole in frekvenc, da bi ker Huffeader omogoča, da za vas, vam niz frekvenc. Torej, lahko greš naprej in kar ignorirati vse, kar z 0 v njem saj ne želimo, 256 listov na koncu od tega. Mi samo želimo število listov, ki so znaki , ki se dejansko uporabljajo v spisu. Si lahko preberete na teh simbolov in vsak od teh simbolov, ki imajo od 0 frekvenc, ki se bodo drevesa. Kaj lahko storite, je vsakič, ko boste brali v tretji 0 simbol frekvence lahko posadili to drevo v gozdu. Ko boste posadili drevesa v gozdu, se lahko pridružite drevesa, kot bratje in sestre, tako vrača v sajenje in nabiranje, kjer izberete 2 in nato rastlina 1, če je ta 1, ki ga je matična rastlina od 2 otroka, ki ste ga izbrali. Torej vaš končni rezultat pa bo eno drevo v svojem gozdu. To je, kako si zgraditi drevo. 

Obstaja nekaj stvari, ki bi lahko gredo narobe saj imamo opravka z izdelavo novih dreves in se ukvarjajo s kazalci in takih stvari. Pred ko smo se ukvarjajo s kazalci, ko smo malloc'd smo želeli, da se prepričajte, da ni vrnil nam NULL vrednost kazalca. Torej v več korakih v tem procesu pa se bodo več primerov če bi tvoj program ne uspe. Kaj želite storiti, je, da želite poskrbite, da boste obravnavo teh napak, in v spec pravi, da jih obravnava elegantno, tako rad izpisal sporočilo uporabniku jim poveste, zakaj je program mora prenehati in potem takoj nehaj. Za to napako ravnanje, ne pozabite, da želite to preveriti vsak čas, da bi lahko prišlo do okvare. Vsakič, da delate nov kazalec želite prepričati, da je to uspešen. Preden kaj smo narediti je, da nov kazalec in malloc it, in potem bi morali preveriti, ali je ta kazalec NULL. Torej se bodo nekateri primeri, kjer si lahko storite, da se ampak včasih ste dejansko kliče funkcijo in v tej funkciji, to je tisti, ki je početje mallocing. V tem primeru, če se ozremo nazaj na nekatere funkcije v kodi, nekateri od njih so Boolove funkcije. V abstraktnem primeru, če imamo logično funkcijo imenovano foo, v bistvu, lahko sklepamo, da poleg počnete karkoli foo ne, saj je logično funkcijo, vrne resnična ali neresnična - Res če bo uspešen, če ne lažno. Zato smo želeli preveriti, ali je vrnitev vrednost foo resnična ali neresnična. Če je napačna, to pomeni, da bomo želeli natisniti nekakšno sporočilo in zaprite program. Kaj želite storiti, je preveriti vrnjeno vrednost foo. Če foo vrne false, potem vemo, da smo naleteli na kakšno napako in moramo zapustiti naš program. Način za to je, da imajo bolezen, če je dejansko funkcija sama vaše stanje. Povejte foo se v x. Mi lahko kot pogoj, če (foo (x)). V bistvu to pomeni, če na koncu foo izvršitve se vrne res, potem lahko to storimo, ker funkcija mora oceniti foo da bi ocenila celotno stanje. Torej to je, kako lahko naredite nekaj, če funkcija vrne true in je uspešen. Toda, ko ste preverjanje napak, lahko le želeli zapustiti, če je vaša funkcija vrne false. Kaj lahko storite, je le dodati == false ali pa dodate pok pred njim in potem boste morali, če (! foo). Znotraj tega organa tega pogoja bi morali vse napake ravnanje, Tako kot, "Ne morem ustvariti to drevo" in se nato vrne 1 ali kaj podobnega. Kaj to naredi, pa je, da čeprav se vrne false foo - Povejte foo vrne true. Potem ti ni treba poklicati foo znova. To je skupna napačno. Ker je bilo v tem stanju, je to že ocenila, tako da že imate rezultat, če boste uporabljali, da drevo ali kaj podobnega ali rastlin ali kramp ali kaj podobnega. Je že to vrednost. To je že izvršena. Torej je smiselno uporabiti logičnih funkcij kot pogoj saj to, ali ste dejansko izvaja telo zanke, ga izvede funkcijo anyway. 

Naš predzadnji korak je pisno sporočilo v datoteko. Ko gradimo drevo Huffman, nato pa s pisanjem sporočila v spis je precej preprosta. To je zelo enostavno zdaj, da sledite 0 in 1s. In tako je po dogovoru vemo, da je na drevesu Huffman kažejo zapustil 0s in 1s kažejo prav. Torej, če ste prebrali v bit by bit, vsakič, ko boste dobili 0 boste sledili levo vejo in nato vsakič, ko boste brali v 1 boste sledili pravo vejo. In potem si bomo še naprej, dokler ne zadeti listov ker se listi se bodo na koncu veje. Kako lahko poveste, ali smo zadeli listov ali ne? Uspelo nam je povedal. [Študent] Če so kazalci NULL. >> Ja. Mi lahko poveste, če smo zadeli liste, če so kazalci tako levi in ​​desni dreves so NULL. Popolno. Vemo, da želimo brati malo po malo v našo datoteko Huff. Kot smo videli prej v dump.c, kaj so naredili, je, da bere malo po malo v datoteko Huff in samo natisnjene, kaj ti je bilo bitov. Ne bomo se s tem. Bomo, da se delaš nekaj, kar je malce bolj zapletena. Toda kaj, kar lahko storimo je, da smo lahko, da delček kode, ki se glasi, da bi bit. Tukaj imamo celo število, ki predstavlja sedanjo bit bit, da smo. Ta skrbi za ponavljanjem vseh bitov v spisu, dokler ne dosežete konec datoteke. Na podlagi tega, potem boste želeli imeti nekakšno iterator za prečkanje drevo. In potem glede na to, bit 0 ali 1, boste želeli niti premakniti iterator na levi ali ga premaknete v desno do konca, dokler ne boste zadeli list, tako da vse do vozlišča, ki ste na ne kaže, da vse več vozlišč. Zakaj lahko to storimo z datoteko Huffman, vendar ne Morse kode? Ker v Morse code tam je malo dvoumnosti. Lahko bi bilo všeč, oh čakati, smo zadeli pismo vzdolž poti, tako da morda je to naša pismo, ker če bomo še naprej le malo dlje, bi potem smo zadeli še eno pismo. Ampak to se ne bo zgodilo kodiranja Huffman, tako da bomo lahko prepričani, da je edini način, da bomo zadeli značaja je, če vozlišča na levi in ​​desni so otroci NULL. 

Na koncu želimo, da osvobodi vse našem spominu. Želimo, da tako blizu spis Huff, da smo se ukvarjajo z kot tudi odstraniti vse dreves v našem gozdu. Glede na vaše izvajanje, ste verjetno boš želel poklicati odstraniti gozd namesto da bi dejansko šel skozi vse drevje sami. Ampak, če ste naredili kakršne koli začasne dreves, boste želeli, da osvobodi. Veš kodo najboljši, tako da boste vedeli, kje ste dodeljevanju pomnilnika. In tako, če greš v, najprej celo nadzor F'ing za knjižnične funkcije malloc, videli, ko boste malloc in pazite, da osvobodi vse, ki potem pa šele skozi svojo kodo, razumevanje, če ste morda dodeliti pomnilnika. Ponavadi bi si rekel: "Na koncu datoteke grem odstraniti gozd na moj gozd" tako da v bistvu jasno, da spomin, brez, da «In potem sem tudi dogaja, da se spis in nato moj program se bo nehal." Vendar pa je, da je edini čas, da vaš program zapre? Ne, ker bi včasih ni bilo napaka, ki se je zgodilo. Mogoče ne bi mogli odpreti datoteko ali ne bi mogli narediti še drevo ali neke vrste napake se je zgodilo v postopku dodeljevanja pomnilnika, zato se je vrnil NULL. Napaka se je zgodilo in potem smo se vrnili in zaprete. Torej hočeš prepričati, da se morebitni čas, da se vaš program zapre, hočeš, da osvobodi vse spominu tam. To ni samo bo na koncu glavne funkcije, ki jo zaprete kodo. Hočeš, da se ozremo v vsakem primeru, da bi vaša koda lahko vrnili predčasno in nato brez spomina ne glede na smisel. Povejte so vabljeni, da gozd in da se vrne false. Potem verjetno ne boste potrebovali, če želite odstraniti gozd ker nimate gozd še ni. Ampak na vsaki točki v kodi, kjer bi lahko vrnete prezgodaj želite poskrbite, da boste sprostili morebitno spomin. 

Torej, ko imamo opravka s sprostitvijo pomnilnika in ob potencialnih lukenj, želimo ne le uporabite našo presojo in naš logiko temveč tudi za uporabo Valgrind ugotoviti, ali smo osvobojeni vseh našem spominu pravilno ali ne. Lahko deluje na Valgrind Puff, potem pa moraš tudi dajati Pravica število argumentov v ukazni vrstici, da Valgrind. Lahko bežiš, ampak rezultat je nekoliko skrivnosten. Smo gotten malo uporablja, da je z speller, vendar še vedno potrebujemo malo več pomoči, Tako potem teče z nekaj več zastav, kot puščanja preverite = celoti, , da bo verjetno, da nam nekaj več koristnih izhod na Valgrind. 

In še koristen namig, ko ste razhroščevanje je ukaz diff. Lahko dostop do izvajanja osebja, ki je v Huff, ki delujejo na besedilno datoteko, in ga nato vnese v binarno datoteko, binarni Huff datoteke, ki je specifična. Potem, če vodijo svojo lastno dim na tej binarne datoteke, potem pa najbolje, vaš izhodni besedilna datoteka, se bo enako s prvotnim tistega, ki ga opravili noter Tukaj sem z hth.txt kot primer, in to je ena govorila v vašem spec. To je dobesedno samo HTH in nato vrstico. Ampak zagotovo počutili svobodne in ste zagotovo spodbuja k uporabi daljših primere za besedilni datoteki. 

Lahko se celo strel na morda stisne in nato simbolne nekatere datoteke, ki jih uporabljajo v speller, kot so Vojna in mir ali Jane Austen ali nekaj takega - da bi bilo nekako kul - ali Austin Powers, vrste, ki se ukvarjajo z večjimi datotekami, ker ne bi prišel do tega Če smo uporabili naslednje funkcije tukaj, ls-l. Mi smo se uporablja za ls, ki v bistvu navaja vse vsebine v našem trenutnem imeniku. Podaje v zastave-l prikaže dejansko velikost teh datotek. Če greš skozi spec pset, da je dejansko vas popelje skozi ustvarjanje binarno datoteko, da bi ga huffing, in boste videli, da je za zelo majhne datoteke prostor stroški stisniti in prevajanje vse te informacije vseh frekvenc in stvari, kot da odtehta dejanske koristi za stiskanje datoteke na prvem mestu. Ampak, če vi prost dostop na nekaj daljših besedilnih datotek, potem lahko vidite, da ste začeli, da bi dobili nekaj koristi V stiskanje te datoteke. 

In potem končno, imamo staro kolega GDB, ki bo zagotovo prišel prav preveč. 

Ali imate vprašanja o drevesih Huff in procesom morda izdelave drevesa ali katera koli druga vprašanja o Puff Huff'n? Ok. Jaz bom ostal približno za malo. 

Hvala vsem. To je bilo Walkthrough 6. In veliko sreče. 

[CS50.TV]