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

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

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

4
00:00:07,240 --> 00:00:12,180
>> Hallo, iedereen, en welkom bij Walkthrough 6: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
In Huff'n Puff wat we doen gaat te maken met een Huffman gecomprimeerd bestand

6
00:00:17,440 --> 00:00:20,740
en dan puffen het back-up, dus decomprimeren,

7
00:00:20,740 --> 00:00:25,810
zodat wij kunnen vertalen van de 0s en 1s dat de gebruiker stuurt ons

8
00:00:25,810 --> 00:00:30,660
en het omzetten terug in de oorspronkelijke tekst.

9
00:00:30,660 --> 00:00:34,360
Pset 6 gaat worden wel cool, want je gaat een aantal van de gereedschappen te zien

10
00:00:34,360 --> 00:00:41,730
die u hebt gebruikt in PSET 4 en PSET 5 en soort van ze te combineren in een vrij netjes begrip

11
00:00:41,730 --> 00:00:43,830
wanneer kom je over na te denken.

12
00:00:43,830 --> 00:00:50,110
>> Ook, misschien wel, PSET 4 en 5 waren de meest uitdagende psets die we te bieden had.

13
00:00:50,110 --> 00:00:53,950
Dus vanaf nu, we hebben dit nog 1 PSET in C,

14
00:00:53,950 --> 00:00:56,480
en dan na dat we op naar web programmeren.

15
00:00:56,480 --> 00:01:02,310
Dus feliciteren jezelf voor het krijgen van meer dan de zwaarste bult in CS50.

16
00:01:03,630 --> 00:01:09,760
>> Moving on voor Huff'n Puff, zijn onze toolbox voor deze PSET gaat worden Huffman bomen,

17
00:01:09,760 --> 00:01:14,700
dus begrijpen niet alleen hoe binaire bomen werken, maar ook specifiek Huffman bomen,

18
00:01:14,700 --> 00:01:16,240
hoe ze gebouwd.

19
00:01:16,240 --> 00:01:20,210
En dan gaan we een heleboel verdeelsleutel hebben in deze PSET,

20
00:01:20,210 --> 00:01:22,480
en we komen om dat daadwerkelijk te zien een aantal van de code

21
00:01:22,480 --> 00:01:24,670
we misschien niet in staat zijn om volledig te begrijpen nog,

22
00:01:24,670 --> 00:01:30,080
en dus die zal de. c bestanden, maar dan is hun bijbehorende. h-bestanden

23
00:01:30,080 --> 00:01:34,300
geeft ons genoeg begrip dat we nodig hebben, zodat we weten hoe deze functies werken

24
00:01:34,300 --> 00:01:38,100
of in ieder geval wat ze moeten doen - hun in-en uitgangen -

25
00:01:38,100 --> 00:01:40,760
zelfs als we niet weten wat er gebeurt in de zwarte doos

26
00:01:40,760 --> 00:01:44,090
of niet begrijpen wat er gebeurt in de zwarte doos binnen.

27
00:01:44,090 --> 00:01:49,400
En dan tot slot, zoals gewoonlijk, hebben we te maken met nieuwe data structuren,

28
00:01:49,400 --> 00:01:51,840
specifieke soorten knooppunten die wijzen op bepaalde dingen,

29
00:01:51,840 --> 00:01:56,080
en dus even met een pen en papier, niet alleen voor het ontwerp-proces

30
00:01:56,080 --> 00:01:58,470
en als je probeert te achterhalen hoe je PSET zou moeten werken

31
00:01:58,470 --> 00:02:00,520
maar ook tijdens debuggen.

32
00:02:00,520 --> 00:02:06,140
U kunt GDB naast uw pen en papier terwijl u op wat de waarden zijn,

33
00:02:06,140 --> 00:02:09,320
waar je pijltjes wijzen, en dat soort dingen.

34
00:02:09,320 --> 00:02:13,720
>> Laten we eerst eens kijken naar Huffman bomen.

35
00:02:13,720 --> 00:02:19,600
Huffman bomen zijn binaire bomen, wat betekent dat elke node slechts 2 kinderen heeft.

36
00:02:19,600 --> 00:02:24,870
In Huffman bomen het kenmerk is dat de meest voorkomende waarden

37
00:02:24,870 --> 00:02:27,140
worden vertegenwoordigd door de minst bits.

38
00:02:27,140 --> 00:02:32,690
We zagen in collegezaal voorbeelden van Morse-code, wat voor soort geconsolideerde sommige brieven.

39
00:02:32,690 --> 00:02:38,030
Als je probeert om een ​​A of een E, bijvoorbeeld vertalen,

40
00:02:38,030 --> 00:02:43,940
je die vaak vertalen, dus in plaats van het hebben van de volledige set van bits te gebruiken

41
00:02:43,940 --> 00:02:48,640
toegewezen voor die gebruikelijke data type, dat u comprimeren tot minder,

42
00:02:48,640 --> 00:02:53,730
en dan die brieven die worden vertegenwoordigd minder vaak worden weergegeven met een langere stukjes

43
00:02:53,730 --> 00:02:59,840
want je kunt veroorloven dat wanneer je weegt de frequenties die die brieven verschijnen.

44
00:02:59,840 --> 00:03:03,020
We hebben hetzelfde idee hier in Huffman bomen

45
00:03:03,020 --> 00:03:12,360
waar we het maken van een ketting, een soort pad om naar de bepaalde tekens.

46
00:03:12,360 --> 00:03:14,470
En dan de personages die het meest frequentie

47
00:03:14,470 --> 00:03:17,940
zullen worden weergegeven met de minste bits.

48
00:03:17,940 --> 00:03:22,020
>> De manier waarop u een Huffman boom te construeren

49
00:03:22,020 --> 00:03:27,430
is door het plaatsen van alle tekens die worden weergegeven in de tekst

50
00:03:27,430 --> 00:03:30,630
en het berekenen van de frequentie, hoe vaak ze verschijnen.

51
00:03:30,630 --> 00:03:33,880
Dit kan ofwel een telling van het aantal keren dat die brieven verschijnen

52
00:03:33,880 --> 00:03:40,270
of misschien een percentage van alle tekens hoeveel elk weergegeven.

53
00:03:40,270 --> 00:03:44,270
En dus wat je doet is als je eenmaal dat alles in kaart gebracht hebben,

54
00:03:44,270 --> 00:03:49,060
dan kijk je voor de 2 laagste frequenties en vervolgens hen te voegen als broers en zussen

55
00:03:49,060 --> 00:03:55,660
waarbij dan het ouderknooppunt een frequentie die de som is van de twee kinderen.

56
00:03:55,660 --> 00:04:00,870
En dan moet je volgens afspraak zeggen dat de linker knooppunt,

57
00:04:00,870 --> 00:04:03,770
volg je dat door het volgen van de 0 tak,

58
00:04:03,770 --> 00:04:08,140
en dan de meest rechtse knooppunt is de 1 tak.

59
00:04:08,140 --> 00:04:16,040
Zoals we zagen in Morse-code, de een gotcha was dat als je had gewoon een pieptoon en de pieptoon

60
00:04:16,040 --> 00:04:18,120
het was dubbelzinnig.

61
00:04:18,120 --> 00:04:22,430
Het kan ofwel een letter of het kan een sequentie van twee letters.

62
00:04:22,430 --> 00:04:27,790
En dus wat Huffman bomen doet is omdat door de aard van de personages

63
00:04:27,790 --> 00:04:34,140
of onze laatste feitelijke tekens als laatste knopen op de tak -

64
00:04:34,140 --> 00:04:39,300
we verwijzen naar die als bladeren - op grond van dat er geen sprake zijn van dubbelzinnigheid

65
00:04:39,300 --> 00:04:45,160
in termen van welke letter die u zoekt coderen met de reeks van bits

66
00:04:45,160 --> 00:04:50,670
want nergens langs de bits die 1 letter vertegenwoordigen

67
00:04:50,670 --> 00:04:55,960
komt u nog een hele brief, en er zal niet er enige verwarring.

68
00:04:55,960 --> 00:04:58,430
Maar we zullen ingaan op voorbeelden die jullie daadwerkelijk kan zien dat

69
00:04:58,430 --> 00:05:02,120
in plaats van ons alleen maar te vertellen dat dat waar is.

70
00:05:02,120 --> 00:05:06,390
>> Laten we eens kijken naar een eenvoudig voorbeeld van een Huffman boom.

71
00:05:06,390 --> 00:05:09,380
Ik heb een string hier dat is 12 tekens lang zijn.

72
00:05:09,380 --> 00:05:14,010
Ik heb 4 Zoals, 6 B's, en 2 Cs.

73
00:05:14,010 --> 00:05:17,270
Mijn eerste stap zou zijn om te tellen.

74
00:05:17,270 --> 00:05:20,760
Hoe vaak doet A verschijnen? Het verschijnt 4 keer in de string.

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

76
00:05:25,060 --> 00:05:28,970
Natuurlijk, ik ga zeggen dat ik B met behulp van het meest,

77
00:05:28,970 --> 00:05:35,970
dus ik wil B vertegenwoordigen met het minste aantal bits, het laagste aantal van 0s en 1s.

78
00:05:35,970 --> 00:05:42,600
En dan ga ik ook gaan verwachten C om de meest bedrag van 0s en 1s nodig ook.

79
00:05:42,600 --> 00:05:48,550
Eerste wat ik hier heb is dat ik plaatste ze in oplopende volgorde in termen van frequentie.

80
00:05:48,550 --> 00:05:52,710
We zien dat de C en de A, dat zijn onze 2 laagste frequenties.

81
00:05:52,710 --> 00:06:00,290
We creëren een parent node, en die ouder knooppunt niet over een brief die ermee verbonden zijn,

82
00:06:00,290 --> 00:06:05,070
maar wel een frequentie, die de som is.

83
00:06:05,070 --> 00:06:08,780
De som wordt 2 + 4, op 6.

84
00:06:08,780 --> 00:06:10,800
Daarna volgen we de linker tak.

