[Powered by Google Translate] [Návod - Problém Set 6] [Zamyla Chan - Harvard University] [To je CS50. - CS50.TV] 

Ahoj, všetci, vitajte na Walkthrough 6: Huff'n Puff. V Puff Huff'n, čo robíme sa bude zaoberať súboru Huffman komprimovaného a potom nafukovanie ju späť hore, tak dekompresiu to, takže môžeme preložiť z 0s a 1s, že užívateľ odošle dotaz a previesť ho späť do pôvodného textu. Pset 6 bude celkom v pohode, pretože budete vidieť niektoré z nástrojov ktoré ste použili v PSet 4 a PSet 5 a druhu a zlúčiť ich do 1 pekne úhľadné koncepcie keď príde na to myslieť. 

Tiež, pravdepodobne, Pset 4 a 5 boli najnáročnejšie psets, ktoré sme mali ponúknuť. Takže od teraz, máme túto 1 väčšiu PSet v C, a potom po tom sme na programovanie pre web. Takže gratulujem seba pre prekonanie najťažšie hrb v CS50. 

Pohybujúce sa na pre Puff Huff'n, naše toolbox pre tento PSet sa bude Huffman stromy, takže pochopenie nielen ako binárne stromy prácu, ale aj špecificky Huffman stromy, ako to početne sú. A potom budeme mať veľa distribučné kódu v tomto PSet, a my prídeme vidieť, že skutočne niektoré z kódu by sme neboli schopní plne pochopiť ešte, a tak ti budú. c súbory, ale potom ich sprievod. h súbory nám dá dostatok pochopenia, že potrebujeme, aby sme vedeli, ako tieto funkcie pracujú alebo aspoň to, čo majú robiť - ich vstupov a výstupov - aj keď nevieme, čo sa deje v čiernej skrinke, alebo nechápu, čo sa deje v čiernej skrinke vnútri. A potom konečne, ako obvykle, máme čo do činenia s novými dátovými štruktúrami, špecifické typy uzlov, ktoré poukazujú na niektoré veci, a tak tu majú ceruzku a papier nielen pre návrhového procesu a keď sa snažíte prísť na to, ako vaše Pset by mal fungovať ale aj pri ladení. Môžete mať GDB vedľa vášho pera a papiera, zatiaľ čo vy sa stanovuje, aké hodnoty sú, , Kde sa vaše šípky smerujú, a podobné veci. 

Najprv sa pozrime na stromy Huffman. Huffman stromy sú binárne stromy, čo znamená, že každý uzol má len 2 deti. V stromov Huffman charakteristikou je, že najčastejšie hodnoty sú zastúpené najmenším počtom bitov. Videli sme v prednáškových príkladov Morseovej abecedy, aký druh konsolidovaných niektoré listy. Ak sa snažíte preložiť A alebo e, napríklad, ste prekladanie, že často, takže miesto by bolo nutné použiť kompletnú sadu bitov pridelené na toto obvyklého typu dát, skomprimovať ho do menej, a potom tie listy, ktoré sú zastúpené menej často sú zastúpené s dlhšími bitov pretože si to môžu dovoliť, že keď sa odváži frekvencie, ktoré tieto listy sa objaví. Máme rovnaký nápad tu na stromoch Huffman kde sme urobili reťaz, druh cesty sa dostať do niektorých postáv. A potom postavy, ktoré majú najväčšiu frekvenciu sa bude zastúpený s najmenším počtom bitov. 

Spôsob, akým si postaviť Huffman strom je tým všetky znaky, ktoré sa vyskytujú v texte a výpočet ich početnosť, ako často sa objavujú. To by mohlo byť buď počet, koľkokrát sa tieto listy sa objaví alebo možno percento zo všetkých postáv, koľko každý z nich objaví. A tak to, čo robíte, je, až budete mať všetky tieto zmapované, potom sa pozriete na 2 najnižších frekvencií a potom sa k nim pripojil ako súrodenci kde potom nadradený uzol má frekvenciu, ktorá je suma 2 deti. A potom sa podľa konvencie hovorí, že ľavý uzol, budete nasledovať, že po 0 vetva, a potom sa úplne vpravo uzol je 1 vetva. Ako sme videli v Morseova abeceda, ten Gotcha bolo, že ak ste mali len pípnutie a pípnutie to bol nejednoznačný. Mohlo by to byť buď 1 písmeno alebo to mohlo byť postupnosť 2 písmen. A tak to, čo Huffman stromy robí, je, pretože podľa povahy postáv alebo naše konečné skutočné postavy ako posledný uzly na pobočke - nazývame tie, ktoré sú listy - na základe, že nemôže byť akákoľvek nejednoznačnosť z hľadiska toho, ktoré písmeno sa snažíte enkódování s radom bitov pretože nikde pozdĺž bitov, ktoré predstavujú 1 písmeno stretnete ďalšie celý list, a tam nebudú žiadne zmätok tam. Ale pôjdeme do príklady, ktoré vy môžete skutočne vidieť, že miesto z nás len hovorím, že je to pravda. 

