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

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

3
00:00:04,810 --> 00:00:07,240
[Mae hyn yn CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Helo bawb, a chroeso i Walkthrough 6: Huff'n pwff.

5
00:00:12,180 --> 00:00:17,440
Yn Huff'n pwff hyn yr ydym yn ei wneud yn mynd i fod yn delio gyda ffeil cywasgedig Huffman

6
00:00:17,440 --> 00:00:20,740
ac yna puffing yn ôl i fyny, felly mae'n ddatgywasgu,

7
00:00:20,740 --> 00:00:25,810
fel y gallwn gyfieithu o'r 0s a 1s bod y defnyddiwr yn anfon

8
00:00:25,810 --> 00:00:30,660
ac addasu yn ôl yn y testun gwreiddiol.

9
00:00:30,660 --> 00:00:34,360
Pset 6 yn mynd i fod yn 'n bert oera oherwydd eich bod yn mynd i weld rhai o'r offer

10
00:00:34,360 --> 00:00:41,730
a ddefnyddiwyd gennych yn pset 4 a 5 a pset math o cyfuno i 1 cysyniad yn eithaf taclus

11
00:00:41,730 --> 00:00:43,830
pan fyddwch yn dod i feddwl am y peth.

12
00:00:43,830 --> 00:00:50,110
>> Hefyd, gellid dadlau, roedd pset 4 a 5 y psets mwyaf heriol a oedd gennym i gynnig.

13
00:00:50,110 --> 00:00:53,950
Felly o hyn, rydym yn cael y pset 1 yn fwy yn y C,

14
00:00:53,950 --> 00:00:56,480
ac yna ar ôl ein bod ar i raglenni ar y we.

15
00:00:56,480 --> 00:01:02,310
Felly llongyfarch eich hunain i gael dros y twmpath anoddaf yn CS50.

16
00:01:03,630 --> 00:01:09,760
>> Symud ymlaen i Huff'n pwff, mae ein pecyn cymorth ar gyfer y pset yn mynd i fod yn goed Huffman,

17
00:01:09,760 --> 00:01:14,700
felly deall nid yn unig sut y coed gwaith deuaidd ond hefyd yn benodol coed Huffman,

18
00:01:14,700 --> 00:01:16,240
sut y maent yn adeiladu.

19
00:01:16,240 --> 00:01:20,210
Ac yna rydym yn mynd i gael llawer o god dosbarthu yn y pset,

20
00:01:20,210 --> 00:01:22,480
a byddwn yn dod i weld bod mewn gwirionedd yn rhai o'r cod

21
00:01:22,480 --> 00:01:24,670
Efallai na fyddwn yn gallu deall yn llawn eto,

22
00:01:24,670 --> 00:01:30,080
ac felly bydd y rheini ar y. ffeiliau c, ond yna eu cyd-fynd. h ffeiliau

23
00:01:30,080 --> 00:01:34,300
fydd yn rhoi i ni ddigon o ddealltwriaeth bod angen er mwyn bod yn gwybod sut y swyddogaethau hynny yn gweithio

24
00:01:34,300 --> 00:01:38,100
neu o leiaf yr hyn y maent i fod i'w wneud - mae eu mewnbynnau ac allbynnau -

25
00:01:38,100 --> 00:01:40,760
hyd yn oed os nad ydym yn gwybod beth sy'n digwydd yn y blwch du

26
00:01:40,760 --> 00:01:44,090
neu nad ydynt yn deall beth sy'n digwydd yn y blwch du mewn.

27
00:01:44,090 --> 00:01:49,400
Ac yna yn olaf, fel arfer, yr ydym yn delio â strwythurau data newydd,

28
00:01:49,400 --> 00:01:51,840
mathau penodol o nodau sy'n cyfeirio at bethau penodol,

29
00:01:51,840 --> 00:01:56,080
ac felly dyma cael pin a phapur, nid yn unig ar gyfer y broses ddylunio

30
00:01:56,080 --> 00:01:58,470
a phan fyddwch yn ceisio at chyfrif i maes sut y dylai eich pset weithio

31
00:01:58,470 --> 00:02:00,520
ond hefyd yn ystod debugging.

32
00:02:00,520 --> 00:02:06,140
Gallwch gael GDB ochr yn ochr â'ch pen a phapur wrth i chi fynd i lawr yr hyn y mae'r gwerthoedd yn,

33
00:02:06,140 --> 00:02:09,320
lle mae eich saethau yn pwyntio, a phethau fel 'na.

34
00:02:09,320 --> 00:02:13,720
>> Yn gyntaf gadewch i ni edrych ar goed Huffman.

35
00:02:13,720 --> 00:02:19,600
Coed Huffman yn goed deuaidd, sy'n golygu bod gan bob nod yn unig y mae 2 o blant.

36
00:02:19,600 --> 00:02:24,870
Mewn coed Huffman y nodwedd yw bod y gwerthoedd mwyaf cyffredin

37
00:02:24,870 --> 00:02:27,140
yn cael eu cynrychioli gan y darnau lleiaf.

38
00:02:27,140 --> 00:02:32,690
Gwelsom enghreifftiau mewn darlith y côd Morse, pa fath o cyfunol rhai llythrennau.

39
00:02:32,690 --> 00:02:38,030
Os ydych yn ceisio i gyfieithu A neu E, er enghraifft,

40
00:02:38,030 --> 00:02:43,940
rydych chi'n cyfieithu yn aml, felly yn hytrach na gorfod defnyddio'r set lawn o ddarnau

41
00:02:43,940 --> 00:02:48,640
ddyrannu ar gyfer y math hwnnw data arferol, byddwch yn cywasgu i lawr i lai,

42
00:02:48,640 --> 00:02:53,730
ac yna y llythyrau hynny sy'n cael eu cynrychioli yn llai aml yn cael eu cynrychioli gyda darnau hirach

43
00:02:53,730 --> 00:02:59,840
oherwydd gallwch fforddio bod pan fyddwch yn pwyso a mesur y amleddau bod y llythyrau yn ymddangos.

44
00:02:59,840 --> 00:03:03,020
Mae gennym yr un syniad yma mewn coed Huffman

45
00:03:03,020 --> 00:03:12,360
ble rydym yn gwneud cadwyn, math o lwybr i gyrraedd y cymeriadau penodol.

46
00:03:12,360 --> 00:03:14,470
Ac yna y cymeriadau sydd â'r amledd y rhan fwyaf o

47
00:03:14,470 --> 00:03:17,940
yn mynd i gael ei gynrychioli gyda'r darnau lleiaf.

48
00:03:17,940 --> 00:03:22,020
>> Mae'r ffordd yr ydych yn adeiladu coeden Huffman

49
00:03:22,020 --> 00:03:27,430
yw drwy osod yr holl gymeriadau sy'n ymddangos yn y testun

50
00:03:27,430 --> 00:03:30,630
a chyfrifo eu hamlder, pa mor aml y maent yn ymddangos.

51
00:03:30,630 --> 00:03:33,880
Gallai hyn naill ai fod yn gyfrif o faint o weithiau y llythyrau hynny yn ymddangos

52
00:03:33,880 --> 00:03:40,270
neu efallai canran o blith yr holl gymeriadau faint o bob un yn ymddangos.

53
00:03:40,270 --> 00:03:44,270
Ac felly yr hyn yr ydych ei wneud yw unwaith y byddwch wedi hynny i gyd allan mapio,

54
00:03:44,270 --> 00:03:49,060
yna rydych yn chwilio am y 2 amleddau isaf ac yna ymuno â hwy fel brodyr a chwiorydd

55
00:03:49,060 --> 00:03:55,660
lle yna mae'r nod rhiant amledd sef y swm ei 2 o blant.

56
00:03:55,660 --> 00:04:00,870
Ac yna chi gan gonfensiwn dweud bod y nod chwith,

57
00:04:00,870 --> 00:04:03,770
eich bod yn dilyn hynny drwy ddilyn y gangen 0,

58
00:04:03,770 --> 00:04:08,140
ac yna y nod rightmost yw cangen 1.

59
00:04:08,140 --> 00:04:16,040
Fel y gwelsom mewn côd Morse, roedd y Gotcha un sydd os ydych yn unig a gafodd Canu a'r Canu

60
00:04:16,040 --> 00:04:18,120
roedd yn amwys.

61
00:04:18,120 --> 00:04:22,430
Gallai fod yn naill ai 1 llythyr neu gallai fod yn ddilyniant o 2 lythyr.

62
00:04:22,430 --> 00:04:27,790
Ac felly pa Huffman coed yn ei wneud yw oherwydd yn ôl natur y cymeriadau

63
00:04:27,790 --> 00:04:34,140
neu ein cymeriadau go iawn terfynol yn y nodau olaf ar y gangen -

64
00:04:34,140 --> 00:04:39,300
rydym yn cyfeirio at y rhai fel dail - yn rhinwedd na ellir cael unrhyw amwysedd

65
00:04:39,300 --> 00:04:45,160
o ran pa lythyren ydych yn ceisio amgodio â chyfres o ddarnau

66
00:04:45,160 --> 00:04:50,670
gan nad oes unman ar hyd y darnau sy'n cynrychioli 1 llythyr

67
00:04:50,670 --> 00:04:55,960
byddwch yn dod ar draws llythyr arall cyfan, ac ni fydd yna unrhyw ddryswch yno.

68
00:04:55,960 --> 00:04:58,430
Ond byddwn yn mynd i mewn i enghreifftiau y gallwch guys mewn gwirionedd yn gweld bod

69
00:04:58,430 --> 00:05:02,120
hytrach na ni jyst dweud wrthych fod hynny'n wir.

70
00:05:02,120 --> 00:05:06,390
>> Gadewch i ni edrych ar enghraifft syml o goeden Huffman.

71
00:05:06,390 --> 00:05:09,380
Mae gen i llinyn yma yw 12 nod o hyd.

72
00:05:09,380 --> 00:05:14,010
Mae gen i 4 Fel, 6 B, C a 2.

73
00:05:14,010 --> 00:05:17,270
Byddai fy cam cyntaf fydd cyfrif.

74
00:05:17,270 --> 00:05:20,760
Faint o weithiau y bydd A yn ymddangos? Mae'n ymddangos 4 gwaith yn y llinyn.

75
00:05:20,760 --> 00:05:25,060
B yn ymddangos 6 gwaith, a C yn ymddangos 2 waith.

76
00:05:25,060 --> 00:05:28,970
Yn naturiol, yr wyf i'n mynd i ddweud fy mod i'n defnyddio B gan amlaf,

77
00:05:28,970 --> 00:05:35,970
felly yr wyf am i gynrychioli B gyda'r nifer lleiaf o ddarnau, y nifer lleiaf o 0au ac 1.

78
00:05:35,970 --> 00:05:42,600
Ac yna Rwyf hefyd yn mynd i ddisgwyl C i'w gwneud yn ofynnol y swm mwyaf o 0s a 1s yn ogystal.

79
00:05:42,600 --> 00:05:48,550
Yn gyntaf beth wnes i yma yn yr wyf yn eu gosod mewn trefn esgynnol o ran amlder.

80
00:05:48,550 --> 00:05:52,710
Rydym yn gweld bod y C a'r A, dyna o'n 2 amleddau isaf.

81
00:05:52,710 --> 00:06:00,290
Rydym yn creu nod rhiant, ac nad yw nod rhiant yn cael llythyr sy'n gysylltiedig ag ef,

82
00:06:00,290 --> 00:06:05,070
ond mae ganddo amledd, sef y swm.

83
00:06:05,070 --> 00:06:08,780
Mae'r swm yn 2 + 4, sydd 6.

84
00:06:08,780 --> 00:06:10,800
Yna rydym yn dilyn y gangen chwith.

85
00:06:10,800 --> 00:06:14,970
Pe baem ar y nod 6, yna byddem yn dilyn 0 i ddod i C

86
00:06:14,970 --> 00:06:17,450
ac yna 1 i fynd i A.

87
00:06:17,450 --> 00:06:20,300
Felly, nawr rydym yn cael 2 nodau.

88
00:06:20,300 --> 00:06:23,920
Mae gennym y gwerth 6 ac yna rydym hefyd wedi arall nod gyda'r gwerth 6.

89
00:06:23,920 --> 00:06:28,550
Ac felly y rhai 2 yn nid yn unig y 2 isaf ond hefyd dim ond y 2 sydd yn cael eu gadael,

90
00:06:28,550 --> 00:06:33,820
felly byddwn yn ymuno rhai gan riant arall, gyda'r swm yn 12.

91
00:06:33,820 --> 00:06:36,300
Felly dyma ni wedi ein Huffman coed

92
00:06:36,300 --> 00:06:40,020
ble i fynd i B, byddai hynny yn unig fod y darn 1

93
00:06:40,020 --> 00:06:45,430
ac yna i fynd i A byddai gennym 01 a wedyn C yn cael 00.

94
00:06:45,430 --> 00:06:51,300
Felly, yma rydym yn gweld bod y bôn rydym yn cynrychioli'r chars gyda naill ai 1 neu 2 ddarnau

95
00:06:51,300 --> 00:06:55,160
lle y B, fel y rhagwelwyd, y lleiaf.

96
00:06:55,160 --> 00:07:01,730
Ac yna rydym wedi disgwyl C i gael y mwyaf, ond gan ei fod yn gymaint o goeden Huffman bach,

97
00:07:01,730 --> 00:07:06,020
yna yr A yn cael ei gynrychioli hefyd gan 2 darnau yn hytrach na rywle yn y canol.

98
00:07:07,820 --> 00:07:11,070
>> Dim ond i fynd dros enghraifft arall syml y goeden Huffman,

99
00:07:11,070 --> 00:07:19,570
ddweud eich bod yn cael y llinyn "Helo."

100
00:07:19,570 --> 00:07:25,360
Beth ydych yn ei wneud yn gyntaf y byddech yn dweud faint o weithiau y bydd H yn ymddangos yn hyn?

101
00:07:25,360 --> 00:07:34,200
H ymddangos unwaith ac yna e yn ymddangos unwaith ac yna mae gennym l ymddangos ddwywaith

102
00:07:34,200 --> 00:07:36,580
ac o ymddangos unwaith.

103
00:07:36,580 --> 00:07:44,310
Ac felly, rydym yn disgwyl y llythyr i gael ei gynrychioli gan y nifer lleiaf o ddarnau?

104
00:07:44,310 --> 00:07:47,450
[Myfyrwyr] l. >> L. Yeah. l yn iawn.

105
00:07:47,450 --> 00:07:50,730
Rydym yn disgwyl l i gael ei gynrychioli gan y nifer lleiaf o ddarnau

106
00:07:50,730 --> 00:07:55,890
oherwydd l yn cael ei ddefnyddio fwyaf yn y llinyn "Helo."

107
00:07:55,890 --> 00:08:04,280
Yr hyn yr wyf i'n mynd i wneud yn awr yw tynnu allan y nodau.

108
00:08:04,280 --> 00:08:15,580
Mae gen i 1, sef H, ac yna un arall 1, sy'n e, ac yna 1, sef o -

109
00:08:15,580 --> 00:08:23,410
ar hyn o bryd rwy'n eu rhoi mewn trefn - ac yna 2, sydd yn l.

110
00:08:23,410 --> 00:08:32,799
Yna mi ddweud y ffordd yr wyf yn adeiladu coeden Huffman yw dod o hyd y 2 nodau â'r amlderau lleiaf

111
00:08:32,799 --> 00:08:38,010
a'u gwneud yn frodyr a chwiorydd drwy greu nod rhiant.

112
00:08:38,010 --> 00:08:41,850
Yma, mae gennym 3 nodau gyda'r amlder isaf. Maen nhw i gyd 1.

113
00:08:41,850 --> 00:08:50,620
Felly, yma rydym yn dewis pa un yr ydym yn mynd i gysylltu yn gyntaf.

114
00:08:50,620 --> 00:08:54,850
Lets 'ddeud i'n dewis y H a e.

115
00:08:54,850 --> 00:09:01,150
Mae swm o 1 + 1 yn 2, ond nid yw hyn nôd yn cael llythyr sy'n gysylltiedig ag ef.

116
00:09:01,150 --> 00:09:04,440
'I jyst yn dal y gwerth.

117
00:09:04,440 --> 00:09:10,950
Nawr rydym yn edrych ar y 2 nesaf amleddau isaf.

118
00:09:10,950 --> 00:09:15,590
Dyna 2 a 1. Gallai hynny fod naill neu'r llall o'r 2, ond rwy'n mynd i ddewis yr un.

119
00:09:15,590 --> 00:09:18,800
Mae'r swm yn 3.

120
00:09:18,800 --> 00:09:26,410
Ac yna yn olaf, dim ond yn cael 2 chwith, fel yna mae hynny'n dod yn 5.

121
00:09:26,410 --> 00:09:32,010
Yna dyma, yn ôl y disgwyl, os wyf yn llenwi'r amgodio ar gyfer hynny,

122
00:09:32,010 --> 00:09:37,480
1s bob amser yn y gangen iawn ac 0s yw'r un sydd ar ôl.

123
00:09:37,480 --> 00:09:45,880
Yna, mae gennym l cynrychioli gan ddim ond 1 ychydig ac yna y o gan 2

124
00:09:45,880 --> 00:09:52,360
ac yna yr e gan 2 ac yna yn disgyn i lawr H i 3 ddarnau.

125
00:09:52,360 --> 00:09:59,750
Felly gallwch drosglwyddo neges hon "Helo" yn hytrach na mewn gwirionedd yn defnyddio'r cymeriadau

126
00:09:59,750 --> 00:10:02,760
gan ychydig 0s a 1s.

127
00:10:02,760 --> 00:10:07,910
Fodd bynnag, cofiwch bod mewn sawl achos roedd gennym gysylltiadau gyda'n amlder.

128
00:10:07,910 --> 00:10:11,900
Gallem fod wedi ymuno naill ai H a 1 o efallai.

129
00:10:11,900 --> 00:10:15,730
Neu wedyn yn nes ymlaen pan gawsom y l a gynrychiolir gan 2

130
00:10:15,730 --> 00:10:19,410
yn ogystal â'r ymuno ag un a gynrychiolir gan 2, gallem fod wedi cysylltu naill ai un.

131
00:10:19,410 --> 00:10:23,630
>> Ac felly pan fyddwch yn anfon y 0s a 1s, nad yw mewn gwirionedd yn gwarantu

132
00:10:23,630 --> 00:10:27,090
y gall y derbynnydd yn llawn yn darllen eich neges dde oddi ar y ystlumod

133
00:10:27,090 --> 00:10:30,490
oherwydd efallai na fyddant yn gwybod pa benderfyniad a wnaed gennych.

134
00:10:30,490 --> 00:10:34,920
Felly, pan fyddwn yn delio â Huffman cywasgu,

135
00:10:34,920 --> 00:10:40,090
rhywsut mae'n rhaid i ni ddweud wrth y derbynnydd ein neges Sut y gwnaethom benderfynu -

136
00:10:40,090 --> 00:10:43,470
Mae angen iddynt wybod rhyw fath o wybodaeth ychwanegol

137
00:10:43,470 --> 00:10:46,580
yn ychwanegol at y neges cywasgedig.

138
00:10:46,580 --> 00:10:51,490
Mae angen iddynt ddeall yr hyn y goeden mewn gwirionedd yn edrych fel,

139
00:10:51,490 --> 00:10:55,450
sut yr ydym mewn gwirionedd yn gwneud y penderfyniadau hynny.

140
00:10:55,450 --> 00:10:59,100
>> Dyma yr oeddem yn ei wneud enghreifftiau yn seiliedig ar y cyfrif ei hunan,

141
00:10:59,100 --> 00:11:01,550
ond weithiau gallwch hefyd gael coeden Huffman

142
00:11:01,550 --> 00:11:05,760
yn seiliedig ar pa mor aml y llythyrau yn ymddangos, ac mae'n yr un broses yn union.

143
00:11:05,760 --> 00:11:09,090
Dyma dwi'n ei fynegi yn nhermau canrannau neu ffracsiwn,

144
00:11:09,090 --> 00:11:11,290
ac felly dyma yr un peth yn union.

145
00:11:11,290 --> 00:11:15,300
Rwy'n dod o hyd y 2 isaf, crynhoi nhw, y 2 isaf nesaf, crynhoi nhw,

146
00:11:15,300 --> 00:11:19,390
hyd nes i mi gael coeden llawn.

147
00:11:19,390 --> 00:11:23,610
Hyd yn oed er y gallai rydym yn ei wneud naill ffordd neu'r llall, pan fyddwn ni'n delio gyda chanrannau,

148
00:11:23,610 --> 00:11:27,760
sy'n golygu ein bod yn rhannu pethau a delio â degolion neu yn hytrach arnofio

149
00:11:27,760 --> 00:11:30,900
os ydym yn meddwl am strwythurau data pennaeth.

150
00:11:30,900 --> 00:11:32,540
Beth ydyn ni'n ei wybod am arnofion?

151
00:11:32,540 --> 00:11:35,180
Beth yw problem gyffredin pan fyddwn ni'n delio gyda fflotiau?

152
00:11:35,180 --> 00:11:38,600
[Myfyrwyr] rhifyddeg amwys. >> Yeah. Anfanyldeb.

153
00:11:38,600 --> 00:11:43,760
Oherwydd anfanyldeb pwynt arnawf, ar gyfer y pset fel ein bod yn gwneud yn siwr

154
00:11:43,760 --> 00:11:49,450
nad ydym yn colli unrhyw werthoedd, yna rydym yn wir yn mynd i fod yn delio gyda'r cyfrif.

155
00:11:49,450 --> 00:11:54,880
Felly, os ydych yn meddwl am nod Huffman, os edrychwch yn ôl at y strwythur yma,

156
00:11:54,880 --> 00:12:01,740
os ydych yn edrych ar y rhai gwyrdd mae ganddo amledd sy'n gysylltiedig ag ef

157
00:12:01,740 --> 00:12:08,760
yn ogystal gan ei fod yn cyfeirio at y nod at ei chwith yn ogystal â nod at ei dde.

158
00:12:08,760 --> 00:12:13,970
Ac yna y rhai coch hefyd yn meddu ar gymeriad sy'n gysylltiedig â hwy.

159
00:12:13,970 --> 00:12:18,900
Nid ydym yn mynd i wneud rhai ar wahân ar gyfer y rhieni ac yna y nodau terfynol,

160
00:12:18,900 --> 00:12:23,680
yr ydym yn cyfeirio ato fel dail, ond yn hytrach bydd rhai dim ond yn cael gwerthoedd null.

161
00:12:23,680 --> 00:12:31,050
Am bob nod bydd gennym cymeriad, y symbol bod y nod yn cynrychioli,

162
00:12:31,050 --> 00:12:40,490
yna amledd yn ogystal â pwyntydd i'w plentyn chwith yn ogystal â'i blentyn i'r dde.

163
00:12:40,490 --> 00:12:45,680
Byddai'r dail, sydd ar y gwaelod un, hefyd yn cael awgrymiadau nod

164
00:12:45,680 --> 00:12:49,550
i'w chwith ac i'w hawl, ond gan nad yw'r gwerthoedd yn cael eu cyfeirio at nodau gwirioneddol,

165
00:12:49,550 --> 00:12:53,970
beth fyddai eu gwerth fod? >> [Myfyrwyr] NULL. >> NULL. Yn union.

166
00:12:53,970 --> 00:12:58,430
Dyma enghraifft o sut y gallech chi cynrychioli'r amlder yn arnofio,

167
00:12:58,430 --> 00:13:02,130
ond rydym yn mynd i fod yn delio ag ef gyda chyfanrifau,

168
00:13:02,130 --> 00:13:06,780
felly wnes i gyd yn newid y math data yno.

169
00:13:06,780 --> 00:13:09,700
>> Gadewch i ni fynd ymlaen i ychydig yn fwy am enghraifft cymhleth.

170
00:13:09,700 --> 00:13:13,360
Ond yn awr ein bod wedi gwneud y rhai syml, dim ond un broses.

171
00:13:13,360 --> 00:13:20,290
Gallwch ddod o hyd y 2 amleddau isaf, crynhoi yr amleddau

172
00:13:20,290 --> 00:13:22,450
a dyna pa mor aml newydd eich nod rhiant,

173
00:13:22,450 --> 00:13:29,310
sydd wedyn yn tynnu sylw at ei chwith gyda changen 0 a hawl gyda changen 1.

174
00:13:29,310 --> 00:13:34,200
Os oes gennym y llinyn "Mae hwn yn cs50," yna yr ydym yn cyfrif faint o weithiau yn cael ei grybwyll T,

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

176
00:13:38,420 --> 00:13:42,010
Yna beth wnes i yma yw gyda nodau coch Fi jyst plannu,

177
00:13:42,010 --> 00:13:48,530
Dywedais fy mod i'n mynd i gael y cymeriadau yn y pen draw ar waelod fy nghoeden.

178
00:13:48,530 --> 00:13:51,740
Mae'r rhai yn mynd i fod yr holl ddail.

179
00:13:51,740 --> 00:13:58,200
Yna beth wnes i yw fy mod ddatrys iddynt gan amlder yn nhrefn esgynnol,

180
00:13:58,200 --> 00:14:02,950
ac mae hyn mewn gwirionedd yn y ffordd y mae'r cod pset mae'n

181
00:14:02,950 --> 00:14:07,550
a yw'n fath iddo gan amlder ac yna yn nhrefn yr wyddor.

182
00:14:07,550 --> 00:14:13,870
Felly, mae wedi y niferoedd yn gyntaf ac yna yn nhrefn yr wyddor gan amlder.

183
00:14:13,870 --> 00:14:18,520
Yna beth fyddwn i'n ei wneud yw byddwn yn dod o hyd i'r isaf 2. Dyna 0 a 5.

184
00:14:18,520 --> 00:14:22,390
Byddwn yn disgrifio'r nhw, a dyna 2. Yna byddwn yn parhau, dod o hyd i'r nesaf 2 isaf.

185
00:14:22,390 --> 00:14:26,100
Dyna'r 1s dau, ac yna dod yn rhai 2 yn ogystal.

186
00:14:26,100 --> 00:14:31,570
Nawr rwy'n gwybod bod fy cam nesaf yn mynd i fod yn ymuno â'r nifer isaf,

187
00:14:31,570 --> 00:14:41,380
sef y T, 1, ac yna dewis un o'r nodau sydd wedi 2 fel pa mor aml.

188
00:14:41,380 --> 00:14:44,560
Felly yma mae gennym 3 opsiwn.

189
00:14:44,560 --> 00:14:47,980
Yr hyn yr wyf i'n mynd i wneud am y sleid yn unig weledol ail-drefnu ar eich cyfer

190
00:14:47,980 --> 00:14:51,790
fel y gallwch weld sut rwy'n adeiladu i fyny.

191
00:14:51,790 --> 00:14:59,040
Beth fyddai'r cod a'ch cod dosbarthu yn mynd i wneud yn cael ei ymuno yr un T

192
00:14:59,040 --> 00:15:01,410
gyda'r nod 0 a 5.

193
00:15:01,410 --> 00:15:05,060
Felly, yna y symiau i 3, ac yna rydym yn parhau â'r broses.

194
00:15:05,060 --> 00:15:08,660
Mae'r 2 a 2 yn awr yn yr isaf, felly, yna rhai sy'n swm i 4.

195
00:15:08,660 --> 00:15:12,560
Mae pawb yn dilyn hyd yn hyn? Iawn.

196
00:15:12,560 --> 00:15:16,410
Yna, ar ôl bod gennym y 3 a'r 3 y mae angen eu hadio at ei gilydd,

197
00:15:16,410 --> 00:15:21,650
hynny eto Im 'jyst yn newid' i fel y gallwch weld ei olwg fel nad yw'n mynd yn rhy anniben.

198
00:15:21,650 --> 00:15:25,740
Yna, mae gennym 6, ac yna mae ein cam olaf yw yn awr ein bod dim ond 2 nodau

199
00:15:25,740 --> 00:15:30,440
rydym yn crynhoi rhai i wneud y wraidd ein coeden, sef 10.

200
00:15:30,440 --> 00:15:34,100
Ac mae'r rhif 10 yn gwneud synnwyr oherwydd bod gan bob nod cynrychioli,

201
00:15:34,100 --> 00:15:40,750
eu gwerth, eu rhif amlder, roedd faint o weithiau y maent yn ymddangos yn y llinyn,

202
00:15:40,750 --> 00:15:46,350
ac yna mae gennym 5 nod yn ein llinyn, er mwyn gwneud synnwyr.

203
00:15:48,060 --> 00:15:52,320
Os byddwn yn edrych i fyny ar sut y byddem yn ei amgodio mewn gwirionedd,

204
00:15:52,320 --> 00:15:56,580
yn ôl y disgwyl, mae'r ia s, sy'n ymddangos y mwyaf yn aml

205
00:15:56,580 --> 00:16:01,350
yn cael eu cynrychioli gan y nifer lleiaf o ddarnau.

206
00:16:03,660 --> 00:16:05,660
>> Byddwch yn ofalus yma.

207
00:16:05,660 --> 00:16:09,780
Mewn coed Huffman yr achos wirioneddol bwysig.

208
00:16:09,780 --> 00:16:13,670
Mae S priflythyren yn wahanol na s llythrennau bach.

209
00:16:13,670 --> 00:16:21,260
Pe bai gennym "Mae hwn yn CS50" gyda phriflythrennau, yna byddai'r s llythrennau bach yn unig yn ymddangos ddwywaith,

210
00:16:21,260 --> 00:16:27,120
byddai'n nod gyda 2 fel ei werth, ac yna byddai priflythyren S dim ond unwaith.

211
00:16:27,120 --> 00:16:33,440
Felly, yna byddai eich coeden yn newid strwythurau oherwydd eich bod mewn gwirionedd yn cael ddeilen ychwanegol yma.

212
00:16:33,440 --> 00:16:36,900
Ond byddai'r swm yn dal i fod yn 10.

213
00:16:36,900 --> 00:16:39,570
Dyna beth rydym yn wir yn mynd i gael ei galw y prawfswm,

214
00:16:39,570 --> 00:16:44,060
ychwanegu pob un o'r cyfrif.

215
00:16:46,010 --> 00:16:50,990
>> Nawr ein bod wedi cynnwys coed Huffman, gallwn plymio i mewn i Huff'n pwff, y pset.

216
00:16:50,990 --> 00:16:52,900
Rydym yn mynd i ddechrau ag adran o gwestiynau,

217
00:16:52,900 --> 00:16:57,990
ac mae hyn yn mynd i fynd â chi yn gyfarwydd â choed deuaidd a sut i weithredu o gwmpas y canlynol:

218
00:16:57,990 --> 00:17:03,230
nodau lluniadu, creu eich strwythur eich hun typedef ar gyfer nod,

219
00:17:03,230 --> 00:17:07,230
a gweld sut y byddwch yn mewnosod i mewn i goeden ddeuaidd, un sydd wedi'i didoli,

220
00:17:07,230 --> 00:17:09,050
tramwyo, a phethau fel 'na.

221
00:17:09,050 --> 00:17:14,560
Bod gwybodaeth yn bendant yn mynd i helpu chi pan fyddwch yn deifio i'r rhan pwff Huff'n

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

223
00:17:19,150 --> 00:17:26,329
Yn y rhifyn safon y pset, eich tasg yw i weithredu pwff,

224
00:17:26,329 --> 00:17:30,240
ac yn y fersiwn haciwr eich tasg yw i weithredu Huff.

225
00:17:30,240 --> 00:17:38,490
Beth Huff wneud yw testun y mae'n ei gymryd ac yna mae'n trosi i mewn i'r 0s a 1s,

226
00:17:38,490 --> 00:17:41,990
felly mae'r broses a wnaethom uchod lle rydym yn cyfrif y amleddau

227
00:17:41,990 --> 00:17:50,970
ac yna gwneud y goeden ac yna dywedodd, "Sut ydw i'n cael T?"

228
00:17:50,970 --> 00:17:54,840
T ei chynrychioli gan 100, pethau fel 'na,

229
00:17:54,840 --> 00:17:58,860
ac yna byddai Huff cymryd y testun ac yna allbwn sy'n deuaidd.

230
00:17:58,860 --> 00:18:04,920
Ond hefyd oherwydd gwyddom ein bod yn awyddus i ganiatáu i'n sawl sy'n derbyn y neges

231
00:18:04,920 --> 00:18:11,790
i ail-greu yr un goeden union, mae hefyd yn cynnwys gwybodaeth am y cyfrifon amlder.

232
00:18:11,790 --> 00:18:17,980
Yna, gyda pwff rydym yn cael ffeil ddeuaidd o 0au ac 1

233
00:18:17,980 --> 00:18:21,740
a hefyd yn cael y wybodaeth am y amleddau.

234
00:18:21,740 --> 00:18:26,740
Rydym yn cyfieithu pob un o'r rheiny yn ôl 0au ac 1 yn y neges wreiddiol a oedd,

235
00:18:26,740 --> 00:18:29,350
felly rydym ni'n ddatgywasgu hynny.

236
00:18:29,350 --> 00:18:36,450
Os ydych chi'n gwneud y rhifyn safonol, nid oes angen i weithredu Huff,

237
00:18:36,450 --> 00:18:39,290
felly, yna gallwch ddefnyddio'r gweithrediad staff y Huff.

238
00:18:39,290 --> 00:18:42,080
Mae cyfarwyddiadau yn y fanyleb ar sut i wneud hynny.

239
00:18:42,080 --> 00:18:48,780
Gallwch redeg gweithredu staff Huff ar ffeil testun penodol

240
00:18:48,780 --> 00:18:53,270
ac yna ddefnyddio'r cynnyrch fel eich mewnbwn i pwff.

241
00:18:53,270 --> 00:18:59,330
>> Fel y soniais o'r blaen, mae gennym lawer o god dosbarthu ar gyfer yr un yma.

242
00:18:59,330 --> 00:19:01,810
Rydw i'n mynd i ddechrau mynd drwyddo.

243
00:19:01,810 --> 00:19:04,400
Rydw i'n mynd i dreulio'r rhan fwyaf o'r amser ar yr. Ffeiliau h

244
00:19:04,400 --> 00:19:07,660
oherwydd yn y. ffeiliau c, gan fod gennym y h.

245
00:19:07,660 --> 00:19:11,650
a bod yn rhoi i ni y prototeipiau o swyddogaethau,

246
00:19:11,650 --> 00:19:15,520
Nid ydym yn llwyr angen i ni ddeall yn union -

247
00:19:15,520 --> 00:19:20,280
Os nad ydych yn deall beth sy'n mynd ymlaen yn y. Ffeiliau c, yna peidiwch â phoeni gormod,

248
00:19:20,280 --> 00:19:23,600
ond yn bendant yn ceisio cymryd golwg oherwydd gallai roi rhywfaint o awgrymiadau

249
00:19:23,600 --> 00:19:29,220
ac mae'n ddefnyddiol i ddod i arfer â ddarllen cod pobl eraill.

250
00:19:38,940 --> 00:19:48,270
>> Gan edrych ar huffile.h, yn y sylwadau y mae'n datgan haen o echdynnu ar gyfer Huffman-codio ffeiliau.

251
00:19:48,270 --> 00:20:01,660
Os ydym yn mynd i lawr, gwelwn fod yna uchafswm o 256 o symbolau y gallai fod angen codau ar gyfer.

252
00:20:01,660 --> 00:20:05,480
Mae hyn yn cynnwys yr holl lythrennau'r wyddor - priflythyren a llythrennau bach -

253
00:20:05,480 --> 00:20:08,250
ac yna symbolau a rhifau, ac ati

254
00:20:08,250 --> 00:20:11,930
Yna dyma gennym nifer hud adnabod ffeil Huffman-godio.

255
00:20:11,930 --> 00:20:15,890
O fewn cod Huffman maen nhw'n mynd i gael nifer penodol hud

256
00:20:15,890 --> 00:20:18,560
gysylltiedig â'r pennawd.

257
00:20:18,560 --> 00:20:21,110
Gallai hyn edrych fel dim ond rhif hud ar hap,

258
00:20:21,110 --> 00:20:27,160
ond os ydych mewn gwirionedd yn ei gyfieithu i'r ASCII, yna mewn gwirionedd mae'n nodi'n huff.

259
00:20:27,160 --> 00:20:34,290
Yma mae gennym strwythur ar gyfer ffeil Huffman-encoded.

260
00:20:34,290 --> 00:20:39,670
Mae pob un o'r nodweddion hyn yn gysylltiedig â ffeil Huff.

261
00:20:39,670 --> 00:20:47,080
Yna i lawr yma mae gennym y pennawd am ffeil Huff, felly rydym yn galw ei Huffeader

262
00:20:47,080 --> 00:20:50,810
yn hytrach na ychwanegu'r h ychwanegol oherwydd ei fod yn swnio yr un fath beth bynnag.

263
00:20:50,810 --> 00:20:52,720
'N giwt.

264
00:20:52,720 --> 00:20:57,790
Mae gennym nifer hud sy'n gysylltiedig ag ef.

265
00:20:57,790 --> 00:21:09,040
Os yw'n ffeil Huff go iawn, mae'n mynd i fod y rhif i fyny uchod, mae hyn yn un hudol.

266
00:21:09,040 --> 00:21:14,720
Ac yna bydd yn cael amrywiaeth.

267
00:21:14,720 --> 00:21:18,750
Felly, ar gyfer pob symbol, ac y mae 256,

268
00:21:18,750 --> 00:21:24,760
mae'n mynd i restru'r hyn y gallai amlder y symbolau o fewn y ffeil Huff.

269
00:21:24,760 --> 00:21:28,090
Ac yna yn olaf, mae gennym checksum gyfer yr amleddau,

270
00:21:28,090 --> 00:21:32,160
a ddylai fod yn y swm o hynny amleddau.

271
00:21:32,160 --> 00:21:36,520
Felly, dyna beth mae Huffeader yn.

272
00:21:36,520 --> 00:21:44,600
Yna, mae gennym rai swyddogaethau sy'n dychwelyd y darn nesaf yn y ffeil Huff

273
00:21:44,600 --> 00:21:52,580
yn ogystal ag ysgrifennu ychydig at y ffeil Huff, ac yna roedd y swyddogaeth yma, hfclose,

274
00:21:52,580 --> 00:21:54,650
sydd mewn gwirionedd yn cau y ffeil Huff.

275
00:21:54,650 --> 00:21:57,290
Cyn hynny, roeddem yn delio â syth yn unig mmap,

276
00:21:57,290 --> 00:22:01,190
ond pan fydd gennych ffeil Huff, yn hytrach na fclosing ei

277
00:22:01,190 --> 00:22:06,080
yr hyn rydych chi mewn gwirionedd yn mynd i wneud yw hfclose a hfopen hynny.

278
00:22:06,080 --> 00:22:13,220
Mae'r rhain yn swyddogaethau penodol i'r ffeiliau Huff ein bod yn mynd i fod yn delio â hwy.

279
00:22:13,220 --> 00:22:19,230
Yna dyma rydym yn darllen yn y pennawd ac yna ysgrifennu y pennawd.

280
00:22:19,230 --> 00:22:25,700
>> Dim ond drwy ddarllen y. Ffeil h gallwn fath o gael synnwyr o'r hyn y gallai fod yn ffeil Huff,

281
00:22:25,700 --> 00:22:32,480
pa nodweddion sydd ganddo, heb mewn gwirionedd yn mynd i mewn i'r huffile.c,

282
00:22:32,480 --> 00:22:36,750
a fydd, os ydym yn plymio i mewn, yn mynd i fod ychydig yn fwy cymhleth.

283
00:22:36,750 --> 00:22:41,270
Mae wedi holl o'r ffeil I / O yma ymdrin â awgrymiadau.

284
00:22:41,270 --> 00:22:48,010
Yma rydym yn gweld bod pan fyddwn yn galw hfread, er enghraifft, mae'n dal i ddelio â'r fread.

285
00:22:48,010 --> 00:22:53,050
Nid ydym yn cael gwared o'r swyddogaethau hynny yn gyfan gwbl, ond rydym yn anfon y rhai sydd i'w cymryd gofal

286
00:22:53,050 --> 00:22:59,760
y tu mewn i'r ffeil Huff yn hytrach na gwneud yr holl waith ein hunain.

287
00:22:59,760 --> 00:23:02,300
Gallwch deimlo'n rhydd i sganio drwy hyn os ydych yn chwilfrydig

288
00:23:02,300 --> 00:23:08,410
ac yn mynd a phlicio yr haen yn ôl ychydig bach.

289
00:23:20,650 --> 00:23:24,060
>> Mae'r ffeil nesaf ein bod ni'n mynd i edrych arno yw tree.h.

290
00:23:24,060 --> 00:23:30,210
O'r blaen yn y Walkthrough sleidiau rydym yn dweud ein bod yn disgwyl nod Huffman

291
00:23:30,210 --> 00:23:32,960
ac rydym wedi gwneud nod strwythur typedef.

292
00:23:32,960 --> 00:23:38,360
Rydym yn disgwyl iddo gael symbol, amledd, ac yna 2 sêr nod.

293
00:23:38,360 --> 00:23:41,870
Yn yr achos hwn yr hyn rydym yn ei wneud yn hyn yn ei hanfod yr un fath

294
00:23:41,870 --> 00:23:46,880
ac eithrio yn hytrach na nod rydym yn mynd i alw eu coed.

295
00:23:48,790 --> 00:23:56,760
Mae gennym swyddogaeth pan fyddwch yn ffonio wneud goeden yn dychwelyd i chi bwyntydd coeden.

296
00:23:56,760 --> 00:24:03,450
Back i Speller, pan fyddwch yn gwneud nod newydd

297
00:24:03,450 --> 00:24:11,410
i chi ddweud nod * gair newydd = malloc (sizeof) a phethau fel 'na.

298
00:24:11,410 --> 00:24:17,510
Yn y bôn, mktree yn mynd i fod yn delio â hynny i chi.

299
00:24:17,510 --> 00:24:20,990
Yn yr un modd, pan fyddwch am i dynnu coeden,

300
00:24:20,990 --> 00:24:24,810
fel bod ei hanfod yn rhyddhau y goeden pan fyddwch chi'n ei wneud ag ef,

301
00:24:24,810 --> 00:24:33,790
yn hytrach na galw yn benodol am ddim ar hynny, rydych chi mewn gwirionedd ond yn mynd i ddefnyddio'r swyddogaeth rmtree

302
00:24:33,790 --> 00:24:40,360
lle byddwch yn mynd heibio yn y pwyntydd i'r goeden ac yna bydd dir.c yn gofalu am hynny i chi.

303
00:24:40,360 --> 00:24:42,490
>> Rydym yn edrych i mewn i tree.c.

304
00:24:42,490 --> 00:24:47,240
Rydym yn disgwyl i'r un swyddogaethau ac eithrio i weld gweithredu yn ogystal.

305
00:24:47,240 --> 00:24:57,720
Fel yr oeddem yn disgwyl, pan fyddwch yn ffonio mktree mae'n mallocs faint o goeden i mewn i pwyntydd,

306
00:24:57,720 --> 00:25:03,190
initializes yr holl werthoedd i'r gwerth NULL, felly 0au neu NULLs,

307
00:25:03,190 --> 00:25:08,280
ac yna dychwelyd y pwyntydd i'r goeden eich bod wedi malloc'd yn unig i chi.

308
00:25:08,280 --> 00:25:13,340
Yma pan fyddwch yn ffonio gwared goeden yn gyntaf yn gwneud yn siwr nad ydych chi'n dwbl rhyddhau.

309
00:25:13,340 --> 00:25:18,320
Mae'n gwneud yn siŵr eich bod mewn gwirionedd yn cael coeden eich bod am ddileu'r.

310
00:25:18,320 --> 00:25:23,330
Yma oherwydd coeden hefyd yn cynnwys ei phlant,

311
00:25:23,330 --> 00:25:29,560
beth yw hyn yn ei recursively galw gwared coeden ar y nôd chwith y goeden

312
00:25:29,560 --> 00:25:31,650
yn ogystal â'r nod cywir.

313
00:25:31,650 --> 00:25:37,790
Cyn rhyddhau'r rhiant, mae angen i ryddhau plant yn ogystal.

314
00:25:37,790 --> 00:25:42,770
Rhieni hefyd yn ymgyfnewidiol gyda gwreiddiau.

315
00:25:42,770 --> 00:25:46,500
Y rhiant cyntaf erioed, felly fel y gor-or-or-or-daid

316
00:25:46,500 --> 00:25:52,130
neu goeden nain, yn gyntaf mae'n rhaid i ni ryddhau i lawr y lefelau cyntaf.

317
00:25:52,130 --> 00:25:58,490
Felly croesi i'r gwaelod, rhad ac am ddim rheini, ac yna dod yn ôl i fyny, rhad ac am ddim rheini, ac ati

318
00:26:00,400 --> 00:26:02,210
Felly dyna goeden.

319
00:26:02,210 --> 00:26:04,240
>> Nawr rydym yn edrych ar goedwig.

320
00:26:04,240 --> 00:26:09,860
Coedwig yw pan fyddwch yn rhoi eich holl goed Huffman.

321
00:26:09,860 --> 00:26:12,910
Mae'n dweud ein bod ni'n mynd i gael rhywbeth a elwir yn llain

322
00:26:12,910 --> 00:26:22,320
sy'n cynnwys pwyntydd i goeden yn ogystal â pwyntydd i blot o'r enw nesaf.

323
00:26:22,320 --> 00:26:28,480
Pa strwythur y mae hyn yn fath o edrych fel?

324
00:26:29,870 --> 00:26:32,490
Mae'n fath o yn dweud ei fod dros yno.

325
00:26:34,640 --> 00:26:36,700
Hawl dros yma.

326
00:26:37,340 --> 00:26:39,170
Mae rhestr cysylltiedig.

327
00:26:39,170 --> 00:26:44,590
Rydym yn gweld bod pan fydd gennym plot mae fel rhestr gysylltiedig o leiniau.

328
00:26:44,590 --> 00:26:53,020
Mae coedwig yn cael ei ddiffinio fel rhestr gysylltiedig o leiniau,

329
00:26:53,020 --> 00:26:58,100
ac felly mae'r strwythur goedwig yw ein bod yn jyst yn mynd i gael pwyntydd at ein plot 1

330
00:26:58,100 --> 00:27:02,740
a bod plot mae coeden o'i mewn neu yn hytrach yn cyfeirio at goeden

331
00:27:02,740 --> 00:27:06,190
ac yna cyfeirio at y plot nesaf, yn y blaen ac yn y blaen.

332
00:27:06,190 --> 00:27:11,100
I wneud coedwig rydym yn galw mkforest.

333
00:27:11,100 --> 00:27:14,930
Yna, mae gennym rai swyddogaethau eithaf defnyddiol yma.

334
00:27:14,930 --> 00:27:23,240
Rydym wedi dewis lle byddwch yn mynd heibio mewn coedwig, ac yna dychwelyd y gwerth yn * Coed,

335
00:27:23,240 --> 00:27:25,210
pwyntydd i goeden.

336
00:27:25,210 --> 00:27:29,370
Beth fydd dewis ei wneud yw y bydd yn mynd i mewn i'r goedwig eich bod yn cyfeirio at

337
00:27:29,370 --> 00:27:35,240
yna tynnwch coeden gydag amlder isaf o'r goedwig

338
00:27:35,240 --> 00:27:38,330
ac yna rhoi i chi y pwyntydd i'r goeden.

339
00:27:38,330 --> 00:27:43,030
Unwaith y byddwch yn ffonio ddewis, ni fydd y goeden yn bodoli yn y goedwig anymore,

340
00:27:43,030 --> 00:27:48,550
ond mae gwerth dychwelyd yn y pwyntydd i'r goeden.

341
00:27:48,550 --> 00:27:50,730
Yna byddwch wedi planhigyn.

342
00:27:50,730 --> 00:27:57,420
Ar yr amod eich bod yn llwyddo mewn pwyntydd i goeden sydd â amlder nad yw'n-0,

343
00:27:57,420 --> 00:28:04,040
beth fydd planhigion yn ei wneud yw y bydd yn ei gymryd i'r goedwig, yn cymryd y goeden, a phlanhigion y tu mewn coed o'r goedwig.

344
00:28:04,040 --> 00:28:06,370
Yma, mae gennym rmforest.

345
00:28:06,370 --> 00:28:11,480
Yn debyg i dynnu coeden, sydd yn y bôn rhyddhau ein holl goed i ni,

346
00:28:11,480 --> 00:28:16,600
gwared goedwig yn popeth am ddim a geir yn y goedwig.

347
00:28:16,600 --> 00:28:24,890
>> Os byddwn yn edrych i mewn i forest.c, byddwn yn disgwyl gweld o leiaf 1 gorchymyn rmtree i mewn 'na,

348
00:28:24,890 --> 00:28:30,090
oherwydd i gof am ddim yn y goedwig os coedwig o goed ynddo,

349
00:28:30,090 --> 00:28:32,930
yn y pen draw ydych chi'n mynd i gael i symud y coed hefyd.

350
00:28:32,930 --> 00:28:41,020
Os byddwn yn edrych i mewn forest.c, rydym wedi ein mkforest, sydd fel yr ydym yn ei ddisgwyl.

351
00:28:41,020 --> 00:28:42,890
Rydym yn malloc pethau.

352
00:28:42,890 --> 00:28:51,740
Rydym yn ymgychwyn y plot cyntaf yn y goedwig fel NULL oherwydd ei fod yn wag i ddechrau,

353
00:28:51,740 --> 00:29:05,940
yna rydym yn gweld ddewis, sy'n peri i'r goeden gyda'r pwysau isaf, pa mor aml isaf,

354
00:29:05,940 --> 00:29:13,560
ac yna yn cael gwared ar y nod benodol sy'n pwyntio at y goeden a'r un nesaf,

355
00:29:13,560 --> 00:29:16,760
felly mae'n cymryd bod allan o'r rhestr gysylltiedig y goedwig.

356
00:29:16,760 --> 00:29:24,510
Ac yna dyma ni wedi planhigyn, sy'n mewnosod goeden i mewn i'r rhestr cysylltiedig.

357
00:29:24,510 --> 00:29:29,960
Pa goedwig yn ei wneud yw ei 'n glws yn cadw ei datrys i ni.

358
00:29:29,960 --> 00:29:37,910
Ac yna yn olaf, mae gennym rmforest ac, yn ôl y disgwyl, mae gennym rmtree enw yno.

359
00:29:46,650 --> 00:29:55,440
>> O edrych ar y cod dosbarthu hyd yn hyn, huffile.c yn ôl pob tebyg o bell ffordd anoddaf i'w ddeall,

360
00:29:55,440 --> 00:29:59,990
tra bod y ffeiliau eraill eu hunain yn eithaf syml i'w dilyn.

361
00:29:59,990 --> 00:30:03,090
Gyda ein gwybodaeth am awgrymiadau a rhestrau cysylltiedig ac o'r fath,

362
00:30:03,090 --> 00:30:04,860
roeddem yn gallu dilyn yn eithaf da.

363
00:30:04,860 --> 00:30:10,500
Ond yr holl mae angen i ni wir wneud yn siŵr ein bod yn llwyr ddeall yw'r. H ffeiliau

364
00:30:10,500 --> 00:30:15,840
oherwydd mae angen i chi gael eu galw swyddogaethau hynny, delio â'r rhai gwerthoedd dychwelyd,

365
00:30:15,840 --> 00:30:20,590
felly gwnewch yn siŵr eich bod yn deall pa gamau fydd yn cael ei berfformio

366
00:30:20,590 --> 00:30:24,290
pryd bynnag fyddwch yn ffonio un o'r swyddogaethau hynny.

367
00:30:24,290 --> 00:30:33,020
Ond mewn gwirionedd yn deall y tu mewn ohono yn eithaf angenrheidiol oherwydd hynny gennym. Ffeiliau h.

368
00:30:35,170 --> 00:30:39,490
Mae gennym 2 yn fwy ffeiliau ar ôl yn ein cod dosbarthu.

369
00:30:39,490 --> 00:30:41,640
>> Gadewch i ni edrych ar domen.

370
00:30:41,640 --> 00:30:47,230
Tomen gan ei sylwadau yma yn cymryd ffeil Huffman-cywasgedig

371
00:30:47,230 --> 00:30:55,580
ac yna yn cyfieithu a gollwng ei holl gynnwys y tu allan.

372
00:31:01,010 --> 00:31:04,260
Yma rydym yn gweld ei fod yn galw hfopen.

373
00:31:04,260 --> 00:31:10,770
Mae hyn yn fath o drychu i ffeilio * mewnbwn = fopen,

374
00:31:10,770 --> 00:31:13,500
ac yna byddwch yn mynd heibio yn y wybodaeth.

375
00:31:13,500 --> 00:31:18,240
Mae bron yn unfath ar wahân yn hytrach na * ffeil rydych chi'n pasio mewn Huffile;

376
00:31:18,240 --> 00:31:22,030
yn hytrach na fopen ydych yn pasio yn hfopen.

377
00:31:22,030 --> 00:31:29,280
Yma, rydym yn darllen yn y pennawd cyntaf, sy'n fath o debyg i sut yr ydym yn darllen yn y pennawd

378
00:31:29,280 --> 00:31:33,580
am ffeil bitmap.

379
00:31:33,580 --> 00:31:38,000
Yr hyn yr ydym ni'n ei wneud yma yn gwirio i weld a yw'r wybodaeth pennawd

380
00:31:38,000 --> 00:31:44,330
cynnwys y nifer hud iawn sy'n dangos ei fod yn ffeil Huff go iawn,

381
00:31:44,330 --> 00:31:53,610
yna pob un o'r gwiriadau i wneud yn siŵr bod y ffeil yr ydym yn agored hon ar ffurf ffeil huffed gwirioneddol neu beidio.

382
00:31:53,610 --> 00:32:05,330
Beth yw hyn yn ei allbynnau amlder yr holl symbolau y gallwn weld

383
00:32:05,330 --> 00:32:09,790
mewn terfynfa i mewn i dabl graffigol.

384
00:32:09,790 --> 00:32:15,240
Mae'r rhan hon yn mynd i fod yn ddefnyddiol.

385
00:32:15,240 --> 00:32:24,680
Mae ganddo ychydig ac yn darllen fesul tipyn yn y bit amrywiol ac yna yn argraffu allan.

386
00:32:28,220 --> 00:32:35,430
Felly, pe bawn yn galw daflu i lawr ar hth.bin, sef y canlyniad chwythu ffeil

387
00:32:35,430 --> 00:32:39,490
ddefnyddio'r datrysiad staff, byddwn yn cael hyn.

388
00:32:39,490 --> 00:32:46,000
Mae'n outputting yr holl nodau hyn ac yna rhoi pa mor aml y maent yn ymddangos.

389
00:32:46,000 --> 00:32:51,180
Os ydym yn edrych, mae'r rhan fwyaf ohonynt yn 0au ac eithrio ar gyfer hyn: H, sy'n ymddangos ddwywaith,

390
00:32:51,180 --> 00:32:54,820
ac yna T, sy'n ymddangos unwaith.

391
00:32:54,820 --> 00:33:07,860
Ac yna dyma gennym y neges gwirioneddol mewn 0s a 1s.

392
00:33:07,860 --> 00:33:15,450
Os ydym yn edrych ar hth.txt, sydd yn ôl pob tebyg y neges gwreiddiol a huffed,

393
00:33:15,450 --> 00:33:22,490
rydym yn disgwyl gweld rhai HS a Ts i mewn 'na.

394
00:33:22,490 --> 00:33:28,720
Yn benodol, rydym yn disgwyl gweld dim ond 1 T a 2 HS.

395
00:33:32,510 --> 00:33:37,440
Dyma ni yn hth.txt. Mae yn wir wedi HTH.

396
00:33:37,440 --> 00:33:41,270
Yn gynwysedig yn yno, er na allwn ei weld, yn gymeriad Newline.

397
00:33:41,270 --> 00:33:53,190
Mae'r hth.bin ffeil Huff hefyd yn amgodio cymeriad Newline yn ogystal.

398
00:33:55,680 --> 00:34:01,330
Yma oherwydd ein bod yn gwybod bod y gorchymyn yn HTH ac yna Newline,

399
00:34:01,330 --> 00:34:07,340
gallwn weld bod fwy na thebyg H yn cael ei gynrychioli gan ychydig o 1 sengl

400
00:34:07,340 --> 00:34:17,120
ac yna y T yn ôl pob tebyg 01 a yna'r H nesaf yw 1 yn ogystal

401
00:34:17,120 --> 00:34:21,139
ac yna mae gennym Newline nodwyd gan ddau 0au.

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

403
00:34:26,530 --> 00:34:31,600
>> Ac yna yn olaf, oherwydd ein bod yn delio â lluosog. C a. Ffeiliau h,

404
00:34:31,600 --> 00:34:36,350
rydym yn mynd i gael dadl gymhleth eithaf i'r compiler,

405
00:34:36,350 --> 00:34:40,460
ac felly dyma gennym Makefile sy'n gwneud tomen i chi.

406
00:34:40,460 --> 00:34:47,070
Ond mewn gwirionedd, mae'n rhaid i chi fynd ati i wneud eich ffeil eich hun puff.c.

407
00:34:47,070 --> 00:34:54,330
Mae'r Makefile mewn gwirionedd yn ymdrin â gwneud puff.c i chi.

408
00:34:54,330 --> 00:34:59,310
Rydym yn gadael y fyny i chi i olygu'r Makefile.

409
00:34:59,310 --> 00:35:05,930
Pan fyddwch yn mynd i mewn i gorchymyn fel gwneud gwbl, er enghraifft, bydd yn gwneud pob un ohonynt i chi.

410
00:35:05,930 --> 00:35:10,760
Teimlwch yn rhydd i edrych ar yr enghreifftiau o Makefile o'r pset gorffennol

411
00:35:10,760 --> 00:35:17,400
yn ogystal â mynd oddi ar hwn i weld sut y gallech chi fod yn gallu gwneud eich ffeil pwff

412
00:35:17,400 --> 00:35:20,260
drwy olygu y Makefile.

413
00:35:20,260 --> 00:35:22,730
Dyna am y peth am ein cod dosbarthu.

414
00:35:22,730 --> 00:35:28,380
>> Unwaith y byddwn wedi gotten drwy hynny, yna dyma dim ond atgof arall

415
00:35:28,380 --> 00:35:30,980
o sut yr ydym yn mynd i fod yn delio â'r nodau Huffman.

416
00:35:30,980 --> 00:35:35,400
Nid ydym yn mynd i gael ei galw yn eu nodau anymore, rydym yn mynd i gael eu galw nhw coed

417
00:35:35,400 --> 00:35:39,260
lle'r ydym yn mynd i fod yn cynrychioli eu symbol gyda golosg,

418
00:35:39,260 --> 00:35:43,340
eu hamlder, y nifer o ddigwyddiadau, gyda cyfanrif.

419
00:35:43,340 --> 00:35:47,370
Rydym yn ei ddefnyddio oherwydd ei fod yn fwy manwl gywir na arnofio.

420
00:35:47,370 --> 00:35:52,980
Ac yna rydym wedi arall pwyntydd i'r plentyn chwith yn ogystal ag i'r plentyn iawn.

421
00:35:52,980 --> 00:35:59,630
Mae coedwig, fel y gwelsom, yn unig yw rhestr gysylltiedig o goed.

422
00:35:59,630 --> 00:36:04,670
Yn y pen draw, pan fyddwn yn adeiladu i fyny ein Huff ffeil,

423
00:36:04,670 --> 00:36:07,580
rydym am i'n goedwig i gynnwys dim ond 1 goeden -

424
00:36:07,580 --> 00:36:12,420
1 goeden, 1 wreiddyn â phlant lluosog.

425
00:36:12,420 --> 00:36:20,840
Yn gynharach pan oeddem yn unig yn gwneud ein coed Huffman,

426
00:36:20,840 --> 00:36:25,360
gennym ar y cychwyn trwy osod pob un o'r nodau ar ein sgrin

427
00:36:25,360 --> 00:36:27,790
a dweud rydym yn mynd i gael y nodau,

428
00:36:27,790 --> 00:36:32,920
yn y pen draw maen nhw'n mynd i fod yn y dail, ac mae hyn yn eu symbol, mae hyn yn eu hamlder.

429
00:36:32,920 --> 00:36:42,070
Yn ein coedwig os ydym yn unig wedi 3 llythyr, sy'n goedwig o 3 coeden.

430
00:36:42,070 --> 00:36:45,150
Ac yna wrth i ni fynd ymlaen, pan fyddwn yn ychwanegu y rhiant cyntaf,

431
00:36:45,150 --> 00:36:48,080
gwnaethom coedwig o 2 goeden.

432
00:36:48,080 --> 00:36:54,930
Rydym yn dileu 2 o'r plant hynny o'n goedwig ac yna yn ei le yn nod rhiant

433
00:36:54,930 --> 00:36:58,820
oedd y 2 nodau fel plant.

434
00:36:58,820 --> 00:37:05,600
Ac yna yn olaf, ein cam diwethaf gyda gwneud ein enghraifft gyda'r Fel, B, ac C

435
00:37:05,600 --> 00:37:08,030
fyddai gwneud y rhiant terfynol,

436
00:37:08,030 --> 00:37:13,190
ac felly yna byddai hynny'n dod â ein cyfrif gyfanswm y coed yn y goedwig i 1.

437
00:37:13,190 --> 00:37:18,140
Ydy pawb yn gweld sut y byddwch yn dechrau allan gyda choed lluosog yn eich coedwig

438
00:37:18,140 --> 00:37:22,520
a darfod i fyny ag 1? Iawn. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Beth sydd angen i ni ei wneud ar gyfer pwff?

440
00:37:28,110 --> 00:37:37,110
Beth sydd angen i chi ei wneud yw sicrhau, fel bob amser, maent yn rhoi i ni y math cywir o fewnbwn

441
00:37:37,110 --> 00:37:39,090
fel y gallwn mewn gwirionedd yn rhedeg y rhaglen.

442
00:37:39,090 --> 00:37:43,130
Yn yr achos hwn maen nhw'n mynd i gael ei rhoi i ni ar ôl eu cyntaf gorchymyn-lein ddadl

443
00:37:43,130 --> 00:37:53,440
2 yn fwy: y ffeil yr ydym am ei datgywasgu'r ac allbwn y ffeil dad-gywasgu.

444
00:37:53,440 --> 00:38:00,410
Ond unwaith i ni wneud yn siŵr eu bod yn pasio heibio i ni yn y swm cywir o werthoedd,

445
00:38:00,410 --> 00:38:05,820
ydym am sicrhau bod y mewnbwn yn ffeil Huff neu beidio.

446
00:38:05,820 --> 00:38:10,420
Ac yna unwaith rydym yn gwarantu ei fod yn ffeil Huff, yna rydym eisiau adeiladu ein coeden,

447
00:38:10,420 --> 00:38:20,940
adeiladu y goeden fel ei fod yn cyfateb i'r goeden fod y person a anfonodd y neges hadeiladu.

448
00:38:20,940 --> 00:38:25,840
Yna, ar ôl i ni yn adeiladu y goeden, yna gallwn ddelio â'r, 0s a 1s eu bod wedi pasio mewn

449
00:38:25,840 --> 00:38:29,590
dilyn y rhai ar hyd ein coeden am ei fod yn union yr un fath,

450
00:38:29,590 --> 00:38:33,510
ac yna ysgrifennwch y neges honno allan, dehongli y darnau yn ôl i chars.

451
00:38:33,510 --> 00:38:35,880
Ac yna ar y diwedd oherwydd ein bod yn delio â awgrymiadau yma,

452
00:38:35,880 --> 00:38:38,110
rydym am wneud yn siŵr nad oes gennym unrhyw ollyngiadau cof

453
00:38:38,110 --> 00:38:41,330
a'n bod yn popeth am ddim.

454
00:38:42,820 --> 00:38:46,430
>> Sicrhau defnydd priodol yn hen het i ni erbyn hyn.

455
00:38:46,430 --> 00:38:51,980
Rydym yn cymryd mewn mewnbwn, sydd yn mynd i fod yn enw'r ffeil i'w pwff,

456
00:38:51,980 --> 00:38:56,010
ac yna rydym yn pennu allbwn,

457
00:38:56,010 --> 00:39:01,580
felly enw'r ffeil ar gyfer yr allbwn ymchwyddo, a fydd yn y ffeil testun.

458
00:39:03,680 --> 00:39:08,820
Dyna defnydd. Ac yn awr rydym yn awyddus i sicrhau bod y mewnbwn yn huffed neu beidio.

459
00:39:08,820 --> 00:39:16,420
Gan feddwl yn ôl, a oedd unrhyw beth yn y cod dosbarthu a allai ein helpu i

460
00:39:16,420 --> 00:39:21,570
gyda dealltwriaeth a yw ffeil yn cael ei huffed ai peidio?

461
00:39:21,570 --> 00:39:26,910
Roedd gwybodaeth yn huffile.c am y Huffeader.

462
00:39:26,910 --> 00:39:33,430
Rydym yn gwybod bod pob ffeil Huff Mae Huffeader sy'n gysylltiedig ag ef gyda nifer hud

463
00:39:33,430 --> 00:39:37,240
yn ogystal ag amrywiaeth o amleddau ar gyfer pob symbol

464
00:39:37,240 --> 00:39:39,570
yn ogystal â checksum.

465
00:39:39,570 --> 00:39:43,180
Rydym yn gwybod hynny, ond rydym hefyd yn cymryd cipolwg ar dump.c,

466
00:39:43,180 --> 00:39:49,120
yr oedd yn darllen i mewn i ffeil Huff.

467
00:39:49,120 --> 00:39:53,990
Ac felly i wneud hynny, bu'n rhaid iddo sicrhau ei fod mewn gwirionedd oedd huffed neu beidio.

468
00:39:53,990 --> 00:40:03,380
Felly, efallai y gallem ddefnyddio dump.c fel strwythur ar gyfer ein puff.c.

469
00:40:03,380 --> 00:40:12,680
Yn ôl i pset 4 pan gawsom y copy.c ffeil gopïo yn treblu'r RGB

470
00:40:12,680 --> 00:40:14,860
ac rydym yn dehongli ar gyfer Whodunit a Newid maint,

471
00:40:14,860 --> 00:40:20,390
yn yr un modd, yr hyn y gallech ei wneud yn cael ei redeg dim ond y gorchymyn fel cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
ac yn defnyddio rhai o'r cod yno.

473
00:40:23,600 --> 00:40:28,210
Fodd bynnag, nid yw'n mynd i fod mor syml o broses

474
00:40:28,210 --> 00:40:33,010
ar gyfer cyfieithu eich dump.c i mewn i puff.c,

475
00:40:33,010 --> 00:40:36,160
ond o leiaf mae'n rhoi rhywle i chi ddechrau

476
00:40:36,160 --> 00:40:40,540
ar sut i sicrhau bod y mewnbwn yn huffed mewn gwirionedd neu beidio

477
00:40:40,540 --> 00:40:43,240
yn ogystal ag ychydig o bethau eraill.

478
00:40:45,930 --> 00:40:50,250
Rydym wedi sicrhau defnydd priodol a sicrhau bod y mewnbwn yn cael ei huffed.

479
00:40:50,250 --> 00:40:53,570
Bob tro yr ydym wedi gwneud ein bod wedi gwneud ein gwirio gwall priodol,

480
00:40:53,570 --> 00:41:01,520
felly dychwelyd a rhoi'r gorau iddi swyddogaeth os oes rhai methiant yn digwydd, os oes problem.

481
00:41:01,520 --> 00:41:07,170
>> Nawr beth rydym am ei wneud yw adeiladu y goeden ei hun.

482
00:41:08,840 --> 00:41:12,640
Os ydym yn edrych yn Forest, mae 2 prif swyddogaethau

483
00:41:12,640 --> 00:41:15,800
ein bod ni'n mynd i eisiau i ddod yn gyfarwydd iawn ag ef.

484
00:41:15,800 --> 00:41:23,870
Mae swyddogaeth y planhigyn Boole bod yn plannu coeden amlder nad yw'n-0 y tu mewn i'n goedwig.

485
00:41:23,870 --> 00:41:29,250
Ac felly dyna chi basio mewn pwyntydd i goedwig a pwyntydd i goeden.

486
00:41:32,530 --> 00:41:40,340
Cwestiwn cyflym: Faint o goedwigoedd sydd gennych pan fyddwch yn adeiladu coeden Huffman?

487
00:41:44,210 --> 00:41:46,650
Mae ein goedwig fel ein gynfas, dde?

488
00:41:46,650 --> 00:41:50,800
Felly, rydym yn unig yn mynd i gael 1 goedwig, ond rydym yn mynd i gael coed lluosog.

489
00:41:50,800 --> 00:41:57,590
Felly, cyn i chi ffonio planhigion, rydych yn ôl pob tebyg yn mynd i eisiau i wneud eich goedwig.

490
00:41:57,590 --> 00:42:04,430
Mae gorchymyn ar gyfer os ydych yn edrych i mewn i forest.h ar sut y gallwch wneud goedwig.

491
00:42:04,430 --> 00:42:09,270
Gallwch blannu coeden. Rydym yn gwybod sut i wneud hynny.

492
00:42:09,270 --> 00:42:11,590
Ac yna gallwch hefyd ddewis coeden o'r goedwig,

493
00:42:11,590 --> 00:42:17,540
tynnu coed gyda'r pwysau isaf ac yn rhoi i chi y pwyntydd i hynny.

494
00:42:17,540 --> 00:42:23,090
Wrth feddwl yn ôl i'r adeg pan oeddem yn gwneud yr enghreifftiau ein hunain,

495
00:42:23,090 --> 00:42:27,980
pan oeddem yn tynnu allan, rydym dim ond dim ond ychwanegodd y cysylltiadau.

496
00:42:27,980 --> 00:42:31,680
Ond yma yn hytrach na dim ond ychwanegu cysylltiadau,

497
00:42:31,680 --> 00:42:40,630
feddwl am y peth yn fwy fel eich bod yn cael gwared 2 o'r rheiny nodau ac yna yn ei le gan un arall.

498
00:42:40,630 --> 00:42:44,200
I fynegi hynny o ran casglu a phlannu,

499
00:42:44,200 --> 00:42:48,840
eich bod yn casglu 2 goeden ac yna plannu coeden arall

500
00:42:48,840 --> 00:42:54,060
sydd yn cael y rheini'n 2 goeden eich bod wedi cyfeirio fel plant.

501
00:42:57,950 --> 00:43:05,280
Er mwyn adeiladu Huffman yn goeden, gallwch ddarllen yn y symbolau ac amleddau er mwyn

502
00:43:05,280 --> 00:43:10,790
oherwydd bod y Huffeader yn rhoi hynny i chi,

503
00:43:10,790 --> 00:43:14,250
yn rhoi i chi amrywiaeth o amleddau.

504
00:43:14,250 --> 00:43:19,660
Felly, gallwch fynd yn ei flaen a dim ond anwybyddu unrhyw beth gyda'r 0 wedi'i ynddo

505
00:43:19,660 --> 00:43:23,760
oherwydd nid ydym am 256 dail ar y diwedd.

506
00:43:23,760 --> 00:43:27,960
Rydym yn unig am y nifer o dail sy'n cymeriadau

507
00:43:27,960 --> 00:43:31,600
sy'n cael eu defnyddio mewn gwirionedd yn y ffeil.

508
00:43:31,600 --> 00:43:37,590
Gallwch ddarllen yn y symbolau, a phob un o'r rhai symbolau sy'n cael nad ydynt yn-0 amlderau,

509
00:43:37,590 --> 00:43:40,440
y rhai yn mynd i fod yn goed.

510
00:43:40,440 --> 00:43:45,990
Beth allwch chi ei wneud yw bob tro y byddwch yn darllen mewn amlder nad yw'n symbol-0,

511
00:43:45,990 --> 00:43:50,660
gallwch blannu y goeden yn y goedwig.

512
00:43:50,660 --> 00:43:56,620
Unwaith y byddwch yn plannu coed yn y goedwig, gallwch ymuno â rhai coed fel brodyr a chwiorydd,

513
00:43:56,620 --> 00:44:01,130
felly yn mynd yn ôl i blannu a dewis lle rydych yn dewis 2 ac yna planhigion 1,

514
00:44:01,130 --> 00:44:05,820
lle bod 1 eich bod yn blanhigyn yw rhiant y 2 o blant eich bod wedi cyfeirio.

515
00:44:05,820 --> 00:44:11,160
Felly, yna bydd eich canlyniad terfynol yn mynd i fod yn un goeden yn eich goedwig.

516
00:44:16,180 --> 00:44:18,170
Dyna sut yr ydych yn adeiladu eich coeden.

517
00:44:18,170 --> 00:44:21,850
>> Mae nifer o bethau a allai fynd o'i le yma

518
00:44:21,850 --> 00:44:26,580
oherwydd ein bod yn delio â gwneud coed newydd a delio â awgrymiadau a phethau fel 'na.

519
00:44:26,580 --> 00:44:30,450
Cyn pan oeddem yn delio â awgrymiadau,

520
00:44:30,450 --> 00:44:36,580
pryd bynnag y byddwn malloc'd roeddem am wneud yn siŵr nad oedd yn dychwelyd i ni gwerth pwyntydd NULL.

521
00:44:36,580 --> 00:44:42,770
Felly, ar nifer o gamau o fewn y broses mae yn mynd i fod sawl achos

522
00:44:42,770 --> 00:44:45,920
lle y gallai eich rhaglen yn methu.

523
00:44:45,920 --> 00:44:51,310
Beth ydych eisiau ei wneud yw eich bod am wneud yn siŵr eich bod yn trin y camgymeriadau hynny,

524
00:44:51,310 --> 00:44:54,580
ac yn y fanyleb yn dweud eu trin yn osgeiddig,

525
00:44:54,580 --> 00:45:00,280
felly hoffwn argraffu neges i'r defnyddiwr ddweud wrthynt pam y rhaglen i roi'r gorau iddi

526
00:45:00,280 --> 00:45:03,050
ac yna rhoi'r gorau iddi yn brydlon hynny.

527
00:45:03,050 --> 00:45:09,490
Er mwyn gwneud hyn trin gwall, cofiwch eich bod am wirio

528
00:45:09,490 --> 00:45:12,160
bob tro y gallai fod yn fethiant.

529
00:45:12,160 --> 00:45:14,660
Bob tro sengl yr ydych chi'n gwneud pwyntydd newydd

530
00:45:14,660 --> 00:45:17,040
chi eisiau gwneud yn siŵr bod hynny'n llwyddiannus.

531
00:45:17,040 --> 00:45:20,320
Cyn hyn yr arferem ei wneud yw gwneud pwyntydd newydd a malloc hynny,

532
00:45:20,320 --> 00:45:22,380
ac yna byddem yn gwirio a yw'r pwyntydd yn null.

533
00:45:22,380 --> 00:45:25,670
Felly, mae mynd i fod rhai achosion lle dim ond gallwch wneud hynny,

534
00:45:25,670 --> 00:45:28,610
ond weithiau rydych chi mewn gwirionedd yn galw swyddogaeth

535
00:45:28,610 --> 00:45:33,100
ac o fewn y swyddogaeth honno, dyna yr un sydd wedi gwneud y mallocing.

536
00:45:33,100 --> 00:45:39,110
Yn yr achos hwnnw, os ydym yn edrych yn ôl at rai o'r swyddogaethau o fewn y cod,

537
00:45:39,110 --> 00:45:42,260
rhai ohonynt yn swyddogaethau Boolean.

538
00:45:42,260 --> 00:45:48,480
Yn yr achos haniaethol os oes gennym swyddogaeth Boolean o'r enw foo,

539
00:45:48,480 --> 00:45:54,580
yn y bôn, gallwn dybio, yn ychwanegol i wneud beth bynnag foo yn ei wneud,

540
00:45:54,580 --> 00:45:57,210
gan ei fod yn swyddogaeth Boole, mae'n dychwelyd wir neu ffug -

541
00:45:57,210 --> 00:46:01,300
wir os yw'n llwyddiannus, ffug os nad ydyw.

542
00:46:01,300 --> 00:46:06,270
Felly, rydym am i weld a yw'r gwerth dychwelyd foo yn wir neu'n anwir.

543
00:46:06,270 --> 00:46:10,400
Os yw'n anwir, mae hynny'n golygu ein bod ni'n mynd i eisiau argraffu rhyw fath o neges

544
00:46:10,400 --> 00:46:14,390
ac yna gadael y rhaglen.

545
00:46:14,390 --> 00:46:18,530
Yr hyn yr ydym eisiau ei wneud yw gwirio gwerth dychwelyd foo.

546
00:46:18,530 --> 00:46:23,310
Os foo yn dychwelyd ffug, yna rydym yn gwybod ein bod yn dod ar draws rhyw fath o wall

547
00:46:23,310 --> 00:46:25,110
ac mae angen i ni roi'r gorau ein rhaglen.

548
00:46:25,110 --> 00:46:35,600
Un ffordd o wneud hyn yw os oes gennych gyflwr lle mae'r swyddogaeth ei hun yw eich cyflwr.

549
00:46:35,600 --> 00:46:39,320
Dweud foo yn cymryd yn x.

550
00:46:39,320 --> 00:46:43,390
Gallwn gael fel amod os (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Yn y bôn, mae hynny'n golygu os, ar ddiwedd weithredu foo mae'n dychwelyd wir,

552
00:46:50,900 --> 00:46:57,390
yna gallwn wneud hyn gan fod y swyddogaeth wedi i werthuso foo

553
00:46:57,390 --> 00:47:00,500
er mwyn gwerthuso cyflwr cyfan.

554
00:47:00,500 --> 00:47:06,500
Felly, yna dyna sut y gallwch wneud rhywbeth os yw'r swyddogaeth yn dychwelyd yn wir ac yn llwyddiannus.

555
00:47:06,500 --> 00:47:11,800
Ond pan fyddwch yn gwirio gwallau, dim ond am roi'r gorau iddi os yw eich swyddogaeth yn dychwelyd ffug.

556
00:47:11,800 --> 00:47:16,090
Beth allech chi ei wneud yw unig ychwanegu == ffug neu ddim ond ychwanegu bang o'i flaen

557
00:47:16,090 --> 00:47:21,010
ac yna mae gennych os (! foo).

558
00:47:21,010 --> 00:47:29,540
O fewn y corff hwnnw amod hwnnw byddai gennych yr holl trin gwall,

559
00:47:29,540 --> 00:47:36,940
felly fel, "Methu creu y goeden hon" ac yna dychwelyd 1 neu rywbeth fel 'na.

560
00:47:36,940 --> 00:47:43,340
Beth yw hynny, fodd bynnag, yw bod hyd yn oed er foo dychwelyd ffug -

561
00:47:43,340 --> 00:47:46,980
Dweud foo yn dychwelyd wir.

562
00:47:46,980 --> 00:47:51,060
Yna nid oes rhaid i chi alw foo eto. Dyna gamsyniad cyffredin.

563
00:47:51,060 --> 00:47:54,730
Gan ei fod yn eich cyflwr, mae'n gwerthuso eisoes,

564
00:47:54,730 --> 00:47:59,430
er mwyn i chi eisoes yn cael y canlyniad os ydych yn defnyddio yn gwneud coeden neu rywbeth fel 'na

565
00:47:59,430 --> 00:48:01,840
neu offer neu ddewis neu rywbeth.

566
00:48:01,840 --> 00:48:07,460
Mae eisoes yn ei werth. Mae'n gweithredu yn barod.

567
00:48:07,460 --> 00:48:10,730
Felly mae'n ddefnyddiol i ddefnyddio swyddogaethau Boolean yn y cyflwr

568
00:48:10,730 --> 00:48:13,890
oherwydd p'un ai a ydych mewn gwirionedd yn gweithredu y corff y ddolen,

569
00:48:13,890 --> 00:48:18,030
wneir ganddo swyddogaeth beth bynnag.

570
00:48:22,070 --> 00:48:27,330
>> Mae ein ail gam olaf yn ysgrifennu neges at y ffeil.

571
00:48:27,330 --> 00:48:33,070
Unwaith y byddwn yn adeiladu y goeden Huffman, yna ysgrifennu neges at y ffeil yn eithaf syml.

572
00:48:33,070 --> 00:48:39,260
Mae'n eithaf syml yn awr i dilynwch y 0s a 1s.

573
00:48:39,260 --> 00:48:45,480
Ac felly gan gonfensiwn rydym yn gwybod bod mewn coeden Huffman y 0au ddatgan eu gadael

574
00:48:45,480 --> 00:48:48,360
a'r 1s yn dangos iawn.

575
00:48:48,360 --> 00:48:53,540
Felly, yna os ydych yn darllen yn fesul tipyn, bob tro eich bod yn cael o 0

576
00:48:53,540 --> 00:48:59,100
byddwch yn dilyn y gangen chwith, ac yna bob tro y byddwch yn darllen 1

577
00:48:59,100 --> 00:49:02,100
rydych yn mynd i ddilyn y gangen cywir.

578
00:49:02,100 --> 00:49:07,570
Ac yna rydych chi'n mynd i barhau hyd nes y byddwch yn taro deilen

579
00:49:07,570 --> 00:49:11,550
oherwydd bod y dail yn mynd i fod ar ddiwedd y canghennau.

580
00:49:11,550 --> 00:49:16,870
Sut allwn ni ddweud a ydym wedi taro ddeilen neu beidio?

581
00:49:19,800 --> 00:49:21,690
Rydym yn dweud hyn o'r blaen.

582
00:49:21,690 --> 00:49:24,040
[Myfyrwyr] Os yw'r arwyddion yn null. >> Yeah.

583
00:49:24,040 --> 00:49:32,220
Gallwn ddweud os ydym wedi taro deilen os yw'r awgrymiadau i goed y chwith a'r dde yn null.

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

585
00:49:34,110 --> 00:49:40,320
Rydym yn gwybod ein bod yn dymuno darllen fesul tipyn i mewn i'n Huff ffeil.

586
00:49:43,870 --> 00:49:51,220
Fel y gwelsom o'r blaen yn dump.c, yr hyn a wnaethant yn eu darllen fesul tipyn i mewn i'r ffeil Huff

587
00:49:51,220 --> 00:49:54,560
a'i argraffu yn unig allan beth oedd y darnau oedd.

588
00:49:54,560 --> 00:49:58,430
Nid ydym yn mynd i fod yn gwneud hynny. Rydym yn mynd i fod yn gwneud rhywbeth sydd ychydig yn fwy cymhleth.

589
00:49:58,430 --> 00:50:03,620
Ond yr hyn y gallwn ei wneud yw y gallwn gymryd ychydig o god sy'n darllen i mewn i'r bit.

590
00:50:03,620 --> 00:50:10,250
Yma, mae gennym y darn cyfanrif cynrychioli y rhan ar hyn o bryd yr ydym yn bod ar.

591
00:50:10,250 --> 00:50:15,520
Mae hyn yn gofalu am ailadrodd yr holl ddarnau yn y ffeil hyd nes i chi gyrraedd diwedd y ffeil.

592
00:50:15,520 --> 00:50:21,270
Yn seiliedig ar hynny, yna rydych chi'n mynd i eisiau cael rhyw fath o iterator

593
00:50:21,270 --> 00:50:26,760
i groesi eich coeden.

594
00:50:26,760 --> 00:50:31,460
Ac yn seiliedig wedyn ar p'un a yw'r darn yn 0 neu 1,

595
00:50:31,460 --> 00:50:36,920
ydych yn mynd i eisiau i naill ai symud y iterator i'r chwith neu ei symud i'r dde

596
00:50:36,920 --> 00:50:44,080
yr holl ffordd hyd nes y byddwch yn taro deilen, felly mae'r holl ffordd hyd y nod eich bod ar

597
00:50:44,080 --> 00:50:48,260
nid yw'n cyfeirio at unrhyw nodau mwy.

598
00:50:48,260 --> 00:50:54,300
Gall Pam rydym yn gwneud hyn gyda ffeil Huffman ond nid côd Morse?

599
00:50:54,300 --> 00:50:56,610
Oherwydd mewn côd Morse mae ychydig o amwysedd.

600
00:50:56,610 --> 00:51:04,440
Gallem fod yn debyg, oh aros, rydym wedi taro llythyr ar hyd y ffordd, felly efallai fod hyn yn ein llythyr,

601
00:51:04,440 --> 00:51:08,150
ond os ydym yn parhau dim ond ychydig yn hirach, yna byddem wedi taro llythyr arall.

602
00:51:08,150 --> 00:51:13,110
Ond nid yw hynny'n mynd i ddigwydd yn Huffman amgodio,

603
00:51:13,110 --> 00:51:17,540
fel y gallwn fod yn sicr mai'r unig ffordd ein bod ni'n mynd i daro gymeriad

604
00:51:17,540 --> 00:51:23,480
yw os yw plant y nod yn y chwith a dde yn null.

605
00:51:28,280 --> 00:51:32,350
>> Yn olaf, rydym am i ryddhau ein holl cof.

606
00:51:32,350 --> 00:51:37,420
Rydym am yn agos y ffeil Huff ein bod ni wedi bod yn delio â

607
00:51:37,420 --> 00:51:41,940
yn ogystal â dileu pob un o'r coed yn ein goedwig.

608
00:51:41,940 --> 00:51:46,470
Yn seiliedig ar eich gweithredu, mae'n debyg eich bod yn mynd i eisiau i alw gwared goedwig

609
00:51:46,470 --> 00:51:49,780
hytrach na mewn gwirionedd yn mynd drwy bob un o'r coed eich hun.

610
00:51:49,780 --> 00:51:53,430
Ond os ydych wedi gwneud unrhyw goed dros dro, youll 'angen at ryddhau hynny.

611
00:51:53,430 --> 00:51:59,060
Rydych yn gwybod eich cod orau, fel eich bod yn gwybod ble rydych chi'n dyrannu cof.

612
00:51:59,060 --> 00:52:04,330
Ac felly os ydych yn mynd i mewn, dechreuwch gan hyd yn oed Rheoli f'ing gyfer malloc,

613
00:52:04,330 --> 00:52:08,330
gweld pan fyddwch yn malloc a gwneud yn siwr eich bod yn rhyddhau hynny i gyd

614
00:52:08,330 --> 00:52:10,190
ond yna dim ond yn mynd drwy eich cod,

615
00:52:10,190 --> 00:52:14,260
deall lle y gallech fod wedi dyrannu cof.

616
00:52:14,260 --> 00:52:21,340
Fel arfer, efallai y byddwch yn dweud, "Ar ddiwedd y ffeil Im 'jyst yn mynd i gael gwared ar fy coedwig coedwig,"

617
00:52:21,340 --> 00:52:23,850
felly yn y bôn yn glir bod y cof, rhad ac am ddim, yn

618
00:52:23,850 --> 00:52:28,310
"Ac yna Rwyf hefyd yn mynd i gau ffeil ac yna fy rhaglen yn mynd i roi'r gorau iddi."

619
00:52:28,310 --> 00:52:33,810
Ond yw bod yr amser yn unig bod eich rhaglen ymddiswyddo?

620
00:52:33,810 --> 00:52:37,880
Na, oherwydd weithiau efallai y bu gwall a ddigwyddodd.

621
00:52:37,880 --> 00:52:42,080
Efallai na allem agor ffeil neu nid oeddem yn gallu gwneud coeden arall

622
00:52:42,080 --> 00:52:49,340
neu ryw fath o wall yn digwydd yn y dyraniad cof broses ac felly mae'n dychwelyd null.

623
00:52:49,340 --> 00:52:56,710
Mae gwall wedi digwydd ac yna aethom yn ôl a rhoi'r gorau iddi.

624
00:52:56,710 --> 00:53:02,040
Felly, yna rydych eisiau gwneud yn siŵr bod unrhyw adeg bosibl y gall eich rhaglen rhoi'r gorau iddi,

625
00:53:02,040 --> 00:53:06,980
ydych am i ryddhau eich holl cof yno.

626
00:53:06,980 --> 00:53:13,370
Nid dim ond yn mynd i fod ar y ddiwedd y brif swyddogaeth yr ydych yn rhoi'r gorau iddi eich cod.

627
00:53:13,370 --> 00:53:20,780
Byddwch am edrych yn ôl i bob achos bod eich cod gallai o bosibl dychwelyd gynamserol

628
00:53:20,780 --> 00:53:25,070
ac yna rhad ac am ddim beth bynnag cof yn gwneud synnwyr.

629
00:53:25,070 --> 00:53:30,830
Dywedwch eich bod wedi galw wneud goedwig ac a ddychwelodd ffug.

630
00:53:30,830 --> 00:53:34,230
Yna byddwch yn debyg na fydd angen i dynnu eich coedwig

631
00:53:34,230 --> 00:53:37,080
oherwydd nad oes gennych goedwig eto.

632
00:53:37,080 --> 00:53:42,130
Ond ar bob pwynt yn y cod lle efallai y byddwch yn dychwelyd gynamserol

633
00:53:42,130 --> 00:53:46,160
ydych am wneud yn siŵr eich bod yn rhyddhau unrhyw cof posibl.

634
00:53:46,160 --> 00:53:50,020
>> Felly, pan fyddwn yn delio â rhyddhau cof a chael gollyngiadau posibl,

635
00:53:50,020 --> 00:53:55,440
rydym am i nid yn unig yn defnyddio ein barn a'n rhesymeg

636
00:53:55,440 --> 00:54:01,850
ond hefyd yn defnyddio Valgrind i benderfynu a ydym wedi rhyddhau ein holl cof yn iawn neu beidio.

637
00:54:01,850 --> 00:54:09,460
Gallwch un ai redeg Valgrind ar pwff ac yna rhaid i chi hefyd basio

638
00:54:09,460 --> 00:54:14,020
y nifer cywir o gorchymyn-lein dadleuon i Valgrind.

639
00:54:14,020 --> 00:54:18,100
Gallwch redeg hynny, ond bydd y canlyniadau ychydig yn cryptig.

640
00:54:18,100 --> 00:54:21,630
Rydym wedi gotten ychydig i arfer ag ef gyda Speller, ond rydym yn dal angen help ychydig yn fwy,

641
00:54:21,630 --> 00:54:26,450
felly, yna ei redeg gyda baneri ychydig mwy fel y gollyngiad-wirio = llawn,

642
00:54:26,450 --> 00:54:32,040
a fydd yn ôl pob tebyg yn rhoi i ni rhywfaint o allbwn yn fwy defnyddiol ar Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Yna arall tip ddefnyddiol pan fyddwch yn debugging yw'r gorchymyn diff.

644
00:54:39,040 --> 00:54:48,520
Gallwch gael mynediad weithrediad y staff o Huff, yn rhedeg hynny ar ffeil destun,

645
00:54:48,520 --> 00:54:55,400
ac yna allbwn i ffeil ddeuaidd, ffeil ddeuaidd Huff, i fod yn benodol.

646
00:54:55,400 --> 00:54:59,440
Yna, os ydych yn rhedeg eich pwff hun ar y ffeil ddeuaidd,

647
00:54:59,440 --> 00:55:03,950
yna yn ddelfrydol, eich ffeil testun outputted yn mynd i fod yn union yr un fath

648
00:55:03,950 --> 00:55:08,200
i'r un gwreiddiol yr ydych yn pasio i mewn

649
00:55:08,200 --> 00:55:15,150
Dyma Im 'yn arfer hth.txt fel enghraifft, a dyna'r neb yn siarad amdanynt yn eich fanyleb.

650
00:55:15,150 --> 00:55:21,040
Dyna llythrennol dim ond HTH ac yna Newline.

651
00:55:21,040 --> 00:55:30,970
Ond yn bendant yn teimlo am ddim ac fe'ch anogir bendant i ddefnyddio enghreifftiau hirach

652
00:55:30,970 --> 00:55:32,620
ar gyfer eich ffeil testun.

653
00:55:32,620 --> 00:55:38,110
>> Gallwch hyd yn oed gymryd ergyd yn efallai cywasgu ac yna ddatgywasgu

654
00:55:38,110 --> 00:55:41,600
rhai o'r ffeiliau yr ydych yn ei ddefnyddio mewn Speller fel Rhyfel a Heddwch

655
00:55:41,600 --> 00:55:46,710
neu Jane Austen neu rywbeth fel 'na - byddai hynny'n fath o oer - neu Pwerau Austin,

656
00:55:46,710 --> 00:55:51,880
math o ddelio gyda ffeiliau mawr oherwydd ni fyddem yn dod i lawr iddo

657
00:55:51,880 --> 00:55:55,590
os ydym yn defnyddio'r offeryn nesaf yma, ls-l.

658
00:55:55,590 --> 00:56:01,150
Rydym yn eu defnyddio i ls, sydd yn y bôn yn rhestru'r holl gynnwys yn ein cyfeirlyfr ar hyn o bryd.

659
00:56:01,150 --> 00:56:07,860
Pasio yn y faner-l mewn gwirionedd yn dangos maint y ffeiliau.

660
00:56:07,860 --> 00:56:12,690
Os byddwch yn mynd trwy'r fanyleb pset, mewn gwirionedd mae'n cerdded chi drwy greu'r ffeil ddeuaidd,

661
00:56:12,690 --> 00:56:16,590
o chwythu, ac yr ydych yn gweld bod ar gyfer ffeiliau bach iawn

662
00:56:16,590 --> 00:56:23,910
cost gofod o gywasgu ac yn cyfieithu holl wybodaeth honno

663
00:56:23,910 --> 00:56:26,980
o'r holl amleddau a phethau fel 'na yn drech na'r budd gwirioneddol

664
00:56:26,980 --> 00:56:30,000
o gywasgu'r ffeil yn y lle cyntaf.

665
00:56:30,000 --> 00:56:37,450
Ond os ydych yn rhedeg ar rai ffeiliau testun hirach, yna efallai y byddwch yn gweld eich bod yn dechrau cael rhywfaint o fudd

666
00:56:37,450 --> 00:56:40,930
wrth gywasgu ffeiliau hynny.

667
00:56:40,930 --> 00:56:46,210
>> Ac yna yn olaf, rydym wedi ein GDB pal oed, sy'n cael ei bendant yn mynd i ddod i mewn 'n hylaw hefyd.

668
00:56:48,360 --> 00:56:55,320
>> A oes gennym unrhyw gwestiynau ar goed Huff neu'r broses efallai o wneud y coed

669
00:56:55,320 --> 00:56:58,590
neu unrhyw gwestiynau eraill ar Huff'n pwff?

670
00:57:00,680 --> 00:57:02,570
Iawn. 'N annhymerus' aros o gwmpas am ychydig.

671
00:57:02,570 --> 00:57:06,570
>> Diolch, bawb. Roedd hyn yn Walkthrough 6. A phob lwc.

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