1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Праходжанне - Праблема Set 6]

2
00:00:02,210 --> 00:00:04,810
[Zamyla Chan - Гарвардскі універсітэт]

3
00:00:04,810 --> 00:00:07,240
[Гэта CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Прывітанне ўсім, і дабро запрашаем Праходжанне 6: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
У Puff Huff'n тое, што мы робім, будзем мець справу з файламі Хафман сціснутага

6
00:00:17,440 --> 00:00:20,740
, А затым пыхкаючы яго назад уверх, так распакавання гэтага,

7
00:00:20,740 --> 00:00:25,810
так што мы можам перакладаць з 0 і 1, якія карыстальнік пасылае нам

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 і 5 і PSET роду аб'яднання іх у 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
>> Пераходзячы да Puff Huff'n, наш інструментар для гэтага PSET збіраецеся быць Huffman дрэў,

17
00:01:09,760 --> 00:01:14,700
таму разуменне не толькі як двайковыя дрэвы працу, але і спецыяльна Huffman дрэў,

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
Huffman дрэў бінарныя дрэвы, а гэта азначае, што кожны вузел мае толькі 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
Мы бачылі ў лекцыі прыклады кода Морзэ, які выгляд кансалідаванага некалькі лістоў.

39
00:02:32,690 --> 00:02:38,030
Калі вы спрабуеце перавесці або E, напрыклад,

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
У нас жа ідэя тут у дрэвы Huffman

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
Як мы бачылі ў азбуцы Морзэ, адзін глюк, што калі вы толькі што гукавы сігнал і гукавы сігнал

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
І тое, што Huffman дрэў робіць гэта таму, што па характары персанажаў

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
Натуральна, што я збіраюся сказаць, я выкарыстоўваю B часцей за ўсё,

77
00:05:28,970 --> 00:05:35,970
Таму я хачу, каб прадстаўляць B з найменшай колькасцю бітаў, найменшая колькасць 0 і 1.

78
00:05:35,970 --> 00:05:42,600
А потым я таксама збіраюся чакаць C патрабаваць найбольшая колькасць 0 і 1, а таксама.

79
00:05:42,600 --> 00:05:48,550
Першае, што я зрабіў тут я змясціў іх у парадку ўзрастання па частаце.

80
00:05:48,550 --> 00:05:52,710
Мы бачым, што C і A, тыя нашы 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, каб дабрацца да A.

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
дзе, каб дабрацца да B, гэта было б проста біт 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
дзе B, як і меркавалася, мае найменшае.

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
ў вас ёсць радок "Hello".

100
00:07:19,570 --> 00:07:25,360
Што вы робіце, спачатку вы б сказаць колькі разоў H з'явіцца ў гэтым?

101
00:07:25,360 --> 00:07:34,200
H з'яўляецца адзін раз, а затым электроннай з'яўляецца адзін раз, і тады мы маем л з'яўляцца ў два разы

102
00:07:34,200 --> 00:07:36,580
і пра якія з'яўляюцца адзін раз.

103
00:07:36,580 --> 00:07:44,310
І так, то мы чакаем, якое літару, якая будзе прадстаўлена найменшай колькасцю біт?

104
00:07:44,310 --> 00:07:47,450
[Студэнт] л. >> Л. Так. л правоў.

105
00:07:47,450 --> 00:07:50,730
Мы чакаем, што я павінен быць прадстаўлены найменшую колькасць біт

106
00:07:50,730 --> 00:07:55,890
таму што я за ўсё выкарыстоўваецца ў радок "Hello".

107
00:07:55,890 --> 00:08:04,280
Што я буду рабіць цяпер выцягнуць гэтыя вузлы.

108
00:08:04,280 --> 00:08:15,580
У мяне ёсць 1, які з'яўляецца H, а потым яшчэ 1, які з'яўляецца электроннай, а затым 1, што пра -

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
Тады мы маем л прадстаўлены толькі 1 біт, а затым на 2 O

124
00:09:45,880 --> 00:09:52,360
, А затым е на 2, а затым H падае да 3 біт.

125
00:09:52,360 --> 00:09:59,750
Такім чынам, вы можаце перадаваць гэта паведамленне "Hello", а на самай справе выкарыстання сімвалаў

126
00:09:59,750 --> 00:10:02,760
на толькі 0 і 1.

127
00:10:02,760 --> 00:10:07,910
Аднак варта памятаць, што ў шэрагу выпадкаў мы мелі сувязяў з нашай частаце.

128
00:10:07,910 --> 00:10:11,900
Мы маглі б альбо далучыліся да H і O Год можа быць.

129
00:10:11,900 --> 00:10:15,730
Ці потым, калі ў нас было л прадстаўлены 2

130
00:10:15,730 --> 00:10:19,410
а таксама далучыўся да адной прадстаўлены 2, мы маглі бы звязаны ні адзін.

131
00:10:19,410 --> 00:10:23,630
>> І таму, калі вы пасылаеце 0 і 1, што на самой справе не гарантуюць

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
які мы называем лісцем, а тыя будуць проста пустыя значэння.

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", то мы злічыць, колькі разоў будзе згадана T,

175
00:13:34,200 --> 00:13:38,420
г згадвалася, I, S, C, 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
якая з'яўляецца T, 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 1

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
Як і чакалася, я і 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 адрозніваецца ад маленькай с.

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
>> Зараз, калі мы разгледзелі Huffman дрэў, мы можам пагрузіцца ў Huff'n Puff, 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
малявання вузлоў, ствараючы свой уласны ЬурейеЕ структуры для вузла,

219
00:17:03,230 --> 00:17:07,230
і, бачачы, як вы маглі б уставіць у бінарным дрэве, той, які сартуецца,

220
00:17:07,230 --> 00:17:09,050
праз яго, і да таго падобнае.

221
00:17:09,050 --> 00:17:14,560
Гэта веданне, безумоўна, дапаможа вам, калі вы апускаецеся ў частцы Puff Huff'n

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

223
00:17:19,150 --> 00:17:26,329
У стандартным выданні PSET, ваша задача складаецца ў рэалізацыі Puff,

224
00:17:26,329 --> 00:17:30,240
і ў хакерскай версіі вашай задачай з'яўляецца рэалізацыя Хафф.

225
00:17:30,240 --> 00:17:38,490
Што Хафф робіць гэта бярэ тэкст, а затым ён перакладае яго ў 0 і 1,

226
00:17:38,490 --> 00:17:41,990
так што працэс, які мы зрабілі вышэй, дзе мы разлічвалі частот

227
00:17:41,990 --> 00:17:50,970
, А затым зрабіў дрэва, а затым сказаў: "Як я магу атрымаць T?"

228
00:17:50,970 --> 00:17:54,840
T прадстаўлена на 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
Затым з Puff дадзена двайковы файл з 0 і 1

233
00:18:17,980 --> 00:18:21,740
і таксама з улікам інфармацыі аб частотах.

234
00:18:21,740 --> 00:18:26,740
Мы пераводзім усе гэтыя 0 і 1 вяртаецца ў зыходнае паведамленне, што было,

235
00:18:26,740 --> 00:18:29,350
так што мы распакавання гэтага.

236
00:18:29,350 --> 00:18:36,450
Калі вы робіце Standard Edition, вам не трэба ажыццяўляць Хафф,

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
а затым выкарыстоўваць гэты выхад як ваш ўклад у зацяжку.

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
таму што ў. з файламі, таму што ў нас ёсць. г

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, у каментарах ён заяўляе пласт абстракцыі для Huffman-кадаваных файлаў.

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
Тады тут у нас ёсць чароўны нумар для ідэнтыфікацыі Huffman-кадаваных файлаў.

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
Тут мы маем структуру для Хафман файл у кадоўцы.

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
Cute.

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
Тады ў нас ёсць некаторыя функцыі, якія вяртаюць наступны біт у файле Huff

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
Раней мы мелі справу з прамым проста Fclose,

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
Ён мае ўсе файлавага ўводу / высновы тут справу з паказальнікамі.

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
і мы зрабілі ЬурейеЕ вузла структуры.

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
Назад да Speller, калі вы рабілі новы вузел

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 значэнне, так 0s або нулі,

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
Гэта свайго роду люстраное ў файл * ўваход = Еореп,

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
замест Еореп вы перадаеце ў 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
Затым усе гэтыя праверкі, каб пераканацца, што файл, які мы адкрытыя з'яўляецца актуальнай фыркнуў файл ці не.

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, якая з'яўляецца вынікам пыхкаючы файл

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
Калі мы паглядзім, большасць з іх 0s за выключэннем гэтага: H, якая з'яўляецца двойчы,

390
00:32:51,180 --> 00:32:54,820
, А затым T, які з'яўляецца адзін раз.

391
00:32:54,820 --> 00:33:07,860
А то тут мы маем фактычнае паведамленне ў 0 і 1.

392
00:33:07,860 --> 00:33:15,450
Калі мы паглядзім на hth.txt, які меркавана зыходнае паведамленне, якое было фыркнуў,

393
00:33:15,450 --> 00:33:22,490
мы чакаем ўбачыць некаторыя Hs і Ц. там.

394
00:33:22,490 --> 00:33:28,720
У прыватнасці, мы чакаем ўбачыць толькі 1 і 2 T Hs.

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 і затым на наступны Н 1, а

401
00:34:17,120 --> 00:34:21,139
а то ў нас новая радок пазначаецца двума 0s.

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

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
а таксама сыходзіць з гэтага, каб убачыць, як вы маглі б зрабіць вашу Puff файл

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
Раней, калі мы былі проста робіць нашу Huffman дрэў,

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, Cs і

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? Добра. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Што мы павінны зрабіць для Puff?

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 і 1, што яны прайшлі ў,

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
Гэта выкарыстанне. І зараз мы хочам пераканацца, што ўваход разбушаваўся, ці не.

459
00:39:08,820 --> 00:39:16,420
Успамінаючы, было што-небудзь у размеркаванні код, які можа дапамагчы нам

460
00:39:16,420 --> 00:39:21,570
з разуменнем, ці з'яўляецца файл разбушаваўся, ці не?

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
І так, каб зрабіць гэта, ён павінен быў праверыць ці сапраўды яна была як раз'юшыўся, ці не.

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
і мы інтэрпрэтавалі, што для дэтэктыўны раман і змяненне памеру,

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
аб тым, як пераканацца, што ўваход на самай справе як раз'юшыўся, ці не

477
00:40:40,540 --> 00:40:43,240
, А таксама некалькі іншых рэчаў.

478
00:40:45,930 --> 00:40:50,250
Мы забяспечылі належнага выкарыстання і запэўніў, што ўваход фыркнуў.

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 вяртае хлусня, то мы ведаем, што мы сутыкнуліся з нейкай памылкай

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 (х)).

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
Але калі ты памылак, вы толькі хочаце кінуць паліць, калі ваша функцыя вяртае хлусня.

