[Powered by Google Translate] [Gözden geçirmek - Problem Set 6] [Zamyla Chan - Harvard Universiteti] [Bu CS50 edir. - CS50.TV] 

Salam, hər kəs və gözden geçirmek 6 xoş gəlmisiniz: Huff'n Puff. Huff'n Puff biz nə bir Huffman sıkıştırılmış fayl ilə məşğul olacaq və sonra geri o şişirme belə decompressing biz 0s və 1s istifadəçi bizə göndərir ki, tərcümə edə bilərsiniz, belə ki, və orijinal mətn daxil geri çevirmək. Siz tools bəzi görmək olacaq çünki Pset 6 olduqca sərin olacaq siz 1 olduqca səliqəli anlayışı onları birləşdirən pset 4 və pset 5 və cür istifadə Bu barədə düşünmək gələndə. 

Həmçinin, arguably, pset 4 və 5 təklif etdi ki, ən çətin psets idi. Beləliklə, biz, C, bu 1 daha pset var və sonra sonra biz web proqramlaşdırma üçün edirik. Belə ki, CS50 də çətin donqar üzərində almaq üçün özünüzü təbrik edirəm. 

Huff'n Puff üçün hərəkət, bu pset üçün Toolbox, Huffman ağacları olacaq belə binar ağac iş, həm də xüsusi Huffman ağacı yalnız necə başa necə inşa edirik. Və sonra biz bu pset paylanması kodu bir çox olacaq və biz kodu bəzi həqiqətən görmək gəlmək lazımdır biz hələ tam dərk edə bilər və həmin onların müşayiət. h faylları. c faylları, lakin edəcək Bizi biz bu funksiyaları necə bilirik ki, lazımdır ki, kifayət qədər anlayış verəcək və ya ən azı nə onlar ehtimal olunur - onların giriş və çıxış - biz qara qutusuna nə bilmirəm, hətta ərzində və ya qara qutu nə baş başa düşmürəm. Və sonra nəhayət, adi kimi, biz yeni data strukturları ilə məşğul olan ki qovşaqlarının xüsusi növləri müəyyən şeylər qeyd və belə ki, burada dizayn prosesi üçün təkcə qələm və kağız olan və zaman pset iş necə anlamaq çalışdığınız həm də ayıklama zamanı. Siz dəyərlər nə yazmaq isə Siz qələm və kağız yanaşı gdb ola bilər harada oxlar işarə edərək, və elə şeylər edir. 

Birinci Huffman ağacları baxaq. Huffman ağac hər node yalnız 2 övladı var, yəni, ikili ağacları daxildir. Huffman ağacları xarakterik olan ən tez-tez dəyərlər ən az bit ilə təmsil olunur. Biz Morse kodu mühazirə nümunələri icmal hansı cür bir məktub gördü. Məsələn, A və ya E, tərcümə çalışdığınız Əgər Əgər tez-tez tərcümə edirik, belə əvəzinə bit tam set istifadə edərək ki, adi data növü üçün ayrılmış, siz daha az üçün aşağı kompres və sonra təmsil edən məktublar az tez-tez artıq bit ilə təmsil olunur bu məktublar görünür ki, tezliklərin həyata çəkin zaman ki, ödəyə bilər. Biz Huffman ağacları burada eyni fikir biz bir zəncir, müəyyən simvol almaq üçün yol bir növ edir. Və sonra ən tezliyi olan simvol ən az bit ilə təmsil olunur. 

Bir Huffman ağac tikmək yolu mətn görünür ki, simvol bütün yerləşdirilməsi ilə və onların tezliyi hesablanması, necə tez-tez görünür. Bu, ya o məktublar görünür neçə dəfə bir sayı ola bilər və ya bəlkə hər bir əmələ nə qədər bütün simvol həyata faizi. Və nə siz, bir dəfə ki, eşlenen həyata bütün var sonra 2 aşağı tezliklərin axtarmaq və sonra bacı kimi onlara qoşulmaq daha sonra ana node onun 2 övladı məbləğin olan tezlik var. Və sonra siz Konvensiya tərəfindən demək ki sol node, Siz 0 filial aşağıdakı tabe və sonra rightmost node 1 qoludur. Biz Morse kodu gördüm kimi, bir gotcha idi ki, yalnız bir beep və beep olsaydı bu birmənalı idi. Bu da 1 məktub ola bilər və ya 2 məktubları bir sequence ola bilər. Və nə Huffman ağac yoxdur ki, simvol təbiəti çünki və ya bizim son faktiki simvol şöbəsində son qovşaqlarının olan - biz yarpaqları həmin baxın - ki, əsasən hər hansı bir qeyri ola bilməz siz bit seriyası ilə kodlar çalışdığınız olan məktub baxımından çünki 1 məktub təmsil edən bit boyunca heç bir yerdə Başqa bir bütöv məktub qarşılaşacaq və hər hansı bir qarışıqlıq olmayacaq. Amma siz uşaqlar həqiqətən görürük ki nümunələri daxil lazımdır ki, əvəzinə bizə yalnız doğru belirten. 

Üzrə Huffman ağac sadə bir misal baxaq. Mən 12 simvol uzunluğunda ki, burada bir simli var. Mən 6 pansiyonlar, 2 Cs kimi 4 var. Mənim ilk addım saymaq olardı. A neçə dəfə görünür? Bu simli 4 dəfə görünür. B 6 dəfə görünür, və C 2 dəfə görünür. Təbii ki, mən ən çox B kullanıyorum demək gedirəm Mən bit və az sayı 0s və 1s və az sayı ilə B təmsil etmək istəyirəm. Və sonra da C həmçinin 0s və 1s ən məbləğ tələb gözləmək gedirəm. Birinci mən burada nə mən tezliyi baxımından üçün artan onlara yerləşdirilir. Biz C və A, bu bizim 2 aşağı tezliklərin ki, görürük. Biz bir valideyn node yaratmaq və valideyn node Bugün məktub yoxdur lakin bu məbləğ bir tezlik, yoxdur. Cəmi 6 olan 2 + 4 olur. Sonra sol qolu edin. Biz 6 node idi, onda biz C almaq üçün 0 edin ki, və sonra 1 A. almaq Belə ki, indi biz 2 qovşaqlarının var. Biz dəyəri 6 və sonra da dəyəri 6 başqa bir node var. Və həmin 2 ən aşağı 2, həm də sol yalnız 2 deyil, yalnız biz cəmi 12 olmaqla, başqa valideyn həmin buyurun. Belə ki, burada biz Huffman ağac var B almaq üçün harada, yalnız az 1 olacaq və sonra A almaq üçün biz C 00 olan sonra 01 və olacaq. Belə ki, burada biz əsasən biz 1 və ya 2 bit ya bu chars təmsil etdiyiniz bax Ü kimi proqnozlaşdırılmış B,, az var. Və sonra, biz C ən olması gözlənilir, lakin belə bir kiçik Huffman ağac olduğundan sonra bir də ortasında yerə qarşı 2 bit təmsil olunur. 