85
00:06:10,800 --> 00:06:14,970
Als we op dat 6 knooppunt, dan zouden we volgen op 0 om C

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

87
00:06:17,450 --> 00:06:20,300
Dus nu hebben we 2 knopen.

88
00:06:20,300 --> 00:06:23,920
Wij hebben de waarde 6 en dan hebben we ook een ander knooppunt met de waarde 6.

89
00:06:23,920 --> 00:06:28,550
Enz. die 2 niet alleen de laagste twee maar alleen de 2 die links,

90
00:06:28,550 --> 00:06:33,820
dus we sluiten die door een andere ouder, waarbij de som wordt 12.

91
00:06:33,820 --> 00:06:36,300
Hier hebben we dus onze Huffman boom

92
00:06:36,300 --> 00:06:40,020
waar te krijgen naar B, dan zou dat wel eens de bit 1

93
00:06:40,020 --> 00:06:45,430
en dan om naar A zouden we 01 en vervolgens C met 00.

94
00:06:45,430 --> 00:06:51,300
Dus hier zien we dat in feite dat we deze chars die met 1 of 2 bits

95
00:06:51,300 --> 00:06:55,160
waarbij de B, zoals voorspeld, de minste.

96
00:06:55,160 --> 00:07:01,730
En dan we hadden verwacht C om het meeste hebben, maar omdat het zo'n klein Huffman boom,

97
00:07:01,730 --> 00:07:06,020
vervolgens de A eveneens door 2 bits tegenover ergens in het midden.

98
00:07:07,820 --> 00:07:11,070
>> Gewoon om te gaan over een ander eenvoudig voorbeeld van de Huffman boom,

99
00:07:11,070 --> 00:07:19,570
zeggen dat je de string "Hallo."

100
00:07:19,570 --> 00:07:25,360
Wat je doet is eerst je zou zeggen hoe vaak heeft H verschijnt in dit?

101
00:07:25,360 --> 00:07:34,200
H verschijnt een keer en dan e verschijnt een keer en dan hebben we l verschijnen twee keer

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

103
00:07:36,580 --> 00:07:44,310
En zo is dan we verwachten welke letter te laten vertegenwoordigen door de minst aantal bits?

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

105
00:07:47,450 --> 00:07:50,730
We verwachten l worden vertegenwoordigd door het minste aantal bits

106
00:07:50,730 --> 00:07:55,890
omdat ik het meest gebruikt in de string "Hallo."

107
00:07:55,890 --> 00:08:04,280
Wat ik nu ga doen is trekken uit deze knooppunten.

108
00:08:04,280 --> 00:08:15,580
Ik heb 1, dat H, en dan nog 1, dat e en een 1, dat o -

109
00:08:15,580 --> 00:08:23,410
nu ben ik ze in volgorde - en dan 2, dat is l.

110
00:08:23,410 --> 00:08:32,799
Dan zeg ik de manier waarop ik een Huffman boom te bouwen is het vinden van de 2 nodes met de minste frequenties

111
00:08:32,799 --> 00:08:38,010
en maken ze broers en zussen door een bovenliggende node.

112
00:08:38,010 --> 00:08:41,850
Hier hebben we 3 knopen met de laagste frequentie. Ze zijn allemaal 1.

113
00:08:41,850 --> 00:08:50,620
Dus hier zijn we kiezen welke we gaan eerst koppelen.

114
00:08:50,620 --> 00:08:54,850
Laten we zeggen dat ik de H en de e.

115
00:08:54,850 --> 00:09:01,150
De som van 1 + 1 is 2, maar dit knooppunt geen brief gekoppeld.

116
00:09:01,150 --> 00:09:04,440
Het houdt alleen de waarde.

117
00:09:04,440 --> 00:09:10,950
Nu gaan we kijken naar de volgende 2 laagste frequenties.

118
00:09:10,950 --> 00:09:15,590
Dat is 2 en 1. Dat zou een van deze twee zijn, maar ik ga dit een te kiezen.

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

120
00:09:18,800 --> 00:09:26,410
En dan tot slot, ik heb maar 2 links, dus dan dat wordt 5.

121
00:09:26,410 --> 00:09:32,010
Dan hier, zoals verwacht, als ik vul de codering voor,

122
00:09:32,010 --> 00:09:37,480
1s zijn altijd de juiste tak en 0s zijn de linker.

123
00:09:37,480 --> 00:09:45,880
Dan hebben we l vertegenwoordigd door slechts 1 bit en vervolgens de o met 2

124
00:09:45,880 --> 00:09:52,360
en de e met 2 en de H valt tot 3 bits.

125
00:09:52,360 --> 00:09:59,750
Dus u kan overbrengen dit bericht "Hello" in plaats van het daadwerkelijk gebruik van de tekens

126
00:09:59,750 --> 00:10:02,760
door gewoon 0s en 1s.

127
00:10:02,760 --> 00:10:07,910
Vergeet echter niet dat in een aantal gevallen hebben we banden met onze frequentie had.

128
00:10:07,910 --> 00:10:11,900
We konden beide hebben zich aangesloten bij de H en de o eerste misschien.

129
00:10:11,900 --> 00:10:15,730
Of later op toen we de l vertegenwoordigd door 2

130
00:10:15,730 --> 00:10:19,410
en de samengevoegde dat voorgesteld door 2, kan ofwel een we hebben verbonden.

131
00:10:19,410 --> 00:10:23,630
>> En dus, wanneer u een van de 0s en 1s, die eigenlijk geen garantie

132
00:10:23,630 --> 00:10:27,090
dat de ontvanger kan uw bericht volledig te lezen recht uit de vleermuis

133
00:10:27,090 --> 00:10:30,490
omdat ze misschien niet weten welke beslissing je hebt gemaakt.

134
00:10:30,490 --> 00:10:34,920
Dus als we te maken hebben met Huffman compressie,

135
00:10:34,920 --> 00:10:40,090
een of andere manier moeten we de ontvanger van onze boodschap hoe we besloten te vertellen -

136
00:10:40,090 --> 00:10:43,470
Ze moeten een soort van extra informatie te kennen

137
00:10:43,470 --> 00:10:46,580
Naast de gecomprimeerde bericht.

138
00:10:46,580 --> 00:10:51,490
Ze moeten begrijpen wat de boom er daadwerkelijk uitziet,

139
00:10:51,490 --> 00:10:55,450
hoe we eigenlijk gemaakt die beslissingen.

140
00:10:55,450 --> 00:10:59,100
>> Hier werden we gewoon doen voorbeelden gebaseerd op de werkelijke telling,

141
00:10:59,100 --> 00:11:01,550
maar soms kun je ook een Huffman boom

142
00:11:01,550 --> 00:11:05,760
op basis van de frequentie waarmee letters verschijnen, en het is precies hetzelfde proces.

143
00:11:05,760 --> 00:11:09,090
Hier ben ik het uit te drukken in termen van percentages en een fractie,

144
00:11:09,090 --> 00:11:11,290
en dus even precies hetzelfde.

145
00:11:11,290 --> 00:11:15,300
Ik vind de 2 laagste, vatten ze de volgende 2 laagste, vatten ze,

146
00:11:15,300 --> 00:11:19,390
tot ik een volle boom.

147
00:11:19,390 --> 00:11:23,610
Ook al konden we het doen hoe dan ook, als we te maken hebben met percentages,

148
00:11:23,610 --> 00:11:27,760
dat betekent dat we dingen te delen en het omgaan met decimalen of liever drijft

149
00:11:27,760 --> 00:11:30,900
als we denken over datastructuren van een hoofd.

150
00:11:30,900 --> 00:11:32,540
Wat weten we over praalwagens?

151
00:11:32,540 --> 00:11:35,180
Wat is een veelvoorkomend probleem wanneer we te maken hebben met praalwagens?

152
00:11:35,180 --> 00:11:38,600
[Student] Onduidelijke rekenen. >> Ja. Onnauwkeurigheid.

153
00:11:38,600 --> 00:11:43,760
Door floating point onnauwkeurigheid, want dit PSET, zodat we er zeker van

154
00:11:43,760 --> 00:11:49,450
dat we geen waarden te verliezen, dan zijn we echt gaan te maken hebben met de telling.

155
00:11:49,450 --> 00:11:54,880
Dus als je te denken van een Huffman knoop, als je kijkt naar de structuur hier,

156
00:11:54,880 --> 00:12:01,740
als je kijkt naar de groene heeft een frequentie die ermee verbonden zijn

157
00:12:01,740 --> 00:12:08,760
en wijst op een knooppunt aan de linkerkant en een knooppunt aan de rechterkant.

158
00:12:08,760 --> 00:12:13,970
En dan de rode is er ook een karakter met hen verbonden.

159
00:12:13,970 --> 00:12:18,900
We gaan niet te scheiden's te maken voor de ouders en dan de laatste knopen,

160
00:12:18,900 --> 00:12:23,680
die we aanduiden als de bladeren, maar die zullen alleen maar NULL-waarden.

161
00:12:23,680 --> 00:12:31,050
Voor elke node hebben we een karakter, het symbool dat dat knooppunt vertegenwoordigt,

162
00:12:31,050 --> 00:12:40,490
dan een frequentie en een verwijzing naar de linker kind en de rechter kind.

163
00:12:40,490 --> 00:12:45,680
De bladeren, die helemaal onderaan, zou ook knooppunt pointers

164
00:12:45,680 --> 00:12:49,550
om hun linker-en aan de rechterkant, maar aangezien deze waarden niet verwijzen naar de werkelijke knooppunten,

165
00:12:49,550 --> 00:12:53,970
wat zou de waarde zijn? >> [Student] NULL. >> NULL. Precies.

166
00:12:53,970 --> 00:12:58,430
Hier is een voorbeeld van hoe u de frequentie te vertegenwoordigen in vlotters,

167
00:12:58,430 --> 00:13:02,130
maar we gaan maken te hebben met het met gehele getallen,

168
00:13:02,130 --> 00:13:06,780
dus alles wat ik deed is er het gegevenstype.

