1
00:00:00,000 --> 00:00:03,423
>> [Muusika mängib]

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

3
00:00:05,380 --> 00:00:08,210
>> ANDI PENG: Tere tulemast nädal 6 punkti.

4
00:00:08,210 --> 00:00:11,620
Me kõrvale kaldunud meie standard
paragrahvi Teisipäeval

5
00:00:11,620 --> 00:00:14,130
Pärastlõunal see armas pühapäeva hommikul.

6
00:00:14,130 --> 00:00:17,330
Aitäh kõigile, et
koos minuga täna, kuid tõsiselt,

7
00:00:17,330 --> 00:00:18,170
aplausi.

8
00:00:18,170 --> 00:00:20,600
>> See on päris suur pingutus.

9
00:00:20,600 --> 00:00:23,600
Ma peaaegu isegi ei oleks
üles ajas, aga see oli OK.

10
00:00:23,600 --> 00:00:27,520
Nii et ma tean, et te kõik
just tegin seda viktoriini.

11
00:00:27,520 --> 00:00:30,370
Esiteks, tere tulemast
Tagakülg selle.

12
00:00:30,370 --> 00:00:32,917
>> Teiseks, me räägime sellest.

13
00:00:32,917 --> 00:00:34,000
Me räägime viktoriin.

14
00:00:34,000 --> 00:00:35,700
Me räägime, kuidas
sa teed klassis.

15
00:00:35,700 --> 00:00:36,550
Sa saad trahvi.

16
00:00:36,550 --> 00:00:39,080
Mul on oma viktoriinid
sa lõpuks siin,

17
00:00:39,080 --> 00:00:42,120
nii et kui te poisid tahavad võtta
pilk see, täiesti korras.

18
00:00:42,120 --> 00:00:46,590
>> Nii kiiresti, enne kui hakkame, siis
päevakorda täna on järgmine.

19
00:00:46,590 --> 00:00:48,430
Nagu näete, oleme
põhimõtteliselt kiire süütamise

20
00:00:48,430 --> 00:00:52,120
läbi terve hunnik andmestruktuurid
tõesti, tõesti, tõesti kiiresti.

21
00:00:52,120 --> 00:00:54,380
Nii sellisena, siis ei ole
super interaktiivne täna.

22
00:00:54,380 --> 00:00:59,620
Seda saad lihtsalt mind mingi karjumine
asju, mida ja kui ma teid segadusse ajada,

23
00:00:59,620 --> 00:01:02,680
kui ma lähen liiga kiiresti, andke mulle teada.

24
00:01:02,680 --> 00:01:05,200
Nad on lihtsalt erinevad andmed
struktuure ning osana

25
00:01:05,200 --> 00:01:07,070
oma pset selle
järgmiseks nädalaks, siis saad

26
00:01:07,070 --> 00:01:10,340
palutakse rakendada üks neist,
võibolla kaks them-- kaks neist

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

28
00:01:12,319 --> 00:01:14,610
OK, nii et ma olen lihtsalt kavatse
alustada mõned teated.

29
00:01:14,610 --> 00:01:19,070
Me läheme üle korstnad ja järjekorrad rohkem
sügavus üle, mida me tegime enne viktoriini.

30
00:01:19,070 --> 00:01:20,990
Me läheme üle seotud
list jälle taas

31
00:01:20,990 --> 00:01:23,899
põhjalikum kui see, mida
meil oli enne viktoriini.

32
00:01:23,899 --> 00:01:26,440
Ja siis me räägime hash
tabelid, puud ja üritab, mis

33
00:01:26,440 --> 00:01:28,890
kõik päris vajalik oma pset.

34
00:01:28,890 --> 00:01:32,925
Ja siis me läheme üle mõned
kasulikke nõuandeid pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, nii viktoriini 0.

36
00:01:37,360 --> 00:01:41,090
Keskmine oli 58%.

37
00:01:41,090 --> 00:01:45,370
See oli väga madal ja nii kutid kõik
tegi väga hästi kooskõlas

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

39
00:01:46,510 --> 00:01:49,970
>> Päris palju, rusikareegel on, kui sa oled
lähemal standardhälbega keskmine

40
00:01:49,970 --> 00:01:52,990
eriti kuna me oleme vähem
Mugav osa, sa oled täiesti korras.

41
00:01:52,990 --> 00:01:54,120
Sa oled õigel teel.

42
00:01:54,120 --> 00:01:55,190
Elu on hea.

43
00:01:55,190 --> 00:01:58,952
>> Ma tean, et see on hirmutav mõelda, et
Ma sain nagu 40% selle viktoriini.

44
00:01:58,952 --> 00:02:00,160
Ma ei suuda seda klassi.

45
00:02:00,160 --> 00:02:02,243
Ma luban teile, te ei ole
läheb suuda klassis.

46
00:02:02,243 --> 00:02:03,680
Sa oled täiesti korras.

47
00:02:03,680 --> 00:02:06,850
>> Neile teist, kes sai üle
keskmine, muljetavaldav, muljetavaldav,

48
00:02:06,850 --> 00:02:08,780
nagu tõsiselt hästi tehtud.

49
00:02:08,780 --> 00:02:09,689
Mul on neid minuga.

50
00:02:09,689 --> 00:02:11,730
Julgelt tulevad jõuda
lõpus osa.

51
00:02:11,730 --> 00:02:14,520
Anna mulle teada, kui teil on mõni
küsimused, küsimused koos nendega.

52
00:02:14,520 --> 00:02:17,204
Kui lisame oma skoor
vale, andke teada.

53
00:02:17,204 --> 00:02:21,240
>> OK, nii pset5, see on tõesti
imelik nädal Yale'i selles mõttes,

54
00:02:21,240 --> 00:02:24,240
et meie pset on tingitud
Kolmapäeva keskpäeval sealhulgas

55
00:02:24,240 --> 00:02:27,317
lõpus päev, nii et see on tegelikult
teoreetiliselt tõttu teisipäeval kell keskpäeval.

56
00:02:27,317 --> 00:02:29,150
Ilmselt keegi valmis
Teisipäevasel keskpäeval.

57
00:02:29,150 --> 00:02:30,830
See on täiesti korras.

58
00:02:30,830 --> 00:02:33,700
Me läheme on tööaega
täna samuti esmaspäeva õhtul.

59
00:02:33,700 --> 00:02:36,810
Ja kõik osad sel nädalal
tegelikult muutunud töötoad,

60
00:02:36,810 --> 00:02:38,800
nii et võid vabalt pop
ükskõik mida soovite,

61
00:02:38,800 --> 00:02:42,810
ja nad on omamoodi mini-pset
töötoad abi, et.

62
00:02:42,810 --> 00:02:45,620
Nii sellisena, et see on ainus lõik
kus me õppematerjale.

63
00:02:45,620 --> 00:02:49,220
Kõik teised lõigud on keskendunud
ainult abiks pset.

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

65
00:02:50,146 --> 00:02:52,000
>> Sihtrühm: Kus tööaega?

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG: Lahtiolekuajad
tonight-- oh, hea küsimus.

67
00:02:56,120 --> 00:03:00,580
Ma arvan, et lahtiolekuaeg täna
on Teal või Commons.

68
00:03:00,580 --> 00:03:02,984
Kui teil vaadata online CS50
ja te lähete tööaega,

69
00:03:02,984 --> 00:03:05,650
tuleks ajakava, mis
ütleb teile, kus kõik on.

70
00:03:05,650 --> 00:03:07,954
>> Ma tean, kas täna
või homme on sinakasroheline,

71
00:03:07,954 --> 00:03:10,120
ja ma arvan, et meil võib olla
common ööl.

72
00:03:10,120 --> 00:03:11,020
Ma ei ole kindel.

73
00:03:11,020 --> 00:03:11,700
Hea küsimus.

74
00:03:11,700 --> 00:03:14,430
Kontrollida CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, küsimusi
ajakava järgmiseks nagu kolm päeva?

76
00:03:18,780 --> 00:03:21,690
Ma luban teile, poisid nagu David
ütles, et see on mäe.

77
00:03:21,690 --> 00:03:23,050
Te olete peaaegu kohal.

78
00:03:23,050 --> 00:03:24,644
Lihtsalt veel kolm päeva.

79
00:03:24,644 --> 00:03:26,310
Sinna, ja siis me kõik langenud.

80
00:03:26,310 --> 00:03:28,114
Me peame kena CS-intervalli.

81
00:03:28,114 --> 00:03:28,780
Me tuleme tagasi.

82
00:03:28,780 --> 00:03:30,779
Me sukelduda web
programmeerimine ja arendamine,

83
00:03:30,779 --> 00:03:35,150
asju, mis on väga lõbus võrreldes
mõnedele teistele psets.

84
00:03:35,150 --> 00:03:37,974
Ja see saab olema chill ja
me on palju nalja.

85
00:03:37,974 --> 00:03:38,890
Me peame rohkem kommi.

86
00:03:38,890 --> 00:03:39,730
Vabandame kommi.

87
00:03:39,730 --> 00:03:40,945
Ma unustasin kommi.

88
00:03:40,945 --> 00:03:43,310
See oli karm hommikul.

89
00:03:43,310 --> 00:03:46,340
Nii kutid on peaaegu olemas,
ja ma olen tõesti uhke teie kutid.

90
00:03:46,340 --> 00:03:49,570
>> OK, nii korstnad.

91
00:03:49,570 --> 00:03:53,331
Kes armastas küsimus Jack
ja tema riided viktoriini?

92
00:03:53,331 --> 00:03:53,830
Mitte keegi?

93
00:03:53,830 --> 00:03:56,500
OK, see on hea.

94
00:03:56,500 --> 00:04:00,200
>> Nii et sisuliselt kui võimalik
Pildi Jack, see kutt siin,

95
00:04:00,200 --> 00:04:03,350
armastab võtta riided
välja riidale,

96
00:04:03,350 --> 00:04:05,750
ja ta paneb selle tagasi peale
virna pärast ta on teinud.

97
00:04:05,750 --> 00:04:07,600
Nii et sel viisil, et ta kunagi
Tundub, et saada

98
00:04:07,600 --> 00:04:10,090
to põhja
Kestab oma riided.

99
00:04:10,090 --> 00:04:12,600
Nii sedalaadi kirjeldab
lähteandmete struktuur

100
00:04:12,600 --> 00:04:16,610
kuidas virna rakendatakse.

101
00:04:16,610 --> 00:04:20,060
>> Sisuliselt mõelda
Kestab nagu virnas objektid

102
00:04:20,060 --> 00:04:24,900
kui paned asjad peale top, ja
siis sa pop neid ülevalt.

103
00:04:24,900 --> 00:04:28,600
Nii LIFO on lühend meile meeldib
to use-- Last In, First Out.

104
00:04:28,600 --> 00:04:32,480
Ja nii kesta kuni tippu
stack on esimene, mis väljub.

105
00:04:32,480 --> 00:04:34,260
Ja nii need kaks sõna
meile meeldib siduda

106
00:04:34,260 --> 00:04:36,190
selle kutsutakse push ja pop.

107
00:04:36,190 --> 00:04:39,790
Kui vajutada midagi peale
Kestab ja sa pop seda uuesti üles.

108
00:04:39,790 --> 00:04:43,422
>> Ja nii ma arvan, et see on omamoodi
abstraktne mõiste neile,

109
00:04:43,422 --> 00:04:45,630
kes tahavad näha nagu
tegeliku rakendamise

110
00:04:45,630 --> 00:04:46,740
reaalses maailmas.

111
00:04:46,740 --> 00:04:50,170
Kui paljud teist on kirjutatud essee
äkki nagu tund enne seda oli tingitud

112
00:04:50,170 --> 00:04:54,510
ja sa kogemata kustutatud suur
patakas see, nagu kogemata?

113
00:04:54,510 --> 00:04:58,560
Ja mis siis kontrolli teha
Me kasutame seda ellu tagasi?

114
00:04:58,560 --> 00:05:00,030
Kontroll-Z, jah?

115
00:05:00,030 --> 00:05:03,640
Kontroll-Z, nii kogus korda
et kontroll-Z on päästnud mu elu,

116
00:05:03,640 --> 00:05:08,820
on salvestatud my ass, iga kord
mis on ellu virna.

117
00:05:08,820 --> 00:05:13,020
>> Sisuliselt kogu teave
see on teie Wordi dokument,

118
00:05:13,020 --> 00:05:15,080
see saab tõugata ja hüppasid tahtmist.

119
00:05:15,080 --> 00:05:19,460
Ja nii sisuliselt kui sa
kustutada midagi, kui pop see tagasi üles.

120
00:05:19,460 --> 00:05:22,820
Ja siis, kui seda vajate tagasi, siis
lükake see, mis on see, mida Kontroll-C teeb.

121
00:05:22,820 --> 00:05:26,770
Ja nii reaalses maailmas funktsiooni
kuidas lihtsate andmete struktuur

122
00:05:26,770 --> 00:05:28,690
aitab oma igapäevaelus.

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

124
00:05:31,710 --> 00:05:40,150
>> Nii struct on nii, et
me tegelikult luua pinu.

125
00:05:40,150 --> 00:05:44,720
Me kirjutada määratleda struct ja seejärel
Me nimetame seda korstna allosas.

126
00:05:44,720 --> 00:05:47,440
Ja jooksul korstnat,
meil on kaks parameetrit

127
00:05:47,440 --> 00:05:51,580
et me saame sisuliselt manipuleerida,
nii et meil on char star stringid võimsust.

128
00:05:51,580 --> 00:05:55,150
>> Kõik, mis ta teeb
loob massiivi

129
00:05:55,150 --> 00:05:58,835
et meil saab salvestada mida iganes sa tahad
mida me saame kindlaks oma suutlikkust.

130
00:05:58,835 --> 00:06:01,990
Võimsus on ainult max summa
kirjed saame panna selle massiivi.

131
00:06:01,990 --> 00:06:05,660
int suurus on counter, mis hoiab
lugu sellest, kuidas paljud teemad on praegu

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

133
00:06:07,850 --> 00:06:11,860
Siis saame jälgida, A,
nii, kui suur tegelik stack on,

134
00:06:11,860 --> 00:06:14,850
ja B, kui palju, et korstnat
me täitsime, sest me ei taha

135
00:06:14,850 --> 00:06:18,800
koguneda üle, mida meie võime on.

136
00:06:18,800 --> 00:06:24,340
>> Nii näiteks see armas
Küsimus oli oma viktoriini.

137
00:06:24,340 --> 00:06:28,160
Sisuliselt kuidas me push
külge üles virna.

138
00:06:28,160 --> 00:06:28,830
Päris lihtne.

139
00:06:28,830 --> 00:06:30,621
Kui te vaatate seda,
me käime läbi selle.

140
00:06:30,621 --> 00:06:32,640
Kui [kuuldamatu] size--
mäletan, kui te

141
00:06:32,640 --> 00:06:35,300
tahad pääseda mistahes
parameeter jooksul struct,

142
00:06:35,300 --> 00:06:40,320
sa nime struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> Sellisel juhul s on
nimi meie stack.

144
00:06:42,720 --> 00:06:46,230
Me tahame, et pääseda suurus
see, et me teeme s.size.

145
00:06:46,230 --> 00:06:50,280
Nii kaua kui suurus ei ole
võrdub võimsusega või nii kaua,

146
00:06:50,280 --> 00:06:52,940
kui see on väiksem kui võimsust,
kas teeks siin.

147
00:06:52,940 --> 00:06:57,180
>> Sa tahad, et pääseda sees
oma korstnat, nii s.strings,

148
00:06:57,180 --> 00:07:00,790
ja sa lähed panna, et uus number
mis sa tahad lisada sinna.

149
00:07:00,790 --> 00:07:05,030
Ütleme nii, et me tahame
lisada int n peale virna,

150
00:07:05,030 --> 00:07:08,905
me võiks teha s.strings,
sulgudes s.size võrdne n.

151
00:07:08,905 --> 00:07:11,030
Kuna suurus on koht, kus me
Praegu on pakis

152
00:07:11,030 --> 00:07:14,590
Kui me läheme suruda
see, et me lihtsalt juurde

153
00:07:14,590 --> 00:07:17,370
sõltumata suurusest, seda
Praeguse täius virna,

154
00:07:17,370 --> 00:07:21,729
ja me push int n peale seda.

155
00:07:21,729 --> 00:07:24,770
Ja siis me tahame veenduda, et
me ka incrementing suurus n,

156
00:07:24,770 --> 00:07:27,436
nii saame jälgida me oleme
lisada ekstra asi virna.

157
00:07:27,436 --> 00:07:29,660
Nüüd on meil suurem suurus.

158
00:07:29,660 --> 00:07:33,196
Kas see siin mõtet
kõik, kuidas loogiliselt see toimib?

159
00:07:33,196 --> 00:07:34,160
See oli selline kiire.

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

161
00:07:39,535 --> 00:07:42,160
Sihtrühm: Kas te lähete üle
s.stringss.strings [s.size] jälle?

162
00:07:42,160 --> 00:07:45,808
ANDI PENG: Muidugi, mis siis teeb
s.size praegu meile?

163
00:07:45,808 --> 00:07:47,440
Sihtrühm: See on praeguse suuruse.

164
00:07:47,440 --> 00:07:50,890
ANDI PENG: Täpselt, nii et
indeks, mis meie suurus on,

