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

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

3
00:00:04,810 --> 00:00:07,240
[Kjo është CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Hello, të gjithë, dhe të mirëpritur të walkthrough 6: pudre Huff'n.

5
00:00:12,180 --> 00:00:17,440
Në Puff Huff'n ajo që ne po bëjmë do të jetë që kanë të bëjnë me një file kompresuar Huffman

6
00:00:17,440 --> 00:00:20,740
dhe pastaj puffing atë back up, kështu që decompressing atë,

7
00:00:20,740 --> 00:00:25,810
kështu që ne mund të përkthehet nga 0s dhe 1s që përdoruesi na dërgon

8
00:00:25,810 --> 00:00:30,660
dhe kthyer atë përsëri në tekstin origjinal.

9
00:00:30,660 --> 00:00:34,360
Pset 6 do të jetë shumë i ftohtë, sepse ju do të jeni për të parë disa nga mjetet

10
00:00:34,360 --> 00:00:41,730
që ju të përdorur në pset 4 dhe 5 pset dhe lloji i kombinuar ato në 1 koncept mjaft i zoti

11
00:00:41,730 --> 00:00:43,830
kur ju vijnë për të menduar për këtë.

12
00:00:43,830 --> 00:00:50,110
>> Gjithashtu, ndoshta, pset 4 dhe 5 ishin më psets sfiduese që kemi pasur për të ofruar.

13
00:00:50,110 --> 00:00:53,950
Pra, nga tani, ne kemi këtë pset 1 më shumë në C,

14
00:00:53,950 --> 00:00:56,480
dhe pastaj, pasi që ne jemi në të programimit web.

15
00:00:56,480 --> 00:01:02,310
Pra, përgëzoj veten për marrjen mbi kodrinë vështira në CS50.

16
00:01:03,630 --> 00:01:09,760
>> Lëvizur më për Puff Huff'n, veglave tona për këtë pset do të jenë pemët Huffman,

17
00:01:09,760 --> 00:01:14,700
kështu kuptuar jo vetëm si punë pemë binare, por edhe konkretisht pemë Huffman,

18
00:01:14,700 --> 00:01:16,240
se si ata janë ndërtuar.

19
00:01:16,240 --> 00:01:20,210
Dhe pastaj ne do të kemi një shumë të kodit të shpërndarjes në këtë pset,

20
00:01:20,210 --> 00:01:22,480
dhe ne do të vijnë për të parë se në fakt disa prej kodit

21
00:01:22,480 --> 00:01:24,670
ne nuk mund të jetë në gjendje për të kuptuar plotësisht ende,

22
00:01:24,670 --> 00:01:30,080
dhe kështu ata do të jenë. fotografi c, por pastaj shoqëruese të tyre. fotografi h

23
00:01:30,080 --> 00:01:34,300
do të na japë të mjaftueshme kuptim që ne kemi nevojë në mënyrë që ne e dimë se si ato funksione punojnë

24
00:01:34,300 --> 00:01:38,100
ose të paktën atë që ata janë të dashur për të bërë - inputet dhe rezultatet e tyre -

25
00:01:38,100 --> 00:01:40,760
edhe në qoftë se ne nuk e dimë se çfarë po ndodh në kutinë e zezë

26
00:01:40,760 --> 00:01:44,090
ose nuk e kuptojnë se çfarë po ndodh në kutinë e zezë brenda.

27
00:01:44,090 --> 00:01:49,400
Dhe pastaj në fund, si zakonisht, kemi të bëjmë me strukturat e të dhënave të reja,

28
00:01:49,400 --> 00:01:51,840
lloje të veçanta të nyjave që tregojnë për gjëra të caktuara,

29
00:01:51,840 --> 00:01:56,080
dhe kështu që këtu ka një stilolaps dhe letër, jo vetëm për procesin e projektimit

30
00:01:56,080 --> 00:01:58,470
dhe kur ju jeni duke u përpjekur të kuptoj se si pset juaj duhet të punojnë

31
00:01:58,470 --> 00:02:00,520
por edhe gjatë debugging.

32
00:02:00,520 --> 00:02:06,140
Ju mund të keni gdb së bashku me stilolaps dhe letër tuaj, ndërsa ju të merrni poshtë atë që vlerat janë,

33
00:02:06,140 --> 00:02:09,320
ku shigjetat tuaja janë treguar, dhe gjëra të tilla si se.

34
00:02:09,320 --> 00:02:13,720
>> Së pari le të shohim në pemë Huffman.

35
00:02:13,720 --> 00:02:19,600
Pemë pemë binare janë Huffman, do të thotë që çdo nyje ka vetëm 2 fëmijë.

36
00:02:19,600 --> 00:02:24,870
Në pemë Huffman karakteristikë është se vlerat më të shpeshta

37
00:02:24,870 --> 00:02:27,140
janë të përfaqësuara nga BITS fewest.

38
00:02:27,140 --> 00:02:32,690
Ne pamë në shembujt e ligjërimit kodin Morse, cili lloj i konsoliduar disa letra.

39
00:02:32,690 --> 00:02:38,030
Nëse ju jeni duke u përpjekur për të përkthyer një A ose nje E, për shembull,

40
00:02:38,030 --> 00:02:43,940
ju jeni përkthimin që shpesh, kështu që në vend që të përdorin seri të plotë të bit

41
00:02:43,940 --> 00:02:48,640
ndarë për atë lloj usual të dhënave, ju ngjesh atë poshtë për pak,

42
00:02:48,640 --> 00:02:53,730
dhe pastaj ato letra që janë të përfaqësuara më pak shpesh janë të përfaqësuara me copa të gjata

43
00:02:53,730 --> 00:02:59,840
sepse ju mund të përballojë se kur ju peshojnë nga frekuencat që ato letra shfaqen.

44
00:02:59,840 --> 00:03:03,020
Ne kemi të njëjtën ide këtu në pemë Huffman

45
00:03:03,020 --> 00:03:12,360
ku ne jemi duke bërë një zinxhir, një lloj rrugën për të shkuar në karaktere të caktuara.

46
00:03:12,360 --> 00:03:14,470
Dhe pastaj karaktere që kanë frekuencën më

47
00:03:14,470 --> 00:03:17,940
do të përfaqësohet me bit fewest.

48
00:03:17,940 --> 00:03:22,020
>> Mënyrë që ju të ndërtuar një pemë Huffman

49
00:03:22,020 --> 00:03:27,430
është duke vendosur të gjitha karakteret që shfaqen në tekst

50
00:03:27,430 --> 00:03:30,630
dhe llogaritjen frekuencën e tyre, sa shpesh ato shfaqen.

51
00:03:30,630 --> 00:03:33,880
Kjo mund të jetë ose një akuzë e sa herë ato letra shfaqet

52
00:03:33,880 --> 00:03:40,270
ose ndoshta një përqindje e nga të gjitha personazhet se sa secili prej tyre duket.

53
00:03:40,270 --> 00:03:44,270
Dhe kështu ajo që ju bëni është një herë ju keni të gjithë se nga planifikuara,

54
00:03:44,270 --> 00:03:49,060
atëherë ju shikoni për 2 frekuenca më të ulëta dhe më pas të bashkohen ato si vëllezërit e motrat

55
00:03:49,060 --> 00:03:55,660
ku pastaj nyjen prind ka një frekuencë që është shuma e 2 fëmijëve të saj.

56
00:03:55,660 --> 00:04:00,870
Dhe pastaj ju nga Konventa thonë se nyja majtë,

57
00:04:00,870 --> 00:04:03,770
ju do të ndiqni se duke ndjekur degën 0,

58
00:04:03,770 --> 00:04:08,140
dhe pastaj nyjen rightmost është 1 degë.

59
00:04:08,140 --> 00:04:16,040
Siç e pamë në kodin Morse, një Gotcha ishte se në qoftë se keni pasur vetëm një bip bip dhe

60
00:04:16,040 --> 00:04:18,120
ai ishte i paqartë.

61
00:04:18,120 --> 00:04:22,430
Ajo mund të jetë ose 1 shkronja ose ajo mund të jetë një sekuencë prej 2 shkronja.

62
00:04:22,430 --> 00:04:27,790
Dhe kështu ajo Huffman pemë bën është sepse nga natyra e personazheve

63
00:04:27,790 --> 00:04:34,140
ose përfundimtare tona karaktere aktuale duke qenë nyje e fundit në degën e -

64
00:04:34,140 --> 00:04:39,300
ne i referohemi atyre si gjethe - me anë të se nuk mund të ketë ndonjë dykuptimësi

65
00:04:39,300 --> 00:04:45,160
në terma të cilat letra ju jeni duke u përpjekur për të kodifikuar me serinë e bit

66
00:04:45,160 --> 00:04:50,670
sepse askund përgjatë bit që përfaqësojnë 1 letër

67
00:04:50,670 --> 00:04:55,960
do të hasni një tjetër letër të tërë, dhe nuk do të ketë asnjë konfuzion atje.

68
00:04:55,960 --> 00:04:58,430
Por ne do të shkojnë në shembujt se ju djema mund të vërtetë shohim se

69
00:04:58,430 --> 00:05:02,120
në vend që të na thënë se vetëm kjo është e vërtetë.

70
00:05:02,120 --> 00:05:06,390
>> Le të shikojmë në një shembull të thjeshtë të një peme Huffman.

71
00:05:06,390 --> 00:05:09,380
Unë kam një varg këtu që është 12 karaktere i gjatë.

72
00:05:09,380 --> 00:05:14,010
Unë kam 4 Si, 6 BS, dhe 2 Cs.

73
00:05:14,010 --> 00:05:17,270
Hapi im i parë do të jetë për të numëruar.

74
00:05:17,270 --> 00:05:20,760
Sa herë ka një duket? Duket se 4 herë në vargun.

75
00:05:20,760 --> 00:05:25,060
B shfaqet 6 herë, dhe C duket 2 herë.

76
00:05:25,060 --> 00:05:28,970
Natyrisht, unë jam duke shkuar për të thonë se unë jam duke përdorur B më shpesh,

77
00:05:28,970 --> 00:05:35,970
kështu që unë dua për të përfaqësuar B me numrin fewest të bit, numri i paktët 0s dhe 1s.

78
00:05:35,970 --> 00:05:42,600
Dhe atëherë unë jam gjithashtu do të presin C të kërkojë shumën më të madhe të 0s dhe 1s si.

79
00:05:42,600 --> 00:05:48,550
Të parë se çfarë kam bërë unë këtu është vendosur ato në ngjitje qëllim në drejtim të frekuencës.

80
00:05:48,550 --> 00:05:52,710
Ne e shohim se C dhe A, ata janë frekuenca 2 tonë më të ulët.

81
00:05:52,710 --> 00:06:00,290
Ne të krijojë një nyje prind, dhe se nyja prind nuk ka një letër lidhur me të,

82
00:06:00,290 --> 00:06:05,070
por ajo ka një frekuencë, e cila është shuma.

83
00:06:05,070 --> 00:06:08,780
Shuma bëhet 2 + 4, i cili është 6.

84
00:06:08,780 --> 00:06:10,800
Atëherë ne ndjekim degën e majtë.

85
00:06:10,800 --> 00:06:14,970
Nëse do të ishim në atë nyje 6, atëherë ne do të ndjekim për të marrë në 0 C

86
00:06:14,970 --> 00:06:17,450
dhe pastaj të merrni 1 në A.

87
00:06:17,450 --> 00:06:20,300
Deri tani ne kemi 2 nyje.

88
00:06:20,300 --> 00:06:23,920
Ne kemi vlerën 6 dhe pastaj ne gjithashtu kemi një nyje me vlerë 6.

89
00:06:23,920 --> 00:06:28,550
Dhe kështu ata 2 nuk janë vetëm 2 të ulët, por edhe vetëm 2 që janë lënë,

90
00:06:28,550 --> 00:06:33,820
kështu që ne të bashkohen ato nga një prind, me shuma të qenit 12.

91
00:06:33,820 --> 00:06:36,300
Pra, këtu kemi Huffman pemë tonë

92
00:06:36,300 --> 00:06:40,020
ku mund të merrni në B, që do të jetë vetëm pak 1

93
00:06:40,020 --> 00:06:45,430
dhe pastaj të shkoj në një ne do të kemi 01 dhe pastaj C ka 00.

94
00:06:45,430 --> 00:06:51,300
Kështu që këtu ne shohim se në thelb ne jemi duke përfaqësuar këto chars me ose 1 ose 2 copa

95
00:06:51,300 --> 00:06:55,160
ku B, parashikoi si, ka më së paku.

96
00:06:55,160 --> 00:07:01,730
Dhe pastaj ne kishim pritur C të ketë më, por që nga ajo është e tillë një pemë e vogël Huffman,

97
00:07:01,730 --> 00:07:06,020
atëherë A është përfaqësuar edhe nga 2 copa në krahasim me diku në mes.

98
00:07:07,820 --> 00:07:11,070
>> Vetëm për të shkuar mbi një tjetër shembull të thjeshtë të pemës Huffman,

99
00:07:11,070 --> 00:07:19,570
thonë se ju keni string "Hello".

100
00:07:19,570 --> 00:07:25,360
Çfarë ju bëni është e parë që ju do të thonë se sa herë do të paraqitet në këtë H?

101
00:07:25,360 --> 00:07:34,200
H shfaqet herë dhe pastaj e duket një herë dhe pastaj kemi l paraqitet dy herë

102
00:07:34,200 --> 00:07:36,580
dhe o shfaqeshin herë.

103
00:07:36,580 --> 00:07:44,310
Dhe kështu, atëherë ne presim që letra të përfaqësohet me numrin më të vogël të bit?

104
00:07:44,310 --> 00:07:47,450
[Student] l. L. >> Po. l është e drejtë.

105
00:07:47,450 --> 00:07:50,730
Ne presim l të përfaqësuara nga numri pak e bit

106
00:07:50,730 --> 00:07:55,890
sepse l është përdorur më shumë në vargun "Hello".

107
00:07:55,890 --> 00:08:04,280
Ajo që unë jam duke shkuar për të bërë tani është të nxjerrë jashtë këto nyje.

108
00:08:04,280 --> 00:08:15,580
Kam 1, e cila është H, dhe pastaj një tjetër 1, e cila është E, dhe pastaj një 1, e cila është O -

109
00:08:15,580 --> 00:08:23,410
tani unë jam vënë ato në mënyrë - dhe pastaj 2, e cila është l.

110
00:08:23,410 --> 00:08:32,799
Atëherë unë them rruga që unë ndërtuar një pemë Huffman është për të gjetur 2 nyjet me frekuenca më pak

111
00:08:32,799 --> 00:08:38,010
dhe t'i bëjë ata vëllezërit e motrat, duke krijuar një nyje prind.

112
00:08:38,010 --> 00:08:41,850
Këtu ne kemi 3 nyjet me frekuencë të ulët. Ata janë të gjithë 1.

113
00:08:41,850 --> 00:08:50,620
Pra, këtu kemi të zgjidhni një ne jemi duke shkuar për të lidhur së pari.

114
00:08:50,620 --> 00:08:54,850
Le të thonë se unë zgjedh H dhe e.

115
00:08:54,850 --> 00:09:01,150
Shuma e 1 + 1 është 2, por kjo nyje nuk ka një letër lidhur me të.

116
00:09:01,150 --> 00:09:04,440
Ajo thjesht e mban vlerën.

117
00:09:04,440 --> 00:09:10,950
Tani ne shikojmë në 2 frekuenca e ardhshme të ulët.

118
00:09:10,950 --> 00:09:15,590
Kjo është 2 dhe 1. Kjo mund të jetë ose nga ato 2, por unë jam duke shkuar për të zgjedhur këtë.

119
00:09:15,590 --> 00:09:18,800
Shuma është 3.

120
00:09:18,800 --> 00:09:26,410
Dhe pastaj në fund, unë vetëm 2 majtas, në mënyrë që pastaj të bëhet 5.

121
00:09:26,410 --> 00:09:32,010
Atëherë këtu, siç pritet, në qoftë se unë të plotësoni në encoding për atë,

122
00:09:32,010 --> 00:09:37,480
1s janë gjithmonë dega e drejtë dhe 0s janë një majtë.

123
00:09:37,480 --> 00:09:45,880
Pastaj kemi l përfaqësuar nga vetëm pak 1 dhe pastaj o nga 2

124
00:09:45,880 --> 00:09:52,360
dhe pastaj e nga 2 dhe pastaj H bie poshtë për 3 copa.

125
00:09:52,360 --> 00:09:59,750
Kështu që ju mund të transmetojë këtë mesazh "Hello" në vend të vërtetë duke përdorur karakteret

126
00:09:59,750 --> 00:10:02,760
vetëm me 0s dhe 1s.

127
00:10:02,760 --> 00:10:07,910
Megjithatë, mbani mend se në disa raste kemi pasur lidhje me frekuencën tonë.

128
00:10:07,910 --> 00:10:11,900
Ne mund të kemi bashkuar ose H dhe o Së pari ndoshta.

129
00:10:11,900 --> 00:10:15,730
Ose pastaj më vonë, kur ne kishim l përfaqësuar nga 2

130
00:10:15,730 --> 00:10:19,410
si dhe u bashkua me një përfaqësohet nga 2, ne mund të kemi lidhur ose një.

131
00:10:19,410 --> 00:10:23,630
>> Dhe kështu që kur ju të dërgoni 0s dhe 1s, që në fakt nuk garanton

132
00:10:23,630 --> 00:10:27,090
se përfituesi mund plotësisht të lexuar mesazhin tuaj të drejtën off bat

133
00:10:27,090 --> 00:10:30,490
sepse ata nuk mund të dinë se cilat vendimi që keni bërë.

134
00:10:30,490 --> 00:10:34,920
Pra, kur ne jemi që kanë të bëjnë me compression Huffman,

135
00:10:34,920 --> 00:10:40,090
disi ne kemi për të të treguar marrësit e mesazhit tonë se si ne kemi vendosur -

136
00:10:40,090 --> 00:10:43,470
Ata duhet të dinë disa lloj informacioni shtesë

137
00:10:43,470 --> 00:10:46,580
Përveç mesazhit të ngjeshur.

138
00:10:46,580 --> 00:10:51,490
Ata kanë nevojë për të kuptuar se çfarë në të vërtetë duket si pema,

139
00:10:51,490 --> 00:10:55,450
se si ne fakt e bëri ato vendime.

140
00:10:55,450 --> 00:10:59,100
>> Këtu ne ishim vetëm duke bërë shembuj bazuar në numërimin aktuale,

141
00:10:59,100 --> 00:11:01,550
por ndonjëherë ju gjithashtu mund të ketë një pemë Huffman

142
00:11:01,550 --> 00:11:05,760
bazuar në frekuencën në të cilën letra shfaqet, dhe kjo është procesi saktë të njëjtën.

143
00:11:05,760 --> 00:11:09,090
Këtu unë jam shprehur atë në aspektin e përqindjeve apo një pjesë,

144
00:11:09,090 --> 00:11:11,290
dhe kështu që këtu gjë e saktë të njëjtën.

145
00:11:11,290 --> 00:11:15,300
I gjeni 2 të ulët, të përmbledhur ato, 2 e ardhshëm më të ulët, të përmbledhur ato,

146
00:11:15,300 --> 00:11:19,390
deri sa unë kam një pemë të plotë.

147
00:11:19,390 --> 00:11:23,610
Edhe pse ne mund të bëjmë atë Ose mënyrë, kur ne jemi që kanë të bëjnë me përqindje,

148
00:11:23,610 --> 00:11:27,760
që do të thotë ne jemi të ndarë gjëra dhe që kanë të bëjnë me decimale ose më mirë gjithandej

149
00:11:27,760 --> 00:11:30,900
në qoftë se ne jemi duke menduar për të dhënat e strukturave të një kokë.

150
00:11:30,900 --> 00:11:32,540
Çfarë ne dimë rreth gjithandej?

151
00:11:32,540 --> 00:11:35,180
Çfarë është një problem i zakonshëm, kur ne jemi që kanë të bëjnë me të gjithandej?

152
00:11:35,180 --> 00:11:38,600
[Student] aritmetike pasakta. Po >>. Pasaktësi.

153
00:11:38,600 --> 00:11:43,760
Për shkak të jo saktësi pikë lundrues, për këtë pset në mënyrë që ne të sigurt

154
00:11:43,760 --> 00:11:49,450
se ne nuk do ta humbasin asnjë vlerat, atëherë ne jemi në të vërtetë do të kanë të bëjnë me numërimin.

155
00:11:49,450 --> 00:11:54,880
Pra, nëse ju keni qenë të mendojnë për një nyje Huffman, nëse ju shikoni prapa në strukturën këtu,

156
00:11:54,880 --> 00:12:01,740
në qoftë se ju shikoni në ato gjelbër ka një frekuencë lidhur me të

157
00:12:01,740 --> 00:12:08,760
si dhe ajo tregon në një nyje në të majtë të saj, si dhe një nyje në të djathtë të tij.

158
00:12:08,760 --> 00:12:13,970
Dhe pastaj ato të kuqe ka gjithashtu kanë një karakter të lidhur me to.

159
00:12:13,970 --> 00:12:18,900
Ne nuk jemi duke shkuar për të bërë ato të veçanta për prindërit dhe pastaj nyjet e fundit,

160
00:12:18,900 --> 00:12:23,680
të cilat ne i referohemi si gjethe, por ata do të ketë vetëm vlera NULL.

161
00:12:23,680 --> 00:12:31,050
Për çdo nyje ne do të kemi një karakter, simboli që kjo nyje përfaqëson,

162
00:12:31,050 --> 00:12:40,490
pastaj një frekuencë, si dhe një tregues për fëmijën e saj të majtë, si dhe fëmijën e saj të drejtë.

163
00:12:40,490 --> 00:12:45,680
Gjethet, të cilat janë në fund shumë, gjithashtu do të ketë pointers nyjen

164
00:12:45,680 --> 00:12:49,550
në të majtë të tyre dhe në të djathtë të tyre, por që këto vlera nuk janë treguar në nyjet aktuale,

165
00:12:49,550 --> 00:12:53,970
çfarë do të jetë vlera e tyre? >> [Student] NULL. NULL. >> Saktësisht.

166
00:12:53,970 --> 00:12:58,430
Ja një shembull se si ju mund të përfaqësojë frekuencën në trap,

167
00:12:58,430 --> 00:13:02,130
por ne jemi duke shkuar për të merret me atë me integers,

168
00:13:02,130 --> 00:13:06,780
kështu që të gjitha që kam bërë është të ndryshojë llojin e të dhënave atje.

169
00:13:06,780 --> 00:13:09,700
>> Le të shkojnë për të pak më shumë se një shembull komplekse.

170
00:13:09,700 --> 00:13:13,360
Por tani që ne kemi bërë ato të thjeshta, kjo është vetëm procesi i njëjtë.

171
00:13:13,360 --> 00:13:20,290
Ju gjeni 2 frekuenca më të ulëta, të përmbledhur frekuencat

172
00:13:20,290 --> 00:13:22,450
dhe kjo është frekuenca e re e nyjeve tuaj mëmë,

173
00:13:22,450 --> 00:13:29,310
e cila më pas tregon në të majtë të saj me degën 0 dhe të drejtën me degën 1.

174
00:13:29,310 --> 00:13:34,200
Në qoftë se ne kemi vargun "Kjo është CS50," atëherë ne numërimin e sa herë është përmendur T,

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

176
00:13:38,420 --> 00:13:42,010
Atëherë çfarë kam bërë këtu është me nyje të kuqe unë vetëm mbjellë,

177
00:13:42,010 --> 00:13:48,530
Kam thënë unë jam duke shkuar të ketë këto karaktere përfundimisht në fund të pemës sime.

178
00:13:48,530 --> 00:13:51,740
Ata do të jenë të gjithë gjethe.

179
00:13:51,740 --> 00:13:58,200
Atëherë çfarë kam bërë unë është renditur ato sipas frekuencës në ngjitje qëllim,

180
00:13:58,200 --> 00:14:02,950
dhe ky fakt është mënyra se kodi pset e bën atë

181
00:14:02,950 --> 00:14:07,550
është ajo lloj atë me frekuencë dhe pastaj alfabetikisht.

182
00:14:07,550 --> 00:14:13,870
Pra, ajo ka numrat e parë dhe pastaj alfabetikisht nga frekuenca.

183
00:14:13,870 --> 00:14:18,520
Atëherë çfarë do të bëj është që unë do të gjeni 2 të ulët. Kjo është 0 dhe 5.

184
00:14:18,520 --> 00:14:22,390
Unë do të përmbledhur ata, dhe kjo është 2. Atëherë unë do të vazhdojë, të gjejnë tjetër 2 të ulët.

185
00:14:22,390 --> 00:14:26,100
Ata janë 1s dy, dhe pastaj ata të bëhen 2 si.

186
00:14:26,100 --> 00:14:31,570
Tani unë e di se hapi im i ardhshëm do të jetë bashkimi me numrin më të vogël,

187
00:14:31,570 --> 00:14:41,380
cila është T, 1, dhe pastaj duke zgjedhur një nga nyjet që ka 2 si frekuencë.

188
00:14:41,380 --> 00:14:44,560
Pra, këtu kemi 3 opsione.

189
00:14:44,560 --> 00:14:47,980
Ajo që unë jam duke shkuar për të bërë për rrëshqitje është vetëm vizualisht korrigjoj ato për ju

190
00:14:47,980 --> 00:14:51,790
kështu që ju mund të shihni se si unë jam duke ndërtuar atë.

191
00:14:51,790 --> 00:14:59,040
Çfarë kodi dhe kodin tuaj të shpërndarjes do të bëjë do të bashkohen me njëri-T

192
00:14:59,040 --> 00:15:01,410
me nyje 0 dhe 5.

193
00:15:01,410 --> 00:15:05,060
Kështu, pra, se shuma në 3, dhe pastaj ne vazhdojmë procesin.

194
00:15:05,060 --> 00:15:08,660
E 2 dhe 2 tani janë më të ulët, në mënyrë që pastaj ata shuma deri në 4.

195
00:15:08,660 --> 00:15:12,560
Gjithkush pas deri tani? Rregull.

196
00:15:12,560 --> 00:15:16,410
Pastaj pas kësaj ne kemi 3 dhe 3 që kanë nevojë për të shtuar deri,

197
00:15:16,410 --> 00:15:21,650
kështu përsëri unë jam vetëm kalimi atë mënyrë që ju mund të shihni me sy në mënyrë që ajo nuk ka marrë shumë të çrregullt.

198
00:15:21,650 --> 00:15:25,740
Pastaj ne kemi një 6, dhe pastaj hapi ynë përfundimtar është tani që ne kemi vetëm 2 nyje

199
00:15:25,740 --> 00:15:30,440
Ne përmbledhur ato për të bërë rrënja e pemës tonë, e cila është 10.

200
00:15:30,440 --> 00:15:34,100
Dhe numri 10 ka kuptim, sepse çdo nyje të përfaqësuara,

201
00:15:34,100 --> 00:15:40,750
vlera e tyre, numri i tyre frekuenca, ishte se sa herë ata u shfaq në varg,

202
00:15:40,750 --> 00:15:46,350
dhe pastaj ne kemi 5 karaktere në vargun tonë, në mënyrë që e bën kuptim.

203
00:15:48,060 --> 00:15:52,320
Nëse ne shikojmë deri në mënyrën se si ne fakt do shifroj atë,

204
00:15:52,320 --> 00:15:56,580
siç pritet, unë dhe s, e cila shfaqet më shpesh

205
00:15:56,580 --> 00:16:01,350
janë të përfaqësuara nga numrin fewest e bit.

206
00:16:03,660 --> 00:16:05,660
>> Të jenë të kujdesshëm këtu.

207
00:16:05,660 --> 00:16:09,780
Në pemë Huffman rasti të vërtetë rëndësi.

208
00:16:09,780 --> 00:16:13,670
Një S uppercase është i ndryshëm se sa një s Fjala.

209
00:16:13,670 --> 00:16:21,260
Nëse do të kishim "Kjo është CS50" me shkronja të mëdha, atëherë s vogla do të shfaqet vetëm dy herë,

210
00:16:21,260 --> 00:16:27,120
do të jetë një nyje me 2 si vlerën e saj, dhe pastaj të uppercase S do të jetë vetëm një herë.

211
00:16:27,120 --> 00:16:33,440
Pra, atëherë pema juaj do të ndryshojë strukturat sepse ju në fakt kanë një fletë shtesë këtu.

212
00:16:33,440 --> 00:16:36,900
Por shuma do të jetë ende 10.

213
00:16:36,900 --> 00:16:39,570
Kjo është ajo që ne jemi në të vërtetë do të jetë quajtur checksum,

214
00:16:39,570 --> 00:16:44,060
shtimi i të gjitha akuzave.

215
00:16:46,010 --> 00:16:50,990
>> Tani që ne kemi mbuluar pemë Huffman, ne mund të zhyten në Puff Huff'n, pset.

216
00:16:50,990 --> 00:16:52,900
Ne jemi duke shkuar për të filluar me një pjesë të pyetjeve,

217
00:16:52,900 --> 00:16:57,990
dhe kjo do të merrni ju për të mësuar me pemë binare dhe si të veprojë rreth se:

218
00:16:57,990 --> 00:17:03,230
nyjet vizatim, krijimin e vet struct tuaj typedef për një nyje,

219
00:17:03,230 --> 00:17:07,230
dhe duke parë se si ju mund të futni në një pemë binare, një që është renditura,

220
00:17:07,230 --> 00:17:09,050
traversing atë, dhe gjëra të tilla si kjo.

221
00:17:09,050 --> 00:17:14,560
Kjo njohuri është padyshim do të ju ndihmojë kur ju pikiatë në pjesën pudre Huff'n

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

223
00:17:19,150 --> 00:17:26,329
Në edicionin e standardit të pset, detyra juaj është për të zbatuar pudre,

224
00:17:26,329 --> 00:17:30,240
dhe në versionin hacker detyra juaj është për të zbatuar Huff.

225
00:17:30,240 --> 00:17:38,490
Çfarë Huff nuk është ajo merr tekstin dhe pastaj ajo përkthen atë në të 0s dhe 1s,

226
00:17:38,490 --> 00:17:41,990
kështu proces që ne e bëmë më sipër, ku ne numërohen frekuencat

227
00:17:41,990 --> 00:17:50,970
dhe pastaj e bëri pemë dhe pastaj tha: "Si mund të shkoj T?"

228
00:17:50,970 --> 00:17:54,840
T është e përfaqësuar nga 100, gjëra të tilla si kjo,

229
00:17:54,840 --> 00:17:58,860
dhe pastaj Huff do të marrë tekstin dhe pastaj e prodhimit që binar.

230
00:17:58,860 --> 00:18:04,920
Por edhe sepse ne e dimë që ne duam për të lejuar marrësit e mesazhit tonë

231
00:18:04,920 --> 00:18:11,790
të krijosh pemë e saktë të njëjta, ajo gjithashtu përfshin informacion në lidhje me akuzat e frekuencave.

232
00:18:11,790 --> 00:18:17,980
Pastaj me Puff ne jemi të dhënë një skedar binar të 0s dhe 1s

233
00:18:17,980 --> 00:18:21,740
dhe duke pasur parasysh edhe informacion në lidhje me frekuenca.

234
00:18:21,740 --> 00:18:26,740
Ne përkthejnë të gjitha ato mbrapa 0s dhe 1s në mesazhin origjinale që ishte,

235
00:18:26,740 --> 00:18:29,350
kështu që ne jemi decompressing se.

236
00:18:29,350 --> 00:18:36,450
Nëse jeni duke bërë edicionin standarde, ju nuk keni nevojë për të zbatuar Huff,

237
00:18:36,450 --> 00:18:39,290
kështu atëherë ju mund të përdorni vetëm zbatimin e stafit Huff.

238
00:18:39,290 --> 00:18:42,080
Ka udhëzime në spekulim se si ta bëjnë këtë.

239
00:18:42,080 --> 00:18:48,780
Ju mund të drejtuar zbatimin e stafit Huff mbi një skedar teksti të caktuar

240
00:18:48,780 --> 00:18:53,270
dhe pastaj të përdorin atë si input output tuaj për pudre.

241
00:18:53,270 --> 00:18:59,330
>> Siç e kam përmendur më parë, ne kemi një shumë të kodit të shpërndarjes për këtë një të tillë.

242
00:18:59,330 --> 00:19:01,810
Unë jam duke shkuar për të filluar shkojnë nëpërmjet saj.

243
00:19:01,810 --> 00:19:04,400
Unë jam duke shkuar për të shpenzuar pjesën më të madhe të kohës në internet. Fotografi h

244
00:19:04,400 --> 00:19:07,660
sepse në fotografi. c, sepse ne kemi. h

245
00:19:07,660 --> 00:19:11,650
dhe që na ofron me prototipa të funksioneve,

246
00:19:11,650 --> 00:19:15,520
ne nuk kemi nevojë për të kuptuar plotësisht saktësisht -

247
00:19:15,520 --> 00:19:20,280
Nëse ju nuk e kuptoni se çfarë po ndodh në fotografi. C, atëherë mos u shqetësoni shumë,

248
00:19:20,280 --> 00:19:23,600
por patjetër të përpiqet të marrë një sy, sepse ajo mund të japë disa lë të kuptohet se

249
00:19:23,600 --> 00:19:29,220
dhe kjo është e dobishme për të marrë të përdoret për të lexuar kodin e njerëzve të tjerë.

250
00:19:38,940 --> 00:19:48,270
>> Duke kërkuar në huffile.h, në komentet që deklaron një shtresë e abstraksionit për Huffman-koduara fotografi.

251
00:19:48,270 --> 00:20:01,660
Nëse ne do të shkojmë poshtë, ne shohim se ka një maksimum prej 256 simboleve që ne mund të kenë nevojë për kodet.

252
00:20:01,660 --> 00:20:05,480
Kjo përfshin të gjitha shkronjat e alfabetit - uppercase dhe të vogla -

253
00:20:05,480 --> 00:20:08,250
dhe pastaj simbolet dhe numrat, etj

254
00:20:08,250 --> 00:20:11,930
Atëherë këtu kemi një numër magjik identifikuar një skedar të koduar Huffman.

255
00:20:11,930 --> 00:20:15,890
Brenda një kod Huffman ata do të kenë një numër të caktuar magjike

256
00:20:15,890 --> 00:20:18,560
shoqëruar me kokë.

257
00:20:18,560 --> 00:20:21,110
Kjo mund të duket si vetëm një numër magjik të rastit,

258
00:20:21,110 --> 00:20:27,160
por në qoftë se ju në të vërtetë përkthejnë atë në ASCII, atëherë ai në fakt parashikon Huff.

259
00:20:27,160 --> 00:20:34,290
Këtu kemi një struct për një skedar Huffman-koduara.

260
00:20:34,290 --> 00:20:39,670
Ka të gjitha këto karakteristika që lidhen me një file Huff.

261
00:20:39,670 --> 00:20:47,080
Pastaj këtu poshtë kemi header për një skedar Huff, kështu që ne e quajmë atë Huffeader

262
00:20:47,080 --> 00:20:50,810
në vend të shtuar h shtesë, sepse kjo tingëllon e njëjtë anyway.

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

264
00:20:52,720 --> 00:20:57,790
Ne kemi një numër magjik lidhur me të.

265
00:20:57,790 --> 00:21:09,040
Në qoftë se kjo është një fotografi aktuale Huff, ajo do të jetë numri lart, kjo magji.

266
00:21:09,040 --> 00:21:14,720
Dhe pastaj ajo do të ketë një rrjet.

267
00:21:14,720 --> 00:21:18,750
Pra, për çdo simbol, e cila ka 256,

268
00:21:18,750 --> 00:21:24,760
ajo do të listës atë që frekuenca e këtyre simboleve janë brenda file Huff.

269
00:21:24,760 --> 00:21:28,090
Dhe pastaj në fund, ne kemi një checksum për frekuencave,

270
00:21:28,090 --> 00:21:32,160
cila duhet të jetë shuma e këtyre frekuencave.

271
00:21:32,160 --> 00:21:36,520
Pra, kjo është ajo që një Huffeader është.

272
00:21:36,520 --> 00:21:44,600
Pastaj ne kemi disa funksione që kthejë pak ardhshëm në dosjen Huff

273
00:21:44,600 --> 00:21:52,580
si shkruan një grimë në dosjen Huff, dhe pastaj ky funksion këtu, hfclose,

274
00:21:52,580 --> 00:21:54,650
që në fakt mbyll dosjen Huff.

275
00:21:54,650 --> 00:21:57,290
Para se, ne kemi qenë që kanë të bëjnë me të drejtë vetëm Shkrimi,

276
00:21:57,290 --> 00:22:01,190
por kur ju keni një fotografi Huff, në vend të fclosing atë

277
00:22:01,190 --> 00:22:06,080
atë që ju jeni të vërtetë do të bëni është të hfclose dhe hfopen atë.

278
00:22:06,080 --> 00:22:13,220
Ata janë funksione specifike për dosjet Huff që ne jemi duke shkuar për të që kanë të bëjnë me të.

279
00:22:13,220 --> 00:22:19,230
Atëherë këtu kemi lexuar në kokë dhe pastaj shkruani header.

280
00:22:19,230 --> 00:22:25,700
>> Vetëm duke lexuar skedarin. H mundemi lloj të marrë një kuptim të asaj një file Huff mund të jetë,

281
00:22:25,700 --> 00:22:32,480
çfarë karakteristikat që ka, në fakt pa shkuar në huffile.c,

282
00:22:32,480 --> 00:22:36,750
të cilat, në qoftë se ne pikiatë në, do të jetë pak më e ndërlikuar.

283
00:22:36,750 --> 00:22:41,270
Ajo ka të gjitha file I / O këtu kanë të bëjnë me pointers.

284
00:22:41,270 --> 00:22:48,010
Këtu ne shohim se kur ne e quajmë hfread, për shembull, është ende që kanë të bëjnë me fread.

285
00:22:48,010 --> 00:22:53,050
Ne nuk jemi duke u shpëtoj prej këtyre funksioneve tërësisht, por ne jemi të dërguar ata për të marrë kujdesin e

286
00:22:53,050 --> 00:22:59,760
brenda file Huff në vend për të bërë të gjithë atë veten.

287
00:22:59,760 --> 00:23:02,300
Ju mund të ndjehen të lirë për të skanoni me këtë, nëse ju jeni kurioz

288
00:23:02,300 --> 00:23:08,410
dhe shkoni dhe zhvishem shtresën e mbrapa pak.

289
00:23:20,650 --> 00:23:24,060
>> Dosja tjetër që ne jemi duke shkuar për të parë në është tree.h.

290
00:23:24,060 --> 00:23:30,210
Parë në Walkthrough slides ne tha se ne presim një nyje Huffman

291
00:23:30,210 --> 00:23:32,960
dhe kemi bërë një nyje typedef struct.

292
00:23:32,960 --> 00:23:38,360
Ne presim që ajo të ketë një simbol, një frekuencë, dhe pastaj 2 yje të mundshëm nyje.

293
00:23:38,360 --> 00:23:41,870
Në këtë rast ajo që ne po bëjmë është kjo është në thelb e njëjtë

294
00:23:41,870 --> 00:23:46,880
përveç në vend të nyjeve ne jemi duke shkuar për të thirrur ata pemëve.

295
00:23:48,790 --> 00:23:56,760
Ne kemi një funksion që kur ju telefononi bëni pemë të kthehet ju një tregues pemë.

296
00:23:56,760 --> 00:24:03,450
Mbrapsht në speller, kur ju u bërë një nyje të re

297
00:24:03,450 --> 00:24:11,410
ju tha nyje * fjalë të re = malloc (sizeof) dhe gjëra të tilla si se.

298
00:24:11,410 --> 00:24:17,510
Në thelb, mktree do të jetë që kanë të bëjnë me atë për ju.

299
00:24:17,510 --> 00:24:20,990
Në mënyrë të ngjashme, kur ju dëshironi të hiqni një pemë,

300
00:24:20,990 --> 00:24:24,810
kështu që në thelb është liruar pemë, kur ju jeni bërë me të,

301
00:24:24,810 --> 00:24:33,790
vend të lirë në mënyrë eksplicite duke bërë thirrje që ju jeni në të vërtetë vetëm duke shkuar për të përdorur funksionin rmtree

302
00:24:33,790 --> 00:24:40,360
ku ju të kalojë në treguesin në atë pemë dhe pastaj elementit do të kujdeset për ju.

303
00:24:40,360 --> 00:24:42,490
>> Ne shikojmë në tree.c.

304
00:24:42,490 --> 00:24:47,240
Ne presim që të njëjtat funksione, përveç për të parë zbatimin si.

305
00:24:47,240 --> 00:24:57,720
Siç kemi pritur, kur ju telefononi atë mktree mallocs madhësinë e një pemë në një akrep,

306
00:24:57,720 --> 00:25:03,190
initializes të gjitha vlerat në vlera null, kështu 0s ose NULLs,

307
00:25:03,190 --> 00:25:08,280
dhe pastaj kthen treguesin në atë pemë që e keni malloc'd vetëm për ju.

308
00:25:08,280 --> 00:25:13,340
Këtu kur ju telefononi për të hequr pemë kjo e parë e bën të sigurt që ju nuk jeni të dyfishtë liruar.

309
00:25:13,340 --> 00:25:18,320
Kjo e bën të sigurt që ju të vërtetë kanë një pemë që ju dëshironi të hiqni.

310
00:25:18,320 --> 00:25:23,330
Këtu sepse një pemë përfshin edhe fëmijët e saj,

311
00:25:23,330 --> 00:25:29,560
Çfarë kjo nuk është ajo e quan Recursively të hequr pemë në nyjen e majtë të pemës

312
00:25:29,560 --> 00:25:31,650
si dhe nyjen e djathtë.

313
00:25:31,650 --> 00:25:37,790
Para se ajo liron prindin, ajo ka nevojë për të liruar fëmijët si.

314
00:25:37,790 --> 00:25:42,770
Prindi është gjithashtu i këmbyeshëm me rrënjë.

315
00:25:42,770 --> 00:25:46,500
Prindi parë ndonjëherë, kështu që si i madh-madhe-madhe-madh-gjyshi

316
00:25:46,500 --> 00:25:52,130
ose dru gjyshja, së pari ne duhet ta lirojmë poshtë niveleve të parë.

317
00:25:52,130 --> 00:25:58,490
Pra, përshkojnë në fund, pa ato, dhe pastaj të kthehen deri, pa ato, etj

318
00:26:00,400 --> 00:26:02,210
Pra, kjo është pema.

319
00:26:02,210 --> 00:26:04,240
>> Tani ne shikojmë në pyll.

320
00:26:04,240 --> 00:26:09,860
Pylli është ajo ku ju vendosni të gjitha pemëve Huffman tuaj.

321
00:26:09,860 --> 00:26:12,910
Është thënë se ne do të kemi diçka të quajtur një komplot

322
00:26:12,910 --> 00:26:22,320
që përmban një tregues për një pemë si një tregues për një komplot të quajtur ardhshëm.

323
00:26:22,320 --> 00:26:28,480
Çfarë e bën këtë strukturë lloj të duken si?

324
00:26:29,870 --> 00:26:32,490
Ai lloj i thotë atë atje.

325
00:26:34,640 --> 00:26:36,700
Drejtë mbi këtu.

326
00:26:37,340 --> 00:26:39,170
Një listë e lidhur.

327
00:26:39,170 --> 00:26:44,590
Ne shohim se kur kemi një komplot është si një listë e lidhur e ngastrave.

328
00:26:44,590 --> 00:26:53,020
Një pyll është përcaktuar si një listë e lidhur e parcelave,

329
00:26:53,020 --> 00:26:58,100
dhe kështu struktura e pyjeve është që ne jemi vetëm do të ketë një tregues për komplot tonë të parë

330
00:26:58,100 --> 00:27:02,740
dhe që komploti ka një pemë brenda saj ose më mirë tregon një pemë

331
00:27:02,740 --> 00:27:06,190
dhe pastaj tregon për komplot tjetër, kështu me radhë e kështu me radhë.

332
00:27:06,190 --> 00:27:11,100
Për të bërë një pyll që ne e quajmë mkforest.

333
00:27:11,100 --> 00:27:14,930
Pastaj ne kemi disa funksione mjaft të dobishme këtu.

334
00:27:14,930 --> 00:27:23,240
Ne kemi marr ku ju të kalojë në një pyll dhe pastaj vlera e kthimit është një * Tree,

335
00:27:23,240 --> 00:27:25,210
një akrep tek një peme.

336
00:27:25,210 --> 00:27:29,370
Çfarë do të bëni është të vini ai do të shkojë në pyll se ju jeni treguar të

337
00:27:29,370 --> 00:27:35,240
atëherë hiqni një pemë me frekuencë më të ulët nga ajo pyll

338
00:27:35,240 --> 00:27:38,330
dhe pastaj ju japin treguesin në atë pemë.

339
00:27:38,330 --> 00:27:43,030
Pasi ju e quani vini, pema nuk do të ekzistojë më në pyll,

340
00:27:43,030 --> 00:27:48,550
por vlera e kthimit është tregues për atë pemë.

341
00:27:48,550 --> 00:27:50,730
Atëherë ju keni bimë.

342
00:27:50,730 --> 00:27:57,420
Me kusht që ju të kalojë në një tregues për një pemë që ka një frekuencë jo-0,

343
00:27:57,420 --> 00:28:04,040
çfarë do të bëni është bimë ajo do të marrë në pyll, të marrë pemë dhe bimë që brenda pema e pyllit.

344
00:28:04,040 --> 00:28:06,370
Këtu kemi rmforest.

345
00:28:06,370 --> 00:28:11,480
Ngjashme për të hequr pemë, e cila në thelb liruar të gjitha pemëve tona për ne,

346
00:28:11,480 --> 00:28:16,600
hiqni çdo gjë do pyll pa përmbajtura në këtë pyll.

347
00:28:16,600 --> 00:28:24,890
>> Nëse ne shikojmë në forest.c, ne do të presim të shohim të paktën 1 komandë rmtree në atje,

348
00:28:24,890 --> 00:28:30,090
për shkak të kujtesës të lirë në pyll nëse një pylli ka pemë në të,

349
00:28:30,090 --> 00:28:32,930
pastaj përfundimisht ju jeni do të duhet për të hequr ato pemë shumë.

350
00:28:32,930 --> 00:28:41,020
Nëse ne shikojmë në forest.c, ne kemi mkforest tonë, e cila është si ne presim.

351
00:28:41,020 --> 00:28:42,890
Ne malloc gjëra.

352
00:28:42,890 --> 00:28:51,740
Ne nisja komplot parë në pyll si NULL, sepse kjo është e zbrazët për të filluar me të,

353
00:28:51,740 --> 00:29:05,940
atëherë ne shohim marr, e cila kthen pemë me peshë të ulët, frekuenca më të ulët,

354
00:29:05,940 --> 00:29:13,560
dhe pastaj merr shpëtoj të asaj nyje të veçantë që tregon atë pemë dhe një tjetër,

355
00:29:13,560 --> 00:29:16,760
kështu që ajo merr nga lista e lidhur e pyllit.

356
00:29:16,760 --> 00:29:24,510
Dhe atëherë këtu kemi bimore, i cili fut një pemë në listën e lidhur.

357
00:29:24,510 --> 00:29:29,960
Çfarë pyll nuk është ajo e bukur e mban atë renditura për ne.

358
00:29:29,960 --> 00:29:37,910
Dhe pastaj në fund, ne kemi rmforest dhe, siç pritej, ne kemi rmtree thirrur atje.

359
00:29:46,650 --> 00:29:55,440
>> Duke parë në kodin e shpërndarjes deri tani, huffile.c ndoshta ishte deri tani më e vështirë për të kuptuar,

360
00:29:55,440 --> 00:29:59,990
ndërsa fotografi të tjera vetë ishin mjaft të thjeshtë për të ndjekur.

361
00:29:59,990 --> 00:30:03,090
Me njohuritë tona të pointers dhe listat e lidhura dhe të tilla,

362
00:30:03,090 --> 00:30:04,860
ne ishim në gjendje për të ndjekur mjaft mirë.

363
00:30:04,860 --> 00:30:10,500
Por të gjithë ne kemi nevojë të vërtetë të siguruar që ne e kuptojmë plotësisht është. Fotografi h

364
00:30:10,500 --> 00:30:15,840
sepse keni nevojë për të thirrur këto funksione, që kanë të bëjnë me ato vlera të kthimit,

365
00:30:15,840 --> 00:30:20,590
prandaj sigurohuni që ju të kuptoni plotësisht atë veprim do të kryhet

366
00:30:20,590 --> 00:30:24,290
kur ju telefononi një prej këtyre funksioneve.

367
00:30:24,290 --> 00:30:33,020
Por në fakt kuptuar në brendësi të saj nuk është mjaft e nevojshme, sepse ne kemi ato. Fotografi h.

368
00:30:35,170 --> 00:30:39,490
Ne kemi 2 më shumë fotografi mbetur në kodin tonë të shpërndarjes.

369
00:30:39,490 --> 00:30:41,640
>> Le të shikojmë në hale.

370
00:30:41,640 --> 00:30:47,230
Hale me komentin e saj këtu merr një skedar të kompresuar Huffman-

371
00:30:47,230 --> 00:30:55,580
dhe pastaj përkthehet dhe deponitë e gjithë përmbajtjen e saj jashtë.

372
00:31:01,010 --> 00:31:04,260
Këtu ne shohim se ajo flet hfopen.

373
00:31:04,260 --> 00:31:10,770
Kjo është lloj i mirroring të paraqesë * Input = fopen,

374
00:31:10,770 --> 00:31:13,500
dhe pastaj të kalojë në informacion.

375
00:31:13,500 --> 00:31:18,240
Kjo është pothuajse identike, përveç në vend të një skedar * ju jeni duke kaluar në një Huffile;

376
00:31:18,240 --> 00:31:22,030
vend të fopen ju jeni duke kaluar në hfopen.

377
00:31:22,030 --> 00:31:29,280
Këtu lexojmë në kokë parë, e cila është lloj i ngjashëm me mënyrën se si kemi lexuar në kokë

378
00:31:29,280 --> 00:31:33,580
për një fotografi bitmap.

379
00:31:33,580 --> 00:31:38,000
Ajo që ne po bëjmë këtu është kontrolluar për të parë nëse informacioni header

380
00:31:38,000 --> 00:31:44,330
përmban numrin e duhur magjike që tregon se ajo është një fotografi aktuale Huff,

381
00:31:44,330 --> 00:31:53,610
atëherë të gjitha këto kontrolle për të siguruar që ne të hapur file që është një file aktuale huffed apo jo.

382
00:31:53,610 --> 00:32:05,330
Çfarë kjo nuk është ajo rezultatet frekuencat e të gjitha simbolet që ne mund të shohim

383
00:32:05,330 --> 00:32:09,790
brenda një terminal në një tryezë grafik.

384
00:32:09,790 --> 00:32:15,240
Kjo pjesë do të jenë të dobishme.

385
00:32:15,240 --> 00:32:24,680
Ajo ka një grimë dhe lexon pak nga pak në pak ndryshueshme dhe pastaj shtyp atë.

386
00:32:28,220 --> 00:32:35,430
Pra, nëse unë do të thërrasë në hth.bin hale, e cila është rezultat i huffing një skedar

387
00:32:35,430 --> 00:32:39,490
duke përdorur zgjidhje stafit, unë do të merrni këtë.

388
00:32:39,490 --> 00:32:46,000
Është outputting të gjitha këto karaktere dhe pastaj duke frekuencën në të cilën ato shfaqen.

389
00:32:46,000 --> 00:32:51,180
Nëse ne shikojmë, shumica e tyre janë 0s përjashtim për këtë: H, të cilat duket se dy herë,

390
00:32:51,180 --> 00:32:54,820
dhe pastaj T, e cila duket një herë.

391
00:32:54,820 --> 00:33:07,860
Dhe atëherë këtu kemi mesazhin aktuale në 0s dhe 1s.

392
00:33:07,860 --> 00:33:15,450
Nëse ne shikojmë në hth.txt, e cila është me sa duket mesazhi origjinal që u huffed,

393
00:33:15,450 --> 00:33:22,490
ne presim të shohim disa HS dhe TS në atje.

394
00:33:22,490 --> 00:33:28,720
Në mënyrë të veçantë, ne presim të shohim vetëm 1 T dhe 2 HS.

395
00:33:32,510 --> 00:33:37,440
Këtu ne jemi në hth.txt. Ajo me të vërtetë ka HTH.

396
00:33:37,440 --> 00:33:41,270
Përfshira në atje, edhe pse ne nuk mund ta shohim atë, është një karakter newline.

397
00:33:41,270 --> 00:33:53,190
The hth.bin fotografi Huff është edhe kodimin karakterin si newline mirë.

398
00:33:55,680 --> 00:34:01,330
Këtu, sepse ne e dimë se qëllim është HTH dhe pastaj newline,

399
00:34:01,330 --> 00:34:07,340
ne mund shih se ndoshta H është përfaqësuara nga vetëm një 1 vetme

400
00:34:07,340 --> 00:34:17,120
dhe pastaj T është ndoshta 01 dhe pastaj H 1 tjetër është edhe

401
00:34:17,120 --> 00:34:21,139
dhe pastaj ne kemi një newline tregohet nga dy 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> Dhe pastaj në fund, sepse ne jemi që kanë të bëjnë me të. C shumta dhe. Fotografi h,

404
00:34:31,600 --> 00:34:36,350
ne do të ketë një argument mjaft kompleks për përpiluesit,

405
00:34:36,350 --> 00:34:40,460
dhe kështu që këtu ne kemi një Makefile që e bën hale për ju.

406
00:34:40,460 --> 00:34:47,070
Por në fakt, ju duhet të shkoni për të bërë vet dosjen tuaj puff.c.

407
00:34:47,070 --> 00:34:54,330
Makefile fakt nuk merret me bërjen e puff.c për ju.

408
00:34:54,330 --> 00:34:59,310
Ne jemi duke lënë që deri tek ju për të redaktuar Makefile.

409
00:34:59,310 --> 00:35:05,930
Kur ju shkruani një komandë si të bëjë të gjitha, për shembull, ajo do të bëjë të gjitha ato për ju.

410
00:35:05,930 --> 00:35:10,760
Ndjehen të lirë për të shikoni në shembujt e Makefile nga pset kaluar

411
00:35:10,760 --> 00:35:17,400
si plaste të këtë një të parë se si ju mund të jetë në gjendje të bëjë dosjen tuaj pudre

412
00:35:17,400 --> 00:35:20,260
nga redaktimi këtë Makefile.

413
00:35:20,260 --> 00:35:22,730
Kjo është në lidhje me atë për kodin tonë të shpërndarjes.

414
00:35:22,730 --> 00:35:28,380
>> Pasi kemi marrë përmes kësaj, atëherë këtu është vetëm një kujtesë

415
00:35:28,380 --> 00:35:30,980
se si ne jemi duke shkuar për të që kanë të bëjnë me nyje Huffman.

416
00:35:30,980 --> 00:35:35,400
Ne nuk do të jeni të duke i quajtur ato nyjet më, ne jemi duke shkuar për të bërë thirrje atyre pemëve

417
00:35:35,400 --> 00:35:39,260
ku ne jemi duke shkuar për të përfaqësuar simbolin e tyre me një char,

418
00:35:39,260 --> 00:35:43,340
frekuenca e tyre, numri i dukurive, me një numër të plotë.

419
00:35:43,340 --> 00:35:47,370
Ne jemi duke përdorur atë, sepse kjo është më e saktë se një noton.

420
00:35:47,370 --> 00:35:52,980
Dhe pastaj ne kemi një tjetër tregues për fëmijën e majtë, si dhe fëmijën e duhur.

421
00:35:52,980 --> 00:35:59,630
Një pyll, siç e pamë, është vetëm një listë e lidhur e pemëve.

422
00:35:59,630 --> 00:36:04,670
Në fund të fundit, kur ne jemi duke ndërtuar Huff dosjen tonë,

423
00:36:04,670 --> 00:36:07,580
ne duam pyjeve tona të përmbajë vetëm pemë 1 -

424
00:36:07,580 --> 00:36:12,420
1 pemë, 1 rrënjë me fëmijë të shumta.

425
00:36:12,420 --> 00:36:20,840
Më herët, kur ne ishim vetëm duke bërë pemë Huffman tona,

426
00:36:20,840 --> 00:36:25,360
kemi filluar nga vendosja të gjitha nyjet mbi ekranin tonë

427
00:36:25,360 --> 00:36:27,790
dhe duke thënë se ne do të kemi këto nyje,

428
00:36:27,790 --> 00:36:32,920
përfundimisht ata do të jenë gjethet, dhe kjo është simbol i tyre, kjo është frekuenca e tyre.

429
00:36:32,920 --> 00:36:42,070
Në pyll tonë nëse ne vetëm kemi 3 letra, që është një pyll prej 3 pemëve.

430
00:36:42,070 --> 00:36:45,150
Dhe pastaj si të shkojmë më, kur kemi shtuar prindin e parë,

431
00:36:45,150 --> 00:36:48,080
kemi bërë një pyll prej 2 pemë.

432
00:36:48,080 --> 00:36:54,930
Ne kemi hequr 2 të këtyre fëmijëve nga pylli tonë dhe pastaj e zëvendësoi atë me një nyje prind

433
00:36:54,930 --> 00:36:58,820
që kishin ato 2 nyjet si fëmijë.

434
00:36:58,820 --> 00:37:05,600
Dhe pastaj në fund, hapi ynë i fundit me marrjen shembullin tonë me AS, BS, dhe Cs

435
00:37:05,600 --> 00:37:08,030
do të jetë për të bërë prind përfundimtar,

436
00:37:08,030 --> 00:37:13,190
dhe kështu atëherë kjo do të sjellë akuzë tonë të plotë të pemëve në pyll për të 1.

437
00:37:13,190 --> 00:37:18,140
A të gjithë të shohim se si ju filloni me pemë të shumta në pyll tuaj

438
00:37:18,140 --> 00:37:22,520
dhe do të përfundojë me 1? Rregull. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Çfarë duhet të bëjmë për Puff?

440
00:37:28,110 --> 00:37:37,110
Ajo që ne duhet të bëni është të siguruar që, si gjithmonë, ata na japin të drejtën llojin e input

441
00:37:37,110 --> 00:37:39,090
kështu që ne mund të vërtetë të drejtuar programin.

442
00:37:39,090 --> 00:37:43,130
Në këtë rast ata do të na dhënë pas tyre argumentit të parë command-line

443
00:37:43,130 --> 00:37:53,440
2 më: fotografia që ne duam të shfryj dhe prodhimi i dosjes dekompresohen.

444
00:37:53,440 --> 00:38:00,410
Por pasi jemi të sigurt se ata na kalojë në shumën e duhur të vlerave,

445
00:38:00,410 --> 00:38:05,820
ne duam të siguruar që input është një file Huff apo jo.

446
00:38:05,820 --> 00:38:10,420
Dhe pastaj një herë ne garantojmë se kjo është një file Huff, atëherë ne duam të ndërtojmë pemë tonë,

447
00:38:10,420 --> 00:38:20,940
ndërtuar deri pemë të tillë që përputhet me pemën që personi që dërgoi mesazhin e ndërtuar.

448
00:38:20,940 --> 00:38:25,840
Pastaj pasi kemi ndërtuar pemë, atëherë ne mund të merren me, 0s dhe 1s që ata kaluan në

449
00:38:25,840 --> 00:38:29,590
ndjekin ato përgjatë pemës tonë, sepse ajo është e njëjtë,

450
00:38:29,590 --> 00:38:33,510
dhe pastaj shkruani këtë mesazh nga, interpretojnë bit përsëri në karaktere.

451
00:38:33,510 --> 00:38:35,880
Dhe pastaj në fund, sepse ne jemi që kanë të bëjnë me pointers këtu,

452
00:38:35,880 --> 00:38:38,110
ne duam të sigurohemi që ne nuk kemi asnjë rrjedhjet e kujtesës

453
00:38:38,110 --> 00:38:41,330
dhe se ne gjithçka falas.

454
00:38:42,820 --> 00:38:46,430
>> Sigurimi i përdorimit të duhur është e vjetruar për ne deri tani.

455
00:38:46,430 --> 00:38:51,980
Ne kemi marrë në një input, e cila do të jetë emri i file për të fryj,

456
00:38:51,980 --> 00:38:56,010
dhe pastaj ne të specifikojë një dalje,

457
00:38:56,010 --> 00:39:01,580
kështu emri i dosjes për dalje fryrë, i cili do të jetë skedar teksti.

458
00:39:03,680 --> 00:39:08,820
Kjo është përdorimi. Dhe tani ne duam të siguruar që input është huffed apo jo.

459
00:39:08,820 --> 00:39:16,420
Menduarit prapa, ishte atje asgjë në kodin e shpërndarjes që mund të na ndihmojë

460
00:39:16,420 --> 00:39:21,570
me të kuptuarit nëse një skedar është huffed apo jo?

461
00:39:21,570 --> 00:39:26,910
Ka pasur informacion në lidhje me huffile.c Huffeader.

462
00:39:26,910 --> 00:39:33,430
Ne e dimë se çdo fotografi Huff ka një Huffeader lidhur me atë me një numër magjik

463
00:39:33,430 --> 00:39:37,240
si dhe një grup i frekuencave për çdo simbol

464
00:39:37,240 --> 00:39:39,570
si edhe një cekimit.

465
00:39:39,570 --> 00:39:43,180
Ne e dimë se, por ne gjithashtu mori një vështrim në dump.c,

466
00:39:43,180 --> 00:39:49,120
në të cilën ai është lexuar në një skedar Huff.

467
00:39:49,120 --> 00:39:53,990
Dhe kështu për ta bërë këtë, ajo kishte për të kontrolluar nëse ajo me të vërtetë ishte huffed apo jo.

468
00:39:53,990 --> 00:40:03,380
Kështu që ndoshta ne mund të përdorim dump.c si një strukturë për puff.c. tonë

469
00:40:03,380 --> 00:40:12,680
Mbrapsht në pset 4 kur kemi pasur copy.c kopjuar file që në treshe RGB

470
00:40:12,680 --> 00:40:14,860
dhe ne interpretohet se për roman policor dhe resize,

471
00:40:14,860 --> 00:40:20,390
Në mënyrë të ngjashme, çfarë ju mund të bëni është të drejtuar vetëm komandën si cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
dhe përdorin disa të kodit atje.

473
00:40:23,600 --> 00:40:28,210
Megjithatë, kjo nuk do të jetë aq i hapur i një procesi

474
00:40:28,210 --> 00:40:33,010
për përkthimin dump.c tuaj në puff.c,

475
00:40:33,010 --> 00:40:36,160
por të paktën kjo ju jep një vend për të filluar

476
00:40:36,160 --> 00:40:40,540
si për të siguruar se input është huffed vërtetë apo jo

477
00:40:40,540 --> 00:40:43,240
si edhe disa gjëra të tjera.

478
00:40:45,930 --> 00:40:50,250
Ne kemi siguruar përdorimin e duhur dhe siguroi se input është huffed.

479
00:40:50,250 --> 00:40:53,570
Çdo herë që ne kemi bërë që kemi bërë kontrollin e duhur gabimi tonë,

480
00:40:53,570 --> 00:41:01,520
kështu që të kthehej dhe të ndalohet pirja e duhanit funksionin nëse disa dështimi ndodh, në qoftë se ka një problem.

481
00:41:01,520 --> 00:41:07,170
>> Tani ajo që ne duam të bëjmë është të ndërtojë pemën aktuale.

482
00:41:08,840 --> 00:41:12,640
Nëse ne shikojmë në pyll, ka 2 funksione kryesore

483
00:41:12,640 --> 00:41:15,800
që ne jemi duke shkuar për të duan të bëhen shumë të njohur me të.

484
00:41:15,800 --> 00:41:23,870
Ka bimë Boolean funksion që bimët jo-0 pemë frekuencave brenda pyllit tonë.

485
00:41:23,870 --> 00:41:29,250
Dhe kështu që nuk do të kalosh në një pointer në një pyll dhe një tregues për një pemë.

486
00:41:32,530 --> 00:41:40,340
Pyetje të shpejtë: Sa pyjet do të keni kur ju jeni ndërtimin e një pemë Huffman?

487
00:41:44,210 --> 00:41:46,650
Pylli ynë është si kanavacë tonë, apo jo?

488
00:41:46,650 --> 00:41:50,800
Pra, ne jemi vetëm do të ketë 1 pyll, por ne do të kemi pemë të shumta.

489
00:41:50,800 --> 00:41:57,590
Pra, para se të telefononi bimore, me sa duket ju jeni do të duan të bëjnë pyll tuaj.

490
00:41:57,590 --> 00:42:04,430
Nuk është një komandë për këtë në qoftë se ju shikoni në forest.h se si ju mund të bëni një pyll.

491
00:42:04,430 --> 00:42:09,270
Ju mund të mbjellësh një pemë. Ne e dimë se si ta bëjnë këtë.

492
00:42:09,270 --> 00:42:11,590
Dhe pastaj ju gjithashtu mund të marr një pemë nga pylli,

493
00:42:11,590 --> 00:42:17,540
heqjen e një pemë me peshë të ulët dhe duke ju dhënë tregues për këtë.

494
00:42:17,540 --> 00:42:23,090
Duke menduar përsëri në kur ne ishim duke bërë shembujt veten,

495
00:42:23,090 --> 00:42:27,980
kur ne u tërhequr atë jashtë, ne thjesht vetëm shtuar lidhjet.

496
00:42:27,980 --> 00:42:31,680
Por këtu në vend të vetëm duke shtuar lidhjet,

497
00:42:31,680 --> 00:42:40,630
të mendojnë për atë më shumë si ju jeni duke hequr 2 e atyre nyjave dhe pastaj duke e zëvendësuar atë me një tjetër.

498
00:42:40,630 --> 00:42:44,200
Të shprehur se në drejtim të ringjallet dhe mbjelljes,

499
00:42:44,200 --> 00:42:48,840
ju jeni picking 2 pemë dhe pastaj mbjelljen e një peme

500
00:42:48,840 --> 00:42:54,060
se ka 2 këto pemë që ju kap si fëmijë.

501
00:42:57,950 --> 00:43:05,280
Për të ndërtuar pemën Huffman, ju mund ta lexoni në simbolet dhe frekuencave në mënyrë

502
00:43:05,280 --> 00:43:10,790
sepse Huffeader jep se për ju,

503
00:43:10,790 --> 00:43:14,250
ju jep një rrjet të frekuencave.

504
00:43:14,250 --> 00:43:19,660
Kështu që ju mund të shkoni përpara dhe vetëm injorojnë asgjë me 0 në të

505
00:43:19,660 --> 00:43:23,760
sepse ne nuk duam 256 gjethet në fund të tij.

506
00:43:23,760 --> 00:43:27,960
Ne vetëm duam numrin e lë që janë karaktere

507
00:43:27,960 --> 00:43:31,600
që janë përdorur në të vërtetë në dosjen.

508
00:43:31,600 --> 00:43:37,590
Ju mund ta lexoni në këto simbole, dhe secili prej këtyre simboleve që kanë jo-0 frekuencave,

509
00:43:37,590 --> 00:43:40,440
ata do të jenë pemët.

510
00:43:40,440 --> 00:43:45,990
Çfarë ju mund të bëni është çdo herë që ju lexoni në një simbol jo-0 frekuencave,

511
00:43:45,990 --> 00:43:50,660
ju mund të mbjellë këtë pemë në pyll.

512
00:43:50,660 --> 00:43:56,620
Pasi të keni mbjellë pemë në pyll, ju mund të bashkohen këto pemë si vëllezërit e motrat,

513
00:43:56,620 --> 00:44:01,130
kështu do të kthehet në mbjelljen dhe ringjallet ku ju të vini 2 dhe pastaj bimore 1,

514
00:44:01,130 --> 00:44:05,820
ku se 1 se ju bimore është prind i 2 fëmijëve që keni zgjedhur.

515
00:44:05,820 --> 00:44:11,160
Pra, atëherë rezultati juaj në fund do të jetë një pemë të vetme në pyll tuaj.

516
00:44:16,180 --> 00:44:18,170
Kjo është se si ju të ndërtuar pemën tuaj.

517
00:44:18,170 --> 00:44:21,850
>> Ka disa gjëra që mund të shkojnë keq këtu

518
00:44:21,850 --> 00:44:26,580
sepse ne jemi që kanë të bëjnë me bërjen e pemëve të reja dhe kanë të bëjnë me pointers dhe gjëra si kjo.

519
00:44:26,580 --> 00:44:30,450
Para se kur ne u bëjmë me pointers,

520
00:44:30,450 --> 00:44:36,580
kurdo ne e kemi dashur malloc'd për t'u siguruar se ajo nuk u kthye ne një vlerë NULL akrep.

521
00:44:36,580 --> 00:44:42,770
Pra, në disa hapa në kuadër të këtij procesi nuk do të jetë disa raste

522
00:44:42,770 --> 00:44:45,920
ku programi juaj mund të dështojnë.

523
00:44:45,920 --> 00:44:51,310
Çfarë doni të bëni është që ju doni të bëni të sigurtë që ju të trajtojë ato gabime,

524
00:44:51,310 --> 00:44:54,580
dhe në spekulim ajo thotë se për të trajtuar ato gracefully,

525
00:44:54,580 --> 00:45:00,280
Pra, si të shtypura nga një mesazh për përdoruesit duke u thënë atyre pse programi ka për të lënë

526
00:45:00,280 --> 00:45:03,050
dhe pastaj menjëherë u largua atë.

527
00:45:03,050 --> 00:45:09,490
Për ta bërë këtë gabim trajtimin, mos harroni se ju doni të kontrolloni atë

528
00:45:09,490 --> 00:45:12,160
çdo herë të vetme që nuk mund të jetë një dështim.

529
00:45:12,160 --> 00:45:14,660
Çdo herë të vetme që ju jeni duke bërë një tregues të ri

530
00:45:14,660 --> 00:45:17,040
ju doni të bëni të sigurtë që kjo është e suksesshme.

531
00:45:17,040 --> 00:45:20,320
Para se çfarë kemi përdorur për të bëni është të bëjë një tregues të ri dhe malloc atë,

532
00:45:20,320 --> 00:45:22,380
dhe pastaj ne do të kontrolloni nëse ky tregues është NULL.

533
00:45:22,380 --> 00:45:25,670
Kështu që nuk do të jenë disa raste kur ju thjesht mund të bëni që,

534
00:45:25,670 --> 00:45:28,610
por ndonjëherë ju jeni në të vërtetë duke e quajtur një funksion

535
00:45:28,610 --> 00:45:33,100
dhe në atë funksion, kjo është ajo që e bën të mallocing.

536
00:45:33,100 --> 00:45:39,110
Në këtë rast, nëse ne shikojmë prapa në disa prej funksioneve brenda kodit,

537
00:45:39,110 --> 00:45:42,260
disa prej tyre janë funksione Boolean.

538
00:45:42,260 --> 00:45:48,480
Në rastin abstrakt qoftë se ne kemi një funksion Boolean quajtur foo,

539
00:45:48,480 --> 00:45:54,580
thelb, ne mund të supozojmë se përveç për të bërë çdo gjë që bën foo,

540
00:45:54,580 --> 00:45:57,210
pasi ajo është një funksion Boolean, ajo kthehet e vërtetë apo e rreme -

541
00:45:57,210 --> 00:46:01,300
vërtetë në qoftë se e suksesshme, false nëse jo.

542
00:46:01,300 --> 00:46:06,270
Pra, ne duam të kontrolloni nëse vlera kthimi i foo është e vërtetë apo e rreme.

543
00:46:06,270 --> 00:46:10,400
Nëse është e rreme, që do të thotë se ne do të duan për të shkruar një lloj mesazhi

544
00:46:10,400 --> 00:46:14,390
dhe pastaj mbaro programin.

545
00:46:14,390 --> 00:46:18,530
Ajo që ne duam të bëjmë është të kontrolloni vlerën e kthimit të foo.

546
00:46:18,530 --> 00:46:23,310
Nëse foo kthen false, atëherë ne e dimë që ne kemi hasur disa lloj të gabimit

547
00:46:23,310 --> 00:46:25,110
dhe ne kemi nevojë për të lënë programin tonë.

548
00:46:25,110 --> 00:46:35,600
Një mënyrë për të bërë këtë është të ketë një kusht, ku funksioni aktual në vetvete është gjendja juaj.

549
00:46:35,600 --> 00:46:39,320
Thuaj foo merr në x.

550
00:46:39,320 --> 00:46:43,390
Ne mund të kemi një gjendje si në qoftë se (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Në thelb, kjo do të thotë në qoftë se në fund të ekzekutimit foo ajo kthehet e vërtetë,

552
00:46:50,900 --> 00:46:57,390
atëherë ne mund të bëjmë këtë, sepse funksioni ka për të vlerësuar foo

553
00:46:57,390 --> 00:47:00,500
në mënyrë që të vlerësojë gjendjen e tërë.

554
00:47:00,500 --> 00:47:06,500
Kështu, pra, kjo është se si ju mund të bëni diçka nëse funksioni kthen vërtetë dhe është i suksesshëm.

555
00:47:06,500 --> 00:47:11,800
Por kur ju jeni duke kontrolluar gabim, ju vetëm duan të lënë në qoftë se funksioni juaj kthehet rreme.

556
00:47:11,800 --> 00:47:16,090
Çfarë ju mund të bëni është që vetëm të shtoni një == false ose thjesht të shtoni një zhurmë në frontin e tij

557
00:47:16,090 --> 00:47:21,010
dhe pastaj ju duhet në qoftë se (! foo).

558
00:47:21,010 --> 00:47:29,540
Brenda atij trupi i asaj kusht që ju do të ketë të gjitha të trajtimit të gabimit,

559
00:47:29,540 --> 00:47:36,940
Pra, si, "I pamundur krijimi i kësaj peme" dhe pastaj do të ktheheni 1 ose diçka të tillë.

560
00:47:36,940 --> 00:47:43,340
Atë që bën, megjithatë, është se edhe pse foo kthye false -

561
00:47:43,340 --> 00:47:46,980
Thuaj foo kthen vërtetë.

562
00:47:46,980 --> 00:47:51,060
Atëherë ju nuk keni për të thirrur foo përsëri. Kjo është një keqkuptim të përbashkët.

563
00:47:51,060 --> 00:47:54,730
Sepse ajo ishte në gjendjen tuaj, kjo është vlerësuar tashmë,

564
00:47:54,730 --> 00:47:59,430
kështu që ju tashmë keni rezultat në qoftë se ju jeni duke përdorur të bëni pemë ose diçka të tillë

565
00:47:59,430 --> 00:48:01,840
ose bimore ose të zgjedhë ose diçka.

566
00:48:01,840 --> 00:48:07,460
Ajo tashmë ka atë vlerë. Është ekzekutuar tashmë.

567
00:48:07,460 --> 00:48:10,730
Pra, kjo është e dobishme për t'u përdorur funksionet boolean si kusht

568
00:48:10,730 --> 00:48:13,890
sepse nëse janë apo jo ju në të vërtetë ekzekutuar trupin e lak,

569
00:48:13,890 --> 00:48:18,030
ajo ekzekuton funksionin anyway.

570
00:48:22,070 --> 00:48:27,330
>> Dytë jonë për hapin e fundit është shkruar mesazhin në dosjen.

571
00:48:27,330 --> 00:48:33,070
Pasi ne kemi ndërtuar pemën Huffman, atëherë shkruar mesazhin në dosjen është shumë i thjeshtë.

572
00:48:33,070 --> 00:48:39,260
Është shumë i thjeshtë tani për vetëm ndjekin 0s dhe 1s.

573
00:48:39,260 --> 00:48:45,480
Dhe kështu nga Konventa ne e dimë se në një pemë Huffman të 0s tregojnë la

574
00:48:45,480 --> 00:48:48,360
dhe 1s tregojnë drejtë.

575
00:48:48,360 --> 00:48:53,540
Prandaj, nëse keni lexuar në pak nga pak, çdo herë që ju të merrni një 0

576
00:48:53,540 --> 00:48:59,100
ju do të ndiqni degë e majtë, dhe pastaj çdo herë që ju lexoni në 1

577
00:48:59,100 --> 00:49:02,100
ju do të jeni të ndjekur degën e duhur.

578
00:49:02,100 --> 00:49:07,570
Dhe atëherë ju jeni do të vazhdojë deri sa ju goditi një fletë

579
00:49:07,570 --> 00:49:11,550
sepse gjethet do të jetë në fund të degëve.

580
00:49:11,550 --> 00:49:16,870
Si mund të thoni nëse ne kemi goditur një gjethe apo jo?

581
00:49:19,800 --> 00:49:21,690
Kemi thënë atë më parë.

582
00:49:21,690 --> 00:49:24,040
[Student] Nëse pointers janë NULL. Po >>.

583
00:49:24,040 --> 00:49:32,220
Ne mund të them nëse kemi goditur një gjethe nëse pointers në pemë dy majtë dhe të djathtë janë NULL.

584
00:49:32,220 --> 00:49:34,110
Përsosur.

585
00:49:34,110 --> 00:49:40,320
Ne e dimë që ne duam të lexuar në pak nga pak në Huff dosjen tonë.

586
00:49:43,870 --> 00:49:51,220
Siç e pamë më parë në dump.c, çfarë ata bënë është që ata lexojnë në pak nga pak në dosjen Huff

587
00:49:51,220 --> 00:49:54,560
dhe të shtypura vetëm se çfarë ata ishin bit.

588
00:49:54,560 --> 00:49:58,430
Ne nuk do të jeni të bërë këtë. Ne jemi duke shkuar për të bërë diçka që është pak më komplekse.

589
00:49:58,430 --> 00:50:03,620
Por ajo që mund të bëjmë është që ne mund të merrni atë grimë e kodit që lexon në të bit.

590
00:50:03,620 --> 00:50:10,250
Këtu kemi pak integer përfaqëson pak se tanishme ne jemi në.

591
00:50:10,250 --> 00:50:15,520
Kjo kujdeset iterating të gjitha bit në dosjen derisa ju goditi në fund të file.

592
00:50:15,520 --> 00:50:21,270
Bazuar në këtë, atëherë ju jeni do të duan që të ketë një lloj të iterator

593
00:50:21,270 --> 00:50:26,760
të kaloj nëpër pemë tuaj.

594
00:50:26,760 --> 00:50:31,460
Dhe pastaj në bazë të a pak është 0 ose 1,

595
00:50:31,460 --> 00:50:36,920
ju jeni do të duan të lëvizin qoftë se iterator në të majtë ose të lëvizin atë në të djathtë

596
00:50:36,920 --> 00:50:44,080
të gjithë rrugën deri sa ju goditi një fletë, në mënyrë që të gjithë rrugën deri në atë nyje që ju jeni në

597
00:50:44,080 --> 00:50:48,260
nuk tregojnë për ndonjë nyje shumë.

598
00:50:48,260 --> 00:50:54,300
Pse mund ta bëjmë këtë me një file Huffman por jo kodin Morse?

599
00:50:54,300 --> 00:50:56,610
Sepse në kodin Morse ka pak paqartësi.

600
00:50:56,610 --> 00:51:04,440
Ne mund të jetë si, Oh wait, ne kemi goditur një letër gjatë rrugës, kështu që ndoshta kjo është letra jonë,

601
00:51:04,440 --> 00:51:08,150
ndërsa nëse ne kemi vazhduar vetëm një pak më të gjatë, atëherë ne do të kemi goditur një tjetër letër.

602
00:51:08,150 --> 00:51:13,110
Por kjo nuk do të ndodhë në kodimin Huffman,

603
00:51:13,110 --> 00:51:17,540
kështu që ne mund të pushoni siguroi se mënyra e vetme që ne jemi duke shkuar për të goditur një karakter

604
00:51:17,540 --> 00:51:23,480
është nëse fëmijët e majtë dhe të djathtë se Nyja janë NULL.

605
00:51:28,280 --> 00:51:32,350
>> Së fundi, ne duam për të liruar të gjithë kujtesën tonë.

606
00:51:32,350 --> 00:51:37,420
Ne duam që të dy të mbyllur dosjen Huff që ne kemi qenë që kanë të bëjnë me

607
00:51:37,420 --> 00:51:41,940
si dhe për të hequr të gjitha pemëve në pyll tonë.

608
00:51:41,940 --> 00:51:46,470
Bazuar në implementimin tuaj, ju jeni me siguri do të duan të thërrasë hequr pyll

609
00:51:46,470 --> 00:51:49,780
në vend që të shkojnë të vërtetë nëpër të gjitha pemëve veten.

610
00:51:49,780 --> 00:51:53,430
Por në qoftë se keni bërë ndonjë pemë të përkohshme, ju do të dëshironi për të liruar atë.

611
00:51:53,430 --> 00:51:59,060
Ju e dini kodin tuaj më të mirë, kështu që ju e dini ku jeni alokimin e kujtesës.

612
00:51:59,060 --> 00:52:04,330
Dhe kështu që nëse ju shkoni në, të fillojnë, madje, Kontrollit F'ing për malloc,

613
00:52:04,330 --> 00:52:08,330
parë sa herë që ju malloc dhe duke e bërë të sigurtë që ju të liruar të gjithë se

614
00:52:08,330 --> 00:52:10,190
por vetëm atëherë kalon kodin tuaj,

615
00:52:10,190 --> 00:52:14,260
kuptuar ku ju mund të kanë ndarë kujtesës.

616
00:52:14,260 --> 00:52:21,340
Zakonisht ju mund të them vetëm, "Në fund të një skedar Unë jam vetëm duke shkuar për të hequr pyll në pyll tim",

617
00:52:21,340 --> 00:52:23,850
Pra, në thelb e qartë se kujtesa, pa se,

618
00:52:23,850 --> 00:52:28,310
"Dhe atëherë unë jam gjithashtu duke shkuar për të mbyllur dosjen dhe pastaj programi im do të lë".

619
00:52:28,310 --> 00:52:33,810
Por është se koha vetëm që programi juaj shpërblej?

620
00:52:33,810 --> 00:52:37,880
Jo, sepse nganjëherë nuk mund të ketë qenë një gabim që ka ndodhur.

621
00:52:37,880 --> 00:52:42,080
Ndoshta ne nuk mund të hapur një skedë ose ne nuk mund të bëjë një tjetër pemë

622
00:52:42,080 --> 00:52:49,340
ose disa lloj të gabimit ndodhur në procesin e alokimit të kujtesës dhe kështu ai u kthye NULL.

623
00:52:49,340 --> 00:52:56,710
Një gabim ka ndodhur dhe pastaj ne u kthye dhe u largua.

624
00:52:56,710 --> 00:53:02,040
Pra, atëherë ju doni të bëni të sigurtë që në çdo kohë të jetë e mundur që programi juaj mund të lë,

625
00:53:02,040 --> 00:53:06,980
ju doni për të liruar të gjithë kujtesën tuaj atje.

626
00:53:06,980 --> 00:53:13,370
Kjo nuk është vetëm do të jetë në fund të funksionit kryesor që ju lë kodin tuaj.

627
00:53:13,370 --> 00:53:20,780
Ju doni të shikoni përsëri në çdo rast se kodi juaj potencialisht mund të kthehen para kohe

628
00:53:20,780 --> 00:53:25,070
dhe pastaj të lirë çdo gjë që kujtesa bën kuptim.

629
00:53:25,070 --> 00:53:30,830
Thonë se ju kishte bërë thirrje të bëni pyll dhe që u kthye rreme.

630
00:53:30,830 --> 00:53:34,230
Atëherë ju ndoshta nuk do të duhet për të hequr pyllin tuaj

631
00:53:34,230 --> 00:53:37,080
sepse ju nuk keni një pyll ende.

632
00:53:37,080 --> 00:53:42,130
Por në çdo moment në kodin ku ju mund të kthehet para kohe

633
00:53:42,130 --> 00:53:46,160
ju doni të bëni të sigurtë që ju të liruar ndonjë kujtim të mundshme.

634
00:53:46,160 --> 00:53:50,020
>> Pra, kur ne jemi që kanë të bëjnë me çlirimin e kujtesës dhe rrjedhjet e mundshme që,

635
00:53:50,020 --> 00:53:55,440
ne duam që të mos përdorin vetëm gjykimin tonë dhe logjikën tonë

636
00:53:55,440 --> 00:54:01,850
por të përdorë gjithashtu edhe Shprehje për të përcaktuar nëse ne kemi liruar të gjithë kujtesën tonë siç duhet apo jo.

637
00:54:01,850 --> 00:54:09,460
Ju ose mund të kandidojë më Shprehje Puff dhe pastaj ju duhet gjithashtu të kalojë atë

638
00:54:09,460 --> 00:54:14,020
Numri drejta e command-line argumente për Shprehje.

639
00:54:14,020 --> 00:54:18,100
Ju mund të kandidojë atë, por prodhimi është pak fshehtë.

640
00:54:18,100 --> 00:54:21,630
Ne kemi marrë një grimë përdoret për atë me speller, por ne ende nevojë për ndihmë pak më shumë,

641
00:54:21,630 --> 00:54:26,450
kështu atëherë running atë me një pak më shumë flamuj si rrjedhje-check = plot,

642
00:54:26,450 --> 00:54:32,040
që ndoshta do të na jepni disa dalje më e dobishme për Shprehje.

643
00:54:32,040 --> 00:54:39,040
>> Pastaj një tjetër tip i dobishëm kur ju jeni debugging është komanda ndrysh.

644
00:54:39,040 --> 00:54:48,520
Ju mund të hyni në zbatimin e stafit e Huff, e drejtuar që në një skedar teksti,

645
00:54:48,520 --> 00:54:55,400
dhe pastaj atë të prodhimit një file binar binar, një fotografi Huff, të jenë specifike.

646
00:54:55,400 --> 00:54:59,440
Pastaj në qoftë se ju drejtuar duhmë tuaj në këtë dosje binar,

647
00:54:59,440 --> 00:55:03,950
pastaj ideale, dosja juaj outputted teksti do të jetë identike

648
00:55:03,950 --> 00:55:08,200
në një origjinal që kaloi in

649
00:55:08,200 --> 00:55:15,150
Këtu unë jam duke përdorur hth.txt si shembull, dhe kjo është një spekulim biseduar rreth në tuaj.

650
00:55:15,150 --> 00:55:21,040
Kjo është fjalë për fjalë vetëm HTH dhe pastaj një newline.

651
00:55:21,040 --> 00:55:30,970
Por patjetër të ndjehen të lirë dhe ju jeni të inkurajuar të përdorin patjetër shembuj më të gjatë

652
00:55:30,970 --> 00:55:32,620
për dosjen tuaj tekst.

653
00:55:32,620 --> 00:55:38,110
>> Ju mund të merrni edhe një e shtënë në ndoshta compressing dhe pastaj decompressing

654
00:55:38,110 --> 00:55:41,600
disa nga dosjet që keni përdorur në speller si Luftës dhe Paqes

655
00:55:41,600 --> 00:55:46,710
ose Jane Austen ose diçka të tillë - që do të jetë lloj i ftohtë - ose Kompetencat Austin,

656
00:55:46,710 --> 00:55:51,880
lloj të merret me fotografi të mëdha, sepse ne nuk do të vijë deri në atë

657
00:55:51,880 --> 00:55:55,590
nëse kemi përdorur mjet tjetër këtu, ls-l.

658
00:55:55,590 --> 00:56:01,150
Ne jemi përdorur për të ls, e cila në thelb listat të gjitha përmbajtjet në directory tonë të tanishëm.

659
00:56:01,150 --> 00:56:07,860
Kalimi në flamurin l-fakt tregon madhësinë e këtyre dosjeve.

660
00:56:07,860 --> 00:56:12,690
Nëse ju shkoni nëpër spekulim pset, në fakt ajo ecën ju nëpërmjet krijimit të file binar,

661
00:56:12,690 --> 00:56:16,590
e huffing atë, dhe ju të shihni se për fotografi shumë të vogla

662
00:56:16,590 --> 00:56:23,910
kostoja hapësira e compressing atë dhe përkthimin e të gjithë atë informacion

663
00:56:23,910 --> 00:56:26,980
të gjitha frekuencave dhe gjëra të tilla si që tejkalon përfitimi aktual

664
00:56:26,980 --> 00:56:30,000
i compressing skedarin në vend të parë.

665
00:56:30,000 --> 00:56:37,450
Por në qoftë se ju drejtuar atë në disa fotografi tekst më të gjatë, atëherë ju mund të shihni që ju të filloni të merrni disa përfitime

666
00:56:37,450 --> 00:56:40,930
në ato fotografi compressing.

667
00:56:40,930 --> 00:56:46,210
>> Dhe pastaj në fund, ne kemi vjetër Gdb tonë PAL, e cila është definitivisht do të jetë në dispozicion shumë.

668
00:56:48,360 --> 00:56:55,320
>> A kemi ndonjë pyetje në pemë Huff ose ndoshta për të bërë procesin e pemëve

669
00:56:55,320 --> 00:56:58,590
ose ndonjë pyetje të tjera mbi Puff Huff'n?

670
00:57:00,680 --> 00:57:02,570
Rregull. Unë do të qëndrojnë rreth e rrotull për një grimë.

671
00:57:02,570 --> 00:57:06,570
>> Faleminderit, të gjithë. Kjo ishte Walkthrough 6. Dhe fat të mirë.

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