1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Návod - Problém Set 6]

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

3
00:00:04,810 --> 00:00:07,240
[To je CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Ahoj, všetci, vitajte na Walkthrough 6: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
V Puff Huff'n, čo robíme sa bude zaoberať súboru Huffman komprimovaného

6
00:00:17,440 --> 00:00:20,740
a potom nafukovanie ju späť hore, tak dekompresiu to,

7
00:00:20,740 --> 00:00:25,810
takže môžeme preložiť z 0s a 1s, že užívateľ odošle dotaz

8
00:00:25,810 --> 00:00:30,660
a previesť ho späť do pôvodného textu.

9
00:00:30,660 --> 00:00:34,360
Pset 6 bude celkom v pohode, pretože budete vidieť niektoré z nástrojov

10
00:00:34,360 --> 00:00:41,730
ktoré ste použili v PSet 4 a PSet 5 a druhu a zlúčiť ich do 1 pekne úhľadné koncepcie

11
00:00:41,730 --> 00:00:43,830
keď príde na to myslieť.

12
00:00:43,830 --> 00:00:50,110
>> Tiež, pravdepodobne, Pset 4 a 5 boli najnáročnejšie psets, ktoré sme mali ponúknuť.

13
00:00:50,110 --> 00:00:53,950
Takže od teraz, máme túto 1 väčšiu PSet v C,

14
00:00:53,950 --> 00:00:56,480
a potom po tom sme na programovanie pre web.

15
00:00:56,480 --> 00:01:02,310
Takže gratulujem seba pre prekonanie najťažšie hrb v CS50.

16
00:01:03,630 --> 00:01:09,760
>> Pohybujúce sa na pre Puff Huff'n, naše toolbox pre tento PSet sa bude Huffman stromy,

17
00:01:09,760 --> 00:01:14,700
takže pochopenie nielen ako binárne stromy prácu, ale aj špecificky Huffman stromy,

18
00:01:14,700 --> 00:01:16,240
ako to početne sú.

19
00:01:16,240 --> 00:01:20,210
A potom budeme mať veľa distribučné kódu v tomto PSet,

20
00:01:20,210 --> 00:01:22,480
a my prídeme vidieť, že skutočne niektoré z kódu

21
00:01:22,480 --> 00:01:24,670
by sme neboli schopní plne pochopiť ešte,

22
00:01:24,670 --> 00:01:30,080
a tak ti budú. c súbory, ale potom ich sprievod. h súbory

23
00:01:30,080 --> 00:01:34,300
nám dá dostatok pochopenia, že potrebujeme, aby sme vedeli, ako tieto funkcie pracujú

24
00:01:34,300 --> 00:01:38,100
alebo aspoň to, čo majú robiť - ich vstupov a výstupov -

25
00:01:38,100 --> 00:01:40,760
aj keď nevieme, čo sa deje v čiernej skrinke,

26
00:01:40,760 --> 00:01:44,090
alebo nechápu, čo sa deje v čiernej skrinke vnútri.

27
00:01:44,090 --> 00:01:49,400
A potom konečne, ako obvykle, máme čo do činenia s novými dátovými štruktúrami,

28
00:01:49,400 --> 00:01:51,840
špecifické typy uzlov, ktoré poukazujú na niektoré veci,

29
00:01:51,840 --> 00:01:56,080
a tak tu majú ceruzku a papier nielen pre návrhového procesu

30
00:01:56,080 --> 00:01:58,470
a keď sa snažíte prísť na to, ako vaše Pset by mal fungovať

31
00:01:58,470 --> 00:02:00,520
ale aj pri ladení.

32
00:02:00,520 --> 00:02:06,140
Môžete mať GDB vedľa vášho pera a papiera, zatiaľ čo vy sa stanovuje, aké hodnoty sú,

33
00:02:06,140 --> 00:02:09,320
, Kde sa vaše šípky smerujú, a podobné veci.

34
00:02:09,320 --> 00:02:13,720
>> Najprv sa pozrime na stromy Huffman.

35
00:02:13,720 --> 00:02:19,600
Huffman stromy sú binárne stromy, čo znamená, že každý uzol má len 2 deti.

36
00:02:19,600 --> 00:02:24,870
V stromov Huffman charakteristikou je, že najčastejšie hodnoty

37
00:02:24,870 --> 00:02:27,140
sú zastúpené najmenším počtom bitov.

38
00:02:27,140 --> 00:02:32,690
Videli sme v prednáškových príkladov Morseovej abecedy, aký druh konsolidovaných niektoré listy.

39
00:02:32,690 --> 00:02:38,030
Ak sa snažíte preložiť A alebo e, napríklad,

40
00:02:38,030 --> 00:02:43,940
ste prekladanie, že často, takže miesto by bolo nutné použiť kompletnú sadu bitov

41
00:02:43,940 --> 00:02:48,640
pridelené na toto obvyklého typu dát, skomprimovať ho do menej,

42
00:02:48,640 --> 00:02:53,730
a potom tie listy, ktoré sú zastúpené menej často sú zastúpené s dlhšími bitov

43
00:02:53,730 --> 00:02:59,840
pretože si to môžu dovoliť, že keď sa odváži frekvencie, ktoré tieto listy sa objaví.

44
00:02:59,840 --> 00:03:03,020
Máme rovnaký nápad tu na stromoch Huffman

45
00:03:03,020 --> 00:03:12,360
kde sme urobili reťaz, druh cesty sa dostať do niektorých postáv.

46
00:03:12,360 --> 00:03:14,470
A potom postavy, ktoré majú najväčšiu frekvenciu

47
00:03:14,470 --> 00:03:17,940
sa bude zastúpený s najmenším počtom bitov.

48
00:03:17,940 --> 00:03:22,020
>> Spôsob, akým si postaviť Huffman strom

49
00:03:22,020 --> 00:03:27,430
je tým všetky znaky, ktoré sa vyskytujú v texte

50
00:03:27,430 --> 00:03:30,630
a výpočet ich početnosť, ako často sa objavujú.

51
00:03:30,630 --> 00:03:33,880
To by mohlo byť buď počet, koľkokrát sa tieto listy sa objaví

52
00:03:33,880 --> 00:03:40,270
alebo možno percento zo všetkých postáv, koľko každý z nich objaví.

53
00:03:40,270 --> 00:03:44,270
A tak to, čo robíte, je, až budete mať všetky tieto zmapované,

54
00:03:44,270 --> 00:03:49,060
potom sa pozriete na 2 najnižších frekvencií a potom sa k nim pripojil ako súrodenci

55
00:03:49,060 --> 00:03:55,660
kde potom nadradený uzol má frekvenciu, ktorá je suma 2 deti.

56
00:03:55,660 --> 00:04:00,870
A potom sa podľa konvencie hovorí, že ľavý uzol,

57
00:04:00,870 --> 00:04:03,770
budete nasledovať, že po 0 vetva,

58
00:04:03,770 --> 00:04:08,140
a potom sa úplne vpravo uzol je 1 vetva.

59
00:04:08,140 --> 00:04:16,040
Ako sme videli v Morseova abeceda, ten Gotcha bolo, že ak ste mali len pípnutie a pípnutie

60
00:04:16,040 --> 00:04:18,120
to bol nejednoznačný.

61
00:04:18,120 --> 00:04:22,430
Mohlo by to byť buď 1 písmeno alebo to mohlo byť postupnosť 2 písmen.

62
00:04:22,430 --> 00:04:27,790
A tak to, čo Huffman stromy robí, je, pretože podľa povahy postáv

63
00:04:27,790 --> 00:04:34,140
alebo naše konečné skutočné postavy ako posledný uzly na pobočke -

64
00:04:34,140 --> 00:04:39,300
nazývame tie, ktoré sú listy - na základe, že nemôže byť akákoľvek nejednoznačnosť

65
00:04:39,300 --> 00:04:45,160
z hľadiska toho, ktoré písmeno sa snažíte enkódování s radom bitov

66
00:04:45,160 --> 00:04:50,670
pretože nikde pozdĺž bitov, ktoré predstavujú 1 písmeno

67
00:04:50,670 --> 00:04:55,960
stretnete ďalšie celý list, a tam nebudú žiadne zmätok tam.

68
00:04:55,960 --> 00:04:58,430
Ale pôjdeme do príklady, ktoré vy môžete skutočne vidieť, že

69
00:04:58,430 --> 00:05:02,120
miesto z nás len hovorím, že je to pravda.

70
00:05:02,120 --> 00:05:06,390
>> Poďme sa pozrieť na jednoduchý príklad stromu Huffman.

71
00:05:06,390 --> 00:05:09,380
Mám reťazec, ktorý je tu 12 znakov.

72
00:05:09,380 --> 00:05:14,010
Mám 4 As, 6 BS a 2 Čs.

73
00:05:14,010 --> 00:05:17,270
Môj prvý krok by bolo počítať.

74
00:05:17,270 --> 00:05:20,760
Koľkokrát sa objaví? Zdá sa, 4 krát v reťazci.

75
00:05:20,760 --> 00:05:25,060
B sa objaví 6 krát, a C sa objaví 2 krát.

76
00:05:25,060 --> 00:05:28,970
Samozrejme, budem hovoriť, že som pomocou B najčastejšie,

77
00:05:28,970 --> 00:05:35,970
tak chcem reprezentovať B s najmenším počtom bitov, pri menšom počte 0s a 1s.

78
00:05:35,970 --> 00:05:42,600
A potom som tiež bude očakávať C vyžadovať najväčšie množstvo 0s a 1s rovnako.

79
00:05:42,600 --> 00:05:48,550
Prvé, čo som urobil je tu som umiestnil je vo vzostupnom poradí podľa frekvencie.

80
00:05:48,550 --> 00:05:52,710
Vidíme, že C a A, ktoré sú naše 2 najnižších frekvencií.

81
00:05:52,710 --> 00:06:00,290
Máme vytvoriť nadradený uzol, a že nadradený uzol nemá písmeno s ním spojené,

82
00:06:00,290 --> 00:06:05,070
ale má frekvenciu, ktorá je súčtom.

83
00:06:05,070 --> 00:06:08,780
Súčet stane 2 + 4, čo je 6.

84
00:06:08,780 --> 00:06:10,800
Potom sa vydáme po ľavej vetva.

85
00:06:10,800 --> 00:06:14,970
Ak sme boli v tej 6 uzla, potom by sme nasledovať 0 dostať sa do C

86
00:06:14,970 --> 00:06:17,450
a potom 1 sa dostať do A.

87
00:06:17,450 --> 00:06:20,300
Takže teraz máme 2 uzly.

88
00:06:20,300 --> 00:06:23,920
Máme hodnotu 6 a potom aj ďalšie uzol s hodnotou 6.

89
00:06:23,920 --> 00:06:28,550
A tak tí, 2 nie sú len 2 najnižšia, ale tiež len 2, ktoré sú vľavo,

90
00:06:28,550 --> 00:06:33,820
tak sme pripojiť sa k tým iným rodičom, s súčet je 12.

91
00:06:33,820 --> 00:06:36,300
Takže tu máme Huffmanova stromu

92
00:06:36,300 --> 00:06:40,020
kde sa dostať do B, to by bolo jednoducho bit 1

93
00:06:40,020 --> 00:06:45,430
a potom sa dostať do budeme mať 01, a potom C s 00.

94
00:06:45,430 --> 00:06:51,300
Takže tu vidíme, že v podstate sme zastupujúci tieto znaky s 1 alebo 2 bity

95
00:06:51,300 --> 00:06:55,160
kde B, ako predpovedal, má najmenej.

96
00:06:55,160 --> 00:07:01,730
A potom sme očakávali C majú najviac, ale pretože je to taký malý Huffman strom,

97
00:07:01,730 --> 00:07:06,020
potom je tiež reprezentovaná 2 bitov oproti niekde uprostred.

98
00:07:07,820 --> 00:07:11,070
>> Stačí si prejsť ďalšie jednoduchý príklad stromu Huffman,

99
00:07:11,070 --> 00:07:19,570
že máte reťazec "Hello."

100
00:07:19,570 --> 00:07:25,360
Čo urobíte ako prvé by ste povedať, ako koľkokrát sa H objaviť v tomto?

101
00:07:25,360 --> 00:07:34,200
H sa objaví raz a potom e sa objaví raz a potom sme l objavilo dvakrát

102
00:07:34,200 --> 00:07:36,580
a o objavujú raz.

103
00:07:36,580 --> 00:07:44,310
A potom sa môžeme očakávať, ktoré písmeno bude zastúpená najmenším počtom bitov?

104
00:07:44,310 --> 00:07:47,450
[Študent] l >> L. Jo. l má pravdu.

105
00:07:47,450 --> 00:07:50,730
Predpokladáme l byť zastúpený najmenším počtom bitov

106
00:07:50,730 --> 00:07:55,890
preto, že som sa používa najčastejšie v reťazci "Hello."

107
00:07:55,890 --> 00:08:04,280
Čo budem robiť, teraz je čerpať z týchto uzlov.

108
00:08:04,280 --> 00:08:15,580
Mám 1, ktorý je H, a potom ešte 1, čo je e, a potom sa 1, čo je o -

109
00:08:15,580 --> 00:08:23,410
teraz som nastavenie - a potom 2, ktorý je l

110
00:08:23,410 --> 00:08:32,799
Potom som povedal tak, že som postaviť Huffman strom je nájsť 2 uzly s najmenej frekvenciou

111
00:08:32,799 --> 00:08:38,010
a aby im súrodencov vytvorením nadradený uzol.

112
00:08:38,010 --> 00:08:41,850
Tu máme 3 uzly s najnižšou frekvenciou. Všetci sú 1.

113
00:08:41,850 --> 00:08:50,620
Tak tu sme si vybrať, ktorý z nich budeme prepojiť prvý.

114
00:08:50,620 --> 00:08:54,850
Povedzme, že som si vybrať H a E.

115
00:08:54,850 --> 00:09:01,150
Súčet 1 + 1 = 2, ale tento uzol nemá písmeno s ním spojené.

116
00:09:01,150 --> 00:09:04,440
Je to len má hodnotu.

117
00:09:04,440 --> 00:09:10,950
Teraz sa pozrieme na ďalšie 2 najnižších frekvencií.

118
00:09:10,950 --> 00:09:15,590
To je 2 a 1. To by mohlo byť jedným z tých 2, ale budem si vybrať tento jeden.

119
00:09:15,590 --> 00:09:18,800
Súčet je 3.

120
00:09:18,800 --> 00:09:26,410
A potom konečne, mám len 2 vľavo, tak potom to bude 5.

121
00:09:26,410 --> 00:09:32,010
Potom tu, ako sa očakávalo, keď som vyplniť kódovanie pre to,

122
00:09:32,010 --> 00:09:37,480
1s sa vždy ten správny odbor a 0s je ľavá.

123
00:09:37,480 --> 00:09:45,880
Potom máme l reprezentovaný iba 1 bit a potom na Õ 2

124
00:09:45,880 --> 00:09:52,360
a potom sa e o 2 a potom H klesá na 3 bitov.

125
00:09:52,360 --> 00:09:59,750
Takže môžete prenášať túto správu "Hello" namiesto skutočne použitie znakov

126
00:09:59,750 --> 00:10:02,760
len o 0s a 1s.

127
00:10:02,760 --> 00:10:07,910
Pamätajte však, že v niekoľkých prípadoch sme mali vzťahy s našou frekvenciou.

128
00:10:07,910 --> 00:10:11,900
Mohli sme buď pripojil k H a o Prvá možná.

129
00:10:11,900 --> 00:10:15,730
Alebo potom o niečo neskôr, keď sme mali l predstavované 2

130
00:10:15,730 --> 00:10:19,410
, Ako aj pripojil ktoré reprezentuje 2, mohli sme spojené buď jeden.

131
00:10:19,410 --> 00:10:23,630
>> A tak, keď pošlete 0s a 1s, že v skutočnosti nezaručuje

132
00:10:23,630 --> 00:10:27,090
že príjemca môže plne čítať správy hneď bat

133
00:10:27,090 --> 00:10:30,490
pretože nemusí vedieť, kedy rozhodnutie ste urobili.

134
00:10:30,490 --> 00:10:34,920
Takže keď máme čo do činenia s kompresiou Huffman,

135
00:10:34,920 --> 00:10:40,090
nejako musíme povedať príjemcu nášho posolstva, ako sme sa rozhodli -

136
00:10:40,090 --> 00:10:43,470
Potrebujú vedieť, nejaké ďalšie informácie

137
00:10:43,470 --> 00:10:46,580
okrem správy stlačeného vzduchu.

138
00:10:46,580 --> 00:10:51,490
Je potrebné, aby pochopili, čo strom vlastne vyzerá,

139
00:10:51,490 --> 00:10:55,450
ako sme vlastne robil tie rozhodnutia.

140
00:10:55,450 --> 00:10:59,100
>> Tu sme robili len to, príklady založené na skutočnej počtu,

141
00:10:59,100 --> 00:11:01,550
ale niekedy môže mať tiež Huffman strom

142
00:11:01,550 --> 00:11:05,760
na základe frekvenciu, pri ktorej sa objavia písmená, a to je presne rovnaký proces.

143
00:11:05,760 --> 00:11:09,090
Tu som vyjadriť to v percentách alebo zlomkom

144
00:11:09,090 --> 00:11:11,290
a tak tu presne to isté.

145
00:11:11,290 --> 00:11:15,300
Zistil som, 2 najnižšej, zhrnúť je, ďalšie 2 najnižšej, zhrnúť je,

146
00:11:15,300 --> 00:11:19,390
až budem mať plnú strom.

147
00:11:19,390 --> 00:11:23,610
Aj keď by sme mohli urobiť to buď tak, keď máme čo do činenia s percentami,

148
00:11:23,610 --> 00:11:27,760
to znamená, že sme rozdelenie veci a nakladanie s desatinných miest, či skôr pláva

149
00:11:27,760 --> 00:11:30,900
ak budeme premýšľať o dátových štruktúr hlavy.

150
00:11:30,900 --> 00:11:32,540
Čo vieme o plaváky?

151
00:11:32,540 --> 00:11:35,180
Čo je to bežný problém, kedy máme čo do činenia s plavákmi?

152
00:11:35,180 --> 00:11:38,600
[Študent] Nepresné aritmetika. Jo >>. Nepresnosť.

153
00:11:38,600 --> 00:11:43,760
Vzhľadom k tomu, v pohyblivej rádovej čiarke nepresnosti, pre tento PSet tak, že sa uistiť,

154
00:11:43,760 --> 00:11:49,450
že aby sme nestratili žiadne hodnoty, potom sme vlastne bude rokovať s grófom.

155
00:11:49,450 --> 00:11:54,880
Takže ak ste mali myslieť na uzle Huffman, keď sa pozriete späť do štruktúry tu,

156
00:11:54,880 --> 00:12:01,740
keď sa pozriete na zelených má frekvenciu s ním spojené

157
00:12:01,740 --> 00:12:08,760
rovnako ako to ukazuje na uzol na jeho ľavej strane, rovnako ako uzol na jeho pravej strane.

158
00:12:08,760 --> 00:12:13,970
Potom červený ty tam tiež majú charakter sú s nimi spojené.

159
00:12:13,970 --> 00:12:18,900
Nebudeme robiť samostatné tie pre rodičov a potom koncových uzlov,

160
00:12:18,900 --> 00:12:23,680
ktoré označujeme ako listy, ale skôr tých budú musieť len hodnoty NULL.

161
00:12:23,680 --> 00:12:31,050
Pre každý uzol budeme mať charakter, symbol, že uzol reprezentuje,

162
00:12:31,050 --> 00:12:40,490
potom frekvencie, rovnako ako ukazovateľ na jeho ľavej dieťa, rovnako ako jeho pravé dieťa.

163
00:12:40,490 --> 00:12:45,680
Listy, ktoré sú na samom dne, by tiež mať uzlov odkazy

164
00:12:45,680 --> 00:12:49,550
po ich ľavici a ich práva, ale pretože tieto hodnoty nie sú poukazom na skutočné uzly,

165
00:12:49,550 --> 00:12:53,970
čo by ich hodnota bola? >> [Študent] NULL. >> NULL. Presne tak.

166
00:12:53,970 --> 00:12:58,430
Tu je príklad toho, ako by sa vám mohol predstavovať frekvenciu v plaváky,

167
00:12:58,430 --> 00:13:02,130
ale budeme rokovať s ním s celými číslami,

168
00:13:02,130 --> 00:13:06,780
takže všetko, čo urobil, je zmeniť dátový typ tam.

169
00:13:06,780 --> 00:13:09,700
>> Poďme na trochu viac komplexný príklad.

170
00:13:09,700 --> 00:13:13,360
Ale teraz, keď sme urobili jednoduché ty, je to len rovnaký proces.

171
00:13:13,360 --> 00:13:20,290
Môžete nájsť 2 najnižších kmitočtov, sčítať frekvencia

172
00:13:20,290 --> 00:13:22,450
a to je nová frekvencia vášho nadradeného uzla,

173
00:13:22,450 --> 00:13:29,310
ktorý potom ukazuje na jeho ľavej strane s 0 pobočky a právo s 1 pobočkou.

174
00:13:29,310 --> 00:13:34,200
Ak máme reťazec "To je cs50," potom budeme počítať, koľkokrát je T uvedené,

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

176
00:13:38,420 --> 00:13:42,010
Potom to, čo som urobil tu je s červenými uzlami som zasadil,

177
00:13:42,010 --> 00:13:48,530
Povedal som, že budem mať tieto znaky nakoniec na dne môjho stromu.

178
00:13:48,530 --> 00:13:51,740
Tí sa bude všetkých listov.

179
00:13:51,740 --> 00:13:58,200
Potom to, čo som urobil je, že som zoradené podľa frekvencie vo vzostupnom poradí,

180
00:13:58,200 --> 00:14:02,950
a to je vlastne spôsob, akým Pset kód robí

181
00:14:02,950 --> 00:14:07,550
Je to druhy to tým, že frekvencia a potom podľa abecedy.

182
00:14:07,550 --> 00:14:13,870
Tak to má čísla a potom abecedne podľa frekvencie.

183
00:14:13,870 --> 00:14:18,520
Tak čo by som urobil je, že som sa nájsť 2 najnižšej. To je 0 a 5.

184
00:14:18,520 --> 00:14:22,390
Chcel by som zhrnúť je, a to je 2. Potom by som pokračovať, nájsť ďalšie 2 najnižšej.

185
00:14:22,390 --> 00:14:26,100
To sú dva 1s, a potom tie, s 2, ako.

186
00:14:26,100 --> 00:14:31,570
Teraz viem, že môj ďalší krok bude sa pripojí najnižšie číslo,

187
00:14:31,570 --> 00:14:41,380
ktoré je T, 1, a potom výberom jedného z uzlov, ktoré má dve ako frekvencie.

188
00:14:41,380 --> 00:14:44,560
Takže tu máme 3 možnosti.

189
00:14:44,560 --> 00:14:47,980
Čo budem robiť po snímke je len vizuálne zmeniť ich poradie pre vás

190
00:14:47,980 --> 00:14:51,790
takže môžete vidieť, ako som buduje.

191
00:14:51,790 --> 00:14:59,040
Čo sa kód a vaša distribúcia kód bude robiť by sa pripojiť k T jeden

192
00:14:59,040 --> 00:15:01,410
s 0 a 5 uzla.

193
00:15:01,410 --> 00:15:05,060
Takže, že sumy až 3, a potom budeme pokračovať v procese.

194
00:15:05,060 --> 00:15:08,660
The 2 a 2 sú teraz najnižšie, takže potom tie Čiastka 4.

195
00:15:08,660 --> 00:15:12,560
Každý po tak ďaleko? Dobre.

196
00:15:12,560 --> 00:15:16,410
Potom po tom máme 3 a 3, ktoré je potrebné sčítať,

197
00:15:16,410 --> 00:15:21,650
takže opäť som len prepínanie to tak, že môžete vidieť vizuálne tak, že to nie je príliš komplikovaná.

198
00:15:21,650 --> 00:15:25,740
Potom máme 6, a potom sa naše posledný krok je teraz, že máme len 2 uzly

199
00:15:25,740 --> 00:15:30,440
Zhrnieme tie, aby sa koreň nášho stromu, čo je 10.

200
00:15:30,440 --> 00:15:34,100
A číslo 10 dáva zmysel, pretože každý uzol predstavuje,

201
00:15:34,100 --> 00:15:40,750
ich hodnota, ich početnosť číslo, bolo koľkokrát sa objavili v reťazci,

202
00:15:40,750 --> 00:15:46,350
a potom máme 5 znakov v našom reťazci, tak to dáva zmysel.

203
00:15:48,060 --> 00:15:52,320
Ak sa pozrieme na to, ako sa budeme skutočne zakódovať,

204
00:15:52,320 --> 00:15:56,580
podľa očakávania, i a y, ktoré sa objavujú najčastejšie

205
00:15:56,580 --> 00:16:01,350
sú zastúpené najmenším počtom bitov.

206
00:16:03,660 --> 00:16:05,660
>> Buďte opatrní.

207
00:16:05,660 --> 00:16:09,780
V stromov Huffman prípad skutočne záleží.

208
00:16:09,780 --> 00:16:13,670
Veľká S sa líši malým s

209
00:16:13,670 --> 00:16:21,260
Ak by sme mali "To je CS50" s veľkými písmenami, potom malá s by sa zobrazí iba dvakrát,

210
00:16:21,260 --> 00:16:27,120
by uzol s 2 ako jeho hodnotu, a potom sa veľká S by iba raz.

211
00:16:27,120 --> 00:16:33,440
Takže váš strom by sa zmenili štruktúry, pretože máte skutočne zvláštny list tu.

212
00:16:33,440 --> 00:16:36,900
Ale suma bude stále 10.

213
00:16:36,900 --> 00:16:39,570
To je to, čo sme vlastne bude volať kontrolný súčet,

214
00:16:39,570 --> 00:16:44,060
pridanie všetkých smeroch.

215
00:16:46,010 --> 00:16:50,990
>> Teraz, keď sme prebrali Huffman stromy, môžeme sa ponoriť do Puff Huff'n sa PSet.

216
00:16:50,990 --> 00:16:52,900
Budeme začať s časťou otázok,

217
00:16:52,900 --> 00:16:57,990
a to bude vám zvyknutí s binárnymi stromami a ako pracovať okolo toho:

218
00:16:57,990 --> 00:17:03,230
kreslenie uzly, vytvoriť si vlastný typedef struct pre uzol,

219
00:17:03,230 --> 00:17:07,230
a vidieť, ako by ste mohli vložiť do binárneho stromu, jeden, ktorý je zoradená,

220
00:17:07,230 --> 00:17:09,050
kríženie je, a podobné veci.

221
00:17:09,050 --> 00:17:14,560
Že vedomosti sa určite pomôže, keď sa ponoríte do časti Puff Huff'n

222
00:17:14,560 --> 00:17:17,089
z PSet.

223
00:17:19,150 --> 00:17:26,329
V štandardnom vydaní PSet, vašou úlohou je realizovať Puff,

224
00:17:26,329 --> 00:17:30,240
a vo hacker verzii vašou úlohou je realizovať Huff.

225
00:17:30,240 --> 00:17:38,490
Čo Huff robí, je, že trvá textu a potom to prekladá do 0s a 1s,

226
00:17:38,490 --> 00:17:41,990
tak proces, ktorý sme urobili vyššie, kde sme napočítali frekvencie

227
00:17:41,990 --> 00:17:50,970
a potom sa na strom a potom povedal: "Ako sa dostanem T?"

228
00:17:50,970 --> 00:17:54,840
T je zastúpená 100, a podobné veci,

229
00:17:54,840 --> 00:17:58,860
a potom Huff by sa text a potom výstupné že binárne.

230
00:17:58,860 --> 00:18:04,920
Ale aj preto, že vieme, že chceme, aby náš príjemcu správy

231
00:18:04,920 --> 00:18:11,790
znovu presne rovnaký strom, ale tiež obsahuje informácie o frekvenčných počíta.

232
00:18:11,790 --> 00:18:17,980
Potom sa Puff je nám daný binárny súbor 0s a 1s

233
00:18:17,980 --> 00:18:21,740
a vzhľadom k tomu aj informácie o frekvenciách.

234
00:18:21,740 --> 00:18:26,740
Prekladáme všetky tie 0s a 1s späť do pôvodnej správy, ktorá bola,

235
00:18:26,740 --> 00:18:29,350
takže sme dekompresie, že.

236
00:18:29,350 --> 00:18:36,450
Ak robíte štandardnej edícii, nemusíte vykonávať Huff,

237
00:18:36,450 --> 00:18:39,290
takže potom stačí použiť zamestnancov vykonávanie Huff.

238
00:18:39,290 --> 00:18:42,080
Tam sú inštrukcie v spec o tom, ako to urobiť.

239
00:18:42,080 --> 00:18:48,780
Môžete spustiť zamestnanca vykonávanie Huff na určité textového súboru

240
00:18:48,780 --> 00:18:53,270
a potom použiť tento výstup ako vstup Puff.

241
00:18:53,270 --> 00:18:59,330
>> Ako som už spomenul predtým, máme veľa distribúcie kódu pre tento jeden.

242
00:18:59,330 --> 00:19:01,810
Chystám sa začať chodiť cez neho.

243
00:19:01,810 --> 00:19:04,400
Budem tráviť väčšinu času na. H súbory

244
00:19:04,400 --> 00:19:07,660
pretože v súbory C, pretože máme. H

245
00:19:07,660 --> 00:19:11,650
a že nám poskytuje prototypy funkcií,

246
00:19:11,650 --> 00:19:15,520
nemáme plne nutné presne pochopiť -

247
00:19:15,520 --> 00:19:20,280
Ak nechcete pochopiť, čo sa deje v Súbory C, potom sa nemusíte starať moc,

248
00:19:20,280 --> 00:19:23,600
ale rozhodne skúste sa pozrieť, pretože by to mohlo dať nejaké rady

249
00:19:23,600 --> 00:19:29,220
a je užitočné si zvyknúť na čítanie kódu iných ľudí.

250
00:19:38,940 --> 00:19:48,270
>> Pri pohľade na huffile.h, do komentárov, že deklaruje vrstvu abstrakcie pre Huffman-kódované súbory.

251
00:19:48,270 --> 00:20:01,660
Ak pôjdeme dole, vidíme, že je maximálne 256 znakov, ktoré by sme mohli potrebovať kódy.

252
00:20:01,660 --> 00:20:05,480
To zahŕňa všetky písmená abecedy - veľká a malá -

253
00:20:05,480 --> 00:20:08,250
a potom symboly a čísla, atď

254
00:20:08,250 --> 00:20:11,930
Potom tu máme magic number, ktorý stanovil Huffman kódovaný súbor.

255
00:20:11,930 --> 00:20:15,890
V rámci kódu Huffman, že budeš mať určitý magické číslo

256
00:20:15,890 --> 00:20:18,560
spojený s hlavičky.

257
00:20:18,560 --> 00:20:21,110
To môže vyzerať ako len náhodné magické číslo,

258
00:20:21,110 --> 00:20:27,160
ale ak ste skutočne preložiť do ASCII, potom to vlastne vysvetľuje nahnevať.

259
00:20:27,160 --> 00:20:34,290
Tu máme struct pre Huffman kódovanie súboru.

260
00:20:34,290 --> 00:20:39,670
Je tu všetky tieto charakteristiky spojené so súborom Huff.

261
00:20:39,670 --> 00:20:47,080
Potom tu máme hlavičku pre súbor Huff, tak hovoríme, že Huffeader

262
00:20:47,080 --> 00:20:50,810
namiesto pridanie ďalšej h, pretože to znie rovnako tak.

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

264
00:20:52,720 --> 00:20:57,790
Máme kúzelné číslo s ním spojené.

265
00:20:57,790 --> 00:21:09,040
Ak je to skutočný Huff súbor, to bude číslo hore, to kúzlo jeden.

266
00:21:09,040 --> 00:21:14,720
A potom to bude mať pole.

267
00:21:14,720 --> 00:21:18,750
Tak pre každý symbol, ktorý je 256,

268
00:21:18,750 --> 00:21:24,760
bude to zoznam toho, čo frekvencia týchto symbolov je v súbore Huff.

269
00:21:24,760 --> 00:21:28,090
A potom konečne, máme kontrolný súčet frekvencií,

270
00:21:28,090 --> 00:21:32,160
, Ktoré by mali byť súčet týchto frekvencií.

271
00:21:32,160 --> 00:21:36,520
Tak to je to, čo Huffeader je.

272
00:21:36,520 --> 00:21:44,600
Potom máme niektoré funkcie, ktoré vracajú ďalšie bit v súbore Huff

273
00:21:44,600 --> 00:21:52,580
rovnako ako zapíše bit súboru Huff, a potom sa táto funkcia tu, hfclose,

274
00:21:52,580 --> 00:21:54,650
ktoré skutočne zavrie súbor Huff.

275
00:21:54,650 --> 00:21:57,290
Skôr sme sa zaoberali priamo len fclose,

276
00:21:57,290 --> 00:22:01,190
ale keď máte súbor Huff, namiesto toho, aby ju fclosing

277
00:22:01,190 --> 00:22:06,080
čo ste vlastne robiť, je hfclose a hfopen ju.

278
00:22:06,080 --> 00:22:13,220
To sú špecifické funkcie Huffová súbory, ktoré budeme sa zaoberať.

279
00:22:13,220 --> 00:22:19,230
Potom tu čítame v hlavičke a potom písať hlavičky.

280
00:22:19,230 --> 00:22:25,700
>> Len tým, že čítanie. H súbor môžeme trochu získať pocit z toho, čo súbor Huff môže byť,

281
00:22:25,700 --> 00:22:32,480
aké vlastnosti má, bez toho by sa skutočne ísť do huffile.c,

282
00:22:32,480 --> 00:22:36,750
ktoré, ak by sme ponoriť, bude trochu zložitejšie.

283
00:22:36,750 --> 00:22:41,270
Má všetky súboru I / O tú sa zaoberá ukazovateľmi.

284
00:22:41,270 --> 00:22:48,010
Tu vidíme, že keď voláme hfread, napríklad, je to stále vysporiadava s fread.

285
00:22:48,010 --> 00:22:53,050
Nie sme zbaviť týchto funkcií úplne, ale posielame, ktoré majú byť postarané

286
00:22:53,050 --> 00:22:59,760
vnútri súboru Huff miesto robí všetko pre to sami.

287
00:22:59,760 --> 00:23:02,300
Môžete pokojne prehľadá to, ak ste zvedaví,

288
00:23:02,300 --> 00:23:08,410
a ísť a kôra vrstve zadnej trochu.

289
00:23:20,650 --> 00:23:24,060
>> Ďalší obrázok, ktorý budeme pozrieť sa na tree.h.

290
00:23:24,060 --> 00:23:30,210
Pred v Walkthrough skĺzne sme povedali, očakávame Huffmanova uzol

291
00:23:30,210 --> 00:23:32,960
a urobili sme typedef struct uzol.

292
00:23:32,960 --> 00:23:38,360
Očakávame, že majú symbol, frekvencia, a potom 2 uzlov hviezdy.

293
00:23:38,360 --> 00:23:41,870
V tomto prípade, čo robíme, je to v podstate rovnaký

294
00:23:41,870 --> 00:23:46,880
okrem namiesto uzla budeme nazývať stromy.

295
00:23:48,790 --> 00:23:56,760
Máme funkciu, ktorá pri volaní, aby strom to vráti vám strom ukazovateľ.

296
00:23:56,760 --> 00:24:03,450
Späť na Speller, keď ste robili nový uzol

297
00:24:03,450 --> 00:24:11,410
ste povedal uzol * nové slovo = malloc (sizeof) a podobné veci.

298
00:24:11,410 --> 00:24:17,510
V podstate, mktree sa bude zaoberať, že pre vás.

299
00:24:17,510 --> 00:24:20,990
Podobne, ak chcete odstrániť strom,

300
00:24:20,990 --> 00:24:24,810
tak to je v podstate uvoľnenie strom, keď ste s ním urobil,

301
00:24:24,810 --> 00:24:33,790
miesto aby bol explicitne volať zadarmo na to, že ste v skutočnosti len tak použiť funkciu rmtree

302
00:24:33,790 --> 00:24:40,360
kde odovzdáte ukazovateľ na daný strom a potom tree.c sa postará o to pre vás.

303
00:24:40,360 --> 00:24:42,490
>> Pozeráme sa do tree.c.

304
00:24:42,490 --> 00:24:47,240
Očakávame, že rovnaké funkcie, okrem nedočkalo realizácie rovnako.

305
00:24:47,240 --> 00:24:57,720
Ako sme očakávali, keď budete volať mktree to mallocs veľkosti stromu do ukazovatele,

306
00:24:57,720 --> 00:25:03,190
inicializuje všetky hodnoty s hodnotou NULL, takže 0s alebo hodnoty Null,

307
00:25:03,190 --> 00:25:08,280
a vráti ukazovateľ na daný strom, ktorý ste práve malloc'd pre vás.

308
00:25:08,280 --> 00:25:13,340
Tu, keď zavoláte odstrániť strom najprv zaistí, že nie ste double uvoľnenie.

309
00:25:13,340 --> 00:25:18,320
To zaisťuje, že budete mať v skutočnosti strom, ktorý chcete odstrániť.

310
00:25:18,320 --> 00:25:23,330
Tu pretože strom aj svoje deti,

311
00:25:23,330 --> 00:25:29,560
Čo to však je, že vyžaduje rekurzívne odstrániť strom na ľavej uzol stromu

312
00:25:29,560 --> 00:25:31,650
, Ako aj na pravej uzla.

313
00:25:31,650 --> 00:25:37,790
Pred tým, než sa uvoľní rodičia, treba oslobodiť deti rovnako.

314
00:25:37,790 --> 00:25:42,770
Parent je tiež zameniteľný s koreňom.

315
00:25:42,770 --> 00:25:46,500
Vôbec prvý rodič, tak ako pra-pra-pra-pra-pradedo

316
00:25:46,500 --> 00:25:52,130
alebo babička strom, musíme najprv uvoľniť sa ustanovujú úrovne prvý.

317
00:25:52,130 --> 00:25:58,490
Takže traverz až na dno, bez tých, a potom sa vrátiť nahor, bez tých, atď

318
00:26:00,400 --> 00:26:02,210
Tak to je strom.

319
00:26:02,210 --> 00:26:04,240
>> Teraz sa pozrieme na les.

320
00:26:04,240 --> 00:26:09,860
Forest je miesto, kde môžete umiestniť všetky svoje stromy Huffman.

321
00:26:09,860 --> 00:26:12,910
Je to tým, že budeme mať niečo ako plot

322
00:26:12,910 --> 00:26:22,320
, Ktorý obsahuje ukazovateľ na strom, rovnako ako ukazovateľ na pozemku s názvom ďalšie.

323
00:26:22,320 --> 00:26:28,480
Aká štruktúra sa tento druh vyzerať?

324
00:26:29,870 --> 00:26:32,490
Je to druh to hovorí tam.

325
00:26:34,640 --> 00:26:36,700
Priamo tu.

326
00:26:37,340 --> 00:26:39,170
Spájať zoznam.

327
00:26:39,170 --> 00:26:44,590
Vidíme, že keď máme pozemok je to ako prepojeného zoznamu parciel.

328
00:26:44,590 --> 00:26:53,020
Les je definovaný ako prepojeného zoznamu pozemkov,

329
00:26:53,020 --> 00:26:58,100
a tak štruktúra lesov je budeme jednoducho musieť ukazovateľ na našu prvú pozemku

330
00:26:58,100 --> 00:27:02,740
a že pozemok má strom v ňom, alebo skôr poukazuje k stromu

331
00:27:02,740 --> 00:27:06,190
a potom sa odkazuje na nasledujúce pozemku, tak ďalej a tak ďalej.

332
00:27:06,190 --> 00:27:11,100
Ak chcete les hovoríme mkforest.

333
00:27:11,100 --> 00:27:14,930
Potom máme niektoré docela užitočné funkcie tu.

334
00:27:14,930 --> 00:27:23,240
Máme vybrať, kde odovzdáte v lese a potom je návratová hodnota Tree *,

335
00:27:23,240 --> 00:27:25,210
ukazovateľ na strom.

336
00:27:25,210 --> 00:27:29,370
Čo pick bude robiť, je, že pôjde do lesa, že ste ukázal na

337
00:27:29,370 --> 00:27:35,240
potom odstráňte strom s najnižším kmitočtu z toho lesa

338
00:27:35,240 --> 00:27:38,330
a potom vám ukazovateľ na ten strom.

339
00:27:38,330 --> 00:27:43,030
Akonáhle zavoláte vybrať, bude sa strom neexistuje v lese už,

340
00:27:43,030 --> 00:27:48,550
ale návratová hodnota je ukazovateľ na ten strom.

341
00:27:48,550 --> 00:27:50,730
Potom máte rastlinu.

342
00:27:50,730 --> 00:27:57,420
Za predpokladu, že odovzdáte ukazovateľ na strom, ktorý má non-0 frekvenciu,

343
00:27:57,420 --> 00:28:04,040
čo rastlina bude robiť, je, že bude trvať do lesa, sa strom, a závod, ktorý strom vnútri lesa.

344
00:28:04,040 --> 00:28:06,370
Tu máme rmforest.

345
00:28:06,370 --> 00:28:11,480
Podobné odstrániť strom, ktorý v podstate oslobodil všetky z našich stromov pre nás,

346
00:28:11,480 --> 00:28:16,600
odobrať les slobodná vôľa všetko obsiahnuté v tomto lese.

347
00:28:16,600 --> 00:28:24,890
>> Ak sa pozrieme do forest.c, budeme očakávať, že aspoň 1 rmtree príkaz tam,

348
00:28:24,890 --> 00:28:30,090
pretože na voľnej pamäte v lese, ak les má stromy v ňom,

349
00:28:30,090 --> 00:28:32,930
potom nakoniec budete musieť odstrániť tie stromy taky.

350
00:28:32,930 --> 00:28:41,020
Ak sa pozrieme do forest.c, máme mkforest, čo je, ako sme očakávali.

351
00:28:41,020 --> 00:28:42,890
My malloc veci.

352
00:28:42,890 --> 00:28:51,740
Sme inicializácii prvý pozemok v lese ako NULL, pretože je prázdna začať,

353
00:28:51,740 --> 00:29:05,940
potom vidíme, vybrať, ktoré vracia strom s najnižšou váhou, najnižšia frekvencia,

354
00:29:05,940 --> 00:29:13,560
a potom zbaví daného uzla, ktorý odkazuje na ten strom a ďalšia skladba,

355
00:29:13,560 --> 00:29:16,760
tak to trvá, že z prepojeného zoznamu lesa.

356
00:29:16,760 --> 00:29:24,510
A potom tu máme závod, ktorý vloží stromu do prepojeného zoznamu.

357
00:29:24,510 --> 00:29:29,960
Čo les robí, je to pekne drží to sú zoradené pre nás.

358
00:29:29,960 --> 00:29:37,910
A potom konečne, máme rmforest a, ako sa očakávalo, máme rmtree vzýval tam.

359
00:29:46,650 --> 00:29:55,440
>> Pri pohľade na distribučné kód tak ďaleko, huffile.c bol pravdepodobne zďaleka najťažší pochopiť,

360
00:29:55,440 --> 00:29:59,990
vzhľadom k tomu, ďalších súborov sami boli celkom jednoduché nasledovať.

361
00:29:59,990 --> 00:30:03,090
Pri našej znalosti ukazovateľov a vzájomne previazaných zoznamov a takých,

362
00:30:03,090 --> 00:30:04,860
sme boli schopní sledovať celkom dobre.

363
00:30:04,860 --> 00:30:10,500
Ale všetko, čo potrebujeme naozaj uistiť, že plne chápeme je. H súbory

364
00:30:10,500 --> 00:30:15,840
pretože je potrebné, aby sa volanie týchto funkcií, ktoré sa zaoberajú týmito návratovej hodnoty,

365
00:30:15,840 --> 00:30:20,590
takže sa uistite, že ste plne porozumeli, aká akcia sa bude vykonávať

366
00:30:20,590 --> 00:30:24,290
kedykoľvek volať jednu z týchto funkcií.

367
00:30:24,290 --> 00:30:33,020
Ale v skutočnosti porozumenie vnútri nej nie je úplne nutné, pretože máme tie. H súbory.

368
00:30:35,170 --> 00:30:39,490
Máme 2 ďalšie súbory, ktoré zostali v našej distribučnej kódu.

369
00:30:39,490 --> 00:30:41,640
>> Poďme sa pozrieť na skládke.

370
00:30:41,640 --> 00:30:47,230
Dump jeho komentármi tu trvá Huffman-komprimovaný súbor

371
00:30:47,230 --> 00:30:55,580
a potom prekladá a skládky všetci jej obsah von.

372
00:31:01,010 --> 00:31:04,260
Tu vidíme, že je to volanie hfopen.

373
00:31:04,260 --> 00:31:10,770
To je druh zrkadlenie súbor * vstup = fopen,

374
00:31:10,770 --> 00:31:13,500
a potom sa prejsť v informácii.

375
00:31:13,500 --> 00:31:18,240
Je to takmer identické, s výnimkou miesto súboru * ste prechádzajúcej v Huffile;

376
00:31:18,240 --> 00:31:22,030
miesto fopen ste mimochodom v hfopen.

377
00:31:22,030 --> 00:31:29,280
Tu čítame v hlavičke prvý, ktorý je tak trochu podobné tomu, ako čítame v záhlaví

378
00:31:29,280 --> 00:31:33,580
pre bitmapový súbor.

379
00:31:33,580 --> 00:31:38,000
Čo tu robíme je kontrola, či informácie v hlavičke

380
00:31:38,000 --> 00:31:44,330
obsahuje správne magické číslo, ktoré označuje, že je to skutočný Huff súbor,

381
00:31:44,330 --> 00:31:53,610
potom všetky tieto kontroly, aby sa uistil, že súbor, ktorý sme otvorený je skutočný nahneval súbor, alebo nie.

382
00:31:53,610 --> 00:32:05,330
Čo to však je, že výstupy frekvencia všetkých symbolov, ktoré môžeme vidieť

383
00:32:05,330 --> 00:32:09,790
v rámci terminálu do grafického tabuľky.

384
00:32:09,790 --> 00:32:15,240
Táto časť bude užitočná.

385
00:32:15,240 --> 00:32:24,680
Má trochu a číta kúsok po kúsku do premennej bit a potom vytlačí ju.

386
00:32:28,220 --> 00:32:35,430
Takže ak by som mal zavolať skládku na hth.bin, ktorý je výsledkom nahnevá súboru

387
00:32:35,430 --> 00:32:39,490
pomocou zamestnancov riešenie, by som si to.

388
00:32:39,490 --> 00:32:46,000
Je to výstup všetkých týchto znakov a potom uvedenie frekvenciu, pri ktorej sa objaví.

389
00:32:46,000 --> 00:32:51,180
Ak sa pozrieme, väčšina z nich sú 0s okrem toho: H, ktorý sa objaví dvakrát,

390
00:32:51,180 --> 00:32:54,820
a potom T, ktorá sa objaví raz.

391
00:32:54,820 --> 00:33:07,860
A potom tu máme skutočný správu 0s a 1s.

392
00:33:07,860 --> 00:33:15,450
Ak sa pozrieme na hth.txt, čo je pravdepodobne pôvodná správa, ktorá bola odfrkol,

393
00:33:15,450 --> 00:33:22,490
očakávame nejaké Hs a TS tam.

394
00:33:22,490 --> 00:33:28,720
Konkrétne, očakávame len 1 T a 2 HS.

395
00:33:32,510 --> 00:33:37,440
Tu sme v hth.txt. To má skutočne HTH.

396
00:33:37,440 --> 00:33:41,270
Zahrnuté tam, hoci my nemôžeme vidieť, je znak nového riadku.

397
00:33:41,270 --> 00:33:53,190
Súbor Huff hth.bin je tiež kódovanie znaku nového riadku rovnako.

398
00:33:55,680 --> 00:34:01,330
Tu pretože vieme, že poriadok je HTH a potom nový riadok,

399
00:34:01,330 --> 00:34:07,340
je vidieť, že asi H je reprezentovaná len jedným 1

400
00:34:07,340 --> 00:34:17,120
a potom T je pravdepodobne 01 a potom ďalšie H 1, rovnako

401
00:34:17,120 --> 00:34:21,139
a potom máme nový riadok označená dvomi 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> A potom konečne, pretože máme čo do činenia s viac. C a H súbory,

404
00:34:31,600 --> 00:34:36,350
budeme mať pekne zložitá argument kompilátor,

405
00:34:36,350 --> 00:34:40,460
a tak tu máme Makefile, ktoré umožňuje výpis pre vás.

406
00:34:40,460 --> 00:34:47,070
Ale v skutočnosti, budete musieť ísť o tom svoje vlastné puff.c súbor.

407
00:34:47,070 --> 00:34:54,330
Makefile vlastne nerieši robiť puff.c pre vás.

408
00:34:54,330 --> 00:34:59,310
Odchádzame, že na vás upraviť Makefile.

409
00:34:59,310 --> 00:35:05,930
Keď zadáte príkaz, ako je, aby všetkým, napríklad, bude to robiť všetky z nich pre vás.

410
00:35:05,930 --> 00:35:10,760
Neváhajte sa pozrieť na príklady Makefile z minulého PSet

411
00:35:10,760 --> 00:35:17,400
rovnako ako ísť preč z tohto vidieť, ako by ste mali byť schopní, aby sa váš Puff súbor

412
00:35:17,400 --> 00:35:20,260
úpravou tohto súboru Makefile.

413
00:35:20,260 --> 00:35:22,730
To je asi tak pre náš distribučný kódu.

414
00:35:22,730 --> 00:35:28,380
>> Akonáhle sme sa dostali cez to, že potom je tu len ďalší pripomienkou toho,

415
00:35:28,380 --> 00:35:30,980
o tom, ako budeme rokovať s uzlami Huffman.

416
00:35:30,980 --> 00:35:35,400
Nebudeme sa volať je uzliny už, budeme sa nazývať stromy

417
00:35:35,400 --> 00:35:39,260
kde budeme zastupovať ich symbol, char,

418
00:35:39,260 --> 00:35:43,340
ich frekvencia, počet výskytov, s celé číslo.

419
00:35:43,340 --> 00:35:47,370
Používame to, pretože to je to presnejšie než plaváku.

420
00:35:47,370 --> 00:35:52,980
A potom máme ďalší ukazovateľ na ľavej dieťaťa rovnako ako pravé dieťa.

421
00:35:52,980 --> 00:35:59,630
Les, ako sme videli, je len previazaný zoznam stromov.

422
00:35:59,630 --> 00:36:04,670
Nakoniec, keď sme budovanie našej Huff súbor,

423
00:36:04,670 --> 00:36:07,580
chceme, aby naše lesy obsahovať len 1 strom -

424
00:36:07,580 --> 00:36:12,420
1 strom, 1 root s viacerými deťmi.

425
00:36:12,420 --> 00:36:20,840
Predtým, keď sme boli len, že naše Huffman stromy,

426
00:36:20,840 --> 00:36:25,360
sme začali tým všetky uzly na našej obrazovke

427
00:36:25,360 --> 00:36:27,790
a hovoriť budeme mať tieto uzly,

428
00:36:27,790 --> 00:36:32,920
nakoniec sa budeš listy, a to je ich symbol, to je ich frekvencia.

429
00:36:32,920 --> 00:36:42,070
V našom lese, keby sme sa 3 písmená, to je les 3 stromov.

430
00:36:42,070 --> 00:36:45,150
A potom, ako budeme pokračovať, keď sme pridali prvý rodičia,

431
00:36:45,150 --> 00:36:48,080
sme sa les 2 stromov.

432
00:36:48,080 --> 00:36:54,930
Odstránili sme 2 z týchto detí z nášho lesa a potom nahradil ju nadradeného uzla

433
00:36:54,930 --> 00:36:58,820
že mal tie 2 uzly ako deti.

434
00:36:58,820 --> 00:37:05,600
A potom konečne, naše posledný krok s výrobou náš príklad s As, Bs, a Cs

435
00:37:05,600 --> 00:37:08,030
by ku konečnému rodičia,

436
00:37:08,030 --> 00:37:13,190
a tak, potom by to priniesť naše celkové počtu stromov v lese na 1.

437
00:37:13,190 --> 00:37:18,140
Má každý vidieť, ako sa začať s niekoľkými stromami v lese

438
00:37:18,140 --> 00:37:22,520
a skončiť s 1? Dobre. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Čo musíme urobiť pre Puff?

440
00:37:28,110 --> 00:37:37,110
Čo musíme urobiť, je zabezpečiť, že ako vždy, nám dávajú ten správny typ vstupu

441
00:37:37,110 --> 00:37:39,090
tak, že sa môže v skutočnosti spustiť program.

442
00:37:39,090 --> 00:37:43,130
V tomto prípade sú to bude, že nám po ich prvom argument príkazového riadku

443
00:37:43,130 --> 00:37:53,440
2 viac: súbor, ktorý chceme dekomprimovať a výstup dekomprimovaného súboru.

444
00:37:53,440 --> 00:38:00,410
Ale akonáhle sme sa uistili, že okolo nás v správnom množstve hodnôt,

445
00:38:00,410 --> 00:38:05,820
Chceme zabezpečiť, aby vstup je súbor Huff, alebo nie.

446
00:38:05,820 --> 00:38:10,420
A potom ešte raz vám zaručiť, že je to súbor Huff, potom chceme budovať náš strom,

447
00:38:10,420 --> 00:38:20,940
vybudovať strom tak, že zodpovedá strom, ktorý človek, ktorý poslal správu postavený.

448
00:38:20,940 --> 00:38:25,840
Potom po staviame strom, potom sa môžeme zaoberať 0s a 1s, že prešiel v roku,

449
00:38:25,840 --> 00:38:29,590
tým, ktoré spolu náš strom, pretože je to rovnaké,

450
00:38:29,590 --> 00:38:33,510
a potom napísať, že posolstvo, interpretovať bity späť do znakov.

451
00:38:33,510 --> 00:38:35,880
A potom na konci, pretože máme čo do činenia s ukazovateľmi tu,

452
00:38:35,880 --> 00:38:38,110
Chceme sa uistiť, že nemáme žiadne úniky pamäte

453
00:38:38,110 --> 00:38:41,330
a že sme voľní všetko.

454
00:38:42,820 --> 00:38:46,430
>> Zabezpečenie riadneho využitia je starý klobúk pre nás teraz.

455
00:38:46,430 --> 00:38:51,980
Berieme v vstup, ktorý bude názov súboru, ktorý chcete nafúknuť,

456
00:38:51,980 --> 00:38:56,010
a potom sme sa špecifikovať výstup,

457
00:38:56,010 --> 00:39:01,580
takže názov súboru pre predvareného výstup, ktorý bude textový súbor.

458
00:39:03,680 --> 00:39:08,820
To je s nimi nakladané. A teraz chceme zabezpečiť, aby vstup fučal, alebo nie.

459
00:39:08,820 --> 00:39:16,420
Keď spomínam, bolo niečo, čo v distribučnej kódu, ktorý nám môže pomôcť

460
00:39:16,420 --> 00:39:21,570
s pochopením, či je súbor nahneval, alebo nie?

461
00:39:21,570 --> 00:39:26,910
Tam boli informácie v huffile.c o Huffeader.

462
00:39:26,910 --> 00:39:33,430
Vieme, že každý súbor Huff má Huffeader s ním spojené s čarovným číslom

463
00:39:33,430 --> 00:39:37,240
, Ako aj rad frekvencií pre každý symbol

464
00:39:37,240 --> 00:39:39,570
rovnako ako kontrolný súčet.

465
00:39:39,570 --> 00:39:43,180
Vieme, že, ale tiež sa nahliadnuť na dump.c,

466
00:39:43,180 --> 00:39:49,120
, V ktorom bolo čítanie do súboru Huff.

467
00:39:49,120 --> 00:39:53,990
A tak k tomu, že to malo overiť, či skutočne bol nahneval, alebo nie.

468
00:39:53,990 --> 00:40:03,380
Takže možno by sme mohli použiť dump.c ako štruktúry pre naše puff.c.

469
00:40:03,380 --> 00:40:12,680
Späť na PSet 4, keď sme mali súbor copy.c, že ​​skopírovali v trojiciach RGB

470
00:40:12,680 --> 00:40:14,860
a my vykladať, že pre detektívka a zmeny veľkosti,

471
00:40:14,860 --> 00:40:20,390
podobne, čo by ste mohli urobiť, je stačí spustiť príkaz ako cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
a použiť niektoré z kódu tam.

473
00:40:23,600 --> 00:40:28,210
Avšak, to nebude tak jednoduché procesu

474
00:40:28,210 --> 00:40:33,010
pre prekladanie si dump.c do puff.c,

475
00:40:33,010 --> 00:40:36,160
ale aspoň to vám dáva niekde začať

476
00:40:36,160 --> 00:40:40,540
o tom, ako zabezpečiť, aby vstup je skutočne odfrkol, alebo nie

477
00:40:40,540 --> 00:40:43,240
rovnako ako pár ďalších vecí.

478
00:40:45,930 --> 00:40:50,250
Sme zaistili správne používanie a zabezpečiť, aby vstup nahneval.

479
00:40:50,250 --> 00:40:53,570
Zakaždým, keď sme urobili, že sme urobili našu správnu kontrolu chýb,

480
00:40:53,570 --> 00:41:01,520
tak vracia a ukončenie funkcie, ak niektoré dôjde k zlyhaniu, v prípade, že je problém.

481
00:41:01,520 --> 00:41:07,170
>> Teraz, čo chceme urobiť, je vytvoriť skutočný strom.

482
00:41:08,840 --> 00:41:12,640
Ak sa pozrieme v lese, tam sú 2 hlavné funkcie

483
00:41:12,640 --> 00:41:15,800
že budeme chcieť, aby sa veľmi dobre.

484
00:41:15,800 --> 00:41:23,870
Tam je Logické funkcie rastlina, ktorá rastliny non-0 Frekvencia strom v našom lese.

485
00:41:23,870 --> 00:41:29,250
A tak tam odovzdáte ukazovateľ na les a ukazovateľ na strom.

486
00:41:32,530 --> 00:41:40,340
Rýchly dotaz: Koľko lesy budete mať, keď staviate Huffman strom?

487
00:41:44,210 --> 00:41:46,650
Naša les je ako náš plátno, nie?

488
00:41:46,650 --> 00:41:50,800
Takže sme len bude mať 1 les, ale budeme mať viac stromov.

489
00:41:50,800 --> 00:41:57,590
Takže predtým, než zavoláte zariadenie, budete pravdepodobne chcieť, aby váš les.

490
00:41:57,590 --> 00:42:04,430
K dispozícii je príkaz pre ktoré, keď sa pozriete do forest.h o tom, ako môžete urobiť les.

491
00:42:04,430 --> 00:42:09,270
Môžete zasadiť strom. Vieme, ako na to.

492
00:42:09,270 --> 00:42:11,590
A potom si môžete vybrať aj strom z lesa,

493
00:42:11,590 --> 00:42:17,540
odstránenie stromu s najnižšou váhou a dáva vám ukazovateľ na to.

494
00:42:17,540 --> 00:42:23,090
Spomínal, keď sme robili v príkladoch sami,

495
00:42:23,090 --> 00:42:27,980
keď sme boli kreslenie to, sme proste len pridali odkazy.

496
00:42:27,980 --> 00:42:31,680
Ale tu nie len pridávanie odkazov,

497
00:42:31,680 --> 00:42:40,630
myslieť na to skôr ako ste odstránenie 2 týchto uzlov a potom nahrádzať ju inou.

498
00:42:40,630 --> 00:42:44,200
Ak chcete vyjadriť, že pokiaľ ide o zber a pestovanie,

499
00:42:44,200 --> 00:42:48,840
ste vychystávanie 2 stromy a potom výsadba ďalšie strom

500
00:42:48,840 --> 00:42:54,060
že má tie 2 stromy, ktoré ste si vybrali ako deti.

501
00:42:57,950 --> 00:43:05,280
Ak chcete vytvoriť Huffman je strom, si môžete prečítať v symboly a frekvencie v poradí

502
00:43:05,280 --> 00:43:10,790
pretože Huffeader dáva, že na vás,

503
00:43:10,790 --> 00:43:14,250
vám dáva rad frekvencií.

504
00:43:14,250 --> 00:43:19,660
Takže môžete ísť dopredu a len tak ignorovať čokoľvek s 0 v ňom

505
00:43:19,660 --> 00:43:23,760
pretože nechceme 256 listy na konci toho.

506
00:43:23,760 --> 00:43:27,960
Chceme len počet listov, ktoré sú znaky

507
00:43:27,960 --> 00:43:31,600
, Ktoré sú v skutočnosti používa v súbore.

508
00:43:31,600 --> 00:43:37,590
Si môžete prečítať v týchto symbolov, a každý z týchto symbolov, ktoré majú non-0 frekvencií,

509
00:43:37,590 --> 00:43:40,440
ty sa bude stromy.

510
00:43:40,440 --> 00:43:45,990
Čo môžete urobiť, je zakaždým, keď si prečítal v non-0 frekvencie symbol,

511
00:43:45,990 --> 00:43:50,660
môžete zasadiť ten strom v lese.

512
00:43:50,660 --> 00:43:56,620
Akonáhle zasadiť stromy v lese, môžete sa pripojiť tie stromy ako súrodenci,

513
00:43:56,620 --> 00:44:01,130
tak vracia na pestovanie a vyberanie, kde si vyberiete 2 a potom závod 1,

514
00:44:01,130 --> 00:44:05,820
kde to 1, ktorá vás rastlín je rodič zo 2 detí, ktoré si vybral.

515
00:44:05,820 --> 00:44:11,160
Takže potom sa vaše konečný výsledok bude jediný strom v lese.

516
00:44:16,180 --> 00:44:18,170
To je, ako si postaviť svoj strom.

517
00:44:18,170 --> 00:44:21,850
>> Existuje niekoľko vecí, ktoré by mohli pokaziť tu

518
00:44:21,850 --> 00:44:26,580
pretože máme čo do činenia s výrobou nových stromov a nakladanie s ukazovateľmi a podobné veci.

519
00:44:26,580 --> 00:44:30,450
Ako keď sme sa zaoberali ukazovateľmi,

520
00:44:30,450 --> 00:44:36,580
keď sme malloc'd sme chceli, aby sa ubezpečil, že sa nevrátil nám NULL ukazovateľ hodnotu.

521
00:44:36,580 --> 00:44:42,770
Takže na niekoľkých krokoch v rámci tohto procesu sú bude niekoľko prípadov

522
00:44:42,770 --> 00:44:45,920
kde váš program by mohol zlyhať.

523
00:44:45,920 --> 00:44:51,310
Čo chcete urobiť, je sa chcete uistiť, že riešite tieto chyby,

524
00:44:51,310 --> 00:44:54,580
a vo spec hovorí s nimi elegantne,

525
00:44:54,580 --> 00:45:00,280
tak ako vytlačiť správu užívateľovi im povie, prečo má program ukončiť

526
00:45:00,280 --> 00:45:03,050
a potom rýchlo ukončite ju.

527
00:45:03,050 --> 00:45:09,490
Ak chcete túto chýb, pamätajte, že chcete skontrolovať

528
00:45:09,490 --> 00:45:12,160
zakaždým, že by mohlo byť zlyhanie.

529
00:45:12,160 --> 00:45:14,660
Zakaždým, že robíš nový ukazovateľ

530
00:45:14,660 --> 00:45:17,040
Chcete, aby sa ubezpečil, že je úspešný.

531
00:45:17,040 --> 00:45:20,320
Ako to, čo sme urobiť, je vytvoriť nový ukazovateľ a malloc ju,

532
00:45:20,320 --> 00:45:22,380
a potom by sme skontrolovať, či je ukazovateľ NULL.

533
00:45:22,380 --> 00:45:25,670
Takže tam sa bude niektoré príklady, kde môžete len urobiť to,

534
00:45:25,670 --> 00:45:28,610
ale niekedy ste vlastne volanie funkcie

535
00:45:28,610 --> 00:45:33,100
av rámci tejto funkcie, to je ten, ktorý je robí mallocing.

536
00:45:33,100 --> 00:45:39,110
V tomto prípade, ak sa pozrieme späť do niektorej z funkcií v kóde,

537
00:45:39,110 --> 00:45:42,260
Niektoré z nich sú logické funkcie.

538
00:45:42,260 --> 00:45:48,480
V abstraktné prípade, ak máme logický funkcia s názvom foo,

539
00:45:48,480 --> 00:45:54,580
v podstate, dá sa predpokladať, že okrem toho, čo foo robí,

540
00:45:54,580 --> 00:45:57,210
pretože je to Logické funkcie, vracia true alebo false -

541
00:45:57,210 --> 00:46:01,300
true, ak úspešný, false v opačnom prípade.

542
00:46:01,300 --> 00:46:06,270
Takže chceme overiť, či je vrátená hodnota foo je true alebo false.

543
00:46:06,270 --> 00:46:10,400
Ak je to false, čo znamená, že budeme chcieť vytlačiť nejakú správu

544
00:46:10,400 --> 00:46:14,390
a potom ukončite program.

545
00:46:14,390 --> 00:46:18,530
Čo chceme urobiť, je skontrolovať vrátenú hodnotu foo.

546
00:46:18,530 --> 00:46:23,310
Ak foo vráti false, potom vieme, že sme sa stretli s nejakou chybou

547
00:46:23,310 --> 00:46:25,110
a musíme prestať náš program.

548
00:46:25,110 --> 00:46:35,600
Spôsob, ako to urobiť, je mať stav, keď skutočná funkcia sama o sebe je Váš zdravotný stav.

549
00:46:35,600 --> 00:46:39,320
Povedzme, že foo berie v x.

550
00:46:39,320 --> 00:46:43,390
Môžeme mať ako podmienku if (foo (x)).

551
00:46:43,390 --> 00:46:50,900
V podstate to znamená, že ak na konci realizácie foo vracia pravda,

552
00:46:50,900 --> 00:46:57,390
potom môžeme urobiť, pretože funkcia musí zhodnotiť foo

553
00:46:57,390 --> 00:47:00,500
aby bolo možné vyhodnotiť celý stav.

554
00:47:00,500 --> 00:47:06,500
Takže je to, ako môžete niečo urobiť, ak funkcia vracia hodnotu true a je úspešný.

555
00:47:06,500 --> 00:47:11,800
Ale keď ste kontrolu chýb, si len chcete ukončiť, ak je vaša funkcia vráti false.

556
00:47:11,800 --> 00:47:16,090
Čo môžete urobiť, je len pridať == false, alebo len pridať tresku pred ním

557
00:47:16,090 --> 00:47:21,010
a potom máte if (! foo).

558
00:47:21,010 --> 00:47:29,540
V rámci tohto orgánu tohto stavu by ste mať všetky chýb,

559
00:47:29,540 --> 00:47:36,940
tak ako, "Nepodarilo sa vytvoriť tento strom" a potom sa vrátiť 1, alebo niečo také.

560
00:47:36,940 --> 00:47:43,340
Čo to robí, keď je to, že aj keď foo vrátil false -

561
00:47:43,340 --> 00:47:46,980
Povedzme, že foo vracia hodnotu true.

562
00:47:46,980 --> 00:47:51,060
Potom nemusíte volať foo znova. To je mylná predstava,.

563
00:47:51,060 --> 00:47:54,730
Vzhľadom k tomu, že bol vo svojom stave, je to už vyhodnotený,

564
00:47:54,730 --> 00:47:59,430
takže už máte výsledok, ak používate, aby strom alebo niečo také

565
00:47:59,430 --> 00:48:01,840
alebo zariadenia alebo pick, alebo tak niečo.

566
00:48:01,840 --> 00:48:07,460
To už má túto hodnotu. Je to už vykonaný.

567
00:48:07,460 --> 00:48:10,730
Takže je to vhodné použiť booleovské funkcie ako podmienku

568
00:48:10,730 --> 00:48:13,890
pretože či už ste alebo nie ste skutočne spustiť telo slučky,

569
00:48:13,890 --> 00:48:18,030
spustí funkciu rovnako.

570
00:48:22,070 --> 00:48:27,330
>> Náš druhý na posledný krok je písanie správy do súboru.

571
00:48:27,330 --> 00:48:33,070
Akonáhle budeme budovať Huffman strom, potom písanie správy do súboru je veľmi jednoduché.

572
00:48:33,070 --> 00:48:39,260
Je to celkom jednoduché teraz stačí nasledovať 0s a 1s.

573
00:48:39,260 --> 00:48:45,480
A tak podľa konvencie vieme, že na strome Huffman uveďte opustil 0s

574
00:48:45,480 --> 00:48:48,360
a 1s uviesť pravdu.

575
00:48:48,360 --> 00:48:53,540
Takže ak budete čítať v kúsok po kúsku, zakaždým, keď dostanete 0

576
00:48:53,540 --> 00:48:59,100
budete sledovať ľavá vetva, a potom zakaždým, keď si prečítal v 1

577
00:48:59,100 --> 00:49:02,100
budete nasledovať správnu vetvu.

578
00:49:02,100 --> 00:49:07,570
A potom budete pokračovať, kým nenarazíte na list

579
00:49:07,570 --> 00:49:11,550
pretože listy sa bude na konci konárov.

580
00:49:11,550 --> 00:49:16,870
Ako môžeme zistiť, či sme hit list alebo nie?

581
00:49:19,800 --> 00:49:21,690
Povedali sme, že to predtým.

582
00:49:21,690 --> 00:49:24,040
[Študent] Ak ukazovatele sú NULL. Jo >>.

583
00:49:24,040 --> 00:49:32,220
Môžeme povedať, či sme hit list v prípade, že ukazovatele na oboch ľavý a pravý stromy sú NULL.

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

585
00:49:34,110 --> 00:49:40,320
Vieme, že chceme čítať v kúsok po kúsku do nášho súboru Huff.

586
00:49:43,870 --> 00:49:51,220
Ako sme videli skôr v dump.c, čo urobili, je, že si v kúsok po kúsku do súboru Huff

587
00:49:51,220 --> 00:49:54,560
a len vytlačiť to, čo tie kúsky boli.

588
00:49:54,560 --> 00:49:58,430
Nebudeme sa s tým. Budeme robiť niečo, čo je trochu zložitejšie.

589
00:49:58,430 --> 00:50:03,620
Ale čo môžeme urobiť, je, že sme si vziať ten kúsok kódu, ktorý číta do bitu.

590
00:50:03,620 --> 00:50:10,250
Tu máme integer bit predstavujúce aktuálne bit, ktorý sme na.

591
00:50:10,250 --> 00:50:15,520
To sa stará o iterácií všetky bity v súbore, kým nenarazíte na koniec súboru.

592
00:50:15,520 --> 00:50:21,270
Na základe toho, potom budete chcieť mať nejaký Iterator

593
00:50:21,270 --> 00:50:26,760
prejsť na strom.

594
00:50:26,760 --> 00:50:31,460
A potom na základe toho, či je bit 0 alebo 1,

595
00:50:31,460 --> 00:50:36,920
budete chcieť, aby buď presunúť tento Iterator vľavo alebo ju presunúť doprava

596
00:50:36,920 --> 00:50:44,080
celú cestu, kým nenarazíte na list, takže celá cesta až do tohto uzla, ktorý ste na

597
00:50:44,080 --> 00:50:48,260
neukazuje na nič viac uzlov.

598
00:50:48,260 --> 00:50:54,300
Prečo môžeme urobiť so súborom Huffman, ale nie Morse kódu?

599
00:50:54,300 --> 00:50:56,610
Vzhľadom k tomu, v Morseova abeceda je tu trochu nejednoznačnosť.

600
00:50:56,610 --> 00:51:04,440
Mohli by sme byť ako, oh čakať, sme hit list na ceste, takže možno to je naša list,

601
00:51:04,440 --> 00:51:08,150
vzhľadom k tomu, či sme pokračovali len trochu dlhšie, potom by sme zasiahli ďalší list.

602
00:51:08,150 --> 00:51:13,110
Ale to sa nestane v kódovaní Huffman,

603
00:51:13,110 --> 00:51:17,540
takže môžeme byť istí, že jediný spôsob, ako budeme hit charakter

604
00:51:17,540 --> 00:51:23,480
Ak je tento uzol je ľavá a pravá deti sú NULL.

605
00:51:28,280 --> 00:51:32,350
>> Napokon, chceme oslobodiť všetky naše pamäť.

606
00:51:32,350 --> 00:51:37,420
Chceme, aby aj konci súboru Huff, že sme sa zaoberáme

607
00:51:37,420 --> 00:51:41,940
rovnako ako odstránenie všetkých stromov v našom lese.

608
00:51:41,940 --> 00:51:46,470
Na základe vašej implementáciu, budete pravdepodobne chcieť volať odstrániť les

609
00:51:46,470 --> 00:51:49,780
miesto skutočne prechádza všetky stromy sami.

610
00:51:49,780 --> 00:51:53,430
Ale ak ste vykonali nejaké dočasné stromy, budete chcieť oslobodiť, že.

611
00:51:53,430 --> 00:51:59,060
Vieš svoj kód najlepšie, takže viete, kde ste prideľovanie pamäte.

612
00:51:59,060 --> 00:52:04,330
A tak ak idete do, začnite tým, dokonca kontrolu F'ing pre malloc,

613
00:52:04,330 --> 00:52:08,330
vidieť kedykoľvek malloc a uistite sa, že ste uvoľniť všetko

614
00:52:08,330 --> 00:52:10,190
ale potom práve prechádza kódu,

615
00:52:10,190 --> 00:52:14,260
porozumenie, kde ste mohli pridelená pamäť.

616
00:52:14,260 --> 00:52:21,340
Zvyčajne môžete len povedať, "Na konci súboru Ja som jednoducho ísť na odstránenie les na mojom lese,"

617
00:52:21,340 --> 00:52:23,850
takže v podstate jasné, že pamäť, zadarmo, ktoré,

618
00:52:23,850 --> 00:52:28,310
"A potom som tiež chystá zatvorte súbor a potom môj program bude prestať."

619
00:52:28,310 --> 00:52:33,810
Ale je to jediný čas, ktorý váš program ukončí?

620
00:52:33,810 --> 00:52:37,880
Nie, pretože niekedy tam mohlo byť chyba, čo sa stalo.

621
00:52:37,880 --> 00:52:42,080
Možno sme nemohli otvoriť súbor alebo my sme nemohli vykonať ďalšie strom

622
00:52:42,080 --> 00:52:49,340
alebo nejaký druh chyby sa stalo v procese prideľovania pamäti, a tak sa vrátil NULL.

623
00:52:49,340 --> 00:52:56,710
Došlo k chybe, a potom sme sa vrátili a ukončite.

624
00:52:56,710 --> 00:53:02,040
Takže chcete, aby sa ubezpečil, že prípadná čas, že váš program môže prestať fajčiť,

625
00:53:02,040 --> 00:53:06,980
Ak chcete uvoľniť všetky svoje pamäti tam.

626
00:53:06,980 --> 00:53:13,370
Nie je to len tak na samom konci hlavnej funkcie, ktoré ukončite kód.

627
00:53:13,370 --> 00:53:20,780
Chceš sa pozrieť späť na každom stupni, že váš kód potenciálne mohol vrátiť predčasne

628
00:53:20,780 --> 00:53:25,070
a potom zadarmo bez ohľadu na pamäti zmysel.

629
00:53:25,070 --> 00:53:30,830
Povedzte, že ste zavolal, aby les a že sa vrátil false.

630
00:53:30,830 --> 00:53:34,230
Potom ste pravdepodobne nebudete potrebovať odstrániť svoj les

631
00:53:34,230 --> 00:53:37,080
pretože nemáte lesa doteraz.

632
00:53:37,080 --> 00:53:42,130
Ale v každom bode v kóde, kde by ste mohli vrátiť predčasne

633
00:53:42,130 --> 00:53:46,160
chcete, aby sa ubezpečil, že ste uvoľniť prípadné pamäť.

634
00:53:46,160 --> 00:53:50,020
>> Takže keď máme čo do činenia s uvoľnením pamäte a majú potenciálne úniky,

635
00:53:50,020 --> 00:53:55,440
chceme využívať nielen náš úsudok a naše logika

636
00:53:55,440 --> 00:54:01,850
ale tiež použiť Valgrind na určenie, či máme uvoľnená všetka našej pamäti správne, alebo nie.

637
00:54:01,850 --> 00:54:09,460
Môžete buď spustiť Valgrind na Puff a potom sa budete musieť tiež odovzdať ho

638
00:54:09,460 --> 00:54:14,020
správny počet argumentov príkazového riadku pre Valgrind.

639
00:54:14,020 --> 00:54:18,100
Môžete spustiť, ale výstup je trochu mystický.

640
00:54:18,100 --> 00:54:21,630
Dostali sme sa trochu na to zvyknutí u Speller, ale stále potrebujeme trochu viac pomoci,

641
00:54:21,630 --> 00:54:26,450
takže potom beží to s niekoľkými ďalšími príznakmi, ako je únik-check = full,

642
00:54:26,450 --> 00:54:32,040
ktoré budú pravdepodobne nám nejaké ďalšie užitočné výstup na Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Potom ďalšie užitočné tip, keď ste ladenie je príkaz diff.

644
00:54:39,040 --> 00:54:48,520
Môžete pristupovať k pracovníkom za vykonávanie Huff, spustite, že na textový súbor,

645
00:54:48,520 --> 00:54:55,400
a potom výstup do binárneho súboru, binárny súbor Huff, byť konkrétny.

646
00:54:55,400 --> 00:54:59,440
Potom, ak sa dostanete svoj vlastný obláčik na tomto binárny súbor,

647
00:54:59,440 --> 00:55:03,950
potom v ideálnom prípade, vaše výstup textový súbor bude totožný

648
00:55:03,950 --> 00:55:08,200
k pôvodnej, ktorý prešiel dovnútra

649
00:55:08,200 --> 00:55:15,150
Tu som pomocou hth.txt ako príklad, a to je ten hovoril o vo vašom špec.

650
00:55:15,150 --> 00:55:21,040
To je doslova HTH a potom nový riadok.

651
00:55:21,040 --> 00:55:30,970
Ale rozhodne neváhajte a ste určite odporúčame používať dlhší príklady

652
00:55:30,970 --> 00:55:32,620
pre textovom súbore.

653
00:55:32,620 --> 00:55:38,110
>> Môžete si dokonca vziať si na mušku možno kompresiu a dekompresiu potom

654
00:55:38,110 --> 00:55:41,600
niektoré zo súborov, ktoré ste použili v Speller ako Vojna a mier

655
00:55:41,600 --> 00:55:46,710
alebo Jane Austen, alebo niečo takého - to by bolo celkom fajn - alebo Austin Powers,

656
00:55:46,710 --> 00:55:51,880
druh rokovaní s väčšími súbormi, pretože by sme prišli na vec

657
00:55:51,880 --> 00:55:55,590
ak sme použili na ďalší nástroj tu, ls-l.

658
00:55:55,590 --> 00:56:01,150
Sme zvyknutí na ls, ktorá v podstate uvádza všetky obsah v našom aktuálnom adresári.

659
00:56:01,150 --> 00:56:07,860
Odovzdávanie v vlajky-l skutočne zobrazuje veľkosť týchto súborov.

660
00:56:07,860 --> 00:56:12,690
Ak prejdete spec PSet, to vlastne vás prevedie vytvorením binárny súbor,

661
00:56:12,690 --> 00:56:16,590
zo dňa nahnevá ho, a uvidíte, že pre veľmi malé súbory

662
00:56:16,590 --> 00:56:23,910
priestor náklady na kompresiu, a prekladať všetky tieto informácie

663
00:56:23,910 --> 00:56:26,980
všetkých frekvencií a podobné veci, ktoré preváži skutočné výhody

664
00:56:26,980 --> 00:56:30,000
kompresiu súboru na prvom mieste.

665
00:56:30,000 --> 00:56:37,450
Ale ak sa dostanete na niektorých dlhších textových súborov, potom by ste mali vidieť, že začnete sa dostať nejaký prospech

666
00:56:37,450 --> 00:56:40,930
v kompresii týchto súborov.

667
00:56:40,930 --> 00:56:46,210
>> A potom konečne, máme starý kamarát GDB, ktorý je určite príde vhod tiež.

668
00:56:48,360 --> 00:56:55,320
>> Ešte budeme mať nejaké otázky, na stromoch Huff alebo procesu snáď robiť stromy

669
00:56:55,320 --> 00:56:58,590
alebo akékoľvek iné otázky týkajúce sa Puff Huff'n?

670
00:57:00,680 --> 00:57:02,570
Dobre. Zostanem asi na chvíľu.

671
00:57:02,570 --> 00:57:06,570
>> Vďaka, všetci. To bolo Návod 6. A veľa šťastia.

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