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

2
00:00:02,210 --> 00:00:04,810
[Zamyla Chan - Hārvarda]

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

4
00:00:07,240 --> 00:00:12,180
>> Sveiki, visiem, un laipni 6 Walkthrough: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
Jo Huff'n Puff, ko mēs darām, ir būs darīšana ar Huffman saspiestu failu

6
00:00:17,440 --> 00:00:20,740
un tad kūpinot to atpakaļ uz augšu, tāpēc decompressing tā,

7
00:00:20,740 --> 00:00:25,810
lai mēs varētu tulkot no 0s un 1s ka lietotājs sūta mums

8
00:00:25,810 --> 00:00:30,660
un pārvērst to atpakaļ sākotnējā teksta.

9
00:00:30,660 --> 00:00:34,360
PSET 6 būs diezgan vēss, jo jūs gatavojas redzēt dažus no instrumentiem

10
00:00:34,360 --> 00:00:41,730
ka tu lieto 4 PSET un PSET 5 un veida apvienojot tos 1 diezgan veikls koncepciju

11
00:00:41,730 --> 00:00:43,830
kad jūs domāt par to.

12
00:00:43,830 --> 00:00:50,110
>> Arī varbūt, 4 PSET un 5 bija vislielākās grūtības psets ka mums bija piedāvāt.

13
00:00:50,110 --> 00:00:53,950
Tātad no šī brīža, mums ir šis vēl 1 PSET C,

14
00:00:53,950 --> 00:00:56,480
un tad pēc tam mēs esam uz web programmēšanu.

15
00:00:56,480 --> 00:01:02,310
Tātad apsveicu sevi, lai iegūtu pār toughest kupris in CS50.

16
00:01:03,630 --> 00:01:09,760
>> Pārvietojas on Huff'n dvesma, mūsu Toolbox šo PSET gribam būt Huffman koki,

17
00:01:09,760 --> 00:01:14,700
lai izprastu ne tikai kā binārā koki darbu, bet arī īpaši Huffman kokus,

18
00:01:14,700 --> 00:01:16,240
kā viņi uzbūvēti.

19
00:01:16,240 --> 00:01:20,210
Un tad mēs ejam, lai ir daudz sadales kodu šajā PSET,

20
00:01:20,210 --> 00:01:22,480
un mēs būsim redzēt, ka faktiski daži kodu

21
00:01:22,480 --> 00:01:24,670
mēs varētu nebūt spējīgs pilnībā saprast vēl,

22
00:01:24,670 --> 00:01:30,080
un tāpēc tie būs. c failus, bet tad to pavadošajiem. h faili

23
00:01:30,080 --> 00:01:34,300
dos mums ir pietiekami daudz izpratnes, ka mums ir nepieciešams, lai mēs zinām, kā šīs funkcijas darbojas

24
00:01:34,300 --> 00:01:38,100
vai vismaz to, ko viņi ir paredzēts darīt - viņu ieejas un izejas -

25
00:01:38,100 --> 00:01:40,760
pat ja mēs nezinām, kas notiek melnajā kastē

26
00:01:40,760 --> 00:01:44,090
vai nesaprot to, kas notiek melnajā kastē laikā.

27
00:01:44,090 --> 00:01:49,400
Un tad beidzot, kā ierasts, mums ir darīšana ar jauniem datu struktūras,

28
00:01:49,400 --> 00:01:51,840
īpašu veidu mezglu, kas norāda uz dažām lietām,

29
00:01:51,840 --> 00:01:56,080
un tāpēc šeit kam pildspalvu un papīru ne tikai projektēšanas procesā

30
00:01:56,080 --> 00:01:58,470
un, kad jūs mēģināt izdomāt, kā jūsu PSET vajadzētu strādāt

31
00:01:58,470 --> 00:02:00,520
bet arī laikā debugging.

32
00:02:00,520 --> 00:02:06,140
Jūs varat būt GDB līdzās savu pildspalvu un papīru, kamēr jūs ņemtu nosaka kādi vērtības ir,

33
00:02:06,140 --> 00:02:09,320
kur jūsu bultas ir norādot, un lietas, piemēram, ka.

34
00:02:09,320 --> 00:02:13,720
>> Vispirms pieņemsim apskatīt Huffman kokiem.

35
00:02:13,720 --> 00:02:19,600
Huffman koki ir binārā koki, kas nozīmē, ka katrs mezgls ir tikai 2 bērni.

36
00:02:19,600 --> 00:02:24,870
Jo Huffman kokiem īpašība ir, ka biežākie vērtības

37
00:02:24,870 --> 00:02:27,140
pārstāv vismazāk bitiem.

38
00:02:27,140 --> 00:02:32,690
Mēs redzējām lekciju piemēri Morzes kodu, kas veida konsolidētā dažus burtus.

39
00:02:32,690 --> 00:02:38,030
Ja jūs mēģināt tulkot A vai E, piemēram,

40
00:02:38,030 --> 00:02:43,940
Jūs esat tulkojot ka bieži, tāpēc tā vietā, lai izmantotu pilnu komplektu bitiem

41
00:02:43,940 --> 00:02:48,640
piešķirams šajā parasto datu tipu, jūs saspiest to uz leju līdz mazāk,

42
00:02:48,640 --> 00:02:53,730
un tad šie burti, kas ir pārstāvētas retāk tiek pārstāvētas ar garākiem bitiem

43
00:02:53,730 --> 00:02:59,840
jo jūs varat atļauties, ka tad, kad jūs nosver frekvences, kas šiem burtiem.

44
00:02:59,840 --> 00:03:03,020
Mums ir tāda pati ideja šeit Huffman kokiem

45
00:03:03,020 --> 00:03:12,360
kur mēs veidojam ķēdi, veida ceļu, lai nokļūtu noteiktu simbolu.

46
00:03:12,360 --> 00:03:14,470
Un tad rakstzīmes, kas ir visvairāk biežumu

47
00:03:14,470 --> 00:03:17,940
gatavojas pārstāv pēc iespējas mazākiem bitiem.

48
00:03:17,940 --> 00:03:22,020
>> Tā, ka jums izveidot Huffman koku

49
00:03:22,020 --> 00:03:27,430
ir, ievietojot visas rakstzīmes, kas parādās tekstā

50
00:03:27,430 --> 00:03:30,630
un aprēķinot to biežumu, cik bieži tie parādās.

51
00:03:30,630 --> 00:03:33,880
Tas varētu būt vai nu skaits, cik reizes šie burti parādīsies

52
00:03:33,880 --> 00:03:40,270
vai varbūt procents no visiem personāžiem, cik daudz katrs parādās.

53
00:03:40,270 --> 00:03:44,270
Un tā, ko jūs darāt, ir, kad jums ir visas šīs nosprauda,

54
00:03:44,270 --> 00:03:49,060
tad jūs meklēt par 2 zemāko frekvenču un pēc tam pievienoties tos kā vecvecākus

55
00:03:49,060 --> 00:03:55,660
kur tad mātes mezglā ir frekvenci, kas ir summa ir 2 bērni.

56
00:03:55,660 --> 00:04:00,870
Un tad tu pēc vienošanās teikt, ka kreisais mezglā,

57
00:04:00,870 --> 00:04:03,770
Jums seko, ka, sekojot 0 filiāli,

58
00:04:03,770 --> 00:04:08,140
un tad rightmost mezgls ir 1 filiāle.

59
00:04:08,140 --> 00:04:16,040
Kā mēs redzējām Morzes kodu, viens gotcha bija, ka, ja jums bija tikai pīkstienu un pīkstiens

60
00:04:16,040 --> 00:04:18,120
tas bija neskaidrs.

61
00:04:18,120 --> 00:04:22,430
Tas varētu būt vai nu 1 burts vai tas varētu būt secība 2 burtiem.

62
00:04:22,430 --> 00:04:27,790
Un tā, kādi Huffman koki dara, ir tāpēc, ka pēc būtības rakstzīmes

63
00:04:27,790 --> 00:04:34,140
vai mūsu galīgās faktiskās rakstzīmes ir pēdējais mezgli par filiāles -

64
00:04:34,140 --> 00:04:39,300
mēs uz tām, lapas - pamatojoties uz, ka nevar būt jebkura neskaidrība

65
00:04:39,300 --> 00:04:45,160
Runājot par kuru vēstulē jūs mēģināt kodēt ar virkni bitu

66
00:04:45,160 --> 00:04:50,670
jo nekur gar biti, kas pārstāv 1 burts

67
00:04:50,670 --> 00:04:55,960
Jūs sastopas citu veselu vēstuli, un tur nebūs neskaidrības tur.

68
00:04:55,960 --> 00:04:58,430
Bet mēs iedziļināties piemēriem, ka jūs guys faktiski var redzēt, ka

69
00:04:58,430 --> 00:05:02,120
vietā mums tikai stāsta, ka tā ir taisnība.

70
00:05:02,120 --> 00:05:06,390
>> Apskatīsim vienkāršu piemēru Huffman koku.

71
00:05:06,390 --> 00:05:09,380
Man ir virkne šeit, ka ir 12 rakstzīmes.

72
00:05:09,380 --> 00:05:14,010
Man ir 4 Kā, 6 BS, un CS 2.

73
00:05:14,010 --> 00:05:17,270
Mans pirmais solis būtu rēķināties.

74
00:05:17,270 --> 00:05:20,760
Cik reizes nav parādās? Šķiet 4 reizes virknē.

75
00:05:20,760 --> 00:05:25,060
B šķiet 6 reizes, un C šķiet 2 reizes.

76
00:05:25,060 --> 00:05:28,970
Protams, es esmu gatavojas teikt, es esmu, izmantojot B visbiežāk,

77
00:05:28,970 --> 00:05:35,970
tāpēc es gribu, lai pārstāvētu B ar vismazāko skaitu biti, vismazāk skaits 0s un 1s.

78
00:05:35,970 --> 00:05:42,600
Un tad es esmu arī gatavojas sagaidīt C pieprasīt lielāko summu 0s un 1s, kā arī.

79
00:05:42,600 --> 00:05:48,550
Pirmais, ko es darīju šeit es novieto tos augošā secībā pēc biežuma.

80
00:05:48,550 --> 00:05:52,710
Mēs redzam, ka C un, tie ir mūsu 2 zemākās frekvences.

81
00:05:52,710 --> 00:06:00,290
Mēs izveidot mātes mezglā, un ka mātes mezglā nav vēstuli saistīts ar to,

82
00:06:00,290 --> 00:06:05,070
bet tas ir frekvence, kas ir summa.

83
00:06:05,070 --> 00:06:08,780
Summa kļūst 2 +4, kas ir 6.

84
00:06:08,780 --> 00:06:10,800
Tad mēs sekojam kreiso filiāli.

85
00:06:10,800 --> 00:06:14,970
Ja mums bija, ka 6 mezglā, tad mēs varētu sekot 0 nokļūt līdz C

86
00:06:14,970 --> 00:06:17,450
un tad 1, lai saņemtu A.

