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

2
00:00:00,500 --> 00:00:03,340
[MUSIC Playing]

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

4
00:00:11,020 --> 00:00:14,010
>> DAVID Malan: Kjo është CS50.

5
00:00:14,010 --> 00:00:18,090
Dhe ky është edhe fillimi dhe
end-- si literally-- pothuajse në fund

6
00:00:18,090 --> 00:00:18,825
nga java e gjashtë.

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

8
00:00:20,030 --> 00:00:22,640
>> Unë mendova se do të ndajnë një
pak e një fakt fun.

9
00:00:22,640 --> 00:00:25,370
Unë e kam tërhequr këtë nga a
Të dhënat SEMESTRI të kaluar caktuar.

10
00:00:25,370 --> 00:00:29,710
Ju mund të kujtojnë se ne ju kërkojmë të çdo
Forma e vendosur p qoftë se ju keni shikuar në internet

11
00:00:29,710 --> 00:00:31,580
ose në qoftë se ju keni marrë pjesë në në person.

12
00:00:31,580 --> 00:00:33,020
Dhe këtu është të të dhënave.

13
00:00:33,020 --> 00:00:34,710
Pra, sot ishte shumë e parashikueshme.

14
00:00:34,710 --> 00:00:37,126
Por ne të kërkuar për të shpenzuar pak
e kohës me ju gjithsesi.

15
00:00:37,126 --> 00:00:40,599
Dikush do të donte për hamendje pse kjo
grafik është aq i dhëmbëzuar, lart poshtë, lart poshtë,

16
00:00:40,599 --> 00:00:41,265
kështu vazhdimisht?

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

18
00:00:42,980 --> 00:00:45,130
Çfarë të bëjë secili nga majat
dhe troughs përfaqësojnë?

19
00:00:45,130 --> 00:00:46,005
>> Audienca: [padëgjueshme]

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

21
00:00:47,002 --> 00:00:47,835
DAVID Malan: Vërtet.

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

23
00:00:50,900 --> 00:00:55,480
Dhe më shumë amusingly, Zoti na ruajt,
ne të mbajë një ligjëratë në një e premte

24
00:00:55,480 --> 00:00:58,960
Në fillim të semestrit,
kjo është ajo që ne shohim të ndodhë.

25
00:00:58,960 --> 00:01:03,430
Pra sot, ne marrim pjesë në një grimë
më shumë në lidhje me strukturat e të dhënave.

26
00:01:03,430 --> 00:01:06,660
Dhe për të ju jap më shumë një të ngurta
Modeli mendor për problemet në pesë,

27
00:01:06,660 --> 00:01:07,450
e cila është tani jashtë.

28
00:01:07,450 --> 00:01:10,817
Gabim, ku, ne do të
ju dorëzojë një skedar teksti disa 100,000

29
00:01:10,817 --> 00:01:12,650
plus fjalë anglisht, dhe
ju jeni do të ketë

30
00:01:12,650 --> 00:01:17,770
të kuptoj se si për të cleverly ngarkesës së tyre
në kujtesë, në RAM, duke përdorur disa të dhëna

31
00:01:17,770 --> 00:01:19,330
Struktura e zgjedhjes suaj.

32
00:01:19,330 --> 00:01:22,470
>> Tani një strukturë e të dhënave të tilla mund të
të jetë, por ndoshta nuk duhet të jetë,

33
00:01:22,470 --> 00:01:25,630
lista mjaft e thjeshtë të lidhur,
të cilat ne kemi prezantuar për herë të fundit.

34
00:01:25,630 --> 00:01:29,220
Dhe një listë e lidhur kishin të paktën
një avantazh mbi një rrjet.

35
00:01:29,220 --> 00:01:32,096
Çfarë është një avantazh i
një listë e lidhur në mënyrë të diskutueshme?

36
00:01:32,096 --> 00:01:32,950
>> AUDIENCA: hyrjes.

37
00:01:32,950 --> 00:01:33,908
>> DAVID Malan: hyrjes.

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

39
00:01:34,155 --> 00:01:35,196
Çfarë doni të thoni me këtë?

40
00:01:35,196 --> 00:01:37,872
>> AUDIENCA: Anywhere bashku
Lista [padëgjueshme].

41
00:01:37,872 --> 00:01:38,770
>> DAVID Malan: Mirë.

42
00:01:38,770 --> 00:01:42,090
Kështu që ju mund të futni një element kudo që
ju doni në mes të listës

43
00:01:42,090 --> 00:01:45,490
pa pasur nevojë për të riorganizimi asgjë,
të cilat kemi konstatuar, në klasifikim tonë

44
00:01:45,490 --> 00:01:47,630
diskutimet, nuk është e
domosdoshmërisht një gjë e mirë,

45
00:01:47,630 --> 00:01:51,200
për shkak se ajo merr kohë për të vërtetë të lëvizur
të gjithë atyre njerëzve të majtë apo të djathtë.

46
00:01:51,200 --> 00:01:55,540
Dhe kështu me një listë të lidhur, ju mund të
vetëm ndajë me malloc, një nyje të re,

47
00:01:55,540 --> 00:01:58,385
dhe pastaj update një çift të
pointers-- dy, tre operacione max--

48
00:01:58,385 --> 00:02:01,480
dhe ne jemi në gjendje për të çarë dikë
në kudo në një listë.

49
00:02:01,480 --> 00:02:03,550
>> Çfarë tjetër ka qenë i favorshëm
në lidhje me një listë të lidhura?

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

51
00:02:04,980 --> 00:02:05,659
Vërtet?

52
00:02:05,659 --> 00:02:06,534
>> Audienca: [padëgjueshme]

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

54
00:02:07,538 --> 00:02:08,413
DAVID Malan: Perfect.

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

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

57
00:02:11,090 --> 00:02:12,070
Është e vërtetë dinamike.

58
00:02:12,070 --> 00:02:15,100
Dhe se ju nuk jeni duke kryer,
më parë, në disa madhësi fikse

59
00:02:15,100 --> 00:02:18,750
copë e kujtesës, si ju do të keni
tek me një grup, të përmbysur e cila

60
00:02:18,750 --> 00:02:22,455
është se ju mund të ndajë nyje vetëm në
Kërkesa e duke përdorur vetëm sa më shumë hapësirë

61
00:02:22,455 --> 00:02:23,330
si ju duhet të vërtetë.

62
00:02:23,330 --> 00:02:26,830
Në kontrast me një rrjet, ju mund të
aksidentalisht ndajë shumë pak.

63
00:02:26,830 --> 00:02:28,871
Dhe atëherë ajo është vetëm do
të jetë një dhimbje në qafës

64
00:02:28,871 --> 00:02:32,440
për të rialokuar një koleksion të ri të madh, kopje
gjithçka mbi, të lirë array vjetër,

65
00:02:32,440 --> 00:02:33,990
dhe më pas të shkojë në lidhje me biznesin tuaj.

66
00:02:33,990 --> 00:02:37,479
Ose më keq, ju mund të ndajë rrugën
më shumë memorie se ju në të vërtetë nevojë,

67
00:02:37,479 --> 00:02:40,520
dhe kështu që ju jeni do të ketë një shumë të
paktë populluar grup, kështu që të flasin.

68
00:02:40,520 --> 00:02:44,350
>> Pra, një listë e lidhur ju jep këto
Përparësitë e dinamizëm dhe fleksibilitet

69
00:02:44,350 --> 00:02:46,080
me insertions dhe fshirje.

70
00:02:46,080 --> 00:02:48,000
Por, me siguri duhet të ketë një çmim të paguar.

71
00:02:48,000 --> 00:02:50,000
Në fakt, një nga temat
hulumtohen në quiz zero

72
00:02:50,000 --> 00:02:52,430
Ishte një çift i tregtisë të humbura
ne kemi parë deri tani.

73
00:02:52,430 --> 00:02:56,161
Pra, çfarë është çmimi i paguar ose
dobësitë e një liste të lidhur?

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

75
00:02:56,660 --> 00:02:57,560
>> AUDIENCA: Nuk ka qasje të rastit.

76
00:02:57,560 --> 00:02:58,809
>> DAVID Malan: Nuk ka qasje të rastit.

77
00:02:58,809 --> 00:02:59,540
Por kush kujdeset?

78
00:02:59,540 --> 00:03:01,546
Qasje të rastësishme nuk tingëllon bindëse.

79
00:03:01,546 --> 00:03:02,421
>> Audienca: [padëgjueshme]

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

81
00:03:04,865 --> 00:03:05,740
DAVID Malan: Pikërisht.

82
00:03:05,740 --> 00:03:07,580
Nëse ju dëshironi të keni
a algorithm-- të caktuar

83
00:03:07,580 --> 00:03:10,170
dhe më lejoni të vërtetë të propozojë
kërko binar në veçanti, të cilat

84
00:03:10,170 --> 00:03:12,600
është një që kam përdorur mjaft bit--
në qoftë se ju nuk keni qasje të rastit,

85
00:03:12,600 --> 00:03:15,516
ju nuk mund të bëni atë aritmetikë të thjeshtë
i gjetur si elementin e mesme

86
00:03:15,516 --> 00:03:16,530
dhe hedhur të drejtë në të.

87
00:03:16,530 --> 00:03:20,239
Ju në vend të kësaj duhet të fillojë në fillim
element dhe lineare kërko nga e majta

88
00:03:20,239 --> 00:03:22,780
në të djathtë në qoftë se ju doni të gjeni
mesme apo ndonjë element tjetër.

89
00:03:22,780 --> 00:03:24,410
>> AUDIENCA: Kjo ndoshta merr shumë memorie.

90
00:03:24,410 --> 00:03:25,040
>> DAVID Malan: merr më shumë memorie.

91
00:03:25,040 --> 00:03:27,464
Ku është kjo shtesë
kosto që vijnë nga në kujtesë?

92
00:03:27,464 --> 00:03:28,339
>> Audienca: [padëgjueshme]

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

94
00:03:32,566 --> 00:03:33,440
DAVID Malan: Pikërisht.

95
00:03:33,440 --> 00:03:35,679
Në këtë rast këtu, kemi pasur
një listë e lidhur për integers,

96
00:03:35,679 --> 00:03:37,470
por ne jemi duke dyfishuar
shuma e memories

97
00:03:37,470 --> 00:03:39,680
ne kemi nevojë për të ruajtur këto pointers.

98
00:03:39,680 --> 00:03:42,090
Tani pak e një punë e madhe si
structs tuaj të merrni më të mëdha

99
00:03:42,090 --> 00:03:45,320
dhe ju jeni ruajtjen jo një numër, por
ndoshta një student apo ndonjë objekt tjetër.

100
00:03:45,320 --> 00:03:46,880
Por pika me siguri mbetet.

101
00:03:46,880 --> 00:03:49,421
Dhe kështu që një numër i operacioneve
në listat e lidhura quheshin

102
00:03:49,421 --> 00:03:50,570
ishin O i madh i n-- lineare.

103
00:03:50,570 --> 00:03:54,730
Gjëra të tilla si futje apo kërkim
ose fshirjen në rast se një element

104
00:03:54,730 --> 00:03:57,720
ka ndodhur të jetë në fund të
lista nëse është e renditura ose jo.

105
00:03:57,720 --> 00:04:01,167
>> Ndonjëherë ju mund të merrni me fat dhe në
kufijtë aq më e ulët në këto operacione

106
00:04:01,167 --> 00:04:04,250
mund të jetë koha konstante në qoftë se ju jeni
gjithmonë kërkuar në elementin e parë,

107
00:04:04,250 --> 00:04:05,070
për shembull.

108
00:04:05,070 --> 00:04:09,360
Por në fund të fundit, ne kemi premtuar
për të arritur Grail shenjtë

109
00:04:09,360 --> 00:04:12,630
i strukturave të të dhënave, ose
disa e saj përafrimi,

110
00:04:12,630 --> 00:04:14,290
nga mënyra e kohës konstante.

111
00:04:14,290 --> 00:04:17,579
Mund të gjejmë elemente apo të shtoni elemente
ose hequr elementet nga një listë?

112
00:04:17,579 --> 00:04:19,059
Ne do të shohim shumë shpejt.

113
00:04:19,059 --> 00:04:21,100
Dhe kjo rezulton se një
i mekanizmave ne jemi

114
00:04:21,100 --> 00:04:23,464
do të fillojnë të përdorin sot,
Përdorimi vjetore në p vendosur pesë,

115
00:04:23,464 --> 00:04:24,630
është në të vërtetë shumë e njohur.

116
00:04:24,630 --> 00:04:27,430
Për shembull, në qoftë se kjo është një bandë
librash provimit, secila prej të cilave

117
00:04:27,430 --> 00:04:29,660
ka një student e parë
emrin dhe mbiemrin në të,

118
00:04:29,660 --> 00:04:31,820
dhe unë marr ato nga
në fund të një provimit,

