[Powered by Google Translate] [Bisita gidatua - Arazoa Set 6] [Zamyla Chan - Harvard Unibertsitatea] [Hau CS50 da. - CS50.TV] 

Kaixo, guztioi, eta gidatua 6 ongi etorria: Huff'n Puff. Huff'n Puff zer egiten ari garen Huffman Konprimitutako fitxategia aurre eta, ondoren, puffing back up, beraz, deskonprimitzerakoan beraz, 0 s eta 1s erabiltzaileak bidaltzen dizkigun itzuli ahal izango dugu. eta berriz jatorrizko testua sartu bihurtzeko. Pset 6 pretty cool izango zaren tresna batzuk ikus delako 4 eta pset pset 5 eta mota erabili konbinatuz 1 kontzeptua pretty neat pentsatu zatoz. 

Era berean, dudarik gabe, 4 eta 5 pset gehien Challenging psets izan dugun eskaintzen ziren. Beraz, hemendik aurrera, C pset 1 gehiago dugu, eta, ondoren, horren ondoren web programazio Oraindik dugu. Beraz, zorionak zuei CS50 konkorraren gogorrenak baino gehiago lortzeko. 

Moving Huff'n Puff, gure pset honetan laukitik Huffman zuhaitz izango dira, beraz, ez bakarrik nola zuhaitz bitar lana, baina, halaber, zehazki Huffman zuhaitz ulertzeko, nola eraikitzen ari dira. Eta gero, banaketa kodea pset honetan asko izan dugu, etorri eta benetan ikusteko kodea dugu ahal izango agian ez dugu oraindik guztiz ulertzen. eta, beraz, c fitxategiak izango da, baina, ondoren, bere erantsitako h fitxategiak nahikoa emango digu ulertzeko behar ditugu, beraz, funtzio horiek nola lan egiten badakigu edo, gutxienez, zer egin behar dira beraien sarrera eta irteera nahiz eta ez dakigu zer kutxa beltza gertatzen ari edo ez dute ulertzen zer kutxa beltza barruan gertatzen ari dena. Eta gero, azkenik, ohikoa den bezala, datu-egitura berriak ari gara aurre, nodo horren mota espezifikoak zenbait gauza, eta, beraz, hemen luma bat eta paper ez da soilik diseinu-prozesua eta nola zure pset behar lan irudikatu saiatzen ari zaren baina arazketa zehar ere. GDB izan dezakezu zure luma eta paper batera hartzen behera balioak dira, zure geziak non apuntatzen dira, eta horrelako gauzak. 

Lehenik eta behin dezagun Huffman zuhaitz begiratu. Huffman zuhaitz bitar zuhaitzak dira, zentzua nodo bakoitzak 2 seme-alaba ditu. Huffman zuhaitz ezaugarri ohikoena balioak bit gutxien irudikatzen dira. Morse kodea hitzaldia adibide, finkatutako mota letrak batzuk ikusi ditugu. Ari zaren, adibidez, A edo E bat itzultzeko saiatzen bada, sarritan itzultzen ari zara, eta, beraz, ordez bit multzo osoa erabili beharrik ohiko datu mota esleitu, konprimitu behera gutxiago, eta, ondoren, letrak direnek irudikatzen gutxiago sarritan bit longer irudikatzen dira duzula ordaindu daitekeelako pisatzen duzu letrak agertzen diren maiztasunak. Ideia bera daukagu ​​hemen Huffman zuhaitzak non, bide mota zenbait karaktere kate bat egiten ari gara. Eta gero maiztasuna gehien duten pertsonaiak bit gutxien irudikatzen joan. 

Huffman zuhaitz bat eraikitzeko duzula testuan agertzen diren karaktereak guztiak jartzea da eta haien maiztasuna kalkulatzeko, nola askotan agertzen dira. Hori bai letrak horiek zenbat aldiz agertzen Aldaketa edo, agian, bat ehuneko zenbat bakoitzak agertzen karaktere guztiak. Eta beraz, zer egin nahi duzu behin hori mapatzen out of duzu ondoren, 2 maiztasun txikiena eta gero sartu anai-arreba gisa non gero guraso nodo frekuentzia bat horrek bere 2 haur batura da. Eta gero, hitzarmen by diotenez, ezker nodo 0 adarra jarraituz jarraitzen duzu, eta, ondoren, eskuinekoa nodoaren 1 adarrean. Morse kodea ikusi bezala, bat Gotcha izan zen soinua eta beep bada anbiguoa izan da. Bai, gutun-1 edo 2 letren segida bat izan da. Eta beraz, zer Huffman zuhaitzak ez da pertsonaien izaera duelako edo gure benetako pertsonaiak adarrean nodo azken final - erreferentzia hosto gisa dugu horren arabera ezin da anbiguotasuna edozein izan terminoak zein letra kodetzeko bit serie saiatzen ari zaren 1 letra ordezkatzen duten bit zehar inon ez delako egingo beste gutun osoa aurkituko duzu, eta ez da nahasmena edozein dago. Baina adibide dugu you guys benetan ikusi ordez, besterik gabe gurekin kontatzea, hori egia da. 

Dezagun begiratu Huffman zuhaitz baten adibide erraz bat. Kate bat da, 12 karakterekoa izan behar dut. 4 daukat, Bs As 6 eta 2 Cs. Nire lehen urratsa, zenbatu izango litzateke. Zenbat aldiz agertzen ez A? 4 aldiz agertzen da katea. B agertzen da 6 aldiz, eta C 2 aldiz agertzen da. Jakina, B erabiltzen dut gehienetan esan nahi dut, beraz bit kopurua, gutxien 0 s eta 1s kopurua gutxien B irudikatu nahi dut. Eta gero, C 0 s eta 1s zenbatekoa gehien behar baita espero dut. Lehenik eta behin hemen zer egin nuen jarri dut Orden Gorakorra maiztasun dagokionez. C eta A, horiek dira gure 2 maiztasun txikiena ikusten dugu. Guraso nodo bat sortzen dugu, eta guraso nodo horrek ez du lotutako eskutitz bat izan, maiztasuna, batura da baina ez da. Batura 2 + 4 bihurtzen da, hau da, 6. Ondoren, ezkerreko adarraren jarraituko dugu. 6 nodo hartan ginen bada, eta 0 jarraituko genuke C lortu eta, ondoren, 1 A. Beraz, gaur egun, 2 nodo dugu. 6 balioa izan dugu, eta, ondoren, izan ere, 6 balioa nodo beste. Eta, beraz, 2 ez bakarrik 2 txikienak baina, aldi berean, besterik gabe, 2 geratzen dira, beraz, guraso beste ere sartu dugu, batura 12 da. Hortaz, hona hemen gure Huffman zuhaitz dugu non B, pixka 1 eta, ondoren, A 01 izango litzateke dugu, eta, ondoren, C 00 izatea. Beraz, hemen, funtsean, karakteretan ordezkari horiek ari gara 1 edo 2 bit ikusiko dugu non B, aurreikusten du, gutxienez. Eta gero, espero genuen C gehien izan, baina txiki bat da Huffman, hala nola, zuhaitz geroztik, ondoren, A ere nonbait aurka erdian 2 biteko irudikatzen da. 