87
00:06:17,450 --> 00:06:20,300
Tāpēc tagad mums ir 2 punktiem.

88
00:06:20,300 --> 00:06:23,920
Mums ir vērtība 6 un tad mums ir arī citu mezglu ar vērtību 6.

89
00:06:23,920 --> 00:06:28,550
Un tā tie 2 ir ne tikai par 2 zemākā, bet arī tikai 2, kas ir pa kreisi,

90
00:06:28,550 --> 00:06:33,820
tāpēc mēs pievienoties tiem cita vecākiem, ar summu par 12.

91
00:06:33,820 --> 00:06:36,300
Tātad šeit mums ir mūsu Huffman koks

92
00:06:36,300 --> 00:06:40,020
kur iegūt uz B, kas būtu tikai būt bit 1

93
00:06:40,020 --> 00:06:45,430
un tad nokļūt līdz mums būtu 01 un tad C kam 00.

94
00:06:45,430 --> 00:06:51,300
Tātad šeit mēs redzam, ka būtībā mēs esam pārstāv šos chars ar 1 vai 2 bitiem

95
00:06:51,300 --> 00:06:55,160
kur B, kā tika gaidīts, ir vismazāk.

96
00:06:55,160 --> 00:07:01,730
Un tad mums bija gaidāms C ir visvairāk, bet jo tas ir tik mazs Huffman koks,

97
00:07:01,730 --> 00:07:06,020
tad ir pārstāvēta arī ar 2 bitu, nevis kaut kur pa vidu.

98
00:07:07,820 --> 00:07:11,070
>> Tikai, lai iet pa citu vienkāršu piemēru no Huffman koku,

99
00:07:11,070 --> 00:07:19,570
saka jums ir virkne "Sveiki".

100
00:07:19,570 --> 00:07:25,360
Kas jums ir vispirms jums teiktu, cik reizes tas H parādās šo?

101
00:07:25,360 --> 00:07:34,200
H parādās vienreiz un pēc tam e parādās vienreiz un tad mums ir l parādās divreiz

102
00:07:34,200 --> 00:07:36,580
un o parādās vienreiz.

103
00:07:36,580 --> 00:07:44,310
Un tad mēs sagaidām, ko vēstule pārstāv vismaz bitu skaitu?

104
00:07:44,310 --> 00:07:47,450
[Students] l. >> L. Yeah. l ir taisnība.

105
00:07:47,450 --> 00:07:50,730
Mēs sagaidām l pārstāv vismaz bitu skaits

106
00:07:50,730 --> 00:07:55,890
jo l izmanto visvairāk virknē "Sveiki".

107
00:07:55,890 --> 00:08:04,280
Ko es esmu gatavojas darīt tagad, ir izdarīt šos mezglus.

108
00:08:04,280 --> 00:08:15,580
Man ir 1, kas ir H, un pēc tam vēl 1, kas ir E, un tad 1, kas o -

109
00:08:15,580 --> 00:08:23,410
šobrīd es esmu savešanu kārtībā - un tad 2, kas ir l.

110
00:08:23,410 --> 00:08:32,799
Tad es saku tā, ka es veidot Huffman koks ir atrast 2 punktiem ar mazāko frekvencēm

111
00:08:32,799 --> 00:08:38,010
un padarīt tos vecvecākus, izveidojot mātes mezglā.

112
00:08:38,010 --> 00:08:41,850
Te mums ir 3 mezgli ar zemāko frekvenci. Viņi visi 1.

113
00:08:41,850 --> 00:08:50,620
Tātad šeit mēs izvēlēties vienu mēs ejam, lai savienotu pirmās.

114
00:08:50,620 --> 00:08:54,850
Pieņemsim, ka es izvēlētos H un e.

115
00:08:54,850 --> 00:09:01,150
Summa 1 + 1 ir 2, bet tas mezgls nav vēstuli saistīti ar to.

116
00:09:01,150 --> 00:09:04,440
Tas tikai tur vērtību.

117
00:09:04,440 --> 00:09:10,950
Tagad mēs skatāmies nākamo 2 zemāko frekvences.

118
00:09:10,950 --> 00:09:15,590
Tas ir 2 un 1. Tas varētu būt vai nu no 2 tiem, bet es esmu gatavojas izvēlēties šo vienu.

119
00:09:15,590 --> 00:09:18,800
Summa ir 3.

120
00:09:18,800 --> 00:09:26,410
Un tad beidzot, man ir tikai 2 Kreisais, lai tad kļūst 5.

121
00:09:26,410 --> 00:09:32,010
Tad šeit, kā gaidīts, ja es aizpildīt kodējumu, ka,

122
00:09:32,010 --> 00:09:37,480
1s vienmēr labi filiāle un 0s ir atstāj vienu.

123
00:09:37,480 --> 00:09:45,880
Tad mums ir l pārstāv tikai 1 bitu un tad o ar 2

124
00:09:45,880 --> 00:09:52,360
un tad ar 2 e tad H krīt līdz 3 bitiem.

125
00:09:52,360 --> 00:09:59,750
Tātad jūs varat nosūtīt šo ziņojumu "Hello", nevis faktiski izmantojot rakstzīmes

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

127
00:10:02,760 --> 00:10:07,910
Tomēr atcerieties, ka vairākos gadījumos mums bija attiecības ar mūsu frekvenci.

128
00:10:07,910 --> 00:10:11,900
Mēs varētu būt vai nu pievienojies H un o 1. varbūt.

129
00:10:11,900 --> 00:10:15,730
Vai tad vēlāk, kad mums bija l pārstāv 2

130
00:10:15,730 --> 00:10:19,410
kā arī pievienojās vienu, veido ar 2, mēs varētu būt saistīti vai nu vienu.

131
00:10:19,410 --> 00:10:23,630
>> Un tad, kad jūs sūtīt 0s un 1s, kas faktiski negarantē

132
00:10:23,630 --> 00:10:27,090
ka saņēmējs var pilnībā lasīt jūsu ziņu labi pie nūja

133
00:10:27,090 --> 00:10:30,490
jo viņi varētu nezināt, ko lēmums jums veikts.

134
00:10:30,490 --> 00:10:34,920
Tātad, ja mums ir darīšana ar Huffman kompresiju,

135
00:10:34,920 --> 00:10:40,090
kaut mums ir pateikt saņēmējs mūsu vēstījumu, kā mēs nolēmām -

136
00:10:40,090 --> 00:10:43,470
Viņiem jāzina sava veida papildu informāciju

137
00:10:43,470 --> 00:10:46,580
papildus saspiestā ziņu.

138
00:10:46,580 --> 00:10:51,490
Viņiem ir nepieciešams saprast, ko koks patiesībā izskatās,

139
00:10:51,490 --> 00:10:55,450
kā mēs faktiski veica šos lēmumus.

140
00:10:55,450 --> 00:10:59,100
>> Šeit mēs tikai dara piemērus, pamatojoties uz faktisko skaitu,

141
00:10:59,100 --> 00:11:01,550
bet reizēm jūs varat arī ir Huffman koks

142
00:11:01,550 --> 00:11:05,760
pamatojoties uz frekvenci, kur burti parādās, un tas ir tieši tas pats process.

143
00:11:05,760 --> 00:11:09,090
Šeit es esmu izsakot to ziņā procentos vai frakciju,

144
00:11:09,090 --> 00:11:11,290
un tāpēc šeit tieši tas pats.

145
00:11:11,290 --> 00:11:15,300
Es uzskatu par 2 zemākais, Apkopojot tos, nākamo 2 zemākais, Apkopojot tos,

146
00:11:15,300 --> 00:11:19,390
kamēr man ir pilna koku.

147
00:11:19,390 --> 00:11:23,610
Pat ja mēs varētu darīt vai nu veidā, kad mums ir darīšana ar procentiem,

148
00:11:23,610 --> 00:11:27,760
tas nozīmē, ka mēs esam dalot lietas un nodarbojas ar decimāldaļām vai drīzāk pludiņi

149
00:11:27,760 --> 00:11:30,900
ja mēs esam domājot par datu struktūrām ar galvu.

150
00:11:30,900 --> 00:11:32,540
Ko mēs zinām par pludiņiem?

151
00:11:32,540 --> 00:11:35,180
Kas izplatīta problēma, kad mums ir darīšana ar pludiņiem?

152
00:11:35,180 --> 00:11:38,600
[Students] neprecīzs aritmētika. >> Jā. Neprecizitāte.

153
00:11:38,600 --> 00:11:43,760
Sakarā ar peldošo komatu neprecizitātes, par šo PSET lai mēs pārliecinātos

154
00:11:43,760 --> 00:11:49,450
ka mums nav zaudēt jebkādu vērtības, tad mēs tiešām gribam būt darīšana ar skaitu.

155
00:11:49,450 --> 00:11:54,880
Tātad, ja Jums bija domāt par Huffman mezglā, ja paskatās atpakaļ uz struktūru šeit,

156
00:11:54,880 --> 00:12:01,740
ja paskatās zaļos tas ir frekvenci saistīti ar to

157
00:12:01,740 --> 00:12:08,760
kā arī tas norāda uz mezglu tā pa kreisi, kā arī mezglu savas tiesības.

158
00:12:08,760 --> 00:12:13,970
Un tad sarkanā tiem tur arī ir raksturs saistītas ar tiem.

159
00:12:13,970 --> 00:12:18,900
Mēs nebrauksim, lai veiktu atsevišķus tiem par vecākiem un tad gala mezgliem,

160
00:12:18,900 --> 00:12:23,680
ko mēs saucam par lapām, bet gan tie, vienkārši ir NULL vērtības.

161
00:12:23,680 --> 00:12:31,050
Par katru mezglu mums būs raksturs, simbols, ka mezgls ir,

162
00:12:31,050 --> 00:12:40,490
tad biežumu, kā arī rādītāju uz kreisajiem bērnam, kā arī tās labās bērnu.

163
00:12:40,490 --> 00:12:45,680
Lapas, kas ir pašā apakšā, būtu arī mezglu norādes

164
00:12:45,680 --> 00:12:49,550
to pa kreisi un tiesības, bet kopš šīs vērtības nav norādot uz faktiskajiem mezgliem,

165
00:12:49,550 --> 00:12:53,970
kāds būtu to vērtība var būt? >> [Students] NULL. >> NULL. Tieši tā.

166
00:12:53,970 --> 00:12:58,430
Lūk, kā jūs varētu pārstāvēt frekvenci pludiņiem piemērs,

167
00:12:58,430 --> 00:13:02,130
bet mēs gribam būt darīšana ar to ar veseliem skaitļiem,

168
00:13:02,130 --> 00:13:06,780
tāpēc viss, ko es darīju, ir mainīt datu tipu tur.

169
00:13:06,780 --> 00:13:09,700
>> Iesim uz mazliet vairāk no sarežģītas piemērs.

170
00:13:09,700 --> 00:13:13,360
Bet tagad, ka mēs esam darījuši vienkāršām, tas ir tikai pats process.