169
00:13:06,780 --> 00:13:09,700
>> Laten we verder gaan naar een beetje meer van een complex voorbeeld.

170
00:13:09,700 --> 00:13:13,360
Maar nu dat we de eenvoudige soorten gedaan, het is gewoon hetzelfde proces.

171
00:13:13,360 --> 00:13:20,290
U vindt de 2 laagste frequenties, de som van de frequenties

172
00:13:20,290 --> 00:13:22,450
en dat is de nieuwe frequentie van uw parent node,

173
00:13:22,450 --> 00:13:29,310
die wijst vervolgens aan de linkerkant met de 0 tak en rechts met de 1 tak.

174
00:13:29,310 --> 00:13:34,200
Als we de string "Dit is CS50," dan gaan we tellen hoe vaak wordt T genoemd,

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

176
00:13:38,420 --> 00:13:42,010
Maar wat ik hier heb gedaan is met de rode knopen ik net geplant,

177
00:13:42,010 --> 00:13:48,530
Ik zei dat ik ga uiteindelijk deze tekens aan de onderkant van mijn boom.

178
00:13:48,530 --> 00:13:51,740
Die zullen worden alle van de bladeren.

179
00:13:51,740 --> 00:13:58,200
Dan wat ik deed is dat ik ze gesorteerd op frequentie in oplopende volgorde,

180
00:13:58,200 --> 00:14:02,950
en dit is eigenlijk de manier waarop de PSET code het doet

181
00:14:02,950 --> 00:14:07,550
is het sorteert het door de frequentie en vervolgens alfabetisch.

182
00:14:07,550 --> 00:14:13,870
Dus het heeft de nummers en vervolgens alfabetisch op de frequentie.

183
00:14:13,870 --> 00:14:18,520
Dan wat ik zou doen is dat ik zou vinden van de 2 laagste. Dat is 0 en 5.

184
00:14:18,520 --> 00:14:22,390
Ik zou samenvatten hen, en dat is 2. Dan zou ik blijven, vinden de volgende 2 laagste.

185
00:14:22,390 --> 00:14:26,100
Dat zijn de twee 1s en die worden 2 en.

186
00:14:26,100 --> 00:14:31,570
Nu weet ik dat mijn volgende stap gaat worden de toetreding tot de laagste nummer,

187
00:14:31,570 --> 00:14:41,380
die de T, de 1 en met een van de knooppunten 2 heeft de frequentie.

188
00:14:41,380 --> 00:14:44,560
Hier hebben we dus 3 opties.

189
00:14:44,560 --> 00:14:47,980
Wat ik ga doen voor de dia is gewoon visueel herschikken ze voor u

190
00:14:47,980 --> 00:14:51,790
zodat u kunt zien hoe ik het opbouwen.

191
00:14:51,790 --> 00:14:59,040
Wat de code en je distributie code gaat doen zou toetreden tot de T een

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

193
00:15:01,410 --> 00:15:05,060
Dus dan die bedragen tot en met 3, en dan hebben we het proces voort te zetten.

194
00:15:05,060 --> 00:15:08,660
De 2 en de 2 nu de laagste, dus dan die som tot 4.

195
00:15:08,660 --> 00:15:12,560
Iedereen volgt tot nu toe? Oke.

196
00:15:12,560 --> 00:15:16,410
Dan na dat we de 3 en de 3 die moeten worden opgeteld,

197
00:15:16,410 --> 00:15:21,650
dus nogmaals, ik ben gewoon te schakelen, zodat je kunt visueel zo zien dat het niet al te rommelig.

198
00:15:21,650 --> 00:15:25,740
Dan hebben we een 6, en dan is onze laatste stap is nu dat we slechts 2 nodes hebben

199
00:15:25,740 --> 00:15:30,440
we de som die aan de wortel van onze boom, dat is 10 te maken.

200
00:15:30,440 --> 00:15:34,100
En het getal 10 is logisch, want elk knooppunt vertegenwoordigd,

201
00:15:34,100 --> 00:15:40,750
hun waarde, hun frequentie-nummer, was hoe vaak ze verscheen in de reeks,

202
00:15:40,750 --> 00:15:46,350
en dan hebben we 5 karakters hebben in onze reeks, dus dat maakt zin.

203
00:15:48,060 --> 00:15:52,320
Als we kijken omhoog naar hoe we zouden eigenlijk coderen,

204
00:15:52,320 --> 00:15:56,580
zoals verwacht, de i en s, die verschijnen de meest

205
00:15:56,580 --> 00:16:01,350
worden voorgesteld door de kleinste aantal bits.

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

207
00:16:05,660 --> 00:16:09,780
In Huffman bomen het geval van belang eigenlijk.

208
00:16:09,780 --> 00:16:13,670
Een hoofdletter S is anders dan een kleine letter s.

209
00:16:13,670 --> 00:16:21,260
Als we "Dit is CS50" met hoofdletters, dan is de kleine letter s zou slechts twee keer verschijnen,

210
00:16:21,260 --> 00:16:27,120
zou een knooppunt met 2 als waarde en hoofdletters S slechts eenmaal worden.

211
00:16:27,120 --> 00:16:33,440
Dus dan is uw boom zou veranderen structuren, omdat je eigenlijk een extra blaadje hier.

212
00:16:33,440 --> 00:16:36,900
Maar de som zou nog steeds 10.

213
00:16:36,900 --> 00:16:39,570
Dat is wat we eigenlijk gaan worden aanroepen van de checksum,

214
00:16:39,570 --> 00:16:44,060
de toevoeging van alle tellingen.

215
00:16:46,010 --> 00:16:50,990
>> Nu we Huffman bomen bedekt, kunnen we een duik nemen in Huff'n Puff, de PSET.

216
00:16:50,990 --> 00:16:52,900
We gaan beginnen met een deel van de vragen,

217
00:16:52,900 --> 00:16:57,990
en dit gaat om je vertrouwd met binaire bomen en de bediening rond die:

218
00:16:57,990 --> 00:17:03,230
tekenen knooppunten, het creëren van uw eigen typedef struct voor een knooppunt,

219
00:17:03,230 --> 00:17:07,230
en te zien hoe u in te voegen in een binaire boom, een die gesorteerd,

220
00:17:07,230 --> 00:17:09,050
doorkruisen, en dat soort dingen.

221
00:17:09,050 --> 00:17:14,560
Die kennis is zeker gaan om u te helpen wanneer u een duik in de Huff'n Puff gedeelte

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

223
00:17:19,150 --> 00:17:26,329
In de standaard editie van de PSET, uw taak is het implementeren van Puff,

224
00:17:26,329 --> 00:17:30,240
en in de hacker-versie uw taak is het implementeren van Huff.

225
00:17:30,240 --> 00:17:38,490
Wat Huff doet is het duurt tekst en dan vertaalt deze in de 0s en 1s,

226
00:17:38,490 --> 00:17:41,990
zodat het proces dat we hierboven hebben waar we telden de frequenties

227
00:17:41,990 --> 00:17:50,970
en maakte vervolgens de boom en zei toen: "Hoe krijg ik T? '

228
00:17:50,970 --> 00:17:54,840
T wordt vertegenwoordigd door 100, dat soort dingen,

229
00:17:54,840 --> 00:17:58,860
en dan Huff zou de tekst en dan output die binair.

230
00:17:58,860 --> 00:18:04,920
Maar ook omdat we weten dat we willen onze ontvanger van het bericht kan

231
00:18:04,920 --> 00:18:11,790
om te recreëren exact dezelfde boom, maar bevat ook informatie over de frequentie telt.

232
00:18:11,790 --> 00:18:17,980
Dan met Puff krijgen we een binair bestand van 0s en 1s

233
00:18:17,980 --> 00:18:21,740
en ook gezien de informatie over de frequenties.

234
00:18:21,740 --> 00:18:26,740
Wij vertalen al die 0s en 1s terug in het oorspronkelijke bericht dat was,

235
00:18:26,740 --> 00:18:29,350
dus we decomprimeren dat.

236
00:18:29,350 --> 00:18:36,450
Als je doet de standaard editie, hoeft u niet te Huff implementeren,

237
00:18:36,450 --> 00:18:39,290
dus dan kun je gewoon gebruik maken van de medewerkers uitvoering van Huff.

238
00:18:39,290 --> 00:18:42,080
Er zijn aanwijzingen in de spec over hoe dat te doen.

239
00:18:42,080 --> 00:18:48,780
U kunt de medewerkers uitvoering van Huff op een bepaald tekstbestand

240
00:18:48,780 --> 00:18:53,270
en gebruik die uitgang als uw opmerkingen toe aan Puff.

241
00:18:53,270 --> 00:18:59,330
>> Zoals ik al eerder vermeld, hebben we veel van de distributie-code voor deze.

242
00:18:59,330 --> 00:19:01,810
Ik ga om te beginnen gaan doorheen.

243
00:19:01,810 --> 00:19:04,400
Ik ga het grootste deel van de tijd doorbrengen op de. H-bestanden

244
00:19:04,400 --> 00:19:07,660
omdat in de. c bestanden, want we hebben het. h

245
00:19:07,660 --> 00:19:11,650
en dat geeft ons de prototypes van de functies,

246
00:19:11,650 --> 00:19:15,520
we niet volledig nodig om precies te begrijpen -

247
00:19:15,520 --> 00:19:20,280
Als je niet begrijpt wat er gaande is in de. C bestanden, kies dan niet te veel zorgen,

248
00:19:20,280 --> 00:19:23,600
maar zeker proberen om een ​​kijkje te nemen, want het zou kunnen geven enkele hints

249
00:19:23,600 --> 00:19:29,220
en het is handig om te wennen aan het lezen van andere mensen de code.

250
00:19:38,940 --> 00:19:48,270
>> Kijkend naar huffile.h, in de opmerkingen die zij verklaart een laag van abstractie voor Huffman-gecodeerde bestanden.

251
00:19:48,270 --> 00:20:01,660
Als we naar beneden gaan, dan zien we dat er een maximum van 256 symbolen die we misschien codes voor nodig hebt.

