[Powered by Google Translate] [Kiirtutvustus - Ülesanded 6] [Zamyla Chan - Harvardi Ülikool] [See on CS50. - CS50.TV] 

Tere kõigile ja tere tulemast kiirtutvustus 6: Huff'n Puff. Aastal Huff'n Puff mida me teeme läheb tegelevad Huffman tihendatud fail ja siis puhitamine seda uuesti üles, nii mahalaadimine see, nii et saame tõlkida 0. ja 1s et kasutaja saadab meile ja teisendada see tagasi esialgse teksti. Pset 6 kavatse olla päris lahe, sest sa lähed näha mõned tööriistad , mida kasutasid pset 4 ja pset 5 ja omamoodi ühendab neid arvesse 1 päris kena mõiste kui sa tuled mõelda. 

Samuti väidetavalt pset 4 ja 5 olid kõige keerulisem psets et meil oli pakkuda. Nii et nüüd on meil see veel 1 pset C, ja siis pärast, et me oleme veebi programmeerimine. Nii et õnnitleda ise saada üle raskeimates küür sisse CS50. 

Liikumine edasi Huff'n Puff, meie tööriistakasti selle pset saab olema Huffman puud, nii mõista mitte ainult kuidas kahendpuuks töö, vaid ka konkreetselt Huffman puud, kuidas nad ehitatud. Ja siis me lähed on palju jaotus kood selles pset, ja me tuleme näha, et tegelikult mõned koodi me ei pruugi täielikult mõista veel, ja nii need on. c faili, kuid siis nende juurde. h failid annab meile piisavalt teadmisi, et me vajame nii et me teame, kuidas need funktsioonid töötavad või vähemalt see, mida nad peaksid tegema - nende sisendid ja väljundid - isegi kui me ei tea, mis toimub musta kasti või ei saa aru, mis toimub musta kasti sees. Ja siis lõpuks, nagu ikka, on tegemist uue andmestruktuure teatud liiki sõlmed, mis viitavad teatud asju, ja nii siin, millel on pliiats ja paber mitte ainult projekteerimise käigus ja kui sa üritad välja selgitada, kuidas oma pset peaks töötama kuid ka ajal silumine. Sul võib olla GDB kõrval oma pliiatsi ja paberi kui te võtate ette, missugune väärtused, kus oma nooltega näidatud ja asjad niimoodi. 

Esiteks vaatame Huffman puud. Huffman puud on kahendpuuks, mis tähendab, et iga sõlm on ainult 2 last. Aastal Huffman puud eripära on see kõige sagedasem väärtused on esindatud kõige vähem bitti. Nägime loengu näited Morse kood, mis liiki konsolideeritud mõned tähed. Kui üritad tõlkida või E, näiteks sa tõlkimise et sageli, nii et selle asemel, et kasutada täiskomplekt bitti eraldatud, et tavapäraste andmete tüüp, siis suruma seda alla vähem, ja siis need tähed, kes on esindatud harvem on esindatud enam bitti sest sa ei saa endale lubada, et kui te kaalute välja sagedustel, et need tähed ilmuvad. Meil on sama mõte siin Huffman puud kus teeme kett, mingi tee, et saada teatud märke. Ja siis karaktereid, kes on kõige sagedus hakkavad olema esindatud võimalikult väheste bitti. 

Nii, et sa ehitada Huffman puu on, pannes kõik märgid, mis esinevad tekstis ja arvutamise sagedus, kui tihti nad ilmuvad. See võib olla kas arv on mitu korda suuremad tähed ilmuvad või ehk protsent välja kõik märgid, kui palju igaüks näib. Ja mis sa teed on, kui sul on kõik see kaardistada, siis sa ootad 2 Madalaim sagedused ja siis nendega liituda kui õed-vennad kus siis vanem sõlme on sagedus, mis on summa tema 2 last. Ja siis kokkuleppeliselt öelda, et vasak sõlme, te järgite, et pärast 0 filiaal, ja siis parempoolsem sõlm on 1 filiaali. Nagu nägime morset, üks gotcha oli see, et kui sul oleks lihtsalt piiks ja piiks see oli ebamäärane. See võiks olla kas 1 täht või see võiks olla järjekord 2 tähte. Ja mis Huffman puud ei ole, sest iseloomust tähemärki või meie lõplik tegelik tähemärki on viimane sõlmede filiaal - me nimetame neid kui lehed - tänu sellele ei saa olla mis tahes kahemõttelisust poolest, mis kirja sa üritad kodeerida mitu bitti sest kusagil mööda bitti, mis esindavad 1 täht siis sul tekib teise kogu kirjast ja seal ei ole segadust seal. Aga me astume näited, et te võib tegelikult näha, et asemel meile lihtsalt ütleb, et see on tõsi. 