119
00:04:31,820 --> 00:04:33,746
dhe ata janë të gjithë mjaft të
shumë në një mënyrë të rastit,

120
00:04:33,746 --> 00:04:36,370
dhe ne duam të shkojnë për klasifikim
këto provime në mënyrë që sapo të vlerësohet

121
00:04:36,370 --> 00:04:38,661
kjo është vetëm një shumë më e lehtë dhe të
më shpejt t'i dorëzojë ato nga mbrapa

122
00:04:38,661 --> 00:04:40,030
për studentët alfabetik.

123
00:04:40,030 --> 00:04:42,770
Çfarë do të jetë instinktet tuaja
për një grumbull të provimeve si kjo?

124
00:04:42,770 --> 00:04:45,019
>> E pra, në qoftë se ju jeni si unë, ju
mund të shihni se kjo është m,

125
00:04:45,019 --> 00:04:48,505
kështu që unë jam duke shkuar për lloj të vënë këtë në,
nëse kjo është tabelë ime apo kat im ku

126
00:04:48,505 --> 00:04:50,650
Unë jam përhapjen gjëra
out-- ose array tim really--

127
00:04:50,650 --> 00:04:52,210
Unë mund të vënë të gjitha të znj në atje.

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

129
00:04:52,710 --> 00:04:55,020
Këtu është një A. Kështu që unë mund të
vënë si mbi këtu.

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

131
00:04:55,520 --> 00:04:57,980
Këtu është një tjetër A. Unë jam duke shkuar
për të vënë atë mbi këtu.

132
00:04:57,980 --> 00:05:02,490
Këtu është një Z. Këtu është një tjetër M. Dhe kështu
Unë mund të fillojnë të bëjnë grumbujt si kjo.

133
00:05:02,490 --> 00:05:06,620
Dhe pastaj ndoshta unë do të shkoj më vonë
dhe lloj shumë nitpicky-ly lloj

134
00:05:06,620 --> 00:05:07,710
grumbujt individuale.

135
00:05:07,710 --> 00:05:11,300
Por çështja është që unë do të shikojmë
në kontributin që unë jam dorëzuar

136
00:05:11,300 --> 00:05:14,016
dhe unë do të bëjë disa llogaritur
Vendimi bazohet në atë të dhëna.

137
00:05:14,016 --> 00:05:15,640
Nëse fillon me A, e vënë atë atje.

138
00:05:15,640 --> 00:05:18,980
Nëse fillon me Z, e vënë atë mbi
atje, dhe çdo gjë në mes.

139
00:05:18,980 --> 00:05:22,730
>> Pra, kjo është një teknikë që është
përgjithësisht i njohur si hashing-- H-A-S-H--

140
00:05:22,730 --> 00:05:26,550
të cilat në përgjithësi do të thotë duke marrë si
input dhe duke përdorur këtë të dhëna për të llogaritur

141
00:05:26,550 --> 00:05:30,940
një vlerë, përgjithësisht një numër, dhe që
Numri është indeksi në ruajtje

142
00:05:30,940 --> 00:05:32,260
enë, si një rrjet.

143
00:05:32,260 --> 00:05:35,490
Pra, me fjalë të tjera, unë mund të ketë një
funksion hash, siç po bëj unë në kokën time,

144
00:05:35,490 --> 00:05:37,940
se në qoftë se unë shoh se dikush është
Emri i cili fillon me A,

145
00:05:37,940 --> 00:05:40,190
Unë jam duke shkuar për të hartë atë
për të zero në kokën time.

146
00:05:40,190 --> 00:05:44,160
Dhe në qoftë se unë shoh dikë me Z, unë jam
do të ndajë se për 25 në kokën time

147
00:05:44,160 --> 00:05:46,220
dhe pastaj të vënë atë në
grumbull fundit më.

148
00:05:46,220 --> 00:05:50,990
>> Tani, në qoftë se ju mendoni për të mos truri im
por një program C, çfarë numrat mund

149
00:05:50,990 --> 00:05:53,170
ju të mbështetet në për të arritur që të njëjtën rezultat?

150
00:05:53,170 --> 00:05:55,594
Me fjalë të tjera, në qoftë se ju
kishte ASCII karakter A,

151
00:05:55,594 --> 00:05:57,510
si mund ta përcaktoni
çfarë kovë për të vënë atë në?

152
00:05:57,510 --> 00:05:59,801
Ju ndoshta nuk duan të
e vënë atë në kovë 65, e cila

153
00:05:59,801 --> 00:06:01,840
do të jetë si atje
për asnjë arsye të mirë.

154
00:06:01,840 --> 00:06:04,320
Ku doni të vendosni një
në terma të vlerës së saj ASCII?

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

156
00:06:05,600 --> 00:06:08,920
Ku doni të bëni të saj ASCII
Vlera për të dalë me një kovë të zgjuar

157
00:06:08,920 --> 00:06:09,480
për ta vënë atë në?

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

159
00:06:10,206 --> 00:06:10,956
>> DAVID Malan: Po.

160
00:06:10,956 --> 00:06:13,190
Pra, minus një ose minus
veçanërisht 65 nëse është e

161
00:06:13,190 --> 00:06:18,240
a A. Kapitali Ose 98 nëse
kjo është një Fjala a.

162
00:06:18,240 --> 00:06:21,300
Dhe kështu që do të na lejojë të, shumë
thjesht dhe shumë arithmetically,

163
00:06:21,300 --> 00:06:23,260
vënë diçka në një kovë si kjo.

164
00:06:23,260 --> 00:06:26,010
Pra, ajo rezulton ne fakt bëjmë
këtë si edhe me kuize.

165
00:06:26,010 --> 00:06:29,051
>> Kështu që ju mund të kujtohet qe rrethuar tuaj
Emri i shokut të mësimdhënies në kopertinën.

166
00:06:29,051 --> 00:06:32,270
Dhe u organizuan emrat TF-së
në këto kolona alfabetikisht,

167
00:06:32,270 --> 00:06:34,400
mirë, besoj se kjo apo jo,
kur të gjithë 80 plus ne

168
00:06:34,400 --> 00:06:37,800
marrë së bashku natën tjetër të klasës,
hapi i fundit në procesin tonë të notimit

169
00:06:37,800 --> 00:06:41,830
është të hash kuize në një të madhe
Hapësira e katit në [e padëgjueshme]

170
00:06:41,830 --> 00:06:45,110
dhe të vënë kuize gjithëve out
pikërisht në mënyrë të Grupit Punues-tat

171
00:06:45,110 --> 00:06:47,700
emrat në kopertinën, sepse
atëherë kjo është një shumë më e lehtë për ne

172
00:06:47,700 --> 00:06:51,290
për të kërkuar nëpër atë duke përdorur lineare
kërko apo ndonjë lloj zgjuarsi

173
00:06:51,290 --> 00:06:54,050
për një TF për të gjetur të tij ose
kuize studentëve të saj.

174
00:06:54,050 --> 00:06:56,060
>> Pra, kjo ide e hashing
që ju do të shihni është

175
00:06:56,060 --> 00:07:00,520
mjaft e fuqishme është në të vërtetë shumë e
zakonshme dhe shumë intuitiv,

176
00:07:00,520 --> 00:07:03,000
ashtu si ndoshta ndajnë dhe
Conquer ishte në javë zero.

177
00:07:03,000 --> 00:07:05,250
Unë përpara të shpejtë të hackathon
nja dy vjet më parë.

178
00:07:05,250 --> 00:07:08,040
Kjo ishte Zamyla dhe një çift i
nxënësit e tjerë përshëndetje stafi

179
00:07:08,040 --> 00:07:09,030
si ata erdhën.

180
00:07:09,030 --> 00:07:12,680
Dhe ne kishim një bandë e tërë e palosjes
tavolina atje me emrin tags.

181
00:07:12,680 --> 00:07:15,380
Dhe ne kishim organizuar tags emrin
me si As mbi atje

182
00:07:15,380 --> 00:07:16,690
dhe Zs atje.

183
00:07:16,690 --> 00:07:20,350
Dhe kështu një nga TFS shumë cleverly
shkroi këtë si udhëzimet

184
00:07:20,350 --> 00:07:21,030
për ditë.

185
00:07:21,030 --> 00:07:24,480
Dhe në javën e 12 të këtij semestrit
të gjitha ka kuptim të përsosur dhe të gjithë

186
00:07:24,480 --> 00:07:25,310
e dinte se çfarë të bëni.

187
00:07:25,310 --> 00:07:27,900
Por kurdo që ju keni
queued në të njëjtën mënyrë,

188
00:07:27,900 --> 00:07:30,272
ju jeni zbatimin
njëjtë nocioni i një hash.

189
00:07:30,272 --> 00:07:31,730
Pra, le të zyrtarizojë atë një pak.

190
00:07:31,730 --> 00:07:32,890
Këtu është një koleksion.

191
00:07:32,890 --> 00:07:36,820
Është tërhequr të jetë pak
të gjerë vetëm të përshkruaj, me sy,

192
00:07:36,820 --> 00:07:38,920
që ne të mund të vënë strings
në diçka si kjo.

193
00:07:38,920 --> 00:07:41,970
Dhe ky grup është
në mënyrë të qartë i madhësisë 26 gjithsej.

194
00:07:41,970 --> 00:07:43,935
Dhe gjëja është quajtur
tryezë në mënyrë arbitrare.

195
00:07:43,935 --> 00:07:48,930
Por kjo është vetëm interpretim një artisti
e asaj që mund të jetë një tavolinë hash.

196
00:07:48,930 --> 00:07:52,799
>> Pra, një tabelë hash tani do të
të jetë një strukturë e të dhënave të nivelit të lartë.

197
00:07:52,799 --> 00:07:54,840
Në fund të ditës
ne jemi gati për të parë se ju

198
00:07:54,840 --> 00:07:58,700
mund të zbatojë një tabelë hash, e cila
është shumë si vijë check-in

199
00:07:58,700 --> 00:08:02,059
në një hackathon shumë si kjo
Tabela e përdorura për klasifikimin e librave provimit.

200
00:08:02,059 --> 00:08:03,850
Por një tabelë hash është
lloj i këtij niveli të lartë

201
00:08:03,850 --> 00:08:08,250
koncept që mund të përdorin një rrjet
nën individualitet ta zbatuar atë,

202
00:08:08,250 --> 00:08:11,890
ose ajo mund të përdorni një listë gjatësi, apo edhe
ndoshta disa struktura të tjera të të dhënave.

203
00:08:11,890 --> 00:08:15,590
Dhe tani që është marrja theme--
disa prej këtyre përbërësve themelore

204
00:08:15,590 --> 00:08:18,310
si një grup dhe kjo ndërtesë
bllokuar tani për një listë gjatësi

205
00:08:18,310 --> 00:08:21,740
dhe duke parë se çfarë tjetër që ne mund të ndërtojmë
në krye të atyre që, si përbërësit

206
00:08:21,740 --> 00:08:26,550
në një recetë, duke e bërë gjithnjë e më shumë
Rezultatet e interesante dhe të dobishme përfundimtare.

207
00:08:26,550 --> 00:08:28,680
>> Pra, me tabelë hash
ne mund të zbatojë atë

208
00:08:28,680 --> 00:08:32,540
në kujtesën e në pikturë si kjo, por
si mund të vërtetë të jetë i koduar up?

209
00:08:32,540 --> 00:08:33,789
E pra, ndoshta pasi thjesht është kjo.

210
00:08:33,789 --> 00:08:38,270
Nëse KAPACITETI në të gjitha shkronja kapitale, është vetëm
disa constant-- për shembull 26,

211
00:08:38,270 --> 00:08:42,030
për 26 letrat e alphabet--
Unë mund të thërrasë tryezën time ndryshueshme,

212
00:08:42,030 --> 00:08:45,630
dhe unë mund të pretendojnë se unë jam duke shkuar për
vënë yjet CHAR në atje, apo string.

213
00:08:45,630 --> 00:08:49,880
Pra, ajo është aq e thjeshtë si kjo në qoftë se ju
duan për të zbatuar një tabelë hash.

214
00:08:49,880 --> 00:08:51,490
Dhe megjithatë, kjo është me të vërtetë vetëm një grup.

215
00:08:51,490 --> 00:08:53,198
Por përsëri, a hash
Tabela tani është ajo që ne do të

216
00:08:53,198 --> 00:08:57,470
thërrisni një lloj abstrakte e të dhënave që është e drejtë
lloj i një layering konceptuale në krye

217
00:08:57,470 --> 00:09:00,780
e diçka më shumë i zakonshëm
tani doja një rrjet.

218
00:09:00,780 --> 00:09:02,960
>> Tani, si do të shkojmë
për zgjidhjen e problemeve?

