1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [It-Taqsima 7: Aktar komda]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Università ta 'Harvard]

3
00:00:05,090 --> 00:00:07,930
[Dan huwa CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Kull dritt. Allura bħal I said fil-email tiegħi,

5
00:00:10,110 --> 00:00:14,060
dan se tkun sezzjoni binarja-siġra intensiv.

6
00:00:14,060 --> 00:00:16,820
Iżda ma jkunx hemm li ħafna mistoqsijiet.

7
00:00:16,820 --> 00:00:18,920
Allura aħna qed tmur biex jippruvaw u tfassal l kull mistoqsija

8
00:00:18,920 --> 00:00:25,430
u jidħlu fid-dettal uġigħ ta 'l-aħjar modi ta' nagħmlu l-affarijiet.

9
00:00:25,430 --> 00:00:31,200
Allura dritt fil-bidu, aħna jgħaddu tpinġijiet kampjun ta 'siġar binarju u l-għalf.

10
00:00:31,200 --> 00:00:35,970
Allura hawnhekk, "Ftakar li siġra binarju għandha lymph simili għal dawk ta 'lista marbuta,

11
00:00:35,970 --> 00:00:38,150
ħlief minflok waħda pointer hemm żewġ: waħda għal "tfal" ix-xellug

12
00:00:38,150 --> 00:00:41,950
u wieħed għad-dritt "tfal". "

13
00:00:41,950 --> 00:00:45,630
Allura siġra binarju huwa bħad lista marbuta,

14
00:00:45,630 --> 00:00:47,910
ħlief il-Struct se jkollha żewġ pointers.

15
00:00:47,910 --> 00:00:51,390
Hemm siġar trinary, li huma se jkollhom tliet pointers,

16
00:00:51,390 --> 00:00:56,540
hemm N-ARY siġar, li biss għandhom pointer ġeneriku

17
00:00:56,540 --> 00:01:00,320
li inti mbagħad ikollhom malloc li jkun kbir biżżejjed biex ikollhom

18
00:01:00,320 --> 00:01:04,840
pointers biżżejjed għall-tfal kollha possibbli.

19
00:01:04,840 --> 00:01:08,200
Allura siġra binarju jiġri biss li jkollhom numru kostanti ta 'tnejn.

20
00:01:08,200 --> 00:01:11,260
Jekk trid, tista 'tagħti lista marbut kif siġra unary,

21
00:01:11,260 --> 00:01:15,360
imma ma naħsibx xi ħadd jitlob dan li.

22
00:01:15,360 --> 00:01:18,060
"Pinġi dijagramma kaxxi-u-vleġeġ ta 'nodu siġra binarju

23
00:01:18,060 --> 00:01:24,110
li jkun fih in-numru favoriti Nate s, 7, fejn kull pointer wild huwa null. "

24
00:01:24,110 --> 00:01:27,780
Allura iPad modalità.

25
00:01:27,780 --> 00:01:30,280
>> Huwa ser ikun pjuttost sempliċi.

26
00:01:30,280 --> 00:01:36,150
Aħna biss se jkollhom node, jien ser tiġbed bħala kwadru.

27
00:01:36,150 --> 00:01:38,730
U jien ser tiġbed l-valuri fil hawn.

28
00:01:38,730 --> 00:01:41,090
Allura l-valur se jmorru fil hawn,

29
00:01:41,090 --> 00:01:44,770
u mbagħad stabbiliti hawn aħna ser ikollhom l-pointer xellug fuq ix-xellug u l-pointer dritt fuq il-lemin.

30
00:01:44,770 --> 00:01:50,430
U huwa ferm hekk konvenzjoni li hija sejħa xellug u dritt, l-ismijiet pointer.

31
00:01:50,430 --> 00:01:52,460
Kemm minn dawn ser ikunu nulli.

32
00:01:52,460 --> 00:01:57,870
Li se biss tkun nulla, u li se jkun biss null.

33
00:01:57,870 --> 00:02:03,630
Okay. Allura lura hawn.

34
00:02:03,630 --> 00:02:05,700
"Ma 'lista marbuta, aħna biss kellhom biex jaħżnu pointer

35
00:02:05,700 --> 00:02:09,639
l-node ewwel fil-lista sabiex tiftakar il-lista kollha marbutin, jew il-lista sħiħa.

36
00:02:09,639 --> 00:02:11,650
Bl-istess mod, bis-siġar, aħna biss biex jaħżnu pointer

37
00:02:11,650 --> 00:02:13,420
għal node wieħed sabiex tiftakar il-siġra kollha.

38
00:02:13,420 --> 00:02:15,980
Dan node huwa Calle l-"għerq" tas-siġra.

39
00:02:15,980 --> 00:02:18,320
Jibnu fuq dijagramma tiegħek minn qabel jew jiġbed waħda ġdida

40
00:02:18,320 --> 00:02:21,690
b'tali mod li inti għandek rappreżentazzjoni kaxxi-u-vleġeġ ta 'siġra binarju

41
00:02:21,690 --> 00:02:25,730
ma 'l-il-valur 7, imbagħad 3 fil-linja xellugija,

42
00:02:25,730 --> 00:02:32,760
imbagħad 9 fuq il-lemin, u mbagħad 6 dwar id-dritt tal-magna 3. "

43
00:02:32,760 --> 00:02:34,810
Ejja naraw jekk I jistgħu jiftakru kollha ta 'dak in my head.

44
00:02:34,810 --> 00:02:37,670
Allura dan se jkun għeruq tagħna up here.

45
00:02:37,670 --> 00:02:41,600
Aħna ser ikollhom xi pointer x'imkien, xi ħaġa li aħna ser sejħa għeruq,

46
00:02:41,600 --> 00:02:45,140
u huwa tipponta lejn dan Guy.

47
00:02:45,140 --> 00:02:48,490
Issa biex tagħmel node ġdid,

48
00:02:48,490 --> 00:02:52,870
dak li għandna, 3 fuq ix-xellug?

49
00:02:52,870 --> 00:02:57,140
Allura node ġdid bi 3, u huwa inizjalment punti null.

50
00:02:57,140 --> 00:02:59,190
I ser biss jitqiegħed N.

51
00:02:59,190 --> 00:03:02,250
Issa aħna tixtieq li tagħmel dan jmorru lejn ix-xellug ta '7.

52
00:03:02,250 --> 00:03:06,840
Allura aħna bidla dan il-werrej li issa jindikaw dan Guy.

53
00:03:06,840 --> 00:03:12,420
U aħna jagħmlu l-istess. Irridu a 9 minn hawn

54
00:03:12,420 --> 00:03:14,620
li inizjalment biss jgħid null.

55
00:03:14,620 --> 00:03:19,600
Aħna ser jibdlu dan il-werrej, punt sa 9,

56
00:03:19,600 --> 00:03:23,310
u issa rridu li tqiegħed 6 lejn il-lemin ta '3.

57
00:03:23,310 --> 00:03:32,170
Allura li għaddej biex - jagħmlu 6.

58
00:03:32,170 --> 00:03:34,310
U li Guy se punt hemmhekk.

59
00:03:34,310 --> 00:03:38,320
Okay. Allura dak kollu li jitlob minna li tagħmel.

60
00:03:38,320 --> 00:03:42,770
>> Issa ejja jmorru fuq xi terminoloġija.

61
00:03:42,770 --> 00:03:46,690
Aħna diġà tkellem dwar kif l-għerq tal-siġra huwa l-node top-aktar fil-siġra.

62
00:03:46,690 --> 00:03:54,720
Il-wieħed li jkun fih 7. Il-lymph fil-qiegħ tas-siġra huma msejħa l-weraq.

63
00:03:54,720 --> 00:04:01,240
Kull node li biss għandu null bħala tfal tagħha hija weraq.

64
00:04:01,240 --> 00:04:03,680
Għalhekk huwa possibbli, jekk siġra binarju tagħna huwa biss node wieħed,

65
00:04:03,680 --> 00:04:10,130
li siġra hija weraq, u li hu.

66
00:04:10,130 --> 00:04:12,060
"Il-" għoli "tas-siġra huwa n-numru ta 'hops għandek tagħmel

67
00:04:12,060 --> 00:04:16,620
biex tikseb mill-quċċata li werqa. "

68
00:04:16,620 --> 00:04:18,640
Aħna ser jsibu rwieħhom, fit-tieni, id-differenza

69
00:04:18,640 --> 00:04:21,940
bejn is-siġar binarju bilanċjat u żbilanċjata,

70
00:04:21,940 --> 00:04:29,470
iżda għal issa, l-għoli ġenerali ta 'din is-siġra

71
00:04:29,470 --> 00:04:34,520
Jien ngħid huwa 3, għalkemm jekk inti jgħoddu l-għadd tal-ħops

72
00:04:34,520 --> 00:04:39,710
inti għandek tagħmel sabiex tikseb sa 9, allura huwa verament biss f'għoli ta '2.

73
00:04:39,710 --> 00:04:43,340
Dritt issa dan huwa siġra binarju żbilanċjat,

74
00:04:43,340 --> 00:04:49,840
iżda aħna ser tkellimna dwar bilanċjat meta jiġrilha li tkun rilevanti.

75
00:04:49,840 --> 00:04:52,040
Allura issa nistgħu nitkellmu dwar nodes fi siġra f'termini

76
00:04:52,040 --> 00:04:54,700
relattiv għall-lymph oħra fil-siġra.

77
00:04:54,700 --> 00:04:59,730
Allura issa għandna ġenituri, tfal, aħwa, antenati, u dixxendenti.

78
00:04:59,730 --> 00:05:05,650
Huma sens pjuttost komuni, dak li jfisser.

79
00:05:05,650 --> 00:05:09,610
Jekk aħna nistaqsu - ġenituri huwa.

80
00:05:09,610 --> 00:05:12,830
Allura x'inhi l-ġenitur tat-3 ta?

81
00:05:12,830 --> 00:05:16,090
[Studenti] 7. >> Yeah. Il-ġenitur huwa biss se tkun liema punti lilek.

82
00:05:16,090 --> 00:05:20,510
Imbagħad liema huma t-tfal ta 7?

83
00:05:20,510 --> 00:05:23,860
[Studenti] 3 u 9. >> Yeah.

84
00:05:23,860 --> 00:05:26,460
Avviż li "tfal" letteralment tfisser tfal,

85
00:05:26,460 --> 00:05:31,010
hekk 6 ma tapplikax, għaliex dan huwa simili neputi.

86
00:05:31,010 --> 00:05:35,540
Imma mbagħad jekk immorru dixxendenti, iva, liema huma l-dixxendenti ta '7?

87
00:05:35,540 --> 00:05:37,500
[Studenti] 3, 6 u 9. >> Yeah.

88
00:05:37,500 --> 00:05:42,330
Il-dixxendenti ta 'l-node għerq se tkun kollox fil-siġra,

89
00:05:42,330 --> 00:05:47,950
ħlief forsi l-node għerq innifsu, jekk inti ma tridx li jikkunsidraw li dixxendent.

90
00:05:47,950 --> 00:05:50,750
U fl-aħħarnett, antenati, dan huwa l-direzzjoni opposta.

91
00:05:50,750 --> 00:05:55,740
Allura x'inhuma l-antenati ta '6?

92
00:05:55,740 --> 00:05:58,920
[Studenti] 3 u 7. >> Yeah. 9 mhix inkluża.

93
00:05:58,920 --> 00:06:02,520
Huwa biss id-dahar nisel dirett għall-għerq

94
00:06:02,520 --> 00:06:13,230
se tkun antenati tiegħek.

95
00:06:13,230 --> 00:06:16,300
>> "Aħna ngħidu li siġra binarju huwa" ordnat "jekk għal kull node fil-siġra,

96
00:06:16,300 --> 00:06:19,530
kollha tal-dixxendenti tiegħu fuq ix-xellug għandhom valuri inqas

97
00:06:19,530 --> 00:06:22,890
u kollha ta 'dawk fuq il-lemin għandhom valuri akbar.

98
00:06:22,890 --> 00:06:27,060
Per eżempju, is-siġra ta 'hawn fuq huwa ordnat iżda mhux l-arranġament possibbli biss ordnat. "

99
00:06:27,060 --> 00:06:30,180
Qabel nikbru għal dan,

100
00:06:30,180 --> 00:06:36,420
siġra binarju ordnat hija magħrufa wkoll bħala siġra tfittxija binarja.

101
00:06:36,420 --> 00:06:38,660
Hawnhekk aħna jiġri li jkun ssejjaħ dan siġra binarju ordnat,

102
00:06:38,660 --> 00:06:41,850
imma jien qatt ma semgħu dan jissejjaħ siġra binarju ordnati qabel,

103
00:06:41,850 --> 00:06:46,650
u fuq kwizz aħna huma ħafna aktar probabbli li jitqiegħdu siġra tfittxija binarja.

104
00:06:46,650 --> 00:06:49,250
Huma qed l-istess,

105
00:06:49,250 --> 00:06:54,580
u huwa importanti li inti jirrikonoxxu d-distinzjoni bejn siġra binarju u siġar tfittxija binarja.

106
00:06:54,580 --> 00:06:58,830
A siġra binarju huwa biss siġra li l-punti għal żewġ affarijiet.

107
00:06:58,830 --> 00:07:02,120
Kull node punti għal żewġ affarijiet.

108
00:07:02,120 --> 00:07:06,310
M'hemm l-ebda motivazzjoni dwar il-valuri li jipponta lejn.

109
00:07:06,310 --> 00:07:11,370
Allura bħal hawn fuq, peress li huwa siġra tfittxija binarju,

110
00:07:11,370 --> 00:07:14,030
nafu li jekk immorru xellug ta '7,

111
00:07:14,030 --> 00:07:16,670
allura kollha tal-valuri li nistgħu possibilment jilħaq

112
00:07:16,670 --> 00:07:19,310
billi tmur xellug ta '7 għandhom ikunu anqas minn 7.

113
00:07:19,310 --> 00:07:24,070
Avviż li l-valuri ta 'inqas minn 7 huma 3 u 6.

114
00:07:24,070 --> 00:07:26,040
Dawk huma kollha fuq ix-xellug ta '7.

115
00:07:26,040 --> 00:07:29,020
Jekk immorru lejn il-lemin tas-7, kollox għandu jkun ikbar minn 7,

116
00:07:29,020 --> 00:07:33,220
hekk 9 huwa għad-dritt tas-7, hekk aħna qed tajba.

117
00:07:33,220 --> 00:07:36,150
Dan mhuwiex il-każ għal siġra binarju,

118
00:07:36,150 --> 00:07:40,020
għal siġra binarju regolari nistgħu biss għandhom 3 fil-quċċata, 7 għall-xellug,

119
00:07:40,020 --> 00:07:47,630
9 ix-xellug ta '7; hemm l-ebda ordni ta' valuri tkun xi tkun.

120
00:07:47,630 --> 00:07:56,140
Issa, aħna mhux se fil-fatt jagħmlu dan għaliex dan huwa tedious u bla bżonn,

121
00:07:56,140 --> 00:07:59,400
imma "jippruvaw jiġbdu siġar kif ħafna ordnat kif inti tista 'taħseb

122
00:07:59,400 --> 00:08:01,900
jużaw in-numri 7, 3, 9, u 6.

123
00:08:01,900 --> 00:08:06,800
Kemm arranġamenti distinti hemm? X'inhu l-għoli ta 'kull waħda? "

124
00:08:06,800 --> 00:08:10,480
>> Aħna ser tagħmel koppja, imma l-idea prinċipali hija,

125
00:08:10,480 --> 00:08:16,530
dan huwa bl-ebda mod ta 'rappreżentazzjoni unika ta' siġra binarju jkun fih dawn il-valuri.

126
00:08:16,530 --> 00:08:22,760
Kollha għandna bżonn huwa xi siġra binarju li fiha 7, 3, 6, u 9.

127
00:08:22,760 --> 00:08:25,960
Ieħor validu possibbli tista 'tkun l-għerq huwa 3,

128
00:08:25,960 --> 00:08:30,260
mur lejn ix-xellug u huwa 6, mur lejn ix-xellug u huwa 7,

129
00:08:30,260 --> 00:08:32,730
mur lejn ix-xellug u huwa 9.

130
00:08:32,730 --> 00:08:36,169
Din hija perfettament valida siġra tfittxija binarja.

131
00:08:36,169 --> 00:08:39,570
Mhuwiex utli ħafna, għaliex dan huwa biss bħal lista marbuta

132
00:08:39,570 --> 00:08:43,750
u kollha ta 'dawn pointers huma biss null.

133
00:08:43,750 --> 00:08:48,900
Iżda huwa siġra valida. Yeah?

134
00:08:48,900 --> 00:08:51,310
[Student] M'għandekx il-valuri għandhom ikunu akbar fuq il-lemin?

135
00:08:51,310 --> 00:08:56,700
Jew hija din -? >> Dawn I fisser li jmorru l-mod ieħor.

136
00:08:56,700 --> 00:09:00,960
Hemm ukoll - yeah, ejja jaqilbu li.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Tajba qabda.

138
00:09:07,770 --> 00:09:11,730
Hija xorta għandha li jobdu dak tfittxija siġra binarju suppost tagħmel.

139
00:09:11,730 --> 00:09:15,650
Allura kollox lejn ix-xellug għandha tkun inqas minn kull node partikolari.

140
00:09:15,650 --> 00:09:23,180
Nistgħu biss jiċċaqalqu, jgħidu, dan 6 u poġġih hawn.

141
00:09:23,180 --> 00:09:26,880
Le, ma nistgħux. Għaliex għandi iżommu tagħmel dan?

142
00:09:26,880 --> 00:09:35,350
Ejja nagħmlu - hawnhekk huwa 6, hawnhekk huwa 7, 6 punti sa 3.

143
00:09:35,350 --> 00:09:39,290
Dan għadu siġra valida tfittxija binarja.

144
00:09:39,290 --> 00:09:49,260
Dak li hu ħażin jekk I - ejja ara jekk nista 'toħroġ bi arranġament.

145
00:09:49,260 --> 00:09:52,280
Yeah, okay. Allura dak li hu ħażin ma 'din is-siġra?

146
00:09:52,280 --> 00:10:08,920
I raden stajt diġà tak ħjiel li hemm xi ħaġa ħażina magħha.

147
00:10:08,920 --> 00:10:14,430
Għaliex għandi iżommu tagħmel dan?

148
00:10:14,430 --> 00:10:18,510
Okay. Dan jidher raġonevoli.

149
00:10:18,510 --> 00:10:22,590
Jekk inħarsu lejn kull node, bħal 7, allura ix-xellug ta '7 huwa 3.

150
00:10:22,590 --> 00:10:24,960
Allura aħna għandna 3, il-ħaġa li d-dritt tat-3 huwa 6.

151
00:10:24,960 --> 00:10:27,750
U jekk inti tħares lejn 6, il-ħaġa li d-dritt tas-6 hija 9.

152
00:10:27,750 --> 00:10:30,910
Allura għaliex huwa dan mhuwiex siġra validu tfittxija binarju?

153
00:10:30,910 --> 00:10:36,330
[Studenti] 9 għadu fuq ix-xellug ta '7. >> Yeah.

154
00:10:36,330 --> 00:10:43,710
Għandu jkun veru li l-valuri kollha inti tista 'possibilment tilħaq billi tmur fuq ix-xellug ta' 7 huma inqas minn 7.

155
00:10:43,710 --> 00:10:49,120
Jekk immorru xellug ta '7, we sa 3 u aħna xorta jistgħu jiksbu sa 6,

156
00:10:49,120 --> 00:10:52,520
aħna xorta jistgħu jiksbu sa 9, iżda minn wara marret inqas minn 7,

157
00:10:52,520 --> 00:10:55,070
aħna ma għandhom ikunu jistgħu jiksbu numru li l-ikbar minn 7.

158
00:10:55,070 --> 00:10:59,830
Allura dan mhux siġra valida tfittxija binarja.

159
00:10:59,830 --> 00:11:02,330
>> My brother attwalment kellu mistoqsija intervista

160
00:11:02,330 --> 00:11:07,760
li kienet bażikament dan, biss il-kodiċi up xi ħaġa li jivvalida

161
00:11:07,760 --> 00:11:10,500
jekk siġra hija siġra tfittxija binarju,

162
00:11:10,500 --> 00:11:13,580
u għalhekk l-ewwel ħaġa huwa ma kien biss tikkontrolla biex tara

163
00:11:13,580 --> 00:11:17,020
jekk ix-xellug u tal-lemin huma korretti, u mbagħad jtenni stabbiliti hemmhekk.

164
00:11:17,020 --> 00:11:19,700
Imma int ma tista 'biss tagħmel dan, inti għandek biex iżommu kont

165
00:11:19,700 --> 00:11:22,550
tal-fatt li issa li stajt marret xellug ta '7,

166
00:11:22,550 --> 00:11:26,340
kollox f'dan subtree għandu jkun inqas minn 7.

167
00:11:26,340 --> 00:11:28,430
L-algoritmu korretta jeħtieġ li jżommu rekord

168
00:11:28,430 --> 00:11:35,970
tal-limiti li l-valuri jistgħu possibbilment jaqgħu pulzieri

169
00:11:35,970 --> 00:11:38,360
Aħna mhux se jmorru permezz ta 'kull wieħed minnhom.

170
00:11:38,360 --> 00:11:41,630
Teżisti relazzjoni rikorrenza sbieħ,

171
00:11:41,630 --> 00:11:44,810
għalkemm aħna ma gotten għal dawk, jew aħna mhux se tikseb għal dawk,

172
00:11:44,810 --> 00:11:47,030
jiddefinixxi kemm hemm fil-fatt huma.

173
00:11:47,030 --> 00:11:53,180
Allura hemm 14 minnhom.

174
00:11:53,180 --> 00:11:56,020
L-idea ta 'kif inti se tagħmel dan matematikament huwa simili,

175
00:11:56,020 --> 00:11:59,770
inti tista 'pick xi wieħed li jkun l-node għerq,

176
00:11:59,770 --> 00:12:03,160
u mbagħad jekk I pick 7 li tkun l-node għerq,

177
00:12:03,160 --> 00:12:08,150
allura hemm, jiġifieri, xi numri li jistgħu imorru jkun node xellug tiegħi,

178
00:12:08,150 --> 00:12:10,440
u hemm xi numri li jistgħu jkunu node dritt tiegħi,

179
00:12:10,440 --> 00:12:15,090
imma jekk jien n għadd totali, allura l-ammont li tista 'tmur lejn ix-xellug

180
00:12:15,090 --> 00:12:18,820
flimkien mal-ammont li jista 'jmur lejn il-lemin huwa n - 1.

181
00:12:18,820 --> 00:12:26,130
Allura tan-numri li jifdal, dawn għandhom ikunu jistgħu jmorru jew lejn ix-xellug jew il-lemin.

182
00:12:26,130 --> 00:12:31,580
Jidher diffiċli li, jekk nressaq 3 1 allura kollox irid imur lejn ix-xellug,

183
00:12:31,580 --> 00:12:35,080
imma jekk nressaq 7, allura xi affarijiet jistgħu jmorru ix-xellug tal-u xi affarijiet jistgħu jmorru lejn il-lemin.

184
00:12:35,080 --> 00:12:39,570
U billi '3 '1 I fisser kollox tista' tmur lejn il-lemin.

185
00:12:39,570 --> 00:12:42,350
Huwa tassew, inti biss għandek biex jaħsbu dwar dan bħala,

186
00:12:42,350 --> 00:12:47,980
affarijiet kemm tista 'tmur fuq il-livell li jmiss tas-siġra.

187
00:12:47,980 --> 00:12:50,420
U niġu biex tkun 14; jew inti tista 'tiġbed minnhom kollha,

188
00:12:50,420 --> 00:12:54,650
u allura inti ser tingħata 14.

189
00:12:54,650 --> 00:13:01,120
>> Jmorru lura hawn,

190
00:13:01,120 --> 00:13:03,510
"Siġar Ordered binarji huma jibred għaliex aħna tista 'tfittex permezz tagħhom

191
00:13:03,510 --> 00:13:06,910
b'mod simili ħafna għal tiftix fuq firxa magħżula.

192
00:13:06,910 --> 00:13:10,120
Biex tagħmel dan, nibdew l-għerq u x-xogħol mod tagħna isfel fil-siġra

193
00:13:10,120 --> 00:13:13,440
lejn weraq, verifika valuri kull node kontra l-valuri li aħna qed tfittex.

194
00:13:13,440 --> 00:13:15,810
Jekk il-valur tal-node attwali hija inqas mill-valur aħna qed tfittex,

195
00:13:15,810 --> 00:13:18,050
inti tmur ħdejn tfal id-dritt tal-node s.

196
00:13:18,050 --> 00:13:20,030
Inkella, inti tmur tifel xellug tal-node s.

197
00:13:20,030 --> 00:13:22,800
F'xi punt, inti ser issib kemm il-valur li qed tfittex, jew tkun taf run fis null,

198
00:13:22,800 --> 00:13:28,520
jindika l-valur mhux fil-siġra. "

199
00:13:28,520 --> 00:13:32,450
Għandi biex tiġbed l-siġra kellna qabel; li ser tieħu t-tieni.

200
00:13:32,450 --> 00:13:38,280
Iżda rridu nħarsu up jekk 6, 10, u 1 huma fil-siġra.

201
00:13:38,280 --> 00:13:49,180
Allura dak li kien, 7, 9, 3, 6. Okay.

202
00:13:49,180 --> 00:13:52,730
In-numri li inti tixtieq tfittex up, irridu li tfittex up 6.

203
00:13:52,730 --> 00:13:55,440
Kif taħdem din algoritmu?

204
00:13:55,440 --> 00:14:03,040
Ukoll, irridu wkoll xi pointer għeruq għall siġra tagħna.

205
00:14:03,040 --> 00:14:12,460
U aħna se jmorru għall-għerq u jgħidu, hija din il-valur ekwivalenti għall-valur aħna qed tiftix għal?

206
00:14:12,460 --> 00:14:15,000
Allura aħna qed infittxu 6, dan mhuwiex ugwali.

207
00:14:15,000 --> 00:14:20,140
Allura aħna iżommu għaddejjin, u issa nistgħu ngħidu, okay, sabiex 6 huwa inqas minn 7.

208
00:14:20,140 --> 00:14:23,940
Dan ifisser li aħna rridu li jmorru lejn ix-xellug, jew irridu li jmorru lejn il-lemin?

209
00:14:23,940 --> 00:14:27,340
[Student] Xellug. >> Yeah.

210
00:14:27,340 --> 00:14:33,340
Huwa ferm aktar faċli, kull ma għandek tagħmel hu li jiġbed 1 node possibbli tas-siġra

211
00:14:33,340 --> 00:14:37,760
u allura inti don 't - minflok tipprova biex jaħsbu fir-ras,

212
00:14:37,760 --> 00:14:40,020
okay, jekk huwa inqas, ma mmur lejn ix-xellug jew mur fuq il-lemin,

213
00:14:40,020 --> 00:14:43,030
biss tħares lejn din l-istampa, huwa ċar ħafna li I ikollhom imorru lejn ix-xellug

214
00:14:43,030 --> 00:14:47,700
jekk dan node huwa akbar mill-valur li jien infittxu.

215
00:14:47,700 --> 00:14:52,600
Allura inti tmur lejn ix-xellug, issa jien fi 3.

216
00:14:52,600 --> 00:14:57,770
Irrid li - 3 huwa anqas mill-valur jien infittxu, li hija 6.

217
00:14:57,770 --> 00:15:03,420
Allura aħna jmorru lejn il-lemin, u issa I jispiċċaw ta '6,

218
00:15:03,420 --> 00:15:07,380
li huwa l-valur jien infittxu, so I ritorn vera.

219
00:15:07,380 --> 00:15:15,760
Il-valur li jmiss jien ser tfittex huwa 10.

220
00:15:15,760 --> 00:15:23,230
Okay. Allura 10, issa, se - cut off li - ser isegwu l-għerq.

221
00:15:23,230 --> 00:15:27,670
Issa, 10 se tkun ikbar minn 7, so I tixtieq tfittex għad-dritt.

222
00:15:27,670 --> 00:15:31,660
Jien ser jiġi maż hawn, 10 se tkun ikbar minn 9,

223
00:15:31,660 --> 00:15:34,520
hekk jien ser tixtieq tfittex għad-dritt.

224
00:15:34,520 --> 00:15:42,100
Nasal hawn fuq, iżda minn hawn issa jien fil null.

225
00:15:42,100 --> 00:15:44,170
X'għandi nagħmel jekk I hit null?

226
00:15:44,170 --> 00:15:47,440
[Student] Ritorn falza? >> Yeah. I ma sabx 10.

227
00:15:47,440 --> 00:15:49,800
1 se jkun hemm każ kważi identiċi,

228
00:15:49,800 --> 00:15:51,950
ħlief huwa biss se jiġu flipped; minflok tħares

229
00:15:51,950 --> 00:15:56,540
fuq il-lemin, jien ser tħares mal-linja xellugija.

230
00:15:56,540 --> 00:16:00,430
>> Now I think we attwalment tikseb għall-kodiċi.

231
00:16:00,430 --> 00:16:04,070
Hawn fejn - tiftaħ il-appliance CS50 u jinnavigaw mod tiegħek hemmhekk,

232
00:16:04,070 --> 00:16:07,010
imma int tista 'wkoll biss tagħmel dan fl-ispazju.

233
00:16:07,010 --> 00:16:09,170
Huwa probabbilment ideali biex jagħmlu dan fl-ispazju,

234
00:16:09,170 --> 00:16:13,760
għaliex nistgħu naħdmu fl-ispazju.

235
00:16:13,760 --> 00:16:19,170
"L-ewwel għandna bzonn definizzjoni tip ġdid għal node siġra binarju jkun fih valuri int.

236
00:16:19,170 --> 00:16:21,400
Uża l-boilerplate typedef hawn taħt,

237
00:16:21,400 --> 00:16:24,510
toħloq definizzjoni tip ġdid għal node fil-siġra binarju.

238
00:16:24,510 --> 00:16:27,930
Jekk ikollok staġnati. . . "Blah, blah, blah. Okay.

239
00:16:27,930 --> 00:16:30,380
Mela ejja tpoġġi l-boilerplate hawn,

240
00:16:30,380 --> 00:16:41,630
typedef Struct node, u node. Yeah, okay.

241
00:16:41,630 --> 00:16:44,270
Allura x'inhuma l-oqsma aħna qed tmur jridu fil node tagħna?

242
00:16:44,270 --> 00:16:46,520
[Student] Int u allura żewġ pointers?

243
00:16:46,520 --> 00:16:49,700
>> Int valur, żewġ pointers? Kif nista 'tikteb l-pointers?

244
00:16:49,700 --> 00:16:58,440
[Student] Struct. >> I għandha zoom pulzieri Yeah, hekk Struct node * xellug,

245
00:16:58,440 --> 00:17:01,320
u Struct node * dritt.

246
00:17:01,320 --> 00:17:03,460
U ftakar-diskussjoni mill-aħħar darba,

247
00:17:03,460 --> 00:17:15,290
li dan jagħmel ebda sens, dan jagħmel ebda sens,

248
00:17:15,290 --> 00:17:18,270
dan jagħmel ebda sens.

249
00:17:18,270 --> 00:17:25,000
Ikollok bżonn kollox hemm biex jiddefinixxu din Struct rikursivi.

250
00:17:25,000 --> 00:17:27,970
Okay, hekk dan huwa dak siġra tagħna se look like.

251
00:17:27,970 --> 00:17:37,670
Jekk għamilna siġra trinary, allura node jista 'dehra b1, b2, Struct * node b3,

252
00:17:37,670 --> 00:17:43,470
fejn b hija fergħa - fil-fatt, stajt aktar smajtu xellug,, id-dritt tan-nofs, iżda tkun xi tkun.

253
00:17:43,470 --> 00:17:55,610
Aħna biss jimpurtahom binarju, hekk id-dritt, xellug.

254
00:17:55,610 --> 00:17:59,110
"Issa tiddikjara varjabbli globali * node għall-għerq tal-siġra."

255
00:17:59,110 --> 00:18:01,510
Allura aħna ma tkunx qed tmur biex tagħmel dan.

256
00:18:01,510 --> 00:18:08,950
Sabiex tagħmel l-affarijiet ftit aktar diffiċli u aktar ġeneralizzata,

257
00:18:08,950 --> 00:18:11,570
aħna mhux se jkollhom varjabbli node globali.

258
00:18:11,570 --> 00:18:16,710
Minflok, fl prinċipali aħna se jiddikjara l-affarijiet node tagħna,

259
00:18:16,710 --> 00:18:20,500
u dan ifisser li hawn taħt, meta aħna tibda taħdem

260
00:18:20,500 --> 00:18:23,130
ma fiha l-funzjoni tagħna u l-funzjoni daħħal tagħna,

261
00:18:23,130 --> 00:18:27,410
minflok ma fiha tagħna jaħdem biss bl-użu dan il-varjabbli node globali,

262
00:18:27,410 --> 00:18:34,280
aħna qed tmur biex ikollhom dan jieħu bħala argument l-siġra li aħna rridu li jipproċessaw.

263
00:18:34,280 --> 00:18:36,650
Wara li l-varjabbli globali kien suppost li tagħmel affarijiet eħfef.

264
00:18:36,650 --> 00:18:42,310
Aħna ser tagħmel l-affarijiet aktar diffiċli.

265
00:18:42,310 --> 00:18:51,210
Issa tieħu minuta jew hekk biex biss tagħmel dan it-tip ta 'ħaġa,

266
00:18:51,210 --> 00:18:57,690
fejn ġewwa tal ewlenija tixtieq toħloq din is-siġra, u li kollox inti trid tagħmel.

267
00:18:57,690 --> 00:19:04,530
Ipprova u jibnu din is-siġra fil-funzjoni prinċipali tiegħek.

268
00:19:42,760 --> 00:19:47,610
>> Okay. Allura inti ma jkollhomx biex tkun mibnija l-siġra l-mod kollu s'issa.

269
00:19:47,610 --> 00:19:49,840
Imma ħadd xi ħaġa I tista 'pull up

270
00:19:49,840 --> 00:20:03,130
biex turi kif wieħed jista 'jibda jibni tali siġra?

271
00:20:03,130 --> 00:20:08,080
[Student] banging Xi ħadd, tipprova toħroġ.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Kull min komda mal-kostruzzjoni siġra tagħhom?

273
00:20:13,100 --> 00:20:15,520
[Student] Sure. Huwa ma jsirx. >> Huwa tal-multa. Nistgħu biss finitura -

274
00:20:15,520 --> 00:20:26,860
oh, tista 'tfaddal dan? Hooray.

275
00:20:26,860 --> 00:20:32,020
Allura hawnhekk għandna - oh, jien ftit maqtugħa.

276
00:20:32,020 --> 00:20:34,770
Am I żżomjati fil-?

277
00:20:34,770 --> 00:20:37,730
Zoom fil-scroll barra. >> Għandi mistoqsija. >> Yeah?

278
00:20:37,730 --> 00:20:44,410
[Student] Meta inti tiddefinixxi Struct, huma affarijiet simili initialized għal xejn?

279
00:20:44,410 --> 00:20:47,160
[Bowden] No >> Okay. Allura inti jkollha initialize -

280
00:20:47,160 --> 00:20:50,450
[Bowden] No Meta inti tiddefinixxi, jew meta inti tiddikjara Struct,

281
00:20:50,450 --> 00:20:55,600
mhuwiex initialized fil-kontumaċja; huwa biss simili jekk inti tiddikjara int.

282
00:20:55,600 --> 00:20:59,020
Huwa eżattament l-istess ħaġa. Huwa simili kull wieħed mill-oqsma individwali tiegħu

283
00:20:59,020 --> 00:21:04,460
jista 'jkollhom valur żibel fiha. >> U huwa possibbli li wieħed jiddefinixxi - jew li jiddikjara Struct

284
00:21:04,460 --> 00:21:07,740
b'mod li dan ma initialize minnhom?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Iva. Allura, sintassi inizjalizzazzjoni shortcut

286
00:21:13,200 --> 00:21:18,660
se look like -

287
00:21:18,660 --> 00:21:22,200
Hemm żewġ modi li nistgħu nagħmlu dan. Naħseb li għandna josservawha

288
00:21:22,200 --> 00:21:25,840
biex clang żgur ukoll ma dan.

289
00:21:25,840 --> 00:21:28,510
L-ordni ta 'argumenti li taqa' fil-Struct,

290
00:21:28,510 --> 00:21:32,170
inti tpoġġi l-ordni ta 'argumenti ġewwa ta' dawn ċineg kaboċċi.

291
00:21:32,170 --> 00:21:35,690
Mela jekk inti tixtieq li initialize li sa 9 u ħalla jiġu nulli u mbagħad dritt null,

292
00:21:35,690 --> 00:21:41,570
ikun 9, null, null.

293
00:21:41,570 --> 00:21:47,890
L-alternattiva hija, u l-editur ma bħal dan sintassi,

294
00:21:47,890 --> 00:21:50,300
u jidhirlu Irrid blokk ġdid,

295
00:21:50,300 --> 00:22:01,800
iżda l-alternattiva hija xi ħaġa simili -

296
00:22:01,800 --> 00:22:04,190
hawn, jien ser poġġih fuq linja ġdida.

297
00:22:04,190 --> 00:22:09,140
Tista 'b'mod espliċitu tgħid, I tinsa l-sintassi eżatta.

298
00:22:09,140 --> 00:22:13,110
Allura inti tista 'espliċitament jindirizzawhom bl-isem, u jgħidu,

299
00:22:13,110 --> 00:22:21,570
. C, jew. Valur = 9,. NULL xellug =.

300
00:22:21,570 --> 00:22:24,540
Jien guessing dawn jeħtieġ li jkunu virgoli.

301
00:22:24,540 --> 00:22:29,110
. Dritt = NULL, sabiex b'dan il-mod inti ma

302
00:22:29,110 --> 00:22:33,780
fil-fatt jeħtieġ li tkun taf l-ordni tal-Struct,

303
00:22:33,780 --> 00:22:36,650
u meta inti qed taqra dan, huwa ħafna aktar espliċita

304
00:22:36,650 --> 00:22:41,920
dwar dak il-valur l-jiġu initialized għall.

305
00:22:41,920 --> 00:22:44,080
>> Dan jiġri li jkun wieħed mill-affarijiet li -

306
00:22:44,080 --> 00:22:49,100
hekk, għall-parti l-kbira, C + + huwa superset ta 'C.

307
00:22:49,100 --> 00:22:54,160
Tista 'tieħu kodiċi C, jimxu jikkonsenjaha lill C + +, u għandu jikkompila.

308
00:22:54,160 --> 00:22:59,570
Din hija waħda mill-affarijiet li C + + ma tagħti appoġġ, sabiex in-nies għandhom tendenza li ma tagħmel dan.

309
00:22:59,570 --> 00:23:01,850
I do not know jekk dan huwa l-unika raġuni nies għandhom tendenza li ma tagħmel dan,

310
00:23:01,850 --> 00:23:10,540
iżda l-każ fejn I meħtieġa sabiex jintuża meħtieġa biex taħdem ma 'C + + u so I ma setgħux jużaw dan.

311
00:23:10,540 --> 00:23:14,000
Eżempju ieħor ta 'xi ħaġa li ma taħdimx mal-C + + huwa

312
00:23:14,000 --> 00:23:16,940
kif malloc jirritorna "* vojt," teknikament,

313
00:23:16,940 --> 00:23:20,200
imma int tista 'biss jgħidu char * x kwalunkwe malloc =,

314
00:23:20,200 --> 00:23:22,840
u se awtomatikament mitfugħa sabiex a * char.

315
00:23:22,840 --> 00:23:25,450
Dan mitfugħa awtomatika ma jiġri fis-C + +.

316
00:23:25,450 --> 00:23:28,150
Dan ma jkunx tiġbor, u inti espliċitament bżonn li ngħidu

317
00:23:28,150 --> 00:23:34,510
* char, malloc, tkun xi tkun, li jitfa hija għal * char.

318
00:23:34,510 --> 00:23:37,270
M'hemmx ħafna affarijiet li C u C + + ma jaqblux fuq,

319
00:23:37,270 --> 00:23:40,620
imma dawn huma tnejn.

320
00:23:40,620 --> 00:23:43,120
Allura aħna ser jmorru ma 'dan sintassi.

321
00:23:43,120 --> 00:23:46,150
Iżda anke jekk aħna ma jmorru ma 'dak sintassi,

322
00:23:46,150 --> 00:23:49,470
dak li hu - jista 'jkun ħażin ma' dan?

323
00:23:49,470 --> 00:23:52,170
[Student] I m'għandhomx bżonn li dereference dan? >> Yeah.

324
00:23:52,170 --> 00:23:55,110
Ftakar li l-vleġġa għandha dereference impliċitu,

325
00:23:55,110 --> 00:23:58,230
u għalhekk meta aħna qed biss jittrattaw ma 'Struct,

326
00:23:58,230 --> 00:24:04,300
irridu jużaw. tikseb fuq ġewwa qasam ta 'l-Struct.

327
00:24:04,300 --> 00:24:07,200
U l-ħin biss nużaw vleġġa huwa meta rridu nagħmlu -

328
00:24:07,200 --> 00:24:13,450
ukoll, vleġġa huwa ekwivalenti għal -

329
00:24:13,450 --> 00:24:17,020
dan huwa dak li kienet tfisser jekk I użati vleġġa.

330
00:24:17,020 --> 00:24:24,600
Kollha mezzi vleġġa qiegħda, dereference dan, issa jien fuq Struct, u nista 'nikseb il-qasam.

331
00:24:24,600 --> 00:24:28,040
Jew jiksbu l-qasam direttament jew dereference u jiksbu l-qasam -

332
00:24:28,040 --> 00:24:30,380
I raden dan għandu jkun il-valur.

333
00:24:30,380 --> 00:24:33,910
Imma hawn jien li jittrattaw biss bi Struct, mhux pointer għal Struct,

334
00:24:33,910 --> 00:24:38,780
u so I ma tistax tuża l-vleġġa.

335
00:24:38,780 --> 00:24:47,510
Iżda dan it-tip ta 'ħaġa li nistgħu nagħmlu għall-lymph.

336
00:24:47,510 --> 00:24:55,790
Oh my God.

337
00:24:55,790 --> 00:25:09,540
Dan huwa 6, 7, u 3.

338
00:25:09,540 --> 00:25:16,470
Imbagħad nistgħu stabbilit il-fergħat fil-siġra tagħna, aħna jista 'jkollna 7 -

339
00:25:16,470 --> 00:25:21,650
jista 'jkollna, xellug tagħha għandu punt sa 3.

340
00:25:21,650 --> 00:25:25,130
Allura kif nistgħu nagħmlu dan?

341
00:25:25,130 --> 00:25:29,320
[Studenti, mhux intelliġibbli] >> Yeah. L-indirizz tal node3,

342
00:25:29,320 --> 00:25:34,170
u jekk inti ma kellhiex indirizz, allura biss ma jikkumpilaw.

343
00:25:34,170 --> 00:25:38,190
Imma ftakar li dawn huma indikaturi għall-lymph jmiss.

344
00:25:38,190 --> 00:25:44,930
Id-dritt għandu jiġi sa 9,

345
00:25:44,930 --> 00:25:53,330
u 3 għandhom jindikaw fuq id-dritt għal 6.

346
00:25:53,330 --> 00:25:58,480
Naħseb li dan huwa stabbilit. Xi kummenti jew mistoqsijiet?

347
00:25:58,480 --> 00:26:02,060
[Student, mhux intelliġibbli] L-għerq se tkun 7.

348
00:26:02,060 --> 00:26:08,210
Nistgħu biss jgħidu node * ptr =

349
00:26:08,210 --> 00:26:14,160
jew, għeruq = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Għall-għanijiet tagħna, aħna qed tmur biex tkun jittrattaw daħħal,

351
00:26:20,730 --> 00:26:25,490
hekk aħna qed tmur jridu jiktbu funzjoni li ddaħħal fil din is-siġra binarju

352
00:26:25,490 --> 00:26:34,230
u daħħal hija inevitabbilment ser sejħa malloc li jinħoloq node ġdid għal din is-siġra.

353
00:26:34,230 --> 00:26:36,590
Allura l-affarijiet se tikseb messy mal-fatt li xi glandoli

354
00:26:36,590 --> 00:26:38,590
bħalissa fuq il-munzell

355
00:26:38,590 --> 00:26:43,680
u l-lymph oħra ser jispiċċaw fuq il-borġ meta aħna daħħal minnhom.

356
00:26:43,680 --> 00:26:47,640
Dan huwa perfettament validu, iżda l-unika raġuni

357
00:26:47,640 --> 00:26:49,600
aħna kapaċi li jagħmlu dan fuq il-munzell

358
00:26:49,600 --> 00:26:51,840
huwa għaliex dan huwa tali eżempju artifiċjali li nafu

359
00:26:51,840 --> 00:26:56,360
l-siġra suppost tkun mibnija b'mod 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Jekk aħna ma kellhomx din, allura aħna ma jkollhomx malloc fl-ewwel post.

361
00:27:02,970 --> 00:27:06,160
Kif Ser naraw daqsxejn aktar tard, għandna nkunu malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Dritt issa huwa perfettament raġonevoli li jitpoġġew fuq il-munzell,

363
00:27:08,570 --> 00:27:14,750
imma ejja bidla dan għal implimentazzjoni malloc.

364
00:27:14,750 --> 00:27:17,160
Allura kull wieħed minn dawn huwa issa se tkun xi ħaġa simili

365
00:27:17,160 --> 00:27:24,240
node * node9 = malloc (sizeof (node)).

366
00:27:24,240 --> 00:27:28,040
U issa aħna qed tmur biex ikollhom jagħmlu verifika tagħna.

367
00:27:28,040 --> 00:27:34,010
jekk (node9 == NULL) - I ma riedx li -

368
00:27:34,010 --> 00:27:40,950
ritorn 1, u allura nistgħu nagħmlu node9-> għaliex issa dan huwa pointer,

369
00:27:40,950 --> 00:27:45,300
valur = 6, node9-> = NULL xellug,

370
00:27:45,300 --> 00:27:48,930
node9-> = NULL dritt,

371
00:27:48,930 --> 00:27:51,410
u aħna qed tmur biex ikollhom jagħmlu dan għal kull waħda minn dawn lymph.

372
00:27:51,410 --> 00:27:57,490
Allura minflok, ejja poġġih ġewwa ta 'funzjoni separata.

373
00:27:57,490 --> 00:28:00,620
Ejja sejħa hija node * build_node,

374
00:28:00,620 --> 00:28:09,050
u dan huwa pjuttost simili għall-APIs aħna jipprovdu għall Huffman kodifikazzjoni.

375
00:28:09,050 --> 00:28:12,730
Aħna nagħtuk l-funzjonijiet initializer għal siġra

376
00:28:12,730 --> 00:28:20,520
u deconstructor "funzjonijiet" għal dawk is-siġar u l-istess għall-foresti.

377
00:28:20,520 --> 00:28:22,570
>> Allura hawnhekk aħna qed tmur biex ikollhom funzjoni initializer

378
00:28:22,570 --> 00:28:25,170
għal ftit jibnu node għalina.

379
00:28:25,170 --> 00:28:29,320
U li għaddej biex tħares pretty ħafna eżattament bħal dan.

380
00:28:29,320 --> 00:28:32,230
U jien anke se tkun għażżien u ma jinbidel l-isem tal-varjabbli,

381
00:28:32,230 --> 00:28:34,380
anki jekk node9 jagħmel ebda sens aktar.

382
00:28:34,380 --> 00:28:38,610
Oh, I raden il-valur node9 li ma kellux 6.

383
00:28:38,610 --> 00:28:42,800
Issa nistgħu lura node9.

384
00:28:42,800 --> 00:28:49,550
U hawn għandna ritorn null.

385
00:28:49,550 --> 00:28:52,690
Kulħadd jaqbel dwar dik il-funzjoni jibnu-a-node?

386
00:28:52,690 --> 00:28:59,780
Allura issa nistgħu biss sejħa li jibnu kwalunkwe node b'valur partikolari u indikaturi nulla.

387
00:28:59,780 --> 00:29:09,750
Issa nistgħu sejħa li, nistgħu nagħmlu node * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
U ejja do. . .

389
00:29:25,810 --> 00:29:33,980
6, 3, 7, 6, 3, 7.

390
00:29:33,980 --> 00:29:39,330
U issa aħna tixtieq li twaqqaf l-pointers istess,

391
00:29:39,330 --> 00:29:42,470
ħlief issa kollox huwa diġà f'termini tal pointers

392
00:29:42,470 --> 00:29:48,480
sabiex l-ebda bżonn aktar l-indirizz ta '.

393
00:29:48,480 --> 00:29:56,300
Okay. Allura x'inhu l-aħħar ħaġa li nixtieq do?

394
00:29:56,300 --> 00:30:03,850
Hemm żball ta 'verifika li jien ma nagħmilx.

395
00:30:03,850 --> 00:30:06,800
Xi jfisser jibnu ritorn node?

396
00:30:06,800 --> 00:30:11,660
[Student, mhux intelliġibbli] >> Yeah. Naqset malloc Jekk, inneħħu ritorn null.

397
00:30:11,660 --> 00:30:16,460
Allura jien ser lazily tpoġġi l-isfel hawn minflok tagħmel kondizzjoni għal kull wieħed.

398
00:30:16,460 --> 00:30:22,320
Jekk (node9 == NULL, jew - anki sempliċi,

399
00:30:22,320 --> 00:30:28,020
din hija ekwivalenti għal biss jekk mhux node9.

400
00:30:28,020 --> 00:30:38,310
Mela jekk le node9, jew mhux node6, jew mhux node3, jew mhux node7, ritorn 1.

401
00:30:38,310 --> 00:30:42,850
Forsi għandna jistampaw malloc naqas, jew xi ħaġa.

402
00:30:42,850 --> 00:30:46,680
[Student] Huwa falza ugwali għal null kif ukoll?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Kwalunkwe valur żero hija falza.

404
00:30:51,290 --> 00:30:53,920
Allura null hija valur żero.

405
00:30:53,920 --> 00:30:56,780
Żero huwa valur żero. Foloz huwa valur żero.

406
00:30:56,780 --> 00:31:02,130
Kull - pretty ħafna l-uniċi 2 valuri żero huma nulli u żero,

407
00:31:02,130 --> 00:31:07,900
falza huwa biss hash definit bħala żero.

408
00:31:07,900 --> 00:31:13,030
Dan japplika wkoll jekk aħna tiddikjara varjabbli globali.

409
00:31:13,030 --> 00:31:17,890
Jekk aħna ma jkollhom l-għeruq * node up hawn,

410
00:31:17,890 --> 00:31:24,150
allura - il-ħaġa sbieħ dwar fatturi varjabbli globali huwa li dawn dejjem ikollhom valur inizjali.

411
00:31:24,150 --> 00:31:27,500
Li mhux veru tal-funzjonijiet, kif ġewwa ta 'hawn,

412
00:31:27,500 --> 00:31:34,870
jekk ikollna, bħal, * node node jew x.

413
00:31:34,870 --> 00:31:37,380
Għandna l-ebda idea dak x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
jew nistgħu jistampaw minnhom u dawn jistgħu jkunu arbitrarja.

415
00:31:40,700 --> 00:31:44,980
Li mhux veru ta 'varjabbli globali.

416
00:31:44,980 --> 00:31:47,450
Għerq Allura node node jew x.

417
00:31:47,450 --> 00:31:53,410
Permezz ta 'default, dak kollu li globali, jekk mhux espliċitament initialized sa ċertu valur,

418
00:31:53,410 --> 00:31:57,390
għandu valur żero bħala l-valur tagħha.

419
00:31:57,390 --> 00:32:01,150
Allura hawnhekk, għeruq * node, aħna ma espliċitament initialize li xejn,

420
00:32:01,150 --> 00:32:06,350
sabiex il-valur default tiegħu se tkun nulla, li huwa l-valur żero ta 'indikaturi.

421
00:32:06,350 --> 00:32:11,870
Il-valur ta 'default ta' x se jfisser li x.value huwa żero,

422
00:32:11,870 --> 00:32:14,260
x.left hija nulla, u x.right huwa null.

423
00:32:14,260 --> 00:32:21,070
Allura peress li huwa Struct, kollha ta 'l-oqsma ta' l-Struct se jkun b'valur żero.

424
00:32:21,070 --> 00:32:24,410
Aħna ma bżonn jużaw dan hawn, għalkemm.

425
00:32:24,410 --> 00:32:27,320
[Student] Il-structs huma differenti minn varjabbli oħra, u l-varjabbli l-oħra

426
00:32:27,320 --> 00:32:31,400
Valuri taż-żibel; dawn huma żerijiet?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Valuri oħra wisq. Għalhekk fl x, x se jkun żero.

428
00:32:36,220 --> 00:32:40,070
Jekk huwa fuq firxa globali, ikollu valur inizjali. Okay. >>

429
00:32:40,070 --> 00:32:48,950
[Bowden] Jew il-valur inizjali inti tatha jew żero.

430
00:32:48,950 --> 00:32:53,260
Naħseb li jieħu ħsieb ta 'dan kollu.

431
00:32:53,260 --> 00:32:58,390
>> Okay. Allura l-parti li jmiss tal-mistoqsija tistaqsi,

432
00:32:58,390 --> 00:33:01,260
"Issa rridu li jiktbu funzjoni msejħa fih

433
00:33:01,260 --> 00:33:04,930
ma 'prototip ta' bool fih valur int. "

434
00:33:04,930 --> 00:33:08,340
Aħna mhux se tagħmel bool fih valur int.

435
00:33:08,340 --> 00:33:15,110
Prototip tagħna se look like

436
00:33:15,110 --> 00:33:22,380
bool fih (valur int.

437
00:33:22,380 --> 00:33:24,490
U allura aħna wkoll qed tmur biex tgħaddih-siġra

438
00:33:24,490 --> 00:33:28,870
li għandu jiġi verifikat biex tara jekk ikollu dak il-valur.

439
00:33:28,870 --> 00:33:38,290
Allura node * siġar). Okay.

440
00:33:38,290 --> 00:33:44,440
U allura nistgħu sejħa hija ma 'xi ħaġa simili,

441
00:33:44,440 --> 00:33:46,090
forsi aħna ser jridu printf jew xi ħaġa.

442
00:33:46,090 --> 00:33:51,040
Fih 6, għeruq tagħna.

443
00:33:51,040 --> 00:33:54,300
Dan għandu jirritorna wieħed, jew vera,

444
00:33:54,300 --> 00:33:59,390
billi fih 5 għerq għandu jirritorna falza.

445
00:33:59,390 --> 00:34:02,690
Allura tieħu t-tieni biex jimplimentaw dan.

446
00:34:02,690 --> 00:34:06,780
Tista 'tagħmel dan jew iteratively jew recursively.

447
00:34:06,780 --> 00:34:09,739
Il-ħaġa sbieħ dwar il-mod kif konna stabbiliti affarijiet up huwa li

448
00:34:09,739 --> 00:34:12,300
tippresta ruħha għall-soluzzjoni rikursivi tagħna ħafna aktar faċli

449
00:34:12,300 --> 00:34:14,719
milli l-mod globali-varjabbli għamlet.

450
00:34:14,719 --> 00:34:19,750
Għaliex jekk aħna biss għandhom jinkludi valur int, allura għandna l-ebda mod ta 'recursing isfel subtrees.

451
00:34:19,750 --> 00:34:24,130
Aħna jkollu bżonn li jkollu funzjoni helper separata li recurses r-subtrees għalina.

452
00:34:24,130 --> 00:34:29,610
Iżda peress li aħna stajt mibdula biex tieħu l-siġra bħala argument,

453
00:34:29,610 --> 00:34:32,760
li għandha dejjem kienu fl-ewwel post,

454
00:34:32,760 --> 00:34:35,710
Issa nistgħu recurse aktar faċilment.

455
00:34:35,710 --> 00:34:38,960
Allura iterattiv jew rikursivi, aħna ser jmorru fuq it-tnejn,

456
00:34:38,960 --> 00:34:46,139
imma aħna ser tara li l-truf jirrikorri biex tkun pjuttost faċli.

457
00:34:59,140 --> 00:35:02,480
Okay. Ħadd ma jkollu xi ħaġa li nistgħu naħdmu ma?

458
00:35:02,480 --> 00:35:12,000
>> [Student] Stajt ltqajna iterattiv soluzzjoni. >> Kull dritt, iterattiv.

459
00:35:12,000 --> 00:35:16,030
Okay, dan jidher tajjeb.

460
00:35:16,030 --> 00:35:18,920
Allura, tixtieq li jimxu lilna permezz ta 'dan?

461
00:35:18,920 --> 00:35:25,780
[Student] Sure. So I sett ta 'varjabbli temperatura li jiksbu l-node 1 tas-siġra.

462
00:35:25,780 --> 00:35:28,330
U mbagħad I biss looped permezz filwaqt temperatura ma null ugwali,

463
00:35:28,330 --> 00:35:31,700
sabiex filwaqt li kien għadu fil-siġra, I raden.

464
00:35:31,700 --> 00:35:35,710
U jekk il-valur huwa ugwali għall-valur li temperatura hija li tipponta lejn,

465
00:35:35,710 --> 00:35:37,640
allura dan jirritorna dak il-valur.

466
00:35:37,640 --> 00:35:40,210
Inkella, hija għandha tivverifika jekk huwa fuq il-lemin jew ix-xellug.

467
00:35:40,210 --> 00:35:43,400
Jekk inti qatt tikseb sitwazzjoni fejn hemm l-ebda siġra aktar,

468
00:35:43,400 --> 00:35:47,330
allura dan jirritorna - meta toħroġ il-linja u prospetti foloz.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Okay. Allura li jidher tajjeb.

470
00:35:52,190 --> 00:35:58,470
Kull min ikollu xi kummenti dwar xi ħaġa?

471
00:35:58,470 --> 00:36:02,400
Għandi l-ebda kummenti korrettezza fil-livelli kollha.

472
00:36:02,400 --> 00:36:11,020
L-unika ħaġa li nistgħu nagħmlu huwa dan Guy.

473
00:36:11,020 --> 00:36:21,660
Oh, li għaddej biex tmur longish ftit.

474
00:36:21,660 --> 00:36:33,460
I ser jiffissaw dan up. Okay.

475
00:36:33,460 --> 00:36:37,150
>> Kulħadd għandhom jiftakru jaħdem tenarji kif.

476
00:36:37,150 --> 00:36:38,610
Kien hemm definittivament ġew kwizzijiet fil-passat

477
00:36:38,610 --> 00:36:41,170
li jtik funzjoni ma 'operatur ta' tlett fibri,

478
00:36:41,170 --> 00:36:45,750
u jgħidu, tittraduċi dan, jagħmel xi ħaġa li ma jużax tenarji.

479
00:36:45,750 --> 00:36:49,140
Allura dan huwa każ komuni ħafna ta 'meta jiena naħseb li tuża tlett fibri,

480
00:36:49,140 --> 00:36:54,610
fejn jekk xi kondizzjoni stabbilita varjabbli għal xi ħaġa,

481
00:36:54,610 --> 00:36:58,580
inkella stabbilit dak il-varjabbli istess għal xi ħaġa oħra.

482
00:36:58,580 --> 00:37:03,390
Dik xi ħaġa li ħafna drabi tista 'tiġi ttrasformata dan it-tip ta' ħaġa

483
00:37:03,390 --> 00:37:14,420
fejn tistabbilixxi li varjabbli għal dan - jew, ukoll, dan huwa minnu? Imbagħad dan, inkella dan.

484
00:37:14,420 --> 00:37:18,550
[Student] L-ewwel waħda hija jekk vera, right?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Yeah. Il-mod I dejjem taqra li huwa, temperatura ugwali valur akbar mill-valur temperatura,

486
00:37:25,570 --> 00:37:30,680
allura dan, inkella dan. Huwa tistaqsi mistoqsija.

487
00:37:30,680 --> 00:37:35,200
Huwa akbar? Imbagħad jagħmlu l-ewwel ħaġa. Inkella jagħmlu l-ħaġa tieni.

488
00:37:35,200 --> 00:37:41,670
I kważi dejjem - il-kolon, I biss - fir-ras tiegħi, I jaqra kif ieħor.

489
00:37:41,670 --> 00:37:47,180
>> Ħadd ma jkollu soluzzjoni rikursivi?

490
00:37:47,180 --> 00:37:49,670
Okay. Dan wieħed aħna qed tmur biex - jista 'diġà jkun kbir,

491
00:37:49,670 --> 00:37:53,990
imma aħna qed tmur biex jagħmilha ferm aħjar.

492
00:37:53,990 --> 00:37:58,720
Dan huwa pjuttost l-idea eżatt l-istess.

493
00:37:58,720 --> 00:38:03,060
Huwa biss, ukoll, inti tixtieq li tispjega?

494
00:38:03,060 --> 00:38:08,340
[Student] Sure. Allura aħna qed jagħmlu ċert li l-siġra ma jkunx null 1,

495
00:38:08,340 --> 00:38:13,380
għaliex jekk l-siġra huwa null allura huwa għaddej biex jirritornaw foloz għaliex aħna ma sabu dan.

496
00:38:13,380 --> 00:38:19,200
U jekk hemm għadu siġra, immorru fis - aħna l-ewwel jiċċekkja jekk il-valur huwa l-node kurrenti.

497
00:38:19,200 --> 00:38:23,740
Ritorn veru jekk huwa, u jekk mhux aħna recurse fuq il-lemin jew xellug.

498
00:38:23,740 --> 00:38:25,970
Does that ħoss xierqa? >> Mm-HMM. (Ftehim)

499
00:38:25,970 --> 00:38:33,880
Allura avviż li din hija kważi - strutturalment simili ħafna għall-soluzzjoni iterattiv.

500
00:38:33,880 --> 00:38:38,200
Huwa biss li minflok recursing, kellna loop waqt.

501
00:38:38,200 --> 00:38:40,840
U l-każ bażiku hawn fejn siġra ma null ugwali

502
00:38:40,840 --> 00:38:44,850
kienet il-kundizzjoni li taħtha aħna kissru barra mill-linja waqt.

503
00:38:44,850 --> 00:38:50,200
Huma qed simili ħafna. Iżda aħna qed tmur biex tieħu dan il-pass wieħed ieħor.

504
00:38:50,200 --> 00:38:54,190
Issa, nagħmlu l-istess ħaġa hawn.

505
00:38:54,190 --> 00:38:57,680
Avviż aħna qed jirritornaw l-istess ħaġa f'dawn iż-żewġ linji,

506
00:38:57,680 --> 00:39:00,220
ħlief għal wieħed argument huwa differenti.

507
00:39:00,220 --> 00:39:07,950
Allura aħna qed tmur biex jagħmlu dak ġo tenarji.

508
00:39:07,950 --> 00:39:13,790
I hit xi ħaġa għażla, u għamel simbolu. Okay.

509
00:39:13,790 --> 00:39:21,720
Allura aħna qed tmur biex jirritorna fih dik.

510
00:39:21,720 --> 00:39:28,030
Dan huwa li jkollna jkun linji multipli, ukoll, żżomjati fl huwa.

511
00:39:28,030 --> 00:39:31,060
Normalment, bħala ħaġa stilistika, ma naħsibx ħafna nies

512
00:39:31,060 --> 00:39:38,640
tpoġġi l-ispazju wara l-vleġġa, imma I raden jekk int konsistenti, huwa multa.

513
00:39:38,640 --> 00:39:44,320
Jekk il-valur huwa inqas mill-valur tas-siġar, irridu recurse fuq ix-xellug siġra,

514
00:39:44,320 --> 00:39:53,890
inkella rridu recurse fuq id-dritt tas-siġar.

515
00:39:53,890 --> 00:39:58,610
Allura li kien pass wieħed ta 'kif issir din tfittex iżgħar.

516
00:39:58,610 --> 00:40:02,660
Pass 2 ta 'kif issir din tfittex iżgħar -

517
00:40:02,660 --> 00:40:09,150
nistgħu separati din għal linji multipli.

518
00:40:09,150 --> 00:40:16,500
Okay. Pass 2 ta 'jagħmilha ħarsa iżgħar hija hawnhekk,

519
00:40:16,500 --> 00:40:25,860
sabiex il-valur tar-ritorn ugwali valur siġra, jew ikun fiha kwalunkwe.

520
00:40:25,860 --> 00:40:28,340
>> Din hija ħaġa importanti.

521
00:40:28,340 --> 00:40:30,860
M'inix ċert jekk hu qal li b'mod espliċitu fil-klassi,

522
00:40:30,860 --> 00:40:34,740
iżda huwa msejjaħ short-circuit evalwazzjoni.

523
00:40:34,740 --> 00:40:41,060
L-idea hija valur == valur siġra.

524
00:40:41,060 --> 00:40:49,960
Jekk dan huwa minnu, allura dan huwa minnu, u rridu li "jew" li ma dak kollu li huwa minn hawn.

525
00:40:49,960 --> 00:40:52,520
Allura mingħajr ma jaħsbu dwar dak kollu li huwa minn hawn,

526
00:40:52,520 --> 00:40:55,070
dak li huwa l-espressjoni sħiħa ser jirritornaw?

527
00:40:55,070 --> 00:40:59,430
[Student] Veru? >> Yeah, minħabba vera ta 'xejn,

528
00:40:59,430 --> 00:41:04,990
or'd - or'd jew vera ma xejn huwa neċessarjament il-każ.

529
00:41:04,990 --> 00:41:08,150
Allura hekk kif naraw valur tar-ritorn valur siġra =,

530
00:41:08,150 --> 00:41:10,140
aħna qed biss jmorru lura veru.

531
00:41:10,140 --> 00:41:15,710
Mhux anki tmur recurse aktar fih il-linja.

532
00:41:15,710 --> 00:41:20,980
Nistgħu nkunu dan il-pass wieħed ieħor.

533
00:41:20,980 --> 00:41:29,490
Siġra Ritorn ma null ugwali u kollha ta 'dan.

534
00:41:29,490 --> 00:41:32,650
Hija għamlitha funzjoni waħda line.

535
00:41:32,650 --> 00:41:36,790
Dan huwa wkoll eżempju ta 'short-circuit evalwazzjoni.

536
00:41:36,790 --> 00:41:40,680
Imma issa huwa l-istess idea -

537
00:41:40,680 --> 00:41:47,320
minflok - hekk jekk siġra ma null ugwali - jew, ukoll,

538
00:41:47,320 --> 00:41:49,580
jekk siġra ma null ugwali, li huwa l-każ ħażin,

539
00:41:49,580 --> 00:41:54,790
jekk siġra ugwali null, allura l-ewwel kundizzjoni se tkun falza.

540
00:41:54,790 --> 00:42:00,550
Allura foloz anded ma 'xi ħaġa se tkun liema?

541
00:42:00,550 --> 00:42:04,640
[Student] Foloz. >> Yeah. Dan huwa l-nofs l-ieħor ta 'ċirkwit qasir evalwazzjoni,

542
00:42:04,640 --> 00:42:10,710
fejn jekk siġra ma null mhux ugwali, allura aħna mhux se anki jmorru -

543
00:42:10,710 --> 00:42:14,930
jew jekk siġra ma null ugwali, allura aħna mhux se jagħmlu valur == valur siġra.

544
00:42:14,930 --> 00:42:17,010
Aħna biss se immedjatament lura falza.

545
00:42:17,010 --> 00:42:20,970
Li huwa importanti, peress li jekk hija ma short-circuit jevalwa,

546
00:42:20,970 --> 00:42:25,860
allura jekk siġra ma null ugwali, din it-tieni kundizzjoni se tort seq,

547
00:42:25,860 --> 00:42:32,510
minħabba siġra-> valur dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Allura dak li. Jista 'jagħmel dan - ċċaqlaq darba fuq.

549
00:42:40,490 --> 00:42:44,840
Din hija ħaġa komuni ħafna wkoll, ma tkunx qed tagħmel din il-linja 1 ma 'dan,

550
00:42:44,840 --> 00:42:49,000
iżda hija ħaġa komuni fil-kondizzjonijiet, forsi mhux dritt hawn,

551
00:42:49,000 --> 00:42:59,380
imma jekk (! siġra = NULL, u siġra-> valur == valur), jagħmlu dak kollu.

552
00:42:59,380 --> 00:43:01,560
Din hija kundizzjoni komuni ħafna, fejn minflok li

553
00:43:01,560 --> 00:43:06,770
li jiksru dan f'żewġ IFs, fejn tixtieq, hija l-null siġra?

554
00:43:06,770 --> 00:43:11,780
Okay, mhuwiex null, hekk issa huwa l-valur siġra ugwali għall-valur? Agħmel dan.

555
00:43:11,780 --> 00:43:17,300
Minflok, din il-kundizzjoni, dan qatt ma se seg tort

556
00:43:17,300 --> 00:43:21,220
minħabba li se break out jekk dan jiġri li jkun null.

557
00:43:21,220 --> 00:43:24,000
Well, I raden jekk siġra tiegħek huwa pointer kompletament invalidu, xorta tista seg tort,

558
00:43:24,000 --> 00:43:26,620
iżda ma jistax seg tort jekk siġra huwa null.

559
00:43:26,620 --> 00:43:32,900
Kieku kien null, ikun break out qabel ma inti qatt dereferenced-pointer fl-ewwel post.

560
00:43:32,900 --> 00:43:35,000
[Student] Huwa dan valutazzjoni għażżien imsejħa?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] evalwazzjoni għażżien hija ħaġa separata.

562
00:43:40,770 --> 00:43:49,880
Evalwazzjoni għażżien huwa aktar simili inti titlob għal xi valur,

563
00:43:49,880 --> 00:43:54,270
inti ssaqsi li jiġi kkalkolat valur, tip ta ', imma inti m'għandekx bżonn dan immedjatament.

564
00:43:54,270 --> 00:43:59,040
Allura sakemm inti fil-fatt bżonn, mhuwiex evalwat.

565
00:43:59,040 --> 00:44:03,920
Dan mhux eżattament l-istess ħaġa, iżda fil-pset Huffman,

566
00:44:03,920 --> 00:44:06,520
jgħid li aħna "lazily" tikteb.

567
00:44:06,520 --> 00:44:08,670
Ir-raġuni nagħmlu dan huwa għaliex aħna qed attwalment lqugħ l write -

568
00:44:08,670 --> 00:44:11,820
aħna ma jridu jiktbu bits individwali fi żmien,

569
00:44:11,820 --> 00:44:15,450
jew bytes individwali kull darba, aħna minflok rridu nġibu blokki ta 'bytes.

570
00:44:15,450 --> 00:44:19,270
Imbagħad ladarba għandna blokki ta 'bytes, allura aħna ser jiktbu out.

571
00:44:19,270 --> 00:44:22,640
Anke jekk inti ssaqsi lilha biex jiktbu - u fwrite u fread jagħmlu l-istess tip ta 'ħaġa.

572
00:44:22,640 --> 00:44:26,260
Huma buffer jaqra tiegħek u jikteb.

573
00:44:26,260 --> 00:44:31,610
Anke jekk inti ssaqsi lilha biex tikteb immedjatament, hija probabbilment mhux se.

574
00:44:31,610 --> 00:44:34,540
U inti ma jistgħux ikunu żguri li l-affarijiet ser ikunu bil-miktub

575
00:44:34,540 --> 00:44:37,540
sakemm inti sejħa hfclose jew kwalunkwe huwa,

576
00:44:37,540 --> 00:44:39,620
li mbagħad jgħid, okay, jien għeluq file tiegħi,

577
00:44:39,620 --> 00:44:43,450
dan ifisser I d aħjar tikteb kollox I ma jkunux miktuba s'issa.

578
00:44:43,450 --> 00:44:45,770
Hija l-ebda ħtieġa li tikteb kollox barra

579
00:44:45,770 --> 00:44:49,010
sakemm inti qed jagħlqu l-fajl, u mbagħad jeħtieġ li.

580
00:44:49,010 --> 00:44:56,220
Hekk li jinsab biss dak għażżien - huwa tistenna sakemm għandu jiġri.

581
00:44:56,220 --> 00:44:59,990
Dan - jieħu 51 u tkun taf tmur fis dan f'aktar dettall,

582
00:44:59,990 --> 00:45:05,470
minħabba OCaml u kollox fil-51, kollox huwa recursion.

583
00:45:05,470 --> 00:45:08,890
M'hemm l-ebda iterattiv soluzzjonijiet, bażikament.

584
00:45:08,890 --> 00:45:11,550
Kollox huwa recursion, u l-evalwazzjoni għażżien

585
00:45:11,550 --> 00:45:14,790
se tkun importanti għal-lott ta 'ċirkostanzi

586
00:45:14,790 --> 00:45:19,920
fejn, jekk inti ma lazily tevalwa, dan ikun ifisser -

587
00:45:19,920 --> 00:45:24,760
L-eżempju huwa flussi, li huma infinitament twil.

588
00:45:24,760 --> 00:45:30,990
Fit-teorija, inti tista 'taħseb-numri naturali bħala nixxiegħa ta' 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Affarijiet Allura lazily evalwati huma multa.

590
00:45:33,090 --> 00:45:37,210
Jekk jiena ngħid irrid in-numru 10, imbagħad I tista 'tevalwa san-numru 10.

591
00:45:37,210 --> 00:45:40,300
Jekk irrid in-numru mija, imbagħad I tista 'tevalwa san-numru mija.

592
00:45:40,300 --> 00:45:46,290
Mingħajr evalwazzjoni għażżien, allura huwa għaddej biex tipprova tevalwa numri kollha immedjatament.

593
00:45:46,290 --> 00:45:50,000
Int evalwazzjoni numri infinitament ħafna, u li jinsab biss mhux possibbli.

594
00:45:50,000 --> 00:45:52,080
Allura hemm ħafna ta 'ċirkostanzi fejn għażżien evalwazzjoni

595
00:45:52,080 --> 00:45:57,840
huwa biss essenzjali li jkollna affarijiet għax-xogħol.

596
00:45:57,840 --> 00:46:05,260
>> Issa rridu li tikteb daħħal fejn daħħal se tkun

597
00:46:05,260 --> 00:46:08,430
bl-istess mod jinbidlu fid-definizzjoni.

598
00:46:08,430 --> 00:46:10,470
Allura issa dritt huwa daħħal bool (valur int).

599
00:46:10,470 --> 00:46:23,850
Aħna ser jibdlu dik li daħħal bool (int valur, node * siġar).

600
00:46:23,850 --> 00:46:29,120
Aħna fil-fatt se jibdlu dan mill-ġdid fi ftit, aħna ser tara għaliex.

601
00:46:29,120 --> 00:46:32,210
U ejja jimxu build_node, biss għall-Heck ta 'dan,

602
00:46:32,210 --> 00:46:36,730
hawn daħħal hekk aħna ma jkollhom jiktbu prototip funzjoni.

603
00:46:36,730 --> 00:46:42,450
Liema huwa ħjiel li int ser tkun qed tuża build_node fl daħħal.

604
00:46:42,450 --> 00:46:49,590
Okay. Ħu minuta għal dan.

605
00:46:49,590 --> 00:46:52,130
I think I ffrankati r-reviżjoni jekk inti tixtieq li pull minn dan,

606
00:46:52,130 --> 00:47:00,240
jew, għall-inqas, I ma issa.

607
00:47:00,240 --> 00:47:04,190
I riedu waqfa żgħira biex jaħsbu dwar il-loġika ta 'daħħal,

608
00:47:04,190 --> 00:47:08,750
jekk inti ma tista 'taħseb dan.

609
00:47:08,750 --> 00:47:12,860
Bażikament, inti biss qatt jiġu inseriti fil-weraq.

610
00:47:12,860 --> 00:47:18,640
Bħal, jekk I daħħal 1, allura jien inevitabbilment ser ikunu inseriti 1 -

611
00:47:18,640 --> 00:47:21,820
I ser bidla għall-iswed - I'll jiġu inseriti 1 hawn fuq.

612
00:47:21,820 --> 00:47:28,070
Jew jekk I daħħal 4, nixtieq li jkun ddaħħal 4 hawn fuq.

613
00:47:28,070 --> 00:47:32,180
Allura l-ebda kwistjoni dak li inti tagħmel, int se tkun ddaħħal fil-weraq.

614
00:47:32,180 --> 00:47:36,130
Kulma għandek tagħmel huwa jtenni r-siġra sakemm ikollok il-node

615
00:47:36,130 --> 00:47:40,890
li għandha tkun ġenitur l-node, il-ġenitur l-node ġdid,

616
00:47:40,890 --> 00:47:44,560
u mbagħad bidla pointer xellug jew id-dritt tagħha, jiddependi fuq jekk

617
00:47:44,560 --> 00:47:47,060
huwa akbar minn jew inqas mill-node kurrenti.

618
00:47:47,060 --> 00:47:51,180
Bidla li pointer għall-punt li node ġdida tiegħek.

619
00:47:51,180 --> 00:48:05,490
Allura ttenni r-siġra, jagħmlu l-punt weraq tal-node ġdid.

620
00:48:05,490 --> 00:48:09,810
Ukoll jaħsbu dwar għaliex li tipprojbixxi t-tip ta 'sitwazzjoni qabel,

621
00:48:09,810 --> 00:48:17,990
fejn I mibnija l-siġra binarju fejn kien korrett

622
00:48:17,990 --> 00:48:19,920
jekk inti biss ħares lejn node wieħed,

623
00:48:19,920 --> 00:48:24,830
imma 9 kien fuq ix-xellug ta '7 jekk inti tenna l isfel it-triq kollha.

624
00:48:24,830 --> 00:48:29,770
Allura dak impossibbli f'dan ix-xenarju, peress li -

625
00:48:29,770 --> 00:48:32,530
jaħsbu dwar ddaħħal 9 jew xi ħaġa; fl-node ewwel,

626
00:48:32,530 --> 00:48:35,350
Jien ser tara 7 u jien biss se jmorru lejn il-lemin.

627
00:48:35,350 --> 00:48:38,490
Allura l-ebda kwistjoni dak I do, jekk jien ddaħħal billi tmur werqa,

628
00:48:38,490 --> 00:48:40,790
u biex werqa permezz tal-algoritmu xierqa,

629
00:48:40,790 --> 00:48:43,130
li għaddej biex tkun impossibbli għalija li daħħal 9 ix-xellug ta '7

630
00:48:43,130 --> 00:48:48,250
għaliex malli I hit 7 jien ser imorru lejn il-lemin.

631
00:48:59,740 --> 00:49:02,070
Ħadd ma jkollu xi ħaġa li tibda bil?

632
00:49:02,070 --> 00:49:05,480
[Student] I do. >> Sure.

633
00:49:05,480 --> 00:49:09,200
[Student, mhux intelliġibbli]

634
00:49:09,200 --> 00:49:14,390
[Student ieħor, mhux intelliġibbli]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Huwa apprezzat. Okay. Trid jispjegaw?

636
00:49:18,330 --> 00:49:20,690
>> [Student] Peress li nafu li konna ddaħħal

637
00:49:20,690 --> 00:49:24,060
punti strateġiċi ġodda fl-aħħar tas-siġra,

638
00:49:24,060 --> 00:49:28,070
I looped permezz tal-siġra iteratively

639
00:49:28,070 --> 00:49:31,360
sakemm sibt li node li indikat null.

640
00:49:31,360 --> 00:49:34,220
U mbagħad I iddeċieda li tqiegħed lilha jew fuq il-lemin jew ix-xellug

641
00:49:34,220 --> 00:49:37,420
jużaw dan il-varjabbli id-dritt; dan qalli fejn li tqiegħed lilha.

642
00:49:37,420 --> 00:49:41,850
U mbagħad, essenzjalment, I biss magħmula li l-aħħar -

643
00:49:41,850 --> 00:49:47,520
dan il-punt node temperatura għall-node ġdid li kien joħloq,

644
00:49:47,520 --> 00:49:50,770
jew fuq ix-xellug jew fuq il-lemin, jiddependi fuq dak il-valur id-dritt kien.

645
00:49:50,770 --> 00:49:56,530
Fl-aħħarnett, I stabbilit il-valur node ġdid għall-valur tal-ittestjar tagħha.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Okay, so I ara waħda kwistjoni.

647
00:49:59,550 --> 00:50:02,050
Dan huwa simili 95% tal-mod hemmhekk.

648
00:50:02,050 --> 00:50:07,550
Il-kwistjoni waħda li nara, ukoll, ma xi ħadd ieħor tara kwistjoni?

649
00:50:07,550 --> 00:50:18,400
X'inhu l-ċirkustanza li taħtha break out tal-linja?

650
00:50:18,400 --> 00:50:22,100
[Student] Jekk temperatura huwa null? >> Yeah. Allura kif inti break out tal-linja hija jekk temperatura hija nulla.

651
00:50:22,100 --> 00:50:30,220
Imma x'għandi nagħmel dritt hawn?

652
00:50:30,220 --> 00:50:35,410
I dereference temperatura, li huwa inevitabbilment null.

653
00:50:35,410 --> 00:50:39,840
Allura l-ħaġa oħra li għandek bżonn tagħmel huwa mhux biss iżommu kont sakemm temperatura huwa null,

654
00:50:39,840 --> 00:50:45,590
inti tixtieq li żżomm rekord tal-ġenitur fil-ħinijiet kollha.

655
00:50:45,590 --> 00:50:52,190
Aħna rridu wkoll ġenitur * node, I raden aħna nkunu nistgħu nżommu dak in null fl-ewwel.

656
00:50:52,190 --> 00:50:55,480
Dan huwa se jkollu l-imġiba stramb għall-għerq tal-siġra,

657
00:50:55,480 --> 00:50:59,210
iżda aħna ser jiksbu għal dak.

658
00:50:59,210 --> 00:51:03,950
Jekk il-valur ikun akbar minn kwalunkwe, allura d-dritt temperatura temperatura =.

659
00:51:03,950 --> 00:51:07,910
Iżda qabel ma nagħmlu dan, ġenitur = temperatura.

660
00:51:07,910 --> 00:51:14,500
Jew li huma ġenituri dejjem se temperatura ugwali? Huwa li l-każ?

661
00:51:14,500 --> 00:51:19,560
Jekk temperatura ma huwiex null, allura jien ser jinżel, irrelevanti x'inhu,

662
00:51:19,560 --> 00:51:24,030
għal node li għalih temperatura hija l-ġenitur.

663
00:51:24,030 --> 00:51:27,500
Allura ġenitur għaddej biex tkun temperatura, u mbagħad I jimxu temperatura isfel.

664
00:51:27,500 --> 00:51:32,410
Issa temperatura hija nulla, iżda jinnota prinċipali għall-ġenitur tal-ħaġa li hija nulla.

665
00:51:32,410 --> 00:51:39,110
Allura stabbiliti hawn, jien ma jridux stabbilit id-dritt huwa ugwali għal 1.

666
00:51:39,110 --> 00:51:41,300
So I mċaqalqa lejn il-lemin, hekk jekk id-dritt = 1,

667
00:51:41,300 --> 00:51:45,130
u I raden inti tixtieq ukoll li tagħmel -

668
00:51:45,130 --> 00:51:48,530
jekk inti tmur lejn ix-xellug, inti tixtieq li twaqqaf id-dritt ugwali għal 0.

669
00:51:48,530 --> 00:51:55,950
Jew inkella jekk inti qatt timxi lejn il-lemin.

670
00:51:55,950 --> 00:51:58,590
Allura dritt = 0. Jekk id-dritt = 1,

671
00:51:58,590 --> 00:52:04,260
issa irridu li l-ġenitur newnode pointer dritt,

672
00:52:04,260 --> 00:52:08,520
inkella irridu li l-ġenitur newnode pointer xellug.

673
00:52:08,520 --> 00:52:16,850
Mistoqsijiet dwar li?

674
00:52:16,850 --> 00:52:24,880
Okay. Allura dan huwa l-mod aħna - ukoll, fil-fatt, minflok tagħmel dan,

675
00:52:24,880 --> 00:52:29,630
aħna 1/2 mistennija biex tuża build_node.

676
00:52:29,630 --> 00:52:40,450
U mbagħad jekk newnode ugwali null, ritorn foloz.

677
00:52:40,450 --> 00:52:44,170
Dak li. Issa, dan huwa dak li aħna mistennija li inti tagħmel.

678
00:52:44,170 --> 00:52:47,690
>> Dan huwa dak li s-soluzzjonijiet Persunal tagħhom jagħmlu.

679
00:52:47,690 --> 00:52:52,360
Ma naqbilx ma 'dan bħala l-"dritt" mod ta' għaddej dwar dan

680
00:52:52,360 --> 00:52:57,820
iżda dan huwa perfettament multa u se taħdem.

681
00:52:57,820 --> 00:53:02,840
Ħaġa waħda thats dritt stramb ftit issa huwa

682
00:53:02,840 --> 00:53:08,310
jekk l-siġra jibda off bħala null, aħna jgħaddu fil-siġra null.

683
00:53:08,310 --> 00:53:12,650
I raden jiddependi fuq kif inti tiddefinixxi l-imġiba ta tgħaddi fil-siġra null.

684
00:53:12,650 --> 00:53:15,490
Jiena naħseb li jekk inti tgħaddi fil-siġra null,

685
00:53:15,490 --> 00:53:17,520
mbagħad ddaħħal il-valur fis-siġra null

686
00:53:17,520 --> 00:53:23,030
għandhom biss ritorn siġra fejn il-valur biss hija li node wieħed.

687
00:53:23,030 --> 00:53:25,830
In-nies jaqblu ma 'dak? Inti tista ', jekk int riedu,

688
00:53:25,830 --> 00:53:28,050
jekk inti tgħaddi fil-siġra null

689
00:53:28,050 --> 00:53:31,320
u inti tixtieq li daħħal il-valur fis dan, ritorn foloz.

690
00:53:31,320 --> 00:53:33,830
Huwa sa inti biex jiddefinixxu dik.

691
00:53:33,830 --> 00:53:38,320
Biex tagħmel l-ewwel ħaġa li għidt u mbagħad -

692
00:53:38,320 --> 00:53:40,720
tajjeb, int ser jkollhom problemi tagħmel dan, minħabba li

693
00:53:40,720 --> 00:53:44,090
ikun aktar faċli jekk kellna pointer globali għall-ħaġa,

694
00:53:44,090 --> 00:53:48,570
iżda aħna ma, hekk jekk siġra huwa null, m'hemm xejn li nistgħu nagħmlu dwar dan.

695
00:53:48,570 --> 00:53:50,960
Nistgħu biss ritorn foloz.

696
00:53:50,960 --> 00:53:52,840
Allura jien se jibdlu daħħal.

697
00:53:52,840 --> 00:53:56,540
Aħna teknikament jista 'biss bidla dan id-dritt hawn,

698
00:53:56,540 --> 00:53:58,400
kif huwa iterazzjoni fuq affarijiet,

699
00:53:58,400 --> 00:54:04,530
imma jien se jibdlu daħħal tieħu node ** siġra.

700
00:54:04,530 --> 00:54:07,510
Pointers Double.

701
00:54:07,510 --> 00:54:09,710
Xi jfisser dan?

702
00:54:09,710 --> 00:54:12,330
Minflok li jittrattaw ma pointers għal punti strateġiċi,

703
00:54:12,330 --> 00:54:16,690
il-ħaġa jien ser tkun manipulazzjoni hija din pointer.

704
00:54:16,690 --> 00:54:18,790
Jien ser tkun manipulazzjoni dan il-werrej.

705
00:54:18,790 --> 00:54:21,770
Jien ser tkun manipulazzjoni pointers direttament.

706
00:54:21,770 --> 00:54:25,760
Dan jagħmel sens għaliex, jaħsbu dwar down -

707
00:54:25,760 --> 00:54:33,340
ukoll, id-dritt issa dan jipponta lejn null.

708
00:54:33,340 --> 00:54:38,130
Dak li nixtieq tagħmel hu li jimmanipulaw dan pointer għall-punt li ma null.

709
00:54:38,130 --> 00:54:40,970
Irrid li punt li node ġdida tiegħi.

710
00:54:40,970 --> 00:54:44,870
Jekk I biss iżommu rekord ta 'indikaturi għall-pointers tiegħi,

711
00:54:44,870 --> 00:54:47,840
imbagħad I m'għandhomx bżonn li jżommu rekord ta 'pointer ġenitur.

712
00:54:47,840 --> 00:54:52,640
I tista 'sempliċement iżommu kont biex tara jekk il-pointer hija li tipponta lejn null,

713
00:54:52,640 --> 00:54:54,580
u jekk il-pointer hija li tipponta lejn null,

714
00:54:54,580 --> 00:54:57,370
bidla għall-punt li l-node nixtieq.

715
00:54:57,370 --> 00:55:00,070
U nista 'bidla dan peress I jkollhom pointer għall-pointer.

716
00:55:00,070 --> 00:55:02,040
Ejja naraw dan id-dritt issa.

717
00:55:02,040 --> 00:55:05,470
Inti tista 'attwalment jagħmlu dan recursively pjuttost faċilment.

718
00:55:05,470 --> 00:55:08,080
Do rridu nagħmlu dan?

719
00:55:08,080 --> 00:55:10,980
Iva, nagħmlu.

720
00:55:10,980 --> 00:55:16,790
>> Ejja naraw dan recursively.

721
00:55:16,790 --> 00:55:24,070
L-ewwel, dak li huwa każ ta 'bażi ​​tagħna se tkun?

722
00:55:24,070 --> 00:55:29,140
Kważi dejjem il-każ bażi tagħna, imma fil-fatt, dan huwa tip ta 'delikata.

723
00:55:29,140 --> 00:55:34,370
L-ewwelnett, jekk (== NULL siġra)

724
00:55:34,370 --> 00:55:37,550
I raden aħna qed biss jmorru lura falza.

725
00:55:37,550 --> 00:55:40,460
Din hija differenti minn null siġra tkun tiegħek.

726
00:55:40,460 --> 00:55:44,510
Dan huwa l-pointer li għerq pointer tiegħek qed null

727
00:55:44,510 --> 00:55:48,360
li jfisser li pointer għerq tiegħek ma teżistix.

728
00:55:48,360 --> 00:55:52,390
Allura stabbiliti hawn, jekk nagħmel

729
00:55:52,390 --> 00:55:55,760
* node - ejja biss użu mill-ġdid dan.

730
00:55:55,760 --> 00:55:58,960
Node * għerq = NULL,

731
00:55:58,960 --> 00:56:00,730
u mbagħad jien ser sejħa daħħal billi tagħmel xi ħaġa simili,

732
00:56:00,730 --> 00:56:04,540
daħħal 4 fis & għerq.

733
00:56:04,540 --> 00:56:06,560
Allura & għeruq, jekk għerq huwa * node

734
00:56:06,560 --> 00:56:11,170
allura & għerq se jkun hemm ** node.

735
00:56:11,170 --> 00:56:15,120
Dan huwa validu. F'dan il-każ, siġar, l hawn,

736
00:56:15,120 --> 00:56:20,120
siġra ma huwiex null - jew daħħal.

737
00:56:20,120 --> 00:56:24,630
Hawnhekk. Siġra ma huwiex null; * siġra huwa null, li huwa multa

738
00:56:24,630 --> 00:56:26,680
għaliex jekk siġra * huwa null, imbagħad I tista 'timmanipola dan

739
00:56:26,680 --> 00:56:29,210
li issa punt għal dak li nixtieq li għall-punt li.

740
00:56:29,210 --> 00:56:34,750
Imma jekk siġra huwa null, dan ifisser I biss niżlet hawn u qal null.

741
00:56:34,750 --> 00:56:42,710
Dan ma jagħmilx sens. I ma tistax tagħmel xejn ma 'dak.

742
00:56:42,710 --> 00:56:45,540
Jekk siġra huwa null, ritorn foloz.

743
00:56:45,540 --> 00:56:48,220
So I bażikament diġà qal dak il-każ tagħna bażi reali huwa.

744
00:56:48,220 --> 00:56:50,580
U dak hu li se jkun?

745
00:56:50,580 --> 00:56:55,030
[Student, mhux intelliġibbli]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Iva. Mela jekk (* siġra == NULL).

747
00:57:00,000 --> 00:57:04,520
Dan jirrigwarda l-każ hawn fuq

748
00:57:04,520 --> 00:57:09,640
fejn jekk pointer aħmar tiegħi huwa l-pointer jien iffukat fuq,

749
00:57:09,640 --> 00:57:12,960
hekk bħal jien iffukat fuq dan il-werrej, issa jien iffukat fuq dan il-werrej.

750
00:57:12,960 --> 00:57:15,150
Issa jien iffukat fuq dan il-werrej.

751
00:57:15,150 --> 00:57:18,160
Mela jekk pointer aħmar tiegħi, li hija ** node tiegħi,

752
00:57:18,160 --> 00:57:22,880
huwa dejjem - jekk *, pointer aħmar tiegħi, huwa qatt null,

753
00:57:22,880 --> 00:57:28,470
dan ifisser li jien fil-każ fejn jien jiffoka fuq pointer li l-punti -

754
00:57:28,470 --> 00:57:32,530
dan huwa pointer li jappartjeni għal werqa.

755
00:57:32,530 --> 00:57:41,090
Irrid li jibdlu dan il-werrej li jindika node ġdida tiegħi.

756
00:57:41,090 --> 00:57:45,230
Come lura fuq hawn.

757
00:57:45,230 --> 00:57:56,490
Newnode tiegħi se jkun biss node * n = build_node (valur)

758
00:57:56,490 --> 00:58:07,300
allura n, jekk n = NULL, ritorn foloz.

759
00:58:07,300 --> 00:58:12,600
Else irridu li jibdlu dak il-pointer bħalissa tipponta lejn

760
00:58:12,600 --> 00:58:17,830
li issa punt għal node mibnijin ġodda tagħna.

761
00:58:17,830 --> 00:58:20,280
Nistgħu attwalment jagħmlu dan hawn.

762
00:58:20,280 --> 00:58:30,660
Minflok qal n, ngħidu * siġra = jekk * siġra.

763
00:58:30,660 --> 00:58:35,450
Kulħadd jifhem li? Illi jittrattaw pointers għal pointers,

764
00:58:35,450 --> 00:58:40,750
nistgħu nbiddlu pointers nulla għall-punt li l-affarijiet li rridu lilhom għall-punt li.

765
00:58:40,750 --> 00:58:42,820
Li każ bażi tagħna.

766
00:58:42,820 --> 00:58:45,740
>> Issa rikorrenza tagħna, jew recursion tagħna,

767
00:58:45,740 --> 00:58:51,430
se tkun simili ħafna għal kull recursions oħra aħna kont qed tagħmel.

768
00:58:51,430 --> 00:58:55,830
Aħna ser tixtieq li daħħal il-valur,

769
00:58:55,830 --> 00:58:59,040
u issa jien ser tuża tlett fibri darb'oħra, iżda dak li hu kundizzjoni tagħna se tkun?

770
00:58:59,040 --> 00:59:05,180
X'inhu aħna qed tfittex li jiddeċiedu jekk irridu li jmorru lemin jew xellug?

771
00:59:05,180 --> 00:59:07,760
Ejja nagħmlu dan fil-passi separati.

772
00:59:07,760 --> 00:59:18,850
Jekk (valur <) liema?

773
00:59:18,850 --> 00:59:23,200
[Student] Valur-siġra tal-?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Mela ftakar li jien bħalissa -

775
00:59:27,490 --> 00:59:31,260
[Studenti, mhux intelliġibbli]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Yeah, hekk dritt hawn, ejja ngħidu li din aħdar vleġġa

777
00:59:34,140 --> 00:59:39,050
huwa eżempju ta 'dak li siġra bħalissa hu, huwa pointer għal dan il-werrej.

778
00:59:39,050 --> 00:59:46,610
Allura dan ifisser I am a pointer għal pointer sa 3.

779
00:59:46,610 --> 00:59:48,800
Il dereference darbtejn tinstema tajba.

780
00:59:48,800 --> 00:59:51,010
What do I - kif nista 'nagħmlu dan?

781
00:59:51,010 --> 00:59:53,210
[Student] Dereference darba, u mbagħad jagħmlu vleġġa li mod?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Mela (* siġra) huwa l-dereference darba, -> valur

783
00:59:58,420 --> 01:00:05,960
huwa ser jagħti lili l-valur tal-node li jien indirettament tipponta lejn.

784
01:00:05,960 --> 01:00:11,980
So I tista 'wkoll tikteb ** tree.value jekk tippreferi li.

785
01:00:11,980 --> 01:00:18,490
Jew xogħlijiet.

786
01:00:18,490 --> 01:00:26,190
Jekk dan huwa l-każ, allura nixtieq li sejħa daħħal il-valur.

787
01:00:26,190 --> 01:00:32,590
U dak li huwa node aġġornata tiegħi ** se tkun?

788
01:00:32,590 --> 01:00:39,440
Irrid immur lejn ix-xellug, sabiex ** tree.left se tkun ix-xellug tiegħi.

789
01:00:39,440 --> 01:00:41,900
U Irrid li l-pointer għal dak ħaġa

790
01:00:41,900 --> 01:00:44,930
b'tali mod li jekk ix-xellug jispiċċa jkun l-pointer null,

791
01:00:44,930 --> 01:00:48,360
I jista 'jimmodifika din għall-punt li node ġdida tiegħi.

792
01:00:48,360 --> 01:00:51,460
>> U l-każ l-ieħor jista 'jkun simili ħafna.

793
01:00:51,460 --> 01:00:55,600
Ejja fil-fatt jagħmlu dan ternarji tiegħi dritt issa.

794
01:00:55,600 --> 01:01:04,480
Daħħal il-valur jekk il-valur <(** siġra). Valur.

795
01:01:04,480 --> 01:01:11,040
Imbagħad irridu li taġġorna ** tagħna lejn ix-xellug,

796
01:01:11,040 --> 01:01:17,030
inkella irridu li taġġorna ** tagħna lejn il-lemin.

797
01:01:17,030 --> 01:01:22,540
[Student] Does li jiksbu l-pointer għall-pointer?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Ftakar li - ** tree.right hija stilla node.

799
01:01:30,940 --> 01:01:35,040
[Student, mhux intelliġibbli] >> Yeah.

800
01:01:35,040 --> 01:01:41,140
** Tree.right hija bħal dan il-werrej jew xi ħaġa.

801
01:01:41,140 --> 01:01:45,140
Allura billi jittieħed pointer għal dan, li tagħti me dak li nixtieq

802
01:01:45,140 --> 01:01:50,090
ta 'l-pointer għal dak Guy.

803
01:01:50,090 --> 01:01:54,260
[Student] Jista immorru aktar mill-ġdid għaliex aħna qed jużaw l-pointers 2?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Yeah. Allura - l-ebda, inti tista ', u din is-soluzzjoni qabel

805
01:01:58,220 --> 01:02:04,540
kien mod ta 'kif isir dan mingħajr ma jsir 2 pointers.

806
01:02:04,540 --> 01:02:08,740
Inti jeħtieġ li tkun kapaċi jifhmu jużaw żewġ pointers,

807
01:02:08,740 --> 01:02:11,660
u din hija soluzzjoni aktar nadifa.

808
01:02:11,660 --> 01:02:16,090
Ukoll, avviż li, x'jiġri jekk siġra tiegħi -

809
01:02:16,090 --> 01:02:24,480
x'jiġri jekk għerq tiegħi kien null? X'jiġri jekk jien tagħmel dan il-każ id-dritt hawn?

810
01:02:24,480 --> 01:02:30,540
Allura node * għerq = NULL, daħħal 4 fis & għerq.

811
01:02:30,540 --> 01:02:35,110
X'inhu għerq se tkun wara dan?

812
01:02:35,110 --> 01:02:37,470
[Student, mhux intelliġibbli] >> Yeah.

813
01:02:37,470 --> 01:02:41,710
Valur Root se tkun 4.

814
01:02:41,710 --> 01:02:45,510
Xellug Root se tkun nulla, id-dritt għerq se tkun nulla.

815
01:02:45,510 --> 01:02:49,490
Fil-każ fejn aħna ma jgħaddu għeruq mill-indirizz,

816
01:02:49,490 --> 01:02:52,490
aħna ma setgħux jimmodifikaw għerq.

817
01:02:52,490 --> 01:02:56,020
Fil-każ fejn l-siġra - fejn għerq kien null,

818
01:02:56,020 --> 01:02:58,410
aħna biss kellhom jirritornaw falza. M'hemm xejn stajna nagħmlu.

819
01:02:58,410 --> 01:03:01,520
Ma nistgħux daħħal node fi siġra vojta.

820
01:03:01,520 --> 01:03:06,810
Imma issa nistgħu; aħna biss tagħmel siġra vojta ġo siġra waħda node.

821
01:03:06,810 --> 01:03:13,400
Liema normalment huwa l-mod mistenni li huwa suppost li taħdem.

822
01:03:13,400 --> 01:03:21,610
>> Barra minn hekk, dan huwa ferm iqsar minn

823
01:03:21,610 --> 01:03:26,240
wkoll iżżomm rekord tal-ġenitur, u għalhekk inti jtenni l isfel it-triq kollha.

824
01:03:26,240 --> 01:03:30,140
Issa għandi ġenitur tiegħi, u jien biss ikollhom ġenitur dritt tiegħi pointer għall-kwalunkwe.

825
01:03:30,140 --> 01:03:35,640
Minflok, jekk aħna ma dan iteratively, huwa d jkun l-istess idea ma 'linja waqt.

826
01:03:35,640 --> 01:03:38,100
Iżda minflok li biex jittrattaw ma 'pointer ġenitur tiegħi,

827
01:03:38,100 --> 01:03:40,600
minflok pointer kurrenti tiegħi jkun il-ħaġa

828
01:03:40,600 --> 01:03:43,790
li jien direttament timmodifika għall-punt li node ġdida tiegħi.

829
01:03:43,790 --> 01:03:46,090
I ma jkollhomx għalfejn jinnegozjaw ma 'jekk huwa tipponta lejn ix-xellug.

830
01:03:46,090 --> 01:03:48,810
I ma jkollhomx għalfejn jinnegozjaw ma 'jekk huwa tipponta lejn il-lemin.

831
01:03:48,810 --> 01:04:00,860
Huwa biss x'ikun dan il-werrej huwa, jien ser tistabbilixxi li għall-punt li node ġdida tiegħi.

832
01:04:00,860 --> 01:04:05,740
Kulħadd jifhem kif taħdem?

833
01:04:05,740 --> 01:04:09,460
Jekk le għaliex irridu li tagħmel dan il-mod,

834
01:04:09,460 --> 01:04:14,920
iżda għall-inqas li din taħdem bħala soluzzjoni?

835
01:04:14,920 --> 01:04:17,110
[Student] Fejn nerġgħu lura vera?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Li probabbilment dritt hawn.

837
01:04:21,550 --> 01:04:26,690
Jekk aħna korrett daħħalha, ritorn veru.

838
01:04:26,690 --> 01:04:32,010
Inkella, stabbiliti hawn aħna qed tmur jridu jirritornaw prospetti daħħal ikun x'ikun.

839
01:04:32,010 --> 01:04:35,950
>> U x'hemm speċjali dwar din il-funzjoni rikursivi?

840
01:04:35,950 --> 01:04:43,010
Huwa denb rikursivi, dan sakemm aħna jikkompilaw ma 'xi ottimizzazzjoni,

841
01:04:43,010 --> 01:04:48,060
se jirrikonoxxu dan u qatt mhu ser tikseb overflow munzell minn dan,

842
01:04:48,060 --> 01:04:53,230
anki jekk siġra tagħna għandu għoli ta '10,000 jew 10 miljun.

843
01:04:53,230 --> 01:04:55,630
[Student, mhux intelliġibbli]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Naħseb tagħmlu fi Dash - jew liema livell ottimizzazzjoni

845
01:05:00,310 --> 01:05:03,820
hija meħtieġa għal recursion denb għandhom ikunu rikonoxxuti.

846
01:05:03,820 --> 01:05:09,350
Naħseb li tirrikonoxxi - GCC u clang

847
01:05:09,350 --> 01:05:12,610
għandhom ukoll tifsiriet differenti għal livelli ottimizzazzjoni tagħhom.

848
01:05:12,610 --> 01:05:17,870
Irrid ngħid huwa DashO 2, għall żgur li se jirrikonoxxu recursion denb.

849
01:05:17,870 --> 01:05:27,880
Iżda aħna - inti tista 'tibni bħal eżempju Fibonocci jew xi ħaġa.

850
01:05:27,880 --> 01:05:30,030
Mhuwiex faċli biex jittestjaw ma 'dan, għaliex dan huwa diffiċli biex jinbena

851
01:05:30,030 --> 01:05:32,600
siġra binarju li hekk kbir.

852
01:05:32,600 --> 01:05:37,140
Iżda yeah, naħseb huwa DashO 2, li

853
01:05:37,140 --> 01:05:40,580
jekk inti tiġbor l DashO 2, se tfittex recursion denb

854
01:05:40,580 --> 01:05:54,030
u jottimizzaw l barra.

855
01:05:54,030 --> 01:05:58,190
Ejja ħa mmorru lura għall - daħħal l litteralment l-aħħar ħaġa li għandha bżonn.

856
01:05:58,190 --> 01:06:04,900
Ejja ħa mmorru lura għall-insert hawn fuq

857
01:06:04,900 --> 01:06:07,840
fejn aħna qed tmur biex jagħmlu l-istess idea.

858
01:06:07,840 --> 01:06:14,340
Hija ser għad għandhom il-difett li ma jkunux jistgħu kompletament jimmaniġġjaw

859
01:06:14,340 --> 01:06:17,940
meta l-għerq innifsu huwa null, jew id-dħul fil-passat huwa null,

860
01:06:17,940 --> 01:06:20,060
iżda minflok li jittrattaw ma 'pointer ġenitur,

861
01:06:20,060 --> 01:06:27,430
ejja japplikaw l-istess loġika ta 'indikaturi żamma għall pointers.

862
01:06:27,430 --> 01:06:35,580
Jekk hawn inżommu node tagħna ** kur,

863
01:06:35,580 --> 01:06:37,860
u aħna ma bżonn li jżommu rekord ta 'dritt aktar,

864
01:06:37,860 --> 01:06:47,190
iżda node ** kur = & siġra.

865
01:06:47,190 --> 01:06:54,800
U issa loop filwaqt tagħna se tkun waqt kur * ma null ugwali.

866
01:06:54,800 --> 01:07:00,270
M'għandekx bżonn biex iżżomm kont tal-ġenituri aktar.

867
01:07:00,270 --> 01:07:04,180
M'għandekx bżonn biex iżżomm kont ta xellug u lemin.

868
01:07:04,180 --> 01:07:10,190
U jien ser sejħa dan temperatura, għaliex aħna qed diġà jużaw temperatura.

869
01:07:10,190 --> 01:07:17,200
Okay. Mela jekk (valur> * temperatura),

870
01:07:17,200 --> 01:07:24,010
allura & (* temperatura) -> dritt

871
01:07:24,010 --> 01:07:29,250
inkella temperatura = & (* temperatura) -> xellug.

872
01:07:29,250 --> 01:07:32,730
U issa, f'dan il-punt, wara dan loop filwaqt li,

873
01:07:32,730 --> 01:07:36,380
I biss tagħmel dan minħabba forsi huwa aktar faċli li wieħed jaħseb dwar iteratively minn recursively,

874
01:07:36,380 --> 01:07:39,010
iżda wara dan loop filwaqt li,

875
01:07:39,010 --> 01:07:43,820
* Temperatura hija l-pointer li rridu bidla.

876
01:07:43,820 --> 01:07:48,960
>> Qabel kellna ġenitur, u ridna li jibdlu kull ġenitur xellug jew ġenitur lemin,

877
01:07:48,960 --> 01:07:51,310
imma jekk irridu li jibdlu id-dritt ġenitur,

878
01:07:51,310 --> 01:07:54,550
allura * temperatura huwa dritt ġenitur, u nistgħu nbiddlu direttament.

879
01:07:54,550 --> 01:08:05,860
Allura stabbiliti hawn, nistgħu nagħmlu * temperatura = newnode, u li hu.

880
01:08:05,860 --> 01:08:09,540
Allura l-avviż, kull għamilna f'din kien tieħu linji ta 'kodiċi.

881
01:08:09,540 --> 01:08:14,770
Sabiex iżżomm kont ta 'l-ġenitur fil dak kollu li hu sforz addizzjonali.

882
01:08:14,770 --> 01:08:18,689
Hawnhekk, jekk aħna biss iżommu rekord ta 'l-pointer għall-pointer,

883
01:08:18,689 --> 01:08:22,990
u anki jekk ridna li teħles minn dawn ċineg kaboċċi issa,

884
01:08:22,990 --> 01:08:27,170
jagħmluha ħarsa iqsar.

885
01:08:27,170 --> 01:08:32,529
Dan issa huwa l-istess soluzzjoni eżatta,

886
01:08:32,529 --> 01:08:38,210
iżda linji inqas ta 'kodiċi.

887
01:08:38,210 --> 01:08:41,229
Ladarba inti tibda tirrikonoxxi dan bħala soluzzjoni valida,

888
01:08:41,229 --> 01:08:43,529
huwa wkoll aktar faċli biex raġuni dwar minn simili, okay,

889
01:08:43,529 --> 01:08:45,779
għaliex għandi din il-bandiera fuq id-dritt int?

890
01:08:45,779 --> 01:08:49,290
X'ifisser dan? Oh, huwa li jfisser li

891
01:08:49,290 --> 01:08:51,370
kull darba mmur id-dritt, I ħtieġa li stabbilixxa din,

892
01:08:51,370 --> 01:08:53,819
inkella jekk immur xellug I ħtieġa li jiġu stabbiliti għal żero.

893
01:08:53,819 --> 01:09:04,060
Hawnhekk, jien ma jkollhom raġuni dwar dan; huwa biss aktar faċli li wieħed jaħseb dwar.

894
01:09:04,060 --> 01:09:06,710
Mistoqsijiet?

895
01:09:06,710 --> 01:09:16,290
[Student, mhux intelliġibbli] >> Yeah.

896
01:09:16,290 --> 01:09:23,359
Okay, hekk fil-aħħar bit -

897
01:09:23,359 --> 01:09:28,080
I raden funzjoni waħda ta 'malajr u faċli li nistgħu nagħmlu huwa,

898
01:09:28,080 --> 01:09:34,910
let's - flimkien, I raden, tipprova u jiktbu fiha funzjoni

899
01:09:34,910 --> 01:09:38,899
li ma care jekk huwa siġra tfittxija binarja.

900
01:09:38,899 --> 01:09:43,770
Dan fih il-funzjoni għandha tirritorna vera

901
01:09:43,770 --> 01:09:58,330
jekk kullimkien fl din is-siġra binarju ġenerali huwa l-valur li aħna qed tfittex.

902
01:09:58,330 --> 01:10:02,520
Mela ejja 1 tagħmel dan recursively u mbagħad aħna ser tagħmel dan iteratively.

903
01:10:02,520 --> 01:10:07,300
Nistgħu attwalment biss tagħmel dan flimkien, għaliex dan se tkun verament qasir.

904
01:10:07,300 --> 01:10:11,510
>> X'inhu każ bażiku tiegħi se tkun?

905
01:10:11,510 --> 01:10:13,890
[Student, mhux intelliġibbli]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Mela jekk (== NULL siġra), imbagħad dak?

907
01:10:18,230 --> 01:10:22,740
[Student] Ritorn falza.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Inkella, ukoll, I m'għandhomx bżonn l-ieħor.

909
01:10:26,160 --> 01:10:30,250
Jekk kien każ tiegħi bażi oħra.

910
01:10:30,250 --> 01:10:32,450
Valur [Student] Tree s? >> Yeah.

911
01:10:32,450 --> 01:10:36,430
Mela jekk (valur == siġra> valur.

912
01:10:36,430 --> 01:10:39,920
Avviż aħna qed lura għall * node, mhux node ** i?

913
01:10:39,920 --> 01:10:42,990
Ma fiha qatt se jkollhom bżonn jużaw xi ** node,

914
01:10:42,990 --> 01:10:45,480
peress li aħna ma timmodifika pointers.

915
01:10:45,480 --> 01:10:50,540
Aħna biss jaqsmu magħhom.

916
01:10:50,540 --> 01:10:53,830
Jekk dan iseħħ, allura aħna rridu li jirritornaw veru.

917
01:10:53,830 --> 01:10:58,270
Else irridu li travers-tfal.

918
01:10:58,270 --> 01:11:02,620
Allura ma nistgħux raġuni dwar jekk kollox lejn ix-xellug huwa inqas

919
01:11:02,620 --> 01:11:05,390
u kollox lejn il-lemin huwa akbar.

920
01:11:05,390 --> 01:11:09,590
Allura x'inhu kondizzjoni tagħna se jkun hawn - jew, liema huma aħna se jagħmlu?

921
01:11:09,590 --> 01:11:11,840
[Student, mhux intelliġibbli] >> Yeah.

922
01:11:11,840 --> 01:11:17,400
Ritorn fih (valur, siġra-> xellug)

923
01:11:17,400 --> 01:11:26,860
jew fiha (valur, siġra-> lemin). U li dan.

924
01:11:26,860 --> 01:11:29,080
U l-avviż li hemm xi evalwazzjoni ta 'ċirkwit qasir,

925
01:11:29,080 --> 01:11:32,520
fejn jekk aħna jiġri li jsibu l-valur fil-siġra xellug,

926
01:11:32,520 --> 01:11:36,820
aħna qatt bżonn li nħarsu lejn l-siġra dritt.

927
01:11:36,820 --> 01:11:40,430
Dik hija l-funzjoni sħiħa.

928
01:11:40,430 --> 01:11:43,690
Issa ejja tagħmel dan iteratively,

929
01:11:43,690 --> 01:11:48,060
li se tkun anqas sbieħ.

930
01:11:48,060 --> 01:11:54,750
Aħna ser tieħu l-bidu tas-soltu ta node * kur = siġra.

931
01:11:54,750 --> 01:12:03,250
Filwaqt li (kur! = NULL).

932
01:12:03,250 --> 01:12:08,600
Malajr se tara problema.

933
01:12:08,600 --> 01:12:12,250
Jekk kur - hawn, jekk aħna qatt break out ta 'dan,

934
01:12:12,250 --> 01:12:16,020
allura konna jispiċċaw ta 'affarijiet li tħares lejn, hekk ritorn foloz.

935
01:12:16,020 --> 01:12:24,810
Jekk (kur-> valur == valur), jirritorna veru.

936
01:12:24,810 --> 01:12:32,910
Allura issa, aħna f'post -

937
01:12:32,910 --> 01:12:36,250
ma nafux jekk irridu li jmorru lemin jew xellug.

938
01:12:36,250 --> 01:12:44,590
Allura arbitrarju, ejja biss jmorru xellug.

939
01:12:44,590 --> 01:12:47,910
Stajt ovvjament run fis kwistjoni fejn stajt kompletament abbandunat kollox -

940
01:12:47,910 --> 01:12:50,760
I se biss qatt jiċċekkja fuq ix-xellug ta 'siġra.

941
01:12:50,760 --> 01:12:56,050
I qatt se jiċċekkja xi ħaġa li huwa tifel dritt ta 'xejn.

942
01:12:56,050 --> 01:13:00,910
Kif nista jiffissaw dan?

943
01:13:00,910 --> 01:13:05,260
[Student] Int għandek iżżomm kont ta 'ix-xellug u tal-lemin fil-munzell.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Yeah. Mela ejja jagħmilha

945
01:13:13,710 --> 01:13:32,360
Struct lista, node * n, u mbagħad node ** jmiss?

946
01:13:32,360 --> 01:13:40,240
Naħseb li xogħlijiet multa.

947
01:13:40,240 --> 01:13:45,940
Aħna rridu li jmorru fuq ix-xellug, jew let's - up here.

948
01:13:45,940 --> 01:13:54,350
= Struct lista lista, li ser tibda

949
01:13:54,350 --> 01:13:58,170
fil din il-lista Struct.

950
01:13:58,170 --> 01:14:04,040
* Lista = NULL. Allura li għaddej biex tkun lista linked tagħna

951
01:14:04,040 --> 01:14:08,430
ta subtrees li għandna skipped fuq.

952
01:14:08,430 --> 01:14:13,800
Aħna ser travers xellug issa,

953
01:14:13,800 --> 01:14:17,870
iżda peress li aħna inevitabbilment bżonn li jiġu lura lejn il-lemin,

954
01:14:17,870 --> 01:14:26,140
Aħna ser iżżomm il-lemin ta 'ġewwa tal-lista Struct tagħna.

955
01:14:26,140 --> 01:14:32,620
Imbagħad aħna ser ikollhom new_list jew Struct,

956
01:14:32,620 --> 01:14:41,080
Struct lista *, new_list = malloc (sizeof (lista)).

957
01:14:41,080 --> 01:14:44,920
Jien ser jinjoraw żbalji kkontrollat ​​li, iżda inti għandek tikkontrolla biex tara jekk huwa null.

958
01:14:44,920 --> 01:14:50,540
New_list-node li għaddej għall-punt li -

959
01:14:50,540 --> 01:14:56,890
oh, hu għalhekk li jien ridt it up here. Huwa ser jiġi ma 'lista Struct 2.

960
01:14:56,890 --> 01:15:02,380
Thats kemm marbuta listi tax-xogħol.

961
01:15:02,380 --> 01:15:04,810
Dan huwa l-istess bħala lista int marbut

962
01:15:04,810 --> 01:15:06,960
ħlief aħna qed biss tissostitwixxi int ma * node.

963
01:15:06,960 --> 01:15:11,040
Huwa eżattament l-istess.

964
01:15:11,040 --> 01:15:15,100
Allura new_list, il-valur tal-node new_list tagħna,

965
01:15:15,100 --> 01:15:19,120
se tkun kur->-dritt.

966
01:15:19,120 --> 01:15:24,280
Il-valur ta 'tagħna new_list-> jmiss se tkun lista oriġinali tagħna,

967
01:15:24,280 --> 01:15:30,760
u allura aħna qed tmur biex taġġorna lista tagħna għall-punt li new_list.

968
01:15:30,760 --> 01:15:33,650
>> Issa għandna bżonn xi tip ta 'mod ta' affarijiet ġbid,

969
01:15:33,650 --> 01:15:37,020
bħal aħna għandna traversat l subtree xellug kollu.

970
01:15:37,020 --> 01:15:40,480
Issa għandna bżonn biex tiġbed Jittieħed barra minnu,

971
01:15:40,480 --> 01:15:43,850
bħal kur huwa null; aħna ma jridux biss jirritornaw falza.

972
01:15:43,850 --> 01:15:50,370
Aħna rridu li issa jiġbdu barra mill-lista l-ġdida tagħna.

973
01:15:50,370 --> 01:15:53,690
A mod konvenjenti ta 'kif isir dan - ukoll, fil-fatt, hemm diversi modi ta' kif isir dan.

974
01:15:53,690 --> 01:15:56,680
Kull min ikollu suġġeriment?

975
01:15:56,680 --> 01:15:58,790
Fejn I għandha tagħmel dan jew kif I għandhom jagħmlu dan?

976
01:15:58,790 --> 01:16:08,010
Aħna biss ftit minuti, imma xi suġġerimenti?

977
01:16:08,010 --> 01:16:14,750
Minflok - mod wieħed, minflok il-kundizzjoni tagħna qed waqt,

978
01:16:14,750 --> 01:16:17,090
dak li aħna bħalissa qed tħares lejn mhux null,

979
01:16:17,090 --> 01:16:22,340
minflok aħna qed tmur biex tkompli tmur sakemm lista tagħna nnifisha hija nulla.

980
01:16:22,340 --> 01:16:25,680
Mela jekk lista tagħna jispiċċa jkun null,

981
01:16:25,680 --> 01:16:30,680
allura għandna jispiċċaw ta 'affarijiet biex tfittex, tfittex fuq.

982
01:16:30,680 --> 01:16:39,860
Iżda dan ifisser li l-ewwel ħaġa fil-lista tagħna huwa biss se tkun l-node ewwel.

983
01:16:39,860 --> 01:16:49,730
L-ewwel ħaġa se jkun - aħna m'għadx bżonn biex tara dak.

984
01:16:49,730 --> 01:16:58,710
Allura lista-> n se jkun siġra tagħna.

985
01:16:58,710 --> 01:17:02,860
lista-> jmiss se tkun nulla.

986
01:17:02,860 --> 01:17:07,580
U issa filwaqt lista ma null ugwali.

987
01:17:07,580 --> 01:17:11,610
Kur se jiġbdu xi ħaġa mill-lista tagħna.

988
01:17:11,610 --> 01:17:13,500
Allura kur se ugwali lista-> n.

989
01:17:13,500 --> 01:17:20,850
U mbagħad lista se ugwali lista '> n, jew lista'>. Li jmiss

990
01:17:20,850 --> 01:17:23,480
Mela valur kur jekk ugwali valur.

991
01:17:23,480 --> 01:17:28,790
Issa nistgħu żid kemm pointer dritt tagħna u pointer xellug tagħna

992
01:17:28,790 --> 01:17:32,900
sakemm dawn mhux qed null.

993
01:17:32,900 --> 01:17:36,390
Down hawn, I raden għandna għamlu li fl-ewwel post.

994
01:17:36,390 --> 01:17:44,080
Jekk (kur->-tajjeb! = NULL)

995
01:17:44,080 --> 01:17:56,380
allura aħna ser daħħal dik node fil-lista tagħna.

996
01:17:56,380 --> 01:17:59,290
Jekk (kur-> xellug), din hija xi ftit ta 'xogħol żejjed, iżda huwa multa.

997
01:17:59,290 --> 01:18:02,690
Jekk (kur-> xellug! = NULL),

998
01:18:02,690 --> 01:18:14,310
u aħna qed tmur biex daħħal ix-xellug fil-lista marbuta tagħna,

999
01:18:14,310 --> 01:18:19,700
u li għandhom ikunu fiha.

1000
01:18:19,700 --> 01:18:22,670
Aħna jtenni - sakemm aħna għandna xi ħaġa fil-lista tagħna,

1001
01:18:22,670 --> 01:18:26,640
għandna ieħor node li tħares lejn.

1002
01:18:26,640 --> 01:18:28,920
Allura aħna nħarsu lejn dak node,

1003
01:18:28,920 --> 01:18:31,390
aħna bil-quddiem lista tagħna għal dak li jmiss.

1004
01:18:31,390 --> 01:18:34,060
Jekk dan node huwa l-valur li aħna qed tfittex, nistgħu ritorn vera.

1005
01:18:34,060 --> 01:18:37,640
Else daħħal kemm subtrees xellug u lemin tagħna,

1006
01:18:37,640 --> 01:18:40,510
sakemm dawn mhux qed null, fil-lista tagħna

1007
01:18:40,510 --> 01:18:43,120
sabiex inkunu inevitabbilment jmorru fuqhom.

1008
01:18:43,120 --> 01:18:45,160
Mela jekk dawn ma kinux null,

1009
01:18:45,160 --> 01:18:47,950
jekk pointer għeruq tagħna rrimarka żewġ affarijiet,

1010
01:18:47,950 --> 01:18:51,670
allura fl-ewwel aħna jinġibed xi ħaġa hekk lista tagħna jispiċċa jkun null.

1011
01:18:51,670 --> 01:18:56,890
U allura aħna mressqa żewġ affarijiet lura, hekk issa lista tagħna huwa ta 'daqs 2.

1012
01:18:56,890 --> 01:19:00,030
Imbagħad aħna qed tmur biex loop back-up u aħna qed biss jmorru biex tiġbed,

1013
01:19:00,030 --> 01:19:04,250
ejja ngħidu, il-pointer xellug tal node għerq tagħna.

1014
01:19:04,250 --> 01:19:07,730
U li ser biss iżommu jiġri; aħna ser jispiċċaw looping fuq kollox.

1015
01:19:07,730 --> 01:19:11,280
>> Avviż li dan kien ferm aktar ikkumplikat

1016
01:19:11,280 --> 01:19:14,160
fis-soluzzjoni rikursivi.

1017
01:19:14,160 --> 01:19:17,260
U stajt qal diversi drabi

1018
01:19:17,260 --> 01:19:25,120
li s-soluzzjoni rikursivi normalment għandha ħafna in komuni mal-iterattiv soluzzjoni.

1019
01:19:25,120 --> 01:19:30,820
Hawn dan huwa eżattament dak li l-soluzzjoni rikursivi qed tagħmel.

1020
01:19:30,820 --> 01:19:36,740
L-unika bidla hi li minflok impliċitament jużaw il-munzell, il-munzell programm,

1021
01:19:36,740 --> 01:19:40,840
bħala mod tiegħek ta 'iżżomm rekord ta' dak li għoqiedi inti xorta jkollok bżonn biex iżuru,

1022
01:19:40,840 --> 01:19:45,430
issa għandek biex espliċitament tuża lista marbuta.

1023
01:19:45,430 --> 01:19:49,070
Fiż-żewġ każijiet, inti qed iżommu rekord ta 'dak node għad irid jiġu viżitati.

1024
01:19:49,070 --> 01:19:51,790
Fil-każ rikursivi huwa biss aktar faċli għaliex munzell

1025
01:19:51,790 --> 01:19:57,100
hija implimentata għalik bħala l-munzell programm.

1026
01:19:57,100 --> 01:19:59,550
Avviż li din il-lista marbuta, huwa munzell.

1027
01:19:59,550 --> 01:20:01,580
Tkun xi tkun aħna biss jitqiegħed fuq il-munzell

1028
01:20:01,580 --> 01:20:09,960
huwa immedjatament dak li aħna qed tmur biex pull off-munzell li jżuru jmiss.

1029
01:20:09,960 --> 01:20:14,380
Aħna tardiv, iżda xi mistoqsijiet?

1030
01:20:14,380 --> 01:20:23,530
[Student, mhux intelliġibbli]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Yeah. Mela jekk ikollna lista linked tagħna,

1032
01:20:27,790 --> 01:20:30,150
attwali se punt għal dan Guy,

1033
01:20:30,150 --> 01:20:34,690
u issa aħna qed biss avvanz lista linked tagħna li tiffoka fuq dan Guy.

1034
01:20:34,690 --> 01:20:44,200
Aħna qed jaqsmu fuq il-lista marbut f'dik il-linja.

1035
01:20:44,200 --> 01:20:51,200
U allura I raden għandna ħielsa lista linked tagħna u l-għalf

1036
01:20:51,200 --> 01:20:53,880
darba qabel jirritornaw vera jew falza, għandna bżonn li

1037
01:20:53,880 --> 01:20:57,360
jtenni fuq lista marbuta tagħna u dejjem stabbiliti hawn, I raden,

1038
01:20:57,360 --> 01:21:03,900
jekk aħna cur dritt ma jkunx ugwali għal, żid dan, hekk issa irridu ħielsa

1039
01:21:03,900 --> 01:21:09,600
kur għaliex, ukoll, aħna ma kompletament tinsa dwar il-lista? Yeah.

1040
01:21:09,600 --> 01:21:12,880
Allura dak hu li rridu nagħmlu hawnhekk.

1041
01:21:12,880 --> 01:21:16,730
Fejn hi l-pointer?

1042
01:21:16,730 --> 01:21:23,320
Kur kien imbagħad - irridu li lista Struct * 10 ugwali lista li jmiss.

1043
01:21:23,320 --> 01:21:29,240
Lista Ħieles, lista = temperatura.

1044
01:21:29,240 --> 01:21:32,820
U fil-każ fejn nerġgħu lura minnu, aħna ma bżonn li jtenni

1045
01:21:32,820 --> 01:21:37,050
tul il-bqija tal-lista linked tagħna ħelsien affarijiet.

1046
01:21:37,050 --> 01:21:39,700
Il-ħaġa sbieħ dwar is-soluzzjoni rikursivi hi ħelsien affarijiet

1047
01:21:39,700 --> 01:21:44,930
ifisser biss factorings popping barra mill-munzell li se jiġri għalik.

1048
01:21:44,930 --> 01:21:50,720
Allura aħna ħadthom marret minn xi ħaġa li huwa simili 3 linji ta 'hard-to-think-kodiċi dwar

1049
01:21:50,720 --> 01:21:57,520
għal xi ħaġa li hija sinifikament aktar ħafna hard-to-think-dwar linji ta 'kodiċi.

1050
01:21:57,520 --> 01:22:00,620
Kwalunkwe aktar mistoqsijiet?

1051
01:22:00,620 --> 01:22:08,760
Kull dritt. Aħna qed tajba. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]