[Powered by Google Translate] [Праходжанне - Праблема Set 6]
[Zamyla Chan - Гарвардскі універсітэт]
[Гэта CS50. - CS50.TV]
>> Прывітанне ўсім, і дабро запрашаем Праходжанне 6: Huff'n Puff.
У Puff Huff'n тое, што мы робім, будзем мець справу з файламі Хафман сціснутага
, А затым пыхкаючы яго назад уверх, так распакавання гэтага,
так што мы можам перакладаць з 0 і 1, якія карыстальнік пасылае нам
і пераўтварыць яго назад у зыходны тэкст.
Pset 6, будзе вельмі выдатна, таму што вы ўбачыце некаторыя з інструментаў
якія вы выкарыстоўвалі ў PSET 4 і 5 і PSET роду аб'яднання іх у 1 вельмі акуратна канцэпцыі
калі вы прыходзіце думаць пра гэта.
>> Акрамя таго, магчыма, PSET 4 і 5 былі найбольш складаных psets, што мы павінны былі прапанаваць.
Такім чынам, з гэтага моманту, у нас ёсць гэта яшчэ 1 PSET ў C,
а пасля гэтага мы на вэб-праграмавання.
Так што віншую сябе для атрымання больш жорсткім горб CS50.
>> Пераходзячы да Puff Huff'n, наш інструментар для гэтага PSET збіраецеся быць Huffman дрэў,
таму разуменне не толькі як двайковыя дрэвы працу, але і спецыяльна Huffman дрэў,
як яны пабудаваны.
І тады мы будзем мець шмат размеркавання кода ў гэтым PSET,
і мы прыйшлі, каб убачыць, што на самай справе некаторыя з кода
Мы не зможам у поўнай меры зразумець ўсё ж,
і таму тыя будуць. з файламі, але потым іх суправаджаюць. ч. файлаў
дасць нам дастаткова разумення таго, што нам трэба, так што мы ведаем, як гэтыя функцыі працуюць
або па крайняй меры тое, што яны павінны рабіць - іх ўваходы і выхады -
нават калі мы не ведаем, што адбываецца ў чорным скрыні
ці не разумеюць, што адбываецца ў чорным скрыні ўнутры.
І, нарэшце, як звычайна, мы маем справу з новымі структурамі дадзеных,
канкрэтныя віды вузлоў, якія паказваюць на пэўныя рэчы,
і вось якая мае ручку і паперу не толькі для працэсу праектавання
і калі вы спрабуеце высветліць, як вашы PSET павінны працаваць
але і падчас адладкі.
Вы можаце мець GDB разам з пяром і паперай у той час як вы бераце тое, што значэнні,
дзе вашыя стрэлкі паказваюць, і таму падобнае.
>> Перш за ўсё, давайце паглядзім на дрэвы Хафман.
Huffman дрэў бінарныя дрэвы, а гэта азначае, што кожны вузел мае толькі 2 дзяцей.
У дрэў Хафман характэрным з'яўляецца тое, што найбольш частыя значэння
прадстаўлена найменшай колькасцю бітаў.
Мы бачылі ў лекцыі прыклады кода Морзэ, які выгляд кансалідаванага некалькі лістоў.
Калі вы спрабуеце перавесці або E, напрыклад,
вы перакладаеце, што часта, так што замест таго, каб выкарыстоўваць увесь набор бітаў
выдзелена на што звычайны тып дадзеных, сціскаць яго да менш,
, А затым гэтыя лісты, якія прадстаўлены радзей прадстаўлены з больш біт
таму што вы можаце сабе гэта дазволіць, калі вы весите з частот, што гэтыя літары з'яўляюцца.
У нас жа ідэя тут у дрэвы Huffman
дзе мы робім ланцуг, свайго роду шлях, каб дабрацца да пэўных знакаў.
І тады персанажы, якія маюць найбольш частоты
будуць прадстаўлены з найменшай колькасцю бітаў.
>> Спосаб, якім вы пабудаваць дрэва Хафман
шляхам размяшчэння ўсіх персанажаў, якія з'яўляюцца ў тэксце
і разліку іх частата, як часта яны з'яўляюцца.
Гэта можа быць альбо з рахунку, колькі раз гэтыя літары з'яўляюцца
ці, магчыма, адсотак з усіх знакаў, колькі кожны з'яўляецца.
І тое, што вы робіце, калі ў вас ёсць усё, што намецілі,
Затым вы паглядзіце на 2 нізкія частоты, а затым далучыцца да іх як браты і сёстры
дзе то бацькоўскі вузел мае частату, якая з'яўляецца сумай сваіх 2 дзяцей.
І тады вы па пагадненні сказаць, што левы вузел,
Вы будзеце вынікаць, што, згодна з 0 галіна,
, А затым правы вузел 1 філіяла.
Як мы бачылі ў азбуцы Морзэ, адзін глюк, што калі вы толькі што гукавы сігнал і гукавы сігнал
было неадназначным.
Гэта можа быць або 1 літару ці гэта можа быць паслядоўнасць з 2 літар.
І тое, што Huffman дрэў робіць гэта таму, што па характары персанажаў
або нашы канчатковыя фактычныя сімвалы быцця апошняга вузла на галінцы -
мы маем на ўвазе тых, хто, як лісце - з-за таго, што там не можа быць ніякай двухсэнсоўнасці
, У тэрмінах якой лісце вы спрабуеце кадаваць з паслядоўнасцю бітаў
таму што нідзе ўздоўж бітаў, якія складаюць 1 ліст
Вы будзеце сутыкацца яшчэ цэлы ліст, і там ня будзе ніякай блытаніны няма.
Але мы будзем ісці ў прыкладах, якія вы, хлопцы, можаце фактычна бачыць, што
замест нас проста кажу вам, што гэта праўда.
>> Давайце паглядзім на просты прыклад дрэва Хафман.
У мяне ёсць радок, што тут мае даўжыню 12 знакаў.
У мяне ёсць 4 У, 6 сняданак, і 2 Cs.
Маім першым крокам было б разлічваць.
Колькі разоў з'яўляюцца? Падобна 4 разы ў радок.
У з'яўляецца 6 разоў, а C з'яўляецца ў 2 разы.
Натуральна, што я збіраюся сказаць, я выкарыстоўваю B часцей за ўсё,
Таму я хачу, каб прадстаўляць B з найменшай колькасцю бітаў, найменшая колькасць 0 і 1.
А потым я таксама збіраюся чакаць C патрабаваць найбольшая колькасць 0 і 1, а таксама.
Першае, што я зрабіў тут я змясціў іх у парадку ўзрастання па частаце.
Мы бачым, што C і A, тыя нашы 2 нізкія частоты.
Мы ствараем бацькоўскі вузел, і што бацькоўскі вузел не мае лісце, звязаныя з ім,
але ў яго ёсць частата, якая з'яўляецца сумай.
Сума становіцца 2 + 4, які з'яўляецца 6.
Затым мы ідзём левай галіны.
Калі б мы былі на што 6 вузлоў, то мы будзем прытрымлівацца ад 0 да дабрацца да C
, А затым 1, каб дабрацца да A.
Так што цяпер у нас ёсць 2 вузла.
У нас ёсць значэнне 6, а затым у нас таксама ёсць яшчэ адзін вузел са значэннем 6.
І вось гэтыя 2 не толькі 2-нізкая, але і толькі 2, якія засталіся,
таму мы далучаемся да тых іншым бацькам, з сумай быцця 12.
Так што тут у нас ёсць дрэва Хафман
дзе, каб дабрацца да B, гэта было б проста біт 1
, А затым, каб дабрацца да нас будзе 01, а затым C які мае 00.
Такім чынам, тут мы бачым, што ў асноўным мы, якія прадстаўляюць гэтыя сімвалы з 1 або 2 біта
дзе B, як і меркавалася, мае найменшае.
І тады мы чакалі C, каб мець большасць, але так як гэта такі маленькі дрэва Хафман,
Затым таксама прадстаўлены 2 біта, а не дзесьці ў сярэдзіне.
>> Проста, каб перайсці на іншы просты прыклад дрэва Хафман,
ў вас ёсць радок "Hello".
Што вы робіце, спачатку вы б сказаць колькі разоў H з'явіцца ў гэтым?
H з'яўляецца адзін раз, а затым электроннай з'яўляецца адзін раз, і тады мы маем л з'яўляцца ў два разы
і пра якія з'яўляюцца адзін раз.
І так, то мы чакаем, якое літару, якая будзе прадстаўлена найменшай колькасцю біт?
[Студэнт] л. >> Л. Так. л правоў.
Мы чакаем, што я павінен быць прадстаўлены найменшую колькасць біт
таму што я за ўсё выкарыстоўваецца ў радок "Hello".
Што я буду рабіць цяпер выцягнуць гэтыя вузлы.
У мяне ёсць 1, які з'яўляецца H, а потым яшчэ 1, які з'яўляецца электроннай, а затым 1, што пра -
Прама цяпер я стаўлю іх у парадак - і затым 2, якая з'яўляецца л.
Тады я кажу так, як я пабудовы дрэва Хафман, каб знайсці 2 вузлоў з найменшымі частотамі
і зрабіць іх братамі і сёстрамі па стварэнні бацькоўскага вузла.
Тут у нас ёсць 3 вузлоў з самай нізкай частатой. Яны ўсе 1.
І вось мы выбраць, які з мы збіраемся звязаць у першую чаргу.
Дапусцім, я выбіраю H і E.
Сума 1 + 1 = 2, але на гэты вузел не мае лісце, звязаныя з ім.
Ён проста трымае значэнне.
Цяпер мы паглядзім на наступныя 2 нізкія частоты.
Гэта 2 і 1. Гэта можа быць любы з гэтых 2, але я збіраюся абраць гэтую.
Сума 3.
І, нарэшце, у мяне толькі 2 левых, так тое, што становіцца 5.
Тады тут, як і чакалася, калі я запаўняю ў кадоўцы для таго,
1s заўсёды правай галіны і 0 з'яўляюцца левую.
Тады мы маем л прадстаўлены толькі 1 біт, а затым на 2 O
, А затым е на 2, а затым H падае да 3 біт.
Такім чынам, вы можаце перадаваць гэта паведамленне "Hello", а на самай справе выкарыстання сімвалаў
на толькі 0 і 1.
Аднак варта памятаць, што ў шэрагу выпадкаў мы мелі сувязяў з нашай частаце.
Мы маглі б альбо далучыліся да H і O Год можа быць.
Ці потым, калі ў нас было л прадстаўлены 2
а таксама далучыўся да адной прадстаўлены 2, мы маглі бы звязаны ні адзін.
>> І таму, калі вы пасылаеце 0 і 1, што на самой справе не гарантуюць
што атрымальнік можа цалкам прачытаць паведамленне прама з месца ў кар'ер
таму што яны не маглі ведаць, якія рашэнні вы зрабілі.
Таму, калі мы маем справу з выкарыстаннем кампрэсіі Хафман,
так ці інакш мы павінны сказаць атрымальніка наша пасланне, як мы вырашылі -
Яны павінны ведаць, нейкі дадатковай інфармацыі
У дадатак да паведамлення сціснутым.
Яны павінны разумець, што дрэва на самай справе выглядае,
як мы на самай справе зрабілі гэтыя рашэнні.
>> Тут мы проста рабілі прыкладаў, заснаваных на фактычнае колькасць,
але часам вы таксама можаце мець дрэва Хафман
у залежнасці ад частаты, на якой літары з'яўляюцца, і гэта сапраўды такі ж працэс.
Тут я выказваю гэта ў тэрмінах працэнты або долі,
і вось адно і тое ж.
Я знаходжу, 2-нізкі, скласці іх, наступныя 2 нізкі, скласці іх,
пакуль у мяне ёсць поўнае дрэва.
Хоць мы маглі б зрабіць гэта ў любым выпадку, калі мы маем справу з працэнтамі,
, Што азначае, што мы дзяленнем рэчаў, і справа з дзясятымі або, хутчэй, плавае
калі мы думаем пра структуры дадзеных з галавы.
Што мы ведаем пра паплаўкоў?
Што такое агульная праблема, калі мы маем справу з паплаўком?
[Студэнт] недакладнасць арыфметыка. >> Так. Недакладнасць.
З-за якая плавае кропкай недакладнасць, для гэтага PSET, так што мы ўпэўненыя,
што мы не губляюць значэння, то на самай справе мы будзем мець справу з ім.
Так што калі вы павінны былі думаць вузла Хафман, калі вы паглядзіце на структуру тут,
калі вы паглядзіце на зялёныя яно мае частату звязаных з ім
а таксама ён паказвае на вузел, каб яго левы, а таксама вузел у сваім праве.
А потым чырвоныя там таксама ёсць характар, звязаны з імі.
Мы не збіраемся рабіць асобныя для бацькоў, а затым канчатковае вузлоў,
які мы называем лісцем, а тыя будуць проста пустыя значэння.
Для кожнага вузла мы будзем мець характар, знак, які ўяўляе вузел,
Затым частоты, а таксама паказальнік на яго левую дзіцяці, а таксама яго правы дзіцяці.
Лісце, якія знаходзяцца на самым дне, будзе таксама мець паказальнікі на ноды
злева ад іх, а таксама іх права, але так як гэтыя значэння не паказвае на фактычнае вузлоў,
што б іх кошт будзе? >> [Студэнт] NULL. >> NULL. Менавіта так.
Вось прыклад таго, як можна прадстаўляць частоты ў паплаўкоў,
але мы збіраемся мець справу з гэтым з цэлымі лікамі,
так што ўсё, што я зрабіў гэта змяніць тып дадзеных няма.
>> Давайце пяройдзем да крыху больш складаны прыклад.
Але цяпер, калі мы зрабілі простыя, гэта проста той жа працэс.
Вы знойдзеце 2-нізкія частоты, падвесці частот
і вось новая частата вашага бацькоўскага вузла,
, Які затым паказвае на яе левым з 0 філіяла і права з 1 філіяла.
Калі ў нас ёсць радок "Гэта CS50", то мы злічыць, колькі разоў будзе згадана T,
г згадвалася, I, S, C, 5, 0.
Затым, што я зрабіў тут з чырвонымі вузламі я проста пасадзіў,
Я сказаў, што я буду мець гэтыя сімвалы ў канчатковым выніку ў ніжняй частцы майго дрэва.
Тыя збіраюцца быць усё лісце.
Затым, што я зрабіў, я сартаваць іх па частаце ў парадку ўзрастання,
і гэта на самай справе так, што PSET код робіць гэта
гэта сартуе іх па частаце, а затым у алфавітным парадку.
Так яно і ёсць колькасць, а затым у алфавітным парадку па частаце.
Тады што я буду рабіць, я б знайсці 2 нізкая. Гэта 0 і 5.
Я б скласці іх, і вось 2. Тады я буду працягваць, знайсці бліжэйшыя 2 нізкая.
Гэтыя два 1s, а затым яны становяцца 2, а.
Цяпер я ведаю, што мой наступны крок будзе далучэнне да найменшай колькасцю,
якая з'яўляецца T, 1, а затым выбраць адзін з вузлоў, які мае 2 як частата.
Так што тут у нас ёсць 3 варыянту.
Што я буду рабіць для слайдаў толькі візуальна змяніць іх для вас
так што вы можаце бачыць, як я будую яго.
Які код і размеркавання кода збіраюцца рабіць будзе далучыцца да T 1
з 0 да 5 вузлоў.
Такім чынам, што сумы да 3, а потым мы працягнем працэс.
2 і 2 зараз з'яўляюцца самымі нізкімі, так што потым гэтыя сумы да 4.
Кожны наступны да гэтага часу? Добра.
А пасля гэтага ў нас ёсць 3 і 3, якія павінны быць дададзеныя ўверх,
так што зноў я проста уключыце яго, так што вы можаце бачыць візуальна так, каб ён не занадта брудным.
Тады ў нас ёсць 6, а затым наш апошні крок зараз, што ў нас ёсць толькі 2 вузлоў
Падсумоўваючы гэтыя каб карані нашай дрэва, якое роўна 10.
І лік 10 мае сэнс, паколькі кожны вузел ўяўляе,
іх значэнне, іх частата нумар, было, колькі разоў яны з'явіліся ў радок,
а то ў нас 5 знакаў у нашу ланцужок, так што мае сэнс.
Калі мы глядзім на тое, як мы на самай справе кадаваць яго,
Як і чакалася, я і S, якія з'яўляюцца часцей за ўсё
прадстаўлены найменшую колькасць біт.
>> Будзьце асцярожныя.
У дрэў Хафман выпадак на самай справе мае значэнне.
Вялікія S адрозніваецца ад маленькай с.
Калі б мы мелі "Гэта CS50" з вялікай літары, то малыя ы будзе з'яўляцца толькі ў два разы,
будзе вузел з 2 у якасці свайго значэння, а затым вялікія S будзе толькі адзін раз.
І тады ваша дрэва будзе змяніць структуры, таму што вы на самай справе маюць дадатковы ліст тут.
Але сума ўсё роўна будзе 10.
Гэта тое, што мы на самай справе будзе выклікам кантрольнай сумы,
Акрамя ўсіх падлікаў.
>> Зараз, калі мы разгледзелі Huffman дрэў, мы можам пагрузіцца ў Huff'n Puff, PSET.
Мы збіраемся пачаць з падзелу пытанняў,
і гэта адбываецца, каб вы прывыклі з бінарнымі дрэвамі і як працаваць вакол гэтага:
малявання вузлоў, ствараючы свой уласны ЬурейеЕ структуры для вузла,
і, бачачы, як вы маглі б уставіць у бінарным дрэве, той, які сартуецца,
праз яго, і да таго падобнае.
Гэта веданне, безумоўна, дапаможа вам, калі вы апускаецеся ў частцы Puff Huff'n
з PSET.
У стандартным выданні PSET, ваша задача складаецца ў рэалізацыі Puff,
і ў хакерскай версіі вашай задачай з'яўляецца рэалізацыя Хафф.
Што Хафф робіць гэта бярэ тэкст, а затым ён перакладае яго ў 0 і 1,
так што працэс, які мы зрабілі вышэй, дзе мы разлічвалі частот
, А затым зрабіў дрэва, а затым сказаў: "Як я магу атрымаць T?"
T прадстаўлена на 100, і да таго падобнае,
, А затым Хафф б тэкст, а затым выснову, што двайковы файл.
Але і таму, што мы ведаем, што мы хочам, каб нашы атрымальнік паведамлення
узнавіць дакладна такую ​​ж дрэва, яно таксама ўключае інфармацыю аб частаце адлікаў.
Затым з Puff дадзена двайковы файл з 0 і 1
і таксама з улікам інфармацыі аб частотах.
Мы пераводзім усе гэтыя 0 і 1 вяртаецца ў зыходнае паведамленне, што было,
так што мы распакавання гэтага.
Калі вы робіце Standard Edition, вам не трэба ажыццяўляць Хафф,
так, то вы можаце проста выкарыстоўваць персанал рэалізацыі Хафф.
Ёсць інструкцыі ў спецыфікацыі аб тым, як гэта зрабіць.
Вы можаце запусціць персаналу ажыццяўлення Хафф на пэўны тэкставы файл
а затым выкарыстоўваць гэты выхад як ваш ўклад у зацяжку.
>> Як я ўжо казаў, у нас ёсць шмат размеркавання кода для гэтага.
Я збіраюся пачаць хадзіць праз яго.
Я буду праводзіць вялікую частку часу на. Ч. файлаў
таму што ў. з файламі, таму што ў нас ёсць. г
і што дае нам прататыпы функцый,
Мы не ў поўнай меры павінны разумець дакладна -
Калі вы не разумееце, што адбываецца ў. Файлаў с, то не турбуйцеся занадта шмат,
але абавязкова паспрабую зірнуць, таму што гэта можа даць некаторыя падказкі
і гэта карысна, каб прывыкнуць да чытання кода іншых людзей.
>> Гледзячы на ​​huffile.h, у каментарах ён заяўляе пласт абстракцыі для Huffman-кадаваных файлаў.
Калі мы пойдзем ўніз, мы бачым, што ёсць максімум 256 знакаў, што мы, магчыма, спатрэбіцца коды.
Гэта ўключае ў сябе ўсе літары алфавіту - вялікія і малыя -
, А затым сімвалы і лічбы, і г.д.
Тады тут у нас ёсць чароўны нумар для ідэнтыфікацыі Huffman-кадаваных файлаў.
У кодзе Хафман яны будуць мець пэўную колькасць магіі
звязаныя з загалоўка.
Гэта можа выглядаць як выпадковае лік, магія,
Але калі вы на самой справе перакладаць яго ў ASCII, то гэта на самай справе выкладае Хафф.
Тут мы маем структуру для Хафман файл у кадоўцы.
Там усе гэтыя характарыстыкі, звязаныя з файлам Хафф.
Тады тут мы маем загаловак файла Хафф, таму мы называем яго Huffeader
Замест дадання дадатковых гадзін, таму што гучыць аднолькава ў любым выпадку.
Cute.
У нас ёсць магічнае лік звязаных з ім.
Калі гэта рэальны файл Хафф, гэта будзе нумар наверсе, гэта чароўны.
І тады яна будзе мець масіў.
Такім чынам, для кожнага знака, у якім ёсць 256,
ён збіраецца пералічыць, што частата гэтых знакаў у файле Хафф.
І, нарэшце, у нас ёсць кантрольная сума для частот,
, Якая павінна быць сума гэтых частотах.
Дык вось што Huffeader ёсць.
Тады ў нас ёсць некаторыя функцыі, якія вяртаюць наступны біт у файле Huff
а таксама піша трохі, каб файл Хафф, а затым гэтая функцыя тут, hfclose,
што на самой справе закрывае файл Хафф.
Раней мы мелі справу з прамым проста Fclose,
Але калі ў вас ёсць файл Хафф, а fclosing гэта
тое, што вы на самай справе збіраецеся зрабіць, гэта hfclose і hfopen яго.
Тыя канкрэтныя функцыі Хафф файлы, якія мы збіраемся мець справу.
Тады вось мы чытаем у загалоўку, а затым напісаць загаловак.
>> Проста чытаючы. Ч файла мы можам атрымаць від сэнс таго, што файл Хафф можа быць,
якія характарыстыкі ў яго ёсць, фактычна не ўдаючыся ў huffile.c,
, Які, калі мы паглыбімся ў, будзе крыху больш складана.
Ён мае ўсе файлавага ўводу / высновы тут справу з паказальнікамі.
Тут мы бачым, што калі мы называем hfread, напрыклад, гэта ўсё яшчэ справу з FREAD.
Мы не пазбавіцца ад гэтых функцый цалкам, але мы пасылаем тых, хто будзе клапаціцца
ўнутры файла Хафф а не рабіць усё гэта самі.
Вы можаце адчуваць сябе свабодна для сканавання праз гэта, калі вам цікава
і сыходзяць, а лупіну пласт назад няшмат.
>> Наступны файл, які мы збіраемся глядзець на гэта tree.h.
Да гэтага ў Пакрокавае кіраўніцтва слізгае мы сказалі, што мы чакаем Хафман вузла
і мы зрабілі ЬурейеЕ вузла структуры.
Мы чакаем, што гэта ёсць сімвал, частоты, а затым 2 зоркі вузла.
У гэтым выпадку тое, што мы робім гэта па сутнасці той жа
толькі замест вузла мы будзем называць іх дрэвамі.
У нас ёсць функцыя, якая пры выкліку зрабіць дрэва ён вяртае вам паказальнік дрэва.
Назад да Speller, калі вы рабілі новы вузел
Вы сказалі вузел * Новае слова = таНос (SizeOf) і таму падобнае.
У прынцыпе, mktree будзе мець справу з гэтым для вас.
Аналагічным чынам, калі вы хочаце выдаліць дрэва,
так што, па сутнасці, вызваляючы дрэва, калі вы скончыце з гэтым,
замест відавочнага выкліку бясплатна на тым, што на самой справе вы проста збіраецеся выкарыстоўваць функцыю rmtree
дзе вы перадаеце паказальнік на гэта дрэва, а затым tree.c клапоціцца аб гэтым за вас.
>> Мы глядзім у tree.c.
Мы чакаем, што тыя ж функцыі, за выключэннем ўбачыць рэалізацыю, а таксама.
Як мы і чакалі, калі вы тэлефануеце mktree гэта mallocs аб'ёму дрэва ў паказальнік,
ініцыялізуе ўсе значэння на NULL значэнне, так 0s або нулі,
і затым вяртае паказальнік на гэтае дрэва, якое вы толькі што malloc'd да вас.
Вось калі вы тэлефануеце выдаліць дрэва ён спачатку пераконваецца, што вы не падвойнае вызваленне.
Ён упэўнены, што ў вас сапраўды ёсць дрэва, якое вы хочаце выдаліць.
Вось таму, што дрэва таксама ўключае ў сябе дзяцей,
што яна робіць гэта рэкурсіўна выклікае выдаленне дрэў на левым вузле дрэва
а таксама права вузлоў.
Перш, чым ён вызваляе аднаго з бацькоў, ён павінен вызваліць дзяцей.
Бацька таксама ўзаемазаменныя з коранем.
Першы ў гісторыі аднаго з бацькоў, так як пра-пра-пра-пра-дзядуля
або бабуля дрэва, спачатку мы павінны вызваліць да ўзроўню першага.
Так што прайсці на дно, свабоднае іх, а затым вярнуцца ўверх, свабодныя тых, і г.д.
Так што гэта дрэва.
>> Цяпер мы паглядзім на лес.
Лес, дзе вы змясцуеце ўсе вашы дрэў Хафман.
Ён казаў, што мы будзем мець тое, што называецца ўчастак
, Які змяшчае паказальнік на дрэва, а таксама паказальнік на ўчастак называецца наступная.
Якая структура робіць гэты від выглядае?
Гэта збольшага кажа, што гэта там.
Права тут.
Звязаны спіс.
Мы бачым, што калі ў нас ёсць сюжэт гэта як звязаны спіс участкаў.
Лес вызначаецца як звязаны спіс участкаў,
і так структуры лесу мы проста будзем мець паказальнік на нашым першым участку
і што ўчастак мае дрэва ў яго ці, хутчэй, паказвае на дрэве
, А затым паказвае на наступны ўчастак, гэтак далей, і гэтак далей.
Для таго, каб лес мы называем mkforest.
Тады ў нас ёсць некалькі даволі карысных функцый тут.
Мы павінны выбраць, дзе вы праходзьце ў лес, а затым вяртаецца значэнне дрэва *,
паказальнік на дрэва.
Які выбар зробіць, яна будзе ісці ў лес, што вы паказваючы на
затым выдаліць дрэва з самай нізкай частатой ад лесу
, А затым даць вам паказальнік на дрэва.
Пасля таго як вы патэлефануеце выбраць, дрэва не будзе існаваць у лесе больш,
але вяртаецца значэнне з'яўляецца паказальнікам на гэтым дрэве.
Тады ў вас ёсць завод.
Пры ўмове, што вы перадаеце паказальнік на дрэва, якое мае не-0 частот,
што завод будзе рабіць гэта будзе лес, узяць дрэў і раслін, што дрэва ўнутры лесу.
Тут мы маем rmforest.
Падобныя выдаліць дрэва, якое ў асноўным вызваліў усіх нашых дрэў для нас,
выдаліць лес будзе бясплатна ўсё, што змяшчаецца ў гэтым лесе.
>> Калі мы паглядзім на forest.c, мы чакаем, што па крайняй меры 1 rmtree каманды там,
таму што, каб вызваліць памяць у лесе, калі лес ёсць дрэвы ў ім,
то ў канчатковым выніку вы будзеце мець, каб выдаліць гэтыя дрэвы таксама.
Калі мы паглядзім на forest.c, у нас ёсць mkforest, які, як мы чакаем.
Мы таНос рэчы.
Мы ініцыялізуем першы ўчастак у лесе, NULL, таму што гэта пустыя Пачнем з таго,
Затым мы бачым, выбар, які вяртае дрэва з нізкім вагой, нізкай частаты,
, А затым пазбаўляецца ад канкрэтнага вузла, які паказвае на гэтае дрэва і наступны,
таму ён прымае, што з звязанага спісу лесу.
А то вось у нас ёсць завод, які ўстаўляе дрэва ў звязаным спісе.
Што лясоў робіць гэта прыгожа трымае яго адсартаваныя для нас.
І, нарэшце, у нас ёсць rmforest і, як і чакалася, у нас ёсць rmtree завецца там.
>> Гледзячы на ​​распаўсюд кода да гэтага часу, huffile.c была, верагодна, нашмат цяжэй зразумець,
у той час як іншыя файлы самі па сабе былі даволі простыя, каб прытрымлівацца.
З нашымі ведамі паказальнікі і звязаныя спісы і такія,
мы былі ў стане прытрымлівацца даволі добра.
Але ўсё, што трэба, каб сапраўды пераканацца, што мы цалкам разумеем гэта. Ч. файлаў
таму што вы павінны быць выклікам гэтых функцый, вырашэнню гэтых вяртаюцца значэнняў,
таму пераканайцеся, што вы цалкам разумееце, якое дзеянне будзе выконвацца
кожны раз, калі вы патэлефануеце па адным з гэтых функцый.
Але на самай справе разумення ўнутры яго зусім не абавязкова, таму што мы ёсць тыя. Ч. файлаў.
У нас ёсць яшчэ 2 файлы, якія застаюцца ў нашай размеркавання кода.
>> Давайце паглядзім на сметнік.
Дамп яго каментар тут займае Хафман сціснутых файлаў
, А затым перакладае і звалкі ўсе яго змесціва з.
Тут мы бачым, што яна кліча hfopen.
Гэта свайго роду люстраное ў файл * ўваход = Еореп,
а затым вы праходзіце ў інфармацыі.
Гэта амаль ідэнтычныя, за выключэннем замест файла * вы перадаеце ў Huffile;
замест Еореп вы перадаеце ў hfopen.
Тут мы чытаем у загалоўку першай, якая з'яўляецца своеасаблівай падобна таму, як мы чытаем у загалоўку
для растравых файлаў.
Што мы робім тут, правяраючы, ці з'яўляецца інфармацыя загалоўка
змяшчае права магічнае лік, якое паказвае, што гэта рэальны файл Хафф,
Затым усе гэтыя праверкі, каб пераканацца, што файл, які мы адкрытыя з'яўляецца актуальнай фыркнуў файл ці не.
Што гэта робіць ён выводзіць частоты ўсе знакі, якія мы бачым,
ў тэрмінале ў графічную табліцу.
Гэтая частка будзе карысна.
Ён мае трохі, і чытаецца па частках ў зменную трохі, а затым раздрукоўвае яе.
Так што, калі б я быў патэлефанаваць звалкі на hth.bin, якая з'яўляецца вынікам пыхкаючы файл
выкарыстанне супрацоўнікамі рашэнні, я хацеў бы атрымаць гэта.
Гэта выводзіць усе гэтыя персанажы, а затым пакласці частоты, на якіх яны з'яўляюцца.
Калі мы паглядзім, большасць з іх 0s за выключэннем гэтага: H, якая з'яўляецца двойчы,
, А затым T, які з'яўляецца адзін раз.
А то тут мы маем фактычнае паведамленне ў 0 і 1.
Калі мы паглядзім на hth.txt, які меркавана зыходнае паведамленне, якое было фыркнуў,
мы чакаем ўбачыць некаторыя Hs і Ц. там.
У прыватнасці, мы чакаем ўбачыць толькі 1 і 2 T Hs.
Тут мы знаходзімся ў hth.txt. Гэта сапраўды мае HTH.
Ўваходзіць у там, хоць мы не бачым, з'яўляецца сімвалам новага радка.
Hth.bin Хафф файл таксама кадаваньне сімвала новага радка, а таксама.
Тут, таму што мы ведаем, што парадак HTH, а затым радкі,
мы бачым, што, верагодна, H прадстаўлена толькі адной 1
, А затым, верагодна, T 01 і затым на наступны Н 1, а
а то ў нас новая радок пазначаецца двума 0s.
Cool.
>> І, нарэшце, таму, што мы маем справу з некалькімі. З і. Ч. файлаў,
мы будзем мець даволі складаны аргумент для кампілятара,
і вось у нас ёсць Makefile, які робіць дамп для вас.
Але на самай справе, вы павінны пайсці аб стварэнні ўласнага puff.c файл.
Makefile на самай справе не мае справу з стварэннем puff.c для вас.
Мы сыходзім, што да Вас, каб змяніць Makefile.
Калі вы ўводзіце каманду зрабіць усё, напрыклад, ён зробіць усё гэта за вас.
Вы можаце паглядзець на прыклады Makefile з мінулага PSET
а таксама сыходзіць з гэтага, каб убачыць, як вы маглі б зрабіць вашу Puff файл
шляхам рэдагавання гэтага файла Makefile.
Вось пра гэта наш размеркавання кода.
>> Як толькі мы прайшлі праз гэта, то тут проста яшчэ адзін напамін
пра тое, як мы збіраемся мець справу з вузламі Хафман.
Мы не збіраемся быць называючы іх вузлоў больш, мы збіраемся называць іх дрэвамі
дзе мы збіраемся прадстаўляць іх знак знак,
іх частата, лік уваходжанняў, з цэлым.
Мы выкарыстоўваем, таму што гэта больш дакладнае, чым плаваць.
А то ў нас яшчэ адзін паказальнік налева дзіцяці, а таксама правы дзіцяці.
Лес, як мы бачылі, гэта проста звязаны спіс дрэў.
У канчатковым рахунку, калі мы будуем нашу Хафф файл,
Мы хочам, каб наш лес, каб утрымліваць толькі 1 дрэва -
1 дрэва, 1 корань з некалькімі дзецьмі.
Раней, калі мы былі проста робіць нашу Huffman дрэў,
Мы пачалі з размяшчэння ўсіх вузлоў на нашым экране
і кажуць, што мы збіраемся, каб гэтыя вузлы,
у канчатковым выніку яны збіраюцца быць лісце, і гэта іх знак, гэта іх частата.
У нашым лесе, калі б мы проста 3 літары, гэта лес з 3 дрэў.
І тое, як мы будзем працягваць, калі мы дадаў першы бацька,
Мы зрабілі лес з 2 дрэў.
Мы знялі 2 з гэтых дзяцей ва ўзросце ад нашага лесу, а затым замяніць яго бацькоўскі вузел
, Што было гэтыя 2 вузла, як дзеці.
І, нарэшце, наш апошні крок зрабіць наш прыклад з As, Bs, Cs і
было б зрабіць канчатковы бацькоў,
і так, то што б наша агульная колькасць дрэў у лесе 1.
Ці ўсё паглядзець, як вы пачынаеце з некалькіх дрэў у лесе
і ў канчатковым выніку з 1? Добра. Cool.
>> Што мы павінны зрабіць для Puff?
Што нам трэба зрабіць, гэта пераканацца, што, як заўсёды, яны даюць нам права тып уваходнага
так што мы сапраўды можам запусціць праграму.
У гэтым выпадку яны будуць даваць нам пасля іх першага аргументу каманднага радка
Яшчэ 2: файл, які мы хочам распакаваць і выхаду распакаваць файл.
Але як толькі мы пераканайцеся, што яны праходзяць міма нас у патрэбнай колькасці каштоўнасцяў,
Мы хочам пераканацца, што ўваход файл Хафф ці не.
І вось аднойчы мы гарантуем, што гэта файл Хафф, то мы хочам пабудаваць наша дрэва,
пабудаваць дрэва так, што яно адпавядае дрэва, чалавек, які адправіў паведамленне пабудаваны.
Затым, пасля мы будуем дрэва, то мы можам мець справу з 0 і 1, што яны прайшлі ў,
ісці за тымі, па нашым дрэве, таму што гэта ідэнтычна,
а потым пішуць, што паведамленне з, інтэрпрэтаваць біты назад у знакі.
І потым, у канцы, таму што мы маем справу з паказальнікамі тут,
Мы хочам пераканацца, што мы не маем любой уцечкі памяці
і што мы ўсё бясплатна.
>> Забеспячэнне належнага выкарыстання з'яўляецца старая капялюш для нас цяпер.
Возьмем у якасці ўваходу, якая будзе імя файла, пыхкаць,
а потым мы паказваем выхад,
таму імя файла для пульхныя выхад, які будзе тэкставы файл.
Гэта выкарыстанне. І зараз мы хочам пераканацца, што ўваход разбушаваўся, ці не.
Успамінаючы, было што-небудзь у размеркаванні код, які можа дапамагчы нам
з разуменнем, ці з'яўляецца файл разбушаваўся, ці не?
Існаваў інфармацыі ў huffile.c аб Huffeader.
Мы ведаем, што кожны файл мае Хафф Huffeader звязаныя з ім з магічным лікам
а таксама масіў частот для кожнага знака
а таксама кантрольную суму.
Мы ведаем, што, але мы таксама прынялі зірнуць на dump.c,
, У якім яна чытала ў файл Хафф.
І так, каб зрабіць гэта, ён павінен быў праверыць ці сапраўды яна была як раз'юшыўся, ці не.
Таму, магчыма, мы маглі б выкарыстоўваць dump.c як структура для нашага puff.c.
Вярнуцца да PSET 4, калі ў нас быў файл copy.c, што скапіявалі ў тройках RGB
і мы інтэрпрэтавалі, што для дэтэктыўны раман і змяненне памеру,
Сапраўды гэтак жа, тое, што вы можаце зрабіць, гэта проста запусціць каманду Ф dump.c puff.c
і выкарыстоўваць некаторыя з код.
Тым не менш, гэта не будзе так проста, працэсу
для перакладу вашага dump.c ў puff.c,
але па крайняй меры гэта дае вам дзе-небудзь, каб пачаць
аб тым, як пераканацца, што ўваход на самай справе як раз'юшыўся, ці не
, А таксама некалькі іншых рэчаў.
Мы забяспечылі належнага выкарыстання і запэўніў, што ўваход фыркнуў.
Кожны раз, калі мы гэта зрабілі, мы зрабілі належныя праверкі на памылкі,
так вяртанні і выхад з функцыі, калі некаторыя з ладу, калі ёсць праблема.
>> Цяпер тое, што мы хочам зрабіць, гэта пабудаваць рэальнае дрэва.
Калі мы паглядзім, у лесе, ёсць 2 асноўныя функцыі
што мы збіраемся хочаце стаць вельмі знаёмыя.
Там у булевай функцыі раслін, што расліны не-0 частата дрэва ў нашым лесе.
І такім чынам, вы перадаеце паказальнік на лес і паказальнік на дрэва.
Хуткі пытанне: колькі лесу будзе ў вас, калі вы будуеце дрэва Хафман?
Наш лес, як наш палатно, так?
Такім чынам, мы толькі збіраемся мець 1 лес, але мы збіраемся мець некалькі дрэў.
Таму, перш чым называць расліны, вы меркавана збіраўся хочаце, каб ваш лес.
Існуе каманда, што калі вы паглядзіце на forest.h аб тым, як вы можаце зрабіць лес.
Вы можаце пасадзіць дрэва. Мы ведаем, як гэта рабіць.
І тады вы можаце таксама выбраць дрэва з лесу,
выдаленне дрэў з нізкім вагой і дае вам паказальнік на гэта.
Успамінаючы, калі мы рабілі прыклады сябе,
Калі мы малявалі яго, мы проста толькі што дадалі спасылкі.
Але тут замест таго, каб проста дадаць спасылкі,
думаю аб ім як вы выдаляеце 2 з гэтых вузлоў, а затым замяніць яго на іншы.
Каб выказаць, што ў плане збору і пасадкі,
Вы выбіраеце 2 дрэва, а затым пасадка іншае дрэва
, Які мае тыя 2 дрэвы, якія вы выбралі, як дзеці.
Для пабудовы дрэва Хафман, вы можаце прачытаць у знаках і частоты ў парадку
таму што Huffeader дае, што для вас,
дае вам масіў частот.
Такім чынам, вы можаце пайсці далей і проста ігнараваць усё, што з 0 у гэтым
таму што мы не хочам 256 лісця ў канцы яго.
Мы толькі хочам, каб колькасць лісця, якія з'яўляюцца сімваламі
, Якія фактычна выкарыстоўваюцца ў файле.
Вы можаце прачытаць у тых знаках, і кожны з гэтых знакаў, якія маюць не-0 частот,
тыя збіраецеся быць дрэў.
Што вы можаце зрабіць, гэта кожны раз, калі вы праглядаеце ў не-0 частата знак,
Вы можаце пасадзіць гэта дрэва ў лесе.
Пасля таго як вы пасадзіце дрэвы ў лесе, вы можаце далучыцца да тых дрэвах, як браты і сёстры,
так вяртаючыся да пасадкі і выбраць, дзе вы выбіраеце 2, а затым завод 1,
дзе то 1, што вы завода з'яўляецца бацькам 2 дзяцей, што вы выбралі.
Такім чынам, то ваш вынік будзе адно дрэва ў лесе.
Вось як вы будуеце сваю дрэва.
>> Ёсць некалькі рэчаў, якія могуць пайсці не так, тут
таму што мы маем справу з стварэннем новых дрэў і справу з паказальнікамі і таму падобнае.
Раней, калі мы маем справу з паказальнікамі,
кожны раз, калі мы malloc'd мы хацелі пераканацца, што ён не вярнуў нам NULL значэнне паказальніка.
Такім чынам, на некалькі крокаў у рамках гэтага працэсу там будзе некалькі выпадкаў
дзе ваша праграма можа не спрацаваць.
Тое, што вы хочаце зрабіць, вы хочаце, каб пераканацца, што вы апрацоўваць гэтыя памылкі,
і ў спецыфікацыі ён гаворыць з імі справіцца вытанчана,
так як раздрукаваць паведамленне карыстачу казаць ім, чаму праграма павінна выйсці
і затым хутка выйсці з яго.
Для гэтага апрацоўка памылак, памятаеце, што вы хочаце, каб праверыць яго
кожны раз, што не можа быць адмовы.
Кожны раз, калі вы робіце новы паказальнік
Вы хочаце, каб пераканацца, што гэта поспех.
Перш, чым тое, што мы рабілі, робяць новы паказальнік і таНос гэта,
і тады мы б праверыць, што паказальнік NULL.
Так што збіраецеся быць у некаторых выпадках, калі вы проста можаце зрабіць гэта,
але часам вы на самой справе выкліку функцыі
і ў рамках гэтай функцыі, гэта той, які робіць mallocing.
У тым выпадку, калі мы азірнемся на некаторых функцый у кодзе,
Некаторыя з іх з'яўляюцца лагічнымі функцыямі.
У абстрактным выпадку, калі ў нас ёсць Булева функцыя называецца Foo,
У прынцыпе, мы можам выказаць здагадку, што ў дадатак да Foo рабіць тое, што робіць,
так як гэта Булева функцыя, яна вяртае сапраўднае або несапраўднае -
дакладна, калі паспяхова, калі не ілжывым.
Таму мы хочам, каб праверыць вяртаецца значэнне Foo з'яўляецца сапраўдным або ілжывым.
Калі гэта хлусня, гэта азначае, што мы збіраемся хочаце надрукаваць нейкую паведамленне
, А затым выйсці з праграмы.
Тое, што мы хочам зрабіць, гэта праверыць вяртаецца значэнне Foo.
Калі Foo вяртае хлусня, то мы ведаем, што мы сутыкнуліся з нейкай памылкай
і мы павінны выйсці з нашай праграмы.
Спосаб зрабіць гэта, гэта ёсць стан, пры якім фактычная функцыя само ваш стан.
Скажам Foo прымае ў х.
Мы можам мець у якасці ўмовы, калі (Foo (х)).
У прынцыпе, гэта азначае, што калі ў канцы выканання Foo ён вяртае ісціну,
Затым мы можам зрабіць гэта, таму што функцыя мае ацаніць Foo
для таго, каб ацаніць агульны стан.
Такім чынам, то гэта, як вы можаце зрабіць нешта, калі функцыя вяртае ісціну і паспяхова.
Але калі ты памылак, вы толькі хочаце кінуць паліць, калі ваша функцыя вяртае хлусня.
Што вы можаце зрабіць, гэта проста дадаць == ілжывых або проста дадаць выбуху перад ім
, А затым, калі ў вас ёсць (! Foo).
У рамках гэтага цела, што ўмова вам прыйдзецца ўсё апрацоўкі памылак,
так як, "Не атрымалася стварыць гэта дрэва", а затым вяртае 1 або нешта накшталт гэтага.
Тое, што гэта робіць, аднак, у тым, што нават калі Foo вярнуліся ілжывай -
Скажам Foo вяртае ісціну.
Тады вам не прыйдзецца выклікаць Foo зноў. Гэта распаўсюджаная памылка.
Таму што гэта было ў вашым стане, гэта ўжо ацэнка,
так у вас ужо ёсць вынік, калі вы выкарыстоўваеце зрабіць дрэва ці нешта накшталт таго
раслін або забраць ці чамусьці.
Ён ужо мае гэта значэнне. Гэта ўжо выканана.
Так што гэта карысна выкарыстоўваць Булевы функцыі як умова
таму што вы ці не на самай справе выканаць цела цыклу,
ён выконвае функцыю ў любым выпадку.
>> Наша другая да апошняга кроку піша паведамленні ў файл.
Як толькі мы пабудуем дрэва Хафман, то напісанне паведамленняў у файл даволі проста.
Гэта даволі проста зараз проста прытрымлівайцеся 0 і 1.
І так па традыцыі мы ведаем, што ў дрэве Хафман 0s паказваюць пакінуў
і 1s паказвае направа.
Такім чынам, калі вы чыталі ў біт за бітам, кожны раз, калі вы атрымаеце 0
Вы будзеце прытрымлівацца левай галіны, а затым кожны раз, калі вы праглядаеце ў 1
Вы збіраецеся прытрымлівацца правай галіны.
І тады вы будзеце працягваць, пакуль вы націснеце ліст
таму што лісце будзе ў канцы галіны.
Як мы можам сказаць, ці будзем мы патрапілі лісце ці не?
Мы казалі гэта раней.
[Студэнт] Калі паказальнікаў NULL. >> Так.
Мы можам сказаць, калі мы трапілі лісце, калі паказальнікі на левага і правага дрэвы NULL.
Perfect.
Мы ведаем, што мы хочам чытаць па макулінках ў нашым файле Хафф.
Як мы бачылі раней у dump.c, што яны зрабілі, яны чыталі ў біт за бітам ў файл Huff
і проста раздрукаваць тое, што гэтыя біты былі.
Мы не збіраемся рабіць гэтага. Мы будзем рабіць тое, што гэта трохі больш складаным.
Але што мы можам зрабіць, мы можам лічыць, што кавалак кода, які чытае ў біт.
Тут мы маем цэлае біт, які ўяўляе бягучы біт, які мы ідзем.
Гэта клапоціцца аб пераборы ўсіх бітаў у файл, пакуль вы не патрапілі ў канец файла.
Грунтуючыся на гэтым, то вы будзеце жадаць мець нейкі итератор
прайсці дрэва.
А потым у залежнасці ад таго біт роўны 0 або 1,
Вы збіраецеся хочаце альбо рухацца, што итератор на левым ці перамясціць яго ў правы
ўсю дарогу, пакуль вы націснеце ліста, так усю дарогу, пакуль гэты вузел, што вы на
не паказвае на любым больш вузлоў.
Чаму мы можам зрабіць гэта з дапамогай файла Хафман, але не азбукі Морзэ?
Таму што ў азбуцы Морзэ ёсць трохі двухсэнсоўнасці.
Мы маглі б быць падобным, ой, пачакайце, мы трапілі лісты па шляху, так што, магчыма, гэта наш ліст,
у той час як, калі б мы працягвалі толькі трохі даўжэй, то мы б трапілі яшчэ адзін ліст.
Але гэта не адбудзецца ў кадаванні Хафман,
так што мы можам быць упэўненыя, што адзіны спосаб, якім мы збіраемся ударыць характар
, Калі левая і правая дзяцей гэтага вузла з'яўляюцца NULL.
>> Нарэшце, мы хочам, каб вызваліць усе нашы памяці.
Мы хочам, каб як зачыніць файл Хафф, што мы маем справу з
а таксама выдаліць усе дрэвы ў нашым лесе.
Грунтуючыся на вашых рэалізацыі, вы, верагодна, захочаце патэлефанаваць выдаліць лесе
а на самай справе перажывае ўсе дрэвы самастойна.
Але калі вы зрабілі якія-небудзь часовыя дрэвы, вы хочаце, каб вызваліць гэта.
Вы ведаеце, ваш код лепш, так што вы ведаеце, дзе вы выдзяленні памяці.
І так, калі вы ідзяце ў, пачнем з кіравання F'ing нават для таНос,
бачыце, калі вы таНос і пераканаўшыся, што вы вызваляліся ўсё, што
але потым проста перажывае свой код,
разумення, дзе вы маглі б выдзеленай памяці.
Звычайна вы маглі б проста сказаць: "У канцы файла Я проста хачу, каб выдаліць лесе на мой лес»,
так у асноўным ясна, што памяць, бясплатна, што,
», А затым я таксама збіраюся, каб закрыць файл, а затым мая праграма будзе кінуць паліць».
Але ў тым, што адзіны раз, калі ваша праграма завяршае працу?
Не, таму што часам, магчыма, было памылкай, што адбылося.
Можа быць, мы не маглі адкрыць файл або мы не маглі зрабіць іншае дрэва
ці нейкая памылка адбылася ў працэсе размеркавання памяці і таму ён вяртаецца NULL.
Адбылася памылка, і затым мы вярнуліся і кінуць паліць.
Дык вось, вы хочаце, каб пераканацца, што любое магчымае час, што ваша праграма можа кінуць паліць,
Вы хочаце, каб вызваліць ўсе вашы памяці там.
Гэта не проста будзе ў самым канцы галоўнай функцыі, якую вы кінуць свой код.
Вы хочаце, каб азірнуцца назад, каб кожны асобнік, што ваш код патэнцыйна можа вярнуцца заўчасна
, А затым вызваліць памяць усё, што мае сэнс.
Скажам, вы заклікалі зрабіць лясоў і вярнуўся ілжывым.
Тады вы, напэўна, не трэба будзе выдаліць лесе
таму што вы не маеце лесе яшчэ няма.
Але ў кожнай кропцы ў кодзе, дзе вы маглі б вярнуцца заўчасна
Вы хочаце, каб пераканацца, што вы вызваліць любыя магчымыя памяці.
>> Таму, калі мы маем справу з вызвалення памяці і які мае патэнцыйныя уцечкі,
Мы хочам, каб не толькі выкарыстаць нашы меркаванні і нашы логікі
але таксама выкарыстоўваць Valgrind вызначыць, ці з'яўляецца мы вызвалілі ўсіх нашых памяццю на належным узроўні ці не.
Вы можаце запусціць Valgrind на Puff, а затым вы павінны таксама прайсці яго
правільнае колькасць аргументаў каманднага радка для Valgrind.
Вы можаце запусціць, але на выхадзе атрымліваецца крыху загадкавы.
Мы атрымалі трохі прывыкнуць да яго з Speller, але ў нас усё яшчэ трэба крыху больш дапамогі,
так, то запусціць яго яшчэ з некалькімі сцягамі, як ўцечка праверыць = поўны,
, Што, верагодна, дасць нам больш карысным выхадам на Valgrind.
>> Потым яшчэ карысны савет пры адладцы гэта каманда параўнання.
Вы можаце атрымаць доступ да ажыццяўлення супрацоўнікаў аб Хафф, запусціць, што ў тэкставым файле,
, А затым выводзіць іх у бінарны файл, двайковы файл Хафф, каб быць вызначаным.
Тады, калі вы выкарыстоўваеце свой уласны пластовага на што двайковы файл,
Затым ідэале, які выводзіцца тэкставага файла будзе ідэнтычным
зыходнаму, што вы прайшлі цалі
Тут я выкарыстоўваю hth.txt ў якасці прыкладу, і гэта адна казалі ў вашай спецыфікацыі.
Вось літаральна толькі што HTH, а затым радка.
Але, безумоўна, адчуваць сябе свабодна і вы, безумоўна, рэкамендуецца выкарыстоўваць больш прыкладаў
для вашага тэкставага файла.
>> Вы нават можаце ўзяць стрэл у магчыма сціск і дэкампрэсію, то
некаторыя з файлаў, якія вы выкарыстоўвалі ў Speller, як вайна і мір
або Джэйн Осцін ці нешта накшталт гэтага - гэта было б крута - ці Осціна Пауэрса,
выгляд працы з вялікімі файламі, таму што мы б не дайшлі да гэтага
калі б мы выкарыстоўвалі наступны інструмент тут, LS-л.
Мы прывыклі да Ls, якія ў асноўным пералічаныя ўсе змесціва ў нашым бягучым каталогу.
Пераходзячы ў сцяг-L на самай справе адлюстроўвае памер гэтых файлаў.
Калі вы ідзяце праз спецыфікацыю PSET, на самай справе правядзе вас праз стварэнне бінарных файлаў,
з пыхкаючы, і вы ўбачыце, што для вельмі маленькіх файлаў
прасторы кошту сціскаючы яго і перакладаў ўсё, што інфармацыя
ўсіх частот і таму падобныя рэчы перавышае фактычную выгаду
сціснуць файл у першую чаргу.
Але калі вы запусціце яго на некалькі доўгіх тэкставых файлаў, то вы можаце бачыць, што вы пачнеце атрымліваць некаторую выгаду
У сціск гэтых файлаў.
>> І, нарэшце, у нас ёсць наш стары прыяцель GDB, які, безумоўна, будзе спатрэбяцца таксама.
>> Ці ёсць у нас якія-небудзь пытанні па дрэвах Хафф або працэс, магчыма, прыняцця дрэў
або любыя іншыя пытанні па Puff Huff'n?
Добра. Я застануся вакол некаторы час.
>> Дзякуй усім. Гэта было Пакрокавае кіраўніцтва 6. І ўдачы.
>> [CS50.TV]