1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:03,340
[Musika sa pag-play]

3
00:00:03,340 --> 00:00:11,020

4
00:00:11,020 --> 00:00:14,010
>> David MALAN: Ito ang CS50.

5
00:00:14,010 --> 00:00:18,090
At ito ay ang parehong sa simula at ang
end-- tulad ng literally-- halos dulo

6
00:00:18,090 --> 00:00:18,825
ng linggo anim.

7
00:00:18,825 --> 00:00:20,030

8
00:00:20,030 --> 00:00:22,640
>> Akala ko Gusto ko magbahagi ng
Medyo ng isang masaya katotohanan.

9
00:00:22,640 --> 00:00:25,370
Nakuha ko na ito up mula sa isang
itakda ang data ng nakaraang semestre ay.

10
00:00:25,370 --> 00:00:29,710
Maaari mong isipin na hinihiling namin sa iyo sa bawat
hanay ng form p kung pinapanood online

11
00:00:29,710 --> 00:00:31,580
o kung nag-aral sa tao.

12
00:00:31,580 --> 00:00:33,020
At dito ay ang data.

13
00:00:33,020 --> 00:00:34,710
Kaya ngayon ay napaka mahuhulaang.

14
00:00:34,710 --> 00:00:37,126
Pero gusto naming gastusin ng kaunti
ng panahon sa iyo gayunman.

15
00:00:37,126 --> 00:00:40,599
Gusto sinuman nais na haka-haka kung bakit ito
Ang graph ay kaya may mga tulis, hanggang pababa, pataas pababa,

16
00:00:40,599 --> 00:00:41,265
kaya tuloy-tuloy?

17
00:00:41,265 --> 00:00:42,980

18
00:00:42,980 --> 00:00:45,130
Ano ang bawat isa sa mga peak
at troughs kumakatawan?

19
00:00:45,130 --> 00:00:46,005
>> Madla: [hindi marinig]

20
00:00:46,005 --> 00:00:47,002

21
00:00:47,002 --> 00:00:47,835
David MALAN: Sa katunayan.

22
00:00:47,835 --> 00:00:50,900

23
00:00:50,900 --> 00:00:55,480
At higit pa amusingly, diyos ipagbawal,
hawakan namin ang isang aralin sa isang Biyernes

24
00:00:55,480 --> 00:00:58,960
sa simula ng semestre,
na kung ano ang namin makita ang mangyayari.

25
00:00:58,960 --> 00:01:03,430
Kaya ngayon, makibahagi namin sa ilang sandali
higit pa tungkol sa mga istraktura ng data.

26
00:01:03,430 --> 00:01:06,660
At upang magbigay ng higit pa sa isang matatag ka
modelo ng isip para sa mga problema sa limang,

27
00:01:06,660 --> 00:01:07,450
na ngayon ay out.

28
00:01:07,450 --> 00:01:10,817
Mga maling spelling, kung saan, kami ay
ibigay sa iyo ng isang text file ilang 100,000

29
00:01:10,817 --> 00:01:12,650
plus mga salitang Ingles, at
ka ng pagpunta sa may

30
00:01:12,650 --> 00:01:17,770
upang malaman kung paano cleverly-load ang mga ito
sa memory, sa RAM, gamit ang ilang data

31
00:01:17,770 --> 00:01:19,330
istraktura na iyong gusto.

32
00:01:19,330 --> 00:01:22,470
>> Ngayon isa tulad istraktura ng data ng dati
, ngunit marahil ay hindi dapat,

33
00:01:22,470 --> 00:01:25,630
ang medyo simplistic naka-link na listahan,
na ipinakilala namin huling beses.

34
00:01:25,630 --> 00:01:29,220
At isang naka-link na listahan ay nagkaroon ng hindi bababa sa
isang kalamangan sa isang array.

35
00:01:29,220 --> 00:01:32,096
Ano ang isang kalamangan ng
naka-link na listahan arguably?

36
00:01:32,096 --> 00:01:32,950
>> Madla: Insertion.

37
00:01:32,950 --> 00:01:33,908
>> David MALAN: Insertion.

38
00:01:33,908 --> 00:01:34,155

39
00:01:34,155 --> 00:01:35,196
Ano ang ibig mong sabihin sa pamamagitan ng na?

40
00:01:35,196 --> 00:01:37,872
>> Madla: Saanman sa kahabaan
ang listahan [hindi marinig].

41
00:01:37,872 --> 00:01:38,770
>> David MALAN: Mahusay.

42
00:01:38,770 --> 00:01:42,090
Kaya maaari mong ipasok ang isang elemento kung saan man
Gusto mo sa gitna ng listahan

43
00:01:42,090 --> 00:01:45,490
nang hindi na kinakailangang kaladkarin ang mga paa ng anumang bagay,
na aming Napagpasyahan ng mga, sa aming uuri-uri

44
00:01:45,490 --> 00:01:47,630
mga talakayan, ay hindi
nangangahulugang isang magandang bagay,

45
00:01:47,630 --> 00:01:51,200
dahil nangangailangan ng panahon upang aktwal na ilipat
lahat ng mga tao pakaliwa o pakanan.

46
00:01:51,200 --> 00:01:55,540
At kaya may naka-link na listahan, maaari kang
maglaan lamang sa malloc, isang bagong node,

47
00:01:55,540 --> 00:01:58,385
at pagkatapos ay i-update ng ilang mga
pointers-- dalawa, tatlo pagpapatakbo max--

48
00:01:58,385 --> 00:02:01,480
at magawa naming puwang ng isang tao
sa kahit saan sa isang listahan.

49
00:02:01,480 --> 00:02:03,550
>> Ano pa ay may pakinabang
tungkol sa isang naka-link na listahan?

50
00:02:03,550 --> 00:02:04,980

51
00:02:04,980 --> 00:02:05,659
Oo?

52
00:02:05,659 --> 00:02:06,534
>> Madla: [hindi marinig]

53
00:02:06,534 --> 00:02:07,538

54
00:02:07,538 --> 00:02:08,413
David MALAN: Perpekto.

55
00:02:08,413 --> 00:02:10,590

56
00:02:10,590 --> 00:02:11,090
Perpekto.

57
00:02:11,090 --> 00:02:12,070
Ito ay talagang dynamic.

58
00:02:12,070 --> 00:02:15,100
At na hindi ka paggawa,
nang maaga, sa ilang mga nakapirming laki

59
00:02:15,100 --> 00:02:18,750
tipak ng memorya, tulad ng gusto mong magkaroon ng
sa gamit ang isang array, ang bentahe ng na

60
00:02:18,750 --> 00:02:22,455
ay maaari mong maglaan ng node lamang sa
demand na sinusulit ang paggamit lamang ng mas maraming espasyo

61
00:02:22,455 --> 00:02:23,330
ng kung aktwal na kailangan mo.

62
00:02:23,330 --> 00:02:26,830
Sa pamamagitan ng kaibahan sa isang array, maaari kang
aksidenteng maglaan ng masyadong maliit.

63
00:02:26,830 --> 00:02:28,871
At pagkatapos lamang ito nangyayari
maging isang sakit sa ulo

64
00:02:28,871 --> 00:02:32,440
upang reallocate ng isang bagong mas malaking array, kopyahin
lahat ng bagay sa ibabaw, magbakante sa lumang array,

65
00:02:32,440 --> 00:02:33,990
at pagkatapos ay ilipat ang tungkol sa iyong negosyo.

66
00:02:33,990 --> 00:02:37,479
O mas masahol pa, maaari kang magtalaga ng paraan
higit pang memory kaysa sa aktwal na kailangan mo,

67
00:02:37,479 --> 00:02:40,520
at kaya ka ng pagpunta sa magkaroon ng isang napaka
sparsely-populated na array, kaya upang makipag-usap.

68
00:02:40,520 --> 00:02:44,350
>> Kaya ay nagbibigay sa iyo ng isang naka-link na listahan ng mga
bentahe ng dynamism at kakayahang umangkop

69
00:02:44,350 --> 00:02:46,080
may mga pagpapasok at pagtatanggal.

70
00:02:46,080 --> 00:02:48,000
Ngunit tiyak ay dapat na mayroong isang presyo na babayaran.

71
00:02:48,000 --> 00:02:50,000
Sa katunayan, ang isa sa mga tema
ginalugad sa pagsusulit zero

72
00:02:50,000 --> 00:02:52,430
ay isang pares ng mga trade-off
nasaksihan namin sa gayon ay malayo.

73
00:02:52,430 --> 00:02:56,161
Kaya kung ano ang isang presyong nabayaran o isang
downside ng isang naka-link na listahan?

74
00:02:56,161 --> 00:02:56,660
Oo.

75
00:02:56,660 --> 00:02:57,560
>> Madla: Walang random na pag-access.

76
00:02:57,560 --> 00:02:58,809
>> David MALAN: Walang random na pag-access.

77
00:02:58,809 --> 00:02:59,540
Ngunit na nagmamalasakit?

78
00:02:59,540 --> 00:03:01,546
Random na access ay hindi akma sa nakapanghihimok.

79
00:03:01,546 --> 00:03:02,421
>> Madla: [hindi marinig]

80
00:03:02,421 --> 00:03:04,865

81
00:03:04,865 --> 00:03:05,740
David MALAN: Eksaktong.

82
00:03:05,740 --> 00:03:07,580
Kung gusto mong magkaroon ng
isang tiyak na algorithm--

83
00:03:07,580 --> 00:03:10,170
at ipaalam sa akin aktwal na ipanukala
binary paghahanap sa partikular, na

84
00:03:10,170 --> 00:03:12,600
ay isa na ginagamit namin ang isang medyo bit--
kung hindi mo na kailangang random na pag-access,

85
00:03:12,600 --> 00:03:15,516
hindi mo maaaring gawin iyon simpleng palatuusan
ng paghahanap tulad ng gitnang elemento

86
00:03:15,516 --> 00:03:16,530
at tumatalon karapatang ito.

87
00:03:16,530 --> 00:03:20,239
Sa halip ay mayroon kang upang magsimula sa unang
elemento at linearly naghahanap mula sa kaliwa

88
00:03:20,239 --> 00:03:22,780
sa kanan kung gusto mong mahanap ang
gitna o anumang iba pang mga elemento.

89
00:03:22,780 --> 00:03:24,410
>> Madla: marahil tumatagal ng higit pang memory.

90
00:03:24,410 --> 00:03:25,040
>> David MALAN: Dadalhin higit pang memory.

91
00:03:25,040 --> 00:03:27,464
Saan ang karagdagang
gastos na nagmumula sa sa memory?

92
00:03:27,464 --> 00:03:28,339
>> Madla: [hindi marinig]

93
00:03:28,339 --> 00:03:32,566

94
00:03:32,566 --> 00:03:33,440
David MALAN: Eksaktong.

95
00:03:33,440 --> 00:03:35,679
Sa kasong ito dito, nagkaroon kami
isang listahan na naka-link para sa integer,

96
00:03:35,679 --> 00:03:37,470
at pa naka-pagdodoble namin
ang dami ng memorya

97
00:03:37,470 --> 00:03:39,680
kailangan naming sa pamamagitan ng pag-iimbak din ang mga payo.

98
00:03:39,680 --> 00:03:42,090
Ngayon mas mababa ng isang malaking bilang deal
ang iyong structs makakuha ng mas malaki

99
00:03:42,090 --> 00:03:45,320
at tapos ka sa pag-iimbak hindi isang numero ngunit
siguro isang mag-aaral o ilang iba pang mga bagay.

100
00:03:45,320 --> 00:03:46,880
Ngunit ang punto ay tiyak na nanatiling.

101
00:03:46,880 --> 00:03:49,421
At sa gayon ang isang bilang ng mga pagpapatakbo
sa naka-link na listahan ay tinawag

102
00:03:49,421 --> 00:03:50,570
ay malaki O ng n-- linear.

103
00:03:50,570 --> 00:03:54,730
Mga bagay tulad ng paghahanap na pagpapasok o
o pagtanggal sa kaso ng isang elemento

104
00:03:54,730 --> 00:03:57,720
ang nangyari sa maging sa pinakadulo ng
ang listahan ng kung ito ay pinagsunod-sunod o hindi.

105
00:03:57,720 --> 00:04:01,167
>> Minsan maaari kang makakuha ng masuwerteng at sa
kaya mas mababang mga hangganan sa mga pagpapatakbong ito

106
00:04:01,167 --> 00:04:04,250
maaari ring maging pare-pareho ang oras kung ikaw ay
laging naghahanap sa unang elemento,

107
00:04:04,250 --> 00:04:05,070
halimbawa.

108
00:04:05,070 --> 00:04:09,360
Ngunit sa huli, aming ipinangako
upang makamit ang banal na Kopita

109
00:04:09,360 --> 00:04:12,630
ng mga istraktura ng data, o
ang ilang mga pagtatantya nito,

110
00:04:12,630 --> 00:04:14,290
sa paraan ng pare-pareho ang oras.

111
00:04:14,290 --> 00:04:17,579
Puwede ba kaming mahanap ang mga elemento o magdagdag ng mga elemento
o alisin ang mga elemento mula sa isang listahan?

112
00:04:17,579 --> 00:04:19,059
Ay dapat namin makita pa sa lalong madaling panahon.

113
00:04:19,059 --> 00:04:21,100
At ito ay lumiliko ang isa na
ng mga mekanismo kami

114
00:04:21,100 --> 00:04:23,464
pagpunta sa simulan na gamitin ngayon,
taunang paggamit sa p-set limang,

115
00:04:23,464 --> 00:04:24,630
ay talagang kaakit-akit na pamilyar.

