1
00:00:00,000 --> 00:00:03,423
>> [MUSIC nagpe-play]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI PENG: Maligayang pagdating sa week 6 ng section.

4
00:00:08,210 --> 00:00:11,620
Lumihis namin mula sa aming standard
time na seksyon ng Martes

5
00:00:11,620 --> 00:00:14,130
hapon na ito kaibig-ibig na umaga Linggo.

6
00:00:14,130 --> 00:00:17,330
Salamat sa iyo para sa lahat na
sumama sa akin ngayon, pero sa totoo lang,

7
00:00:17,330 --> 00:00:18,170
isang ikot ng papuri.

8
00:00:18,170 --> 00:00:20,600
>> Iyan ay isang medyo malaking pagsisikap.

9
00:00:20,600 --> 00:00:23,600
Halos ako ay hindi kahit na gawin itong
up sa oras, ngunit ito ay OK.

10
00:00:23,600 --> 00:00:27,520
Kaya alam ko na ang lahat ng sa iyo
may ginawa lamang ito sa pagsusulit.

11
00:00:27,520 --> 00:00:30,370
Una sa lahat, maligayang pagdating sa
tingnan ang bahagi ng na.

12
00:00:30,370 --> 00:00:32,917
>> Pangalawa, makikita namin makipag-usap tungkol dito.

13
00:00:32,917 --> 00:00:34,000
Susubukan naming makipag-usap tungkol sa pagsusulit.

14
00:00:34,000 --> 00:00:35,700
Susubukan naming makipag-usap tungkol sa kung paano
ang iyong ginagawa sa klase.

15
00:00:35,700 --> 00:00:36,550
Ikaw ay fine.

16
00:00:36,550 --> 00:00:39,080
Mayroon akong ang iyong mga pagsusulit para sa
sa iyo sa dulo ng dito,

17
00:00:39,080 --> 00:00:42,120
kaya kung gusto mong guys na kumuha ng
isang tumingin sa ito, lubos fine.

18
00:00:42,120 --> 00:00:46,590
>> Kaya mabilis bago tayo magsimula, ang mga
agenda para sa araw na ito ay ang mga sumusunod.

19
00:00:46,590 --> 00:00:48,430
Tulad ng iyong nakikita, hindi namin
talaga mabilis na pagpapaputok

20
00:00:48,430 --> 00:00:52,120
sa pamamagitan ng isang buong grupo ng mga istruktura ng data
tunay, tunay, tunay mabilis.

21
00:00:52,120 --> 00:00:54,380
Kaya bilang gayon, hindi ito magiging
super interactive ngayon.

22
00:00:54,380 --> 00:00:59,620
Makikita ito lamang maging akin uri ng abot
mga bagay-bagay na sa iyo, at kung malito ko sa inyo,

23
00:00:59,620 --> 00:01:02,680
kung ako pagpunta masyadong mabilis, ipaalam sa akin.

24
00:01:02,680 --> 00:01:05,200
Sila ay lamang ng iba't-ibang data
kaayusan, at bilang bahagi

25
00:01:05,200 --> 00:01:07,070
ng iyong pset para sa mga ito
paparating na linggo, makikita mo

26
00:01:07,070 --> 00:01:10,340
hilingin sa iyo na ipatupad ang isa sa kanila,
marahil ang dalawa sa them-- dalawa sa kanila

27
00:01:10,340 --> 00:01:12,319
sa iyong pset.

28
00:01:12,319 --> 00:01:14,610
OK, kaya ako lamang ang pagpunta sa
magsimula sa ilang mga announcements.

29
00:01:14,610 --> 00:01:19,070
Kami ay pumunta sa paglipas ng mga stack at queues higit pa sa
malalim kaysa sa kung ano ang ginawa namin bago ang pagsusulit.

30
00:01:19,070 --> 00:01:20,990
Kami ay pumunta sa paglipas ng naka-link
listahan muli, muli,

31
00:01:20,990 --> 00:01:23,899
mas malalalim na kaysa sa kung ano
kami ay nagkaroon ng bago ang pagsusulit.

32
00:01:23,899 --> 00:01:26,440
At pagkatapos ay gagamitin namin makipag-usap tungkol hash
mga talahanayan, mga puno at mga pagsusubok, na

33
00:01:26,440 --> 00:01:28,890
ay ang lahat ng kaakit-akit na kinakailangan para sa iyong pset.

34
00:01:28,890 --> 00:01:32,925
At pagkatapos kami ay pumunta sa paglipas ng ilang
helpful tips para sa pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, kaya quiz 0.

36
00:01:37,360 --> 00:01:41,090
Average ay isang 58%.

37
00:01:41,090 --> 00:01:45,370
Ito ay napaka-mababa, at kaya mo guys lahat
Ginawa tunay, tunay mabuti alinsunod

38
00:01:45,370 --> 00:01:46,510
na iyon.

39
00:01:46,510 --> 00:01:49,970
>> Medyo marami, patakaran ng hinlalaki ay na kung ikaw ay
sa loob ng isang standard na paglihis ng mga ibig sabihin ng

40
00:01:49,970 --> 00:01:52,990
lalo na dahil hindi namin sa isang mas
umaliw seksyon, ikaw ay ganap na multa.

41
00:01:52,990 --> 00:01:54,120
Ikaw ay nasa track.

42
00:01:54,120 --> 00:01:55,190
Maganda ang buhay.

43
00:01:55,190 --> 00:01:58,952
>> Alam ko ito ay nakakatakot na isipin na
Tulad ng isang 40% sa mga pagsusulit na ito ang nakuha ko.

44
00:01:58,952 --> 00:02:00,160
Pupunta ako sa mabibigo klase na ito.

45
00:02:00,160 --> 00:02:02,243
Pangako ko sa iyo, hindi ka
pagpunta sa mabibigo sa klase.

46
00:02:02,243 --> 00:02:03,680
Ikaw ay lubos na fine.

47
00:02:03,680 --> 00:02:06,850
>> Para sa mga mo na nakuha sa ibabaw
ang ibig sabihin, kahanga-hanga, kahanga-hanga,

48
00:02:06,850 --> 00:02:08,780
tulad ng, sineseryoso magaling.

49
00:02:08,780 --> 00:02:09,689
Mayroon akong mga ito sa akin.

50
00:02:09,689 --> 00:02:11,730
Huwag mag-atubili na dumating makakuha ng mga ito
sa dulo ng seksyon.

51
00:02:11,730 --> 00:02:14,520
Ipaalam sa akin kung mayroon kang anumang mga
isyu, mga katanungan sa kanila.

52
00:02:14,520 --> 00:02:17,204
Kung idagdag namin ang iyong iskor
mali, ipaalam sa amin.

53
00:02:17,204 --> 00:02:21,240
>> OK, kaya pset5, ito ay isang tunay na
kakaiba linggo para sa Yale sa kamalayan

54
00:02:21,240 --> 00:02:24,240
na ang aming pset ay dahil
Miyerkules sa tanghali kasama

55
00:02:24,240 --> 00:02:27,317
ang late na araw, kaya ito ay aktwal na
theoretically dahil Martes sa tanghali.

56
00:02:27,317 --> 00:02:29,150
Marahil hindi isa tapos
sa Martes sa tanghali.

57
00:02:29,150 --> 00:02:30,830
Iyan ay lubos fine.

58
00:02:30,830 --> 00:02:33,700
Kami ay pagpunta sa may mga oras ng opisina
ngayong gabi pati na rin ang Lunes ng gabi.

59
00:02:33,700 --> 00:02:36,810
At ang lahat ng mga seksyon sa linggong ito ay
talagang i-turn papunta workshops,

60
00:02:36,810 --> 00:02:38,800
kaya huwag mag-atubiling mag-pop in
anumang mga seksyon na nais mo,

61
00:02:38,800 --> 00:02:42,810
at ang mga ito ay uri ng mini-pset
workshops para sa tulong sa mga iyon.

62
00:02:42,810 --> 00:02:45,620
Kaya dahil dito, ito ay ang tanging seksyon
na kung saan kami ay pagtuturo materyal.

63
00:02:45,620 --> 00:02:49,220
Ang lahat ng mga iba pang mga seksyon ay nagbibigay-diin
eksklusibo sa tulong para sa pset.

64
00:02:49,220 --> 00:02:50,146
Oo?

65
00:02:50,146 --> 00:02:52,000
>> Madla: Kung nasaan oras ng opisina?

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG: Oras ng opisina
tonight-- oh, magandang katanungan.

67
00:02:56,120 --> 00:03:00,580
Sa tingin ko oras ng opisina ngayong gabi
ay nasa Teal o sa Commons.

68
00:03:00,580 --> 00:03:02,984
Kung tingnan mo online CS50
at pumunta ka sa oras ng opisina,

69
00:03:02,984 --> 00:03:05,650
dapat ay mayroong isang iskedyul na
ay nagsasabi sa iyo kung saan ang lahat ng mga ito ay.

70
00:03:05,650 --> 00:03:07,954
>> Alam ko mag-ngayong gabi
o bukas ay tial,

71
00:03:07,954 --> 00:03:10,120
at sa tingin ko ay magkaroon kayo ng
commons para sa iba pang mga gabi.

72
00:03:10,120 --> 00:03:11,020
Di ako sigurado.

73
00:03:11,020 --> 00:03:11,700
Magandang tanong.

74
00:03:11,700 --> 00:03:14,430
Lagyan ng check sa CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, anumang mga katanungan tungkol sa
iskedyul para sa susunod tulad ng tatlong araw?

76
00:03:18,780 --> 00:03:21,690
Pangako ko sa inyo guys gaya ni David
sinabi, ito ay ang tuktok ng burol.

77
00:03:21,690 --> 00:03:23,050
Ikaw guys ay halos doon.

78
00:03:23,050 --> 00:03:24,644
Just tatlong higit pang mga araw.

79
00:03:24,644 --> 00:03:26,310
Kumuha ng doon, at pagkatapos ay gagamitin namin ang lahat ng dumating down.

80
00:03:26,310 --> 00:03:28,114
Magkakaroon kami ng isang magandang CS-free break.

81
00:03:28,114 --> 00:03:28,780
Maligayang pagbabalik.

82
00:03:28,780 --> 00:03:30,779
Ipapakita namin sumisid sa web
programming at pag-unlad,

83
00:03:30,779 --> 00:03:35,150
mga bagay na napaka-masaya kumpara
sa ilan sa mga iba pang psets.

84
00:03:35,150 --> 00:03:37,974
At makikita ito ay ginaw, at
kakailanganin naming maraming masaya.

85
00:03:37,974 --> 00:03:38,890
Magkakaroon kami ng mas maraming kendi.

86
00:03:38,890 --> 00:03:39,730
Paumanhin para sa kendi.

87
00:03:39,730 --> 00:03:40,945
Nakalimutan ko ang kendi.

88
00:03:40,945 --> 00:03:43,310
Ito ay isang magaspang umaga.

89
00:03:43,310 --> 00:03:46,340
Kaya ka guys ay halos doon,
at ako ay talagang maipagmamalaki mo guys.

90
00:03:46,340 --> 00:03:49,570
>> OK, kaya stack.

91
00:03:49,570 --> 00:03:53,331
Sino ang mga mahal sa tanong tungkol sa Jack
at ang kanyang mga damit sa pagsusulit?

92
00:03:53,331 --> 00:03:53,830
Walang sinuman?

93
00:03:53,830 --> 00:03:56,500
OK, na fine.

94
00:03:56,500 --> 00:04:00,200
>> Kaya mahalagang hangga't maaari mong
picture Jack, ito tao dito,

95
00:04:00,200 --> 00:04:03,350
nagmamahal upang gawin ang mga damit
out sa tuktok ng stack,

96
00:04:03,350 --> 00:04:05,750
at inilalagay ito pabalik papunta
stack pagkatapos siya ay tapos na.

97
00:04:05,750 --> 00:04:07,600
Kaya sa ganitong paraan, hindi siya
parang pagkuha ng

98
00:04:07,600 --> 00:04:10,090
sa ibaba ng
stack sa kanyang damit.

99
00:04:10,090 --> 00:04:12,600
Kaya ito uri ng naglalarawan
ang pangunahing istraktura ng data

100
00:04:12,600 --> 00:04:16,610
kung paano ang isang stack ay ipinatupad.

101
00:04:16,610 --> 00:04:20,060
>> Mahalaga, sa tingin ng isang
stack bilang ng anumang stack ng mga bagay

102
00:04:20,060 --> 00:04:24,900
kung saan mo ilagay ang mga bagay papunta sa itaas, at
pagkatapos ay pop mo ang mga ito out mula sa tuktok.

103
00:04:24,900 --> 00:04:28,600
Kaya LIFO ay ang acronym tulad namin
upang use-- Huling In, First Out.

104
00:04:28,600 --> 00:04:32,480
At kaya tatagal sa sa itaas ng
stack ay ang unang isa na dumating out.

105
00:04:32,480 --> 00:04:34,260
At upang ang dalawang termino
gusto namin upang iugnay

106
00:04:34,260 --> 00:04:36,190
may mga tinatawag na push at pop.

107
00:04:36,190 --> 00:04:39,790
Kapag itulak mo ang isang bagay papunta sa
stack, at pop mo ito back up.

108
00:04:39,790 --> 00:04:43,422
>> At kaya ako hulaan ito ay uri ng isang
abstract konsepto, para sa inyo

109
00:04:43,422 --> 00:04:45,630
na nais na makita tulad ng isang
aktwal na pagpapatupad ng mga ito

110
00:04:45,630 --> 00:04:46,740
sa tunay na mundo.

111
00:04:46,740 --> 00:04:50,170
Ilan sa inyo ang may nakasulat na sanaysay
siguro tulad ng isang oras bago ito ay dahil,

112
00:04:50,170 --> 00:04:54,510
at hindi mo sinasadyang natanggal ang isang malaking
tipak ng mga ito, tulad ng aksidenteng?

113
00:04:54,510 --> 00:04:58,560
At pagkatapos ay kung ano ang control gawin
ginagamit namin upang ilagay ito pabalik?

114
00:04:58,560 --> 00:05:00,030
Control-Z, oo?

115
00:05:00,030 --> 00:05:03,640
Control-Z, kaya ang halaga ng beses
na Control-Z ay nai-save ang aking buhay,

116
00:05:03,640 --> 00:05:08,820
Iniligtas aking asno, sa bawat panahon
na ipinatupad sa pamamagitan ng isang stack.

117
00:05:08,820 --> 00:05:13,020
>> Totoo lahat ng mga impormasyon
na sa iyong Word document,

118
00:05:13,020 --> 00:05:15,080
ito ay makakakuha ng hunhon at pop sa kalooban.

119
00:05:15,080 --> 00:05:19,460
At kaya mahalagang kailan mo
tanggalin ang anumang bagay, pop mo ito back up.

120
00:05:19,460 --> 00:05:22,820
At pagkatapos ay kung kailangan mo ito muli, ikaw
itulak ito, na kung saan ay kung ano ang Control-C.

121
00:05:22,820 --> 00:05:26,770
At kaya tunay na function mundo
ng kung paano simpleng istraktura ng data

122
00:05:26,770 --> 00:05:28,690
maaaring makatulong sa iyong pang-araw araw na buhay.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Kaya ang isang struct ay ang paraan na
kami ang tunay na lumikha ng isang stack.

125
00:05:40,150 --> 00:05:44,720
Type naming tukuyin struct, at pagkatapos ay
tawag namin ito stack sa ilalim.

126
00:05:44,720 --> 00:05:47,440
At sa loob ng stack,
kami ay may dalawang mga parameter

127
00:05:47,440 --> 00:05:51,580
na maaari naming mahalagang manipulahin,
kaya kami ay may char kapasidad star string.

128
00:05:51,580 --> 00:05:55,150
>> Lahat na ito ay ginagawa
ay ang paglikha ng isang array

129
00:05:55,150 --> 00:05:58,835
na maaari kaming mag-imbak ng anumang nais mo
na kung saan maaari naming matukoy ang kapasidad nito.

130
00:05:58,835 --> 00:06:01,990
Kapasidad Ay lang ang max na halaga ng
mga item na maaari naming ilagay sa array na ito.

131
00:06:01,990 --> 00:06:05,660
size int ay ang counter na mapigil
subaybayan kung gaano karaming mga item ay kasalukuyang

132
00:06:05,660 --> 00:06:07,850
sa stack.

133
00:06:07,850 --> 00:06:11,860
Kaya pagkatapos ay maaari naming subaybayan ang, A,
pareho kung paano malaki ang aktwal na stack ay,

134
00:06:11,860 --> 00:06:14,850
at, B, kung gaano karami ng stack
aming pinuno dahil hindi namin nais

135
00:06:14,850 --> 00:06:18,800
pag-apaw sa kung ano ang aming kapasidad ay.

136
00:06:18,800 --> 00:06:24,340
>> Kaya halimbawa, ang kaibig-ibig
tanong ay sa iyong pagsusulit.

137
00:06:24,340 --> 00:06:28,160
Mahalaga kung paano gawin namin itulak
papunta sa tuktok ng isang stack.

138
00:06:28,160 --> 00:06:28,830
Medyo simple.

139
00:06:28,830 --> 00:06:30,621
Kung titingnan mo ang mga ito,
babagtasin namin ito.

140
00:06:30,621 --> 00:06:32,640
Kung [hindi marinig] size--
Tandaan, kahit kailan mo

141
00:06:32,640 --> 00:06:35,300
nais na ma-access ang anumang mga
parameter sa loob ng isang struct,

142
00:06:35,300 --> 00:06:40,320
gawin mo ang pangalan ng struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> Sa kasong ito, s ay
pangalan ng ating stack.

144
00:06:42,720 --> 00:06:46,230
Gusto naming ma-access ang laki
ng mga ito, kaya ginagawa namin s.size.

145
00:06:46,230 --> 00:06:50,280
Kaya't hangga't ang laki ay hindi
katumbas ng kapasidad o hangga't

146
00:06:50,280 --> 00:06:52,940
bilang na ito ay mas mababa kaysa sa kapasidad,
alinman na nais magtrabaho dito.

147
00:06:52,940 --> 00:06:57,180
>> Gusto mong ma-access ang loob
ng iyong stack, kaya s.strings,

148
00:06:57,180 --> 00:07:00,790
at ikaw ay pagpunta sa ilagay na bagong numero ng
na gusto mong ipasok sa doon.

149
00:07:00,790 --> 00:07:05,030
Sabihin lang kami nais na
ipasok int n papunta sa stack,

150
00:07:05,030 --> 00:07:08,905
maaari naming gawin s.strings,
bracket, s.size katumbas n.

151
00:07:08,905 --> 00:07:11,030
Dahil laki ay kung saan namin
kasalukuyang nasa stack

152
00:07:11,030 --> 00:07:14,590
kung kami ay pagpunta sa itulak
ito sa, namin ma-access lamang

153
00:07:14,590 --> 00:07:17,370
nasaan ang laki ay, ang
kasalukuyang kabuuan ng stack,

154
00:07:17,370 --> 00:07:21,729
at itulak namin ang int n papunta ito.

155
00:07:21,729 --> 00:07:24,770
At pagkatapos ay nais naming tiyakin na
kami ay incrementing din laki ng n,

156
00:07:24,770 --> 00:07:27,436
upang maaari naming subaybayan ang mga na namin
idinagdag ng dagdag na bagay sa stack.

157
00:07:27,436 --> 00:07:29,660
Ngayon kami ay may isang mas mataas na laki.

158
00:07:29,660 --> 00:07:33,196
Ito dito magkaroon ng kahulugan sa
lahat ng tao, kung paano lohikal ito gumagana?

159
00:07:33,196 --> 00:07:34,160
Ito ay uri ng mabilis.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
Madla: Maaari kang pumunta sa ibabaw
ang s.stringss.strings [s.size] muli?

162
00:07:42,160 --> 00:07:45,808
ANDI PENG: Oo naman, kaya kung ano ang ginagawa
s.size kasalukuyang bigyan kami ng?

