[Powered by Google Translate] [Walkthrough - Set Problema 6] [Zamyla Chan - Universitatea Harvard] [Acest lucru este CS50. - CS50.TV] 

Bună ziua, tuturor, si bun venit la Walkthrough 6: Huff'n Puff. În Puff Huff'n ceea ce facem va fi de-a face cu un fișier comprimat Huffman și apoi puffing-l înapoi, așa că decompressing, astfel încât să putem traduce din 0s și 1s că utilizatorul trimite-ne și ao transforma înapoi în textul original. PSET 6 se va fi destul de cool pentru că ai de gând pentru a vedea unele dintre instrumentele pe care ați utilizat în PSET 4 și 5 și PSET un fel de a le combina într-un concept destul de elegant atunci când vin să te gândești la asta. 

De asemenea, fără îndoială, PSET 4 și 5 au fost cele mai dificile pe care psets am avut de oferit. Deci, de acum, avem această PSET 1 mai mult în C, și apoi după că suntem pe programare web. Deci, vă felicit pentru obtinerea peste cele mai dificile bizon în CS50. 

Mutarea de pe Puff pentru Huff'n, set de instrumente nostru pentru acest PSET vor fi copaci Huffman, astfel încât înțelegerea nu numai modul de lucru binar copaci, dar, de asemenea, în special arbori Huffman, modul în care sunt construite. Și apoi vom avea o mulțime de cod de distribuție în acest PSET, și vom veni să vedem că de fapt, o parte din codul noi nu ar putea fi capabil să înțeleagă pe deplin încă, și astfel cei care vor fi fișierele. c, dar apoi își însoțesc h fișiere. ne va da suficient de înțelegere de care avem nevoie, astfel încât să știm cum funcționează aceste funcții sau cel puțin ceea ce ar trebui să facă - intrări și ieșiri ale acestora - chiar dacă nu știm ce se întâmplă în cutia neagră sau nu înțeleg ce se întâmplă în cutia neagră în termen de. Și apoi în cele din urmă, ca de obicei, avem de-a face cu structuri de date noi, anumite tipuri de noduri care indica anumite lucruri, și astfel avem aici un creion și hârtie, nu numai pentru procesul de proiectare și atunci când sunteți încercarea de a seama cum PSET ta ar trebui să funcționeze dar, de asemenea, în timpul de depanare. Puteți avea GDB alături de creion și o hârtie în timp ce ia în jos ce valorile sunt, în cazul în care săgețile tale sunt orientate, și lucruri de genul asta. 

În primul rând să ne uităm la copaci Huffman. Arbori Huffman sunt arbori binari, ceea ce înseamnă că fiecare nod are doar 2 copii. În copaci Huffman caracteristică este că valorile cele mai frecvente sunt reprezentate de cele mai putine biți. Am văzut în exemplele de curs de codul Morse, ce fel de consolidat niște scrisori. Dacă sunteți încercarea de a traduce un A sau un E, de exemplu, te traducerea că de multe ori, astfel încât în ​​loc de a avea pentru a utiliza un set complet de biți alocate pentru acel tip de date de obicei, îl comprimați până la mai puține, și apoi aceste scrisori, care sunt reprezentate mai multe ori sunt reprezentate cu biți mai lungi pentru că vă puteți permite ca, atunci când se cântăresc frecvențele că aceste scrisori apar. Avem aceeași idee aici, în copaci Huffman în cazul în care facem un lanț, un fel de cale pentru a ajunge la anumite personaje. Și apoi personajele care au cea mai mare frecvență vor fi reprezentate cu cele mai putine biți. 

Modul în care vă construi un copac Huffman este prin plasarea dintre toate personajele care apar în text și calcularea frecvenței lor, cât de des acestea apar. Acest lucru ar putea fi un număr de câte ori apar aceste scrisori sau poate un procent de din toate personajele câte fiecare dintre apare. Și astfel ceea ce faci este o dată aveți toate că afară cartografiate, Apoi te uiți pentru frecvențele mai mici 2 și apoi li se alăture ca frații în cazul în care, atunci nodul părinte are o frecvență care este suma sale 2 copii. Și apoi, prin convenție, spune că din stânga nod, urmați de faptul că în urma ramura 0, și apoi nodul din dreapta este ramura 1. Așa cum am văzut în codul Morse, unul a fost prins că, dacă ați avut doar un bip bip și a fost ambiguă. S-ar putea să fie o literă sau ar putea fi o secvență de 2 litere. Și ce face este Huffman copaci, deoarece prin natura personajelor sau noastre finale de caractere reale fiind nodurile de pe ultimele ramura - ne referim la cele cum frunzele - în virtutea că nu poate exista nici o ambiguitate în funcție de care scrisorii pe care încercați să codifica cu seria de biți deoarece nicăieri de-a lungul biți care reprezintă 1 literă te va întâlni o altă scrisoare întreg, și nu va fi nici o confuzie acolo. Dar noi vom merge în exemple pe care voi poate vedea de fapt, că în loc de noi doar vă spun că e adevărat. 

