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 - 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
>> Pozdravljeni, vsi, in dobrodošli potopis 6: Huff'n dim.

5
00:00:12,180 --> 00:00:17,440
V Puff Huff'n kar počnemo se bo ukvarja z datoteko Huffman stisnjenega

6
00:00:17,440 --> 00:00:20,740
in ga nato puhala nazaj, tako da simbolne,

7
00:00:20,740 --> 00:00:25,810
tako da bomo lahko prevesti iz 0s in 1s, da si nam pošilja

8
00:00:25,810 --> 00:00:30,660
in ga spremeniti nazaj v izvirno besedilo.

9
00:00:30,660 --> 00:00:34,360
Pset 6 se bo zelo kul, ker boste videli nekaj orodij

10
00:00:34,360 --> 00:00:41,730
, ki ste jih uporabili v pset 4 in 5 pset in vrsta jih združile v 1 zelo čeden koncept

11
00:00:41,730 --> 00:00:43,830
Ko pomislim na to.

12
00:00:43,830 --> 00:00:50,110
>> Prav tako verjetno, pset 4 in 5 sta najbolj zahtevna psets ki smo jih imeli v ponudbi.

13
00:00:50,110 --> 00:00:53,950
Torej od zdaj imamo to za več pset 1 v C-ju

14
00:00:53,950 --> 00:00:56,480
in nato po tem, da smo na spletnem programiranju.

15
00:00:56,480 --> 00:01:02,310
Torej sami čestitam za pridobivanje več najtežjih grba v CS50.

16
00:01:03,630 --> 00:01:09,760
>> Gremo naprej, za puff Huff'n, naše orodje za to pset se bodo Huffman drevesa,

17
00:01:09,760 --> 00:01:14,700
Tako razumevanje, ne samo, kako dvojiška drevesa delo, ampak tudi posebej Huffman drevesa,

18
00:01:14,700 --> 00:01:16,240
kako si izdelani ti.

19
00:01:16,240 --> 00:01:20,210
In potem bomo imeli veliko kode distribucije v tem pset,

20
00:01:20,210 --> 00:01:22,480
in bomo prišli pogledat, ki dejansko nekaj kode

21
00:01:22,480 --> 00:01:24,670
morda ne bomo mogli v celoti razumejo še,

22
00:01:24,670 --> 00:01:30,080
in tako bodo tisti, se je C slik., nato pa njihovih spremljevalcev h datoteke.

23
00:01:30,080 --> 00:01:34,300
nam bo dala dovolj razumevanja, da moramo tako, da vemo, kako te funkcije delujejo

24
00:01:34,300 --> 00:01:38,100
ali vsaj tisto, kar naj bi storil - njihovi vhodi in izhodi -

25
00:01:38,100 --> 00:01:40,760
tudi če ne vemo, kaj se dogaja v črni škatli

26
00:01:40,760 --> 00:01:44,090
ali ne razumejo, kaj se dogaja v črni škatli znotraj.

27
00:01:44,090 --> 00:01:49,400
In potem na koncu, kot ponavadi, smo se ukvarjajo z novimi podatkovnih struktur,

28
00:01:49,400 --> 00:01:51,840
Posebne vrste vozlišč, ki opozarjajo na nekatere stvari,

29
00:01:51,840 --> 00:01:56,080
in tako sem ob svinčnik in papir ne samo za proces oblikovanja

30
00:01:56,080 --> 00:01:58,470
in ko ste poskuša ugotoviti, kako bi morala delovati pset

31
00:01:58,470 --> 00:02:00,520
ampak tudi med razhroščevanje.

32
00:02:00,520 --> 00:02:06,140
Lahko imaš GDB poleg vaše pero in papir, medtem ko ste vzeli dol, kaj so vrednote,

33
00:02:06,140 --> 00:02:09,320
če vaše puščice obrnjene, in take stvari.

34
00:02:09,320 --> 00:02:13,720
>> Najprej si oglejmo dreves Huffman.

35
00:02:13,720 --> 00:02:19,600
Huffman drevesa so dvojiška drevesa, kar pomeni, da je vsako vozlišče ima le 2 otroka.

36
00:02:19,600 --> 00:02:24,870
V dreves Huffman značilnost je, da so najpogostejše vrednosti

37
00:02:24,870 --> 00:02:27,140
predstavljajo čim manj bitov.

38
00:02:27,140 --> 00:02:32,690
Videli smo v predavalnicah primerov Morse kode, ki je nekakšno konsolidiranih nekatere črke.

39
00:02:32,690 --> 00:02:38,030
Če ste poskušali prevesti A ali E, na primer,

40
00:02:38,030 --> 00:02:43,940
ste prevajanje, ki se pogosto, tako da namesto ob uporabi celoten sklop bitov

41
00:02:43,940 --> 00:02:48,640
dodeli za to običajno vrsto podatkov, ko jo stisnemo do manj,

42
00:02:48,640 --> 00:02:53,730
in potem te črke, ki jih zastopa, redkeje zastopane z več bitov

43
00:02:53,730 --> 00:02:59,840
ker si lahko privoščijo, da ko odtehta frekvenc, ki te črke na zaslonu.

44
00:02:59,840 --> 00:03:03,020
Imamo isto idejo tukaj na drevesih Huffman

45
00:03:03,020 --> 00:03:12,360
kjer smo se kar verige, vrste poti priti do nekaterih znakov.

46
00:03:12,360 --> 00:03:14,470
In potem so znaki, ki imajo največjo frekvenco

47
00:03:14,470 --> 00:03:17,940
se bodo zastopane s čim manj bitov.

48
00:03:17,940 --> 00:03:22,020
>> Tako, da si zgradi drevo Huffman

49
00:03:22,020 --> 00:03:27,430
je z dajanjem vseh znakov, ki se pojavljajo v besedilu

50
00:03:27,430 --> 00:03:30,630
in pogostost izračuna, kolikokrat se pojavijo.

51
00:03:30,630 --> 00:03:33,880
To je lahko bodisi število, kolikokrat ti črki sta

52
00:03:33,880 --> 00:03:40,270
ali morda odstotek od vseh likov, koliko vsak od pojavi.

53
00:03:40,270 --> 00:03:44,270
In kaj morate storiti, je, ko imaš vso to zarisano,

54
00:03:44,270 --> 00:03:49,060
potem poglej za 2 najnižjih frekvenc in potem se jim pridružijo kot bratje in sestre

55
00:03:49,060 --> 00:03:55,660
če pa starši vozlišče ima frekvenco, ki je vsota njegovih 2 otroka.

56
00:03:55,660 --> 00:04:00,870
In potem pravijo, da je po dogovoru levo vozlišče,

57
00:04:00,870 --> 00:04:03,770
sledite ki jih po 0 podružnico,

58
00:04:03,770 --> 00:04:08,140
in potem skrajno desno vozlišče je 1 podružnica.

59
00:04:08,140 --> 00:04:16,040
Kot smo videli v Morsejevi kodi, ena kavelj je, da če bi imeli samo piska in pisk

60
00:04:16,040 --> 00:04:18,120
je bil dvoumen.

61
00:04:18,120 --> 00:04:22,430
To bi lahko bil bodisi 1 črka ali pa bi se zaporedje 2 črk.

62
00:04:22,430 --> 00:04:27,790
In kaj Huffman drevesa pa je zato, ker po naravi znakov

63
00:04:27,790 --> 00:04:34,140
ali naši končni dejanska znakov kot zadnjega vozlišča na veji -

64
00:04:34,140 --> 00:04:39,300
smo se nanašajo na takšne, kot so listi - na podlagi, da ne more biti vse nejasnosti

65
00:04:39,300 --> 00:04:45,160
glede katerih črka, ki jo poskušate kodiranje s serijo bitov

66
00:04:45,160 --> 00:04:50,670
ker nikjer po bitov, ki predstavljajo 1 črko

67
00:04:50,670 --> 00:04:55,960
boste naleteli na še eno celo pismo, in da ne bo zmede obstaja.

68
00:04:55,960 --> 00:04:58,430
Ampak bomo šli v primerih, da lahko fantje videli, da dejansko

69
00:04:58,430 --> 00:05:02,120
namesto da bi nas samo povedal, da je to res.

70
00:05:02,120 --> 00:05:06,390
>> Oglejmo si preprost primer drevesa Huffman.

71
00:05:06,390 --> 00:05:09,380
Imam niz tukaj, ki je 12 znakov.

72
00:05:09,380 --> 00:05:14,010
Imam 4 Ker 6 BS in 2-jev.

73
00:05:14,010 --> 00:05:17,270
Moj prvi korak je, da računajo.

74
00:05:17,270 --> 00:05:20,760
Kolikokrat se pojavijo? Zdi se 4-krat v nizu.

75
00:05:20,760 --> 00:05:25,060
B se zdi, 6-krat in C se pojavi 2 krat.

76
00:05:25,060 --> 00:05:28,970
Seveda bom rekel, da sem z B najpogosteje

77
00:05:28,970 --> 00:05:35,970
zato želim, da zastopa B z najmanjšim številom bitov, najmanj pa število 0s in 1s.

78
00:05:35,970 --> 00:05:42,600
In potem sem tudi dogaja, da pričakujejo, C in zahtevajo največ znesek 0s in 1s, kot dobro.

79
00:05:42,600 --> 00:05:48,550
Prvo, kar sem storil tu sem jih dali v naraščajočem vrstnem redu glede na frekvence.

80
00:05:48,550 --> 00:05:52,710
Vidimo, da je C, in tistih, ki so naša 2 Najnižje frekvence.

81
00:05:52,710 --> 00:06:00,290
Ustvarjamo nadrejeno vozlišče, in da staršev vozlišče nima pismo, povezane z njo,

82
00:06:00,290 --> 00:06:05,070
vendar pa ima frekvenco, ki je vsota.

83
00:06:05,070 --> 00:06:08,780
Vsota postane 2 + 4, ki je 6.

84
00:06:08,780 --> 00:06:10,800
Nato sledimo levo vejo.

85
00:06:10,800 --> 00:06:14,970
Če smo bili v tistem 6 vozlišča, potem bi morali slediti 0 priti do C

