[Powered by Google Translate] [Walkthrough - Probléma Set 6] [Zamyla Chan - Harvard University] [Ez CS50. - CS50.TV] 

Hello, mindenkinek, és üdvözöljük a Walkthrough 6: Huff'n Puff. A Huff'n Puff mit teszünk fog foglalkozni a Huffman tömörített fájl majd szuszogva vissza, szóval kibontás azt, hogy tudjuk fordítani a 0s és 1s, hogy a felhasználói küld nekünk és átalakítani, hogy vissza az eredeti szöveget. Pset 6 lesz elég jó, mert fogsz látni néhány eszköz hogy használt Pset 4. és Pset 5 és milyen egyesíti őket 1 elég ügyes koncepció ha jön gondolni rá. 

Is, vitathatóan, Pset 4 és 5 volt a legnehezebb psets hogy mi kellett ajánlania. Úgyhogy most már ez az 1 látna Pset C, , majd azt követően, hogy mi vagyunk a webes programozás. Szóval gratulálok magatokat szerzés át a legkeményebb púp a CS50. 

Továbblépve a Huff'n Puff, a toolbox erre Pset lesznek Huffman fák, így megértése nem csak, hogy bináris fák a munka, hanem a kifejezetten Huffman fák, miként ők épített. És akkor mi lesz egy csomó forgalmazási kód ebben Pset, és mi a meglátás, hogy valóban egyes kód talán nem lesz képes teljesen megérteni még, és így ezek lesznek. c fájlokat, de akkor a kísérő. h fájlok ad nekünk elég megértését, hogy szükség van, hogy tudjuk, hogyan működnek azok a funkciók vagy legalábbis mit kellene tenni - a be-és kimenetek - még akkor is, ha nem tudjuk, mi történik a fekete doboz vagy nem érti, mi történik a fekete doboz belül. És végül, mint mindig, van szó, az új adatszerkezetek, bizonyos típusú csomópontok mutatnak bizonyos dolgokat, és így van, amelynek egy tollat ​​és papírt nem csak a tervezési folyamat és ha akarsz, hogy kitaláljuk, hogyan kell működnie Pset hanem közben hibakeresés. Egyszerre GDB mellett a tollat ​​és papírt, miközben vegye le mik az értékek, ahol a nyilak mutatnak, és hasonló dolgok. 

Először is nézzük meg Huffman fák. Huffman fák bináris fák, ami azt jelenti, hogy minden csomópont csak 2 gyermek részére. -Ban Huffman fák a jellemző az, hogy a leggyakoribb értékek képviseli a legkevesebb bit. Láttuk előadás példákat Morse-kódot, amely egyfajta konszolidált néhány betű. Ha megpróbálja lefordítani a A vagy E, például te fordítás, hogy gyakran, így ahelyett, hogy használja a teljes készlet a bitek sorszámát az adott szokásos adatok típusát, tömöríteni le, hogy kevesebb, majd ezeket a leveleket, akik kevesebb gyakran képviseli a hosszabb bit mert megengedheti magának, hogy ha mérjük ki a frekvenciákat, hogy ezek a levelek jelennek meg. Mi van egyforma elképzelés itt Huffman fák hol vagyunk, hogy egy lánc, egyfajta út, hogy eljusson az egyes karaktereket. És akkor a karakter, aki a legtöbb frekvencia lesznek képviselve a legkevesebb bit. 

Az út, amit építeni a Huffman fa van azáltal, hogy az összes a karakterek jelennek meg a szövegben és számítási azok gyakoriságát, milyen gyakran jelennek meg. Ez lehet akár egy száma, hogy hányszor jelenik meg a leveleket vagy esetleg egy százaléka az összes karakter hány mindegyik jelenik meg. És mit csinál az, ha már az összes, hogy Felvázolta, akkor keresse meg a 2 legalacsonyabb frekvenciák, majd kössük össze őket, mint a testvérek ha majd a szülő csomópont a frekvencia, amely az összege a 2 gyermek. És akkor megegyezés mondani, hogy a bal oldali csomópont, Ön következik, hogy követve a 0 ág, majd a jobb szélső csomópont az 1 ág. Mint láttuk Morse-kódot, az egyik az volt, hogy megvagy, ha csak egy hangjelzés és a sípszó volt egyértelmű. Ez lehet vagy legyen 1 betű vagy lehet egy sorozata 2 betű. És mi Huffman fák csinál, mert a természet a karakterek vagy a mi végső aktuális karaktert, hogy az utolsó csomópont a fióktelep - utalunk azokra a levelek - alapján, hogy nem lehet semmi félreérthető szempontjából melyik betű akarsz kódolni a sorozat bitek mert sehol mentén a biteket reprezentáló 1 betű fogsz találkozni más egész levelet, és nem lesz semmi zavar ott. De megyünk be példákat, hogy ti valóban láthatjuk, hogy ahelyett, hogy nekünk csak azt mondom, hogy ez igaz. 

Nézzünk egy egyszerű példát a Huffman fa. Nekem van egy húr van, amely 12 karakter hosszú. Nekem van 4 A, 6 Bs és 2 Cs. Az első lépés az lenne, hogy számít. Hányszor Egy megjelenni? Úgy tűnik, 4-szer a húr. B megjelenik 6-szor, és a C 2-szer megjelenik. Természetesen fogok mondani, én vagyok a B leggyakrabban így azt akarom, hogy képviselje a B a legkevesebb bitek száma, a legkevesebb 0s és 1s. És akkor én is lesz számíthat C megkövetelni a legnagyobb összeget a 0s és 1s is. Először is, mit csináltam itt helyeztem őket emelkedő sorrendben a gyakoriság. Látjuk, hogy a C és az A, ezek a 2 legalacsonyabb frekvenciákon. Készítünk egy szülő csomópont, és hogy szülő csomópont nem rendelkezik írni társítva, de ez nem is a frekvencia, amely az az összeg. Az összeg válik 2 + 4, amely 6. Ezután kövesse a bal ága. Ha voltunk, hogy 6 csomópontot, akkor mi lenne követni 0, hogy a C , majd 1, hogy eljusson A. Tehát most van 2 csomópont. Megvan az érték 6 és akkor mi is van egy másik csomópont az érték 6. És ezek 2 nem csak a 2 legalacsonyabb, hanem csak a 2, hogy marad, így csatlakozni a másik szülő, az összeg pedig 12. Tehát itt van a Huffman-fa hogy hol kap a B, ez csak az 1-es bit majd eljutni A mi lett volna 01, majd a C, amelynek 00. Tehát itt azt látjuk, hogy tulajdonképpen mi ezeket képviselő karakter 1 vagy 2 bit ahol a B, mint előre, van a legkisebb. Aztán várta C van a legtöbb, de mivel ez egy ilyen kis Huffman fa, akkor az A is képviseli 2 bit szemben valahol a közepén. 