Vaatame lihtsat näidet Huffman puu. Mul on string, mis käib 12 tähemärki pikk. Mul on 4 Nagu, 6 Bs, ja 2 Cs. Minu esimene samm oleks loota. Mitu korda ei ilmu? Tundub 4 korda stringi. B ilmub 6 korda, ja C ilmub 2 korda. Loomulikult ma lähen ütlen ma kasutan B kõige sagedamini nii et ma tahan esindada B võimalikult väheste bittide arv, kõige vähem 0. ja 1s. Ja siis ma lähen samuti oodata C nõuda kõige summa 0. ja 1s samuti. Esimene mida ma tegin siin ma panid need kasvavas järjekorras sageduse. Me näeme, et C ja need on meie 2 madalaim sagedustel. Loome vanem sõlme, ja et vanem sõlme ei ole kirjas sellega seotud, kuid see on sagedus, mis on summa. Summa muutub 2 + 4, mis on 6. Siis me järgime vasak haru. Kui olime, et 6 sõlme, siis me käiks 0 C-ni jõuda ja siis 1 pääseda A. Nii et nüüd on meil 2 sõlmed. Meil on väärtus 6 ja siis meil on ka teine ​​sõlm väärtus 6. Ja nii need 2 ei ole ainult 2 Madalaim vaid ka lihtsalt 2, mis on jäänud, nii me liituda need teise vanemaga, koos summa on 12. Nii et siin on meil Huffman puu kust saada B, et oleks lihtsalt bitt 1 ja siis saada meil oleks 01 ja siis K võttes 00. Nii et siin me näeme, et põhimõtteliselt me ​​neid esindavate tähemärki koos 1 või 2 bitti kus B, nagu ennustatud, on vähemalt. Ja siis me ootasime C on kõige, kuid kuna see on nii väike Huffman puu, siis on esindatud ka 2 bitti mitte kusagil keskel. 

Lihtsalt minna üle teise lihtsa näite Huffman puu, et teil on string "Tere." Mida teha, on kõigepealt pead ütleks mitu korda ei H ilmub selles? H ilmub üks kord ja seejärel e ilmub üks kord ja siis on meil l ilmumist kaks korda ja o ilmuvad kord. Ja nii siis ootame mis kirja esindab vähemalt bittide arvuga? [Üliõpilane] l. >> L. Jah. l on õigus. Ootame l olla esindatud vähemalt bittide arv sest ma kasutatakse kõige string "Tere." Mida ma teen nüüd venitama need sõlmed. Mul on 1, mis on H, ja siis veel 1, mis on e ja seejärel 1, mis on o - praegu ma kordategemine - ja siis 2, mis on l. Siis ma ütlen, et ma ehitada Huffman puu on leida 2 tippu koos vähemalt sagedused ja need õed-vennad, luues vanem sõlme. Siin on 3 sõlmed, millel on madalaim sagedus. Nad kõik 1. Nii et siin me valida, milline neist me ei kavatse siduda esimene. Oletame, et ma valin H ja e. Summa 1 + 1 on 2, kuid see sõlm ei ole kirjas sellega seotud. See lihtsalt hoiab raha. Nüüd me vaatame järgmise 2 madalaim sagedustel. See on 2 ja 1. See võiks olla üks nendest 2, kuid ma lähen valima selle ühe. Summa on 3. Ja siis lõpuks, ma ainult 2 vasakule, nii siis mis saab 5. Siis siin, nagu oodati, kui ma täita kodeering, et 1s on alati õigus filiaal ja 0. on vasakuga. Siis on meil l esindatud vaid 1 natuke ja siis o 2 ja siis e 2 ja siis H kukub 3 bitti. Nii saate edastada selle sõnumi "Tere" asemel tegelikult kasutatavate märkide mida just 0. ja 1s. Kuid pidage meeles, et mitmel juhul oli meil sidemed meie sagedust. Oleksime võinud kas liitus H ja Ö esimeses võibolla. Või siis hiljem, kui meil oli l esindatud 2 samuti liitus üks esindas 2, oleksime seotud kas ühe. 

Ja nii kui saadate 0. ja 1s, et tegelikult ei taga et teenuse kasutaja saaks täielikult lugeda oma sõnum õigus ära nahkhiir sest nad ei pruugi teada, mis otsuse sa tegid. Nii et kui me tegeleme Huffman kokkusurumine, kuidagi peame rääkima saaja meie sõnum, kuidas me otsustasime - Nad peavad teadma, mingi pildi info lisaks kokkusurutud sõnum. Nad peavad aru, mida puu tegelikult välja näeb, kuidas me tegelikult tehtud neid otsuseid. 

Siin me lihtsalt teeme näiteid aluseks tegelik arv, kuid mõnikord võib olla ka Huffman puu põhineb sagedus, mille tähed ilmuvad, ja see on täpselt sama protsess. Siin ma olen väljendades seda nii protsente või fraktsioon, ja nii siin täpselt sama asi. Ma leian, 2 madalaim, need kokku liita, järgmise 2 madalaim, need kokku liita, kuni mul on täielik puusse. Kuigi me võiksime seda teha kas nii, kui me tegeleme protsendid, see tähendab, et me jagame asju ja tegelevad kümnendkohtade või pigem hõljub kui me mõtleme andmestruktuuridega pea. Mida me teame ujukite? Mis on üldine probleem, kui me tegeleme ujukite? [Üliõpilane] Ebatäpsed aritmeetika. >> Jah. Ebatäpsusega. Kuna ujukoma ebatäpsus, selle pset nii et me veenduge, et me ei kaota väärtust, siis me tegelikult läheb tegelema loota. Nii et kui sa olid mõelda Huffman sõlme, kui te vaatate tagasi struktuuris siin, kui te vaatate roheline ones see on sagedus sellega seotud samuti osutab ta sõlme oma vasakule samuti sõlm tema õigust. Ja siis punased seal on ka märk nendega. Me ei kavatse teha eraldi välja need vanemad ja siis lõplik tippu, mida me nimetame lehed, vaid need peavad lihtsalt NULL väärtusi. Iga sõlme me peame iseloomu, sümbol, et tipp esindab, siis sagedus samuti viit selle vasak laps samuti oma õigust last. Lehed, mis on väga põhjas, oleks ka sõlme viiteid oma vasakule ja õigust, kuid kuna need väärtused ei ole osutab tegelik tippu, milline oleks nende väärtus olla? >> [Üliõpilane] NULL. >> NULL. Täpselt. Siin on näide, kuidas võiks esindada sagedus ujukite, kuid me ei kavatse tegelema seda täisarvud, nii ma tegin, on muuta andmete tüüp seal. 