Poďme sa pozrieť na jednoduchý príklad stromu Huffman. Mám reťazec, ktorý je tu 12 znakov. Mám 4 As, 6 BS a 2 Čs. Môj prvý krok by bolo počítať. Koľkokrát sa objaví? Zdá sa, 4 krát v reťazci. B sa objaví 6 krát, a C sa objaví 2 krát. Samozrejme, budem hovoriť, že som pomocou B najčastejšie, tak chcem reprezentovať B s najmenším počtom bitov, pri menšom počte 0s a 1s. A potom som tiež bude očakávať C vyžadovať najväčšie množstvo 0s a 1s rovnako. Prvé, čo som urobil je tu som umiestnil je vo vzostupnom poradí podľa frekvencie. Vidíme, že C a A, ktoré sú naše 2 najnižších frekvencií. Máme vytvoriť nadradený uzol, a že nadradený uzol nemá písmeno s ním spojené, ale má frekvenciu, ktorá je súčtom. Súčet stane 2 + 4, čo je 6. Potom sa vydáme po ľavej vetva. Ak sme boli v tej 6 uzla, potom by sme nasledovať 0 dostať sa do C a potom 1 sa dostať do A. Takže teraz máme 2 uzly. Máme hodnotu 6 a potom aj ďalšie uzol s hodnotou 6. A tak tí, 2 nie sú len 2 najnižšia, ale tiež len 2, ktoré sú vľavo, tak sme pripojiť sa k tým iným rodičom, s súčet je 12. Takže tu máme Huffmanova stromu kde sa dostať do B, to by bolo jednoducho bit 1 a potom sa dostať do budeme mať 01, a potom C s 00. Takže tu vidíme, že v podstate sme zastupujúci tieto znaky s 1 alebo 2 bity kde B, ako predpovedal, má najmenej. A potom sme očakávali C majú najviac, ale pretože je to taký malý Huffman strom, potom je tiež reprezentovaná 2 bitov oproti niekde uprostred. 

Stačí si prejsť ďalšie jednoduchý príklad stromu Huffman, že máte reťazec "Hello." Čo urobíte ako prvé by ste povedať, ako koľkokrát sa H objaviť v tomto? H sa objaví raz a potom e sa objaví raz a potom sme l objavilo dvakrát a o objavujú raz. A potom sa môžeme očakávať, ktoré písmeno bude zastúpená najmenším počtom bitov? [Študent] l >> L. Jo. l má pravdu. Predpokladáme l byť zastúpený najmenším počtom bitov preto, že som sa používa najčastejšie v reťazci "Hello." Čo budem robiť, teraz je čerpať z týchto uzlov. Mám 1, ktorý je H, a potom ešte 1, čo je e, a potom sa 1, čo je o - teraz som nastavenie - a potom 2, ktorý je l Potom som povedal tak, že som postaviť Huffman strom je nájsť 2 uzly s najmenej frekvenciou a aby im súrodencov vytvorením nadradený uzol. Tu máme 3 uzly s najnižšou frekvenciou. Všetci sú 1. Tak tu sme si vybrať, ktorý z nich budeme prepojiť prvý. Povedzme, že som si vybrať H a E. Súčet 1 + 1 = 2, ale tento uzol nemá písmeno s ním spojené. Je to len má hodnotu. Teraz sa pozrieme na ďalšie 2 najnižších frekvencií. To je 2 a 1. To by mohlo byť jedným z tých 2, ale budem si vybrať tento jeden. Súčet je 3. A potom konečne, mám len 2 vľavo, tak potom to bude 5. Potom tu, ako sa očakávalo, keď som vyplniť kódovanie pre to, 1s sa vždy ten správny odbor a 0s je ľavá. Potom máme l reprezentovaný iba 1 bit a potom na Õ 2 a potom sa e o 2 a potom H klesá na 3 bitov. Takže môžete prenášať túto správu "Hello" namiesto skutočne použitie znakov len o 0s a 1s. Pamätajte však, že v niekoľkých prípadoch sme mali vzťahy s našou frekvenciou. Mohli sme buď pripojil k H a o Prvá možná. Alebo potom o niečo neskôr, keď sme mali l predstavované 2 , Ako aj pripojil ktoré reprezentuje 2, mohli sme spojené buď jeden. 

A tak, keď pošlete 0s a 1s, že v skutočnosti nezaručuje že príjemca môže plne čítať správy hneď bat pretože nemusí vedieť, kedy rozhodnutie ste urobili. Takže keď máme čo do činenia s kompresiou Huffman, nejako musíme povedať príjemcu nášho posolstva, ako sme sa rozhodli - Potrebujú vedieť, nejaké ďalšie informácie okrem správy stlačeného vzduchu. Je potrebné, aby pochopili, čo strom vlastne vyzerá, ako sme vlastne robil tie rozhodnutia. 

Tu sme robili len to, príklady založené na skutočnej počtu, ale niekedy môže mať tiež Huffman strom na základe frekvenciu, pri ktorej sa objavia písmená, a to je presne rovnaký proces. Tu som vyjadriť to v percentách alebo zlomkom a tak tu presne to isté. Zistil som, 2 najnižšej, zhrnúť je, ďalšie 2 najnižšej, zhrnúť je, až budem mať plnú strom. Aj keď by sme mohli urobiť to buď tak, keď máme čo do činenia s percentami, to znamená, že sme rozdelenie veci a nakladanie s desatinných miest, či skôr pláva ak budeme premýšľať o dátových štruktúr hlavy. Čo vieme o plaváky? Čo je to bežný problém, kedy máme čo do činenia s plavákmi? [Študent] Nepresné aritmetika. Jo >>. Nepresnosť. Vzhľadom k tomu, v pohyblivej rádovej čiarke nepresnosti, pre tento PSet tak, že sa uistiť, že aby sme nestratili žiadne hodnoty, potom sme vlastne bude rokovať s grófom. Takže ak ste mali myslieť na uzle Huffman, keď sa pozriete späť do štruktúry tu, keď sa pozriete na zelených má frekvenciu s ním spojené rovnako ako to ukazuje na uzol na jeho ľavej strane, rovnako ako uzol na jeho pravej strane. Potom červený ty tam tiež majú charakter sú s nimi spojené. Nebudeme robiť samostatné tie pre rodičov a potom koncových uzlov, ktoré označujeme ako listy, ale skôr tých budú musieť len hodnoty NULL. Pre každý uzol budeme mať charakter, symbol, že uzol reprezentuje, potom frekvencie, rovnako ako ukazovateľ na jeho ľavej dieťa, rovnako ako jeho pravé dieťa. Listy, ktoré sú na samom dne, by tiež mať uzlov odkazy po ich ľavici a ich práva, ale pretože tieto hodnoty nie sú poukazom na skutočné uzly, čo by ich hodnota bola? >> [Študent] NULL. >> NULL. Presne tak. Tu je príklad toho, ako by sa vám mohol predstavovať frekvenciu v plaváky, ale budeme rokovať s ním s celými číslami, takže všetko, čo urobil, je zmeniť dátový typ tam. 

