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

2
00:00:02,210 --> 00:00:04,810
[Zamyla Chan - Sveučilište Harvard]

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

4
00:00:07,240 --> 00:00:12,180
>> Pozdrav, svima, i dobrodošli na Walkthrough 6: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
U Huff'n lisnato ono što mi radimo će se baviti datoteku Huffman komprimiranog

6
00:00:17,440 --> 00:00:20,740
i onda ga puffing natrag gore, pa ga dekompresije,

7
00:00:20,740 --> 00:00:25,810
tako da možemo prevesti iz 0s i 1s da korisnik nam šalje

8
00:00:25,810 --> 00:00:30,660
i pretvoriti ga natrag u izvornom tekstu.

9
00:00:30,660 --> 00:00:34,360
Pset 6 će biti prilično cool jer si idući u vidjeti neke od alata

10
00:00:34,360 --> 00:00:41,730
koje ste koristili u pset 4 i 5 pset i vrsta kombinirajući ih u jednom prilično uredan koncept

11
00:00:41,730 --> 00:00:43,830
kada dođete do razmišljati o tome.

12
00:00:43,830 --> 00:00:50,110
>> Također, nedvojbeno, pset 4 i 5 su najproblematičniji psets da smo imali za ponuditi.

13
00:00:50,110 --> 00:00:53,950
Dakle, od sada, imamo ovaj jedan više pset u C,

14
00:00:53,950 --> 00:00:56,480
i onda nakon toga smo na web programiranje.

15
00:00:56,480 --> 00:01:02,310
Tako sami čestitati za dobivanje preko najtežih grba u CS50.

16
00:01:03,630 --> 00:01:09,760
>> Premještanje na za Huff'n lisnato, naša kutija za ovaj pset će biti Huffman stabala,

17
00:01:09,760 --> 00:01:14,700
tako da razumijevanje ne samo kako binarnog stabla rad, ali i konkretno Huffman stabla,

18
00:01:14,700 --> 00:01:16,240
kako oni izgrađeni.

19
00:01:16,240 --> 00:01:20,210
A onda ćemo imati puno distribucije koda u ovom pset,

20
00:01:20,210 --> 00:01:22,480
a mi ćemo doći vidjeti kako zapravo neke od koda

21
00:01:22,480 --> 00:01:24,670
mi možda neće biti u mogućnosti u potpunosti razumjeti, ali,

22
00:01:24,670 --> 00:01:30,080
pa oni će biti. c slika, ali onda su njihovi popratni. h slika

23
00:01:30,080 --> 00:01:34,300
će nam dati dovoljno razumijevanja da trebamo da znamo kako te funkcije rade

24
00:01:34,300 --> 00:01:38,100
ili barem ono što su trebali učiniti - njihovi ulazi i izlazi -

25
00:01:38,100 --> 00:01:40,760
čak i ako ne znamo što se događa u crnoj kutiji

26
00:01:40,760 --> 00:01:44,090
ili ne razumiju što se događa u crnoj kutiji roku.

27
00:01:44,090 --> 00:01:49,400
I onda na kraju, kao i obično, mi smo se bave novim strukturama podataka,

28
00:01:49,400 --> 00:01:51,840
određene vrste čvorova koji upućuju na određene stvari,

29
00:01:51,840 --> 00:01:56,080
pa ovdje ima olovku i papir, ne samo za proces projektiranja

30
00:01:56,080 --> 00:01:58,470
i kada pokušavate shvatiti kako vaš pset treba raditi

31
00:01:58,470 --> 00:02:00,520
, ali i tijekom ispravljanje pogrešaka.

32
00:02:00,520 --> 00:02:06,140
Možete imati GDB uz svoje olovke i papira dok vas odvesti dolje što su vrijednosti,

33
00:02:06,140 --> 00:02:09,320
gdje strelice ukazuju, i slične stvari.

34
00:02:09,320 --> 00:02:13,720
>> Prvo pogledajmo Huffman stabala.

35
00:02:13,720 --> 00:02:19,600
Huffman stabla su binarni drveće, što znači da je svaki čvor ima samo 2 djece.

36
00:02:19,600 --> 00:02:24,870
U Huffman stabala karakteristika je da su najčešći vrijednosti

37
00:02:24,870 --> 00:02:27,140
predstavljeni su i najmanje komadiće.

38
00:02:27,140 --> 00:02:32,690
Vidjeli smo u predavaonicama primjera Morse koda, koja vrsta konsolidirane neki slova.

39
00:02:32,690 --> 00:02:38,030
Ako pokušavate prevesti A ili E, na primjer,

40
00:02:38,030 --> 00:02:43,940
ti si prevodio da često, pa umjesto da koriste cijeli set bitova

41
00:02:43,940 --> 00:02:48,640
sredstva za tu uobičajenu vrstu podataka, možete ga stisnuti prema dolje na manje,

42
00:02:48,640 --> 00:02:53,730
i onda ta slova koji su zastupljeni rjeđe zastupljene su s više bitova

43
00:02:53,730 --> 00:02:59,840
jer si možete priuštiti da kada odmjeriti frekvencije koje ta slova pojavljuju.

44
00:02:59,840 --> 00:03:03,020
Imamo istu ideju ovdje u Huffman stabala

45
00:03:03,020 --> 00:03:12,360
gdje smo izradu lanac, svojevrsni put doći do određenih likova.

46
00:03:12,360 --> 00:03:14,470
A onda su likovi koji imaju najviše frekvencije

47
00:03:14,470 --> 00:03:17,940
će biti zastupljena s najmanje bita.

48
00:03:17,940 --> 00:03:22,020
>> Način na koji ćete izgraditi Huffman stablo

49
00:03:22,020 --> 00:03:27,430
je stavljanjem svi likovi koji se pojavljuju u tekstu

50
00:03:27,430 --> 00:03:30,630
i izračuna njihovu učestalost, koliko često se pojavljuju.

51
00:03:30,630 --> 00:03:33,880
To je mogao biti računati koliko puta ta slova pojavljuju

52
00:03:33,880 --> 00:03:40,270
ili možda postotak od svih likova koliko svatko se pojavljuje.

53
00:03:40,270 --> 00:03:44,270
I tako ono što trebate učiniti je kada imate sve te zacrtao,

54
00:03:44,270 --> 00:03:49,060
onda ste u potrazi za dvije najnižih frekvencija, a zatim im se pridruže kao braće i sestara

55
00:03:49,060 --> 00:03:55,660
gdje onda roditelj čvor ima frekvenciju koja je zbroj njegovih 2 djece.

56
00:03:55,660 --> 00:04:00,870
I onda po konvenciji reći da je lijeva čvor,

57
00:04:00,870 --> 00:04:03,770
slijedite da slijedeći 0 granu,

58
00:04:03,770 --> 00:04:08,140
a zatim desni čvor je 1 granu.

59
00:04:08,140 --> 00:04:16,040
Kao što smo vidjeli u Morse kodu, onaj Gotcha je da ako ste imali samo zvučni signal i zvučni signal

60
00:04:16,040 --> 00:04:18,120
to je bio neodređen.

61
00:04:18,120 --> 00:04:22,430
To je mogao biti jedan dopis ili to može biti slijed dva slova.

62
00:04:22,430 --> 00:04:27,790
I tako ono što Huffman stabala radi jer po prirodi likova

63
00:04:27,790 --> 00:04:34,140
ili naše konačne stvarni likovi su posljednji čvorovi na grani -

64
00:04:34,140 --> 00:04:39,300
mislimo na one što lišća - samim tim ne može biti bilo dvosmislenosti

65
00:04:39,300 --> 00:04:45,160
u terminima koje slovo ste pokušavali kodirati s nizom bitova

66
00:04:45,160 --> 00:04:50,670
jer nigdje uz bitova koji predstavljaju jedan dopis

67
00:04:50,670 --> 00:04:55,960
ćete naići na još jedan cijeli pismo, i tu neće biti nikakvih konfuzija tamo.

68
00:04:55,960 --> 00:04:58,430
No, mi ćemo ići na primjerima da vi zapravo može vidjeti da

69
00:04:58,430 --> 00:05:02,120
umjesto nas samo reći da je to istina.

70
00:05:02,120 --> 00:05:06,390
>> Pogledajmo jednostavan primjer Huffman stabla.

71
00:05:06,390 --> 00:05:09,380
Imam niz ovdje da je 12 znakova.

72
00:05:09,380 --> 00:05:14,010
Imam četiri Kao, 6 BS, i dva CS.

73
00:05:14,010 --> 00:05:17,270
Moj prvi korak bio bi računati.

74
00:05:17,270 --> 00:05:20,760
Koliko puta se pojavljuju? Čini se četiri puta u nizu.

75
00:05:20,760 --> 00:05:25,060
B pojavljuje 6 puta, i C se 2 puta.

76
00:05:25,060 --> 00:05:28,970
Naravno, ja ću reći da sam pomoću B najčešće,

77
00:05:28,970 --> 00:05:35,970
pa želim da predstavljaju B s najmanjim brojem bitova, najmanji broj 0S i 1S.

78
00:05:35,970 --> 00:05:42,600
I onda ja idem očekivati ​​C zahtijevati najveći iznos 0S i 1s kao dobro.

79
00:05:42,600 --> 00:05:48,550
Prvo što sam učinio ovdje sam stavio ih u rastućem poretku u smislu frekvencije.

80
00:05:48,550 --> 00:05:52,710
Vidimo da je C i, oni su naši dvije najniže frekvencije.

81
00:05:52,710 --> 00:06:00,290
Mi stvaramo roditeljski čvor, a da roditelj čvor ne imati pismo povezane s njom,

82
00:06:00,290 --> 00:06:05,070
ali ona ima frekvenciju, što je zbroj.

83
00:06:05,070 --> 00:06:08,780
Zbroj postaje 2 + 4, koji je 6.

84
00:06:08,780 --> 00:06:10,800
Onda smo slijediti lijevu granu.

85
00:06:10,800 --> 00:06:14,970
Ako smo bili u tom 6 čvora, onda bismo slijediti 0 doći do C

