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

2
00:00:02,210 --> 00:00:04,810
[Zamyla Chan - Harvardo universiteto]

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

4
00:00:07,240 --> 00:00:12,180
>> Sveiki, visi, ir sveiki atvykę į Walkthrough 6: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
Huff'n Puff tai, ką mes darome, yra ketiname būti susijusios su Hafmano suspaustą failą

6
00:00:17,440 --> 00:00:20,740
ir tada skleisdamas jį atgal į viršų, todėl dekompresowania jį,

7
00:00:20,740 --> 00:00:25,810
, kad galėtume versti iš 0s ir 1s, kad vartotojas siunčia mums

8
00:00:25,810 --> 00:00:30,660
ir konvertuoti jį atgal į originalo tekstą.

9
00:00:30,660 --> 00:00:34,360
Pset 6 bus gana kietas, nes jūs ketinate pamatyti kai kurias iš priemonių,

10
00:00:34,360 --> 00:00:41,730
, kuriuos naudojote 4 pset ir pset 5 ir rūšis, sujungti juos į 1 gana tvarkingas koncepcija

11
00:00:41,730 --> 00:00:43,830
kai tu atėjai, galvoti apie tai.

12
00:00:43,830 --> 00:00:50,110
>> Taip pat, be abejo, pset 4 ir 5 buvo labiausiai sudėtinga psets, kad mes siūlome.

13
00:00:50,110 --> 00:00:53,950
Taigi nuo šiol, mes turime šį 1 Daugiau pset C,

14
00:00:53,950 --> 00:00:56,480
ir po, kad mes interneto programavimo.

15
00:00:56,480 --> 00:01:02,310
Taigi sveikinu save gauti per sunkiausias kupra CS50.

16
00:01:03,630 --> 00:01:09,760
>> Permainos Huff'n Puff mūsų Įrankiai šio pset bus Huffman medžiai,

17
00:01:09,760 --> 00:01:14,700
todėl suprasti ne tik kaip dvejetainiai medžiai darbą, bet taip pat specialiai Huffman medžius,

18
00:01:14,700 --> 00:01:16,240
kaip jie pastatyti.

19
00:01:16,240 --> 00:01:20,210
Ir tada mes ketiname turėti platinimo kodo šiame pset daug,

20
00:01:20,210 --> 00:01:22,480
ir mes atėjo pamatyti, kad iš tikrųjų kai kurie kodų sistemai

21
00:01:22,480 --> 00:01:24,670
gali būti neįmanoma iki galo suprasti dar,

22
00:01:24,670 --> 00:01:30,080
ir taip bus c failai, bet tada lydintys h failai

23
00:01:30,080 --> 00:01:34,300
duos mums pakankamai supratimo, kad mums reikia, kad mes žinome, kaip šios funkcijos veikia

24
00:01:34,300 --> 00:01:38,100
arba bent jau tai, ką jie turėtų daryti - jų įėjimai ir išėjimai -

25
00:01:38,100 --> 00:01:40,760
net jei mes nežinome, kas vyksta juodojoje dėžėje

26
00:01:40,760 --> 00:01:44,090
arba nesuprantate, kas vyksta "black box", per.

27
00:01:44,090 --> 00:01:49,400
Ir galiausiai, kaip įprasta, mes susiduriame su naujais duomenų struktūras,

28
00:01:49,400 --> 00:01:51,840
konkrečių rūšių mazgų, atkreipti dėmesį į tam tikrus dalykus,

29
00:01:51,840 --> 00:01:56,080
ir todėl čia ne tik projektavimo procesą, rašiklį ir popieriaus

30
00:01:56,080 --> 00:01:58,470
ir kai jūs bandote išsiaiškinti, kaip jūsų pset turėtų dirbti

31
00:01:58,470 --> 00:02:00,520
bet taip pat derinimo metu.

32
00:02:00,520 --> 00:02:06,140
Jūs galite turėti gdb šalia rašiklį ir popieriaus, o jūs imtis žemyn, kokios vertybės,

33
00:02:06,140 --> 00:02:09,320
kur yra jūsų rodyklės nukreipta, ir dalykų, pavyzdžiui, kad.

34
00:02:09,320 --> 00:02:13,720
>> Pirmiausia leiskite pažvelgti Huffman medžių.

35
00:02:13,720 --> 00:02:19,600
Huffman medžiai yra dvejetainiai medžiai, tai reiškia, kad kiekvienas mazgas turi tik 2 vaikus.

36
00:02:19,600 --> 00:02:24,870
Huffman medžių charakteristika yra ta, kad dažniausios reikšmės

37
00:02:24,870 --> 00:02:27,140
atstovauja Mažiausiai bitų.

38
00:02:27,140 --> 00:02:32,690
Matėme paskaitų pavyzdžių Morzės abėcėle, kokios konsoliduotų kai kurių raidžių.

39
00:02:32,690 --> 00:02:38,030
Jei jūs bandote versti A arba E, pavyzdžiui,

40
00:02:38,030 --> 00:02:43,940
jūs versti, kad dažnai, todėl vietoj to, kad naudoti pilną bitais

41
00:02:43,940 --> 00:02:48,640
skirta mums įprasto duomenų tipą, galite suspausti jį žemyn, kad mažiau

42
00:02:48,640 --> 00:02:53,730
ir tada tie laiškai, kurie atstovauja rečiau yra atstovaujama su ilgiau bitų

43
00:02:53,730 --> 00:02:59,840
, nes galite sau leisti, kad, kai jūs pasveriama dažnius, kad tokiomis raidėmis.

44
00:02:59,840 --> 00:03:03,020
Mes turime tą pačią idėją čia Huffman medžių

45
00:03:03,020 --> 00:03:12,360
kur mes darome grandinę, keliu natūra gauti tam tikrų ženklų.

46
00:03:12,360 --> 00:03:14,470
Ir tada simbolius, kurie turi didžiausią dažnį

47
00:03:14,470 --> 00:03:17,940
bus atstovaujama su mažiausiai bitų.

48
00:03:17,940 --> 00:03:22,020
>> Taip, kad jūs statyti Huffman medis

49
00:03:22,020 --> 00:03:27,430
pateikiant visų ženklų, kad tekste

50
00:03:27,430 --> 00:03:30,630
ir skaičiuojant jų dažnumą, kaip dažnai jie atrodo.

51
00:03:30,630 --> 00:03:33,880
Tai gali būti arba skaičius, kiek kartų tos raidės yra

52
00:03:33,880 --> 00:03:40,270
arba galbūt iš procentas visų simbolių, kiek kiekvienas iš jų atrodo.

53
00:03:40,270 --> 00:03:44,270
Ir taip, ką jūs darote yra, kai jūs turite visus to apibudino,

54
00:03:44,270 --> 00:03:49,060
tada jums atrodo 2 žemiausių dažnių ir tada prisijungti prie jų broliai ir seserys,

55
00:03:49,060 --> 00:03:55,660
kur tada patronuojanti mazgas turi dažnį, kuris yra jos 2 vaikais suma.

56
00:03:55,660 --> 00:04:00,870
Ir tada jūs pagal susitarimą sako, kad kairė mazgas,

57
00:04:00,870 --> 00:04:03,770
jums sekti, kad po 0 filialą,

58
00:04:03,770 --> 00:04:08,140
ir tada dešinė mazgas 1 filialas.

59
00:04:08,140 --> 00:04:16,040
Kaip matėme Morzės abėcėle, vienas kabliuko, kad jei turėjo tik pyptelėjimą ir Beep

60
00:04:16,040 --> 00:04:18,120
tai buvo dviprasmiškas.

61
00:04:18,120 --> 00:04:22,430
Jis gali būti arba 1 raidė arba ji gali būti iš 2 raidžių seka.

62
00:04:22,430 --> 00:04:27,790
Ir kas Huffman medžiai, nes pagal savo pobūdį iš simbolių

63
00:04:27,790 --> 00:04:34,140
ar mūsų galutiniai faktiniai ženklai yra paskutinis ant šakos mazgai -

64
00:04:34,140 --> 00:04:39,300
mes vadiname kaip lapai - remiantis tuo, kad negali būti jokių dviprasmybių

65
00:04:39,300 --> 00:04:45,160
laiškas, kurį bandote koduoti bitų serijos

66
00:04:45,160 --> 00:04:50,670
nes niekur kartu bitai, kurie atstovauja 1 raidė

67
00:04:50,670 --> 00:04:55,960
jūs susitinkate kitą visą laišką ir nebus bet kokios painiavos.

68
00:04:55,960 --> 00:04:58,430
Bet mes eiti į pavyzdžių, kad jus vaikinai iš tikrųjų galite pamatyti, kad

69
00:04:58,430 --> 00:05:02,120
vietoj mums tik sakau, kad tai tiesa.

70
00:05:02,120 --> 00:05:06,390
>> Pažvelkime Hafmano medžio paprastas pavyzdys.

71
00:05:06,390 --> 00:05:09,380
Turiu eilutę čia, kad yra 12 simbolių.

72
00:05:09,380 --> 00:05:14,010
Turiu 4 Kadangi 6 BS, ir 2 CS.

73
00:05:14,010 --> 00:05:17,270
Mano pirmas žingsnis būtų suskaičiuoti.

74
00:05:17,270 --> 00:05:20,760
Kiek kartų atrodo? Atrodo, 4 kartus į eilutę.

75
00:05:20,760 --> 00:05:25,060
B atrodo 6 kartus, o C atrodo 2 kartus.

76
00:05:25,060 --> 00:05:28,970
Žinoma, aš ruošiuosi pasakyti, aš naudoju B dažniausiai,

77
00:05:28,970 --> 00:05:35,970
todėl aš noriu atstovauti B su mažiausiai bitų skaičius, kuo mažiau 0s ir 1s.

78
00:05:35,970 --> 00:05:42,600
Ir tada aš taip pat ketina tikėtis C, taip pat reikalauti, kad labiausiai suma 0s ir 1s.

79
00:05:42,600 --> 00:05:48,550
Pirma, ką aš čia, aš pasidėjau jas didėjančia tvarka pagal dažnumą.

80
00:05:48,550 --> 00:05:52,710
Mes matome, kad C ir, jie yra mūsų 2 mažiausios dažniai.

81
00:05:52,710 --> 00:06:00,290
Mes sukursime patronuojanti mazgas, ir ta patronuojanti mazgas neturi laišką, su juo susijusios,

82
00:06:00,290 --> 00:06:05,070
tačiau ji turi dažnį, kuris yra suma.

83
00:06:05,070 --> 00:06:08,780
Suma tampa 2 + 4, kuris yra 6.

84
00:06:08,780 --> 00:06:10,800
Sekame paskui kairįjį filialą.

85
00:06:10,800 --> 00:06:14,970
Jeigu mes buvo, kad 6 mazgo, tada mes paseks 0 patekti į C