Just Huffman zuhaitz simple beste adibide bat baino gehiago joan dira, esan katea behar duzu "Kaixo". Zer egin nahi duzu lehen esan zenbat aldiz ez H honetan agertzen nahi duzun? H agertzen da behin eta, ondoren, e agertzen da behin eta, ondoren, l birritan agertzen dugu eta o behin agertzen. Eta, beraz, ondoren, gutun bit kopurua gutxienez irudikatzen espero dugu? [Ikasleen] l. >> L. Bai. l eskubidea da. L bit kopurua gutxienez irudikatzen espero dugu l erabiltzen da gehien katea "Hello. delako" Orain zer egin behar dut, marrazteko nodo horiek. 1 daukat, hau da, H, eta, ondoren, beste 1, hau da, e, eta, ondoren, 1, hau da, o oraintxe ari naiz ordena jarriz, eta ondoren, 2, hau da, l. Ondoren, I Huffman zuhaitz bat eraikitzeko, gutxienez maiztasun nodo 2 diot anai-arrebak, eta guraso nodo bat sortuz. Hemen, 3 maiztasun txikiena nodo dugu. 1 Oraindik dute. Hortaz, hona hemen zein lehena lotzeko goaz aukeratu dugu. Demagun H eta e aukeratu dut. Batura 1 + 1, 2, baina nodo horrek ez du lotutako eskutitz bat izan. Dauka besterik ez du balio. Orain 2 hurrengoa maiztasun txikiena at ikusi dugu. 2 eta 1. Hori bai horiek 2 izan daiteke, baina hau aukeratu dut. Batura 3 da. Eta gero, azkenik, besterik ez dut 2 Ezkerraldean, eta, beraz, orduan bihurtzen da 5. Gero, hemen, espero bezala, horretarako kodeketa bete bada, 1s dira beti eskuineko adarraren eta 0 s ezkerreko dira. Ondoren, 2 l 1 bit eta gero o irudikatzen dugu eta, ondoren, e 2, eta, ondoren, H 3 bit jaitsierak behera. Beraz, mezu hau transmititu dezakezu, "Hello" ordez benetan pertsonaiak erabiliz 0 s eta 1s, besterik gabe. Hala eta guztiz ere, ez ahaztu askotan gure maiztasuna lotura izan genuen. Izan bai genezake elkartu H o lehen agian. Edo gero 2 irudikatzen l izan dugu , baita 2 irudikatzen fitxatu du, lotuta izan dugu, bai bat. 

Eta beraz, bidal 0 s eta 1s, benetan ez da bermatzen hartzaileak guztiz bat eskuinera off zure mezua irakurri agian ez direlako ezagutzen den erabaki egin. Beraz, Huffman konpresio aurre ari gara, nolabait, nola erabaki dugu, gure mezua hartzailearen esan behar dugu Informazio gehigarria mota batzuk ezagutu behar dute Konprimitutako mezua gain. Zuhaitz benetan itxura ulertu behar dute, nola egin dugu erabaki horiek. 

Hemen besterik ez genuen egiten benetako Aldaketa oinarritutako adibide, baina batzuetan ere izan dezakezu Huffman zuhaitz bat maiztasuna oinarritzen gutunak agertzen dira, eta prozesu bera zehatza da. Hemen nago adierazteko, ehunekoak edo zati bat dagokionez, eta, beraz, hemen zehatza gauza bera. 2 txikiena, Laburbilduz, hurrengo 2 txikiena, laburbildu aurkitu dut, dut zuhaitz bat osoa izan arte. Nahiz eta egin genezake bai, ehunekoak aurre ari gara, horrek esan nahi du gauzak ari gara zatituz eta hamarren aurre, edo, hobeto esanda, flotatzen ari gara buru baten egitura buruzko datuak pentsatzen bada. Zer jakin karroza gara? Zer arazo komun bat karroza ari gara aurre? [Ikasleak] Imprecise aritmetika. >> Bai. Imprecision. Delako koma mugikorreko imprecision, pset hau da, beraz, ziurtatu dugu balio edozein ez dugu galtzen, eta, ondoren, benetan ari gara Aldaketa duen aurre. Beraz, bada Huffman nodo bat pentsatu, begiratu itzuliz gero egitura hemen zinen, berdea dira begiratzen baduzu lotutako maiztasuna du baita puntu haren ezkerreko nodo, baita bere eskubidea nodo bat. Eta gero, gorria dira bertan ere haiekin lotutako pertsonaia bat. Ez da aparteko batzu egiten ari gara guraso eta gero, azken nodoak, erreferentzia hosto gisa, baizik ere NULL balio izan. Nodo bakoitzean, pertsonaia bat, nodo hori adierazten duen ikurra izan dugu, maiztasuna, baita haren ezkerreko seme-alaba, baita haren eskuinaldean seme erakuslea. Hostoak, oso behean daude, izan ere nodo erakusleak ezkerreko eta beren eskubidea, baina balio horiek ez dira benetako nodo seinalatuz geroztik, zer egingo zenuke beren balio izan? >> [Ikasleak] NULL. >> NULL. Hain zuzen ere. Hona hemen nola irudikatu maiztasuna dezakezu karroza en adibide bat, baina harekin zenbaki osoen aurre goaz, beraz, egin nuen han, datu mota aldatu. 

