[Powered by Google Translate] [Walkthrough - Harjoitus 6] [Zamyla Chan - Harvardin yliopisto] [Tämä on CS50. - CS50.TV] 

Hei, kaikki, ja tervetuloa Walkthrough 6: Huff'n Puff. Vuonna Huff'n Puff mitä teemme aiotaan käsitellä Huffman pakatun tiedoston ja sitten turvotusta se takaisin ylös, niin puretaan se, jotta voimme kääntää 0s ja 1s että käyttäjä lähettää meille ja muuntaa sen takaisin alkuperäiseen tekstiin. PSET 6 tulee olemaan melko viileä, koska olet menossa nähdä joitakin työkaluja että käytit PSET 4 ja PSET 5 ja millaisia ​​niiden yhdistämistä 1 aika siisti käsite kun tulet ajatella sitä. 

Myös luultavasti, PSET 4 ja 5 olivat haastavin psets että meillä oli tarjota. Joten nyt meillä on tämä 1 enemmän PSET C, ja sitten sen jälkeen, että olemme web ohjelmointi. Joten onnitella itseänne saada yli kovimmat piikki CS50. 

Liikettä ja Huff'n Puff, meidän työkalupakki tästä PSET tulevat olemaan Huffman puita, joten ymmärtäminen ei vain miten binääripuita työtä, mutta myös nimenomaan Huffman puita, miten he rakennettu. Ja sitten me aiomme olla paljon jakelun koodia tässä PSET, ja tulemme näkemään, että todellisuudessa osa koodia emme ehkä pysty täysin ymmärtämään vielä, ja niin ne tulevat olemaan. C-tiedostoja, mutta sitten heidän mukanaan. h tiedostot antaa meille tarpeeksi ymmärrystä, että tarvitsemme, jotta tiedämme, miten nämä toiminnot toimivat tai ainakin mitä heidän pitäisi tehdä - niiden tulot ja lähdöt - vaikka emme tiedä mitä tapahtuu musta laatikko tai eivät ymmärrä mitä tapahtuu mustan laatikon sisällä. Ja sitten lopuksi, kuten tavallista, olemme tekemisissä uusien tietorakenteiden, tietyntyyppisiin solmujen osoittavat tiettyjä asioita, ja niin tässä ottaa kynän ja paperin paitsi suunnitteluprosessia ja kun yrität selvittää miten PSET pitäisi toimia mutta myös aikana virheenkorjaus. Voit olla GDB rinnalla kynä ja paperia, kun otat alas mitä arvot ovat, missä nuolet osoittavat, ja tuollaista. 

Ensimmäinen katsokaamme Huffman puita. Huffman puut ovat binääripuita, eli kukin solmu on vain 2 lasta. In Huffman puita ominaisuus on se, että yleisin arvot edustavat vähiten bittiä. Näimme luennossa esimerkkejä morseaakkoset, millaisia ​​konsernin joitakin kirjeitä. Jos olet yrittää kääntää tai E, esimerkiksi olet kääntämiseen että usein, joten sen sijaan, että käyttää koko joukko bittejä myönnetty, että tavallisia tietotyyppiä, voit pakata sen alas vähemmän, ja sitten nämä kirjeet, jotka ovat edustettuina harvemmin ovat edustettuina pidemmän bittiä koska sinulla on varaa, että kun punnitaan taajuudet että näitä kirjaimia. Meillä on sama idea täällä Huffman puita jossa teemme ketju, eräänlainen polku päästä tiettyjä merkkejä. Ja sitten hahmoja, jotka ovat eniten taajuus aiotaan edustettuina vähiten bittiä. 

Tapa, että voit rakentaa Huffman puu on sijoittamalla kaikki merkit, jotka esiintyvät tekstissä ja lasketaan niiden tiheys, kuinka usein ne näyttävät. Tämä voi olla joko laskea, kuinka monta kertaa ne kirjaimia tai ehkä prosenttiosuus pois kaikki merkit, kuinka monta kunkin näkyviin. Ja niin mitä teet on kun olet kaiken tämän kartoitettu, sitten etsiä 2 alimmat taajuudet ja sitten liittyä ne sisarukset jos niin isäsolmuun on taajuus, joka on summa sen 2 lasta. Ja sitten Sovitun sanoa että vasen solmu, seuraat että seuraamalla 0 sivuliike, ja sitten oikeanpuoleisin solmu on 1 haara. Kuten näimme morseaakkoset, yksi ähäkutti oli, että jos sinulla olisi vain piippaus ja äänimerkki se oli epäselvä. Se voi olla joko 1 kirjain tai se voi olla sekvenssi 2 kirjainta. Ja niin mitä Huffman puita tekee siksi luonteeltaan merkit tai meidän lopullinen todellisia merkkejä on viimeksi solmujen Branch - me sanomme niistä, kuten lehtiä - nojalla, että ei voi olla mitään epäselvyyttä suhteen mikä kirjain yrität koodata kanssa sarjan bittien koska missään pitkin bitit, jotka edustavat 1 kirjain sinä kohtaat toisen koko kirjeen, ja ei tule mitään sekaannusta siellä. Mutta me mennä esimerkkejä että te voitte itse nähdä, että eikä meistä vain kertoa teille, että se on totta. 