Să ne uităm la un exemplu simplu de un copac Huffman. Am un șir de aici, care este de 12 caractere. Am 4 Ca, 6 B, C și 2. Primul meu pas ar fi să număr. Cum de multe ori nu o sa apara? Se pare de 4 ori în șir. B apare de 6 ori, și C apare de 2 ori. Firește, am de gând să spun eu sunt, folosind B cele mai multe ori, așa că am dori să reprezinte B cu cel mai mic număr de biți, cel mai mic număr de 0s și 1s. Și apoi, de asemenea, am de gând să aștepte C a solicita mai cantitatea de 0s și 1s, de asemenea. În primul rând ceea ce am făcut aici este le-am plasat în ordine crescătoare, în ceea ce privește frecvența. Vedem că C și A, acestea sunt cele 2 cele mai mici frecvențe. Vom crea un nod părinte, și că nodul părinte nu are o scrisoare de asociat cu acesta, dar ea are o frecvență, care este suma. Suma devine 2 + 4, care este de 6. Apoi urmăm ramura stanga. Dacă am fost la acel nod 6, atunci ne-ar urma pentru a ajunge la 0 C și apoi 1 pentru a obține la A. Deci acum avem 2 noduri. Avem valoare 6 și apoi ne-am, de asemenea, un alt nod cu valoarea 6. Și astfel cei doi nu sunt doar mai mic, dar, de asemenea, la doar 2 2 care au rămas, asa ne alăturăm celor de un alt părinte, cu suma fiind de 12. Deci, aici avem copacul nostru Huffman în cazul în care pentru a ajunge la B, care ar fi doar bit 1 și apoi pentru a ajunge la o vom avea 01, iar apoi C cu 00. Deci, aici vom vedea că practic ne reprezintă aceste caractere, cu 1 sau 2 biți în cazul în care B, după cum a prezis, are cel. Și apoi ne-am asteptat sa aiba cea mai mare C, dar din moment ce este un astfel de mic copac Huffman, atunci A este, de asemenea, reprezentată de 2 biți, spre deosebire de undeva la mijloc. 

Doar pentru a trece peste un alt exemplu simplu de arbore Huffman, spunem că aveți șirul "Hello". Ceea ce faci este în primul rând v-ar spune de câte ori se H apare în asta? H apare o singură dată și apoi e apare o singură dată și apoi ne-am l apar de două ori și o dată apare. Și așa, atunci ne așteptăm scrisoarea, care să fie reprezentate de către cel mai mic număr de biți? [Elev] L. L >>. Da. L are dreptate. Ne așteptăm ca l pentru a fi reprezentat de cel mai mic număr de biți deoarece l este utilizat cel mai mult în șirul "Hello". Ceea ce am de gând să fac acum este egal în aceste noduri. Am 1, care este H, iar apoi un alt 1, care este e, iar apoi o 1, care este o - acum le-am pune în ordine - și apoi 2, care este l. Apoi am spus modul în care am construi un arbore Huffman este de a găsi cele 2 noduri cu cel mai frecvențele și să le facă frați prin crearea unui nod parinte. Aici avem 3 noduri cu frecvența cea mai mică. Sunt toate 1. Deci, aici vom alege care unul ne vom lega mai întâi. Să spunem că am alege H și e. Suma de 1 + 1 este 2, dar acest nod nu are o scrisoare de asociat cu aceasta. El detine doar valoarea. Acum ne uităm la următoarele 2 mai mici frecvențe. Asta e 2 și 1. Asta ar putea fi una dintre cele 2, dar am de gând să alegeți această unul. Suma este de 3. Și apoi în cele din urmă, am doar 2 stânga, astfel încât atunci care devine 5. Atunci aici, cum era de așteptat, în cazul în care am completați în codificarea pentru că, 1s sunt întotdeauna ramura dreapta si 0s sunt cel stâng. Apoi, avem am reprezentată de doar 1 bit și apoi o cu 2 si apoi e de 2 și apoi H cade la 3 biți. Astfel încât să puteți transmite acest mesaj "Bună ziua" în loc de a folosi efectiv caracterele doar prin 0s și 1s. Cu toate acestea, amintiți-vă că, în multe cazuri am avut legături cu frecvența noastră. Am fi putut s-au alăturat, fie H și o prima poate. Sau mai târziu, atunci când am avut am reprezentat cu 2 precum și sa alăturat uneia reprezentat de 2, am fi putut legate fie unul. 

Și așa că atunci când vă trimite 0s și 1s, că de fapt nu garantează că destinatarul poate citi pe deplin mesajul dvs. right off BAT deoarece acestea ar putea să nu știe ce decizie ai luat. Așa că atunci când avem de a face cu compresie Huffman, cumva avem să spunem destinatarul mesajului nostru modul în care ne-am decis - Ei au nevoie să știe un fel de informații suplimentare în plus față de mesajul comprimat. Ei au nevoie să înțeleagă ceea ce de fapt copacul arata ca, cum ne-am facut de fapt aceste decizii. 

Aici facem doar exemple bazate pe numărul de efective, dar, uneori, puteți avea, de asemenea, un copac Huffman bazat pe frecvența la care literele apar, si este exact acelasi proces. Aici eu o exprimă în termeni de procente sau o fracțiune, și astfel aici, exact același lucru. Mi se pare cel mai mic 2, concluzie le, 2 Urmatorul cel mai mic, le însumați, până când am un copac plin. Chiar dacă am putea face nici un fel, atunci când avem de-a face cu procente, înseamnă că suntem împărțirea lucrurilor și care se ocupă cu zecimale sau, mai degrabă plutește dacă ne gândim despre structurile de date ale unui cap. Ce știm despre flotoare? Ce este o problemă comună atunci când avem de-a face cu flotoare? [Elev] impreciși aritmetică. Da >>. Imprecizie. Din cauza impreciziei în virgulă mobilă, pentru acest PSET, astfel încât să ne asigurăm că noi nu pierdem nici o valoare, apoi vom fapt de gând să se ocupe cu numărul. Deci, dacă ar fi să gândească la un nod Huffman, daca te uiti inapoi la structura aici, daca te uiti la cei verzi are o frecvență asociat cu acesta precum și punctele de la un nod la stânga acestuia, precum și un nod la dreptul său. Și apoi cele roșii au existat, de asemenea, un caracter asociate cu acestea. Noi nu suntem de gând să facă cele separate pentru părinți și apoi noduri finale, care ne vom referi în continuare frunze, ci mai degrabă cei care vor avea doar valori NULL. Pentru fiecare nod vom avea un caracter, simbol că acest nod reprezintă, apoi o frecvență, precum și un pointer la copilul său din stânga, precum și de dreptul său de copil. Frunzele, care se află la partea de jos foarte, ar trebui, de asemenea, indicii de nod la stânga și la dreapta lor, dar din moment ce aceste valori nu sunt orientate în ganglionii reale, ceea ce ar fi valoarea lor? >> [Elev] NULL. NULL >>. Exact. Iată un exemplu despre cum ați putea reprezenta frecvența în flotoare, dar am de gând să se ocupe cu ea cu numere întregi, deci tot ce am făcut este să schimbăm tipul de date acolo. 

