1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Gözden geçirmek - Problem Set 6]

2
00:00:02,210 --> 00:00:04,810
[Zamyla Chan - Harvard Universiteti]

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

4
00:00:07,240 --> 00:00:12,180
>> Salam, hər kəs və gözden geçirmek 6 xoş gəlmisiniz: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
Huff'n Puff biz nə bir Huffman sıkıştırılmış fayl ilə məşğul olacaq

6
00:00:17,440 --> 00:00:20,740
və sonra geri o şişirme belə decompressing

7
00:00:20,740 --> 00:00:25,810
biz 0s və 1s istifadəçi bizə göndərir ki, tərcümə edə bilərsiniz, belə ki,

8
00:00:25,810 --> 00:00:30,660
və orijinal mətn daxil geri çevirmək.

9
00:00:30,660 --> 00:00:34,360
Siz tools bəzi görmək olacaq çünki Pset 6 olduqca sərin olacaq

10
00:00:34,360 --> 00:00:41,730
siz 1 olduqca səliqəli anlayışı onları birləşdirən pset 4 və pset 5 və cür istifadə

11
00:00:41,730 --> 00:00:43,830
Bu barədə düşünmək gələndə.

12
00:00:43,830 --> 00:00:50,110
>> Həmçinin, arguably, pset 4 və 5 təklif etdi ki, ən çətin psets idi.

13
00:00:50,110 --> 00:00:53,950
Beləliklə, biz, C, bu 1 daha pset var

14
00:00:53,950 --> 00:00:56,480
və sonra sonra biz web proqramlaşdırma üçün edirik.

15
00:00:56,480 --> 00:01:02,310
Belə ki, CS50 də çətin donqar üzərində almaq üçün özünüzü təbrik edirəm.

16
00:01:03,630 --> 00:01:09,760
>> Huff'n Puff üçün hərəkət, bu pset üçün Toolbox, Huffman ağacları olacaq

17
00:01:09,760 --> 00:01:14,700
belə binar ağac iş, həm də xüsusi Huffman ağacı yalnız necə başa

18
00:01:14,700 --> 00:01:16,240
necə inşa edirik.

19
00:01:16,240 --> 00:01:20,210
Və sonra biz bu pset paylanması kodu bir çox olacaq

20
00:01:20,210 --> 00:01:22,480
və biz kodu bəzi həqiqətən görmək gəlmək lazımdır

21
00:01:22,480 --> 00:01:24,670
biz hələ tam dərk edə bilər

22
00:01:24,670 --> 00:01:30,080
və həmin onların müşayiət. h faylları. c faylları, lakin edəcək

23
00:01:30,080 --> 00:01:34,300
Bizi biz bu funksiyaları necə bilirik ki, lazımdır ki, kifayət qədər anlayış verəcək

24
00:01:34,300 --> 00:01:38,100
və ya ən azı nə onlar ehtimal olunur - onların giriş və çıxış -

25
00:01:38,100 --> 00:01:40,760
biz qara qutusuna nə bilmirəm, hətta

26
00:01:40,760 --> 00:01:44,090
ərzində və ya qara qutu nə baş başa düşmürəm.

27
00:01:44,090 --> 00:01:49,400
Və sonra nəhayət, adi kimi, biz yeni data strukturları ilə məşğul olan

28
00:01:49,400 --> 00:01:51,840
ki qovşaqlarının xüsusi növləri müəyyən şeylər qeyd

29
00:01:51,840 --> 00:01:56,080
və belə ki, burada dizayn prosesi üçün təkcə qələm və kağız olan

30
00:01:56,080 --> 00:01:58,470
və zaman pset iş necə anlamaq çalışdığınız

31
00:01:58,470 --> 00:02:00,520
həm də ayıklama zamanı.

32
00:02:00,520 --> 00:02:06,140
Siz dəyərlər nə yazmaq isə Siz qələm və kağız yanaşı gdb ola bilər

33
00:02:06,140 --> 00:02:09,320
harada oxlar işarə edərək, və elə şeylər edir.

34
00:02:09,320 --> 00:02:13,720
>> Birinci Huffman ağacları baxaq.

35
00:02:13,720 --> 00:02:19,600
Huffman ağac hər node yalnız 2 övladı var, yəni, ikili ağacları daxildir.

36
00:02:19,600 --> 00:02:24,870
Huffman ağacları xarakterik olan ən tez-tez dəyərlər

37
00:02:24,870 --> 00:02:27,140
ən az bit ilə təmsil olunur.

38
00:02:27,140 --> 00:02:32,690
Biz Morse kodu mühazirə nümunələri icmal hansı cür bir məktub gördü.

39
00:02:32,690 --> 00:02:38,030
Məsələn, A və ya E, tərcümə çalışdığınız Əgər

40
00:02:38,030 --> 00:02:43,940
Əgər tez-tez tərcümə edirik, belə əvəzinə bit tam set istifadə edərək

41
00:02:43,940 --> 00:02:48,640
ki, adi data növü üçün ayrılmış, siz daha az üçün aşağı kompres

42
00:02:48,640 --> 00:02:53,730
və sonra təmsil edən məktublar az tez-tez artıq bit ilə təmsil olunur

43
00:02:53,730 --> 00:02:59,840
bu məktublar görünür ki, tezliklərin həyata çəkin zaman ki, ödəyə bilər.

44
00:02:59,840 --> 00:03:03,020
Biz Huffman ağacları burada eyni fikir

45
00:03:03,020 --> 00:03:12,360
biz bir zəncir, müəyyən simvol almaq üçün yol bir növ edir.

46
00:03:12,360 --> 00:03:14,470
Və sonra ən tezliyi olan simvol

47
00:03:14,470 --> 00:03:17,940
ən az bit ilə təmsil olunur.

48
00:03:17,940 --> 00:03:22,020
>> Bir Huffman ağac tikmək yolu

49
00:03:22,020 --> 00:03:27,430
mətn görünür ki, simvol bütün yerləşdirilməsi ilə

50
00:03:27,430 --> 00:03:30,630
və onların tezliyi hesablanması, necə tez-tez görünür.

51
00:03:30,630 --> 00:03:33,880
Bu, ya o məktublar görünür neçə dəfə bir sayı ola bilər

52
00:03:33,880 --> 00:03:40,270
və ya bəlkə hər bir əmələ nə qədər bütün simvol həyata faizi.

53
00:03:40,270 --> 00:03:44,270
Və nə siz, bir dəfə ki, eşlenen həyata bütün var

54
00:03:44,270 --> 00:03:49,060
sonra 2 aşağı tezliklərin axtarmaq və sonra bacı kimi onlara qoşulmaq

55
00:03:49,060 --> 00:03:55,660
daha sonra ana node onun 2 övladı məbləğin olan tezlik var.

56
00:03:55,660 --> 00:04:00,870
Və sonra siz Konvensiya tərəfindən demək ki sol node,

57
00:04:00,870 --> 00:04:03,770
Siz 0 filial aşağıdakı tabe

58
00:04:03,770 --> 00:04:08,140
və sonra rightmost node 1 qoludur.

59
00:04:08,140 --> 00:04:16,040
Biz Morse kodu gördüm kimi, bir gotcha idi ki, yalnız bir beep və beep olsaydı

60
00:04:16,040 --> 00:04:18,120
bu birmənalı idi.

61
00:04:18,120 --> 00:04:22,430
Bu da 1 məktub ola bilər və ya 2 məktubları bir sequence ola bilər.

62
00:04:22,430 --> 00:04:27,790
Və nə Huffman ağac yoxdur ki, simvol təbiəti çünki

63
00:04:27,790 --> 00:04:34,140
və ya bizim son faktiki simvol şöbəsində son qovşaqlarının olan -

64
00:04:34,140 --> 00:04:39,300
biz yarpaqları həmin baxın - ki, əsasən hər hansı bir qeyri ola bilməz

65
00:04:39,300 --> 00:04:45,160
siz bit seriyası ilə kodlar çalışdığınız olan məktub baxımından

66
00:04:45,160 --> 00:04:50,670
çünki 1 məktub təmsil edən bit boyunca heç bir yerdə

67
00:04:50,670 --> 00:04:55,960
Başqa bir bütöv məktub qarşılaşacaq və hər hansı bir qarışıqlıq olmayacaq.

68
00:04:55,960 --> 00:04:58,430
Amma siz uşaqlar həqiqətən görürük ki nümunələri daxil lazımdır ki,

69
00:04:58,430 --> 00:05:02,120
əvəzinə bizə yalnız doğru belirten.

70
00:05:02,120 --> 00:05:06,390
>> Üzrə Huffman ağac sadə bir misal baxaq.

71
00:05:06,390 --> 00:05:09,380
Mən 12 simvol uzunluğunda ki, burada bir simli var.

72
00:05:09,380 --> 00:05:14,010
Mən 6 pansiyonlar, 2 Cs kimi 4 var.

73
00:05:14,010 --> 00:05:17,270
Mənim ilk addım saymaq olardı.

74
00:05:17,270 --> 00:05:20,760
A neçə dəfə görünür? Bu simli 4 dəfə görünür.

75
00:05:20,760 --> 00:05:25,060
B 6 dəfə görünür, və C 2 dəfə görünür.

76
00:05:25,060 --> 00:05:28,970
Təbii ki, mən ən çox B kullanıyorum demək gedirəm

77
00:05:28,970 --> 00:05:35,970
Mən bit və az sayı 0s və 1s və az sayı ilə B təmsil etmək istəyirəm.

78
00:05:35,970 --> 00:05:42,600
Və sonra da C həmçinin 0s və 1s ən məbləğ tələb gözləmək gedirəm.

79
00:05:42,600 --> 00:05:48,550
Birinci mən burada nə mən tezliyi baxımından üçün artan onlara yerləşdirilir.

80
00:05:48,550 --> 00:05:52,710
Biz C və A, bu bizim 2 aşağı tezliklərin ki, görürük.

81
00:05:52,710 --> 00:06:00,290
Biz bir valideyn node yaratmaq və valideyn node Bugün məktub yoxdur

82
00:06:00,290 --> 00:06:05,070
lakin bu məbləğ bir tezlik, yoxdur.

83
00:06:05,070 --> 00:06:08,780
Cəmi 6 olan 2 + 4 olur.

84
00:06:08,780 --> 00:06:10,800
Sonra sol qolu edin.

85
00:06:10,800 --> 00:06:14,970
Biz 6 node idi, onda biz C almaq üçün 0 edin ki,

86
00:06:14,970 --> 00:06:17,450
və sonra 1 A. almaq

87
00:06:17,450 --> 00:06:20,300
Belə ki, indi biz 2 qovşaqlarının var.