Katsotaanpa yksinkertainen esimerkki Huffman puu. Minulla on merkkijono täällä, että on 12 merkkiä pitkä. Olen 4 Koska 6 Bs ja 2 Cs. Ensimmäinen askel olisi laskea. Kuinka monta kertaa se näyttää? Vaikuttaa siltä 4 kertaa merkkijono. B ilmestyy 6 kertaa, ja C näkyy 2 kertaa. Luonnollisesti, aion sanoa Käytän B useimmiten, niin haluan edustaa B Vähiten bittiä Vähiten 0s ja 1s. Ja sitten olen myös menossa odottaa C vaativat eniten määrä 0s ja 1s samoin. Ensimmäinen mitä tein täällä laitoin ne nousevassa järjestyksessä suhteen taajuuden. Näemme, että C-ja, jotka ovat meidän 2 alimpia taajuuksia. Luomme isäsolmuun, ja että isäsolmuun ei ole kirje liittyy siihen, mutta sillä on taajuus, joka on summa. Summa tulee 2 + 4, joka on 6. Sitten seuraa vasempaan haaraan. Jos olisimme tuossa 6 solmu, niin me seuraisi 0 päästä C ja sitten 1 päästäkseen A. Joten nyt meillä on 2 solmua. Meillä on arvo 6 ja sen jälkeen meillä on myös toinen solmu arvo 6. Ja niin nuo 2 eivät vain 2 alin lisäksi vain 2, jotka ovat jäljellä, joten liitymme niitä toisen vanhemman kanssa summa on 12. Joten tässä meillä on Huffman puu mistä saa B, että olisi vain bitti 1 ja sitten päästä meillä olisi 01 ja C ottaa 00. Joten tässä me näemme, että pohjimmiltaan olemme edustavat näitä chars joko 1 tai 2 bittiä jossa B, kuten ennustettiin, on vähiten. Ja sitten odotimme C on eniten, mutta koska se on niin pieni Huffman puu, sitten edustaa myös 2 bittiä toisin kuin jossain keskellä. 

Vain mennä yli toiselle yksinkertainen esimerkki Huffman puu, että sinulla on merkkijono "Hello." Mitä tehdä, on ensin sanoa, kuinka monta kertaa se H näkyvät tässä? H ilmestyy kerran ja sitten tulee e kerran ja sitten meillä on l esiintyy kahdesti ja o esiintyvät kerran. Ja niin sitten odotamme mikä kirjain tulee edustaa vähintään bittien? [Opiskelija] L. >> L. Joo. l on oikea. Odotamme l edustaa vähiten bittien koska l käytetään eniten merkkijonon "Hei." Mitä aion tehdä nyt vetää näitä solmuja. I on 1, joka on H, ja sitten toinen 1, joka on e, ja sitten 1, joka on O - nyt Laitan ne järjestyksessä - ja sitten 2, joka on l. Sitten sanon niin että voin rakentaa Huffman puu on löytää 2 solmut vähiten taajuudet ja ne sisarukset luomalla isäsolmuun. Täällä meillä on 3 solmut matalin taajuus. He kaikki 1. Joten tässä me valitsemme kumpi aiomme yhdistää ensin. Sanotaan valitsen H ja E. Summa 1 + 1 on 2, mutta tämä solmu ei ole kirje liittyy siihen. Se vain pitää arvoa. Nyt katsomme seuraavan 2 alimmat taajuudet. Se on 2 ja 1. Se voisi olla joko näistä 2, mutta aion valita tämä. Summa on 3. Ja sitten lopuksi, minulla on vain 2 vasemmalle, niin sitten se tulee 5. Sitten täällä, odotetusti, jos en täytä koodaus, että 1s aina oikeaan haaraan ja 0s ovat vasen. Sitten meillä on l edustaa vain 1 vähän ja sitten O 2 ja sitten e 2: lla ja sitten H putoaa 3 bittiä. Joten voit lähettää tämän viestin "Hei" eikä todellisuudessa käyttävät merkkejä vain hieman 0s ja 1s. Muista kuitenkin, että useissa tapauksissa meillä oli suhteita meidän taajuudella. Olisimme voineet joko liittynyt H ja O Ensimmäinen Ehkä. Tai sitten myöhemmin, kun meillä oli l edustaa 2 sekä liittyi jota edustaa 2, olisimme voineet liittyä joko yksi. 

Ja niin kun lähetät 0s ja 1s, jotka todella ei takaa että vastaanottaja voi täysin lukea viestisi oikeus pois bat koska he eivät tiedä, mikä päätös teit. Joten kun olemme tekemisissä Huffman puristus, jotenkin meidän täytyy kertoa vastaanottajalle viestimme miten päätimme - Heidän täytyy tietää jonkinlaista ylimääräistä tietoa lisäksi pakatun viestin. Heidän täytyy ymmärtää, mitä puu todellisuudessa näyttää, miten todella tehdä näitä päätöksiä. 

Täällä olimme juuri tekemässä esimerkkejä perustuu todelliseen määrä, mutta joskus voi olla myös Huffman puu perustuu taajuus, jolla kirjaimia, ja se on täsmälleen sama prosessi. Täällä olen ilmaista sen kannalta prosentteina tai murto- joten tässä täsmälleen sama asia. Minusta 2 alin, lasketaan ne yhteen, seuraavat 2 alin, lasketaan ne yhteen, kunnes olen täysi puu. Vaikka voisimme tehdä sen joko niin, kun olemme tekemisissä prosenttiosuudet, se tarkoittaa, että olemme jakamalla asioita ja käsittelevät desimaalit tai paremminkin kelluu jos ajattelemme tietorakenteita pään. Mitä tiedämme kelluu? Mikä yleinen ongelma, kun olemme tekemisissä kelluu? [Opiskelija] Epätarkat aritmeettinen. >> Joo. Epätarkkuutta. Koska liukuluku epätarkkuus, tämä PSET jotta voimme varmistaa että emme menetä mitään arvoja, niin olemme todella aiotaan käsitellä count. Joten jos olit ajatella Huffman solmun, jos näytät takaisin rakenteeseen täällä, jos tarkastellaan vihreitä se taajuus siihen liittyvä samoin kuin se viittaa solmun sen vasemmalla puolella sekä solmu sen oikealla puolella. Ja sitten punaisia ​​siellä on myös luonteeltaan niihin liittyviä. Emme aio tehdä erillisten vanhemmille ja sitten lopullinen solmut, jota me kutsumme lehtiä, vaan ne täytyy vain NULL-arvoja. Sillä jokainen solmu saamme merkin, symbolin että solmu edustaa, Sitten taajuus sekä osoitin sen vasen lapsi sekä sen oikea lapsi. Lehdet, jotka ovat hyvin alhaalla, olisi myös solmun osoittimet niiden vasemmalle ja heidän oikeutensa, mutta koska arvot eivät viittaa todellisiin solmuja, mikä niiden arvo on? >> [Opiskelija] NULL. >> NULL. Aivan. Tässä esimerkki siitä, miten voi edustaa taajuus kellukkeet, mutta aiomme olla tekemisissä sen kanssa kokonaislukuja, joten kaikki tein on muuttaa tietotyyppiä siellä. 