86
00:06:14,970 --> 00:06:17,450
ir tada gauti 1 A.

87
00:06:17,450 --> 00:06:20,300
Taigi dabar mes turime 2 mazgų.

88
00:06:20,300 --> 00:06:23,920
Mes turime vertė Vertė 6 ir tada mes taip pat turime kitos mazgas vertės 6.

89
00:06:23,920 --> 00:06:28,550
Ir taip 2 yra ne tik 2 mažiausios, o tik 2, kurie liko,

90
00:06:28,550 --> 00:06:33,820
todėl mes prisijungti prie kito iš tėvų, su suma yra 12.

91
00:06:33,820 --> 00:06:36,300
Taigi čia mes turime Huffman medis

92
00:06:36,300 --> 00:06:40,020
kur gauti B, kad būtų tiesiog bit 1

93
00:06:40,020 --> 00:06:45,430
ir tada gauti mes norėtume turėti 01 ir tada C, turintys 00.

94
00:06:45,430 --> 00:06:51,300
Taigi čia matome, kad iš esmės mes atstovaujame šiuos simbolius su 1 arba 2 bitai

95
00:06:51,300 --> 00:06:55,160
kur B, kaip prognozuojama, mažiausiai.

96
00:06:55,160 --> 00:07:01,730
Ir tada mes tikėjomės C turi labiausiai, bet kadangi ji tokia maža Huffman medis,

97
00:07:01,730 --> 00:07:06,020
tada taip pat atstovauja 2 bitai, o ne kažkur per vidurį.

98
00:07:07,820 --> 00:07:11,070
>> Tiesiog eiti per kitą paprastą pavyzdį Hafmano medžio,

99
00:07:11,070 --> 00:07:19,570
tarkime, jūs turite eilutę "Hello".

100
00:07:19,570 --> 00:07:25,360
Ką jūs darote, yra pirmasis galėtumėte pasakyti, kiek kartų H rodomi?

101
00:07:25,360 --> 00:07:34,200
H vieną kartą ir tada e atrodo vieną kartą ir tada mes turime l nesimatytų du kartus

102
00:07:34,200 --> 00:07:36,580
o pasirodo tik vieną kartą.

103
00:07:36,580 --> 00:07:44,310
Ir taip, tada mes tikimės, kad laiškas būti atstovaujamos mažiausiai bitų skaičius?

104
00:07:44,310 --> 00:07:47,450
[Studentas] l. >> L. Taip. l yra teisinga.

105
00:07:47,450 --> 00:07:50,730
Mes tikimės, l, kad jam būtų atstovaujama mažiausių bitų skaičius

106
00:07:50,730 --> 00:07:55,890
nes l į eilutę "Hello".

107
00:07:55,890 --> 00:08:04,280
Ką aš ruošiuosi padaryti dabar atkreipti dėmesį į šiuos mazgus.

108
00:08:04,280 --> 00:08:15,580
Turiu 1, kuris yra H, o tada dar 1, kuris yra e, tada A 1, kuris O

109
00:08:15,580 --> 00:08:23,410
dabar aš jų išleidimą, kad ir po to 2, kuris yra l.

110
00:08:23,410 --> 00:08:32,799
Tada aš sakau, taip, kad aš sukurti Huffman medį rasti 2 mazgų su mažiausiai dažnių

111
00:08:32,799 --> 00:08:38,010
ir padaryti juos broliai ir seserys, patronuojanti mazgas.

112
00:08:38,010 --> 00:08:41,850
Čia mes turime 3 mazgus su žemiausio dažnio. Jie visi 1.

113
00:08:41,850 --> 00:08:50,620
Taigi čia mes pasirinkti, kurį vieną mes ketiname susieti 1..

114
00:08:50,620 --> 00:08:54,850
Tarkime, aš pasirinksiu H ir e.

115
00:08:54,850 --> 00:09:01,150
Suma 1 + 1 yra 2, bet šis mazgas neturi laišką, su juo susijusios.

116
00:09:01,150 --> 00:09:04,440
Jis tiesiog turi vertę.

117
00:09:04,440 --> 00:09:10,950
Dabar pažvelgsime artimiausius 2 žemiausių dažnių.

118
00:09:10,950 --> 00:09:15,590
Štai 2 ir 1. Tai gali būti arba iš tų 2, bet aš ruošiuosi pasirinkti šį vieną.

119
00:09:15,590 --> 00:09:18,800
Suma yra 3.

120
00:09:18,800 --> 00:09:26,410
Ir galiausiai, aš tik 2 left, kad tada, kuris tampa 5.

121
00:09:26,410 --> 00:09:32,010
Tai čia, kaip ir tikėtasi, jei man užpildyti, kad kodavimo,

122
00:09:32,010 --> 00:09:37,480
1s visada teisę filialas ir 0s yra kairė.

123
00:09:37,480 --> 00:09:45,880
Tada mes turime l, sudaro tik 1 bit ir tada THE O 2

124
00:09:45,880 --> 00:09:52,360
ir tada iš 2, E ir H nukrenta iki 3 bitai.

125
00:09:52,360 --> 00:09:59,750
Todėl jūs galite perduoti šį pranešimą "Labas", o ne faktiškai naudojant simbolius

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

127
00:10:02,760 --> 00:10:07,910
Tačiau atminkite, kad kai kuriais atvejais mes turėjome ryšius su mūsų dažnumą.

128
00:10:07,910 --> 00:10:11,900
Galėjo arba prisijungė prie H ir pirmąjį THE O gal.

129
00:10:11,900 --> 00:10:15,730
Arba vėliau, kai mes turėjome 2 atstovaujama l

130
00:10:15,730 --> 00:10:19,410
taip pat prisijungė prie vienos atstovaujama 2, mes galime sieja vieną.

131
00:10:19,410 --> 00:10:23,630
>> Ir todėl, kai jūs siunčiate 0s ir 1s, kad iš tiesų negarantuoja

132
00:10:23,630 --> 00:10:27,090
kad paslaugų gavėjas galėtų visiškai skaityti jūsų pranešimą Iškart

133
00:10:27,090 --> 00:10:30,490
nes jie gali nežinoti, kuris sprendimas, kurį padarė.

134
00:10:30,490 --> 00:10:34,920
Taigi, kai mes susiduriame su Hafmano suspaudimo,

135
00:10:34,920 --> 00:10:40,090
kažkaip mes turime pasakyti, kad mūsų žinios gavėją, kaip mes nusprendėme -

136
00:10:40,090 --> 00:10:43,470
Jie turi žinoti, kažkokia papildoma informacija

137
00:10:43,470 --> 00:10:46,580
be suspausto pranešimo.

138
00:10:46,580 --> 00:10:51,490
Jie turi suprasti, kas iš tikrųjų atrodo kaip medis,

139
00:10:51,490 --> 00:10:55,450
kaip mes iš tikrųjų šiuos sprendimus.

140
00:10:55,450 --> 00:10:59,100
>> Šiuo atveju buvo tik tai, apie faktinį kiekį pagal pavyzdžius,

141
00:10:59,100 --> 00:11:01,550
bet kartais jums taip pat gali turėti Huffman medis

142
00:11:01,550 --> 00:11:05,760
pagal nurodytą dažnumą raidės yra, ir jis yra lygiai toks pats procesas.

143
00:11:05,760 --> 00:11:09,090
Čia aš išreikšti procentais arba mažiau,

144
00:11:09,090 --> 00:11:11,290
ir todėl čia lygiai toks pats dalykas.

145
00:11:11,290 --> 00:11:15,300
Manau, kad 2 iš mažiausių, apibendrinti juos, kitas 2 žemiausias, apibendrinti juos,

146
00:11:15,300 --> 00:11:19,390
kol aš visą medį.

147
00:11:19,390 --> 00:11:23,610
Net jei mes ir galėjome tai padaryti bet kuriuo atveju, kai mes susiduriame su procentais,

148
00:11:23,610 --> 00:11:27,760
tai reiškia, kad mes dalijant dalykų ir, susijusius su po kablelio, arba, o plūdės

149
00:11:27,760 --> 00:11:30,900
jei mes galvojame apie duomenų struktūrų galvos.

150
00:11:30,900 --> 00:11:32,540
Ką mes žinome apie plūdės?

151
00:11:32,540 --> 00:11:35,180
Kas yra dažna problema, kai mes susiduriame su plūdžių?

152
00:11:35,180 --> 00:11:38,600
[Studentas] Netiksliai aritmetika. >> Taip. Netikslumas.

153
00:11:38,600 --> 00:11:43,760
Dėl slankiojo kablelio netikslumo, šį pset, kad, kad mes pasirūpinsime, kad

154
00:11:43,760 --> 00:11:49,450
kad mes neturime prarasti bet kokią vertę, tada mes iš tikrųjų ketiname būti susijusios su skaičiavimo.

155
00:11:49,450 --> 00:11:54,880
Taigi, jei jūs galvoti apie Hafmano mazgas, jei pažvelgti atgal struktūros čia,

156
00:11:54,880 --> 00:12:01,740
jei peržvelgsite žaliųjų dažnį su juo susijusios

157
00:12:01,740 --> 00:12:08,760
taip pat atkreipia dėmesį į savo kairę mazgas, taip pat jos teisės mazgas.

158
00:12:08,760 --> 00:12:13,970
Ir tada raudona jų ten taip pat turi simbolį, susiję su jais.

159
00:12:13,970 --> 00:12:18,900
Mes neketiname pateikti atskirus tie, tėvų ir tada galutinių mazgų,

160
00:12:18,900 --> 00:12:23,680
mes vadiname kaip lapai, o tik tos, turės tik NULL verčių.

161
00:12:23,680 --> 00:12:31,050
Kiekvienam mazgas mes turime simbolį, simbolis, kad mazgas reiškia,

162
00:12:31,050 --> 00:12:40,490
tada dažnis taip pat rodyklė, kairėje vaikui, taip pat jo dešinėje vaikui.

163
00:12:40,490 --> 00:12:45,680
Lapai, kurie yra pačioje apačioje, taip pat turėtų mazgas patarimų

164
00:12:45,680 --> 00:12:49,550
jų kairėje, o dešinėje, bet ir nuo tos vertės nėra nukreipta į faktinius mazgų,

165
00:12:49,550 --> 00:12:53,970
koks būtų jų vertė? >> [Studentas] NULL. >> NULL. Tiksliai.

166
00:12:53,970 --> 00:12:58,430
Štai pavyzdys, kaip galima atstovauti dažnį plaustai,

167
00:12:58,430 --> 00:13:02,130
bet mes ketiname būti susijusios su sveikaisiais skaičiais,

168
00:13:02,130 --> 00:13:06,780
kad viskas, ką aš padariau, tai pakeisti duomenų tipą.

169
00:13:06,780 --> 00:13:09,700
>> Eikime šiek tiek daugiau sudėtingos pavyzdyje.