Să mergem pe la un pic mai mult de un exemplu complex. Dar acum, că am făcut cele mai simple, e doar același proces. Puteți găsi frecvențele cele mai mici 2, însumați frecvențele si asta e noua frecventa a nodului părinte, care apoi arată la stânga cu ramura 0 și dreapta cu ramura 1. Dacă avem șirul "Aceasta este CS50," atunci vom conta de câte ori este menționat T, h menționat, I, S, C, 5, 0. Atunci ce am făcut aici este cu noduri roșii am plantate, Am spus că voi avea aceste personaje în cele din urmă, la partea de jos a copacul meu. Cei care vor să fie tot de frunze. Atunci ceea ce am făcut este că le-clasificate în funcție de frecvență, în ordine crescătoare, și acest lucru este de fapt modul în care codul de PSET o face Este îl sortează după frecvența și apoi după alfabet. Deci, are numere mai întâi și apoi în ordine alfabetică de frecvență. Atunci ce aș face este că va găsi cel mai mic 2. Asta e 0 și 5. Eu le-ar rezuma, și asta e 2. Atunci aș continua, găsiți următoarele 2 mai mic. Acestea sunt 1s două, și apoi devin cei 2, precum. Acum, eu știu că pasul următor este meu va fi aderarea cel mai mic număr, care este T, 1, și alegând apoi unul dintre nodurile care are 2 ca frecvență. Deci, aici avem 3 optiuni. Ceea ce am de gând să fac pentru diapozitiv este doar vizual rearanja-le pentru tine astfel încât să puteți vedea cum eu o construirea. Ce cod și codul de distribuție este de gând să facă ar fi alătura t un cu nodul 0 și 5. Deci faptul că sumele la 3, iar apoi vom continua procesul. 2 și 2 acum sunt cele mai mici, astfel încât atunci cei suma intre la 4. Toată lumea urma până acum? Bine. Apoi, după ce că avem 3 și 3, care trebuie să fie adăugate, deci din nou, eu sunt doar de comutare, astfel încât să puteți vedea vizual, astfel încât să nu se prea murdar. Atunci avem un 6, iar apoi pas nostru final este acum că avem doar 2 noduri am rezuma cele de a face rădăcina arborelui nostru, care este de 10. Și numărul 10 are sens, deoarece fiecare nod reprezentat, valoarea lor, numărul lor de frecvență, a fost de câte ori au apărut în șir, și apoi avem 5 caractere în șirul nostru, astfel încât are sens. Dacă ne uităm în sus la modul în care ne-ar codifica de fapt, cum era de asteptat, i și s, care apar cel mai des sunt reprezentate de cel mai mic număr de biți. 

Fii atent aici. În copaci Huffman caz, de fapt contează. Un S majuscule este diferită de un s. litere mici. Dacă am fi avut "Aceasta este CS50" cu majuscule, atunci s-ar părea minuscule doar de două ori, ar fi un nod cu 2 valoarea sa, și apoi cu majuscule S-ar fi doar o singură dată. Deci, atunci arborele se va schimba structurile că aveți de fapt, o frunză în plus aici. Dar suma ar fi încă 10. Asta e ceea ce esti de fapt, o să fie de asteptare de control, adăugarea tuturor conteaza. 

Acum, că ne-am acoperit copaci Huffman, putem scufunda in Puff Huff'n, PSET. Vom începe cu o secțiune de întrebări, și acest lucru se întâmplă pentru a te obișnui cu pomi binare și modul în care să opereze în jurul valorii de faptul că: noduri de desen, crearea de dvs. struct propria typedef pentru un nod, și văzând cum s-ar putea insera într-un arbore binar, unul care e sortate, traversează aceasta, și lucruri de genul asta. Această cunoaștere este cu siguranta te va ajuta atunci cand se arunca cu capul în partea Puff Huff'n a PSET. În ediția standard a PSET, sarcina dumneavoastră este de a pune în aplicare Puff, și în versiunea hacker sarcina dumneavoastră este de a pune în aplicare Huff. Ce Huff nu este nevoie de text și apoi îl traduce în 0s și 1s, astfel procesul care am făcut mai sus în cazul în care am numarat frecvențelor și apoi a făcut copac și apoi a spus, "Cum pot obține T?" T este reprezentat de 100, lucruri de genul asta, și apoi Huff va lua textul și apoi de ieșire care binar. Dar, de asemenea, pentru că știm că ne-o dorim pentru a permite destinatarului mesajului nostru de pentru a recrea exact același copac, aceasta include, de asemenea, informații despre numărul de frecvențe. Apoi, cu Puff ni se dă un fișier binar de 0s și 1s și având în vedere, de asemenea, informații despre frecvențele. Noi traducem toți cei înapoi 0s și 1s în mesajul original, care a fost, așa că suntem decompressing. Dacă faci ediția standard, nu trebuie să pună în aplicare Huff, astfel încât, atunci puteți folosi doar punerea în aplicare a personalului Huff. Există instrucțiuni în spec. cu privire la modul de a face acest lucru. Puteți rula punerea în aplicare a personalului Huff asupra unui anumit fișier text și de a folosi apoi că producția ca intrare la Puff. 

Așa cum am menționat mai înainte, avem o mulțime de cod de distribuție pentru asta. Am de gând să înceapă merge prin ea. Am de gând să-și petreacă cea mai mare parte a timpului pe fișiere. H deoarece în fișierele. c, pentru că avem ore. și care ne oferă cu prototipuri ale funcțiilor, nu avem nevoie de a înțelege pe deplin exact - Dacă nu înțelegi ce se întâmplă în fișierele. C, atunci nu vă faceți griji prea mult, dar încercați cu siguranta pentru a lua o privire, pentru că s-ar putea da unele sugestii și este util să te obișnuiești cu citirea codului altor oameni. 

