1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [7.pants: ērtāku]

2
00:00:02,770 --> 00:00:05,090
[Robs Bowden] [Hārvarda]

3
00:00:05,090 --> 00:00:07,930
[Tas ir CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Labi. Tātad, piemēram, es teicu manu e-pastu,

5
00:00:10,110 --> 00:00:14,060
Tas būs bināro koku intensīva sadaļā.

6
00:00:14,060 --> 00:00:16,820
Bet tur nav nemaz tik daudz jautājumu.

7
00:00:16,820 --> 00:00:18,920
Tāpēc mēs esam gatavojas izmēģināt un izņemt katru jautājumu

8
00:00:18,920 --> 00:00:25,430
un iedziļināties sāpīgu detalizācijas visiem labākajiem veidiem, kā to lietas.

9
00:00:25,430 --> 00:00:31,200
Tik labi sākumā, mēs iet cauri izlases zīmējumiem divkāršo koku un stuff.

10
00:00:31,200 --> 00:00:35,970
Tātad šeit, "Atceries, ka bināro koks ir mezglu līdzīgi saistītajā sarakstā,

11
00:00:35,970 --> 00:00:38,150
izņemot nevis vienu rādītāju ir divi: viens par kreisi "bērns"

12
00:00:38,150 --> 00:00:41,950
un viens par pareizo "bērnu". "

13
00:00:41,950 --> 00:00:45,630
Tātad bināro koks ir tāpat kā saistīts saraksts,

14
00:00:45,630 --> 00:00:47,910
izņemot struct gatavojas ir divas norādes.

15
00:00:47,910 --> 00:00:51,390
Tur trinary koki, kas drīzumā ir trīs norādes,

16
00:00:51,390 --> 00:00:56,540
ir N-ary koki, kas tikko ir generic rādītāju

17
00:00:56,540 --> 00:01:00,320
ka jums tad ir malloc pietiekami liela, lai būtu

18
00:01:00,320 --> 00:01:04,840
pietiekami norādes uz visām iespējamām bērniem.

19
00:01:04,840 --> 00:01:08,200
Tik bināro koku vienkārši notiek, ir pastāvīgs skaits divi.

20
00:01:08,200 --> 00:01:11,260
Ja jūs vēlaties, jūs varat dot saistītu sarakstu kā unary koku,

21
00:01:11,260 --> 00:01:15,360
bet es nedomāju, ka kāds to nosauc par to.

22
00:01:15,360 --> 00:01:18,060
"Zīmēt kastes-un-bultas diagramma bināro koku mezglā

23
00:01:18,060 --> 00:01:24,110
satur Nate mīļāko numuru, 7, kur katrs bērns rādītājs ir nulle. "

24
00:01:24,110 --> 00:01:27,780
Tātad iPad režīmā.

25
00:01:27,780 --> 00:01:30,280
>> Tas būs diezgan vienkārši.

26
00:01:30,280 --> 00:01:36,150
Mēs esam tikai nāksies mezglu, es izdarīt to kā kvadrātu.

27
00:01:36,150 --> 00:01:38,730
Un es izdarīt vērtības šeit.

28
00:01:38,730 --> 00:01:41,090
Tā vērtība iet šeit,

29
00:01:41,090 --> 00:01:44,770
un tad uz leju šeit mums būs kreiso pa kreisi rādītāju un labo rādītāju uz labo pusi.

30
00:01:44,770 --> 00:01:50,430
Un tas ir ļoti daudz, tāpēc konvencija, lai izsauktu to pa kreisi un pa labi, rādītājs vārdi.

31
00:01:50,430 --> 00:01:52,460
Abi šie ir būs nulle.

32
00:01:52,460 --> 00:01:57,870
Tas būs tikai nulle, un tas būs tikai nulle.

33
00:01:57,870 --> 00:02:03,630
Labi. Tātad atpakaļ šeit.

34
00:02:03,630 --> 00:02:05,700
"Ar saistīts saraksts, mums bija tikai, lai uzglabātu rādītāju

35
00:02:05,700 --> 00:02:09,639
uz pirmo mezglu sarakstu, lai atcerēties visu saistīts saraksts, vai visu sarakstu.

36
00:02:09,639 --> 00:02:11,650
Tāpat ar kokiem, mums ir tikai uzglabāt rādītāju

37
00:02:11,650 --> 00:02:13,420
ar vienu mezglu, lai atcerēties visu koku.

38
00:02:13,420 --> 00:02:15,980
Šis mezgls ir calle par "saknes" no koka.

39
00:02:15,980 --> 00:02:18,320
Balstīties uz tavām no pirms vai izdarīt jaunu

40
00:02:18,320 --> 00:02:21,690
tā, ka jums ir kastes-un-bultas tēlojums bināro koku

41
00:02:21,690 --> 00:02:25,730
ar vērtību 7, tad 3 kreisi,

42
00:02:25,730 --> 00:02:32,760
tad 9 par tiesībām, 6 un pēc tam labajā pusē 3. "

43
00:02:32,760 --> 00:02:34,810
Redzēsim, vai es varu atcerēties visu, kas manā galvā.

44
00:02:34,810 --> 00:02:37,670
Tātad tas būs mūsu saknes šeit.

45
00:02:37,670 --> 00:02:41,600
Mums būs sava rādītāju kaut kur, kaut kas mēs saucam saknes,

46
00:02:41,600 --> 00:02:45,140
un tas norāda uz šo puisis.

47
00:02:45,140 --> 00:02:48,490
Tagad, lai padarītu jaunu mezglu,

48
00:02:48,490 --> 00:02:52,870
Ko mums ir, 3 pa kreisi?

49
00:02:52,870 --> 00:02:57,140
Tik jaunu mezglu ar 3, un tas sākotnēji norāda Null.

50
00:02:57,140 --> 00:02:59,190
Es ņemšu tikai izvirzīti N.

51
00:02:59,190 --> 00:03:02,250
Tagad mēs vēlamies, lai tas iet pa kreisi no 7.

52
00:03:02,250 --> 00:03:06,840
Tāpēc mēs mainīt šo rādītāju, lai tagad norādīt uz šo puisi.

53
00:03:06,840 --> 00:03:12,420
Un mēs paši. Mēs vēlamies 9 nekā šeit

54
00:03:12,420 --> 00:03:14,620
kas sākotnēji vienkārši saka null.

55
00:03:14,620 --> 00:03:19,600
Mēs ejam, lai mainītu šo rādītāju, norādiet uz 9,

56
00:03:19,600 --> 00:03:23,310
un tagad mēs vēlamies likt 6 tiesībām uz 3.

57
00:03:23,310 --> 00:03:32,170
Tātad tas notiek - veikt 6.

58
00:03:32,170 --> 00:03:34,310
Un tas puisis būs punkts tur.

59
00:03:34,310 --> 00:03:38,320
Labi. Tā ka viss tas mūs aicina darīt.

60
00:03:38,320 --> 00:03:42,770
>> Tagad iesim pa kādu terminoloģiju.

61
00:03:42,770 --> 00:03:46,690
Mēs jau runājām par to, kā no koka sakne ir top-visvairāk mezglu kokā.

62
00:03:46,690 --> 00:03:54,720
Viens satur 7. Apakšā koku mezgli sauc lapas.

63
00:03:54,720 --> 00:04:01,240
Jebkurā mezglā, kas tāpat ir Null, jo tās bērniem ir lapa.

64
00:04:01,240 --> 00:04:03,680
Tātad tas ir iespējams, ja mūsu bināro koku ir tikai viens mezgls,

65
00:04:03,680 --> 00:04:10,130
ka koks ir lapas, un tas arī viss.

66
00:04:10,130 --> 00:04:12,060
"Ar" augstums "no koka ir numurs apiņu jums ir veikt

67
00:04:12,060 --> 00:04:16,620
lai saņemtu no augšas uz lapu. "

68
00:04:16,620 --> 00:04:18,640
Mēs nokļūt, jo otrkārt, starpību

69
00:04:18,640 --> 00:04:21,940
starp līdzsvarotus un nesabalansēta bināro koku,

70
00:04:21,940 --> 00:04:29,470
bet tagad, kopējais augstums šo koku

71
00:04:29,470 --> 00:04:34,520
Es teiktu, ir 3, lai gan, ja jūs saskaitīt apiņu

72
00:04:34,520 --> 00:04:39,710
jums ir veikt, lai iegūtu līdz 9, tad tas tiešām ir tikai augstumu no 2.

73
00:04:39,710 --> 00:04:43,340
Tieši tagad tas ir nelīdzsvarota binārs koks,

74
00:04:43,340 --> 00:04:49,840
bet mēs runājām par līdzsvarots, kad tā kļūst par būtiskiem.

75
00:04:49,840 --> 00:04:52,040
Tātad tagad mēs varam runāt par punktiem kokā ziņā

76
00:04:52,040 --> 00:04:54,700
salīdzinot ar citiem mezgliem kokā.

77
00:04:54,700 --> 00:04:59,730
Tāpēc tagad mums ir vecāki, bērni, brāļi un māsas, senči, un pēcnācējus.

78
00:04:59,730 --> 00:05:05,650
Tie ir diezgan saprātīgi, ko tie nozīmē.

79
00:05:05,650 --> 00:05:09,610
Ja mēs jautājam - tas ir vecākiem.

80
00:05:09,610 --> 00:05:12,830
Tātad, kas ir no 3 mātes?

81
00:05:12,830 --> 00:05:16,090
[Studentiem] 7. >> Jā. Vecāks ir tikai būs ko norāda uz jums.

82
00:05:16,090 --> 00:05:20,510
Tad kādi ir 7 bērni?

83
00:05:20,510 --> 00:05:23,860
[Studenti] 3 un 9. >> Jā.

84
00:05:23,860 --> 00:05:26,460
Ievērojiet, ka "bērni" burtiski nozīmē bērni,

85
00:05:26,460 --> 00:05:31,010
tāpēc 6 netika piemērota, jo tā ir kā mazbērns.

86
00:05:31,010 --> 00:05:35,540
Bet tad, ja mēs ejam pēcnācējus, tā, kādi ir gada 7 pēcteči?

87
00:05:35,540 --> 00:05:37,500
[Studenti] 3, 6 un 9. >> Jā.

88
00:05:37,500 --> 00:05:42,330
No saknes mezgla pēcteči būs viss kokā,

89
00:05:42,330 --> 00:05:47,950
izņemot varbūt saknes mezglu pats, ja jūs nevēlaties, lai uzskatītu, ka pēcnācējs.

90
00:05:47,950 --> 00:05:50,750
Un visbeidzot, senči, tāpēc tas ir pretējā virzienā.

91
00:05:50,750 --> 00:05:55,740
Tātad, kādi ir par 6 senči?

92
00:05:55,740 --> 00:05:58,920
[Studenti] 3 un 7. >> Jā. 9 nav iekļauti.

93
00:05:58,920 --> 00:06:02,520
Tas ir tikai tiešais ciltsrakstiem atpakaļ uz saknes

94
00:06:02,520 --> 00:06:13,230
būs jūsu senči.

95
00:06:13,230 --> 00:06:16,300
>> "Mēs sakām, ka bināro koks" pasūtīts ", ja par katru mezglu koka,

96
00:06:16,300 --> 00:06:19,530
visi tās pēcnācēji pa kreisi ir mazāk vērtības

97
00:06:19,530 --> 00:06:22,890
un visi par tiesībām tiem ir lielākas vērtības.

98
00:06:22,890 --> 00:06:27,060
Piemēram, koku iepriekš pasūtīt, taču tas nav vienīgais iespējamais sakārtotas. "

99
00:06:27,060 --> 00:06:30,180
Pirms mēs nokļūt, ka,

100
00:06:30,180 --> 00:06:36,420
pasūtīts bināro koku ir arī pazīstams kā bināro meklēšanas koku.

101
00:06:36,420 --> 00:06:38,660
Šeit mēs gadās būt aicinot to sakārtotu bināro koku,

102
00:06:38,660 --> 00:06:41,850
bet es nekad neesmu dzirdējis to sauc pasūtīts bināro koku pirms,

103
00:06:41,850 --> 00:06:46,650
un uz viktorīnas mēs esam daudz vairāk varētu ievietot bināro meklēšanas koku.

104
00:06:46,650 --> 00:06:49,250
Viņi viens un tas pats,

105
00:06:49,250 --> 00:06:54,580
un tas ir svarīgi atpazīt atšķirību starp bināro koku un binārā meklēšanas koku.

106
00:06:54,580 --> 00:06:58,830
Binārs koks ir tikai koks, kas norāda uz divām lietām.

107
00:06:58,830 --> 00:07:02,120
Katrs mezgls norāda uz divām lietām.

108
00:07:02,120 --> 00:07:06,310
Nav par tām vērtībām, kas tas norāda uz argumentāciju.

109
00:07:06,310 --> 00:07:11,370
Tātad patīk vairāk nekā šeit, jo tas ir bināro meklēšanas koku,

110
00:07:11,370 --> 00:07:14,030
mēs zinām, ka, ja mēs aiziet pa kreisi no 7,

111
00:07:14,030 --> 00:07:16,670
tad visas vērtības, ko mēs varam, iespējams sasniegt

112
00:07:16,670 --> 00:07:19,310
ejot pa kreisi gada 7 jābūt vismaz 7.

113
00:07:19,310 --> 00:07:24,070
Ievērojiet, ka visi mazāk nekā 7 vērtības ir 3 un 6.

114
00:07:24,070 --> 00:07:26,040
Tie visi ir pa kreisi no 7.

115
00:07:26,040 --> 00:07:29,020
Ja mēs ejam uz tiesībām 7, viss ir lielāks par 7,

116
00:07:29,020 --> 00:07:33,220
tāpēc 9 ir pa labi no 7, tāpēc mēs esam labi.

117
00:07:33,220 --> 00:07:36,150
Šis nav gadījums bināro koku,

118
00:07:36,150 --> 00:07:40,020
regulāro bināro koku mēs varam vienkārši ir 3 augšā, 7 pa kreisi,

119
00:07:40,020 --> 00:07:47,630
9 kreisi no 7; tur nav vērtības whatsoever pasūtīšanu.

120
00:07:47,630 --> 00:07:56,140
Tagad mēs faktiski darīt, jo tas ir garlaicīgs un nevajadzīgs,

121
00:07:56,140 --> 00:07:59,400
bet "mēģināt izdarīt tik daudz pasūtītās koki, kā jūs varat iedomāties

122
00:07:59,400 --> 00:08:01,900
izmantojot skaitļus 7, 3, 9, 6 un.

123
00:08:01,900 --> 00:08:06,800
Cik atšķirīgas kārtība ir tur? Kāda ir katras augstums? "

124
00:08:06,800 --> 00:08:10,480
>> Mēs darīsim pāris, bet galvenā ideja ir,

125
00:08:10,480 --> 00:08:16,530
tas nekādā veidā unikāla reprezentācija bināro koku satur šīs vērtības.

126
00:08:16,530 --> 00:08:22,760
Viss, kas mums nepieciešams, ir dažas binārs koks, kas satur 7, 3, 6, 9 un.

127
00:08:22,760 --> 00:08:25,960
Cits iespējams derīga viena būtu sakne ir 3,

128
00:08:25,960 --> 00:08:30,260
iet pa kreisi un tas ir 6, dodieties pa kreisi un tas ir 7,

129
00:08:30,260 --> 00:08:32,730
iet pa kreisi un tas ir 9.

130
00:08:32,730 --> 00:08:36,169
Tas ir pilnīgi derīgs bināro meklēšanas koku.

131
00:08:36,169 --> 00:08:39,570
Tas nav ļoti noderīgs, jo tas ir tāpat kā saistīts saraksts

132
00:08:39,570 --> 00:08:43,750
un visi šie norādes ir tikai Null.

133
00:08:43,750 --> 00:08:48,900
Bet tas ir derīgs koks. Yeah?

134
00:08:48,900 --> 00:08:51,310
[Studentu] nav vērtības ir lielāks par tiesībām?

135
00:08:51,310 --> 00:08:56,700
Vai tas ir -? >> Tie es gribēju iet citu ceļu.

136
00:08:56,700 --> 00:09:00,960
Pastāv arī - jā, pieņemsim pāriet kas.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Labs loms.

138
00:09:07,770 --> 00:09:11,730
Tā joprojām ir jāpakļaujas kāda bināro koku meklēšana ir paredzēts darīt.

139
00:09:11,730 --> 00:09:15,650
Tātad viss pa kreisi, ir mazāks nekā jebkurā mezglā.

140
00:09:15,650 --> 00:09:23,180
Mēs varētu vienkārši pāriet, teiksim, šo 6 un nodot to šeit.

141
00:09:23,180 --> 00:09:26,880
Nē, mēs nevaram. Kāpēc es glabāt darot, ka?

142
00:09:26,880 --> 00:09:35,350
Darīsim - šeit ir 6, šeit ir 7, 6 punkti līdz 3.

143
00:09:35,350 --> 00:09:39,290
Tas ir vēl derīga bināro meklēšanas koku.

144
00:09:39,290 --> 00:09:49,260
Kas ir nepareizi, ja es - pieņemsim redzēt, ja es varētu nākt klajā ar vienošanos.

145
00:09:49,260 --> 00:09:52,280
Jā, labi. Tātad, kas ir nepareizi ar šo koku?

146
00:09:52,280 --> 00:10:08,920
Es domāju, es esmu jau devis mājienu, ka kaut kas nav kārtībā ar to.

147
00:10:08,920 --> 00:10:14,430
Kāpēc es glabāt darot, ka?

148
00:10:14,430 --> 00:10:18,510
Labi. Tas izskatās saprātīgs.

149
00:10:18,510 --> 00:10:22,590
Ja mēs skatāmies uz katru mezglu, piemēram, 7, tad pa kreisi no 7 ir 3.

150
00:10:22,590 --> 00:10:24,960
Tāpēc mums ir 3, lieta tiesībām uz 3 ir 6.

151
00:10:24,960 --> 00:10:27,750
Un, ja paskatās 6, lieta tiesībām uz 6 ir 9.

152
00:10:27,750 --> 00:10:30,910
Tad kāpēc tas nav derīgs bināro meklēšanas koku?

153
00:10:30,910 --> 00:10:36,330
[Studenti] 9 joprojām ir pa kreisi no 7. >> Jā.

154
00:10:36,330 --> 00:10:43,710
Tā ir taisnība, ka visas vērtības jūs varat iespējams sasniegt, ejot pa kreisi no 7 ir mazāk nekā 7.

155
00:10:43,710 --> 00:10:49,120
Ja mēs ejam pa kreisi gada 7, mēs ar 3 un mēs joprojām var saņemt līdz 6,

156
00:10:49,120 --> 00:10:52,520
mēs joprojām var saņemt līdz 9, bet kad viņš bija mazāks nekā 7,

157
00:10:52,520 --> 00:10:55,070
Mums nevajadzētu būt iespējai saņemt uz numuru, kas ir arī lielāks par 7.

158
00:10:55,070 --> 00:10:59,830
Tātad tas nav derīgs bināro meklēšanas koku.

159
00:10:59,830 --> 00:11:02,330
>> Mans brālis tiešām bija intervija jautājumu

160
00:11:02,330 --> 00:11:07,760
ka galvenokārt bija tas, vienkārši kods līdz kaut ko apstiprinātu

161
00:11:07,760 --> 00:11:10,500
vai koks ir binārs meklēšanas koks,

162
00:11:10,500 --> 00:11:13,580
un tā ir pirmā lieta, ko viņš darīja, bija tikai pārbaudīt, lai redzētu

163
00:11:13,580 --> 00:11:17,020
ja pa kreisi un pa labi, ir pareizi, un tad atkārtot tur lejā.

164
00:11:17,020 --> 00:11:19,700
Bet jūs varat ne tikai darīt, jums ir sekot līdzi

165
00:11:19,700 --> 00:11:22,550
par to, ka tagad, es esmu gājusi pa kreisi no 7,

166
00:11:22,550 --> 00:11:26,340
Viss šajā apakškoka jābūt mazākam par 7.

167
00:11:26,340 --> 00:11:28,430
Pareizs algoritms ir sekot līdzi

168
00:11:28,430 --> 00:11:35,970
no robežās, vērtības var, iespējams ietilpst iekšā

169
00:11:35,970 --> 00:11:38,360
Mēs ne iet cauri visiem no tiem.

170
00:11:38,360 --> 00:11:41,630
Ir jauki atkārtošanās saistība,

171
00:11:41,630 --> 00:11:44,810
kaut gan mēs neesam gotten tiem, vai mēs nevarēsim iegūt tiem,

172
00:11:44,810 --> 00:11:47,030
nosakot, cik daudz tur patiesībā ir.

173
00:11:47,030 --> 00:11:53,180
Tātad tur ir 14 no tiem.

174
00:11:53,180 --> 00:11:56,020
Par to, kā jūs varētu to darīt ideja matemātiski ir, piemēram,

175
00:11:56,020 --> 00:11:59,770
Jūs varat izvēlēties jebkuru nevienu būt saknes mezglu,

176
00:11:59,770 --> 00:12:03,160
un tad, ja es paņemu 7 par saknes mezglu,

177
00:12:03,160 --> 00:12:08,150
tad tur ir, teiksim, daži skaitļi, kas var noiet būt mana kreisā mezglā,

178
00:12:08,150 --> 00:12:10,440
un tur ir daži skaitļi, kas var būt manas tiesības mezglā,

179
00:12:10,440 --> 00:12:15,090
bet, ja man ir n kopskaitu, tad summa, kas var iet pa kreisi

180
00:12:15,090 --> 00:12:18,820
pieskaitot summu, kas var iet uz labo pusi, ir n - 1.

181
00:12:18,820 --> 00:12:26,130
Tātad no atlikušajiem skaitļiem, tiem jābūt iespējai doties vai nu pa kreisi vai pa labi.

182
00:12:26,130 --> 00:12:31,580
Šķiet grūti, ka, ja man 3 Pirmais tad viss ir iet pa kreisi,

183
00:12:31,580 --> 00:12:35,080
bet, ja man 7, tad dažas lietas var iet pa kreisi un dažas lietas var iet uz labo pusi.

184
00:12:35,080 --> 00:12:39,570
Un pēc '3 pirmais "Es gribēju viss var aiziet uz labo pusi.

185
00:12:39,570 --> 00:12:42,350
Tas ir ļoti, jums vienkārši ir jādomā par to, kā,

186
00:12:42,350 --> 00:12:47,980
cik daudz lietas var doties uz nākamo līmeni no koka.

187
00:12:47,980 --> 00:12:50,420
Un tas nāk, lai būtu 14 vai jūs varat izdarīt visi no tiem,

188
00:12:50,420 --> 00:12:54,650
un tad jūs saņemsiet 14.

189
00:12:54,650 --> 00:13:01,120
>> Dodas atpakaļ šeit,

190
00:13:01,120 --> 00:13:03,510
"Sakārtoti binārie koki ir foršs, jo mēs varam meklēt caur tiem

191
00:13:03,510 --> 00:13:06,910
ir ļoti līdzīgi kā meklējot pa šķiroto masīvs.

192
00:13:06,910 --> 00:13:10,120
Lai to izdarītu, mēs sākam pie saknes un strādāt mūsu ceļu uz leju koku

193
00:13:10,120 --> 00:13:13,440
uz lapām, pārbaudot katrs mezgls vērtības pret vērtībām mēs meklē.

194
00:13:13,440 --> 00:13:15,810
Ja pašreizējais mezgla vērtība ir mazāka par vērtību, mēs meklējam,

195
00:13:15,810 --> 00:13:18,050
jums iet blakus mezglu labajā bērnu.

196
00:13:18,050 --> 00:13:20,030
Pretējā gadījumā jums iet uz mezglu kreisajā bērnu.

197
00:13:20,030 --> 00:13:22,800
Kādā brīdī, jūs vai nu atrast vērtību jūs meklējat, vai jūs satikt nulli,

198
00:13:22,800 --> 00:13:28,520
norādot vērtību nav kokā. "

199
00:13:28,520 --> 00:13:32,450
Man ir, lai ievilktu koku mums bija pirms; ka ņemšu sekundē.

200
00:13:32,450 --> 00:13:38,280
Bet mēs gribam meklēt vai 6, 10, 1 un ir kokā.

201
00:13:38,280 --> 00:13:49,180
Tātad, ko tas bija, 7, 9, 3, 6. Labi.

202
00:13:49,180 --> 00:13:52,730
Skaitļi jūs vēlaties meklēt, mēs vēlamies meklēt 6.

203
00:13:52,730 --> 00:13:55,440
Kā tas algoritms darbojas?

204
00:13:55,440 --> 00:14:03,040
Nu, mums ir arī dažas saknes rādītāju uz mūsu koku.

205
00:14:03,040 --> 00:14:12,460
Un mēs varētu iet uz saknes un teikt, tas ir vērtība, kas vienāda ar vērtību mēs meklējot?

206
00:14:12,460 --> 00:14:15,000
Tāpēc mēs meklējam 6, tāpēc tas nav vienāds.

207
00:14:15,000 --> 00:14:20,140
Tātad mēs tur notiek, un tagad mēs sakām, labi, tāpēc 6 ir mazāks par 7.

208
00:14:20,140 --> 00:14:23,940
Vai tas nozīmē, ka mēs gribam iet pa kreisi, vai arī mēs gribam iet uz labo pusi?

209
00:14:23,940 --> 00:14:27,340
[Studentu] Left. >> Jā.

210
00:14:27,340 --> 00:14:33,340
Tas ir ievērojami vieglāk, viss, kas jums jādara, ir izdarīt vienu iespējamo mezglu no koka

211
00:14:33,340 --> 00:14:37,760
un tad jūs Don '- nevis mēģināt domāt ar galvu,

212
00:14:37,760 --> 00:14:40,020
labi, ja tas ir mazāk, es varu iet pa kreisi vai doties tiesības,

213
00:14:40,020 --> 00:14:43,030
tikai meklē šo attēlu, tas ir ļoti skaidrs, ka man ir jāiet pa kreisi

214
00:14:43,030 --> 00:14:47,700
ja tas mezgls ir lielāka nekā vērtība, kas es esmu meklē.

215
00:14:47,700 --> 00:14:52,600
Tātad jūs iet pa kreisi, tagad es esmu pie 3.

216
00:14:52,600 --> 00:14:57,770
Es gribu - 3 ir mazāka nekā vērtība Es meklēju, kas ir 6.

217
00:14:57,770 --> 00:15:03,420
Tāpēc mēs ejam pa labi, un tagad es galu galā pie 6,

218
00:15:03,420 --> 00:15:07,380
kas ir vērtība Es meklēju, lai es atgrieztos taisnība.

219
00:15:07,380 --> 00:15:15,760
Nākamais vērtība Es esmu gatavojas meklēt ir 10.

220
00:15:15,760 --> 00:15:23,230
Labi. Tātad 10, tagad, gatavojas - nogrieztu ka - gatavojas sekot saknes.

221
00:15:23,230 --> 00:15:27,670
Tagad, 10 būs lielāks par 7, tāpēc es gribu skatīties pa labi.

222
00:15:27,670 --> 00:15:31,660
Es esmu gatavojas nākt nekā šeit, 10 būs lielāks par 9,

223
00:15:31,660 --> 00:15:34,520
tāpēc es esmu gatavojas vēlas skatīties uz labo pusi.

224
00:15:34,520 --> 00:15:42,100
Es nāku nekā šeit, bet nekā šeit tagad es esmu pie null.

225
00:15:42,100 --> 00:15:44,170
Ko man darīt, ja es hit null?

226
00:15:44,170 --> 00:15:47,440
[Studentu] atgriezties viltus? >> Jā. Es neatradu 10.

227
00:15:47,440 --> 00:15:49,800
1 būs gandrīz identisks gadījums,

228
00:15:49,800 --> 00:15:51,950
izņemot tas ir tikai būs Pagriezts, tā vietā, lai meklē

229
00:15:51,950 --> 00:15:56,540
leju labajā pusē, es esmu gatavojas skatīties pa kreiso flangu.

230
00:15:56,540 --> 00:16:00,430
>> Tagad es domāju, ka mēs faktiski nokļūt kodu.

231
00:16:00,430 --> 00:16:04,070
Lūk, kur - atvērt CS50 iekārtu un virzītos savu ceļu tur,

232
00:16:04,070 --> 00:16:07,010
bet jūs varat arī vienkārši darīt to telpā.

233
00:16:07,010 --> 00:16:09,170
Tas ir iespējams, ideāli to darīt telpā,

234
00:16:09,170 --> 00:16:13,760
jo mēs varam strādāt telpā.

235
00:16:13,760 --> 00:16:19,170
"Vispirms mums ir nepieciešama jauna tipa definīciju bināru koku mezglu satur int vērtības.

236
00:16:19,170 --> 00:16:21,400
Izmantojot Tekstveidnes typedef zemāk,

237
00:16:21,400 --> 00:16:24,510
izveidot jaunu tipa definīciju par mezglu bināro koku.

238
00:16:24,510 --> 00:16:27,930
Ja Jums ir iestrēdzis. . . "Blah, blah, blah. Labi.

239
00:16:27,930 --> 00:16:30,380
Tāpēc pieņemsim likts tekstveidnes šeit,

240
00:16:30,380 --> 00:16:41,630
typedef struktūrai mezglā, un mezglu. Jā, labi.

241
00:16:41,630 --> 00:16:44,270
Tātad, kādi ir lauki, mēs spēsim vēlēties mūsu mezglu?

242
00:16:44,270 --> 00:16:46,520
[Studentu] Int un tad divas norādes?

243
00:16:46,520 --> 00:16:49,700
>> Int vērtība, divas norādes? Kā es varu uzrakstīt norādes?

244
00:16:49,700 --> 00:16:58,440
[Studentu] struct. >> Es tuvinātu iekšā Jā, tā struktūrai mezglā * kreisi,

245
00:16:58,440 --> 00:17:01,320
un struktūrai mezglu * labi.

246
00:17:01,320 --> 00:17:03,460
Un atcerieties apspriedes no pēdējo reizi,

247
00:17:03,460 --> 00:17:15,290
ka šis nav jēgas, tas nav jēgas,

248
00:17:15,290 --> 00:17:18,270
Tas nav jēgas.

249
00:17:18,270 --> 00:17:25,000
Jums ir nepieciešams viss tur, lai definētu šo rekursīvas struct.

250
00:17:25,000 --> 00:17:27,970
Labi, lai tas, ko mūsu koks gatavojas izskatās.

251
00:17:27,970 --> 00:17:37,670
Ja mums bija trinary koks, tad mezglu varētu izskatīties B1, B2, struct mezglā * B3,

252
00:17:37,670 --> 00:17:43,470
kur b ir filiāle - patiesībā, es esmu vairāk dzirdējis tas atstāja, vidējas, labo, bet vienalga.

253
00:17:43,470 --> 00:17:55,610
Mēs tikai rūp binārā, tāpēc labi, pa kreisi.

254
00:17:55,610 --> 00:17:59,110
"Tagad atzīt globālās mezglu * mainīgo par koka saknēm."

255
00:17:59,110 --> 00:18:01,510
Tāpēc mēs nebrauksim, lai to izdarītu.

256
00:18:01,510 --> 00:18:08,950
Lai padarītu lietas nedaudz grūtāk un vairāk vispārināt

257
00:18:08,950 --> 00:18:11,570
mums nebūs globāla mezglu mainīgo.

258
00:18:11,570 --> 00:18:16,710
Tā vietā, jo galvenais mēs deklarēt visus mūsu mezglu lietas,

259
00:18:16,710 --> 00:18:20,500
un tas nozīmē, ka turpmāk, ja mēs sāktu darboties

260
00:18:20,500 --> 00:18:23,130
Mūsu Satur funkcijas un mūsu ievietot funkciju,

261
00:18:23,130 --> 00:18:27,410
vietā no mūsu satur funkcija tikai izmantojot šo globālo mezglā mainīgo,

262
00:18:27,410 --> 00:18:34,280
mēs esam nāksies to pieņemt kā arguments koku ka mēs gribam to apstrādāt.

263
00:18:34,280 --> 00:18:36,650
Ņemot globālā mainīgā bija paredzēts, lai padarītu lietas vieglāk.

264
00:18:36,650 --> 00:18:42,310
Mēs ejam, lai padarītu lietas grūtāk.

265
00:18:42,310 --> 00:18:51,210
Tagad ņemt minūti, vai arī tā vienkārši darīt šāda veida lieta,

266
00:18:51,210 --> 00:18:57,690
kur iekšpusē galvenais vēlaties izveidot šo koku, un tas ir viss, ko vēlaties darīt.

267
00:18:57,690 --> 00:19:04,530
Izmēģiniet un būvēt šo koku savā galvenā funkcija.

268
00:19:42,760 --> 00:19:47,610
>> Labi. Tātad jums nav pat jābūt konstruētām koks visu ceļu vēl.

269
00:19:47,610 --> 00:19:49,840
Bet kāds ir kaut ko es varētu uzvilkt

270
00:19:49,840 --> 00:20:03,130
lai parādītu, kā varētu sākt būvēt šādu koku?

271
00:20:03,130 --> 00:20:08,080
[Studentu] kāda rīvēšanās, mēģinot izkļūt.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Ikviens apmierināti ar savu koku konstrukcijas?

273
00:20:13,100 --> 00:20:15,520
[Studentu] Protams. Tas nav izdarīts. >> Tas ir jauki. Mēs varam tikai pabeigt -

274
00:20:15,520 --> 00:20:26,860
Ak, jūs varat to saglabāt? Urā.

275
00:20:26,860 --> 00:20:32,020
Tāpēc šeit mēs esam - ak, es esmu nedaudz nogriezta.

276
00:20:32,020 --> 00:20:34,770
Es pietuvināto?

277
00:20:34,770 --> 00:20:37,730
Tuvinātu, ritiniet ārā. >> Man ir jautājums. >> Yeah?

278
00:20:37,730 --> 00:20:44,410
[Studentu] Definējot struct, ir lietas, piemēram inicializēts ar kaut ko?

279
00:20:44,410 --> 00:20:47,160
[Bowden] Nē >> Labi. Lai jūs būtu inicializēt -

280
00:20:47,160 --> 00:20:50,450
[Bowden] Nē Ja jums noteikt, vai ja jūs atzīt struct,

281
00:20:50,450 --> 00:20:55,600
tas nav inicializēts pēc noklusējuma, tas ir tāpat kā, ja jūs atzīt int.

282
00:20:55,600 --> 00:20:59,020
Tas ir tieši tas pats. Tas ir tāpat kā katrā no atsevišķiem laukiem

283
00:20:59,020 --> 00:21:04,460
var būt atkritumu vērtība tajā. >> Un tas ir iespējams noteikt - vai atzīt struct

284
00:21:04,460 --> 00:21:07,740
tādā veidā, ka tas sāktu viņiem?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Jā. Tātad, īsceļu inicializācijas sintakse

286
00:21:13,200 --> 00:21:18,660
gatavojas izskatās -

287
00:21:18,660 --> 00:21:22,200
Ir divi veidi, kā mēs varam izdarīt. Es domāju, ka mums vajadzētu sastādīt to

288
00:21:22,200 --> 00:21:25,840
lai pārliecinātos šķindēt arī tas.

289
00:21:25,840 --> 00:21:28,510
Kārtībā argumentiem, kas nāk struct,

290
00:21:28,510 --> 00:21:32,170
jūs likts tik kārtībā argumentiem iekšpusē šo cirtaini lencēm.

291
00:21:32,170 --> 00:21:35,690
Tātad, ja jūs vēlaties, lai sāktu to 9 un pa kreisi tiks anulēts un tad pa labi būt nulle,

292
00:21:35,690 --> 00:21:41,570
tas būtu 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Alternatīva ir, un redaktors nepatīk šo sintaksi,

294
00:21:47,890 --> 00:21:50,300
un tā domā, ka es gribu jaunu bloku,

295
00:21:50,300 --> 00:22:01,800
bet alternatīva ir kaut kas līdzīgs -

296
00:22:01,800 --> 00:22:04,190
šeit, es nolikšu to par jaunu līniju.

297
00:22:04,190 --> 00:22:09,140
Jūs varat skaidri pateikt, es aizmirst precīzu sintaksi.

298
00:22:09,140 --> 00:22:13,110
Tātad jūs varat skaidri jārisina viņus vārdā, un teikt,

299
00:22:13,110 --> 00:22:21,570
. C vai. Vērtība = 9. Kreisi = NULL.

300
00:22:21,570 --> 00:22:24,540
Es esmu guessing tie līdz komatus.

301
00:22:24,540 --> 00:22:29,110
. Labi = NULL, tāpēc šādā veidā jums nav

302
00:22:29,110 --> 00:22:33,780
tiešām ir nepieciešams zināt secību struct,

303
00:22:33,780 --> 00:22:36,650
un, kad jūs lasāt šo, tas ir daudz skaidrāk

304
00:22:36,650 --> 00:22:41,920
par to, ko vērtība ir tiek inicializēts ar.

305
00:22:41,920 --> 00:22:44,080
>> Tas notiek, ir viena no lietām, ka -

306
00:22:44,080 --> 00:22:49,100
tāpēc, lai lielākā daļa, C + + ir superset C.

307
00:22:49,100 --> 00:22:54,160
Jūs varat lietot C kodu, pārvietot to pa C + +, un tas būtu jāapkopo.

308
00:22:54,160 --> 00:22:59,570
Šī ir viena no lietām, ka C + + neatbalsta, tāpēc cilvēki nemēdz darīt.

309
00:22:59,570 --> 00:23:01,850
Es nezinu, ja tas ir vienīgais iemesls, cilvēki nemēdz darīt,

310
00:23:01,850 --> 00:23:10,540
bet gadījumā, ja man vajadzēja to izmantot jāstrādā ar C + + un tāpēc es nevarēju izmantot šo.

311
00:23:10,540 --> 00:23:14,000
Vēl kaut kas piemērs nedarbojas ar C + + ir

312
00:23:14,000 --> 00:23:16,940
Kā malloc atgriež "spēkā neesošs *," tehniski,

313
00:23:16,940 --> 00:23:20,200
bet jūs varētu vienkārši pateikt char * x = malloc neatkarīgi,

314
00:23:20,200 --> 00:23:22,840
un tas automātiski tiks nodotas uz char *.

315
00:23:22,840 --> 00:23:25,450
Ka automātiskā lietie nenotiek C + +.

316
00:23:25,450 --> 00:23:28,150
Tas nav apkopo, un jums būtu skaidri jāpasaka

317
00:23:28,150 --> 00:23:34,510
char *, malloc, neatkarīgi, nodot to uz char *.

318
00:23:34,510 --> 00:23:37,270
Nav daudz lietas, ka C un C + + vienisprātis par,

319
00:23:37,270 --> 00:23:40,620
bet tie ir divi.

320
00:23:40,620 --> 00:23:43,120
Tāpēc mēs iet ar šo sintaksi.

321
00:23:43,120 --> 00:23:46,150
Bet pat tad, ja mums nebūtu iet ar šo sintaksi,

322
00:23:46,150 --> 00:23:49,470
kāda ir - varētu būt nepareizi ar šo?

323
00:23:49,470 --> 00:23:52,170
[Studentu] man nav nepieciešams dereference to? >> Jā.

324
00:23:52,170 --> 00:23:55,110
Atcerieties, ka bulta ir netiešs dereference,

325
00:23:55,110 --> 00:23:58,230
un tad, kad mēs esam tikai nodarbojas ar struct,

326
00:23:58,230 --> 00:24:04,300
mēs vēlamies izmantot. nokļūt pie lauka iekšpusē no struct.

327
00:24:04,300 --> 00:24:07,200
Un tikai laika mēs izmantojam bultiņas ir, ja mēs vēlamies darīt -

328
00:24:07,200 --> 00:24:13,450
labi, bultiņa ir līdzvērtīga -

329
00:24:13,450 --> 00:24:17,020
tas, ko tas nozīmētu, ja es izmanto bultiņu.

330
00:24:17,020 --> 00:24:24,600
Viss bultiņa līdzekļi ir, dereference tas, tagad es esmu pie struct, un es varu saņemt lauku.

331
00:24:24,600 --> 00:24:28,040
Nu saņemt lauku tieši vai dereference un saņemt lauku -

332
00:24:28,040 --> 00:24:30,380
Es domāju, tas būtu vērtība.

333
00:24:30,380 --> 00:24:33,910
Bet šeit es esmu, kas nodarbojas tikai ar struct, ne rādītāju uz struct,

334
00:24:33,910 --> 00:24:38,780
un tāpēc es nevaru izmantot bultiņu.

335
00:24:38,780 --> 00:24:47,510
Bet šī veida lieta, mēs varam darīt, lai visu mezglu.

336
00:24:47,510 --> 00:24:55,790
Ak mans Dievs.

337
00:24:55,790 --> 00:25:09,540
Tas ir 6, 7, un 3.

338
00:25:09,540 --> 00:25:16,470
Tad mēs varam izveidot filiāles mūsu koku, mēs varam būt 7 -

339
00:25:16,470 --> 00:25:21,650
mēs varam būt, tās kreisajā vajadzētu norādīt uz 3.

340
00:25:21,650 --> 00:25:25,130
Tātad, kā mēs to darām?

341
00:25:25,130 --> 00:25:29,320
[Studenti, nesaprotami] >> jā. Adrese node3,

342
00:25:29,320 --> 00:25:34,170
un, ja Jums nav adreses, tad tas vienkārši nebūtu sastādīt.

343
00:25:34,170 --> 00:25:38,190
Bet atcerieties, ka tie ir norādes uz nākamo mezglu.

344
00:25:38,190 --> 00:25:44,930
Tiesības vajadzētu norādīt uz 9,

345
00:25:44,930 --> 00:25:53,330
un 3 vajadzētu norādīt uz tiesībām uz 6.

346
00:25:53,330 --> 00:25:58,480
Es domāju, ka tas ir visu komplektu. Jebkādus komentārus vai jautājumus?

347
00:25:58,480 --> 00:26:02,060
[Studentu, nesaprotami] Saknes būs 7.

348
00:26:02,060 --> 00:26:08,210
Mēs varam tikai teikt mezglā * PTR =

349
00:26:08,210 --> 00:26:14,160
vai saknes, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Lai mūsu mērķiem, mēs gribam būt darīšana ar ieliktni,

351
00:26:20,730 --> 00:26:25,490
tāpēc mēs esam gatavojas vēlas uzrakstīt funkciju, lai ievietotu šajā bināro koku

352
00:26:25,490 --> 00:26:34,230
un ieliktnis ir neizbēgami gatavojas aicināt malloc izveidot jaunu mezglu šo koku.

353
00:26:34,230 --> 00:26:36,590
Tātad lietas gatavojas saņemt netīrs ar faktu, ka daži mezgli

354
00:26:36,590 --> 00:26:38,590
Šobrīd uz skursteņa

355
00:26:38,590 --> 00:26:43,680
un citi mezgli ir gatavojas galu galā uz kaudzes, kad mēs ievietot tos.

356
00:26:43,680 --> 00:26:47,640
Tas ir pilnīgi derīgs, bet vienīgais iemesls

357
00:26:47,640 --> 00:26:49,600
mēs esam spējīgi to darīt uz skursteņa

358
00:26:49,600 --> 00:26:51,840
ir tāpēc, ka tas ir tik neīsts piemērs, ka mēs zinām

359
00:26:51,840 --> 00:26:56,360
koks ir paredzēts būt konstruēts kā 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Ja mums nebija tas, tad mums nebūtu malloc pirmajā vietā.

361
00:27:02,970 --> 00:27:06,160
Kā mēs redzēsim nedaudz vēlāk, mums būtu malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Šobrīd tas ir pilnīgi pamatoti likt uz skursteņa,

363
00:27:08,570 --> 00:27:14,750
bet pieņemsim mainīt uz malloc īstenošanu.

364
00:27:14,750 --> 00:27:17,160
Tāpēc katra no tām ir tagad būs kaut kas līdzīgs

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

366
00:27:24,240 --> 00:27:28,040
Un tagad mēs esam nāksies darīt mūsu čeku.

367
00:27:28,040 --> 00:27:34,010
ja (node9 == NULL) - Es negribēju, ka -

368
00:27:34,010 --> 00:27:40,950
return 1, un tad mēs varam darīt node9-> jo tagad tas ir rādītājs,

369
00:27:40,950 --> 00:27:45,300
vērtība = 6, node9-> kreisi = NULL,

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

371
00:27:48,930 --> 00:27:51,410
un mēs esam nāksies to darīt par katru no šiem punktiem.

372
00:27:51,410 --> 00:27:57,490
Tā vietā, pieņemsim, nodot to iekšpusē atsevišķas funkcijas.

373
00:27:57,490 --> 00:28:00,620
Sauksim to mezglā * build_node,

374
00:28:00,620 --> 00:28:09,050
un tas ir nedaudz līdzīgs API mēs sniedzam Huffman kodēšana.

375
00:28:09,050 --> 00:28:12,730
Mēs jums initializer funkcijas koku

376
00:28:12,730 --> 00:28:20,520
un deconstructor "funkcijas" tiem kokiem un par mežu pašiem.

377
00:28:20,520 --> 00:28:22,570
>> Tāpēc šeit mēs esam gatavojas būt initializer funkciju

378
00:28:22,570 --> 00:28:25,170
lai tikai veidot mezglu mums.

379
00:28:25,170 --> 00:28:29,320
Un tas notiek, lai izskatās diezgan daudz tieši kā šis.

380
00:28:29,320 --> 00:28:32,230
Un es esmu pat būs slinks un nemaina nosaukumu mainīgo,

381
00:28:32,230 --> 00:28:34,380
kaut node9 nav jēgas vairs.

382
00:28:34,380 --> 00:28:38,610
Ak, es domāju node9 vērtība nebūtu bijis 6.

383
00:28:38,610 --> 00:28:42,800
Tagad mēs varam atgriezties node9.

384
00:28:42,800 --> 00:28:49,550
Un šeit mums vajadzētu atgriezties null.

385
00:28:49,550 --> 00:28:52,690
Ikvienam vienoties par šo būvēt-mezglu funkciju?

386
00:28:52,690 --> 00:28:59,780
Tāpēc tagad mēs varam tikai zvanu, ka, lai izveidotu jebkuru mezglu ar konkrētu vērtību un Null norādes.

387
00:28:59,780 --> 00:29:09,750
Tagad mēs varam zvanīt, ka mēs varam darīt mezglā * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Un pieņemsim darīt. . .

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

390
00:29:33,980 --> 00:29:39,330
Un tagad mēs vēlamies izveidot pašus norādes,

391
00:29:39,330 --> 00:29:42,470
izņemot tagad viss jau ziņā šautru

392
00:29:42,470 --> 00:29:48,480
tāpēc vairs nav nepieciešams adresi.

393
00:29:48,480 --> 00:29:56,300
Labi. Tātad, kāda ir pēdējā lieta, ko es gribu darīt?

394
00:29:56,300 --> 00:30:03,850
Tur kļūdu pārbaude, ka es to nedaru.

395
00:30:03,850 --> 00:30:06,800
Kāda būvēt mezglā atdevi?

396
00:30:06,800 --> 00:30:11,660
[Studentu, nesaprotami] >> Jā. Ja malloc neizdevās, tas būs atpakaļ null.

397
00:30:11,660 --> 00:30:16,460
Tāpēc es esmu gatavojas laiski likt to šeit, nevis darīt nosacījumu par katru.

398
00:30:16,460 --> 00:30:22,320
Ja (node9 == NULL, vai - vēl vienkāršāk,

399
00:30:22,320 --> 00:30:28,020
tas ir līdzvērtīgs tikai ja ne node9.

400
00:30:28,020 --> 00:30:38,310
Tātad, ja nav node9, vai nav node6, vai nav node3, vai ne node7, atgriezties 1.

401
00:30:38,310 --> 00:30:42,850
Varbūt mums vajadzētu drukāt malloc neizdevās, vai kaut ko.

402
00:30:42,850 --> 00:30:46,680
[Studentu] Vai viltus vienāds ar null, kā arī?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Jebkura nulles vērtība ir nepatiesa.

404
00:30:51,290 --> 00:30:53,920
Tātad Null ir nulles vērtība.

405
00:30:53,920 --> 00:30:56,780
Nulle ir nulles vērtība. Viltus ir nulles vērtība.

406
00:30:56,780 --> 00:31:02,130
Jebkurš - diezgan daudz tikai 2 nulles vērtības ir spēkā un nulle,

407
00:31:02,130 --> 00:31:07,900
viltus ir tikai jaukšanas definēta kā nulle.

408
00:31:07,900 --> 00:31:13,030
Tas attiecas arī tad, ja mēs atzīt globālo mainīgo.

409
00:31:13,030 --> 00:31:17,890
Ja mums tomēr ir mezglā * saknes šeit,

410
00:31:17,890 --> 00:31:24,150
tad - jauka lieta par globālo mainīgo, ka viņi vienmēr ir sākotnējo vērtību.

411
00:31:24,150 --> 00:31:27,500
Tas nav taisnība funkciju, cik iekšā šeit,

412
00:31:27,500 --> 00:31:34,870
ja mums ir, piemēram, mezglu * vai mezglu x.

413
00:31:34,870 --> 00:31:37,380
Mums nav ne jausmas, ko x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
vai mēs varētu drukāt tos un tie varētu būt patvaļīga.

415
00:31:40,700 --> 00:31:44,980
Tas nav taisnība globālo mainīgo.

416
00:31:44,980 --> 00:31:47,450
Tātad mezgls saknes vai mezglu x.

417
00:31:47,450 --> 00:31:53,410
Pēc noklusējuma, viss, kas ir globāls, ja nav skaidri inicializēts ar kādu vērtību,

418
00:31:53,410 --> 00:31:57,390
ir nulles vērtība kā tās vērtību.

419
00:31:57,390 --> 00:32:01,150
Tātad šeit, mezglu * saknes, mums nav skaidri inicializ tā neko,

420
00:32:01,150 --> 00:32:06,350
tāpēc tās noklusējuma vērtība būs nulle, kas ir nulles vērtība norādes.

421
00:32:06,350 --> 00:32:11,870
Noklusējuma vērtība x ir gatavojas nozīmē, ka x.value ir nulle,

422
00:32:11,870 --> 00:32:14,260
x.left ir nulle, un x.right ir nulle.

423
00:32:14,260 --> 00:32:21,070
Tāpēc, ka tas ir struktūrai, visi no struct jomās būs nulles vērtības.

424
00:32:21,070 --> 00:32:24,410
Mums nav nepieciešams izmantot, ka šeit, lai gan.

425
00:32:24,410 --> 00:32:27,320
[Studentu] Šīs structs ir savādāki nekā citiem mainīgajiem, un citi mainīgie ir

426
00:32:27,320 --> 00:32:31,400
atkritumu vērtības, tie ir nulles?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Pārējās vērtības too. Tātad x, x būs nulle.

428
00:32:36,220 --> 00:32:40,070
Ja tas ir pie pasaules mēroga, tas ir sākotnējo vērtību. >> Labi.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Nu sākotnējā vērtība jums iedeva vai nulle.

430
00:32:48,950 --> 00:32:53,260
Es domāju, ka rūpējas par visu.

431
00:32:53,260 --> 00:32:58,390
>> Labi. Tāpēc nākamais jautājuma daļu jautā,

432
00:32:58,390 --> 00:33:01,260
"Tagad mēs vēlamies, lai rakstītu funkciju sauc satur

433
00:33:01,260 --> 00:33:04,930
ar prototipu bool satur int vērtību. "

434
00:33:04,930 --> 00:33:08,340
Mums nav gatavojas darīt bool ir int vērtību.

435
00:33:08,340 --> 00:33:15,110
Mūsu prototips ir gatavojas izskatās

436
00:33:15,110 --> 00:33:22,380
bool satur (int vērtību.

437
00:33:22,380 --> 00:33:24,490
Un tad mēs esam arī gatavojas nodot to koku

438
00:33:24,490 --> 00:33:28,870
ka tas būtu pārbaudi, lai redzētu, vai tas ir šo vērtību.

439
00:33:28,870 --> 00:33:38,290
Tātad mezglu * koks). Labi.

440
00:33:38,290 --> 00:33:44,440
Un tad mēs varam zvanīt to ar kaut ko līdzīgu,

441
00:33:44,440 --> 00:33:46,090
varbūt mēs vēlamies printf vai kaut ko.

442
00:33:46,090 --> 00:33:51,040
Satur 6, mūsu saknes.

443
00:33:51,040 --> 00:33:54,300
Ka vajadzētu atgriezties vienu, vai taisnība,

444
00:33:54,300 --> 00:33:59,390
tā satur 5 sakne būtu atgriezties viltus.

445
00:33:59,390 --> 00:34:02,690
Tātad ņemt otrais īstenot šo.

446
00:34:02,690 --> 00:34:06,780
To var izdarīt, vai nu iteratīvi vai rekursīvi.

447
00:34:06,780 --> 00:34:09,739
Jauka lieta par to, kā mēs esam, kas lietām up ir tas, ka

448
00:34:09,739 --> 00:34:12,300
tas pakļauj sevi mūsu rekursīvas risinājums ir daudz vieglāk

449
00:34:12,300 --> 00:34:14,719
nekā pasaules mainīgo veidā izdarīja.

450
00:34:14,719 --> 00:34:19,750
Jo, ja mēs vienkārši ir ietverti int vērtība, tad mums nav veids, recursing leju subtrees.

451
00:34:19,750 --> 00:34:24,130
Mums būtu jābūt ar atsevišķu palīgs funkcija, kas recurses paredz subtrees par mums.

452
00:34:24,130 --> 00:34:29,610
Bet tā kā mēs esam nomainījuši veikt koku kā argumentu,

453
00:34:29,610 --> 00:34:32,760
kas tas būtu vienmēr ir bijis pirmajā vietā,

454
00:34:32,760 --> 00:34:35,710
Tagad mēs varam Recurse vieglāk.

455
00:34:35,710 --> 00:34:38,960
Tātad iteratīvs vai rekursīvs, mēs iet pār abiem,

456
00:34:38,960 --> 00:34:46,139
bet mēs redzēsim, ka rekursīvas beidzas ar to diezgan viegli.

457
00:34:59,140 --> 00:35:02,480
Labi. Vai kāds ir kaut ko mēs varam strādāt ar?

458
00:35:02,480 --> 00:35:12,000
>> [Studentu] Man iteratīvu risinājumu. >> Labi, iteratīvs.

459
00:35:12,000 --> 00:35:16,030
Labi, tas izskatās labi.

460
00:35:16,030 --> 00:35:18,920
Tātad, gribu staigāt mūs caur to?

461
00:35:18,920 --> 00:35:25,780
[Studentu] Protams. Tāpēc es noteikti temp mainīgo iegūt pirmo mezglu no koka.

462
00:35:25,780 --> 00:35:28,330
Un tad es vienkārši looped cauri, bet temperatūra nav vienāda null,

463
00:35:28,330 --> 00:35:31,700
tāpēc, kamēr vēl bija kokā, es domāju.

464
00:35:31,700 --> 00:35:35,710
Un, ja vērtība ir vienāda ar vērtību, kas temperatūra ir vērsta uz,

465
00:35:35,710 --> 00:35:37,640
tad tas atgriežas šo vērtību.

466
00:35:37,640 --> 00:35:40,210
Pretējā gadījumā tas pārbauda, ​​vai tas ir uz labo pusi, vai kreisās puses.

467
00:35:40,210 --> 00:35:43,400
Ja Jums kādreiz iegūt situāciju, kad tur nav daudz koku,

468
00:35:43,400 --> 00:35:47,330
tad tas atgriežas - tas izejām cilpu un atgriež nepatiess.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Labi. Tā ka, šķiet labi.

470
00:35:52,190 --> 00:35:58,470
Kāds ir kādi komentāri par kaut ko?

471
00:35:58,470 --> 00:36:02,400
Man nav pareizības komentārus vispār.

472
00:36:02,400 --> 00:36:11,020
Viena lieta, ko mēs varam darīt, ir tas puisis.

473
00:36:11,020 --> 00:36:21,660
Ak, tas notiek, lai iet nedaudz gareni.

474
00:36:21,660 --> 00:36:33,460
Es noteikt, ka uz augšu. Labi.

475
00:36:33,460 --> 00:36:37,150
>> Ikvienam vajadzētu atcerēties, kā trijnieks darbi.

476
00:36:37,150 --> 00:36:38,610
Ir noteikti ir viktorīnu pagātnē

477
00:36:38,610 --> 00:36:41,170
kas jums funkcija ar trīskāršu operators,

478
00:36:41,170 --> 00:36:45,750
un teikt, tulkot, darīt kaut ko, kas neizmanto trīskāršo.

479
00:36:45,750 --> 00:36:49,140
Tātad šī ir ļoti izplatīta lieta, kad es domāju, lai izmantotu trīskāršo,

480
00:36:49,140 --> 00:36:54,610
ja ja daži nosacījums mainīgo uz kaut ko,

481
00:36:54,610 --> 00:36:58,580
cits noteikt to pašu mainīgo, lai kaut kas cits.

482
00:36:58,580 --> 00:37:03,390
Tas ir kaut kas ļoti bieži var tikt pārveidoti par šāda veida lieta

483
00:37:03,390 --> 00:37:14,420
kur noteikts, ka mainīgo šo - vai, nu, tas ir taisnība? Tad šī, vēl šis.

484
00:37:14,420 --> 00:37:18,550
[Studentu] Pirmais ir, ja taisnība, vai ne?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Jā. Kā es vienmēr izlasīt to ir, temperatūra ir vienāda vērtība lielāka nekā temp vērtību,

486
00:37:25,570 --> 00:37:30,680
tad tas, cits to. Tas uzdodot jautājumu.

487
00:37:30,680 --> 00:37:35,200
Tas ir lielāks? Tad darīt to pirmā lieta. Cits to otra lieta.

488
00:37:35,200 --> 00:37:41,670
Es gandrīz vienmēr - kolu, es tikai - manā galvā, es izlasīju kā citur.

489
00:37:41,670 --> 00:37:47,180
>> Vai kāds ir rekursīvas risinājums?

490
00:37:47,180 --> 00:37:49,670
Labi. Šis viena mēs spēsim - tas jau var būt liels,

491
00:37:49,670 --> 00:37:53,990
bet mēs ejam, lai padarītu to vēl labāku.

492
00:37:53,990 --> 00:37:58,720
Tas ir diezgan daudz pašā precīzu ideja.

493
00:37:58,720 --> 00:38:03,060
Tas ir tikai labi, jūs vēlaties, lai izskaidrotu?

494
00:38:03,060 --> 00:38:08,340
[Studentu] Protams. Tāpēc mēs esam pārliecinoties, ka koks nav null, pirmkārt,

495
00:38:08,340 --> 00:38:13,380
jo, ja koks ir nulle, tad tas notiek, lai atgrieztos nepatiess, jo mēs neesam atraduši.

496
00:38:13,380 --> 00:38:19,200
Un, ja tur ir vēl koks, mēs iedziļināties - mēs vispirms pārbaudiet, ja vērtība ir pašreizējā mezglā.

497
00:38:19,200 --> 00:38:23,740
Atgriešanās taisnība, ja tā ir, un, ja ne mēs Recurse pa kreisi vai pa labi.

498
00:38:23,740 --> 00:38:25,970
Vai tas skaņu gadījumā? >> Mm-hmm. (Līgums)

499
00:38:25,970 --> 00:38:33,880
Tāpēc ievērosiet, ka tas ir gandrīz - strukturāli ļoti līdzīgs atkārtojuma risinājumu.

500
00:38:33,880 --> 00:38:38,200
Tas ir tikai, ka tā vietā, lai recursing, mums bija, kamēr cilpa.

501
00:38:38,200 --> 00:38:40,840
Un bāzes gadījums, kad koks nav vienāds null

502
00:38:40,840 --> 00:38:44,850
bija nosacījums, saskaņā ar kuru mēs izcēlās kamēr cilpa.

503
00:38:44,850 --> 00:38:50,200
Viņi ir ļoti līdzīgi. Bet mēs spēsim veikt šo vienu soli tālāk.

504
00:38:50,200 --> 00:38:54,190
Tagad, mēs darīt to pašu šeit.

505
00:38:54,190 --> 00:38:57,680
Pamanīt mēs atgriežoties vienu un to pašu gan no šīm līnijām,

506
00:38:57,680 --> 00:39:00,220
izņemot vienu arguments ir atšķirīgs.

507
00:39:00,220 --> 00:39:07,950
Tāpēc mēs esam gatavojas darīt, ka par trīskāršu.

508
00:39:07,950 --> 00:39:13,790
Es hit iespēju kaut ko, un tas veikts simbolu. Labi.

509
00:39:13,790 --> 00:39:21,720
Tāpēc mēs esam gatavojas atgriezties satur to.

510
00:39:21,720 --> 00:39:28,030
Tas kļūst par vairākas līnijas, labi, pietuvināto tas ir.

511
00:39:28,030 --> 00:39:31,060
Parasti, kā stilistisku lieta, es nedomāju, ka daudzi cilvēki

512
00:39:31,060 --> 00:39:38,640
likts atstarpi pēc bultiņas, bet es domāju, ja tu esi konsekventa, tas ir labi.

513
00:39:38,640 --> 00:39:44,320
Ja vērtība ir mazāka nekā koku vērtību, mēs vēlamies Recurse no koku pa kreisi,

514
00:39:44,320 --> 00:39:53,890
cits mēs vēlamies Recurse par koku tiesībām.

515
00:39:53,890 --> 00:39:58,610
Tāpēc, ka bija veidot šo izskatās mazāks viens solis.

516
00:39:58,610 --> 00:40:02,660
Otrais solis, lai šis izskatās mazāks -

517
00:40:02,660 --> 00:40:09,150
mēs varam atdalīt ar vairākām līnijām.

518
00:40:09,150 --> 00:40:16,500
Labi. Padarīt to izskatās mazākas divpakāpju ir šeit,

519
00:40:16,500 --> 00:40:25,860
tāpēc atgriešanās vērtība ir koka vērtību, vai satur neatkarīgi.

520
00:40:25,860 --> 00:40:28,340
>> Tas ir svarīga lieta.

521
00:40:28,340 --> 00:40:30,860
Es neesmu pārliecināts, vai viņš teica, ka tas skaidri klasē,

522
00:40:30,860 --> 00:40:34,740
bet tā sauc īssavienojuma novērtējums.

523
00:40:34,740 --> 00:40:41,060
Ideja šeit ir vērtība == koku vērtība.

524
00:40:41,060 --> 00:40:49,960
Ja tā ir taisnība, tad tas ir taisnība, un mēs vēlamies, lai "vai" kas ar kāda ir vairāk nekā šeit.

525
00:40:49,960 --> 00:40:52,520
Tātad, pat domāt par visu, nekā šeit,

526
00:40:52,520 --> 00:40:55,070
kāda ir visa izteiksme gatavojas atgriezties?

527
00:40:55,070 --> 00:40:59,430
[Studentu] True? >> Jā, jo taisnība neko,

528
00:40:59,430 --> 00:41:04,990
or'd - vai taisnība or'd ar jebko ir vienmēr taisnība.

529
00:41:04,990 --> 00:41:08,150
Tā tiklīdz mēs redzam atgriešanās vērtību = koku vērtību,

530
00:41:08,150 --> 00:41:10,140
mēs esam tikai gatavojas atgriezties taisnība.

531
00:41:10,140 --> 00:41:15,710
Nav pat gatavojas Recurse further satur leju līniju.

532
00:41:15,710 --> 00:41:20,980
Mēs varam veikt šo vienu soli tālāk.

533
00:41:20,980 --> 00:41:29,490
Atgriešanās koks nav vienāds anulēts un visu.

534
00:41:29,490 --> 00:41:32,650
Tas padarīja viena līnija funkcija.

535
00:41:32,650 --> 00:41:36,790
Tas ir arī piemērs īssavienojumu novērtējumu.

536
00:41:36,790 --> 00:41:40,680
Bet tagad tas ir pati ideja -

537
00:41:40,680 --> 00:41:47,320
vietā - tāpēc, ja koks nav vienāds null - vai, nu,

538
00:41:47,320 --> 00:41:49,580
ja koks nav vienāda null, kas ir slikti gadījums,

539
00:41:49,580 --> 00:41:54,790
ja koks vienāds Null, tad pirmais nosacījums būs nepatiesa.

540
00:41:54,790 --> 00:42:00,550
Tātad viltus anded ar jebko būs ko?

541
00:42:00,550 --> 00:42:04,640
[Studentu] Aplams. >> Jā. Tas ir otra puse īssavienojumu novērtējumu,

542
00:42:04,640 --> 00:42:10,710
ja ja koks nav vienāds Null, tad mēs nebrauksim, lai pat iet -

543
00:42:10,710 --> 00:42:14,930
vai ja koks nav vienāda null, tad mēs neesam gatavojas darīt vērtību == koku vērtība.

544
00:42:14,930 --> 00:42:17,010
Mēs esam tikai gatavojas nekavējoties atgriezties viltus.

545
00:42:17,010 --> 00:42:20,970
Kas ir svarīgi, jo, ja tā nav īssavienojumu novērtēt,

546
00:42:20,970 --> 00:42:25,860
tad, ja koks nav vienāda null, šis otrais nosacījums ir gatavojas SEG vaina,

547
00:42:25,860 --> 00:42:32,510
jo koks-> vērtību dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Tātad tas ir kas. Var padarīt šo - novirzīt vienreiz pāri.

549
00:42:40,490 --> 00:42:44,840
Tas ir ļoti bieži lieta arī, nevis padarot šo par vienu līniju ar šo,

550
00:42:44,840 --> 00:42:49,000
bet tas ir parasta lieta apstākļos, varbūt ne tieši šeit,

551
00:42:49,000 --> 00:42:59,380
bet, ja (koks! = NULL, un koks-> vērtība == vērtība), darīt visu.

552
00:42:59,380 --> 00:43:01,560
Tas ir ļoti bieži stāvoklis, kad tā vietā,

553
00:43:01,560 --> 00:43:06,770
lauzt šo divās IF, kur patīk, ir koks Null?

554
00:43:06,770 --> 00:43:11,780
Labi, tas nav nulle, tāpēc tagad ir koks vērtība ir vienāda ar vērtību? Izdarīt.

555
00:43:11,780 --> 00:43:17,300
Tā vietā, šis nosacījums, tas nekad SEG vaina

556
00:43:17,300 --> 00:43:21,220
jo tā būs pārtraukums, ja tas notiek, ir nulle.

557
00:43:21,220 --> 00:43:24,000
Nu, es domāju, ja jūsu koks ir pilnīgi nederīgs rādītāju, tas joprojām var SEG vaina,

558
00:43:24,000 --> 00:43:26,620
bet tā nevar SEG vaina, ja koks ir nulle.

559
00:43:26,620 --> 00:43:32,900
Ja tas būtu nulle, tas izcelties pirms jūs kādreiz dereferenced rādītāju pirmajā vietā.

560
00:43:32,900 --> 00:43:35,000
[Studentu] Vai tas saucamais slinks novērtējums?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Slinks vērtēšana ir atsevišķa lieta.

562
00:43:40,770 --> 00:43:49,880
Slinks novērtējums ir vairāk kā jūs lūgt par vērtību,

563
00:43:49,880 --> 00:43:54,270
jūs lūgt, lai aprēķinātu vērtību, veida, bet jums nav nepieciešams to nekavējoties.

564
00:43:54,270 --> 00:43:59,040
Tātad līdz brīdim, kad tiešām ir nepieciešams, tā nav novērtēta.

565
00:43:59,040 --> 00:44:03,920
Tas nav tieši tas pats, bet Huffman PSET,

566
00:44:03,920 --> 00:44:06,520
tā saka, ka mēs "laiski" rakstīt.

567
00:44:06,520 --> 00:44:08,670
Iemesls, kāpēc mēs darīt, ir tāpēc, ka mēs esam patiešām buffering rakstīt -

568
00:44:08,670 --> 00:44:11,820
Mēs nevēlamies, lai rakstīt atsevišķus bitus laikā,

569
00:44:11,820 --> 00:44:15,450
vai atsevišķas baiti vienlaicīgi, mēs tā vietā vēlas saņemt rieciens baitu.

570
00:44:15,450 --> 00:44:19,270
Tad, kad mums ir rieciens baitu, tad mēs to uzraksta.

571
00:44:19,270 --> 00:44:22,640
Pat ja jūs lūgt to rakstīt - un fwrite un fread darīt to pašu veida lieta.

572
00:44:22,640 --> 00:44:26,260
Viņi buferis savu lasa un raksta.

573
00:44:26,260 --> 00:44:31,610
Pat ja jūs lūgt to rakstīt uzreiz, tas, iespējams, nebūs.

574
00:44:31,610 --> 00:44:34,540
Un jūs varat būt pārliecināti, ka lietas notiek, kas rakstīts

575
00:44:34,540 --> 00:44:37,540
līdz zvanīt hfclose vai kāds tas ir,

576
00:44:37,540 --> 00:44:39,620
kas tad saka, labi, es esmu slēgšanas manu failu,

577
00:44:39,620 --> 00:44:43,450
tas nozīmē, ka es labāk rakstīt visu, man nav rakstisku vēl.

578
00:44:43,450 --> 00:44:45,770
Tam nav nepieciešams rakstīt viss out

579
00:44:45,770 --> 00:44:49,010
līdz pietuvojas failu, un tad tas ir.

580
00:44:49,010 --> 00:44:56,220
Tātad tas ir tikai to, ko slinks - tas gaida, kamēr tas ir noticis.

581
00:44:56,220 --> 00:44:59,990
Tas - ņem 51 un jūs iedziļināties to sīkāk,

582
00:44:59,990 --> 00:45:05,470
jo OCaml un viss 51, viss ir rekursija.

583
00:45:05,470 --> 00:45:08,890
Nav iteratīvs risinājumus, būtībā.

584
00:45:08,890 --> 00:45:11,550
Viss ir rekursija, un slinks novērtēšana

585
00:45:11,550 --> 00:45:14,790
būs svarīgi daudz apstākļu

586
00:45:14,790 --> 00:45:19,920
kur, ja Jums nav laiski novērtēt, tas nozīmētu -

587
00:45:19,920 --> 00:45:24,760
Piemērs ir straumes, kas ir bezgalīgi garš.

588
00:45:24,760 --> 00:45:30,990
Teorētiski, jūs varat domāt par dabas numuriem kā plūsmā 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Tātad laiski novērtētie lietas ir labi.

590
00:45:33,090 --> 00:45:37,210
Ja es saku es gribu desmito numuru, tad es varētu novērtēt līdz desmito numuru.

591
00:45:37,210 --> 00:45:40,300
Ja es gribu simto numuru, tad es varētu novērtēt līdz simto numuru.

592
00:45:40,300 --> 00:45:46,290
Bez slinks novērtējumu, tad tas notiek, lai mēģinātu novērtēt visus numurus uzreiz.

593
00:45:46,290 --> 00:45:50,000
Tu esi izvērtējot bezgala daudz numurus, un tas vienkārši nav iespējams.

594
00:45:50,000 --> 00:45:52,080
Tātad tur ir apstākļi daudz kur slinks novērtējums

595
00:45:52,080 --> 00:45:57,840
ir tikai būtiska, lai iegūtu lietas darbu.

596
00:45:57,840 --> 00:46:05,260
>> Tagad mēs vēlamies, lai rakstītu ieliktni kur ievietot būs

597
00:46:05,260 --> 00:46:08,430
Tāpat mainās tā definīciju.

598
00:46:08,430 --> 00:46:10,470
Tātad šobrīd tas bool ieliktnis (int vērtība).

599
00:46:10,470 --> 00:46:23,850
Mēs ejam, lai mainītu, ka uz bool ieliktni (int vērtība, mezglu * koks).

600
00:46:23,850 --> 00:46:29,120
Mēs esam patiešām gatavojas mainīt, ka atkal mazliet, mēs redzēsim, kāpēc.

601
00:46:29,120 --> 00:46:32,210
Un pāriesim build_node, tikai heck no tā,

602
00:46:32,210 --> 00:46:36,730
Iepriekš ievietot tāpēc mums nav rakstīt funkcijas prototips.

603
00:46:36,730 --> 00:46:42,450
Kas ir mājiens, ka jūs esat būs izmantojot build_node ar ieliktņa.

604
00:46:42,450 --> 00:46:49,590
Labi. Paņem minūti par to.

605
00:46:49,590 --> 00:46:52,130
Es domāju, ka es saglabāti jāpārskata, ja jūs vēlaties, lai vilktu no tā,

606
00:46:52,130 --> 00:47:00,240
vai, vismaz, es darīju tagad.

607
00:47:00,240 --> 00:47:04,190
Es gribēju nedaudz pārtraukumu, lai padomātu par loģiku ievietot,

608
00:47:04,190 --> 00:47:08,750
ja jūs nevarat domāt par to.

609
00:47:08,750 --> 00:47:12,860
Būtībā, jums būs tikai kādreiz ievietojot pie lapām.

610
00:47:12,860 --> 00:47:18,640
Piemēram, ja es ievietot 1, tad es esmu neizbēgami būs ievietojot 1 -

611
00:47:18,640 --> 00:47:21,820
Es izmaiņas melnā - I'll būt ievietojot 1 nekā šeit.

612
00:47:21,820 --> 00:47:28,070
Vai, ja es ievietotu 4, es gribu būt ievietojot 4 vairāk nekā šeit.

613
00:47:28,070 --> 00:47:32,180
Līdz ar to nav svarīgi, ko jūs darāt, jūs esat būs ievietojot pie lapas.

614
00:47:32,180 --> 00:47:36,130
Viss, kas Jums jādara, ir atkārtot pa koku līdz jums mezglu

615
00:47:36,130 --> 00:47:40,890
kas būtu mezglā mātes, jaunā mezgla mātes,

616
00:47:40,890 --> 00:47:44,560
un tad mainīt savu kreiso vai labo rādītāju, atkarībā no tā, vai

617
00:47:44,560 --> 00:47:47,060
tas ir lielāks vai mazāks nekā pašreizējā mezglā.

618
00:47:47,060 --> 00:47:51,180
Mainītu šo rādītāju norādīt uz savu jauno mezglu.

619
00:47:51,180 --> 00:48:05,490
Tāpēc atkārtot pa koku, padarīt lapu norāda uz jaunu mezglu.

620
00:48:05,490 --> 00:48:09,810
Arī domāju par to, kāpēc, kas aizliedz veida situāciju pirms,

621
00:48:09,810 --> 00:48:17,990
kur es būvēti bināro koku, kur tas bija pareizs

622
00:48:17,990 --> 00:48:19,920
ja tu tikai paskatījās vienā mezglā,

623
00:48:19,920 --> 00:48:24,830
bet 9 bija pa kreisi no 7 Ja jūs uzsvēra leju visu ceļu.

624
00:48:24,830 --> 00:48:29,770
Tā ka ir neiespējami šajā scenārijā, jo -

625
00:48:29,770 --> 00:48:32,530
domā par ievietojot 9 vai kaut; pašu pirmo mezglu,

626
00:48:32,530 --> 00:48:35,350
Es esmu gatavojas, lai redzētu 7 un es esmu tikai gatavojas iet uz labo pusi.

627
00:48:35,350 --> 00:48:38,490
Līdz ar to nav svarīgi, ko es daru, ja es esmu ievietojot dodoties uz lapu,

628
00:48:38,490 --> 00:48:40,790
un uz lapu, izmantojot atbilstošu algoritmu,

629
00:48:40,790 --> 00:48:43,130
tas būs neiespējami man ievietot 9 pa kreisi no 7

630
00:48:43,130 --> 00:48:48,250
jo tiklīdz es hit 7 Es esmu gatavojas iet uz labo pusi.

631
00:48:59,740 --> 00:49:02,070
Vai kāds ir kaut ko sākt?

632
00:49:02,070 --> 00:49:05,480
[Studentu] man. >> Protams.

633
00:49:05,480 --> 00:49:09,200
[Studentu, nesaprotami]

634
00:49:09,200 --> 00:49:14,390
[Citi students, nesaprotami]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Tas ir appreciated. Labi. Gribu paskaidrot?

636
00:49:18,330 --> 00:49:20,690
>> [Studentu] Tā kā mēs zinām, ka mēs bijām ievietojot

637
00:49:20,690 --> 00:49:24,060
krustpunkti beigās koka,

638
00:49:24,060 --> 00:49:28,070
Es looped cauri koku iteratīvi

639
00:49:28,070 --> 00:49:31,360
līdz es saņēmu mezglu, norādīja uz null.

640
00:49:31,360 --> 00:49:34,220
Un tad es nolēmu nodot to vai nu uz labo pusi vai kreisajā pusē

641
00:49:34,220 --> 00:49:37,420
Izmantojot šīs tiesības mainīgo, tas teica man, kur likt to.

642
00:49:37,420 --> 00:49:41,850
Un tad, būtībā, es tikko ka pēdējo -

643
00:49:41,850 --> 00:49:47,520
ka temperatūra mezglā norāda uz jauno mezglu, tas bija radīt,

644
00:49:47,520 --> 00:49:50,770
nu kreisajā pusē vai labajā pusē, atkarībā no tā, kāda vērtība labi bija.

645
00:49:50,770 --> 00:49:56,530
Visbeidzot, es noteikt jauno mezglu vērtību vērtību tās testēšana.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Labi, tāpēc es redzu vienu jautājumu šeit.

647
00:49:59,550 --> 00:50:02,050
Tas ir tāpat kā 95% no tur.

648
00:50:02,050 --> 00:50:07,550
Viens jautājums, ka es redzu, labi, vai kāds cits redzu problēmu?

649
00:50:07,550 --> 00:50:18,400
Kas ir apstāklis, saskaņā ar kuru tās uzliesmo no cilpas?

650
00:50:18,400 --> 00:50:22,100
[Studentu] Ja temperatūra ir nulle? >> Jā. Tātad, kā jūs izkļūt no cilpas ir, ja temperatūra ir nulle.

651
00:50:22,100 --> 00:50:30,220
Bet ko man darīt tieši šeit?

652
00:50:30,220 --> 00:50:35,410
Es dereference temp, kas ir neizbēgami Null.

653
00:50:35,410 --> 00:50:39,840
Tātad otra lieta, kas jums jādara, ir ne tikai sekot līdz temperatūra ir nulle,

654
00:50:39,840 --> 00:50:45,590
Jūs vēlaties, lai sekotu no mātes visu laiku.

655
00:50:45,590 --> 00:50:52,190
Mēs arī vēlamies mezglā * vecāks, es domāju, mēs varam saglabāt, ka null sākumā.

656
00:50:52,190 --> 00:50:55,480
Tas ir nāksies dīvainu uzvedību uz koka saknēm,

657
00:50:55,480 --> 00:50:59,210
bet mēs nokļūt, ka.

658
00:50:59,210 --> 00:51:03,950
Ja vērtība ir lielāka nekā kāds, tad temp = temp labi.

659
00:51:03,950 --> 00:51:07,910
Taču, pirms mēs to darām, vecākiem = temp.

660
00:51:07,910 --> 00:51:14,500
Vai vecāki vienmēr būs vienāda temp? Vai tas tā ir?

661
00:51:14,500 --> 00:51:19,560
Ja temperatūra nav Null, tad es esmu gatavojas pārcelties uz leju, vienalga ko,

662
00:51:19,560 --> 00:51:24,030
uz mezglu, par kuru temperatūra ir mātes.

663
00:51:24,030 --> 00:51:27,500
Tāpēc vecākiem būs temperatūra, un tad es eju temp leju.

664
00:51:27,500 --> 00:51:32,410
Tagad temperatūra ir nulle, bet vecāka norāda uz mātes lieta, kas ir nulle.

665
00:51:32,410 --> 00:51:39,110
Tātad šeit lejā, es nevēlos, lai noteikt tiesības ir vienāds ar 1.

666
00:51:39,110 --> 00:51:41,300
Tāpēc es pārcēlos uz labo, tāpēc, ja labi = 1,

667
00:51:41,300 --> 00:51:45,130
un es domāju, jūs arī vēlaties darīt -

668
00:51:45,130 --> 00:51:48,530
ja jūs pārvietoties pa kreisi, jūs vēlaties noteikt tiesības vienāda ar 0.

669
00:51:48,530 --> 00:51:55,950
Vai arī, ja jūs kādreiz pārvietot uz labo pusi.

670
00:51:55,950 --> 00:51:58,590
Tik labi = 0. Ja labi = 1,

671
00:51:58,590 --> 00:52:04,260
Tagad mēs vēlamies, lai mātes pareizo rādītāju newnode,

672
00:52:04,260 --> 00:52:08,520
cits mēs vēlamies, lai mātes kreiso rādītāju newnode.

673
00:52:08,520 --> 00:52:16,850
Jautājumi par šo?

674
00:52:16,850 --> 00:52:24,880
Labi. Tātad šis ir veids, kā mēs - labi, patiesībā, nevis darīt to,

675
00:52:24,880 --> 00:52:29,630
mēs 1/2 gaidīts jums izmantot build_node.

676
00:52:29,630 --> 00:52:40,450
Un tad, ja newnode vienāds Null, atgriezties viltus.

677
00:52:40,450 --> 00:52:44,170
Tas, ka. Tagad, tas ir tas, ko mēs gaidīts jums darīt.

678
00:52:44,170 --> 00:52:47,690
>> Tas ir tas, ko darbinieki risinājumi darīt.

679
00:52:47,690 --> 00:52:52,360
Es nepiekrītu ar to kā "pareizo" ceļu, iet par to

680
00:52:52,360 --> 00:52:57,820
bet tas ir pilnīgi naudas sodu, un tas strādā.

681
00:52:57,820 --> 00:53:02,840
Viena lieta, ka ir mazliet dīvaini šobrīd ir

682
00:53:02,840 --> 00:53:08,310
ja koks sāk off par spēkā, mums iet ar Null koku.

683
00:53:08,310 --> 00:53:12,650
Es domāju, tas atkarīgs no tā, kā jūs definētu uzvedību aizrit Null koku.

684
00:53:12,650 --> 00:53:15,490
Es domāju, ka, ja jums iet ar Null koku,

685
00:53:15,490 --> 00:53:17,520
tad ievietojot vērtību par Null kokā

686
00:53:17,520 --> 00:53:23,030
būtu tikai atgriezties kokā, kur vienīgā vērtība ir tā, ka viena mezglā.

687
00:53:23,030 --> 00:53:25,830
Vai cilvēki piekrīt, ka? Jūs varētu, ja vēlaties,

688
00:53:25,830 --> 00:53:28,050
ja jums iet ar Null kokā

689
00:53:28,050 --> 00:53:31,320
un jūs vēlaties ievietot vērtības vērā to, atgriezties viltus.

690
00:53:31,320 --> 00:53:33,830
Tas ir atkarīgs no jums, lai noteiktu to.

691
00:53:33,830 --> 00:53:38,320
Lai to izdarītu, pirmā lieta, man teica, un tad -

692
00:53:38,320 --> 00:53:40,720
labi, jūs gatavojas ir problēmas darot, ka, jo

693
00:53:40,720 --> 00:53:44,090
tas būtu vieglāk, ja mums bija pasaules rādītāju uz lieta,

694
00:53:44,090 --> 00:53:48,570
bet mums nav, tādēļ, ja koks ir nulle, tur neko nevar darīt par to.

695
00:53:48,570 --> 00:53:50,960
Mēs varam vienkārši atgriezties viltus.

696
00:53:50,960 --> 00:53:52,840
Tāpēc es esmu gatavojas mainīt ieliktni.

697
00:53:52,840 --> 00:53:56,540
Mēs tehniski varētu vienkārši mainīt šīs tiesības šeit,

698
00:53:56,540 --> 00:53:58,400
kā tas atkārtojot pār lietām,

699
00:53:58,400 --> 00:54:04,530
bet es esmu gatavojas mainīt ievietot veikt mezgla ** koku.

700
00:54:04,530 --> 00:54:07,510
Double norādes.

701
00:54:07,510 --> 00:54:09,710
Ko tas nozīmē?

702
00:54:09,710 --> 00:54:12,330
Nevis nodarbojas ar norādes uz mezgliem,

703
00:54:12,330 --> 00:54:16,690
lieta, ko es esmu būs manipulējot tas rādītājs.

704
00:54:16,690 --> 00:54:18,790
Es esmu būs manipulējot šo rādītāju.

705
00:54:18,790 --> 00:54:21,770
Es esmu būs manipulējot norādes tieši.

706
00:54:21,770 --> 00:54:25,760
Tas ir jēga, jo, domāju par leju -

707
00:54:25,760 --> 00:54:33,340
labi, tagad tas norāda uz null.

708
00:54:33,340 --> 00:54:38,130
Ko es gribu darīt, ir manipulēt šo rādītāju, lai norādītu uz nav null.

709
00:54:38,130 --> 00:54:40,970
Es vēlos, lai norādītu uz savu jauno mezglu.

710
00:54:40,970 --> 00:54:44,870
Ja es tikko sekot līdzi norādes uz manu norādes,

711
00:54:44,870 --> 00:54:47,840
tad man nav nepieciešams, lai sekotu mātes rādītāju.

712
00:54:47,840 --> 00:54:52,640
Es varu tikai sekot, lai redzētu, ja rādītājs ir vērsta uz null,

713
00:54:52,640 --> 00:54:54,580
un ja rādītājs ir vērsta uz null,

714
00:54:54,580 --> 00:54:57,370
mainīt to norādīt uz mezglu es gribu.

715
00:54:57,370 --> 00:55:00,070
Un es varu mainīt to, jo man ir rādītāju uz rādītāja.

716
00:55:00,070 --> 00:55:02,040
Pieņemsim redzēt šīs tiesības tagad.

717
00:55:02,040 --> 00:55:05,470
Jūs faktiski var darīt to rekursīvi diezgan viegli.

718
00:55:05,470 --> 00:55:08,080
Vai mēs gribam to darīt?

719
00:55:08,080 --> 00:55:10,980
Jā, mēs darām.

720
00:55:10,980 --> 00:55:16,790
>> Pieņemsim redzēt to rekursīvi.

721
00:55:16,790 --> 00:55:24,070
Pirmkārt, kāda ir mūsu bāzes scenārijs būs?

722
00:55:24,070 --> 00:55:29,140
Gandrīz vienmēr mūsu bāzes scenārijs, bet patiesībā, tas ir sava veida grūts.

723
00:55:29,140 --> 00:55:34,370
Pirmās lietas, pirmkārt, ja (koks == NULL)

724
00:55:34,370 --> 00:55:37,550
Es domāju, mēs esam tikai gatavojas atgriezties viltus.

725
00:55:37,550 --> 00:55:40,460
Tas atšķiras no jūsu koku pagaidām null.

726
00:55:40,460 --> 00:55:44,510
Tas ir rādītājs, lai jūsu saknes rādītājs pagaidām Null

727
00:55:44,510 --> 00:55:48,360
kas nozīmē, ka jūsu saknes rādītājs nav.

728
00:55:48,360 --> 00:55:52,390
Tātad šeit lejā, ja man

729
00:55:52,390 --> 00:55:55,760
mezglu * - pieņemsim tikai atkārtotu to.

730
00:55:55,760 --> 00:55:58,960
Mezglu * sakne = NULL,

731
00:55:58,960 --> 00:56:00,730
un tad es esmu dodas uz zvanu ieliktni darot kaut kas līdzīgs,

732
00:56:00,730 --> 00:56:04,540
ievietot 4 stājas & saknes.

733
00:56:04,540 --> 00:56:06,560
Tātad & sakne, ja sakne ir mezgls *

734
00:56:06,560 --> 00:56:11,170
Tad & sakne būs mezgla **.

735
00:56:11,170 --> 00:56:15,120
Tas ir derīgs. Šajā gadījumā, koks, šeit,

736
00:56:15,120 --> 00:56:20,120
koks nav Null - vai ievietot.

737
00:56:20,120 --> 00:56:24,630
Šeit. Koks nav null; * koks ir nulle, kas ir labi

738
00:56:24,630 --> 00:56:26,680
jo, ja * koks ir nulle, tad es varētu manipulēt ar to

739
00:56:26,680 --> 00:56:29,210
lai tagad norāda uz to, ko es gribu to norādīt uz.

740
00:56:29,210 --> 00:56:34,750
Bet, ja koks ir nulle, tas nozīmē, ka es tikko nācis šeit un teica null.

741
00:56:34,750 --> 00:56:42,710
Tas nav jēgas. Es nevaru darīt neko ar to.

742
00:56:42,710 --> 00:56:45,540
Ja koks ir Null, atgriezties viltus.

743
00:56:45,540 --> 00:56:48,220
Tāpēc es būtībā jau teicu, ko mūsu reālā bāzes scenārijs ir.

744
00:56:48,220 --> 00:56:50,580
Un kas tas būs?

745
00:56:50,580 --> 00:56:55,030
[Studentu, nesaprotami]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Jā. Tātad, ja (* koks == NULL).

747
00:57:00,000 --> 00:57:04,520
Tas attiecas uz lietu nekā šeit

748
00:57:04,520 --> 00:57:09,640
ja ja mana sarkanā rādītājs ir rādītājs es esmu vērsta uz,

749
00:57:09,640 --> 00:57:12,960
tāpēc, piemēram, es esmu vērsta uz šo rādītāju, tagad es esmu vērsta uz šo rādītāju.

750
00:57:12,960 --> 00:57:15,150
Tagad es esmu vērsta uz šo rādītāju.

751
00:57:15,150 --> 00:57:18,160
Tātad, ja mana sarkanā rādītājs, kas ir mana mezglu **,

752
00:57:18,160 --> 00:57:22,880
ir kādreiz - ja *, mana sarkanā rādītājs, ir kādreiz Null,

753
00:57:22,880 --> 00:57:28,470
tas nozīmē, ka es esmu pie lietas, kur es esmu koncentrējoties uz rādītājs, kas norāda -

754
00:57:28,470 --> 00:57:32,530
Tas ir rādītājs, kas pieder lapu.

755
00:57:32,530 --> 00:57:41,090
Es vēlos mainīt šo rādītāju norādīt savu jauno mezglu.

756
00:57:41,090 --> 00:57:45,230
Atgriezties nekā šeit.

757
00:57:45,230 --> 00:57:56,490
Mans newnode būs tikai mezglu * n = build_node (vērtība)

758
00:57:56,490 --> 00:58:07,300
tad n, ja n = null, atgriezties viltus.

759
00:58:07,300 --> 00:58:12,600
Cits mēs gribam mainīt to, ko rādītājs pašlaik norādot uz

760
00:58:12,600 --> 00:58:17,830
šim norādīt uz mūsu jaunceļamā mezglā.

761
00:58:17,830 --> 00:58:20,280
Mēs faktiski var darīt šeit.

762
00:58:20,280 --> 00:58:30,660
Vietā, sakot n, mēs sakām * koks = ja * koku.

763
00:58:30,660 --> 00:58:35,450
Ikviens saprot, ka? Ka, risinot ar norādes uz norādes,

764
00:58:35,450 --> 00:58:40,750
mēs varam mainīt Null norādes norādīt uz lietām, mēs vēlamies, lai viņi norāda uz.

765
00:58:40,750 --> 00:58:42,820
Tas ir mūsu bāzes scenārijs.

766
00:58:42,820 --> 00:58:45,740
>> Tagad mūsu atkārtošanās, vai mūsu rekursija,

767
00:58:45,740 --> 00:58:51,430
būs ļoti līdzīga visām citām recursions mēs esam darījuši.

768
00:58:51,430 --> 00:58:55,830
Mēs esam gatavojas vēlaties ievietot vērtību,

769
00:58:55,830 --> 00:58:59,040
un tagad es esmu gatavojas izmantot trīskāršo vēlreiz, bet to, kas ir mūsu nosacījums būs?

770
00:58:59,040 --> 00:59:05,180
Kāda tā ir, mēs meklējam izlemt, vai mēs gribam iet pa kreisi vai pa labi?

771
00:59:05,180 --> 00:59:07,760
Darīsim to atsevišķos posmos.

772
00:59:07,760 --> 00:59:18,850
Ja (vērtība <) ko?

773
00:59:18,850 --> 00:59:23,200
[Studentu] koks ir vērtība?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Tāpēc atcerieties, ka es esmu šobrīd -

775
00:59:27,490 --> 00:59:31,260
[Studenti, nesaprotami]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Jā, tik labi šeit, pieņemsim, ka šī zaļā bulta

777
00:59:34,140 --> 00:59:39,050
ir piemērs tam, ko koks ir patlaban, ir rādītājs uz šo rādītāju.

778
00:59:39,050 --> 00:59:46,610
Tātad tas nozīmē, ka es esmu rādītāju uz norādi uz 3.

779
00:59:46,610 --> 00:59:48,800
The dereference divreiz skanēja labi.

780
00:59:48,800 --> 00:59:51,010
Kas man - kā es varu darīt?

781
00:59:51,010 --> 00:59:53,210
[Studentu] Dereference vienreiz, un tad darīt bulta, ka veidā?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Tātad (* koks) ir dereference reizi, -> vērtība

783
00:59:58,420 --> 01:00:05,960
gatavojas sniegt man vērtību mezglā, ka es esmu netieši norādot uz.

784
01:00:05,960 --> 01:00:11,980
Lai es varētu rakstīt arī to ** tree.value ja vēlaties, ka.

785
01:00:11,980 --> 01:00:18,490
Nu strādā.

786
01:00:18,490 --> 01:00:26,190
Ja tas ir gadījumā, tad es vēlos aicināt ievietot ar vērtību.

787
01:00:26,190 --> 01:00:32,590
Un kāda ir mana atjaunināts mezgla ** būs?

788
01:00:32,590 --> 01:00:39,440
Es gribu iet pa kreisi, lai ** tree.left būs mana kreisā.

789
01:00:39,440 --> 01:00:41,900
Un es gribu rādītāju uz šo lietu

790
01:00:41,900 --> 01:00:44,930
tā, ka, ja pa kreisi beidzas ar to nulles rādītājs,

791
01:00:44,930 --> 01:00:48,360
Es varu mainīt to norādīt uz manu jauno mezglu.

792
01:00:48,360 --> 01:00:51,460
>> Un otru lietu var būt ļoti līdzīgi.

793
01:00:51,460 --> 01:00:55,600
Pieņemsim faktiski padarīt ka ​​mana trīskāršu tiesības tagad.

794
01:00:55,600 --> 01:01:04,480
Ievietot vērtību, ja vērtība <(** koks). Vērtība.

795
01:01:04,480 --> 01:01:11,040
Tad mēs vēlamies, lai atjauninātu mūsu ** pa kreisi,

796
01:01:11,040 --> 01:01:17,030
cits mēs gribam, lai atjauninātu mūsu ** pa labi.

797
01:01:17,030 --> 01:01:22,540
[Studentu] Vai tas iegūtu rādītāju rādītāja?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Atcerieties, ka - ** tree.right ir mezglā zvaigzne.

799
01:01:30,940 --> 01:01:35,040
[Studentu, nesaprotami] >> Jā.

800
01:01:35,040 --> 01:01:41,140
** Tree.right ir kā šī rādītāja vai kaut ko.

801
01:01:41,140 --> 01:01:45,140
Tātad, ņemot rādītāju tam, ka dod man, ko es gribu

802
01:01:45,140 --> 01:01:50,090
gada rādītāja uz šo puisis.

803
01:01:50,090 --> 01:01:54,260
[Studentu] Vai mēs aiziet atkal kāpēc mēs izmantojam divas norādes?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Jā. Tātad - nē, jūs varat, un ka risinājums pirms

805
01:01:58,220 --> 01:02:04,540
bija veids, kā to dara bez darīt divas norādes.

806
01:02:04,540 --> 01:02:08,740
Jums ir nepieciešams, lai varētu saprast, izmantojot divus norādes,

807
01:02:08,740 --> 01:02:11,660
un tas ir tīrāks risinājums.

808
01:02:11,660 --> 01:02:16,090
Arī paziņojums, ka tas, kas notiek, ja mans koks -

809
01:02:16,090 --> 01:02:24,480
kas notiek, ja mana sakne ir Null? Kas notiek, ja man darīt šo lietu tieši šeit?

810
01:02:24,480 --> 01:02:30,540
Tātad mezglu * sakne = NULL, ievietojiet 4 stājas & saknes.

811
01:02:30,540 --> 01:02:35,110
Kas ir sakne būs pēc šo?

812
01:02:35,110 --> 01:02:37,470
[Studentu, nesaprotami] >> Jā.

813
01:02:37,470 --> 01:02:41,710
Sakne vērtība būs 4.

814
01:02:41,710 --> 01:02:45,510
Sakne kreisi būs nulle, sakņu tiesības būs nulle.

815
01:02:45,510 --> 01:02:49,490
Gadījumā, ja mēs neizturēja sakni pēc adreses,

816
01:02:49,490 --> 01:02:52,490
mēs nevarētu mainīt saknes.

817
01:02:52,490 --> 01:02:56,020
Gadījumā, ja koks - ja sakne ir nulle,

818
01:02:56,020 --> 01:02:58,410
mēs tikko bija atgriezties viltus. Tur nekas mēs varētu darīt.

819
01:02:58,410 --> 01:03:01,520
Mēs nevaram ievietot mezglu tukšā koku.

820
01:03:01,520 --> 01:03:06,810
Bet tagad mēs varam, mēs tikai veikt tukšu koku uz vienu mezglu koka.

821
01:03:06,810 --> 01:03:13,400
Kas parasti ir paredzamais veids, ka tas ir paredzēts strādāt.

822
01:03:13,400 --> 01:03:21,610
>> Turklāt, tas ir ievērojami īsāks nekā

823
01:03:21,610 --> 01:03:26,240
arī sekotu mātes, un tāpēc jums atkārtot leju visu ceļu.

824
01:03:26,240 --> 01:03:30,140
Tagad man ir mana vecākiem, un man vienkārši ir mana mātes tiesības rādītāju uz whatever.

825
01:03:30,140 --> 01:03:35,640
Tā vietā, ja mēs to izdarīja iteratīvi, tas lūdzu būt pati ideja ar kamēr cilpa.

826
01:03:35,640 --> 01:03:38,100
Bet tā vietā, lai risinātu ar manu mātes rādītājs,

827
01:03:38,100 --> 01:03:40,600
vietā mans pašreizējais rādītājs būtu lieta

828
01:03:40,600 --> 01:03:43,790
ka es esmu tieši mainīt norādīt savu jauno mezglu.

829
01:03:43,790 --> 01:03:46,090
Man nav jātiek galā ar to, vai tas ir vērstas virzienā pa kreisi.

830
01:03:46,090 --> 01:03:48,810
Man nav jātiek galā ar to, vai tas ir vērsta uz labo pusi.

831
01:03:48,810 --> 01:04:00,860
Tas ir tikai kāds šis rādītājs ir, es esmu gatavojas noteikt to norādīt uz savu jauno mezglu.

832
01:04:00,860 --> 01:04:05,740
Ikvienam jāsaprot, kā tā darbojas?

833
01:04:05,740 --> 01:04:09,460
Ja ne, kāpēc mēs vēlamies darīt to šādā veidā,

834
01:04:09,460 --> 01:04:14,920
bet vismaz, ka tas darbojas kā risinājumu?

835
01:04:14,920 --> 01:04:17,110
[Studentu] Ja mēs atgrieztos taisnība?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Tas ir iespējams šeit.

837
01:04:21,550 --> 01:04:26,690
Ja mēs pareizi ievietojiet to, atgriešanās patiess.

838
01:04:26,690 --> 01:04:32,010
Cits, noteikti šeit mēs esam gatavojas vēlaties atgriezties jebkādos ievietot atdevi.

839
01:04:32,010 --> 01:04:35,950
>> Un, kas ir īpašs par šo rekursīvo funkciju?

840
01:04:35,950 --> 01:04:43,010
Tas ir astes rekursīvs, tik ilgi, kamēr mēs apkopotu ar kādu optimizāciju,

841
01:04:43,010 --> 01:04:48,060
tā atzīst, ka, un jūs nekad get kaudze pārplūdes no tā,

842
01:04:48,060 --> 01:04:53,230
pat ja mūsu koku augstums ir 10000 vai 10 miljoni.

843
01:04:53,230 --> 01:04:55,630
[Studentu, nesaprotami]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Es domāju, tas to Dash - vai ko optimizācija līmenī

845
01:05:00,310 --> 01:05:03,820
ir nepieciešams, lai asti rekursijas jāatzīst.

846
01:05:03,820 --> 01:05:09,350
Es domāju, tā atzīst - GCC un šķindēt

847
01:05:09,350 --> 01:05:12,610
ir arī dažādas nozīmes saviem optimizācijas līmeni.

848
01:05:12,610 --> 01:05:17,870
Es gribu teikt, tas ir DashO 2, lai pārliecinātos, ka tas atzīst asti rekursijas.

849
01:05:17,870 --> 01:05:27,880
Bet mēs - tu varētu uzbūvēt, piemēram, Fibonocci piemēram, vai kaut ko.

850
01:05:27,880 --> 01:05:30,030
Tas nav viegli pārbaudīt ar šo, jo tas ir grūti salikt

851
01:05:30,030 --> 01:05:32,600
binārs koks, kas ir tik liels.

852
01:05:32,600 --> 01:05:37,140
Bet jā, es domāju, ka tas DashO 2, kas

853
01:05:37,140 --> 01:05:40,580
ja jūs sastādīt ar 2 DashO, tas būs meklēt asti rekursijas

854
01:05:40,580 --> 01:05:54,030
un optimizēt ka ārā.

855
01:05:54,030 --> 01:05:58,190
Iesim atpakaļ uz - ievietot burtiski pēdējā lieta tai ir vajadzīga.

856
01:05:58,190 --> 01:06:04,900
Iesim atpakaļ uz ieliktni nekā šeit

857
01:06:04,900 --> 01:06:07,840
kur mēs esam gatavojas darīt to pašu domu.

858
01:06:07,840 --> 01:06:14,340
Tas būs vēl ir slikti ir, jo nevar pilnībā rīkoties

859
01:06:14,340 --> 01:06:17,940
kad saknes pati ir nulle, vai pagātnes ieraksts ir nulle,

860
01:06:17,940 --> 01:06:20,060
bet nevis nodarbojas ar mātes rādītājs,

861
01:06:20,060 --> 01:06:27,430
pieņemsim piemērot tādu pašu loģiku saglabājot norādes uz norādes.

862
01:06:27,430 --> 01:06:35,580
Ja šeit mēs turpinām mūsu mezglā ** pašreizējo,

863
01:06:35,580 --> 01:06:37,860
un mums nav nepieciešams, lai sekotu tiesības vairs,

864
01:06:37,860 --> 01:06:47,190
bet mezglu ** pašreizējo = & koks.

865
01:06:47,190 --> 01:06:54,800
Un tagad mūsu kamēr cilpa būs kamēr * hronoloģija nav vienāds null.

866
01:06:54,800 --> 01:07:00,270
Nav nepieciešams sekot vecāku vairs.

867
01:07:00,270 --> 01:07:04,180
Nav nepieciešams sekot līdzi pa kreisi un pa labi.

868
01:07:04,180 --> 01:07:10,190
Un es aicinu to temp, jo mēs esam jau izmanto temp.

869
01:07:10,190 --> 01:07:17,200
Labi. Tātad, ja (vērtība> * temperatūra),

870
01:07:17,200 --> 01:07:24,010
tad & (* temp) -> tiesības

871
01:07:24,010 --> 01:07:29,250
cits temp = & (* temp) -> pa kreisi.

872
01:07:29,250 --> 01:07:32,730
Un tagad, šajā brīdī, kad šī kamēr cilpa,

873
01:07:32,730 --> 01:07:36,380
Es tikai darīt, jo varbūt tas ir vieglāk domāt par iteratīvi nekā rekursīvi,

874
01:07:36,380 --> 01:07:39,010
bet pēc šī kamēr cilpa,

875
01:07:39,010 --> 01:07:43,820
* Temp ir rādītājs mēs vēlamies mainīt.

876
01:07:43,820 --> 01:07:48,960
>> Pirms mums bija vecāks, un mēs vēlējāmies, lai mainītu vai nu mātes kreisi vai vecākus labi,

877
01:07:48,960 --> 01:07:51,310
bet, ja mēs gribam mainīt vecāku tiesības,

878
01:07:51,310 --> 01:07:54,550
tad * temp ir mātes tiesības, un mēs varam to mainīt tieši.

879
01:07:54,550 --> 01:08:05,860
Tātad šeit lejā, mēs varam darīt * temp = newnode, un tas arī viss.

880
01:08:05,860 --> 01:08:09,540
Tātad paziņojums, viss, ko mēs darījām, tas bija izņemt rindas kodu.

881
01:08:09,540 --> 01:08:14,770
Lai sekotu no mātes visu, kas ir papildu pūles.

882
01:08:14,770 --> 01:08:18,689
Lūk, ja mēs vienkārši sekot rādītāju uz rādītāja,

883
01:08:18,689 --> 01:08:22,990
un pat tad, ja mēs vēlējāmies, lai atbrīvotos no visiem šiem cirtaini bikšturi tagad,

884
01:08:22,990 --> 01:08:27,170
lai tas izskatās īsāks.

885
01:08:27,170 --> 01:08:32,529
Tas šobrīd ir tieši tāds pats risinājums,

886
01:08:32,529 --> 01:08:38,210
bet mazāk rindas kods.

887
01:08:38,210 --> 01:08:41,229
Kad jūs sākat atzīstot to kā derīgu risinājumu,

888
01:08:41,229 --> 01:08:43,529
tas ir arī vieglāk iemesla apmēram nekā, piemēram, labi,

889
01:08:43,529 --> 01:08:45,779
kāpēc man ir šī karogu int tiesības?

890
01:08:45,779 --> 01:08:49,290
Ko tas nozīmē? Ak, tas nozīmētu, ka

891
01:08:49,290 --> 01:08:51,370
Katru reizi, kad es iet labi, man ir nepieciešams, lai uzstādītu to,

892
01:08:51,370 --> 01:08:53,819
cits ja es eju pa kreisi man ir nepieciešams, lai uzstādītu to uz nulli.

893
01:08:53,819 --> 01:09:04,060
Lūk, man nav iemesla par to, tas ir tikai vieglāk domāt par.

894
01:09:04,060 --> 01:09:06,710
Jautājumi?

895
01:09:06,710 --> 01:09:16,290
[Studentu, nesaprotami] >> Jā.

896
01:09:16,290 --> 01:09:23,359
Labi, tāpēc pēdējā bit -

897
01:09:23,359 --> 01:09:28,080
Es domāju viens ātrs un vienkāršs funkciju mēs varam darīt, ir,

898
01:09:28,080 --> 01:09:34,910
let's - kopā, es domāju, izmēģināt un uzrakstīt satur funkcijas

899
01:09:34,910 --> 01:09:38,899
kas nav vienalga, vai tas ir bināro meklēšanas koku.

900
01:09:38,899 --> 01:09:43,770
Tas satur funkcija būtu atgriezties true

901
01:09:43,770 --> 01:09:58,330
ja nekur šajā vispārējā bināro koks ir vērtība, mēs meklējam.

902
01:09:58,330 --> 01:10:02,520
Tāpēc pieņemsim vispirms to darīt rekursīvi un tad mēs darīsim to iteratīvi.

903
01:10:02,520 --> 01:10:07,300
Mēs faktiski var vienkārši darīt to kopā, jo tas būs ļoti īss.

904
01:10:07,300 --> 01:10:11,510
>> Kāda ir mana bāzes scenārijs būs?

905
01:10:11,510 --> 01:10:13,890
[Studentu, nesaprotami]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Tātad, ja (koks == NULL), tad ko?

907
01:10:18,230 --> 01:10:22,740
[Studentu] atgriezties viltus.

908
01:10:22,740 --> 01:10:26,160
[Bowden] cits, labi, man nav nepieciešams cits.

909
01:10:26,160 --> 01:10:30,250
Ja bija mana citu gadījumu.

910
01:10:30,250 --> 01:10:32,450
[Studentu] Tree vērtība? >> Jā.

911
01:10:32,450 --> 01:10:36,430
Tātad, ja (koks-> vērtība == vērtība.

912
01:10:36,430 --> 01:10:39,920
Pamanīt mēs esam atpakaļ uz mezglu *, nevis mezgls ** s?

913
01:10:39,920 --> 01:10:42,990
Satur nekad nepieciešams izmantot mezglu **,

914
01:10:42,990 --> 01:10:45,480
jo mēs neesam modificējot norādes.

915
01:10:45,480 --> 01:10:50,540
Mēs esam tikai šķērso tos.

916
01:10:50,540 --> 01:10:53,830
Ja tas notiks, tad mēs vēlamies atgriezties taisnība.

917
01:10:53,830 --> 01:10:58,270
Cits mēs vēlamies, lai šķērsotu bērnus.

918
01:10:58,270 --> 01:11:02,620
Tāpēc mēs nevaram spriest par to, vai viss pa kreisi, ir mazāks

919
01:11:02,620 --> 01:11:05,390
un viss pa labi ir lielāks.

920
01:11:05,390 --> 01:11:09,590
Tātad, kas ir mūsu nosacījums būs šeit - vai, ko mēs gatavojamies darīt?

921
01:11:09,590 --> 01:11:11,840
[Studentu, nesaprotami] >> Jā.

922
01:11:11,840 --> 01:11:17,400
Atgriešanās satur (vērtība, koks-> pa kreisi)

923
01:11:17,400 --> 01:11:26,860
vai satur (vērtība, koks-> pa labi). Un tas arī viss.

924
01:11:26,860 --> 01:11:29,080
Un paziņojums ir daži īssavienojumu novērtējumu,

925
01:11:29,080 --> 01:11:32,520
kur, ja mēs gadās atrast vērtību kreisajā koku,

926
01:11:32,520 --> 01:11:36,820
mēs nekad jāmeklē īstajā koku.

927
01:11:36,820 --> 01:11:40,430
Tas ir viss funkcija.

928
01:11:40,430 --> 01:11:43,690
Tagad pieņemsim to darīt iteratīvi,

929
01:11:43,690 --> 01:11:48,060
kas būs mazāk jauki.

930
01:11:48,060 --> 01:11:54,750
Mēs ņemšu parasto sākumu mezglu * cur = koku.

931
01:11:54,750 --> 01:12:03,250
Kamēr (ar pašreizējo! = NULL).

932
01:12:03,250 --> 01:12:08,600
Ātri gatavojas redzēt problēmu.

933
01:12:08,600 --> 01:12:12,250
Ja cur - šeit, ja mēs kādreiz izkļūt no šīs,

934
01:12:12,250 --> 01:12:16,020
tad mēs esam izsīkšanai lietas, lai apskatīt, tāpēc atgriezties viltus.

935
01:12:16,020 --> 01:12:24,810
Ja (paš-> vērtība == vērtība), atgriešanās patiess.

936
01:12:24,810 --> 01:12:32,910
Tāpēc tagad mēs esam vietā -

937
01:12:32,910 --> 01:12:36,250
Mēs nezinām, vai mēs gribam iet pa kreisi vai pa labi.

938
01:12:36,250 --> 01:12:44,590
Tātad patvaļīgi, pieņemsim tikai iet pa kreisi.

939
01:12:44,590 --> 01:12:47,910
Es esmu protams uzskriet jautājumu, kur es esmu pilnīgi pamesta viss -

940
01:12:47,910 --> 01:12:50,760
Es tikai kādreiz pārbauda kreiso pusi koku.

941
01:12:50,760 --> 01:12:56,050
Es nekad pārbaudīt visu, kas ir tiesības bērns neko.

942
01:12:56,050 --> 01:13:00,910
Kā es varu noteikt šo?

943
01:13:00,910 --> 01:13:05,260
[Studentu] Jums ir sekot kreisi un pa labi kaudze.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Jā. Tāpēc pieņemsim, būtu

945
01:13:13,710 --> 01:13:32,360
struktūrai sarakstu, mezglu * n, un tad mezglu ** tālāk?

946
01:13:32,360 --> 01:13:40,240
Es domāju, ka darbojas naudas sodu.

947
01:13:40,240 --> 01:13:45,940
Mēs vēlamies, lai iet pa kreisi, vai let's - šeit.

948
01:13:45,940 --> 01:13:54,350
Struct saraksts saraksts =, tas būs sākums

949
01:13:54,350 --> 01:13:58,170
veic šo struct sarakstā.

950
01:13:58,170 --> 01:14:04,040
* Saraksta = NULL. Tāpēc, ka būs mūsu saistīts saraksts

951
01:14:04,040 --> 01:14:08,430
gada subtrees ka mēs esam izlaidis vairāk.

952
01:14:08,430 --> 01:14:13,800
Mēs gatavojamies, lai šķērsotu pa kreisi tagad,

953
01:14:13,800 --> 01:14:17,870
bet, jo mēs neizbēgami jānāk atpakaļ uz labo pusi,

954
01:14:17,870 --> 01:14:26,140
Mēs ejam, lai saglabātu labo pusi iekšā mūsu struct saraksta.

955
01:14:26,140 --> 01:14:32,620
Tad mums būs new_list vai struktūrai,

956
01:14:32,620 --> 01:14:41,080
struktūrai saraksts *, new_list = malloc (sizeof (saraksts)).

957
01:14:41,080 --> 01:14:44,920
Es esmu gatavojas ignorēt kļūdu pārbaudot, bet jums vajadzētu pārbaudīt, lai redzētu, ja tas ir null.

958
01:14:44,920 --> 01:14:50,540
New_list mezglu tas notiek, lai norādītu uz -

959
01:14:50,540 --> 01:14:56,890
ak, tāpēc es gribēju to šeit. Tas notiek, lai norādītu uz otro struct sarakstā.

960
01:14:56,890 --> 01:15:02,380
Tas ir tikai kā saistīts sarakstus darbu.

961
01:15:02,380 --> 01:15:04,810
Tas ir tas pats kā int saistīts saraksts

962
01:15:04,810 --> 01:15:06,960
izņemot mēs esam tikai aizstājot int ar mezglu *.

963
01:15:06,960 --> 01:15:11,040
Tas ir tieši tas pats.

964
01:15:11,040 --> 01:15:15,100
Tātad new_list, vērtību mūsu new_list mezglā,

965
01:15:15,100 --> 01:15:19,120
būs pašreizējo-> labi.

966
01:15:19,120 --> 01:15:24,280
Vērtība mūsu new_list-> nākamā būs mūsu sākotnējais saraksts,

967
01:15:24,280 --> 01:15:30,760
un tad mēs esam gatavojas atjaunināt savu sarakstu, lai norādītu uz new_list.

968
01:15:30,760 --> 01:15:33,650
>> Tagad mums ir nepieciešama sava veida veidā velkot lietas,

969
01:15:33,650 --> 01:15:37,020
kā mēs ir pārvieto visu kreisi apakškoka.

970
01:15:37,020 --> 01:15:40,480
Tagad mums ir nepieciešams, lai pull sīkumi no tā,

971
01:15:40,480 --> 01:15:43,850
tāpat hronoloģija ir Null, mēs negribam, lai tikai atgriezties viltus.

972
01:15:43,850 --> 01:15:50,370
Mēs vēlamies, lai tagad vilktu ārā mūsu jauno sarakstu.

973
01:15:50,370 --> 01:15:53,690
Ērts veids, kā to izdarīt - labi, patiesībā, tur ir vairāki veidi, kā to izdarīt.

974
01:15:53,690 --> 01:15:56,680
Kāds ir ieteikums?

975
01:15:56,680 --> 01:15:58,790
Kur man būtu jādara tas, vai un kā man būtu darīt?

976
01:15:58,790 --> 01:16:08,010
Mums ir tikai pāris minūtes, bet kādi ieteikumi?

977
01:16:08,010 --> 01:16:14,750
Vietā - vienā veidā, nevis mūsu stāvoklī ir, bet,

978
01:16:14,750 --> 01:16:17,090
ko mēs šobrīd meklē nav Null,

979
01:16:17,090 --> 01:16:22,340
vietā mēs turpināsim iet līdz mūsu saraksts pats par sevi ir nulle.

980
01:16:22,340 --> 01:16:25,680
Tātad, ja mūsu saraksts beidzas ar to, null,

981
01:16:25,680 --> 01:16:30,680
tad mēs esam izsīkšanai lietas meklēt, lai meklētu vairāk.

982
01:16:30,680 --> 01:16:39,860
Bet tas nozīmē, ka pirmā lieta, kas mūsu sarakstā ir tikai gatavojas būt pirmais mezgls.

983
01:16:39,860 --> 01:16:49,730
Pati pirmā lieta būs - mums vairs nav nepieciešams, lai redzētu, ka.

984
01:16:49,730 --> 01:16:58,710
Tā saraksts-> n būs mūsu koku.

985
01:16:58,710 --> 01:17:02,860
saraksts-> blakus būs nulle.

986
01:17:02,860 --> 01:17:07,580
Un tagad, kamēr saraksts nav vienāds null.

987
01:17:07,580 --> 01:17:11,610
Cur gatavojas pull kaut ko no mūsu saraksta.

988
01:17:11,610 --> 01:17:13,500
Tāpēc pašreizējo gatavojas vienlīdzīgu saraksta-> n.

989
01:17:13,500 --> 01:17:20,850
Un tad saraksts ir gatavojas vienlīdzīgu saraksta-> N, vai saraksta-> nākamo.

990
01:17:20,850 --> 01:17:23,480
Tātad, ja ar pašreizējo vērtība ir vērtība.

991
01:17:23,480 --> 01:17:28,790
Tagad mēs varam pievienot gan mūsu labo rādītāju un mūsu kreiso šautriņu

992
01:17:28,790 --> 01:17:32,900
kamēr viņi nav null.

993
01:17:32,900 --> 01:17:36,390
Noteikti šeit, es domāju, mēs būtu jādara, ka pirmajā vietā.

994
01:17:36,390 --> 01:17:44,080
Ja (paš-> labi! = NULL)

995
01:17:44,080 --> 01:17:56,380
tad mēs ievietot šī mezglu mūsu sarakstā.

996
01:17:56,380 --> 01:17:59,290
Ja (paš-> pa kreisi), tas ir mazliet papildus darbu, bet tas ir labi.

997
01:17:59,290 --> 01:18:02,690
Ja (paš-> kreisi! = NULL),

998
01:18:02,690 --> 01:18:14,310
un mēs ejam, lai ievietotu palikuši mūsu saistīts saraksts,

999
01:18:14,310 --> 01:18:19,700
un kas būtu tā.

1000
01:18:19,700 --> 01:18:22,670
Mēs atkārtot - kamēr mums ir kaut kas mūsu sarakstā,

1001
01:18:22,670 --> 01:18:26,640
Mums ir cits mezgls aplūkot.

1002
01:18:26,640 --> 01:18:28,920
Tāpēc mēs skatāmies šo mezglu,

1003
01:18:28,920 --> 01:18:31,390
mēs iepriekš mūsu sarakstu uz nākamo.

1004
01:18:31,390 --> 01:18:34,060
Ja tas mezgls ir vērtība, mēs meklējam, mēs varam atgriezties taisnība.

1005
01:18:34,060 --> 01:18:37,640
Cits ievietot gan mūsu kreiso un labo subtrees,

1006
01:18:37,640 --> 01:18:40,510
kamēr viņi nav nulle, mūsu sarakstā

1007
01:18:40,510 --> 01:18:43,120
lai mēs neizbēgami iet pār tiem.

1008
01:18:43,120 --> 01:18:45,160
Tātad, ja tie nav null,

1009
01:18:45,160 --> 01:18:47,950
ja mūsu saknes rādītājs norādīja uz divām lietām,

1010
01:18:47,950 --> 01:18:51,670
tad vispirms mēs velk kaut kas tik mūsu saraksts beidzas ar to null.

1011
01:18:51,670 --> 01:18:56,890
Un tad mēs ieliekam divas lietas atpakaļ, tāpēc tagad mūsu saraksts ir 2 izmēru.

1012
01:18:56,890 --> 01:19:00,030
Tad mēs ejam uz cilpas atpakaļ uz augšu un mēs esam tikai gatavojas pull,

1013
01:19:00,030 --> 01:19:04,250
teiksim, kreiso peles mūsu saknes mezgla.

1014
01:19:04,250 --> 01:19:07,730
Un tas būs tikai glabāt notiek, mēs galu galā looping pāri visam.

1015
01:19:07,730 --> 01:19:11,280
>> Ievērojiet, ka šī bija ievērojami sarežģītāks

1016
01:19:11,280 --> 01:19:14,160
kas rekursīvs risinājumu.

1017
01:19:14,160 --> 01:19:17,260
Un es esmu teica vairākas reizes

1018
01:19:17,260 --> 01:19:25,120
ka rekursīvas risinājums parasti ir daudz kopīga ar iteratīvu risinājumu.

1019
01:19:25,120 --> 01:19:30,820
Šeit tas ir tieši tas, ko rekursīvas risinājums dara.

1020
01:19:30,820 --> 01:19:36,740
Vienīgā izmaiņa ir, ka tā vietā netieši izmantojot steku, programma kaudze,

1021
01:19:36,740 --> 01:19:40,840
kā savu ceļu, lai sekotu, ko mezgliem jums joprojām ir nepieciešams apmeklēt,

1022
01:19:40,840 --> 01:19:45,430
Tagad jums ir skaidri izmantot saistīto sarakstu.

1023
01:19:45,430 --> 01:19:49,070
Abos gadījumos jums ir sekot kāda mezgla vēl ir apmeklējis.

1024
01:19:49,070 --> 01:19:51,790
Šajā rekursīvs gadījumā tas ir tikai vieglāk, jo kaudze

1025
01:19:51,790 --> 01:19:57,100
tiek īstenots, lai jūs kā programmas kaudze.

1026
01:19:57,100 --> 01:19:59,550
Ievērojiet, ka šī saistīts saraksts, tas ir kaudze.

1027
01:19:59,550 --> 01:20:01,580
Lai ko mēs tikko likts uz skursteņa

1028
01:20:01,580 --> 01:20:09,960
uzreiz, ko mēs ejam, lai pull off kaudze apmeklēt nākamo.

1029
01:20:09,960 --> 01:20:14,380
Mēs esam no laika, bet kādi jautājumi?

1030
01:20:14,380 --> 01:20:23,530
[Studentu, nesaprotami]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Jā. Tātad, ja mums ir saistīts saraksts,

1032
01:20:27,790 --> 01:20:30,150
strāva gatavojas norādīt uz šo puisis,

1033
01:20:30,150 --> 01:20:34,690
un tagad mēs esam tikai padziļinot mūsu saistīts saraksts koncentrēties uz šo puisis.

1034
01:20:34,690 --> 01:20:44,200
Mēs šķērso pa saistīts saraksts šajā rindā.

1035
01:20:44,200 --> 01:20:51,200
Un tad es domāju, mēs būtu bez mūsu saistīts saraksts un stuff

1036
01:20:51,200 --> 01:20:53,880
reizi pirms atgriešanās patiess vai nepatiess, mums ir nepieciešams, lai

1037
01:20:53,880 --> 01:20:57,360
atkārtot pār mūsu saistīts saraksts un vienmēr leju šeit, es domāju,

1038
01:20:57,360 --> 01:21:03,900
ja mēs cur tiesības nav vienāds, pievienojiet to, tāpēc tagad mēs vēlamies, lai atbrīvotu

1039
01:21:03,900 --> 01:21:09,600
cur jo, labi, vai mēs pilnīgi aizmirst par sarakstu? Yeah.

1040
01:21:09,600 --> 01:21:12,880
Tātad tas, ko mēs vēlamies darīt šeit.

1041
01:21:12,880 --> 01:21:16,730
Kur ir rādītājs?

1042
01:21:16,730 --> 01:21:23,320
Cur bija tad - mēs vēlamies struct sarakstā * 10 vienāds sarakstu nākamo.

1043
01:21:23,320 --> 01:21:29,240
Bezmaksas saraksts, saraksts = temp.

1044
01:21:29,240 --> 01:21:32,820
Un gadījumā, ja mēs atgrieztos taisnība, mums ir nepieciešams, lai atkārtot

1045
01:21:32,820 --> 01:21:37,050
atlikušajā mūsu saistīts saraksts atbrīvojot lietas.

1046
01:21:37,050 --> 01:21:39,700
Jauka lieta par rekursīvas risinājums ir atbrīvot lietas

1047
01:21:39,700 --> 01:21:44,930
nozīmē tikai popping factorings off kaudze, kas notiks par jums.

1048
01:21:44,930 --> 01:21:50,720
Tāpēc mēs esam aizgājuši no kaut kas ir, piemēram, 3 līnijas grūti domāt, par kodu

1049
01:21:50,720 --> 01:21:57,520
lai kaut kas ir ievērojami daudz vairāk grūti domāt-par rindas kodu.

1050
01:21:57,520 --> 01:22:00,620
Kādi jautājumi?

1051
01:22:00,620 --> 01:22:08,760
Labi. Mēs esam labi. Atā!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]