163
00:07:45,808 --> 00:07:47,440
Madla: Ito ay ang kasalukuyang laki.

164
00:07:47,440 --> 00:07:50,890
ANDI PENG: Eksakto, kaya ang
kasalukuyang index na ang aming mga sukat ay,

165
00:07:50,890 --> 00:07:57,780
at kaya gusto naming ilagay ang bagong integer
na gusto naming ipasok sa s.size.

166
00:07:57,780 --> 00:07:58,760
Ba na magkaroon ng kahulugan?

167
00:07:58,760 --> 00:08:01,110
Dahil s.strings, ang lahat na
ay ang pangalan ng array.

168
00:08:01,110 --> 00:08:03,510
Lahat ng ito ay ay ma-access ang
array sa loob ng aming struct,

169
00:08:03,510 --> 00:08:06,030
at kaya kung gusto naming
ilagay n sa index na,

170
00:08:06,030 --> 00:08:09,651
maaari naming ma-access lamang ito
paggamit ng mga braket s.size.

171
00:08:09,651 --> 00:08:10,150
Cool.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Lahat ng mga karapatan pop,, Pseudocode ko ito
para sa iyo guys, ngunit katulad na konsepto.

174
00:08:18,916 --> 00:08:19,790
Ba na magkaroon ng kahulugan?

175
00:08:19,790 --> 00:08:22,310
Kung ang sukat ay mas malaki
kaysa sa zero, at pagkatapos ay

176
00:08:22,310 --> 00:08:25,350
malaman na nais mong kumuha ng isang bagay
out dahil kung ang laki ay hindi

177
00:08:25,350 --> 00:08:27,620
mas mataas sa zero, at pagkatapos ay
walang kinalaman sa stack.

178
00:08:27,620 --> 00:08:29,840
>> Kaya gusto mo lamang i-execute
ang code na ito, ito ay maaari lamang

179
00:08:29,840 --> 00:08:32,320
pop kung may isang bagay sa pop.

180
00:08:32,320 --> 00:08:35,830
Kaya kung ang laki ay mas malaki
kaysa sa 0, kami ay binawasan ang laki.

181
00:08:35,830 --> 00:08:40,020
Pagbawas namin ang laki at pagkatapos ay bumalik
kahit na ano ay sa loob ng mga ito dahil

182
00:08:40,020 --> 00:08:42,710
sa pamamagitan ng pop, gusto naming
access ang anumang ay naka-imbak

183
00:08:42,710 --> 00:08:45,694
sa index ng tuktok ng stack.

184
00:08:45,694 --> 00:08:46,610
Lahat ng bagay ay magkaroon ng kahulugan?

185
00:08:46,610 --> 00:08:49,693
Kung ginawa ko sa inyo guys isulat ito out,
ay maaaring isulat ito sa iyo guys?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
OK, ka guys ay maaaring i-play sa paligid sa mga ito.

188
00:08:53,570 --> 00:08:55,252
Huwag mag-alala kung hindi mo makuha ang mga ito.

189
00:08:55,252 --> 00:08:57,460
Wala kaming oras upang code
ito ngayon dahil hindi namin

190
00:08:57,460 --> 00:08:59,959
Nakakuha ng maraming mga kaayusan
pumunta sa pamamagitan ng, ngunit mahalagang

191
00:08:59,959 --> 00:09:02,214
pseudocode, tunay, tunay na katulad sa itulak.

192
00:09:02,214 --> 00:09:03,380
Sundan lang sa kahabaan ng logic.

193
00:09:03,380 --> 00:09:06,092
Tiyakin na ikaw ay pag-access sa lahat ng mga
mga tampok ng iyong struct tama.

194
00:09:06,092 --> 00:09:06,574
Oo?

195
00:09:06,574 --> 00:09:09,282
>> Madla: ba ang mga slide at
ang buong bagay na maging up ngayon-ish?

196
00:09:09,282 --> 00:09:11,586
ANDI PENG: Laging, yep.

197
00:09:11,586 --> 00:09:13,710
Pupunta ako sa subukan upang ilagay
ito up tulad ng isang oras pagkatapos.

198
00:09:13,710 --> 00:09:16,626
Kukunin ko i-email David, David ay susubukan na
ilagay ito up tulad ng isang oras matapos na ito.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> OK, kaya pagkatapos naming ilipat ito sa iba pang mga
kaibig-ibig na istraktura ng data na tinatawag na isang queue.

201
00:09:25,470 --> 00:09:30,140
Tulad nang nakikita dito sa iyo guys, isang
pila, para sa mga British sa gitna natin,

202
00:09:30,140 --> 00:09:32,010
lahat ng ito ay ay isang linya.

203
00:09:32,010 --> 00:09:34,680
Kaya salungat sa kung ano
sa tingin mo ang isang stack ay,

204
00:09:34,680 --> 00:09:37,750
isang pila ay kung ano mismo
lohikal na sa tingin mo ay ito.

205
00:09:37,750 --> 00:09:41,914
Ito ay gaganapin sa pamamagitan ng mga patakaran ng FIFO,
na kung saan ay Una Sa, Unang Out.

206
00:09:41,914 --> 00:09:43,705
Kung ikaw ay ang unang
isa sa mga linya, ikaw ay

207
00:09:43,705 --> 00:09:46,230
ang unang isa na
dumating sa labas ng linya.

208
00:09:46,230 --> 00:09:49,680
>> Kaya kung ano ang aming nais na tawag ito
ay dequeueing at enqueueing.

209
00:09:49,680 --> 00:09:52,380
Kung nais namin na magdagdag ng isang bagay
sa aming pila, enqueue namin.

210
00:09:52,380 --> 00:09:55,690
Kung gusto naming dequeue, o kumuha ng
isang bagay ang layo, dequeue namin.

211
00:09:55,690 --> 00:10:03,350
>> Kaya parehong kahulugan na hindi namin uri ng
paglikha elemento nakapirming-size na tayo

212
00:10:03,350 --> 00:10:06,500
Maaaring mag-imbak ng ilang mga
mga bagay-bagay, ngunit maaari din namin

213
00:10:06,500 --> 00:10:10,100
baguhin kung saan kami ay paglalagay
parameter sa loob ng mga ito

214
00:10:10,100 --> 00:10:13,140
batay sa kung anong uri ng
functionality gusto namin.

215
00:10:13,140 --> 00:10:16,700
Kaya stack, gusto naming huling
isa, N na ang unang isa out.

216
00:10:16,700 --> 00:10:19,800
Queue ay gusto namin ang unang bagay
sa na maging ang unang bagay out.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Kaya ang struct-type
tukuyin, tulad ng makikita mo,

219
00:10:26,710 --> 00:10:29,470
ito ay Medyo naiiba
mula sa kung ano ang stack ay

220
00:10:29,470 --> 00:10:33,120
dahil lamang hindi kami ay may upang panatilihin
subaybayan kung saan ang laki sa kasalukuyan ay,

221
00:10:33,120 --> 00:10:37,420
Gusto din namin upang subaybayan ang ulo
pati na rin kung saan kami ay kasalukuyang ay.

222
00:10:37,420 --> 00:10:39,580
Kaya sa tingin ko mas madali
kung gumuhit ko ito up.

223
00:10:39,580 --> 00:10:53,270
Kaya ni isipin namin nakuha ng isang queue ipaalam,
kaya sabihin natin na ang ulo ay karapatan dito.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
Ang ulo ng linya, sabihin
lang sabihin na kasalukuyang doon,

226
00:10:58,310 --> 00:11:01,809
at gusto naming ipasok
isang bagay sa queue.

227
00:11:01,809 --> 00:11:04,350
Pupunta ako sa tawagan size mahalagang
ay ang parehong bagay tulad ng likod o hulihan,

228
00:11:04,350 --> 00:11:06,314
sa dulo ng kung saan ang iyong queue.

229
00:11:06,314 --> 00:11:07,730
Sabihin lang ang laki ay karapatan dito.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Kaya kung paano gumagana ang isa feasibly
ipasok ang isang bagay sa isang queue?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
Ano index ang gusto namin upang ilagay
kung saan gusto naming ipasok sa.

234
00:11:24,130 --> 00:11:29,320
Kung ito ang simula ng iyong
queue at ito ay ang dulo ng ito

235
00:11:29,320 --> 00:11:31,860
o ang laki ng mga ito, kung saan tayo
gustong idagdag ang susunod na object?

236
00:11:31,860 --> 00:11:32,920
>> Madla: [hindi marinig]

237
00:11:32,920 --> 00:11:35,920
ANDI PENG: Eksakto, na nais mong idagdag
ito depende sa ikaw ay may nakasulat na ito.

238
00:11:35,920 --> 00:11:37,840
Alinman ito ay blangko o ng nasa blangko.

239
00:11:37,840 --> 00:11:42,630
Kaya nais mong idagdag ang mga ito ay malamang na
dito dahil kung ang laki is--

240
00:11:42,630 --> 00:11:50,540
kung ang mga ito ay puno ng lahat, na nais mong
upang idagdag ito dito mismo, di ba?

241
00:11:50,540 --> 00:11:57,150
>> At kaya na, habang tunay, tunay
simple, hindi lubos na laging tama

242
00:11:57,150 --> 00:12:00,690
dahil ang pangunahing pagkakaiba
sa pagitan ng isang queue at isang stack

243
00:12:00,690 --> 00:12:04,350
ay na ang queue Maaari
talagang manipulahin

244
00:12:04,350 --> 00:12:06,980
upang ang mga pagbabago sa ulo
depende sa kung saan mo nais

245
00:12:06,980 --> 00:12:08,650
sa simula ng iyong cue upang magsimula.

246
00:12:08,650 --> 00:12:11,900
At bilang isang resulta, ang iyong mga buntot
ay din ng pagpunta sa pagbabago.

247
00:12:11,900 --> 00:12:14,770
At kaya tingnan sa
ang code na ito sa ngayon.

248
00:12:14,770 --> 00:12:18,620
Bilang ka guys ay nagtanong din sa
isulat sa pagsusulit, enqueue.

249
00:12:18,620 --> 00:12:22,580
Siguro makikita namin makipag-usap sa pamamagitan ng kung bakit
ang sagot ay kung ano iyon.

250
00:12:22,580 --> 00:12:26,790
>> Hindi ko lubos na magkasya ang linyang ito sa isa,
ngunit mahalagang ito piraso ng code

251
00:12:26,790 --> 00:12:29,030
ay dapat na sa isang linya.

252
00:12:29,030 --> 00:12:30,140
Spend tulad ng 30 segundo.

253
00:12:30,140 --> 00:12:33,000
Kunin ang hitsura, at makita kung bakit
ito ay ang paraan na ito ay.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Tunay, halos katulad struct, tunay, tunay
katulad na istraktura bilang ang nakaraang

256
00:12:55,420 --> 00:12:58,090
stack maliban para marahil
isang linya ng code.

257
00:12:58,090 --> 00:13:01,190
At na isang linya ng code
ang tumutukoy sa mga pag-andar.

258
00:13:01,190 --> 00:13:03,900
At talagang iiba
isang pila mula sa isang stack.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Sinuman na nais na kumuha ng isang ulos
sa nagpapaliwanag kung bakit na sa iyo

261
00:13:22,010 --> 00:13:24,980
Nakakuha ito komplikadong bagay in dito?

262
00:13:24,980 --> 00:13:27,845
Nakikita natin ang pagbabalik ng ating
kahanga-hangang kaibigan modulus.

263
00:13:27,845 --> 00:13:31,020
Bilang ka guys ay malapit nang dumating
upang makilala sa programming,

264
00:13:31,020 --> 00:13:34,910
halos anumang oras na kailangan mo ng isang bagay
sa wrapper sa paligid ng anumang bagay,

265
00:13:34,910 --> 00:13:36,850
modulus ay magiging ang paraan upang gawin ito.

266
00:13:36,850 --> 00:13:40,510
Kaya alam na, ang sinuman na nais
subukan na nagpapaliwanag na linya ng code?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Oo, ang lahat ng mga sagot ay
tinanggap at maligayang pagdating.

269
00:13:47,507 --> 00:13:48,840
Madla: Ikaw ba ay nakikipag-usap sa akin?

270
00:13:48,840 --> 00:13:49,506
ANDI PENG: Oo.

271
00:13:49,506 --> 00:13:56,200
Madla: Oh, walang sorry.

272
00:13:56,200 --> 00:14:00,250
ANDI PENG: OK, kaya sabihin
maglakad sa pamamagitan ng code na ito.

273
00:14:00,250 --> 00:14:03,642
Kaya kapag sinusubukan mong
magdagdag ng isang bagay papunta sa isang pila,

274
00:14:03,642 --> 00:14:08,510
sa kaibig-ibig na kaso na ang ulo mangyayari
upang maging dito mismo, ito ay tunay madali para sa amin

275
00:14:08,510 --> 00:14:10,960
pumunta lamang sa dulo
ipasok ang isang bagay, i-right?

276
00:14:10,960 --> 00:14:14,690
Ngunit ang buong punto ng isang pila ay
na ang ulo ang tunay na maaari dynamically

277
00:14:14,690 --> 00:14:17,280
magbago depende sa kung saan kami
gusto sa simula ng aming q na,

278
00:14:17,280 --> 00:14:19,880
at dahil dito, ang buntot
ay din ng pagpunta sa pagbabago.

279
00:14:19,880 --> 00:14:31,100
>> At kaya isipin na hindi ang mga ito ay
nakatayo sa hilera, ngunit sa halip ito ay ang queue.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Ipagpalagay natin na ang ulo ay karapatan dito.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Ipagpalagay natin na ang ating queue mukhang ito.

284
00:14:56,980 --> 00:15:00,190
Kung gusto naming shift kung saan
sa simula ng linya ay,

285
00:15:00,190 --> 00:15:03,400
sabihin natin Nilipat namin ulo
sa ganitong paraan at sukat dito.

286
00:15:03,400 --> 00:15:07,100
>> Ngayon nais namin na magdagdag ng isang bagay sa
ito queue, ngunit bilang maaari mong makita ang isang lalaki,

287
00:15:07,100 --> 00:15:11,150
ito ay hindi kaya simple bilang na lamang
magdagdag ng kahit na ano ay pagkatapos ng laki

288
00:15:11,150 --> 00:15:13,630
dahil pagkatapos kami maubusan ng
hangganan ng aming mga aktwal na array.

289
00:15:13,630 --> 00:15:16,190
Saan ang gusto naming talagang magdagdag ay dito.

290
00:15:16,190 --> 00:15:18,610
Iyan ang kagandahan ng isang queue
ay na sa amin, biswal na ito

291
00:15:18,610 --> 00:15:22,380
Mukhang ang linya napupunta tulad nito,
ngunit kapag naka-imbak sa isang istraktura ng data,

292
00:15:22,380 --> 00:15:29,370
bigyan nila ito bilang tulad ng isang cycle.

293
00:15:29,370 --> 00:15:32,360
Ito ay uri ng bumabalot sa palibot
sa harap na sa parehong paraan

294
00:15:32,360 --> 00:15:34,780
na maaari ring balutin ng isang linya
sa paligid depende sa kung saan mo man

295
00:15:34,780 --> 00:15:36,279
nais na simula ng linya na.

296
00:15:36,279 --> 00:15:38,630
At kaya kung tumagal kami ng isang
tumungo dito, sabihin

297
00:15:38,630 --> 00:15:40,880
sabihin gusto naming lumikha ng isang
function na tinatawag enqueue.

298
00:15:40,880 --> 00:15:43,980
Nais naming magdagdag ng int n sa na q.

299
00:15:43,980 --> 00:15:49,250
Kung q.size q-- namin ang tawag na ang aming data
structure-- kung ang aming queue.size hindi

300
00:15:49,250 --> 00:15:52,520
katumbas ng kapasidad o kung
ito ay mas mababa kaysa sa kapasidad,

301
00:15:52,520 --> 00:15:55,120
q.strings ay ang array sa loob ng aming q.

302
00:15:55,120 --> 00:15:58,380
Kami ay pagpunta upang i-set
na katumbas ng q.heads,

303
00:15:58,380 --> 00:16:02,730
na kung saan ay dito mismo, kasama ang q.size
modulus ng kapasidad, na

304
00:16:02,730 --> 00:16:04,290
balutin sa amin pabalik sa paligid dito.

305
00:16:04,290 --> 00:16:08,040
>> Kaya sa ganitong halimbawa, index
ng ulo ay 1, di ba?

306
00:16:08,040 --> 00:16:11,480
Ang index ng laki ay 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Kaya maaari naming gawin 1 plus 4 modulus
pamamagitan ng aming kapasidad na kung saan ay 5.

308
00:16:19,500 --> 00:16:20,920
Ano ang ibig na magbibigay sa atin?

309
00:16:20,920 --> 00:16:23,270
Ano ang index na
dumating sa labas ng ito?

310
00:16:23,270 --> 00:16:24,080
>> Madla: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI PENG: 0, kung saan
mangyayari sa maging dito mismo,

312
00:16:27,870 --> 00:16:30,640
at kaya gusto naming ma
upang ipasok sa karapatan dito.

313
00:16:30,640 --> 00:16:34,730
At kaya ito equation dito uri
ng lang gumagana sa anumang mga numero ng

314
00:16:34,730 --> 00:16:36,750
depende sa kung saan ang iyong mga
ulo at ang iyong mga sukat ay.

315
00:16:36,750 --> 00:16:38,541
Kung alam mo kung ano ang mga
bagay na ito ay, alam mo

316
00:16:38,541 --> 00:16:43,170
eksakto kung saan mo nais na ipasok
kahit na ano ay pagkatapos ng iyong queue.

317
00:16:43,170 --> 00:16:44,640
Ba na magkaroon ng kahulugan sa lahat ng tao?

318
00:16:44,640 --> 00:16:48,560
>> Alam ko ang uri ng isang utak
teaser lalo na dahil ito

319
00:16:48,560 --> 00:16:50,512
dumating sa mga resulta ng iyong pagsusulit.

320
00:16:50,512 --> 00:16:52,220
Ngunit sana sa lahat ng tao
ngayon ay maaaring maunawaan

321
00:16:52,220 --> 00:16:57,800
kung bakit ito solusyon o ito
function na ay ang paraan na ito ay.

322
00:16:57,800 --> 00:16:59,840
Sinuman isang bit hindi maliwanag sa mga iyon?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
SIGE.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> At kaya ngayon, kung ikaw
Nais upang dequeue, ito

327
00:17:09,970 --> 00:17:15,240
ay kung saan ang aming mga ulo ay paglilipat
dahil kung kami ay upang dequeue,

328
00:17:15,240 --> 00:17:17,030
hindi kami gumawa ng off sa dulo ng q.

329
00:17:17,030 --> 00:17:19,130
Gusto naming mag-alis ng ulo, di ba?

330
00:17:19,130 --> 00:17:24,260
Kaya bilang isang resulta, ang ulo ay pagpunta sa pagbabago,
at iyon ay kung bakit kapag enqueue mo,

331
00:17:24,260 --> 00:17:26,800
nakuha mo na subaybayan ang
kung saan ang iyong ulo at ang iyong mga laki

332
00:17:26,800 --> 00:17:29,450
ay para ma-ipasok
sa tamang posisyon.

333
00:17:29,450 --> 00:17:32,740
>> At kaya kapag dequeue mo,
Pseudocode ito rin ako out.

334
00:17:32,740 --> 00:17:35,480
Huwag mag-atubiling kung nais mong
upang tangkain coding na ito out.

335
00:17:35,480 --> 00:17:36,980
Gusto mong ilipat ang ulo, di ba?

336
00:17:36,980 --> 00:17:39,320
Kung Nais kong dequeue, ako
nais ilipat ang ulo sa ibabaw.

337
00:17:39,320 --> 00:17:40,800
Ito ay ang ulo.

338
00:17:40,800 --> 00:17:45,617
>> At ang aming mga kasalukuyang laki ng gagawin
ibawas dahil hindi na kami

339
00:17:45,617 --> 00:17:46,950
may apat na mga elemento sa array.