88
00:06:20,300 --> 00:06:23,920
Biz dəyəri 6 və sonra da dəyəri 6 başqa bir node var.

89
00:06:23,920 --> 00:06:28,550
Və həmin 2 ən aşağı 2, həm də sol yalnız 2 deyil, yalnız

90
00:06:28,550 --> 00:06:33,820
biz cəmi 12 olmaqla, başqa valideyn həmin buyurun.

91
00:06:33,820 --> 00:06:36,300
Belə ki, burada biz Huffman ağac var

92
00:06:36,300 --> 00:06:40,020
B almaq üçün harada, yalnız az 1 olacaq

93
00:06:40,020 --> 00:06:45,430
və sonra A almaq üçün biz C 00 olan sonra 01 və olacaq.

94
00:06:45,430 --> 00:06:51,300
Belə ki, burada biz əsasən biz 1 və ya 2 bit ya bu chars təmsil etdiyiniz bax

95
00:06:51,300 --> 00:06:55,160
Ü kimi proqnozlaşdırılmış B,, az var.

96
00:06:55,160 --> 00:07:01,730
Və sonra, biz C ən olması gözlənilir, lakin belə bir kiçik Huffman ağac olduğundan

97
00:07:01,730 --> 00:07:06,020
sonra bir də ortasında yerə qarşı 2 bit təmsil olunur.

98
00:07:07,820 --> 00:07:11,070
>> Yalnız Huffman ağac bir sadə misal üzərində getmək üçün

99
00:07:11,070 --> 00:07:19,570
Siz simli var demək "Hello".

100
00:07:19,570 --> 00:07:25,360
Nə siz neçə dəfə H bu görünür deyərdim ilk?

101
00:07:25,360 --> 00:07:34,200
H dəfə və sonra e görünür görünür bir dəfə və daha sonra iki dəfə görünen l var

102
00:07:34,200 --> 00:07:36,580
və o bir dəfə görünmesi.

103
00:07:36,580 --> 00:07:44,310
Və sonra biz bit ən az təmsil edən məktubu gözləyirik?

104
00:07:44,310 --> 00:07:47,450
[Tələbə] l. >> L. Bəli. l hüququdur.

105
00:07:47,450 --> 00:07:50,730
Biz l bit ən az təmsil gözləyirik

106
00:07:50,730 --> 00:07:55,890
çünki l "Hello". simli ən istifadə olunur

107
00:07:55,890 --> 00:08:04,280
Mən indi gedirəm nə bu qovşaqlarının çıxartmaq olunur.

108
00:08:04,280 --> 00:08:15,580
Mən o olan e olan digər 1, sonra 1, H olan, 1 var, -

109
00:08:15,580 --> 00:08:23,410
l olan, sonra 2 - İndi onları qoyulması alıram.

110
00:08:23,410 --> 00:08:32,799
Sonra mən Huffman ağac qurmaq yolu ən tezliklərin ilə 2 qovşaqlarının tapmaq demək

111
00:08:32,799 --> 00:08:38,010
və valideyn node yaratmaqla onları bacı edir.

112
00:08:38,010 --> 00:08:41,850
Burada ən aşağı tezlikli 3 qovşaqlarının var. Onlar 1 istəyirik.

113
00:08:41,850 --> 00:08:50,620
Belə ki, burada biz ilk keçid olacaq bir seçin.

114
00:08:50,620 --> 00:08:54,850
Gəlin mən H və E seçmək deyirlər.

115
00:08:54,850 --> 00:09:01,150
1 məbləği + 1 2 deyil, bu node Bugün məktub mövcut deyil.

116
00:09:01,150 --> 00:09:04,440
Bu, yalnız dəyəri vardır.

117
00:09:04,440 --> 00:09:10,950
İndi biz növbəti 2 aşağı tezliklərin oldu.

118
00:09:10,950 --> 00:09:15,590
Ki, 2 və 1 var. Bu da o 2 ola bilər, amma bu bir seçmək üçün gedirəm.

119
00:09:15,590 --> 00:09:18,800
Cəmi 3.

120
00:09:18,800 --> 00:09:26,410
Və sonra nəhayət, mən yalnız sonra 5 olur ki, 2 sol var.

121
00:09:26,410 --> 00:09:32,010
Mən bunun üçün kodlama doldurmaq Əgər burada kimi gözlənilir

122
00:09:32,010 --> 00:09:37,480
1s həmişə düzgün filialı və 0s sol bir olunur.

123
00:09:37,480 --> 00:09:45,880
Sonra 2-yalnız 1 bit və sonra o təmsil l var

124
00:09:45,880 --> 00:09:52,360
və sonra 2-e, sonra H 3 bit aşağı düşür.

125
00:09:52,360 --> 00:09:59,750
Belə ki, "Hello" Bu mesaj ötürmək bilər əvəzinə faktiki Sandıqı istifadə edərək,

126
00:09:59,750 --> 00:10:02,760
yalnız 0s və 1s tərəfindən.

127
00:10:02,760 --> 00:10:07,910
Lakin, bir neçə hallarda biz tezliyi ilə əlaqələri olduğunu unutmayın.

128
00:10:07,910 --> 00:10:11,900
Biz ya bəlkə ilk H və o qoşulmuşdur bilər.

129
00:10:11,900 --> 00:10:15,730
Yoxsa sonra biz 2 təmsil l zaman haqqında

130
00:10:15,730 --> 00:10:19,410
həmçinin 2 təmsil bir qoşulub, biz bir bağlı ola bilər.

131
00:10:19,410 --> 00:10:23,630
>> Və siz göndərmək zaman 0s və 1s, həqiqətən, zəmanət deyil

132
00:10:23,630 --> 00:10:27,090
Alıcı tam hüququ yarasa off oxumaq bilər ki,

133
00:10:27,090 --> 00:10:30,490
onlar edən qərar bilmirəm bilər, çünki.

134
00:10:30,490 --> 00:10:34,920
Beləliklə, biz Huffman sıxılma ilə məşğul olduğunuz zaman,

135
00:10:34,920 --> 00:10:40,090
birtəhər biz qərara necə bizim mesaj alan demək var -

136
00:10:40,090 --> 00:10:43,470
Onlar əlavə məlumat bir növ bilmək lazımdır

137
00:10:43,470 --> 00:10:46,580
sıxılmış mesaj əlavə.

138
00:10:46,580 --> 00:10:51,490
Onlar ağac həqiqətən kimi görünür nə başa düşmək lazımdır

139
00:10:51,490 --> 00:10:55,450
biz, həqiqətən, bu qərarlar qəbul necə.

140
00:10:55,450 --> 00:10:59,100
>> Burada biz yalnız faktiki sayı əsasında nümunələri edirdilər

141
00:10:59,100 --> 00:11:01,550
amma bəzən də bir Huffman ağac ola bilər

142
00:11:01,550 --> 00:11:05,760
tezlik əsasında hərfləri görünür, bu eyni proses var olan.

143
00:11:05,760 --> 00:11:09,090
Burada, faiz və ya bir qismini baxımından bu ifadə edirəm

144
00:11:09,090 --> 00:11:11,290
və belə ki, burada eyni şey.

145
00:11:11,290 --> 00:11:15,300
I, 2-aşağı, onları vurmaq, aşağı növbəti 2, onlara yekun tapmaq

146
00:11:15,300 --> 00:11:19,390
Mən tam ağac qədər.

147
00:11:19,390 --> 00:11:23,610
Biz biz faiz ilə məşğul olduğunuz zaman ya yol, nə ola bilər baxmayaraq,

148
00:11:23,610 --> 00:11:27,760
biz şeyi ayırıcı və ondalık ilə məşğul olduğunuz deməkdir və ya daha çox üzüb gedirdi ki,

149
00:11:27,760 --> 00:11:30,900
biz bir baş data strukturları düşünərək edirsinizsə.

150
00:11:30,900 --> 00:11:32,540
Biz üzüb gedirdi haqqında nə bilirik?

151
00:11:32,540 --> 00:11:35,180
Biz üzüb gedirdi ilə məşğul olduğunuz zaman ortaq problem nədir?

152
00:11:35,180 --> 00:11:38,600
[Tələbə] qeyri-dəqiq hesab. >> Bəli. Qeyri-dəqiqlik.

153
00:11:38,600 --> 00:11:43,760
Çünki üzən qeyri-dəqiqlik, bu pset biz əmin olun ki,

154
00:11:43,760 --> 00:11:49,450
biz heç bir dəyərləri itirmək deyil ki, biz, həqiqətən, sayı ilə məşğul olmaq üçün olacaq.

155
00:11:49,450 --> 00:11:54,880
Siz burada quruluşuna geri baxmaq əgər, bir Huffman node hesab idi əgər

156
00:11:54,880 --> 00:12:01,740
siz yaşıl isə baxmaq əgər Bugün tezlik var

157
00:12:01,740 --> 00:12:08,760
habelə onun sol bir node habelə hüququ bir node göstərir.

158
00:12:08,760 --> 00:12:13,970
Və sonra qırmızı olanlar orada da onlara bağlı bir xarakter daşıyır.

159
00:12:13,970 --> 00:12:18,900
Biz valideynlər və sonra yekun qovşaqlarının üçün ayrı-ayrı olanları etmək fikrində deyilik

160
00:12:18,900 --> 00:12:23,680
olan biz yarpaqları kimi istinad deyil, o yalnız NULL dəyərlər var.

161
00:12:23,680 --> 00:12:31,050
Hər node üçün biz bir xarakter ki, node təmsil simvolu olacaq

162
00:12:31,050 --> 00:12:40,490
sonra tezlik habelə onun sol uşaq, eləcə də sağ uşaq bir göstərici.

163
00:12:40,490 --> 00:12:45,680
Çox altında olan yarpaq, həmçinin node göstəricilərinə olacaq

164
00:12:45,680 --> 00:12:49,550
onların sol və sağ, lakin o dəyərləri faktiki qovşaqlarının işarə deyil, çünki

165
00:12:49,550 --> 00:12:53,970
onların dəyəri nə olardı? >> [Tələbə] NULL. >> NULL. Exactly.

166
00:12:53,970 --> 00:12:58,430
Burada üzüb gedirdi olan tezlik təmsil bilər necə bir misal var

167
00:12:58,430 --> 00:13:02,130
amma biz integers ilə məşğul olmaq üçün olacaq

168
00:13:02,130 --> 00:13:06,780
belə etdim bütün orada data type dəyişdirmək deyil.

169
00:13:06,780 --> 00:13:09,700
>> Üzrə kompleks Məsələn bir az daha davam edək.

170
00:13:09,700 --> 00:13:13,360
Amma indi biz sadə olanları etdik ki, yalnız eyni proses var.