Privind la huffile.h, în comentariile pe care le declară un strat de abstractizare pentru Huffman-codificate fișiere. Dacă mergem în jos, vom vedea că există un număr maxim de 256 de simboluri pe care le-ar putea avea nevoie de coduri pentru. Aceasta include toate literele din alfabet - mari și mici - și apoi simboluri și numere, etc Atunci aici avem un numar magic de identificare un fișier Huffman-codat. În termen de un cod Huffman au de gând să aibă un anumit numar magic asociat cu antet. Acest lucru ar putea arata ca doar un numar magic aleator, dar dacă traduce de fapt în ASCII, atunci este de fapt vrăji Huff. Aici avem o struct pentru un fișier Huffman-codificat. Există toate aceste caracteristici asociate cu un fișier Huff. Atunci aici jos, avem un fișier antet pentru Huff, de aceea îl numim Huffeader în loc de a adăuga h în plus pentru că sună la fel, oricum. Drăguț. Avem un număr de magie asociate cu aceasta. Dacă e un real fișier Huff, că va fi numărul de deasupra, acest magic. Și apoi va avea o matrice. Deci, pentru fiecare simbol, din care există 256, se va lista ce frecvența acestor simboluri se află în fișierul Huff. Și apoi în cele din urmă, avem o sumă de control pentru frecvențele, care ar trebui să fie suma intre aceste frecvențe. Deci, asta e ceea ce o Huffeader este. Apoi, avem unele funcții care returnează următorul bit în dosarul Huff precum și scrie un pic la dosar Huff, iar apoi această funcție aici, hfclose, care se închide, de fapt fișierul Huff. Înainte, am fost de-a face cu drept fclose doar, dar atunci când aveți un fișier Huff, în loc să-l fclosing ceea ce de fapt de gând să faceți este să hfclose și hfopen-l. Acestea sunt funcții specifice fișierelor Huff că suntem de gând să se ocupe cu. Apoi aici am citit în antet și apoi scrie antetul. 

Doar prin citirea fișierului h.. Putem fel de a obține un sentiment de ceea ce un fișier Huff ar putea fi, ce caracteristici are, de fapt, fără a intra în huffile.c, pe care, dacă am arunca cu capul în, va fi un pic mai complex. Ea are toate fișierului I / O, aici de-a face cu pointeri. Aici vom vedea că atunci când ne numim hfread, de exemplu, este încă de-a face cu fread. Nu ne scăpa de aceste funcții în întregime, dar vă trimitem pe cei care urmează să fie luate în grijă de în interiorul fișierul Huff loc de a face totul singuri. Puteți simți liber pentru a scana prin acest lucru, dacă ești curios și du-te și coaja de stratul de spate un pic. 

Urmatorul fisier pe care am de gând să se uite la este tree.h. Înainte de a în Walkthrough alunecă am spus ne așteptăm la un nod Huffman și am făcut un nod typedef struct. Ne așteptăm ca acesta să aibă un simbol, o frecvență, apoi 2 stele nod. În acest caz, ceea ce facem noi este acest lucru este în esență același cu excepția loc de nod vom numi copaci. Avem o funcție care, atunci când apelați face copac se întoarce ai un pointer copac. Copii de la Speller, atunci când s-au a face un nod nou ai spus nod * nou cuvânt = malloc (sizeof) și lucruri de genul asta. Practic, mktree va fi a face cu asta pentru tine. În mod similar, atunci când doriți să eliminați un copac, Deci, asta e, în esență eliberarea copac atunci când ați terminat cu ea, în loc de în mod explicit apel gratuit de pe care, tu esti de fapt doar de gând să utilizeze funcția rmtree în cazul în care vă trece în pointer la acel pom și apoi tree.c va avea grija de asta pentru tine. 

Ne uităm în tree.c. Ne așteptăm ca aceleași funcții, cu excepția pentru a vedea punerea în aplicare, de asemenea. Așa cum ne-am așteptat, atunci când apelați mktree l mallocs marimea unui copac într-un pointer, initializeaza toate valorile la valoarea NULL, deci 0s sau valori nule, și apoi returnează pointer la acel copac pe care tocmai l-ați malloc'd pentru tine. Aici atunci când apelați scoateți copac mai întâi se asigură că nu ești dublu eliberarea. Se face-vă că aveți de fapt, un copac pe care doriți să o eliminați. Aici, deoarece un copac include, de asemenea copiii săi, ce face asta este recursiv solicită eliminarea copac de pe nodul din stânga a arborelui precum și dreptul de nod. Înainte de a elibereaza-mamă, de care are nevoie pentru a elibera copii, precum și. Mamă este, de asemenea, interschimbabile cu rădăcină. Mamă pentru prima dată, așa cum ar fi stră-stră-stră-stră-bunicul sau copac bunica, în primul rând trebuie să ne eliberăm de stabilire a nivelurilor primul. Deci, pentru a traversa partea de jos, cele libere, și apoi întoarce-te, gratis cele, etc Deci asta e copacul. 

Acum ne uităm la pădure. Pădurea este locul unde vă plasați toate copacii Huffman. Se spune că vom avea ceva numit un complot care conține un pointer la un copac, precum și un pointer la un complot numit următoare. Ce structura are acest tip de arata ca? Intr-un fel se spune de acolo. Chiar aici. O listă legate. Vedem că, atunci când avem un teren e ca o listă legată de parcele. O pădure este definită ca o listă legată de parcele, și astfel structura de pădure este de suntem doar de gând să aibă un pointer la primul nostru complot și că Parcela dispune de un copac în el sau, mai degrabă arată într-un copac și apoi indică următoarea parcelă, așa mai departe și așa mai departe. Pentru a face o pădure numim mkforest. Apoi, avem unele funcții destul de utile aici. Avem alege unde să treci într-o pădure, apoi valoarea returnata este un copac *, un pointer la un copac. Ce alegere va face este că va merge în pădure pe care îl indică spre apoi scoateți un copac cu cea mai mică frecvență de la acea pădure și să dea apoi pointer la acel copac. Odată ce ați alege suna, copacul nu va exista în pădure mai, dar valoarea returnată este pointer la acel copac. Apoi, aveți de plante. În cazul în care să treci într-un pointer la un copac care are o frecvență non-0, ce planta va face este că va lua pădure, ia copac, și a plantelor ca in interiorul copac din pădure. Aici avem rmforest. Similar pentru a elimina copac, care practic toate eliberat de arbori noastre pentru noi, eliminarea pădure vor totul gratis conținută în acea pădure. 