340
00:17:46,950 --> 00:17:51,370
Kami lamang magkaroon ng tatlo, at pagkatapos ay nais naming
upang bumalik anumang ay naka-imbak sa loob

341
00:17:51,370 --> 00:17:56,260
ng ulo dahil gusto naming gawin ito
halaga sa labas kaya halos kapareho sa stack.

342
00:17:56,260 --> 00:17:58,010
Basta ikaw ay dinadala
mula sa ibang lugar,

343
00:17:58,010 --> 00:18:01,770
at kailangan mong muling italaga ang iyong pointer
sa ibang lugar bilang isang resulta.

344
00:18:01,770 --> 00:18:03,890
Logically, sundin ang lahat?

345
00:18:03,890 --> 00:18:05,690
Great.

346
00:18:05,690 --> 00:18:10,156
>> OK, kaya kami ay pagpunta sa makipag-usap ng kaunti
higit pa sa malalim tungkol sa mga listahan ng link

347
00:18:10,156 --> 00:18:13,280
dahil ang mga ito ay tunay, tunay na mahalaga
para sa iyo sa kurso ng na ito linggo

348
00:18:13,280 --> 00:18:14,964
psets.

349
00:18:14,964 --> 00:18:17,130
Mga listahan ng naka-link, tulad ng sa iyo guys
matandaan, ang lahat ng mga ito ay

350
00:18:17,130 --> 00:18:22,570
mga nodes na nodes ng mga tiyak
mga halaga ng pareho ang halaga at isang pointer

351
00:18:22,570 --> 00:18:26,290
na-link na magkasama
sa pamamagitan ng mga payo.

352
00:18:26,290 --> 00:18:29,880
At upang ang struct sa kung paano
lumikha kami ng isang node dito ay namin

353
00:18:29,880 --> 00:18:33,569
Mayroon int n, na kung saan ay kahit na ano
ang halaga sa isang tindahan o string n

354
00:18:33,569 --> 00:18:35,610
o kahit anong gusto mong
tawag na ito, ang mga char star n.

355
00:18:35,610 --> 00:18:41,482
Struct node star, na kung saan ay ang pointer
na nais mong magkaroon sa bawat node,

356
00:18:41,482 --> 00:18:43,690
ikaw ay pagpunta sa may na
pointer point patungo sa susunod.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Magkakaroon ka ng ulo
ng isang listahan ng mga link na

359
00:18:50,040 --> 00:18:53,140
pagpunta upang tumuro sa mga natitirang bahagi ng
ang mga halaga para sa at iba pa

360
00:18:53,140 --> 00:18:55,290
hanggang sa huli mong maabot ang dulo.

361
00:18:55,290 --> 00:18:58,040
At ito huling node ay lamang
pagpunta sa hindi magkaroon ng isang pointer.

362
00:18:58,040 --> 00:18:59,952
Ito ay pagpunta upang tumuro sa
null, at na kapag

363
00:18:59,952 --> 00:19:01,910
alam mo mo na pindutin ang
dulo ng iyong listahan na naka-link

364
00:19:01,910 --> 00:19:04,076
ay kapag ang iyong huling pointer
ay hindi point sa kahit ano.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Kaya kami ay pagpunta sa pumunta ng kaunti pa sa
malalim tungkol sa kung paano ang isa gagawin posibleng

367
00:19:10,990 --> 00:19:12,400
maghanap ng isang listahan ng mga link.

368
00:19:12,400 --> 00:19:15,460
Tandaan kung ano ang ilan sa mga
drawbacks ng mga listahan ng link

369
00:19:15,460 --> 00:19:19,340
mga bersikulo ng isang array patungkol paghahanap.

370
00:19:19,340 --> 00:19:22,565
Isang hanay ng maaari mong binary paghahanap, ngunit
kung bakit hindi mo maaaring gawin na sa isang listahan ng mga link?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> Madla: Dahil sila ay konektado sa lahat,
ngunit hindi mo masyadong alam kung saan

373
00:19:30,320 --> 00:19:31,330
[Hindi marinig].

374
00:19:31,330 --> 00:19:34,600
>> ANDI PENG: Oo, eksakto kaya tandaan
na ang kinang ng isang array

375
00:19:34,600 --> 00:19:37,190
ay ang katunayan na kami ay
random access memory kung saan

376
00:19:37,190 --> 00:19:41,580
kung gusto ko ang mga halaga mula sa index
anim, maaari ko lamang sabihin index anim,

377
00:19:41,580 --> 00:19:42,407
bigyan ako ng halagang iyon.

378
00:19:42,407 --> 00:19:45,240
At iyon ay dahil array ay pinagsunod-sunod
sa isang magkadikit na puwang ng memory

379
00:19:45,240 --> 00:19:48,020
sa isang lugar, kung saan ang
uri ng mga listahan ng link

380
00:19:48,020 --> 00:19:52,820
ay sapalarang kahalong lahat sa paligid,
at ang tanging paraan na maaari mong mahanap ang isa

381
00:19:52,820 --> 00:19:56,890
ay sa pamamagitan ng isang pointer na nagsasabi sa iyo
ang address kung saan na ang susunod na node ay.

382
00:19:56,890 --> 00:20:00,290
>> At kaya bilang isang resulta, ang tanging paraan
sa paghahanap sa pamamagitan ng isang listahan ng mga link

383
00:20:00,290 --> 00:20:01,560
ay linear paghahanap.

384
00:20:01,560 --> 00:20:05,890
Dahil hindi ko alam kung saan mismo
ang ika-12 na halaga sa naka-link na listahan ay,

385
00:20:05,890 --> 00:20:08,780
Kailangan ko bang tawirin ang kabuuan
ng na listahan ng mga link sa isa

386
00:20:08,780 --> 00:20:12,450
sa pamamagitan ng isa mula sa ulo sa unang node,
sa ikalawang node, sa ikatlong node,

387
00:20:12,450 --> 00:20:17,690
lahat ng mga paraan pababa hanggang sa wakas ako makakuha
na kung saan na node Naghahanap ako ay.

388
00:20:17,690 --> 00:20:22,110
At kaya sa puntong ito, ang paghahanap
sa isang listahan ng mga link ay palaging n.

389
00:20:22,110 --> 00:20:23,040
Ito ay palaging n.

390
00:20:23,040 --> 00:20:25,690
Ito ay palaging sa haba ng panahon.

391
00:20:25,690 --> 00:20:28,470
>> At upang ang mga code na kung saan ang
kami ipatupad ito, at ito

392
00:20:28,470 --> 00:20:32,620
ay isang bit bago para sa iyo guys dahil ikaw
guys ay hindi tunay na usapan tungkol sa o kailanman

393
00:20:32,620 --> 00:20:35,000
nakita mga payo sa kung paano sa
paghahanap sa pamamagitan ng mga payo,

394
00:20:35,000 --> 00:20:37,670
kaya kami ay sa pamamagitan ng paglalakad
ito tunay, tunay dahan-dahan.

395
00:20:37,670 --> 00:20:40,200
Kaya bool search, kanan,
Sabihin isipin gusto naming ipaalam

396
00:20:40,200 --> 00:20:42,820
upang lumikha ng isang function na tinatawag na
paghahanap na nagbabalik ng tunay

397
00:20:42,820 --> 00:20:46,820
kung nakita mo ang halaga sa loob ng mga naka-link
list, at ito ay nagbabalik ng mga maling paraan.

398
00:20:46,820 --> 00:20:50,030
Listahan Node star ay
kasalukuyan lamang ang pointer

399
00:20:50,030 --> 00:20:52,960
sa unang item sa iyong listahan ng naka-link.

400
00:20:52,960 --> 00:20:56,700
int n ay ang halaga na ikaw ay
na naghahanap para sa listahang iyon.

401
00:20:56,700 --> 00:20:58,770
>> Kaya node star pointer katumbas listahan.

402
00:20:58,770 --> 00:21:00,970
Ito ay nangangahulugan na kami ay pagtatakda
at paglikha ng isang pointer

403
00:21:00,970 --> 00:21:03,592
sa na unang node sa loob ng listahan.

404
00:21:03,592 --> 00:21:04,300
Ang bawat sa akin?

405
00:21:04,300 --> 00:21:06,530
Kaya kung kami ay upang pumunta
bumalik dito, nais kong magkaroon ng

406
00:21:06,530 --> 00:21:13,850
initialize isang pointer na tumuturo sa
ang ulo ng kahit anong listahan na.

407
00:21:13,850 --> 00:21:18,600
>> At pagkatapos ay sa sandaling makakuha ka down na dito,
habang pointer ay hindi katumbas null,

408
00:21:18,600 --> 00:21:22,160
nang sa gayon ay ang mga loop na kung saan tayo
magiging sa dakong huli traversing

409
00:21:22,160 --> 00:21:25,940
ang natitirang bahagi ng aming listahan dahil kung ano
mangyayari kapag pointer katumbas null?

410
00:21:25,940 --> 00:21:27,550
Alam namin na have-- namin

411
00:21:27,550 --> 00:21:28,450
>> Madla: [hindi marinig]

412
00:21:28,450 --> 00:21:31,491
>> ANDI PENG: Eksakto, upang malaman namin na
naabot na namin ang dulo ng listahan, i-right?

413
00:21:31,491 --> 00:21:34,470
Kung ikaw ay bumalik dito, ang bawat node
dapat na tumuturo sa ibang node

414
00:21:34,470 --> 00:21:36,550
at iba pa
hanggang maabot mo sa huli

415
00:21:36,550 --> 00:21:41,589
sa likod o hulihan ng iyong listahan ng naka-link,
na kung saan ay may isang pointer na lamang

416
00:21:41,589 --> 00:21:43,130
ay hindi point kahit saan maliban sa no.

417
00:21:43,130 --> 00:21:47,510
At kaya talaga alam mo na
ang iyong listahan ay mayroon pa rin up

418
00:21:47,510 --> 00:21:50,900
hanggang pointer ay hindi katumbas ng
null dahil sa sandaling ito ay katumbas ng null,

419
00:21:50,900 --> 00:21:53,310
Alam mo ba na walang higit pang mga bagay-bagay.

420
00:21:53,310 --> 00:21:56,930
>> Kaya na ang loop na kung saan hindi namin
pagpunta sa may ang aktwal na paghahanap.

421
00:21:56,930 --> 00:22:01,690
At kung ang pointer-- mo makita
na uri ng mga arrow na function doon?

422
00:22:01,690 --> 00:22:06,930
Kaya kung pointer mga puntos upang n, kung
ang pointer sa n katumbas ng ay katumbas n,

423
00:22:06,930 --> 00:22:09,180
kaya na nangangahulugan na kung ang
ang pointer na kayo

424
00:22:09,180 --> 00:22:13,420
na naghahanap para sa dulo ng bawat
node ay talagang katumbas ng halaga

425
00:22:13,420 --> 00:22:15,990
naghahanap ka ng, at pagkatapos ay
gusto mong bumalik totoo.

426
00:22:15,990 --> 00:22:19,280
Kaya talaga, kung ikaw ay nasa isang node na
ay ang halaga na iyong hinahanap para sa,

427
00:22:19,280 --> 00:22:23,550
alam mo na ikaw ay naging
matagumpay na mai maghanap.

428
00:22:23,550 --> 00:22:27,150
>> Kung hindi man, nais mong itakda
iyong pointer sa susunod na node.

429
00:22:27,150 --> 00:22:28,850
Iyon ay kung ano ang ginagawa na linya dito.

430
00:22:28,850 --> 00:22:31,750
Pointer katumbas pointer susunod.

431
00:22:31,750 --> 00:22:33,360
Ang bawat makita kung paano na gumagana?

432
00:22:33,360 --> 00:22:36,580
>> At mahalagang kayo ay pagpunta sa makatarungan
tawirin ang kabuuan ng listahan,

433
00:22:36,580 --> 00:22:41,920
reset ang iyong pointer sa bawat oras hanggang
sa wakas pindutin ang dulo ng listahan.

434
00:22:41,920 --> 00:22:45,030
At alam mo na walang mga
higit pang mga node sa paghahanap sa pamamagitan ng,

435
00:22:45,030 --> 00:22:47,999
at pagkatapos ay maaari kang bumalik false
dahil alam mo na, oh, well,

436
00:22:47,999 --> 00:22:50,540
kung ako ay ma-search
sa pamamagitan ng kabuuan ng listahan.

437
00:22:50,540 --> 00:22:54,530
Kung sa halimbawang ito, kung nais ko
upang hanapin ang halaga ng 10,

438
00:22:54,530 --> 00:22:57,250
at sisimulan ko sa ulo, at
Ako sa paghahanap ng lahat ng mga paraan down,

439
00:22:57,250 --> 00:23:00,550
at sa huli nakuha ko na ito, kung saan
isang pointer na tumuturo sa null,

440
00:23:00,550 --> 00:23:04,415
Alam ko na, crap, hulaan ko 10 ay wala sa
ang listahan na ito dahil hindi ko mahanap ang mga ito.

441
00:23:04,415 --> 00:23:06,520
At ako sa dulo ng listahan.

442
00:23:06,520 --> 00:23:11,040
At sa kaso na kilala mo
Pupunta ako sa bumalik false.

443
00:23:11,040 --> 00:23:12,900
>> Hayaan na magbabad sa para sa ilang sandali.

444
00:23:12,900 --> 00:23:17,350
Ito ang magiging pretty
mahalaga para sa iyong pset.

445
00:23:17,350 --> 00:23:21,140
Ang lohika ng mga ito ay napaka-simple, marahil
syntactically lang ang pagpapatupad nito.

446
00:23:21,140 --> 00:23:23,365
Gusto mong guys na gumawa
tiyakin na iyong naiintindihan.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Cool.

449
00:23:27,650 --> 00:23:32,560
>> OK, kaya kung paano kami ay magiging
pagpasok nodes, kanan,

450
00:23:32,560 --> 00:23:35,380
sa isang listahan dahil tandaan
ano ang mga ano ang mga benepisyo

451
00:23:35,380 --> 00:23:39,230
ng pagkakaroon ng isang listahan ng mga link na laban
isang array sa mga tuntunin ng imbakan?

452
00:23:39,230 --> 00:23:41,110
>> Madla: Ito ay dynamic,
kaya mas madaling to--

453
00:23:41,110 --> 00:23:43,180
>> ANDI PENG: Eksakto,
kaya dynamic, na

454
00:23:43,180 --> 00:23:46,880
ay nangangahulugan na maaari itong palawakin at pag-urong
depende sa mga pangangailangan ng gumagamit.

455
00:23:46,880 --> 00:23:56,570
At ito, sa puntong ito, hindi namin kailangan
mag-aksaya ng mga hindi kailangan na memory dahil ako

456
00:23:56,570 --> 00:24:00,850
kung hindi ko alam kung gaano karaming mga halaga ko gusto
sa store, ito ay hindi magkaroon ng kahulugan para sa akin

457
00:24:00,850 --> 00:24:04,310
upang lumikha ng isang array dahil
kung gusto kong mag-imbak 10 halaga

458
00:24:04,310 --> 00:24:08,380
at gumawa ako ng isang array ng 1000, na ang
isang pulutong ng mga nasayang na memorya, na inilaan.

459
00:24:08,380 --> 00:24:11,180
Iyon ang dahilan kung bakit gusto naming gamitin ang isang naka-link
list para ma-dynamically

460
00:24:11,180 --> 00:24:13,860
baguhin o pag-urong ng aming laki.

461
00:24:13,860 --> 00:24:17,040
>> At kaya na gumagawa ng insertion
ng kaunti pang kumplikado.

462
00:24:17,040 --> 00:24:20,810
Dahil hindi namin sapalarang maaaring ma-access na mga elemento
ang paraan na gusto naming ng isang array.

463
00:24:20,810 --> 00:24:24,270
Kung gusto kong ipasok ang isang elemento
sa ikapitong index,

464
00:24:24,270 --> 00:24:26,930
Ko lamang maaari itong ipasok
sa ikapitong index.

465
00:24:26,930 --> 00:24:30,020
Sa isang naka-link na listahan, ito ay hindi
lubos na magtrabaho bilang madali,

466
00:24:30,020 --> 00:24:34,947
at kaya kung gusto naming ipasok
ang isa dito sa naka-link na listahan,

467
00:24:34,947 --> 00:24:36,280
biswal, ito ay tunay madali upang makita.

468
00:24:36,280 --> 00:24:39,363
Gusto lang namin na ipasok ito doon,
karapatan sa simula ng listahan,

469
00:24:39,363 --> 00:24:40,840
karapatan pagkatapos ulo.

470
00:24:40,840 --> 00:24:44,579
>> Ngunit ang paraan na kung saan mayroon kaming upang muling italaga
ang mga payo ay isang bit convoluted

471
00:24:44,579 --> 00:24:47,620
o, lohikal, ito ang akma, ngunit
Gusto mong tiyakin na mayroon ka nito

472
00:24:47,620 --> 00:24:50,250
ganap down dahil
ang huling bagay na gusto mo

473
00:24:50,250 --> 00:24:52,990
ay upang muling italaga ang isang pointer sa
paraan na ginagawa namin dito.

474
00:24:52,990 --> 00:24:58,170
Kung ikaw dereference ang
pointer mula sa ulo sa 1,

475
00:24:58,170 --> 00:25:01,086
at pagkatapos ang lahat ng isang biglaang ang
natitirang bahagi ng iyong listahan ng mga link

476
00:25:01,086 --> 00:25:04,680
ay nawala dahil hindi mo pa talaga
lumikha ng isang pansamantalang kahit ano.

477
00:25:04,680 --> 00:25:06,220
Iyan ay itinuturo sa 2.

478
00:25:06,220 --> 00:25:10,080
Kung muling italaga mo ang pointer, at pagkatapos ay ang
natitirang bahagi ng iyong listahan ay ganap na nawala.

479
00:25:10,080 --> 00:25:13,310
Kaya nais mong maging
tunay, tunay maingat dito

480
00:25:13,310 --> 00:25:17,010
sa unang magtalaga ng
pointer mula sa anumang ikaw

481
00:25:17,010 --> 00:25:20,150
nais na ipasok sa kahit saan
gusto mo, at pagkatapos ay sa iyo

482
00:25:20,150 --> 00:25:22,710
Maaari dereference ang natitirang bahagi ng iyong listahan.

483
00:25:22,710 --> 00:25:25,250
>> Kaya ito ay naaangkop para sa kahit saan
sinusubukan mong ipasok sa.

484
00:25:25,250 --> 00:25:27,520
Kung nais mong ipasok sa
ulo, kung gusto mong sagutin dito,

485
00:25:27,520 --> 00:25:29,455
kung gusto mong ipasok sa
Sa katapusan, na rin, ang katapusan ko

486
00:25:29,455 --> 00:25:30,910
hulaan gagawin mo lang
walang pointer, ngunit ikaw

487
00:25:30,910 --> 00:25:33,830
nais na tiyakin na hindi mo
mawala ang natitirang bahagi ng iyong listahan.

488
00:25:33,830 --> 00:25:36,640
Gusto mong palaging upang tiyakin
ang iyong bagong node ay tumuturo

489
00:25:36,640 --> 00:25:39,330
patungo sa kahit anong ka
nais na ipasok sa,

490
00:25:39,330 --> 00:25:42,170
at pagkatapos ay maaari mong idagdag ang pagdudugtong pa.

491
00:25:42,170 --> 00:25:43,330
Ang bawat malinaw?

492
00:25:43,330 --> 00:25:45,427
>> Ito ay magiging
ang isa sa mga tunay na mga isyu.

493
00:25:45,427 --> 00:25:48,010
Isa sa mga pinaka pangunahing isyu
ikaw ay pagpunta sa may sa iyong pset

494
00:25:48,010 --> 00:25:51,340
ay na kayo ay pagpunta sa subukan upang lumikha ng
isang listahan ng mga link at insert bagay

495
00:25:51,340 --> 00:25:53,340
ngunit pagkatapos ay mawawala lamang ang
natitirang bahagi ng iyong listahan ng naka-link.