219
00:09:02,960 --> 00:09:06,980
E pra, më herët kam pasur luksin
për të pasur hapësirë ​​të mjaftueshme tryezë këtu

220
00:09:06,980 --> 00:09:09,460
në mënyrë që unë mund të vënë
kuize kudo kam kërkuar.

221
00:09:09,460 --> 00:09:10,620
Pra, si mund të shkoni këtu.

222
00:09:10,620 --> 00:09:12,100
Zs mund të shkoni këtu.

223
00:09:12,100 --> 00:09:13,230
Ms mund të shkoni këtu.

224
00:09:13,230 --> 00:09:14,740
Dhe pastaj kam pasur një hapësirë ​​shtesë.

225
00:09:14,740 --> 00:09:18,740
Por kjo është pak e një të drejte mashtrojnë
tani sepse këtë tryezë, në qoftë se unë me të vërtetë

226
00:09:18,740 --> 00:09:22,720
menduar atë si një grup, është vetëm
do të jenë të një madhësie të caktuar.

227
00:09:22,720 --> 00:09:25,380
>> Pra teknikisht, në qoftë se unë tërheq
up quiz tjetër studentit

228
00:09:25,380 --> 00:09:28,490
dhe shikoni, oh, ky personi
Emri i fillon me një A tepër,

229
00:09:28,490 --> 00:09:30,980
Unë lloj i dua të vënë atë atje.

230
00:09:30,980 --> 00:09:34,740
Por, sa më shpejt që kam vënë atë atje, në qoftë se
kjo tabelë të vërtetë paraqet një rrjet,

231
00:09:34,740 --> 00:09:37,840
Unë jam duke shkuar të jetë mbizotërues apo të clobbering
kushdo quiz këtë nxënës është.

232
00:09:37,840 --> 00:09:38,340
E drejtë?

233
00:09:38,340 --> 00:09:41,972
Nëse kjo është një grup, vetëm një gjë mund të
shkojnë në secilën nga këto qeliza ose elemente.

234
00:09:41,972 --> 00:09:43,680
Dhe kështu që unë lloj i kanë
të zgjedhë dhe të zgjedhin.

235
00:09:43,680 --> 00:09:45,735
>> Tani më parë I lloj
mashtruar dhe e bëri këtë apo I

236
00:09:45,735 --> 00:09:47,526
vetëm lloji i bërë pirg
ato sipër njëri tjetrin.

237
00:09:47,526 --> 00:09:49,170
Por kjo nuk do të fluturojnë në kodin.

238
00:09:49,170 --> 00:09:52,260
Pra, ku mund ta vënë
Studenti i dytë emri i të cilit

239
00:09:52,260 --> 00:09:54,964
A është nëse të gjithë kam pasur është kjo
hapësirë ​​tryezë në dispozicion?

240
00:09:54,964 --> 00:09:57,880
Dhe unë e kam përdorur tre lojëra elektronike dhe atë
duket sikur ka vetëm disa të tjerë.

241
00:09:57,880 --> 00:09:58,959
Çfarë mund të bëni?

242
00:09:58,959 --> 00:09:59,834
Audienca: [padëgjueshme]

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

244
00:10:00,565 --> 00:10:01,315
DAVID Malan: Po.

245
00:10:01,315 --> 00:10:02,370
Ndoshta le vetëm ta mbani atë të thjeshtë.

246
00:10:02,370 --> 00:10:02,660
E drejtë?

247
00:10:02,660 --> 00:10:04,243
Ajo nuk përshtatet ku unë dua të vënë atë.

248
00:10:04,243 --> 00:10:07,450
Kështu që unë jam duke shkuar për të vënë atë
teknikisht ku B do të shkojnë.

249
00:10:07,450 --> 00:10:09,932
Tani, natyrisht, unë jam duke filluar
për të pikturuar veten në një qoshe.

250
00:10:09,932 --> 00:10:11,890
Nëse unë të marrë për një student
emri i të cilit është në të vërtetë B,

251
00:10:11,890 --> 00:10:14,840
tani B do të të zhvendoset pak
përpara, siç mund të ndodhë, yep,

252
00:10:14,840 --> 00:10:17,530
në qoftë se kjo është një B, tani ajo ka për të shkuar këtu.

253
00:10:17,530 --> 00:10:20,180
>> Dhe kështu që kjo shumë shpejt
mund të bëhet problematike,

254
00:10:20,180 --> 00:10:23,850
por kjo është një teknikë që në fakt
është referuar si linear probing,

255
00:10:23,850 --> 00:10:26,650
ku ju vetëm konsideroni tuaj
array të jenë përgjatë vijës.

256
00:10:26,650 --> 00:10:29,680
Dhe ju vetëm lloji i hetuar apo
inspektojë çdo element në dispozicion

257
00:10:29,680 --> 00:10:31,360
duke kërkuar për një vend në dispozicion.

258
00:10:31,360 --> 00:10:34,010
Dhe, sa më shpejt që ju të gjeni
një, ju bie në atë pikë.

259
00:10:34,010 --> 00:10:38,390
>> Tani, çmimi u paguar tani
për këtë zgjidhje është ajo?

260
00:10:38,390 --> 00:10:41,300
Ne kemi një rrjet të madhësisë fikse,
dhe kur kam futur emra

261
00:10:41,300 --> 00:10:44,059
në të, të paktën në fillim, çfarë është
koha drejtimin e futje

262
00:10:44,059 --> 00:10:46,350
për vënien e nxënësve "
kuize në kova të drejtë?

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

264
00:10:48,710 --> 00:10:50,002
O Big për çfarë?

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

266
00:10:51,147 --> 00:10:52,480
DAVID Malan: Kam dëgjuar O e madhe e n.

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

268
00:10:53,530 --> 00:10:54,300
Nuk është e vërtetë.

269
00:10:54,300 --> 00:10:56,490
Por ne do të ngas përveç
pse në vetëm një moment.

270
00:10:56,490 --> 00:10:57,702
Çfarë tjetër mund të jetë?

271
00:10:57,702 --> 00:10:58,755
>> Audienca: [padëgjueshme]

272
00:10:58,755 --> 00:11:00,380
DAVID Malan: Dhe më lejoni të bëjë atë me sy.

273
00:11:00,380 --> 00:11:04,720
Pra, mendoj që kjo është letër S.

274
00:11:04,720 --> 00:11:05,604
>> AUDIENCA: Kjo është një.

275
00:11:05,604 --> 00:11:06,520
DAVID Malan: Kjo është një.

276
00:11:06,520 --> 00:11:06,710
E drejtë?

277
00:11:06,710 --> 00:11:08,950
Ky është një grup, i cili
do të thotë që ne kemi qasje të rastit.

278
00:11:08,950 --> 00:11:11,790
Dhe në qoftë se ne mendojmë për këtë
zero dhe kjo si 25,

279
00:11:11,790 --> 00:11:13,800
dhe ne e kuptojmë se,
oh, këtu është kontributi im S,

280
00:11:13,800 --> 00:11:16,350
Unë me siguri mund të konvertohet
S, një karakter ASCII,

281
00:11:16,350 --> 00:11:18,540
për një numër korrespondues
mes zero dhe 25

282
00:11:18,540 --> 00:11:20,910
dhe pastaj menjëherë
vënë atë aty ku i takon.

283
00:11:20,910 --> 00:11:26,120
>> Por natyrisht, sa më shpejt që unë të shkoj në
personi i dytë i cili është emri është A ose B ose C

284
00:11:26,120 --> 00:11:29,300
përfundimisht, në qoftë se unë kam përdorur
linear probing si zgjidhje e mia,

285
00:11:29,300 --> 00:11:31,360
koha drejtimin e
futje në rastin më të keq

286
00:11:31,360 --> 00:11:33,120
është në të vërtetë do të zhvilloheshin në çfarë?

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

288
00:11:34,270 --> 00:11:36,045
Dhe unë e kam dëgjuar këtu
saktë herët.

289
00:11:36,045 --> 00:11:36,920
Audienca: [padëgjueshme]

290
00:11:36,920 --> 00:11:41,620
DAVID Malan: Pra, kjo është me të vërtetë n herë
ju keni një grup mjaft të madh të të dhënave.

291
00:11:41,620 --> 00:11:44,410
Pra, nga njëra anë, në qoftë se
array juaj është mjaft e madhe

292
00:11:44,410 --> 00:11:48,287
dhe të dhënat e juaj është mjaft e rrallë, që ju
merrni këtë kohë të bukur të vazhdueshme.

293
00:11:48,287 --> 00:11:50,620
Por, sa më shpejt që ju të filloni
duke marrë elemente gjithnjë e më shumë,

294
00:11:50,620 --> 00:11:53,200
dhe vetëm statistikisht ju merrni
më shumë njerëz me letër

295
00:11:53,200 --> 00:11:56,030
A si emri i tyre ose letra
B, ajo mund të potencialisht

296
00:11:56,030 --> 00:11:57,900
bie në diçka më shumë lineare.

297
00:11:57,900 --> 00:11:59,640
Pra, jo mjaft të përsosur.

298
00:11:59,640 --> 00:12:00,690
Pra, mund të bëjmë më mirë?

299
00:12:00,690 --> 00:12:03,210
>> E pra, çfarë ishte tonë
Zgjidhja më parë, kur ne

300
00:12:03,210 --> 00:12:06,820
duan që të ketë më shumë dinamizëm se
diçka si një grup i lejuar?

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

302
00:12:08,085 --> 00:12:08,960
Audienca: [padëgjueshme]

303
00:12:08,960 --> 00:12:10,030
DAVID Malan: Çfarë kemi prezantuar?

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

305
00:12:10,530 --> 00:12:11,430
Pra, një listë të lidhura.

306
00:12:11,430 --> 00:12:14,430
E pra, le të shohim se çfarë një i lidhur
Lista mund të bëjë për ne vend.

307
00:12:14,430 --> 00:12:17,630
E pra, më lejoni të propozojë që ne
të nxjerrë foto si më poshtë.

308
00:12:17,630 --> 00:12:19,620
Tani kjo është një tjetër
foto nga një shembull

309
00:12:19,620 --> 00:12:24,750
nga një tekst tjetër, në të vërtetë, se
është në të vërtetë duke përdorur një rrjet të madhësisë 31.

310
00:12:24,750 --> 00:12:28,220
Dhe kjo autor thjesht
vendosi të hash strings

311
00:12:28,220 --> 00:12:32,430
nuk është e bazuar në emrat e personit,
por në bazë të datëlindjet e tyre.

312
00:12:32,430 --> 00:12:35,680
Pavarësisht të muajit, ata i realizuar artistikisht
në qoftë se ju jeni të lindur ditën e parë të muajit

313
00:12:35,680 --> 00:12:39,580
ose 31 të një muaji, autori
do të hash bazuar në atë vlerë,

314
00:12:39,580 --> 00:12:44,154
në mënyrë që të përhapet emrat jashtë një grimë
më shumë se vetëm 26 spote mund të lejojë.

315
00:12:44,154 --> 00:12:47,320
Dhe ndoshta kjo është një uniformë pak më shumë
se sa do me shkronja alfabetike,

316
00:12:47,320 --> 00:12:50,236
sepse sigurisht nuk ka siguri
më shumë njerëz në botë me emra

317
00:12:50,236 --> 00:12:54,020
që të fillojë me A se me siguri
disa letra të tjera të alfabetit.

318
00:12:54,020 --> 00:12:56,380
Pra, ndoshta kjo është pak
më e njëtrajtshme, duke supozuar

319
00:12:56,380 --> 00:12:58,640
një shpërndarje uniforme
e foshnjave të gjithë një muaj.

320
00:12:58,640 --> 00:12:59,990
>> Por, sigurisht, kjo është ende e papërsosur.

321
00:12:59,990 --> 00:13:00,370
E drejtë?

322
00:13:00,370 --> 00:13:01,370
Ne jemi të paturit goditjet.

323
00:13:01,370 --> 00:13:04,680
Njerëzit të shumta në këtë
Struktura e të dhënave janë ende

324
00:13:04,680 --> 00:13:08,432
duke pasur të njëjtën ditëlindjen paktën
ju jeni pavarësisht nga muaji.

325
00:13:08,432 --> 00:13:09,640
Por çfarë i ka bërë autori?

326
00:13:09,640 --> 00:13:13,427
E pra, kjo duket sikur ne kemi një rrjet
në anën e majtë tërhequr vertikalisht,

327
00:13:13,427 --> 00:13:15,010
por kjo është vetëm interpretim i një artisti.

328
00:13:15,010 --> 00:13:18,009
Nuk ka rëndësi se çfarë drejtimi të
të nxjerrë një rrjet, është ende një grup.

329
00:13:18,009 --> 00:13:20,225
Çfarë është kjo një grup i duket?

330
00:13:20,225 --> 00:13:21,500
>> AUDIENCA: Lista Linked.

