[Powered by Google Translate] [Walkthrough - Проблем Set 6] [Zamyla Chan - Харвардския университет] [Това е CS50. - CS50.TV] 

Здравейте на всички, и добре дошли Walkthrough 6: Huff'n Puff. В Puff Huff'n това, което правим, ще се занимава с Huffman компресиран файл и след това пухтене назад, така че декомпресиране, така че можем да преведем от 0s и 1s, че потребителят ни изпраща и да го конвертирате обратно в оригиналния текст. Pset 6 ще бъде много готино, защото вие ще видите някои от инструментите който сте използвали в pset 4 и pset 5 и вид на обединяването им в един доста чист концепция когато дойдеш да мисля за това. 

Също така, може би, pset 4 и 5 са ​​най-голямото предизвикателство psets, че ние трябва да предлагат. Така че от сега, имаме още 1 pset в C, и тогава, след това сме на уеб програмирането. Така че сами поздравя за преодоляването на най-тежката гърбица в CS50. 

Преминавайки за Puff Huff'n, инструментариум за тази pset са ще бъде Хъфман дървета, това разбиране не само как двоичен работа дърветата, но също така и специално Хъфман дървета, как те са построени. И тогава ние ще трябва много код на разпределение в тази pset, и ние ще дойдем да видим, че всъщност част от кода ние може да не е в състояние да разберат напълно още, и така тези, които ще бъдат в файлове, но след това придружаващите ги з файлове ще ни даде достатъчно разбиране, че ние трябва да знаем как тези функции работят или поне това, което трябваше да направя - техните входове и изходи - дори и ако ние не знаем какво се случва в черната кутия или не разбират какво се случва в черната кутия в. И накрая, както обикновено, ние се занимаваме с нови структури от данни, специфични видове възли, които сочат към някои неща, и така тук с писалка и хартия не само за процеса на проектиране и когато се опитвате да разбера как си pset трябва да работят но също така и по време на отстраняване на грешки. Можете да имате GDB заедно с писалка и хартия, докато ви отведе определяне какви са стойностите, когато стрелките са насочени, и такива неща. 

Първо нека погледнем дървета Хъфман. Huffman дървета са двоични дървета, което означава, че всеки възел има само две деца. По дърветата Хъфман характеристика е, че най-често срещаните стойности са представени от най-малко бита. Видяхме в лекциите примери на морзовата азбука, какъв вид на консолидирания някои букви. Ако се опитвате да превежда А или Е, например, сте превода, че често, така че вместо да се налага да се използва пълният набор от битове разпределят за тази обичайния тип данни, да го компресира до по-малко, и след това тези писма, които са представени по-рядко са представени с по-дълги бита защото можете да си позволите, че когато се претеглят честоти, че тези писма се появяват. Ние имаме същата идея тук, в дървета Хъфман , където ние правим верига, един вид път да стигнем до определени символи. И тогава героите, които имат най-честотата ще бъде представена с най-малко бита. 

Начина, по който изгради едно дърво на Хъфман е чрез поставяне на всички символи, които се появяват в текста и изчисляване на честотата им, колко често те се появяват. Това може да бъде или броят колко пъти по-високи от тези букви се появяват или може би един процент от всички герои колко се появява всеки един. И така, това, което правите, е след като имате всички, че начертан, търсите две ниските честоти и след това да се присъедини към тях като братя и сестри където майка възел има честота, което е сумата от нейните две деца. И тогава по силата на споразумение казват, че лявата възел, следва, че след 0 клон, и след това най-дясната възел е 1 клон. Както видяхме в морзовата азбука, нещо, за което е, че ако сте имали само звуков сигнал и сигнал тя е двусмислен. Тя може да бъде или една буква или тя може да бъде поредица от две букви. И така, какво Huffman дървета е така, защото по природа на героите или нашите окончателните реалните герои са последните възли в бранша - ние наричаме като листа - по силата на това, че не може да бъде всякакво двусмислие по отношение на коя буква се опитвате да кодирате с поредица от битове защото никъде по протежение на бита, които представляват 1, буква ще срещнете друг цялото писмо, и там няма да има объркване там. Но ние ще отидем в примери, че вие ​​действително може да видите, че вместо нас просто ви казвам, че това е вярно. 

