1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Walk Through - Probleem Set 6]

2
00:00:02,210 --> 00:00:04,810
[Zamyla Chan - Harvard Universiteit]

3
00:00:04,810 --> 00:00:07,240
[Hierdie is CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Hallo, almal, en welkom om Walk Through 6: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
In Huff'n Puff wat ons doen gaan word wat handel met 'n Huffman saamgeperste lêer

6
00:00:17,440 --> 00:00:20,740
en dan gepruttel dit terug, so decompressie,

7
00:00:20,740 --> 00:00:25,810
sodat ons kan vertaal uit die 0'e en 1s dat die gebruiker stuur ons

8
00:00:25,810 --> 00:00:30,660
en sit dit terug in die oorspronklike teks.

9
00:00:30,660 --> 00:00:34,360
Pset 6 gaan wees pretty cool want jy gaan om te sien sommige van die gereedskap

10
00:00:34,360 --> 00:00:41,730
wat jy gebruik in pset 4 en pset 5 en soort en kombineer hulle in 1 mooi netjiese konsep

11
00:00:41,730 --> 00:00:43,830
wanneer jy kom om te dink oor dit.

12
00:00:43,830 --> 00:00:50,110
>> Ook, waarskynlik, pset 4 en 5 was die mees uitdagende psets wat ons gehad het om te bied.

13
00:00:50,110 --> 00:00:53,950
So van nou af, het ons hierdie 1 meer pset in C,

14
00:00:53,950 --> 00:00:56,480
en dan na dat ons op web programmering.

15
00:00:56,480 --> 00:01:02,310
So geluk julle om oor die moeilikste skof in CS50.

16
00:01:03,630 --> 00:01:09,760
>> Moving vir Huff'n Puff, ons toolbox vir hierdie pset gaan wees Huffman bome,

17
00:01:09,760 --> 00:01:14,700
so verstaan ​​van nie net hoe binêre bome werk, maar ook spesifiek Huffman bome,

18
00:01:14,700 --> 00:01:16,240
hoe hulle saamgestel.

19
00:01:16,240 --> 00:01:20,210
En dan gaan ons 'n baie van die verspreiding-kode te hê in hierdie pset,

20
00:01:20,210 --> 00:01:22,480
en ons sal kom om te sien wat werklik sommige van die kode

21
00:01:22,480 --> 00:01:24,670
ons dalk nie in staat wees om ten volle te verstaan ​​nog,

22
00:01:24,670 --> 00:01:30,080
en so sal die c-lêers., maar dan hul meegaande h lêers.

23
00:01:30,080 --> 00:01:34,300
sal ons genoeg begrip wat ons nodig het, sodat ons weet hoe die funksies werk

24
00:01:34,300 --> 00:01:38,100
of ten minste wat hulle veronderstel is om te doen - hulle insette en uitsette -

25
00:01:38,100 --> 00:01:40,760
selfs al weet ons nie wat gebeur in die swart blokkie

26
00:01:40,760 --> 00:01:44,090
of verstaan ​​nie wat gebeur in die swart blokkie in.

27
00:01:44,090 --> 00:01:49,400
En dan uiteindelik, soos gewoonlik, het ons te make met 'n nuwe datastrukture,

28
00:01:49,400 --> 00:01:51,840
spesifieke tipes van nodes wat verwys na sekere dinge,

29
00:01:51,840 --> 00:01:56,080
en so hier met 'n pen en papier nie net vir die ontwerp-proses

30
00:01:56,080 --> 00:01:58,470
en wanneer jy probeer om uit te vind hoe jou pset moet werk

31
00:01:58,470 --> 00:02:00,520
maar ook tydens ontfouting.

32
00:02:00,520 --> 00:02:06,140
Jy kan GDB langs jou pen en papier hê terwyl jy neem af wat die waardes is,

33
00:02:06,140 --> 00:02:09,320
waar jou pyle wys, en dinge soos dat.

34
00:02:09,320 --> 00:02:13,720
>> Eerste laat ons kyk na Huffman bome.

35
00:02:13,720 --> 00:02:19,600
Huffman bome binêre bome, wat beteken dat elke node net het 2 kinders.

36
00:02:19,600 --> 00:02:24,870
In Huffman bome die eienskap is dat die mees algemene waardes

37
00:02:24,870 --> 00:02:27,140
verteenwoordig deur die minste stukkies.

38
00:02:27,140 --> 00:02:32,690
Ons het gesien in die lesing voorbeelde van Morsekode, watter soort van gekonsolideerde sommige letters.

39
00:02:32,690 --> 00:02:38,030
As jy probeer om 'n A of 'n E te vertaal, byvoorbeeld,

40
00:02:38,030 --> 00:02:43,940
jy wat dikwels vertaling, so in plaas van met die volledige stel van die stukkies te gebruik

41
00:02:43,940 --> 00:02:48,640
toegeken vir daardie gewone datatipe jy compress dit af na minder,

42
00:02:48,640 --> 00:02:53,730
en dan die letters wat verteenwoordig minder dikwels word verteenwoordig met 'n lang stukkies

43
00:02:53,730 --> 00:02:59,840
want jy kan bekostig dat wanneer jy weeg die frekwensies wat daardie letters verskyn.

44
00:02:59,840 --> 00:03:03,020
Ons het dieselfde idee hier in Huffman bome

45
00:03:03,020 --> 00:03:12,360
waar ons 'n ketting, 'n soort van die pad om te kry om die bepaalde karakters.

46
00:03:12,360 --> 00:03:14,470
En dan die karakters wat die meeste frekwensie

47
00:03:14,470 --> 00:03:17,940
gaan word verteenwoordig met die minste stukkies.

48
00:03:17,940 --> 00:03:22,020
>> Die manier waarop jy bou 'n Huffman boom

49
00:03:22,020 --> 00:03:27,430
is deur die plasing van al die karakters wat verskyn in die teks

50
00:03:27,430 --> 00:03:30,630
en die berekening van die frekwensie, hoe dikwels hulle verskyn.

51
00:03:30,630 --> 00:03:33,880
Dit kan óf 'n telling van hoeveel keer die letters verskyn

52
00:03:33,880 --> 00:03:40,270
of dalk 'n persentasie uit van al die karakters hoeveel elkeen verskyn.

53
00:03:40,270 --> 00:03:44,270
En so wat jy doen, is wanneer jy al van daardie gekarteer uit,

54
00:03:44,270 --> 00:03:49,060
dan moet jy kyk vir die 2 laagste frekwensies en dan saam met hulle as broers en susters

55
00:03:49,060 --> 00:03:55,660
Waar is dan die ouer node het 'n frekwensie wat is die som van sy 2 kinders.

56
00:03:55,660 --> 00:04:00,870
En dan kan jy deur konvensie sê dat die linker node,

57
00:04:00,870 --> 00:04:03,770
jy volg dat deur die 0 tak,

58
00:04:03,770 --> 00:04:08,140
en dan die regterkantste node is die 1-tak.

59
00:04:08,140 --> 00:04:16,040
Soos ons gesien het in Morsekode, die een Gotcha was dat as jy net 'n beep en die beep

60
00:04:16,040 --> 00:04:18,120
dit was dubbelsinnig.

61
00:04:18,120 --> 00:04:22,430
Dit kan óf 1 letter of dit kan 'n reeks van 2 letters.

62
00:04:22,430 --> 00:04:27,790
En wat Huffman bome is gevolg deur die aard van die karakters

63
00:04:27,790 --> 00:04:34,140
of ons finale werklike karakters synde die laaste nodes op die tak -

64
00:04:34,140 --> 00:04:39,300
ons verwys na as blare - uit hoofde van daardie kan daar nie enige dubbelsinnigheid

65
00:04:39,300 --> 00:04:45,160
in terme van watter letter jy probeer om te enkodeer met die reeks van bisse

66
00:04:45,160 --> 00:04:50,670
want nêrens langs die bisse wat 1 letter

67
00:04:50,670 --> 00:04:55,960
sal jy nog 'n hele brief teëkom, en daar sal nie enige verwarring daar.

68
00:04:55,960 --> 00:04:58,430
Maar ons gaan in voorbeelde wat julle eintlik kan sien wat

69
00:04:58,430 --> 00:05:02,120
in plaas van ons net wat jy vertel dat dit is waar.

70
00:05:02,120 --> 00:05:06,390
>> Kom ons kyk na 'n eenvoudige voorbeeld van 'n Huffman boom.

71
00:05:06,390 --> 00:05:09,380
Ek het hier 'n string wat is 12 karakters lank wees.

72
00:05:09,380 --> 00:05:14,010
Ek het 4 As, 6 Bs, en 2 Cs.

73
00:05:14,010 --> 00:05:17,270
My eerste stap sou wees om te tel.

74
00:05:17,270 --> 00:05:20,760
Hoeveel keer het 'n verskyn? Dit blyk 4 keer in die tou.

75
00:05:20,760 --> 00:05:25,060
B verskyn 6 keer, en C verskyn 2 keer.

76
00:05:25,060 --> 00:05:28,970
Natuurlik, ek gaan om te sê Ek B is die gebruik van die meeste,

77
00:05:28,970 --> 00:05:35,970
Ek wil so om B te stel met die minste aantal bisse, die minste aantal 0'e en 1s.

78
00:05:35,970 --> 00:05:42,600
En dan is ek ook gaan om te verwag dat C die meeste bedrag van 0'e en 1s sowel vereis.

79
00:05:42,600 --> 00:05:48,550
Eerste wat ek hier het ek hulle in stygende orde in terme van frekwensie.

80
00:05:48,550 --> 00:05:52,710
Ons sien dat die C en die A, wat is ons 2 laagste frekwensies.

81
00:05:52,710 --> 00:06:00,290
Ons skep 'n ouer node, en daardie ouer node het nie 'n brief wat verband hou met dit,

82
00:06:00,290 --> 00:06:05,070
maar dit het 'n frekwensie wat is die som.

83
00:06:05,070 --> 00:06:08,780
Die som word 2 + 4, wat is 6.

84
00:06:08,780 --> 00:06:10,800
Dan volg ons die linker-tak.

85
00:06:10,800 --> 00:06:14,970
As ons op daardie 6 node, dan sou ons volg 0 om te kry tot C

86
00:06:14,970 --> 00:06:17,450
en dan 1 te kry A.

87
00:06:17,450 --> 00:06:20,300
So nou het ons 2 nodes.

88
00:06:20,300 --> 00:06:23,920
Ons het die waarde 6 en dan het ons ook 'n ander node met die waarde 6.

89
00:06:23,920 --> 00:06:28,550
En so het die 2 is nie net die 2 laagste, maar ook net die 2 wat oorgebly,

90
00:06:28,550 --> 00:06:33,820
sodat ons saam met dié deur 'n ander ouer, met die som 12.

91
00:06:33,820 --> 00:06:36,300
So hier is ons het ons Huffman boom

92
00:06:36,300 --> 00:06:40,020
waar om te kry tot B, sou dit net die bietjie 1

93
00:06:40,020 --> 00:06:45,430
en dan te kry om 'ons wil hê dat 01 en dan C met 00.

94
00:06:45,430 --> 00:06:51,300
So hier sien ons dat ons basies hierdie karakters is verteenwoordig met 1 of 2 bisse

95
00:06:51,300 --> 00:06:55,160
waar die B, soos voorspel, het die minste.

96
00:06:55,160 --> 00:07:01,730
En dan het ons verwag het C die meeste te hê, maar omdat dit so 'n klein Huffman boom,

97
00:07:01,730 --> 00:07:06,020
dan is die A word ook verteenwoordig deur 2 stukkies in teenstelling tot iewers in die middel.

98
00:07:07,820 --> 00:07:11,070
>> Net om te gaan oor 'n ander eenvoudige voorbeeld van die Huffman boom,

99
00:07:11,070 --> 00:07:19,570
sê jy het die string "Hello."

100
00:07:19,570 --> 00:07:25,360
Wat jy doen is die eerste wat jy sou sê hoeveel keer het H verskyn in hierdie?

101
00:07:25,360 --> 00:07:34,200
H verskyn een en dan e verskyn een keer en dan het ons l verskyn twee keer

102
00:07:34,200 --> 00:07:36,580
en o verskyn een keer.

103
00:07:36,580 --> 00:07:44,310
En so is daar dan verwag ons watter letter om verteenwoordig te word deur die minste aantal bisse?

104
00:07:44,310 --> 00:07:47,450
[Student] l. >> L. Ja. l is reg.

105
00:07:47,450 --> 00:07:50,730
Ons verwag dat l om verteenwoordig te word deur die minste aantal bisse

106
00:07:50,730 --> 00:07:55,890
want l is die meeste gebruik word in die tou "Hallo."

107
00:07:55,890 --> 00:08:04,280
Wat ek nou doen is trek uit hierdie nodes.

108
00:08:04,280 --> 00:08:15,580
Ek het 1, wat is H, en dan ander 1, wat e, en dan 'n 1, wat is o -

109
00:08:15,580 --> 00:08:23,410
ek nou om dit in orde - en dan 2, wat l.

110
00:08:23,410 --> 00:08:32,799
Dan sê ek die manier wat ek gaan bou, 'n Huffman boom is die 2 nodes met die minste frekwensies te vind

111
00:08:32,799 --> 00:08:38,010
en maak hulle broers en susters deur die skep van 'n ouer node.

112
00:08:38,010 --> 00:08:41,850
Hier het ons het 3 nodusse met die laagste frekwensie. Hulle is almal 1.

113
00:08:41,850 --> 00:08:50,620
So hier is ons kies watter een gaan ons eerste skakel.

114
00:08:50,620 --> 00:08:54,850
Kom ons sê ek kies die H en die e.

115
00:08:54,850 --> 00:09:01,150
Die som van 1 + 1 is 2, maar hierdie node het nie 'n brief wat verband hou met dit.

116
00:09:01,150 --> 00:09:04,440
Dit hou net die waarde.

117
00:09:04,440 --> 00:09:10,950
Nou moet ons kyk na die volgende 2 laagste frekwensies.

118
00:09:10,950 --> 00:09:15,590
Dit is 2 en 1. Dit kan een van daardie 2 wees, maar ek gaan hierdie een te kies.

119
00:09:15,590 --> 00:09:18,800
Die som 3.

120
00:09:18,800 --> 00:09:26,410
En dan uiteindelik, ek het net 2 links, so dan is dit word 5.

121
00:09:26,410 --> 00:09:32,010
Dan is hier, soos verwag, as ek in die kodering vir daardie vul,

122
00:09:32,010 --> 00:09:37,480
1s die regte tak en 0'e altyd die linker een.

123
00:09:37,480 --> 00:09:45,880
Dan het ons l verteenwoordig deur net 1 bietjie en dan die o 2

124
00:09:45,880 --> 00:09:52,360
en dan die e deur 2 en dan val die H 3 stukkies.

125
00:09:52,360 --> 00:09:59,750
So kan jy hierdie boodskap oordra "Hallo" eerder as om werklik die gebruik van die karakters

126
00:09:59,750 --> 00:10:02,760
deur net 0'e en 1s.

127
00:10:02,760 --> 00:10:07,910
Onthou egter dat in verskeie gevalle moes ons bande met ons frekwensie.

128
00:10:07,910 --> 00:10:11,900
Ons kan óf die H en die o eerste miskien aangesluit het.

129
00:10:11,900 --> 00:10:15,730
Of dan later toe ons die l verteenwoordig deur 2

130
00:10:15,730 --> 00:10:19,410
sowel as die by een verteenwoordig deur 2, kan ons óf een gekoppel.

131
00:10:19,410 --> 00:10:23,630
>> En so wanneer jy die 0'e en 1s, wat eintlik nie waarborg

132
00:10:23,630 --> 00:10:27,090
dat die ontvanger ten volle kan lees jou boodskap regs af die vlermuis

133
00:10:27,090 --> 00:10:30,490
omdat hulle dalk nie weet watter besluit wat jy gemaak het.

134
00:10:30,490 --> 00:10:34,920
So wanneer ons te doen het met Huffman kompressie,

135
00:10:34,920 --> 00:10:40,090
een of ander manier het ons die ontvanger van ons boodskap te vertel hoe ons besluit -

136
00:10:40,090 --> 00:10:43,470
Hulle moet 'n soort van ekstra inligting om te weet

137
00:10:43,470 --> 00:10:46,580
in Benewens die saamgeperste boodskap.

138
00:10:46,580 --> 00:10:51,490
Wat hulle nodig het om te verstaan ​​wat die boom eintlik lyk soos,

139
00:10:51,490 --> 00:10:55,450
hoe ons eintlik het dié besluite hê.

140
00:10:55,450 --> 00:10:59,100
>> Hier het ons net voorbeelde wat gebaseer is op die werklike telling doen,

141
00:10:59,100 --> 00:11:01,550
maar soms kan jy ook 'n Huffman boom

142
00:11:01,550 --> 00:11:05,760
gebaseer op die frekwensie waarteen letters verskyn, en dit is die presiese dieselfde proses.

143
00:11:05,760 --> 00:11:09,090
Hier is ek die uitdrukking van dit in terme van persentasies of 'n breuk,

144
00:11:09,090 --> 00:11:11,290
en so hier is die presies dieselfde ding.

145
00:11:11,290 --> 00:11:15,300
Ek vind die 2 laagste, vat hulle die volgende 2 laagste, vat hulle,

146
00:11:15,300 --> 00:11:19,390
totdat ek het 'n volledige boom.

147
00:11:19,390 --> 00:11:23,610
Selfs al kan ons dit doen een manier, wanneer ons te doen het met persentasies,

148
00:11:23,610 --> 00:11:27,760
dit beteken dat ons dinge is die verdeling en die hantering van desimale of dryf eerder

149
00:11:27,760 --> 00:11:30,900
As ons dink oor data strukture van 'n kop.

150
00:11:30,900 --> 00:11:32,540
Wat weet ons oor die dryf?

151
00:11:32,540 --> 00:11:35,180
Wat is 'n algemene probleem wanneer ons te doen het met dryf?

152
00:11:35,180 --> 00:11:38,600
[Student] vaag rekenkunde. >> Ja. Onakkuraatheid.

153
00:11:38,600 --> 00:11:43,760
As gevolg van floating point onakkuraatheid, vir hierdie pset so dat ons seker maak

154
00:11:43,760 --> 00:11:49,450
dat ons nie enige waardes verloor, dan is ons eintlik gaan om te word wat met die telling.

155
00:11:49,450 --> 00:11:54,880
So as jy was om te dink van 'n Huffman node, as jy kyk terug na die struktuur,

156
00:11:54,880 --> 00:12:01,740
as jy kyk na die groen, dit het 'n frekwensie wat verband hou met dit

157
00:12:01,740 --> 00:12:08,760
sowel as dit dui op 'n knoop aan die linkerkant asook 'n knoop aan sy regterkant.

158
00:12:08,760 --> 00:12:13,970
En dan die rooies is daar ook 'n karakter wat verband hou met hulle.

159
00:12:13,970 --> 00:12:18,900
Ons gaan nie afsonderlike kinders te maak vir die ouers en dan die finale nodes,

160
00:12:18,900 --> 00:12:23,680
wat ons verwys na as blare, maar eerder dié sal net NULL waardes.

161
00:12:23,680 --> 00:12:31,050
Vir elke node sal ons 'n karakter, die simbool dat node verteenwoordig,

162
00:12:31,050 --> 00:12:40,490
dan 'n frekwensie sowel as 'n wyser na die linkerkant kind sowel as sy reg kind.

163
00:12:40,490 --> 00:12:45,680
Die blare, wat heel aan die onderkant, sal ook node pointers

164
00:12:45,680 --> 00:12:49,550
aan hul linkerkant en aan hulle hul reg, maar sedert daardie waardes word nie verwys na die werklike nodes,

165
00:12:49,550 --> 00:12:53,970
wat hul waarde sou wees? >> [Student] null. >> Null. Presies.

166
00:12:53,970 --> 00:12:58,430
Hier is 'n voorbeeld van hoe jy kan verteenwoordig in die frekwensie dryf,

167
00:12:58,430 --> 00:13:02,130
maar ons gaan word om dit te hanteer met heelgetalle,

168
00:13:02,130 --> 00:13:06,780
so al wat ek gedoen het, is verander die datatipe daar.

169
00:13:06,780 --> 00:13:09,700
>> Kom ons gaan op 'n bietjie meer van 'n komplekse voorbeeld.

170
00:13:09,700 --> 00:13:13,360
Maar nou dat ons die eenvoudiges gedoen het nie, dis net dieselfde proses.

171
00:13:13,360 --> 00:13:20,290
Jy kry die 2 laagste frekwensies, som die frekwensies

172
00:13:20,290 --> 00:13:22,450
en dit is die nuwe frekwensie van jou voorgangernode,

173
00:13:22,450 --> 00:13:29,310
wat dui dan aan die linkerkant met die 0-tak en die reg met die 1-tak.

174
00:13:29,310 --> 00:13:34,200
As ons die string "Dit is cs50," dan moet ons tel hoeveel keer is T genoem,

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

176
00:13:38,420 --> 00:13:42,010
Dan wat ek hier gedoen het, is met die rooi nodes Ek het net geplant,

177
00:13:42,010 --> 00:13:48,530
Ek het gesê ek gaan hierdie karakters om uiteindelik aan die onderkant van my boom.

178
00:13:48,530 --> 00:13:51,740
Diegene gaan wees al die blare.

179
00:13:51,740 --> 00:13:58,200
Dan wat ek gedoen het, is ek hulle deur die frekwensie in stygende volgorde gesorteer,

180
00:13:58,200 --> 00:14:02,950
en dit is eintlik die manier waarop die pset kode doen dit

181
00:14:02,950 --> 00:14:07,550
is dit sorteer dit deur die frekwensie en dan alfabeties.

182
00:14:07,550 --> 00:14:13,870
So het die syfers vir die eerste keer en dan alfabeties volgens die frekwensie.

183
00:14:13,870 --> 00:14:18,520
Dan wat ek sou doen, is ek die 2 laagste sou vind. Dit is 0 en 5.

184
00:14:18,520 --> 00:14:22,390
Ek sou vat, en dit is 2. Dan sou ek voortgaan, vind die volgende 2 laagste.

185
00:14:22,390 --> 00:14:26,100
Dit is die twee 1s, en dan dié geword 2 as goed.

186
00:14:26,100 --> 00:14:31,570
Nou weet ek dat my volgende stap gaan word by die laagste getal,

187
00:14:31,570 --> 00:14:41,380
wat is die T 1, en dan die keuse van een van die nodusse wat 2 as die frekwensie.

188
00:14:41,380 --> 00:14:44,560
So hier is ons het 3 opsies.

189
00:14:44,560 --> 00:14:47,980
Wat ek gaan om te doen vir die skyfie is visueel herrangskik hulle net vir jou

190
00:14:47,980 --> 00:14:51,790
sodat jy kan sien hoe ek dit is die opbou.

191
00:14:51,790 --> 00:14:59,040
Wat die kode en jou verspreiding kode gaan doen sou aansluit by die T-

192
00:14:59,040 --> 00:15:01,410
met die 0 en 5 node.

193
00:15:01,410 --> 00:15:05,060
So dan dat die somme tot 3, en dan sal ons voortgaan om die proses.

194
00:15:05,060 --> 00:15:08,660
Die 2 en die 2 nou is die laagste, so dan daardie som tot 4.

195
00:15:08,660 --> 00:15:12,560
Almal volg so ver? Okay.

196
00:15:12,560 --> 00:15:16,410
Daarna het ons die 3 en die 3 wat aangespreek moet word opgetel,

197
00:15:16,410 --> 00:15:21,650
so ek is net skakel dit so dat jy kan visueel so sien dat dit nie te morsige.

198
00:15:21,650 --> 00:15:25,740
Dan het ons 'n 6, en dan is ons finale stap is nou dat ons slegs 2 nodes

199
00:15:25,740 --> 00:15:30,440
ons som die wortel van die boom, wat 10 te maak.

200
00:15:30,440 --> 00:15:34,100
En die getal 10 maak sin omdat elke node verteenwoordig,

201
00:15:34,100 --> 00:15:40,750
hul waarde, die frekwensie, was hoeveel keer hulle in die tou verskyn,

202
00:15:40,750 --> 00:15:46,350
en dan het ons 5 karakters in ons string, so dit maak sin.

203
00:15:48,060 --> 00:15:52,320
As ons kyk hoe ons dit sou eintlik enkodeer,

204
00:15:52,320 --> 00:15:56,580
soos verwag, die ek en die s, en wat die meeste

205
00:15:56,580 --> 00:16:01,350
word verteenwoordig deur die minste aantal bisse.

206
00:16:03,660 --> 00:16:05,660
>> Wees versigtig hier.

207
00:16:05,660 --> 00:16:09,780
In Huffman bome van die geval saak eintlik.

208
00:16:09,780 --> 00:16:13,670
'N hoofletter S is anders as 'n kleinletter s.

209
00:16:13,670 --> 00:16:21,260
As ons gehad het "Dit is CS50" met hoofletters, dan die klein letters is net twee keer verskyn,

210
00:16:21,260 --> 00:16:27,120
'n knoop met 2 as sy waarde sou wees, en dan hoofletters S sal slegs een keer.

211
00:16:27,120 --> 00:16:33,440
So dan is jou boom strukture sou verander omdat jy eintlik 'n ekstra blaar hier.

212
00:16:33,440 --> 00:16:36,900
Maar die som sou nog 10.

213
00:16:36,900 --> 00:16:39,570
Dit is wat ons eintlik gaan om die roeping van die checksum,

214
00:16:39,570 --> 00:16:44,060
die toevoeging van al die tellings.

215
00:16:46,010 --> 00:16:50,990
>> Nou dat ons Huffman bome het gedek, kan ons duik in Huff'n Puff, die pset.

216
00:16:50,990 --> 00:16:52,900
Ons gaan om te begin met 'n gedeelte van die vrae,

217
00:16:52,900 --> 00:16:57,990
en dit gaan te kry wat jy gewoond met binêre bome en hoe om te werk om dat:

218
00:16:57,990 --> 00:17:03,230
teken nodes, die skep van jou eie typedef struct vir 'n node,

219
00:17:03,230 --> 00:17:07,230
en sien hoe jy kan plaas in 'n binêre boom, een wat gesorteer,

220
00:17:07,230 --> 00:17:09,050
kameelkoei dit, en dinge soos dat.

221
00:17:09,050 --> 00:17:14,560
Daardie kennis is beslis gaan om jou te help wanneer jy duik in die Huff'n Puff gedeelte

222
00:17:14,560 --> 00:17:17,089
van die pset.

223
00:17:19,150 --> 00:17:26,329
In die standaard uitgawe van die pset, jou taak is om Puff te implementeer,

224
00:17:26,329 --> 00:17:30,240
en in die hacker weergawe is jou taak is Huff te implementeer.

225
00:17:30,240 --> 00:17:38,490
Wat Huff doen, is wat dit neem om teks en dan is dit vertaal dit in die 0'e en 1s,

226
00:17:38,490 --> 00:17:41,990
sodat die proses wat ons hierbo gedoen het waar ons die frekwensies getel

227
00:17:41,990 --> 00:17:50,970
en dan het die boom en dan sê: "Hoe kry ek 'T?"

228
00:17:50,970 --> 00:17:54,840
T word verteenwoordig deur 100, dinge soos dat,

229
00:17:54,840 --> 00:17:58,860
en dan Huff sal neem om die teks en dan uitset dat binêre.

230
00:17:58,860 --> 00:18:04,920
Maar ook omdat ons weet dat ons wil ons ontvanger van die boodskap toe te laat

231
00:18:04,920 --> 00:18:11,790
die presiese dieselfde boom te herskep, sluit dit ook inligting oor die frekwensie tel.

232
00:18:11,790 --> 00:18:17,980
Dan met Puff ons gegee is om 'n binêre lêer van 0'e en 1s

233
00:18:17,980 --> 00:18:21,740
en ook die inligting oor die frekwensies.

234
00:18:21,740 --> 00:18:26,740
Ons vertaal al van daardie 0'e en 1s terug in die oorspronklike boodskap wat was,

235
00:18:26,740 --> 00:18:29,350
sodat ons decompressie.

236
00:18:29,350 --> 00:18:36,450
As jy die standaard uitgawe doen, hoef jy nie te implementeer Huff,

237
00:18:36,450 --> 00:18:39,290
so dan kan jy net gebruik maak van die personeel implementering van Huff.

238
00:18:39,290 --> 00:18:42,080
Daar is instruksies oor hoe om dit te doen in die spec.

239
00:18:42,080 --> 00:18:48,780
Jy kan die personeel implementering van Huff loop op 'n sekere teks lêer

240
00:18:48,780 --> 00:18:53,270
en gebruik dan dat die uitset as jou insette Puff.

241
00:18:53,270 --> 00:18:59,330
>> Soos ek voorheen genoem het, ons het 'n baie van verspreiding-kode vir hierdie een.

242
00:18:59,330 --> 00:19:01,810
Ek gaan om te begin gaan deur dit.

243
00:19:01,810 --> 00:19:04,400
Ek gaan die meeste van die tyd te spandeer op die h lêers

244
00:19:04,400 --> 00:19:07,660
want in die C-lêers., want ons het die h

245
00:19:07,660 --> 00:19:11,650
en dat ons met die prototipes van die funksies,

246
00:19:11,650 --> 00:19:15,520
ons nie ten volle nie nodig om presies te verstaan ​​-

247
00:19:15,520 --> 00:19:20,280
As jy nie verstaan ​​wat gaan aan in die C-lêers., Doen dan nie te veel bekommerd wees,

248
00:19:20,280 --> 00:19:23,600
maar beslis probeer om 'n blik te neem, want dit kan 'n paar wenke gee

249
00:19:23,600 --> 00:19:29,220
en dit is nuttig om gewoond te raak aan die lees van ander mense se kode.

250
00:19:38,940 --> 00:19:48,270
>> Looking by huffile.h, in die kommentaar dit verklaar 'n laag van abstraksie vir Huffman-gekodeerde lêers.

251
00:19:48,270 --> 00:20:01,660
As ons gaan af, sien ons dat daar 'n maksimum van 256 simbole wat ons codes dalk nodig vir.

252
00:20:01,660 --> 00:20:05,480
Dit sluit al die letters van die alfabet - hoofletters en klein -

253
00:20:05,480 --> 00:20:08,250
en dan simbole en nommers, ens.

254
00:20:08,250 --> 00:20:11,930
Dan is hier ons het 'n magie nommer die identifisering van 'n Huffman-gekodeerde lêer.

255
00:20:11,930 --> 00:20:15,890
Binne 'n Huffman-kode hulle gaan 'n sekere magic number

256
00:20:15,890 --> 00:20:18,560
wat verband hou met die kop.

257
00:20:18,560 --> 00:20:21,110
Dit kan lyk soos net 'n ewekansige magic number,

258
00:20:21,110 --> 00:20:27,160
maar as jy eintlik is dit vertaal in ASCII, dan is dit spel eintlik uit HUFF.

259
00:20:27,160 --> 00:20:34,290
Hier het ons het 'n struct vir 'n Huffman-geënkodeerde lêer.

260
00:20:34,290 --> 00:20:39,670
Daar is al van hierdie eienskappe wat verband hou met 'n Huff-lêer.

261
00:20:39,670 --> 00:20:47,080
Dan af hier het ons die bladsyboskrif ('header') vir 'n Huff-lêer, sodat ons noem dit Huffeader

262
00:20:47,080 --> 00:20:50,810
in plaas van die toevoeging van die ekstra h, want dit klink in elk geval dieselfde.

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

264
00:20:52,720 --> 00:20:57,790
Ons het 'n magie nommer wat verband hou met dit.

265
00:20:57,790 --> 00:21:09,040
As dit is 'n werklike Huff lêer, gaan dit na die nommer bo, hierdie magie.

266
00:21:09,040 --> 00:21:14,720
En dan sal dit 'n skikking.

267
00:21:14,720 --> 00:21:18,750
Dus, vir elke simbool, waarvan daar 256,

268
00:21:18,750 --> 00:21:24,760
dit gaan om te lys wat die frekwensie van daardie simbole binne die Huff-lêer.

269
00:21:24,760 --> 00:21:28,090
En dan uiteindelik, ons het 'n checksum vir die frekwensies,

270
00:21:28,090 --> 00:21:32,160
wat moet die som van die frekwensies.

271
00:21:32,160 --> 00:21:36,520
So dit is wat 'n Huffeader is.

272
00:21:36,520 --> 00:21:44,600
Dan het ons het 'n paar funksies wat die standaard van die volgende bietjie in die Huff-lêer

273
00:21:44,600 --> 00:21:52,580
sowel as skryf 'n bietjie aan die Huff lêer en dan hierdie funksie hier, hfclose

274
00:21:52,580 --> 00:21:54,650
Dit sluit eintlik die Huff lêer.

275
00:21:54,650 --> 00:21:57,290
Voor, het ons te make met reguit net fclose,

276
00:21:57,290 --> 00:22:01,190
maar wanneer jy 'n Huff lêer, in plaas van fclosing dit

277
00:22:01,190 --> 00:22:06,080
wat jy eintlik gaan doen, is hfclose en hfopen dit.

278
00:22:06,080 --> 00:22:13,220
Dit is spesifieke funksies aan die Huff lêers wat ons gaan die hantering van.

279
00:22:13,220 --> 00:22:19,230
Dan is hier ons lees in die kop en skryf dan die kop.

280
00:22:19,230 --> 00:22:25,700
>> Net deur die lees van die h-lêer, kan ons soort van 'n gevoel kry van wat 'n Huff lêer kan wees,

281
00:22:25,700 --> 00:22:32,480
watter eienskappe dit het, sonder om eintlik gaan in die huffile.c,

282
00:22:32,480 --> 00:22:36,750
wat, as ons duik in, gaan 'n bietjie meer kompleks.

283
00:22:36,750 --> 00:22:41,270
Dit het al van die lêer I / O hier te doen met verwysings.

284
00:22:41,270 --> 00:22:48,010
Hier sien ons dat wanneer ons noem hfread, byvoorbeeld, is dit nog steeds doen het met fread.

285
00:22:48,010 --> 00:22:53,050
Ons is nie om ontslae te raak van daardie werksaamhede in sy geheel, maar ons stuur wat geneem moet word versorging van

286
00:22:53,050 --> 00:22:59,760
binne die Huff lêer in plaas van die doen dit self.

287
00:22:59,760 --> 00:23:02,300
Jy kan voel vry om te scan deur as jy nuuskierig

288
00:23:02,300 --> 00:23:08,410
en gaan en skil die laag 'n bietjie terug.

289
00:23:20,650 --> 00:23:24,060
>> Die volgende lêer dat ons gaan om te kyk na is tree.h.

290
00:23:24,060 --> 00:23:30,210
Voor in die Walk Through skyfies het ons gesê ons verwag 'n Huffman node

291
00:23:30,210 --> 00:23:32,960
en ons het 'n typedef struct node.

292
00:23:32,960 --> 00:23:38,360
Ons verwag dat dit 'n simbool, 'n frekwensie, en dan 2 node sterre.

293
00:23:38,360 --> 00:23:41,870
In hierdie geval wat ons doen, is dit in wese dieselfde is

294
00:23:41,870 --> 00:23:46,880
behalwe in plaas van node het ons gaan om te bel hulle bome.

295
00:23:48,790 --> 00:23:56,760
Ons het 'n funksie dat wanneer jy noem maak boom dit terug jy 'n boom wyser.

296
00:23:56,760 --> 00:24:03,450
Terug na Speller, wanneer jy besig was om 'n nuwe node

297
00:24:03,450 --> 00:24:11,410
jy sê node * nuwe woord = malloc (sizeof) en dinge soos dat.

298
00:24:11,410 --> 00:24:17,510
Basies, is mktree gaan doen met dit vir jou.

299
00:24:17,510 --> 00:24:20,990
Net so, wanneer jy wil om 'n boom te verwyder,

300
00:24:20,990 --> 00:24:24,810
sodat legen die boom wanneer jy klaar is met dit,

301
00:24:24,810 --> 00:24:33,790
in plaas van uitdruklik roep op daardie, jy eintlik net gaan om die funksie te rmtree gebruik

302
00:24:33,790 --> 00:24:40,360
waar jy in die wyser na daardie boom en dan tree.c sal sorg dit vir jou.

303
00:24:40,360 --> 00:24:42,490
>> Ons sien in tree.c.

304
00:24:42,490 --> 00:24:47,240
Ons verwag dieselfde funksies behalwe die implementering sowel sien.

305
00:24:47,240 --> 00:24:57,720
As wat ons verwag het, wanneer jy bel mktree dit mallocs die grootte van 'n boom in 'n wyser,

306
00:24:57,720 --> 00:25:03,190
initialisatie van al die waardes aan die NULL waarde, so 0s of NULLs,

307
00:25:03,190 --> 00:25:08,280
en terugstuur dan die wyser na daardie boom wat jy het nou net malloc'd aan jou.

308
00:25:08,280 --> 00:25:13,340
Hier wanneer jy noem verwyder boom dit maak eers seker dat jy dubbel is nie bevry.

309
00:25:13,340 --> 00:25:18,320
Dit maak seker dat jy eintlik 'n boom wat jy wil verwyder.

310
00:25:18,320 --> 00:25:23,330
Hier, want 'n boom sluit ook sy kinders,

311
00:25:23,330 --> 00:25:29,560
Wat dit beteken is dit noem rekursief verwyder boom aan die linkerkant node van die boom

312
00:25:29,560 --> 00:25:31,650
sowel as die regte node.

313
00:25:31,650 --> 00:25:37,790
Voordat dit bevry die ouer, die kinders wat dit nodig het om so goed te bevry.

314
00:25:37,790 --> 00:25:42,770
Ouer is ook uitruilbaar met wortel.

315
00:25:42,770 --> 00:25:46,500
Die eerste keer ooit ouer, so soos die groot-groot-groot-groot-oupa

316
00:25:46,500 --> 00:25:52,130
of ouma boom, het ons eers af te bevry die vlakke vir die eerste keer.

317
00:25:52,130 --> 00:25:58,490
So deurkruis na die bodem, gratis diegene, en dan terug te kom, gratis diegene, ens.

318
00:26:00,400 --> 00:26:02,210
So wat se boom.

319
00:26:02,210 --> 00:26:04,240
>> Nou kyk ons ​​in die bos.

320
00:26:04,240 --> 00:26:09,860
Bos is waar jy plaas al jou Huffman bome.

321
00:26:09,860 --> 00:26:12,910
Dit sê dat ons gaan om iets te hê wat 'n plot genoem

322
00:26:12,910 --> 00:26:22,320
Dit bevat 'n wyser na 'n boom sowel as 'n wyser na 'n plot genoem volgende.

323
00:26:22,320 --> 00:26:28,480
Watter struktuur doen hierdie soort van lyk?

324
00:26:29,870 --> 00:26:32,490
Dit soort van sê dit daar.

325
00:26:34,640 --> 00:26:36,700
Reg oor hier.

326
00:26:37,340 --> 00:26:39,170
'N geskakelde lys.

327
00:26:39,170 --> 00:26:44,590
Sien ons dat wanneer ons 'n plot dit is soos 'n geskakelde lys van persele.

328
00:26:44,590 --> 00:26:53,020
'N bos is gedefinieer as 'n geskakelde lys van erwe,

329
00:26:53,020 --> 00:26:58,100
en so die struktuur van die bos is ons net gaan om 'n wyser te hê aan ons eerste plot

330
00:26:58,100 --> 00:27:02,740
en dat die plot het 'n boom in dit of eerder aan 'n boom

331
00:27:02,740 --> 00:27:06,190
en wys dan na die volgende plot, so aan en so voort.

332
00:27:06,190 --> 00:27:11,100
'N bos te maak, noem ons mkforest.

333
00:27:11,100 --> 00:27:14,930
Dan het ons 'n paar mooi nuttige funksies hier.

334
00:27:14,930 --> 00:27:23,240
Ons het kies waar jy in 'n bos en dan die terugkeer waarde is 'n Tree *

335
00:27:23,240 --> 00:27:25,210
'n wyser na 'n boom.

336
00:27:25,210 --> 00:27:29,370
Wat pick sal doen, is dit gaan in die bos dat jy verwys na

337
00:27:29,370 --> 00:27:35,240
verwyder dan 'n boom met die laagste frekwensie van daardie bos

338
00:27:35,240 --> 00:27:38,330
en dan gee jy die wyser na daardie boom.

339
00:27:38,330 --> 00:27:43,030
Sodra jy 'n beroep kies, sal die boom nie bestaan ​​in die bos nie,

340
00:27:43,030 --> 00:27:48,550
maar die opbrengs waarde is die wyser na daardie boom.

341
00:27:48,550 --> 00:27:50,730
Dan moet jy plant.

342
00:27:50,730 --> 00:27:57,420
Met dien verstande dat jy in 'n wyser na 'n boom wat 'n nie-0 frekwensie,

343
00:27:57,420 --> 00:28:04,040
watter plant sal doen, sal dit die bos, neem die boom, en plant wat binnekant van die bos boom.

344
00:28:04,040 --> 00:28:06,370
Hier het ons 'rmforest.

345
00:28:06,370 --> 00:28:11,480
Similar boom te verwyder, wat basies almal van ons bome bevry vir ons,

346
00:28:11,480 --> 00:28:16,600
verwyder bos sal gratis alles vervat in daardie bos.

347
00:28:16,600 --> 00:28:24,890
>> As ons kyk na forest.c, sal ons verwag om ten minste 1 rmtree opdrag om te sien daar,

348
00:28:24,890 --> 00:28:30,090
omdat gratis geheue in die bos as 'n bos bome in,

349
00:28:30,090 --> 00:28:32,930
dan uiteindelik sal jy gaan hê om die bome te verwyder.

350
00:28:32,930 --> 00:28:41,020
As ons kyk na forest.c, ons het ons mkforest, wat soos ons verwag.

351
00:28:41,020 --> 00:28:42,890
Ons malloc dinge.

352
00:28:42,890 --> 00:28:51,740
Ons inisialiseer die eerste plot in die bos as NULL, omdat dit leeg is om mee te begin,

353
00:28:51,740 --> 00:29:05,940
dan sien ons pluk, wat gee die boom met die laagste gewig, die laagste frekwensie,

354
00:29:05,940 --> 00:29:13,560
en dan ontslae raak van daardie spesifieke node dat punte aan daardie boom en die volgende een,

355
00:29:13,560 --> 00:29:16,760
so dit neem dat van die geskakelde lys van die bos.

356
00:29:16,760 --> 00:29:24,510
En dan is hier ons het 'n plant, wat voeg 'n boom in die geskakelde lys.

357
00:29:24,510 --> 00:29:29,960
Wat bos is dit mooi hou dit gesorteer vir ons.

358
00:29:29,960 --> 00:29:37,910
En dan uiteindelik, ons het rmforest en, soos verwag, het ons rmtree genoem daar.

359
00:29:46,650 --> 00:29:55,440
>> Op soek na die verspreiding kode so ver, huffile.c was waarskynlik verreweg die moeilikste om te verstaan,

360
00:29:55,440 --> 00:29:59,990
terwyl die ander lêers self was redelik maklik om te volg.

361
00:29:59,990 --> 00:30:03,090
Met ons kennis van wysers en geskakelde lyste en sodanige

362
00:30:03,090 --> 00:30:04,860
ons in staat was om baie goed volg.

363
00:30:04,860 --> 00:30:10,500
Maar al wat ons nodig het om werklik te maak seker dat ons ten volle verstaan ​​die h-lêers.

364
00:30:10,500 --> 00:30:15,840
want jy moet die roeping van daardie werksaamhede, wat handel met daardie opgawe waardes,

365
00:30:15,840 --> 00:30:20,590
so maak seker dat jy ten volle verstaan ​​watter stappe uitgevoer gaan word

366
00:30:20,590 --> 00:30:24,290
wanneer jy bel een van daardie funksies.

367
00:30:24,290 --> 00:30:33,020
Maar eintlik begrip binnekant van dit is nie heeltemal nodig nie, want ons het daardie h lêers.

368
00:30:35,170 --> 00:30:39,490
Ons het 2 meer lêers links in ons verspreiding kode.

369
00:30:39,490 --> 00:30:41,640
>> Kom ons kyk na dump.

370
00:30:41,640 --> 00:30:47,230
Stort deur sy kommentaar hier, neem 'n Huffman-saamgeperste lêer

371
00:30:47,230 --> 00:30:55,580
en dan vertaal en vullishope van die inhoud uit.

372
00:31:01,010 --> 00:31:04,260
Hier sien ons dat dit hfopen opbelt.

373
00:31:04,260 --> 00:31:10,770
Dit is 'n soort van die spieël * insette FILE = fopen,

374
00:31:10,770 --> 00:31:13,500
en dan is jy in die inligting.

375
00:31:13,500 --> 00:31:18,240
Dit is byna identies, behalwe in plaas van 'n lêer * jy verby in 'n Huffile;

376
00:31:18,240 --> 00:31:22,030
in plaas van fopen jy verby in hfopen.

377
00:31:22,030 --> 00:31:29,280
Hier lees ons in die kop eerste, wat is 'n soort van soortgelyk aan hoe ons lees in die kop

378
00:31:29,280 --> 00:31:33,580
vir 'n bitmap-lêer.

379
00:31:33,580 --> 00:31:38,000
Wat ons hier doen, is om te kyk of die header information

380
00:31:38,000 --> 00:31:44,330
bevat die regte magie getal wat aandui dat dit 'n werklike Huff lêer,

381
00:31:44,330 --> 00:31:53,610
dan sal al hierdie kontrole om seker te maak dat die lêer wat ons oop is 'n werklike huffed lêer of nie.

382
00:31:53,610 --> 00:32:05,330
Wat dit beteken is dit uitgange die frekwensies van al die simbole wat ons kan sien

383
00:32:05,330 --> 00:32:09,790
binne 'n terminaal in 'n grafiese tafel.

384
00:32:09,790 --> 00:32:15,240
Hierdie gedeelte gaan nuttig te wees.

385
00:32:15,240 --> 00:32:24,680
Dit het 'n bietjie en lees bietjie vir bietjie in die veranderlike bietjie en dan druk dit uit.

386
00:32:28,220 --> 00:32:35,430
So as ek dump te roep op hth.bin, wat die gevolg is van 'n lêer te hijgen

387
00:32:35,430 --> 00:32:39,490
met behulp van die personeel oplossing, sou ek hierdie.

388
00:32:39,490 --> 00:32:46,000
Dit is printer al hierdie karakters en dan om die frekwensie waarteen hulle verskyn.

389
00:32:46,000 --> 00:32:51,180
As ons kyk, die meeste van hulle is 0e behalwe vir hierdie: H, wat twee keer voorkom,

390
00:32:51,180 --> 00:32:54,820
en dan T, wat verskyn een keer.

391
00:32:54,820 --> 00:33:07,860
En dan hier het ons die werklike boodskap in 0'e en 1s.

392
00:33:07,860 --> 00:33:15,450
As ons kyk by die hth.txt, wat vermoedelik die oorspronklike boodskap wat huffed,

393
00:33:15,450 --> 00:33:22,490
ons verwag om te sien sommige Hs en Ts daar.

394
00:33:22,490 --> 00:33:28,720
Spesifiek, ons verwag net 1 T om te sien en 2 Hs.

395
00:33:32,510 --> 00:33:37,440
Hier is ons in hth.txt. Dit het inderdaad HTH.

396
00:33:37,440 --> 00:33:41,270
Ingesluit in daar, maar ons kan dit nie sien nie, is 'n newline karakter.

397
00:33:41,270 --> 00:33:53,190
Die Huff lêer hth.bin is ook die enkodering van die newline karakter as goed.

398
00:33:55,680 --> 00:34:01,330
Hier omdat ons weet dat die orde is HTH en dan newline,

399
00:34:01,330 --> 00:34:07,340
kan ons sien dat waarskynlik die H is verteenwoordig deur net 'n enkele 1

400
00:34:07,340 --> 00:34:17,120
en dan die T is waarskynlik 01 en dan die volgende H 1 asook

401
00:34:17,120 --> 00:34:21,139
en dan het ons 'n newline aangedui deur twee 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> En dan uiteindelik, omdat ons te doen het met verskeie c en h lêers,

404
00:34:31,600 --> 00:34:36,350
ons gaan 'n redelik komplekse argument te hê aan die vertaler,

405
00:34:36,350 --> 00:34:40,460
en so hier het ons 'n makefile wat dump maak vir jou.

406
00:34:40,460 --> 00:34:47,070
Maar eintlik, jy het om te gaan oor die maak van jou eie puff.c lêer.

407
00:34:47,070 --> 00:34:54,330
Die makefile eintlik nie hanteer vir jou puff.c te maak.

408
00:34:54,330 --> 00:34:59,310
Ons verlaat dat tot jy die makefile te wysig.

409
00:34:59,310 --> 00:35:05,930
Wanneer jy 'n opdrag soos alles maak, byvoorbeeld, sal dit maak almal van hulle vir jou.

410
00:35:05,930 --> 00:35:10,760
Voel vry om te kyk na die voorbeelde van makefile uit die verlede pset

411
00:35:10,760 --> 00:35:17,400
sowel as van hierdie een af ​​om te sien hoe jy dalk in staat wees om jou Puff lêer te maak

412
00:35:17,400 --> 00:35:20,260
deur die redigering van hierdie makefile.

413
00:35:20,260 --> 00:35:22,730
Dit is omtrent dit vir ons verspreiding kode.

414
00:35:22,730 --> 00:35:28,380
>> Sodra ons gekry het deur daardie, dan is hier is net 'n herinnering

415
00:35:28,380 --> 00:35:30,980
van hoe ons gaan doen met die Huffman nodes.

416
00:35:30,980 --> 00:35:35,400
Ons gaan nie bel hulle nodes nie, ons gaan om te bel hulle bome

417
00:35:35,400 --> 00:35:39,260
waar ons gaan te word wat hul simbool met 'n char,

418
00:35:39,260 --> 00:35:43,340
hulle frekwensie, die aantal voorvalle, met 'n heelgetal.

419
00:35:43,340 --> 00:35:47,370
Wat ons gebruik, want dit is meer akkuraat is as 'n float.

420
00:35:47,370 --> 00:35:52,980
En dan het ons nog 'n wyser na die linker kind sowel as die regte kind.

421
00:35:52,980 --> 00:35:59,630
'N bos, soos ons gesien het, is net 'n geskakelde lys van bome.

422
00:35:59,630 --> 00:36:04,670
Uiteindelik, wanneer ons die opbou van ons Huff lêer,

423
00:36:04,670 --> 00:36:07,580
ons wil ons bos net 1 boom te bevat -

424
00:36:07,580 --> 00:36:12,420
1 boom, 1 wortel met verskeie kinders.

425
00:36:12,420 --> 00:36:20,840
Vroeër op wanneer ons net om ons Huffman bome,

426
00:36:20,840 --> 00:36:25,360
ons begin deur al die nodusse op ons skerm

427
00:36:25,360 --> 00:36:27,790
en gesê ons gaan hierdie nodes te hê,

428
00:36:27,790 --> 00:36:32,920
Uiteindelik het hulle gaan om die blare te wees, en dit is hul simbool, dit is hulle frekwensie.

429
00:36:32,920 --> 00:36:42,070
In ons bos as ons net 3 letters het, dis 'n bos van 3 bome.

430
00:36:42,070 --> 00:36:45,150
En dan as ons gaan, wanneer ons die eerste ouer bygevoeg,

431
00:36:45,150 --> 00:36:48,080
ons het 'n bos van 2 bome.

432
00:36:48,080 --> 00:36:54,930
Ons verwyder 2 van die kinders uit die bos en dan vervang dit met 'n ouer node

433
00:36:54,930 --> 00:36:58,820
wat die 2 nodes as kinders gehad het.

434
00:36:58,820 --> 00:37:05,600
En dan uiteindelik, ons laaste stap met die maak van ons 'n voorbeeld met die As, Bs, en Cs

435
00:37:05,600 --> 00:37:08,030
sou wees om die finale ouer te maak,

436
00:37:08,030 --> 00:37:13,190
en so dan sou dit bring ons totale telling van die bome in die bos tot 1.

437
00:37:13,190 --> 00:37:18,140
Nie almal sien hoe jy begin met verskeie bome in jou bos

438
00:37:18,140 --> 00:37:22,520
en eindig met 1? Okay. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Wat moet ons doen om vir Puff?

440
00:37:28,110 --> 00:37:37,110
Wat ons nodig het om te doen is om seker te maak dat, soos altyd, hulle gee ons die regte tipe van inset

441
00:37:37,110 --> 00:37:39,090
sodat ons kan eintlik loop die program.

442
00:37:39,090 --> 00:37:43,130
In hierdie geval is hulle gaan om te gee ons na hul eerste command-line argument

443
00:37:43,130 --> 00:37:53,440
2 meer: ​​die lêer wat ons wil decomprimeren en die uitset van die gedecomprimeerd lêer.

444
00:37:53,440 --> 00:38:00,410
Maar wanneer ons maak seker dat hulle slaag ons in die regte hoeveelheid van waardes,

445
00:38:00,410 --> 00:38:05,820
ons wil om te verseker dat die inset is 'n Huff lêer of nie.

446
00:38:05,820 --> 00:38:10,420
En dan wanneer ons waarborg dat dit is 'n Huff lêer, dan wil ons ons boom te bou,

447
00:38:10,420 --> 00:38:20,940
die opbou van die boom van so 'n aard dat dit ooreenstem met die boom wat die persoon wat die boodskap gestuur het gebou.

448
00:38:20,940 --> 00:38:25,840
Dan na ons bou die boom, dan kan ons hanteer die 0'e en 1s dat hulle geslaag het,

449
00:38:25,840 --> 00:38:29,590
volg wat langs ons boom omdat dit identies is,

450
00:38:29,590 --> 00:38:33,510
en skryf dan die boodskap uit, interpreteer die stukkies terug in die karakters.

451
00:38:33,510 --> 00:38:35,880
En dan aan die einde, want ons handel met wysers hier,

452
00:38:35,880 --> 00:38:38,110
ons wil hê om seker te maak dat ons nie enige geheue lekkasies

453
00:38:38,110 --> 00:38:41,330
en dat ons alles.

454
00:38:42,820 --> 00:38:46,430
>> Verseker korrekte gebruik is ou hoed vir ons deur die nou.

455
00:38:46,430 --> 00:38:51,980
Ons neem in 'n inset, wat gaan die naam van die lêer om te puff,

456
00:38:51,980 --> 00:38:56,010
en dan het ons 'n uitset spesifiseer,

457
00:38:56,010 --> 00:39:01,580
sodat die naam van die lêer vir die gepofte produksie, wat sal die tekslêer wees.

458
00:39:03,680 --> 00:39:08,820
Dit is gebruik. En nou is ons wil om te verseker dat die insette huffed of nie.

459
00:39:08,820 --> 00:39:16,420
Dink terug, was daar iets in die verspreiding-kode wat ons kan help

460
00:39:16,420 --> 00:39:21,570
met 'n begrip of 'n lêer huffed of nie?

461
00:39:21,570 --> 00:39:26,910
Daar is inligting in huffile.c oor die Huffeader.

462
00:39:26,910 --> 00:39:33,430
Ons weet dat elke Huff-lêer het 'n Huffeader wat daarmee geassosieer word met 'n magie nommer

463
00:39:33,430 --> 00:39:37,240
sowel as 'n verskeidenheid van die frekwensies vir elke simbool

464
00:39:37,240 --> 00:39:39,570
sowel as 'n checksum.

465
00:39:39,570 --> 00:39:43,180
Ons weet dat, maar ons het ook 'n blik op dump.c,

466
00:39:43,180 --> 00:39:49,120
waarin dit lees in 'n Huff-lêer.

467
00:39:49,120 --> 00:39:53,990
En so het dit te doen, dit het om te kyk of dit regtig is huffed of nie.

468
00:39:53,990 --> 00:40:03,380
So miskien kan ons gebruik as 'n struktuur vir ons puff.c. dump.c

469
00:40:03,380 --> 00:40:12,680
Terug na pset 4 toe ons die lêer copy.c wat gekopieer in RGB triples

470
00:40:12,680 --> 00:40:14,860
en ons verduidelik dat vir detective verhaal en Resize,

471
00:40:14,860 --> 00:40:20,390
insgelyks, is net wat jy kan doen voer die opdrag soos cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
en gebruik sommige van die kode daar.

473
00:40:23,600 --> 00:40:28,210
, Is dit egter nie so eenvoudig te wees van 'n proses

474
00:40:28,210 --> 00:40:33,010
vir die vertaling jou dump.c in puff.c,

475
00:40:33,010 --> 00:40:36,160
maar ten minste is dit gee jou iewers te begin

476
00:40:36,160 --> 00:40:40,540
oor hoe om te verseker dat die insette is eintlik huffed of nie

477
00:40:40,540 --> 00:40:43,240
sowel as 'n paar ander dinge.

478
00:40:45,930 --> 00:40:50,250
Ons het verseker behoorlike gebruik en verseker dat die insette huffed.

479
00:40:50,250 --> 00:40:53,570
Elke keer wat ons gedoen het dat ons behoorlike foutopsporing gedoen het,

480
00:40:53,570 --> 00:41:01,520
so terugkeer en ophou van die funksie as sommige versuim plaasvind, as daar 'n probleem is.

481
00:41:01,520 --> 00:41:07,170
>> Nou wat ons wil doen is om die bou van die werklike boom.

482
00:41:08,840 --> 00:41:12,640
As ons kyk in die Bos, is daar 2 belangrikste funksies

483
00:41:12,640 --> 00:41:15,800
dat ons gaan om te wil om 'n baie vertroud is met.

484
00:41:15,800 --> 00:41:23,870
Daar is die Boole-funksie plant dat plante 'n nie-0 frekwensie boom in ons bos.

485
00:41:23,870 --> 00:41:29,250
En so is daar jy slaag in 'n wyser na 'n bos en 'n wyser na 'n boom.

486
00:41:32,530 --> 00:41:40,340
Vinnige vraag: Hoeveel woude sal jy hê wanneer jy die bou van 'n Huffman boom?

487
00:41:44,210 --> 00:41:46,650
Ons bos is soos ons doek, reg?

488
00:41:46,650 --> 00:41:50,800
So gaan ons net 1 bos te hê, maar ons gaan verskeie bome te hê.

489
00:41:50,800 --> 00:41:57,590
Dus, voordat jy plant noem, is jy waarskynlik gaan om te wil jou bos te maak.

490
00:41:57,590 --> 00:42:04,430
Daar is 'n opdrag dat as jy kyk na forest.h oor hoe jy kan 'n bos maak.

491
00:42:04,430 --> 00:42:09,270
Jy kan 'n boom plant. Ons weet hoe om dit te doen.

492
00:42:09,270 --> 00:42:11,590
En dan kan jy ook kies 'n boom uit die bos,

493
00:42:11,590 --> 00:42:17,540
die verwydering van 'n boom met die laagste gewig en gee jou die wyser na daardie.

494
00:42:17,540 --> 00:42:23,090
Dink terug aan toe ons besig was om die voorbeelde wat onsself,

495
00:42:23,090 --> 00:42:27,980
wanneer ons dit te teken, het ons eenvoudig net die skakels bygevoeg.

496
00:42:27,980 --> 00:42:31,680
Maar hier in plaas van net die toevoeging van die skakels,

497
00:42:31,680 --> 00:42:40,630
dink dit meer as jy 2 van daardie nodes is die verwydering en dan dit te vervang deur 'n ander een.

498
00:42:40,630 --> 00:42:44,200
Uit te druk in terme van die pluk en te plant,

499
00:42:44,200 --> 00:42:48,840
jy pluk 2 bome en dan ander boom te plant

500
00:42:48,840 --> 00:42:54,060
wat die 2 bome wat jy opgetel het as kinders.

501
00:42:57,950 --> 00:43:05,280
Huffman se boom op te bou, kan jy lees in die simbole en frekwensies ten einde

502
00:43:05,280 --> 00:43:10,790
omdat die Huffeader gee wat aan u,

503
00:43:10,790 --> 00:43:14,250
gee jou 'n verskeidenheid van die frekwensies.

504
00:43:14,250 --> 00:43:19,660
Sodat jy kan gaan voort en ignoreer maar net enigiets met die 0

505
00:43:19,660 --> 00:43:23,760
want ons wil nie 256 blare aan die einde van dit.

506
00:43:23,760 --> 00:43:27,960
Ons wil net die aantal blare wat karakters

507
00:43:27,960 --> 00:43:31,600
wat werklik gebruik word in die lêer.

508
00:43:31,600 --> 00:43:37,590
Jy kan lees in die simbole, en elk van die simbole wat nie-0 frekwensies,

509
00:43:37,590 --> 00:43:40,440
dié gaan wees bome.

510
00:43:40,440 --> 00:43:45,990
Wat jy kan doen, is elke keer as jy lees in 'n nie-0 frekwensie simbool,

511
00:43:45,990 --> 00:43:50,660
jy kan plant daardie boom in die bos.

512
00:43:50,660 --> 00:43:56,620
Sodra jy plant die bome in die bos, kan jy saam met die bome as broers en susters,

513
00:43:56,620 --> 00:44:01,130
so terug te gaan na plant en pluk waar jy kies 2 en dan plant 1,

514
00:44:01,130 --> 00:44:05,820
waar dat die 1 wat jy plant is die ouer van die 2 kinders wat jy opgetel het.

515
00:44:05,820 --> 00:44:11,160
So dan is jou eindresultaat is gaan na 'n enkele boom in jou bos te wees.

516
00:44:16,180 --> 00:44:18,170
Dit is hoe jy jou boom te bou.

517
00:44:18,170 --> 00:44:21,850
>> Daar is 'n paar dinge wat kon verkeerd gaan hier

518
00:44:21,850 --> 00:44:26,580
omdat ons te doen het met die maak van nuwe bome en die hantering met wenke en dinge soos dat.

519
00:44:26,580 --> 00:44:30,450
Voordat wanneer ons te doen het met pointers,

520
00:44:30,450 --> 00:44:36,580
wanneer ons malloc'd ons wou om seker te maak dat dit nie terug vir ons 'n NULL pointer waarde.

521
00:44:36,580 --> 00:44:42,770
So op verskeie stappe in hierdie proses is daar gaan wees verskeie gevalle

522
00:44:42,770 --> 00:44:45,920
waar jou program kan misluk.

523
00:44:45,920 --> 00:44:51,310
Wat jy wil doen, is wat jy wil om seker te maak dat jy die foute hanteer,

524
00:44:51,310 --> 00:44:54,580
en in die spec dit sê hulle om grasieus te hanteer,

525
00:44:54,580 --> 00:45:00,280
so graag 'n boodskap aan die gebruiker druk vertel hulle waarom die program het om op te hou

526
00:45:00,280 --> 00:45:03,050
en dan stop dit dadelik.

527
00:45:03,050 --> 00:45:09,490
Hierdie fout hantering om te doen, onthou dat jy dit wil hê om seker te maak

528
00:45:09,490 --> 00:45:12,160
elke keer dat daar 'n mislukking te wees.

529
00:45:12,160 --> 00:45:14,660
Elke keer wat jy maak 'n nuwe pointer

530
00:45:14,660 --> 00:45:17,040
jy wil om seker te maak dat suksesvolle.

531
00:45:17,040 --> 00:45:20,320
Voor wat ons gebruik om te doen, is om 'n nuwe wyser en malloc dit maak,

532
00:45:20,320 --> 00:45:22,380
en dan sou ons kontroleer of dat die wyser is NULL.

533
00:45:22,380 --> 00:45:25,670
So daar gaan 'n paar gevalle waar jy kan net dit doen,

534
00:45:25,670 --> 00:45:28,610
maar soms is jy eintlik die roeping van 'n funksie

535
00:45:28,610 --> 00:45:33,100
en binne daardie funksie, wat is die een wat die mallocing doen.

536
00:45:33,100 --> 00:45:39,110
In daardie geval, as ons terugkyk na sommige van die funksies in die kode,

537
00:45:39,110 --> 00:45:42,260
sommige van hulle is Boole-funksies.

538
00:45:42,260 --> 00:45:48,480
In die abstrakte geval as ons 'n Boole-funksie genoem foo,

539
00:45:48,480 --> 00:45:54,580
basies, kan ons aanneem dat benewens om te doen alles wat foo doen,

540
00:45:54,580 --> 00:45:57,210
want dit is 'n Boole-funksie, is dit terug waar of onwaar -

541
00:45:57,210 --> 00:46:01,300
ware indien suksesvol, valse indien nie.

542
00:46:01,300 --> 00:46:06,270
So ons wil om te kontroleer of die terugkeer waarde van foo is waar of onwaar is.

543
00:46:06,270 --> 00:46:10,400
As dit vals is, dit beteken dat ons gaan om te wil 'n soort van 'n boodskap te druk

544
00:46:10,400 --> 00:46:14,390
en dan sluit die program.

545
00:46:14,390 --> 00:46:18,530
Wat ons wil doen, is kyk na die terugkeer waarde van cat.

546
00:46:18,530 --> 00:46:23,310
As foo terugkeer vals is, dan weet ons dat ons 'n soort van fout teëgekom

547
00:46:23,310 --> 00:46:25,110
en ons moet ons program om op te hou.

548
00:46:25,110 --> 00:46:35,600
'N manier om dit te doen is 'n toestand waar die werklike funksie self is jou toestand.

549
00:46:35,600 --> 00:46:39,320
Sê foo neem in x.

550
00:46:39,320 --> 00:46:43,390
Ons kan as 'n voorwaarde as (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Basies, wat beteken dat aan die einde van die uitvoering van foo dit terug waar,

552
00:46:50,900 --> 00:46:57,390
dan kan ons doen dit omdat die funksie het foo te evalueer

553
00:46:57,390 --> 00:47:00,500
ten einde die hele toestand te evalueer.

554
00:47:00,500 --> 00:47:06,500
So dan is dit hoe jy iets kan doen indien die funksie gee waar en suksesvol is.

555
00:47:06,500 --> 00:47:11,800
Maar wanneer jy foutopsporing, jy wil net om op te hou as jou funksie gee vals.

556
00:47:11,800 --> 00:47:16,090
Wat jy kan doen is net voeg 'n == vals of voeg net 'n slag in die voorkant van dit

557
00:47:16,090 --> 00:47:21,010
en dan moet jy if (! foo).

558
00:47:21,010 --> 00:47:29,540
Binne daardie liggaam van daardie toestand wat jy wil hê van die fout hantering,

559
00:47:29,540 --> 00:47:36,940
so wil hê, "Kon nie hierdie boom" en dan terug 1 of iets soos dit.

560
00:47:36,940 --> 00:47:43,340
Wat dit doen, al is, is dat selfs al foo teruggekeer valse -

561
00:47:43,340 --> 00:47:46,980
Sê foo terugkeer ware.

562
00:47:46,980 --> 00:47:51,060
Dan hoef jy nie foo weer bel. Dit is 'n algemene wanopvatting.

563
00:47:51,060 --> 00:47:54,730
Want dit was in jou toestand, dit reeds geëvalueer,

564
00:47:54,730 --> 00:47:59,430
sodat jy het reeds die resultaat as jy gebruik maak boom of iets soos dit

565
00:47:59,430 --> 00:48:01,840
of plant of pick of iets.

566
00:48:01,840 --> 00:48:07,460
Dit het reeds daardie waarde. Dit is reeds uitgevoer.

567
00:48:07,460 --> 00:48:10,730
So dit is nuttig Boole-funksies te gebruik as die toestand

568
00:48:10,730 --> 00:48:13,890
want of jy nie eintlik die liggaam van die lus uitvoer,

569
00:48:13,890 --> 00:48:18,030
Dit voer die funksie in elk geval.

570
00:48:22,070 --> 00:48:27,330
>> Ons tweede laaste stap is om die boodskap te skryf na die lêer.

571
00:48:27,330 --> 00:48:33,070
Sodra ons die bou van die Huffman boom, dan skryf die boodskap na die lêer is redelik eenvoudig.

572
00:48:33,070 --> 00:48:39,260
Dit is redelik eenvoudig nou net volg die 0'e en 1s.

573
00:48:39,260 --> 00:48:45,480
En so deur konvensie ons weet dat die 0'e dui in 'n Huffman boom links

574
00:48:45,480 --> 00:48:48,360
en die 1s dui reg.

575
00:48:48,360 --> 00:48:53,540
Daarom dan, as jy lees bietjie vir bietjie, elke keer dat jy 'n 0

576
00:48:53,540 --> 00:48:59,100
jy volg die linker-tak, en dan elke keer wat jy lees in 'n 1

577
00:48:59,100 --> 00:49:02,100
jy gaan die regte tak te volg.

578
00:49:02,100 --> 00:49:07,570
En dan is jy gaan om voort te gaan totdat jy getref 'n blaar

579
00:49:07,570 --> 00:49:11,550
omdat die blare gaan word aan die einde van die takke.

580
00:49:11,550 --> 00:49:16,870
Hoe kan ons vertel of ons het 'n blaar of nie getref?

581
00:49:19,800 --> 00:49:21,690
Ons het gesê dit voor.

582
00:49:21,690 --> 00:49:24,040
[Student] As die verwysings is NULL. >> Ja.

583
00:49:24,040 --> 00:49:32,220
Ons kan sê as ons 'n blaar getref het as die verwysings na beide die linker en regter bome is NULL.

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

585
00:49:34,110 --> 00:49:40,320
Ons weet wat ons wil lees bietjie vir bietjie in ons Huff lêer.

586
00:49:43,870 --> 00:49:51,220
Soos ons gesien het voor in dump.c, wat hulle gedoen het, is hulle lees bietjie vir bietjie in die Huff-lêer

587
00:49:51,220 --> 00:49:54,560
en net gedruk wat daardie stukkies was.

588
00:49:54,560 --> 00:49:58,430
Ons is nie van plan om dit te doen. Ons gaan te wees om iets te doen wat 'n bietjie meer kompleks is.

589
00:49:58,430 --> 00:50:03,620
Maar wat ons kan doen is wat ons kan neem dat die bietjie van die kode wat in die stuk lees.

590
00:50:03,620 --> 00:50:10,250
Hier het ons die integer bietjie wat die huidige bietjie dat ons op.

591
00:50:10,250 --> 00:50:15,520
Dit sorg iterating al die stukkies in die lêer totdat jy getref die einde van die lêer.

592
00:50:15,520 --> 00:50:21,270
Gebaseer op dat, dan is jy gaan om te wil 'n soort van Iterator

593
00:50:21,270 --> 00:50:26,760
jou boom te verken.

594
00:50:26,760 --> 00:50:31,460
En dan gebaseer op of die bietjie 0 of 1,

595
00:50:31,460 --> 00:50:36,920
jy gaan hê om óf dat Iterator skuif na links of na regs beweeg

596
00:50:36,920 --> 00:50:44,080
al die pad tot jy 'n blaar getref, sodat al die pad tot op daardie node dat jy op

597
00:50:44,080 --> 00:50:48,260
nie wys nie meer nodes.

598
00:50:48,260 --> 00:50:54,300
Hoekom kan ons dit doen met 'n Huffman lêer, maar nie Morsekode?

599
00:50:54,300 --> 00:50:56,610
Want in Morsekode is daar is 'n bietjie van dubbelsinnigheid.

600
00:50:56,610 --> 00:51:04,440
Ons kon wees, oh wag, het ons 'n letter langs die pad getref het, so miskien is dit is ons brief,

601
00:51:04,440 --> 00:51:08,150
terwyl as ons voortgegaan om net 'n bietjie meer, dan sou ons getref het 'n ander brief.

602
00:51:08,150 --> 00:51:13,110
Maar dit is nie gaan gebeur in Huffman kodering,

603
00:51:13,110 --> 00:51:17,540
sodat ons kan verseker wees dat die enigste manier waarop ons gaan om 'n karakter te tref

604
00:51:17,540 --> 00:51:23,480
is indien daardie node se links en regs kinders NULL.

605
00:51:28,280 --> 00:51:32,350
>> Ten slotte, ons wil al ons geheue te bevry.

606
00:51:32,350 --> 00:51:37,420
Ons wil aan beide naby die Huff lêer wat ons het is die hantering van

607
00:51:37,420 --> 00:51:41,940
sowel as al die bome in die bos verwyder.

608
00:51:41,940 --> 00:51:46,470
Gebaseer op jou implementering, jy is waarskynlik gaan om te wil om te bel bos verwyder

609
00:51:46,470 --> 00:51:49,780
in plaas van eintlik gaan deur al die bome self.

610
00:51:49,780 --> 00:51:53,430
Maar as jy enige tydelike bome, wil jy te bevry.

611
00:51:53,430 --> 00:51:59,060
Jy weet jou kode die beste, sodat jy weet waar jy die toekenning van geheue.

612
00:51:59,060 --> 00:52:04,330
En so, as jy gaan, begin deur selfs beheer F'ing vir malloc,

613
00:52:04,330 --> 00:52:08,330
sien wanneer jy malloc en maak seker dat jy vry om al van daardie

614
00:52:08,330 --> 00:52:10,190
maar dan net gaan deur jou kode,

615
00:52:10,190 --> 00:52:14,260
begrip van waar jy kan geheue toegeken het.

616
00:52:14,260 --> 00:52:21,340
Gewoonlik kan jy net sê: "Aan die einde van 'n lêer is ek net gaan op my bos bos te verwyder,"

617
00:52:21,340 --> 00:52:23,850
so basies duidelik dat die geheue, gratis,

618
00:52:23,850 --> 00:52:28,310
"En dan het ek ook gaan om die lêer te sluit en dan my program gaan om op te hou."

619
00:52:28,310 --> 00:52:33,810
Maar is dit die enigste keer dat jou program verlaat?

620
00:52:33,810 --> 00:52:37,880
Nee, want soms is daar kon gewees het 'n fout wat gebeur het.

621
00:52:37,880 --> 00:52:42,080
Miskien kan ons nie 'n lêer oopmaak of ons kon nie 'n ander boom

622
00:52:42,080 --> 00:52:49,340
of 'n soort van fout in die geheue toekenning proses gebeur en daarom is dit het NUL teruggestuur.

623
00:52:49,340 --> 00:52:56,710
'N Fout het gebeur en dan is ons terug en stop.

624
00:52:56,710 --> 00:53:02,040
So is julle dan wil hê om seker te maak dat enige moontlike tyd dat jou program kan ophou,

625
00:53:02,040 --> 00:53:06,980
jy wil al jou geheue om daar te bevry.

626
00:53:06,980 --> 00:53:13,370
Dit is nie net gaan aan die einde van die hooffunksie dat jy ophou om jou kode te wees.

627
00:53:13,370 --> 00:53:20,780
Jy wil om terug te kyk na elke geval dat jou kode potensieel kan vroeg terug

628
00:53:20,780 --> 00:53:25,070
en dan vry watter geheue sin maak.

629
00:53:25,070 --> 00:53:30,830
Sê jy het 'n beroep maak bos en teruggekom het vals.

630
00:53:30,830 --> 00:53:34,230
Dan sal jy waarskynlik nie nodig om jou bos te verwyder

631
00:53:34,230 --> 00:53:37,080
want jy het nie 'n bos nie.

632
00:53:37,080 --> 00:53:42,130
Maar by elke punt in die kode waar jy kan vroeg terug

633
00:53:42,130 --> 00:53:46,160
jy wil om seker te maak dat jy vry om enige moontlike geheue.

634
00:53:46,160 --> 00:53:50,020
>> So wanneer ons te doen het met bevry geheue en met moontlike lekkasies,

635
00:53:50,020 --> 00:53:55,440
ons wil nie net gebruik maak van ons oordeel en ons logika

636
00:53:55,440 --> 00:54:01,850
maar ook gebruik om Valgrind te bepaal of ons al ons geheue behoorlik bevry het of nie.

637
00:54:01,850 --> 00:54:09,460
Jy kan een Valgrind op Puff en dan het jy ook dit slaag

638
00:54:09,460 --> 00:54:14,020
die regte hoeveelheid van command-line argumente te Valgrind.

639
00:54:14,020 --> 00:54:18,100
Jy kan hardloop, maar die uitset is 'n bietjie kripties.

640
00:54:18,100 --> 00:54:21,630
Ons het 'n bietjie wat gebruik word om dit met Speller gekry, maar ons het nog 'n bietjie meer hulp nodig het,

641
00:54:21,630 --> 00:54:26,450
so dan loop dit met 'n paar vlae soos die lek-check = volle,

642
00:54:26,450 --> 00:54:32,040
wat sal waarskynlik gee ons 'n paar meer nuttig uitset op Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Nog 'n nuttige wenk wanneer jy ontfouting is die diff opdrag.

644
00:54:39,040 --> 00:54:48,520
Jy kan toegang tot die personeel se implementering van Huff, hardloop dat 'n tekslêer,

645
00:54:48,520 --> 00:54:55,400
en dan uitvoer om dit te 'n binêre lêer, 'n binêre Huff lêer, om meer spesifiek te wees.

646
00:54:55,400 --> 00:54:59,440
Dan as jy jou eie puff op daardie binêre lêer,

647
00:54:59,440 --> 00:55:03,950
dan ideaal is jou outputted tekslêer gaan identies wees

648
00:55:03,950 --> 00:55:08,200
na die oorspronklike een wat jy geslaag het.

649
00:55:08,200 --> 00:55:15,150
Hier is ek met behulp van hth.txt as die voorbeeld, en dit is die een wat gepraat oor in jou spec.

650
00:55:15,150 --> 00:55:21,040
Dit is letterlik net HTH en dan 'n newline.

651
00:55:21,040 --> 00:55:30,970
Maar beslis voel vry en jy is beslis aangemoedig om meer voorbeelde te gebruik

652
00:55:30,970 --> 00:55:32,620
vir jou teks lêer.

653
00:55:32,620 --> 00:55:38,110
>> Jy kan selfs 'n kans op die miskien comprimeren en dan decompressie

654
00:55:38,110 --> 00:55:41,600
sommige van die lêers wat jy gebruik in Speller soos oorlog en vrede

655
00:55:41,600 --> 00:55:46,710
of Jane Austen of iets soos dit - dit sal gaaf wees - of Austin Powers,

656
00:55:46,710 --> 00:55:51,880
soort van die hantering van groter lêers, want ons sal nie afkom om dit

657
00:55:51,880 --> 00:55:55,590
as ons die volgende hulpmiddel hier, ls-l gebruik.

658
00:55:55,590 --> 00:56:01,150
Ons kan gebruik om ls, wat basies al die inhoud lys in ons huidige gids.

659
00:56:01,150 --> 00:56:07,860
Wat in die vlag-l vertoon eintlik die grootte van die lêers.

660
00:56:07,860 --> 00:56:12,690
As jy gaan deur die pset spec, dit loop jy eintlik deur die skep van die binêre lêer,

661
00:56:12,690 --> 00:56:16,590
hijgen dit, en jy sien dat vir baie klein lêers

662
00:56:16,590 --> 00:56:23,910
die ruimte koste van die comprimeren en die vertaling van al die inligting

663
00:56:23,910 --> 00:56:26,980
van al die frekwensies en dinge soos wat swaarder weeg as die werklike voordeel

664
00:56:26,980 --> 00:56:30,000
van die comprimeren van die lêer in die eerste plek.

665
00:56:30,000 --> 00:56:37,450
Maar as u hardloop en dit op 'n paar langer teks lêers, dan moet jy kan sien dat jy begin om voordeel te kry

666
00:56:37,450 --> 00:56:40,930
in die comprimeren van die lêers.

667
00:56:40,930 --> 00:56:46,210
>> En dan uiteindelik, ons het ons ou pal GDB, wat is beslis gaan om te kom handig te pas.

668
00:56:48,360 --> 00:56:55,320
>> Het ons enige vrae oor Huff bome of die proses miskien van die maak van die bome

669
00:56:55,320 --> 00:56:58,590
of enige ander vrae oor Huff'n Puff?

670
00:57:00,680 --> 00:57:02,570
Okay. Ek sal bly vir 'n bietjie rond.

671
00:57:02,570 --> 00:57:06,570
>> Dankie, almal. Dit was Walk Through 6. En 'n goeie geluk.

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