Lähme edasi natuke rohkem keeruline näide. Aga nüüd, et me oleme teinud lihtsaid, see on lihtsalt sama protsessi. Leiad 2 Madalaim sagedusi, kokku sagedused ja ongi uus sagedus teie vanem sõlme, mis siis osutab oma vasaku koos 0 filiaali ja paremale 1 filiaali. Kui meil on string "See on cs50", siis me kokku, mitu korda on T mainitud, h mainitud, I, S, C, 5, 0. Siis mida ma tegin siin on punase sõlmede ma lihtsalt istutada, Ma ütlesin, et ma lähen on need märgid lõpuks allosas minu puu. Need hakkavad olema kõik lehed. Siis mida ma tegin on mul järjestatud nende esinemissageduse järgi kahanevas järjekorras, ja see on tegelikult nii, et pset koodi see on see jõuaks seda sagedust ja siis tähestikulises järjekorras. Seega on numbrid ja alles seejärel tähestiku sageduse järgi. Siis mida ma teen on minu leiaks 2 madalaim. See on 0 ja 5. Ma liidaks neid, ja see on 2. Siis ma jätkata, leida järgmise 2 madalaim. Need on kaks 1s ja siis need muutuvad 2 samuti. Nüüd ma tean, et minu järgmine samm saab olema liitumist väiksem number, mis on T-1 ja seejärel valida üks tippe, mis on 2 kuna sagedust. Nii et siin on meil 3 võimalust. Mida ma teha slaidi lihtsalt visuaalselt ümber neid teile nii et saate näha, kuidas ma praegu luuakse. Mis koodi ja levitamine kood kavatseb teha oleks liituda T ühe koos 0 ja 5 sõlme. Nii siis, et summad 3, ja siis me protsessi jätkata. 2 ja 2 nüüd on madalaim, nii siis need summa kuni 4. Igaüks pärast nii palju? Okei. Siis pärast, et meil on 3 ja 3, et tuleb kokku liita, nii et jälle ma lihtsalt sisselülitamist nii, et sa näed visuaalselt nii et see ei saa liiga räpane. Siis on meil 6 ja seejärel meie viimane samm on nüüd, et meil on ainult 2 tippu me Kokkuvõttes need teha just meie puu, mis on 10. Ja number 10 on mõistlik, sest iga sõlm esindab, nende väärtus, sagedus arv oli mitu korda nad ilmusid stringi, ja siis meil on 5 tähemärki meie string, nii et on mõtet. Kui me vaatame üles, kuidas me tegelikult kodeerida seda, ootuspäraselt, i ja s, mis tunduvad kõige sagedamini on esindatud kõige vähem bitti. 

Olge siin. Aastal Huffman puud juhul tegelikult oluline on. Suur-S on teistsugune kui väiketähti s. Kui meil oleks "See on CS50" suurte tähtedega, siis väiketähti s, mis ilmnevad alles kaks korda, oleks sõlme 2 kui selle väärtus, ja siis suur-S oleks ainult üks kord. Nii et siis oma puu muudaks struktuurid sest sa tegelikult pildi leht siin. Aga summa ikkagi 10. See, mida me tegelikult hakatakse kutsudes kontrollsumma, Lisaks kõigi loeb. 

Nüüd, kui oleme kaetud Huffman puud, saame sukelduda Huff'n Puff, pset. Me läheme alustada osas küsimusi, ja see läheb sulle harjunud koos kahendpuuks ja kuidas tegutseda umbes, et: joonistus tippu, luues oma typedef struktuure jaoks sõlme, ja näha, kuidas sa võiksid lisada kahendpuu, üks, mis on sorteeritud, liiklevad, ja asjad niimoodi. See teadmine on kindlasti kavatse sind aidata, kui sa sukelduda Huff'n Puff osa Euroopa pset. In standard väljaanne pset, teie ülesanne on rakendada Puff, ja häkker versioon teie ülesanne on rakendada Huff. Mis Huff ei ole see võtab teksti ja siis see tõlgib see 0. ja 1s, nii protsess, mis me tegime eespool, kus me lugeda sagedused ja siis tehakse puust ja siis ütles: "Kuidas ma saan T?" T on esindatud 100, asju, ja siis Huff võtaks teksti ja siis väljund, et binaarne. Aga ka sellepärast, et me teame, et me tahame, et meie saaja sõnum taasluua täpselt sama puu, see sisaldab ka teavet sagedus loeb. Siis Puff oleme andnud binaarne fail 0. ja 1s ja antud ka infot sagedustel. Tõlgime kõiki neid 0. ja 1s tagasi algse sõnumi, mis oli, nii et me oleme mahalaadimine et. Kui sa teed Standard Edition, sa ei pea rakendama Huff, nii siis võid lihtsalt kasutada töötajate rakendamist Huff. On juhiseid spec, kuidas seda teha. Võite käivitada töötajate rakendamist Huff peale teatud tekstifaili ja siis kasutada, et väljund oma panuse Puff. 

Nagu ütlesin, on meil palju jaotus kood see üks. Ma lähen alustada läbimas seda. Ma veedan suurema osa ajast. H failid sest. c faili, sest meil on. h ja mis annab meile prototüübid funktsioone, me täielikult ei pea täpselt teadma - Kui te ei saa aru, mis siin toimub. C faili, siis ärge muretsege liiga palju, kuid kindlasti proovida heita, sest see võib anda mõned vihjed ja see on kasulik harjuda lugemine teiste inimeste koodi. 