Нека разгледаме един прост пример на едно дърво на Хъфман. Имам низ, че тук е 12 знака. Имам 4 като 6 BS, и 2 Cs. Първата ми стъпка ще бъде да се брои. Колко пъти се появи? Той се появява четири пъти в низа. B се появява шест пъти, а C се появява два пъти. Естествено, аз ще да кажа, че съм с Б, най-често, така че аз искам да представляват Б с най-малък брой битове, най-малък брой на 0s и 1s. И тогава аз ще да се очаква, C, както и да изисква най-голямо количество на 0s и 1s. Първо това, което направих тук Аз ги поставя във възходящ ред по отношение на честотата. Виждаме, че С и А, това са нашите два най-ниските честоти. Ние създаваме възел, майка и този възел майка не разполага с писмо, свързани с нея, но тя има честота, която е сумата. Сумата става 2 + 4, което е с 6. След това ние следваме по лявото отклонение. Ако бяхме в този възел 6, а след това ще последва 0, за да стигнем до C и след това 1 да стигнем до А. Така че сега имаме два възли. Имаме стойност 6 и след това ние също имаме друг възел със стойност 6. И така, тези две са не само две най-ниската, но само две, които са оставени, така че ние се присъединя към тези от друг родител, като сумата е 12. Така че тук ние имаме Хъфман дърво къде да стигнем до точка Б, че просто ще бъде малко 1 и след това да стигнем до бихме има 01 и след това C като 00. Така че тук ние виждаме, че в общи линии ние представляваме тези символа или с един или два бита където B, като прогнозира, има най-малко. И тогава бяхме очаква да има най-много, но тъй като тя е толкова малка дърво Хъфман, А също е представена от два бита, за разлика от някъде по средата. 

Само да премине друг прост пример на дървото на Хъфман, кажем, че имате низ "Hello". Това, което трябва да направите, е първата бихте казали колко пъти H се появяват в този? H се появява веднъж и след това д се появява веднъж и след това имаме появява два пъти и о появява веднъж. И така, тогава ние очакваме коя буква да бъдат представлявани от най-малко броя на битовете? [Ученик] л. >> Л. Да. л е прав. Очакваме да бъдат представлявани от най-малко броя на битовете защото л се използва най-много в низа "Hello". Какво съм аз ще да направя сега е да се изведат тези възли. Имам 1, който е H, а след това още 1, която е електронна, а след това и едно, което е о - точно сега аз съм пускането им в ред - и след това 2, който е л. После казват, че начина, по който гради дърво Хъфман е да намерите два възли с най-малко честоти и да ги направят братя и сестри чрез създаване на майка възел. Тук имаме три възли с най-ниска честота. Всички те са 1. Така че тук ние избираме кой отива да се свържат първо. Да кажем, че изберете H и електронна. Сумата от 1 + 1 е 2, но този възел не разполага с писмо, свързани с нея. Той просто притежава стойност. Сега търсим в следващите две най-ниските честоти. Това е 2 и 1. Това може да е една от тези две, но аз отивам да се избере този,. Сумата е три. И накрая, аз само два ляво, така че това става 5. Тогава, както се очаква, ако попълнете кодиране за това, 1s винаги клон и 0 лявата. Тогава имаме представени само с 1 малко и после о от 2 и след това д от 2 и след това H пада до 3 бита. Така че може да предава това съобщение "Hello", вместо на реално използване на героите само с 0s и 1s. Все пак, не забравяйте, че в няколко случая имахме връзки с нашата честота. Би могъл да се присъедини към H и о първо може би. Или може би по-късно, когато имахме л, представлявано от 2 както и се присъедини, представлявано от 2, бихме могли да са свързани нито една. 

И така, когато ви изпрати 0s и 1s, че всъщност не е гаранция че получателят може напълно да прочетат вашето съобщение правото на разстояние бухалката , тъй като те може да не знаят кое решение сте направили. Така че, когато си имаме работа с компресия Хъфман, някак си трябва да каже на получателя на посланието ни, как решихме - Те трябва да знаят някаква допълнителна информация в допълнение към съобщението сгъстен. Те трябва да разберат, какво дърво изглежда, как ние всъщност тези решения. 

Тук ние просто се прави примери, основаващи се на действително отчетените но понякога може да има дърво Huffman въз основа на честотата, на която буквите се появяват, и това е точно един и същ процес. Тук съм го изразяват по отношение на проценти или фракция, И така, ето точно същото нещо. Две най-ниската, да ги обобщим, следващите 2 най-ниската, да ги обобщим, докато имам пълно дърво. Въпреки че можем да го направим така или иначе, когато си имаме работа с проценти, това означава, че ние сме се раздели нещата и да се занимават с десетични дроби, или по-скоро плува ако мислим за структури от данни на ръководител. Какво знаем за плувки? Какво е често срещан проблем, когато си имаме работа с поплавъци? [Ученик] неточно аритметика. >> Да. Неточности. Поради плаваща запетая неточности, този pset, така че ние сме сигурни, че ние не губят стойности, тогава ние всъщност ще се занимава с преброяването. Така че, ако ви се налага да мисля за Хъфман възел, ако погледнем назад към структурата тук, ако се вгледате в зелените има честота, свързани с нея както и да го насочва към възел от ляво, както и възел правото си. И тогава червените имат характер, свързани с тях. Ние няма да се направят отделни за родителите, а след това и крайните възли, което ние наричаме като листа, а по-скоро тези, които просто ще трябва NULL стойности. За всеки възел ще имаме характер, символ, който представлява този възел, честота, както и показалеца на лявата си дете, както и правото си дете. Листата, които са на самото дъно, също ще възел указатели отляво и тяхното право, но тъй като тези стойности не са насочени към действителните възли, какво ще им стойност? >> Студент NULL. >> NULL. Точно така. Ето един пример за това как може да представлява честотата на салове, но ние ще трябва да се занимават с него с цели числа, така че всичко, което направих е да промените типа данни. 