165
00:07:50,890 --> 00:07:57,780
ja nii me tahame panna uue täisarv
et me tahame lisada s.size.

166
00:07:57,780 --> 00:07:58,760
Kas see on mõtet?

167
00:07:58,760 --> 00:08:01,110
Kuna s.strings, kõik, mis
on on nimi massiivi.

168
00:08:01,110 --> 00:08:03,510
Kõik see on on pääseda
massiivi meie struct,

169
00:08:03,510 --> 00:08:06,030
ja nii kui me tahame
paigutada n sellesse indeks,

170
00:08:06,030 --> 00:08:09,651
saame lihtsalt kasutada seda
kasutades sulgudes s.size.

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

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

173
00:08:13,580 --> 00:08:18,916
>> Olgu, pop, ma pseudokoodi it out
kutid, kuid sarnane kontseptsioon.

174
00:08:18,916 --> 00:08:19,790
Kas see on mõtet?

175
00:08:19,790 --> 00:08:22,310
Kui suurus on suurem
kui null, siis

176
00:08:22,310 --> 00:08:25,350
tean, et sa tahad teha midagi
välja, sest kui suurus ei ole

177
00:08:25,350 --> 00:08:27,620
suurem kui null, siis
pole midagi pakis.

178
00:08:27,620 --> 00:08:29,840
>> Nii tahad ainult käivitada
Selle koodiga see võib ainult

179
00:08:29,840 --> 00:08:32,320
pop, kui midagi on pop.

180
00:08:32,320 --> 00:08:35,830
Nii et kui suurus on suurem
kui 0, me miinus suurusest.

181
00:08:35,830 --> 00:08:40,020
Me kahandab suurus ja siis tagasi
kõik, mis on sees, sest

182
00:08:40,020 --> 00:08:42,710
popping, me tahame
juurdepääsu iganes on salvestatud

183
00:08:42,710 --> 00:08:45,694
indeks on riidale.

184
00:08:45,694 --> 00:08:46,610
Kõik mõtet?

185
00:08:46,610 --> 00:08:49,693
Kui ma tegin teiega kirjutada see välja,
te poisid oleks võimalik kirjutada välja?

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

187
00:08:52,029 --> 00:08:53,570
OK, kutid saavad mängida seda.

188
00:08:53,570 --> 00:08:55,252
Ära muretse, kui sa ei saa aru.

189
00:08:55,252 --> 00:08:57,460
Meil ei ole aega, et koodi
seda täna, sest me oleme

190
00:08:57,460 --> 00:08:59,959
sain palju need struktuurid
läbida, kuid sisuliselt

191
00:08:59,959 --> 00:09:02,214
pseudokoodi, väga, väga sarnane suruda.

192
00:09:02,214 --> 00:09:03,380
Jälgi mööda loogika.

193
00:09:03,380 --> 00:09:06,092
Veenduge, et olete juurdepääsusoovide kõiki
Teie struct õigesti.

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

195
00:09:06,574 --> 00:09:09,282
>> Sihtrühm: Kas need slaidid ja
kogu see asi olla täna-ish?

196
00:09:09,282 --> 00:09:11,586
ANDI PENG: Alati, eks.

197
00:09:11,586 --> 00:09:13,710
Ma lähen, et proovida panna
see üles nagu tund pärast.

198
00:09:13,710 --> 00:09:16,626
Ma posti David, David püüab
pane see üles nagu tund pärast seda.

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

200
00:09:20,040 --> 00:09:25,470
>> OK, nii et siis Astume seda teiste
armas andmete struktuuri nimetatakse järjekorda.

201
00:09:25,470 --> 00:09:30,140
Nagu te poisid näen siin, et
järjekorda, Briti meie hulgas

202
00:09:30,140 --> 00:09:32,010
kõik see on on line.

203
00:09:32,010 --> 00:09:34,680
Nii et vastupidi
te arvate virna on,

204
00:09:34,680 --> 00:09:37,750
järjekorras on täpselt see, mida
loogiliselt see on teie arvates.

205
00:09:37,750 --> 00:09:41,914
Mess toimub reeglite järgi FIFO,
mis on First In, First Out.

206
00:09:41,914 --> 00:09:43,705
Kui oled esimest
üks rida, sa oled

207
00:09:43,705 --> 00:09:46,230
esimene, mis
väljub liin.

208
00:09:46,230 --> 00:09:49,680
>> Mida me tahame nimetame seda
on dequeueing ja enqueueing.

209
00:09:49,680 --> 00:09:52,380
Kui me tahame midagi lisada
meie järjekorda, me Lisa järjekorda.

210
00:09:52,380 --> 00:09:55,690
Kui me tahame dequeue või võtta
midagi ära, me dequeue.

211
00:09:55,690 --> 00:10:03,350
>> Nii sama tunne, et me oleme omamoodi
luua kindla suurusega elemente, mida me

212
00:10:03,350 --> 00:10:06,500
saab salvestada teatud
asju, aga saame ka

213
00:10:06,500 --> 00:10:10,100
muuta, kui me pannes
parameetrite sees neist

214
00:10:10,100 --> 00:10:13,140
põhineb millist
funktsionaalsus, mida me tahame.

215
00:10:13,140 --> 00:10:16,700
Nii korstnad, tahtsime viimase
üks, N olla esimene välja.

216
00:10:16,700 --> 00:10:19,800
Järjekord on tahame esimene asi
aastal olla esimene asi välja.

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

218
00:10:22,510 --> 00:10:26,710
>> Nii struct-tüüpi
määratleda, nagu näete,

219
00:10:26,710 --> 00:10:29,470
see on natuke erinev
sellest, mida pakis oli

220
00:10:29,470 --> 00:10:33,120
sest mitte ainult meil hoida
peal, kus suurust praegu on,

221
00:10:33,120 --> 00:10:37,420
tahame ka jälgida juht
samuti, kus me praegu oleme.

222
00:10:37,420 --> 00:10:39,580
Nii et ma arvan, et see on lihtsam
kui ma juhtida selle üles.

223
00:10:39,580 --> 00:10:53,270
Nii saab kujutada meil järjekorras,
Ütleme, et juht on siinsamas.

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

225
00:10:55,811 --> 00:10:58,310
Pea line, olgem
lihtsalt öelda, et on praegu olemas,

226
00:10:58,310 --> 00:11:01,809
ja me tahame lisada
midagi järjekorda.

227
00:11:01,809 --> 00:11:04,350
Ma kutsun suurus sisuliselt
on sama asi nagu saba,

228
00:11:04,350 --> 00:11:06,314
lõpuks kõikjal oma järjekord.

229
00:11:06,314 --> 00:11:07,730
Ütleme nii, et suurus on siinsamas.

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

231
00:11:14,380 --> 00:11:18,400
>> Niisiis, kuidas üks feasibly
lisada midagi ümber järjekorda?

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

233
00:11:21,000 --> 00:11:24,130
Mis indeks me tahame panna
kus me tahame lisada.

234
00:11:24,130 --> 00:11:29,320
Kui see on alguses oma
järjekorda ja see on lõpuks see

235
00:11:29,320 --> 00:11:31,860
või suurusest see, kus me
tahan lisada järgmise objekti?

236
00:11:31,860 --> 00:11:32,920
>> Sihtrühm: [kuuldamatu]

237
00:11:32,920 --> 00:11:35,920
ANDI PENG: Täpselt, mida soovite lisada
see sõltub olete kirjutanud.

238
00:11:35,920 --> 00:11:37,840
Kas see on tühi või mis on tühi.

239
00:11:37,840 --> 00:11:42,630
Nii et sa tahad lisada see ilmselt
siin, sest kui suurus on--

240
00:11:42,630 --> 00:11:50,540
kui need kõik on täis, sa tahad
lisada see siin, eks?

241
00:11:50,540 --> 00:11:57,150
>> Ja nii see on, kuigi väga
Lihtne, mitte päris alati õige

242
00:11:57,150 --> 00:12:00,690
sest peamine erinevus
vahel järjekorras ja korstna

243
00:12:00,690 --> 00:12:04,350
on see, et järjekorda ei
tegelikult manipuleerida

244
00:12:04,350 --> 00:12:06,980
nii et pea muudatusi
sõltuvalt sellest, kus sa tahad

245
00:12:06,980 --> 00:12:08,650
alguses oma kii alustada.

246
00:12:08,650 --> 00:12:11,900
Ja selle tulemusena oma saba
Samuti muutub.

247
00:12:11,900 --> 00:12:14,770
Ja nii, kui heita pilk
See kood praegu.

248
00:12:14,770 --> 00:12:18,620
Nagu te poisid paluti ka
kirjuta läbi viktoriini, Lisa järjekorda.

249
00:12:18,620 --> 00:12:22,580
Võib-olla me räägime läbi, miks
vastus oli, mis see oli.

250
00:12:22,580 --> 00:12:26,790
>> Ma ei saanud päris sobi see joon ühe,
kuid sisuliselt see tükk koodi

251
00:12:26,790 --> 00:12:29,030
peaks olema üks rida.

252
00:12:29,030 --> 00:12:30,140
Kuluta nagu 30 sekundi jooksul.

253
00:12:30,140 --> 00:12:33,000
Heitke pilk, ja miks
see on nii, et see on.

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

255
00:12:50,030 --> 00:12:55,420
>> Väga, väga sarnane struct, väga, väga
sarnase struktuuriga kui eelmine

256
00:12:55,420 --> 00:12:58,090
Kestab välja arvatud ehk
üks rida koodi.

257
00:12:58,090 --> 00:13:01,190
Ja et üks rida koodi
määrab funktsionaalsus.

258
00:13:01,190 --> 00:13:03,900
Ja see on tõesti eristavad
järjekorras korstnatest.

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

260
00:13:18,510 --> 00:13:22,010
>> Igaüks taha võtke torkehaav
oli selgitada, miks olete

261
00:13:22,010 --> 00:13:24,980
sain selle keerulise asi siin?

262
00:13:24,980 --> 00:13:27,845
Me näeme tagasipöördumist meie
imeline sõber moodul.

263
00:13:27,845 --> 00:13:31,020
Nagu te poisid peagi
tunnustada programmeerimine,

264
00:13:31,020 --> 00:13:34,910
Peaaegu igal vajate midagi
ümbritsev midagi,

265
00:13:34,910 --> 00:13:36,850
moodul saab olema nii, et seda teha.

266
00:13:36,850 --> 00:13:40,510
Nii teades, et keegi ei taha
proovida selgitades, et koodirida?

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

268
00:13:44,060 --> 00:13:47,507
Jah, kõik vastused on
tunnustatud ja oodatud.

269
00:13:47,507 --> 00:13:48,840
Sihtrühm: Kas sa räägid minuga?

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

271
00:13:49,506 --> 00:13:56,200
Sihtrühm: Oh, no sorry.

272
00:13:56,200 --> 00:14:00,250
ANDI PENG: OK, nii et olgem
kõndida läbi selle koodi.

273
00:14:00,250 --> 00:14:03,642
Nii et kui sa üritad
lisada midagi peale järjekorda,

274
00:14:03,642 --> 00:14:08,510
kenas nii, et pea juhtub
olla siin, see on väga lihtne meile

275
00:14:08,510 --> 00:14:10,960
minge lõpuni
lisada midagi, eks?

276
00:14:10,960 --> 00:14:14,690
Aga mõte järjekord on
et pea saab tegelikult dünaamiliselt

277
00:14:14,690 --> 00:14:17,280
muutuda sõltuvalt kus me
tahan algust meie q olema,

278
00:14:17,280 --> 00:14:19,880
ning sellistena saba
Samuti muutub.

279
00:14:19,880 --> 00:14:31,100
>> Ja nii kujutan ette, et see ei olnud
järjekorras, vaid see oli järjekorras.

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

281
00:14:37,900 --> 00:14:39,330
Oletame, et juht on siinsamas.

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

283
00:14:54,900 --> 00:14:56,980
Oletame, et meie järjekorda nägi välja selline.

284
00:14:56,980 --> 00:15:00,190
Kui me tahtsime minna, kus
Alguses rida,

285
00:15:00,190 --> 00:15:03,400
oletame me nihkunud pea
Sel moel ja suurused siin.

286
00:15:03,400 --> 00:15:07,100
>> Nüüd tahame midagi lisada
Selles järjekorras, kuid kui poisid näevad,

287
00:15:07,100 --> 00:15:11,150
see ei ole nii lihtne kui lihtsalt
lisada iganes on pärast suurus

288
00:15:11,150 --> 00:15:13,630
sest siis otsa
piire meie tegelik massiivi.

289
00:15:13,630 --> 00:15:16,190
Kus me tahame tõesti lisada siin.

290
00:15:16,190 --> 00:15:18,610
See on ilu järjekorras
on see, et meile, visuaalselt see

291
00:15:18,610 --> 00:15:22,380
Tundub, et liin läheb niimoodi,
aga kui salvestatud andmete struktuur,

292
00:15:22,380 --> 00:15:29,370
Annavad see nii nagu tsüklis.

293
00:15:29,370 --> 00:15:32,360
See liik murtakse
ees samamoodi

294
00:15:32,360 --> 00:15:34,780
et liin võib ka pakkima
ümber sõltuvalt kus sa

295
00:15:34,780 --> 00:15:36,279
tahan rea algusesse olla.

296
00:15:36,279 --> 00:15:38,630
Ja kui me võtame
odavnema siin, olgem

297
00:15:38,630 --> 00:15:40,880
öelda tahtsime luua
funktsiooni nimetatakse Lisa järjekorda.

298
00:15:40,880 --> 00:15:43,980
Me tahtsime, et lisada int n sellesse q.

299
00:15:43,980 --> 00:15:49,250
Kui q.size q-- me kutsume, et meie andmed
structure-- kui meie queue.size ei

300
00:15:49,250 --> 00:15:52,520
võrdne võimsus või kui
see on vähem kui võimsust,

301
00:15:52,520 --> 00:15:55,120
q.strings on massiivi meie q.

302
00:15:55,120 --> 00:15:58,380
Me läheme seatud
mis võrdub q.heads,

303
00:15:58,380 --> 00:16:02,730
mis on siinsamas, pluss q.size
moodul poolt võimsust, mis

304
00:16:02,730 --> 00:16:04,290
murrab meid tagasi siinkandis.

305
00:16:04,290 --> 00:16:08,040
>> Nii selles näites indeksi
Pea on 1, eks?

306
00:16:08,040 --> 00:16:11,480
Indeks suurus on 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Nii saame teha 1 pluss 4 moodulit
meie suutlikkust, mis on 5.

308
00:16:19,500 --> 00:16:20,920
Mida see meile annab?

309
00:16:20,920 --> 00:16:23,270
Mis on indeks, mis
väljub seda?

310
00:16:23,270 --> 00:16:24,080
>> Sihtrühm: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI PENG: 0, mis
juhtub olema just siin,

312
00:16:27,870 --> 00:16:30,640
ja nii me tahame, et oleks võimalik
et lisada siin.

313
00:16:30,640 --> 00:16:34,730
Ja nii see võrrand siin mingi
lihtsalt töötab iga numbrid

314
00:16:34,730 --> 00:16:36,750
sõltuvalt sellest, kus teie
pea ja oma suurus on.

315
00:16:36,750 --> 00:16:38,541
Kui sa tead, mida need
asjad on, sa tead

316
00:16:38,541 --> 00:16:43,170
täpselt, kuhu soovite lisada
kõik, mis on pärast oma järjekorda.

317
00:16:43,170 --> 00:16:44,640
Kas see mõtet kõigile?

318
00:16:44,640 --> 00:16:48,560
>> Ma tean, et mingi aju
teaser eriti kuna see

319
00:16:48,560 --> 00:16:50,512
tuli pärast oma viktoriini.

320
00:16:50,512 --> 00:16:52,220
Aga loodetavasti kõik
Nüüd saan aru,

321
00:16:52,220 --> 00:16:57,800
miks see lahendus või selle
funktsiooni on nii, et see on.

322
00:16:57,800 --> 00:16:59,840
Igaüks natuke ebaselge, mis?

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

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

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

326
00:17:07,109 --> 00:17:09,970
>> Ja nii nüüd, kui te
tahtsin dequeue, seda

327
00:17:09,970 --> 00:17:15,240
on koht, kus meie peas oleks nihkub
sest kui me dequeue,

328
00:17:15,240 --> 00:17:17,030
me ei stardi lõppu q.

329
00:17:17,030 --> 00:17:19,130
Me tahame võtta pea maha, eks?

330
00:17:19,130 --> 00:17:24,260
Nii tõttu, peas on muutu,
ja sellepärast, kui teil Lisa järjekorda,

331
00:17:24,260 --> 00:17:26,800
sul jälgida
kus oma peaga ja oma suurus

332
00:17:26,800 --> 00:17:29,450
oleksid võimelised sisestada
õigesse asendisse.

333
00:17:29,450 --> 00:17:32,740
>> Ja nii, kui sa dequeue,
Ma ka pseudokoodi välja.

334
00:17:32,740 --> 00:17:35,480
Julgelt kui soovite
püüda kodeerimine selle välja.

335
00:17:35,480 --> 00:17:36,980
Sa tahad, et liigutada pea, eks?