86
00:06:14,970 --> 00:06:17,450
i onda jednom doći do A.

87
00:06:17,450 --> 00:06:20,300
Dakle, sada imamo dva čvorova.

88
00:06:20,300 --> 00:06:23,920
Imamo vrijednost 6, a onda imamo još jedan čvor s vrijednošću 6.

89
00:06:23,920 --> 00:06:28,550
I tako one dvije nisu samo dvije najniže ali i samo dva koja su ostavila,

90
00:06:28,550 --> 00:06:33,820
tako da smo se pridruže onima drugi roditelj, sa zbrojem koji 12.

91
00:06:33,820 --> 00:06:36,300
Dakle, ovdje imamo Huffman stablo

92
00:06:36,300 --> 00:06:40,020
gdje doći do B, da bi samo biti malo 1

93
00:06:40,020 --> 00:06:45,430
i onda doći do bismo imati 01, a zatim C ima 00.

94
00:06:45,430 --> 00:06:51,300
Dakle, ovdje vidimo da je u osnovi smo zastupa ove znakova s ​​bilo 1 ili 2 bita

95
00:06:51,300 --> 00:06:55,160
gdje je B, kao što je predviđeno, ima najmanje.

96
00:06:55,160 --> 00:07:01,730
I onda smo očekivali C imaju najviše, ali budući da je kao mali Huffman stablo,

97
00:07:01,730 --> 00:07:06,020
tada također predstavlja dva bita za razliku negdje u sredini.

98
00:07:07,820 --> 00:07:11,070
>> Samo da ide preko drugog jednostavnom primjeru Huffman stabla,

99
00:07:11,070 --> 00:07:19,570
kažu da imaju niz "Zdravo".

100
00:07:19,570 --> 00:07:25,360
Što trebate učiniti je prvo što će reći koliko puta se H pojaviti u to?

101
00:07:25,360 --> 00:07:34,200
H pojavljuje jednom, a zatim e se jednom i onda imamo l pojavljuju dva puta

102
00:07:34,200 --> 00:07:36,580
te o pojavljuju jednom.

103
00:07:36,580 --> 00:07:44,310
I tako onda očekujemo koje slovo da ga zastupa najmanjim brojem bita?

104
00:07:44,310 --> 00:07:47,450
[Student] l. >> L. Aha. l je u pravu.

105
00:07:47,450 --> 00:07:50,730
Očekujemo l moraju predstavljati najmanjim brojem bitova

106
00:07:50,730 --> 00:07:55,890
jer sam se najviše koristi u nizu "Halo".

107
00:07:55,890 --> 00:08:04,280
Što ću učiniti sada je izvući iz ove čvorove.

108
00:08:04,280 --> 00:08:15,580
Imam 1, koji je H, a zatim još 1, što je E, a zatim 1, što je o -

109
00:08:15,580 --> 00:08:23,410
sada sam stavljajući ih u cilju - a zatim 2, koji je l.

110
00:08:23,410 --> 00:08:32,799
Tada sam rekao ono što sam izgraditi Huffman stablo je pronaći dvije čvorova sa najmanje frekvencijama

111
00:08:32,799 --> 00:08:38,010
i učiniti ih siblings stvaranjem roditeljski čvor.

112
00:08:38,010 --> 00:08:41,850
Ovdje imamo tri čvora s najnižom učestalosti. Oni su svi jedan.

113
00:08:41,850 --> 00:08:50,620
Dakle, ovdje ćemo odabrati koji ćemo povezati prvi.

114
00:08:50,620 --> 00:08:54,850
Ajmo reći da sam izabrati H i E.

115
00:08:54,850 --> 00:09:01,150
Zbroj 1 + 1 je 2, ali to čvor ne imati pismo povezane s njom.

116
00:09:01,150 --> 00:09:04,440
To samo ima vrijednost.

117
00:09:04,440 --> 00:09:10,950
Sada ćemo pogledati u narednih dva najnižim frekvencijama.

118
00:09:10,950 --> 00:09:15,590
To je 2 i 1. To bi mogao biti bilo koji od tih dva, ali ja ću izabrati ovu.

119
00:09:15,590 --> 00:09:18,800
Zbroj je tri.

120
00:09:18,800 --> 00:09:26,410
I onda na kraju, imam samo dva lijevo, pa onda to postaje 5.

121
00:09:26,410 --> 00:09:32,010
Onda ovdje, kao što se očekuje, ako sam ispunite kodiranje za to,

122
00:09:32,010 --> 00:09:37,480
1s uvijek pravo grana i 0s su lijevi.

123
00:09:37,480 --> 00:09:45,880
Onda imamo l zastupa samo jedan zalogaj i onda je O po dva

124
00:09:45,880 --> 00:09:52,360
a zatim e po 2, a zatim H padne na 3 bita.

125
00:09:52,360 --> 00:09:59,750
Dakle, možete prenijeti tu poruku "Hello" umjesto zapravo koristi znakove

126
00:09:59,750 --> 00:10:02,760
po samo 0s i 1s.

127
00:10:02,760 --> 00:10:07,910
Međutim, ne zaboravite da je u nekoliko slučajeva koje smo imali veze s našim frekvencije.

128
00:10:07,910 --> 00:10:11,900
Mogli bismo ni pridružili su H i O prvi možda.

129
00:10:11,900 --> 00:10:15,730
Ili onda kasnije, kada smo imali l zastupa dvoje

130
00:10:15,730 --> 00:10:19,410
kao i pridružio jedan zastupao 2, mogli smo povezani ni jedan.

131
00:10:19,410 --> 00:10:23,630
>> I tako kada poslati 0s i 1s, koji zapravo ne jamči

132
00:10:23,630 --> 00:10:27,090
da primatelj može u potpunosti pročitati vašu poruku pravo isključiti šišmiš

133
00:10:27,090 --> 00:10:30,490
jer oni ne mogu znati što ste napravili odluku.

134
00:10:30,490 --> 00:10:34,920
Dakle, kada imamo posla s Huffman kompresije,

135
00:10:34,920 --> 00:10:40,090
nekako moramo reći primatelja naše poruke kako smo odlučili -

136
00:10:40,090 --> 00:10:43,470
Oni moraju znati nekakav dodatne informacije

137
00:10:43,470 --> 00:10:46,580
osim komprimiranog poruke.

138
00:10:46,580 --> 00:10:51,490
Oni trebaju shvatiti što je stablo zapravo izgleda,

139
00:10:51,490 --> 00:10:55,450
kako mi je zapravo napravio tih odluka.

140
00:10:55,450 --> 00:10:59,100
>> Ovdje smo samo radili primjere na temelju stvarnog broja,

141
00:10:59,100 --> 00:11:01,550
ali ponekad možete imati Huffman stablo

142
00:11:01,550 --> 00:11:05,760
temelji se na frekvenciji na kojoj se pojavljuju slova, a to je isti proces.

143
00:11:05,760 --> 00:11:09,090
Evo ja sam ga izražava u procentima ili frakcije,

144
00:11:09,090 --> 00:11:11,290
i tako je i ovdje točno ista stvar.

145
00:11:11,290 --> 00:11:15,300
Ja pronašli dva najniža ih Ukratko, sljedeći dva najniža ih zbrojiti,

146
00:11:15,300 --> 00:11:19,390
dok imam punu stablo.

147
00:11:19,390 --> 00:11:23,610
Iako bismo mogli to učiniti bilo koji način, kad smo se bavi postocima,

148
00:11:23,610 --> 00:11:27,760
to znači da smo dijeljenjem stvari i bave decimala odnosno pluta

149
00:11:27,760 --> 00:11:30,900
ako ćemo razmišljati o podatkovnih struktura glave.

150
00:11:30,900 --> 00:11:32,540
Što znamo o plovaka?

151
00:11:32,540 --> 00:11:35,180
Što je čest problem kada imamo posla s plovcima?

152
00:11:35,180 --> 00:11:38,600
[Student] neprecizan aritmetika. >> Da. Nepreciznost.

153
00:11:38,600 --> 00:11:43,760
Zbog pomičnim zarezom nepreciznosti, za ovaj pset, tako da smo bili sigurni

154
00:11:43,760 --> 00:11:49,450
da mi ne izgubiti sve vrijednosti, onda mi zapravo idemo se bave računati.

155
00:11:49,450 --> 00:11:54,880
Dakle, ako ste bili razmišljati o Huffman čvor, ako se osvrnuti na strukturu ovdje,

156
00:11:54,880 --> 00:12:01,740
ako pogledate zelene one ima frekvenciju povezane s njom

157
00:12:01,740 --> 00:12:08,760
, kao i to ukazuje na čvor na svojoj lijevoj strani, kao i čvor na njegovo pravo.

158
00:12:08,760 --> 00:12:13,970
I onda one crvene tamo također imaju karakter povezane s njima.

159
00:12:13,970 --> 00:12:18,900
Nećemo napraviti odvojene one za roditelje i zatim završnih čvorova,

160
00:12:18,900 --> 00:12:23,680
što mi nazivamo lišća, nego one samo imati NULL vrijednosti.

161
00:12:23,680 --> 00:12:31,050
Za svaki čvor ćemo imati karakter, simbol da je taj čvor predstavlja,

162
00:12:31,050 --> 00:12:40,490
onda frekvencija, kao i pokazivač na svojoj lijevoj djeteta, kao i svoje pravo djeteta.

163
00:12:40,490 --> 00:12:45,680
Listovi, koji su na samom dnu, također će imati čvor upućuje

164
00:12:45,680 --> 00:12:49,550
s njihove lijeve strane, a na njihova prava, ali budući da se te vrijednosti ne ukazuju na stvarne čvorova,

165
00:12:49,550 --> 00:12:53,970
što bi njihova vrijednost bila? >> [Student] NULL. >> NULL. Točno.

166
00:12:53,970 --> 00:12:58,430
Evo primjera kako biste mogli predstavljaju frekvencije u plovaka,

167
00:12:58,430 --> 00:13:02,130
ali mi ćemo se baviti s njim s brojeva,