252
00:20:01,660 --> 00:20:05,480
Dit omvat alle letters van het alfabet - hoofdletters en kleine letters -

253
00:20:05,480 --> 00:20:08,250
en symbolen en nummers, etc.

254
00:20:08,250 --> 00:20:11,930
Dan hebben we hier een magisch nummer ter identificatie van een Huffman-gecodeerde bestand.

255
00:20:11,930 --> 00:20:15,890
Binnen een Huffman code ze gaan om een ​​bepaald magisch getal hebben

256
00:20:15,890 --> 00:20:18,560
verband met de header.

257
00:20:18,560 --> 00:20:21,110
Dit kan eruit zien als een willekeurig magisch getal,

258
00:20:21,110 --> 00:20:27,160
maar als je echt te vertalen naar ASCII, dan is het spreuken eigenlijk uit HUFF.

259
00:20:27,160 --> 00:20:34,290
Hier hebben we een struct voor een Huffman-gecodeerd bestand.

260
00:20:34,290 --> 00:20:39,670
Er is al deze kenmerken die geassocieerd worden met een Huff bestand.

261
00:20:39,670 --> 00:20:47,080
Dan hier beneden hebben we de header voor een Huff bestand, dus we noemen het Huffeader

262
00:20:47,080 --> 00:20:50,810
in plaats van het toevoegen van de extra h want het klinkt toch hetzelfde.

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

264
00:20:52,720 --> 00:20:57,790
We hebben een magisch nummer gekoppeld.

265
00:20:57,790 --> 00:21:09,040
Als het een echte Huff bestand, het gaat om het aantal te boven, deze magische een.

266
00:21:09,040 --> 00:21:14,720
En dan zal een array.

267
00:21:14,720 --> 00:21:18,750
Dus voor elk symbool, waarvan er 256,

268
00:21:18,750 --> 00:21:24,760
het gaat naar wat de frequentie van die symbolen zijn in het Huff bestand.

269
00:21:24,760 --> 00:21:28,090
En dan tot slot hebben we een checksum voor de frequenties,

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

271
00:21:32,160 --> 00:21:36,520
Dus dat is wat een Huffeader is.

272
00:21:36,520 --> 00:21:44,600
Dan hebben we een aantal functies die de volgende bit terug te keren in de Huff-bestand

273
00:21:44,600 --> 00:21:52,580
alsmede schrijft een beetje aan het Huff bestand en deze functie hier,, hfclose

274
00:21:52,580 --> 00:21:54,650
die sluit eigenlijk de Huff-bestand.

275
00:21:54,650 --> 00:21:57,290
Voorheen werden we te maken met rechte net fclose,

276
00:21:57,290 --> 00:22:01,190
maar als je een Huff bestand hebben, in plaats van fclosing het

277
00:22:01,190 --> 00:22:06,080
wat je eigenlijk gaan doen, is hfclose en hfopen het.

278
00:22:06,080 --> 00:22:13,220
Dat zijn specifieke functies om de Huff bestanden die we gaan te maken hebben.

279
00:22:13,220 --> 00:22:19,230
Dan hier lezen we in de header en schrijf dan de header.

280
00:22:19,230 --> 00:22:25,700
>> Gewoon door het lezen van de. H-bestand kunnen we soort van een gevoel van wat een Huff bestand zou kunnen zijn,

281
00:22:25,700 --> 00:22:32,480
Welke kenmerken heeft het, zonder daadwerkelijk te gaan op de huffile.c,

282
00:22:32,480 --> 00:22:36,750
die, als we duiken in, gaat een beetje complexer.

283
00:22:36,750 --> 00:22:41,270
Het heeft alle van het bestand I / O hier te maken met pointers.

284
00:22:41,270 --> 00:22:48,010
Hier zien we dat wanneer we hfread noemen, bijvoorbeeld, is het nog te maken heeft fread.

285
00:22:48,010 --> 00:22:53,050
We zijn niet het wegwerken van deze functies volledig, maar we sturen de te nemen maatregelen zorgen

286
00:22:53,050 --> 00:22:59,760
in het Huff bestand in plaats van het doen van al het zelf.

287
00:22:59,760 --> 00:23:02,300
U kunt gerust te scannen door middel van deze als je nieuwsgierig bent

288
00:23:02,300 --> 00:23:08,410
en gaan en schil de laag terug een beetje.

289
00:23:20,650 --> 00:23:24,060
>> Het volgende bestand dat we gaan kijken is tree.h.

290
00:23:24,060 --> 00:23:30,210
Voordat in de Walkthrough schuift we zeiden verwachten wij een Huffman knooppunt

291
00:23:30,210 --> 00:23:32,960
en we maakten een typedef struct node.

292
00:23:32,960 --> 00:23:38,360
We verwachten dat het een symbool, een frequentie, en dan 2 knooppunt sterren hebben.

293
00:23:38,360 --> 00:23:41,870
In dit geval wat we doen is dit is in wezen hetzelfde

294
00:23:41,870 --> 00:23:46,880
behalve in plaats van knooppunt gaan we noemen ze bomen.

295
00:23:48,790 --> 00:23:56,760
We hebben de functie dat wanneer u belt maakt boom geeft hij je een boom pointer.

296
00:23:56,760 --> 00:24:03,450
Terug naar Speller, toen je een nieuw knooppunt te maken

297
00:24:03,450 --> 00:24:11,410
je zei dat knooppunt * nieuw woord = malloc (sizeof) en dat soort dingen.

298
00:24:11,410 --> 00:24:17,510
In principe is mktree zal te maken hebben met dat voor u.

299
00:24:17,510 --> 00:24:20,990
Ook wanneer u een boom te verwijderen,

300
00:24:20,990 --> 00:24:24,810
dus dat is in wezen het bevrijden van de boom als je klaar bent met het,

301
00:24:24,810 --> 00:24:33,790
in plaats van expliciet te bellen gratis op dat, je bent eigenlijk alleen maar gaat om de functie te gebruiken rmtree

302
00:24:33,790 --> 00:24:40,360
waar u doorgeeft in de pointer naar die boom en dan ontbrekend zal zorgen dat voor u.

303
00:24:40,360 --> 00:24:42,490
>> We kijken naar tree.c.

304
00:24:42,490 --> 00:24:47,240
We verwachten dat dezelfde functies, behalve om de uitvoering, maar ook zien.

305
00:24:47,240 --> 00:24:57,720
Zoals we verwacht hadden, als je mktree noemen mallocs de grootte van een boom in een pointer,

306
00:24:57,720 --> 00:25:03,190
initialiseert alle waarden van de NULL waarde, zodat 0s of nullen,

307
00:25:03,190 --> 00:25:08,280
en keert dan terug de pointer naar die boom die je net hebt malloc'd voor jou.

308
00:25:08,280 --> 00:25:13,340
Hier als u belt verwijderen boom het maakt eerste zeker van dat je niet dubbel te bevrijden.

309
00:25:13,340 --> 00:25:18,320
Het zorgt ervoor dat je eigenlijk een boom die u wilt verwijderen te hebben.

310
00:25:18,320 --> 00:25:23,330
Is, omdat de boom ook de kinderen

311
00:25:23,330 --> 00:25:29,560
Wat dit doet is het noemt recursief te verwijderen boom aan de linkerkant knooppunt van de boom

312
00:25:29,560 --> 00:25:31,650
en rechts node.

313
00:25:31,650 --> 00:25:37,790
Voordat het bevrijdt de ouder, die het nodig heeft om de kinderen vrij te maken ook.

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

315
00:25:42,770 --> 00:25:46,500
De allereerste ouder, dus net als de over-over-over-over-grootvader

316
00:25:46,500 --> 00:25:52,130
of grootmoeder boom, eerst moeten we bevrijden beneden de niveaus eerste.

317
00:25:52,130 --> 00:25:58,490
Dus doorkruisen naar de bodem, vrij die, en dan weer terug komen, gratis die, enz.

318
00:26:00,400 --> 00:26:02,210
Dus dat is boom.

319
00:26:02,210 --> 00:26:04,240
>> Nu kijken we naar het bos.

320
00:26:04,240 --> 00:26:09,860
Bos plaatst u al uw Huffman bomen.

321
00:26:09,860 --> 00:26:12,910
Het is te zeggen dat we gaan iets hebben genoemd een perceel

322
00:26:12,910 --> 00:26:22,320
dat bevat een pointer naar een boom en een pointer naar een plot genaamd volgende.

323
00:26:22,320 --> 00:26:28,480
Welke structuur doet dit soort eruit?

324
00:26:29,870 --> 00:26:32,490
Het soort van zegt dat het daar.

325
00:26:34,640 --> 00:26:36,700
Deze kant op.

326
00:26:37,340 --> 00:26:39,170
Een gelinkte lijst.

327
00:26:39,170 --> 00:26:44,590
We zien dat als we een perceel hebben het is als een gelinkte lijst van percelen.

328
00:26:44,590 --> 00:26:53,020
Een bos wordt gedefinieerd als een gelinkte lijst van percelen,

329
00:26:53,020 --> 00:26:58,100
en dus de structuur van het bos is dat we gaan gewoon met een pointer moeten onze eerste perceel

330
00:26:58,100 --> 00:27:02,740
en dat perceel heeft een boom in zich of liever wijst op een boom

331
00:27:02,740 --> 00:27:06,190
en wijst naar de volgende plot, enzovoort, enzovoort.

332
00:27:06,190 --> 00:27:11,100
Om een ​​bos te maken noemen we mkforest.

333
00:27:11,100 --> 00:27:14,930
Dan hebben we een aantal mooie handige functies hier.

334
00:27:14,930 --> 00:27:23,240
We hebben halen waar je langs in een bos en dan de return waarde is een boom *,

335
00:27:23,240 --> 00:27:25,210
een pointer naar een boom.

336
00:27:25,210 --> 00:27:29,370
Wat pick zal doen, is het zal gaan in het bos dat je te wijzen op

337
00:27:29,370 --> 00:27:35,240
verwijder vervolgens een boom met de laagste frequentie van dat bos