Нека да отидем на малко повече от сложен пример. Но сега, че сме направили най-простите, това е просто един и същ процес. Ще намерите две ниските честоти, обобщават честоти и това е новата честота на вашия родител възел, , които след това се насочва към левия му с клон 0 и правото с клон 1. Ако имаме низа "Това е cs50," тогава ние брои колко пъти се споменава T, з споменах, аз, S, C, 5, 0. Тогава това, което направих тук е с червени възли Току-що засадени, Казах, че ще се наложи тези герои в крайна сметка в дъното на моето дърво. Тези, които ще бъдат на листата. Тогава това, което направих е, че ги подредени по честота във възходящ ред, и това е всъщност начин, че pset код го прави го сортира по честота и след това по азбучен ред. Така че има номера и след това по азбучен ред на честотата. Тогава какво щях да правя, е, че ще открие две най-ниската. Това е 0 и 5. Аз ще ги обобщим и това е 2. След това ще продължа да намерите следващия 2-ниската. Това са двете 1s, и след това стана 2, както и. Сега знам, че следващата ми стъпка ще се присъедини към най-малък брой, който е T 1, и след това изберете един от възлите, че има две, както и честотата. Така че тук имаме три възможности. Това, което аз ще направя за слайда е просто визуално да ги пренарежда за вас , така че можете да видите как съм го изграждане. Какво кода и разпределение код ще направи ще се присъедини към T с 0 и 5 възела. Значи, че суми до 3, а след това продължи процеса. 2 и 2 сега са най-ниски, така че след тези сума 4. Всеки следващ досега? Добре. След това имаме 3 и 3, които трябва да се добавят, така че отново съм просто я включите, така че можете да видите визуално, така че да не стане твърде разхвърлян. Тогава ние имаме 6, а след това нашата крайна стъпка сега е, че имаме само два възли обобщим тези, на основата на нашето дърво, което е с 10. И числото 10 има смисъл, защото всеки възел представлява, тяхната стойност, честотата им брой, колко пъти те се появяват в низа, и след това имаме пет герои в нашия низ, така че има смисъл. Ако се вгледаме в начина, по който всъщност ще го кодират, както се очаква, аз и S, които се появяват най-често са представени с най-малък брой битове. 

Бъдете внимателни тук. По дърветата Хъфман случай действително има значение. Главна S е различен от малки и. Ако имахме "Това е CS50" с главни букви, а след това и с малки букви ще се появи само два пъти, ще бъде възел с две като стойността му, а след това главни букви S ще бъде само веднъж. Тогава си дърво ще се промени структури, защото тук всъщност трябва допълнително листо. Но сумата все още ще бъде 10. Това е, което ние всъщност ще се обадите на контролна, добавянето на графовете. 

Сега, когато сме обхванати Хъфман дървета, може да се потопите в Puff Huff'n, pset. Ние ще започнем с част от въпроси, и това се случва, за да сте свикнали с двоични дървета и как да работят наоколо, че: рисуване възли, създаването на своя собствена typedef структура за възел, и виждам как може да вмъкнете в двоичен дърво, един, който е сортиран, пресичат, и такива неща. Това знание определено ще ви помогне, когато се потопите в Puff част Huff'n на pset. В стандартното издание на pset, вашата задача е да се приложи Puff, и в хакер версия вашата задача е да се приложи Хъф. Какво Хъф е, че отнема текст и след това тя се превръща в 0s и 1s, така че процес, който ние направихме по-горе, където преброи честоти и след това дървото и после каза: "Как мога да получа T? T е представена от 100, такива неща, и след това Хъф ще отнеме текста и след това продукция, която двоичен. Но също така, защото ние знаем, че искаме да позволим на получателя на съобщението да пресъздаде точно същото дърво, тя включва също информация за честотните е от значение. След това с Пъф са дадени на двоичен файл на 0s и 1s и като се има предвид също така информация за честотите. Ние превеждаме всички тези 0s и 1s обратно в първоначалното съобщение, че е така че ние сме декомпресиране. Ако правиш стандартното издание, не трябва да се прилагат Хъф, така, тогава можете просто да използвате персонала изпълнението на Хъф. Има инструкции в спецификацията за това как да направите това. Можете да стартирате изпълнението на персонала Хъф при определен текстов файл и след това използвайте тази продукция като вход, за да се надуе. 

Както споменах и преди, ние имаме много код на разпределение за това. Отивам да започне да минава през нея. Отивам да прекарват по-голямата част от времето на з файлове защото в файлове в, защото имаме. ч и това ни дава прототипи на функциите, ние не трябва да се разбере точно - Ако вие не разбирате какво се случва в файлове в, тогава не се притеснявайте твърде много, но определено се опита да вземе един поглед, защото тя може да даде някои съвети и е полезно да се използва за четене на код на други хора. 