86
00:06:14,970 --> 00:06:17,450
in nato 1 priti do A.

87
00:06:17,450 --> 00:06:20,300
Torej, zdaj imamo 2 vozlišč.

88
00:06:20,300 --> 00:06:23,920
Imamo vrednost 6 in potem imamo tudi eno vozlišče z vrednostjo 6.

89
00:06:23,920 --> 00:06:28,550
In tako so 2 niso le 2 najnižja pa tudi samo 2, ki so odšli,

90
00:06:28,550 --> 00:06:33,820
zato smo se pridružili tistim, ki jih drugi od staršev, pri čemer je vsota 12.

91
00:06:33,820 --> 00:06:36,300
Torej, tukaj imamo Huffman drevo

92
00:06:36,300 --> 00:06:40,020
če bi dobili na B, bi to samo se bit 1

93
00:06:40,020 --> 00:06:45,430
in potem priti do ne bi imeli 01 C in nato ob 00.

94
00:06:45,430 --> 00:06:51,300
Torej, tukaj vidimo, da smo v bistvu kar te znakov z 1 ali 2 bitov

95
00:06:51,300 --> 00:06:55,160
kjer je B, kot je napovedano, ima najmanj.

96
00:06:55,160 --> 00:07:01,730
In potem smo se pričakuje, C so najbolj, ampak ker je tako majhno drevo Huffman,

97
00:07:01,730 --> 00:07:06,020
potem je tudi zastopnik 2 bitov za razliko nekje v sredini.

98
00:07:07,820 --> 00:07:11,070
>> Samo, da gredo na drugo preprost primer drevesa Huffman,

99
00:07:11,070 --> 00:07:19,570
da imate niz "Hello".

100
00:07:19,570 --> 00:07:25,360
Kaj morate storiti, je prvo, kar bi rekel, koliko krat se pojavi H v to?

101
00:07:25,360 --> 00:07:34,200
H pojavi enkrat in potem se pojavi, ko e in potem jaz ne pojavljajo dvakrat

102
00:07:34,200 --> 00:07:36,580
in o pojavlja enkrat.

103
00:07:36,580 --> 00:07:44,310
In tako potem pričakujemo, da bo pismo, ki naj bi ga najmanjšim številom bitov?

104
00:07:44,310 --> 00:07:47,450
[Študent] l. >> L. Ja. l je prav.

105
00:07:47,450 --> 00:07:50,730
Pričakujemo, da sem, da je zastopana z najmanjšim številom bitov

106
00:07:50,730 --> 00:07:55,890
ker sem se največ uporablja v nizu "Hello".

107
00:07:55,890 --> 00:08:04,280
Kaj sem storil sedaj se črpa iz teh vozlišč.

108
00:08:04,280 --> 00:08:15,580
Imam 1, ki je H in nato še 1, ki je e, nato pa je 1, ki je o -

109
00:08:15,580 --> 00:08:23,410
zdaj sem jih postavi v redu - in potem 2, ki je l.

110
00:08:23,410 --> 00:08:32,799
Potem sem rekel, da sem tako graditi drevo Huffman je najti 2 vozlišča z manj frekvencah

111
00:08:32,799 --> 00:08:38,010
in da jim bratje in sestre, ki jih ustvarja nadrejeno vozlišče.

112
00:08:38,010 --> 00:08:41,850
Tukaj imamo 3 vozlišč z najnižjo frekvenco. Oni so vsi 1.

113
00:08:41,850 --> 00:08:50,620
Torej, tukaj smo se odločili, katero bomo najprej povezati.

114
00:08:50,620 --> 00:08:54,850
Recimo, da izberejo H in e.

115
00:08:54,850 --> 00:09:01,150
Vsota 1 + 1 je 2, vendar to vozlišče nima pismo z njo povezana.

116
00:09:01,150 --> 00:09:04,440
Prav tako ima vrednost.

117
00:09:04,440 --> 00:09:10,950
Zdaj gledamo na naslednjih 2 najnižjih frekvenc.

118
00:09:10,950 --> 00:09:15,590
To je 2 in 1. To bi lahko bil eden od tistih, 2, vendar bom, da izberejo to.

119
00:09:15,590 --> 00:09:18,800
Vsota je 3.

120
00:09:18,800 --> 00:09:26,410
In potem končno, imam samo 2 levo, tako da potem postane 5.

121
00:09:26,410 --> 00:09:32,010
Potem pa sem, kot se pričakuje, če izpolnite kodiranje za to,

122
00:09:32,010 --> 00:09:37,480
1s vedno pravico, podružnice in 0s sta leva.

123
00:09:37,480 --> 00:09:45,880
Potem imamo l, ki jo predstavlja le 1 bit in nato Õ 2

124
00:09:45,880 --> 00:09:52,360
in potem e z 2 in nato H pade na 3 kose.

125
00:09:52,360 --> 00:09:59,750
Torej si lahko pošlje to sporočilo "Hello", namesto da dejansko uporabljate znake

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

127
00:10:02,760 --> 00:10:07,910
Vendar ne pozabite, da v več primerih smo imeli stike z našo frekvenco.

128
00:10:07,910 --> 00:10:11,900
Lahko bi bodisi pridružil h in o, 1. morda.

129
00:10:11,900 --> 00:10:15,730
Ali pa kasneje, ko smo imeli l zastopa 2

130
00:10:15,730 --> 00:10:19,410
kot tudi pridružil 1 2 zastopa, bi lahko povezan niti ena.

131
00:10:19,410 --> 00:10:23,630
>> In tako, ko pošljete 0s in 1s, ki dejansko ne zagotavlja

132
00:10:23,630 --> 00:10:27,090
da jo lahko prejemnik v celoti preberete sporočilo pravico off kij

133
00:10:27,090 --> 00:10:30,490
zato, ker ne bi vedeli, katere odločitev, ki ste jih naredili.

134
00:10:30,490 --> 00:10:34,920
Torej, ko imamo opravka s stiskanjem Huffman,

135
00:10:34,920 --> 00:10:40,090
Nekako moramo povedati prejemniku našega sporočila, kako smo se odločili -

136
00:10:40,090 --> 00:10:43,470
Morajo vedeti, kakšno dodatne informacije

137
00:10:43,470 --> 00:10:46,580
poleg sporočila stisnjen.

138
00:10:46,580 --> 00:10:51,490
Morajo razumeti, kaj drevo dejansko izgleda,

139
00:10:51,490 --> 00:10:55,450
kako dejansko so te odločitve.

140
00:10:55,450 --> 00:10:59,100
>> Tukaj smo samo delaš primere, ki se nanašajo na dejansko število,

141
00:10:59,100 --> 00:11:01,550
včasih pa lahko imate tudi drevo Huffman

142
00:11:01,550 --> 00:11:05,760
glede na frekvenco, pri kateri črki zdi se, da je popolnoma enak proces.

143
00:11:05,760 --> 00:11:09,090
Tukaj sem ga izrazil v zvezi z odstotki ali frakcij,

144
00:11:09,090 --> 00:11:11,290
in tako sem točno isto stvar.

145
00:11:11,290 --> 00:11:15,300
Se mi zdi 2 najnižja, ki jih povzamemo, naslednji 2 najnižja, ki jih povzamemo,

146
00:11:15,300 --> 00:11:19,390
dokler ne bom imel polno drevo.

147
00:11:19,390 --> 00:11:23,610
Čeprav smo lahko to storite tako ali tako, ko imamo opravka z odstotki,

148
00:11:23,610 --> 00:11:27,760
to pomeni, da smo tako stvari, ki se ukvarjajo z decimalk ali ne plava

149
00:11:27,760 --> 00:11:30,900
če razmišljate o podatkovnih strukturah glavo.

150
00:11:30,900 --> 00:11:32,540
Kaj vemo o plovci?

151
00:11:32,540 --> 00:11:35,180
Kaj je pogost problem, ko imamo opravka s plovci?

152
00:11:35,180 --> 00:11:38,600
[Študent] nenatančno aritmetično. >> Ja. Nenatančnost.

153
00:11:38,600 --> 00:11:43,760
Zaradi nenatančnosti plavajoče točke, za to pset, da poskrbimo, da

154
00:11:43,760 --> 00:11:49,450
da ne bomo izgubili nobene vrednosti, potem bomo dejansko dogaja, da se ukvarjajo s štetjem.

155
00:11:49,450 --> 00:11:54,880
Torej, če ste bili, da razmišljajo o vozlišča Huffman, če pogledaš nazaj v strukturi tukaj,

156
00:11:54,880 --> 00:12:01,740
če pogledaš na tiste zelene ima frekvenco povezano z njim

157
00:12:01,740 --> 00:12:08,760
kot tudi to kaže na vozlišče na njegovi levi, kot tudi vozlišče v njegovo pravico.

158
00:12:08,760 --> 00:12:13,970
In potem tisti rdeči pa tudi znak, povezane z njimi.

159
00:12:13,970 --> 00:12:18,900
Ne bomo narediti ločene tiste, za starše in nato končnih vozlišč,

160
00:12:18,900 --> 00:12:23,680
ki jo označujemo z listi, ampak bo samo še tiste vrednosti NULL.

161
00:12:23,680 --> 00:12:31,050
Za vsako vozlišče bomo imeli znak, simbol, da predstavlja vozlišče,

162
00:12:31,050 --> 00:12:40,490
nato frekvenco, kot tudi kazalec na njegovi levi otroka, kot tudi njegovo pravico otroka.

163
00:12:40,490 --> 00:12:45,680
Listi, ki so na samem dnu, bi tudi vozlišče napotke

164
00:12:45,680 --> 00:12:49,550
na svoji levi in ​​njihove pravice, ampak ker te vrednosti se ne kaže dejanskih vozlišč,

165
00:12:49,550 --> 00:12:53,970
Kaj bi njihova vrednost? >> [Študent] NULL. >> NULL. Točno tako.

166
00:12:53,970 --> 00:12:58,430
Tukaj je primer, kako lahko predstavlja frekvenco v plovci,