338
00:27:35,240 --> 00:27:38,330
en geven u de aanwijzer naar die boom.

339
00:27:38,330 --> 00:27:43,030
Zodra u belt plukken, zal de boom niet meer bestaat in het bos,

340
00:27:43,030 --> 00:27:48,550
maar de return waarde is de aanwijzer naar die boom.

341
00:27:48,550 --> 00:27:50,730
Dan heb je plant.

342
00:27:50,730 --> 00:27:57,420
Op voorwaarde dat u doorgeeft in een pointer naar een boom die een niet-0 frequentie heeft,

343
00:27:57,420 --> 00:28:04,040
welke plant zal doen, is het zal het bos te nemen, neem de boom en plant die boom in het bos.

344
00:28:04,040 --> 00:28:06,370
Hier hebben we rmforest.

345
00:28:06,370 --> 00:28:11,480
Net als boom, die in feite al onze bomen vrijgemaakt voor ons te verwijderen,

346
00:28:11,480 --> 00:28:16,600
Verwijder bos zal gratis alles in dat bos.

347
00:28:16,600 --> 00:28:24,890
>> Als we kijken naar forest.c, dan verwachten we minstens 1 rmtree commando zie daar,

348
00:28:24,890 --> 00:28:30,090
want om geheugen vrij te in het bos als een bos heeft bomen in het,

349
00:28:30,090 --> 00:28:32,930
dan uiteindelijk je gaat te hebben om te verwijderen die bomen.

350
00:28:32,930 --> 00:28:41,020
Als we kijken naar forest.c, hebben we onze mkforest, dat is zoals we verwachten.

351
00:28:41,020 --> 00:28:42,890
We malloc dingen.

352
00:28:42,890 --> 00:28:51,740
We initialiseren het eerste perceel in het bos als NULL omdat het leeg om te beginnen,

353
00:28:51,740 --> 00:29:05,940
dan zien we pick, dat de boom terug met het laagste gewicht, de laagste frequentie,

354
00:29:05,940 --> 00:29:13,560
en dan krijgt ontdoen van die bepaalde node die verwijst naar die boom en de volgende,

355
00:29:13,560 --> 00:29:16,760
dus het duurt dat van de gekoppelde lijst van het bos.

356
00:29:16,760 --> 00:29:24,510
En dan hebben we hier plant, die voegt een boom in de gekoppelde lijst.

357
00:29:24,510 --> 00:29:29,960
Wat bos doet is het mooi houdt het gesorteerd voor ons.

358
00:29:29,960 --> 00:29:37,910
En tenslotte hebben we rmforest en zoals verwacht hebben we rmtree daar genoemd.

359
00:29:46,650 --> 00:29:55,440
>> Als we kijken naar de verdeling code tot nu toe, huffile.c was waarschijnlijk veruit de moeilijkste om te begrijpen,

360
00:29:55,440 --> 00:29:59,990
terwijl de andere bestanden zelf waren vrij eenvoudig te volgen.

361
00:29:59,990 --> 00:30:03,090
Met onze kennis van pointers en gelinkte lijsten en dergelijke,

362
00:30:03,090 --> 00:30:04,860
konden we vrij goed te volgen.

363
00:30:04,860 --> 00:30:10,500
Maar alles wat we nodig om echt ervoor te zorgen dat we volledig begrijpen is het. H-bestanden

364
00:30:10,500 --> 00:30:15,840
want je moet worden bellen die functies, het omgaan met deze terugkeer waarden,

365
00:30:15,840 --> 00:30:20,590
dus zorg ervoor dat u volledig begrijpt welke actie zal worden uitgevoerd

366
00:30:20,590 --> 00:30:24,290
wanneer je een van die functies aan te roepen.

367
00:30:24,290 --> 00:30:33,020
Maar eigenlijk begrijpen binnenkant van het is niet helemaal nodig omdat wij die hebben. H-bestanden.

368
00:30:35,170 --> 00:30:39,490
We hebben 2 meer bestanden links in onze distributie-code.

369
00:30:39,490 --> 00:30:41,640
>> Laten we eens kijken naar dump.

370
00:30:41,640 --> 00:30:47,230
Hier dumpen door haar reactie neemt een Huffman-gecomprimeerd bestand

371
00:30:47,230 --> 00:30:55,580
en dan vertaalt en dumpt al zijn inhoud uit.

372
00:31:01,010 --> 00:31:04,260
Hier zien we dat het is hfopen belt.

373
00:31:04,260 --> 00:31:10,770
Dit is een beetje spiegelen aan * input file = fopen,

374
00:31:10,770 --> 00:31:13,500
en dan passeert u in de informatie.

375
00:31:13,500 --> 00:31:18,240
Het is bijna identiek, behalve in plaats van een bestand * je voorbij in een Huffile;

376
00:31:18,240 --> 00:31:22,030
in plaats van fopen je voorbij in hfopen.

377
00:31:22,030 --> 00:31:29,280
Hier lezen we in de header eerste, dat is een beetje vergelijkbaar met de manier waarop we lezen in de header

378
00:31:29,280 --> 00:31:33,580
voor een bitmap-bestand.

379
00:31:33,580 --> 00:31:38,000
Wat we hier doen is het controleren om te zien of de header informatie

380
00:31:38,000 --> 00:31:44,330
bevat de juiste magische getal dat aangeeft dat het een echte Huff bestand,

381
00:31:44,330 --> 00:31:53,610
dan al deze controles om ervoor te zorgen dat het bestand dat we geopend is een echte hufde bestand of niet.

382
00:31:53,610 --> 00:32:05,330
Wat dit doet is voordat het de frequenties van alle symbolen die we kunnen zien

383
00:32:05,330 --> 00:32:09,790
bij een terminal in een grafische tabel.

384
00:32:09,790 --> 00:32:15,240
Dit deel zal nuttig zijn.

385
00:32:15,240 --> 00:32:24,680
Het heeft een beetje en leest beetje bij beetje in de variabele beetje en dan drukt het uit.

386
00:32:28,220 --> 00:32:35,430
Dus als ik dump een beroep doen op hth.bin, die het gevolg is van hijgend een bestand

387
00:32:35,430 --> 00:32:39,490
met behulp van het personeel oplossing, zou ik dit.

388
00:32:39,490 --> 00:32:46,000
Het is het uitvoeren van al deze personages en dan zetten de frequentie waarin ze voorkomen.

389
00:32:46,000 --> 00:32:51,180
Kijken we meeste zijn 0s behalve voor: H, die tweemaal verschijnt

390
00:32:51,180 --> 00:32:54,820
en dan T, die ooit verschijnt.

391
00:32:54,820 --> 00:33:07,860
En dan hebben we hier de werkelijke boodschap in 0s en 1s.

392
00:33:07,860 --> 00:33:15,450
Als we kijken naar hth.txt, dat is vermoedelijk het oorspronkelijke bericht dat werd hufde,

393
00:33:15,450 --> 00:33:22,490
verwachten we een aantal Hs en Ts zien daar.

394
00:33:22,490 --> 00:33:28,720
In het bijzonder, verwachten we slechts 1 T en 2 Hs zien.

395
00:33:32,510 --> 00:33:37,440
Hier zijn we in hth.txt. Het heeft inderdaad HTH.

396
00:33:37,440 --> 00:33:41,270
Inbegrepen in daar, hoewel we niet kunnen zien, is een nieuwe regel karakter.

397
00:33:41,270 --> 00:33:53,190
De Huff bestand hth.bin is ook dat codeert voor het newline karakter.

398
00:33:55,680 --> 00:34:01,330
Hier omdat we weten dat de bestelling is HTH en dan newline,

399
00:34:01,330 --> 00:34:07,340
kunnen we dat waarschijnlijk de H wordt vertegenwoordigd zien door slechts een enkele 1

400
00:34:07,340 --> 00:34:17,120
en de T waarschijnlijk 01 en de volgende H is 1 en

401
00:34:17,120 --> 00:34:21,139
en dan hebben we een nieuwe regel aangegeven met twee 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> En dan tot slot, omdat we te maken hebben met meerdere. C en. H-bestanden,

404
00:34:31,600 --> 00:34:36,350
we gaan een mooi complex argument moet de compiler,

405
00:34:36,350 --> 00:34:40,460
en dus hier hebben we een Makefile die dump voor je maakt.

406
00:34:40,460 --> 00:34:47,070
Maar eigenlijk, je moet gaan over het maken van uw eigen puff.c bestand.

407
00:34:47,070 --> 00:34:54,330
De Makefile doet eigenlijk niet bezig met het maken van puff.c voor u.

408
00:34:54,330 --> 00:34:59,310
We vertrekken dat het aan jou om de Makefile bewerken.

409
00:34:59,310 --> 00:35:05,930
Wanneer u een opdracht als make alle betreden, bijvoorbeeld, zal het allemaal voor u.

410
00:35:05,930 --> 00:35:10,760
Voel je vrij om bij de voorbeelden van Makefile kijken uit het verleden PSET

411
00:35:10,760 --> 00:35:17,400
alsmede gaan uit van deze om te zien hoe je zou kunnen uw Puff bestand maken

412
00:35:17,400 --> 00:35:20,260
door het bewerken van deze Makefile.

413
00:35:20,260 --> 00:35:22,730
Dat is het zowat voor onze distributie-code.

414
00:35:22,730 --> 00:35:28,380
>> Zodra we hebben gekregen door dat, dan is hier gewoon een herinnering

415
00:35:28,380 --> 00:35:30,980
van hoe we te maken te hebben met de Huffman knooppunten.

416
00:35:30,980 --> 00:35:35,400
We gaan niet te bellen ze knopen meer, we gaan te bellen ze bomen

417
00:35:35,400 --> 00:35:39,260
waar we naartoe gaan worden die hun symbool met een char,

418
00:35:39,260 --> 00:35:43,340
de frequentie, het aantal gebeurtenissen, een integer.

419
00:35:43,340 --> 00:35:47,370
We gebruiken dat omdat het nauwkeuriger dan een vlotter.