Mennään edelleen hieman enemmän monimutkaisempi esimerkki. Mutta nyt olemme tehneet yksinkertaiset, se on aivan sama prosessi. Löydät 2 alimmat taajuudet, summa taajuudet ja se on uutta taajuutta oman vanhemman solmun, joka sitten osoittaa sen vasemmalle kanssa 0 haara ja oikealle 1 haara. Jos meillä on merkkijono "Tämä on cs50", niin laskemme kuinka monta kertaa on T mainitaan, h mainittiin, i, s, c, 5, 0. Sitten tein täällä on kanssa punainen solmut juuri istutettu, Sanoin Aion olla näitä merkkejä lopulta alareunassa minun puu. Ne tulevat olemaan kaikki lehdet. Sitten mitä tein on I lajiteltu niiden esiintymistiheyden nousevassa järjestyksessä, ja tämä on todella niin, että PSET koodi tekee sen on se lajittelee sen taajuus ja sitten aakkosjärjestyksessä. Niin se on numerot ensin ja sitten aakkosjärjestykseen taajuus. Sitten mitä haluaisin tehdä on löytäisin 2 alhaisin. Se on 0 ja 5. Haluaisin tiivistää niitä, ja se on 2. Sitten haluaisin jatkaa, löytää seuraavan 2 alhaisin. Nämä ovat kaksi 1s, ja sitten ne tulevat 2 samoin. Nyt tiedän, että minun seuraava askel tulee olemaan liittyä pienin numero, joka on T, 1, ja valitsemalla sitten yksi solmuista, joka on 2, kun taajuus. Joten tässä meillä on 3 vaihtoehtoa. Mitä aion tehdä dia vain visuaalisesti järjestää ne sinulle jotta näet miten olen rakentaa sen. Mitä koodin ja jakelu koodin aikoo tehdä olisi liittyä T yksi kanssa 0 ja 5 solmun. Joten sitten, että summat 3, ja sitten jatkamme prosessia. 2 ja 2 ovat nyt pienin, niin sitten nuo summan 4. Jokainen jälkeen toistaiseksi? Okei. Sitten sen jälkeen, että meillä on 3 ja 3, jotka on laskettava yhteen, joten taas olen vain vaihtaa niin, että voit nähdä visuaalisesti niin, että se ei ole liian sotkuinen. Sitten meillä on 6, ja sitten meidän viimeinen askel on nyt, että meillä on vain 2 solmua meidän summa niille, jotta juuriin puu, joka on 10. Ja numero 10 on järkeä, koska jokainen solmu edustaa, niiden arvo, tiheys numero, oli kuinka monta kertaa he ilmestyi merkkijono, ja sitten meillä on 5 merkkiä meidän merkkijonon, joten on järkevää. Jos katsomme ylös kuinka me todella koodata sitä, kuten odotettua, i ja t, jotka näkyvät useimmiten edustaa vähiten bittien määrä. 

Ole varovainen täällä. Vuonna Huffman puita asia todella on väliä. Isot S on erilainen kuin pieniä s. Jos meillä olisi "Tämä on CS50" isoilla kirjaimilla, niin pieni ta tuntuisivat vain kahdesti, olisi solmu 2 sen arvo, ja sitten isot S olisi vain kerran. Joten teidän puu muuttuisi rakenteita, koska sinulla todella on ylimääräistä lehtiä täällä. Mutta summa olisi edelleen 10. Sitähän me todella olemaan soittamalla tarkistussumma, Lisäksi kaikkien laskee. 

Nyt kun olemme kattaa Huffman puita, voimme sukeltaa Huff'n Puff, PSET. Aiomme aloittaa osan kysymyksiä, ja tämä on menossa sinut tottunut binary puita ja miten toimia noin että: piirustus solmut, luoda omia typedef struct varten solmun, ja nähdä kuinka saatat lisättävän binääripuu, joka on lajiteltu, liikkumisesta, ja tuollaista. Tämä tieto on varmasti auta sinua, kun sukeltaa Huff'n Puff osa ja PSET. Vuonna standardin painos PSET, teidän tehtävänne on toteuttaa Puff, ja hakkeri versiossa sinun tehtäväsi on toteuttaa Huff. Mikä Huff ei se vie tekstin ja sitten se muuntaa sen 0s ja 1s, joten prosessi, että teimme yläpuolella, jossa laskimme taajuudet ja sitten tehdään puusta ja sanoi sitten: "Miten saan T?" T edustaa 100, tuollaista, ja sitten Huff veisi tekstin ja sitten lähtö että binary. Mutta myös koska tiedämme, että haluamme antaa meidän viestin vastaanottaja luoda uudelleen täsmälleen samassa puussa, se sisältää myös tietoa taajuus laskee. Sitten Puff saamme binaaritiedoston 0 ja 1s ja annetaan myös tiedot taajuuksilla. Käännämme kaikki nämä 0s ja 1s takaisin alkuperäiseen viesti oli, joten olemme purettaessa että. Jos teet Standard Edition, sinun ei tarvitse toteuttaa Huff, niin sitten voit vain käyttää henkilöstön toteuttamista Huff. On ohjeita spec, miten tehdä se. Voit suorittaa henkilöstö täytäntöönpanoa Huff tietystä tekstitiedosto ja sitten käyttää tuotoksen kuin panos Puff. 

Kuten aiemmin mainitsin, meillä on paljon jakelu koodin tämä yksi. Aion aloittaa menee läpi. Aion viettää suurimman osan aikaa. H tiedostot koska. C-tiedostoja, koska meillä on. h ja joka tarjoaa meille prototyyppejä toimintoja, emme täysin täytyy ymmärtää - Jos et ymmärrä mitä tapahtuu vuonna. C-tiedostoja, niin älä huolehdi liikaa, mutta ehdottomasti kokeilla katsomaan, koska se saattaa antaa joitakin vihjeitä ja se on hyödyllistä tottua lukea toisten koodia. 