170
00:13:09,700 --> 00:13:13,360
Bet dabar, kad mes padarėme paprastų, tai tik tą patį procesą.

171
00:13:13,360 --> 00:13:20,290
Jums susirasti 2 žemiausias dažnius, apibendrinti dažnius

172
00:13:20,290 --> 00:13:22,450
ir kad savo patronuojančiai mazgas naują dažnių,

173
00:13:22,450 --> 00:13:29,310
kuris nurodo kairėje su 0 filialas ir teisė 1 filialas.

174
00:13:29,310 --> 00:13:34,200
Jei mes turime eilutę "Tai yra CS50," tada mes suskaičiuoti, kiek kartų yra t paminėta,

175
00:13:34,200 --> 00:13:38,420
h minėta, i, S, C, 5, 0.

176
00:13:38,420 --> 00:13:42,010
Tada, ką aš čia su raudona mazgų, aš ką tik pasodinti,

177
00:13:42,010 --> 00:13:48,530
Man sakė, kad aš ruošiuosi šiuos simbolius galiausiai mano medžio apačioje.

178
00:13:48,530 --> 00:13:51,740
Tie, kurie bus visi lapų.

179
00:13:51,740 --> 00:13:58,200
Tada, ką aš padariau, aš juos surūšiuoti pagal dažnį didėjančia tvarka,

180
00:13:58,200 --> 00:14:02,950
ir iš tikrųjų tai yra būdas, kad ji pset kodas

181
00:14:02,950 --> 00:14:07,550
ji rūšiuoja ją dažnį ir tada abėcėlę.

182
00:14:07,550 --> 00:14:13,870
Taigi ji turi numerius ir tada abėcėlės tvarka pagal dažnumo.

183
00:14:13,870 --> 00:14:18,520
Tada, ką daryčiau, norėčiau rasti 2 žemiausias. Štai 0 iki 5.

184
00:14:18,520 --> 00:14:22,390
Norėčiau apibendrinti juos, ir kad 2. Tada aš norėčiau tęsti, rasti kitą 2 žemiausias.

185
00:14:22,390 --> 00:14:26,100
Tai yra du 1s, ir tada tie tampa 2, taip pat.

186
00:14:26,100 --> 00:14:31,570
Dabar aš žinau, kad mano kitas žingsnis bus prisijungti prie mažiausią skaičių,

187
00:14:31,570 --> 00:14:41,380
T, 1 ir tada pasirinkti vieną iš mazgų, kad turi 2 periodiškumą.

188
00:14:41,380 --> 00:14:44,560
Taigi čia mes turime 3 variantų.

189
00:14:44,560 --> 00:14:47,980
Ką aš ruošiuosi daryti skaidrę tik vizualiai pertvarkyti juos už jus

190
00:14:47,980 --> 00:14:51,790
, kad jūs galite pamatyti, kaip aš ji yra kuriama.

191
00:14:51,790 --> 00:14:59,040
Kas kodą ir savo platinimo kodas ketina daryti būtų prisijungti prie T

192
00:14:59,040 --> 00:15:01,410
0 ir 5 mazgas.

193
00:15:01,410 --> 00:15:05,060
Taip, tada, kad sumos iki 3, ir tada mes tęsti šį procesą.

194
00:15:05,060 --> 00:15:08,660
2 ir 2 dabar yra žemiausias, taigi tada tie suma iki 4.

195
00:15:08,660 --> 00:15:12,560
Kiekvienas po kiek? Gerai.

196
00:15:12,560 --> 00:15:16,410
Tada po to mes turime 3 ir 3, kuri turi būti pridėta,

197
00:15:16,410 --> 00:15:21,650
todėl vėl aš funkcija gali naudotis tik taip, kad jūs galite pamatyti vizualiai, kad jis neturi gauti pernelyg nepatogus.

198
00:15:21,650 --> 00:15:25,740
Tada mes turime 6 ir tada mūsų galutinis žingsnis yra dabar, kad turime tik 2 mazgų

199
00:15:25,740 --> 00:15:30,440
mes apibendrinti, kad mūsų medžio šaknies, kuris yra 10.

200
00:15:30,440 --> 00:15:34,100
Ir skaičius 10 turi prasmę, nes kiekvienas mazgas atstovaujama

201
00:15:34,100 --> 00:15:40,750
jų vertė, jų dažnumą, kiek kartų jie pasirodė į eilutę,

202
00:15:40,750 --> 00:15:46,350
ir tada mes turime mūsų eilutę 5 simbolius, kad tai turi prasmę.

203
00:15:48,060 --> 00:15:52,320
Jei pažvelgsime, kaip mes iš tikrųjų užkoduoti tai,

204
00:15:52,320 --> 00:15:56,580
kaip ir tikėtasi, i ir s, kuri pasireiškia dažniausiai

205
00:15:56,580 --> 00:16:01,350
atstovauja mažiausiai bitų skaičius.

206
00:16:03,660 --> 00:16:05,660
>> Būkite atsargus čia.

207
00:16:05,660 --> 00:16:09,780
Huffman medžių atveju tiesų svarbu.

208
00:16:09,780 --> 00:16:13,670
Didžiąsias S kitoks nei mažosiomis s.

209
00:16:13,670 --> 00:16:21,260
Jei mes turėjome "Tai CS50" didžiosiomis raidėmis, tada mažosiomis ai rodomi tik du kartus,

210
00:16:21,260 --> 00:16:27,120
būtų mazgas su 2 kaip jos vertę, ir tada didžiąsias S būtų tik vieną kartą.

211
00:16:27,120 --> 00:16:33,440
Taip, tada medis pasikeistų struktūros, nes jūs iš tikrųjų turite papildomų lapų čia.

212
00:16:33,440 --> 00:16:36,900
Tačiau suma vis tiek būtų 10.

213
00:16:36,900 --> 00:16:39,570
Kad tai, ką mes iš tikrųjų bus paskambinus kontrolinė,

214
00:16:39,570 --> 00:16:44,060
visų grafų papildymas.

215
00:16:46,010 --> 00:16:50,990
>> Dabar, kad mes, kuriems Huffman medžius, mes galime pasinerti į Huff'n Puff, pset.

216
00:16:50,990 --> 00:16:52,900
Mes ketiname pradėti nuo klausimų skyriuje,

217
00:16:52,900 --> 00:16:57,990
ir tai vyksta jums pripratę su dvejetainiai medžiai ir kaip veikia aplink, kad:

218
00:16:57,990 --> 00:17:03,230
braižybos mazgai, kurti savo Typedef struct mazgas,

219
00:17:03,230 --> 00:17:07,230
ir pamatysite, kaip jūs galite įterpti į dvejetainis medis, vienas, kad yra rūšiuojami,

220
00:17:07,230 --> 00:17:09,050
važiuoja, ir dalykų, pavyzdžiui, kad.

221
00:17:09,050 --> 00:17:14,560
Kad žinios yra tikrai ketina padėti jums, kai jums pasinerti į Huff'n Puff dalis

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

223
00:17:19,150 --> 00:17:26,329
Standartinis leidimas į pset, jūsų užduotis yra įgyvendinti Puff,

224
00:17:26,329 --> 00:17:30,240
hacker versija jūsų užduotis yra įgyvendinti Huff.

225
00:17:30,240 --> 00:17:38,490
Tai, ką daro Huff jis užima tekstą, o tada jis paverčia jį į 0s ir 1s,

226
00:17:38,490 --> 00:17:41,990
taigi procesas, kad mes padarėme anksčiau, kur mes skaičiuojami dažniai

227
00:17:41,990 --> 00:17:50,970
ir tada padarė medį ir sakė: "Kaip aš galiu gauti T?"

228
00:17:50,970 --> 00:17:54,840
T atstovaujamos 100, dalykai kaip, kad

229
00:17:54,840 --> 00:17:58,860
ir tada Huff tekstą, o tada išėjimo, kad dvejetainis.

230
00:17:58,860 --> 00:18:04,920
, Bet taip pat dėl ​​to, kad mes žinome, kad norite leisti mūsų Pranešimo gavėjas

231
00:18:04,920 --> 00:18:11,790
atkurti tą patį medį, ji taip pat apima informaciją apie dažnių skaičiaus.

232
00:18:11,790 --> 00:18:17,980
Tada su Puff mes dvejetainis failas 0s ir 1s

233
00:18:17,980 --> 00:18:21,740
ir atsižvelgiant į apie dažnių informaciją.

234
00:18:21,740 --> 00:18:26,740
Verčiame visų tų 0s ir 1s atgal į pirminį pranešimą, kuris,

235
00:18:26,740 --> 00:18:29,350
todėl mes dekompresowania kad.

236
00:18:29,350 --> 00:18:36,450
Jei jūs darote Standard Edition, jums nereikės įgyvendinti Huff

237
00:18:36,450 --> 00:18:39,290
taip, tada galite tiesiog naudokite personalo įgyvendinimą Huff.

238
00:18:39,290 --> 00:18:42,080
Čia rasite instrukcijas apie tai, kaip padaryti, kad spec.

239
00:18:42,080 --> 00:18:48,780
Galite paleisti personalo įgyvendinimą Huff tam tikru tekstinį failą

240
00:18:48,780 --> 00:18:53,270
ir tada naudoti tą srovę, kaip jūsų indėlį į Puff.

241
00:18:53,270 --> 00:18:59,330
>> Kaip jau minėjau anksčiau, mes turime daug platinimo kodo šį vieną.

242
00:18:59,330 --> 00:19:01,810
Aš ruošiuosi pradėti vyksta per ją.

243
00:19:01,810 --> 00:19:04,400
Aš ruošiuosi išleisti didžiąją laiko dalį h failai

244
00:19:04,400 --> 00:19:07,660
nes C failus, nes mes turime h

245
00:19:07,660 --> 00:19:11,650
ir kad suteikia mums funkcijų prototipų,

246
00:19:11,650 --> 00:19:15,520
mes ne iki galo reikia tiksliai suprasti -

247
00:19:15,520 --> 00:19:20,280
Jei jūs nesuprantate, kas vyksta į C failus, tada nereikia nerimauti per daug,

248
00:19:20,280 --> 00:19:23,600
bet tikrai pabandyti pažvelgti, nes jis gali duoti keletą patarimų

249
00:19:23,600 --> 00:19:29,220
ir tai naudinga priprasti skaityti kitų žmonių kodą.

250
00:19:38,940 --> 00:19:48,270
>> Žiūri huffile.h, ji pareiškia pastabas, abstrakcijos sluoksnis Huffman-koduotų failų.

251
00:19:48,270 --> 00:20:01,660
Jei mes einame, mes matome, kad yra ne daugiau kaip 256 simbolių, kad mums gali prireikti kodus.

252
00:20:01,660 --> 00:20:05,480
Tai apima visus abėcėlės raides - didžiąsias ir mažąsias -