331
00:13:21,500 --> 00:13:21,650
>> DAVID Malan: Po.

332
00:13:21,650 --> 00:13:23,490
Ajo duket si ajo është një
Grup i listës të lidhura.

333
00:13:23,490 --> 00:13:26,490
Pra, përsëri, në këtë pikë të lloj
i përdorimit të këtyre strukturave të të dhënave tani

334
00:13:26,490 --> 00:13:28,550
si përbërësit për më shumë
zgjidhje interesante,

335
00:13:28,550 --> 00:13:30,862
ju mund absolutisht të marrë një
themelore, si një grup,

336
00:13:30,862 --> 00:13:33,320
dhe pastaj të marrë diçka më shumë
interesante si një listë e lidhur

337
00:13:33,320 --> 00:13:36,660
dhe madje edhe të kombinuar ato në një edhe
Struktura më interesante e të dhënave.

338
00:13:36,660 --> 00:13:39,630
Dhe në të vërtetë, kjo shumë do të
të quhet një tabelë hash,

339
00:13:39,630 --> 00:13:42,610
ku array është
me të vërtetë tabela hash,

340
00:13:42,610 --> 00:13:45,600
por kjo tabelë hash ka
zinxhirët, në mënyrë që të flasin,

341
00:13:45,600 --> 00:13:50,220
që mund të rriten, ose tkurret bazuar në
Numri i elementeve që ju doni të futur.

342
00:13:50,220 --> 00:13:52,990
>> Tani, në përputhje me rrethanat, çfarë është
kohë running tani?

343
00:13:52,990 --> 00:13:58,030
Nëse unë dua të futur dikë
ditëlindja e të cilit është October 31,

344
00:13:58,030 --> 00:13:59,040
ku bën ai ose ajo të shkojë?

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

346
00:14:00,530 --> 00:14:01,030
Dakord.

347
00:14:01,030 --> 00:14:02,819
Në fund fare, ku ai thotë se 31.

348
00:14:02,819 --> 00:14:03,610
Dhe kjo është e përsosur.

349
00:14:03,610 --> 00:14:05,060
Kjo ishte koha konstante.

350
00:14:05,060 --> 00:14:08,760
Por, çfarë nëse ne gjejmë dikë tjetër
ditëlindja e të cilit është, le të shohim,

351
00:14:08,760 --> 00:14:10,950
Tetor, nëntor, 31 dhjetor?

352
00:14:10,950 --> 00:14:12,790
Ku është ai ose ajo do të shkojë?

353
00:14:12,790 --> 00:14:13,290
Të njëjtën gjë.

354
00:14:13,290 --> 00:14:13,970
Dy hap pse.

355
00:14:13,970 --> 00:14:15,303
Kjo është konstante edhe pse nuk është ajo?

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

357
00:14:16,360 --> 00:14:16,860
Dakord.

358
00:14:16,860 --> 00:14:17,840
Në këtë moment ajo është.

359
00:14:17,840 --> 00:14:20,570
Por në rastin e përgjithshëm,
më shumë njerëz ne add,

360
00:14:20,570 --> 00:14:23,790
probabilistically, ne jemi duke shkuar
të merrni më shumë dhe më shumë goditjet.

361
00:14:23,790 --> 00:14:26,820
>> Tani kjo është pak
më të mirë, sepse teknikisht

362
00:14:26,820 --> 00:14:34,580
tani zinxhirët e mi mund të jetë në
rastin më të keq se sa kohë?

363
00:14:34,580 --> 00:14:38,890
Nëse unë futur n njerëzit në këtë më
Struktura e të dhënave të sofistikuar, n popull,

364
00:14:38,890 --> 00:14:41,080
në rastin më të keq ajo do të jetë n.

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

366
00:14:41,815 --> 00:14:43,332
>> AUDIENCA: Sepse nëse të gjithë
ka të njëjtën ditëlindje,

367
00:14:43,332 --> 00:14:44,545
ata do të jetë një linjë.

368
00:14:44,545 --> 00:14:45,420
DAVID Malan: Perfect.

369
00:14:45,420 --> 00:14:47,480
Kjo mund të jetë pak e sajuar,
por me të vërtetë në rastin më të keq,

370
00:14:47,480 --> 00:14:50,117
nëse të gjithë kanë të njëjtën ditëlindje,
duke pasur parasysh inputet që ju keni,

371
00:14:50,117 --> 00:14:51,950
ju jeni do të ketë një
zinxhir masivisht të gjatë.

372
00:14:51,950 --> 00:14:54,241
Dhe kështu, ju mund të telefononi atë një
hash tryezë, por me të vërtetë kjo është

373
00:14:54,241 --> 00:14:56,810
vetëm një listë masive lidhur me
një tërësi shumë hapësirë ​​tretur.

374
00:14:56,810 --> 00:15:00,460
Por në përgjithësi, në qoftë se ne supozojmë se
të paktën ditëlindjet janë uniform--

375
00:15:00,460 --> 00:15:01,750
dhe kjo ndoshta nuk është.

376
00:15:01,750 --> 00:15:02,587
Unë jam duke e bërë atë lart.

377
00:15:02,587 --> 00:15:04,420
Por në qoftë se ne supozojmë, për
hir të diskutimit

378
00:15:04,420 --> 00:15:07,717
se ata janë, atëherë teorikisht, nëse
ky është përfaqësimi vertikale

379
00:15:07,717 --> 00:15:11,050
e array, edhe atëherë shpresojmë se ju jeni
do të merrni zinxhirët që janë, ju e dini,

380
00:15:11,050 --> 00:15:15,880
afërsisht të njëjtën gjatësi ku secili prej
këto përfaqëson një ditë të muajit.

381
00:15:15,880 --> 00:15:19,930
>> Tani në qoftë se ka 31 ditë në muaj,
do të thotë se në kohën time running vërtetë

382
00:15:19,930 --> 00:15:25,230
është O e madhe e n mbi 31, e cila
ndihet më mirë se lineare.

383
00:15:25,230 --> 00:15:27,950
Por ajo ishte një nga tonë
Angazhimet e disa javë

384
00:15:27,950 --> 00:15:31,145
më parë, kur ai erdhi për të shprehur
koha drejtimin e një algoritmi?

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

386
00:15:33,450 --> 00:15:35,190
Vetëm vetëm shikoni në afat të lartë të rendit.

387
00:15:35,190 --> 00:15:35,690
E drejtë?

388
00:15:35,690 --> 00:15:37,400
31 është definitivisht e dobishme.

389
00:15:37,400 --> 00:15:39,610
Por kjo është ende O i madh i n.

390
00:15:39,610 --> 00:15:41,730
Por një nga temat
Problemi i vendosur pesë

391
00:15:41,730 --> 00:15:43,950
do të jetë për
pranojmë se absolutisht,

392
00:15:43,950 --> 00:15:47,320
asymptotically, teorikisht
kjo strukturë e të dhënave

393
00:15:47,320 --> 00:15:50,470
është më mirë se vetëm
një listë masive të lidhura.

394
00:15:50,470 --> 00:15:53,550
Dhe me të vërtetë, në rastin më të keq, kjo
tabela hash mund të bie në atë.

395
00:15:53,550 --> 00:15:57,620
>> Por në botën reale, me ne njerëzit
se Macs vet ose PC apo çfarëdo

396
00:15:57,620 --> 00:16:01,240
dhe vrapojnë botën reale
software në të dhënat e botës reale,

397
00:16:01,240 --> 00:16:03,260
të cilat algorithm po ju do të preferoni?

398
00:16:03,260 --> 00:16:09,180
Ai që merr hapa fund ose
ai që merr n ndarë nga 31 hapa

399
00:16:09,180 --> 00:16:12,900
për të gjetur disa pjesë të të dhënave ose
të kërkoni disa informacione?

400
00:16:12,900 --> 00:16:16,580
Unë do të thotë, absolutisht e 31 bën
një ndryshim në botën reale.

401
00:16:16,580 --> 00:16:18,540
Ajo është 31 herë më të shpejtë.

402
00:16:18,540 --> 00:16:20,880
Dhe ne njerëzit janë sigurisht
do të vlerësojmë atë.

403
00:16:20,880 --> 00:16:23,004
>> Pra, të kuptojnë dikotominë
atje në mes të vërtetë

404
00:16:23,004 --> 00:16:25,920
duke folur për gjëra teorike
dhe asymptotically cilat patjetër

405
00:16:25,920 --> 00:16:28,760
ka vlerë si ne kemi parë,
por në botën e vërtetë,

406
00:16:28,760 --> 00:16:32,930
në qoftë se ju intereson vetëm duke e bërë
të lumtur njerëzore për inputet e përgjithshme,

407
00:16:32,930 --> 00:16:36,010
ju mund shumë mirë të duan të pranojnë
fakti se, po, kjo është linear,

408
00:16:36,010 --> 00:16:38,360
por kjo është 31 herë më shpejt
se mund të jetë linear.

409
00:16:38,360 --> 00:16:41,610
Dhe më mirë akoma, ne nuk vetëm duhet të
të bëjë diçka arbitrare si datëlindja,

410
00:16:41,610 --> 00:16:44,030
ne mund të shpenzojnë pak
më shumë kohë dhe zgjuarsia

411
00:16:44,030 --> 00:16:47,140
dhe të mendojnë për atë që ne mund të bëjmë,
dhënë emrin e një personi dhe ndoshta

412
00:16:47,140 --> 00:16:50,130
ditëlindja e tyre për të kombinuar ato
përbërësit për të kuptoj se diçka

413
00:16:50,130 --> 00:16:52,720
kjo është me të vërtetë shumë
uniforme dhe më pak i dhëmbëzuar,

414
00:16:52,720 --> 00:16:56,250
në mënyrë që të flasin se këtë foto
aktualisht sugjeron se mund të jetë.

415
00:16:56,250 --> 00:16:57,750
Si mund të kemi zbatuar këtë në kodin?

416
00:16:57,750 --> 00:17:00,280
E pra, më lejoni të propozojë që ne
vetëm të marrë hua disa sintaksë kemi

417
00:17:00,280 --> 00:17:01,799
përdorur nja dy herë deri tani.

418
00:17:01,799 --> 00:17:03,590
Dhe unë jam duke shkuar për të përcaktuar
një nyje, e cila përsëri

419
00:17:03,590 --> 00:17:06,812
është një term i përgjithshëm për vetëm disa
enë për disa strukturën e të dhënave.

420
00:17:06,812 --> 00:17:09,020
Unë jam duke shkuar për të propozojë që
a string po ndodh në atje.

421
00:17:09,020 --> 00:17:11,369
Por ne jemi duke shkuar për të filluar të marrë
ata trajnimi rrota off tani.

422
00:17:11,369 --> 00:17:13,230
>> Jo më shumë bibliotekë CS50
me të vërtetë, nëse ju dëshironi

423
00:17:13,230 --> 00:17:15,230
ta përdorin atë për finale tuaj
Projekti, i cili është e mirë,

424
00:17:15,230 --> 00:17:18,569
por tani ne jemi duke shkuar për të tërhequr mbrapsht
perde dhe thonë se kjo është vetëm një yll char.

425
00:17:18,569 --> 00:17:22,069
Pra, fjala nuk do të jetë
emrin e personit në fjalë.

426
00:17:22,069 --> 00:17:25,079
Dhe tani kam një lidhje
këtu për nyjen e ardhshëm

427
00:17:25,079 --> 00:17:28,170
në mënyrë që këto paraqesin
secili prej nyjeve

428
00:17:28,170 --> 00:17:30,950
në zinxhirin, potencialisht,
një listë të lidhura.

429
00:17:30,950 --> 00:17:34,090
>> Dhe tani se si mund ta deklaroj
tabela hash vetë?

430
00:17:34,090 --> 00:17:36,660
Si mund ta shpjegojë këtë strukturë të tërë?

431
00:17:36,660 --> 00:17:40,960
E pra, me të vërtetë, ashtu si kam përdorur një akrep
të vetëm të elementit të parë të një liste

432
00:17:40,960 --> 00:17:44,510
para, në mënyrë të ngjashme mund të them vetëm
Unë vetëm nevojë për një bandë e pointers

433
00:17:44,510 --> 00:17:46,270
për të zbatuar këtë tabelë hash tërë.

434
00:17:46,270 --> 00:17:49,484
Unë jam duke shkuar të ketë një rrjet
bëri thirrje tavolinë për tavolinë hash.

435
00:17:49,484 --> 00:17:50,900
Ajo do të jetë e kapacitetit madhësi.

436
00:17:50,900 --> 00:17:52,525
Kjo është sa elemente mund të përshtatet në të.

437
00:17:52,525 --> 00:17:56,180
Dhe secili prej këtyre elementeve në këtë
array do të jetë një yll nyje.

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

439
00:17:56,810 --> 00:18:00,160
E pra, për këtë foto, ajo që unë jam
zbatimin tabelën hash si