420
00:35:47,370 --> 00:35:52,980
En dan nog een pointer naar links kind als het rechter kind.

421
00:35:52,980 --> 00:35:59,630
Een woud, zoals we zagen, is slechts een gelinkte lijst van bomen.

422
00:35:59,630 --> 00:36:04,670
Uiteindelijk, als we de opbouw van onze Huff-bestand,

423
00:36:04,670 --> 00:36:07,580
we willen dat onze bossen naar slechts 1 boom bevatten -

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

425
00:36:12,420 --> 00:36:20,840
Eerder toen we alleen het maken van onze Huffman bomen,

426
00:36:20,840 --> 00:36:25,360
We zijn begonnen met het plaatsen van alle knooppunten op ons scherm

427
00:36:25,360 --> 00:36:27,790
en zeggen we gaan deze knooppunten hebben,

428
00:36:27,790 --> 00:36:32,920
uiteindelijk ze gaan zijn de bladeren, en dit is hun symbool, dit is hun frequentie.

429
00:36:32,920 --> 00:36:42,070
In onze bossen als we alleen maar 3 letters, dat is een bos van 3 bomen.

430
00:36:42,070 --> 00:36:45,150
En dan als we verder gaan, als we de eerste ouder toegevoegd,

431
00:36:45,150 --> 00:36:48,080
hebben we een bos van 2 bomen.

432
00:36:48,080 --> 00:36:54,930
Wij verwijderd 2 van die kinderen van onze bossen en daarna vervangen door een parent node

433
00:36:54,930 --> 00:36:58,820
dat had die 2 knopen als kinderen.

434
00:36:58,820 --> 00:37:05,600
En dan tot slot, onze laatste stap bij het maken van ons voorbeeld met de As, B, en C's

435
00:37:05,600 --> 00:37:08,030
zou de uiteindelijke bovenliggende maken,

436
00:37:08,030 --> 00:37:13,190
en zo dan zou dat brengen onze totale telling van de bomen in het bos op 1.

437
00:37:13,190 --> 00:37:18,140
Heeft iedereen zien hoe je begint met meerdere bomen in je bos

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

439
00:37:25,530 --> 00:37:28,110
>> Wat hebben we nodig om te doen voor Puff?

440
00:37:28,110 --> 00:37:37,110
Wat we moeten doen is ervoor te zorgen dat, zoals altijd, zij geven ons het juiste type van de input

441
00:37:37,110 --> 00:37:39,090
zodat we daadwerkelijk kunnen uitvoeren van het programma.

442
00:37:39,090 --> 00:37:43,130
In dit geval gaan ze te geven van ons na hun eerste opdrachtregelargument

443
00:37:43,130 --> 00:37:53,440
2 meer: ​​het bestand dat we willen decomprimeren en de uitgang van de gedecomprimeerde bestand.

444
00:37:53,440 --> 00:38:00,410
Maar zodra wij zorgen ervoor dat ze ons pas in de juiste hoeveelheid waarden,

445
00:38:00,410 --> 00:38:05,820
We willen ervoor zorgen dat de invoer een Huff bestand of niet.

446
00:38:05,820 --> 00:38:10,420
En dan als we garanderen dat het een Huff bestand, dan willen we onze boom te bouwen,

447
00:38:10,420 --> 00:38:20,940
de opbouw van de boom zodanig dat zij de boom die de persoon die het bericht heeft gestuurd gebouwd past.

448
00:38:20,940 --> 00:38:25,840
Dan na bouwen we de boom, dan kunnen we omgaan met de 0s en 1s dat ze voorbij in,

449
00:38:25,840 --> 00:38:29,590
volgen die langs onze boom, want het is identiek,

450
00:38:29,590 --> 00:38:33,510
en schrijf dan die boodschap uit, terug de interpretatie van de bits in tekens.

451
00:38:33,510 --> 00:38:35,880
En dan aan het einde, omdat we te maken hebben met pointers hier,

452
00:38:35,880 --> 00:38:38,110
willen we ervoor zorgen dat we geen geheugenlekken hebben

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

454
00:38:42,820 --> 00:38:46,430
>> Zorgen voor het juiste gebruik is oude koek voor ons nu.

455
00:38:46,430 --> 00:38:51,980
We nemen in een input, die gaat naar de naam van het bestand te blazen zijn,

456
00:38:51,980 --> 00:38:56,010
en dan specificeren we een uitgang,

457
00:38:56,010 --> 00:39:01,580
zodat de naam van het bestand voor het gepofte output, die de tekstbestanden.

458
00:39:03,680 --> 00:39:08,820
Dat is gebruik. En nu willen we ervoor zorgen dat de ingang snoof of niet.

459
00:39:08,820 --> 00:39:16,420
Terugdenkend, was er iets in de verdeelsleutel die ons kunnen helpen

460
00:39:16,420 --> 00:39:21,570
met het begrijpen van de vraag of er een bestand is hufde of niet?

461
00:39:21,570 --> 00:39:26,910
Er was informatie in huffile.c over de Huffeader.

462
00:39:26,910 --> 00:39:33,430
We weten dat elke Huff bestand een Huffeader verbonden aan een magisch getal is

463
00:39:33,430 --> 00:39:37,240
alsmede een reeks van frequenties voor elk symbool

464
00:39:37,240 --> 00:39:39,570
en een checksum.

465
00:39:39,570 --> 00:39:43,180
We weten dat, maar we namen ook een kijkje op dump.c,

466
00:39:43,180 --> 00:39:49,120
waarin het aan het lezen was in een Huff bestand.

467
00:39:49,120 --> 00:39:53,990
En dus om dat te doen, moest om te controleren of het echt was snoof of niet.

468
00:39:53,990 --> 00:40:03,380
Dus misschien kunnen we dump.c als een structuur te gebruiken voor onze puff.c.

469
00:40:03,380 --> 00:40:12,680
Terug naar PSET 4 wanneer we het bestand copy.c die gekopieerd in RGB triples hadden

470
00:40:12,680 --> 00:40:14,860
en we uitgelegd dat voor Whodunit en Resize,

471
00:40:14,860 --> 00:40:20,390
evenzo is wat je zou kunnen doen gewoon de commando als cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
en gebruik een aantal van de code daar.

473
00:40:23,600 --> 00:40:28,210
Echter, het is niet van plan om zo eenvoudig van een proces

474
00:40:28,210 --> 00:40:33,010
voor het vertalen van uw dump.c in puff.c,

475
00:40:33,010 --> 00:40:36,160
maar in ieder geval het geeft je ergens beginnen om

476
00:40:36,160 --> 00:40:40,540
hoe dat de ingang daadwerkelijk hufde of niet

477
00:40:40,540 --> 00:40:43,240
evenals een paar andere dingen.

478
00:40:45,930 --> 00:40:50,250
Wij hebben ervoor gezorgd juiste gebruik en ervoor gezorgd dat de ingang wordt hufde.

479
00:40:50,250 --> 00:40:53,570
Elke keer dat we hebben gedaan dat we onze goede foutcontrole gedaan,

480
00:40:53,570 --> 00:41:01,520
zo terug te keren en het verlaten van de functie als sommige optreedt, wanneer er een probleem is.

481
00:41:01,520 --> 00:41:07,170
>> Wat we nu willen doen is bouwen van de eigenlijke boom.

482
00:41:08,840 --> 00:41:12,640
Als we kijken in Vorst, zijn er 2 belangrijke functies

483
00:41:12,640 --> 00:41:15,800
dat we gaan willen heel vertrouwd te raken met.

484
00:41:15,800 --> 00:41:23,870
Er is de Booleaanse functie plant die planten een niet-0-frequentie boom in ons bos.

485
00:41:23,870 --> 00:41:29,250
En zo zijn er passeert u in een pointer naar een bos en een pointer naar een boom.

486
00:41:32,530 --> 00:41:40,340
Snelle vraag: Hoeveel bossen zult u wanneer u het bouwen van een Huffman boom?

487
00:41:44,210 --> 00:41:46,650
Ons bos is als onze canvas, toch?

488
00:41:46,650 --> 00:41:50,800
Dus we alleen maar een bos, maar we gaan om meerdere bomen.

489
00:41:50,800 --> 00:41:57,590
Dus voordat je plant noemen, je waarschijnlijk gaat te willen om uw bos te maken.

490
00:41:57,590 --> 00:42:04,430
Er is een commando voor dat als je kijkt naar forest.h over hoe je kunt een bos te maken.

491
00:42:04,430 --> 00:42:09,270
U kunt de plant een boom. We weten hoe dat te doen.

492
00:42:09,270 --> 00:42:11,590
En dan kun je ook kiezen een boom uit het bos,

493
00:42:11,590 --> 00:42:17,540
het verwijderen van een boom met het laagste gewicht en geven u de aanwijzer naar dat.

494
00:42:17,540 --> 00:42:23,090
Terugdenkend aan toen we aan het doen waren de voorbeelden zelf,

495
00:42:23,090 --> 00:42:27,980
toen we het tekenen, we simpelweg toegevoegd de links.

496
00:42:27,980 --> 00:42:31,680
Maar hier in plaats van alleen het toevoegen van de links,

497
00:42:31,680 --> 00:42:40,630
denk aan het meer als je 2 van die knooppunten te verwijderen en daarna te vervangen door een andere.

498
00:42:40,630 --> 00:42:44,200
Om dat uit te drukken in termen van het plukken en planten,

499
00:42:44,200 --> 00:42:48,840
je plukken 2 bomen en planten een andere boom

500
00:42:48,840 --> 00:42:54,060
dat heeft die 2 bomen dat u heeft geselecteerd als kinderen.

501
00:42:57,950 --> 00:43:05,280
Om Huffman's boom op te bouwen, kunt u lezen in de symbolen en frequenties op te

502
00:43:05,280 --> 00:43:10,790
omdat de Huffeader geeft dat aan u,

503
00:43:10,790 --> 00:43:14,250
geeft u een array van de frequenties.

504
00:43:14,250 --> 00:43:19,660
U kunt dus gaan en gewoon alles negeren met de 0 in het