336
00:17:36,980 --> 00:17:39,320
Kui ma tahtsin dequeue, ma
liiguksid pea üle.

337
00:17:39,320 --> 00:17:40,800
See oleks peas.

338
00:17:40,800 --> 00:17:45,617
>> Ja meie praegune suurus oleks
lahutada, sest meil ei ole enam

339
00:17:45,617 --> 00:17:46,950
on neli elementi massiivi.

340
00:17:46,950 --> 00:17:51,370
Meil on ainult kolm, ja siis me tahame
tagasi iganes oli ladestunud

341
00:17:51,370 --> 00:17:56,260
pea, sest me tahame seda
väärtust, nii väga sarnane pinu.

342
00:17:56,260 --> 00:17:58,010
Just te võtate
alates erinevas kohas

343
00:17:58,010 --> 00:18:01,770
ja sa pead ümber jaotada pointer
et teises kohas kui tulemus.

344
00:18:01,770 --> 00:18:03,890
Loogiliselt igaüks jälgida?

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

346
00:18:05,690 --> 00:18:10,156
>> OK, nii et me ei kavatse rääkida natuke
põhjalikum umbes ahelloendid

347
00:18:10,156 --> 00:18:13,280
sest nad on väga väärtuslik
Teile käigus sel nädalal

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

349
00:18:14,964 --> 00:18:17,130
Ahelloendid, kui poisid
ei mäleta, kõik nad on

350
00:18:17,130 --> 00:18:22,570
on sõlmed, mis on sõlmede teatud
väärtused nii väärtus ja osuti

351
00:18:22,570 --> 00:18:26,290
mis on omavahel ühendatud
need suunanäitajaks.

352
00:18:26,290 --> 00:18:29,880
Ja nii struct kuidas
loome sõlme siin on meil

353
00:18:29,880 --> 00:18:33,569
on int n, mis on iganes
väärtus poest või string n

354
00:18:33,569 --> 00:18:35,610
või mis iganes soovid
nimetame seda, süsi star n.

355
00:18:35,610 --> 00:18:41,482
Struct node täht, mis on pointer
et sa tahad olla iga sõlme,

356
00:18:41,482 --> 00:18:43,690
sa lähed on, et
pointer punkti suunas kõrval.

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

358
00:18:48,207 --> 00:18:50,040
Sul on head
on seotud loend, mis on

359
00:18:50,040 --> 00:18:53,140
läheb viitavad ülejäänud
väärtused nii edasi ja nii edasi

360
00:18:53,140 --> 00:18:55,290
kuni sa lõpuks jõuda lõpuni.

361
00:18:55,290 --> 00:18:58,040
Ja see viimane sõlm on lihtsalt
läheb ole kursorit.

362
00:18:58,040 --> 00:18:59,952
See saab osutada
null, ja see on kui

363
00:18:59,952 --> 00:19:01,910
sa tead, olete tabanud
lõpuks oma ahelloendid

364
00:19:01,910 --> 00:19:04,076
on siis, kui viimane pointer
ei viita midagi.

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

366
00:19:06,670 --> 00:19:10,990
>> Nii et me läheme veidi rohkem
sügavus kohta, kuidas keegi võib-olla

367
00:19:10,990 --> 00:19:12,400
otsi ahelloend.

368
00:19:12,400 --> 00:19:15,460
Pea meeles, mida on mõned
puudused ahelloendid

369
00:19:15,460 --> 00:19:19,340
salmid massiivi osas otsingud.

370
00:19:19,340 --> 00:19:22,565
Hulgaliselt saate Kahendotsingupuu, kuid
miks ei saa sa seda teha ahelloend?

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

372
00:19:26,834 --> 00:19:30,320
>> Sihtrühm: Sest nad kõik ühendatud,
kuid sa ei tea täpselt, kus

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

374
00:19:31,330 --> 00:19:34,600
>> ANDI PENG: Jah, täpselt nii, mäletan
et sära massiivi

375
00:19:34,600 --> 00:19:37,190
oli see, et meil oli
muutmälu, kus

376
00:19:37,190 --> 00:19:41,580
kui ma tahtsin väärtuse indeksi
kuus, võin öelda indeks kuus,

377
00:19:41,580 --> 00:19:42,407
mulle, et väärtus.

378
00:19:42,407 --> 00:19:45,240
Ja seda sellepärast, massiivid on järjestatud
saadakse katkematu space mälu

379
00:19:45,240 --> 00:19:48,020
ühes kohas, samas
Selline ahelloendid

380
00:19:48,020 --> 00:19:52,820
on juhuslikult segamini kogu,
ja ainus viis sa leiad ühe

381
00:19:52,820 --> 00:19:56,890
on läbi osuti, mis ütleb,
aadress, kus see järgmine sõlm.

382
00:19:56,890 --> 00:20:00,290
>> Ja nii selle tulemusena ainus viis
otsida ahelloend

383
00:20:00,290 --> 00:20:01,560
on lineaarne otsing.

384
00:20:01,560 --> 00:20:05,890
Kuna ma ei tea täpselt, kus
12. väärtusega seotud nimekiri on,

385
00:20:05,890 --> 00:20:08,780
Mul on läbida tervikuna
Selle ahelloendid üks

386
00:20:08,780 --> 00:20:12,450
ühe peast esimese sõlme,
Teise sõlme, kolmandale sõlme,

387
00:20:12,450 --> 00:20:17,690
täiesti alla, kuni ma lõpuks saada
kust selle sõlme Otsin on.

388
00:20:17,690 --> 00:20:22,110
Ja nii selles mõttes, otsi
kohta ahelloend on alati n.

389
00:20:22,110 --> 00:20:23,040
See on alati n.

390
00:20:23,040 --> 00:20:25,690
See on alati lineaarne aeg.

391
00:20:25,690 --> 00:20:28,470
>> Ja nii kood, milles
meil rakendada seda, ja see

392
00:20:28,470 --> 00:20:32,620
on natuke uue kutid, sest sa
poisid on tõesti ei rääkinud või kunagi

393
00:20:32,620 --> 00:20:35,000
näinud viiteid, kuidas
Otsige vihjeid,

394
00:20:35,000 --> 00:20:37,670
nii me käime läbi
see väga aeglaselt.

395
00:20:37,670 --> 00:20:40,200
Nii bool otsing, õige,
Oletame, me tahame

396
00:20:40,200 --> 00:20:42,820
luua funktsiooni nimetatakse
otsing, mis tagastab true

397
00:20:42,820 --> 00:20:46,820
Kui olete leidnud väärtus sees seotud
nimekirja ning ta naaseb vale teisiti.

398
00:20:46,820 --> 00:20:50,030
Sõlme star nimekiri on
Praegu lihtsalt kursor

399
00:20:50,030 --> 00:20:52,960
esimese punkti oma ahelloendid.

400
00:20:52,960 --> 00:20:56,700
int n on väärtus, et sa oled
otsivad selles nimekirjas.

401
00:20:56,700 --> 00:20:58,770
>> Nii sõlme star pointer võrdub nimekirja.

402
00:20:58,770 --> 00:21:00,970
See tähendab, et me, millega
ja luua pointer

403
00:21:00,970 --> 00:21:03,592
Seda esimest sõlme sisemusse nimekirja.

404
00:21:03,592 --> 00:21:04,300
Igaüks minuga?

405
00:21:04,300 --> 00:21:06,530
Nii et kui me olime minna
siia tagasi, oleksin

406
00:21:06,530 --> 00:21:13,850
vormindatud osuti, mis viitab
juht iganes see nimekiri on.

407
00:21:13,850 --> 00:21:18,600
>> Ja siis kui sa siin,
samas osuti ei võrdu null,

408
00:21:18,600 --> 00:21:22,160
nii et on silmus, kus me oleme
läheb hiljem liiklevad

409
00:21:22,160 --> 00:21:25,940
Ülejäänud meie nimekirjas, sest mida
juhtub, kui osuti võrdub null?

410
00:21:25,940 --> 00:21:27,550
Me teame, et me have--

411
00:21:27,550 --> 00:21:28,450
>> Sihtrühm: [kuuldamatu]

412
00:21:28,450 --> 00:21:31,491
>> ANDI PENG: Täpselt, nii et me teame, et
oleme jõudnud nimekirja, eks?

413
00:21:31,491 --> 00:21:34,470
Kui sa lähed tagasi siin, iga sõlm
tuleks juhtides teise sõlme

414
00:21:34,470 --> 00:21:36,550
ja nii edasi ja nii edasi
kuni jõuad lõpuks

415
00:21:36,550 --> 00:21:41,589
saba oma ahelloendid,
mis on viit, et lihtsalt

416
00:21:41,589 --> 00:21:43,130
ei viita kusagil peale no.

417
00:21:43,130 --> 00:21:47,510
Ja nii sa põhimõtteliselt teada, et
Sinu loend on ikka seal üleval

418
00:21:47,510 --> 00:21:50,900
kuni osuti ei võrdu
null, sest kui see võrdub null,

419
00:21:50,900 --> 00:21:53,310
sa tead, et seal ei ole rohkem asju.

420
00:21:53,310 --> 00:21:56,930
>> Nii et on silmus, kus me oleme
läheb on tegelik otsing.

421
00:21:56,930 --> 00:22:01,690
Ja kui pointer-- näete
sellist nool funktsioon olemas?

422
00:22:01,690 --> 00:22:06,930
Nii et kui osuti osutab n, kui
osutiga kell n võrdub võrdub n,

423
00:22:06,930 --> 00:22:09,180
et tähendab, et kui
kursorit, et sa oled

424
00:22:09,180 --> 00:22:13,420
otsivad otsas iga
sõlm on tegelikult võrdub

425
00:22:13,420 --> 00:22:15,990
otsite, siis
soovite naasta tõsi.

426
00:22:15,990 --> 00:22:19,280
Ühesõnaga, kui sa oled sõlmes, et
on väärtus, mida te otsite,

427
00:22:19,280 --> 00:22:23,550
sa tead, et sa oled olnud
edukalt otsida.

428
00:22:23,550 --> 00:22:27,150
>> Muidu soovite seada
kursor järgmisele sõlme.

429
00:22:27,150 --> 00:22:28,850
Just seda rida siin teeb.

430
00:22:28,850 --> 00:22:31,750
Pointer võrdub pointer kõrval.

431
00:22:31,750 --> 00:22:33,360
Igaüks, kuidas see töötab?

432
00:22:33,360 --> 00:22:36,580
>> Ja sisuliselt sa lähed lihtsalt
läbida kogu nimekirja

433
00:22:36,580 --> 00:22:41,920
ennistamist kursor iga kord enne
sa lõpuks tabas nimekirja lõppu.

434
00:22:41,920 --> 00:22:45,030
Ja sa tead, et ei ole
rohkem sõlmede otsida,

435
00:22:45,030 --> 00:22:47,999
ja siis saate tagasi vale
sest sa tead, et oh, noh,

436
00:22:47,999 --> 00:22:50,540
kui ma olen suutnud leida
läbi kogu nimekiri.

437
00:22:50,540 --> 00:22:54,530
Kui käesoleva näite, kui ma tahtsin
otsima väärtuses 10,

438
00:22:54,530 --> 00:22:57,250
ja ma hakkan eesotsas, ja
Ma otsin täiesti alla,

439
00:22:57,250 --> 00:23:00,550
ja ma lõpuks sain selle, mis
osuti, mis juhib tühjaks,

440
00:23:00,550 --> 00:23:04,415
Ma tean, et jama, ma arvan, et 10 ei ole
seda nimekirja, sest ma ei suutnud seda leida.

441
00:23:04,415 --> 00:23:06,520
Ja Kõht lõpus nimekirjast.

442
00:23:06,520 --> 00:23:11,040
Ja sel juhul sa tead
Ma lähen tagasi vale.

443
00:23:11,040 --> 00:23:12,900
>> Lubage, et õlil natuke.

444
00:23:12,900 --> 00:23:17,350
See on päris
oluline oma pset.

445
00:23:17,350 --> 00:23:21,140
Loogika on väga lihtne, ehk
süntaktiliselt lihtsalt rakendamisel.

446
00:23:21,140 --> 00:23:23,365
Tahate teha
Veenduge, et saate aru.

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

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

449
00:23:27,650 --> 00:23:32,560
>> OK, nii et kui me oleks
sisestades sõlmed, õigus,

450
00:23:32,560 --> 00:23:35,380
loendisse, sest mäletan
Mis on see, mis kasu

451
00:23:35,380 --> 00:23:39,230
võttes ahelloend versus
massiivi nii ladustamise?

452
00:23:39,230 --> 00:23:41,110
>> Sihtrühm: See on dünaamiline,
nii et see on lihtsam mina--

453
00:23:41,110 --> 00:23:43,180
>> ANDI PENG: Täpselt,
nii et see on dünaamiline, mis

454
00:23:43,180 --> 00:23:46,880
tähendab, et seda saab laiendada ja kahaneb
sõltuvalt kasutaja vajadustest.

455
00:23:46,880 --> 00:23:56,570
Ja nii, selles mõttes, et me ei vaja
raisata tarbetu mälu, sest ma

456
00:23:56,570 --> 00:24:00,850
kui ma ei tea, kui palju väärtusi ma tahan
salvestada, siis ei ole mõtet mind

457
00:24:00,850 --> 00:24:04,310
luua massiivi sest
kui ma tahan salvestada 10 väärtused

458
00:24:04,310 --> 00:24:08,380
ja ma luua massiivi 1000, mis on
palju raisatud mälu, eraldatud.

459
00:24:08,380 --> 00:24:11,180
Sellepärast me tahame kasutada seotud
nimekirja saaks dünaamiliselt

460
00:24:11,180 --> 00:24:13,860
muuta või vähendada meie suurus.

461
00:24:13,860 --> 00:24:17,040
>> Ja nii, et teeb sisestamise
natuke keerulisem.

462
00:24:17,040 --> 00:24:20,810
Kuna me ei saa juhuslikult juurde elemendid
nii, et me oleks massiivi.

463
00:24:20,810 --> 00:24:24,270
Kui ma tahan lisada element
arvesse seitsmenda indeks,

464
00:24:24,270 --> 00:24:26,930
Ma lihtsalt ei aseta
arvesse seitsmenda indeks.

465
00:24:26,930 --> 00:24:30,020
On ahelloend, see ei ole
päris töö nii lihtsalt,

466
00:24:30,020 --> 00:24:34,947
ja nii kui tahtsime sisestada
üks siin seotud nimekirja,

467
00:24:34,947 --> 00:24:36,280
visuaalselt, et see on väga lihtne näha.

468
00:24:36,280 --> 00:24:39,363
Tahame lihtsalt sisestada see seal,
kohe alguses nimekirja,

469
00:24:39,363 --> 00:24:40,840
kohe pärast pea.

470
00:24:40,840 --> 00:24:44,579
>> Aga kuidas on meil võimalik loovutada
suunanäitajaks on natuke keerdunud

471
00:24:44,579 --> 00:24:47,620
või loogiliselt, on mõttekas, kuid
soovite veenduda, et teil on see

472
00:24:47,620 --> 00:24:50,250
täiesti alla, kuna
viimane asi, mida sa tahad

473
00:24:50,250 --> 00:24:52,990
on ümberhindamist pointer
nii, et me teeme siin.

474
00:24:52,990 --> 00:24:58,170
Kui te apparent
pointer pealaest 1

475
00:24:58,170 --> 00:25:01,086
siis kõik äkki
ülejäänud ahelloendid

476
00:25:01,086 --> 00:25:04,680
on kadunud, sest sa ei ole tegelikult
loodud ajutine midagi.

477
00:25:04,680 --> 00:25:06,220
See on osutanud 2.

478
00:25:06,220 --> 00:25:10,080
Kui te ümber jaotada kursorit, siis
Ülejäänud oma nimekirja täiesti kadunud.

479
00:25:10,080 --> 00:25:13,310
Nii et sa tahad olla
väga, väga ettevaatlik siin

480
00:25:13,310 --> 00:25:17,010
kõigepealt määrata
pointer alates iganes

481
00:25:17,010 --> 00:25:20,150
tahan lisada kõikjal
soovite, ja siis

482
00:25:20,150 --> 00:25:22,710
saab apparent ülejäänud oma nimekirja.

483
00:25:22,710 --> 00:25:25,250
>> Nii et see kehtib kõikjal
sa üritad lisada.

484
00:25:25,250 --> 00:25:27,520
Kui soovite sisestada juures
pea, kui soovite vastata siin

485
00:25:27,520 --> 00:25:29,455
Kui soovite lisada juures
lõpus, noh, ma lõpuks

486
00:25:29,455 --> 00:25:30,910
arvan, et sul oleks lihtsalt
ei viida, kuid sa

487
00:25:30,910 --> 00:25:33,830
soovite veenduda, et te ei
kaotavad oma ülejäänud nimekirja.

488
00:25:33,830 --> 00:25:36,640
Tahad alati veenduda
endale sõlme on suunatud

489
00:25:36,640 --> 00:25:39,330
suunas iganes
tahan lisada,

490
00:25:39,330 --> 00:25:42,170
ja siis saad lisada aheldamine kohta.

491
00:25:42,170 --> 00:25:43,330
Igaüks selge?

492
00:25:43,330 --> 00:25:45,427
>> See saab olema
üks tegelikke probleeme.