Csak, hogy menjen át egy másik egyszerű példa a Huffman fa, mondod, hogy a húr "Hello". Mit csinálsz először is ezt fogod mondani, hányszor jelent H jelenik meg ez? H egyszer jelenik meg, majd e egyszer jelenik meg, és akkor már l kétszer megjelenő és o megjelenő egyszer. És így aztán várunk, amely levél képviseli a legkisebb bitek számát? [Hallgató] l. >> L. Yeah. l igaza van. Elvárjuk l képviseletét a legkevesebb bit mert l használják leginkább a húr "Hello". Mit fogok most csinálni a döntetlen ezeket a csomópontokat. Van 1, amely hidrogénatom, majd egy másik 1, amely az e, és azután egy 1, ami az o - Most én vagyok a beszabályozását is -, majd 2, ami l. Akkor azt mondom, az is, hogy építek egy Huffman fa, hogy megtalálják a 2 csomópontok a legkevesebb frekvenciák és azokat testvérek létrehozásával szülő csomópont. Itt van 3 csomópontok a legalacsonyabb frekvenciával. Ők mind 1. Tehát itt úgy döntünk, melyiket fogjuk összekapcsolni először. Tegyük fel, hogy válassza ki a H és az e. Összege 1 + 1 = 2, de ez csomópont nincs betű társítva. Csak tartja az értéket. Most nézd meg a következő 2 legalacsonyabb frekvenciákon. Ez 2 és 1. Ez lehet akár az említett 2, de fogom ezt választja. Az összeg 3 lehet. És végül, csak van 2 balra, így aztán, hogy lesz 5. Aztán itt is, mint az várható volt, ha töltse ki a kódolás, hogy a 1s mindig a megfelelő ágat, és 0-ák a balt. Aztán ott van l képviselők csak 1 bit, majd a 2-o és azután a 2-e, majd a H-esik le a 3 bites. Szóval lehet továbbítani ezt az üzenetet "Hello" helyett ténylegesen a karakterek mellett csak 0s és 1s. Ne feledje azonban, hogy számos esetben kellett kapcsolatai a frekvencia. Mi volna sem csatlakozott a H és az o 1. talán. Vagy később, amikor már megvolt a l képviselők 2 valamint az egyesített 1, például a 2, mi volna összekapcsolt közül az egyik. 

És így, amikor elküldi a 0s és 1s, hogy valóban nem garantálja hogy a kedvezményezett teljes mértékben olvasni az üzenetet rögtön a denevér mert lehet, hogy nem tudja, hogy melyik döntés, amit tett. Tehát, ha van dolgunk Huffman tömörítés, valahogy el kell mondanunk a címzettnek az üzenetünk, hogy úgy döntöttünk, - Tudniuk kell, valamilyen további információk Amellett, hogy a tömörített üzenet. Meg kell érteniük, hogy mi a fa néznek ki, hogyan ténylegesen ezeket a határozatokat. 

Itt éppen csinál példákat a tényleges szám, de néha akkor is van egy Huffman fa alapján a frekvenciát, amelynél betűk jelennek meg, és ez pontosan ugyanazt a folyamatot. Itt vagyok kifejezni azt szempontjából százalékos, vagy egy része, és ezért itt pontosan ugyanaz a dolog. Találom a 2 legalacsonyabb Összefoglalva őket, a következő 2 legalacsonyabb, összefoglalva azokat, amíg egy teljes fa. Bár tudnánk csinálni akár úgy, ha van dolgunk százalékos, azt jelenti, hogy mi elosztjuk a dolgokat, és foglalkozik tizedes vagy inkább úszik ha gondolsz adatszerkezetek a fejét. Mit tudunk úszik? Mi egy gyakori probléma, amikor dolgunk úszók? [Hallgató] Pontatlan számtani. >> Igen. Pontatlanság. Mivel a lebegőpontos pontatlanság, mert ez Pset hogy mi győződjön meg arról, , hogy ne vesszenek el értékeket, akkor mi tényleg lesz foglalkozik a gróf. Tehát, ha úgy döntesz, hogy úgy gondolja, a Huffman csomópont, ha megnézi vissza a szerkezet itt, ha megnézi a zöldek van egy frekvencia társított valamint azt hangsúlyozza, hogy egy csomópont a tőle balra, valamint csomópont annak jobbra. És akkor a piros is ott is van egy karakter velük kapcsolatban. Nem megyünk, hogy külön is a szülők, majd a végleges csomópont, amit utalnak a levelek, hanem inkább csak meg NULL értékeket. Minden node mi lesz egy karaktert, a szimbólumot, hogy csomópont jelent, akkor gyakorisággal valamint egy mutatót a balra gyermek, valamint a jobb gyermeknek. A levelek, amely akkor a legalsó, ezen kívül el kellene csomópont mutató azok balra és azok helyes, de mivel ezek az értékek nem mutatnak tényleges csomópontok, mi lenne, ha értékük lehet? >> [Hallgató] NULL. >> NULL. Pontosan. Íme egy példa arra, hogyan lehet, hogy képviselje a frekvencia úszók, de fogunk foglalkozni azt egészek, így minden tettem a változás az adattípus van. 