Tarkasteltaessa huffile.h vuonna kommentit julistaa kerros abstraktio Huffman-koodattu tiedostot. Jos menemme alas, voimme nähdä, että siellä on enintään 256 symboleja, että saatamme tarvita koodeja. Tämä sisältää kaikki aakkosten - isot ja pienet - ja sitten symboleja ja numeroita jne. Sitten täällä meillä maaginen tunnistenumero Huffman-koodattu tiedosto. Sisällä Huffman he aikovat olla tietty maaginen numero liittyvä otsikko. Tämä saattaa näyttää vain satunnainen maaginen luku, mutta jos todella kääntää ASCII, niin se todella täsmennetään Huff. Täällä meillä struct varten Huffman-koodattu tiedosto. Siellä on kaikki nämä ominaisuudet liittyvät Huff-tiedosto. Sitten täällä meillä otsikkoa Huff tiedostoa, joten kutsumme sitä Huffeader sijaan lisätä ylimääräisiä h, koska se kuulostaa samalta muutenkin. Cute. Meillä on maaginen numero liittyy siihen. Jos se on todellinen Huff tiedoston, se tulee olemaan numero ylhäällä, tämä taika yksi. Ja niin se on jono. Joten kunkin symbolin, joita on 256, se tulee luetella mitä taajuutta näiden symbolien ovat Huff tiedosto. Ja sitten lopuksi meillä tarkistussumma taajuuksilla, jonka pitäisi olla niiden summa taajuuksilla. Niin, että mitä Huffeader on. Sitten meillä on joitakin toimintoja, jotka palauttavat seuraava bitti Huff tiedosto sekä kirjoittaa vähän sen Huff tiedoston, ja sitten tämä toiminto tässä, hfclose, että todellisuudessa sulkee Huff-tiedosto. Ennen olimme tekemisissä suoraan vain FSulje, mutta kun on Huff tiedoston sijaan fclosing se mitä olet todella aikoo tehdä, on hfclose ja hfopen sitä. Nämä ovat tiettyjä toimintoja Huff tiedostojen aiomme olla tekemisissä. Sitten täällä luemme otsikko ja kirjoita otsikko. 

Vain lukemalla. H tiedosto me voi sellaista saada tunteen mitä Huff tiedosto voi olla, Mitä ominaisuuksia sillä on, ilman että menee huffile.c, joka, jos me sukeltaa, tulee olemaan hieman monimutkaisempi. Siinä on kaikki tiedoston I / O täällä tekemisissä viitteitä. Tässä näemme, että kun me kutsumme hfread, esimerkiksi, se on edelleen tekemisissä fread. Emme päästä eroon näistä toiminnoista kokonaan, mutta lähetämme ne on pidettävä huolta sisällä Huff tiedoston sijaan tehdä kaiken sen itse. Voit vapaasti selata tätä jos olet kiinnostunut ja mene ja kuori kerros takaisin hieman. 

Seuraava kuva, että olemme menossa katsomaan on tree.h. Aikaisemmin Walkthrough liukuu sanoimme odotamme Huffman solmu ja teimme typedef struct solmu. Odotamme sen olevan symbolin, taajuus, ja sitten 2 solmun tähteä. Tässä tapauksessa mitä teemme on tämä on pohjimmiltaan sama paitsi sen sijaan solmun aiomme kutsua niitä puita. Meillä on toiminto, kun soitat tehdä puusta se palauttaa sinut puu osoittimen. Takaisin oikeinkirjoituksen, kun tekivät uuden solmun Sanoit solmu * uusi sana = malloc (sizeof) ja tuollaista. Pohjimmiltaan mktree aiotaan käsitellä sen sinulle. Vastaavasti, kun haluat poistaa puun, Niin, että lähinnä vapauttaa puuta, kun olet tehnyt sen, sijasta nimenomaan kehotetaan ilmaiseksi, että olet todella vain aio käyttää toimintoa rmtree jossa voit kulkea osoitin, että puun ja sitten tree.c hoitaa sen puolestasi. 

Katsomme tree.c. Odotamme samat toiminnot paitsi nähdä täytäntöönpanoon samoin. Kuten odotimme, kun soitat mktree se mallocs koko puu osaksi osoitin, alustaa kaikki arvot arvon NULL, joten 0s tai nollia, ja palaa sitten osoitin että puu että olet juuri malloc'd sinulle. Täällä kun soitat poistat puu ensin varmistaa, että et ole kaksinkertaista vapauttaa. Se varmistaa, että sinulla todella on puu, jonka haluat poistaa. Täällä, koska puu sisältää myös sen lapsia, Mikä tämä on se rekursiivisesti kehotetaan poistamaan puu vasemmalla solmu puun sekä oikea solmu. Ennen se vapauttaa vanhempi, se tarvitsee vapauttaa myös lapset. Vanhempi on myös vaihdettavissa root. Ensimmäinen vanhempi, joten kuten iso-iso-iso-iso-isoisä tai isoäiti puu, ensin meidän täytyy vapauttaa alas tasolle ensin. Joten kulkevat pohjaan, ilmainen näitä, ja sitten tulla takaisin ylös, ilmainen näitä jne. Joten se puu. 

Nyt katsomme metsää. Metsä on missä laitat kaikki Huffman puita. On selvää, että me aiomme olla jotain kutsutaan juoni , joka sisältää osoittimen puuhun sekä osoittimen juonen kutsutaan seuraavaksi. Mitä rakenne tekee tällaista näyttää? Se tavallaan kertoo tuolla. Oikea tänne. Linkitetty lista. Näemme, että kun meillä on tontti tuntuu linkitetty lista tontteja. Metsä määritellään linkitetty luettelo tonttien, joten rakenne metsän olemme juuri menossa on osoitin ensimmäinen tontti ja että tontti on puu sisällä tai pikemminkin osoittaa puuhun ja sitten viittaa seuraavaan tontti, niin edelleen ja niin edelleen. Jotta metsä kutsumme mkforest. Sitten meillä on joitakin melko hyödyllisiä toimintoja täällä. Olemme poimia missä kulkea metsässä ja sitten palauttaa arvo on Tree * osoittimen puuhun. Mitä pick tekee se menee metsään että olet osoittavat irrota puun matalin taajuus tuosta metsästä ja sitten antaa sinulle osoittimen tuon puun. Kun soitat valita, puu ei ole metsässä enää, mutta paluuarvo on osoitin, että puu. Sitten sinulla on kasvi. Edellyttäen, että kulkea osoittimen puu, joka on ei-0 taajuus, mitä tehdas tekee se vie metsän, ottaa puu ja kasvi että puu sisällä metsän. Täällä meillä on rmforest. Samanlaisia ​​poistaa puun, joka pohjimmiltaan vapautti kaikki meidän puut meille, Poista metsän vapaa kaikkeen sisältyy, että metsässä. 