116
00:04:24,630 --> 00:04:27,430
Halimbawa, kung ito ay isang bungkos
ng mga aklat pagsusulit, ang bawat isa

117
00:04:27,430 --> 00:04:29,660
May isang mag-aaral muna ni
pangalanan at apelyido dito,

118
00:04:29,660 --> 00:04:31,820
at ako kunin ang mga ito mula sa
sa dulo ng isang pagsusulit,

119
00:04:31,820 --> 00:04:33,746
at ang mga ito ay ang lahat ng kaakit-akit
magkano sa isang random na pagkakasunod-sunod,

120
00:04:33,746 --> 00:04:36,370
at gusto naming pumunta tungkol sa pag-uuri
ang mga pagsusulit nang sa gayon ay isang beses gradong

121
00:04:36,370 --> 00:04:38,661
ito ay isang marami lang mas madali at
Mas mabilis na ipasa ang mga ito pabalik out

122
00:04:38,661 --> 00:04:40,030
mag-aaral ayon sa abakada.

123
00:04:40,030 --> 00:04:42,770
Ano ang gusto iyong instincts maging
para sa isang tumpok ng mga pagsusulit na tulad nito?

124
00:04:42,770 --> 00:04:45,019
>> Well, kung ikaw ay tulad ng sa akin, ikaw
Maaaring makita na ito ay m,

125
00:04:45,019 --> 00:04:48,505
kaya ako pagpunta sa uri ng ilagay ito sa,
kung ito ang aking talahanayan o ang aking palapag kung saan

126
00:04:48,505 --> 00:04:50,650
Ako nagkakalat bagay
out-- o ang aking array really--

127
00:04:50,650 --> 00:04:52,210
Maaari ko bang ilagay ang lahat ng mga Ms doon.

128
00:04:52,210 --> 00:04:52,710
Oh.

129
00:04:52,710 --> 00:04:55,020
Narito ang isang A. Kaya maaari ko
ilagay ang Tulad ng sa paglipas dito.

130
00:04:55,020 --> 00:04:55,520
Oh.

131
00:04:55,520 --> 00:04:57,980
Narito ang isa pang A. pupuntahan ko
upang ilagay na sa paglipas dito.

132
00:04:57,980 --> 00:05:02,490
Narito ang isang Z. Narito ang isa pang M. At kaya
Maaaring simulan ko na gawin piles tulad nito.

133
00:05:02,490 --> 00:05:06,620
At pagkatapos ay marahil Gusto ko pumunta sa ibang pagkakataon
at uri ng napaka-nitpicky-.ly pag-uuri

134
00:05:06,620 --> 00:05:07,710
ang mga indibidwal na piles.

135
00:05:07,710 --> 00:05:11,300
Ngunit ang punto ay gusto ko bang tingnan
sa input na ako kamay

136
00:05:11,300 --> 00:05:14,016
at gusto kong gumawa ng ilang kinakalkula
batay sa input na desisyon.

137
00:05:14,016 --> 00:05:15,640
Kung nagsisimula ito sa A, ilagay ito doon.

138
00:05:15,640 --> 00:05:18,980
Kung nagsisimula ito sa Z, ilagay ito sa paglipas ng
doon, at lahat ng bagay sa pagitan.

139
00:05:18,980 --> 00:05:22,730
>> Kaya ito ay isang diskarte na
Sa pangkalahatan ay kilala bilang hashing-- H-A-S-H--

140
00:05:22,730 --> 00:05:26,550
na sa pangkalahatan ay nangangahulugan na ang pagkuha ng
-input at paggamit ng pag-input na upang makalkula

141
00:05:26,550 --> 00:05:30,940
isang halaga, sa pangkalahatan ay isang numero, at na
bilang na ito ay index sa isang imbakan

142
00:05:30,940 --> 00:05:32,260
lalagyan, tulad ng isang array.

143
00:05:32,260 --> 00:05:35,490
Kaya sa ibang salita, maaaring mayroon akong
hash, tulad ng ginagawa ko sa aking ulo,

144
00:05:35,490 --> 00:05:37,940
na kung makikita ko ang isang tao ay
pangalan na nagsisimula sa A,

145
00:05:37,940 --> 00:05:40,190
Pupunta ako sa map na
sa zero sa aking ulo.

146
00:05:40,190 --> 00:05:44,160
At kung makikita ko ang isang tao na may Z, ako
pagpunta sa map na sa 25 sa aking ulo

147
00:05:44,160 --> 00:05:46,220
at pagkatapos ay ilagay na sa
ang huling pinaka-pile.

148
00:05:46,220 --> 00:05:50,990
>> Ngayon, kung sa tingin mo tungkol sa hindi aking utak
ngunit isang programa C, kung ano ang mga numero ng dati

149
00:05:50,990 --> 00:05:53,170
umasa sa upang makamit ang parehong resulta?

150
00:05:53,170 --> 00:05:55,594
Sa ibang salita, kung
Nagkaroon ng ASCII na character na A,

151
00:05:55,594 --> 00:05:57,510
paano ko sa iyo na matukoy
ano bucket upang ilagay ito sa?

152
00:05:57,510 --> 00:05:59,801
Malamang na hindi nais na
ilagay ito sa bucket 65, na

153
00:05:59,801 --> 00:06:01,840
ay magiging tulad ng doon
para sa walang magandang dahilan.

154
00:06:01,840 --> 00:06:04,320
Saan mo nais na ilagay ang isang
sa mga tuntunin ng halaga ASCII nito?

155
00:06:04,320 --> 00:06:05,600

156
00:06:05,600 --> 00:06:08,920
Saan ang gusto mong gawin sa kanyang ASCII
halaga upang makabuo ng isang mas matalinong bucket

157
00:06:08,920 --> 00:06:09,480
upang ilagay ito sa?

158
00:06:09,480 --> 00:06:10,206
>> Madla: Minus A.

159
00:06:10,206 --> 00:06:10,956
>> David MALAN: Oo.

160
00:06:10,956 --> 00:06:13,190
Kaya minus A o minus
partikular na 65 kung ito ay

161
00:06:13,190 --> 00:06:18,240
ng kapital A. O 98 kung
ito ay isang maliit na mga a.

162
00:06:18,240 --> 00:06:21,300
At upang ang daan sa amin na, napaka
nang simple at napaka-arithmetically,

163
00:06:21,300 --> 00:06:23,260
maglagay ng isang bagay sa isang bucket tulad na.

164
00:06:23,260 --> 00:06:26,010
Kaya ito ay lumiliko ang aktwal na namin gawin
ito pati na rin kahit na ang mga pagsusulit.

165
00:06:26,010 --> 00:06:29,051
>> Kaya maaari mong isipin ang mo ang iyong circled
Pangalan ng pagtuturo kapwa sa mga pabalat.

166
00:06:29,051 --> 00:06:32,270
At pangalan ng tf ni ay isinaayos
sa mga hanay na ito ayon sa abakada,

167
00:06:32,270 --> 00:06:34,400
well, naniniwala ito o hindi,
kapag ang lahat ng 80 plus sa atin

168
00:06:34,400 --> 00:06:37,800
Nakakuha magkasama ang iba pang mga gabi sa grado,
ang huling hakbang sa aming proseso grading

169
00:06:37,800 --> 00:06:41,830
ay ang pag-hash ang pagsusulit sa isang malaking
espasyo ng sahig sa [hindi marinig]

170
00:06:41,830 --> 00:06:45,110
at upang mag-ipon ng mga pagsusulit ng lahat out
sa eksaktong pagkakasunud-sunod ng kanilang tf ni

171
00:06:45,110 --> 00:06:47,700
mga pangalan sa cover, dahil
pagkatapos ay ito ay isang mas madaling para sa amin

172
00:06:47,700 --> 00:06:51,290
upang maghanap sa pamamagitan ng na ang paggamit ng linear
maghanap o ilang mga uri ng talino

173
00:06:51,290 --> 00:06:54,050
para sa isang tf upang makita ang kanyang o
mga pagsusulit sa kanyang mga mag-aaral '.

174
00:06:54,050 --> 00:06:56,060
>> Kaya ito ideya ng hashing
na makikita mo ay

175
00:06:56,060 --> 00:07:00,520
masyadong malakas ay talagang kaakit-akit
palasak at napaka madaling maunawaan,

176
00:07:00,520 --> 00:07:03,000
tulad marahil hatiin at
gumahis ay nasa linggo zero.

177
00:07:03,000 --> 00:07:05,250
Ako mabilis inaabangan ang panahon na ang hackathon
ng dalawang taon na ang nakakaraan.

178
00:07:05,250 --> 00:07:08,040
Ito ay Zamyla at isang pares ng mga
iba pang mga mag-aaral na pagbati kawani

179
00:07:08,040 --> 00:07:09,030
bilang sila ay dumating sa.

180
00:07:09,030 --> 00:07:12,680
At nagkaroon kami ng buong bungkos ng natitiklop
mga talahanayan doon sa mga name tag.

181
00:07:12,680 --> 00:07:15,380
At kami ay isinaayos ng mga name tag
may tulad ng Tulad ng doon

182
00:07:15,380 --> 00:07:16,690
at ang Zs doon.

183
00:07:16,690 --> 00:07:20,350
At kaya isa sa mga TFs napaka cleverly
nagsulat na ito bilang ang mga tagubilin

184
00:07:20,350 --> 00:07:21,030
para sa araw.

185
00:07:21,030 --> 00:07:24,480
At sa linggo 12 ng semestre na ito
lahat ginawa perpektong pakiramdam at ang lahat

186
00:07:24,480 --> 00:07:25,310
Alam kung ano ang gagawin.

187
00:07:25,310 --> 00:07:27,900
Ngunit anumang oras ikaw ay
nakapila sa parehong paraan,

188
00:07:27,900 --> 00:07:30,272
ka sa pagpapatupad ng mga
parehong kuru-kuro ng isang hash.

189
00:07:30,272 --> 00:07:31,730
Kaya gawing pormal natin ito nang kaunti ipaalam.

190
00:07:31,730 --> 00:07:32,890
Narito ang isang array.

191
00:07:32,890 --> 00:07:36,820
Ito ay iginuhit upang maging isang maliit na
malawak lamang sa ilarawan, biswal,

192
00:07:36,820 --> 00:07:38,920
na maaari naming ilagay ang mga string
sa isang bagay na katulad nito.

193
00:07:38,920 --> 00:07:41,970
At ito array ay
malinaw na sukat ng 26 kabuuang.

194
00:07:41,970 --> 00:07:43,935
At ang bagay ay tinatawag na
talahanayan nagkataon.

195
00:07:43,935 --> 00:07:48,930
Ngunit ito lamang ang pag-awit ng artist
ng kung ano ang maaaring maging isang hash table.

196
00:07:48,930 --> 00:07:52,799
>> Kaya isang hash talahanayan ngayon ay pagpunta sa
maging isang mas mataas na istraktura ng data na antas.

197
00:07:52,799 --> 00:07:54,840
Sa pagtatapos ng araw
kami ay tungkol sa upang makita na iyong

198
00:07:54,840 --> 00:07:58,700
Maaari ipatupad ang hash talahanayan, na
ay halos tulad ng linya ng check-in

199
00:07:58,700 --> 00:08:02,059
sa isang hackathon tulad ito
talahanayan na ginagamit para sa pagbubukod-bukod ng mga aklat pagsusulit.

200
00:08:02,059 --> 00:08:03,850
Ngunit isang hash talahanayan ay
uri ng mga ito mataas na antas

201
00:08:03,850 --> 00:08:08,250
konsepto na maaaring gamitin ng isang array
sa ilalim ng hood sa ipatupad ito,

202
00:08:08,250 --> 00:08:11,890
o maaaring gumamit ng isang listahan ng haba, o kahit na
marahil ilang iba pang mga istraktura ng data.

203
00:08:11,890 --> 00:08:15,590
At ngayon na ang theme-- pagkuha
ang ilan sa mga pangunahing sangkap

204
00:08:15,590 --> 00:08:18,310
tulad ng isang array at ang gusaling ito
-block na ngayon ng isang listahan ng haba

205
00:08:18,310 --> 00:08:21,740
at makita kung ano pa ang maaari naming bumuo ng
sa itaas ng mga, tulad ng mga sangkap

206
00:08:21,740 --> 00:08:26,550
sa isang recipe, na ginagawang higit pa at higit pa
kawili-wili at kapaki-pakinabang huling resulta.

207
00:08:26,550 --> 00:08:28,680
>> Kaya gamit ang hash talahanayan
maaari naming ipatupad ito

208
00:08:28,680 --> 00:08:32,540
sa memory pictorially na tulad nito, ngunit
kung paano maaaring aktwal na ito ay naka-code up?

209
00:08:32,540 --> 00:08:33,789
Well, siguro ay ito bilang simple.

210
00:08:33,789 --> 00:08:38,270
Kung kapasidad sa lahat ng mga pag-cap, ay lamang
ilang constant-- halimbawa 26,

211
00:08:38,270 --> 00:08:42,030
para sa 26 titik ng alphabet--
Maaaring tumawag ako variable talahanayan aking,

212
00:08:42,030 --> 00:08:45,630
at maaaring i-claim ko na pupuntahan ko
ilagay char bituin sa doon, o string.

213
00:08:45,630 --> 00:08:49,880
Kaya ito ay kasing simple ng ito kung
nais na ipatupad ng hash table.

214
00:08:49,880 --> 00:08:51,490
At pa, ito ay talagang lamang ng isang array.

215
00:08:51,490 --> 00:08:53,198
Ngunit muli, isang hash
talahanayan na ngayon kung ano ang kami ay