Menjünk tovább egy kicsit összetett példát. De most, hogy már kész is az egyszerű, csak ugyanazt a folyamatot. Talál a 2 legalacsonyabb frekvenciák összefoglalva a frekvenciák és ez az új frekvencia a szülő csomópont, amely azután kiemeli annak balra a 0 ág és a jobb az 1 ág. Ha megvan a string "Ez CS50", akkor mi számít, hogy hányszor kerül T említettük, h említettük, i, s, C, 5, 0. Akkor mit csináltam itt a piros csomópontok csak ültetett, Azt mondtam, hogy megyek, hogy ezek a karakterek végül alján az én fa. Ezek lesznek az összes levél. Akkor mit tettem, hogy én rendezve őket gyakorisága növekvő sorrendben, és ez valójában az is, hogy a Pset kódot csinálja ez rendezi azt gyakoriságát, majd betűrendben. Tehát azt a számok első, majd betűrendben a frekvencia. Akkor mit szeretnék csinálni, hogy én fogja találni a 2 legalacsonyabb. Ez 0-tól 5. Szeretném összefoglalni őket, és ez 2. Aztán folytatódni fog, megtalálja a következő 2 legalacsonyabb. Ez az a két 1-esek, és majd azok kerülnek 2 is. Most már tudom, hogy az én következő lépés az lesz, hogy csatlakozik a legkevesebb, amely a T, a 1, majd választva a csomópontok a 2 mint a frekvencia. Tehát itt van 3 lehetőség. Mit fogok tenni a dia éppen vizuálisan rendezni őket az Ön számára így láthatja, hogyan építek fel. Mi a kódot, és a forgalmazás kód fog tenni kellene csatlakozni a T-1 a 0 és 5 csomópont. Tehát akkor azt összegek 3, majd folytatjuk a folyamatot. A 2 és a 2 most már a legkisebb, így aztán ezen összeg 4-ig. Mindenki követően eddig? Oké. Akkor azután, hogy megvan a 3 és a 3, amelyeket meg kell összeadni, így ismét Én csak kapcsolási úgy, hogy láthatja vizuálisan úgy, hogy nem lesz túl rendetlen. Aztán van egy 6, majd a végső lépés, most, hogy már csak 2 csomópont összeadjuk ezeket, hogy a gyökér a fa, amely 10. És a 10-es számú van értelme, mert minden egyes csomópont képviseli, azok értékét, a frekvencia szám volt, hogy hányszor jelent meg a húr, és akkor mi van 5 karakter a string, hogy van értelme. Ha megnézzük ki, hogyan fog valójában kódolni, ahogy az várható volt, az i és az s, amelyek megjelennek a leggyakrabban képviseli a legkevesebb bit. 

Legyen óvatos itt. A Huffman fák esetében ténylegesen számít. A nagybetűs S más, mint egy kisbetűs s. Ha lenne "Ez CS50" nagybetűkkel, akkor a kisbetűvel s csak kétszer jelenik meg, lenne egy csomópont a 2 értékét, majd nagybetűs S csak akkor egyszer. Akkor a fa változna struktúrákat, mert valóban van egy extra levél itt. De az összeg még mindig 10-ig. Ez az, amit mi valójában lesz hívja a checksum, hozzáadása minden számít. 

Most, hogy már lefedett Huffman fák, mi is belevetik magukat Huff'n Puff, a Pset. Fogunk kezdeni egy részének kérdést, és ez fog kapni megszokott bináris fák és hogyan kell működtetni körül, hogy: rajz csomópontok, ami a saját typedef struct egy csomópont, és látván, hogyan lehet beilleszteni egy bináris fa, az egyik, hogy van rendezve, áthaladó, és ilyesmik. Ez a tudás mindenképpen segíteni fog neked, amikor belevetik magukat a Huff'n Puff rész A Pset. A standard kiadás a Pset, a feladat végrehajtása Puff, és a hacker változata a feladat végrehajtása Huff. Mit csinál, Huff tart szöveget, majd azt lefordítja a 0s és 1s, így a folyamat, hogy mi volt fent, ahol számít a frekvenciák és ezután a fát, majd azt mondta: "Hogyan lehet T?" T jelentése 100, ilyesmi, majd Huff venné a szöveget, majd a kimenet bináris. De azért is, mert tudjuk, hogy szeretné, hogy a címzett az üzenet hogy újra pontosan ugyanazon a fán, ez is tartalmaz információkat a frekvencia számít. Aztán Puff adott egy bináris fájlt 0s és 1s és mivel még a tájékoztatás a frekvenciákat. Mi lefordítani az összes ilyen 0s és 1s vissza az eredeti üzenet volt, úgyhogy kicsomagoláskor ezt. Ha csinálsz a standard verzió, akkor nem kell végrehajtania Huff, így akkor csak használ a személyzet végrehajtását Huff. Vannak utasításokat a specifikációt, hogyan kell csinálni. Futtathatja a személyzet végrehajtását Huff upon egy bizonyos szöveges fájl majd, hogy a kibocsátás, mint a bemeneti Puff. 

Mint már korábban említettem, van egy csomó forgalmazási kód ez. Fogom kezdeni megy rajta. Fogom tölteni a legtöbb időt a. H fájlok mert a. ac fájlokat, mert van a. h és ez biztosítja számunkra a prototípusok a funkciók, nem teljes mértékben meg kell érteniük, hogy pontosan - Ha nem érti, mi folyik a. Ac fájlokat, akkor ne aggódj túl sokat, de mindenképpen próbálja meg, hogy egy pillantást, mert adhat néhány tanácsot és ez hasznos, hogy megszokja olvasni más emberek kódot. 

