1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Artikolu 7] [Inqas Komdu]

2
00:00:02,500 --> 00:00:04,890
[Nate Hardison] [Università ta 'Harvard]

3
00:00:04,890 --> 00:00:07,000
[Dan huwa CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Merħba għas-Sezzjoni 7.

5
00:00:09,080 --> 00:00:11,330
Grazzi għall uragan Ramlija,

6
00:00:11,330 --> 00:00:13,440
minflok li jkollha sezzjoni normali din il-ġimgħa,

7
00:00:13,440 --> 00:00:17,650
aħna qed tagħmel dan walk-through, permezz tat-taqsima tal-mistoqsijiet.

8
00:00:17,650 --> 00:00:22,830
Jien ser jiġu wara flimkien mal-Problema Set 6 Ispeċifikazzjoni,

9
00:00:22,830 --> 00:00:25,650
u li jmorru kollha permezz tal-mistoqsijiet fl-

10
00:00:25,650 --> 00:00:27,770
A sezzjoni ta 'Mistoqsijiet sezzjoni.

11
00:00:27,770 --> 00:00:30,940
Jekk ikun hemm xi mistoqsijiet,

12
00:00:30,940 --> 00:00:32,960
jekk jogħġbok post dawn fuq CS50 Iddiskuti.

13
00:00:32,960 --> 00:00:35,480
>> Alright. Ejja tibda.

14
00:00:35,480 --> 00:00:40,780
Dritt issa jien tħares lejn paġna 3 tal-Ispeċifikazzjoni Set Problema.

15
00:00:40,780 --> 00:00:44,110
Aħna ser ewwel tibda jitkellem dwar siġar binarju

16
00:00:44,110 --> 00:00:47,850
peress li dawn għandhom ħafna ta 'rilevanza għal sett problema din il-ġimgħa -

17
00:00:47,850 --> 00:00:49,950
il-kodifikazzjoni Tree Huffman.

18
00:00:49,950 --> 00:00:55,000
Wieħed mill-istrutturi tad-data ħafna ewwel tkellimna dwar fuq CS50 kien il-firxa.

19
00:00:55,000 --> 00:01:00,170
Ftakar li l-firxa hija sekwenza ta 'elementi -

20
00:01:00,170 --> 00:01:04,019
kollha ta 'l-istess tip - maħżuna dritt li jmiss ma' xulxin fil-memorja.

21
00:01:04,019 --> 00:01:14,420
Jekk I jkollhom firxa integer li nista 'jiġbed jużaw dan l-istil kaxxi-numri interi--

22
00:01:14,420 --> 00:01:20,290
Ejja ngħidu għandi 5 fil-kaxxa 1, għandi 7 fit-tieni,

23
00:01:20,290 --> 00:01:27,760
imbagħad għandi 8, 10, u 20 fil-kaxxa finali.

24
00:01:27,760 --> 00:01:33,000
Affarijiet Ftakar, it-tnejn verament tajba dwar dan array

25
00:01:33,000 --> 00:01:38,800
huma li aħna għandna dan l-aċċess kontinwu ta 'żmien li kull element partikolari

26
00:01:38,800 --> 00:01:40,500
 fil-firxa jekk nafu indiċi tagħha.

27
00:01:40,500 --> 00:01:44,670
Per eżempju, jekk irrid grab-tielet element fil-firxa -

28
00:01:44,670 --> 00:01:47,870
fil-indiċi 2 jużaw sistema tagħna indiċjar zero bbażati fuq -

29
00:01:47,870 --> 00:01:52,220
I litteralment biss għandek tagħmel kalkolu matematiku sempliċi,

30
00:01:52,220 --> 00:01:56,170
tal-ħops li din il-pożizzjoni fil-firxa,

31
00:01:56,170 --> 00:01:57,840
iġbed il-8 li hija maħżuna hemmhekk,

32
00:01:57,840 --> 00:01:59,260
u jien tajba biex tmur.

33
00:01:59,260 --> 00:02:03,350
>> Waħda mill-affarijiet ħżiena dwar dan array - li tkellimna dwar

34
00:02:03,350 --> 00:02:05,010
meta aħna diskussi listi marbuta -

35
00:02:05,010 --> 00:02:09,120
hija li jekk jien tixtieq li daħħal element fis dan array,

36
00:02:09,120 --> 00:02:11,090
Jien ser ikollhom jagħmlu xi ċaqliq madwar.

37
00:02:11,090 --> 00:02:12,940
Per eżempju, dan array dritt hawn

38
00:02:12,940 --> 00:02:16,850
hija fl-ordni magħżula - magħżula f'ordni axxendenti -

39
00:02:16,850 --> 00:02:19,440
5, imbagħad 7, allura 8, allura 10, u mbagħad 20 -

40
00:02:19,440 --> 00:02:23,100
imma jekk jien tixtieq li daħħal in-numru 9 fi dan il-firxa,

41
00:02:23,100 --> 00:02:27,460
Jien ser ikollhom li ċċaqlaq xi wħud mill-elementi sabiex tagħmel spazju.

42
00:02:27,460 --> 00:02:30,440
Nistgħu nużaw dan hawn.

43
00:02:30,440 --> 00:02:35,650
Jien ser ikollhom biex iċċaqlaq il-5, is-7, u allura l-8;

44
00:02:35,650 --> 00:02:38,720
toħloq lakuna fejn I tista 'tpoġġi l-9,

45
00:02:38,720 --> 00:02:45,910
u allura l-10 u l-20 tista 'tmur għad-dritt ta' l-9.

46
00:02:45,910 --> 00:02:49,450
Dan huwa tip ta 'uġigħ minħabba fil-agħar xenarju -

47
00:02:49,450 --> 00:02:54,350
meta qed ikollna li daħħal kemm fil-bidu jew fl-aħħar

48
00:02:54,350 --> 00:02:56,040
ta 'l-array, jiddependi fuq kif aħna qed tiċċaqlaq -

49
00:02:56,040 --> 00:02:58,850
nistgħu jispiċċaw wara li ċċaqlaq l-elementi kollha

50
00:02:58,850 --> 00:03:00,750
li aħna qed attwalment ħażna fil-firxa.

51
00:03:00,750 --> 00:03:03,810
>> Allura, dak li kien il-mod madwar dan?

52
00:03:03,810 --> 00:03:09,260
Il-mod madwar dan kien li tmur linked-lista tagħna Metodu meta -

53
00:03:09,260 --> 00:03:19,820
minflok ħażna tal-elementi 5, 7, 8, 10, u 20 kull ħdejn xulxin fil-memorja -

54
00:03:19,820 --> 00:03:25,630
dak li aħna minflok ma ġie jaħżinhom tip ta 'fejn ridna li jaħżinhom

55
00:03:25,630 --> 00:03:32,470
f'dawn lymph lista linked-liema jien tpinġija hawn, it-tip ta 'ad hoc.

56
00:03:32,470 --> 00:03:42,060
U allura aħna konnessi flimkien jużaw dawn pointers jmiss.

57
00:03:42,060 --> 00:03:44,370
I jista 'jkollhom pointer minn 5 sa l-7,

58
00:03:44,370 --> 00:03:46,420
pointer mill-7 sa l-8,

59
00:03:46,420 --> 00:03:47,770
pointer mill-8 sa l-10,

60
00:03:47,770 --> 00:03:51,220
u finalment, pointer mill-10 sa l-20,

61
00:03:51,220 --> 00:03:54,880
u mbagħad pointer null fil-20 jindikaw li hemm xejn xellug.

62
00:03:54,880 --> 00:03:59,690
Il-kompromess li għandna hawn

63
00:03:59,690 --> 00:04:05,360
hija li issa jekk irridu li daħħal in-numru 9 fil-lista magħżula tagħna,

64
00:04:05,360 --> 00:04:08,270
kollha għandna tagħmel hu li toħloq node ġdid ma 9,

65
00:04:08,270 --> 00:04:12,290
wajer it up għall-punt li l-post xieraq,

66
00:04:12,290 --> 00:04:20,630
u mbagħad mill-ġdid tal-wajer l-8-punt sa l-9.

67
00:04:20,630 --> 00:04:25,660
Li pretty fast, jekk wieħed jassumi nafu eżattament fejn irridu li daħħal il-9.

68
00:04:25,660 --> 00:04:32,610
Iżda l-kompromess bi skambju għal dan hija li aħna stajt issa tilfu l-aċċess kontinwu ta 'żmien

69
00:04:32,610 --> 00:04:36,230
għal kull element partikolari fl-istruttura tad-data tagħna.

70
00:04:36,230 --> 00:04:40,950
Per eżempju, jekk irrid li ssib l-element 4 f'din il-lista konness,

71
00:04:40,950 --> 00:04:43,510
Jien ser ikollhom jibdew fil-bidu nett tal-lista

72
00:04:43,510 --> 00:04:48,930
u x-xogħol tiegħi mod permezz għadd node-by-node sal I isibu l-waħda raba '.

73
00:04:48,930 --> 00:04:55,870
>> Sabiex tikseb aċċess aħjar prestazzjoni minn lista marbuta -

74
00:04:55,870 --> 00:04:59,360
iżda wkoll iżommu xi wħud mill-benefiċċji li kellna

75
00:04:59,360 --> 00:05:01,800
f'termini ta 'dħul-time minn lista marbuta -

76
00:05:01,800 --> 00:05:05,750
siġra binarju huwa ser ikollok bżonn tuża memorja ftit aktar.

77
00:05:05,750 --> 00:05:11,460
B'mod partikolari, minflok sempliċiment li wieħed pointer fi node siġra binarju -

78
00:05:11,460 --> 00:05:13,350
ma node bħall-lista marbuta--

79
00:05:13,350 --> 00:05:16,950
aħna qed tmur biex iżżid pointer 2 għall-node siġra binarju.

80
00:05:16,950 --> 00:05:19,950
Pjuttost milli sempliċiment wara li wieħed pointer għall-element li jmiss,

81
00:05:19,950 --> 00:05:24,420
aħna qed tmur biex ikollhom pointer għal tfal xellug u tifel dritt.

82
00:05:24,420 --> 00:05:26,560
>> Ejja tfassal stampa biex tara dak li attwalment tidher qiesha.

83
00:05:26,560 --> 00:05:31,350
Għal darb'oħra, jien ser jużaw dawn il-kaxxi u l-vleġeġ.

84
00:05:31,350 --> 00:05:37,150
A node siġra binarju se tibda off ma biss kaxxa sempliċi.

85
00:05:37,150 --> 00:05:40,940
Huwa ser jkollhom spazju għall-valur,

86
00:05:40,940 --> 00:05:47,280
u allura huwa wkoll se jkollhom spazju għall-tarbija xellug u l-minuri dritt.

87
00:05:47,280 --> 00:05:49,280
Jien ser tikketta hawnhekk.

88
00:05:49,280 --> 00:05:57,560
Aħna ser ikollhom it-tfal tax-xellug, u allura aħna qed tmur biex ikollhom it-tfal dritt.

89
00:05:57,560 --> 00:05:59,920
Hemm ħafna modi differenti ta 'kif isir dan.

90
00:05:59,920 --> 00:06:02,050
Kultant għall-ispazju u l-konvenjenza,

91
00:06:02,050 --> 00:06:06,460
I ser attwalment tiġbed simili li qed nagħmel hawn fuq il-qiegħ

92
00:06:06,460 --> 00:06:10,910
fejn jien ser ikollhom l-valur fil-quċċata,

93
00:06:10,910 --> 00:06:14,060
u allura l-wild dritt fuq il-qiegħ dritt,

94
00:06:14,060 --> 00:06:16,060
u l-wild xellug fuq il-qiegħ tax-xellug.

95
00:06:16,060 --> 00:06:20,250
Li jmorru lura għal dan dijagramma ta 'fuq,

96
00:06:20,250 --> 00:06:22,560
aħna għandna l-valur fuq nett,

97
00:06:22,560 --> 00:06:25,560
allura aħna għandna l-pointer fuq ix-tfal, u allura għandna l-pointer dritt tat-tfal.

98
00:06:25,560 --> 00:06:30,110
>> Fil-Ispeċifikazzjoni Set Problema,

99
00:06:30,110 --> 00:06:33,110
nitkellmu dwar tfassil node li għandu valur 7,

100
00:06:33,110 --> 00:06:39,750
u mbagħad pointer fuq ix-xellug tat-tfal li huwa null, u pointer dritt tat-tfal li huwa null.

101
00:06:39,750 --> 00:06:46,040
Nistgħu jew ikteb NULL kapital fl-ispazju għall-

102
00:06:46,040 --> 00:06:51,610
kemm il-wild xellug u l-minuri dritt, jew nistgħu jiġbed dan mmejla dijagonali

103
00:06:51,610 --> 00:06:53,750
permezz ta 'kull tal-kaxxi li tindika li huwa null.

104
00:06:53,750 --> 00:06:57,560
Jien ser jagħmlu dan biss għaliex dan huwa sempliċi.

105
00:06:57,560 --> 00:07:03,700
Dak li tara hawnhekk huma żewġ modi ta 'diagramming sempliċi ħafna node siġra binarju

106
00:07:03,700 --> 00:07:07,960
fejn għandna l-valur 7 u pointers tfal nulla.

107
00:07:07,960 --> 00:07:15,220
>> It-tieni parti ta 'taħdidiet speċifikazzjoni tagħna dwar kif ma' listi marbuta -

108
00:07:15,220 --> 00:07:18,270
ftakar, aħna biss kellhom jżommu lill-element ewwel fil-lista

109
00:07:18,270 --> 00:07:20,270
li tiftakar il-lista sħiħa -

110
00:07:20,270 --> 00:07:26,140
u l-istess, ma 'siġra binarju, aħna biss biex iżomm il-1 pointer għall-siġra

111
00:07:26,140 --> 00:07:31,120
sabiex jinżamm kontroll fuq l-istruttura tad-data kollha.

112
00:07:31,120 --> 00:07:36,150
Dan l-element speċjali tas-siġra huwa msejjaħ il-node għerq tal-siġra.

113
00:07:36,150 --> 00:07:43,360
Per eżempju, jekk dan node wieħed - dan node fih il-valur 7

114
00:07:43,360 --> 00:07:45,500
ma pointers nulla xellug-u dritt tat-tfal -

115
00:07:45,500 --> 00:07:47,360
kienu l-valur biss siġar tagħna,

116
00:07:47,360 --> 00:07:50,390
allura dan ikun node għerq tagħna.

117
00:07:50,390 --> 00:07:52,240
Hu l-bidu nett ta 'siġar tagħna.

118
00:07:52,240 --> 00:07:58,530
Nistgħu naraw dan ftit aktar ċar darba nibdew żżid għoqiedi aktar siġar tagħna.

119
00:07:58,530 --> 00:08:01,510
Let me pull up paġna ġdida.

120
00:08:01,510 --> 00:08:05,000
>> Issa aħna qed tmur biex tiġbed siġra li għandha 7 fil-għerq,

121
00:08:05,000 --> 00:08:10,920
u 3 ta 'ġewwa tal-wild xellug, u 9 ta' ġewwa tal-wild dritt.

122
00:08:10,920 --> 00:08:13,500
Għal darb'oħra, dan huwa pjuttost sempliċi.

123
00:08:13,500 --> 00:08:26,510
Imxejna ltqajna 7, jiġbed node għall-3, node għal 9,

124
00:08:26,510 --> 00:08:32,150
u jien ser jistabbilixxu l-pointer fuq ix-xellug tifel ta '7 għall-punt li l-node fih 3,

125
00:08:32,150 --> 00:08:37,850
u l-pointer dritt tat-tfal ta 'l-node fih 7 għall-node fih 9.

126
00:08:37,850 --> 00:08:42,419
Issa, peress 3 u 9 ma jkollhom ebda tfal,

127
00:08:42,419 --> 00:08:48,500
aħna qed tmur biex jistabbilixxu kollha ta 'pointers tfal tagħhom li jkunu null.

128
00:08:48,500 --> 00:08:56,060
Hawnhekk, l-għerq tal-siġra tagħna tikkorrispondi mal-node fih in-numru 7.

129
00:08:56,060 --> 00:09:02,440
Tista 'tara li jekk kollha għandna huwa pointer għal dak node għerq,

130
00:09:02,440 --> 00:09:07,330
nistgħu mbagħad jimxu permezz tas-siġar tagħna u l-aċċess lymph tfal iż -

131
00:09:07,330 --> 00:09:10,630
kemm 3 u 9.

132
00:09:10,630 --> 00:09:14,820
Ebda ħtieġa li tinżamm pointers għal kull node wieħed fuq is-siġra.

133
00:09:14,820 --> 00:09:22,080
Alright. Issa aħna qed tmur biex żid ieħor node għal din dijagramma.

134
00:09:22,080 --> 00:09:25,370
Aħna ser iżid node fih 6,

135
00:09:25,370 --> 00:09:34,140
u aħna qed tmur biex iżżid dan bħala l-wild dritt ta 'l-node fih 3.

136
00:09:34,140 --> 00:09:41,850
Biex tagħmel dan, jien ser iħassar dik pointer null fil-3-node

137
00:09:41,850 --> 00:09:47,750
u wajer it up għall-punt li l-node fih 6. Alright.

138
00:09:47,750 --> 00:09:53,800
>> Fuq dan il-punt, ejja jmorru fuq ftit ta 'terminoloġija.

139
00:09:53,800 --> 00:09:58,230
Biex tibda, ir-raġuni li din tissejjaħ siġra binarju, b'mod partikolari

140
00:09:58,230 --> 00:10:00,460
huwa li għandha pointers tfal 2.

141
00:10:00,460 --> 00:10:06,020
Hemm tipi oħra ta 'siġar li għandhom pointers tfal aktar.

142
00:10:06,020 --> 00:10:10,930
B'mod partikolari, inti għamilt "jippruvaw" fil Set Problem 5.

143
00:10:10,930 --> 00:10:19,310
Int ser ikollok avviż li f'dak jipprova, kellek 27 pointers differenti għal tfal differenti -

144
00:10:19,310 --> 00:10:22,410
wieħed għal kull waħda mill-ittri 26 fil-alfabett Ingliż,

145
00:10:22,410 --> 00:10:25,410
u allura l-27 għall-apostrophe -

146
00:10:25,410 --> 00:10:28,900
hekk, li huwa simili għal tip ta 'siġra.

147
00:10:28,900 --> 00:10:34,070
Iżda hawnhekk, peress binarja huwa, aħna biss pointers tfal 2.

148
00:10:34,070 --> 00:10:37,880
>> Barra minn dan node għerq li tkellimna dwar,

149
00:10:37,880 --> 00:10:41,470
konna wkoll ġew jitfg madwar dan it-terminu "tfal."

150
00:10:41,470 --> 00:10:44,470
Xi jfisser għal wieħed node li huma tfal ta 'ieħor node?

151
00:10:44,470 --> 00:10:54,060
Huwa letteralment ifisser li node wild huwa tifel ta 'ieħor node

152
00:10:54,060 --> 00:10:58,760
jekk dik il-node ieħor għandha waħda mill pointers tfal tagħha stabbiliti għall-punt li dak node.

153
00:10:58,760 --> 00:11:01,230
Biex dan f'termini iktar konkreti,

154
00:11:01,230 --> 00:11:11,170
jekk 3 huwa indikat minn wieħed mill-pointers tfal ta '7, allura 3 huwa tifel ta' 7.

155
00:11:11,170 --> 00:11:14,510
Jekk konna li ċifra barra dak it-tfal ta '7 huma -

156
00:11:14,510 --> 00:11:18,510
ukoll, naraw li 7 għandu pointer sa 3 u pointer sa 9,

157
00:11:18,510 --> 00:11:22,190
hekk 9 u 3 huma t-tfal ta 7.

158
00:11:22,190 --> 00:11:26,650
Disa m'għandha l-ebda tfal minħabba pointers tfal tagħha huma nulli,

159
00:11:26,650 --> 00:11:30,940
u 3 għandu biss wild wieħed, 6.

160
00:11:30,940 --> 00:11:37,430
Sitta wkoll għandha l-ebda tfal minħabba tnejn pointers tagħha huma nulli, li aħna ser tiġbed dritt issa.

161
00:11:37,430 --> 00:11:45,010
>> Barra minn hekk, aħna wkoll jitkellmu dwar il-ġenituri ta 'node partikolari,

162
00:11:45,010 --> 00:11:51,100
u dan huwa, kif youd jistennew, il-maqlub ta 'din id-deskrizzjoni tat-tfal.

163
00:11:51,100 --> 00:11:58,620
Kull node għandha ġenitur wieħed biss - minflok tnejn kif inti tista 'tistenna mal-bnedmin.

164
00:11:58,620 --> 00:12:03,390
Per eżempju, il-ġenitur tat-3 huwa 7.

165
00:12:03,390 --> 00:12:10,800
Il-ġenitur tad-9 huwa wkoll 7, u l-ġenitur ta '6 huwa 3. Mhux ħafna għaliha.

166
00:12:10,800 --> 00:12:15,720
Għandna wkoll it-termini biex jitkellmu dwar nanniet u neputijiet,

167
00:12:15,720 --> 00:12:18,210
u b'mod aktar ġenerali nitkellmu dwar l-antenati

168
00:12:18,210 --> 00:12:20,960
u d-dixxendenti ta 'node partikolari.

169
00:12:20,960 --> 00:12:25,710
Il-antenat ta 'nodu - jew antenati, pjuttost, ta' nodu -

170
00:12:25,710 --> 00:12:32,730
huma kollha ta 'l-għoqiedi li jinsabu fit-triq mill-għeruq għal dak node.

171
00:12:32,730 --> 00:12:36,640
Per eżempju, jekk jien tħares lejn l-6 node,

172
00:12:36,640 --> 00:12:46,430
allura l-antenati ser ikunu kemm 3 u 7.

173
00:12:46,430 --> 00:12:55,310
L-antenati ta 9, per eżempju, huma - jekk jien tħares lejn l-9 node -

174
00:12:55,310 --> 00:12:59,990
allura l-antenat tad-9 huwa biss 7.

175
00:12:59,990 --> 00:13:01,940
U d-dixxendenti huma eżattament il-maqlub.

176
00:13:01,940 --> 00:13:05,430
Jekk irrid li tħares lejn kollha ta 'l-dixxendenti ta' 7,

177
00:13:05,430 --> 00:13:11,020
imbagħad I għandek tfittex fil-livelli kollha tal-lymph taħt dan.

178
00:13:11,020 --> 00:13:16,950
So, I jkollhom 3, 9, u 6 kollha bħala dixxendenti ta '7.

179
00:13:16,950 --> 00:13:24,170
>> It-terminu finali li aħna ser nitkellmu dwar huwa dan il-kunċett li tkun parentela.

180
00:13:24,170 --> 00:13:27,980
Aħwa - tip ta 'wara flimkien fuq dawn it-termini tal-familja -

181
00:13:27,980 --> 00:13:33,150
huma lymph li huma fl-istess livell fil-siġra.

182
00:13:33,150 --> 00:13:42,230
Allura, 3 u 9 huma aħwa minħabba li huma fl-istess livell fil-siġra.

183
00:13:42,230 --> 00:13:46,190
Huma t-tnejn għandhom l-istess ġenitur, 7.

184
00:13:46,190 --> 00:13:51,400
Il 6 m'għandha l-ebda aħwa għax 9 ma jkollhom l-ebda tfal.

185
00:13:51,400 --> 00:13:55,540
U 7 ma jkollu ebda aħwa, għaliex dan huwa l-għerq ta 'siġra tagħna,

186
00:13:55,540 --> 00:13:59,010
u hemm biss qatt 1 għerq.

187
00:13:59,010 --> 00:14:02,260
Għal 7 li jkollhom aħwa hemm irid ikun node fuq 7.

188
00:14:02,260 --> 00:14:07,480
Ikun hemm għandek tkun ġenitur ta '7, f'liema każ 7 ma jibqax l-għerq tal-siġra.

189
00:14:07,480 --> 00:14:10,480
Imbagħad dak il-ġenitur l-ġdida tas-7 jkollha wkoll li jkollhom tfal,

190
00:14:10,480 --> 00:14:16,480
u dak it-tifel mbagħad tkun l-aħwa ta '7.

191
00:14:16,480 --> 00:14:21,040
>> Alright. Nimxu fuq.

192
00:14:21,040 --> 00:14:24,930
Meta bdejna diskussjoni tagħna ta 'siġar binarju,

193
00:14:24,930 --> 00:14:28,790
tkellimna dwar kif konna se jużawhom biex

194
00:14:28,790 --> 00:14:32,800
jiksbu vantaġġ fuq kemm arrays u listi marbuta.

195
00:14:32,800 --> 00:14:37,220
U l-mod kif aħna qed tmur biex tagħmel dan huwa ma 'din il-proprjetà li tordna.

196
00:14:37,220 --> 00:14:41,080
Aħna ngħidu li siġra binarju ikun ordnat, skond l-ispeċifikazzjoni,

197
00:14:41,080 --> 00:14:45,740
jekk għal kull node fil siġra tagħna, kollha tal-dixxendenti tiegħu fuq ix-xellug -

198
00:14:45,740 --> 00:14:48,670
il-minuri xellug u kollha ta 'dixxendenti tat-tfal tax-xellug tal -

199
00:14:48,670 --> 00:14:54,510
għandhom valuri inqas, u kollha ta 'l-għoqiedi fuq id-dritt -

200
00:14:54,510 --> 00:14:57,770
il-wild dritt u kollha ta 'dixxendenti tat-tfal dritt ta -

201
00:14:57,770 --> 00:15:02,800
jkollhom lymph akbar mill-valur tal-node attwali li aħna qed tfittex fuq.

202
00:15:02,800 --> 00:15:07,850
Just għas-sempliċità, aħna qed tmur biex wieħed jassumi li ma jkunx hemm xi punti ta 'konġunzjoni duplikat fil-siġra tagħna.

203
00:15:07,850 --> 00:15:11,180
Per eżempju, f'dan il-siġra aħna ma tkunx qed tmur biex tittratta l-każ

204
00:15:11,180 --> 00:15:13,680
fejn għandna l-valur 7 fil-għerq

205
00:15:13,680 --> 00:15:16,720
 u allura għandna wkoll il-valur 7 x'imkien ieħor fil-siġra.

206
00:15:16,720 --> 00:15:24,390
F'dan il-każ, inti ser ikollok avviż li din is-siġra huwa tabilħaqq ordnat.

207
00:15:24,390 --> 00:15:26,510
Għandna l-valur 7 fil-għerq.

208
00:15:26,510 --> 00:15:29,720
Kollox fuq ix-xellug ta '7 -

209
00:15:29,720 --> 00:15:35,310
jekk I jneħħu kollha ta 'dawn il-marki ftit hawn -

210
00:15:35,310 --> 00:15:40,450
kollox ix-xellug ta '7 - il-3 u 6 -

211
00:15:40,450 --> 00:15:49,410
dawk il-valuri huma t-tnejn inqas minn 7, u kollox għad-dritt - li huwa biss dan 9 -

212
00:15:49,410 --> 00:15:53,450
huwa aktar minn 7.

213
00:15:53,450 --> 00:15:58,650
>> Din mhix l-siġra biss ordnat li fihom dawn il-valuri,

214
00:15:58,650 --> 00:16:03,120
imma ejja jiġbed aktar ftit minnhom.

215
00:16:03,120 --> 00:16:05,030
Hemm fil-fatt mazz sħiħ ta 'modi li nistgħu nagħmlu dan.

216
00:16:05,030 --> 00:16:09,380
Jien ser tuża shorthand biss li żżomm affarijiet sempliċi meta -

217
00:16:09,380 --> 00:16:11,520
aktar milli jfasslu l-sħiħ kaxxi-u-vleġeġ -

218
00:16:11,520 --> 00:16:14,220
Jien biss ser tiġbed in-numri u żid vleġeġ li jgħaqqduhom.

219
00:16:14,220 --> 00:16:22,920
Biex tibda, aħna ser biss jiktbu siġra oriġinali tagħna għal darb'oħra meta kellna 7, u mbagħad 3,

220
00:16:22,920 --> 00:16:25,590
u mbagħad 3 enfasizzat lura għad-dritt li l-6,

221
00:16:25,590 --> 00:16:30,890
u 7 kellhom tifel dritt li kien 9.

222
00:16:30,890 --> 00:16:33,860
Alright. X'hemm mod ieħor li nistgħu tikteb din is-siġra?

223
00:16:33,860 --> 00:16:38,800
Minflok ma jkollhom 3 jkun l-wild xellug ta '7,

224
00:16:38,800 --> 00:16:41,360
nistgħu wkoll il-6 ikunu l-wild xellug ta '7,

225
00:16:41,360 --> 00:16:44,470
u mbagħad 3 tkun l-wild xellug tal-6.

226
00:16:44,470 --> 00:16:48,520
Dan look like din is-siġra dritt hawn fejn stajt ltqajna 7,

227
00:16:48,520 --> 00:16:57,860
imbagħad 6, imbagħad 3, u 9 fuq il-lemin.

228
00:16:57,860 --> 00:17:01,490
Aħna wkoll ma għandhomx għalfejn ikollhom 7 bħala node għerq tagħna.

229
00:17:01,490 --> 00:17:03,860
Nistgħu wkoll 6 kif node għerq tagħna.

230
00:17:03,860 --> 00:17:06,470
X'għandu li look like?

231
00:17:06,470 --> 00:17:09,230
Jekk aħna qed tmur biex iżommu din il-proprjetà ordnat,

232
00:17:09,230 --> 00:17:12,970
kollox għall-xellug tal-6 għandu jkun inqas minn dan.

233
00:17:12,970 --> 00:17:16,540
Hemm wieħed biss possibbiltà, u li 3.

234
00:17:16,540 --> 00:17:19,869
Iżda mbagħad bħala l-wild dritt ta '6, għandna żewġ possibbiltajiet.

235
00:17:19,869 --> 00:17:25,380
L-ewwel, jista 'jkollna l-7 u allura l-9,

236
00:17:25,380 --> 00:17:28,850
jew nistgħu tiġbed - bħal jien waslu biex jagħmlu hawnhekk -

237
00:17:28,850 --> 00:17:34,790
fejn għandna l-9 bħala l-wild dritt tal-6,

238
00:17:34,790 --> 00:17:39,050
u allura l-7 bħala l-wild xellug tal-9.

239
00:17:39,050 --> 00:17:44,240
>> Issa, 7 u 6 mhumiex l-valuri biss possibbli għall-għerq.

240
00:17:44,240 --> 00:17:50,200
Nistgħu wkoll 3 tkun l-għerq.

241
00:17:50,200 --> 00:17:52,240
X'jiġri jekk 3 hija l-għerq?

242
00:17:52,240 --> 00:17:54,390
Hawnhekk, l-affarijiet jiksbu ftit interessanti.

243
00:17:54,390 --> 00:17:58,440
Tliet ma jkollhom xi valuri li huma inqas minn dan,

244
00:17:58,440 --> 00:18:02,070
sabiex naħa tax-xellug kollu tas-siġra huwa biss se tkun nulla.

245
00:18:02,070 --> 00:18:03,230
Hemm mhux ser ikun xejn hemm.

246
00:18:03,230 --> 00:18:07,220
Għad-dritt, nistgħu lista affarijiet f'ordni axxendenti.

247
00:18:07,220 --> 00:18:15,530
Aħna jista 'jkollhom 3, imbagħad 6, imbagħad 7, imbagħad 9.

248
00:18:15,530 --> 00:18:26,710
Or, nistgħu nagħmlu 3, imbagħad 6, allura 9, allura 7.

249
00:18:26,710 --> 00:18:35,020
Or, nistgħu nagħmlu 3, imbagħad 7, imbagħad 6, imbagħad 9.

250
00:18:35,020 --> 00:18:40,950
Or, 3, 7 - fil-fatt l-ebda, aħna ma tistax tagħmel a 7 aktar.

251
00:18:40,950 --> 00:18:43,330
Dik hija ħaġa waħda tagħna hemmhekk.

252
00:18:43,330 --> 00:18:54,710
Nistgħu nagħmlu 9, u mbagħad mill-9 nistgħu nagħmlu 6 u mbagħad 7.

253
00:18:54,710 --> 00:19:06,980
Or, nistgħu nagħmlu 3, allura 9, allura 7, u mbagħad 6.

254
00:19:06,980 --> 00:19:12,490
>> Ħaġa waħda li tiġbed l-attenzjoni tiegħek għal hawnhekk huwa

255
00:19:12,490 --> 00:19:14,510
li dawn is-siġar huma ftit stramb li tħares.

256
00:19:14,510 --> 00:19:17,840
B'mod partikolari, jekk inħarsu lejn il-siġar 4 fuq il-lemin -

257
00:19:17,840 --> 00:19:20,930
I ser ċirku minnhom, hawn -

258
00:19:20,930 --> 00:19:28,410
dawn is-siġar tfittex kważi eżattament bħall-lista marbuta.

259
00:19:28,410 --> 00:19:32,670
Kull node għandha biss wild wieħed,

260
00:19:32,670 --> 00:19:38,950
u għalhekk aħna ma jkollhomx xi parti minn dan struttura ta 'siġra simili li naraw, per eżempju,

261
00:19:38,950 --> 00:19:44,720
 f'dan siġra 1 isolati hawn fuq fuq il-qiegħ tax-xellug.

262
00:19:44,720 --> 00:19:52,490
Dawn is-siġar huma attwalment imsejħa jiddeġenera siġar binarju,

263
00:19:52,490 --> 00:19:54,170
u aħna ser jitkellmu dwar dawn aktar fil-futur -

264
00:19:54,170 --> 00:19:56,730
speċjalment jekk inti tmur fuq biex jieħdu korsijiet oħra tax-xjenza tal-kompjuter.

265
00:19:56,730 --> 00:19:59,670
Dawn is-siġar huma jiddeġenera.

266
00:19:59,670 --> 00:20:03,780
Huma qed mhux utli ħafna għaliex, fil-fatt, din l-istruttura jippresta ruħu

267
00:20:03,780 --> 00:20:08,060
 biex lookup f'ħinijiet simili għal dik ta 'lista marbuta.

268
00:20:08,060 --> 00:20:13,050
Aħna ma jiksbu biex jieħdu vantaġġ mill-memorja extra - dan pointer extra -

269
00:20:13,050 --> 00:20:18,840
minħabba l-istruttura tagħna jkunu ħżiena b'dan il-mod.

270
00:20:18,840 --> 00:20:24,700
Pjuttost milli jmorru fuq u tfassal l-siġar binarju li jkollhom 9 fil-għerq,

271
00:20:24,700 --> 00:20:27,220
li huwa l-każ finali li rridu naraw,

272
00:20:27,220 --> 00:20:32,380
aħna qed minflok, f'dan il-punt, ser jitkellmu ftit dwar dan it-terminu ieħor

273
00:20:32,380 --> 00:20:36,150
li nużaw meta wieħed jitkellem dwar siġar, li tissejjaħ l-għoli.

274
00:20:36,150 --> 00:20:45,460
>> L-għoli ta 'siġra hija d-distanza mill-għeruq lill-node l-aktar imbiegħda,

275
00:20:45,460 --> 00:20:48,370
jew pjuttost in-numru ta 'ħops li inti jkollha tagħmel sabiex

276
00:20:48,370 --> 00:20:53,750
tibda mill-għeruq u mbagħad jispiċċaw fil-node-aktar imbiegħda fil-siġra.

277
00:20:53,750 --> 00:20:57,330
Jekk nagħtu ħarsa lejn xi wħud minn dawn is-siġar li konna mfassla dritt hawn,

278
00:20:57,330 --> 00:21:07,870
nistgħu naraw li jekk nieħdu din is-siġra fil-rokna tax-xellug ta 'fuq u aħna tibda fil-3,

279
00:21:07,870 --> 00:21:14,510
allura għandna biex jagħmlu 1 hop biex jiksbu l-6, tal-ħops 2 biex jiksbu l-7,

280
00:21:14,510 --> 00:21:20,560
u ħops 3 biex jiksbu l-9.

281
00:21:20,560 --> 00:21:26,120
Għalhekk, l-għoli ta 'din is-siġra huwa 3.

282
00:21:26,120 --> 00:21:30,640
Nistgħu nagħmlu l-istess eżerċizzju, għas-siġar l-oħra msemmija ma 'dan aħdar,

283
00:21:30,640 --> 00:21:40,100
u naraw li l-għoli ta 'kollha ta' dawn is-siġar huwa wkoll tassew 3.

284
00:21:40,100 --> 00:21:45,230
Dan huwa parti minn dak li jagħmel lilhom jiddeġenera -

285
00:21:45,230 --> 00:21:53,750
li tul tagħhom huwa biss wieħed inqas min-numru ta 'nodes fil-siġra kollu.

286
00:21:53,750 --> 00:21:58,400
Jekk inħarsu lejn din is-siġra oħra li l mdawra bl-aħmar, min-naħa l-oħra,

287
00:21:58,400 --> 00:22:03,920
naraw li n-nodi tal-weraq aktar imbiegħda huma l-6 u 9 -

288
00:22:03,920 --> 00:22:06,940
il-weraq huma dawk lymph li m'għandhomx tfal.

289
00:22:06,940 --> 00:22:11,760
Għalhekk, sabiex tikseb mill-node għerq jew lill-6 jew l-9,

290
00:22:11,760 --> 00:22:17,840
aħna għandna biex jagħmlu waħda ħops li jasal sal-7 u mbagħad ħops 2 biex jiksbu l-9,

291
00:22:17,840 --> 00:22:21,240
u l-istess, biss ħops tieni mill-7 biex jiksbu l-6.

292
00:22:21,240 --> 00:22:29,080
Għalhekk, l-għoli ta 'din is-siġra hawn fuq huwa biss 2.

293
00:22:29,080 --> 00:22:35,330
Inti tista 'tmur lura u tagħmel dan għall kollha tal-siġar oħra li aħna diskuss qabel

294
00:22:35,330 --> 00:22:37,380
li jibda bil-7 u l-6,

295
00:22:37,480 --> 00:22:42,500
u inti ser issib li l-għoli ta 'dawn l-siġar huwa wkoll 2.

296
00:22:42,500 --> 00:22:46,320
>> Ir-raġuni aħna kont qed jitkellem dwar ordnati siġar binarju

297
00:22:46,320 --> 00:22:50,250
u għaliex dawn qed jibred minħabba li inti tista 'tfittex permezz tagħhom fl-

298
00:22:50,250 --> 00:22:53,810
b'mod simili ħafna għall-tiftix fuq firxa magħżula.

299
00:22:53,810 --> 00:22:58,720
Dan huwa fejn nitkellmu dwar jkollna dak iż-żmien lookup mtejba

300
00:22:58,720 --> 00:23:02,730
fuq il-lista sempliċi marbuta.

301
00:23:02,730 --> 00:23:05,010
Ma 'lista marbut - jekk inti tixtieq li ssib l-element partikolari -

302
00:23:05,010 --> 00:23:07,470
int fl-aħjar se jagħmlu xi tip ta 'tfittxija lineari

303
00:23:07,470 --> 00:23:10,920
fejn tibda fil-bidu ta 'lista u ħops wieħed mill-wieħed -

304
00:23:10,920 --> 00:23:12,620
1 node minn wieħed node -

305
00:23:12,620 --> 00:23:16,060
permezz tal-lista sħiħa sakemm issib xi tkun qed tfittex.

306
00:23:16,060 --> 00:23:19,440
Billi, jekk għandek siġra binarju li l-maħżuna f'dan il-format sbieħ,

307
00:23:19,440 --> 00:23:23,300
inti tista 'attwalment tikseb aktar ta' tfittxija binarja għaddejjin

308
00:23:23,300 --> 00:23:25,160
fejn inti taqsam u conquer

309
00:23:25,160 --> 00:23:29,490
u tfittxija permezz-nofs xieraq tas-siġra f'kull pass.

310
00:23:29,490 --> 00:23:32,840
Ejja naraw kif din taħdem.

311
00:23:32,840 --> 00:23:38,850
>> Jekk għandna - għal darb'oħra, li tmur lura għall-siġra oriġinali tagħna -

312
00:23:38,850 --> 00:23:46,710
nibdew fi 7, għandna 3 fuq ix-xellug 9 fuq il-lemin,

313
00:23:46,710 --> 00:23:51,740
u taħt l-3 għandna l-6.

314
00:23:51,740 --> 00:24:01,880
Jekk irridu li tfittex għan-numru 6 fil din is-siġra, aħna'd tibda fil-għerq.

315
00:24:01,880 --> 00:24:08,910
Aħna ser jipparaguna l-valur aħna qed tfittex għal, ngħidu 6,

316
00:24:08,910 --> 00:24:12,320
għall-valur maħżuna fil-node li aħna qed attwalment tħares lejn, 7,

317
00:24:12,320 --> 00:24:21,200
issib li 6 huwa tabilħaqq inqas minn 7, hekk aħna d jimxu lejn ix-xellug.

318
00:24:21,200 --> 00:24:25,530
Jekk il-valur tas-6 kien ikbar minn 7, rridu naraw minflok jiċċaqalqu lejn il-lemin.

319
00:24:25,530 --> 00:24:29,770
Peress li nafu li - minħabba l-istruttura tas-siġra tagħna binarju ordnat -

320
00:24:29,770 --> 00:24:33,910
kollha tal-valuri ta 'inqas minn 7 huma ser jiġi maħżun ix-xellug ta' 7,

321
00:24:33,910 --> 00:24:40,520
hemm ebda bżonn li jolqot anki tfittex permezz il-lemin tal-siġra.

322
00:24:40,520 --> 00:24:43,780
Ladarba nimxu lejn ix-xellug u aħna qed issa fil-node fih 3,

323
00:24:43,780 --> 00:24:48,110
nistgħu nagħmlu dan il-paragun istess mill-ġdid fejn aħna jqabblu l-3 u l-6.

324
00:24:48,110 --> 00:24:52,430
U insibu li filwaqt li 6 - il-valur aħna qed tfittex - huwa akbar minn 3,

325
00:24:52,430 --> 00:24:58,580
nistgħu mmorru għall-lemin tal-node fih 3.

326
00:24:58,580 --> 00:25:02,670
M'hemm l-ebda naħa tax-xellug hawn, hekk aħna setgħet injorat dan.

327
00:25:02,670 --> 00:25:06,510
Iżda aħna biss nafu li għaliex aħna qed tħares lejn il-siġra nnifisha,

328
00:25:06,510 --> 00:25:08,660
u nistgħu naraw li s-siġra għandha l-ebda tfal.

329
00:25:08,660 --> 00:25:13,640
>> Huwa wkoll pjuttost faċli li wieħed ifittex 6 fil din is-siġra jekk aħna qed tagħmel dan lilna nfusna bħala bnedmin,

330
00:25:13,640 --> 00:25:16,890
imma ejja ssegwi dan il-proċess mekkaniku bħal kompjuter li ser jagħmlu

331
00:25:16,890 --> 00:25:18,620
biex verament jifhmu l-algoritmu.

332
00:25:18,620 --> 00:25:26,200
Fuq dan il-punt, aħna qed issa tħares lejn node li fih 6,

333
00:25:26,200 --> 00:25:29,180
u aħna qed ifittxu għall-valur 6,

334
00:25:29,180 --> 00:25:31,740
hekk, fil-fatt, aħna ħadthom sabet il-node xierqa.

335
00:25:31,740 --> 00:25:35,070
Sibna l-valur 6 fil siġra tagħna, u aħna tista 'twaqqaf tfittxija tagħna.

336
00:25:35,070 --> 00:25:37,330
Fuq dan il-punt, jiddependi fuq x'inhu għaddej,

337
00:25:37,330 --> 00:25:41,870
nistgħu ngħidu, iva, sibna l-valur 6, teżisti fil-siġra tagħna.

338
00:25:41,870 --> 00:25:47,640
Jew, jekk aħna qed tippjana biex jiddaħħal node jew tagħmel xi ħaġa, nistgħu nagħmlu dan f'dan il-punt.

339
00:25:47,640 --> 00:25:53,010
>> Ejja nagħmlu lookups koppja aktar biss biex tara kif taħdem din.

340
00:25:53,010 --> 00:25:59,390
Ejja nħarsu lejn dak li jiġri jekk konna biex jippruvaw u tfittex l-valur 10.

341
00:25:59,390 --> 00:26:02,970
Jekk konna li wieħed ifittex l-valur 10, aħna se tibda fl-għeruq.

342
00:26:02,970 --> 00:26:07,070
Aħna tixtieq tara li 10 huwa aktar minn 7, hekk aħna d jimxu lejn il-lemin.

343
00:26:07,070 --> 00:26:13,640
Aħna tixtieq tikseb l-9 u jqabblu 9 sa l-10 u tara li 9 huwa tabilħaqq inqas minn 10.

344
00:26:13,640 --> 00:26:16,210
Għalhekk għal darb'oħra, aħna'd jippruvaw jimxu lejn il-lemin.

345
00:26:16,210 --> 00:26:20,350
Iżda f'dan il-punt, aħna'd avviż li aħna qed fuq node null.

346
00:26:20,350 --> 00:26:23,080
M'hemm xejn hemmhekk. M'hemm xejn meta l-10 għandu jkun.

347
00:26:23,080 --> 00:26:29,360
Dan huwa fejn nistgħu rapport falliment - li hemm tabilħaqq nru 10 fil-siġra.

348
00:26:29,360 --> 00:26:35,420
U fl-aħħarnett, ejja jgħaddu mill-każ fejn aħna qed jippruvaw biex wieħed ifittex 1 fil-siġra.

349
00:26:35,420 --> 00:26:38,790
Dan huwa simili għal dak li jiġri jekk aħna tfittex up 10, ħlief minflok tmur lejn il-lemin,

350
00:26:38,790 --> 00:26:41,260
aħna qed tmur biex tmur ix-xellug.

351
00:26:41,260 --> 00:26:46,170
Nibdew fil-7 u tara li 1 huwa inqas minn 7, hekk nimxu lejn ix-xellug.

352
00:26:46,170 --> 00:26:51,750
Nikbru lill-magna 3 u tara li l-1 huwa inqas minn 3, sabiex għal darb'oħra aħna jippruvaw jimxu lejn ix-xellug.

353
00:26:51,750 --> 00:26:59,080
Fuq dan il-punt għandna node null, sabiex għal darb'oħra nistgħu rapport falliment.

354
00:26:59,080 --> 00:27:10,260
>> Jekk inti tixtieq titgħallem aktar dwar siġar binarju,

355
00:27:10,260 --> 00:27:14,420
hemm mazz sħiħ ta 'problemi ftit gost li inti tista' tagħmel magħhom.

356
00:27:14,420 --> 00:27:19,450
Nissuġġerixxi prattikanti it-tfassil minn dawn dijagrammi wieħed mill-wieħed

357
00:27:19,450 --> 00:27:21,910
u wara kollha permezz tal-passi differenti,

358
00:27:21,910 --> 00:27:25,060
għaliex dan se jidħlu fil handy super-

359
00:27:25,060 --> 00:27:27,480
mhux biss meta int tagħmel is-sett Huffman problema kodifikazzjoni

360
00:27:27,480 --> 00:27:29,390
iżda wkoll fil-korsijiet tal-ġejjieni -

361
00:27:29,390 --> 00:27:32,220
biss tagħlim kif tfassal out dawn l-istrutturi tad-data u think permezz tal-problemi

362
00:27:32,220 --> 00:27:38,000
mal-pinna u l-karta jew, f'dan il-każ, iPad u istilus.

363
00:27:38,000 --> 00:27:41,000
>> Fuq dan il-punt għalkemm, aħna qed tmur biex jimxu fuq jagħmlu xi prattika kodifikazzjoni

364
00:27:41,000 --> 00:27:44,870
u fil-fatt jilagħbu ma 'dawn is-siġar binarju u ara.

365
00:27:44,870 --> 00:27:52,150
Jien ser jaqilbu lura fuq il-kompjuter tiegħi.

366
00:27:52,150 --> 00:27:58,480
Għal din il-parti tat-taqsima, minflok li jużaw CS50 Run jew CS50 Spazji,

367
00:27:58,480 --> 00:28:01,500
Jien ser tuża l-appliance.

368
00:28:01,500 --> 00:28:04,950
>> Wara flimkien mal-ispeċifikazzjoni Set Problema,

369
00:28:04,950 --> 00:28:07,740
Nara li jien suppost li jiftħu l-appliance,

370
00:28:07,740 --> 00:28:11,020
mur folder Dropbox tiegħi, toħloq folder imsejjaħ Sezzjoni 7,

371
00:28:11,020 --> 00:28:15,730
u mbagħad toħloq fajl imsejjaħ binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Here we go. Stajt ltqajna l-appliance diġà miftuħa.

373
00:28:22,050 --> 00:28:25,910
Jien ser pull up terminal.

374
00:28:25,910 --> 00:28:38,250
Jien ser tmur fil-folder Dropbox, jagħmel direttorju imsejjaħ section7,

375
00:28:38,250 --> 00:28:42,230
u tara huwa totalment vojta.

376
00:28:42,230 --> 00:28:48,860
Issa jien ser jiftħu binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Alright. Here we go - fajl vojt.

378
00:28:51,750 --> 00:28:54,330
>> Ejja ħa mmorru lura għall-ispeċifikazzjoni.

379
00:28:54,330 --> 00:28:59,850
L-ispeċifikazzjoni jitlob li tinħoloq definizzjoni tip ġdid

380
00:28:59,850 --> 00:29:03,080
għal node siġra binarju jkun fih valuri int -

381
00:29:03,080 --> 00:29:07,110
bħad-valuri li aħna ġibdet fl diagramming tagħna qabel.

382
00:29:07,110 --> 00:29:11,740
Aħna ser jużaw dan boilerplate typedef li aħna ghamilt dritt hawn

383
00:29:11,740 --> 00:29:14,420
li inti għandek jirrikonoxxu mid Set Problema 5 -

384
00:29:14,420 --> 00:29:19,190
jekk inti ma l-mod tabella hash tal conquering-programm speller.

385
00:29:19,190 --> 00:29:22,540
Għandek ukoll jirrikonoxxu mit-taqsima ġimgħa li għaddiet

386
00:29:22,540 --> 00:29:23,890
fejn tkellimna dwar listi marbuta.

387
00:29:23,890 --> 00:29:27,870
Imxejna ltqajna dan typedef ta node Struct,

388
00:29:27,870 --> 00:29:34,430
u konna mogħtija din node Struct dan l-isem tad node Struct minn qabel

389
00:29:34,430 --> 00:29:39,350
sabiex inkunu nistgħu mbagħad tirreferi għaliha peress li aħna inneħħu jridu li jkollhom pointers node Struct

390
00:29:39,350 --> 00:29:45,740
bħala parti mill-Struct tagħna, iżda aħna ve mbagħad mdawwar dan -

391
00:29:45,740 --> 00:29:47,700
jew pjuttost, magħluqa dan - fil-typedef

392
00:29:47,700 --> 00:29:54,600
sabiex, aktar tard fil-kodiċi, nistgħu jirreferu għal din Struct biss bħala node minflok node Struct.

393
00:29:54,600 --> 00:30:03,120
>> Din se tkun simili ħafna għad-definizzjoni lista waħedhom-linked li rajna ġimgħa li għaddiet.

394
00:30:03,120 --> 00:30:20,070
Biex tagħmel dan, ejja biss tibda billi tikteb l-boilerplate.

395
00:30:20,070 --> 00:30:23,840
Aħna nafu li għandna li jkollhom valur sħiħ,

396
00:30:23,840 --> 00:30:32,170
hekk aħna ser jitqiegħdu fil-valur int, u mbagħad minflok li waħda biss pointer għall-element li jmiss -

397
00:30:32,170 --> 00:30:33,970
kif għamilna ma weħidhom marbuta listi -

398
00:30:33,970 --> 00:30:38,110
aħna qed tmur biex ikollhom pointers tfal xellug u lemin.

399
00:30:38,110 --> 00:30:42,880
Li pjuttost sempliċi wisq - Struct node wild * xellug;

400
00:30:42,880 --> 00:30:51,190
u Struct node * wild dritt;. Kessaħ.

401
00:30:51,190 --> 00:30:54,740
Li qisu bidu pjuttost tajba.

402
00:30:54,740 --> 00:30:58,530
Ejja ħa mmorru lura għall-ispeċifikazzjoni.

403
00:30:58,530 --> 00:31:05,030
>> Issa għandna bżonn li tiddikjara varjabbli globali * node għall-għerq ta 'siġra.

404
00:31:05,030 --> 00:31:10,590
Aħna ser tagħmel dan globali bħad għamilna pointer ewwel fil-lista marbuta tagħna wkoll globali.

405
00:31:10,590 --> 00:31:12,690
Dan kien tant li fil-funzjonijiet li aħna jiktbu

406
00:31:12,690 --> 00:31:16,180
aħna ma għandhomx iżommu jgħaddi madwar dan għerq -

407
00:31:16,180 --> 00:31:19,620
għalkemm aħna ser tara li jekk inti trid tikteb dawn il-funzjonijiet recursively,

408
00:31:19,620 --> 00:31:22,830
jista 'jkun aħjar li ma anki jgħaddu madwar bħala globali fl-ewwel post

409
00:31:22,830 --> 00:31:28,090
u minflok initialize din lokalment fil-funzjoni prinċipali tiegħek.

410
00:31:28,090 --> 00:31:31,960
Iżda, aħna ser tagħmel dan globalment biex tibda.

411
00:31:31,960 --> 00:31:39,920
Għal darb'oħra, aħna ser jagħtuk ftit spazji, u jien ser tiddikjara għerq * node.

412
00:31:39,920 --> 00:31:46,770
Just biex tiżgura li jien ma jħallu din uninitialized, jien ser tistabbilixxi li ugwali għal null.

413
00:31:46,770 --> 00:31:52,210
Issa, fil-funzjoni ewlenija - li aħna ser jiktbu verament malajr dritt hawn -

414
00:31:52,210 --> 00:32:00,450
int prinċipali (int argc, const char * ARGV []) -

415
00:32:00,450 --> 00:32:10,640
u jien ser tibda tiddikjara firxa ARGV tiegħi bħala const biss hekk li naf

416
00:32:10,640 --> 00:32:14,550
li dawn l-argumenti huma argumenti li jien probabbilment ma jridux li timmodifika.

417
00:32:14,550 --> 00:32:18,390
Jekk irrid li timmodifika minnhom I għandhom probabbilment tkun qed tagħmel kopji tagħhom.

418
00:32:18,390 --> 00:32:21,740
Int ser ikollok tara dan ħafna fil-kodiċi.

419
00:32:21,740 --> 00:32:25,440
Huwa tal-multa jew mod. Huwa multa li jitilqu minnu bħala - ħalli barra l-const jekk inti tixtieq.

420
00:32:25,440 --> 00:32:28,630
I tipikament poġġih fil biss hekk li I ifakkru lili nnifsi

421
00:32:28,630 --> 00:32:33,650
 li jien probabbilment ma jridux li timmodifika dawn l-argumenti.

422
00:32:33,650 --> 00:32:39,240
>> Bħal dejjem, jien ser tinkludi dan il-prospett 0 linja fl-aħħar tal prinċipali.

423
00:32:39,240 --> 00:32:45,730
Hawnhekk, I se initialize node għerq tiegħi.

424
00:32:45,730 --> 00:32:48,900
Kif inhi dritt issa, stajt ltqajna pointer li l-ssettjat għal null,

425
00:32:48,900 --> 00:32:52,970
hekk huwa tipponta lejn xejn.

426
00:32:52,970 --> 00:32:57,480
Sabiex effettivament jibda jinbena l-node,

427
00:32:57,480 --> 00:32:59,250
I l-ewwel ħtieġa li jiġu allokati memorja għal dan.

428
00:32:59,250 --> 00:33:05,910
Jien ser tagħmel dan billi tagħmel memorja fuq il-munzell użu malloc.

429
00:33:05,910 --> 00:33:10,660
Jien ser jistabbilixxu għerq ugwali għar-riżultat tal malloc,

430
00:33:10,660 --> 00:33:19,550
u jien ser tuża l-operatur sizeof biex tikkalkula l-daqs ta 'node.

431
00:33:19,550 --> 00:33:24,990
Ir-raġuni li nuża node sizeof-kuntrarju, ngħidu aħna,

432
00:33:24,990 --> 00:33:37,020
tagħmel xi ħaġa bħal din - malloc (4 + 4 +4) jew malloc 12 -

433
00:33:37,020 --> 00:33:40,820
huwa għaliex nixtieq kodiċi tiegħi li tkun kompatibbli kemm jista 'jkun.

434
00:33:40,820 --> 00:33:44,540
Irrid li tkun tista 'tieħu dan il-fajl c., Josservawha fuq l-appliance,

435
00:33:44,540 --> 00:33:48,820
u mbagħad josservawha fuq 64-bit Mac tiegħi -

436
00:33:48,820 --> 00:33:52,040
jew fuq arkitettura kompletament differenti -

437
00:33:52,040 --> 00:33:54,640
u nixtieq dan kollu biex jaħdmu l-istess.

438
00:33:54,640 --> 00:33:59,510
>> Jekk jien jagħmlu suppożizzjonijiet dwar id-daqs ta 'varjabbli -

439
00:33:59,510 --> 00:34:02,070
id-daqs ta 'int jew id-daqs ta pointer -

440
00:34:02,070 --> 00:34:06,070
allura jien ukoll jsiru suppożizzjonijiet dwar it-tipi ta arkitetturi

441
00:34:06,070 --> 00:34:10,440
li fuqha kodiċi tiegħi tista b'suċċess jikkompilaw meta jitħaddmu.

442
00:34:10,440 --> 00:34:15,030
Dejjem uża sizeof kif oppost għad manwalment jingħaddu l-oqsma Struct.

443
00:34:15,030 --> 00:34:20,500
Ir-raġuni oħra hija li hemm tista 'wkoll tkun padding li l-kumpilatur tpoġġi fil-Struct.

444
00:34:20,500 --> 00:34:26,570
Anke biss jingħaddu l-oqsma individwali mhux xi ħaġa li inti tipikament trid tagħmel,

445
00:34:26,570 --> 00:34:30,340
hekk, iħassru dik il-linja.

446
00:34:30,340 --> 00:34:33,090
Issa, biex verament initialize din node għerq,

447
00:34:33,090 --> 00:34:36,489
Jien ser ikollhom biex plagg fil-valuri għal kull ta 'oqsma differenti tagħha.

448
00:34:36,489 --> 00:34:41,400
Per eżempju, għal valur naf nixtieq li initialize sa 7,

449
00:34:41,400 --> 00:34:46,920
u għal issa jien ser jistabbilixxu l-minuri xellug jkun null

450
00:34:46,920 --> 00:34:55,820
u l-wild dritt li wkoll tkun nulla. Great!

451
00:34:55,820 --> 00:35:02,670
Aħna ghamilt dik il-parti ta 'l-spec.

452
00:35:02,670 --> 00:35:07,390
>> L-ispeċifikazzjoni stabbiliti fil-qiegħ tal-paġna 3 tistaqsi lili biex joħolqu tliet aktar glandoli -

453
00:35:07,390 --> 00:35:10,600
wieħed li jkun fih 3, wieħed li jkun fih 6, u wieħed ma 9 -

454
00:35:10,600 --> 00:35:14,210
u mbagħad wajer flimkien sabiex jidher eżattament bħall dijagramma siġra tagħna

455
00:35:14,210 --> 00:35:17,120
li konna nitkellmu qabel.

456
00:35:17,120 --> 00:35:20,450
Ejja nagħmlu dan pretty malajr hawn.

457
00:35:20,450 --> 00:35:26,270
Int ser ikollok tara verament malajr li jien ser tibda bil-miktub mazz ta 'kodiċi duplikat.

458
00:35:26,270 --> 00:35:32,100
Jien ser toħloq * node u jien ser sejħa hija tlieta.

459
00:35:32,100 --> 00:35:36,000
Jien ser tistabbilixxi li ugwali għal malloc (sizeof (node)).

460
00:35:36,000 --> 00:35:41,070
Jien ser jistabbilixxu tliet> valur = 3.

461
00:35:41,070 --> 00:35:54,780
Tliet -> left_child = NULL; 3 -> lemin _child = NULL; kif ukoll.

462
00:35:54,780 --> 00:36:01,150
Li jistenna pjuttost simili għall initializing-għerq, u dan huwa eżattament dak

463
00:36:01,150 --> 00:36:05,760
Jien ser ikollhom jagħmlu jekk nibda initializing 6 u 9 kif ukoll.

464
00:36:05,760 --> 00:36:20,720
I ser tagħmel li verament malajr hawnhekk - fil-fatt, jien ser tagħmel kopja u paste ftit,

465
00:36:20,720 --> 00:36:46,140
u kun żgur li I - alright.

466
00:36:46,470 --> 00:37:09,900
 Issa, stajt ltqajna dan kkupjati u I tista 'tmur quddiem u jistabbilixxu dan ugwali għal 6.

467
00:37:09,900 --> 00:37:14,670
Tista 'tara li dan jieħu awhile u mhux super-effiċjenti.

468
00:37:14,670 --> 00:37:22,610
Fi ftit ftit, aħna ser jiktbu funzjoni li se jagħmel dan għalina.

469
00:37:22,610 --> 00:37:32,890
Irrid li tissostitwixxi dan ma '9, jissostitwih bid a 6.

470
00:37:32,890 --> 00:37:37,360
>> Issa konna ltqajna kollha ta 'punti ta' konġunzjoni tagħna maħluqa u initialized.

471
00:37:37,360 --> 00:37:41,200
Imxejna ltqajna għeruq tagħna stabbilit ugwali għal 7, jew li jkun fihom il-valur 7,

472
00:37:41,200 --> 00:37:46,510
node tagħna fihom 3, node tagħna fiha 6, u node tagħna fihom 9.

473
00:37:46,510 --> 00:37:50,390
Fuq dan il-punt, kollha għandna nagħmlu huwa kollox wajer up.

474
00:37:50,390 --> 00:37:53,020
Ir-raġuni I initialized l-pointers għal null huwa biss hekk li jien tagħmel ċert li

475
00:37:53,020 --> 00:37:56,260
Jien m'għandi l-ebda indikazzjonijiet uninitialized fil hemm mill-inċident.

476
00:37:56,260 --> 00:38:02,290
U wkoll peress li, f'dan il-punt, I biss għandek attwalment jgħaqqdu l-lymph lil xulxin -

477
00:38:02,290 --> 00:38:04,750
għal dawk li dawn qed attwalment konnessi mal - I ma jkollhom jgħaddu u tagħmel

478
00:38:04,750 --> 00:38:08,240
ċert li l-nulls huma hemmhekk fil-postijiet adattati.

479
00:38:08,240 --> 00:38:15,630
>> Tibda fl-għerq, naf dak it-tifel xellug l-għerq huwa 3.

480
00:38:15,630 --> 00:38:21,250
Naf dak it-tifel dritt l-għerq huwa 9.

481
00:38:21,250 --> 00:38:24,880
Wara dan, it-tfal biss l-oħra li I ħallew għalfejn tinkwieta dwar

482
00:38:24,880 --> 00:38:39,080
huwa tifel dritt 3, li hija 6.

483
00:38:39,080 --> 00:38:44,670
Wara dan, dan kollu jidher pjuttost tajba.

484
00:38:44,670 --> 00:38:54,210
Aħna ser tħassar xi wħud minn dawn il-linji.

485
00:38:54,210 --> 00:38:59,540
Issa kollox jistenna pretty tajba.

486
00:38:59,540 --> 00:39:04,240
Ejja ħa mmorru lura għall-ispeċifikazzjoni tagħna u ara dak li għandna biex jagħmlu li jmiss.

487
00:39:04,240 --> 00:39:07,610
>> Fuq dan il-punt, għandna biex jiktbu funzjoni msejħa "fih"

488
00:39:07,610 --> 00:39:14,150
ma 'prototip ta' ma fiha bool (int valur).

489
00:39:14,150 --> 00:39:17,060
U dan jinkludi funzjoni se ritorn vera

490
00:39:17,060 --> 00:39:21,200
 jekk l-siġra indikat mill-varjabbli tagħna għeruq globali

491
00:39:21,200 --> 00:39:26,950
 fiha l-valur għadda fil-funzjoni u falza mod ieħor.

492
00:39:26,950 --> 00:39:29,000
Ejja imorru quddiem u tagħmel dan.

493
00:39:29,000 --> 00:39:35,380
Din se tkun eżattament bħall-lookup li għamilna bl-idejn fuq il-iPad biss ftit ilu.

494
00:39:35,380 --> 00:39:40,130
Ejja zoom lura ftit u iscroll.

495
00:39:40,130 --> 00:39:43,130
Aħna ser tpoġġi din il-funzjoni dritt fuq il-funzjoni prinċipali tagħna

496
00:39:43,130 --> 00:39:48,990
hekk li aħna ma jkollhom jagħmlu xi tip ta 'prototipi.

497
00:39:48,990 --> 00:39:55,960
Allura, bool fih (int valur).

498
00:39:55,960 --> 00:40:00,330
Hemm immorru. Hemm dikjarazzjoni boilerplate tagħna.

499
00:40:00,330 --> 00:40:02,900
Just biex tiżgura li dan se tikkompila,

500
00:40:02,900 --> 00:40:06,820
Jien ser jimxi 'l quddiem u biss sett huwa ugwali għal ritorn foloz.

501
00:40:06,820 --> 00:40:09,980
Dritt issa din il-funzjoni biss mhux se tagħmel xejn u dejjem jirrappurtaw li

502
00:40:09,980 --> 00:40:14,010
il-valur li aħna qed tfittex ma tkunx fil-siġra.

503
00:40:14,010 --> 00:40:16,280
>> Wara dan, huwa probabbilment idea tajba -

504
00:40:16,280 --> 00:40:19,600
peress li aħna ħadthom miktub mazz sħiħ ta 'kodiċi u aħna lanqas biss ppruvaw ittestjar encore -

505
00:40:19,600 --> 00:40:22,590
biex ikun żgurat li dan kollu jikkompila.

506
00:40:22,590 --> 00:40:27,460
Hemm ftit affarijiet li rridu nagħmlu biex tiżgura li dan fil-fatt jiġbor.

507
00:40:27,460 --> 00:40:33,530
L-ewwel, ara jekk aħna kont qed tuża xi funzjonijiet xi libreriji li għadna ma inklużi.

508
00:40:33,530 --> 00:40:37,940
Il-funzjonijiet konna użati s'issa huma malloc,

509
00:40:37,940 --> 00:40:43,310
u allura konna wkoll qegħdin jużaw dan it-tip - dan it-tip nonstandard imsejjaħ "bool' -

510
00:40:43,310 --> 00:40:45,750
li hija inkluża fil-fajl tal-header standard bool.

511
00:40:45,750 --> 00:40:53,250
We definitely tixtieq li jinkludu bool.h standard għat-tip bool,

512
00:40:53,250 --> 00:40:59,230
u aħna wkoll jixtiequ # Jinkludu lib.h standard għall-libreriji standard

513
00:40:59,230 --> 00:41:03,530
li jinkludu malloc, u ħielsa, u kollha ta 'dak.

514
00:41:03,530 --> 00:41:08,660
Allura, zoom out, aħna qed tmur biex nieqaf.

515
00:41:08,660 --> 00:41:14,190
Ejja jippruvaw jagħmlu ċert li dan fil-fatt ma jikkompilaw.

516
00:41:14,190 --> 00:41:18,150
Naraw li dan huwa minnu, hekk aħna qed fuq il-binarju dritt.

517
00:41:18,150 --> 00:41:22,990
>> Ejja jiftħu binary_tree.c mill-ġdid.

518
00:41:22,990 --> 00:41:34,530
Hija jikkompila. Ejja jinżlu u kun żgur li aħna daħħal xi sejħiet għal ma fiha l-funzjoni tagħna -

519
00:41:34,530 --> 00:41:40,130
biss tagħmel ċert li dan huwa kollu tajjeb u tajba.

520
00:41:40,130 --> 00:41:43,170
Per eżempju, meta għamilna xi lookups fil siġra tagħna qabel,

521
00:41:43,170 --> 00:41:48,500
aħna ppruvaw li tfittex l-valuri 6, 10, u 1, u aħna kien jaf li kienet 6 fil-siġra,

522
00:41:48,500 --> 00:41:52,220
10 ma kienx fil-siġra, u 1 kienx fil-siġra jew.

523
00:41:52,220 --> 00:41:57,230
Ejja tuża dawk is-sejħiet tal-kampjuni bħala mod biex insemmu jekk jew le

524
00:41:57,230 --> 00:41:59,880
ma fiha l-funzjoni tagħna qed taħdem.

525
00:41:59,880 --> 00:42:05,210
Sabiex tagħmel dan, jien ser tuża l-funzjoni printf,

526
00:42:05,210 --> 00:42:10,280
u aħna qed tmur biex jistampa r-riżultat tas-sejħa għall fih.

527
00:42:10,280 --> 00:42:13,280
Jien ser jitqiegħdu fil string "fih (% d) = għax

528
00:42:13,280 --> 00:42:20,470
 aħna qed tmur biex plagg fil-valur li aħna qed tmur biex tfittex,

529
00:42:20,470 --> 00:42:27,130
u =% s \ n "u l-użu li bħala string format tagħna.

530
00:42:27,130 --> 00:42:30,720
Aħna biss se tara - litteralment jistampa fuq l-iskrin -

531
00:42:30,720 --> 00:42:32,060
dak qisu sejħa funzjoni.

532
00:42:32,060 --> 00:42:33,580
Dan mhuwiex attwalment l-sejħa funzjoni.

533
00:42:33,580 --> 00:42:36,760
 Dan huwa biss sekwenza mfassla biex dehra ta 'sejħa funzjoni.

534
00:42:36,760 --> 00:42:41,140
>> Issa, aħna qed tmur biex plagg fil-valuri.

535
00:42:41,140 --> 00:42:43,580
Aħna ser tipprova fih fis-6,

536
00:42:43,580 --> 00:42:48,340
u allura dak li aħna qed tmur biex tagħmel hawnhekk huwa użu li operatur tenarji.

537
00:42:48,340 --> 00:42:56,340
Ejja naraw - fih 6 - hekk, issa stajt jinsabu 6 u jekk fih 6 huwa veru,

538
00:42:56,340 --> 00:43:01,850
l-sekwenza li aħna qed tmur biex jibagħtu lill-karattru format tal-% s

539
00:43:01,850 --> 00:43:04,850
se tkun l-sekwenza "vera".

540
00:43:04,850 --> 00:43:07,690
Ejja iscroll fuq ftit.

541
00:43:07,690 --> 00:43:16,210
Inkella, irridu li jibgħat l-sekwenza "false" jekk fih 6 dikjarazzjonijiet foloz.

542
00:43:16,210 --> 00:43:19,730
Dan huwa ftit goofy li tħares, iżda I figura I jistgħu wkoll juru

543
00:43:19,730 --> 00:43:23,780
dak l-operatur ternarji qisu peress li aħna ma bbenefikawx għall awhile.

544
00:43:23,780 --> 00:43:27,670
Dan se jkun sbieħ, mod handy biex insemmu jekk ma fiha l-funzjoni tagħna qed taħdem.

545
00:43:27,670 --> 00:43:30,040
Jien ser iscroll lura fuq ix-xellug,

546
00:43:30,040 --> 00:43:39,900
u jien ser kopja u paste din il-linja għal xi ftit drabi.

547
00:43:39,900 --> 00:43:44,910
Huwa biddel xi wħud minn dawn il-valuri madwar,

548
00:43:44,910 --> 00:43:59,380
għalhekk dan se jkun 1, u dan se jkun ta '10.

549
00:43:59,380 --> 00:44:02,480
>> Fuq dan il-punt konna ltqajna funzjoni ma fiha sbieħ.

550
00:44:02,480 --> 00:44:06,080
Imxejna ltqajna xi testijiet, u aħna ser tara jekk dan xogħlijiet kollha.

551
00:44:06,080 --> 00:44:08,120
Fuq dan il-punt konna bil-miktub kodiċi ftit aktar.

552
00:44:08,120 --> 00:44:13,160
Ħin li nieqaf out u kun żgur li kollox għadu jikkompila.

553
00:44:13,160 --> 00:44:20,360
Nieqaf out, u issa ejja tipprova tagħmel siġra binarju mill-ġdid.

554
00:44:20,360 --> 00:44:22,260
Ukoll, jidher qisu konna ltqajna żball,

555
00:44:22,260 --> 00:44:26,930
u konna ltqajna dan b'mod espliċitu li tiddikjara l-funzjoni librerija printf.

556
00:44:26,930 --> 00:44:39,350
Jidher qisu għandna bżonn li jmorru fi u # Jinkludu standardio.h.

557
00:44:39,350 --> 00:44:45,350
U ma 'dan, kollox għandu jiġbor. Aħna kollha tajbin.

558
00:44:45,350 --> 00:44:50,420
Issa ejja tipprova taħdem siġar binarju u ara dak li jiġri.

559
00:44:50,420 --> 00:44:53,520
Hawnhekk aħna,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
u naraw li, kif aħna mistennija -

561
00:44:55,190 --> 00:44:56,910
għaliex aħna ma implimentawx fih għadhom,

562
00:44:56,910 --> 00:44:59,800
jew pjuttost, konna biss jitqiegħed fl-ritorn foloz -

563
00:44:59,800 --> 00:45:03,300
naraw li huwa biss jirritorna falza għalihom kollha,

564
00:45:03,300 --> 00:45:06,180
hekk li kollox jaħdem għall-parti l-kbira pjuttost tajjeb.

565
00:45:06,180 --> 00:45:11,860
>> Ejja ħa mmorru lura u fil-fatt jimplimentaw fih f'dan il-punt.

566
00:45:11,860 --> 00:45:17,490
Jien ser iscroll, zoom fi, u -

567
00:45:17,490 --> 00:45:22,330
ftakar, l-algoritmu li aħna użati kienet li bdejna fil-node għerq

568
00:45:22,330 --> 00:45:28,010
u mbagħad kull node li aħna jiltaqgħu, nagħmlu paragun,

569
00:45:28,010 --> 00:45:32,380
u bbażat fuq il-paragun aħna jew jimxu lejn il-wild xellug jew lill-wild dritt.

570
00:45:32,380 --> 00:45:39,670
Dan ser tfittex simili ħafna għall-kodiċi tfittxija binarju li aħna kiteb aktar kmieni fi żmien.

571
00:45:39,670 --> 00:45:47,810
Meta nibdew off, nafu li aħna rridu li jżommu lill-node kurrenti

572
00:45:47,810 --> 00:45:54,050
li aħna qed tħares lejn, u l-node attwali se tkun initialized għall-node għerq.

573
00:45:54,050 --> 00:45:56,260
U issa, aħna qed tmur biex iżommu għaddejjin mill-siġra,

574
00:45:56,260 --> 00:45:58,140
u ftakar li kundizzjoni waqfien tagħna -

575
00:45:58,140 --> 00:46:01,870
 meta aħna effettivament maħduma permezz tal-eżempju bl-idejn -

576
00:46:01,870 --> 00:46:03,960
kien meta aħna jiltaqgħu node null,

577
00:46:03,960 --> 00:46:05,480
mhux meta ħarisna lejn tifel null,

578
00:46:05,480 --> 00:46:09,620
iżda pjuttost meta aħna fil-fatt mċaqilqa għal node fil-siġra

579
00:46:09,620 --> 00:46:12,640
u sabet li aħna qed fuq node null.

580
00:46:12,640 --> 00:46:20,720
Aħna ser jtenni sakemm kur mhuwiex ugwali għal null.

581
00:46:20,720 --> 00:46:22,920
U dak li aħna se jagħmlu?

582
00:46:22,920 --> 00:46:31,610
Aħna ser tittestja jekk (kur -> == valur valur),

583
00:46:31,610 --> 00:46:35,160
allura nafu li aħna ħadthom attwalment sabet l-node li aħna qed tfittex.

584
00:46:35,160 --> 00:46:40,450
Allura hawn, nistgħu ritorn vera.

585
00:46:40,450 --> 00:46:49,830
Inkella, irridu naraw jekk il-valur huwa inqas mill-valur.

586
00:46:49,830 --> 00:46:53,850
Jekk il-valur tal-node attwali hija inqas mill-valur aħna qed tfittex,

587
00:46:53,850 --> 00:46:57,280
aħna qed tmur biex jimxu lejn il-lemin.

588
00:46:57,280 --> 00:47:10,600
Allura, kur = kur -> right_child, u inkella, aħna qed tmur biex jimxu lejn ix-xellug.

589
00:47:10,600 --> 00:47:17,480
= kur kur -> left_child;. Pretty sempliċi.

590
00:47:17,480 --> 00:47:22,830
>> You probabbilment jirrikonoxxu l-linja li tidher simili ħafna għal dan mill-

591
00:47:22,830 --> 00:47:27,580
tfittxija binarja aktar kmieni fit-terminu, ħlief allura konna jittrattaw baxx, medju, u għoli.

592
00:47:27,580 --> 00:47:30,000
Hawnhekk, aħna biss għandek tfittex fil-valur kurrenti,

593
00:47:30,000 --> 00:47:31,930
dan huwa sbieħ u sempliċi.

594
00:47:31,930 --> 00:47:34,960
Ejja kun żgur din il-kodiċi qed taħdem.

595
00:47:34,960 --> 00:47:42,780
L-ewwel, kun żgur li tiġbor. Qisu ma.

596
00:47:42,780 --> 00:47:47,920
Ejja nippruvaw ġestjoni tiegħu.

597
00:47:47,920 --> 00:47:50,160
U fil-fatt, hija prints dak kollu li aħna mistennija.

598
00:47:50,160 --> 00:47:54,320
Hija tikkonstata 6 fil-siġra, ma ssib 10 minħabba 10 mhuwiex fil-siġra,

599
00:47:54,320 --> 00:47:57,740
u ma jsibu 1 jew għaliex 1 wkoll mhux fil-siġra.

600
00:47:57,740 --> 00:48:01,420
Kessaħ Jittieħed.

601
00:48:01,420 --> 00:48:04,470
>> Alright. Ejja ħa mmorru lura għall-ispeċifikazzjoni tagħna u ara dak li jmiss.

602
00:48:04,470 --> 00:48:07,990
Issa, huwa jrid iżid punti ta 'konġunzjoni xi aktar biex siġra tagħna.

603
00:48:07,990 --> 00:48:11,690
Hija trid li żżid 5, 2, u 8, u kun żgur li tagħna fiha Kodiċi

604
00:48:11,690 --> 00:48:13,570
għadu jaħdem kif mistenni.

605
00:48:13,570 --> 00:48:14,900
Ejja jmorru jagħmlu dan.

606
00:48:14,900 --> 00:48:19,430
Fuq dan il-punt, aktar milli tagħmel dik il-kopja annoying u paste mill-ġdid,

607
00:48:19,430 --> 00:48:23,770
ejja tikteb funzjoni li attwalment joħolqu node.

608
00:48:23,770 --> 00:48:27,740
Jekk aħna iscroll-triq kollha lejn prinċipali, naraw li aħna kont qed tagħmel dan

609
00:48:27,740 --> 00:48:31,210
Kodiċi simili ħafna fuq u aktar mill-ġdid kull darba li aħna nixtiequ noħolqu node.

610
00:48:31,210 --> 00:48:39,540
>> Ejja jiktbu funzjoni li fil-fatt se tibni node għalina u jirritornaha.

611
00:48:39,540 --> 00:48:41,960
Jien ser sejħa hija build_node.

612
00:48:41,960 --> 00:48:45,130
Jien ser tibni node b'valur partikolari.

613
00:48:45,130 --> 00:48:51,040
Zoom fil hawn.

614
00:48:51,040 --> 00:48:56,600
L-ewwel ħaġa li jien ser tagħmel hu li attwalment joħolqu spazju għall-node fuq il-borġ.

615
00:48:56,600 --> 00:49:05,400
Allura, node * n = malloc (sizeof (node)); -; n> valur valur =

616
00:49:05,400 --> 00:49:14,960
u allura hawnhekk, jien biss ser initialize kollha ta 'l-oqsma li jkun valuri xierqa.

617
00:49:14,960 --> 00:49:22,500
U fl-aħħar nett, aħna ser terġa 'lura node tagħna.

618
00:49:22,500 --> 00:49:28,690
Alright. Ħaġa waħda li wieħed jinnota li din il-funzjoni dritt hawn

619
00:49:28,690 --> 00:49:34,320
se jirritorna pointer għall-memorja li ġie borġ-allokazzjoni.

620
00:49:34,320 --> 00:49:38,880
X'hemm sbieħ dwar dan hija li dan node issa -

621
00:49:38,880 --> 00:49:42,420
għandna li tiddikjaraha fuq il-borġ għaliex jekk aħna iddikjarat fuq il-munzell

622
00:49:42,420 --> 00:49:45,050
aħna ma jkunux jistgħu jagħmlu dan f'din il-funzjoni bħal din.

623
00:49:45,050 --> 00:49:47,690
Li memorja se jmorru barra ta 'ambitu

624
00:49:47,690 --> 00:49:51,590
u jkun invalidu jekk aħna ppruvaw li jkollhom aċċess għaliha aktar tard.

625
00:49:51,590 --> 00:49:53,500
Peress li aħna tiddikjara borġ-allokazzjoni tal-memorja,

626
00:49:53,500 --> 00:49:55,830
aħna ser ikollok tieħu kura ta 'ħelsien iktar tard

627
00:49:55,830 --> 00:49:58,530
għall-programm tagħna biex ma jnixxi ebda memorja.

628
00:49:58,530 --> 00:50:01,270
Imxejna ġiet punting fuq li għal kull ħaġa oħra fil-kodiċi

629
00:50:01,270 --> 00:50:02,880
biss għall-finijiet sempliċità fil-ħin,

630
00:50:02,880 --> 00:50:05,610
imma jekk inti qatt tikteb funzjoni li tidher bħal dan

631
00:50:05,610 --> 00:50:10,370
fejn inti ħadthom ltqajna - xi sejħa hija ta 'malloc jew realloc ġewwa -

632
00:50:10,370 --> 00:50:14,330
inti tixtieq li tagħmel ċert li inti tpoġġi xi tip ta 'kumment up hawn li tgħid,

633
00:50:14,330 --> 00:50:29,970
ħej, inti taf, jirritorna node borġ 'allokat initialized mal-valur għadda-in.

634
00:50:29,970 --> 00:50:33,600
U allura inti tixtieq li tagħmel ċert li inti tpoġġi fil xi tip ta 'nota li tgħid

635
00:50:33,600 --> 00:50:41,720
l-sejjieħ għandha tilliberalizza l-memorja lura.

636
00:50:41,720 --> 00:50:45,450
B'dan il-mod, jekk xi ħadd qatt tmur u l-użi li l-funzjoni,

637
00:50:45,450 --> 00:50:48,150
huma jafu li dak kollu li jiksbu lura minn dik il-funzjoni

638
00:50:48,150 --> 00:50:50,870
f'xi punt se jeħtieġu li jiġu liberati.

639
00:50:50,870 --> 00:50:53,940
>> Jekk wieħed jassumi li kollox huwa tajjeb u tajba hawn,

640
00:50:53,940 --> 00:51:02,300
nistgħu mmorru l isfel fil-kodiċi tagħna u jissostitwixxi kollha ta 'dawn il-linji dritt hawn

641
00:51:02,300 --> 00:51:05,410
ma 'sejħiet għal funzjoni tagħna node jibnu.

642
00:51:05,410 --> 00:51:08,170
Ejja nagħmlu dan verament malajr.

643
00:51:08,170 --> 00:51:15,840
Il-parti l-waħda li aħna ma tkunx qed tmur biex jissostitwixxu hija din il-parti stabbiliti hawn

644
00:51:15,840 --> 00:51:18,520
fil-qiegħ fejn aħna attwalment wajer ta 'l-għoqiedi għall-punt ta' xulxin,

645
00:51:18,520 --> 00:51:21,030
minħabba li aħna ma tistax tagħmel fil-funzjoni tagħna.

646
00:51:21,030 --> 00:51:37,400
Imma, ejja nagħmlu għerq = build_node (7); node * 3 = build_node (3);

647
00:51:37,400 --> 00:51:47,980
node * 6 = build_node (6); node * 9 = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
U issa, aħna wkoll ried iżid lymph għall -

649
00:51:52,590 --> 00:52:03,530
node * 5 = build_node (5); node * 8 = build_node (8);

650
00:52:03,530 --> 00:52:09,760
u dak li kien l-node oħra? Ejja naraw hawnhekk. Ridna wkoll żżid 2 -

651
00:52:09,760 --> 00:52:20,280
node * 2 = build_node (2);.

652
00:52:20,280 --> 00:52:26,850
Alright. Fuq dan il-punt, aħna nafu li konna ltqajna l-7, it-3, il-9, u l-6

653
00:52:26,850 --> 00:52:30,320
kollha fili up xieraq, iżda xi ngħidu dwar il-5, l-8, u l-2?

654
00:52:30,320 --> 00:52:33,550
Biex iżommu kollox fl-ordni xierqa,

655
00:52:33,550 --> 00:52:39,230
aħna nafu li tifel dritt 3 huwa 6.

656
00:52:39,230 --> 00:52:40,890
Għalhekk, jekk aħna qed tmur biex iżżid il-5,

657
00:52:40,890 --> 00:52:46,670
il-5 jappartjeni wkoll fil-lemin tal-siġra li minnhom 3 hija l-għerq,

658
00:52:46,670 --> 00:52:50,440
hekk 5 jappartjeni bħala l-wild xellug ta '6.

659
00:52:50,440 --> 00:52:58,650
Nistgħu nagħmlu dan billi qal, 6 -> left_child = 5;

660
00:52:58,650 --> 00:53:10,790
u mbagħad l-8 jappartjeni bħala l-wild xellug tal 9, hekk 9 -> left_child = 8;

661
00:53:10,790 --> 00:53:22,190
u mbagħad 2 huwa l-wild xellug ta '3, sabiex inkunu nistgħu nagħmlu dan up hawn - thee -> left_child = 2;.

662
00:53:22,190 --> 00:53:27,730
Jekk inti ma pjuttost isegwu flimkien ma 'dan, nissuġġerixxi inti tiġbed it out yourself.

663
00:53:27,730 --> 00:53:35,660
>> Alright. Ejja jiffranka dan. Ejja tmur u kun żgur li jikkompila,

664
00:53:35,660 --> 00:53:40,760
u allura nistgħu żid fis-sejħiet fih tagħna.

665
00:53:40,760 --> 00:53:44,120
Id-Dehra kollox xorta jikkompila.

666
00:53:44,120 --> 00:53:51,790
Ejja jmorru fi u żid f'xi fih sejħiet.

667
00:53:51,790 --> 00:53:59,640
Għal darb'oħra, jien ser tagħmel ftit ta 'kopja u paste.

668
00:53:59,640 --> 00:54:15,860
Issa ejja tfittex 5, 8, u 2. Alright.

669
00:54:15,860 --> 00:54:28,330
Ejja kun żgur li dan kollu jidher tajjeb xorta. Great! Ħlief u nieqaf.

670
00:54:28,330 --> 00:54:33,220
Issa ejja jagħmlu, tiġbor, u issa ejja jimxu.

671
00:54:33,220 --> 00:54:37,540
Mir-riżultati, jidher qisu kollox qed taħdem biss sbieħ u tajjeb.

672
00:54:37,540 --> 00:54:41,780
Great! Allura issa konna ltqajna ma fiha tagħna jiffunzjonaw bil-miktub.

673
00:54:41,780 --> 00:54:46,160
Ejja jimxu fuq u jibdew jaħdmu fuq kif daħħal lymph fis-siġra

674
00:54:46,160 --> 00:54:50,000
peress li, kif aħna qed tagħmel dan id-dritt issa, l-affarijiet mhumiex ħafna pretty.

675
00:54:50,000 --> 00:54:52,280
>> Jekk immorru lura għall-ispeċifikazzjoni,

676
00:54:52,280 --> 00:55:00,540
hija tistaqsi magħna biex jiktbu funzjoni msejħa daħħal - għal darb'oħra, jirritornaw bool

677
00:55:00,540 --> 00:55:04,400
għal jekk nistgħu attwalment daħħal il-node fil-siġra -

678
00:55:04,400 --> 00:55:07,710
u allura l-valur li ddaħħal fil-siġra hija speċifikata bħala

679
00:55:07,710 --> 00:55:11,060
l-argument biss għall-funzjoni daħħal tagħna.

680
00:55:11,060 --> 00:55:18,180
Aħna se terġa 'lura minnu jekk nistgħu tabilħaqq daħħal il-valur node fih fil-siġra,

681
00:55:18,180 --> 00:55:20,930
li jfisser li aħna, wieħed, kellha memorja biżżejjed,

682
00:55:20,930 --> 00:55:24,840
u mbagħad tnejn, li node ma jkunux diġà jeżistu fl-siġra mill -

683
00:55:24,840 --> 00:55:32,170
ftakar, aħna mhux se jkollhom valuri duplikat fil-siġra, biss biex jagħmlu l-affarijiet sempliċi.

684
00:55:32,170 --> 00:55:35,590
Alright. Back għall-kodiċi.

685
00:55:35,590 --> 00:55:44,240
Jiftħuh. Zoom fi ftit, imbagħad iscroll.

686
00:55:44,240 --> 00:55:47,220
Ejja tpoġġi l-funzjoni daħħal dritt fuq il-ma fiha.

687
00:55:47,220 --> 00:55:56,360
Għal darb'oħra, li għaddej biex jiġu msejħa daħħal bool (int valur).

688
00:55:56,360 --> 00:56:01,840
Agħti spazju ftit aktar, u mbagħad, bħala default,

689
00:56:01,840 --> 00:56:08,870
ejja tpoġġi lura falz fl-aħħar nett.

690
00:56:08,870 --> 00:56:22,620
Issa l isfel fil-qiegħ, ejja imorru quddiem u minflok manwalment bini tal-lymph

691
00:56:22,620 --> 00:56:27,900
fl prinċipali nfusna u wajers minnhom sa punt lil xulxin simili aħna qed tagħmel,

692
00:56:27,900 --> 00:56:30,600
aħna ser jiddependu fuq il-funzjoni daħħal tagħna biex tagħmel dan.

693
00:56:30,600 --> 00:56:35,510
Aħna mhux se tistrieħ fuq il-funzjoni daħħal tagħna biex tinbena l-siġra kollu mill-bidu għadha biss,

694
00:56:35,510 --> 00:56:39,970
iżda aħna ser teħles minn dawn il-linji - we'll jikkummentaw out dawn il-linji -

695
00:56:39,970 --> 00:56:43,430
li jibnu l-lymph 5, 8, u 2.

696
00:56:43,430 --> 00:56:55,740
U minflok, aħna ser daħħal sejħiet għall-funzjoni daħħal tagħna

697
00:56:55,740 --> 00:57:01,280
biex tiżgura li li attwalment xogħlijiet.

698
00:57:01,280 --> 00:57:05,840
Here we go.

699
00:57:05,840 --> 00:57:09,300
>> Issa konna ikkummenta out dawn il-linji.

700
00:57:09,300 --> 00:57:13,700
Aħna biss ikollhom 7, 3, 9, u 6 fil siġra tagħna f'dan il-punt.

701
00:57:13,700 --> 00:57:18,870
Biex tkun żgur li din hija kollha tax-xogħol,

702
00:57:18,870 --> 00:57:25,050
nistgħu zoom out, tagħmel siġra binarju tagħna,

703
00:57:25,050 --> 00:57:30,750
run, u nistgħu naraw li fih huwa issa tgħidilna li aħna qed totalment dritt -

704
00:57:30,750 --> 00:57:33,110
5, 8, u 2 m'għadhomx fil-siġra.

705
00:57:33,110 --> 00:57:37,960
Mur lura fil-kodiċi,

706
00:57:37,960 --> 00:57:41,070
u kif ser nieħdu daħħal?

707
00:57:41,070 --> 00:57:46,290
Ftakar dak li għamilna meta konna fil-fatt li jdaħħal 5, 8, u 2 qabel.

708
00:57:46,290 --> 00:57:50,100
Aħna lagħbu din il-logħba Plinko fejn bdejna fil-għerq,

709
00:57:50,100 --> 00:57:52,780
niżlet il-wieħed siġra minn wieħed wieħed

710
00:57:52,780 --> 00:57:54,980
sakemm sibna l-vojt xieraq,

711
00:57:54,980 --> 00:57:57,570
u allura aħna fili fil-node fil-post xieraq.

712
00:57:57,570 --> 00:57:59,480
Aħna qed tmur biex jagħmlu l-istess ħaġa.

713
00:57:59,480 --> 00:58:04,070
Dan huwa bażikament simili kitba l-kodiċi li aħna użati fil-funzjoni fih

714
00:58:04,070 --> 00:58:05,910
biex issib l-post fejn il-node għandu jkun,

715
00:58:05,910 --> 00:58:10,560
u allura aħna qed biss jmorru biex tiddaħħal l-node hemm dritt.

716
00:58:10,560 --> 00:58:17,000
Nibdew tagħmel dan.

717
00:58:17,000 --> 00:58:24,200
>> Allura aħna għandna node * kur = għerq; aħna qed biss jmorru biex isegwu l-kodiċi fih

718
00:58:24,200 --> 00:58:26,850
sakemm insibu li ma pjuttost xogħol għalina.

719
00:58:26,850 --> 00:58:32,390
Aħna ser jgħaddu mill-siġra filwaqt li l-element attwali mhix null,

720
00:58:32,390 --> 00:58:45,280
u jekk insibu valur li kur hija ugwali għall-valur li aħna qed jippruvaw daħħal -

721
00:58:45,280 --> 00:58:49,600
ukoll, dan huwa wieħed mill-każijiet li fihom aħna ma setgħux effettivament daħħal il-node

722
00:58:49,600 --> 00:58:52,730
fil-siġra għax dan ifisser li għandna valur duplikat.

723
00:58:52,730 --> 00:58:59,010
Hawnhekk aħna qed attwalment għaddejjin li jirritornaw falza.

724
00:58:59,010 --> 00:59:08,440
Issa, inkella jekk il-valur kur hija inqas mill-valur,

725
00:59:08,440 --> 00:59:10,930
issa nafu li nimxu lejn il-lemin

726
00:59:10,930 --> 00:59:17,190
 minħabba li l-valur jappartjeni fil-nofs tal-lemin tas-siġra kur.

727
00:59:17,190 --> 00:59:30,110
Inkella, aħna qed tmur biex jimxu lejn ix-xellug.

728
00:59:30,110 --> 00:59:37,980
Li bażikament ma fiha tagħna jaħdem hemm dritt.

729
00:59:37,980 --> 00:59:41,820
>> Fuq dan il-punt, ladarba aħna ħadthom temmew dan loop filwaqt li,

730
00:59:41,820 --> 00:59:47,350
pointer kur tagħna se tkun tipponta lejn null

731
00:59:47,350 --> 00:59:51,540
jekk il-funzjoni ma tkunx diġà lura.

732
00:59:51,540 --> 00:59:58,710
Aħna li għaldaqstant għandha kur fil-post fejn irridu li daħħal il-node ġdid.

733
00:59:58,710 --> 01:00:05,210
Dak li għad irid isir huwa li fil-fatt jiżviluppaw l-node ġdid,

734
01:00:05,210 --> 01:00:08,480
li nistgħu nagħmlu pjuttost faċilment.

735
01:00:08,480 --> 01:00:14,930
Nistgħu nużaw super-handy funzjoni tagħna node jibnu,

736
01:00:14,930 --> 01:00:17,210
u xi ħaġa li aħna ma tagħmel preċedenti -

737
01:00:17,210 --> 01:00:21,400
aħna biss tip ta 'ħa għall mogħtija iżda issa aħna ser nagħmlu biss biex tiżgura -

738
01:00:21,400 --> 01:00:27,130
aħna ser test biex tiżgura li l-valur lura mill node ġdid kien effettivament

739
01:00:27,130 --> 01:00:33,410
mhux null, għaliex aħna ma jridu jibdew aċċess li l-memorja jekk huwa null.

740
01:00:33,410 --> 01:00:39,910
Aħna tista 'test biex tiżgura li node ġdid mhuwiex ugwali għal null.

741
01:00:39,910 --> 01:00:42,910
Jew minflok, nistgħu biss tara jekk fil-fatt hu null,

742
01:00:42,910 --> 01:00:52,120
u jekk huwa null, allura nistgħu biss ritorn foloz kmieni.

743
01:00:52,120 --> 01:00:59,090
>> Fuq dan il-punt, irridu wajer node ġdid fil-post xieraq tagħha fil-siġra.

744
01:00:59,090 --> 01:01:03,510
Jekk inħarsu lura lejn prinċipali u fejn konna fil-fatt wiring fil-valuri qabel,

745
01:01:03,510 --> 01:01:08,470
naraw li l-mod aħna kienu qed jagħmlu dan meta ridna li tpoġġi 3 fil-siġra

746
01:01:08,470 --> 01:01:11,750
kienet aħna aċċessati l-minuri xellug tal għerq.

747
01:01:11,750 --> 01:01:14,920
Meta npoġġux 9 fil-siġra, kellna biex jaċċessaw il-wild dritt ta 'l-għerq.

748
01:01:14,920 --> 01:01:21,030
Kellna li jkollhom pointer lill-ġenitur sabiex twaqqaf il-valur il-ġdid fis-siġra.

749
01:01:21,030 --> 01:01:24,430
Scrolling back up li daħħal, li mhux ser pjuttost xogħol hawn

750
01:01:24,430 --> 01:01:27,550
għaliex aħna ma jkollhomx pointer ġenitur.

751
01:01:27,550 --> 01:01:31,650
Dak li rridu li tkun tista 'tagħmel huwa, f'dan il-punt,

752
01:01:31,650 --> 01:01:37,080
jiċċekkjaw il-valur tal-ġenitur u ara - ukoll, gosh,

753
01:01:37,080 --> 01:01:41,990
jekk il-valur tal-ġenitur huwa inqas mill-valur kurrenti,

754
01:01:41,990 --> 01:01:54,440
imbagħad tifel dritt tal-ġenitur għandha tkun l-node ġdid;

755
01:01:54,440 --> 01:02:07,280
xort'oħra, tfal xellug tal-ġenitur għandha tkun l-node ġdid.

756
01:02:07,280 --> 01:02:10,290
Iżda, aħna ma jkollhomx dan il-werrej prinċipali għadhom pjuttost.

757
01:02:10,290 --> 01:02:15,010
>> Sabiex tikseb dan, aħna qed attwalment se jkollhom track kif aħna jgħaddu mill-siġra

758
01:02:15,010 --> 01:02:18,440
u ssib il-post xieraq fil loop tagħna hawn fuq.

759
01:02:18,440 --> 01:02:26,840
Nistgħu nagħmlu dan billi scrolling back up għall-quċċata tal-funzjoni daħħal tagħna

760
01:02:26,840 --> 01:02:32,350
u t-traċċar ieħor varjabbli pointer imsejjaħ il-ġenitur.

761
01:02:32,350 --> 01:02:39,340
Aħna ser tistabbilixxi li ugwali għal null inizjalment,

762
01:02:39,340 --> 01:02:43,640
u mbagħad kull darba li jgħaddu mill-siġra,

763
01:02:43,640 --> 01:02:51,540
aħna qed tmur biex jistabbilixxu l-pointer ġenitur biex tqabbel il-pointer kurrenti.

764
01:02:51,540 --> 01:02:59,140
Set ġenitur ugwali għal cur.

765
01:02:59,140 --> 01:03:02,260
Dan il-mod, kull darba immorru permezz,

766
01:03:02,260 --> 01:03:05,550
aħna qed tmur biex jiżguraw li l-pointer kurrenti gets inkrementat

767
01:03:05,550 --> 01:03:12,640
il-pointer ġenitur ġej dan - biss livell wieħed ogħla mill-pointer attwali fil-siġra.

768
01:03:12,640 --> 01:03:17,370
Dan kollu jidher pjuttost tajba.

769
01:03:17,370 --> 01:03:22,380
>> Naħseb li l-unika ħaġa li aħna inneħħu jridu jaġġustaw hija din tinbena null node jirritornaw.

770
01:03:22,380 --> 01:03:25,380
Sabiex tikseb jibnu node biex effettivament b'suċċess ritorn null,

771
01:03:25,380 --> 01:03:31,060
aħna ser ikollhom jimmodifikaw dan il-kodiċi,

772
01:03:31,060 --> 01:03:37,270
għaliex hawnhekk, aħna qatt ttestjati biex tiżgura li malloc lura pointer valida.

773
01:03:37,270 --> 01:03:53,390
Għalhekk, jekk (n = NULL!), Allura -

774
01:03:53,390 --> 01:03:55,250
jekk malloc rritornaw pointer valida, allura aħna ser initialize dan;

775
01:03:55,250 --> 01:04:02,540
mod ieħor, aħna ser biss jirritorna u li se jispiċċaw jirritornaw null għalina.

776
01:04:02,540 --> 01:04:13,050
Issa kollha jistenna pretty tajba. Ejja jagħmlu ċert li din fil-fatt jikkompila.

777
01:04:13,050 --> 01:04:22,240
Għamla siġra binarju, u oh, konna ltqajna xi għalf jiġri hawn.

778
01:04:22,240 --> 01:04:29,230
>> Imxejna ltqajna dikjarazzjoni impliċita ta 'funzjoni jibnu node.

779
01:04:29,230 --> 01:04:31,950
Għal darb'oħra, ma 'dawn kompilaturi, aħna qed tmur biex tibda fil-quċċata.

780
01:04:31,950 --> 01:04:36,380
Dak li għandu jfisser hu li jien ssejjaħ jibnu node qabel stajt attwalment ddikjarat lilha.

781
01:04:36,380 --> 01:04:37,730
Ejja ħa mmorru lura għall-kodiċi verament malajr.

782
01:04:37,730 --> 01:04:43,510
Skrollja 'l isfel, u żgur biżżejjed, funzjoni daħħal tiegħi huwa ddikjarat

783
01:04:43,510 --> 01:04:47,400
fuq il-funzjoni node jibnu,

784
01:04:47,400 --> 01:04:50,070
imma jien jippruvaw jużaw tibni node ġewwa tal daħħal.

785
01:04:50,070 --> 01:05:06,610
Jien ser tmur fi u kopja - u mbagħad paste l-mod jibnu funzjoni node up hawn fil-quċċata.

786
01:05:06,610 --> 01:05:11,750
B'dan il-mod, wieħed jittama li se jaħdmu. Ejjew nagħtu dan ieħor tmur.

787
01:05:11,750 --> 01:05:18,920
Issa dan kollu jikkompila. Kollha hija tajba.

788
01:05:18,920 --> 01:05:21,640
>> Iżda f'dan il-punt, aħna ma attwalment imsejħa funzjoni daħħal tagħna.

789
01:05:21,640 --> 01:05:26,510
Aħna biss jafu li jikkompila, hekk ejja jmorru fi u mqiegħda xi sejħiet pulzieri

790
01:05:26,510 --> 01:05:28,240
Ejja nagħmlu dan fil-funzjoni ewlenija tagħna.

791
01:05:28,240 --> 01:05:32,390
Hawnhekk, aħna ikkummenta out 5, 8, u 2,

792
01:05:32,390 --> 01:05:36,680
u allura aħna ma wajer lilhom stabbiliti hawn.

793
01:05:36,680 --> 01:05:41,640
Ejja jagħmlu xi sejħiet li ddaħħal,

794
01:05:41,640 --> 01:05:46,440
u ejja wkoll jużaw l-istess tip ta 'għalf li aħna użati

795
01:05:46,440 --> 01:05:52,810
meta għamilna dawn is-sejħiet printf biex tiżgura li kollox ma jiksbu jiddaħħal kif suppost.

796
01:05:52,810 --> 01:06:00,550
Jien ser kopja u paste,

797
01:06:00,550 --> 01:06:12,450
u minflok fih aħna qed tmur biex tagħmel daħħal.

798
01:06:12,450 --> 01:06:30,140
U minflok 6, 10, u 1, aħna qed tmur għall-użu 5, 8, u 2.

799
01:06:30,140 --> 01:06:37,320
Dan għandu nisperaw daħħal 5, 8, u 2 fil-siġra.

800
01:06:37,320 --> 01:06:44,050
Jikkompilaw. Kollha hija tajba. Issa aħna ser tmexxi effettivament programm tagħna.

801
01:06:44,050 --> 01:06:47,330
>> Kollox lura falza.

802
01:06:47,330 --> 01:06:53,830
Allura, 5, 8, u 2 ma tmurx, u jidher qisu ma fiha ma jsibu lilhom lanqas.

803
01:06:53,830 --> 01:06:58,890
X'qed jiġri? Ejja zoom out.

804
01:06:58,890 --> 01:07:02,160
L-ewwel problema kienet li daħħal deher li jirritornaw falza,

805
01:07:02,160 --> 01:07:08,750
u jidher qisu dan għaliex aħna xellug fis-sejħa lura falza tagħna,

806
01:07:08,750 --> 01:07:14,590
u aħna qatt fil-fatt ritornat veru.

807
01:07:14,590 --> 01:07:17,880
Aħna tista 'tistabbilixxi li up.

808
01:07:17,880 --> 01:07:25,290
It-tieni problema hija, issa anke jekk nagħmlu - ħlief dan, nieqaf dan,

809
01:07:25,290 --> 01:07:34,530
run jagħmlu mill-ġdid, li hija tiġbor, imbagħad run dan -

810
01:07:34,530 --> 01:07:37,670
naraw li xi ħaġa oħra ġara hawn.

811
01:07:37,670 --> 01:07:42,980
Il-5, 8, u 2 kienu għadhom qatt ma jinstabu fil-siġra.

812
01:07:42,980 --> 01:07:44,350
Allura, x'inhu għaddej?

813
01:07:44,350 --> 01:07:45,700
>> Ejja tagħti ħarsa lejn dan il-kodiċi.

814
01:07:45,700 --> 01:07:49,790
Ejja naraw jekk nistgħu figura dan.

815
01:07:49,790 --> 01:07:57,940
Nibdew mal-ġenitur ma jkunx null.

816
01:07:57,940 --> 01:07:59,510
Waqqafna l-pointer attwali ugwali għall-pointer għerq,

817
01:07:59,510 --> 01:08:04,280
u aħna qed tmur biex jaħdmu mod tagħna isfel permezz tal-siġra.

818
01:08:04,280 --> 01:08:08,650
Jekk l-node attwali mhuwiex null, allura nafu li nistgħu jimxu l isfel ftit.

819
01:08:08,650 --> 01:08:12,330
Waqqafna pointer parent tagħna li tkun ugwali għall-pointer attwali,

820
01:08:12,330 --> 01:08:15,420
ċċekkjati l-valur - jekk il-valuri huma l-istess aħna lura falza.

821
01:08:15,420 --> 01:08:17,540
Jekk il-valuri huma inqas aħna mċaqilqa lejn il-lemin;

822
01:08:17,540 --> 01:08:20,399
mod ieħor, aħna mċaqalqa lejn ix-xellug.

823
01:08:20,399 --> 01:08:24,220
Imbagħad aħna nibnu node. I ser zoom fi ftit.

824
01:08:24,220 --> 01:08:31,410
U hawn, aħna qed tmur biex tipprova wajer ta l-valuri li huma l-istess.

825
01:08:31,410 --> 01:08:37,250
X'qed jiġri? Ejja naraw jekk possibbilment Valgrind tista 'tagħtina ħjiel.

826
01:08:37,250 --> 01:08:43,910
>> I simili għall-użu Valgrind biss minħabba Valgrind verament malajr runs

827
01:08:43,910 --> 01:08:46,729
u jgħidlek jekk hemm xi żbalji memorja.

828
01:08:46,729 --> 01:08:48,300
Meta aħna run Valgrind dwar il-kodiċi,

829
01:08:48,300 --> 01:08:55,859
kif tista 'tara hit here--Valgrind./binary_tree--and dritt tidħol.

830
01:08:55,859 --> 01:09:03,640
Inti tara li aħna ma jkollhom l-ebda żball fil-memorja, hekk jidher qisu kollox huwa okay s'issa.

831
01:09:03,640 --> 01:09:07,529
We do jkollhom xi tnixxijiet memorja, li nafu, għaliex aħna mhux qed

832
01:09:07,529 --> 01:09:08,910
jiġri biex ħielsa xi lymph tagħna.

833
01:09:08,910 --> 01:09:13,050
Ejja tipprova taħdem GDB biex tara x'inhu attwalment għaddejjin.

834
01:09:13,050 --> 01:09:20,010
Aħna ser tagħmel GDB. / Binary_tree. Hija Booted up biss multa.

835
01:09:20,010 --> 01:09:23,670
Ejja jistabbilixxu punt tal-qasma fuq daħħal.

836
01:09:23,670 --> 01:09:28,600
Ejja run.

837
01:09:28,600 --> 01:09:31,200
Jidher qisu aħna qatt attwalment imsejħa daħħal.

838
01:09:31,200 --> 01:09:39,410
Jidher qisu l-problema kienet biss li meta I biddel l isfel hawn prinċipali -

839
01:09:39,410 --> 01:09:44,279
kollha ta 'dawn is-sejħiet printf mill fiha -

840
01:09:44,279 --> 01:09:56,430
Jien qatt ma attwalment nbidlu dawn li jsejħu daħħal.

841
01:09:56,430 --> 01:10:01,660
Issa ejja jipprova hu. Ejja jikkompilaw.

842
01:10:01,660 --> 01:10:09,130
Kollha jidher tajjeb hemm. Issa ejja ipprova ġestjoni tiegħu, tara x'jiġri.

843
01:10:09,130 --> 01:10:13,320
Alright! Kollox jidher pjuttost tajba hemmhekk.

844
01:10:13,320 --> 01:10:18,130
>> Il-ħaġa finali li wieħed jaħseb dwar huwa, hemm xi każijiet tarf għal dan daħħal?

845
01:10:18,130 --> 01:10:23,170
U jirriżulta li, ukoll, il-każ tarf wieħed li huwa dejjem interessanti li wieħed jaħseb dwar

846
01:10:23,170 --> 01:10:26,250
huwa, x'jiġri jekk siġra tiegħek ikun vojt u inti sejħa din il-funzjoni daħħal?

847
01:10:26,250 --> 01:10:30,330
Se taħdem? Ukoll, ejja jipprova hu.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
Il-mod kif aħna qed tmur biex jittestjaw dan, aħna qed tmur biex jinżlu għal funzjoni prinċipali tagħna,

850
01:10:35,810 --> 01:10:41,690
u minflok wiring dawn in-nodi up bħal dan,

851
01:10:41,690 --> 01:10:56,730
aħna qed biss jmorru biex jikkummenta l-ħaġa sħiħa,

852
01:10:56,730 --> 01:11:02,620
u minflok ta 'wajers ta' l-lymph nfusna,

853
01:11:02,620 --> 01:11:09,400
nistgħu attwalment biss jimxi 'l quddiem u ħassar kollha ta' dan.

854
01:11:09,400 --> 01:11:17,560
Aħna ser tagħmel dak kollu sejħa li daħħal.

855
01:11:17,560 --> 01:11:49,020
Allura, ejja do - minflok ta '5, 8, u 2, aħna qed tmur biex daħħal 7, 3, u 9.

856
01:11:49,020 --> 01:11:58,440
U allura aħna ser ukoll tixtieq li daħħal 6 kif ukoll.

857
01:11:58,440 --> 01:12:05,190
Save. Nieqaf. Għamla siġra binarju.

858
01:12:05,190 --> 01:12:08,540
Dan kollu jikkompila.

859
01:12:08,540 --> 01:12:10,320
Nistgħu biss run kif u tara x'jiġri,

860
01:12:10,320 --> 01:12:12,770
iżda huwa wkoll se tkun verament importanti li jiġi żgurat li

861
01:12:12,770 --> 01:12:14,740
aħna m'għandniex xi żbalji memorja,

862
01:12:14,740 --> 01:12:16,840
peress li dan huwa wieħed mill-każijiet tarf tagħna li nafu dwar.

863
01:12:16,840 --> 01:12:20,150
>> Ejja kun żgur li taħdem sew taħt Valgrind,

864
01:12:20,150 --> 01:12:28,310
li aħna ser nagħmlu billi biss running Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Jidher qisu aħna tabilħaqq għandna waħda iżbalji minn kuntest -

866
01:12:31,110 --> 01:12:33,790
aħna għandna dan tort segmentazzjoni.

867
01:12:33,790 --> 01:12:36,690
Dak li ġara?

868
01:12:36,690 --> 01:12:41,650
Valgrind attwalment tgħidilna fejn hu.

869
01:12:41,650 --> 01:12:43,050
Zoom out ftit.

870
01:12:43,050 --> 01:12:46,040
Jidher qisu dan qed jiġri fil-funzjoni daħħal tagħna,

871
01:12:46,040 --> 01:12:53,420
fejn għandna taqra invalidu 'daqs 4 fi daħħal, linja 60.

872
01:12:53,420 --> 01:13:03,590
Ejja mmorru lura u tara x'inhu għaddej hawn.

873
01:13:03,590 --> 01:13:05,350
Zoom out verament malajr.

874
01:13:05,350 --> 01:13:14,230
I jixtiequ jagħmlu ċert li din ma tmurx għall-tarf tal-iskrin sabiex nistgħu naraw kollox.

875
01:13:14,230 --> 01:13:18,760
Iġbed li fi ftit. Alright.

876
01:13:18,760 --> 01:13:35,030
Skrollja 'l isfel, u l-problema hija dritt hawn.

877
01:13:35,030 --> 01:13:40,120
X'jiġri jekk irridu jiksbu l isfel u node attwali tagħna hija diġà null,

878
01:13:40,120 --> 01:13:44,010
node prinċipali tagħna huwa null, hekk jekk inħarsu up fuq nett, dritt hawn -

879
01:13:44,010 --> 01:13:47,340
jekk dan loop filwaqt li qatt ma attwalment tesegwixxi

880
01:13:47,340 --> 01:13:52,330
għaliex il-valur attwali tagħna huwa null - għeruq tagħna huwa null tant kur huwa null -

881
01:13:52,330 --> 01:13:57,810
imbagħad parent tagħna qatt gets stabbiliti biex kur jew għal valur validu,

882
01:13:57,810 --> 01:14:00,580
hekk, ġenitur se jkun ukoll null.

883
01:14:00,580 --> 01:14:03,700
Għandna bżonn li wieħed jiftakar sabiex jikkontrolla għal dak

884
01:14:03,700 --> 01:14:08,750
mill-ħin aħna nikseb stabbiliti hawn, u nibdew aċċess valur tal-ġenitur.

885
01:14:08,750 --> 01:14:13,190
Allura, dak li jiġri? Ukoll, jekk il-ġenitur huwa null -

886
01:14:13,190 --> 01:14:17,990
jekk (ġenitur == NULL) - allura aħna nafu li

887
01:14:17,990 --> 01:14:19,530
m'għandux ikun hemm xejn fil-siġra.

888
01:14:19,530 --> 01:14:22,030
Għandna nkunu qed jipprova daħħalha fil-għerq.

889
01:14:22,030 --> 01:14:32,570
Nistgħu nagħmlu dan billi sempliċiment jistabbilixxi l-għerq ugwali għall-node ġdid.

890
01:14:32,570 --> 01:14:40,010
Imbagħad f'dan il-punt, aħna ma attwalment jridu jgħaddu dawn l-affarijiet l-oħra.

891
01:14:40,010 --> 01:14:44,780
Minflok, dritt hawn, nistgħu nagħmlu la inkella ta 'jekk-ieħor,

892
01:14:44,780 --> 01:14:47,610
jew nistgħu jikkombinaw kollox up here b'mod ieħor,

893
01:14:47,610 --> 01:14:56,300
iżda hawnhekk aħna ser biss użu ieħor u tagħmel dan il-mod.

894
01:14:56,300 --> 01:14:59,030
Issa, aħna qed tmur biex tittestja biex taċċerta ruħek li ġenitur tagħna ma huwiex null

895
01:14:59,030 --> 01:15:02,160
qabel mbagħad fil-fatt jippruvaw jiksbu aċċess għas-oqsma tagħha.

896
01:15:02,160 --> 01:15:05,330
Dan għandu jgħina tevita l-tort segmentazzjoni.

897
01:15:05,330 --> 01:15:14,740
Allura, aħna nieqaf, zoom out, tikkompila, run.

898
01:15:14,740 --> 01:15:18,130
>> Ebda żbalji, iżda xorta għad għandhom mazz ta 'tnixxijiet memorja

899
01:15:18,130 --> 01:15:20,650
għaliex aħna ma ħielsa xi lymph tagħna.

900
01:15:20,650 --> 01:15:24,350
Iżda, jekk immorru up hawn u nħarsu lejn printout tagħna,

901
01:15:24,350 --> 01:15:30,880
naraw li, ukoll, qisu kollha ta 'inserts tagħna kienu jirritornaw vera, li hija tajba.

902
01:15:30,880 --> 01:15:33,050
L-inserzjonijiet huma kollha vera,

903
01:15:33,050 --> 01:15:36,670
u mbagħad is-sejħiet fih xierqa huma wkoll veru.

904
01:15:36,670 --> 01:15:41,510
>> Tajba tax-xogħol! Jidher qisu aħna ħadthom b'suċċess bil-miktub daħħal.

905
01:15:41,510 --> 01:15:47,430
Li kollox għandna għall Speċifikazzjoni din il-ġimgħa Set Problema.

906
01:15:47,430 --> 01:15:51,720
Waħda mill-isfidi gost li wieħed jaħseb dwar huwa kif inti fil-fatt imorru fil

907
01:15:51,720 --> 01:15:55,340
u ħielsa kollha tal-lymph f'dan siġra.

908
01:15:55,340 --> 01:15:58,830
Nistgħu nagħmlu hekk numru ta 'modi differenti,

909
01:15:58,830 --> 01:16:01,930
imma jien ser leave li sa inti biex esperiment,

910
01:16:01,930 --> 01:16:06,080
u bħala sfida gost, ipprova u kun żgur li inti tista 'tagħmel ċert

911
01:16:06,080 --> 01:16:09,490
li dan ir-rapport Valgrind prospetti ebda żbalji u l-ebda tnixxijiet.

912
01:16:09,490 --> 01:16:12,880
>> Xorti tajba dwar din il-ġimgħa sett Huffman problema kodifikazzjoni,

913
01:16:12,880 --> 01:16:14,380
u aħna ser tara inti ġimgħa d-dieħla!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]