[Powered by Google Translate] [Solisyon - Set Pwoblèm 6]
[Zamyla Chan - Inivèsite Harvard]
[Sa a se CS50. - CS50.TV]
>> Hello, tout moun, epi byenveni nan solisyon 6: Huff'n feyte.
Nan feyte Huff'n ki sa nou ap fè yo pral fè fas ak yon dosye konprese Huffman
ak Lè sa a, aletman li tounen moute, se konsa dekonprese li,
pou nou ka tradui soti nan ki 0s ak 1S voye nan itilizatè a nou
epi konvèti li tounen nan tèks orijinal la.
Pset 6 a pwal trè fre paske w ap ale nan wè kèk nan zouti yo
ke ou te itilize nan pset 4 ak pset 5 ak kalite konbine yo nan 1 konsèp trè pwòp
lè ou vini nan panse sou sa.
>> Epitou, joui, pset 4 ak 5 yo te pi psets yo solid ki nou te gen yo ofri.
Se konsa, soti nan kounye a, nou gen sa a pset 1 plis nan C,
ak Lè sa a, apre ke nou se sou pwogramasyon entènèt.
Se konsa, felisite tèt nou pou jwenn plis pase bòs la pi di nan CS50.
>> Deplase sou pou feyte Huff'n, bwat zouti pou nou an pou sa a pset pwal gen Huffman pye bwa,
Se konsa konprann pa sèlman ki jan binè pyebwa travay, men tou espesyalman Huffman pye bwa,
ki jan yo ap konstwi.
Lè sa a, nou pral gen yon anpil nan kòd distribisyon nan sa a pset,
epi n ap vin wè ki aktyèlman kèk nan kòd la
nou pa ka kapab konprann konplètman ankò,
ak sa moun yo pral. dosye yo c, men Lè sa a, akonpaye yo. dosye h
pral ban nou ase konpreyansyon ke nou bezwen pou nou konnen ki jan moun ki fonksyon travay
oswa omwen sa yo ap sipoze fè - entrain yo epi yo sorti -
menm si nou pa konnen sa k ap pase nan ti bwat la nwa
oswa ou pa konprann sa k ap pase nan ti bwat la nwa nan.
Lè sa a, finalman, kòm dabitid, nou ap fè fas ak estrikti done nouvo,
kalite espesifik nan nœuds ki pwen a sèten bagay,
e konsa isit la gen yon plim ak papye pa sèlman pou pwosesis la konsepsyon
ak ki lè ou ap eseye figi konnen kouman pset ou yo ta dwe travay
men tou pandan debogaj.
Ou ka gen gdb ansanm ak plim ou ak papye pandan w ap pran desann sa ki valè yo ye a,
kote flèch ou yo ap lonje dwèt, ak bagay sa yo tankou sa.
>> Premye kite pou yo gade nan Huffman pyebwa.
Pye bwa yo se pye bwa Huffman binè, sa vle di ke chak ne sèlman gen 2 timoun yo.
Nan Huffman pye bwa karakteristik la se ke valè yo pi souvan
yo reprezante nan Bits yo gen mwens.
Nou te wè nan egzanp konferans nan Morse kòd, ki kalite consolidée kèk lèt.
Si w ap eseye tradui yon A oswa E yon, pou egzanp,
w ap tradui ki souvan, se konsa olye pou yo gen yo sèvi ak seri a plen nan Bits
afekte pou sa kalite abityèl done, ou konpresyon li desann nan mwens,
ak Lè sa a, lèt sa yo ki ap reprezante mwens souvan yo reprezante ak pi long Bits
paske ou kapab peye ke lè ou peze soti fwekans yo ke lèt sa yo parèt.
Nou gen lide nan menm isit la nan Huffman pye bwa
kote nou yo ap fè yon chèn, yon kalite chemen pou li ale nan karaktè yo ki sèten.
Lè sa a, karaktè yo ki gen frekans ki pi
yo pral reprezante ak Bits yo gen mwens.
>> Fason ke ou konstwi yon pyebwa Huffman
se lè w mete tout nan karaktè yo ki parèt nan tèks la
ak kalkile frekans yo, konbyen fwa yo parèt.
Sa a te swa gen yon konte nan konbyen fwa lèt sa yo parèt
oswa petèt yon pousantaj nan soti nan tout karaktè yo ki jan anpil chak moun parèt.
Se konsa, sa ou fè se yon fwa ou gen tout ki soti mappé,
Lè sa a, ou gade pou 2 fwekans yo pi ba a epi Lè sa a, rantre nan yo tankou frè ak sè
Lè sa a, kote ne nan paran yo gen yon frekans ki se sòm total la nan 2 timoun li yo.
Lè sa a, ou pa konvansyon di ke ne gòch la,
ou swiv ki pa swiv branch nan 0,
ak Lè sa a, ne la rightmost se branch nan 1.
Kòm nou te wè nan Morse kòd, gotcha nan youn te ke si ou te gen jis yon BEEP ak BEEP la
li te Limit.
Li te kapab swa dwe 1 lèt oswa li ka yon sekans nan 2 lèt yo.
Se konsa, sa ki Huffman pye bwa fè a se paske pa nati nan karaktè yo ki
oswa karaktè final nou an ke yo te vrè nœuds ki sot pase yo sou branch la -
nou al gade nan sa yo kòm fèy - pa vèrtu nan ke gen pa kapab gen nenpòt ki anbigwite
an tèm de ki lèt w ap eseye programme ak seri a nan Bits
paske okenn kote ansanm Bits yo ki reprezante 1 lèt
ou pral rankontre yon lòt lèt antye, e gen pa yo pral nenpòt konfizyon la.
Men, nou pral ale nan egzanp ke ou nèg ka aktyèlman wè ke
olye pou yo jis nou di ou ke sa a, se vre.
>> Se pou yo gade nan yon egzanp senp nan yon pyebwa Huffman.
Mwen gen yon fisèl isit la ke se 12 karaktè nan longè.
Mwen gen 4 Kòm, 6 B, ak 2 CS.
Premye etap mwen ta dwe konte.
Konbyen fwa Yon parèt? Li parèt 4 fwa nan fil la.
B parèt 6 fwa, ak C parèt 2 fwa.
Natirèlman, mwen pral di mwen sèvi ak B pi souvan,
Se konsa, mwen vle reprezante B avèk nimewo a mwens nan Bits, nimewo a mwens nan 0s ak 1S.
Lè sa a, mwen tou ale nan atann C rive nan mande pou kantite lajan nan pi fò nan 0s ak 1S kòm byen.
Premye sa mwen te fè isit la se mwen mete yo nan lòd moute an tèm de frekans.
Nou wè ke C a ak A a, sa yo se 2 nou an ki pi ba frekans.
Nou kreye yon ne paran, e ke ne paran pa gen yon lèt ki asosye ak li,
men li fè sa gen yon frekans, ki se sòm total la.
Sòm la vin tounen 2 + 4, ki se 6.
Lè sa a, nou swiv branch lan kite.
Si nou tout nou te nan ki ne, 6, Lè sa a, nou ta swiv 0 pou li ale nan C
ak Lè sa a, 1 pou li ale nan A.
Se konsa, kounye a nou gen 2 nœuds.
Nou gen valè a 6 ak Lè sa a, nou menm tou nou gen yon lòt ne ak valè a 6.
Se konsa, sa yo 2 yo se pa sèlman 2 ki pi ba a, men tou jis 2 a ki rete,
pou nou antre nan sa yo pa yon lòt paran, ak sòm total la ke yo te 12.
Se konsa, isit la nou gen pyebwa Huffman nou
kote pou li ale nan B, ki ta ka jis pou ti jan nan 1
ak Lè sa a, pou li ale nan Yon nou ta gen 01 ak Lè sa a, C ki gen 00.
Se konsa, isit la nou wè ke nou ap fondamantalman ki reprezante sa yo charaktèr ak swa Bits 1 oswa 2
kote B a, kòm prevwa, gen omwen nan.
Lè sa a, nou te espere C rive gen pi plis nan yo, men depi li nan tankou yon ti Huffman pyebwa,
Lè sa a, Yon lan tou se reprezante pa 2 Bits kòm opoze a yon kote nan mitan an.
>> Jis ale sou yon lòt egzanp senp nan pye bwa a Huffman,
di ou gen fisèl la "Hello."
Ki sa ou fè se premye fwa ou ta di konbyen fwa H parèt nan sa a?
H parèt yon sèl fwa ak Lè sa a, e parèt yon sèl fwa ak Lè sa a, nou gen l parèt de fwa
ak o parèt yon fwa.
Se konsa, Lè sa a, nou espere ki lèt yo dwe reprezante pa genyen pi piti kantite Bits?
[Elèv] l. >> L. Yeah. l ki dwat.
Nou atann pou l yo dwe reprezante pa genyen pi piti kantite Bits
paske l se itilize pi nan fisèl la "Hello."
Sa mwen ap pral fè koulye a, se trase soti sa yo nœuds.
Mwen gen 1, ki se H, ak Lè sa a, yon lòt 1, ki se e, ak Lè sa a, yon 1, ki se o -
kounye a mwen mete yo nan lòd - ak Lè sa a, 2, ki se l.
Lè sa a, mwen di wout la ke mwen bati yon pyebwa Huffman se jwenn nœuds yo 2 ak fwekans yo pi piti
epi fè yo frè ak sè pa kreye yon ne paran yo.
Isit la nou gen 3 nœuds ak frekans ki pi ba a. Yo ap tout 1.
Se konsa, isit la nou chwazi ki youn nou pral konekte premye.
Se pou nou di mwen chwazi H la ak e a.
Sòm la 1 + 1 se 2, men sa a ne pa gen yon lèt ki asosye ak li.
Li jis kenbe valè a.
Koulye a, nou gade nan 2 pwochen fwekans yo ki pi ba.
Sa a 2 ak 1. Yo ki te kapab swa nan sa yo 2, men mwen pral chwazi yon sèl sa a.
Sòm la se 3.
Lè sa a, finalman, mwen sèlman gen 2 bò gòch, se konsa Lè sa a, ki vin 5.
Lè sa a, isit la, kòm espere, si mwen ranpli nan kodaj la pou sa,
1S yo toujou branch nan dwa ak 0s yo se youn nan bò gòch.
Lè sa a, nou gen l reprezante pa jis ti jan 1 ak Lè sa a, o la pa 2
ak Lè sa a, e nan pa 2 epi Lè sa a, H a tonbe desann nan 3 miyèt moso.
Se konsa, ou ka transmèt mesaj sa a "Alo" olye pou yo aktyèlman lè l sèvi avèk karaktè yo
pa jis 0s ak 1S.
Sepandan, sonje ke nan ka plizyè nou te gen relasyon ak frekans nou an.
Nou te ka genyen swa ansanm H la ak o an premye petèt.
Oswa Lè sa a, pita sou lè nou te lan l reprezante pa 2
kòm byen ke ansanm nan yon sèl reprezante pa 2, nou te ka genyen lye swa youn.
>> Se konsa, lè ou voye 0s ak 1, ki aktyèlman pa garanti a
ki benefisyè a ka rive li mesaj ou a dwa koupe baton an
paske yo pa ta ka konnen ki desizyon ou te fè.
Se konsa, lè nou ap fè fas ak konpresyon Huffman,
yon jan kanmenm nou oblije di benefisyè a nan mesaj nou an ki jan nou deside -
Yo bezwen konnen kèk kalite enfòmasyon anplis
nan adisyon a mesaj la konprese.
Yo bezwen konprann sa pyebwa sa a aktyèlman sanble,
ki jan nou aktyèlman te fè desizyon sa yo.
>> Isit la nou te jis ap fè kèk egzanp ki baze sou konte aktyèl la,
men pafwa ou ka genyen tou yon pyebwa Huffman
ki baze sou frekans lan nan ki lèt parèt, epi li pwosesis la egzak menm.
Men mwen ap eksprime li an tèm de pousantaj oswa fraksyon yon,
e konsa isit la egzak menm bagay la.
Mwen jwenn 2 ki pi ba, rapò kantite yo, 2 nan pwochen ki pi ba, sòm la yo,
jouk tan mwen genyen yon pye bwa plen.
Menm si nou ta ka fè li swa fason, lè nou ap fè fas ak pousantaj,
sa vle di nou ap divize bagay sa yo ak fè fas ak desimal ou pito flote
si nou ap panse sou done estrikti nan yon tèt.
Ki sa nou konnen sou cha?
Ki sa ki nan yon komen pwoblèm lè nou ap fè fas ak cha?
[Elèv] enpresizyon aritmetik. >> Yeah. Enpresizyon.
Paske nan enpresizyon pwen k ap flote, pou sa a pset pou nou asire
ke nou pa pèdi nenpòt valè, Lè sa a, nou ap aktyèlman yo pral fè fas ak konte a.
Se konsa, si ou te panse a yon ne Huffman, si ou gade tounen nan estrikti a isit la,
si ou gade nan sa yo vèt li gen yon frekans ki asosye ak li
kòm byen ke li lonje dwèt nan yon ne a gòch li yo kòm osi byen yon ne a dwat li yo.
Lè sa a, yo menm ki wouj la tou gen yon karaktè ki asosye ak yo.
Nou pa pwal fè sa ki apa pou paran yo ak Lè sa a, nœuds yo final la,
ki nou al gade nan kòm fèy yo, men pito sa yo pral jis yo gen valè nil.
Pou chak ne n ap gen yon karaktè, senbòl la ki ki ne reprezante,
Lè sa a, yon frekans kòm osi byen yon konsèy ak pitit li yo bò gòch kòm byen ke pitit dwa li yo.
Fèy yo, ki se nan pati anba a trè, ta yo te genyen tou endikasyon ne
sou bò goch yo ak sou bò dwat yo, men yo depi valè sa yo yo pa lonje dwèt nœuds reyèl,
sa ki ta valè yo ta dwe ye? >> [Elèv] nil. >> Nil. Egzakteman.
Isit la nan yon egzanp sou kouman ou ta ka reprezante frekans lan nan flote,
men nou ap pral fè fas ak li avèk nonm antye yo,
se konsa tout mwen te fè se chanje kalite a done a.
>> Se pou nou ale nan yon ti jan plis nan yon egzanp konplèks.
Men, kounye a ke nou te fè sa ki senp, li la jis pwosesis la menm.
Ou jwenn 2 ki pi ba fwekans yo, rapò kantite fwekans yo
ak sa a, se frekans nan nouvo nan ne paran ou a,
ki lè sa a lonje dwèt sou bò goch li yo ak branch nan 0 ak dwa a ak branch nan 1.
Si nou gen fisèl la "Sa a se cs50," Lè sa a, nou konte konbyen fwa se T mansyone,
h mansyone, mwen, s, c, 5, 0.
Lè sa a, sa mwen te fè isit la se ak nœuds yo wouj mwen jis te plante,
M 'te di mwen pral gen sa yo karaktè evantyèlman nan fon an nan pyebwa m' yo.
Moun sa yo ki pwal gen tout fèy yo.
Lè sa a, sa mwen te fè se mwen Ranje yo nan frekans nan Ascending lòd,
ak sa a se aktyèlman fason la ki kòd la pset fè li
se li kalite li pa frekans ak Lè sa a, lòd avèk lèt ​​alfabè.
Se konsa, li gen nimewo yo premye ak Lè sa a, lòd avèk lèt ​​alfabè pa frekans lan.
Lè sa a, ki sa mwen ta fè se mwen ta jwenn ki pi ba a 2. Sa a 0 ak 5.
Mwen ta rapò kantite yo, epi ki nan 2. Apre sa, mwen ta kontinye, jwenn pwochen 2 ki pi ba a.
Moun sa yo se 1S an de, ak Lè sa a, sa yo vin 2 kòm byen.
Koulye a mwen konnen pwochen etap mwen yo pral rantre nan nimewo ki pi ba a,
ki se T a, 1 an, ak Lè sa a, chwazi youn nan nœuds yo ki gen 2 kòm frekans lan.
Se konsa, isit la nou gen 3 opsyon.
Ki sa ki mwen pral fè pou glise nan se jis vizyèlman ordonne yo pou ou
pou ke ou ka wè ki jan mwen bati li.
Ki sa ki kòd la ak kòd distribisyon ou a pral nan fè ta dwe enskri nan youn nan T
ak ne a 0 ak 5.
Se konsa, Lè sa a, ki montan lajan nan 3, ak Lè sa a, nou kontinye pwosesis la.
2 a ak 2 a kounye a se ki pi ba a, se konsa Lè sa a, sa yo sòm a 4.
Tout moun swiv byen lwen tèlman? Oke.
Lè sa a, apre ke nou gen 3 an ak 3 an ki bezwen ajoute leve,
Se konsa ankò mwen jis oblije chanje li pou ke ou ka wè vizyèlman konsa ke li pa jwenn twò lèd.
Lè sa a, nou gen yon 6, epi Lè sa a, etap final nou an, se kounye a ke nou gen sèlman 2 nœuds
nou rapò kantite moun ki fè rasin nan pyebwa nou an, ki se 10.
Ak nimewo a 10 fè sans paske chak ne reprezante,
valè yo, nimewo frekans yo, te konbyen fwa yo parèt nan fisèl la,
ak Lè sa a, nou gen 5 karaktè nan fisèl nou an, se konsa ki fè sans.
Si nou gade moute nan ki jan nou ta aktyèlman programme li,
kòm espere, mwen la ak s la, ki parèt pi souvan nan
yo reprezante pa kantite mwens nan miyèt moso.
>> Fè atansyon isit la.
Nan Huffman pye bwa ka a aktyèlman zafè.
Yon S majuskul se diferan pase yon s miniskil.
Si nou te gen "Sa a se CS50" ak lèt ​​majiskil, lè sa a yo nan miniskil ta sèlman parèt de fwa,
ta dwe yon ne ak 2 kòm valè li yo, ak Lè sa a, majuskul S ta ka sèlman yon fwa.
Se konsa, Lè sa a, pye bwa ou ta ka chanje estrikti paske ou gen aktyèlman gen yon fèy siplemantè isit la.
Men, sòm total la ta dwe toujou 10.
Sa a ki sa nou ap aktyèlman yo pral rele kontwòl la,
adisyon a nan tout konte yo.
>> Kounye a ke nou te kouvri Huffman pye bwa, nou ka plonje nan feyte Huff'n, pset la.
Nou pwal kòmanse avèk yon seksyon nan kesyon,
ak sa a ki pral fè ou jwenn abitye ak pye bwa binè ak kouman yo opere alantou ke:
desen nœuds, kreye pwòp ou a tipedèf struct pou yon ne,
ak wè kijan ou ta ka insert nan yon pyebwa binè, youn ki nan Ranje,
Travelers li, epi bagay sa yo tankou sa.
Konesans sa a se definitivman pral ede ou lè ou plonje nan pòsyon nan feyte Huff'n
nan pset la.
Nan edisyon an estanda nan pset a, travay ou a se fè aplike feyte,
ak nan vèsyon an aker travay ou a se fè aplike Huff.
Ki sa ki Huff fè se li pran tèks ak Lè sa a, li tradui l 'nan 0s a ak 1,
Se konsa pwosesis ki nou te fè sa pi wo a kote nou konte fwekans yo
ak Lè sa a, te fè pye bwa a ak Lè sa a, te di, "Kouman pou mwen jwenn T?"
T ap reprezante pa 100, bagay sa yo tankou sa,
ak Lè sa a, Huff ta pran tèks la ak Lè sa a, pwodiksyon ki binè.
Men tou paske nou konnen ke nou vle pèmèt benefisyè nou an mesaj la
rkree egzak pyebwa a menm, li tou gen ladan enfòmasyon sou konte yo frekans.
Lè sa a, ak feyte nou yo bay yon dosye binè nan 0s ak 1S
yo ak ba yo tou enfòmasyon sou fwekans yo.
Nou tradui tout nan tout sa yo tounen 0s ak 1S nan mesaj orijinal la ki te,
se konsa n ap dekonprese sa.
Si ou ap fè edisyon an estanda, ou pa bezwen aplike Huff,
se konsa Lè sa a, ou ka jis sèvi ak aplikasyon an anplwaye nan Huff.
Gen enstriksyon nan espèk a sou ki jan fè sa.
Ou ka kouri aplikasyon an anplwaye nan Huff sou yon dosye tèks sèten
ak Lè sa a, sèvi ak ke randman kòm opinyon ou nan soufle.
>> Kòm mwen mansyone anvan, nou gen yon anpil nan kòd distribisyon pou yon sèl sa a.
Mwen pral kòmanse ale atravè li.
Mwen pral pase pifò tan an sou la. Dosye h
paske se nan. dosye yo c, paske nou gen h la.
ak ki bay nou ak prototip yo nan fonksyon yo,
nou pa totalman bezwen konprann egzakteman -
Si ou pa konprann ki sa k ap pase nan. Dosye yo c, Lè sa a, pa enkyete twòp,
men definitivman eseye pran yon gade paske li ta ka bay kèk sijesyon
epi li itil nan jwenn itilize lekti kòd lòt moun.
>> Gade nan huffile.h, nan kòmantè yo li deklare yon kouch abstraction pou Huffman-kode dosye.
Si nou desann, nou wè ki di ke gen yon maksimòm de 256 senbòl ki nou ta ka bezwen kòd pou.
Sa gen ladan tout lèt nan alfabè a - majuskul ak miniskil -
ak Lè sa a, senbòl ak nimewo, elatriye
Lè sa a, isit la nou gen yon nimewo majik idantifye yon dosye Huffman-kode.
Nan yon kòd Huffman yo pwal santi yo gen yon nimewo majik sèten
ki asosye ak header la.
Sa a ta ka sanble jis nimewo yon o aza majik,
Men, si ou aktyèlman tradui l 'nan ASCII, lè sa a li aktyèlman eple soti Huff.
Isit la nou gen yon struct pou yon dosye Huffman-ankode.
Genyen nan tout nan karakteristik sa yo ki asosye avèk yon dosye Huff.
Lè sa a, desann isit la nou gen header la pou yon dosye Huff, se konsa nou rele li Huffeader
olye pou yo ajoute h siplemantè a paske li son menm bagay la tou de tout fason.
Bèl.
Nou gen yon nimewo majik asosye ak li.
Si li nan yon vrè Huff dosye, li te pral fè nimewo a moute pi wo a, yon sèl sa a majik.
Lè sa a, li pral gen yon etalaj.
Se konsa, pou chak senbòl, ki gen 256,
li pral fè yon lis ki sa frekans lan nan tout sa yo senbòl yo nan dosye a Huff.
Lè sa a, finalman, nou gen yon kontwòl pou fwekans yo,
ki ta dwe sòm total la nan tout sa yo frekans.
Se konsa, se sa ki yon Huffeader se.
Lè sa a, nou gen kèk fonksyon ki retounen ti jan nan pwochen nan dosye a Huff
kòm byen ke ekri yon ti jan nan dosye a Huff, ak Lè sa a, sa a fonksyon isit la, hfclose,
ki aktyèlman fèmen dosye a Huff.
Anvan, nou te fè fas ak tou dwat jis fkloz,
Men, lè ou gen yon dosye Huff, olye pou yo fclosing li
ki sa w ap aktyèlman pral fè se hfclose ak hfopen li.
Moun sa yo se fonksyon espesifik nan dosye yo Huff ke nou ap pral fè fas ak.
Lè sa a, isit la nou li nan header a ak Lè sa a, ekri header la.
>> Jis pa lekti. H dosye a nou kapab kalite ka resevwa yon sans de sa ki yon dosye Huff ta kapab,
sa ki karakteristik li gen, san yo pa aktyèlman ale nan huffile.c a,
ki, si nou plonje nan, a pwal yon ti jan plis konplèks.
Li te gen tout nan dosye a mwen / O isit la ki gen rapò ak pwent.
Isit la nou wè ke lè nou rele hfread, pou egzanp, li la toujou fè fas ak frèd.
Nou pa resevwa debarase de sa yo fonksyon antyèman, men nou ap voye sa yo li dwe te pran swen nan
andedan dosye a Huff olye pou yo fè tout sa a li tèt nou.
Ou ka santi lib yo analysis nan sa a si w ap kirye
epi ale epi kale kouch a tounen yon ti jan.
>> Dosye a pwochen ke nou ap pral gade se tree.h.
Anvan nan solisyon an glisad nou te di nou espere yon ne Huffman
epi nou te fè yon ne struct tipedèf.
Nou atann pou li genyen yon senbòl, frekans yon, ak Lè sa a, 2 zetwal ne.
Nan ka sa a sa n ap fè se sa a se esansyèlman menm bagay la tou
eksepte olye pou yo ne nou pral rele yo pyebwa yo.
Nou gen yon fonksyon ki lè w rele fè pyebwa li retounen ou yon konsèy pyebwa.
Retounen nan ortograf, lè ou te konn fè yon ne nouvo
ou te di ne * nouvo mo = malok (sizof) ak bagay sa yo tankou sa.
Fondamantalman, mktree yo pral fè fas ak ki pou ou.
Menm jan tou, lè ou vle retire yon pyebwa,
pou ki nan esansyèlman libere pyebwa sa a lè w ap fè ak li,
olye pou yo fòmèlman rele gratis sou sa, w ap aktyèlman jis ale nan sèvi avèk fonksyon an rmtree
ki kote ou pase nan konsèy la ak sa yo ki pye bwa yo epi Lè sa a, tree.c pral pran swen nan ke pou ou.
>> Nou gade nan tree.c.
Nou atann pou fonksyon yo menm eksepte wè aplikasyon sa a tou.
Kòm nou espere, lè w rele mktree li mallocs gwosè a nan yon pye bwa nan yon konsèy,
inisyalizasyon tout valè yo nan valè a nil, se konsa 0s oswa NULLs,
ak Lè sa a, retounen konsèy la ak sa yo ki pyebwa ke ou te jis malloc'd ba ou.
Isit la lè ou rele retire pye bwa li premye fè asire w ke ou pa ap doub libere.
Li fè asire w ke ou gen aktyèlman yon pye bwa ki ou vle yo retire.
Isit la paske yon pye bwa gen ladan tou timoun li yo,
ki sa sa a fè se li recursive rele retire pye bwa nan ne an gòch nan pye bwa a
kòm byen ke ne a dwat.
Anvan li libere paran an, li bezwen yo libere timoun yo kòm byen.
Paran tou se ka ranplase ak rasin.
Premye paran an tout tan, se konsa tankou gwo-gran-gran gwo granpapa a-
oswa pyebwa grann, premye nou dwe libere desann nivo yo an premye.
Se konsa, Traverse jouk anba a, gratis sa yo, ak Lè sa a, vin tounen moute, gratis sa yo, elatriye
Se konsa, sa a, se pye bwa.
>> Koulye a, nou gade nan forè.
Forest a se kote ou mete tout Huffman pye bwa ou an.
Li nan ki di ke nou pwal gen yon bagay yo rele yon konplo
ki gen ladan yon konsèy nan yon pyebwa kòm osi byen yon konsèy nan yon konplo yo rele pwochen.
Ki sa ki fè sa ki estrikti sa a kalite gade tankou?
Li kalite di li sou la.
Dwa sou isit la.
Yon lis lye.
Nou wè ke lè nou gen yon konplo se tankou yon lis lye nan kav.
Yon forè defini kòm yon lis lye nan kav,
e konsa estrikti a nan forè se nou ap jis pral gen yon konsèy trase premye nou
e ke konplo a gen yon pye bwa nan li ou pito lonje dwèt nan yon pyebwa
ak Lè sa a, pwen trase nan pwochen, se konsa sou ak pou fè.
Pou fè yon forè nou rele mkforest.
Lè sa a, nou gen kèk fonksyon trè itil isit la.
Nou gen ranmase kote ou pase nan yon forè ak Lè sa a, valè a retounen se yon * Tree,
yon konsèy nan yon pyebwa.
Ki sa ki chwazi pral fè se li pral ale nan forè a ke w ap lonje dwèt
Lè sa a, retire yon pye bwa ak frekans ki pi ba a soti nan ki forè
ak Lè sa a, ba ou konsèy la ak sa yo ki pyebwa.
Yon fwa ou rele chwazi, pyebwa a pa pral egziste nan forè a ankò,
men valè a retounen se konsèy la ak sa yo ki pyebwa.
Lè sa a, ou gen plant.
Depi ke ou pase nan yon konsèy nan yon pye bwa ki gen yon frekans ki pa 0,
sa plant ap fè se li pral pran forè a, pran pye bwa a, ak plant ki anndan pyebwa ki nan forè an.
Isit la nou gen rmforest.
Menm jan ak retire pye bwa, ki fondamantalman libere tout pyebwa nou yo pou nou,
retire forè pral gratis tout bagay ki genyen nan ke forè.
>> Si nou gade nan forest.c, nou pral espere wè omwen 1 rmtree lòd nan la,
paske gratis memwa nan forè a si yon forè gen pye bwa nan li,
Lè sa a, evantyèlman w ap ale nan gen yo retire sa yo pyebwa tou.
Si nou gade nan forest.c, nou gen mkforest nou an, ki se kòm nou espere.
Nou malok bagay sa yo.
Nou inisyalize trase nan premye nan forè a kòm nil paske li nan vid yo kòmanse avèk yo,
Lè sa a, nou wè chwazi, ki retounen pyebwa a ak pwa ki pi ba a, frekans ki pi ba a,
ak Lè sa a, vin debarase m de ki ne patikilye ki pwen ak sa yo ki pye bwa yo epi youn nan pwochen,
Se konsa li pran ki soti nan lis la lye nan forè a.
Lè sa a, isit la nou gen plant yo, ki mete anndan yon pye bwa nan lis la lye.
Ki sa ki forè se li joliman kenbe li Ranje pou nou.
Lè sa a, finalman, nou gen rmforest, epi, kòm espere, nou gen rmtree rele la.
>> Gade nan kòd la distribisyon twò lwen, huffile.c te pwobableman pa lwen pi di a yo konprann,
Lè nou konsidere ke dosye yo lòt tèt yo te trè senp yo swiv.
Ki gen konesans nou nan pwent e li bay lis lye ak sa yo,
nou te kapab swiv trè byen.
Men, tout sa nou bezwen vrèman asire w ke nou konprann konplètman se. Dosye yo h
paske ou bezwen yo dwe rele moun ki fonksyon, ki gen rapò ak valè sa yo retou,
se konsa asire w ke ou konprann tout sa aksyon ki pral fèt
nenpòt lè ou rele youn nan moun ki fonksyon.
Men, aktyèlman konprann andedan nan li se pa byen nesesè paske nou gen sa yo. Dosye h.
Nou gen 2 plis dosye kite nan kòd distribisyon nou an.
>> Se pou yo gade nan pil fatra.
Pil fatra nan kòmantè li yo isit la pran yon dosye Huffman-konprese
ak Lè sa a, tradui ak jete li tout kontni li yo deyò.
Isit la nou wè ke li nan rele hfopen.
Sa a se kalite mirwar pote * opinyon = fopen,
ak Lè sa a, ou pase nan enfòmasyon an.
Li nan prèske eksepte olye de yon * dosye w ap pase nan yon Huffile;
olye pou yo fopen w ap pase nan hfopen.
Isit la nou li nan header a an premye, ki se kalite ki sanble ak ki jan nou li nan header a
pou yon dosye bitmap.
Sa n ap fè isit la se tcheke yo wè si wi ou non header enfòmasyon an
gen nimewo a majik dwa ki endike ke li nan yon vrè Huff ranpli,
Lè sa a, tout moun sa yo chèk a asire w ke dosye a ke nou louvri a se yon dosye aktyèl huffed oswa ou pa.
Ki sa sa fè se li sorti fwekans yo nan tout nan senbòl yo ke nou ka wè
ki nan yon tèminal nan yon tablo grafik.
Nan pati sa a a pwal itil.
Li te gen yon ti jan ak li ti jan pa ti jan nan ti jan a varyab ak Lè sa a, simagri li soti.
Se konsa, si m 'te rele pil fatra sou hth.bin, ki se rezilta nan huffing yon dosye
lè l sèvi avèk solisyon an anplwaye yo, mwen ta jwenn sa a.
Li nan sorti tout moun sa yo karaktè ak Lè sa a, mete frekans la nan kote yo parèt.
Si nou gade, pi fò nan yo se 0s eksepte pou sa a: H, ki parèt de fwa,
ak Lè sa a, T, ki parèt yon fwa.
Lè sa a, isit la nou gen mesaj la reyèl nan 0s ak 1S.
Si nou gade nan hth.txt, ki se prezimableman mesaj orijinal la ki te huffed,
nou espere wè kèk HS ak teritwar an la.
Espesyalman, nou espere wè jis 1 T ak HS 2.
Isit la nou yo nan hth.txt. Li tout bon gen HTH.
Enkli nan la, malgre ke nou pa ka wè li, se yon karaktè newline.
Hth.bin nan dosye Huff tou se kodaj karaktè a newline kòm byen.
Isit la paske nou konnen lòd la se HTH ak Lè sa a, newline,
nou ka wè ki pwobableman se H la reprezante nan jis yon sèl 1
ak Lè sa a, T a se pwobableman 01 ak Lè sa a, H nan pwochen se 1 kòm byen
ak Lè sa a, nou gen yon newline endike pa de 0s.
Fre.
>> Lè sa a, finalman, paske nou ap fè fas ak miltip c. Ak. Dosye h,
nou pwal gen yon trè konplèks agiman du a,
e konsa isit la nou gen yon makfil ki fè pil fatra pou ou.
Men, aktyèlman, ou gen yo ale sou fè pwòp ou a puff.c dosye-a.
Makfil a aktyèlman pa fè fas ak fè puff.c pou ou.
Nou pap kite sa jiska ou edite makfil la.
Lè ou antre nan yon lòd tankou fè tout, pou egzanp, li pral fè tout nan yo pou ou.
Santi yo lib fè yon gade nan egzanp yo nan makfil soti nan pset ki sot pase a
kòm byen ke pral koupe nan yon sèl sa a yo wè ki jan ou ka kapab fè dosye feyte ou
pa koreksyon sa a makfil.
Sa a sou li pou kòd distribisyon nou an.
>> Yon fwa nou te vinn nan sa, Lè sa a, isit la nan jis yon lòt rapèl
nan ki jan nou ap pral fè fas ak nœuds yo Huffman.
Nou pa pwal yo dwe rele yo nœuds ankò; nou ap pral rele yo pye bwa
kote nou ap pral reprezante senbòl yo ak yon Char,
frekans yo, ki kantite evènman, ak yon antye relatif.
Nou ap lè l sèvi avèk sa paske li nan pi presi pase yon flote.
Lè sa a, nou gen yon lòt konsèy ak timoun nan bò gòch kòm byen ke timoun nan dwa.
Yon forè, kòm nou te wè, se jis yon lis lye nan pyebwa yo.
Alafen, lè nou bati dosye Huff nou an,
nou vle forè nou yo gen ladan jis 1 pyebwa -
1 pye bwa, 1 rasin ak timoun miltip.
Byen bonè nan lè nou te jis ap fè pye bwa Huffman nou an,
nou te kòmanse soti lè w mete tout nœuds yo sou ekran nou an
yo t'ap di konsa nou pwal gen sa yo nœuds,
evantyèlman yo pwal santi yo gen fèy yo, e sa se senbòl yo, sa a se frekans yo.
Nan forè nou si nou jis gen 3 lèt, ki nan yon forè nan 3 pye bwa.
Lè sa a, kòm nou ale sou, lè nou te ajoute paran a an premye,
nou te fè yon forè nan 2 pye bwa.
Nou retire 2 nan timoun sa yo soti nan forè nou yo ak Lè sa a, ranplase li ak yon ne paran
ki te gen sa yo nœuds 2 kòm timoun yo.
Lè sa a, finalman, etap dènye nou an ak fè egzanp nou an ak Kòm B a,, ak CS
ta dwe fè paran final la,
e konsa Lè sa a, ki ta ka pote konte total nou an nan pyebwa nan forè a nan 1.
tout moun wè ki jan ou kòmanse soti ak pye bwa miltip nan forè ou
ak fini ak 1 an? Oke. Fre.
>> Ki sa nou bezwen pou fè pou feyte?
Ki sa nou bezwen fè se asire ke, kòm toujou, yo di nou ki kalite a dwa a opinyon
pou nou ka aktyèlman kouri pwogram nan.
Nan ka sa a yo pwal santi yo dwe ban nou apre agiman premye yo lòd-liy
2 pi plis: dosye a ke nou vle dekonprimra ak pwodiksyon an nan dosye a dekonprime.
Men, yon fwa nou asire yo ke yo pase nou nan kantite lajan an dwa valè yo,
nou vle asire yo ke D 'la se yon dosye Huff oswa ou pa.
Lè sa a, yon fwa nou garanti ke li nan yon dosye Huff, lè sa a nou vle bati pyebwa nou yo,
bati pyebwa sa a tankou ke li matche ak pye bwa a pou moun sa a ki te voye mesaj la bati a.
Lè sa a, apre nou fin bati pyebwa a, Lè sa a, nou ka fè fas ak, nan 0s ak 1S yo ke yo te pase nan
swiv sa yo ansanm pyebwa nou paske li nan idantik,
ak Lè sa a, ekri mesaj sa soti, entèprete Bits yo tounen nan charaktèr.
Lè sa a, nan fen a paske nou ap fè fas ak endikasyon isit la,
nou vle asire ke nou pa genyen kote dlo ap koule memwa
e ke nou gratis tout bagay.
>> Garanti bon itilizasyon se chapo fin vye granmoun pou nou pa kounye a.
Nou pran nan yon D ', ki a pwal non an nan dosye a soufle,
ak Lè sa a, nou espesifye yon pwodiksyon,
Se konsa non an nan dosye a pou pwodiksyon an souple, ki pral dosye a tèks.
Sa a se l '. Epi, koulye a nou vle asire ke yo D 'a huffed oswa ou pa.
Panse tounen, te gen anyen nan kòd la distribisyon ki ta ka ede nou
ak konprann si yon dosye huffed oswa ou pa?
Te gen enfòmasyon ki nan huffile.c sou Huffeader la.
Nou konnen ke chak dosye Huff gen yon Huffeader asosye ak li ak yon kantite majik
kòm byen ke yon etalaj de fwekans yo pou chak senbòl
kòm osi byen yon kontwòl.
Nou konnen ke, men nou menm tou nou te pran yon gade vit nan dump.c,
nan ki li te lekti nan yon dosye Huff.
Se konsa, fè sa, li te gen a tcheke si li vrèman te huffed oswa ou pa.
Se konsa, petèt nou te ka sèvi ak dump.c kòm yon estrikti pou puff.c. nou
Retounen nan pset 4 lè nou te gen copy.c nan dosye ki kopye nan rgb tripl
epi nou entèprete sa pou Whodunit ak rdimansyonman,
Menm jan an, ki sa ou ta ka fè se jis kouri yo lòd, ki tankou cp dump.c puff.c
epi sèvi ak kèk nan kòd la a.
Sepandan, li pa k ap pase yo dwe kòm dwat nan yon pwosesis
pou tradui dump.c ou a nan puff.c,
men omwen li ba ou yon kote yo kòmanse
sou kòman yo asire ke yo D 'a aktyèlman huffed oswa ou pa
kòm byen ke yon bagay kèk lòt.
Nou te asire ke bon itilizasyon ak asire ke se opinyon nan huffed.
Chak fwa ke nou te fè ke nou te fè kont kouran bon erè nou an,
se konsa retounen ak yon moun kite fimen fonksyon an si gen kèk echèk rive, si gen nan yon pwoblèm.
>> Kounye a ki sa nou vle fè se bati pyebwa a vrè.
Si nou gade nan Forest, gen 2 fonksyon prensipal
ke nou ap pral vle vin trè abitye avèk yo.
Genyen nan plant la fonksyon Boolean ke plant yon pyebwa frekans ki pa 0 andedan forè nou yo.
Se konsa, gen ou pase nan yon konsèy nan yon forè ak yon konsèy nan yon pyebwa.
Quick kesyon: Konbyen forè ou pral gen lè w ap bati yon pyebwa Huffman?
Forè nou yo, se tankou twal nou an, dwa?
Se konsa, nou ap sèlman pral gen 1 forè, men nou pwal gen pye bwa miltip.
Se konsa, anvan ou rele plant yo, w ap prezimableman pral vle fè forè ou.
Gen yon lòd pou ke si ou gade nan forest.h sou ki jan ou ka fè yon forè.
Ou ka plante yon pye bwa. Nou konnen ki jan fè sa.
Lè sa a, ou ka tou chwazi yon pyebwa soti nan forè a,
retire yon pye bwa ak pwa a pi ba a epi ban nou konsèy la ak sa yo ki.
Panse tounen nan lè nou te fè egzanp yo tèt nou,
lè nou te fè desen li soti, nou tou senpleman jis ajoute lyen yo.
Men, isit la olye pou yo jis ajoute lyen yo,
panse a li pi plis pase jan w ap retire 2 nan moun ki nœuds ak Lè sa a, ranplase li pa yon lòt.
Yo eksprime ki an tèm de davwa epi plante,
w ap davwa 2 pye bwa ak Lè sa a, plante yon lòt pye bwa
ki gen sa yo pyebwa 2 ke ou te chwazi kòm timoun yo.
Yo pral bati pyebwa Huffman a, ou ka li nan senbòl yo ak fwekans yo nan lòd
paske Huffeader a bay sa gade ou,
ap ba ou yon etalaj de frekans yo.
Se konsa, ou ka ale pi devan ak jis inyore anyen ak 0 a nan li
paske nou pa vle 256 fèy nan fen li.
Nou sèlman vle ki kantite fèy ki karaktè
ke yo aktyèlman itilize nan dosye a.
Ou ka li nan sa yo senbòl, ak chak nan sa yo senbòl ki gen frekans ki pa 0,
sa yo pwal gen pyebwa.
Ki sa ou ka fè se chak fwa ou li nan yon senbòl frekans ki pa 0,
ou ka plante ki pyebwa ki nan forè an.
Yon fwa ou plante pyebwa yo nan forè a, ou ka rantre nan sa yo pyebwa kòm frè ak sè,
se konsa pral tounen nan plante ak davwa ki kote ou chwazi 2 ak Lè sa a, plant 1,
ki kote ke ou 1 plante a se paran an nan 2 timoun yo ke ou te keyi.
Se konsa, Lè sa a, fini ou rezilta a pwal yon pyebwa sèl nan forè ou.
Sa a se ki jan ou bati pyebwa ou a.
>> Genyen plizyè bagay ki ta kapab ale mal isit la
paske nou ap fè fas ak fè pye bwa ak nouvo fè fas ak endikasyon ak bagay sa yo tankou sa.
Anvan lè nou te fè fas ak endikasyon,
chak fwa nou malloc'd nou te vle asire w ke li pa t 'tounen nou yon valè konsèy nil.
Se konsa, nan plizyè etap nan pwosesis sa a gen pwal gen plizyè ka
kote pwogram ou an te kapab febli.
Ki sa ou vle fè se ou vle asire w ke ou okipe sa yo erè,
ak nan espèk a li di yo okipe yo grasyeu,
se konsa renmen enprime soti yon mesaj bay itilizatè a vle di yo poukisa pwogram nan gen kite fimen
ak Lè sa a, san pèdi tan kite l '.
Pou fè sa manyen erè, sonje ke ou vle tcheke li
chak fwa yon sèl ke ta kapab gen yon echèk.
Chak fwa yon sèl ke w ap fè yon konsèy nouvo
ou vle asire w ke sa a, se siksè.
Anvan sa nou itilize yo fè se fè yon konsèy ak nouvo malok li,
ak Lè sa a, nou ta tcheke si ke konsèy se nil.
Se konsa, gen pwal gen kèk ka kote ou jis ka fè sa,
men pafwa w ap aktyèlman rele yon fonksyon
e nan lespas de ki fonksyon, ki nan youn nan ki nan fè mallocing la.
Nan ka sa a, si nou tounen gade dèyè a kèk nan fonksyon yo nan kòd la,
kèk nan yo yo fonksyon Boolean.
Nan ka abstrè si nou gen yon fonksyon Boolean rele foo,
fondamantalman, nou ka asime ke nan adisyon a fè tou sa foo fè,
depi li nan yon fonksyon Boolean, li retounen vre oubyen fo -
vre si siksè, fo si se pa.
Se konsa, nou vle tcheke si valè a retounen nan foo se vre oubyen fo.
Si li nan fo, sa vle di ke nou ap pral vle enprime kèk kalite mesaj
ak Lè sa a, kite pwogram nan.
Ki sa nou vle fè se tcheke valè a retounen nan foo.
Si foo retounen fo, Lè sa a, nou konnen ke nou rankontre kèk kalite erè
e nou bezwen kite pwogram nou an.
Yon fason yo fè sa a se gen yon kondisyon kote fonksyon aktyèl la li menm se eta sante ou.
Di foo pran nan x.
Nou ka gen kòm yon kondisyon si (foo (x)).
Fondamantalman, sa vle di si nan fen pwomenad foo li retounen vre,
Lè sa a, nou ka fè sa a paske fonksyon an gen evalye foo
yo nan lòd yo evalye kondisyon an antye.
Se konsa, Lè sa a, lè sa a jan ou ka fè yon bagay si fonksyon an retounen vre epi se siksè.
Men, lè ou se kont kouran erè, ou sèlman vle kite fimen, si fonksyon ou retounen fo.
Ki sa ou ta ka fè se jis ajoute yon == ki fo oswa ki jis ajoute yon Bang nan devan li
ak Lè sa a, ou gen si (! foo).
Nan ki nan kò a ki kondisyon ou ta gen tout manyen la erè a,
se konsa renmen, "pa t 'kapab kreye pye bwa sa a" ak Lè sa a, retounen 1 oswa yon bagay tankou sa.
Ki sa ki sa li fè, menm si, se ke menm si foo tounen fo -
Di foo retounen vre.
Lè sa a, ou pa bezwen rele foo ankò. Sa se yon miskonsepsyon komen.
Paske li te nan yon kondisyon ou, li te deja evalye,
konsa ou te deja genyen rezilta a si w ap fè lè l sèvi avèk pye bwa oswa yon bagay tankou sa
oswa plant oubyen chwazi oswa yon bagay.
Li deja genyen ki valè. Li nan deja egzekite.
Se konsa, li itil nan itilize fonksyon Boolean kòm kondisyon an
paske si ou pa ou aktyèlman egzekite kò a nan riban an,
li ègzekutra fonksyon an de tout fason.
>> Dezyèm nou an etap dènye ap ekri mesaj la nan dosye a.
Yon fwa nou bati pyebwa a Huffman, lè sa a ekri mesaj la nan dosye a se trè senp.
Li trè senp kounye a nan jis swiv 0s la ak 1S.
Se konsa, pa konvansyon nou konnen ke nan yon pyebwa Huffman 0s la endike kite
ak 1S a endike dwat.
Se konsa, Lè sa a, si w li nan ti jan pa ti jan, chak fwa ke ou jwenn yon 0
ou pral swiv branch nan bò gòch, ak Lè sa a, chak fwa ou li nan yon 1
w ap ale nan swiv branch a dwat.
Lè sa a, w ap ale nan yo ap kontinye jouk ou frape yon fèy
paske fèy yo pwal gen nan fen branch yo.
Ki jan nou ka di si nou te frape yon fèy oswa ou pa?
Nou te di l 'devan.
[Elèv] Si endikasyon yo ki nil. >> Yeah.
Nou kapab di si nou te frape yon fèy si pwent yo nan pyebwa tou de bò gòch la ak dwa yo se nil.
Pafè.
Nou konnen nou vle li nan ti jan pa ti jan nan dosye Huff nou an.
Kòm nou te wè anvan an dump.c, ki sa yo te fè se yo li nan ti jan pa ti jan nan dosye a Huff
ak jis enprime konnen ki sa ki sa yo Bits yo te.
Nou pa pwal yo dwe fè sa. Nou ap pral fè yon bagay ki nan yon ti jan pi plis konplèks.
Men, sa nou kapab fè se nou ka pran ki ti jan nan kòd ki li nan ti jan an.
Isit la nou gen ti jan nan nonb antye relatif ki reprezante ti jan li ye kounye a ke nou ap sou.
Sa a pran swen de iteration tout Bits yo nan dosye a jiskaske ou frape nan fen dosye a.
Ki baze sou sa, Lè sa a, w ap ale nan vle gen kèk kalite iterator
Traverse pyebwa ou a.
Lè sa a, ki baze sou si wi ou non ti jan la se 0 oswa 1,
w ap ale nan vle swa deplase ki iterator a gòch la oswa deplase li a dwat a
tout wout la jouk ou frape yon fèy, se konsa tout wout la jouk ki ne ke ou se sou
pa lonje dwèt sou nenpòt ki plis nœuds.
Poukisa nou ka fè sa avèk yon dosye Huffman, men se pa Morse kòd?
Paske nan kòd Morse gen nan yon ti jan nan anbigwite.
Nou te ka fè tankou, O rete tann, nou te frape yon lèt nan tout wout la, se konsa petèt sa a se lèt nou an,
Lè nou konsidere ke si nou kontinye jis yon ti jan pi long, Lè sa a, nou ta gen frape yon lòt lèt.
Men, ki pa nan pwal rive nan kodaj Huffman,
pou nou ka Rest te asire ke wout la sèlman ke nou ap ale nan frape yon karaktè
se si timoun yo kite la ak dwa ki ne la yo se nil.
>> Finalman, nou vle libere tout nan memwa nou an.
Nou vle tou de pre dosye a Huff ke nou ve yo te fè fas ak
kòm byen ke retire tout nan pyebwa yo nan forè nou yo.
Ki baze sou aplikasyon ou an, w ap pwobableman pral vle rele retire forè
olye pou yo aktyèlman ale atravè tout tout nan pyebwa yo tèt ou.
Men, si ou te fè nenpòt pye bwa tanporè, ou pral vle libere sa.
Ou konnen kòd ou a pi bon, kidonk, ou konnen ki kote w ap allocation memwa.
Se konsa, si ou ale nan, kòmanse nan menm kontwòl F'ing pou malok,
wè nenpòt lè ou malok ak fè asire w ke ou libere nan tout sa
men Lè sa a, jis ale atravè tout kòd ou a,
konprann ki kote ou ka gen afekte memwa.
Anjeneral ou ta ka jis di, "Nan fen yon dosye mwen jis ale nan retire forè sou forè m 'yo,"
Se konsa, fondamantalman klè ke memwa, gratis ki,
"Ak Lè sa a, mwen tou ale nan fèmen dosye a ak Lè sa a, pwogram mwen ki pral kite."
Men, se tan sa a la sèlman ki pwogram ou an L Kite?
Non, paske pafwa gen ta ka fèt yon yon erè ki te rive.
Petèt nou pa t 'kapab louvri yon dosye oswa nou pa t' kapab fè yon lòt pye bwa
oswa kèk kalite erè ki te pase nan pwosesis la alokasyon memwa ak se konsa li tounen nil.
Yon erè ki te pase ak Lè sa a, nou tounen, yo kite fimen.
Se konsa, Lè sa a, ou vle asire w ke nenpòt ki lè posib ke pwogram ou a ka kite fimen,
ou vle libere tout nan memwa ou a la.
Li pa nan jis pral fèt nan fen anpil nan fonksyon prensipal ke ou kite kòd ou a.
Ou vle gade tounen nan chak egzanp ki kòd ou a potansyèlman ta ka retounen prematireman
ak Lè sa a, gratis kèlkeswa sa memwa fè sans.
Di ou te rele fè forè e ke tounen fo.
Lè sa a, pwobableman ou pa pral bezwen yo retire forè ou
paske ou pa gen yon forè ankò.
Men, nan chak pwen nan kòd la kote ou ta ka retounen prematireman
ou vle asire w ke ou libere nenpòt memwa posib.
>> Se konsa, lè nou ap fè fas ak delivre memwa epi ki gen fwit potansyèl,
nou vle pa sèlman sèvi ak jijman nou yo ak lojik nou
men tou sèvi ak Valgrind kapab detèmine si nou te libere tout memwa nou byen oswa ou pa.
Ou kapab swa kouri Valgrind sou feyte ak Lè sa a, ou gen tou pase l
nimewo a dwa a bay lòd-liy agiman Valgrind.
Ou ka kouri sa, men pwodiksyon an se yon ti jan skre.
Nou te vinn yon ti jan yo itilize li ak ortograf, men nou toujou bezwen yon ti jan plis èd,
se konsa Lè sa a, kouri li ak yon drapo kèk plis tankou fuit radyasyon-tcheke plen nan =,
ki pral pwobableman ba nou kèk pwodiksyon plis itil sou Valgrind.
>> Lè sa a, yon lòt pwent itil lè w ap debogaj se yo lòd, ki diff.
Ou ka jwenn aksè aplikasyon anplwaye a nan Huff, kouri sa sou yon dosye tèks,
ak Lè sa a, Sòti li nan yon dosye binè, yon binè Huff dosye, yo dwe espesifik.
Lè sa a, si ou kouri soufle pwòp ou a sou sa dosye binè,
Lè sa a, depreferans, dosye outputted tèks ou a pwal idantik
nan yon sèl orijinal la ke ou te pase pous
Isit la mwen sèvi ak hth.txt kòm egzanp lan, ak sa a, se yon sèl la te pale osijè de nan espèk ou a.
Sa a se literalman jis HTH ak Lè sa a, yon newline.
Men, definitivman santi yo lib, epi ou yo definitivman ankouraje yo sèvi ak pi long egzanp
pou dosye tèks ou.
>> Ou ka menm pran yon bal nan petèt konpresan ak Lè sa a, dekonpresyon
kèk nan dosye yo ke ou te itilize nan ortograf tankou Lagè ak Lapè
oswa Jane Austen oswa yon bagay tankou sa - ki ta ka kalite fre - oswa Austin Powers,
kalite ki gen rapò ak pi gwo dosye paske nou pa t 'vle vini desann nan li
si nou te itilize zouti nan pwochen isit la, ls-l.
Nou abitye a ls, ki fondamantalman lis tout sa ki nan anyè aktyèl nou yo.
Pase nan drapo l la-aktyèlman montre gwosè a nan tout sa yo dosye.
Si ou ale nan espèk a pset, li aktyèlman ap mache ou atravè kreye dosye a binè,
nan huffing li, epi ou wè sa a pou dosye ki piti anpil
espas pri a nan konpresan li epi li tradui tout enfòmasyon sa a
nan tout fwekans yo ak bagay sa yo tankou ki depas benefis aktyèl la
nan konpresan dosye a an plas an premye.
Men, si ou kouri li sou kèk fichye tèks pi long, Lè sa a, ou ta ka wè ke ou kòmanse jwenn kèk benefis
nan konpresan sa yo dosye.
>> Lè sa a, finalman, nou gen fin vye granmoun nou zanmi gdb, ki se definitivman pral vini an sou la men tou.
>> nou gen nenpòt kesyon sou Huff pye bwa oubyen pwosesis la petèt nan fè pyebwa yo
oswa nenpòt lòt kesyon ki sou feyte Huff'n?
Oke. Mwen pral rete alantou pou yon ti jan.
>> Di Bondye mèsi, tout moun. Sa a te solisyon 6. Ak bon chans.
>> [CS50.TV]