Dezagun adibide konplexu apur bat gehiago joan. Baina orain egin ditudan sinpleak dira, besterik ez da prozesua bera. 2 maiztasun txikiena aurkituko duzu, laburbildu maiztasunak eta hori zure guraso nodoaren maiztasun berria da, gero bere ezkerretara puntu 0 adar eta eskuineko 1 adarrean. Dugu katea "Hau da cs50," bada, orduan, zenbat aldiz T aipatu zenbatu ditugu, h aipatu, i, s, c, 5, 0. Ondoren, hemen zer egin nuen landatu dut nodo gorria da, Karaktere horiek, azkenean, nire zuhaitzaren beheko noa esan dut. Dutenek hostoak guztiak izango dira. Orduan, zer egin nuen horrela antolatu I maiztasunaren arabera ordena gorakorrean, eta hori da, benetan kodea pset du da maiztasunaren arabera ordenatzen da eta, ondoren, alfabetikoki. Beraz, zenbakiak du lehenik eta, ondoren, alfabetikoki maiztasuna. Orduan, zer egin nahi dut 2 txikiena aurkituko nuke. 0 eta 5. Laburbildu nuke, eta hori 2. Gero jarraituko nuke, hurrengo 2 txikiena aurkitu. Dutenek bi 1s dira, eta, ondoren, horiek bihurtu 2 baita. Orain nire hurrengo urratsa hori sartu kopurua txikiena ezagutzen dut, T da, 1, eta, ondoren, duela 2 maiztasuna nodo bat aukeratzerakoan. Hortaz, hona hemen 3 aukera ditugu. Zer diapositiba egin dut besterik ez da ikusmen berrantolatzeko dituzu beraz, nola eraikitzen ari naiz ... ikusi ahal izango duzu. Zer kodea eta zure kodea banaketa egingo da sartu T bat izango litzateke 0 eta 5 nodo. Orduan, 3 batuketa, eta, ondoren, prozesua jarraituko dugu. 2 eta 2 baxuenak dira, eta, beraz, ondoren, 4 batura horiek. Pertsona orok du, beraz, orain arte jarraituz? Ongi da. Gero, ondoren, 3 eta 3 gehitu behar zaizkio sortu behar duten dugu, , beraz, berriro besterik ez dut, beraz, kommutazio ikusi ikusmen dezakezu ez dela gehiegi messy. Ondoren, 6 dugu, eta gero, gure azken urratsa da gaur egun bakarrik dugun 2 nodo horiek laburbildu dugu gure zuhaitza, hau da, 10 root egiteko. Eta 10 zenbakia zentzua irudikatzen nodo bakoitzean delako, beren balioa, haien maiztasuna zenbakia, zenbat aldiz agertu katea, eta, ondoren, 5 karaktere izan gure katea, eta, beraz, zentzua, beraz. Begiratzen dugu, bada, nola benetan genuke kodetuko da, Espero zen bezala, i eta s, gehienetan agertzen bit kopurua gutxien irudikatzen dira. 

Kontuz ibili hemen. Huffman zuhaitz Kasu benetan axola. Maiuskulaz S bat minuskulaz s baino desberdina da. Izan badugu "Hau CS50 da" maiuskulaz eta, ondoren, minuskulaz s soilik bi aldiz agertuko da, bere balioa 2 nodo bat izango litzateke, eta, ondoren, maiuskulaz S behin bakarrik izango litzateke. Orduan, zure zuhaitz egitura aldatuko luketen benetan duzu delako extra hosto bat hemen. Baina batura izango litzateke, oraindik 10 izango da. Hori da benetan ari gara checksum dira deituz, zenbatzen, guztien gain. 

Orain estalita ditudan Huffman zuhaitzak, Huff'n Puff, pset murgiltze sartu ahal izango dugu. Galdera atal bat hasi gara, eta hori ohituta zuhaitz bitarra eta nola inguruan jarduteko: marrazketa nodo, zure typedef struct nodo bat sortzea, eta nola sartu zuhaitz bitar bat, hori horrela antolatu dezakezu ikusita, da, eta horrelako gauzak traversing. Ezagutza da behin betiko laguntzeko dive Huff'n Puff zati duzun joan pset da. Pset, estandar edizioan, zeregin Puff ezartzeko, eta hacker bertsioa zure zeregina da Huff ezartzeko. Zer Huff ez da testua hartzen du, eta, ondoren, itzultzen 0 s eta 1s, prozesua egin dugun non maiztasunak zenbatuko dugu, beraz eta, ondoren, zuhaitza egin eta gero, esan zuen: "Nola T lortzeko I?" T 100 irudikatzen da, horrelako gauzak, eta, ondoren, Huff testua, eta, ondoren, irteera bitarra dela hartuko luke. Baina badakigu, halaber, nahi dugu, gure mezuaren hartzaileak ahal izateko delako Zuhaitz berean zehatza birsortzeko, maiztasuna zenbatzen buruzko informazioa ere. Ondoren Puff gaude 0 s eta 1s fitxategi bitarra eta maiztasunak buruzko informazioa eman ere. 0 s eta 1s horiek atzera itzultzea izan zen, jatorrizko mezua sartu, horrela ari gara deskonprimitzerakoan. Ari zaren estandarrak edizioa egiten ari bada, ez duzu behar Huff ezartzeko, beraz, ondoren, bakarrik erabili ahal izango duzu Huff langileek ezartzeko. Zehaztutako nola egiten den buruzko argibideak daude. Huff langileek ezartzea zenbait testu fitxategi gainean exekuta dezakezu eta, ondoren, irteera hori erabili zure sarrera gisa Puff. 

Aipatu dudan bezala lehenago, banaketa kode asko dugu hau. Bidez hasten naiz. Denbora pasatzera noa. H fitxategiak c fitxategiak delako, izan ere, h dugu eta hori eskaintzen digu funtzioen prototipoak, ez dugu guztiz zehatz-mehatz ulertu behar Ez baduzu ulertzen zer ari den gertatzen. C fitxategiak, eta gero ez kezkatu gehiegi, baina behin betiko saiatu begirada bat hartu eta zenbait aholku eman leza eta erabilgarria beste pertsona kodea irakurtzeko erabiliko da. 