Yalnız Huffman ağac bir sadə misal üzərində getmək üçün Siz simli var demək "Hello". Nə siz neçə dəfə H bu görünür deyərdim ilk? H dəfə və sonra e görünür görünür bir dəfə və daha sonra iki dəfə görünen l var və o bir dəfə görünmesi. Və sonra biz bit ən az təmsil edən məktubu gözləyirik? [Tələbə] l. >> L. Bəli. l hüququdur. Biz l bit ən az təmsil gözləyirik çünki l "Hello". simli ən istifadə olunur Mən indi gedirəm nə bu qovşaqlarının çıxartmaq olunur. Mən o olan e olan digər 1, sonra 1, H olan, 1 var, - l olan, sonra 2 - İndi onları qoyulması alıram. Sonra mən Huffman ağac qurmaq yolu ən tezliklərin ilə 2 qovşaqlarının tapmaq demək və valideyn node yaratmaqla onları bacı edir. Burada ən aşağı tezlikli 3 qovşaqlarının var. Onlar 1 istəyirik. Belə ki, burada biz ilk keçid olacaq bir seçin. Gəlin mən H və E seçmək deyirlər. 1 məbləği + 1 2 deyil, bu node Bugün məktub mövcut deyil. Bu, yalnız dəyəri vardır. İndi biz növbəti 2 aşağı tezliklərin oldu. Ki, 2 və 1 var. Bu da o 2 ola bilər, amma bu bir seçmək üçün gedirəm. Cəmi 3. Və sonra nəhayət, mən yalnız sonra 5 olur ki, 2 sol var. Mən bunun üçün kodlama doldurmaq Əgər burada kimi gözlənilir 1s həmişə düzgün filialı və 0s sol bir olunur. Sonra 2-yalnız 1 bit və sonra o təmsil l var və sonra 2-e, sonra H 3 bit aşağı düşür. Belə ki, "Hello" Bu mesaj ötürmək bilər əvəzinə faktiki Sandıqı istifadə edərək, yalnız 0s və 1s tərəfindən. Lakin, bir neçə hallarda biz tezliyi ilə əlaqələri olduğunu unutmayın. Biz ya bəlkə ilk H və o qoşulmuşdur bilər. Yoxsa sonra biz 2 təmsil l zaman haqqında həmçinin 2 təmsil bir qoşulub, biz bir bağlı ola bilər. 

Və siz göndərmək zaman 0s və 1s, həqiqətən, zəmanət deyil Alıcı tam hüququ yarasa off oxumaq bilər ki, onlar edən qərar bilmirəm bilər, çünki. Beləliklə, biz Huffman sıxılma ilə məşğul olduğunuz zaman, birtəhər biz qərara necə bizim mesaj alan demək var - Onlar əlavə məlumat bir növ bilmək lazımdır sıxılmış mesaj əlavə. Onlar ağac həqiqətən kimi görünür nə başa düşmək lazımdır biz, həqiqətən, bu qərarlar qəbul necə. 

Burada biz yalnız faktiki sayı əsasında nümunələri edirdilər amma bəzən də bir Huffman ağac ola bilər tezlik əsasında hərfləri görünür, bu eyni proses var olan. Burada, faiz və ya bir qismini baxımından bu ifadə edirəm və belə ki, burada eyni şey. I, 2-aşağı, onları vurmaq, aşağı növbəti 2, onlara yekun tapmaq Mən tam ağac qədər. Biz biz faiz ilə məşğul olduğunuz zaman ya yol, nə ola bilər baxmayaraq, biz şeyi ayırıcı və ondalık ilə məşğul olduğunuz deməkdir və ya daha çox üzüb gedirdi ki, biz bir baş data strukturları düşünərək edirsinizsə. Biz üzüb gedirdi haqqında nə bilirik? Biz üzüb gedirdi ilə məşğul olduğunuz zaman ortaq problem nədir? [Tələbə] qeyri-dəqiq hesab. >> Bəli. Qeyri-dəqiqlik. Çünki üzən qeyri-dəqiqlik, bu pset biz əmin olun ki, biz heç bir dəyərləri itirmək deyil ki, biz, həqiqətən, sayı ilə məşğul olmaq üçün olacaq. Siz burada quruluşuna geri baxmaq əgər, bir Huffman node hesab idi əgər siz yaşıl isə baxmaq əgər Bugün tezlik var habelə onun sol bir node habelə hüququ bir node göstərir. Və sonra qırmızı olanlar orada da onlara bağlı bir xarakter daşıyır. Biz valideynlər və sonra yekun qovşaqlarının üçün ayrı-ayrı olanları etmək fikrində deyilik olan biz yarpaqları kimi istinad deyil, o yalnız NULL dəyərlər var. Hər node üçün biz bir xarakter ki, node təmsil simvolu olacaq sonra tezlik habelə onun sol uşaq, eləcə də sağ uşaq bir göstərici. Çox altında olan yarpaq, həmçinin node göstəricilərinə olacaq onların sol və sağ, lakin o dəyərləri faktiki qovşaqlarının işarə deyil, çünki onların dəyəri nə olardı? >> [Tələbə] NULL. >> NULL. Exactly. Burada üzüb gedirdi olan tezlik təmsil bilər necə bir misal var amma biz integers ilə məşğul olmaq üçün olacaq belə etdim bütün orada data type dəyişdirmək deyil. 