505
00:43:19,660 --> 00:43:23,760
omdat we niet willen dat 256 blaadjes aan het eind van het.

506
00:43:23,760 --> 00:43:27,960
We willen alleen het aantal bladeren die tekens

507
00:43:27,960 --> 00:43:31,600
die werkelijk worden gebruikt in het bestand.

508
00:43:31,600 --> 00:43:37,590
Leest u in deze symbolen, en elk van deze symbolen niet-0 frequenties,

509
00:43:37,590 --> 00:43:40,440
deze zullen worden bomen.

510
00:43:40,440 --> 00:43:45,990
Wat je kunt doen is elke keer dat je leest in een niet-0-frequentie symbool,

511
00:43:45,990 --> 00:43:50,660
U kunt de plant die boom in het bos.

512
00:43:50,660 --> 00:43:56,620
Zodra u de bomen te planten in het bos, kunt u deelnemen aan die bomen als broers en zussen,

513
00:43:56,620 --> 00:44:01,130
dus terug te gaan naar het planten en plukken waar je plukken 2 en vervolgens plant 1,

514
00:44:01,130 --> 00:44:05,820
waar dat 1 die u plant is de ouder van de 2 kinderen dat u heeft geselecteerd.

515
00:44:05,820 --> 00:44:11,160
Dus dan is uw eindresultaat gaat om een ​​enkele boom in uw bos.

516
00:44:16,180 --> 00:44:18,170
Zo bouw je je boom.

517
00:44:18,170 --> 00:44:21,850
>> Er zijn verschillende dingen die hier mis kan gaan

518
00:44:21,850 --> 00:44:26,580
omdat we te maken hebben met het maken van nieuwe bomen en het omgaan met pointers en dat soort dingen.

519
00:44:26,580 --> 00:44:30,450
Toen we te maken hadden met pointers,

520
00:44:30,450 --> 00:44:36,580
wanneer we malloc'd we wilden er zeker van dat het niet terug ons een NULL pointer waarde.

521
00:44:36,580 --> 00:44:42,770
Dus op een aantal stappen in dit proces zijn er gaan worden een aantal gevallen

522
00:44:42,770 --> 00:44:45,920
waar uw programma zou kunnen mislukken.

523
00:44:45,920 --> 00:44:51,310
Wat u wilt doen is wilt u ervoor zorgen dat u deze fouten af ​​te handelen,

524
00:44:51,310 --> 00:44:54,580
en in de spec staat om gracieus mee om te gaan,

525
00:44:54,580 --> 00:45:00,280
zo graag afdrukken van een bericht aan de gebruiker hen te vertellen waarom het programma te stoppen

526
00:45:00,280 --> 00:45:03,050
en begeef u direct stoppen met het.

527
00:45:03,050 --> 00:45:09,490
Om dit te foutafhandeling doen, bedenk dan dat je wilt om het te controleren

528
00:45:09,490 --> 00:45:12,160
elke keer dat er een mislukking.

529
00:45:12,160 --> 00:45:14,660
Elke keer dat je een nieuwe pointer maken

530
00:45:14,660 --> 00:45:17,040
wilt u ervoor zorgen dat dat succesvol is.

531
00:45:17,040 --> 00:45:20,320
Voor wat we vroeger doen is een nieuwe aanwijzer en malloc te maken,

532
00:45:20,320 --> 00:45:22,380
en dan zouden we kijken of dat pointer NULL is.

533
00:45:22,380 --> 00:45:25,670
Dus er zullen zijn sommige gevallen waar je kunt gewoon doen,

534
00:45:25,670 --> 00:45:28,610
maar soms moet je je eigenlijk het aanroepen van een functie

535
00:45:28,610 --> 00:45:33,100
en binnen die functie, dat is degene die doet het mallocing.

536
00:45:33,100 --> 00:45:39,110
In dat geval, als we kijken naar een aantal functies in de code,

537
00:45:39,110 --> 00:45:42,260
sommige van hen zijn Booleaanse functies.

538
00:45:42,260 --> 00:45:48,480
In de abstracte geval als we een Booleaanse functie genaamd foo,

539
00:45:48,480 --> 00:45:54,580
in principe, kunnen we aannemen dat in aanvulling op doen wat foo doet,

540
00:45:54,580 --> 00:45:57,210
want het is een Booleaanse functie, het geeft true of false -

541
00:45:57,210 --> 00:46:01,300
waar indien succesvol, false als niet.

542
00:46:01,300 --> 00:46:06,270
Dus we willen controleren of de return waarde van foo waar of onwaar is.

543
00:46:06,270 --> 00:46:10,400
Als het valse, dat betekent dat we gaan willen een soort boodschap af te drukken

544
00:46:10,400 --> 00:46:14,390
en sluit het programma.

545
00:46:14,390 --> 00:46:18,530
Wat wij willen doen is controleren de return waarde van foo.

546
00:46:18,530 --> 00:46:23,310
Als foo false retourneren, dan weten we dat we een soort van fout is opgetreden

547
00:46:23,310 --> 00:46:25,110
en we moeten ons programma af te sluiten.

548
00:46:25,110 --> 00:46:35,600
Een manier om dit te doen is een aandoening waarbij de eigenlijke functie zelf is uw conditie.

549
00:46:35,600 --> 00:46:39,320
Zeg foo neemt in x.

550
00:46:39,320 --> 00:46:43,390
We kunnen als voorwaarde if (foo (x)).

551
00:46:43,390 --> 00:46:50,900
In principe, dat betekent dat als aan het einde van het uitvoeren van foo het true retourneert,

552
00:46:50,900 --> 00:46:57,390
dan kunnen we dit doen omdat de functie te evalueren foo

553
00:46:57,390 --> 00:47:00,500
om de gehele toestand te evalueren.

554
00:47:00,500 --> 00:47:06,500
Zo dan dat is hoe je iets kunt doen als de functie true teruggeeft en is succesvol.

555
00:47:06,500 --> 00:47:11,800
Maar als je foutcontrole, u alleen wilt stoppen als uw functie false retourneert.

556
00:47:11,800 --> 00:47:16,090
Wat je zou kunnen doen is gewoon voeg een == false of voeg gewoon een knal in de voorkant van het

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

558
00:47:21,010 --> 00:47:29,540
Binnen dat lichaam van die voorwaarde zou je alle foutafhandeling,

559
00:47:29,540 --> 00:47:36,940
zo graag, "Kan deze boom te creëren" en dan terug 1 of iets dergelijks.

560
00:47:36,940 --> 00:47:43,340
Wat dat doet, is echter dat, hoewel foo vals terug -

561
00:47:43,340 --> 00:47:46,980
Zeg foo true retourneert.

562
00:47:46,980 --> 00:47:51,060
Dan hoeft u niet opnieuw te bellen foo. Dat is een veel voorkomende misvatting.

563
00:47:51,060 --> 00:47:54,730
Omdat het in uw toestand, het is al geëvalueerd,

564
00:47:54,730 --> 00:47:59,430
zodat u al het resultaat als je het gebruik van make boom of iets dergelijks

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

566
00:48:01,840 --> 00:48:07,460
Het heeft al die waarde. Het is al uitgevoerd.

567
00:48:07,460 --> 00:48:10,730
Dus het is handig om Booleaanse functies te gebruiken als de conditie

568
00:48:10,730 --> 00:48:13,890
want of u daadwerkelijk uitvoeren van de body van de lus,

569
00:48:13,890 --> 00:48:18,030
het voert de functie toch.

570
00:48:22,070 --> 00:48:27,330
>> Onze voorlaatste stap is het schrijven van het bericht naar het bestand.

571
00:48:27,330 --> 00:48:33,070
Zodra we bouwen de Huffman boom, dan het schrijven van het bericht naar het bestand is vrij eenvoudig.

572
00:48:33,070 --> 00:48:39,260
Het is vrij eenvoudig nu volg gewoon de 0s en 1s.

573
00:48:39,260 --> 00:48:45,480
En dus volgens afspraak weten we dat in een Huffman boom de 0s wijzen links

574
00:48:45,480 --> 00:48:48,360
en 1s dan rechts.

575
00:48:48,360 --> 00:48:53,540
Dus dan kun je het lezen in beetje bij beetje, elke keer dat u een 0 krijgt

576
00:48:53,540 --> 00:48:59,100
volg je de linker tak, en dan elke keer dat u leest in een 1

577
00:48:59,100 --> 00:49:02,100
je gaat naar de juiste vestiging te volgen.

578
00:49:02,100 --> 00:49:07,570
En dan ga je verder tot je een blad

579
00:49:07,570 --> 00:49:11,550
omdat de bladeren gaan aan het einde van de takken.

580
00:49:11,550 --> 00:49:16,870
Hoe kunnen we zeggen of we slaan een blad of niet?

581
00:49:19,800 --> 00:49:21,690
We zeiden het al eerder.

582
00:49:21,690 --> 00:49:24,040
[Student] Als de wijzers NULL zijn. >> Ja.

583
00:49:24,040 --> 00:49:32,220
We kunnen zien of we slaan een blad als de verwijzingen naar zowel links en rechts bomen zijn NULL.

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

585
00:49:34,110 --> 00:49:40,320
We weten dat we willen in wat te lezen bij beetje in onze Huff bestand.

586
00:49:43,870 --> 00:49:51,220
Zoals we eerder zagen in dump.c, wat zij deden is dat ze in bit gelezen door boor in het Huff bestand

587
00:49:51,220 --> 00:49:54,560
en gewoon uitgeprint wat die stukjes waren.

588
00:49:54,560 --> 00:49:58,430
We gaan niet te doen. We gaan iets doen dat is een beetje complexer.

589
00:49:58,430 --> 00:50:03,620
Maar wat we kunnen doen is kunnen we dat stukje code die leest in de bit.

590
00:50:03,620 --> 00:50:10,250
Hier hebben we de integer bit die de huidige bit dat we op.

591
00:50:10,250 --> 00:50:15,520
Dit zorgt itereren alle bits in het bestand tot je het einde van het bestand.