Jos katsomme forest.c, me odottaa vähintään 1 rmtree komento siellä, koska vapaan muistin metsässä, jos metsässä on puita siinä, sitten lopulta olet menossa on poistaa nämä puut liikaa. Jos katsomme forest.c, meillä mkforest, joka on niin odotamme. Me malloc asioita. Me alustaa ensimmäisen tontin metsästä NULL koska se on tyhjä aluksi, sitten näemme pick, joka palauttaa puun kanssa alin paino, alin taajuus, ja sitten pääsee eroon, että tietyn solmun, joka osoittaa, että puun ja seuraava, niin se vie että ulos linkitetty lista metsän. Ja sitten täällä meillä on tehdas, joka lisää puun osaksi linkitetty lista. Mitä metsä ei se hienosti pitää sitä lajiteltu meille. Ja sitten lopuksi, meillä on rmforest, ja kuten odotettua, meillä on rmtree kutsutaan siellä. 

Tarkasteltaessa jakelu koodin toistaiseksi huffile.c oli luultavasti ylivoimaisesti vaikein ymmärtää, taas muut tiedostot itse oli melko helppo seurata. Kanssa tietomme osoittimien ja linkitettyjen listojen ja tällainen, pystyimme seuraamaan melko hyvin. Mutta kaikki me tarvitsemme todella varmistaa, että ymmärrämme on. H tiedostot koska sinun täytyy soittaa kyseisiä toimintoja käsitellä sellaisia ​​paluuarvot, joten varmista, että olet täysin ymmärrä, mitä toimia aiotaan suorittaa kun soitat yhtä näistä toiminnoista. Mutta todellisuudessa ymmärtäminen sisältä se ei ole aivan välttämätöntä, koska meillä on nuo. H. tiedostoja. Meillä on 2 lisää tiedostoja jäljellä meidän jakelussa koodin. 

Katsotaanpa kaatopaikalle. Dump sen kommentin tähän vie Huffman-pakattu tiedosto ja sitten kääntää ja tyhjentää kaikki sen sisältö ulos. Tässä näemme, että se soittaa hfopen. Tämä on tavallaan peilaus tiedostoon * input = fopen, ja sitten ohitat tiedoissa. Se on melkein identtinen paitsi sijasta tiedoston * olet ohimennen Huffile; sijaan fopen olet ohimennen hfopen. Täällä luemme otsikon ensimmäinen, joka on tavallaan samanlainen miten luemme otsikon varten bittikarttatiedosto. Mitä me teemme täällä on tarkistaa, onko otsikkotiedot sisältää oikea maaginen numero, joka ilmaisee, että se on todellinen Huff tiedoston, Sitten kaikki nämä tarkastukset varmista, että tiedosto avaamme on todellinen puuskahti tiedostoa tai ei. Mikä tämä on se tuottaa taajuudet kaikilla symboleilla, että voimme nähdä sisällä päätelaitteelle graafinen taulukkoon. Tämä osa tulee olemaan hyödyllinen. Se on vähän ja lukee vähän kerrallaan muuttujaan vähän ja sitten tulostaa sen. Joten jos olisin soittaa polkumyyntiin hth.bin, mikä on seurausta huffing tiedoston avulla henkilöstö ratkaisu, haluan saada tämän. Se syöttöä kaikki nämä merkit ja sitten asettaa taajuuden, jossa ne esiintyvät. Jos katsomme, useimmat niistä ovat 0s, lukuun ottamatta tätä: H, joka esiintyy kahdesti, ja sitten T, joka esiintyy kerran. Ja sitten täällä on todellinen viesti 0s ja 1s. Jos tarkastelemme hth.txt, joka on oletettavasti alkuperäisen viestin, joka oli huffed, odotamme joitakin Hs ja Ts siellä. Erityisesti odotamme vain 1 T ja 2 Hs. Täällä olemme hth.txt. Se todellakin on HTH. Mukana siellä, vaikka emme voi nähdä sitä, on rivinvaihtomerkki. Huff tiedosto hth.bin myös koodaa rivinvaihtomerkki samoin. Täällä sillä me tiedämme, että järjestys on HTH ja sitten rivinvaihto, voimme nähdä, että luultavasti H edustaa vain yhden 1 ja sitten T on todennäköisesti 01 ja sen jälkeen seuraava H on 1 samoin ja sitten meillä on rivinvaihto merkitään kahdella 0s. Cool. 

Ja sitten lopuksi, koska olemme tekemisissä useita. C ja. H tiedostoja, aiomme olla melko monimutkainen argumentti kääntäjä, joten tässä meillä on Makefile joka tekee dump teitä. Mutta todella, sinun täytyy mennä noin tehdä omia puff.c tiedosto. Makefile oikeastaan ​​ei käsitellä tehdä puff.c sinulle. Lähdemme siitä, että jopa voit muokata Makefile. Kun kirjoitat komennon kuten tekevät kaikki, se esimerkiksi tekee kaikki ne sinulle. Voit vapaasti katsoa esimerkkejä Makefile menneisyydestä PSET sekä menossa pois tämä kuinka saatat pystyä tekemään Puff tiedosto muokkaamalla tätä Makefile. Se siitä meidän jakelua koodia. 