Vaadates huffile.h, oma kommentaarides ta deklareerib kiht võtmiseks jaoks Huffman kodeeritud faile. Kui me läheme, näeme, et seal on kuni 256 sümbolid, et me võib-olla koodid. See hõlmab kõiki tähestiku tähti - suuri ja väikeseid - ja siis sümbolid ja numbrid jne Siis on meil siin magic number Huffman kodeeritud faili. Jooksul Huffman kood nad lähed on teatud maagiline number seotud päises. See võib tunduda just juhuslikult maagiline number, aga kui sa tegelikult seda tõlkida ASCII, siis tegelikult sõnastab Huff. Siin on meil struct jaoks Huffman kodeeritud faili. Seal on kõik need omadused, mis on seotud Huff faili. Siis siin all on meil päises Huff faili, nii et me nimetame seda Huffeader lisamise asemel pildi h sest see kõlab sama niikuinii. Armas. Meil on maagiline number on seostatud sellega. Kui see on tegelik Huff faili, see saab olema number kuni eespool, see maagiline üks. Ja siis see on massiiv. Nii et iga sümbol, mida on 256, see läheb nimekirja, mida sagedus need sümbolid kuuluvad Huff faili. Ja siis lõpuks, meil on kontrollsumma sagedused, mis peaks olema summa nende sagedustel. Nii see on, mida Huffeader on. Siis meil on mõned funktsioonid, mis tagastavad kõrval natuke Huff fail samuti kirjutab natuke Huff faili ja siis see funktsioon siin, hfclose, et tegelikult sulgeb Huff faili. Enne olime tegelevad otse lihtsalt kirjutamisel, aga kui sul on Huff faili asemel fclosing see mida sa tegelikult tegema hakkad on hfclose ja hfopen ta. Need on konkreetsed ülesanded Huff faile, me ei kavatse tegelema. Siis siin loeme päises ja siis kirjutage päises. 

Lihtsalt lugedes. H fail saame omamoodi saada tunnet, mida Huff fail võib olla, millised omadused tal on, ilma päriselt sinna huffile.c, mis, kui me sukelduda, saab olema natuke keerulisem. See on kõik faili I / O siin tegemist suunanäitajaks. Siin näeme, et kui me kutsume hfread, näiteks, see on ikka tegelevad fread. Me ei vabaneda neid ülesandeid täielikult, kuid me saadame need tuleb hoolitseda sees Huff faili asemel teeb see kõik ise. Võite julgelt skaneerimise abil seda, kui sa oled uudishimulik ja minna ja koor kiht veidi tagasi. 

Järgnevat pilti, et me ei kavatse pilk on tree.h. Enne sisse kiirtutvustus libiseb me ütlesime me ootame Huffman sõlme ja tegime typedef struktuure sõlme. Me ootame, et on sümbol, sagedus, ja siis 2 sõlme tähte. Sel juhul, mida me teeme on see sisuliselt sama välja arvatud asemel sõlme me ei kavatse nimetada neid puid. Meil on funktsioon, et kui helistate teha puu see naasete puu pointer. Tagasi Speller, kui sa tegid uue tipu sa ütlesid sõlme * uus sõna = malloc (sizeof) ja asjad niimoodi. Põhimõtteliselt mktree läheb tegeleb selle sulle. Samamoodi, kui soovite eemaldada puud, Nii et sisuliselt vabastades puu, kui oled hakkama saanud, asemel selgesõnaliselt helistades tasuta, et sa oled tegelikult lihtsalt kavatse kasutada funktsiooni rmtree kuhu viiakse kursor selle puu ja siis tree.c hoolitseme, et teie jaoks. 

Me vaatame tree.c. Ootame samad funktsioonid, välja arvatud näha rakendamise samuti. Nagu me ootasime, millal sa helistada mktree see mallocs suurus puu sisse pointer, algväärtustab kõik väärtused väärtus NULL, nii 0s või NULLS, ning tagastab viida, et puud, mis sa oled malloc'd teile. Siin, kui helistate eemaldada puu see esimene tagab, et te ei ole topelt vabastamine. See tagab, et te tegelikult on puu, mida soovite eemaldada. Siin sest puu on ka oma lapsed, Mis see on see rekursiivselt kutsutakse eemaldada puud vasakul sõlme puu samuti õigus sõlme. Enne see vabastab vanem, ta vajab, et vabastada lapsed samuti. Vanem on ka vahetatavad juur. Esimene vanem, nii nagu vana-vana-vana-vana-vanaisa või vanaema puu, esiteks, me peame tasuta alla tasanditel esiteks. Nii risti põhja, tasuta need, ja siis tagasi tulla üles, vabasta need, jne Nii et see puu. 

Nüüd vaatame metsa. Mets on kui paned kõik oma Huffman puud. See on selge, et me ei kavatse on midagi, mida nimetatakse krunt , mis sisaldab viit puud samuti kursor krunt kutsus järgmise. Mida struktuur teeb selliseid välja näeb? See liik ütleb, et see on seal. Siinsamas. Seotud nimekirja. Me näeme, et kui meil on krunt see on nagu seotud nimekirja krundid. Mets on määratletud seotud nimekirja krundid, ja nii struktuuri mets on me lihtsalt läheb on kursor meie esimene krunt ja et krunt on puu sees või pigem viitab puu ja siis punkti järgmisele krunt, nii edasi ja nii edasi. Selleks, et metsa kutsume mkforest. Siis on meil päris kasulikud funktsioonid siin. Meil on valida, kuhu viiakse metsa ja siis tagastatav väärtus on Tree * kursor puu. Mis pick teeb on see läheb metsa, et sa osutades Seejärel eemaldage puu madalaima sagedusega, et metsa ja siis annan teile kursor selle puu. Kui te helistate valida, puu ei eksisteeri metsas enam kuid tagastatav väärtus on kursor, et puu. Siis on taim. Eeldusel, et sa läbima viit puu, mis on mitte-0 sagedus, Mis taim teeb on see võtab metsa võtma puust ja taim, mis puu sees metsa. Siin on meil rmforest. Sarnased eemaldada puud, mis põhimõtteliselt vabastada kõik meie puud meie jaoks, eemaldada mets tasuta kõike sisalduv et metsa. 