Търси в huffile.h в коментарите декларира слой на абстракция за Huffman кодирани файлове. Ако слезем, ние виждаме, че има максимум 256 символа, че ние може да се наложи кодове за. Това включва всички букви от азбуката - главни и малки букви - и след това символи и цифри и др. Тогава тук имаме магическо число идентифициране на Хъфман кодиран файл. В рамките на код Хъфман те ще имат определен брой магия свързани с горния. Това може да изглежда като просто случаен номер магия, но ако действително го преведат в ASCII, тогава всъщност са посочени обиждам. Тук имаме една структура за Huffman кодиран файл. Има всички тези характеристики, свързани с даден файл Хъф. Тогава тук имаме горния файл Хъф, така че ние го наричаме Huffeader вместо за добавяне на допълнително ч, защото така или иначе звучи еднакво. Сладко. Ние имаме магическо число, свързани с нея. Ако това е действителния файл Хъф, той ще бъде броя на страните-горе, тази магия. И тогава ще има масив. Така че за всеки символ, който има 256, към списъка честотата на тези символи са в рамките на файла Хъф. И накрая, имаме контролна за честотите, която трябва да бъде сумата на тези честоти. Така че това, което Huffeader. Тогава ние имаме някои функции, които връщат следващата част във файла Хъф , както пише малко, за да Хъф файла, и след това тази функция тук, hfclose, че всъщност затваря файла Хъф. Преди това, ние се занимавахме с права само неуспешно, но когато имате файл Хъф, вместо да го fclosing това, което наистина ще направим, е да го hfclose и hfopen. Това са специфични функции на файловете Хъф, че отиваме да се занимава с. Тогава тук четем в заглавието и след това напишете заглавието. 

Само с четене. З файл да се получи усещане от това, което може да бъде файл Хъф, какви характеристики има, без всъщност се случва в huffile.c които, ако ние се гмуркат, ще бъде малко по-сложен. Той има всички на файла I / O, занимаващи се с указатели. Тук виждаме, че когато ние наричаме hfread, например, все още се занимават с fread. Ние не сме да се отървем от тези функции изцяло, но ние сме изпращане на онези, които трябва да се вземат грижи за във файла Хъф, вместо да правим всичко сами. Можете да се чувстват свободни да сканирате чрез това, ако сте любопитни и си отиват и кори слой малко назад. 

Следващия файл, че отиваме да разгледаме tree.h. Преди в Walkthrough пързалки сме казали, че очакват Хъфман възел и ние направихме typedef възел структура. Очакваме тя да има символ, честота, а след това две звезди възли. В този случай това, което правим, е това е по същество същата с изключение вместо възел отиваме да ги наричат ​​дървета. Ние имаме функция, която, когато ти се обадя дърво ви връща показалеца дърво. Обратно към правопис, когато сте били прави нов възел ти каза възел * нова дума = изчистване (sizeof) и такива неща. По принцип, mktree ще се занимава с това за вас. По същия начин, когато искате да премахнете дърво, така че по същество освобождаването на дървото, когато сте готови с нея, вместо изрично призовава безплатно, вие всъщност ще използвате функцията rmtree премине в показалеца на това дърво и след това tree.c ще се погрижа за това за вас. 

Ние търсим в tree.c. Очакваме същите функции освен да видите прилагане, както и. Както очаквахме, когато ти се обадя mktree mallocs размера на едно дърво в показалеца инициализира всички стойности на нулева стойност, така че 0s или спадове, и връща указател към това дърво, че току-що сте malloc'd да ви. Когато ти се обадя премахване на дърво за първи път прави сигурни, че не сте двойно освобождаване. Това прави сте сигурни, че всъщност имат едно дърво, което искате да премахнете. Тук, защото дървото включва също и неговите деца, какво прави това е рекурсивно призовава за премахване на дърво в ляво възел на дървото както и правото възел. Преди да освободи майка, тя трябва да освободи деца, както и. Майка взаимозаменяеми с корен. Първата по рода си родител, така че като пра-пра-пра-пра-дядо или баба дърво, първо трябва да се освободи нивата първото. Така преминават към дъното, безплатен тези, и след това се върна, безплатен тези и др. Така че това е дърво. 

Сега търсим в гората. Forest където можете да поставите на вашите дървета Хъфман. Той казва, че отива да има нещо, наречено заговор , която съдържа указател към едно дърво, както и показалеца на заговор, наречен следващия. Какво структура този вид прилича? Вид се казва там. Точно тук. Свързан списък. Виждаме, че когато имаме даден имот е като свързан списък на парцели. Една гора се определя като свързан списък на парцели, и така структурата на горите е, че ние просто ще трябва указател към първия ни парцел и този участък има дърво в нея, или по-скоро сочи към едно дърво и след това се насочва към съседния парцел, така нататък и така нататък. За да направите гората ние наричаме mkforest. Тогава ние имаме някои доста полезни функции. Имаме вземете премине в гората и след това връщаната стойност е дърво *, указател за едно дърво. Какво мотика ще направи, е, че ще отиде в гората, че сте сочи към след това извадете дърво с най-ниска честота от тази гора и след това да ви даде показалеца на това дърво. След като ти се обадя мотика, дървото няма да съществува повече в гората, но връщаната стойност е показалеца на това дърво. След това имате растение. В случай, че премине в указател към едно дърво, което има 0 честота, какво растение ще направи това ще отнеме гората, дървото и растителни, че дърво вътрешността на гората. Тук имаме rmforest. Подобно премахване на дърво, които основно се освободи всички от нашите дървета за нас, премахване на гората ще освободи всичко, съдържаща се в тази гора. 