Kun olemme saaneet läpi, niin tässä on vain toinen muistutus miten aiomme olla tekemisissä Huffman solmut. Emme aio olla kutsuen heitä solmuja enää, aiomme olla kutsumassa niitä puita minne olemme menossa edustamaan heidän symboli char, niiden taajuuden, tapahtumien määrä, jossa kokonaisluku. Käytämme että koska se on tarkempi kuin float. Ja sitten meillä on toinen osoitin vasemmalle lasta sekä oikea lapsi. Metsä, kuten näimme, on vain linkitetyn listan puita. Lopulta, kun olemme rakentamassa meidän Huff tiedosto, haluamme metsä sisältää vain 1 puu - 1 puu, 1 root useita lapsia. Aiemmin kun olimme juuri tehdessämme Huffman puita, aloitimme asettamalla kaikki solmut päälle meidän näytöllä ja sanoi aiomme olla näitä solmuja, Lopulta he olemaan lehdet, ja tämä on heidän symboli, tämä on heidän taajuus. Meidän metsä jos meillä vain on 3 kirjainta, joka on metsän 3 puita. Ja sitten me mennä, kun lisäsimme ensimmäinen vanhempi, teimme metsässä 2 puuta. Poistimme 2 näistä lapsista meidän metsästä ja sitten korvannut sen vanhemman solmun että oli nuo 2 solmua lapsina. Ja sitten lopuksi, meidän viimeinen askel kanssa tekemällä esimerkiksi As, Bs ja Cs olisi tehdä lopullinen emoyhtiö, ja niin sitten se toisi meidän yhteen laskettu metsän puiden 1. Onko jokainen miten aloitat useita puita omassa metsässä ja lopulta 1? Okei. Cool. 

Mitä meidän täytyy tehdä Puff? Meidän tarvitsee vain varmistaa, että aina, ne antavat meille oikean tyyppinen tulo jotta voimme ajaa ohjelman. Tässä tapauksessa he aikovat olla antaa meille jälkeen ensimmäinen komentoriviargumentin 2 lisää: tiedosto, haluamme purkaa ja lähtö puretun tiedoston. Mutta kun me varmista, että ne kulkevat meille oikean määrän arvoja, Haluamme varmistaa, että tulo on Huff tiedosto tai ei. Ja sitten kun me takaamme, että se on Huff tiedosto, niin me haluamme rakentaa puu, rakentaa puu siten, että se vastaa puun että henkilö lähetti viestin rakennettu. Sitten kun me rakennamme puu, niin voimme käsitellä 0s ja 1s että ne hyväksyttiin, noudata niitä pitkin meidän puu, koska se on sama, ja sitten kirjoittaa, että viestisi, tulkita bitit takaisin merkkiä. Ja sitten lopussa, koska olemme tekemisissä osoittimet täällä, Haluamme varmistaa, että meillä ei ole mitään muistivuotoja ja että me vapaa kaikesta. 

Varmistamalla asianmukainen käyttö on vanha hattu meille nyt. Otamme in tulo, joka tulee olemaan tiedoston nimi puff, ja sitten me määritä lähtö, joten tiedoston nimi varten turvotettua tuotos, joka on tekstitiedosto. Se käyttöä. Ja nyt me haluamme varmistaa, että tuloa puuskahti vai ei. Thinking takaisin, oli siellä mitään jakelu koodin, jotka voivat auttaa meitä ymmärtämisestä onko tiedosto puuskahti vai ei? Oli tietoja huffile.c tietoa Huffeader. Tiedämme, että jokainen Huff tiedosto on Huffeader liittyy se maaginen numero samoin kuin erilaisia ​​taajuuksia kunkin symbolin sekä tarkistussumma. Tiedämme sen, mutta otimme myös kurkistaa dump.c, jossa se luki osaksi Huff tiedostoon. Ja niin tehdä, että se oli tarkistaa, onko se todella ollut puuskahti vai ei. Joten ehkä voisimme käyttää dump.c kuin rakenne meidän puff.c. Takaisin PSET 4, kun meillä oli tiedosto copy.c että kopioitu RGB kolminkertaistuu ja me tulkitaan että jännäri ja kokoa, Vastaavasti mitä voisit tehdä, on vain ajaa komentoa cp dump.c puff.c ja käyttää joitakin koodin sinne. Kuitenkin, se ei tule olemaan yhtä mutkatonta ja prosessin kääntämiseen teidän dump.c osaksi puff.c, mutta ainakin se antaa sinulle jonnekin aloittaa siitä, kuinka varmistetaan, että tulo on todellisuudessa huffed tai ei sekä muutamia muita asioita. Olemme varmistaneet asianmukainen käyttö ja varmistettava, että tulo puuskahti. Joka kerta, kun olemme tehneet, että olemme tehneet oikean virheentarkistukset, niin palaamassa ja lopetus toiminto jos jokin vika, jos on ongelmia. 

Nyt me haluamme tehdä, on rakentaa todellista puu. Jos katsomme Forest, on 2 tärkeimmät toiminnot että olemme menossa halua tulla hyvin tuttu. On Boolen funktio kasvi, kasvit kuin 0 taajuus puu sisällä meidän metsä. Ja niin siinä ohitat vuonna osoittimen metsä ja osoitin puun. Nopea kysymys: Kuinka monta metsien olet kun olet rakentamassa Huffman puu? Meidän metsä on kuin meidän kankaalle, eikö? Joten me vain olemaan 1 metsää, mutta me aiomme olla useita puita. Joten ennen kuin soitat kasvi, olet luultavasti menossa haluavat tehdä metsään. On komento, että jos näytät forest.h miten voit tehdä metsän. Voit istuttaa puun. Tiedämme, miten tehdä se. Ja sitten voit myös valita puu metsä poistamalla puun alin paino ja antaa sinulle osoittimen siihen. Thinking takaisin kun olimme tekemässä esimerkit itseämme, kun olimme vetämällä sitä ulos, me yksinkertaisesti vain lisätä linkkejä. Mutta täällä sen sijaan vain lisäämällä yhteyksiä, ajattele sitä enemmän olet poistamalla 2 näitä solmuja ja sitten korvaa sen toiseen. Ilmaista, että suhteen poiminta ja istutus, olet poiminta 2 puut ja sitten istutus toiseen puuhun että on nuo 2 puita että olet valinnut lapsina. Rakentaa Huffman puiden, voit lukea symboleja ja taajuudet järjestyksessä koska Huffeader antaa sen sinulle, antaa erilaisia ​​taajuuksia. Joten voit mennä eteenpäin ja vain sivuuttaa mitään 0 siinä koska emme halua 256 lähtee lopussa se. Haluamme vain lehtien lukumäärä, jotka ovat merkkejä joita tosiasiallisesti käytetään tiedostoon. Voi lukea ne symbolit, ja kukin näistä symboleja, jotka ovat ei-0 taajuuksia, ne tulevat olemaan puita. Mitä voit tehdä, on aina lukea kuin 0 taajuuden symbolin, voit istuttaa että puu metsässä. Kun istuttaa puita metsässä, voit liittyä nuo puut sisarukset, niin menee takaisin istutus ja poiminta, jossa voit valita 2 ja sitten kasvi 1, jos se 1 että kasvi on vanhempi 2 lasta, että olet valinnut. Joten sitten sinun lopputulos tulee olemaan yksi puu omassa metsässä. Näin voit rakentaa puu. 