171
00:13:13,360 --> 00:13:20,290
Jūs atradīsiet arī 2 zemākās frekvences, Apkopojot frekvences

172
00:13:20,290 --> 00:13:22,450
un tas ir jauns biežums jūsu mātes mezglā,

173
00:13:22,450 --> 00:13:29,310
kas tad norāda uz to kreisi ar 0 filiāli un tiesības ar 1 filiāle.

174
00:13:29,310 --> 00:13:34,200
Ja mums ir virkne "Tas ir CS50", tad mēs saskaitītu, cik reižu ir T minēts,

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

176
00:13:38,420 --> 00:13:42,010
Tad ko es darīju šeit ir ar sarkanu mezglu es tikko iestādīti,

177
00:13:42,010 --> 00:13:48,530
Es teicu, es esmu nāksies šīs zīmes beidzot apakšā manu koku.

178
00:13:48,530 --> 00:13:51,740
Tiem ir būs visas lapām.

179
00:13:51,740 --> 00:13:58,200
Tad ko es darīju, ir man sakārtoti tos pēc biežuma augošā secībā,

180
00:13:58,200 --> 00:14:02,950
un tas ir faktiski tā, ka PSET kods to dara

181
00:14:02,950 --> 00:14:07,550
ir tā veidu to ar frekvenci un pēc tam alfabēta.

182
00:14:07,550 --> 00:14:13,870
Tātad tas ir skaitļus vispirms un pēc tam alfabētiski pēc biežuma.

183
00:14:13,870 --> 00:14:18,520
Tad ko es varētu darīt, ir, es varētu atrast par 2 viszemākais. Tas ir 0 un 5.

184
00:14:18,520 --> 00:14:22,390
Es jāsummē tos, un tas ir 2. Tad es varētu turpināt, atrast nākamo 2 viszemākais.

185
00:14:22,390 --> 00:14:26,100
Tie ir divi 1s, un tad tie kļūst par 2, kā arī.

186
00:14:26,100 --> 00:14:31,570
Tagad es zinu, ka mans nākamais solis būs pievienosies vismazākais skaits,

187
00:14:31,570 --> 00:14:41,380
kas ir T, 1, un pēc tam izvēloties vienu no mezgliem, kas ir 2 kā biežumu.

188
00:14:41,380 --> 00:14:44,560
Tātad šeit mums ir 3 iespējas.

189
00:14:44,560 --> 00:14:47,980
Ko es esmu gatavojas darīt, lai slaidā ir tikai vizuāli pārkārtot tos jums

190
00:14:47,980 --> 00:14:51,790
lai jūs varētu redzēt, kā es esmu celtniecības to.

191
00:14:51,790 --> 00:14:59,040
Ko kods un jūsu izplatīšanas kods ir gatavojas darīt būtu pievienoties T 1

192
00:14:59,040 --> 00:15:01,410
ar 0 un 5 mezglu.

193
00:15:01,410 --> 00:15:05,060
Lai tad summas līdz 3, un tad mēs turpinātu šo procesu.

194
00:15:05,060 --> 00:15:08,660
Ar 2 un 2 tagad ir viszemākais, lai tad tie, summa līdz 4.

195
00:15:08,660 --> 00:15:12,560
Ikvienam pēc līdz šim? Labi.

196
00:15:12,560 --> 00:15:16,410
Tad pēc tam mums ir 3 un 3, kas nepieciešams, ir jāsummē,

197
00:15:16,410 --> 00:15:21,650
tāpēc atkal es esmu tikai pārejot tā, lai jūs varētu redzēt vizuāli tā, ka tas nav pārāk netīrs.

198
00:15:21,650 --> 00:15:25,740
Tad mums ir 6, un tad mūsu pēdējais solis ir tagad, ka mums ir tikai 2 punktiem

199
00:15:25,740 --> 00:15:30,440
Mēs summa tiem darīt saknes mūsu koks, kas ir par 10.

200
00:15:30,440 --> 00:15:34,100
Un numurs 10 ir jēga, jo katrs mezgls pārstāvētas,

201
00:15:34,100 --> 00:15:40,750
to vērtību, to biežums skaits, bija, cik reizes viņi parādījās virknē,

202
00:15:40,750 --> 00:15:46,350
un tad mums ir 5 rakstzīmes mūsu virknes, lai jēga.

203
00:15:48,060 --> 00:15:52,320
Ja mēs skatāmies uz augšu pie kā mēs varētu reāli kodēt to,

204
00:15:52,320 --> 00:15:56,580
kā gaidīts, i un i, kas parādās visbiežāk

205
00:15:56,580 --> 00:16:01,350
pārstāv vismazāko bitu skaits.

206
00:16:03,660 --> 00:16:05,660
>> Esi uzmanīgs šeit.

207
00:16:05,660 --> 00:16:09,780
Jo Huffman kokiem lieta faktiski jautājumiem.

208
00:16:09,780 --> 00:16:13,670
Lielais S ir savādāka nekā mazo s.

209
00:16:13,670 --> 00:16:21,260
Ja mums bija: "Tas ir CS50" ar lielajiem burtiem, tad mazie s parādīsies tikai divreiz,

210
00:16:21,260 --> 00:16:27,120
būtu mezglu ar 2, jo tā vērtība, un tad lielais S būtu tikai vienu reizi.

211
00:16:27,120 --> 00:16:33,440
Tātad tad jūsu koks varētu mainīt struktūru, jo jums tiešām ir papildu lapu šeit.

212
00:16:33,440 --> 00:16:36,900
Bet summa joprojām būtu 10.

213
00:16:36,900 --> 00:16:39,570
Ka tas, ko mēs patiesībā gribam būt zvanot kontrolsummu,

214
00:16:39,570 --> 00:16:44,060
pievienojot visu skaita.

215
00:16:46,010 --> 00:16:50,990
>> Tagad, ka mēs esam uz Huffman koki, mēs varam nodoties Huff'n Puff, tad PSET.

216
00:16:50,990 --> 00:16:52,900
Mēs esam gatavojas sākt ar daļu no jautājumiem,

217
00:16:52,900 --> 00:16:57,990
un tas ir gatavojas iegūt jums pieradis ar bināriem kokiem un kā darboties aptuveni ka:

218
00:16:57,990 --> 00:17:03,230
zīmēšanas mezglus, izveidojot savu typedef struktūrai par mezglu,

219
00:17:03,230 --> 00:17:07,230
un redzēt, kā jūs varētu ievietot bināro koku, viens, kas ir sakārtoti,

220
00:17:07,230 --> 00:17:09,050
šķērso to, un lietas, piemēram, ka.

221
00:17:09,050 --> 00:17:14,560
Ka zināšanas ir noteikti gatavojas palīdzēt jums, kad jūs pikējošais Huff'n Puff daļu

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

223
00:17:19,150 --> 00:17:26,329
Ar standarta izdevumā PSET, jūsu uzdevums ir ieviest Puff,

224
00:17:26,329 --> 00:17:30,240
un hakeru versiju jūsu uzdevums ir īstenot pukoties.

225
00:17:30,240 --> 00:17:38,490
Kas Huff tas ir tas aizņem tekstu un pēc tam tas pārveido to par 0s un 1s,

226
00:17:38,490 --> 00:17:41,990
lai process, ko mēs darījām iepriekš, kad mēs skaitīti frekvences

227
00:17:41,990 --> 00:17:50,970
un tad veic koku un tad teica: "Kā es varu iegūt T?"

228
00:17:50,970 --> 00:17:54,840
T pārstāv 100, lietām, piemēram, ka,

229
00:17:54,840 --> 00:17:58,860
un tad Huff varētu veikt tekstu un tad izejas, ka bināro.

230
00:17:58,860 --> 00:18:04,920
Bet arī tāpēc, ka mēs zinām, ka mēs vēlamies, lai mūsu adresātu sarakstā

231
00:18:04,920 --> 00:18:11,790
atjaunot tieši tādu pašu koku, tā ietver arī informāciju par frekvenču skaitu.

232
00:18:11,790 --> 00:18:17,980
Tad ar Puff mums ir dota bināro failu 0s un 1s

233
00:18:17,980 --> 00:18:21,740
un ņemot vērā arī informāciju par frekvencēm.

234
00:18:21,740 --> 00:18:26,740
Mēs tulkojam visas šīs 0s un 1s atpakaļ oriģinālā ziņojuma, kas bija,

235
00:18:26,740 --> 00:18:29,350
tāpēc mēs esam decompressing ka.

236
00:18:29,350 --> 00:18:36,450
Ja jūs darāt standarta versiju, jums nav nepieciešams, lai īstenotu pukoties,

237
00:18:36,450 --> 00:18:39,290
tā, tad jūs varat izmantot personāla ieviešanu Huff.

238
00:18:39,290 --> 00:18:42,080
Ir instrukcijas spec par to, kā to izdarīt.

239
00:18:42,080 --> 00:18:48,780
Jūs varat palaist personāla ieviešanu Huff uz noteiktu teksta failu

240
00:18:48,780 --> 00:18:53,270
un pēc tam izmantot šo produkciju kā savu ieguldījumu, lai dvesma.

241
00:18:53,270 --> 00:18:59,330
>> Kā jau minēju iepriekš, mums ir daudz sadales kodu par šo vienu.

242
00:18:59,330 --> 00:19:01,810
Es esmu gatavojas sākt iet caur to.

243
00:19:01,810 --> 00:19:04,400
Es esmu gatavojas pavadīt lielāko daļu laika par. H faili

244
00:19:04,400 --> 00:19:07,660
jo kas. c failiem, jo ​​mums ir. h

245
00:19:07,660 --> 00:19:11,650
un kas nodrošina mūs ar funkciju prototipu,

246
00:19:11,650 --> 00:19:15,520
mums nav pilnīgi nepieciešams, lai saprastu tieši -

247
00:19:15,520 --> 00:19:20,280
Ja jūs nesaprotat, kas notiek ar. C failus, tad nav jāuztraucas pārāk daudz,

248
00:19:20,280 --> 00:19:23,600
bet noteikti mēģināt paskatīties, jo tas varētu dot dažus padomus

249
00:19:23,600 --> 00:19:29,220
un tas ir noderīgi, lai pierastu pie lasīšanas citu cilvēku kodu.

250
00:19:38,940 --> 00:19:48,270
>> Aplūkojot huffile.h, jo komentārus tā deklarē slānis abstrakcijas par Huffman kodēta failus.

251
00:19:48,270 --> 00:20:01,660
Ja mēs ejam uz leju, mēs redzam, ka ir no 256 simboliem maksimālais ka mums varētu būt nepieciešams kodus.

252
00:20:01,660 --> 00:20:05,480
Tas ietver visus burtus alfabēta - lielie un mazie -

253
00:20:05,480 --> 00:20:08,250
un tad simboli un skaitļi utt

254
00:20:08,250 --> 00:20:11,930
Tad šeit mums ir burvju skaitu identificē Huffman kodējumu failu.