171
00:13:13,360 --> 00:13:20,290
Siz 2 aşağı tezliklərin tapmaq tezliklərin yekun

172
00:13:20,290 --> 00:13:22,450
və ki, sizin ana node yeni tezlik var

173
00:13:22,450 --> 00:13:29,310
daha sonra 1-filialı ilə 0 filialı və sağ ilə sol göstərir.

174
00:13:29,310 --> 00:13:34,200
Biz string "Bu cs50 ki," var, onda biz, T qeyd neçə dəfə saymaq

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

176
00:13:38,420 --> 00:13:42,010
Sonra nə mən burada idi, mən yalnız əkilmiş qırmızı qovşaqlarının ilə

177
00:13:42,010 --> 00:13:48,530
Mən ağac altında nəticədə bu simvol var gedirəm deyib.

178
00:13:48,530 --> 00:13:51,740
Bu yarpaqları bütün olacaq.

179
00:13:51,740 --> 00:13:58,200
Sonra nə etdim, mən sifariş artan tezlik onlara sıralanır edir

180
00:13:58,200 --> 00:14:02,950
və bu əslində pset kodu yoxdur ki, yolu

181
00:14:02,950 --> 00:14:07,550
bu tezlik ilə növ bu və sonra əlifba sırası edir.

182
00:14:07,550 --> 00:14:13,870
Belə ki, tezlik ilə əlifba sırası ilə ilk və sonra nömrələri var.

183
00:14:13,870 --> 00:14:18,520
Sonra nə edəcəyini mən 2 aşağı tapmaq edir. Bu 0 və 5 var.

184
00:14:18,520 --> 00:14:22,390
Mən onları yekunlaşdırmaq olardı ki, 2 deyil. Sonra növbəti 2 aşağı tapmaq, davam edir.

185
00:14:22,390 --> 00:14:26,100
Bu iki 1s və həmin həmçinin 2 çevrilmişdir.

186
00:14:26,100 --> 00:14:31,570
İndi növbəti addım, ən aşağı sayı qoşulması olacaq bilirik ki,

187
00:14:31,570 --> 00:14:41,380
olan, 1-T, sonra tezlik 2 ki qovşaqlarının birini seçmək.

188
00:14:41,380 --> 00:14:44,560
Belə ki, burada biz 3 variantları var.

189
00:14:44,560 --> 00:14:47,980
Mən slayd üçün nə etmək gidiyorum nə yalnız vizual sizin üçün yeniden edir

190
00:14:47,980 --> 00:14:51,790
belə ki, mən bu qədər tikinti oldum necə görə bilərsiniz.

191
00:14:51,790 --> 00:14:59,040
Kodu və bölüşdürülməsi kodu edəcəyimiz nə T bir qoşulmaq olar

192
00:14:59,040 --> 00:15:01,410
0 və 5 node ilə.

193
00:15:01,410 --> 00:15:05,060
Belə ki, daha sonra 3 məbləğləri və biz prosesi davam edir.

194
00:15:05,060 --> 00:15:08,660
2 və 2 indi sonra, 4 bu məbləğ ən aşağı edir.

195
00:15:08,660 --> 00:15:12,560
Hər kəs bu günə qədər sonra? Okay.

196
00:15:12,560 --> 00:15:16,410
Sonra bundan sonra, 3 və əlavə etmək lazımdır ki, 3 mövcut

197
00:15:16,410 --> 00:15:21,650
siz çox messy almaq deyil ki, vizual belə görürük ki, belə daha yalnız keçid alıram.

198
00:15:21,650 --> 00:15:25,740
Biz yalnız 2 qovşaqlarının ki, sonra biz 6, və sonra bizim son addım indi

199
00:15:25,740 --> 00:15:30,440
10 olan ağac kökü etmək o edib.

200
00:15:30,440 --> 00:15:34,100
Hər node təmsil çünki sayı 10, hissi verir

201
00:15:34,100 --> 00:15:40,750
onların dəyəri, onların tezliyi, sayı, onlar simli çıxdı neçə dəfə

202
00:15:40,750 --> 00:15:46,350
və sonra biz simli 5 simvol var, hissi verir ki,.

203
00:15:48,060 --> 00:15:52,320
Biz həqiqətən kodlar necə qədər baxsaq,

204
00:15:52,320 --> 00:15:56,580
gözlənilən kimi, i və ən tez-tez görünür olan s,

205
00:15:56,580 --> 00:16:01,350
bit və az sayda təmsil olunurlar.

206
00:16:03,660 --> 00:16:05,660
>> Burada diqqətli olun.

207
00:16:05,660 --> 00:16:09,780
Huffman ağacları işin faktiki məsələləri.

208
00:16:09,780 --> 00:16:13,670
Bir böyük S kiçik s çox fərqlidir.

209
00:16:13,670 --> 00:16:21,260
Biz idi varsa, kiçik s yalnız iki dəfə görünür sonra, kapital hərflərlə "Bu CS50 deyil"

210
00:16:21,260 --> 00:16:27,120
onun dəyəri 2 ilə node olacaq, sonra böyük S yalnız bir dəfə olacaq.

211
00:16:27,120 --> 00:16:33,440
Həqiqətən burada əlavə yarpaq, çünki Belə ki, sonra ağac strukturları dəyişdirmək olar.

212
00:16:33,440 --> 00:16:36,900
Amma məbləğ hələ 10 olardı.

213
00:16:36,900 --> 00:16:39,570
Yəni biz əslində checksum zəng etmək olacaq nə

214
00:16:39,570 --> 00:16:44,060
bu sayar bütün əlavə.

215
00:16:46,010 --> 00:16:50,990
>> İndi Huffman ağacları əhatə etdik ki, biz Huff'n Puff ki, pset daxil dive bilər.

216
00:16:50,990 --> 00:16:52,900
Biz, suallar bölməsi ilə başlamaq olacaq

217
00:16:52,900 --> 00:16:57,990
və bu ikili ağac və necə ki, ətrafında fəaliyyət ilə vərdiş əldə edir:

218
00:16:57,990 --> 00:17:03,230
rəsm qovşaqlarının, bir node üçün öz typedef struct yaradılması,

219
00:17:03,230 --> 00:17:07,230
və bir ikili ağac, sorted ki, bir daxil ola bilər necə görən,

220
00:17:07,230 --> 00:17:09,050
o ki, kimi şeylər traversing.

221
00:17:09,050 --> 00:17:14,560
Bu bilik mütləq Huff'n Puff hissəsi daxil zaman dive sizə kömək edir

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

223
00:17:19,150 --> 00:17:26,329
Bu pset səviyyəsinin nəşr, sizin vəzifəsi Puff həyata keçirmək

224
00:17:26,329 --> 00:17:30,240
və hacker versiyası Task Huff həyata keçirilməsidir.

225
00:17:30,240 --> 00:17:38,490
Huff edir nə, bu mətn edir və onda 0s və 1s onu çevirir

226
00:17:38,490 --> 00:17:41,990
biz tezliklərin sayılır biz yuxarıda ki prosesi

227
00:17:41,990 --> 00:17:50,970
və sonra ağac və sonra dedi: "Mən T alıram?"

228
00:17:50,970 --> 00:17:54,840
T 100 ilə təmsil olunur ki, kimi şeylər,

229
00:17:54,840 --> 00:17:58,860
və sonra Huff mətn və sonra çıxış edən ikili edəcək.

230
00:17:58,860 --> 00:18:04,920
Lakin biz mesaj bizim alan imkan istəyirəm bilirik ki, çünki

231
00:18:04,920 --> 00:18:11,790
eyni ağac yeniden, bu da tezliyi sayıları haqqında məlumat daxildir.

232
00:18:11,790 --> 00:18:17,980
Sonra Puff biz 0s və 1s bir ikili fayl verilir

233
00:18:17,980 --> 00:18:21,740
və həmçinin tezliklərin haqqında məlumat verilir.

234
00:18:21,740 --> 00:18:26,740
Biz ki, orijinal mesajı o 0s və 1s geri bütün tərcümə

235
00:18:26,740 --> 00:18:29,350
belə ki decompressing edirik.

236
00:18:29,350 --> 00:18:36,450
Siz standart nəşr edirik, siz, Huff həyata ehtiyac yoxdur

237
00:18:36,450 --> 00:18:39,290
belə sonra yalnız Huff heyəti həyata istifadə edə bilərsiniz.

238
00:18:39,290 --> 00:18:42,080
Bunu necə spec ildə təlimat var.

239
00:18:42,080 --> 00:18:48,780
Siz müəyyən bir mətn faylı ilə Huff heyəti həyata çalıştırabilirsiniz

240
00:18:48,780 --> 00:18:53,270
və sonra yastıq üçün giriş kimi çıxış istifadə edin.

241
00:18:53,270 --> 00:18:59,330
>> Mən əvvəl qeyd etdiyim kimi, biz bu bir distribution kodu var.

242
00:18:59,330 --> 00:19:01,810
Mən bunu keçir başlamaq üçün gedirəm.

243
00:19:01,810 --> 00:19:04,400
Mən də çox vaxt sərf etmək niyyətindədir edirəm. H faylları

244
00:19:04,400 --> 00:19:07,660
biz. h var çünki. c faylları, çünki

245
00:19:07,660 --> 00:19:11,650
və ki, funksiyaları prototipləri bizi təmin edir

246
00:19:11,650 --> 00:19:15,520
tam dəqiq anlamaq üçün ehtiyac yoxdur -

247
00:19:15,520 --> 00:19:20,280
Siz. C faylları neler başa düşmürəm, onda çox narahat olmayın

248
00:19:20,280 --> 00:19:23,600
bəzi göstərişlər vermək bilər, çünki mütləq bir nəzər cəhd

249
00:19:23,600 --> 00:19:29,220
və digər insanların kodu oxu üçün istifadə almaq üçün yararlıdır.

250
00:19:38,940 --> 00:19:48,270
>> Huffile.h baxanda şərh bu Huffman kodlu faylları üçün abstraksiya bir qat bəyan edir.

251
00:19:48,270 --> 00:20:01,660
Biz aşağı getmək varsa, biz kodları lazımdır ki, 256 simvol maksimum olduğunu görürük.

252
00:20:01,660 --> 00:20:05,480
Böyük və kiçik - - Bu əlifba bütün məktubları daxildir

253
00:20:05,480 --> 00:20:08,250
və sonra simvol və nömrələri, və s.

254
00:20:08,250 --> 00:20:11,930
Sonra burada bir Huffman kodlu fayl müəyyən bir sehrli var.

255
00:20:11,930 --> 00:20:15,890
Bir Huffman kodu çərçivəsində onlar müəyyən bir sehrli sıra olacaq

256
00:20:15,890 --> 00:20:18,560
mövzu ilə bağlı.