Kui me vaatame forest.c, me oodata vähemalt 1 rmtree käsk sinna, sest vaba mälu metsas kui metsas on puud see, siis lõpuks sa lähed on eemaldada need puud ka. Kui me vaatame forest.c on meil mkforest, mis on nagu me ootame. Me malloc asju. Me initsialiseerida esimene krundile metsa NULL, sest see on tühi alustada, siis näeme pick, mis tagastab puu madalaima kaalu, mis on madalaim sagedus, ja siis läheb lahti, et eelkõige sõlme, mis osutab, et puude ja järgmise, nii et see võtab, et välja on seotud nimekirja metsas. Ja siis on meil siin taim, mis lisab puult seotud nimekirja. Mis metsas ei ole see kenasti hoiab ta järjestatud meile. Ja siis lõpuks, meil on rmforest ja ootuspäraselt meil rmtree hüüdis seal. 

Vaadates jaotust koodi seni, huffile.c oli ilmselt kõige raskem mõista, arvestades, et muid faile ise olid üsna lihtne järgida. Meie teadmised viiteid ja lingitud nimekirjad ja need, suutsime järgida päris hästi. Aga kõik me peame tõesti veenduda, et me mõistame on. H failid sest sa pead olema kutsudes neid ülesandeid, tegeledes nendega, kes tagastab väärtuste, nii et veenduge, et Te saate täielikult aru, missuguseid meetmeid on plaanis teha kui sa nimetad üks neist funktsioone. Aga tegelikult mõista sees see ei ole päris vajalik, sest meil on need. H faile. Meil on veel 2 faili lahkus meie jaotus kood. 

Vaatame prügimäele. Dump oma kommentaar siia võtab Huffman-tihendatud fail ja siis tõlgib ja puistab kõik selle sisu välja. Siin näeme, et see helistab hfopen. See on omamoodi peegeldamine FILE * sisse = fopen, ja siis te kaotate teabes. See on peaaegu identsed, välja arvatud asemel faili * sa läbides Huffile; asemel fopen sa läbides hfopen. Siin me loeme päises esimene, mis on omamoodi sarnane sellele, kuidas me loeme päises jaoks bitmap faili. Mis me teeme siin on kontrollides, et näha, kas päiseteavet sisaldab õigust maagiline number, mis näitab, et see on tegelik Huff faili siis kõik need kontrollid veendumaks, et fail, mida me avatud on tegelik puhises fail või mitte. Mis see on see väljundid sagedused kõik sümbolid, mis me näeme jooksul terminal graafiline tabel. See osa saab olema kasulik. See on natuke ja loeb vähehaaval arvesse muutuva natuke ja siis trükib selle välja. Nii et kui ma kutsun prügila kohta hth.bin, mis on tingitud huffing fail kasutades personal lahendus, ma saaksin seda. See kirjutamine kõiki neid tähti ja siis paneb sagedus, mille juures nad ilmuvad. Kui me vaatame, enamik neist on 0. väljaarvatud selle: H, mis ilmub kaks korda, ja siis T, mis ilmub kord. Ja siis on meil siin tegelik sõnum 0. ja 1s. Kui me vaatame hth.txt, mis on arvatavasti algne sõnum, mis oli puhises, ootame mõned Hs ja Ts seal. Nimelt ootame vaid 1 T ja 2 HS. Siin me oleme hth.txt. See tõepoolest on HTH. Kuulub sinna, kuigi me seda ei näe, on reavahetus sümbol. Huff faili hth.bin ka kodeeriva reavahetus sümbol samuti. Siin sest me teame, et selleks on HTH ja siis reavahetus, näeme, et tõenäoliselt H on esindatud ainult üks 1 ja siis T on ilmselt 01 ja siis järgmine H 1 ning ja siis on meil reavahetus näitavad kaks 0.. Lahe. 

Ja siis lõpuks, sest me tegeleme mitu. C ja. H failid, me lähed on päris keeruline argument kompilaator, ja nii on meil siin Makefile, mis muudab prügila teile. Aga tegelikult, sa pead minema umbes tehes oma puff.c faili. Makefile tegelikult ei tegele tegemise puff.c teile. Me lahkume, et kuni redigeerida Makefile. Kui sisestad käsu nagu teevad kõik, näiteks, see teeb neile kõigile teile. Julgelt vaadata näiteid Makefile minevikust pset samuti läheb maha selle ühe näha, kuidas sa võiksid teha oma Puff fail muutes selle Makefile. Ja ongi meie jaotus kood. 