Üzrə kompleks Məsələn bir az daha davam edək. Amma indi biz sadə olanları etdik ki, yalnız eyni proses var. Siz 2 aşağı tezliklərin tapmaq tezliklərin yekun və ki, sizin ana node yeni tezlik var daha sonra 1-filialı ilə 0 filialı və sağ ilə sol göstərir. Biz string "Bu cs50 ki," var, onda biz, T qeyd neçə dəfə saymaq h qeyd i, s, c, 5, 0. Sonra nə mən burada idi, mən yalnız əkilmiş qırmızı qovşaqlarının ilə Mən ağac altında nəticədə bu simvol var gedirəm deyib. Bu yarpaqları bütün olacaq. Sonra nə etdim, mən sifariş artan tezlik onlara sıralanır edir və bu əslində pset kodu yoxdur ki, yolu bu tezlik ilə növ bu və sonra əlifba sırası edir. Belə ki, tezlik ilə əlifba sırası ilə ilk və sonra nömrələri var. Sonra nə edəcəyini mən 2 aşağı tapmaq edir. Bu 0 və 5 var. Mən onları yekunlaşdırmaq olardı ki, 2 deyil. Sonra növbəti 2 aşağı tapmaq, davam edir. Bu iki 1s və həmin həmçinin 2 çevrilmişdir. İndi növbəti addım, ən aşağı sayı qoşulması olacaq bilirik ki, olan, 1-T, sonra tezlik 2 ki qovşaqlarının birini seçmək. Belə ki, burada biz 3 variantları var. Mən slayd üçün nə etmək gidiyorum nə yalnız vizual sizin üçün yeniden edir belə ki, mən bu qədər tikinti oldum necə görə bilərsiniz. Kodu və bölüşdürülməsi kodu edəcəyimiz nə T bir qoşulmaq olar 0 və 5 node ilə. Belə ki, daha sonra 3 məbləğləri və biz prosesi davam edir. 2 və 2 indi sonra, 4 bu məbləğ ən aşağı edir. Hər kəs bu günə qədər sonra? Okay. Sonra bundan sonra, 3 və əlavə etmək lazımdır ki, 3 mövcut siz çox messy almaq deyil ki, vizual belə görürük ki, belə daha yalnız keçid alıram. Biz yalnız 2 qovşaqlarının ki, sonra biz 6, və sonra bizim son addım indi 10 olan ağac kökü etmək o edib. Hər node təmsil çünki sayı 10, hissi verir onların dəyəri, onların tezliyi, sayı, onlar simli çıxdı neçə dəfə və sonra biz simli 5 simvol var, hissi verir ki,. Biz həqiqətən kodlar necə qədər baxsaq, gözlənilən kimi, i və ən tez-tez görünür olan s, bit və az sayda təmsil olunurlar. 

Burada diqqətli olun. Huffman ağacları işin faktiki məsələləri. Bir böyük S kiçik s çox fərqlidir. Biz idi varsa, kiçik s yalnız iki dəfə görünür sonra, kapital hərflərlə "Bu CS50 deyil" onun dəyəri 2 ilə node olacaq, sonra böyük S yalnız bir dəfə olacaq. Həqiqətən burada əlavə yarpaq, çünki Belə ki, sonra ağac strukturları dəyişdirmək olar. Amma məbləğ hələ 10 olardı. Yəni biz əslində checksum zəng etmək olacaq nə bu sayar bütün əlavə. 

İndi Huffman ağacları əhatə etdik ki, biz Huff'n Puff ki, pset daxil dive bilər. Biz, suallar bölməsi ilə başlamaq olacaq və bu ikili ağac və necə ki, ətrafında fəaliyyət ilə vərdiş əldə edir: rəsm qovşaqlarının, bir node üçün öz typedef struct yaradılması, və bir ikili ağac, sorted ki, bir daxil ola bilər necə görən, o ki, kimi şeylər traversing. Bu bilik mütləq Huff'n Puff hissəsi daxil zaman dive sizə kömək edir bu pset edir. Bu pset səviyyəsinin nəşr, sizin vəzifəsi Puff həyata keçirmək və hacker versiyası Task Huff həyata keçirilməsidir. Huff edir nə, bu mətn edir və onda 0s və 1s onu çevirir biz tezliklərin sayılır biz yuxarıda ki prosesi və sonra ağac və sonra dedi: "Mən T alıram?" T 100 ilə təmsil olunur ki, kimi şeylər, və sonra Huff mətn və sonra çıxış edən ikili edəcək. Lakin biz mesaj bizim alan imkan istəyirəm bilirik ki, çünki eyni ağac yeniden, bu da tezliyi sayıları haqqında məlumat daxildir. Sonra Puff biz 0s və 1s bir ikili fayl verilir və həmçinin tezliklərin haqqında məlumat verilir. Biz ki, orijinal mesajı o 0s və 1s geri bütün tərcümə belə ki decompressing edirik. Siz standart nəşr edirik, siz, Huff həyata ehtiyac yoxdur belə sonra yalnız Huff heyəti həyata istifadə edə bilərsiniz. Bunu necə spec ildə təlimat var. Siz müəyyən bir mətn faylı ilə Huff heyəti həyata çalıştırabilirsiniz və sonra yastıq üçün giriş kimi çıxış istifadə edin. 

Mən əvvəl qeyd etdiyim kimi, biz bu bir distribution kodu var. Mən bunu keçir başlamaq üçün gedirəm. Mən də çox vaxt sərf etmək niyyətindədir edirəm. H faylları biz. h var çünki. c faylları, çünki və ki, funksiyaları prototipləri bizi təmin edir tam dəqiq anlamaq üçün ehtiyac yoxdur - Siz. C faylları neler başa düşmürəm, onda çox narahat olmayın bəzi göstərişlər vermək bilər, çünki mütləq bir nəzər cəhd və digər insanların kodu oxu üçün istifadə almaq üçün yararlıdır. 