Dacă ne uităm în forest.c, vom aștepta să vedem cel puțin 1 comandă rmtree acolo, deoarece pentru a elibera memorie în pădure, dacă o pădure are copaci în ea, apoi în cele din urmă ai de gând să aibă de a elimina aceste copaci prea. Dacă ne uităm în forest.c, avem mkforest nostru, care este la fel ne asteptam. Am malloc lucruri. Am inițializa complot primul pădure ca NULL pentru ca este gol pentru a începe cu, apoi vom vedea alege, care returnează copac cu cea mai mică greutate, frecvența cea mai mică, si apoi scapa de acel nod special, care indică faptul că la pomul și alta, așa că ia că din lista legată de pădure. Și apoi aici, avem de plante, care introduce un copac în lista de legat. Ce pădure nu este frumos menține sortate pentru noi. Și apoi în cele din urmă, avem rmforest și, cum era de asteptat, avem rmtree chemat acolo. 

Privind la codul de distribuție până în prezent, a fost, probabil, huffile.c de departe cel mai greu de înțeles, întrucât celelalte fișiere înșiși au fost destul de simplu de urmat. Cu cunoștințele noastre de indicii și liste legate și astfel, noi am fost capabil să urmeze destul de bine. Dar tot ce avem nevoie pentru a face sigur că am înțeles pe deplin este h fișierele. pentru că aveți nevoie pentru a fi de asteptare acestor funcții, care se ocupă cu aceste valori de returnare, astfel încât asigurați-vă că ați înțeles pe deplin ce acțiuni urmează să fie efectuate ori de câte ori te sun una din aceste funcții. Dar, de fapt înțelegerea în interiorul acestuia nu este destul de necesar, deoarece avem cele. Fișiere oră. Avem 2 mai multe fișiere rămase în codul nostru de distributie. 

Să ne uităm la groapa de gunoi. Utilitară benă de comentariul său are aici un fișier Huffman-comprimat și apoi traduce si din haldele de toate de conținutul său out. Aici vom vedea că sună hfopen. Aceasta este un fel de oglindire a depune * intrare = fopen, si apoi treci la informații. E aproape identice, cu excepția în loc de un fișier * te trece într-o Huffile; în loc de fopen ce te trece în hfopen. Aici am citit în antet în primul rând, care este un fel de similar cu modul în care am citit în antetul pentru un fișier de tip bitmap. Ceea ce facem noi aici este de verificare pentru a vedea dacă antetul informații conține numărul magic dreapta care indică faptul că acesta este un real fișier Huff, atunci toate aceste controale pentru a se asigura că fișierul pe care am deschis un fișier este reală sau nu rățoiește. Ceea ce face este să emită frecvențele toate simbolurile pe care le putem vedea într-un terminal de într-un tabel grafic. Această parte va fi utilă. Ea are un pic și citește bit cu bit în biți variabilă și apoi se imprimă. Deci, dacă ar fi să sun la groapa de hth.bin, care este rezultatul unui fișier huffing folosind soluția de personal, mi-ar lua asta. Este scoate toate aceste personaje și apoi punerea frecvența la care ele apar. Dacă ne uităm, cele mai multe dintre ele sunt 0s, cu excepția pentru acest lucru: H, care apare de două ori, și atunci T, care apare o singură dată. Și apoi aici, avem mesajul real în 0s și 1s. Dacă ne uităm la hth.txt, care este probabil mesajul original care a fost rățoiește, ne așteptăm să vedem niște Hs și Ts acolo. Concret, ne așteptăm să vedem doar 1 T și 2 HS. Aici suntem în hth.txt. Ea într-adevăr are HTH. Incluse în acolo, desi nu-l putem vedea, este un personaj linie noua. Hth.bin fișier Huff este, de asemenea, codificarea caracter linie noua, de asemenea. Aici, pentru că știm că ordinea este HTH și apoi linie noua, putem vedea că, probabil, H este reprezentat de doar un singur 1 și apoi T este, probabil, 01 și apoi H următoarea este de 1, precum și și apoi vom avea o linie nouă indicate prin două 0s. Mișto. 

Și apoi în final, pentru că avem de a face cu mai multe. C și fișiere. H, vom avea un argument destul de complex pentru compilator, și așa mai departe aici avem un Makefile care face benă de tine. Dar, de fapt, trebuie să te duci despre a face dvs. de propriul dosar puff.c. Makefile de fapt, nu se ocupă cu efectuarea puff.c pentru tine. Plecăm că până la tine pentru a edita Makefile. Atunci când introduceți o comandă ca fac toate, de exemplu, se va face tot de pe ei pentru tine. Simțiți-vă liber să se uite la exemple de Makefile din PSET trecut precum și merge off de aceasta pentru a vedea cum s-ar putea fi capabil de a face fișierul Puff prin editarea acestui fișier Makefile. Asta e despre asta pentru codul noastre de distribuție. 