253
00:20:05,480 --> 00:20:08,250
ir tada, simboliai ir skaičiai, ir tt

254
00:20:08,250 --> 00:20:11,930
Tada čia mes turime Magiškas skaičius, kuriose Huffman koduotą failą.

255
00:20:11,930 --> 00:20:15,890
Per Hafmano kodą jie ketina turėti tam tikrą magišką skaičių

256
00:20:15,890 --> 00:20:18,560
susijęs su antraštę.

257
00:20:18,560 --> 00:20:21,110
Tai gali atrodyti tik atsitiktinai Magiškas skaičius,

258
00:20:21,110 --> 00:20:27,160
tačiau, jei jūs iš tikrųjų jį išversti į ASCII, tada ji iš tikrųjų yra išsamiai išdėstytos Huff.

259
00:20:27,160 --> 00:20:34,290
Čia mes turime Hafmano užkoduotą failą struct.

260
00:20:34,290 --> 00:20:39,670
Yra visų šių savybių, susijusių su Huff failą.

261
00:20:39,670 --> 00:20:47,080
Tada žemyn čia mes turime už Huff failo antraštę, todėl mes jį vadiname Huffeader

262
00:20:47,080 --> 00:20:50,810
, o ne pridedant papildomų h, nes skamba tas pats vistiek.

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

264
00:20:52,720 --> 00:20:57,790
Mes turime Magiškas skaičius, su juo susijusios.

265
00:20:57,790 --> 00:21:09,040
Jei tai tikrasis Huff failas, tai bus skaičius iki pirmiau, ši stebuklinga.

266
00:21:09,040 --> 00:21:14,720
Ir tada jis turės masyvą.

267
00:21:14,720 --> 00:21:18,750
Taigi, kiekvieno simbolio, kurių yra 256,

268
00:21:18,750 --> 00:21:24,760
tai važiuoju į sąrašą, ką iš šių simbolių dažnis yra per Huff failą.

269
00:21:24,760 --> 00:21:28,090
Ir galiausiai, turime už dažnių kontrolinė,

270
00:21:28,090 --> 00:21:32,160
kuris turėtų būti šiais dažniais suma.

271
00:21:32,160 --> 00:21:36,520
, Kad Huffeader.

272
00:21:36,520 --> 00:21:44,600
Tada mes turime tam tikras funkcijas, kad grįžti kitą tiek į Huff failą

273
00:21:44,600 --> 00:21:52,580
rašo, taip pat šiek tiek į Huff failą, ir tada ši funkcija čia, hfclose,

274
00:21:52,580 --> 00:21:54,650
kad iš tikrųjų uždaro Huff failą.

275
00:21:54,650 --> 00:21:57,290
Anksčiau, mes buvo susijusios su tiesiu tik fclose

276
00:21:57,290 --> 00:22:01,190
tačiau, kai jūs turite Huff failą, o ne jį fclosing

277
00:22:01,190 --> 00:22:06,080
tai, ką jūs iš tikrųjų ketinate daryti yra hfclose ir hfopen jį.

278
00:22:06,080 --> 00:22:13,220
Tie, kurie specifines funkcijas, kurios Huff failus, kad mes ketiname būti susijusios su.

279
00:22:13,220 --> 00:22:19,230
Tada čia mes skaitome į antraštę ir tada rašyti antraštę.

280
00:22:19,230 --> 00:22:25,700
>> Tiesiog skaitant failą h mes galime natūra gauti, ką Huff failas gali būti jausmą,

281
00:22:25,700 --> 00:22:32,480
kokie bruožai ji, be faktiškai vyksta į huffile.c

282
00:22:32,480 --> 00:22:36,750
, jei mes pasinerti bus šiek tiek sudėtingesnis.

283
00:22:36,750 --> 00:22:41,270
Jis turi visas bylos, I / O čia, susijusius su rodykles.

284
00:22:41,270 --> 00:22:48,010
Čia mes matome, kad, kai mes vadiname hfread, pavyzdžiui, jis vis dar susiduriame su fread.

285
00:22:48,010 --> 00:22:53,050
Mes ne gauti atsikratyti šių funkcijų visiškai, bet mes siunčiame būti pasirūpinta

286
00:22:53,050 --> 00:22:59,760
viduje Huff failą, o tai visi jos patikimumo.

287
00:22:59,760 --> 00:23:02,300
Galite jaustis laisvai nuskaityti per, jei esate smalsus

288
00:23:02,300 --> 00:23:08,410
ir išeina, ir žievelės sluoksnio atgal šiek tiek.

289
00:23:20,650 --> 00:23:24,060
>> Kitas failas, kad mes ketiname pažvelgti į tree.h.

290
00:23:24,060 --> 00:23:30,210
Prieš Walkthrough skaidres sakėme tikėtis Huffman mazgas

291
00:23:30,210 --> 00:23:32,960
Typedef struct mazgas.

292
00:23:32,960 --> 00:23:38,360
Mes tikimės, kad ji turi simbolį, dažnį ir tada 2 mazgas žvaigždes.

293
00:23:38,360 --> 00:23:41,870
Šiuo atveju tai, ką mes darome, yra tai iš esmės tas pats

294
00:23:41,870 --> 00:23:46,880
išskyrus vietoj mazgo mes ketiname juos vadinti medžiai.

295
00:23:48,790 --> 00:23:56,760
Mes turime funkciją, kuri, kai skambinate, kad medis ji grąžina jums medis žymeklį.

296
00:23:56,760 --> 00:24:03,450
Atgal, kad Speller, kai buvo padaryti naują mazgas

297
00:24:03,450 --> 00:24:11,410
jūs sakėte mazgas * naujas žodis = malloc (sizeof) ir dalykų, pavyzdžiui, kad.

298
00:24:11,410 --> 00:24:17,510
Iš esmės, mktree ketina būti susijusios su, kad už jus.

299
00:24:17,510 --> 00:24:20,990
Be to, kai norite pašalinti medį,

300
00:24:20,990 --> 00:24:24,810
kad iš esmės atlaisvinus medį, kai baigsite su juo,

301
00:24:24,810 --> 00:24:33,790
vietoj aiškiai paskambinus nemokamai, jūs iš tikrųjų tik ketinate naudoti šią funkciją rmtree

302
00:24:33,790 --> 00:24:40,360
kur jums perduoti žymiklį į tą medį, ir tada tree.c rūpinsis tai už jus.

303
00:24:40,360 --> 00:24:42,490
>> Mes žvelgiame į tree.c.

304
00:24:42,490 --> 00:24:47,240
Mes tikimės, kad tas pačias funkcijas išskyrus pamatyti įgyvendinimą, taip pat.

305
00:24:47,240 --> 00:24:57,720
Kaip ir tikėjomės, kai skambinate mktree mallocs medžio dydį į rodykle,

306
00:24:57,720 --> 00:25:03,190
inicijuoja visas reikšmes į nulinę vertę, todėl 0S ar nulls,

307
00:25:03,190 --> 00:25:08,280
ir tada grąžina žymiklį į tą medį, kad jūs tiesiog malloc'd jums.

308
00:25:08,280 --> 00:25:13,340
Čia, kai skambinate pašalinti medį ji pirmą kartą, įsitikinkite, kad jūs ne dvigubai atlaisvinti.

309
00:25:13,340 --> 00:25:18,320
Ji užtikrina, kad jūs iš tikrųjų turi medį, kurį norite pašalinti.

310
00:25:18,320 --> 00:25:23,330
Čia, nes medis taip pat savo vaikus,

311
00:25:23,330 --> 00:25:29,560
Kas tai yra rekursyviai ragina pašalinti medį kairėje medžio mazgo

312
00:25:29,560 --> 00:25:31,650
taip pat teisinga mazgas.

313
00:25:31,650 --> 00:25:37,790
Prieš tai išlaisvina tėvų, ji turi išlaisvinti vaikus, taip pat.

314
00:25:37,790 --> 00:25:42,770
Patronuojanti įmonė yra sukeičiami su šaknies.

315
00:25:42,770 --> 00:25:46,500
Pirmasis iš tėvų, todėl, pavyzdžiui, puikiai puikiai puikiai puikiai senelis

316
00:25:46,500 --> 00:25:52,130
ar močiutė medis, pirmiausia mes turime išlaisvinti lygiai pirmą kartą.

317
00:25:52,130 --> 00:25:58,490
Taigi feed į apačią, nemokamai tiems, ir tada grįžti, nemokama tiems, ir tt

318
00:26:00,400 --> 00:26:02,210
Taigi, kad medis.

319
00:26:02,210 --> 00:26:04,240
>> Dabar mes ieškome miške.

320
00:26:04,240 --> 00:26:09,860
Miškas yra, kur jūs įdėti savo Huffman medžių.

321
00:26:09,860 --> 00:26:12,910
Jis sako, kad mes ketiname turėti kažką vadinama sklypas

322
00:26:12,910 --> 00:26:22,320
kad yra žymiklį į medį, taip pat žymiklį į sklypo vadinamas kitą.

323
00:26:22,320 --> 00:26:28,480
Kokią struktūra daro tokią atrodyti?

324
00:26:29,870 --> 00:26:32,490
Tai tipo sako, kad ji ten.

325
00:26:34,640 --> 00:26:36,700
Teisė čia.

326
00:26:37,340 --> 00:26:39,170
Susijęs sąrašas.

327
00:26:39,170 --> 00:26:44,590
Mes matome, kad kai mes turime sklypą, kaip susijęs sklypų sąrašą.

328
00:26:44,590 --> 00:26:53,020
Miškas yra apibrėžiamas kaip susietą sklypų sąrašą,

329
00:26:53,020 --> 00:26:58,100
ir todėl miško struktūra, mes tiesiog teks rodyklę į mūsų pirmojo sklypo

330
00:26:58,100 --> 00:27:02,740
ir kad sklypas per medį ar veikiau nurodo į medį

331
00:27:02,740 --> 00:27:06,190
ir tada nurodo į kitą sklypą, taip toliau ir taip toliau.

332
00:27:06,190 --> 00:27:11,100
Į mišką mes vadiname mkforest.

333
00:27:11,100 --> 00:27:14,930
Tada mes turime keletą gana naudingų funkcijų.

334
00:27:14,930 --> 00:27:23,240
Mes turime pasirinkti, kai pereisite į mišką ir tada grąžina vertė yra medis *,

335
00:27:23,240 --> 00:27:25,210
rodyklė į medį.

336
00:27:25,210 --> 00:27:29,370
Ką pasiimti darys, tai bus eiti į mišką, kad Jūs nurodote,

337
00:27:29,370 --> 00:27:35,240
tada pašalinti medį su žemiausio dažnio ir nuo tos miško

338
00:27:35,240 --> 00:27:38,330
ir tada duoti jums žymiklį į tą medį.

