1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> Tagapagsalita 1: Ang lahat ng mga karapatan, sa gayon ito ay
CS50 ito ay ang katapusan ng linggo limang.

3
00:00:15,860 --> 00:00:19,220
At isipin na ang huling oras na namin
nagsimula ang pagtingin sa mga may interes data

4
00:00:19,220 --> 00:00:22,310
istruktura na nagsimula upang malutas
problema, na nagsimula upang ipakilala

5
00:00:22,310 --> 00:00:25,640
bagong mga problema, ngunit ang key na ito
ay ang uri ng threading na tayo

6
00:00:25,640 --> 00:00:27,940
nagsimula na gawin mula sa node sa node.

7
00:00:27,940 --> 00:00:30,085
Kaya ito ng mga kurso ay
isang isa-isa naka-link na listahan.

8
00:00:30,085 --> 00:00:31,960
At sa pamamagitan ng isa-isa naka-link,
Ibig kong sabihin may isa lamang

9
00:00:31,960 --> 00:00:33,380
thread sa pagitan ng bawat isa sa mga nodes.

10
00:00:33,380 --> 00:00:35,890
Lumiliko out na maaari mong gawin ng may interes
mga bagay tulad ng doble listahan ng link

11
00:00:35,890 --> 00:00:38,470
kung saan ikaw ay may isang arrow
pagpunta sa parehong direksyon, na kung saan

12
00:00:38,470 --> 00:00:40,320
maaaring makatulong sa ilang mga kahusayan.

13
00:00:40,320 --> 00:00:42,000
Ngunit ito nalutas na ang problema?

14
00:00:42,000 --> 00:00:43,500
Ano ang problema ay malutas ito?

15
00:00:43,500 --> 00:00:46,620
Bakit pag-aalaga namin sa Lunes?

16
00:00:46,620 --> 00:00:49,820
Bakit, sa teorya, ay nagmamalasakit kami sa Lunes?

17
00:00:49,820 --> 00:00:50,630
Ano ang ginagawa nito?

18
00:00:50,630 --> 00:00:51,950
>> Madla: Maaari dynamic naming baguhin ang laki nito.

19
00:00:51,950 --> 00:00:53,740
>> Tagapagsalita 1: OK, upang maaari naming
magilas na baguhin ang laki nito.

20
00:00:53,740 --> 00:00:54,710
Magaling sa inyong dalawa.

21
00:00:54,710 --> 00:00:57,560
Kaya maaari mong dynamic na baguhin ang laki ng mga ito
istraktura ng data, kung saan ang isang array,

22
00:00:57,560 --> 00:01:00,760
pagpapabalik, kailangan mong malaman kung ang isang
walang pagsubok kung magkano ang space na gusto mo

23
00:01:00,760 --> 00:01:03,870
at kung kailangan mo ng kaunti pa
space, ikaw ay uri ng out of luck.

24
00:01:03,870 --> 00:01:05,560
Mayroon kang lumikha ng isang buong bagong array.

25
00:01:05,560 --> 00:01:07,893
Kailangan mong ilipat ang lahat ng iyong
data mula sa isa sa iba pang,

26
00:01:07,893 --> 00:01:10,600
huli free ang lumang array
maaari mong, at pagkatapos ay magpatuloy kung.

27
00:01:10,600 --> 00:01:13,891
Aling lamang pakiramdam ng masyadong magastos at napaka
walang kakayahan, at sa katunayan ito ay maaaring.

28
00:01:13,891 --> 00:01:14,890
Ngunit ito ay hindi lahat ng mabuti.

29
00:01:14,890 --> 00:01:18,180
Nagbabayad kami ng isang presyo, ano ang isa
sa mga mas malinaw na mga presyo namin

30
00:01:18,180 --> 00:01:20,550
magbayad sa pamamagitan ng paggamit ng isang listahan ng mga link?

31
00:01:20,550 --> 00:01:22,825
>> Madla: Mayroon kaming upang gamitin ang
double space para sa bawat isa.

32
00:01:22,825 --> 00:01:25,200
Tagapagsalita 1: Oo, kaya kailangan namin
ng hindi bababa sa dalawang beses ng mas maraming espasyo.

33
00:01:25,200 --> 00:01:27,700
Sa katunayan, ako na natanto na larawan na ito
kahit na isang maliit na mali,

34
00:01:27,700 --> 00:01:32,200
dahil sa CS50 IDE sa isang pulutong ng mga modernong
mga computer, ang isang pointer o address

35
00:01:32,200 --> 00:01:33,700
ay hindi sa katunayan apat na bytes.

36
00:01:33,700 --> 00:01:36,090
Very madalas ang mga ito ay
araw walong bytes, kung saan

37
00:01:36,090 --> 00:01:38,530
nangangahulugan ibaba karamihan
parihaba doon sa katotohanan

38
00:01:38,530 --> 00:01:40,900
mga uri ng dalawang beses bilang
malaking bilang kung ano ang iginuhit ko na,

39
00:01:40,900 --> 00:01:44,409
na nangangahulugan na ikaw ay gumagamit ng tatlong beses ng
mas maraming espasyo bilang ay magkaroon tayo ng ibang paraan.

40
00:01:44,409 --> 00:01:46,700
Ngayon at sa parehong oras, hindi namin
pakikipag-usap pa rin bytes, di ba?

41
00:01:46,700 --> 00:01:49,140
Hindi kami palaging pakikipag-usap
megabytes o gigabytes,

42
00:01:49,140 --> 00:01:51,000
maliban kung ang mga data kaayusan makakuha ng malaki.

43
00:01:51,000 --> 00:01:54,510
>> At kaya ngayon namin simulan upang isaalang-alang
kung paano namin maaaring galugarin ang data

44
00:01:54,510 --> 00:01:57,310
mas mahusay kung in
katunayan ang data ay makakakuha ng mas malaki.

45
00:01:57,310 --> 00:02:00,360
Ngunit sabihin subukan upang canonicalize ipaalam
ang operasyon ng unang

46
00:02:00,360 --> 00:02:02,460
na maaari mong gawin sa mga
mga uri ng istruktura ng data.

47
00:02:02,460 --> 00:02:04,790
Kaya ang isang bagay tulad ng isang naka-link
list pangkalahatan ay sumusuporta sa

48
00:02:04,790 --> 00:02:07,514
operations gusto tanggalin,
ipasok, at sa paghahanap.

49
00:02:07,514 --> 00:02:08,639
At kung ano ang ibig sabihin ako sa pamamagitan ng na?

50
00:02:08,639 --> 00:02:11,222
Iyon ay nangangahulugan lamang na kadalasan,
kung ang mga tao ay gumagamit ng naka-link na listahan,

51
00:02:11,222 --> 00:02:14,287
sila o sa ibang tao ay ipinatupad
function tulad ng delete, insert,

52
00:02:14,287 --> 00:02:16,120
at sa paghahanap, sa gayon maaari mong
talagang gawin ang isang bagay

53
00:02:16,120 --> 00:02:18,030
kapaki-pakinabang sa mga istraktura ng data.

54
00:02:18,030 --> 00:02:20,760
Kaya sabihin kumuha ng isang mabilis na pagtingin
sa kung paano namin maaaring ipatupad

55
00:02:20,760 --> 00:02:24,530
ang ilang mga code para sa isang listahan ng mga link tulad ng sumusunod.

56
00:02:24,530 --> 00:02:27,885
>> Kaya ito ay ilan lamang sa C code,
hindi kahit isang kumpletong programa

57
00:02:27,885 --> 00:02:29,260
na ako tunay mabilis wip up.

58
00:02:29,260 --> 00:02:32,300
Ito ay hindi online sa pamamahagi
code, dahil hindi ito aktwal na tatakbo.

59
00:02:32,300 --> 00:02:33,790
Ngunit mapansin na hindi ko na lang
sa isang komento nagsabi,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, may isang bagay
doon, tuldok tuldok tuldok, isang bagay doon.

61
00:02:36,130 --> 00:02:38,410
At Tingnan lang natin ang hahanapin
kung ano ang mga makatas mga bahagi ay.

62
00:02:38,410 --> 00:02:40,790
Kaya sa tatlong linya,
pagpapabalik na ito ay ngayon

63
00:02:40,790 --> 00:02:45,960
namin ipinanukalang deklarasyon ng isang node huling
panahon, isa sa mga parihabang bagay.

64
00:02:45,960 --> 00:02:48,790
Ito ay may isang int na namin ang tawag N,
ngunit kami ay maaaring tumawag ito anumang bagay,

65
00:02:48,790 --> 00:02:51,920
at pagkatapos ng isang struct node bituin na tinatawag na susunod.

66
00:02:51,920 --> 00:02:55,520
At upang maging lamang malinaw, na second
line, sa anim na linya, ano na?

67
00:02:55,520 --> 00:02:57,930
Ano ang ginagawa nito para sa amin?

68
00:02:57,930 --> 00:03:01,044
Dahil ito ay tiyak na mukhang mas
cryptic sa aming karaniwang mga variable.

69
00:03:01,044 --> 00:03:02,740
>> Madla: Ito ay ginagawang ilipat sa ibabaw ng isa.

70
00:03:02,740 --> 00:03:04,650
>> Tagapagsalita 1: Ito ay ginagawang ilipat sa ibabaw ng isa.

71
00:03:04,650 --> 00:03:08,580
At upang maging mas tiyak,
ito store ang address

72
00:03:08,580 --> 00:03:11,582
ng node na ay sinadya upang maging
semantically sa tabi nito, di ba?

73
00:03:11,582 --> 00:03:13,540
Kaya ito ay hindi pagpunta sa
kinakailangang ilipat ang anumang bagay.

74
00:03:13,540 --> 00:03:15,290
Lamang Ito ay pagpunta sa
tindahan ng isang halaga, na kung saan ay

75
00:03:15,290 --> 00:03:17,170
magiging address
ng ilang mga iba pang node,

76
00:03:17,170 --> 00:03:20,810
at iyon ang dahilan kung bakit namin sinabi na struct
node star, ang star nagsasaad

77
00:03:20,810 --> 00:03:22,370
isang pointer o address.

78
00:03:22,370 --> 00:03:26,390
OK, kaya ngayon kung akala mo na mayroon kami
na magagamit sa amin ang N, at sabihin

79
00:03:26,390 --> 00:03:29,490
ipalagay na ang ibang tao ay may
nakapasok ng buong bungkos ng mga integer

80
00:03:29,490 --> 00:03:30,400
sa isang listahan ng mga link.

81
00:03:30,400 --> 00:03:35,640
At na listahan ng mga link ay
nakatutok sa pamamagitan ng ilang mga punto

82
00:03:35,640 --> 00:03:39,040
isang variable na tinatawag na listahan na
lumipas in dito bilang isang parameter,

83
00:03:39,040 --> 00:03:43,120
paano ko pumunta tungkol sa line
14 pagpapatupad ng paghahanap?

84
00:03:43,120 --> 00:03:45,990
Sa ibang salita, kung ako ay pagpapatupad
function na ang layunin sa buhay

85
00:03:45,990 --> 00:03:48,889
ay ang kumuha ng isang int at pagkatapos ay ang
simula ng isang listahan ng mga link,

86
00:03:48,889 --> 00:03:50,430
iyon ay isang pointer sa naka-link na listahan.

87
00:03:50,430 --> 00:03:52,992
Tulad ng una, na sa tingin ko David
ay ang aming volunteer sa Lunes,

88
00:03:52,992 --> 00:03:54,700
siya ay nakaturo sa
ang buong listahan ng mga link,

89
00:03:54,700 --> 00:03:57,820
ito ay bilang bagaman kami ay pagpasa
David sa bilang ating argument dito.

90
00:03:57,820 --> 00:03:59,990
Paano namin pumunta tungkol bumabagtas sa listahang ito?

91
00:03:59,990 --> 00:04:04,640
Well, ito ay lumiliko out na kahit na
mga payo ay relatibong bago ngayon sa amin,

92
00:04:04,640 --> 00:04:07,010
maaari naming gawin ito relatibong
tuwiran.

93
00:04:07,010 --> 00:04:09,500
>> Pupunta ako sa sige at
magpahayag ng isang pansamantalang variable na

94
00:04:09,500 --> 00:04:12,364
sa pamamagitan ng convention ay lamang ang pagpunta
na tinatawag na pointer, o PTR,

95
00:04:12,364 --> 00:04:14,030
ngunit maaari kang tumawag ito anumang nais mo.

96
00:04:14,030 --> 00:04:16,470
At ako pagpunta sa magpasimula
ito sa simula ng listahan.

97
00:04:16,470 --> 00:04:20,050
Kaya maaari mong uri ng tingin ng mga ito
bilang ako guro sa isang araw,

98
00:04:20,050 --> 00:04:23,580
uri ng pagturo sa isang tao
sa gitna ng aming mga kawani na tao bilang boluntaryo.

99
00:04:23,580 --> 00:04:26,470
Kaya ako ng isang pansamantalang variable na
lamang ng pagturo sa parehong bagay

100
00:04:26,470 --> 00:04:31,390
na ang aming coincidentally pinangalanan
volunteer David ay din ng pagturo out.

101
00:04:31,390 --> 00:04:35,440
Ngayon habang pointer ay
hindi null, dahil pagpapabalik

102
00:04:35,440 --> 00:04:40,350
na null ay ang ilang mga espesyal na halaga nagbabantay
ang demarkasyon sa dulo ng listahan,

103
00:04:40,350 --> 00:04:44,280
kaya habang hindi ko na nakaturo sa
lupa tulad ng aming huling volunteer

104
00:04:44,280 --> 00:04:47,190
ay, sabihin sige
at gawin ang sumusunod.

105
00:04:47,190 --> 00:04:51,820
Kung pointer-- at ngayon ako uri ng gusto
upang gawin kung ano ang ginawa namin sa mag-aaral ang

106
00:04:51,820 --> 00:04:57,410
structure-- kung pointer tuldok sa tabi
equals-- halip, kung pointer dot N katumbas

107
00:04:57,410 --> 00:05:02,290
ay katumbas ng variable N, ang
argument na na lumipas sa,

108
00:05:02,290 --> 00:05:05,370
pagkatapos ay gusto kong sige
at sabihin nagbabalik ng tunay.

109
00:05:05,370 --> 00:05:11,020
Ako ay may natagpuan ang bilang N sa loob ng
isa sa mga node ng aking listahan na naka-link.

110
00:05:11,020 --> 00:05:13,500
Ngunit walang mga tuldok na
gumagana sa kontekstong ito,

111
00:05:13,500 --> 00:05:17,260
dahil pointer, PTR, ay
sa katunayan ng isang pointer, isang address,

112
00:05:17,260 --> 00:05:20,632
talaga namin maaari kamangha-mangha
gamitin ang wakas ng isang piraso ng syntax

113
00:05:20,632 --> 00:05:22,590
na uri ng mga gumagawa
intuitive na kahulugan at ang tunay na

114
00:05:22,590 --> 00:05:27,870
gamitin ang isang arrow dito, na nangangahulugan na pumunta mula sa
address na sa integer may in.

115
00:05:27,870 --> 00:05:30,160
Kaya ito ay lubos na katulad sa
espiritu na ang tuldok operator,

116
00:05:30,160 --> 00:05:33,860
ngunit dahil pointer ay hindi isang pointer
at hindi isang aktwal struct mismo,

117
00:05:33,860 --> 00:05:35,380
gamitin lamang namin ang mga arrow.

118
00:05:35,380 --> 00:05:40,620
>> Kaya kung ang kasalukuyang node na ako, ang
pansamantalang variable, ay tumuturo sa

119
00:05:40,620 --> 00:05:43,060
Hindi N, ano ang gusto kong gawin?

120
00:05:43,060 --> 00:05:45,910
Well, sa aking mga tao boluntaryo
na nagkaroon kami dito sa ibang mga araw,

121
00:05:45,910 --> 00:05:49,710
kung ang aking unang tao ay hindi ang isa ko
gusto, at marahil ang pangalawang tao ay hindi

122
00:05:49,710 --> 00:05:52,660
ang isa na nais ko, at sa pangatlo, ako
kailangan upang mapanatili ang pisikal na paglipat.

123
00:05:52,660 --> 00:05:54,690
Tulad ng kung paano mo ako na hakbang sa pamamagitan ng isang listahan?

124
00:05:54,690 --> 00:05:57,470
Mo ang Kapag nagkaroon kami ng isang array,
ginawa lamang tulad ko plus plus.

125
00:05:57,470 --> 00:06:03,660
Ngunit sa kasong ito, sapat na
gawin pointer, nakakakuha, pointer, susunod.

126
00:06:03,660 --> 00:06:07,580
Sa ibang salita, ang susunod na field
ay tulad ng lahat ng kaliwang kamay

127
00:06:07,580 --> 00:06:10,880
na ang aming mga tao boluntaryo sa Lunes
ay gamit upang ituro sa ilang iba pang mga node.

128
00:06:10,880 --> 00:06:12,890
Mga ay ang kanilang susunod na mga kapitbahay.

129
00:06:12,890 --> 00:06:17,060
>> Kaya kung gusto kong magbasa-basa sa listahan na ito,
Hindi ko lang gagawin ko plus plus anymore,

130
00:06:17,060 --> 00:06:20,120
Sa halip ko na kailangang sabihin
I, pointer, ay pagpunta

131
00:06:20,120 --> 00:06:24,650
sa pantay ano man ang susunod na field ay,
ang susunod na field ay, ang susunod na field ay,

132
00:06:24,650 --> 00:06:28,350
pagsunod sa lahat ng mga kaliwa sa kamay
na nagkaroon kami sa entablado pagturo

133
00:06:28,350 --> 00:06:30,000
sa ilang mga kasunod na mga halaga.

134
00:06:30,000 --> 00:06:32,590
At kung makakuha ako sa pamamagitan ng
na ang buong pag-ulit,

135
00:06:32,590 --> 00:06:39,330
at sa wakas, ako pindutin null hindi pagkakaroon
natagpuan N pa, babalik ko na lang na hindi totoo.

136
00:06:39,330 --> 00:06:44,100
Kaya muli, ang lahat na ginagawa namin dito,
bilang sa bawat ang mga larawan ng ilang sandali ang nakalipas,

137
00:06:44,100 --> 00:06:47,840
ay nagsisimula sa pamamagitan ng pagturo sa
simula ng listahan siguro.

138
00:06:47,840 --> 00:06:50,970
At pagkatapos kong i-check, ay ang halaga
Naghahanap ako ng katumbas ng siyam?

139
00:06:50,970 --> 00:06:52,650
Kung gayon, bumalik ako totoo at ako tapos na.

140
00:06:52,650 --> 00:06:56,450
Kung hindi, i-update ko ang aking kamay,
AKA pointer, upang ituro