257
00:20:18,560 --> 00:20:21,110
Bu, yalnız bir təsadüfi sehrli sayı kimi ola bilər

258
00:20:21,110 --> 00:20:27,160
həqiqətən ASCII onu tərcümə olsa, o, həqiqətən HUFF həyata spells.

259
00:20:27,160 --> 00:20:34,290
Burada biz bir Huffman-kodlanmış fayl üçün struct var.

260
00:20:34,290 --> 00:20:39,670
Bir Huff fayl ilə bağlı bu xüsusiyyətlər bütün var.

261
00:20:39,670 --> 00:20:47,080
Sonra aşağı burada bir Huff fayl üçün başlıq var, belə ki, biz bu Huffeader zəng

262
00:20:47,080 --> 00:20:50,810
əvəzinə hər halda eyni səslənir, çünki əlavə h durub.

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

264
00:20:52,720 --> 00:20:57,790
Biz bununla bağlı bir sehrli var.

265
00:20:57,790 --> 00:21:09,040
Bir faktiki Huff fayl varsa, o qədər yuxarıda bu sehrli bir sıra olacaq.

266
00:21:09,040 --> 00:21:14,720
Və sonra bir sıra olacaq.

267
00:21:14,720 --> 00:21:18,750
Belə ki, hər bir simvolu üçün olan 256, var

268
00:21:18,750 --> 00:21:24,760
bu simvol tezliyi də Huff fayl ərzində nə siyahısını olacaq.

269
00:21:24,760 --> 00:21:28,090
Və sonra nəhayət, biz tezliklərin üçün checksum var

270
00:21:28,090 --> 00:21:32,160
olan tezliklərin məbləğ olmalıdır.

271
00:21:32,160 --> 00:21:36,520
Belə ki, nə bir Huffeader edir.

272
00:21:36,520 --> 00:21:44,600
Sonra Huff fayl növbəti bit qayıtmaq ki, bəzi funksiyaları vardır

273
00:21:44,600 --> 00:21:52,580
habelə hfclose, burada bu funksiya, sonra Huff fayl bir az yazır,

274
00:21:52,580 --> 00:21:54,650
ki, əslində Huff fayl bağlayır.

275
00:21:54,650 --> 00:21:57,290
Əvvəl, biz düz yalnız fclose ilə məşğul idi

276
00:21:57,290 --> 00:22:01,190
ancaq bir Huff fayl zaman əvəzinə fclosing haqqında

277
00:22:01,190 --> 00:22:06,080
nə həqiqətən nə olacaq hfclose və hfopen edir.

278
00:22:06,080 --> 00:22:13,220
Bu biz ilə məşğul olacaq olduğunuz Huff faylları xüsusi funksiyaları.

279
00:22:13,220 --> 00:22:19,230
Sonra burada mövzu oxumaq və sonra mövzu yazın.

280
00:22:19,230 --> 00:22:25,700
>> Yalnız. H fayl oxuyaraq biz bir Huff fayl ola bilər nə bir mənada almaq cür bilərsiniz

281
00:22:25,700 --> 00:22:32,480
bu, əslində huffile.c daxil davam olmadan, nə xüsusiyyətləri

282
00:22:32,480 --> 00:22:36,750
ki, biz dalış, əgər bir az daha kompleks olacaq.

283
00:22:36,750 --> 00:22:41,270
Bu I / O burada göstəricilər ilə məşğul olan fayl bütün var.

284
00:22:41,270 --> 00:22:48,010
Burada biz hfread zəng zaman, məsələn, hələ fread ilə məşğul ki, görürük.

285
00:22:48,010 --> 00:22:53,050
Biz tamamilə həmin funksiyaları kurtulmanın deyilik, amma biz qayğı bu gönderiyorsanız

286
00:22:53,050 --> 00:22:59,760
əvəzinə özümüzü bütün etmənin Huff fayl daxilində.

287
00:22:59,760 --> 00:23:02,300
Siz maraqlı olduğunuz halda bu vasitəsilə scan pulsuz hiss edə bilərsiniz

288
00:23:02,300 --> 00:23:08,410
və getmək və geri qat bir az qabığı.

289
00:23:20,650 --> 00:23:24,060
>> Biz baxmaq olacaq ki, növbəti fayl tree.h. edir

290
00:23:24,060 --> 00:23:30,210
Bu gözden geçirmek slaydlar əvvəl biz Huffman node gözlədiklərini söylədi

291
00:23:30,210 --> 00:23:32,960
və biz typedef struct node etdi.

292
00:23:32,960 --> 00:23:38,360
Biz simvolu tezlik, sonra 2 node ulduz gözləmir.

293
00:23:38,360 --> 00:23:41,870
Bu halda biz nə edirik bu mahiyyətcə eyni edir

294
00:23:41,870 --> 00:23:46,880
əvəzinə node başqa biz onlara ağac zəng olacaq.

295
00:23:48,790 --> 00:23:56,760
Biz sizə ağac etmək zəng zaman bir ağac göstərici qaytarır bir funksiyası var.

296
00:23:56,760 --> 00:24:03,450
Yeni bir node edilməsi zaman Speller geri

297
00:24:03,450 --> 00:24:11,410
dediniz node * yeni söz = malloc (sizeof) və bu kimi şeylər.

298
00:24:11,410 --> 00:24:17,510
Əsasən, mktree sizin üçün ki, ilə məşğul olacaq.

299
00:24:17,510 --> 00:24:20,990
Eynilə, bir ağac aradan qaldırılması üçün istədiyiniz zaman,

300
00:24:20,990 --> 00:24:24,810
ki, mahiyyətcə, bu ilə bittiğinde ağac azad edir

301
00:24:24,810 --> 00:24:33,790
əvəzinə aydın ki, pulsuz zəng, həqiqətən, yalnız rmtree funksiyasını istifadə etmək olacaq

302
00:24:33,790 --> 00:24:40,360
Əgər ki, ağac üçün pointer keçmək və harada tree.c sizin üçün ki, qayğı olacaq.

303
00:24:40,360 --> 00:24:42,490
>> Biz tree.c. baxmaq

304
00:24:42,490 --> 00:24:47,240
Biz həyata görmək istisna olmaqla, eyni funksiyaları gözləyirik.

305
00:24:47,240 --> 00:24:57,720
Biz gözlənilir ki, siz mktree zəng zaman, bir göstərici bir ağac boy mallocs

306
00:24:57,720 --> 00:25:03,190
bu NULL dəyəri, belə 0s və ya NULLs, bu dəyərlərin bütün initializes

307
00:25:03,190 --> 00:25:08,280
və sonra yalnız sizin üçün malloc'd etdik ki, ağac üçün pointer qaytarır.

308
00:25:08,280 --> 00:25:13,340
Burada ağac aradan zəng zaman ilk ikiqat azad deyilik təmin edir.

309
00:25:13,340 --> 00:25:18,320
Bu, həqiqətən, aradan qaldırılması, istədiyiniz bir ağac var ki, təmin edir.

310
00:25:18,320 --> 00:25:23,330
Bir ağac da öz uşaqlar daxildir, çünki burada

311
00:25:23,330 --> 00:25:29,560
Bu nə o recursively ağac sol node haqqında ağac aradan çağırır

312
00:25:29,560 --> 00:25:31,650
habelə sağ node kimi.

313
00:25:31,650 --> 00:25:37,790
Bu ana kurtarır əvvəl, habelə uşaqların azad etmək lazımdır.

314
00:25:37,790 --> 00:25:42,770
Ana da kök ilə əvəz edir.

315
00:25:42,770 --> 00:25:46,500
Belə böyük-böyük-böyük-böyük babası kimi ilk valideyn,

316
00:25:46,500 --> 00:25:52,130
və ya nənə ağac, ilk biz ilk səviyyəsi aşağı azad var.

317
00:25:52,130 --> 00:25:58,490
Belə ki, o, pulsuz altına axır, sonra o, s, geri pulsuz gəlib

318
00:26:00,400 --> 00:26:02,210
Belə ki, ağac var.

319
00:26:02,210 --> 00:26:04,240
>> İndi biz meşə baxın.

320
00:26:04,240 --> 00:26:09,860
Siz Huffman ağac bütün yerləşdirmək yerləşir Forest edir.

321
00:26:09,860 --> 00:26:12,910
Bu süjet adlı biz bir şey olacaq ki, var

322
00:26:12,910 --> 00:26:22,320
ki, bir ağac bir göstərici, eləcə də sonrakı adlı süjet bir göstərici var.

323
00:26:22,320 --> 00:26:28,480
Hansı struktur kimi baxmaq bu cür edir?

324
00:26:29,870 --> 00:26:32,490
Bu cür orada artıq deyir.

325
00:26:34,640 --> 00:26:36,700
Burada artıq.

326
00:26:37,340 --> 00:26:39,170
A bağlı siyahısı.

327
00:26:39,170 --> 00:26:44,590
Biz bir süjet zaman bu sahələri bir bağlı siyahı kimi görürük.

328
00:26:44,590 --> 00:26:53,020
A meşə, sahələrinin bağlı siyahı kimi müəyyən edilir

329
00:26:53,020 --> 00:26:58,100
və belə meşə quruluşu biz yalnız bizim ilk süjet bir göstərici var olacaq ki,

330
00:26:58,100 --> 00:27:02,740
və süjet içinde bir ağac və ya daha çox ağac işarə

331
00:27:02,740 --> 00:27:06,190
və sonra və s, növbəti sahəsi göstərir.

332
00:27:06,190 --> 00:27:11,100
Meşə etmək üçün biz mkforest çağırırıq.

333
00:27:11,100 --> 00:27:14,930
Sonra biz burada olduqca faydalı funksiyaları vardır.

334
00:27:14,930 --> 00:27:23,240
Siz qaytarılması dəyəri Tree * sonra bir meşə keçir və Biz, seçin var

335
00:27:23,240 --> 00:27:25,210
bir ağac bir göstərici.

336
00:27:25,210 --> 00:27:29,370
Nə pick edəcəyik siz işarə edirik ki, meşə getmək edəcək

337
00:27:29,370 --> 00:27:35,240
o meşə aşağı tezlikli bir ağac çıxarmaq

338
00:27:35,240 --> 00:27:38,330
və o ağac sizə göstərici verir.

339
00:27:38,330 --> 00:27:43,030
Seçdiyiniz zəng sonra, ağac, artıq meşə mövcud deyil

340
00:27:43,030 --> 00:27:48,550
lakin qaytarılması dəyər ki, ağac göstəricisidir.

341
00:27:48,550 --> 00:27:50,730
Sonra bitki var.

342
00:27:50,730 --> 00:27:57,420
Bir qeyri-0 tezlik var ki, bir ağac bir pointer keçmək şərtlə ki,