Huffile.h baxanda şərh bu Huffman kodlu faylları üçün abstraksiya bir qat bəyan edir. Biz aşağı getmək varsa, biz kodları lazımdır ki, 256 simvol maksimum olduğunu görürük. Böyük və kiçik - - Bu əlifba bütün məktubları daxildir və sonra simvol və nömrələri, və s. Sonra burada bir Huffman kodlu fayl müəyyən bir sehrli var. Bir Huffman kodu çərçivəsində onlar müəyyən bir sehrli sıra olacaq mövzu ilə bağlı. Bu, yalnız bir təsadüfi sehrli sayı kimi ola bilər həqiqətən ASCII onu tərcümə olsa, o, həqiqətən HUFF həyata spells. Burada biz bir Huffman-kodlanmış fayl üçün struct var. Bir Huff fayl ilə bağlı bu xüsusiyyətlər bütün var. Sonra aşağı burada bir Huff fayl üçün başlıq var, belə ki, biz bu Huffeader zəng əvəzinə hər halda eyni səslənir, çünki əlavə h durub. Cute. Biz bununla bağlı bir sehrli var. Bir faktiki Huff fayl varsa, o qədər yuxarıda bu sehrli bir sıra olacaq. Və sonra bir sıra olacaq. Belə ki, hər bir simvolu üçün olan 256, var bu simvol tezliyi də Huff fayl ərzində nə siyahısını olacaq. Və sonra nəhayət, biz tezliklərin üçün checksum var olan tezliklərin məbləğ olmalıdır. Belə ki, nə bir Huffeader edir. Sonra Huff fayl növbəti bit qayıtmaq ki, bəzi funksiyaları vardır habelə hfclose, burada bu funksiya, sonra Huff fayl bir az yazır, ki, əslində Huff fayl bağlayır. Əvvəl, biz düz yalnız fclose ilə məşğul idi ancaq bir Huff fayl zaman əvəzinə fclosing haqqında nə həqiqətən nə olacaq hfclose və hfopen edir. Bu biz ilə məşğul olacaq olduğunuz Huff faylları xüsusi funksiyaları. Sonra burada mövzu oxumaq və sonra mövzu yazın. 

Yalnız. H fayl oxuyaraq biz bir Huff fayl ola bilər nə bir mənada almaq cür bilərsiniz bu, əslində huffile.c daxil davam olmadan, nə xüsusiyyətləri ki, biz dalış, əgər bir az daha kompleks olacaq. Bu I / O burada göstəricilər ilə məşğul olan fayl bütün var. Burada biz hfread zəng zaman, məsələn, hələ fread ilə məşğul ki, görürük. Biz tamamilə həmin funksiyaları kurtulmanın deyilik, amma biz qayğı bu gönderiyorsanız əvəzinə özümüzü bütün etmənin Huff fayl daxilində. Siz maraqlı olduğunuz halda bu vasitəsilə scan pulsuz hiss edə bilərsiniz və getmək və geri qat bir az qabığı. 

Biz baxmaq olacaq ki, növbəti fayl tree.h. edir Bu gözden geçirmek slaydlar əvvəl biz Huffman node gözlədiklərini söylədi və biz typedef struct node etdi. Biz simvolu tezlik, sonra 2 node ulduz gözləmir. Bu halda biz nə edirik bu mahiyyətcə eyni edir əvəzinə node başqa biz onlara ağac zəng olacaq. Biz sizə ağac etmək zəng zaman bir ağac göstərici qaytarır bir funksiyası var. Yeni bir node edilməsi zaman Speller geri dediniz node * yeni söz = malloc (sizeof) və bu kimi şeylər. Əsasən, mktree sizin üçün ki, ilə məşğul olacaq. Eynilə, bir ağac aradan qaldırılması üçün istədiyiniz zaman, ki, mahiyyətcə, bu ilə bittiğinde ağac azad edir əvəzinə aydın ki, pulsuz zəng, həqiqətən, yalnız rmtree funksiyasını istifadə etmək olacaq Əgər ki, ağac üçün pointer keçmək və harada tree.c sizin üçün ki, qayğı olacaq. 

Biz tree.c. baxmaq Biz həyata görmək istisna olmaqla, eyni funksiyaları gözləyirik. Biz gözlənilir ki, siz mktree zəng zaman, bir göstərici bir ağac boy mallocs bu NULL dəyəri, belə 0s və ya NULLs, bu dəyərlərin bütün initializes və sonra yalnız sizin üçün malloc'd etdik ki, ağac üçün pointer qaytarır. Burada ağac aradan zəng zaman ilk ikiqat azad deyilik təmin edir. Bu, həqiqətən, aradan qaldırılması, istədiyiniz bir ağac var ki, təmin edir. Bir ağac da öz uşaqlar daxildir, çünki burada Bu nə o recursively ağac sol node haqqında ağac aradan çağırır habelə sağ node kimi. Bu ana kurtarır əvvəl, habelə uşaqların azad etmək lazımdır. Ana da kök ilə əvəz edir. Belə böyük-böyük-böyük-böyük babası kimi ilk valideyn, və ya nənə ağac, ilk biz ilk səviyyəsi aşağı azad var. Belə ki, o, pulsuz altına axır, sonra o, s, geri pulsuz gəlib Belə ki, ağac var. 

İndi biz meşə baxın. Siz Huffman ağac bütün yerləşdirmək yerləşir Forest edir. Bu süjet adlı biz bir şey olacaq ki, var ki, bir ağac bir göstərici, eləcə də sonrakı adlı süjet bir göstərici var. Hansı struktur kimi baxmaq bu cür edir? Bu cür orada artıq deyir. Burada artıq. A bağlı siyahısı. Biz bir süjet zaman bu sahələri bir bağlı siyahı kimi görürük. A meşə, sahələrinin bağlı siyahı kimi müəyyən edilir və belə meşə quruluşu biz yalnız bizim ilk süjet bir göstərici var olacaq ki, və süjet içinde bir ağac və ya daha çox ağac işarə və sonra və s, növbəti sahəsi göstərir. Meşə etmək üçün biz mkforest çağırırıq. Sonra biz burada olduqca faydalı funksiyaları vardır. Siz qaytarılması dəyəri Tree * sonra bir meşə keçir və Biz, seçin var bir ağac bir göstərici. Nə pick edəcəyik siz işarə edirik ki, meşə getmək edəcək o meşə aşağı tezlikli bir ağac çıxarmaq və o ağac sizə göstərici verir. Seçdiyiniz zəng sonra, ağac, artıq meşə mövcud deyil lakin qaytarılması dəyər ki, ağac göstəricisidir. Sonra bitki var. Bir qeyri-0 tezlik var ki, bir ağac bir pointer keçmək şərtlə ki, nə bitki edəcəyik ki, meşə alması ağac almaq və bitki edir ki, meşə ağac daxilində. Burada rmforest var. Əsasən bizim ağac bütün azad olan ağac, aradan qaldırılması Oxşar meşə aradan qaldırılması meşə olan pulsuz hər şey olacaq. 