167
00:12:58,430 --> 00:13:02,130
ampak se bomo morali ukvarjati z njim s števil,

168
00:13:02,130 --> 00:13:06,780
tako da vse, kar sem storil, je spremeniti podatkovni tip tam.

169
00:13:06,780 --> 00:13:09,700
>> Gremo na bolj malo zapleteno primer.

170
00:13:09,700 --> 00:13:13,360
Toda zdaj, ko smo naredili preproste tiste, to je samo isti postopek.

171
00:13:13,360 --> 00:13:20,290
Boste našli 2 najnižje frekvence, povzamemo frekvenc

172
00:13:20,290 --> 00:13:22,450
in da je nova frekvenca vašega nadrejenega vozlišča,

173
00:13:22,450 --> 00:13:29,310
ki se potem kaže na njegovo levo z 0 vejo in pravice z 1 podružnice.

174
00:13:29,310 --> 00:13:34,200
Če imamo niz "To je cs50", potem pa preštejte, koliko krat je T omenjeno,

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

176
00:13:38,420 --> 00:13:42,010
Torej, kaj sem naredil tukaj, je z rdečimi vozlišč sem zasajene,

177
00:13:42,010 --> 00:13:48,530
Rekel sem, da bom imel te znake sčasoma na dnu mojega drevesa.

178
00:13:48,530 --> 00:13:51,740
Tisti, ki se bodo vsi listi.

179
00:13:51,740 --> 00:13:58,200
Torej, kaj sem naredil je, da sem jih razporejene po pogostosti v naraščajočem vrstnem redu,

180
00:13:58,200 --> 00:14:02,950
in to je pravzaprav način, da to stori pset koda

181
00:14:02,950 --> 00:14:07,550
je jo razvrsti po pogostnosti in nato po abecedi.

182
00:14:07,550 --> 00:14:13,870
Torej ima številke in šele nato po abecedi glede na frekvenco.

183
00:14:13,870 --> 00:14:18,520
Torej, kaj želim storiti, je, jaz bi našli 2 najnižja. To je 0 in 5.

184
00:14:18,520 --> 00:14:22,390
Jaz bi jih sešteje, in to je 2. Potem sem nadaljeval, je bil naslednji 2 najnižja.

185
00:14:22,390 --> 00:14:26,100
To sta dve 1s, nato pa so postali 2, kot dobro.

186
00:14:26,100 --> 00:14:31,570
Zdaj vem, da je moj naslednji korak se bo pridružil najnižjo številko,

187
00:14:31,570 --> 00:14:41,380
ki je T, 1 in nato izberete eno od vozlišč, ki ima 2 s pogostnostjo.

188
00:14:41,380 --> 00:14:44,560
Torej, tukaj imamo 3 možnosti.

189
00:14:44,560 --> 00:14:47,980
Kaj bom naredil za diapozitiv je samo vizualno preurediti za vas

190
00:14:47,980 --> 00:14:51,790
tako da lahko vidite, kako sem ga izgradnji.

191
00:14:51,790 --> 00:14:59,040
Kaj je koda in vaša distribucija koda je storil, bi se pridružili T 1

192
00:14:59,040 --> 00:15:01,410
z 0 in 5 vozlišče.

193
00:15:01,410 --> 00:15:05,060
Torej, da zneski do 3, nato pa bomo nadaljevali postopek.

194
00:15:05,060 --> 00:15:08,660
Cilj 2 in 2 zdaj so najnižje, tako da potem tisti znesek, do 4.

195
00:15:08,660 --> 00:15:12,560
Vsakdo po do sedaj? Ok.

196
00:15:12,560 --> 00:15:16,410
Potem, ko da imamo 3 in 3, ki jih je treba sešteti,

197
00:15:16,410 --> 00:15:21,650
zato še enkrat sem samo prehod, tako da lahko vidite vizualno, tako da ne preveč grdo.

198
00:15:21,650 --> 00:15:25,740
Potem imamo 6, nato pa naš končni korak je ta, da zdaj imamo samo 2 vozlišč

199
00:15:25,740 --> 00:15:30,440
povzamemo, da so bistva našega drevesa, kar je 10.

200
00:15:30,440 --> 00:15:34,100
In številka 10 je smiseln, saj vsako vozlišče predstavljeno,

201
00:15:34,100 --> 00:15:40,750
njihova vrednost, njihova pogostost število, je kolikokrat se je pojavil v nizu,

202
00:15:40,750 --> 00:15:46,350
in potem imamo 5 znakov v našem nizu, tako da ima smisel.

203
00:15:48,060 --> 00:15:52,320
Če si pa poglej kako bi se ga dejansko kodiranje,

204
00:15:52,320 --> 00:15:56,580
kot je bilo pričakovano, i in y, ki se pojavljajo najpogosteje

205
00:15:56,580 --> 00:16:01,350
so zastopane z najmanjšim številom bitov.

206
00:16:03,660 --> 00:16:05,660
>> Bodite previdni tukaj.

207
00:16:05,660 --> 00:16:09,780
V dreves Huffman primeru dejansko pomembno.

208
00:16:09,780 --> 00:16:13,670
Velika črka S se razlikuje od malimi črkami je.

209
00:16:13,670 --> 00:16:21,260
Če bi imeli "To je CS50" z velikimi črkami, potem male črke y bo prikazana samo dvakrat,

210
00:16:21,260 --> 00:16:27,120
bi bilo vozlišče z 2 kot svojo vrednost, potem pa velika črka S samo enkrat.

211
00:16:27,120 --> 00:16:33,440
Tako bo vaša drevesa spremeniti strukture, ker ste dejansko imajo dodatno krilo tukaj.

212
00:16:33,440 --> 00:16:36,900
Vendar bi vsota še vedno 10.

213
00:16:36,900 --> 00:16:39,570
To je tisto, kar smo dejansko dogaja, da se sklic checksum,

214
00:16:39,570 --> 00:16:44,060
dodajanje vseh pogledih.

215
00:16:46,010 --> 00:16:50,990
>> Zdaj, ko smo iz Huffman dreves, smo lahko potopite v Puff Huff'n je pset.

216
00:16:50,990 --> 00:16:52,900
Bomo začeli z delom vprašanj,

217
00:16:52,900 --> 00:16:57,990
in to se dogaja, da boste dobili navajeni, z binarnih dreves in kako deluje približno tako:

218
00:16:57,990 --> 00:17:03,230
risanje vozlišč, ustvarjanju lastne typedef struct za vozlišče,

219
00:17:03,230 --> 00:17:07,230
in videli, kako lahko vstavite v binarno drevo, tisti, ki je urejen,

220
00:17:07,230 --> 00:17:09,050
vozijo ga, in stvari, kot je ta.

221
00:17:09,050 --> 00:17:14,560
To znanje bo zagotovo vam pomaga, ko se potopite v delu Puff Huff'n

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

223
00:17:19,150 --> 00:17:26,329
V standardni izdaji pset, vaša naloga je izvajanje Puff,

224
00:17:26,329 --> 00:17:30,240
in v različici hacker vaša naloga je izvajanje Huff.

225
00:17:30,240 --> 00:17:38,490
Kaj Huff pa je potrebno besedilo in nato jo z drugimi besedami pomeni 0s in 1s,

226
00:17:38,490 --> 00:17:41,990
tako da je proces, ki smo to naredili zgoraj, kjer smo našteli frekvenc

227
00:17:41,990 --> 00:17:50,970
nato pa je drevo, nato pa je rekel: "Kako dobim T?"

228
00:17:50,970 --> 00:17:54,840
T predstavlja 100, take stvari,

229
00:17:54,840 --> 00:17:58,860
in potem bi Huff se besedilo, nato pa izhod, ki binarno.

230
00:17:58,860 --> 00:18:04,920
Pa tudi zato, ker vemo, da želimo, da bi naše prejemnika sporočila

231
00:18:04,920 --> 00:18:11,790
da ponovno natančno isto drevo, vključuje tudi podatke o pogostosti razlogov.

232
00:18:11,790 --> 00:18:17,980
Nato s Puff smo dobili binarno datoteko 0s in 1s

233
00:18:17,980 --> 00:18:21,740
in glede na to tudi podatke o frekvencah.

234
00:18:21,740 --> 00:18:26,740
Prevajamo vse tiste 0s in 1s nazaj v izvirno sporočilo, da je bil,

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

236
00:18:29,350 --> 00:18:36,450
Če delaš Standard Edition, vam ni treba izvajati Huff,

237
00:18:36,450 --> 00:18:39,290
tako, potem lahko preprosto uporabite kadrovske izvajanje Huff.

238
00:18:39,290 --> 00:18:42,080
Obstajajo navodila v določilu o tem, kako to storiti.

239
00:18:42,080 --> 00:18:48,780
Lahko zaženete zaposlenih izvajanje Huff o posameznem besedilno datoteko

240
00:18:48,780 --> 00:18:53,270
in nato uporabite, da izhod v vaš prispevek k Puff.

241
00:18:53,270 --> 00:18:59,330
>> Kot sem že omenil, imamo veliko kode distribucije za to.

242
00:18:59,330 --> 00:19:01,810
Jaz bom za začetek šel skozi to.

243
00:19:01,810 --> 00:19:04,400
Jaz grem, da preživijo večino časa na. H datoteke

244
00:19:04,400 --> 00:19:07,660
saj v datotekah. C, ker imamo. H

245
00:19:07,660 --> 00:19:11,650
in da nam daje s prototipi funkcij,

246
00:19:11,650 --> 00:19:15,520
ne bomo v celoti treba natančno razumeti -

247
00:19:15,520 --> 00:19:20,280
Če ne razumete, kaj se dogaja v datotekah. C, potem ne skrbi preveč,

248
00:19:20,280 --> 00:19:23,600
ampak definitivno poskusil, da si ogledate, saj lahko to daje nekaj namigov

249
00:19:23,600 --> 00:19:29,220
in to je koristno, da se privadite branje kodo drugih ljudi.

250
00:19:38,940 --> 00:19:48,270
>> Če pogledamo huffile.h, v komentarjih razglasi plast abstrakcije za Huffman kodiranimi datotekami.