216
00:08:53,198 --> 00:08:57,470
tumawag sa isang abstract na uri ng data na lamang
uri ng isang haka-haka layering sa tuktok

217
00:08:57,470 --> 00:09:00,780
ng isang bagay na mas pangmundo
ngayon gusto ang isang array.

218
00:09:00,780 --> 00:09:02,960
>> Ngayon, paano mo kami
tungkol sa paglutas ng mga problema?

219
00:09:02,960 --> 00:09:06,980
Well, mas maaga ako ay nagkaroon ng luxury
ng pagkakaroon ng sapat na espasyo talahanayan dito

220
00:09:06,980 --> 00:09:09,460
nang sa gayon ay maaari ko bang ilagay ang
mga pagsusulit sa kahit saan ko gusto.

221
00:09:09,460 --> 00:09:10,620
Kaya Tulad ng maaaring pumunta dito.

222
00:09:10,620 --> 00:09:12,100
Baka pumunta dito Zs.

223
00:09:12,100 --> 00:09:13,230
Ms maaaring umalis dito.

224
00:09:13,230 --> 00:09:14,740
At pagkatapos ay nagkaroon ako ng ilang dagdag na espasyo.

225
00:09:14,740 --> 00:09:18,740
Ngunit ito ay isang bit ng isang impostor kanan
ngayon dahil table na ito, kung ako talaga

226
00:09:18,740 --> 00:09:22,720
naisip ng ito bilang isang array, ay lamang
magiging ng ilang mga nakapirming laki.

227
00:09:22,720 --> 00:09:25,380
>> Kaya technically, kung hilahin ko
up ng isa pang pagsusulit ng mag-aaral

228
00:09:25,380 --> 00:09:28,490
at tingnan, oh, ng taong ito
pangalan ay nagsisimula sa isang A masyadong,

229
00:09:28,490 --> 00:09:30,980
Ako uri ng nais na ilagay ito doon.

230
00:09:30,980 --> 00:09:34,740
Ngunit sa lalong madaling ko bang ilagay doon, kung
talahanayang ito sa katunayan ay kumakatawan sa isang array,

231
00:09:34,740 --> 00:09:37,840
Pupunta ako sa i-override o clobbering
kung sinuman ang pagsusulit ng mag-aaral na ito ay.

232
00:09:37,840 --> 00:09:38,340
Mag-right?

233
00:09:38,340 --> 00:09:41,972
Kung ito ay isang array, tanging isang bagay na maaari
pumunta sa bawat isa sa mga cell o mga elemento.

234
00:09:41,972 --> 00:09:43,680
At kaya ko uri ng mayroon
upang pumili at piliin ang.

235
00:09:43,680 --> 00:09:45,735
>> Ngayon mas maaga ako uri ng
ginulangan at ginawa ito o ko

236
00:09:45,735 --> 00:09:47,526
lamang uri ng nakasalansan
ang mga ito sa itaas ng bawat isa.

237
00:09:47,526 --> 00:09:49,170
Ngunit na hindi pagpunta sa lumipad sa code.

238
00:09:49,170 --> 00:09:52,260
Kaya kung saan maaari ko bang ilagay ang
pangalawang mag-aaral na ang pangalan

239
00:09:52,260 --> 00:09:54,964
ay isang kung ang lahat ko ay nagkaroon ay ito
magagamit na puwang ng talahanayan?

240
00:09:54,964 --> 00:09:57,880
At ginamit ko ang tatlong mga puwang at ito
Mukhang mayroong ilang iba.

241
00:09:57,880 --> 00:09:58,959
Ano ang maaari mong gawin?

242
00:09:58,959 --> 00:09:59,834
Madla: [hindi marinig]

243
00:09:59,834 --> 00:10:00,565

244
00:10:00,565 --> 00:10:01,315
David MALAN: Oo.

245
00:10:01,315 --> 00:10:02,370
Siguro hayaan panatilihin ito ng mga simpleng lamang.

246
00:10:02,370 --> 00:10:02,660
Mag-right?

247
00:10:02,660 --> 00:10:04,243
Hindi ito magkasya kung saan ako gustong ilagay ito.

248
00:10:04,243 --> 00:10:07,450
Kaya ako pagpunta sa ilagay ito
technically kung saan ang isang B ay pupunta.

249
00:10:07,450 --> 00:10:09,932
Ngayon, siyempre, ako nagsisimula
upang ipinta ang aking sarili sa isang sulok.

250
00:10:09,932 --> 00:10:11,890
Kung nakuha ko sa isang mag-aaral
ang pangalan ay talagang B,

251
00:10:11,890 --> 00:10:14,840
ngayon B ay pagpunta sa ililipat ng kaunti
pasulong, tulad ng maaaring mangyari, yep,

252
00:10:14,840 --> 00:10:17,530
kung ito ay isang B, ngayon ito ay may upang pumunta dito.

253
00:10:17,530 --> 00:10:20,180
>> At kaya ito masyadong mabilis
maaaring maging problema,

254
00:10:20,180 --> 00:10:23,850
ngunit ito ay isang diskarte na aktwal na
ay tinutukoy na linear probing,

255
00:10:23,850 --> 00:10:26,650
kung saan isaalang-alang mo lamang ang iyong
array na sa kahabaan ng linya.

256
00:10:26,650 --> 00:10:29,680
At mo lamang uri ng suriin o
siyasatin bawat magagamit na elemento

257
00:10:29,680 --> 00:10:31,360
naghahanap para sa isang magagamit na lugar.

258
00:10:31,360 --> 00:10:34,010
At sa lalong madaling mahanap ka
isa, i-drop mo ito doon.

259
00:10:34,010 --> 00:10:38,390
>> Ngayon, ang presyo na binabayaran ngayon
para sa solusyon na ito ay kung ano?

260
00:10:38,390 --> 00:10:41,300
Mayroon kaming nakapirming laki ng array,
at kapag ipasok ko pangalan

261
00:10:41,300 --> 00:10:44,059
sa ito, hindi bababa sa una, kung ano ang
ang oras ng paggana ng pagpapasok

262
00:10:44,059 --> 00:10:46,350
para sa paglalagay ng mga mag-aaral '
mga pagsusulit sa kanang bucket?

263
00:10:46,350 --> 00:10:48,710

264
00:10:48,710 --> 00:10:50,002
Big O kung ano?

265
00:10:50,002 --> 00:10:51,147
>> Madla: n.

266
00:10:51,147 --> 00:10:52,480
David MALAN: Narinig ko malaking O ng n.

267
00:10:52,480 --> 00:10:53,530

268
00:10:53,530 --> 00:10:54,300
Hindi totoo.

269
00:10:54,300 --> 00:10:56,490
Ngunit kami ay mang-ulol hiwalayin
kung bakit sa sandali lamang.

270
00:10:56,490 --> 00:10:57,702
Ano pa ang maaari itong maging?

271
00:10:57,702 --> 00:10:58,755
>> Madla: [hindi marinig]

272
00:10:58,755 --> 00:11:00,380
David MALAN: At hayaan mo akong gawin ito biswal.

273
00:11:00,380 --> 00:11:04,720
Kaya ipagpalagay na ito ay ang titik S.

274
00:11:04,720 --> 00:11:05,604
>> Madla: Ito ay isa.

275
00:11:05,604 --> 00:11:06,520
David MALAN: Ito ay isa.

276
00:11:06,520 --> 00:11:06,710
Mag-right?

277
00:11:06,710 --> 00:11:08,950
Ito ay isang array, na
Nangangahulugan mayroon kaming mga random na pag-access.

278
00:11:08,950 --> 00:11:11,790
At kung sa tingin namin ng ito
bilang zero at ito bilang 25,

279
00:11:11,790 --> 00:11:13,800
at Napagtanto namin na,
naku, narito ang aking input S,

280
00:11:13,800 --> 00:11:16,350
Maaari ko tiyak na mag-convert
S, isang character na ASCII,

281
00:11:16,350 --> 00:11:18,540
sa isang katumbas na dami
sa pagitan ng zero at 25

282
00:11:18,540 --> 00:11:20,910
at pagkatapos ay agad-agad
ilagay ito kung saan ito ay kabilang.

283
00:11:20,910 --> 00:11:26,120
>> Ngunit siyempre, sa lalong madaling makakuha ako sa
pangalawang tao kung sino ang pangalan ay A o B o C

284
00:11:26,120 --> 00:11:29,300
Sa kalaunan, kung iyong ginamit ko ang
linear probing bilang aking solusyon,

285
00:11:29,300 --> 00:11:31,360
ang oras ng paggana ng
pagpapasok sa pinakamasamang sitwasyon

286
00:11:31,360 --> 00:11:33,120
ay talagang pagpunta sa malipat sa kung anong?

287
00:11:33,120 --> 00:11:34,270

288
00:11:34,270 --> 00:11:36,045
At ko narinig ito dito
tama nang maaga.

289
00:11:36,045 --> 00:11:36,920
Madla: [hindi marinig]

290
00:11:36,920 --> 00:11:41,620
David MALAN: Kaya ito ay sa katunayan n-sabay
mayroon kang sapat na malaki ang hanay ng data.

291
00:11:41,620 --> 00:11:44,410
Kaya, sa isang banda, kung
ang iyong mga array ay sapat na malaki

292
00:11:44,410 --> 00:11:48,287
at ang iyong data ay kalat-kalat sapat, mo
makuha ang magandang pare-pareho ang oras.

293
00:11:48,287 --> 00:11:50,620
Ngunit sa lalong madaling simulan mo
pagkuha ng higit pa at higit pang mga elemento,

294
00:11:50,620 --> 00:11:53,200
at istatistika lamang kang makakuha ng
higit pang mga tao na may sulat

295
00:11:53,200 --> 00:11:56,030
Ang bilang kanilang pangalan o ang titik
B, ito ay maaaring potensyal na

296
00:11:56,030 --> 00:11:57,900
malipat sa isang bagay na mas linear.

297
00:11:57,900 --> 00:11:59,640
Kaya hindi pa perpekto.

298
00:11:59,640 --> 00:12:00,690
Kaya maaari naming gawin mas mahusay?

299
00:12:00,690 --> 00:12:03,210
>> Well, kung ano ang aming
solusyon bago kung kailan namin

300
00:12:03,210 --> 00:12:06,820
nais na magkaroon ng higit pa sa dynamism
isang bagay tulad ng isang array pinapayagan?

301
00:12:06,820 --> 00:12:08,085

302
00:12:08,085 --> 00:12:08,960
Madla: [hindi marinig]

303
00:12:08,960 --> 00:12:10,030
David MALAN: Ano ang ipakilala kami?

304
00:12:10,030 --> 00:12:10,530
Oo.

305
00:12:10,530 --> 00:12:11,430
Kaya naka-link na listahan.

306
00:12:11,430 --> 00:12:14,430
Well, sabihin makita kung ano ang isang naka-link
maaaring gawin listahan para sa amin sa halip.

307
00:12:14,430 --> 00:12:17,630
Well, hayaan mo akong magpanukala na namin
gumuhit ng larawan tulad ng sumusunod.

308
00:12:17,630 --> 00:12:19,620
Ngayon ito ay isang iba't ibang
larawan mula sa isang halimbawa

309
00:12:19,620 --> 00:12:24,750
mula sa ibang teksto, talaga, na
ay aktwal na paggamit ng isang hanay ng mga laki 31.

310
00:12:24,750 --> 00:12:28,220
At lamang ang may-akda
nagpasyang hash string

311
00:12:28,220 --> 00:12:32,430
hindi batay sa mga pangalan ng tao,
ngunit batay sa kanilang birthdates.

312
00:12:32,430 --> 00:12:35,680
Hindi isinasaalang-alang ng buwan, sila ay may korte
kung gumagamit ka ipinanganak sa unang ng buwan

313
00:12:35,680 --> 00:12:39,580
o ang ika-31 ng buwan, ang may-akda
ay hash batay sa halaga na iyon,

314
00:12:39,580 --> 00:12:44,154
upang ikalat ang mga pangalan out ng kaunti
higit pa kaysa sa maaaring payagan lamang 26 spot.

315
00:12:44,154 --> 00:12:47,320
At marahil ito ay isang kaunti pa uniporme
kaysa sa pagpunta sa alpabetikong titik,

316
00:12:47,320 --> 00:12:50,236
dahil sa kurso doon ay marahil
higit pang mga tao sa mundo na may mga pangalan

317
00:12:50,236 --> 00:12:54,020
na panimula sa isang tiyak kaysa sa
ilang iba pang mga titik ng alpabeto.

318
00:12:54,020 --> 00:12:56,380
Kaya marahil ito ay isang maliit na
higit uniporme, sa pag-aakala

319
00:12:56,380 --> 00:12:58,640
isang pare-parehong pamamahagi
ng sanggol sa isang buwan.

320
00:12:58,640 --> 00:12:59,990
>> Ngunit, siyempre, ito ay hindi lubos na pagsisisi pa rin.

321
00:12:59,990 --> 00:13:00,370
Mag-right?

322
00:13:00,370 --> 00:13:01,370
Nagkakaroon kami ng collisions.

323
00:13:01,370 --> 00:13:04,680
Maraming tao sa
istraktura ng data ay pa rin

324
00:13:04,680 --> 00:13:08,432
pagkakaroon ng parehong petsa ng kapanganakan ng hindi bababa sa
ikaw ay hindi isinasaalang-alang ng buwan.

325
00:13:08,432 --> 00:13:09,640
Ngunit kung ano ang ginawa ng may-akda?

326
00:13:09,640 --> 00:13:13,427
Well, mukhang mayroon kaming isang array
sa kaliwang gilid iginuhit patayo,