496
00:25:53,340 --> 00:25:54,900
At ikaw ay pagpunta sa maging tulad ng, ako ay
hindi alam kung bakit ito ang nangyayari?

497
00:25:54,900 --> 00:25:58,040
At ito ay isang sakit upang pumunta sa pamamagitan ng
at hanapin ang lahat ng iyong mga payo.

498
00:25:58,040 --> 00:26:02,100
>> At ginagarantiya ko sa iyo na ito sa pset,
pagsulat at pagguhit ng mga nodes out

499
00:26:02,100 --> 00:26:03,344
ay tunay, tunay na kapaki-pakinabang.

500
00:26:03,344 --> 00:26:06,010
Kaya maaari mong ganap na subaybayan
ng kung saan ang lahat ng iyong mga payo ay,

501
00:26:06,010 --> 00:26:08,540
ano ang pagpunta mali,
na kung saan ang lahat ng iyong mga nodes ay,

502
00:26:08,540 --> 00:26:12,660
kung ano ang kailangan mong gawin upang ma-access o
ipasok o tanggalin o anuman sa mga ito.

503
00:26:12,660 --> 00:26:14,550
Ang bawat mabuting may na?

504
00:26:14,550 --> 00:26:15,050
Cool.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Kaya kung nais namin na tingnan ang code?

507
00:26:22,600 --> 00:26:24,470
Oh, hindi ko alam kung kami
maaaring makita the-- OK, kaya

508
00:26:24,470 --> 00:26:27,940
sa tuktok ng lahat ng ito ay isang function
pinangalanan insert kung saan nais namin

509
00:26:27,940 --> 00:26:31,365
upang ipasok int n sa mga naka-link na listahan.

510
00:26:31,365 --> 00:26:32,740
Kami ay pagpunta sa paglalakad sa pamamagitan ng mga ito.

511
00:26:32,740 --> 00:26:34,770
Ito ay isang pulutong ng mga code, ang isang pulutong ng mga bagong syntax.

512
00:26:34,770 --> 00:26:36,220
Babalik kami OK.

513
00:26:36,220 --> 00:26:39,120
>> Kaya up sa tuktok, sa tuwing
nais namin na lumikha ng anumang bagay

514
00:26:39,120 --> 00:26:42,380
kung ano ang kailangan namin upang gawin, lalo na kung ikaw
gusto hindi ito na naka-imbak sa stack

515
00:26:42,380 --> 00:26:43,920
ngunit sa magbunton?

516
00:26:43,920 --> 00:26:45,460
Pumunta kami sa isang malloc, di ba?

517
00:26:45,460 --> 00:26:48,240
Kaya kami ay pagpunta upang lumikha ng isang pointer.

518
00:26:48,240 --> 00:26:52,074
Node, pointer, bagong equals
malloc ang laki ng isang node

519
00:26:52,074 --> 00:26:53,740
dahil gusto naming na node na nilikha.

520
00:26:53,740 --> 00:26:56,720
Gusto naming ang dami ng
memory na ang isang node ay tumatagal ng hanggang

521
00:26:56,720 --> 00:26:59,300
na inilaan para sa
paglikha ng mga bagong node.

522
00:26:59,300 --> 00:27:02,270
>> At pagkatapos kami ay pagpunta upang suriin upang
makita kung ang bagong equals katumbas null.

523
00:27:02,270 --> 00:27:03,370
Tandaan kung ano ang sinabi namin?

524
00:27:03,370 --> 00:27:06,470
Anuman ang malloc,
kung ano ang dapat mo rin itong gawin?

525
00:27:06,470 --> 00:27:09,490
Dapat mong palaging suriin upang makita
kung o hindi na null.

526
00:27:09,490 --> 00:27:13,620
>> Halimbawa, kung ang iyong mga operating
sistema ay ganap na puno na,

527
00:27:13,620 --> 00:27:17,060
kung ikaw ay walang higit pang memory sa
lahat at mong subukan na malloc,

528
00:27:17,060 --> 00:27:18,410
ito ay bumalik null para sa iyo.

529
00:27:18,410 --> 00:27:21,094
At kaya kung sinubukan mong gamitin ito
kapag ito ay tumuturo sa null,

530
00:27:21,094 --> 00:27:23,260
Hindi ka pagpunta sa ma
upang ma-access ang impormasyon na iyon.

531
00:27:23,260 --> 00:27:27,010
At kaya dahil dito, gusto naming gawing
Siguraduhin na kapag ikaw ay mallocing,

532
00:27:27,010 --> 00:27:30,500
lagi ka check upang makita kung
na memory na ibinigay sa iyo ay null.

533
00:27:30,500 --> 00:27:33,670
At kung ito ay hindi, pagkatapos ay maaari naming ilipat
sa sa mga natitirang bahagi ng aming code.

534
00:27:33,670 --> 00:27:36,140
>> Kaya kami ay pagpunta sa
magpasimula ng bagong node.

535
00:27:36,140 --> 00:27:39,050
Kami ay pagpunta sa gawin ang mga bagong n ay katumbas ng n.

536
00:27:39,050 --> 00:27:42,390
At pagkatapos kami ay pagpunta sa gawin
itakda ang bagong mga pointer sa bagong

537
00:27:42,390 --> 00:27:46,900
sa null dahil sa ngayon ay hindi kami
gusto anumang bagay para sa mga ito upang tumuro sa.

538
00:27:46,900 --> 00:27:48,755
Wala kaming ideya kung saan
ito ay pagpunta sa ilagay mo,

539
00:27:48,755 --> 00:27:50,630
at pagkatapos ay kung nais nating
ipasok ito sa ulo,

540
00:27:50,630 --> 00:27:53,820
pagkatapos ay maaari naming muling italaga
ang pointer sa ulo.

541
00:27:53,820 --> 00:27:58,530
Lahat ng tao sundin ba ang logic
ng kung saan na ang nangyayari?

542
00:27:58,530 --> 00:28:02,502
>> Lahat ng aming ginagawa ay ang paglikha ng isang bagong
node, ang pagtatakda ng pointer na null,

543
00:28:02,502 --> 00:28:04,210
at pagkatapos reassigning
ito sa ulo kung tayo

544
00:28:04,210 --> 00:28:06,320
alam gusto naming ipasok ito sa ulo.

545
00:28:06,320 --> 00:28:09,420
At pagkatapos ay ang ulo ay pagpunta sa
point patungo na ang mga bagong node.

546
00:28:09,420 --> 00:28:11,060
Ang bawat ok na?

547
00:28:11,060 --> 00:28:12,380
>> Kaya ito ay isang proseso na may dalawang hakbang.

548
00:28:12,380 --> 00:28:14,760
Mayroon kayong na unang magtalaga
kahit anong lumilikha ka.

549
00:28:14,760 --> 00:28:18,260
Itakda na pointer sa
isangguni, at pagkatapos ay sa iyo

550
00:28:18,260 --> 00:28:21,400
Maaari uri ng dereference
ang unang pointer

551
00:28:21,400 --> 00:28:22,972
at ituro ito patungo sa bagong node.

552
00:28:22,972 --> 00:28:25,680
Hangga't gusto mong ipasok ito,
na logic ay pagpunta sa hold totoo.

553
00:28:25,680 --> 00:28:27,530
>> Ito ay uri ng tulad ng pagtatalaga
pansamantalang variable.

554
00:28:27,530 --> 00:28:28,700
Tandaan, nakuha mo na
tiyakin na ikaw ay

555
00:28:28,700 --> 00:28:30,346
huwag mawala sa pagsubaybay ng kung ikaw ay pagpapalit.

556
00:28:30,346 --> 00:28:33,470
Gusto mong tiyakin na ikaw ay may isang
pansamantalang variable na uri ng mapigil

557
00:28:33,470 --> 00:28:35,620
subaybayan kung saan bagay na
ay naka-imbak sa gayon ay ikaw

558
00:28:35,620 --> 00:28:41,190
huwag mawalan ng anumang mga halaga sa kurso
ng mga tulad ng panggugulo sa paligid sa mga ito.

559
00:28:41,190 --> 00:28:42,710
>> OK, kaya ang code ay magiging dito.

560
00:28:42,710 --> 00:28:45,020
Ikaw guys kumuha ng isang pagtingin pagkatapos ng seksyon.

561
00:28:45,020 --> 00:28:48,060
Ito ay magiging doon.

562
00:28:48,060 --> 00:28:50,280
>> Kaya ako hulaan kung paano gumagana ang
ito ay naiiba na kung gusto naming

563
00:28:50,280 --> 00:28:52,300
upang ipasok sa gitna o sa dulo?

564
00:28:52,300 --> 00:28:57,892
Kahit sino ay may isang ideya ng kung ano ang mga
pseudocode bilang ang lohikal na reference

565
00:28:57,892 --> 00:29:00,350
na kami ay kumuha ng kung gusto naming
ipasok ito sa gitna?

566
00:29:00,350 --> 00:29:03,391
Kaya kung gusto naming upang ipasok ito sa
head, ang lahat ng aming gagawin ay lumikha ng isang bagong node.

567
00:29:03,391 --> 00:29:06,311
Itinakda namin ang pointer ng na
bagong node sa ano man ang ulo,

568
00:29:06,311 --> 00:29:08,310
at pagkatapos ay itakda natin ang ulo
sa bagong node, di ba?

569
00:29:08,310 --> 00:29:11,560
Kung gusto naming upang ipasok ito sa gitna
ng listahan, kung ano ang kailangan nating gawin?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> Madla: Ito ay pa rin
maging isang katulad na proseso

572
00:29:16,110 --> 00:29:19,114
ng mga tulad ng pagtatalaga ng pointer at
pagkatapos ay nagtatalaga na pointer,

573
00:29:19,114 --> 00:29:20,530
ngunit kami ay may sa mahanap doon.

574
00:29:20,530 --> 00:29:23,560
>> ANDI PENG: Eksakto, kaya eksakto
ang parehong proseso maliban sa iyo

575
00:29:23,560 --> 00:29:27,820
kung hanapin kung saan ang eksaktong ikaw
gusto na ang mga bagong pointer upang pumunta sa,

576
00:29:27,820 --> 00:29:44,790
kaya kung gusto kong ipasok sa
sa gitna ng naka-link list-- OK,

577
00:29:44,790 --> 00:29:46,370
sabihin natin na ang aming listahan na naka-link.

578
00:29:46,370 --> 00:29:49,500
Kung nais namin na ipasok ito dito mismo,
kami ay pagpunta upang lumikha ng isang bagong node.

579
00:29:49,500 --> 00:29:50,520
Kami ay pagpunta sa malloc.

580
00:29:50,520 --> 00:29:52,220
Kami ay pagpunta upang lumikha ng isang bagong node.

581
00:29:52,220 --> 00:29:55,940
Kami ay pagpunta sa italaga ang
pointer ng node dito.

582
00:29:55,940 --> 00:29:58,335
>> Ngunit ang problema na naiiba
mula sa kung saan ang ulo ay

583
00:29:58,335 --> 00:30:00,490
ay na namin alam ang eksaktong
kung saan ang ulo ay.

584
00:30:00,490 --> 00:30:01,930
Ito ay karapatan sa unang, tama?

585
00:30:01,930 --> 00:30:04,870
Ngunit dito namin nakuha upang subaybayan
ng kung saan kami ay pagpasok ito sa.

586
00:30:04,870 --> 00:30:07,930
Kung kami ay pagpasok ng aming
node dito, mayroon ka namin

587
00:30:07,930 --> 00:30:12,270
tiyakin na ang mga
isang nakaraang sa node

588
00:30:12,270 --> 00:30:14,172
ay ang isa na reassigns ang pointer.

589
00:30:14,172 --> 00:30:16,380
Kaya pagkatapos ninyong mag-uri ng
subaybayan ng dalawang bagay.

590
00:30:16,380 --> 00:30:19,420
Kapag patuloy mong subaybayan ng kung saan ito
node ay kasalukuyang pagpasok sa.

591
00:30:19,420 --> 00:30:23,280
Mayroon ka ding upang subaybayan kung saan
ang nakaraang node na ikaw ay naghahanap sa

592
00:30:23,280 --> 00:30:24,340
ay naroon din.

593
00:30:24,340 --> 00:30:25,830
Ang bawat mabuting may na?

594
00:30:25,830 --> 00:30:26,500
SIGE.

595
00:30:26,500 --> 00:30:28,000
>> Paano ang tungkol sa pagpasok sa dulo?

596
00:30:28,000 --> 00:30:34,220
Kung Nais kong idagdag ito here-- kung nais ko
upang magdagdag ng bagong node sa dulo ng isang listahan,

597
00:30:34,220 --> 00:30:37,009
paano ko maaaring pumunta tungkol sa paggawa na?

598
00:30:37,009 --> 00:30:39,300
Madla: Kaya sa kasalukuyan, ang mga
matulis huling isa upang null.

599
00:30:39,300 --> 00:30:40,960
ANDI PENG: Oo.

600
00:30:40,960 --> 00:30:43,560
Eksakto, kaya ang isang ito
kasalukuyan ay itinuturo na malaman,

601
00:30:43,560 --> 00:30:46,720
at upang hulaan ko, sa ganitong kahulugan, ito ay
madali upang magdagdag ng hanggang sa dulo ng isang listahan.

602
00:30:46,720 --> 00:30:51,810
Ang kailangan mong gawin ay itakda ito
katumbas ng null at pagkatapos ay biglang lumakas.

603
00:30:51,810 --> 00:30:53,070
Right doon, napakadaling.

604
00:30:53,070 --> 00:30:53,960
Very simple.

605
00:30:53,960 --> 00:30:56,430
>> Na halos kapareho sa
ulo, ngunit lohikal iyo

606
00:30:56,430 --> 00:30:59,690
nais na tiyakin na ang mga hakbang
magdadala sa iyo patungo sa paggawa sa alinman sa mga ito,

607
00:30:59,690 --> 00:31:01,500
ikaw ay sumusunod sa kahabaan.

608
00:31:01,500 --> 00:31:04,420
Ito ay napakadaling, sa gitna
ng iyong code, mahuli up sa,

609
00:31:04,420 --> 00:31:05,671
oh, Mayroon akong kaya maraming mga payo.

610
00:31:05,671 --> 00:31:07,461
Hindi ko alam kung saan
anumang bagay ay tumuturo sa.

611
00:31:07,461 --> 00:31:09,170
Hindi ko kahit na malaman kung aling mga node on ako.

612
00:31:09,170 --> 00:31:11,490
Ano ang nangyayari?

613
00:31:11,490 --> 00:31:13,620
>> Mamahinga, tahimik na, huminga nang malalim.

614
00:31:13,620 --> 00:31:15,530
Gumuhit ang iyong listahan ng naka-link.

615
00:31:15,530 --> 00:31:18,800
Kung sinasabi mo, alam ko na kung saan ang eksaktong
Kailangan ko bang ipasok ito sa

616
00:31:18,800 --> 00:31:22,970
at alam ko nang eksakto kung paano muling italaga ang aking
mga payo, magkano, mas madali na larawan

617
00:31:22,970 --> 00:31:27,200
out-- much, lubhang mas madaling hindi
mawala sa bugs ng iyong code.

618
00:31:27,200 --> 00:31:29,410
Ang bawat ok na?

619
00:31:29,410 --> 00:31:31,380
SIGE.

620
00:31:31,380 --> 00:31:35,120
>> Kaya ako hulaan ang isang konsepto na kami ay hindi
talagang usapan tungkol sa bago ngayon,

621
00:31:35,120 --> 00:31:38,131
at ako hulaan ikaw ay malamang na
hindi makaharap marami yet--

622
00:31:38,131 --> 00:31:40,880
ito ay uri ng isang advanced concept--
ay na namin talagang magkaroon ng isang data

623
00:31:40,880 --> 00:31:43,900
istraktura na tinatawag na isang doble-link na listahan.

624
00:31:43,900 --> 00:31:46,390
Kaya bilang maaari mong makita ang isang lalaki,
lahat ng aming ginagawa ay ang paglikha

625
00:31:46,390 --> 00:31:50,400
isang aktwal na halaga, ng dagdag na
pointer sa bawat isa sa aming mga nodes

626
00:31:50,400 --> 00:31:52,660
na din ang mga puntos sa nakaraang node.

627
00:31:52,660 --> 00:31:58,170
Kaya hindi lamang ang mayroon namin ang aming mga
nodes point sa susunod na isa.

628
00:31:58,170 --> 00:32:01,430
Sila din point sa isang nakaraan.

629
00:32:01,430 --> 00:32:04,310
Pupunta ako upang huwag pansinin ito ng dalawang ngayon.

630
00:32:04,310 --> 00:32:06,740
>> Kaya nga ikaw ay may isang kadena
na maaaring ilipat sa parehong paraan,

631
00:32:06,740 --> 00:32:09,630
at pagkatapos ay ito ay isang bit mas madali
lohikal na sundin kasama.

632
00:32:09,630 --> 00:32:11,896
Tulad dito, sa halip ng
pagpapanatili ng track ng, oh, ako

633
00:32:11,896 --> 00:32:14,520
kung alam na ito node ay
ang isa na kailangan kong muling italaga,

634
00:32:14,520 --> 00:32:17,532
Maaari ba akong pumunta lang dito at
lamang pull sa nakaraang.

635
00:32:17,532 --> 00:32:19,490
Pagkatapos ako kung saan
iyon ay, at pagkatapos ay sa iyo

636
00:32:19,490 --> 00:32:21,130
Hindi mo na kailangang tawirin ang
kabuuan ng mga naka-link na listahan.

637
00:32:21,130 --> 00:32:22,180
Ito ay isang bit mas madali.

638
00:32:22,180 --> 00:32:24,960
>> Ngunit dahil dito, mayroon kang doble
ang dami ng mga payo,

639
00:32:24,960 --> 00:32:26,960
na double ang halaga ng memorya.

640
00:32:26,960 --> 00:32:28,950
Ito ay isang pulutong ng mga payo upang subaybayan.

641
00:32:28,950 --> 00:32:32,140
Ito ay isang bit mas kumplikado, ngunit ito ay
ng kaunti pang user friendly depende

642
00:32:32,140 --> 00:32:34,080
sa kung ano ang sinusubukan mong makamit.

643
00:32:34,080 --> 00:32:36,910
>> Kaya ito uri ng data
istraktura ganap na umiiral,

644
00:32:36,910 --> 00:32:40,280
at ang istraktura para sa ay tunay, tunay
simple maliban sa lahat nagkakaroon ka ay,

645
00:32:40,280 --> 00:32:43,850
sa halip ng isang pointer lang sa susunod,
ikaw din ay mayroong isang pointer sa nakaraang.

646
00:32:43,850 --> 00:32:45,940
Iyan na ang lahat ng mga pagkakaiba ay.

647
00:32:45,940 --> 00:32:47,740
Ang bawat mabuting may na?

648
00:32:47,740 --> 00:32:48,240
Cool.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Lahat ng karapatan, kaya ngayon ako
na talagang gastusin marahil

651
00:32:53,280 --> 00:32:56,870
tulad ng 15 hanggang 20 minuto o ang bulk
mga natitirang bahagi ng oras sa seksyon

652
00:32:56,870 --> 00:32:58,360
pakikipag-usap tungkol hash talahanayan.

653
00:32:58,360 --> 00:33:02,590
Ilan sa inyo guys
nabasa pset5 spec?

654
00:33:02,590 --> 00:33:03,620
Lahat ng mga karapatan, mabuti.

655
00:33:03,620 --> 00:33:06,160
Iyan ay mas mataas kaysa sa 50% ng normal.

656
00:33:06,160 --> 00:33:07,560
Ito ay OK.

657
00:33:07,560 --> 00:33:10,345
>> Kaya bilang ka guys ay makita,
ikaw ay hamon sa pset5

658
00:33:10,345 --> 00:33:16,790
ay upang ipatupad ang isang diksiyunaryo
kung saan nag-load ng higit sa 140,000 mga salita