Kui oleme saanud läbi, et siis siin on lihtsalt üks meeldetuletus kuidas me kavatseme tegelema Huffman sõlmed. Me ei kavatse olla kutsudes neid tippe enam, me ei kavatse olla kutsudes neid puid kuhu me läheme, mida esindavad nende sümbol char, nende sagedus, esinemiste arv, kus täisarv. Me kasutame seda, sest see on täpsem kui sularahaga. Ja siis on meil veel üks osuti vasakule laps samuti õigus laps. Metsa, nagu nägime, on lihtsalt seotud nimekirja puud. Lõppkokkuvõttes, kui me ehitame üles meie Huff faili me tahame, et meie metsa sisaldada vaid 1 puu - 1 puu, 1 root mitme lastele. Varem, kui me just muutes meie Huffman puud, alustasime paigutades kõik sõlmed peale meie ekraanil ja ütle, et me lähed on need sõlmed, lõpuks nad ei kavatse olla lehed, ja see on nende sümbol, see on nende sagedus. Meie metsa kui me lihtsalt 3 tähte, mis on metsa 3 puud. Ja siis kui me minna, kui me lisame esimesel vanem, tegime metsa 2 puud. Me eemaldada 2 neist lastest meie metsade ja seejärel asendas selle vanem sõlme et oli neid 2 sõlmed nagu lapsed. Ja siis lõpuks, meie viimane samm, et meie näiteks Nagu, BS ja Tingimused oleks teha lõplik vanem, ja nii siis mis tooks meie koguarvule puud metsas 1. Kas igaüks vaadata, kuidas hakkate läbi mitu puud oma metsast ja lõpuks 1? Okei. Lahe. 

Mida me vajame, et teha Puff? Mida me peame tegema, on tagada, et alati, nad annavad meile õiget tüüpi sisend nii et me saame tegelikult käivitada programmi. Sel juhul nad ei kavatse anda meile pärast oma esimese käsurea argument 2 rohkem: fail, mida tahame lahti ja väljund hõrendatakse faili. Aga kui me veenduge, et nad on läbinud meid õiges summas väärtused, me soovime tagada, et sisend on Huff fail või mitte. Ja siis kui me garanteerida, et see on Huff faili, siis me tahame ehitada meie puu, ehitada puu nii, et see sobib puu, et inimene, kes saatis sõnumi ehitatud. Siis pärast me ehitada puu, siis saame tegeleda 0. ja 1s et nad sooritanud, järgige neid mööda meie puu, sest see on identsed, ja siis kirjutada, et sõnum välja, tõlgendada bitti tagasi tähemärki. Ja siis lõpus, sest me tegeleme vihjeid siin, tahame veenduda, et me ei ole mingit mälu lekked ja et me tasuta kõike. 

Tagada nõuetekohane kasutamine on vana müts meiega nüüd. Me võtame ka sisend, mis saab olema faili nimi pahv, ja siis me täpsustada väljund, nii faili nime jaoks paisutatud väljund, mis on tekstifaili. See on kasutamist. Ja nüüd me tahame tagada, et sisend on puhises või mitte. Mõeldes tagasi, oli seal midagi jaotus kood, mis aitaks meil arusaamisega, kas fail on puhises või mitte? Oli teavet huffile.c umbes Huffeader. Me teame, et iga Huff fail on Huffeader seotud see maagiline number samuti hulgaliselt sagedused iga sümbol samuti kontrollsumma. Me teame seda, kuid me võtsid ka piiluda dump.c, kus ta luges sisse Huff faili. Ja nii teha, et ta pidi kontrollima, kas see tõesti oli puhises või mitte. Nii et ehk me võiksime kasutada dump.c nagu struktuuri meie puff.c. Tagasi pset 4, kui meil oli faili copy.c et kopeeritud RGB kolmikute ja me tõlgendada, et Dekkari ja suuruse muutmine, Samamoodi mida sa võiksid teha, on lihtsalt käivitada käsk nagu cp dump.c puff.c ja kasutada mõningaid kood seal. Kuid ta ei kavatse olla nii lihtne protsessi tõlkimisega dump.c arvesse puff.c, kuid vähemalt see annab teile kuskil alustada kuidas tagada, et sisend on tegelikult puhises või mitte samuti mõned muud asjad. Meil on taganud nõuetekohast kasutamist ja tagatakse, et sisend on puhises. Iga kord, kui me oleme teinud, et me oleme teinud oma õige veatuvastuse, nii tagasi ja suitsetamisest funktsiooni kui mõned tõrge, kui seal on probleem. 

Nüüd, mida me tahame teha, on luua tegelik puu. Kui me vaatame Forest on 2 põhiülesanded et me ei kavatse tahad saada väga tuttav. Seal on Boole'i ​​funktsioon taime taimed mitte-0 sagedus puu sees meie metsa. Ja nii sa läbima kursor metsa ja viit puud. Kiire küsimus: Kui palju metsi teil on, kui sa oled hoone Huffman puu? Meie metsas on nagu meie lõuend, eks? Nii et me ainult kavatse olla 1 metsa, kuid me ei kavatse olla mitu puud. Nii et enne helistamist taim, sa oled ilmselt läheb tahad teha oma metsast. On käsk, et kui sa vaatad forest.h kohta kuidas saate teha metsa. Te saate taime puu. Me teame, kuidas seda teha. Ja siis võite valida ka metsast, eemaldades puu madalaima kaalu ja annab teile kursor sellele. Mõeldes tagasi ajale, mil me tegime näited ise, kui olime joonistus välja, me lihtsalt lihtsalt lisada linke. Aga siin mitte lihtsalt lisades lingid, ma arvan et rohkem kui sa eemaldades 2 nende sõlmede ja seejärel asendada see teine. Väljendada, et nii korjamine ja istutusmaterjali, olete korjamine 2 puud ja seejärel istutada uue puu millel on need 2 puud, mida korjatakse nagu lapsed. Et ehitada Huffman on puu, saate lugeda sümbolid ja sageduste sest Huffeader annab selle sulle, annab teile array sagedustel. Nii saate edasi minna ja lihtsalt ignoreerida midagi 0 see sest me ei taha 256 lehed lõpus ta. Me tahame ainult mõned lehed, mis on märki mis on tegelikult kasutatud faili. Te saate lugeda ka need sümbolid ja kõik need sümbolid, mis on mitte-0 sagedused, need hakkavad olema puud. Mida saab teha, on iga kord, kui lugeda mitte-0 sagedus sümbol, saate taime puu metsas. Kui sa taime puud metsas, võite liituda need puud nagu õed-vennad, nii läheb tagasi istutamine ja korjamine kus on võimalik valida 2 ja siis taim 1 kui see 1, et te taime on vanem 2 last, et valisite. Nii siis teie lõpptulemus saab olema ühe puu oma metsas. See, kuidas teil ehitada oma puu. 

