1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Walkthrough - Проблем Постави 6]

2
00:00:02,210 --> 00:00:04,810
[Zamyla Чан - Универзитетот Харвард]

3
00:00:04,810 --> 00:00:07,240
[Ова е CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Здраво на сите, и добредојде на можи 6: Huff'n издувам.

5
00:00:12,180 --> 00:00:17,440
Во Huff'n издувам она што го правиме нема да се занимаваат со Хафман компресирана датотека

6
00:00:17,440 --> 00:00:20,740
а потоа puffing го врати, така што декомпресија,

7
00:00:20,740 --> 00:00:25,810
така што ние може да го преведе од 0-ти и 1S дека корисникот испраќа нас

8
00:00:25,810 --> 00:00:30,660
и го претвори назад во оригиналниот текст.

9
00:00:30,660 --> 00:00:34,360
Pset 6 ќе биде прилично кул бидејќи ви се случува да видите некои од алатките

10
00:00:34,360 --> 00:00:41,730
што ќе се користи во pset 4 и pset 5 и вид на комбинирајќи ги во 1 прилично уредни концепт

11
00:00:41,730 --> 00:00:43,830
кога ќе дојде да се размислува за тоа.

12
00:00:43,830 --> 00:00:50,110
>> Исто така, веројатно, pset 4 и 5 беа најголемиот предизвик psets што моравме да понуди.

13
00:00:50,110 --> 00:00:53,950
Значи од сега, имаме ова уште 1 pset во C,

14
00:00:53,950 --> 00:00:56,480
а потоа после тоа ние сме на за веб програмирање.

15
00:00:56,480 --> 00:01:02,310
Значи себе честитам за добивање на над најтешките грпка во CS50.

16
00:01:03,630 --> 00:01:09,760
>> Преселба на за Huff'n издувам, нашите алатникот за овој pset ќе бидат Хафман дрвја,

17
00:01:09,760 --> 00:01:14,700
така разбирање не само како бинарни дрва работа, но, исто така, посебно Хафман дрвја,

18
00:01:14,700 --> 00:01:16,240
како тие се изградени.

19
00:01:16,240 --> 00:01:20,210
А потоа ние ќе имаме многу дистрибуција код во овој pset,

20
00:01:20,210 --> 00:01:22,480
и ние ќе дојдат да се види дека всушност некои од кодот

21
00:01:22,480 --> 00:01:24,670
ние не би можеле да бидат во можност да се разбере целосно уште,

22
00:01:24,670 --> 00:01:30,080
и така тие ќе бидат. в датотеки, но потоа нивните придружни. ж датотеки

23
00:01:30,080 --> 00:01:34,300
ќе ни даде доволно разбирање дека ние треба, така што ние знаеме како тие функции работат

24
00:01:34,300 --> 00:01:38,100
или барем она што тие треба да се направи - нивните влезови и излези -

25
00:01:38,100 --> 00:01:40,760
дури и ако не знаеме што се случува во црна кутија

26
00:01:40,760 --> 00:01:44,090
или не го разбираат она што се случува во црната кутија во рамките.

27
00:01:44,090 --> 00:01:49,400
А потоа конечно, како и обично, ние се справуваме со новите структури на податоци,

28
00:01:49,400 --> 00:01:51,840
одредени видови на јазли кои укажуваат на некои работи,

29
00:01:51,840 --> 00:01:56,080
и така тука има пенкало и хартија не само за процесот на дизајн

30
00:01:56,080 --> 00:01:58,470
и кога ќе се обидуваш да дознаам како вашиот pset треба да работат

31
00:01:58,470 --> 00:02:00,520
но исто така и за време на дебагирање.

32
00:02:00,520 --> 00:02:06,140
Можете да имаат GDB заедно со вашиот пенкало и хартија додека ве однесе долу она што вредностите се,

33
00:02:06,140 --> 00:02:09,320
каде се вашите стрели се укажува, и работи како што.

34
00:02:09,320 --> 00:02:13,720
>> Прво нека се погледне на Хафман дрвја.

35
00:02:13,720 --> 00:02:19,600
Хафман дрва се бинарни дрва, што значи дека секој јазол има само 2 деца.

36
00:02:19,600 --> 00:02:24,870
Во Хафман дрвја карактеристика е дека најчести вредности

37
00:02:24,870 --> 00:02:27,140
се претставени со најмалку бита.

38
00:02:27,140 --> 00:02:32,690
Ние видовме во предавање примери на Morse code, кој вид на консолидиран некои букви.

39
00:02:32,690 --> 00:02:38,030
Ако се обидуваш да се преведе А или Е, на пример,

40
00:02:38,030 --> 00:02:43,940
сте преведување дека често, па наместо да се користи целосен сет на битови

41
00:02:43,940 --> 00:02:48,640
наменети за таа вообичаените тип на податоци, ќе го компресира до помалку,

42
00:02:48,640 --> 00:02:53,730
а потоа тие писма кои се претставени помалку често се претставени со повеќе битови

43
00:02:53,730 --> 00:02:59,840
затоа што може да си го дозволи тоа кога ќе тежат од фреквенциите кои тие букви.

44
00:02:59,840 --> 00:03:03,020
Имаме иста идеја тука во Хафман дрва

45
00:03:03,020 --> 00:03:12,360
каде што се прави еден синџир, еден вид на патот да се дојде до одредени карактери.

46
00:03:12,360 --> 00:03:14,470
А потоа на ликовите, кои имаат најмногу фреквенција

47
00:03:14,470 --> 00:03:17,940
се случува да бидат застапени со најмалку бита.

48
00:03:17,940 --> 00:03:22,020
>> Начинот на кој ќе се изгради дрво Хафман

49
00:03:22,020 --> 00:03:27,430
е со ставање на сите ликови кои се појавуваат во текстот

50
00:03:27,430 --> 00:03:30,630
и пресметување на нивната фреквенција, колку често тие се појавуваат.

51
00:03:30,630 --> 00:03:33,880
Ова или може да биде брои колку пати се појавуваат тие писма

52
00:03:33,880 --> 00:03:40,270
или можеби процент од надвор на сите ликови колку секој од нив се појавува.

53
00:03:40,270 --> 00:03:44,270
И така она што го правите е еднаш имате сето тоа одбележан,

54
00:03:44,270 --> 00:03:49,060
тогаш ќе се погледне за 2 најниска фреквенции, а потоа им се придружи како браќа и сестри

55
00:03:49,060 --> 00:03:55,660
каде тогаш родителот јазол има фреквенција која е збир на 2 деца.

56
00:03:55,660 --> 00:04:00,870
И тогаш од конвенцијата велат дека левата јазол,

57
00:04:00,870 --> 00:04:03,770
те следам дека со следење на 0 гранка,

58
00:04:03,770 --> 00:04:08,140
а потоа најдесната јазол е 1 гранка.

59
00:04:08,140 --> 00:04:16,040
Како што видовме во Morse code, оној gotcha беше дека ако сте имале само звучен сигнал и сигнал

60
00:04:16,040 --> 00:04:18,120
тоа е двосмислена.

61
00:04:18,120 --> 00:04:22,430
Тоа или би можел да биде 1 писмо или тоа би можело да биде низа од 2 букви.

62
00:04:22,430 --> 00:04:27,790
И уште па што Хафман дрвја не е затоа што по природа на ликовите

63
00:04:27,790 --> 00:04:34,140
или нашата крајна вистински ликови се последните јазли на гранка -

64
00:04:34,140 --> 00:04:39,300
ние се однесува на оние што лисја - врз основа на тоа што таму не може да биде било двосмисленост

65
00:04:39,300 --> 00:04:45,160
во однос на која буква ти се обидуваш да се кодираат со серија на битови

66
00:04:45,160 --> 00:04:50,670
бидејќи никаде по битови кои претставуваат 1 писмо

67
00:04:50,670 --> 00:04:55,960
ќе се судрите со друг целиот писмо, и нема да има никаква забуна таму.

68
00:04:55,960 --> 00:04:58,430
Но, ние ќе одиме во примери кои вие момци всушност може да се види дека

69
00:04:58,430 --> 00:05:02,120
наместо нас само ти кажувам дека тоа е вистина.

70
00:05:02,120 --> 00:05:06,390
>> Да ги погледнеме во едноставен пример на едно дрво Хафман.

71
00:05:06,390 --> 00:05:09,380
Имам низа тука дека е 12 карактери.

72
00:05:09,380 --> 00:05:14,010
Имам 4 Како, 6 БС, и 2 CS.

73
00:05:14,010 --> 00:05:17,270
Мојот прв чекор ќе биде да се избројат.

74
00:05:17,270 --> 00:05:20,760
Колку пати ли се појави? Се чини 4 пати во низа.

75
00:05:20,760 --> 00:05:25,060
Б појавува 6 пати, и C се појавува 2 пати.

76
00:05:25,060 --> 00:05:28,970
Секако, јас одам да се каже јас сум користење на Б најчесто,

77
00:05:28,970 --> 00:05:35,970
па сакам да претставуваат Б со најмали број на битови, најмалку бројот на 0-ти и 1S.

78
00:05:35,970 --> 00:05:42,600
И тогаш јас сум исто така, ќе се очекува C до потреба од поголемиот износ на 0-ти и 1S, како и.

79
00:05:42,600 --> 00:05:48,550
Прво она што го направив тука е ги стави во растечки редослед во однос на фреквенцијата.

80
00:05:48,550 --> 00:05:52,710
Гледаме дека Ц и А, тие се нашите 2 најниска фреквенции.

81
00:05:52,710 --> 00:06:00,290
Ние создаваме родител јазол, и тој родител јазол нема писмо поврзани со неа,

82
00:06:00,290 --> 00:06:05,070
но тоа не мора фреквенција, која е сума.

83
00:06:05,070 --> 00:06:08,780
Збирот станува 2 + 4, што е 6.

84
00:06:08,780 --> 00:06:10,800
Потоа ние ја следиме левата гранка.

85
00:06:10,800 --> 00:06:14,970
Ако бевме во тоа 6 јазол, тогаш ние ќе ги следиме 0 за да стигнат до C

86
00:06:14,970 --> 00:06:17,450
а потоа 1 да се дојде до А

87
00:06:17,450 --> 00:06:20,300
Така, сега имаме 2 јазли.

88
00:06:20,300 --> 00:06:23,920
Имаме вредност 6 а потоа ние исто така имаат друг јазол со вредност 6.

89
00:06:23,920 --> 00:06:28,550
И така тие 2 не се само 2 најниска но, исто така, само 2 кои се оставени,

90
00:06:28,550 --> 00:06:33,820
па ние се придружи на оние од друг родител, со сума е 12.

91
00:06:33,820 --> 00:06:36,300
Значи тука имаме Хафман дрво

92
00:06:36,300 --> 00:06:40,020
каде да се дојде до Б, тоа само ќе биде малку 1

93
00:06:40,020 --> 00:06:45,430
а потоа да се дојде до ќе имаме 01 и тогаш C со 00.

94
00:06:45,430 --> 00:06:51,300
Па овде можеме да видиме дека во основа ние сме претставуваат овие знаци со 1 или 2 парчиња

95
00:06:51,300 --> 00:06:55,160
каде Б, како што е предвидено, има најмалку.

96
00:06:55,160 --> 00:07:01,730
И тогаш бевме очекува C да имаат најмногу, но бидејќи тоа е толку мал Хафман дрво,

97
00:07:01,730 --> 00:07:06,020
тогаш А е исто така застапени од 2 парчиња, за разлика некаде во средината.

98
00:07:07,820 --> 00:07:11,070
>> Само за да поминат уште едноставен пример на дрвото Хафман,

99
00:07:11,070 --> 00:07:19,570
велат дека имаат низа "Здраво".

100
00:07:19,570 --> 00:07:25,360
Она што го правите е прв ќе каже колку пати ги H појави во ова?

101
00:07:25,360 --> 00:07:34,200
H појавува еднаш, а потоа е се појавува еднаш и потоа имаме l појавува двапати

102
00:07:34,200 --> 00:07:36,580
и o појавува еднаш.

103
00:07:36,580 --> 00:07:44,310
И така тогаш ние очекуваме која писмо да биде претставен од страна на најмал број на битови?

104
00:07:44,310 --> 00:07:47,450
[Студент] л. >> L. Да. l е во право.

105
00:07:47,450 --> 00:07:50,730
Очекуваме л да бидат застапувани од најмалку бројот на битови

106
00:07:50,730 --> 00:07:55,890
бидејќи л се користи најмногу во низа "Здраво".

107
00:07:55,890 --> 00:08:04,280
Она што јас ќе одам да направите сега е да извлечеш овие јазли.

108
00:08:04,280 --> 00:08:15,580
Имам 1, кој е H, а потоа уште 1, кој е e, а потоа 1, кој е o -

109
00:08:15,580 --> 00:08:23,410
право сега сум ги стави во ред - и потоа 2, кој е л.

110
00:08:23,410 --> 00:08:32,799
Тогаш велам начинот на кој јас се изгради дрво Хафман е да се најде 2 јазли со најмалку фреквенции

111
00:08:32,799 --> 00:08:38,010
и ги направи браќа и сестри, преку создавање на родител јазол.

112
00:08:38,010 --> 00:08:41,850
Тука имаме 3 јазли со најниска фреквенција. Сите тие се 1.

113
00:08:41,850 --> 00:08:50,620
Па еве ние се избере една која ние ќе водат во прв план.

114
00:08:50,620 --> 00:08:54,850
Да речеме јас го избере H и e.

115
00:08:54,850 --> 00:09:01,150
Збирот на 1 + 1 е 2, но овој јазол не мора писмо поврзани со неа.

116
00:09:01,150 --> 00:09:04,440
Тоа само држи вредност.

117
00:09:04,440 --> 00:09:10,950
Сега ќе погледнеме во следните 2 најниска фреквенции.

118
00:09:10,950 --> 00:09:15,590
Тоа е 2 и 1. Тоа може да биде било кој од овие 2, но јас ќе одам да се избере оваа.

119
00:09:15,590 --> 00:09:18,800
Сумата е 3.

120
00:09:18,800 --> 00:09:26,410
А потоа конечно, ми останува само 2 лево, па тогаш што станува 5.

121
00:09:26,410 --> 00:09:32,010
Потоа тука, како што се очекува, ако се пополнат кодирање за тоа,

122
00:09:32,010 --> 00:09:37,480
1s се секогаш на правото гранка и 0-ти се левата.

123
00:09:37,480 --> 00:09:45,880
Тогаш имаме l претставен од само 1 бит а потоа о од 2

124
00:09:45,880 --> 00:09:52,360
и тогаш е со 2, а потоа H паѓа до 3 бита.

125
00:09:52,360 --> 00:09:59,750
Така може да се пренесе оваа порака "Здраво", наместо всушност користење на карактери

126
00:09:59,750 --> 00:10:02,760
од само 0-ти и 1S.

127
00:10:02,760 --> 00:10:07,910
Сепак, не заборавајте дека во неколку случаи имаше врски со нашите фреквенција.

128
00:10:07,910 --> 00:10:11,900
Ние би можеле да имаат или се приклучија на H и о првиот можеби.

129
00:10:11,900 --> 00:10:15,730
Или потоа подоцна кога имавме l претставен од 2

130
00:10:15,730 --> 00:10:19,410
како и се приклучија една претставена со 2, ние може да се поврзани ниту една.

131
00:10:19,410 --> 00:10:23,630
>> И така, кога ви испратиме 0-ти и 1S, кои, всушност, не е гаранција

132
00:10:23,630 --> 00:10:27,090
дека примачот може целосно да ја прочита вашата порака право надвор од лилјак

133
00:10:27,090 --> 00:10:30,490
затоа што тие не би можеле да знаат што одлуката сте го направиле.

134
00:10:30,490 --> 00:10:34,920
Значи, кога ние сме се занимаваат со Хафман компресија,

135
00:10:34,920 --> 00:10:40,090
некако мора да се каже примателот на нашата порака како решивме -

136
00:10:40,090 --> 00:10:43,470
Тие треба да знаат некој вид на дополнителни информации

137
00:10:43,470 --> 00:10:46,580
во прилог на пораката компресирана.

138
00:10:46,580 --> 00:10:51,490
Тие треба да се разбере она дрво, всушност, изгледа,

139
00:10:51,490 --> 00:10:55,450
како ние всушност направени тие одлуки.

140
00:10:55,450 --> 00:10:59,100
>> Тука бевме само прави примери врз основа на реалните брои,

141
00:10:59,100 --> 00:11:01,550
но понекогаш ти исто така може да има дрво Хафман

142
00:11:01,550 --> 00:11:05,760
врз основа на фреквенцијата на која букви, и тоа е точно истиот процес.

143
00:11:05,760 --> 00:11:09,090
Еве јас сум го изразува во однос на проценти или дел,

144
00:11:09,090 --> 00:11:11,290
и така тука иста работа.

145
00:11:11,290 --> 00:11:15,300
Сметам дека 2 најниска, сумира нив, наредните 2 најниска, ги сумира,

146
00:11:15,300 --> 00:11:19,390
додека имам целосна дрво.

147
00:11:19,390 --> 00:11:23,610
Иако би можеле да го направи тоа во секој случај, кога ние сме се занимаваат со процентите,

148
00:11:23,610 --> 00:11:27,760
тоа значи дека ние сме дели работи и кои се занимаваат со децимали или подобро кажано лебди

149
00:11:27,760 --> 00:11:30,900
ако ние сме размислување за структури на податоци на главата.

150
00:11:30,900 --> 00:11:32,540
Што знаеме за плови?

151
00:11:32,540 --> 00:11:35,180
Што е заеднички проблем кога ние сме се занимаваат со лебди?

152
00:11:35,180 --> 00:11:38,600
[Студент] непрецизна аритметика. >> Да. Непрецизност.

153
00:11:38,600 --> 00:11:43,760
Поради подвижна запирка непрецизност, за овој pset така што можеме да бидете сигурни

154
00:11:43,760 --> 00:11:49,450
дека ние не губат сите вредности, тогаш ние всушност ќе треба да се занимаваат со пребројувањето на гласовите.

155
00:11:49,450 --> 00:11:54,880
Значи, ако сте во ситуација да мислам на еден јазол Хафман, ако се погледне назад на структурата тука,

156
00:11:54,880 --> 00:12:01,740
ако се погледне на зелени оние има фреквенција поврзани со неа

157
00:12:01,740 --> 00:12:08,760
како и тоа укажува на еден јазол до неговата лева, како и јазол своето право.

158
00:12:08,760 --> 00:12:13,970
А потоа црвени таму, исто така, имаат карактер поврзани со нив.

159
00:12:13,970 --> 00:12:18,900
Ние нема да направат посебни оние за родителите, а потоа конечниот јазли,

160
00:12:18,900 --> 00:12:23,680
кои ние се однесуваат како лисја, туку тие само ќе имаат NULL вредности.

161
00:12:23,680 --> 00:12:31,050
За секој јазол ќе имаме карактер, симболот дека тој јазол претставува,

162
00:12:31,050 --> 00:12:40,490
тогаш фреквенцијата, како и покажувач на неговата лева детето, како и неговото право дете.

163
00:12:40,490 --> 00:12:45,680
Лисјата, кои се на самото дно, исто така, ќе имаат јазол совети

164
00:12:45,680 --> 00:12:49,550
на нивните лево и нивно право, но бидејќи тие вредности не се укажува на вистински јазли,

165
00:12:49,550 --> 00:12:53,970
што нивната вредност ќе биде? >> [Студент] NULL. >> NULL. Точно.

166
00:12:53,970 --> 00:12:58,430
Еве еден пример за тоа како може да претставуваат фреквенцијата во плови,

167
00:12:58,430 --> 00:13:02,130
но ние ќе треба да се занимаваат со тоа со цели броеви,

168
00:13:02,130 --> 00:13:06,780
па сите што го направив е промена на тип на податок таму.

169
00:13:06,780 --> 00:13:09,700
>> Ајде да одиме за да се малку повеќе од комплексен пример.

170
00:13:09,700 --> 00:13:13,360
Но сега дека ние сме направиле едноставни оние, тоа е само истиот процес.

171
00:13:13,360 --> 00:13:20,290
Ќе најдете 2 најниска фреквенции, сумира фреквенции

172
00:13:20,290 --> 00:13:22,450
и тоа е нова фреквенција на вашиот родител јазол,

173
00:13:22,450 --> 00:13:29,310
кои потоа укажува на неговата лева со 0 гранка и правото со 1 гранка.

174
00:13:29,310 --> 00:13:34,200
Ако имаме стринг "Ова е cs50", тогаш ние брои колку пати е Т рековме,

175
00:13:34,200 --> 00:13:38,420
ж споменато, јас, и, в, 5, 0.

176
00:13:38,420 --> 00:13:42,010
Тогаш она што го направив тука е со црвена јазли Јас само сади,

177
00:13:42,010 --> 00:13:48,530
Реков јас ќе одам да имаат овие карактери на крајот на дното на моето дрво.

178
00:13:48,530 --> 00:13:51,740
Тоа се случува да бидат сите на листовите.

179
00:13:51,740 --> 00:13:58,200
Тогаш она што го направив е што ги подредени по зачестеност во растечки редослед,

180
00:13:58,200 --> 00:14:02,950
и ова е всушност начинот на кој pset код го прави тоа

181
00:14:02,950 --> 00:14:07,550
е тоа што видови на фреквенција, а потоа по азбучен ред.

182
00:14:07,550 --> 00:14:13,870
Така што има броеви, а потоа по азбучен ред од страна на фреквенција.

183
00:14:13,870 --> 00:14:18,520
Тогаш што ќе правам е ќе најдете 2 најниска. Тоа е 0 и 5.

184
00:14:18,520 --> 00:14:22,390
Јас би ги сумира, а тоа е 2. Тогаш јас ќе продолжи, најдете на следните 2 најниска.

185
00:14:22,390 --> 00:14:26,100
Тоа се две 1s, а потоа тие стануваат точки 2, како и.

186
00:14:26,100 --> 00:14:31,570
Сега знам дека мојот следен чекор ќе се приклучи на најмал број,

187
00:14:31,570 --> 00:14:41,380
што е Т, на 1, а потоа избирање на една од јазли кои има 2 како на фреквенција.

188
00:14:41,380 --> 00:14:44,560
Значи тука имаме 3 опции.

189
00:14:44,560 --> 00:14:47,980
Она што јас ќе одам да направите за слајд е само визуелно ги преуредите за вас

190
00:14:47,980 --> 00:14:51,790
така што ќе може да се види како јас сум таа градење.

191
00:14:51,790 --> 00:14:59,040
Што кодот и Вашиот дистрибуција код ќе го направи да се ќе се приклучат на T, една

192
00:14:59,040 --> 00:15:01,410
со 0 и 5 јазол.

193
00:15:01,410 --> 00:15:05,060
Па тогаш тоа суми до 3, а потоа продолжи процесот.

194
00:15:05,060 --> 00:15:08,660
На 2 и 2 сега се најниски, па потоа оние сума до 4.

195
00:15:08,660 --> 00:15:12,560
Секој кој го следи досега? Во ред.

196
00:15:12,560 --> 00:15:16,410
Потоа, по што имаме 3 и 3 кои треба да се собираат,

197
00:15:16,410 --> 00:15:21,650
па повторно јас сум само тоа префрлување, така што можете да видите визуелно, така што тоа не се премногу неуредна.

198
00:15:21,650 --> 00:15:25,740
Потоа имаме 6, а потоа нашите последниот чекор е дека сега имаме само 2 јазли

199
00:15:25,740 --> 00:15:30,440
ние сумира овие да се направи коренот на нашите дрво, која е 10.

200
00:15:30,440 --> 00:15:34,100
И бројот 10 има смисла, бидејќи секој јазол претставен,

201
00:15:34,100 --> 00:15:40,750
нивната вредност, нивната фреквенција број, беше колку пати тие се појави во низа,

202
00:15:40,750 --> 00:15:46,350
и тогаш имаме 5 знаци во нашата низа, така што има смисла.

203
00:15:48,060 --> 00:15:52,320
Ако ние се погледне до колку ние всушност ќе го кодираат,

204
00:15:52,320 --> 00:15:56,580
како што се очекуваше, i и S, кои се појавуваат најчесто

205
00:15:56,580 --> 00:16:01,350
се претставени со најмалку бројот на битови.

206
00:16:03,660 --> 00:16:05,660
>> Бидете внимателни овде.

207
00:16:05,660 --> 00:16:09,780
Во Хафман дрвја случај всушност е важно.

208
00:16:09,780 --> 00:16:13,670
На големи S е различен од мали s.

209
00:16:13,670 --> 00:16:21,260
Ако имавме "Ова е CS50" со големи букви, тогаш мали и само ќе се појави два пати,

210
00:16:21,260 --> 00:16:27,120
ќе биде еден јазол со 2 како неговата вредност, а потоа големи S ќе биде само еднаш.

211
00:16:27,120 --> 00:16:33,440
Па тогаш дрвото ќе се промени структури затоа што всушност има екстра лист овде.

212
00:16:33,440 --> 00:16:36,900
Но збирот сепак, ќе биде 10.

213
00:16:36,900 --> 00:16:39,570
Тоа е она што ние всушност ќе треба да се јавите на проверката,

214
00:16:39,570 --> 00:16:44,060
додавање на сите точки од обвинението.

215
00:16:46,010 --> 00:16:50,990
>> Сега дека ние сме опфатени Хафман дрвја, ние може да се нурне во Huff'n издувам, на pset.

216
00:16:50,990 --> 00:16:52,900
Ние ќе почне со делот на прашања,

217
00:16:52,900 --> 00:16:57,990
и ова ќе ти навикнати со бинарни дрва и како да работат околу тоа:

218
00:16:57,990 --> 00:17:03,230
цртање јазли, создавање на свој typedef struct за еден јазол,

219
00:17:03,230 --> 00:17:07,230
и види како може да се вметне во бинарно дрво, која е сортирани,

220
00:17:07,230 --> 00:17:09,050
traversing него, и работи како што.

221
00:17:09,050 --> 00:17:14,560
Дека знаењето е дефинитивно ќе ви помогнат кога ќе се нурне во издувам Huff'n дел

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

223
00:17:19,150 --> 00:17:26,329
Во стандардна верзија на pset, вашата задача е да се имплементира издувам,

224
00:17:26,329 --> 00:17:30,240
и во хакер верзија вашата задача е да се имплементира Хаф.

225
00:17:30,240 --> 00:17:38,490
Што Хаф не е потребно текст и потоа тоа го преведува во 0-ти и 1S,

226
00:17:38,490 --> 00:17:41,990
така што процесот што го направивме погоре каде што пребројуваше фреквенции

227
00:17:41,990 --> 00:17:50,970
а потоа направи од дрвото, а потоа рече: "Како можам да добијам Т?"

228
00:17:50,970 --> 00:17:54,840
Т е застапена со 100, работи како што,

229
00:17:54,840 --> 00:17:58,860
а потоа Хаф ќе го земе текстот и потоа излез кој бинарни.

230
00:17:58,860 --> 00:18:04,920
Но, исто така, затоа што знаеме дека ние сакаме да им овозможи на нашите примачот на пораката

231
00:18:04,920 --> 00:18:11,790
да се рекреираат исти дрво, исто така, содржи информации за фреквенција се брои.

232
00:18:11,790 --> 00:18:17,980
Потоа со издувам ние се дадени бинарна датотека на 0-ти и 1S

233
00:18:17,980 --> 00:18:21,740
и со оглед исто така, информации за фреквенции.

234
00:18:21,740 --> 00:18:26,740
Ние се преведе на сите оние 0-ти и 1S се врати во оригиналната порака, која беше

235
00:18:26,740 --> 00:18:29,350
па ние сме decompressing тоа.

236
00:18:29,350 --> 00:18:36,450
Ако правиш стандардната верзија, вие не треба да се спроведе Хаф,

237
00:18:36,450 --> 00:18:39,290
па тогаш само може да се користи на вработените имплементација на Хаф.

238
00:18:39,290 --> 00:18:42,080
Постојат инструкции во спецификации за тоа како да го направите тоа.

239
00:18:42,080 --> 00:18:48,780
Можете да го извршите на персоналот имплементација на Хаф по одредени текстуална датотека

240
00:18:48,780 --> 00:18:53,270
а потоа ја користат таа излез како вашиот влез Puff.

241
00:18:53,270 --> 00:18:59,330
>> Како што споменав порано, ние имаме многу на дистрибуција код за оваа.

242
00:18:59,330 --> 00:19:01,810
Одам да се започне одат преку неа.

243
00:19:01,810 --> 00:19:04,400
Одам да го поминат поголемиот дел од времето на. Ж датотеки

244
00:19:04,400 --> 00:19:07,660
бидејќи во. в датотеки, бидејќи имаме. h

245
00:19:07,660 --> 00:19:11,650
и дека ни обезбедува со прототипи на функции,

246
00:19:11,650 --> 00:19:15,520
ние не целосно треба да се разбере токму -

247
00:19:15,520 --> 00:19:20,280
Ако не го разбирате она што се случува во. В датотеки, тогаш не грижете се премногу,

248
00:19:20,280 --> 00:19:23,600
но дефинитивно се обиде да ги погледне, бидејќи тоа би можело да даде некои совети

249
00:19:23,600 --> 00:19:29,220
и тоа е корисно да се користи за читање на другите луѓе код.

250
00:19:38,940 --> 00:19:48,270
>> Гледајќи huffile.h, во коментарите се декларира еден слој на апстракција за Хафман-кодирани датотеки.

251
00:19:48,270 --> 00:20:01,660
Ако одиме надолу, гледаме дека постои максимум 256 симболи кои би можеле да треба кодови за.

252
00:20:01,660 --> 00:20:05,480
Ова ги вклучува сите букви од азбуката - големи и мали -

253
00:20:05,480 --> 00:20:08,250
а потоа симболи и броеви, итн

254
00:20:08,250 --> 00:20:11,930
Тогаш тука имаме магичната бројка идентификување на Хафман-кодирани датотека.

255
00:20:11,930 --> 00:20:15,890
Во рамките на код Хафман тие ќе имаат одредени магичната бројка

256
00:20:15,890 --> 00:20:18,560
поврзани со насловот.

257
00:20:18,560 --> 00:20:21,110
Ова може да изгледа како само случајна магичната бројка,

258
00:20:21,110 --> 00:20:27,160
но ако навистина го преведе на ASCII, а потоа тоа всушност ја искажува Хаф.

259
00:20:27,160 --> 00:20:34,290
Тука имаме struct за Хафман-кодирани датотека.

260
00:20:34,290 --> 00:20:39,670
Има сите овие карактеристики поврзани со датотека Хаф.

261
00:20:39,670 --> 00:20:47,080
Тогаш овде имаме насловот за датотеката Хаф, па ние го нарекуваме Huffeader

262
00:20:47,080 --> 00:20:50,810
наместо на додавање на екстра час, бидејќи тоа звучи исто во секој случај.

263
00:20:50,810 --> 00:20:52,720
Симпатична.

264
00:20:52,720 --> 00:20:57,790
Ние имаме магичната бројка поврзани со неа.

265
00:20:57,790 --> 00:21:09,040
Ако тоа е вистински Хаф датотека, тоа нема да биде бројот погоре, оваа магија еден.

266
00:21:09,040 --> 00:21:14,720
И тогаш ќе имаат низа.

267
00:21:14,720 --> 00:21:18,750
Значи за секој симбол, од кои има 256,

268
00:21:18,750 --> 00:21:24,760
тоа се случува да наведете што фреквенција на оние симболи се во рамките на датотека Хаф.

269
00:21:24,760 --> 00:21:28,090
А потоа конечно, имаме проверка за фреквенции,

270
00:21:28,090 --> 00:21:32,160
која треба да биде на збирот на тие фреквенции.

271
00:21:32,160 --> 00:21:36,520
Значи тоа е она што Huffeader е.

272
00:21:36,520 --> 00:21:44,600
Потоа имаме некои функции кои ја врати следната малку во датотеката Хаф

273
00:21:44,600 --> 00:21:52,580
како и пишува малку во датотеката Хаф, а потоа оваа функција овде, hfclose,

274
00:21:52,580 --> 00:21:54,650
кои, всушност, го затвора датотека Хаф.

275
00:21:54,650 --> 00:21:57,290
Пред тоа, ние се занимаваат со прави само запишам,

276
00:21:57,290 --> 00:22:01,190
но кога ќе имаат датотеки Хаф, наместо fclosing тоа

277
00:22:01,190 --> 00:22:06,080
она што сте, всушност, ќе треба да направите е hfclose и hfopen неа.

278
00:22:06,080 --> 00:22:13,220
Оние кои се специфични функции на Хаф датотеки кои ние ќе треба да се занимаваат со.

279
00:22:13,220 --> 00:22:19,230
Потоа тука читаме во насловот и потоа напишете го насловот.

280
00:22:19,230 --> 00:22:25,700
>> Само со читање на. Ж датотека може да се вид на се добие чувство за она датотека Хаф може да биде,

281
00:22:25,700 --> 00:22:32,480
она што карактеристики има, без всушност да одат во huffile.c,

282
00:22:32,480 --> 00:22:36,750
кои, ако се нурне во, ќе биде малку посложени.

283
00:22:36,750 --> 00:22:41,270
Таа ги има сите на датотека I / O тука се занимаваат со покажувачи.

284
00:22:41,270 --> 00:22:48,010
Овде гледаме дека кога ние го нарекуваме hfread, на пример, тоа е уште се занимаваат со fread.

285
00:22:48,010 --> 00:22:53,050
Ние не сме да се ослободиме од тие функции во целост, но ние сме испраќање на оние што треба да се преземат грижата за

286
00:22:53,050 --> 00:22:59,760
во внатрешноста на датотека Хаф, наместо за правење на сите за тоа самите себеси.

287
00:22:59,760 --> 00:23:02,300
Можете да се чувствуваат слободни да скенира преку ова ако сте љубопитни

288
00:23:02,300 --> 00:23:08,410
и да си одат и кора слој назад малку.

289
00:23:20,650 --> 00:23:24,060
>> Следниот датотека што ние ќе треба да се погледне е tree.h.

290
00:23:24,060 --> 00:23:30,210
Пред во можи слајдови рековме дека очекуваме Хафман јазол

291
00:23:30,210 --> 00:23:32,960
и ние направивме typedef struct јазол.

292
00:23:32,960 --> 00:23:38,360
Очекуваме да има симбол, фреквенција, а потоа 2 јазол ѕвезди.

293
00:23:38,360 --> 00:23:41,870
Во овој случај она што го правиме е тоа е во суштина иста

294
00:23:41,870 --> 00:23:46,880
освен наместо на јазол ние ќе ги наречеме дрвја.

295
00:23:48,790 --> 00:23:56,760
Имаме функција која кога ќе се јавите направи дрво тоа ви се враќа дрво покажувач.

296
00:23:56,760 --> 00:24:03,450
Вратете се на правопис, кога ќе се прави нов јазол

297
00:24:03,450 --> 00:24:11,410
ти рече јазол * нов збор = Примерок (sizeof) и работи како што.

298
00:24:11,410 --> 00:24:17,510
Во суштина, mktree ќе се занимаваат со тоа за вас.

299
00:24:17,510 --> 00:24:20,990
Слично на тоа, кога ќе сакате да го отстраните дрво,

300
00:24:20,990 --> 00:24:24,810
така што во суштина ослободување на дрвото кога ќе завршиш со него,

301
00:24:24,810 --> 00:24:33,790
наместо експлицитно повикување бесплатно на тоа, ти си, всушност, само ќе ја користите функцијата rmtree

302
00:24:33,790 --> 00:24:40,360
каде ќе помине во покажувачот во тој дрво, а потоа tree.c ќе се грижи за тоа за вас.

303
00:24:40,360 --> 00:24:42,490
>> Ние се погледне во tree.c.

304
00:24:42,490 --> 00:24:47,240
Ние очекуваме истите функции, освен да го видиш имплементација, како и.

305
00:24:47,240 --> 00:24:57,720
Како што се очекуваше, кога ќе се јавите mktree тоа mallocs големината на дрво во покажувач,

306
00:24:57,720 --> 00:25:03,190
иницијализира сите вредности на NULL вредност, така 0-ти или NULLS,

307
00:25:03,190 --> 00:25:08,280
а потоа се враќа покажувач на тоа дрво дека сте само malloc'd за вас.

308
00:25:08,280 --> 00:25:13,340
Еве кога ќе се јавите отстрани дрвото за прв пат прави сигурни дека не сте двојно ослободување.

309
00:25:13,340 --> 00:25:18,320
Тоа го прави сигурни дека всушност имаат дрво кое сакате да го отстраните.

310
00:25:18,320 --> 00:25:23,330
Тука, бидејќи дрво, исто така, вклучува своите деца,

311
00:25:23,330 --> 00:25:29,560
Што тоа не е тоа рекурзивно повици отстранат дрво од левата јазол на дрво

312
00:25:29,560 --> 00:25:31,650
како и правото јазол.

313
00:25:31,650 --> 00:25:37,790
Пред да го ослободи родителот, треба да ги ослободи децата.

314
00:25:37,790 --> 00:25:42,770
Родител е исто така заменлив со корен.

315
00:25:42,770 --> 00:25:46,500
Првиот родител, па како пра-пра-пра-пра-дедо

316
00:25:46,500 --> 00:25:52,130
или баба дрво, прво треба да се ослободи по нивоа во прв план.

317
00:25:52,130 --> 00:25:58,490
Значи напречни до дното, без оние, а потоа се врати нагоре, бесплатни оние, итн

318
00:26:00,400 --> 00:26:02,210
Значи тоа е дрво.

319
00:26:02,210 --> 00:26:04,240
>> Сега гледаме шумата.

320
00:26:04,240 --> 00:26:09,860
Шума е местото каде што ќе поставите на сите ваши Хафман дрвја.

321
00:26:09,860 --> 00:26:12,910
Тоа е велејќи дека ние ќе имаме нешто што се нарекува заговор

322
00:26:12,910 --> 00:26:22,320
кој се состои покажувач до дрвото, како и покажувач на заговор наречен следната.

323
00:26:22,320 --> 00:26:28,480
Што структура го прави овој вид на изгледа?

324
00:26:29,870 --> 00:26:32,490
Тој вид на тоа дека таму.

325
00:26:34,640 --> 00:26:36,700
Право овде.

326
00:26:37,340 --> 00:26:39,170
А поврзани листа.

327
00:26:39,170 --> 00:26:44,590
Гледаме дека кога имаме заговор тоа е како поврзани листа на парцели.

328
00:26:44,590 --> 00:26:53,020
А шумата е дефинирана како се поврзани листа на парцели,

329
00:26:53,020 --> 00:26:58,100
и така структурата на шумите е ние сме само ќе мора покажувач на нашата прва заговор

330
00:26:58,100 --> 00:27:02,740
и дека Парцела има едно дрво во неа или подобро укажува на дрвото

331
00:27:02,740 --> 00:27:06,190
а потоа укажува на следното заговор, па натаму и така натаму.

332
00:27:06,190 --> 00:27:11,100
Да се ​​направи шума што ние го нарекуваме mkforest.

333
00:27:11,100 --> 00:27:14,930
Тогаш имаме некои прилично корисни функции тука.

334
00:27:14,930 --> 00:27:23,240
Имаме собереш каде што ќе помине во шумата и тогаш вратената вредност е едно дрво *,

335
00:27:23,240 --> 00:27:25,210
покажувач на дрво.

336
00:27:25,210 --> 00:27:29,370
Што пик ќе го направите е дека ќе одат во шумата дека сте укажува на

337
00:27:29,370 --> 00:27:35,240
потоа отстранете дрво со најниска фреквенција од таа шума

338
00:27:35,240 --> 00:27:38,330
и потоа да ви даде покажувач на тоа дрво.

339
00:27:38,330 --> 00:27:43,030
Откако ќе се јавите собереш, дрвото нема да постои во шумата веќе,

340
00:27:43,030 --> 00:27:48,550
но вратената вредност е покажувач на тоа дрво.

341
00:27:48,550 --> 00:27:50,730
Тогаш имате растение.

342
00:27:50,730 --> 00:27:57,420
Под услов да помине во покажувач на дрво кој има не-0 фреквенција,

343
00:27:57,420 --> 00:28:04,040
што фабриката ќе направите е тоа ќе потрае шумата, да ги преземе дрво и растение кое дрво во внатрешноста на шумата.

344
00:28:04,040 --> 00:28:06,370
Тука имаме rmforest.

345
00:28:06,370 --> 00:28:11,480
Слични да се отстранат дрво, што во основа ослободени сите наши дрва за нас,

346
00:28:11,480 --> 00:28:16,600
отстрани шума ќе се ослободи се содржани во таа шума.

347
00:28:16,600 --> 00:28:24,890
>> Ако ги погледнеме во forest.c, ќе очекуваат да видат најмалку 1 rmtree команда во таму,

348
00:28:24,890 --> 00:28:30,090
бидејќи за слободна меморија во шумата ако шума има дрвја во него,

349
00:28:30,090 --> 00:28:32,930
потоа на крајот ви се случува да мора да се отстранат оние дрвја премногу.

350
00:28:32,930 --> 00:28:41,020
Ако ги погледнеме во forest.c, ние си имаме mkforest, која е како што очекував.

351
00:28:41,020 --> 00:28:42,890
Ние Примерок работи.

352
00:28:42,890 --> 00:28:51,740
Ние се иницијализира на прво заговор во шумата како NULL, бидејќи тоа е празна да започне со тоа,

353
00:28:51,740 --> 00:29:05,940
тогаш можеме да видиме мотиката, која се враќа на дрвото со најниска тежина, најниската фреквенција,

354
00:29:05,940 --> 00:29:13,560
а потоа добива ослободи од таа јазол што укажува на тоа дрво и следната,

355
00:29:13,560 --> 00:29:16,760
па го зема дека од поврзани листа на шумата.

356
00:29:16,760 --> 00:29:24,510
И тогаш тука имаме фабриката, која внесува дрво во поврзани листа.

357
00:29:24,510 --> 00:29:29,960
Што шума не е тоа убаво го чува складирано за нас.

358
00:29:29,960 --> 00:29:37,910
А потоа конечно, имаме rmforest и, како што се очекуваше, имаме rmtree наречен таму.

359
00:29:46,650 --> 00:29:55,440
>> Гледајќи дистрибуција код досега, huffile.c веројатно беше далеку од најтешко да се разбере,

360
00:29:55,440 --> 00:29:59,990
додека други датотеки самите се прилично едноставни да го следат.

361
00:29:59,990 --> 00:30:03,090
Со нашето знаење за совети и поврзани листи и такви,

362
00:30:03,090 --> 00:30:04,860
ние бевме во можност да го следат многу добро.

363
00:30:04,860 --> 00:30:10,500
Но, сите ние треба навистина да бидете сигурни дека ние се разбере целосно е. Ж датотеки

364
00:30:10,500 --> 00:30:15,840
затоа што треба да се повикуваат на тие функции, кои се занимаваат со оние враќање вредности,

365
00:30:15,840 --> 00:30:20,590
така бидете сигурни дека ќе се разбере целосно она што акција се случува да се изврши

366
00:30:20,590 --> 00:30:24,290
кога ќе се јавите една од тие функции.

367
00:30:24,290 --> 00:30:33,020
Но всушност разбирање во него не е сосема неопходно бидејќи имаме оние. Ж датотеки.

368
00:30:35,170 --> 00:30:39,490
Имаме 2 повеќе датотеки лево во нашата дистрибутивна код.

369
00:30:39,490 --> 00:30:41,640
>> Да ги погледнеме на депонија.

370
00:30:41,640 --> 00:30:47,230
Шутнат од страна на неговиот коментар овде зема Хафман-компресирана датотека

371
00:30:47,230 --> 00:30:55,580
а потоа ги преведува и депонии сите негови содржини надвор.

372
00:31:01,010 --> 00:31:04,260
Овде гледаме дека тоа е повикувајќи hfopen.

373
00:31:04,260 --> 00:31:10,770
Ова е вид на слика на датотека * внесување = fopen,

374
00:31:10,770 --> 00:31:13,500
а потоа ќе помине во информацијата.

375
00:31:13,500 --> 00:31:18,240
Тоа е речиси идентични, освен наместо на датотека * си поминува во Huffile;

376
00:31:18,240 --> 00:31:22,030
наместо fopen сте поминува во hfopen.

377
00:31:22,030 --> 00:31:29,280
Еве што читаме во насловот прво, кој е вид на слично на тоа како што читаме во насловот

378
00:31:29,280 --> 00:31:33,580
за битмапа датотеки.

379
00:31:33,580 --> 00:31:38,000
Она што го правиме тука е проверка за да види дали технички податоци

380
00:31:38,000 --> 00:31:44,330
содржи правото магичната бројка што укажува на тоа дека тоа е вистински Хаф датотека,

381
00:31:44,330 --> 00:31:53,610
тогаш сите од овие проверки за да бидете сигурни дека датотеката што ние отворен е вистински huffed датотека или не.

382
00:31:53,610 --> 00:32:05,330
Што тоа не е тоа излези на фреквенциите на сите симболи кои можеме да видиме

383
00:32:05,330 --> 00:32:09,790
во рамките на терминал во графички табела.

384
00:32:09,790 --> 00:32:15,240
Овој дел ќе биде корисно.

385
00:32:15,240 --> 00:32:24,680
Таа има малку и гласи малку по малку во променлива малку, а потоа печати.

386
00:32:28,220 --> 00:32:35,430
Значи, ако јас да се јавам депонија на hth.bin, која е резултат на huffing датотека

387
00:32:35,430 --> 00:32:39,490
користење на персоналот решение, јас ќе ја добие ова.

388
00:32:39,490 --> 00:32:46,000
Тоа е Ставање сите тие ликови и потоа ставање на фреквенцијата на која тие се појавуваат.

389
00:32:46,000 --> 00:32:51,180
Ако ги погледнеме, повеќето од нив се 0-ти освен за ова: H, кој се појавува двапати,

390
00:32:51,180 --> 00:32:54,820
а потоа Т, која се појавува еднаш.

391
00:32:54,820 --> 00:33:07,860
И тогаш ја имаме вистинската порака во 0-ти и 1S.

392
00:33:07,860 --> 00:33:15,450
Ако ги погледнеме hth.txt, што е веројатно оригиналната порака, која беше huffed,

393
00:33:15,450 --> 00:33:22,490
ние очекуваме да видите некои Hs и Т таму.

394
00:33:22,490 --> 00:33:28,720
Поточно, ние очекуваме да се види само 1 T и 2 ХС.

395
00:33:32,510 --> 00:33:37,440
Тука сме во hth.txt. Тоа навистина има HTH.

396
00:33:37,440 --> 00:33:41,270
Вклучени во таму, иако не можеме да го видиме, е линија карактер.

397
00:33:41,270 --> 00:33:53,190
Датотеката Хаф hth.bin е исто така кодирање на линија карактер, како и.

398
00:33:55,680 --> 00:34:01,330
Тука, затоа што знаеме дека наредбата е HTH, а потоа линија,

399
00:34:01,330 --> 00:34:07,340
можеме да видиме дека веројатно H е претставена со само еден 1

400
00:34:07,340 --> 00:34:17,120
а потоа T е веројатно 01 и потоа на следниот H е 1, како и

401
00:34:17,120 --> 00:34:21,139
и тогаш имаме нова линија означена со два 0-ти.

402
00:34:22,420 --> 00:34:24,280
Кул.

403
00:34:26,530 --> 00:34:31,600
>> А потоа конечно, затоа што ние сме се занимаваат со повеќе. В и. Ж датотеки,

404
00:34:31,600 --> 00:34:36,350
ние ќе имаат доста сложени аргумент на компајлерот,

405
00:34:36,350 --> 00:34:40,460
и така тука имаме Makefile што го прави депонија за вас.

406
00:34:40,460 --> 00:34:47,070
Но, всушност, треба да одат за правење на своја сопствена puff.c датотека.

407
00:34:47,070 --> 00:34:54,330
На Makefile всушност не се занимава со правење puff.c за вас.

408
00:34:54,330 --> 00:34:59,310
Тргнуваме дека до вас да ги уредувате Makefile.

409
00:34:59,310 --> 00:35:05,930
Кога ќе внесете ја командата како прават сите, на пример, тоа ќе го направи сите од нив за вас.

410
00:35:05,930 --> 00:35:10,760
Слободно да се погледне на примери на Makefile од минатото pset

411
00:35:10,760 --> 00:35:17,400
како и ќе отиде на ова да видиме колку може да биде во можност да се направи вашиот издувам датотека

412
00:35:17,400 --> 00:35:20,260
со уредување на оваа Makefile.

413
00:35:20,260 --> 00:35:22,730
Тоа е за тоа за нашата дистрибутивна код.

414
00:35:22,730 --> 00:35:28,380
>> Откако сме добиле преку тоа, тогаш тука е само уште еден потсетник

415
00:35:28,380 --> 00:35:30,980
за тоа како ние ќе треба да се занимаваат со Хафман јазли.

416
00:35:30,980 --> 00:35:35,400
Ние нема да се нарекувајќи ги јазли повеќе, ние ќе треба да се ги повикувам дрва

417
00:35:35,400 --> 00:35:39,260
каде што ќе треба да се застапуваат нивните симбол со знак,

418
00:35:39,260 --> 00:35:43,340
нивната фреквенција, бројот на појавувања, со цел број.

419
00:35:43,340 --> 00:35:47,370
Ние сме користење на тоа, бидејќи тоа е попрецизно отколку со подвижна запирка.

420
00:35:47,370 --> 00:35:52,980
И тогаш имаме уште покажувачот лево детето, како и право дете.

421
00:35:52,980 --> 00:35:59,630
А шума, како што видовме, е само поврзани листа на дрвјата.

422
00:35:59,630 --> 00:36:04,670
На крајот на краиштата, кога градиме до нашите Хаф датотека,

423
00:36:04,670 --> 00:36:07,580
ние сакаме нашите шуми да содржи само 1 дрво -

424
00:36:07,580 --> 00:36:12,420
1 дрво, 1 корен со повеќе деца.

425
00:36:12,420 --> 00:36:20,840
Претходно кога бевме само што нашите Хафман дрвја,

426
00:36:20,840 --> 00:36:25,360
ние започна со ставање на сите јазли врз нашите екран

427
00:36:25,360 --> 00:36:27,790
и велејќи ние ќе ги имаат овие јазли,

428
00:36:27,790 --> 00:36:32,920
на крајот тие ќе бидат лисја, и ова е нивен симбол, ова е нивната фреквенција.

429
00:36:32,920 --> 00:36:42,070
Во нашата шума, ако ние само треба 3 букви, тоа е шума од 3 дрва.

430
00:36:42,070 --> 00:36:45,150
А потоа како да одиме на, кога ќе додаде првиот родител,

431
00:36:45,150 --> 00:36:48,080
ние направивме една шума од 2 дрвја.

432
00:36:48,080 --> 00:36:54,930
Ние отстранета 2 на оние деца од нашата шума и потоа се заменува со еден родител јазол

433
00:36:54,930 --> 00:36:58,820
кои имаа оние 2 јазли како деца.

434
00:36:58,820 --> 00:37:05,600
А потоа, конечно, нашиот последен чекор со правење нашиот пример со As, Bs и акредитиви

435
00:37:05,600 --> 00:37:08,030
ќе биде да ја донесе конечната родител,

436
00:37:08,030 --> 00:37:13,190
и така тогаш тоа ќе донесе нашите вкупниот бројот на дрвјата во шумата 1.

437
00:37:13,190 --> 00:37:18,140
Не сите се види како ќе почнете да излегува со повеќе дрвја во вашиот шума

438
00:37:18,140 --> 00:37:22,520
и завршуваат со 1? Во ред. Кул.

439
00:37:25,530 --> 00:37:28,110
>> Што треба да направите за издувам?

440
00:37:28,110 --> 00:37:37,110
Она што треба да направите е да се осигура дека, како и секогаш, тие ни даваат право тип на влез

441
00:37:37,110 --> 00:37:39,090
така што ние всушност може да ја стартувате програмата.

442
00:37:39,090 --> 00:37:43,130
Во овој случај тие ќе бидат ни даваат по нивната прва командната линија аргумент

443
00:37:43,130 --> 00:37:53,440
2 повеќе: датотеката што сакате да декомпресија и излез на декомпресиран датотека.

444
00:37:53,440 --> 00:38:00,410
Но еднаш сме бидете сигурни дека тие не помине во точниот износ на вредности,

445
00:38:00,410 --> 00:38:05,820
сакаме да се осигураме дека влезот е датотека Хаф или не.

446
00:38:05,820 --> 00:38:10,420
А потоа откако ќе гарантира дека тоа е датотека Хаф, тогаш ние сакаме да ја градиме нашата дрво,

447
00:38:10,420 --> 00:38:20,940
изгради дрвото како што тоа се совпаѓа со дрво дека лицето кое ја испратил пораката изграден.

448
00:38:20,940 --> 00:38:25,840
Потоа, откако ќе се изгради на дрвото, а потоа можеме да се справиме со 0-ти и 1S дека тие поминаа во,

449
00:38:25,840 --> 00:38:29,590
следат оние долж нашите дрво, бидејќи тоа е идентична,

450
00:38:29,590 --> 00:38:33,510
а потоа пишуваат дека пораката, толкуваат на битови назад во карактери.

451
00:38:33,510 --> 00:38:35,880
А потоа на крајот, бидејќи ние сме се занимаваат со покажувачи тука,

452
00:38:35,880 --> 00:38:38,110
ние сакаме да се осигураме дека можеме немаат меморија протекување

453
00:38:38,110 --> 00:38:41,330
и дека слободно сè.

454
00:38:42,820 --> 00:38:46,430
>> Обезбедување на соодветна употреба е стара шапка за нас до сега.

455
00:38:46,430 --> 00:38:51,980
Ние се во влез, кој ќе биде името на датотеката да се издувам,

456
00:38:51,980 --> 00:38:56,010
а потоа наведете излезна,

457
00:38:56,010 --> 00:39:01,580
па името на датотеката за умирам излез, која ќе биде текстуална датотека.

458
00:39:03,680 --> 00:39:08,820
Тоа е употреба. И сега сакаме да се осигураме дека влезот е huffed или не.

459
00:39:08,820 --> 00:39:16,420
Размислување назад, немаше ништо во дистрибуцијата код кој може да ни помогне

460
00:39:16,420 --> 00:39:21,570
со разбирање дали датотеката е huffed или не?

461
00:39:21,570 --> 00:39:26,910
Имаше информации во huffile.c за Huffeader.

462
00:39:26,910 --> 00:39:33,430
Ние знаеме дека секој фајл Хаф има Huffeader поврзани со неа со магичната бројка

463
00:39:33,430 --> 00:39:37,240
како и низа на фреквенции за секој симбол

464
00:39:37,240 --> 00:39:39,570
како и проверката.

465
00:39:39,570 --> 00:39:43,180
Ние знаеме тоа, но ние исто така, зеде погледнеме dump.c,

466
00:39:43,180 --> 00:39:49,120
во која читав во датотека Хаф.

467
00:39:49,120 --> 00:39:53,990
И така да го стори тоа, таа мораше да се провери дали тоа навистина беше huffed или не.

468
00:39:53,990 --> 00:40:03,380
Па можеби и ние може да се користи dump.c како структура за нашиот puff.c.

469
00:40:03,380 --> 00:40:12,680
Назад кон pset 4 кога имавме датотеката copy.c дека копирани во RGB тројки

470
00:40:12,680 --> 00:40:14,860
и ние толкува дека за Whodunit и големината,

471
00:40:14,860 --> 00:40:20,390
Слично на тоа, она што може да направите е само да ја извршите командата како ср dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
и употреба на некои од кодот таму.

473
00:40:23,600 --> 00:40:28,210
Сепак, тоа нема да биде лесно на процесот

474
00:40:28,210 --> 00:40:33,010
за преведување на вашата dump.c во puff.c,

475
00:40:33,010 --> 00:40:36,160
но барем тоа ви дава некаде да се започне

476
00:40:36,160 --> 00:40:40,540
како да се обезбеди дека влезот е всушност huffed или не

477
00:40:40,540 --> 00:40:43,240
како и неколку други работи.

478
00:40:45,930 --> 00:40:50,250
Имаме обезбедено правилно користење и гарантира дека влезот е huffed.

479
00:40:50,250 --> 00:40:53,570
Секој пат дека ние сме направиле тоа ние сме го направиле нашиот правилно грешка проверка,

480
00:40:53,570 --> 00:41:01,520
па враќање и напуштање на функцијата ако некои неуспех се јавува, ако има некој проблем.

481
00:41:01,520 --> 00:41:07,170
>> Сега она што сакате да го направите е да се изгради вистински дрво.

482
00:41:08,840 --> 00:41:12,640
Ако ги погледнеме во шума, постојат 2 основни функции

483
00:41:12,640 --> 00:41:15,800
дека ние ќе сакаат да станат многу запознаени со.

484
00:41:15,800 --> 00:41:23,870
Тука е Булова функција растение кое растенија не-0 фреквенција дрво во внатрешноста на нашите шуми.

485
00:41:23,870 --> 00:41:29,250
И така таму ќе помине во покажувач кон шумата и покажувач на дрво.

486
00:41:32,530 --> 00:41:40,340
Брзи прашање: Колку шуми ќе имате кога ќе градиме дрво Хафман?

487
00:41:44,210 --> 00:41:46,650
Нашите шуми е како нашата платно, нели?

488
00:41:46,650 --> 00:41:50,800
Па ние сме само ќе треба 1 шума, но ние ќе имаат повеќе дрвја.

489
00:41:50,800 --> 00:41:57,590
Значи пред да се јавите фабрика, ти си веројатно ќе сакате да направите вашиот шума.

490
00:41:57,590 --> 00:42:04,430
Постои команда за тоа ако се погледне во forest.h за тоа како можете да направите шума.

491
00:42:04,430 --> 00:42:09,270
Можете да засади дрво. Знаеме како да го направите тоа.

492
00:42:09,270 --> 00:42:11,590
И тогаш исто така можете да изберете дрво од шумата,

493
00:42:11,590 --> 00:42:17,540
отстранување на дрво со најниска тежина и ви даваат покажувач за тоа.

494
00:42:17,540 --> 00:42:23,090
Размислување назад кога бевме прави примери себе,

495
00:42:23,090 --> 00:42:27,980
кога бевме тоа извлекувањето, ние едноставно само додава линкови.

496
00:42:27,980 --> 00:42:31,680
Но, тука, наместо само додавање на линкови,

497
00:42:31,680 --> 00:42:40,630
мислам на тоа повеќе како сте отстранување 2 на оние јазли, а потоа негово заменување со друг.

498
00:42:40,630 --> 00:42:44,200
Да го изразат дека во однос на подигање и садење,

499
00:42:44,200 --> 00:42:48,840
сте подигање 2 дрвја, а потоа садат друго дрво

500
00:42:48,840 --> 00:42:54,060
дека има оние 2 дрвјата кои што сте го одбрале како деца.

501
00:42:57,950 --> 00:43:05,280
Да се ​​изгради дрво Хафман, можете да прочитате во симболи и фреквенции со цел

502
00:43:05,280 --> 00:43:10,790
бидејќи Huffeader дава тоа за вас,

503
00:43:10,790 --> 00:43:14,250
ви дава низа на фреквенции.

504
00:43:14,250 --> 00:43:19,660
Па можете да одите напред и едноставно игнорирајте ништо со 0 во него

505
00:43:19,660 --> 00:43:23,760
бидејќи ние не сакаме 256 листови на крајот од неа.

506
00:43:23,760 --> 00:43:27,960
Ние само сакаме бројот на листови кои се ликови

507
00:43:27,960 --> 00:43:31,600
кои се всушност користени во датотеката.

508
00:43:31,600 --> 00:43:37,590
Можете да прочитате во оние симболи, и секоја од овие симболи кои имаат не-0 фреквенции,

509
00:43:37,590 --> 00:43:40,440
тие се случува да бидат дрвја.

510
00:43:40,440 --> 00:43:45,990
Што можете да направите е секој пат кога ќе го прочитате во не-0 фреквенција симбол,

511
00:43:45,990 --> 00:43:50,660
ќе може да посади тоа дрво во шумата.

512
00:43:50,660 --> 00:43:56,620
Откако ќе засади дрвца во шумата, можете да се приклучат на оние дрвја како браќа и сестри,

513
00:43:56,620 --> 00:44:01,130
па ќе се вратам на садење и изборот каде ќе ги собереш 2, а потоа растенијата 1,

514
00:44:01,130 --> 00:44:05,820
каде што 1 дека фабриката е родител на 2 деца кои што сте го одбрале.

515
00:44:05,820 --> 00:44:11,160
Па тогаш вашиот Крајниот резултат ќе биде една дрво во шумата.

516
00:44:16,180 --> 00:44:18,170
Тоа е како да изградите вашиот дрво.

517
00:44:18,170 --> 00:44:21,850
>> Постојат неколку работи што може да тргне наопаку тука

518
00:44:21,850 --> 00:44:26,580
бидејќи ние сме се занимаваат со создавање на нови дрва и се занимаваат со совети и работи како што.

519
00:44:26,580 --> 00:44:30,450
Пред кога ние се занимаваат со покажувачи,

520
00:44:30,450 --> 00:44:36,580
секогаш кога malloc'd сакавме да бидете сигурни дека тоа не ни се врати NULL покажувачот вредност.

521
00:44:36,580 --> 00:44:42,770
Па на неколку чекори во овој процес таму ќе биде неколку случаи

522
00:44:42,770 --> 00:44:45,920
каде што вашата програма може да не успее.

523
00:44:45,920 --> 00:44:51,310
Што сакате да направите е да сакате да бидете сигурни дека ќе се справи со овие грешки,

524
00:44:51,310 --> 00:44:54,580
и во спецификации што се вели да се справи со нив благодатно,

525
00:44:54,580 --> 00:45:00,280
Значи како испечатите порака до корисникот кажувајќи им зошто на програмата е да престанам

526
00:45:00,280 --> 00:45:03,050
а потоа брзо се повлече.

527
00:45:03,050 --> 00:45:09,490
Да го направите ова грешка ракување, не заборавајте дека сакате да го проверите

528
00:45:09,490 --> 00:45:12,160
секој пат дека би можел да биде неуспех.

529
00:45:12,160 --> 00:45:14,660
Секој пат кога ќе се прави нов покажувач

530
00:45:14,660 --> 00:45:17,040
вие сакате да бидете сигурни дека тоа е успешна.

531
00:45:17,040 --> 00:45:20,320
Пред она што се користи да направите е да се направи нов покажувач и Примерок тоа,

532
00:45:20,320 --> 00:45:22,380
и тогаш ние ќе провери дали покажувачот е NULL.

533
00:45:22,380 --> 00:45:25,670
Па таму се случува да биде некои случаи, каде што само може да го направи тоа,

534
00:45:25,670 --> 00:45:28,610
но понекогаш ти си, всушност, нарекувајќи функција

535
00:45:28,610 --> 00:45:33,100
Во таа функција, тоа е оној кој го прави на mallocing.

536
00:45:33,100 --> 00:45:39,110
Во тој случај, ако се погледне назад на некои од функциите во рамките на код,

537
00:45:39,110 --> 00:45:42,260
некои од нив се Булови функции.

538
00:45:42,260 --> 00:45:48,480
Во апстрактни случај ако имаме Булова функција наречена foo,

539
00:45:48,480 --> 00:45:54,580
основа, можеме да претпоставиме дека во прилог на тоа што foo не,

540
00:45:54,580 --> 00:45:57,210
бидејќи тоа е Булова функција, го враќа точно или неточно -

541
00:45:57,210 --> 00:46:01,300
точно ако е успешна, лажни ако не.

542
00:46:01,300 --> 00:46:06,270
Значи, ние сакаме да се провери дали повратната вредност на foo е точно или неточно.

543
00:46:06,270 --> 00:46:10,400
Ако е неточно, тоа значи дека ние ќе сакате да се печати некој вид на порака

544
00:46:10,400 --> 00:46:14,390
а потоа да престанам програмата.

545
00:46:14,390 --> 00:46:18,530
Она што сакаме да направите е да се провери повратната вредност на foo.

546
00:46:18,530 --> 00:46:23,310
Ако foo враќа false, тогаш знаеме дека ние се сретнал некој вид на грешка

547
00:46:23,310 --> 00:46:25,110
и ние треба да се откажат од нашата програма.

548
00:46:25,110 --> 00:46:35,600
Еден начин да го направите ова е да има состојба каде вистинските самата функција е вашата состојба.

549
00:46:35,600 --> 00:46:39,320
Велат foo зема во х.

550
00:46:39,320 --> 00:46:43,390
Ние може да има како услов ако (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Во суштина, тоа значи дека ако на крајот на извршување foo го враќа точно,

552
00:46:50,900 --> 00:46:57,390
тогаш можеме да го направите ова, бидејќи функцијата има да се оцени foo

553
00:46:57,390 --> 00:47:00,500
со цел да се оцени целата состојба.

554
00:47:00,500 --> 00:47:06,500
Па тогаш тоа е како можете да направите нешто ако функцијата враќа точно и е успешна.

555
00:47:06,500 --> 00:47:11,800
Но, кога сте грешка проверка, вие само сакате да се откажете, ако вашата функција враќа false.

556
00:47:11,800 --> 00:47:16,090
Што можете да направите е само да додадете == лажни или само додадете тресне пред него

557
00:47:16,090 --> 00:47:21,010
а потоа ќе мора if (! foo).

558
00:47:21,010 --> 00:47:29,540
Во рамките на тој орган на таа состојба ќе имаат сите на грешка ракување,

559
00:47:29,540 --> 00:47:36,940
Значи како "Не можам да креирам ова дрво", а потоа се врати 1 или нешто слично.

560
00:47:36,940 --> 00:47:43,340
Она што го прави тоа, сепак, е дека иако foo врати лажни -

561
00:47:43,340 --> 00:47:46,980
Велат foo враќа точно.

562
00:47:46,980 --> 00:47:51,060
Тогаш не треба да се јавите foo повторно. Тоа е честа заблуда.

563
00:47:51,060 --> 00:47:54,730
Бидејќи тоа е во вашата состојба, тоа е веќе оценети,

564
00:47:54,730 --> 00:47:59,430
па имате резултат ако сте со користење направи дрво или нешто слично

565
00:47:59,430 --> 00:48:01,840
или растителни или пик или нешто.

566
00:48:01,840 --> 00:48:07,460
Таа веќе има таа вредност. Тоа е веќе извршена.

567
00:48:07,460 --> 00:48:10,730
Така, тоа е корисно да се користи Булови функции како услов

568
00:48:10,730 --> 00:48:13,890
бидејќи тоа дали или не сте всушност извршување на телото на јамка,

569
00:48:13,890 --> 00:48:18,030
го извршува функцијата во секој случај.

570
00:48:22,070 --> 00:48:27,330
>> Нашиот втор до последното чекор е пишување на порака до датотеката.

571
00:48:27,330 --> 00:48:33,070
Откако ќе се изгради на дрвото Хафман, а потоа пишување на порака до датотека е прилично јасна.

572
00:48:33,070 --> 00:48:39,260
Тоа е прилично јасна сега само да го следат 0-ти и 1S.

573
00:48:39,260 --> 00:48:45,480
И така од конвенцијата знаеме дека во дрво Хафман на 0-ти укажуваат лево

574
00:48:45,480 --> 00:48:48,360
и 1s укажуваат право.

575
00:48:48,360 --> 00:48:53,540
Па тогаш ако го прочитате во малку од малку, секогаш кога ќе добие 0

576
00:48:53,540 --> 00:48:59,100
ќе следат левата гранка, а потоа секој пат кога ќе прочитате во 1

577
00:48:59,100 --> 00:49:02,100
ви се случува да се следи вистинскиот гранка.

578
00:49:02,100 --> 00:49:07,570
А потоа ви се случува да продолжи додека не го погоди еден лист

579
00:49:07,570 --> 00:49:11,550
бидејќи лисјата се случува да биде на крајот од гранките.

580
00:49:11,550 --> 00:49:16,870
Како што може да каже дали ние сме хит лист или не?

581
00:49:19,800 --> 00:49:21,690
Ние тоа го рече пред тоа.

582
00:49:21,690 --> 00:49:24,040
[Студент] Ако совети се ништовни. >> Да.

583
00:49:24,040 --> 00:49:32,220
Ние може да каже дали ние сме хит лист ако совети за двете лево и десно дрвја се ништовни.

584
00:49:32,220 --> 00:49:34,110
Совршена.

585
00:49:34,110 --> 00:49:40,320
Знаеме дека сакате да го прочитате во малку по малку во нашите Хаф датотека.

586
00:49:43,870 --> 00:49:51,220
Како што видовме досега во dump.c, она што се случи е дека тие читаат во малку по малку во датотеката Хаф

587
00:49:51,220 --> 00:49:54,560
и само печатени од она што тие делови беа.

588
00:49:54,560 --> 00:49:58,430
Ние нема да се прави тоа. Ние ќе се прави нешто што е малку посложена.

589
00:49:58,430 --> 00:50:03,620
Но, она што можеме да направиме е што може да се земе дека малку на кодот кој гласи во малку.

590
00:50:03,620 --> 00:50:10,250
Тука имаме цел број малку претставуваат сегашниот малку дека ние сме на.

591
00:50:10,250 --> 00:50:15,520
Ова се грижи за процесирањето на сите битови во датотека додека не го погоди крајот на датотеката.

592
00:50:15,520 --> 00:50:21,270
Врз основа на тоа, тогаш ви се случува да сакаат да имаат некој вид на iterator

593
00:50:21,270 --> 00:50:26,760
да напречни дрвото.

594
00:50:26,760 --> 00:50:31,460
А потоа врз основа на тоа дали малку е 0 или 1,

595
00:50:31,460 --> 00:50:36,920
сте ќе сакате или да се движат дека iterator на лево или преместите во право

596
00:50:36,920 --> 00:50:44,080
по целиот пат додека не го погоди еден лист, па сите на патот до тој јазол дека сте на

597
00:50:44,080 --> 00:50:48,260
не укажуваат на повеќе јазли.

598
00:50:48,260 --> 00:50:54,300
Зошто ние да го правиме ова со датотека Хафман, но не Morse code?

599
00:50:54,300 --> 00:50:56,610
Бидејќи во Morse code има малку двосмисленост.

600
00:50:56,610 --> 00:51:04,440
Ние може да биде како, ох чекаат, ние сме хит писмо на патот, па можеби и ова е нашето писмо,

601
00:51:04,440 --> 00:51:08,150
а ако продолжи малку подолго, тогаш ние ќе ја погодеше друго писмо.

602
00:51:08,150 --> 00:51:13,110
Но, тоа нема да се случи во Хафман кодирање,

603
00:51:13,110 --> 00:51:17,540
така што може да бидат сигурни дека единствениот начин на кој ние ќе ја погоди карактер

604
00:51:17,540 --> 00:51:23,480
е ако лево и десно деца кои јазол се ништовни.

605
00:51:28,280 --> 00:51:32,350
>> Конечно, ние сакаме да ги ослободи сите од нашата меморија.

606
00:51:32,350 --> 00:51:37,420
Ние сакаме да и блиски на датотеката Хаф дека ние сме биле занимаваат со

607
00:51:37,420 --> 00:51:41,940
како и отстрани сите дрвја во нашата шума.

608
00:51:41,940 --> 00:51:46,470
Врз основа на вашата институција, ти си веројатно ќе сакате да го повикате отстрани шума

609
00:51:46,470 --> 00:51:49,780
наместо всушност минува низ сите на дрвјата себе.

610
00:51:49,780 --> 00:51:53,430
Но, ако сте го направиле било привремени дрвја, ќе сакате да се ослободи тоа.

611
00:51:53,430 --> 00:51:59,060
Знаеш вашиот код најдобрите, па да знаете каде сте доделување меморија.

612
00:51:59,060 --> 00:52:04,330
И така, ако одите во, почнете со дури контрола F'ing за Примерок,

613
00:52:04,330 --> 00:52:08,330
види кога Примерок и прави сигурни дека ќе ги ослободи сите на кои

614
00:52:08,330 --> 00:52:10,190
но тогаш само оди преку вашиот код,

615
00:52:10,190 --> 00:52:14,260
разбирање каде што може да се распределени меморија.

616
00:52:14,260 --> 00:52:21,340
Обично вие само може да се каже, "На крајот на датотеката јас сум само ќе ги отстрани шума на мојата шума"

617
00:52:21,340 --> 00:52:23,850
Значи, во основа јасно дека меморијата, слободна дека,

618
00:52:23,850 --> 00:52:28,310
"И тогаш јас сум исто така, ќе го затвори датотека, а потоа мојата програма ќе се откажам."

619
00:52:28,310 --> 00:52:33,810
Но, дали е тоа единствениот пат дека вашата програма поднесе оставка?

620
00:52:33,810 --> 00:52:37,880
Не, затоа што понекогаш може да е грешка што се случи.

621
00:52:37,880 --> 00:52:42,080
Можеби не можеме да отворите датотека или ние не би можеле да направат друго дрво

622
00:52:42,080 --> 00:52:49,340
или некој вид на грешка се случи во распределбата на меморија процес и затоа таа се врати NULL.

623
00:52:49,340 --> 00:52:56,710
Грешка се случи, а потоа се вративме и се повлече.

624
00:52:56,710 --> 00:53:02,040
Па тогаш ќе сакате да бидете сигурни дека сите можни време дека вашата програма може да престанам,

625
00:53:02,040 --> 00:53:06,980
сакате да ги ослободи сите на вашата мемориска таму.

626
00:53:06,980 --> 00:53:13,370
Тоа не е само ќе биде на самиот крај од главната функција што ќе ја завршите вашиот код.

627
00:53:13,370 --> 00:53:20,780
Сакате да се погледне назад во секој случај дека вашиот код потенцијално може да се врати предвреме

628
00:53:20,780 --> 00:53:25,070
и тогаш слободно без оглед меморија прави смисла.

629
00:53:25,070 --> 00:53:30,830
Велат дека се јавил направи шума и дека се врати лажни.

630
00:53:30,830 --> 00:53:34,230
Тогаш веројатно нема да има потреба да ги отстраните вашите шума

631
00:53:34,230 --> 00:53:37,080
затоа што немаат шумата сеуште.

632
00:53:37,080 --> 00:53:42,130
Но, во секоја точка во кодот каде што може да се врати предвреме

633
00:53:42,130 --> 00:53:46,160
вие сакате да бидете сигурни дека ќе ги ослободи сите можни меморија.

634
00:53:46,160 --> 00:53:50,020
>> Значи, кога ние сме се занимаваат со ослободување на меморија и има потенцијал протекување,

635
00:53:50,020 --> 00:53:55,440
ние сакаме да го користи само наше мислење и нашата логика

636
00:53:55,440 --> 00:54:01,850
но исто така се користи Valgrind да се утврди дали ние сме ослободени сите наши меморија правилно или не.

637
00:54:01,850 --> 00:54:09,460
Можете или да го извршите Valgrind на издувам, а потоа мора да се, исто така, го предадете

638
00:54:09,460 --> 00:54:14,020
вистинскиот број на командната линија аргументи Valgrind.

639
00:54:14,020 --> 00:54:18,100
Можете да го извршите тоа, но на излез е малку криптичната.

640
00:54:18,100 --> 00:54:21,630
Ние добивано и малку се користи за да со правопис, но ние сепак треба малку повеќе помош,

641
00:54:21,630 --> 00:54:26,450
па потоа трча со неколку знамиња како течење проверете = полн,

642
00:54:26,450 --> 00:54:32,040
дека веројатно ќе ни даде некои повеќе корисни излез на Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Па уште еден корисен совет кога сте дебагирање е команда разл.

644
00:54:39,040 --> 00:54:48,520
Можете да пристапите до имплементација на персоналот на Хаф, работи кои на еден текст фајл,

645
00:54:48,520 --> 00:54:55,400
а потоа излез на бинарна датотека, бинарен Хаф датотека, да бидат конкретни.

646
00:54:55,400 --> 00:54:59,440
Потоа, ако се кандидира свој здив на тој бинарна датотека,

647
00:54:59,440 --> 00:55:03,950
тогаш идеално, вашиот outputted текстуална датотека ќе биде идентична

648
00:55:03,950 --> 00:55:08,200
на оригиналниот оној што го донесе внатре

649
00:55:08,200 --> 00:55:15,150
Еве јас сум со користење hth.txt како пример, а тоа е еден зборуваше во вашиот спецификации.

650
00:55:15,150 --> 00:55:21,040
Тоа е буквално само HTH, а потоа нова линија.

651
00:55:21,040 --> 00:55:30,970
Но дефинитивно се чувствувам слободно и вие сте дефинитивно охрабруваат да ги користат повеќе примери

652
00:55:30,970 --> 00:55:32,620
за вашиот текст фајл.

653
00:55:32,620 --> 00:55:38,110
>> Можете дури и да се сними во можеби компресирање а потоа декомпресија

654
00:55:38,110 --> 00:55:41,600
некои од фајловите што ќе се користи во правопис како Војна и мир

655
00:55:41,600 --> 00:55:46,710
или Џејн Остин или нешто слично - тоа ќе биде вид на кул - или Остин сили,

656
00:55:46,710 --> 00:55:51,880
вид на справување со поголеми фајлови, бидејќи ние нема да дојде до тоа

657
00:55:51,880 --> 00:55:55,590
ако ние се користи следната алатка тука, ls-l.

658
00:55:55,590 --> 00:56:01,150
Ние сме навикнати да ls, што во основа ги содржи сите содржини во нашите тековниот директориум.

659
00:56:01,150 --> 00:56:07,860
Предавање на знамето-l, всушност, ја покажува големината на овие датотеки.

660
00:56:07,860 --> 00:56:12,690
Ако одите преку спецификации pset, тоа всушност ќе шета низ создавање на бинарна датотека,

661
00:56:12,690 --> 00:56:16,590
на huffing него, и ќе видите дека за многу мали датотеки

662
00:56:16,590 --> 00:56:23,910
просторот трошоците за компресирање на неа, и преведување сите тие информации

663
00:56:23,910 --> 00:56:26,980
на сите фреквенции и работи како што надминува реалните корист

664
00:56:26,980 --> 00:56:30,000
на компресирање на датотеката на прво место.

665
00:56:30,000 --> 00:56:37,450
Но, ако тоа се кандидира на некои повеќе текстуални датотеки, тогаш може да се види дека ќе почнете да се добие некоја корист

666
00:56:37,450 --> 00:56:40,930
во компресирање на овие датотеки.

667
00:56:40,930 --> 00:56:46,210
>> А потоа конечно, имаме нашиот стар другар GDB, која е дефинитивно ќе дојде во рака премногу.

668
00:56:48,360 --> 00:56:55,320
>> Дали имаме било какви прашања на Хаф дрва или процесот можеби за изработка на дрвја

669
00:56:55,320 --> 00:56:58,590
или било какви други прашања за Huff'n издувам?

670
00:57:00,680 --> 00:57:02,570
Во ред. Јас ќе останат околу за малку.

671
00:57:02,570 --> 00:57:06,570
>> Ви благодариме, секого. Ова беше можи 6. И среќа.

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