255
00:20:11,930 --> 00:20:15,890
Ietvaros Huffman kodu viņi gatavojas ir zināma burvju numuru

256
00:20:15,890 --> 00:20:18,560
saistīti ar galveni.

257
00:20:18,560 --> 00:20:21,110
Tas varētu izskatīties tikai izlases burvju numuru,

258
00:20:21,110 --> 00:20:27,160
bet, ja jūs tiešām to pārtulkot ASCII, tad tas tiešām ir skaidri noteikts pukoties.

259
00:20:27,160 --> 00:20:34,290
Šeit mums ir struct par Huffman-kodētu failu.

260
00:20:34,290 --> 00:20:39,670
Tur visas šīs īpašības saistītas ar Huff failu.

261
00:20:39,670 --> 00:20:47,080
Tad noteikti šeit mums ir galveni Huff failu, tāpēc mēs to saucam Huffeader

262
00:20:47,080 --> 00:20:50,810
nevis pievienojot papildu h, jo tas izklausās pats vienalga.

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

264
00:20:52,720 --> 00:20:57,790
Mums ir burvju skaitu saistīti ar to.

265
00:20:57,790 --> 00:21:09,040
Ja tas ir faktiskā Huff failu, tas būs skaits augšas, šī burvju vienu.

266
00:21:09,040 --> 00:21:14,720
Un tad tas būs masīvs.

267
00:21:14,720 --> 00:21:18,750
Tātad par katru simbolu, kas ir 256,

268
00:21:18,750 --> 00:21:24,760
tas notiek uzskaitīt kādām šīm simbolu frekvence ir robežās Huff failu.

269
00:21:24,760 --> 00:21:28,090
Un tad beidzot, mums ir kontrolsummu attiecībā uz frekvencēm,

270
00:21:28,090 --> 00:21:32,160
kas būtu summa šajās frekvencēs.

271
00:21:32,160 --> 00:21:36,520
Tātad, tas ko Huffeader ir.

272
00:21:36,520 --> 00:21:44,600
Tad mums ir dažas funkcijas, kas atgriež nākamo bitu, Huff failā

273
00:21:44,600 --> 00:21:52,580
kā arī raksta mazliet uz Huff failu, un tad šī funkcija šeit, hfclose,

274
00:21:52,580 --> 00:21:54,650
kas faktiski aizver Huff failu.

275
00:21:54,650 --> 00:21:57,290
Pirms tam mums bija darīšana ar taisni tikai fclose,

276
00:21:57,290 --> 00:22:01,190
bet, ja jums ir Huff fails, nevis fclosing to

277
00:22:01,190 --> 00:22:06,080
ko jūs tiešām gatavojas darīt, ir hfclose un hfopen to.

278
00:22:06,080 --> 00:22:13,220
Tie ir īpašas funkcijas uz Huff failiem ka mēs ejam, lai būtu darīšana ar.

279
00:22:13,220 --> 00:22:19,230
Tad šeit mēs lasām galvenē un tad uzrakstiet galveni.

280
00:22:19,230 --> 00:22:25,700
>> Tikai izlasot. H failu mēs varam veida nokļūt sajūtu, ko Huff fails varētu būt,

281
00:22:25,700 --> 00:22:32,480
kādas īpašības tā, bet faktiski iet uz huffile.c,

282
00:22:32,480 --> 00:22:36,750
kas, ja mēs ienirt, būs nedaudz sarežģītāka.

283
00:22:36,750 --> 00:22:41,270
Tā ir visas failu I / O šeit nodarbojas ar norādes.

284
00:22:41,270 --> 00:22:48,010
Šeit mēs redzam, ka tad, kad mēs saucam hfread, piemēram, tas joprojām nodarbojas ar fread.

285
00:22:48,010 --> 00:22:53,050
Mēs esam ne atbrīvojoties no šīm funkcijām pilnībā, bet mēs nosūtām tiem jāņem aprūpi

286
00:22:53,050 --> 00:22:59,760
iekšpusē Huff failu nevis dara visu par to paši.

287
00:22:59,760 --> 00:23:02,300
Jūs varat justies brīvi, lai skenētu ar to, ja jūs esat ieinteresēti

288
00:23:02,300 --> 00:23:08,410
un iet un mizas slānis muguras mazliet.

289
00:23:20,650 --> 00:23:24,060
>> Nākamais fails, mēs ejam, lai apskatīt ir tree.h.

290
00:23:24,060 --> 00:23:30,210
Agrāk Walkthrough slaidi mēs teicām, mēs sagaidām Huffman mezglu

291
00:23:30,210 --> 00:23:32,960
un mēs, typedef struktūrai mezglā.

292
00:23:32,960 --> 00:23:38,360
Mēs sagaidām, ka tas ir simbols, ar biežumu un tad 2 mezglu zvaigznēm.

293
00:23:38,360 --> 00:23:41,870
Šajā gadījumā tas, ko mēs darām, ir tas būtībā tas pats

294
00:23:41,870 --> 00:23:46,880
izņemot vietā mezgla mēs ejam, lai viņiem piezvanīt kokiem.

295
00:23:48,790 --> 00:23:56,760
Mums ir funkcija, kas, ja jūs zvanīt veikt koku to atgriež jums koku rādītāju.

296
00:23:56,760 --> 00:24:03,450
Atpakaļ uz Speller, kad Jums bija padarīt jaunu mezglu

297
00:24:03,450 --> 00:24:11,410
jūs teicāt mezglu * jaunais vārds = malloc (sizeof) un lietas, piemēram, ka.

298
00:24:11,410 --> 00:24:17,510
Būtībā, mktree tiek būs darīšana ar to jums.

299
00:24:17,510 --> 00:24:20,990
Tāpat, ja jūs vēlaties, lai novērstu koku,

300
00:24:20,990 --> 00:24:24,810
tā ka ir būtiski atbrīvojot koku, kad esat pabeidzis ar to,

301
00:24:24,810 --> 00:24:33,790
instead of skaidri aicinot bezmaksas ka jūs faktiski tikai gatavojas izmantot šo funkciju rmtree

302
00:24:33,790 --> 00:24:40,360
kur jūs iet uz rādītāju uz tā koka, un tad tree.c būs rūpēties par to, lai jums.

303
00:24:40,360 --> 00:24:42,490
>> Mēs izpētīt tree.c.

304
00:24:42,490 --> 00:24:47,240
Mēs sagaidām tās pašas funkcijas, izņemot redzēt īstenošanu, kā arī.

305
00:24:47,240 --> 00:24:57,720
Kā mēs gaidīts, kad jūs zvanu mktree to mallocs lielumu kokā rādītājs,

306
00:24:57,720 --> 00:25:03,190
initializes visas vērtības uz nulles vērtībā, tādēļ 0s vai nulls,

307
00:25:03,190 --> 00:25:08,280
un pēc tam atgriež rādītāju uz šo koku, kas jūs esat tikko malloc'd jums.

308
00:25:08,280 --> 00:25:13,340
Šeit, kad jūs zvanu noņemt koku vispirms pārliecinās, ka jūs esat ne dubultā atbrīvojot.

309
00:25:13,340 --> 00:25:18,320
Tas nodrošina, ka jums tiešām ir koks, kuru vēlaties noņemt.

310
00:25:18,320 --> 00:25:23,330
Šeit, jo koks ir arī savus bērnus,

311
00:25:23,330 --> 00:25:29,560
Kas tas ir tas rekursīvi aicina likvidēt koks kreisajā mezgla koka

312
00:25:29,560 --> 00:25:31,650
kā arī labo mezglu.

313
00:25:31,650 --> 00:25:37,790
Pirms tā atbrīvo no vecākiem, tai atbrīvotu bērnus, kā arī.

314
00:25:37,790 --> 00:25:42,770
Vecāki ir arī aizstājamas ar sakni.

315
00:25:42,770 --> 00:25:46,500
Pirmais vecāks, tāpēc tāpat kā liels-liels-liels-vecvectēvs

316
00:25:46,500 --> 00:25:52,130
vai vecmāmiņa koks, vispirms mums ir bezmaksas leju līmeni pirmās.

317
00:25:52,130 --> 00:25:58,490
Tāpēc traversa uz leju, bez tiem, un pēc tam nāk atpakaļ uz augšu, bez tiem, uc

318
00:26:00,400 --> 00:26:02,210
Tātad tas ir koks.

319
00:26:02,210 --> 00:26:04,240
>> Tagad mēs apskatīt mežu.

320
00:26:04,240 --> 00:26:09,860
Mežs ir, ja jūs vieta visiem jūsu Huffman kokiem.

321
00:26:09,860 --> 00:26:12,910
Tas ir saprotams, ka mēs ejam, lai būtu kaut ko sauc gabals

322
00:26:12,910 --> 00:26:22,320
kas satur rādītāju uz koku, kā arī rādītāju uz zemes gabala sauc nākamo.

323
00:26:22,320 --> 00:26:28,480
Kāda struktūra dara šāda veida izskatās?

324
00:26:29,870 --> 00:26:32,490
Tā veida saka tā tur.

325
00:26:34,640 --> 00:26:36,700
Tiesības pār šeit.

326
00:26:37,340 --> 00:26:39,170
Saistīts saraksts.

327
00:26:39,170 --> 00:26:44,590
Mēs redzam, ka tad, kad mums ir gabals tas ir kā saistīts sarakstu gabaliem.

328
00:26:44,590 --> 00:26:53,020
Mežs ir definēta kā saistīts sarakstu gabalu,

329
00:26:53,020 --> 00:26:58,100
un tāpēc meža struktūra mēs esam tikai nāksies rādītāju uz mūsu pirmo gabals

330
00:26:58,100 --> 00:27:02,740
un ka gabals ir koks tajā, vai drīzāk norāda uz koku

331
00:27:02,740 --> 00:27:06,190
un tad norāda uz nākamo gabals, tā tālāk un tā tālāk.

332
00:27:06,190 --> 00:27:11,100
Lai veiktu meža mēs saucam mkforest.

333
00:27:11,100 --> 00:27:14,930
Tad mums ir daži diezgan noderīgas funkcijas šeit.

334
00:27:14,930 --> 00:27:23,240
Mums ir uzņemt kur jūs iet mežā un tad atgriešanās vērtība ir koks *,

335
00:27:23,240 --> 00:27:25,210
pointers uz koku.

336
00:27:25,210 --> 00:27:29,370
Ko pick būs jādara, ir tas iet uz mežu, ka jūs esat norādot uz

337
00:27:29,370 --> 00:27:35,240
Tad noņemiet koks ar zemāko frekvenci no šī meža

338
00:27:35,240 --> 00:27:38,330
un tad jums rādītāju uz šo koku.

339
00:27:38,330 --> 00:27:43,030
Kad jūs zvanu izvēlēties, koks nepastāv mežā vairs,

340
00:27:43,030 --> 00:27:48,550
bet atgriešanās vērtība ir rādītājs uz šo koku.

341
00:27:48,550 --> 00:27:50,730
Tad jums ir iekārta.