168
00:13:02,130 --> 00:13:06,780
tako da sve što sam učinio je promijeniti tip podataka postoji.

169
00:13:06,780 --> 00:13:09,700
>> Idemo na malo više od složenog primjer.

170
00:13:09,700 --> 00:13:13,360
Ali sada da smo učinili jednostavne one, to je samo isti proces.

171
00:13:13,360 --> 00:13:20,290
Možete pronaći dvije najniže frekvencije, zbroj frekvencija

172
00:13:20,290 --> 00:13:22,450
i da je nova frekvencija vašeg matičnog čvora,

173
00:13:22,450 --> 00:13:29,310
koji je tada ukazuje na svojoj lijevoj strani s 0 podružnice i pravo s jedne grane.

174
00:13:29,310 --> 00:13:34,200
Ako imamo niz "Ovo je cs50", onda ćemo brojati koliko puta je T spomenuto,

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

176
00:13:38,420 --> 00:13:42,010
Onda ono što sam učinio ovdje je s crvenim čvorova sam zasađenih,

177
00:13:42,010 --> 00:13:48,530
Rekla sam da ću imati ove znakove na kraju na dnu mog stabla.

178
00:13:48,530 --> 00:13:51,740
Oni su idući u biti sve od lišća.

179
00:13:51,740 --> 00:13:58,200
Onda ono što sam učinio je da sam ih sortirati po učestalosti u uzlaznom redoslijedu,

180
00:13:58,200 --> 00:14:02,950
i to je zapravo način na koji se to radi kod pset

181
00:14:02,950 --> 00:14:07,550
Je li to sortira po učestalosti i onda po abecednom redu.

182
00:14:07,550 --> 00:14:13,870
Tako da ima brojeve, a zatim po abecednom redu frekvenciji.

183
00:14:13,870 --> 00:14:18,520
Onda ono što ću učiniti je ja bi pronašli dva najniža. To je 0 i 5.

184
00:14:18,520 --> 00:14:22,390
Ja bih ih zbrojiti, a to je dva. Onda bih nastaviti, naći sljedeći dva najniža.

185
00:14:22,390 --> 00:14:26,100
To su dva 1s, a onda oni postaju 2 kao dobro.

186
00:14:26,100 --> 00:14:31,570
Sada znam da je moj sljedeći korak će biti spajanje najmanji broj,

187
00:14:31,570 --> 00:14:41,380
što je T, 1, a zatim odabirom jedne od čvorova koji ima 2 kao frekvencije.

188
00:14:41,380 --> 00:14:44,560
Dakle, ovdje imamo tri opcije.

189
00:14:44,560 --> 00:14:47,980
Što ću učiniti za slajd samo vizualno ih preurediti za vas

190
00:14:47,980 --> 00:14:51,790
tako da možete vidjeti kako ću ga gradi.

191
00:14:51,790 --> 00:14:59,040
Što kod i vaš distribucija koda će učiniti da bi se pridružiti T jedan

192
00:14:59,040 --> 00:15:01,410
s 0 i 5 čvora.

193
00:15:01,410 --> 00:15:05,060
Pa onda da iznosi do tri, a onda smo se nastavi proces.

194
00:15:05,060 --> 00:15:08,660
The 2 i 2 sada su najniže, pa onda oni zbroj za četiri.

195
00:15:08,660 --> 00:15:12,560
Svatko slijedi do sada? Ok.

196
00:15:12,560 --> 00:15:16,410
Onda nakon toga imamo tri i tri koje je potrebno da se zbrajaju,

197
00:15:16,410 --> 00:15:21,650
pa opet ja sam samo to prebacivanje tako da možete vidjeti vizualno tako da se ne bi previše neuredan.

198
00:15:21,650 --> 00:15:25,740
Onda imamo šest, a onda je naša konačna korak je da sada imamo samo dva čvorova

199
00:15:25,740 --> 00:15:30,440
Ukratko ćemo one bi korijen našeg stabla, što je 10.

200
00:15:30,440 --> 00:15:34,100
A broj 10 ima smisla, jer svaki čvor predstavlja,

201
00:15:34,100 --> 00:15:40,750
njihova vrijednost, njihova učestalost broj, bio koliko puta su se pojavili u nizu,

202
00:15:40,750 --> 00:15:46,350
i onda imamo pet znakova u našem nizu, tako da ima smisla.

203
00:15:48,060 --> 00:15:52,320
Ako ćemo gledati na koliko smo zapravo bi ga kodirati,

204
00:15:52,320 --> 00:15:56,580
kao što se očekivalo, ja i S, koje se pojavljuju najčešće

205
00:15:56,580 --> 00:16:01,350
predstavljaju manjem broju bitova.

206
00:16:03,660 --> 00:16:05,660
>> Budite oprezni ovdje.

207
00:16:05,660 --> 00:16:09,780
U Huffman stabala slučaj zapravo važno.

208
00:16:09,780 --> 00:16:13,670
S velikim slovima je drugačiji nego malim slovom S.

209
00:16:13,670 --> 00:16:21,260
Ako smo imali "Ovo je CS50" s velikim slovima, onda je mala i pojavit će se tek dva puta,

210
00:16:21,260 --> 00:16:27,120
će biti čvor s dva kao svoje vrijednosti, a zatim veliko S će biti samo jednom.

211
00:16:27,120 --> 00:16:33,440
Pa onda vaše stablo će promijeniti strukturu jer ste zapravo imaju dodatni list ovdje.

212
00:16:33,440 --> 00:16:36,900
No, iznos i dalje će biti 10.

213
00:16:36,900 --> 00:16:39,570
To je ono što mi zapravo idemo se zovete ček,

214
00:16:39,570 --> 00:16:44,060
dodatak od svih računa.

215
00:16:46,010 --> 00:16:50,990
>> Sada kada smo pokriveni Huffman stabala, možemo zaroniti u Huff'n lisnato, The pset.

216
00:16:50,990 --> 00:16:52,900
Mi ćemo početi s dijela pitanja,

217
00:16:52,900 --> 00:16:57,990
i to će doći na koju ste navikli kod binarnih stabala i kako raditi oko toga:

218
00:16:57,990 --> 00:17:03,230
crtanje čvorovi, stvarajući svoj vlastiti typedef struct za čvor,

219
00:17:03,230 --> 00:17:07,230
i gledajući kako biste mogli umetnuti u binarno stablo, jedan koji je sortiran,

220
00:17:07,230 --> 00:17:09,050
poprijeko ga, i slične stvari.

221
00:17:09,050 --> 00:17:14,560
To znanje definitivno će vam pomoći kada zaronite u dijelu Huff'n Puff

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

223
00:17:19,150 --> 00:17:26,329
U standardnom izdanju pset, vaš je zadatak provesti Puff,

224
00:17:26,329 --> 00:17:30,240
i hakerske verziji Vaš zadatak je provesti Huff.

225
00:17:30,240 --> 00:17:38,490
Što Huff ipak to traje tekst i onda ga prevodi u 0s i 1s,

226
00:17:38,490 --> 00:17:41,990
tako da je proces koji smo radili gore, gdje smo brojali frekvencije

227
00:17:41,990 --> 00:17:50,970
, a zatim je stablo, a zatim je rekao: "Kako mogu dobiti T?"

228
00:17:50,970 --> 00:17:54,840
T predstavlja 100, slične stvari,

229
00:17:54,840 --> 00:17:58,860
i onda Huff bi tekst, a zatim izlaz da binarno.

230
00:17:58,860 --> 00:18:04,920
Ali, isto tako, jer znamo da želimo omogućiti našim primatelja poruke

231
00:18:04,920 --> 00:18:11,790
ponovno isti stablo, ona također sadrži informacije o frekvencijskim tačkama.

232
00:18:11,790 --> 00:18:17,980
Tada s lisnato smo dobili binarnu datoteku 0S i 1S

233
00:18:17,980 --> 00:18:21,740
i dao je također podatke o frekvencijama.

234
00:18:21,740 --> 00:18:26,740
Mi prevodimo sve one 0s i 1s natrag u izvornu poruku da je,

235
00:18:26,740 --> 00:18:29,350
tako da smo decompressing da.

236
00:18:29,350 --> 00:18:36,450
Ako radite standardni izdanje, ne morate provesti Huff,

237
00:18:36,450 --> 00:18:39,290
pa onda možete samo koristiti osoblje provedbu Huff.

238
00:18:39,290 --> 00:18:42,080
Tu su i upute za spec. o tome kako to učiniti.

239
00:18:42,080 --> 00:18:48,780
Možete pokrenuti osoblje provedbu Huff na određene tekstualne datoteke

240
00:18:48,780 --> 00:18:53,270
i onda koristiti taj izlaz kao ulaz za Puff.

241
00:18:53,270 --> 00:18:59,330
>> Kao što sam spomenuo prije, imamo puno distribucije koda za ovaj jedan.

242
00:18:59,330 --> 00:19:01,810
Ja ću početi prolazi kroz njega.

243
00:19:01,810 --> 00:19:04,400
Ja ću provesti većinu vremena na internetu. H slika

244
00:19:04,400 --> 00:19:07,660
jer u c. datoteka, jer mi imamo. h

245
00:19:07,660 --> 00:19:11,650
i da nam se pruža s prototipova funkcija,

246
00:19:11,650 --> 00:19:15,520
mi u potpunosti ne treba shvatiti točno -

247
00:19:15,520 --> 00:19:20,280
Ako ne razumiju što se događa u c. Datotekama, onda ne brinite previše,

248
00:19:20,280 --> 00:19:23,600
ali definitivno pokušati pogledati, jer bi to moglo dati neke savjete

249
00:19:23,600 --> 00:19:29,220
i to je korisno da se koristi za čitanje tuđe koda.

250
00:19:38,940 --> 00:19:48,270
>> Gledajući huffile.h, u komentarima to izjavljuje sloj apstrakcije za Huffman kodiranih datoteka.

251
00:19:48,270 --> 00:20:01,660
Ako idemo dolje, vidimo da je maksimalno 256 znakova koje smo možda trebati kodove za.