Poďme na trochu viac komplexný príklad. Ale teraz, keď sme urobili jednoduché ty, je to len rovnaký proces. Môžete nájsť 2 najnižších kmitočtov, sčítať frekvencia a to je nová frekvencia vášho nadradeného uzla, ktorý potom ukazuje na jeho ľavej strane s 0 pobočky a právo s 1 pobočkou. Ak máme reťazec "To je cs50," potom budeme počítať, koľkokrát je T uvedené, h spomenuté, i, s, c, 5, 0. Potom to, čo som urobil tu je s červenými uzlami som zasadil, Povedal som, že budem mať tieto znaky nakoniec na dne môjho stromu. Tí sa bude všetkých listov. Potom to, čo som urobil je, že som zoradené podľa frekvencie vo vzostupnom poradí, a to je vlastne spôsob, akým Pset kód robí Je to druhy to tým, že frekvencia a potom podľa abecedy. Tak to má čísla a potom abecedne podľa frekvencie. Tak čo by som urobil je, že som sa nájsť 2 najnižšej. To je 0 a 5. Chcel by som zhrnúť je, a to je 2. Potom by som pokračovať, nájsť ďalšie 2 najnižšej. To sú dva 1s, a potom tie, s 2, ako. Teraz viem, že môj ďalší krok bude sa pripojí najnižšie číslo, ktoré je T, 1, a potom výberom jedného z uzlov, ktoré má dve ako frekvencie. Takže tu máme 3 možnosti. Čo budem robiť po snímke je len vizuálne zmeniť ich poradie pre vás takže môžete vidieť, ako som buduje. Čo sa kód a vaša distribúcia kód bude robiť by sa pripojiť k T jeden s 0 a 5 uzla. Takže, že sumy až 3, a potom budeme pokračovať v procese. The 2 a 2 sú teraz najnižšie, takže potom tie Čiastka 4. Každý po tak ďaleko? Dobre. Potom po tom máme 3 a 3, ktoré je potrebné sčítať, takže opäť som len prepínanie to tak, že môžete vidieť vizuálne tak, že to nie je príliš komplikovaná. Potom máme 6, a potom sa naše posledný krok je teraz, že máme len 2 uzly Zhrnieme tie, aby sa koreň nášho stromu, čo je 10. A číslo 10 dáva zmysel, pretože každý uzol predstavuje, ich hodnota, ich početnosť číslo, bolo koľkokrát sa objavili v reťazci, a potom máme 5 znakov v našom reťazci, tak to dáva zmysel. Ak sa pozrieme na to, ako sa budeme skutočne zakódovať, podľa očakávania, i a y, ktoré sa objavujú najčastejšie sú zastúpené najmenším počtom bitov. 

Buďte opatrní. V stromov Huffman prípad skutočne záleží. Veľká S sa líši malým s Ak by sme mali "To je CS50" s veľkými písmenami, potom malá s by sa zobrazí iba dvakrát, by uzol s 2 ako jeho hodnotu, a potom sa veľká S by iba raz. Takže váš strom by sa zmenili štruktúry, pretože máte skutočne zvláštny list tu. Ale suma bude stále 10. To je to, čo sme vlastne bude volať kontrolný súčet, pridanie všetkých smeroch. 

Teraz, keď sme prebrali Huffman stromy, môžeme sa ponoriť do Puff Huff'n sa PSet. Budeme začať s časťou otázok, a to bude vám zvyknutí s binárnymi stromami a ako pracovať okolo toho: kreslenie uzly, vytvoriť si vlastný typedef struct pre uzol, a vidieť, ako by ste mohli vložiť do binárneho stromu, jeden, ktorý je zoradená, kríženie je, a podobné veci. Že vedomosti sa určite pomôže, keď sa ponoríte do časti Puff Huff'n z PSet. V štandardnom vydaní PSet, vašou úlohou je realizovať Puff, a vo hacker verzii vašou úlohou je realizovať Huff. Čo Huff robí, je, že trvá textu a potom to prekladá do 0s a 1s, tak proces, ktorý sme urobili vyššie, kde sme napočítali frekvencie a potom sa na strom a potom povedal: "Ako sa dostanem T?" T je zastúpená 100, a podobné veci, a potom Huff by sa text a potom výstupné že binárne. Ale aj preto, že vieme, že chceme, aby náš príjemcu správy znovu presne rovnaký strom, ale tiež obsahuje informácie o frekvenčných počíta. Potom sa Puff je nám daný binárny súbor 0s a 1s a vzhľadom k tomu aj informácie o frekvenciách. Prekladáme všetky tie 0s a 1s späť do pôvodnej správy, ktorá bola, takže sme dekompresie, že. Ak robíte štandardnej edícii, nemusíte vykonávať Huff, takže potom stačí použiť zamestnancov vykonávanie Huff. Tam sú inštrukcie v spec o tom, ako to urobiť. Môžete spustiť zamestnanca vykonávanie Huff na určité textového súboru a potom použiť tento výstup ako vstup Puff. 

Ako som už spomenul predtým, máme veľa distribúcie kódu pre tento jeden. Chystám sa začať chodiť cez neho. Budem tráviť väčšinu času na. H súbory pretože v súbory C, pretože máme. H a že nám poskytuje prototypy funkcií, nemáme plne nutné presne pochopiť - Ak nechcete pochopiť, čo sa deje v Súbory C, potom sa nemusíte starať moc, ale rozhodne skúste sa pozrieť, pretože by to mohlo dať nejaké rady a je užitočné si zvyknúť na čítanie kódu iných ľudí. 