Biz forest.c baxmaq varsa, orada ən azı 1 rmtree əmr görmək üçün gözləmək lazımdır çünki bir meşə bu ağacları var əgər meşə pulsuz yaddaş, sonra nəhayət, siz də o ağacları aradan qaldırılması üçün olacaq. Biz forest.c baxmaq varsa, biz gözləyirik kimi olan mkforest var. Biz malloc şeylər. Ilə başlamaq üçün boş, çünki Biz, NULL kimi meşə ilk süjet başlamaq biz ən aşağı çəki ilə ağac qaytarır olan pick, aşağı tezlikli bax və sonra xüsusi node xilas olur ki, ağac bal və növbəti bir, belə ki, meşə bağlı siyahı ki, edir. Və sonra biz burada olan bağlı siyahısına daxil edər bir ağac bitki var. Nə meşə, bu gözəl, bizim üçün sıralanır saxlayır deyil. Və sonra, nəhayət, biz gözlənildiyi kimi, biz orada deyilir rmtree var rmforest var. 

Bu günə qədər paylama kodu baxanda huffile.c, başa qədər ağır tərəfindən yəqin idi digər faylları halbuki özləri riayət etmək olduqca sadə idi. Göstəricilərinə və bağlı siyahıları və bizim bilik ilə, biz olduqca yaxşı əməl edə bildik. Amma biz həqiqətən biz tam başa əmin etmək lazım olan bütün. H faylları edir Siz, o geri dəyərləri ilə məşğul olan, həmin funksiyaları zəng etmək lazımdır, çünki belə tam həyata gedir nə hərəkət başa əmin olun bu funksiyaları bir zəng zaman. Amma həqiqətən daxilində anlaşma biz həmin çünki olduqca zəruri deyil. H faylları. Biz bölüşdürülməsi kodu qalan 2 daha çox fayl var. 

Nin dump baxaq. Burada comment ilə kötük bir Huffman sıkıştırılmış fayl edir və sonra tərcümə və zibilliklərin onun məzmunu bütün. Burada o hfopen zəng ki, görürük. Bu, * input = fopen fayl aynalama növü və sonra məlumat keçir. Əvəzinə bir Huffile keçən edirik bir file * istisna olmaqla demək olar ki, eyni deyil; əvəzinə fopen sizə hfopen keçən edirik. Burada cür biz mövzu oxumaq necə oxşar olan, ilk mövzu oxumaq bir bitmap fayl üçün. Biz burada edirik görmək yoxlanılması olub başlığı məlumat bir faktiki Huff fayl ki, göstərir ki, doğru sehrli sayı ehtiva edir, sonra əmin həmin çek bütün biz açıq bir faktiki huffed fayl və ya deyil ki, fayl ki. Bu nə biz görürük ki, rəmzləri bütün tezliklərdə çıxışlar edir qrafik masa bir terminal daxilində. Bu hissə faydalı olacaq. Bu bir az var və dəyişən bit daxil yavaş-yavaş oxuyur və sonra çap edir. Mən bir fayl huffing nəticəsində olan hth.bin üzrə dump zəng idi əgər heyəti həll istifadə edərək, mən bu almaq olardı. Bu simvol bütün tipi və onlar görünür hansı tezlik verilməsi oldu. Biz baxsaq, onların əksəriyyəti bu istisna 0s olunur: iki dəfə görünür H, və sonra bir dəfə görünür T. Və sonra biz burada 0s və 1s faktiki mesaj var. Biz hth.txt baxsaq, bu, güman huffed ki, orijinal mesaj biz bəzi Hs və Ts görmək gözləyirik. Xüsusilə, biz yalnız 1 T və 2 Hs görmək gözləyirik. Burada hth.txt var. Bu, həqiqətən HTH var. Biz bunu görə bilmirik, baxmayaraq ki, orada daxil bir newline karakter. The Huff fayl hth.bin də həmçinin newline karakter kodlama olunur. Burada biz, sifariş newline sonra HTH və bilirik ki, çünki biz yalnız bir 1 yəqin ki, H təmsil görə bilərsiniz və sonra T yəqin ki, 01 və sonrakı H 1 eləcə və sonra biz iki 0s tərəfindən göstərilən bir newline var. Cool. 

Və sonra, nəhayət, biz çox. C ilə məşğul olan və. Edirik çünki h faylları, biz compiler üçün olduqca kompleks bəhanə olacaq və belə ki, burada sizin üçün dump edir Makefile var. Amma faktiki olaraq, öz puff.c fayl edilməsi haqqında getmək üçün var. Bu Makefile həqiqətən sizin üçün puff.c edilməsi ilə məşğul deyil. Biz Makefile redaktə sizə qədər tərk edirik. Siz bütün kimi bir komanda daxil edərkən, məsələn, bu sizin üçün bütün edəcək. Ötən pset dən Makefile nümunələri baxmaq üçün çekinmeyin eləcə də sizin Puff fayl edə bilər necə bu bir gediş bu Makefile redaktə edir. Yəni bizim paylanması kodu bu barədə var. 

Biz vasitəsilə kazanılmış sonra, sonra burada yalnız bir öyüd-nəsihət var necə ki, biz Huffman qovşaqlarının ilə məşğul olmaq üçün olacaq. Biz artıq onlara qovşaqlarının zəng etmək fikrində deyilik, biz onlara ağac zəng etmək olacaq biz bir char öz rəmzi təmsil olacaq yerləşir, onların tezliyi, bir tam olan hadisələr sayı. Bir float daha dəqiq çünki Biz istifadə edirik. Və sonra biz sol uşaq, eləcə də sağ uşaq başqa bir göstərici yoxdur. A meşə, biz gördüyümüz kimi, yalnız ağac bağlı siyahısı. Nəhayət, biz Huff fayl yaradılmasına etdiyiniz zaman, biz forest yalnız 1 ağac ehtiva istəyirəm - 1 ağac, bir çox uşaqlar ilə 1 kök. Əvvəllər biz yalnız bizim Huffman ağacları edirdilər zaman, biz ekran üzərində qovşaqlarının bütün qoymaqla başlayıb və biz bu qovşaqlarının var olacaq deyərək nəhayət yarpaqları olmaq olacaq və bu, onların simvoludur, bu onların tezliyi edir. Biz yalnız 3 məktub varsa, bizim meşə ki, 3 ağac bir meşə var. Və sonra biz ilk valideyn əlavə zaman, getmək kimi biz 2 ağacların meşə etdi. Biz meşə həmin uşaqların 2 çıxarılır və sonra bir valideyn node ilə əvəz uşaqlar kimi o 2 qovşaqlarının idi. Və sonra nəhayət, bizim son olaraq, pansiyonlar ilə məsələn edilməsi ilə addım və Cs son ana etmək olardı, və belə sonra 1-meşə ağacları bizim ümumi sayı gətirəcəyini. Hər kəs sizin meşə çox ağac ilə başlamaq necə görür və 1 ilə qədər? Okay. Cool. 