141
00:06:56,450 --> 00:06:59,540
sa lokasyon na ang susunod na arrow, at
pagkatapos ay lokasyon sa susunod na arrow,

142
00:06:59,540 --> 00:07:00,480
at sa susunod.

143
00:07:00,480 --> 00:07:03,770
Lang ako sa paglalakad sa pamamagitan ng array.

144
00:07:03,770 --> 00:07:06,010
>> Kaya muli, na nagmamalasakit?

145
00:07:06,010 --> 00:07:07,861
Tulad ng kung ano ito ng isang sangkap para sa?

146
00:07:07,861 --> 00:07:10,360
Well, isipin ang na ipinakilala namin
ang paniwala ng isang stack, na

147
00:07:10,360 --> 00:07:15,400
ay i-type ang isang abstract data sa abot ng ito ay
hindi isang C bagay, ito ay hindi isang CS50 bagay,

148
00:07:15,400 --> 00:07:19,430
ito ay isang abstract na ideya, ito ideya ng
stacking mga bagay sa ibabaw ng bawat isa

149
00:07:19,430 --> 00:07:21,820
na maaaring ipatupad sa
kumpol na iba't ibang paraan.

150
00:07:21,820 --> 00:07:25,600
At isang paraan namin iminungkahi ay may
isang array, o sa isang naka-link na listahan.

151
00:07:25,600 --> 00:07:29,570
At ito ay lumiliko out na canonically, isang
stack sinusuportahan ng hindi bababa sa dalawang mga operasyon.

152
00:07:29,570 --> 00:07:32,320
At ang mga salita buzz ay push, upang
itulak ang isang bagay papunta sa stack,

153
00:07:32,320 --> 00:07:34,770
tulad ng isang bagong tray sa
dining hall, o pop,

154
00:07:34,770 --> 00:07:39,000
na nangangahulugan na tanggalin ang kataas-taasan
tray mula sa stack sa dining

155
00:07:39,000 --> 00:07:41,500
hall, at pagkatapos ay marahil ilang
iba pang mga pagpapaandar na rin.

156
00:07:41,500 --> 00:07:45,770
Kaya kung paano namin maaaring tukuyin ang istraktura
na ngayon kami ay pagtawag ng isang stack?

157
00:07:45,770 --> 00:07:50,020
>> Well, kami ay lahat ng mga bagay na kailangan
syntax sa aming itapon sa C. sinasabi ko,

158
00:07:50,020 --> 00:07:53,830
bigyan ako ng isang uri ng kahulugan ng
isang struct sa loob ng isang stack,

159
00:07:53,830 --> 00:07:58,030
Pupunta ako sa sabihin ay isang array, ng isang
buong grupo ng mga numero at pagkatapos ay ang laki.

160
00:07:58,030 --> 00:08:00,930
Kaya sa ibang salita, kung gusto ko
upang ipatupad ito sa code,

161
00:08:00,930 --> 00:08:03,830
hayaan mo akong pumunta at lamang uri ng
gumuhit ng kung ano ito ay sinasabi.

162
00:08:03,830 --> 00:08:06,317
Kaya ito ay nagsasabi, bigyan ako ng isang
structure na nakuha ng isang array,

163
00:08:06,317 --> 00:08:09,400
at hindi ko alam kung ano ang kapasidad ay,
ito ay tila ang ilang mga tapat na ko

164
00:08:09,400 --> 00:08:10,858
tinukoy sa ibang lugar, at na fine.

165
00:08:10,858 --> 00:08:15,260
Ngunit ipagpalagay na ito ay isa lamang,
dalawa, tatlo, apat, lima.

166
00:08:15,260 --> 00:08:16,700
Kaya kapasidad ay 5.

167
00:08:16,700 --> 00:08:21,730
Elementong ito sa loob ng aking
istraktura ay tinatawag na numero.

168
00:08:21,730 --> 00:08:24,020
At pagkatapos ay kailangan ko ng isa
iba pang mga variable sa malas

169
00:08:24,020 --> 00:08:27,814
tinatawag na laki na sa una pupuntahan ko
sa magtadhana ay nasimulan sa zero.

170
00:08:27,814 --> 00:08:29,730
Kung may wala sa
stack, laki ay zero,

171
00:08:29,730 --> 00:08:31,420
at ito ay mga halaga ng basura sa mga numero.

172
00:08:31,420 --> 00:08:33,450
Wala akong palagay kung ano ang doon pa lamang.

173
00:08:33,450 --> 00:08:36,059
>> Kaya kung nais kong itulak
isang bagay papunta sa stack,

174
00:08:36,059 --> 00:08:40,780
Ipagpalagay tawag ko ang function push, at
Sinasabi ko itulak 50, tulad ng bilang sa 50,

175
00:08:40,780 --> 00:08:44,090
kung saan nais mong imungkahi
Gumuhit ko ito sa array na ito?

176
00:08:44,090 --> 00:08:47,124
May limang iba't ibang posibleng sagot.

177
00:08:47,124 --> 00:08:48,790
Saan mo gustong upang itulak ang bilang ng 50?

178
00:08:48,790 --> 00:08:51,899
Kung ang layunin dito, muli, tumawag sa
function na push, pumasa sa isang argument

179
00:08:51,899 --> 00:08:52,940
50, kung saan ko ilalagay ito?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
Five possible-- 20% na pagkakataon
ng paghula tama.

182
00:08:59,052 --> 00:08:59,896
Oo?

183
00:08:59,896 --> 00:09:00,740
>> Madla: Far karapatan.

184
00:09:00,740 --> 00:09:01,990
>> Tagapagsalita 1: Far karapatan.

185
00:09:01,990 --> 00:09:08,359
Mayroon na ngayong isang 25% na pagkakataon
ng paghula tama.

186
00:09:08,359 --> 00:09:09,650
Kaya na ay tunay na maging fine.

187
00:09:09,650 --> 00:09:12,770
Sa pamamagitan ng convention, kukunin ko na sabihin na may isang array,
Gusto naming simulan ang pangkalahatan sa kaliwa,

188
00:09:12,770 --> 00:09:14,519
ngunit maaari naming tiyak
simulan sa kanan.

189
00:09:14,519 --> 00:09:17,478
Kaya ang spoiler dito ay Ako
marahil pagpunta sa gumuhit ito sa kaliwa,

190
00:09:17,478 --> 00:09:20,060
gusto lang sa isang normal na array kung saan
Sisimulan ko ang pagpunta sa kaliwa papuntang kanan.

191
00:09:20,060 --> 00:09:21,780
Ngunit kung maaari mong i-flip
ang arithmetic, fine.

192
00:09:21,780 --> 00:09:23,060
Ito lamang ay hindi maginoo.

193
00:09:23,060 --> 00:09:24,880
OK, kailangan kong gumawa ng isa
higit pang mga pagbabago kahit na.

194
00:09:24,880 --> 00:09:27,710
Ngayon na itinulak ako ng isang bagay
papunta sa stack, ano ang susunod?

195
00:09:27,710 --> 00:09:29,400
>> Lahat ng mga karapatan, mayroon akong upang dagdagan ang laki.

196
00:09:29,400 --> 00:09:32,600
Kaya hayaan mo akong magpatuloy at lang
i-update ito, na kung saan ay zero.

197
00:09:32,600 --> 00:09:35,950
At sa halip na ngayon, pupuntahan ko
upang ilagay sa ang halaga ng isa.

198
00:09:35,950 --> 00:09:39,460
At ngayon ipagpalagay itulak ako ng isa pang
number papunta sa stack, tulad ng 51.

199
00:09:39,460 --> 00:09:42,680
Well, kailangan kong gumawa ng isa pa
pagbabago, na kung saan ay hanggang sa ang laki dalawa.

200
00:09:42,680 --> 00:09:46,100
At pagkatapos ay ipagpalagay itulak ako ng isa pa
number papunta sa stack tulad ng 61,

201
00:09:46,100 --> 00:09:52,530
ngayon ay kailangan ko upang i-update ang laki ng isa pa
panahon, at makuha ang halaga ng 3 bilang ang laki.

202
00:09:52,530 --> 00:09:54,690
At ngayon ipagpalagay tawag ko pop.

203
00:09:54,690 --> 00:09:57,250
Ngayon pop, sa pamamagitan ng convention,
ay hindi kumuha ng isang argumento.

204
00:09:57,250 --> 00:10:00,430
Sa pamamagitan ng isang stack, ang buong
punto ng tray talinghaga

205
00:10:00,430 --> 00:10:03,450
ay na hindi mo na kailangang discretion
pumunta makakuha ng na tray, maaari lahat ng gagawin mo

206
00:10:03,450 --> 00:10:06,330
ay pop ang pinakamataas na isa mula sa
stack, dahil lamang.

207
00:10:06,330 --> 00:10:08,010
Iyon ay kung ano ang ibig istraktura ng data.

208
00:10:08,010 --> 00:10:12,250
>> Kaya sa pamamagitan ng na ang logic kung ako
sabihin pop, kung ano ang dumating off?

209
00:10:12,250 --> 00:10:13,080
Kaya 61.

210
00:10:13,080 --> 00:10:15,402
Kaya kung ano ang tunay ay ang computer
pagpunta sa gawin sa memory?

211
00:10:15,402 --> 00:10:16,610
Ano ang kailangang gawin ng aking code?

212
00:10:16,610 --> 00:10:20,330
Ano ang gusto mong ipanukala
palitan namin sa screen?

213
00:10:20,330 --> 00:10:23,410
Ano ang dapat baguhin?

214
00:10:23,410 --> 00:10:24,960
Paumanhin?

215
00:10:24,960 --> 00:10:26,334
Kaya natin mapupuksa ang 61.

216
00:10:26,334 --> 00:10:27,500
Kaya ko talagang gawin iyon.

217
00:10:27,500 --> 00:10:28,640
At maaari ko mapupuksa ang 61.

218
00:10:28,640 --> 00:10:30,980
At pagkatapos ay kung ano ang iba pang mga
kailangang mangyari sa pagbabago?

219
00:10:30,980 --> 00:10:33,160
Size marahil ay may upang bumalik sa dalawang.

220
00:10:33,160 --> 00:10:34,210
At kaya na multa.

221
00:10:34,210 --> 00:10:36,690
Ngunit maghintay ng isang minuto, laki
ilang sandali ang nakalipas ay tatlo.

222
00:10:36,690 --> 00:10:38,240
Gawin ni lamang ng isang mabilis katinuan suriin Hayaan.

223
00:10:38,240 --> 00:10:41,810
Paano nakarating ang alam namin na kami ay
wanted mapupuksa ang 61?

224
00:10:41,810 --> 00:10:42,760
Dahil kami ay pop.

225
00:10:42,760 --> 00:10:46,450
At kaya mayroon akong ito pangalawang size property.

226
00:10:46,450 --> 00:10:48,470
>> Sandali lang, hindi ako
iisip bumalik sa linggo dalawang

227
00:10:48,470 --> 00:10:51,660
kapag sinimulan namin ang pakikipag-usap tungkol
array, kung saan ito ay lokasyon zero,

228
00:10:51,660 --> 00:10:55,920
ito ay lokasyon sa isa, ito ay lokasyon
dalawang, ito ay lokasyon tatlo, apat,

229
00:10:55,920 --> 00:10:58,460
tila ang
relasyon sa pagitan ng laki

230
00:10:58,460 --> 00:11:02,780
at ang mga elemento na gusto kong tanggalin
mula sa mga array ay lilitaw upang maging kung ano lang?

231
00:11:02,780 --> 00:11:05,120
Size minus isa.

232
00:11:05,120 --> 00:11:07,786
At kaya na kung paano bilang tao
Alam namin ang unang 61 ay dumating.

233
00:11:07,786 --> 00:11:09,160
Paano ang pagpunta upang malaman ang mga computer?

234
00:11:09,160 --> 00:11:11,701
Kapag ang iyong code, kung saan ikaw ay malamang na
nais na gawin size minus isa,

235
00:11:11,701 --> 00:11:14,950
kaya tatlong minus isa ay dalawa, at na
ay nangangahulugan na gusto naming mapupuksa 61.

236
00:11:14,950 --> 00:11:18,000
At pagkatapos ay maaari naming katunayan agad
ang laki kaya laki na ngayon

237
00:11:18,000 --> 00:11:20,300
napupunta 3-2 lang.

238
00:11:20,300 --> 00:11:24,520
At upang maging pedantic lang, pupuntahan ko
imungkahi na ako tapos na, i-right?

239
00:11:24,520 --> 00:11:27,660
Iminungkahi mong intuitively
tama ang dapat ko mapupuksa ang 61.

240
00:11:27,660 --> 00:11:30,700
Subalit hindi ako uri ng
uri ng tapat na paraan alisan ng 61?

241
00:11:30,700 --> 00:11:33,790
Epektibo ko nakalimutan
na ito ay aktwal na doon.

242
00:11:33,790 --> 00:11:37,680
At sa tingin bumalik sa PSET4, kung nabasa mo na
mga artikulo tungkol sa forensics, ang PDF

243
00:11:37,680 --> 00:11:40,780
na nagkaroon kami sa iyo guys basahin, o mo
ay basahin sa linggong ito para PSET4.

244
00:11:40,780 --> 00:11:44,300
Alalahanin na ito ay tunay na dyermeyn sa
ang buong ideya ng forensics computer.

245
00:11:44,300 --> 00:11:47,820
Ano pangkalahatan ay isang computer ay
lamang nakalimutan ito kung saan ang isang bagay ay,

246
00:11:47,820 --> 00:11:51,300
ngunit ito ay hindi pumunta sa at tulad ng
subukan upang scratch ito sa labas o override

247
00:11:51,300 --> 00:11:54,560
mga bits na may mga zero at mga
o ilang iba pang mga random na pattern

248
00:11:54,560 --> 00:11:56,690
maliban kung mong gawin ang iyong sarili kaya't kusa.

249
00:11:56,690 --> 00:11:58,930
Kaya ang iyong Swersey ay
karapatan, sabihin mapupuksa 61.

250
00:11:58,930 --> 00:12:00,650
Ngunit sa katotohanan, hindi namin kailangang mag-abala.

251
00:12:00,650 --> 00:12:04,040
Kailangan lang namin na kalimutan na
ito ay doon sa pamamagitan ng pagbabago sa aming laki.

252
00:12:04,040 --> 00:12:05,662
>> Ngayon ay mayroong isang problema sa mga ito stack.

253
00:12:05,662 --> 00:12:07,620
Kung patuloy kong pagtulak ng mga bagay
papunta sa stack, kung ano ang

254
00:12:07,620 --> 00:12:11,167
malinaw naman pagpunta sa mangyayari
sa loob lamang ng ilang oras sandali?

255
00:12:11,167 --> 00:12:12,500
Kami ay pagpunta sa maubusan ng space.

256
00:12:12,500 --> 00:12:13,580
At kung ano ang gagawin namin?

257
00:12:13,580 --> 00:12:14,680
Uri ng Kami ay screwed.

258
00:12:14,680 --> 00:12:19,000
Pagpapatupad na ito ay hindi nagpapahintulot
amin palitan ang laki ng array, dahil ang paggamit ng

259
00:12:19,000 --> 00:12:21,240
ang syntax na ito, kung ikaw
sa tingin bumalik sa dalawang linggo,

260
00:12:21,240 --> 00:12:23,520
kapag nakalikha ka na ipinahayag
ang laki ng isang array,

261
00:12:23,520 --> 00:12:26,780
hindi pa namin kung saan makikita ang isang mekanismo
maaari mong baguhin ang laki ng array.

262
00:12:26,780 --> 00:12:29,020
At sa katunayan C wala na katangian ay.

263
00:12:29,020 --> 00:12:32,524
Kung sinasabi mo bigyan mo ako ng limang
Nths, tumawag sa kanila ng mga numero,

264
00:12:32,524 --> 00:12:33,940
na ang lahat ng iyong pagpunta sa kumuha ito.

265
00:12:33,940 --> 00:12:38,790
Kaya ang ginagawa namin ngayon bilang ng Lunes, mayroon
ang kakayahan upang ipahayag ang isang solusyon

266
00:12:38,790 --> 00:12:42,480
bagaman, kailangan lang namin na mag-tweak
ang kahulugan ng ating stack

267
00:12:42,480 --> 00:12:46,840
upang hindi maging ilang mga hard-code na array,
ngunit upang mag-imbak lamang ng isang address.

268
00:12:46,840 --> 00:12:47,890
>> Ngayon kung bakit ito?

269
00:12:47,890 --> 00:12:51,690
Ngayon lang namin na maging komportable sa
ang katotohanan na kapag tumatakbo ang aking mga programa,

270
00:12:51,690 --> 00:12:53,730
Siguro ako pagpunta sa
kailangang tanungin ang mga tao,

271
00:12:53,730 --> 00:12:55,110
kung gaano karaming mga numero nais mong i-store?

272
00:12:55,110 --> 00:12:56,776
Kaya ang input ay na dumating mula sa isang lugar.

273
00:12:56,776 --> 00:12:59,140
Ngunit sa sandaling alam ko na
numero, pagkatapos ay maaari ko lamang

274
00:12:59,140 --> 00:13:02,470
gamitin kung ano ang gumana upang bigyan
sa akin ng isang tipak ng memory?

275
00:13:02,470 --> 00:13:03,580
Maaari ko bang gamitin ang malloc.

276
00:13:03,580 --> 00:13:06,710
At maaari kong sabihin ang anumang bilang ng mga
bytes gusto kong bumalik para sa mga Nths.

277
00:13:06,710 --> 00:13:10,910
At lahat ng kailangan kong mag-imbak sa mga numero
variable dito sa loob ng struct

278
00:13:10,910 --> 00:13:13,480
dapat na kung ano?

279
00:13:13,480 --> 00:13:18,440
Ano ang tunay na napupunta sa
numero sa sitwasyon na ito?

280
00:13:18,440 --> 00:13:21,300
Oo, isang pointer sa unang
byte ng na tipak ng memory,

281
00:13:21,300 --> 00:13:24,940
o mas partikular, ang mga address
sa mga unang ng mga bytes.

282
00:13:24,940 --> 00:13:27,300
Hindi mahalaga kung ito ay isa
byte o isang bilyong bytes,

283
00:13:27,300 --> 00:13:28,890
Kailangan ko lang pag-aalaga tungkol sa mga unang.

284
00:13:28,890 --> 00:13:31,530
Dahil kung ano ang garantiya malloc at
ang aking mga garantiya operating system,

285
00:13:31,530 --> 00:13:34,170
ay na ang mga tipak ng memorya ko
makakuha ng, ito ay pagpunta sa maging magkalapit.

286
00:13:34,170 --> 00:13:35,378
Mayroong hindi magiging gaps.

287
00:13:35,378 --> 00:13:38,576
Kaya kung ko na hiniling para sa 50
bytes o 1000 bytes,