252
00:20:01,660 --> 00:20:05,480
To uključuje sve slova abecede - velikih i malih -

253
00:20:05,480 --> 00:20:08,250
i onda simboli i brojevi, itd.

254
00:20:08,250 --> 00:20:11,930
Onda ovdje imamo čarobni broj identificira Huffman-coded datoteku.

255
00:20:11,930 --> 00:20:15,890
Unutar Huffman koda oni će imati određenu čarobnu broj

256
00:20:15,890 --> 00:20:18,560
povezan s zaglavlja.

257
00:20:18,560 --> 00:20:21,110
To bi moglo izgledati samo slučajnih čarobni broj,

258
00:20:21,110 --> 00:20:27,160
ali ako zaista prevesti ga u ASCII, onda je to zapravo navodi Huff.

259
00:20:27,160 --> 00:20:34,290
Ovdje imamo struct za Huffman-kodirane datoteke.

260
00:20:34,290 --> 00:20:39,670
Tu je sve od tih karakteristika povezanih s Huff datoteku.

261
00:20:39,670 --> 00:20:47,080
Onda ovdje dolje imamo zaglavlje za ljutnja datoteku, tako da mi to zovemo Huffeader

262
00:20:47,080 --> 00:20:50,810
umjesto dodajući dodatni h jer to zvuči isto svejedno.

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

264
00:20:52,720 --> 00:20:57,790
Imamo čarobni broj povezan s njim.

265
00:20:57,790 --> 00:21:09,040
Ako je stvarna Huff datoteke, to će biti broj gore, ovaj čarobni jedan.

266
00:21:09,040 --> 00:21:14,720
A onda će imati niz.

267
00:21:14,720 --> 00:21:18,750
Dakle, za svaki simbol, od kojih su 256,

268
00:21:18,750 --> 00:21:24,760
to će navesti što je učestalost tih simbola su unutar Huff datoteku.

269
00:21:24,760 --> 00:21:28,090
I onda napokon, imamo ček za frekvencije,

270
00:21:28,090 --> 00:21:32,160
koji bi trebao biti zbroj tih frekvencija.

271
00:21:32,160 --> 00:21:36,520
Dakle, to je ono što je Huffeader.

272
00:21:36,520 --> 00:21:44,600
Onda imamo neke funkcije koje vraćaju sljedećoj malo u Huff datoteku

273
00:21:44,600 --> 00:21:52,580
kao piše malo na Huff datoteku, a zatim je ova funkcija ovdje, hfclose,

274
00:21:52,580 --> 00:21:54,650
da zapravo zatvara Huff datoteku.

275
00:21:54,650 --> 00:21:57,290
Prije smo bili bave ravno samo fclose,

276
00:21:57,290 --> 00:22:01,190
ali kad imate Huff datoteku, umjesto da ga fclosing

277
00:22:01,190 --> 00:22:06,080
ono što ste zapravo će učiniti je hfclose i hfopen.

278
00:22:06,080 --> 00:22:13,220
Oni su specifične funkcije do Huff datoteka koje ćemo se baviti.

279
00:22:13,220 --> 00:22:19,230
Onda ovdje čitamo u zaglavlju, a zatim napisati zaglavlje.

280
00:22:19,230 --> 00:22:25,700
>> Samo čitajući. H datoteku možemo vrsta dobiti osjećaj za ono što Huff datoteka može biti,

281
00:22:25,700 --> 00:22:32,480
što obilježja ima, bez zapravo događa u huffile.c,

282
00:22:32,480 --> 00:22:36,750
koji, ako ćemo roniti u, što će biti malo složeniji.

283
00:22:36,750 --> 00:22:41,270
Ona ima sve datoteke I / O ovdje bavi pokazivače.

284
00:22:41,270 --> 00:22:48,010
Ovdje vidimo da kada mi zovemo hfread, na primjer, to je još uvijek bave fread.

285
00:22:48,010 --> 00:22:53,050
Mi ne uzimajući osloboditi od tih funkcija u potpunosti, ali šaljemo onima koji će se pobrinuti

286
00:22:53,050 --> 00:22:59,760
unutar Huff datoteku umjesto radiš sve to mi sami.

287
00:22:59,760 --> 00:23:02,300
Možete slobodno skenirati kroz to, ako vas zanima

288
00:23:02,300 --> 00:23:08,410
i otići i oguliti sloju leđa malo.

289
00:23:20,650 --> 00:23:24,060
>> Sljedeći sliku da ćemo pogledati je tree.h.

290
00:23:24,060 --> 00:23:30,210
Prije u Walkthrough klizi mi je rekao očekujemo Huffman čvor

291
00:23:30,210 --> 00:23:32,960
i napravili smo typedef struct čvor.

292
00:23:32,960 --> 00:23:38,360
Očekujemo da imaju simbol, frekvencija i onda dva čvora zvijezde.

293
00:23:38,360 --> 00:23:41,870
U tom slučaju ono što mi radimo je to u suštini isti

294
00:23:41,870 --> 00:23:46,880
osim umjesto čvora ćemo zvati ih stabala.

295
00:23:48,790 --> 00:23:56,760
Imamo funkciju da kada nazovete učiniti stablo se vraća vam stablo pokazivač.

296
00:23:56,760 --> 00:24:03,450
Povratak na Speller, kada su stvaranje novog čvora

297
00:24:03,450 --> 00:24:11,410
rekli ste čvor * nova riječ = malloc (sizeof) i slične stvari.

298
00:24:11,410 --> 00:24:17,510
Uglavnom, mktree će se baviti za vas.

299
00:24:17,510 --> 00:24:20,990
Slično tome, kada želite ukloniti stablo,

300
00:24:20,990 --> 00:24:24,810
tako da u suštini je oslobađajući stablo Kada završite s njim,

301
00:24:24,810 --> 00:24:33,790
umjesto izričito poziva besplatno na to, zapravo samo će koristiti funkciju rmtree

302
00:24:33,790 --> 00:24:40,360
gdje ste proći u pokazivač za tog stabla, a zatim tree.c će se pobrinuti da se za vas.

303
00:24:40,360 --> 00:24:42,490
>> Mi gledamo u tree.c.

304
00:24:42,490 --> 00:24:47,240
Očekujemo iste funkcije, osim da vidi provedbe, kao dobro.

305
00:24:47,240 --> 00:24:57,720
Kao što smo i očekivali, kada nazovete mktree to mallocs veličinu stabla u pokazivač,

306
00:24:57,720 --> 00:25:03,190
inicijalizira sve vrijednosti na null vrijednost, tako 0S ili ugašenih,

307
00:25:03,190 --> 00:25:08,280
, a zatim se vraća pokazivač na taj stabla koje ste upravo malloc'd za vas.

308
00:25:08,280 --> 00:25:13,340
Ovdje kada nazovete ukloniti stablo je prvi čini sigurni da ste ne dvostruko oslobađanju.

309
00:25:13,340 --> 00:25:18,320
To čini sigurni da ste zapravo imaju stablo koje želite ukloniti.

310
00:25:18,320 --> 00:25:23,330
Ovdje jer stablo također uključuje svoje djece,

311
00:25:23,330 --> 00:25:29,560
što to znači je to rekurzivno poziva ukloniti stablo na lijevoj čvor stabla

312
00:25:29,560 --> 00:25:31,650
kao i pravo čvora.

313
00:25:31,650 --> 00:25:37,790
Prije nego što se oslobađa roditelja, treba ga osloboditi djecu kao dobro.

314
00:25:37,790 --> 00:25:42,770
Roditelj je također zamjenjiva s korijenom.

315
00:25:42,770 --> 00:25:46,500
Prvi roditelj, pa kao pra-pra-pra-pra-pradjed

316
00:25:46,500 --> 00:25:52,130
ili baka stablo, prvo moramo osloboditi dolje razine prvi.

317
00:25:52,130 --> 00:25:58,490
Tako poprijeko na dno, bez one, a zatim se vratiti gore, bez onih, itd.

318
00:26:00,400 --> 00:26:02,210
Tako da je stablo.

319
00:26:02,210 --> 00:26:04,240
>> Sada ćemo pogledati šumi.

320
00:26:04,240 --> 00:26:09,860
Šuma je mjesto gdje ćete sve svoje Huffman stabala.

321
00:26:09,860 --> 00:26:12,910
To govori da ćemo imati nešto zove zemljište

322
00:26:12,910 --> 00:26:22,320
koji sadrži pokazivač na stablu, kao i upustvo na parceli zove sljedeći.

323
00:26:22,320 --> 00:26:28,480
Što struktura čini ovu vrstu izgledaju?

324
00:26:29,870 --> 00:26:32,490
To je vrsta to kaže tamo.

325
00:26:34,640 --> 00:26:36,700
Pravo ovamo.

326
00:26:37,340 --> 00:26:39,170
Povezani popis.

327
00:26:39,170 --> 00:26:44,590
Vidimo da kada imamo zemljište to je kao povezane popis parcela.

328
00:26:44,590 --> 00:26:53,020
Šuma je definirana kao povezane popis parcela,

329
00:26:53,020 --> 00:26:58,100
i tako je struktura šuma mi smo samo će imati pokazivač na naš prvi parceli

330
00:26:58,100 --> 00:27:02,740
i da zemljište ima stablo unutar nje, odnosno ukazuje na stablu

331
00:27:02,740 --> 00:27:06,190
, a zatim ukazuje na sljedeću parceli, tako dalje i tako dalje.

332
00:27:06,190 --> 00:27:11,100
Da bi šumu zovemo mkforest.

333
00:27:11,100 --> 00:27:14,930
Onda imamo neke prilično korisne funkcije ovdje.

334
00:27:14,930 --> 00:27:23,240
Imamo pokupiti gdje ste proći u šumi, a potom povratna vrijednost je stablo *,

335
00:27:23,240 --> 00:27:25,210
pokazivač na stablo.

336
00:27:25,210 --> 00:27:29,370
Što pick će učiniti je da će ići u šumu da ste pokazujući na

337
00:27:29,370 --> 00:27:35,240
zatim uklonite stablo s najnižom učestalosti od tog šumi