Iruzkinak, huffile.h begira, abstrakzio geruza Huffman-kodetuak fitxategiak adierazten du. Joaten gara behera bada, gehienez 256 sinbolo bat da kodeak behar izatea ez dagoela ikusiko dugu. Alfabetoaren letra guztiak maiuskulaz eta minuskulaz eta, ondoren, sinboloak eta zenbakiak, etab. Ondoren, hemen Huffman-kodetuak fitxategi bat identifikatzeko magia zenbaki bat behar dugu. Huffman kode bat barruan, magia-zenbaki jakin bat izan dute goiburua lotutako. Magiko bat ausazko zenbaki hori itxura, baina itzuli bada, ASCII sartu eta, ondoren, askatzea da benetan izarrekin Huff. Hemen Huffman-kodeketako fitxategi bat eta egitura bat behar dugu. Huff fitxategia lotutako ezaugarri hauek guztiak. Ondoren, behera hemen Huff fitxategi bat goiburua dugu, beraz, Huffeader deitzen dugun ordez extra h gehituz soinuak bera delako hala ere. Cute. Lotutako magia zenbaki bat behar dugu. Da oraingo Huff fitxategia bada, zenbaki izan arte, batez ere, magiko bat egingo da. Eta, ondoren, array bat izango da. Beraz, ikur bakoitzaren, eta horietatik 256, sinbolo horien maiztasuna Huff fitxategia barruan dira zerrendara. Eta gero, azkenik, maiztasun checksum bat dugu, maiztasunak horien batura izan behar du. Beraz, zer Huffeader bat da. Ondoren, hurrengo bit Huff fitxategia funtzio batzuetara itzultzeko dugu , baita pixka bat idazten Huff fitxategia, eta, ondoren, funtzio hau hemen, hfclose, benetan Huff fitxategia ixten. Aurretik, zuzenean besterik ez fclose ginen aurre, baina Huff fitxategi bat behar duzu, ordez fclosing benetan ari zaren egingo da hfclose eta hfopen. Huff fitxategiak dutenek jakin funtzioak ari dira eta aurre egingo dira. Ondoren, hemen goiburua irakurri dugu eta, ondoren, idatzi goiburua. 

Just h fitxategia irakurtzean Huff fitxategi bat izan liteke zentzu mota egin ahal izango dugu, zer ezaugarri ditu, benetan huffile.c sartzen joan gabe, Izan ere, badugu artelan, eta pixka bat konplexuagoa izango da. I / O hemen erakusleak aurre fitxategi guztiak ditu. Hemen denean hfread deitzen dugu, esate baterako, oraindik ari da fread aurre ikusiko dugu. Ez dugu funtzio horiek deusezten oso-osorik, baina ari gara bidaltzeko hartu beharreko arreta fitxategia ez da geure buruari egiten Huff barruan. Honen bidez eskaneatzeko free sentitzen duzu Oraindik bitxia bada eta joan eta geruza apur bat zuritu. 

Hurrengo fitxategia begiratzen ari gara tree.h. Aurretik Bisita gidatua slides Huffman nodoa espero dugu esan genuen typedef struct nodo bat egin dugu. Sinbolo bat, maiztasuna, eta ondoren, 2 nodo ko izatea espero dugu. Kasu honetan, zer egiten ari gara, hau da, funtsean, gauza bera nodoaren ordez izan ezik, horiek zuhaitz deitu dugu. Funtzio bat daukagu ​​egiteko zuhaitz deitu zuhaitz erakuslea itzultzen du. Speller atzera, nodo berria zinen esan nodo * hitz berri = malloc (sizeof) eta horrelako gauzak. Funtsean, mktree behar duten aurre. Era berean, zuhaitz bat kendu nahi duzula? beraz, hori funtsean egiten duzunean zuhaitz uzten, horretan esplizituki free deituz ordez, benetan ari zaren funtzioa erabiltzeko rmtree joan erakuslea non pasatzen duzu zuhaitz hori, eta, ondoren, modulua zuretzat hori zaintzeko hartuko dute parte. 

Tree.c. ditugu Funtzio berberak espero dugu ezartzeko ere ikusi izan ezik. Espero dugu, mktree deitu zuhaitz baten tamaina mallocs erakuslea, initializes balioak NULL balioa, eta, beraz, 0 s edo nuluak eta, ondoren, erakuslea itzultzen du zuhaitz hori duzula besterik ez duzu malloc'd. Kendu zuhaitz deitu egiten du lehen ziur ez zarela bikoitza libre uzten. Ziur benetan duzula nahi duzun kentzeko zuhaitz bat egiten du. Hemen, zuhaitz bat ere biltzen ditu bere seme-alabak, zer ez da deiak errekurtsiboki kendu zuhaitza zuhaitzaren ezker nodo baita eskuineko nodoa. Askatzen aurretik guraso, seme-alabak, baita libre behar du. Guraso ere root truka. Lehen gurasoa, eta, beraz, handi-handi-handi-handi-aitona atsegin dute edo amonaren zuhaitza, lehen mailak behera askatzea lehen egin behar dugu. Beraz, beheraino zeharkatuko du, doan dira, eta, ondoren, itzuli, free dira, eta abar. Beraz, zuhaitz. 

Orain begiratu baso dugu. Forest da non zure Huffman zuhaitz guztiak jartzen. Ari gara zerbait esaten izeneko lursail batean zuhaitz baten erakuslea, baita izeneko lursailean hurrengo erakuslea dauka. Zer itxura bezalako egitura mota hau? Dio mota baino gehiago dago. Eskuin hemen. Lotuta zerrenda. Partzela bat dugu lursailen zerrenda bat lotuta bezala ikusten dugu. Baso lursailen zerrenda bat lotuta gisa definitzen da, eta, beraz, baso-egitura besterik ez da ari gara erakuslea izan da gure lehen lursailean eta lursail hori barruan zuhaitz bat edo zuhaitz bat baizik eta puntu eta, ondoren, hurrengo argumentua adierazi du, eta, beraz, eta abar. Basoan bat egiteko mkforest deitzen diogu. Gero, nahiko erabilgarria zenbait funtzio dugu hemen. Jaso ditugu non pasatzen baso batean, eta gero itzulitako balioan Zuhaitza * zuhaitz baten erakuslea. Zer pick egingo da basoan sartuko da ari zarela seinalatuz ondoren, zuhaitz bat kendu maiztasun txikiena duen baso eta, ondoren, emango dizu erakuslea zuhaitz hori. Behin jaso deitzen duzunean, zuhaitza basoan ez da existitzen jada, Itzultzen den balioa zuhaitz hori erakuslea da. Ondoren, landare behar duzu. Provided erakuslea pasatzen duten zuhaitz-0 maiztasuna ez du, zer planta egingo da basoan hartu du, hartu zuhaitz eta landare zuhaitza basoaren barruan. Hemen rmforest dugu. Similar zuhaitza, funtsean askatu Gurekin gure zuhaitz guztiak kendu, kendu baso free baso horretan jasotako guztia. 

