1
00:00:00,000 --> 00:00:11,460

2
00:00:11,460 --> 00:00:12,250
>> David MALAN: Lahat ng karapatan.

3
00:00:12,250 --> 00:00:13,860
Maligayang pagbalik sa CS50.

4
00:00:13,860 --> 00:00:16,190
Ito ang simula ng linggo 8.

5
00:00:16,190 --> 00:00:21,320
At isipin ang problema na hanay 5 natapos na
na may isang maliit na bit ng isang hamon.

6
00:00:21,320 --> 00:00:25,210
Kaya ipagpalagay na nakuhang muli ang lahat ng iyong
pagtuturo Fellows at CA ng litrato

7
00:00:25,210 --> 00:00:30,480
sa file card.raw, ikaw ay karapat-dapat
sa ngayon mahanap ang lahat ng mga tao, at

8
00:00:30,480 --> 00:00:34,510
isa masuwerteng nagwagi ay lumakad tahanan sa isa
ng mga bagay na ito, ang mga hakbang paggalaw

9
00:00:34,510 --> 00:00:37,450
aparato na maaari mong gamitin para sa final
mga proyekto, halimbawa.

10
00:00:37,450 --> 00:00:39,860
>> Na ito, sa bawat taon, ay humahantong sa
ng kaunting creepiness.

11
00:00:39,860 --> 00:00:43,480
At kung ano ang kaya naisip ko na gusto kong gawin ay ibahagi
sa iyo ang ilan sa mga tala na mayroon

12
00:00:43,480 --> 00:00:47,370
nawala na pabalik-balik sa ibabaw
ang kawani ng listahan ng mga late.

13
00:00:47,370 --> 00:00:51,110
Halimbawa, lamang kagabi, quote
magpanipi, mula sa isa sa mga tauhan

14
00:00:51,110 --> 00:00:55,000
mga miyembro, "ko lang ay nagkaroon ng isang mag-aaral magpatumba
sa aking pinto na kumuha ng larawan sa akin.

15
00:00:55,000 --> 00:00:59,020
Stalkers, Sinasabi ko sa iyo. "Pagsisimula off
medyo mapaglarawan at pagkatapos namin inilipat

16
00:00:59,020 --> 00:01:02,830
on sa, isang oras o kaya mamaya, "ako ay nagkaroon ng isang
mag-aaral ng paghihintay para sa akin pagkatapos ng seksyon

17
00:01:02,830 --> 00:01:06,080
at siya ay nagkaroon ng lahat ng aming mga pangalan at larawan
sa ilang mga sheet ng papel. "Lahat ng karapatan.

18
00:01:06,080 --> 00:01:09,230
Kaya isinaayos, ngunit hindi
lahat na katakut-takot pa.

19
00:01:09,230 --> 00:01:12,520
>> Pagkatapos, "ako ay sa labas ng bayan sa pagtatapos ng linggo na ito,
at kapag ang nakuha ko pabalik, nagkaroon ng isa sa

20
00:01:12,520 --> 00:01:12,630
ko

21
00:01:12,630 --> 00:01:16,740
bedroom. "[tawa]

22
00:01:16,740 --> 00:01:20,410
David MALAN: Susunod na quote mula sa isang kawani
miyembro, "isang mag-aaral ang dumating sa aking bahay sa

23
00:01:20,410 --> 00:01:25,330
Somerville sa 4:00 ito umaga. "Susunod
staff, "ang nakuha ko sa aking hotel na ito sa San

24
00:01:25,330 --> 00:01:30,016
Francisco at isang mag-aaral ay na naghihintay para sa
sa akin sa lobby na may tatlong DSLRs. "

25
00:01:30,016 --> 00:01:31,510
Uri ng camera.

26
00:01:31,510 --> 00:01:34,980
"Hindi ako kahit na sa mga kawani na ito semestre,
ngunit ang mag-aaral ng isang sinira sa aking bahay na ito

27
00:01:34,980 --> 00:01:40,480
umaga at naitala ang buong bagay
gamit ang Google Glass. "At pagkatapos ay bilang wakas,

28
00:01:40,480 --> 00:01:43,650
"Hindi bababa sa 12 mga tao ay sabik
naghihintay para sa akin kapag ang nakuha ko out ng aking

29
00:01:43,650 --> 00:01:44,800
Limo, at pagkatapos ay ako

30
00:01:44,800 --> 00:01:46,970
woke up. "Lahat ng karapatan.

31
00:01:46,970 --> 00:01:57,690
Kaya kabilang sa mga litrato, bilang maaari mong
pagkuhang muli, ay kapwa ito dito, kung sino ka

32
00:01:57,690 --> 00:02:01,850
maaaring malaman bilang Milo Saging, nakatira
may Lauren Carvalho, ang aming ulo

33
00:02:01,850 --> 00:02:02,905
pagtuturo Fellow.

34
00:02:02,905 --> 00:02:05,170
Milo, Milo, halika batang lalaki.

35
00:02:05,170 --> 00:02:06,320
Milo.

36
00:02:06,320 --> 00:02:08,650
Milo.

37
00:02:08,650 --> 00:02:12,230
Tututol ka, siya suot Google Glass, kaya
ipapakita namin sa iyo ang lahat ng ito pagkatapos.

38
00:02:12,230 --> 00:02:16,190
Kaya ito ay Milo kung nais mong
tumagal ng isang larawan na kasama niya Pagkatapos.

39
00:02:16,190 --> 00:02:18,240
Kung gusto mo upang tumingin out
sa madla doon.

40
00:02:18,240 --> 00:02:19,430
OK.

41
00:02:19,430 --> 00:02:20,200
Iyan ay mahusay na footage.

42
00:02:20,200 --> 00:02:22,556
Well, Milo Saging.

43
00:02:22,556 --> 00:02:23,941
Oh, huwag gawin iyon.

44
00:02:23,941 --> 00:02:29,020
>> [Tawa]

45
00:02:29,020 --> 00:02:29,470
>> OK.

46
00:02:29,470 --> 00:02:34,550
Kaya ang salita pagkatapos ay sa kung ano ang namamalagi maaga,
dahil bilang namin magsimula sa transition na ito,

47
00:02:34,550 --> 00:02:38,410
ngayong linggo partikular, mula sa C sa isang
command line kapaligiran sa PHP at

48
00:02:38,410 --> 00:02:42,720
JavaScript at SQL at HTML at CSS sa
isang web-based na kapaligiran, kami ay magiging

49
00:02:42,720 --> 00:02:44,490
equipping sa iyo ng lahat ng mga
higit na kaalaman para sa

50
00:02:44,490 --> 00:02:46,010
potensyal na huling proyekto.

51
00:02:46,010 --> 00:02:49,240
Patungo sa layuning iyon, ang mga kurso ay may
tradisyon ng mga may hawak na seminar kung saan

52
00:02:49,240 --> 00:02:50,950
ay tanghential sa mga paksa
sa kurso.

53
00:02:50,950 --> 00:02:54,330
Sobra na may kaugnayan sa programming at upang
app development at iba pa, ngunit

54
00:02:54,330 --> 00:02:57,010
hindi kinakailangang ginalugad sa pamamagitan ng
sariling syllabus ang kurso ni.

55
00:02:57,010 --> 00:03:00,250
>> Kaya kung maaari kang maging interesado sa isa
o higit pa sa mga seminar na ito taon,

56
00:03:00,250 --> 00:03:02,530
magparehistro sa cs50.net/seminar.

57
00:03:02,530 --> 00:03:06,170
Mayroong mas lumang seminar
sa cs50.net/seminars.

58
00:03:06,170 --> 00:03:10,620
At sa roster kaya malayo para sa taong ito
ang mga kamangha-manghang mga Web Apps na may Ruby sa

59
00:03:10,620 --> 00:03:13,580
Daang-bakal, na kung saan ay isang alternatibo
wika na PHP.

60
00:03:13,580 --> 00:03:14,900
Computational lingguwistika.

61
00:03:14,900 --> 00:03:18,710
Panimula sa iOS, kung saan ay ang
platform na ginamit para sa iPhone at

62
00:03:18,710 --> 00:03:19,850
iPad-develop.

63
00:03:19,850 --> 00:03:22,890
JavaScript para sa Web Apps, tatalakayin namin
na, ngunit sa mga seminar na ito, pupunta ka

64
00:03:22,890 --> 00:03:24,070
mas detalyado.

65
00:03:24,070 --> 00:03:27,390
>> Tumalon Paggalaw, kaya ipapakita namin talagang makakuha ng ilang
ng ating mga kaibigan mula sa tumalon Motion,

66
00:03:27,390 --> 00:03:29,160
ang kumpanya mismo, sumali sa amin.

67
00:03:29,160 --> 00:03:31,800
Bukas, sa katunayan, upang magbigay ng
isang hands-on seminar, kung

68
00:03:31,800 --> 00:03:33,320
ng interes sa iyo.

69
00:03:33,320 --> 00:03:38,770
Meteor.js, isang alternatibong pamamaraan para
gamit ang JavaScript ay hindi sa isang browser,

70
00:03:38,770 --> 00:03:39,970
ngunit sa isang server.

71
00:03:39,970 --> 00:03:42,110
Node.js, na higit na mas
sa na ugat pati na rin.

72
00:03:42,110 --> 00:03:43,650
Sleek Android Design.

73
00:03:43,650 --> 00:03:46,990
Android pagiging isang napaka-tanyag na alternatibo
sa iOS at Windows Phone

74
00:03:46,990 --> 00:03:48,790
at iba pang mga mobile platform.

75
00:03:48,790 --> 00:03:51,180
At Web Security Aktibo Defense.

76
00:03:51,180 --> 00:03:54,590
>> Kaya sa katunayan, kung nais mong
upang makisali sa mga ito, ipaalam sa akin

77
00:03:54,590 --> 00:03:55,840
gumawa ng tala ng mga ito.

78
00:03:55,840 --> 00:03:57,790
Kami ay labis na nasisiyahan na sabihin na
ang aming mga kaibigan sa tumalon

79
00:03:57,790 --> 00:03:59,140
Paggalaw, na isang startup -

80
00:03:59,140 --> 00:04:01,300
aparato na ito ay talagang lamang ay dumating
out ng ilang mga buwan na nakalipas -

81
00:04:01,300 --> 00:04:05,960
si marikit donasyon 30 tulad na mga aparato
sa klase para sa maraming mga mag-aaral, kung

82
00:04:05,960 --> 00:04:08,670
gusto mong hiramin ang hardware
patungo sa katapusan ng semestre at gamitin ito para sa

83
00:04:08,670 --> 00:04:10,390
isang aktwal na huling proyekto.

84
00:04:10,390 --> 00:04:11,890
Sinusuportahan ng mga ito ay may bilang ng mga wika.

85
00:04:11,890 --> 00:04:16,040
Wala sa mga ito C, wala sa kanila ang PHP, kaya
Napagtanto ng isa o higit pa sa mga seminar na ito

86
00:04:16,040 --> 00:04:16,899
maaaring patunayan ng interes.

87
00:04:16,899 --> 00:04:19,730
At lahat ng mga ito ay kumuha sa
mga kaganapan na hindi ka makapag

88
00:04:19,730 --> 00:04:21,380
na dumalo sa tao.

89
00:04:21,380 --> 00:04:25,000
Ang iskedyul ay inihayag sa pamamagitan ng
mag-email bilang pagkaisahin namin kuwarto.

90
00:04:25,000 --> 00:04:28,460
>> At bilang wakas, kung pumunta ka sa
projects.cs.50.net, ito ay isang website

91
00:04:28,460 --> 00:04:31,450
panatilihin namin ang bawat taon na naming mag-anyaya
kakailanganin ng mga tao mula sa komunidad, faculty,

92
00:04:31,450 --> 00:04:36,420
kagawaran, kawani, at pareho
sa isang labas ng CS50 sa

93
00:04:36,420 --> 00:04:37,730
ipanukala ang mga ideya sa proyekto.

94
00:04:37,730 --> 00:04:39,050
Mga bagay ng interes sa mga mag-aaral.

95
00:04:39,050 --> 00:04:40,600
Mga bagay ng interes sa mga kagawaran.

96
00:04:40,600 --> 00:04:43,990
Kaya huwag i-on doon kung ikaw ay struggling
sa kawalan ng katiyakan bilang sa kung ano ang iyong

97
00:04:43,990 --> 00:04:46,700
Gusto mo mismo i-pagharap sa isang bagay.

98
00:04:46,700 --> 00:04:51,760
>> Kaya huling beses na ipinakilala namin ang isang arguably
mas kumplikadong istraktura ng data kaysa sa kami ay

99
00:04:51,760 --> 00:04:53,300
nakita sa nakalipas na linggo.

100
00:04:53,300 --> 00:04:56,550
Gusto naming ginagamit ang array medyo
maligaya bilang isang kapaki-pakinabang kung

101
00:04:56,550 --> 00:04:58,160
simplistic data istraktura.

102
00:04:58,160 --> 00:05:00,570
Pagkatapos ay ipinakilala namin ang mga ito, na
siyempre ay naka-link listahan.

103
00:05:00,570 --> 00:05:05,470
At kung ano ay isa sa mga motivations para sa
nagpapakilala ang data na kaayusan?

104
00:05:05,470 --> 00:05:06,930
Oo?

105
00:05:06,930 --> 00:05:07,250
Ano iyan?

106
00:05:07,250 --> 00:05:08,080
>> Madla: Dynamic na laki.

107
00:05:08,080 --> 00:05:09,040
>> David MALAN: Dynamic na laki.

108
00:05:09,040 --> 00:05:11,890
Kaya samantalang sa array, mayroon kang upang
alam nito laki nang maaga kapag

109
00:05:11,890 --> 00:05:12,740
magtalaga ng mga ito sa iyo.

110
00:05:12,740 --> 00:05:14,380
Sa listahan na naka-link, hindi mo pag
mayroon na malaman na.

111
00:05:14,380 --> 00:05:17,610
Maaari mo lamang malloc, o sa mas pangkalahatang paraan,
magtalaga ng isang karagdagang

112
00:05:17,610 --> 00:05:20,720
node, kaya na magsalita, anumang oras mo
nais upang ipasok higit pang data.

113
00:05:20,720 --> 00:05:22,670
At node ay walang paunang natukoy na kahulugan.

114
00:05:22,670 --> 00:05:25,580
Ito ay lamang ng isang generic term na naglalarawan
ang ilang mga uri ng lalagyan na hindi namin

115
00:05:25,580 --> 00:05:29,610
paggamit sa aming mga istraktura ng data upang mag-imbak
ilang mga item ng interes, na sa ganitong

116
00:05:29,610 --> 00:05:31,750
sakaling mangyari na maging integer.

117
00:05:31,750 --> 00:05:33,160
>> Ngunit mayroong palaging isang tradeoff.

118
00:05:33,160 --> 00:05:38,070
Kaya makuha namin dynamic na sukat ng data
istraktura, ngunit kung ano ang presyo namin magbayad?

119
00:05:38,070 --> 00:05:40,040
Ano ang downside ng naka-link na mga listahan?

120
00:05:40,040 --> 00:05:41,006
Oo?

121
00:05:41,006 --> 00:05:41,980
>> Madla: Nangangailangan ng higit pang memory.

122
00:05:41,980 --> 00:05:44,240
>> David MALAN: Ito ay nangangailangan ng higit pa
memorya, nang eksakto kung paano?

123
00:05:44,240 --> 00:05:46,440
>> Madla: [hindi marinig].

124
00:05:46,440 --> 00:05:47,050
>> David MALAN: Mismong.

125
00:05:47,050 --> 00:05:50,460
Kaya ngayon namin ang pointer pagkuha up
dagdag na memorya na kami dati

126
00:05:50,460 --> 00:05:53,040
ay hindi kailangan, dahil ang kalamangan
ng isang array, siyempre, ay na

127
00:05:53,040 --> 00:05:54,860
ang lahat ng bagay ay magkadikit, likod
upang i-back sa likod, na

128
00:05:54,860 --> 00:05:56,380
Binibigyan ka ng random access.

129
00:05:56,380 --> 00:06:00,710
Dahil sa pamamagitan lamang ng paggamit ng square bracket
pagtatanda, o mas technically pointer

130
00:06:00,710 --> 00:06:03,580
pang-aritmetika, napaka-simple pa rito,
maaari mong ma-access ang anumang mga

131
00:06:03,580 --> 00:06:05,700
mga elemento sa pare-pareho ang panahon.

132
00:06:05,700 --> 00:06:08,975
At sa katunayan, iyon ang uri ng hinting sa
ibang presyo na kami nagbabayad sa isang

133
00:06:08,975 --> 00:06:09,760
naka-link na listahan.