338
00:27:35,240 --> 00:27:38,330
i onda vam dati pokazivač tog stabla.

339
00:27:38,330 --> 00:27:43,030
Nakon što nazivamo pokupiti, drvo neće postojati u šumi više,

340
00:27:43,030 --> 00:27:48,550
ali povratna vrijednost je pokazivač na tom stablu.

341
00:27:48,550 --> 00:27:50,730
Tada imate biljku.

342
00:27:50,730 --> 00:27:57,420
Pod uvjetom da ste proći pokazivač na stablo koje ima ne-0 frekvenciju,

343
00:27:57,420 --> 00:28:04,040
što biljka će učiniti je da će se u šumu, uzeti stablo, a biljka koja stabla unutar šume.

344
00:28:04,040 --> 00:28:06,370
Ovdje imamo rmforest.

345
00:28:06,370 --> 00:28:11,480
Slično ukloniti stabla, koja u osnovi oslobođeni svih naših stabala za nas,

346
00:28:11,480 --> 00:28:16,600
uklanjanje šuma će besplatno sve sadržano u toj šumi.

347
00:28:16,600 --> 00:28:24,890
>> Ako ćemo gledati u forest.c, mi ćemo očekivati ​​da će vidjeti barem jednom rmtree naredbu tamo,

348
00:28:24,890 --> 00:28:30,090
jer radi oslobađanja memorije u šumi, ako šuma ima stabala u njemu,

349
00:28:30,090 --> 00:28:32,930
onda na kraju ćete morati ukloniti one stabala previše.

350
00:28:32,930 --> 00:28:41,020
Ako ćemo gledati u forest.c, imamo mkforest, koji je kao što smo očekivali.

351
00:28:41,020 --> 00:28:42,890
Mi malloc stvari.

352
00:28:42,890 --> 00:28:51,740
Mi inicijalizirati prvu radnju u šumi kao NULL, jer to je prazna za početak,

353
00:28:51,740 --> 00:29:05,940
onda ćemo vidjeti motika, koji vraća stablo uz najmanju težinu, što je najniža frekvencija,

354
00:29:05,940 --> 00:29:13,560
, a zatim dobiva osloboditi od tog čvora koji ukazuje na to stablo i pored jedne,

355
00:29:13,560 --> 00:29:16,760
tako da je potrebno da se od povezanog popisa šuma.

356
00:29:16,760 --> 00:29:24,510
I onda ovdje imamo biljka, koja se umeće stablo u povezane liste.

357
00:29:24,510 --> 00:29:29,960
Što šuma ne je to lijepo drži razvrstani za nas.

358
00:29:29,960 --> 00:29:37,910
I onda napokon, imamo rmforest i, kako se očekuje, imamo rmtree zove tamo.

359
00:29:46,650 --> 00:29:55,440
>> Gledajući na distribucijsku koda tako daleko, huffile.c je vjerojatno bio daleko najteže razumjeti,

360
00:29:55,440 --> 00:29:59,990
dok druge datoteke i sami bili prilično jednostavno slijediti.

361
00:29:59,990 --> 00:30:03,090
Uz naše znanje upućuje i povezanih listama i takvih,

362
00:30:03,090 --> 00:30:04,860
bili smo u mogućnosti pratiti prilično dobro.

363
00:30:04,860 --> 00:30:10,500
No, sve što je potrebno kako bi stvarno bili sigurni da ćemo u potpunosti razumjeti je. H slika

364
00:30:10,500 --> 00:30:15,840
jer vam je potrebno da se zove ta funkcija, koja se bavi tim povratnih vrijednosti,

365
00:30:15,840 --> 00:30:20,590
kako bi bili sigurni da ste u potpunosti razumjeli što akcija će biti izvedena

366
00:30:20,590 --> 00:30:24,290
kad god nazvati jedan od tih funkcija.

367
00:30:24,290 --> 00:30:33,020
Ali zapravo razumijevanje unutar nje nije sasvim neophodno jer imamo one. H datoteke.

368
00:30:35,170 --> 00:30:39,490
Imamo dva više datoteke preostale u našem distribucije koda.

369
00:30:39,490 --> 00:30:41,640
>> Pogledajmo deponij.

370
00:30:41,640 --> 00:30:47,230
Kiperi svojim komentarom ovdje ima Huffman sažetu datoteku

371
00:30:47,230 --> 00:30:55,580
a zatim prevodi i deponijama sve njezin sadržaj vani.

372
00:31:01,010 --> 00:31:04,260
Ovdje vidimo da je to zove hfopen.

373
00:31:04,260 --> 00:31:10,770
To je vrsta zrcaljenje podnijeti * Ulazni = fopen,

374
00:31:10,770 --> 00:31:13,500
i onda prođe u informacijama.

375
00:31:13,500 --> 00:31:18,240
To je gotovo identična, osim umjesto datoteke * ste prolazi u Huffile;

376
00:31:18,240 --> 00:31:22,030
umjesto fopen ste prolazi u hfopen.

377
00:31:22,030 --> 00:31:29,280
Ovdje možemo pročitati u zaglavlju prvi, što je vrsta slična kako čitamo u zaglavlju

378
00:31:29,280 --> 00:31:33,580
za bitmap datoteku.

379
00:31:33,580 --> 00:31:38,000
Ono što mi radimo ovdje je provjera kako bi vidjeli hoće li informacije u zaglavlju

380
00:31:38,000 --> 00:31:44,330
sadrži pravu čaroliju broj koji ukazuje da je stvarna Huff datoteka,

381
00:31:44,330 --> 00:31:53,610
onda sve ove provjere kako bi bili sigurni da je datoteka koje smo otvoreni je stvarna huffed datoteka ili ne.

382
00:31:53,610 --> 00:32:05,330
Što to znači je ona izlazi frekvencije svih simbola koje možemo vidjeti

383
00:32:05,330 --> 00:32:09,790
unutar terminala u grafičkom tablici.

384
00:32:09,790 --> 00:32:15,240
Ovaj dio će biti korisna.

385
00:32:15,240 --> 00:32:24,680
To je malo i čita malo po malo u varijablu malo, a zatim ga ispisuje.

386
00:32:28,220 --> 00:32:35,430
Dakle, ako sam bio na poziv deponij na hth.bin, što je rezultat huffing datoteku

387
00:32:35,430 --> 00:32:39,490
pomoću osoblja rješenje, ja bih se toga.

388
00:32:39,490 --> 00:32:46,000
To je outputting svih tih likova, a zatim stavljanjem frekvenciju na kojoj se pojavljuju.

389
00:32:46,000 --> 00:32:51,180
Ako gledamo, a većina njih su 0s osim za ovo: H, koja se pojavljuje dva puta,

390
00:32:51,180 --> 00:32:54,820
a zatim T, koja se pojavljuje nakon.

391
00:32:54,820 --> 00:33:07,860
I onda ovdje imamo stvarnu poruku 0s i 1s.

392
00:33:07,860 --> 00:33:15,450
Ako gledamo hth.txt, što je vjerojatno je izvorna poruka koje je huffed,

393
00:33:15,450 --> 00:33:22,490
očekujemo da će vidjeti neke HS i TS tamo.

394
00:33:22,490 --> 00:33:28,720
Naime, očekujemo kako bi vidjeli samo jedan T i dvije HS.

395
00:33:32,510 --> 00:33:37,440
Ovdje smo u hth.txt. To zaista ima HTH.

396
00:33:37,440 --> 00:33:41,270
Uključeno u tu, iako ne možemo vidjeti, je newline karakter.

397
00:33:41,270 --> 00:33:53,190
The hth.bin Huff datoteka također je kodiranje newline karakter kao dobro.

398
00:33:55,680 --> 00:34:01,330
Evo, jer znamo da bi je HTH i onda newline,

399
00:34:01,330 --> 00:34:07,340
možemo vidjeti da je vjerojatno H predstavlja samo jednu jednom

400
00:34:07,340 --> 00:34:17,120
a zatim T je vjerojatno 01 i zatim sljedeća H 1 kao i

401
00:34:17,120 --> 00:34:21,139
i onda imamo newline ukazuje na dvije 0S.

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

403
00:34:26,530 --> 00:34:31,600
>> I onda napokon, jer smo se bave više. St. i. H datoteke,

404
00:34:31,600 --> 00:34:36,350
idemo imaju prilično složene argument prevodilac,

405
00:34:36,350 --> 00:34:40,460
pa ovdje imamo makefile koji čini deponij za vas.

406
00:34:40,460 --> 00:34:47,070
Ali, zapravo, morate ići oko izrade vlastite puff.c datoteku.

407
00:34:47,070 --> 00:34:54,330
The Makefile zapravo ne bave izradu puff.c za vas.

408
00:34:54,330 --> 00:34:59,310
Odlazimo da do vas urediti Makefile.

409
00:34:59,310 --> 00:35:05,930
Kad unesete naredbu poput učiniti sve, na primjer, da će učiniti sve od njih za vas.

410
00:35:05,930 --> 00:35:10,760
Slobodno pogledate primjere makefile iz prošlosti pset

411
00:35:10,760 --> 00:35:17,400
kao i odlaze ovog jednog da vidite kako može biti u mogućnosti kako bi vaš lisnato datoteku

412
00:35:17,400 --> 00:35:20,260
uređivanjem ovaj makefile.

413
00:35:20,260 --> 00:35:22,730
To je otprilike to za naše distribucije koda.

414
00:35:22,730 --> 00:35:28,380
>> Nakon što smo dobili kroz to, onda ovdje je samo još jedan podsjetnik

415
00:35:28,380 --> 00:35:30,980
kako ćemo se baviti Huffman čvorova.

416
00:35:30,980 --> 00:35:35,400
Nećemo biti nazivajući ih čvorovi više, idemo se nazivajući ih stabala

417
00:35:35,400 --> 00:35:39,260
gdje idemo se predstavlja svoj simbol s char,

418
00:35:39,260 --> 00:35:43,340
njihova učestalost, broj pojava, s cijeli broj.

