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 - Università ta 'Harvard]

3
00:00:04,810 --> 00:00:07,240
[Dan huwa CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Hello, kulħadd, u jilqgħu għall Walkthrough 6: Puff Huff'n.

5
00:00:12,180 --> 00:00:17,440
Fil Puff Huff'n dak li qed nagħmlu se tkun jittrattaw ma 'fajl kompressata Huffman

6
00:00:17,440 --> 00:00:20,740
u mbagħad puffing lura up, hekk decompressing dan,

7
00:00:20,740 --> 00:00:25,810
sabiex inkunu nistgħu jittraduċu mill-0s u 1s li l-utent jibgħat magħna

8
00:00:25,810 --> 00:00:30,660
u jikkonvertu lura fit-test oriġinali.

9
00:00:30,660 --> 00:00:34,360
Pset 6 se tkun pjuttost jibred għaliex int ser tara xi wħud mill-għodod

10
00:00:34,360 --> 00:00:41,730
li inti użati fil pset 4 u pset 5 u tip ta 'jingħaqdu fis-1 kunċett pjuttost pulita

11
00:00:41,730 --> 00:00:43,830
meta inti tidħol għall taħseb dwarha.

12
00:00:43,830 --> 00:00:50,110
>> Ukoll, forsi, pset 4 u 5 kienu l-aktar ta 'sfida psets li aħna kellhom joffru.

13
00:00:50,110 --> 00:00:53,950
Allura minn issa, aħna għandna dan pset 1 aktar fis-C,

14
00:00:53,950 --> 00:00:56,480
u mbagħad wara li aħna qed dwar l-ipprogrammar tal-web.

15
00:00:56,480 --> 00:01:02,310
Allura nifirħu infuskom għall jkollna fuq il-hump aktar ħorox fid CS50.

16
00:01:03,630 --> 00:01:09,760
>> Nimxu fuq għal Puff Huff'n, għodda tagħna għal dan pset ser ikunu siġar Huffman,

17
00:01:09,760 --> 00:01:14,700
hekk fehim mhux biss kif binarja siġar xogħol iżda wkoll speċifikament siġar Huffman,

18
00:01:14,700 --> 00:01:16,240
kif dawn qed jinbnew.

19
00:01:16,240 --> 00:01:20,210
U allura aħna qed tmur biex ikollhom ħafna ta 'kodiċi ta' distribuzzjoni f'dan pset,

20
00:01:20,210 --> 00:01:22,480
u aħna ser jaslu biex tara li fil-fatt xi wħud mill-kodiċi

21
00:01:22,480 --> 00:01:24,670
aħna ma jista 'jkun kapaċi li jifhem bis-sħiħ għadu,

22
00:01:24,670 --> 00:01:30,080
u għalhekk dawn se jkunu l-fajls c., iżda mbagħad jakkumpanjawhom. tagħhom h fajls

23
00:01:30,080 --> 00:01:34,300
se tagħtina biżżejjed għarfien li għandna bżonn biex inkunu nafu kif dawk il-funzjonijiet tax-xogħol

24
00:01:34,300 --> 00:01:38,100
jew għall-inqas dak li suppost tagħmel - inputs u l-outputs tagħhom -

25
00:01:38,100 --> 00:01:40,760
anke jekk ma nafux x'inhu jiġri fil-kaxxa s-sewda

26
00:01:40,760 --> 00:01:44,090
jew ma jifhmux dak li qed jiġri fil-kaxxa s-sewda ġewwa.

27
00:01:44,090 --> 00:01:49,400
U mbagħad finalment, bħas-soltu, aħna qed jittrattaw ma 'strutturi ta' dejta ġodda,

28
00:01:49,400 --> 00:01:51,840
tipi speċifiċi ta 'għoqiedi li jindikaw ċerti affarijiet,

29
00:01:51,840 --> 00:01:56,080
u għalhekk hawn li jkollhom pinna u karta mhux biss għall-proċess tad-disinn

30
00:01:56,080 --> 00:01:58,470
u meta inti qed tipprova figura kif pset tiegħek għandha taħdem

31
00:01:58,470 --> 00:02:00,520
iżda wkoll matul debugging.

32
00:02:00,520 --> 00:02:06,140
Inti jista 'jkollhom GDB flimkien pinna tiegħek u l-karta waqt li tkun tieħu r liema l-valuri huma,

33
00:02:06,140 --> 00:02:09,320
fejn vleġeġ tiegħek huma tipponta, u affarijiet bħal dik.

34
00:02:09,320 --> 00:02:13,720
>> L-ewwel ejja nħarsu lejn siġar Huffman.

35
00:02:13,720 --> 00:02:19,600
Siġar Huffman huma siġar binarju, li jfisser li kull node għandha biss 2 tfal.

36
00:02:19,600 --> 00:02:24,870
Fl-siġar Huffman il-karatteristika hija li l-valuri l-aktar frekwenti

37
00:02:24,870 --> 00:02:27,140
huma rappreżentati mill-bits inqas.

38
00:02:27,140 --> 00:02:32,690
Rajna fl-eżempji lecture tal Morse code, li tip ta 'kkonsolidata xi ittri.

39
00:02:32,690 --> 00:02:38,030
Jekk inti qed tipprova biex tittraduċi xi A jew E, per eżempju,

40
00:02:38,030 --> 00:02:43,940
int traduzzjoni li ta 'spiss, u għalhekk minflok li jużaw is-sett sħiħ ta' bits

41
00:02:43,940 --> 00:02:48,640
allokat għal dak it-tip tad-data tas-soltu, inti kkompressat l-isfel għal inqas,

42
00:02:48,640 --> 00:02:53,730
u mbagħad dawn l-ittri li huma rappreżentati inqas ta 'spiss huma rappreżentati bil bits itwal

43
00:02:53,730 --> 00:02:59,840
għaliex inti tistax taffordja li meta inti iżen il-frekwenzi li dawn l-ittri jidhru.

44
00:02:59,840 --> 00:03:03,020
Għandna l-istess idea hawn siġar Huffman

45
00:03:03,020 --> 00:03:12,360
fejn aħna qed jagħmlu katina, tip ta 'triq biex jiksbu l-karattri ċerti.

46
00:03:12,360 --> 00:03:14,470
U allura l-karattri li jkollhom l-frekwenza aktar

47
00:03:14,470 --> 00:03:17,940
ser ikunu rappreżentati bl-bits inqas.

48
00:03:17,940 --> 00:03:22,020
>> Il-mod li inti tibni siġra Huffman

49
00:03:22,020 --> 00:03:27,430
huwa billi tpoġġi kollha tal-karattri li jidhru fit-test

50
00:03:27,430 --> 00:03:30,630
u l-kalkolu frekwenza tagħhom, kemm-il darba jidhru.

51
00:03:30,630 --> 00:03:33,880
Dan jista 'jkun jew għadd ta' kif ħafna drabi dawn l-ittri jidhru

52
00:03:33,880 --> 00:03:40,270
jew forsi persentaġġ ta 'barra ta' l-karattri kemm kull wieħed jidher.

53
00:03:40,270 --> 00:03:44,270
U hekk dak li għandek tagħmel hu li ladarba inti għandek kollha ta 'dak l fassal,

54
00:03:44,270 --> 00:03:49,060
allura inti tfittex l-frekwenzi 2 aktar baxx u mbagħad għaqqadhom bħala aħwa

55
00:03:49,060 --> 00:03:55,660
fejn allura l-node ġenitur għandu frekwenza li hija s-somma ta '2-tfal tagħha.

56
00:03:55,660 --> 00:04:00,870
U allura inti permezz tal-konvenzjoni tgħid li l-xellug node,

57
00:04:00,870 --> 00:04:03,770
inti ssegwi dan billi ssegwi l-fergħa 0,

58
00:04:03,770 --> 00:04:08,140
u allura l-node lemini hija l-fergħa 1.

59
00:04:08,140 --> 00:04:16,040
Kif rajna fil Morse code, il-gotcha wieħed kien li jekk kellek biss ħoss u l-ħoss

60
00:04:16,040 --> 00:04:18,120
kien ambigwu.

61
00:04:18,120 --> 00:04:22,430
Dan jista 'jkun jew 1 ittra jew jista' jkun sekwenza ta '2 ittri.

62
00:04:22,430 --> 00:04:27,790
U hekk dak Huffman siġar ma huwa minħabba fin-natura tal-karattri

63
00:04:27,790 --> 00:04:34,140
jew tagħna karattri attwali finali huma l-lymph aħħar fuq il-fergħa -

64
00:04:34,140 --> 00:04:39,300
nirreferu għal dawk kif weraq - bis-saħħa ta 'dak ma jistax ikun hemm xi ambigwità

65
00:04:39,300 --> 00:04:45,160
f'termini ta 'liema ittra qed tipprova encode mas-serje ta' bits

66
00:04:45,160 --> 00:04:50,670
għaliex imkien tul il-bits li jirrappreżentaw 1 ittra

67
00:04:50,670 --> 00:04:55,960
ser tiltaqa 'ma' ittra oħra kollha, u mhux se jkun hemm xi konfużjoni hemmhekk.

68
00:04:55,960 --> 00:04:58,430
Iżda aħna ser imorru fis eżempji li inti guys tista 'attwalment tara li

69
00:04:58,430 --> 00:05:02,120
minflok minna biss tghidlek li dan huwa veru.

70
00:05:02,120 --> 00:05:06,390
>> Ejja nħarsu lejn eżempju sempliċi ta 'siġra Huffman.

71
00:05:06,390 --> 00:05:09,380
I jkollhom string hawnhekk li huwa ta '12 karattri fit-tul.

72
00:05:09,380 --> 00:05:14,010
Għandi 4 Kif, 6 Bs, u 2 Cs.

73
00:05:14,010 --> 00:05:17,270
Ewwel pass tiegħi jkun li għadd.

74
00:05:17,270 --> 00:05:20,760
Kemm-il darba ma jidhirx A? Jidher 4 darbiet fis-sekwenza.

75
00:05:20,760 --> 00:05:25,060
B jidher 6 darbiet, u C jidher 2 darbiet.

76
00:05:25,060 --> 00:05:28,970
Naturalment, jien ser ngħid jien jużaw B-aktar spiss,

77
00:05:28,970 --> 00:05:35,970
hekk nixtieq li jirrappreżentaw B bl-inqas numru ta 'bits, l-inqas numru ta' 0s u 1s.

78
00:05:35,970 --> 00:05:42,600
U allura jien ukoll ser jistennew C li jeħtieġu l-aktar ammont ta '0s u 1s ukoll.

79
00:05:42,600 --> 00:05:48,550
L-ewwel dak li għamilt hawnhekk hija I mqiegħda f'ordni axxendenti f'termini ta 'frekwenza.

80
00:05:48,550 --> 00:05:52,710
Naraw li l-Ċ u l-A, dawn huma 2-frekwenzi tagħna aktar baxx.

81
00:05:52,710 --> 00:06:00,290
Aħna joħolqu node ġenitur, u li node ġenitur ma jkollu ittra assoċjat miegħu,

82
00:06:00,290 --> 00:06:05,070
iżda ma jkollu frekwenza, li hija s-somma.

83
00:06:05,070 --> 00:06:08,780
Is-somma isir 2 + 4, li hija 6.

84
00:06:08,780 --> 00:06:10,800
Imbagħad aħna isegwu l-fergħa tax-xellug.

85
00:06:10,800 --> 00:06:14,970
Jekk konna f'dak node 6, allura aħna isegwu 0 biex jiksbu C

86
00:06:14,970 --> 00:06:17,450
u mbagħad 1 sabiex insir A.

87
00:06:17,450 --> 00:06:20,300
Allura issa għandna 2 lymph.

88
00:06:20,300 --> 00:06:23,920
Għandna l-valur 6 u mbagħad aħna wkoll ieħor node mal-valur 6.

89
00:06:23,920 --> 00:06:28,550
U għalhekk dawn 2 huma mhux biss l-2 aktar baxx, iżda wkoll biss il-2 li jitħallew,

90
00:06:28,550 --> 00:06:33,820
hekk aħna jissieħbu dawk minn ieħor ġenitur, mas-somma li jkunu 12.

91
00:06:33,820 --> 00:06:36,300
Allura hawnhekk għandna siġra Huffman tagħna

92
00:06:36,300 --> 00:06:40,020
fejn tikseb sa B, li jkun biss il-bit 1

93
00:06:40,020 --> 00:06:45,430
u mbagħad sabiex insir A rridu naraw 01 u mbagħad C li jkollhom 00.

94
00:06:45,430 --> 00:06:51,300
Allura hawn naraw li bażikament aħna qed jirrappreżentaw dawn Chars ma '1 jew 2 bits

95
00:06:51,300 --> 00:06:55,160
fejn il-B, kif previst, għandha l-inqas.

96
00:06:55,160 --> 00:07:01,730
U allura kellna mistenni C li jkollhom l-aktar, iżda peress li huwa tali siġra Huffman żgħir,

97
00:07:01,730 --> 00:07:06,020
allura l-A hija wkoll rappreżentata minn 2 bits għall-kuntrarju x'imkien fin-nofs.

98
00:07:07,820 --> 00:07:11,070
>> Just jmorru fuq eżempju ieħor sempliċi tas-siġra Huffman,

99
00:07:11,070 --> 00:07:19,570
jiġifieri għandek l-sekwenza "Hello."

100
00:07:19,570 --> 00:07:25,360
Dak li għandek tagħmel huwa l-ewwel inti ngħid kif ħafna drabi ma H jidher f'dan?

101
00:07:25,360 --> 00:07:34,200
H tidher tidher e darba u mbagħad darba u mbagħad għandna l jidhru darbtejn

102
00:07:34,200 --> 00:07:36,580
u o jidhru darba.

103
00:07:36,580 --> 00:07:44,310
U hekk allura aħna nistennew li l-ittra li tkun rappreżentata mill-inqas numru ta 'bits?

104
00:07:44,310 --> 00:07:47,450
[Student] l. L >>. Yeah. l huwa dritt.

105
00:07:47,450 --> 00:07:50,730
Aħna nistennew l li tkun rappreżentata mill-inqas numru ta 'bits

106
00:07:50,730 --> 00:07:55,890
minħabba l tiġi użata l-aktar fil-sekwenza "Hello."

107
00:07:55,890 --> 00:08:04,280
Dak li jien ser tagħmel hu issa jiġbed out dawn in-nodi.

108
00:08:04,280 --> 00:08:15,580
Għandi 1, li hija H, u mbagħad ieħor 1, li huwa e, u mbagħad 1, li hija o -

109
00:08:15,580 --> 00:08:23,410
dritt issa jien tqegħid f'ordni tagħha - u mbagħad 2, li huwa l.

110
00:08:23,410 --> 00:08:32,799
Imbagħad I jiġifieri l-mod li jien jibnu siġra Huffman huwa li jinstabu l-lymph 2 mal-frekwenzi inqas

111
00:08:32,799 --> 00:08:38,010
u jagħmluhom aħwa billi toħloq node ġenitur.

112
00:08:38,010 --> 00:08:41,850
Hawnhekk għandna 3 lymph bl-inqas frekwenza. Huma qed kollha 1.

113
00:08:41,850 --> 00:08:50,620
Allura hawnhekk għandna jagħżlu liema waħda aħna qed tmur biex tagħmel link ewwel.

114
00:08:50,620 --> 00:08:54,850
Ejja ngħidu I jagħżlu l-H u l-e.

115
00:08:54,850 --> 00:09:01,150
Is-somma ta 1 + 1 huwa 2, iżda dan node ma jkollu ittra assoċjati magħha.

116
00:09:01,150 --> 00:09:04,440
Hija biss għandha l-valur.

117
00:09:04,440 --> 00:09:10,950
Issa aħna nħarsu lejn il-li jmiss 2 frekwenzi aktar baxxi.

118
00:09:10,950 --> 00:09:15,590
Dak 2 u 1. Dan jista 'jkun jew ta' dawk 2, iżda jien ser jagħżlu dan wieħed.

119
00:09:15,590 --> 00:09:18,800
Is-somma hija ta '3.

120
00:09:18,800 --> 00:09:26,410
U mbagħad finalment, I biss 2 xellug, hekk allura li ssir 5.

121
00:09:26,410 --> 00:09:32,010
Imbagħad hawn, kif mistenni, jekk I imla l-kodifikazzjoni għal dan,

122
00:09:32,010 --> 00:09:37,480
1s huma dejjem l-fergħa dritt u 0s l-waħda xellug.

123
00:09:37,480 --> 00:09:45,880
Imbagħad għandna l rappreżentata mill biss 1 daqsxejn u mbagħad lo bi 2

124
00:09:45,880 --> 00:09:52,360
u allura l-e minn 2 u allura l-H taqa isfel sa 3 bits.

125
00:09:52,360 --> 00:09:59,750
Allura inti tista 'tittrasmetti dan il-messaġġ "Hello" minflok attwalment jużaw il-karattri

126
00:09:59,750 --> 00:10:02,760
bi ftit 0s u 1s.

127
00:10:02,760 --> 00:10:07,910
Madankollu, ftakar li f'diversi każi kellna rabtiet ma 'frekwenzi tagħna.

128
00:10:07,910 --> 00:10:11,900
Aħna jista 'jkollhom jew ingħaqdu mal-H u lo 1 forsi.

129
00:10:11,900 --> 00:10:15,730
Jew imbagħad aktar tard meta kellna l-l rappreżentat minn 2

130
00:10:15,730 --> 00:10:19,410
kif ukoll l-magħquda 1 rappreżentata minn 2, jista 'jkollna konnessi jew wieħed.

131
00:10:19,410 --> 00:10:23,630
>> U hekk meta inti tibgħat l-0s u 1s, li attwalment ma tiggarantix

132
00:10:23,630 --> 00:10:27,090
li r-riċevitur tista 'kollox taqra messaġġ tiegħek dritt off BAT

133
00:10:27,090 --> 00:10:30,490
minħabba li dawn jistgħu ma jkunux jafu liema deċiżjoni tkun għamilt.

134
00:10:30,490 --> 00:10:34,920
Allura meta aħna qed jittrattaw ma 'kompressjoni Huffman,

135
00:10:34,920 --> 00:10:40,090
b'xi mod għandna biex tgħid min jirċievi l-messaġġ tagħna kif aħna iddeċieda -

136
00:10:40,090 --> 00:10:43,470
Dawn jeħtieġ li jkunu jafu xi tip ta 'informazzjoni addizzjonali

137
00:10:43,470 --> 00:10:46,580
minbarra l-messaġġ kompressata.

138
00:10:46,580 --> 00:10:51,490
Dawn jeħtieġ li jifhmu dak li l-siġra attwalment tidher qiesha,

139
00:10:51,490 --> 00:10:55,450
kif aħna attwalment magħmula dawn id-deċiżjonijiet.

140
00:10:55,450 --> 00:10:59,100
>> Hawnhekk konna biss tagħmel eżempji bbażati fuq l-għadd attwali,

141
00:10:59,100 --> 00:11:01,550
imma xi kultant tista 'wkoll ikollhom siġra Huffman

142
00:11:01,550 --> 00:11:05,760
ibbażata fuq il-frekwenza li fiha l-ittri jidhru, u huwa l-istess proċess eżatt.

143
00:11:05,760 --> 00:11:09,090
Hawnhekk jien jesprimuhom f'termini ta 'perċentwali jew frazzjoni,

144
00:11:09,090 --> 00:11:11,290
u għalhekk hawn l-istess ħaġa eżatt.

145
00:11:11,290 --> 00:11:15,300
I isibu l-2 aktar baxx, is-somma tagħhom, il-2 li jmiss l-aktar baxx, is-somma tagħhom,

146
00:11:15,300 --> 00:11:19,390
sakemm I jkollhom siġra sħiħa.

147
00:11:19,390 --> 00:11:23,610
Anki jekk aħna tista 'tagħmel dan jew mod, meta aħna qed jittrattaw ma' perċentwali,

148
00:11:23,610 --> 00:11:27,760
dan ifisser li aħna qed jiġi diviż l-affarijiet u jittrattaw deċimi jew aktar flowts

149
00:11:27,760 --> 00:11:30,900
jekk aħna qed jaħsbu dwar strutturi ta 'dejta ta' ras.

150
00:11:30,900 --> 00:11:32,540
Dak li nafu dwar flowts?

151
00:11:32,540 --> 00:11:35,180
X'hemm problema komuni meta aħna qed jittrattaw ma 'flowts?

152
00:11:35,180 --> 00:11:38,600
[Student] impreċiżi aritmetika. >> Yeah. Nuqqas ta 'preċiżjoni.

153
00:11:38,600 --> 00:11:43,760
Minħabba nuqqas ta 'preċiżjoni punt f'wiċċ l-ilma, għal dan pset sabiex nagħmlu ċert

154
00:11:43,760 --> 00:11:49,450
li aħna ma jitilfu ebda valur, allura aħna qed fil-fatt se jkunu jittrattaw l-għadd.

155
00:11:49,450 --> 00:11:54,880
Mela jekk ġejt biex jaħsbu ta 'node Huffman, jekk inti tħares lura lejn l-istruttura hawn,

156
00:11:54,880 --> 00:12:01,740
jekk inti tħares lejn dawk aħdar għandu frekwenza assoċjati miegħu

157
00:12:01,740 --> 00:12:08,760
kif ukoll li jindika node fuq ix-xellug tagħha kif ukoll node għad-dritt tiegħu.

158
00:12:08,760 --> 00:12:13,970
U allura dawk aħmar hemm ukoll karattru assoċjati magħhom.

159
00:12:13,970 --> 00:12:18,900
Aħna mhux se tagħmel dawk separati għall-ġenituri u allura l-lymph finali,

160
00:12:18,900 --> 00:12:23,680
li nirreferu għalih bħala weraq, iżda dawn se biss għandhom valuri NULL.

161
00:12:23,680 --> 00:12:31,050
Għal kull node aħna ser ikollhom karattru, is-simbolu li din node jirrappreżenta,

162
00:12:31,050 --> 00:12:40,490
imbagħad frekwenza kif ukoll pointer għat-tarbija xellug tiegħu kif ukoll wild dritt tiegħu.

163
00:12:40,490 --> 00:12:45,680
Il-weraq, li huma fil-qiegħ nett, ikollu wkoll indikazzjonijiet node

164
00:12:45,680 --> 00:12:49,550
għax-xellug u għal-lemin tagħhom, iżda peress li dawn il-valuri ma jkunux tipponta lejn lymph attwali,

165
00:12:49,550 --> 00:12:53,970
dak li l-valur tagħhom ikun? >> [Student] NULL. NULL. >> Eżattament.

166
00:12:53,970 --> 00:12:58,430
Hawn eżempju ta 'kif inti tista' tirrappreżenta l-frekwenza fil sufruni,

167
00:12:58,430 --> 00:13:02,130
imma aħna qed tmur biex tkun jittrattaw ma 'interi,

168
00:13:02,130 --> 00:13:06,780
għalhekk kull I ma hija l-bidla tat-tip tad-data hemmhekk.

169
00:13:06,780 --> 00:13:09,700
>> Ejja jmorru fuq għal ftit aktar ta 'eżempju kumpless.

170
00:13:09,700 --> 00:13:13,360
Imma issa li aħna ghamilt dawk sempliċi, huwa biss l-istess proċess.

171
00:13:13,360 --> 00:13:20,290
Inti issib il-frekwenzi 2-aktar baxx, is-somma tal-frekwenzi

172
00:13:20,290 --> 00:13:22,450
u dak l-ġdid għall-frekwenzi tar node ġenitur tiegħek,

173
00:13:22,450 --> 00:13:29,310
li mbagħad jindika xellug tagħha mal-fergħa 0 u d-dritt mal-fergħa 1.

174
00:13:29,310 --> 00:13:34,200
Jekk għandna l-sekwenza "Dan huwa cs50," allura aħna jgħoddu kif ħafna drabi huwa T msemmi,

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

176
00:13:38,420 --> 00:13:42,010
Imbagħad dak li għamilt hawnhekk huwa l-lymph aħmar I biss mħawla,

177
00:13:42,010 --> 00:13:48,530
I said jien ser ikollhom dawn il-karattri eventwalment fil-qiegħ ta 'siġra tiegħi.

178
00:13:48,530 --> 00:13:51,740
Dawk ser ikunu kollha tal-weraq.

179
00:13:51,740 --> 00:13:58,200
Imbagħad dak li għamilt huwa I magħżula minnhom skont il-frekwenza f'ordni axxendenti,

180
00:13:58,200 --> 00:14:02,950
u dan huwa effettivament il-mod li l-kodiċi pset tagħmlu

181
00:14:02,950 --> 00:14:07,550
huwa dan xorta huwa skond il-frekwenza u mbagħad alfabetikament.

182
00:14:07,550 --> 00:14:13,870
Għalhekk hija għandha n-numri ewwel u mbagħad alfabetikament mill-frekwenza.

183
00:14:13,870 --> 00:14:18,520
Imbagħad dak li nixtieq nagħmel huwa I se ssib l-aktar baxx 2. Dak 0 u 5.

184
00:14:18,520 --> 00:14:22,390
Nixtieq qosor minnhom, u li 2. Imbagħad I se tkompli, isibu l-jmiss 2 aktar baxx.

185
00:14:22,390 --> 00:14:26,100
Dawk huma l-1s tnejn, u mbagħad dawk isir 2 kif ukoll.

186
00:14:26,100 --> 00:14:31,570
Issa naf dak il-pass li jmiss tiegħi se tkun li tgħaqqad in-numru aktar baxx,

187
00:14:31,570 --> 00:14:41,380
li huwa l-T, il-1, u mbagħad jagħżlu waħda mill-lymph li għandha 2 bħala l-frekwenza.

188
00:14:41,380 --> 00:14:44,560
Allura hawnhekk għandna 3 għażliet.

189
00:14:44,560 --> 00:14:47,980
What jien ser tagħmel għall-slide hija biss viżwalment rranġati lilhom għalik

190
00:14:47,980 --> 00:14:51,790
sabiex inti tista 'tara kif jien tibniha.

191
00:14:51,790 --> 00:14:59,040
X'inhu l-kodiċi u l-kodiċi ta 'distribuzzjoni tiegħek se tagħmel huwa jkun jissieħbu fl-1 T

192
00:14:59,040 --> 00:15:01,410
ma 'l-node 0 u 5.

193
00:15:01,410 --> 00:15:05,060
Mela allura dak somom sa 3, u mbagħad aħna tkompli l-proċess.

194
00:15:05,060 --> 00:15:08,660
Il-2 u l-2 issa huma l-aktar baxx, u għalhekk allura dawk is-somma sa 4.

195
00:15:08,660 --> 00:15:12,560
Kulħadd wara s'issa? Okay.

196
00:15:12,560 --> 00:15:16,410
Imbagħad wara li għandna l-3 u l-3 li jeħtieġu li jiġu miżjuda,

197
00:15:16,410 --> 00:15:21,650
hekk darb'oħra jien biss switching hekk li inti tista 'tara viżwalment hekk li ma tikseb wisq messy.

198
00:15:21,650 --> 00:15:25,740
Imbagħad għandna 6, u mbagħad pass finali tagħna issa hija li aħna biss 2 nodi

199
00:15:25,740 --> 00:15:30,440
aħna somma dawk li jagħmlu l-għerq tal-siġra tagħna, li huwa 10.

200
00:15:30,440 --> 00:15:34,100
U n-numru 10 jagħmel sens għaliex kull node rappreżentati,

201
00:15:34,100 --> 00:15:40,750
il-valur tagħhom, in-numru frekwenza tagħhom, kien kif ħafna drabi dawn dehru fis-sekwenza,

202
00:15:40,750 --> 00:15:46,350
u allura għandna 5 karattri string tagħna, hekk li jagħmel sens.

203
00:15:48,060 --> 00:15:52,320
Jekk inħarsu lejn kif aħna up fil-fatt jikkodifikaw dan,

204
00:15:52,320 --> 00:15:56,580
kif mistenni, l-i u l-i, li jidhru l-aktar spiss

205
00:15:56,580 --> 00:16:01,350
huma rappreżentati mill-inqas numru ta 'bits.

206
00:16:03,660 --> 00:16:05,660
>> Oqgħod attent hawnhekk.

207
00:16:05,660 --> 00:16:09,780
Fl-siġar Huffman-każ attwalment kwistjonijiet.

208
00:16:09,780 --> 00:16:13,670
An S uppercase huwa differenti minn i zghar.

209
00:16:13,670 --> 00:16:21,260
Jekk kellna "Dan huwa CS50" ma 'ittri kapitali, allura l-i zghar biss tidher darbtejn,

210
00:16:21,260 --> 00:16:27,120
ikun node mal 2 bħala valur tagħha, u mbagħad uppercase S ikun biss darba.

211
00:16:27,120 --> 00:16:33,440
Mela allura siġra tiegħek se tinbidel strutturi għax inti fil-fatt ikollhom weraq żejda hawn.

212
00:16:33,440 --> 00:16:36,900
Iżda s-somma xorta jkun 10.

213
00:16:36,900 --> 00:16:39,570
Dak hu li aħna qed fil-fatt se tkun sejħa tal-checksum,

214
00:16:39,570 --> 00:16:44,060
iż-żieda ta 'kollha tal-għadd.

215
00:16:46,010 --> 00:16:50,990
>> Issa li konna koperti siġar Huffman, nistgħu adsa fis Puff Huff'n, il pset.

216
00:16:50,990 --> 00:16:52,900
Aħna ser tibda bil sezzjoni ta 'mistoqsijiet,

217
00:16:52,900 --> 00:16:57,990
u dan se tikseb inti mdorri bis-siġar binarji u kif joperaw madwar li:

218
00:16:57,990 --> 00:17:03,230
lymph tpinġija, ħolqien Struct typedef tiegħek stess għal node,

219
00:17:03,230 --> 00:17:07,230
u tara kif inti tista 'daħħal fis-siġra binarju, wieħed thats magħżula,

220
00:17:07,230 --> 00:17:09,050
traversat, u affarijiet bħal dik.

221
00:17:09,050 --> 00:17:14,560
Dan l-għarfien huwa definittivament se jgħinuk meta inti adsa fis-porzjon Puff Huff'n

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

223
00:17:19,150 --> 00:17:26,329
Fl-edizzjoni standard tal-pset, ix-xogħol tiegħek huwa li timplimenta Puff,

224
00:17:26,329 --> 00:17:30,240
u fil-verżjoni Hacker kompitu tiegħek huwa li jiġu implimentati Huff.

225
00:17:30,240 --> 00:17:38,490
X'inhu Huff ma huwa li jieħu test u mbagħad jittraduċi hija fil-0s u 1s,

226
00:17:38,490 --> 00:17:41,990
sabiex il-proċess li għamilna hawn fejn aħna magħduda l-frekwenzi

227
00:17:41,990 --> 00:17:50,970
u mbagħad isiru l-siġra u mbagħad qal, "Kif nista 'nikseb T?"

228
00:17:50,970 --> 00:17:54,840
T hija rappreżentata minn 100, affarijiet bħal dik,

229
00:17:54,840 --> 00:17:58,860
u mbagħad Huff kienet ser tieħu t-test u mbagħad output li binarja.

230
00:17:58,860 --> 00:18:04,920
Iżda wkoll għaliex aħna nafu li aħna rridu li jippermettu riċevitur tagħna tal-messaġġ

231
00:18:04,920 --> 00:18:11,790
jirrikreaw-siġra istess eżatt, din tinkludi wkoll informazzjoni dwar l-għadd ta 'frekwenzi.

232
00:18:11,790 --> 00:18:17,980
Imbagħad ma 'Puff aħna jingħataw fajl binarju ta 0s u 1s

233
00:18:17,980 --> 00:18:21,740
u minħabba wkoll l-informazzjoni dwar il-frekwenzi.

234
00:18:21,740 --> 00:18:26,740
Aħna tittraduċi dawk kollha lura 0s u 1s fil-messaġġ oriġinali li kien,

235
00:18:26,740 --> 00:18:29,350
hekk aħna qed decompressing dan.

236
00:18:29,350 --> 00:18:36,450
Jekk inti qed tagħmel l-edizzjoni standard, inti m'għandekx bżonn biex jimplimentaw Huff,

237
00:18:36,450 --> 00:18:39,290
iva allura inti tista 'biss tuża l-implimentazzjoni tal-persunal ta' Huff.

238
00:18:39,290 --> 00:18:42,080
Hemm struzzjonijiet fil-spec dwar kif jagħmlu dan.

239
00:18:42,080 --> 00:18:48,780
Inti tista 'taħdem l-implimentazzjoni tal-persunal ta Huff fuq fajl test ċerta

240
00:18:48,780 --> 00:18:53,270
u mbagħad jużaw dak l-output bħala input tiegħek biex Puff.

241
00:18:53,270 --> 00:18:59,330
>> Kif semmejt qabel, għandna ħafna ta 'kodiċi ta' distribuzzjoni għal dan wieħed.

242
00:18:59,330 --> 00:19:01,810
Jien ser tibda għaddejja minn ġo fih.

243
00:19:01,810 --> 00:19:04,400
Jien ser jonfqu l-aktar tal-ħin fuq il-. Fajls h

244
00:19:04,400 --> 00:19:07,660
minħabba li fil-fajls c., għaliex għandna l-h.

245
00:19:07,660 --> 00:19:11,650
u li tagħtina l-prototipi tal-funzjonijiet,

246
00:19:11,650 --> 00:19:15,520
aħna ma kollox jeħtieġ li jifhmu eżattament -

247
00:19:15,520 --> 00:19:20,280
Jekk ma tifhimx x'inhu għaddej fil-fajls c., Allura ma jinkwetaw wisq,

248
00:19:20,280 --> 00:19:23,600
iżda definittivament tipprova tagħti ħarsa għaliex din tista 'tagħti xi ideat

249
00:19:23,600 --> 00:19:29,220
u huwa utli li jidraw qari kodiċi nies oħrajn.

250
00:19:38,940 --> 00:19:48,270
>> Ħarsa lejn huffile.h, fil-kummenti li tiddikjara saff ta 'estrazzjoni għall Huffman-coded fajls.

251
00:19:48,270 --> 00:20:01,660
Jekk aħna jinżlu, naraw li hemm massimu ta '256 simboli li għandna jistgħu jeħtieġu kodiċi għall.

252
00:20:01,660 --> 00:20:05,480
Dan jinkludi l-ittri tal-alfabett - uppercase u zghar -

253
00:20:05,480 --> 00:20:08,250
u mbagħad simboli u numri, eċċ

254
00:20:08,250 --> 00:20:11,930
Imbagħad hawnhekk għandna numru magic tidentifika fajl Huffman-coded.

255
00:20:11,930 --> 00:20:15,890
Fi ħdan kodiċi Huffman dawn qed tmur biex ikollhom numru magic ċertu

256
00:20:15,890 --> 00:20:18,560
assoċjati mal-header.

257
00:20:18,560 --> 00:20:21,110
Dan jista 'dehra biss numru magic każwali,

258
00:20:21,110 --> 00:20:27,160
imma jekk inti fil-fatt din tissarraf f'azzjoni ASCII, allura fil-fatt tispjega l Huff.

259
00:20:27,160 --> 00:20:34,290
Hawnhekk għandna Struct għal fajl Huffman-encoded.

260
00:20:34,290 --> 00:20:39,670
Hemm kollha ta 'dawn il-karatteristiċi assoċjati ma' fajl Huff.

261
00:20:39,670 --> 00:20:47,080
Imbagħad stabbiliti hawn għandna l-header għal fajl Huff, hekk aħna sejħa hija Huffeader

262
00:20:47,080 --> 00:20:50,810
minflok ma żżid il-h żejda għaliex ħsejjes l-istess xorta waħda.

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

264
00:20:52,720 --> 00:20:57,790
Għandna numru magic assoċjati magħha.

265
00:20:57,790 --> 00:21:09,040
Jekk huwa fajl Huff attwali, li għaddej biex jkun in-numru ta 'hawn fuq, dan wieħed magic.

266
00:21:09,040 --> 00:21:14,720
U allura se jkollhom firxa.

267
00:21:14,720 --> 00:21:18,750
Allura għal kull simbolu, li minnhom hemm 256,

268
00:21:18,750 --> 00:21:24,760
li għaddej biex lista dak l-frekwenza ta 'dawn is-simboli huma fil-fajl Huff.

269
00:21:24,760 --> 00:21:28,090
U mbagħad finalment, aħna għandna checksum għall-frekwenzi,

270
00:21:28,090 --> 00:21:32,160
li għandu jkun is-somma ta 'dawk il-frekwenzi.

271
00:21:32,160 --> 00:21:36,520
Allura dak hu li l-Huffeader hu.

272
00:21:36,520 --> 00:21:44,600
Imbagħad għandna xi funzjonijiet li jirritornaw il-ftit li jmiss fil-fajl Huff

273
00:21:44,600 --> 00:21:52,580
kif ukoll jikteb daqsxejn għall-fajl Huff, u mbagħad din il-funzjoni hawn, hfclose,

274
00:21:52,580 --> 00:21:54,650
li attwalment jarkivja l-fajl Huff.

275
00:21:54,650 --> 00:21:57,290
Qabel, konna jittrattaw dritta biss fclose,

276
00:21:57,290 --> 00:22:01,190
imma meta jkollok fajl Huff, minflok fclosing dan

277
00:22:01,190 --> 00:22:06,080
dak li int fil-fatt se tagħmel hu hfclose u hfopen dan.

278
00:22:06,080 --> 00:22:13,220
Dawk huma funzjonijiet speċifiċi għall-fajls Huff li aħna qed tmur biex tkun jittrattaw.

279
00:22:13,220 --> 00:22:19,230
Imbagħad hawn naqraw fil-header u mbagħad jiktbu l-header.

280
00:22:19,230 --> 00:22:25,700
>> Biss mill-qari tal-fajl h. Nistgħu tip ta tikseb sens ta 'dak fajl Huff jista' jkun,

281
00:22:25,700 --> 00:22:32,480
liema karatteristiċi għandu, mingħajr ma attwalment għaddejjin fil-huffile.c,

282
00:22:32,480 --> 00:22:36,750
li, jekk aħna adsa fi, se tkun daqsxejn aktar kumplessa.

283
00:22:36,750 --> 00:22:41,270
Dan għandu l-fajl I / O hawn jittrattaw pointers.

284
00:22:41,270 --> 00:22:48,010
Hawnhekk naraw li meta nagħmlu sejħa hfread, per eżempju, huwa għadu jittrattaw fread.

285
00:22:48,010 --> 00:22:53,050
Aħna ma jwarrbu dawk il-funzjonijiet kollox, iżda aħna qed jibgħat dawk li għandhom jittieħdu kura ta '

286
00:22:53,050 --> 00:22:59,760
ġewwa l-fajl Huff minflok tagħmel kollha ta 'dan nfusna.

287
00:22:59,760 --> 00:23:02,300
Tista 'tħossok liberu li scan permezz ta' dan jekk int kurjuż

288
00:23:02,300 --> 00:23:08,410
u mur u titqaxxar il-saff lura ftit.

289
00:23:20,650 --> 00:23:24,060
>> Il-fajl li jmiss li aħna qed tmur biex tħares lejn huwa tree.h.

290
00:23:24,060 --> 00:23:30,210
Qabel fil-Walkthrough pjastri għidna aħna nistennew node Huffman

291
00:23:30,210 --> 00:23:32,960
u għamilna node Struct typedef.

292
00:23:32,960 --> 00:23:38,360
Aħna nistennew li jkollhom simbolu, frekwenza, u mbagħad istilel node 2.

293
00:23:38,360 --> 00:23:41,870
F'dan il-każ dak li aħna qed tagħmel huwa dan huwa essenzjalment l-istess

294
00:23:41,870 --> 00:23:46,880
ħlief minflok node aħna qed tmur li jsejħu lilhom siġar.

295
00:23:48,790 --> 00:23:56,760
Għandna funzjoni li meta inti sejħa tagħmel siġra dan jirritorna inti pointer siġra.

296
00:23:56,760 --> 00:24:03,450
Back li speller, meta inti kienu qed jagħmlu node ġdid

297
00:24:03,450 --> 00:24:11,410
inti qal node * kelma ġdida = malloc (sizeof) u affarijiet bħal dik.

298
00:24:11,410 --> 00:24:17,510
Bażikament, mktree se jkunu jittrattaw dan għalik.

299
00:24:17,510 --> 00:24:20,990
Bl-istess mod, meta inti tixtieq li tneħħi siġra,

300
00:24:20,990 --> 00:24:24,810
b'tali mod li s essenzjalment tillibera l-siġra meta qed isir ma 'dan,

301
00:24:24,810 --> 00:24:33,790
minflok espliċitament sejħa b'xejn fuq dan, int fil-fatt biss ser tuża l-funzjoni rmtree

302
00:24:33,790 --> 00:24:40,360
fejn inti tgħaddi fil-pointer għal dak siġra u mbagħad tree.c se jieħdu ħsieb ta 'dak għalik.

303
00:24:40,360 --> 00:24:42,490
>> Aħna nħarsu fis tree.c.

304
00:24:42,490 --> 00:24:47,240
Aħna nistennew l-istess funzjonijiet, ħlief biex tara d-implimentazzjoni kif ukoll.

305
00:24:47,240 --> 00:24:57,720
Kif aħna mistennija, meta inti sejħa mktree hija mallocs-daqs ta 'siġra fi pointer,

306
00:24:57,720 --> 00:25:03,190
initializes kollha tal-valuri tal-valur NULL, hekk 0s jew NULLs,

307
00:25:03,190 --> 00:25:08,280
u mbagħad jirritorna l-pointer għal dak siġra li inti stajt biss malloc'd lilek.

308
00:25:08,280 --> 00:25:13,340
Hawnhekk meta inti sejħa tneħħi siġra l-ewwel jagħmel żgur li int mhux doppja ħelsien.

309
00:25:13,340 --> 00:25:18,320
Hija tagħmel ċert li inti fil-fatt ikollhom siġra li inti tixtieq li tneħħi.

310
00:25:18,320 --> 00:25:23,330
Hawnhekk għaliex siġra jinkludi wkoll it-tfal tiegħu,

311
00:25:23,330 --> 00:25:29,560
dak li dan ma huwa recursively jitlob tneħħi siġra fuq il-node xellug tal-siġra

312
00:25:29,560 --> 00:25:31,650
kif ukoll il-node dritt.

313
00:25:31,650 --> 00:25:37,790
Qabel ma jillibera l-ġenitur, jeħtieġ li tilliberalizza t-tfal ukoll.

314
00:25:37,790 --> 00:25:42,770
Parent hija wkoll interskambjabbli ma għerq.

315
00:25:42,770 --> 00:25:46,500
Il-ġenitur qatt ewwel, hekk bħall-kbira-kbira-kbira-great-grandfather

316
00:25:46,500 --> 00:25:52,130
jew siġra nanna, l-ewwel għandna biex ħielsa l-livelli l-ewwel.

317
00:25:52,130 --> 00:25:58,490
Allura travers il-qiegħ, ħielsa dawk, u mbagħad jiġu lura up, free dawk, eċċ

318
00:26:00,400 --> 00:26:02,210
Allura dak siġra.

319
00:26:02,210 --> 00:26:04,240
>> Issa nħarsu lejn foresti.

320
00:26:04,240 --> 00:26:09,860
Foresti huwa fejn inti post kollha ta 'siġar Huffman tiegħek.

321
00:26:09,860 --> 00:26:12,910
Huwa qal li aħna qed tmur biex ikollhom xi ħaġa imsejħa plott

322
00:26:12,910 --> 00:26:22,320
li fih pointer għal siġra kif ukoll pointer ma 'plot imsejjaħ jmiss.

323
00:26:22,320 --> 00:26:28,480
Liema istruttura ma dan it-tip ta look like?

324
00:26:29,870 --> 00:26:32,490
Huwa tip ta 'jgħid li hemmhekk.

325
00:26:34,640 --> 00:26:36,700
Dritt hawn fuq.

326
00:26:37,340 --> 00:26:39,170
A marbut lista.

327
00:26:39,170 --> 00:26:44,590
Naraw li meta għandna plott huwa simili lista marbuta ta 'plottijiet.

328
00:26:44,590 --> 00:26:53,020
A foresti hija definita bħala lista marbuta ta 'plottijiet,

329
00:26:53,020 --> 00:26:58,100
u għalhekk l-istruttura tal-foresti hija li aħna qed biss se jkollhom pointer biex plot ewwel tagħna

330
00:26:58,100 --> 00:27:02,740
u li plot għandha siġra fih jew jindika pjuttost il siġra

331
00:27:02,740 --> 00:27:06,190
u mbagħad jindika l-plott li jmiss, hekk u ibqa 'sejjer hekk.

332
00:27:06,190 --> 00:27:11,100
Biex tagħmel foresta nitolbu mkforest.

333
00:27:11,100 --> 00:27:14,930
Imbagħad għandna xi funzjonijiet pretty utli hawn.

334
00:27:14,930 --> 00:27:23,240
Aħna pick fejn inti tgħaddi fil-foresti u allura l-valur tar-ritorn hija * Tree,

335
00:27:23,240 --> 00:27:25,210
pointer ma 'siġra.

336
00:27:25,210 --> 00:27:29,370
Liema pick se tagħmel huwa se jmorru fil-foresti li int tipponta lejn

337
00:27:29,370 --> 00:27:35,240
imbagħad neħħi siġra bl-inqas frekwenza minn dak tal-foresti

338
00:27:35,240 --> 00:27:38,330
u mbagħad jagħtuk l-pointer għal dak siġra.

339
00:27:38,330 --> 00:27:43,030
Ladarba inti sejħa pick, is-siġra ma tkunx teżisti fil-foresti aktar,

340
00:27:43,030 --> 00:27:48,550
iżda l-valur tar-ritorn hija l-pointer għal dak siġra.

341
00:27:48,550 --> 00:27:50,730
Imbagħad għandek pjanti.

342
00:27:50,730 --> 00:27:57,420
Iżda inti tgħaddi fil-pointer ma 'siġra li għandu frekwenza mhux-0,

343
00:27:57,420 --> 00:28:04,040
liema impjant se tagħmel huwa se tieħu l-foresti, jieħdu l-siġra, u pjanti li ġewwa siġra tal-foresta.

344
00:28:04,040 --> 00:28:06,370
Hawnhekk għandna rmforest.

345
00:28:06,370 --> 00:28:11,480
Simili biex jitneħħew siġra, li bażikament meħlusa kollha ta 'siġar tagħna għalina,

346
00:28:11,480 --> 00:28:16,600
neħħi foresti se kollox ħielsa li tinsab f'dak l-foresti.

347
00:28:16,600 --> 00:28:24,890
>> Jekk nagħtu ħarsa lejn forest.c, aħna ser nistennew li naraw mill-inqas 1 kmand rmtree fil hemm,

348
00:28:24,890 --> 00:28:30,090
minħabba li memorja ħielsa fil-foresta jekk foresta għandha siġar fiha,

349
00:28:30,090 --> 00:28:32,930
imbagħad eventwalment int ser ikollhom biex jitneħħew dawk is-siġar wisq.

350
00:28:32,930 --> 00:28:41,020
Jekk nagħtu ħarsa lejn forest.c, għandna mkforest tagħna, li huwa kif aħna nistennew.

351
00:28:41,020 --> 00:28:42,890
Aħna malloc affarijiet.

352
00:28:42,890 --> 00:28:51,740
Aħna initialize-plott ewwel fil-foresta bħala NULL, għaliex dan huwa vojt biex jibdew,

353
00:28:51,740 --> 00:29:05,940
allura naraw pick, li jirritorna l-siġra bil-piż aktar baxx, il-frekwenza baxxa,

354
00:29:05,940 --> 00:29:13,560
u mbagħad gets rid ta 'dak node partikolari li jindika li l-siġra u l-1 li jmiss,

355
00:29:13,560 --> 00:29:16,760
hekk li tieħu l barra mill-lista marbuta tal-foresta.

356
00:29:16,760 --> 00:29:24,510
U allura hawnhekk għandna impjant, li tintroduċi siġra fil-lista marbuta.

357
00:29:24,510 --> 00:29:29,960
X'inhu foresti ma huwa nicely jżommu magħżula għalina.

358
00:29:29,960 --> 00:29:37,910
U mbagħad finalment, għandna rmforest u, kif mistenni, għandna rmtree imsejħa hemmhekk.

359
00:29:46,650 --> 00:29:55,440
>> Ħarsa lejn il-kodiċi tad-distribuzzjoni s'issa huffile.c kien probabbilment bil-bosta l-aktar diffiċli li wieħed jifhem,

360
00:29:55,440 --> 00:29:59,990
billi l-fajls l-oħra nfushom kienu pjuttost sempliċi biex isegwu.

361
00:29:59,990 --> 00:30:03,090
Bl-għarfien tagħna ta 'pointers u listi marbuta u bħal dawn,

362
00:30:03,090 --> 00:30:04,860
konna kapaċi jsegwu pretty ukoll.

363
00:30:04,860 --> 00:30:10,500
Imma kollha għandna bżonn li verament tagħmel ċert li aħna jifhmu bis-sħiħ huwa l-. H fajls

364
00:30:10,500 --> 00:30:15,840
għaliex inti jeħtieġ li tkun sejħa dawk il-funzjonijiet, li jittrattaw ma 'dawk il-valuri ta' ritorn,

365
00:30:15,840 --> 00:30:20,590
sabiex tagħmel ċert li inti tifhem kompletament liema azzjoni tkun se ssir

366
00:30:20,590 --> 00:30:24,290
kull meta inti sejħa waħda minn dawk il-funzjonijiet.

367
00:30:24,290 --> 00:30:33,020
Imma fil-fatt fehim ġewwa ta 'dan huwa pjuttost mhux meħtieġ għaliex għandna dawn. Fajls h.

368
00:30:35,170 --> 00:30:39,490
We have 2 aktar fajls jitħalla fil-kodiċi ta 'distribuzzjoni tagħna.

369
00:30:39,490 --> 00:30:41,640
>> Ejja nħarsu lejn dump.

370
00:30:41,640 --> 00:30:47,230
Dump mill-kumment tagħha hawn tieħu fajl Huffman-kompressata

371
00:30:47,230 --> 00:30:55,580
u mbagħad jittraduċi u tarmi l-kontenut tagħha barra.

372
00:31:01,010 --> 00:31:04,260
Hawnhekk naraw li l-sejħa hfopen.

373
00:31:04,260 --> 00:31:10,770
Dan huwa tip ta 'mera ghal-fajl * input = fopen,

374
00:31:10,770 --> 00:31:13,500
u allura inti jgħaddu fl-informazzjoni.

375
00:31:13,500 --> 00:31:18,240
Huwa kważi identiċi minbarra minflok * fajl int tgħaddi fil-Huffile;

376
00:31:18,240 --> 00:31:22,030
minflok fopen int tgħaddi fil hfopen.

377
00:31:22,030 --> 00:31:29,280
Hawnhekk naqraw fl-intestatura 1, li huwa tip ta simili għal kif naqraw fil-header

378
00:31:29,280 --> 00:31:33,580
għal fajl Bitmap.

379
00:31:33,580 --> 00:31:38,000
Dak li aħna qed tagħmel hawn qed jiċċekkja biex tara jekk l-informazzjoni header

380
00:31:38,000 --> 00:31:44,330
fih in-numru magic dritt li jindika li huwa ta 'fajl Huff attwali,

381
00:31:44,330 --> 00:31:53,610
allura kollha ta 'dawn il-kontrolli biex tiżgura li l-fajl li aħna miftuħa huwa fajl huffed attwali jew le.

382
00:31:53,610 --> 00:32:05,330
X'inhu dan ma huwa outputs il-frekwenzi kollha ta 'l-simboli li nistgħu naraw

383
00:32:05,330 --> 00:32:09,790
fi terminal fis-tabella grafika.

384
00:32:09,790 --> 00:32:15,240
Din il-parti se tkun utli.

385
00:32:15,240 --> 00:32:24,680
Hija għandha ftit u jaqra ftit ftit fil-ftit varjabbli u mbagħad stampi dan jitwettaq.

386
00:32:28,220 --> 00:32:35,430
Mela jekk jien kellhom sejħa dump fuq hth.bin, li hija r-riżultat ta huffing 'fajl

387
00:32:35,430 --> 00:32:39,490
tuża s-soluzzjoni tal-persunal, nixtieq nikseb dan.

388
00:32:39,490 --> 00:32:46,000
Huwa outputting kollha ta 'dawn il-karattri u mbagħad tqegħid l-frekwenza li fiha għandhom jidhru.

389
00:32:46,000 --> 00:32:51,180
Jekk nagħtu ħarsa, ħafna minnhom huma 0s ħlief għal dan: H, li jidher darbtejn,

390
00:32:51,180 --> 00:32:54,820
u mbagħad T, li tidher darba.

391
00:32:54,820 --> 00:33:07,860
U allura hawnhekk għandna l-messaġġ attwali fil 0s u 1s.

392
00:33:07,860 --> 00:33:15,450
Jekk inħarsu lejn hth.txt, li huwa preżumibbilment l-messaġġ oriġinali li kien huffed,

393
00:33:15,450 --> 00:33:22,490
aħna nistennew li naraw xi Hs u Ts fil hemmhekk.

394
00:33:22,490 --> 00:33:28,720
Speċifikament, aħna nistennew li naraw biss 1 T u 2 Hs.

395
00:33:32,510 --> 00:33:37,440
Hawnhekk aħna fil hth.txt. Hija fil-fatt għandha HTH.

396
00:33:37,440 --> 00:33:41,270
Inklużi fil hemm, għalkemm aħna ma tistax tara dan, huwa karattru newline.

397
00:33:41,270 --> 00:33:53,190
Il hth.bin fajl Huff hija wkoll kodifikazzjoni-karattru newline ukoll.

398
00:33:55,680 --> 00:34:01,330
Hawnhekk għaliex aħna nafu li l-ordni hija HTH u mbagħad newline,

399
00:34:01,330 --> 00:34:07,340
nistgħu naraw li probabbilment l-H huwa rappreżentat minn biss 1 wieħed

400
00:34:07,340 --> 00:34:17,120
u allura l-T hija probabbilment 01 u allura l-H jmiss huwa 1 kif ukoll

401
00:34:17,120 --> 00:34:21,139
u allura għandna newline indikat minn żewġ 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> U allura finalment, għaliex aħna qed jittrattaw ma multipli. Cu. Fajls h,

404
00:34:31,600 --> 00:34:36,350
aħna qed tmur biex ikollhom argument kumpless pretty mal-kompilatur,

405
00:34:36,350 --> 00:34:40,460
u hekk hawn għandna Makefile li tagħmel dump għalik.

406
00:34:40,460 --> 00:34:47,070
Imma fil-fatt, ikollok tmur dwar teħid fajl puff.c tiegħek stess.

407
00:34:47,070 --> 00:34:54,330
Il Makefile attwalment ma jittrattax tagħmel puff.c għalik.

408
00:34:54,330 --> 00:34:59,310
Aħna qed tħalli li sa inti biex jeditjaw il-Makefile.

409
00:34:59,310 --> 00:35:05,930
Meta inti tidħol kmand bħal tagħmel kollox, per eżempju, hija ser tagħmel kull wieħed minnhom għalik.

410
00:35:05,930 --> 00:35:10,760
Ħossok liberu li tħares lejn l-eżempji ta Makefile mill-pset passat

411
00:35:10,760 --> 00:35:17,400
kif ukoll tmur off ta 'dan wieħed biex tara kif inti tista' tkun kapaċi tagħmel fajl Puff tiegħek

412
00:35:17,400 --> 00:35:20,260
mill-editjar dan Makefile.

413
00:35:20,260 --> 00:35:22,730
Li dwar dan għal kodiċi tad-distribuzzjoni tagħna.

414
00:35:22,730 --> 00:35:28,380
>> Ladarba aħna ħadthom gotten permezz ta 'dan, allura hawnhekk biss ieħor tifkira

415
00:35:28,380 --> 00:35:30,980
ta 'kif aħna qed tmur biex tkun jittrattaw ma' punti strateġiċi Huffman.

416
00:35:30,980 --> 00:35:35,400
Aħna mhux se tkun titlob minnhom lymph aktar; aħna qed tmur biex tkun titlob minnhom siġar

417
00:35:35,400 --> 00:35:39,260
fejn aħna qed tmur biex tkun tirrappreżenta simbolu tagħhom ma 'char,

418
00:35:39,260 --> 00:35:43,340
frekwenza tagħhom, in-numru ta 'okkorrenzi, ma integer.

419
00:35:43,340 --> 00:35:47,370
Aħna qed jużaw dan għaliex dan huwa aktar preċiż minn float.

420
00:35:47,370 --> 00:35:52,980
U allura għandna ieħor pointer lill-wild xellug kif ukoll il-wild dritt.

421
00:35:52,980 --> 00:35:59,630
A foresti, kif rajna, hija biss lista linked ta 'siġar.

422
00:35:59,630 --> 00:36:04,670
Fl-aħħarnett, meta aħna qed tibni fajl Huff tagħna,

423
00:36:04,670 --> 00:36:07,580
irridu foresti tagħna li fihom biss 1 siġra -

424
00:36:07,580 --> 00:36:12,420
1 siġar, 1 għerq mat-tfal multipli.

425
00:36:12,420 --> 00:36:20,840
Preċedenti dwar meta konna biss tagħmel siġar Huffman tagħna,

426
00:36:20,840 --> 00:36:25,360
bdejna mill-tqegħid kollha ta 'l-għoqiedi fuq l-iskrin tagħna

427
00:36:25,360 --> 00:36:27,790
u qal aħna qed tmur biex ikollhom dawn in-nodi,

428
00:36:27,790 --> 00:36:32,920
eventwalment dawn qed tmur biex tkun il-weraq, u dan huwa simbolu tagħhom, dan huwa l-frekwenza tagħhom.

429
00:36:32,920 --> 00:36:42,070
Fil-foresti tagħna jekk aħna biss għandhom 3 ittri, li l-foresti ta 'siġar 3.

430
00:36:42,070 --> 00:36:45,150
U allura kif aħna jmorru fuq, meta aħna miżjud l-ġenitur l-ewwel,

431
00:36:45,150 --> 00:36:48,080
għamilna foresti ta 'siġar 2.

432
00:36:48,080 --> 00:36:54,930
Aħna imneħħija 2 ta 'dawk it-tfal mill-foresti tagħna u mbagħad jinbidel ma node ġenitur

433
00:36:54,930 --> 00:36:58,820
li kellhom dawn l-lymph 2 huma t-tfal.

434
00:36:58,820 --> 00:37:05,600
U mbagħad finalment, l-aħħar pass tagħna ma jagħmlu eżempju tagħna ma 'l-As, Bs, u Cs

435
00:37:05,600 --> 00:37:08,030
jkun li jagħmel il-ġenitur finali,

436
00:37:08,030 --> 00:37:13,190
u hekk allura li ġġib magħha għadd totali tagħna ta 'siġar fil-foresti għal 1.

437
00:37:13,190 --> 00:37:18,140
Ma kulħadd tara kif tista 'tibda bl-siġar multipli fil-foresti tiegħek

438
00:37:18,140 --> 00:37:22,520
u tispiċċa bil 1? Okay. Kessaħ.

439
00:37:25,530 --> 00:37:28,110
>> What do we bżonn tagħmel biex Puff?

440
00:37:28,110 --> 00:37:37,110
Dak li għandna bżonn tagħmel hu li jiżgura li, bħal dejjem, dawn jagħtu lilna t-tip korrett ta 'input

441
00:37:37,110 --> 00:37:39,090
sabiex inkunu nistgħu effettivament imexxu l-programm.

442
00:37:39,090 --> 00:37:43,130
F'dan il-każ dawn qed tmur biex tkun tagħti us wara l-ewwel kmand tal-linja tagħhom argument

443
00:37:43,130 --> 00:37:53,440
2 aktar: il-fajl li aħna rridu li decompress u l-produzzjoni tal-fajl decompressed.

444
00:37:53,440 --> 00:38:00,410
Imma ladarba irridu niżguraw li dawn jgħaddu lilna fil-ammont korrett ta 'valuri,

445
00:38:00,410 --> 00:38:05,820
irridu niżguraw li l-input il-fajl huwa Huff jew le.

446
00:38:05,820 --> 00:38:10,420
U allura ladarba aħna garanzija li din hija fajl Huff, allura rridu nibnu siġra tagħna,

447
00:38:10,420 --> 00:38:20,940
jibnu l-siġra tali li jaqbel mal-siġra li l-persuna li bagħtet l-messaġġ mibnija.

448
00:38:20,940 --> 00:38:25,840
Imbagħad wara nibnu l-siġra, allura nistgħu jittrattaw l-0s u 1s li għadda fil-

449
00:38:25,840 --> 00:38:29,590
isegwu dawk max siġra tagħna għaliex dan huwa identiku,

450
00:38:29,590 --> 00:38:33,510
u mbagħad jiktbu dak il-messaġġ out, tinterpreta l-bits lura fis Chars.

451
00:38:33,510 --> 00:38:35,880
U mbagħad fl-aħħar għaliex aħna qed jittrattaw ma 'pointers hawn,

452
00:38:35,880 --> 00:38:38,110
irridu niżguraw li aħna ma jkollhomx xi tnixxijiet memorja

453
00:38:38,110 --> 00:38:41,330
u li aħna kollox ħielsa.

454
00:38:42,820 --> 00:38:46,430
>> L-iżgurar użu xieraq huwa hat qodma għalina minn issa.

455
00:38:46,430 --> 00:38:51,980
Nieħdu fi input, li se tkun l-isem tal-fajl lill puff,

456
00:38:51,980 --> 00:38:56,010
u allura aħna jispeċifikaw l-output,

457
00:38:56,010 --> 00:39:01,580
hekk l-isem tal-fajl għall-produzzjoni minfuħ, li se jkun il-fajl test.

458
00:39:03,680 --> 00:39:08,820
Dak użu. U issa aħna tixtieq li tiżgura li l-input huwa huffed jew le.

459
00:39:08,820 --> 00:39:16,420
Thinking lura, kien hemm xejn fil-kodiċi ta 'distribuzzjoni li tista' tgħinna

460
00:39:16,420 --> 00:39:21,570
bil-fehim jekk fajl huffed jew le?

461
00:39:21,570 --> 00:39:26,910
Kien hemm informazzjoni fil huffile.c dwar il-Huffeader.

462
00:39:26,910 --> 00:39:33,430
Aħna nafu li kull fajl Huff għandha Huffeader assoċjati magħha ma 'numru magic

463
00:39:33,430 --> 00:39:37,240
kif ukoll firxa tal-frekwenzi għal kull simbolu

464
00:39:37,240 --> 00:39:39,570
kif ukoll checksum.

465
00:39:39,570 --> 00:39:43,180
Aħna nafu li, iżda aħna wkoll ħa Peek fuq dump.c,

466
00:39:43,180 --> 00:39:49,120
fejn kien qari fis-fajl Huff.

467
00:39:49,120 --> 00:39:53,990
U hekk li tagħmel dan, hija kellha tivverifika jekk verament kien huffed jew le.

468
00:39:53,990 --> 00:40:03,380
Allura forsi nistgħu jużaw dump.c bħala struttura għall puff.c. tagħna

469
00:40:03,380 --> 00:40:12,680
Lura għall pset 4 meta kellna l-copy.c fajl li kkupjati fil triples RGB

470
00:40:12,680 --> 00:40:14,860
u aħna interpretat li għal whodunit u Resize,

471
00:40:14,860 --> 00:40:20,390
bl-istess mod, dak li inti tista 'tagħmel huwa biss run-kmand bħal cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
u l-użu xi wħud mill-kodiċi hemmhekk.

473
00:40:23,600 --> 00:40:28,210
Madankollu, mhuwiex ser ikunu kif sempliċi ta 'proċess

474
00:40:28,210 --> 00:40:33,010
biex jittraduċi dump.c tiegħek fis puff.c,

475
00:40:33,010 --> 00:40:36,160
iżda mill-inqas inti tagħti x'imkien biex tibda

476
00:40:36,160 --> 00:40:40,540
dwar kif jiġi żgurat li l-input huwa attwalment huffed jew le

477
00:40:40,540 --> 00:40:43,240
kif ukoll affarijiet oħra ftit.

478
00:40:45,930 --> 00:40:50,250
Aħna żgurat l-użu xieraq u l żgurat li l-input huwa huffed.

479
00:40:50,250 --> 00:40:53,570
Kull darba li aħna ghamilt li għamilna verifika tagħna żball xierqa,

480
00:40:53,570 --> 00:41:01,520
hekk jirritornaw u jaqtagħhom l-funzjoni jekk xi falliment jiġri, jekk ikun hemm problema.

481
00:41:01,520 --> 00:41:07,170
>> Issa dak li rridu nagħmlu huwa tinbena l-siġra attwali.

482
00:41:08,840 --> 00:41:12,640
Jekk nagħtu ħarsa fil-Foresti, hemm 2 funzjonijiet prinċipali

483
00:41:12,640 --> 00:41:15,800
li aħna qed tmur jridu jsiru familjari ħafna ma.

484
00:41:15,800 --> 00:41:23,870
Hemm l-impjant funzjoni Boolean li l-pjanti siġra frekwenza mhux-0 ġewwa foresti tagħna.

485
00:41:23,870 --> 00:41:29,250
U hekk hemm inti tgħaddi fil-pointer lejn foresti u werrej ma 'siġra.

486
00:41:32,530 --> 00:41:40,340
Mistoqsija Quick: Kemm foresti ser ikollok meta int bini ta 'siġra Huffman?

487
00:41:44,210 --> 00:41:46,650
Foresti tagħna huwa bħal kanvas tagħna, id-dritt?

488
00:41:46,650 --> 00:41:50,800
Allura aħna qed biss ser ikollha 1 foresti, imma aħna qed tmur biex ikollhom siġar multipli.

489
00:41:50,800 --> 00:41:57,590
Allura qabel ma inti sejħa tal-pjanti, int preżumibbilment tmur jixtiequ jagħmlu foresti tiegħek.

490
00:41:57,590 --> 00:42:04,430
Hemm kmand għal dak jekk inti tħares lejn forest.h dwar kif inti tista 'tagħmel foresti.

491
00:42:04,430 --> 00:42:09,270
Tista 'pjanti siġra. Nafu kif għandek tagħmel dan.

492
00:42:09,270 --> 00:42:11,590
U allura inti tista 'wkoll pick siġra mill-foresti,

493
00:42:11,590 --> 00:42:17,540
tneħħija siġra bil-piż aktar baxx u jagħtik l-pointer għal dan.

494
00:42:17,540 --> 00:42:23,090
Thinking lura għal meta konna qed jagħmlu l-eżempji nfusna,

495
00:42:23,090 --> 00:42:27,980
meta konna tfassil it out, aħna sempliċiment biss miżjud il-links.

496
00:42:27,980 --> 00:42:31,680
Imma hawn minflok sempliċiment żżid il-links,

497
00:42:31,680 --> 00:42:40,630
x'taħseb dwar dan aktar kif int tneħħi 2 ta 'dawk lymph u mbagħad jbiddlu ieħor.

498
00:42:40,630 --> 00:42:44,200
Li jesprimu li f'termini ta 'picking u żrigħ,

499
00:42:44,200 --> 00:42:48,840
int picking 2 siġar u mbagħad tħawwil siġra oħra

500
00:42:48,840 --> 00:42:54,060
li għandha dawk is-siġar 2 li inti qabad bħala tfal.

501
00:42:57,950 --> 00:43:05,280
Biex tibni siġra Huffman, inti tista 'taqra fil-simboli u l-frekwenzi sabiex

502
00:43:05,280 --> 00:43:10,790
minħabba li l-Huffeader jagħtik li lilek,

503
00:43:10,790 --> 00:43:14,250
jagħtik firxa tal-frekwenzi.

504
00:43:14,250 --> 00:43:19,660
Allura inti tista 'tmur quddiem u biss jinjora xi ħaġa ma' 0 fiha

505
00:43:19,660 --> 00:43:23,760
għaliex aħna ma rridux 256 weraq fl-aħħar ta 'dan.

506
00:43:23,760 --> 00:43:27,960
Aħna biss trid li l-għadd ta 'weraq li huma karattri

507
00:43:27,960 --> 00:43:31,600
li huma attwalment użati fil-fajl.

508
00:43:31,600 --> 00:43:37,590
Tista 'taqra f'dawk simboli, u kull wieħed minn dawn is-simboli li għandhom mhux 0 frekwenzi,

509
00:43:37,590 --> 00:43:40,440
dawk ser ikunu siġar.

510
00:43:40,440 --> 00:43:45,990
X'tista 'tagħmel huwa kull darba li inti taqra fil simbolu frekwenza mhux-0,

511
00:43:45,990 --> 00:43:50,660
inti tista 'pjanti li siġra fil-foresti.

512
00:43:50,660 --> 00:43:56,620
Ladarba inti pjanti l-siġar fil-foresti, tista 'tingħaqad dawk is-siġar kif aħwa,

513
00:43:56,620 --> 00:44:01,130
hekk tmur lura għall tħawwil u picking fejn inti pick 2 u mbagħad pjanti 1,

514
00:44:01,130 --> 00:44:05,820
fejn dik 1 li inti pjanti huwa l-ġenitur tat-tfal 2 li inti qabad.

515
00:44:05,820 --> 00:44:11,160
Mela allura riżultat aħħari tiegħek se tkun siġra waħda fil-foresti tiegħek.

516
00:44:16,180 --> 00:44:18,170
Li kif inti tibni siġra tiegħek.

517
00:44:18,170 --> 00:44:21,850
>> Hemm diversi affarijiet li tista 'tmur ħażin hawn

518
00:44:21,850 --> 00:44:26,580
għaliex aħna qed jittrattaw ma jagħmlu siġar ġodda u jittrattaw pointers u affarijiet bħal dik.

519
00:44:26,580 --> 00:44:30,450
Qabel meta konna jittrattaw pointers,

520
00:44:30,450 --> 00:44:36,580
kull meta aħna malloc'd ridna biex tiżgura li ma jerġax lura lilna valur pointer NULL.

521
00:44:36,580 --> 00:44:42,770
Allura fil diversi passi fi ħdan dan il-proċess hemm ser ikunu diversi kawżi

522
00:44:42,770 --> 00:44:45,920
fejn programm tiegħek jista 'jfalli.

523
00:44:45,920 --> 00:44:51,310
Dak li trid tagħmel huwa li inti tixtieq li tagħmel ċert li inti tagħmel handling dawn l-iżbalji,

524
00:44:51,310 --> 00:44:54,580
u fil-spec jgħid li jħaddmuhom gracefully,

525
00:44:54,580 --> 00:45:00,280
hekk tixtieq jistampa messaġġ lill-utent tgħidilhom għaliex il-programm għandu nieqaf

526
00:45:00,280 --> 00:45:03,050
u mbagħad minnufih nieqaf dan.

527
00:45:03,050 --> 00:45:09,490
Biex tagħmel dan tqandil żball, ftakar li inti tixtieq li jiċċekkjaha

528
00:45:09,490 --> 00:45:12,160
kull wieħed ħin li jista 'jkun hemm falliment.

529
00:45:12,160 --> 00:45:14,660
Kull darba waħda li int tagħmel pointer ġdida

530
00:45:14,660 --> 00:45:17,040
inti tixtieq li tagħmel ċert li dan huwa ta 'suċċess.

531
00:45:17,040 --> 00:45:20,320
Qabel dak li aħna użati biex tagħmel hu li tagħmel pointer ġdid u malloc dan,

532
00:45:20,320 --> 00:45:22,380
u allura aħna se tiċċekkja jekk dik pointer huwa NULL.

533
00:45:22,380 --> 00:45:25,670
Allura hemm ser jkun hemm xi każijiet fejn inti biss tista 'tagħmel dan,

534
00:45:25,670 --> 00:45:28,610
imma xi kultant int attwalment sejħa funzjoni

535
00:45:28,610 --> 00:45:33,100
u fi ħdan dik il-funzjoni, li l-waħda li qed jagħmel l-mallocing.

536
00:45:33,100 --> 00:45:39,110
F'dak il-każ, jekk inħarsu lura lejn uħud mill-funzjonijiet fi ħdan il-kodiċi,

537
00:45:39,110 --> 00:45:42,260
xi wħud minnhom huma funzjonijiet Boolean.

538
00:45:42,260 --> 00:45:48,480
Fil-każ astratt jekk ikollna funzjoni Boolean imsejjaħ foo,

539
00:45:48,480 --> 00:45:54,580
bażikament, nistgħu nassumu li minbarra li jagħmlu kwalunkwe foo ma,

540
00:45:54,580 --> 00:45:57,210
peress li l-funzjoni Boolean, dan jirritorna vera jew falza -

541
00:45:57,210 --> 00:46:01,300
minnu jekk tirnexxi, falza jekk le.

542
00:46:01,300 --> 00:46:06,270
Allura aħna tixtieq li jivverifika jekk il-valur tar-ritorn ta 'foo hija vera jew falza.

543
00:46:06,270 --> 00:46:10,400
Jekk huwa falz, li jfisser li aħna qed tmur jridu li jistampaw xi tip ta 'messaġġ

544
00:46:10,400 --> 00:46:14,390
u mbagħad nieqaf-programm.

545
00:46:14,390 --> 00:46:18,530
Dak li rridu nagħmlu huwa li jiċċekkja l-valur tar-ritorn ta 'foo.

546
00:46:18,530 --> 00:46:23,310
Jekk foo prospetti falz, allura nafu li aħna jiltaqgħu magħhom xi tip ta 'żball

547
00:46:23,310 --> 00:46:25,110
u għandna bżonn li nieqaf-programm tagħna.

548
00:46:25,110 --> 00:46:35,600
A mod biex isir dan huwa minn kundizzjoni fejn il-funzjoni innifisha hija kundizzjoni tiegħek.

549
00:46:35,600 --> 00:46:39,320
Say foo jieħu fil x.

550
00:46:39,320 --> 00:46:43,390
Jista 'jkollna bħala kundizzjoni jekk (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Bażikament, li jfisser li jekk fl-aħħar ta 'eżekuzzjoni foo huwa u jirritorna veru,

552
00:46:50,900 --> 00:46:57,390
allura nistgħu nagħmlu dan minħabba l-funzjoni għandha tevalwa foo

553
00:46:57,390 --> 00:47:00,500
sabiex tevalwa l-kundizzjoni kollha.

554
00:47:00,500 --> 00:47:06,500
Allura mbagħad thats kif inti tista 'tagħmel xi ħaġa jekk il-funzjoni lura vera u huwa ta' suċċess.

555
00:47:06,500 --> 00:47:11,800
Imma meta int iċċekkjar żball, inti biss tixtieq li nieqaf jekk il-funzjoni tiegħek jirritorna falza.

556
00:47:11,800 --> 00:47:16,090
What inti tista 'tagħmel huwa biss żid == falz jew sempliċiment żid bang quddiem ta' dan

557
00:47:16,090 --> 00:47:21,010
u allura inti għandek jekk (! foo).

558
00:47:21,010 --> 00:47:29,540
Fi ħdan dak il-korp ta 'din il-kundizzjoni inti għandek kollha ta' l-immaniġġjar żball,

559
00:47:29,540 --> 00:47:36,940
hekk simili, "Ma kellekx joħolqu din is-siġra" u mbagħad jirritornaw 1 jew xi ħaġa bħal dik.

560
00:47:36,940 --> 00:47:43,340
Dak li ma, għalkemm, hi li, anki jekk foo lura foloz -

561
00:47:43,340 --> 00:47:46,980
Say foo prospetti vera.

562
00:47:46,980 --> 00:47:51,060
Imbagħad inti ma għandekx sejħa foo mill-ġdid. Li l-kunċett żbaljat komuni.

563
00:47:51,060 --> 00:47:54,730
Minħabba li kien fil-kundizzjoni tiegħek, huwa diġà evalwati,

564
00:47:54,730 --> 00:47:59,430
sabiex inti diġà għandhom ir-riżultat jekk inti qed tuża tagħmel siġra jew xi ħaġa bħal dik

565
00:47:59,430 --> 00:48:01,840
jew impjant jew pick jew xi ħaġa.

566
00:48:01,840 --> 00:48:07,460
Hija diġà għandha dik valur. Huwa diġà eżegwit.

567
00:48:07,460 --> 00:48:10,730
Allura huwa utli li tintuża l-funzjonijiet Boolean bħala l-kondizzjoni

568
00:48:10,730 --> 00:48:13,890
għaliex jekk jew le inti fil-fatt tesegwixxi l-korp tal-linja,

569
00:48:13,890 --> 00:48:18,030
tesegwixxi l-funzjoni xorta waħda.

570
00:48:22,070 --> 00:48:27,330
>> 2 tagħna għall-aħħar pass huwa miktub l-messaġġ għall-fajl.

571
00:48:27,330 --> 00:48:33,070
Ladarba aħna nibnu l-siġra Huffman, allura bil-miktub il-messaġġ għall-fajl huwa pjuttost sempliċi.

572
00:48:33,070 --> 00:48:39,260
Huwa pjuttost sempliċi issa biex kemm issegwi l-0s u 1s.

573
00:48:39,260 --> 00:48:45,480
U hekk permezz tal-konvenzjoni aħna nafu li fil-siġra Huffman l 0s jindikaw xellug

574
00:48:45,480 --> 00:48:48,360
u l-1s jindikaw id-dritt.

575
00:48:48,360 --> 00:48:53,540
Mela allura jekk inti jinqara ftit ftit, kull darba li inti tikseb 0

576
00:48:53,540 --> 00:48:59,100
inti ser issegwi l-fergħa tax-xellug, u mbagħad kull darba li inti taqra fil-1

577
00:48:59,100 --> 00:49:02,100
int ser isegwu l-fergħa dritt.

578
00:49:02,100 --> 00:49:07,570
U allura int ser tkompli sakemm inti hit werqa

579
00:49:07,570 --> 00:49:11,550
minħabba li l-weraq ser ikunu fl-aħħar tal-fergħat.

580
00:49:11,550 --> 00:49:16,870
Kif nistgħu tgħid jekk konna hit werqa jew le?

581
00:49:19,800 --> 00:49:21,690
Aħna qal li qabel.

582
00:49:21,690 --> 00:49:24,040
[Student] Jekk il-pointers huma NULL. >> Yeah.

583
00:49:24,040 --> 00:49:32,220
Aħna jista 'jgħidlek jekk konna hit werqa jekk il-pointers għall-siġar kemm il-xellug u lemin huma NULL.

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

585
00:49:34,110 --> 00:49:40,320
Aħna nafu li aħna rridu li jinqara ftit ftit fil-fajl Huff tagħna.

586
00:49:43,870 --> 00:49:51,220
Kif rajna qabel fl dump.c, x'għamlu huwa li jinqara ftit ftit fil-fajl Huff

587
00:49:51,220 --> 00:49:54,560
u biss stampata x'inhuma dawn bits kienu.

588
00:49:54,560 --> 00:49:58,430
Aħna mhux se tkun qed twettaq dan. Aħna ser tkun tagħmel xi ħaġa li l-daqsxejn aktar kumplessa.

589
00:49:58,430 --> 00:50:03,620
Imma dak li nistgħu nagħmlu huwa li nistgħu nieħdu li ftit tal-kodiċi li jaqra fil lill-bit.

590
00:50:03,620 --> 00:50:10,250
Hawnhekk għandna l-daqsxejn eqreb numru sħiħ li tirrappreżenta l-ftit attwali li aħna qed dwar.

591
00:50:10,250 --> 00:50:15,520
Dan jieħu ħsieb ta 'iterazzjoni kollha tal-bits fil-fajl sakemm inti hit-aħħar tal-fajl.

592
00:50:15,520 --> 00:50:21,270
Ibbażat fuq dan, allura int ser jridu li jkollhom xi tip ta 'iterator

593
00:50:21,270 --> 00:50:26,760
travers siġra tiegħek.

594
00:50:26,760 --> 00:50:31,460
U mbagħad ibbażata fuq jekk il-bit hija 0 jew 1,

595
00:50:31,460 --> 00:50:36,920
int tmur jridu jew jiċċaqalqu li iterator lejn ix-xellug jew jġorrhom lejn il-lemin

596
00:50:36,920 --> 00:50:44,080
it-triq kollha sakemm inti hit weraq, hekk it-triq kollha sa dak node li int fuq

597
00:50:44,080 --> 00:50:48,260
ma punt għal punti strateġiċi f'kull aktar.

598
00:50:48,260 --> 00:50:54,300
Għaliex nistgħu nagħmlu dan bil-fajl Huffman iżda mhux il-kodiċi Morse?

599
00:50:54,300 --> 00:50:56,610
Minħabba fil-kodiċi Morse hemm daqsxejn ta 'ambigwità.

600
00:50:56,610 --> 00:51:04,440
Aħna jista 'jkun simili, oh stenna, konna hit ittra tul it-triq, hekk forsi din hija ittra tagħna,

601
00:51:04,440 --> 00:51:08,150
billi jekk aħna nkomplu biss ftit itwal, allura aħna laħqu ittra oħra.

602
00:51:08,150 --> 00:51:13,110
Iżda li mhux se jiġri fil-kodifikazzjoni Huffman,

603
00:51:13,110 --> 00:51:17,540
sabiex inkunu tista 'mistrieħ assigurat li l-uniku mod li aħna qed tmur biex hit karattru

604
00:51:17,540 --> 00:51:23,480
huwa jekk it-tfal tax-xellug u lemin li l-glandoli huma NULL.

605
00:51:28,280 --> 00:51:32,350
>> Fl-aħħarnett, irridu biex ħielsa kollha ta 'memorja tagħna.

606
00:51:32,350 --> 00:51:37,420
Aħna rridu li kemm mill-qrib il-fajl Huff li aħna kont qed jittrattaw ma '

607
00:51:37,420 --> 00:51:41,940
kif ukoll neħħi kollha tal-siġar fil-foresti tagħna.

608
00:51:41,940 --> 00:51:46,470
Ibbażat fuq l-implimentazzjoni tiegħek, int probabilment tmur jridu sejħa jitneħħew foresti

609
00:51:46,470 --> 00:51:49,780
minflok attwalment għaddejjin kollha tas-siġar yourself.

610
00:51:49,780 --> 00:51:53,430
Imma jekk inti ssir xi siġar temporanji, tixtieq tkun taf biex ħielsa li.

611
00:51:53,430 --> 00:51:59,060
Inti taf kodiċi tiegħek aħjar, sabiex inti tkun taf fejn int allokazzjoni memorja.

612
00:51:59,060 --> 00:52:04,330
U hekk jekk inti tmur fi, tibda billi anke Kontroll F'ing għall malloc,

613
00:52:04,330 --> 00:52:08,330
jaraw kull meta inti malloc u jagħmlu ċert li inti liberu kollha ta 'dak

614
00:52:08,330 --> 00:52:10,190
iżda mbagħad biss jmorru permezz ta 'kodiċi tiegħek,

615
00:52:10,190 --> 00:52:14,260
ftehim fejn inti jista 'jkollok allokati memorja.

616
00:52:14,260 --> 00:52:21,340
Normalment inti tista 'biss jgħidu, "Fl-aħħar ta' fajl jien biss se tneħħi foresti fuq foresti tiegħi,"

617
00:52:21,340 --> 00:52:23,850
hekk bażikament ċar li l-memorja, b'xejn li,

618
00:52:23,850 --> 00:52:28,310
"U mbagħad jien ukoll ser tagħlaq il-fajl u mbagħad programm tiegħi se nieqaf."

619
00:52:28,310 --> 00:52:33,810
Iżda huwa li l-unika darba li l-programm tiegħek quits?

620
00:52:33,810 --> 00:52:37,880
Le, għaliex kultant jista 'jkun hemm żball li ġara.

621
00:52:37,880 --> 00:52:42,080
Forsi aħna ma setgħetx tiftaħ fajl jew aħna ma setgħux jagħmlu siġra oħra

622
00:52:42,080 --> 00:52:49,340
jew xi tip ta 'żball ġara fil-proċess ta' allokazzjoni memorja u għalhekk lura NULL.

623
00:52:49,340 --> 00:52:56,710
Żball ġara u mbagħad aħna lura u nieqaf.

624
00:52:56,710 --> 00:53:02,040
Mela allura inti tixtieq li tagħmel ċert li kull ħin possibbli dak il-programm tiegħek jista nieqaf,

625
00:53:02,040 --> 00:53:06,980
inti tixtieq biex ħielsa kollha ta 'memorja tiegħek hemmhekk.

626
00:53:06,980 --> 00:53:13,370
Huwa mhux biss se tkun fl-aħħar nett tal-funzjoni prinċipali li inti nieqaf kodiċi tiegħek.

627
00:53:13,370 --> 00:53:20,780
Inti trid tfittex lura għal kull każ li l-kodiċi tiegħek potenzjalment jistgħu jirritornaw qabel iż-żmien

628
00:53:20,780 --> 00:53:25,070
u mbagħad ħielsa tkun xi tkun memorja jagħmel sens.

629
00:53:25,070 --> 00:53:30,830
Tgħid li inti kien talab tagħmel foresta u li lura falza.

630
00:53:30,830 --> 00:53:34,230
Imbagħad inti probabilment mhux se jkollhom bżonn li jitneħħew foresti tiegħek

631
00:53:34,230 --> 00:53:37,080
għaliex inti ma għandekx foresti s'issa.

632
00:53:37,080 --> 00:53:42,130
Iżda f'kull punt fil-kodiċi fejn inti tista 'tirritorna qabel iż-żmien

633
00:53:42,130 --> 00:53:46,160
inti tixtieq li tagħmel ċert li inti liberu kwalunkwe memorja possibbli.

634
00:53:46,160 --> 00:53:50,020
>> Allura meta aħna qed jittrattaw ma 'ħelsien memorja u li jkollhom tnixxijiet potenzjali,

635
00:53:50,020 --> 00:53:55,440
irridu mhux biss jużaw il-ġudizzju tagħna u l-loġika tagħna

636
00:53:55,440 --> 00:54:01,850
iżda wkoll jużaw Valgrind biex jiddeterminaw jekk konna meħlusa kollha tal-memorja tagħna b'mod korrett jew le.

637
00:54:01,850 --> 00:54:09,460
Inti tista 'jew taħdem Valgrind fuq Puff u imbagħad inti għandek ukoll tgħaddih

638
00:54:09,460 --> 00:54:14,020
in-numru dritt ta 'kmand tal-linja argumenti għall Valgrind.

639
00:54:14,020 --> 00:54:18,100
Inti tista 'taħdem, iżda l-output huwa daqsxejn cryptic.

640
00:54:18,100 --> 00:54:21,630
Imxejna gotten daqsxejn użati biex dan ma speller, iżda għad għandna bżonn l-għajnuna ftit aktar,

641
00:54:21,630 --> 00:54:26,450
hekk allura running bil-bnadar ftit aktar bħall-tnixxija check = sħiħa,

642
00:54:26,450 --> 00:54:32,040
li probabbilment se tagħtina xi output aktar utli dwar Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Imbagħad ieħor ponta utli meta int debugging huwa l-kmand diff.

644
00:54:39,040 --> 00:54:48,520
Tista 'aċċess implimentazzjoni tal-persunal ta' Huff, run li fuq fajl test,

645
00:54:48,520 --> 00:54:55,400
u mbagħad output li fajl binarju, fajl Huff binarju, li jkunu speċifiċi.

646
00:54:55,400 --> 00:54:59,440
Imbagħad jekk inti tmexxi puff tiegħek dwar dan il-fajl binarju,

647
00:54:59,440 --> 00:55:03,950
allura idealment, fajl tiegħek test outputted se tkun identika

648
00:55:03,950 --> 00:55:08,200
għal dak oriġinali li inti għadda pulzieri

649
00:55:08,200 --> 00:55:15,150
Hawnhekk jien jużaw hth.txt bħala l-eżempju, u li l-waħda tkellem dwar fl spec tiegħek.

650
00:55:15,150 --> 00:55:21,040
Li litteralment biss HTH u mbagħad newline.

651
00:55:21,040 --> 00:55:30,970
Iżda żgur li tħossok liberu u inti definittivament mħeġġa biex jużaw eżempji itwal

652
00:55:30,970 --> 00:55:32,620
għall-fajl test tiegħek.

653
00:55:32,620 --> 00:55:38,110
>> Tista 'anki tieħu xi sparatura fil forsi kompressjoni u mbagħad decompressing

654
00:55:38,110 --> 00:55:41,600
xi wħud mill-fajls li inti użati fil speller bħall Gwerra u l-Paċi

655
00:55:41,600 --> 00:55:46,710
jew Jane Austen jew xi ħaġa bħal dik - li jkun tip ta 'kessaħ - jew Poteri Austin,

656
00:55:46,710 --> 00:55:51,880
tip ta 'tittratta fajls akbar għaliex aħna mhux se tinżel għal dan

657
00:55:51,880 --> 00:55:55,590
jekk aħna użata l-għodda li jmiss hawn, Ls-l.

658
00:55:55,590 --> 00:56:01,150
Aħna użati biex ls, li bażikament jelenka l-kontenuti fl-direttorju attwali tagħna.

659
00:56:01,150 --> 00:56:07,860
Tgħaddi fil-bandiera l-fatt juri d-daqs ta 'dawk il-fajls.

660
00:56:07,860 --> 00:56:12,690
Jekk inti tmur permezz tal-spec pset, attwalment mixjiet inti permezz tal-ħolqien tal-fajl binarju,

661
00:56:12,690 --> 00:56:16,590
ta huffing, u tara li għall-fajls żgħar ħafna

662
00:56:16,590 --> 00:56:23,910
l-ispiża ispazju ta 'kompressjoni dan u tittraduċi kollha ta' dik l-informazzjoni

663
00:56:23,910 --> 00:56:26,980
ta 'l-frekwenzi u affarijiet bħal dik jegħleb l-benefiċċju attwali

664
00:56:26,980 --> 00:56:30,000
tal kompressjoni-fajl fl-ewwel post.

665
00:56:30,000 --> 00:56:37,450
Imma jekk inti tmexxi fuq xi fajls test itwal, allura inti tista 'tara li inti tibda tikseb xi benefiċċju

666
00:56:37,450 --> 00:56:40,930
fil jikkompressaw dawn il-fajls.

667
00:56:40,930 --> 00:56:46,210
>> U mbagħad finalment, aħna għandna GDB qodma tagħna PAL, li huwa definittivament se jidħol fil handy wisq.

668
00:56:48,360 --> 00:56:55,320
>> Do we xi mistoqsijiet dwar is-siġar Huff jew il-proċess ta 'teħid forsi l-siġar

669
00:56:55,320 --> 00:56:58,590
jew xi mistoqsijiet oħra dwar Puff Huff'n?

670
00:57:00,680 --> 00:57:02,570
Okay. I ser jibqgħu madwar għal bit.

671
00:57:02,570 --> 00:57:06,570
>> Grazzi, kulħadd. Dan kien Walkthrough 6. U Xorti tajba.

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