134
00:06:09,760 --> 00:06:13,890
>> Ano ang mangyayari sa mga oras ng paggana ng
isang bagay tulad ng Search, kung gusto kong

135
00:06:13,890 --> 00:06:17,270
mahanap ang ilang mga halaga at loob
ng isang naka-link na listahan?

136
00:06:17,270 --> 00:06:20,290
Ano ang aking tumatakbo oras maging?

137
00:06:20,290 --> 00:06:21,560
Big O ng n.

138
00:06:21,560 --> 00:06:24,060
Kung ito ay pinagsunod-sunod sa?

139
00:06:24,060 --> 00:06:25,440
Paano kung ang data ng istraktura ay pinagsunod-sunod?

140
00:06:25,440 --> 00:06:28,640
Maaari ko bang gawin mas mahusay kaysa sa malaki
O ng n para maghanap?

141
00:06:28,640 --> 00:06:31,700
Hindi, dahil sa ang pinakamasama kaso ay maaaring ito
napaka mahusay na pinagsunod-sunod, ngunit ang bilang

142
00:06:31,700 --> 00:06:32,950
naghahanap ka ng mga maaaring maging malaki.

143
00:06:32,950 --> 00:06:35,370
Maaaring maging ang numero 100, na
maaaring mangyari upang maging lahat

144
00:06:35,370 --> 00:06:36,410
ang paraan sa dulo.

145
00:06:36,410 --> 00:06:39,950
At dahil maaari ka lamang ma-access ang isang naka-link na
sa listahan na ito sa pamamagitan ng pagpapatupad

146
00:06:39,950 --> 00:06:42,690
paraan ng kanyang unang node, ikaw ay
pa rin ang uri ng out ka sana.

147
00:06:42,690 --> 00:06:47,450
Mayroon kang upang tawirin ang buong bagay
mula sa unang tatagal upang matagpuan ang

148
00:06:47,450 --> 00:06:49,150
na malaking halaga tulad ng 100.

149
00:06:49,150 --> 00:06:51,350
O upang matukoy kung ito ay
hindi kahit doon.

150
00:06:51,350 --> 00:06:55,960
>> Kaya hindi namin maaaring gawin kung ano ang algorithm sa isang data
istraktura na ganito ang hitsura?

151
00:06:55,960 --> 00:06:59,460
Hindi namin maaaring gawin binary paghahanap, dahil
binary paghahanap kinakailangan na nagkaroon kami

152
00:06:59,460 --> 00:07:00,740
random access.

153
00:07:00,740 --> 00:07:04,500
Maaari lang namin tumalon mula sa lokasyon
lokasyon nang hindi na kinakailangang sundin

154
00:07:04,500 --> 00:07:07,080
mga tinapay crumbs sa anyo
ng lahat ng mga payo.

155
00:07:07,080 --> 00:07:08,300
>> Ngayon, kung paano namin ay ipatupad ito?

156
00:07:08,300 --> 00:07:12,830
Well, kung pumunta kami sa screen dito, kung
maaari naming mabilis reimplement ang data na ito

157
00:07:12,830 --> 00:07:13,440
istraktura -

158
00:07:13,440 --> 00:07:15,670
ang aking sulat-kamay ay hindi lahat na
mahusay dito, ngunit susubukan naming.

159
00:07:15,670 --> 00:07:22,030
Kaya typedef struct, at kung ano ang ginawa ko
nais na itawag sa bagay up dito?

160
00:07:22,030 --> 00:07:22,960
Node.

161
00:07:22,960 --> 00:07:24,580
Kaya makikita ako makakakuha ng sa amin makapagsimula.

162
00:07:24,580 --> 00:07:27,860
At ngayon, ano ang mga kailangan upang maging sa loob ng
ang istraktura ng data para sa kanyang sarili na

163
00:07:27,860 --> 00:07:28,430
naka-link na listahan?

164
00:07:28,430 --> 00:07:29,950
Gaano karaming mga patlang?

165
00:07:29,950 --> 00:07:30,450
>> Kaya dalawa.

166
00:07:30,450 --> 00:07:31,570
Ang isa ay medyo madali.

167
00:07:31,570 --> 00:07:33,050
Kaya int n.

168
00:07:33,050 --> 00:07:35,930
At maaari kaming tawagan n kahit ano gusto namin,
ngunit ito ay kailangang maging isang int kung hindi kami

169
00:07:35,930 --> 00:07:37,660
pagpapatupad ng isang naka-link na listahan para sa ints.

170
00:07:37,660 --> 00:07:41,920
At ngayon kung ano ang ipinapakita ng ikalawang
patlang na kailangang maging?

171
00:07:41,920 --> 00:07:43,460
Struct node *.

172
00:07:43,460 --> 00:07:50,570
Kaya kung gagawin ko struct node *, at pagkatapos ay ako
maaaring tumawag ito din kahit anong gusto ko,

173
00:07:50,570 --> 00:07:53,510
ngunit para lamang maging malinaw Tatawag ako
susunod na ito, bilang namin nai-paggawa.

174
00:07:53,510 --> 00:07:55,270
At pagkatapos ay kukunin ko isasara ang aking kulot tirante.

175
00:07:55,270 --> 00:08:00,700
>> At ngayon, bilang huling oras,
Ko bang ilagay ang node down na dito.

176
00:08:00,700 --> 00:08:03,830
Ngunit kung ako deklarasyon na ito ay bilang isang
node, bakit ako mag-abala sa pagiging kaya

177
00:08:03,830 --> 00:08:07,320
masyadong masalita dito sa deklarasyon struct
node * susunod, bilang kabaligtaran

178
00:08:07,320 --> 00:08:09,210
upang lamang node * susunod?

179
00:08:09,210 --> 00:08:09,904
Oo?

180
00:08:09,904 --> 00:08:12,810
>> Madla: [hindi marinig].

181
00:08:12,810 --> 00:08:14,050
>> David MALAN: Mismong.

182
00:08:14,050 --> 00:08:14,530
Mismong.

183
00:08:14,530 --> 00:08:18,320
Dahil C talagang magdadala sa iyo literal at
nakikita lamang ang kahulugan ng node

184
00:08:18,320 --> 00:08:21,230
paraan down na dito, hindi mo magagawa
sumangguni sa mga ito up dito.

185
00:08:21,230 --> 00:08:24,760
Kaya mayroon kaming ang ganitong uri ng preemptive
pagpapahayag dito, na kung saan ay tinatanggap na

186
00:08:24,760 --> 00:08:25,390
mas maligoy.

187
00:08:25,390 --> 00:08:27,810
Struct node, na nangangahulugang
maaari naming ngayon itong ma-access

188
00:08:27,810 --> 00:08:29,760
sa loob ng data ng istraktura.

189
00:08:29,760 --> 00:08:33,370
>> At bilang isang tabi, dahil ito ay
nagiging isang kaunti pa subjective ngayon,

190
00:08:33,370 --> 00:08:36,230
bituin ang maaaring technically pumunta dito,
maaari itong pumunta dito, maaari itong

191
00:08:36,230 --> 00:08:37,179
kahit na pumunta sa gitna.

192
00:08:37,179 --> 00:08:39,890
Aming ampon, sa estilo gabay para sa
ang kurso, ang convention ng paglalagay ng

193
00:08:39,890 --> 00:08:42,299
ang star sa tabi mismo ng data
uri, na sa kasong ito,

194
00:08:42,299 --> 00:08:43,460
magiging struct node.

195
00:08:43,460 --> 00:08:46,620
Ngunit Napagtanto ng maraming mga aklat-aralin at
online na mga sanggunian, maaari mo talaga

196
00:08:46,620 --> 00:08:48,450
makita ito sa kabilang panig.

197
00:08:48,450 --> 00:08:52,200
Ngunit lamang mapagtanto na ang parehong kalooban talaga
gumana at dapat mo lamang maging

198
00:08:52,200 --> 00:08:52,970
pare-pareho.

199
00:08:52,970 --> 00:08:53,580
>> Ayos lang.

200
00:08:53,580 --> 00:08:55,630
Kaya na noon ay aming deklarasyon
ng struct node.

201
00:08:55,630 --> 00:08:59,430
Ngunit pagkatapos namin sinimulan ang paggawa nang higit pa
sopistikadong mga bagay.

202
00:08:59,430 --> 00:09:03,410
Halimbawa, napagpasyahan naming ipakilala
isang bagay tulad ng isang hash table.

203
00:09:03,410 --> 00:09:08,160
Kaya dito ay isang hash talahanayan ng n laki,
na-index mula sa 0 sa tuktok na kaliwa sa n

204
00:09:08,160 --> 00:09:09,690
minus 1 sa ibabang kaliwa.

205
00:09:09,690 --> 00:09:11,640
Ito ay maaaring maging isang hash
mesa para sa kahit ano.

206
00:09:11,640 --> 00:09:15,340
Ngunit ano ang mga uri ng mga bagay ay namin makipag-usap
tungkol sa paggamit ng hash talahanayan para sa?

207
00:09:15,340 --> 00:09:18,370
Ang pag-iimbak ano?

208
00:09:18,370 --> 00:09:18,800
>> Mga Pangalan.

209
00:09:18,800 --> 00:09:20,870
Maaari naming gawin ang mga pangalan tulad ng
ginawa namin huling oras.

210
00:09:20,870 --> 00:09:22,200
At talagang, maaari kang mag-imbak ng kahit ano.

211
00:09:22,200 --> 00:09:24,640
At kami na makita ito muli sa
PHP at sa JavaScript.

212
00:09:24,640 --> 00:09:28,550
Ang isang hash talahanayan ay isang magaling na uri ng Swiss
Army kutsilyo na nagbibigay-daan sa iyo upang mag-imbak

213
00:09:28,550 --> 00:09:33,690
medyo magkano ang kahit anong gusto mo sa loob ng
ito sa pamamagitan ng uugnay ng mga susi na may halaga.

214
00:09:33,690 --> 00:09:34,770
Keys na may halaga.

215
00:09:34,770 --> 00:09:37,800
>> Ngayon sa ito simpleng kaso, ang aming
key lang ang mga numero.

216
00:09:37,800 --> 00:09:40,380
Kami ay pagpapatupad ng hash
talahanayan bilang isang array.

217
00:09:40,380 --> 00:09:43,500
At kaya ang mga key ay 0,
1, 2, at iba pa.

218
00:09:43,500 --> 00:09:47,200
At kaya namin, bilang mga tao, nagpasya huling
linggo na alam mo kung ano, kung hindi kami

219
00:09:47,200 --> 00:09:50,410
pagpunta sa mga pangalan ng tindahan, sabihin lamang
mang, ngunit medyo makatwirang,

220
00:09:50,410 --> 00:09:54,680
ipinapalagay na Alice, isang Isang pangalan,
lamang ay mai-index sa 0.

221
00:09:54,680 --> 00:09:58,030
At si Bob, ang isang B pangalan, ay mai-index
sa 1, at iba pa.

222
00:09:58,030 --> 00:10:02,490
Kaya nagkaroon kami ng mapping sa pagitan ng input,
na kung saan ay mga string, at ang hash

223
00:10:02,490 --> 00:10:04,560
lokasyon, na mga numero.

224
00:10:04,560 --> 00:10:07,740
>> Kaya proseso na ay karaniwang kilala bilang
isang hash, at maaari mong tunay

225
00:10:07,740 --> 00:10:09,130
ipatupad ito sa code.

226
00:10:09,130 --> 00:10:12,080
Kung Nais kong ipatupad ang isang hash
na gumagana nang eksakto kung ano ang aming

227
00:10:12,080 --> 00:10:17,070
na inilarawan mula sa huling oras, maaari ko
magpahayag ng isang function na tumatagal, bilang

228
00:10:17,070 --> 00:10:18,330
input halimbawa -

229
00:10:18,330 --> 00:10:22,190
at sabihin gawin ito sa ito
screen sa paglipas dito.

230
00:10:22,190 --> 00:10:26,180
Kung Nais kong ipatupad ng hash
function, maaari ko bang sabihin

231
00:10:26,180 --> 00:10:27,410
isang bagay na katulad nito.

232
00:10:27,410 --> 00:10:29,030
>> Ito ay pagpunta sa bumalik sa isang int.

233
00:10:29,030 --> 00:10:33,600
Ito ay pagpunta sa ay tinatawag na hash, at ito ay
pagpunta sa tanggapin bilang isang argument isang

234
00:10:33,600 --> 00:10:38,920
string, o maaari naming maging mas maayos na ngayon,
at sabihin pansamantalang trabaho *, magpapadala kami tumawag ito s.

235
00:10:38,920 --> 00:10:43,840
At pagkatapos ay ang lahat ng mga function na ito ay may sa gawin,
sa huli, ay bumalik sa isang int.

236
00:10:43,840 --> 00:10:45,990
Ngayon, kung paano ito gumagana na kapangyarihan
hindi kaya maging malinaw.

237
00:10:45,990 --> 00:10:49,510
Pupunta ako sa ipatupad ito nang walang anumang
bumubuo ng mga error ng pagsuri sa ngayon.

238
00:10:49,510 --> 00:10:55,740
Lamang ako ng pagpunta sa sabihin nang walang taros, bumalik
ano ay sa mga bracket 0, minus,

239
00:10:55,740 --> 00:10:58,850
sabihin nating, kabisera Isang tuldok-kuwit.

240
00:10:58,850 --> 00:10:59,960
>> Lahat-lahat nasira.

241
00:10:59,960 --> 00:11:02,620
Ito ay hindi perpekto dahil
isa, paano kung s ay walang bisa?

242
00:11:02,620 --> 00:11:04,000
Hindi mahusay na mga bagay ay pagpunta sa mangyayari.

243
00:11:04,000 --> 00:11:07,940
Two, kung ano ang unang titik sa mga ito
pangalan ay hindi isang malaking titik?

244
00:11:07,940 --> 00:11:09,860
Na hindi pagpunta sa i
out na rin ang alinman.

245
00:11:09,860 --> 00:11:11,970
Maaaring maging isang maliit na mga titik
o hindi ang isang sulat sa lahat.

246
00:11:11,970 --> 00:11:15,520
Kaya lubos na kuwarto para sa pagpapabuti dito,
ngunit ito ay ang pangunahing ideya.

247
00:11:15,520 --> 00:11:19,010
>> Ano kami ng inilarawan noong nakaraang linggo pasalita bilang
lamang ang proseso ng paggawa ng mga mapa Alice sa

248
00:11:19,010 --> 00:11:23,360
0 at Bob sa 1 maaaring ipinahayag
tiyak mas formulaically bilang isang C

249
00:11:23,360 --> 00:11:24,320
gumana dito.

250
00:11:24,320 --> 00:11:28,630
Tinatawag na muli hash, tumatagal ng isang string bilang
input, at pagkatapos ay sa paanuman ang isang bagay

251
00:11:28,630 --> 00:11:31,020
may na input upang makabuo ng isang output.

252
00:11:31,020 --> 00:11:34,130
Hindi hindi tulad ng aming itim na kahon paglalarawan
matagal na ginawa namin.

253
00:11:34,130 --> 00:11:36,550
Hindi ko alam kung paano maaaring ito ay
nagtatrabaho sa ilalim ng hood.

254
00:11:36,550 --> 00:11:40,120
>> Para sa mga problema sa set 6, isa sa mga hamon
ay para sa iyo na magpasya kung ano ang

255
00:11:40,120 --> 00:11:41,920
ay ang iyong hash maging?

256
00:11:41,920 --> 00:11:45,760
Ano kaya ang nangyari sa maging sa loob ng itim na
kahon, at siguro, makikita ito maging isang

257
00:11:45,760 --> 00:11:50,380
kaunti pa kaysa sa mga kagiliw-giliw na ito, at
Talagang mas madaling kapitan ng sakit sa error

258
00:11:50,380 --> 00:11:53,180
pagsusuri kaysa sa partikular na
pagpapatupad.

259
00:11:53,180 --> 00:11:54,580
>> Ngunit ang problema ay maaaring lumabas dahil, tama?

260
00:11:54,580 --> 00:11:57,760
Kung mayroon kaming data istraktura tulad ng mga ito
isa, ano ang isa sa mga problema

261
00:11:57,760 --> 00:12:01,600
maaari mong patakbuhin sa paglipas ng panahon bilang mong isingit
higit pa at higit pang mga pangalan sa

262
00:12:01,600 --> 00:12:02,880
hash talahanayan?

263
00:12:02,880 --> 00:12:04,630
Makakakuha ka ng banggaan, tama?

264
00:12:04,630 --> 00:12:07,560
Paano kung mayroon kang Alice at Aaron,
dalawang tao ang mga pangalan nangyari

265
00:12:07,560 --> 00:12:08,190
upang magsimula sa A?