Forest.c erreparatzen badiogu, gutxienez 1 rmtree komando espero bertan ikusi dugu, basoko memoria free zuhaitz baso bat bada delako, ondoren, azkenean zuhaitz horiek kentzeko ere izan duzu. Erreparatzen badiogu forest.c sartu, gure mkforest dugu, hau da, espero dugun bezala. Gauza malloc dugu. NULL gisa baso lursailean lehen abiarazi dugu hasiko da hutsik dagoelako, ondoren, pick, zuhaitz pisu txikiena itzultzen du, maiztasun txikiena ikusiko dugu, eta, ondoren, lortzen jakin nodo kentzeko zuhaitz hori puntu eta hurrengoa, horrela hartzen du baso-zerrenda lotuta. Eta gero, hara, landare, txertatzen zuhaitz bati lotuta zerrenda egin behar dugu. Zer basoa ez da mantentzen nicely ordenatuko gurekin. Eta gero, azkenik, rmforest dugu, eta, espero bezala, rmtree izeneko bertan dugu. 

Banaketa kodea hain urrun begira, huffile.c ziurrenik urruti gogorrena ulertzeko, beste fitxategi batzuk, berriz, nahiko erraz jarraitu izan dute. Erakusleak eta lotutako zerrendak eta, besteak beste, gure ezagutza, gai nahiko ongi jarraitu behar izan dugu. Baina benetan ziurtatu erabat dugun ulertu behar dugu. H fitxategiak behar duzu deituz funtzio horiek, itzulera balio duten aurre delako, beraz, ziurtatu erabat duzula ulertzen zer egin behar den. bakoitzean funtzio horietako bat deitzen duzu. Baina, egia esan, barruan ulertzea ez da nahiko beharrezkoa izan dugulako duten. H fitxategiak. 2 gehiago gure banaketa kodea fitxategi utzi ditugu. 

Dezagun dump begiratu. Bere comment Irauli hemen Huffman-konprimitutako fitxategi bat hartzen du eta, ondoren, itzuli eta zabortegiak bere eduki guztiak. Hemen dela hfopen deituz ikusiko dugu. * Sarrerako fitxategia = fopen ispilu mota da, eta, ondoren, informazioa pasatzen duzu. Ia berdina da file * Huffile batean ari zaren pasatzen ordez izan ezik; ordez fopen hfopen pasatzen ari zaren. Hemen goiburua irakurri dugu lehen, hau da, mota nola goiburua irakurri dugu antzeko bitmap file. Zer ari gara hemen egiten da goiburua informazioa ala ez egiaztatzeko magia eskuineko zenbaki hori adierazten duela oraingo Huff fitxategia dauka, gero, txekeak horiek guztiak, ziurtatu fitxategia irekita dugu benetako huffed fitxategia edo ez da. Zer da hau ez da ikusi ahal izango dugu, sinbolo guztiak maiztasun irteerak grafiko bat taula batean terminal baten barruan. Zati hori erabilgarria izango da. Pixka bat ditu eta bit irakurtzen bit bit aldagaiak sartu eta, ondoren, inprimatzen ditu out. Beraz, bada, hth.bin,, fitxategi batean huffing emaitza da dump deitu ziren I langileen irtenbidea erabiliz, hau nuke. Pertsonaia hauen outputting da, eta ondoren agertzen dira frekuentzia jarriz. Begiratzen badugu, izan dira gehien 0 s hau izan ezik: H, agertzen da bi aldiz, eta, ondoren, T, agertzen da behin. Eta gero, hemen benetako mezua 0 s eta 1s ditugu. Hth.txt begiratzen badiogu, hau da, zentzuzkoa zen huffed jatorrizko mezua, Hs eta TS batzuk ikusteko espero dugu. Hain zuzen ere, 1 T eta 2 Hs ikusteko espero dugu. Hona hemen hth.txt dugu. HTH du, hain zuzen ere. Dago sartuta, ikusi ezin dugun arren, lerro pertsonaia bat da. Huff fitxategia hth.bin ere newline pertsonaia kodetzean baita. Hemen ezagutzen dugulako ordena HTH da eta, ondoren, newline, ikus ziurrenik H irudikatzen den, ezin dugu bakar bat baino ez 1 eta, ondoren, T da seguruenik 01 eta, ondoren, hurrengo H 1 baita eta, ondoren, bi 0 s adierazitako newline dugu. Cool. 

Eta gero, azkenik, ari gara. Anitz c delako eta aurre egiteko. H fitxategiak, Konpilatzailearen argumentu konplexua eder bat izan dugu, eta, beraz, hemen Makefile duzun dump egiten dugu. Baina, benetan, zure puff.c fitxategia joan behar duzu. Makefile benetan ez puff.c egiten duzu aurre egiteko. Horretan ari gara Makefile editatzeko. Egin guztiei bezala komando bat idazten duzunean, adibidez, den-denak egingo duzu. Feel free Makefile adibide begiratu iraganeko pset , baita hau nola Puff file egiteko gai izan liteke Makefile hau editatzen. Hori da horri buruz gure banaketa-kodea. 