Keresi huffile.h, a hozzászólások kijelenti, egy réteg absztrakció a Huffman-kódolt fájlokat. Ha lemegyünk, azt látjuk, hogy van egy legfeljebb 256 szimbólum, hogy szüksége lehet kódokat. Ez magában foglalja az összes az ábécé betűit - kis-és nagybetűk - majd a szimbólumok és számok, stb Aztán itt van egy bűvös szám azonosítja a Huffman-kódolt fájlt. Belül a Huffman-kód fognak egy bizonyos bűvös szám társított fejléc. Ez így fog kinézni, csak egy véletlen mágikus szám, de ha lefordítani a be ASCII, akkor a ténylegesen kifejti HUFF. Itt van egy struct a Huffman-kódolt fájlt. Ott van az összes ezeket a jellemzőket társított Huff fájlt. Aztán meg itt van a fejlécben a Huff fájlt, így hívjuk Huffeader ahelyett, hogy az extra h, mert úgy hangzik ugyanaz egyébként. Aranyos. Van egy bűvös szám társul hozzá. Ha ez egy valódi Huff fájlt, ez lesz a szám fölött, ez a mágikus 1. És akkor lesz egy tömb. Így minden egyes szimbólum, akik közül 256, ez fog felsorolni milyen gyakorisággal e jelképek a Huff fájlt. És végül, van egy ellenőrző a frekvenciák amelyeket össze kell az összege e frekvenciák. Szóval, ez az, amit a Huffeader van. Aztán van néhány funkció, hogy visszatérjen a következő bit a Huff fájlban valamint ír egy kicsit a Huff fájlt, majd ez a funkció itt, hfclose, hogy valóban bezárja a Huff fájlt. Korábban dolgunk egyenes csak fclose, de ha van egy Huff fájl, ahelyett, hogy fclosing amit valójában csinálsz az hfclose és hfopen azt. Ezek konkrét feladatok a Huff fájlokat fogunk foglalkozni. Aztán itt azt olvassuk a fejlécben és írjuk be a fejléc. 

Csak, ha elolvassa a. H fájlban tudjuk milyen lesz az értelme, amit egy Huff fájl lehet, milyen tulajdonságokkal rendelkezik, anélkül, hogy ténylegesen megy a huffile.c, amely, ha merüljön, lesz egy kicsit bonyolultabb. Ez az összes fájl I / O Itt foglalkozó mutatók. Itt azt látjuk, hogy mikor hívjuk hfread, például, még mindig foglalkozik fread. Nem vagyunk megszabadulni ezeket a funkciókat teljesen, de küldünk e kell gondoskodni belül a Huff fájlt, ahelyett, hogy az egészet magunkat. Akkor bátran átkutat keresztül ha kíváncsi és megy, és húzza a réteget vissza egy kicsit. 

A következő kép, hogy mi megyünk, hogy nézd meg tree.h. Mielőtt a Walkthrough diák azt mondta, várjuk Huffman csomópont és tettünk egy typedef struct csomópont. Arra számítunk, hogy egy szimbólum, a frekvenciát, majd a 2 node csillagok. Ebben az esetben mit csinálunk ez lényegében azonos kivéve, hogy a csomópont fogunk hívni őket fákat. Van olyan funkció, amikor telefonál, hogy fát ad vissza egy fa mutató. Vissza az Speller, amikor arra, hogy egy új csomópont azt mondta, node * új szó = malloc (sizeof), és ilyesmik. Alapvetően mktree fog foglalkozni, hogy az Ön számára. Hasonlóképpen, ha azt szeretné, hogy távolítsa el a fa, annak érdekében, hogy ez lényegében felszabadítása a fát, ha végeztél vele, ahelyett, hogy kifejezetten kéri ingyenesen, hogy te valójában csak fogja használni a funkció rmtree ahol át a mutatót, hogy a fát, majd tree.c vigyázni fog, hogy az Ön számára. 

Bízunk a tree.c. Arra számítunk, hogy ugyanazokat a funkciókat, kivéve, hogy a végrehajtás is. Ahogy az várható volt, amikor telefonál mktree azt mallocs akkora, mint egy fa, egy mutató, inicializálja az összes értékeket a NULL értéket, így 0s vagy NULL, majd visszatér a mutatót, hogy a fa, amit csak malloc'd neked. Itt, amikor telefonál eltávolítani fa először gondoskodik arról, hogy ön nem kettős felszabadítása. Ez gondoskodik arról, hogy valóban van egy fa, amely az eltávolítani kívánt. Itt azért, mert a fa is a gyermekek, hogy ez mire jó ez rekurzívan hívja távolítsa el a bal oldali fa csomópont a fa valamint a megfelelő csomópont. Mielőtt felszabadítja a szülő, meg kell szabadítani a gyerekeket is. Szülő is felcserélhető root. Az első szülő, úgy mint az ük-ük-ük-ük-nagyapja vagy nagymama fa, először meg kell szabadítani azokat a szinteket először. Így áthalad az alsó, szabad e, és utána gyere vissza, szabad e, stb Szóval ez fa. 

Most nézzük erdőben. Forest, ahol helyet az összes Huffman fák. Ez azt mondja, hogy mi megy, hogy egy úgynevezett telek , amely egy mutató egy fa, valamint egy mutató egy telek hívott következő. Milyen struktúra jelent ez a fajta néz ki? Ez a fajta mondja, hogy ott van. Jobb itt. A csatolt listában. Látjuk, hogy ha van egy telek ez olyan, mint egy láncolt lista a parcellák. Egy erdő definíció szerint a láncolt lista a telkek, és így a szerkezete erdő mi csak megy, hogy egy mutatót az első telek és hogy a telek egy fán belül, vagy inkább emlékeztet egy fa , majd rámutat, hogy a következő telek, így tovább és így tovább. Ahhoz, hogy egy erdőben nevezzük mkforest. Aztán van néhány nagyon hasznos funkciók itt. Van, ahol meg vedd át az erdőben, majd a visszatérési érték egy fa *, a mutató egy fa. Mit csákány fog tenni ez fog menni az erdőbe, hogy te mutató majd távolítsa el a fa, a legalacsonyabb frekvencia, hogy az erdészeti majd adja meg a mutatót, hogy a fát. Miután hívja csákány, a fa nem létezik az erdőben már, de a visszatérési érték a mutatót, hogy a fát. Akkor növény. Feltéve, hogy adja át a mutatót egy fa, amely egy nem-0 frekvencia, milyen növény fog tenni ez lesz az erdőben, hogy a fa, és a növény, hogy a fa belsejében az erdőre. Itt van rmforest. Hasonló eltávolítani a fa, ami alapvetően megszabadított minden kedves fákat számunkra, eltávolítás erdő szabad mindent tartalmazott az erdőben. 