343
00:27:57,420 --> 00:28:04,040
nə bitki edəcəyik ki, meşə alması ağac almaq və bitki edir ki, meşə ağac daxilində.

344
00:28:04,040 --> 00:28:06,370
Burada rmforest var.

345
00:28:06,370 --> 00:28:11,480
Əsasən bizim ağac bütün azad olan ağac, aradan qaldırılması Oxşar

346
00:28:11,480 --> 00:28:16,600
meşə aradan qaldırılması meşə olan pulsuz hər şey olacaq.

347
00:28:16,600 --> 00:28:24,890
>> Biz forest.c baxmaq varsa, orada ən azı 1 rmtree əmr görmək üçün gözləmək lazımdır

348
00:28:24,890 --> 00:28:30,090
çünki bir meşə bu ağacları var əgər meşə pulsuz yaddaş,

349
00:28:30,090 --> 00:28:32,930
sonra nəhayət, siz də o ağacları aradan qaldırılması üçün olacaq.

350
00:28:32,930 --> 00:28:41,020
Biz forest.c baxmaq varsa, biz gözləyirik kimi olan mkforest var.

351
00:28:41,020 --> 00:28:42,890
Biz malloc şeylər.

352
00:28:42,890 --> 00:28:51,740
Ilə başlamaq üçün boş, çünki Biz, NULL kimi meşə ilk süjet başlamaq

353
00:28:51,740 --> 00:29:05,940
biz ən aşağı çəki ilə ağac qaytarır olan pick, aşağı tezlikli bax

354
00:29:05,940 --> 00:29:13,560
və sonra xüsusi node xilas olur ki, ağac bal və növbəti bir,

355
00:29:13,560 --> 00:29:16,760
belə ki, meşə bağlı siyahı ki, edir.

356
00:29:16,760 --> 00:29:24,510
Və sonra biz burada olan bağlı siyahısına daxil edər bir ağac bitki var.

357
00:29:24,510 --> 00:29:29,960
Nə meşə, bu gözəl, bizim üçün sıralanır saxlayır deyil.

358
00:29:29,960 --> 00:29:37,910
Və sonra, nəhayət, biz gözlənildiyi kimi, biz orada deyilir rmtree var rmforest var.

359
00:29:46,650 --> 00:29:55,440
>> Bu günə qədər paylama kodu baxanda huffile.c, başa qədər ağır tərəfindən yəqin idi

360
00:29:55,440 --> 00:29:59,990
digər faylları halbuki özləri riayət etmək olduqca sadə idi.

361
00:29:59,990 --> 00:30:03,090
Göstəricilərinə və bağlı siyahıları və bizim bilik ilə,

362
00:30:03,090 --> 00:30:04,860
biz olduqca yaxşı əməl edə bildik.

363
00:30:04,860 --> 00:30:10,500
Amma biz həqiqətən biz tam başa əmin etmək lazım olan bütün. H faylları edir

364
00:30:10,500 --> 00:30:15,840
Siz, o geri dəyərləri ilə məşğul olan, həmin funksiyaları zəng etmək lazımdır, çünki

365
00:30:15,840 --> 00:30:20,590
belə tam həyata gedir nə hərəkət başa əmin olun

366
00:30:20,590 --> 00:30:24,290
bu funksiyaları bir zəng zaman.

367
00:30:24,290 --> 00:30:33,020
Amma həqiqətən daxilində anlaşma biz həmin çünki olduqca zəruri deyil. H faylları.

368
00:30:35,170 --> 00:30:39,490
Biz bölüşdürülməsi kodu qalan 2 daha çox fayl var.

369
00:30:39,490 --> 00:30:41,640
>> Nin dump baxaq.

370
00:30:41,640 --> 00:30:47,230
Burada comment ilə kötük bir Huffman sıkıştırılmış fayl edir

371
00:30:47,230 --> 00:30:55,580
və sonra tərcümə və zibilliklərin onun məzmunu bütün.

372
00:31:01,010 --> 00:31:04,260
Burada o hfopen zəng ki, görürük.

373
00:31:04,260 --> 00:31:10,770
Bu, * input = fopen fayl aynalama növü

374
00:31:10,770 --> 00:31:13,500
və sonra məlumat keçir.

375
00:31:13,500 --> 00:31:18,240
Əvəzinə bir Huffile keçən edirik bir file * istisna olmaqla demək olar ki, eyni deyil;

376
00:31:18,240 --> 00:31:22,030
əvəzinə fopen sizə hfopen keçən edirik.

377
00:31:22,030 --> 00:31:29,280
Burada cür biz mövzu oxumaq necə oxşar olan, ilk mövzu oxumaq

378
00:31:29,280 --> 00:31:33,580
bir bitmap fayl üçün.

379
00:31:33,580 --> 00:31:38,000
Biz burada edirik görmək yoxlanılması olub başlığı məlumat

380
00:31:38,000 --> 00:31:44,330
bir faktiki Huff fayl ki, göstərir ki, doğru sehrli sayı ehtiva edir,

381
00:31:44,330 --> 00:31:53,610
sonra əmin həmin çek bütün biz açıq bir faktiki huffed fayl və ya deyil ki, fayl ki.

382
00:31:53,610 --> 00:32:05,330
Bu nə biz görürük ki, rəmzləri bütün tezliklərdə çıxışlar edir

383
00:32:05,330 --> 00:32:09,790
qrafik masa bir terminal daxilində.

384
00:32:09,790 --> 00:32:15,240
Bu hissə faydalı olacaq.

385
00:32:15,240 --> 00:32:24,680
Bu bir az var və dəyişən bit daxil yavaş-yavaş oxuyur və sonra çap edir.

386
00:32:28,220 --> 00:32:35,430
Mən bir fayl huffing nəticəsində olan hth.bin üzrə dump zəng idi əgər

387
00:32:35,430 --> 00:32:39,490
heyəti həll istifadə edərək, mən bu almaq olardı.

388
00:32:39,490 --> 00:32:46,000
Bu simvol bütün tipi və onlar görünür hansı tezlik verilməsi oldu.

389
00:32:46,000 --> 00:32:51,180
Biz baxsaq, onların əksəriyyəti bu istisna 0s olunur: iki dəfə görünür H,

390
00:32:51,180 --> 00:32:54,820
və sonra bir dəfə görünür T.

391
00:32:54,820 --> 00:33:07,860
Və sonra biz burada 0s və 1s faktiki mesaj var.

392
00:33:07,860 --> 00:33:15,450
Biz hth.txt baxsaq, bu, güman huffed ki, orijinal mesaj

393
00:33:15,450 --> 00:33:22,490
biz bəzi Hs və Ts görmək gözləyirik.

394
00:33:22,490 --> 00:33:28,720
Xüsusilə, biz yalnız 1 T və 2 Hs görmək gözləyirik.

395
00:33:32,510 --> 00:33:37,440
Burada hth.txt var. Bu, həqiqətən HTH var.

396
00:33:37,440 --> 00:33:41,270
Biz bunu görə bilmirik, baxmayaraq ki, orada daxil bir newline karakter.

397
00:33:41,270 --> 00:33:53,190
The Huff fayl hth.bin də həmçinin newline karakter kodlama olunur.

398
00:33:55,680 --> 00:34:01,330
Burada biz, sifariş newline sonra HTH və bilirik ki, çünki

399
00:34:01,330 --> 00:34:07,340
biz yalnız bir 1 yəqin ki, H təmsil görə bilərsiniz

400
00:34:07,340 --> 00:34:17,120
və sonra T yəqin ki, 01 və sonrakı H 1 eləcə

401
00:34:17,120 --> 00:34:21,139
və sonra biz iki 0s tərəfindən göstərilən bir newline var.

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

403
00:34:26,530 --> 00:34:31,600
>> Və sonra, nəhayət, biz çox. C ilə məşğul olan və. Edirik çünki h faylları,

404
00:34:31,600 --> 00:34:36,350
biz compiler üçün olduqca kompleks bəhanə olacaq

405
00:34:36,350 --> 00:34:40,460
və belə ki, burada sizin üçün dump edir Makefile var.

406
00:34:40,460 --> 00:34:47,070
Amma faktiki olaraq, öz puff.c fayl edilməsi haqqında getmək üçün var.

407
00:34:47,070 --> 00:34:54,330
Bu Makefile həqiqətən sizin üçün puff.c edilməsi ilə məşğul deyil.

408
00:34:54,330 --> 00:34:59,310
Biz Makefile redaktə sizə qədər tərk edirik.

409
00:34:59,310 --> 00:35:05,930
Siz bütün kimi bir komanda daxil edərkən, məsələn, bu sizin üçün bütün edəcək.

410
00:35:05,930 --> 00:35:10,760
Ötən pset dən Makefile nümunələri baxmaq üçün çekinmeyin

411
00:35:10,760 --> 00:35:17,400
eləcə də sizin Puff fayl edə bilər necə bu bir gediş

412
00:35:17,400 --> 00:35:20,260
bu Makefile redaktə edir.

413
00:35:20,260 --> 00:35:22,730
Yəni bizim paylanması kodu bu barədə var.

414
00:35:22,730 --> 00:35:28,380
>> Biz vasitəsilə kazanılmış sonra, sonra burada yalnız bir öyüd-nəsihət var

415
00:35:28,380 --> 00:35:30,980
necə ki, biz Huffman qovşaqlarının ilə məşğul olmaq üçün olacaq.

416
00:35:30,980 --> 00:35:35,400
Biz artıq onlara qovşaqlarının zəng etmək fikrində deyilik, biz onlara ağac zəng etmək olacaq

417
00:35:35,400 --> 00:35:39,260
biz bir char öz rəmzi təmsil olacaq yerləşir,

418
00:35:39,260 --> 00:35:43,340
onların tezliyi, bir tam olan hadisələr sayı.

419
00:35:43,340 --> 00:35:47,370
Bir float daha dəqiq çünki Biz istifadə edirik.

420
00:35:47,370 --> 00:35:52,980
Və sonra biz sol uşaq, eləcə də sağ uşaq başqa bir göstərici yoxdur.

421
00:35:52,980 --> 00:35:59,630
A meşə, biz gördüyümüz kimi, yalnız ağac bağlı siyahısı.

422
00:35:59,630 --> 00:36:04,670
Nəhayət, biz Huff fayl yaradılmasına etdiyiniz zaman,

423
00:36:04,670 --> 00:36:07,580
biz forest yalnız 1 ağac ehtiva istəyirəm -

424
00:36:07,580 --> 00:36:12,420
1 ağac, bir çox uşaqlar ilə 1 kök.