251
00:19:48,270 --> 00:20:01,660
Če gremo, smo videli, da je največ 256 znakov, ki bi jih potrebovali kode za.

252
00:20:01,660 --> 00:20:05,480
To vključuje vse črke abecede - velikih in malih -

253
00:20:05,480 --> 00:20:08,250
in potem simboli in številke, itd

254
00:20:08,250 --> 00:20:11,930
Potem imamo tukaj magično številko je navedla Huffman označenih datoteko.

255
00:20:11,930 --> 00:20:15,890
V kodeksu Huffman, da boš imela določeno število čarobno

256
00:20:15,890 --> 00:20:18,560
povezano z glavo.

257
00:20:18,560 --> 00:20:21,110
To bi izgledal zgolj naključno magično številko,

258
00:20:21,110 --> 00:20:27,160
če pa dejansko prevesti v ASCII, nato pa je dejansko opredeljuje Huff.

259
00:20:27,160 --> 00:20:34,290
Tukaj imamo struct za Huffman kodirani datoteki.

260
00:20:34,290 --> 00:20:39,670
Tam je vse te značilnosti, povezane z datoteko Huff.

261
00:20:39,670 --> 00:20:47,080
Potem tukaj imamo glavo datoteke Huff, zato pravimo, da Huffeader

262
00:20:47,080 --> 00:20:50,810
namesto da bi dodali dodatno h, ker zveni nekako enako.

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

264
00:20:52,720 --> 00:20:57,790
Imamo magično število, povezano z njim.

265
00:20:57,790 --> 00:21:09,040
Če je dejanska slika Huff, da se bo število tam zgoraj, to čarobno 1.

266
00:21:09,040 --> 00:21:14,720
In potem bo dobil niz.

267
00:21:14,720 --> 00:21:18,750
Torej za vsak znak, ki je 256,

268
00:21:18,750 --> 00:21:24,760
da se bo seznam, kaj je pogostost teh simbolov so v datoteki Huff.

269
00:21:24,760 --> 00:21:28,090
In potem končno, imamo checksum za frekvencah,

270
00:21:28,090 --> 00:21:32,160
ki bi morala biti vsota teh frekvencah.

271
00:21:32,160 --> 00:21:36,520
Tako da je tisto, kar je Huffeader.

272
00:21:36,520 --> 00:21:44,600
Potem imamo nekaj funkcij, ki vrnejo naslednji bit v datoteki Huff

273
00:21:44,600 --> 00:21:52,580
kot piše malo jezen na datoteko, nato pa ta funkcija tukaj, hfclose,

274
00:21:52,580 --> 00:21:54,650
ki dejansko arhivira Huff.

275
00:21:54,650 --> 00:21:57,290
Pred tem smo imeli opravka z ravno prav fclose,

276
00:21:57,290 --> 00:22:01,190
ko pa imate datoteko Huff, namesto da bi jo fclosing

277
00:22:01,190 --> 00:22:06,080
kaj ste dejansko storili, je hfclose in ga hfopen.

278
00:22:06,080 --> 00:22:13,220
Tisti, ki so določene naloge do datotek Huff, da bomo v stiku s.

279
00:22:13,220 --> 00:22:19,230
Potem tukaj beremo v glavo, nato pa pisati glavo.

280
00:22:19,230 --> 00:22:25,700
>> Samo z branjem h datoteko. Bomo lahko nekako dobili občutek, kaj bi lahko bilo datoteka Huff,

281
00:22:25,700 --> 00:22:32,480
katere lastnosti ima, ne da bi se dejansko dogaja v huffile.c,

282
00:22:32,480 --> 00:22:36,750
ki bo, če bomo potopili, se bo malo bolj zapletena.

283
00:22:36,750 --> 00:22:41,270
Ima vse datoteke I / O obravnavamo kazalca.

284
00:22:41,270 --> 00:22:48,010
Tukaj vidimo, da ko smo klic hfread, na primer, je še vedno ukvarjajo z fread.

285
00:22:48,010 --> 00:22:53,050
Ne bomo znebili teh funkcij v celoti, vendar vam pošiljamo tistim, ki so poskrbeli

286
00:22:53,050 --> 00:22:59,760
znotraj datoteke Huff, namesto da delaš vse to mi sami.

287
00:22:59,760 --> 00:23:02,300
Lahko vas prosimo, da skandirati skozi to, če ste radovedni

288
00:23:02,300 --> 00:23:08,410
in pojdi in olupite plasti nazaj malo.

289
00:23:20,650 --> 00:23:24,060
>> Naslednja slika, da bomo gledati, je tree.h.

290
00:23:24,060 --> 00:23:30,210
Preden v Walkthrough vodili smo rekli, pričakujemo Huffman vozlišče

291
00:23:30,210 --> 00:23:32,960
in smo se typedef struct vozlišče.

292
00:23:32,960 --> 00:23:38,360
Pričakujemo, da ima simbol, se pogostost in nato 2 vozlišča zvezde.

293
00:23:38,360 --> 00:23:41,870
V tem primeru, kar počnemo, je to v bistvu enak

294
00:23:41,870 --> 00:23:46,880
razen namesto vozlišča bomo jim pravimo drevesa.

295
00:23:48,790 --> 00:23:56,760
Imamo funkcijo, ko pokličeš, da je drevo vrne vam drevo kazalec.

296
00:23:56,760 --> 00:24:03,450
Nazaj na speller, ko ste bili kar novo vozlišče

297
00:24:03,450 --> 00:24:11,410
si rekel vozlišče * Nova beseda = malloc (sizeof) in take stvari.

298
00:24:11,410 --> 00:24:17,510
V bistvu, mktree se bo obravnava za vas.

299
00:24:17,510 --> 00:24:20,990
Podobno, če želite odstraniti drevo,

300
00:24:20,990 --> 00:24:24,810
tako da je v bistvu sprostitev drevo, ko ste storili z njim,

301
00:24:24,810 --> 00:24:33,790
Namesto izrecno poziva brezplačno, da ste dejansko šele tekoč, da uporabite funkcijo rmtree

302
00:24:33,790 --> 00:24:40,360
če se boste peljali v kazalec na tisto drevo, nato pa se bo tree.c poskrbel za to za vas.

303
00:24:40,360 --> 00:24:42,490
>> Upamo, da bomo v tree.c.

304
00:24:42,490 --> 00:24:47,240
Pričakujemo, da bodo iste funkcije, razen za ogled izvajanja, kot tudi.

305
00:24:47,240 --> 00:24:57,720
Kot smo pričakovali, ko ste klic mktree je mallocs velikost drevesa v kazalcem

306
00:24:57,720 --> 00:25:03,190
inicializira vse vrednosti na NULL vrednosti, tako da 0s ali ničel,

307
00:25:03,190 --> 00:25:08,280
in nato vrne kazalec na tisto drevo, ki ste jo pravkar malloc'd za vas.

308
00:25:08,280 --> 00:25:13,340
Tukaj, ko pokličete odstraniti drevo najprej poskrbi, da ne boš dvojno osvoboditev.

309
00:25:13,340 --> 00:25:18,320
To zagotavlja, da ste dejansko imajo drevo, ki ga želite odstraniti.

310
00:25:18,320 --> 00:25:23,330
Tukaj ker drevo tudi svoje otroke,

311
00:25:23,330 --> 00:25:29,560
kaj pa je to rekurzivno zahteva odstranitev drevesa na levem vozlišču drevesa

312
00:25:29,560 --> 00:25:31,650
kot pravi vozlišča.

313
00:25:31,650 --> 00:25:37,790
Preden se osvobaja od staršev, je potrebno sprostiti otroke, kot tudi.

314
00:25:37,790 --> 00:25:42,770
Matično tudi zamenljiv z root.

315
00:25:42,770 --> 00:25:46,500
Prvo od staršev, tako kot pra-pra-pra-pradedek

316
00:25:46,500 --> 00:25:52,130
ali babica drevo, moramo najprej osvoboditi določitvi stopnje najprej.

317
00:25:52,130 --> 00:25:58,490
Torej prečkala do dna, brez tistih, potem pa pridi nazaj gor, brez tistih, itd

318
00:26:00,400 --> 00:26:02,210
Torej, to je drevo.

319
00:26:02,210 --> 00:26:04,240
>> Zdaj gledamo na gozd.

320
00:26:04,240 --> 00:26:09,860
Gozd je, če jih postavite vse vaše dreves Huffman.

321
00:26:09,860 --> 00:26:12,910
To je rekel, da bomo imeli nekaj pozval plot

322
00:26:12,910 --> 00:26:22,320
, ki vsebuje kazalec na drevo, kot tudi kazalec na parceli, imenovano drugo.

323
00:26:22,320 --> 00:26:28,480
Kaj struktura pa takšno videti?

324
00:26:29,870 --> 00:26:32,490
Nekako piše tam.

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

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

327
00:26:39,170 --> 00:26:44,590
Vidimo, da je, ko imamo parcelo je kot povezan seznam parcel.

328
00:26:44,590 --> 00:26:53,020
Gozdov je opredeljena kot povezan seznam parcel,

329
00:26:53,020 --> 00:26:58,100
in tako je struktura gozda smo le, da bo imel kazalec na prvo parcelo

330
00:26:58,100 --> 00:27:02,740
in da je parcela ima drevo v njej ali ne kaže na drevesu

331
00:27:02,740 --> 00:27:06,190
in nato opozarja na naslednje parcele, tako naprej in tako naprej.

332
00:27:06,190 --> 00:27:11,100
Če želite gozd pravimo mkforest.

333
00:27:11,100 --> 00:27:14,930
Potem imamo nekaj zelo uporabnih funkcij tukaj.

334
00:27:14,930 --> 00:27:23,240
Imamo izbrati, če se boste peljali v gozd in se nato vrne vrednost je drevo *

335
00:27:23,240 --> 00:27:25,210
kazalec na drevo.

336
00:27:25,210 --> 00:27:29,370
Kaj izbor bo naredil, je, da bo šel v gozd, da ste kar kaže na