659
00:33:16,790 --> 00:33:20,610
na bigyan ka namin at pagtiyak ng pagbaybay
ito laban sa lahat ng mga teksto.

660
00:33:20,610 --> 00:33:22,580
Bibigyan ka namin ng random
mga piraso ng panitikan.

661
00:33:22,580 --> 00:33:23,520
Bibigyan ka namin ng Odyssey Ang.

662
00:33:23,520 --> 00:33:24,561
Bibigyan ka namin ng The Iliad.

663
00:33:24,561 --> 00:33:26,350
Bibigyan ka namin ng Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> At ang iyong mga hamon
ay i-spell check

665
00:33:28,220 --> 00:33:31,760
bawat solong salita sa lahat
ng mga diksyunaryo

666
00:33:31,760 --> 00:33:34,960
mahalagang sa aming spell checker.

667
00:33:34,960 --> 00:33:38,620
At kaya mayroong ilang mga bahagi
ng paglikha ng mga ito pset,

668
00:33:38,620 --> 00:33:41,970
unang gusto mong maging
able sa tunay na-load

669
00:33:41,970 --> 00:33:43,970
lahat ng mga salita sa iyong
diksyonaryo, at pagkatapos ay sa iyo

670
00:33:43,970 --> 00:33:45,530
nais na ma-
spell-check ang lahat ng mga ito.

671
00:33:45,530 --> 00:33:48,780
At kaya dahil dito, ikaw ay pagpunta sa nangangailangan
isang istraktura ng data na maaaring gawin ito mabilis

672
00:33:48,780 --> 00:33:50,790
at mahusay at pabago-bago.

673
00:33:50,790 --> 00:33:52,900
>> Kaya ipagpalagay ko ang pinakamadaling
paraan upang gawin ito, ikaw

674
00:33:52,900 --> 00:33:55,010
ay malamang na lumikha ng isang array, di ba?

675
00:33:55,010 --> 00:33:58,910
Ang pinakamadaling paraan ng imbakan ay sa iyo
ay maaaring lumikha ng isang hanay ng mga 140,000 mga salita

676
00:33:58,910 --> 00:34:03,400
at ilagay lamang ang mga ito ang lahat doon at
pagkatapos bagtasin ang mga ito sa pamamagitan ng paghahanap ng binary

677
00:34:03,400 --> 00:34:06,780
o sa pamamagitan ng pagpili, o not--
Paumanhin na pag-uuri.

678
00:34:06,780 --> 00:34:10,729
Maaari mong ayusin ang mga ito at pagkatapos bagtasin ang mga ito
sa pamamagitan ng binary paghahanap o lamang linear paghahanap

679
00:34:10,729 --> 00:34:13,730
at lamang huling mga salita, ngunit na
tumatagal ng isang malaking halaga ng memorya,

680
00:34:13,730 --> 00:34:15,190
at ito ay hindi masyadong mahusay.

681
00:34:15,190 --> 00:34:18,350
>> At kaya kami ay pagpunta sa simulan
pakikipag-usap tungkol sa mga paraan ng paggawa ng

682
00:34:18,350 --> 00:34:20,110
mas mahusay ang aming mga oras na tumatakbo.

683
00:34:20,110 --> 00:34:23,190
At ang aming layunin ay upang makakuha ng
pare-pareho ang mga oras kung saan

684
00:34:23,190 --> 00:34:25,810
ito ay halos tulad array, kung saan
mayroon kang madalian access.

685
00:34:25,810 --> 00:34:28,560
Kung gusto ko upang maghanap para sa anumang bagay,
Gusto ko na ma-lamang,

686
00:34:28,560 --> 00:34:30,810
boom, hanapin ito eksakto, at bunutin ito.

687
00:34:30,810 --> 00:34:34,100
At kaya isang kaayusan kung saan
makikita ay nagiging kami masyadong malapit

688
00:34:34,100 --> 00:34:37,569
upang ma-access ang constant
panahon, ang banal na Kopita

689
00:34:37,569 --> 00:34:41,370
sa programming ng pare-pareho
oras ay tinatawag na isang hash table.

690
00:34:41,370 --> 00:34:45,370
At kaya David naunang nabanggit ang
[Hindi marinig] nang kaunti sa panayam,

691
00:34:45,370 --> 00:34:49,100
ngunit kami ay pagpunta sa tunay
dive sa malalim na ngayong linggo

692
00:34:49,100 --> 00:34:51,780
sa isang piraso na patungkol
kung paano ang isang hash table.

693
00:34:51,780 --> 00:34:53,949
>> Kaya ang paraan na ang isang hash
gawa table, halimbawa,

694
00:34:53,949 --> 00:35:00,230
kung nais ko upang mag-imbak ng grupo ng mga salita, ang isang
grupo ng mga salita sa wikang Ingles,

695
00:35:00,230 --> 00:35:02,940
Kaya kong theoretically ilagay
banana, apple, kiwi, mangga, pair,

696
00:35:02,940 --> 00:35:04,980
at milong bilog lahat sa isang array.

697
00:35:04,980 --> 00:35:07,044
Maaari nilang lahat magkasya sa at maaaring mahanap.

698
00:35:07,044 --> 00:35:09,210
Gusto Ito ay uri ng isang sakit na
paghahanap sa pamamagitan ng at pag-access,

699
00:35:09,210 --> 00:35:12,920
ngunit ang mga mas madaling paraan ng paggawa nito ay
na maaari naming lumikha talagang isang istraktura

700
00:35:12,920 --> 00:35:15,680
tinatawag na isang hash table kung saan namin hash.

701
00:35:15,680 --> 00:35:19,880
Nagpapatakbo kami ng lahat ng aming mga key sa pamamagitan
sumira ng isang function, isang equation,

702
00:35:19,880 --> 00:35:22,600
na lumiliko silang lahat sa
ilang uri ng mga halaga ng isang

703
00:35:22,600 --> 00:35:28,740
na pagkatapos ay maaari naming mag-imbak papunta
mahalagang isang hanay ng mga naka-link na listahan.

704
00:35:28,740 --> 00:35:32,570
>> At kaya dito, kung gusto naming
sa tindahan ng mga salitang Ingles,

705
00:35:32,570 --> 00:35:37,250
maaari namin potensyal na lang, hindi ako
alam, i-lahat ang mga unang titik

706
00:35:37,250 --> 00:35:39,630
sa ilang mga uri ng isang numero.

707
00:35:39,630 --> 00:35:43,140
At kaya, halimbawa, kung nais ko
A na magkasingkahulugan sa apple--

708
00:35:43,140 --> 00:35:47,460
o sa index ng 0, at
B na magkasingkahulugan sa 1,

709
00:35:47,460 --> 00:35:51,030
maaari kaming magkaroon ng 26 mga entry
na maaari lamang mag-imbak

710
00:35:51,030 --> 00:35:53,610
lahat ng mga titik ng
alpabeto na kami ay magsimula sa.

711
00:35:53,610 --> 00:35:56,130
At pagkatapos ay maaari kaming magkaroon ng
apple sa index ng 0.

712
00:35:56,130 --> 00:35:59,160
Maaari naming magkaroon ng banana sa index ng
1, milong bilog sa index ng 2,

713
00:35:59,160 --> 00:36:00,540
at iba pa.

714
00:36:00,540 --> 00:36:04,460
At kaya kung gusto ko upang maghanap
aking hash table at pag-access ng mansanas,

715
00:36:04,460 --> 00:36:07,560
Alam ko nagsisimula mansanas na may
isang A, at alam ko nang eksakto

716
00:36:07,560 --> 00:36:10,860
na ito ay dapat at ang hash
talahanayan sa index 0 dahil

717
00:36:10,860 --> 00:36:13,620
ng pag-andar na dating nakatalaga.

718
00:36:13,620 --> 00:36:16,572
>> Kaya hindi ko alam, tayo
isang programa kung saan ang user

719
00:36:16,572 --> 00:36:18,780
sisingilin ka na may
arbitrarily-- hindi nagkataon,

720
00:36:18,780 --> 00:36:22,530
sa sinusubukan na thoughtfully
mag-isip ng mabuti equation

721
00:36:22,530 --> 00:36:25,460
para ma-kumalat
ang lahat ng iyong mga halaga

722
00:36:25,460 --> 00:36:29,370
sa isang paraan na maaari nilang madaling ma-access
ito sa susunod na may tulad ng isang equation

723
00:36:29,370 --> 00:36:31,130
na ikaw, ang iyong sarili, malaman.

724
00:36:31,130 --> 00:36:35,210
Kaya sa kamalayan kung Nais kong pumunta sa
mangga, alam ko, oh, ito ay nagsisimula sa m.

725
00:36:35,210 --> 00:36:37,134
Ito ay dapat na sa index ng 12.

726
00:36:37,134 --> 00:36:38,800
Hindi ko na kailangang maghanap sa pamamagitan ng kahit ano.

727
00:36:38,800 --> 00:36:42,080
Alam ko exactly-- maaari kong pumunta lamang sa
ang index ng 12 at hilahin na out.

728
00:36:42,080 --> 00:36:45,520
>> Ang bawat malinaw sa kung paano ang isang
gumagana hash talahanayan?

729
00:36:45,520 --> 00:36:48,380
Ito ay uri ng lamang ng isang mas kumplikadong array.

730
00:36:48,380 --> 00:36:50,010
Iyan na ang lahat ng ito ay.

731
00:36:50,010 --> 00:36:51,630
SIGE.

732
00:36:51,630 --> 00:36:57,690
>> Kaya ako hulaan namin tumakbo sa
ang isyu na ito ng kung ano ang

733
00:36:57,690 --> 00:37:06,390
ang mangyayari kung mayroon kang maramihang mga bagay-bagay
na magbibigay sa iyo ng parehong index?

734
00:37:06,390 --> 00:37:10,570
Kaya sinasabi ng aming mga function, ang lahat ng ito
ginawa ay gawin na ang unang titik

735
00:37:10,570 --> 00:37:14,490
at turn na sa isang
kani 0 hanggang 25 index.

736
00:37:14,490 --> 00:37:17,137
Iyan ay lubos na multa kung
magkaroon ng isa sa bawat ka lamang.

737
00:37:17,137 --> 00:37:18,970
Ngunit ang pangalawang simulan mo
pagkakaroon ng mas maraming, ikaw ay

738
00:37:18,970 --> 00:37:20,910
pagpunta sa may kung ano ang tinatawag na isang banggaan.

739
00:37:20,910 --> 00:37:25,580
>> Kaya kung sinusubukan kong ipasok ibaon sa isang hash
mesa na mayroon ng banana sa mga ito,

740
00:37:25,580 --> 00:37:27,870
kung ano ang nangyayari sa mangyayari kapag
subukan mong ipasok na?

741
00:37:27,870 --> 00:37:30,930
Bad bagay dahil saging
Umiiral na sa loob ng index

742
00:37:30,930 --> 00:37:33,800
na nais mong i-imbak ang mga ito sa.

743
00:37:33,800 --> 00:37:35,560
Berry uri ng ay tulad ng, ah, kung ano ang gagawin ko?

744
00:37:35,560 --> 00:37:37,080
Hindi ko alam kung saan pupunta.

745
00:37:37,080 --> 00:37:38,410
Paano ko malutas ito?

746
00:37:38,410 --> 00:37:41,150
>> At kaya ka guys ay uri ng
makita ang ginagawa namin ito mapaglalang bagay

747
00:37:41,150 --> 00:37:44,810
kung saan maaari naming uri ng aktwal na
lumikha ng listahan ng mga link sa aming mga array.

748
00:37:44,810 --> 00:37:46,840
At kaya ang pinakamadaling paraan
mag-isip tungkol sa mga ito,

749
00:37:46,840 --> 00:37:50,830
lahat ng hash table ay isang
ang dami ng mga naka-link na mga listahan.

750
00:37:50,830 --> 00:37:55,670
At ito, sa kamalayan na, mayroon kang
ito maganda ang dami ng mga payo,

751
00:37:55,670 --> 00:37:58,740
at pagkatapos ay sa bawat pointer sa
halaga na, sa index na,

752
00:37:58,740 --> 00:38:00,740
maaaring aktwal na tumuturo sa ibang mga bagay.

753
00:38:00,740 --> 00:38:05,720
At kaya mayroon ka ng lahat ng mga hiwalay na
chains darating off ng isang malaking array.

754
00:38:05,720 --> 00:38:07,960
>> At kaya dito, kung ako
Nais upang ipasok itlog ng isda,

755
00:38:07,960 --> 00:38:11,220
Alam ko, OK, ako pagpunta sa input
ito sa pamamagitan ng aking hash.

756
00:38:11,220 --> 00:38:15,070
Pupunta ako sa dulo hanggang sa index ng
1, at pagkatapos ay ako pagpunta upang ma-magkaroon ng

757
00:38:15,070 --> 00:38:20,410
lamang ng isang mas maliit na subset ng mga ito
140,000-salita sa diksyunaryo giant.

758
00:38:20,410 --> 00:38:24,220
At pagkatapos ay ako ay maaari lamang tumingin
sa pamamagitan ng 1/26 na iyon.

759
00:38:24,220 --> 00:38:27,910
>> At kaya pagkatapos ko ma lang ipasok
isang itlog ng isda alinman sa bago o pagkatapos ng banana

760
00:38:27,910 --> 00:38:28,820
sa kasong ito?

761
00:38:28,820 --> 00:38:29,700
Pagkatapos, i-right?

762
00:38:29,700 --> 00:38:33,920
At kaya ikaw ay pagpunta sa nais na
ipasok ito node matapos saging,

763
00:38:33,920 --> 00:38:36,667
at upang ikaw ay pagpunta upang magsingit
sa likod o hulihan ng na naka-link na listahan.

764
00:38:36,667 --> 00:38:38,500
Pupunta ako sa bumalik
sa nakaraang slide,

765
00:38:38,500 --> 00:38:40,680
kaya ka guys ay maaaring makita kung paano
gumagana hash.

766
00:38:40,680 --> 00:38:43,980
>> Kaya hash ay equation na ito
na ikaw ay nagpapatakbo ng mga uri ng iyong input

767
00:38:43,980 --> 00:38:46,940
sa pamamagitan ng upang makakuha ng anumang index
na nais mong italaga ito patungo.

768
00:38:46,940 --> 00:38:51,130
At ito, sa halimbawang ito, gusto namin ang lahat ng
na gawin ay gawin ang unang titik,

769
00:38:51,130 --> 00:38:55,890
turn na sa isang index, at pagkatapos namin
Maaaring mag-imbak na sa aming hash.

770
00:38:55,890 --> 00:39:00,160
Lahat ng ginagawa namin dito ay hindi namin
nagko-convert ang mga unang titik.

771
00:39:00,160 --> 00:39:04,770
Kaya Keykey [0] ay lamang ang mga unang titik
ng anumang string namin sa pag,

772
00:39:04,770 --> 00:39:05,720
kami ay pagpasa sa.

773
00:39:05,720 --> 00:39:09,740
Kami ay nagko-convert na sa itaas, at ng
kami ay pagbabawas ng uppercase A,

774
00:39:09,740 --> 00:39:11,740
kaya ang lahat na ang ginagawa
ay nagbibigay sa amin ng isang bilang

775
00:39:11,740 --> 00:39:13,670
sa kung saan namin hash aming mga halaga papunta.

776
00:39:13,670 --> 00:39:16,550
>> At pagkatapos kami ay pagpunta sa
bumalik hash modulus SIZE.

777
00:39:16,550 --> 00:39:19,340
Maging tunay, tunay maingat
dahil, theoretically, dito

778
00:39:19,340 --> 00:39:21,870
ang iyong halaga ng hash ay maaaring maging walang hanggan.

779
00:39:21,870 --> 00:39:23,660
Ito ay maaaring pumunta lamang sa at sa at sa.

780
00:39:23,660 --> 00:39:26,080
Ito ay maaaring maging ng ilang mga talagang,
talagang malaking halaga,

781
00:39:26,080 --> 00:39:29,849
ngunit dahil ang iyong mga talahanayan ng hash na
nalikha mo na lamang ay may 26 na index,

782
00:39:29,849 --> 00:39:31,890
nais mong tiyakin na ang iyong
modulusing upang ikaw

783
00:39:31,890 --> 00:39:33,848
huwag run-- ito ay ang parehong
bagay bilang iyong queue--

784
00:39:33,848 --> 00:39:36,320
sa gayon ay hindi mo na tumakbo off ang
ibaba ng iyong hash.

785
00:39:36,320 --> 00:39:39,210
>> Gusto mong ibalot ito pabalik sa paligid
sa parehong paraan sa [hindi marinig] kapag

786
00:39:39,210 --> 00:39:41,750
nagkaroon ka ng tulad ng isang tunay,
napakalaking sulat, ikaw ay

787
00:39:41,750 --> 00:39:43,740
Ayaw na sa
patakbuhin lamang off sa dulo.

788
00:39:43,740 --> 00:39:46,948
Parehong bagay dito, gusto mong tiyakin
hindi ito tatakbo off ang katapusan sa pamamagitan ng pambalot

789
00:39:46,948 --> 00:39:48,330
sa paligid sa tuktok ng talahanayan.

790
00:39:48,330 --> 00:39:50,530
Kaya ito ay lamang ng isang napaka
simple hash.

791
00:39:50,530 --> 00:39:56,570
Lahat na ginawa ay gawin ang unang
sulat ng ano man ang aming input ay

792
00:39:56,570 --> 00:40:01,660
at turn na sa isang index na
maaari naming ilagay sa aming hash table.

793
00:40:01,660 --> 00:40:05,450
>> Oo, at sa gayon tulad ng sinabi ko bago,
ang paraan na malutas namin ang banggaan

794
00:40:05,450 --> 00:40:09,330
sa aming hash talahanayan ay nakakaranas ng,
kung ano ang aming tawagan, pagdudugtong.

795
00:40:09,330 --> 00:40:13,860
Kaya kung subukan mong ipasok ang maramihang
salita na nagsisimula sa mga parehong bagay,

796
00:40:13,860 --> 00:40:16,145
ikaw ay pagpunta sa magkaroon ng isa hash value.

797
00:40:16,145 --> 00:40:18,770
Avocados at mansanas, kung na sa iyo
patakbuhin ito sa pamamagitan ng aming hash function,

798
00:40:18,770 --> 00:40:21,450
ay pagpunta sa magbibigay sa iyo ng
parehong numero, ang bilang ng mga 0.

799
00:40:21,450 --> 00:40:24,550
At upang ang mga paraan namin malutas na
na namin ang tunay na uri ng link ang mga ito

800
00:40:24,550 --> 00:40:27,010
sama sa pamamagitan ng mga listahan ng link.

801
00:40:27,010 --> 00:40:29,600
>> At kaya sa ganitong kahulugan,
ka guys ay maaaring makita ang mga uri

802
00:40:29,600 --> 00:40:32,640
ng kung paano mga istraktura ng data na
namin nai-set dati

803
00:40:32,640 --> 00:40:35,870
tulad ng isang raisin linked uri list
ng maaaring dumating nang magkasama sa isa.

804
00:40:35,870 --> 00:40:38,860
At pagkatapos ay maaari kang lumikha ng malayo
mas mahusay na istruktura ng data

805
00:40:38,860 --> 00:40:43,350
na maaaring hawakan ng mas malaking halaga ng
data, na dynamic na baguhin ang laki depende

806
00:40:43,350 --> 00:40:44,870
sa iyong mga pangangailangan.

807
00:40:44,870 --> 00:40:45,620
Ang bawat malinaw?

808
00:40:45,620 --> 00:40:47,580
Ang bawat uri ng malinaw na
sa kung ano ang mangyayari dito?

809
00:40:47,580 --> 00:40:52,110
>> Kung Nais kong insert-- kung ano ang isang
prutas na nagsisimula sa, hindi ko alam,

810
00:40:52,110 --> 00:40:54,726
B, na iba sa isang itlog ng isda, saging.

811
00:40:54,726 --> 00:40:55,710
>> Madla: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI PENG: Blackberry, blackberry.