Biz Puff üçün nə etmək lazımdır? Biz nə etmək lazımdır kimi həmişə, onlar bizə giriş hüququ növü vermək təmin edilir biz, həqiqətən, bu proqram çalıştırabilirsiniz ki. Bu halda onlar ilk komanda-line arqument sonra bizə verilməsi üçün olacaq 2: biz decompress və decompressed faylı çıxış istədiyiniz faylı. Amma bir dəfə biz, onlar dəyərlər hüququ məbləği bizə keçir əmin olun biz daxil Huff fayl və ya deyil ki, təmin etmək istəyirik. Və sonra bir dəfə biz, sonra biz ağac qurmaq istəyirik, bu Huff fayl ki, zəmanət bu mesajı şəxs inşa ağac oyunları belə ağac qurmaq. Biz ağac qurmaq sonra, biz ilə 0s və onlar keçdi 1s, məşğul ola bilər bu eyni, çünki, bizim ağac yanaşı bu əməl və sonra, mesaj yazmaq chars geri bit şərh. Və sonra sonunda biz burada göstəricilər ilə məşğul olduğunuz çünki Biz hər hansı bir yaddaş sızıntıları yoxdur əmin etmək istəyirəm və biz pulsuz hər şey. 

Düzgün istifadə edilməsi artıq bizim üçün köhnə hat edir. Biz daxil etmək, hansı kabartmak üçün fayl adı olacaq, və sonra bir çıxış müəyyən belə mətn faylı olacaq puffed çıxış üçün fayl adı. Bu istifadə edir. İndi biz daxil huffed və ya deyil ki, təmin etmək istəyirik. Geri düşüncələri, bizə kömək edə bilər ki, distribution kodu orada bir şey idi bir fayl huffed və ya olub-olmadığını anlama ilə? Bu Huffeader haqqında huffile.c məlumat var idi. Biz hər Huff fayl sehrli sayı ilə bağlı Huffeader var bilirik ki, hər rəmzi üçün tezliklərin eləcə də bir sıra həmçinin bir checksum kimi. Biz bilirik ki, ancaq biz də dump.c bir peek etdi olan bir Huff fayla oxuyurdum. Və bunu, o, həqiqətən huffed və ya olub-olmadığını yoxlamaq idi. Belə ki, bəlkə biz puff.c. üçün struktur kimi dump.c istifadə edə bilər Geri pset 4 biz RGB üç dəfə replikasiya ki fayl copy.c zaman və biz Whodunit və RSS üçün şərh eyni, nə edə yalnız cp dump.c puff.c kimi komanda çalışır və kodu bəzi istifadə edin. Lakin, bir müddət kimi sadə olacaq deyil puff.c daxil dump.c çevrilməsində, lakin ən azı başlamaq üçün haradasa verir giriş həqiqətən huffed və ya təmin etmək üçün necə həmçinin bir neçə digər şeylər kimi. Biz düzgün istifadə təmin giriş huffed ki, təmin etmişdir. Biz müvafiq səhv yoxlanılması etmişik etdik ki, hər zaman, belə bir problem varsa, geri və bir uğursuzluq baş əgər funksiyası çıxdıqda. 

İndi biz nə etmək istəyirəm faktiki ağac qurmaq deyil. Biz Meşə baxsanız, 2 əsas funksiyaları var biz çox tanış olmaq istədiyiniz olacaq ki,. Orada Boolean funksiyası bitki ki, bizim meşə daxilində qeyri-0 tezlik ağac bitkiləri. Və orada bir meşə və ağac bir göstərici bir pointer ilə keçir. Sadə sual: Bir Huffman ağac tikinti etdiyiniz zaman neçə meşə siz olacaq? Bizim meşə hüququ, bizim kətan kimi? Beləliklə, biz yalnız 1 meşə var olacaq, lakin biz çox ağac var olacaq. Siz bitki zəng Belə əvvəl ehtimalla sizin meşə etmək istəyirəm olacaq. Bir meşə edə bilər necə forest.h baxmaq əgər bir komanda üçün var. Siz bir ağac əkmək bilər. Biz bunu bilirik. Və sonra da, meşə bir ağac ala bilərsiniz aşağı çəki ilə bir ağac aradan qaldırılması və sizə göstərici verilməsi. Biz nümunələri özümüz bunu zaman geri düşüncələri, biz onu rəsm zaman biz sadəcə yalnız links əlavə edib. Amma burada əvəzinə yalnız links əlavə bu qovşaqlarının 2 aradan qaldırılması və sonra başqa bir ilə əvəz etdiyiniz kimi daha düşünün. Seçmək və əkin baxımından ifadə etmək üçün, 2 ağacları picking və sonra başqa bir ağac əkilməsi edirik ki, siz uşaqlar kimi seçilmiş olan 2 ağacları var. Huffman nin ağac qurmaq üçün, üçün simvollar və tezliklərdə oxuya bilərsiniz bu Huffeader sizə verir, çünki Siz tezliklərin bir sıra verir. Beləliklə, siz davam edə bilər və yalnız bu 0 şey ignore biz bu ilin sonunda 256 yarpaqları istəmirəm çünki. Biz yalnız simvol ki, yarpaqları sayı istəyirəm əslində fayl istifadə olunur. Siz bu işarələri oxumaq və qeyri-0 tezliklərin ki, bu simvol hər bilər o ağac olacaq. Nə olar, bir qeyri-0 tezlik simvolu oxumaq hər zaman siz meşə ki, ağac əkmək bilər. Siz meşə ağacları əkmək sonra, bacı kimi bu ağac qoşulmaq olar Belə ki, əkin və seçin yerləşir aldığınız 2 və sonra bitki 1 geri gedir 1-ki, bitki siz seçilmiş ki, 2 uşaq valideyn edir. Belə ki, sonra son nəticə sizin meşə bir ağac olacaq. Bu sizin ağac qurmaq nasıl. 