425
00:36:12,420 --> 00:36:20,840
Əvvəllər biz yalnız bizim Huffman ağacları edirdilər zaman,

426
00:36:20,840 --> 00:36:25,360
biz ekran üzərində qovşaqlarının bütün qoymaqla başlayıb

427
00:36:25,360 --> 00:36:27,790
və biz bu qovşaqlarının var olacaq deyərək

428
00:36:27,790 --> 00:36:32,920
nəhayət yarpaqları olmaq olacaq və bu, onların simvoludur, bu onların tezliyi edir.

429
00:36:32,920 --> 00:36:42,070
Biz yalnız 3 məktub varsa, bizim meşə ki, 3 ağac bir meşə var.

430
00:36:42,070 --> 00:36:45,150
Və sonra biz ilk valideyn əlavə zaman, getmək kimi

431
00:36:45,150 --> 00:36:48,080
biz 2 ağacların meşə etdi.

432
00:36:48,080 --> 00:36:54,930
Biz meşə həmin uşaqların 2 çıxarılır və sonra bir valideyn node ilə əvəz

433
00:36:54,930 --> 00:36:58,820
uşaqlar kimi o 2 qovşaqlarının idi.

434
00:36:58,820 --> 00:37:05,600
Və sonra nəhayət, bizim son olaraq, pansiyonlar ilə məsələn edilməsi ilə addım və Cs

435
00:37:05,600 --> 00:37:08,030
son ana etmək olardı,

436
00:37:08,030 --> 00:37:13,190
və belə sonra 1-meşə ağacları bizim ümumi sayı gətirəcəyini.

437
00:37:13,190 --> 00:37:18,140
Hər kəs sizin meşə çox ağac ilə başlamaq necə görür

438
00:37:18,140 --> 00:37:22,520
və 1 ilə qədər? Okay. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Biz Puff üçün nə etmək lazımdır?

440
00:37:28,110 --> 00:37:37,110
Biz nə etmək lazımdır kimi həmişə, onlar bizə giriş hüququ növü vermək təmin edilir

441
00:37:37,110 --> 00:37:39,090
biz, həqiqətən, bu proqram çalıştırabilirsiniz ki.

442
00:37:39,090 --> 00:37:43,130
Bu halda onlar ilk komanda-line arqument sonra bizə verilməsi üçün olacaq

443
00:37:43,130 --> 00:37:53,440
2: biz decompress və decompressed faylı çıxış istədiyiniz faylı.

444
00:37:53,440 --> 00:38:00,410
Amma bir dəfə biz, onlar dəyərlər hüququ məbləği bizə keçir əmin olun

445
00:38:00,410 --> 00:38:05,820
biz daxil Huff fayl və ya deyil ki, təmin etmək istəyirik.

446
00:38:05,820 --> 00:38:10,420
Və sonra bir dəfə biz, sonra biz ağac qurmaq istəyirik, bu Huff fayl ki, zəmanət

447
00:38:10,420 --> 00:38:20,940
bu mesajı şəxs inşa ağac oyunları belə ağac qurmaq.

448
00:38:20,940 --> 00:38:25,840
Biz ağac qurmaq sonra, biz ilə 0s və onlar keçdi 1s, məşğul ola bilər

449
00:38:25,840 --> 00:38:29,590
bu eyni, çünki, bizim ağac yanaşı bu əməl

450
00:38:29,590 --> 00:38:33,510
və sonra, mesaj yazmaq chars geri bit şərh.

451
00:38:33,510 --> 00:38:35,880
Və sonra sonunda biz burada göstəricilər ilə məşğul olduğunuz çünki

452
00:38:35,880 --> 00:38:38,110
Biz hər hansı bir yaddaş sızıntıları yoxdur əmin etmək istəyirəm

453
00:38:38,110 --> 00:38:41,330
və biz pulsuz hər şey.

454
00:38:42,820 --> 00:38:46,430
>> Düzgün istifadə edilməsi artıq bizim üçün köhnə hat edir.

455
00:38:46,430 --> 00:38:51,980
Biz daxil etmək, hansı kabartmak üçün fayl adı olacaq,

456
00:38:51,980 --> 00:38:56,010
və sonra bir çıxış müəyyən

457
00:38:56,010 --> 00:39:01,580
belə mətn faylı olacaq puffed çıxış üçün fayl adı.

458
00:39:03,680 --> 00:39:08,820
Bu istifadə edir. İndi biz daxil huffed və ya deyil ki, təmin etmək istəyirik.

459
00:39:08,820 --> 00:39:16,420
Geri düşüncələri, bizə kömək edə bilər ki, distribution kodu orada bir şey idi

460
00:39:16,420 --> 00:39:21,570
bir fayl huffed və ya olub-olmadığını anlama ilə?

461
00:39:21,570 --> 00:39:26,910
Bu Huffeader haqqında huffile.c məlumat var idi.

462
00:39:26,910 --> 00:39:33,430
Biz hər Huff fayl sehrli sayı ilə bağlı Huffeader var bilirik ki,

463
00:39:33,430 --> 00:39:37,240
hər rəmzi üçün tezliklərin eləcə də bir sıra

464
00:39:37,240 --> 00:39:39,570
həmçinin bir checksum kimi.

465
00:39:39,570 --> 00:39:43,180
Biz bilirik ki, ancaq biz də dump.c bir peek etdi

466
00:39:43,180 --> 00:39:49,120
olan bir Huff fayla oxuyurdum.

467
00:39:49,120 --> 00:39:53,990
Və bunu, o, həqiqətən huffed və ya olub-olmadığını yoxlamaq idi.

468
00:39:53,990 --> 00:40:03,380
Belə ki, bəlkə biz puff.c. üçün struktur kimi dump.c istifadə edə bilər

469
00:40:03,380 --> 00:40:12,680
Geri pset 4 biz RGB üç dəfə replikasiya ki fayl copy.c zaman

470
00:40:12,680 --> 00:40:14,860
və biz Whodunit və RSS üçün şərh

471
00:40:14,860 --> 00:40:20,390
eyni, nə edə yalnız cp dump.c puff.c kimi komanda çalışır

472
00:40:20,390 --> 00:40:23,600
və kodu bəzi istifadə edin.

473
00:40:23,600 --> 00:40:28,210
Lakin, bir müddət kimi sadə olacaq deyil

474
00:40:28,210 --> 00:40:33,010
puff.c daxil dump.c çevrilməsində,

475
00:40:33,010 --> 00:40:36,160
lakin ən azı başlamaq üçün haradasa verir

476
00:40:36,160 --> 00:40:40,540
giriş həqiqətən huffed və ya təmin etmək üçün necə

477
00:40:40,540 --> 00:40:43,240
həmçinin bir neçə digər şeylər kimi.

478
00:40:45,930 --> 00:40:50,250
Biz düzgün istifadə təmin giriş huffed ki, təmin etmişdir.

479
00:40:50,250 --> 00:40:53,570
Biz müvafiq səhv yoxlanılması etmişik etdik ki, hər zaman,

480
00:40:53,570 --> 00:41:01,520
belə bir problem varsa, geri və bir uğursuzluq baş əgər funksiyası çıxdıqda.

481
00:41:01,520 --> 00:41:07,170
>> İndi biz nə etmək istəyirəm faktiki ağac qurmaq deyil.

482
00:41:08,840 --> 00:41:12,640
Biz Meşə baxsanız, 2 əsas funksiyaları var

483
00:41:12,640 --> 00:41:15,800
biz çox tanış olmaq istədiyiniz olacaq ki,.

484
00:41:15,800 --> 00:41:23,870
Orada Boolean funksiyası bitki ki, bizim meşə daxilində qeyri-0 tezlik ağac bitkiləri.

485
00:41:23,870 --> 00:41:29,250
Və orada bir meşə və ağac bir göstərici bir pointer ilə keçir.

486
00:41:32,530 --> 00:41:40,340
Sadə sual: Bir Huffman ağac tikinti etdiyiniz zaman neçə meşə siz olacaq?

487
00:41:44,210 --> 00:41:46,650
Bizim meşə hüququ, bizim kətan kimi?

488
00:41:46,650 --> 00:41:50,800
Beləliklə, biz yalnız 1 meşə var olacaq, lakin biz çox ağac var olacaq.

489
00:41:50,800 --> 00:41:57,590
Siz bitki zəng Belə əvvəl ehtimalla sizin meşə etmək istəyirəm olacaq.

490
00:41:57,590 --> 00:42:04,430
Bir meşə edə bilər necə forest.h baxmaq əgər bir komanda üçün var.

491
00:42:04,430 --> 00:42:09,270
Siz bir ağac əkmək bilər. Biz bunu bilirik.

492
00:42:09,270 --> 00:42:11,590
Və sonra da, meşə bir ağac ala bilərsiniz

493
00:42:11,590 --> 00:42:17,540
aşağı çəki ilə bir ağac aradan qaldırılması və sizə göstərici verilməsi.

494
00:42:17,540 --> 00:42:23,090
Biz nümunələri özümüz bunu zaman geri düşüncələri,

495
00:42:23,090 --> 00:42:27,980
biz onu rəsm zaman biz sadəcə yalnız links əlavə edib.

496
00:42:27,980 --> 00:42:31,680
Amma burada əvəzinə yalnız links əlavə

497
00:42:31,680 --> 00:42:40,630
bu qovşaqlarının 2 aradan qaldırılması və sonra başqa bir ilə əvəz etdiyiniz kimi daha düşünün.

498
00:42:40,630 --> 00:42:44,200
Seçmək və əkin baxımından ifadə etmək üçün,

499
00:42:44,200 --> 00:42:48,840
2 ağacları picking və sonra başqa bir ağac əkilməsi edirik

500
00:42:48,840 --> 00:42:54,060
ki, siz uşaqlar kimi seçilmiş olan 2 ağacları var.

501
00:42:57,950 --> 00:43:05,280
Huffman nin ağac qurmaq üçün, üçün simvollar və tezliklərdə oxuya bilərsiniz

502
00:43:05,280 --> 00:43:10,790
bu Huffeader sizə verir, çünki

503
00:43:10,790 --> 00:43:14,250
Siz tezliklərin bir sıra verir.

504
00:43:14,250 --> 00:43:19,660
Beləliklə, siz davam edə bilər və yalnız bu 0 şey ignore

505
00:43:19,660 --> 00:43:23,760
biz bu ilin sonunda 256 yarpaqları istəmirəm çünki.

506
00:43:23,760 --> 00:43:27,960
Biz yalnız simvol ki, yarpaqları sayı istəyirəm

507
00:43:27,960 --> 00:43:31,600
əslində fayl istifadə olunur.

508
00:43:31,600 --> 00:43:37,590
Siz bu işarələri oxumaq və qeyri-0 tezliklərin ki, bu simvol hər bilər

