[Powered by Google Translate] [Walkthrough - Set Problem 6]
[Zamyla Chan - Universiteti i Harvardit]
[Kjo është CS50. - CS50.TV]
>> Hello, të gjithë, dhe të mirëpritur të walkthrough 6: pudre Huff'n.
Në Puff Huff'n ajo që ne po bëjmë do të jetë që kanë të bëjnë me një file kompresuar Huffman
dhe pastaj puffing atë back up, kështu që decompressing atë,
kështu që ne mund të përkthehet nga 0s dhe 1s që përdoruesi na dërgon
dhe kthyer atë përsëri në tekstin origjinal.
Pset 6 do të jetë shumë i ftohtë, sepse ju do të jeni për të parë disa nga mjetet
që ju të përdorur në pset 4 dhe 5 pset dhe lloji i kombinuar ato në 1 koncept mjaft i zoti
kur ju vijnë për të menduar për këtë.
>> Gjithashtu, ndoshta, pset 4 dhe 5 ishin më psets sfiduese që kemi pasur për të ofruar.
Pra, nga tani, ne kemi këtë pset 1 më shumë në C,
dhe pastaj, pasi që ne jemi në të programimit web.
Pra, përgëzoj veten për marrjen mbi kodrinë vështira në CS50.
>> Lëvizur më për Puff Huff'n, veglave tona për këtë pset do të jenë pemët Huffman,
kështu kuptuar jo vetëm si punë pemë binare, por edhe konkretisht pemë Huffman,
se si ata janë ndërtuar.
Dhe pastaj ne do të kemi një shumë të kodit të shpërndarjes në këtë pset,
dhe ne do të vijnë për të parë se në fakt disa prej kodit
ne nuk mund të jetë në gjendje për të kuptuar plotësisht ende,
dhe kështu ata do të jenë. fotografi c, por pastaj shoqëruese të tyre. fotografi h
do të na japë të mjaftueshme kuptim që ne kemi nevojë në mënyrë që ne e dimë se si ato funksione punojnë
ose të paktën atë që ata janë të dashur për të bërë - inputet dhe rezultatet e tyre -
edhe në qoftë se ne nuk e dimë se çfarë po ndodh në kutinë e zezë
ose nuk e kuptojnë se çfarë po ndodh në kutinë e zezë brenda.
Dhe pastaj në fund, si zakonisht, kemi të bëjmë me strukturat e të dhënave të reja,
lloje të veçanta të nyjave që tregojnë për gjëra të caktuara,
dhe kështu që këtu ka një stilolaps dhe letër, jo vetëm për procesin e projektimit
dhe kur ju jeni duke u përpjekur të kuptoj se si pset juaj duhet të punojnë
por edhe gjatë debugging.
Ju mund të keni gdb së bashku me stilolaps dhe letër tuaj, ndërsa ju të merrni poshtë atë që vlerat janë,
ku shigjetat tuaja janë treguar, dhe gjëra të tilla si se.
>> Së pari le të shohim në pemë Huffman.
Pemë pemë binare janë Huffman, do të thotë që çdo nyje ka vetëm 2 fëmijë.
Në pemë Huffman karakteristikë është se vlerat më të shpeshta
janë të përfaqësuara nga BITS fewest.
Ne pamë në shembujt e ligjërimit kodin Morse, cili lloj i konsoliduar disa letra.
Nëse ju jeni duke u përpjekur për të përkthyer një A ose nje E, për shembull,
ju jeni përkthimin që shpesh, kështu që në vend që të përdorin seri të plotë të bit
ndarë për atë lloj usual të dhënave, ju ngjesh atë poshtë për pak,
dhe pastaj ato letra që janë të përfaqësuara më pak shpesh janë të përfaqësuara me copa të gjata
sepse ju mund të përballojë se kur ju peshojnë nga frekuencat që ato letra shfaqen.
Ne kemi të njëjtën ide këtu në pemë Huffman
ku ne jemi duke bërë një zinxhir, një lloj rrugën për të shkuar në karaktere të caktuara.
Dhe pastaj karaktere që kanë frekuencën më
do të përfaqësohet me bit fewest.
>> Mënyrë që ju të ndërtuar një pemë Huffman
është duke vendosur të gjitha karakteret që shfaqen në tekst
dhe llogaritjen frekuencën e tyre, sa shpesh ato shfaqen.
Kjo mund të jetë ose një akuzë e sa herë ato letra shfaqet
ose ndoshta një përqindje e nga të gjitha personazhet se sa secili prej tyre duket.
Dhe kështu ajo që ju bëni është një herë ju keni të gjithë se nga planifikuara,
atëherë ju shikoni për 2 frekuenca më të ulëta dhe më pas të bashkohen ato si vëllezërit e motrat
ku pastaj nyjen prind ka një frekuencë që është shuma e 2 fëmijëve të saj.
Dhe pastaj ju nga Konventa thonë se nyja majtë,
ju do të ndiqni se duke ndjekur degën 0,
dhe pastaj nyjen rightmost është 1 degë.
Siç e pamë në kodin Morse, një Gotcha ishte se në qoftë se keni pasur vetëm një bip bip dhe
ai ishte i paqartë.
Ajo mund të jetë ose 1 shkronja ose ajo mund të jetë një sekuencë prej 2 shkronja.
Dhe kështu ajo Huffman pemë bën është sepse nga natyra e personazheve
ose përfundimtare tona karaktere aktuale duke qenë nyje e fundit në degën e -
ne i referohemi atyre si gjethe - me anë të se nuk mund të ketë ndonjë dykuptimësi
në terma të cilat letra ju jeni duke u përpjekur për të kodifikuar me serinë e bit
sepse askund përgjatë bit që përfaqësojnë 1 letër
do të hasni një tjetër letër të tërë, dhe nuk do të ketë asnjë konfuzion atje.
Por ne do të shkojnë në shembujt se ju djema mund të vërtetë shohim se
në vend që të na thënë se vetëm kjo është e vërtetë.
>> Le të shikojmë në një shembull të thjeshtë të një peme Huffman.
Unë kam një varg këtu që është 12 karaktere i gjatë.
Unë kam 4 Si, 6 BS, dhe 2 Cs.
Hapi im i parë do të jetë për të numëruar.
Sa herë ka një duket? Duket se 4 herë në vargun.
B shfaqet 6 herë, dhe C duket 2 herë.
Natyrisht, unë jam duke shkuar për të thonë se unë jam duke përdorur B më shpesh,
kështu që unë dua për të përfaqësuar B me numrin fewest të bit, numri i paktët 0s dhe 1s.
Dhe atëherë unë jam gjithashtu do të presin C të kërkojë shumën më të madhe të 0s dhe 1s si.
Të parë se çfarë kam bërë unë këtu është vendosur ato në ngjitje qëllim në drejtim të frekuencës.
Ne e shohim se C dhe A, ata janë frekuenca 2 tonë më të ulët.
Ne të krijojë një nyje prind, dhe se nyja prind nuk ka një letër lidhur me të,
por ajo ka një frekuencë, e cila është shuma.
Shuma bëhet 2 + 4, i cili është 6.
Atëherë ne ndjekim degën e majtë.
Nëse do të ishim në atë nyje 6, atëherë ne do të ndjekim për të marrë në 0 C
dhe pastaj të merrni 1 në A.
Deri tani ne kemi 2 nyje.
Ne kemi vlerën 6 dhe pastaj ne gjithashtu kemi një nyje me vlerë 6.
Dhe kështu ata 2 nuk janë vetëm 2 të ulët, por edhe vetëm 2 që janë lënë,
kështu që ne të bashkohen ato nga një prind, me shuma të qenit 12.
Pra, këtu kemi Huffman pemë tonë
ku mund të merrni në B, që do të jetë vetëm pak 1
dhe pastaj të shkoj në një ne do të kemi 01 dhe pastaj C ka 00.
Kështu që këtu ne shohim se në thelb ne jemi duke përfaqësuar këto chars me ose 1 ose 2 copa
ku B, parashikoi si, ka më së paku.
Dhe pastaj ne kishim pritur C të ketë më, por që nga ajo është e tillë një pemë e vogël Huffman,
atëherë A është përfaqësuar edhe nga 2 copa në krahasim me diku në mes.
>> Vetëm për të shkuar mbi një tjetër shembull të thjeshtë të pemës Huffman,
thonë se ju keni string "Hello".
Çfarë ju bëni është e parë që ju do të thonë se sa herë do të paraqitet në këtë H?
H shfaqet herë dhe pastaj e duket një herë dhe pastaj kemi l paraqitet dy herë
dhe o shfaqeshin herë.
Dhe kështu, atëherë ne presim që letra të përfaqësohet me numrin më të vogël të bit?
[Student] l. L. >> Po. l është e drejtë.
Ne presim l të përfaqësuara nga numri pak e bit
sepse l është përdorur më shumë në vargun "Hello".
Ajo që unë jam duke shkuar për të bërë tani është të nxjerrë jashtë këto nyje.
Kam 1, e cila është H, dhe pastaj një tjetër 1, e cila është E, dhe pastaj një 1, e cila është O -
tani unë jam vënë ato në mënyrë - dhe pastaj 2, e cila është l.
Atëherë unë them rruga që unë ndërtuar një pemë Huffman është për të gjetur 2 nyjet me frekuenca më pak
dhe t'i bëjë ata vëllezërit e motrat, duke krijuar një nyje prind.
Këtu ne kemi 3 nyjet me frekuencë të ulët. Ata janë të gjithë 1.
Pra, këtu kemi të zgjidhni një ne jemi duke shkuar për të lidhur së pari.
Le të thonë se unë zgjedh H dhe e.
Shuma e 1 + 1 është 2, por kjo nyje nuk ka një letër lidhur me të.
Ajo thjesht e mban vlerën.
Tani ne shikojmë në 2 frekuenca e ardhshme të ulët.
Kjo është 2 dhe 1. Kjo mund të jetë ose nga ato 2, por unë jam duke shkuar për të zgjedhur këtë.
Shuma është 3.
Dhe pastaj në fund, unë vetëm 2 majtas, në mënyrë që pastaj të bëhet 5.
Atëherë këtu, siç pritet, në qoftë se unë të plotësoni në encoding për atë,
1s janë gjithmonë dega e drejtë dhe 0s janë një majtë.
Pastaj kemi l përfaqësuar nga vetëm pak 1 dhe pastaj o nga 2
dhe pastaj e nga 2 dhe pastaj H bie poshtë për 3 copa.
Kështu që ju mund të transmetojë këtë mesazh "Hello" në vend të vërtetë duke përdorur karakteret
vetëm me 0s dhe 1s.
Megjithatë, mbani mend se në disa raste kemi pasur lidhje me frekuencën tonë.
Ne mund të kemi bashkuar ose H dhe o Së pari ndoshta.
Ose pastaj më vonë, kur ne kishim l përfaqësuar nga 2
si dhe u bashkua me një përfaqësohet nga 2, ne mund të kemi lidhur ose një.
>> Dhe kështu që kur ju të dërgoni 0s dhe 1s, që në fakt nuk garanton
se përfituesi mund plotësisht të lexuar mesazhin tuaj të drejtën off bat
sepse ata nuk mund të dinë se cilat vendimi që keni bërë.
Pra, kur ne jemi që kanë të bëjnë me compression Huffman,
disi ne kemi për të të treguar marrësit e mesazhit tonë se si ne kemi vendosur -
Ata duhet të dinë disa lloj informacioni shtesë
Përveç mesazhit të ngjeshur.
Ata kanë nevojë për të kuptuar se çfarë në të vërtetë duket si pema,
se si ne fakt e bëri ato vendime.
>> Këtu ne ishim vetëm duke bërë shembuj bazuar në numërimin aktuale,
por ndonjëherë ju gjithashtu mund të ketë një pemë Huffman
bazuar në frekuencën në të cilën letra shfaqet, dhe kjo është procesi saktë të njëjtën.
Këtu unë jam shprehur atë në aspektin e përqindjeve apo një pjesë,
dhe kështu që këtu gjë e saktë të njëjtën.
I gjeni 2 të ulët, të përmbledhur ato, 2 e ardhshëm më të ulët, të përmbledhur ato,
deri sa unë kam një pemë të plotë.
Edhe pse ne mund të bëjmë atë Ose mënyrë, kur ne jemi që kanë të bëjnë me përqindje,
që do të thotë ne jemi të ndarë gjëra dhe që kanë të bëjnë me decimale ose më mirë gjithandej
në qoftë se ne jemi duke menduar për të dhënat e strukturave të një kokë.
Çfarë ne dimë rreth gjithandej?
Çfarë është një problem i zakonshëm, kur ne jemi që kanë të bëjnë me të gjithandej?
[Student] aritmetike pasakta. Po >>. Pasaktësi.
Për shkak të jo saktësi pikë lundrues, për këtë pset në mënyrë që ne të sigurt
se ne nuk do ta humbasin asnjë vlerat, atëherë ne jemi në të vërtetë do të kanë të bëjnë me numërimin.
Pra, nëse ju keni qenë të mendojnë për një nyje Huffman, nëse ju shikoni prapa në strukturën këtu,
në qoftë se ju shikoni në ato gjelbër ka një frekuencë lidhur me të
si dhe ajo tregon në një nyje në të majtë të saj, si dhe një nyje në të djathtë të tij.
Dhe pastaj ato të kuqe ka gjithashtu kanë një karakter të lidhur me to.
Ne nuk jemi duke shkuar për të bërë ato të veçanta për prindërit dhe pastaj nyjet e fundit,
të cilat ne i referohemi si gjethe, por ata do të ketë vetëm vlera NULL.
Për çdo nyje ne do të kemi një karakter, simboli që kjo nyje përfaqëson,
pastaj një frekuencë, si dhe një tregues për fëmijën e saj të majtë, si dhe fëmijën e saj të drejtë.
Gjethet, të cilat janë në fund shumë, gjithashtu do të ketë pointers nyjen
në të majtë të tyre dhe në të djathtë të tyre, por që këto vlera nuk janë treguar në nyjet aktuale,
çfarë do të jetë vlera e tyre? >> [Student] NULL. NULL. >> Saktësisht.
Ja një shembull se si ju mund të përfaqësojë frekuencën në trap,
por ne jemi duke shkuar për të merret me atë me integers,
kështu që të gjitha që kam bërë është të ndryshojë llojin e të dhënave atje.
>> Le të shkojnë për të pak më shumë se një shembull komplekse.
Por tani që ne kemi bërë ato të thjeshta, kjo është vetëm procesi i njëjtë.
Ju gjeni 2 frekuenca më të ulëta, të përmbledhur frekuencat
dhe kjo është frekuenca e re e nyjeve tuaj mëmë,
e cila më pas tregon në të majtë të saj me degën 0 dhe të drejtën me degën 1.
Në qoftë se ne kemi vargun "Kjo është CS50," atëherë ne numërimin e sa herë është përmendur T,
h përmendur, i, s, c, 5, 0.
Atëherë çfarë kam bërë këtu është me nyje të kuqe unë vetëm mbjellë,
Kam thënë unë jam duke shkuar të ketë këto karaktere përfundimisht në fund të pemës sime.
Ata do të jenë të gjithë gjethe.
Atëherë çfarë kam bërë unë është renditur ato sipas frekuencës në ngjitje qëllim,
dhe ky fakt është mënyra se kodi pset e bën atë
është ajo lloj atë me frekuencë dhe pastaj alfabetikisht.
Pra, ajo ka numrat e parë dhe pastaj alfabetikisht nga frekuenca.
Atëherë çfarë do të bëj është që unë do të gjeni 2 të ulët. Kjo është 0 dhe 5.
Unë do të përmbledhur ata, dhe kjo është 2. Atëherë unë do të vazhdojë, të gjejnë tjetër 2 të ulët.
Ata janë 1s dy, dhe pastaj ata të bëhen 2 si.
Tani unë e di se hapi im i ardhshëm do të jetë bashkimi me numrin më të vogël,
cila është T, 1, dhe pastaj duke zgjedhur një nga nyjet që ka 2 si frekuencë.
Pra, këtu kemi 3 opsione.
Ajo që unë jam duke shkuar për të bërë për rrëshqitje është vetëm vizualisht korrigjoj ato për ju
kështu që ju mund të shihni se si unë jam duke ndërtuar atë.
Çfarë kodi dhe kodin tuaj të shpërndarjes do të bëjë do të bashkohen me njëri-T
me nyje 0 dhe 5.
Kështu, pra, se shuma në 3, dhe pastaj ne vazhdojmë procesin.
E 2 dhe 2 tani janë më të ulët, në mënyrë që pastaj ata shuma deri në 4.
Gjithkush pas deri tani? Rregull.
Pastaj pas kësaj ne kemi 3 dhe 3 që kanë nevojë për të shtuar deri,
kështu përsëri unë jam vetëm kalimi atë mënyrë që ju mund të shihni me sy në mënyrë që ajo nuk ka marrë shumë të çrregullt.
Pastaj ne kemi një 6, dhe pastaj hapi ynë përfundimtar është tani që ne kemi vetëm 2 nyje
Ne përmbledhur ato për të bërë rrënja e pemës tonë, e cila është 10.
Dhe numri 10 ka kuptim, sepse çdo nyje të përfaqësuara,
vlera e tyre, numri i tyre frekuenca, ishte se sa herë ata u shfaq në varg,
dhe pastaj ne kemi 5 karaktere në vargun tonë, në mënyrë që e bën kuptim.
Nëse ne shikojmë deri në mënyrën se si ne fakt do shifroj atë,
siç pritet, unë dhe s, e cila shfaqet më shpesh
janë të përfaqësuara nga numrin fewest e bit.
>> Të jenë të kujdesshëm këtu.
Në pemë Huffman rasti të vërtetë rëndësi.
Një S uppercase është i ndryshëm se sa një s Fjala.
Nëse do të kishim "Kjo është CS50" me shkronja të mëdha, atëherë s vogla do të shfaqet vetëm dy herë,
do të jetë një nyje me 2 si vlerën e saj, dhe pastaj të uppercase S do të jetë vetëm një herë.
Pra, atëherë pema juaj do të ndryshojë strukturat sepse ju në fakt kanë një fletë shtesë këtu.
Por shuma do të jetë ende 10.
Kjo është ajo që ne jemi në të vërtetë do të jetë quajtur checksum,
shtimi i të gjitha akuzave.
>> Tani që ne kemi mbuluar pemë Huffman, ne mund të zhyten në Puff Huff'n, pset.
Ne jemi duke shkuar për të filluar me një pjesë të pyetjeve,
dhe kjo do të merrni ju për të mësuar me pemë binare dhe si të veprojë rreth se:
nyjet vizatim, krijimin e vet struct tuaj typedef për një nyje,
dhe duke parë se si ju mund të futni në një pemë binare, një që është renditura,
traversing atë, dhe gjëra të tilla si kjo.
Kjo njohuri është padyshim do të ju ndihmojë kur ju pikiatë në pjesën pudre Huff'n
i pset.
Në edicionin e standardit të pset, detyra juaj është për të zbatuar pudre,
dhe në versionin hacker detyra juaj është për të zbatuar Huff.
Çfarë Huff nuk është ajo merr tekstin dhe pastaj ajo përkthen atë në të 0s dhe 1s,
kështu proces që ne e bëmë më sipër, ku ne numërohen frekuencat
dhe pastaj e bëri pemë dhe pastaj tha: "Si mund të shkoj T?"
T është e përfaqësuar nga 100, gjëra të tilla si kjo,
dhe pastaj Huff do të marrë tekstin dhe pastaj e prodhimit që binar.
Por edhe sepse ne e dimë që ne duam për të lejuar marrësit e mesazhit tonë
të krijosh pemë e saktë të njëjta, ajo gjithashtu përfshin informacion në lidhje me akuzat e frekuencave.
Pastaj me Puff ne jemi të dhënë një skedar binar të 0s dhe 1s
dhe duke pasur parasysh edhe informacion në lidhje me frekuenca.
Ne përkthejnë të gjitha ato mbrapa 0s dhe 1s në mesazhin origjinale që ishte,
kështu që ne jemi decompressing se.
Nëse jeni duke bërë edicionin standarde, ju nuk keni nevojë për të zbatuar Huff,
kështu atëherë ju mund të përdorni vetëm zbatimin e stafit Huff.
Ka udhëzime në spekulim se si ta bëjnë këtë.
Ju mund të drejtuar zbatimin e stafit Huff mbi një skedar teksti të caktuar
dhe pastaj të përdorin atë si input output tuaj për pudre.
>> Siç e kam përmendur më parë, ne kemi një shumë të kodit të shpërndarjes për këtë një të tillë.
Unë jam duke shkuar për të filluar shkojnë nëpërmjet saj.
Unë jam duke shkuar për të shpenzuar pjesën më të madhe të kohës në internet. Fotografi h
sepse në fotografi. c, sepse ne kemi. h
dhe që na ofron me prototipa të funksioneve,
ne nuk kemi nevojë për të kuptuar plotësisht saktësisht -
Nëse ju nuk e kuptoni se çfarë po ndodh në fotografi. C, atëherë mos u shqetësoni shumë,
por patjetër të përpiqet të marrë një sy, sepse ajo mund të japë disa lë të kuptohet se
dhe kjo është e dobishme për të marrë të përdoret për të lexuar kodin e njerëzve të tjerë.
>> Duke kërkuar në huffile.h, në komentet që deklaron një shtresë e abstraksionit për Huffman-koduara fotografi.
Nëse ne do të shkojmë poshtë, ne shohim se ka një maksimum prej 256 simboleve që ne mund të kenë nevojë për kodet.
Kjo përfshin të gjitha shkronjat e alfabetit - uppercase dhe të vogla -
dhe pastaj simbolet dhe numrat, etj
Atëherë këtu kemi një numër magjik identifikuar një skedar të koduar Huffman.
Brenda një kod Huffman ata do të kenë një numër të caktuar magjike
shoqëruar me kokë.
Kjo mund të duket si vetëm një numër magjik të rastit,
por në qoftë se ju në të vërtetë përkthejnë atë në ASCII, atëherë ai në fakt parashikon Huff.
Këtu kemi një struct për një skedar Huffman-koduara.
Ka të gjitha këto karakteristika që lidhen me një file Huff.
Pastaj këtu poshtë kemi header për një skedar Huff, kështu që ne e quajmë atë Huffeader
në vend të shtuar h shtesë, sepse kjo tingëllon e njëjtë anyway.
Cute.
Ne kemi një numër magjik lidhur me të.
Në qoftë se kjo është një fotografi aktuale Huff, ajo do të jetë numri lart, kjo magji.
Dhe pastaj ajo do të ketë një rrjet.
Pra, për çdo simbol, e cila ka 256,
ajo do të listës atë që frekuenca e këtyre simboleve janë brenda file Huff.
Dhe pastaj në fund, ne kemi një checksum për frekuencave,
cila duhet të jetë shuma e këtyre frekuencave.
Pra, kjo është ajo që një Huffeader është.
Pastaj ne kemi disa funksione që kthejë pak ardhshëm në dosjen Huff
si shkruan një grimë në dosjen Huff, dhe pastaj ky funksion këtu, hfclose,
që në fakt mbyll dosjen Huff.
Para se, ne kemi qenë që kanë të bëjnë me të drejtë vetëm Shkrimi,
por kur ju keni një fotografi Huff, në vend të fclosing atë
atë që ju jeni të vërtetë do të bëni është të hfclose dhe hfopen atë.
Ata janë funksione specifike për dosjet Huff që ne jemi duke shkuar për të që kanë të bëjnë me të.
Atëherë këtu kemi lexuar në kokë dhe pastaj shkruani header.
>> Vetëm duke lexuar skedarin. H mundemi lloj të marrë një kuptim të asaj një file Huff mund të jetë,
çfarë karakteristikat që ka, në fakt pa shkuar në huffile.c,
të cilat, në qoftë se ne pikiatë në, do të jetë pak më e ndërlikuar.
Ajo ka të gjitha file I / O këtu kanë të bëjnë me pointers.
Këtu ne shohim se kur ne e quajmë hfread, për shembull, është ende që kanë të bëjnë me fread.
Ne nuk jemi duke u shpëtoj prej këtyre funksioneve tërësisht, por ne jemi të dërguar ata për të marrë kujdesin e
brenda file Huff në vend për të bërë të gjithë atë veten.
Ju mund të ndjehen të lirë për të skanoni me këtë, nëse ju jeni kurioz
dhe shkoni dhe zhvishem shtresën e mbrapa pak.
>> Dosja tjetër që ne jemi duke shkuar për të parë në është tree.h.
Parë në Walkthrough slides ne tha se ne presim një nyje Huffman
dhe kemi bërë një nyje typedef struct.
Ne presim që ajo të ketë një simbol, një frekuencë, dhe pastaj 2 yje të mundshëm nyje.
Në këtë rast ajo që ne po bëjmë është kjo është në thelb e njëjtë
përveç në vend të nyjeve ne jemi duke shkuar për të thirrur ata pemëve.
Ne kemi një funksion që kur ju telefononi bëni pemë të kthehet ju një tregues pemë.
Mbrapsht në speller, kur ju u bërë një nyje të re
ju tha nyje * fjalë të re = malloc (sizeof) dhe gjëra të tilla si se.
Në thelb, mktree do të jetë që kanë të bëjnë me atë për ju.
Në mënyrë të ngjashme, kur ju dëshironi të hiqni një pemë,
kështu që në thelb është liruar pemë, kur ju jeni bërë me të,
vend të lirë në mënyrë eksplicite duke bërë thirrje që ju jeni në të vërtetë vetëm duke shkuar për të përdorur funksionin rmtree
ku ju të kalojë në treguesin në atë pemë dhe pastaj elementit do të kujdeset për ju.
>> Ne shikojmë në tree.c.
Ne presim që të njëjtat funksione, përveç për të parë zbatimin si.
Siç kemi pritur, kur ju telefononi atë mktree mallocs madhësinë e një pemë në një akrep,
initializes të gjitha vlerat në vlera null, kështu 0s ose NULLs,
dhe pastaj kthen treguesin në atë pemë që e keni malloc'd vetëm për ju.
Këtu kur ju telefononi për të hequr pemë kjo e parë e bën të sigurt që ju nuk jeni të dyfishtë liruar.
Kjo e bën të sigurt që ju të vërtetë kanë një pemë që ju dëshironi të hiqni.
Këtu sepse një pemë përfshin edhe fëmijët e saj,
Çfarë kjo nuk është ajo e quan Recursively të hequr pemë në nyjen e majtë të pemës
si dhe nyjen e djathtë.
Para se ajo liron prindin, ajo ka nevojë për të liruar fëmijët si.
Prindi është gjithashtu i këmbyeshëm me rrënjë.
Prindi parë ndonjëherë, kështu që si i madh-madhe-madhe-madh-gjyshi
ose dru gjyshja, së pari ne duhet ta lirojmë poshtë niveleve të parë.
Pra, përshkojnë në fund, pa ato, dhe pastaj të kthehen deri, pa ato, etj
Pra, kjo është pema.
>> Tani ne shikojmë në pyll.
Pylli është ajo ku ju vendosni të gjitha pemëve Huffman tuaj.
Është thënë se ne do të kemi diçka të quajtur një komplot
që përmban një tregues për një pemë si një tregues për një komplot të quajtur ardhshëm.
Çfarë e bën këtë strukturë lloj të duken si?
Ai lloj i thotë atë atje.
Drejtë mbi këtu.
Një listë e lidhur.
Ne shohim se kur kemi një komplot është si një listë e lidhur e ngastrave.
Një pyll është përcaktuar si një listë e lidhur e parcelave,
dhe kështu struktura e pyjeve është që ne jemi vetëm do të ketë një tregues për komplot tonë të parë
dhe që komploti ka një pemë brenda saj ose më mirë tregon një pemë
dhe pastaj tregon për komplot tjetër, kështu me radhë e kështu me radhë.
Për të bërë një pyll që ne e quajmë mkforest.
Pastaj ne kemi disa funksione mjaft të dobishme këtu.
Ne kemi marr ku ju të kalojë në një pyll dhe pastaj vlera e kthimit është një * Tree,
një akrep tek një peme.
Çfarë do të bëni është të vini ai do të shkojë në pyll se ju jeni treguar të
atëherë hiqni një pemë me frekuencë më të ulët nga ajo pyll
dhe pastaj ju japin treguesin në atë pemë.
Pasi ju e quani vini, pema nuk do të ekzistojë më në pyll,
por vlera e kthimit është tregues për atë pemë.
Atëherë ju keni bimë.
Me kusht që ju të kalojë në një tregues për një pemë që ka një frekuencë jo-0,
çfarë do të bëni është bimë ajo do të marrë në pyll, të marrë pemë dhe bimë që brenda pema e pyllit.
Këtu kemi rmforest.
Ngjashme për të hequr pemë, e cila në thelb liruar të gjitha pemëve tona për ne,
hiqni çdo gjë do pyll pa përmbajtura në këtë pyll.
>> Nëse ne shikojmë në forest.c, ne do të presim të shohim të paktën 1 komandë rmtree në atje,
për shkak të kujtesës të lirë në pyll nëse një pylli ka pemë në të,
pastaj përfundimisht ju jeni do të duhet për të hequr ato pemë shumë.
Nëse ne shikojmë në forest.c, ne kemi mkforest tonë, e cila është si ne presim.
Ne malloc gjëra.
Ne nisja komplot parë në pyll si NULL, sepse kjo është e zbrazët për të filluar me të,
atëherë ne shohim marr, e cila kthen pemë me peshë të ulët, frekuenca më të ulët,
dhe pastaj merr shpëtoj të asaj nyje të veçantë që tregon atë pemë dhe një tjetër,
kështu që ajo merr nga lista e lidhur e pyllit.
Dhe atëherë këtu kemi bimore, i cili fut një pemë në listën e lidhur.
Çfarë pyll nuk është ajo e bukur e mban atë renditura për ne.
Dhe pastaj në fund, ne kemi rmforest dhe, siç pritej, ne kemi rmtree thirrur atje.
>> Duke parë në kodin e shpërndarjes deri tani, huffile.c ndoshta ishte deri tani më e vështirë për të kuptuar,
ndërsa fotografi të tjera vetë ishin mjaft të thjeshtë për të ndjekur.
Me njohuritë tona të pointers dhe listat e lidhura dhe të tilla,
ne ishim në gjendje për të ndjekur mjaft mirë.
Por të gjithë ne kemi nevojë të vërtetë të siguruar që ne e kuptojmë plotësisht është. Fotografi h
sepse keni nevojë për të thirrur këto funksione, që kanë të bëjnë me ato vlera të kthimit,
prandaj sigurohuni që ju të kuptoni plotësisht atë veprim do të kryhet
kur ju telefononi një prej këtyre funksioneve.
Por në fakt kuptuar në brendësi të saj nuk është mjaft e nevojshme, sepse ne kemi ato. Fotografi h.
Ne kemi 2 më shumë fotografi mbetur në kodin tonë të shpërndarjes.
>> Le të shikojmë në hale.
Hale me komentin e saj këtu merr një skedar të kompresuar Huffman-
dhe pastaj përkthehet dhe deponitë e gjithë përmbajtjen e saj jashtë.
Këtu ne shohim se ajo flet hfopen.
Kjo është lloj i mirroring të paraqesë * Input = fopen,
dhe pastaj të kalojë në informacion.
Kjo është pothuajse identike, përveç në vend të një skedar * ju jeni duke kaluar në një Huffile;
vend të fopen ju jeni duke kaluar në hfopen.
Këtu lexojmë në kokë parë, e cila është lloj i ngjashëm me mënyrën se si kemi lexuar në kokë
për një fotografi bitmap.
Ajo që ne po bëjmë këtu është kontrolluar për të parë nëse informacioni header
përmban numrin e duhur magjike që tregon se ajo është një fotografi aktuale Huff,
atëherë të gjitha këto kontrolle për të siguruar që ne të hapur file që është një file aktuale huffed apo jo.
Çfarë kjo nuk është ajo rezultatet frekuencat e të gjitha simbolet që ne mund të shohim
brenda një terminal në një tryezë grafik.
Kjo pjesë do të jenë të dobishme.
Ajo ka një grimë dhe lexon pak nga pak në pak ndryshueshme dhe pastaj shtyp atë.
Pra, nëse unë do të thërrasë në hth.bin hale, e cila është rezultat i huffing një skedar
duke përdorur zgjidhje stafit, unë do të merrni këtë.
Është outputting të gjitha këto karaktere dhe pastaj duke frekuencën në të cilën ato shfaqen.
Nëse ne shikojmë, shumica e tyre janë 0s përjashtim për këtë: H, të cilat duket se dy herë,
dhe pastaj T, e cila duket një herë.
Dhe atëherë këtu kemi mesazhin aktuale në 0s dhe 1s.
Nëse ne shikojmë në hth.txt, e cila është me sa duket mesazhi origjinal që u huffed,
ne presim të shohim disa HS dhe TS në atje.
Në mënyrë të veçantë, ne presim të shohim vetëm 1 T dhe 2 HS.
Këtu ne jemi në hth.txt. Ajo me të vërtetë ka HTH.
Përfshira në atje, edhe pse ne nuk mund ta shohim atë, është një karakter newline.
The hth.bin fotografi Huff është edhe kodimin karakterin si newline mirë.
Këtu, sepse ne e dimë se qëllim është HTH dhe pastaj newline,
ne mund shih se ndoshta H është përfaqësuara nga vetëm një 1 vetme
dhe pastaj T është ndoshta 01 dhe pastaj H 1 tjetër është edhe
dhe pastaj ne kemi një newline tregohet nga dy 0s.
Cool.
>> Dhe pastaj në fund, sepse ne jemi që kanë të bëjnë me të. C shumta dhe. Fotografi h,
ne do të ketë një argument mjaft kompleks për përpiluesit,
dhe kështu që këtu ne kemi një Makefile që e bën hale për ju.
Por në fakt, ju duhet të shkoni për të bërë vet dosjen tuaj puff.c.
Makefile fakt nuk merret me bërjen e puff.c për ju.
Ne jemi duke lënë që deri tek ju për të redaktuar Makefile.
Kur ju shkruani një komandë si të bëjë të gjitha, për shembull, ajo do të bëjë të gjitha ato për ju.
Ndjehen të lirë për të shikoni në shembujt e Makefile nga pset kaluar
si plaste të këtë një të parë se si ju mund të jetë në gjendje të bëjë dosjen tuaj pudre
nga redaktimi këtë Makefile.
Kjo është në lidhje me atë për kodin tonë të shpërndarjes.
>> Pasi kemi marrë përmes kësaj, atëherë këtu është vetëm një kujtesë
se si ne jemi duke shkuar për të që kanë të bëjnë me nyje Huffman.
Ne nuk do të jeni të duke i quajtur ato nyjet më, ne jemi duke shkuar për të bërë thirrje atyre pemëve
ku ne jemi duke shkuar për të përfaqësuar simbolin e tyre me një char,
frekuenca e tyre, numri i dukurive, me një numër të plotë.
Ne jemi duke përdorur atë, sepse kjo është më e saktë se një noton.
Dhe pastaj ne kemi një tjetër tregues për fëmijën e majtë, si dhe fëmijën e duhur.
Një pyll, siç e pamë, është vetëm një listë e lidhur e pemëve.
Në fund të fundit, kur ne jemi duke ndërtuar Huff dosjen tonë,
ne duam pyjeve tona të përmbajë vetëm pemë 1 -
1 pemë, 1 rrënjë me fëmijë të shumta.
Më herët, kur ne ishim vetëm duke bërë pemë Huffman tona,
kemi filluar nga vendosja të gjitha nyjet mbi ekranin tonë
dhe duke thënë se ne do të kemi këto nyje,
përfundimisht ata do të jenë gjethet, dhe kjo është simbol i tyre, kjo është frekuenca e tyre.
Në pyll tonë nëse ne vetëm kemi 3 letra, që është një pyll prej 3 pemëve.
Dhe pastaj si të shkojmë më, kur kemi shtuar prindin e parë,
kemi bërë një pyll prej 2 pemë.
Ne kemi hequr 2 të këtyre fëmijëve nga pylli tonë dhe pastaj e zëvendësoi atë me një nyje prind
që kishin ato 2 nyjet si fëmijë.
Dhe pastaj në fund, hapi ynë i fundit me marrjen shembullin tonë me AS, BS, dhe Cs
do të jetë për të bërë prind përfundimtar,
dhe kështu atëherë kjo do të sjellë akuzë tonë të plotë të pemëve në pyll për të 1.
A të gjithë të shohim se si ju filloni me pemë të shumta në pyll tuaj
dhe do të përfundojë me 1? Rregull. Cool.
>> Çfarë duhet të bëjmë për Puff?
Ajo që ne duhet të bëni është të siguruar që, si gjithmonë, ata na japin të drejtën llojin e input
kështu që ne mund të vërtetë të drejtuar programin.
Në këtë rast ata do të na dhënë pas tyre argumentit të parë command-line
2 më: fotografia që ne duam të shfryj dhe prodhimi i dosjes dekompresohen.
Por pasi jemi të sigurt se ata na kalojë në shumën e duhur të vlerave,
ne duam të siguruar që input është një file Huff apo jo.
Dhe pastaj një herë ne garantojmë se kjo është një file Huff, atëherë ne duam të ndërtojmë pemë tonë,
ndërtuar deri pemë të tillë që përputhet me pemën që personi që dërgoi mesazhin e ndërtuar.
Pastaj pasi kemi ndërtuar pemë, atëherë ne mund të merren me, 0s dhe 1s që ata kaluan në
ndjekin ato përgjatë pemës tonë, sepse ajo është e njëjtë,
dhe pastaj shkruani këtë mesazh nga, interpretojnë bit përsëri në karaktere.
Dhe pastaj në fund, sepse ne jemi që kanë të bëjnë me pointers këtu,
ne duam të sigurohemi që ne nuk kemi asnjë rrjedhjet e kujtesës
dhe se ne gjithçka falas.
>> Sigurimi i përdorimit të duhur është e vjetruar për ne deri tani.
Ne kemi marrë në një input, e cila do të jetë emri i file për të fryj,
dhe pastaj ne të specifikojë një dalje,
kështu emri i dosjes për dalje fryrë, i cili do të jetë skedar teksti.
Kjo është përdorimi. Dhe tani ne duam të siguruar që input është huffed apo jo.
Menduarit prapa, ishte atje asgjë në kodin e shpërndarjes që mund të na ndihmojë
me të kuptuarit nëse një skedar është huffed apo jo?
Ka pasur informacion në lidhje me huffile.c Huffeader.
Ne e dimë se çdo fotografi Huff ka një Huffeader lidhur me atë me një numër magjik
si dhe një grup i frekuencave për çdo simbol
si edhe një cekimit.
Ne e dimë se, por ne gjithashtu mori një vështrim në dump.c,
në të cilën ai është lexuar në një skedar Huff.
Dhe kështu për ta bërë këtë, ajo kishte për të kontrolluar nëse ajo me të vërtetë ishte huffed apo jo.
Kështu që ndoshta ne mund të përdorim dump.c si një strukturë për puff.c. tonë
Mbrapsht në pset 4 kur kemi pasur copy.c kopjuar file që në treshe RGB
dhe ne interpretohet se për roman policor dhe resize,
Në mënyrë të ngjashme, çfarë ju mund të bëni është të drejtuar vetëm komandën si cp dump.c puff.c
dhe përdorin disa të kodit atje.
Megjithatë, kjo nuk do të jetë aq i hapur i një procesi
për përkthimin dump.c tuaj në puff.c,
por të paktën kjo ju jep një vend për të filluar
si për të siguruar se input është huffed vërtetë apo jo
si edhe disa gjëra të tjera.
Ne kemi siguruar përdorimin e duhur dhe siguroi se input është huffed.
Çdo herë që ne kemi bërë që kemi bërë kontrollin e duhur gabimi tonë,
kështu që të kthehej dhe të ndalohet pirja e duhanit funksionin nëse disa dështimi ndodh, në qoftë se ka një problem.
>> Tani ajo që ne duam të bëjmë është të ndërtojë pemën aktuale.
Nëse ne shikojmë në pyll, ka 2 funksione kryesore
që ne jemi duke shkuar për të duan të bëhen shumë të njohur me të.
Ka bimë Boolean funksion që bimët jo-0 pemë frekuencave brenda pyllit tonë.
Dhe kështu që nuk do të kalosh në një pointer në një pyll dhe një tregues për një pemë.
Pyetje të shpejtë: Sa pyjet do të keni kur ju jeni ndërtimin e një pemë Huffman?
Pylli ynë është si kanavacë tonë, apo jo?
Pra, ne jemi vetëm do të ketë 1 pyll, por ne do të kemi pemë të shumta.
Pra, para se të telefononi bimore, me sa duket ju jeni do të duan të bëjnë pyll tuaj.
Nuk është një komandë për këtë në qoftë se ju shikoni në forest.h se si ju mund të bëni një pyll.
Ju mund të mbjellësh një pemë. Ne e dimë se si ta bëjnë këtë.
Dhe pastaj ju gjithashtu mund të marr një pemë nga pylli,
heqjen e një pemë me peshë të ulët dhe duke ju dhënë tregues për këtë.
Duke menduar përsëri në kur ne ishim duke bërë shembujt veten,
kur ne u tërhequr atë jashtë, ne thjesht vetëm shtuar lidhjet.
Por këtu në vend të vetëm duke shtuar lidhjet,
të mendojnë për atë më shumë si ju jeni duke hequr 2 e atyre nyjave dhe pastaj duke e zëvendësuar atë me një tjetër.
Të shprehur se në drejtim të ringjallet dhe mbjelljes,
ju jeni picking 2 pemë dhe pastaj mbjelljen e një peme
se ka 2 këto pemë që ju kap si fëmijë.
Për të ndërtuar pemën Huffman, ju mund ta lexoni në simbolet dhe frekuencave në mënyrë
sepse Huffeader jep se për ju,
ju jep një rrjet të frekuencave.
Kështu që ju mund të shkoni përpara dhe vetëm injorojnë asgjë me 0 në të
sepse ne nuk duam 256 gjethet në fund të tij.
Ne vetëm duam numrin e lë që janë karaktere
që janë përdorur në të vërtetë në dosjen.
Ju mund ta lexoni në këto simbole, dhe secili prej këtyre simboleve që kanë jo-0 frekuencave,
ata do të jenë pemët.
Çfarë ju mund të bëni është çdo herë që ju lexoni në një simbol jo-0 frekuencave,
ju mund të mbjellë këtë pemë në pyll.
Pasi të keni mbjellë pemë në pyll, ju mund të bashkohen këto pemë si vëllezërit e motrat,
kështu do të kthehet në mbjelljen dhe ringjallet ku ju të vini 2 dhe pastaj bimore 1,
ku se 1 se ju bimore është prind i 2 fëmijëve që keni zgjedhur.
Pra, atëherë rezultati juaj në fund do të jetë një pemë të vetme në pyll tuaj.
Kjo është se si ju të ndërtuar pemën tuaj.
>> Ka disa gjëra që mund të shkojnë keq këtu
sepse ne jemi që kanë të bëjnë me bërjen e pemëve të reja dhe kanë të bëjnë me pointers dhe gjëra si kjo.
Para se kur ne u bëjmë me pointers,
kurdo ne e kemi dashur malloc'd për t'u siguruar se ajo nuk u kthye ne një vlerë NULL akrep.
Pra, në disa hapa në kuadër të këtij procesi nuk do të jetë disa raste
ku programi juaj mund të dështojnë.
Çfarë doni të bëni është që ju doni të bëni të sigurtë që ju të trajtojë ato gabime,
dhe në spekulim ajo thotë se për të trajtuar ato gracefully,
Pra, si të shtypura nga një mesazh për përdoruesit duke u thënë atyre pse programi ka për të lënë
dhe pastaj menjëherë u largua atë.
Për ta bërë këtë gabim trajtimin, mos harroni se ju doni të kontrolloni atë
çdo herë të vetme që nuk mund të jetë një dështim.
Çdo herë të vetme që ju jeni duke bërë një tregues të ri
ju doni të bëni të sigurtë që kjo është e suksesshme.
Para se çfarë kemi përdorur për të bëni është të bëjë një tregues të ri dhe malloc atë,
dhe pastaj ne do të kontrolloni nëse ky tregues është NULL.
Kështu që nuk do të jenë disa raste kur ju thjesht mund të bëni që,
por ndonjëherë ju jeni në të vërtetë duke e quajtur një funksion
dhe në atë funksion, kjo është ajo që e bën të mallocing.
Në këtë rast, nëse ne shikojmë prapa në disa prej funksioneve brenda kodit,
disa prej tyre janë funksione Boolean.
Në rastin abstrakt qoftë se ne kemi një funksion Boolean quajtur foo,
thelb, ne mund të supozojmë se përveç për të bërë çdo gjë që bën foo,
pasi ajo është një funksion Boolean, ajo kthehet e vërtetë apo e rreme -
vërtetë në qoftë se e suksesshme, false nëse jo.
Pra, ne duam të kontrolloni nëse vlera kthimi i foo është e vërtetë apo e rreme.
Nëse është e rreme, që do të thotë se ne do të duan për të shkruar një lloj mesazhi
dhe pastaj mbaro programin.
Ajo që ne duam të bëjmë është të kontrolloni vlerën e kthimit të foo.
Nëse foo kthen false, atëherë ne e dimë që ne kemi hasur disa lloj të gabimit
dhe ne kemi nevojë për të lënë programin tonë.
Një mënyrë për të bërë këtë është të ketë një kusht, ku funksioni aktual në vetvete është gjendja juaj.
Thuaj foo merr në x.
Ne mund të kemi një gjendje si në qoftë se (foo (x)).
Në thelb, kjo do të thotë në qoftë se në fund të ekzekutimit foo ajo kthehet e vërtetë,
atëherë ne mund të bëjmë këtë, sepse funksioni ka për të vlerësuar foo
në mënyrë që të vlerësojë gjendjen e tërë.
Kështu, pra, kjo është se si ju mund të bëni diçka nëse funksioni kthen vërtetë dhe është i suksesshëm.
Por kur ju jeni duke kontrolluar gabim, ju vetëm duan të lënë në qoftë se funksioni juaj kthehet rreme.
Çfarë ju mund të bëni është që vetëm të shtoni një == false ose thjesht të shtoni një zhurmë në frontin e tij
dhe pastaj ju duhet në qoftë se (! foo).
Brenda atij trupi i asaj kusht që ju do të ketë të gjitha të trajtimit të gabimit,
Pra, si, "I pamundur krijimi i kësaj peme" dhe pastaj do të ktheheni 1 ose diçka të tillë.
Atë që bën, megjithatë, është se edhe pse foo kthye false -
Thuaj foo kthen vërtetë.
Atëherë ju nuk keni për të thirrur foo përsëri. Kjo është një keqkuptim të përbashkët.
Sepse ajo ishte në gjendjen tuaj, kjo është vlerësuar tashmë,
kështu që ju tashmë keni rezultat në qoftë se ju jeni duke përdorur të bëni pemë ose diçka të tillë
ose bimore ose të zgjedhë ose diçka.
Ajo tashmë ka atë vlerë. Është ekzekutuar tashmë.
Pra, kjo është e dobishme për t'u përdorur funksionet boolean si kusht
sepse nëse janë apo jo ju në të vërtetë ekzekutuar trupin e lak,
ajo ekzekuton funksionin anyway.
>> Dytë jonë për hapin e fundit është shkruar mesazhin në dosjen.
Pasi ne kemi ndërtuar pemën Huffman, atëherë shkruar mesazhin në dosjen është shumë i thjeshtë.
Është shumë i thjeshtë tani për vetëm ndjekin 0s dhe 1s.
Dhe kështu nga Konventa ne e dimë se në një pemë Huffman të 0s tregojnë la
dhe 1s tregojnë drejtë.
Prandaj, nëse keni lexuar në pak nga pak, çdo herë që ju të merrni një 0
ju do të ndiqni degë e majtë, dhe pastaj çdo herë që ju lexoni në 1
ju do të jeni të ndjekur degën e duhur.
Dhe atëherë ju jeni do të vazhdojë deri sa ju goditi një fletë
sepse gjethet do të jetë në fund të degëve.
Si mund të thoni nëse ne kemi goditur një gjethe apo jo?
Kemi thënë atë më parë.
[Student] Nëse pointers janë NULL. Po >>.
Ne mund të them nëse kemi goditur një gjethe nëse pointers në pemë dy majtë dhe të djathtë janë NULL.
Përsosur.
Ne e dimë që ne duam të lexuar në pak nga pak në Huff dosjen tonë.
Siç e pamë më parë në dump.c, çfarë ata bënë është që ata lexojnë në pak nga pak në dosjen Huff
dhe të shtypura vetëm se çfarë ata ishin bit.
Ne nuk do të jeni të bërë këtë. Ne jemi duke shkuar për të bërë diçka që është pak më komplekse.
Por ajo që mund të bëjmë është që ne mund të merrni atë grimë e kodit që lexon në të bit.
Këtu kemi pak integer përfaqëson pak se tanishme ne jemi në.
Kjo kujdeset iterating të gjitha bit në dosjen derisa ju goditi në fund të file.
Bazuar në këtë, atëherë ju jeni do të duan që të ketë një lloj të iterator
të kaloj nëpër pemë tuaj.
Dhe pastaj në bazë të a pak është 0 ose 1,
ju jeni do të duan të lëvizin qoftë se iterator në të majtë ose të lëvizin atë në të djathtë
të gjithë rrugën deri sa ju goditi një fletë, në mënyrë që të gjithë rrugën deri në atë nyje që ju jeni në
nuk tregojnë për ndonjë nyje shumë.
Pse mund ta bëjmë këtë me një file Huffman por jo kodin Morse?
Sepse në kodin Morse ka pak paqartësi.
Ne mund të jetë si, Oh wait, ne kemi goditur një letër gjatë rrugës, kështu që ndoshta kjo është letra jonë,
ndërsa nëse ne kemi vazhduar vetëm një pak më të gjatë, atëherë ne do të kemi goditur një tjetër letër.
Por kjo nuk do të ndodhë në kodimin Huffman,
kështu që ne mund të pushoni siguroi se mënyra e vetme që ne jemi duke shkuar për të goditur një karakter
është nëse fëmijët e majtë dhe të djathtë se Nyja janë NULL.
>> Së fundi, ne duam për të liruar të gjithë kujtesën tonë.
Ne duam që të dy të mbyllur dosjen Huff që ne kemi qenë që kanë të bëjnë me
si dhe për të hequr të gjitha pemëve në pyll tonë.
Bazuar në implementimin tuaj, ju jeni me siguri do të duan të thërrasë hequr pyll
në vend që të shkojnë të vërtetë nëpër të gjitha pemëve veten.
Por në qoftë se keni bërë ndonjë pemë të përkohshme, ju do të dëshironi për të liruar atë.
Ju e dini kodin tuaj më të mirë, kështu që ju e dini ku jeni alokimin e kujtesës.
Dhe kështu që nëse ju shkoni në, të fillojnë, madje, Kontrollit F'ing për malloc,
parë sa herë që ju malloc dhe duke e bërë të sigurtë që ju të liruar të gjithë se
por vetëm atëherë kalon kodin tuaj,
kuptuar ku ju mund të kanë ndarë kujtesës.
Zakonisht ju mund të them vetëm, "Në fund të një skedar Unë jam vetëm duke shkuar për të hequr pyll në pyll tim",
Pra, në thelb e qartë se kujtesa, pa se,
"Dhe atëherë unë jam gjithashtu duke shkuar për të mbyllur dosjen dhe pastaj programi im do të lë".
Por është se koha vetëm që programi juaj shpërblej?
Jo, sepse nganjëherë nuk mund të ketë qenë një gabim që ka ndodhur.
Ndoshta ne nuk mund të hapur një skedë ose ne nuk mund të bëjë një tjetër pemë
ose disa lloj të gabimit ndodhur në procesin e alokimit të kujtesës dhe kështu ai u kthye NULL.
Një gabim ka ndodhur dhe pastaj ne u kthye dhe u largua.
Pra, atëherë ju doni të bëni të sigurtë që në çdo kohë të jetë e mundur që programi juaj mund të lë,
ju doni për të liruar të gjithë kujtesën tuaj atje.
Kjo nuk është vetëm do të jetë në fund të funksionit kryesor që ju lë kodin tuaj.
Ju doni të shikoni përsëri në çdo rast se kodi juaj potencialisht mund të kthehen para kohe
dhe pastaj të lirë çdo gjë që kujtesa bën kuptim.
Thonë se ju kishte bërë thirrje të bëni pyll dhe që u kthye rreme.
Atëherë ju ndoshta nuk do të duhet për të hequr pyllin tuaj
sepse ju nuk keni një pyll ende.
Por në çdo moment në kodin ku ju mund të kthehet para kohe
ju doni të bëni të sigurtë që ju të liruar ndonjë kujtim të mundshme.
>> Pra, kur ne jemi që kanë të bëjnë me çlirimin e kujtesës dhe rrjedhjet e mundshme që,
ne duam që të mos përdorin vetëm gjykimin tonë dhe logjikën tonë
por të përdorë gjithashtu edhe Shprehje për të përcaktuar nëse ne kemi liruar të gjithë kujtesën tonë siç duhet apo jo.
Ju ose mund të kandidojë më Shprehje Puff dhe pastaj ju duhet gjithashtu të kalojë atë
Numri drejta e command-line argumente për Shprehje.
Ju mund të kandidojë atë, por prodhimi është pak fshehtë.
Ne kemi marrë një grimë përdoret për atë me speller, por ne ende nevojë për ndihmë pak më shumë,
kështu atëherë running atë me një pak më shumë flamuj si rrjedhje-check = plot,
që ndoshta do të na jepni disa dalje më e dobishme për Shprehje.
>> Pastaj një tjetër tip i dobishëm kur ju jeni debugging është komanda ndrysh.
Ju mund të hyni në zbatimin e stafit e Huff, e drejtuar që në një skedar teksti,
dhe pastaj atë të prodhimit një file binar binar, një fotografi Huff, të jenë specifike.
Pastaj në qoftë se ju drejtuar duhmë tuaj në këtë dosje binar,
pastaj ideale, dosja juaj outputted teksti do të jetë identike
në një origjinal që kaloi in
Këtu unë jam duke përdorur hth.txt si shembull, dhe kjo është një spekulim biseduar rreth në tuaj.
Kjo është fjalë për fjalë vetëm HTH dhe pastaj një newline.
Por patjetër të ndjehen të lirë dhe ju jeni të inkurajuar të përdorin patjetër shembuj më të gjatë
për dosjen tuaj tekst.
>> Ju mund të merrni edhe një e shtënë në ndoshta compressing dhe pastaj decompressing
disa nga dosjet që keni përdorur në speller si Luftës dhe Paqes
ose Jane Austen ose diçka të tillë - që do të jetë lloj i ftohtë - ose Kompetencat Austin,
lloj të merret me fotografi të mëdha, sepse ne nuk do të vijë deri në atë
nëse kemi përdorur mjet tjetër këtu, ls-l.
Ne jemi përdorur për të ls, e cila në thelb listat të gjitha përmbajtjet në directory tonë të tanishëm.
Kalimi në flamurin l-fakt tregon madhësinë e këtyre dosjeve.
Nëse ju shkoni nëpër spekulim pset, në fakt ajo ecën ju nëpërmjet krijimit të file binar,
e huffing atë, dhe ju të shihni se për fotografi shumë të vogla
kostoja hapësira e compressing atë dhe përkthimin e të gjithë atë informacion
të gjitha frekuencave dhe gjëra të tilla si që tejkalon përfitimi aktual
i compressing skedarin në vend të parë.
Por në qoftë se ju drejtuar atë në disa fotografi tekst më të gjatë, atëherë ju mund të shihni që ju të filloni të merrni disa përfitime
në ato fotografi compressing.
>> Dhe pastaj në fund, ne kemi vjetër Gdb tonë PAL, e cila është definitivisht do të jetë në dispozicion shumë.
>> A kemi ndonjë pyetje në pemë Huff ose ndoshta për të bërë procesin e pemëve
ose ndonjë pyetje të tjera mbi Puff Huff'n?
Rregull. Unë do të qëndrojnë rreth e rrotull për një grimë.
>> Faleminderit, të gjithë. Kjo ishte Walkthrough 6. Dhe fat të mirë.
>> [CS50.TV]