339
00:27:38,330 --> 00:27:43,030
Kai skambinate pasiimti, medis nėra miške nebėra,

340
00:27:43,030 --> 00:27:48,550
bet grąžina vertė yra rodyklė į tą medį.

341
00:27:48,550 --> 00:27:50,730
Tada jūs turite gamyklą.

342
00:27:50,730 --> 00:27:57,420
Su sąlyga, kad jums perduoti žymiklį į medį, kuris turi ne-0 dažnį,

343
00:27:57,420 --> 00:28:04,040
kokia elektrinė bus padaryti tai užtruks mišką, medį, ir augalų, kad viduje miško medžių.

344
00:28:04,040 --> 00:28:06,370
Čia mes turime rmforest.

345
00:28:06,370 --> 00:28:11,480
Panašus pašalinti medį, kuris iš esmės nepanaudota visų mūsų medžių, mums,

346
00:28:11,480 --> 00:28:16,600
pašalinti mišką nemokamai viskas, esančius tame miške.

347
00:28:16,600 --> 00:28:24,890
>> Jei pažvelgsime į forest.c, mes tikimės pamatyti bent 1 rmtree komandą ten,

348
00:28:24,890 --> 00:28:30,090
nes, kad atlaisvintumėte atminties, tarp miškų, jei miško medžius,

349
00:28:30,090 --> 00:28:32,930
tada galiausiai jūs ketinate per pašalinti tuos medžius.

350
00:28:32,930 --> 00:28:41,020
Jei pažvelgsime į forest.c, mes turime mkforest, o tai, kaip mes tikimės.

351
00:28:41,020 --> 00:28:42,890
Mes malloc dalykų.

352
00:28:42,890 --> 00:28:51,740
Mes inicijuoti pirmąjį pripažinimo netekusiais miško sklypas, nes jis tuščias pradėti,

353
00:28:51,740 --> 00:29:05,940
tada mes matome pasirinkti, kuri grąžina į medį su mažiausiu svoriu, žemiausio dažnio,

354
00:29:05,940 --> 00:29:13,560
ir tada gauna atsikratyti tos konkrečios mazgo, kad atkreipia dėmesį į tą medį, o kitą,

355
00:29:13,560 --> 00:29:16,760
todėl reikia, kad iš miško susietą sąrašą.

356
00:29:16,760 --> 00:29:24,510
Ir tada čia mes turime augalas, kuris įterpia į susietą sąrašą medis.

357
00:29:24,510 --> 00:29:29,960
, Ką miškas tai gražiai saugo ją surūšiuoti mums.

358
00:29:29,960 --> 00:29:37,910
Ir galiausiai, turime rmforest ir, kaip tikimasi, turime rmtree pakvietė ten.

359
00:29:46,650 --> 00:29:55,440
>> Žiūri paskirstymo kodas iki šiol, huffile.c tikriausiai buvo bene sunkiausia suprasti,

360
00:29:55,440 --> 00:29:59,990
kadangi kitų failų patys buvo gana paprasta laikytis.

361
00:29:59,990 --> 00:30:03,090
Su mūsų žinias apie nurodymus ir susijusių sąrašų ir tokių,

362
00:30:03,090 --> 00:30:04,860
mes galėjome sekti gana gerai.

363
00:30:04,860 --> 00:30:10,500
Bet visi mes turime tikrai įsitikinti, kad mes visiškai suprantame, yra H failai

364
00:30:10,500 --> 00:30:15,840
nes jums reikia paskambinus šias funkcijas, susijusius su šiais grąžinti reikšmes,

365
00:30:15,840 --> 00:30:20,590
todėl įsitikinkite, kad jūs visiškai suprasti, kokių veiksmų bus atliekamas

366
00:30:20,590 --> 00:30:24,290
kai skambinate vieną iš šių funkcijų.

367
00:30:24,290 --> 00:30:33,020
Bet iš tikrųjų suprasti viduje ji yra ne visai būtina, nes mes turime tuos val failai.

368
00:30:35,170 --> 00:30:39,490
Mes turime 2 daugiau failų į kairę mūsų platinimo kode.

369
00:30:39,490 --> 00:30:41,640
>> Leiskite pažvelgti į sąvartyną.

370
00:30:41,640 --> 00:30:47,230
Sąvartynas savo komentarą čia trunka Huffman-suspaustą failą

371
00:30:47,230 --> 00:30:55,580
ir tada verčia ir išverčia visas jo turinys.

372
00:31:01,010 --> 00:31:04,260
Čia mes matome, kad jis skambina hfopen.

373
00:31:04,260 --> 00:31:10,770
Tai rūšies atvaizdį į failą * Įvesties = fopen,

374
00:31:10,770 --> 00:31:13,500
ir tada jums perduoti informacijos.

375
00:31:13,500 --> 00:31:18,240
Tai beveik identiški, išskyrus vietoj failą * jūs, einančios į Huffile;

376
00:31:18,240 --> 00:31:22,030
vietoj fopen jūs artimųjų hfopen.

377
00:31:22,030 --> 00:31:29,280
Čia mes skaitome, kurios antraštėje yra pirmasis, kuris panašus į, kaip mes skaitome, kurios antraštėje yra natūra

378
00:31:29,280 --> 00:31:33,580
rastrinio formato failą.

379
00:31:33,580 --> 00:31:38,000
Ką mes darome čia tikrina, siekdama išsiaiškinti, ar antraštės informaciją

380
00:31:38,000 --> 00:31:44,330
turi teisę Magiškas skaičius, kuris rodo, kad tai tikrasis Huff failą,

381
00:31:44,330 --> 00:31:53,610
tada visi iš tų patikrinimų, siekiant užtikrinti, kad byla, kad mes atidaryti yra tikrasis huffed failą, ar ne.

382
00:31:53,610 --> 00:32:05,330
Kas tai yra, ji išveda visų simbolių, kad mes galime pamatyti dažnius

383
00:32:05,330 --> 00:32:09,790
per terminalo į grafinę lentelėje.

384
00:32:09,790 --> 00:32:15,240
Ši dalis bus naudinga.

385
00:32:15,240 --> 00:32:24,680
Ji turi šiek tiek ir skamba šiek tiek šiek tiek į Variable Bit ir išspausdina jį.

386
00:32:28,220 --> 00:32:35,430
Taigi, jei aš skambinti į hth.bin sąvartynas, kuris yra huffing failą

387
00:32:35,430 --> 00:32:39,490
naudojant personalo tirpalas, aš norėčiau gauti.

388
00:32:39,490 --> 00:32:46,000
Jis išvedė iš šių simbolių ir tada pradėti dažnį, kuriuo jie pateikiami.

389
00:32:46,000 --> 00:32:51,180
Jei pažvelgsime, dauguma jų yra 0s išskyrus: H, pasirodo du kartus,

390
00:32:51,180 --> 00:32:54,820
ir tada T, kuris pasirodo kartą.

391
00:32:54,820 --> 00:33:07,860
Ir tada čia mes turime faktinį pranešimą, 0s ir 1s.

392
00:33:07,860 --> 00:33:15,450
Jei pažvelgsime į hth.txt, kuris yra turbūt originalus pranešimas, kad buvo huffed

393
00:33:15,450 --> 00:33:22,490
mes tikimės pamatyti kai SS ir TS ten.

394
00:33:22,490 --> 00:33:28,720
Konkrečiai, mes tikimės pamatyti tik 1 T ir 2 hs.

395
00:33:32,510 --> 00:33:37,440
Čia mes esame hth.txt. Jis iš tiesų yra HTH.

396
00:33:37,440 --> 00:33:41,270
Įtraukti į ten, nors mes negalime matyti, yra naujos eilutės simboliai.

397
00:33:41,270 --> 00:33:53,190
Huff failas hth.bin taip pat koduojamas naujos eilutės simboliai taip pat.

398
00:33:55,680 --> 00:34:01,330
Čia, nes mes žinome, kad pavedimas yra HTH, ir tada naują eilutę,

399
00:34:01,330 --> 00:34:07,340
matome, kad turbūt H atstovauja tik vieną 1

400
00:34:07,340 --> 00:34:17,120
ir tada T tikriausiai 01 ir tada kitas H 1, taip pat

401
00:34:17,120 --> 00:34:21,139
ir tada mes turime naujos eilutės nurodė du 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> Ir galiausiai, nes mes susiduriame su išsėtine c ir h failus,

404
00:34:31,600 --> 00:34:36,350
mes ketiname turėti gana sudėtingą argumentą kompiliatorių,

405
00:34:36,350 --> 00:34:40,460
ir todėl čia mes turime Makefile, kuri leidžia jums sąvartynas.

406
00:34:40,460 --> 00:34:47,070
Bet iš tikrųjų, jūs turite eiti apie tai savo puff.c bylą.

407
00:34:47,070 --> 00:34:54,330
Faktiškai neturi Makefile spręsti su priėmimo puff.c jums.

408
00:34:54,330 --> 00:34:59,310
Mes palikti, kad iki jums redaguoti Makefile.

409
00:34:59,310 --> 00:35:05,930
Kai įvedate komandą, kaip kad visi, pavyzdžiui, kad visi jie už jus.

410
00:35:05,930 --> 00:35:10,760
Nesivaržykite pažvelgti į Makefile pavyzdžių iš praeities pset

411
00:35:10,760 --> 00:35:17,400
taip pat vyksta ne šį vieną, kad pamatytumėte, kaip jums gali būti suteikta, kad jūsų Puff failą

412
00:35:17,400 --> 00:35:20,260
redaguodami šį Makefile.

413
00:35:20,260 --> 00:35:22,730
Štai apie tai mūsų platinimo kodas.

414
00:35:22,730 --> 00:35:28,380
>> , Kai mes Dotarłeś per tą, tai čia tik dar vienas priminimas

415
00:35:28,380 --> 00:35:30,980
apie tai, kaip mes ketiname būti susijusios su Huffman mazgų.

416
00:35:30,980 --> 00:35:35,400
Mes neketiname būti vadindamas juos mazgai nebėra, mes ketiname būti vadindami juos "medžiai

417
00:35:35,400 --> 00:35:39,260
kur mes einame atstovaus savo char simbolį,

418
00:35:39,260 --> 00:35:43,340
jų dažnumas, įvykių skaičius, su sveikojo skaičiaus.

419
00:35:43,340 --> 00:35:47,370
Mes naudojame, nes tai tiksliau nei plūdės.

420
00:35:47,370 --> 00:35:52,980
Ir tada mes turime kitą žymeklį į kairę vaikui, taip pat teisinga vaiko.

421
00:35:52,980 --> 00:35:59,630
Miško, kaip matėme, yra tik susieta sąrašas medžių.

422
00:35:59,630 --> 00:36:04,670
Galiausiai, kai mes sukurti mūsų Huff failą

423
00:36:04,670 --> 00:36:07,580
mes norime, kad mūsų miškas yra tik 1 medis -