Pri pohľade na huffile.h, do komentárov, že deklaruje vrstvu abstrakcie pre Huffman-kódované súbory. Ak pôjdeme dole, vidíme, že je maximálne 256 znakov, ktoré by sme mohli potrebovať kódy. To zahŕňa všetky písmená abecedy - veľká a malá - a potom symboly a čísla, atď Potom tu máme magic number, ktorý stanovil Huffman kódovaný súbor. V rámci kódu Huffman, že budeš mať určitý magické číslo spojený s hlavičky. To môže vyzerať ako len náhodné magické číslo, ale ak ste skutočne preložiť do ASCII, potom to vlastne vysvetľuje nahnevať. Tu máme struct pre Huffman kódovanie súboru. Je tu všetky tieto charakteristiky spojené so súborom Huff. Potom tu máme hlavičku pre súbor Huff, tak hovoríme, že Huffeader namiesto pridanie ďalšej h, pretože to znie rovnako tak. Cute. Máme kúzelné číslo s ním spojené. Ak je to skutočný Huff súbor, to bude číslo hore, to kúzlo jeden. A potom to bude mať pole. Tak pre každý symbol, ktorý je 256, bude to zoznam toho, čo frekvencia týchto symbolov je v súbore Huff. A potom konečne, máme kontrolný súčet frekvencií, , Ktoré by mali byť súčet týchto frekvencií. Tak to je to, čo Huffeader je. Potom máme niektoré funkcie, ktoré vracajú ďalšie bit v súbore Huff rovnako ako zapíše bit súboru Huff, a potom sa táto funkcia tu, hfclose, ktoré skutočne zavrie súbor Huff. Skôr sme sa zaoberali priamo len fclose, ale keď máte súbor Huff, namiesto toho, aby ju fclosing čo ste vlastne robiť, je hfclose a hfopen ju. To sú špecifické funkcie Huffová súbory, ktoré budeme sa zaoberať. Potom tu čítame v hlavičke a potom písať hlavičky. 

Len tým, že čítanie. H súbor môžeme trochu získať pocit z toho, čo súbor Huff môže byť, aké vlastnosti má, bez toho by sa skutočne ísť do huffile.c, ktoré, ak by sme ponoriť, bude trochu zložitejšie. Má všetky súboru I / O tú sa zaoberá ukazovateľmi. Tu vidíme, že keď voláme hfread, napríklad, je to stále vysporiadava s fread. Nie sme zbaviť týchto funkcií úplne, ale posielame, ktoré majú byť postarané vnútri súboru Huff miesto robí všetko pre to sami. Môžete pokojne prehľadá to, ak ste zvedaví, a ísť a kôra vrstve zadnej trochu. 

Ďalší obrázok, ktorý budeme pozrieť sa na tree.h. Pred v Walkthrough skĺzne sme povedali, očakávame Huffmanova uzol a urobili sme typedef struct uzol. Očakávame, že majú symbol, frekvencia, a potom 2 uzlov hviezdy. V tomto prípade, čo robíme, je to v podstate rovnaký okrem namiesto uzla budeme nazývať stromy. Máme funkciu, ktorá pri volaní, aby strom to vráti vám strom ukazovateľ. Späť na Speller, keď ste robili nový uzol ste povedal uzol * nové slovo = malloc (sizeof) a podobné veci. V podstate, mktree sa bude zaoberať, že pre vás. Podobne, ak chcete odstrániť strom, tak to je v podstate uvoľnenie strom, keď ste s ním urobil, miesto aby bol explicitne volať zadarmo na to, že ste v skutočnosti len tak použiť funkciu rmtree kde odovzdáte ukazovateľ na daný strom a potom tree.c sa postará o to pre vás. 

Pozeráme sa do tree.c. Očakávame, že rovnaké funkcie, okrem nedočkalo realizácie rovnako. Ako sme očakávali, keď budete volať mktree to mallocs veľkosti stromu do ukazovatele, inicializuje všetky hodnoty s hodnotou NULL, takže 0s alebo hodnoty Null, a vráti ukazovateľ na daný strom, ktorý ste práve malloc'd pre vás. Tu, keď zavoláte odstrániť strom najprv zaistí, že nie ste double uvoľnenie. To zaisťuje, že budete mať v skutočnosti strom, ktorý chcete odstrániť. Tu pretože strom aj svoje deti, Čo to však je, že vyžaduje rekurzívne odstrániť strom na ľavej uzol stromu , Ako aj na pravej uzla. Pred tým, než sa uvoľní rodičia, treba oslobodiť deti rovnako. Parent je tiež zameniteľný s koreňom. Vôbec prvý rodič, tak ako pra-pra-pra-pra-pradedo alebo babička strom, musíme najprv uvoľniť sa ustanovujú úrovne prvý. Takže traverz až na dno, bez tých, a potom sa vrátiť nahor, bez tých, atď Tak to je strom. 

Teraz sa pozrieme na les. Forest je miesto, kde môžete umiestniť všetky svoje stromy Huffman. Je to tým, že budeme mať niečo ako plot , Ktorý obsahuje ukazovateľ na strom, rovnako ako ukazovateľ na pozemku s názvom ďalšie. Aká štruktúra sa tento druh vyzerať? Je to druh to hovorí tam. Priamo tu. Spájať zoznam. Vidíme, že keď máme pozemok je to ako prepojeného zoznamu parciel. Les je definovaný ako prepojeného zoznamu pozemkov, a tak štruktúra lesov je budeme jednoducho musieť ukazovateľ na našu prvú pozemku a že pozemok má strom v ňom, alebo skôr poukazuje k stromu a potom sa odkazuje na nasledujúce pozemku, tak ďalej a tak ďalej. Ak chcete les hovoríme mkforest. Potom máme niektoré docela užitočné funkcie tu. Máme vybrať, kde odovzdáte v lese a potom je návratová hodnota Tree *, ukazovateľ na strom. Čo pick bude robiť, je, že pôjde do lesa, že ste ukázal na potom odstráňte strom s najnižším kmitočtu z toho lesa a potom vám ukazovateľ na ten strom. Akonáhle zavoláte vybrať, bude sa strom neexistuje v lese už, ale návratová hodnota je ukazovateľ na ten strom. Potom máte rastlinu. Za predpokladu, že odovzdáte ukazovateľ na strom, ktorý má non-0 frekvenciu, čo rastlina bude robiť, je, že bude trvať do lesa, sa strom, a závod, ktorý strom vnútri lesa. Tu máme rmforest. Podobné odstrániť strom, ktorý v podstate oslobodil všetky z našich stromov pre nás, odobrať les slobodná vôľa všetko obsiahnuté v tomto lese. 