Burada yanlış getmək bilər ki, bir neçə şey var çünki biz yeni ağac edilməsi və bu kimi göstəricilər və hər şeyi ilə məşğul ilə məşğul olursunuz. Biz göstəricilər ilə məşğul olan zaman əvvəl, biz malloc'd zaman biz bunu bizə NULL pointer dəyər qaytarmayıb əmin etmək istəyirdi. Beləliklə, bu prosesi çərçivəsində bir neçə addımlar bir neçə hallarda olmalıdır gedir Ü proqram uğursuz ola bilər. Nə istəyirəm, siz bu səhvlər idarə əmin etmək istəyirəm ki, və spec bu, qəşəng onları idarə etmək üçün deyir belə proqram çıxmaq var niyə izah istifadəçi bir mesaj çap istəyirəm və sonra dərhal bu çıxın. Bu səhv rəftar etmək, onu yoxlamaq istəyirəm ki, xatırlayıram uğursuz ola bilər ki, hər bir zaman. Yeni bir pointer edirik ki, hər bir zaman Əgər uğurlu və əmin etmək istəyirəm. Yeni bir pointer və malloc onu nə üçün istifadə nə əvvəl, və sonra biz bu göstərici NULL olub yoxlamaq olardı. Belə ki, bunu yalnız bilər, bəzi hallarda olmalıdır gedir amma bəzən həqiqətən bir funksiyası zəng etdiyiniz və funksiyası ərzində ki, mallocing məşğul olan biri. Bu halda, biz kodu çərçivəsində funksiyaları bəzi geri baxmaq əgər, bəziləri Boolean funksiyaları. Abstrakt halda biz foo adlı Boolean funksiyası varsa, əsasən, biz foo nə olursa olsun bunu əlavə güman edə bilər bir Boolean funksiyası olduğundan, bu, doğru və ya yalan qaytarır - əgər doğru uğurlu, yalan əgər. Beləliklə, biz foo qaytarılması dəyəri doğru və ya yalan olub-olmadığını yoxlamaq istəyirlər. O yalan varsa, biz mesajı bir növ çap etmək istəyirəm olacaq o deməkdir ki, və sonra proqram çıxın. Biz nə istəyirik foo qaytarılması dəyəri kontrol edir. Foo yalan qaytarır, onda biz səhv bir növ rast bilirik ki, və biz proqram çıxmaq lazımdır. Bunun yolu faktiki funksiyası özü üçün şərt olduğu bir vəziyyət var. Foo x götürür söyləyin. Biz əgər bir şərt kimi ola bilər (foo (x)). Foo icra sonunda doğru qayıtdıqda əgər əsasən, o deməkdir ki, funksiyası foo qiymətləndirmək, çünki biz bunu edə bilərsiniz bütün şəraiti qiymətləndirmək üçün. Belə ki, o funksiyası doğru qayıdır və uğurlu Əgər bir şey edə bilərsiniz. Amma səhv yoxlanılması olduğunuzda, siz yalnız funksiyası yalan qaytarır əgər çıxmaq istəyirəm. Nə edə bilərdi yalnız əlavə edilir == saxta və ya yalnız qarşısında bang əlavə sonra (! foo) əgər var. Bu şərtlə ki, ki, bədən daxilində siz səhv rəftar bütün olardı belə "Bu ağac yaratmaq bilmədi" kimi və sonra 1 və ya bu kimi bir şey geri. Ki, nə olsa da, foo yalan geri baxmayaraq ki, - Foo doğru qaytarır söyləyin. Sonra yenidən foo zəng etmək yoxdur. Bu ümumi misconception var. Sizin vəziyyətdə idi, çünki artıq qiymətləndirilir ki, siz ağac və ya kimi bir şey etmək kullanıyorsanız siz artıq nəticə var və ya bitki və ya seçin və ya bir şey. Bu artıq dəyər var. Artıq icra edir. Belə ki, vəziyyət Boolean funksiyaları istifadə etmək faydalıdır çünki və ya, həqiqətən, loop orqanı həyata deyil, hər halda funksiyasını icra edir. 

Son addım Bizim ikinci fayl mesaj yazır. Sonra biz Huffman ağac tikmək, sonra fayl mesaj yazılı olduqca sadə deyil. Bu, yalnız 0s və 1s riayət indi olduqca sadə var. Və qaydaları ilə biz bir Huffman ağac ildə 0s tərk göstərir bilirik ki, və 1s sağ göstərir. Bir 0 almaq ki, yavaş-yavaş oxumaq Beləliklə, əgər hər dəfə Əgər 1-ci oxumaq hər zaman sonra sol qolu edin və lazımdır sağ filialı izləmək olacaq. Bir yarpaq hit qədər və sonra davam etmək olacaq yarpaqları filiallarının sonunda olacaq, çünki. Biz bir yarpaq və ya təşkil etdik olub necə deyə bilərsiniz? Biz əvvəl bildirib. [Tələbə] Bu göstəricilər NULL edin. >> Bəli. Sol və sağ, həm də ağaclar üçün göstəricilərinə NULL, əgər biz bir yarpaq təşkil etdik, biz deyə bilərik. Mükəmməldir. Biz Huff fayla yavaş-yavaş oxumaq istəyirəm ki, bilirik. Biz dump.c əvvəl gördüm ki, onlar nə onlar Huff fayla yavaş-yavaş oxumaq deyil və yalnız bit nə çap. Biz bunu etmək fikrində deyilik. Biz bir az daha kompleks olduğunu bir şey bunu etmək olacaq. Amma nə biz nə edə bilər, biz bit üçün deyilir ki kodu ki, bit almaq olar. Burada biz istəyirik ki, cari bit təmsil tam bit var. Dosyayı sonunda hit qədər Bu faylı bit bütün iterating qayğısına qalır. Ki, əsasən, sonra iterator bir növ istəyirəm olacaq Sizin ağac axır etmək. Və sonra bit 0 və ya 1 olub əsaslanır ya sol ki iterator hərəkət və ya sağa hərəkət etmək istəyirəm olacaq bütün yolu bir yarpaq hit qədər, belə ki, bütün yol etdiyiniz ki node qədər daha çox qovşaqlarının qeyd deyil. Niyə biz bir Huffman fayl deyil Morze əlifbası ilə bunu edə bilərsiniz? Morse kodu qeyri bir az var idi. Biz gözləyin oh kimi ola bilər ki, yol boyunca bir məktub edib sonra, belə bəlkə bu, bizim məktub biz yalnız bir az artıq davam edərsə, onda biz başqa məktub hit olardı halbuki. Amma ki, Huffman encoding baş gedən deyil biz olacaq ki, yalnız yol xarakteri edib ki, arxayın ola bilərsiniz ki node sol və sağ uşaqlar NULL əgər edir. 