Ha megnézzük a forest.c, akkor várható, hogy legalább 1 rmtree parancs van, mivel a szabad memória az erdőben, ha egy erdei fák vannak benne, majd végül fogsz, hogy távolítsa el a fák is. Ha megnézzük a forest.c, van mkforest, amely mint várunk. Mi malloc dolgokat. Mi inicializálni az első telek az erdőben, mint NULL, mert üres kezdeni, akkor azt látjuk, csákány, amely visszaadja a fa a legkisebb súly, a legalacsonyabb frekvencia, majd megszabadul az adott csomópont, amely rámutat arra, hogy a fa és a következő egy, ezért úgy, hogy ki a láncolt lista az erdőre. És akkor itt van növény, amely beszúr egy fa a láncolt listába. Mit jelent az erdő szépen tartja sorrendje nekünk. És végül, van rmforest, és mint várható volt, mi rmtree hívott oda. 

Keresi az elosztás kódot eddigi huffile.c valószínűleg messze a legnehezebb megérteni, míg a többi fájl maguk is elég egyszerű, hogy kövesse. A tudásunk mutatókat és a kapcsolódó listákat és ilyen, tudtuk követni nagyon jól. De minden kell ahhoz, hogy valóban győződjön meg arról, hogy teljes mértékben megértsék a. H fájlok mert meg kell hívni ezeket a funkciókat, foglalkozik azokkal a visszatérési érték, úgyhogy győződjön meg róla, hogy megértsük, milyen intézkedéseket fog végezni Valahányszor hívsz egy ilyen funkciókat. De valójában megértése belül ez nem teljesen szükséges, mert van ilyen. H fájlokat. Jelenleg 2 több fájl maradt disztribúciós kódot. 

Nézzük dump. Dump által kommentezni ide tart Huffman-tömörített fájl majd lefordítja és szeméttárolót annak minden tartalmát ki. Itt azt látjuk, hogy hív hfopen. Ez a fajta tükrözés fájlba * bemenet = fopen, és akkor adja át az információkat. Már majdnem azonosak, kivéve helyett egy file * te halad a Huffile; helyett fopen te halad hfopen. Itt olvasható a fejlécben az első, ami elég hasonló ahhoz, ahogy azt olvassuk a fejlécben egy bitmap fájlt. Amit mi csinálunk itt ellenőrzi, hogy vajon a fejléc információ tartalmazza a megfelelő bűvös szám, amely azt jelzi, hogy ez egy valódi Huff fájl, akkor az összes ilyen ellenőrzések, hogy győződjön meg arról, hogy a fájl, hogy nyitva van egy tényleges dohogott fájl vagy sem. Amit ez tesz, kiadja az frekvenciái minden szimbólumok látjuk egy terminál egy grafikus tábla. Ez a rész lesz hasznos. Ez egy kicsit, és így szól apránként a változó bit, majd kinyomtatja. Szóval, ha én hívni dump hth.bin, ami annak a következménye, dúlt a fájl a személyzet megoldás, én értem. Ez kimenetre az összes ezeket a karaktereket, majd üzembe a frekvencián, amelyen megjelennek. Ha megnézzük, a legtöbbjük 0s kivéve ezt: H, amely kétszer jelenik meg, és azután a T, amely úgy tűnik, egyszer. És akkor itt van a tényleges üzenetet 0s és 1s. Ha megnézzük hth.txt, ami feltehetően az eredeti üzenet, melyet dohogott, várunk néhány Hs és Ts ott. Pontosabban, azt várjuk, hogy csak 1 T és 2 Hs. Itt vagyunk hth.txt. Ez valóban rendelkezik HTH. Tartalmaz ott, bár nem látom, van egy új sor karakter. A Huff fájl hth.bin is kódoló újsor karaktert is. Itt mert tudjuk, hogy a megbízás HTH majd új sor, láthatjuk, hogy talán a H képviseli csak egy egyszeri, 1 és azután a T jelentése valószínűleg 01. és majd a következő H-1 is és akkor van egy újsor jelzett két 0s. Cool. 

És végül, mivel van dolgunk több. C és. H fájlokat, megyünk, hogy egy szép összetett érv a fordító, és ezért itt van egy Makefile ami kiíratás az Ön számára. De valójában, el kell járni, hogy a saját puff.c fájlt. A Makefile valójában nem foglalkozik, hogy puff.c az Ön számára. Elmegyünk, hogy rajtad múlik, hogy a Makefile. Ha belép egy hasonló parancsot, hogy minden, például, meg fog tenni minden őket. Nyugodtan nézd meg a példákat a Makefile-t a múlt Pset valamint a folyamatos le ezt, hogy hogyan lehet, hogy képes arra, hogy a Puff fájl szerkesztésével a Makefile. Ez körülbelül azt disztribúciós kódot. 