Ak sa pozrieme do forest.c, budeme očakávať, že aspoň 1 rmtree príkaz tam, pretože na voľnej pamäte v lese, ak les má stromy v ňom, potom nakoniec budete musieť odstrániť tie stromy taky. Ak sa pozrieme do forest.c, máme mkforest, čo je, ako sme očakávali. My malloc veci. Sme inicializácii prvý pozemok v lese ako NULL, pretože je prázdna začať, potom vidíme, vybrať, ktoré vracia strom s najnižšou váhou, najnižšia frekvencia, a potom zbaví daného uzla, ktorý odkazuje na ten strom a ďalšia skladba, tak to trvá, že z prepojeného zoznamu lesa. A potom tu máme závod, ktorý vloží stromu do prepojeného zoznamu. Čo les robí, je to pekne drží to sú zoradené pre nás. A potom konečne, máme rmforest a, ako sa očakávalo, máme rmtree vzýval tam. 

Pri pohľade na distribučné kód tak ďaleko, huffile.c bol pravdepodobne zďaleka najťažší pochopiť, vzhľadom k tomu, ďalších súborov sami boli celkom jednoduché nasledovať. Pri našej znalosti ukazovateľov a vzájomne previazaných zoznamov a takých, sme boli schopní sledovať celkom dobre. Ale všetko, čo potrebujeme naozaj uistiť, že plne chápeme je. H súbory pretože je potrebné, aby sa volanie týchto funkcií, ktoré sa zaoberajú týmito návratovej hodnoty, takže sa uistite, že ste plne porozumeli, aká akcia sa bude vykonávať kedykoľvek volať jednu z týchto funkcií. Ale v skutočnosti porozumenie vnútri nej nie je úplne nutné, pretože máme tie. H súbory. Máme 2 ďalšie súbory, ktoré zostali v našej distribučnej kódu. 

Poďme sa pozrieť na skládke. Dump jeho komentármi tu trvá Huffman-komprimovaný súbor a potom prekladá a skládky všetci jej obsah von. Tu vidíme, že je to volanie hfopen. To je druh zrkadlenie súbor * vstup = fopen, a potom sa prejsť v informácii. Je to takmer identické, s výnimkou miesto súboru * ste prechádzajúcej v Huffile; miesto fopen ste mimochodom v hfopen. Tu čítame v hlavičke prvý, ktorý je tak trochu podobné tomu, ako čítame v záhlaví pre bitmapový súbor. Čo tu robíme je kontrola, či informácie v hlavičke obsahuje správne magické číslo, ktoré označuje, že je to skutočný Huff súbor, potom všetky tieto kontroly, aby sa uistil, že súbor, ktorý sme otvorený je skutočný nahneval súbor, alebo nie. Čo to však je, že výstupy frekvencia všetkých symbolov, ktoré môžeme vidieť v rámci terminálu do grafického tabuľky. Táto časť bude užitočná. Má trochu a číta kúsok po kúsku do premennej bit a potom vytlačí ju. Takže ak by som mal zavolať skládku na hth.bin, ktorý je výsledkom nahnevá súboru pomocou zamestnancov riešenie, by som si to. Je to výstup všetkých týchto znakov a potom uvedenie frekvenciu, pri ktorej sa objaví. Ak sa pozrieme, väčšina z nich sú 0s okrem toho: H, ktorý sa objaví dvakrát, a potom T, ktorá sa objaví raz. A potom tu máme skutočný správu 0s a 1s. Ak sa pozrieme na hth.txt, čo je pravdepodobne pôvodná správa, ktorá bola odfrkol, očakávame nejaké Hs a TS tam. Konkrétne, očakávame len 1 T a 2 HS. Tu sme v hth.txt. To má skutočne HTH. Zahrnuté tam, hoci my nemôžeme vidieť, je znak nového riadku. Súbor Huff hth.bin je tiež kódovanie znaku nového riadku rovnako. Tu pretože vieme, že poriadok je HTH a potom nový riadok, je vidieť, že asi H je reprezentovaná len jedným 1 a potom T je pravdepodobne 01 a potom ďalšie H 1, rovnako a potom máme nový riadok označená dvomi 0s. Cool. 

A potom konečne, pretože máme čo do činenia s viac. C a H súbory, budeme mať pekne zložitá argument kompilátor, a tak tu máme Makefile, ktoré umožňuje výpis pre vás. Ale v skutočnosti, budete musieť ísť o tom svoje vlastné puff.c súbor. Makefile vlastne nerieši robiť puff.c pre vás. Odchádzame, že na vás upraviť Makefile. Keď zadáte príkaz, ako je, aby všetkým, napríklad, bude to robiť všetky z nich pre vás. Neváhajte sa pozrieť na príklady Makefile z minulého PSet rovnako ako ísť preč z tohto vidieť, ako by ste mali byť schopní, aby sa váš Puff súbor úpravou tohto súboru Makefile. To je asi tak pre náš distribučný kódu. 