Dugu horren bidez ondoren, ahaztuak, eta gero hemen berreskuratu beste besterik ez da nola Huffman nodo aurre goaz. Ez ari gara deituz horiek nodo gehiago joan dira deituz horiek zuhaitz goaz non ordezkari bere sinbolo char bat dugu, haien maiztasuna, agerraldi kopurua, zenbaki oso bat. Mugikor bat baino gehiago zehatza delako erabiltzen ari gara. Eta gero, ezkerreko haur eta baita eskuineko umearen erakuslea beste izen bat izan dugu. Baso bat, ikusi dugun bezala, zuhaitz-zerrenda lotutako bat besterik ez da. Azken finean, gure Huff fitxategia eraikitzen ari gara, 1 zuhaitza gure basoan eduki nahi dugu 1 zuhaitza, haur hainbat erro 1. Lehenago besterik ez ginen gure Huffman zuhaitz egiten, nodo guztiak gure pantailan gainean jarriz hasi ginen eta nodo horiek izan behar dugu esaten, azkenean hostoak ari dira joan, eta bere sinboloa da, bere maiztasuna da. Gure baso batean 3 hizki besterik ez dugu bada, 3 zuhaitz baso bat da. Eta gero goazela, aurreneko gurasoaren gehitu dugu, 2 zuhaitz baso bat egin dugu. 2 haur horiek kendu dugu gure baso eta gero nodo gurasoaren ordez 2 seme-alaba gisa nodo horiek izan. Eta gero, azkenik, gure azken urratsa, gure adibidean egiten den bezala, Bs, eta Cs azken gurasoaren izango litzateke, eta, beraz, ondoren, gure basoan zuhaitz Aldaketa guztira ekarriko luke 1. Denek ikusi nola hasten zara zure baso zuhaitz baino gehiago eta, azkenean, 1? Ongi da. Cool. 

Zer Puff egin behar dugu? Zer egin behar dugu, beti bezala, sarrera mota ematen dute eskubidea bermatzeko da beraz, benetan, programa exekutatu ahal izango dugu. Kasu honetan emango digu bere lehen argumentua ondoren komando-line ari dira. 2 gehiago: destrinkotuko fitxategia deskonprimitu eta irteera fitxategia nahi dugun. Baina behin ziurtatu gainditu gaituzte balioak eskuineko zenbatekoa egiten dugu, sarrera Huff fitxategia edo ez da ziurtatu nahi dugu. Eta gero, behin Huff fitxategi bat dela bermatzen dugu, eta, ondoren, gure zuhaitz eraiki nahi dugu, hala nola, zuhaitz bat datorren zuhaitz mezua bidali duten pertsona eraiki eraikitzeko sortu. Gero, zuhaitza eraikitzen dugu ondoren eta, ondoren, aurre egin ahal izango dugu, 0 s eta 1s dutela onartu zuen, jarraitu gure zuhaitz zehar da berdin-berdina delako, eta, ondoren, idatzi mezu bat, bit interpretatzeko karakteretan sartu. Eta gero, amaieran ari gara erakusleak direlako, hemen aurre, Ziur ez dugu izan inolako memoria filtrazioak egin nahi dugu eta dugu free guztia. 

Egokia erabilera bermatzea orain Gurekin hat zaharra da. Sarrera bat hartu dugu, hau da, fitxategiaren izena puff izango, eta, ondoren, irteera bat zehaztu dugu, beraz, irteera puffed, testu-fitxategia izango da fitxategi izena. Hori erabilera. Eta orain,, sarrera hori huffed edo ez ziurtatu nahi dugu. Back Thinking zegoen ezer banaketa kodea lagunduko digun fitxategi bat den edo ez huffed edo ez ulertzeko? Ez zen huffile.c Huffeader buruzko informazioa. Huff fitxategi bakoitza lotutako zenbaki magiko bat Huffeader du ezagutzen dugu , ikur bakoitzaren maiztasunak array bat, baita baita checksum gisa. Jakin badakigu, baina peek a dump.c ere hartu dugu, Huff fitxategi batean irakurtzea. Eta, beraz, horretarako, benetan huffed ote den edo ez begiratu behar izan du. Beraz, agian, egitura gisa erabili dump.c genezake gure puff.c. Itzuli pset 4 fitxategi copy.c RGB triples kopiatu izan dugu interpretatzen dugu eta Whodunit eta Resize, era berean, zer egin ahal izango duzu besterik ez da exekutatu komando bezala cp dump.c puff.c eta erabili han kodea batzuk. Hala eta guztiz ere, ez da prozesu bat erraza izango dump.c itzultzeko puff.c baina, gutxienez, ematen du nonbait hasteko nola sarrera hori benetan huffed edo ez ziurtatzeko baita beste zenbait gauza ere. Ziurtatzen dugu, ongi erabili eta ziurtatu sarrera huffed. Denbora bakoitzak egin ditudan dugu gure error egiaztapena egokia egin dugu, beraz, itzuli eta funtzioa irtetea porrota batzuk gertatzen bada, arazoren bat badago. 

Orain zer egin nahi dugun da eraikitzeko benetako zuhaitzaren. Forest erreparatzen badiogu, ez dira funtzio nagusiak 2 ari gara eta oso ezagunak bihurtu nahi du. Funtzio boolearrak landare landareak ez-0 maiztasuna zuhaitza gure basoan barruan. Eta beraz, ez pasatzen da erakuslea baso bat eta zuhaitz baten erakuslea. Quick question: Zenbat baso Huffman zuhaitz bat eraikitzen ari zaren izan al duzu? Gure baso gure mihise bezala da, ezta? Beraz, soilik ari gara 1 basoa izan du, baina zuhaitz bat baino gehiago izan dugu. Beraz, aurretik landare deitzen duzunean, ustez ari zara zure baso egin nahi du. Komando bat dela forest.h begiratuz gero nola baso bat egin ahal izango duzu. Zuhaitz bat landatu ahal izango duzu. Nola egiten den jakin nahi dugu. Eta gero, basoan zuhaitz bat jaso ahal izango duzu, zuhaitz bat kendu, pisu txikiena eta erakuslea eman ahal izateko. Atzera Thinking adibideak egingo dugu geure burua, ginen marrazketa, besterik ez dugu gehitu estekak. Baina hemen ordez loturak gehituz, pentsatu gehiago ari gisa nodo horien 2 kendu eta gero ordez beste bat. Biltzea eta landatzen termino hori adierazteko, 2 zuhaitz ari zaren picking eta, ondoren, beste zuhaitz bat landatu duten 2 zuhaitz haurrak bildu ditu. Huffman-en zuhaitza eraikitzeko, sinbolo eta maiztasunak ordenean irakurri ahal izango duzu Huffeader ematen duelako duzu, maiztasunak array bat ematen dizu. Beraz, aurrera dezakezu, eta besterik gabe, ezer ez ikusi egin 0 du nahi dugu ez delako 256 bukaeran hostoak. Bakarrik nahi dugu hosto diren karaktere kopurua fitxategia erabiltzen diren benetan. Sinbolo horiek irakur dezakezu, eta ez-0 maiztasun duten sinboloak bakoitzean, horiek zuhaitzak izango. Zer egin dezakezu aldi bakoitzean irakurtzen ez-0 maiztasuna sinboloa da, basoan zuhaitz hori landatu ahal izango duzu. Landatu zuhaitz Behin basoan, zuhaitz horiek sartu ahal izango duzu anai-arrebak, beraz, landatu eta non hautatu picking 2 eta, ondoren, landare-1, non 1 planta 2 haur bildu duzula gurasoa. Orduan, zure azken emaitza da zure baso zuhaitz bakar bat izango da. Hau da zure zuhaitz nola eraiki duzu. 