288
00:13:38,576 --> 00:13:40,450
lahat sila ay magiging
bumalik sa likod sa likod.

289
00:13:40,450 --> 00:13:44,500
At hanggang matandaan ko kung gaano kalaki, kung paano
marami akong tinanong para sa, lahat ng kailangan kong malaman

290
00:13:44,500 --> 00:13:46,230
ay ang unang tulad address.

291
00:13:46,230 --> 00:13:48,660
>> Kaya ngayon kami ay may kakayahan sa code.

292
00:13:48,660 --> 00:13:51,280
Kahit na, ito ay pagpunta sa kumuha sa amin
mas maraming oras upang isulat ito up,

293
00:13:51,280 --> 00:13:55,900
maaaring namin ngayon reallocate na memorya sa pamamagitan ng
pag-iimbak lamang ng ibang address doon

294
00:13:55,900 --> 00:13:59,060
kung gusto namin ng mas malaking o kahit
isang mas maliit na tipak ng memory.

295
00:13:59,060 --> 00:14:00,170
Kaya dito sa isang kalakalan off.

296
00:14:00,170 --> 00:14:01,360
Ngayon makuha namin dynamism.

297
00:14:01,360 --> 00:14:03,350
Mayroon pa kaming
contiguousness ko na pagtubos.

298
00:14:03,350 --> 00:14:05,881
Dahil malloc ay magbibigay sa amin
isang magkadikit na tipak ng memory.

299
00:14:05,881 --> 00:14:08,630
Ngunit ito ay magiging isang sakit sa
leeg para sa amin, ang mga programmer,

300
00:14:08,630 --> 00:14:09,770
sa aktwal na code up.

301
00:14:09,770 --> 00:14:10,730
Ito ay lamang ng mas maraming trabaho.

302
00:14:10,730 --> 00:14:13,930
Kailangan namin ang code na katulad sa kung ano ako ay
banging out lamang ng isang sandali ang nakalipas.

303
00:14:13,930 --> 00:14:16,120
Very maaaring gawin, ngunit ito ay nagdadagdag ng pagiging kumplikado.

304
00:14:16,120 --> 00:14:19,520
At kaya oras na developer, programmer
oras ay isa pang mapagkukunan

305
00:14:19,520 --> 00:14:22,520
na maaaring kailangan naming gastusin
ilang oras upang makakuha ng mga bagong tampok.

306
00:14:22,520 --> 00:14:24,020
At pagkatapos ng kurso doon ay isang queue.

307
00:14:24,020 --> 00:14:26,227
Hindi namin pumunta sa ito
isa sa maraming detalye.

308
00:14:26,227 --> 00:14:27,560
Ngunit ito ay lubos na katulad sa espiritu.

309
00:14:27,560 --> 00:14:31,220
Maaari ko bang ipatupad ang isang pila, at
kanyang kaukulang mga pagpapatakbo,

310
00:14:31,220 --> 00:14:35,660
enqueue o dequeue, tulad ng magdagdag o mag-alis,
ito lamang ay isang may interes paraan ng pagsabi nito,

311
00:14:35,660 --> 00:14:38,100
enqueue o dequeue, tulad ng sumusunod.

312
00:14:38,100 --> 00:14:41,170
Maaari ko lang bigyan ang aking sarili ng isang struct
na muli ay may array ng isang numero, ang

313
00:14:41,170 --> 00:14:44,000
na muli ay may sukat,
ngunit bakit kailangan ko ngayon

314
00:14:44,000 --> 00:14:46,940
upang subaybayan ang mga harap ng isang queue?

315
00:14:46,940 --> 00:14:50,630
Hindi ko kailangang malaman
harap ng aking stack.

316
00:14:50,630 --> 00:14:53,570
Well, kung ako muli para sa isang
queue-- sabihin mahirap lamang

317
00:14:53,570 --> 00:14:57,870
code na ito bilang pagkakaroon ng tulad ng limang
integer in dito potensyal.

318
00:14:57,870 --> 00:15:00,940
Kaya ito ay zero, isa, dalawa, tatlo, apat.

319
00:15:00,940 --> 00:15:03,430
Ito ay magiging
muli tinatawag na numero.

320
00:15:03,430 --> 00:15:06,940
At ito ay tatawaging laki.

321
00:15:06,940 --> 00:15:10,056
>> Bakit hindi sapat
upang magkaroon ng laki lamang?

322
00:15:10,056 --> 00:15:11,680
Well, itulak ni ang mga parehong numero sa ipaalam.

323
00:15:11,680 --> 00:15:14,220
Kaya pushed-- ko enqueued ko, o itinulak.

324
00:15:14,220 --> 00:15:20,150
Ngayon kukunin ko na enqueue 50, at pagkatapos ay
51, at pagkatapos ay 61, at tuldok tuldok tuldok.

325
00:15:20,150 --> 00:15:21,070
Kaya na enqueue.

326
00:15:21,070 --> 00:15:23,176
Enqueued ko 50, pagkatapos 51, pagkatapos ay 61.

327
00:15:23,176 --> 00:15:25,050
At na mukhang magkapareho
sa isang stack kaya sa ngayon,

328
00:15:25,050 --> 00:15:27,190
maliban na kailangan ko upang gumawa ng isang pagbabago.

329
00:15:27,190 --> 00:15:33,680
Kailangan ko upang i-update ang sukat na ito, kaya pumunta ako
mula sa zero sa isa sa 02:58 ngayon.

330
00:15:33,680 --> 00:15:35,760
Paano ko dequeue?

331
00:15:35,760 --> 00:15:36,890
Ano ang mangyayari sa dequeue?

332
00:15:36,890 --> 00:15:41,950
Sino ang dapat dumating off muna ang listahan na ito
kung ito ay ang linya sa Apple Store?

333
00:15:41,950 --> 00:15:42,780
Kaya 50.

334
00:15:42,780 --> 00:15:44,700
Kaya ito ay uri ng trickier oras na ito.

335
00:15:44,700 --> 00:15:47,880
Sapagkat huling oras na ito ay sobrang
madaling gawin lang size minus isa,

336
00:15:47,880 --> 00:15:51,440
Nakukuha ko na ang dulo ng aking array epektibong
kung saan ang mga numero ay, ito ay nagtanggal 61.

337
00:15:51,440 --> 00:15:52,920
Ngunit hindi ko nais na alisin ang 61.

338
00:15:52,920 --> 00:15:55,030
Gusto kong kumuha ng 50, na
ay naroon at 5:00

339
00:15:55,030 --> 00:15:56,790
sa line up para sa
bagong iPhone o watnat.

340
00:15:56,790 --> 00:16:01,200
At kaya mapupuksa 50, ako
hindi maaari lamang gawin ito, i-right?

341
00:16:01,200 --> 00:16:02,547
Maaari ko bang i-cross out 50.

342
00:16:02,547 --> 00:16:04,380
Ngunit sinabi namin namin lamang
Hindi mo na kailangang maging kaya anal

343
00:16:04,380 --> 00:16:06,330
bilang sa scratch out o itago ang data.

344
00:16:06,330 --> 00:16:08,090
Maaari lang namin kalimutan kung saan ito.

345
00:16:08,090 --> 00:16:12,330
>> Ngunit kapag binago ko ang aking mga sukat na ngayon upang
dalawa, ay ito ng sapat na impormasyon

346
00:16:12,330 --> 00:16:15,711
malaman kung ano ang nangyayari sa aking queue?

347
00:16:15,711 --> 00:16:16,680
Hindi naman.

348
00:16:16,680 --> 00:16:19,830
Tulad ng aking mga sukat ay dalawa, ngunit
kung saan magsisimula ang pila,

349
00:16:19,830 --> 00:16:22,980
lalo na kung mayroon pa rin ako
ang mga parehong mga numero sa memorya.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Kaya kailangan kong matandaan
ngayon kung saan ang front ay.

352
00:16:27,090 --> 00:16:29,630
At gayon na gaya ng iminungkahi up
doon, makikita namin lamang na tinatawag na

353
00:16:29,630 --> 00:16:33,729
Nth front, na ang unang
halaga ang dapat ay kung ano?

354
00:16:33,729 --> 00:16:35,270
Zero, isa lamang sa simula ng listahan.

355
00:16:35,270 --> 00:16:40,876
Ngunit ngayon bilang karagdagan sa decrementing
ang laki, dinagdagan pa lang namin sa harap.

356
00:16:40,876 --> 00:16:42,000
Ngayon dito ay isa pang problema.

357
00:16:42,000 --> 00:16:43,030
Kaya minsan ako panatilihin ang pagpunta.

358
00:16:43,030 --> 00:16:47,520
Ipagpalagay na ito ay ang bilang ng mga
tulad ng 121, 124, at pagkatapos, dammit,

359
00:16:47,520 --> 00:16:48,610
Ako sa labas ng space.

360
00:16:48,610 --> 00:16:50,390
Ngunit maghintay ng isang minuto, hindi ako.

361
00:16:50,390 --> 00:16:55,630
Kaya sa puntong ito sa kuwento,
Ipagpalagay na ang sukat ay isa, dalawa,

362
00:16:55,630 --> 00:17:00,370
tatlo, apat, kaya ipagpalagay na ang
laki ay apat, ang harap ay isa,

363
00:17:00,370 --> 00:17:01,621
kaya 51 ay sa harap.

364
00:17:01,621 --> 00:17:04,329
Gusto kong maglagay ng isa pang numero dito,
ngunit, dammit, ako sa labas ng space.

365
00:17:04,329 --> 00:17:06,710
Ngunit hindi talaga ako, di ba?

366
00:17:06,710 --> 00:17:11,192
Saan ko maaaring ilagay ang ilang mga
karagdagang halaga, tulad ng 171?

367
00:17:11,192 --> 00:17:13,400
Oo, maaari ko lamang ang uri ng
bumalik sa banda roon, di ba?

368
00:17:13,400 --> 00:17:18,161
At pagkatapos ay i-cross out ang 50, o
patungan lamang ito sa 171.

369
00:17:18,161 --> 00:17:20,410
At kung ikaw ay nagtataka kung bakit
ang aming mga numero nakuha kaya random,

370
00:17:20,410 --> 00:17:24,150
ang mga ito ay karaniwang kinuha ng computer
science courses sa Harvard pagkatapos CS50.

371
00:17:24,150 --> 00:17:27,510
Ngunit iyon ay isang mahusay na optimization,
dahil ngayon Hindi ko na pag-aaksaya ng espasyo.

372
00:17:27,510 --> 00:17:30,750
Mayroon pa akong upang tandaan
kung paano malaki ang bagay na ito ay total.

373
00:17:30,750 --> 00:17:31,500
Ito ay limang total.

374
00:17:31,500 --> 00:17:33,375
Dahil hindi ko nais na
simulan Sasapawan 51.

375
00:17:33,375 --> 00:17:36,260
Kaya ngayon ako pa rin ang out of space,
kaya ang parehong problema tulad ng dati.

376
00:17:36,260 --> 00:17:39,140
Ngunit maaari mong makita kung paano ngayon
sa iyong code, ikaw ay malamang na

377
00:17:39,140 --> 00:17:41,910
kailangang magsulat ng isang maliit na mas
pagiging kumplikado upang gumawa na mangyari.

378
00:17:41,910 --> 00:17:44,510
At sa katunayan, kung ano ang operator
sa C marahil ay nagbibigay-daan

379
00:17:44,510 --> 00:17:48,110
ikaw ay magically gawin ito ang circularity?

380
00:17:48,110 --> 00:17:50,160
Oo ang modulo operator,
ang tanda porsyento.

381
00:17:50,160 --> 00:17:53,160
Kaya kung ano ang uri ng mga cool tungkol sa isang pila,
kahit na panatilihin namin ang pagguhit ng array

382
00:17:53,160 --> 00:17:56,520
dahil ang mga ito tulad ng tuwid na mga linya, kung ikaw
uri ng isipin ang tungkol sa mga ito pati na curving

383
00:17:56,520 --> 00:18:00,341
sa paligid bilang isang bilog, pagkatapos lamang
intuitively ito uri ng gumagana sa pag-iisip

384
00:18:00,341 --> 00:18:01,590
Tingin ko ang isang maliit na mas malinis.

385
00:18:01,590 --> 00:18:05,190
Gusto mo pa rin na ipatupad
na model ng isip sa mga code.

386
00:18:05,190 --> 00:18:07,550
Kaya hindi na mahirap,
sa huli, upang ipatupad,

387
00:18:07,550 --> 00:18:12,430
ngunit nawala pa rin namin ang size-- sa halip, ang
kakayahan upang baguhin ang laki, maliban kung gagawin namin ito.

388
00:18:12,430 --> 00:18:15,310
>> Mayroon kaming upang makakuha ng alisan ng array, kami
palitan ito ng isang solong pointer,

389
00:18:15,310 --> 00:18:20,010
at pagkatapos ay sa isang lugar sa aking mga code na nakuha ko
isang tawag kung ano gumana sa tunay na lumikha

390
00:18:20,010 --> 00:18:23,720
ang array na tinatawag na numero?

391
00:18:23,720 --> 00:18:26,190
Malloc, o ilang mga katulad
function, eksakto.

392
00:18:26,190 --> 00:18:30,481
Anumang mga katanungan sa mga stack o queue.

393
00:18:30,481 --> 00:18:30,980
Oo?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Magandang tanong.

396
00:18:34,240 --> 00:18:35,830
Ano modulo nais mong gamitin dito.

397
00:18:35,830 --> 00:18:38,520
Kaya sa pangkalahatan, kapag ang paggamit ng
mod, gusto mong gawin ito

398
00:18:38,520 --> 00:18:40,620
sa laki ng
buong istraktura ng data.

399
00:18:40,620 --> 00:18:44,120
Kaya ang isang bagay tulad ng lima o kapasidad, kung
ito ay pare-pareho, ay malamang na kasangkot.

400
00:18:44,120 --> 00:18:47,100
Ngunit ginagawa lamang modulo limang
marahil ay hindi sapat,

401
00:18:47,100 --> 00:18:51,380
dahil kailangan naming malaman ang ginagawa namin
pambalot sa paligid dito o dito o dito.

402
00:18:51,380 --> 00:18:54,160
Kaya ikaw ay malamang din sa iyo
pagpunta sa nais na kasangkot sa

403
00:18:54,160 --> 00:18:57,220
ang laki ng mga bagay, o
sa harap na variable rin.

404
00:18:57,220 --> 00:19:00,140
Kaya lamang ito relatibong
simple arithmetic expression,

405
00:19:00,140 --> 00:19:02,000
ngunit modulo ay ang susi sahog.

406
00:19:02,000 --> 00:19:03,330
>> Kaya short film kung ikaw ay.

407
00:19:03,330 --> 00:19:05,780
Ang isang animation na ang ilang mga
kamag-anak sa ibang unibersidad

408
00:19:05,780 --> 00:19:08,060
magkasama na kami
iniakma para sa talakayang ito.

409
00:19:08,060 --> 00:19:12,630
Ito ay nagsasangkot ng Jack-aaral ang
mga katotohanan tungkol sa queue at stats.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> FILM: Minsan,
nagkaroon ng isang tao na may pangalang Jack.

412
00:19:21,890 --> 00:19:25,330
Kapag dumating ito sa paggawa ng mga kaibigan,
Jack ay hindi magkaroon ng isang pambihirang kakayahan.

413
00:19:25,330 --> 00:19:28,220
Kaya nagpunta Jack na makipag-usap sa mga
pinaka-tanyag na tao na alam niya.

414
00:19:28,220 --> 00:19:30,920
Pumunta siya sa Lou at nagtanong, Ano ang gagawin ko?

415
00:19:30,920 --> 00:19:33,400
Nakita Lou na ang kanyang kaibigan
ay talagang nababalisa.

416
00:19:33,400 --> 00:19:36,050
Well, siya ay magsimula, lamang
tingnan kung paano ka manamit.

417
00:19:36,050 --> 00:19:38,680
Huwag kang magkaroon ng anumang mga damit
may isang iba't ibang mga hitsura?

418
00:19:38,680 --> 00:19:39,660
Oo, sinabi Jack.

419
00:19:39,660 --> 00:19:40,840
Ako ba na gawin.

420
00:19:40,840 --> 00:19:43,320
Halika sa aking bahay at
Kukunin ko ipakita ang mga ito sa iyo.

421
00:19:43,320 --> 00:19:44,550
Kaya sila nagpunta off sa Jack.

422
00:19:44,550 --> 00:19:47,520
At ipinakita Jack Lou ang kahon
kung saan siya nag-iingat sa lahat ng kanyang mga kamiseta,

423
00:19:47,520 --> 00:19:49,260
at ang kanyang pantalon, at ang kaniyang medyas.

424
00:19:49,260 --> 00:19:52,290
Sinabi Lou, nakikita ko ikaw ay may
lahat ng iyong mga damit sa isang pile.

425
00:19:52,290 --> 00:19:54,870
Bakit hindi ka magsuot ng ilang
iba beses sa sandali?

426
00:19:54,870 --> 00:19:58,020
>> Jack sinabi, well, kapag ako
tanggalin ang mga damit at medyas,

427
00:19:58,020 --> 00:20:00,780
Hugasan ko ang mga ito at ilagay
ito ang layo sa kahon.

428
00:20:00,780 --> 00:20:03,210
Pagkatapos ay dumating ang susunod na
umaga, at up ko hop.

429
00:20:03,210 --> 00:20:06,380
Pumunta ako sa kahon at makakuha ng
aking mga damit off sa tuktok.

430
00:20:06,380 --> 00:20:09,070
Lou mabilis na natanto
ang mga problema sa Jack.

431
00:20:09,070 --> 00:20:12,080
Tinupad niya ang mga damit, CD,
at mga libro sa stack.

432
00:20:12,080 --> 00:20:14,420
Kapag siya naabot para
isang bagay na basahin o isuot,

433
00:20:14,420 --> 00:20:17,100
gusto niya piliin ang mga top libro o underwear.

434
00:20:17,100 --> 00:20:19,500
At kapag siya ay tapos na, siya
ay ilagay ito sa kanan likod.

435
00:20:19,500 --> 00:20:21,970
Bumalik ito ay pumunta, sa itaas ng stack.

436
00:20:21,970 --> 00:20:24,460
Alam ko ang solusyon,
Sinabi ng isang matagumpay na malakas.

437
00:20:24,460 --> 00:20:27,090
Kailangan mong malaman upang
simulan ang paggamit ng isang queue.

438
00:20:27,090 --> 00:20:29,870
Kinuha Lou damit Jack at
nag-hang ang mga ito sa maliit na silid.

439
00:20:29,870 --> 00:20:32,710
At kapag siya ay mawawalan ng laman
kahon, siya tossed lamang ito.

440
00:20:32,710 --> 00:20:36,500
>> Pagkatapos ay sinabi niya, ngayon Jack, sa dulo ng
ang araw, ilagay ang iyong mga damit sa kaliwa