424
00:36:07,580 --> 00:36:12,420
1 medis, 1 root su keliais vaikų.

425
00:36:12,420 --> 00:36:20,840
Anksčiau, kai mes buvome tik kad mūsų Huffman medžius,

426
00:36:20,840 --> 00:36:25,360
mes pradėjome pateikdamas visus mazgų ant mūsų ekrane

427
00:36:25,360 --> 00:36:27,790
ir sako: mes ketiname turėti šiuos mazgus,

428
00:36:27,790 --> 00:36:32,920
galiausiai jie bus lapai, ir tai yra jų simbolis, tai yra jų dažnis.

429
00:36:32,920 --> 00:36:42,070
Mūsų miškų, jei mes tiesiog turime 3 raides, kad 3 medžių miško.

430
00:36:42,070 --> 00:36:45,150
Ir tada kaip mes einame, kai mes pridėjome pirmąjį tėvų,

431
00:36:45,150 --> 00:36:48,080
mes padarėme 2 medžių mišką.

432
00:36:48,080 --> 00:36:54,930
Mes pašalinome 2 iš šių vaikų iš mūsų miškų ir tuomet jį pakeitė su patronuojančia mazgas

433
00:36:54,930 --> 00:36:58,820
, kurie turėjo tuos 2 mazgų kaip vaikai.

434
00:36:58,820 --> 00:37:05,600
Ir galiausiai, mūsų paskutinis žingsnis, kad mūsų pavyzdys su AS, BS, ir Cs

435
00:37:05,600 --> 00:37:08,030
būtų galima atlikti galutinį tėvų,

436
00:37:08,030 --> 00:37:13,190
ir taip, tada, kad būtų pasiekti mūsų bendrą skaičių medžių miške iki 1.

437
00:37:13,190 --> 00:37:18,140
Ar visi pamatysite, kaip jums pradėti su keliais savo miško medžių

438
00:37:18,140 --> 00:37:22,520
ir galų gale su 1? Gerai. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Ką mes turime daryti Puff?

440
00:37:28,110 --> 00:37:37,110
Tai, ką mes turime padaryti, yra užtikrinti, kad, kaip visada, jie suteikia mums teisę tipo įėjimo

441
00:37:37,110 --> 00:37:39,090
taip, kad mes iš tikrųjų gali paleisti programą.

442
00:37:39,090 --> 00:37:43,130
Šiuo atveju jie bus mums duoda po pirmojo komandų eilutės argumento

443
00:37:43,130 --> 00:37:53,440
2 daugiau: failas, kad mes norime išskleisti ir Išspausti Failo produkcija.

444
00:37:53,440 --> 00:38:00,410
Bet kai mes įsitikinkite, kad jie pereina mums reikiamu kiekiu vertybių,

445
00:38:00,410 --> 00:38:05,820
mes norime užtikrinti, kad įvesties Huff byla, ar ne.

446
00:38:05,820 --> 00:38:10,420
Ir tada, kai mes garantuojame, kad tai Huff failą, tada mes norime sukurti mūsų medelį,

447
00:38:10,420 --> 00:38:20,940
sukurti medį taip, kad jis atitinka medį, kad asmuo, kuris nusiuntė pranešimą pastatytas.

448
00:38:20,940 --> 00:38:25,840
Tada, kai mes sukurti medį, tada mes galime spręsti 0s ir 1s, kad jie išlaikė,

449
00:38:25,840 --> 00:38:29,590
sekti palei mūsų medžio, nes jis identiškas,

450
00:38:29,590 --> 00:38:33,510
ir tada parašyti šį pranešimą, interpretuoti bitai atgal į simbolių.

451
00:38:33,510 --> 00:38:35,880
Ir tada pabaigoje, nes mes susiduriame su rodyklės čia,

452
00:38:35,880 --> 00:38:38,110
mes norime įsitikinti,, kad mes neturime jokių Atminties nutekėjimas

453
00:38:38,110 --> 00:38:41,330
ir kad mes nemokamai viskas.

454
00:38:42,820 --> 00:38:46,430
>> Užtikrinti tinkamą naudojimą yra sena skrybėlę mums iki šiol.

455
00:38:46,430 --> 00:38:51,980
Mes priimti vieną iš įvesties duomenų, kurie bus Bylos pavadinimas sluoksniuotos,

456
00:38:51,980 --> 00:38:56,010
ir tada mes nurodyti produkciją,

457
00:38:56,010 --> 00:39:01,580
todėl pūsto produkcija, kuri bus tekstinis failas, failo pavadinimas.

458
00:39:03,680 --> 00:39:08,820
Štai naudojimas. Ir dabar mes norime užtikrinti,, kad įvesties huffed arba ne.

459
00:39:08,820 --> 00:39:16,420
Mintys atgal, ten buvo nieko platinimo kodą, kuri galėtų padėti mums

460
00:39:16,420 --> 00:39:21,570
suprasti, ar failas yra huffed, ar ne?

461
00:39:21,570 --> 00:39:26,910
Ten buvo informacija huffile.c apie Huffeader.

462
00:39:26,910 --> 00:39:33,430
Mes žinome, kad kiekvienas Huff failas turi Huffeader su juo susijusios su Magiškas skaičius

463
00:39:33,430 --> 00:39:37,240
taip pat kiekvieno simbolio dažnių masyvas

464
00:39:37,240 --> 00:39:39,570
taip pat kontrolinė.

465
00:39:39,570 --> 00:39:43,180
Mes žinome, kad, bet mes taip pat atkreipė žvilgtelėti dump.c

466
00:39:43,180 --> 00:39:49,120
, kurioje jis buvo skaityti į Huff failą.

467
00:39:49,120 --> 00:39:53,990
Ir taip padaryti, kad ji turėjo patikrinti, ar jis tikrai buvo huffed ar ne.

468
00:39:53,990 --> 00:40:03,380
Taigi, galbūt galėtume naudoti dump.c kaip struktūra mūsų puff.c.

469
00:40:03,380 --> 00:40:12,680
Grįžti į pset 4, kai mes turėjome, kad nukopijuotą RGB triviečiai failo copy.c

470
00:40:12,680 --> 00:40:14,860
ir mes aiškinama, kad Detektīvromāns ir dydį,

471
00:40:14,860 --> 00:40:20,390
panašiai, ką galite padaryti tiesiog paleisti kaip cp dump.c puff.c komandą

472
00:40:20,390 --> 00:40:23,600
naudotis kai kodo ten.

473
00:40:23,600 --> 00:40:28,210
Tačiau, tai nebus taip paprasta, proceso

474
00:40:28,210 --> 00:40:33,010
už vertimą savo dump.c į puff.c

475
00:40:33,010 --> 00:40:36,160
bet bent jau suteikia jums kažkur pradėti

476
00:40:36,160 --> 00:40:40,540
apie tai, kaip užtikrinti, kad įėjimas yra iš tikrųjų huffed ar ne

477
00:40:40,540 --> 00:40:43,240
taip pat keletą kitų dalykų.

478
00:40:45,930 --> 00:40:50,250
Mes turime užtikrinti, tinkamą naudojimą ir užtikrinti, kad įvesties huffed.

479
00:40:50,250 --> 00:40:53,570
Kiekvieną kartą, kai mes padarėme, kad mes padarėme mūsų tinkamą klaidų tikrinimas,

480
00:40:53,570 --> 00:41:01,520
taip grąžinimo ir mesti funkciją, jei kai gedimas atsiranda, jei yra problema.

481
00:41:01,520 --> 00:41:07,170
>> Dabar tai, ką mes norime padaryti, tai sukurti tikrą medį.

482
00:41:08,840 --> 00:41:12,640
Jei pažvelgsime miške, yra 2 pagrindinės funkcijos

483
00:41:12,640 --> 00:41:15,800
kad mes ketiname norite tapti labai gerai susipažinęs su.

484
00:41:15,800 --> 00:41:23,870
Būlio funkcija augalų, kad augalai ne-0 dažnis viduje mūsų miškų medžių.

485
00:41:23,870 --> 00:41:29,250
Ir todėl jums perduoti žymiklį į mišką ir rodyklė į medį.

486
00:41:32,530 --> 00:41:40,340
Greitas klausimas: Kiek miškai Jūs turėsite, kai kuriate Huffman medį?

487
00:41:44,210 --> 00:41:46,650
Mūsų miškas yra kaip mūsų drobės, tiesa?

488
00:41:46,650 --> 00:41:50,800
Taigi mes tik ketina turėti 1 mišką, bet mes ketiname turėti keletą medžių.

489
00:41:50,800 --> 00:41:57,590
Taigi prieš jus paraginti gamyklą, jūs tikriausiai ketinate norite, kad jūsų mišką.

490
00:41:57,590 --> 00:42:04,430
Yra komandos, kad jei pažvelgti į forest.h, kaip jūs galite padaryti su mišku.

491
00:42:04,430 --> 00:42:09,270
Galite pasodinti medį. Mes žinome, kaip tai padaryti.

492
00:42:09,270 --> 00:42:11,590
Ir tada taip pat galite pasirinkti medį iš miško,

493
00:42:11,590 --> 00:42:17,540
pašalinti medį su mažiausiu svoriu ir duoti jums žymeklį.

494
00:42:17,540 --> 00:42:23,090
Mintys atgal, kai mes darome pateiktuose pavyzdžiuose save,

495
00:42:23,090 --> 00:42:27,980
kai mes buvome piešimo jį, mes tiesiog nuorodas.

496
00:42:27,980 --> 00:42:31,680
Bet čia, o ne tiesiog pridedant ryšius,

497
00:42:31,680 --> 00:42:40,630
galvoti apie tai, kaip jūs pašalinti 2 šių mazgų ir tada pakeisti jį kitu.

498
00:42:40,630 --> 00:42:44,200
Pareikšti, kad skynimas ir sodinamosios

499
00:42:44,200 --> 00:42:48,840
jūs perkate 2 medžius ir tada sodinti kitą medį

500
00:42:48,840 --> 00:42:54,060
, kad turi tuos 2 medžius, pasirinktą kaip vaikai.

501
00:42:57,950 --> 00:43:05,280
Sukurti Huffman medį, galite perskaityti simbolių ir dažnius, kad būtų

502
00:43:05,280 --> 00:43:10,790
, nes Huffeader suteikia, kad jums,

503
00:43:10,790 --> 00:43:14,250
suteikia jums dažnių masyvas.

504
00:43:14,250 --> 00:43:19,660
Todėl jūs galite eiti į priekį ir tiesiog ignoruoti, nieko 0

505
00:43:19,660 --> 00:43:23,760
nes mes nenorime, 256 lapų ne jo pabaigoje.

506
00:43:23,760 --> 00:43:27,960
Mes tik norime lapai, kurie yra simbolių skaičių