Akonáhle sme sa dostali cez to, že potom je tu len ďalší pripomienkou toho, o tom, ako budeme rokovať s uzlami Huffman. Nebudeme sa volať je uzliny už, budeme sa nazývať stromy kde budeme zastupovať ich symbol, char, ich frekvencia, počet výskytov, s celé číslo. Používame to, pretože to je to presnejšie než plaváku. A potom máme ďalší ukazovateľ na ľavej dieťaťa rovnako ako pravé dieťa. Les, ako sme videli, je len previazaný zoznam stromov. Nakoniec, keď sme budovanie našej Huff súbor, chceme, aby naše lesy obsahovať len 1 strom - 1 strom, 1 root s viacerými deťmi. Predtým, keď sme boli len, že naše Huffman stromy, sme začali tým všetky uzly na našej obrazovke a hovoriť budeme mať tieto uzly, nakoniec sa budeš listy, a to je ich symbol, to je ich frekvencia. V našom lese, keby sme sa 3 písmená, to je les 3 stromov. A potom, ako budeme pokračovať, keď sme pridali prvý rodičia, sme sa les 2 stromov. Odstránili sme 2 z týchto detí z nášho lesa a potom nahradil ju nadradeného uzla že mal tie 2 uzly ako deti. A potom konečne, naše posledný krok s výrobou náš príklad s As, Bs, a Cs by ku konečnému rodičia, a tak, potom by to priniesť naše celkové počtu stromov v lese na 1. Má každý vidieť, ako sa začať s niekoľkými stromami v lese a skončiť s 1? Dobre. Cool. 

Čo musíme urobiť pre Puff? Čo musíme urobiť, je zabezpečiť, že ako vždy, nám dávajú ten správny typ vstupu tak, že sa môže v skutočnosti spustiť program. V tomto prípade sú to bude, že nám po ich prvom argument príkazového riadku 2 viac: súbor, ktorý chceme dekomprimovať a výstup dekomprimovaného súboru. Ale akonáhle sme sa uistili, že okolo nás v správnom množstve hodnôt, Chceme zabezpečiť, aby vstup je súbor Huff, alebo nie. A potom ešte raz vám zaručiť, že je to súbor Huff, potom chceme budovať náš strom, vybudovať strom tak, že zodpovedá strom, ktorý človek, ktorý poslal správu postavený. Potom po staviame strom, potom sa môžeme zaoberať 0s a 1s, že prešiel v roku, tým, ktoré spolu náš strom, pretože je to rovnaké, a potom napísať, že posolstvo, interpretovať bity späť do znakov. A potom na konci, pretože máme čo do činenia s ukazovateľmi tu, Chceme sa uistiť, že nemáme žiadne úniky pamäte a že sme voľní všetko. 

Zabezpečenie riadneho využitia je starý klobúk pre nás teraz. Berieme v vstup, ktorý bude názov súboru, ktorý chcete nafúknuť, a potom sme sa špecifikovať výstup, takže názov súboru pre predvareného výstup, ktorý bude textový súbor. To je s nimi nakladané. A teraz chceme zabezpečiť, aby vstup fučal, alebo nie. Keď spomínam, bolo niečo, čo v distribučnej kódu, ktorý nám môže pomôcť s pochopením, či je súbor nahneval, alebo nie? Tam boli informácie v huffile.c o Huffeader. Vieme, že každý súbor Huff má Huffeader s ním spojené s čarovným číslom , Ako aj rad frekvencií pre každý symbol rovnako ako kontrolný súčet. Vieme, že, ale tiež sa nahliadnuť na dump.c, , V ktorom bolo čítanie do súboru Huff. A tak k tomu, že to malo overiť, či skutočne bol nahneval, alebo nie. Takže možno by sme mohli použiť dump.c ako štruktúry pre naše puff.c. Späť na PSet 4, keď sme mali súbor copy.c, že ​​skopírovali v trojiciach RGB a my vykladať, že pre detektívka a zmeny veľkosti, podobne, čo by ste mohli urobiť, je stačí spustiť príkaz ako cp dump.c puff.c a použiť niektoré z kódu tam. Avšak, to nebude tak jednoduché procesu pre prekladanie si dump.c do puff.c, ale aspoň to vám dáva niekde začať o tom, ako zabezpečiť, aby vstup je skutočne odfrkol, alebo nie rovnako ako pár ďalších vecí. Sme zaistili správne používanie a zabezpečiť, aby vstup nahneval. Zakaždým, keď sme urobili, že sme urobili našu správnu kontrolu chýb, tak vracia a ukončenie funkcie, ak niektoré dôjde k zlyhaniu, v prípade, že je problém. 

Teraz, čo chceme urobiť, je vytvoriť skutočný strom. Ak sa pozrieme v lese, tam sú 2 hlavné funkcie že budeme chcieť, aby sa veľmi dobre. Tam je Logické funkcie rastlina, ktorá rastliny non-0 Frekvencia strom v našom lese. A tak tam odovzdáte ukazovateľ na les a ukazovateľ na strom. Rýchly dotaz: Koľko lesy budete mať, keď staviate Huffman strom? Naša les je ako náš plátno, nie? Takže sme len bude mať 1 les, ale budeme mať viac stromov. Takže predtým, než zavoláte zariadenie, budete pravdepodobne chcieť, aby váš les. K dispozícii je príkaz pre ktoré, keď sa pozriete do forest.h o tom, ako môžete urobiť les. Môžete zasadiť strom. Vieme, ako na to. A potom si môžete vybrať aj strom z lesa, odstránenie stromu s najnižšou váhou a dáva vám ukazovateľ na to. Spomínal, keď sme robili v príkladoch sami, keď sme boli kreslenie to, sme proste len pridali odkazy. Ale tu nie len pridávanie odkazov, myslieť na to skôr ako ste odstránenie 2 týchto uzlov a potom nahrádzať ju inou. Ak chcete vyjadriť, že pokiaľ ide o zber a pestovanie, ste vychystávanie 2 stromy a potom výsadba ďalšie strom že má tie 2 stromy, ktoré ste si vybrali ako deti. Ak chcete vytvoriť Huffman je strom, si môžete prečítať v symboly a frekvencie v poradí pretože Huffeader dáva, že na vás, vám dáva rad frekvencií. Takže môžete ísť dopredu a len tak ignorovať čokoľvek s 0 v ňom pretože nechceme 256 listy na konci toho. Chceme len počet listov, ktoré sú znaky , Ktoré sú v skutočnosti používa v súbore. Si môžete prečítať v týchto symbolov, a každý z týchto symbolov, ktoré majú non-0 frekvencií, ty sa bude stromy. Čo môžete urobiť, je zakaždým, keď si prečítal v non-0 frekvencie symbol, môžete zasadiť ten strom v lese. Akonáhle zasadiť stromy v lese, môžete sa pripojiť tie stromy ako súrodenci, tak vracia na pestovanie a vyberanie, kde si vyberiete 2 a potom závod 1, kde to 1, ktorá vás rastlín je rodič zo 2 detí, ktoré si vybral. Takže potom sa vaše konečný výsledok bude jediný strom v lese. To je, ako si postaviť svoj strom. 