419
00:35:43,340 --> 00:35:47,370
Mi koristimo jer je to preciznije nego plutaju.

420
00:35:47,370 --> 00:35:52,980
I onda imamo još jedan pokazivač na lijevu djeteta, kao i pravo djeteta.

421
00:35:52,980 --> 00:35:59,630
Šuma, kao što smo vidjeli, samo je povezana popis stabala.

422
00:35:59,630 --> 00:36:04,670
U konačnici, kada smo izgradnju naše Huff datoteku,

423
00:36:04,670 --> 00:36:07,580
želimo naše šume da sadrži samo jedan stablo -

424
00:36:07,580 --> 00:36:12,420
1 stablo, jedan korijen s više djece.

425
00:36:12,420 --> 00:36:20,840
Ranije kad smo bili samo što naše Huffman stabala,

426
00:36:20,840 --> 00:36:25,360
počeli smo se postavljanjem svih čvorova na našem zaslonu

427
00:36:25,360 --> 00:36:27,790
i rekao da ćemo imati ove čvorove,

428
00:36:27,790 --> 00:36:32,920
na kraju oni će biti lišće, a to je njihov simbol, to je njihova frekvencija.

429
00:36:32,920 --> 00:36:42,070
U našoj šumi, ako imamo samo tri slova, da je šuma 3 stabala.

430
00:36:42,070 --> 00:36:45,150
I onda kao što smo ići dalje, kada smo dodali prvi roditelja,

431
00:36:45,150 --> 00:36:48,080
smo napravili šumu dva stabla.

432
00:36:48,080 --> 00:36:54,930
Uklonili smo dvije od one djece iz naše šume, a zatim ga zamijeniti s matičnom čvoru

433
00:36:54,930 --> 00:36:58,820
koji je imao one dvije čvorova kao i djeca.

434
00:36:58,820 --> 00:37:05,600
I onda na kraju, naš zadnji korak u izradi naš primjer s AS, BS, i Cs

435
00:37:05,600 --> 00:37:08,030
bi donijeti konačnu roditelja,

436
00:37:08,030 --> 00:37:13,190
pa onda da će donijeti naš ukupan broj stabala u šumi na jedan.

437
00:37:13,190 --> 00:37:18,140
Da li su svi vidjeli kako ste započeli s više stabala u šumi

438
00:37:18,140 --> 00:37:22,520
i završiti s jednom? Ok. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Što trebamo učiniti za lisnato?

440
00:37:28,110 --> 00:37:37,110
Ono što trebate učiniti je osigurati da, kao i uvijek, daju nam pravu vrstu ulaza

441
00:37:37,110 --> 00:37:39,090
tako da zapravo možemo pokrenuti program.

442
00:37:39,090 --> 00:37:43,130
U tom slučaju oni će biti dajući nam nakon svog prvog naredbenog retka argument

443
00:37:43,130 --> 00:37:53,440
2 više: datoteka koja želimo smanjivati, a izlaz otpakirati datoteke.

444
00:37:53,440 --> 00:38:00,410
No, kad smo bili sigurni da nam prođe u pravom iznosu od vrijednosti,

445
00:38:00,410 --> 00:38:05,820
želimo osigurati da je ulaz Huff datoteka ili ne.

446
00:38:05,820 --> 00:38:10,420
I onda odjednom jamčimo da je Huff datoteku, onda želimo graditi našu stablo,

447
00:38:10,420 --> 00:38:20,940
izgraditi stablo takav da odgovara stablo da osoba koja je poslala poruku izgrađen.

448
00:38:20,940 --> 00:38:25,840
Onda nakon što smo izgraditi stablo, onda možemo nositi s 0s i 1s da su prošli u,

449
00:38:25,840 --> 00:38:29,590
slijediti one uz našu stabla jer je identičan,

450
00:38:29,590 --> 00:38:33,510
i onda napisati tu poruku van, tumačiti bitova natrag u znakovi.

451
00:38:33,510 --> 00:38:35,880
I onda na kraju, jer smo se bave pokazivače ovdje,

452
00:38:35,880 --> 00:38:38,110
želimo biti sigurni da mi nemamo nikakve memory leaks

453
00:38:38,110 --> 00:38:41,330
i da smo slobodni sve.

454
00:38:42,820 --> 00:38:46,430
>> Osiguranje pravilno korištenje je stari šešir za nas do sada.

455
00:38:46,430 --> 00:38:51,980
Mi se u ulazu, koji će biti ime datoteke napuhati,

456
00:38:51,980 --> 00:38:56,010
i onda smo naveli izlaz,

457
00:38:56,010 --> 00:39:01,580
tako da je ime datoteke za napuhan izlaz, koji će biti tekstualna datoteka.

458
00:39:03,680 --> 00:39:08,820
To je običaj. A sada želimo osigurati da je ulaz huffed ili ne.

459
00:39:08,820 --> 00:39:16,420
Razmišljajući unatrag, je li nešto u distribuciji koda koji bi nam moglo pomoći

460
00:39:16,420 --> 00:39:21,570
s razumijevanjem da li je datoteka huffed ili ne?

461
00:39:21,570 --> 00:39:26,910
Došlo je do informacije u huffile.c o Huffeader.

462
00:39:26,910 --> 00:39:33,430
Znamo da je svaki Huff datoteka ima Huffeader povezane s njom s čarobnim brojem

463
00:39:33,430 --> 00:39:37,240
kao niz frekvencija za svaki simbol

464
00:39:37,240 --> 00:39:39,570
kao i checksum.

465
00:39:39,570 --> 00:39:43,180
Znamo da, ali mi smo također uzeo zaviriti u dump.c,

466
00:39:43,180 --> 00:39:49,120
u kojoj je čitao u Huff datoteku.

467
00:39:49,120 --> 00:39:53,990
I tako to učiniti, morao je provjeriti je li to stvarno bila huffed ili ne.

468
00:39:53,990 --> 00:40:03,380
Pa možda bismo mogli koristiti dump.c kao strukture za naše puff.c.

469
00:40:03,380 --> 00:40:12,680
Povratak na pset 4 kada smo imali datoteke copy.c da kopira u RGB trojke

470
00:40:12,680 --> 00:40:14,860
i mi tumači da je za detektivski roman i veličinu,

471
00:40:14,860 --> 00:40:20,390
slično, što bi mogao učiniti samo pokrenuti naredbu kao k.č. dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
i koristiti neke od zakonika.

473
00:40:23,600 --> 00:40:28,210
Međutim, to ne će biti kao jednostavan procesa

474
00:40:28,210 --> 00:40:33,010
za prevođenje svoj dump.c u puff.c,

475
00:40:33,010 --> 00:40:36,160
ali barem vam daje negdje početi

476
00:40:36,160 --> 00:40:40,540
o tome kako bi se osiguralo da je ulaz zapravo huffed ili ne

477
00:40:40,540 --> 00:40:43,240
kao i nekoliko drugih stvari.

478
00:40:45,930 --> 00:40:50,250
Osigurali smo pravilno korištenje i osigurao da je ulaz huffed.

479
00:40:50,250 --> 00:40:53,570
Svaki put da smo učinili što smo učinili našu pravilnu provjera,

480
00:40:53,570 --> 00:41:01,520
tako povratka i odvikavanje funkciju ako neke pogreške, ako postoji problem.

481
00:41:01,520 --> 00:41:07,170
>> Sada ono što želimo učiniti je izgraditi stvarni stablo.

482
00:41:08,840 --> 00:41:12,640
Ako ćemo gledati u šumi, tu su i dvije glavne funkcije

483
00:41:12,640 --> 00:41:15,800
da ćemo želite postati vrlo dobro poznaju.

484
00:41:15,800 --> 00:41:23,870
Tu je Booleova funkcija biljka koja biljke ne 0 frekvencija stabala unutar naše šume.

485
00:41:23,870 --> 00:41:29,250
I tako postoji li proći u pokazivač na šumu i pokazivač na stablo.

486
00:41:32,530 --> 00:41:40,340
Brzo pitanje: Koliko šume ćete imati kad ste izgradnji Huffman stablo?

487
00:41:44,210 --> 00:41:46,650
Naša šuma je kao naš platnu, zar ne?

488
00:41:46,650 --> 00:41:50,800
Tako smo samo ćeš imati jedan šumu, ali ćemo imati više stabala.

489
00:41:50,800 --> 00:41:57,590
Dakle, prije nego nazovete biljku vjerojatno idete da želite da vaš šumu.

490
00:41:57,590 --> 00:42:04,430
Tu je naredba za to ako pogledate u forest.h o tome kako možete napraviti šumu.

491
00:42:04,430 --> 00:42:09,270
Možete posaditi drvo. Mi znamo kako to učiniti.

492
00:42:09,270 --> 00:42:11,590
A onda možete odabrati stablo iz šume,

493
00:42:11,590 --> 00:42:17,540
uklanjanja stabla s najmanjom težinom i daje vam pokazivač na to.

494
00:42:17,540 --> 00:42:23,090
Osvrčući se kad smo radili na primjerima sebe,

495
00:42:23,090 --> 00:42:27,980
kada smo ga izvlači, mi jednostavno samo dodao linkove.

496
00:42:27,980 --> 00:42:31,680
Ali ovdje, umjesto samo dodao linkove,

497
00:42:31,680 --> 00:42:40,630
mislim da je to više kao da ste uklanjanjem dvije od tih čvorova, a zatim ga zamijeniti još jedan.

498
00:42:40,630 --> 00:42:44,200
Za izraziti da je u pitanju branje i sadnja,

499
00:42:44,200 --> 00:42:48,840
ste branje dva stabla, a zatim sadnju još stablo

500
00:42:48,840 --> 00:42:54,060
da ima one dvije stabala koje ste odabrali kao djeca.

501
00:42:57,950 --> 00:43:05,280
Za izgradnju Huffman je stablo, možete pročitati u simbolima i frekvencija u cilju

502
00:43:05,280 --> 00:43:10,790
jer Huffeader daje da bi vas,

503
00:43:10,790 --> 00:43:14,250
daje vam niz frekvencija.