On useita asioita, jotka voivat mennä pieleen koska olemme tekemisissä tehdä uusia puita ja käsitellä osoittimet ja tuollaista. Ennen kun olimme tekemisissä osoittimia, kun me malloc'd halusimme varmistaa, että se ei palauta meille NULL osoittimen arvo. Joten useita vaiheita tässä prosessissa on menossa olla useita tapauksia missä ohjelma voisi epäonnistua. Mitä haluat tehdä on haluat varmistaa, että voit hoitaa nämä virheet, ja spec sanotaan käsitellä niitä sulavasti, joten haluaisin tulostaa viestin käyttäjälle heille, miksi ohjelma on lopettaa ja sitten heti lopettaa se. Voit tehdä tämän virheenkäsittely, muista, että haluat tarkistaa joka ikinen kerta, että siellä voisi olla vika. Joka ikinen kerta, että teet uuden osoittimen haluat varmistaa, että se on onnistunut. Ennen mitä käytimme vain tehdä uuden osoittimen ja malloc sitä, ja sitten voisimme tarkistaa, onko kyseinen osoitin on NULL. Joten ei aiotaan joitakin tapauksia, joissa voit vain tehdä se, mutta joskus olet todella kutsuvan funktion ja kyseisessä toiminto, se joka tekee mallocing. Siinä tapauksessa, jos katsomme taaksepäin joidenkin toimintojen koodin, jotkut niistä ovat Boolen toimintoja. Vuonna abstrakti jos meillä Boolen funktio nimeltä foo- pohjimmiltaan, voimme olettaa, että sen lisäksi tekee mitä foo tekee, koska se on Boolen funktio, se palauttaa true tai false - true jos onnistuu, false jos ei. Niinpä haluamme onko palauttaa arvon foo on tosi tai epätosi. Jos se on väärä, se tarkoittaa, että olemme menossa halua tulostaa jonkinlaisen viestin ja sulje ohjelma. Mitä me haluamme tehdä, on tarkistaa paluuarvon foo. Jos foo palauttaa false, niin tiedämme, että meillä on ollut jonkinlainen virhe ja meidän täytyy lopettaa ohjelmaamme. Tapa tehdä tämä on saada tila, jossa varsinainen toiminta itsessään on kunnossa. Sano foo vie x. Voimme olla ehtona if (foo (x)). Pohjimmiltaan, se tarkoittaa, että jos lopussa täytäntöönpanovaltion foo se palauttaa totta, voimme tehdä tämän, koska toiminto on arvioitava foo jotta voidaan arvioida koko tila. Joten sitten se, miten voit tehdä jotain, jos funktio palauttaa true ja onnistuu. Mutta kun olet virheentarkistukset, haluat vain lopettaa jos funktio palauttaa false. Mitä voisit tehdä, on vain lisätä == false tai vain lisätä bang edessä on ja sitten on jos (! foo). Kyseisen laitoksen kyseisen edellytyksen sinulla olisi kaikki virheiden käsittelyä, joten kuten, "ei voitu luoda tätä puuta" ja palaa sitten 1 tai jotain. Mitä se tekee kuitenkin se, että vaikka foo palautetaan false - Sano foo palauttaa true. Silloin sinun ei tarvitse soittaa foo uudelleen. Tuo yleinen väärinkäsitys. Koska se oli vointisi, se on jo arvioinut, joten sinulla on jo tulos jos käytät tehdä puusta tai jotain tai kasvin tai poimia tai jotain. Se on jo kyseisen arvon. Se on jo toteutettu. Joten se on hyödyllistä käyttää Boolen toimii kunnossa koska vai et itse suorittaa elin silmukan, se suorittaa toiminnon muutenkin. 

Meidän toiseksi viimeinen vaihe on kirjallisesti viestin tiedoston. Kun me rakennamme Huffman puu, sitten kirjallisesti viesti tiedosto on melko yksinkertainen. Se on melko yksinkertainen nyt vain seurata 0s ja 1s. Ja näin yleissopimuksessa tiedämme, että Huffman puu 0s osoittavat vasemmalle ja 1s osoittavat oikealle. Joten jos olet lukenut vähän kerrallaan, aina kun saat 0 voit seurata vasen haara, ja sitten aina lukea 1 aiot seurata oikeaan haaraan. Ja sitten olet menossa jatkamaan kunnes osut lehtiä koska lehdet tulevat olemaan lopussa oksat. Miten voimme tietää, onko meillä osuma lehtiä vai ei? Sanoimme ennen. [Opiskelija] Jos osoittimet ovat NULL. >> Joo. Voimme kertoa, jos olemme osuma lehtiä, jos osoittimia sekä vasen ja oikea puut ovat NULL. Perfect. Me tiedämme, että haluamme lukea vähän kerrallaan meidän Huff tiedostoon. Kuten näimme aiemmin dump.c, mitä he tekivät on ne luetaan vähän kerrallaan osaksi Huff tiedosto ja vain tulostaa mitä nämä bitit olivat. Emme aio tehdä sitä. Aiomme tehdä jotain, joka on hieman monimutkaisempi. Mutta mitä voimme tehdä on, voimme ottaa sen vähän koodia, joka lukee sisään bitti. Täällä meillä on kokonaisluku bitti edustaa nykyistä hieman, että olemme. Tämä huolehtii iteroimalla kaikki bitit tiedostoon, kunnes osut tiedoston loppuun. Perustuu että sitten olet menossa halua olla jonkinlainen iteraattori kulkemaan teidän puu. Ja sitten sen perusteella, onko kyseinen bitti on 0 tai 1, olet menossa haluavat joko siirtää että iteraattori vasemmalle tai siirrä se oikealle aina kunnes osut lehtiä, niin aina kunnes solmu että olet ei viitata enää solmuja. Miksi teemme tätä Huffman tiedoston, mutta ei morseaakkoset? Koska morseaakkoset siellä hieman epäselvyyttä. Voisimme olla kuin, Voi odottaa, olemme osuma kirjeen matkan varrella, joten ehkä tämä on meidän kirjeen, katsoo, että jos jatkamme vain vähän kauemmin, niin olisimme osuma toisen kirjeen. Mutta se ei tule tapahtumaan Huffman koodausta, jotta voimme olla varmoja, että ainoa tapa, jolla aiomme osuma merkki On jos solmun vasen ja oikea lapset ovat NULL. 