327
00:13:13,427 --> 00:13:15,010
ngunit ito lamang ay pag-awit ng artist.

328
00:13:15,010 --> 00:13:18,009
Hindi mahalaga kung ano ang direksyon mo
gumuhit ng isang array, ito ay isang array pa rin.

329
00:13:18,009 --> 00:13:20,225
Ano ang isang array ng wari?

330
00:13:20,225 --> 00:13:21,500
>> Madla: Naka-link na listahan.

331
00:13:21,500 --> 00:13:21,650
>> David MALAN: Oo.

332
00:13:21,650 --> 00:13:23,490
Mukhang ito ay isang
hanay ng mga naka-link na listahan.

333
00:13:23,490 --> 00:13:26,490
Kaya muli, sa punto ng pag-uuri
ng paggamit ng mga kaayusan data ngayon

334
00:13:26,490 --> 00:13:28,550
bilang sangkap sa mas maraming
kagiliw-giliw na mga solusyon,

335
00:13:28,550 --> 00:13:30,862
maaari mong ganap na kumuha ng isang
pangunahing, tulad ng isang array,

336
00:13:30,862 --> 00:13:33,320
at pagkatapos gumawa ng isang bagay na higit pa
kagiliw-giliw na tulad ng isang naka-link na listahan

337
00:13:33,320 --> 00:13:36,660
at kahit pagsamahin ang mga ito sa isang pantay na
mas kawili-wiling istraktura ng data.

338
00:13:36,660 --> 00:13:39,630
At sa katunayan, ito masyadong gagawin
tawagin ng hash table,

339
00:13:39,630 --> 00:13:42,610
kung saan ang array ay
talaga ang hash talahanayan,

340
00:13:42,610 --> 00:13:45,600
ngunit na hash talahanayan ay
chain, kaya upang magsalita,

341
00:13:45,600 --> 00:13:50,220
na maaaring lumaki o Paliitin batay sa
numero ng mga elemento na gusto mong ipasok.

342
00:13:50,220 --> 00:13:52,990
>> Ngayon, nang naaayon, kung ano ang
ang oras tumatakbo na ngayon?

343
00:13:52,990 --> 00:13:58,030
Kung gusto kong ipasok ang isang tao
na ang kaarawan ay Oktubre 31,

344
00:13:58,030 --> 00:13:59,040
kung saan ay siya pumunta?

345
00:13:59,040 --> 00:14:00,530

346
00:14:00,530 --> 00:14:01,030
Lahat ng karapatan.

347
00:14:01,030 --> 00:14:02,819
Sa ilalim napaka kung saan sinasabi nito na 31.

348
00:14:02,819 --> 00:14:03,610
At iyon ay perpekto.

349
00:14:03,610 --> 00:14:05,060
Iyon ay pare-pareho ang oras.

350
00:14:05,060 --> 00:14:08,760
Ngunit paano kung malaman naming ibang tao
na ang kaarawan ay, sabihin makita,

351
00:14:08,760 --> 00:14:10,950
Oktubre, Nobyembre, Disyembre 31?

352
00:14:10,950 --> 00:14:12,790
Saan ay siya pagpunta sa pumunta?

353
00:14:12,790 --> 00:14:13,290
Parehong bagay.

354
00:14:13,290 --> 00:14:13,970
Dalawang hakbang na.

355
00:14:13,970 --> 00:14:15,303
Iyon ay pare-pareho kahit na hindi ito?

356
00:14:15,303 --> 00:14:16,360

357
00:14:16,360 --> 00:14:16,860
Lahat ng karapatan.

358
00:14:16,860 --> 00:14:17,840
Sa sandaling ito ay.

359
00:14:17,840 --> 00:14:20,570
Ngunit sa pangkalahatang kaso,
ang higit pang mga tao magdagdag namin,

360
00:14:20,570 --> 00:14:23,790
probabilistically, kami ay pagpunta
upang makakuha ng higit at higit pa collisions.

361
00:14:23,790 --> 00:14:26,820
>> Ngayon ito ay isang maliit na
mas mahusay dahil technically

362
00:14:26,820 --> 00:14:34,580
ngayon ang aking chain ay maaaring maging sa
ang pinakamasamang sitwasyon kung gaano katagal?

363
00:14:34,580 --> 00:14:38,890
Kung ipasok ko n ang mga tao sa ito nang higit pa
sopistikadong istraktura ng data, n tao,

364
00:14:38,890 --> 00:14:41,080
sa pinakamalala kaso ito ay magiging n.

365
00:14:41,080 --> 00:14:41,815
Bakit?

366
00:14:41,815 --> 00:14:43,332
>> Madla: Dahil kung lahat
May parehong petsa ng kapanganakan,

367
00:14:43,332 --> 00:14:44,545
sila ay magiging isang linya.

368
00:14:44,545 --> 00:14:45,420
David MALAN: Perpekto.

369
00:14:45,420 --> 00:14:47,480
Maaaring maging isang maliit na contrived,
pero tunay na sa pinakamasamang sitwasyon,

370
00:14:47,480 --> 00:14:50,117
kung ang lahat ay may parehong petsa ng kapanganakan,
na naibigay ang mga input na mayroon ka,

371
00:14:50,117 --> 00:14:51,950
na iyong pupuntahan ay may
massively mahabang chain.

372
00:14:51,950 --> 00:14:54,241
At kaya, maaari mo itong isang tumawag
hash talahanayan, ngunit talagang ito

373
00:14:54,241 --> 00:14:56,810
isang napakalaking listahan ng naka-link lamang sa
marami ng nasayang na espasyo.

374
00:14:56,810 --> 00:15:00,460
Ngunit sa pangkalahatan, kung ipinapalagay namin na
hindi bababa sa mga kaarawan ng mga uniform--

375
00:15:00,460 --> 00:15:01,750
at ito ay malamang na hindi.

376
00:15:01,750 --> 00:15:02,587
Ako sa paggawa na up.

377
00:15:02,587 --> 00:15:04,420
Ngunit kung ipinapalagay namin, para sa
ang alang-alang ng talakayan

378
00:15:04,420 --> 00:15:07,717
na ang mga ito, pagkatapos ay sa teorya, kung
ito ay ang vertical na representasyon

379
00:15:07,717 --> 00:15:11,050
ng array, na rin pagkatapos sana ikaw ay
pagpunta upang makakuha ng chain na, alam mo na,

380
00:15:11,050 --> 00:15:15,880
halos kapareho ng haba kung saan ang bawat isa sa
ang mga kumakatawan sa isang araw ng buwan.

381
00:15:15,880 --> 00:15:19,930
>> Ngayon kung mayroong 31 araw sa buwan,
nangangahulugan iyon na aking ng panahon talaga

382
00:15:19,930 --> 00:15:25,230
ay malaking O ng n higit sa 31, na
pakiramdam ng mas mahusay kaysa sa linear.

383
00:15:25,230 --> 00:15:27,950
Ngunit ano ang isa sa aming mga
pagtatalaga ng ilang linggo

384
00:15:27,950 --> 00:15:31,145
nakalipas tuwing ito ay dumating sa pagpapahayag
ang oras ng paggana ng isang algorithm?

385
00:15:31,145 --> 00:15:33,450

386
00:15:33,450 --> 00:15:35,190
Lamang tumingin lamang sa mataas na terminong ginamit sa pagkakasunod-sunod.

387
00:15:35,190 --> 00:15:35,690
Mag-right?

388
00:15:35,690 --> 00:15:37,400
31 ay talagang kapaki-pakinabang.

389
00:15:37,400 --> 00:15:39,610
Ngunit ito ay malaking O ng n pa rin.

390
00:15:39,610 --> 00:15:41,730
Ngunit ang isa sa mga tema
ng problema itakda ang limang

391
00:15:41,730 --> 00:15:43,950
ay magiging sa
Kinikilala na ganap,

392
00:15:43,950 --> 00:15:47,320
asymptotically, theoretically
ang istraktura ng data

393
00:15:47,320 --> 00:15:50,470
Walang mas mahusay kaysa lamang
isang napakalaking naka-link na listahan.

394
00:15:50,470 --> 00:15:53,550
At sa katunayan, sa pinakamasama kaso, ito
Maaaring malipat hash talahanayan sa iyon.

395
00:15:53,550 --> 00:15:57,620
>> Ngunit sa tunay na mundo, sa amin tao
na sariling mga Mac o PC o anumang

396
00:15:57,620 --> 00:16:01,240
at tumatakbo ang tunay na mundo
software sa totoong data mundo,

397
00:16:01,240 --> 00:16:03,260
na algorithm pupunta ka ba sa ginusto?

398
00:16:03,260 --> 00:16:09,180
Ang isa na tumatagal ng mga hakbang sa dulo o ang
isa na tumatagal n hinati sa 31 mga hakbang

399
00:16:09,180 --> 00:16:12,900
upang makahanap ng ilang mga piraso ng data o
upang maghanap ng ilang mga impormasyon?

400
00:16:12,900 --> 00:16:16,580
Ibig kong sabihin, walang pasubali sa 31 Gumagawa
isang pagkakaiba sa tunay na mundo.

401
00:16:16,580 --> 00:16:18,540
Ito ay 31 beses na mas mabilis.

402
00:16:18,540 --> 00:16:20,880
At namin ang mga tao ay tiyak
pagpunta sa Pinahahalagahan na iyon.

403
00:16:20,880 --> 00:16:23,004
>> Kaya Napagtanto ang paghihiwalay sa dalawang bahagi
doon sa pagitan ng aktwal na

404
00:16:23,004 --> 00:16:25,920
pakikipag-usap tungkol sa mga bagay theoretically
at asymptotically na siguradong

405
00:16:25,920 --> 00:16:28,760
May halaga bilang nasaksihan namin,
ngunit sa tunay na mundo,

406
00:16:28,760 --> 00:16:32,930
kung mahalaga sa iyo sa paggawa ng lamang ang
masaya tao para sa pangkalahatang input,

407
00:16:32,930 --> 00:16:36,010
maaari mong lubos na rin nais na tanggapin
ang katotohanan na, oo, ito ay linear,

408
00:16:36,010 --> 00:16:38,360
ngunit ito ay 31 beses na mas mabilis
kaysa sa guhit ay maaaring maging.

409
00:16:38,360 --> 00:16:41,610
At mas mahusay pa, hindi namin lamang magkaroon upang
gawin ang isang bagay arbitrary tulad ng isang petsa ng kapanganakan,

410
00:16:41,610 --> 00:16:44,030
maaari kaming magpalipas ng kaunti
mas maraming oras at katalasan ng isip

411
00:16:44,030 --> 00:16:47,140
at sa tingin tungkol sa kung ano ang maaari naming gawin,
ibinigay na pangalan at marahil ng isang tao

412
00:16:47,140 --> 00:16:50,130
ang kanilang mga petsa ng kapanganakan upang pagsamahin ang mga
sangkap upang malaman kung ang isang bagay

413
00:16:50,130 --> 00:16:52,720
na tunay na higit pa
pare-pareho at mas may mga tulis,

414
00:16:52,720 --> 00:16:56,250
kaya upang makipag-usap sa larawang ito
Kasalukuyang nagmumungkahi maaari itong maging.

415
00:16:56,250 --> 00:16:57,750
Paano namin ipatupad ito sa code?

416
00:16:57,750 --> 00:17:00,280
Well, hayaan mo akong magpanukala na namin
humiram lamang ng ilang syntax hindi namin

417
00:17:00,280 --> 00:17:01,799
ginamit ng ilang beses kaya sa ngayon.

418
00:17:01,799 --> 00:17:03,590
At ako pupunta upang tukuyin ang
isang node, na muli

419
00:17:03,590 --> 00:17:06,812
ay isang generic na termino para lamang ng ilang
lalagyan para sa ilang mga istraktura ng data.

420
00:17:06,812 --> 00:17:09,020
Pupunta ako sa ipanukala na
isang string ay pagpunta sa doon.

421
00:17:09,020 --> 00:17:11,369
Ngunit kami ay pagpunta upang simulan ang pagkuha
mga pagsasanay gulong-off ngayon.

422
00:17:11,369 --> 00:17:13,230
>> Wala nang CS50 library
talaga ito, maliban kung gusto mo

423
00:17:13,230 --> 00:17:15,230
gamitin ito para sa iyong panghuling
proyekto, na kung saan ay multa,

424
00:17:15,230 --> 00:17:18,569
ngunit ngayon kami ay pagpunta upang hilahin pabalik ang
kurtina at sabihin ito ay lamang ng isang pansamantalang trabaho star.

425
00:17:18,569 --> 00:17:22,069
Kaya ang salitang doon ay magiging
pangalan ng tao na pinag-uusapan.

426
00:17:22,069 --> 00:17:25,079
At ngayon Mayroon akong isang link
dito sa susunod na node

427
00:17:25,079 --> 00:17:28,170
upang ang mga kumatawan
bawat isa sa mga node

428
00:17:28,170 --> 00:17:30,950
sa chain, potensyal,
ng isang naka-link na listahan.

429
00:17:30,950 --> 00:17:34,090
>> At ngayon kung paano gawin Ipinahahayag ko
mismo ang hash talahanayan?

430
00:17:34,090 --> 00:17:36,660
Paano ko idedeklara ito buong kaayusan?

431
00:17:36,660 --> 00:17:40,960
Well, talaga, tulad ng ginamit ko ng isang pointer
lang sa unang elemento ng isang listahan

432
00:17:40,960 --> 00:17:44,510
bago, katulad maaari ko lang sabihin
Kailangan ko lamang ng isang bungkos ng mga payo