440
00:18:00,160 --> 00:18:04,330
efektive në fillim është vetëm
ky grup që ne kemi tërhequr vertikalisht,

441
00:18:04,330 --> 00:18:06,820
secili prej shesheve të cilëve
përfaqëson një tregues.

442
00:18:06,820 --> 00:18:09,170
Se ato që kanë godet
përmes tyre janë vetëm null.

443
00:18:09,170 --> 00:18:11,410
Dhe ato që kanë
shigjeta shkojnë në të djathtë

444
00:18:11,410 --> 00:18:16,140
janë pointers aktuale në nyjet aktuale,
prandaj fillimin e një listë të lidhura.

445
00:18:16,140 --> 00:18:19,050
>> Kështu që këtu, atëherë, është se si ne mund
zbatojnë një tabelë hash që

446
00:18:19,050 --> 00:18:21,580
zbaton chaining të veçantë.

447
00:18:21,580 --> 00:18:22,840
Tani mund të bëjmë më mirë?

448
00:18:22,840 --> 00:18:25,632
Të gjitha të drejtat I premtuar për herë të fundit që
ne mund të arrijmë kohë konstante.

449
00:18:25,632 --> 00:18:27,381
Dhe unë lloj të dhënë
Koha konstante këtu,

450
00:18:27,381 --> 00:18:29,850
por pastaj nuk e ka thënë me të vërtetë
Koha konstante për shkak se ajo është ende e

451
00:18:29,850 --> 00:18:31,890
varur totalit
Numri i elementeve

452
00:18:31,890 --> 00:18:34,500
ju jeni inputting në
Struktura e të dhënave.

453
00:18:34,500 --> 00:18:35,980
Por mendoj ne e bëmë këtë.

454
00:18:35,980 --> 00:18:39,550
Më lejoni të kthehem në ekran gjatë këtu.

455
00:18:39,550 --> 00:18:44,520
Më lejoni gjithashtu projektojnë këtë deri këtu, qartë
ekran, dhe mendoj se kam bërë këtë.

456
00:18:44,520 --> 00:18:49,300
Mendoj unë të kërkuar për të futur emrin
Daven në në strukturën e të dhënave time.

457
00:18:49,300 --> 00:18:52,100
>> Kështu që unë dua për të futur një varg
Daven në strukturën e të dhënave.

458
00:18:52,100 --> 00:18:54,370
Çka nëse unë nuk do të përdorë
hash tryezë, por unë e përdorin

459
00:18:54,370 --> 00:18:56,980
diçka që është më shumë pemë-si
si një pemë familjare, ku

460
00:18:56,980 --> 00:18:59,670
ju keni disa rrënjë në
nyje të lartë dhe pastaj e lë

461
00:18:59,670 --> 00:19:01,440
që shkojnë poshtë dhe jashtë.

462
00:19:01,440 --> 00:19:04,450
Supozoni pastaj, që unë
doni të futur Daven e

463
00:19:04,450 --> 00:19:06,430
në atë që është aktualisht një listë bosh.

464
00:19:06,430 --> 00:19:09,780
Unë jam duke shkuar për të bërë në vijim: Unë jam
do të krijojë një nyje në këtë familje

465
00:19:09,780 --> 00:19:15,170
pemë-si strukturë e të dhënave që duket
a pak si kjo, secila prej të cilave

466
00:19:15,170 --> 00:19:19,640
rectangles ka, le të themi,
për tani 26 elemente në të.

467
00:19:19,640 --> 00:19:21,650
Dhe secili prej qelizave
në këtë grup do

468
00:19:21,650 --> 00:19:23,470
për të përfaqësuar letër e alfabetit.

469
00:19:23,470 --> 00:19:28,190
>> Në mënyrë të veçantë, unë jam duke shkuar për të trajtuar
kjo është A, pastaj B, pastaj C, atëherë D,

470
00:19:28,190 --> 00:19:29,310
kjo këtu.

471
00:19:29,310 --> 00:19:32,940
Pra, kjo do të në mënyrë efektive
përfaqësojnë letër D.

472
00:19:32,940 --> 00:19:36,040
Por për të futur të gjithë Daven së
emrin unë duhet të bëjë pak më shumë.

473
00:19:36,040 --> 00:19:37,840
Kështu që unë jam duke shkuar për të parë hash, kështu që të flasin.

474
00:19:37,840 --> 00:19:41,049
Unë jam duke shkuar për të parë në letrën e parë
në Daven e cila është padyshim një D,

475
00:19:41,049 --> 00:19:42,840
dhe unë jam duke shkuar për të ndarë
një nyje që duket

476
00:19:42,840 --> 00:19:45,570
si this-- një drejtkëndësh të madhe të madhe
të mjaftueshme për të përshtaten të gjithë alfabetin.

477
00:19:45,570 --> 00:19:47,140
>> Tani D është bërë.

478
00:19:47,140 --> 00:19:49,720
Tani A. D-A-V-E-N është qëllimi.

479
00:19:49,720 --> 00:19:51,220
Deri tani ajo që unë jam duke shkuar për të bërë është kjo.

480
00:19:51,220 --> 00:19:54,027
Sapo kam filluar njoftim D
nuk ka asnjë tregues atje.

481
00:19:54,027 --> 00:19:56,860
Kjo është vlera mbeturinave në këtë moment,
ose unë mund të nisja atë të pavlefshëm.

482
00:19:56,860 --> 00:19:59,630
Por më lejoni të mbajë me
kjo ide të ndërtimit të një pemë.

483
00:19:59,630 --> 00:20:04,260
Më lejoni të ndajë një tjetër një nga këto
nyje që ka 26 elemente në të.

484
00:20:04,260 --> 00:20:05,150
>> Dhe ju e dini se çfarë?

485
00:20:05,150 --> 00:20:09,130
Nëse kjo është vetëm një nyje në kujtesë se
I krijuar me malloc, duke përdorur një e strukturës

486
00:20:09,130 --> 00:20:11,240
si ne do të shohim së shpejti,
Unë jam duke shkuar për të bërë this--

487
00:20:11,240 --> 00:20:14,450
Unë jam duke shkuar për të nxjerrë një shigjetë nga
gjë që përfaqësohet D poshtë

488
00:20:14,450 --> 00:20:15,860
në këtë nyje të re.

489
00:20:15,860 --> 00:20:19,240
Dhe tani, së pari e ardhshme
Letra në emër të Daven së,

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V-- Unë jam duke shkuar për të shkuar përpara
dhe të nxjerrë një nyje si kjo,

491
00:20:24,150 --> 00:20:30,150
ku, të V elementet këtu, të cilat
ne do të tërheqë për Uh instance--.

492
00:20:30,150 --> 00:20:31,020
Ne nuk do të tërheqë atje.

493
00:20:31,020 --> 00:20:31,936
Ajo do të shkoni këtu.

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

495
00:20:32,890 --> 00:20:35,712
>> Pastaj ne jemi duke shkuar për
konsiderojnë këtë të jetë V.

496
00:20:35,712 --> 00:20:44,920
Dhe pastaj këtu poshtë ne jemi duke shkuar për të indeksit
poshtë nga V në atë që ne do të konsiderojmë E.

497
00:20:44,920 --> 00:20:50,100
Dhe pastaj nga këtu ne jemi duke shkuar për
shkoni të ketë një nga këto nyje këtu.

498
00:20:50,100 --> 00:20:52,930
Dhe tani ne kemi një pyetje për t'iu përgjigjur.

499
00:20:52,930 --> 00:20:57,840
Unë kam nevojë për një farë mënyre tregojnë se
ne jemi në fund të vargut Daven.

500
00:20:57,840 --> 00:20:59,490
Kështu që unë vetëm mund të lënë atë null.

501
00:20:59,490 --> 00:21:02,670
>> Por, çfarë nëse kemi Daven e
emri i plotë gjithashtu, e cila

502
00:21:02,670 --> 00:21:04,280
është, siç kemi thënë, Davenport?

503
00:21:04,280 --> 00:21:06,970
Pra, çfarë nëse Daven është
në fakt një substring,

504
00:21:06,970 --> 00:21:08,960
një prefiks i një varg më të gjatë?

505
00:21:08,960 --> 00:21:11,450
Ne nuk mund vetëm të përhershme
thonë se asgjë nuk është duke shkuar

506
00:21:11,450 --> 00:21:14,410
për të shkuar atje, sepse ne mund të
kurrë të futur një fjalë si Davenport

507
00:21:14,410 --> 00:21:15,840
në këtë Struktura e të dhënave

508
00:21:15,840 --> 00:21:19,560
>> Pra, ajo që ne mund të bëjmë në vend është
trajtojnë secili prej këtyre elementëve

509
00:21:19,560 --> 00:21:22,170
si ndoshta duke pasur dy
elemente brenda prej tyre.

510
00:21:22,170 --> 00:21:24,810
Njëra është një akrep, me të vërtetë,
si unë kam qenë duke bërë.

511
00:21:24,810 --> 00:21:27,100
Pra, secili prej këtyre kutive
nuk është vetëm një qelizë.

512
00:21:27,100 --> 00:21:29,855
Por çfarë nëse top
one-- një fund të

513
00:21:29,855 --> 00:21:32,230
do të jetë e pavlefshme, sepse
nuk ka Davenport vetëm ende.

514
00:21:32,230 --> 00:21:34,197
Çfarë ndodh nëse një krye
është një vlerë të veçantë?

515
00:21:34,197 --> 00:21:36,530
Dhe kjo do të jetë pak
e vështirë për të nxjerrë të kësaj madhësie.

516
00:21:36,530 --> 00:21:38,130
Por mendoj se është vetëm një shenjë kontrolloni.

517
00:21:38,130 --> 00:21:38,920
Kontrolloni.

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-N është një varg
Në këtë strukturë të dhënave.

519
00:21:44,230 --> 00:21:48,350
>> Ndërkohë, në qoftë se kam pasur më shumë hapësirë
këtu, unë mund të bëjë P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
dhe unë mund të vënë kontroll në nyjen
që ka letrën T në fund.

521
00:21:52,650 --> 00:21:55,460
Pra, kjo është një masivisht
kompleks-looking strukturën e të dhënave.

522
00:21:55,460 --> 00:21:57,210
Dhe dorëshkrimit im
me siguri nuk do të të ndihmojë.

523
00:21:57,210 --> 00:22:00,043
Por në qoftë se unë të kërkuar për të futur diçka
tjetër, e konsiderojnë atë që ne do të bëjmë.

524
00:22:00,043 --> 00:22:03,370
Nëse ne të kërkuar për të vënë Davidin,
ne do të ndjekin të njëjtën logjikë, D-A-V,

525
00:22:03,370 --> 00:22:08,802
por tani unë do të veçoja në tjetër
element jo nga E, por nga I tek D.

526
00:22:08,802 --> 00:22:10,760
Pra, nuk do të jetë
më shumë nyje në këtë pemë.

527
00:22:10,760 --> 00:22:12,325
Ne do të kemi thirrjes malloc më shumë.

528
00:22:12,325 --> 00:22:14,700
Por unë nuk dua të bëjë një
rrëmujë të plotë të kësaj tabloje.

529
00:22:14,700 --> 00:22:17,710
Pra, le të shohim në një vend
që është para-formuluara

530
00:22:17,710 --> 00:22:21,810
si ky me nuk dot, dot,
pika, por vargjeve vetëm shkurtuar.

531
00:22:21,810 --> 00:22:23,950
Por secili prej nyjeve
në këtë pemë këtu

532
00:22:23,950 --> 00:22:26,700
paraqet të njëjtën thing--
një grup Ray e madhësisë 26.

533
00:22:26,700 --> 00:22:28,860
>> Ose në qoftë se ne duam që të jenë të
me të vërtetë e duhur tani, çfarë

534
00:22:28,860 --> 00:22:30,790
nëse emri i dikujt si
një apostrof, le të

535
00:22:30,790 --> 00:22:35,560
supozojmë se çdo nyje të vërtetë ka
si 27 indekseve në të, jo vetëm 26.

536
00:22:35,560 --> 00:22:42,020
Pra, kjo është tani do të jetë një e të dhënave
Struktura e quajti një trie-- T-R-I-E.

537
00:22:42,020 --> 00:22:46,120
A trie, e cila është kinse
historikisht një emër i zgjuar për një pemë

538
00:22:46,120 --> 00:22:49,040
që është e optimizuar për
rikthim, e cila natyrisht,

539
00:22:49,040 --> 00:22:50,870
është shkruar me një I-E kështu që është trie.

540
00:22:50,870 --> 00:22:52,710
Por kjo është historia e trie.

541
00:22:52,710 --> 00:22:55,860
>> Pra, a është kjo trie të dhëna pemë-si
Struktura si një pemë familjare