Existuje niekoľko vecí, ktoré by mohli pokaziť tu pretože máme čo do činenia s výrobou nových stromov a nakladanie s ukazovateľmi a podobné veci. Ako keď sme sa zaoberali ukazovateľmi, keď sme malloc'd sme chceli, aby sa ubezpečil, že sa nevrátil nám NULL ukazovateľ hodnotu. Takže na niekoľkých krokoch v rámci tohto procesu sú bude niekoľko prípadov kde váš program by mohol zlyhať. Čo chcete urobiť, je sa chcete uistiť, že riešite tieto chyby, a vo spec hovorí s nimi elegantne, tak ako vytlačiť správu užívateľovi im povie, prečo má program ukončiť a potom rýchlo ukončite ju. Ak chcete túto chýb, pamätajte, že chcete skontrolovať zakaždým, že by mohlo byť zlyhanie. Zakaždým, že robíš nový ukazovateľ Chcete, aby sa ubezpečil, že je úspešný. Ako to, čo sme urobiť, je vytvoriť nový ukazovateľ a malloc ju, a potom by sme skontrolovať, či je ukazovateľ NULL. Takže tam sa bude niektoré príklady, kde môžete len urobiť to, ale niekedy ste vlastne volanie funkcie av rámci tejto funkcie, to je ten, ktorý je robí mallocing. V tomto prípade, ak sa pozrieme späť do niektorej z funkcií v kóde, Niektoré z nich sú logické funkcie. V abstraktné prípade, ak máme logický funkcia s názvom foo, v podstate, dá sa predpokladať, že okrem toho, čo foo robí, pretože je to Logické funkcie, vracia true alebo false - true, ak úspešný, false v opačnom prípade. Takže chceme overiť, či je vrátená hodnota foo je true alebo false. Ak je to false, čo znamená, že budeme chcieť vytlačiť nejakú správu a potom ukončite program. Čo chceme urobiť, je skontrolovať vrátenú hodnotu foo. Ak foo vráti false, potom vieme, že sme sa stretli s nejakou chybou a musíme prestať náš program. Spôsob, ako to urobiť, je mať stav, keď skutočná funkcia sama o sebe je Váš zdravotný stav. Povedzme, že foo berie v x. Môžeme mať ako podmienku if (foo (x)). V podstate to znamená, že ak na konci realizácie foo vracia pravda, potom môžeme urobiť, pretože funkcia musí zhodnotiť foo aby bolo možné vyhodnotiť celý stav. Takže je to, ako môžete niečo urobiť, ak funkcia vracia hodnotu true a je úspešný. Ale keď ste kontrolu chýb, si len chcete ukončiť, ak je vaša funkcia vráti false. Čo môžete urobiť, je len pridať == false, alebo len pridať tresku pred ním a potom máte if (! foo). V rámci tohto orgánu tohto stavu by ste mať všetky chýb, tak ako, "Nepodarilo sa vytvoriť tento strom" a potom sa vrátiť 1, alebo niečo také. Čo to robí, keď je to, že aj keď foo vrátil false - Povedzme, že foo vracia hodnotu true. Potom nemusíte volať foo znova. To je mylná predstava,. Vzhľadom k tomu, že bol vo svojom stave, je to už vyhodnotený, takže už máte výsledok, ak používate, aby strom alebo niečo také alebo zariadenia alebo pick, alebo tak niečo. To už má túto hodnotu. Je to už vykonaný. Takže je to vhodné použiť booleovské funkcie ako podmienku pretože či už ste alebo nie ste skutočne spustiť telo slučky, spustí funkciu rovnako. 

Náš druhý na posledný krok je písanie správy do súboru. Akonáhle budeme budovať Huffman strom, potom písanie správy do súboru je veľmi jednoduché. Je to celkom jednoduché teraz stačí nasledovať 0s a 1s. A tak podľa konvencie vieme, že na strome Huffman uveďte opustil 0s a 1s uviesť pravdu. Takže ak budete čítať v kúsok po kúsku, zakaždým, keď dostanete 0 budete sledovať ľavá vetva, a potom zakaždým, keď si prečítal v 1 budete nasledovať správnu vetvu. A potom budete pokračovať, kým nenarazíte na list pretože listy sa bude na konci konárov. Ako môžeme zistiť, či sme hit list alebo nie? Povedali sme, že to predtým. [Študent] Ak ukazovatele sú NULL. Jo >>. Môžeme povedať, či sme hit list v prípade, že ukazovatele na oboch ľavý a pravý stromy sú NULL. Perfect. Vieme, že chceme čítať v kúsok po kúsku do nášho súboru Huff. Ako sme videli skôr v dump.c, čo urobili, je, že si v kúsok po kúsku do súboru Huff a len vytlačiť to, čo tie kúsky boli. Nebudeme sa s tým. Budeme robiť niečo, čo je trochu zložitejšie. Ale čo môžeme urobiť, je, že sme si vziať ten kúsok kódu, ktorý číta do bitu. Tu máme integer bit predstavujúce aktuálne bit, ktorý sme na. To sa stará o iterácií všetky bity v súbore, kým nenarazíte na koniec súboru. Na základe toho, potom budete chcieť mať nejaký Iterator prejsť na strom. A potom na základe toho, či je bit 0 alebo 1, budete chcieť, aby buď presunúť tento Iterator vľavo alebo ju presunúť doprava celú cestu, kým nenarazíte na list, takže celá cesta až do tohto uzla, ktorý ste na neukazuje na nič viac uzlov. Prečo môžeme urobiť so súborom Huffman, ale nie Morse kódu? Vzhľadom k tomu, v Morseova abeceda je tu trochu nejednoznačnosť. Mohli by sme byť ako, oh čakať, sme hit list na ceste, takže možno to je naša list, vzhľadom k tomu, či sme pokračovali len trochu dlhšie, potom by sme zasiahli ďalší list. Ale to sa nestane v kódovaní Huffman, takže môžeme byť istí, že jediný spôsob, ako budeme hit charakter Ak je tento uzol je ľavá a pravá deti sú NULL. 