342
00:27:50,730 --> 00:27:57,420
Ja jums iet ar rādītāju uz koku, kas ir ne-0 frekvenci,

343
00:27:57,420 --> 00:28:04,040
ko iekārta būs jādara, ir tas prasīs mežā, veikt koku un augu ka koks iekšpusē mežā.

344
00:28:04,040 --> 00:28:06,370
Šeit mums ir rmforest.

345
00:28:06,370 --> 00:28:11,480
Līdzīgi kā novērst koku, kas pamatā atbrīvojušies visas mūsu koku mums,

346
00:28:11,480 --> 00:28:16,600
noņemt mežā bez viss ietverts šajā mežā.

347
00:28:16,600 --> 00:28:24,890
>> Ja mēs skatāmies uz forest.c, mēs sagaidām, lai redzētu vismaz 1 rmtree komandu tur,

348
00:28:24,890 --> 00:28:30,090
jo, lai atbrīvotu atmiņu mežā ja mežs ir koki tajā,

349
00:28:30,090 --> 00:28:32,930
tad beidzot jūs nāksies novērst šos kokus pārāk.

350
00:28:32,930 --> 00:28:41,020
Ja mēs skatāmies uz forest.c, mums ir mūsu mkforest, kas, kā mēs sagaidām.

351
00:28:41,020 --> 00:28:42,890
Mēs malloc lietas.

352
00:28:42,890 --> 00:28:51,740
Mēs inicializēt pirmo gabals mežā par spēkā, jo tas ir tukšs, lai sāktu ar,

353
00:28:51,740 --> 00:29:05,940
Tad mēs redzētu pick, kas atgriež koks ar zemāko svaru, zemākās frekvences,

354
00:29:05,940 --> 00:29:13,560
un tad izpaužas atbrīvoties no konkrētā mezglā, kas norāda uz tā koka, un nākamo,

355
00:29:13,560 --> 00:29:16,760
lai tā veic, ka no saistītā saraksta mežā.

356
00:29:16,760 --> 00:29:24,510
Un tad šeit mums ir rūpnīcas, kas ievieto kokā saistītajā sarakstā.

357
00:29:24,510 --> 00:29:29,960
Kas mežs tas ir tas labi saglabā tā sakārtoti, lai mums.

358
00:29:29,960 --> 00:29:37,910
Un tad beidzot, mums ir rmforest un, kā plānots, mums ir rmtree sauc tur.

359
00:29:46,650 --> 00:29:55,440
>> Raugoties uz sadales kodu šim, huffile.c bija iespējams līdz šim visgrūtāk saprast,

360
00:29:55,440 --> 00:29:59,990
tā kā citi faili paši bija diezgan vienkārši sekot.

361
00:29:59,990 --> 00:30:03,090
Ar mūsu zināšanas par norādes un saistīto saraksti un tādiem,

362
00:30:03,090 --> 00:30:04,860
mums bija iespēja sekot diezgan labi.

363
00:30:04,860 --> 00:30:10,500
Bet viss, kas mums nepieciešams, lai tiešām pārliecinātos, ka mēs pilnībā saprotam ir. H faili

364
00:30:10,500 --> 00:30:15,840
jo jums ir nepieciešams būt aicinot tās funkcijas, kas nodarbojas ar šiem atgriešanās vērtībām,

365
00:30:15,840 --> 00:30:20,590
tāpēc pārliecinieties, ka jūs pilnībā saprast, kādi pasākumi būs jāveic

366
00:30:20,590 --> 00:30:24,290
kad tu sauc vienu no šīm funkcijām.

367
00:30:24,290 --> 00:30:33,020
Bet patiesībā izpratne iekšpusē tā nav gluži nepieciešams, jo mums ir tiem. H failus.

368
00:30:35,170 --> 00:30:39,490
Mums ir vēl 2 failus, kas palikuši mūsu izplatīšanas kodu.

369
00:30:39,490 --> 00:30:41,640
>> Apskatīsim izgāztuves.

370
00:30:41,640 --> 00:30:47,230
Dump ar savu komentāru šeit notiek Huffman-saspiestu failu

371
00:30:47,230 --> 00:30:55,580
un tad pārvērš un izgāztuves visu tā saturu uzmanību.

372
00:31:01,010 --> 00:31:04,260
Šeit mēs redzam, ka tas zvana hfopen.

373
00:31:04,260 --> 00:31:10,770
Tas ir sava veida sasaucoties iesniegt * Ieejas = fopen,

374
00:31:10,770 --> 00:31:13,500
un tad jums iet ar informāciju.

375
00:31:13,500 --> 00:31:18,240
Tas ir gandrīz identiski, izņemot vietā failu * jūs iet ar Huffile;

376
00:31:18,240 --> 00:31:22,030
vietā fopen jūs iet uz hfopen.

377
00:31:22,030 --> 00:31:29,280
Šeit mēs lasām galvenē pirmais, kas ir veida līdzīga kā mēs lasīt galvenē

378
00:31:29,280 --> 00:31:33,580
uz bitkartes failu.

379
00:31:33,580 --> 00:31:38,000
Ko mēs darām šeit ir pārbaudīt, lai redzētu, vai galvenes informāciju

380
00:31:38,000 --> 00:31:44,330
satur pareizo burvju numuru, kas norāda, ka tā ir faktiskā Huff fails,

381
00:31:44,330 --> 00:31:53,610
tad visi šie pārbaudes, lai pārliecinātos, ka fails, ka mēs atveram ir faktiskā huffed failu vai ne.

382
00:31:53,610 --> 00:32:05,330
Kas tas ir tas izejas frekvences visu simbolu, ka mēs varam redzēt

383
00:32:05,330 --> 00:32:09,790
laikā termināla uz grafisko tabulā.

384
00:32:09,790 --> 00:32:15,240
Šī daļa būs noderīga.

385
00:32:15,240 --> 00:32:24,680
Tas ir mazliet un skan pamazām stājas mainīgo bitu un tad drukā to ārā.

386
00:32:28,220 --> 00:32:35,430
Tātad, ja es būtu aicināt dump uz hth.bin, kas izriet no huffing failu

387
00:32:35,430 --> 00:32:39,490
izmantojot personāla risinājumu, es varētu saņemt šo.

388
00:32:39,490 --> 00:32:46,000
Tas outputting visiem šiem burtiem un tad liekot biežumu, kurā tie parādās.

389
00:32:46,000 --> 00:32:51,180
Ja mēs skatāmies, vairums no tiem ir 0s izņemot šo: H, kas parādās divas reizes,

390
00:32:51,180 --> 00:32:54,820
un tad T, kas parādās reizi.

391
00:32:54,820 --> 00:33:07,860
Un tad šeit mums ir faktisko ziņu 0s un 1s.

392
00:33:07,860 --> 00:33:15,450
Ja mēs skatāmies hth.txt, kas ir iespējams, sākotnējais ziņojums, kas tika huffed,

393
00:33:15,450 --> 00:33:22,490
Mēs sagaidām, lai redzētu kādu HS un TS tur.

394
00:33:22,490 --> 00:33:28,720
Konkrēti, mēs sagaidām, lai redzētu tikai T 1 un 2 HS.

395
00:33:32,510 --> 00:33:37,440
Šeit mēs esam hth.txt. Tā patiešām ir HTH.

396
00:33:37,440 --> 00:33:41,270
Iekļautas tur, gan mēs nevaram redzēt, ir newline raksturs.

397
00:33:41,270 --> 00:33:53,190
The Huff fails hth.bin arī kodē newline raksturs, kā arī.

398
00:33:55,680 --> 00:34:01,330
Šeit, jo mēs zinām, ka pasūtījums ir HTH un tad newline,

399
00:34:01,330 --> 00:34:07,340
mēs varam redzēt, ka, iespējams H pārstāv tikai vienu 1

400
00:34:07,340 --> 00:34:17,120
un tad T ir iespējams 01 un tad nākamo H 1, kā arī

401
00:34:17,120 --> 00:34:21,139
un tad mums ir newline norāda ar diviem 0S.

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

403
00:34:26,530 --> 00:34:31,600
>> Un tad beidzot, jo mums ir darīšana ar vairākiem. C un. H failus,

404
00:34:31,600 --> 00:34:36,350
mēs esam nāksies diezgan sarežģīts argumentu uz kompilators,

405
00:34:36,350 --> 00:34:40,460
un tāpēc šeit mums ir Makefile kas padara dump jums.

406
00:34:40,460 --> 00:34:47,070
Bet patiesībā, jums ir iet par padarot savu puff.c failu.

407
00:34:47,070 --> 00:34:54,330
Makefaila faktiski nenodarbojas ar padarot puff.c jums.

408
00:34:54,330 --> 00:34:59,310
Mēs esam atstājot, ka līdz jums, lai rediģētu Makefile.

409
00:34:59,310 --> 00:35:05,930
Kad jūs ievadiet komandu, piemēram, darīt visu, piemēram, tas dos viņiem visiem jums.

410
00:35:05,930 --> 00:35:10,760
Jūtieties brīvi apskatīt Makefile piemēriem no pagātnes PSET

411
00:35:10,760 --> 00:35:17,400
kā arī dodas pie šo vienu, lai redzētu, kā jūs varētu veikt savu Puff failu

412
00:35:17,400 --> 00:35:20,260
, rediģējot šo Makefile.

413
00:35:20,260 --> 00:35:22,730
Tas ir par to, lai mūsu izplatīšanas kodu.

414
00:35:22,730 --> 00:35:28,380
>> Kad esam tikuši cauri, ka tad šeit ir tikai citu atgādinājums

415
00:35:28,380 --> 00:35:30,980
par to, kā mēs gribam būt darīšana ar Huffman mezgliem.

416
00:35:30,980 --> 00:35:35,400
Mēs nebrauksim aicinās viņus mezgliem vairs, mēs gribam būt aicinot tos kokus

417
00:35:35,400 --> 00:35:39,260
kur mēs ejam, lai būtu pārstāv savu simbolu ar palija,

418
00:35:39,260 --> 00:35:43,340
biežumu, atkārtojumu skaitu, ar veselam skaitlim.

419
00:35:43,340 --> 00:35:47,370
Mēs izmantojam, jo ​​tas ir precīzāka nekā apgrozāmos līdzekļus.

420
00:35:47,370 --> 00:35:52,980
Un tad mums ir citu rādītāju pa kreisi bērnu, kā arī tiesības bērns.

421
00:35:52,980 --> 00:35:59,630
Mežs, kā mēs redzējām, ir tikai saistīts saraksts koku.

422
00:35:59,630 --> 00:36:04,670
Galu galā, ja mēs esam veidojot mūsu Huff failu,

423
00:36:04,670 --> 00:36:07,580
Mēs vēlamies, lai mūsu meži, satur tikai 1 koks -

424
00:36:07,580 --> 00:36:12,420
1 koks, 1 sakne ar vairākiem bērniem.

425
00:36:12,420 --> 00:36:20,840
Agrāk, kad mēs bijām tikai padarīt mūsu Huffman kokus,