266
00:12:08,190 --> 00:12:11,660
Na begs ang tanong, kung saan ka
ilagay ang pangalawang katulad Isang pangalan?

267
00:12:11,660 --> 00:12:15,050
>> Well, maaari mong naively lamang ilagay ito
kung saan si Bob ay kabilang, ngunit pagkatapos ay Bob

268
00:12:15,050 --> 00:12:17,300
uri ng screwed kung sinusubukan mong
isingit ang kanyang pangalan at susunod

269
00:12:17,300 --> 00:12:18,240
walang room para sa kanya.

270
00:12:18,240 --> 00:12:21,400
Kaya maaari mong ilagay Bob kung saan Charlie ay,
at maaari mong isipin na ito masyadong mabilis

271
00:12:21,400 --> 00:12:23,020
devolving sa isang bit ng isang gulo.

272
00:12:23,020 --> 00:12:25,600
Isang bagay na linear sa dulo, kung saan ka
lamang magkaroon upang hanapin ang buong bagay

273
00:12:25,600 --> 00:12:28,190
naghahanap ng Alice o Bob
o Aaron o Charlie.

274
00:12:28,190 --> 00:12:33,230
>> Kaya sa halip iminungkahi namin, sa halip na lamang
linearly probing para sa open space

275
00:12:33,230 --> 00:12:36,450
at plopping ang mga pangalan doon, namin
Ipinanukala isang may interes na diskarte.

276
00:12:36,450 --> 00:12:41,740
Ang isang hash talahanayan ipinatupad pa rin gamit ang isang
array ng mga indeks, ngunit ang data uri ng

277
00:12:41,740 --> 00:12:44,500
mga indeks ng ngayon ay mga payo.

278
00:12:44,500 --> 00:12:47,360
Mungkahi ukol sa kung ano?

279
00:12:47,360 --> 00:12:48,730
Payo sa naka-link na mga listahan.

280
00:12:48,730 --> 00:12:53,330
>> Dahil na isipin ang isang naka-link na ang listahan
talaga lang ang pointer sa isang node, at

281
00:12:53,330 --> 00:12:57,110
na node ay may susunod na patlang, at na node
May susunod na patlang, at iba pa.

282
00:12:57,110 --> 00:13:00,690
Kaya maaari ka na ngayong mag-isip ng array na ito sa
sa kaliwang bahagi ng isang hash talahanayan bilang

283
00:13:00,690 --> 00:13:01,820
humahantong sa isang naka-link na listahan.

284
00:13:01,820 --> 00:13:07,000
Ang bentahe ng na kung kumuha ka ng isang
banggaan sa pagitan ng Alice at Aaron,

285
00:13:07,000 --> 00:13:09,300
ano ang iyong magagawa sa mga
pangalawang nasabing tao?

286
00:13:09,300 --> 00:13:14,150
Ikaw lamang maglakip sa kanyang mga
pagtatapos, o kahit na sa simula

287
00:13:14,150 --> 00:13:15,490
ng mga naka-link na listahan.

288
00:13:15,490 --> 00:13:17,340
>> At talagang, sabihin lamang sa pamamagitan ng pansit
na para lang isang segundo.

289
00:13:17,340 --> 00:13:18,640
Saan masulit ang kahulugan?

290
00:13:18,640 --> 00:13:22,060
Kung ako isingit Alice at siya ay nagtatapos up sa
sa unang lokasyon, pagkatapos ay subukan kong

291
00:13:22,060 --> 00:13:25,310
isingit Aaron ang pangalan, at mayroong
malinaw naman isang banggaan, dapat ko bang ilagay

292
00:13:25,310 --> 00:13:27,400
sa kanya sa simula
ng mga naka-link na listahan?

293
00:13:27,400 --> 00:13:30,944
Iyon na sa unang lokasyon,
o sa dulo?

294
00:13:30,944 --> 00:13:31,440
>> Madla: [hindi marinig].

295
00:13:31,440 --> 00:13:31,990
>> David MALAN: OK.

296
00:13:31,990 --> 00:13:32,490
Narinig ko simula.

297
00:13:32,490 --> 00:13:33,903
Bakit sa simula?

298
00:13:33,903 --> 00:13:34,750
>> Madla: [hindi marinig].

299
00:13:34,750 --> 00:13:34,940
>> David MALAN: OK.

300
00:13:34,940 --> 00:13:36,520
Ito ay alphabetical, kaya na magaling.

301
00:13:36,520 --> 00:13:37,330
Iyon ay isang mahusay na ari-arian.

302
00:13:37,330 --> 00:13:39,335
Ito ay i-save sa akin ang ilang oras potensyal.

303
00:13:39,335 --> 00:13:43,290
Hindi ito ay magbibigay-daan sa akin gawin binary paghahanap, ngunit ko
maaaring hindi bababa sa magagawang masira out

304
00:13:43,290 --> 00:13:47,340
ng isang loop kung Napag-alaman kong, well, ako paraan
nakaraan ay Aaron ay magiging sa

305
00:13:47,340 --> 00:13:48,310
pinagsunod-sunod naka-link na listahan.

306
00:13:48,310 --> 00:13:50,360
Hindi ko kailangang mag-aaksaya ng aking oras hinahanap
ang lahat ng mga paraan sa dulo.

307
00:13:50,360 --> 00:13:51,530
Kaya na makatwirang.

308
00:13:51,530 --> 00:13:54,710
Bakit iba baka gusto mong isingit
ang nagbabanggaan na pangalan sa

309
00:13:54,710 --> 00:13:56,660
simula ng listahan?

310
00:13:56,660 --> 00:13:57,397
Ano iyan?

311
00:13:57,397 --> 00:13:58,680
>> Madla: [hindi marinig].

312
00:13:58,680 --> 00:14:00,820
>> David MALAN: Maaaring magtagal ng mahabang panahon
upang makakuha ng sa dulo ng listahan.

313
00:14:00,820 --> 00:14:02,490
At sa katunayan, mas mahaba at mas mahaba.

314
00:14:02,490 --> 00:14:04,920
Ang higit pang mga pangalan sa iyo na ipasok
magsimula sa A, ang mas mahaba na

315
00:14:04,920 --> 00:14:06,280
chain ay pagpunta upang makakuha ng.

316
00:14:06,280 --> 00:14:07,890
Ang mas mahaba na naka-link
listahan ay pagpunta upang makakuha ng.

317
00:14:07,890 --> 00:14:09,420
Kaya't kung ikaw talaga lamang
pag-aaksaya ng iyong oras.

318
00:14:09,420 --> 00:14:14,070
Marahil, ikaw ay mas mahusay na off pagpapanatili
pare-pareho ang pagpapasok ng oras, malaki O ng 1,

319
00:14:14,070 --> 00:14:18,470
sa pamamagitan ng palaging paglalagay ang nagbabanggaan sa pangalan
simula ng naka-link na listahan,

320
00:14:18,470 --> 00:14:21,230
at hindi nag-aalala bilang magkano
tungkol sa pag-uuri.

321
00:14:21,230 --> 00:14:22,600
>> Ano ang pinakamahusay na sagot?

322
00:14:22,600 --> 00:14:23,320
Hindi ito malinaw.

323
00:14:23,320 --> 00:14:26,140
Ito uri ng depende sa kung ano ang
pamamahagi ay, kung ano ang pattern ay

324
00:14:26,140 --> 00:14:27,850
ng pangalan mo ay pagpasok.

325
00:14:27,850 --> 00:14:29,430
Ito ay hindi kinakailangan
isang halata sagot.

326
00:14:29,430 --> 00:14:33,100
Ngunit dito sa, muli, ay
isang disenyo pagkakataon.

327
00:14:33,100 --> 00:14:37,220
>> Kaya namin pagkatapos ay tumingin sa bagay na ito, na
talaga ang iba pang mga malaking pagkakataon

328
00:14:37,220 --> 00:14:38,180
para p-set 6.

329
00:14:38,180 --> 00:14:41,770
At napagtanto, kung hindi mo pa nagagawa,
Zamyla dives sa pareho sa mga ito, hash

330
00:14:41,770 --> 00:14:43,260
mga talahanayan at sinusubukang, nang mas detalyado.

331
00:14:43,260 --> 00:14:45,630
At ang video na walkthrough ay
naka-embed sa p-set spec.

332
00:14:45,630 --> 00:14:46,590
Ito ay isang trie -

333
00:14:46,590 --> 00:14:51,670
T-R-I-E. At kung ano ang tungkol sa mga kawili-wiling
ito ay na tumatakbo ang oras

334
00:14:51,670 --> 00:14:59,510
ng paghahanap para sa isang pangalan, tulad ng Maxwell
huling beses, ay malaki O ng kung ano?

335
00:14:59,510 --> 00:15:01,040
Ano iyan?

336
00:15:01,040 --> 00:15:01,920
>> Audience: Ang bilang ng mga titik.

337
00:15:01,920 --> 00:15:02,550
>> David MALAN: Bilang ng mga titik.

338
00:15:02,550 --> 00:15:03,210
Narinig ko ang dalawang bagay.

339
00:15:03,210 --> 00:15:04,630
Bilang ng mga titik at pare-pareho ang panahon.

340
00:15:04,630 --> 00:15:05,540
Kaya sabihin pumunta sa na una.

341
00:15:05,540 --> 00:15:06,410
Ang bilang ng mga titik.

342
00:15:06,410 --> 00:15:10,195
Well, ang data na istraktura, isipin ang, ay
ng isang puno, isang family tree, sa bawat isa sa

343
00:15:10,195 --> 00:15:12,860
na node ay binubuo ng array.

344
00:15:12,860 --> 00:15:16,300
At ang mga array ay pointer sa
ibang tulad ng mga node, o iba pang ganoong

345
00:15:16,300 --> 00:15:17,670
array sa tree.

346
00:15:17,670 --> 00:15:22,890
>> Kaya kung gusto naming pagkatapos malaman
kung Maxwell ay nasa dito, maaari ba akong mag-

347
00:15:22,890 --> 00:15:26,890
sa unang array, sa pinakatuktok ng
sa puno, ang tinaguriang ugat, tuktok ng

348
00:15:26,890 --> 00:15:30,521
ang trie, at pagkatapos ay sundin ang m pointer,
pagkatapos ng isang pointer, pagkatapos ay x,

349
00:15:30,521 --> 00:15:31,710
w, e, l, l.

350
00:15:31,710 --> 00:15:34,910
At pagkatapos ay kapag nakita ko ang ilang mga espesyal na simbolo,
naitala dito bilang isang tatsulok.

351
00:15:34,910 --> 00:15:38,480
Sa code na makikita mo naming imungkahi na sa iyo
ipinatupad bilang isang bool, sinasabi lang yes

352
00:15:38,480 --> 00:15:40,540
o hindi, ang isang salita tumitigil dito.

353
00:15:40,540 --> 00:15:45,270
>> Well, isang beses na namin nawala sa M-A-X-W-E-L-L,
nararamdaman tulad ng pitong, siguro

354
00:15:45,270 --> 00:15:48,910
walo kung pumunta kami ng isa nakalipas na ito, walong
hakbang na ito upang makahanap ng Maxwell.

355
00:15:48,910 --> 00:15:53,050
O kaya sabihin call ito K. Ngunit isipin ang huling
oras, ako Nagtalo na kung mayroong

356
00:15:53,050 --> 00:15:57,540
realistically isang maximum na haba sa isang
salita, tulad ng 40-ilang-kakaiba character, isang

357
00:15:57,540 --> 00:16:00,810
maximum na haba nagpapahiwatig
isang pare-pareho ang halaga.

358
00:16:00,810 --> 00:16:05,770
Kaya talaga, oo, ito ay technically malaki O
ng 8 o 7, o talagang malaki O ng K. Ngunit

359
00:16:05,770 --> 00:16:09,420
kung mayroong isang may wakas cap sa kung ano ang
K maaaring maging, ito ay isang constant.

360
00:16:09,420 --> 00:16:12,080
At kaya malaki O ng 1 sa
ang pagtatapos ng araw.

361
00:16:12,080 --> 00:16:13,040
>> Hindi sa tunay na mundo.

362
00:16:13,040 --> 00:16:15,960
Kapag hindi mo talagang simulan ang panonood
ang iyong orasan bilang tumatakbo ang iyong mga program.

363
00:16:15,960 --> 00:16:20,690
Talagang Ito ay pagpunta sa maging isang bit
mas mabagal kaysa sa tunay na pare-pareho

364
00:16:20,690 --> 00:16:21,840
oras na may isang hakbang.

365
00:16:21,840 --> 00:16:25,540
Ito ay pagpunta sa maging pitong o walong mga hakbang,
ngunit pa rin na magkano, magkano ang mas mahusay na

366
00:16:25,540 --> 00:16:30,080
kaysa sa isang algorithm tulad ng malaki ng O n na
Depende sa laki ng kung ano ang sa

367
00:16:30,080 --> 00:16:31,220
istraktura ng data.

368
00:16:31,220 --> 00:16:34,970
>> Pansinin ng bentahe dito ay maaari naming isingit
isang milyong higit pang mga pangalan na ito sa

369
00:16:34,970 --> 00:16:38,170
istraktura ng data, ngunit kung gaano karaming mga karagdagang hakbang
ito ay pagpunta sa tumagal sa amin upang mahanap ang

370
00:16:38,170 --> 00:16:40,480
Maxwell sa kasong iyon?

371
00:16:40,480 --> 00:16:40,780
Wala.

372
00:16:40,780 --> 00:16:41,820
Siya ay hindi maaapektuhan.

373
00:16:41,820 --> 00:16:45,480
At sa petsa, palagay ko ay hindi nasaksihan namin
isang halimbawa ng data ng istraktura o isang

374
00:16:45,480 --> 00:16:48,560
algorithm na noon ay ganap na
maaapektuhan ng panlabas

375
00:16:48,560 --> 00:16:50,040
tulad ng pag-uugali na.

376
00:16:50,040 --> 00:16:51,160
Ngunit ito ay hindi maaaring maging kahanga-hangang.

377
00:16:51,160 --> 00:16:52,900
Ito ay hindi maaaring ang tanging solusyon
para sa mga p-set

378
00:16:52,900 --> 00:16:53,570
>> At ito ay hindi.

379
00:16:53,570 --> 00:16:55,980
Ito ay hindi nangangahulugang ang data
istraktura dapat mong i-gravitate,

380
00:16:55,980 --> 00:16:58,220
dahil tulad ng hash talahanayan, tradeoff.

381
00:16:58,220 --> 00:17:00,500
Ano ang presyo na binabayaran mo dito?

382
00:17:00,500 --> 00:17:00,940
Memory.

383
00:17:00,940 --> 00:17:02,890
Ibig kong sabihin, ito ay isang mabangis
halaga ng memorya.

384
00:17:02,890 --> 00:17:05,569
At hindi pa ninyo makita ito dito dahil
ang may-akda ng larawan na ito

385
00:17:05,569 --> 00:17:09,420
malinaw naman pinutol lahat ng mga array,
at hindi namin nakikita ng maraming mga A at

386
00:17:09,420 --> 00:17:12,700
B at C at T at Y ay
at Z sa mga array.

387
00:17:12,700 --> 00:17:13,630
Ngunit ang mga ito doon.

388
00:17:13,630 --> 00:17:17,660
>> Ang bawat isa sa ang mga nodes ay isang buong array
ng ilang mga 26 o higit pang mga bytes, ang bawat isa ng

389
00:17:17,660 --> 00:17:19,170
na kung saan ay kumakatawan sa isang liham.

390
00:17:19,170 --> 00:17:22,920
27 sa aming kaso, upang maaari naming suportahan
apostrophes sa hanay problema.

391
00:17:22,920 --> 00:17:27,030
Kaya ang data na istraktura talaga,
talagang siksik at malawak na.

392
00:17:27,030 --> 00:17:30,880
At mag-isa na maaaring magtapos up pagbagal
bagay down, o hindi bababa sa ay nagkakahalaga ng sa iyo ng isang

393
00:17:30,880 --> 00:17:32,240
maraming mas maraming espasyo.

394
00:17:32,240 --> 00:17:34,020
Ngunit muli, maaari naming gumuhit
mga paghahambing dito.

395
00:17:34,020 --> 00:17:39,190
>> Isipin ang isang habang pabalik, namin nakakamit magkano
mas kapana-panabik na tumatakbo sa oras ng pag-uuri

396
00:17:39,190 --> 00:17:42,880
kapag ginagamit namin ang pagsasama-uri, ngunit ang mga presyo
kami binayaran upang makamit n log n para sa pagsasama

397
00:17:42,880 --> 00:17:46,930
sort kailangan na gastusin namin
higit pang mga mapagkukunan kung ano?