493
00:25:45,427 --> 00:25:48,010
Üks peamisi küsimusi
sa lähed on oma pset

494
00:25:48,010 --> 00:25:51,340
on see, et sa lähed, et proovida luua
ahelloend ja lisada asju

495
00:25:51,340 --> 00:25:53,340
aga siis lihtsalt kaotada
ülejäänud seotud nimekirja.

496
00:25:53,340 --> 00:25:54,900
Ja sa lähed on, ma
ei tea, miks see toimub?

497
00:25:54,900 --> 00:25:58,040
Ja see valu läbi minna
ja otsida kõiki oma suunanäitajaks.

498
00:25:58,040 --> 00:26:02,100
>> Ja ma garanteerin teile selle pset,
kirjutamise ja joonistamise need sõlmed välja

499
00:26:02,100 --> 00:26:03,344
on väga, väga kasulik.

500
00:26:03,344 --> 00:26:06,010
Nii saab täiesti jälgida
kus kõik oma suunanäitajaks on,

501
00:26:06,010 --> 00:26:08,540
mis toimub vale,
kus kõik oma sõlmed,

502
00:26:08,540 --> 00:26:12,660
mida sa pead tegema, et pääseda või
sisestada või kustutada või ühtegi neist.

503
00:26:12,660 --> 00:26:14,550
Igaüks hea on?

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

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

506
00:26:19,300 --> 00:26:22,600
>> Nii et kui me tahtsime vaadata koodi?

507
00:26:22,600 --> 00:26:24,470
Oh, ma ei tea, kas me
näete the-- OK, nii et

508
00:26:24,470 --> 00:26:27,940
ülaosas kõik see on funktsioon
nimega insert, kus me tahame

509
00:26:27,940 --> 00:26:31,365
lisada int n arvesse seotud nimekirja.

510
00:26:31,365 --> 00:26:32,740
Me läheme suudad seda.

511
00:26:32,740 --> 00:26:34,770
See on palju koodi, palju uusi süntaks.

512
00:26:34,770 --> 00:26:36,220
Me oleme OK.

513
00:26:36,220 --> 00:26:39,120
>> Nii up tipus, kui see
me tahame luua midagi

514
00:26:39,120 --> 00:26:42,380
Mida me peame tegema, eriti kui teil
tahad seda ei tohi hoida virnas

515
00:26:42,380 --> 00:26:43,920
kuid hunnik?

516
00:26:43,920 --> 00:26:45,460
Läheme malloc, eks?

517
00:26:45,460 --> 00:26:48,240
Nii et me läheme luua pointer.

518
00:26:48,240 --> 00:26:52,074
Sõlme, pointer, uus võrdsete
malloc suurust sõlme

519
00:26:52,074 --> 00:26:53,740
sest me tahame, et sõlm luua.

520
00:26:53,740 --> 00:26:56,720
Me soovime, et summa
mälu, et sõlm kulub

521
00:26:56,720 --> 00:26:59,300
jaotatava jaoks
loomiseks uute sõlme.

522
00:26:59,300 --> 00:27:02,270
>> Ja siis me ei kavatse vaadata,
kas uue võrdsete võrdub null.

523
00:27:02,270 --> 00:27:03,370
Pea meeles, mida me ütlesime?

524
00:27:03,370 --> 00:27:06,470
Mida iganes sa malloc,
mida tuleb alati teha?

525
00:27:06,470 --> 00:27:09,490
Alati tuleb vaadata,
kas see on null.

526
00:27:09,490 --> 00:27:13,620
>> Näiteks, kui teie operatsioonisüsteemi
Süsteem oli täiesti täis,

527
00:27:13,620 --> 00:27:17,060
Kui te ei ole enam mälu
kõik ja püüad malloc,

528
00:27:17,060 --> 00:27:18,410
oleks tagasi null teile.

529
00:27:18,410 --> 00:27:21,094
Ja kui sa püüad seda kasutada
kui see oli juhtides tühjaks,

530
00:27:21,094 --> 00:27:23,260
sa ei kavatse võimalik
juurdepääsu sellele teabele.

531
00:27:23,260 --> 00:27:27,010
Ja nii, nagu me tahtsime teha
Veenduge, et iga kord, kui sa oled mallocing,

532
00:27:27,010 --> 00:27:30,500
sa oled alati kontrollida, et näha, kas
et mälu antakse teile on null.

533
00:27:30,500 --> 00:27:33,670
Ja kui see ei ole, siis saame edasi liikuda
kohta koos kogu meie koodi.

534
00:27:33,670 --> 00:27:36,140
>> Nii et me läheme
initsialiseerida uus sõlm.

535
00:27:36,140 --> 00:27:39,050
Me teeme uue n võrdne n.

536
00:27:39,050 --> 00:27:42,390
Ja siis me teeme
seada uusi kursorit uus

537
00:27:42,390 --> 00:27:46,900
to null sest praegu me seda ei tee
taha midagi selle eest osutada.

538
00:27:46,900 --> 00:27:48,755
Me ei tea, kus
see saab panna teid,

539
00:27:48,755 --> 00:27:50,630
ja siis, kui me tahame
lisab selle juht,

540
00:27:50,630 --> 00:27:53,820
siis saame ümber jaotada
kursor pea.

541
00:27:53,820 --> 00:27:58,530
Kas kõik järgivad loogikat
kus see toimub?

542
00:27:58,530 --> 00:28:02,502
>> Kõik me teeme on loomisel uus
sõlm, milles kursorit tühjaks,

543
00:28:02,502 --> 00:28:04,210
ja siis ümberjagamise
see pähe, kui me

544
00:28:04,210 --> 00:28:06,320
tea me tahame lisada see eesotsas.

545
00:28:06,320 --> 00:28:09,420
Ja siis pea läheb
kohakuti, et uus sõlm.

546
00:28:09,420 --> 00:28:11,060
Igaüks OK on?

547
00:28:11,060 --> 00:28:12,380
>> Nii et see on kaheastmeline protsess.

548
00:28:12,380 --> 00:28:14,760
Sul Esmalt määrake
iganes sa luua.

549
00:28:14,760 --> 00:28:18,260
Määra et kursor
viide, ja siis

550
00:28:18,260 --> 00:28:21,400
saab omamoodi apparent
Esimeses pointer

551
00:28:21,400 --> 00:28:22,972
ja suunake see kaasa uue sõlme.

552
00:28:22,972 --> 00:28:25,680
Kui sa tahad lisada see,
Selle loogika läheb paika.

553
00:28:25,680 --> 00:28:27,530
>> See on selline nagu määrates
Ajutise muutujaid.

554
00:28:27,530 --> 00:28:28,700
Pea meeles, et sul
veenduda, et teil

555
00:28:28,700 --> 00:28:30,346
ei kaota peal kui sa vahetada.

556
00:28:30,346 --> 00:28:33,470
Sa tahad teha kindel, et teil on
Ajutise muutuja sellist hoiab

557
00:28:33,470 --> 00:28:35,620
jälgida, kui see asi
on säilitatud nii, et teil

558
00:28:35,620 --> 00:28:41,190
ei kaota väärtust käigus
ja nagu jamada sellega.

559
00:28:41,190 --> 00:28:42,710
>> OK, nii et kood on siin.

560
00:28:42,710 --> 00:28:45,020
Te heita pilk peale osa.

561
00:28:45,020 --> 00:28:48,060
See on seal.

562
00:28:48,060 --> 00:28:50,280
>> Nii et ma arvan, kuidas
Selle erinevad, kui me tahtsime

563
00:28:50,280 --> 00:28:52,300
lisada keskele või lõppu?

564
00:28:52,300 --> 00:28:57,892
Kas kellelgi on aimu, milline on
pseudokoodi kui loogilist viide

565
00:28:57,892 --> 00:29:00,350
et me võtaks, kui me tahtsime
lisada see keskel?

566
00:29:00,350 --> 00:29:03,391
Nii et kui me tahame, et lisab selle
Pea kõik me teeme, on luua uus sõlm.

567
00:29:03,391 --> 00:29:06,311
Seame kursorit selle
uus sõlm iganes pähe,

568
00:29:06,311 --> 00:29:08,310
ja siis seadsime juht
Uue sõlme, eks?

569
00:29:08,310 --> 00:29:11,560
Kui me tahame lisada selle keskel
nimekirja, mis oleks me peame tegema?

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

571
00:29:14,108 --> 00:29:16,110
>> Sihtrühm: ikkagi
olla sarnane protsess

572
00:29:16,110 --> 00:29:19,114
samasuguse määrates viit ja
Seejärel määrates, et osuti,

573
00:29:19,114 --> 00:29:20,530
aga oleks meil leida seal.

574
00:29:20,530 --> 00:29:23,560
>> ANDI PENG: Täpselt nii täpselt
sama protsessi peale sinu

575
00:29:23,560 --> 00:29:27,820
on leida, kus täpselt sa
tahan, et uue viida minema,

576
00:29:27,820 --> 00:29:44,790
nii et kui ma tahan lisada
Keset seotud list-- OK,

577
00:29:44,790 --> 00:29:46,370
Oletame, et on meie ahelloendid.

578
00:29:46,370 --> 00:29:49,500
Kui me tahame, et lisada see siin,
me läheme uue sõlme.

579
00:29:49,500 --> 00:29:50,520
Me läheme malloc.

580
00:29:50,520 --> 00:29:52,220
Me läheme uue sõlme.

581
00:29:52,220 --> 00:29:55,940
Me läheme loovutada
pointer selle sõlme siin.

582
00:29:55,940 --> 00:29:58,335
>> Aga probleem, mis erineb
kust on pea

583
00:29:58,335 --> 00:30:00,490
on see, et me teadsime täpselt
kus pea.

584
00:30:00,490 --> 00:30:01,930
See oli kohe esimene, eks?

585
00:30:01,930 --> 00:30:04,870
Aga siin on meil jälgida
kus me sisestamist.

586
00:30:04,870 --> 00:30:07,930
Kui me sisestamist meie
sõlme siin, meil

587
00:30:07,930 --> 00:30:12,270
veenduda, et
üks eelmise sellele sõlme

588
00:30:12,270 --> 00:30:14,172
on see, et omistab pointer.

589
00:30:14,172 --> 00:30:16,380
Nii siis on selline
jälgida kahte asja.

590
00:30:16,380 --> 00:30:19,420
Kui teil jälgida, kui see
sõlme praegu on sisestamisel arvesse.

591
00:30:19,420 --> 00:30:23,280
Sul on ka jälgida, kui
Eelmise sõlme, et te vaatate

592
00:30:23,280 --> 00:30:24,340
Samuti oli seal.

593
00:30:24,340 --> 00:30:25,830
Igaüks hea on?

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

595
00:30:26,500 --> 00:30:28,000
>> Kuidas panemist lõpus?

596
00:30:28,000 --> 00:30:34,220
Kui ma tahtsin lisada siin-- kui ma tahtsin
lisada uue tipu lõpu nimekirja,

597
00:30:34,220 --> 00:30:37,009
kuidas võiks ma minna seda teed, et?

598
00:30:37,009 --> 00:30:39,300
Sihtrühm: Nii praegu on
Viimane on osutanud null.

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

600
00:30:40,960 --> 00:30:43,560
Täpselt nii see
Praegu on märgitud teada,

601
00:30:43,560 --> 00:30:46,720
ja nii ma arvan, selles mõttes, et see on
väga lihtne lõppu lisada nimekirja.

602
00:30:46,720 --> 00:30:51,810
Kõik, mida pead tegema, on määrata see
võrdne tühjaks ja siis buum.

603
00:30:51,810 --> 00:30:53,070
Just sinna, väga lihtne.

604
00:30:53,070 --> 00:30:53,960
Väga lihtne.

605
00:30:53,960 --> 00:30:56,430
>> Väga sarnane
pea, kuid loogiliselt teile

606
00:30:56,430 --> 00:30:59,690
soovite veenduda, et sammud
te võtate poole teed kõik selle,

607
00:30:59,690 --> 00:31:01,500
Te jälgite mööda.

608
00:31:01,500 --> 00:31:04,420
See on väga lihtne, keskel
oma koodi, sattuda kohta,

609
00:31:04,420 --> 00:31:05,671
oh, mul on nii palju viiteid.

610
00:31:05,671 --> 00:31:07,461
Ma ei tea, kus
midagi osutades.

611
00:31:07,461 --> 00:31:09,170
Ma isegi ei tea, mis sõlme ma olen.

612
00:31:09,170 --> 00:31:11,490
Mis toimub?

613
00:31:11,490 --> 00:31:13,620
>> Relax, rahune maha, hinga sügavalt sisse.

614
00:31:13,620 --> 00:31:15,530
Joonista välja oma ahelloendid.

615
00:31:15,530 --> 00:31:18,800
Kui te ütlete, ma tean, kus täpselt
Mul on vaja sisestada seda arvesse

616
00:31:18,800 --> 00:31:22,970
ja ma tean täpselt, kuidas ümber jaotada minu
suunanäitajaks, palju, palju lihtsam pilt

617
00:31:22,970 --> 00:31:27,200
out-- palju, palju kergem ole
eksida vigu oma koodi.

618
00:31:27,200 --> 00:31:29,410
Igaüks OK on?

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

620
00:31:31,380 --> 00:31:35,120
>> Nii et ma arvan, et mõiste, et me ei ole
tõesti rääkisime enne nüüd,

621
00:31:35,120 --> 00:31:38,131
ja ma arvan, et sa ilmselt
ei esine palju yet--

622
00:31:38,131 --> 00:31:40,880
see on selline arenenud concept--
on see, et me tegelikult on andmed

623
00:31:40,880 --> 00:31:43,900
struktuuri nimetatakse kahekordselt seotud nimekirja.

624
00:31:43,900 --> 00:31:46,390
Nii nagu te poisid ei vaata,
kõik me teeme on luua

625
00:31:46,390 --> 00:31:50,400
tegelik väärtus, extra
osuti iga meie tippe

626
00:31:50,400 --> 00:31:52,660
mis viitab ka eelmise sõlme.

627
00:31:52,660 --> 00:31:58,170
Nii et mitte ainult meil meie
sõlmede juhtida järgmise üks.

628
00:31:58,170 --> 00:32:01,430
Nad juhivad tähelepanu ka eelmine.

629
00:32:01,430 --> 00:32:04,310
Ma ei pea neid kahte just nüüd.

630
00:32:04,310 --> 00:32:06,740
>> Nii siis on kett
mis võib liigutada mõlemas suunas,

631
00:32:06,740 --> 00:32:09,630
ja siis see on natuke lihtsam
loogiliselt jälgida mööda.

632
00:32:09,630 --> 00:32:11,896
Nagu siin asemel
jälgida, oh, ma

633
00:32:11,896 --> 00:32:14,520
on teada, et see sõlm
üks, mis ma pean ümber jaotada,

634
00:32:14,520 --> 00:32:17,532
Ma lihtsalt minna siin ja
lihtsalt tõmmake eelmisest.

635
00:32:17,532 --> 00:32:19,490
Siis ma tean täpselt, kus
mis on, ja siis

636
00:32:19,490 --> 00:32:21,130
ei ole liiklemiseks
tervikuna on seotud nimekirja.

637
00:32:21,130 --> 00:32:22,180
See on natuke lihtsam.

638
00:32:22,180 --> 00:32:24,960
>> Aga kui sellist, siis on kahekordselt
summa suunanäitajaks,

639
00:32:24,960 --> 00:32:26,960
see on kaks korda rohkem mälu.

640
00:32:26,960 --> 00:32:28,950
See on palju viiteid jälgida.

641
00:32:28,950 --> 00:32:32,140
See on natuke keerulisem, kuid see on
natuke kasutajasõbralikumaks sõltuvalt

642
00:32:32,140 --> 00:32:34,080
mida sa üritad saavutada.

643
00:32:34,080 --> 00:32:36,910
>> Nii seda tüüpi andmeid
struktuuri täiesti olemas,

644
00:32:36,910 --> 00:32:40,280
ja struktuur on väga, väga
Lihtne peale kõik sul on,

645
00:32:40,280 --> 00:32:43,850
selle asemel, et lihtsalt kursor kõrval,
teil ka viit eelmist.

646
00:32:43,850 --> 00:32:45,940
See on kõik, vahe oli.

647
00:32:45,940 --> 00:32:47,740
Igaüks hea on?

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

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

650
00:32:50,940 --> 00:32:53,280
>> Olgu, nii et nüüd ma olen
tõesti kulutada ilmselt

651
00:32:53,280 --> 00:32:56,870
nagu 15-20 minutit või lahtiselt
ülejäänud aja osas

652
00:32:56,870 --> 00:32:58,360
räägime hash tabeleid.

653
00:32:58,360 --> 00:33:02,590
Kui paljud kutid
lugenud pset5 spec?

654
00:33:02,590 --> 00:33:03,620
Hea küll, hea.

655
00:33:03,620 --> 00:33:06,160
See on suurem kui 50% normaalselt.

656
00:33:06,160 --> 00:33:07,560
See on OK.

657
00:33:07,560 --> 00:33:10,345
>> Nii nagu te poisid näevad,
sa oled väljakutse pset5

658
00:33:10,345 --> 00:33:16,790
saab rakendada sõnastik
kus sisestad üle 140.000 sõnad