On mitmeid asju, mis võiks valesti minna siin sest me tegeleme teha uusi puid ja tegelevad viiteid ja asjad niimoodi. Enne kui me tegelesime suunanäitajaks, kui me malloc'd tahtsime veenduda, et see ei andnud meile nullviida väärtus. Nii et mitu sammu selles protsessis seal saab olema mitmeid juhtumeid kus teie programm võiks ebaõnnestuda. Mida sa tahad teha, on sa tahad teha kindel, et sa hakkama neid vigu, ja spec ta ütleb neid lahendab nõtkelt, Nii nagu välja printida sõnumi kasutaja neile öelnud, miks programm on loobuda ja siis kohe lahkud. Selleks veakäsitlust, pea meeles, et sa tahad seda kontrollida iga kord, et võib esineda rike. Iga kord, et te teete uue pointer sa tahad teha kindel, et see on edukas. Enne mida olime harjunud tegema, on teha uus osuti ja malloc see, ja siis me kontrollida, kas see pointer on NULL. Nii et ei kavatse olla mõned juhtumid, kus saab lihtsalt teha, et kuid mõnikord sa tegelikult kutsutakse funktsioon ja selles funktsioon, see on üks, mis teeb mallocing. Sellisel juhul, kui me vaatame tagasi teatud funktsioone jooksul koodi, mõned neist on Boole'i ​​funktsioonid. Teoreetiliselt juhul kui meil on Boole'i ​​funktsioon nimega foo, Põhimõtteliselt võime eeldada, et lisaks teha kõik foo teeb, kuna see on Boole'i ​​funktsioon, siis tagastab true või false - tõsi kui see õnnestub, vale, kui mitte. Nii et me tahame kontrollida, kas tagastatav väärtus foo on õige või vale. Kui see on vale, see tähendab, et me ei kavatse soovite printida mingi sõnum ja seejärel sulgege programm. Mida me tahame teha, on kontrollida tagastatav väärtus suva. Kui foo tagastab false, siis me teame, et me tekkinud mingi viga ja me peame loobuma meie programm. Viis seda teha on on seisund, kus tegelik funktsioon ise on oma tingimus. Ütle suva võtab X. Meil võib olla tingimusena if (foo (x)). Põhimõtteliselt tähendab see, et kui lõpus täidesaatva suva see tagastab tõsi, siis saame seda teha, sest funktsioon peab hindama foo et hinnata kogu seisukorras. Nii siis, et kuidas saab midagi teha, kui funktsioon tagastab tõese ja on edukas. Aga kui sa oled veatuvastuse, siis ainult taha loobuda, kui teie funktsioon tagastab false. Mida võiks teha, on lihtsalt lisada == false või lihtsalt lisada paugu ta ees ja siis on teil if (! suva). Jooksul, et keha selle tingimuse siis oleks kõik veakäsitlust nii meeldib, "Ei saa luua seda puud" ja siis tagasi 1 või midagi sellist. Mida see teeb, kuigi see, et kuigi foo tagasi vale - Ütle suva tagastab tõsi. Siis sa ei pea helistada suva uuesti. See on levinud eksiarvamus. Sest see oli sinu seisund, see on juba hinnatud, nii sul on juba tulemus, kui te kasutate teha puu või midagi sellist või taime või pick või midagi. See on juba selline väärtus. See on juba täidetud. Nii et see on kasulik kasutada Boole'i ​​funktsioonid, kui tingimus sest kas te tegelikult täidab keha silmus, ta täidab funktsiooni niikuinii. 

Meie poolt teine ​​samm on kirjutame sõnum faili. Kui me ehitame Huffman puu, siis kirjutame sõnum fail on üsna lihtne. See on päris lihtne nüüd lihtsalt järgige 0. ja 1s. Ja nii kokkuleppeliselt me ​​teame, et Huffman puu 0s näitavad vasakule ja 1s näitavad õigus. Siis kui sa lugeda vähehaaval, iga kord, kui sa saad 0 saate jälgida vasak haru ja siis iga kord, kui lugeda 1 sa lähed järgima õiguse filiaal. Ja siis sa lähed seni, kuni te tabanud lehed sest lehed hakkavad olema lõpus filiaalid. Kuidas me saame öelda, kas oleme tabanud lehtedega või mitte? Me ütlesime seda varem. [Üliõpilane] Kui osuti on NULL. >> Jah. Me ei saa öelda, kui oleme tabanud lehed kui viiteid nii vasakule ja paremale puud on NULL. Perfect. Me teame, mida me tahame lugeda vähehaaval meie Huff faili. Nagu nägime varem dump.c, mida nad tegid on nad lugeda vähehaaval sisse Huff fail ja lihtsalt välja printida, millised need jupid. Me ei kavatse seda teha. Me hakkame tegema midagi, mis on natuke keerulisem. Aga mida me teha saame, on meil võimalik võtta, et natuke koodi, mis loeb sisse natuke. Siin on meil täisarv natuke kujutavad praegust natuke, et me oleme. See hoolitseb itereerimise kõik bittide fail kuni vajutad faili lõppu. Tuginedes sellele, siis sa lähed, et tahad olla mingi iteraatori läbida oma puu. Ja siis selle põhjal, kas natuke on 0 või 1, sa lähed tahan kas liikuda, et iteraatori vasakule või liigutada paremale kogu tee kuni jõuate lehed, nii et kõik viis kuni selle sõlme, et sa oled ei viita veel sõlmed. Miks me saame seda teha koos Huffman faili, kuid ei Morse kood? Sest morsetähestik seal natuke ebaselgeks. Meil võiks olla nagu, oh oota, oleme tabanud kirja teel, et äkki see on meie kirjale arvestades, et kui me jätkame lihtsalt veidi kauem, siis me oleks tabanud veel ühe kirja. Aga see ei juhtu ka Huffman kodeerimine, nii saame olla kindlad, et ainus viis, et me ei kavatse tabanud iseloomuga on kui see sõlm vasakule ja paremale lapsed on NULL. 