426
00:36:20,840 --> 00:36:25,360
mēs sākām, novietojot visas mezglu uz mūsu ekrāna

427
00:36:25,360 --> 00:36:27,790
un sakot mēs esam nāksies šos mezglus,

428
00:36:27,790 --> 00:36:32,920
beidzot viņi būs lapas, un tas ir viņu simbols, tas ir viņu frekvence.

429
00:36:32,920 --> 00:36:42,070
Mūsu mežā, ja mēs vienkārši ir 3 burti, kas ir mežs 3 kokiem.

430
00:36:42,070 --> 00:36:45,150
Un tad, kā mēs iet tālāk, kad mēs pievienot pirmais mātes,

431
00:36:45,150 --> 00:36:48,080
mēs, mežs 2 kokiem.

432
00:36:48,080 --> 00:36:54,930
Mēs noņemt 2 no tiem bērniem no mūsu mežu un pēc tam aizstāt to ar mātes mezglā

433
00:36:54,930 --> 00:36:58,820
kas bija tās 2 punktiem, kā bērniem.

434
00:36:58,820 --> 00:37:05,600
Un tad beidzot, mūsu pēdējais solis, lai mūsu piemērs ar AS, BS, un Cs

435
00:37:05,600 --> 00:37:08,030
būtu veikt galīgo vecāks,

436
00:37:08,030 --> 00:37:13,190
un tā tad kas varētu sniegt mūsu kopējo skaitu koku mežā ar 1.

437
00:37:13,190 --> 00:37:18,140
Vai visi redzētu, kā jūs sākt ar vairākiem kokiem savā mežā

438
00:37:18,140 --> 00:37:22,520
un galu galā ar 1? Labi. Atdzist.

439
00:37:25,530 --> 00:37:28,110
>> Kas mums jādara, lai Puff?

440
00:37:28,110 --> 00:37:37,110
Kas mums jādara, ir nodrošināt, ka vienmēr, tie dod mums pareizo veidu ieejas

441
00:37:37,110 --> 00:37:39,090
lai mēs faktiski var palaist programmu.

442
00:37:39,090 --> 00:37:43,130
Šajā gadījumā viņi būs dodot mums pēc pirmā komandrindas argumentu

443
00:37:43,130 --> 00:37:53,440
2 vairāk: fails, ko mēs vēlamies, lai atspiest un tās atspiests failu izeja.

444
00:37:53,440 --> 00:38:00,410
Bet tad, kad mēs pārliecināmies, ka viņi iet mūs pareizajā apmērā vērtībām,

445
00:38:00,410 --> 00:38:05,820
Mēs vēlamies nodrošināt, ka ieguldījums ir Huff failu vai ne.

446
00:38:05,820 --> 00:38:10,420
Un tad, kad mēs garantējam, ka tas Huff failu, tad mēs vēlamies veidot mūsu koku,

447
00:38:10,420 --> 00:38:20,940
veidot koku tā, lai tas atbilst koku ka persona, kas nosūtīja vēstījumu būvēts.

448
00:38:20,940 --> 00:38:25,840
Tad, kad mēs veidot koku, tad mēs varam tikt galā ar 0s un 1s ka tie pieņemti,

449
00:38:25,840 --> 00:38:29,590
sekot tiem līdzi mūsu koku, jo tas ir identisks,

450
00:38:29,590 --> 00:38:33,510
un tad rakstīt, ka ziņu, kas, interpretēt biti atpakaļ simboli.

451
00:38:33,510 --> 00:38:35,880
Un tad beigās, jo mums ir darīšana ar norādes šeit,

452
00:38:35,880 --> 00:38:38,110
Mēs vēlamies, lai pārliecinātos, ka mums nav nekādas atmiņas noplūde

453
00:38:38,110 --> 00:38:41,330
un ka mēs bez maksas viss.

454
00:38:42,820 --> 00:38:46,430
>> Nodrošinot pareizu lietošanu ir vecs cepuru mums līdz šim.

455
00:38:46,430 --> 00:38:51,980
Mēs uztveram ieejas, kas gatavojas būt vārds faila dvesma,

456
00:38:51,980 --> 00:38:56,010
un tad mēs norādiet produkciju,

457
00:38:56,010 --> 00:39:01,580
tāpēc faila nosaukums par miltu produkcijas, kas būs teksta failu.

458
00:39:03,680 --> 00:39:08,820
Tas ir izmantošana. Un tagad mēs vēlamies nodrošināt, lai ievade huffed vai ne.

459
00:39:08,820 --> 00:39:16,420
Atceroties, bija tur kaut kas ar sadales kodu, kas varētu palīdzēt mums

460
00:39:16,420 --> 00:39:21,570
ar sapratni vai fails huffed vai ne?

461
00:39:21,570 --> 00:39:26,910
Tur bija informācija huffile.c par Huffeader.

462
00:39:26,910 --> 00:39:33,430
Mēs zinām, ka katrs Huff fails ir Huffeader saistīti ar to ar burvju numuru

463
00:39:33,430 --> 00:39:37,240
kā arī masīvs par katru simbolu frekvencēm

464
00:39:37,240 --> 00:39:39,570
kā arī kontrolsummu.

465
00:39:39,570 --> 00:39:43,180
Mēs zinām, ka, bet mēs arī ņēma palūrēt dump.c,

466
00:39:43,180 --> 00:39:49,120
kurā tas bija lasījumā par Huff failā.

467
00:39:49,120 --> 00:39:53,990
Un tāpēc, lai izdarītu, bija jāpārbauda, ​​vai tas tiešām bija huffed vai ne.

468
00:39:53,990 --> 00:40:03,380
Tāpēc varbūt mēs varētu izmantot dump.c kā struktūra mūsu puff.c.

469
00:40:03,380 --> 00:40:12,680
Atpakaļ uz 4 PSET kad mums bija failu copy.c ka kopēts RGB trīskāršojas

470
00:40:12,680 --> 00:40:14,860
un mēs interpretē ka detektīvromāns un mainīt,

471
00:40:14,860 --> 00:40:20,390
Tāpat, ko jūs varētu darīt, ir vienkārši palaist komandu, piemēram, cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
un izmantot dažas no koda tur.

473
00:40:23,600 --> 00:40:28,210
Tomēr, tas nav būs tik vienkārši no procesa

474
00:40:28,210 --> 00:40:33,010
tulkošanai savu dump.c vērā puff.c,

475
00:40:33,010 --> 00:40:36,160
bet vismaz tas dod jums kaut kur, lai sāktu

476
00:40:36,160 --> 00:40:40,540
par to, kā nodrošināt, ka ieeja ir faktiski huffed vai ne

477
00:40:40,540 --> 00:40:43,240
kā arī dažas citas lietas.

478
00:40:45,930 --> 00:40:50,250
Mums ir jānodrošina, pareizu izmantošanu un nodrošināja, ka ieeja ir huffed.

479
00:40:50,250 --> 00:40:53,570
Katru reizi, kad mēs esam darījuši, mēs esam darījuši pareizi kļūdu pārbaudi,

480
00:40:53,570 --> 00:41:01,520
tāpēc atgriešanās un atmest šo funkciju, ja kāds sabojājas, ja tur ir problēma.

481
00:41:01,520 --> 00:41:07,170
>> Tagad to, ko mēs vēlamies darīt, ir veidot faktisko koku.

482
00:41:08,840 --> 00:41:12,640
Ja mēs skatāmies Forest, ir 2 galvenās funkcijas

483
00:41:12,640 --> 00:41:15,800
ka mēs esam gatavojas vēlaties kļūt ļoti labi pārzina.

484
00:41:15,800 --> 00:41:23,870
Tur Būla funkcija augs ka augi nav-0 frekvence koku iekšā mūsu mežā.

485
00:41:23,870 --> 00:41:29,250
Un tā tur jums iet ar rādītāju uz mežu un rādītāju uz koku.

486
00:41:32,530 --> 00:41:40,340
Ātrs jautājums: Cik meži būs jums, kad jūs esat celtniecības Huffman koku?

487
00:41:44,210 --> 00:41:46,650
Mūsu mežu ir kā mūsu audekls, labi?

488
00:41:46,650 --> 00:41:50,800
Tātad, mēs esam tikai gatavojas būt 1 mežs, bet mēs esam nāksies vairākus kokus.

489
00:41:50,800 --> 00:41:57,590
Tātad, pirms jūs aicinu augu, jūs, iespējams, gatavojas vēlaties, lai jūsu mežu.

490
00:41:57,590 --> 00:42:04,430
Ir komanda, kas, ja jūs apskatīt forest.h par to, kā jūs varat veikt mežu.

491
00:42:04,430 --> 00:42:09,270
Jūs varat augu koku. Mēs zinām, kā to izdarīt.

492
00:42:09,270 --> 00:42:11,590
Un tad jūs varat arī izvēlēties koku no meža,

493
00:42:11,590 --> 00:42:17,540
noņemot koku ar mazāko svaru un sniedzot jums rādītāju uz to.

494
00:42:17,540 --> 00:42:23,090
Domāšanas atpakaļ, kad mēs darām piemēri sevi,

495
00:42:23,090 --> 00:42:27,980
kad mēs bijām zīmēšanas to ārā, mēs vienkārši vienkārši pievienot saites.

496
00:42:27,980 --> 00:42:31,680
Bet šeit, nevis tikai pievienojot saites,

497
00:42:31,680 --> 00:42:40,630
domā par to vairāk, kā jūs likvidējot 2 no šiem punktiem un tad aizstājot to ar vienu citu.

498
00:42:40,630 --> 00:42:44,200
Paust, ka attiecībā uz picking un stādīšanas,

499
00:42:44,200 --> 00:42:48,840
jūs pacelt 2 koki un tad stādīt citu koku

500
00:42:48,840 --> 00:42:54,060
kas ir tās 2 kokus, kas jums ir palielinājies par bērniem.

501
00:42:57,950 --> 00:43:05,280
Lai izveidotu Huffman ir koks, jūs varat lasīt simbolu un frekvences, lai

502
00:43:05,280 --> 00:43:10,790
jo Huffeader dod, ka jums,

503
00:43:10,790 --> 00:43:14,250
sniedz jums masīvs frekvences.

504
00:43:14,250 --> 00:43:19,660
Tātad jūs varat iet uz priekšu un vienkārši ignorēt kaut ar 0 tajā

505
00:43:19,660 --> 00:43:23,760
jo mēs nevēlamies 256 lapiņas beigās tā.

506
00:43:23,760 --> 00:43:27,960
Mēs tikai vēlamies skaitu lapām, kas ir rakstzīmes

507
00:43:27,960 --> 00:43:31,600
kas ir faktiski izmantoti failā.

508
00:43:31,600 --> 00:43:37,590
Jūs varat lasīt šādu simbolu, un katrs no šiem simboliem, kas ir ārpus 0 frekvences,

509
00:43:37,590 --> 00:43:40,440
tie ir būs koki.