507
00:43:27,960 --> 00:43:31,600
kad yra iš tikrųjų naudojami prie bylos medžiagos.

508
00:43:31,600 --> 00:43:37,590
Galite perskaityti šių simbolių, ir kiekviena iš šių simbolių, kurie ne-0 dažnius,

509
00:43:37,590 --> 00:43:40,440
kurie bus medžiai.

510
00:43:40,440 --> 00:43:45,990
, Ką galite padaryti, tai kiekvieną kartą, kai jūs skaitote ne-0 dažnių simboliu,

511
00:43:45,990 --> 00:43:50,660
galite pasodinti medį, kad miške.

512
00:43:50,660 --> 00:43:56,620
Kai jūs sodinti medžių miške, galite prisijungti prie šių medžių kaip broliai ir seserys,

513
00:43:56,620 --> 00:44:01,130
todėl grįžta sodinti ir skinti, kur jums pasirinkti 2 ir tada įmonės 1

514
00:44:01,130 --> 00:44:05,820
kur, kad 1, kad augalas yra iš 2 vaikus, pasirinktą patronuojanti.

515
00:44:05,820 --> 00:44:11,160
Taip, tada jūsų galutinis rezultatas bus vienas medis savo miško.

516
00:44:16,180 --> 00:44:18,170
Štai, kaip jums sukurti savo medį.

517
00:44:18,170 --> 00:44:21,850
>> Yra keletas dalykų, kurie gali suklysti čia

518
00:44:21,850 --> 00:44:26,580
nes mes susiduriame su naujus medžius ir sprendžiant su nurodymus ir panašių dalykų.

519
00:44:26,580 --> 00:44:30,450
Anksčiau, kai mes buvo susijusios su rodyklės,

520
00:44:30,450 --> 00:44:36,580
kai mes malloc'd mes norėjome įsitikinti, kad ji negrįžo mums NULL rodyklė vertę.

521
00:44:36,580 --> 00:44:42,770
Taigi, keliais etapais, šio proceso metu bus keletas atvejų

522
00:44:42,770 --> 00:44:45,920
kur yra jūsų programa gali žlugti.

523
00:44:45,920 --> 00:44:51,310
Ką jūs norite daryti yra jūs norite įsitikinti, kad jums tvarkyti šias klaidas,

524
00:44:51,310 --> 00:44:54,580
ir spec sako, elgtis su jais grakščiai,

525
00:44:54,580 --> 00:45:00,280
Taigi, kaip atsispausdinti žinutę vartotojui, pasakoja jiems, kodėl ši programa turi mesti

526
00:45:00,280 --> 00:45:03,050
ir skubiai mesti jį.

527
00:45:03,050 --> 00:45:09,490
Norėdami tai padaryti klaidų, nepamirškite, kad jūs norite check it

528
00:45:09,490 --> 00:45:12,160
kiekvieną kartą, kad galėtų būti gedimas.

529
00:45:12,160 --> 00:45:14,660
Kiekvieną kartą, kad jūs kuriate naują žymeklį

530
00:45:14,660 --> 00:45:17,040
jūs norite įsitikinti,, kad būtų sėkmingai.

531
00:45:17,040 --> 00:45:20,320
Prieš ką mes naudojamas padaryti, tai naują žymeklį ir malloc jį,

532
00:45:20,320 --> 00:45:22,380
ir tada mes patikrinti, ar, kad žymeklis yra NULL.

533
00:45:22,380 --> 00:45:25,670
Taigi, ten bus keletas atvejų, kai jūs galite tiesiog padaryti, kad,

534
00:45:25,670 --> 00:45:28,610
bet kartais jūs iš tikrųjų raginama funkciją

535
00:45:28,610 --> 00:45:33,100
ir per tą funkciją, kad vienas, kad daro mallocing.

536
00:45:33,100 --> 00:45:39,110
Tuo atveju, jei mes žiūrime atgal į kai kurias funkcijas, per kodą,

537
00:45:39,110 --> 00:45:42,260
kai kurie iš jų yra Būlio funkcijų.

538
00:45:42,260 --> 00:45:48,480
Abstrakčios atveju, jei mes turime Bulio funkcija vadinama foo

539
00:45:48,480 --> 00:45:54,580
iš esmės, mes galime manyti, kad to daryti visa, kas foo nėra

540
00:45:54,580 --> 00:45:57,210
, nes tai Būlio funkcijos, ji grąžina true arba false -

541
00:45:57,210 --> 00:46:01,300
tiesa, jei jis bus sėkmingas, false, jei ne.

542
00:46:01,300 --> 00:46:06,270
Taigi, mes norime patikrinti, ar gražinama reikšmė foo yra true arba false.

543
00:46:06,270 --> 00:46:10,400
Jei klaidingai, tai reiškia, kad mes ketiname norite spausdinti kažkokį pranešimą

544
00:46:10,400 --> 00:46:14,390
ir tada uždarykite programą.

545
00:46:14,390 --> 00:46:18,530
Ką mes norime padaryti, tai patikrinti grąžinimo vertę foo.

546
00:46:18,530 --> 00:46:23,310
Jei foo grąžina neteisingas, tada mes žinome, kad mes susidūrėme su tam tikrą klaidų

547
00:46:23,310 --> 00:46:25,110
ir mes turime mesti mūsų programą.

548
00:46:25,110 --> 00:46:35,600
Būdas tai padaryti yra būklė, kai faktinė pati funkcija yra Jūsų būklė.

549
00:46:35,600 --> 00:46:39,320
Pasakykite foo imasi x.