Lõpuks tahame vabastada kõik meie mälu. Me tahame nii lähedale Huff faili, et oleme arutanud samuti eemaldada kõik puud meie metsas. Tuginedes oma rakendamise, sa oled ilmselt läheb soovite helistada eemaldada metsa asemel tegelikult läbimas kõik puud ise. Aga kui te olete teinud ajutise puud, tahad, et vabastada seda. Sa tead oma koodi parim, et sa tead, kuhu eraldatakse mälu. Ja kui te lähete, alusta isegi kontrolli F'ing jaoks malloc, nähes kui sa malloc ja veenduge, et teil vabastama kõik selle aga siis lihtsalt läbimas oma koodi, mõista, kus sa võisid eraldatud mälu. Tavaliselt võid lihtsalt öelda: "Lõpus fail Ma lihtsalt eemaldada metsa minu metsa" nii et põhimõtteliselt on selge, et mälu, vaba, et "Ja siis ma lähen samuti toimiku sulgemise ja siis minu programm läheb loobuda." Aga see, et ainus kord, kui teie programm sulgub? Ei, sest mõnikord on võinud olla viga, mis juhtus. Võib-olla me ei suutnud avada faili või me ei saaks teha teise puu või mingi viga juhtus mälu eraldamise protsessi ja nii see tagastatakse NULL. Viga juhtus ja siis tagasi ja lõpetan. Nii siis tahan veenduda, et iga võimaliku aja jooksul, et teie programm võib loobuda, soovite vabastada kõik oma mälu seal. See ei ole lihtsalt saab olema päris lõpus peamine funktsioon, et sa loobud oma kood. Sa tahad vaadata tagasi igal juhul, et kood potentsiaalselt võib naasta enneaegselt ja siis vaba iganes mälu mõtet. Ütle, et kutsus tegema metsa ja mis tagastatakse vale. Siis sa ilmselt ei vaja eemaldada oma metsa sest sa ei pea metsa veel. Ent igal hetkel kood, kus te võite naasta enneaegselt sa tahad teha kindel, et sa vabastada võimalikest mälu. 

Nii et kui me tegeleme vabastades mälu ja millel on potentsiaal lekkeid, me tahame mitte ainult kasutada meie otsus ja meie loogika vaid ka kasutada Valgrind kas me oleme vabanenud kõik meie mälu korralikult või mitte. Võite käivitada Valgrind kohta Puff ja siis sa pead ka andke seda õige mitu käsurea argumente Valgrind. Võite käivitada, kuid toodang on veidi segasena. Me oleme saanud natuke kasutatakse seda Speller, kuid peame siiski veidi rohkem abi, nii siis töötab ta veel mõned lipud nagu lekke-check = täis, et tõenäoliselt annab meile rohkem abiks toodangut Valgrind. 

Siis veel üks kasulik näpunäide, kui olete silumine on käsu diff. Võite kasutada töötajate rakendamist Huff, joosta, et tekstifaili ja siis tulemuse selle binaarfaili, binaarne Huff faili, eripäraseks. Siis kui sa jooksed oma pahv, et binaarfaili siis ideaalis oma Väljundfailid tekstifaili saab olema identne esialgse üks, et olete sooritanud sisse Siin ma kasutan hth.txt nagu näiteks, ja see on üks rääkis oma spec. See on sõna otseses mõttes lihtsalt HTH ja siis reavahetus. Aga kindlasti tunda vaba ja olete kindlasti julgustada kasutama enam näiteid oma teksti faili. 

Saate ka tulistas võibolla pakkimist ja siis mahalaadimine mõned failid, mida kasutatakse Speller nagu Sõda ja rahu või Jane Austeni või midagi sellist - et oleks selline lahe - või Austin Powers, selline tegelevad suuremate failide sest me ei tulnud maha see kui me kasutada järgmise tööriista siin, ls-l. Me oleme harjunud ls, mis põhimõtteliselt on loetletud kõik sisu meie praeguses kataloogis. Läbivad lipu-l tegelikult kuvab suurus need failid. Kui te lähete kaudu pset spec, siis tegelikult te loeksite luua binaarfaili kohta huffing see, ja te näete, et väga väikeste failide ruumi maksumus pakkimata ja tõlkides kõik, et teave kõik sagedused ja asjad, mis kaalub üles tegelik kasu kokkusurumise fail esiteks. Aga kui sa jooksed selle mõned pikemat teksti faili, siis võite näha, et hakkate saada teatud kasu aastal kokkusurumise neid faile. 

Ja siis lõpuks oleme meie vana semu GDB, mis on kindlasti kavatse tulla mugav ka. 

Kas meil on lisaküsimusi Huff puud või protsessi ehk tegemise puud või lisaküsimusi Huff'n Puff? Okei. Ma jään umbes natuke. 

Tänu kõigile. See oli kiirtutvustus 6. Ja õnne. 

[CS50.TV]