337
00:27:29,370 --> 00:27:35,240
nato odstranite drevo z najnižjo frekvenco od tega gozda

338
00:27:35,240 --> 00:27:38,330
in potem vam kazalec na drevesu.

339
00:27:38,330 --> 00:27:43,030
Ko kličete kramp, drevo ne bo, v gozdu več,

340
00:27:43,030 --> 00:27:48,550
vendar je donosnost vrednost je kazalec na drevesu.

341
00:27:48,550 --> 00:27:50,730
Potem imate napravo.

342
00:27:50,730 --> 00:27:57,420
Pod pogojem, da se boste peljali v kazalec na drevo, ki ima non-0 frekvenco,

343
00:27:57,420 --> 00:28:04,040
kaj bo naredil obrat je bo v gozd, da drevo, in rastlin, da drevo v notranjosti gozda.

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

345
00:28:06,370 --> 00:28:11,480
Podobno odstraniti drevo, ki v bistvu osvobodite vseh naših dreves za nas,

346
00:28:11,480 --> 00:28:16,600
odstrani gozd bo osvobodil vse vsebuje ta gozd.

347
00:28:16,600 --> 00:28:24,890
>> Če se ozremo v forest.c, bomo pričakujemo, da bo vsaj 1 rmtree ukaz tam,

348
00:28:24,890 --> 00:28:30,090
ker prostega pomnilnika v gozdu, če ima gozd drevesa v njem,

349
00:28:30,090 --> 00:28:32,930
nato pa na koncu boste morali odstraniti drevesa, preveč.

350
00:28:32,930 --> 00:28:41,020
Če se ozremo v forest.c, imamo mkforest, ki je, kot smo pričakovali.

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

352
00:28:42,890 --> 00:28:51,740
Mi inicializirati 1. parcelo v gozdu za nično, ker je prazen na začetku,

353
00:28:51,740 --> 00:29:05,940
potem vidimo, kramp, ki vrne drevo z najmanjšo težo, kar je najnižja pogostost,

354
00:29:05,940 --> 00:29:13,560
in potem znebil tega določenega vozlišča, ki kaže na to drevo in naslednji 1,

355
00:29:13,560 --> 00:29:16,760
zato meni, da je iz povezanega seznama gozda.

356
00:29:16,760 --> 00:29:24,510
In tukaj imamo tovarno, ki dodaja drevesa v povezanem seznamu.

357
00:29:24,510 --> 00:29:29,960
Kaj gozd pa je lepo ohranja razporejene za nas.

358
00:29:29,960 --> 00:29:37,910
In potem končno, imamo rmforest in, kot se pričakuje, imamo rmtree pozval tam.

359
00:29:46,650 --> 00:29:55,440
>> Če pogledamo na distribucijskem kodo tako daleč, huffile.c je verjetno daleč najtežje razumeti,

360
00:29:55,440 --> 00:29:59,990
ker druge datoteke, sami so bili zelo enostavno slediti.

361
00:29:59,990 --> 00:30:03,090
Z našim znanjem in povezanih kazalcev seznamov in take,

362
00:30:03,090 --> 00:30:04,860
smo lahko spremljali zelo dobro.

363
00:30:04,860 --> 00:30:10,500
Toda vse, kar potrebujete, da bo res poskrbeti, da bomo popolnoma razumeli je H datotek.

364
00:30:10,500 --> 00:30:15,840
ker je treba kliče tiste funkcije, ki se ukvarjajo s temi izračunani vrednosti

365
00:30:15,840 --> 00:30:20,590
zato poskrbite, da boste popolnoma razumeli, kakšne ukrepe bo treba opraviti

366
00:30:20,590 --> 00:30:24,290
ko pokličete eno od teh funkcij.

367
00:30:24,290 --> 00:30:33,020
Ampak dejansko razumevanje znotraj njega ni ravno potrebno, ker smo jih. H datotek.

368
00:30:35,170 --> 00:30:39,490
Imamo še 2 datotek ostane v našem distribucijskem kodo.

369
00:30:39,490 --> 00:30:41,640
>> Oglejmo si smetišču.

370
00:30:41,640 --> 00:30:47,230
Smetišče s svojim komentarjem sem vzame Huffman stisnjen datoteko

371
00:30:47,230 --> 00:30:55,580
in nato prevaja in stresa vse njene vsebine ven.

372
00:31:01,010 --> 00:31:04,260
Tukaj vidimo, da kliče hfopen.

373
00:31:04,260 --> 00:31:10,770
To je nekako zrcali v datoteko * vhodne = fopen,

374
00:31:10,770 --> 00:31:13,500
in potem preide v vednost.

375
00:31:13,500 --> 00:31:18,240
To je skoraj enaki, razen namesto datoteke * ti, ki poteka v Huffile;

376
00:31:18,240 --> 00:31:22,030
namesto fopen ste potujejo hfopen.

377
00:31:22,030 --> 00:31:29,280
Tukaj smo brali v glavo prvi, ki je nekako podobno, kako beremo v glavi

378
00:31:29,280 --> 00:31:33,580
za datoteke bitnih.

379
00:31:33,580 --> 00:31:38,000
Kaj delamo tukaj se preverjali, ali so informacije v glavi

380
00:31:38,000 --> 00:31:44,330
vsebuje pravo magično številko, ki nakazuje, da je dejanska slika Huff,

381
00:31:44,330 --> 00:31:53,610
Nato vse te preglede, da se prepriča, da je dokumentacija, ki smo odprti, je dejanska huffed datoteke ali ne.

382
00:31:53,610 --> 00:32:05,330
Kaj to je oddaja frekvence vseh simbolov, ki jih lahko vidimo

383
00:32:05,330 --> 00:32:09,790
v terminalu v grafični tabeli.

384
00:32:09,790 --> 00:32:15,240
Ta del se bo koristen.

385
00:32:15,240 --> 00:32:24,680
To je malo in se glasi bit by bit v spremenljivki bit in ga natisne.

386
00:32:28,220 --> 00:32:35,430
Torej, če sem bil, da pokličete na smetišče hth.bin, ki je posledica huffing datoteko

387
00:32:35,430 --> 00:32:39,490
s pomočjo kadrovske rešitve, bi to dobil.

388
00:32:39,490 --> 00:32:46,000
To je prikazovanje vseh teh znakov in nato dajanje frekvenco, pri kateri se pojavi.

389
00:32:46,000 --> 00:32:51,180
Če pogledamo, večina od njih so 0s, razen to: H, ki se pojavi dvakrat,

390
00:32:51,180 --> 00:32:54,820
in nato T, ki se pojavi enkrat.

391
00:32:54,820 --> 00:33:07,860
In tukaj imamo dejansko sporočilo v 0s in 1s.

392
00:33:07,860 --> 00:33:15,450
Če pogledamo hth.txt, ki je menda izvirno sporočilo, da je bil huffed,

393
00:33:15,450 --> 00:33:22,490
pričakujemo, da bomo videli nekaj HS in TS tam.

394
00:33:22,490 --> 00:33:28,720
Natančneje, pričakujemo, da bomo videli samo 1 in 2 T HS.

395
00:33:32,510 --> 00:33:37,440
Tu smo v hth.txt. V resnici se je HTH.

396
00:33:37,440 --> 00:33:41,270
Gostje imajo tam, čeprav ne moremo videti, je znak za novo vrstico.

397
00:33:41,270 --> 00:33:53,190
Datoteka Huff hth.bin tudi kodiranje znak za novo vrstico, kot dobro.

398
00:33:55,680 --> 00:34:01,330
Tukaj, saj vemo, da je za HTH in nato v novo vrstico,

399
00:34:01,330 --> 00:34:07,340
lahko vidimo, da verjetno predstavlja H z enim samim 1

400
00:34:07,340 --> 00:34:17,120
in potem je verjetno T 01 in potem naslednji H 1, kakor tudi

401
00:34:17,120 --> 00:34:21,139
in potem imamo novo vrstico navede z dvema 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> In končno, ker imamo opravka z več c. In. H datoteke,

404
00:34:31,600 --> 00:34:36,350
da bomo imeli precej kompleksen argument prevajalnik,

405
00:34:36,350 --> 00:34:40,460
in zato imamo tukaj Makefile, ki omogoča smetišče za vas.

406
00:34:40,460 --> 00:34:47,070
Toda v resnici, boste morali iti na izdelavo lastne puff.c datoteko.

407
00:34:47,070 --> 00:34:54,330
Datoteka Makefile dejansko ne ukvarja z izdelavo puff.c za vas.

408
00:34:54,330 --> 00:34:59,310
Odhajamo, da je do vas, da uredite Makefile.

409
00:34:59,310 --> 00:35:05,930
Ko vnesete ukaz, kot da bi vse, na primer, se bo vse od njih za vas.

410
00:35:05,930 --> 00:35:10,760
Vas prosimo, da pogled na primere Makefile iz preteklih pset

411
00:35:10,760 --> 00:35:17,400
kot tudi zletel tega eno, kako boste morda lahko, da bo vaše Puff datoteko

412
00:35:17,400 --> 00:35:20,260
z urejanjem tega Makefile.

413
00:35:20,260 --> 00:35:22,730
To je vse za našo distribucijsko kode.

414
00:35:22,730 --> 00:35:28,380
>> Ko smo gotten skozi vse to, potem tukaj je samo še en opomin

415
00:35:28,380 --> 00:35:30,980
o tem, kako se bomo morali ukvarjati z vozlišči Huffman.

416
00:35:30,980 --> 00:35:35,400
Ne bomo se jim kliče vozlov več, da bomo lahko kličem jim drevesa

417
00:35:35,400 --> 00:35:39,260
kjer bomo predstavljali svoj simbol s char,

418
00:35:39,260 --> 00:35:43,340
njihova pogostost, število dogodkov, s celo število.

419
00:35:43,340 --> 00:35:47,370
Mi smo z uporabo, ker je bolj natančna kot likvidna sredstva.

420
00:35:47,370 --> 00:35:52,980
In potem imamo še eno kazalec na levi otrok, kot tudi pravico otroka.

421
00:35:52,980 --> 00:35:59,630
Gozdov, kot smo videli, je le povezani seznam dreves.