398
00:17:46,930 --> 00:17:47,690
Higit pang mga puwang.

399
00:17:47,690 --> 00:17:50,530
Kinakailangan namin ng isang pangalawang array sa
kopyahin ang mga tao sa, tulad ng

400
00:17:50,530 --> 00:17:51,620
ginawa namin dito sa entablado.

401
00:17:51,620 --> 00:17:55,880
Kaya muli, walang malinaw na nagwagi,
ngunit lamang subjective disenyo

402
00:17:55,880 --> 00:17:57,710
pagpapasya na isasagawa.

403
00:17:57,710 --> 00:17:58,060
>> Ayos lang.

404
00:17:58,060 --> 00:17:59,130
Kaya kung paano tungkol dito?

405
00:17:59,130 --> 00:18:02,050
Sinuman makilala kung aling mga D-Hall?

406
00:18:02,050 --> 00:18:02,440
OK.

407
00:18:02,440 --> 00:18:03,170
Kaya tatlo sa amin gawin.

408
00:18:03,170 --> 00:18:03,750
Mather House.

409
00:18:03,750 --> 00:18:05,070
Kaya ito ay para sa Mather sa mga dining.

410
00:18:05,070 --> 00:18:09,650
Magpapadala ako pumusta lahat sa dining hall mayroon
stack ng trays na katulad nito.

411
00:18:09,650 --> 00:18:11,950
At ito ay talagang kinatawan
ng isang bagay na namin

412
00:18:11,950 --> 00:18:13,050
malinaw naman nakita pa.

413
00:18:13,050 --> 00:18:14,850
Namin na tinatawag na ito ng isang literal na stack.

414
00:18:14,850 --> 00:18:18,970
At ang stack, sa mga tuntunin ng iyong
computer memory, ay kung saan ilalagay ang data

415
00:18:18,970 --> 00:18:20,460
habang ang mga function ay ina tinatawag.

416
00:18:20,460 --> 00:18:23,410
>> Halimbawa, kung ano ang mga uri ng mga bagay pumunta
sa stack na may pagsasaalang-alang sa

417
00:18:23,410 --> 00:18:27,420
memory layout namin tinalakay
sa nakaraang linggo?

418
00:18:27,420 --> 00:18:28,736
Ano iyan?

419
00:18:28,736 --> 00:18:29,670
>> Audience: Ang mga tawag sa mga function.

420
00:18:29,670 --> 00:18:30,260
>> David MALAN: Sorry.

421
00:18:30,260 --> 00:18:31,210
>> Audience: Ang mga tawag sa mga function.

422
00:18:31,210 --> 00:18:33,590
>> David MALAN: Ang mga tawag sa pag-andar, ngunit
partikular, kung ano ang nasa loob ng bawat isa sa

423
00:18:33,590 --> 00:18:35,340
mga frame?

424
00:18:35,340 --> 00:18:37,220
Anong mga uri ng mga bagay-bagay?

425
00:18:37,220 --> 00:18:37,460
Oo.

426
00:18:37,460 --> 00:18:38,500
Kaya lokal na variable.

427
00:18:38,500 --> 00:18:43,080
Anumang oras kinailangan naming ang ilang mga lokal na imbakan,
tulad ng isang argument, o int ko, o int

428
00:18:43,080 --> 00:18:45,940
Temp, o anumang ang lokal
variable ay, kami nakapunta

429
00:18:45,940 --> 00:18:47,210
paglalagay na sa stack.

430
00:18:47,210 --> 00:18:49,610
At tinatawag namin itong isang stack dahil
ng layering na ideya.

431
00:18:49,610 --> 00:18:52,940
Lang ang uri ng pagtutugma up sa katotohanan,
ang konsepto hinggil doon.

432
00:18:52,940 --> 00:18:56,650
>> Ngunit ito lumiliko out na stack ng lata din
ay nakita bilang isang istraktura ng data, isang

433
00:18:56,650 --> 00:19:00,110
alternatibo sa isang array, isang alternatibong
sa isang naka-link na listahan.

434
00:19:00,110 --> 00:19:02,770
Isang bagay na conceptually mas kawili-wiling
na maaari pa ring maging

435
00:19:02,770 --> 00:19:06,030
ipinatupad gumagamit ng alinman sa mga
bagay, ngunit ito ay isang iba't ibang mga uri ng

436
00:19:06,030 --> 00:19:09,140
data istraktura pagsuporta, talaga,
lamang ng dalawang mga operasyon.

437
00:19:09,140 --> 00:19:11,000
Ngunit maaari mong idagdag sa may interes
mga tampok kaysa sa mga ito.

438
00:19:11,000 --> 00:19:12,180
Ngunit ang mga ito ay ang mga pangunahing kaalaman -

439
00:19:12,180 --> 00:19:13,510
itulak at magpa-pop.

440
00:19:13,510 --> 00:19:19,240
>> At ang mga ideya na may isang stack ay na kung ako
mayroon dito, mayroon o walang Annenberg

441
00:19:19,240 --> 00:19:22,880
pag-alam, isang tray mula sa susunod na pinto
kasama ang numero 9 sa ito.

442
00:19:22,880 --> 00:19:23,870
Kaya lang sa isang int.

443
00:19:23,870 --> 00:19:26,990
At gusto ko upang itulak ito papunta sa data
istraktura, na kung saan ay kasalukuyang walang laman.

444
00:19:26,990 --> 00:19:28,790
Isaalang-alang na ito sa ilalim ng stack.

445
00:19:28,790 --> 00:19:33,150
Gusto ko itulak ang numerong 9 papunta sa
isalansan, at ngayon ito doon.

446
00:19:33,150 --> 00:19:36,040
>> Ngunit ang mga kagiliw-giliw na bagay tungkol sa isang stack
ay kung ako ngayon ay nais upang itulak

447
00:19:36,040 --> 00:19:40,210
sa ilang ibang mga halaga, tulad ng 17, at itulak ako
ito papunta sa stack, pupuntahan ko gawin

448
00:19:40,210 --> 00:19:43,290
ang tanging bagay na madaling maunawaan, lamang ako pupunta
upang ilagay ito ng tama kung saan kami mga kawani na tao

449
00:19:43,290 --> 00:19:45,180
ay hilig upang ilagay ito, sa tuktok.

450
00:19:45,180 --> 00:19:48,850
Ngunit kung ano ang kawili-wili ngayon
ay, paano ako makakakuha ng sa 9?

451
00:19:48,850 --> 00:19:50,670
Alam mo yun, gagawin ko hindi na walang ilang mga pagsisikap.

452
00:19:50,670 --> 00:19:54,070
>> Kaya kung ano ang tungkol sa mga kawili-wiling
isang stack ay na sa pamamagitan ng disenyo,

453
00:19:54,070 --> 00:19:56,330
ito ay isang istraktura ng LIFO data.

454
00:19:56,330 --> 00:19:59,680
Hangal na paraan ng naglalarawan
huling in, out muna.

455
00:19:59,680 --> 00:20:03,280
Kaya ang huling numero sa
sa oras na ito ay 17.

456
00:20:03,280 --> 00:20:07,540
Kaya kapag gusto kong mag-pop ng isang bagay off
ng stack, maaari itong lamang maging 17.

457
00:20:07,540 --> 00:20:11,890
Kaya mayroong isang ipinag-uutos na pagkakasunud-sunod ng
pagpapatakbo dito, kung saan ang huling item

458
00:20:11,890 --> 00:20:14,260
sa may upang maging ang unang isa out.

459
00:20:14,260 --> 00:20:16,440
Samakatuwid ang acronym, LIFO.

460
00:20:16,440 --> 00:20:19,160
>> Kaya bakit ito ay maaaring maging kapaki-pakinabang?

461
00:20:19,160 --> 00:20:22,690
Sigurado kanilang konteksto kung saan ikaw ay
Gusto ng data kaayusan tulad ng ito?

462
00:20:22,690 --> 00:20:24,810
Well, tiyak na ito ay naging kapaki-pakinabang
sa loob ng isang computer.

463
00:20:24,810 --> 00:20:29,050
Kaya mga operating system malinaw na gamitin ito
uri ng data na istraktura para sa stack.

464
00:20:29,050 --> 00:20:32,800
Makikita rin namin makikita ang parehong ideya
pagdating sa mga pahina ng web.

465
00:20:32,800 --> 00:20:35,890
Kaya ito linggo at mga susunod na linggo at higit pa,
at bilang simulan mo ang pagpapatupad ng web

466
00:20:35,890 --> 00:20:39,490
mga pahina sa isang wika na tinatawag na HTML, maaari mong
talaga gumamit ng data kaayusan tulad ng

467
00:20:39,490 --> 00:20:42,690
ito upang matukoy kung ang pahina
tama ang format.

468
00:20:42,690 --> 00:20:47,170
Dahil makikita namin makita ang lahat ng mga web page sundin
isang uri ng hierarchy, isang indentation

469
00:20:47,170 --> 00:20:52,030
iyon ay, sa pagtatapos ng araw, maging isang
puno istraktura sa ilalim ng hood.

470
00:20:52,030 --> 00:20:53,620
Kaya higit pa sa na sa loob lamang ng kaunti.

471
00:20:53,620 --> 00:20:56,560
>> Ngunit para sa ngayon, sabihin ipanukala para sa isang
sandali, paano kami maaaring pumunta tungkol sa

472
00:20:56,560 --> 00:20:58,830
na kumakatawan sa kung ano ang isang stack ay?

473
00:20:58,830 --> 00:21:03,370
Hayaan akong magpanukala na aming ipapatupad
isang stack gamit ang code na tulad nito.

474
00:21:03,370 --> 00:21:07,990
Kaya isang stack ay pagpunta sa may loob nito
dalawang bagay, isang array, na tinatawag na trays,

475
00:21:07,990 --> 00:21:09,510
lamang na maging pare-pareho sa demo.

476
00:21:09,510 --> 00:21:12,660
At ang bawat isa sa mga item sa array na
ay magiging isang uri ng int.

477
00:21:12,660 --> 00:21:14,740
At kapasidad ay siguro ano?

478
00:21:14,740 --> 00:21:18,796
Dahil hindi ko na nakasulat sa
buong kahulugan dito.

479
00:21:18,796 --> 00:21:21,535
>> Ito ay marahil ang pinakamalaking
laki ng array.

480
00:21:21,535 --> 00:21:25,150
At marahil ito ay ipinahayag bilang isang matalim
tukuyin sa tuktok ng file, ang ilang mga

481
00:21:25,150 --> 00:21:28,450
uri ng pare-pareho ang bilang ipinahiwatig sa pamamagitan ng
galos lamang ang capitalization.

482
00:21:28,450 --> 00:21:32,250
Kaya sa isang lugar kapasidad ay tinukoy
bilang ang maximum na posibleng laki.

483
00:21:32,250 --> 00:21:35,590
Samantala, sa loob ng mga istraktura ng data
Kilala bilang isang stack doon kalooban

484
00:21:35,590 --> 00:21:38,630
maging isang integer lamang kilala
lamang bilang laki.

485
00:21:38,630 --> 00:21:43,400
>> Kaya kung ako ay upang kumatawan ito ngayon
pictorially, sabihin ipagpalagay na ito

486
00:21:43,400 --> 00:21:48,070
buong itim na kahon ay kumakatawan sa aking stack.

487
00:21:48,070 --> 00:21:50,070
Sa loob nito ay dalawang variable.

488
00:21:50,070 --> 00:21:54,780
Kaya ako ng pagpunta sa gumuhit ang
unang isa bilang laki.

489
00:21:54,780 --> 00:21:57,420
At ang pangalawang isa ako pupunta
upang gumuhit ng isang array.

490
00:21:57,420 --> 00:22:01,060
>> Ngunit lamang upang panatilihin ang mga bagay na nasa ayos,
normal Gusto ko gumuhit ng isang array tulad ng

491
00:22:01,060 --> 00:22:04,910
ito, ngunit ito uri ng magaling
kung namin ay tumutugma sa katotohanan, o

492
00:22:04,910 --> 00:22:06,230
tumugma sa mental modelo.

493
00:22:06,230 --> 00:22:12,880
Kaya ipaalam sa akin sa halip gumuhit ng array
patayo, na kung saan ay, muli,

494
00:22:12,880 --> 00:22:13,840
pag-awit artist.

495
00:22:13,840 --> 00:22:16,610
Hindi talaga mahalaga kung ano ito
ay sa ilalim ng hood.

496
00:22:16,610 --> 00:22:20,350
At kami na sabihin, sa pamamagitan ng default,
kapasidad ay magiging tatlo.

497
00:22:20,350 --> 00:22:23,480
Kaya ito ang magiging lokasyon ng 0, ito
Magiging lokasyon 1, ito

498
00:22:23,480 --> 00:22:25,740
Magiging lokasyon 2.

499
00:22:25,740 --> 00:22:29,330
>> Kung ako suhol na may bola stress, gagawin
isang tao na gusto na dumating up at magpatakbo ng mga

500
00:22:29,330 --> 00:22:30,870
pumanhik dito para sa sandali lamang?

501
00:22:30,870 --> 00:22:31,960
OK, nakakita ng iyong mga kamay muna.

502
00:22:31,960 --> 00:22:33,950
Halika sa up.

503
00:22:33,950 --> 00:22:36,500
Ayos lang.

504
00:22:36,500 --> 00:22:38,760
Kaya naniniwala akong ito ay Steven.

505
00:22:38,760 --> 00:22:40,035
Halika sa up.

506
00:22:40,035 --> 00:22:40,770
Ayos lang.

507
00:22:40,770 --> 00:22:46,760
>> Ngunit ipagpalagay na namin ngayon ang rewind sa paunang
kalagayan ng mundo kung saan ako

508
00:22:46,760 --> 00:22:52,180
Na ipinahayag lamang ng isang stack, at ito ay
pagpunta sa maging kapasidad ng tatlo.

509
00:22:52,180 --> 00:22:54,470
Ngunit laki ay hindi pa natutukoy.

510
00:22:54,470 --> 00:22:56,100
Trays ay hindi pa natutukoy.

511
00:22:56,100 --> 00:22:57,300
Kaya isang pares ng mga katanungan muna.

512
00:22:57,300 --> 00:23:01,310
At hayaan mo akong bigyan ka ng mic sa gayon maaari mong
saluhan mas aktibo sa ito.

513
00:23:01,310 --> 00:23:05,190
>> Kaya kung ano ay nasa loob ng laki sa panahon na ito
sa oras kung lahat gumawa ako ay

514
00:23:05,190 --> 00:23:09,340
ipinahayag ng isang stack na may
isang linya ng code?

515
00:23:09,340 --> 00:23:10,100
>> Steven: Hindi magkano.

516
00:23:10,100 --> 00:23:12,080
>> David MALAN: OK, hindi magkano.

517
00:23:12,080 --> 00:23:14,410
Huwag namin alam kung ano ang nasa loob ng laki,
huwag naming malaman kung ano ang nasa loob

518
00:23:14,410 --> 00:23:16,330
ng array na ito dito?

519
00:23:16,330 --> 00:23:18,630
>> Steven: lamang random code, tama?

520
00:23:18,630 --> 00:23:20,220
Lang -

521
00:23:20,220 --> 00:23:23,230
>> David MALAN: Oo, pupuntahan ko
tumawag itong code, ngunit random -

522
00:23:23,230 --> 00:23:23,820
>> Steven: Mga bagay.

523
00:23:23,820 --> 00:23:28,290
>> David MALAN: Mga bagay tulad ng random

524
00:23:28,290 --> 00:23:28,870
>> Steven: Bits.

525
00:23:28,870 --> 00:23:29,530
>> David MALAN: Bits, tama?

526
00:23:29,530 --> 00:23:31,190
Kaya basura mga halaga, tama?

527
00:23:31,190 --> 00:23:33,470
Kaya permutations ng 0 at 1 ni.

528
00:23:33,470 --> 00:23:35,920
Mga Labi ng nakaraang usages
ng memorya na ito.

529
00:23:35,920 --> 00:23:38,150
At hindi namin talaga alam kung ano ang mga halaga
ay, kaya kami ay karaniwang gumuhit ng mga ito

530
00:23:38,150 --> 00:23:38,930
bilang tanong marks.

531
00:23:38,930 --> 00:23:41,990
>> Kaya ang unang bagay na kami siguro
pagpunta sa nais na gawin dito -

532
00:23:41,990 --> 00:23:46,630
at hayaan mo akong bigyan ang patlang na ito sa loob ng
ng may isang pangalan - trays.

533
00:23:46,630 --> 00:23:49,540
Ano ang dapat naming siguro initialize
laki sa kung gusto naming

534
00:23:49,540 --> 00:23:51,040
simulan ang paggamit ito stack?