Ако погледнем в forest.c, ние ще очакваме да видим поне един rmtree команда там, защото за да освободите памет в гората, ако гората има дървета в нея, след това в крайна сметка вие ще трябва да премахнете тези дървета. Ако погледнем в forest.c, ние имаме mkforest, което е както очакваме. Ние изчистване неща. Инициализира първия парцел в гората, NULL, тъй като тя е празна, да започнем с това, после виждаме мотика, която връща дървото с най-ниско тегло, най-ниската честота, и след това се отървава от тази конкретна възел, който сочи към това дърво, а следващата, така че, че на свързан списък на гората. А пък тук имаме растение, което вмъква дърво в свързан списък. Какво гора е добре го поддържа подредени за нас. И накрая, имаме rmforest и, както се очаква, ние имаме rmtree нарича там. 

Търсите разпределението код досега, huffile.c е може би най-трудната за разбиране, докато другите файлове са били сами по себе си доста просто да се следват. С нашите познания на указатели и свързани списъци и такива, ние бяхме в състояние да следват доста добре. Но всичко, което трябва наистина да сме сигурни, че напълно разбират е з файлове защото трябва да се обади на тези функции, занимаващи се с тези за връщане стойности, така че се уверете, че напълно разбирате какви действия ще се извършват всеки път, когато ти се обадя един от тези функции. Но всъщност разбиране вътре в него не е необходимо, тъй като имаме тези ч файлове. Имаме две повече файлове, останали в нашата дистрибуторска код. 

Нека да погледнем в сметището. Изсипване от неговия коментар тук се Хъфман компресиран файл и след това превежда и сметища всички на неговото съдържание,. Тук виждаме, че се обажда hfopen. Това е вид отражение файл * = fopen вход, и след това преминават в информацията. Това е почти идентични, с изключение вместо на файл *, който преминава в Huffile; вместо fopen сте преминаване в hfopen. Тук четем в заглавието първият, който е нещо подобно как четем в заглавието за растерна графика файл. Това, което правим тук, е проверка да се види дали информацията в заглавието съдържа правилния брой магия, която показва, че това е действителния файл Хъф, тогава всички тези проверки, за да се уверите, че файла, който открито е действително вдишвали файл или не. Това, което прави е да подава на честотите на всички символи, които можем да видим в рамките на терминала в графична таблица. Тази част ще бъде полезен. Той е малко и чете малко по малко в променливата малко и след това го отпечатва. Така че, ако се обадиш изсере на hth.bin, което е резултат от huffing файл използването на служители решение, щях да се получи това. Това е извеждане на всички тези символи и след това пускането честотата, с която те се появяват. Ако погледнем, повечето от тях са 0s с изключение на това: H, който се появява два пъти, и след това T, който се появява веднъж. А пък тук имаме действителната съобщение 0s и 1s. Ако се вгледаме в hth.txt, която вероятно първоначалното съобщение, че е вдишвали ние очакваме да видим някои Hs и Ц. там. Конкретно, ние очакваме да видим само на 1 T и 2 ХС. Тук сме в hth.txt. Тя наистина има HTH. В там, макар и да не могат да го видят, е символ за нов ред. Файл Хъф hth.bin кодиране на символ за нов ред, както добре. Тук, защото ние знаем, че поръчката е HTH и след това нов ред, можем да видим, че вероятно H е представена само от един милиард и след това T вероятно е 01 и след това на следващия Н е 1, както и и тогава ще имаме нов ред, посочен от две 0s. Cool. 

И накрая, защото си имаме работа с множествена в з файлове, ние ще трябва доста сложна аргумент на компилатора, и така тук имаме Makefile, което прави сметище за вас. Но всъщност, вие трябва да отида за да създавате свои собствени puff.c файл. Makefile всъщност не се занимава с като puff.c за вас. Тръгваме си, че можете да редактирате Makefile. Когато въведете команда като направи всичко, например, той ще направи всичко от тях за вас. Чувствайте се свободни да погледнете примерите на Makefile от миналото pset , както и на това да се види как може да сте в състояние да направите вашия файл Puff редактирането на този Makefile. Това е за него за дистрибуторската ни код. 