422
00:35:59,630 --> 00:36:04,670
Konec koncev, če bomo izgradnji naše Huff datoteko

423
00:36:04,670 --> 00:36:07,580
želimo, da naši gozdovi, da vsebuje samo 1 drevo -

424
00:36:07,580 --> 00:36:12,420
1 drevo, 1 koren z več otroki.

425
00:36:12,420 --> 00:36:20,840
Prej, ko sva samo, da naše Huffman dreves,

426
00:36:20,840 --> 00:36:25,360
smo začeli s postavitvijo vseh vozlišč na našem zaslonu

427
00:36:25,360 --> 00:36:27,790
in pravi, da bomo imeli teh vozlišč,

428
00:36:27,790 --> 00:36:32,920
na koncu so si bo listi, in to je njihova simbol, to je njihova pogostost.

429
00:36:32,920 --> 00:36:42,070
V našem gozdu, če imamo samo 3 črke, da je gozd 3 dreves.

430
00:36:42,070 --> 00:36:45,150
In potem, ko gremo naprej, ko smo dodali prvo staršev,

431
00:36:45,150 --> 00:36:48,080
smo naredili gozd 2 dreves.

432
00:36:48,080 --> 00:36:54,930
Odstranili smo 2 teh otrok iz našega gozda in jo nadomestiti z matično vozlišču

433
00:36:54,930 --> 00:36:58,820
da je imela ta 2 vozlišč, kot otrok.

434
00:36:58,820 --> 00:37:05,600
In potem končno, naš zadnji korak z izdelavo naš primer z AS, BS in Cs

435
00:37:05,600 --> 00:37:08,030
bi bilo, da bi končno staršev,

436
00:37:08,030 --> 00:37:13,190
in tako potem bi to lahko naša skupna števila dreves v gozdu v 1.

437
00:37:13,190 --> 00:37:18,140
Ali vsi videli, kako ste začeli z več dreves v svojem gozdu

438
00:37:18,140 --> 00:37:22,520
in na koncu z 1? Ok. Kul.

439
00:37:25,530 --> 00:37:28,110
>> Kaj moramo storiti za Puff?

440
00:37:28,110 --> 00:37:37,110
Kaj moramo storiti, je zagotoviti, da se, tako kot vedno, so nam pravo vrsto vnosa

441
00:37:37,110 --> 00:37:39,090
tako da bomo lahko dejansko zagnati program.

442
00:37:39,090 --> 00:37:43,130
V tem primeru se bomo, da se nam daje po prvi argument v ukazni vrstici

443
00:37:43,130 --> 00:37:53,440
Še 2: slika, da želimo raztezanje in proizvodnja raztegne datoteko.

444
00:37:53,440 --> 00:38:00,410
Toda, ko bomo poskrbeli, da so nas prehaja v pravo mero vrednosti,

445
00:38:00,410 --> 00:38:05,820
želimo zagotoviti, da bo vnos je datoteka Huff ali ne.

446
00:38:05,820 --> 00:38:10,420
In potem, ko bomo zagotovili, da je datoteka Huff, nato pa želimo zgraditi naše drevo,

447
00:38:10,420 --> 00:38:20,940
zgraditi drevo tako, da se ujema z drevesa, da oseba, ki je poslal sporočilo zgrajena.

448
00:38:20,940 --> 00:38:25,840
Potem, ko smo zgradili drevo, potem lahko imamo opravka z 0 in 1s, da sta se srečala na,

449
00:38:25,840 --> 00:38:29,590
ravnajo po našem drevesu, ker je enaka,

450
00:38:29,590 --> 00:38:33,510
nato pa napisali, da je sporočilo jasno, razlagajo bitov nazaj v znakov.

451
00:38:33,510 --> 00:38:35,880
In potem na koncu, ker imamo opravka z kazalci tukaj

452
00:38:35,880 --> 00:38:38,110
želimo zagotoviti, da nimamo nobenih spomin razpoka

453
00:38:38,110 --> 00:38:41,330
in da smo brez vsega.

454
00:38:42,820 --> 00:38:46,430
>> Zagotavljanje pravilne uporabe je star klobuk za nas do sedaj.

455
00:38:46,430 --> 00:38:51,980
Mi v vložek, ki se bo ime datoteke za napihniti,

456
00:38:51,980 --> 00:38:56,010
nato pa določite izhod,

457
00:38:56,010 --> 00:39:01,580
tako ime datoteke za proizvodnjo škroba v prahu, ki bo besedilna datoteka.

458
00:39:03,680 --> 00:39:08,820
To je navada. In zdaj smo želeli zagotoviti, da se vnos huffed ali ne.

459
00:39:08,820 --> 00:39:16,420
Thinking nazaj, je bilo še kaj v distribucijski kodo, da bi nam pomagali

460
00:39:16,420 --> 00:39:21,570
z razumevanjem, ali je datoteka huffed ali ne?

461
00:39:21,570 --> 00:39:26,910
Ni bilo informacij v huffile.c o Huffeader.

462
00:39:26,910 --> 00:39:33,430
Vemo, da ima vsaka datoteka Huff je Huffeader z njim povezan s čarobno številko

463
00:39:33,430 --> 00:39:37,240
kot tudi niz frekvenc za vsak znak

464
00:39:37,240 --> 00:39:39,570
kot tudi vsote.

465
00:39:39,570 --> 00:39:43,180
Vemo, da je, ampak tako je pokukati v dump.c,

466
00:39:43,180 --> 00:39:49,120
, v katerem je bilo branje v datoteko Huff.

467
00:39:49,120 --> 00:39:53,990
In so za to, da se je morala preveriti, ali je bilo res huffed ali ne.

468
00:39:53,990 --> 00:40:03,380
Torej, morda bi lahko uporabili dump.c kot strukturo za naše puff.c.

469
00:40:03,380 --> 00:40:12,680
Nazaj na pset 4, ko smo imeli datoteke copy.c da kopirali v trojic RGB

470
00:40:12,680 --> 00:40:14,860
in mi razlaga, da je za Whodunit in velikost,

471
00:40:14,860 --> 00:40:20,390
Podobno je, kaj lahko narediš, samo zaženite ukaz cp, kot dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
in uporabi nekaterih kodeksa tam.

473
00:40:23,600 --> 00:40:28,210
Vendar pa to ne bo tako enostavno procesa

474
00:40:28,210 --> 00:40:33,010
za prevajanje vašega dump.c v puff.c,

475
00:40:33,010 --> 00:40:36,160
ampak vsaj vam daje nekje začeti

476
00:40:36,160 --> 00:40:40,540
o tem, kako zagotoviti, da se vnos dejansko huffed ali ne

477
00:40:40,540 --> 00:40:43,240
kot tudi nekaj drugih stvari.

478
00:40:45,930 --> 00:40:50,250
Smo zagotoviti pravilno uporabo in zagotoviti, da se huffed vnos.

479
00:40:50,250 --> 00:40:53,570
Vsakič, ko smo naredili, da smo naredili našo pravilno preverjanje napak,

480
00:40:53,570 --> 00:41:01,520
Tako vračanje in zapustil funkcijo, če pride do izpada nekaterih, če je to problem.

481
00:41:01,520 --> 00:41:07,170
>> Zdaj, kaj želimo storiti, je graditi dejanski drevo.

482
00:41:08,840 --> 00:41:12,640
Če se ozremo v gozdu, so 2 glavne naloge

483
00:41:12,640 --> 00:41:15,800
da bomo želeli postati zelo pozna.

484
00:41:15,800 --> 00:41:23,870
Tam je logično funkcijo rastlin, da rastline, ki niso 0 frekvenca dreves v naših gozdov.

485
00:41:23,870 --> 00:41:29,250
In tako se podaš v kazalec v gozd in je kazalec na drevo.

486
00:41:32,530 --> 00:41:40,340
Hitro vprašanje: Koliko gozdovi boste imeli, ko ste izgradnjo drevo Huffman?

487
00:41:44,210 --> 00:41:46,650
Naš gozd je kot naša platna, kajne?

488
00:41:46,650 --> 00:41:50,800
Torej smo le, da bo še 1 gozd, pa bomo imeli več dreves.

489
00:41:50,800 --> 00:41:57,590
Torej, preden pokličete napravo, ste verjetno boš želel, da bi svoj gozd.

490
00:41:57,590 --> 00:42:04,430
Tukaj je ukaz za to, če pogledaš na forest.h o tem, kako si lahko gozd.

491
00:42:04,430 --> 00:42:09,270
Lahko posadi drevo. Vemo, kako to storiti.

492
00:42:09,270 --> 00:42:11,590
In potem si lahko tudi izberete drevo od gozda,

493
00:42:11,590 --> 00:42:17,540
odstranitev drevesa z najmanjšo težo in vam daje kazalec na to.

494
00:42:17,540 --> 00:42:23,090
Thinking nazaj, ko smo delali od primerov sebe,

495
00:42:23,090 --> 00:42:27,980
Ko smo jo črpa, preprosto le dodal povezav.

496
00:42:27,980 --> 00:42:31,680
Ampak tukaj, namesto da bi ga zgolj dodajanje povezav

497
00:42:31,680 --> 00:42:40,630
si o njej mislijo več, kot ste odstraniti 2 teh vozlišč in jo zamenjati z drugo.

498
00:42:40,630 --> 00:42:44,200
Če želite izraziti, da je glede na obiranje in sajenje

499
00:42:44,200 --> 00:42:48,840
boš pobiral 2 dreves in nato sajenje drugo drevo

500
00:42:48,840 --> 00:42:54,060
da ima ta 2 drevesa, ki ste ga izbrali kot otroci.

501
00:42:57,950 --> 00:43:05,280
Za izgradnjo drevo Huffman, si lahko preberete v simbole in frekvenc, da bi

502
00:43:05,280 --> 00:43:10,790
ker Huffeader omogoča, da za vas,

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

504
00:43:14,250 --> 00:43:19,660
Torej, lahko greš naprej in kar ignorirati vse, kar z 0 v njem