433
00:17:44,510 --> 00:17:46,270
upang ipatupad ang buong hash talahanayan.

434
00:17:46,270 --> 00:17:49,484
Pupunta ako sa may isang array
tinatawag na table para sa hash talahanayan.

435
00:17:49,484 --> 00:17:50,900
Ito ay magiging ng kapasidad laki.

436
00:17:50,900 --> 00:17:52,525
Iyon ay kung gaano karaming mga elemento mapagkasya sa loob nito.

437
00:17:52,525 --> 00:17:56,180
At bawat isa sa mga elemento sa
array ay magiging isang node bituin.

438
00:17:56,180 --> 00:17:56,810
Bakit?

439
00:17:56,810 --> 00:18:00,160
Well, sa bawat ang larawang ito, kung ano ang ako
pagpapatupad ng hash talahanayan bilang

440
00:18:00,160 --> 00:18:04,330
epektibo sa simula lamang
ang array na na-iginuhit namin nang patayo,

441
00:18:04,330 --> 00:18:06,820
ang bawat isa sa kung saan ang mga parisukat
ay kumakatawan sa isang pointer.

442
00:18:06,820 --> 00:18:09,170
Na mga na may slashes
sa pamamagitan ng mga ito ay lamang null.

443
00:18:09,170 --> 00:18:11,410
At ang mga na mayroon
mga arrow ng pagpunta sa kanan

444
00:18:11,410 --> 00:18:16,140
ay mga aktwal na pointer sa aktwal na node,
samakatuwid sa simula ng isang naka-link na listahan.

445
00:18:16,140 --> 00:18:19,050
>> Kaya dito, pagkatapos, ay kung paano namin maaari
ipatupad ng hash talahanayan na

446
00:18:19,050 --> 00:18:21,580
ipinapatupad ng nakahiwalay na chaining.

447
00:18:21,580 --> 00:18:22,840
Ngayon ay maaari naming gawin mas mahusay?

448
00:18:22,840 --> 00:18:25,632
Ang lahat ng mga karapatan ipinangako ko huling beses na
maaari kaming makamit ang pare-pareho ang oras.

449
00:18:25,632 --> 00:18:27,381
At uri ng ko ibinigay sa iyo
pare-pareho ang oras dito,

450
00:18:27,381 --> 00:18:29,850
ngunit pagkatapos ay sinabi hindi talaga
pare-pareho ang oras dahil ito ay pa rin

451
00:18:29,850 --> 00:18:31,890
nakadepende sa kabuuang
numero ng mga elemento

452
00:18:31,890 --> 00:18:34,500
ka inputting sa
ang istraktura ng data.

453
00:18:34,500 --> 00:18:35,980
Ngunit ipagpalagay na ginawa namin ito.

454
00:18:35,980 --> 00:18:39,550
Hayaan akong bumalik sa screen sa paglipas dito.

455
00:18:39,550 --> 00:18:44,520
Hayaan akong i-project din up dito, malinaw na
screen, at ipagpalagay na ginawa ko ito.

456
00:18:44,520 --> 00:18:49,300
Ipagpalagay na nais kong ipasok ang pangalan
Daven sa sa aking istraktura ng data.

457
00:18:49,300 --> 00:18:52,100
>> Kaya gusto kong ipasok ang isang string
Daven sa istraktura ng data.

458
00:18:52,100 --> 00:18:54,370
Paano kung hindi ko ginagamit ang
hash talahanayan, ngunit gagamitin ko

459
00:18:54,370 --> 00:18:56,980
isang bagay na mas tree-tulad ng
tulad ng isang pamilya tree, kung saan

460
00:18:56,980 --> 00:18:59,670
mayroon kang ilang mga ugat sa
itaas at pagkatapos ay i-node at mga dahon

461
00:18:59,670 --> 00:19:01,440
na pumunta pababa at palabas.

462
00:19:01,440 --> 00:19:04,450
Ipagpalagay na pagkatapos, na aking
Gusto upang ipasok Daven ni

463
00:19:04,450 --> 00:19:06,430
sa kung ano ang kasalukuyang isang walang lamang listahan.

464
00:19:06,430 --> 00:19:09,780
Pupunta ako sa gawin ang mga sumusunod: ako
pagpunta upang lumikha ng isang node sa pamilya na ito

465
00:19:09,780 --> 00:19:15,170
tree-tulad ng istraktura ng data na ganito ang
isang maliit na tulad nito, ang bawat isa

466
00:19:15,170 --> 00:19:19,640
mga parihaba ay, sabihin nating,
sa ngayon 26 mga elemento sa loob nito.

467
00:19:19,640 --> 00:19:21,650
At bawat isa sa mga cell
sa array ay pagpunta

468
00:19:21,650 --> 00:19:23,470
upang kumatawan sa sulat ng isang alpabeto.

469
00:19:23,470 --> 00:19:28,190
>> Sa partikular, pupunta ako sa paggamot sa
ito ay A, pagkatapos ay B, pagkatapos ay C, pagkatapos D,

470
00:19:28,190 --> 00:19:29,310
ang isang ito dito.

471
00:19:29,310 --> 00:19:32,940
Kaya ito ay pagpunta upang epektibong
kumakatawan sa mga titik D.

472
00:19:32,940 --> 00:19:36,040
Ngunit upang ipasok ang lahat ng Daven ni
pangalanan ang kailangan kong gawin nang kaunti pa.

473
00:19:36,040 --> 00:19:37,840
Kaya ako unang pagpunta sa hash, kaya upang makipag-usap.

474
00:19:37,840 --> 00:19:41,049
Pupunta ako sa tumingin sa ang unang titik
sa Daven kung saan ay malinaw naman isang D,

475
00:19:41,049 --> 00:19:42,840
at ako pagpunta sa maglaan
isang node na mukhang

476
00:19:42,840 --> 00:19:45,570
tulad ng this-- isang malaking parihaba malaki
sapat na upang magkasya ang buong alpabeto.

477
00:19:45,570 --> 00:19:47,140
>> Ngayon D ay tapos na.

478
00:19:47,140 --> 00:19:49,720
Ngayon A. D-A-V-E-N ay ang layunin.

479
00:19:49,720 --> 00:19:51,220
Kaya ngayon kung ano ang ako pagpunta sa gawin ay ito.

480
00:19:51,220 --> 00:19:54,027
Sa sandaling sinimulan ko notice D
walang pointer doon.

481
00:19:54,027 --> 00:19:56,860
Ito ay mga halaga ng basura sa sandaling ito,
o maaaring initialize ko ito sa null.

482
00:19:56,860 --> 00:19:59,630
Ngunit hayaan mo akong panatilihing pagpunta sa
ang ideya ng pagbuo ng isang puno.

483
00:19:59,630 --> 00:20:04,260
Hayaan akong maglaan ng isa pang isa sa mga
node na may 26 mga elemento sa loob nito.

484
00:20:04,260 --> 00:20:05,150
>> At alam mo kung ano?

485
00:20:05,150 --> 00:20:09,130
Kung ito ay isang node lamang sa memorya na
Nilikha ko ang malloc, gamit ang isang struct

486
00:20:09,130 --> 00:20:11,240
bilang makikita sa lalong madaling panahon namin makita,
Pupunta ako sa gawin this--

487
00:20:11,240 --> 00:20:14,450
Pupunta ako upang gumuhit ng isang arrow mula sa
ang bagay na kinakatawan D pababa

488
00:20:14,450 --> 00:20:15,860
sa bagong node.

489
00:20:15,860 --> 00:20:19,240
At ngayon, sa unang susunod na
sulat sa pangalan ni Daven,

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V-- Pupunta ako sa sige
at gumuhit ng isa pang node na tulad nito,

491
00:20:24,150 --> 00:20:30,150
kung saan, ang mga elemento ng V dito, na
kami ay gumuhit para sa instance-- Oops.

492
00:20:30,150 --> 00:20:31,020
Hindi namin gumuhit doon.

493
00:20:31,020 --> 00:20:31,936
Ito ay pagpunta sa pumunta dito.

494
00:20:31,936 --> 00:20:32,890

495
00:20:32,890 --> 00:20:35,712
>> Pagkatapos kami ay pagpunta sa
isaalang-alang na ito upang maging V.

496
00:20:35,712 --> 00:20:44,920
At pagkatapos ay down na dito kami ng pagpunta sa index
down na mula sa V sa kung ano ang makikita namin isaalang-alang ang E.

497
00:20:44,920 --> 00:20:50,100
At pagkatapos ay mula dito kami ng pagpunta sa
pumunta magkaroon ng isa sa mga node dito.

498
00:20:50,100 --> 00:20:52,930
At ngayon kami ay may isang tanong upang sagutin.

499
00:20:52,930 --> 00:20:57,840
Kailangan ko bang kahit papaano ay nagpapahiwatig na
Ikinalulungkot namin sa dulo ng string Daven.

500
00:20:57,840 --> 00:20:59,490
Kaya maaari ko bang iwan lang ito null.

501
00:20:59,490 --> 00:21:02,670
>> Ngunit kung ano kung mayroon Daven ng namin
buong pangalan din, na

502
00:21:02,670 --> 00:21:04,280
ay, pati na sinabi namin, Davenport?

503
00:21:04,280 --> 00:21:06,970
Kaya kung ano kung Daven ay
tunay na isang substring,

504
00:21:06,970 --> 00:21:08,960
isang prefix ng isang mas matagal string?

505
00:21:08,960 --> 00:21:11,450
Hindi namin magagawa permanenteng lamang
sabihin walang pagpunta

506
00:21:11,450 --> 00:21:14,410
pumunta doon, dahil maaari naming
Hindi kailanman magpasok ng isang salita tulad ng Davenport

507
00:21:14,410 --> 00:21:15,840
sa ito Istraktura ng data

508
00:21:15,840 --> 00:21:19,560
>> Kaya ano ang maaari naming gawin sa halip ay
ituturing ng bawat isa sa mga elemento

509
00:21:19,560 --> 00:21:22,170
bilang marahil pagkakaroon ng dalawang
mga elemento sa loob ng mga ito.

510
00:21:22,170 --> 00:21:24,810
Isa ay isang pointer, sa katunayan,
bilang ko ang paggawa.

511
00:21:24,810 --> 00:21:27,100
Kaya bawat isa sa mga kahon
Hindi isang cell lamang.

512
00:21:27,100 --> 00:21:29,855
Ngunit paano kung ang tuktok
one-- ang isa sa ibaba

513
00:21:29,855 --> 00:21:32,230
pagpunta sa null, dahil
walang Davenport pa lamang.

514
00:21:32,230 --> 00:21:34,197
Paano kung ang isa tuktok
ay ilang mga espesyal na halaga?

515
00:21:34,197 --> 00:21:36,530
At ito ay magiging isang maliit na
mahirap upang gumuhit ng mga ito sa ganitong laki.

516
00:21:36,530 --> 00:21:38,130
Ngunit ipagpalagay na ito ay lamang ng isang marka ng tsek.

517
00:21:38,130 --> 00:21:38,920
Lagyan ng check.

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-N ay isang string
sa istraktura ng data.

519
00:21:44,230 --> 00:21:48,350
>> Samantala, kung nagkaroon ako ng mas maraming espasyo
dito, maaari kong gawin P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
at maaari ko bang ilagay ang check sa node
na may sulat T sa dulo.

521
00:21:52,650 --> 00:21:55,460
Kaya ito ay isang massively
complex-naghahanap istraktura ng data.

522
00:21:55,460 --> 00:21:57,210
At ang aking sulat-kamay
tiyak na hindi ito makatulong.

523
00:21:57,210 --> 00:22:00,043
Ngunit kung nais kong ipasok ang isang bagay
iba, isaalang-alang kung ano ang gusto naming gawin.

524
00:22:00,043 --> 00:22:03,370
Kung gusto naming ilagay David sa,
nais naming sundin ang parehong logic, D-A-V,

525
00:22:03,370 --> 00:22:08,802
ngunit ngayon Gusto ko ituro sa susunod na
elemento hindi mula sa E, ngunit mula ako sa D.

526
00:22:08,802 --> 00:22:10,760
Kaya may pupuntahan maging
higit pang mga node sa puno na ito.

527
00:22:10,760 --> 00:22:12,325
Kami ay pagpunta sa magkaroon ng higit tawag malloc.

528
00:22:12,325 --> 00:22:14,700
Ngunit hindi ko nais upang gumawa ng
Kumpleto na ang gulo ng ang larawang ito.

529
00:22:14,700 --> 00:22:17,710
Kaya sa halip na tumingin sa isa hayaan
na na-pre-formulated

530
00:22:17,710 --> 00:22:21,810
tulad nito sa hindi tuldok, tuldok,
mga tuldok, ngunit dinaglat lamang array.

531
00:22:21,810 --> 00:22:23,950
Subalit ang bawat isa sa mga node
sa puno hanggang dito

532
00:22:23,950 --> 00:22:26,700
kumakatawan sa parehong thing--
isang array Ray ng laki 26.

533
00:22:26,700 --> 00:22:28,860
>> O kung gusto namin na maging
talagang maayos na ngayon, kung ano

534
00:22:28,860 --> 00:22:30,790
kung pangalan ng isang tao bilang
isang kudlit, sabihin

535
00:22:30,790 --> 00:22:35,560
ipagpalagay na ang bawat node ay talagang
tulad ng 27-i-index sa loob nito, hindi lang 26.

536
00:22:35,560 --> 00:22:42,020
Kaya ito ngayon ay magiging isang data
istraktura na tinatawag na trie-- T-R-I-E.

537
00:22:42,020 --> 00:22:46,120
Ang isang trie, na parang
kasaysayan ng isang matalino pangalan para sa isang puno