504
00:43:14,250 --> 00:43:19,660
Dakle, možete ići naprijed i jednostavno ignorirati sve s 0 u njemu

505
00:43:19,660 --> 00:43:23,760
jer ne želimo 256 lišća na kraju njega.

506
00:43:23,760 --> 00:43:27,960
Mi samo želimo broj listova koji su likovi

507
00:43:27,960 --> 00:43:31,600
koji su zapravo koristi u datoteci.

508
00:43:31,600 --> 00:43:37,590
Možete pročitati u tim simbolima, a svaki od tih simbola koji imaju non-0 frekvencije,

509
00:43:37,590 --> 00:43:40,440
oni će biti stabla.

510
00:43:40,440 --> 00:43:45,990
Što možete učiniti je svaki put kad pročitate u non-0 frekvencije simbol,

511
00:43:45,990 --> 00:43:50,660
možete posaditi da stabla u šumi.

512
00:43:50,660 --> 00:43:56,620
Nakon što se biljka stabala u šumi, možete se pridružiti te stabla kao braća i sestre,

513
00:43:56,620 --> 00:44:01,130
pa ide natrag u sadnju i branje gdje pokupiti dvije, a zatim biljka 1,

514
00:44:01,130 --> 00:44:05,820
gdje je taj jedan da ti biljka je roditelj dvoje djece od koje beru.

515
00:44:05,820 --> 00:44:11,160
Pa onda tvoj krajnji rezultat će biti nijedno stablo u šumi.

516
00:44:16,180 --> 00:44:18,170
To je kako ste izgraditi stablo.

517
00:44:18,170 --> 00:44:21,850
>> Postoji nekoliko stvari koje bi mogle poći po zlu ovdje

518
00:44:21,850 --> 00:44:26,580
jer smo se bave s izradom novih stabala, a koje se bave upućuje i tome slično.

519
00:44:26,580 --> 00:44:30,450
Prije kad smo se bave pokazivače,

520
00:44:30,450 --> 00:44:36,580
kad smo malloc'd smo željeli biti sigurni da se ne vrati nam null pointer vrijednost.

521
00:44:36,580 --> 00:44:42,770
Dakle, na nekoliko koraka unutar tog procesa tamo će biti nekoliko slučajeva

522
00:44:42,770 --> 00:44:45,920
gdje je vaš program mogao uspjeti.

523
00:44:45,920 --> 00:44:51,310
Što želite učiniti je da želite da biste bili sigurni da ste radili te pogreške,

524
00:44:51,310 --> 00:44:54,580
au spec. piše da ih nositi dostojanstveno,

525
00:44:54,580 --> 00:45:00,280
tako bih ispisati poruku korisniku reći im zašto program mora prestati

526
00:45:00,280 --> 00:45:03,050
i onda odmah to prestati.

527
00:45:03,050 --> 00:45:09,490
Da biste to učinili rukovanje pogreškama, sjetite se da ga želite provjeriti

528
00:45:09,490 --> 00:45:12,160
svaki put da bi moglo biti neuspjeh.

529
00:45:12,160 --> 00:45:14,660
Svaki put da ste stvaranje novog pokazivač

530
00:45:14,660 --> 00:45:17,040
želite da biste bili sigurni da je to uspješan.

531
00:45:17,040 --> 00:45:20,320
Prije što smo učiniti je novi pokazivač i malloc ga,

532
00:45:20,320 --> 00:45:22,380
a onda bismo provjerili da li da pokazivač je NULL.

533
00:45:22,380 --> 00:45:25,670
Dakle, tu su idući u biti neki slučajevi gdje možete samo to učiniti,

534
00:45:25,670 --> 00:45:28,610
ali ponekad ste zapravo zove funkciju

535
00:45:28,610 --> 00:45:33,100
i unutar te funkcije, to je onaj koji je radi mallocing.

536
00:45:33,100 --> 00:45:39,110
U tom slučaju, ako se osvrnemo na neke od funkcija u kodu,

537
00:45:39,110 --> 00:45:42,260
neki od njih su Booleove funkcije.

538
00:45:42,260 --> 00:45:48,480
U apstraktnom slučaju ako imamo Booleova funkcija zove foo,

539
00:45:48,480 --> 00:45:54,580
u osnovi, možemo pretpostaviti da osim što god foo radi,

540
00:45:54,580 --> 00:45:57,210
budući da je Booleova funkcija, vraća true ili false -

541
00:45:57,210 --> 00:46:01,300
istina ako je uspješna, false ako nije.

542
00:46:01,300 --> 00:46:06,270
Dakle, želimo provjeriti je li povratak vrijednost foo je istinita ili lažna.

543
00:46:06,270 --> 00:46:10,400
Ako je lažna, to znači da ćemo ispisati nekakvu poruku

544
00:46:10,400 --> 00:46:14,390
a zatim zatvorite program.

545
00:46:14,390 --> 00:46:18,530
Ono što želimo učiniti je provjeriti povratnu vrijednost foo.

546
00:46:18,530 --> 00:46:23,310
Ako foo false, onda znamo da smo naišli neku vrstu pogreške

547
00:46:23,310 --> 00:46:25,110
i trebamo prestati naš program.

548
00:46:25,110 --> 00:46:35,600
Način da to učinite je imati stanje u kojem je stvarna funkcija sama po sebi je vaše stanje.

549
00:46:35,600 --> 00:46:39,320
Recimo foo uzima u x.