535
00:23:51,040 --> 00:23:53,070
>> Steven: Tray ay sub 3.

536
00:23:53,070 --> 00:23:53,910
>> David MALAN: Kaya, OK.

537
00:23:53,910 --> 00:23:56,710
Upang maging malinaw, kapasidad ay ipinahayag
sa ibang dako bilang tatlong.

538
00:23:56,710 --> 00:23:58,570
At na kung ano na nagamit ko
upang maglaan ng array.

539
00:23:58,570 --> 00:24:03,535
Laki ay pagpunta sa sumangguni sa kung gaano karaming
trays kasalukuyang nasa stack.

540
00:24:03,535 --> 00:24:03,880
>> Steven: Zero.

541
00:24:03,880 --> 00:24:04,460
>> David MALAN: Kaya ito ay kailangang maging zero.

542
00:24:04,460 --> 00:24:07,760
Kaya't sige, at sa sinumang daliri,
gumuhit ng zero ang laki.

543
00:24:07,760 --> 00:24:08,440
Ayos lang.

544
00:24:08,440 --> 00:24:10,920
Kaya ngayon, kung ano ang nasa loob ng mga ito
dito, hindi namin alam.

545
00:24:10,920 --> 00:24:12,160
Ang mga ito ay talagang lamang ang mga halaga ng basura.

546
00:24:12,160 --> 00:24:14,800
Kaya maaari naming gumuhit ng mga marka tanong, ngunit
sabihin board panatilihin ang malinis para sa ngayon

547
00:24:14,800 --> 00:24:16,300
dahil hindi mahalaga
kung ano ang doon.

548
00:24:16,300 --> 00:24:19,130
Hindi namin kailangang mag-initialize ang array
sa anumang bagay, dahil kung alam namin na

549
00:24:19,130 --> 00:24:23,100
ang laki ng stack ay zero, mahusay, namin
Hindi dapat na tumitingin sa anumang bagay sa

550
00:24:23,100 --> 00:24:25,590
ito array pa rin sa
ang puntong ito sa panahon.

551
00:24:25,590 --> 00:24:29,970
>> Kaya ngayon ipagpalagay na ako itulak ang
number 9 papunta sa stack.

552
00:24:29,970 --> 00:24:33,750
Paano dapat naming i-update ang data ng istraktura
sa loob ng ito itim na kahon?

553
00:24:33,750 --> 00:24:35,540
Anong mga halaga ang kailangang baguhin?

554
00:24:35,540 --> 00:24:36,200
>> Steven: Sa loob ng -

555
00:24:36,200 --> 00:24:37,400
ang laki?

556
00:24:37,400 --> 00:24:37,650
>> David MALAN: OK.

557
00:24:37,650 --> 00:24:38,770
Laki dapat bang maging ano?

558
00:24:38,770 --> 00:24:39,580
>> Steven: Laki ay magiging isa.

559
00:24:39,580 --> 00:24:39,870
>> David MALAN: OK.

560
00:24:39,870 --> 00:24:41,110
Kaya laki dapat bang maging isa.

561
00:24:41,110 --> 00:24:42,540
Kaya maaari mong gawin ito sa isang paraan pares.

562
00:24:42,540 --> 00:24:46,920
Hayaan akong magbigay sa iyo, ngayon ay ang iyong
daliri ay isang pambura.

563
00:24:46,920 --> 00:24:47,260
Ayos lang.

564
00:24:47,260 --> 00:24:49,960
Pagkatapos ngayon ang iyong daliri ay isang brush.

565
00:24:49,960 --> 00:24:50,330
Ayos lang.

566
00:24:50,330 --> 00:24:52,820
At ngayon kung ano pa ang may upang baguhin,
malinaw naman, sa istraktura ng data?

567
00:24:52,820 --> 00:24:57,060
>> Steven: Kami ay pagpunta mula sa
ilalim ng hanggang sa 9.

568
00:24:57,060 --> 00:24:57,760
>> David MALAN: 9.

569
00:24:57,760 --> 00:24:58,420
OK, Magandang.

570
00:24:58,420 --> 00:25:01,550
Kaya pa rin ay hindi mahalaga kung ano ang sa
lokasyon ng isa o dalawang dahil hindi nila

571
00:25:01,550 --> 00:25:04,520
mga halaga ng basura, ngunit hindi namin dapat mag-abala
Naghahanap doon dahil ang sukat ng

572
00:25:04,520 --> 00:25:07,540
na nagsasabi sa amin na ang unang lamang ang elemento
ay talagang lehitimo.

573
00:25:07,540 --> 00:25:10,400
Kaya ngayon ako itulak 17 papunta sa listahan.

574
00:25:10,400 --> 00:25:11,830
Ano ang mangyayari sa ang larawang ito?

575
00:25:11,830 --> 00:25:14,720
>> Steven: Kaya laki ay pagpunta sa pumunta sa dalawa.

576
00:25:14,720 --> 00:25:15,300
>> David MALAN: OK.

577
00:25:15,300 --> 00:25:16,070
Ikaw pambura -

578
00:25:16,070 --> 00:25:16,810
oops.

579
00:25:16,810 --> 00:25:18,026
Ikaw ay isang pambura.

580
00:25:18,026 --> 00:25:18,840
>> Steven: Pambura.

581
00:25:18,840 --> 00:25:19,720
>> David MALAN: Ikaw ang brush.

582
00:25:19,720 --> 00:25:20,560
>> Steven: Brush.

583
00:25:20,560 --> 00:25:20,920
>> David MALAN: OK.

584
00:25:20,920 --> 00:25:21,600
At ano pa?

585
00:25:21,600 --> 00:25:22,600
>> Steven: At pagkatapos namin -

586
00:25:22,600 --> 00:25:22,915
>> David MALAN: Aming hunhon 17.

587
00:25:22,915 --> 00:25:24,760
>> Steven: dumikit namin 17 sa tuktok, kaya -

588
00:25:24,760 --> 00:25:25,710
>> David MALAN: OK, mabuti.

589
00:25:25,710 --> 00:25:27,040
>> Steven: - drop ito pababa.

590
00:25:27,040 --> 00:25:27,530
>> David MALAN: Lahat ng karapatan.

591
00:25:27,530 --> 00:25:27,940
Nagiging madali.

592
00:25:27,940 --> 00:25:29,300
Hindi ako pagpunta upang makatulong sa iyo sa oras na ito.

593
00:25:29,300 --> 00:25:30,510
Itulak 22.

594
00:25:30,510 --> 00:25:31,720
>> Steven: Tapos na.

595
00:25:31,720 --> 00:25:34,870
Mawalan ng pambura.

596
00:25:34,870 --> 00:25:37,340
Ako magiging isang brush.

597
00:25:37,340 --> 00:25:39,340
At pagkatapos ay ako ay paglalagay 22.

598
00:25:39,340 --> 00:25:40,100
>> David MALAN: 22.

599
00:25:40,100 --> 00:25:40,620
Magaling.

600
00:25:40,620 --> 00:25:41,380
Kaya isa pang beses.

601
00:25:41,380 --> 00:25:44,280
Ngayon ako pagpunta sa itulak
papunta sa stack 26.

602
00:25:44,280 --> 00:25:46,350
>> Steven: Ooh.

603
00:25:46,350 --> 00:25:50,278
Oh sus.

604
00:25:50,278 --> 00:25:52,520
Ikaw talaga nahuli ako off bantay.

605
00:25:52,520 --> 00:25:53,703
>> MALAN David: Ikaw ay hindi
makita ito darating?

606
00:25:53,703 --> 00:25:55,930
>> Steven: Hindi ko nakita ito darating.

607
00:25:55,930 --> 00:25:58,756
Ma muli naming paunang kapasidad?

608
00:25:58,756 --> 00:25:59,790
>> David MALAN: Iyon ay isang mahusay na tanong.

609
00:25:59,790 --> 00:26:02,360
Kaya namin ang uri ng pininturahan ating sarili
sa isang sulok dito.

610
00:26:02,360 --> 00:26:06,740
Mayroong talaga ay walang mabuting out para sa Steven
dahil kami inilalaan array na ito

611
00:26:06,740 --> 00:26:09,130
statically, kaya na magsalita, sa loob
ng mga istraktura ng data.

612
00:26:09,130 --> 00:26:12,170
At kami ng lubos na hard code
ito upang maging sukat ng tatlo.

613
00:26:12,170 --> 00:26:14,170
Kaya hindi talaga namin maaaring reallocate ito.

614
00:26:14,170 --> 00:26:20,020
>> Maaaring namin kung kami nagpunta bumalik sa, namin
redefined trays na maging isang pointer na

615
00:26:20,020 --> 00:26:22,300
namin pagkatapos ay gamitin ang malloc sa kamay memory sa.

616
00:26:22,300 --> 00:26:25,050
Dahil kung namin ang nakuha mula sa memory
ang kimpal sa pamamagitan ng malloc, namin

617
00:26:25,050 --> 00:26:26,430
pagkatapos ma magbakante ito.

618
00:26:26,430 --> 00:26:29,630
Ngunit bago pagbabakante ito, maaari naming
reallocate ng mas malaking tipak ng memory,

619
00:26:29,630 --> 00:26:31,330
i-update ang pointer, at iba pa.

620
00:26:31,330 --> 00:26:33,500
Ngunit para sa ngayon, talaga ito
ang pinakamahusay na maaari naming gawin.

621
00:26:33,500 --> 00:26:36,360
Itulak at magpa-pop ay siguro pagpunta
upang magkaroon ng upang magsenyas ng ilang mga error.

622
00:26:36,360 --> 00:26:40,270
>> Kaya halimbawa, ang aming pagpapatupad
ng push maaaring magbalik ng bool na

623
00:26:40,270 --> 00:26:42,390
dati ibinalik na totoo, totoo, totoo.

624
00:26:42,390 --> 00:26:48,390
Ngunit ang ika-apat na oras, ito ay pagpunta sa may
upang bumalik false, halimbawa.

625
00:26:48,390 --> 00:26:48,540
Ayos lang.

626
00:26:48,540 --> 00:26:49,540
Tunay na magaling.

627
00:26:49,540 --> 00:26:50,060
Binabati kita.

628
00:26:50,060 --> 00:26:52,160
Kumita ka ng stress ang iyong mga bola ngayon.

629
00:26:52,160 --> 00:26:53,110
>> [Palakpakan]

630
00:26:53,110 --> 00:26:54,382
>> Steven: Salamat sa iyo.

631
00:26:54,382 --> 00:26:55,680
>> David MALAN: Salamat sa iyo.

632
00:26:55,680 --> 00:26:59,740
OK, sa gayon ito ay anyong hindi magkano
ng isang hakbang pasulong, tama?

633
00:26:59,740 --> 00:27:01,410
Inilalarawan namin ang data na ito istraktura.

634
00:27:01,410 --> 00:27:02,320
Naging nakakahimok, tama?

635
00:27:02,320 --> 00:27:03,200
Operating system ito nais.

636
00:27:03,200 --> 00:27:06,360
Tila ang web ay maaaring gamitin ng mga ito,
at iba pang mga application pa rin.

637
00:27:06,360 --> 00:27:10,870
Ngunit kung ano ang isang bobo limitasyon na kami
i-back sa isang uri ng dalawang linggo limitasyon

638
00:27:10,870 --> 00:27:12,880
kung saan kami naayos array laki.

639
00:27:12,880 --> 00:27:15,010
>> Kaya may mga talaga ng dalawang
paraan maaari naming malutas ito.

640
00:27:15,010 --> 00:27:18,750
Maaari naming dynamic na magtalaga ng mga array,
hindi sa pamamagitan ng matapang na coding ito bilang nag ako

641
00:27:18,750 --> 00:27:22,600
tapos dito, ngunit sa halip ay muling deklarasyon
ito, para lamang maging malinaw, bilang

642
00:27:22,600 --> 00:27:23,830
isang bagay na katulad nito.

643
00:27:23,830 --> 00:27:29,040
Int * trays, hindi nagpapasya
sa isang kapasidad pa.

644
00:27:29,040 --> 00:27:35,460
Ngunit kapag ako magpahayag ng stack sa ibang lugar
sa aking code, maaari ko pagkatapos tawagan malloc,

645
00:27:35,460 --> 00:27:38,250
makuha ang address ng isang tipak ng
memorya, at maaari ba akong magtalaga

646
00:27:38,250 --> 00:27:39,980
na address sa trays.

647
00:27:39,980 --> 00:27:43,340
>> At pagkatapos, dahil ito lamang ay isang tipak ng
memorya, maaari ba akong patuloy na gamitin ang square

648
00:27:43,340 --> 00:27:45,450
bracket notation sa karaniwang paraan.

649
00:27:45,450 --> 00:27:49,020
Dahil muli, mayroong uri ng mga ito
functional katumbas ng array at

650
00:27:49,020 --> 00:27:50,820
chunks ng memorya na dumating
pabalik mula sa malloc.

651
00:27:50,820 --> 00:27:53,090
Maaari naming ituring bilang isa sa iba pang mga
gamit ang pointer aritmetika o

652
00:27:53,090 --> 00:27:54,440
square bracket pagtatanda.

653
00:27:54,440 --> 00:27:55,660
Kaya iyon ang isa na diskarte.

654
00:27:55,660 --> 00:28:00,120
>> Ngunit paano pa ang maaari naming ipatupad ang
parehong istraktura ng data, potensyal na?

655
00:28:00,120 --> 00:28:00,280
I-right?

656
00:28:00,280 --> 00:28:04,530
Pakiramdam ko ay tulad lang namin malutas ito
problema tulad ng isang linggo na ang nakakalipas.

657
00:28:04,530 --> 00:28:08,860
Ano ang solusyon sa problemang ito
na Steven bumangga sa?

658
00:28:08,860 --> 00:28:10,370
Kaya naka-link na mga listahan, i-right.

659
00:28:10,370 --> 00:28:13,410
>> Kung ang problema ay na kami ay pagpipinta
ating sarili sa isang sulok sa pamamagitan ng paglaan ng

660
00:28:13,410 --> 00:28:17,580
maaga masyadong maliit na memory namin
pagkatapos ay sa paanuman upang harapin ang, mahusay,

661
00:28:17,580 --> 00:28:19,880
bakit hindi iwasan lamang na
maglalabas ng sama-sama?

662
00:28:19,880 --> 00:28:26,170
Bakit hindi lamang magpahayag ng trays na maging isang
pointer sa isang node samakatuwid, isang naka-link na listahan,

663
00:28:26,170 --> 00:28:30,740
at pagkatapos lamang magtalaga ng bagong node
tuwing Steven na kailangan upang umangkop sa isang

664
00:28:30,740 --> 00:28:32,400
numero sa ang istraktura ng data.

665
00:28:32,400 --> 00:28:34,200
>> Kaya ang larawan ay magkakaroon upang baguhin.

666
00:28:34,200 --> 00:28:38,220
Hindi Ito ay pagpunta sa maging bilang malinis at bilang
simple lamang bilang isang array ng tatlong ints.

667
00:28:38,220 --> 00:28:42,970
Ngayon ito ay pagpunta sa maging isang pointer sa isang
struct, at struct na pagpunta sa

668
00:28:42,970 --> 00:28:44,830
magkaroon ng isang int at isang susunod na pointer.

669
00:28:44,830 --> 00:28:47,670
Ito ay pagpunta sa humantong sa pamamagitan ng na ang pointer
sa isa pang tulad struct sa

670
00:28:47,670 --> 00:28:48,600
isa pang tulad struct.

671
00:28:48,600 --> 00:28:50,560
Kaya larawan ang gagawin talaga
makakuha ng isang bit Messier.

672
00:28:50,560 --> 00:28:52,950
At gusto namin ang mga arrow tinali
lahat ng bagay magkasama.

673
00:28:52,950 --> 00:28:55,280
>> Ngunit iyon fine, kanan, dahil
nasaksihan namin kung paano gawin ito.

674
00:28:55,280 --> 00:28:58,180
At sa sandaling makakuha ka komportable
pagpapatupad ng isang bagay tulad ng isang naka-link na

675
00:28:58,180 --> 00:29:01,450
listahan, na kung saan kailangan mong gawin kapag mo
pumili upang ipatupad ang isang hash talahanayan na may

676
00:29:01,450 --> 00:29:05,120
hiwalay chaining para p-set 6, maaari mong
gamitin ito bilang isang bloke ng gusali, o isang

677
00:29:05,120 --> 00:29:08,870
sahog, o sa scratch magsalita, isang
pamamaraan, isang bagay na inilagay mo, mo

678
00:29:08,870 --> 00:29:12,560
nilikha ang iyong sariling mga puzzle piraso
na maaari mong gamitin muli pagkatapos.