След като сме придобили през това, след това тук е просто още едно напомняне за това как ние ще се занимава с възли Хъфман. Ние не започваш да се наричайки ги възли вече отиваме да им се обадите дървета къде отиваме да им символ с Чар, честотата им, броя на случаите, с цяло число. Ние използваме това, защото това е по-точен, отколкото с плаваща запетая. И тогава ние имаме друг показалеца на лявата детето, както и право дете. Гора, както видяхме, е само свързан списък на дърветата. Крайна сметка, когато ние строим нашата Хъф файл, искаме гората, да съдържат само 1 дърво - 1 дърво, 1 корен с няколко деца. По-рано, когато бяхме просто Хъфман дървета, ние започнахме чрез поставяне на всички възли на нашия екран и казваш, че ще има тези възли, в крайна сметка те ще бъдат листата, и това е техният символ, това е тяхната честота. В нашата гора, ако ние просто има три букви, това е гора от три дървета. И тогава, както и да отидем, когато сме добавили първия родител, ние направихме гората на две дървета. Премахнати две от тези деца от нашата гора и след това го заменя с един родител възел , които са имали тези две възли като деца. И накрая, последната стъпка с нашия пример с, BS и Cs ще бъде да направи окончателния родител, и така това ще доведе до общ брой на дърветата в гората 1. Всеки да види как да започнете с множество дървета в гората си и се свърши с една? Добре. Cool. 

Какво ни е нужно да се направи за Puff? Това, което ние трябва да направим, е да се гарантира, че, както винаги, те ни дават правото вид на входа така че ние действително можем да стартирате програмата. В този случай те ще трябва да се ни дава след първата им командния ред аргумент 2: файла, който искаме да се натиска и на изхода на декомпресира файл. Но след като ние сме сигурни, че те ни преминават в точното количество на ценностите, искаме да сме сигурни, че входът е файл Хъф или не. А след това веднъж ние гарантираме, че това е файл Хъф, а след това искаме да изградим нашето дърво, изгради такава, че да съответства на дърво, че лицето, което изпраща съобщението, построен на дървото. Тогава, след като строим дървото, тогава ние може да се справи с 0s и 1s, че премина в следват тези по нашето дърво, защото е идентичен, и след това напишете това съобщение, тълкуване на бита в символа. И след това в края, защото ние си имаме работа с указатели, ние искаме да направим сме сигурни, че не разполагат с никакви изтичане на памет и че сме всичко. 

Осигуряване на правилно използване е стара шапка за нас от сега. Ние приемаме в един вход, който ще бъде името на файла да се надуе, и след това ние определяме изход, така че името на файла за бухнали изход, който ще бъде текстов файл. Това е използване. И сега искаме да сме сигурни, че входът е вдишвали или не. Мисли, имаше нещо в кода на дистрибуция, която може да ни помогне с разбирането дали даден файл е вдишвали или не? Имаше информация в huffile.c за Huffeader. Ние знаем, че всеки файл Хъф има Huffeader, свързани с нея с магическо число , както и набор от честоти за всеки символ както и контролна. Ние знаем това, но ние също така взе един поглед на dump.c, в който е бил четене във файл Хъф. И така, за да направи това, той трябваше да се провери дали наистина е вдишвали или не. Така че може би бихме могли да използвате dump.c като структура за нашия puff.c. Обратно към pset 4, когато имахме файла резервното, която да копира в тройки RGB и ние тълкува, че за криминале и Resize по същия начин, какво можеш да направиш, е просто да изпълните командата като CP dump.c puff.c и да използвате някои на кода там. Въпреки това, той няма да бъде толкова лесно на един процес за превода dump.c в puff.c, но поне ви дава някъде да се започне за това как да се гарантира, че входът е всъщност вдишвали или не , както и няколко други неща. Гарантира правилното използване и гарантира, че входът е вдишвали. Всеки път, когато сме направили, че сме си свършили правилно при проверка на грешка, така че връщането и отказване на функцията, ако се появи някаква повреда, ако има проблем. 

Сега това, което искаме да направим, е да се изгради действителното дърво. Ако погледнем в гората, има две основни функции че отиваме да искат да станат много добре запознати с. Има Булева функция растение, че растенията 0 честота дърво вътре в нашата гора. И така, има ли преминават в показалеца до гора и показалеца на едно дърво. Бърз въпрос: Колко гори ще имате, когато сте изграждането на дърво Хъфман? Нашата гора е като нашето платно, нали? Така че ние сме само ще има една гора, но отиваме да имат множество дървета. Така че, преди да се обадите растение, вие вероятно ще искате да направите вашия гора. Има команда за това, ако погледнете в forest.h за това как можете да направите гората. Можете да посадиш дърво. Ние знаем как да го направя. И тогава можете да вземете едно дърво от гората, отстраняване на дървото с най-ниско тегло и ви дава показалеца за това. Мисля, когато правехме примери себе си, когато бяхме съставянето, ние просто добавят линкове. Но тук, вместо просто да се добавят връзки, мисля за него, както сте премахване на два от тези възли и след това да го заменя с друг. Да изрази, че по отношение на бране и посадъчен сте бране две дървета и засаждане на друго дърво , който има тези две дървета, които сте избрали като деца. Да се ​​изгради дърво Хъфман, можете да прочетете в символи и честоти, за защото Huffeader дава, че за вас, ви дава масив на честотите. Така че можете да отидете напред и просто да игнорираш всичко с 0 защото ние не искаме 256 листа в края на това. Искаме само броя на листата, които са герои , които действително се използват във файла. Можете да прочетете в тези символи, и всеки от тези символи, които имат 0 честоти, тези, които ще бъдат дървета. Какво можете да направите, е всеки път, когато прочетох в 0 честота символ, можете да засадите това дърво в гората. След като засадят дървета в гората, може да се присъединят към тези дървета като братя и сестри, така че връщане назад към засаждане и бране, където да изберете две и след това растение 1, 1, че растението е майка на две деца, които сте избрали. Тогава крайният резултат ще бъде едно дърво в гората си. Ето как да изградите вашето дърво. 