659
00:33:16,790 --> 00:33:20,610
et me anname teile ja õigekirja kontroll
seda vastu kogu tekst.

660
00:33:20,610 --> 00:33:22,580
Anname juhuslik
tükki kirjandust.

661
00:33:22,580 --> 00:33:23,520
Anname Odüsseia.

662
00:33:23,520 --> 00:33:24,561
Anname Ilias.

663
00:33:24,561 --> 00:33:26,350
Anname Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> Ja teie väljakutse
on õigekirja kontrolli

665
00:33:28,220 --> 00:33:31,760
iga sõna kõigis
nende sõnastikud

666
00:33:31,760 --> 00:33:34,960
sisuliselt meie õigekirjakontrolli.

667
00:33:34,960 --> 00:33:38,620
Ja nii seal on mõned osad
luua selle pset,

668
00:33:38,620 --> 00:33:41,970
Alguses sa tahad olla
suudab tegelikult koormus

669
00:33:41,970 --> 00:33:43,970
kõik sõnad oma
sõnastik, ja siis

670
00:33:43,970 --> 00:33:45,530
taha olla võimelised
õigekirja kontrolli neid kõiki.

671
00:33:45,530 --> 00:33:48,780
Ja nii, nagu sa lähed vaja
andmestruktuur, et seda teha kiiresti

672
00:33:48,780 --> 00:33:50,790
ja tõhusalt ja dünaamiliselt.

673
00:33:50,790 --> 00:33:52,900
>> Nii et ma arvan, et kõige lihtsam
kuidas seda teha, siis

674
00:33:52,900 --> 00:33:55,010
ilmselt luua massiivi, eks?

675
00:33:55,010 --> 00:33:58,910
Lihtsaim viis ladustamiseks on teil
saab luua massiivi 140.000 sõnad

676
00:33:58,910 --> 00:34:03,400
ja lihtsalt panna need kõik olemas ja
siis läbida neid Kahendotsingupuu

677
00:34:03,400 --> 00:34:06,780
või valikute või Mitte--
kahju, et sorteerimiskeskuses.

678
00:34:06,780 --> 00:34:10,729
Teil on võimalik järjestada neid ja siis läbida neid
poolt Kahendotsingupuu või lihtsalt lineaarne otsing

679
00:34:10,729 --> 00:34:13,730
ja lihtsalt lõplik sõna, kuid mis
võtab tohutu mälu,

680
00:34:13,730 --> 00:34:15,190
ja see ei ole väga tõhus.

681
00:34:15,190 --> 00:34:18,350
>> Ja nii me ei kavatse hakata
räägi, kuidas muuta

682
00:34:18,350 --> 00:34:20,110
Meie sõiduaega tõhusamaks.

683
00:34:20,110 --> 00:34:23,190
Ja meie eesmärk on saada
konstantse ajaga, kus

684
00:34:23,190 --> 00:34:25,810
see on peaaegu nagu massiivid, kus
sul on hetkeline juurdepääs.

685
00:34:25,810 --> 00:34:28,560
Kui ma tahtsin otsida midagi,
Ma tahan, et oleks võimalik lihtsalt,

686
00:34:28,560 --> 00:34:30,810
Buumi leida täpselt, ja tõmmake see välja.

687
00:34:30,810 --> 00:34:34,100
Ja nii struktuuri, mis
saadame muutumas väga lähedal

688
00:34:34,100 --> 00:34:37,569
to pääse konstantse
aega, see Püha Graal

689
00:34:37,569 --> 00:34:41,370
programmeerimise pidev
aega nimetatakse hash tabelit.

690
00:34:41,370 --> 00:34:45,370
Ja nii David varem mainitud
[Kuuldamatu] natuke loengus,

691
00:34:45,370 --> 00:34:49,100
aga me läheme tõesti
sukelduda sügavale sel nädalal

692
00:34:49,100 --> 00:34:51,780
tükk, mis on seoses
kuidas hash tabelis toimib.

693
00:34:51,780 --> 00:34:53,949
>> Nii nii, et räsi
Tabelis teoseid, näiteks

694
00:34:53,949 --> 00:35:00,230
kui ma tahtsin salvestada kamp sõnadega,
kamp sõna inglise keeles,

695
00:35:00,230 --> 00:35:02,940
Ma võiks teoreetiliselt panna
banaan, õun, kiivi, mango, paar,

696
00:35:02,940 --> 00:35:04,980
ja cantaloupe kõik lihtsalt massiivi.

697
00:35:04,980 --> 00:35:07,044
Nad võiksid kõik sobib ja võib leida.

698
00:35:07,044 --> 00:35:09,210
Oleks selline valu
Otsige ja juurdepääsu,

699
00:35:09,210 --> 00:35:12,920
kuid lihtsam viis seda teha on
et suudame luua tegelikult struktuur

700
00:35:12,920 --> 00:35:15,680
nimetatakse hash tabelit, kus me hash.

701
00:35:15,680 --> 00:35:19,880
Meil töötavad kõik meie võtmeid
räsi funktsioon, võrrand,

702
00:35:19,880 --> 00:35:22,600
mis muudab neid kõiki
mingi väärtus

703
00:35:22,600 --> 00:35:28,740
et siis saame salvestada peale
sisuliselt massiivi seotud nimekirja.

704
00:35:28,740 --> 00:35:32,570
>> Ja nii siin, kui me tahtsime
salvestada inglise sõnad

705
00:35:32,570 --> 00:35:37,250
me võiks lihtsalt, ma ei
tean, muuta kõik esimesed tähed

706
00:35:37,250 --> 00:35:39,630
mingisugune hulk.

707
00:35:39,630 --> 00:35:43,140
Ja nii, kui näiteks tahtsin
A sünonüüm apple--

708
00:35:43,140 --> 00:35:47,460
või indeksiga 0 ja
B sünonüümideks 1,

709
00:35:47,460 --> 00:35:51,030
meil on 26 kirjed
et lihtsalt hoida

710
00:35:51,030 --> 00:35:53,610
kõik tähed
tähestiku, et hakkame koos.

711
00:35:53,610 --> 00:35:56,130
Ja siis saame
Apple on indeks 0.

712
00:35:56,130 --> 00:35:59,160
Saame banaani indeks
1, melon on indeks 2,

713
00:35:59,160 --> 00:36:00,540
ja nii edasi ja nii edasi.

714
00:36:00,540 --> 00:36:04,460
Ja nii kui ma tahtsin otsida
minu hash tabelit ja juurdepääsu õun,

715
00:36:04,460 --> 00:36:07,560
Ma tean, et apple algab
A, ja ma tean täpselt

716
00:36:07,560 --> 00:36:10,860
et see peab olema ja hash
laua indeks 0, sest

717
00:36:10,860 --> 00:36:13,620
Funktsiooni varem määratud.

718
00:36:13,620 --> 00:36:16,572
>> Nii et ma ei tea, me oleme
kasutaja programm, kus

719
00:36:16,572 --> 00:36:18,780
Teil tuleb tasuda koos
arbitrarily-- ei omavoliliselt

720
00:36:18,780 --> 00:36:22,530
üritab mõtlikult
arvan hea võrrandid

721
00:36:22,530 --> 00:36:25,460
saaks levida
välja kõik oma väärtusi

722
00:36:25,460 --> 00:36:29,370
nii nad saavad hõlpsasti
see hiljem koos nagu võrrand

723
00:36:29,370 --> 00:36:31,130
mis sa, ise tead.

724
00:36:31,130 --> 00:36:35,210
Nii selles mõttes kui ma tahtsin minna
mango, ma tean, oh, see algab m.

725
00:36:35,210 --> 00:36:37,134
See peab olema indeks 12.

726
00:36:37,134 --> 00:36:38,800
Mul ei ole otsida midagi.

727
00:36:38,800 --> 00:36:42,080
Ma tean exactly-- ma võiks lihtsalt minna
indeks 12 ja tõmmake see välja.

728
00:36:42,080 --> 00:36:45,520
>> Igaüks selge, kuidas
hash tabeli funktsioon toimib?

729
00:36:45,520 --> 00:36:48,380
See on selline lihtsalt keerulisem massiivi.

730
00:36:48,380 --> 00:36:50,010
See on kõik see.

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

732
00:36:51,630 --> 00:36:57,690
>> Nii et ma arvan, et me joosta
see küsimus, mida

733
00:36:57,690 --> 00:37:06,390
juhtub, kui teil on mitu asja
et teile sama indeksit?

734
00:37:06,390 --> 00:37:10,570
Nii öelda meie funktsioon, kõik see
ei olnud võtta, et esimene täht

735
00:37:10,570 --> 00:37:14,490
ja keerake seda arvesse
vastavate 0 kuni 25 indeks.

736
00:37:14,490 --> 00:37:17,137
See on täiesti trahvi, kui
sul on ainult üks iga.

737
00:37:17,137 --> 00:37:18,970
Aga teine ​​hakkad
millel on rohkem, sa oled

738
00:37:18,970 --> 00:37:20,910
läheb on, mida nimetatakse kokkupõrget.

739
00:37:20,910 --> 00:37:25,580
>> Nii et kui ma püüan sisestada matta ümber hash
tabel, mis on juba banaani peal,

740
00:37:25,580 --> 00:37:27,870
Mis juhtub, kui
üritate sisestada, et?

741
00:37:27,870 --> 00:37:30,930
Halbu asju, sest banaan
juba olemas indeksi

742
00:37:30,930 --> 00:37:33,800
et sa tahad seda säilitada.

743
00:37:33,800 --> 00:37:35,560
Berry selline on nagu, ah, mida ma pean tegema?

744
00:37:35,560 --> 00:37:37,080
Ma ei tea, kuhu minna.

745
00:37:37,080 --> 00:37:38,410
Kuidas lahendada?

746
00:37:38,410 --> 00:37:41,150
>> Ja nii kutid liiki
vaata me seda keeruline asi

747
00:37:41,150 --> 00:37:44,810
kus saame sellist tegelikult
luua ahelloendid meie massiivid.

748
00:37:44,810 --> 00:37:46,840
Ja nii on kõige lihtsam viis
mõtlema sellele,

749
00:37:46,840 --> 00:37:50,830
kõik hash tabel on
massiivi seotud nimekirju.

750
00:37:50,830 --> 00:37:55,670
Ja nii, selles mõttes, sa pead
see ilus massiivi osuti,

751
00:37:55,670 --> 00:37:58,740
ja siis iga kursorit
et väärtus nimetatud indeksis,

752
00:37:58,740 --> 00:38:00,740
saab tegelikult viidata muid asju.

753
00:38:00,740 --> 00:38:05,720
Ja siis on kõik need eraldi
ketid maha tulemata üks suur massiiv.

754
00:38:05,720 --> 00:38:07,960
>> Ja nii siin, kui ma
tahtsin lisada marja-,

755
00:38:07,960 --> 00:38:11,220
Ma tean, OK, ma lähen sisend
läbi minu hash funktsiooni.

756
00:38:11,220 --> 00:38:15,070
Ma lähen lõpuks indeks
1, ja siis ma lähen saama

757
00:38:15,070 --> 00:38:20,410
vaid väiksemad alagrupis seda
hiiglane 140000-sõna sõnastikku.

758
00:38:20,410 --> 00:38:24,220
Ja siis ma lihtsalt otsida
läbi 1/26 sellest.

759
00:38:24,220 --> 00:38:27,910
>> Ja nii siis ma lihtsalt sisestada
marja kas enne või pärast banaani

760
00:38:27,910 --> 00:38:28,820
sel juhul?

761
00:38:28,820 --> 00:38:29,700
Pärast, eks?

762
00:38:29,700 --> 00:38:33,920
Ja nii sa lähed tahan
sisestada selle sõlme pärast banaan,

763
00:38:33,920 --> 00:38:36,667
ja nii sa lähed sisestada
kell saba, mis on seotud nimekirja.

764
00:38:36,667 --> 00:38:38,500
Ma lähen tagasi
Selle eelmise slaidi

765
00:38:38,500 --> 00:38:40,680
nii kutid saavad näha, kuidas
hash funktsiooni toimib.

766
00:38:40,680 --> 00:38:43,980
>> Nii hash funktsiooni on see võrrand
et näed selline oma panus

767
00:38:43,980 --> 00:38:46,940
läbi saada olenemata indeks
soovite määrata selle suunas.

768
00:38:46,940 --> 00:38:51,130
Ja nii, selles näites, kes kõik tahtsime
teha oli võtta esimene täht,

769
00:38:51,130 --> 00:38:55,890
keerata, et võtta indeks, siis me
saab salvestada et meie hash funktsiooni.

770
00:38:55,890 --> 00:39:00,160
Kõik me teeme siin me oleme
ümberehitamiseks esimene täht.

771
00:39:00,160 --> 00:39:04,770
Nii keykey [0] on lihtsalt esimese tähe
mis tahes string meil oli,

772
00:39:04,770 --> 00:39:05,720
me möödaminnes.

773
00:39:05,720 --> 00:39:09,740
Me muutma seda, et ülemine ja
me lahutades poolt suur- A,

774
00:39:09,740 --> 00:39:11,740
seega kõik, mis teeb
annab meile mitmeid

775
00:39:11,740 --> 00:39:13,670
kus saame hash meie väärtuste peale.

776
00:39:13,670 --> 00:39:16,550
>> Ja siis me läheme
tagasi hash moodul suurus.

777
00:39:16,550 --> 00:39:19,340
Ole väga ettevaatlik
sest teoreetiliselt siit

778
00:39:19,340 --> 00:39:21,870
Sinu räsi väärtus võib olla lõpmatu.

779
00:39:21,870 --> 00:39:23,660
See võiks lihtsalt minna ja edasi ja edasi.

780
00:39:23,660 --> 00:39:26,080
See võiks olla mõned tõesti,
tõesti suur väärtus,

781
00:39:26,080 --> 00:39:29,849
kuid kuna teie hash tabelit, et
olete loonud ainult 26 indeksid,

782
00:39:29,849 --> 00:39:31,890
sa tahad teha kindel, et teie
modulusing nii, et teil

783
00:39:31,890 --> 00:39:33,848
ei run-- see on sama
asja nagu oma queue--

784
00:39:33,848 --> 00:39:36,320
nii et sa ei jookse ära
alt oma hash funktsiooni.

785
00:39:36,320 --> 00:39:39,210
>> Tahad murrab ta tagasi umbes
samamoodi [kuuldamatu] kui

786
00:39:39,210 --> 00:39:41,750
sul oli nagu väga,
väga suur täht, sa

787
00:39:41,750 --> 00:39:43,740
ei taha, et
lihtsalt joosta ära lõpuks.

788
00:39:43,740 --> 00:39:46,948
Sama asi siin, sa tahad teha kindel,
see ei tööta otsast maha pakkimine

789
00:39:46,948 --> 00:39:48,330
ümber ülemise tabeli.

790
00:39:48,330 --> 00:39:50,530
Nii et see on lihtsalt väga
Lihtne hash funktsiooni.

791
00:39:50,530 --> 00:39:56,570
Kõik, mis tegin oli võtta esimese
kirjas iganes meie panus oli

792
00:39:56,570 --> 00:40:01,660
ja keerake seda arvesse indeks, mis
me võiks panna meie hash tabelit.

793
00:40:01,660 --> 00:40:05,450
>> Jah, ja nii nagu ma enne ütlesin,
nii, et me lahendada kokkupõrked

794
00:40:05,450 --> 00:40:09,330
Meie hash tabeleid võttes,
mida me nimetame, ühendamine.

795
00:40:09,330 --> 00:40:13,860
Nii et kui sa püüad lisada mitu
sõnad, mis algavad sama asi,

796
00:40:13,860 --> 00:40:16,145
sa lähed on üks räsi.

797
00:40:16,145 --> 00:40:18,770
Avokaadod ja õuna, kui olete
kestab see läbi meie hash funktsiooni,

798
00:40:18,770 --> 00:40:21,450
annan sulle
sama numbrit, mitmeid 0.

799
00:40:21,450 --> 00:40:24,550
Ja nii nagu me lahendada see
et me saame tegelikult omamoodi siduda need

800
00:40:24,550 --> 00:40:27,010
koos läbi ahelloendid.

801
00:40:27,010 --> 00:40:29,600
>> Ja nii selles mõttes,
kutid näen sellist

802
00:40:29,600 --> 00:40:32,640
kuidas andmestruktuurid, et
me oleme, millega varem

803
00:40:32,640 --> 00:40:35,870
nagu rosina seotud nimekirja lahke
on võimalik kokku ühte.

804
00:40:35,870 --> 00:40:38,860
Ja siis saate luua palju
tõhusam andmestruktuurid

805
00:40:38,860 --> 00:40:43,350
et saab hakkama suuremaid summasid
andmed, mis dünaamiliselt suurust sõltuvalt

806
00:40:43,350 --> 00:40:44,870
oma vajadustele.

807
00:40:44,870 --> 00:40:45,620
Igaüks selge?

808
00:40:45,620 --> 00:40:47,580
Igaüks omamoodi selge
mis juhtub siin?

809
00:40:47,580 --> 00:40:52,110
>> Kui ma tahtsin insert-- mida on
puu, mis algab, ma ei tea,

810
00:40:52,110 --> 00:40:54,726
B, välja arvatud marja-, banaan.