538
00:22:46,120 --> 00:22:49,040
na-optimize para sa
pagbawi, na syempre,

539
00:22:49,040 --> 00:22:50,870
ay na-spell na may I-E kaya trie.

540
00:22:50,870 --> 00:22:52,710
Ngunit iyon ay ang kasaysayan ng trie.

541
00:22:52,710 --> 00:22:55,860
>> Kaya isang trie ay ang data na ito tulad ng tree-
istraktura tulad ng isang pamilya puno

542
00:22:55,860 --> 00:22:57,510
na ganap na behaves tulad na.

543
00:22:57,510 --> 00:23:00,890
At dito ay isa lamang halimbawa ng isang
ang maramihang mga pangalan ng ibang tao.

544
00:23:00,890 --> 00:23:03,540
Subalit ang tanong ngayon
sa kamay ay kung ano ang

545
00:23:03,540 --> 00:23:08,070
Nakakuha kami ng nagpapakilala arguably ng isang mas
kumplikadong istraktura ng data, at isa,

546
00:23:08,070 --> 00:23:09,870
nang tapat, na ginagamit ng maraming memory.

547
00:23:09,870 --> 00:23:11,703
>> Dahil kahit na,
sa sandaling ito, lamang ako

548
00:23:11,703 --> 00:23:15,050
gamit D's pointer at
A at V at Es at NS,

549
00:23:15,050 --> 00:23:16,700
Ako aksaya ng isang ano ba ng maraming memory.

550
00:23:16,700 --> 00:23:18,030

551
00:23:18,030 --> 00:23:22,660
Ngunit kung saan gagastusin ko ang isa na mapagkukunan,
Malamang kong huwag makakuha muli ng isa pa.

552
00:23:22,660 --> 00:23:26,020
Kaya kung ako gumagastos ng karagdagang espasyo,
kung ano ang malamang na ang pag-asa?

553
00:23:26,020 --> 00:23:27,407
Na ako gumagasta ng mas mababa sa kung ano?

554
00:23:27,407 --> 00:23:28,240
Madla: Mas mababa oras.

555
00:23:28,240 --> 00:23:28,990
David MALAN: Time.

556
00:23:28,990 --> 00:23:30,320
Ngayon kung bakit maaaring maging iyon?

557
00:23:30,320 --> 00:23:33,880
Well, ano ang pagpapasok
oras, sa mga tuntunin ng malaking O ngayon,

558
00:23:33,880 --> 00:23:37,660
ng isang pangalan tulad ng Daven
o Davenport o David?

559
00:23:37,660 --> 00:23:39,340
Well, Daven ay limang mga hakbang.

560
00:23:39,340 --> 00:23:42,350
Maringal na aparador ay magiging siyam na mga hakbang,
kaya magiging ilan pang mga hakbang.

561
00:23:42,350 --> 00:23:44,250
David ay magiging pati na rin ang limang hakbang na ito.

562
00:23:44,250 --> 00:23:47,230
Kaya mga mga kongkreto
numero, ngunit tiyak na mayroong

563
00:23:47,230 --> 00:23:49,550
isang upper bound sa
haba ng pangalan ng isang tao.

564
00:23:49,550 --> 00:23:52,240
At sa katunayan, sa problema
hanay ng limang pagtutukoy,

565
00:23:52,240 --> 00:23:54,050
kami ay pagpunta sa ipanukala
na ito ay isang bagay na

566
00:23:54,050 --> 00:23:55,470
na 40 ilang-kakaiba character.

567
00:23:55,470 --> 00:23:58,180
>> Realistically, walang isa ay
isang walang hanggan mahaba ang pangalan,

568
00:23:58,180 --> 00:24:01,542
na kung saan ay upang sabihin na ang haba ng isang
pangalan o ang haba ng isang string maaari naming

569
00:24:01,542 --> 00:24:03,750
May ilang mga estado ng
istraktura ay arguably kung ano?

570
00:24:03,750 --> 00:24:05,550

571
00:24:05,550 --> 00:24:06,250
Ito ay pare-pareho.

572
00:24:06,250 --> 00:24:06,430
Mag-right?

573
00:24:06,430 --> 00:24:09,310
Maaaring maging isang malaking pare-pareho tulad ng
40-isang bagay, ngunit ito ay pare-pareho.

574
00:24:09,310 --> 00:24:13,752
At ito ay walang dependency sa kung gaano karaming
iba pang mga pangalan ay nasa ito istraktura ng data.

575
00:24:13,752 --> 00:24:15,460
Sa ibang salita, kung ako
Nais na ngayon magpasok

576
00:24:15,460 --> 00:24:20,540
Colton o Gabriel o Rob o Zamyla o
Alison o Belinda o anumang iba pang mga pangalan

577
00:24:20,540 --> 00:24:23,940
mula sa mga tauhan sa ang data na ito
istraktura, ang oras tumatakbo

578
00:24:23,940 --> 00:24:26,750
ng pagpasok ng iba pang mga pangalan
magiging sa lahat ng naapektuhan

579
00:24:26,750 --> 00:24:30,220
sa pamamagitan ng kung gaano karaming iba pang mga elemento ay
sa istraktura ng data na?

580
00:24:30,220 --> 00:24:31,040
Hindi ito.

581
00:24:31,040 --> 00:24:31,540
Mag-right?

582
00:24:31,540 --> 00:24:36,150
Dahil epektibo aming ginagamit
ito multi-layer hash talahanayan.

583
00:24:36,150 --> 00:24:38,280
At ang oras ng paggana ng
anuman sa mga pagpapatakbong ito

584
00:24:38,280 --> 00:24:41,510
Nakadepende hindi sa bilang ng mga
mga elemento na sa istraktura ng data

585
00:24:41,510 --> 00:24:43,090
o na huli ng pagpunta
upang maging sa istraktura ng data,

586
00:24:43,090 --> 00:24:44,714
ngunit sa haba ng kung ano ang partikular na?

587
00:24:44,714 --> 00:24:46,500

588
00:24:46,500 --> 00:24:49,200
>> Ang string pagiging
Ipinasok, na ang gumawa

589
00:24:49,200 --> 00:24:52,580
ito asymptotically pare-pareho
time-- malaking O na isa.

590
00:24:52,580 --> 00:24:54,720
At lantaran, lamang sa
sa tunay na mundo, ito

591
00:24:54,720 --> 00:24:58,380
Nangangahulugan pagpasok ng pangalan Daven ni tumatagal
tulad ng limang mga hakbang, o Davenport siyam

592
00:24:58,380 --> 00:25:00,100
mga hakbang, o David limang hakbang.

593
00:25:00,100 --> 00:25:03,071
Iyon ay medyo nagsulsi maliit na mga panahon ng pagtakbo.

594
00:25:03,071 --> 00:25:05,320
At, sa katunayan, iyon ay isang napaka
mabuting bagay, lalo na kapag

595
00:25:05,320 --> 00:25:08,126
hindi ito nakasalalay sa kabuuang
numero ng mga elemento doon.

596
00:25:08,126 --> 00:25:10,500
Kaya kung paano na maaari naming ipatupad ang
uri ng istruktura sa code?

597
00:25:10,500 --> 00:25:12,900
Ito ay isang kaunti pa
complex, ngunit pa rin ito

598
00:25:12,900 --> 00:25:15,050
ang isang application lamang ng
pangunahing gusali bloke.

599
00:25:15,050 --> 00:25:17,830
Pupunta ako sa muling tukuyin
amin node bilang mga sumusunod:

600
00:25:17,830 --> 00:25:21,100
bool tinatawag word-- at ito
ma-tinatawag na kahit ano.

601
00:25:21,100 --> 00:25:23,970
Ngunit ang bool ay kumakatawan
kung ano ang aking iginuhit bilang isang marka ng tsek.

602
00:25:23,970 --> 00:25:24,490
Oo.

603
00:25:24,490 --> 00:25:26,720
Ito ang katapusan ng isang string
sa istraktura ng data.

604
00:25:26,720 --> 00:25:30,702
>> At, siyempre, ang node bituin
doon ay nagre-refer sa mga bata.

605
00:25:30,702 --> 00:25:32,410
At, sa katunayan, i lamang
isang pamilya tree, mo

606
00:25:32,410 --> 00:25:34,370
Gusto isaalang-alang ang mga node
na nakikipag-hang-off

607
00:25:34,370 --> 00:25:36,920
ng ibaba ng ilang mga magulang
elemento na maging bata.

608
00:25:36,920 --> 00:25:40,510
At upang ang mga bata ay pagpunta sa
isang array ng 27, ang isang 27

609
00:25:40,510 --> 00:25:41,680
lamang pagiging para sa kudlit.

610
00:25:41,680 --> 00:25:43,390
Kami ay pagpunta sa uri-uriin
ng mga espesyal na kaso na iyon.

611
00:25:43,390 --> 00:25:45,400
Kaya maaaring magkaroon ka ng ilang
mga pangalan na may kudlit.

612
00:25:45,400 --> 00:25:47,399
Siguro kahit gitling dapat
pumunta doon, ngunit ikaw ay

613
00:25:47,399 --> 00:25:50,330
makita sa hanay p 5 lamang sa pangangalaga namin
tungkol sa mga titik at kudlit.

614
00:25:50,330 --> 00:25:52,990
>> At pagkatapos ay kung paano gawin kinakatawan
ang mismong istraktura ng data?

615
00:25:52,990 --> 00:25:56,454
Paano mo kumatawan sa root
ng trie, kaya upang makipag-usap?

616
00:25:56,454 --> 00:25:59,620
Well, gusto lamang na may naka-link na listahan, mo
Kailangan ng pointer sa unang elemento.

617
00:25:59,620 --> 00:26:04,270
Sa isang trie kailangan mo lang ng isang
pointer sa root ng ito trie.

618
00:26:04,270 --> 00:26:07,290
At mula doon maaari mong hash
ang iyong paraan down na mas malalim at mas malalim

619
00:26:07,290 --> 00:26:10,460
sa bawat iba pang mga node sa istraktura.

620
00:26:10,460 --> 00:26:13,440
Kaya lang sa lata
kumakatawan namin na struct.

621
00:26:13,440 --> 00:26:15,877
>> Ngayon Meanwhile-- Oh, pinag-uusapan.

622
00:26:15,877 --> 00:26:17,220
>> Madla: Ano ang bool salita?

623
00:26:17,220 --> 00:26:20,490
>> David MALAN: Bool salita ay
lamang ito C pagkakatawang-tao

624
00:26:20,490 --> 00:26:22,920
ng kung ano ang ko na inilarawan sa
sa kahon na ito dito, kapag

625
00:26:22,920 --> 00:26:26,000
Nagsimula ako paghiwalayin ang bawat isa sa
mga elemento ng array na sa dalawang piraso.

626
00:26:26,000 --> 00:26:27,600
Isa ay isang pointer sa susunod na node.

627
00:26:27,600 --> 00:26:30,280
Ang iba pang ay dapat na
isang bagay tulad ng isang check box

628
00:26:30,280 --> 00:26:33,770
sabihin ninyo ang oo, may
salita Daven na nagtatapos dito,

629
00:26:33,770 --> 00:26:35,610
dahil hindi namin nais,
sa sandaling ito, Dave.

630
00:26:35,610 --> 00:26:39,320
>> Kahit na Dave ay magiging isang
lehitimong salita, siya ay wala sa trie

631
00:26:39,320 --> 00:26:39,830
pa.

632
00:26:39,830 --> 00:26:40,950
At D ay hindi isang salita.

633
00:26:40,950 --> 00:26:42,770
At D-A ay hindi isang salita o ng isang pangalan.

634
00:26:42,770 --> 00:26:45,020
Kaya check mark
Ipinapahiwatig lamang ng isang beses sa iyo

635
00:26:45,020 --> 00:26:48,190
maabot ang na node ay ang
mga nakaraang path ng character

636
00:26:48,190 --> 00:26:50,700
tunay na isang string na iyong ipinasok.

637
00:26:50,700 --> 00:26:53,660
Kaya na ang lahat ng mga bool
doon ay ginagawa para sa atin.

638
00:26:53,660 --> 00:26:55,500
>> Anumang iba pang mga katanungan sa pagsubok?

639
00:26:55,500 --> 00:26:56,215
Oo.

640
00:26:56,215 --> 00:26:58,035
>> Madla: Ano ang overlap?

641
00:26:58,035 --> 00:26:59,945
Paano kung mayroon kang Dave at Daven?

642
00:26:59,945 --> 00:27:00,820
David MALAN: Perpekto.

643
00:27:00,820 --> 00:27:02,580
Paano kung mayroon kang Dave at Daven?

644
00:27:02,580 --> 00:27:06,240
Kaya kung ipasok namin, sinasabi ng isang palayaw,
para sa David-- Dave-- D-A-V-E?

645
00:27:06,240 --> 00:27:07,370

646
00:27:07,370 --> 00:27:08,700
Ito ay talagang napaka-simple.

647
00:27:08,700 --> 00:27:10,325
Kaya namin lamang ng pagpunta sa tumagal ng apat na hakbang.

648
00:27:10,325 --> 00:27:11,042

649
00:27:11,042 --> 00:27:15,847
D-A-V-E. At kung ano ang kailangan kong
gagawin sa sandaling pindutin ko na pang-apat na node?

650
00:27:15,847 --> 00:27:16,680
Pagpunta lamang upang suriin.

651
00:27:16,680 --> 00:27:18,000
Kami ay naka-handa na upang.

652
00:27:18,000 --> 00:27:18,840
Tapos na.

653
00:27:18,840 --> 00:27:19,750
Apat na hakbang.