Gauzak gaizki joan izan hemen daude hainbat ari garelako, zuhaitz berriak eginez, eta erakusleak eta gauzak horrela aurre aurre. Erakusleak ginen aurre egin aurretik, bakoitzean dugu malloc'd ziurtatu zuen ez dela itzuliko digu NULL erakuslea balioa egin nahi izan dugu. Beraz, prozesu horren barruan, urrats bat baino gehiago daude hainbat kasu izango non zure programa ezin huts egin. Zer egin nahi duzu akatsak horiek kudeatzeko duzula ziur egin nahi duzun, eta horiek kudeatzeko ondo zehaztutako dio, beraz, inprimatu mezu bat erabiltzaileari kontatzeko zergatik programa irten eta, ondoren, berehala irten da. Error manipulazioa Horretarako, gogoan izan nahi duzula egiaztatzeko bakoitza denbora ez dagoela porrot bat izan daiteke. Bakoitza denbora erakuslea berri bat egiten ari zarela zaitez hori arrakastatsua egin nahi duzu. Zer egin dugu berri bat erakuslea eta malloc da egin da aurretik, eta, ondoren, egiaztatu erakuslea NULL duten ala ez genuke. Beraz, ez dira zenbait kasutan bakarrik egin dezakezu hori izango da, baina, batzuetan, benetan ari zaren funtzio bat deituz eta funtzio horren barruan, duten mallocing bat egiten ari da. Kasu horretan, begiratu dugu atzera kodea barruan, funtzio batzuk horietako batzuek funtzio boolearrak dira. Abstraktua kasu izeneko foo Boolean funtzio bat izanez gero, funtsean, hori onar dezakegu edozein izanda ere foo du egiten gain, Boolean funtzio bat zenetik, egia edo gezurra itzultzen du benetako arrakasta izanez gero, faltsua ez bada. Beraz foo itzulera balioa egia edo gezurra den ala ez egiaztatu nahi dugu. Faltsua bada, horrek esan nahi du mezu bat inprimatu nahi dugun eta programa eta irten. Zer egin nahi dugun foo balio itzulera egiaztatu da. Foo itzultzen Faltsua bada, akats-mota batzuk aurkitu dugun badakigu eta gure programa irten behar dugu. Horretarako modu bat da, baldintza bat dute non benetako funtzioa bera da zure egoera. Esan foo x hartzen. Baldintza bat balitz bezala dugu (foo (x)). Funtsean, horrek esan nahi du foo exekutatzean amaieran true itzultzen bada, ondoren, hau egin ahal izango dugu funtzioa du foo ebaluatzeko ordena osoan egoera ebaluatzeko. Orduan hori nola zerbait egin dezakezu funtzioa itzultzen du egia bada, eta arrakastatsua izan da. Baina error egiaztapena zaudenean, bakarrik nahi duzu zure funtzioak faltsua bada irten. Zer egin ahal duzu besterik ez da gehitu == false, edo, besterik gabe, horren aurrean bang bat gehitu eta, ondoren, (! foo) behar duzu. Baldintza hori gorputz horren barruan error manipulazioa guztiak izango litzateke, bezala, "Ezin izan da sortu Zuhaitz hau" eta, ondoren, 1 edo horrelako zerbait itzultzeko. Zer egiten duen, baina, nahiz foo itzuli faltsua - Esan foo eta TRUE (EGIA) itzultzen du. Orduan ez duzu foo berriro deitzeko. Misconception komun bat da. Zure egoera zelako, dagoeneko ebaluatu, beraz, dagoeneko baduzu emaitza zaren zuhaitz edo horrelako zerbait erabiliz gero edo landare edo pick edo zerbait. Dagoeneko Balio hori. Dagoeneko exekutatu. Beraz, erabilgarria da boolear funtzioak erabili ahal izateko baldintza gisa ala ez exekutatu benetan loop-gorputza delako, funtzioa exekutatzen du, hala ere. 

Gure azken urratsa bigarren mezua da fitxategia idaztean. Behin Huffman zuhaitz eraikitzeko dugu, eta ondoren, mezua idazteko fitxategia nahiko erraza da. Nahiko erraza da 0 s eta 1s jarraitu. Eta, beraz, konbentzio Huffman zuhaitz bat 0 s adierazten utzi badakigu eta 1s adierazteko eskubidea. Beraz, gero, irakurri bit bit by, aldi bakoitzean bat duzula 0 ezkerreko adarraren jarraitu ahal izango duzu, eta, ondoren, behin irakurtzen 1 eskuineko adarraren jarraitu behar duzu. Eta gero, jarraitu zaren hosto bat sakatzen duzun arte dira hostoak, adarrak amaieran direlako. Nola ahal dugu hit hosto bat edo ez den edo ez esango dugu? Esan dugu aurretik. [Ikasleen] erakusleak NULL badira. >> Bai. Dugu hit hosto bat bada, bai ezkerreko eta eskuineko zuhaitzak erakusleak dira NULL bada esan dezakegu. Perfect. Bit bit gure Huff fitxategi irakurri nahi dugun erabaki dugu. Dump.c aurretik ikusi bezala, zer egin zuten irakurri bit bit Huff fitxategia bihurtu eta bakarrik inprimatutako bit horiek zer ziren. Ez ari gara egiten hori. Egiten pixka bat konplexuagoa da zerbait ari gara. Baina zer egin dezakegu Kode bit pixka irakurtzen hartu ahal izango dugu. Hemen dugun Oraindik uneko bit adierazten duen zenbaki oso bit ditugu. Fitxategia bit bit arduratzen hit lerro amaierara arte. Based on, eta gero iterator nolabaiteko izan nahi ari zaren zure zuhaitz zeharkatzeko. Eta gero bit da, 0 edo 1 den, iterator bai mugitu ezkerrera edo eskuinera mugitu nahi duzun modu hosto bat sakatzen duzun arte, beraz, modu guztiak nodo hori Oraindik duzun arte ez du gehiago nodo seinalatu. Zergatik ezin dugu hori Huffman fitxategi bat, baina ez da Morse kodea? Morse kodea anbiguotasun pixka bat delako. Bezala, oh itxaronaldia izan dugu, bidean gutun bat sakatu dugu, eta, beraz, agian hau da gure gutun jarraitu dugu, pixka bat luzeagoa bada, eta ondoren, berriz, izan hit genuke beste gutun bat. Baina hori ez da gertatuko Huffman kodeketa, beraz, atseden ziurtaturik modu bakarra ari dugu karaktere bat sakatu ahal izango dugu Nodo horrek ezkerreko eta eskuineko haurrak dira NULL bada. 