811
00:40:54,726 --> 00:40:55,710
>> Sihtrühm: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI PENG: Blackberry, murakas.

813
00:40:57,910 --> 00:41:00,530
Kust Blackberry minna siin?

814
00:41:00,530 --> 00:41:04,251
Noh, me tegelikult ei ole järjestatud
see veel, kuid teoreetiliselt

815
00:41:04,251 --> 00:41:06,250
kui me tahtnud seda
tähestikulises järjekorras,

816
00:41:06,250 --> 00:41:07,944
kus peaks Blackberry minna?

817
00:41:07,944 --> 00:41:09,210
>> Sihtrühm: [kuuldamatu]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG: Täpselt pärast siin, eks?

819
00:41:11,100 --> 00:41:14,950
Aga kuna see on väga raske
reorder-- Ma arvan, et see on kuni teil poisid.

820
00:41:14,950 --> 00:41:17,920
Te saate täielikult
rakendada iganes sa tahad.

821
00:41:17,920 --> 00:41:20,730
Tõhusama
tehes seda ehk

822
00:41:20,730 --> 00:41:24,570
oleks sortida seotud
nimekirjast tähestikulises järjekorras

823
00:41:24,570 --> 00:41:26,520
ja nii kui sa oled
sisestades asju, mida soovid

824
00:41:26,520 --> 00:41:28,632
olla kindel, pange
arvesse tähestikulises järjekorras

825
00:41:28,632 --> 00:41:30,590
et siis, kui sa oled
üritan otsida neid,

826
00:41:30,590 --> 00:41:32,410
sa ei pea läbida kõike.

827
00:41:32,410 --> 00:41:35,290
Sa tead täpselt, kus
see on, ja see on lihtsam.

828
00:41:35,290 --> 00:41:39,100
>> Aga kui sa selline on
asju segamini juhuslikult,

829
00:41:39,100 --> 00:41:41,420
sa ikka lähed on
läbida niikuinii.

830
00:41:41,420 --> 00:41:44,990
Ja nii kui ma tahtsin lihtsalt
lisada Blackberry siin

831
00:41:44,990 --> 00:41:47,470
ja ma tahtsin otsida
see, ma tean, oh, murakas

832
00:41:47,470 --> 00:41:52,012
peab algama indeks 1, nii et ma
tean silmapilkselt lihtsalt otsida 1.

833
00:41:52,012 --> 00:41:53,970
Ja siis ma ei saa sellist
läbida seotud nimekirja

834
00:41:53,970 --> 00:41:56,120
kuni saan Blackberry,
ja then-- jah?

835
00:41:56,120 --> 00:41:59,550
>> Sihtrühm: Kui sa üritad create--
Ma arvan, et niimoodi on väga lihtne hash

836
00:41:59,550 --> 00:42:00,050
funktsiooni.

837
00:42:00,050 --> 00:42:02,835
Ja kui me tahtsime teha
mitmekihilisuse, et nagu,

838
00:42:02,835 --> 00:42:05,870
OK, me tahame eraldub
nagu kõik tähestiku tähti

839
00:42:05,870 --> 00:42:09,040
ja siis jälle meeldima teine ​​komplekt
tähtedest tähed selles,

840
00:42:09,040 --> 00:42:11,715
me panna nagu hash
Tabelis jooksul hash tabelit,

841
00:42:11,715 --> 00:42:13,256
või nagu funktsiooni funktsioon?

842
00:42:13,256 --> 00:42:14,880
Või on selle--

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG: Nii et teie hash
funktsioon-- oma hash tabelis

844
00:42:17,510 --> 00:42:19,360
võib olla nii suur kui sa tahad seda.

845
00:42:19,360 --> 00:42:21,930
Nii selles mõttes, ma arvasin
see oli väga lihtne, väga

846
00:42:21,930 --> 00:42:25,320
lihtne minu jaoks justkui põhineb
kirjadele esimese sõna.

847
00:42:25,320 --> 00:42:28,690
Ja nii seal on ainult 26 võimalusi.

848
00:42:28,690 --> 00:42:32,650
Võin ainult saada 26 valikutest
0 kuni 25, kuna nad saavad ainult

849
00:42:32,650 --> 00:42:36,510
alustada A-st Z aga kui sa tahtsid
lisada ehk rohkem keerukust

850
00:42:36,510 --> 00:42:39,260
või kiiremini joosta aega oma
hash tabelit, mida absoluutselt

851
00:42:39,260 --> 00:42:40,760
saab teha igasuguseid asju.

852
00:42:40,760 --> 00:42:43,330
Võite teha oma
võrrandit, mis annab teile

853
00:42:43,330 --> 00:42:48,000
rohkem jaotus oma
sõnad, siis, kui te otsite,

854
00:42:48,000 --> 00:42:49,300
see saab olema kiirem.

855
00:42:49,300 --> 00:42:52,100
>> See on täiesti su poisid
kuidas sa tahad seda rakendama.

856
00:42:52,100 --> 00:42:55,140
Mõtle seda lihtsalt ämbrid.

857
00:42:55,140 --> 00:42:57,376
Kui ma tahtsin olla
26 ämbrid, ma lähen

858
00:42:57,376 --> 00:42:59,420
sorteerida asju neisse ämbrid.

859
00:42:59,420 --> 00:43:02,980
Aga ma lähen on kamp
kraami iga ämber,

860
00:43:02,980 --> 00:43:05,890
nii et kui sa tahad teha seda
kiiremaks ja tõhusamaks,

861
00:43:05,890 --> 00:43:07,190
andke mulle sada ämbrid.

862
00:43:07,190 --> 00:43:09,290
>> Aga siis sa pead välja mõtlema
viis sorteerida asju, et nad oleksid

863
00:43:09,290 --> 00:43:11,040
õiges kopp nad peaksid olema.

864
00:43:11,040 --> 00:43:13,331
Aga siis, kui sa tegelikult
tahan vaadata, et kopp,

865
00:43:13,331 --> 00:43:16,410
see on palju kiirem, kuna seal on
vähem kraami iga ämber.

866
00:43:16,410 --> 00:43:20,250
Ja nii, jah, see on tegelikult
trikk kutid pset5

867
00:43:20,250 --> 00:43:22,360
on see, et sa pead olema
vaidlustas lihtsalt luua

868
00:43:22,360 --> 00:43:26,170
kõik, mis on kõige tõhusam
funktsiooni võite mõelda, et olla

869
00:43:26,170 --> 00:43:28,520
võimalik salvestada ja vaadata neid väärtusi.

870
00:43:28,520 --> 00:43:30,840
>> Täiesti kuni kutid
aga sa tahad seda teha,

871
00:43:30,840 --> 00:43:32,229
aga see on tõesti hea koht.

872
00:43:32,229 --> 00:43:34,520
Et selline loogika sul
tahan hakata mõtlema

873
00:43:34,520 --> 00:43:37,236
on hästi, miks ma ei tee enam ämbrid.

874
00:43:37,236 --> 00:43:39,527
Ja siis ma pean otsima
vähem asju, ja siis äkki ma

875
00:43:39,527 --> 00:43:41,640
on erinev hash funktsiooni.

876
00:43:41,640 --> 00:43:45,500
>> Jah, seal on palju võimalusi, kuidas seda teha
pset, mõned on teistest kiiremini.

877
00:43:45,500 --> 00:43:50,630
Ma täiesti läheb lihtsalt näha, kuidas
kiire oli kiireim kutid

878
00:43:50,630 --> 00:43:55,170
oleks võimalik saada oma funktsioonide tööd.

879
00:43:55,170 --> 00:43:58,176
OK, kõik hea
ühendamine ja hash tabeleid?

880
00:43:58,176 --> 00:44:00,800
See on tegelikult nagu väga lihtne
mõiste kui sa mõtle selle peale.

881
00:44:00,800 --> 00:44:05,160
Kõik see on on eraldades iganes
Sinu sisendid on kopad,

882
00:44:05,160 --> 00:44:10,670
sorteerimist, ja siis otsida
loetleb, et seal on seostatud.

883
00:44:10,670 --> 00:44:11,852
>> Cool.

884
00:44:11,852 --> 00:44:18,160
Olgu, nüüd on teistmoodi
andmete struktuur, mis nimetatakse puu.

885
00:44:18,160 --> 00:44:20,850
Lähme sisse ja rääkida üritab
mis on selgelt erinevad,

886
00:44:20,850 --> 00:44:22,330
aga samasse kategooriasse.

887
00:44:22,330 --> 00:44:29,010
Sisuliselt kõik puud on selle asemel
korraldamise andmete lineaarselt

888
00:44:29,010 --> 00:44:32,560
et hash tabelis does-- sa
teate, see sai ülemiseks ja alumiseks

889
00:44:32,560 --> 00:44:37,900
ja siis mingi link välja see--
Puu on top kuhu helistada juur,

890
00:44:37,900 --> 00:44:40,220
ja siis on lehed kõik selle ümber.

891
00:44:40,220 --> 00:44:42,390
>> Ja nii kõik olete siin
on lihtsalt ülemise sõlme

892
00:44:42,390 --> 00:44:45,980
mis osutab muude sõlmede, et punktid
rohkem sõlmed, ja nii edasi ja nii edasi.

893
00:44:45,980 --> 00:44:48,130
Ja nii sa lihtsalt osadeks oksad.

894
00:44:48,130 --> 00:44:53,255
See on lihtsalt teistmoodi korraldada
andmed, ja kuna me nimetame seda puud,

895
00:44:53,255 --> 00:44:56,270
kutid lihtsalt-- see on lihtsalt
modelleeritud välja nägema puu.

896
00:44:56,270 --> 00:44:57,670
Sellepärast me nimetame seda puud.

897
00:44:57,670 --> 00:44:59,370
>> Hash tabel näeb välja nagu tabelis.

898
00:44:59,370 --> 00:45:01,310
Puu lihtsalt näeb välja nagu puu.

899
00:45:01,310 --> 00:45:03,300
Kõik see on on eraldi
korraldamise viis sõlmed

900
00:45:03,300 --> 00:45:06,020
sõltuvalt sellest, mida teie vajadused.

901
00:45:06,020 --> 00:45:11,810
>> Nii et teil on root ja
siis on lehed.

902
00:45:11,810 --> 00:45:15,380
Nii, et me saame eriti
mõtle selle peale on Binääripuu,

903
00:45:15,380 --> 00:45:18,150
Binääripuu on lihtsalt
konkreetset tüüpi puu

904
00:45:18,150 --> 00:45:22,450
kus iga sõlme ainult punktid
to, maks, kaks sõlmed.

905
00:45:22,450 --> 00:45:25,434
Ja nii siin on erinevad
sümmeetria oma puu

906
00:45:25,434 --> 00:45:28,600
mis muudab lihtsamaks liiki otsima
millise väärtustab olete, sest siis

907
00:45:28,600 --> 00:45:30,150
on alati vasakule või paremale.

908
00:45:30,150 --> 00:45:33,150
Seal on kunagi nagu vasakul kolmas
vasakul või 4. vasakult.

909
00:45:33,150 --> 00:45:36,358
See on lihtsalt sul on vasakul ja paremal
ja võite otsida kumbagi.

910
00:45:36,358 --> 00:45:38,980
Ja miks on see kasulik?

911
00:45:38,980 --> 00:45:40,980
Nii, et see on
kasulik on kui otsite

912
00:45:40,980 --> 00:45:42,890
otsida väärtusi, eks?

913
00:45:42,890 --> 00:45:45,640
Selle asemel, et rakendada binaarne
otsida viga massiiv,

914
00:45:45,640 --> 00:45:49,260
kui sa tahad, et oleks võimalik sisestada sõlmed
ja ära sõlmi tahte ja ka

915
00:45:49,260 --> 00:45:52,185
säilitada otsing
võimekust Kahendotsingupuu.

916
00:45:52,185 --> 00:45:54,560
Nii et sel viisil, et me oleme omamoodi
tricking-- mäletan, kui me

917
00:45:54,560 --> 00:45:56,530
ütles ahelloendid saa Kahendotsingupuu?

918
00:45:56,530 --> 00:46:01,700
Me mingi luua andmebaasi struktuuri
mis trikke, et tööle jääda.

919
00:46:01,700 --> 00:46:05,034
>> Ja seda sellepärast, et ahelloendid on lineaarne,
nad ainult siduda üksteise järel.

920
00:46:05,034 --> 00:46:06,950
Saame selline on
teistsuguse viiteid

921
00:46:06,950 --> 00:46:09,408
Sel hetkel erinevate sõlmede
mis võib aidata meil otsida.

922
00:46:09,408 --> 00:46:12,590
Ja nii siin, kui ma tahtsin
on kahendotsingupuu,

923
00:46:12,590 --> 00:46:14,090
Ma tean, et mu keskmine kui 55.

924
00:46:14,090 --> 00:46:18,280
Ma lihtsalt luua, et
kui mu keskmine, nagu minu juure,

925
00:46:18,280 --> 00:46:20,770
ja siis ma lähen
väärtuste eralduma ta.

926
00:46:20,770 --> 00:46:25,610
>> Nii et siin, kui ma lähen otsima
väärtus 66, võin hakata 55.

927
00:46:25,610 --> 00:46:27,310
On 66 üle 55?

928
00:46:27,310 --> 00:46:30,970
Jah, see on, nii et ma tean, et ma mus otsida
i n õige kursori selle puu.

929
00:46:30,970 --> 00:46:32,440
Ma lähen 77.

930
00:46:32,440 --> 00:46:35,367
OK, on ​​66 alla või üle 77?

931
00:46:35,367 --> 00:46:37,950
See on vähem kui, et sa tead, oh,
mis peab olema vasakul sõlme.

932
00:46:37,950 --> 00:46:41,410
>> Ja nii siin me sellist säilitamine
kõik suuri asju massiivid,

933
00:46:41,410 --> 00:46:44,420
nii nagu dünaamiline saneerimist
objektide, olles

934
00:46:44,420 --> 00:46:49,530
võimalik sisestada ja kustutada tahtmist,
ilma et peaks muretsema fikseeritud

935
00:46:49,530 --> 00:46:50,370
palju ruumi.

936
00:46:50,370 --> 00:46:52,820
Meil on veel säilitada kõik
neid imelisi asju

937
00:46:52,820 --> 00:46:57,140
samas on võimalik säilitada
sisse ja otsida aeg Kahendotsingupuu

938
00:46:57,140 --> 00:47:00,450
et meil oli ainult varem
võimalik saada fraasi.

939
00:47:00,450 --> 00:47:06,310
>> Cool andmete struktuuri, millist
keeruline rakendada, sõlme.

940
00:47:06,310 --> 00:47:08,311
Nagu näete, kõik see
on struct sõlme

941
00:47:08,311 --> 00:47:10,143
on see, et teil on vasakul
ja õigus pointer.

942
00:47:10,143 --> 00:47:11,044
See on kõik see.

943
00:47:11,044 --> 00:47:12,960
Nii et pigem lihtsalt
võttes x või eelmise.

944
00:47:12,960 --> 00:47:15,920
Sul on vasakul või paremal, ning seejärel
saab omamoodi ühendame

945
00:47:15,920 --> 00:47:16,836
aga sa nii valida.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, me tegelikult toimub
lihtsalt võtta paar minutit.

948
00:47:24,270 --> 00:47:25,790
Nii et me läheme tagasi siia.

949
00:47:25,790 --> 00:47:28,270
Nagu ma ütlesin varem,
Ma nagu selgitas

950
00:47:28,270 --> 00:47:31,520
loogika, kuidas me
oleks otsida seda.

951
00:47:31,520 --> 00:47:33,860
Me läheme püüdma
pseudocoding see välja näha

952
00:47:33,860 --> 00:47:38,000
kui saame mingi kohaldada
Sama loogika Kahendotsingupuu

953
00:47:38,000 --> 00:47:40,055
Erinevat liiki andmete struktuuri.

954
00:47:40,055 --> 00:47:45,049
Kui te tahate võtta nagu paar
minutit ainult mõelda sellele.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
OKEI.

957
00:48:46,925 --> 00:48:51,407
Olgu, ma lähen
tegelikult lihtsalt teile the-- ole,

958
00:48:51,407 --> 00:48:52,990
me räägime pseudokoodi esimene.

959
00:48:52,990 --> 00:48:56,580
Nii ei keegi taha
anda torkehaav, mida

960
00:48:56,580 --> 00:49:02,100
Esimene asi, mida sa teha tahad, kui
sa oled hakanud välja otsimine on?

961
00:49:02,100 --> 00:49:04,460
Kui me otsime
väärtus 66, mis on

962
00:49:04,460 --> 00:49:07,940
Esimene asi, mida me tahame teha, kui
tahame Kahendotsingupuu see puu?

963
00:49:07,940 --> 00:49:10,760
>> Sihtrühm: Sa tahad otsida õige
ja vaatame vasakule ja vaata [kuuldamatu]

964
00:49:10,760 --> 00:49:11,230
suurem number.

965
00:49:11,230 --> 00:49:12,271
>> ANDI PENG: Jah, täpselt.

966
00:49:12,271 --> 00:49:15,350
Nii et sa lähed vaatama oma juurte.

967
00:49:15,350 --> 00:49:18,180
Seal on palju võimalusi, kuidas helistada
see, teie vanem sõlme inimesed ütlevad.