441
00:20:36,500 --> 00:20:37,990
kapag ikaw ay ilagay ang mga ito ang layo.

442
00:20:37,990 --> 00:20:41,300
Pagkatapos bukas ng umaga kapag ikaw
makita ang liwanag ng araw, kumuha ng iyong mga damit

443
00:20:41,300 --> 00:20:43,440
sa kanan, mula sa dulo ng linya.

444
00:20:43,440 --> 00:20:44,880
Huwag mong makita? sinabi Lou.

445
00:20:44,880 --> 00:20:46,370
Ito ay kaya maganda.

446
00:20:46,370 --> 00:20:49,770
Makikita magsuot lahat nang isang beses
bago ka magsuot ng isang bagay nang dalawang beses.

447
00:20:49,770 --> 00:20:52,670
At sa lahat ng bagay sa queue
sa kanyang closet at shelf,

448
00:20:52,670 --> 00:20:55,160
Nagsimula Jack sa pakiramdam
lubos na sigurado ng kanyang sarili.

449
00:20:55,160 --> 00:20:59,720
Lahat salamat sa Lou at
ang kanyang mga kahanga-hangang queue.

450
00:20:59,720 --> 00:21:01,220
Tagapagsalita 1: Ang lahat ng mga karapatan, ito ay karapat-dapat sambahin.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Kaya kung ano ay talagang pagpunta
sa ilalim ng hood ngayon?

453
00:21:10,080 --> 00:21:12,370
Na kami ay may mga payo,
na kami malloc,

454
00:21:12,370 --> 00:21:15,680
na kami ay may kakayahan upang lumikha ng
tipak ng memory para sa ating sarili

455
00:21:15,680 --> 00:21:16,344
pabago-bago.

456
00:21:16,344 --> 00:21:18,510
Kaya ito ay isang larawan namin
glimpsed lamang ng ibang mga araw.

457
00:21:18,510 --> 00:21:21,180
Kami ay hindi talagang tumira
sa mga ito, ngunit ang larawang ito

458
00:21:21,180 --> 00:21:24,180
Wala na nangyayari sa ilalim
ng hood para sa linggo ngayon.

459
00:21:24,180 --> 00:21:27,050
At kaya ito ay kumakatawan, makatarungan
isang parihaba na iyong iginuhit namin,

460
00:21:27,050 --> 00:21:28,180
memory ng iyong computer.

461
00:21:28,180 --> 00:21:31,850
At siguro iyong computer, o CS50
ID, may isang gigabyte ng memorya o RAM

462
00:21:31,850 --> 00:21:33,050
o dalawang gigabytes o apat.

463
00:21:33,050 --> 00:21:34,450
Ito ay hindi talagang mahalaga.

464
00:21:34,450 --> 00:21:37,240
Ang iyong operating system
Windows o Mac OS o Linux,

465
00:21:37,240 --> 00:21:41,120
mahalagang nagpapahintulot sa iyong mga programa
mag-isip na may access dito

466
00:21:41,120 --> 00:21:42,982
sa kabuuan ng
memory ng iyong computer,

467
00:21:42,982 --> 00:21:45,440
kahit na maaari mong patakbuhin ang
maramihang mga programa ng sabay-sabay.

468
00:21:45,440 --> 00:21:46,990
Kaya sa katotohanan, na hindi talaga gumagana.

469
00:21:46,990 --> 00:21:49,448
Ngunit ito ay uri ng isang ilusyon
na ibinibigay sa lahat ng iyong mga programa.

470
00:21:49,448 --> 00:21:53,110
Kaya kung mayroon kang dalawang gig ng RAM, ito
ay kung paano maaaring sa tingin ng mga ito sa computer.

471
00:21:53,110 --> 00:21:57,110
>> Ngayon coincidentally, ang isa sa mga
bagay na ito, isa sa mga segment ng memorya,

472
00:21:57,110 --> 00:21:58,350
ay tinatawag na isang stack.

473
00:21:58,350 --> 00:22:01,680
At sa katunayan anumang oras
kaya sa ngayon sa pamamagitan ng pagsulat ng code

474
00:22:01,680 --> 00:22:05,900
na ikaw ay tinatawag na isang
function, halimbawa main.

475
00:22:05,900 --> 00:22:08,410
Alalahanin na anumang oras na hindi ko na
memory iginuhit computer,

476
00:22:08,410 --> 00:22:10,640
Ako palaging gumuhit ng uri ng
kalahati ng isang parihaba dito

477
00:22:10,640 --> 00:22:12,520
at hindi abala sa pakikipag-usap
tungkol sa kung ano ang nasa itaas.

478
00:22:12,520 --> 00:22:15,980
Dahil kapag main ay tinatawag na, inaangkin ko
na makuha mo ito magtilad ng memory

479
00:22:15,980 --> 00:22:16,970
na napupunta down dito.

480
00:22:16,970 --> 00:22:20,650
At kung main tinatawag na isang function
tulad swap, well mapupunta dito swap.

481
00:22:20,650 --> 00:22:23,720
At ito ay lumiliko out, na ang
kung saan ito ay nagtatapos up.

482
00:22:23,720 --> 00:22:26,277
Sa isang bagay na tinatawag na isang stack
sa loob ng memory ng iyong computer.

483
00:22:26,277 --> 00:22:28,360
At sa katapusan ng araw,
ito ay lamang ng mga address.

484
00:22:28,360 --> 00:22:30,680
Ito ay tulad ng byte zero,
byte isa, byte 2 bilyon.

485
00:22:30,680 --> 00:22:33,130
Pero kung sa tingin mo ang tungkol dito
bilang na ito ng hugis-parihaba object,

486
00:22:33,130 --> 00:22:35,130
lahat ng ginagawa namin sa bawat
time ang tawag namin sa isang function ay

487
00:22:35,130 --> 00:22:37,180
layering isang bagong slice ng memory.

488
00:22:37,180 --> 00:22:41,700
Kami ay nagbibigay sa mga function na ang isang slice
ng kanyang sariling memory upang gumana sa.

489
00:22:41,700 --> 00:22:44,490
>> At isipin na ngayon na ito ay mahalaga.

490
00:22:44,490 --> 00:22:46,400
Dahil kung mayroon tayo
isang bagay tulad ng swap

491
00:22:46,400 --> 00:22:51,610
at dalawang lokal na mga variable tulad ng A at B at
palitan namin ang mga halaga mula sa isa at dalawa

492
00:22:51,610 --> 00:22:55,130
sa dalawang at isa, pagpapabalik
na kapag swap nagbabalik,

493
00:22:55,130 --> 00:22:58,330
ito ay parang ito slice
ng memory ay wala na lang.

494
00:22:58,330 --> 00:23:00,080
Sa katotohanan, ito ay pa rin
may forensically.

495
00:23:00,080 --> 00:23:01,940
At ang isang bagay ay talagang pa rin doon.

496
00:23:01,940 --> 00:23:05,410
Ngunit conceptually, ito ay bilang
kahit na ito ay ganap na nawala.

497
00:23:05,410 --> 00:23:10,910
At kaya main ay hindi alam ang alinman sa mga trabaho
na gawa sa na swap function,

498
00:23:10,910 --> 00:23:14,890
maliban na lamang kung talagang ito ay lumampas na sa mga
argumento sa pamamagitan ng pointer o sa pamamagitan ng reference.

499
00:23:14,890 --> 00:23:17,790
Ngayon, ang pangunahing solusyon
sa na problema sa swap

500
00:23:17,790 --> 00:23:19,970
ay paglipas ng mga bagay sa pamamagitan ng address.

501
00:23:19,970 --> 00:23:23,250
Ngunit ito ay lumiliko out, masyadong, kung ano ang
na-pagpunta sa itaas na bahagi

502
00:23:23,250 --> 00:23:26,330
ng rektanggulo ang lahat ng oras na ito ay
pa mayroon pa memory up doon.

503
00:23:26,330 --> 00:23:28,790
At kapag ikaw magilas
magtalaga ng memory,

504
00:23:28,790 --> 00:23:32,020
maging ito man ay sa loob ng GetString, na
kami ay ginagawa para sa iyo sa CS50

505
00:23:32,020 --> 00:23:34,710
library, o kung ikaw guys
tumawag malloc at hilingin

506
00:23:34,710 --> 00:23:37,950
mga operating system para sa isang tipak ng
memory, ito ay hindi dumating mula sa stack.

507
00:23:37,950 --> 00:23:40,960
Nagmumula ito mula sa ibang lugar
sa memory ng iyong computer

508
00:23:40,960 --> 00:23:42,220
na tinatawag ang magbunton.

509
00:23:42,220 --> 00:23:43,430
At iyan ay hindi anumang naiiba.

510
00:23:43,430 --> 00:23:44,285
Ito ay ang parehong RAM.

511
00:23:44,285 --> 00:23:45,160
Ito ay ang parehong memory.

512
00:23:45,160 --> 00:23:49,080
Ito lang ang RAM na ang bahala
doon sa halip ng pababa dito.

513
00:23:49,080 --> 00:23:50,750
>> At kaya kung ano ang ibig sabihin nito?

514
00:23:50,750 --> 00:23:53,650
Well, kung ang iyong computer ay may
takda na halaga ng memory

515
00:23:53,650 --> 00:23:57,450
at ang stack ay lumalaking up, kaya
magsalita, at magbunton, ayon

516
00:23:57,450 --> 00:23:59,349
sa arrow, ay lumalaking pababa.

517
00:23:59,349 --> 00:24:01,140
Sa ibang salita, ang bawat
oras na tawagan ka malloc,

518
00:24:01,140 --> 00:24:03,430
na kayo ay bibigyan ng isang slice
ng memorya mula sa itaas,

519
00:24:03,430 --> 00:24:06,630
pagkatapos ay marahil isang maliit na mas mababa, at pagkatapos ng isang maliit na
mas mababa, sa bawat oras na ikaw ay tumawag malloc,

520
00:24:06,630 --> 00:24:10,100
magbunton, ito ay ang paggamit,
ay uri ng lumalagong,

521
00:24:10,100 --> 00:24:11,950
lumalaking mas malapit at mas malapit sa kung ano?

522
00:24:11,950 --> 00:24:13,382
Ang stack.

523
00:24:13,382 --> 00:24:14,840
Kaya ito ay tila tulad ng isang magandang ideya?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
Ibig kong sabihin, kung saan ito ay hindi talagang malinaw
ano pa ang maaari mong gawin kung ikaw lamang

526
00:24:22,140 --> 00:24:23,910
magkaroon ng isang tiyak na halaga ng memory.

527
00:24:23,910 --> 00:24:25,200
Ngunit ito ay tiyak na masama.

528
00:24:25,200 --> 00:24:27,920
Mga dalawang arrow ay nasa isang
course crash sa isa't isa.

529
00:24:27,920 --> 00:24:31,930
>> At ito ay lumiliko out na ang masamang tao, kamag-anak na
ay partikular na mahusay sa programming,

530
00:24:31,930 --> 00:24:36,140
at sinusubukan mong tadtarin sa mga computer,
maaaring kasangkapanin ito katotohanan.

531
00:24:36,140 --> 00:24:38,290
Sa katunayan, isaalang-alang ng ipaalam
isang maliit na snippet.

532
00:24:38,290 --> 00:24:41,350
Kaya ito ay isang halimbawa maaari mong basahin ang
tungkol sa mas maraming detalye sa Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Susubukan naming ituro sa iyo sa
artikulo kung curious.

534
00:24:43,100 --> 00:24:45,650
Subalit mayroong isang pag-atake sa pangkalahatan
kilala bilang buffer overflow na

535
00:24:45,650 --> 00:24:49,570
ay umiiral para sa hangga't ang tao
ay nagkaroon ng kakayahan upang mamanipula

536
00:24:49,570 --> 00:24:53,120
memory computer, lalo na sa C.
Kaya ito ay isang napaka-arbitrary na programa,

537
00:24:53,120 --> 00:24:55,130
ngunit sabihin basahin ang mga ito mula sa ilalim up.

538
00:24:55,130 --> 00:24:57,650
Main sa argc char star argv.

539
00:24:57,650 --> 00:24:59,830
Kaya ito ay isang programa na tumatagal
command line argumento.

540
00:24:59,830 --> 00:25:03,620
At ang lahat ng mga pangunahing ay tila ay call
isang function, tumawag ito F para sa simple.

541
00:25:03,620 --> 00:25:04,610
At ito ay ipinapasa sa kung ano?

542
00:25:04,610 --> 00:25:05,490
Argv ng isa.

543
00:25:05,490 --> 00:25:09,320
Kaya ito ay ipinapasa sa F anuman
ang salita ay na nag-type ang user

544
00:25:09,320 --> 00:25:11,500
sa prompt pagkatapos ng
pangalan ng programa sa lahat.

545
00:25:11,500 --> 00:25:15,730
Kaya marami tulad ng Caesar o Vigenere, na
maaari mong isipin ang ginagawa sa argv.

546
00:25:15,730 --> 00:25:16,680
>> Kaya kung ano ang F?

547
00:25:16,680 --> 00:25:19,760
F tumatagal sa isang string
bilang sarili nitong argument,

548
00:25:19,760 --> 00:25:22,100
AKA isang char star, parehong
bagay, bilang isang string.

549
00:25:22,100 --> 00:25:24,920
At ito ay tinatawag na nagkataon
bar sa halimbawang ito.

550
00:25:24,920 --> 00:25:27,710
At pagkatapos char c 12,
lamang sa mga tuntunin ng karaniwang tao,

551
00:25:27,710 --> 00:25:31,750
ano ang char c bracket 12 ginagawa para sa atin?

552
00:25:31,750 --> 00:25:33,440
Ano ang gagawin?

553
00:25:33,440 --> 00:25:36,490
Paglaan memory, partikular
12 bytes para sa 12 na karakter.

554
00:25:36,490 --> 00:25:36,990
Mismong.

555
00:25:36,990 --> 00:25:40,000
At pagkatapos ay ang huling linya, pukawin at
kopya, marahil mo na hindi nakita.

556
00:25:40,000 --> 00:25:43,360
Ito ay isang string ng kopya
function na ang layunin sa buhay

557
00:25:43,360 --> 00:25:48,160
ay upang kopyahin ang kanyang ikalawang argument
sa kanyang unang argument,

558
00:25:48,160 --> 00:25:51,190
ngunit lamang hanggang sa isang
tiyak na bilang ng bytes.

559
00:25:51,190 --> 00:25:53,860
Ganito ang sabi ng ikatlong argument,
kung ilang bytes dapat kopyahin mo?

560
00:25:53,860 --> 00:25:56,720
Ang haba ng bar,
ano man ang user na nai-type in.

561
00:25:56,720 --> 00:25:59,320
At ang mga nilalaman ng
bar, na string, ay

562
00:25:59,320 --> 00:26:02,330
kinopya sa memory nakatutok sa sa C.

563
00:26:02,330 --> 00:26:04,060
>> Kaya ito ay tila uri ng hangal, at ito ay.

564
00:26:04,060 --> 00:26:06,300
Ito ay isang contrived halimbawa,
ngunit ito ay kinatawan

565
00:26:06,300 --> 00:26:10,100
ng isang klase ng pag-atake vectors,
isang paraan ng umaatake ang isang programa.

566
00:26:10,100 --> 00:26:15,050
Lahat ay multa at mabuti kung ang user
mga uri sa isang salita na 11 character

567
00:26:15,050 --> 00:26:18,040
o mas kaunti, kasama ang backslash zero.

568
00:26:18,040 --> 00:26:22,830
Paano kung ang uri ng user sa higit sa
11 o 12 o 20 o 50 mga character?

569
00:26:22,830 --> 00:26:25,090
Ano ang programang ito ng pagpunta sa gawin?

570
00:26:25,090 --> 00:26:29,360
Potensyal seg fault. Ito ay pagpunta
nang walang taros kopyahin ang lahat sa bar up

571
00:26:29,360 --> 00:26:31,750
sa haba nito, na kung saan ay
literal lahat ng bagay sa bar,

572
00:26:31,750 --> 00:26:36,307
sa address itinuturo sa C. Ngunit C
ay may lamang preemptively ibinigay bilang 12 bytes.

573
00:26:36,307 --> 00:26:37,640
Ngunit walang karagdagang check.

574
00:26:37,640 --> 00:26:38,700
Walang kung kondisyon.

575
00:26:38,700 --> 00:26:40,580
Walang error checking dito.

576
00:26:40,580 --> 00:26:43,270
>> At kaya kung ano ang program na ito ay
pagpunta sa gawin ay lamang taros

577
00:26:43,270 --> 00:26:45,750
kopyahin ang isang bagay sa iba.

578
00:26:45,750 --> 00:26:47,880
At kaya kung gumuhit namin ito
bilang isang larawan, ito ang

579
00:26:47,880 --> 00:26:49,860
lamang ng isang salubsob ng puwang sa memorya.

580
00:26:49,860 --> 00:26:53,470
Kaya paunawa sa ibaba, kami ay
Mayroon ang mga lokal na variable bar.

581
00:26:53,470 --> 00:26:57,330
Kaya na pointer na pupuntahan store--
sa halip na ang mga lokal argument na

582
00:26:57,330 --> 00:26:58,672
pagpunta sa mga tindahan ang string bar.

583
00:26:58,672 --> 00:27:00,380
At pagkatapos lamang na abiso
sa itaas nito sa isang stack,

584
00:27:00,380 --> 00:27:02,505
dahil sa tuwing hihilingin sa iyo
para sa memory sa stack,

585
00:27:02,505 --> 00:27:04,310
ito ay pumunta sa isang maliit na piraso
sa itaas nito pictorially,

586
00:27:04,310 --> 00:27:06,270
paunawa na nakuha namin ang 12 bytes doon.

587
00:27:06,270 --> 00:27:10,690
Ang tuktok ng isa sa kaliwa ay C bracket zero at
ang tama ilalim ay C bracket 11.

588
00:27:10,690 --> 00:27:12,870
Iyan na lamang kung paano ang mga computer
pagpunta sa maglatag na ito.

589
00:27:12,870 --> 00:27:18,300
Kaya intuitively lang, kung bar ay may higit
sa 12 mga character sa kabuuan, kabilang

590
00:27:18,300 --> 00:27:25,790
ang backslash zero, kung saan ay ang
12 o ang C bracket 12 pagpunta sa pumunta?

591
00:27:25,790 --> 00:27:28,440
O sa halip na kung saan ay ang ika-12
karakter o ang ika-13 na character,

592
00:27:28,440 --> 00:27:30,900
bahagi ng isang daan karakter pagpunta
sa dulo hanggang sa larawan?

593
00:27:30,900 --> 00:27:33,400
Sa itaas o sa ibaba?