592
00:50:15,520 --> 00:50:21,270
Op basis van dat, dan zul je wilt een soort van iterator hebben

593
00:50:21,270 --> 00:50:26,760
om uw boom te steken.

594
00:50:26,760 --> 00:50:31,460
En afhankelijk van of de bit 0 of 1 is,

595
00:50:31,460 --> 00:50:36,920
je gaat te willen dat iterator ofwel naar links of naar rechts te verplaatsen

596
00:50:36,920 --> 00:50:44,080
helemaal tot je een blad, zodat de hele weg tot dat knooppunt dat je op

597
00:50:44,080 --> 00:50:48,260
niet wijzen op enig meer knooppunten.

598
00:50:48,260 --> 00:50:54,300
Waarom kunnen we dit doen met een Huffman-bestand, maar niet Morse code?

599
00:50:54,300 --> 00:50:56,610
Omdat in morse is er een beetje van dubbelzinnigheid.

600
00:50:56,610 --> 00:51:04,440
We kunnen zijn als, oh wacht, we hebben een brief langs de weg raken, dus misschien is dit onze brief,

601
00:51:04,440 --> 00:51:08,150
terwijl als we verder gewoon een beetje langer, dan zouden we hebben geraakt een andere brief.

602
00:51:08,150 --> 00:51:13,110
Maar dat gaat niet gebeuren in Huffman codering,

603
00:51:13,110 --> 00:51:17,540
dus we kunnen er zeker van zijn dat de enige manier dat we gaan om een ​​teken te raken

604
00:51:17,540 --> 00:51:23,480
is als dat knooppunt links en rechts kinderen zijn NULL.

605
00:51:28,280 --> 00:51:32,350
>> Tot slot willen we alle van ons geheugen vrij te maken.

606
00:51:32,350 --> 00:51:37,420
We willen beide in de buurt van de Huff bestand dat we hebben te maken met

607
00:51:37,420 --> 00:51:41,940
alsmede verwijder alle van de bomen in onze bossen.

608
00:51:41,940 --> 00:51:46,470
Op basis van uw implementatie, ben je waarschijnlijk gaat te willen bellen bos te verwijderen

609
00:51:46,470 --> 00:51:49,780
in plaats van het daadwerkelijk gaan door alle bomen zelf.

610
00:51:49,780 --> 00:51:53,430
Maar als je geen tijdelijke bomen, wil je bevrijden dat.

611
00:51:53,430 --> 00:51:59,060
U kent uw code beste, zodat je weet waar je het toewijzen van geheugen.

612
00:51:59,060 --> 00:52:04,330
En dus als je in, begin met zelfs Controle F'ing voor malloc,

613
00:52:04,330 --> 00:52:08,330
zien wanneer u malloc en ervoor te zorgen dat je dat allemaal vrij

614
00:52:08,330 --> 00:52:10,190
maar dan gewoon door uw code,

615
00:52:10,190 --> 00:52:14,260
begrijpen waar u zou kunnen hebben toegewezen geheugen.

616
00:52:14,260 --> 00:52:21,340
Meestal kun je net zeggen: "Aan het einde van een bestand Ik ga naar het bos te verwijderen op mijn bos,"

617
00:52:21,340 --> 00:52:23,850
dus in principe duidelijk dat geheugen, vrij dat,

618
00:52:23,850 --> 00:52:28,310
"En dan ga ik ook naar het bestand te sluiten en mijn programma gaat om te stoppen."

619
00:52:28,310 --> 00:52:33,810
Maar is dat de enige keer dat het programma wordt afgesloten?

620
00:52:33,810 --> 00:52:37,880
Nee, want soms zijn er misschien wel een fout is gebeurd.

621
00:52:37,880 --> 00:52:42,080
Misschien kunnen we een bestand niet openen of we konden geen andere boom

622
00:52:42,080 --> 00:52:49,340
of een soort van fout is opgetreden in het geheugen toewijzing en dus het terug NULL.

623
00:52:49,340 --> 00:52:56,710
Er is een fout gebeurd en dan zijn we terug en stoppen.

624
00:52:56,710 --> 00:53:02,040
Dus dan wilt u ervoor zorgen dat eventuele tijd die uw programma kunnen stoppen,

625
00:53:02,040 --> 00:53:06,980
je wilt er bevrijden van al uw geheugen.

626
00:53:06,980 --> 00:53:13,370
Het is niet alleen zal zijn aan het einde van de belangrijkste functie die u uw code af te sluiten.

627
00:53:13,370 --> 00:53:20,780
Wil je terug kijken naar elke instantie dat uw code mogelijk voortijdig zou terugkeren

628
00:53:20,780 --> 00:53:25,070
en dan vrij wat geheugen zinvol.

629
00:53:25,070 --> 00:53:30,830
Stel dat je had gebeld om bos en dat geretourneerd valse.

630
00:53:30,830 --> 00:53:34,230
Dan zal je waarschijnlijk niet nodig hebt om uw bos te verwijderen

631
00:53:34,230 --> 00:53:37,080
omdat u nog niet over een bos.

632
00:53:37,080 --> 00:53:42,130
Maar op elk punt in de code waar u misschien voortijdig terug te keren

633
00:53:42,130 --> 00:53:46,160
wilt u ervoor zorgen dat u eventuele geheugen vrij te maken.

634
00:53:46,160 --> 00:53:50,020
>> Dus als we te maken hebben met het vrijmaken van geheugen en het hebben van mogelijke lekken,

635
00:53:50,020 --> 00:53:55,440
we willen niet alleen gebruik maken van ons oordeel en onze logica

636
00:53:55,440 --> 00:54:01,850
maar ook gebruik maken van Valgrind om te bepalen of we hebben allemaal van ons geheugen vrijgemaakt behoorlijk of niet.

637
00:54:01,850 --> 00:54:09,460
U kunt lopen Valgrind op Puff en dan moet je ook doorgeven

638
00:54:09,460 --> 00:54:14,020
het juiste aantal command-line argumenten Valgrind.

639
00:54:14,020 --> 00:54:18,100
U kunt dat, maar de output is een beetje cryptisch.

640
00:54:18,100 --> 00:54:21,630
We hebben gekregen een beetje aan gewend met Speller, maar we moeten nog steeds een beetje meer hulp,

641
00:54:21,630 --> 00:54:26,450
dus dan loopt het met een paar vlaggen, zoals de lek-check = vol,

642
00:54:26,450 --> 00:54:32,040
die waarschijnlijk zal ons wat meer nuttige output op Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Dan nog een handige tip als je debuggen is het diff commando.

644
00:54:39,040 --> 00:54:48,520
U kunt de medewerkers uitvoering van Huff, lopen dat op een tekstbestand,

645
00:54:48,520 --> 00:54:55,400
en dan uitvoeren naar een binair bestand, een binair bestand Huff, om precies te zijn.

646
00:54:55,400 --> 00:54:59,440
Dan als je je eigen bladerdeeg op die binair bestand,

647
00:54:59,440 --> 00:55:03,950
dan ideaal, wordt uw uitgestuurde tekstbestand zal identiek zijn

648
00:55:03,950 --> 00:55:08,200
naar de oorspronkelijke degene die je voorbij inch

649
00:55:08,200 --> 00:55:15,150
Hier ben ik met behulp van hth.txt als voorbeeld, en dat is degene over gesproken in uw spec.

650
00:55:15,150 --> 00:55:21,040
Dat is letterlijk HTH en dan een nieuwe regel.

651
00:55:21,040 --> 00:55:30,970
Maar zeker voel je vrij en bent u zeker aangemoedigd om langer voorbeelden te gebruiken

652
00:55:30,970 --> 00:55:32,620
voor uw tekst bestand.

653
00:55:32,620 --> 00:55:38,110
>> U kunt zelfs een schot op misschien het comprimeren en decomprimeren dan

654
00:55:38,110 --> 00:55:41,600
een aantal van de bestanden die u gebruikt in Speller, zoals Oorlog en Vrede

655
00:55:41,600 --> 00:55:46,710
of Jane Austen of zoiets - dat zou wel cool zijn - of Austin Powers,

656
00:55:46,710 --> 00:55:51,880
soort van omgaan met grotere bestanden, omdat we niet naar beneden komen om het

657
00:55:51,880 --> 00:55:55,590
Als we de volgende gereedschap hier, ls-l.

658
00:55:55,590 --> 00:56:01,150
We zijn gewend aan ls, die in feite alle inhoud geeft in onze huidige directory.

659
00:56:01,150 --> 00:56:07,860
Het passeren van de vlag-l eigenlijk wordt de grootte van deze bestanden.

660
00:56:07,860 --> 00:56:12,690
Als je door de PSET spec, het loopt eigenlijk u bij het maken van de binaire bestand,

661
00:56:12,690 --> 00:56:16,590
van hijgend, en zie je dat voor zeer kleine bestanden

662
00:56:16,590 --> 00:56:23,910
de ruimte kosten comprimeren en vertalen al die informatie

663
00:56:23,910 --> 00:56:26,980
van alle frequenties en dat soort dingen opweegt tegen het werkelijke voordeel

664
00:56:26,980 --> 00:56:30,000
comprimeren van het bestand in de eerste plaats.

665
00:56:30,000 --> 00:56:37,450
Maar als je het op een aantal langere tekstbestanden, dan kun je misschien zien dat je begint om wat voordeel te krijgen

666
00:56:37,450 --> 00:56:40,930
comprimeren in deze bestanden.

667
00:56:40,930 --> 00:56:46,210
>> En dan tot slot, hebben we onze oude vriend GDB, die zeker zal te pas komen.

668
00:56:48,360 --> 00:56:55,320
>> Hebben we misschien nog vragen over Huff bomen of het proces van het maken van de bomen

669
00:56:55,320 --> 00:56:58,590
of andere vragen over Huff'n Puff?

670
00:57:00,680 --> 00:57:02,570
Oke. Ik zal rond blijven voor een beetje.

671
00:57:02,570 --> 00:57:06,570
>> Bedankt, iedereen. Dit was Walkthrough 6. En veel geluk.

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