813
00:40:57,910 --> 00:41:00,530
Saan ang blackberry pumunta dito?

814
00:41:00,530 --> 00:41:04,251
Well, talagang hindi pa namin inayos
ito pa, ngunit theoretically

815
00:41:04,251 --> 00:41:06,250
kung gusto naming magkaroon ng ganitong
sa alpabetong pagkakasunud-sunod,

816
00:41:06,250 --> 00:41:07,944
kung saan dapat BlackBerry pumunta?

817
00:41:07,944 --> 00:41:09,210
>> Madla: [hindi marinig]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG: Eksakto, pagkatapos dito, tama?

819
00:41:11,100 --> 00:41:14,950
Pero dahil ito ay masyadong mahirap na
reorder-- Hulaan ko ito ay nasa sa iyo guys.

820
00:41:14,950 --> 00:41:17,920
Ikaw guys Maaari ganap
ipatupad ang anumang gusto mo.

821
00:41:17,920 --> 00:41:20,730
Ang mas mahusay na paraan
ng paggawa nito marahil

822
00:41:20,730 --> 00:41:24,570
ay magiging upang ayusin ang iyong mga naka-link
ilista sa alpabetong pagkakasunud-sunod,

823
00:41:24,570 --> 00:41:26,520
at iba kapag ikaw ay
pagpasok ng mga bagay, na nais mong

824
00:41:26,520 --> 00:41:28,632
upang siguraduhin na ipasok ang mga ito
sa alpabetong pagkakasunud-sunod

825
00:41:28,632 --> 00:41:30,590
kaya na pagkatapos ay kapag ikaw ay
sinusubukan mong hanapin ang mga ito,

826
00:41:30,590 --> 00:41:32,410
hindi mo na kailangang tawirin ang lahat.

827
00:41:32,410 --> 00:41:35,290
Alam mo nang eksakto kung saan
ito ay, at ito ay mas madali.

828
00:41:35,290 --> 00:41:39,100
>> Ngunit kung ikaw uri ng may
bagay kahalong random,

829
00:41:39,100 --> 00:41:41,420
pupuntahan mo pa rin na magkaroon ng
sa pagtawid ito anyways.

830
00:41:41,420 --> 00:41:44,990
At kaya kung Nais kong lamang
ipasok blackberry dito

831
00:41:44,990 --> 00:41:47,470
at nais ko upang maghanap para sa
ito, alam ko, oh, blackberry

832
00:41:47,470 --> 00:41:52,012
dapat magsimula sa mga index ng 1, kaya ko
Alam agad lamang ng paghahanap sa 1.

833
00:41:52,012 --> 00:41:53,970
At pagkatapos ay maaari ako uri ng
tawirin ang listahan ng mga link

834
00:41:53,970 --> 00:41:56,120
hanggang sa makakuha ako sa BlackBerry,
at then-- oo?

835
00:41:56,120 --> 00:41:59,550
>> Madla: Kung sinusubukan mong create--
Hulaan ko ito ay isang napaka-simpleng hash

836
00:41:59,550 --> 00:42:00,050
function.

837
00:42:00,050 --> 00:42:02,835
At kung gusto naming gawin
maramihang mga layer ng ganyan,

838
00:42:02,835 --> 00:42:05,870
OK, gusto naming hiwalay sa
tulad ng lahat ng alpabetikong titik

839
00:42:05,870 --> 00:42:09,040
at pagkatapos ay muli upang gustuhin ng isa pang hanay
ng alpabetikong titik sa loob nito,

840
00:42:09,040 --> 00:42:11,715
ay namin ang paglalagay ko ng hash
mesa sa loob ng isang hash table,

841
00:42:11,715 --> 00:42:13,256
o tulad ng isang function sa loob ng isang function?

842
00:42:13,256 --> 00:42:14,880
O kaya ay na-

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG: So iyong hash
function-- iyong hash talahanayan

844
00:42:17,510 --> 00:42:19,360
maaaring bilang malaking bilang na gusto mo ito sa.

845
00:42:19,360 --> 00:42:21,930
Kaya sa puntong ito, naisip ko
ito ay tunay madali, napaka

846
00:42:21,930 --> 00:42:25,320
simple para sa akin na uri lamang batay
sa mga titik ng unang salita.

847
00:42:25,320 --> 00:42:28,690
At kaya may mga opsyon 26 lamang.

848
00:42:28,690 --> 00:42:32,650
Maaari lamang ba akong makakuha ng 26 mga pagpipilian mula sa
0 hanggang 25 dahil sila lamang

849
00:42:32,650 --> 00:42:36,510
simulan mula A hanggang Z. Subalit kung nais mong
upang idagdag, marahil, mas kumplikado

850
00:42:36,510 --> 00:42:39,260
o magpatakbo ng mas mabilis na oras sa iyong
hash table, kung talagang

851
00:42:39,260 --> 00:42:40,760
maaaring gawin ang lahat ng uri ng bagay.

852
00:42:40,760 --> 00:42:43,330
Maaari kang gumawa ng iyong sariling
equation na nagbibigay sa iyo

853
00:42:43,330 --> 00:42:48,000
higit pang pamamahagi sa iyong
mga salita, at pagkatapos ay kapag naghanap ka,

854
00:42:48,000 --> 00:42:49,300
ito ay magiging mas mabilis.

855
00:42:49,300 --> 00:42:52,100
>> Ito ay lubos na nakasalalay sa iyo guys
paano mo nais na ipatupad na.

856
00:42:52,100 --> 00:42:55,140
Isipin ito bilang lamang ng mga bucket.

857
00:42:55,140 --> 00:42:57,376
Kung Nais kong magkaroon ng
26 mga bucket, pupuntahan ko

858
00:42:57,376 --> 00:42:59,420
upang ayusin ang mga bagay sa mga bucket.

859
00:42:59,420 --> 00:43:02,980
Ngunit ako pagpunta sa magkaroon ng isang grupo
ng mga bagay-bagay sa bawat bucket,

860
00:43:02,980 --> 00:43:05,890
kaya kung nais mong gumawa ng ito
mas mabilis at mas mahusay,

861
00:43:05,890 --> 00:43:07,190
hayaan mo akong magkaroon ng isang daang mga bucket.

862
00:43:07,190 --> 00:43:09,290
>> Ngunit pagkatapos ay mayroon kang upang malaman kung ang isang
paraan upang ayusin ang mga bagay upang ang mga ito

863
00:43:09,290 --> 00:43:11,040
sa wastong bucket dapat sila ay sa.

864
00:43:11,040 --> 00:43:13,331
Ngunit pagkatapos ay kapag ikaw talaga
nais na tingnan ang mga na bucket,

865
00:43:13,331 --> 00:43:16,410
ito ay isang pulutong ng mas mabilis dahil mayroong
mas bagay-bagay sa bawat bucket.

866
00:43:16,410 --> 00:43:20,250
At kaya, oo, na talagang
ang bilis ng kamay para sa iyo guys sa pset5

867
00:43:20,250 --> 00:43:22,360
ay na kayo ay
hinamon upang lumikha lamang

868
00:43:22,360 --> 00:43:26,170
kahit na ano ay ang pinaka mahusay na
function na maaari mong isipin na maging

869
00:43:26,170 --> 00:43:28,520
makakapag-imbak at i-check ang mga halagang ito.

870
00:43:28,520 --> 00:43:30,840
>> Lubos na nakasalalay sa iyo guys
subalit nais mong gawin ito,

871
00:43:30,840 --> 00:43:32,229
ngunit iyan ay isang tunay na magandang point.

872
00:43:32,229 --> 00:43:34,520
Iyon ang mga uri ng logic mo
gusto mong simulan ang pag-iisip tungkol

873
00:43:34,520 --> 00:43:37,236
ay, well, bakit hindi ako gumawa ng mas maraming mga bucket.

874
00:43:37,236 --> 00:43:39,527
At pagkatapos ko bang hanapin
mas bagay, at pagkatapos ay marahil ko

875
00:43:39,527 --> 00:43:41,640
magkaroon ng isang iba't ibang mga pag-andar hash.

876
00:43:41,640 --> 00:43:45,500
>> Oo, mayroong isang pulutong ng mga paraan upang gawin ito
pset, ang ilan ay mas mabilis kaysa sa iba.

877
00:43:45,500 --> 00:43:50,630
Ganap na ako pagpunta upang makita kung paano
mabilis ay ang pinakamabilis na ka guys ay

878
00:43:50,630 --> 00:43:55,170
ay maaaring makakuha ng iyong mga function sa trabaho.

879
00:43:55,170 --> 00:43:58,176
OK, lahat ng mabuti sa
chaining at hash talahanayan?

880
00:43:58,176 --> 00:44:00,800
Ito ay tulad ng isang napaka-simple talaga
konsepto kung sa tingin mo ang tungkol dito.

881
00:44:00,800 --> 00:44:05,160
Lahat ng ito ay ay naghihiwalay sa kahit anong
iyong input ay sa mga bucket,

882
00:44:05,160 --> 00:44:10,670
paghihiwalay sa kanila, at pagkatapos ay sa paghahanap sa
naglilista na nauugnay sa.

883
00:44:10,670 --> 00:44:11,852
>> Cool.

884
00:44:11,852 --> 00:44:18,160
Lahat ng karapatan, ngayon kami ay may isang iba't ibang mga uri
ng istraktura ng data na tinatawag na isang puno.

885
00:44:18,160 --> 00:44:20,850
Sabihin pumunta sa at makipag-usap tungkol pagsusubok
na kung saan ay malinaw na iba't ibang,

886
00:44:20,850 --> 00:44:22,330
ngunit sa parehong kategorya.

887
00:44:22,330 --> 00:44:29,010
Mahalaga, ang lahat ng punong kahoy ay sa halip
ng pag-aayos ng data sa mga guhit na paraan

888
00:44:29,010 --> 00:44:32,560
na ang isang hash table does-- mo
malaman, ito ay nakuha ng isang tuktok at ibaba

889
00:44:32,560 --> 00:44:37,900
at pagkatapos mong uri ng link off ng it-- isang
puno ay may isang tuktok na kayong tumawag sa root,

890
00:44:37,900 --> 00:44:40,220
at pagkatapos ito ay may mga dahon sa palibot.

891
00:44:40,220 --> 00:44:42,390
>> At kaya lahat ng kailangan mo dito
ay lamang tuktok node

892
00:44:42,390 --> 00:44:45,980
na ang mga puntos sa iba pang mga nodes, na puntos
sa mas maraming mga nodes, at iba pa at iba pa.

893
00:44:45,980 --> 00:44:48,130
At kaya mo na lang paghahati sanga.

894
00:44:48,130 --> 00:44:53,255
Ito lamang ay isang iba't ibang mga paraan ng pag-aayos
data, at dahil tinatawag namin itong isang puno,

895
00:44:53,255 --> 00:44:56,270
ka guys just-- ito lamang
imo-modelo out sa hitsura ng isang puno.

896
00:44:56,270 --> 00:44:57,670
Iyon ay kung bakit ang tawag namin ito puno.

897
00:44:57,670 --> 00:44:59,370
>> Mukhang hash talahanayan tulad ng isang table.

898
00:44:59,370 --> 00:45:01,310
Ang isang puno lang ang hitsura ng isang puno.

899
00:45:01,310 --> 00:45:03,300
Lahat ng ito ay isang hiwalay na
paraan ng pag-aayos ng mga node

900
00:45:03,300 --> 00:45:06,020
depende sa kung ano ang inyong mga pangangailangan.

901
00:45:06,020 --> 00:45:11,810
>> Kaya ikaw ay may isang ugat at
pagkatapos ay mayroon kang mga dahon.

902
00:45:11,810 --> 00:45:15,380
Ang paraan na aming makakaya lalo
isipin ang tungkol sa ito ay isang binary tree,

903
00:45:15,380 --> 00:45:18,150
isang binary puno ay lamang ng isang
partikular na uri ng isang puno

904
00:45:18,150 --> 00:45:22,450
kung saan ang tanging mga puntos bawat node
upang, sa max, dalawang iba pang mga nodes.

905
00:45:22,450 --> 00:45:25,434
At kaya dito mayroon kang natatanging
mahusay na proporsyon sa iyong mga puno

906
00:45:25,434 --> 00:45:28,600
na ginagawang mas madali ang uri ng hitsura
sa kung ano ang halaga na ikaw ay dahil pagkatapos mo

907
00:45:28,600 --> 00:45:30,150
Mayroon palaging isang kaliwa o kanan.

908
00:45:30,150 --> 00:45:33,150
Mayroong hindi kailanman tulad ng isang kaliwang ikatlong mula
sa kaliwa o isang ika-apat mula sa kaliwa.

909
00:45:33,150 --> 00:45:36,358
Ito lang ang mayroon ka ng isang kaliwa at isang kanan
at maaari mong hanapin ang alinman sa mga dalawang.

910
00:45:36,358 --> 00:45:38,980
At kaya kung bakit kapaki-pakinabang na ito ay?

911
00:45:38,980 --> 00:45:40,980
Ang paraan na ito ay
kapaki-pakinabang ay kung ikaw ay naghahanap

912
00:45:40,980 --> 00:45:42,890
sa paghahanap sa pamamagitan values, di ba?

913
00:45:42,890 --> 00:45:45,640
Sa halip na ang pagpapatupad ng binary
maghanap sa isang error array,

914
00:45:45,640 --> 00:45:49,260
kung iyong nais na ma-ipasok nodes
at mag-alis ng nodes sa kalooban at din

915
00:45:49,260 --> 00:45:52,185
mapanatili ang search
kakayahan ng binary paghahanap.

916
00:45:52,185 --> 00:45:54,560
Kaya sa ganitong paraan, hindi namin uri ng
tricking-- tandaan kapag kami ay

917
00:45:54,560 --> 00:45:56,530
Sinabi listahan ng link ay maaaring hindi binary paghahanap?

918
00:45:56,530 --> 00:46:01,700
Kami ay uri ng paglikha ng isang istraktura ng data
na trick na sa pagtatrabaho.

919
00:46:01,700 --> 00:46:05,034
>> At kaya dahil naka-link na listahan ay linear,
sila lamang ang link ng isa pagkatapos ng isa.

920
00:46:05,034 --> 00:46:06,950
Maaari uri ng kaming may
iba't ibang uri ng mga payo

921
00:46:06,950 --> 00:46:09,408
sa puntong iyon sa iba't ibang mga node
na maaaring makatulong sa amin sa paghahanap.

922
00:46:09,408 --> 00:46:12,590
At kaya dito, kung nais kong
magkaroon ng isang binary puno ng paghahanap,

923
00:46:12,590 --> 00:46:14,090
Alam ko na ang aking gitna kung 55.

924
00:46:14,090 --> 00:46:18,280
Ako lamang ang pagpunta upang lumikha ng na
bilang aking middle, tulad ng aking mga ugat,

925
00:46:18,280 --> 00:46:20,770
at pagkatapos ay ako pagpunta sa may
mga halaga iikot off ng mga ito.

926
00:46:20,770 --> 00:46:25,610
>> Kaya dito, kung ako pagpunta upang maghanap para sa
ang halaga ng 66, maaari ba akong magsimula sa 55.

927
00:46:25,610 --> 00:46:27,310
Ito ay 66 mas malaki kaysa sa 55?

928
00:46:27,310 --> 00:46:30,970
Oo ito ay, upang malaman ko mus ko sa paghahanap
i n kanan pointer ng punong ito.

929
00:46:30,970 --> 00:46:32,440
Pumunta ako sa 77.

930
00:46:32,440 --> 00:46:35,367
OK, ay 66 mas mababa sa o mas malaki kaysa sa 77?

931
00:46:35,367 --> 00:46:37,950
Ito ay mas mababa kaysa sa, upang malaman mo, oh,
na may upang maging kaliwa node.

932
00:46:37,950 --> 00:46:41,410
>> At kaya dito namin uri ng na pinapanatili
lahat ng mahusay na mga bagay-bagay tungkol sa array,

933
00:46:41,410 --> 00:46:44,420
kaya tulad ng mga dynamic na pagbabago ng laki
ng mga bagay, pagiging

934
00:46:44,420 --> 00:46:49,530
maaaring ipasok at tanggalin sa kalooban,
nang hindi na kinakailangang mag-alala tungkol sa mga fixed

935
00:46:49,530 --> 00:46:50,370
halaga ng puwang.

936
00:46:50,370 --> 00:46:52,820
Mapanatili pa rin namin ang lahat ng
mga magagandang bagay

937
00:46:52,820 --> 00:46:57,140
habang nagagawa ring upang mapanatili ang
mag-log at oras ng binary paghahanap sa paghahanap

938
00:46:57,140 --> 00:47:00,450
na lamang namin dati
maaaring makakuha ng isang phrase.

939
00:47:00,450 --> 00:47:06,310
>> Cool istraktura ng data, uri ng
kumplikadong upang ipatupad, ang node.

940
00:47:06,310 --> 00:47:08,311
Tulad ng iyong nakikita, ang lahat ng ito
ay ang struct ng buko

941
00:47:08,311 --> 00:47:10,143
ay na mayroon ka ng isang kaliwa
at isang karapatan pointer.

942
00:47:10,143 --> 00:47:11,044
Iyan na ang lahat ng ito ay.

943
00:47:11,044 --> 00:47:12,960
Kaya sa halip na lamang
pagkakaroon ng isang x o isang nakaraang.

944
00:47:12,960 --> 00:47:15,920
Mayroon kang isang kaliwa o kanan, at pagkatapos ay
maaari mong uri ng link ang mga ito nang sama-sama

945
00:47:15,920 --> 00:47:16,836
gayunpaman pinili mo ito.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, aktwal na kami ay pagpunta
tumagal lamang ng ilang minuto.

948
00:47:24,270 --> 00:47:25,790
Kaya kami ay pagpunta upang bumalik dito.

949
00:47:25,790 --> 00:47:28,270
Tulad ng dati sabi ko,
Ako uri ng ipinaliwanag

950
00:47:28,270 --> 00:47:31,520
ang logic sa likod kung paano namin
Gusto paghahanap sa pamamagitan ng mga ito.

951
00:47:31,520 --> 00:47:33,860
Kami ay pagpunta sa subukan
pseudocoding this out upang makita ang

952
00:47:33,860 --> 00:47:38,000
kung maaari naming uri ng mag-apply ang
parehong lohika ng binary paghahanap

953
00:47:38,000 --> 00:47:40,055
sa iba't ibang uri ng istraktura ng data.

954
00:47:40,055 --> 00:47:45,049
Kung ikaw guys na nais na kumuha ng tulad ng isang pares
minuto upang lamang isipin ang tungkol ito.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
SIGE.

957
00:48:46,925 --> 00:48:51,407
Lahat ng karapatan, ako pagpunta sa
talagang lamang magbigay the-- mo ang hindi,

958
00:48:51,407 --> 00:48:52,990
Kukunin namin ang unang makipag-usap tungkol sa mga pseudocode.

959
00:48:52,990 --> 00:48:56,580
Kaya kahit sino ay gusto
na magbigay ng isang ulos sa kung ano ang

960
00:48:56,580 --> 00:49:02,100
ang unang bagay na gusto mong gawin kapag
kayo ay nagsisimula searching ay?

961
00:49:02,100 --> 00:49:04,460
Kung kami ay naghahanap para sa
ang halaga ng 66, kung ano ang

962
00:49:04,460 --> 00:49:07,940
ang unang bagay na gusto naming gawin kung
gusto naming binary paghahanap punong kahoy na ito?

963
00:49:07,940 --> 00:49:10,760
>> Madla: Gusto mong tingnan ang karapatan
at tumingin sa kaliwa at makita [hindi marinig]

964
00:49:10,760 --> 00:49:11,230
mas malaking bilang.

965
00:49:11,230 --> 00:49:12,271
>> ANDI PENG: Oo, eksakto.

966
00:49:12,271 --> 00:49:15,350
Kaya ikaw ay pagpunta upang tumingin sa iyong root.

