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

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

3
00:00:04,810 --> 00:00:07,240
[Ito ay CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Hello, lahat, at maligayang pagdating sa walkthrough 6: Huff'n papamintugin.

5
00:00:12,180 --> 00:00:17,440
Sa Huff'n papamintugin kung ano ang ginagawa namin ay pagpunta sa pagharap sa isang Huffman compressed file

6
00:00:17,440 --> 00:00:20,740
at pagkatapos ay puffing ito back up, kaya decompressing ito,

7
00:00:20,740 --> 00:00:25,810
upang maaari naming isalin ang mula sa 0s at 1s na ang user ay nagpapadala sa amin

8
00:00:25,810 --> 00:00:30,660
at i-convert ito pabalik sa orihinal na teksto.

9
00:00:30,660 --> 00:00:34,360
Pset 6 ay medyo cool dahil ka upang makita ang ilan sa mga tool

10
00:00:34,360 --> 00:00:41,730
na ginamit mo sa pset 4 at pset 5 at uri ng pagsasama-sama ng mga ito sa 1 medyo kapong baka konsepto

11
00:00:41,730 --> 00:00:43,830
kapag dumating ka upang isipin ang tungkol dito.

12
00:00:43,830 --> 00:00:50,110
>> Gayundin, arguably, pset 4 at 5 ay ang pinaka-mapaghamong psets na nagkaroon kami upang mag-alok.

13
00:00:50,110 --> 00:00:53,950
Kaya mula ngayon, mayroon kaming ito 1 pang pset sa C,

14
00:00:53,950 --> 00:00:56,480
at pagkatapos ay matapos na hindi namin sa web programming.

15
00:00:56,480 --> 00:01:02,310
Kaya bumati sa inyong sarili para sa pagkuha sa ibabaw ng toughest umbok sa CS50.

16
00:01:03,630 --> 00:01:09,760
>> Paglipat sa para Huff'n papamintugin, aming toolbox para sa pset Huffman puno,

17
00:01:09,760 --> 00:01:14,700
kaya unawa hindi lamang kung paano binary puno ng trabaho ngunit partikular Huffman puno,

18
00:01:14,700 --> 00:01:16,240
kung paano sila ay binuo.

19
00:01:16,240 --> 00:01:20,210
At pagkatapos kami ay pagpunta sa magkaroon ng maraming ng pamamahagi code sa pset,

20
00:01:20,210 --> 00:01:22,480
at kami na dumating upang makita na aktwal na ilan ng code

21
00:01:22,480 --> 00:01:24,670
maaaring hindi namin magagawang ganap na maunawaan pa,

22
00:01:24,670 --> 00:01:30,080
at kaya mga ay ang. c file, ngunit ang kanilang mga kasamang. h file

23
00:01:30,080 --> 00:01:34,300
ay magbibigay sa amin ng sapat na pang-unawa na kailangan namin kaya na alam namin kung paano ang mga function gumagana

24
00:01:34,300 --> 00:01:38,100
o hindi bababa sa kung ano ang kanilang dapat gawin - kanilang mga input at output -

25
00:01:38,100 --> 00:01:40,760
kahit na hindi namin alam kung ano ang nangyayari sa itim na kahon

26
00:01:40,760 --> 00:01:44,090
o hindi maunawaan kung ano ang nangyayari sa itim na kahon sa loob.

27
00:01:44,090 --> 00:01:49,400
At pagkatapos ay sa wakas, gaya ng dati, kami ay pagharap sa bagong istraktura ng data,

28
00:01:49,400 --> 00:01:51,840
partikular na mga uri ng node na ituro sa ilang mga bagay,

29
00:01:51,840 --> 00:01:56,080
at kaya dito nagkakaroon ng panulat at papel hindi lamang para sa disenyo ng proseso

30
00:01:56,080 --> 00:01:58,470
at kapag na sinusubukan mong malaman kung paano dapat gumana ang iyong pset

31
00:01:58,470 --> 00:02:00,520
kundi pati na rin sa panahon ng pag-debug.

32
00:02:00,520 --> 00:02:06,140
Maaari kang magkaroon ng GDB sa tabi ng iyong panulat at papel habang magdadala sa iyo pababa kung ano ang mga halaga,

33
00:02:06,140 --> 00:02:09,320
kung saan ang iyong mga arrow na tumuturo, at mga bagay tulad na.

34
00:02:09,320 --> 00:02:13,720
>> Una tingnan natin sa Huffman puno.

35
00:02:13,720 --> 00:02:19,600
Huffman puno binary mga puno, nangangahulugan lamang na ang bawat node ay may 2 bata.

36
00:02:19,600 --> 00:02:24,870
Sa Huffman puno ay ang katangian na ang pinaka-madalas na halaga

37
00:02:24,870 --> 00:02:27,140
ay kinakatawan ng fewest bit.

38
00:02:27,140 --> 00:02:32,690
Nakita namin sa mga halimbawa ng panayam ng Morse code, na uri ng mga pinagsama-samang ilang mga titik.

39
00:02:32,690 --> 00:02:38,030
Kung ikaw ay sinusubukan upang isalin ang isang A o isang E, halimbawa,

40
00:02:38,030 --> 00:02:43,940
ka-translate na madalas, kaya sa halip ng pagkakaroon upang gamitin ang buong hanay ng mga bit

41
00:02:43,940 --> 00:02:48,640
inilaan para sa na dati uri ng data, compress ang ito sa mas kaunti,

42
00:02:48,640 --> 00:02:53,730
at ang mga titik na kinakatawan mas mababa madalas ay kinakatawan mas mahaba bit

43
00:02:53,730 --> 00:02:59,840
dahil maaari mong bayaran na kapag timbangin mo ang mga frequency na lilitaw ang mga titik.

44
00:02:59,840 --> 00:03:03,020
Mayroon kaming ang parehong ideya dito sa Huffman puno

45
00:03:03,020 --> 00:03:12,360
kung saan kami ay gumagawa ng chain, isang uri ng landas upang makakuha ng sa ilang mga character.

46
00:03:12,360 --> 00:03:14,470
At pagkatapos ay ang mga character na may pinaka-dalas

47
00:03:14,470 --> 00:03:17,940
pagpunta sa kinakatawan gamit ang fewest bit.

48
00:03:17,940 --> 00:03:22,020
>> Ang paraan na ikaw ay makagawa ng isang puno ng Huffman

49
00:03:22,020 --> 00:03:27,430
sa pamamagitan ng paglalagay ng lahat ng mga character na lumilitaw sa teksto

50
00:03:27,430 --> 00:03:30,630
at pagkalkula ng kanilang dalas, kung gaano kadalas lumilitaw ang mga ito.

51
00:03:30,630 --> 00:03:33,880
Ito ay maaaring isang bilang ng kung gaano karaming beses ang mga titik ay lilitaw

52
00:03:33,880 --> 00:03:40,270
o marahil ng isang porsyento ng lahat ng mga character kung gaano karaming bawat isa ay lilitaw.

53
00:03:40,270 --> 00:03:44,270
At kaya kung ano ang gagawin mo sa sandaling mayroon ka ng lahat ng na nai-map out,

54
00:03:44,270 --> 00:03:49,060
titingnan mo para sa 2 pinakamababang frequency at pagkatapos ay sumali sa kanila bilang kapatid

55
00:03:49,060 --> 00:03:55,660
kung saan pagkatapos ng magulang na node ay may isang dalas kung saan ay ang kabuuan ng mga 2 bata.

56
00:03:55,660 --> 00:04:00,870
At pagkatapos ay sa iyo sa pamamagitan ng convention natin na kaliwang node,

57
00:04:00,870 --> 00:04:03,770
sundin mo na sa pamamagitan ng pagsunod sa 0 sangay,

58
00:04:03,770 --> 00:04:08,140
at pagkatapos ay ang rightmost node ay 1 branch.

59
00:04:08,140 --> 00:04:16,040
Tulad ng nakita natin sa Morse code, ang isang gotcha na kung ikaw ay may lamang pugak at ang pugak

60
00:04:16,040 --> 00:04:18,120
ito ay hindi maliwanag.

61
00:04:18,120 --> 00:04:22,430
Maaaring alinman sa 1 titik o maaaring ito ay isang pagkakasunod-sunod ng mga 2 titik.

62
00:04:22,430 --> 00:04:27,790
At kaya kung ano Huffman puno ginagawa ay dahil sa pamamagitan ng likas na katangian ng ang mga character na

63
00:04:27,790 --> 00:04:34,140
o ang aming panghuling mga aktwal na character pagiging ang huling node sa branch -

64
00:04:34,140 --> 00:04:39,300
sumangguni namin sa mga bilang dahon - sa pamamagitan ng kabutihan ng na doon ay hindi maaaring maging anumang kalabuan

65
00:04:39,300 --> 00:04:45,160
sa mga tuntunin kung saan sulat na sinusubukan mong i-encode gamit ang serye ng mga bit

66
00:04:45,160 --> 00:04:50,670
dahil wala saanman sa kahabaan ng mga bit na kumakatawan sa 1 titik

67
00:04:50,670 --> 00:04:55,960
nakatagpo ka ng isa pang buong sulat, at doon ay hindi anumang pagkalito doon.

68
00:04:55,960 --> 00:04:58,430
Ngunit kami sa halimbawa na iyong guys ay maaaring aktwal na makita na

69
00:04:58,430 --> 00:05:02,120
sa halip ng sa amin lamang nagsasabi sa iyo na na totoo.

70
00:05:02,120 --> 00:05:06,390
>> Tingnan natin sa isang simpleng halimbawa ng isang puno ng Huffman.

71
00:05:06,390 --> 00:05:09,380
Mayroon akong isang string dito na 12 character ang haba.

72
00:05:09,380 --> 00:05:14,010
Mayroon akong 4 Bilang, 6 BS, at 2 CS.

73
00:05:14,010 --> 00:05:17,270
Aking unang hakbang ay upang mabilang.

74
00:05:17,270 --> 00:05:20,760
Kung gaano karaming beses ang A? Ito lumilitaw sa 4 na beses sa string.

75
00:05:20,760 --> 00:05:25,060
B lilitaw 6 beses, at C lilitaw 2 beses.

76
00:05:25,060 --> 00:05:28,970
Natural, ako pagpunta sa sabihin gumagamit ako ng B madalas,

77
00:05:28,970 --> 00:05:35,970
kaya gusto ko upang kumatawan ang B na may fewest bilang ng bits, ang fewest bilang ng 0s at 1s.

78
00:05:35,970 --> 00:05:42,600
At pagkatapos din ako pagpunta sa inaasahan C sa nangangailangan ang pinaka-halaga ng 0s at 1s pati na rin.

79
00:05:42,600 --> 00:05:48,550
Una kung ano ang ginawa ko dito inilagay ko sa kanila sa pataas na pagkakasunod-sunod sa mga tuntunin ng dalas.

80
00:05:48,550 --> 00:05:52,710
Nakikita namin na ang C at A, mga aming 2 pinakamababang frequency.

81
00:05:52,710 --> 00:06:00,290
Lumikha kami ng magulang na node, at na ang magulang na node ay hindi magkaroon ng isang sulat na nauugnay dito,

82
00:06:00,290 --> 00:06:05,070
ngunit ang ng dalas, kung saan ay ang kabuuan.

83
00:06:05,070 --> 00:06:08,780
Kabuuan ay nagiging 2 + 4, na kung saan ay 6.

84
00:06:08,780 --> 00:06:10,800
Pagkatapos namin sundin ang kaliwang sangay.

85
00:06:10,800 --> 00:06:14,970
Kung kami ay sa node na 6, pagkatapos ay namin sundin 0 upang makakuha ng sa C

86
00:06:14,970 --> 00:06:17,450
at pagkatapos ay 1 upang makakuha ng sa A.

87
00:06:17,450 --> 00:06:20,300
Kaya ngayon mayroon kaming 2 node.

88
00:06:20,300 --> 00:06:23,920
Mayroon kaming ang halaga 6 at pagkatapos namin ay mayroon ding isa pang node ng halagang 6.

89
00:06:23,920 --> 00:06:28,550
At kaya mga 2 ay hindi lamang ang 2 pinakamababang kundi pati na rin lamang ang 2 na pakaliwa,

90
00:06:28,550 --> 00:06:33,820
kaya namin sumali mga ng ibang magulang, sa kabuuan sa 12.

91
00:06:33,820 --> 00:06:36,300
Kaya dito mayroon kaming aming Huffman puno

92
00:06:36,300 --> 00:06:40,020
kung saan upang makakuha ng sa B, na lamang bit 1

93
00:06:40,020 --> 00:06:45,430
at pagkatapos ay upang makakuha ng sa A ay mayroon kaming 01 at pagkatapos C nagkakaroon 00.

94
00:06:45,430 --> 00:06:51,300
Kaya dito namin makita na talaga namin ay kumakatawan sa mga karakter na may alinman sa 1 o 2 bit

95
00:06:51,300 --> 00:06:55,160
kung saan ang B, bilang hinulaang, ay ang hindi bababa sa.

96
00:06:55,160 --> 00:07:01,730
At pagkatapos namin inaasahan C sa may ang pinaka, ngunit dahil ito ay isang maliit na puno Huffman,

97
00:07:01,730 --> 00:07:06,020
pagkatapos ng A ay kinakatawan ng 2 bit bilang laban sa isang lugar sa gitna.

98
00:07:07,820 --> 00:07:11,070
>> Lamang upang pumunta sa paglipas ng isa pang simpleng halimbawa ng Huffman tree,

99
00:07:11,070 --> 00:07:19,570
sabihin nating mayroon kang ang string "Hello."

100
00:07:19,570 --> 00:07:25,360
Ano ang gusto mong sabihin kung gaano karaming beses ang H lumitaw sa?

101
00:07:25,360 --> 00:07:34,200
H isang beses at pagkatapos e lumilitaw isang beses at pagkatapos ay mayroon kaming l lumilitaw dalawang beses

102
00:07:34,200 --> 00:07:36,580
at o lumilitaw nang isang beses.

103
00:07:36,580 --> 00:07:44,310
At kaya inaasahan namin kung aling mga titik na kinakatawan ng hindi bababa sa bilang ng mga bits?

104
00:07:44,310 --> 00:07:47,450
[Mag-aaral] l. >> L. Oo. l ay kanan.

105
00:07:47,450 --> 00:07:50,730
Inaasahan namin na l na kinakatawan ng hindi bababa sa bilang ng mga bits

106
00:07:50,730 --> 00:07:55,890
dahil l ay ginagamit pinaka sa string "Hello."

107
00:07:55,890 --> 00:08:04,280
Ano ako pagpunta sa gawin ngayon ay gumuhit ang mga node na ito.

108
00:08:04,280 --> 00:08:15,580
Mayroon akong 1, na H, at pagkatapos ay isa pang 1, na e, at pagkatapos 1, na kung saan ay o -

109
00:08:15,580 --> 00:08:23,410
ngayon ako paglalagay ng mga ito upang - at pagkatapos ay 2, na kung saan ay l.

110
00:08:23,410 --> 00:08:32,799
Pagkatapos sabihin ko ang paraan na bumuo akong Huffman puno ay upang mahanap ang 2 node na may hindi bababa sa frequency

111
00:08:32,799 --> 00:08:38,010
at gumawa ang mga ito ng mga kapatid sa pamamagitan ng paglikha ng isang magulang na node.

112
00:08:38,010 --> 00:08:41,850
Narito mayroon namin ang 3 node na may pinakamababang dalas. Ang mga ito ang lahat ng 1.

113
00:08:41,850 --> 00:08:50,620
Kaya dito pinili namin kung saan kami ay pagpunta sa link muna.

114
00:08:50,620 --> 00:08:54,850
Sabihin nating ko bang piliin ang H at ang e.

115
00:08:54,850 --> 00:09:01,150
Ang kabuuan ng 1 + 1 ay 2, ngunit node na ito ay hindi magkaroon ng isang sulat na nauugnay dito.

116
00:09:01,150 --> 00:09:04,440
Mayroon lamang hold ang halaga.

117
00:09:04,440 --> 00:09:10,950
Ngayon namin tumingin sa susunod na 2 pinakamababang frequency.

118
00:09:10,950 --> 00:09:15,590
Na ang 2 at 1. Na maaaring maging alinman ng mga 2, ngunit ako pagpunta sa pumili ng isang ito.

119
00:09:15,590 --> 00:09:18,800
Kabuuan ay 3.

120
00:09:18,800 --> 00:09:26,410
At pagkatapos ay sa wakas, ako lamang magkaroon ng 2 kaliwa, kaya't pagkatapos na magiging 5.

121
00:09:26,410 --> 00:09:32,010
Pagkatapos dito, tulad ng inaasahan, kung ako punan sa pag-encode para sa,

122
00:09:32,010 --> 00:09:37,480
1s ay palaging ang karapatan na sangay at 0s kaliwang.

123
00:09:37,480 --> 00:09:45,880
Pagkatapos kami ay may l na kinakatawan ng lang 1 bit at pagkatapos ay ang o sa pamamagitan ng 2

124
00:09:45,880 --> 00:09:52,360
at pagkatapos e ng 2 at pagkatapos ay ang H Nabibilang ang down sa 3 bit.

125
00:09:52,360 --> 00:09:59,750
Sa gayon ay maaari kang magpadala ang mensaheng ito "Kumusta" sa halip na aktwal na paggamit ng mga character

126
00:09:59,750 --> 00:10:02,760
sa pamamagitan lamang 0s at 1s.

127
00:10:02,760 --> 00:10:07,910
Gayunpaman, tandaan na sa ilang mga kaso nagkaroon kami ay gumagana sa aming dalas.

128
00:10:07,910 --> 00:10:11,900
Maaaring alinman namin sumali sa H at ang o unang siguro.

129
00:10:11,900 --> 00:10:15,730
O pagkatapos mamaya sa kapag kami ay l na kinakatawan ng 2

130
00:10:15,730 --> 00:10:19,410
pati na rin ang sumali kinakatawan ng 2, maaari naming nai-link ang alinman sa isa.

131
00:10:19,410 --> 00:10:23,630
>> At kaya kapag nagpadala ka ng 0s at 1s, na aktwal na ay hindi ginagarantiya

132
00:10:23,630 --> 00:10:27,090
na ang tatanggap sa ganap na basahin ang iyong mga mensahe karapatan off ang bat

133
00:10:27,090 --> 00:10:30,490
dahil maaaring hindi nila alam kung saan ang desisyon na ginawa mo.

134
00:10:30,490 --> 00:10:34,920
Kaya kapag kami ay pagharap sa Huffman compression,

135
00:10:34,920 --> 00:10:40,090
sa paanuman namin upang sabihin ang tatanggap ng aming mga mensahe kung paano namin nagpasya -

136
00:10:40,090 --> 00:10:43,470
Kailangan nila malaman ang ilang mga uri ng karagdagang impormasyon

137
00:10:43,470 --> 00:10:46,580
sa karagdagan sa mensahe compressed.

138
00:10:46,580 --> 00:10:51,490
Kailangan nila upang maunawaan kung ano ang puno ang aktwal na kamukha,

139
00:10:51,490 --> 00:10:55,450
kung paano ginawa namin ang aktwal na mga desisyon.

140
00:10:55,450 --> 00:10:59,100
>> Narito lang namin ginagawa ng halimbawa na batay sa aktwal na bilang ng,

141
00:10:59,100 --> 00:11:01,550
ngunit minsan maaari mo ring magkaroon ng isang puno ng Huffman

142
00:11:01,550 --> 00:11:05,760
batay sa dalas na kung saan lumitaw sa mga titik, at ito ay ang eksaktong parehong proseso.

143
00:11:05,760 --> 00:11:09,090
Narito ako pagpapahayag ito sa mga tuntunin ng porsyento o ng isang fraction,

144
00:11:09,090 --> 00:11:11,290
at kaya dito ang eksaktong parehong bagay.

145
00:11:11,290 --> 00:11:15,300
Nakahanap ako sa 2 pinakamababang, sabihin sa ilang mga ito, sa susunod na 2 pinakamababang, sabihin sa ilang mga ito,

146
00:11:15,300 --> 00:11:19,390
hanggang sa mayroon akong isang buong puno.

147
00:11:19,390 --> 00:11:23,610
Kahit na maaari naming gawin ito alinman sa paraan, kapag kami ay pagharap sa porsyento,

148
00:11:23,610 --> 00:11:27,760
ito ay nangangahulugan na namin ang paghahati ng mga bagay at pagharap sa decimal o sa halip sa kamay

149
00:11:27,760 --> 00:11:30,900
kung kami ay iniisip tungkol sa mga data kaayusan ng isang ulo.

150
00:11:30,900 --> 00:11:32,540
Ano ang gagawin namin malaman tungkol sa kamay?

151
00:11:32,540 --> 00:11:35,180
Ano ang isang karaniwang problema kapag kami ay pagharap sa kamay?

152
00:11:35,180 --> 00:11:38,600
[Mag-aaral] Imprecise aritmetika. >> Oo. Imprecision.

153
00:11:38,600 --> 00:11:43,760
Dahil lumulutang point imprecision, para sa pset kaya na ginawa namin ba

154
00:11:43,760 --> 00:11:49,450
na hindi namin mawawala ang anumang mga halaga, pagkatapos ay aktwal na kami ay pagpunta sa pagharap sa ang bilang.

155
00:11:49,450 --> 00:11:54,880
Kaya kung ikaw ay mag-isip ng isang Huffman node, kung titingnan mo bumalik sa ang istraktura dito,

156
00:11:54,880 --> 00:12:01,740
kung titingnan mo ang berdeng mga ito ay may isang dalas na nauugnay dito

157
00:12:01,740 --> 00:12:08,760
pati na rin ang mga punto upang node sa kaliwa at pati na rin ng node sa kanyang karapatan.

158
00:12:08,760 --> 00:12:13,970
At pagkatapos ay ang pulang mga doon ay mayroon ding isang character na nauugnay sa mga ito.

159
00:12:13,970 --> 00:12:18,900
Hindi namin upang gumawa ng hiwalay na mga para sa mga magulang at pagkatapos ay ang panghuling node,

160
00:12:18,900 --> 00:12:23,680
kung saan namin sumangguni sa bilang mga dahon, ngunit sa halip mga ay lamang null halaga.

161
00:12:23,680 --> 00:12:31,050
Para sa bawat node ay makikita namin ang isang character, ang simbolo na kinakatawan ng node na,

162
00:12:31,050 --> 00:12:40,490
pagkatapos ng dalas pati na rin ang isang pointer sa kaliwang bata pati na rin ang kanang anak nito.

163
00:12:40,490 --> 00:12:45,680
Mga dahon, na kung saan ay sa ibaba, ay ring node na mga payo

164
00:12:45,680 --> 00:12:49,550
sa kanilang kaliwa at sa kanilang karapatan, ngunit dahil ang mga halaga ay hindi na tumuturo sa aktwal na node,

165
00:12:49,550 --> 00:12:53,970
kung ano ang kanilang mga halaga? >> [Mag-aaral] null. >> Null. Eksakto.

166
00:12:53,970 --> 00:12:58,430
Narito ang isang halimbawa ng kung paano mo maaaring kumatawan sa dalas sa kamay,

167
00:12:58,430 --> 00:13:02,130
ngunit kami ay pagpunta sa pagharap sa ito sa integer,

168
00:13:02,130 --> 00:13:06,780
kaya lahat ko ginawa ay baguhin ang uri ng data doon.

169
00:13:06,780 --> 00:13:09,700
>> Natin pumunta sa kaunti higit pa sa isang kumplikadong halimbawa.

170
00:13:09,700 --> 00:13:13,360
Ngunit ngayon na tapos kami na ang mga simpleng mga, lamang ang parehong proseso.

171
00:13:13,360 --> 00:13:20,290
Mahanap mo ang 2 pinakamababang frequency, nagtutuos ang frequency

172
00:13:20,290 --> 00:13:22,450
at na ang bagong dalas ng iyong magulang na node,

173
00:13:22,450 --> 00:13:29,310
na pagkatapos POINTS sa kaliwa na may 0 sangay at kanan na may 1 branch.

174
00:13:29,310 --> 00:13:34,200
Kung mayroon namin ang string na "Ito ay cs50," pagkatapos namin ang bilang ng kung gaano karaming beses ay nabanggit T,

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

176
00:13:38,420 --> 00:13:42,010
Pagkatapos kung ano ang ginawa ko dito gamit ang pulang nodes ko lang nakatanim,

177
00:13:42,010 --> 00:13:48,530
Sinabi ko ako pagpunta sa kalaunan ang mga character na ito sa ilalim ng aking puno.

178
00:13:48,530 --> 00:13:51,740
Yaong na ang lahat ng mga dahon.

179
00:13:51,740 --> 00:13:58,200
Pagkatapos sa aking ginawa ay pinagsunod-sunod ko sa kanila sa pamamagitan ng dalas sa pataas na pagkakasunod-sunod,

180
00:13:58,200 --> 00:14:02,950
at ito ay talagang ang paraan na ang code ng pset ginagawa ito

181
00:14:02,950 --> 00:14:07,550
kusa itong isinasaayos ito sa pamamagitan ng dalas at pagkatapos ay ayon sa alpabeto.

182
00:14:07,550 --> 00:14:13,870
Kaya ito ay ang mga numero una at pagkatapos ay ayon sa alpabeto sa pamamagitan ng ang dalas.

183
00:14:13,870 --> 00:14:18,520
Pagkatapos kung ano ang gusto kong gawin ay Gusto ko mahanap ang 2 pinakamababang. Iyon ay 0 at 5.

184
00:14:18,520 --> 00:14:22,390
Gusto ko sabihin sa ilang mga ito, at na 2. Gusto ko magpatuloy, mahanap ang susunod na 2 pinakamababang.

185
00:14:22,390 --> 00:14:26,100
Iyon ang mga dalawang 1s, at pagkatapos ay mga naging 2 pati na rin.

186
00:14:26,100 --> 00:14:31,570
Ngayon alam ko na ang aking susunod na hakbang ay pagpunta sa pagsali sa pinakamababang numero,

187
00:14:31,570 --> 00:14:41,380
na T, ang 1, at pagkatapos ay piliin ang isa ng node na may 2 bilang ang dalas.

188
00:14:41,380 --> 00:14:44,560
Kaya dito kami ay may 3 mga pagpipilian.

189
00:14:44,560 --> 00:14:47,980
Ano ako pagpunta sa gawin para sa slide lamang biswal muling ayusin ang mga ito para sa iyo

190
00:14:47,980 --> 00:14:51,790
sa gayon ay maaari mong makita kung paano ako sa pagbuo ng mga ito.

191
00:14:51,790 --> 00:14:59,040
Ano ang code at ang iyong code sa pamamahagi ng pagpunta sa gawin ay sumali sa T

192
00:14:59,040 --> 00:15:01,410
may 0 at 5 node.

193
00:15:01,410 --> 00:15:05,060
Kaya pagkatapos na sums sa 3, at pagkatapos ay patuloy naming ang proseso.

194
00:15:05,060 --> 00:15:08,660
Ang 2 at ang 2 ngayon ay ang pinakamababang, kaya ang mga kabuuan sa 4.

195
00:15:08,660 --> 00:15:12,560
Ang bawat tao'y ng pagsunod sa ngayon? Okay.

196
00:15:12,560 --> 00:15:16,410
Pagkatapos matapos na namin ang 3 at sa 3 na kailangang idagdag,

197
00:15:16,410 --> 00:15:21,650
kaya muli ako lumipat ito sa gayon maaari mong makita ang biswal sa gayon na ito ay hindi masyadong magulo.

198
00:15:21,650 --> 00:15:25,740
Pagkatapos kami ay may 6, at pagkatapos ay ang aming huling hakbang ay ngayon na lamang namin may 2 node

199
00:15:25,740 --> 00:15:30,440
namin sabihin sa ilang mga upang gawin ang root ng aming puno, na kung saan ay 10.

200
00:15:30,440 --> 00:15:34,100
At ang bilang 10 saysay dahil ang node bawat kinakatawan,

201
00:15:34,100 --> 00:15:40,750
ang kanilang mga halaga, ang kanilang dalas numero, kung gaano karaming beses sila lumitaw sa string,

202
00:15:40,750 --> 00:15:46,350
at pagkatapos ay mayroon kaming 5 character sa aming string, kaya na saysay.

203
00:15:48,060 --> 00:15:52,320
Kung titingnan namin sa kung paano namin ang aktwal na-encode ang mga ito,

204
00:15:52,320 --> 00:15:56,580
tulad ng inaasahan, ang i at s, na lumitaw nang mas madalas

205
00:15:56,580 --> 00:16:01,350
ay kinakatawan ng fewest bilang ng mga bits.

206
00:16:03,660 --> 00:16:05,660
>> Mag-ingat dito.

207
00:16:05,660 --> 00:16:09,780
Sa Huffman puno kaso aktwal na mahalaga.

208
00:16:09,780 --> 00:16:13,670
Isang uppercase S naiiba kaysa isang lowercase s.

209
00:16:13,670 --> 00:16:21,260
Kung nagkaroon kami ng "Ito ay CS50" na may mga malalaking titik, pagkatapos ay lowercase s lamang lumitaw nang dalawang beses,

210
00:16:21,260 --> 00:16:27,120
node na may 2 dahil ang mga halaga, at pagkatapos ay uppercase S ay isang beses lamang na.

211
00:16:27,120 --> 00:16:33,440
Kaya ang iyong puno ay baguhin ang istraktura dahil iyong aktwal na may dagdag na dahon dito.

212
00:16:33,440 --> 00:16:36,900
Ngunit ang kabuuan pa rin 10.

213
00:16:36,900 --> 00:16:39,570
Na kung ano ang aktwal na kami ay pagpunta sa pagtawag sa checksum,

214
00:16:39,570 --> 00:16:44,060
ang pagdaragdag ng lahat ng mga bilang.

215
00:16:46,010 --> 00:16:50,990
>> Ngayon na namin ang saklaw ng mga puno Huffman, maaari naming sumisid sa Huff'n papamintugin, ang pset.

216
00:16:50,990 --> 00:16:52,900
Kami ay pagpunta sa magsimula sa isang seksyon ng mga katanungan,

217
00:16:52,900 --> 00:16:57,990
at ito ay pagpunta upang makakuha ka sanay sa binary mga puno at kung paano upang mapatakbo sa buong:

218
00:16:57,990 --> 00:17:03,230
pagguhit node, ang paglikha ng iyong sariling typedef struct para sa isang node,

219
00:17:03,230 --> 00:17:07,230
at nakikita kung paano maaari mong ipasok sa isang binary puno, isa na pinagsunod-sunod,

220
00:17:07,230 --> 00:17:09,050
traversing ito, at mga bagay tulad na.

221
00:17:09,050 --> 00:17:14,560
Na kaalaman ay tiyak pagpunta upang makatulong sa iyo kapag nag-dive sa bahagi ng Huff'n papamintugin

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

223
00:17:19,150 --> 00:17:26,329
Sa standard edition ng pset, ang iyong mga gawain ay ipatupad ang papamintugin,

224
00:17:26,329 --> 00:17:30,240
at sa bersyon Hacker ang iyong gawain ay ipatupad ang pagtatampo.

225
00:17:30,240 --> 00:17:38,490
Ano magtampo ang ay tumatagal ng teksto at pagkatapos ito isinasalin ito sa 0s at 1s,

226
00:17:38,490 --> 00:17:41,990
kaya ang proseso na ginawa namin sa itaas kung saan binibilang namin ang frequency

227
00:17:41,990 --> 00:17:50,970
at pagkatapos ay gumawa ng tree at pagkatapos sinabi, "Paano ako makakakuha ng T?"

228
00:17:50,970 --> 00:17:54,840
T ay kinakatawan ng 100, ang mga bagay tulad na,

229
00:17:54,840 --> 00:17:58,860
at pagkatapos magtampo ang teksto at pagkatapos ay ang output na binary.

230
00:17:58,860 --> 00:18:04,920
Ngunit din dahil alam namin na gusto naming payagan ang aming tatanggap ng mensahe

231
00:18:04,920 --> 00:18:11,790
upang muling likhain ang eksaktong parehong puno, kabilang ang impormasyon tungkol sa bilang ng dalas.

232
00:18:11,790 --> 00:18:17,980
Pagkatapos may papamintugin namin ay bibigyan ng isang binary file ng 0s at 1s

233
00:18:17,980 --> 00:18:21,740
at ibinigay rin ang impormasyon tungkol sa mga frequency.

234
00:18:21,740 --> 00:18:26,740
Tina-translate namin ang lahat ng mga 0s at 1s likod sa orihinal na mensahe na,

235
00:18:26,740 --> 00:18:29,350
kaya kami ay decompressing na.

236
00:18:29,350 --> 00:18:36,450
Kung ginagawa mo ang standard edition, hindi mo na kailangang ipatupad sa sumpong,

237
00:18:36,450 --> 00:18:39,290
kaya maaari mo lamang gamitin ang pagpapatupad ng kawani ng magtampo.

238
00:18:39,290 --> 00:18:42,080
Mayroong mga tagubilin sa spec sa kung paano gawin iyon.

239
00:18:42,080 --> 00:18:48,780
Maaari kang magpatakbo sa mga tauhan ng pagpapatupad ng pagtatampo sa isang tiyak na file ng teksto

240
00:18:48,780 --> 00:18:53,270
at pagkatapos ay gamitin na output bilang iyong input sa papamintugin.

241
00:18:53,270 --> 00:18:59,330
>> Tulad ng nabanggit ko bago, mayroon kaming maraming pamamahagi code para sa isang ito.

242
00:18:59,330 --> 00:19:01,810
Ako pagpunta upang simulan ang pagpunta sa pamamagitan nito.

243
00:19:01,810 --> 00:19:04,400
Ako pagpunta sa paggastos karamihan ng oras sa h file

244
00:19:04,400 --> 00:19:07,660
dahil sa file c, dahil mayroon kaming. h

245
00:19:07,660 --> 00:19:11,650
at na nagbibigay sa amin sa mga modelo ng mga pag-andar,

246
00:19:11,650 --> 00:19:15,520
hindi namin ganap na kailangan upang maunawaan nang eksakto -

247
00:19:15,520 --> 00:19:20,280
Kung hindi mo maunawaan kung ano ang nangyayari sa file c, pagkatapos huwag mag-alala masyadong maraming,

248
00:19:20,280 --> 00:19:23,600
ngunit tiyak na subukan upang tingnan dahil maaaring magbigay ng ilang mga pahiwatig

249
00:19:23,600 --> 00:19:29,220
at ito ay kapaki-pakinabang upang magamit sa pagbabasa ng ibang tao code.

250
00:19:38,940 --> 00:19:48,270
>> Naghahanap sa huffile.h, sa comments declares isang layer ng abstraction para sa Huffman-code na mga file.

251
00:19:48,270 --> 00:20:01,660
Kung pumunta kami, nakita namin na may isang maximum na 256 simbolo na maaari naming kailanganin ang mga code para sa.

252
00:20:01,660 --> 00:20:05,480
Kabilang dito ang lahat ang mga titik ng alpabeto - uppercase at lowercase -

253
00:20:05,480 --> 00:20:08,250
at pagkatapos ay simbolo at numero, atbp.

254
00:20:08,250 --> 00:20:11,930
Pagkatapos dito mayroon kaming isang magic bilang pagkilala Huffman-code file.

255
00:20:11,930 --> 00:20:15,890
Sa loob ng code ng Huffman sila ay pagpunta sa magkaroon ng isang tiyak na bilang ng magic

256
00:20:15,890 --> 00:20:18,560
na nauugnay sa header.

257
00:20:18,560 --> 00:20:21,110
Ito ay maaaring magmukhang lamang ng random na numero ng magic,

258
00:20:21,110 --> 00:20:27,160
ngunit kung aktwal mong isalin ito sa ASCII, pagkatapos ito aktwal na spells ang pagtatampo.

259
00:20:27,160 --> 00:20:34,290
Narito mayroon kami ng struct para Huffman-encode na file.

260
00:20:34,290 --> 00:20:39,670
Mayroong ang lahat ng mga katangian na nauugnay sa isang file magtampo.

261
00:20:39,670 --> 00:20:47,080
Pagkatapos pababa dito namin ang header para sa isang file ng magtampo, kaya tinatawag naming Huffeader

262
00:20:47,080 --> 00:20:50,810
sa halip na sa pagdaragdag ng dagdag na h dahil ito tunog ang parehong pa rin.

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

264
00:20:52,720 --> 00:20:57,790
Mayroon kaming isang magic numero na nauugnay dito.

265
00:20:57,790 --> 00:21:09,040
Kung ito ay isang aktwal na file ng magtampo, ito na ang numero sa itaas, ito magic.

266
00:21:09,040 --> 00:21:14,720
At pagkatapos ay ito ay isang array.

267
00:21:14,720 --> 00:21:18,750
Kaya para sa bawat simbolo, na kung saan may mga 256,

268
00:21:18,750 --> 00:21:24,760
ito ilista kung ano ang dalas ng mga simbolo sa loob ng file magtampo.

269
00:21:24,760 --> 00:21:28,090
At pagkatapos ay sa wakas, mayroon kaming isang checksum para sa frequency,

270
00:21:28,090 --> 00:21:32,160
na dapat ay ang kabuuan ng mga frequency.

271
00:21:32,160 --> 00:21:36,520
Kaya iyon ang Huffeader ng.

272
00:21:36,520 --> 00:21:44,600
Pagkatapos kami ay may ilang mga function na ibalik ang susunod na kaunti sa file ng magtampo

273
00:21:44,600 --> 00:21:52,580
pati na rin ang nagsusulat ng kaunti upang magtampo ang file, at pagkatapos ay ang function na dito, hfclose,

274
00:21:52,580 --> 00:21:54,650
na aktwal na isinasara ang magtampo file.

275
00:21:54,650 --> 00:21:57,290
Bago, kami ay pakikitungo na may tuwid lamang fclose,

276
00:21:57,290 --> 00:22:01,190
ngunit kapag mayroon ka ng isang file sa pagtatampo, sa halip na fclosing ito

277
00:22:01,190 --> 00:22:06,080
kung ano ang aktwal na gawin ay hfclose at hfopen ito.

278
00:22:06,080 --> 00:22:13,220
Iyon ang tiyak na mga function sa ang mga file magtampo na kami ay pagpunta sa pagharap sa.

279
00:22:13,220 --> 00:22:19,230
Pagkatapos dito namin basahin sa header at pagkatapos ay isulat ang header.

280
00:22:19,230 --> 00:22:25,700
>> Sa pamamagitan lamang ng pagbabasa ang file na. H maaari namin ang uri ng makakuha ng ideya ng kung ano ng magtampo file ay maaaring,

281
00:22:25,700 --> 00:22:32,480
kung ano ang mga katangian ito ay may, nang hindi aktwal na pagpunta sa huffile.c,

282
00:22:32,480 --> 00:22:36,750
kung saan, kung namin sumisid sa, pagpunta sa isang bit mas kumplikado.

283
00:22:36,750 --> 00:22:41,270
Mayroon ito ng lahat ng file I / O dito pagharap sa mga payo.

284
00:22:41,270 --> 00:22:48,010
Narito makita namin na kapag tinatawag naming hfread, halimbawa, pa rin ito pagharap sa fread.

285
00:22:48,010 --> 00:22:53,050
Hindi namin inaalis ng mga function ganap na, ngunit ipinapadala namin sa mga na kinuha pag-aalaga ng

286
00:22:53,050 --> 00:22:59,760
sa loob ng magtampo file sa halip ng paggawa ng lahat ng ito ating sarili.

287
00:22:59,760 --> 00:23:02,300
Maaari mong huwag mag-atubiling i-scan sa pamamagitan ng kung gusto mong malaman

288
00:23:02,300 --> 00:23:08,410
at pumunta at alisan ng balat layer likod ng kaunti.

289
00:23:20,650 --> 00:23:24,060
>> Ang susunod na file na kami ay pagpunta upang tumingin sa tree.h.

290
00:23:24,060 --> 00:23:30,210
Bago sa ang mga slide na walkthrough sinabi namin inaasahan namin Huffman node

291
00:23:30,210 --> 00:23:32,960
at nagsagawa kami ng typedef struct node.

292
00:23:32,960 --> 00:23:38,360
Inaasahan namin na ito sa isang simbolo, kadalasan, at ang 2 node bituin.

293
00:23:38,360 --> 00:23:41,870
Sa kasong ito kung anong ginagawa namin ito ay mahalagang parehong

294
00:23:41,870 --> 00:23:46,880
maliban sa halip ng node namin na tumawag sa kanila puno.

295
00:23:48,790 --> 00:23:56,760
Mayroon kaming isang function na kapag tumawag ka gumawa ng puno ito nagbabalik ka ng isang puno pointer.

296
00:23:56,760 --> 00:24:03,450
Back sa Speller, kapag ikaw ay paggawa ng isang bagong node

297
00:24:03,450 --> 00:24:11,410
sinabi mo node * bagong salita = malloc (sizeof) at mga bagay tulad na.

298
00:24:11,410 --> 00:24:17,510
Talaga, mktree ay pagpunta sa pagharap sa para sa iyo.

299
00:24:17,510 --> 00:24:20,990
Katulad nito, kapag gusto mong alisin ang isang puno,

300
00:24:20,990 --> 00:24:24,810
kaya na mahalagang pagbabakante tree kapag tapos ka na dito,

301
00:24:24,810 --> 00:24:33,790
sa halip ng tahasang pagtawag libreng on na, aktwal ka lamang gamitin ang function na rmtree

302
00:24:33,790 --> 00:24:40,360
kung saan pumasa ka sa pointer sa puno na iyon at pagkatapos ay tree.c-aalaga ng na para sa iyo.

303
00:24:40,360 --> 00:24:42,490
>> Inaasahan naming sa tree.c.

304
00:24:42,490 --> 00:24:47,240
Inaasahan namin ang parehong mga function maliban upang makita ang pagpapatupad pati na rin.

305
00:24:47,240 --> 00:24:57,720
Tulad ng inaasahan namin, kapag tumawag ka mktree mallocs ang laki ng isang puno sa isang pointer,

306
00:24:57,720 --> 00:25:03,190
ay initializes sa lahat ng ang mga halaga sa null halaga, kaya 0s o NULLs,

307
00:25:03,190 --> 00:25:08,280
at pagkatapos ay bumalik sa pointer na puno mo lang malloc'd sa iyo.

308
00:25:08,280 --> 00:25:13,340
Dito kapag tumawag ka alisin puno muna ito tinitiyak na hindi ka double pagbabakante.

309
00:25:13,340 --> 00:25:18,320
Tinitiyak na iyong aktwal na magkaroon ng isang puno na gusto mong alisin.

310
00:25:18,320 --> 00:25:23,330
Dito dahil puno Kasama rin sa mga bata nito,

311
00:25:23,330 --> 00:25:29,560
kung ano ang ginagawa ito recursively tawag-alis ng puno sa kaliwa node ng puno

312
00:25:29,560 --> 00:25:31,650
pati na rin ang karapatan node.

313
00:25:31,650 --> 00:25:37,790
Bago pinakakawalan nito isang magulang, kailangang magbakante ang mga bata at pati na rin.

314
00:25:37,790 --> 00:25:42,770
Magulang din mapagpapalit may ugat.

315
00:25:42,770 --> 00:25:46,500
Ang unang kailanman magulang, kaya tulad ng ang dakilang-dakilang-dakilang-dakilang sa tuhod

316
00:25:46,500 --> 00:25:52,130
o lola puno, muna namin magbakante pababa sa antas ng unang.

317
00:25:52,130 --> 00:25:58,490
Kaya pagbagtas sa ibaba, libreng iyon, at pagkatapos ay bumalik up, libreng mga, atbp.

318
00:26:00,400 --> 00:26:02,210
Kaya na puno.

319
00:26:02,210 --> 00:26:04,240
>> Ngayon tinitingnan namin sa kagubatan.

320
00:26:04,240 --> 00:26:09,860
Kagubatan kung saan inilagay mo ang lahat ng iyong mga puno sa Huffman.

321
00:26:09,860 --> 00:26:12,910
Ito ay nagsasabi na kami ay pagpunta sa magkaroon ng tinatawag na isang lagay ng lupa

322
00:26:12,910 --> 00:26:22,320
na naglalaman ng pointer sa isang puno pati na rin ang isang pointer sa isang lagay ng lupa na tinatawag na susunod.

323
00:26:22,320 --> 00:26:28,480
Ano ang istraktura ng ito uri ng itsura?

324
00:26:29,870 --> 00:26:32,490
Ito uri ng sabi ni banda roon.

325
00:26:34,640 --> 00:26:36,700
Mag-right sa paglipas dito.

326
00:26:37,340 --> 00:26:39,170
Ang isang naka-link na listahan.

327
00:26:39,170 --> 00:26:44,590
Nakikita namin na kapag mayroon kami ng isang lagay ng lupa ito ay tulad ng isang naka-link na listahan ng mga plots.

328
00:26:44,590 --> 00:26:53,020
Kagubatan ay tinukoy bilang isang naka-link na listahan ng mga plots,

329
00:26:53,020 --> 00:26:58,100
at kaya ang istraktura ng kagubatan lang kami pagpunta sa magkaroon ng isang pointer sa aming unang balangkas

330
00:26:58,100 --> 00:27:02,740
at isang lagay ng lupa na may puno sa loob nito o sa halip na mga punto sa isang puno

331
00:27:02,740 --> 00:27:06,190
at pagkatapos ay mga punto sa susunod na isang lagay ng lupa, kaya sa at iba pa.

332
00:27:06,190 --> 00:27:11,100
Upang gumawa ng isang gubat na tinatawag naming mkforest.

333
00:27:11,100 --> 00:27:14,930
Pagkatapos mayroon kaming ilang mga medyo kapaki-pakinabang function dito.

334
00:27:14,930 --> 00:27:23,240
Mayroon kaming pumili kung saan pumasa ka sa kagubatan at pagkatapos ang return halaga ay isang Tree *,

335
00:27:23,240 --> 00:27:25,210
isang pointer sa isang puno.

336
00:27:25,210 --> 00:27:29,370
Ano ang pick ay gawin ito pumunta sa gubat ka na tumuturo sa

337
00:27:29,370 --> 00:27:35,240
pagkatapos ay alisin ang isang puno na may pinakamababang dalas mula sa na kagubatan

338
00:27:35,240 --> 00:27:38,330
at pagkatapos ay magbibigay sa iyo ang pointer sa puno na.

339
00:27:38,330 --> 00:27:43,030
Kapag tumawag ka pumili, ang puno ay hindi umiiral sa gubat na ito,

340
00:27:43,030 --> 00:27:48,550
ngunit ang return halaga ay ang pointer na puno.

341
00:27:48,550 --> 00:27:50,730
Pagkatapos mayroon kang halaman.

342
00:27:50,730 --> 00:27:57,420
Ibinigay na pumasa ka sa isang pointer sa isang puno na may non-0 dalas,

343
00:27:57,420 --> 00:28:04,040
kung ano ang halaman ay gawin ito ay tumagal ng kagubatan, ang tree, at halaman na puno sa loob ng kagubatan.

344
00:28:04,040 --> 00:28:06,370
Narito mayroon namin rmforest.

345
00:28:06,370 --> 00:28:11,480
Katulad sa alisin ang tree, na isa lamang napalaya ang lahat ng aming mga puno para sa amin,

346
00:28:11,480 --> 00:28:16,600
alisin ang kagubatan ay libre na ang lahat ng nilalaman sa kagubatan na.

347
00:28:16,600 --> 00:28:24,890
>> Kung titingnan namin sa forest.c, makikita naming asahan na makita ang hindi bababa sa 1 rmtree utos sa doon,

348
00:28:24,890 --> 00:28:30,090
dahil sa libreng memorya sa kagubatan kung ang isang kagubatan ay puno sa,

349
00:28:30,090 --> 00:28:32,930
pagkatapos kalaunan mo ay upang alisin ang mga puno.

350
00:28:32,930 --> 00:28:41,020
Kung titingnan namin sa forest.c, mayroon kaming aming mkforest, na tulad ng iyong inaasahan namin.

351
00:28:41,020 --> 00:28:42,890
Namin malloc bagay.

352
00:28:42,890 --> 00:28:51,740
Namin initialize ang unang balangkas sa kagubatan bilang null dahil ito ay walang laman upang magsimula sa,

353
00:28:51,740 --> 00:29:05,940
pagkatapos namin makita ang pick, na magbabalik ng mga puno na may pinakamababang timbang, ang pinakamababang dalas,

354
00:29:05,940 --> 00:29:13,560
at pagkatapos ay nakakakuha mapupuksa ng na partikular na node na ang mga puntos sa puno na iyon at sa susunod,

355
00:29:13,560 --> 00:29:16,760
kaya ito ay tumatagal na ng mga naka-link na listahan ng mga gubat.

356
00:29:16,760 --> 00:29:24,510
At pagkatapos dito mayroon kaming planta, kung saan pagsingit ng puno sa naka-link na listahan.

357
00:29:24,510 --> 00:29:29,960
Ano kagubatan ay mabuti ito mapigil ang ito pinagsunod-sunod para sa amin.

358
00:29:29,960 --> 00:29:37,910
At pagkatapos ay sa wakas, mayroon kaming rmforest at, tulad ng inaasahan, mayroon kaming rmtree tinatawag doon.

359
00:29:46,650 --> 00:29:55,440
>> Pagtingin sa pamamahagi ng code sa ngayon, huffile.c ay marahil sa pamamagitan ng malayo ang hardest upang maunawaan,

360
00:29:55,440 --> 00:29:59,990
habang ang iba pang mga file ang kanilang mga sarili ay medyo simple sa sundin.

361
00:29:59,990 --> 00:30:03,090
Gamit ang aming kaalaman ng payo at ng mga naka-link na listahan at tulad,

362
00:30:03,090 --> 00:30:04,860
nagawa naming sundin medyo.

363
00:30:04,860 --> 00:30:10,500
Subalit ang lahat ng kailangan namin talagang tiyakin na namin ganap na maunawaan ang. H file

364
00:30:10,500 --> 00:30:15,840
dahil kailangan mo na pagtawag ng mga function na iyon, pagharap sa mga halagang iyon return,

365
00:30:15,840 --> 00:30:20,590
kaya tiyakin na ganap mong nauunawaan kung ano pagkilos ay pagpunta upang maisagawa ang

366
00:30:20,590 --> 00:30:24,290
tuwing tawagan ka ng isa sa mga function.

367
00:30:24,290 --> 00:30:33,020
Ngunit aktwal na pag-unawa sa loob nito ay hindi pa kinakailangan dahil mayroon kaming mga h file.

368
00:30:35,170 --> 00:30:39,490
Mayroon kaming 2 higit pang mga file na naiwan sa aming pamamahagi ng code.

369
00:30:39,490 --> 00:30:41,640
>> Hayaan ang mga tumingin sa dump.

370
00:30:41,640 --> 00:30:47,230
Dump sa pamamagitan ng komento dito tumatagal ng isang Huffman-compressed file

371
00:30:47,230 --> 00:30:55,580
at pagkatapos ay ibig sabihin at lungkot lahat ng nilalaman nito ang.

372
00:31:01,010 --> 00:31:04,260
Narito namin makita na ang pagtawag ng hfopen.

373
00:31:04,260 --> 00:31:10,770
Ito ay uri ng mirror file * input = fopen,

374
00:31:10,770 --> 00:31:13,500
at pagkatapos ay pumasa ka sa impormasyon.

375
00:31:13,500 --> 00:31:18,240
Ito ay halos katulad maliban sa halip ng isang file * ka pagpasa sa isang Huffile;

376
00:31:18,240 --> 00:31:22,030
sa halip na fopen ka pagpasa sa hfopen.

377
00:31:22,030 --> 00:31:29,280
Narito namin basahin sa unang header, na kung saan ay uri ng katulad sa kung paano namin basahin sa header

378
00:31:29,280 --> 00:31:33,580
para sa bitmap na file.

379
00:31:33,580 --> 00:31:38,000
Kung anong ginagawa namin dito ang check upang makita kung ang impormasyon ng header

380
00:31:38,000 --> 00:31:44,330
naglalaman ng tamang bilang ng magic na nagpapahiwatig na ito ay isang aktwal na file magtampo,

381
00:31:44,330 --> 00:31:53,610
pagkatapos ang lahat ng mga tseke upang matiyak na ang mga file na bukas namin ay isang aktwal na huffed file o hindi.

382
00:31:53,610 --> 00:32:05,330
Kung ano ang ginagawa ng output ang mga frequency ng lahat ng mga simbolo na maaari naming makita

383
00:32:05,330 --> 00:32:09,790
sa loob ng isang terminal sa isang graphical table.

384
00:32:09,790 --> 00:32:15,240
Ang bahagi na ito ay maging kapaki-pakinabang.

385
00:32:15,240 --> 00:32:24,680
Ito ay isang bit at bumabasa bit sa pamamagitan ng bit sa variable bit at pagkatapos ng mga Kopya ito.

386
00:32:28,220 --> 00:32:35,430
Kaya kung ako ay upang tawagan ang dump sa hth.bin, kung saan ay ang resulta ng huffing ng isang file

387
00:32:35,430 --> 00:32:39,490
gamit ang solusyon ng kawani, Gusto ko makakuha ng ito.

388
00:32:39,490 --> 00:32:46,000
Ito ay outputting ang lahat ng mga character na ito at pagkatapos paglalagay ng dalas sa kung saan lumilitaw ang mga ito.

389
00:32:46,000 --> 00:32:51,180
Kung titingnan namin, karamihan sa kanila ay 0s maliban para sa: H, na lumilitaw dalawang beses,

390
00:32:51,180 --> 00:32:54,820
at pagkatapos ay T, na lumilitaw sa sandaling.

391
00:32:54,820 --> 00:33:07,860
At pagkatapos dito mayroon kaming ang aktwal na mensahe sa 0s at 1s.

392
00:33:07,860 --> 00:33:15,450
Kung titingnan namin sa hth.txt, na siguro ang orihinal na mensahe na huffed,

393
00:33:15,450 --> 00:33:22,490
inaasahan namin upang makita ang ilang Hs at TS sa doon.

394
00:33:22,490 --> 00:33:28,720
Sa partikular, inaasahan namin upang makita ang 1 T at 2 Hs.

395
00:33:32,510 --> 00:33:37,440
Narito ang namin sa hth.txt. Ito sa katunayan ay may HTH.

396
00:33:37,440 --> 00:33:41,270
Kasama sa doon, bagaman hindi namin makita ito, ay isang newline character.

397
00:33:41,270 --> 00:33:53,190
Ang magtampo file hth.bin din page-encode ang newline character pati na rin.

398
00:33:55,680 --> 00:34:01,330
Dito dahil alam namin na ang order ay HTH at pagkatapos newline,

399
00:34:01,330 --> 00:34:07,340
maaari naming makita na marahil H ay kinakatawan ng isang solong 1

400
00:34:07,340 --> 00:34:17,120
at pagkatapos T ay marahil 01 at pagkatapos ay sa susunod na H ay 1 pati na rin

401
00:34:17,120 --> 00:34:21,139
at pagkatapos ay mayroon kaming isang newline na ipinahiwatig sa pamamagitan ng dalawang 0s.

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

403
00:34:26,530 --> 00:34:31,600
>> At pagkatapos ay sa wakas, dahil kami ay pagharap sa maramihang mga. C at. H file,

404
00:34:31,600 --> 00:34:36,350
kami ay isang medyo kumplikadong argumento sa tagatala,

405
00:34:36,350 --> 00:34:40,460
at kaya dito mayroon kaming Makefile na gumagawa ng dump para sa iyo.

406
00:34:40,460 --> 00:34:47,070
Pero sa totoo, mayroon kang upang pumunta tungkol sa paggawa ng iyong sariling puff.c file.

407
00:34:47,070 --> 00:34:54,330
Makefile ang na aktwal na ay hindi humarap sa na puff.c para sa iyo.

408
00:34:54,330 --> 00:34:59,310
Aalis Kami ay na hanggang sa iyo upang i-edit ang Makefile.

409
00:34:59,310 --> 00:35:05,930
Kapag nagpasok ka ng isang utos tulad gawin ang lahat, halimbawa, ito ay gumawa ng lahat ng mga ito para sa iyo.

410
00:35:05,930 --> 00:35:10,760
Huwag mag-atubiling upang tumingin sa mga halimbawa ng mga Makefile mula sa nakaraang pset

411
00:35:10,760 --> 00:35:17,400
pati na rin ang pagpunta off ng isang ito upang makita kung paano mo maaaring magagawang upang gawin ang iyong file sa papamintugin

412
00:35:17,400 --> 00:35:20,260
sa pamamagitan ng pag-edit na ito Makefile.

413
00:35:20,260 --> 00:35:22,730
Na ang tungkol dito para sa aming code ng pamamahagi.

414
00:35:22,730 --> 00:35:28,380
>> Sandaling namin na nakuha sa pamamagitan ng na, pagkatapos ay narito ang isa pang paalala lamang

415
00:35:28,380 --> 00:35:30,980
ng kung paano namin ay pagpunta sa pagharap sa node Huffman.

416
00:35:30,980 --> 00:35:35,400
Hindi Kami ay pagpunta sa ay ang pagtawag sa kanila node ito; kami ay pagpunta sa ay pagtawag sa kanila ng mga puno

417
00:35:35,400 --> 00:35:39,260
kung saan kami ay pagpunta sa ay kumakatawan sa kanilang simbolo na may isang pansamantalang trabaho,

418
00:35:39,260 --> 00:35:43,340
kanilang dalas, ang bilang ng mga pangyayari, na may isang integer.

419
00:35:43,340 --> 00:35:47,370
Ginagamit namin na dahil ito ay mas tumpak na kaysa sa isang Float.

420
00:35:47,370 --> 00:35:52,980
At pagkatapos kami ay may isa pang pointer sa kaliwa anak pati na rin ang karapatan na bata.

421
00:35:52,980 --> 00:35:59,630
Kagubatan A, tulad ng nakita natin, ay isang naka-link na listahan ng mga puno.

422
00:35:59,630 --> 00:36:04,670
Sa huli, kapag kami ay pagbuo ng aming magtampo file,

423
00:36:04,670 --> 00:36:07,580
nais namin na ang aming kagubatan na naglalaman ng 1 puno lang -

424
00:36:07,580 --> 00:36:12,420
1 tree, 1 root na may maraming mga bata.

425
00:36:12,420 --> 00:36:20,840
Mas maaga sa kapag lamang namin ay paggawa ng aming mga puno Huffman,

426
00:36:20,840 --> 00:36:25,360
nagsimula kaming pamamagitan ng paglalagay ng lahat ng node papunta sa aming screen

427
00:36:25,360 --> 00:36:27,790
at sinasabi namin ay pagpunta sa mga node,

428
00:36:27,790 --> 00:36:32,920
kalaunan sila ay pagpunta sa mga dahon, at ito ang kanilang mga simbolo, ito ang kanilang dalas.

429
00:36:32,920 --> 00:36:42,070
Sa aming kagubatan kung lang namin 3 titik, na ng kagubatan ng 3 puno.

430
00:36:42,070 --> 00:36:45,150
At pagkatapos ay bilang pumunta kami sa, kapag idinagdag namin ang unang magulang,

431
00:36:45,150 --> 00:36:48,080
ginawa namin ng kagubatan ng 2 puno.

432
00:36:48,080 --> 00:36:54,930
Inalis namin 2 ng mga bata mula sa aming kagubatan at pagkatapos ay pinalitan ito na may isang pangunahing node

433
00:36:54,930 --> 00:36:58,820
na may mga 2 node bilang bata.

434
00:36:58,820 --> 00:37:05,600
At pagkatapos ay sa wakas, ang aming huling hakbang sa paggawa ng aming halimbawa sa mga Bilang, BS, at CS

435
00:37:05,600 --> 00:37:08,030
ay gawin ang panghuling magulang,

436
00:37:08,030 --> 00:37:13,190
at kaya pagkatapos na dalhin ang sa aming kabuuang bilang ng mga puno sa gubat sa 1.

437
00:37:13,190 --> 00:37:18,140
Ba ang lahat makita kung paano simulan mo na may maraming mga puno sa iyong kagubatan

438
00:37:18,140 --> 00:37:22,520
at nagtatapos na may 1? Okay. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Ano ang gagawin namin kailangan gawin para papamintugin?

440
00:37:28,110 --> 00:37:37,110
Ano ang kailangan naming gawin ay matiyak na, gaya ng lagi, bigyan sila sa amin ang tamang uri ng input

441
00:37:37,110 --> 00:37:39,090
upang maaari naming aktwal na patakbuhin ang program.

442
00:37:39,090 --> 00:37:43,130
Sa kasong ito sila ay pagpunta sa pagbigay sa amin pagkatapos ng kanilang unang command-line na argumento

443
00:37:43,130 --> 00:37:53,440
2 higit pa: ang mga file na gusto naming upang magbawas ng bigat at ang output ng decompressed file.

444
00:37:53,440 --> 00:38:00,410
Ngunit sa sandaling sigurado kami na pumasa sila sa amin sa tamang halaga ng mga halaga,

445
00:38:00,410 --> 00:38:05,820
nais naming matiyak na ang input ay isang magtampo file o hindi.

446
00:38:05,820 --> 00:38:10,420
At pagkatapos ay sa sandaling gina-garantiya namin na ang isang file magtampo, gusto naming upang bumuo ang aming puno,

447
00:38:10,420 --> 00:38:20,940
bumuo ng tree tulad na tumutugma sa puno na ang taong nagpadala sa mensahe binuo.

448
00:38:20,940 --> 00:38:25,840
Pagkatapos pagkatapos bumuo kami ng tree, pagkatapos ay maaari naming harapin ang 0s at 1s na sila nakapasa sa,

449
00:38:25,840 --> 00:38:29,590
sundin ang mga kahabaan ng aming puno dahil ito ay magkakahawig,

450
00:38:29,590 --> 00:38:33,510
at pagkatapos ay isulat na mensahe, bigyang-kahulugan ang mga bits pabalik sa char.

451
00:38:33,510 --> 00:38:35,880
At pagkatapos ay sa dulo dahil kami ay pagharap sa mga payo dito,

452
00:38:35,880 --> 00:38:38,110
nais naming tiyakin na hindi namin anumang mga paglabas ng memory

453
00:38:38,110 --> 00:38:41,330
at na namin libreng lahat.

454
00:38:42,820 --> 00:38:46,430
>> Pagtiyak ng tamang paggamit ng lumang sumbrero para sa amin sa pamamagitan ng ngayon.

455
00:38:46,430 --> 00:38:51,980
Namin sa isang input, na ang pangalan ng file sa papamintugin,

456
00:38:51,980 --> 00:38:56,010
at pagkatapos naming tukuyin ang isang output,

457
00:38:56,010 --> 00:39:01,580
kaya ang pangalan ng file para sa puffed output, na text file.

458
00:39:03,680 --> 00:39:08,820
Na ang paggamit. At ngayon nais naming matiyak na input ay huffed o hindi.

459
00:39:08,820 --> 00:39:16,420
Iniisip pabalik, ay Mayroon bang anumang sa pamamahagi ng code na maaaring makatulong sa amin

460
00:39:16,420 --> 00:39:21,570
sa pag-unawa kung ang isang file ay huffed o hindi?

461
00:39:21,570 --> 00:39:26,910
Nagkaroon ng impormasyon sa huffile.c tungkol sa Huffeader.

462
00:39:26,910 --> 00:39:33,430
Alam namin na ang bawat pagtatampo file ay may Huffeader nauugnay dito na may magic numero

463
00:39:33,430 --> 00:39:37,240
pati na rin ang isang hanay ng mga frequency para sa bawat simbolo

464
00:39:37,240 --> 00:39:39,570
pati na rin bilang isang checksum.

465
00:39:39,570 --> 00:39:43,180
Alam namin na, ngunit din namin kinuha ng isang silip sa dump.c,

466
00:39:43,180 --> 00:39:49,120
kung saan ito ay pagbabasa sa isang file ng magtampo.

467
00:39:49,120 --> 00:39:53,990
At iba pa upang gawin iyon, ay upang suriin kung ito ay talagang ay huffed o hindi.

468
00:39:53,990 --> 00:40:03,380
Kaya marahil maaari naming gamitin ang dump.c bilang isang istraktura para sa aming puff.c.

469
00:40:03,380 --> 00:40:12,680
Bumalik sa pset 4 kapag nagkaroon kami file copy.c na kinopya sa RGB triple

470
00:40:12,680 --> 00:40:14,860
at kahulugan namin na para sa sinong may kagagawan at Baguhin ang laki,

471
00:40:14,860 --> 00:40:20,390
katulad, kung ano ang maaari mong gawin ay lamang patakbuhin ang command na tulad ng cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
at gamitin ang ilan ng code doon.

473
00:40:23,600 --> 00:40:28,210
Gayunpaman, hindi ito ay pagpunta sa tapat ng isang proseso sa

474
00:40:28,210 --> 00:40:33,010
para sa pagsalin ng iyong dump.c sa puff.c,

475
00:40:33,010 --> 00:40:36,160
ngunit hindi bababa sa ito ay nagbibigay sa iyo ng isang lugar upang simulan ang

476
00:40:36,160 --> 00:40:40,540
kung paano upang matiyak na ang input ay talagang huffed o hindi

477
00:40:40,540 --> 00:40:43,240
pati na rin ng ilang mga iba pang mga bagay.

478
00:40:45,930 --> 00:40:50,250
Natiyak namin ang tamang paggamit at natiyak na input ay huffed.

479
00:40:50,250 --> 00:40:53,570
Bawat oras na ginawa namin na namin ginawa ang aming tamang error checking,

480
00:40:53,570 --> 00:41:01,520
kaya bumabalik at sa pagtigil sa pag-andar kung ang ilang pagkabigo nangyayari, kung may problema.

481
00:41:01,520 --> 00:41:07,170
>> Ngayon kung ano ang gusto naming gawin ay bumuo ng ang aktwal na puno.

482
00:41:08,840 --> 00:41:12,640
Kung titingnan namin sa Forest, may 2 pangunahing function

483
00:41:12,640 --> 00:41:15,800
na kami ay pagpunta sa nais upang maging napaka-pamilyar sa.

484
00:41:15,800 --> 00:41:23,870
Ang Boolean function na halaman na non-0 tree dalas sa loob ng aming kagubatan halaman.

485
00:41:23,870 --> 00:41:29,250
At kaya pumasa ka sa isang pointer sa isang gubat at ng pointer sa isang puno.

486
00:41:32,530 --> 00:41:40,340
Quick tanong: Gaano karaming mga kagubatan ay mayroon ka kapag ikaw ay pagbuo ng isang puno Huffman?

487
00:41:44,210 --> 00:41:46,650
Aming kagubatan ay tulad ng ating canvas, tama?

488
00:41:46,650 --> 00:41:50,800
Kaya lamang namin ang 1 kagubatan, ngunit kami ay pagpunta sa magkaroon ng maramihang mga puno.

489
00:41:50,800 --> 00:41:57,590
Kaya bago tumawag ka ng halaman, baka ka pagpunta sa gusto mong gawin ang iyong mga kagubatan.

490
00:41:57,590 --> 00:42:04,430
May isang utos para sa kung tiningnan mo sa forest.h sa kung paano maaari mong gumawa ng kagubatan.

491
00:42:04,430 --> 00:42:09,270
Maaari mong planta ng isang puno. Alam namin kung paano gawin iyon.

492
00:42:09,270 --> 00:42:11,590
At pagkatapos maaari ka ring pumili ng isang puno mula sa kagubatan,

493
00:42:11,590 --> 00:42:17,540
pag-aalis ng isang puno na may pinakamababang timbang at nagbibigay sa iyo ng ang pointer iyon.

494
00:42:17,540 --> 00:42:23,090
Iniisip pabalik sa kapag kami ay paggawa ng mga halimbawa na ating sarili,

495
00:42:23,090 --> 00:42:27,980
kapag kami ay pagguhit ito, lamang namin lamang na idinagdag ang link.

496
00:42:27,980 --> 00:42:31,680
Ngunit dito sa halip ng pagdaragdag ng mga link,

497
00:42:31,680 --> 00:42:40,630
-isip ng mas habang ikaw ay alisin ang 2 ng mga node at pagkatapos ay palitan ito ng ibang.

498
00:42:40,630 --> 00:42:44,200
Upang ipahayag na sa mga tuntunin ng pagpili at planting,

499
00:42:44,200 --> 00:42:48,840
ka pagpili ng 2 puno at pagkatapos planting isa pang puno

500
00:42:48,840 --> 00:42:54,060
na may mga 2 puno na iyong pinili bilang mga bata.

501
00:42:57,950 --> 00:43:05,280
Upang bumuo ng puno Huffman, maaari mong basahin sa mga simbolo at mga frequency upang

502
00:43:05,280 --> 00:43:10,790
dahil Huffeader ang nagbibigay na sa iyo,

503
00:43:10,790 --> 00:43:14,250
nagbibigay sa iyo ng isang array ng mga frequency.

504
00:43:14,250 --> 00:43:19,660
Sa gayon maaari mong magpatuloy at huwag pansinin ang anumang bagay na may 0 sa ito

505
00:43:19,660 --> 00:43:23,760
dahil hindi namin nais 256 dahon sa dulo nito.

506
00:43:23,760 --> 00:43:27,960
Nais lamang namin ang bilang ng mga dahon na character

507
00:43:27,960 --> 00:43:31,600
na aktwal na ginagamit sa file.

508
00:43:31,600 --> 00:43:37,590
Maaari mong basahin sa mga simbolo, at ang bawat isa sa mga simbolo na may non-0 frequency,

509
00:43:37,590 --> 00:43:40,440
mga pagpunta sa maging ang mga puno.

510
00:43:40,440 --> 00:43:45,990
Ano ang maaari mong gawin sa bawat oras na basahin sa isang non-0 simbolo ng dalas,

511
00:43:45,990 --> 00:43:50,660
maaari mong planta na puno sa kagubatan.

512
00:43:50,660 --> 00:43:56,620
Sandaling planta mo ang mga puno sa gubat, maaari mong sumali sa mga puno bilang mga kapatid,

513
00:43:56,620 --> 00:44:01,130
kaya bumalik sa planting at pagpili kung saan pumili ka 2 at pagkatapos ay planta 1,

514
00:44:01,130 --> 00:44:05,820
kung saan na 1 na halaman mo ang magulang ng 2 bata na pinili mo.

515
00:44:05,820 --> 00:44:11,160
Kaya ang iyong pagtatapos resulta ng isang puno sa iyong kagubatan.

516
00:44:16,180 --> 00:44:18,170
Kung paano buuin mo ang iyong puno.

517
00:44:18,170 --> 00:44:21,850
>> May ilang mga bagay na maaaring magkamali dito

518
00:44:21,850 --> 00:44:26,580
dahil kami ay pagharap sa paggawa ng mga bagong puno at pagharap sa mga payo at mga bagay tulad na.

519
00:44:26,580 --> 00:44:30,450
Bago kapag kami ay pagharap sa mga payo,

520
00:44:30,450 --> 00:44:36,580
tuwing malloc'd namin namin nais upang matiyak na hindi ito bumalik sa amin ng Null pointer halaga.

521
00:44:36,580 --> 00:44:42,770
Kaya sa ilang mga hakbang sa loob ng prosesong ito pagpunta sa ilang mga kaso

522
00:44:42,770 --> 00:44:45,920
kung saan ang iyong programa ay maaaring mabigo.

523
00:44:45,920 --> 00:44:51,310
Ano ang gusto mong gawin ay nais mong tiyakin mong pangasiwaan ang mga error,

524
00:44:51,310 --> 00:44:54,580
at sa spec sinasabi nito upang mahawakan ang mga ito maganda,

525
00:44:54,580 --> 00:45:00,280
kaya bang i-print ang isang mensahe sa user na nagsasabi sa kanila kung bakit ang programa ay may na umalis

526
00:45:00,280 --> 00:45:03,050
at pagkatapos ay agad na mag-quit ito.

527
00:45:03,050 --> 00:45:09,490
Upang gawin ito error handling, tandaan na nais mong upang suriin ito

528
00:45:09,490 --> 00:45:12,160
bawat solong oras na may isang pagkabigo.

529
00:45:12,160 --> 00:45:14,660
Bawat solong oras na nagsasagawa ka ng isang bagong pointer

530
00:45:14,660 --> 00:45:17,040
nais mong upang matiyak na na matagumpay.

531
00:45:17,040 --> 00:45:20,320
Bago kung ano ang ginamit namin gawin ay gumawa ng isang bagong pointer at malloc ito,

532
00:45:20,320 --> 00:45:22,380
at pagkatapos ay naming suriin kung ang pointer na null.

533
00:45:22,380 --> 00:45:25,670
Kaya pagpunta sa ilang mga pagkakataon kung saan mo lang gawin na,

534
00:45:25,670 --> 00:45:28,610
ngunit minsan aktwal ka pagtawag ng isang function

535
00:45:28,610 --> 00:45:33,100
at sa loob ng function na iyon, na ang isa na ginagawa ang mallocing.

536
00:45:33,100 --> 00:45:39,110
Sa kasong iyon, kung tiningnan namin pabalik sa ilang mga pag-andar sa loob ng code,

537
00:45:39,110 --> 00:45:42,260
Ang ilan sa kanila ay Boolean function.

538
00:45:42,260 --> 00:45:48,480
Sa abstract kaso kung kami ay may isang Boolean function na tinatawag foo,

539
00:45:48,480 --> 00:45:54,580
talaga, maaari naming ipagpalagay na sa karagdagan sa paggawa ng anumang foo ginagawa,

540
00:45:54,580 --> 00:45:57,210
dahil ito ay isang Boolean function na ito, nagbalik tama o mali -

541
00:45:57,210 --> 00:46:01,300
totoo kung matagumpay, maling kung hindi.

542
00:46:01,300 --> 00:46:06,270
Kaya gusto namin upang suriin kung ang return halaga ng foo ay totoo o hindi.

543
00:46:06,270 --> 00:46:10,400
Kung ito ang maling, na nangangahulugan na kami ay pagpunta sa gusto upang i-print ang ilang mga uri ng mensahe

544
00:46:10,400 --> 00:46:14,390
at pagkatapos ay mag-quit sa programa.

545
00:46:14,390 --> 00:46:18,530
Ano ang gusto naming gawin ay suriin ang return halaga ng foo.

546
00:46:18,530 --> 00:46:23,310
Kung nagbabalik ng foo maling, alam namin na namin na nakaranas kami ng ilang mga uri ng error

547
00:46:23,310 --> 00:46:25,110
at kailangan namin na umalis ang aming programa.

548
00:46:25,110 --> 00:46:35,600
Ang isang paraan upang gawin ito ay isang kalagayan kung saan ang aktwal na function na mismo ang iyong kundisyon.

549
00:46:35,600 --> 00:46:39,320
Sabihing foo tumatagal sa x.

550
00:46:39,320 --> 00:46:43,390
Maaari naming bilang isang kondisyon kung (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Talaga, na nangangahulugan kung sa dulo ng pag-execute foo ito nagbabalik totoo,

552
00:46:50,900 --> 00:46:57,390
maaari naming gawin ito dahil ang function ay upang suriin foo

553
00:46:57,390 --> 00:47:00,500
upang suriin ang buong kondisyon.

554
00:47:00,500 --> 00:47:06,500
Kaya pagkatapos na kung paano mo maaaring gawin ang isang bagay kung ang function ay nagbabalik ng tunay at matagumpay ang.

555
00:47:06,500 --> 00:47:11,800
Ngunit kapag hindi mo ang error checking, gusto mo lamang na umalis kung ang iyong function na ay nagbabalik ng maling.

556
00:47:11,800 --> 00:47:16,090
Ano ang maaari mong gawin ay idagdag lamang ng == mali o idagdag lamang ang isang putok sa unahan nito

557
00:47:16,090 --> 00:47:21,010
at pagkatapos ay mayroon kang kung (! foo).

558
00:47:21,010 --> 00:47:29,540
Sa loob ng katawan ng kondisyon na mayroon ka ng lahat ng handling ng error,

559
00:47:29,540 --> 00:47:36,940
kaya i, "Hindi malikha ang puno na ito" at pagkatapos ay bumalik sa 1 o isang bagay tulad na.

560
00:47:36,940 --> 00:47:43,340
Ano na, bagaman, na kahit foo ibinalik maling -

561
00:47:43,340 --> 00:47:46,980
Sabihing foo nagbabalik totoo.

562
00:47:46,980 --> 00:47:51,060
Pagkatapos hindi mo na kailangang tumawag muli ang foo. Na ang isang karaniwang maling kuru-kuro.

563
00:47:51,060 --> 00:47:54,730
Dahil ito ay sa iyong kondisyon, na ito sinusuri,

564
00:47:54,730 --> 00:47:59,430
kaya mo na ang resulta kung gumagamit ka ng puno o isang bagay tulad na

565
00:47:59,430 --> 00:48:01,840
o halaman o pick o isang bagay.

566
00:48:01,840 --> 00:48:07,460
Ito ay mayroon ng halagang iyon. Na ito ay pinaandar.

567
00:48:07,460 --> 00:48:10,730
Kaya ito ay kapaki-pakinabang na gumamit ng Boolean function bilang ang kundisyon

568
00:48:10,730 --> 00:48:13,890
dahil mo man o hindi aktwal na isagawa ang katawan ng loop,

569
00:48:13,890 --> 00:48:18,030
executes-andar pa rin.

570
00:48:22,070 --> 00:48:27,330
>> Ang aming ikalawang sa huling hakbang ay sumusulat ang mensahe sa file.

571
00:48:27,330 --> 00:48:33,070
Sa sandaling namin buuin ang Huffman puno, pagkatapos pagsulat ang mensahe sa file ay medyo direkta.

572
00:48:33,070 --> 00:48:39,260
Medyo direkta ngayon upang sundin lamang ang mga 0s at 1s.

573
00:48:39,260 --> 00:48:45,480
At ito sa pamamagitan ng convention na alam namin na sa isang puno ng Huffman 0s ipahiwatig ang natitira

574
00:48:45,480 --> 00:48:48,360
at 1s ipahiwatig karapatan.

575
00:48:48,360 --> 00:48:53,540
Kaya pagkatapos kung ikaw basahin unti-unti, sa bawat oras na makakakuha ka ng 0

576
00:48:53,540 --> 00:48:59,100
makikita mo sundin ang kaliwang sangay, at bawat oras na basahin mo sa 1

577
00:48:59,100 --> 00:49:02,100
ka pagpunta sa sundin ang mga karapatan sangay.

578
00:49:02,100 --> 00:49:07,570
At pagkatapos ka pagpunta upang magpatuloy hanggang maabot ang isang dahon

579
00:49:07,570 --> 00:49:11,550
dahil ang mga dahon sa dulo ng sanga.

580
00:49:11,550 --> 00:49:16,870
Paano maaari naming sabihin kung kami ay pindutin ang isang dahon o hindi?

581
00:49:19,800 --> 00:49:21,690
Sinabi namin ito dati.

582
00:49:21,690 --> 00:49:24,040
[Mag-aaral] Kung ang mga payo ay null. >> Oo.

583
00:49:24,040 --> 00:49:32,220
Maaari naming sabihin kung namin pindutin ang dahon kung ang mga payo sa parehong kaliwa at kanang mga puno null.

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

585
00:49:34,110 --> 00:49:40,320
Alam namin na gusto namin na basahin ang unti-unti sa aming pagtatampo file.

586
00:49:43,870 --> 00:49:51,220
Tulad ng nakita natin bago sa dump.c, kung ano ang kanilang ginawa nila basahin sa unti-unti sa file magtampo

587
00:49:51,220 --> 00:49:54,560
at naka-print kung ano ang mga bits ay.

588
00:49:54,560 --> 00:49:58,430
Hindi Kami ay pagpunta sa paggawa na. Kami ay pagpunta sa paggawa ng isang bagay na mas kumplikado ang ng kaunti.

589
00:49:58,430 --> 00:50:03,620
Ngunit kung ano ang maaari naming gawin ay maaari namin na bit ng code na bumabasa in sa bit.

590
00:50:03,620 --> 00:50:10,250
Narito mayroon namin ang integer bit na kumakatawan sa kasalukuyang bit na hindi namin sa.

591
00:50:10,250 --> 00:50:15,520
Ito ay tumatagal ng pag-aalaga ng iterating ang lahat ng mga piraso sa file hanggang maabot ang dulo ng file.

592
00:50:15,520 --> 00:50:21,270
Batay sa na, pagkatapos ikaw ay pagpunta sa nais na magkaroon ng ilang mga uri ng iterator

593
00:50:21,270 --> 00:50:26,760
sa pagbagtas ang iyong puno.

594
00:50:26,760 --> 00:50:31,460
At pagkatapos ay batay sa kung ang bit sa 0 o 1,

595
00:50:31,460 --> 00:50:36,920
ka pagpunta sa nais na ilipat na iterator sa kaliwa o ilipat ito sa kanan

596
00:50:36,920 --> 00:50:44,080
ang lahat ng paraan hanggang maabot ang isang dahon, kaya ang lahat ng mga paraan hanggang sa na node na ikaw ay nasa

597
00:50:44,080 --> 00:50:48,260
ay hindi tumuturo sa anumang higit pang mga node.

598
00:50:48,260 --> 00:50:54,300
Bakit maaari naming gawin ito sa Huffman file ngunit hindi Morse code?

599
00:50:54,300 --> 00:50:56,610
Dahil sa Morse code ng kaunting kalabuan.

600
00:50:56,610 --> 00:51:04,440
Maaaring namin na tulad ng, oh paghihintay, kami pindutin ang isang sulat sa kahabaan ng paraan, kaya maaaring ito ay ang aming sulat,

601
00:51:04,440 --> 00:51:08,150
samantalang kung patuloy namin ng kaunti lamang na, pagkatapos ay namin ang pindutin ang sulat ng isa pang.

602
00:51:08,150 --> 00:51:13,110
Ngunit na hindi pagpunta sa mangyayari sa Huffman pag-encode,

603
00:51:13,110 --> 00:51:17,540
upang maaari naming magpahinga panatag na ang tanging paraan na kami ay pagpunta upang maabot ang isang character

604
00:51:17,540 --> 00:51:23,480
kung ang kaliwa at kanang mga bata na node null.

605
00:51:28,280 --> 00:51:32,350
>> Panghuli, nais naming upang magbakante ang lahat ng aming memory.

606
00:51:32,350 --> 00:51:37,420
Nais naming sa parehong malapit sa pagtatampo file na namin ang pagharap sa

607
00:51:37,420 --> 00:51:41,940
pati na rin alisin ang lahat ng mga puno sa ating kagubatan.

608
00:51:41,940 --> 00:51:46,470
Batay sa iyong pagpapatupad, marahil ka pagpunta sa nais upang tumawag alisin kagubatan

609
00:51:46,470 --> 00:51:49,780
sa halip ng mga aktwal na pagpunta sa pamamagitan ng lahat ng mga puno sa iyong sarili.

610
00:51:49,780 --> 00:51:53,430
Ngunit kung gumawa ka ng anumang pansamantalang puno, makikita mo nais na magbakante na.

611
00:51:53,430 --> 00:51:59,060
Alam mo pinakamahusay na ang iyong code, kaya alam mo kung saan ka paglaan ng memorya.

612
00:51:59,060 --> 00:52:04,330
At kaya kung pumunta ka sa, magsimula sa pamamagitan ng kahit Control F'ing para sa malloc,

613
00:52:04,330 --> 00:52:08,330
nakikita tuwing malloc at siguraduhin na magbakante mo ang lahat ng na

614
00:52:08,330 --> 00:52:10,190
ngunit pagkatapos lamang ng pagpunta sa pamamagitan ng iyong code,

615
00:52:10,190 --> 00:52:14,260
unawa kung saan maaari mong inilalaan memory.

616
00:52:14,260 --> 00:52:21,340
Karaniwan maaari mong lang sabihin, "Sa dulo ng isang file lamang ako upang alisin ang kagubatan sa aking kagubatan,"

617
00:52:21,340 --> 00:52:23,850
kaya talaga i-clear na memorya, libreng,

618
00:52:23,850 --> 00:52:28,310
"At pagkatapos din ako pagpunta upang isara ang file at pagkatapos ay ang aking programa ay na umalis."

619
00:52:28,310 --> 00:52:33,810
Ngunit na lamang ang oras na tabla ng iyong programa?

620
00:52:33,810 --> 00:52:37,880
Hindi, dahil minsan may maaaring isang error na nangyari.

621
00:52:37,880 --> 00:52:42,080
Siguro hindi namin ma-buksan ang isang file o hindi namin maaaring gumawa ng isa pang tree

622
00:52:42,080 --> 00:52:49,340
o ilang mga uri ng error na nangyari sa proseso ng paglalaan ng memorya at kaya ibinalik null.

623
00:52:49,340 --> 00:52:56,710
May error na nangyari at pagkatapos ay ibinalik namin at huminto.

624
00:52:56,710 --> 00:53:02,040
Kaya nais mong upang matiyak na ang anumang posibleng pagkakataon na ang iyong programa ay maaaring mag-quit,

625
00:53:02,040 --> 00:53:06,980
gusto mong magbakante lahat ng iyong memory doon.

626
00:53:06,980 --> 00:53:13,370
Hindi ito lamang sa pinakadulo ng pangunahing function na lumabas mula sa iyong code.

627
00:53:13,370 --> 00:53:20,780
Nais mong upang tumingin pabalik sa bawat pagkakataon na ang iyong code potensyal na maaaring bumalik nang maaga

628
00:53:20,780 --> 00:53:25,070
at pagkatapos libreng anumang memory saysay.

629
00:53:25,070 --> 00:53:30,830
Sinasabi mo ay tinatawag na gumawa ng kagubatan at ibinalik maling.

630
00:53:30,830 --> 00:53:34,230
Pagkatapos ay malamang na hindi ka kailangang alisin ang iyong kagubatan

631
00:53:34,230 --> 00:53:37,080
dahil hindi mo pa ng kagubatan.

632
00:53:37,080 --> 00:53:42,130
Ngunit sa bawat punto sa code kung saan maaari kang bumalik maaga

633
00:53:42,130 --> 00:53:46,160
nais mong tiyakin na magbakante kang anumang mga posibleng memory.

634
00:53:46,160 --> 00:53:50,020
>> Kaya kapag kami ay pagharap sa pagbabakante memory at pagkakaroon ng mga potensyal na paglabas,

635
00:53:50,020 --> 00:53:55,440
gusto naming upang hindi lamang gamitin ang aming paghatol at ang aming logic

636
00:53:55,440 --> 00:54:01,850
ngunit ring gamitin Valgrind upang matukoy kung namin ang napalaya ang lahat ng aming mga memory maayos o hindi.

637
00:54:01,850 --> 00:54:09,460
Maaari mong patakbuhin ang Valgrind sa papamintugin at pagkatapos ay mayroon kang ring magpasa

638
00:54:09,460 --> 00:54:14,020
ang tamang bilang ng mga command-line argumento sa Valgrind.

639
00:54:14,020 --> 00:54:18,100
Maaari kang magpatakbo ng na, ngunit ang output bit misteriyoso.

640
00:54:18,100 --> 00:54:21,630
Namin na nakuha ng isang bit na ginamit sa ito sa Speller, ngunit kailangan pa rin namin ng kaunti pang tulong,

641
00:54:21,630 --> 00:54:26,450
kaya pagkatapos tumatakbo ito na may ilang higit pang mga flag tulad ng sa mahayag-check = buong,

642
00:54:26,450 --> 00:54:32,040
na malamang na bigyan kami ng ilang mga mas kapaki-pakinabang na output sa Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Pagkatapos ay isa pang kapaki-pakinabang na tip kapag ikaw ay pag-debug ay ang diff utos.

644
00:54:39,040 --> 00:54:48,520
Maaari mong ma-access ang pagpapatupad sa mga tauhan ng magtampo, patakbuhin na sa isang text file,

645
00:54:48,520 --> 00:54:55,400
at pagkatapos output ito sa isang binary file, isang binary file ng magtampo, maging tukoy.

646
00:54:55,400 --> 00:54:59,440
Pagkatapos kung nagpapatakbo ka ang iyong sariling papamintugin sa binary file na iyon,

647
00:54:59,440 --> 00:55:03,950
pagkatapos perpektong, iyong outputted text file ay pagpunta sa magkakahawig

648
00:55:03,950 --> 00:55:08,200
sa orihinal na ang pumasa ka.

649
00:55:08,200 --> 00:55:15,150
Narito ako gumagamit ng hth.txt bilang halimbawa, at na uusapang tungkol sa iyong spec.

650
00:55:15,150 --> 00:55:21,040
Iyon ay literal lamang HTH at pagkatapos ay isang newline.

651
00:55:21,040 --> 00:55:30,970
Ngunit talagang huwag mag-atubiling at tiyak na ikaw ay hinihikayat na gumamit ng mas mahabang halimbawa

652
00:55:30,970 --> 00:55:32,620
para sa iyong text file.

653
00:55:32,620 --> 00:55:38,110
>> Maaari ka ring kumuha ng shot siguro pigain at pagkatapos decompressing

654
00:55:38,110 --> 00:55:41,600
ilan sa ang mga file na ginamit mo sa Speller tulad ng Digmaan at Kapayapaan

655
00:55:41,600 --> 00:55:46,710
o Jane Austen o isang bagay tulad na - na uri ng mga cool na - o Austin Powers,

656
00:55:46,710 --> 00:55:51,880
uri ng pakikitungo na may mas malaking mga file dahil hindi namin ay bumaba ito

657
00:55:51,880 --> 00:55:55,590
kung ginamit namin sa susunod na tool dito, ls-l.

658
00:55:55,590 --> 00:56:01,150
Kami ay ginagamit sa ls, kung saan talaga ay naglilista ng lahat ng mga nilalaman sa aming kasalukuyang direktoryo.

659
00:56:01,150 --> 00:56:07,860
Pagpasa sa bandila-l na aktwal na ipinapakita ang laki ng mga file.

660
00:56:07,860 --> 00:56:12,690
Kung pupunta ka sa pamamagitan ng spec pset, aktwal na ito ay nagtuturo sa iyo sa pamamagitan ng paglikha ng binary file,

661
00:56:12,690 --> 00:56:16,590
ng huffing ito, at nakikita mo na para sa napakaliit na file

662
00:56:16,590 --> 00:56:23,910
ang gastos ng espasyo ng pigain ito at nagta-translate ang lahat ng impormasyon na iyon

663
00:56:23,910 --> 00:56:26,980
ng lahat ng mga frequency at mga bagay tulad na outweighs ang aktwal na benepisyo

664
00:56:26,980 --> 00:56:30,000
ng pigain ang file sa unang lugar.

665
00:56:30,000 --> 00:56:37,450
Ngunit kung nagpapatakbo ka sa ilang mga mas mahabang mga tekstong file, pagkatapos ay maaari mong makita na simulan mo upang makakuha ng ilang mga pakinabang

666
00:56:37,450 --> 00:56:40,930
sa pigain ng mga file.

667
00:56:40,930 --> 00:56:46,210
>> At pagkatapos ay sa wakas, mayroon namin ang aming lumang pal GDB, na kung saan ay tiyak na darating sa madaling-gamiting.

668
00:56:48,360 --> 00:56:55,320
>> Namin may anumang mga katanungan sa mga puno ng pagtatampo o ang proseso marahil ng paggawa ng mga puno

669
00:56:55,320 --> 00:56:58,590
o anumang iba pang mga mga tanong sa Huff'n papamintugin?

670
00:57:00,680 --> 00:57:02,570
Okay. Magtatagal ako sa paligid para sa isang bit.

671
00:57:02,570 --> 00:57:06,570
>> Salamat, sa lahat. Ito walkthrough 6. At good luck.

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