542
00:22:55,860 --> 00:22:57,510
që në fund të fundit sillet si kjo.

543
00:22:57,510 --> 00:23:00,890
Dhe këtu është vetëm një shembull i një
tërë bandë e emrave të njerëzve të tjerë.

544
00:23:00,890 --> 00:23:03,540
Por pyetja tani
në dorë është ajo që kemi

545
00:23:03,540 --> 00:23:08,070
kemi fituar duke futur ndoshta një më
strukturë të komplikuar e të dhënave, dhe një,

546
00:23:08,070 --> 00:23:09,870
sinqerisht, që përdor një shumë të kujtesës.

547
00:23:09,870 --> 00:23:11,703
>> Sepse edhe pse,
në këtë moment, unë jam vetëm

548
00:23:11,703 --> 00:23:15,050
përdorur D's tregues dhe
Një dhe V dhe Es dhe Ns,

549
00:23:15,050 --> 00:23:16,700
Unë jam humbur një dreq e shumë të kujtesës.

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

551
00:23:18,030 --> 00:23:22,660
Por ku kam shpenzuar një burim,
Unë synoj që të mund të fitojë përsëri një tjetër.

552
00:23:22,660 --> 00:23:26,020
Pra, në qoftë se unë jam duke shpenzuar më shumë hapësirë,
çfarë është ndoshta shpresa?

553
00:23:26,020 --> 00:23:27,407
Se unë jam shpenzojnë më pak çfarë?

554
00:23:27,407 --> 00:23:28,240
AUDIENCA: pak kohë.

555
00:23:28,240 --> 00:23:28,990
DAVID Malan: Koha.

556
00:23:28,990 --> 00:23:30,320
Tani pse mund që të jetë?

557
00:23:30,320 --> 00:23:33,880
E pra, ajo që është shtënie
kohë, në aspektin e O i madh tani,

558
00:23:33,880 --> 00:23:37,660
një emër si Daven
ose Davenport apo David?

559
00:23:37,660 --> 00:23:39,340
Well, Daven ishte pesë hapa.

560
00:23:39,340 --> 00:23:42,350
Davenport do të jetë nëntë hapa,
kështu që do të jetë një pak më shumë hapa.

561
00:23:42,350 --> 00:23:44,250
David do të jetë pesë hapa si.

562
00:23:44,250 --> 00:23:47,230
Pra, ato janë konkrete
numrat, por me siguri ka

563
00:23:47,230 --> 00:23:49,550
një kufi i sipërm për
Gjatësia e emrit të dikujt.

564
00:23:49,550 --> 00:23:52,240
Dhe me të vërtetë, në problemin
grupe të pesë specifikim,

565
00:23:52,240 --> 00:23:54,050
ne jemi duke shkuar për të propozuar
se kjo është diçka e

566
00:23:54,050 --> 00:23:55,470
kjo është karaktere 40-disa-rastësishëm.

567
00:23:55,470 --> 00:23:58,180
>> Realisht, askush nuk e ka
një emër pafundësisht të gjatë,

568
00:23:58,180 --> 00:24:01,542
që do të thotë se gjatësia e një
emrin ose gjatësia e një varg, ne mund

569
00:24:01,542 --> 00:24:03,750
kanë të sigurt shteti i
Struktura është ndoshta çfarë?

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

571
00:24:05,550 --> 00:24:06,250
Kjo është konstante.

572
00:24:06,250 --> 00:24:06,430
E drejtë?

573
00:24:06,430 --> 00:24:09,310
Ajo mund të jetë një konstante e madhe si
40-diçka, por ajo është konstante.

574
00:24:09,310 --> 00:24:13,752
Dhe kjo nuk ka varësi nga sa
Emrat e tjerë janë në këtë strukturë të dhënave.

575
00:24:13,752 --> 00:24:15,460
Me fjalë të tjera, në qoftë se unë
kërkuar për të futur tani

576
00:24:15,460 --> 00:24:20,540
Colton ose Gabriel ose Rob a Zamyla ose
Alison ose Belinda ose ndonjë emra të tjerë

577
00:24:20,540 --> 00:24:23,940
nga stafi në këto të dhëna
struktura, është koha running

578
00:24:23,940 --> 00:24:26,750
i futur emra të tjerë
do të jetë në të gjitha ndikuar

579
00:24:26,750 --> 00:24:30,220
nga sa shumë elemente të tjera janë
në strukturën dhënave tashmë?

580
00:24:30,220 --> 00:24:31,040
Kjo nuk është.

581
00:24:31,040 --> 00:24:31,540
E drejtë?

582
00:24:31,540 --> 00:24:36,150
Sepse ne jemi duke përdorur në mënyrë efektive
kjo multi-layer tabelë hash.

583
00:24:36,150 --> 00:24:38,280
Dhe koha drejtimin e
ndonjë prej këtyre operacioneve

584
00:24:38,280 --> 00:24:41,510
është jo i varur nga numri i
elemente që janë në strukturën dhënave

585
00:24:41,510 --> 00:24:43,090
ose që eventualisht do
të jetë në strukturën dhënave,

586
00:24:43,090 --> 00:24:44,714
por në gjatësinë e atë mënyrë specifike?

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

588
00:24:46,500 --> 00:24:49,200
>> String qenit
futur, e cila ka të bëjë

589
00:24:49,200 --> 00:24:52,580
kjo asymptotically konstante
time-- O e madhe e një.

590
00:24:52,580 --> 00:24:54,720
Dhe sinqerisht, vetëm në
bota reale, kjo

591
00:24:54,720 --> 00:24:58,380
thotë futur emrin Daven merr
si pesë hapa, apo Davenport nëntë

592
00:24:58,380 --> 00:25:00,100
hapa, apo David pesë hapa.

593
00:25:00,100 --> 00:25:03,071
Kjo është goxha i mallkuar herë vogla running.

594
00:25:03,071 --> 00:25:05,320
Dhe, me të vërtetë, kjo është një shumë
gjë e mirë, sidomos kur

595
00:25:05,320 --> 00:25:08,126
kjo nuk është e varur nga gjithsej
Numri i elementeve ne atje.

596
00:25:08,126 --> 00:25:10,500
Pra, si mund të zbatojmë këtë
lloj strukture në kodin?

597
00:25:10,500 --> 00:25:12,900
Kjo është pak më shumë
komplekse, por ende është e

598
00:25:12,900 --> 00:25:15,050
vetëm një aplikim i
blloqe themelore të ndërtimit.

599
00:25:15,050 --> 00:25:17,830
Unë jam duke shkuar për të ripërcaktuar
ne nyje si më poshtë:

600
00:25:17,830 --> 00:25:21,100
bool quajti word-- dhe kjo
mund të quhet asgjë.

601
00:25:21,100 --> 00:25:23,970
Por bool përfaqëson
ajo që unë tërhoqi si një shenjë kontrolloni.

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

603
00:25:24,490 --> 00:25:26,720
Ky është fundi i një varg
Në këtë strukturë të dhënave.

604
00:25:26,720 --> 00:25:30,702
>> Dhe, sigurisht, ylli nyjen
nuk i referohet fëmijëve.

605
00:25:30,702 --> 00:25:32,410
Dhe, me të vërtetë, ashtu si
një pemë familjare, ju

606
00:25:32,410 --> 00:25:34,370
do të marrë në konsideratë nyje
që janë të varur off

607
00:25:34,370 --> 00:25:36,920
e poshtme të ndonjë prind
element të jenë fëmijë.

608
00:25:36,920 --> 00:25:40,510
Dhe kështu fëmijët do të
të jetë një grup i 27, një 27

609
00:25:40,510 --> 00:25:41,680
vetëm duke e apostrof.

610
00:25:41,680 --> 00:25:43,390
Ne jemi duke shkuar për të zgjidhur
e rastit të veçantë asaj.

611
00:25:43,390 --> 00:25:45,400
Kështu që ju mund të keni të sigurtë
Emrat me apostrofat.

612
00:25:45,400 --> 00:25:47,399
Ndoshta edhe vizë ndarëse duhet
të shkojnë në atje, por ju do të

613
00:25:47,399 --> 00:25:50,330
shihni në p grup 5 ne vetëm të kujdesit
në lidhje me letrat dhe apostrofat.

614
00:25:50,330 --> 00:25:52,990
>> Dhe pastaj si bëni ju përfaqësoni
Struktura e të dhënave në vetvete?

615
00:25:52,990 --> 00:25:56,454
Si mund të përfaqësojnë rrënjë
i këtij trie, kështu që të flasin?

616
00:25:56,454 --> 00:25:59,620
E pra, ashtu si me një listë të lidhura, ju
duhet një tregues për elementin e parë.

617
00:25:59,620 --> 00:26:04,270
Me një trie ju vetëm nevojë për një
treguesin në rrënjë të këtij trie.

618
00:26:04,270 --> 00:26:07,290
Dhe nga atje ju mund të hash
rrugën tuaj poshtë thellë e më thellë

619
00:26:07,290 --> 00:26:10,460
për çdo nyje tjetër në strukturën.

620
00:26:10,460 --> 00:26:13,440
Pra, thjesht me kjo mund të
ne përfaqësojmë atë e strukturës.

621
00:26:13,440 --> 00:26:15,877
>> Tani Meanwhile-- Oh, pyetje.

622
00:26:15,877 --> 00:26:17,220
>> AUDIENCA: Çfarë është fjala bool?

623
00:26:17,220 --> 00:26:20,490
>> DAVID Malan: Fjala bool është
vetëm këtë mishërim C

624
00:26:20,490 --> 00:26:22,920
e asaj që e përshkroi
në këtë kuti këtu, kur

625
00:26:22,920 --> 00:26:26,000
I filluar ndarjen secili prej
Elementet Array it ndahen në dy pjesë.

626
00:26:26,000 --> 00:26:27,600
Njëra është një tregues për nyjen e ardhshëm.

627
00:26:27,600 --> 00:26:30,280
Tjetër duhet të jetë
diçka si një kuti kontrolloni

628
00:26:30,280 --> 00:26:33,770
të themi po, ka një
Fjala Daven që përfundon këtu,

629
00:26:33,770 --> 00:26:35,610
sepse ne nuk duam,
në këtë moment, Dave.

630
00:26:35,610 --> 00:26:39,320
>> Edhe pse Dave do të jetë një
Fjala legjitim, ai nuk është në trie

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

632
00:26:39,830 --> 00:26:40,950
Dhe D nuk është një fjalë.

633
00:26:40,950 --> 00:26:42,770
Dhe D-A nuk është një fjalë ose një emër.

634
00:26:42,770 --> 00:26:45,020
Pra, në shenjë kontrolloni
tregon vetëm një herë ju

635
00:26:45,020 --> 00:26:48,190
hit kjo nyjë është
rruga e mëparshme e karaktereve

636
00:26:48,190 --> 00:26:50,700
në fakt një varg që e keni futur.

637
00:26:50,700 --> 00:26:53,660
Pra, kjo është e gjitha bool
nuk është duke bërë për ne.

638
00:26:53,660 --> 00:26:55,500
>> Çdo pyetje të tjera mbi përpiqet?

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

640
00:26:56,215 --> 00:26:58,035
>> AUDIENCA: Çfarë është mbivendosje?

641
00:26:58,035 --> 00:26:59,945
Çfarë ndodh nëse ju keni një Dave dhe Daven?

642
00:26:59,945 --> 00:27:00,820
DAVID Malan: Perfect.

643
00:27:00,820 --> 00:27:02,580
Çfarë ndodh nëse ju keni një Dave dhe Daven?

644
00:27:02,580 --> 00:27:06,240
Pra, nëse ne të futur, thonë se një pseudonim,
për David-- Dave-- D-A-V-E?

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

646
00:27:07,370 --> 00:27:08,700
Kjo është në të vërtetë super e thjeshtë.

647
00:27:08,700 --> 00:27:10,325
Pra, ne jemi vetëm duke shkuar për të marrë katër hapa.

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

649
00:27:11,042 --> 00:27:15,847
D-A-V-E. Dhe çfarë kam për të
të bëjë një herë unë goditi atë nyje të katërt?

650
00:27:15,847 --> 00:27:16,680
Vetëm duke shkuar për të kontrolluar.

651
00:27:16,680 --> 00:27:18,000
Ne jemi tashmë të mirë për të shkuar.

652
00:27:18,000 --> 00:27:18,840
Bërë.

653
00:27:18,840 --> 00:27:19,750
Katër hapa.

654
00:27:19,750 --> 00:27:21,590
Koha Constant asymptotically.

655
00:27:21,590 --> 00:27:26,300
Dhe tani ne kemi treguar se si Dave
dhe Daven janë vargjet në strukturën.

656
00:27:26,300 --> 00:27:27,710
Pra, nuk është një problem.

657
00:27:27,710 --> 00:27:30,200
Dhe vini re se si praninë
e Daven nuk e bëjnë atë