După ce am trecut prin asta, atunci aici e doar un alt memento de modul în care vom fi de-a face cu noduri Huffman. Noi nu vom fi numindu-le nodurile mai, vom fi numindu-le copaci în cazul în care vom reprezenta simbolul lor cu un char, frecvența lor, numarul de aparitii, cu un număr întreg. Suntem folosind ca pentru ca este mult mai precisă decât un flotor. Și apoi avem un alt indicatorul la stânga copilului, precum și dreptul de copil. O pădure, așa cum am văzut, este doar o listă legat de copaci. În cele din urmă, atunci când suntem construirea dosarul nostru Huff, vrem pădure noastră să conțină doar 1 copac - 1 copac, 1 radacina cu copii multiple. Mai devreme cand am fost a face doar copacii noastre Huffman, am inceput prin plasarea toate nodurile pe ecran noastră și spunând vom avea aceste noduri, în cele din urmă ei vor fi frunze, iar acest lucru este simbolul lor, acest lucru este frecvența lor. În pădure noastră, dacă avem doar 3 litere, asta e o pădure de copaci 3. Și apoi ca mergem mai departe, atunci când am adăugat-mamă în primul rând, ne-am facut-o pădure de 2 copaci. Am eliminat 2 din acei copii din pădure noastră și apoi a înlocuit-o cu un nod parinte care a avut cele 2 noduri ca și copii. Și apoi în cele din urmă, ultimul pas noastră cu a face exemplul nostru cu Ca, B, și C ar fi de a face-mamă finală, și așa mai apoi că ar aduce numărul nostru total de pomi în pădure la 1. Are toată lumea vedea cum începe cu mai mulți arbori în pădure dvs. și se încheie cu 1? Bine. Mișto. 

Ce trebuie să facem pentru Puff? Ceea ce trebuie să faceți este să se asigure că, ca întotdeauna, ei ne dau dreptul de tipul de intrare astfel încât să putem rula de fapt programul. În acest caz, ei vor să fie oferindu-ne după prima lor linie de comandă argumentul 2 mai mult: fișierul pe care ne-o dorim pentru a decomprima și de ieșire a fișierului decomprimat. Dar odată ce ne asigurăm că ne-au trecut în dreptul de suma de valori, dorim să ne asigurăm că este un fișier de intrare Huff sau nu. Și apoi, odată ce vom garanta faptul că este un fișier Huff, apoi vrem să construim copacul nostru, construi copac, astfel încât se potrivește copac care persoana care a trimis mesajul construit. Apoi, după ce ne-am construit arborele, atunci putem face cu, 0s și 1s că au trecut în urmați de-a lungul celor copacul nostru, deoarece este identic, și să scrie apoi că mesajul, interpreta biții înapoi în caractere. Și apoi, la sfârșit, deoarece avem de-a face cu pointeri aici, vrem să ne asigurăm că nu avem nici o scurgere de memorie și că avem totul gratuit. 

Asigurarea de utilizare corectă este pălărie vechi pentru noi până acum. Ne ia într-o intrare, care va fi numele fișierului pentru a sufla, și apoi vom specifica o iesire, astfel încât numele fișierului de ieșire pentru umflat, care va fi fișierul text. Asta e de utilizare. Și acum vrem să ne asigurăm că intrarea este rățoiește sau nu. Gândindu-mă, a fost ceva în codul de distribuție, care ne-ar putea ajuta cu înțelegerea dacă un fișier este rățoiește sau nu? Nu a fost de informații în huffile.c despre Huffeader. Stim ca fiecare fișier are un Huff Huffeader asociat cu acesta, cu un număr de magie precum și o serie de frecvențe pentru fiecare simbol , precum și o sumă de control. Știm asta, dar am luat, de asemenea, o privire la dump.c, în care a fost citit într-un fișier Huff. Și așa să faci asta, a trebuit să verifice dacă într-adevăr a fost rățoiește sau nu. Deci, poate că am putea folosi dump.c ca o structură de puff.c. nostru Înapoi la PSET 4 când am avut copy.c fișierul pe care copiat în triplete RGB și am interpretat că, pentru roman sau film polițist și Redimensionare, În mod similar, ceea ce ai putea face este doar să rulați comanda ca cp dump.c puff.c și de a folosi o parte din codul de acolo. Cu toate acestea, ea nu va fi la fel de simplă a unui proces de pentru traducerea dump.c dvs. în puff.c, dar cel puțin te dă pe undeva pentru a începe cu privire la modul pentru a se asigura că intrarea este de fapt rățoiește sau nu precum și alte câteva lucruri. Ne-am asigurat de utilizare corectă și a asigurat că de intrare este rățoiește. De fiecare dată când ne-am făcut că ne-am făcut verificarea noastra de eroare corespunzătoare, astfel returnarea și renunti funcție dacă apare un eșec, în cazul în care există o problemă. 

Acum, ceea ce dorim să facem este construirea copac real. Dacă ne uităm în Pădurea, există 2 funcții principale că am de gând să doriți să devină foarte familiarizat cu. Nu e planta funcție booleană care plantele un copac non-0 frecvență în interiorul pădurii nostru. Și deci nu te treci intr-un pointer la o pădure și un pointer la un copac. Intrebare rapida: Câte pădurile vei avea atunci când veți construi un copac Huffman? Padurea noastra este ca panza nostru, nu? Deci, vom avea doar o pădure, dar vom avea mai mulți arbori. Deci, înainte de a apela plantelor, probabil ai de gând să doriți să vă padure. Există o comandă pentru că, dacă te uiți în forest.h privind modul în care puteți face o pădure. Puteți planta un copac. Știm cum să faci asta. Și apoi puteți alege, de asemenea, un copac din pădure, eliminarea unui copac cu cel mai mic greutate și oferindu-vă pointer la asta. Gândindu-mă la momentul făceam exemple noi înșine, cand am fost l întocmirea, pur și simplu adăugat doar link-urile. Dar aici în loc de a adăuga doar link-uri, cred că de ea mai mult ca esti eliminarea acestor 2 din noduri și apoi înlocuirea acesteia cu o alta. Pentru a exprima faptul că, în ceea ce privește alegerea și de răsaduri, te cules 2 copaci și apoi plantarea alt copac care are acele 2 copaci care ați ales ca si copii. Pentru a construi arborele Huffman, puteți citi în simbolurile și frecvențele în ordine deoarece oferă Huffeader că, pentru a vă, vă oferă o gamă de frecvențe. Astfel încât să puteți merge mai departe și să ignore pur și simplu nimic cu 0 în ea pentru ca nu vrem 256 frunze la sfârșitul anului acesta. Dorim doar numărul de frunze, care sunt de caractere care sunt utilizate efectiv în fișierul. Puteți citi în aceste simboluri, și fiecare dintre aceste simboluri care au non-0 frecvențe, cei care vor fi copaci. Ce puteți face este de fiecare dată când citesc în frecvență un simbol non-0, puteți planta acel copac în pădure. După ce planta copaci în pădure, vă puteți alătura acestor copaci ca frații, așa merge înapoi la plantarea și în cazul în care alegeți 2 și apoi a plantelor 1, în cazul în care o instalație care le este mamă a doi copii pe care i-ați ales. Deci, atunci rezultatul final va fi un singur copac în pădure ta. Asta e modul în care vă construiți arborele. 