968
00:49:18,180 --> 00:49:21,317
Mulle meeldib öelda root sest
see on nagu puu juur.

969
00:49:21,317 --> 00:49:23,400
Sa lähed vaadata
Sinu Juursõlme, ja sa oled

970
00:49:23,400 --> 00:49:26,940
näeme on 66 suurem
või väiksem kui 55.

971
00:49:26,940 --> 00:49:30,360
Ja kui see on suurem kui, noh, see on
suurem kui kui me tahame vaadata?

972
00:49:30,360 --> 00:49:32,000
Kus me tahame leida nüüd, eks?

973
00:49:32,000 --> 00:49:34,340
Me tahame, et otsida
paremal pool seda puud.

974
00:49:34,340 --> 00:49:38,390
>> Nii et meil on, Sobivalt
pointer, mis osutab paremale.

975
00:49:38,390 --> 00:49:44,325
Ja nii siis saame
meie uus root olema 77.

976
00:49:44,325 --> 00:49:46,450
Me lihtsalt minna sinna, kus
osuti osutab.

977
00:49:46,450 --> 00:49:49,100
Noh, oh, siin me oleme hakanud
kell 77, ja me saame lihtsalt

978
00:49:49,100 --> 00:49:51,172
Selleks rekursiivselt uuesti ja uuesti.

979
00:49:51,172 --> 00:49:52,880
Sel moel saad liiki
kohta on funktsiooni.

980
00:49:52,880 --> 00:49:57,430
Sul on võimalus otsida, et te
lihtsalt korrata ikka ja jälle ja jälle,

981
00:49:57,430 --> 00:50:02,720
sõltuvalt sellest, kus sa tahad otsida
kuni sa lõpuks saada väärtus

982
00:50:02,720 --> 00:50:04,730
mis te otsite.

983
00:50:04,730 --> 00:50:05,230
On loogiline?

984
00:50:05,230 --> 00:50:07,800
>> Ma olen umbes näidata teile tegelik
kood, ja see on palju koodi.

985
00:50:07,800 --> 00:50:08,674
Ei ole vaja närvi.

986
00:50:08,674 --> 00:50:09,910
Me räägime läbi.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Tegelikult mitte.

989
00:50:14,020 --> 00:50:15,061
See oli lihtsalt pseudokoodi.

990
00:50:15,061 --> 00:50:17,860
OK, see oli lihtsalt pseudokoodi,
mis on natuke keeruline,

991
00:50:17,860 --> 00:50:19,751
aga see on täiesti korras.

992
00:50:19,751 --> 00:50:21,000
Igaüks järgmisi koos siin?

993
00:50:21,000 --> 00:50:24,260
Kui juur on null, tagastamise
vale, sest see tähendab

994
00:50:24,260 --> 00:50:26,850
sa ei pea isegi midagi seal.

995
00:50:26,850 --> 00:50:31,376
>> Kui root n on väärtus, nii et kui see
juhtub olema üks vaatate,

996
00:50:31,376 --> 00:50:34,000
siis sa lähed tagasi true
sest sa tead, sa leidsid.

997
00:50:34,000 --> 00:50:36,250
Aga kui väärtus on väiksem
kui juur n, sa oled

998
00:50:36,250 --> 00:50:38,332
läheb otsima vasakul
laps või vasakule lehed,

999
00:50:38,332 --> 00:50:39,540
mida iganes sa tahad seda kutsuda.

1000
00:50:39,540 --> 00:50:41,750
Ja kui väärtus on suurem kui juurestik,
sa lähed otsima õige puu,

1001
00:50:41,750 --> 00:50:44,610
siis lihtsalt käivitada funktsiooni
läbi otsida uuesti.

1002
00:50:44,610 --> 00:50:48,037
>> Ja kui juur on null, et see
tähendab olete jõudnud?

1003
00:50:48,037 --> 00:50:50,120
See tähendab, et sa ei ole
rohkem rohkem lehti otsida,

1004
00:50:50,120 --> 00:50:52,230
siis sa tead, oh, ma
arvan, et see ei ole siin

1005
00:50:52,230 --> 00:50:55,063
sest pärast Olen tutvunud läbi
kogu asi ja see ei ole siin,

1006
00:50:55,063 --> 00:50:56,930
see lihtsalt ei pruugi olla siin.

1007
00:50:56,930 --> 00:50:58,350
>> Kas see mõtet kõigile?

1008
00:50:58,350 --> 00:51:03,230
Nii et see on nagu Kahendotsingupuu säilitamine
võimeid ahelloendid.

1009
00:51:03,230 --> 00:51:09,200
Cool, ja nii teist tüüpi
andmete struktuuri kutid

1010
00:51:09,200 --> 00:51:13,180
võid proovida rakendada oma pset,
sul on ainult valida üks meetod.

1011
00:51:13,180 --> 00:51:19,430
Aga võib-olla alternatiivne meetod
hash tabelis on see, mida me nimetame Prefiksipuu.

1012
00:51:19,430 --> 00:51:24,080
>> Kõik Prefiksipuu on on
konkreetset tüüpi puu

1013
00:51:24,080 --> 00:51:28,600
on väärtused, mis lähevad muud väärtused.

1014
00:51:28,600 --> 00:51:31,450
Nii et selle asemel, millel on binaarsed
puu selles mõttes, et ainult üks

1015
00:51:31,450 --> 00:51:35,940
asi võib tuua kaks, sul võib olla
üks asi käsk palju, palju asju.

1016
00:51:35,940 --> 00:51:39,450
Sa põhimõtteliselt on massiivid
mille sees hoiad

1017
00:51:39,450 --> 00:51:41,790
viiteid, mis viitavad teistele massiivid.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Nii sõlme, kuidas me
oleks määratleda Prefiksipuu

1020
00:51:49,460 --> 00:51:52,590
on me tahame olla
Loogiline, c sõna, eks?

1021
00:51:52,590 --> 00:51:54,920
Nii et sõlm on Boole'i
nagu õige või vale,

1022
00:51:54,920 --> 00:51:58,490
Kõigepealt eesotsas
et massiivi, on see sõna?

1023
00:51:58,490 --> 00:52:03,620
Teiseks, sa tahad olla suunanäitajaks
mis iganes mujal neid on.

1024
00:52:03,620 --> 00:52:07,470
Natuke keeruline, natuke abstraktne, kuid
Ma selgitan, mida see kõik tähendab.

1025
00:52:07,470 --> 00:52:13,800
>> Nii et siin, tipus, kui te
on hulgaliselt kuulutas juba,

1026
00:52:13,800 --> 00:52:17,040
sõlme, kus teil on Boole'i
salvestatud väärtuse ees

1027
00:52:17,040 --> 00:52:19,490
mis ütleb teile, on see sõna?

1028
00:52:19,490 --> 00:52:20,520
See ei ole sõna?

1029
00:52:20,520 --> 00:52:23,240
Ja siis on
ülejäänud massiivi

1030
00:52:23,240 --> 00:52:26,040
tegelikult salvestab kõik
võimalusi, mida see võiks olla.

1031
00:52:26,040 --> 00:52:28,660
Nii näiteks, nagu
ülaosas teil on

1032
00:52:28,660 --> 00:52:32,140
Esimene asi, mis räägib tõtt või
vale, jah või ei, see on sõna.

1033
00:52:32,140 --> 00:52:38,130
>> Ja siis on 0 kuni 26
tähed, et võite salvestada.

1034
00:52:38,130 --> 00:52:42,790
Kui ma tahtsin otsida siin
Nahkhiirte, ma lähen üles

1035
00:52:42,790 --> 00:52:49,200
ja ma vaatan B. leian B minu
massiiv, ja nii et ma tean, OK, on ​​B sõna?

1036
00:52:49,200 --> 00:52:53,010
B ei ole sõna, nii et seega
Pean hoida otsimine.

1037
00:52:53,010 --> 00:52:56,410
Ma lähevad B ja ma vaadata
pointer, et B osutab

1038
00:52:56,410 --> 00:53:00,900
ja ma ei näe teist valikut teavet,
sama struktuur, mis meil oli enne.

1039
00:53:00,900 --> 00:53:05,240
>> Ja siin-- oh, järgmise
kirja [kuuldamatu] on A.

1040
00:53:05,240 --> 00:53:07,210
Nii me vaatame, et massiivi.

1041
00:53:07,210 --> 00:53:10,860
Leiame kaheksanda väärtus,
ja siis me vaatame, oh,

1042
00:53:10,860 --> 00:53:12,840
hei, on see, et sõna on B-A sõna?

1043
00:53:12,840 --> 00:53:13,807
See ei ole sõna.

1044
00:53:13,807 --> 00:53:14,890
Meil hoida otsin.

1045
00:53:14,890 --> 00:53:17,850
>> Ja nii siis me vaatame, kus
kursorit A punktid,

1046
00:53:17,850 --> 00:53:21,130
ja see juhib teise tee
mis meil on rohkem väärtust salvestatud.

1047
00:53:21,130 --> 00:53:24,150
Ja lõpuks, saame
B-A-T, mis on sõna.

1048
00:53:24,150 --> 00:53:25,970
Ja nii et järgmine kord
sa vaatad, sa lähed

1049
00:53:25,970 --> 00:53:30,850
on, et kontrollida, jah,
Selle Boole'i ​​funktsioon on tõsi.

1050
00:53:30,850 --> 00:53:35,450
Ja nii selles mõttes, et me oleme omamoodi
võttes puu massiivid.

1051
00:53:35,450 --> 00:53:39,890
>> Nii siis võib selline otsida maha.

1052
00:53:39,890 --> 00:53:43,650
Selle asemel hashing funktsioon ja
väärtuse omistamisel poolt seotud nimekirja,

1053
00:53:43,650 --> 00:53:49,190
võite lihtsalt ellu
Prefiksipuu mis otsib downwords.

1054
00:53:49,190 --> 00:53:50,850
Tõesti, tõesti keeruline värk.

1055
00:53:50,850 --> 00:53:54,060
Pole lihtne mõelda, sest ma olen nagu
sülitamine nii palju andmestruktuurid välja

1056
00:53:54,060 --> 00:53:58,710
sind, kuid ei igaüks omamoodi
mõista, kuidas loogika see toimib?

1057
00:53:58,710 --> 00:54:01,920
>> OK, lahe.

1058
00:54:01,920 --> 00:54:05,600
Nii B-A-T, ja seejärel
sa lähed otsima.

1059
00:54:05,600 --> 00:54:07,940
Järgmine kord, kui lähed
näha, oh, hei, see on tõsi,

1060
00:54:07,940 --> 00:54:09,273
seega ma tean, et see peab olema sõna.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Sama asi loomaaias.

1063
00:54:13,770 --> 00:54:17,960
Nii et siin on asi just nüüd, kui me
tahtsin otsida loomaaias, just nüüd,

1064
00:54:17,960 --> 00:54:20,780
Praegu loomaaias ei ole
Sõna meie sõnastikku

1065
00:54:20,780 --> 00:54:25,300
sest, nagu kutid näha,
esiteks, et meil on Boole'i

1066
00:54:25,300 --> 00:54:28,590
tagasi tõsi on lõpus zoom.

1067
00:54:28,590 --> 00:54:30,430
Meil on Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> Ja nii siin, me tegelikult ei ole
sõna, zoo, meie sõnastikku

1069
00:54:33,900 --> 00:54:36,070
kuna see kast on märkimata.

1070
00:54:36,070 --> 00:54:39,540
Nii arvuti ei
tean, et loomaaed on sõna

1071
00:54:39,540 --> 00:54:42,430
sest nii, et me oleme
hoidnud seda, vaid zoom siin

1072
00:54:42,430 --> 00:54:44,920
tegelikult on tõeväärtus
mis on olnud välja tõsi.

1073
00:54:44,920 --> 00:54:49,380
Nii et kui me tahame lisada
Sõna, zoo, meie sõnastikku

1074
00:54:49,380 --> 00:54:51,770
Kuidas me minema umbes teeb seda?

1075
00:54:51,770 --> 00:54:55,960
Mida me peame tegema, et veenduda meie
arvuti teab, et Z-O-O on sõna

1076
00:54:55,960 --> 00:54:58,130
ja ole esimene sõna on Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> Sihtrühm: [kuuldamatu]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI PENG: Täpselt, me
soovite veenduda, et see

1079
00:55:01,450 --> 00:55:07,890
siin, et tõeväärtus on
kontrollida off, et see on tõsi.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, siis me läheme, et kontrollida,
nii et me teame täpselt, hei, loomaaias on sõna.

1081
00:55:13,297 --> 00:55:15,380
Ma ütlen
arvuti, et see sõna nii

1082
00:55:15,380 --> 00:55:18,000
et kui arvuti kontrolli,
ta teab, et loomaaed on sõna.

1083
00:55:18,000 --> 00:55:21,269
>> Sest mäletan kõiki neid andmeid
struktuure, see on väga lihtne meile

1084
00:55:21,269 --> 00:55:22,310
öelda, oh, nahkhiir on sõna.

1085
00:55:22,310 --> 00:55:22,851
Loomaaed on sõna.

1086
00:55:22,851 --> 00:55:23,611
Zoom on sõna.

1087
00:55:23,611 --> 00:55:25,860
Aga kui sa oled hoone see,
arvuti ei tea.

1088
00:55:25,860 --> 00:55:28,619
>> Nii et teil on öelda seda täpselt
millisel hetkel on see sõna?

1089
00:55:28,619 --> 00:55:29,910
Mis hetkest on see sõna pole?

1090
00:55:29,910 --> 00:55:31,784
Ja millisel hetkel ma
vaja otsida asju,

1091
00:55:31,784 --> 00:55:34,000
ja millisel hetkel ma pean minema edasi?

1092
00:55:34,000 --> 00:55:37,010
Igaüks selge, et?

1093
00:55:37,010 --> 00:55:39,540
Cool.

1094
00:55:39,540 --> 00:55:42,530
>> Ja nii siis saabub
probleem, kuidas oleks meil

1095
00:55:42,530 --> 00:55:45,560
minna sisestamist midagi
see on tegelikult ei ole seal?

1096
00:55:45,560 --> 00:55:49,090
Nii ütleme lihtsalt tahame lisada
sõna, vann, meie Prefiksipuu.

1097
00:55:49,090 --> 00:55:53,589
Nagu te poisid ei vaata nagu praegu
kõik meil nüüd on B-A-T,

1098
00:55:53,589 --> 00:55:55,630
ja see uus andmestruktuur
seal oli pint, et

1099
00:55:55,630 --> 00:55:59,740
osutas null, sest me eeldame
et oh, pole sõnu pärast B-A-T,

1100
00:55:59,740 --> 00:56:02,530
Miks me peame hoidma
võttes asju pärast, et T.

1101
00:56:02,530 --> 00:56:06,581
>> Aga probleem tekib siis, kui me teeme teile
tahad olla sõna, mis tuleb pärast

1102
00:56:06,581 --> 00:56:07,080
T s.

1103
00:56:07,080 --> 00:56:09,500
Kui teil on vann, sa oled
lähed tahan H õigus.

1104
00:56:09,500 --> 00:56:13,290
Ja nii nagu me teeme, mis on
me ei kavatse luua eraldi sõlme.

1105
00:56:13,290 --> 00:56:16,840
Me ei jaotada iganes summa
mälu selle uue massiivi,

1106
00:56:16,840 --> 00:56:20,720
ja me ei kavatse loovutada suunanäitajaks.

1107
00:56:20,720 --> 00:56:22,947
>> Me läheme loovutada
H, Esiteks on selles null,

1108
00:56:22,947 --> 00:56:24,030
me läheme vabaneda.

1109
00:56:24,030 --> 00:56:26,590
Me läheme pea
H-punktist allapoole.

1110
00:56:26,590 --> 00:56:30,600
Kui me näeme H, me tahame seda
minna kuhugi mujale.

1111
00:56:30,600 --> 00:56:33,910
>> Siin saame siis vaadake ära jah.

1112
00:56:33,910 --> 00:56:38,170
Kui me tabanud H pärast T, oh,
siis me teame, et see on sõna.

1113
00:56:38,170 --> 00:56:41,110
Loogiline läheb tagasi tõsi.

1114
00:56:41,110 --> 00:56:42,950
Igaüks selge, kuidas see juhtus?

1115
00:56:42,950 --> 00:56:45,110
OKEI.

1116
00:56:45,110 --> 00:56:47,214
>> Nii et sisuliselt kõik
Nende andmestruktuuride

1117
00:56:47,214 --> 00:56:50,130
et oleme läinud üle täna, ma olen
läinud üle neid tõesti kiiresti

1118
00:56:50,130 --> 00:56:52,192
ja mitte palju
detail, ja see on OK.

1119
00:56:52,192 --> 00:56:53,900
Kui hakkate jama
Mis, sa pead olema

1120
00:56:53,900 --> 00:56:55,733
jälgida, kus
kõiki viiteid on,

1121
00:56:55,733 --> 00:56:58,060
mis toimub teie
andmestruktuuride jne.

1122
00:56:58,060 --> 00:56:59,810
Nad on väga kasulik,
ja see on kuni teil

1123
00:56:59,810 --> 00:57:03,890
poisid täiesti aru saada, kuidas
soovite rakendada asjad.