509
00:43:37,590 --> 00:43:40,440
o ağac olacaq.

510
00:43:40,440 --> 00:43:45,990
Nə olar, bir qeyri-0 tezlik simvolu oxumaq hər zaman

511
00:43:45,990 --> 00:43:50,660
siz meşə ki, ağac əkmək bilər.

512
00:43:50,660 --> 00:43:56,620
Siz meşə ağacları əkmək sonra, bacı kimi bu ağac qoşulmaq olar

513
00:43:56,620 --> 00:44:01,130
Belə ki, əkin və seçin yerləşir aldığınız 2 və sonra bitki 1 geri gedir

514
00:44:01,130 --> 00:44:05,820
1-ki, bitki siz seçilmiş ki, 2 uşaq valideyn edir.

515
00:44:05,820 --> 00:44:11,160
Belə ki, sonra son nəticə sizin meşə bir ağac olacaq.

516
00:44:16,180 --> 00:44:18,170
Bu sizin ağac qurmaq nasıl.

517
00:44:18,170 --> 00:44:21,850
>> Burada yanlış getmək bilər ki, bir neçə şey var

518
00:44:21,850 --> 00:44:26,580
çünki biz yeni ağac edilməsi və bu kimi göstəricilər və hər şeyi ilə məşğul ilə məşğul olursunuz.

519
00:44:26,580 --> 00:44:30,450
Biz göstəricilər ilə məşğul olan zaman əvvəl,

520
00:44:30,450 --> 00:44:36,580
biz malloc'd zaman biz bunu bizə NULL pointer dəyər qaytarmayıb əmin etmək istəyirdi.

521
00:44:36,580 --> 00:44:42,770
Beləliklə, bu prosesi çərçivəsində bir neçə addımlar bir neçə hallarda olmalıdır gedir

522
00:44:42,770 --> 00:44:45,920
Ü proqram uğursuz ola bilər.

523
00:44:45,920 --> 00:44:51,310
Nə istəyirəm, siz bu səhvlər idarə əmin etmək istəyirəm ki,

524
00:44:51,310 --> 00:44:54,580
və spec bu, qəşəng onları idarə etmək üçün deyir

525
00:44:54,580 --> 00:45:00,280
belə proqram çıxmaq var niyə izah istifadəçi bir mesaj çap istəyirəm

526
00:45:00,280 --> 00:45:03,050
və sonra dərhal bu çıxın.

527
00:45:03,050 --> 00:45:09,490
Bu səhv rəftar etmək, onu yoxlamaq istəyirəm ki, xatırlayıram

528
00:45:09,490 --> 00:45:12,160
uğursuz ola bilər ki, hər bir zaman.

529
00:45:12,160 --> 00:45:14,660
Yeni bir pointer edirik ki, hər bir zaman

530
00:45:14,660 --> 00:45:17,040
Əgər uğurlu və əmin etmək istəyirəm.

531
00:45:17,040 --> 00:45:20,320
Yeni bir pointer və malloc onu nə üçün istifadə nə əvvəl,

532
00:45:20,320 --> 00:45:22,380
və sonra biz bu göstərici NULL olub yoxlamaq olardı.

533
00:45:22,380 --> 00:45:25,670
Belə ki, bunu yalnız bilər, bəzi hallarda olmalıdır gedir

534
00:45:25,670 --> 00:45:28,610
amma bəzən həqiqətən bir funksiyası zəng etdiyiniz

535
00:45:28,610 --> 00:45:33,100
və funksiyası ərzində ki, mallocing məşğul olan biri.

536
00:45:33,100 --> 00:45:39,110
Bu halda, biz kodu çərçivəsində funksiyaları bəzi geri baxmaq əgər,

537
00:45:39,110 --> 00:45:42,260
bəziləri Boolean funksiyaları.

538
00:45:42,260 --> 00:45:48,480
Abstrakt halda biz foo adlı Boolean funksiyası varsa,

539
00:45:48,480 --> 00:45:54,580
əsasən, biz foo nə olursa olsun bunu əlavə güman edə bilər

540
00:45:54,580 --> 00:45:57,210
bir Boolean funksiyası olduğundan, bu, doğru və ya yalan qaytarır -

541
00:45:57,210 --> 00:46:01,300
əgər doğru uğurlu, yalan əgər.

542
00:46:01,300 --> 00:46:06,270
Beləliklə, biz foo qaytarılması dəyəri doğru və ya yalan olub-olmadığını yoxlamaq istəyirlər.

543
00:46:06,270 --> 00:46:10,400
O yalan varsa, biz mesajı bir növ çap etmək istəyirəm olacaq o deməkdir ki,

544
00:46:10,400 --> 00:46:14,390
və sonra proqram çıxın.

545
00:46:14,390 --> 00:46:18,530
Biz nə istəyirik foo qaytarılması dəyəri kontrol edir.

546
00:46:18,530 --> 00:46:23,310
Foo yalan qaytarır, onda biz səhv bir növ rast bilirik ki,

547
00:46:23,310 --> 00:46:25,110
və biz proqram çıxmaq lazımdır.

548
00:46:25,110 --> 00:46:35,600
Bunun yolu faktiki funksiyası özü üçün şərt olduğu bir vəziyyət var.

549
00:46:35,600 --> 00:46:39,320
Foo x götürür söyləyin.