Există mai multe lucruri care ar putea merge greșit aici pentru că avem de-a face cu a face copaci noi și care se ocupă cu pointeri si lucruri de genul asta. Înainte de a atunci când am de-a face cu pointeri, ori de câte ori am malloc'd am vrut să ne asigurăm că nu ne-a returnat o valoare pointer NULL. Deci, la mai multe etape în cadrul acestui proces se vor fi mai multe cazuri în cazul în care programul ar putea eșua. Ce vrei să faci este doriți să vă asigurați că ați ocupe de aceste erori, și în spec. se spune să se ocupe de ele grațios, asa ca imprima un mesaj de la utilizatorul spunându-le de ce trebuie sa renunte la programul si apoi iesi cu promptitudine. Pentru a face acest lucru eroare de manipulare, amintiți-vă că doriți să-l verificați de fiecare dată că ar putea exista un eșec. De fiecare data cand faci un pointer nou doriți să vă asigurați că este de succes. Înainte de a ceea ce am folosit pentru a face este de a face un pointer nou și malloc-l, si atunci ne-ar verifica dacă această indicatorul este NULL. Deci nu vor fi unele cazuri în care tocmai ați putea face asta, dar, uneori, esti de asteptare de fapt, o funcție și în această funcție, că e cel care face mallocing. În acest caz, dacă ne uităm înapoi la anumite funcții în cadrul codului, unele dintre ele sunt funcții booleene. În cazul în abstract, în cazul în care avem o functie booleana numit foo, practic, putem presupune că, în afară de a face tot ce face foo, din moment ce este o funcție booleană, se returneaza true sau false - true în caz de succes, dacă nu false. Așa că vrem să verifice dacă valoarea returnată de foo este adevărată sau falsă. Dacă e fals, ceea ce înseamnă că am de gând să doriți să imprimați un fel de mesaj apoi părăsiți programul. Ceea ce vrem să facem este să verificați valoarea returnată de foo. Dacă foo returneaza false, atunci știm că am întâlnit un fel de eroare și avem nevoie pentru a iesi programul nostru. O modalitate de a face acest lucru este să aibă o condiție în cazul în care funcția în sine este starea dumneavoastră. Spune foo ia în x. Putem avea, ca o condiție în cazul în care (foo (x)). Practic, asta înseamnă că dacă la sfârșitul anului de executare foo-l returneaza true, atunci putem face acest lucru, deoarece funcția trebuie să evalueze foo în scopul de a evalua starea întreg. Deci asta e modul în care puteți face ceva în cazul în care funcția returnează adevărat și este de succes. Dar când ești verificarea erorilor, doriți doar să renunțe dacă funcția dumneavoastră returnează false. Ce ai putea face este sa adaugi doar un == fals sau doar adaugă o bubuitură în fața sa si apoi ai if (! foo). În cadrul acestui organism de această condiție le-ar fi toate de tratare a erorilor, asa ca, "Nu am putut crea acest copac" și apoi să se întoarcă 1 sau ceva de genul asta. Ceea ce face, însă, este că, chiar dacă foo revenit false - Spune foo returneaza true. Apoi, nu trebuie să sun din nou foo. Asta e o concepție greșită comună. Pentru că a fost în stare ta, este deja evaluate, astfel încât aveți deja rezultatul dacă utilizați face copac sau ceva de genul asta sau ale plantelor sau de preluare sau ceva de genul. Ea are deja acea valoare. E deja executate. Deci, este util să folosiți funcții booleene ca condiție pentru că dacă aveți sau nu executa de fapt, corpul buclei, , execută funcția oricum. 

Două noastră de a Ultimul pas este scris mesajul la dosar. După ce vom construi arborele Huffman, apoi scris mesajul la dosar este destul de simplă. E destul de simplu acum să urmeze doar 0s și 1s. Și astfel, prin convenție, știm că într-un copac Huffman a 0s indica plecat și indică dreptul de 1s. Deci, dacă ați citit în bit cu bit, de fiecare dată când obțineți un 0 veți urmări ramura stânga, și apoi de fiecare dată când citesc în un 1 ai de gând să urmeze ramura dreapta. Și apoi ai de gând să continue până când te-a lovit o frunză deoarece frunzele vor fi la sfârșitul sucursale. Cum putem spune dacă ne-am lovit-o frunză sau nu? Am spus-o înainte. [Elev] În cazul în care indicii sunt nule. Da >>. Noi putem spune dacă ne-am lovit o frunză în cazul în care indicii de copaci, atât stânga și dreapta sunt nule. Eveniment. Știm că vrem să citesc în bit cu bit în fișierul nostru Huff. Așa cum am văzut înainte în dump.c, ceea ce au făcut ei este citit în bit cu bit în dosarul Huff si doar tipărite ce acei biți au fost. Noi nu suntem de gând să faci asta. Vom face ceva care este un pic mai complex. Dar ceea ce putem face este să putem avea că pic de cod care citeste in pentru a biți. Aici avem biti reprezentand putin curent pe care suntem pe. Aceasta are grija de iterarea tuturor biți din fișierul până când te-a lovit la sfârșitul fișierului. Bazat pe faptul că, atunci ai de gând să doriți să aveți un fel de iterator pentru a traversa copac. Și apoi, dacă pe bit este 0 sau 1, ai de gând să doriți să mutați, fie că iterator la stânga sau mutați-l la dreapta tot drumul până când a lovit o frunză, astfel încât tot drumul până la acel nod pe care esti pe nu indică nici mai noduri. De ce putem face acest lucru cu un fișier Huffman, dar nu codul Morse? Pentru că în codul Morse e un pic de ambiguitate. Am putea fi ca, Oh, așteptați, ne-am lovit-o scrisoare de-a lungul drum, așa că poate aceasta este scrisoarea noastră, întrucât în ​​cazul în care am continuat doar un pic mai mult, atunci ne-ar fi lovit o altă scrisoare. Dar asta nu se va întâmpla în codificarea Huffman, astfel încât să putem fi siguri că singurul mod în care vom lovi un caracter este în cazul în care copiii nod stânga și dreapta sunt nule. 