550
00:46:39,320 --> 00:46:43,390
Mes galime turėti kaip sąlyga, jei (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Iš esmės, tai reiškia, kad jei ne vykdyti foo pabaigoje jis grąžina true,

552
00:46:50,900 --> 00:46:57,390
tada mes galime tai daryti, nes funkcija turi įvertinti foo

553
00:46:57,390 --> 00:47:00,500
siekiant įvertinti visą sąlygą.

554
00:47:00,500 --> 00:47:06,500
Taip, tada tai, kaip jūs galite padaryti kažką, jei ši funkcija grąžina true ir yra sėkmingas.

555
00:47:06,500 --> 00:47:11,800
Bet kai esate klaidų tikrinimas, jūs tik norite išeiti, jei jūsų funkcija grąžina neteisingas.

556
00:47:11,800 --> 00:47:16,090
Ką galite padaryti tiesiog pridėkite == FALSE arba tiesiog pridėti sprogimo priešais jį

557
00:47:16,090 --> 00:47:21,010
ir tada jūs turite if (! foo).

558
00:47:21,010 --> 00:47:29,540
Per tą šios sąlygos kūną, jums reikės visų klaidų,

559
00:47:29,540 --> 00:47:36,940
taip patinka, "Nepavyko sukurti šį medį", o tada 1 ar kažką panašaus, kad grįžti.

560
00:47:36,940 --> 00:47:43,340
Kas, kad nėra, nors, yra tai, kad nors foo grįžo klaidingas -

561
00:47:43,340 --> 00:47:46,980
Pasakykite foo grąžina true.

562
00:47:46,980 --> 00:47:51,060
Tada jūs neturite skambinti foo vėl. Tai yra paplitusi klaidinga nuomonė.

563
00:47:51,060 --> 00:47:54,730
, Nes ji buvo savo būklę, tai jau įvertino,

564
00:47:54,730 --> 00:47:59,430
, kad jūs jau turite rezultatą, jei jūs naudojate medį ar kažką panašaus, kad

565
00:47:59,430 --> 00:48:01,840
ar augalų ar pasiimti ar kažką.

566
00:48:01,840 --> 00:48:07,460
Ji jau turi šią vertę. Tai jau įvykdytas.

567
00:48:07,460 --> 00:48:10,730
Todėl naudinga pasinaudoti Būlio funkcijas, su sąlyga,

568
00:48:10,730 --> 00:48:13,890
nes, ar jūs iš tikrųjų vykdyti kilpos kūną,

569
00:48:13,890 --> 00:48:18,030
ji vykdo šią funkciją vistiek.

570
00:48:22,070 --> 00:48:27,330
>> Mūsų antrasis paskutiniame žingsnyje Rašydami pranešimą į failą.

571
00:48:27,330 --> 00:48:33,070
Kai mes sukurti Huffman medį, tada raštu pranešimą į failą yra gana paprasta.

572
00:48:33,070 --> 00:48:39,260
Tai gana paprasta, dabar tiesiog atlikite 0s ir 1s.

573
00:48:39,260 --> 00:48:45,480
Ir taip mes žinome, kad pagal susitarimą Hafmano medžio 0s nurodyti paliko

574
00:48:45,480 --> 00:48:48,360
1s rodo į dešinę.

575
00:48:48,360 --> 00:48:53,540
Taigi tada, jei jūs skaityti po truputį, kiekvieną kartą, kad jūs gaunate 0

576
00:48:53,540 --> 00:48:59,100
, jums kairįjį filialą, ir tada kiekvieną kartą, kai jūs skaitote santykiu 1

577
00:48:59,100 --> 00:49:02,100
jūs ketinate laikytis tinkamą filialas.

578
00:49:02,100 --> 00:49:07,570
Ir tada jūs ketinate ir toliau, kol paspausite lapą

579
00:49:07,570 --> 00:49:11,550
nes lapai bus ne filialų pabaigoje.

580
00:49:11,550 --> 00:49:16,870
Kaip mes galime pasakyti, ar mes nukentėjo lapą, ar ne?

581
00:49:19,800 --> 00:49:21,690
Mes sakėme anksčiau.

582
00:49:21,690 --> 00:49:24,040
[Studentas] Jei rodykles yra NULL. >> Taip.

583
00:49:24,040 --> 00:49:32,220
Mes galime pasakyti, jei mes nukentėjo, jei rodykles į kairę ir į dešinę medžių lapų yra NULL.

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

585
00:49:34,110 --> 00:49:40,320
Mes žinome, kad mes norime skaityti po truputį į mūsų Huff failą.

586
00:49:43,870 --> 00:49:51,220
Kaip matėme prieš dump.c, ką jie padarė, jie skaityti po truputį į Huff failą

587
00:49:51,220 --> 00:49:54,560
ir tiesiog atspausdinti, ką tie bitai buvo.

588
00:49:54,560 --> 00:49:58,430
Mes neketiname daryti, kad. Mes ketinate daryti kažką, kad šiek tiek sudėtingesnis.

589
00:49:58,430 --> 00:50:03,620
Bet tai, ką mes galime padaryti, mes galime imtis šiek rašoma, kad kodo fragmentą, kuris.

590
00:50:03,620 --> 00:50:10,250
Čia mes turime sveikuoju skaičiumi, kuris išreiškia dabartines tiek, kad mes šiek tiek.

591
00:50:10,250 --> 00:50:15,520
Iteravimu visi bylos bitų rūpinasi, kol paspausite failo pabaigoje.

592
00:50:15,520 --> 00:50:21,270
Remiantis, kad tada jūs ketinate nori turėti tam tikrą Iterator natūra

593
00:50:21,270 --> 00:50:26,760
feed savo medį.

594
00:50:26,760 --> 00:50:31,460
Ir tada ar bitas yra 0 arba 1,

595
00:50:31,460 --> 00:50:36,920
jūs ketinate norite, arba judėti, kad Iterator į kairę arba perkelti jį į dešinę

596
00:50:36,920 --> 00:50:44,080
visą kelią, kol paspausite lapų, todėl visą kelią iki to mazgo, kad esate

597
00:50:44,080 --> 00:50:48,260
nenurodo, bet daugiau mazgų.

598
00:50:48,260 --> 00:50:54,300
Kodėl mes galime tai padaryti su Hafmano failas, o ne Morzės abėcėlė?

599
00:50:54,300 --> 00:50:56,610
Nes Morzės kodas yra šiek tiek neaiškumų.

600
00:50:56,610 --> 00:51:04,440
Gali būti, pavyzdžiui, O laukti, mes nukentėjo laišką pakeliui, tai gal tai yra mūsų laiškas,

601
00:51:04,440 --> 00:51:08,150
o jei mes ir toliau tik šiek tiek ilgiau, tada mes būtume nukentėjo kitą laišką.

602
00:51:08,150 --> 00:51:13,110
Bet, kad nesiruošia atsitikti Hafmano kodavimas,

603
00:51:13,110 --> 00:51:17,540
todėl mes galime būti tikri, kad vienintelis būdas, kad mes ketiname, kad pasiektų simbolį

604
00:51:17,540 --> 00:51:23,480
Šis mazgas kairę ir dešinę vaikai yra NULL.

605
00:51:28,280 --> 00:51:32,350
>> Galiausiai, mes norime išlaisvinti mūsų atmintyje.

606
00:51:32,350 --> 00:51:37,420
Mes norime, kad artimas Huff failo, kad mes buvo susijusios su

607
00:51:37,420 --> 00:51:41,940
, taip pat pašalinti iš mūsų miškų medžių.

608
00:51:41,940 --> 00:51:46,470
Remiantis savo įgyvendinimo, jūs tikriausiai ketinate norite skambinti pašalinti mišką

609
00:51:46,470 --> 00:51:49,780
o ne iš tikrųjų vyksta per visus medžių sau.

610
00:51:49,780 --> 00:51:53,430
Tačiau, jei jūs padarėte kokius nors laikinus medžius, jūs norite nemokamai, kad.

611
00:51:53,430 --> 00:51:59,060
Jūs žinote geriausiai savo kodą, kad jūs žinote, kur jūs skiriant atmintį.

612
00:51:59,060 --> 00:52:04,330
Ir todėl, jei jūs einate į, pradėti net kontroliuoti F'ing už malloc

613
00:52:04,330 --> 00:52:08,330
matyti, kai jūs malloc ir įsitikinkite, kad jums atlaisvinti visa tai

614
00:52:08,330 --> 00:52:10,190
bet tada tiesiog išgyvena savo kodą,

615
00:52:10,190 --> 00:52:14,260
suprasti, kur jūs galite skyrė atmintis.

616
00:52:14,260 --> 00:52:21,340
Paprastai galite tiesiog pasakyti "failo pabaigoje aš tiesiog ketinate pašalinti mišką savo miško,"

617
00:52:21,340 --> 00:52:23,850
todėl iš esmės aišku, kad atmintis, nemokama, kad

618
00:52:23,850 --> 00:52:28,310
"Ir tada aš taip pat ketina uždaryti failą ir tada mano programa ketina mesti".

619
00:52:28,310 --> 00:52:33,810
Bet tai, kad tik laiko, kad jūsų programa baigia darbą?

620
00:52:33,810 --> 00:52:37,880
Ne, nes kartais gali buvo klaida, kad atsitiko.

621
00:52:37,880 --> 00:52:42,080
Gal mes negalėjo atidaryti failą arba mes negalėjome padaryti kitą medį

622
00:52:42,080 --> 00:52:49,340
arba įvyko kažkoks klaidų atminties paskirstymo procese ir todėl jis grįžo NULL.

623
00:52:49,340 --> 00:52:56,710
Įvyko klaida, ir tada mes sugrįžo ir mesti.

624
00:52:56,710 --> 00:53:02,040
Taip, tada jūs norite įsitikinti, kad bet koks galimas laikas, kad jūsų programa gali mesti,

625
00:53:02,040 --> 00:53:06,980
norite išlaisvinti visus jūsų atminties.

626
00:53:06,980 --> 00:53:13,370
Tai ne tik bus ne galo pagrindinės funkcijos, kad jūs mesti savo kodą.

627
00:53:13,370 --> 00:53:20,780
Norite atrodyti, kad kiekvienu atveju, kad jūsų kodas potencialiai gali grįžti anksti

628
00:53:20,780 --> 00:53:25,070
ir tada kokia atminties prasmę.

629
00:53:25,070 --> 00:53:30,830
Pasakykite, vadino mišką ir grįžo klaidinga.

630
00:53:30,830 --> 00:53:34,230
Tada jums tikriausiai nereikia ištrinti savo mišką

631
00:53:34,230 --> 00:53:37,080
nes jūs neturite mišką.

632
00:53:37,080 --> 00:53:42,130
Tačiau kiekviename kode taško, kur jūs galite grįžti anksti

633
00:53:42,130 --> 00:53:46,160
jūs norite įsitikinti, kad jums nemokamai bet kokį galimą atmintį.

634
00:53:46,160 --> 00:53:50,020
>> Taigi, kai mes susiduriame su atlaisvinti atmintį ir galimiems nutekėjimams,

635
00:53:50,020 --> 00:53:55,440
mes norime ne tik naudoti savo sprendimą ir mūsų logika

636
00:53:55,440 --> 00:54:01,850
bet taip pat naudoti Valgrind nustatyti, ar mes išlaisvino visus mūsų atmintyje tinkamai, ar ne.

637
00:54:01,850 --> 00:54:09,460
Jūs galite paleisti Valgrind ant Puff ir tada taip pat turite perduoti jį

638
00:54:09,460 --> 00:54:14,020
teisę komandinės eilutės argumentai Valgrind.

639
00:54:14,020 --> 00:54:18,100
Galite paleisti, tačiau produkcija yra šiek tiek paslaptingas.

640
00:54:18,100 --> 00:54:21,630
Mes Dotarłeś šiek tiek priprasti prie jo su Speller, bet mes vis dar reikia šiek tiek daugiau pagalbos,

641
00:54:21,630 --> 00:54:26,450
taip, tada paleisti jį su keletą vėliavomis, pavyzdžiui, nuotėkio patikrinti = visas,

642
00:54:26,450 --> 00:54:32,040
kad tikriausiai duoti mums šiek tiek daugiau naudingos Valgrind išvesties.

643
00:54:32,040 --> 00:54:39,040
>> Tada dar vienas naudingas patarimas, kai jūs derinti skirt komanda.

644
00:54:39,040 --> 00:54:48,520
Galite prieiti prie darbuotojų įgyvendinimą Huff, paleisti, kad tekstiniame faile,

645
00:54:48,520 --> 00:54:55,400
ir tada išvesti jį į dvejetainis failas, dvejetainis Huff failo, turi būti konkretus.

646
00:54:55,400 --> 00:54:59,440
Tada, jei jūs naudojate savo inhaliacijas tą dvejetainis failas,

647
00:54:59,440 --> 00:55:03,950
tada idealiai, jūsų sklidusiam tekstinis failas bus identiškas

648
00:55:03,950 --> 00:55:08,200
į pradinį vienas, kad jūs išlaikėte.

649
00:55:08,200 --> 00:55:15,150
Čia aš naudojant hth.txt kaip, pavyzdžiui, ir tai yra vienas kalbėjo apie savo spec.

650
00:55:15,150 --> 00:55:21,040
Kad pažodžiui tik HTH, ir tada naują eilutę.

651
00:55:21,040 --> 00:55:30,970
Bet tikrai jaustis laisvi ir jūs tikrai skatinami naudoti ilgesnius pavyzdžius

652
00:55:30,970 --> 00:55:32,620
jūsų tekstinį failą.

653
00:55:32,620 --> 00:55:38,110
>> Jūs netgi galite imtis ne gal suspaudžiant fotografiją ir tada dekompresowania

654
00:55:38,110 --> 00:55:41,600
kai kurių failų, kuriuos, pavyzdžiui, "Karas ir taika naudojamų Speller

655
00:55:41,600 --> 00:55:46,710
arba Jane Austen ar kažkas panašaus - kad būtų tipo kietas - Austin Powers,

656
00:55:46,710 --> 00:55:51,880
natūra, susijusius su didesniais failus, nes mes ne ateiti į ją

657
00:55:51,880 --> 00:55:55,590
jei mes naudojome kitą įrankį, ls-l.

658
00:55:55,590 --> 00:56:01,150
Esame įpratę prie LS, kuris iš esmės nurodytos visos mūsų einamojo katalogo turinį.

659
00:56:01,150 --> 00:56:07,860
Einančios vėliavos-l, iš tikrųjų rodo šių failų dydį.

660
00:56:07,860 --> 00:56:12,690
Jeigu jūs einate per pset spec, ji iš tikrųjų walks jus per sukurti dvejetainis failas,

661
00:56:12,690 --> 00:56:16,590
huffing jį, ir pamatysite, kad labai mažų failų

662
00:56:16,590 --> 00:56:23,910
vietos išlaidos suspaudimą, ir versti visus šios informacijos

663
00:56:23,910 --> 00:56:26,980
visų dažnių ir dalykų, pavyzdžiui, kad didesnė faktinė nauda

664
00:56:26,980 --> 00:56:30,000
suspaudžiant failą į pirmąją vietą.

665
00:56:30,000 --> 00:56:37,450
Bet jei jūs naudojate jį vienur ilgiau tekstinius failus, tada jūs galite pamatyti, kad jūs pradėtumėte gauti tam tikros naudos,

666
00:56:37,450 --> 00:56:40,930
suspaudžiant tuos failus.

667
00:56:40,930 --> 00:56:46,210
>> Ir pagaliau, mes turime senas drauguži gdb, kuris yra tikrai ketina praversti.

668
00:56:48,360 --> 00:56:55,320
>> Ar mes turime klausimų Huff medžių arba procesas, galbūt priimant medžius

669
00:56:55,320 --> 00:56:58,590
arba bet kokius kitus klausimus apie Huff'n Puff?

670
00:57:00,680 --> 00:57:02,570
Gerai. Zatrzymam aplink šiek tiek.

671
00:57:02,570 --> 00:57:06,570
>> Ačiū visiems. Tai buvo Walkthrough 6. Ir geros kloties.

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