Amint már ütött át, hogy aztán itt is csak egy emlékeztető hogy hogyan fogunk foglalkozni a Huffman csomópontokat. Mi nem lesz nevezve őket csomópontok többé, mi lesz nevezve őket a fák hová fogunk képviselni a szimbólum a char, azok gyakoriságát, az előfordulások számát, egy egész. Mi használja, mert ez pontosabb, mint egy úszó. Aztán van egy másik mutatót balra gyermek, valamint a megfelelő gyermek. Az erdő, mint láttuk, csak egy láncolt lista a fák. Végül, amikor a mi kiépítése a mi Huff fájl, azt akarjuk, hogy erdészeti tartalmazzon csak 1 fa - 1 fa, 1 root több gyermek. Korábban, amikor éppen, hogy a Huffman fák, kezdtük el azáltal, hogy az összes csomópont rá a képernyőre és azt mondja: mi megy, hogy ezek a csomópontok, végül ők lesznek a levelek, és ez a szimbólum, ez a frekvencia. A mi erdőben, ha már csak 3 betű, ez egy erdő 3-fák. Aztán, ahogy haladunk tovább, amikor hozzá az első szülő, tettünk egy erdő 2 fákat. Mi eltávolítjuk 2 of azoknak a gyermekeknek a mi erdei, majd helyette egy szülő csomópont hogy már a 2 csomópontokat, mint a gyermekek. És végül, az utolsó lépést, hogy a példa az As, Bs és Cs lenne a végső anyavállalat, és így akkor az járna a teljes száma a fák az erdő 1-re. Mindenki nézze meg, hogyan indul ki több fák az erdő és a végén 1? Oké. Cool. 

Mit kell tennünk a Puff? Amire kell tennie, hogy, mint mindig, hogy megadja nekünk a megfelelő típusú bemenet hogy mi is valójában a program futtatásához. Ebben az esetben ők fogják ad nekünk után az első parancssori argumentum További 2: A fájlt akarunk kitömöríteni, és a kimenet a kitömörített fájlt. De ha egyszer teszünk arról, hogy adja át nekünk a megfelelő mennyiségű értékek, szeretnénk, hogy a bemenet egy Huff fájlt vagy sem. És akkor egyszer mi garantáljuk, hogy ez egy Huff fájlt, majd szeretnénk építeni a fa, felépíteni a fát úgy, hogy megfelel a fát, hogy a személy, aki az üzenetet küldte épült. Majd miután építünk a fát, akkor tudjuk kezelni a 0s és 1s hogy telt el, követik azok mentén fa, mert azonosak, majd írni, hogy az üzenetet ki, értelmezze a biteket vissza a karakter. És akkor a végén, mert dolgunk mutató itt, szeretnénk, hogy győződjön meg arról, hogy mi nincs memóriavesztés és hogy szabad mindent. 

Biztosítva a megfelelő használat öreg számunkra most. Mi egy olyan bemenet, ami lesz a neve, a fájl puff, és aztán meg egy kimeneti, így a fájl neve a puffasztott kimenet, melyik lesz a szöveges fájl. Ez használat. És most szeretnénk biztosítani, hogy a bemenet dohogott vagy sem. Gondolkodás vissza, volt valami a forgalmazási kódot, ami segíthet nekünk A megértés, hogy egy fájl dohogott, vagy nem? Volt információt huffile.c a Huffeader. Tudjuk, hogy minden Huff fájl egy Huffeader társítva egy bűvös szám valamint egy sor a frekvenciák minden szimbólum valamint egy ellenőrző összeg. Tudjuk, hogy, de azt is vett egy kandikál dump.c, amelyben azt olvasott egy Huff fájlba. És így kell csinálni, hogy meg kellett ellenőrizni, hogy valóban volt dohogott, vagy sem. Így talán jönne dump.c mint struktúra a mi puff.c. Vissza az Pset 4 amikor már a fájl copy.c hogy másolt RGB tripletek és azt értelmezni, hogy a detektívregény és átméretezése hasonlóképpen, mit tehetne éppen a parancsot, mint a cp dump.c puff.c és használhatja a kódot is. Azonban ez nem lesz olyan egyszerű egy folyamat fordításához a dump.c a puff.c, de legalább ad valahol kezdeni arról, hogyan biztosítható, hogy a bemenet valójában dohogott vagy nem valamint néhány más dolog. Mi biztosítja a megfelelő használatot, és biztosította, hogy a bemenet dohogott. Minden alkalommal, hogy már kész, hogy mi megtettünk megfelelő hibaellenőrzés, így visszatérő és kilépés a funkciót, ha valamilyen hiba lép fel, ha van egy kis probléma. 

Most mit akarunk csinálni a kiépítése a tényleges fa. Ha megnézzük az erdőben, van 2 fő funkciói hogy fogunk akarnak lenni nagyon ismerik. Ott van a Boole-függvény növény, hogy a növények egy nem-0 frekvencia fa belsejében a erdő. És így ott át a mutató egy erdő és egy mutató a fa. Gyors kérdés: Hány erdők van, amikor az épület egy Huffman fa? A erdő, mint a mi, vászon, ugye? Szóval csak megy, hogy 1 erdőben, de fogunk több fákat. Tehát mielőtt hívja növény, akkor valószínűleg fog szeretnénk, hogy az erdő. Van egy parancsot, hogy ha belenéz forest.h, hogyan lehet, hogy egy erdőben. Akkor ültess fát. Tudjuk, hogyan kell csinálni. És akkor is vegye a fa az erdőből, eltávolítása egy fa a legalacsonyabb súlya és így a mutatót, hogy a. Gondolkodás vissza, amikor csinálunk a példák magunkat, amikor mi voltunk rajz ki, egyszerűen csak hozzá a linkeket. De itt nem csak hozzá a link, gondolni rá, inkább te eltávolítása 2 e csomópontok, majd helyette egy újat. Kifejezni, hogy mind a szedés és ültetési, te szedés 2 fákat majd ültetési másik fa amely a 2 fát, hogy felvette a gyermekek. Építeni Huffman a fa, akkor olvassa el a szimbólumok és frekvenciák érdekében mert a Huffeader ad, hogy az Ön számára, ad egy sor a frekvenciákat. Így megy előre, és ne törődj semmit a 0 benne mert nem akarjuk, 256 levél végén is. Mi csak szeretnénk, a levelek száma, melyek karakterek hogy a ténylegesen használt fájl. Tud olvasni ezek a szimbólumok, és minden egyes ilyen szimbólumok, amelyek nem-0 frekvenciák, ezek lesznek fák. Mit tehetünk, minden alkalommal, amikor olvas egy nem-0 frekvenciájú jel, lehet ültetni azt a fát az erdőben. Miután növény a fák az erdőben, akkor csatlakozhat a fák, mint testvérek, így megy vissza az ültetés és szedés ahol kiválaszthatja 2, majd 1 üzem, ha ez 1, hogy a növény a szülő a 2 gyerek, amit szedett. Tehát a végeredmény lesz egy fát az erdő. Ez hogyan készítsd el a fát. 