654
00:27:19,750 --> 00:27:21,590
Ang patuloy na oras asymptotically.

655
00:27:21,590 --> 00:27:26,300
At ngayon Isinaad namin na ang parehong Dave
at Daven ay mga string sa istraktura.

656
00:27:26,300 --> 00:27:27,710
Kaya hindi problema.

657
00:27:27,710 --> 00:27:30,200
At pansinin kung paano ang presensya
ng Daven ay hindi nakaabot

658
00:27:30,200 --> 00:27:34,750
gumawa ng anumang higit pang mga oras o mas mababa
oras para sa Dave at vice versa.

659
00:27:34,750 --> 00:27:36,000
>> Kaya ano pa ang maaari naming gawin ngayon?

660
00:27:36,000 --> 00:27:40,680
Ginagamit namin ang talinghaga bago
ng trays na kumakatawan sa isang bagay.

661
00:27:40,680 --> 00:27:43,380
Ngunit ito ay lumiliko out na ang isang
stack ng mga trays ay talagang

662
00:27:43,380 --> 00:27:47,187
nagpapakilala ng isa pang abstract data
type-- isang mas mataas na istraktura ng data sa antas ng

663
00:27:47,187 --> 00:27:49,770
na sa pagtatapos ng araw lamang
tulad ng isang array o naka-link na listahan

664
00:27:49,770 --> 00:27:50,970
o isang bagay na mas pangmundo.

665
00:27:50,970 --> 00:27:53,270
Ngunit ito ay isang mas kawili-wiling
haka-haka konsepto.

666
00:27:53,270 --> 00:27:56,440
Ang isang stack, tulad ng mga ito
trays dito sa Mather,

667
00:27:56,440 --> 00:27:58,750
ay karaniwang tinatawag na
that-- lamang ng stack.

668
00:27:58,750 --> 00:28:02,540
>> At sa ganitong uri ng istraktura ng data
mayroon kang dalawang operations--

669
00:28:02,540 --> 00:28:05,880
mayroon kang isa na tinatawag na push para sa
pagdaragdag ng isang bagay sa stack,

670
00:28:05,880 --> 00:28:08,320
tulad ng paglalagay ng isa pang tray
-back sa tuktok ng stack.

671
00:28:08,320 --> 00:28:11,350
At pagkatapos ay i-pop, na nangangahulugang
gawin ang mga kataas-taasan-off ang tray.

672
00:28:11,350 --> 00:28:16,210
Ngunit kung ano ang key tungkol sa isang stack ay na
ito ay nakuha ko ito kataka-taka katangian.

673
00:28:16,210 --> 00:28:19,560
Bilang dining hall staff
rearranging ang trays para sa susunod na pagkain,

674
00:28:19,560 --> 00:28:21,380
kung ano ang magiging
totoo tungkol sa kung paano mag-aaral

675
00:28:21,380 --> 00:28:22,856
makipag-ugnayan sa ang istraktura ng data?

676
00:28:22,856 --> 00:28:24,480
Madla: Ang mga ito ay pagpunta sa pop-off ang isa.

677
00:28:24,480 --> 00:28:26,550
David MALAN: Ang mga ito ay pagpunta sa
-pop isa-off, sana sa itaas.

678
00:28:26,550 --> 00:28:28,910
Kung hindi man ito lamang uri ng nakababagod
upang pumunta sa lahat ng mga paraan sa ibaba.

679
00:28:28,910 --> 00:28:29,070
Mag-right?

680
00:28:29,070 --> 00:28:31,620
Ang istraktura ng data ay hindi talaga payagan
mong i-grab sa ibaba tray ng hindi bababa sa

681
00:28:31,620 --> 00:28:32,520
madali.

682
00:28:32,520 --> 00:28:35,040
Kaya ito hindi karaniwan
ari-arian sa isang stack

683
00:28:35,040 --> 00:28:39,730
na ang huling item sa ay
pagpunta sa maging unang isa out.

684
00:28:39,730 --> 00:28:43,400
At mga siyentipiko computer na tumawag
ito LIFO-- magtatagal in, unang out.

685
00:28:43,400 --> 00:28:45,540
At talagang mayroon
kawili-wiling mga application.

686
00:28:45,540 --> 00:28:50,090
Ito ay hindi kinakailangan ng kapansin-pansing bilang ilang mga
iba, ngunit ito ay maaaring, sa katunayan, maging kapaki-pakinabang,

687
00:28:50,090 --> 00:28:54,040
at ito ay maaaring, sa katunayan, ay ipinatupad
sa loob ng ilang iba't ibang mga paraan.

688
00:28:54,040 --> 00:28:58,550
>> Kaya isa, at aktwal na, sabihin
sa akin ay hindi na sumisid sa iyon.

689
00:28:58,550 --> 00:28:59,860
Ni gawin ito sa halip Hayaan.

690
00:28:59,860 --> 00:29:03,700
Tingnan natin ang isang bagay na halos Hayaan
parehong ideya, ngunit ito ay isang maliit na fairer.

691
00:29:03,700 --> 00:29:04,200
Mag-right?

692
00:29:04,200 --> 00:29:07,560
Kung ikaw ay isa sa mga fan lalaki o
mga batang babae na talaga ang may gusto mga produkto ng Apple

693
00:29:07,560 --> 00:29:10,130
at woke up sa 03:00
sa line up sa ilang mga tindahan

694
00:29:10,130 --> 00:29:14,150
upang makuha ang pinakabagong iPhone, mo
maaaring naka-queue up na katulad nito.

695
00:29:14,150 --> 00:29:15,800
>> Ngayon isang queue ay napaka sadyang may pangalang.

696
00:29:15,800 --> 00:29:18,190
Ito ay isang linya dahil mayroong
ilang pagkamakatarungan dito.

697
00:29:18,190 --> 00:29:18,690
Mag-right?

698
00:29:18,690 --> 00:29:21,690
Ito ay uri ng sinipsip kung ikaw ay
nakapunta roon muna sa Apple Store

699
00:29:21,690 --> 00:29:25,700
ngunit ikaw ay epektibo ang pinakamababa
tray dahil ang mga empleyado ng Apple pagkatapos ay

700
00:29:25,700 --> 00:29:28,189
-pop ang huling taong nag
aktwal na nakuha ko sa linya.

701
00:29:28,189 --> 00:29:31,230
Kaya stack at queues, kahit na
sa pagtakbo ang mga ito ay uri ng same--

702
00:29:31,230 --> 00:29:33,105
ito lamang ang koleksyon na ito
ng mga mapagkukunan na

703
00:29:33,105 --> 00:29:36,210
pagpunta sa lumalaki at shrink-- doon ay
ang pagiging makatarungan aspeto dito,

704
00:29:36,210 --> 00:29:39,634
hindi bababa sa tunay na mundo,
kung saan ang mga pagpapatakbo ng ehersisyo sa iyo

705
00:29:39,634 --> 00:29:40,800
ay sa panimula naiiba.

706
00:29:40,800 --> 00:29:43,360
Isang stack-- isang queue
rather-- ay sinabi na magkaroon ng

707
00:29:43,360 --> 00:29:45,320
dalawang pagpapatakbo: n queue at d queue.

708
00:29:45,320 --> 00:29:46,341

709
00:29:46,341 --> 00:29:48,090
O kaya, maaari kang tumawag sa kanila
anumang bilang ng mga bagay.

710
00:29:48,090 --> 00:29:50,770
Ngunit nais mo lamang upang makuha ang
ang paniwala na ang isa ay pagdaragdag

711
00:29:50,770 --> 00:29:53,230
at ang isa ay sa huli ng pagbabawas.

712
00:29:53,230 --> 00:29:58,840
>> Ngayon sa ilalim ng hood, ang parehong ng stack
at isang queue ma-ipinatupad paano?

713
00:29:58,840 --> 00:30:01,390
Hindi namin pumunta sa code ng
ito dahil ang mas mataas na antas

714
00:30:01,390 --> 00:30:03,387
ideya ay isang uri ng higit pang mga halatang.

715
00:30:03,387 --> 00:30:04,470
Ibig kong sabihin, ano ang mga tao gawin?

716
00:30:04,470 --> 00:30:07,030
Kung ako ang unang tao sa Apple
Mag-imbak at ito ay ang pinto,

717
00:30:07,030 --> 00:30:08,130
alam mo na, pupuntahan ko tumayo dito.

718
00:30:08,130 --> 00:30:09,750
At sa susunod na tao
pagpunta sa tumayo dito.

719
00:30:09,750 --> 00:30:11,500
At sa susunod na tao
pagpunta sa tumayo dito.

720
00:30:11,500 --> 00:30:13,792
Kaya kung ano ang istraktura ng data
lends mismo sa isang queue?

721
00:30:13,792 --> 00:30:14,542
>> Madla: Ang isang queue.

722
00:30:14,542 --> 00:30:15,667
David MALAN: Well, isang queue.

723
00:30:15,667 --> 00:30:16,390
Oo naman.

724
00:30:16,390 --> 00:30:16,920
Ano pa?

725
00:30:16,920 --> 00:30:17,600
>> Madla: Ang isang naka-link na listahan.

726
00:30:17,600 --> 00:30:18,990
>> David MALAN: Isang naka-link
ilista ang maaari mong ipatupad.

727
00:30:18,990 --> 00:30:22,500
At isang naka-link na listahan ay maganda dahil pagkatapos
maaari itong lumalago nagkataon mahaba bilang kabaligtaran

728
00:30:22,500 --> 00:30:24,880
sa pagkakaroon ng ilang mga nakapirming numero
ng mga tao sa store.

729
00:30:24,880 --> 00:30:27,030
Pero siguro isang nakapirming numero
ng mga lugar ay lehitimo.

730
00:30:27,030 --> 00:30:30,350
Dahil kung ang mga ito ay may lamang tulad ng 20
iPhone sa unang araw, siguro

731
00:30:30,350 --> 00:30:33,930
Kailangan lang nila ng isang hanay ng mga laki
20 upang kumatawan na queue, na

732
00:30:33,930 --> 00:30:37,070
ay lamang na sabihin ngayon sa sandaling sinimulan namin ang pakikipag-usap
tungkol sa mga mas mataas na mga problema sa antas ng,

733
00:30:37,070 --> 00:30:38,890
maaari mo itong ipatupad
sa anumang bilang ng mga paraan.

734
00:30:38,890 --> 00:30:42,030
At doon ay marahil lamang ng pagpunta sa
maging off ang isang kalakalan sa espasyo at oras

735
00:30:42,030 --> 00:30:43,950
o lamang sa iyong sariling pagiging kumplikado code.

736
00:30:43,950 --> 00:30:45,380
>> Ano ang tungkol sa isang stack?

737
00:30:45,380 --> 00:30:48,190
Well, isang stack, nasaksihan namin masyadong
ay maaaring lamang ang mga trays.

738
00:30:48,190 --> 00:30:50,007
At maaari mong ipatupad ang isang array.

739
00:30:50,007 --> 00:30:53,090
Ngunit sa ilang mga punto kung gumagamit ka ng isang array,
kung ano ang nangyayari sa mangyayari sa trays

740
00:30:53,090 --> 00:30:54,173
na sinusubukan mong ilagay down?

741
00:30:54,173 --> 00:30:55,170

742
00:30:55,170 --> 00:30:55,670
Lahat ng karapatan.

743
00:30:55,670 --> 00:30:57,490
Ka lamang ng pagpunta sa
magagawang pumunta kaya mataas.

744
00:30:57,490 --> 00:31:00,156
At sa tingin ko sa Mather ang mga ito
talaga recessed sa na pagbubukas.

745
00:31:00,156 --> 00:31:01,950
Kaya nga, ito ay halos
tulad ng Mather ay gumagamit ng

746
00:31:01,950 --> 00:31:03,783
isang hanay ng mga nakapirming laki,
dahil maaari ka lamang

747
00:31:03,783 --> 00:31:08,302
magkasya kaya maraming mga trays sa pambungad na sa
sa pader pababa sa ibaba tuhod ng mga tao.

748
00:31:08,302 --> 00:31:10,010
At sa gayon ay maaaring maging
sinabi sa isang array,

749
00:31:10,010 --> 00:31:14,300
ngunit maaari kaming tiyak na ipatupad na
higit pa sa pangkalahatan ay may isang naka-link na listahan.

750
00:31:14,300 --> 00:31:16,390
>> Well, kung ano ang tungkol sa isa pang istraktura ng data?

751
00:31:16,390 --> 00:31:18,760
Hayaan akong makuha ang isa sa iba pang mga visual na dito.

752
00:31:18,760 --> 00:31:24,710
Isang bagay na tulad ng kung paano tungkol sa isang ito dito?

753
00:31:24,710 --> 00:31:28,920
Kung ano ang maaaring maging kapaki-pakinabang na magkaroon ng hindi
isang bagay bilang magarbong bilang isang trie, na

754
00:31:28,920 --> 00:31:32,370
nakita namin ay may mga napaka lapad nodes,
ang bawat isa ay nasa isang array?

755
00:31:32,370 --> 00:31:35,740
Ngunit paano kung ang ginagawa namin ng isang bagay na higit pa
lamang, tulad ng isang lumang puno ng pamilya ng paaralan,

756
00:31:35,740 --> 00:31:38,110
ang bawat isa sa kung saan ang mga node dito
ay ang pag-iimbak lamang ang isang numero.

757
00:31:38,110 --> 00:31:42,180
Sa halip na isang pangalan o isang supling
ay ang pag-iimbak lamang ng isang numero tulad nito.

