1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Walkthrough - Harjoitus 6]

2
00:00:02,210 --> 00:00:04,810
[Zamyla Chan - Harvardin yliopisto]

3
00:00:04,810 --> 00:00:07,240
[Tämä on CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Hei, kaikki, ja tervetuloa Walkthrough 6: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
Vuonna Huff'n Puff mitä teemme aiotaan käsitellä Huffman pakatun tiedoston

6
00:00:17,440 --> 00:00:20,740
ja sitten turvotusta se takaisin ylös, niin puretaan se,

7
00:00:20,740 --> 00:00:25,810
jotta voimme kääntää 0s ja 1s että käyttäjä lähettää meille

8
00:00:25,810 --> 00:00:30,660
ja muuntaa sen takaisin alkuperäiseen tekstiin.

9
00:00:30,660 --> 00:00:34,360
PSET 6 tulee olemaan melko viileä, koska olet menossa nähdä joitakin työkaluja

10
00:00:34,360 --> 00:00:41,730
että käytit PSET 4 ja PSET 5 ja millaisia ​​niiden yhdistämistä 1 aika siisti käsite

11
00:00:41,730 --> 00:00:43,830
kun tulet ajatella sitä.

12
00:00:43,830 --> 00:00:50,110
>> Myös luultavasti, PSET 4 ja 5 olivat haastavin psets että meillä oli tarjota.

13
00:00:50,110 --> 00:00:53,950
Joten nyt meillä on tämä 1 enemmän PSET C,

14
00:00:53,950 --> 00:00:56,480
ja sitten sen jälkeen, että olemme web ohjelmointi.

15
00:00:56,480 --> 00:01:02,310
Joten onnitella itseänne saada yli kovimmat piikki CS50.

16
00:01:03,630 --> 00:01:09,760
>> Liikettä ja Huff'n Puff, meidän työkalupakki tästä PSET tulevat olemaan Huffman puita,

17
00:01:09,760 --> 00:01:14,700
joten ymmärtäminen ei vain miten binääripuita työtä, mutta myös nimenomaan Huffman puita,

18
00:01:14,700 --> 00:01:16,240
miten he rakennettu.

19
00:01:16,240 --> 00:01:20,210
Ja sitten me aiomme olla paljon jakelun koodia tässä PSET,

20
00:01:20,210 --> 00:01:22,480
ja tulemme näkemään, että todellisuudessa osa koodia

21
00:01:22,480 --> 00:01:24,670
emme ehkä pysty täysin ymmärtämään vielä,

22
00:01:24,670 --> 00:01:30,080
ja niin ne tulevat olemaan. C-tiedostoja, mutta sitten heidän mukanaan. h tiedostot

23
00:01:30,080 --> 00:01:34,300
antaa meille tarpeeksi ymmärrystä, että tarvitsemme, jotta tiedämme, miten nämä toiminnot toimivat

24
00:01:34,300 --> 00:01:38,100
tai ainakin mitä heidän pitäisi tehdä - niiden tulot ja lähdöt -

25
00:01:38,100 --> 00:01:40,760
vaikka emme tiedä mitä tapahtuu musta laatikko

26
00:01:40,760 --> 00:01:44,090
tai eivät ymmärrä mitä tapahtuu mustan laatikon sisällä.

27
00:01:44,090 --> 00:01:49,400
Ja sitten lopuksi, kuten tavallista, olemme tekemisissä uusien tietorakenteiden,

28
00:01:49,400 --> 00:01:51,840
tietyntyyppisiin solmujen osoittavat tiettyjä asioita,

29
00:01:51,840 --> 00:01:56,080
ja niin tässä ottaa kynän ja paperin paitsi suunnitteluprosessia

30
00:01:56,080 --> 00:01:58,470
ja kun yrität selvittää miten PSET pitäisi toimia

31
00:01:58,470 --> 00:02:00,520
mutta myös aikana virheenkorjaus.

32
00:02:00,520 --> 00:02:06,140
Voit olla GDB rinnalla kynä ja paperia, kun otat alas mitä arvot ovat,

33
00:02:06,140 --> 00:02:09,320
missä nuolet osoittavat, ja tuollaista.

34
00:02:09,320 --> 00:02:13,720
>> Ensimmäinen katsokaamme Huffman puita.

35
00:02:13,720 --> 00:02:19,600
Huffman puut ovat binääripuita, eli kukin solmu on vain 2 lasta.

36
00:02:19,600 --> 00:02:24,870
In Huffman puita ominaisuus on se, että yleisin arvot

37
00:02:24,870 --> 00:02:27,140
edustavat vähiten bittiä.

38
00:02:27,140 --> 00:02:32,690
Näimme luennossa esimerkkejä morseaakkoset, millaisia ​​konsernin joitakin kirjeitä.

39
00:02:32,690 --> 00:02:38,030
Jos olet yrittää kääntää tai E, esimerkiksi

40
00:02:38,030 --> 00:02:43,940
olet kääntämiseen että usein, joten sen sijaan, että käyttää koko joukko bittejä

41
00:02:43,940 --> 00:02:48,640
myönnetty, että tavallisia tietotyyppiä, voit pakata sen alas vähemmän,

42
00:02:48,640 --> 00:02:53,730
ja sitten nämä kirjeet, jotka ovat edustettuina harvemmin ovat edustettuina pidemmän bittiä

43
00:02:53,730 --> 00:02:59,840
koska sinulla on varaa, että kun punnitaan taajuudet että näitä kirjaimia.

44
00:02:59,840 --> 00:03:03,020
Meillä on sama idea täällä Huffman puita

45
00:03:03,020 --> 00:03:12,360
jossa teemme ketju, eräänlainen polku päästä tiettyjä merkkejä.

46
00:03:12,360 --> 00:03:14,470
Ja sitten hahmoja, jotka ovat eniten taajuus

47
00:03:14,470 --> 00:03:17,940
aiotaan edustettuina vähiten bittiä.

48
00:03:17,940 --> 00:03:22,020
>> Tapa, että voit rakentaa Huffman puu

49
00:03:22,020 --> 00:03:27,430
on sijoittamalla kaikki merkit, jotka esiintyvät tekstissä

50
00:03:27,430 --> 00:03:30,630
ja lasketaan niiden tiheys, kuinka usein ne näyttävät.

51
00:03:30,630 --> 00:03:33,880
Tämä voi olla joko laskea, kuinka monta kertaa ne kirjaimia

52
00:03:33,880 --> 00:03:40,270
tai ehkä prosenttiosuus pois kaikki merkit, kuinka monta kunkin näkyviin.

53
00:03:40,270 --> 00:03:44,270
Ja niin mitä teet on kun olet kaiken tämän kartoitettu,

54
00:03:44,270 --> 00:03:49,060
sitten etsiä 2 alimmat taajuudet ja sitten liittyä ne sisarukset

55
00:03:49,060 --> 00:03:55,660
jos niin isäsolmuun on taajuus, joka on summa sen 2 lasta.

56
00:03:55,660 --> 00:04:00,870
Ja sitten Sovitun sanoa että vasen solmu,

57
00:04:00,870 --> 00:04:03,770
seuraat että seuraamalla 0 sivuliike,

58
00:04:03,770 --> 00:04:08,140
ja sitten oikeanpuoleisin solmu on 1 haara.

59
00:04:08,140 --> 00:04:16,040
Kuten näimme morseaakkoset, yksi ähäkutti oli, että jos sinulla olisi vain piippaus ja äänimerkki

60
00:04:16,040 --> 00:04:18,120
se oli epäselvä.

61
00:04:18,120 --> 00:04:22,430
Se voi olla joko 1 kirjain tai se voi olla sekvenssi 2 kirjainta.

62
00:04:22,430 --> 00:04:27,790
Ja niin mitä Huffman puita tekee siksi luonteeltaan merkit

63
00:04:27,790 --> 00:04:34,140
tai meidän lopullinen todellisia merkkejä on viimeksi solmujen Branch -

64
00:04:34,140 --> 00:04:39,300
me sanomme niistä, kuten lehtiä - nojalla, että ei voi olla mitään epäselvyyttä

65
00:04:39,300 --> 00:04:45,160
suhteen mikä kirjain yrität koodata kanssa sarjan bittien

66
00:04:45,160 --> 00:04:50,670
koska missään pitkin bitit, jotka edustavat 1 kirjain

67
00:04:50,670 --> 00:04:55,960
sinä kohtaat toisen koko kirjeen, ja ei tule mitään sekaannusta siellä.

68
00:04:55,960 --> 00:04:58,430
Mutta me mennä esimerkkejä että te voitte itse nähdä, että

69
00:04:58,430 --> 00:05:02,120
eikä meistä vain kertoa teille, että se on totta.

70
00:05:02,120 --> 00:05:06,390
>> Katsotaanpa yksinkertainen esimerkki Huffman puu.

71
00:05:06,390 --> 00:05:09,380
Minulla on merkkijono täällä, että on 12 merkkiä pitkä.

72
00:05:09,380 --> 00:05:14,010
Olen 4 Koska 6 Bs ja 2 Cs.

73
00:05:14,010 --> 00:05:17,270
Ensimmäinen askel olisi laskea.

74
00:05:17,270 --> 00:05:20,760
Kuinka monta kertaa se näyttää? Vaikuttaa siltä 4 kertaa merkkijono.

75
00:05:20,760 --> 00:05:25,060
B ilmestyy 6 kertaa, ja C näkyy 2 kertaa.

76
00:05:25,060 --> 00:05:28,970
Luonnollisesti, aion sanoa Käytän B useimmiten,

77
00:05:28,970 --> 00:05:35,970
niin haluan edustaa B Vähiten bittiä Vähiten 0s ja 1s.

78
00:05:35,970 --> 00:05:42,600
Ja sitten olen myös menossa odottaa C vaativat eniten määrä 0s ja 1s samoin.

79
00:05:42,600 --> 00:05:48,550
Ensimmäinen mitä tein täällä laitoin ne nousevassa järjestyksessä suhteen taajuuden.

80
00:05:48,550 --> 00:05:52,710
Näemme, että C-ja, jotka ovat meidän 2 alimpia taajuuksia.

81
00:05:52,710 --> 00:06:00,290
Luomme isäsolmuun, ja että isäsolmuun ei ole kirje liittyy siihen,

82
00:06:00,290 --> 00:06:05,070
mutta sillä on taajuus, joka on summa.

83
00:06:05,070 --> 00:06:08,780
Summa tulee 2 + 4, joka on 6.

84
00:06:08,780 --> 00:06:10,800
Sitten seuraa vasempaan haaraan.

85
00:06:10,800 --> 00:06:14,970
Jos olisimme tuossa 6 solmu, niin me seuraisi 0 päästä C

86
00:06:14,970 --> 00:06:17,450
ja sitten 1 päästäkseen A.

87
00:06:17,450 --> 00:06:20,300
Joten nyt meillä on 2 solmua.

88
00:06:20,300 --> 00:06:23,920
Meillä on arvo 6 ja sen jälkeen meillä on myös toinen solmu arvo 6.

89
00:06:23,920 --> 00:06:28,550
Ja niin nuo 2 eivät vain 2 alin lisäksi vain 2, jotka ovat jäljellä,

90
00:06:28,550 --> 00:06:33,820
joten liitymme niitä toisen vanhemman kanssa summa on 12.

91
00:06:33,820 --> 00:06:36,300
Joten tässä meillä on Huffman puu

92
00:06:36,300 --> 00:06:40,020
mistä saa B, että olisi vain bitti 1

93
00:06:40,020 --> 00:06:45,430
ja sitten päästä meillä olisi 01 ja C ottaa 00.

94
00:06:45,430 --> 00:06:51,300
Joten tässä me näemme, että pohjimmiltaan olemme edustavat näitä chars joko 1 tai 2 bittiä

95
00:06:51,300 --> 00:06:55,160
jossa B, kuten ennustettiin, on vähiten.

96
00:06:55,160 --> 00:07:01,730
Ja sitten odotimme C on eniten, mutta koska se on niin pieni Huffman puu,

97
00:07:01,730 --> 00:07:06,020
sitten edustaa myös 2 bittiä toisin kuin jossain keskellä.

98
00:07:07,820 --> 00:07:11,070
>> Vain mennä yli toiselle yksinkertainen esimerkki Huffman puu,

99
00:07:11,070 --> 00:07:19,570
että sinulla on merkkijono "Hello."

100
00:07:19,570 --> 00:07:25,360
Mitä tehdä, on ensin sanoa, kuinka monta kertaa se H näkyvät tässä?

101
00:07:25,360 --> 00:07:34,200
H ilmestyy kerran ja sitten tulee e kerran ja sitten meillä on l esiintyy kahdesti

102
00:07:34,200 --> 00:07:36,580
ja o esiintyvät kerran.

103
00:07:36,580 --> 00:07:44,310
Ja niin sitten odotamme mikä kirjain tulee edustaa vähintään bittien?

104
00:07:44,310 --> 00:07:47,450
[Opiskelija] L. >> L. Joo. l on oikea.

105
00:07:47,450 --> 00:07:50,730
Odotamme l edustaa vähiten bittien

106
00:07:50,730 --> 00:07:55,890
koska l käytetään eniten merkkijonon "Hei."

107
00:07:55,890 --> 00:08:04,280
Mitä aion tehdä nyt vetää näitä solmuja.

108
00:08:04,280 --> 00:08:15,580
I on 1, joka on H, ja sitten toinen 1, joka on e, ja sitten 1, joka on O -

109
00:08:15,580 --> 00:08:23,410
nyt Laitan ne järjestyksessä - ja sitten 2, joka on l.

110
00:08:23,410 --> 00:08:32,799
Sitten sanon niin että voin rakentaa Huffman puu on löytää 2 solmut vähiten taajuudet

111
00:08:32,799 --> 00:08:38,010
ja ne sisarukset luomalla isäsolmuun.

112
00:08:38,010 --> 00:08:41,850
Täällä meillä on 3 solmut matalin taajuus. He kaikki 1.

113
00:08:41,850 --> 00:08:50,620
Joten tässä me valitsemme kumpi aiomme yhdistää ensin.

114
00:08:50,620 --> 00:08:54,850
Sanotaan valitsen H ja E.

115
00:08:54,850 --> 00:09:01,150
Summa 1 + 1 on 2, mutta tämä solmu ei ole kirje liittyy siihen.

116
00:09:01,150 --> 00:09:04,440
Se vain pitää arvoa.

117
00:09:04,440 --> 00:09:10,950
Nyt katsomme seuraavan 2 alimmat taajuudet.

118
00:09:10,950 --> 00:09:15,590
Se on 2 ja 1. Se voisi olla joko näistä 2, mutta aion valita tämä.

119
00:09:15,590 --> 00:09:18,800
Summa on 3.

120
00:09:18,800 --> 00:09:26,410
Ja sitten lopuksi, minulla on vain 2 vasemmalle, niin sitten se tulee 5.

121
00:09:26,410 --> 00:09:32,010
Sitten täällä, odotetusti, jos en täytä koodaus, että

122
00:09:32,010 --> 00:09:37,480
1s aina oikeaan haaraan ja 0s ovat vasen.

123
00:09:37,480 --> 00:09:45,880
Sitten meillä on l edustaa vain 1 vähän ja sitten O 2

124
00:09:45,880 --> 00:09:52,360
ja sitten e 2: lla ja sitten H putoaa 3 bittiä.

125
00:09:52,360 --> 00:09:59,750
Joten voit lähettää tämän viestin "Hei" eikä todellisuudessa käyttävät merkkejä

126
00:09:59,750 --> 00:10:02,760
vain hieman 0s ja 1s.

127
00:10:02,760 --> 00:10:07,910
Muista kuitenkin, että useissa tapauksissa meillä oli suhteita meidän taajuudella.

128
00:10:07,910 --> 00:10:11,900
Olisimme voineet joko liittynyt H ja O Ensimmäinen Ehkä.

129
00:10:11,900 --> 00:10:15,730
Tai sitten myöhemmin, kun meillä oli l edustaa 2

130
00:10:15,730 --> 00:10:19,410
sekä liittyi jota edustaa 2, olisimme voineet liittyä joko yksi.

131
00:10:19,410 --> 00:10:23,630
>> Ja niin kun lähetät 0s ja 1s, jotka todella ei takaa

132
00:10:23,630 --> 00:10:27,090
että vastaanottaja voi täysin lukea viestisi oikeus pois bat

133
00:10:27,090 --> 00:10:30,490
koska he eivät tiedä, mikä päätös teit.

134
00:10:30,490 --> 00:10:34,920
Joten kun olemme tekemisissä Huffman puristus,

135
00:10:34,920 --> 00:10:40,090
jotenkin meidän täytyy kertoa vastaanottajalle viestimme miten päätimme -

136
00:10:40,090 --> 00:10:43,470
Heidän täytyy tietää jonkinlaista ylimääräistä tietoa

137
00:10:43,470 --> 00:10:46,580
lisäksi pakatun viestin.

138
00:10:46,580 --> 00:10:51,490
Heidän täytyy ymmärtää, mitä puu todellisuudessa näyttää,

139
00:10:51,490 --> 00:10:55,450
miten todella tehdä näitä päätöksiä.

140
00:10:55,450 --> 00:10:59,100
>> Täällä olimme juuri tekemässä esimerkkejä perustuu todelliseen määrä,

141
00:10:59,100 --> 00:11:01,550
mutta joskus voi olla myös Huffman puu

142
00:11:01,550 --> 00:11:05,760
perustuu taajuus, jolla kirjaimia, ja se on täsmälleen sama prosessi.

143
00:11:05,760 --> 00:11:09,090
Täällä olen ilmaista sen kannalta prosentteina tai murto-

144
00:11:09,090 --> 00:11:11,290
joten tässä täsmälleen sama asia.

145
00:11:11,290 --> 00:11:15,300
Minusta 2 alin, lasketaan ne yhteen, seuraavat 2 alin, lasketaan ne yhteen,

146
00:11:15,300 --> 00:11:19,390
kunnes olen täysi puu.

147
00:11:19,390 --> 00:11:23,610
Vaikka voisimme tehdä sen joko niin, kun olemme tekemisissä prosenttiosuudet,

148
00:11:23,610 --> 00:11:27,760
se tarkoittaa, että olemme jakamalla asioita ja käsittelevät desimaalit tai paremminkin kelluu

149
00:11:27,760 --> 00:11:30,900
jos ajattelemme tietorakenteita pään.

150
00:11:30,900 --> 00:11:32,540
Mitä tiedämme kelluu?

151
00:11:32,540 --> 00:11:35,180
Mikä yleinen ongelma, kun olemme tekemisissä kelluu?

152
00:11:35,180 --> 00:11:38,600
[Opiskelija] Epätarkat aritmeettinen. >> Joo. Epätarkkuutta.

153
00:11:38,600 --> 00:11:43,760
Koska liukuluku epätarkkuus, tämä PSET jotta voimme varmistaa

154
00:11:43,760 --> 00:11:49,450
että emme menetä mitään arvoja, niin olemme todella aiotaan käsitellä count.

155
00:11:49,450 --> 00:11:54,880
Joten jos olit ajatella Huffman solmun, jos näytät takaisin rakenteeseen täällä,

156
00:11:54,880 --> 00:12:01,740
jos tarkastellaan vihreitä se taajuus siihen liittyvä

157
00:12:01,740 --> 00:12:08,760
samoin kuin se viittaa solmun sen vasemmalla puolella sekä solmu sen oikealla puolella.

158
00:12:08,760 --> 00:12:13,970
Ja sitten punaisia ​​siellä on myös luonteeltaan niihin liittyviä.

159
00:12:13,970 --> 00:12:18,900
Emme aio tehdä erillisten vanhemmille ja sitten lopullinen solmut,

160
00:12:18,900 --> 00:12:23,680
jota me kutsumme lehtiä, vaan ne täytyy vain NULL-arvoja.

161
00:12:23,680 --> 00:12:31,050
Sillä jokainen solmu saamme merkin, symbolin että solmu edustaa,

162
00:12:31,050 --> 00:12:40,490
Sitten taajuus sekä osoitin sen vasen lapsi sekä sen oikea lapsi.

163
00:12:40,490 --> 00:12:45,680
Lehdet, jotka ovat hyvin alhaalla, olisi myös solmun osoittimet

164
00:12:45,680 --> 00:12:49,550
niiden vasemmalle ja heidän oikeutensa, mutta koska arvot eivät viittaa todellisiin solmuja,

165
00:12:49,550 --> 00:12:53,970
mikä niiden arvo on? >> [Opiskelija] NULL. >> NULL. Aivan.

166
00:12:53,970 --> 00:12:58,430
Tässä esimerkki siitä, miten voi edustaa taajuus kellukkeet,

167
00:12:58,430 --> 00:13:02,130
mutta aiomme olla tekemisissä sen kanssa kokonaislukuja,

168
00:13:02,130 --> 00:13:06,780
joten kaikki tein on muuttaa tietotyyppiä siellä.

169
00:13:06,780 --> 00:13:09,700
>> Mennään edelleen hieman enemmän monimutkaisempi esimerkki.

170
00:13:09,700 --> 00:13:13,360
Mutta nyt olemme tehneet yksinkertaiset, se on aivan sama prosessi.

171
00:13:13,360 --> 00:13:20,290
Löydät 2 alimmat taajuudet, summa taajuudet

172
00:13:20,290 --> 00:13:22,450
ja se on uutta taajuutta oman vanhemman solmun,

173
00:13:22,450 --> 00:13:29,310
joka sitten osoittaa sen vasemmalle kanssa 0 haara ja oikealle 1 haara.

174
00:13:29,310 --> 00:13:34,200
Jos meillä on merkkijono "Tämä on cs50", niin laskemme kuinka monta kertaa on T mainitaan,

175
00:13:34,200 --> 00:13:38,420
h mainittiin, i, s, c, 5, 0.

176
00:13:38,420 --> 00:13:42,010
Sitten tein täällä on kanssa punainen solmut juuri istutettu,

177
00:13:42,010 --> 00:13:48,530
Sanoin Aion olla näitä merkkejä lopulta alareunassa minun puu.

178
00:13:48,530 --> 00:13:51,740
Ne tulevat olemaan kaikki lehdet.

179
00:13:51,740 --> 00:13:58,200
Sitten mitä tein on I lajiteltu niiden esiintymistiheyden nousevassa järjestyksessä,

180
00:13:58,200 --> 00:14:02,950
ja tämä on todella niin, että PSET koodi tekee sen

181
00:14:02,950 --> 00:14:07,550
on se lajittelee sen taajuus ja sitten aakkosjärjestyksessä.

182
00:14:07,550 --> 00:14:13,870
Niin se on numerot ensin ja sitten aakkosjärjestykseen taajuus.

183
00:14:13,870 --> 00:14:18,520
Sitten mitä haluaisin tehdä on löytäisin 2 alhaisin. Se on 0 ja 5.

184
00:14:18,520 --> 00:14:22,390
Haluaisin tiivistää niitä, ja se on 2. Sitten haluaisin jatkaa, löytää seuraavan 2 alhaisin.

185
00:14:22,390 --> 00:14:26,100
Nämä ovat kaksi 1s, ja sitten ne tulevat 2 samoin.

186
00:14:26,100 --> 00:14:31,570
Nyt tiedän, että minun seuraava askel tulee olemaan liittyä pienin numero,

187
00:14:31,570 --> 00:14:41,380
joka on T, 1, ja valitsemalla sitten yksi solmuista, joka on 2, kun taajuus.

188
00:14:41,380 --> 00:14:44,560
Joten tässä meillä on 3 vaihtoehtoa.

189
00:14:44,560 --> 00:14:47,980
Mitä aion tehdä dia vain visuaalisesti järjestää ne sinulle

190
00:14:47,980 --> 00:14:51,790
jotta näet miten olen rakentaa sen.

191
00:14:51,790 --> 00:14:59,040
Mitä koodin ja jakelu koodin aikoo tehdä olisi liittyä T yksi

192
00:14:59,040 --> 00:15:01,410
kanssa 0 ja 5 solmun.

193
00:15:01,410 --> 00:15:05,060
Joten sitten, että summat 3, ja sitten jatkamme prosessia.

194
00:15:05,060 --> 00:15:08,660
2 ja 2 ovat nyt pienin, niin sitten nuo summan 4.

195
00:15:08,660 --> 00:15:12,560
Jokainen jälkeen toistaiseksi? Okei.

196
00:15:12,560 --> 00:15:16,410
Sitten sen jälkeen, että meillä on 3 ja 3, jotka on laskettava yhteen,

197
00:15:16,410 --> 00:15:21,650
joten taas olen vain vaihtaa niin, että voit nähdä visuaalisesti niin, että se ei ole liian sotkuinen.

198
00:15:21,650 --> 00:15:25,740
Sitten meillä on 6, ja sitten meidän viimeinen askel on nyt, että meillä on vain 2 solmua

199
00:15:25,740 --> 00:15:30,440
meidän summa niille, jotta juuriin puu, joka on 10.

200
00:15:30,440 --> 00:15:34,100
Ja numero 10 on järkeä, koska jokainen solmu edustaa,

201
00:15:34,100 --> 00:15:40,750
niiden arvo, tiheys numero, oli kuinka monta kertaa he ilmestyi merkkijono,

202
00:15:40,750 --> 00:15:46,350
ja sitten meillä on 5 merkkiä meidän merkkijonon, joten on järkevää.

203
00:15:48,060 --> 00:15:52,320
Jos katsomme ylös kuinka me todella koodata sitä,

204
00:15:52,320 --> 00:15:56,580
kuten odotettua, i ja t, jotka näkyvät useimmiten

205
00:15:56,580 --> 00:16:01,350
edustaa vähiten bittien määrä.

206
00:16:03,660 --> 00:16:05,660
>> Ole varovainen täällä.

207
00:16:05,660 --> 00:16:09,780
Vuonna Huffman puita asia todella on väliä.

208
00:16:09,780 --> 00:16:13,670
Isot S on erilainen kuin pieniä s.

209
00:16:13,670 --> 00:16:21,260
Jos meillä olisi "Tämä on CS50" isoilla kirjaimilla, niin pieni ta tuntuisivat vain kahdesti,

210
00:16:21,260 --> 00:16:27,120
olisi solmu 2 sen arvo, ja sitten isot S olisi vain kerran.

211
00:16:27,120 --> 00:16:33,440
Joten teidän puu muuttuisi rakenteita, koska sinulla todella on ylimääräistä lehtiä täällä.

212
00:16:33,440 --> 00:16:36,900
Mutta summa olisi edelleen 10.

213
00:16:36,900 --> 00:16:39,570
Sitähän me todella olemaan soittamalla tarkistussumma,

214
00:16:39,570 --> 00:16:44,060
Lisäksi kaikkien laskee.

215
00:16:46,010 --> 00:16:50,990
>> Nyt kun olemme kattaa Huffman puita, voimme sukeltaa Huff'n Puff, PSET.

216
00:16:50,990 --> 00:16:52,900
Aiomme aloittaa osan kysymyksiä,

217
00:16:52,900 --> 00:16:57,990
ja tämä on menossa sinut tottunut binary puita ja miten toimia noin että:

218
00:16:57,990 --> 00:17:03,230
piirustus solmut, luoda omia typedef struct varten solmun,

219
00:17:03,230 --> 00:17:07,230
ja nähdä kuinka saatat lisättävän binääripuu, joka on lajiteltu,

220
00:17:07,230 --> 00:17:09,050
liikkumisesta, ja tuollaista.

221
00:17:09,050 --> 00:17:14,560
Tämä tieto on varmasti auta sinua, kun sukeltaa Huff'n Puff osa

222
00:17:14,560 --> 00:17:17,089
ja PSET.

223
00:17:19,150 --> 00:17:26,329
Vuonna standardin painos PSET, teidän tehtävänne on toteuttaa Puff,

224
00:17:26,329 --> 00:17:30,240
ja hakkeri versiossa sinun tehtäväsi on toteuttaa Huff.

225
00:17:30,240 --> 00:17:38,490
Mikä Huff ei se vie tekstin ja sitten se muuntaa sen 0s ja 1s,

226
00:17:38,490 --> 00:17:41,990
joten prosessi, että teimme yläpuolella, jossa laskimme taajuudet

227
00:17:41,990 --> 00:17:50,970
ja sitten tehdään puusta ja sanoi sitten: "Miten saan T?"

228
00:17:50,970 --> 00:17:54,840
T edustaa 100, tuollaista,

229
00:17:54,840 --> 00:17:58,860
ja sitten Huff veisi tekstin ja sitten lähtö että binary.

230
00:17:58,860 --> 00:18:04,920
Mutta myös koska tiedämme, että haluamme antaa meidän viestin vastaanottaja

231
00:18:04,920 --> 00:18:11,790
luoda uudelleen täsmälleen samassa puussa, se sisältää myös tietoa taajuus laskee.

232
00:18:11,790 --> 00:18:17,980
Sitten Puff saamme binaaritiedoston 0 ja 1s

233
00:18:17,980 --> 00:18:21,740
ja annetaan myös tiedot taajuuksilla.

234
00:18:21,740 --> 00:18:26,740
Käännämme kaikki nämä 0s ja 1s takaisin alkuperäiseen viesti oli,

235
00:18:26,740 --> 00:18:29,350
joten olemme purettaessa että.

236
00:18:29,350 --> 00:18:36,450
Jos teet Standard Edition, sinun ei tarvitse toteuttaa Huff,

237
00:18:36,450 --> 00:18:39,290
niin sitten voit vain käyttää henkilöstön toteuttamista Huff.

238
00:18:39,290 --> 00:18:42,080
On ohjeita spec, miten tehdä se.

239
00:18:42,080 --> 00:18:48,780
Voit suorittaa henkilöstö täytäntöönpanoa Huff tietystä tekstitiedosto

240
00:18:48,780 --> 00:18:53,270
ja sitten käyttää tuotoksen kuin panos Puff.

241
00:18:53,270 --> 00:18:59,330
>> Kuten aiemmin mainitsin, meillä on paljon jakelu koodin tämä yksi.

242
00:18:59,330 --> 00:19:01,810
Aion aloittaa menee läpi.

243
00:19:01,810 --> 00:19:04,400
Aion viettää suurimman osan aikaa. H tiedostot

244
00:19:04,400 --> 00:19:07,660
koska. C-tiedostoja, koska meillä on. h

245
00:19:07,660 --> 00:19:11,650
ja joka tarjoaa meille prototyyppejä toimintoja,

246
00:19:11,650 --> 00:19:15,520
emme täysin täytyy ymmärtää -

247
00:19:15,520 --> 00:19:20,280
Jos et ymmärrä mitä tapahtuu vuonna. C-tiedostoja, niin älä huolehdi liikaa,

248
00:19:20,280 --> 00:19:23,600
mutta ehdottomasti kokeilla katsomaan, koska se saattaa antaa joitakin vihjeitä

249
00:19:23,600 --> 00:19:29,220
ja se on hyödyllistä tottua lukea toisten koodia.

250
00:19:38,940 --> 00:19:48,270
>> Tarkasteltaessa huffile.h vuonna kommentit julistaa kerros abstraktio Huffman-koodattu tiedostot.

251
00:19:48,270 --> 00:20:01,660
Jos menemme alas, voimme nähdä, että siellä on enintään 256 symboleja, että saatamme tarvita koodeja.

252
00:20:01,660 --> 00:20:05,480
Tämä sisältää kaikki aakkosten - isot ja pienet -

253
00:20:05,480 --> 00:20:08,250
ja sitten symboleja ja numeroita jne.

254
00:20:08,250 --> 00:20:11,930
Sitten täällä meillä maaginen tunnistenumero Huffman-koodattu tiedosto.

255
00:20:11,930 --> 00:20:15,890
Sisällä Huffman he aikovat olla tietty maaginen numero

256
00:20:15,890 --> 00:20:18,560
liittyvä otsikko.

257
00:20:18,560 --> 00:20:21,110
Tämä saattaa näyttää vain satunnainen maaginen luku,

258
00:20:21,110 --> 00:20:27,160
mutta jos todella kääntää ASCII, niin se todella täsmennetään Huff.

259
00:20:27,160 --> 00:20:34,290
Täällä meillä struct varten Huffman-koodattu tiedosto.

260
00:20:34,290 --> 00:20:39,670
Siellä on kaikki nämä ominaisuudet liittyvät Huff-tiedosto.

261
00:20:39,670 --> 00:20:47,080
Sitten täällä meillä otsikkoa Huff tiedostoa, joten kutsumme sitä Huffeader

262
00:20:47,080 --> 00:20:50,810
sijaan lisätä ylimääräisiä h, koska se kuulostaa samalta muutenkin.

263
00:20:50,810 --> 00:20:52,720
Cute.

264
00:20:52,720 --> 00:20:57,790
Meillä on maaginen numero liittyy siihen.

265
00:20:57,790 --> 00:21:09,040
Jos se on todellinen Huff tiedoston, se tulee olemaan numero ylhäällä, tämä taika yksi.

266
00:21:09,040 --> 00:21:14,720
Ja niin se on jono.

267
00:21:14,720 --> 00:21:18,750
Joten kunkin symbolin, joita on 256,

268
00:21:18,750 --> 00:21:24,760
se tulee luetella mitä taajuutta näiden symbolien ovat Huff tiedosto.

269
00:21:24,760 --> 00:21:28,090
Ja sitten lopuksi meillä tarkistussumma taajuuksilla,

270
00:21:28,090 --> 00:21:32,160
jonka pitäisi olla niiden summa taajuuksilla.

271
00:21:32,160 --> 00:21:36,520
Niin, että mitä Huffeader on.

272
00:21:36,520 --> 00:21:44,600
Sitten meillä on joitakin toimintoja, jotka palauttavat seuraava bitti Huff tiedosto

273
00:21:44,600 --> 00:21:52,580
sekä kirjoittaa vähän sen Huff tiedoston, ja sitten tämä toiminto tässä, hfclose,

274
00:21:52,580 --> 00:21:54,650
että todellisuudessa sulkee Huff-tiedosto.

275
00:21:54,650 --> 00:21:57,290
Ennen olimme tekemisissä suoraan vain FSulje,

276
00:21:57,290 --> 00:22:01,190
mutta kun on Huff tiedoston sijaan fclosing se

277
00:22:01,190 --> 00:22:06,080
mitä olet todella aikoo tehdä, on hfclose ja hfopen sitä.

278
00:22:06,080 --> 00:22:13,220
Nämä ovat tiettyjä toimintoja Huff tiedostojen aiomme olla tekemisissä.

279
00:22:13,220 --> 00:22:19,230
Sitten täällä luemme otsikko ja kirjoita otsikko.

280
00:22:19,230 --> 00:22:25,700
>> Vain lukemalla. H tiedosto me voi sellaista saada tunteen mitä Huff tiedosto voi olla,

281
00:22:25,700 --> 00:22:32,480
Mitä ominaisuuksia sillä on, ilman että menee huffile.c,

282
00:22:32,480 --> 00:22:36,750
joka, jos me sukeltaa, tulee olemaan hieman monimutkaisempi.

283
00:22:36,750 --> 00:22:41,270
Siinä on kaikki tiedoston I / O täällä tekemisissä viitteitä.

284
00:22:41,270 --> 00:22:48,010
Tässä näemme, että kun me kutsumme hfread, esimerkiksi, se on edelleen tekemisissä fread.

285
00:22:48,010 --> 00:22:53,050
Emme päästä eroon näistä toiminnoista kokonaan, mutta lähetämme ne on pidettävä huolta

286
00:22:53,050 --> 00:22:59,760
sisällä Huff tiedoston sijaan tehdä kaiken sen itse.

287
00:22:59,760 --> 00:23:02,300
Voit vapaasti selata tätä jos olet kiinnostunut

288
00:23:02,300 --> 00:23:08,410
ja mene ja kuori kerros takaisin hieman.

289
00:23:20,650 --> 00:23:24,060
>> Seuraava kuva, että olemme menossa katsomaan on tree.h.

290
00:23:24,060 --> 00:23:30,210
Aikaisemmin Walkthrough liukuu sanoimme odotamme Huffman solmu

291
00:23:30,210 --> 00:23:32,960
ja teimme typedef struct solmu.

292
00:23:32,960 --> 00:23:38,360
Odotamme sen olevan symbolin, taajuus, ja sitten 2 solmun tähteä.

293
00:23:38,360 --> 00:23:41,870
Tässä tapauksessa mitä teemme on tämä on pohjimmiltaan sama

294
00:23:41,870 --> 00:23:46,880
paitsi sen sijaan solmun aiomme kutsua niitä puita.

295
00:23:48,790 --> 00:23:56,760
Meillä on toiminto, kun soitat tehdä puusta se palauttaa sinut puu osoittimen.

296
00:23:56,760 --> 00:24:03,450
Takaisin oikeinkirjoituksen, kun tekivät uuden solmun

297
00:24:03,450 --> 00:24:11,410
Sanoit solmu * uusi sana = malloc (sizeof) ja tuollaista.

298
00:24:11,410 --> 00:24:17,510
Pohjimmiltaan mktree aiotaan käsitellä sen sinulle.

299
00:24:17,510 --> 00:24:20,990
Vastaavasti, kun haluat poistaa puun,

300
00:24:20,990 --> 00:24:24,810
Niin, että lähinnä vapauttaa puuta, kun olet tehnyt sen,

301
00:24:24,810 --> 00:24:33,790
sijasta nimenomaan kehotetaan ilmaiseksi, että olet todella vain aio käyttää toimintoa rmtree

302
00:24:33,790 --> 00:24:40,360
jossa voit kulkea osoitin, että puun ja sitten tree.c hoitaa sen puolestasi.

303
00:24:40,360 --> 00:24:42,490
>> Katsomme tree.c.

304
00:24:42,490 --> 00:24:47,240
Odotamme samat toiminnot paitsi nähdä täytäntöönpanoon samoin.

305
00:24:47,240 --> 00:24:57,720
Kuten odotimme, kun soitat mktree se mallocs koko puu osaksi osoitin,

306
00:24:57,720 --> 00:25:03,190
alustaa kaikki arvot arvon NULL, joten 0s tai nollia,

307
00:25:03,190 --> 00:25:08,280
ja palaa sitten osoitin että puu että olet juuri malloc'd sinulle.

308
00:25:08,280 --> 00:25:13,340
Täällä kun soitat poistat puu ensin varmistaa, että et ole kaksinkertaista vapauttaa.

309
00:25:13,340 --> 00:25:18,320
Se varmistaa, että sinulla todella on puu, jonka haluat poistaa.

310
00:25:18,320 --> 00:25:23,330
Täällä, koska puu sisältää myös sen lapsia,

311
00:25:23,330 --> 00:25:29,560
Mikä tämä on se rekursiivisesti kehotetaan poistamaan puu vasemmalla solmu puun

312
00:25:29,560 --> 00:25:31,650
sekä oikea solmu.

313
00:25:31,650 --> 00:25:37,790
Ennen se vapauttaa vanhempi, se tarvitsee vapauttaa myös lapset.

314
00:25:37,790 --> 00:25:42,770
Vanhempi on myös vaihdettavissa root.

315
00:25:42,770 --> 00:25:46,500
Ensimmäinen vanhempi, joten kuten iso-iso-iso-iso-isoisä

316
00:25:46,500 --> 00:25:52,130
tai isoäiti puu, ensin meidän täytyy vapauttaa alas tasolle ensin.

317
00:25:52,130 --> 00:25:58,490
Joten kulkevat pohjaan, ilmainen näitä, ja sitten tulla takaisin ylös, ilmainen näitä jne.

318
00:26:00,400 --> 00:26:02,210
Joten se puu.

319
00:26:02,210 --> 00:26:04,240
>> Nyt katsomme metsää.

320
00:26:04,240 --> 00:26:09,860
Metsä on missä laitat kaikki Huffman puita.

321
00:26:09,860 --> 00:26:12,910
On selvää, että me aiomme olla jotain kutsutaan juoni

322
00:26:12,910 --> 00:26:22,320
, joka sisältää osoittimen puuhun sekä osoittimen juonen kutsutaan seuraavaksi.

323
00:26:22,320 --> 00:26:28,480
Mitä rakenne tekee tällaista näyttää?

324
00:26:29,870 --> 00:26:32,490
Se tavallaan kertoo tuolla.

325
00:26:34,640 --> 00:26:36,700
Oikea tänne.

326
00:26:37,340 --> 00:26:39,170
Linkitetty lista.

327
00:26:39,170 --> 00:26:44,590
Näemme, että kun meillä on tontti tuntuu linkitetty lista tontteja.

328
00:26:44,590 --> 00:26:53,020
Metsä määritellään linkitetty luettelo tonttien,

329
00:26:53,020 --> 00:26:58,100
joten rakenne metsän olemme juuri menossa on osoitin ensimmäinen tontti

330
00:26:58,100 --> 00:27:02,740
ja että tontti on puu sisällä tai pikemminkin osoittaa puuhun

331
00:27:02,740 --> 00:27:06,190
ja sitten viittaa seuraavaan tontti, niin edelleen ja niin edelleen.

332
00:27:06,190 --> 00:27:11,100
Jotta metsä kutsumme mkforest.

333
00:27:11,100 --> 00:27:14,930
Sitten meillä on joitakin melko hyödyllisiä toimintoja täällä.

334
00:27:14,930 --> 00:27:23,240
Olemme poimia missä kulkea metsässä ja sitten palauttaa arvo on Tree *

335
00:27:23,240 --> 00:27:25,210
osoittimen puuhun.

336
00:27:25,210 --> 00:27:29,370
Mitä pick tekee se menee metsään että olet osoittavat

337
00:27:29,370 --> 00:27:35,240
irrota puun matalin taajuus tuosta metsästä

338
00:27:35,240 --> 00:27:38,330
ja sitten antaa sinulle osoittimen tuon puun.

339
00:27:38,330 --> 00:27:43,030
Kun soitat valita, puu ei ole metsässä enää,

340
00:27:43,030 --> 00:27:48,550
mutta paluuarvo on osoitin, että puu.

341
00:27:48,550 --> 00:27:50,730
Sitten sinulla on kasvi.

342
00:27:50,730 --> 00:27:57,420
Edellyttäen, että kulkea osoittimen puu, joka on ei-0 taajuus,

343
00:27:57,420 --> 00:28:04,040
mitä tehdas tekee se vie metsän, ottaa puu ja kasvi että puu sisällä metsän.

344
00:28:04,040 --> 00:28:06,370
Täällä meillä on rmforest.

345
00:28:06,370 --> 00:28:11,480
Samanlaisia ​​poistaa puun, joka pohjimmiltaan vapautti kaikki meidän puut meille,

346
00:28:11,480 --> 00:28:16,600
Poista metsän vapaa kaikkeen sisältyy, että metsässä.

347
00:28:16,600 --> 00:28:24,890
>> Jos katsomme forest.c, me odottaa vähintään 1 rmtree komento siellä,

348
00:28:24,890 --> 00:28:30,090
koska vapaan muistin metsässä, jos metsässä on puita siinä,

349
00:28:30,090 --> 00:28:32,930
sitten lopulta olet menossa on poistaa nämä puut liikaa.

350
00:28:32,930 --> 00:28:41,020
Jos katsomme forest.c, meillä mkforest, joka on niin odotamme.

351
00:28:41,020 --> 00:28:42,890
Me malloc asioita.

352
00:28:42,890 --> 00:28:51,740
Me alustaa ensimmäisen tontin metsästä NULL koska se on tyhjä aluksi,

353
00:28:51,740 --> 00:29:05,940
sitten näemme pick, joka palauttaa puun kanssa alin paino, alin taajuus,

354
00:29:05,940 --> 00:29:13,560
ja sitten pääsee eroon, että tietyn solmun, joka osoittaa, että puun ja seuraava,

355
00:29:13,560 --> 00:29:16,760
niin se vie että ulos linkitetty lista metsän.

356
00:29:16,760 --> 00:29:24,510
Ja sitten täällä meillä on tehdas, joka lisää puun osaksi linkitetty lista.

357
00:29:24,510 --> 00:29:29,960
Mitä metsä ei se hienosti pitää sitä lajiteltu meille.

358
00:29:29,960 --> 00:29:37,910
Ja sitten lopuksi, meillä on rmforest, ja kuten odotettua, meillä on rmtree kutsutaan siellä.

359
00:29:46,650 --> 00:29:55,440
>> Tarkasteltaessa jakelu koodin toistaiseksi huffile.c oli luultavasti ylivoimaisesti vaikein ymmärtää,

360
00:29:55,440 --> 00:29:59,990
taas muut tiedostot itse oli melko helppo seurata.

361
00:29:59,990 --> 00:30:03,090
Kanssa tietomme osoittimien ja linkitettyjen listojen ja tällainen,

362
00:30:03,090 --> 00:30:04,860
pystyimme seuraamaan melko hyvin.

363
00:30:04,860 --> 00:30:10,500
Mutta kaikki me tarvitsemme todella varmistaa, että ymmärrämme on. H tiedostot

364
00:30:10,500 --> 00:30:15,840
koska sinun täytyy soittaa kyseisiä toimintoja käsitellä sellaisia ​​paluuarvot,

365
00:30:15,840 --> 00:30:20,590
joten varmista, että olet täysin ymmärrä, mitä toimia aiotaan suorittaa

366
00:30:20,590 --> 00:30:24,290
kun soitat yhtä näistä toiminnoista.

367
00:30:24,290 --> 00:30:33,020
Mutta todellisuudessa ymmärtäminen sisältä se ei ole aivan välttämätöntä, koska meillä on nuo. H. tiedostoja.

368
00:30:35,170 --> 00:30:39,490
Meillä on 2 lisää tiedostoja jäljellä meidän jakelussa koodin.

369
00:30:39,490 --> 00:30:41,640
>> Katsotaanpa kaatopaikalle.

370
00:30:41,640 --> 00:30:47,230
Dump sen kommentin tähän vie Huffman-pakattu tiedosto

371
00:30:47,230 --> 00:30:55,580
ja sitten kääntää ja tyhjentää kaikki sen sisältö ulos.

372
00:31:01,010 --> 00:31:04,260
Tässä näemme, että se soittaa hfopen.

373
00:31:04,260 --> 00:31:10,770
Tämä on tavallaan peilaus tiedostoon * input = fopen,

374
00:31:10,770 --> 00:31:13,500
ja sitten ohitat tiedoissa.

375
00:31:13,500 --> 00:31:18,240
Se on melkein identtinen paitsi sijasta tiedoston * olet ohimennen Huffile;

376
00:31:18,240 --> 00:31:22,030
sijaan fopen olet ohimennen hfopen.

377
00:31:22,030 --> 00:31:29,280
Täällä luemme otsikon ensimmäinen, joka on tavallaan samanlainen miten luemme otsikon

378
00:31:29,280 --> 00:31:33,580
varten bittikarttatiedosto.

379
00:31:33,580 --> 00:31:38,000
Mitä me teemme täällä on tarkistaa, onko otsikkotiedot

380
00:31:38,000 --> 00:31:44,330
sisältää oikea maaginen numero, joka ilmaisee, että se on todellinen Huff tiedoston,

381
00:31:44,330 --> 00:31:53,610
Sitten kaikki nämä tarkastukset varmista, että tiedosto avaamme on todellinen puuskahti tiedostoa tai ei.

382
00:31:53,610 --> 00:32:05,330
Mikä tämä on se tuottaa taajuudet kaikilla symboleilla, että voimme nähdä

383
00:32:05,330 --> 00:32:09,790
sisällä päätelaitteelle graafinen taulukkoon.

384
00:32:09,790 --> 00:32:15,240
Tämä osa tulee olemaan hyödyllinen.

385
00:32:15,240 --> 00:32:24,680
Se on vähän ja lukee vähän kerrallaan muuttujaan vähän ja sitten tulostaa sen.

386
00:32:28,220 --> 00:32:35,430
Joten jos olisin soittaa polkumyyntiin hth.bin, mikä on seurausta huffing tiedoston

387
00:32:35,430 --> 00:32:39,490
avulla henkilöstö ratkaisu, haluan saada tämän.

388
00:32:39,490 --> 00:32:46,000
Se syöttöä kaikki nämä merkit ja sitten asettaa taajuuden, jossa ne esiintyvät.

389
00:32:46,000 --> 00:32:51,180
Jos katsomme, useimmat niistä ovat 0s, lukuun ottamatta tätä: H, joka esiintyy kahdesti,

390
00:32:51,180 --> 00:32:54,820
ja sitten T, joka esiintyy kerran.

391
00:32:54,820 --> 00:33:07,860
Ja sitten täällä on todellinen viesti 0s ja 1s.

392
00:33:07,860 --> 00:33:15,450
Jos tarkastelemme hth.txt, joka on oletettavasti alkuperäisen viestin, joka oli huffed,

393
00:33:15,450 --> 00:33:22,490
odotamme joitakin Hs ja Ts siellä.

394
00:33:22,490 --> 00:33:28,720
Erityisesti odotamme vain 1 T ja 2 Hs.

395
00:33:32,510 --> 00:33:37,440
Täällä olemme hth.txt. Se todellakin on HTH.

396
00:33:37,440 --> 00:33:41,270
Mukana siellä, vaikka emme voi nähdä sitä, on rivinvaihtomerkki.

397
00:33:41,270 --> 00:33:53,190
Huff tiedosto hth.bin myös koodaa rivinvaihtomerkki samoin.

398
00:33:55,680 --> 00:34:01,330
Täällä sillä me tiedämme, että järjestys on HTH ja sitten rivinvaihto,

399
00:34:01,330 --> 00:34:07,340
voimme nähdä, että luultavasti H edustaa vain yhden 1

400
00:34:07,340 --> 00:34:17,120
ja sitten T on todennäköisesti 01 ja sen jälkeen seuraava H on 1 samoin

401
00:34:17,120 --> 00:34:21,139
ja sitten meillä on rivinvaihto merkitään kahdella 0s.

402
00:34:22,420 --> 00:34:24,280
Cool.

403
00:34:26,530 --> 00:34:31,600
>> Ja sitten lopuksi, koska olemme tekemisissä useita. C ja. H tiedostoja,

404
00:34:31,600 --> 00:34:36,350
aiomme olla melko monimutkainen argumentti kääntäjä,

405
00:34:36,350 --> 00:34:40,460
joten tässä meillä on Makefile joka tekee dump teitä.

406
00:34:40,460 --> 00:34:47,070
Mutta todella, sinun täytyy mennä noin tehdä omia puff.c tiedosto.

407
00:34:47,070 --> 00:34:54,330
Makefile oikeastaan ​​ei käsitellä tehdä puff.c sinulle.

408
00:34:54,330 --> 00:34:59,310
Lähdemme siitä, että jopa voit muokata Makefile.

409
00:34:59,310 --> 00:35:05,930
Kun kirjoitat komennon kuten tekevät kaikki, se esimerkiksi tekee kaikki ne sinulle.

410
00:35:05,930 --> 00:35:10,760
Voit vapaasti katsoa esimerkkejä Makefile menneisyydestä PSET

411
00:35:10,760 --> 00:35:17,400
sekä menossa pois tämä kuinka saatat pystyä tekemään Puff tiedosto

412
00:35:17,400 --> 00:35:20,260
muokkaamalla tätä Makefile.

413
00:35:20,260 --> 00:35:22,730
Se siitä meidän jakelua koodia.

414
00:35:22,730 --> 00:35:28,380
>> Kun olemme saaneet läpi, niin tässä on vain toinen muistutus

415
00:35:28,380 --> 00:35:30,980
miten aiomme olla tekemisissä Huffman solmut.

416
00:35:30,980 --> 00:35:35,400
Emme aio olla kutsuen heitä solmuja enää, aiomme olla kutsumassa niitä puita

417
00:35:35,400 --> 00:35:39,260
minne olemme menossa edustamaan heidän symboli char,

418
00:35:39,260 --> 00:35:43,340
niiden taajuuden, tapahtumien määrä, jossa kokonaisluku.

419
00:35:43,340 --> 00:35:47,370
Käytämme että koska se on tarkempi kuin float.

420
00:35:47,370 --> 00:35:52,980
Ja sitten meillä on toinen osoitin vasemmalle lasta sekä oikea lapsi.

421
00:35:52,980 --> 00:35:59,630
Metsä, kuten näimme, on vain linkitetyn listan puita.

422
00:35:59,630 --> 00:36:04,670
Lopulta, kun olemme rakentamassa meidän Huff tiedosto,

423
00:36:04,670 --> 00:36:07,580
haluamme metsä sisältää vain 1 puu -

424
00:36:07,580 --> 00:36:12,420
1 puu, 1 root useita lapsia.

425
00:36:12,420 --> 00:36:20,840
Aiemmin kun olimme juuri tehdessämme Huffman puita,

426
00:36:20,840 --> 00:36:25,360
aloitimme asettamalla kaikki solmut päälle meidän näytöllä

427
00:36:25,360 --> 00:36:27,790
ja sanoi aiomme olla näitä solmuja,

428
00:36:27,790 --> 00:36:32,920
Lopulta he olemaan lehdet, ja tämä on heidän symboli, tämä on heidän taajuus.

429
00:36:32,920 --> 00:36:42,070
Meidän metsä jos meillä vain on 3 kirjainta, joka on metsän 3 puita.

430
00:36:42,070 --> 00:36:45,150
Ja sitten me mennä, kun lisäsimme ensimmäinen vanhempi,

431
00:36:45,150 --> 00:36:48,080
teimme metsässä 2 puuta.

432
00:36:48,080 --> 00:36:54,930
Poistimme 2 näistä lapsista meidän metsästä ja sitten korvannut sen vanhemman solmun

433
00:36:54,930 --> 00:36:58,820
että oli nuo 2 solmua lapsina.

434
00:36:58,820 --> 00:37:05,600
Ja sitten lopuksi, meidän viimeinen askel kanssa tekemällä esimerkiksi As, Bs ja Cs

435
00:37:05,600 --> 00:37:08,030
olisi tehdä lopullinen emoyhtiö,

436
00:37:08,030 --> 00:37:13,190
ja niin sitten se toisi meidän yhteen laskettu metsän puiden 1.

437
00:37:13,190 --> 00:37:18,140
Onko jokainen miten aloitat useita puita omassa metsässä

438
00:37:18,140 --> 00:37:22,520
ja lopulta 1? Okei. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Mitä meidän täytyy tehdä Puff?

440
00:37:28,110 --> 00:37:37,110
Meidän tarvitsee vain varmistaa, että aina, ne antavat meille oikean tyyppinen tulo

441
00:37:37,110 --> 00:37:39,090
jotta voimme ajaa ohjelman.

442
00:37:39,090 --> 00:37:43,130
Tässä tapauksessa he aikovat olla antaa meille jälkeen ensimmäinen komentoriviargumentin

443
00:37:43,130 --> 00:37:53,440
2 lisää: tiedosto, haluamme purkaa ja lähtö puretun tiedoston.

444
00:37:53,440 --> 00:38:00,410
Mutta kun me varmista, että ne kulkevat meille oikean määrän arvoja,

445
00:38:00,410 --> 00:38:05,820
Haluamme varmistaa, että tulo on Huff tiedosto tai ei.

446
00:38:05,820 --> 00:38:10,420
Ja sitten kun me takaamme, että se on Huff tiedosto, niin me haluamme rakentaa puu,

447
00:38:10,420 --> 00:38:20,940
rakentaa puu siten, että se vastaa puun että henkilö lähetti viestin rakennettu.

448
00:38:20,940 --> 00:38:25,840
Sitten kun me rakennamme puu, niin voimme käsitellä 0s ja 1s että ne hyväksyttiin,

449
00:38:25,840 --> 00:38:29,590
noudata niitä pitkin meidän puu, koska se on sama,

450
00:38:29,590 --> 00:38:33,510
ja sitten kirjoittaa, että viestisi, tulkita bitit takaisin merkkiä.

451
00:38:33,510 --> 00:38:35,880
Ja sitten lopussa, koska olemme tekemisissä osoittimet täällä,

452
00:38:35,880 --> 00:38:38,110
Haluamme varmistaa, että meillä ei ole mitään muistivuotoja

453
00:38:38,110 --> 00:38:41,330
ja että me vapaa kaikesta.

454
00:38:42,820 --> 00:38:46,430
>> Varmistamalla asianmukainen käyttö on vanha hattu meille nyt.

455
00:38:46,430 --> 00:38:51,980
Otamme in tulo, joka tulee olemaan tiedoston nimi puff,

456
00:38:51,980 --> 00:38:56,010
ja sitten me määritä lähtö,

457
00:38:56,010 --> 00:39:01,580
joten tiedoston nimi varten turvotettua tuotos, joka on tekstitiedosto.

458
00:39:03,680 --> 00:39:08,820
Se käyttöä. Ja nyt me haluamme varmistaa, että tuloa puuskahti vai ei.

459
00:39:08,820 --> 00:39:16,420
Thinking takaisin, oli siellä mitään jakelu koodin, jotka voivat auttaa meitä

460
00:39:16,420 --> 00:39:21,570
ymmärtämisestä onko tiedosto puuskahti vai ei?

461
00:39:21,570 --> 00:39:26,910
Oli tietoja huffile.c tietoa Huffeader.

462
00:39:26,910 --> 00:39:33,430
Tiedämme, että jokainen Huff tiedosto on Huffeader liittyy se maaginen numero

463
00:39:33,430 --> 00:39:37,240
samoin kuin erilaisia ​​taajuuksia kunkin symbolin

464
00:39:37,240 --> 00:39:39,570
sekä tarkistussumma.

465
00:39:39,570 --> 00:39:43,180
Tiedämme sen, mutta otimme myös kurkistaa dump.c,

466
00:39:43,180 --> 00:39:49,120
jossa se luki osaksi Huff tiedostoon.

467
00:39:49,120 --> 00:39:53,990
Ja niin tehdä, että se oli tarkistaa, onko se todella ollut puuskahti vai ei.

468
00:39:53,990 --> 00:40:03,380
Joten ehkä voisimme käyttää dump.c kuin rakenne meidän puff.c.

469
00:40:03,380 --> 00:40:12,680
Takaisin PSET 4, kun meillä oli tiedosto copy.c että kopioitu RGB kolminkertaistuu

470
00:40:12,680 --> 00:40:14,860
ja me tulkitaan että jännäri ja kokoa,

471
00:40:14,860 --> 00:40:20,390
Vastaavasti mitä voisit tehdä, on vain ajaa komentoa cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
ja käyttää joitakin koodin sinne.

473
00:40:23,600 --> 00:40:28,210
Kuitenkin, se ei tule olemaan yhtä mutkatonta ja prosessin

474
00:40:28,210 --> 00:40:33,010
kääntämiseen teidän dump.c osaksi puff.c,

475
00:40:33,010 --> 00:40:36,160
mutta ainakin se antaa sinulle jonnekin aloittaa

476
00:40:36,160 --> 00:40:40,540
siitä, kuinka varmistetaan, että tulo on todellisuudessa huffed tai ei

477
00:40:40,540 --> 00:40:43,240
sekä muutamia muita asioita.

478
00:40:45,930 --> 00:40:50,250
Olemme varmistaneet asianmukainen käyttö ja varmistettava, että tulo puuskahti.

479
00:40:50,250 --> 00:40:53,570
Joka kerta, kun olemme tehneet, että olemme tehneet oikean virheentarkistukset,

480
00:40:53,570 --> 00:41:01,520
niin palaamassa ja lopetus toiminto jos jokin vika, jos on ongelmia.

481
00:41:01,520 --> 00:41:07,170
>> Nyt me haluamme tehdä, on rakentaa todellista puu.

482
00:41:08,840 --> 00:41:12,640
Jos katsomme Forest, on 2 tärkeimmät toiminnot

483
00:41:12,640 --> 00:41:15,800
että olemme menossa halua tulla hyvin tuttu.

484
00:41:15,800 --> 00:41:23,870
On Boolen funktio kasvi, kasvit kuin 0 taajuus puu sisällä meidän metsä.

485
00:41:23,870 --> 00:41:29,250
Ja niin siinä ohitat vuonna osoittimen metsä ja osoitin puun.

486
00:41:32,530 --> 00:41:40,340
Nopea kysymys: Kuinka monta metsien olet kun olet rakentamassa Huffman puu?

487
00:41:44,210 --> 00:41:46,650
Meidän metsä on kuin meidän kankaalle, eikö?

488
00:41:46,650 --> 00:41:50,800
Joten me vain olemaan 1 metsää, mutta me aiomme olla useita puita.

489
00:41:50,800 --> 00:41:57,590
Joten ennen kuin soitat kasvi, olet luultavasti menossa haluavat tehdä metsään.

490
00:41:57,590 --> 00:42:04,430
On komento, että jos näytät forest.h miten voit tehdä metsän.

491
00:42:04,430 --> 00:42:09,270
Voit istuttaa puun. Tiedämme, miten tehdä se.

492
00:42:09,270 --> 00:42:11,590
Ja sitten voit myös valita puu metsä

493
00:42:11,590 --> 00:42:17,540
poistamalla puun alin paino ja antaa sinulle osoittimen siihen.

494
00:42:17,540 --> 00:42:23,090
Thinking takaisin kun olimme tekemässä esimerkit itseämme,

495
00:42:23,090 --> 00:42:27,980
kun olimme vetämällä sitä ulos, me yksinkertaisesti vain lisätä linkkejä.

496
00:42:27,980 --> 00:42:31,680
Mutta täällä sen sijaan vain lisäämällä yhteyksiä,

497
00:42:31,680 --> 00:42:40,630
ajattele sitä enemmän olet poistamalla 2 näitä solmuja ja sitten korvaa sen toiseen.

498
00:42:40,630 --> 00:42:44,200
Ilmaista, että suhteen poiminta ja istutus,

499
00:42:44,200 --> 00:42:48,840
olet poiminta 2 puut ja sitten istutus toiseen puuhun

500
00:42:48,840 --> 00:42:54,060
että on nuo 2 puita että olet valinnut lapsina.

501
00:42:57,950 --> 00:43:05,280
Rakentaa Huffman puiden, voit lukea symboleja ja taajuudet järjestyksessä

502
00:43:05,280 --> 00:43:10,790
koska Huffeader antaa sen sinulle,

503
00:43:10,790 --> 00:43:14,250
antaa erilaisia ​​taajuuksia.

504
00:43:14,250 --> 00:43:19,660
Joten voit mennä eteenpäin ja vain sivuuttaa mitään 0 siinä

505
00:43:19,660 --> 00:43:23,760
koska emme halua 256 lähtee lopussa se.

506
00:43:23,760 --> 00:43:27,960
Haluamme vain lehtien lukumäärä, jotka ovat merkkejä

507
00:43:27,960 --> 00:43:31,600
joita tosiasiallisesti käytetään tiedostoon.

508
00:43:31,600 --> 00:43:37,590
Voi lukea ne symbolit, ja kukin näistä symboleja, jotka ovat ei-0 taajuuksia,

509
00:43:37,590 --> 00:43:40,440
ne tulevat olemaan puita.

510
00:43:40,440 --> 00:43:45,990
Mitä voit tehdä, on aina lukea kuin 0 taajuuden symbolin,

511
00:43:45,990 --> 00:43:50,660
voit istuttaa että puu metsässä.

512
00:43:50,660 --> 00:43:56,620
Kun istuttaa puita metsässä, voit liittyä nuo puut sisarukset,

513
00:43:56,620 --> 00:44:01,130
niin menee takaisin istutus ja poiminta, jossa voit valita 2 ja sitten kasvi 1,

514
00:44:01,130 --> 00:44:05,820
jos se 1 että kasvi on vanhempi 2 lasta, että olet valinnut.

515
00:44:05,820 --> 00:44:11,160
Joten sitten sinun lopputulos tulee olemaan yksi puu omassa metsässä.

516
00:44:16,180 --> 00:44:18,170
Näin voit rakentaa puu.

517
00:44:18,170 --> 00:44:21,850
>> On useita asioita, jotka voivat mennä pieleen

518
00:44:21,850 --> 00:44:26,580
koska olemme tekemisissä tehdä uusia puita ja käsitellä osoittimet ja tuollaista.

519
00:44:26,580 --> 00:44:30,450
Ennen kun olimme tekemisissä osoittimia,

520
00:44:30,450 --> 00:44:36,580
kun me malloc'd halusimme varmistaa, että se ei palauta meille NULL osoittimen arvo.

521
00:44:36,580 --> 00:44:42,770
Joten useita vaiheita tässä prosessissa on menossa olla useita tapauksia

522
00:44:42,770 --> 00:44:45,920
missä ohjelma voisi epäonnistua.

523
00:44:45,920 --> 00:44:51,310
Mitä haluat tehdä on haluat varmistaa, että voit hoitaa nämä virheet,

524
00:44:51,310 --> 00:44:54,580
ja spec sanotaan käsitellä niitä sulavasti,

525
00:44:54,580 --> 00:45:00,280
joten haluaisin tulostaa viestin käyttäjälle heille, miksi ohjelma on lopettaa

526
00:45:00,280 --> 00:45:03,050
ja sitten heti lopettaa se.

527
00:45:03,050 --> 00:45:09,490
Voit tehdä tämän virheenkäsittely, muista, että haluat tarkistaa

528
00:45:09,490 --> 00:45:12,160
joka ikinen kerta, että siellä voisi olla vika.

529
00:45:12,160 --> 00:45:14,660
Joka ikinen kerta, että teet uuden osoittimen

530
00:45:14,660 --> 00:45:17,040
haluat varmistaa, että se on onnistunut.

531
00:45:17,040 --> 00:45:20,320
Ennen mitä käytimme vain tehdä uuden osoittimen ja malloc sitä,

532
00:45:20,320 --> 00:45:22,380
ja sitten voisimme tarkistaa, onko kyseinen osoitin on NULL.

533
00:45:22,380 --> 00:45:25,670
Joten ei aiotaan joitakin tapauksia, joissa voit vain tehdä se,

534
00:45:25,670 --> 00:45:28,610
mutta joskus olet todella kutsuvan funktion

535
00:45:28,610 --> 00:45:33,100
ja kyseisessä toiminto, se joka tekee mallocing.

536
00:45:33,100 --> 00:45:39,110
Siinä tapauksessa, jos katsomme taaksepäin joidenkin toimintojen koodin,

537
00:45:39,110 --> 00:45:42,260
jotkut niistä ovat Boolen toimintoja.

538
00:45:42,260 --> 00:45:48,480
Vuonna abstrakti jos meillä Boolen funktio nimeltä foo-

539
00:45:48,480 --> 00:45:54,580
pohjimmiltaan, voimme olettaa, että sen lisäksi tekee mitä foo tekee,

540
00:45:54,580 --> 00:45:57,210
koska se on Boolen funktio, se palauttaa true tai false -

541
00:45:57,210 --> 00:46:01,300
true jos onnistuu, false jos ei.

542
00:46:01,300 --> 00:46:06,270
Niinpä haluamme onko palauttaa arvon foo on tosi tai epätosi.

543
00:46:06,270 --> 00:46:10,400
Jos se on väärä, se tarkoittaa, että olemme menossa halua tulostaa jonkinlaisen viestin

544
00:46:10,400 --> 00:46:14,390
ja sulje ohjelma.

545
00:46:14,390 --> 00:46:18,530
Mitä me haluamme tehdä, on tarkistaa paluuarvon foo.

546
00:46:18,530 --> 00:46:23,310
Jos foo palauttaa false, niin tiedämme, että meillä on ollut jonkinlainen virhe

547
00:46:23,310 --> 00:46:25,110
ja meidän täytyy lopettaa ohjelmaamme.

548
00:46:25,110 --> 00:46:35,600
Tapa tehdä tämä on saada tila, jossa varsinainen toiminta itsessään on kunnossa.

549
00:46:35,600 --> 00:46:39,320
Sano foo vie x.

550
00:46:39,320 --> 00:46:43,390
Voimme olla ehtona if (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Pohjimmiltaan, se tarkoittaa, että jos lopussa täytäntöönpanovaltion foo se palauttaa totta,

552
00:46:50,900 --> 00:46:57,390
voimme tehdä tämän, koska toiminto on arvioitava foo

553
00:46:57,390 --> 00:47:00,500
jotta voidaan arvioida koko tila.

554
00:47:00,500 --> 00:47:06,500
Joten sitten se, miten voit tehdä jotain, jos funktio palauttaa true ja onnistuu.

555
00:47:06,500 --> 00:47:11,800
Mutta kun olet virheentarkistukset, haluat vain lopettaa jos funktio palauttaa false.

556
00:47:11,800 --> 00:47:16,090
Mitä voisit tehdä, on vain lisätä == false tai vain lisätä bang edessä on

557
00:47:16,090 --> 00:47:21,010
ja sitten on jos (! foo).

558
00:47:21,010 --> 00:47:29,540
Kyseisen laitoksen kyseisen edellytyksen sinulla olisi kaikki virheiden käsittelyä,

559
00:47:29,540 --> 00:47:36,940
joten kuten, "ei voitu luoda tätä puuta" ja palaa sitten 1 tai jotain.

560
00:47:36,940 --> 00:47:43,340
Mitä se tekee kuitenkin se, että vaikka foo palautetaan false -

561
00:47:43,340 --> 00:47:46,980
Sano foo palauttaa true.

562
00:47:46,980 --> 00:47:51,060
Silloin sinun ei tarvitse soittaa foo uudelleen. Tuo yleinen väärinkäsitys.

563
00:47:51,060 --> 00:47:54,730
Koska se oli vointisi, se on jo arvioinut,

564
00:47:54,730 --> 00:47:59,430
joten sinulla on jo tulos jos käytät tehdä puusta tai jotain

565
00:47:59,430 --> 00:48:01,840
tai kasvin tai poimia tai jotain.

566
00:48:01,840 --> 00:48:07,460
Se on jo kyseisen arvon. Se on jo toteutettu.

567
00:48:07,460 --> 00:48:10,730
Joten se on hyödyllistä käyttää Boolen toimii kunnossa

568
00:48:10,730 --> 00:48:13,890
koska vai et itse suorittaa elin silmukan,

569
00:48:13,890 --> 00:48:18,030
se suorittaa toiminnon muutenkin.

570
00:48:22,070 --> 00:48:27,330
>> Meidän toiseksi viimeinen vaihe on kirjallisesti viestin tiedoston.

571
00:48:27,330 --> 00:48:33,070
Kun me rakennamme Huffman puu, sitten kirjallisesti viesti tiedosto on melko yksinkertainen.

572
00:48:33,070 --> 00:48:39,260
Se on melko yksinkertainen nyt vain seurata 0s ja 1s.

573
00:48:39,260 --> 00:48:45,480
Ja näin yleissopimuksessa tiedämme, että Huffman puu 0s osoittavat vasemmalle

574
00:48:45,480 --> 00:48:48,360
ja 1s osoittavat oikealle.

575
00:48:48,360 --> 00:48:53,540
Joten jos olet lukenut vähän kerrallaan, aina kun saat 0

576
00:48:53,540 --> 00:48:59,100
voit seurata vasen haara, ja sitten aina lukea 1

577
00:48:59,100 --> 00:49:02,100
aiot seurata oikeaan haaraan.

578
00:49:02,100 --> 00:49:07,570
Ja sitten olet menossa jatkamaan kunnes osut lehtiä

579
00:49:07,570 --> 00:49:11,550
koska lehdet tulevat olemaan lopussa oksat.

580
00:49:11,550 --> 00:49:16,870
Miten voimme tietää, onko meillä osuma lehtiä vai ei?

581
00:49:19,800 --> 00:49:21,690
Sanoimme ennen.

582
00:49:21,690 --> 00:49:24,040
[Opiskelija] Jos osoittimet ovat NULL. >> Joo.

583
00:49:24,040 --> 00:49:32,220
Voimme kertoa, jos olemme osuma lehtiä, jos osoittimia sekä vasen ja oikea puut ovat NULL.

584
00:49:32,220 --> 00:49:34,110
Perfect.

585
00:49:34,110 --> 00:49:40,320
Me tiedämme, että haluamme lukea vähän kerrallaan meidän Huff tiedostoon.

586
00:49:43,870 --> 00:49:51,220
Kuten näimme aiemmin dump.c, mitä he tekivät on ne luetaan vähän kerrallaan osaksi Huff tiedosto

587
00:49:51,220 --> 00:49:54,560
ja vain tulostaa mitä nämä bitit olivat.

588
00:49:54,560 --> 00:49:58,430
Emme aio tehdä sitä. Aiomme tehdä jotain, joka on hieman monimutkaisempi.

589
00:49:58,430 --> 00:50:03,620
Mutta mitä voimme tehdä on, voimme ottaa sen vähän koodia, joka lukee sisään bitti.

590
00:50:03,620 --> 00:50:10,250
Täällä meillä on kokonaisluku bitti edustaa nykyistä hieman, että olemme.

591
00:50:10,250 --> 00:50:15,520
Tämä huolehtii iteroimalla kaikki bitit tiedostoon, kunnes osut tiedoston loppuun.

592
00:50:15,520 --> 00:50:21,270
Perustuu että sitten olet menossa halua olla jonkinlainen iteraattori

593
00:50:21,270 --> 00:50:26,760
kulkemaan teidän puu.

594
00:50:26,760 --> 00:50:31,460
Ja sitten sen perusteella, onko kyseinen bitti on 0 tai 1,

595
00:50:31,460 --> 00:50:36,920
olet menossa haluavat joko siirtää että iteraattori vasemmalle tai siirrä se oikealle

596
00:50:36,920 --> 00:50:44,080
aina kunnes osut lehtiä, niin aina kunnes solmu että olet

597
00:50:44,080 --> 00:50:48,260
ei viitata enää solmuja.

598
00:50:48,260 --> 00:50:54,300
Miksi teemme tätä Huffman tiedoston, mutta ei morseaakkoset?

599
00:50:54,300 --> 00:50:56,610
Koska morseaakkoset siellä hieman epäselvyyttä.

600
00:50:56,610 --> 00:51:04,440
Voisimme olla kuin, Voi odottaa, olemme osuma kirjeen matkan varrella, joten ehkä tämä on meidän kirjeen,

601
00:51:04,440 --> 00:51:08,150
katsoo, että jos jatkamme vain vähän kauemmin, niin olisimme osuma toisen kirjeen.

602
00:51:08,150 --> 00:51:13,110
Mutta se ei tule tapahtumaan Huffman koodausta,

603
00:51:13,110 --> 00:51:17,540
jotta voimme olla varmoja, että ainoa tapa, jolla aiomme osuma merkki

604
00:51:17,540 --> 00:51:23,480
On jos solmun vasen ja oikea lapset ovat NULL.

605
00:51:28,280 --> 00:51:32,350
>> Lopuksi haluamme vapauttaa meidän kaikkien muistissa.

606
00:51:32,350 --> 00:51:37,420
Haluamme molemmat lähellä Huff tiedosto olemme tekemisissä

607
00:51:37,420 --> 00:51:41,940
sekä poistaa kaikki puut meidän metsässä.

608
00:51:41,940 --> 00:51:46,470
Perustuu omaan toteuttamisesta, olet todennäköisesti menossa halua soittaa poistaa metsä

609
00:51:46,470 --> 00:51:49,780
sijaan todella menee läpi kaikki puut itse.

610
00:51:49,780 --> 00:51:53,430
Mutta jos olet tehnyt mitään väliaikaista puita, sinun kannattaa vapauttaa se.

611
00:51:53,430 --> 00:51:59,060
Tiedät koodin parasta, niin tiedät minne olet jaettaessa muistia.

612
00:51:59,060 --> 00:52:04,330
Ja niin jos menet, aloita vaikka ohjaus F'ing varten malloc,

613
00:52:04,330 --> 00:52:08,330
nähdä aina malloc ja varmista, että sinulla vapauttaa kaikki, jotka

614
00:52:08,330 --> 00:52:10,190
mutta sitten vain menee läpi koodin,

615
00:52:10,190 --> 00:52:14,260
ymmärtää missä olet ehkä jaettu muisti.

616
00:52:14,260 --> 00:52:21,340
Yleensä voit vain sanoa, "Lopussa tiedoston Aion poistaa metsä minun metsä"

617
00:52:21,340 --> 00:52:23,850
joten periaatteessa selvää, että muistin, vapaa, että

618
00:52:23,850 --> 00:52:28,310
"Ja sitten olen myös menossa sulkea tiedoston ja sitten minun ohjelma tulee lopettaa."

619
00:52:28,310 --> 00:52:33,810
Mutta onko se ainoa kerta, että ohjelma sulkeutuu?

620
00:52:33,810 --> 00:52:37,880
Ei, koska joskus saattaa olla virhe tapahtui.

621
00:52:37,880 --> 00:52:42,080
Ehkä emme voi avata tiedostoa tai emme voineet tehdä toinen puu

622
00:52:42,080 --> 00:52:49,340
tai jonkinlainen virhe tapahtui muistinvaraustila prosessia ja niin se palasi NULL.

623
00:52:49,340 --> 00:52:56,710
Virhe tapahtui, ja sitten palasimme ja lopeta.

624
00:52:56,710 --> 00:53:02,040
Joten sitten haluat varmistaa, että mahdolliset aika että ohjelma voidaan lopettaa,

625
00:53:02,040 --> 00:53:06,980
haluat vapauttaa kaikki muisti siellä.

626
00:53:06,980 --> 00:53:13,370
Se ei vain olemaan aivan lopussa päätehtävä että lopetat koodi.

627
00:53:13,370 --> 00:53:20,780
Haluat katsoa takaisin joka kerta, että koodin mahdollisesti voisi palata ennenaikaisesti

628
00:53:20,780 --> 00:53:25,070
ja sitten vapaa mitä muistia järkeä.

629
00:53:25,070 --> 00:53:30,830
Sano oli soittanut tehdä metsän ja palasi vääriä.

630
00:53:30,830 --> 00:53:34,230
Sitten luultavasti ei tarvitse poistaa metsä

631
00:53:34,230 --> 00:53:37,080
koska sinulla ei ole metsää vielä.

632
00:53:37,080 --> 00:53:42,130
Mutta kaikissa pisteissä koodi, jos saatat palata ennenaikaisesti

633
00:53:42,130 --> 00:53:46,160
haluat varmistaa, että voit vapauttaa mahdolliset muistia.

634
00:53:46,160 --> 00:53:50,020
>> Joten kun olemme tekemisissä vapauttaa muistia ja ottaa mahdolliset vuodot,

635
00:53:50,020 --> 00:53:55,440
Haluamme paitsi käyttää harkintaa ja meidän logiikka

636
00:53:55,440 --> 00:54:01,850
mutta myös käyttää Valgrind onko olemme vapautti kaikki meidän muistia oikein vai ei.

637
00:54:01,850 --> 00:54:09,460
Voit joko ajaa Valgrind päälle Puff ja sitten on myös sitä tule

638
00:54:09,460 --> 00:54:14,020
oikea määrä komentorivin argumentteja Valgrind.

639
00:54:14,020 --> 00:54:18,100
Voit juosta, mutta lähtö on vähän arvoituksellinen.

640
00:54:18,100 --> 00:54:21,630
Olemme saaneet hieman käyttää sitä oikeinkirjoituksen, mutta tarvitsemme vielä hieman enemmän apua,

641
00:54:21,630 --> 00:54:26,450
niin sitten käynnissä sitä muutaman lippuja kuin vuoto-check = täynnä,

642
00:54:26,450 --> 00:54:32,040
Todennäköisesti saamme hieman lisää hyödyllisiä lähtö Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Sitten toinen vihje kun olet virheenkorjaus on diff komennon.

644
00:54:39,040 --> 00:54:48,520
Voit käyttää henkilöstön täytäntöönpanon Huff, ajaa että tekstitiedosto,

645
00:54:48,520 --> 00:54:55,400
ja sitten tulostaa sen binaaritiedosto, binary Huff tiedoston, erityiseksi.

646
00:54:55,400 --> 00:54:59,440
Sitten jos voit suorittaa oman henkosesta että binaaritiedosto,

647
00:54:59,440 --> 00:55:03,950
Sitten ihannetapauksessa nimellä lähtönä tekstitiedosto tulee olemaan identtisiä

648
00:55:03,950 --> 00:55:08,200
kuin alkuperäinen että olet läpäissyt sisään

649
00:55:08,200 --> 00:55:15,150
Tässä olen käyttäen hth.txt kuten esimerkiksi ja se on yksi puhutuimmista teidän spec.

650
00:55:15,150 --> 00:55:21,040
Se on kirjaimellisesti vain HTH ja rivinvaihto.

651
00:55:21,040 --> 00:55:30,970
Mutta ehdottomasti rohkeasti ja olet varmasti kannustetaan käyttämään pidempään esimerkkejä

652
00:55:30,970 --> 00:55:32,620
oman tekstitiedosto.

653
00:55:32,620 --> 00:55:38,110
>> Voit jopa ottaa ampui ehkä puristamalla ja purkamiseen

654
00:55:38,110 --> 00:55:41,600
joitakin tiedostoja käytit Speller kuten Sota ja rauha

655
00:55:41,600 --> 00:55:46,710
tai Jane Austen tai jotain - se olisi eräänlainen cool - tai Austin Powers,

656
00:55:46,710 --> 00:55:51,880
Tällainen käsitellä suurempia tiedostoja, koska meidän ei tule alas se

657
00:55:51,880 --> 00:55:55,590
jos käytämme seuraava työkalu tässä, ls-l.

658
00:55:55,590 --> 00:56:01,150
Olemme tottuneet ls, joka pohjimmiltaan luetellaan kaikki sisältö meidän hakemistossa.

659
00:56:01,150 --> 00:56:07,860
Syöttäminen on lippu-l todella näyttää kokoon nämä tiedostot.

660
00:56:07,860 --> 00:56:12,690
Jos menet läpi PSET spec, se todella opastaa luomaan binaaritiedosto

661
00:56:12,690 --> 00:56:16,590
ja huffing sitä, ja näet, että hyvin pieniä tiedostoja

662
00:56:16,590 --> 00:56:23,910
tilan kustannukset puristamalla sitä ja kääntää kaikki nämä tiedot

663
00:56:23,910 --> 00:56:26,980
kaikki taajuudet ja tuollaista suurempi todellinen hyöty

664
00:56:26,980 --> 00:56:30,000
pakata tiedoston ensimmäinen paikka.

665
00:56:30,000 --> 00:56:37,450
Mutta jos käytät sitä jonkin enää tekstitiedostoja, niin saatat nähdä, että aloitat saada jonkinlaista hyötyä

666
00:56:37,450 --> 00:56:40,930
vuonna puristamalla kyseiset tiedostot.

667
00:56:40,930 --> 00:56:46,210
>> Ja sitten lopuksi, meillä on vanha kamu GDB, joka on ehdottomasti menossa ovat käteviä myös.

668
00:56:48,360 --> 00:56:55,320
>> Onko meillä mitään kysymyksiä Huff puita tai prosessin ehkä tehdä puut

669
00:56:55,320 --> 00:56:58,590
tai muita kysymyksiä Huff'n Puff?

670
00:57:00,680 --> 00:57:02,570
Okei. Viivyn ympäriinsä hieman.

671
00:57:02,570 --> 00:57:06,570
>> Kiitos kaikille. Tämä oli läpikäynti 6. Ja onnea.

672
00:57:08,660 --> 00:57:10,000
>> [CS50.TV]