Napokon, chceme oslobodiť všetky naše pamäť. Chceme, aby aj konci súboru Huff, že sme sa zaoberáme rovnako ako odstránenie všetkých stromov v našom lese. Na základe vašej implementáciu, budete pravdepodobne chcieť volať odstrániť les miesto skutočne prechádza všetky stromy sami. Ale ak ste vykonali nejaké dočasné stromy, budete chcieť oslobodiť, že. Vieš svoj kód najlepšie, takže viete, kde ste prideľovanie pamäte. A tak ak idete do, začnite tým, dokonca kontrolu F'ing pre malloc, vidieť kedykoľvek malloc a uistite sa, že ste uvoľniť všetko ale potom práve prechádza kódu, porozumenie, kde ste mohli pridelená pamäť. Zvyčajne môžete len povedať, "Na konci súboru Ja som jednoducho ísť na odstránenie les na mojom lese," takže v podstate jasné, že pamäť, zadarmo, ktoré, "A potom som tiež chystá zatvorte súbor a potom môj program bude prestať." Ale je to jediný čas, ktorý váš program ukončí? Nie, pretože niekedy tam mohlo byť chyba, čo sa stalo. Možno sme nemohli otvoriť súbor alebo my sme nemohli vykonať ďalšie strom alebo nejaký druh chyby sa stalo v procese prideľovania pamäti, a tak sa vrátil NULL. Došlo k chybe, a potom sme sa vrátili a ukončite. Takže chcete, aby sa ubezpečil, že prípadná čas, že váš program môže prestať fajčiť, Ak chcete uvoľniť všetky svoje pamäti tam. Nie je to len tak na samom konci hlavnej funkcie, ktoré ukončite kód. Chceš sa pozrieť späť na každom stupni, že váš kód potenciálne mohol vrátiť predčasne a potom zadarmo bez ohľadu na pamäti zmysel. Povedzte, že ste zavolal, aby les a že sa vrátil false. Potom ste pravdepodobne nebudete potrebovať odstrániť svoj les pretože nemáte lesa doteraz. Ale v každom bode v kóde, kde by ste mohli vrátiť predčasne chcete, aby sa ubezpečil, že ste uvoľniť prípadné pamäť. 

Takže keď máme čo do činenia s uvoľnením pamäte a majú potenciálne úniky, chceme využívať nielen náš úsudok a naše logika ale tiež použiť Valgrind na určenie, či máme uvoľnená všetka našej pamäti správne, alebo nie. Môžete buď spustiť Valgrind na Puff a potom sa budete musieť tiež odovzdať ho správny počet argumentov príkazového riadku pre Valgrind. Môžete spustiť, ale výstup je trochu mystický. Dostali sme sa trochu na to zvyknutí u Speller, ale stále potrebujeme trochu viac pomoci, takže potom beží to s niekoľkými ďalšími príznakmi, ako je únik-check = full, ktoré budú pravdepodobne nám nejaké ďalšie užitočné výstup na Valgrind. 

Potom ďalšie užitočné tip, keď ste ladenie je príkaz diff. Môžete pristupovať k pracovníkom za vykonávanie Huff, spustite, že na textový súbor, a potom výstup do binárneho súboru, binárny súbor Huff, byť konkrétny. Potom, ak sa dostanete svoj vlastný obláčik na tomto binárny súbor, potom v ideálnom prípade, vaše výstup textový súbor bude totožný k pôvodnej, ktorý prešiel dovnútra Tu som pomocou hth.txt ako príklad, a to je ten hovoril o vo vašom špec. To je doslova HTH a potom nový riadok. Ale rozhodne neváhajte a ste určite odporúčame používať dlhší príklady pre textovom súbore. 

Môžete si dokonca vziať si na mušku možno kompresiu a dekompresiu potom niektoré zo súborov, ktoré ste použili v Speller ako Vojna a mier alebo Jane Austen, alebo niečo takého - to by bolo celkom fajn - alebo Austin Powers, druh rokovaní s väčšími súbormi, pretože by sme prišli na vec ak sme použili na ďalší nástroj tu, ls-l. Sme zvyknutí na ls, ktorá v podstate uvádza všetky obsah v našom aktuálnom adresári. Odovzdávanie v vlajky-l skutočne zobrazuje veľkosť týchto súborov. Ak prejdete spec PSet, to vlastne vás prevedie vytvorením binárny súbor, zo dňa nahnevá ho, a uvidíte, že pre veľmi malé súbory priestor náklady na kompresiu, a prekladať všetky tieto informácie všetkých frekvencií a podobné veci, ktoré preváži skutočné výhody kompresiu súboru na prvom mieste. Ale ak sa dostanete na niektorých dlhších textových súborov, potom by ste mali vidieť, že začnete sa dostať nejaký prospech v kompresii týchto súborov. 

A potom konečne, máme starý kamarát GDB, ktorý je určite príde vhod tiež. 

Ešte budeme mať nejaké otázky, na stromoch Huff alebo procesu snáď robiť stromy alebo akékoľvek iné otázky týkajúce sa Puff Huff'n? Dobre. Zostanem asi na chvíľu. 

Vďaka, všetci. To bolo Návod 6. A veľa šťastia. 

[CS50.TV]