[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]