679
00:29:12,560 --> 00:29:17,090
Kaya tradeoffs, ngunit potensyal na solusyon
na aktwal na nasaksihan namin dati.

680
00:29:17,090 --> 00:29:20,560
>> Kaya medyo madalas, makikita mo ito sa bawat
taon o dalawang kapag Apple release

681
00:29:20,560 --> 00:29:23,060
ng isang bagong bagay, at ang lahat ng mga nakatutuwang mga tao
line up sa labas ng Apple

682
00:29:23,060 --> 00:29:27,050
mag-imbak upang bumili ng kanilang mga nasa gilid
mag-upgrade sa hardware.

683
00:29:27,050 --> 00:29:30,420
Sinasabi ko ito, ito ay OK, dahil
Ako ay isa sa mga taong iyon.

684
00:29:30,420 --> 00:29:35,140
Kaya kung anong uri ng data na istraktura
Maaaring kumatawan ang katotohanan?

685
00:29:35,140 --> 00:29:36,980
>> Well, sabihin call ito ng isang pila, isang linya.

686
00:29:36,980 --> 00:29:40,270
Kaya gusto British tumawag ito isang karaniwang
pila pa rin, sa gayon ito ay isang magaling na pangalan.

687
00:29:40,270 --> 00:29:44,960
At ang dalawang mga operasyon na ang isang queue
dapat suportahan namin tumawag sa isang enqueue

688
00:29:44,960 --> 00:29:48,900
operasyon at isang dequeue pagpapatakbo,
na kung saan ay katulad sa

689
00:29:48,900 --> 00:29:50,120
espiritu upang itulak at magpa-pop.

690
00:29:50,120 --> 00:29:54,060
Ito ay lamang uri ng iba't ibang mga sa
convention, ano kami mga pagtawag.

691
00:29:54,060 --> 00:29:57,680
Ngunit sa enqueue isang bagay ay nangangahulugan na upang magdagdag ng
o ipasok ito sa istraktura ng data.

692
00:29:57,680 --> 00:29:59,570
Upang dequeue nangangahulugan na alisin ito.

693
00:29:59,570 --> 00:30:05,170
Ngunit habang ang isang stack ay isang LIFO data
istraktura, isang pila ay isang unang in,

694
00:30:05,170 --> 00:30:06,740
out muna ang istraktura ng data.

695
00:30:06,740 --> 00:30:10,050
>> Kung ikaw ang unang tao sa linya,
ay ikaw ang unang tao upang makakuha ng

696
00:30:10,050 --> 00:30:12,420
out ng mga linya at bilhin ang iyong bagong device.

697
00:30:12,420 --> 00:30:18,070
Isipin kung paano sira ang mga taong ito ay magiging
kung Apple sa halip ay gumamit ng isang stack, para sa

698
00:30:18,070 --> 00:30:21,250
Halimbawa, upang ipatupad ang pagpili
up ng iyong bagong laruan.

699
00:30:21,250 --> 00:30:24,310
Kaya queues kabuluhan, walang duda, at
maaari naming isipin ang lahat ng uri ng

700
00:30:24,310 --> 00:30:27,480
application, siguro, para sa queues,
lalo na kapag gusto mong pagkamakatarungan.

701
00:30:27,480 --> 00:30:30,040
Kaya kung paano namin ipatupad ang mga
bilang isang istraktura ng data?

702
00:30:30,040 --> 00:30:33,680
>> Well, ipinapanukala ko na maaari naming
kailangang gawin ito sa ganitong paraan.

703
00:30:33,680 --> 00:30:35,225
Kaya pupuntahan ko ay mayroon na ngayong mga numero.

704
00:30:35,225 --> 00:30:38,190
Kaya naming panatilihin itong simple at hindi
kinakailangan na makipag-usap sa mga tuntunin ng trays.

705
00:30:38,190 --> 00:30:40,220
Lamang ang mga numero na ang mga tao ng nakuha.

706
00:30:40,220 --> 00:30:43,760
Kapasidad ay pagpunta sa, muli, ayusin ang
kabuuang bilang ng mga tao na maaaring nasa

707
00:30:43,760 --> 00:30:46,900
ang linyang ito, bilang tatlo o
anumang iba pang mga halaga.

708
00:30:46,900 --> 00:30:50,760
>> Ngunit ipanukala ko na kailangan kong i-track ang
hindi lamang ng laki ng

709
00:30:50,760 --> 00:30:52,370
queue, kung gaano karaming mga bagay ang sa loob nito.

710
00:30:52,370 --> 00:30:56,310
Kaya't ang sukat ng kasalukuyang laki, kapasidad
ay ang maximum na laki.

711
00:30:56,310 --> 00:30:58,540
Lang ulit, mga katawagan
sa pamamagitan ng convention.

712
00:30:58,540 --> 00:31:03,680
Bakit ko kailangan ng isang karagdagang int loob
ng isang pila upang masubaybayan kung sino ang nasa

713
00:31:03,680 --> 00:31:05,365
harapan ng linya?

714
00:31:05,365 --> 00:31:07,930

715
00:31:07,930 --> 00:31:10,910
Bakit kailangan kong gawin iyon sa kasong ito?

716
00:31:10,910 --> 00:31:14,750

717
00:31:14,750 --> 00:31:16,190
>> Well, kung paano ay ang larawang ito
pagpunta sa palitan?

718
00:31:16,190 --> 00:31:19,280
Maaari ko bang gamitin muli marahil pinaka-
ng larawan na ito.

719
00:31:19,280 --> 00:31:21,480
Hayaan akong sige at burahin ang kung ano ang meron dito.

720
00:31:21,480 --> 00:31:24,580
Susubukan naming bigyan ito ng isang bahagyang
ibang pangalan up dito.

721
00:31:24,580 --> 00:31:28,930
Natin mapupuksa ang mga 17, sabihin mapupuksa
ng 9, sabihin mapupuksa ng 3.

722
00:31:28,930 --> 00:31:30,410
At sabihin magdagdag ng isa pang bagay.

723
00:31:30,410 --> 00:31:34,710
Ipanukala ko na kailangan kong subaybayan
harap ng listahan, na kung saan ay lamang

724
00:31:34,710 --> 00:31:35,570
pagpunta sa maging isang int pati na rin.

725
00:31:35,570 --> 00:31:36,550
At kami ay pagpunta sa panatilihin itong simple.

726
00:31:36,550 --> 00:31:37,740
Walang naka-link na listahan para sa ngayon.

727
00:31:37,740 --> 00:31:40,900
>> Susubukan naming umamin na kami ng pagpunta sa
mauntog up laban sa limitasyong ito.

728
00:31:40,900 --> 00:31:43,720
Ngunit kung ano ang gusto kong makita
mangyari oras na ito?

729
00:31:43,720 --> 00:31:47,240
Kaya ipagpalagay ko sige at ang unang
tao ay lumalabas sa linya, at

730
00:31:47,240 --> 00:31:48,560
ito ang numero 9.

731
00:31:48,560 --> 00:31:49,680
Kami ng mga bola stress.

732
00:31:49,680 --> 00:31:51,330
Maaari ko bang nakawin, sabihin nating, dalawa o tatlong mga tao?

733
00:31:51,330 --> 00:31:52,690
Ang isa, dalawa, tatlo?

734
00:31:52,690 --> 00:31:53,120
Halika sa up.

735
00:31:53,120 --> 00:31:56,022
Kanan mula sa harap, dahil
magsasagawa kami ng isang mabilis na ito.

736
00:31:56,022 --> 00:31:59,415
>> Ang bawat isa sa iyo ngayon ay pagpunta sa maging
isang fan boy sa linya sa Apple.

737
00:31:59,415 --> 00:32:03,970

738
00:32:03,970 --> 00:32:06,210
Ikaw ay hindi pagtanggap ng Apple hardware
sa dulo ng ito bagaman.

739
00:32:06,210 --> 00:32:06,500
Ayos lang.

740
00:32:06,500 --> 00:32:09,430
Kaya ikaw ay number 9, ikaw ay
number 17, number 22.

741
00:32:09,430 --> 00:32:12,130
Ito ang mga arbitrary na numero, tulad ng
mga ID ng mag-aaral o watnat.

742
00:32:12,130 --> 00:32:14,550
At sa loob lamang ng isang sandali, sabihin simulan
upang magsimulang magdagdag ng mga bagay-bagay.

743
00:32:14,550 --> 00:32:16,000
At kukunin ko na tumakbo sa board dito oras na ito.

744
00:32:16,000 --> 00:32:19,570
>> Kaya sa kasong ito, ko na nasimulan
front ang upang maging -

745
00:32:19,570 --> 00:32:22,380
Ko talagang hindi talagang mahalaga kung ano ang
front ay, dahil ang laki ay zero.

746
00:32:22,380 --> 00:32:24,480
Kaya ito ay maaaring pati na rin lamang
maging isang tandang pananong.

747
00:32:24,480 --> 00:32:26,170
Ito ang lahat ng mga marka tanong.

748
00:32:26,170 --> 00:32:29,880
Kaya ngayon sisimulan naming upang aktwal na makita ang ilang mga
mga tao lining up sa tindahan.

749
00:32:29,880 --> 00:32:33,320
>> Kaya kung number 9, ikaw ang unang isa
doon sa 5:00, sige at pumila,

750
00:32:33,320 --> 00:32:34,210
o ang gabi bago.

751
00:32:34,210 --> 00:32:34,580
OK.

752
00:32:34,580 --> 00:32:35,940
Kaya ngayon ay 9 dito.

753
00:32:35,940 --> 00:32:37,940
Kaya 9 ay nasa harap ng mga listahan.

754
00:32:37,940 --> 00:32:41,440
Kaya pupuntahan ko sige at i-update
ang laki ng mga ito ang kasalukuyang data

755
00:32:41,440 --> 00:32:44,740
istraktura upang hindi maging 0 ngayon,
ngunit upang maging 1.

756
00:32:44,740 --> 00:32:47,630
Pupunta ako sa 9 na ilagay sa
harapan ng listahan.

757
00:32:47,630 --> 00:32:51,020
Hayaan akong sige at magpalipat-lipat ng screen
upang maaari naming makita ang nakaraan sa amin dito.

758
00:32:51,020 --> 00:32:53,220
>> At ngayon kung ano ang gusto ko
upang ilagay sa harap?

759
00:32:53,220 --> 00:32:56,240
Pupunta ako sa subaybayan na ang
harapan ng pila sa ngayon

760
00:32:56,240 --> 00:32:58,570
ay nasa 0 lokasyon.

761
00:32:58,570 --> 00:33:00,510
Dahil kung ano ang susunod na pagpunta sa mangyayari?

762
00:33:00,510 --> 00:33:03,000
Well, ipagpalagay na ngayon ko enqueue
17 pati na rin.

763
00:33:03,000 --> 00:33:04,510
Kaya Hop sa linya doon.

764
00:33:04,510 --> 00:33:07,060
At muli, ang uri ng mga pintuan ng
tindahan ay magiging dito.

765
00:33:07,060 --> 00:33:08,700
Kaya ngayon Idinagdag ko na 17.

766
00:33:08,700 --> 00:33:10,810
At kahit na ang mga guys ay hinaharangan
ang screen, na OK lang,

767
00:33:10,810 --> 00:33:12,300
dahil maaari naming makita ito up dito.

768
00:33:12,300 --> 00:33:12,910
Sorry.

769
00:33:12,910 --> 00:33:13,810
>> Madla: Maaari naming ilipat -

770
00:33:13,810 --> 00:33:14,660
>> David MALAN: Hindi, iyan ay OK.

771
00:33:14,660 --> 00:33:16,000
Ito ay malaking up doon.

772
00:33:16,000 --> 00:33:18,580
Kaya 17 ay ngayon sa loob ng queue.

773
00:33:18,580 --> 00:33:21,332
Kailangan ko upang i-update na
field ngayon bagaman?

774
00:33:21,332 --> 00:33:23,210
OK, siguradong laki.

775
00:33:23,210 --> 00:33:26,430
At kung paano tungkol sa front?

776
00:33:26,430 --> 00:33:27,040
OK, hindi.

777
00:33:27,040 --> 00:33:30,200
Front ay hindi dapat magbago, dahil
hindi katulad ng isang stack, kami

778
00:33:30,200 --> 00:33:31,370
nais upang mapanatili ang pagiging patas.

779
00:33:31,370 --> 00:33:35,150
Kaya kung 9 ay dumating sa unang, nais naming 9
upang maging una sa labas ng linya

780
00:33:35,150 --> 00:33:36,420
at sa mga tindahan.

781
00:33:36,420 --> 00:33:37,220
>> Sa katunayan, sabihin makita na.

782
00:33:37,220 --> 00:33:42,235
Bago namin isingit 22, sabihin
sige at dequeue 9.

783
00:33:42,235 --> 00:33:42,970
Ano ang inyong pangalan muli?

784
00:33:42,970 --> 00:33:43,680
>> Madla: Jake.

785
00:33:43,680 --> 00:33:45,440
>> David MALAN: Jake ay pagpunta
na dequeued ngayon.

786
00:33:45,440 --> 00:33:48,050
Kaya mo makakuha upang maglakad papunta sa tindahan.

787
00:33:48,050 --> 00:33:49,880
At magpanggap na mga tindahan
ay banda roon.

788
00:33:49,880 --> 00:33:51,970
Kaya ngayon ano ang mga kailangan - dit-dit-dit!

789
00:33:51,970 --> 00:33:53,400
Ano ang kailangang mangyari ngayon?

790
00:33:53,400 --> 00:33:54,490
Disenyo desisyon.

791
00:33:54,490 --> 00:33:56,825
Kaya hindi isang masamang likas na hilig, ngunit -
ano ang iyong pangalan muli?

792
00:33:56,825 --> 00:33:57,090
>> Madla: David.

793
00:33:57,090 --> 00:33:57,500
>> David MALAN: David.

794
00:33:57,500 --> 00:33:58,810
Kaya kung ano ang David gawin?

795
00:33:58,810 --> 00:34:02,590
Siya ay sinusubukan upang ayusin ng maayos ang data
istraktura at ilipat mula sa kanyang lokasyon

796
00:34:02,590 --> 00:34:04,100
sa dating lokasyon ni Jake.

797
00:34:04,100 --> 00:34:06,740
At iyon ang masarap na kung hindi kami payag
tanggapin na bilang isang

798
00:34:06,740 --> 00:34:08,199
pagpapatupad detalye.

799
00:34:08,199 --> 00:34:11,100
Ngunit una, sabihin i-update ang data
istraktura bago gawin namin iyon.

800
00:34:11,100 --> 00:34:14,139
Dahil hindi ako paggusto ang ideya ng lahat
ang mga tao paglilipat sa linyang ito.

801
00:34:14,139 --> 00:34:17,360
>> Ito ay hindi sang-ayon kung David ang ipinapakita ito sa
isang hakbang, ngunit muli, sa tingin pabalik sa

802
00:34:17,360 --> 00:34:20,360
kapag mayroon kaming walong boluntaryo sa
stage at ginawa namin tulad ng pagpapasok

803
00:34:20,360 --> 00:34:22,600
-uri-uriin, kung saan nagkaroon kami upang magsimulang
paglipat ng lahat ng tao sa paligid.

804
00:34:22,600 --> 00:34:23,790
Nakakuha na mahal, tama?

805
00:34:23,790 --> 00:34:28,330
Na gumagawa sa akin sumukot tungkol sa malaking O
ng n, malaki O ng n nakalapat muli.

806
00:34:28,330 --> 00:34:30,650
Hindi ito tulad ng pakiramdam
isang mainam na kalalabasan.

807
00:34:30,650 --> 00:34:32,080
>> Kaya sabihin lamang i-update ito.

808
00:34:32,080 --> 00:34:35,120
Kaya ang laki ng queue
Hindi na 2.

809
00:34:35,120 --> 00:34:37,090
Ito ay ngayon lamang 1.

810
00:34:37,090 --> 00:34:40,360
Ngunit maaari ko na ngayong i-update ang isang bagay
Hindi ko i-update ang bago, ang

811
00:34:40,360 --> 00:34:41,130
harapan ng listahan.

812
00:34:41,130 --> 00:34:45,420
Maaari ko lang sabihin, ang lokasyon na 1?

813
00:34:45,420 --> 00:34:49,770
Kaya ngayon kami ay may basura halaga dito,
basura halaga dito, at David sa

814
00:34:49,770 --> 00:34:51,469
gitna ng basura ito.

815
00:34:51,469 --> 00:34:54,980
Ngunit ang data ng istraktura
ay pa rin buo.

816
00:34:54,980 --> 00:34:58,540
>> At sa katunayan, hindi ko kahit na kailangan upang
baguhin ang dating numero Jake ni