505
00:43:19,660 --> 00:43:23,760
saj ne želimo, 256 listov na koncu od tega.

506
00:43:23,760 --> 00:43:27,960
Mi samo želimo število listov, ki so znaki

507
00:43:27,960 --> 00:43:31,600
, ki se dejansko uporabljajo v spisu.

508
00:43:31,600 --> 00:43:37,590
Si lahko preberete na teh simbolov in vsak od teh simbolov, ki imajo od 0 frekvenc,

509
00:43:37,590 --> 00:43:40,440
ki se bodo drevesa.

510
00:43:40,440 --> 00:43:45,990
Kaj lahko storite, je vsakič, ko boste brali v tretji 0 simbol frekvence

511
00:43:45,990 --> 00:43:50,660
lahko posadili to drevo v gozdu.

512
00:43:50,660 --> 00:43:56,620
Ko boste posadili drevesa v gozdu, se lahko pridružite drevesa, kot bratje in sestre,

513
00:43:56,620 --> 00:44:01,130
tako vrača v sajenje in nabiranje, kjer izberete 2 in nato rastlina 1,

514
00:44:01,130 --> 00:44:05,820
če je ta 1, ki ga je matična rastlina od 2 otroka, ki ste ga izbrali.

515
00:44:05,820 --> 00:44:11,160
Torej vaš končni rezultat pa bo eno drevo v svojem gozdu.

516
00:44:16,180 --> 00:44:18,170
To je, kako si zgraditi drevo.

517
00:44:18,170 --> 00:44:21,850
>> Obstaja nekaj stvari, ki bi lahko gredo narobe

518
00:44:21,850 --> 00:44:26,580
saj imamo opravka z izdelavo novih dreves in se ukvarjajo s kazalci in takih stvari.

519
00:44:26,580 --> 00:44:30,450
Pred ko smo se ukvarjajo s kazalci,

520
00:44:30,450 --> 00:44:36,580
ko smo malloc'd smo želeli, da se prepričajte, da ni vrnil nam NULL vrednost kazalca.

521
00:44:36,580 --> 00:44:42,770
Torej v več korakih v tem procesu pa se bodo več primerov

522
00:44:42,770 --> 00:44:45,920
če bi tvoj program ne uspe.

523
00:44:45,920 --> 00:44:51,310
Kaj želite storiti, je, da želite poskrbite, da boste obravnavo teh napak,

524
00:44:51,310 --> 00:44:54,580
in v spec pravi, da jih obravnava elegantno,

525
00:44:54,580 --> 00:45:00,280
tako rad izpisal sporočilo uporabniku jim poveste, zakaj je program mora prenehati

526
00:45:00,280 --> 00:45:03,050
in potem takoj nehaj.

527
00:45:03,050 --> 00:45:09,490
Za to napako ravnanje, ne pozabite, da želite to preveriti

528
00:45:09,490 --> 00:45:12,160
vsak čas, da bi lahko prišlo do okvare.

529
00:45:12,160 --> 00:45:14,660
Vsakič, da delate nov kazalec

530
00:45:14,660 --> 00:45:17,040
želite prepričati, da je to uspešen.

531
00:45:17,040 --> 00:45:20,320
Preden kaj smo narediti je, da nov kazalec in malloc it,

532
00:45:20,320 --> 00:45:22,380
in potem bi morali preveriti, ali je ta kazalec NULL.

533
00:45:22,380 --> 00:45:25,670
Torej se bodo nekateri primeri, kjer si lahko storite, da se

534
00:45:25,670 --> 00:45:28,610
ampak včasih ste dejansko kliče funkcijo

535
00:45:28,610 --> 00:45:33,100
in v tej funkciji, to je tisti, ki je početje mallocing.

536
00:45:33,100 --> 00:45:39,110
V tem primeru, če se ozremo nazaj na nekatere funkcije v kodi,

537
00:45:39,110 --> 00:45:42,260
nekateri od njih so Boolove funkcije.

538
00:45:42,260 --> 00:45:48,480
V abstraktnem primeru, če imamo logično funkcijo imenovano foo,

539
00:45:48,480 --> 00:45:54,580
v bistvu, lahko sklepamo, da poleg počnete karkoli foo ne,

540
00:45:54,580 --> 00:45:57,210
saj je logično funkcijo, vrne resnična ali neresnična -

541
00:45:57,210 --> 00:46:01,300
Res če bo uspešen, če ne lažno.

542
00:46:01,300 --> 00:46:06,270
Zato smo želeli preveriti, ali je vrnitev vrednost foo resnična ali neresnična.

543
00:46:06,270 --> 00:46:10,400
Če je napačna, to pomeni, da bomo želeli natisniti nekakšno sporočilo

544
00:46:10,400 --> 00:46:14,390
in zaprite program.

545
00:46:14,390 --> 00:46:18,530
Kaj želite storiti, je preveriti vrnjeno vrednost foo.

546
00:46:18,530 --> 00:46:23,310
Če foo vrne false, potem vemo, da smo naleteli na kakšno napako

547
00:46:23,310 --> 00:46:25,110
in moramo zapustiti naš program.

548
00:46:25,110 --> 00:46:35,600
Način za to je, da imajo bolezen, če je dejansko funkcija sama vaše stanje.

549
00:46:35,600 --> 00:46:39,320
Povejte foo se v x.

550
00:46:39,320 --> 00:46:43,390
Mi lahko kot pogoj, če (foo (x)).

551
00:46:43,390 --> 00:46:50,900
V bistvu to pomeni, če na koncu foo izvršitve se vrne res,

552
00:46:50,900 --> 00:46:57,390
potem lahko to storimo, ker funkcija mora oceniti foo

553
00:46:57,390 --> 00:47:00,500
da bi ocenila celotno stanje.

554
00:47:00,500 --> 00:47:06,500
Torej to je, kako lahko naredite nekaj, če funkcija vrne true in je uspešen.

555
00:47:06,500 --> 00:47:11,800
Toda, ko ste preverjanje napak, lahko le želeli zapustiti, če je vaša funkcija vrne false.

556
00:47:11,800 --> 00:47:16,090
Kaj lahko storite, je le dodati == false ali pa dodate pok pred njim

557
00:47:16,090 --> 00:47:21,010
in potem boste morali, če (! foo).

558
00:47:21,010 --> 00:47:29,540
Znotraj tega organa tega pogoja bi morali vse napake ravnanje,

559
00:47:29,540 --> 00:47:36,940
Tako kot, "Ne morem ustvariti to drevo" in se nato vrne 1 ali kaj podobnega.

560
00:47:36,940 --> 00:47:43,340
Kaj to naredi, pa je, da čeprav se vrne false foo -

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

562
00:47:46,980 --> 00:47:51,060
Potem ti ni treba poklicati foo znova. To je skupna napačno.

563
00:47:51,060 --> 00:47:54,730
Ker je bilo v tem stanju, je to že ocenila,

564
00:47:54,730 --> 00:47:59,430
tako da že imate rezultat, če boste uporabljali, da drevo ali kaj podobnega

565
00:47:59,430 --> 00:48:01,840
ali rastlin ali kramp ali kaj podobnega.

566
00:48:01,840 --> 00:48:07,460
Je že to vrednost. To je že izvršena.

567
00:48:07,460 --> 00:48:10,730
Torej je smiselno uporabiti logičnih funkcij kot pogoj

568
00:48:10,730 --> 00:48:13,890
saj to, ali ste dejansko izvaja telo zanke,

569
00:48:13,890 --> 00:48:18,030
ga izvede funkcijo anyway.

570
00:48:22,070 --> 00:48:27,330
>> Naš predzadnji korak je pisno sporočilo v datoteko.

571
00:48:27,330 --> 00:48:33,070
Ko gradimo drevo Huffman, nato pa s pisanjem sporočila v spis je precej preprosta.

572
00:48:33,070 --> 00:48:39,260
To je zelo enostavno zdaj, da sledite 0 in 1s.

573
00:48:39,260 --> 00:48:45,480
In tako je po dogovoru vemo, da je na drevesu Huffman kažejo zapustil 0s

574
00:48:45,480 --> 00:48:48,360
in 1s kažejo prav.

575
00:48:48,360 --> 00:48:53,540
Torej, če ste prebrali v bit by bit, vsakič, ko boste dobili 0

576
00:48:53,540 --> 00:48:59,100
boste sledili levo vejo in nato vsakič, ko boste brali v 1

577
00:48:59,100 --> 00:49:02,100
boste sledili pravo vejo.

578
00:49:02,100 --> 00:49:07,570
In potem si bomo še naprej, dokler ne zadeti listov

579
00:49:07,570 --> 00:49:11,550
ker se listi se bodo na koncu veje.

580
00:49:11,550 --> 00:49:16,870
Kako lahko poveste, ali smo zadeli listov ali ne?

581
00:49:19,800 --> 00:49:21,690
Uspelo nam je povedal.

582
00:49:21,690 --> 00:49:24,040
[Študent] Če so kazalci NULL. >> Ja.

583
00:49:24,040 --> 00:49:32,220
Mi lahko poveste, če smo zadeli liste, če so kazalci tako levi in ​​desni dreves so NULL.

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

585
00:49:34,110 --> 00:49:40,320
Vemo, da želimo brati malo po malo v našo datoteko Huff.

586
00:49:43,870 --> 00:49:51,220
Kot smo videli prej v dump.c, kaj so naredili, je, da bere malo po malo v datoteko Huff

587
00:49:51,220 --> 00:49:54,560
in samo natisnjene, kaj ti je bilo bitov.

588
00:49:54,560 --> 00:49:58,430
Ne bomo se s tem. Bomo, da se delaš nekaj, kar je malce bolj zapletena.

589
00:49:58,430 --> 00:50:03,620
Toda kaj, kar lahko storimo je, da smo lahko, da delček kode, ki se glasi, da bi bit.

590
00:50:03,620 --> 00:50:10,250
Tukaj imamo celo število, ki predstavlja sedanjo bit bit, da smo.

591
00:50:10,250 --> 00:50:15,520
Ta skrbi za ponavljanjem vseh bitov v spisu, dokler ne dosežete konec datoteke.