În cele din urmă, dorim să eliberăm toată memoria noastră. Ne dorim atât de aproape de fișier Huff pe care le-am fost de-a face cu precum și eliminarea ca toate copacii din pădure noastră. Bazat pe punerea în aplicare tau, esti, probabil, de gând să doriți să apelați eliminați pădure în loc de fapt, trece prin toate copaci singuri. Dar, dacă ați făcut orice copaci temporare, veți dori să eliberați asta. Tu știi cel mai bine codul, astfel încât să știi unde te alocare de memorie. Și așa, dacă te duci în, începeți prin chiar F'ing de control pentru malloc, ori de câte ori văd malloc și asigurându-vă că vă elibera toate că dar apoi trece printr-cod, înțelegerea în cazul în care s-ar putea s-au alocat de memorie. De obicei, s-ar putea spune doar, "La sfârșitul unui fișier Mă duc să elimine pădure în pădure mea," atât de clar încât practic de memorie, fără ca, "Si apoi am, de asemenea, de gând să închidă fișierul și apoi programul meu este de gând să renunțe." Dar este faptul că singura dată când se închide programul tău? Nu, pentru că, uneori, nu ar fi putut fi o eroare care sa întâmplat. Poate nu am putut deschide un fișier sau nu am putut face un alt copac sau un fel de eroare sa întâmplat în procesul de alocare de memorie și așa sa întors NULL. O eroare a avut loc și apoi ne-am întors și ieși. Deci, apoi doriți să vă asigurați că în orice moment posibil ca programul dvs. poate renunta, doriți să eliberați toate memoria ta acolo. Nu este doar de gând să fie la sfârșitul foarte de funcția principală pe care ai renunțat codul. Vrei să te uiți înapoi la fiecare instanță a codului potențial s-ar putea întoarce prematur și apoi liber, indiferent de memorie are sens. Spuneți că ați avut chemat face de pădure și care a returnat false. Atunci probabil nu va fi nevoie pentru a elimina padure pentru că nu aveți încă o pădure. Dar la fiecare punct din cod unde s-ar putea întoarce prematur doriți să vă asigurați că ați elibera orice memorie este posibil. 

Așa că atunci când avem de a face cu eliberarea de memorie și având scurgeri potențiale, vrem să folosească nu numai judecata noastră și logica noastră dar folosesc, de asemenea, Valgrind pentru a determina dacă ne-am eliberat toate memorie în mod corect sau nu. Puteți rula fie pe Puff Valgrind și apoi va trebui să treci de asemenea, sa numărul corect de argumente de linie de comandă pentru a Valgrind. Puteți rula asta, dar rezultatul este un pic criptic. Am ajuns un pic folosit pentru a-l cu Speller, dar avem nevoie de încă un pic de ajutor mai mult, asa apoi rulează cu câteva steaguri mai mult, cum ar fi scurgeri de check = complet, care va da, probabil, ne unii de ieșire de mai mult ajutor pe Valgrind. 

Apoi, un alt sfat util atunci când sunteți depanare este comanda dif. Puteți accesa punerea în aplicare personalului de Huff, executați pe un fișier text, și transmite apoi într-un fișier binar, un binar Huff fișier, să fie specifice. Apoi, dacă aveți o puf ta cu privire la acest fisier binar, atunci în mod ideal, fișierul text scoase este de gând să fie identice la cel original pe care l-ai trecut inch Aici eu sunt, folosind hth.txt ca exemplu, si asta e cel vorbit despre în spec. ta. Asta e literalmente doar HTH și apoi o linie nouă. Dar cu siguranta se simt liber și vă sunt cu siguranta încurajați să folosească exemple mai lungi pentru fișierul text. 

Puteți lua chiar și o șansă la comprimarea poate și apoi decomprima unele dintre fișierele pe care le-ați utilizat în Speller ca Război și pace sau Jane Austen sau ceva de genul asta - care ar fi un fel de rece - sau Austin Powers, un fel de a face cu fișiere mai mari, deoarece nu ne-ar veni să-l daca am folosit instrumentul următoarea aici, ls-l. Suntem obișnuiți să ls, care enumeră, practic toate componentele în directorul nostru curent. Trece în pavilion-l afișează, de fapt dimensiunea acestor fișiere. Dacă te duci prin spec. PSET, de fapt tu plimba prin crearea de fișier binar, huffing de el, și veți vedea că pentru fisiere foarte mici costul spațiului de comprimare ea și traducerea tuturor informațiilor a tuturor frecvențelor și lucruri de genul asta depășește beneficiul real de a comprima fișierul în primul rând. Dar dacă îl executați pe unele fișiere de text mai lungi, atunci s-ar putea vedea că începe pentru a obține niște beneficii în comprimarea acestor fișiere. 

Și apoi în cele din urmă, avem vechiul nostru prieten GDB, care este cu siguranta va veni la îndemână prea. 

Nu avem întrebări pe copaci Huff sau procesul, probabil, de a face copaci sau orice alte întrebări cu privire Puff Huff'n? Bine. Voi rămâne în jurul valorii de un pic. 

Mulțumesc, tuturor. Acest lucru a fost Walkthrough 6. Și noroc. 

[CS50.TV]