817
00:34:58,540 --> 00:35:00,460
9, dahil sino nagmamalasakit.

818
00:35:00,460 --> 00:35:04,470
Mayroon akong sapat na impormasyon ngayon sa
laki na alam ko may marami sa isang tao sa

819
00:35:04,470 --> 00:35:05,030
ito queue.

820
00:35:05,030 --> 00:35:08,340
At alam ko na ang taong iyon
ay nasa lokasyon 1, hindi 0.

821
00:35:08,340 --> 00:35:09,760
Hindi ako pagbibilang.

822
00:35:09,760 --> 00:35:11,300
Kaya 1 pati na rin.

823
00:35:11,300 --> 00:35:13,410
Kaya ang data ng istraktura pa rin ang OK.

824
00:35:13,410 --> 00:35:14,330
>> Well, kung ano ang susunod na mangyayari?

825
00:35:14,330 --> 00:35:15,010
Sabihin enqueue -

826
00:35:15,010 --> 00:35:15,370
ano ang pangalan mo?

827
00:35:15,370 --> 00:35:16,160
>> Madla: Callen.

828
00:35:16,160 --> 00:35:16,580
>> David MALAN: Callen.

829
00:35:16,580 --> 00:35:20,770
Sabihin enqueue isang Callen, at
22 ay nasa queue.

830
00:35:20,770 --> 00:35:22,300
Kaya ngayon kung ano ay may upang baguhin dito?

831
00:35:22,300 --> 00:35:24,380
Front ay hindi papunta sa
baguhin, nang walang alinlangan.

832
00:35:24,380 --> 00:35:27,160
Laki ay pagpunta upang baguhin upang maging 2 muli.

833
00:35:27,160 --> 00:35:31,590
At 22 ay nagtatapos up dito, 9 ay naroroon pa rin,
ngunit ito ay isang epektibong

834
00:35:31,590 --> 00:35:32,600
basura halaga ngayon.

835
00:35:32,600 --> 00:35:35,910
Ito ay lamang ng isang labi ng Jake nakaraan.

836
00:35:35,910 --> 00:35:39,200
>> Kaya ngayon kung ano ang mangyayari kung
Dequeue kong David?

837
00:35:39,200 --> 00:35:41,560
Isang huling operasyon, dequeue David.

838
00:35:41,560 --> 00:35:46,070
Maaari naming shift, ngunit ipanukala ko sabihin
gawin bilang maliit na trabaho hangga't maaari.

839
00:35:46,070 --> 00:35:50,280
Ngayon ang aking data istraktura napupunta
i-back sa laki 2-1.

840
00:35:50,280 --> 00:35:53,730
Ngunit sa harap ng pila
ngayon nagiging 2.

841
00:35:53,730 --> 00:35:56,640
Hindi ko kailangang baguhin ang mga bilang na ito
sa ngayon, dahil hindi nila

842
00:35:56,640 --> 00:35:58,230
lamang ang mga halaga ng basura.

843
00:35:58,230 --> 00:35:59,720
>> Ngunit ngayon kung ano ang mangyayari?

844
00:35:59,720 --> 00:36:03,280
Ipagpalagay ko enqueue sarili ko, 26?

845
00:36:03,280 --> 00:36:05,890
Pakiramdam ko ay tulad nabibilang ako sa ibabaw dito.

846
00:36:05,890 --> 00:36:06,890
Kaya ako ina-enqueued.

847
00:36:06,890 --> 00:36:08,760
Kaya ako uri ng nabibilang dito.

848
00:36:08,760 --> 00:36:11,300
At kahit na hindi mo pa masyadong
Pinahahalagahan ito biswal sa entablado,

849
00:36:11,300 --> 00:36:15,075
dahil kami ay may maraming kuwarto, ang dapat kong
Hindi ma-nakatayo dito, bakit?

850
00:36:15,075 --> 00:36:16,290
>> Madla: Naubusan ka na ng hanggahan.

851
00:36:16,290 --> 00:36:16,370
>> David MALAN: Kanan.

852
00:36:16,370 --> 00:36:16,940
Ako out sa hanggahan.

853
00:36:16,940 --> 00:36:19,330
Ko na ang na-index na higit sa
hanggahan ng array na ito.

854
00:36:19,330 --> 00:36:23,420
Ako talaga ay dapat nasa isa sa mga
tatlong posibleng mga lokasyon.

855
00:36:23,420 --> 00:36:25,150
Ngayon, nasaan ang pinaka-natural na pumunta?

856
00:36:25,150 --> 00:36:27,760
Ipanukala ko naming magagamit
sa isang linggo sa isang kahanga-hangang gawa.

857
00:36:27,760 --> 00:36:30,150
Ang mga mod operator, porsyento.

858
00:36:30,150 --> 00:36:36,850
Dahil technically ako nakatayo sa
3 lokasyon, ngunit kong gawin 3 mod kapasidad,

859
00:36:36,850 --> 00:36:40,250
kaya 3, isang porsiyento sign, 3 -

860
00:36:40,250 --> 00:36:40,970
kapasidad ang 3.

861
00:36:40,970 --> 00:36:41,720
Ano iyan?

862
00:36:41,720 --> 00:36:43,700
Ano ang natitira kapag
hatiin mo ang 3 sa pamamagitan ng 3?

863
00:36:43,700 --> 00:36:44,070
0.

864
00:36:44,070 --> 00:36:48,140
>> Kaya na naglalagay sa akin ay Jake noon,
na kung saan ay tunay mabuti.

865
00:36:48,140 --> 00:36:50,370
Kaya ngayon ang pagpapatupad
ng mga bagay na ito ang nangyayari sa

866
00:36:50,370 --> 00:36:51,250
maging isang bit ng isang sakit ng ulo.

867
00:36:51,250 --> 00:36:53,740
Ito ay talagang lamang ng isang linya
ng sakit ng ulo, ng code.

868
00:36:53,740 --> 00:36:56,580
Ngunit hindi bababa sa ngayon ay may basura
halaga dito, ngunit mayroong dalawang

869
00:36:56,580 --> 00:36:57,910
lehitimong ints dito.

870
00:36:57,910 --> 00:37:04,160
At inaangkin ko na ngayon na namin tapos
kung ano mismo ang kailangan namin upang gawin ito hangga't

871
00:37:04,160 --> 00:37:08,600
naming baguhin kung ano Jake ni
halaga ay upang maging 26.

872
00:37:08,600 --> 00:37:12,110
>> Kami ngayon ay may sapat na impormasyon pa rin
upang mapanatili ang integridad

873
00:37:12,110 --> 00:37:13,060
ng data na ito istraktura.

874
00:37:13,060 --> 00:37:17,160
Kami pa rin ang uri ng out ka sana kapag kami
nais upang ipasok apat o higit pang kabuuang

875
00:37:17,160 --> 00:37:20,740
mga elemento, ngunit maaari ko ng hindi bababa sa gawing kaakit-akit
mahusay na paggamit ng mga ito pare-pareho

876
00:37:20,740 --> 00:37:21,740
oras, sa katunayan.

877
00:37:21,740 --> 00:37:27,150
Hindi ko kailangang mag-alala tungkol sa paglilipat
lahat ng tao, pati na ni David ang pagkahilig noon.

878
00:37:27,150 --> 00:37:30,816
>> Ang anumang mga katanungan sa stack,
o ito queue?

879
00:37:30,816 --> 00:37:32,184
>> Madla: ba ang dahilan kung bakit
kailangan mo laki kaya alam mo

880
00:37:32,184 --> 00:37:34,010
kung saan upang magkaroon ng isang tao?

881
00:37:34,010 --> 00:37:34,770
>> David MALAN: Mismong.

882
00:37:34,770 --> 00:37:38,230
Kailangan kong malaman ang laki ng array
dahil kailangan kong malaman kung paano mismo

883
00:37:38,230 --> 00:37:41,940
marami sa mga halagang ito ay lehitimo,
at sa gayon ay maaari ko bang mahanap kung saan upang ilagay

884
00:37:41,940 --> 00:37:42,800
sa susunod na tao.

885
00:37:42,800 --> 00:37:43,300
Mismong.

886
00:37:43,300 --> 00:37:44,580
Ang laki ay -

887
00:37:44,580 --> 00:37:46,360
talaga, hindi kami i-update ito pa.

888
00:37:46,360 --> 00:37:48,380
Nagdagdag ako sa sarili ko 26.

889
00:37:48,380 --> 00:37:51,760
Ang laki na ngayon, hindi 1, pero 2.

890
00:37:51,760 --> 00:37:57,780
Kaya ngayon ito sa katunayan ay nakakatulong sa akin mahanap ang
ulo ng listahan, na kung saan ay hindi 0, hindi

891
00:37:57,780 --> 00:37:59,250
1, ngunit ay 2.

892
00:37:59,250 --> 00:38:01,665
Ang harap ng listahan
talaga ang numero 22.

893
00:38:01,665 --> 00:38:05,120
Dahil siya ay dumating sa unang, kaya dapat siya
pahihintulutang papunta sa tindahan bago sa akin,

894
00:38:05,120 --> 00:38:08,780
kahit na biswal na ako nakatayo
mas malapit sa mga tindahan.

895
00:38:08,780 --> 00:38:09,220
>> Ang lahat ng mga karapatan?

896
00:38:09,220 --> 00:38:12,410
Ang isang ikot ng papuri para sa mga guys
at ipapaalam namin sa out ang mga ito doon.

897
00:38:12,410 --> 00:38:17,090
>> [Palakpakan]

898
00:38:17,090 --> 00:38:18,150
>> David MALAN: kaya kong ipaalam
panatilihin mo ang tray.

899
00:38:18,150 --> 00:38:20,760
Maaari naming makita kung ano ang mangyayari kung
gusto mo, ngunit marahil hindi.

900
00:38:20,760 --> 00:38:21,590
Ayos lang.

901
00:38:21,590 --> 00:38:25,380
Kaya kung ano ngayon ay na mag-iwan sa amin?

902
00:38:25,380 --> 00:38:28,900
Well, hayaan mo akong magpanukala na mayroong isang
ilang iba pang data ng mga istraktura ng dati namin

903
00:38:28,900 --> 00:38:33,810
magsimulang magdagdag sa aming tool kit na kalooban
talaga lubos na, medyo may-katuturang mga bilang

904
00:38:33,810 --> 00:38:35,270
namin sumisid sa web stuff.

905
00:38:35,270 --> 00:38:38,150
Aling muli, ay may ilang mga uri ng koneksyon
sa mga puno sa anyo ng

906
00:38:38,150 --> 00:38:40,550
isang bagay na tinatawag na DOM, dokumento
bagay na modelo.

907
00:38:40,550 --> 00:38:42,370
Ngunit kailangan naming makita ang higit pa sa
na bago ang haba.

908
00:38:42,370 --> 00:38:46,260
>> Hayaan akong magpanukala definitionally na namin
tumawag puno ngayon kung ano ang maaaring kilala bilang

909
00:38:46,260 --> 00:38:48,820
higit pa sa isang family tree, kung saan ka
May ilang mga ninuno sa

910
00:38:48,820 --> 00:38:49,790
Roots ng puno.

911
00:38:49,790 --> 00:38:54,480
Ang isang makaama o isang matriarch sa
pinakatuktok ng puno.

912
00:38:54,480 --> 00:38:56,700
Kapag wala ang kanilang mga asawa, sa kasong ito.

913
00:38:56,700 --> 00:39:00,940
Ngunit kami ay mayroon na ngayong kung ano ang makikita namin tumawag
mga anak, na mga nodes na mag-hang

914
00:39:00,940 --> 00:39:05,480
off sa kaliwa anak o sa kanan anak,
mga arrow bilang itinatanghal dito.

915
00:39:05,480 --> 00:39:10,490
>> Sa ibang salita, sa isang puno istraktura ng data
sa computer, puno ng isang may zero

916
00:39:10,490 --> 00:39:11,480
o higit pang mga node.

917
00:39:11,480 --> 00:39:13,500
Kung ito ay may hindi bababa sa isang node,
na tinatawag na ugat ng.

918
00:39:13,500 --> 00:39:15,700
Ito ay ang mga bagay na biswal na
gumuhit kami sa tuktok.

919
00:39:15,700 --> 00:39:20,280
At node na, tulad ng anumang iba pang mga node, maaari
mayroon zero, isa, o dalawa, o tatlong,

920
00:39:20,280 --> 00:39:23,600
o gayunpaman maraming mga bata ang
data istraktura ay sumusuporta sa.

921
00:39:23,600 --> 00:39:29,150
Sa kasong ito, ang mga ugat, pag-iimbak ng mga
halaga ng isa, ay may dalawang mga bata, 2 at 3,

922
00:39:29,150 --> 00:39:33,020
kaya namin sa pangkalahatan ay tumawag 2 sa kaliwa
bata at 3 sa kanan anak.

923
00:39:33,020 --> 00:39:36,940
>> At pagkatapos ay kapag makuha namin down sa 5, 6, at
7, 6 na maaaring tawagin sa gitna anak.

924
00:39:36,940 --> 00:39:38,940
Kung mayroon kang apat na mga anak,
ito ay makakakuha ng nakalilito.

925
00:39:38,940 --> 00:39:42,260
Kaya naming ihinto ang paggamit ng ganoong uri
shortcut ng pasalita.

926
00:39:42,260 --> 00:39:44,580
Ngunit ito ay talagang lamang ng isang family tree.

927
00:39:44,580 --> 00:39:48,880
At ang mga dahon dito ay ang mga nodes na
mayroon kanilang mga sarili walang mga bata.

928
00:39:48,880 --> 00:39:52,540
Hang-off ang mga ito sa ilalim ng tree.

929
00:39:52,540 --> 00:39:56,940
>> Kaya kung paano namin ipatupad ang isang puno na
Mayroon lamang dalawang bata maximally?

930
00:39:56,940 --> 00:39:58,410
Susubukan naming tumawag ito ng isang binary tree.

931
00:39:58,410 --> 00:40:00,960
Bi muli ibig sabihin dalawa, sa ganitong
kaso, tulad ng sa binary.

932
00:40:00,960 --> 00:40:04,830
At sa gayon maaari itong magkaroon zero, isa,
o dalawang bata maximally.

933
00:40:04,830 --> 00:40:08,650
>> Kukunin ko ipanukala na namin ipapatupad ang node
para na istraktura sa isang int n,

934
00:40:08,650 --> 00:40:11,910
at pagkatapos ay dalawang payo, isa na tinatawag na
pakaliwa, isa na tinatawag na karapatan.

935
00:40:11,910 --> 00:40:14,830
Ngunit iyon lamang ang maganda
arbitrary balarila.

936
00:40:14,830 --> 00:40:18,170
At kung ano ang maganda ngayon, lalo na kung
uri ng struggled conceptually may

937
00:40:18,170 --> 00:40:21,300
recursion, o naisip na ito ay hindi
talaga isang solusyon sa anumang bagay,

938
00:40:21,300 --> 00:40:23,120
lalo na kung magagawa mong
Naubusan ng memorya.

939
00:40:23,120 --> 00:40:26,600
Ngayon na pinag-uusapan natin ang tungkol sa data
mga istraktura at mga algorithm na payagan

940
00:40:26,600 --> 00:40:31,030
sa amin sa pagtawid at manipulahin ang mga ito,
lumiliko out na recursion ay bumalik sa

941
00:40:31,030 --> 00:40:34,240
isang magkano ang mas nakakahimok
kung hindi magandang paraan.

942
00:40:34,240 --> 00:40:38,670
>> Kaya ito ipanukala ko ay ang pagpapatupad
ng isang Search function.

943
00:40:38,670 --> 00:40:39,870
Given dalawang input -

944
00:40:39,870 --> 00:40:41,570
kaya sa tingin ng mga ito bilang isang itim na kahon.

945
00:40:41,570 --> 00:40:46,560
Given dalawang input, n, isang int, at isang
pointer sa isang puno, isang pointer sa isang

946
00:40:46,560 --> 00:40:50,020
node, o talagang ugat ng isang puno, ako
paghabol na ang function na ito ay maaaring bumalik

947
00:40:50,020 --> 00:40:53,530
tama o mali, na ang halaga n
ay nasa loob ng tree.

948
00:40:53,530 --> 00:40:55,210
>> Ano ang nasa loob ng mga ito itim na kahon?

949
00:40:55,210 --> 00:40:57,440
Well, apat na sanga.

950
00:40:57,440 --> 00:40:58,385
Ang unang lamang ang sumusuri.

951
00:40:58,385 --> 00:41:00,490
Kung ang puno ay null, bumalik lang hindi totoo.

952
00:41:00,490 --> 00:41:04,580
Kung mayroong walang node, mayroong n walang,
mayroong walang numero, bumalik lang mali.