Azkenik, gure memoria libre nahi dugu. Itxi bi Huff fitxategia nahi dugu dugun aurre eta baita gure basoan zuhaitz guztiak kentzeko. Zure ezartzeko oinarrituta, seguruenik ari zaren nahi kendu baso deitu ordez benetan zuhaitz eskuz guztiak igaro. Baina egin duzun aldi baterako zuhaitz edozein bada, libre duten nahi duzu. Zure kodea Badakizu onena, beraz, badakizu non memoria ari zaren esleitzean. Eta beraz, behar izanez gero, joan beharko duzu, hasteko, nahiz eta Kontrol malloc for F'ing ikusten duzunean malloc eta ziur egiten askatzea duzun hori guztia , baina gero soilik zure kodea zeharkatuz, non memoria esleitu dakizukeela ulertzeko. Normalean besterik ez dezakezu esan, "fitxategi baten amaieran besterik ez dut nire baso baso kendu egingo" beraz, funtsean, garbitu memoria hori, free, "Eta ondoren ere naiz fitxategia itxi eta gero, nire programa irten egingo da." Baina bakarrik zure programa irten da? Ez, batzuetan dagoelako izan dezake errore bat gertatu da. Agian ezin dugu fitxategi bat ireki, edo ezin izan dugu beste zuhaitz bat egiteko edo akats-mota batzuk memoria esleipen prozesua gertatu zen, eta, beraz, NULL itzuli du. Errore bat gertatu da, eta, ondoren, itzuli gara eta irten. Beraz, ziurtatu daiteke edozein unetan zure programa irten ondoren, egin nahi duzun, Zure memoria askatzea nahi duzun. Ez da, besterik gabe, zure kodea ixtea funtzioa nagusia amaieran izango da. Adibidez behin atzera begiratu nahi duzu zure kodea duten potentzialki behar baino lehenago itzultzeko agian eta, ondoren, free edozein izanda ere memoria zentzua. Esan deitu zuen baso eta itzuli faltsua. Ondoren Ziurrenik ez duzu behar zure baso kendu ez duzulako baso bat oraindik. Baina, kodea puntu guztietan non itzultzeko behar baino lehenago, baliteke ziur askatzea posible memoria edozein egin nahi duzu. 

Beraz, memoria libre uzten ari gara eta aurre izatea potentzial filtrazioak, ez bakarrik erabili nahi dugu gure epaia eta gure logika baina ere erabil Valgrind dugu ala ez dugu gure memoria askatua dagoela edo ez zehazteko. Puff on edo exekutatu dezakezu Valgrind eta gero ere gainditu behar duzu komando-lerroko argumentu kopuru zuzena Valgrind. Abiarazi ahal izango duzu, baina irteera pixka bat críptica. Ahaztuak dugu erabiltzen Speller pixka bat, baina apur bat gehiago laguntza behar dugu, beraz, ondoren exekutatzen leak-check = full banderak bezala batzuk gehiago, Ziurrenik Valgrind irteera lagungarria batzuk ematen dizkigute. 

Ondoren, beste erabilgarria tip arazketa ari zaren diff komandoa da. Huff langileek ezartzeko sartu ahal izango duzu, exekutatu testu-fitxategi batean, eta, ondoren, bistaratu fitxategi bitarra, binary file Huff, zehatza izan. Ondoren exekutatu zure puff fitxategi bitarra dela, ondoren, haien, zure outputted testu fitxategi berdin-berdina izango da original bat sartu gainditu Hemen hth.txt dut adibide gisa erabiliz, eta hori buruz hitz egin zuen zure zehaztapenak. Hau da, hitzez hitz besterik ez HTH eta, ondoren, lerro berri bat. Baina, zalantzarik gabe, sentitzen free eta behin betiko animatu dira luzeagoa adibideak erabili zure testu-fitxategi. 

Agian konprimitzea filmatu ditzakezu eta, ondoren, deskonprimitzerakoan fitxategiak Speller duzula Gerra eta Bakea bezala erabiltzen batzuk edo Jane Austen edo horrelako zerbait cool mota izango litzateke - edo Austin Powers fitxategi handiago aurre mota genuke ez delako etorri da tresna erabiltzen dugu hurrengo hemen, ls-l bada. Ls, funtsean, gure uneko direktorioan eduki guztiak zerrendatzen gara. Ez-l gainditzea benetan fitxategi horiek tamaina erakusten du. Pset zehaztutako bidez joaten bazara, ibiltzen da benetan fitxategi bitarra sortzen bidez, huffing, eta hori ikusten duzun fitxategiak oso txikiak konprimitzea eta informazio hori guztia itzultzeko kostua espazioa maiztasunak eta gauzak horrela benetako prestazioa outweighs fitxategi konprimitzea Lehenik eta behin. Baina zenbait testu fitxategiak luzeagoa exekutatzen baduzu, eta gero ikusiko onura batzuk lortzeko dezake fitxategi horiek konprimitzea. 

Eta gero, azkenik, gure pal GDB zaharra, hau da, behin betiko handy etorri ere egingo dugu. 

Huff zuhaitzak edo prozesuari buruzko edozein zalantza izan dugu, agian, zuhaitz egiteko Puff Huff'n buruzko galderak beste edozein? Ongi da. Lo inguruan dut apur bat. 

Eskerrik asko, denek. Bisita gidatua 6 izan zen. Eta zorte ona. 

[CS50.TV]