594
00:27:33,400 --> 00:27:36,300
>> Right, dahil kahit na
stack mismo lumalaki paitaas,

595
00:27:36,300 --> 00:27:39,590
kapag nakalikha ka na maglagay ng mga bagay-bagay sa
ito, ito para sa mga dahilan na disenyo,

596
00:27:39,590 --> 00:27:41,294
inilalagay ang memorya mula sa itaas hanggang sa ibaba.

597
00:27:41,294 --> 00:27:44,460
Kaya kung mayroon ka ng higit sa 12 bytes,
ikaw ay pagpunta sa simulan upang patungan bar.

598
00:27:44,460 --> 00:27:47,280
Ngayon na ang isang bug, ngunit ito ay
hindi talagang isang malaking pakikitungo.

599
00:27:47,280 --> 00:27:51,130
Ngunit ito ay isang malaking pakikitungo, dahil mayroong
higit pang mga bagay-bagay na nangyayari sa memory.

600
00:27:51,130 --> 00:27:53,074
Kaya narito ang kung paano namin maaaring
ilagay hello, upang maging malinaw.

601
00:27:53,074 --> 00:27:54,490
Kung nai-type ko sa halo sa prompt.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O backslash zero, nagtatapos up sa loob ng
mga 12 bytes, at nagpapaumanhin kami super safe.

603
00:27:59,330 --> 00:28:00,330
Ang lahat ay mabuti.

604
00:28:00,330 --> 00:28:03,020
Ngunit kung nagta-type ako ng isang bagay
mas matagal, potensyal na ito ay

605
00:28:03,020 --> 00:28:05,860
pagpunta sa kilabot sa bar space.

606
00:28:05,860 --> 00:28:08,405
Ngunit mas masahol pa, ito ay lumiliko
out ang lahat ng oras na ito,

607
00:28:08,405 --> 00:28:11,530
kahit na hindi namin na-usapan ang tungkol sa
ito, ang mga stack ay ginagamit para sa iba pang mga bagay-bagay.

608
00:28:11,530 --> 00:28:13,560
Ito ay hindi lokal na mga variable lamang.

609
00:28:13,560 --> 00:28:15,100
>> C ay isang mababang antas ng wika.

610
00:28:15,100 --> 00:28:17,810
At ito ang uri ng mga lihim
ay gumagamit ng mga stack din

611
00:28:17,810 --> 00:28:21,260
tandaan na kapag ang isang
function ay tinatawag na, kung ano

612
00:28:21,260 --> 00:28:26,040
ang address ay sa mga nakaraang pag-andar,
kaya ito ay maaaring lumipat pabalik sa na function.

613
00:28:26,040 --> 00:28:29,980
Kaya kapag magpalit pangunahing mga tawag, kabilang
ang mga bagay na itinulak papunta sa stack

614
00:28:29,980 --> 00:28:34,380
ay hindi lamang swaps lokal na variable,
o mga argument nito, lihim din itinulak

615
00:28:34,380 --> 00:28:37,510
papunta sa stack na kinakatawan
sa pamamagitan ng pulang slice dito,

616
00:28:37,510 --> 00:28:40,520
ay ang address ng main pisikal
sa memory ng iyong computer,

617
00:28:40,520 --> 00:28:44,180
upang kapag swap ay tapos na, ang computer
alam na kailangan ko upang bumalik sa pangunahing

618
00:28:44,180 --> 00:28:46,760
at tapusin Isinasagawa ang pangunahing pag-andar.

619
00:28:46,760 --> 00:28:51,960
Kaya ito ay mapanganib na ngayon, dahil kung
uri ng user sa well higit hello,

620
00:28:51,960 --> 00:28:57,030
tulad na input ng user clobbers
o overwrites na red na seksyon,

621
00:28:57,030 --> 00:28:59,820
lohikal na kung ang computer
lamang ang pagpunta sa walang taros ipalagay

622
00:28:59,820 --> 00:29:03,830
na ang bytes sa na red slice ay
ang address kung saan dapat itong bumalik,

623
00:29:03,830 --> 00:29:09,020
paano kung ang kalaban ay smart sapat o
mapalad sapat na upang ilagay ang isang pagkakasunod-sunod ng mga byte

624
00:29:09,020 --> 00:29:13,450
diyan na ganito ang hitsura ng isang address,
ngunit ito ay ang address ng code

625
00:29:13,450 --> 00:29:18,730
na siya ay nais ang computer
upang maipatupad sa halip ng main?

626
00:29:18,730 --> 00:29:21,670
>> Sa ibang salita, kung ano ang
user ay nagta-type sa prompt,

627
00:29:21,670 --> 00:29:23,850
ay hindi lamang isang bagay
hindi nakasasama tulad ng hello,

628
00:29:23,850 --> 00:29:28,210
ngunit ito ay aktwal na code na katumbas
upang tanggalin ang lahat ng mga file ng user na ito?

629
00:29:28,210 --> 00:29:30,060
O mag-email ng kanilang mga password sa akin?

630
00:29:30,060 --> 00:29:31,940
O simulan ang pag-log sa kanilang mga
keystroke, di ba?

631
00:29:31,940 --> 00:29:34,920
May ay isang paraan, magtadhana sa ngayon hayaan,
na maaaring sila ay nagta-type sa Hindi lang kumusta

632
00:29:34,920 --> 00:29:36,711
mundo o sa kanilang mga pangalan,
maaaring ito ay mahalagang

633
00:29:36,711 --> 00:29:39,570
pumasa sa code, zero at
sa buhay, na ang computer

634
00:29:39,570 --> 00:29:43,450
pagkakamali para sa parehong code at isang address.

635
00:29:43,450 --> 00:29:48,950
Kaya kahit na medyo abstractly, kung ang
mga uri ng user sa sapat adversarial code

636
00:29:48,950 --> 00:29:52,330
na kami ng tuntuning panlahat dito bilang
A. A ay atake o kaaway.

637
00:29:52,330 --> 00:29:53,140
Kaya lang masamang bagay-bagay.

638
00:29:53,140 --> 00:29:55,306
Hindi namin pakialam tungkol sa
numero o ang zero o iyan

639
00:29:55,306 --> 00:29:59,470
ngayon, tulad na ang katapusan mo up
Sasapawan nito na red na seksyon,

640
00:29:59,470 --> 00:30:01,580
mapapansin na ang pagkakasunod-sunod ng bytes.

641
00:30:01,580 --> 00:30:05,020
O 835 C zero eight zero.

642
00:30:05,020 --> 00:30:08,960
At ngayon habang artikulo ng Wikipedia dito
ay iminungkahi, kung ikaw ay tunay na ngayong simulan

643
00:30:08,960 --> 00:30:12,460
label ang mga bytes sa computer ang iyong
memory, ano ang mga artikulo sa Wikipedia ay

644
00:30:12,460 --> 00:30:19,060
minumungkahi ay na, kung ano kung ang address
ng na kaliwang tuktok byte ay 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Sa ibang salita, kung ang masamang tao ay
matalino na sapat sa kanyang code

646
00:30:22,200 --> 00:30:26,650
upang aktwal na ilagay ang isang numero dito na
tumutugon sa address ng code

647
00:30:26,650 --> 00:30:29,180
siya iturok
sa mga computer, mo

648
00:30:29,180 --> 00:30:31,050
maaari lansihin ang computer
sa paggawa ng anumang bagay.

649
00:30:31,050 --> 00:30:34,140
Inaalis ang mga file, pag-email
mga bagay-bagay, sniffing ang iyong trapiko,

650
00:30:34,140 --> 00:30:36,710
literal anumang bagay ang maaaring maging
iturok sa computer.

651
00:30:36,710 --> 00:30:39,220
At sa gayon ang isang buffer overflow
pag-atake sa kanyang kaibuturan

652
00:30:39,220 --> 00:30:43,530
ay lamang ng isang hangal, tangang
pinakamahalaga ng isang array na

653
00:30:43,530 --> 00:30:45,840
ay hindi magkaroon ng naka-check na mga hangganan nito.

654
00:30:45,840 --> 00:30:48,850
At ito ay kung ano ay sobrang mapanganib
at sabay na sobrang malakas

655
00:30:48,850 --> 00:30:52,560
sa C ay na sa katunayan tayong
pag-access sa kahit saan sa memory.

656
00:30:52,560 --> 00:30:55,320
Ito ay nasa sa amin, ang mga programmers,
na magsulat ng mga orihinal na code

657
00:30:55,320 --> 00:30:59,330
upang suriin ang haba darn ng anumang
array na kami ay pagmamanipula.

658
00:30:59,330 --> 00:31:00,750
Kaya upang maging malinaw, ano ang ayusin?

659
00:31:00,750 --> 00:31:03,190
Kung roll kami pabalik sa ito
code, hindi ko dapat lamang

660
00:31:03,190 --> 00:31:08,000
baguhin ang haba ng bar, kung ano
pa ang dapat kong ma-check?

661
00:31:08,000 --> 00:31:10,620
Ano pa ang dapat kong gawin upang
maiwasan ang atake na ito ganap?

662
00:31:10,620 --> 00:31:14,110
Hindi ko gusto na walang taros lamang sabihin
na dapat mong kopyahin ng maraming bytes

663
00:31:14,110 --> 00:31:16,140
bilang ay ang haba ng bar.

664
00:31:16,140 --> 00:31:18,910
Gusto kong sabihin, kopyahin bilang
maraming byte bilang ay sa bar

665
00:31:18,910 --> 00:31:24,090
hanggang sa ang inilalaan
memory, o 12 maximally.

666
00:31:24,090 --> 00:31:27,450
Kaya kailangan ko ng ilang mga uri ng kung kondisyon
na ginagawa ng check ang haba ng bar,

667
00:31:27,450 --> 00:31:32,800
ngunit kung ito ay lumampas sa 12, lamang mahirap naming code
12 bilang ang pinakamataas na posibleng distance.

668
00:31:32,800 --> 00:31:35,910
Kung hindi man ang tinatawag na buffer
overflow atake ay maaaring mangyari.

669
00:31:35,910 --> 00:31:38,451
Sa ibaba ng mga slide,
kung gusto mong malaman upang basahin ang nalalaman

670
00:31:38,451 --> 00:31:41,200
ay ang aktwal na orihinal na artikulo
kung gusto mo na tingnan.

671
00:31:41,200 --> 00:31:44,550
>> Ngunit ngayon, sa gitna ng mga presyo
binayaran dito ay inefficiencies.

672
00:31:44,550 --> 00:31:46,680
Kaya na ay isang mabilis
mababang pagtingin antas kung ano

673
00:31:46,680 --> 00:31:49,709
problema ay maaaring lumitaw ngayon na kami
may access sa memory computer.

674
00:31:49,709 --> 00:31:51,750
Ngunit ang isa pang problema namin
na stumbled sa Lunes

675
00:31:51,750 --> 00:31:53,800
ay isa lamang ang kawalan ng kaalaman
ng isang naka-link na listahan.

676
00:31:53,800 --> 00:31:56,019
Kami ay pabalik sa haba ng panahon.

677
00:31:56,019 --> 00:31:57,560
Hindi na kami ay may isang magkadikit na array.

678
00:31:57,560 --> 00:31:58,980
Wala kaming random access.

679
00:31:58,980 --> 00:32:00,710
Hindi namin maaaring gamitin ang square bracket pagtatanda.

680
00:32:00,710 --> 00:32:04,590
Kami literal na kailangang gumamit ng isang habang loop
tulad ng isa na sinulat ko ng ilang sandali ang nakalipas.

681
00:32:04,590 --> 00:32:09,740
Ngunit sa Lunes, inaangkin namin na makakaya namin
gumapang pabalik sa kaharian ng kahusayan

682
00:32:09,740 --> 00:32:13,040
pagkamit ng isang bagay na
logarithmic siguro, o pinakamahusay pa,

683
00:32:13,040 --> 00:32:16,120
marahil kahit na isang bagay na
tinatawag na pare-pareho ang panahon.

684
00:32:16,120 --> 00:32:19,840
Kaya kung paano namin gawin iyon sa pamamagitan ng paggamit ng mga bagong
mga kasangkapan, mga address, mga payo,

685
00:32:19,840 --> 00:32:22,210
at threading bagay sa aming mga sarili?

686
00:32:22,210 --> 00:32:23,960
Well, ipagpalagay na
dito, ang mga ito ay isang bungkos

687
00:32:23,960 --> 00:32:27,170
ng mga numero na nais naming mag-imbak sa isang
istraktura ng data at mga search mahusay.

688
00:32:27,170 --> 00:32:30,960
Maaari ganap namin rewind upang week
dalawang, itapon ang mga ito sa isang array,

689
00:32:30,960 --> 00:32:33,150
at hanapin ang mga ito gamit ang binary paghahanap.

690
00:32:33,150 --> 00:32:34,040
Hatiin at mapaglabanan.

691
00:32:34,040 --> 00:32:37,720
At sa katunayan ang iyong sinulat
binary paghahanap sa PSET3,

692
00:32:37,720 --> 00:32:40,100
kung saan mo ipatupad ang programa find.

693
00:32:40,100 --> 00:32:40,890
Pero alam mo kung ano.

694
00:32:40,890 --> 00:32:45,060
Mayroong uri ng isang mas
matalino na paraan ng paggawa nito.

695
00:32:45,060 --> 00:32:47,390
Ito ay isang maliit na mas
sopistikadong at ito marahil

696
00:32:47,390 --> 00:32:50,830
ay nagbibigay-daan sa amin upang makita kung bakit binary
search ay kaya mas mabilis.

697
00:32:50,830 --> 00:32:52,980
Una, sabihin ipakilala ipaalam
ang paniwala ng isang puno.

698
00:32:52,980 --> 00:32:54,730
Aling kahit na sa
katotohanan puno uri ng

699
00:32:54,730 --> 00:32:57,730
lumaki na tulad nito, sa mundo ng mga computer
agham uri ng lumalaki sila pababa

700
00:32:57,730 --> 00:33:00,830
tulad ng isang pamilya tree, kung saan mayroon kang
ang iyong mga lolo at lola o dakilang grandparents

701
00:33:00,830 --> 00:33:04,580
o watnat sa tuktok, ang apo at
ang matriarch ng pamilya, isa lang

702
00:33:04,580 --> 00:33:07,930
tinatawag na root, node, sa ibaba
na kung saan ay ang kanyang mga anak,

703
00:33:07,930 --> 00:33:11,442
ibaba kung saan ay ang kanyang mga anak, o
kaapu-apuhan nito sa mas pangkalahatang.

704
00:33:11,442 --> 00:33:13,400
At sinuman sa pader off
sa ibaba ng pamilya

705
00:33:13,400 --> 00:33:16,070
tree, bukod sa pagiging
bunsong sa pamilya,

706
00:33:16,070 --> 00:33:19,520
ay maaari ding maging generically lamang
tinatawag na ang mga dahon ng punong kahoy.

707
00:33:19,520 --> 00:33:21,800
>> Kaya ito ay isang bungkos lamang
ng mga salita at mga kahulugan

708
00:33:21,800 --> 00:33:25,790
para sa isang bagay na tinatawag na isang puno sa computer
science, marami tulad ng isang family tree.

709
00:33:25,790 --> 00:33:28,770
Ngunit mayroong mga may interes anyo
ng mga puno, isa rito

710
00:33:28,770 --> 00:33:30,780
ay tinatawag na isang binary puno ng paghahanap.

711
00:33:30,780 --> 00:33:34,380
At maaari mong uri ng mang-ulol
bukod sa kung ano ang ginagawa ang bagay na ito.

712
00:33:34,380 --> 00:33:37,180
Well, ito ay binary sa kung ano ang kahulugan?

713
00:33:37,180 --> 00:33:41,455
Saan nanggagaling ang binary mula dito?

714
00:33:41,455 --> 00:33:41,955
Paumanhin?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
Ito ay hindi kaya magkano ang isang mag-o.

717
00:33:47,210 --> 00:33:52,000
Ito ay higit pa ang bawat isa sa mga node ay walang
higit sa dalawang mga bata, tulad ng nakikita natin dito.

718
00:33:52,000 --> 00:33:54,990
Sa pangkalahatan, ang isang tree-- at
ang iyong mga magulang at mga lolo at lola

719
00:33:54,990 --> 00:33:57,640
maaaring magkaroon ng maraming mga bata o
Mga Apo pati talagang gusto nila,

720
00:33:57,640 --> 00:34:00,820
at iba halimbawa may kami ay may tatlong
bata off kanang kamay na node,

721
00:34:00,820 --> 00:34:05,480
ngunit sa isang binary puno, isang node ay may
zero, isa, o dalawang bata maximally.

722
00:34:05,480 --> 00:34:08,496
At iyon ay isang magaling na ari-arian,
dahil kung ito ay nilimitahan sa pamamagitan ng dalawang,

723
00:34:08,496 --> 00:34:10,620
kami ay pagpunta sa ma-
makakuha ng isang maliit log base dalawang

724
00:34:10,620 --> 00:34:11,975
action na nangyayari dito sa huli.

725
00:34:11,975 --> 00:34:13,350
Kaya kami ay may isang bagay na logarithmic.

726
00:34:13,350 --> 00:34:14,558
Ngunit higit pa sa na sa isang sandali.

727
00:34:14,558 --> 00:34:19,810
Puno Search ay nangangahulugan na ang mga numero ay
nakaayos tulad na kaliwang anak

728
00:34:19,810 --> 00:34:22,429
halaga ay mas malaki kaysa sa root.

729
00:34:22,429 --> 00:34:26,010
At karapatan ng bata nito ay
mas malaki kaysa sa root.

730
00:34:26,010 --> 00:34:29,290
Sa ibang salita, kung kumuha ka ng alinman sa mga
nodes, ang mga lupon sa larawan na ito,

731
00:34:29,290 --> 00:34:31,840
at tumitingin sa kaliwa nito
anak at kanang bata nito,

732
00:34:31,840 --> 00:34:34,739
ang unang dapat na mas mababa kaysa sa,
dapat na mas malaki kaysa sa pangalawa.

733
00:34:34,739 --> 00:34:36,159
Kaya katinuan check 55.

734
00:34:36,159 --> 00:34:37,780
Ito ay iniwan ang bata ay 33.

735
00:34:37,780 --> 00:34:38,620
Ito ay mas mababa kaysa sa.

736
00:34:38,620 --> 00:34:40,929
55, right anak nito ay 77.

737
00:34:40,929 --> 00:34:41,783
Ito ay mas malaki kaysa sa.

738
00:34:41,783 --> 00:34:43,199
At iyon ay isang recursive kahulugan.

739
00:34:43,199 --> 00:34:46,480
Maaari naming suriin ang bawat isa sa mga iyon
nodes at ang parehong pattern ay hold.

740
00:34:46,480 --> 00:34:49,389
>> Kaya kung ano ang magaling sa isang
binary puno ng paghahanap, ay