953
00:41:04,580 --> 00:41:12,330
Kung bagaman, n, ang halaga na iyong hinahanap
para sa, ay mas mababa sa puno n arrow, at

954
00:41:12,330 --> 00:41:15,180
para lamang maging malinaw, kung ano ang ibig sabihin kapag
Isulat ko ang tree at pagkatapos ay ang arrow

955
00:41:15,180 --> 00:41:18,150
pagtatanda, n?

956
00:41:18,150 --> 00:41:18,690
Mismong.

957
00:41:18,690 --> 00:41:21,970
Ito ay nangangahulugan na dereference
pointer tinatawag tree.

958
00:41:21,970 --> 00:41:26,750
Pumunta doon, at pagkatapos ay makakuha sa loob ng na
node at makakuha nito field na tinatawag n.

959
00:41:26,750 --> 00:41:30,810
At pagkatapos ay ihambing ang aktwal n na noon ay
pumasa sa Search laban dito.

960
00:41:30,810 --> 00:41:35,390
>> Kaya kung n ay mas mababa, ang halaga n
sa tree node mismo, na rin,

961
00:41:35,390 --> 00:41:36,720
ano ang nilalaman na ibig sabihin nito?

962
00:41:36,720 --> 00:41:40,690
Iyon ay nangangahulugang wala sa unang tingin.

963
00:41:40,690 --> 00:41:40,900
I-right?

964
00:41:40,900 --> 00:41:45,560
Katulad ng kapag mayroon kang isang hanay ng mga
mga halaga, maaari mong mag-apply binary

965
00:41:45,560 --> 00:41:48,290
maghanap bilang isang paraan ng hatiin
at lupigin.

966
00:41:48,290 --> 00:41:51,790
Ngunit ano ang palagay ay kailangan namin upang magsagawa ng
para sa binary paghahanap upang gumana sa lahat

967
00:41:51,790 --> 00:41:54,510
sa phone book at
mas maaga mga halimbawa?

968
00:41:54,510 --> 00:41:55,530
>> Paano na pinagsunod-sunod.

969
00:41:55,530 --> 00:41:59,490
Kaya sabihin pinuhin ang kahulugan ng puno
dito ay hindi upang maging lamang ng isang puno, na kung saan maaari

970
00:41:59,490 --> 00:42:00,880
magkaroon ng anumang bilang ng mga bata.

971
00:42:00,880 --> 00:42:04,700
Hindi lamang isang binary tree, kung saan maaari
mayroon kang 0, 1, 2 o maximally.

972
00:42:04,700 --> 00:42:09,700
Ngunit bilang isang binary puno ng paghahanap, o BST,
na kung saan ay lamang ng isang magarbong paraan ng sinasabi ng

973
00:42:09,700 --> 00:42:15,430
binary puno tulad na ang bawat node ni
kaliwa bata, kung kasalukuyan, ay

974
00:42:15,430 --> 00:42:16,830
mas mababa kaysa sa node.

975
00:42:16,830 --> 00:42:20,170
At karapatan bata bawat node ni,
kung kasalukuyan, ay mas malaki

976
00:42:20,170 --> 00:42:21,740
kaysa sa node mismo.

977
00:42:21,740 --> 00:42:25,200
>> Kaya sa ibang salita, kung ikaw ay upang gumuhit
sa puno out, ang lahat ng mga numero ay

978
00:42:25,200 --> 00:42:30,620
maingat na balanse ang ganito upang kung
mayroon kang 55 bilang root, 33 maaaring pumunta

979
00:42:30,620 --> 00:42:33,090
sa kaliwa nito dahil ito ay mas mababa kaysa sa 55.

980
00:42:33,090 --> 00:42:36,430
77 maaaring pumunta sa kanan nito dahil
ito ay mas malaki sa 55.

981
00:42:36,430 --> 00:42:40,750
Ngunit ngayon mapansin, ang parehong kahulugan,
ito ay isang recursive kahulugan sa salita,

982
00:42:40,750 --> 00:42:42,600
May mag-aplay para sa 33.

983
00:42:42,600 --> 00:42:47,610
33 ni kaliwa bata ay dapat mas mababa ito,
at kanan anak ni 33, 44, dapat

984
00:42:47,610 --> 00:42:48,580
mas malaki kaysa ito.

985
00:42:48,580 --> 00:42:51,670
>> Kaya ito ay isang binary puno ng paghahanap, at
Ipanukala ko, gamit ang isang kaunting

986
00:42:51,670 --> 00:42:53,910
recursion, maaari naming ngayon mahanap n.

987
00:42:53,910 --> 00:42:59,160
Kaya kung n ay mas mababa sa halaga n na
kasalukuyang node, pupuntahan ko pumunta

988
00:42:59,160 --> 00:43:04,090
Magpatuloy at magtikin, kaya na magsalita, at lamang
bumalik ano ang sagot ay sa

989
00:43:04,090 --> 00:43:08,470
naghahanap ng n sa
kaliwa anak ni puno.

990
00:43:08,470 --> 00:43:11,370
Pansinin muli, function na ito lamang
Inaasahan ng isang node bituin, isang

991
00:43:11,370 --> 00:43:12,780
pointer sa isang node.

992
00:43:12,780 --> 00:43:17,360
Kaya tiyak lamang ako maaaring magawa puno
kaliwang arrow, na kung saan ay hahantong

993
00:43:17,360 --> 00:43:18,400
sa akin sa isa pang node.

994
00:43:18,400 --> 00:43:19,480
Ngunit ano ang node na?

995
00:43:19,480 --> 00:43:22,820
>> Well, ayon sa pahayag na ito,
kaliwa lamang ang pointer, kaya na lamang

996
00:43:22,820 --> 00:43:27,090
ibig sabihin ako ng pagpasa sa pag-andar ng paghahanap
ng ibang pointer, lalo

997
00:43:27,090 --> 00:43:30,750
ang isa na kumakatawan
puno ang aking kaliwang anak.

998
00:43:30,750 --> 00:43:36,040
Kaya sa kasong ito, ang pointer sa 33, kung
ito ay ang aming sample input Samantala, kung

999
00:43:36,040 --> 00:43:40,740
n ay mas mataas kaysa sa halaga n sa
kasalukuyang node sa tree, pagkatapos ay ako

1000
00:43:40,740 --> 00:43:43,370
pagpunta sa sige at magtikin sa iba pang mga
direksyon at lang sabihin, gawin ko hindi

1001
00:43:43,370 --> 00:43:47,280
malalaman kung ang halagang ito n ay sa tree,
pero alam ko kung ito ay, ito ay ang aking

1002
00:43:47,280 --> 00:43:49,090
karapatan branch, kaya na magsalita.

1003
00:43:49,090 --> 00:43:53,120
Kaya ipaalam sa akin recursively tawagan kayo maghanap,
pagdaan ng isang n ulit, pero ang pagpasa sa isang

1004
00:43:53,120 --> 00:43:54,580
pointer sa aking kanan anak.

1005
00:43:54,580 --> 00:44:00,020
>> Sa ibang salita, kung ako sa kasalukuyan sa 55
at Naghahanap ako para sa 99, alam ko na 99

1006
00:44:00,020 --> 00:44:04,270
ay mas malaki sa 55, kaya lang tulad ko torus
ang phone book linggo ang nakalipas at hindi na namin

1007
00:44:04,270 --> 00:44:07,140
nagpunta ang mga karapatan, katulad tayo
pagpunta sa pumunta dito mismo.

1008
00:44:07,140 --> 00:44:11,960
At hindi ko alam kung ito ay sa aking mga karapatan
bata, at ito ay hindi, 77 ay doon, ngunit

1009
00:44:11,960 --> 00:44:13,210
Alam ko ito sa na direksyon.

1010
00:44:13,210 --> 00:44:18,770
Kaya tumawag ako sa paghahanap sa aking kanan anak,
77, at hayaan ang paghahanap figure out mula sa

1011
00:44:18,770 --> 00:44:24,950
kung may 99 na ito sa di-makatwirang
Halimbawa ay talagang doon.

1012
00:44:24,950 --> 00:44:26,900
>> Iba Pa, ano ang huling kaso?

1013
00:44:26,900 --> 00:44:28,620
Kung ang puno ay walang bisa ay isa kaso.

1014
00:44:28,620 --> 00:44:31,890
Kung n ay mas mababa kaysa sa kasalukuyang node ni
halaga ay isa pang kaso.

1015
00:44:31,890 --> 00:44:35,120
Kung n ay mas mataas kaysa sa kasalukuyang
node na halaga ay isang third kaso.

1016
00:44:35,120 --> 00:44:38,250
Ano ang pang-apat at huling kaso?

1017
00:44:38,250 --> 00:44:39,480
Sa tingin ko kami ay out ng mga kaso, tama?

1018
00:44:39,480 --> 00:44:44,690
Ito dapat na n ay nasa
kasalukuyang node na ako sa.

1019
00:44:44,690 --> 00:44:49,640
>> Kaya kung ako naghahanap ng mga 55 sa puntong ito
sa mga kuwento, na sangay ng

1020
00:44:49,640 --> 00:44:51,780
puno ay magbabalik totoo.

1021
00:44:51,780 --> 00:44:55,380
Kaya kung ano ang kawili-wiling dito ay ang pagpapalit namin
talaga, hindi tulad ng mga linggo nakaraan, kami uri

1022
00:44:55,380 --> 00:44:56,740
magkaroon ng dalawang mga kaso base.

1023
00:44:56,740 --> 00:44:58,300
At hindi nila kailangang mag-
maging lahat sa tuktok.

1024
00:44:58,300 --> 00:45:01,390
Ang tuktok ay isang base ng kaso dahil kung ang
puno ay null, mayroong walang kinalaman.

1025
00:45:01,390 --> 00:45:03,410
Bumalik lang ng hard-code
halaga ng huwad.

1026
00:45:03,410 --> 00:45:07,400
>> Ang ilalim ng sangay ay isang uri ng mga
default, kung saan kung kami naka-check para sa

1027
00:45:07,400 --> 00:45:11,550
null, kami naka-check kung ito ay kailangang maging
umalis, ngunit hindi ito dapat maging, na namin

1028
00:45:11,550 --> 00:45:14,640
naka-check kung ito ay kailangang maging karapatan, ngunit ito
hindi dapat, malinaw na ito ay dapat na

1029
00:45:14,640 --> 00:45:15,870
karapatan kung nasaan kami.

1030
00:45:15,870 --> 00:45:16,780
Iyan ay isang batayang case.

1031
00:45:16,780 --> 00:45:19,920
Kaya mayroong dalawang mga kaso recursive
sandwiched doon sa gitna.

1032
00:45:19,920 --> 00:45:21,630
Ngunit maaaring isinulat ko
ito sa anumang pagkakasunud-sunod.

1033
00:45:21,630 --> 00:45:24,520
Ko lang naisip ito uri ng nadama natural
sa unang suriin para sa isang posibleng mga error,

1034
00:45:24,520 --> 00:45:28,340
pagkatapos suriin pakaliwa, pagkatapos ay i-check ang karapatan, pagkatapos ay
ipinapalagay na ikaw ay sa node

1035
00:45:28,340 --> 00:45:30,630
talaga ang hinahanap mo.

1036
00:45:30,630 --> 00:45:36,240
>> Kaya bakit ito ay maaaring maging kapaki-pakinabang?

1037
00:45:36,240 --> 00:45:37,910
Kaya ito lumiliko out -

1038
00:45:37,910 --> 00:45:42,110
at hayaan mo akong lumipat sa teaser
dito na sa web.

1039
00:45:42,110 --> 00:45:44,920
Kami ay pagpunta sa simulan ang paggamit ng isang hindi
mga programa na wika sa unang, ngunit isang

1040
00:45:44,920 --> 00:45:46,030
markup language.

1041
00:45:46,030 --> 00:45:48,740
Ang isang markup language pagiging isang bagay na
katulad sa espiritu sa programming

1042
00:45:48,740 --> 00:45:51,715
wika, ngunit hindi ito nagbibigay sa iyo ng
kakayahan upang ipahayag ang iyong sarili lohikal.

1043
00:45:51,715 --> 00:45:55,070
Ito lamang ay nagbibigay sa iyo ng kakayahan upang
ipahayag ang iyong sarili structurally.

1044
00:45:55,070 --> 00:45:57,960
>> Saan ang nais mong ilagay ang isang bagay
sa pahina, ang web page na ito?

1045
00:45:57,960 --> 00:45:59,200
Anong kulay ang gusto mong gawin ito?

1046
00:45:59,200 --> 00:46:00,950
Ano ang laki ng font ang gusto mong gawin ito?

1047
00:46:00,950 --> 00:46:02,970
Ano ang mga salita gawin mo talaga
gusto sa web page?

1048
00:46:02,970 --> 00:46:04,060
Kaya na ang isang markup language.

1049
00:46:04,060 --> 00:46:07,690
Ngunit pagkatapos ay magpapadala kami masyadong mabilis ipakilala
JavaScript, na isang full-nasimulan

1050
00:46:07,690 --> 00:46:08,560
mga programa wika.

1051
00:46:08,560 --> 00:46:12,530
Tunay na katulad syntactically sa hitsura
sa C, ngunit magkakaroon ito ng ilang

1052
00:46:12,530 --> 00:46:15,200
magaling, mas malakas, mas
user friendly na mga tampok.

1053
00:46:15,200 --> 00:46:18,050
>> At ang isa sa mga frustrations sa ito
punto sa semestre ay na bibigyan namin ng

1054
00:46:18,050 --> 00:46:22,065
madaling ipatupad speller sa malayo mas kaunting
linya ng code gamit ang iba pang mga wika

1055
00:46:22,065 --> 00:46:25,580
C kaysa sa sarili nito ay nagbibigay-daan, ngunit para sa dahilan ng
ipapakita namin sa lalong madaling panahon maunawaan.

1056
00:46:25,580 --> 00:46:27,750
Ito ang magiging unang tulad ng web page.

1057
00:46:27,750 --> 00:46:30,120
Ito ay magiging ganap na underwhelming,
ang unang isa ginawa namin.

1058
00:46:30,120 --> 00:46:31,400
Ito ay simpleng sabihin, kumusta mundo.

1059
00:46:31,400 --> 00:46:34,010
Ngunit kung hindi mo pa nakikita ito
bago, ito ay HTML,

1060
00:46:34,010 --> 00:46:35,670
Hypertext Markup Language.

1061
00:46:35,670 --> 00:46:39,310
>> Kung pupunta ka sa isang tiyak na pagpipilian sa menu
karamihan ng anumang browser, sa anumang web page sa

1062
00:46:39,310 --> 00:46:43,160
ang internet, maaari mong makita ang HTML
na ang ilang mga tao ay sumulat sa

1063
00:46:43,160 --> 00:46:44,400
lumikha ng mga web na pahina.

1064
00:46:44,400 --> 00:46:47,850
At ito ay malamang na hindi kamukha ng
maikling o bilang kapong baka bilang na ito.

1065
00:46:47,850 --> 00:46:51,400
Ngunit ito ay sundin ang mga pattern ng mga
open bracket at slashes at

1066
00:46:51,400 --> 00:46:53,660
titik at potensyal na mga numero.

1067
00:46:53,660 --> 00:46:56,770
>> Naisip ko na gusto kong bigyan ka ng isang teaser
ng kung ano ang magagawa mong gawin

1068
00:46:56,770 --> 00:46:57,950
pagkatapos ng pagkuha ng CS50.

1069
00:46:57,950 --> 00:47:02,620
Hayaan akong pumunta sa cs.harvard.edu / looban,
ating sariling Rob Bowden gumagana sa homepage.

1070
00:47:02,620 --> 00:47:06,080
Siya ginawa ito para sa amin.

1071
00:47:06,080 --> 00:47:07,490
Kaya makikita mo sa lalong madaling panahon magagawang upang gawin iyon.

1072
00:47:07,490 --> 00:47:10,660
At din, kung ano ang iyong narinig
ito umaga -

1073
00:47:10,660 --> 00:47:12,480
kung ano ang iyong narinig ito umaga -

1074
00:47:12,480 --> 00:47:13,780
>> [Hamster dance musika]

1075
00:47:13,780 --> 00:47:15,702
>> - You'll magagawang gumawa ito.

1076
00:47:15,702 --> 00:47:16,790
Na naghihintay sa amin sa Miyerkules.

1077
00:47:16,790 --> 00:47:17,791
Kami ay makita mo pagkatapos.

1078
00:47:17,791 --> 00:47:22,950
>> [Hamster dance musika]

1079
00:47:22,950 --> 00:47:24,300
David MALAN: Sa susunod na CS50 -

1080
00:47:24,300 --> 00:47:31,670