550
00:46:39,320 --> 00:46:43,390
Biz əgər bir şərt kimi ola bilər (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Foo icra sonunda doğru qayıtdıqda əgər əsasən, o deməkdir ki,

552
00:46:50,900 --> 00:46:57,390
funksiyası foo qiymətləndirmək, çünki biz bunu edə bilərsiniz

553
00:46:57,390 --> 00:47:00,500
bütün şəraiti qiymətləndirmək üçün.

554
00:47:00,500 --> 00:47:06,500
Belə ki, o funksiyası doğru qayıdır və uğurlu Əgər bir şey edə bilərsiniz.

555
00:47:06,500 --> 00:47:11,800
Amma səhv yoxlanılması olduğunuzda, siz yalnız funksiyası yalan qaytarır əgər çıxmaq istəyirəm.

556
00:47:11,800 --> 00:47:16,090
Nə edə bilərdi yalnız əlavə edilir == saxta və ya yalnız qarşısında bang əlavə

557
00:47:16,090 --> 00:47:21,010
sonra (! foo) əgər var.

558
00:47:21,010 --> 00:47:29,540
Bu şərtlə ki, ki, bədən daxilində siz səhv rəftar bütün olardı

559
00:47:29,540 --> 00:47:36,940
belə "Bu ağac yaratmaq bilmədi" kimi və sonra 1 və ya bu kimi bir şey geri.

560
00:47:36,940 --> 00:47:43,340
Ki, nə olsa da, foo yalan geri baxmayaraq ki, -

561
00:47:43,340 --> 00:47:46,980
Foo doğru qaytarır söyləyin.

562
00:47:46,980 --> 00:47:51,060
Sonra yenidən foo zəng etmək yoxdur. Bu ümumi misconception var.

563
00:47:51,060 --> 00:47:54,730
Sizin vəziyyətdə idi, çünki artıq qiymətləndirilir ki,

564
00:47:54,730 --> 00:47:59,430
siz ağac və ya kimi bir şey etmək kullanıyorsanız siz artıq nəticə var

565
00:47:59,430 --> 00:48:01,840
və ya bitki və ya seçin və ya bir şey.

566
00:48:01,840 --> 00:48:07,460
Bu artıq dəyər var. Artıq icra edir.

567
00:48:07,460 --> 00:48:10,730
Belə ki, vəziyyət Boolean funksiyaları istifadə etmək faydalıdır

568
00:48:10,730 --> 00:48:13,890
çünki və ya, həqiqətən, loop orqanı həyata deyil,

569
00:48:13,890 --> 00:48:18,030
hər halda funksiyasını icra edir.

570
00:48:22,070 --> 00:48:27,330
>> Son addım Bizim ikinci fayl mesaj yazır.

571
00:48:27,330 --> 00:48:33,070
Sonra biz Huffman ağac tikmək, sonra fayl mesaj yazılı olduqca sadə deyil.

572
00:48:33,070 --> 00:48:39,260
Bu, yalnız 0s və 1s riayət indi olduqca sadə var.

573
00:48:39,260 --> 00:48:45,480
Və qaydaları ilə biz bir Huffman ağac ildə 0s tərk göstərir bilirik ki,

574
00:48:45,480 --> 00:48:48,360
və 1s sağ göstərir.

575
00:48:48,360 --> 00:48:53,540
Bir 0 almaq ki, yavaş-yavaş oxumaq Beləliklə, əgər hər dəfə

576
00:48:53,540 --> 00:48:59,100
Əgər 1-ci oxumaq hər zaman sonra sol qolu edin və lazımdır

577
00:48:59,100 --> 00:49:02,100
sağ filialı izləmək olacaq.

578
00:49:02,100 --> 00:49:07,570
Bir yarpaq hit qədər və sonra davam etmək olacaq

579
00:49:07,570 --> 00:49:11,550
yarpaqları filiallarının sonunda olacaq, çünki.

580
00:49:11,550 --> 00:49:16,870
Biz bir yarpaq və ya təşkil etdik olub necə deyə bilərsiniz?

581
00:49:19,800 --> 00:49:21,690
Biz əvvəl bildirib.

582
00:49:21,690 --> 00:49:24,040
[Tələbə] Bu göstəricilər NULL edin. >> Bəli.

583
00:49:24,040 --> 00:49:32,220
Sol və sağ, həm də ağaclar üçün göstəricilərinə NULL, əgər biz bir yarpaq təşkil etdik, biz deyə bilərik.

584
00:49:32,220 --> 00:49:34,110
Mükəmməldir.

585
00:49:34,110 --> 00:49:40,320
Biz Huff fayla yavaş-yavaş oxumaq istəyirəm ki, bilirik.

586
00:49:43,870 --> 00:49:51,220
Biz dump.c əvvəl gördüm ki, onlar nə onlar Huff fayla yavaş-yavaş oxumaq deyil

587
00:49:51,220 --> 00:49:54,560
və yalnız bit nə çap.

588
00:49:54,560 --> 00:49:58,430
Biz bunu etmək fikrində deyilik. Biz bir az daha kompleks olduğunu bir şey bunu etmək olacaq.

589
00:49:58,430 --> 00:50:03,620
Amma nə biz nə edə bilər, biz bit üçün deyilir ki kodu ki, bit almaq olar.

590
00:50:03,620 --> 00:50:10,250
Burada biz istəyirik ki, cari bit təmsil tam bit var.

591
00:50:10,250 --> 00:50:15,520
Dosyayı sonunda hit qədər Bu faylı bit bütün iterating qayğısına qalır.

592
00:50:15,520 --> 00:50:21,270
Ki, əsasən, sonra iterator bir növ istəyirəm olacaq

593
00:50:21,270 --> 00:50:26,760
Sizin ağac axır etmək.

594
00:50:26,760 --> 00:50:31,460
Və sonra bit 0 və ya 1 olub əsaslanır

595
00:50:31,460 --> 00:50:36,920
ya sol ki iterator hərəkət və ya sağa hərəkət etmək istəyirəm olacaq

596
00:50:36,920 --> 00:50:44,080
bütün yolu bir yarpaq hit qədər, belə ki, bütün yol etdiyiniz ki node qədər

597
00:50:44,080 --> 00:50:48,260
daha çox qovşaqlarının qeyd deyil.

598
00:50:48,260 --> 00:50:54,300
Niyə biz bir Huffman fayl deyil Morze əlifbası ilə bunu edə bilərsiniz?

599
00:50:54,300 --> 00:50:56,610
Morse kodu qeyri bir az var idi.

600
00:50:56,610 --> 00:51:04,440
Biz gözləyin oh kimi ola bilər ki, yol boyunca bir məktub edib sonra, belə bəlkə bu, bizim məktub

601
00:51:04,440 --> 00:51:08,150
biz yalnız bir az artıq davam edərsə, onda biz başqa məktub hit olardı halbuki.

602
00:51:08,150 --> 00:51:13,110
Amma ki, Huffman encoding baş gedən deyil

603
00:51:13,110 --> 00:51:17,540
biz olacaq ki, yalnız yol xarakteri edib ki, arxayın ola bilərsiniz

604
00:51:17,540 --> 00:51:23,480
ki node sol və sağ uşaqlar NULL əgər edir.

605
00:51:28,280 --> 00:51:32,350
>> Nəhayət, biz yaddaş bütün azad etmək istəyirik.

606
00:51:32,350 --> 00:51:37,420
Biz məşğul olduğunuz hər iki yaxın Huff fayl istəyirəm

607
00:51:37,420 --> 00:51:41,940
habelə meşə ağacları bütün çıxarın.

608
00:51:41,940 --> 00:51:46,470
Sizin həyata əsaslanır, yəqin ki, meşə aradan səslənmək istəyirəm olacaq

609
00:51:46,470 --> 00:51:49,780
əvəzinə faktiki ağac özünüzü bütün keçir.

610
00:51:49,780 --> 00:51:53,430
Əgər hər hansı bir müvəqqəti ağacları edilən Lakin, bu azad lazımdır.

611
00:51:53,430 --> 00:51:59,060
Siz yaxşı bilirsiniz kodu, belə yaddaş ayrılması olduğunuz bilirsiniz.

612
00:51:59,060 --> 00:52:04,330
Və siz getmək əgər, malloc üçün F'ing hətta Control ilə başlamaq

613
00:52:04,330 --> 00:52:08,330
görən zaman malloc və ki, bütün azad əmin edilməsi

614
00:52:08,330 --> 00:52:10,190
lakin sonra yalnız, kodu keçir

615
00:52:10,190 --> 00:52:14,260
yaddaş ayrılmış ola bilər Ü anlama.

616
00:52:14,260 --> 00:52:21,340
Adətən yalnız "bir fayl sonunda mən yalnız mənim meşə meşə aradan qaldırılması üçün gedirəm" deyə bilər

617
00:52:21,340 --> 00:52:23,850
belə əsasən pulsuz ki, yaddaş sil ki,

618
00:52:23,850 --> 00:52:28,310
"Və sonra da faylı bağlamaq və sonra mənim proqram çıxmaq niyyətindədir gedirəm."

619
00:52:28,310 --> 00:52:33,810
Lakin proqram fit ki, yalnız vaxt?

620
00:52:33,810 --> 00:52:37,880
Xeyr, çünki bəzən baş verən bir səhv var bilər.

621
00:52:37,880 --> 00:52:42,080
Bəlkə bir fayl açmaq bilməz və ya başqa bir ağac gələ bilmədi

622
00:52:42,080 --> 00:52:49,340
və ya səhv bir növ yaddaş ayrılması prosesi baş və buna NULL döndü.

623
00:52:49,340 --> 00:52:56,710
Bir səhv baş, sonra geri və çıxın.

624
00:52:56,710 --> 00:53:02,040
Beləliklə, sizin proqram hər hansı bir zamanda tərk edə bilər ki, əmin etmək istəyirəm

625
00:53:02,040 --> 00:53:06,980
siz yaddaş bütün azad etmək istəyirik.

626
00:53:06,980 --> 00:53:13,370
Bu yalnız sizin kodu çıxmaq əsas funksiyası çox sonunda olacaq deyil.

627
00:53:13,370 --> 00:53:20,780
Siz kodu potensial vaxtından əvvəl geri ola bilər ki, hər bir instansiya geri baxmaq istəyirəm

628
00:53:20,780 --> 00:53:25,070
və sonra azad nə yaddaş hissi verir.

629
00:53:25,070 --> 00:53:30,830
Siz meşə etmək və saxta geri çağırmışdı edirlər.

630
00:53:30,830 --> 00:53:34,230
Sonra yəqin ki, meşə aradan qaldırılması lazım deyil

631
00:53:34,230 --> 00:53:37,080
Henüz bir meşə yoxdur çünki.

632
00:53:37,080 --> 00:53:42,130
Amma kodu hər nöqtəsində sizi vaxtından əvvəl geri bilər Ü

633
00:53:42,130 --> 00:53:46,160
Əgər hər hansı yaddaş azad əmin etmək istəyirəm.

634
00:53:46,160 --> 00:53:50,020
>> Beləliklə, biz yaddaş azad ilə məşğul olan və potensial itkilərin qarşılaşdıqda zaman,

635
00:53:50,020 --> 00:53:55,440
biz qərar və məntiq istifadə yalnız mənə

636
00:53:55,440 --> 00:54:01,850
həm də düzgün və ya bizim yaddaş bütün azad belirlemek üçün Valgrind istifadə edin.

637
00:54:01,850 --> 00:54:09,460
Siz ya Puff haqqında Valgrind çalıştırabilirsiniz və sonra siz də onu keçmək üçün

638
00:54:09,460 --> 00:54:14,020
komanda-line dəlilləri hüququnu sayı Valgrind üçün.

639
00:54:14,020 --> 00:54:18,100
Siz çalıştırabilirsiniz, ancaq çıxış bir az sirli edir.

640
00:54:18,100 --> 00:54:21,630
Biz Speller ilə istifadə bir az kazanılmış sonra, lakin biz hələ bir az daha kömək lazımdır

641
00:54:21,630 --> 00:54:26,450
belə, sonra qaçaq kontrol = tam kimi bir neçə bayraqları ilə çalışan

642
00:54:26,450 --> 00:54:32,040
ki, yəqin ki, bizə Valgrind bir çox faydalı çıxış edəcək.

643
00:54:32,040 --> 00:54:39,040
>> Sonra ayıklama etdiyiniz zaman digər faydalı tip fərq əmr edir.

644
00:54:39,040 --> 00:54:48,520
Siz Huff heyəti icrası daxil run bir metin fayl, bilər

645
00:54:48,520 --> 00:54:55,400
və sonra xüsusi olmaq, ikili fayl, ikili Huff fayl üçün çıxış.

646
00:54:55,400 --> 00:54:59,440
Sonra ki, ikili fayl öz yastıq run, əgər

647
00:54:59,440 --> 00:55:03,950
sonra ideal, sizin outputted mətn faylı eyni olacaq

648
00:55:03,950 --> 00:55:08,200
Daxil keçdi orijinal bir

649
00:55:08,200 --> 00:55:15,150
Burada nümunə kimi hth.txt kullanıyorum və sizin spec haqqında danışdı biri.

650
00:55:15,150 --> 00:55:21,040
Bu sözün yalnız HTH sonra newline var.

651
00:55:21,040 --> 00:55:30,970
Amma mütləq çekinmeyin və siz mütləq artıq nümunələr istifadə etmək tövsiyə olunur

652
00:55:30,970 --> 00:55:32,620
mətn faylı üçün.

653
00:55:32,620 --> 00:55:38,110
>> Siz hətta decompressing sonra bəlkə kompressor bir shot almaq olar

654
00:55:38,110 --> 00:55:41,600
Müharibə və Sülh kimi Speller istifadə olunan faylları bəzi

655
00:55:41,600 --> 00:55:46,710
və ya Jane Austen və ya kimi bir şey - sərin cür ki, - və ya Austin Powers,

656
00:55:46,710 --> 00:55:51,880
biz bu böyük faylları ilə məşğul cür enmək deyil, çünki

657
00:55:51,880 --> 00:55:55,590
Burada növbəti aracı, ls-l istifadə edin.

658
00:55:55,590 --> 00:56:01,150
Biz əsasən cari kataloq bütün məzmunu listeler ls, istifadə edirik.

659
00:56:01,150 --> 00:56:07,860
Bayraq-l keçən həqiqətən bu faylların ölçüsünü göstərir.

660
00:56:07,860 --> 00:56:12,690
Siz pset spec keçir, bu, həqiqətən, ikili fayl yaratmaq vasitəsilə dolaşır

661
00:56:12,690 --> 00:56:16,590
onu huffing və siz çox kiçik faylları görmək

662
00:56:16,590 --> 00:56:23,910
bu kompressor və məlumat bütün tərcümə yer dəyəri

663
00:56:23,910 --> 00:56:26,980
kimi bütün tezliklərdə və şeyi faktiki fayda üstələyir

664
00:56:26,980 --> 00:56:30,000
ilk növbədə fayl sıxılma edir.

665
00:56:30,000 --> 00:56:37,450
Bir uzun mətn faylları run əgər Lakin, sonra sizə bir xeyir əldə etmək başlamaq ki, görə bilərsiniz

666
00:56:37,450 --> 00:56:40,930
bu faylları kompressor edir.

667
00:56:40,930 --> 00:56:46,210
>> Və sonra, nəhayət, biz mütləq çox lazımlı gələcək olan bizim köhnə dost gdb var.

668
00:56:48,360 --> 00:56:55,320
>> Biz ağaclar edilməsi bəlkə Huff ağac və ya prosesin hər hansı bir sual yoxdur

669
00:56:55,320 --> 00:56:58,590
və ya Huff'n Puff hər hansı digər suallar?

670
00:57:00,680 --> 00:57:02,570
Okay. Mən bir az ətrafında qalmaq lazımdır.

671
00:57:02,570 --> 00:57:06,570
>> Thanks, everyone. Bu gözden geçirmek 6 idi. Və uğurlar yaxşı.

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