741
00:34:49,389 --> 00:34:52,204
na ang isa, maaari naming ipatupad
may isang struct, gusto lamang ito.

742
00:34:52,204 --> 00:34:54,620
At kahit na kami ay ibinabato
maraming mga istraktura sa iyong,

743
00:34:54,620 --> 00:34:56,560
ang mga ito ay medyo
intuitive ngayon sana.

744
00:34:56,560 --> 00:35:00,570
Ang syntax ay arcane para bang pa rin,
ngunit ang mga nilalaman ng isang node sa ito

745
00:35:00,570 --> 00:35:02,786
context-- at panatilihin namin
gamit ang salitang node,

746
00:35:02,786 --> 00:35:04,910
maging ito man ay isang parihaba
sa screen o sa isang bilog,

747
00:35:04,910 --> 00:35:08,970
ito lamang ang ilang mga pangkaraniwang lalagyan,
sa kasong ito ng isang puno, tulad ng isa

748
00:35:08,970 --> 00:35:11,780
Nakita namin, kailangan namin ng isang integer
sa bawat isa sa mga nodes

749
00:35:11,780 --> 00:35:15,460
at pagkatapos ay kailangan ko ng dalawang mga payo na tumuturo
sa kaliwa anak at kanang bata,

750
00:35:15,460 --> 00:35:16,590
ayon sa pagkakabanggit.

751
00:35:16,590 --> 00:35:20,730
Kaya na kung paano namin maaaring
ipatupad na sa isang struct.

752
00:35:20,730 --> 00:35:22,315
At kung paano maaaring ako ipatupad ito sa code?

753
00:35:22,315 --> 00:35:26,730
Well, sabihin kumuha ng isang mabilis
tingnan ang mga ito maliit na maliit na halimbawa.

754
00:35:26,730 --> 00:35:29,820
Ito ay hindi sa pagganap, ngunit hindi ko na
kopyahin at ilagay sa istraktura na.

755
00:35:29,820 --> 00:35:33,510
At kung ang aking pag-andar para sa isang binary
puno ng paghahanap ay tinatawag na paghahanap,

756
00:35:33,510 --> 00:35:36,980
at ito ay tumatagal ng dalawang argumento,
isang integer N at isang pointer

757
00:35:36,980 --> 00:35:41,400
sa isang node, kaya isang pointer sa puno
o isang pointer sa ugat ng isang puno,

758
00:35:41,400 --> 00:35:43,482
paano ko pumunta tungkol sa paghahanap para N?

759
00:35:43,482 --> 00:35:45,440
Well, una, dahil ako
pagharap sa mga payo,

760
00:35:45,440 --> 00:35:46,750
Pupunta ako upang gawin ang isang katinuan check.

761
00:35:46,750 --> 00:35:54,279
Kung puno equals katumbas null, ay N
sa punong kahoy na ito o hindi sa punong kahoy na ito?

762
00:35:54,279 --> 00:35:55,070
Hindi ito maaaring maging, tama?

763
00:35:55,070 --> 00:35:56,870
Kung ako ay nakalipas na null,
may walang may.

764
00:35:56,870 --> 00:35:59,230
Ako maaaring pati na rin lamang
walang taros sabihin bumalik false.

765
00:35:59,230 --> 00:36:04,050
Kung ako magbibigay sa iyo wala, tiyak kong hindi maaari
mahanap ang anumang bilang N. Kaya ano pa ang maaari ko

766
00:36:04,050 --> 00:36:04,750
Tingnan ngayon?

767
00:36:04,750 --> 00:36:12,830
Pupunta ako sa sabihin na rin ng iba pa kung N ay
mas mababa sa kahit na ano ay sa puno ng buko

768
00:36:12,830 --> 00:36:16,300
na ako ng kamay N value.

769
00:36:16,300 --> 00:36:20,270
Sa ibang salita, kung ang bilang ako
hinahanap, N, ay mas mababa kaysa sa node

770
00:36:20,270 --> 00:36:21,340
na Naghahanap ako sa.

771
00:36:21,340 --> 00:36:23,190
At ang mga node Naghahanap ako
sa ay tinatawag na puno,

772
00:36:23,190 --> 00:36:26,370
at pagpapabalik mula sa mga nakaraang mga halimbawa
upang makakuha ng sa halaga sa isang pointer,

773
00:36:26,370 --> 00:36:28,310
Gamitin ko ang arrow pagtatanda.

774
00:36:28,310 --> 00:36:35,960
Kaya kung N ay mas mababa sa puno arrow
N, gusto kong conceptually pumunta kaliwa.

775
00:36:35,960 --> 00:36:38,590
Paano searching ko express kaliwa?

776
00:36:38,590 --> 00:36:41,560
Upang maging malinaw, kung ito ay
ang mga larawan na pinag-uusapan,

777
00:36:41,560 --> 00:36:44,612
at ako ay lumipas na kataas-taasan
palaso na nakaturo pababa.

778
00:36:44,612 --> 00:36:45,570
Iyon ang aking puno pointer.

779
00:36:45,570 --> 00:36:48,060
Ako sa pagturo sa ugat ng puno.

780
00:36:48,060 --> 00:36:52,100
At Naghahanap ako sabihin,
ang bilang 44, nagkataon.

781
00:36:52,100 --> 00:36:55,300
Ay 44 mas mababa sa o
mas malaki kaysa sa 55 malinaw naman?

782
00:36:55,300 --> 00:36:56,360
Kaya ito ay mas mababa kaysa sa.

783
00:36:56,360 --> 00:36:58,760
At kaya ito kung ang condition ay nalalapat.

784
00:36:58,760 --> 00:37:03,981
Kaya conceptually, kung ano ang gusto kong
maghanap susunod kung ako naghahanap para sa 44?

785
00:37:03,981 --> 00:37:04,480
Oo?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Eksakto, gusto kong
maghanap sa kaliwang bata,

788
00:37:11,100 --> 00:37:12,789
o kaliwa sub-puno ng mga larawan na ito.

789
00:37:12,789 --> 00:37:14,830
At sa katunayan, sabihin sa akin sa pamamagitan
ang larawan down dito

790
00:37:14,830 --> 00:37:17,770
para sa sandali lamang, dahil
Hindi ko ma-scratch ito out.

791
00:37:17,770 --> 00:37:21,150
Kung sisimulan ko dito at 55, at
Alam ko na ang halaga ng 44

792
00:37:21,150 --> 00:37:23,180
Naghahanap ako ng ay upang
sa kaliwa, ito ay uri

793
00:37:23,180 --> 00:37:26,010
ng mga tulad ng mapunit ang libro ng telepono sa
kalahati o mapunit ang tree sa kalahati.

794
00:37:26,010 --> 00:37:29,660
Wala na akong pakialam tungkol sa
ang buong kalahati ng mga puno.

795
00:37:29,660 --> 00:37:33,270
At gayon pa man, nang mausisa sa mga tuntunin ng
istraktura, ang bagay na ito sa paglipas dito na

796
00:37:33,270 --> 00:37:36,682
nagsisimula sa 33, na sa kanyang sarili
ay isang binary puno ng paghahanap.

797
00:37:36,682 --> 00:37:39,890
Sinabi ko ang salitang recursive bago dahil
sa katunayan na ito ay isang istraktura ng data na

798
00:37:39,890 --> 00:37:41,707
sa pamamagitan ng kahulugan ay recursive.

799
00:37:41,707 --> 00:37:44,540
Maaari mong magkaroon ng isang puno na ito
malaki, ngunit ang bawat isa sa kanyang mga anak

800
00:37:44,540 --> 00:37:46,870
ay kumakatawan sa isang puno lamang ng isang maliit na mas maliit.

801
00:37:46,870 --> 00:37:50,910
Sa halip na ito sa pagiging lolo
o lola, ngayon ay ang ina lamang

802
00:37:50,910 --> 00:37:54,300
or-- Hindi ko say-- hindi mom
o ama, na magiging kakaiba.

803
00:37:54,300 --> 00:37:59,000
Sa halip na ang dalawang mga bata doon
ay magiging tulad ng kapatid na lalaki at kapatid.

804
00:37:59,000 --> 00:38:01,120
Ang isang bagong henerasyon ng pamilya tree.

805
00:38:01,120 --> 00:38:02,900
Ngunit structurally, ito ay ang parehong mga ideya.

806
00:38:02,900 --> 00:38:06,790
At ito ay lumiliko out mayroon akong isang function
na kung saan maaari ba akong maghanap ng isang binary search

807
00:38:06,790 --> 00:38:07,290
tree.

808
00:38:07,290 --> 00:38:08,680
Ito ay tinatawag na paghahanap.

809
00:38:08,680 --> 00:38:17,870
Ako sa paghahanap para N sa puno arrow kaliwa
iba kung N ay mas malaki sa halaga

810
00:38:17,870 --> 00:38:18,870
na ako ay kasalukuyang sa.

811
00:38:18,870 --> 00:38:20,800
55 sa mga kuwento ng ilang sandali ang nakalipas.

812
00:38:20,800 --> 00:38:23,780
Mayroon akong isang function na tinatawag na
search na maaari ko lamang

813
00:38:23,780 --> 00:38:29,660
ipasa N na ito at recursively maghanap
mga sub-puno at return lamang

814
00:38:29,660 --> 00:38:30,620
kahit na ano na sagot.

815
00:38:30,620 --> 00:38:33,530
Iba Pa Mayroon akong ilang huling base kaso dito.

816
00:38:33,530 --> 00:38:35,310
>> Ano ang huling kaso?

817
00:38:35,310 --> 00:38:36,570
Tree ay alinman null.

818
00:38:36,570 --> 00:38:39,980
Ang halaga ng alinman Naghahanap ako ay
mas mababa kaysa ito o mas mataas kaysa sa na

819
00:38:39,980 --> 00:38:42,610
o katumbas ng mga ito.

820
00:38:42,610 --> 00:38:44,750
At maaari ko bang sabihin pantay
pantay-pantay, ngunit lohikal ito ay

821
00:38:44,750 --> 00:38:46,500
katumbas lang sinasabi ng ibang tao dito.

822
00:38:46,500 --> 00:38:49,150
Kaya totoo ay kung paano mahanap ko ang isang bagay.

823
00:38:49,150 --> 00:38:51,710
Kaya sana ito ay isang
kahit na mas nakakahimok halimbawa

824
00:38:51,710 --> 00:38:54,900
kaysa sa tangang pag-andar na palatandaan
Ginawa namin ang ilang mga aralin sa likod,

825
00:38:54,900 --> 00:38:58,360
kung saan ito ay tulad ng madaling upang gamitin ang isang loop
upang mabilang ang lahat ng mga numero mula sa isang

826
00:38:58,360 --> 00:39:02,390
sa N. Dito sa isang istraktura ng data
na mismo ay recursively

827
00:39:02,390 --> 00:39:07,050
tinukoy at recursively iginuhit, ngayon kami
may kakayahan upang ipahayag ang ating sarili

828
00:39:07,050 --> 00:39:09,780
sa code na mismo ay recursive.

829
00:39:09,780 --> 00:39:12,580
Kaya ito ay ang parehong code dito.

830
00:39:12,580 --> 00:39:14,400
>> Kaya kung ano ang iba pang mga problema na maaari naming malutas?

831
00:39:14,400 --> 00:39:18,160
Kaya isang mabilis na hakbang ang layo mula
puno para sa sandali lamang.

832
00:39:18,160 --> 00:39:20,130
Dito ay, sabihin, ang bandila German.

833
00:39:20,130 --> 00:39:22,020
At mayroong malinaw na ang isang
pattern upang i-flag ito.

834
00:39:22,020 --> 00:39:23,811
At mayroong maraming mga
flags sa mundo na

835
00:39:23,811 --> 00:39:27,560
ay kasing simple ng ito sa mga tuntunin
ng kanilang mga kulay at mga pattern.

836
00:39:27,560 --> 00:39:31,930
Ngunit ipagpalagay na ito ay naka-imbak bilang
.GIF, O isang JPEG, o bitmap, o isang ping,

837
00:39:31,930 --> 00:39:34,240
anumang graphical na format ng file
na kung saan hindi ka pamilyar,

838
00:39:34,240 --> 00:39:36,460
ang ilan ay hindi namin
naglalaro sa mga in PSET4.

839
00:39:36,460 --> 00:39:41,550
Ito ay hindi mukhang kapaki-pakinabang sa mga tindahan ng
black pixel, black pixel, black pixel,

840
00:39:41,550 --> 00:39:44,790
tuldok, tuldok, tuldok, ang maramihang mga
black pixels para sa unang scanline,

841
00:39:44,790 --> 00:39:47,430
o hilera, pagkatapos ng buong bungkos ng
ang parehong, pagkatapos ng buong bungkos

842
00:39:47,430 --> 00:39:49,530
ng parehong, at pagkatapos ay isang
buong bungkos ng pulang pixels,

843
00:39:49,530 --> 00:39:53,020
pulang pixels, red pixels, at pagkatapos ng isang buong
grupo ng mga kulay-dilaw na mga pixel, yellow, di ba?

844
00:39:53,020 --> 00:39:55,050
>> May tulad ng kawalan ng kaalaman dito.

845
00:39:55,050 --> 00:39:59,040
Paano gagawin mo intuitively
compress ang bandila German

846
00:39:59,040 --> 00:40:01,320
kung ang pagpapatupad ng mga ito bilang isang file?

847
00:40:01,320 --> 00:40:04,940
Tulad ng kung anong impormasyon ang maaari naming hindi
abala sa pag-iimbak sa disk upang

848
00:40:04,940 --> 00:40:08,040
upang bawasan ang aming laki ng file mula sa tulad ng
isang megabyte sa isang kilobyte, isang bagay

849
00:40:08,040 --> 00:40:09,430
mas maliit?

850
00:40:09,430 --> 00:40:13,130
Kung saan namamalagi ang kalabisan
para maging malinaw?

851
00:40:13,130 --> 00:40:13,880
Ano ang maaari mong gawin?

852
00:40:13,880 --> 00:40:14,380
Oo?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Mismong.

855
00:40:21,970 --> 00:40:24,550
Bakit hindi sa halip na tandaan
ang kulay ng bawat darn pixel

856
00:40:24,550 --> 00:40:28,200
tulad ng iyong ginagawa sa PSET4
na may format na bitmap file,

857
00:40:28,200 --> 00:40:32,060
bakit hindi kumakatawan ikaw lamang ang
pinakakaliwa haligi ng pixels, halimbawa

858
00:40:32,060 --> 00:40:35,370
ng grupo ng mga black pixels, ng grupo
ng pula, at ng grupo ng yellow,

859
00:40:35,370 --> 00:40:39,210
at pagkatapos lamang sa paanuman encode ang
ideya ng ulitin ito 100 ulit

860
00:40:39,210 --> 00:40:41,020
o ulitin ito 1,000 ulit?

861
00:40:41,020 --> 00:40:43,430
Saan 100 o 1000 ay
lamang ng isang integer, kaya mo

862
00:40:43,430 --> 00:40:47,290
maaaring makakuha ng malayo na may lamang ng isang numero
sa halip ng daan-daan o libu-libo

863
00:40:47,290 --> 00:40:48,270
ng mga karagdagang pixels.

864
00:40:48,270 --> 00:40:50,990
At sa katunayan, na kung paano namin
maaaring i-compress ang bandila German.

865
00:40:50,990 --> 00:40:51,490
At

866
00:40:51,490 --> 00:40:53,470
Ngayon kung ano ang tungkol sa mga Pranses bandila?

867
00:40:53,470 --> 00:40:58,930
At isang maliit na ilang mga uri ng
mental na ehersisyo, na kung saan bandila

868
00:40:58,930 --> 00:41:01,040
maaaring compress more on disk?

869
00:41:01,040 --> 00:41:05,720
Ang German bandila o ang Pranses
flag, kung lubos naming diskarte na?

870
00:41:05,720 --> 00:41:08,490
Ang bandila German, dahil mayroong
mas horizontal kalabisan.

871
00:41:08,490 --> 00:41:12,190
At sa pamamagitan ng disenyo, maraming mga graphical file
format gawin sa katunayan trabaho linya bilang scan

872
00:41:12,190 --> 00:41:12,830
horizontally.

873
00:41:12,830 --> 00:41:14,674
Sila ay maaaring magtrabaho
patayo, lamang ang sangkatauhan

874
00:41:14,674 --> 00:41:17,090
nagpasya taon na nakalipas na bibigyan namin ng
karaniwang tingin ng row bagay

875
00:41:17,090 --> 00:41:18,880
sa pamamagitan ng hilera sa halip ng haligi sa pamamagitan ng column.

876
00:41:18,880 --> 00:41:20,820
Kaya nga kung ikaw ay
upang tingnan ang mga file

877
00:41:20,820 --> 00:41:24,670
laki ng isang German bandila at isang Pranses
flag, kaya hangga't ang resolution ay

878
00:41:24,670 --> 00:41:27,530
ang parehong, ang parehong lapad
at taas, ang isang ito

879
00:41:27,530 --> 00:41:31,580
dito ay magiging mas malaki, dahil ikaw
kailangang ulitin ang iyong sarili ng tatlong beses.

880
00:41:31,580 --> 00:41:35,570
Kailangang tukuyin mo ang blue, ulitin
sa iyong sarili, puti, ulitin ang iyong sarili, pula,

881
00:41:35,570 --> 00:41:36,740
ulitin ang iyong sarili.

882
00:41:36,740 --> 00:41:39,000
Hindi ka maaaring pumunta lamang ang lahat
ang daan sa kanan.

883
00:41:39,000 --> 00:41:41,200
At bilang isang bukod, na gumawa
i-clear ang compression

884
00:41:41,200 --> 00:41:43,910
sa lahat ng dako, kung ang mga ito ay
apat na mga frame mula sa isang video-- mo

885
00:41:43,910 --> 00:41:45,890
maaaring isipin na ang isang pelikula
o video ay karaniwang

886
00:41:45,890 --> 00:41:47,286
tulad ng 29 o 30 mga frame sa bawat segundo.

887
00:41:47,286 --> 00:41:50,410
Ito ay tulad ng isang maliit na tingnan ang mga libro na kung saan kayo
makita lamang ng imahe, larawan, imahe, larawan,

888
00:41:50,410 --> 00:41:54,410
image lang sobrang bilis kaya mukhang
ang mga aktor sa screen ay gumagalaw.

889
00:41:54,410 --> 00:41:57,130
Narito ang isang gumulo pukyutan sa
tuktok ng isang bungkos ng mga bulaklak.

890
00:41:57,130 --> 00:41:59,790
At bagaman maaari itong maging uri ng
mahirap na makita sa unang tingin,

891
00:41:59,790 --> 00:42:04,020
ang tanging bagay na gumagalaw sa
pelikula na ito ay ang pukyutan.