658
00:27:30,200 --> 00:27:34,750
marrë ndonjë më shumë kohë ose më pak
koha për Dave dhe anasjelltas.

659
00:27:34,750 --> 00:27:36,000
>> Pra, çfarë tjetër mund të bëjmë tani?

660
00:27:36,000 --> 00:27:40,680
Ne kemi përdorur këtë metaforë më parë
e tabaka përfaqësojnë diçka.

661
00:27:40,680 --> 00:27:43,380
Por kjo rezulton se një
rafte e tabaka është në të vërtetë

662
00:27:43,380 --> 00:27:47,187
demonstrative të një të dhënave abstrakte
type-- një strukturë e të dhënave të nivelit të lartë

663
00:27:47,187 --> 00:27:49,770
se në fund dita është vetëm
si një grup apo një listë e lidhur

664
00:27:49,770 --> 00:27:50,970
ose diçka më shumë i zakonshëm.

665
00:27:50,970 --> 00:27:53,270
Por kjo është një më interesante
Koncepti konceptual.

666
00:27:53,270 --> 00:27:56,440
Një turrë, si këto
tabaka këtu në Mather,

667
00:27:56,440 --> 00:27:58,750
janë quajtur përgjithësisht
vetëm that-- një pirg.

668
00:27:58,750 --> 00:28:02,540
>> Dhe në këtë lloj të strukturës së të dhënave
ju keni dy operations--

669
00:28:02,540 --> 00:28:05,880
ju keni një të quajtur shtytje për
duke shtuar diçka për të rafte,

670
00:28:05,880 --> 00:28:08,320
vënë si një tabaka
Kthehu në krye të rafte.

671
00:28:08,320 --> 00:28:11,350
Dhe pastaj pop, që do të thotë ju
marrë tabaka off larti.

672
00:28:11,350 --> 00:28:16,210
Por, ajo që është shumë e rëndësishme në lidhje me një pirg është se
ajo e mori këtë karakteristikë kurioz.

673
00:28:16,210 --> 00:28:19,560
Si stafit sallë ngrënie janë
rikomponimin e tabaka për vakt tjetër,

674
00:28:19,560 --> 00:28:21,380
çfarë do të jetë
e vërtetë në lidhje me mënyrën se si studentët

675
00:28:21,380 --> 00:28:22,856
ndërveprojnë me këtë strukturë të dhënat?

676
00:28:22,856 --> 00:28:24,480
AUDIENCA: Ata do të pop një off.

677
00:28:24,480 --> 00:28:26,550
DAVID Malan: Ata janë duke shkuar për të
pop një off, me shpresë të lartë.

678
00:28:26,550 --> 00:28:28,910
Përndryshe kjo është vetëm lloj i trashë
për të shkuar gjatë gjithë rrugës për në fund.

679
00:28:28,910 --> 00:28:29,070
E drejtë?

680
00:28:29,070 --> 00:28:31,620
Struktura e të dhënave të vërtetë nuk lejon
ju për të rrëmbyer tabaka fund paku

681
00:28:31,620 --> 00:28:32,520
të lehtë.

682
00:28:32,520 --> 00:28:35,040
Pra, nuk është kjo kurioz
pronës në një pirg

683
00:28:35,040 --> 00:28:39,730
se pika e fundit në është
do të jetë i pari ai jashtë.

684
00:28:39,730 --> 00:28:43,400
Dhe shkencëtarët kompjuter telefononi
kjo LIFO-- fundit në, e parë jashtë.

685
00:28:43,400 --> 00:28:45,540
Dhe ai në fakt ka
aplikacione interesante.

686
00:28:45,540 --> 00:28:50,090
Kjo nuk është domosdoshmërisht aq e qartë si disa
të tjerët, por ajo mund të, me të vërtetë, të jetë e dobishme,

687
00:28:50,090 --> 00:28:54,040
dhe kjo mund të, me të vërtetë, do të zbatohen
në disa mënyra të ndryshme.

688
00:28:54,040 --> 00:28:58,550
>> Pra një, dhe në fakt, le të
mua mos të zhyten në atë.

689
00:28:58,550 --> 00:28:59,860
Le ta bëjmë këtë vend.

690
00:28:59,860 --> 00:29:03,700
Le të shikojmë në atë që është pothuajse e
të njëjtën ide, por kjo është një më të drejtë të vogël.

691
00:29:03,700 --> 00:29:04,200
E drejtë?

692
00:29:04,200 --> 00:29:07,560
Nëse ju jeni një nga këta djem tifoz, ose
Vajzat që me të vërtetë i pëlqen produktet Apple

693
00:29:07,560 --> 00:29:10,130
dhe ju u zgjua në 3:00
të vijë deri në një dyqan

694
00:29:10,130 --> 00:29:14,150
për të marrë iPhone më të fundit, ju
mund të ketë queued lart si kjo.

695
00:29:14,150 --> 00:29:15,800
>> Tani një radhë është quajtur me shumë kujdes.

696
00:29:15,800 --> 00:29:18,190
Kjo është një linjë, sepse nuk ka
disa korrektësisë me të.

697
00:29:18,190 --> 00:29:18,690
E drejtë?

698
00:29:18,690 --> 00:29:21,690
Ajo do lloj thithur në qoftë se ju keni
mori aty për herë të parë në Apple Store

699
00:29:21,690 --> 00:29:25,700
por ju jeni në mënyrë efektive më i fundit
tabaka sepse punonjësit Apple pastaj

700
00:29:25,700 --> 00:29:28,189
pop personin e fundit që
në të vërtetë mori në linjë.

701
00:29:28,189 --> 00:29:31,230
Pra, oxhaqet dhe radhët e gjata, madje edhe pse
funksionalisht ata janë lloj i same--

702
00:29:31,230 --> 00:29:33,105
kjo është vetëm për këtë koleksion
e burimeve që është

703
00:29:33,105 --> 00:29:36,210
do të rritet dhe shrink-- atje ka
ky aspekt drejtësia me të,

704
00:29:36,210 --> 00:29:39,634
të paktën në botën e vërtetë,
ku operacionet ju ushtroni

705
00:29:39,634 --> 00:29:40,800
janë krejtësisht të ndryshme.

706
00:29:40,800 --> 00:29:43,360
Një stack-- një radhë
rather-- është e thënë të ketë

707
00:29:43,360 --> 00:29:45,320
dy operacione: n radhë dhe d radhë.

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

709
00:29:46,341 --> 00:29:48,090
Ose ju mund të telefononi ata
çdo numër të gjërave.

710
00:29:48,090 --> 00:29:50,770
Por ju vetëm doni të kapni
nocioni se ai është duke shtuar

711
00:29:50,770 --> 00:29:53,230
dhe një është në fund të fundit i zbritur.

712
00:29:53,230 --> 00:29:58,840
>> Tani nën kapuç, si rafte
dhe një radhë të mund të zbatohet si?

713
00:29:58,840 --> 00:30:01,390
Ne nuk do të shkojë në kodin e
kjo për shkak të nivelit të lartë

714
00:30:01,390 --> 00:30:03,387
Ideja është lloj më i dukshëm.

715
00:30:03,387 --> 00:30:04,470
Unë do të thotë, çfarë bëjnë njerëzit?

716
00:30:04,470 --> 00:30:07,030
Në qoftë se unë jam personi i parë në Apple
Dyqan dhe kjo është derë e parë,

717
00:30:07,030 --> 00:30:08,130
ju e dini, unë jam duke shkuar për të dalë këtu.

718
00:30:08,130 --> 00:30:09,750
Dhe personi tjetër të
do të qëndrojë këtu.

719
00:30:09,750 --> 00:30:11,500
Dhe personi tjetër të
do të qëndrojë këtu.

720
00:30:11,500 --> 00:30:13,792
Pra, çfarë strukturë e të dhënave
jep vetë në një radhë?

721
00:30:13,792 --> 00:30:14,542
>> AUDIENCA: A radhë.

722
00:30:14,542 --> 00:30:15,667
DAVID Malan: Pra, a radhë.

723
00:30:15,667 --> 00:30:16,390
Të sigurt.

724
00:30:16,390 --> 00:30:16,920
Çfarë tjetër?

725
00:30:16,920 --> 00:30:17,600
>> AUDIENCA: Një listë të lidhura.

726
00:30:17,600 --> 00:30:18,990
>> DAVID Malan: Një lidhje
lista që ju mund të zbatojë.

727
00:30:18,990 --> 00:30:22,500
Dhe një listë e lidhur është e bukur, sepse atëherë
ajo mund të rritet në mënyrë arbitrare të gjatë në krahasim

728
00:30:22,500 --> 00:30:24,880
për të pasur një numër të caktuar
e njerëzve në dyqan.

729
00:30:24,880 --> 00:30:27,030
Por ndoshta një numër të caktuar
e vendeve është e ligjshme.

730
00:30:27,030 --> 00:30:30,350
Sepse në qoftë se ata vetëm kanë si 20
iPhones në ditën e parë, ndoshta

731
00:30:30,350 --> 00:30:33,930
ata kanë nevojë vetëm për një grup të madhësisë
20 për të përfaqësuar atë radhë, e cila

732
00:30:33,930 --> 00:30:37,070
vetëm të them tani sapo kemi filluar duke folur
në lidhje me këto probleme të nivelit të lartë,

733
00:30:37,070 --> 00:30:38,890
ju mund të zbatojë atë
në çdo numër të mënyra.

734
00:30:38,890 --> 00:30:42,030
Dhe nuk ka ndoshta vetëm do të
të jetë një tregti off në hapësirë ​​dhe kohë

735
00:30:42,030 --> 00:30:43,950
ose vetëm në vetë kompleksitetin tuaj kodit.

736
00:30:43,950 --> 00:30:45,380
>> Po në lidhje me një pirg?

737
00:30:45,380 --> 00:30:48,190
E pra, një pirg, ne kemi parë shumë
mund të jetë vetëm këto tabaka.

738
00:30:48,190 --> 00:30:50,007
Dhe ju mund të zbatojë këtë një grup.

739
00:30:50,007 --> 00:30:53,090
Por në një moment në qoftë se ju përdorni një rrjet,
se çfarë do të ndodhë me tabaka

740
00:30:53,090 --> 00:30:54,173
jeni duke u përpjekur për të vënë poshtë?

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

742
00:30:55,170 --> 00:30:55,670
Dakord.

743
00:30:55,670 --> 00:30:57,490
Ju jeni vetëm do të
të jenë në gjendje për të shkuar deri të lartë.

744
00:30:57,490 --> 00:31:00,156
Dhe unë mendoj se në Mather ata janë
fakt recessed në këtë hapje.

745
00:31:00,156 --> 00:31:01,950
Pra me të vërtetë, kjo është pothuajse e
si Mather është duke përdorur

746
00:31:01,950 --> 00:31:03,783
një grup të madhësisë fikse,
sepse ju vetëm mund të

747
00:31:03,783 --> 00:31:08,302
përshtatet kaq shumë tabaka në atë hapje në
muri poshtë nën gjunjë njerëzve.

748
00:31:08,302 --> 00:31:10,010
Dhe kështu që mund të jetë
e thënë të jetë një grup,

749
00:31:10,010 --> 00:31:14,300
por ne me siguri mund të zbatojë atë
më përgjithësisht me një listë të lidhura.

750
00:31:14,300 --> 00:31:16,390
>> E pra, çka në lidhje me një tjetër strukturën e të dhënave?

751
00:31:16,390 --> 00:31:18,760
Më lejoni të tërheqë një tjetër vizuale këtu.

752
00:31:18,760 --> 00:31:24,710
Diçka si si në lidhje me këtë këtu?

753
00:31:24,710 --> 00:31:28,920
Pse mund të jetë e dobishme që të mos ketë
diçka si dashuroj si një trie, e cila

754
00:31:28,920 --> 00:31:32,370
pamë pasur këto nyje shumë të gjerë,
secili i cili është në një grup?

755
00:31:32,370 --> 00:31:35,740
Por, çfarë nëse ne bëjmë diçka më shumë
thjesht, si një pemë e vjetër familjare shkollë,

756
00:31:35,740 --> 00:31:38,110
secili nga nyjet këtu cilit
është vetëm ruajtjen e një numri.

757
00:31:38,110 --> 00:31:42,180
Në vend të një emri apo një pasardhës
është vetëm ruajtjen e një numër të tillë.

758
00:31:42,180 --> 00:31:45,250
>> Well, zhargon ne përdorim në
Strukturat e të dhënave është edhe mundohet

759
00:31:45,250 --> 00:31:49,510
dhe pemë, ku një trie, përsëri, është e
vetëm një nyje e të cilit janë të vargjeve,

760
00:31:49,510 --> 00:31:51,680
është ende ajo që ju mund të
përdorim nga klasën e shkollës