Van néhány dolog, ami baj van mert mi dolgunk, hogy új fákat és kezelésére szolgáló mutatók és ilyesmik. Mielőtt amikor dolgunk mutatók, valahányszor malloc'd akartuk, hogy megbizonyosodjon arról, hogy nem adott vissza nekünk NULL pointer értéket. Tehát több lépést ezen a folyamatban ott lesznek számos esetben amennyiben a program sikertelen lehet. Mit akarok, azt szeretnénk, hogy győződjön meg arról, hogy kezeli a hiba, és a spec azt mondja, hogy kezelni őket kecsesen, így szeretnék nyomtassa ki egy üzenetet, hogy a felhasználó azt mondta nekik, miért program leszokni majd azonnal kilép azt. Ehhez hibakezelés, ne feledjük, hogy szeretné, hogy ellenőrizze minden egyes alkalommal, hogy ott lehet a hiba. Minden egyes alkalommal, hogy te, hogy egy új mutató azt szeretnénk, hogy győződjön meg arról, hogy ez sikeres. Mielőtt amit mi a teendő az, hogy egy új mutató és malloc azt, és akkor mi lenne ellenőrizni, hogy ez a mutató értéke NULL. Tehát ott lesznek Bizonyos esetekben, ahol csak csinálni, de néha te valójában hív egy függvényt belül ez a funkció, ez az egyik, hogy csinál a mallocing. Abban az esetben, ha megnézzük vissza az egyes funkciók a kódot, néhány közülük Boole-függvények. Abban az elméleti esetben, ha van egy Boole-függvény neve foo, alapvetően, akkor feltételezhetjük, hogy amellett, hogy megteszi, ami foo nem, mivel ez egy Boole-függvény, visszatér igaz vagy hamis - igaz, ha sikeres, hamis, ha nem. Tehát szeretné, hogy ellenőrizze, hogy a visszatérési értéke az ize igaz-e vagy hamis. Ha ez hamis, azt jelenti, hogy fogunk nyomtatni kívánt valamiféle üzenet majd lépjen ki a programot. Amit akarok, hogy ellenőrizze a visszatérési értéke az ize. Ha a foo függvény hamis, akkor tudjuk, hogy találkozott valamilyen hiba és meg kell, hogy kilép a program. Egy módja ennek az, hogy olyan állapot, amelyben a tényleges funkciója maga a feltétel. Mondja foo vesz x. Mi lehet a feltétele if (foo (x)). Alapvetően ez azt jelenti, ha a végén végrehajtó ize visszatérési igaz, akkor meg tudjuk csinálni, mert a funkció, hogy értékelje foo hogy értékelni lehessen az egész feltételt. Szóval akkor ez hogyan lehet tenni valamit, ha a függvény igaz és sikeres. De ha te hibaellenőrzés, akkor csak ki akar lépni, ha a függvény a false. Mit tehetne az csak adj egy == hamis vagy csak adj egy bumm előtte és akkor if (! foo). Ezen belül szerv e feltétel akkor rendelkezik a hibakezelés, úgy tetszik, "Nem sikerült létrehozni ezt a fát", majd vissza 1 vagy valami ilyesmi. Mi az, hogy nem, de az, hogy bár foo vissza false - Mondja foo függvény igaz. Akkor nem kell hívni foo újra. Ez egy gyakori tévhit. Mert ez volt az állapota, ez már értékelt, így már az eredmény, ha a 'használ, hogy fa, vagy valami ilyesmi illetve növényi vagy csákány, vagy valami. Azt már ezt az értéket. Már kivégezték. Tehát célszerű használni Boole-függvények, mint a feltétel mert függetlenül attól, hogy Ön ténylegesen végrehajtja a test a hurok végrehajtja a funkciót egyébként. 

A második az utolsó lépés az üzenet beírását a fájl. Amint építeni a Huffman fa, majd írja meg az üzenetet, hogy a fájl nagyon egyszerű. Elég egyszerű most egyszerűen kövesse a 0s és 1s. És így megegyezés alapján tudjuk, hogy a Huffman fa a 0s jelezze balra és az 1s jelzik jobbra. Tehát, ha olvasni apránként, minden alkalommal, hogy kapsz a 0 akkor kövesse a bal ág, majd minden alkalommal, amikor olvasott egy 1 mész, hogy kövesse a jobb oldali ág. És akkor fogod folytatni, amíg bejön egy levél mivel a levelek lesznek végére az ágak. Hogyan lehet megmondani, hogy mi már megüt egy levél, vagy nem? Azt mondta korábban. [Hallgató] Ha a mutató a NULL. >> Igen. Meg tudja mondani, ha már megüt a levél, ha a mutató mind a bal és a jobb fák NULL. Tökéletes. Tudjuk, hogy szeretnénk olvasni apránként a mi Huff fájlba. Ahogy láttuk korábban dump.c, mit tettek ők azok értelmezni apránként a Huff fájlba és csak kinyomtatható mik azok bitek voltak. Nem megyünk, hogy csinálja. Fogunk csinál valamit, ami egy kicsit bonyolultabb. De mit tehetünk tudjuk vállalni, hogy kis kód, amely beolvassa a kicsit. Itt van az egész bit képviseli a jelenlegi kicsit, hogy vagyunk. Ez gondoskodik iterációjával összes bit a fájlt, amíg eléred a végén a fájl. Alapul véve, hogy akkor fogsz szeretnénk valamilyen iterator áthalad a fát. És azután az alapján, hogy a bit értéke 0 vagy 1, fogsz szeretnénk, hogy sem mozogni, hogy iterator balra vagy helyezze át a jobb egészen addig, amíg bejön egy levél, így egészen addig, amíg a csomópont, hogy te vagy a nem mutat semmilyen további csomópontok. Miért tesszük ezt egy Huffman fájlt, de nem Morse kód? Mert a Morse-kódot, van egy kis kétértelműséget. Mi is, mint, oh wait, már megüt egy levelet az út mentén, így talán ez a levél, mivel ha továbbra is csak egy kicsit, akkor eltalált volna egy levelet. De ez nem fog megtörténni Huffman kódolás, így biztos lehet benne, hogy az egyetlen módja, hogy fogunk ütni egy karakter , ha a csomópont a bal és a jobb gyerekek NULL. 