892
00:42:04,020 --> 00:42:06,880
>> Ano ang pipi tungkol sa pag-iimbak
hindi naka-compress video?

893
00:42:06,880 --> 00:42:11,420
Ito ay uri ng isang pag-aaksaya sa mga tindahan ng video
bilang apat na halos magkapareho mga imahe na

894
00:42:11,420 --> 00:42:13,670
naiiba lamang sa abot ng kung saan ang mga laywan ay.

895
00:42:13,670 --> 00:42:16,280
Maaari mong itapon ang pinaka
ng impormasyon na iyon

896
00:42:16,280 --> 00:42:20,190
at tandaan lamang, halimbawa,
ang unang frame at ang huling frame,

897
00:42:20,190 --> 00:42:22,180
key frames kung na sa iyo
kailanman narinig ang mga salita,

898
00:42:22,180 --> 00:42:24,337
at mag-imbak lamang sa
gitna kung saan ang mga laywan ay.

899
00:42:24,337 --> 00:42:26,170
At hindi mo na kailangang
tindahan ng lahat ng mga rosas,

900
00:42:26,170 --> 00:42:28,330
at ang asul, at ang
green halaga pati na rin.

901
00:42:28,330 --> 00:42:31,200
Kaya ito ay upang lamang sabihin na
compression ay lahat ng dako.

902
00:42:31,200 --> 00:42:34,900
Ito ay isang pamamaraan madalas naming gamitin
o mang-ahas na mga araw.

903
00:42:34,900 --> 00:42:38,750
>> Ngunit paano mo compress ang text?

904
00:42:38,750 --> 00:42:40,450
Paano mo pumunta tungkol sa pigain text?

905
00:42:40,450 --> 00:42:45,410
Well, ang bawat isa sa mga character sa
Ascii ay isa byte, o walong bits.

906
00:42:45,410 --> 00:42:47,360
At iyon ay uri ng pipi, di ba?

907
00:42:47,360 --> 00:42:51,160
Dahil malamang type ka A
at E at I at ng O at U ng isang pulutong

908
00:42:51,160 --> 00:42:55,270
mas madalas kaysa sa gusto W o Q o Z,
depende sa wika kung saan

909
00:42:55,270 --> 00:42:56,610
sumusulat ka tiyak.

910
00:42:56,610 --> 00:42:59,600
At kaya bakit kami gamit
walong bits para sa bawat titik,

911
00:42:59,600 --> 00:43:02,040
kabilang ang hindi bababa sa
popular na mga titik, i-right?

912
00:43:02,040 --> 00:43:05,300
Bakit hindi gamitin ang mas kaunting mga bits para
ang sobrang sikat na mga titik,

913
00:43:05,300 --> 00:43:07,760
tulad ng E, ang mga bagay na hulaan mo
una sa gulong ng kapalaran,

914
00:43:07,760 --> 00:43:10,450
at gamitin ang higit pang mga piraso ng
ang mas popular na titik?

915
00:43:10,450 --> 00:43:10,950
Bakit?

916
00:43:10,950 --> 00:43:13,130
Dahil lang kami ng pagpunta sa
gamitin ang mga ito ng mas madalas.

917
00:43:13,130 --> 00:43:15,838
>> Well, ito ay lumiliko out na magkaroon ng
mga pagtatangka na ginawa upang gawin ito.

918
00:43:15,838 --> 00:43:18,630
At kung ang pagpapabalik sa iyo mula sa grade
school o high school, Morse code.

919
00:43:18,630 --> 00:43:20,400
Morse code ay tuldok
at gitling na maaaring maging

920
00:43:20,400 --> 00:43:24,270
ipinapadala kasama ng isang wire bilang
tunog o signal ng ilang mga uri.

921
00:43:24,270 --> 00:43:25,930
Ngunit Morse code ay isang napakabilis malinis.

922
00:43:25,930 --> 00:43:29,010
Ito ay uri ng isang binary system in
na ikaw ay may mga tuldok o gitling.

923
00:43:29,010 --> 00:43:30,977
Ngunit kung makakita ka ng, halimbawa, dalawang tuldok.

924
00:43:30,977 --> 00:43:33,810
O kung sa tingin mo bumalik sa operator
na napupunta tulad beep, beep, beep,

925
00:43:33,810 --> 00:43:36,760
beep, pagpindot ng isang maliit na mag-trigger
na nagpapadala ng isang senyas,

926
00:43:36,760 --> 00:43:40,360
kung ikaw, ang tatanggap, na natatanggap ng dalawang
mga tuldok, kung ano ang mensahe na natanggap mo?

927
00:43:40,360 --> 00:43:43,490
Ganap na arbitrary.

928
00:43:43,490 --> 00:43:44,450
>> I?

929
00:43:44,450 --> 00:43:45,060
I?

930
00:43:45,060 --> 00:43:47,500
O kung ano about-- o ako?

931
00:43:47,500 --> 00:43:49,570
Siguro, ito ay lamang ng dalawang mga karapatan E ni?

932
00:43:49,570 --> 00:43:52,480
Kaya may problemang ito
ng decodability may Morse

933
00:43:52,480 --> 00:43:54,890
code, kung saan maliban kung ang
tao sa pagpapadala sa iyo ng mga mensahe

934
00:43:54,890 --> 00:43:59,510
talagang pause upang maaari mong ayusin ng
makita o marinig ang puwang sa pagitan ng mga titik,

935
00:43:59,510 --> 00:44:02,990
ito ay hindi sapat lamang upang
magpadala ng isang stream ng mga zero at mga,

936
00:44:02,990 --> 00:44:05,610
o tuldok at gitling,
dahil may kalabuan.

937
00:44:05,610 --> 00:44:08,640
E ay isang single dot, kaya kung ikaw
makakita ng dalawang tuldok o marinig ng dalawang tuldok,

938
00:44:08,640 --> 00:44:11,254
marahil ito ay dalawang E o marahil ito ay isa I.

939
00:44:11,254 --> 00:44:13,670
Kaya kailangan namin ng isang sistema na ang isang
maliit na mas matalino kaysa sa.

940
00:44:13,670 --> 00:44:16,851
Kaya ang isang lalaki na nagngangalang Huffman taon
ang nakalipas ay dumating up na may eksaktong ito.

941
00:44:16,851 --> 00:44:18,600
Kaya lamang kami ay pagpunta
upang kumuha ng isang mabilis na sulyap

942
00:44:18,600 --> 00:44:20,114
at kung paano ang puno ay dyermeyn sa ito.

943
00:44:20,114 --> 00:44:22,530
Ipagpalagay na ito ay ilang
tangang mensahe na nais mong ipadala,

944
00:44:22,530 --> 00:44:26,342
binubuo ng lamang A, B, C D'ni S at E ni,
ngunit may isang pulutong ng mga kalabisan dito.

945
00:44:26,342 --> 00:44:27,550
Hindi ito ay nilalayong maging Ingles.

946
00:44:27,550 --> 00:44:28,341
Ito ay hindi naka-encrypt.

947
00:44:28,341 --> 00:44:30,540
Ito ay lamang ng tangang mensahe
na may maraming pag-uulit.

948
00:44:30,540 --> 00:44:34,010
Kaya kung aktwal mong bilangin ang lahat ng mga
A, E ni B, C, D, at, narito ang

949
00:44:34,010 --> 00:44:34,890
ang dalas.

950
00:44:34,890 --> 00:44:37,800
20% ng mga titik ay
A, ang 45% ng mga titik

951
00:44:37,800 --> 00:44:39,660
mga E, at ang tatlong iba pang mga frequency.

952
00:44:39,660 --> 00:44:41,960
Kami ay mabibilang up doon manu-mano
at ginawa ang matematika.

953
00:44:41,960 --> 00:44:44,579
>> Kaya ito ay lumiliko out na
Huffman, ilang oras ang nakalipas,

954
00:44:44,579 --> 00:44:46,620
natanto na, alam mo
ano, kung sisimulan ko na gusali

955
00:44:46,620 --> 00:44:51,172
isang puno, o gubat ng mga puno, kung ikaw ay,
tulad ng sumusunod, maaari kong gawin ang mga sumusunod.

956
00:44:51,172 --> 00:44:53,880
Pupunta ako upang bigyan ng node sa bawat
sa mga titik na ako pag-aalaga tungkol

957
00:44:53,880 --> 00:44:55,530
at ako pagpunta sa mga tindahan ng
sa loob ng na node

958
00:44:55,530 --> 00:44:58,610
ang frequency bilang isang lumulutang point
halaga, o maaari mo itong gamitin ng isang N, masyadong,

959
00:44:58,610 --> 00:45:00,210
ngunit lamang namin makikita gumamit ng isang float dito.

960
00:45:00,210 --> 00:45:03,100
At ang mga algorithm na
iminungkahi na siya ay na kayo

961
00:45:03,100 --> 00:45:07,210
tumagal ito ng gubat ng solong node
puno, kaya super maikling puno,

962
00:45:07,210 --> 00:45:11,920
at simulan mo pagkonekta sa kanila sa
bagong grupo, bagong mga magulang, kung ikaw ay.

963
00:45:11,920 --> 00:45:16,150
At gawin mo ito sa pamamagitan ng pagpili ng
dalawang pinakamaliit na frequency sa isang pagkakataon.

964
00:45:16,150 --> 00:45:18,110
Kaya ko kinuha ng 10% at 10%.

965
00:45:18,110 --> 00:45:19,090
Lumikha ako ng bagong node.

966
00:45:19,090 --> 00:45:20,910
At ang tawag ko sa bagong node sa 20%.

967
00:45:20,910 --> 00:45:22,750
>> Ano ang dalawang nodes pagsamahin ko susunod?

968
00:45:22,750 --> 00:45:23,810
Ito ay isang maliit na hindi maliwanag.

969
00:45:23,810 --> 00:45:26,643
Kaya may ilang mga sulok ng mga kaso sa
isaalang-alang, ngunit upang panatilihin medyo bagay,

970
00:45:26,643 --> 00:45:29,300
Pupunta ako upang pumili ng 20% ​​-
Ngayon huwag pansinin ko ang mga anak.

971
00:45:29,300 --> 00:45:33,640
Pupunta ako upang pumili ng 20% ​​at
15% at gumuhit ng dalawang bagong mga gilid.

972
00:45:33,640 --> 00:45:35,624
At ngayon kung saan ang dalawang nodes
huwag lohikal kong pagsamahin?

973
00:45:35,624 --> 00:45:38,540
Huwag pansinin ang lahat ng mga bata, ang lahat ng mga
apo, tingnan lamang sa mga ugat

974
00:45:38,540 --> 00:45:39,070
ngayon.

975
00:45:39,070 --> 00:45:42,220
Ano ang dalawang nodes ko itali?

976
00:45:42,220 --> 00:45:44,530
Dalawang Point at 0.35.

977
00:45:44,530 --> 00:45:45,890
Kaya ipaalam sa akin gumuhit ng dalawang bagong mga gilid.

978
00:45:45,890 --> 00:45:47,570
At pagkatapos lamang ang nakuha ko ang isa kaliwa.

979
00:45:47,570 --> 00:45:48,650
Kaya narito ang isang puno.

980
00:45:48,650 --> 00:45:51,160
At ito ay iguguhit kusa
upang tumingin ng uri ng pretty,

981
00:45:51,160 --> 00:45:55,870
ngunit mapapansin na ang mga gilid ay may
din ay may label na zero at isa.

982
00:45:55,870 --> 00:45:59,510
Kaya lahat ng kaliwang gilid ay zero
nagkataon, ngunit patuloy.

983
00:45:59,510 --> 00:46:01,170
Ang lahat ng mga karapatan gilid ay bago.

984
00:46:01,170 --> 00:46:05,070
>> At kaya kung ano ipinanukalang Hoffman ay,
kung nais mong kumatawan ng isang B,

985
00:46:05,070 --> 00:46:10,080
sa halip na kumakatawan sa bilang 66 bilang
isang Ascii kung saan ay walong buong bits,

986
00:46:10,080 --> 00:46:13,360
alam mo kung ano, kung store
mga pattern zero, zero, zero,

987
00:46:13,360 --> 00:46:17,030
zero, dahil iyon ang landas
mula sa aking mga puno, tree Mr. Huffman ni,

988
00:46:17,030 --> 00:46:18,600
sa dahon mula sa mga ugat.

989
00:46:18,600 --> 00:46:20,970
Kung nais mong i-store ang isang
E, sa pamamagitan ng kaibahan, hindi

990
00:46:20,970 --> 00:46:26,290
magpadala ng walong bits na kumakatawan sa isang E.
Sa halip, magpadala ng kung ano ang pattern ng bits?

991
00:46:26,290 --> 00:46:26,890
One.

992
00:46:26,890 --> 00:46:30,410
At kung ano ang magaling tungkol sa ito ay
na E ay ang pinaka-popular na mga titik,

993
00:46:30,410 --> 00:46:32,340
at gumagamit ka ng mga
pinakamaikling code para dito.

994
00:46:32,340 --> 00:46:34,090
Ang susunod na pinaka popular
Mukhang sulat tulad nito

995
00:46:34,090 --> 00:46:37,380
ay A. At kaya kung gaano karaming mga bits
niya iminungkahing gamit para sa na?

996
00:46:37,380 --> 00:46:38,270
Zero, isa.

997
00:46:38,270 --> 00:46:41,060
>> At dahil ito ay ipinatupad
bilang punong ito, para sa ngayon

998
00:46:41,060 --> 00:46:43,350
hayaan mo akong magtadhana mayroong
walang kalabuan bilang sa Morse

999
00:46:43,350 --> 00:46:46,090
code, dahil ang lahat ng
mga titik na mahalaga sa iyo

1000
00:46:46,090 --> 00:46:48,780
ay nasa dulo ng mga gilid.

1001
00:46:48,780 --> 00:46:50,580
Kaya na ang isa lamang sa
application ng isang puno.

1002
00:46:50,580 --> 00:46:52,538
Ito is-- at makikita ko iwagayway
ang aking mga kamay sa ito kung paano mo

1003
00:46:52,538 --> 00:46:55,570
maaaring ipatupad ito bilang isang istraktura C.

1004
00:46:55,570 --> 00:46:58,260
Kailangan lang namin upang pagsamahin
isang simbolo, tulad ng isang pansamantalang trabaho,

1005
00:46:58,260 --> 00:46:59,910
at ang dalas sa kaliwa at kanan.

1006
00:46:59,910 --> 00:47:02,510
Ngunit Tingnan natin ang dalawang ipaalam
huling halimbawa na makikita mo

1007
00:47:02,510 --> 00:47:06,070
makakuha ng lubos na pamilyar sa matapos
quiz zero sa hanay ng problema limang.

1008
00:47:06,070 --> 00:47:09,210
>> Kaya may mga istraktura ng data
kilala bilang isang hash table.

1009
00:47:09,210 --> 00:47:12,247
At isang hash table ay uri ng
palamig na ito ay may mga bucket.

1010
00:47:12,247 --> 00:47:14,830
At ipagpalagay na mayroong apat na timba
dito, lamang ng apat na blangko ang puwang.

1011
00:47:14,830 --> 00:47:20,830
Narito ang isang deck ng mga baraha, at dito ay
club, pala, club, diamonds, club,

1012
00:47:20,830 --> 00:47:25,960
diamonds, club, diamonds,
clubs-- kaya ito ay ang random.

1013
00:47:25,960 --> 00:47:30,330
Puso, kaya hindi ako hearts--
bucketizing lahat ng mga input dito.

1014
00:47:30,330 --> 00:47:32,430
At isang pangangailangan hash table
upang tumingin sa iyong input,

1015
00:47:32,430 --> 00:47:34,850
at pagkatapos ay ilagay ito sa isang tiyak
maglagay batay sa kung ano ang nakikita mo.

1016
00:47:34,850 --> 00:47:35,600
Ito ay isang algorithm.

1017
00:47:35,600 --> 00:47:37,980
At ako ay gumagamit ng isang super
simpleng visual algorithm.

1018
00:47:37,980 --> 00:47:40,030
Ang pinakamahirap na bahagi ng kung saan ay
alala kung ano ang mga larawan ay.

1019
00:47:40,030 --> 00:47:41,590
At pagkatapos ay may apat na total bagay.

1020
00:47:41,590 --> 00:47:45,440
>> Ngayon ang mga stack ay lumalaki, na
ay isang sinadya disenyo bagay dito.

1021
00:47:45,440 --> 00:47:46,540
Ngunit ano pa ang maaari kong gawin?

1022
00:47:46,540 --> 00:47:49,080
Kaya talagang dito kami ay may isang
grupo ng mga lumang libro pagsusulit paaralan.

1023
00:47:49,080 --> 00:47:51,240
Ipagpalagay na ang isang grupo ng mga
pangalan mag-aaral ay sa dito.

1024
00:47:51,240 --> 00:47:52,570
Narito ang isang mas malaking hash table.

1025
00:47:52,570 --> 00:47:54,867
Sa halip ng apat na bucket,
Ako ay may, sabihin natin 26.

1026
00:47:54,867 --> 00:47:57,950
At hindi namin nais na pumunta humiram 26
mga bagay-bagay mula sa labas [? Annenberg?], Kaya

1027
00:47:57,950 --> 00:48:00,289
narito ang limang na kumakatawan
A pamamagitan Z. At kung ako

1028
00:48:00,289 --> 00:48:03,580
makita ang isang mag-aaral na ang pangalan ay nagsisimula sa A,
Pupunta ako upang ilagay ang kanyang quiz doon.

1029
00:48:03,580 --> 00:48:08,850
Kung ang isang tao ay nagsisimula sa C, sa banda roon,
A-- talaga, ay hindi nais na gawin iyon.

1030
00:48:08,850 --> 00:48:10,060
B napupunta sa paglipas dito.

1031
00:48:10,060 --> 00:48:13,390
Kaya ko na nakuha ng A at B at C. At
ngayon narito ang isa pang Ang mag-aaral.

1032
00:48:13,390 --> 00:48:16,212
Ngunit kung ito hash table ay
ipinatupad sa isang array,

1033
00:48:16,212 --> 00:48:17,920
Uri ng ako screwed
sa puntong ito, right?

1034
00:48:17,920 --> 00:48:19,510
Ako uri ng kailangan upang ilagay ito sa isang lugar.

1035
00:48:19,510 --> 00:48:24,380
>> Kaya isang paraan ang maaari kong malutas ito ay, ang lahat ng
karapatan, A ay abala, B ay abala, C ay abala.

1036
00:48:24,380 --> 00:48:28,880
Pupunta ako sa ilagay sa kanya sa D. Kaya sa
una, ako ay may random instant access

1037
00:48:28,880 --> 00:48:31,064
sa bawat isa sa mga bucket para sa mga mag-aaral.