510
00:43:40,440 --> 00:43:45,990
Ko jūs varat darīt, ir katru reizi, kad jūs lasīt bez 0 frekvenču simbolu,

511
00:43:45,990 --> 00:43:50,660
Jūs varat augu, kas koku mežā.

512
00:43:50,660 --> 00:43:56,620
Tiklīdz jūs stādīt kokus mežā, jūs varat pievienoties šos kokus kā vecvecākus,

513
00:43:56,620 --> 00:44:01,130
lai iet atpakaļ uz stādīšanas un pacelt, kur jums izvēlēties 2 un tad augu 1,

514
00:44:01,130 --> 00:44:05,820
ja, ka 1 kas jums augs ir vecāks par 2 bērni, kas jums noplūktiem.

515
00:44:05,820 --> 00:44:11,160
Tātad, tad jūsu gala rezultāts būs viens koks savā mežā.

516
00:44:16,180 --> 00:44:18,170
Tas ir, kā jūs veidot savu koku.

517
00:44:18,170 --> 00:44:21,850
>> Ir vairākas lietas, kas varētu noiet greizi šeit

518
00:44:21,850 --> 00:44:26,580
jo mums ir darīšana ar padarot jaunus kokus un nodarbojas ar norādes un lietām, piemēram, ka.

519
00:44:26,580 --> 00:44:30,450
Pirms kad mēs būtu darīšana ar norādes,

520
00:44:30,450 --> 00:44:36,580
kad mēs malloc'd mēs vēlējāmies, lai pārliecinātos, ka tā nav atgriešanās mums NULL rādītājs vērtību.

521
00:44:36,580 --> 00:44:42,770
Tāpēc vairākos posmos procesa ietvaros ir būs būt vairāki gadījumi

522
00:44:42,770 --> 00:44:45,920
kur jūsu programma varētu neizdoties.

523
00:44:45,920 --> 00:44:51,310
Ko jūs vēlaties darīt, ir jūs vēlaties, lai pārliecinātos, ka jūs rīkoties šīs kļūdas,

524
00:44:51,310 --> 00:44:54,580
un spec saka rīkoties ar tām graciozi,

525
00:44:54,580 --> 00:45:00,280
tāpēc gribētu izdrukāt ziņu lietotājam stāstīt viņiem, kāpēc programma ir atmest

526
00:45:00,280 --> 00:45:03,050
un tad nekavējoties atmest to.

527
00:45:03,050 --> 00:45:09,490
Lai veiktu šo kļūdu apstrādi, atcerieties, ka jūs vēlaties, lai pārbaudītu to

528
00:45:09,490 --> 00:45:12,160
katru reizi, ka tur varētu būt neveiksme.

529
00:45:12,160 --> 00:45:14,660
Katru reizi, kad jūs gūstat jaunu rādītāju

530
00:45:14,660 --> 00:45:17,040
Jūs vēlaties, lai pārliecinātos, ka tas ir veiksmīgs.

531
00:45:17,040 --> 00:45:20,320
Pirms ko mēs izmantojām darīt, ir veikt jaunu rādītāju un malloc to,

532
00:45:20,320 --> 00:45:22,380
un tad mēs varētu pārbaudīt, vai šis rādītājs ir NULL.

533
00:45:22,380 --> 00:45:25,670
Tātad ir būs daži gadījumi, kad jūs varat vienkārši darīt, ka,

534
00:45:25,670 --> 00:45:28,610
bet reizēm jūs faktiski aicinot funkciju

535
00:45:28,610 --> 00:45:33,100
un šajā funkciju, tas ir viens, kas dara šo mallocing.

536
00:45:33,100 --> 00:45:39,110
Šajā gadījumā, ja mēs atskatāmies uz kādu no funkcijām kodā,

537
00:45:39,110 --> 00:45:42,260
daži no tiem ir Būla funkcijas.

538
00:45:42,260 --> 00:45:48,480
Jo abstraktu gadījumā, ja mums ir Būla funkciju sauc foo,

539
00:45:48,480 --> 00:45:54,580
Būtībā, mēs varam pieņemt, ka papildus dara visu foo dara,

540
00:45:54,580 --> 00:45:57,210
jo tas ir Būla funkcija, tā atgriež patiess vai nepatiess -

541
00:45:57,210 --> 00:46:01,300
taisnība, ja veiksmīga, false, ja nav.

542
00:46:01,300 --> 00:46:06,270
Tāpēc mēs vēlamies, lai pārbaudītu, vai atgriešanās vērtību foo ir patiess vai nepatiess.

543
00:46:06,270 --> 00:46:10,400
Ja tas ir nepatiess, tas nozīmē, ka mēs spēsim vēlaties izdrukāt kādu ziņu

544
00:46:10,400 --> 00:46:14,390
un tad atmest programmu.

545
00:46:14,390 --> 00:46:18,530
Ko mēs vēlamies darīt, ir pārbaudīt atgriezto vērtību foo.

546
00:46:18,530 --> 00:46:23,310
Ja foo atgriež nepatiess, tad mēs zinām, ka mums radās sava veida kļūda

547
00:46:23,310 --> 00:46:25,110
un mums vajag atmest mūsu programmu.

548
00:46:25,110 --> 00:46:35,600
Veids, kā to izdarīt, ir ir slimība, kad faktiskā funkcija pati ir Jūsu stāvoklis.

549
00:46:35,600 --> 00:46:39,320
Say foo uzņem x.