Végül szeretnénk felszabadítani minden kedves memóriát. Azt akarjuk, hogy mind a közeli a Huff fájlt, hogy már évek óta foglalkozik valamint meg kell szüntetnie az összes fát a mi erdőben. Alapján a végrehajtás, akkor valószínűleg szeretne majd hívni eltávolítani erdő ahelyett, hogy ténylegesen megy végig a fák magad. De ha tett ideiglenes bitófák, akkor szeretnénk felszabadítani azt. Tudod, hogy a kódot a legjobb, hogy tudd, hová elosztásának memória. És ha megy, először még Ellenőrző F'ing a malloc, látta, amikor malloc és gondoskodjanak arról, hogy szabadon az összes, hogy de aztán csak megy keresztül a kód, megértése, ahol lehet, hogy memóriát. Általában lehet, hogy csak azt mondja: "a végén a fájl Én csak megy, hogy távolítsa el erdő én Erdő," Tehát alapvetően világos, hogy memória, szabad, hogy a "Majd én is lesz, hogy bezárja a fájlt, majd a program fog lépni." De az, hogy az egyetlen alkalom, hogy a program kilép? Nem, mert néha lehetett egy hiba, ami történt. Talán nem tudja megnyitni a fájlt, vagy nem tudnánk, hogy egy másik fa vagy valamilyen hiba történt a memória kiosztás folyamatát és így vissza NULL. Egy hiba történt, és aztán visszatért, és kilép. Tehát azt szeretnénk, hogy győződjön meg arról, hogy minden lehetséges alkalommal, hogy a program kilép, szeretne felszabadítani az összes memóriát is. Ez nem csak az lesz a legvégén a fő funkciója, hogy lépjen ki a kódot. Azt akarod, hogy nézz vissza, hogy minden esetben, hogy a kód potenciálisan adhatja vissza idő előtt majd a szabad memória bármi értelme. Mondja el, hogy hívta, hogy erdő és vissza hamis. Akkor valószínűleg nem kell eltávolítani az erdő mert nincs erdő még. De minden ponton a kódot, ha lehet, vissza idő előtt azt szeretnénk, hogy győződjön meg arról, hogy az esetleges felszabadítani memóriát. 

Tehát, ha van dolgunk felszabadítani memória és tekintettel a potenciális szivárgás, azt akarjuk, hogy ne csak használja a megítélés és a logika hanem használja Valgrind annak megállapítására, hogy mi már megszabadult minden kedves memória helyesen vagy sem. Akkor sem futtatható Valgrind szóló Puff, és akkor kell is átadni a megfelelő számú parancssori érveket Valgrind. Futtathat, de a kimenet egy kicsit rejtélyes. Már ütött egy kicsit használt azt Speller, de még mindig szükség van egy kicsit több segítséget, így aztán fut néhány nagyobb zászlók, mint a szivárgás-ellenőrzés = teljes, hogy valószínűleg nekünk még néhány hasznos kimenetet Valgrind. 

Aztán egy másik hasznos tipp, amikor hibakeresés a diff parancs. Érheti el a személyzet végrehajtását Huff, fuss, hogy egy szöveges fájl, majd a kimenetet, hogy egy bináris fájl egy bináris fájlt Huff, egyedinek. Akkor, ha fut a saját puff e bináris fájl, akkor ideális, a kiadott szöveges fájl lesz azonos az eredeti egyik, hogy telt be Itt én vagyok a hth.txt mint a példa, és ez az egyik beszélt a spec. Ez szó szerint csak HTH, majd egy újsor. De határozottan, bátran és akkor határozottan arra ösztönzik, hogy hosszabb példa a szöveges fájl. 

Akár azt is, hogy egy lövés talán tömörítése, majd a kicsomagoláskor egyes fájlok használt Speller, mint a Háború és béke vagy Jane Austen, vagy valami ilyesmi -, hogy lenne ilyen hideg - vagy Austin Powers, fajta foglalkozó nagyobb fájlokat, mert akkor nem jön le, hogy ha használják a következő szerszám itt ls-l. Mi használt ls, amely alapvetően felsorolja az összes tartalom a mi aktuális könyvtárban. Átadás a zászló-l ténylegesen megjeleníti a méretét a fájlok. Ha valaki átmegy a Pset spec, tulajdonképpen végigvezeti létrehozása a bináris fájlt, A dúlt, és azt látja, hogy a nagyon kis fájlok a tér költségek tömörítse és fordítás minden ezen információk az összes frekvenciát, és a dolgok, mint például, hogy felülmúlja a tényleges haszon tömörítése a fájlt az első helyen. De ha futtatni néhány hosszabb szöveges fájl, akkor lehet látni, hogy elkezdi, hogy egy kis haszon A tömörítés a fájlokat. 

És végül, mi a régi haver GDB, ami biztosan megy jól jöhet is. 

Tudjuk bármilyen további kérdése van Huff fák, vagy a folyamat talán, hogy a fák vagy bármilyen más kérdésre Huff'n Puff? Oké. Maradok még egy kicsit. 

Köszönöm, mindenkinek. Ez volt Walkthrough 6. És sok szerencsét. 

[CS50.TV]