1038
00:48:31,064 --> 00:48:33,230
Ngunit ngayon ito ay uri ng devolved
sa isang bagay na sa guhit,

1039
00:48:33,230 --> 00:48:36,750
dahil kung gusto ko upang maghanap para sa isang tao
Pangalan na nagsisimula sa A, i-check ko dito.

1040
00:48:36,750 --> 00:48:38,854
Ngunit kung ito ay hindi ang isang
mag-aaral na Naghahanap ako ng,

1041
00:48:38,854 --> 00:48:41,520
Ako uri ng may upang simulan ang paglagay ng tsek
ang mga balde, dahil ang aking ginawa

1042
00:48:41,520 --> 00:48:44,530
ay isang uri ng linear
suriing mabuti ang istraktura ng data.

1043
00:48:44,530 --> 00:48:47,710
Isang hangal na paraan ng sinasabi tingnan lamang
para sa unang magagamit pagbubukas,

1044
00:48:47,710 --> 00:48:51,850
at ilagay bilang isang plan B, kaya na magsalita,
o plano D sa kasong ito, ang halaga

1045
00:48:51,850 --> 00:48:53,340
sa lokasyong iyon sa halip.

1046
00:48:53,340 --> 00:48:56,470
Ito ay upang lamang na kung na sa iyo
Nakakuha ng 26 mga lokasyon at walang mga mag-aaral

1047
00:48:56,470 --> 00:49:00,600
may pangalan Q o Z, o isang bagay tulad
na, hindi bababa sa ikaw ay gumagamit ng space.

1048
00:49:00,600 --> 00:49:03,140
>> Ngunit na namin nakita pa
matalino solusyon dito, tama?

1049
00:49:03,140 --> 00:49:04,870
Ano ang gusto mong gawin sa halip
kung mayroon kang isang banggaan?

1050
00:49:04,870 --> 00:49:06,670
Kung ang dalawang tao ay may
ang pangalan A, ano ang gagawin

1051
00:49:06,670 --> 00:49:09,160
ay isang mas matalinong o higit pa
madaling gamitin na solusyon na lamang

1052
00:49:09,160 --> 00:49:12,840
paglagay A kung saan ang D ay dapat na maging?

1053
00:49:12,840 --> 00:49:14,810
Bakit hindi ko na lang pumunta
sa labas [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
tulad ng malloc, isa pang node, ilagay ito
dito, at pagkatapos ay ilagay na isang mag-aaral dito.

1055
00:49:19,960 --> 00:49:22,120
Kaya na ako ay may mahalagang
ilang mga uri ng isang array,

1056
00:49:22,120 --> 00:49:25,590
o marahil mas elegante bilang hindi namin
simula upang makita ang isang listahan ng mga link.

1057
00:49:25,590 --> 00:49:29,520
>> At kaya ng hash table ay isang istraktura
na maaaring maging ganito ang hitsura lamang,

1058
00:49:29,520 --> 00:49:33,900
ngunit mas cleverly, ka ng isang bagay na tinatawag na
hiwalay na pagdudugtong, kung saan ang isang hash table

1059
00:49:33,900 --> 00:49:38,340
lubos na lamang ay isang array, ang bawat isa sa
na ang mga elemento ay hindi isang numero,

1060
00:49:38,340 --> 00:49:40,470
ay mismong isang listahan ng mga link.

1061
00:49:40,470 --> 00:49:45,080
Kaya na makakuha ka ng sobrang mabilis na access
pagpapasya kung saan upang sirain ang iyong halaga sa.

1062
00:49:45,080 --> 00:49:48,059
Karamihan tulad ng sa halimbawa sa card,
Ginawa ko ang sobrang mabilis na mga desisyon.

1063
00:49:48,059 --> 00:49:49,600
Hearts mapupunta dito, diamonds mapupunta dito.

1064
00:49:49,600 --> 00:49:52,180
Parehong dito, A dito napupunta,
D mapupunta dito, B mapupunta dito.

1065
00:49:52,180 --> 00:49:55,740
Kaya napakabilis na look-ups, at kung
mangyari sa iyo upang tumakbo sa isang case

1066
00:49:55,740 --> 00:49:59,429
kung saan nakuha mo na ang mga banggaan, dalawang
mga tao na may parehong pangalan, kung sa gayon

1067
00:49:59,429 --> 00:50:00,970
simulan mo na lang pag-link ang mga ito nang magkakasama.

1068
00:50:00,970 --> 00:50:03,900
At siguro mong panatilihin ang pinagsunod-sunod ang mga ito
alpabeto, marahil hindi mo gusto.

1069
00:50:03,900 --> 00:50:05,900
Ngunit hindi bababa sa ngayon kami ay ang dynamism.

1070
00:50:05,900 --> 00:50:10,250
Kaya sa isang banda mayroon kaming sobrang mabilis
pare-pareho ang oras, at ang uri ng haba ng panahon

1071
00:50:10,250 --> 00:50:14,110
kasangkot kung ang mga naka-link na mga listahan
simulan upang makakuha ng isang maliit na mahaba.

1072
00:50:14,110 --> 00:50:16,880
>> Kaya ito uri ng isang walang isip,
geeky joke taon na ang nakakaraan.

1073
00:50:16,880 --> 00:50:19,590
Sa CS50 hack-a-Thon,
kapag mag-aaral-check in,

1074
00:50:19,590 --> 00:50:22,040
ilang TF o CA sa bawat taon
sa palagay nito ay nakatatawa upang ilagay up

1075
00:50:22,040 --> 00:50:27,772
isang tanda na ito, kung saan ito lamang
ay nangangahulugan na ang iyong pangalan ay nagsisimula sa isang A,

1076
00:50:27,772 --> 00:50:28,870
pumunta sa ganitong paraan.

1077
00:50:28,870 --> 00:50:31,110
Kung ang iyong pangalan ay nagsisimula
may isang B, pumunta this-- OK,

1078
00:50:31,110 --> 00:50:33,290
ito ay nakatatawa baka mamaya sa semester.

1079
00:50:33,290 --> 00:50:36,420
Subalit mayroong isa pang
paraan ng paggawa nito, masyadong.

1080
00:50:36,420 --> 00:50:37,410
Bumalik sa na.

1081
00:50:37,410 --> 00:50:38,600
>> Kaya may structure na ito.

1082
00:50:38,600 --> 00:50:40,420
At ito ang aming huling
istraktura para sa araw na ito,

1083
00:50:40,420 --> 00:50:42,400
na kung saan ay isang bagay na tinatawag na isang trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, na para sa ilang kadahilanan ay maikli
para sa pagkuha, ngunit ito ay tinatawag trie.

1085
00:50:47,140 --> 00:50:51,389
Kaya ang isang trie ay isa pang kawili-wiling
amalgam ng isang pulutong ng mga ideya.

1086
00:50:51,389 --> 00:50:52,930
Ito ay isang puno, na kung saan namin nakita bago.

1087
00:50:52,930 --> 00:50:54,180
Ito ay hindi isang binary puno ng paghahanap.

1088
00:50:54,180 --> 00:50:58,410
Ito ay isang puno na may anumang bilang ng mga bata,
ngunit ang bawat isa sa mga anak sa isang trie

1089
00:50:58,410 --> 00:51:00,090
ay isang array.

1090
00:51:00,090 --> 00:51:04,790
Isang hanay ng mga sukat, sabihin, 26 o marahil 27
kung gusto mong suportahan nagigitlingan mga pangalan

1091
00:51:04,790 --> 00:51:06,790
o apostrophes sa mga pangalan ng mga tao.

1092
00:51:06,790 --> 00:51:08,280
>> At kaya ito ay isang istraktura ng data.

1093
00:51:08,280 --> 00:51:10,290
At kung titingnan mo mula sa tuktok
hanggang sa ibaba, tulad ng kung ikaw

1094
00:51:10,290 --> 00:51:13,710
tumingin sa itaas node doon, M, ay
tumuturo sa pinakakaliwa bagay doon,

1095
00:51:13,710 --> 00:51:17,665
na kung saan pagkatapos A, X, W, E, L, L. Ito ang
lamang ng isang istraktura ng data na nagkataon

1096
00:51:17,665 --> 00:51:19,120
ay pag-iimbak ng mga pangalan ng mga tao.

1097
00:51:19,120 --> 00:51:25,720
At Maxwell ay naka-imbak sa pamamagitan ng mga sumusunod na lamang
isang landas ng array na array na array.

1098
00:51:25,720 --> 00:51:30,050
Ngunit kung ano ang amazing tungkol sa isang trie ay
na iyon, kung saan ang isang listahan ng mga link at kahit na

1099
00:51:30,050 --> 00:51:34,520
isang array, ang pinakamahusay na kailanman namin nakuha ay
sa haba ng panahon o logarithmic oras ng pagtingin

1100
00:51:34,520 --> 00:51:35,600
isang tao up.

1101
00:51:35,600 --> 00:51:40,530
Sa data na istraktura ng isang trie, kung
aking mga istraktura ng data ay may isang pangalan sa loob nito

1102
00:51:40,530 --> 00:51:43,720
at Naghahanap ako ng Maxwell, ako
pagpunta upang mahanap sa kanya ng medyo mabilis.

1103
00:51:43,720 --> 00:51:47,910
Inaasahan ko lamang para sa M-A-X-W-E-L-L. Kapag
ito istraktura ng data, sa pamamagitan ng kaibahan,

1104
00:51:47,910 --> 00:51:51,830
kung N ay isang milyon, kung may isang
milyong pangalan sa istraktura ng data,

1105
00:51:51,830 --> 00:51:57,100
Maxwell ay pa rin pagpunta sa maging
natutuklasan matapos lamang M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
hakbang.

1107
00:51:58,090 --> 00:52:01,276
At David-- D-A-V-I-D na mga hakbang.

1108
00:52:01,276 --> 00:52:03,400
Sa ibang salita, sa pamamagitan ng pagbuo
isang istraktura ng data na

1109
00:52:03,400 --> 00:52:07,240
nakuha ko ang lahat ng mga array, ang lahat ay
suportahan ang kanilang sarili random access,

1110
00:52:07,240 --> 00:52:11,090
Maaari ko bang magsimula naghahanap up tao
pangalan ng paggamit ng isang halaga ng oras na

1111
00:52:11,090 --> 00:52:14,340
proporsyonal sa hindi ang bilang
ng mga bagay sa istraktura ng data,

1112
00:52:14,340 --> 00:52:16,330
tulad ng isang milyong mga umiiral na mga pangalan.

1113
00:52:16,330 --> 00:52:20,135
Ang halaga ng oras na aabutin sa akin upang mahanap
M-A-X-W-E-L-L sa ganitong istraktura ng data ay

1114
00:52:20,135 --> 00:52:22,260
proportional na hindi ang
laki ng mga istraktura ng data,

1115
00:52:22,260 --> 00:52:25,930
ngunit sa ang haba ng pangalan.

1116
00:52:25,930 --> 00:52:28,440
At makatotohanan ang
pangalan hinahanap namin up

1117
00:52:28,440 --> 00:52:29,970
ay hindi kailanman pagpunta na mabaliw sa haba.

1118
00:52:29,970 --> 00:52:32,600
Siguro isang tao ay may isang 10 na karakter
pangalan, 20 pangalan ng character.

1119
00:52:32,600 --> 00:52:33,900
Ito ay tiyak na may hangganan, di ba?

1120
00:52:33,900 --> 00:52:37,110
May isang tao sa Earth na
may pinakamahabang posibleng pangalan,

1121
00:52:37,110 --> 00:52:39,920
ngunit na ang pangalan ay isang pare-pareho
haba ng halaga, i-right?

1122
00:52:39,920 --> 00:52:41,980
Hindi ito nag-iiba sa anumang kahulugan.

1123
00:52:41,980 --> 00:52:45,090
Kaya sa ganitong paraan, na namin
nakakamit ng isang istraktura ng data

1124
00:52:45,090 --> 00:52:47,800
iyon ay pare-pareho ang time look-up.

1125
00:52:47,800 --> 00:52:50,670
Ito ay tumagal ng isang bilang ng mga hakbang
depende sa haba ng input,

1126
00:52:50,670 --> 00:52:54,250
ngunit hindi ang bilang ng mga pangalan
sa istraktura ng data.

1127
00:52:54,250 --> 00:52:58,700
Kaya kung double namin ang bilang ng mga pangalan
sa susunod na taon mula sa isang bilyon sa dalawang bilyon,

1128
00:52:58,700 --> 00:53:03,720
paghahanap ng Maxwell ay pagpunta sa tumagal
ang eksaktong parehong bilang ng mga pitong hakbang

1129
00:53:03,720 --> 00:53:04,650
upang mahanap sa kanya.

1130
00:53:04,650 --> 00:53:08,810
At kaya kami ay tila na magkaroon ng nakakamit
ang aming banal na Kopita ng pagtakbo ng oras.

1131
00:53:08,810 --> 00:53:10,860
>> Kaya ang isang pares ng mga mabilis announcements.

1132
00:53:10,860 --> 00:53:11,850
Pagsusulit zero ay paparating na.

1133
00:53:11,850 --> 00:53:14,600
Higit pa sa na sa website ng kurso
sa loob ng susunod na ilang mga araw.

1134
00:53:14,600 --> 00:53:17,120
Lunes ng lecture-- ito ay isang holiday
dito sa Harvard sa Lunes.

1135
00:53:17,120 --> 00:53:18,850
Hindi ito sa New Haven,
kaya kami ay ang pagkuha ng mga klase

1136
00:53:18,850 --> 00:53:20,310
sa New Haven para sa mga panayam sa Lunes.

1137
00:53:20,310 --> 00:53:22,550
Lahat ng bagay ay kumuha
at stream ng live na tulad ng dati,

1138
00:53:22,550 --> 00:53:24,900
ngunit magtapos sa ngayon hayaan
may isang 30 segundong clip

1139
00:53:24,900 --> 00:53:26,910
tinatawag na "Deep saloobin"
sa pamamagitan ng Daven Farnham, na

1140
00:53:26,910 --> 00:53:30,850
ay inspirasyon ng nakaraang taon sa pamamagitan ng Sabado
"Deep saloobin" Night Live ni

1141
00:53:30,850 --> 00:53:35,700
sa pamamagitan ng Jack na madaling gamitin, na kung saan
dapat gumawa na ngayon ng kahulugan.

1142
00:53:35,700 --> 00:53:38,810
>> Pelikula: At ngayon, "Deep
Mga saloobin "sa pamamagitan ng Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash table.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> Tagapagsalita 1: Ang lahat ng mga karapatan, na ito para sa ngayon.

1147
00:53:47,660 --> 00:53:48,805
Kami ay makikita mo sa susunod na linggo.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Upang makita ang mga ito sa aksyon.

1150
00:53:56,680 --> 00:53:58,304
Kaya sabihin kumuha ng isang pagtingin sa na ngayon.

1151
00:53:58,304 --> 00:53:59,890
Kaya dito, mayroon kaming isang unsorted array.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, maaari mong sige, at i-restart
na ito para lang isang segundo, please.

1153
00:54:04,860 --> 00:54:08,562
Lahat ng mga karapatan, mga camera ay lumiligid, kaya
pagkilos sa tuwing ikaw ay handa na, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Lahat ng mga karapatan, kaya kung ano ang aming
Mayroon dito ay isang unsorted array.

1155
00:54:11,020 --> 00:54:13,960
At ako may kulay na ang lahat ng mga elemento
red upang ipahiwatig na ito ay, sa katunayan,

1156
00:54:13,960 --> 00:54:14,460
unsorted.

1157
00:54:14,460 --> 00:54:17,960
Kaya isipin na ang unang bagay na aming
ay namin ayusin ang kaliwa kalahati ng array.

1158
00:54:17,960 --> 00:54:20,630
Pagkatapos ayusin namin ang karapatan
kalahati ng array.

1159
00:54:20,630 --> 00:54:22,830
At ya-da, ya-da, ya-da,
sumanib namin ang mga ito nang magkakasama.

1160
00:54:22,830 --> 00:54:24,520
At kami ay may isang ganap na pinagsunod-sunod array.

1161
00:54:24,520 --> 00:54:25,360
Kaya na kung paano pagsamahin ang mga uri gumagana.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, aba, aba,
cut, cut, cut, cut.

1163
00:54:27,109 --> 00:54:30,130
Doug, maaari mong hindi lamang ya-da, ya-da,
ya-da, ang iyong paraan sa pamamagitan ng pagsasama-uuri.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: ginawa ko lang.

1165
00:54:31,970 --> 00:54:32,832
Ayos lang.

1166
00:54:32,832 --> 00:54:33,540
Humihingi kami ng magandang pumunta.

1167
00:54:33,540 --> 00:54:34,760
Lamang panatilihin ang rolling Hayaan.

1168
00:54:34,760 --> 00:54:35,380
Kaya pa rin,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Ikaw ay may na ipaliwanag
mas ganap kaysa sa na ito.

1170
00:54:37,800 --> 00:54:39,999
Iyan na lamang hindi sapat.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, hindi tayo
kailangan upang bumalik sa isa.

1172
00:54:41,790 --> 00:54:42,350
Ayos lang.

1173
00:54:42,350 --> 00:54:45,690
Kaya pa rin, kung patuloy naming may merge--
Ian, hindi namin sa gitna ng paggawa ng pelikula.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: alam ko.

1175
00:54:46,612 --> 00:54:49,320
At hindi namin maaari lamang ya-da, ya-da,
ya-da, sa pamamagitan ng buong proseso.

1176
00:54:49,320 --> 00:54:52,200
Ikaw ay may na ipaliwanag kung paano ang
dalawang panig makakuha ipinagsama-sama.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Ngunit hindi namin nai
ipinaliwanag kung paano ang dalawang sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Lamang ka na ipinapakita
kanila ng isang merge array.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Alam nila ang proseso.

1180
00:54:56,486 --> 00:54:57,172
Ang mga ito ay multa.

1181
00:54:57,172 --> 00:54:58,380
Na wala na kami ng mahigit sa sampung beses.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: lalaktawan mo tama lang sa ibabaw nito.

1183
00:55:00,330 --> 00:55:03,360
Kami ay pagpunta bumalik sa isa, ikaw
hindi maaari ya-da mo, ya-da sa ibabaw nito.

1184
00:55:03,360 --> 00:55:05,480
Sige, bumalik sa isa.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Mayroon akong upang bumalik
sa pamamagitan ng lahat ng mga slide?

1186
00:55:07,833 --> 00:55:08,332
Diyos ko.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Ito ay tulad ng ika-anim na oras, Ian.

1189
00:55:13,004 --> 00:55:13,940
Ayos lang.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Lahat ng karapatan.

1191
00:55:15,200 --> 00:55:16,590
Handa ka na?

1192
00:55:16,590 --> 00:55:17,400
Great.

1193
00:55:17,400 --> 00:55:18,950
Action.