550
00:46:39,320 --> 00:46:43,390
Mēs varam būt par nosacījumu, ja (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Būtībā, tas nozīmē, ka, ja gada beigās izpildes foo tas atgriež taisnība,

552
00:46:50,900 --> 00:46:57,390
tad mēs varam darīt, jo funkcija ir izvērtēt foo

553
00:46:57,390 --> 00:47:00,500
lai novērtētu visu stāvokli.

554
00:47:00,500 --> 00:47:06,500
Tātad, tad tas, kā jūs varat kaut ko darīt, ja funkcija atgriež patiess un ir veiksmīga.

555
00:47:06,500 --> 00:47:11,800
Bet, kad tu esi kļūdu pārbaude, jūs tikai vēlas atmest, ja jūsu funkcija atgriež nepatiess.

556
00:47:11,800 --> 00:47:16,090
Ko jūs varētu darīt, ir vienkārši pievienot == nepatiess vai vienkārši pievienot sprādziena tā priekšā

557
00:47:16,090 --> 00:47:21,010
un tad jums ir, ja (! foo).

558
00:47:21,010 --> 00:47:29,540
Šajā institūcijā šī nosacījuma jūs būtu visu kļūdu apstrādi,

559
00:47:29,540 --> 00:47:36,940
tā patīk, "Nevar izveidot šo koku" un pēc tam atgriezties 1 vai kaut kas tamlīdzīgs.

560
00:47:36,940 --> 00:47:43,340
Ko tas dara, lai gan, ir tas, ka pat ja foo atgriezās nepatiess -

561
00:47:43,340 --> 00:47:46,980
Say foo atgriež taisnība.

562
00:47:46,980 --> 00:47:51,060
Tad jums nav, lai izsauktu foo vēlreiz. Tas ir kopīgs nepareizs.

563
00:47:51,060 --> 00:47:54,730
Jo tas bija jūsu stāvoklī, tas jau jāizvērtē,

564
00:47:54,730 --> 00:47:59,430
tāpēc jums jau ir rezultāts, ja jūs izmantojat veikt koku vai kaut kas tamlīdzīgs

565
00:47:59,430 --> 00:48:01,840
vai augu vai pick vai kaut.

566
00:48:01,840 --> 00:48:07,460
Tas jau ir šo vērtību. Tas jau izpildīts.

567
00:48:07,460 --> 00:48:10,730
Tātad, tas ir lietderīgi izmantot Būla funkcijas kā nosacījumu

568
00:48:10,730 --> 00:48:13,890
jo vai jūs faktiski izpildīt ķermeņa cilpas,

569
00:48:13,890 --> 00:48:18,030
tā izpilda funkciju vienalga.

570
00:48:22,070 --> 00:48:27,330
>> Mūsu otrais pēdējais solis ir rakstīt ziņu uz failu.

571
00:48:27,330 --> 00:48:33,070
Kad mēs veidojam Huffman koku, tad rakstot ziņu uz failu, ir diezgan vienkārši.

572
00:48:33,070 --> 00:48:39,260
Tas ir diezgan vienkārši, tagad vienkārši sekot 0s un 1s.

573
00:48:39,260 --> 00:48:45,480
Un tā pēc vienošanās mēs zinām, ka ir Huffman Tree 0s norāda uz kreisās

574
00:48:45,480 --> 00:48:48,360
un 1s norāda tiesības.

575
00:48:48,360 --> 00:48:53,540
Tātad tad, ja jūs lasīt pamazām, katru reizi, jums ir 0

576
00:48:53,540 --> 00:48:59,100
jūs sekot kreiso filiāli, un tad katru reizi, kad jūs lasīt ir 1

577
00:48:59,100 --> 00:49:02,100
jūs gatavojas sekot pareizo filiāli.

578
00:49:02,100 --> 00:49:07,570
Un tad jūs gatavojas turpināt līdz jūs hit lapu

579
00:49:07,570 --> 00:49:11,550
jo lapas ir būs beigās filiālēm.

580
00:49:11,550 --> 00:49:16,870
Kā mēs varam pateikt, vai mēs esam hit lapu vai ne?

581
00:49:19,800 --> 00:49:21,690
Mēs teicām agrāk.

582
00:49:21,690 --> 00:49:24,040
[Students] Ja norādes ir NULL. >> Jā.

583
00:49:24,040 --> 00:49:32,220
Mēs varam pateikt, ja mēs esam hit lapu, ja norādes gan uz kreiso un labo koki ir NULL.

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

585
00:49:34,110 --> 00:49:40,320
Mēs zinām, ka mēs vēlamies lasīt pamazām mūsu Huff failā.

586
00:49:43,870 --> 00:49:51,220
Kā mēs redzējām agrāk dump.c, ko viņi darīja, ir viņi lasa pamazām uz Huff failā

587
00:49:51,220 --> 00:49:54,560
un vienkārši izdrukāt, kādi ir šie biti bija.

588
00:49:54,560 --> 00:49:58,430
Mēs neesam gatavojas darīt to. Mēs ejam, lai darīt kaut ko, kas ir nedaudz sarežģītāka.

589
00:49:58,430 --> 00:50:03,620
Bet tas, ko mēs varam darīt, ir, mēs varam pieņemt, ka mazliet kodu, kas skan uz biti.

590
00:50:03,620 --> 00:50:10,250
Šeit mums ir veselu mazliet raksturo kārtējo mazliet, ka mēs esam par.

591
00:50:10,250 --> 00:50:15,520
Tas rūpējas par atkārtojot visu lietas materiālos bitu līdz jūs hit beigām failu.

592
00:50:15,520 --> 00:50:21,270
Balstoties uz to, tad jūs gatavojas vēlaties, lai būtu sava veida iterator

593
00:50:21,270 --> 00:50:26,760
traversa savu koku.

594
00:50:26,760 --> 00:50:31,460
Un tad, pamatojoties uz to, vai bits ir 0 vai 1,

595
00:50:31,460 --> 00:50:36,920
jūs gatavojas vēlaties, lai nu pārvietot, ka iterator pa kreisi vai pārvietot to uz pareizā

596
00:50:36,920 --> 00:50:44,080
galam, līdz jūs hit lapiņu, tāpēc visu ceļu līdz šim mezglam, ka jūs par

597
00:50:44,080 --> 00:50:48,260
nenorāda uz kādu vairāk mezglu.

598
00:50:48,260 --> 00:50:54,300
Kāpēc mēs varam izdarīt ar Huffman failu, bet ne Morzes kodu?

599
00:50:54,300 --> 00:50:56,610
Jo Morzes kodu tur mazliet neskaidrības.

600
00:50:56,610 --> 00:51:04,440
Mēs varētu būt, piemēram, ak jāgaida, mēs esam hit vēstuli pa ceļu, tāpēc varbūt tas ir mūsu vēstule,

601
00:51:04,440 --> 00:51:08,150
tā kā, ja mēs turpinājās tikai mazliet ilgāk, tad mēs būtu hit citu vēstuli.

602
00:51:08,150 --> 00:51:13,110
Bet tas nav gatavojas notikt Huffman kodēšanas,

603
00:51:13,110 --> 00:51:17,540
lai mēs varētu būt droši, ka vienīgais veids, ka mēs ejam, lai hit raksturs

604
00:51:17,540 --> 00:51:23,480
ir tad, ja šis mezgls ir pa kreisi un pa labi bērni ir NULL.

605
00:51:28,280 --> 00:51:32,350
>> Visbeidzot, mēs gribam, lai atbrīvotu visas mūsu atmiņas.

606
00:51:32,350 --> 00:51:37,420
Mēs vēlamies, lai gan gandrīz Huff failu, ka mēs esam bijuši saistīti ar

607
00:51:37,420 --> 00:51:41,940
kā arī noņemt visus mūsu meža kokiem.

608
00:51:41,940 --> 00:51:46,470
Pamatojoties uz jūsu īstenošanu, jūs, iespējams, gatavojas vēlaties, lai izsauktu noņemt mežs

609
00:51:46,470 --> 00:51:49,780
nevis faktiski iet cauri visiem kokiem pats.

610
00:51:49,780 --> 00:51:53,430
Bet, ja jūs veicāt kādas pagaidu koki, jūs vēlaties, lai atbrīvotu to.

611
00:51:53,430 --> 00:51:59,060
Jūs zināt savu kodu vislabāk, lai jūs zināt, kur tu esi piešķirot atmiņu.

612
00:51:59,060 --> 00:52:04,330
Un tā, ja jūs iet, jāsāk ar pat kontroles F'ing par malloc,

613
00:52:04,330 --> 00:52:08,330
redzot, kad jūs malloc un pārliecinoties, ka jūs bez visiem, kas

614
00:52:08,330 --> 00:52:10,190
bet tad tikai iet caur savu kodu,

615
00:52:10,190 --> 00:52:14,260
sapratni kur jūs varētu būt piešķirti atmiņu.

616
00:52:14,260 --> 00:52:21,340
Parasti jūs varētu vienkārši pateikt: "Pēc faila es esmu tikai gatavojas likvidēt mežu manā mežā,"

617
00:52:21,340 --> 00:52:23,850
tāpēc būtībā skaidrs, ka atmiņas, bezmaksas ka,

618
00:52:23,850 --> 00:52:28,310
", Un tad es esmu arī gatavojas slēgt lietu, un tad mana programma gatavojas pamest."

619
00:52:28,310 --> 00:52:33,810
Bet ir tā, ka tikai laiks, ka jūsu programma aizveras?

620
00:52:33,810 --> 00:52:37,880
Nē, jo dažreiz tur varētu būt kļūda, kas noticis.

621
00:52:37,880 --> 00:52:42,080
Varbūt mēs nevarējām atvērt failu vai mēs nevarētu veikt citu koku

622
00:52:42,080 --> 00:52:49,340
vai kādu kļūdu veida noticis atmiņas sadales procesu un tā tas atgriezās NULL.

623
00:52:49,340 --> 00:52:56,710
Kļūda notika, un tad mēs atgriezāmies un atmest.

624
00:52:56,710 --> 00:53:02,040
Tātad, tad jūs vēlaties, lai pārliecinātos, ka jebkurš iespējamais laiks, ka jūsu programma var atmest,

625
00:53:02,040 --> 00:53:06,980
Jūs vēlaties, lai atbrīvotu visu savu atmiņu tur.

626
00:53:06,980 --> 00:53:13,370
Tas nav tikai būs pašās beigās no galvenā funkcija, kas jūs atmest savu kodu.

627
00:53:13,370 --> 00:53:20,780
Jūs vēlaties, lai atskatītos uz katru piemēram, ka kods potenciāli varētu atgriezties priekšlaicīgi

628
00:53:20,780 --> 00:53:25,070
un tad bez jebkāda atmiņas jēga.

629
00:53:25,070 --> 00:53:30,830
Say jums bija aicinājis veikt mežu un atgriezās nepatiess.

630
00:53:30,830 --> 00:53:34,230
Tad jūs, iespējams, nebūs nepieciešams, lai novērstu jūsu mežs

631
00:53:34,230 --> 00:53:37,080
jo jums nav mežs vēl.

632
00:53:37,080 --> 00:53:42,130
Bet katrā brīdī kodu, kur jūs varētu atgriezties priekšlaicīgi

633
00:53:42,130 --> 00:53:46,160
Jūs vēlaties pārliecināties, ka jūs bez jebkādas iespējamās atmiņu.

634
00:53:46,160 --> 00:53:50,020
>> Tātad, ja mums ir darīšana ar atbrīvojot atmiņu un kam iespējamos noplūdes,

635
00:53:50,020 --> 00:53:55,440
Mēs vēlamies ne tikai izmantot savu spriedumu un mūsu loģika

636
00:53:55,440 --> 00:54:01,850
bet arī izmantot Valgrind lai noteiktu, vai mēs esam atbrīvojušies visas mūsu atmiņas pareizi vai ne.

637
00:54:01,850 --> 00:54:09,460
Jūs varat vai nu palaist Valgrind par Puff un tad jums ir, lai arī nodot to

638
00:54:09,460 --> 00:54:14,020
Tiesības skaits komandrindas argumentus Valgrind.

639
00:54:14,020 --> 00:54:18,100
Jūs varat palaist to, bet rezultāts ir mazliet noslēpumains.

640
00:54:18,100 --> 00:54:21,630
Mēs esam gotten mazliet izmanto, lai to ar Speller, bet mums vēl mazliet vairāk palīdzēt,

641
00:54:21,630 --> 00:54:26,450
tā tad rādīt to ar vēl pāris karogiem piemēram noplūdes pārbaudīt = pilns,

642
00:54:26,450 --> 00:54:32,040
kas, iespējams, dotu mums kādu vairāk noderīgi produkciju Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Tad vēl viens noderīgs padoms, ja jūs atkļūdošana ir diff komandu.

644
00:54:39,040 --> 00:54:48,520
Jūs varat piekļūt personāla ieviešanu Huff, palaist, ka uz teksta failu,

645
00:54:48,520 --> 00:54:55,400
un tad izejas to uz bināro failu, binārā Huff failu, ir īpaša.

646
00:54:55,400 --> 00:54:59,440
Tad, ja jūs vadāt savu dvesma par šo bināro failu,

647
00:54:59,440 --> 00:55:03,950
tad ideāli, jūsu izvadīt teksta fails būs identiski

648
00:55:03,950 --> 00:55:08,200
ar sākotnējo vienu, ka jūs pagājis collas

649
00:55:08,200 --> 00:55:15,150
Šeit es esmu, izmantojot hth.txt kā piemērs, un tas ir viens runāja par jūsu spec.

650
00:55:15,150 --> 00:55:21,040
Tas ir burtiski tikai HTH un tad newline.

651
00:55:21,040 --> 00:55:30,970
Bet noteikti justies brīvi un jūs noteikti aicināti izmantot garākus piemērus

652
00:55:30,970 --> 00:55:32,620
Jūsu teksta failu.

653
00:55:32,620 --> 00:55:38,110
>> Jūs pat varat veikt nošauta pie varbūt saspiežot un tad decompressing

654
00:55:38,110 --> 00:55:41,600
dažas lietas, kas jums izmanto Speller piemēram Karš un miers

655
00:55:41,600 --> 00:55:46,710
vai Džeinas Ostinas vai kaut kas tamlīdzīgs - tas būtu veida atdzist - vai Austin Powers,

656
00:55:46,710 --> 00:55:51,880
veida nodarbojas ar lielākiem failiem, jo ​​mēs nebūtu nonākuši pie tā

657
00:55:51,880 --> 00:55:55,590
ja mēs izmantojām nākamo rīku šeit, Ls-l.

658
00:55:55,590 --> 00:56:01,150
Mēs esam izmanto ls, kas būtībā ir uzskaitītas visas saturu mūsu pašreizējā direktorijā.

659
00:56:01,150 --> 00:56:07,860
Aizrit karoga-l faktiski parāda lielumu šiem failiem.

660
00:56:07,860 --> 00:56:12,690
Ja jūs iet cauri PSET spec, tas tiešām iet jums pa izveidojot bināro failu,

661
00:56:12,690 --> 00:56:16,590
gada huffing to, un jūs redzēsiet, ka ļoti maziem failiem

662
00:56:16,590 --> 00:56:23,910
telpa izmaksas saspiežot to un tulkojot visu šo informāciju

663
00:56:23,910 --> 00:56:26,980
visu frekvenču un lietām, piemēram, ka atsver faktiskais ieguvums

664
00:56:26,980 --> 00:56:30,000
saspiežot failu pirmajā vietā.

665
00:56:30,000 --> 00:56:37,450
Bet, ja jūs palaist to uz dažām ilgāka teksta failus, tad jūs varētu redzēt, ka jūs sākat, lai saņemtu kādu labumu

666
00:56:37,450 --> 00:56:40,930
saspiežot šos failus.

667
00:56:40,930 --> 00:56:46,210
>> Un tad beidzot, mums ir mūsu vecā draugs GDB, kas ir noteikti gatavojas noderēs pārāk.

668
00:56:48,360 --> 00:56:55,320
>> Vai mums ir kādi jautājumi par Huff kokiem vai process varbūt padarīt kokus

669
00:56:55,320 --> 00:56:58,590
vai kādi citi jautājumi par Huff'n Puff?

670
00:57:00,680 --> 00:57:02,570
Labi. Es palikšu apkārt mazliet.

671
00:57:02,570 --> 00:57:06,570
>> Paldies, visiem. Tas bija Walkthrough 6. Un labu veiksmi.

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