758
00:31:42,180 --> 00:31:45,250
>> Well, ang magulong pag-uusap na ginagamit namin sa
mga istraktura ng data ay ang parehong pagsubok

759
00:31:45,250 --> 00:31:49,510
at mga puno, kung saan ang isang trie, muli, ay
isa na kung saan ang mga node ay array lamang,

760
00:31:49,510 --> 00:31:51,680
pa rin ang kung ano ang maaari kang
gamitin mula sa mababang paaralan

761
00:31:51,680 --> 00:31:53,860
kapag gumawa ka ng isang pamilya
tree-- dahon at root

762
00:31:53,860 --> 00:31:57,250
mula sa puno at mga bata ng mga
magulang at kapatid noon.

763
00:31:57,250 --> 00:32:03,670
At maaari naming ipatupad ng isang puno,
halimbawa, bilang simpleng bilang na ito.

764
00:32:03,670 --> 00:32:07,420
Puno A, kung ito bilang isang node, isa sa
mga lupon na may isang numero,

765
00:32:07,420 --> 00:32:09,947
hindi ito pagpunta sa may
isang pointer, ngunit dalawang.

766
00:32:09,947 --> 00:32:11,780
At sa sandaling idagdag mo
isang pangalawang pointer, mo

767
00:32:11,780 --> 00:32:13,905
Maaari aktwal na ngayon ng pag-uuri
ng dalawang-dimensional na data

768
00:32:13,905 --> 00:32:14,780
kaayusan sa memory.

769
00:32:14,780 --> 00:32:16,660
Karamihan tulad ng isang dalawang-dimensional
array, maaari kang

770
00:32:16,660 --> 00:32:18,904
May uri ng dalawang-dimensional
mga listahan ng mga ngunit naka-link

771
00:32:18,904 --> 00:32:20,820
na sundin ang isang pattern
kung saan walang cycle.

772
00:32:20,820 --> 00:32:24,487
Ito ay tunay na isang puno na may isang
lolo o lola paraan up dito at pagkatapos ay

773
00:32:24,487 --> 00:32:27,320
ang ilang mga magulang at mga anak at
apo at apo sa apo.

774
00:32:27,320 --> 00:32:28,370
at iba pa.

775
00:32:28,370 --> 00:32:32,390
>> Ngunit kung ano ang talagang kapong baka tungkol sa masyadong,
lamang upang mang-ulol sa iyo ng isang bit ng code,

776
00:32:32,390 --> 00:32:35,370
pagpapabalik mula sa Rekursiyon
sandali bumalik, kung saan

777
00:32:35,370 --> 00:32:38,220
sumulat ka ng isang function na tawag mismo.

778
00:32:38,220 --> 00:32:41,140
Ito ay isang magandang pagkakataon
upang ipatupad ang isang bagay

779
00:32:41,140 --> 00:32:42,920
tulad ng Rekursiyon, dahil isaalang-alang na ito.

780
00:32:42,920 --> 00:32:43,860
>> Ito ay isang tree.

781
00:32:43,860 --> 00:32:48,040
At ko pa ng kaunti anal sa kung paano
Naglagay ako ng integer sa kalye.

782
00:32:48,040 --> 00:32:51,020
Kaya magkano upang ito ay may espesyal na
name-- isang binary paghahanap tree.

783
00:32:51,020 --> 00:32:53,460
Ngayon nalaman namin ng binary
maghanap, ngunit maaari kang

784
00:32:53,460 --> 00:32:55,180
gumagana pabalik mula pangalan bagay na ito?

785
00:32:55,180 --> 00:32:59,280
Ano ang pattern ng kung paano ko
Ipinasok ang integer sa puno na ito?

786
00:32:59,280 --> 00:33:00,696
Ito ay hindi di-makatwirang.

787
00:33:00,696 --> 00:33:01,570
Mayroong ilang mga pattern.

788
00:33:01,570 --> 00:33:02,090
Oo.

789
00:33:02,090 --> 00:33:03,370
>> Madla: Mas Maliit mga nasa kaliwa.

790
00:33:03,370 --> 00:33:03,690
>> David MALAN: Oo.

791
00:33:03,690 --> 00:33:05,062
Mas maliit alin ang sa kaliwa.

792
00:33:05,062 --> 00:33:06,270
Mas malaki alin ang sa kanan.

793
00:33:06,270 --> 00:33:12,940
Ang ganitong na ang isang tunay na pahayag ay isang
magulang ay mas malaki sa kaliwang anak nito,

794
00:33:12,940 --> 00:33:14,850
ngunit mas mababa sa kanang anak nito.

795
00:33:14,850 --> 00:33:17,750
At na lamang ang kahit na isang
recursive pandiwang kahulugan

796
00:33:17,750 --> 00:33:20,500
dahil maaari kang mag-aplay na
parehong logic sa bawat node

797
00:33:20,500 --> 00:33:23,080
at ito lamang bottoms
out, isang batayang kaso kung

798
00:33:23,080 --> 00:33:25,740
gagawin kapag pinindot ninyo ang isa sa mga
mga dahon, kaya upang magsalita,

799
00:33:25,740 --> 00:33:28,580
kung saan ang isang bakasyon ay may karagdagang mga bata.

800
00:33:28,580 --> 00:33:30,614
>> Ngayon kung paano maaari mong makita ang bilang 44?

801
00:33:30,614 --> 00:33:32,280
Gusto mong simulan sa root at sabihin, Hm.

802
00:33:32,280 --> 00:33:35,690
55 Hindi 44 Kaya ang gusto ko ang umalis
karapatan o ang gusto kong sasamang kaliwa?

803
00:33:35,690 --> 00:33:37,190
Well, malinaw naman gusto mong pumunta kaliwa.

804
00:33:37,190 --> 00:33:40,060
At kaya tulad lamang ang telepono
Halimbawa aklat sa binary paghahanap

805
00:33:40,060 --> 00:33:41,099
higit pa sa pangkalahatan.

806
00:33:41,099 --> 00:33:43,390
Ngunit kami ay pagpapatupad ng mga ito
ngayon ng kaunti pa sa pabagu-bagong

807
00:33:43,390 --> 00:33:45,339
kaysa sa maaaring payagan ang isang array.

808
00:33:45,339 --> 00:33:48,130
At sa katunayan, kung nais mong hanapin
sa code, sa unang tingin sigurado.

809
00:33:48,130 --> 00:33:49,671
Mukhang ang maramihang mga linya.

810
00:33:49,671 --> 00:33:51,220
Ngunit ito ay maganda simple.

811
00:33:51,220 --> 00:33:54,490
Kung gusto mong ipatupad ang isang function
tinatawag na paghahanap na layunin sa buhay

812
00:33:54,490 --> 00:33:57,290
ay upang maghanap para sa isang halaga
tulad n, isang integer,

813
00:33:57,290 --> 00:34:01,756
at tapos ka nakapasa sa isang isa pointer--
isang pointer sa node ng mga ugat,

814
00:34:01,756 --> 00:34:04,380
sa halip, ng punong kahoy na mula sa kung saan
maaari mong ma-access ang lahat ng iba pa,

815
00:34:04,380 --> 00:34:08,850
pansinin kung paano straightforwardly
maaari mong ipatupad ang logic.

816
00:34:08,850 --> 00:34:10,880
Kung puno ay null,
Malinaw na hindi ito doon.

817
00:34:10,880 --> 00:34:11,880
Hayaan ang mga bumalik na lamang false.

818
00:34:11,880 --> 00:34:12,000
Mag-right?

819
00:34:12,000 --> 00:34:14,040
Kung ipasa mo ito wala,
walang mayroong.

820
00:34:14,040 --> 00:34:17,900
>> Iba Pa, kung n ay mas mababa sa
puno arrow n-- ngayon arrow n,

821
00:34:17,900 --> 00:34:20,670
isipin ipinakilala namin ang sobrang
sa madaling sabi ang iba pang mga araw,

822
00:34:20,670 --> 00:34:25,100
at na lamang ay nangangahulugan de-reference ang
pointer at tumingin sa patlang na tinatawag n.

823
00:34:25,100 --> 00:34:27,690
Kaya ito ay nangangahulugan na pumunta doon at
tumingin sa patlang na tinatawag n.

824
00:34:27,690 --> 00:34:33,810
Kaya kung n, ang halaga na iyong ibinigay, ay mas mababa
kaysa sa halaga sa mga puno integer,

825
00:34:33,810 --> 00:34:35,449
kung saan mo gustong pumunta?

826
00:34:35,449 --> 00:34:36,389
Sa kaliwa.

827
00:34:36,389 --> 00:34:37,780
>> Kaya mapansin ang Rekursiyon.

828
00:34:37,780 --> 00:34:39,860
Ako returning-- hindi totoo.

829
00:34:39,860 --> 00:34:40,989
Hindi totoo.

830
00:34:40,989 --> 00:34:45,670
Ako bumabalik anuman ang sagot
ay mula sa isang pagtawag sa sarili ko, pagpasa

831
00:34:45,670 --> 00:34:50,100
muli ng isang n, na paulit-ulit,
ngunit kung ano ang bahagyang naiiba ngayon?

832
00:34:50,100 --> 00:34:51,989
Paano ako sa paggawa ng mga problema sa mas maliit?

833
00:34:51,989 --> 00:34:54,920
Ako pagpasa sa bilang ikalawang
argument, hindi root ng tree,

834
00:34:54,920 --> 00:34:59,616
ngunit sa kaliwang bata sa kasong ito.

835
00:34:59,616 --> 00:35:00,990
Kaya ako pagpasa sa kaliwang bata.

836
00:35:00,990 --> 00:35:04,720
>> Samantala, kung n ay mas malaki kaysa
ang node na kasalukuyan kong tinitingnan,

837
00:35:04,720 --> 00:35:06,690
Hahanapin ko ang kanang bahagi.

838
00:35:06,690 --> 00:35:10,880
Iba Pa, kung ang puno ay hindi null, at
kung ang elemento hindi sa kaliwa

839
00:35:10,880 --> 00:35:13,240
at ito ay hindi sa kanan,
kung ano ang kamangha-mangha ang kaso?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
Na tunay na nakita namin ang node sa
-uusapan, at kaya bumalik kami totoo.

842
00:35:18,440 --> 00:35:21,490
>> Kaya nagbigay lamang scratched namin ang ibabaw
ngayon ang ilan sa mga mga istraktura ng data.

843
00:35:21,490 --> 00:35:24,370
Sa set problema limang ikaw
galugarin ang mga pang karagdagang,

844
00:35:24,370 --> 00:35:27,250
at makikita mo dapat ibigay ang iyong mga disenyo
pagpili ng kung paano pumunta tungkol dito.

845
00:35:27,250 --> 00:35:30,250
Ano Gusto kong pagtibayin sa
ay isang 30 segundong teaser lamang

846
00:35:30,250 --> 00:35:32,080
ng kung ano ang naghihintay sa susunod na linggo at higit pa.

847
00:35:32,080 --> 00:35:35,390
>> Bilang begin-- namin Sa kabutihang palad maaari kang
think-- aming transition mabagal

848
00:35:35,390 --> 00:35:38,680
mula sa mundo ng C at mas mababang
Mga detalye ng pagpapatupad antas,

849
00:35:38,680 --> 00:35:42,090
sa isang mundo kung saan maaari kaming magsagawa ng para sa
Binigyan na ibang tao ay sa wakas

850
00:35:42,090 --> 00:35:44,010
nagpatupad ng mga data
kaayusan para sa atin,

851
00:35:44,010 --> 00:35:47,570
at magsisimula kami upang maunawaan ang mga
tunay na mundo ay nangangahulugan ng pagpapatupad

852
00:35:47,570 --> 00:35:50,560
mga programa ng web-based at
mga website sa mas pangkalahatang paraan

853
00:35:50,560 --> 00:35:52,910
at din ang seguridad napaka
implikasyon na hindi namin lamang

854
00:35:52,910 --> 00:35:54,850
nagsimula sa scratch sa ibabaw ng.

855
00:35:54,850 --> 00:35:57,320
Narito ang kung ano ang naghihintay sa amin
sa araw na darating.

856
00:35:57,320 --> 00:36:00,480
>> [VIDEO pag-playback]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -He Kasama ang isang mensahe,
may protocol ang lahat ng sarili niyang.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
Dumating siya sa isang mundo ng malupit
firewall, uncaring router,

861
00:36:30,894 --> 00:36:33,368
at mga panganib malayo mas masahol pa kaysa sa kamatayan.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
Siya ay mabilis.

864
00:36:36,236 --> 00:36:37,980
Siya ay malakas.

865
00:36:37,980 --> 00:36:42,830
Siya ay TCP / IP, at nakuha niya ang iyong address.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"Warriors ng Net."

868
00:36:48,074 --> 00:36:49,660
[END VIDEO pag-playback]

869
00:36:49,660 --> 00:36:50,910
David MALAN: Paparating susunod na linggo.

870
00:36:50,910 --> 00:36:51,880
Makikita natin sa iyo pagkatapos.

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[VIDEO pag-playback]

873
00:36:56,060 --> 00:36:59,240
-And Ngayon, "Deep saloobin"
sa pamamagitan ng Daven Farnham.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
Laging nagsisimula -David
mga aralin sa, "Lahat ng karapatan."

876
00:37:05,820 --> 00:37:08,750
Bakit hindi, "Narito ang solusyon
sa hanay problemang ito linggong "

877
00:37:08,750 --> 00:37:12,180
o "Kami ay nagbibigay sa lahat ng mga ka ng A?"

878
00:37:12,180 --> 00:37:13,380
[Tumatawa]

879
00:37:13,380 --> 00:37:15,530
[END VIDEO pag-playback]