592
00:50:15,520 --> 00:50:21,270
Na podlagi tega, potem boste želeli imeti nekakšno iterator

593
00:50:21,270 --> 00:50:26,760
za prečkanje drevo.

594
00:50:26,760 --> 00:50:31,460
In potem glede na to, bit 0 ali 1,

595
00:50:31,460 --> 00:50:36,920
boste želeli niti premakniti iterator na levi ali ga premaknete v desno

596
00:50:36,920 --> 00:50:44,080
do konca, dokler ne boste zadeli list, tako da vse do vozlišča, ki ste na

597
00:50:44,080 --> 00:50:48,260
ne kaže, da vse več vozlišč.

598
00:50:48,260 --> 00:50:54,300
Zakaj lahko to storimo z datoteko Huffman, vendar ne Morse kode?

599
00:50:54,300 --> 00:50:56,610
Ker v Morse code tam je malo dvoumnosti.

600
00:50:56,610 --> 00:51:04,440
Lahko bi bilo všeč, oh čakati, smo zadeli pismo vzdolž poti, tako da morda je to naša pismo,

601
00:51:04,440 --> 00:51:08,150
ker če bomo še naprej le malo dlje, bi potem smo zadeli še eno pismo.

602
00:51:08,150 --> 00:51:13,110
Ampak to se ne bo zgodilo kodiranja Huffman,

603
00:51:13,110 --> 00:51:17,540
tako da bomo lahko prepričani, da je edini način, da bomo zadeli značaja

604
00:51:17,540 --> 00:51:23,480
je, če vozlišča na levi in ​​desni so otroci NULL.

605
00:51:28,280 --> 00:51:32,350
>> Na koncu želimo, da osvobodi vse našem spominu.

606
00:51:32,350 --> 00:51:37,420
Želimo, da tako blizu spis Huff, da smo se ukvarjajo z

607
00:51:37,420 --> 00:51:41,940
kot tudi odstraniti vse dreves v našem gozdu.

608
00:51:41,940 --> 00:51:46,470
Glede na vaše izvajanje, ste verjetno boš želel poklicati odstraniti gozd

609
00:51:46,470 --> 00:51:49,780
namesto da bi dejansko šel skozi vse drevje sami.

610
00:51:49,780 --> 00:51:53,430
Ampak, če ste naredili kakršne koli začasne dreves, boste želeli, da osvobodi.

611
00:51:53,430 --> 00:51:59,060
Veš kodo najboljši, tako da boste vedeli, kje ste dodeljevanju pomnilnika.

612
00:51:59,060 --> 00:52:04,330
In tako, če greš v, najprej celo nadzor F'ing za knjižnične funkcije malloc,

613
00:52:04,330 --> 00:52:08,330
videli, ko boste malloc in pazite, da osvobodi vse, ki

614
00:52:08,330 --> 00:52:10,190
potem pa šele skozi svojo kodo,

615
00:52:10,190 --> 00:52:14,260
razumevanje, če ste morda dodeliti pomnilnika.

616
00:52:14,260 --> 00:52:21,340
Ponavadi bi si rekel: "Na koncu datoteke grem odstraniti gozd na moj gozd"

617
00:52:21,340 --> 00:52:23,850
tako da v bistvu jasno, da spomin, brez, da

618
00:52:23,850 --> 00:52:28,310
«In potem sem tudi dogaja, da se spis in nato moj program se bo nehal."

619
00:52:28,310 --> 00:52:33,810
Vendar pa je, da je edini čas, da vaš program zapre?

620
00:52:33,810 --> 00:52:37,880
Ne, ker bi včasih ni bilo napaka, ki se je zgodilo.

621
00:52:37,880 --> 00:52:42,080
Mogoče ne bi mogli odpreti datoteko ali ne bi mogli narediti še drevo

622
00:52:42,080 --> 00:52:49,340
ali neke vrste napake se je zgodilo v postopku dodeljevanja pomnilnika, zato se je vrnil NULL.

623
00:52:49,340 --> 00:52:56,710
Napaka se je zgodilo in potem smo se vrnili in zaprete.

624
00:52:56,710 --> 00:53:02,040
Torej hočeš prepričati, da se morebitni čas, da se vaš program zapre,

625
00:53:02,040 --> 00:53:06,980
hočeš, da osvobodi vse spominu tam.

626
00:53:06,980 --> 00:53:13,370
To ni samo bo na koncu glavne funkcije, ki jo zaprete kodo.

627
00:53:13,370 --> 00:53:20,780
Hočeš, da se ozremo v vsakem primeru, da bi vaša koda lahko vrnili predčasno

628
00:53:20,780 --> 00:53:25,070
in nato brez spomina ne glede na smisel.

629
00:53:25,070 --> 00:53:30,830
Povejte so vabljeni, da gozd in da se vrne false.

630
00:53:30,830 --> 00:53:34,230
Potem verjetno ne boste potrebovali, če želite odstraniti gozd

631
00:53:34,230 --> 00:53:37,080
ker nimate gozd še ni.

632
00:53:37,080 --> 00:53:42,130
Ampak na vsaki točki v kodi, kjer bi lahko vrnete prezgodaj

633
00:53:42,130 --> 00:53:46,160
želite poskrbite, da boste sprostili morebitno spomin.

634
00:53:46,160 --> 00:53:50,020
>> Torej, ko imamo opravka s sprostitvijo pomnilnika in ob potencialnih lukenj,

635
00:53:50,020 --> 00:53:55,440
želimo ne le uporabite našo presojo in naš logiko

636
00:53:55,440 --> 00:54:01,850
temveč tudi za uporabo Valgrind ugotoviti, ali smo osvobojeni vseh našem spominu pravilno ali ne.

637
00:54:01,850 --> 00:54:09,460
Lahko deluje na Valgrind Puff, potem pa moraš tudi dajati

638
00:54:09,460 --> 00:54:14,020
Pravica število argumentov v ukazni vrstici, da Valgrind.

639
00:54:14,020 --> 00:54:18,100
Lahko bežiš, ampak rezultat je nekoliko skrivnosten.

640
00:54:18,100 --> 00:54:21,630
Smo gotten malo uporablja, da je z speller, vendar še vedno potrebujemo malo več pomoči,

641
00:54:21,630 --> 00:54:26,450
Tako potem teče z nekaj več zastav, kot puščanja preverite = celoti,

642
00:54:26,450 --> 00:54:32,040
, da bo verjetno, da nam nekaj več koristnih izhod na Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> In še koristen namig, ko ste razhroščevanje je ukaz diff.

644
00:54:39,040 --> 00:54:48,520
Lahko dostop do izvajanja osebja, ki je v Huff, ki delujejo na besedilno datoteko,

645
00:54:48,520 --> 00:54:55,400
in ga nato vnese v binarno datoteko, binarni Huff datoteke, ki je specifična.

646
00:54:55,400 --> 00:54:59,440
Potem, če vodijo svojo lastno dim na tej binarne datoteke,

647
00:54:59,440 --> 00:55:03,950
potem pa najbolje, vaš izhodni besedilna datoteka, se bo enako

648
00:55:03,950 --> 00:55:08,200
s prvotnim tistega, ki ga opravili noter

649
00:55:08,200 --> 00:55:15,150
Tukaj sem z hth.txt kot primer, in to je ena govorila v vašem spec.

650
00:55:15,150 --> 00:55:21,040
To je dobesedno samo HTH in nato vrstico.

651
00:55:21,040 --> 00:55:30,970
Ampak zagotovo počutili svobodne in ste zagotovo spodbuja k uporabi daljših primere

652
00:55:30,970 --> 00:55:32,620
za besedilni datoteki.

653
00:55:32,620 --> 00:55:38,110
>> Lahko se celo strel na morda stisne in nato simbolne

654
00:55:38,110 --> 00:55:41,600
nekatere datoteke, ki jih uporabljajo v speller, kot so Vojna in mir

655
00:55:41,600 --> 00:55:46,710
ali Jane Austen ali nekaj takega - da bi bilo nekako kul - ali Austin Powers,

656
00:55:46,710 --> 00:55:51,880
vrste, ki se ukvarjajo z večjimi datotekami, ker ne bi prišel do tega

657
00:55:51,880 --> 00:55:55,590
Če smo uporabili naslednje funkcije tukaj, ls-l.

658
00:55:55,590 --> 00:56:01,150
Mi smo se uporablja za ls, ki v bistvu navaja vse vsebine v našem trenutnem imeniku.

659
00:56:01,150 --> 00:56:07,860
Podaje v zastave-l prikaže dejansko velikost teh datotek.

660
00:56:07,860 --> 00:56:12,690
Če greš skozi spec pset, da je dejansko vas popelje skozi ustvarjanje binarno datoteko,

661
00:56:12,690 --> 00:56:16,590
da bi ga huffing, in boste videli, da je za zelo majhne datoteke

662
00:56:16,590 --> 00:56:23,910
prostor stroški stisniti in prevajanje vse te informacije

663
00:56:23,910 --> 00:56:26,980
vseh frekvenc in stvari, kot da odtehta dejanske koristi

664
00:56:26,980 --> 00:56:30,000
za stiskanje datoteke na prvem mestu.

665
00:56:30,000 --> 00:56:37,450
Ampak, če vi prost dostop na nekaj daljših besedilnih datotek, potem lahko vidite, da ste začeli, da bi dobili nekaj koristi

666
00:56:37,450 --> 00:56:40,930
V stiskanje te datoteke.

667
00:56:40,930 --> 00:56:46,210
>> In potem končno, imamo staro kolega GDB, ki bo zagotovo prišel prav preveč.

668
00:56:48,360 --> 00:56:55,320
>> Ali imate vprašanja o drevesih Huff in procesom morda izdelave drevesa

669
00:56:55,320 --> 00:56:58,590
ali katera koli druga vprašanja o Puff Huff'n?

670
00:57:00,680 --> 00:57:02,570
Ok. Jaz bom ostal približno za malo.

671
00:57:02,570 --> 00:57:06,570
>> Hvala vsem. To je bilo Walkthrough 6. In veliko sreče.

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