Nəhayət, biz yaddaş bütün azad etmək istəyirik. Biz məşğul olduğunuz hər iki yaxın Huff fayl istəyirəm habelə meşə ağacları bütün çıxarın. Sizin həyata əsaslanır, yəqin ki, meşə aradan səslənmək istəyirəm olacaq əvəzinə faktiki ağac özünüzü bütün keçir. Əgər hər hansı bir müvəqqəti ağacları edilən Lakin, bu azad lazımdır. Siz yaxşı bilirsiniz kodu, belə yaddaş ayrılması olduğunuz bilirsiniz. Və siz getmək əgər, malloc üçün F'ing hətta Control ilə başlamaq görən zaman malloc və ki, bütün azad əmin edilməsi lakin sonra yalnız, kodu keçir yaddaş ayrılmış ola bilər Ü anlama. Adətən yalnız "bir fayl sonunda mən yalnız mənim meşə meşə aradan qaldırılması üçün gedirəm" deyə bilər belə əsasən pulsuz ki, yaddaş sil ki, "Və sonra da faylı bağlamaq və sonra mənim proqram çıxmaq niyyətindədir gedirəm." Lakin proqram fit ki, yalnız vaxt? Xeyr, çünki bəzən baş verən bir səhv var bilər. Bəlkə bir fayl açmaq bilməz və ya başqa bir ağac gələ bilmədi və ya səhv bir növ yaddaş ayrılması prosesi baş və buna NULL döndü. Bir səhv baş, sonra geri və çıxın. Beləliklə, sizin proqram hər hansı bir zamanda tərk edə bilər ki, əmin etmək istəyirəm siz yaddaş bütün azad etmək istəyirik. Bu yalnız sizin kodu çıxmaq əsas funksiyası çox sonunda olacaq deyil. Siz kodu potensial vaxtından əvvəl geri ola bilər ki, hər bir instansiya geri baxmaq istəyirəm və sonra azad nə yaddaş hissi verir. Siz meşə etmək və saxta geri çağırmışdı edirlər. Sonra yəqin ki, meşə aradan qaldırılması lazım deyil Henüz bir meşə yoxdur çünki. Amma kodu hər nöqtəsində sizi vaxtından əvvəl geri bilər Ü Əgər hər hansı yaddaş azad əmin etmək istəyirəm. 

Beləliklə, biz yaddaş azad ilə məşğul olan və potensial itkilərin qarşılaşdıqda zaman, biz qərar və məntiq istifadə yalnız mənə həm də düzgün və ya bizim yaddaş bütün azad belirlemek üçün Valgrind istifadə edin. Siz ya Puff haqqında Valgrind çalıştırabilirsiniz və sonra siz də onu keçmək üçün komanda-line dəlilləri hüququnu sayı Valgrind üçün. Siz çalıştırabilirsiniz, ancaq çıxış bir az sirli edir. Biz Speller ilə istifadə bir az kazanılmış sonra, lakin biz hələ bir az daha kömək lazımdır belə, sonra qaçaq kontrol = tam kimi bir neçə bayraqları ilə çalışan ki, yəqin ki, bizə Valgrind bir çox faydalı çıxış edəcək. 

Sonra ayıklama etdiyiniz zaman digər faydalı tip fərq əmr edir. Siz Huff heyəti icrası daxil run bir metin fayl, bilər və sonra xüsusi olmaq, ikili fayl, ikili Huff fayl üçün çıxış. Sonra ki, ikili fayl öz yastıq run, əgər sonra ideal, sizin outputted mətn faylı eyni olacaq Daxil keçdi orijinal bir Burada nümunə kimi hth.txt kullanıyorum və sizin spec haqqında danışdı biri. Bu sözün yalnız HTH sonra newline var. Amma mütləq çekinmeyin və siz mütləq artıq nümunələr istifadə etmək tövsiyə olunur mətn faylı üçün. 

Siz hətta decompressing sonra bəlkə kompressor bir shot almaq olar Müharibə və Sülh kimi Speller istifadə olunan faylları bəzi və ya Jane Austen və ya kimi bir şey - sərin cür ki, - və ya Austin Powers, biz bu böyük faylları ilə məşğul cür enmək deyil, çünki Burada növbəti aracı, ls-l istifadə edin. Biz əsasən cari kataloq bütün məzmunu listeler ls, istifadə edirik. Bayraq-l keçən həqiqətən bu faylların ölçüsünü göstərir. Siz pset spec keçir, bu, həqiqətən, ikili fayl yaratmaq vasitəsilə dolaşır onu huffing və siz çox kiçik faylları görmək bu kompressor və məlumat bütün tərcümə yer dəyəri kimi bütün tezliklərdə və şeyi faktiki fayda üstələyir ilk növbədə fayl sıxılma edir. Bir uzun mətn faylları run əgər Lakin, sonra sizə bir xeyir əldə etmək başlamaq ki, görə bilərsiniz bu faylları kompressor edir. 

Və sonra, nəhayət, biz mütləq çox lazımlı gələcək olan bizim köhnə dost gdb var. 

Biz ağaclar edilməsi bəlkə Huff ağac və ya prosesin hər hansı bir sual yoxdur və ya Huff'n Puff hər hansı digər suallar? Okay. Mən bir az ətrafında qalmaq lazımdır. 

Thanks, everyone. Bu gözden geçirmek 6 idi. Və uğurlar yaxşı. 

[CS50.TV]