967
00:49:15,350 --> 00:49:18,180
Mayroong maraming mga paraan na maaari mong tawagan
ito, sabihin sa iyong mga magulang na node tao.

968
00:49:18,180 --> 00:49:21,317
Gusto kong sabihin na ugat dahil
na tulad ng mga ugat ng puno.

969
00:49:21,317 --> 00:49:23,400
Ikaw ay pagpunta sa tumingin sa
iyong root node, at ikaw ay

970
00:49:23,400 --> 00:49:26,940
pagpunta upang makita ang 66 na mas malaki
kaysa sa o mas mababa kaysa sa 55.

971
00:49:26,940 --> 00:49:30,360
At kung ito ay mas malaki kaysa sa, well, ito ay
mas malaki kaysa sa, kung saan nais namin na tingnan ang?

972
00:49:30,360 --> 00:49:32,000
Saan ang gusto namin sa paghahanap ngayon, tama?

973
00:49:32,000 --> 00:49:34,340
Gusto naming hanapin ang
kanang kalahati ng punong kahoy na ito.

974
00:49:34,340 --> 00:49:38,390
>> Kaya mayroon kami, Maginhawang, isang
pointer na tumuturo sa kanan.

975
00:49:38,390 --> 00:49:44,325
At kaya pagkatapos ay maaari naming i-set
ang aming bagong ugat na 77.

976
00:49:44,325 --> 00:49:46,450
Maaari naming pumunta lamang sa kung saan man
ang pointer ay pagturo.

977
00:49:46,450 --> 00:49:49,100
Well, oh, dito kami ay nagsisimula
sa 77, at maaari naming lamang

978
00:49:49,100 --> 00:49:51,172
gawin ito recursively muli at muli.

979
00:49:51,172 --> 00:49:52,880
Sa ganitong paraan, uri kayo
ng magkaroon ng isang function.

980
00:49:52,880 --> 00:49:57,430
Mayroon kang isang paraan ng paghahanap na iyong
Maaari lamang ulitin paulit-ulit-ulit,

981
00:49:57,430 --> 00:50:02,720
depende sa kung saan nais mong tingnan ang
hanggang sa wakas makakuha ng halaga

982
00:50:02,720 --> 00:50:04,730
na kayo ay naghahanap para sa.

983
00:50:04,730 --> 00:50:05,230
Magkaroon ng kahulugan?

984
00:50:05,230 --> 00:50:07,800
>> Ako ay tungkol sa upang ipakita sa iyo ang aktwal
code, at ito ay isang pulutong ng code.

985
00:50:07,800 --> 00:50:08,674
Hindi na kailangang mag pambihira out.

986
00:50:08,674 --> 00:50:09,910
Susubukan naming makipag-usap sa pamamagitan nito.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Sa totoo lang, hindi.

989
00:50:14,020 --> 00:50:15,061
Iyon ay pseudocode lamang.

990
00:50:15,061 --> 00:50:17,860
OK, na lamang ang pseudocode,
kung saan ay isang bit kumplikado,

991
00:50:17,860 --> 00:50:19,751
ngunit ito ay ganap na multa.

992
00:50:19,751 --> 00:50:21,000
Ang bawat mga sumusunod na kasama dito?

993
00:50:21,000 --> 00:50:24,260
Kung ang ugat ay null, return
hindi totoo dahil ang ibig sabihin nito

994
00:50:24,260 --> 00:50:26,850
hindi mo kahit na magkaroon ng kahit ano doon.

995
00:50:26,850 --> 00:50:31,376
>> Kung ugat n ay ang halaga, kaya kung ito
ang mangyayari sa maging ang isa ikaw ay naghahanap sa,

996
00:50:31,376 --> 00:50:34,000
pagkatapos ikaw ay pagpunta upang bumalik true
dahil alam mo na iyong natagpuan ito.

997
00:50:34,000 --> 00:50:36,250
Ngunit kung ang mga halaga ay mas mababa
sa ugat ng n, ikaw ay

998
00:50:36,250 --> 00:50:38,332
pagpunta sa paghahanap sa kaliwa
bata o kaliwa na dahon,

999
00:50:38,332 --> 00:50:39,540
kahit anong gusto mo sa tawag na ito.

1000
00:50:39,540 --> 00:50:41,750
At kung ang mga halaga ay mas malaki kaysa sa root,
ikaw ay pagpunta sa paghahanap ng tamang tree,

1001
00:50:41,750 --> 00:50:44,610
pagkatapos ay tatakbo lamang sa mga function
sa pamamagitan ng search muli.

1002
00:50:44,610 --> 00:50:48,037
>> At kung ugat ay null, na na
nangangahulugan naabot mo na ang dulo?

1003
00:50:48,037 --> 00:50:50,120
Ito ay nangangahulugan na wala kang
mas higit pang mga dahon sa paghahanap,

1004
00:50:50,120 --> 00:50:52,230
pagkatapos ay alam mo, oh, ako
hulaan ito ay hindi in dito

1005
00:50:52,230 --> 00:50:55,063
dahil matapos ko na tumingin sa pamamagitan ng
ang buong bagay at ito ay hindi dito,

1006
00:50:55,063 --> 00:50:56,930
ito ay maaaring hindi lamang dito.

1007
00:50:56,930 --> 00:50:58,350
>> Ba na magkaroon ng kahulugan sa lahat ng tao?

1008
00:50:58,350 --> 00:51:03,230
Kaya ito ay tulad ng paghahanap ng binary pinapanatili
ang mga kakayahan ng mga listahan ng link.

1009
00:51:03,230 --> 00:51:09,200
Cool, at sa gayon ang ikalawang uri
ng istraktura ng data guys

1010
00:51:09,200 --> 00:51:13,180
Maaari subukan ang pagpapatupad sa iyong pset,
mayroon na lamang kayong pumili ng isang paraan.

1011
00:51:13,180 --> 00:51:19,430
Ngunit marahil isang alternatibong paraan upang
ang hash table ay kung ano ang tawag namin sa isang trie.

1012
00:51:19,430 --> 00:51:24,080
>> Lahat ng isang trie ay ay isang
partikular na uri ng puno na

1013
00:51:24,080 --> 00:51:28,600
may halaga na pumunta sa iba pang mga halaga.

1014
00:51:28,600 --> 00:51:31,450
Kaya sa halip ng pagkakaroon ng isang binary
puno sa kamalayan na ang isa lamang sa

1015
00:51:31,450 --> 00:51:35,940
bagay ay maaaring punto sa dalawa, maaari kang magkaroon ng
isang bagay point sa maraming, maraming mga bagay.

1016
00:51:35,940 --> 00:51:39,450
Ikaw ay may mahalagang mga array
sa loob ng na-imbak mo

1017
00:51:39,450 --> 00:51:41,790
mga payo na tumuturo sa ibang mga array.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Kaya ang node ng kung paano namin
nais tukuyin ang isang trie

1020
00:51:49,460 --> 00:51:52,590
ay nais naming magkaroon ng isang
Boolean, c salita, tama?

1021
00:51:52,590 --> 00:51:54,920
Kaya ang node ay Boolean
tulad ng tama o mali,

1022
00:51:54,920 --> 00:51:58,490
una sa lahat sa ulo ng
na array, salita kaya ito?

1023
00:51:58,490 --> 00:52:03,620
Pangalawa, nais mong magkaroon ng mga payo
sa ano man ang iba sa kanila ay.

1024
00:52:03,620 --> 00:52:07,470
A bit complex, medyo abstract, ngunit
Ako ay ipaliwanag kung ano na ang lahat ng paraan.

1025
00:52:07,470 --> 00:52:13,800
>> Kaya dito, sa tuktok, kung ikaw
ipinahayag ng isang array na,

1026
00:52:13,800 --> 00:52:17,040
isang node kung saan ikaw ay may isang Boolean
halaga na naka-imbak sa harap

1027
00:52:17,040 --> 00:52:19,490
na nagsasabi sa iyo na ito ay isang salita?

1028
00:52:19,490 --> 00:52:20,520
Hindi ba ito ang isang salita?

1029
00:52:20,520 --> 00:52:23,240
At pagkatapos ay mayroon kang mga
natitirang bahagi ng iyong array na

1030
00:52:23,240 --> 00:52:26,040
tunay na mga tindahan ng lahat ng mga
posibilidad ng kung ano ito ay maaaring.

1031
00:52:26,040 --> 00:52:28,660
Kaya, halimbawa, tulad ng
sa tuktok mayroon kang

1032
00:52:28,660 --> 00:52:32,140
ang unang bagay na nagsasabing totoo o
false, oo o hindi, ito ay isang salita.

1033
00:52:32,140 --> 00:52:38,130
>> At pagkatapos ay mayroon kang 0 hanggang 26 ng
ang mga titik na maaari mong tindahan.

1034
00:52:38,130 --> 00:52:42,790
Kung Nais kong hanapin dito
para sa bat, pumunta ako sa tuktok

1035
00:52:42,790 --> 00:52:49,200
at ako ay tumingin para sa B. mahanap ko B sa aking
array, at upang malaman ko, OK, ay B ng isang salita?

1036
00:52:49,200 --> 00:52:53,010
B ay hindi isang salita, kaya ganito
Dapat ko bang patuloy na maghanap.

1037
00:52:53,010 --> 00:52:56,410
Pumunta ko mula sa B, at ako ay tumingin sa
pointer na B puntos na patungo

1038
00:52:56,410 --> 00:53:00,900
at nakikita ko ang ibang hanay ng mga impormasyon,
ang parehong istraktura na kami dati.

1039
00:53:00,900 --> 00:53:05,240
>> At here-- oh, ang susunod na
sulat sa [hindi marinig] ay A.

1040
00:53:05,240 --> 00:53:07,210
Kaya tingnan natin sa na array.

1041
00:53:07,210 --> 00:53:10,860
Makikita natin ang ika-walong halaga,
at pagkatapos, hanapin namin upang makita, oh,

1042
00:53:10,860 --> 00:53:12,840
hey, na isang salita, ay B-A ng isang salita?

1043
00:53:12,840 --> 00:53:13,807
Ito ay hindi isang salita.

1044
00:53:13,807 --> 00:53:14,890
Mayroon kaming upang patuloy na naghahanap.

1045
00:53:14,890 --> 00:53:17,850
>> At kaya pagkatapos namin tumingin sa kung saan
ang pointer ng isang puntos,

1046
00:53:17,850 --> 00:53:21,130
at ang mga puntos sa ibang paraan sa
na kung saan kami ay may higit na halaga na naka-imbak.

1047
00:53:21,130 --> 00:53:24,150
At sa huli, na nakukuha namin na
B-A-T, na kung saan ay isang salita.

1048
00:53:24,150 --> 00:53:25,970
At upang ang mga susunod na panahon
tumingin ka, ikaw ay pagpunta

1049
00:53:25,970 --> 00:53:30,850
na magkaroon ng na-check ng, oo,
Boolean function na ito ay totoo.

1050
00:53:30,850 --> 00:53:35,450
At kaya sa kamalayan hindi namin uri
ng pagkakaroon ng isang puno na may mga array.

1051
00:53:35,450 --> 00:53:39,890
>> Kaya pagkatapos ay maaari mong uri ng paghahanap down.

1052
00:53:39,890 --> 00:53:43,650
Kaysa sa hashing isang function at
pagtatalaga ng mga halaga sa pamamagitan ng listahan ng mga link,

1053
00:53:43,650 --> 00:53:49,190
maaari mo lamang ipatupad ang isang
trie na mga paghahanap downwords.

1054
00:53:49,190 --> 00:53:50,850
Talagang, talagang kumplikado stuff.

1055
00:53:50,850 --> 00:53:54,060
Hindi madaling mag-isip tungkol sa dahil ako tulad ng
pagdura kaya maraming mga istruktura ng data out

1056
00:53:54,060 --> 00:53:58,710
sa iyo, ngunit ang ginagawa ng lahat ng uri ng
maunawaan kung paano gumagana ang logic ng mga ito?

1057
00:53:58,710 --> 00:54:01,920
>> OK, cool.

1058
00:54:01,920 --> 00:54:05,600
Kaya B-A-T, at pagkatapos ay
ikaw ay pagpunta upang maghanap.

1059
00:54:05,600 --> 00:54:07,940
Ang susunod na panahon na kayo ay pagpunta
upang makita, oh, hey, ito ay totoo,

1060
00:54:07,940 --> 00:54:09,273
kaya alam ko na ito ay dapat na isang salita.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Parehong bagay para sa zoo.

1063
00:54:13,770 --> 00:54:17,960
Kaya dito ang mga bagay sa ngayon, kung tayo
Nais upang maghanap para sa mga zoo, sa ngayon,

1064
00:54:17,960 --> 00:54:20,780
kasalukuyang zoo ay hindi isang
salita sa aming diksyunaryo

1065
00:54:20,780 --> 00:54:25,300
dahil, gaya ng maaaring makakita sa iyo guys, ang
unang lugar na kami ay may isang Boolean

1066
00:54:25,300 --> 00:54:28,590
nagbabalik ng tunay ay sa dulo ng zoom.

1067
00:54:28,590 --> 00:54:30,430
Mayroon kaming Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> At kaya dito, hindi namin talagang magkaroon
ang salita, zoo, sa aming diksyunaryo

1069
00:54:33,900 --> 00:54:36,070
dahil ang check box na ito ay hindi naka-check.

1070
00:54:36,070 --> 00:54:39,540
Kaya ang computer ay hindi
malaman na ang zoo ay isang salita

1071
00:54:39,540 --> 00:54:42,430
dahil ang paraan na kami
naka-imbak ito, tanging isang zoom dito

1072
00:54:42,430 --> 00:54:44,920
talaga ay isang Boolean halaga
na na-naka-totoo.

1073
00:54:44,920 --> 00:54:49,380
Kaya kung nais namin na ipasok ang
salita, zoo, sa aming diksyonaryo,

1074
00:54:49,380 --> 00:54:51,770
kung paano namin pumunta tungkol sa paggawa na?

1075
00:54:51,770 --> 00:54:55,960
Ano ang kailangan namin upang gawin upang tiyakin na ang aming
alam computer na Z-O-O ay isang salita

1076
00:54:55,960 --> 00:54:58,130
at hindi ang unang salita ay Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> Madla: [hindi marinig]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI PENG: Eksakto, namin
nais na tiyakin na ang

1079
00:55:01,450 --> 00:55:07,890
dito, na Boolean halaga ay
checked off na ito ay totoo.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, pagkatapos kami ay pagpunta upang suriin na,
upang malaman namin ang eksaktong, hey, zoo ay isang salita.

1081
00:55:13,297 --> 00:55:15,380
Pupunta ako upang sabihin sa
computer na ito ay isang salita sa gayon

1082
00:55:15,380 --> 00:55:18,000
na kapag ang mga tseke computer,
alam na zoo ay isang salita.

1083
00:55:18,000 --> 00:55:21,269
>> Dahil tandaan ang lahat ng mga data na ito
kaayusan, ito ay tunay madali para sa amin

1084
00:55:21,269 --> 00:55:22,310
sabihin, oh, bat ang isang salita.

1085
00:55:22,310 --> 00:55:22,851
Zoo ay isang salita.

1086
00:55:22,851 --> 00:55:23,611
Mag-zoom ay isang salita.

1087
00:55:23,611 --> 00:55:25,860
Ngunit kapag ikaw ay pagbuo ng mga ito,
ang computer ay walang mga ideya.

1088
00:55:25,860 --> 00:55:28,619
>> Kaya ikaw ay may upang sabihin ito nang eksakto
sa anong punto salita kaya ito?

1089
00:55:28,619 --> 00:55:29,910
Sa anong punto ay hindi ito isang salita?

1090
00:55:29,910 --> 00:55:31,784
At sa anong punto ko
kailangan upang maghanap ng mga bagay,

1091
00:55:31,784 --> 00:55:34,000
at sa anong punto ang kailangan kong pumunta sa susunod?

1092
00:55:34,000 --> 00:55:37,010
Ang bawat malinaw na iyon?

1093
00:55:37,010 --> 00:55:39,540
Cool.

1094
00:55:39,540 --> 00:55:42,530
>> At kaya pagkatapos ay dumating ang
problema ng kung paano gagawin namin

1095
00:55:42,530 --> 00:55:45,560
pumunta tungkol sa pagpasok ng isang bagay
na talagang hindi doon?

1096
00:55:45,560 --> 00:55:49,090
Kaya sabihin lang sabihin gusto naming ipasok
ang salita, bakit, sa aming trie.

1097
00:55:49,090 --> 00:55:53,589
Tulad nang nakikita mo guys tulad ng kasalukuyan
lahat ng mayroon kami ngayon ay B-A-T,

1098
00:55:53,589 --> 00:55:55,630
at ang bagong istraktura ng data
doon ay isang pinta na

1099
00:55:55,630 --> 00:55:59,740
matulis sa null dahil ipinapalagay namin
na, oh, walang mga salita pagkatapos ng B-A-T,

1100
00:55:59,740 --> 00:56:02,530
bakit kailangan namin upang panatilihin
pagkakaroon ng mga bagay-bagay matapos na T.

1101
00:56:02,530 --> 00:56:06,581
>> Ngunit ang problema arises kung gagawin namin sa iyo
gusto mong magkaroon ng isang salita na nauuna matapos

1102
00:56:06,581 --> 00:56:07,080
ang T.

1103
00:56:07,080 --> 00:56:09,500
Kung ikaw ay may paliguan, ikaw ay
pagpunta sa gusto ng isang H karapatan.

1104
00:56:09,500 --> 00:56:13,290
At upang ang mga paraan namin ay pagpunta sa gawin iyon ay
kami ay pagpunta upang lumikha ng isang hiwalay na node.

1105
00:56:13,290 --> 00:56:16,840
Hindi kami mag-ukol kahit anong halaga
ng memory para sa bagong array,

1106
00:56:16,840 --> 00:56:20,720
at kami ay pagpunta sa muling italaga ang mga payo.

1107
00:56:20,720 --> 00:56:22,947
>> Kami ay pagpunta sa italaga ang
H, Una sa lahat, ito null,

1108
00:56:22,947 --> 00:56:24,030
kami ay pagpunta sa mapupuksa.

1109
00:56:24,030 --> 00:56:26,590
Kami ay pagpunta sa may
ang H point pababa.

1110
00:56:26,590 --> 00:56:30,600
Kapag nakita namin ang isang H, gusto namin ito
upang pumunta sa ibang lugar.

1111
00:56:30,600 --> 00:56:33,910
>> Sa dito, maaari naming pagkatapos ay i-check off yes.

1112
00:56:33,910 --> 00:56:38,170
Kung ang hit namin ang isang H pagkatapos ng T, oh,
pagkatapos ay alam namin na ito ay isang salita.

1113
00:56:38,170 --> 00:56:41,110
Ang Boolean ay pagpunta sa bumalik totoo.

1114
00:56:41,110 --> 00:56:42,950
Ang bawat malinaw sa kung paano na nangyari?

1115
00:56:42,950 --> 00:56:45,110
SIGE.

1116
00:56:45,110 --> 00:56:47,214
>> Kaya mahalagang, ang lahat ng mga
mga istruktura ng data

1117
00:56:47,214 --> 00:56:50,130
na kami ay wala sa paglipas ng araw na ito, hindi ko na
wala na sa kanila tunay, tunay mabilis

1118
00:56:50,130 --> 00:56:52,192
at hindi in sa marami
detalye, at iyon ang OK.

1119
00:56:52,192 --> 00:56:53,900
Sa sandaling simulan mo ang panggugulo
sa mga ito, makikita mo ang

1120
00:56:53,900 --> 00:56:55,733
pagpapanatili ng track ng kung saan
lahat ng payo ay,

1121
00:56:55,733 --> 00:56:58,060
kung ano ang nangyayari sa iyong
istruktura ng data, at iba pa.

1122
00:56:58,060 --> 00:56:59,810
Makikita nila na tunay na kapaki-pakinabang,
at ito ay nakasalalay sa iyo

1123
00:56:59,810 --> 00:57:03,890
guys sa ganap na malaman kung paano
na nais mong ipatupad bagay.