Lopuksi haluamme vapauttaa meidän kaikkien muistissa. Haluamme molemmat lähellä Huff tiedosto olemme tekemisissä sekä poistaa kaikki puut meidän metsässä. Perustuu omaan toteuttamisesta, olet todennäköisesti menossa halua soittaa poistaa metsä sijaan todella menee läpi kaikki puut itse. Mutta jos olet tehnyt mitään väliaikaista puita, sinun kannattaa vapauttaa se. Tiedät koodin parasta, niin tiedät minne olet jaettaessa muistia. Ja niin jos menet, aloita vaikka ohjaus F'ing varten malloc, nähdä aina malloc ja varmista, että sinulla vapauttaa kaikki, jotka mutta sitten vain menee läpi koodin, ymmärtää missä olet ehkä jaettu muisti. Yleensä voit vain sanoa, "Lopussa tiedoston Aion poistaa metsä minun metsä" joten periaatteessa selvää, että muistin, vapaa, että "Ja sitten olen myös menossa sulkea tiedoston ja sitten minun ohjelma tulee lopettaa." Mutta onko se ainoa kerta, että ohjelma sulkeutuu? Ei, koska joskus saattaa olla virhe tapahtui. Ehkä emme voi avata tiedostoa tai emme voineet tehdä toinen puu tai jonkinlainen virhe tapahtui muistinvaraustila prosessia ja niin se palasi NULL. Virhe tapahtui, ja sitten palasimme ja lopeta. Joten sitten haluat varmistaa, että mahdolliset aika että ohjelma voidaan lopettaa, haluat vapauttaa kaikki muisti siellä. Se ei vain olemaan aivan lopussa päätehtävä että lopetat koodi. Haluat katsoa takaisin joka kerta, että koodin mahdollisesti voisi palata ennenaikaisesti ja sitten vapaa mitä muistia järkeä. Sano oli soittanut tehdä metsän ja palasi vääriä. Sitten luultavasti ei tarvitse poistaa metsä koska sinulla ei ole metsää vielä. Mutta kaikissa pisteissä koodi, jos saatat palata ennenaikaisesti haluat varmistaa, että voit vapauttaa mahdolliset muistia. 

Joten kun olemme tekemisissä vapauttaa muistia ja ottaa mahdolliset vuodot, Haluamme paitsi käyttää harkintaa ja meidän logiikka mutta myös käyttää Valgrind onko olemme vapautti kaikki meidän muistia oikein vai ei. Voit joko ajaa Valgrind päälle Puff ja sitten on myös sitä tule oikea määrä komentorivin argumentteja Valgrind. Voit juosta, mutta lähtö on vähän arvoituksellinen. Olemme saaneet hieman käyttää sitä oikeinkirjoituksen, mutta tarvitsemme vielä hieman enemmän apua, niin sitten käynnissä sitä muutaman lippuja kuin vuoto-check = täynnä, Todennäköisesti saamme hieman lisää hyödyllisiä lähtö Valgrind. 

Sitten toinen vihje kun olet virheenkorjaus on diff komennon. Voit käyttää henkilöstön täytäntöönpanon Huff, ajaa että tekstitiedosto, ja sitten tulostaa sen binaaritiedosto, binary Huff tiedoston, erityiseksi. Sitten jos voit suorittaa oman henkosesta että binaaritiedosto, Sitten ihannetapauksessa nimellä lähtönä tekstitiedosto tulee olemaan identtisiä kuin alkuperäinen että olet läpäissyt sisään Tässä olen käyttäen hth.txt kuten esimerkiksi ja se on yksi puhutuimmista teidän spec. Se on kirjaimellisesti vain HTH ja rivinvaihto. Mutta ehdottomasti rohkeasti ja olet varmasti kannustetaan käyttämään pidempään esimerkkejä oman tekstitiedosto. 

Voit jopa ottaa ampui ehkä puristamalla ja purkamiseen joitakin tiedostoja käytit Speller kuten Sota ja rauha tai Jane Austen tai jotain - se olisi eräänlainen cool - tai Austin Powers, Tällainen käsitellä suurempia tiedostoja, koska meidän ei tule alas se jos käytämme seuraava työkalu tässä, ls-l. Olemme tottuneet ls, joka pohjimmiltaan luetellaan kaikki sisältö meidän hakemistossa. Syöttäminen on lippu-l todella näyttää kokoon nämä tiedostot. Jos menet läpi PSET spec, se todella opastaa luomaan binaaritiedosto ja huffing sitä, ja näet, että hyvin pieniä tiedostoja tilan kustannukset puristamalla sitä ja kääntää kaikki nämä tiedot kaikki taajuudet ja tuollaista suurempi todellinen hyöty pakata tiedoston ensimmäinen paikka. Mutta jos käytät sitä jonkin enää tekstitiedostoja, niin saatat nähdä, että aloitat saada jonkinlaista hyötyä vuonna puristamalla kyseiset tiedostot. 

Ja sitten lopuksi, meillä on vanha kamu GDB, joka on ehdottomasti menossa ovat käteviä myös. 

Onko meillä mitään kysymyksiä Huff puita tai prosessin ehkä tehdä puut tai muita kysymyksiä Huff'n Puff? Okei. Viivyn ympäriinsä hieman. 

Kiitos kaikille. Tämä oli läpikäynti 6. Ja onnea. 

[CS50.TV]