761
00:31:51,680 --> 00:31:53,860
kur keni bërë një familje
lë tree-- dhe rrënja

762
00:31:53,860 --> 00:31:57,250
nga pema dhe fëmijët e
prind dhe vëllezërit e motrat e tyre.

763
00:31:57,250 --> 00:32:03,670
Dhe ne mund të zbatojë një pemë,
për shembull, si thjesht si kjo.

764
00:32:03,670 --> 00:32:07,420
Një pemë, në qoftë se ajo si një nyje, një prej
këto qarqe që ka një numër,

765
00:32:07,420 --> 00:32:09,947
ajo nuk do të ketë
një akrep, por dy.

766
00:32:09,947 --> 00:32:11,780
Dhe, sa më shpejt që ju të shtoni
një tregues të dytë, ju

767
00:32:11,780 --> 00:32:13,905
mund të vërtetë të bëjë tani lloj
të të dhënave të dy-dimensionale

768
00:32:13,905 --> 00:32:14,780
Strukturat në kujtesën.

769
00:32:14,780 --> 00:32:16,660
Ashtu si një dy-dimensionale
array, ju mund të

770
00:32:16,660 --> 00:32:18,904
kemi lloj i dy-dimensionale
Listat e lidhura, por ato

771
00:32:18,904 --> 00:32:20,820
që ndjekin një model
ku nuk ka asnjë cikle.

772
00:32:20,820 --> 00:32:24,487
Kjo është me të vërtetë një pemë me një
Mënyra gjysh deri këtu dhe pastaj

773
00:32:24,487 --> 00:32:27,320
disa prindër dhe fëmijët e
nipërit dhe stërnipërit e stërmbesat.

774
00:32:27,320 --> 00:32:28,370
dhe kështu me radhë.

775
00:32:28,370 --> 00:32:32,390
>> Por ajo që është me të vërtetë i zoti për këtë shumë,
vetëm për të vë në lojë ju me një pak të kodit,

776
00:32:32,390 --> 00:32:35,370
recursion risjell nga
një copë herë prapa, ku

777
00:32:35,370 --> 00:32:38,220
ju shkruani një funksion që e quan veten.

778
00:32:38,220 --> 00:32:41,140
Kjo është një mundësi e bukur
të zbatojnë diçka

779
00:32:41,140 --> 00:32:42,920
si recursion, sepse e konsiderojnë këtë.

780
00:32:42,920 --> 00:32:43,860
>> Kjo është një pemë.

781
00:32:43,860 --> 00:32:48,040
Dhe unë kam qenë një anal pak me mënyrën se si
I vënë integers në rrugë.

782
00:32:48,040 --> 00:32:51,020
Pra, shumë në mënyrë që ajo ka një të veçantë
name-- një pemë kërkimi binar.

783
00:32:51,020 --> 00:32:53,460
Tani ne kemi dëgjuar binar
kërkoni, por ju mund të

784
00:32:53,460 --> 00:32:55,180
punojnë prapa nga emri kjo gjë është?

785
00:32:55,180 --> 00:32:59,280
Cili është modeli se si unë
futur integers në këtë pemë?

786
00:32:59,280 --> 00:33:00,696
Kjo nuk është arbitrare.

787
00:33:00,696 --> 00:33:01,570
Ka disa model.

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

789
00:33:02,090 --> 00:33:03,370
>> AUDIENCA: ato më të vogla në të majtë.

790
00:33:03,370 --> 00:33:03,690
>> DAVID Malan: Po.

791
00:33:03,690 --> 00:33:05,062
Ato më të vogla janë në të majtë.

792
00:33:05,062 --> 00:33:06,270
Ato janë më të mëdha në të djathtë.

793
00:33:06,270 --> 00:33:12,940
Tillë që një deklaratë e vërtetë është një
prind është më i madh se fëmijën e saj të majtë,

794
00:33:12,940 --> 00:33:14,850
por më pak se fëmijën e saj të drejtë.

795
00:33:14,850 --> 00:33:17,750
Dhe kjo është vetëm edhe një
përkufizim gjithkund rekursive verbal

796
00:33:17,750 --> 00:33:20,500
sepse ju mund të aplikoni atë
të njëjtën logjikë për çdo nyje

797
00:33:20,500 --> 00:33:23,080
dhe ai vetëm fundeve
out, një rast bazë, nëse ju

798
00:33:23,080 --> 00:33:25,740
do, kur ju goditi një
gjethet, në mënyrë që të flasin,

799
00:33:25,740 --> 00:33:28,580
ku një pushimi nuk ka fëmijë më tej.

800
00:33:28,580 --> 00:33:30,614
>> Tani si mund ju të gjeni numrin 44?

801
00:33:30,614 --> 00:33:32,280
Ju do të fillojë në rrënjë dhe të thonë, HM.

802
00:33:32,280 --> 00:33:35,690
55 nuk është 44 Prandaj nuk dua të shkoj
drejtë ose nuk dua të shkojnë majtas?

803
00:33:35,690 --> 00:33:37,190
Well, natyrisht që ju dëshironi të shkoni majtas.

804
00:33:37,190 --> 00:33:40,060
Dhe kështu kjo është vetëm si telefon
shembull libër në kërkim binar

805
00:33:40,060 --> 00:33:41,099
në përgjithësi.

806
00:33:41,099 --> 00:33:43,390
Por ne jemi në zbatim të tij
tani pak më dinamike

807
00:33:43,390 --> 00:33:45,339
se një grup mund të lejojë.

808
00:33:45,339 --> 00:33:48,130
Dhe në fakt, në qoftë se ju doni të shikoni
në kodin, në shikim të parë i sigurt.

809
00:33:48,130 --> 00:33:49,671
Ajo duket si një bandë e tërë e linjave.

810
00:33:49,671 --> 00:33:51,220
Por kjo është bukur e thjeshtë.

811
00:33:51,220 --> 00:33:54,490
Nëse ju doni të zbatojë një funksion
quajtur search qëllimi i të cilit në jetë

812
00:33:54,490 --> 00:33:57,290
është për të kërkuar për një vlerë
si n, një numër i plotë,

813
00:33:57,290 --> 00:34:01,756
dhe ju jeni duke kaluar në një një pointer--
një tregues për nyjen e rrënjëve,

814
00:34:01,756 --> 00:34:04,380
në vend, e atë pemë prej të cilave
ju mund të hyni në çdo gjë tjetër,

815
00:34:04,380 --> 00:34:08,850
njoftim sa drejpërdrejtë
ju mund të zbatojë logjikën.

816
00:34:08,850 --> 00:34:10,880
Nëse pema është i pavlefshëm,
natyrisht kjo nuk është atje.

817
00:34:10,880 --> 00:34:11,880
Le të kthehen vetëm false.

818
00:34:11,880 --> 00:34:12,000
E drejtë?

819
00:34:12,000 --> 00:34:14,040
Nëse ju dorë atë asgjë,
nuk ka asgjë atje.

820
00:34:14,040 --> 00:34:17,900
>> Tjetër, nëse n është më pak se
pemë shigjetë n-- tani shigjetë n,

821
00:34:17,900 --> 00:34:20,670
kujtojnë ne kemi prezantuar super
shkurtimisht ditë të tjera,

822
00:34:20,670 --> 00:34:25,100
dhe kjo vetëm do të thotë de-referencë e
tregues dhe të kërkoni në fushën e quajtur n.

823
00:34:25,100 --> 00:34:27,690
Pra, kjo do të thotë të shkojnë atje dhe të
shikoni në fushën e quajtur n.

824
00:34:27,690 --> 00:34:33,810
Pra, nëse n, vlera ju jeni duke i dhënë, është më pak i
se vlera e pemëve numër i plotë,

825
00:34:33,810 --> 00:34:35,449
ku ju doni të shkoni?

826
00:34:35,449 --> 00:34:36,389
Në të majtë.

827
00:34:36,389 --> 00:34:37,780
>> Pra njoftim recursion.

828
00:34:37,780 --> 00:34:39,860
Unë jam returning-- nuk është e vërtetë.

829
00:34:39,860 --> 00:34:40,989
Jo false.

830
00:34:40,989 --> 00:34:45,670
Unë jam kthyer çfarëdo përgjigje
është nga një thirrje për veten time, duke kaluar

831
00:34:45,670 --> 00:34:50,100
n një herë, i cili është i tepërt,
por ajo është pak më ndryshe tani?

832
00:34:50,100 --> 00:34:51,989
Sa jam unë duke e bërë problem më të vogël?

833
00:34:51,989 --> 00:34:54,920
Unë jam duke kaluar në, si të dytë
Argumenti, nuk rrënja e pemës,

834
00:34:54,920 --> 00:34:59,616
por fëmija majtë në këtë rast.

835
00:34:59,616 --> 00:35:00,990
Kështu që unë jam duke kaluar në fëmijën e majtë.

836
00:35:00,990 --> 00:35:04,720
>> Ndërkohë, nëse n është më e madhe se
nyja Unë jam duke kërkuar në,

837
00:35:04,720 --> 00:35:06,690
I kërko anën e djathtë.

838
00:35:06,690 --> 00:35:10,880
Tjetër, në qoftë se pema nuk është i pavlefshëm, dhe
nëse element nuk është në të majtë

839
00:35:10,880 --> 00:35:13,240
dhe kjo nuk është në të djathtë,
çfarë është mrekullisht rasti?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
Ne kemi gjetur në të vërtetë nyjen në
pyetje, dhe kështu që ne kthehemi vërtetë.

842
00:35:18,440 --> 00:35:21,490
>> Pra, ne kemi gërvishtem vetëm sipërfaqen
tani disa prej këtyre strukturave të dhënave.

843
00:35:21,490 --> 00:35:24,370
Në Problemi vendosur pesë ju do të
eksplorojë këto akoma më tej,

844
00:35:24,370 --> 00:35:27,250
dhe ju do të jepet dizajnit tuaj
zgjedhje se si të shkojë në lidhje me këtë.

845
00:35:27,250 --> 00:35:30,250
Ajo që unë do të doja të përfundojë në
është vetëm një ngacmues 30 dytë

846
00:35:30,250 --> 00:35:32,080
e asaj që pret javën e ardhshme dhe më gjerë.

847
00:35:32,080 --> 00:35:35,390
>> Si ne begin-- fatmirësisht ju mund të
think-- tranzicionit tonë ngadalë

848
00:35:35,390 --> 00:35:38,680
nga bota e C dhe më të ulët
Detajet e implementimit të nivelit,

849
00:35:38,680 --> 00:35:42,090
në një botë në të cilën ne mund të marrë për të
dhënë se dikush tjetër e ka më në fund

850
00:35:42,090 --> 00:35:44,010
zbatohen këto të dhëna
Strukturat për ne,

851
00:35:44,010 --> 00:35:47,570
dhe ne do të fillojmë të kuptojmë
bota reale do të thotë të zbatimit

852
00:35:47,570 --> 00:35:50,560
Programet web-bazuar dhe
faqet e internetit më të përgjithshme

853
00:35:50,560 --> 00:35:52,910
dhe gjithashtu shumë i sigurisë
Implikimet që ne kemi vetëm

854
00:35:52,910 --> 00:35:54,850
filluar për të zeroja sipërfaqe e.

855
00:35:54,850 --> 00:35:57,320
Këtu është ajo që na pret
në ditët që do të vijnë.

856
00:35:57,320 --> 00:36:00,480
>> [VIDEO Playback]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -Ai Erdhi me një mesazh,
me një protokoll delet e tij.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
Ai erdhi në një botë të egër
firewalls, routers pa ndjenja,

861
00:36:30,894 --> 00:36:33,368
dhe rreziqe shumë më keq se vdekja.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
Ai është i shpejtë.

864
00:36:36,236 --> 00:36:37,980
Ai është i fortë.

865
00:36:37,980 --> 00:36:42,830
Ai është TCP / IP, dhe ai mori adresën tuaj.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"Warriors e Net".

868
00:36:48,074 --> 00:36:49,660
[END VIDEO rishikim]

869
00:36:49,660 --> 00:36:50,910
DAVID Malan: Së javën e ardhshme.

870
00:36:50,910 --> 00:36:51,880
Ne do të shohim ju pastaj.

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[VIDEO Playback]

873
00:36:56,060 --> 00:36:59,240
-Dhe Tani, "Mendime të thella"
nga Daven Farnham.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-David Gjithmonë fillon
ligjërata me "gjithë të drejtë."

876
00:37:05,820 --> 00:37:08,750
Pse jo, "Ja zgjidhja
të problemit të vendosur e kësaj jave "

877
00:37:08,750 --> 00:37:12,180
apo "Ne jemi duke i dhënë të gjithë ju një A?"

878
00:37:12,180 --> 00:37:13,380
[Qesh]

879
00:37:13,380 --> 00:37:15,530
[END VIDEO rishikim]