1124
00:57:03,890 --> 00:57:07,650
>> At kaya pset4, ng 5-- oh, na ang mali.

1125
00:57:07,650 --> 00:57:10,140
Pset5 ay maling spelling.

1126
00:57:10,140 --> 00:57:13,710
Tulad ng sinabi ko bago, ikaw ay pagpunta sa, isang beses
muli, i-download ang source code mula sa amin.

1127
00:57:13,710 --> 00:57:16,210
May pupuntahan ng tatlong pangunahing
bagay na makikita mo ay pag-download.

1128
00:57:16,210 --> 00:57:18,470
Makikita mong i-download diksyunaryo,
kers, at teksto.

1129
00:57:18,470 --> 00:57:21,660
>> Lahat ng mga bagay ay ang mga
mag mga diksyunaryo ng mga salita

1130
00:57:21,660 --> 00:57:25,190
na gusto namin sa iyo na suriin ang
o test ng impormasyon

1131
00:57:25,190 --> 00:57:26,930
na gusto namin sa iyo sa oras ng paggawa check.

1132
00:57:26,930 --> 00:57:29,670
At upang ang mga diksyunaryo
bigyan ka namin ay pagpunta

1133
00:57:29,670 --> 00:57:34,870
upang bigyan ka ng aktwal na mga salita na gusto naming
sa inyo na tindahan sa anumang paraan sa isang paraan na

1134
00:57:34,870 --> 00:57:36,530
mas mahusay kaysa sa isang array.

1135
00:57:36,530 --> 00:57:38,470
At pagkatapos ay ang teksto ay
magiging kung ano kami

1136
00:57:38,470 --> 00:57:43,900
na humihiling sa iyo na baybayin suriin upang tiyakin na
lahat ng mga salita na may mga tunay na salita.

1137
00:57:43,900 --> 00:57:47,970
>> At upang ang mga tatlong bloke ng
mga programa na ibibigay namin sa iyo

1138
00:57:47,970 --> 00:57:51,130
ay tinatawag dictionary.c,
dictionary.h, at speller.c.

1139
00:57:51,130 --> 00:57:56,500
At sa gayon ang lahat dictionary.c ay ay
kung ano ang iyong hiniling na ipatupad.

1140
00:57:56,500 --> 00:57:57,880
Naglo-load Ito salita.

1141
00:57:57,880 --> 00:58:02,000
Ito spell tseke ang mga ito, at ito ay gumagawa sigurado
na ang lahat ng bagay ay wastong inilagay.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h ay isang file library lamang
na nagpapahayag ng lahat ng mga pag-andar.

1143
00:58:05,180 --> 00:58:07,650
At speller.c, kami ay pagpunta sa magbibigay sa iyo.

1144
00:58:07,650 --> 00:58:09,290
Hindi mo kailangang baguhin ang anuman sa mga ito.

1145
00:58:09,290 --> 00:58:14,290
Lahat speller.c ay ay tumagal na,
naglo-load ito, sinusuri ang bilis ng mga ito,

1146
00:58:14,290 --> 00:58:19,190
pagsusulit ang benchmark ng tulad ng kung paano
mabilis na nagawa mong gawin ang mga bagay.

1147
00:58:19,190 --> 00:58:20,410
>> Ito ay isang speller.

1148
00:58:20,410 --> 00:58:23,920
Gawin lamang na hindi gulo sa mga ito, ngunit gumawa
siguraduhin na maunawaan kung ano ang ginagawa nito.

1149
00:58:23,920 --> 00:58:28,090
Ginagamit namin ang isang function na tinatawag na getrusage na
pagsusulit ang pagganap ng iyong mga oras ng paggawa

1150
00:58:28,090 --> 00:58:28,590
checker.

1151
00:58:28,590 --> 00:58:32,200
Lahat ng ginagawa nito ay talaga subukan ang mga
oras ng lahat ng bagay sa iyong diksyunaryo,

1152
00:58:32,200 --> 00:58:33,680
kaya tiyaking nauunawaan mo ang mga ito.

1153
00:58:33,680 --> 00:58:36,660
Maging maingat sa hindi gulo sa mga ito o
pa ang mga bagay-bagay ay hindi tatakbo nang maayos.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> At sa karamihan ng mga hamon na ito ay para sa mga
ka guys upang talagang baguhin dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Kami ay pagpunta sa magbibigay sa iyo ng
140,000 mga salita sa isang diksiyunaryo.

1157
00:58:48,526 --> 00:58:50,900
Kami ay pagpunta sa magbibigay sa iyo ng isang text
file na may mga salitang iyon,

1158
00:58:50,900 --> 00:58:54,840
at nais ka naming ma-organisa
mga ito sa isang hash table o isang trie

1159
00:58:54,840 --> 00:58:58,140
dahil kapag hinihiling namin sa iyo sa oras ng paggawa
check-- isipin kung ikaw ay spell

1160
00:58:58,140 --> 00:59:00,690
suri tulad Odyssey ni Homer.

1161
00:59:00,690 --> 00:59:03,010
Ito ay tulad nito malaking, malaking pagsubok.

1162
00:59:03,010 --> 00:59:05,190
>> Isipin kung ang bawat isang
word mo ay nagkaroon upang tumingin

1163
00:59:05,190 --> 00:59:08,100
sa pamamagitan ng isang hanay ng mga 140,000 na mga halaga.

1164
00:59:08,100 --> 00:59:10,350
Iyon ay tumagal magpakailanman
para sa iyong machine na tumakbo.

1165
00:59:10,350 --> 00:59:14,490
Iyon ang dahilan kung bakit gusto naming ayusin ang aming
data sa mas mahusay na mga istraktura ng data

1166
00:59:14,490 --> 00:59:17,270
tulad ng isang hash table o isang trie.

1167
00:59:17,270 --> 00:59:20,700
At pagkatapos mong guys Maaari uri
ng kapag naghahanap ka ng access

1168
00:59:20,700 --> 00:59:22,570
mas madali at mas mabilis na mga bagay.

1169
00:59:22,570 --> 00:59:24,934
>> At kaya maging maingat upang malutas ang mga banggaan.

1170
00:59:24,934 --> 00:59:27,350
Ikaw ay pagpunta upang makakuha ng grupo
ng mga salita ng yaong magsimula sa A.

1171
00:59:27,350 --> 00:59:29,957
Ikaw ay pagpunta upang makakuha ng grupo ng mga salita
na nagsisimula sa B. Hanggang sa iyo

1172
00:59:29,957 --> 00:59:31,290
guys kung paano mo gusto upang malutas ito.

1173
00:59:31,290 --> 00:59:34,144
Marahil mayroong higit pa
mabisa hash

1174
00:59:34,144 --> 00:59:36,810
na lamang ang unang titik ng
isang bagay, at sa gayon ay ang bahala sa iyo

1175
00:59:36,810 --> 00:59:38,190
guys sa uri ng gawin ang anumang gusto mo.

1176
00:59:38,190 --> 00:59:40,148
>> Siguro gusto mong idagdag
lahat ang mga titik na magkasama.

1177
00:59:40,148 --> 00:59:43,410
Siguro gusto mong gusto gawin kakaiba mga bagay
sa account ang bilang ng mga titik,

1178
00:59:43,410 --> 00:59:43,970
kahit ano.

1179
00:59:43,970 --> 00:59:45,386
Hanggang sa iyo guys kung paano mo nais na gawin.

1180
00:59:45,386 --> 00:59:49,262
Kung nais mong gumawa ng isang hash table, kung ikaw
Gusto mong subukan ang isang trie, ganap na nakasalalay sa iyo.

1181
00:59:49,262 --> 00:59:52,470
Ko sa inyo kung maagang ng panahon na ang
trie ay karaniwang isang bit mas mahirap

1182
00:59:52,470 --> 00:59:54,520
dahil lang may isang pulutong
higit pang mga payo upang subaybayan.

1183
00:59:54,520 --> 00:59:55,645
Ngunit ganap sa inyo guys.

1184
00:59:55,645 --> 00:59:58,742
Ito ay malayo mas mabisa
sa karamihan ng pagkakataon.

1185
00:59:58,742 --> 01:00:01,450
Gusto mong talagang magagawang upang panatilihin
subaybayan ng lahat ng iyong mga payo.

1186
01:00:01,450 --> 01:00:03,850
Tulad gawin ang parehong bagay
na ako ay ginagawa dito.

1187
01:00:03,850 --> 01:00:06,871
Kapag sinusubukan mong ipasok
mga halaga sa isang hash table o tanggalin,

1188
01:00:06,871 --> 01:00:08,620
tiyakin na ikaw ay
talagang sa pagpapanatili ng track

1189
01:00:08,620 --> 01:00:11,860
ng kung saan ang lahat ay dahil sa
ito ay tunay madali para sa kung ako

1190
01:00:11,860 --> 01:00:14,727
sinusubukan mong ipasok tulad ng mga salita, andy.

1191
01:00:14,727 --> 01:00:16,810
Sabihin lang sabihin na ang isang
tunay na salita, ang salita, andy,

1192
01:00:16,810 --> 01:00:19,640
sa isang higanteng listahan ng A salita.

1193
01:00:19,640 --> 01:00:22,450
>> Kung mangyari ko lang na muling italaga
isang pointer mali, Oops,

1194
01:00:22,450 --> 01:00:24,940
may napupunta ang kabuuan ng
ang natitirang bahagi ng aking listahan ng mga link.

1195
01:00:24,940 --> 01:00:26,897
Ngayon ang tanging salita ko
magkaroon ay andy, at ngayon

1196
01:00:26,897 --> 01:00:29,230
lahat ng iba pang mga salita sa
diksiyunaryo ay nawala.

1197
01:00:29,230 --> 01:00:31,370
At kaya gusto mong tiyakin na ikaw ay
subaybayan ang lahat ng iyong mga payo

1198
01:00:31,370 --> 01:00:33,661
o ibang tao ikaw ay pagpunta upang makakuha ng
malaking problema sa iyong code.

1199
01:00:33,661 --> 01:00:35,840
Gumuhit ng mga bagay sa labas ng mabuti sa bawat hakbang.

1200
01:00:35,840 --> 01:00:37,870
Ito ay ginagawang mas madaling i-isip ng.

1201
01:00:37,870 --> 01:00:40,910
>> At sa wakas, na nais mong ma-
subukan ang iyong pagganap ng iyong mga programa

1202
01:00:40,910 --> 01:00:41,618
sa malaking board.

1203
01:00:41,618 --> 01:00:43,710
Kung ikaw guys kumuha ng isang
tingnan CS50 sa ngayon,

1204
01:00:43,710 --> 01:00:45,210
mayroon kaming kung ano ang tinatawag na ang malaking board.

1205
01:00:45,210 --> 01:00:50,200
Ito ay ang score sheet sa pinakamabilis
pagtiyak sa pagbaybay beses sa kabuuan ng lahat ng CS50

1206
01:00:50,200 --> 01:00:55,720
sa ngayon, tingin ko ang mga top tulad ng 10
beses sa tingin ko walong ng mga ito ay mga kawani.

1207
01:00:55,720 --> 01:00:57,960
Kami ay talagang nais mong guys na matalo sa amin.

1208
01:00:57,960 --> 01:01:00,870
>> Lahat tayo ay sinusubukan upang ipatupad
ang pinakamabilis na code hangga't maaari.

1209
01:01:00,870 --> 01:01:04,880
Gusto namin sa iyo guys upang subukan upang tutulan
amin at magpatupad ng mas mabilis kaysa sa ating lahat

1210
01:01:04,880 --> 01:01:05,550
maaari.

1211
01:01:05,550 --> 01:01:07,970
At kaya ito ay talagang
ang unang pagkakataon na hindi namin

1212
01:01:07,970 --> 01:01:12,680
na humihiling sa iyo guys na gawin ang isang pset na
Maaari mo ba talagang gawin sa kahit anong paraan

1213
01:01:12,680 --> 01:01:13,760
gusto mo.

1214
01:01:13,760 --> 01:01:17,730
>> Ako palaging sabihin, ito ay higit pa sa akin
sa isang solusyon sa tunay na buhay, di ba?

1215
01:01:17,730 --> 01:01:19,550
Sinasabi ko, hey, kailangan ko sa iyo na gawin ito.

1216
01:01:19,550 --> 01:01:21,380
Bumuo ng isang programa na ito para sa akin.

1217
01:01:21,380 --> 01:01:22,630
Gawin ito gayunpaman gusto mo.

1218
01:01:22,630 --> 01:01:24,271
Alam ko lang na gusto kong mag-ayuno.

1219
01:01:24,271 --> 01:01:25,770
Iyan ang iyong hamon para sa linggong ito.

1220
01:01:25,770 --> 01:01:27,531
Ikaw guys, kami ay pagpunta
upang bigyan ka ng isang gawain.

1221
01:01:27,531 --> 01:01:29,030
Kami ay pagpunta sa magbibigay sa iyo ng isang hamon.

1222
01:01:29,030 --> 01:01:31,559
At pagkatapos ito ay nakasalalay sa iyo guys
upang ganap na malaman lamang

1223
01:01:31,559 --> 01:01:34,100
ano ang pinakamabilis at pinaka
mahusay na paraan upang ipatupad ito.

1224
01:01:34,100 --> 01:01:34,600
Oo?

1225
01:01:34,600 --> 01:01:37,476
>> Madla: Pinapahintulutan namin na kung
wanted sa pananaliksik mas mabilis na paraan

1226
01:01:37,476 --> 01:01:40,821
gawin hash talahanayan online, maaari naming gawin
na at sipiin code ng ibang tao?

1227
01:01:40,821 --> 01:01:42,070
ANDI PENG: Oo, ganap na fine.

1228
01:01:42,070 --> 01:01:44,320
Kaya't kung ikaw guys basahin ang
spec, may isang linya

1229
01:01:44,320 --> 01:01:48,310
sa spec na nagsasabing kayo guys
ay libre upang magsaliksik ng hash

1230
01:01:48,310 --> 01:01:51,070
function sa kung ano ang ilang
ng mas mabilis na mga pag-andar hash

1231
01:01:51,070 --> 01:01:54,720
upang magpatakbo ng mga bagay-bagay sa pamamagitan ng bilang
hangga't banggitin mo na ang code.

1232
01:01:54,720 --> 01:01:57,220
Kaya ang ilang mga tao ay may mga naka
korte ang mabilis na paraan

1233
01:01:57,220 --> 01:02:00,250
ng paggawa ng spell dama, ng mabilis
paraan ng pag-iimbak ng impormasyon.

1234
01:02:00,250 --> 01:02:02,750
Lubos na nakasalalay sa iyo guys kung ikaw
nais na kunin lang iyon, di ba?

1235
01:02:02,750 --> 01:02:04,045
Tiyakin na ikaw ay binabanggit.

1236
01:02:04,045 --> 01:02:06,170
Ang hamon dito talagang
na kami ay sinusubukan upang subukan

1237
01:02:06,170 --> 01:02:09,750
ay siguraduhin na alam mo
ang iyong paraan sa paligid ng mga payo.

1238
01:02:09,750 --> 01:02:12,700
Bilang malayo bilang ka pagpapatupad
ang aktwal na pag-andar hash

1239
01:02:12,700 --> 01:02:15,070
at pagdating sa tulad ng
ang matematika upang gawin iyon,

1240
01:02:15,070 --> 01:02:17,570
ka guys ay maaaring magsaliksik ng kahit anong
pamamaraan online ka guys gusto.

1241
01:02:17,570 --> 01:02:17,996
Oo?

1242
01:02:17,996 --> 01:02:19,700
>> Madla: Maaari naming banggitin lamang
pamamagitan ng paggamit ng [hindi marinig]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI PENG: Oo.

1244
01:02:20,120 --> 01:02:22,328
Ikaw lamang ang maaaring, sa iyong mga komento,
maaari mong sipiin tulad ng, oh,

1245
01:02:22,328 --> 01:02:26,127
kinuha mula sa EK, EK,
yada, hash.

1246
01:02:26,127 --> 01:02:27,210
Sinuman ay may anumang mga katanungan?

1247
01:02:27,210 --> 01:02:29,694
Kami ay talagang breezed
sa pamamagitan ng seksyon na ngayon.

1248
01:02:29,694 --> 01:02:31,610
Ako ay magiging up para
sagutin ang mga tanong na rin.

1249
01:02:31,610 --> 01:02:36,570
>> Gayundin, tulad ng sinabi ko, office
oras ngayong gabi at bukas.

1250
01:02:36,570 --> 01:02:40,307
Ang spec this week ay talagang
napakadaling at super maikling magbasa.

1251
01:02:40,307 --> 01:02:43,140
Imumungkahi ko ang pagkuha ng isang pagtingin, makatarungan
basahin sa pamamagitan ng kabuuan ng mga ito.

1252
01:02:43,140 --> 01:02:45,730
>> At Zamyla talagang nagtuturo sa iyo sa
sa pamamagitan ng bawat isa sa mga pag-andar

1253
01:02:45,730 --> 01:02:49,796
kailangan mo upang ipatupad, at sa gayon ito ay
tunay, tunay na malinaw kung paano gawin ang lahat.

1254
01:02:49,796 --> 01:02:51,920
Lamang upang matiyak na ikaw ay
pagpapanatili ng track ng mga payo.

1255
01:02:51,920 --> 01:02:53,650
Ito ay isang lubhang mahirap pset.

1256
01:02:53,650 --> 01:02:56,744
>> Ito ay hindi mahirap dahil gusto,
naku, ang mga konsepto ay kaya marami pang iba

1257
01:02:56,744 --> 01:02:59,160
mahirap, o kailangan mong malaman
kaya magkano bagong syntax ng ang paraan

1258
01:02:59,160 --> 01:03:00,650
na ginawa mo para sa huling pset.

1259
01:03:00,650 --> 01:03:03,320
Pset na ito ay mahirap dahil
may mga kaya maraming mga payo,

1260
01:03:03,320 --> 01:03:06,980
at pagkatapos ay masyadong, napakadaling isang beses
ikaw ay may isang bug sa iyong code ay hindi ma

1261
01:03:06,980 --> 01:03:08,315
upang mahanap kung saan na bug ay.

1262
01:03:08,315 --> 01:03:13,200
>> At kaya kumpleto at salitain pananampalataya sa iyo
guys para makapag-matalo ang aming [hindi marinig]

1263
01:03:13,200 --> 01:03:13,700
baybay.

1264
01:03:13,700 --> 01:03:16,640
Ako tunay na may hindi anumang nakasulat mine
pa, ngunit ako isusulat ko.

1265
01:03:16,640 --> 01:03:19,070
Kaya habang ikaw ay sumusulat
iyo, Kukunin ko ay sumusulat mine.

1266
01:03:19,070 --> 01:03:21,070
Pupunta ako sa subukan na gumawa
minahan ng mas mabilis kaysa sa iyo.

1267
01:03:21,070 --> 01:03:23,940
Susubukan naming makita kung sino ang may pinakamabilis na isa.

1268
01:03:23,940 --> 01:03:27,340
>> At oo, ako makita ang lahat ng
kayo guys dito sa Martes.

1269
01:03:27,340 --> 01:03:29,510
Ako ay tatakbo sa isang uri tulad ng isang pset workshop.

1270
01:03:29,510 --> 01:03:32,640
Lahat ng mga seksyon na ito
linggo ay pset workshops,

1271
01:03:32,640 --> 01:03:36,690
kaya ikaw ay may isang lalaki ng maraming pagkakataon
para sa tulong, mga oras ng opisina gaya ng lagi,

1272
01:03:36,690 --> 01:03:41,330
at talagang ako inaabangan
pagbabasa ng lahat ng code sa iyong mga guys '.

1273
01:03:41,330 --> 01:03:44,160
Mayroon up quizzes ko dito kung ikaw
Gusto guys na dumating makakuha ng mga iyon.

1274
01:03:44,160 --> 01:03:45,880
Iyan na ang lahat.

1275
01:03:45,880 --> 01:03:48,180