1124
00:57:03,890 --> 00:57:07,650
>> Ja nii pset4, on 5-- oh, mis on valesti.

1125
00:57:07,650 --> 00:57:10,140
Pset5 on kirjavead.

1126
00:57:10,140 --> 00:57:13,710
Nagu ma enne ütlesin, sa lähed, kui
uuesti laadida lähtekoodi meilt.

1127
00:57:13,710 --> 00:57:16,210
Seal saab olema kolm peamist
asjad, mida sa allalaadimine.

1128
00:57:16,210 --> 00:57:18,470
Sa laadida sõnastikud,
neelata, ja tekste.

1129
00:57:18,470 --> 00:57:21,660
>> Kõik need asjad on on
kas sõnastikud sõnu

1130
00:57:21,660 --> 00:57:25,190
et me tahame sind vaadata
või test teabe

1131
00:57:25,190 --> 00:57:26,930
et me tahame, et te õigekirja kontroll.

1132
00:57:26,930 --> 00:57:29,670
Ja nii sõnastikud
anname sa lähed

1133
00:57:29,670 --> 00:57:34,870
teile tegelik sõnad, mida me tahame
salvestada kuidagi nii, et see

1134
00:57:34,870 --> 00:57:36,530
tõhusam kui massiivi.

1135
00:57:36,530 --> 00:57:38,470
Ja siis tekst on
saab olema, mida me oleme

1136
00:57:38,470 --> 00:57:43,900
palume teil kirjutada veenduge
kõik sõnad on tõeline sõnu.

1137
00:57:43,900 --> 00:57:47,970
>> Ja nii kolme plokki
programme, et me anname teile

1138
00:57:47,970 --> 00:57:51,130
nimetatakse dictionary.c,
dictionary.h ja speller.c.

1139
00:57:51,130 --> 00:57:56,500
Ja nii kõik dictionary.c teeb on
mida sa palusid rakendada.

1140
00:57:56,500 --> 00:57:57,880
See laeb sõnu.

1141
00:57:57,880 --> 00:58:02,000
See õigekirja kontrolli neid, ja see teeb kindlasti
et kõik on õigesti sisestatud.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h on vaid teegi faili
mis kuulutab kõik need funktsioonid.

1143
00:58:05,180 --> 00:58:07,650
Ja speller.c, me ei kavatse anda teile.

1144
00:58:07,650 --> 00:58:09,290
Sa ei pea midagi muuta ta.

1145
00:58:09,290 --> 00:58:14,290
Kõik speller.c ei ei võta, et
koormustele, kontrollib kiirust see,

1146
00:58:14,290 --> 00:58:19,190
testib mõõdupuuks meeldib, kuidas
kiiresti sa oled võimeline tegema asju.

1147
00:58:19,190 --> 00:58:20,410
>> See on speller.

1148
00:58:20,410 --> 00:58:23,920
Lihtsalt ei jama, kuid teha
Kindlasti saate aru, mida ta teeb.

1149
00:58:23,920 --> 00:58:28,090
Me kasutame funktsiooni nimetatakse getrusage et
testib täita oma õigekirja

1150
00:58:28,090 --> 00:58:28,590
kontrollija.

1151
00:58:28,590 --> 00:58:32,200
Kõik see on põhimõtteliselt testida
ajal kõik oma sõnastikku

1152
00:58:32,200 --> 00:58:33,680
nii, et sa sellest aru.

1153
00:58:33,680 --> 00:58:36,660
Ole ettevaatlik, et mitte jama või
muud asjad ei tööta korralikult.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> Ja suurem osa selle väljakutse on
kutid tõesti muuta dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Me läheme teile
140,000 sõnu sõnaraamatus.

1157
00:58:48,526 --> 00:58:50,900
Me läheme teile tekst
fail, mis on need sõnad,

1158
00:58:50,900 --> 00:58:54,840
ja me tahame, peate olema suuteline korraldama
neid hash tabelit või Prefiksipuu

1159
00:58:54,840 --> 00:58:58,140
sest kui me palume teil kirjutada
kontroll-- kujutage ette, kui sa oled õigekirja

1160
00:58:58,140 --> 00:59:00,690
kontrollides nagu Homerose Odüsseia.

1161
00:59:00,690 --> 00:59:03,010
See on nagu see suur, suur test.

1162
00:59:03,010 --> 00:59:05,190
>> Kujutage ette, kui iga
sõna, mida tuli vaatama

1163
00:59:05,190 --> 00:59:08,100
läbi hulgaliselt 140,000 väärtusi.

1164
00:59:08,100 --> 00:59:10,350
See võtaks igavesti
Teie masin käivitada.

1165
00:59:10,350 --> 00:59:14,490
See on põhjus, miks me tahame korraldada meie
andmed tõhusam andmestruktuurid

1166
00:59:14,490 --> 00:59:17,270
nagu hash tabelit või Prefiksipuu.

1167
00:59:17,270 --> 00:59:20,700
Ja siis saate ikka omamoodi
ja kui te otsite juurdepääsu

1168
00:59:20,700 --> 00:59:22,570
asju lihtsamalt ja kiiremini.

1169
00:59:22,570 --> 00:59:24,934
>> Ja nii olla ettevaatlik, et lahendada kokkupõrkeid.

1170
00:59:24,934 --> 00:59:27,350
Sa lähed, et saada hunnik
sõnade, mis algavad A.

1171
00:59:27,350 --> 00:59:29,957
Sa lähed, et saada hunnik sõnu
et alustada B. sinust

1172
00:59:29,957 --> 00:59:31,290
poisid, kuidas sa tahad seda lahendada.

1173
00:59:31,290 --> 00:59:34,144
Võibolla seal on rohkem
tõhus hash funktsiooni

1174
00:59:34,144 --> 00:59:36,810
kui lihtsalt esimese tähe
midagi, ja nii, et sinust

1175
00:59:36,810 --> 00:59:38,190
poisid sellist teha mida iganes sa tahad.

1176
00:59:38,190 --> 00:59:40,148
>> Võib-olla soovite lisada
kõik tähed kokku.

1177
00:59:40,148 --> 00:59:43,410
Ehk soovid meeldib teha imelikke asju
arvestab tähtede arv,

1178
00:59:43,410 --> 00:59:43,970
mida iganes.

1179
00:59:43,970 --> 00:59:45,386
Kuni kutid, kuidas sa tahad seda teha.

1180
00:59:45,386 --> 00:59:49,262
Kui soovite teha hash tabelit, kui te
tahan proovida Prefiksipuu, täiesti sinust.

1181
00:59:49,262 --> 00:59:52,470
Ma hoiatan teid enne tähtaega, et
Prefiksipuu on tavaliselt veidi raskem

1182
00:59:52,470 --> 00:59:54,520
lihtsalt sellepärast, et seal on palju
rohkem viiteid jälgida.

1183
00:59:54,520 --> 00:59:55,645
Aga täiesti su poisid.

1184
00:59:55,645 --> 00:59:58,742
See on palju tõhusam
Enamasti.

1185
00:59:58,742 --> 01:00:01,450
Sa tahad tõesti võimalik hoida
meeles kõik oma suunanäitajaks.

1186
01:00:01,450 --> 01:00:03,850
Nagu sama asja tegema
et ma tegin siin.

1187
01:00:03,850 --> 01:00:06,871
Kui sa üritad sisestada
väärtused räsi tabeli või kustutada,

1188
01:00:06,871 --> 01:00:08,620
veenduge, et olete
tõesti jälgida

1189
01:00:08,620 --> 01:00:11,860
kus kõik on seetõttu
see on tõesti lihtne, kui ma olen

1190
01:00:11,860 --> 01:00:14,727
üritan sisestada nagu sõna, Andy.

1191
01:00:14,727 --> 01:00:16,810
Ütleme nii, et see on
õige sõna, sõna, andy,

1192
01:00:16,810 --> 01:00:19,640
hiiglane nimekirjas sõnu.

1193
01:00:19,640 --> 01:00:22,450
>> Kui mul just ümber jaotada
kursor vale, oops,

1194
01:00:22,450 --> 01:00:24,940
seal läheb tervikuna
mu ülejäänud seotud nimekirja.

1195
01:00:24,940 --> 01:00:26,897
Nüüd ainult sõna ma
on, Andy ja nüüd

1196
01:00:26,897 --> 01:00:29,230
kõik teised sõnad
sõnastik on kadunud.

1197
01:00:29,230 --> 01:00:31,370
Ja nii sa tahad teha kindel, et sa
jälgida kõiki oma suunanäitajaks

1198
01:00:31,370 --> 01:00:33,661
või sa lähed, et saada
suuri probleeme oma koodi.

1199
01:00:33,661 --> 01:00:35,840
Joonista asju ettevaatlikult sammhaaval.

1200
01:00:35,840 --> 01:00:37,870
See muudab palju lihtsam mõelda.

1201
01:00:37,870 --> 01:00:40,910
>> Ja lõpuks, sa tahad, et oleks võimalik
testida oma tulemuslikkust oma programmi

1202
01:00:40,910 --> 01:00:41,618
suurel pardal.

1203
01:00:41,618 --> 01:00:43,710
Kui kutid võtta
vaata CS50 kohe,

1204
01:00:43,710 --> 01:00:45,210
meil on, mida nimetatakse suureks pardal.

1205
01:00:45,210 --> 01:00:50,200
On skoor lehel kiiremini
õigekirjakontrolli korda kõigis CS50

1206
01:00:50,200 --> 01:00:55,720
Just nüüd, ma arvan, et top nagu 10
korda ma arvan, neist kaheksa on töötajad.

1207
01:00:55,720 --> 01:00:57,960
Me tõesti tahame, et te poisid peksid meid.

1208
01:00:57,960 --> 01:01:00,870
>> Kõik me püüdsime rakendada
kiireim koodi kui võimalik.

1209
01:01:00,870 --> 01:01:04,880
Me tahame teiega proovida vaidlustada
USA ja rakendama kiiremini kui me kõik

1210
01:01:04,880 --> 01:01:05,550
võimalik.

1211
01:01:05,550 --> 01:01:07,970
Ja nii on see tõesti
Esimest korda, et me oleme

1212
01:01:07,970 --> 01:01:12,680
küsib kutid teha pset, et
saab tõesti teha ükskõik mis meetodil

1213
01:01:12,680 --> 01:01:13,760
sa soovid.

1214
01:01:13,760 --> 01:01:17,730
>> Ma olen alati öelnud, et see on rohkem sarnane
reaalse elu lahendus, eks?

1215
01:01:17,730 --> 01:01:19,550
Ma ütlen, hei, ma vajan sind seda tegema.

1216
01:01:19,550 --> 01:01:21,380
Ehitamine programm, mis teeb selle minu jaoks.

1217
01:01:21,380 --> 01:01:22,630
Kas see aga soovite.

1218
01:01:22,630 --> 01:01:24,271
Ma lihtsalt tean, et ma tahan kiiresti.

1219
01:01:24,271 --> 01:01:25,770
See on teie ülesanne sellel nädalal.

1220
01:01:25,770 --> 01:01:27,531
Te, me ei kavatse
teile ülesanne.

1221
01:01:27,531 --> 01:01:29,030
Me läheme teile väljakutse.

1222
01:01:29,030 --> 01:01:31,559
Ja siis see on kuni teil poisid
täiesti lihtsalt nuputada

1223
01:01:31,559 --> 01:01:34,100
Mis on kiireim ja
tõhusam viis täita seda.

1224
01:01:34,100 --> 01:01:34,600
Jah?

1225
01:01:34,600 --> 01:01:37,476
>> Sihtrühm: Kas me lubatud, kui
tahtsin uurida kiiremini viise

1226
01:01:37,476 --> 01:01:40,821
teha räsitabeli online, me saame teha
seda ja tuua kellegi kood?

1227
01:01:40,821 --> 01:01:42,070
ANDI PENG: Jah, täiesti korras.

1228
01:01:42,070 --> 01:01:44,320
Nii et kui te poisid lugeda
spec, seal on line

1229
01:01:44,320 --> 01:01:48,310
spec, mis ütleb teile poisid
on täiesti tasuta teadus hash

1230
01:01:48,310 --> 01:01:51,070
funktsioone, mida mõned
on kiirem räsifunktsioone

1231
01:01:51,070 --> 01:01:54,720
käivitada asju läbi nagu
Niikaua kui te tsiteerivad, et koodi.

1232
01:01:54,720 --> 01:01:57,220
Nii mõned inimesed on juba
arvasin, kiire viise

1233
01:01:57,220 --> 01:02:00,250
tehes õigekirja kabe, kiire
võimalusi teabe säilitamiseks.

1234
01:02:00,250 --> 01:02:02,750
Täiesti kuni kutid kui te
tahan lihtsalt võtta, eks?

1235
01:02:02,750 --> 01:02:04,045
Veenduge, et olete viidates.

1236
01:02:04,045 --> 01:02:06,170
Väljakutseks tõesti
et me üritame testida

1237
01:02:06,170 --> 01:02:09,750
on tagada, et sa tead
teed umbes suunanäitajaks.

1238
01:02:09,750 --> 01:02:12,700
Niipalju kui rakendatakse
tegelik hash funktsiooni

1239
01:02:12,700 --> 01:02:15,070
ja tulemas nagu
matemaatika seda teha,

1240
01:02:15,070 --> 01:02:17,570
kutid teadus iganes
meetodid Online kutid tahavad.

1241
01:02:17,570 --> 01:02:17,996
Jah?

1242
01:02:17,996 --> 01:02:19,700
>> Sihtrühm: Kas me tsiteerida lihtsalt
abil [kuuldamatu]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI PENG: Jah.

1244
01:02:20,120 --> 01:02:22,328
Sa võid, sinu kommentaar,
Teile võib tuua näiteks, oh,

1245
01:02:22,328 --> 01:02:26,127
võetud jutt, jutt,
JANKUTUSTA, hash funktsiooni.

1246
01:02:26,127 --> 01:02:27,210
Igaüks on mingeid küsimusi?

1247
01:02:27,210 --> 01:02:29,694
Me tegelikult breezed
läbi osa täna.

1248
01:02:29,694 --> 01:02:31,610
Ma olen siin, et
vastata küsimustele nii hästi.

1249
01:02:31,610 --> 01:02:36,570
>> Samuti, nagu ma ütlesin, kontor
tundi täna ja homme.

1250
01:02:36,570 --> 01:02:40,307
Spec sel nädalal on tegelikult
super lihtne ja super lühike lugeda.

1251
01:02:40,307 --> 01:02:43,140
Pakun võttes pilk, just
läbi lugeda kogu seda.

1252
01:02:43,140 --> 01:02:45,730
>> Ja Zamyla tegelikult juhatab teid
läbi iga funktsioone

1253
01:02:45,730 --> 01:02:49,796
teil on vaja rakendada, ja nii see on
väga, väga selge, kuidas seda teha kõike.

1254
01:02:49,796 --> 01:02:51,920
Lihtsalt veenduge, et olete
jälgida viiteid.

1255
01:02:51,920 --> 01:02:53,650
See on väga keeruline pset.

1256
01:02:53,650 --> 01:02:56,744
>> See ei ole keeruline, sest nagu,
oh, mõisted on nii palju

1257
01:02:56,744 --> 01:02:59,160
raske või sa pead õppima
nii palju uusi süntaks teed

1258
01:02:59,160 --> 01:03:00,650
et sa tegid viimase pset.

1259
01:03:00,650 --> 01:03:03,320
See pset on raske, kuna
seal on nii palju viiteid,

1260
01:03:03,320 --> 01:03:06,980
ja siis on see väga lihtne, kui
sul on viga teie koodi ei saa

1261
01:03:06,980 --> 01:03:08,315
leida, kui et viga on.

1262
01:03:08,315 --> 01:03:13,200
>> Ja nii täielik ja lausuma usu sind
poisid, et oleks võimalik võita meie [kuuldamatu]

1263
01:03:13,200 --> 01:03:13,700
kirjaviisiga.

1264
01:03:13,700 --> 01:03:16,640
Ma tegelikult ei ole ühtegi kirjalikku kaevanduse
veel, aga ma olen umbes et kirjutada minu.

1265
01:03:16,640 --> 01:03:19,070
Niisiis, kui olete kirjalikult
sinu, ma tulen kirjalikult kaevanduse.

1266
01:03:19,070 --> 01:03:21,070
Ma püüan teha
minu kiiremini kui sinu oma.

1267
01:03:21,070 --> 01:03:23,940
Me näeme, kes on kõige kiirem.

1268
01:03:23,940 --> 01:03:27,340
>> Ja jah, ma näen kõik
kutid siin teisipäeval.

1269
01:03:27,340 --> 01:03:29,510
Ma jooksen mingi nagu pset töökoda.

1270
01:03:29,510 --> 01:03:32,640
Kõik lõigud see
nädal on pset töötoad,

1271
01:03:32,640 --> 01:03:36,690
nii kutid on palju võimalusi
appi, tööaega nagu alati,

1272
01:03:36,690 --> 01:03:41,330
ja ma tõesti ootan
lugedes kõik oma poisid "koodi.

1273
01:03:41,330 --> 01:03:44,160
Mul on viktoriinid siin kui te
poisid tahavad tulla saan neid.

1274
01:03:44,160 --> 01:03:45,880
See on kõik.

1275
01:03:45,880 --> 01:03:48,180