Има няколко неща, които биха могли да възникнат тук защото ние сме се занимават с правенето на нови дървета и се занимават с указатели и подобни неща. Преди, когато си имаме работа с указатели, когато ние malloc'd искахме да сме сигурни, че това не ни върне NULL стойност показалеца. Така че в няколко стъпки в този процес ще бъдат няколко случая , където вашата програма може да се провали. Какво искате да направите, е да искате да се уверите, че да се справят с тези грешки, и в спец. казва, че трябва да се справиш с тях грациозно, така като печат съобщение на потребителя да им кажете защо програмата трябва да се откажат и скоро след това да се откажат от него. За да направите това отстраняване на грешките, помнете, че вие ​​искате да го проверите всеки един момент, че може да има провал. Всеки път, че сте прави нова показалеца искате да се уверите, че това е успешен. Преди това, което сме свикнали да направите, е да се направи нов показалеца и изчистване го, и тогава ще проверите дали това показалецът е NULL. Така че там ще бъдат някои случаи, където можете просто да направите това, но понякога сте извикването на функция и в рамките на тази функция, това е този, който прави mallocing. В този случай, ако погледнем назад към някои от функциите в кода, някои от тях са булеви функции. В абстрактния случай, ако имаме булева функция, наречена Foo, основно, можем да предположим, че в допълнение към правиш каквото Foo прави, , тъй като това е булева функция, той се връща истина или лъжа - вярно, ако успешно, невярно, ако не. Така че ние искаме да се провери дали връщането стойност на Foo е вярно или невярно. Ако това е невярно, това означава, че ние ще искате да отпечатате някакъв вид послание и след това спиране на програмата. Това, което искаме да направим, е да проверите на връщаната стойност от Foo. Ако Foo връща, тогава ние знаем, че сме срещнали някаква грешка и ние трябва да се откажат от нашата програма. Един от начините да направите това е състояние, при което самата функция е състоянието ви. Кажи Foo отвежда в х. Ние можем да имаме като условие, ако (Foo (х)). По принцип, това означава, че ако в края на изпълнението на Foo връща вярно, тогава можем да направим това, защото тази функция трябва да прецени Foo за да се оцени цялата състояние. Тогава как можете да направите нещо, ако функцията връща вярно и успешно. Но когато сте проверка за грешки, само искам да се откажат, ако си функция връща. Какво можете да направите, е просто добавете == невярна или просто добавете гръм и трясък в пред него и тогава ще трябва ако (! Foo). В този орган на това условие ще имате на механизъм за обработка на грешки, И тъй като "не може да се създаде това дърво" и след това се върнете един или нещо подобно. Това, обаче, е, че въпреки че Foo върнати фалшиви - Кажи Foo връща вярно. Тогава не трябва да се обадя на Foo отново. Това е често срещано погрешно схващане. Защото това беше в състоянието си, вече са били оценени, така че вече има резултат, ако използвате дърво или нещо подобно или растение или мотика или нещо такова. Тя вече има тази стойност. Той вече е изпълнена. Така че това е полезно да се използват булеви функции като условие защото дали сте или не сте действително изпълнение на тялото на цикъла, той изпълнява функцията, така или иначе. 

Вторият ни към последната стъпка е писмено съобщение до файла. След строим дървото на Хъфман, след това писмено съобщение до файла е доста ясен. Това е доста ясен сега просто следвайте 0s и 1s. И така, по силата на споразумение, ние знаем, че в дърво Хъфман 0s показват оставяли и 1s показват прав. Значи, ако прочетете малко по малко, всеки път, когато получи 0 ще следват левия клон, а след това всеки път, когато прочетох в един ти започваш да следва право клон. И тогава започваш да продължи, докато не удари едно листо защото листата ще бъде в края на клоните. Как можем да кажем дали сме хит листо или не? Ние го казах и преди. [Ученик] Ако указатели са NULL. >> Да. Можем да кажем, ако сме хит листо, ако указатели към левия и десния дървета са NULL. Perfect. Ние знаем, че искате да прочетете малко по малко в нашия файл Хъф. Както видяхме преди в dump.c, какво са направили, е, че те четат малко по малко във файла Хъф и току-що отпечатани, какви са тези битове. Ние няма да се правиш, че. Отиваме да се прави нещо, което е малко по-сложен. Но това, което можем да направим е да можем да вземем тази част на кода, който се гласи за малко. Тук имаме цяло число малко, представляващ текущата малко, че сме на. Това се грижи итерации всички битове във файла, докато не удари края на файла. Въз основа на това, тогава вие ще искате да има някакъв вид на итератор да преминават през вашата дърво. И тогава се основава дали бит е 0 или 1, , вие ще искате да се движат, че итератор на ляво или да го преместите надясно по целия път, докато не удари едно листо, така че по целия път до този възел, че сте на не се посочват повече възли. Защо можем да направим това с файл Хъфман, но не морзовата азбука? Защото в Морзовата азбука има малко неяснота. Ние можем да бъдем като О, чакайте, ние сме ударени писмо по протежение на пътя, така че може би това е нашето писмо, като има предвид, че ако продължи малко по-дълго, тогава ние ще са хит друго писмо. Но това няма да се случи в Huffman кодиране, така че ние може да бъдете сигурни, че единственият начин, че отиваме да удари характер е, ако този възел левия и десния децата са NULL. 