550
00:46:39,320 --> 00:46:43,390
Mi možemo imati kao uvjet if (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Uglavnom, to znači da ako na kraju izvršenja foo to true

552
00:46:50,900 --> 00:46:57,390
onda možemo to učiniti, jer je funkcija mora ocijeniti foo

553
00:46:57,390 --> 00:47:00,500
kako bi se procijenio cijeli stanje.

554
00:47:00,500 --> 00:47:06,500
Dakle to je kako možete učiniti nešto ako funkcija vraća istinita i je uspješna.

555
00:47:06,500 --> 00:47:11,800
No, kada ste pogreška provjere, samo želite prestati ako vaš funkcija vraća false.

556
00:47:11,800 --> 00:47:16,090
Što mogu učiniti samo dodati == false ili samo dodati prasak ispred njega

557
00:47:16,090 --> 00:47:21,010
i onda imate ako (! foo).

558
00:47:21,010 --> 00:47:29,540
U tom tijelu takvom stanju da bi sve pogreške rukovanja,

559
00:47:29,540 --> 00:47:36,940
tako sviđa, "ne mogu stvoriti ovo drvo", a zatim se vratiti jednog ili nešto slično.

560
00:47:36,940 --> 00:47:43,340
Što da ne, ipak, da iako foo vratio lažna -

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

562
00:47:46,980 --> 00:47:51,060
Onda nemate nazvati foo opet. To je uobičajena zabluda.

563
00:47:51,060 --> 00:47:54,730
Budući da je u svom zdravstvenom stanju, to je već ocijenjen,

564
00:47:54,730 --> 00:47:59,430
pa već imate rezultat, ako ste koristeći napraviti stablo ili nešto slično

565
00:47:59,430 --> 00:48:01,840
ili biljka ili pokupiti ili nešto.

566
00:48:01,840 --> 00:48:07,460
To već ima tu vrijednost. To je već izvršena.

567
00:48:07,460 --> 00:48:10,730
Dakle, to je korisno koristiti Boolean funkcije kao uvjet

568
00:48:10,730 --> 00:48:13,890
jer da li ili ne zapravo izvršiti tijelo petlje,

569
00:48:13,890 --> 00:48:18,030
izvršava funkciju ionako.

570
00:48:22,070 --> 00:48:27,330
>> Naš drugi na zadnji korak je pisanje poruke u datoteku.

571
00:48:27,330 --> 00:48:33,070
Nakon što smo izgraditi Huffman stablo, zatim pisanja poruke u datoteku je prilično jednostavan.

572
00:48:33,070 --> 00:48:39,260
To je prilično jednostavan sada samo slijediti 0S i 1S.

573
00:48:39,260 --> 00:48:45,480
I tako po konvenciji znamo da u Huffman stablo 0s ukazuju na lijevo

574
00:48:45,480 --> 00:48:48,360
i 1s pokazuju pravu.

575
00:48:48,360 --> 00:48:53,540
Dakle, ako ste pročitali u malo po malo, svaki put da ste dobili 0

576
00:48:53,540 --> 00:48:59,100
ćete slijediti lijevu granu, a onda svaki put kad pročitate u jednom

577
00:48:59,100 --> 00:49:02,100
ćeš slijediti pravu granu.

578
00:49:02,100 --> 00:49:07,570
A onda ćeš nastaviti sve dok ne pogoditi list

579
00:49:07,570 --> 00:49:11,550
jer su listovi će biti na kraju grane.

580
00:49:11,550 --> 00:49:16,870
Kako možemo reći da li smo hit list ili ne?

581
00:49:19,800 --> 00:49:21,690
Mi to rekao prije.

582
00:49:21,690 --> 00:49:24,040
[Student] Ako pokazivači su NULL. >> Da.

583
00:49:24,040 --> 00:49:32,220
Možemo reći ako smo pogodak list ako upućuje na obje lijeve i desne stabala NULL.

584
00:49:32,220 --> 00:49:34,110
Savršeno.

585
00:49:34,110 --> 00:49:40,320
Znamo da želimo pročitati u malo po malo u naš Huff datoteku.

586
00:49:43,870 --> 00:49:51,220
Kao što smo vidjeli prije u dump.c, ono što su učinili oni pročitati u malo po malo u Huff datoteku

587
00:49:51,220 --> 00:49:54,560
i samo ispisati ono što ti bitovi bili.

588
00:49:54,560 --> 00:49:58,430
Nećemo se radi. Idemo da se radi nešto što je malo složeniji.

589
00:49:58,430 --> 00:50:03,620
No, ono što možemo učiniti je da možemo uzeti da je malo koda koji glasi na na malo.

590
00:50:03,620 --> 00:50:10,250
Ovdje imamo cijeli zalogaj predstavlja trenutno malo da smo na.

591
00:50:10,250 --> 00:50:15,520
Ovo brine Ponavljanje svih bitova u datoteci dok ne pogoditi kraj datoteke.

592
00:50:15,520 --> 00:50:21,270
Na temelju toga, onda ćeš htjeti imati nekakav iteratora

593
00:50:21,270 --> 00:50:26,760
proći svoje stablo.

594
00:50:26,760 --> 00:50:31,460
I onda na temelju li malo je 0 ili 1,

595
00:50:31,460 --> 00:50:36,920
idete da želite ili premjestiti taj iteratora na lijevoj ili ga premjestiti na desno

596
00:50:36,920 --> 00:50:44,080
sve dok ne pogoditi list, pa sve do tog čvora koji ste na

597
00:50:44,080 --> 00:50:48,260
ne ukazuju na bilo više čvorova.

598
00:50:48,260 --> 00:50:54,300
Zašto možemo to učiniti s Huffman datoteku, ali ne Morse koda?

599
00:50:54,300 --> 00:50:56,610
Jer u Morse kodu postoji malo dvosmislenosti.

600
00:50:56,610 --> 00:51:04,440
Mogli bi biti kao što je, oh čekati, mi smo hit pismo na putu, pa možda je to naš pismo,

601
00:51:04,440 --> 00:51:08,150
a ako smo nastavili samo malo duže, onda bismo pogodio jedno pismo.

602
00:51:08,150 --> 00:51:13,110
No, to se neće dogoditi u Huffman encoding,

603
00:51:13,110 --> 00:51:17,540
tako da možemo biti sigurni da je jedini način da ćemo pogoditi karakter

604
00:51:17,540 --> 00:51:23,480
je li te čvora lijevo i desno su djeca NULL.

605
00:51:28,280 --> 00:51:32,350
>> Konačno, želimo osloboditi sve naše pamćenje.

606
00:51:32,350 --> 00:51:37,420
Želimo i zatvoriti Huff datoteka koje smo bave

607
00:51:37,420 --> 00:51:41,940
kao i uklanjanje svih stabala u našoj šumi.

608
00:51:41,940 --> 00:51:46,470
Na temelju vašeg provedbi, vjerojatno idete da želite nazvati uklanjanje šuma

609
00:51:46,470 --> 00:51:49,780
umjesto zapravo prolazi kroz sve stabala sebe.

610
00:51:49,780 --> 00:51:53,430
Ali, ako ste napravili bilo kakve privremene stabala, da ćete želite osloboditi toga.

611
00:51:53,430 --> 00:51:59,060
Znate svoj kôd najbolje, tako da znate gdje ste dodjele memorije.

612
00:51:59,060 --> 00:52:04,330
I tako, ako idete u, početi čak i kontrolu F'ing za malloc,

613
00:52:04,330 --> 00:52:08,330
vidim kad god malloc i pazeći da oslobodi sve koji

614
00:52:08,330 --> 00:52:10,190
ali onda samo prolazi kroz kodu,

615
00:52:10,190 --> 00:52:14,260
razumijevanje gdje ste možda dodjeljuje memoriju.

616
00:52:14,260 --> 00:52:21,340
Obično se samo može reći: "Na kraju datoteku Samo ću ukloniti šumu na mom šumi"

617
00:52:21,340 --> 00:52:23,850
tako da u osnovi jasno da sjećanje, bez da

618
00:52:23,850 --> 00:52:28,310
"I onda ja idem zatvoriti datoteku, a zatim moj program će se zatvoriti."

619
00:52:28,310 --> 00:52:33,810
No, je li to jedini put da je vaš program zatvara?

620
00:52:33,810 --> 00:52:37,880
Ne, jer ponekad možda bio pogreška što se dogodilo.

621
00:52:37,880 --> 00:52:42,080
Možda nismo mogli otvoriti datoteku ili nismo mogli napraviti još jedan stablo

622
00:52:42,080 --> 00:52:49,340
ili neka vrsta pogreške se dogodilo u procesu dodjela memorije i tako se vratio NULL.

623
00:52:49,340 --> 00:52:56,710
Pogreška se dogodilo, a onda smo se vratili i prestati.

624
00:52:56,710 --> 00:53:02,040
Dakle želite biti sigurni da bilo moguće vrijeme da vaš program može zatvoriti,

625
00:53:02,040 --> 00:53:06,980
Želite li osloboditi sve svoje memorije tamo.

626
00:53:06,980 --> 00:53:13,370
To nije samo će biti na samom kraju glavne funkcije koju prestati svoj kôd.

627
00:53:13,370 --> 00:53:20,780
Želite li pogledati natrag u svakom slučaju da je vaš broj potencijalno može vratiti prijevremeno

628
00:53:20,780 --> 00:53:25,070
i onda bez obzira memorije smisla.

629
00:53:25,070 --> 00:53:30,830
Recimo da je pozvao da šumu i da se vratio lažna.

630
00:53:30,830 --> 00:53:34,230
Onda ti vjerojatno neće trebati ukloniti šumu

631
00:53:34,230 --> 00:53:37,080
jer nemate šumu još.

632
00:53:37,080 --> 00:53:42,130
No, u svakom trenutku u kodu gdje se može vratiti prijevremeno

633
00:53:42,130 --> 00:53:46,160
želite da biste bili sigurni da ćete osloboditi eventualne memorije.

634
00:53:46,160 --> 00:53:50,020
>> Dakle, kada imamo posla s oslobađanjem memorije i imaju potencijalne curenja,

635
00:53:50,020 --> 00:53:55,440
želimo ne samo koristiti naše presudu i našu logiku

636
00:53:55,440 --> 00:54:01,850
ali također koristiti Valgrind kako bi se utvrdilo da li smo oslobođeni svih naših memorije ispravno ili ne.

637
00:54:01,850 --> 00:54:09,460
Možete pokrenuti Valgrind na lisnato i onda morate također ga proći

638
00:54:09,460 --> 00:54:14,020
Pravo broj naredbenog retka argumente za Valgrind.

639
00:54:14,020 --> 00:54:18,100
Možete pokrenuti, ali izlaz je malo zagonetan.

640
00:54:18,100 --> 00:54:21,630
Dobili smo malo koristi za njega Speller, ali mi još uvijek treba malo više pomoći,

641
00:54:21,630 --> 00:54:26,450
pa onda to radi s još nekoliko zastava poput curenja provjerite = puni,

642
00:54:26,450 --> 00:54:32,040
da vjerojatno će nam dati neke više korisnih izlaz na Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Zatim još jedan koristan savjet kad ste debugging je razl naredbu.

644
00:54:39,040 --> 00:54:48,520
Možete pristupiti osoblja provedbu Huff, pokrenuti da na tekstualnu datoteku,

645
00:54:48,520 --> 00:54:55,400
, a zatim ga reproducirati na binarnu datoteku, binarna datoteka Huff, biti specifičan.

646
00:54:55,400 --> 00:54:59,440
Onda ako pokrenuti vlastiti napuhati na taj binarnu datoteku,

647
00:54:59,440 --> 00:55:03,950
onda je idealno, vaš outputted tekstualna datoteka će biti identičan

648
00:55:03,950 --> 00:55:08,200
na prvobitni koju je donio u.

649
00:55:08,200 --> 00:55:15,150
Evo ja sam koristeći hth.txt kao primjer, a to je jedan govorio o vašem spec..

650
00:55:15,150 --> 00:55:21,040
To je doslovno samo HTH i onda newline.

651
00:55:21,040 --> 00:55:30,970
Ali definitivno slobodno i sigurno se potiče da koriste duže primjere

652
00:55:30,970 --> 00:55:32,620
za tekstualnoj datoteci.

653
00:55:32,620 --> 00:55:38,110
>> Možete čak i uzeti pucao na možda sažimanje i onda decompressing

654
00:55:38,110 --> 00:55:41,600
neke od datoteka koje se koriste u Speller poput rata i mira

655
00:55:41,600 --> 00:55:46,710
ili Jane Austen ili nešto slično - da bi se vrsta cool - ili Austin Powers,

656
00:55:46,710 --> 00:55:51,880
vrste koje se bave većim datotekama, jer mi ne bi došli do njega

657
00:55:51,880 --> 00:55:55,590
ako smo koristili sljedeću alat ovdje, ls-l.

658
00:55:55,590 --> 00:56:01,150
Mi smo navikli na LS, koji je u osnovi navodi sve sadržaje u našoj trenutnoj imenik.

659
00:56:01,150 --> 00:56:07,860
Dodavanje u zastave-l zapravo prikazuje veličinu tih datoteka.

660
00:56:07,860 --> 00:56:12,690
Ako idete kroz pset spec., to je zapravo vodi vas kroz stvaranje binarnu datoteku,

661
00:56:12,690 --> 00:56:16,590
da ga huffing, i vidjet ćete da za vrlo male datoteke

662
00:56:16,590 --> 00:56:23,910
Prostor trošak ga sažimanje i prevodio sve te informacije

663
00:56:23,910 --> 00:56:26,980
od svih frekvencija i stvari kao što je to nadilazi stvarni korist

664
00:56:26,980 --> 00:56:30,000
sažimanje datoteke na prvom mjestu.

665
00:56:30,000 --> 00:56:37,450
Ali ako ga pokrenuti na nekim duže tekstualne datoteke, onda ste mogli vidjeti da počnete da biste dobili neke koristi

666
00:56:37,450 --> 00:56:40,930
u sažimanje te datoteke.

667
00:56:40,930 --> 00:56:46,210
>> I onda na kraju, mi imamo stari pajdaš gdb, koji definitivno će doći u ruci previše.

668
00:56:48,360 --> 00:56:55,320
>> Imamo li kakvih pitanja o Huff stabala ili proces možda izrade stabla

669
00:56:55,320 --> 00:56:58,590
ili sva ostala pitanja na Huff'n lisnato?

670
00:57:00,680 --> 00:57:02,570
Ok. Ja ću ostati oko za malo.

671
00:57:02,570 --> 00:57:06,570
>> Hvala, svima. To je bio Walkthrough šest. I sretno.

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