556
00:47:11,800 --> 00:47:16,090
Што вы можаце зрабіць, гэта проста дадаць == ілжывых або проста дадаць выбуху перад ім

557
00:47:16,090 --> 00:47:21,010
, А затым, калі ў вас ёсць (! 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 і 1.

573
00:48:39,260 --> 00:48:45,480
І так па традыцыі мы ведаем, што ў дрэве Хафман 0s паказваюць пакінуў

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
[Студэнт] Калі паказальнікаў NULL. >> Так.

583
00:49:24,040 --> 00:49:32,220
Мы можам сказаць, калі мы трапілі лісце, калі паказальнікі на левага і правага дрэвы NULL.

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

585
00:49:34,110 --> 00:49:40,320
Мы ведаем, што мы хочам чытаць па макулінках ў нашым файле Хафф.

586
00:49:43,870 --> 00:49:51,220
Як мы бачылі раней у dump.c, што яны зрабілі, яны чыталі ў біт за бітам ў файл Huff

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
Грунтуючыся на гэтым, то вы будзеце жадаць мець нейкі итератор

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
Вы збіраецеся хочаце альбо рухацца, што итератор на левым ці перамясціць яго ў правы

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
Чаму мы можам зрабіць гэта з дапамогай файла Хафман, але не азбукі Морзэ?

599
00:50:54,300 --> 00:50:56,610
Таму што ў азбуцы Морзэ ёсць трохі двухсэнсоўнасці.

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
, Калі левая і правая дзяцей гэтага вузла з'яўляюцца NULL.

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 на Puff, а затым вы павінны таксама прайсці яго

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
Мы атрымалі трохі прывыкнуць да яго з Speller, але ў нас усё яшчэ трэба крыху больш дапамогі,

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
Затым ідэале, які выводзіцца тэкставага файла будзе ідэнтычным

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
некаторыя з файлаў, якія вы выкарыстоўвалі ў Speller, як вайна і мір

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-л.

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
з пыхкаючы, і вы ўбачыце, што для вельмі маленькіх файлаў

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
або любыя іншыя пытанні па Puff 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]