И накрая, ние искаме да освободи всички на нашата памет. Искаме до края на файла Хъф, че ние сме били занимаващи се с както и да премахне всички дървета в гората,. Въз основа на изпълнението си, че вероятно ще искате да се обадите премахване на гората вместо всъщност се случва всичко от себе си дървета. Но ако сте направили всички временни дървета, вие ще искате да освободите. Вие най-добре знаете кода си, за да знаете къде сте разпределяне на памет. И така, ако вие отидете в, започнете, като дори и да е контрол, F'ing за изчистване, виждам, когато изчистване и като се уверите, че ви освободи всичко това но след това просто става чрез кода си, разбирането, където може да сте заделената памет. Обикновено може да се каже, "В края на файла аз съм просто ще да премахнете гора на моя горо" Така че основно ясно, че памет, безплатен, че "И тогава аз също съм за да затворите файла и след това програмата ми се ще да се откажа." Но е, че единственият път, че вашата програма напусна? Не, защото понякога може да е грешка, което се случи. Може би ние не може да отвори файл или ние не може да направи друго дърво или някаква грешка не е станало в процеса на разпределение на паметта и така я връща NULL. Възникна грешка и след това ще се върна и да се откажат. Значи искате да се уверите, че всеки възможен път, че вашата програма може да се откаже, искате да освободите от паметта ви. Това не е просто ще бъде в самия край на основната функция, която напусна своя код. Искаш ли да погледнем назад към всеки случай, че кодът потенциално може да се върне преждевременно и след това без каквото и памет има смисъл. Да кажем, че бе нарекъл гората и да се върнат невярна. Тогава най-вероятно няма да се наложи да премахнете гора защото не е нужно гора все още. Но във всеки един момент в кодекса, където може да се върне преждевременно искате да се уверите, че ви освободи всички възможни памет. 

Така че, когато си имаме работа с освобождаването на паметта и като потенциални течове, ние искаме да не се използват само нашата преценка и нашата логика но също така да използвате Valgrind, за да се определи дали сме освободени всички ни памет правилно или не. Можете да тече Valgrind на Пъф и тогава ще трябва да го давате точния брой аргументи от командния ред, за да Valgrind. Можете да изпълнявате това, но изходът е малко загадъчно. Сме придобили малко с правопис, но ние все още се нуждаят от малко повече помощ, така че след това с още няколко знамена като течове проверка = пълно, , които вероятно ще ни даде някои по-полезна за извеждане на Valgrind. 

Тогава друг полезен съвет, когато сте дебъгване е командата разл. Можете да получите достъп до прилагането на персонала на Хъф, бягай, че на текстов файл, и след това го подаде на двоичен файл, двоичен файл Хъф, да бъдат конкретни. Тогава, ако стартирате свой собствен бутер че двоичен файл В идеалния случай, вашият изведен текстов файл ще бъде идентичен на оригинала, че сте издържали инча Тук аз съм с hth.txt като пример, и това е единственото, говорихме си спец.. Това е буквално HTH и след това нов ред. Но определено се чувствам свободен и определено са насърчавани да използват дълги примери за текстов файл. 

Можете дори да изстрел може би компресиране и след това декомпресиране някои от файловете, които сте използвали в Speller като Война и мир или Джейн Остин или нещо подобно - това ще бъде нещо готино или Остин Пауърс, вид, занимаващи се с по-големи файлове, защото ние няма да слезе да го ако използват следващия инструмент, LS-л. Свикнали сме да ли, които основно се изброява цялото съдържание в сегашния ни директория. Минавайки в знаме-л всъщност показва размера на тези файлове. Ако отидете чрез спец. pset, всъщност ви води чрез създаването на двоичен файл, huffing тя, и ще видите, че за много малки файлове пространството разходите за компресиране и превод на всички на тази информация на всички честоти и такива неща надвишава действителната полза на компресира файла на първо място. Но ако го изпълните на някои по-дълги текстови файлове, тогава може да се види, че започват да се получи някаква полза за компресиране на файлове. 

И накрая, ние разполагаме със стария GDB приятел, който определено ще дойде по-удобно. 

Да може би имаме някакви въпроси по дърветата обиждам или процеса на дърветата или някакви други въпроси на Пъф Huff'n? Добре. Ще остана наоколо за малко. 

Благодаря на всички. Това е репетиция 6. И късмет. 

[CS50.TV]