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

2
00:00:00,500 --> 00:00:05,120
[Predvajanje glasbe]

3
00:00:05,120 --> 00:00:12,026

4
00:00:12,026 --> 00:00:12,900
SPEAKER 1: Dobro.

5
00:00:12,900 --> 00:00:14,600
Vsi dobrodošli nazaj na oddelek.

6
00:00:14,600 --> 00:00:18,660
Upam, da ste vsi uspešno
odpočili od kviza

7
00:00:18,660 --> 00:00:19,510
od prejšnjega tedna.

8
00:00:19,510 --> 00:00:22,564
Vem, da je malo nor na trenutke.

9
00:00:22,564 --> 00:00:25,230
Kot sem rekel prej, če ste
v okviru standardnega odklona,

10
00:00:25,230 --> 00:00:28,188
Res ne skrbi, še posebej,
za manj udobno oddelku.

11
00:00:28,188 --> 00:00:30,230
To je o tem, kje bi morali biti.

12
00:00:30,230 --> 00:00:32,850
>> Če si velik, potem pa super.

13
00:00:32,850 --> 00:00:33,650
Čast za vas.

14
00:00:33,650 --> 00:00:36,149
In če se počutite všeč, kar potrebujete
malo več pomoči, prosim

15
00:00:36,149 --> 00:00:38,140
vas prosimo, da se doseže
ven kateremkoli od TF.

16
00:00:38,140 --> 00:00:40,030
Vsi smo tukaj, da vam pomaga.

17
00:00:40,030 --> 00:00:40,960
>> Zato učimo.

18
00:00:40,960 --> 00:00:44,550
Zato sem tukaj vsak ponedeljek za vas
fantje in v pisarni ur ob četrtkih.

19
00:00:44,550 --> 00:00:48,130
Torej, vas prosimo, da mi sporočite
Če ste v skrbeh, kaj

20
00:00:48,130 --> 00:00:52,450
ali če je kaj na kvizu
da boš res všeč obravnavati.

21
00:00:52,450 --> 00:00:56,940
>> Torej agenda za danes
Vse o podatkovnih struktur.

22
00:00:56,940 --> 00:01:01,520
Nekatere od teh so le, da bo prav
da se boste seznanili z njimi.

23
00:01:01,520 --> 00:01:04,870
Ne smete nikoli izvajati
jim v tem razredu.

24
00:01:04,870 --> 00:01:08,690
Nekateri od njih se boste,
kot je za vaš Speller pset.

25
00:01:08,690 --> 00:01:11,380
>> Boste imeli svojo izbiro
med hash tabel in poskusih.

26
00:01:11,380 --> 00:01:13,680
Torej bomo zagotovo šli čez tiste.

27
00:01:13,680 --> 00:01:18,690
To bo zagotovo več vrst
strokovne skupine na visoki ravni še danes, čeprav,

28
00:01:18,690 --> 00:01:22,630
ker obstaja veliko od njih, in če
smo šli v podrobnosti izvajanja

29
00:01:22,630 --> 00:01:26,490
na vse to, da ne bi
celo dobili s povezanimi seznami

30
00:01:26,490 --> 00:01:28,520
in morda malo hash tabel.

31
00:01:28,520 --> 00:01:31,200
>> Tako nosijo s seboj.

32
00:01:31,200 --> 00:01:33,530
Ne bomo, da se delaš
toliko kodiranje tokrat.

33
00:01:33,530 --> 00:01:36,870
Če imate kakršna koli vprašanja o tem
ali želite videti izvaja

34
00:01:36,870 --> 00:01:39,260
ali ga preizkusite sami,
Jaz vsekakor priporočam

35
00:01:39,260 --> 00:01:44,250
bo study.cs50.net, ki
ima primere vseh teh.

36
00:01:44,250 --> 00:01:46,400
Da bomo imeli svoje Powerpointi
s pojasnili, ki jih

37
00:01:46,400 --> 00:01:50,860
nagibajo k uporabi, kakor tudi nekaj programiranja
vaje, zlasti za stvari

38
00:01:50,860 --> 00:01:55,250
kot povezanih seznamih in binarno
drevesa cevi in ​​palice.

39
00:01:55,250 --> 00:01:59,590
Tako malo bolj na visoki ravni, ki
bi bilo lepo za vaju.

40
00:01:59,590 --> 00:02:01,320
>> Torej, s tem, bomo začeli.

41
00:02:01,320 --> 00:02:03,060
In tudi, yes-- kvizi.

42
00:02:03,060 --> 00:02:06,550
Mislim, da večina od vas, ki so v
moj oddelek ima svoje kvize,

43
00:02:06,550 --> 00:02:12,060
toda kdo prihaja v ali nekega razloga
ne, oni so tukaj v ospredju.

44
00:02:12,060 --> 00:02:12,740
>> Tako povezana seznamov.

45
00:02:12,740 --> 00:02:15,650
Vem, da te vrste gre
nazaj pred kvizu.

46
00:02:15,650 --> 00:02:17,940
To je bil teden dni pred
da smo se učili o tem.

47
00:02:17,940 --> 00:02:21,040
Toda v tem primeru bomo samo
iti malo bolj v globino.

48
00:02:21,040 --> 00:02:25,900
>> Torej, zakaj bi mi izbrati
povezani seznam preko matrike?

49
00:02:25,900 --> 00:02:27,130
Kaj jih loči?

50
00:02:27,130 --> 00:02:27,630
Ja?

51
00:02:27,630 --> 00:02:30,464
>> OBČINSTVO: Lahko razširite povezana
Seznam versus fiksne velikosti array je.

52
00:02:30,464 --> 00:02:31,171
SPEAKER 1: Right.

53
00:02:31,171 --> 00:02:33,970
Niz je fiksna velikost medtem
povezani seznam spremenljivo velikost.

54
00:02:33,970 --> 00:02:36,970
Torej, če ne vemo, kako
veliko želimo shraniti,

55
00:02:36,970 --> 00:02:39,880
povezani seznam nam daje velik
način za to, ker smo lahko samo

56
00:02:39,880 --> 00:02:43,730
dodamo na drugem vozlišču in dodajte na
drugo vozlišče in dodamo na drugo vozlišče.

57
00:02:43,730 --> 00:02:45,750
Toda kaj lahko trade-off?

58
00:02:45,750 --> 00:02:49,521
Ali kdo spomnite kompromis
med nizi in povezanih seznamov?

59
00:02:49,521 --> 00:02:50,020
Mmhmm?

60
00:02:50,020 --> 00:02:51,460
>> OBČINSTVO: Moraš
gredo skozi vse poti

61
00:02:51,460 --> 00:02:53,738
skozi povezani seznam
poiskati element na seznamu.

62
00:02:53,738 --> 00:02:55,570
V matriki, lahko
samo najti element.

63
00:02:55,570 --> 00:02:56,278
>> SPEAKER 1: Right.

64
00:02:56,278 --> 00:02:57,120
Torej z arrays--

65
00:02:57,120 --> 00:02:58,500
>> OBČINSTVO: [neslišno].

66
00:02:58,500 --> 00:03:01,090
>> SPEAKER 1: Z nizi, imamo
kar se imenuje random access.

67
00:03:01,090 --> 00:03:04,820
Pomeni, da tisto, kar je, če želimo
kdaj Peta točka seznama

68
00:03:04,820 --> 00:03:07,230
ali Peta točka našega
matrika, lahko smo samo zagrabiti.

69
00:03:07,230 --> 00:03:10,440
Če je povezani seznam, imamo
Ponovil skozi, kajne?

70
00:03:10,440 --> 00:03:14,020
Torej dostop element pri
matrika konstantna čas,

71
00:03:14,020 --> 00:03:19,530
ker s seznamom povezano, da bi
najverjetneje linearni čas, ker morda

72
00:03:19,530 --> 00:03:21,370
naš element je vso pot na koncu.

73
00:03:21,370 --> 00:03:23,446
Moramo iskati skozi vse.

74
00:03:23,446 --> 00:03:25,320
Torej z vsemi temi podatki
strukture gremo

75
00:03:25,320 --> 00:03:29,330
ki se porabi malo več časa,
kaj so plusi in negativov.

76
00:03:29,330 --> 00:03:31,480
Ko bi mi želeli
uporabite enega nad drugim?

77
00:03:31,480 --> 00:03:34,970
In to je nekako
večja stvar vzeti.

78
00:03:34,970 --> 00:03:40,140
>> Torej imamo tukaj
definicija vozlišča.

79
00:03:40,140 --> 00:03:43,040
To je kot enega elementa v
naš povezani seznam, kajne?

80
00:03:43,040 --> 00:03:46,180
Torej smo vsi seznanjeni
z našimi typedef konstruktov,

81
00:03:46,180 --> 00:03:47,980
ki smo šli čez v pregledu zadnjič.

82
00:03:47,980 --> 00:03:53,180
To je bil v bistvu samo ustvarjanje
druga vrsta podatkov, da bi lahko uporabili.

83
00:03:53,180 --> 00:03:57,930
>> In v tem primeru, to je nekaj vozlišče
da bo imela nekaj celo v.

84
00:03:57,930 --> 00:04:00,210
In kaj potem je drugi del tukaj?

85
00:04:00,210 --> 00:04:03,192

86
00:04:03,192 --> 00:04:05,677
Kdorkoli?

87
00:04:05,677 --> 00:04:06,680
>> OBČINSTVO: [neslišno].

88
00:04:06,680 --> 00:04:07,020
>> SPEAKER 1: Ja.

89
00:04:07,020 --> 00:04:08,400
To je kazalec na naslednje vozlišče.

90
00:04:08,400 --> 00:04:12,610
Torej, to bi moralo dejansko biti tukaj.

91
00:04:12,610 --> 00:04:18,790
To je kazalec tipa
vozlišče na naslednjo stvar.

92
00:04:18,790 --> 00:04:22,410
In to je tisto, kar
Obsega naše vozlišče.

93
00:04:22,410 --> 00:04:24,060
Cool.

94
00:04:24,060 --> 00:04:29,390
>> Vse je v redu, tako da z iskanjem, saj smo bili
samo rekel pred roko, če ste

95
00:04:29,390 --> 00:04:31,840
gre za iskanje skozi,
moraš dejansko Ponovil

96
00:04:31,840 --> 00:04:33,660
prek povezanega seznama.

97
00:04:33,660 --> 00:04:38,530
Tako da, če iščemo številko
9, bi morali začeti na naši glavi

98
00:04:38,530 --> 00:04:41,520
in ki nas opozarja na začetku
našega povezani seznam, kajne?

99
00:04:41,520 --> 00:04:44,600
In smo rekli, v redu, pa to
vozlišče vsebuje številko 9?

100
00:04:44,600 --> 00:04:45,690
Ne?

101
00:04:45,690 --> 00:04:47,500
>> Vse je v redu, pojdite na naslednjo.

102
00:04:47,500 --> 00:04:48,312
Sledi mu.

103
00:04:48,312 --> 00:04:49,520
Ali vsebuje številko 9?

104
00:04:49,520 --> 00:04:50,570
No.

105
00:04:50,570 --> 00:04:51,550
Sledite naslednjo.

106
00:04:51,550 --> 00:04:55,490
>> Zato moramo dejansko Ponovil
preko našega povezani seznam.

107
00:04:55,490 --> 00:05:00,070
Ne moremo iti neposredno do mesta, kjer je 9.

108
00:05:00,070 --> 00:05:05,860
In če vi dejansko želijo
videli nekaj psevdo-kodo gor.

109
00:05:05,860 --> 00:05:10,420
Imamo nekaj funkcijo iskanja tukaj
ki traja in-- kaj je potrebno v?

110
00:05:10,420 --> 00:05:13,110

111
00:05:13,110 --> 00:05:14,320
Kaj menite?

112
00:05:14,320 --> 00:05:15,960
Tako lahka.

113
00:05:15,960 --> 00:05:17,784
Kaj je to?

114
00:05:17,784 --> 00:05:18,700
OBČINSTVO: [neslišno].

115
00:05:18,700 --> 00:05:20,366
SPEAKER 1: Število iščemo.

116
00:05:20,366 --> 00:05:20,980
Kajne?

117
00:05:20,980 --> 00:05:22,875
In kaj bi to ustreza?

118
00:05:22,875 --> 00:05:25,020
To je kazalec?

119
00:05:25,020 --> 00:05:26,000
>> OBČINSTVO: vozlišče.

120
00:05:26,000 --> 00:05:28,980
>> SPEAKER 1: vozlišče na seznam
da gledaš, kajne?

121
00:05:28,980 --> 00:05:33,700
Torej imamo nekaj vozlišč kazalec tukaj.

122
00:05:33,700 --> 00:05:37,240
To je točka, ki se dogaja, da
dejansko ponovitev prek našega seznama.

123
00:05:37,240 --> 00:05:39,630
Postavili smo ga enak seznam
ker je to ravno

124
00:05:39,630 --> 00:05:44,380
nastavitev je enaka
začetek našega povezani seznam.

125
00:05:44,380 --> 00:05:50,660
>> In medtem ko to ni NULL, medtem
imamo še vedno stvari v našem seznamu,

126
00:05:50,660 --> 00:05:55,580
preverite, če ima to vozlišče
Število iščemo.

127
00:05:55,580 --> 00:05:57,740
Return true.

128
00:05:57,740 --> 00:06:01,070
V nasprotnem primeru ga dopolni, kajne?

129
00:06:01,070 --> 00:06:04,870
>> Če je NULL, zapustimo naš
while zanko in vrne false

130
00:06:04,870 --> 00:06:08,340
ker to pomeni, da nismo ga našli.

131
00:06:08,340 --> 00:06:11,048
Ali so vsi dobili, kako to deluje?

132
00:06:11,048 --> 00:06:11,548
OK.

133
00:06:11,548 --> 00:06:14,940

134
00:06:14,940 --> 00:06:20,260
>> Torej z vstavljanje, si
imajo tri različne načine.

135
00:06:20,260 --> 00:06:25,250
Moramo dodati, lahko pripnemo
in ga lahko vstavite v kompletu.

136
00:06:25,250 --> 00:06:28,215
V tem primeru smo
bo naredil prepend.

137
00:06:28,215 --> 00:06:33,380
Ali kdo ve, kako tiste,
trije primeri se lahko razlikujejo?

138
00:06:33,380 --> 00:06:36,920
>> Torej prepend pomeni, da si dal
je na sprednji strani vašega seznama.

139
00:06:36,920 --> 00:06:39,770
Tako, da bi to pomenilo, da ni važno,
kaj je tvoj vozlišče, ne glede na to,

140
00:06:39,770 --> 00:06:43,160
kakšna je vrednost, boš
da bi ga tukaj spredaj, OK?

141
00:06:43,160 --> 00:06:45,160
To se dogaja, da je treba najprej
element na seznamu.

142
00:06:45,160 --> 00:06:49,510
>> Če ga priložiti, da se bo
da gredo na zadnji strani vašega seznama.

143
00:06:49,510 --> 00:06:54,010
In vstavite v kompletu pomeni, da ste
bo dal dejansko v mestu

144
00:06:54,010 --> 00:06:57,700
kjer se ohranja vaš povezani seznam razporejene.

145
00:06:57,700 --> 00:07:00,810
Again, kako uporabljate
tisti, in ko uporabljate

146
00:07:00,810 --> 00:07:02,530
jim bo odvisno od vašega primera.

147
00:07:02,530 --> 00:07:05,834

148
00:07:05,834 --> 00:07:07,750
Če to ni potrebno
treba sortirati, prepend nagiba

149
00:07:07,750 --> 00:07:10,460
da je tisto, kar večina ljudi
uporabljati, ker si ne

150
00:07:10,460 --> 00:07:15,680
iti skozi celoten seznam
da bi našli konec, da ga dodate na, kajne?

151
00:07:15,680 --> 00:07:17,720
Lahko samo držijo desno.

152
00:07:17,720 --> 00:07:21,930
>> Torej bomo šli skozi
vstavljanje 1 zdaj.

153
00:07:21,930 --> 00:07:26,360
Torej, ena stvar, ki jo bom
Priporočam, o tem pset

154
00:07:26,360 --> 00:07:29,820
je pripraviti stvari, kot vedno.

155
00:07:29,820 --> 00:07:35,130
To je zelo pomembno, da posodobite
vaši kazalci v pravilnem vrstnem redu

156
00:07:35,130 --> 00:07:38,620
ker če jih posodablja
nekoliko v okvari,

157
00:07:38,620 --> 00:07:42,210
boš na koncu
izgubili dele vašega seznama.

158
00:07:42,210 --> 00:07:49,680
>> Tako na primer, v tem primeru, da smo
pripoveduje glavo na samo točko 1.

159
00:07:49,680 --> 00:07:56,070
Če bomo samo to, da
brez shranjevanja to 1,

160
00:07:56,070 --> 00:07:58,570
nimamo pojma, kaj
1 je treba poudariti, da je sedaj

161
00:07:58,570 --> 00:08:02,490
ker smo izgubili, kar
glava opozoril.

162
00:08:02,490 --> 00:08:05,530
Torej, ena stvar, da se spomnimo
ko delaš prepend

163
00:08:05,530 --> 00:08:09,630
je rešiti, kaj je
glava kaže na prvi,

164
00:08:09,630 --> 00:08:15,210
nato pa jo dodelite, in nato posodobite
kaj bi bilo vaše novo vozlišče opozarjajo.

165
00:08:15,210 --> 00:08:20,870

166
00:08:20,870 --> 00:08:22,560
V tem primeru, to je eden od načinov za to.

167
00:08:22,560 --> 00:08:25,440
>> Torej, če smo to storili na ta način
kjer smo samo prerazporedili glavo,

168
00:08:25,440 --> 00:08:30,320
izgubimo v bistvu Nostra
Celoten seznam, kajne?

169
00:08:30,320 --> 00:08:38,000
Eden od načinov za to je, da ima 1 točko
Naslednji, nato pa imajo glavno točko 1.

170
00:08:38,000 --> 00:08:42,650
Ali lahko narediš nekako kot
začasno skladiščenje, kar sem govoril.

171
00:08:42,650 --> 00:08:45,670
>> Ampak prerazporeditev Vam nadaljne
kazalci v pravilnem zaporedju

172
00:08:45,670 --> 00:08:48,750
se bo zelo, zelo
Pomembno za to pset.

173
00:08:48,750 --> 00:08:53,140
V nasprotnem primeru boste imeli hash
tabele ali poskus, ki je le, da bo treba

174
00:08:53,140 --> 00:08:56,014
le del besed, ki jih
želijo in potem you're-- mmhmm?

175
00:08:56,014 --> 00:08:58,930
OBČINSTVO: Kaj je bilo začasno
shranjevanje stvar, ki jo je bilo govoriš?

176
00:08:58,930 --> 00:09:00,305
SPEAKER 1: začasno skladiščenje.

177
00:09:00,305 --> 00:09:02,760
Torej v bistvu drugo
Tako boste lahko to storite

178
00:09:02,760 --> 00:09:07,650
je shranjevanje glavo nečesa, kot
Shranite ga začasno spremenljivko.

179
00:09:07,650 --> 00:09:11,250
Dodelite 1 in
nato posodobite 1 točko

180
00:09:11,250 --> 00:09:13,830
da ne glede na glavo, s katero kažete.

181
00:09:13,830 --> 00:09:16,920
Tako je očitno
bolj elegantno, ker vas

182
00:09:16,920 --> 00:09:20,770
ne potrebujejo začasno vrednost, vendar
samo ponujajo še en način, da to storite.

183
00:09:20,770 --> 00:09:23,999

184
00:09:23,999 --> 00:09:25,790
In dejansko imajo
del kode za to.

185
00:09:25,790 --> 00:09:28,080
Tako za povezani seznam, smo
dejansko imajo neko kodo.

186
00:09:28,080 --> 00:09:31,930
Torej vstaviti tukaj, to je prepending.

187
00:09:31,930 --> 00:09:34,290
Torej, to ga vklopi na glavi.

188
00:09:34,290 --> 00:09:38,820
>> Torej prva stvar, morate
ustvarite novo vozlišče, seveda,

189
00:09:38,820 --> 00:09:40,790
in preverite NULL.

190
00:09:40,790 --> 00:09:43,250
Vedno dobro.

191
00:09:43,250 --> 00:09:47,840
In potem boste morali dodeliti vrednosti.

192
00:09:47,840 --> 00:09:51,260
Vsakič, ko ustvarite novo vozlišče, vas
Ne vem, kaj je to kaže na naslednjo,

193
00:09:51,260 --> 00:09:54,560
tako da boste želeli, da ga zažene na NULL.

194
00:09:54,560 --> 00:09:58,760
Če se to ne končajo kar kaže na nekaj,
drugje, dobi prerazporediti in to je v redu.

195
00:09:58,760 --> 00:10:00,740
Če je prva stvar,
na seznamu, ki jih potrebuje

196
00:10:00,740 --> 00:10:04,270
izpostaviti, ker NULL
da je konec seznama.

197
00:10:04,270 --> 00:10:12,410
>> Torej, da ga vstavite, vidimo tu
so dodeljevanje naslednjo vrednost našega vozlišča

198
00:10:12,410 --> 00:10:17,380
da se ne glede na glavo,
ki je tisto, kar smo imeli tukaj.

199
00:10:17,380 --> 00:10:19,930
To je tisto, kar smo pravkar storil.

200
00:10:19,930 --> 00:10:25,820
In potem smo dodeljevanje glave do točke
za našo novo vozlišče, saj se spomnite,

201
00:10:25,820 --> 00:10:31,090
Novo je nekaj kazalec na vozlišče,
in to je točno tisto, kar glava.

202
00:10:31,090 --> 00:10:34,370
To je točno, zakaj smo
imajo to puščico accessor.

203
00:10:34,370 --> 00:10:37,030

204
00:10:37,030 --> 00:10:37,530
Cool?

205
00:10:37,530 --> 00:10:38,130
Mmhmm?

206
00:10:38,130 --> 00:10:41,100
>> OBČINSTVO: Ali moramo
zagnati nov Naprej najprej NULL,

207
00:10:41,100 --> 00:10:44,240
ali lahko samo inicializacijo na glavo?

208
00:10:44,240 --> 00:10:48,210
>> SPEAKER 1: New Naslednja
mora biti NULL začeti

209
00:10:48,210 --> 00:10:53,760
ker ne veste,
kjer se dogaja, da se.

210
00:10:53,760 --> 00:10:56,100
Tudi to je vrsta
tako kot paradigmo.

211
00:10:56,100 --> 00:10:59,900
Nastavite, da enaka NULL samo, da bi
Prepričajte se, da so zajete vse vaše baze

212
00:10:59,900 --> 00:11:04,070
preden to storite tako, da kakršno koli prerazporeditev
ste vedno zagotovljeno, da se bo

213
00:11:04,070 --> 00:11:08,880
se kaže na določeno vrednost
primerjavi kot smeti vrednosti.

214
00:11:08,880 --> 00:11:12,210
Ker, ja, moramo določiti
Nov dostavo samodejno,

215
00:11:12,210 --> 00:11:15,420
ampak to je bolj tako kot
dobra praksa inicializacijo

216
00:11:15,420 --> 00:11:19,270
na ta način in potem prerazporedil.

217
00:11:19,270 --> 00:11:23,420
>> OK, tako da dvojno povezani seznam zdaj.

218
00:11:23,420 --> 00:11:24,601
Kaj menite?

219
00:11:24,601 --> 00:11:26,350
Kaj je drugačen z
dvojno povezani seznam?

220
00:11:26,350 --> 00:11:30,750

221
00:11:30,750 --> 00:11:34,300
>> Torej, v naših povezanih seznamov, smo lahko
premikate samo v eno smer, kajne?

222
00:11:34,300 --> 00:11:35,270
Imamo samo naslednje.

223
00:11:35,270 --> 00:11:36,760
Gremo lahko le naprej.

224
00:11:36,760 --> 00:11:40,300
>> Z dvojno povezani seznam,
bomo lahko tudi umakne nazaj.

225
00:11:40,300 --> 00:11:44,810
Torej imamo poleg
Številka, ki jih želite shraniti,

226
00:11:44,810 --> 00:11:50,110
imamo kje pa opozarja, da poleg
in kje smo pravkar prišli.

227
00:11:50,110 --> 00:11:52,865
Torej, to omogoča
nekaj bolje prečkanje.

228
00:11:52,865 --> 00:11:56,620

229
00:11:56,620 --> 00:12:01,240
>> Torej dvakrat povezanih vozlišč,
zelo podobni, kajne?

230
00:12:01,240 --> 00:12:05,000
Edina razlika je, zdaj smo
imajo naslednji in prejšnji.

231
00:12:05,000 --> 00:12:06,235
To je edina razlika.

232
00:12:06,235 --> 00:12:09,570

233
00:12:09,570 --> 00:12:14,790
>> Torej, če smo bili, da moramo dodati ali append-- smo
nimajo nobene kode za ta up here--

234
00:12:14,790 --> 00:12:17,830
ampak, če ste bili, da poskusite in
jo vstavite, pomembno stvar

235
00:12:17,830 --> 00:12:19,980
se morate, da
Preverite, ali ste dodeljevanje

236
00:12:19,980 --> 00:12:23,360
tako vaše prejšnje in vaš
Naslednji kazalec pravilno.

237
00:12:23,360 --> 00:12:29,010
Torej, v tem primeru, bi vam
ne le zagnati zraven,

238
00:12:29,010 --> 00:12:31,820
ponastaviti prejšnje.

239
00:12:31,820 --> 00:12:36,960
Če smo na vrhu seznama smo
bi ne samo glava enako novo,

240
00:12:36,960 --> 00:12:41,750
ampak naša nova prejšnje naj
opozarjajo na glavo, kajne?

241
00:12:41,750 --> 00:12:43,380
>> To je edina razlika.

242
00:12:43,380 --> 00:12:47,200
In če si želite več vaditi z
ti so povezani s seznami, s vstavljanje,

243
00:12:47,200 --> 00:12:49,900
z brisanjem z vložkom
je v urejenem seznamu

244
00:12:49,900 --> 00:12:52,670
Prosimo preverite study.cs50.net.

245
00:12:52,670 --> 00:12:54,870
Tam je kup odličnih vaj.

246
00:12:54,870 --> 00:12:55,870
Toplo jih priporočam.

247
00:12:55,870 --> 00:12:59,210
Želim si, da je imel čas, da gredo skozi njih
ampak tam je veliko podatkovnih struktur

248
00:12:59,210 --> 00:13:01,530
priti skozi.

249
00:13:01,530 --> 00:13:02,650
>> OK, tako razpršene tabele.

250
00:13:02,650 --> 00:13:07,070
To je verjetno najbolj
koristno bit za vaše pset

251
00:13:07,070 --> 00:13:11,090
tukaj, ker boš biti
izvajanje enega od teh, ali poskusiti.

252
00:13:11,090 --> 00:13:12,200
Res mi je všeč hash tabele.

253
00:13:12,200 --> 00:13:13,110
Oni so zelo kul.

254
00:13:13,110 --> 00:13:17,080
>> Torej v bistvu, kaj
zgodi, je razpršena tabela

255
00:13:17,080 --> 00:13:22,050
je, ko res potrebujemo hitro
vstavljanje, brisanje in iskanje.

256
00:13:22,050 --> 00:13:25,010
To so stvari, ki sva
prednostno v hash tabelo.

257
00:13:25,010 --> 00:13:29,500
Lahko dobijo precej velik,
ampak kot smo videli pri poskusih,

258
00:13:29,500 --> 00:13:33,040
obstajajo stvari, ki so veliko večje.

259
00:13:33,040 --> 00:13:38,330
>> Ampak v bistvu, vse hash
Miza je funkcija hash

260
00:13:38,330 --> 00:13:47,215
ki vam pove, katero bucket dati vsak
vaših podatkov, vsako od vaših elementov.

261
00:13:47,215 --> 00:13:51,140
Preprost način, da razmišljajo o hash tabele
je, da je le vedra stvari,

262
00:13:51,140 --> 00:13:51,770
kajne?

263
00:13:51,770 --> 00:13:59,720
Torej, ko ste sortiranje stvari, ki jih
kot prvo črko svojega imena,

264
00:13:59,720 --> 00:14:01,820
to je nekako kot hash tabele.

265
00:14:01,820 --> 00:14:06,180
>> Torej, če bi bil jaz skupini vidva je
v skupine kdor začne ime

266
00:14:06,180 --> 00:14:11,670
z več kot tukaj, ali kdor je za rojstni dan
je v januarju, februarju, marcu,

267
00:14:11,670 --> 00:14:15,220
karkoli, da je učinkovito
ustvarjanjem razpršene tabele.

268
00:14:15,220 --> 00:14:18,120
To je samo ustvarjanje žlice, ki
ste razvrstiti elemente v

269
00:14:18,120 --> 00:14:19,520
tako da boste lahko najti jih je lažje.

270
00:14:19,520 --> 00:14:22,300
Torej, na ta način, ko moram
da bi našli enega izmed vas,

271
00:14:22,300 --> 00:14:24,680
Nimam za iskanje
skozi vsako od vaših imen.

272
00:14:24,680 --> 00:14:29,490
Lahko sem kot, oh, vem, da
Danielle rojstni dan je in--

273
00:14:29,490 --> 00:14:30,240
OBČINSTVO: --April.

274
00:14:30,240 --> 00:14:30,948
SPEAKER 1: april.

275
00:14:30,948 --> 00:14:33,120
Zato sem pogledal v mojo april
vedro, in z malo sreče,

276
00:14:33,120 --> 00:14:38,270
ona je samo ena tam in
moj čas je bil stalnica v tem smislu,

277
00:14:38,270 --> 00:14:41,230
ker se, če moram iskati
skozi cel kup ljudi,

278
00:14:41,230 --> 00:14:43,090
da bo trajalo veliko dlje.

279
00:14:43,090 --> 00:14:45,830
Tako razpršene tabele so res le vedra.

280
00:14:45,830 --> 00:14:48,630
Enostaven način, da razmišljajo o njih.

281
00:14:48,630 --> 00:14:52,930
>> Tako zelo pomembna stvar
hash tabela je funkcija hash.

282
00:14:52,930 --> 00:14:58,140
Torej stvari, sem govoril o, kot so
tvoja prva črka vaše ime

283
00:14:58,140 --> 00:15:01,450
ali vaš rojstni dan, mesec,
To so ideje, ki

284
00:15:01,450 --> 00:15:03,070
Res korelaciji s funkcijo razpršitve.

285
00:15:03,070 --> 00:15:08,900
To je samo način odločanja, ki
ste bucket ste element gre v, OK?

286
00:15:08,900 --> 00:15:14,850
Torej za to pset, si lahko ogledate do
precej koli funkcija hash želite.

287
00:15:14,850 --> 00:15:16,030
>> Ni nujno, da bo svoje.

288
00:15:16,030 --> 00:15:21,140
Obstaja nekaj res kul tisti iz
tam, da stori vse vrste nor matematiki.

289
00:15:21,140 --> 00:15:25,170
In če želite, da bo vaš
črkovalnik super hitro,

290
00:15:25,170 --> 00:15:27,620
Jaz bi definitivno
poglej v eno od teh.

291
00:15:27,620 --> 00:15:32,390
>> Vendar pa obstajajo tudi
preprosti tisti, kot compute

292
00:15:32,390 --> 00:15:39,010
vsota besed, kot
vsaka črka ima številko.

293
00:15:39,010 --> 00:15:39,940
Izračunajte vsoto.

294
00:15:39,940 --> 00:15:42,230
Ki določa vedro.

295
00:15:42,230 --> 00:15:45,430
Imajo tudi enostavno tisti, ki
so tako kot vse je tukaj,

296
00:15:45,430 --> 00:15:47,050
vse B je tukaj.

297
00:15:47,050 --> 00:15:48,920
Koli od teh.

298
00:15:48,920 --> 00:15:55,770
>> V bistvu, to samo ti pove, katere
matrika indeks vaše element mora iti v.

299
00:15:55,770 --> 00:15:58,690
Samo odločanju o bucket--
to je vse razpršilna funkcija je.

300
00:15:58,690 --> 00:16:04,180
Torej, tu imamo primer, ki je
Samo prvo črko niza

301
00:16:04,180 --> 00:16:05,900
da sem pravkar govoril.

302
00:16:05,900 --> 00:16:11,900
>> Torej imate nekaj hash, ki je pravkar
prva črka vašega godalni minus A,

303
00:16:11,900 --> 00:16:16,090
ki vam bo dala nekaj
število med 0 in 25.

304
00:16:16,090 --> 00:16:20,790
In tisto, kar želite storiti, je
poskrbite, da to predstavlja

305
00:16:20,790 --> 00:16:24,110
velikost vašega hash table--
koliko vedra obstajajo.

306
00:16:24,110 --> 00:16:25,860
Z mnogimi od teh
zgoščevalne funkcije, oni

307
00:16:25,860 --> 00:16:31,630
dogaja se vrača vrednosti, ki bi lahko
biti daleč nad številom žlice

308
00:16:31,630 --> 00:16:33,610
da ste dejansko imajo
V vašem hash tabele,

309
00:16:33,610 --> 00:16:37,240
tako da boste morali, da bi
prepričani, in mod tisti.

310
00:16:37,240 --> 00:16:42,190
Sicer pa je reči,
oh, bi moralo biti v vedru 5000

311
00:16:42,190 --> 00:16:46,040
vendar imate le 30
vedra v vašem hash tabelo.

312
00:16:46,040 --> 00:16:49,360
In seveda, vsi vemo, da je
bo povzročilo nekaj norega napak.

313
00:16:49,360 --> 00:16:52,870
Zato poskrbite, da mod, ki ga
velikost vašega hash tabele.

314
00:16:52,870 --> 00:16:58,430

315
00:16:58,430 --> 00:16:58,930
Cool.

316
00:16:58,930 --> 00:17:00,506
Torej trčenj.

317
00:17:00,506 --> 00:17:02,620
So vsi dobro, tako daleč?

318
00:17:02,620 --> 00:17:03,120
Mmhmm?

319
00:17:03,120 --> 00:17:05,900
>> OBČINSTVO: Zakaj bi bilo
vrnete tako veliko vrednost?

320
00:17:05,900 --> 00:17:09,210
>> SPEAKER 1: Glede na algoritmu
da vaš hash funkcija uporablja.

321
00:17:09,210 --> 00:17:12,270
Nekateri od njih bodo storili
noro množenje.

322
00:17:12,270 --> 00:17:16,270
In to je vse približno pridobivanje
enakomerna porazdelitev,

323
00:17:16,270 --> 00:17:18,490
da počnejo nekaj res
Včasih noro stvari.

324
00:17:18,490 --> 00:17:20,960
To je vse.

325
00:17:20,960 --> 00:17:22,140
Kaj drugega?

326
00:17:22,140 --> 00:17:22,829
OK.

327
00:17:22,829 --> 00:17:24,480
>> Torej trčenj.

328
00:17:24,480 --> 00:17:29,270
V bistvu, kot sem rekel že prej,
v najboljšem primeru

329
00:17:29,270 --> 00:17:32,040
vsaka bucket sem pogledati v je
dogaja, da imajo eno stvar,

330
00:17:32,040 --> 00:17:34,160
tako da mi ni treba gledati na vse, kajne?

331
00:17:34,160 --> 00:17:37,040
Jaz niti vedel, da je tam, ali pa je
ne, in to je tisto, kar si resnično želimo.

332
00:17:37,040 --> 00:17:43,960
Ampak, če imamo več deset tisoč
podatkovne točke in je nižja od te številke

333
00:17:43,960 --> 00:17:48,700
žlic, bomo imeli
Trki kjer na koncu nekaj

334
00:17:48,700 --> 00:17:54,210
se dogaja, da imajo na koncu leta
bucket, ki že ima element.

335
00:17:54,210 --> 00:17:57,390
>> Torej, vprašanje je, kaj
storimo v tem primeru?

336
00:17:57,390 --> 00:17:58,480
Kaj naj naredimo?

337
00:17:58,480 --> 00:17:59,300
Imamo že nekaj tam?

338
00:17:59,300 --> 00:18:00,060
Ali smo samo vrgel ven?

339
00:18:00,060 --> 00:18:00,700
>> No.

340
00:18:00,700 --> 00:18:01,980
Moramo ohraniti oba.

341
00:18:01,980 --> 00:18:06,400
Torej način, da smo
značilno to, da je kaj?

342
00:18:06,400 --> 00:18:08,400
Kakšna je struktura podatkov
smo pravkar govorili?

343
00:18:08,400 --> 00:18:09,316
OBČINSTVO: Povezan seznam.

344
00:18:09,316 --> 00:18:10,500
SPEAKER 1: povezani seznam.

345
00:18:10,500 --> 00:18:16,640
Torej sedaj, namesto da vsak od teh
vedra le imajo en element,

346
00:18:16,640 --> 00:18:24,020
to se dogaja, da vsebujejo povezan seznam
elementi, ki so zgoščene v njej.

347
00:18:24,020 --> 00:18:27,588
OK, pa vsi nekako dobil to idejo?

348
00:18:27,588 --> 00:18:30,546
Ker nismo mogli imeti niz
ker ne vemo, kako veliko stvari

349
00:18:30,546 --> 00:18:31,730
se bo tam.

350
00:18:31,730 --> 00:18:36,540
Povezani seznam nam omogoča, da
imajo samo točno številko, ki

351
00:18:36,540 --> 00:18:38,465
so zgoščene v tisto vedro, kajne?

352
00:18:38,465 --> 00:18:42,260

353
00:18:42,260 --> 00:18:50,500
>> Torej linearni merilni sistem se
v bistvu je to idea--

354
00:18:50,500 --> 00:18:52,300
to je eden od načinov, da se ukvarjajo z trčenja.

355
00:18:52,300 --> 00:18:58,010
Kaj lahko storite, je, če se v tem
Primer je bil berry zgoščen v 1

356
00:18:58,010 --> 00:19:01,130
in že imamo
nekaj tam, si

357
00:19:01,130 --> 00:19:04,840
nadaljuj, dokler
boste našli prazno režo.

358
00:19:04,840 --> 00:19:06,370
To je eden od načinov za ravnanje z njimi.

359
00:19:06,370 --> 00:19:09,020
Drug način za obravnavanje
da je s tem, kar smo pravkar

360
00:19:09,020 --> 00:19:12,280
called-- povezana
Seznam imenujemo veriženje.

361
00:19:12,280 --> 00:19:20,510
>> Tako da je ta ideja deluje, če
Vaše hash tabela menite

362
00:19:20,510 --> 00:19:24,150
je veliko večja od
vaš nabor podatkov ali če vas

363
00:19:24,150 --> 00:19:28,870
želeli poskusiti in zmanjšati verižni
dokler je to nujno potrebno.

364
00:19:28,870 --> 00:19:34,050
Torej, ena stvar je linearna
sondiranje seveda pomeni,

365
00:19:34,050 --> 00:19:37,290
da vaš hash funkcijo
ni tako koristno

366
00:19:37,290 --> 00:19:42,200
ker boste na koncu z uporabo
Vaše hash funkcijo, dobili do točke,

367
00:19:42,200 --> 00:19:46,400
ste linearna sonda navzdol
nekem kraju, ki je na voljo.

368
00:19:46,400 --> 00:19:49,670
Toda zdaj, seveda, kaj
drugega, ki se konča tam,

369
00:19:49,670 --> 00:19:52,050
boste morali
iskanje še navzdol.

370
00:19:52,050 --> 00:19:55,650
>> In tam je veliko več
Odhodki za iskanje, da

371
00:19:55,650 --> 00:19:59,820
gre v vnesla element
v hash tabelo zdaj, kajne?

372
00:19:59,820 --> 00:20:05,640
In zdaj, ko greš in poskusite najti
berry spet ste tekoč, da ga hash,

373
00:20:05,640 --> 00:20:07,742
in to se dogaja, da se reči,
oh, poglej v vedro 1,

374
00:20:07,742 --> 00:20:09,700
in to ne bo
v vedro 1, tako da ste

375
00:20:09,700 --> 00:20:11,970
bodo morali za prečkanje
Cez teh.

376
00:20:11,970 --> 00:20:17,720
Tako da je včasih koristno,
vendar v večini primerov,

377
00:20:17,720 --> 00:20:22,660
bomo rekli, da
veriženje je tisto, kar želite narediti.

378
00:20:22,660 --> 00:20:25,520
>> Torej, o tem smo govorili že prej.

379
00:20:25,520 --> 00:20:27,812
Imam malo pred sebe.

380
00:20:27,812 --> 00:20:33,560
Vendar veriženje je v bistvu, da
vsak vedro v hash tabelo

381
00:20:33,560 --> 00:20:36,120
je samo povezani seznam.

382
00:20:36,120 --> 00:20:39,660
>> Torej še en način, ali bolj tehnični
način, da razmišljajo o hash tabele

383
00:20:39,660 --> 00:20:44,490
je, da je le niz
povezanih seznamov, ki

384
00:20:44,490 --> 00:20:49,330
Ko pišete slovar
in skušaš ga naložiti,

385
00:20:49,330 --> 00:20:52,070
razmišljam o njem kot
Niz povezanih seznamov

386
00:20:52,070 --> 00:20:54,390
bo veliko lažje
za vas, da se zažene.

387
00:20:54,390 --> 00:20:57,680
>> OBČINSTVO: Torej hash tabela
vnaprej določeno velikost,

388
00:20:57,680 --> 00:20:58,980
kot [neslišno] veder?

389
00:20:58,980 --> 00:20:59,220
>> SPEAKER 1: Right.

390
00:20:59,220 --> 00:21:01,655
Torej ima določeno število
vedra, ki jih determine--

391
00:21:01,655 --> 00:21:03,530
ki vidva naj
vas prosimo, da igrajo z.

392
00:21:03,530 --> 00:21:05,269
To je lahko precej kul
da vidite, kaj se zgodi,

393
00:21:05,269 --> 00:21:06,810
kot ste spremenili svoje število segmentov.

394
00:21:06,810 --> 00:21:09,410

395
00:21:09,410 --> 00:21:11,510
Ampak ja, to je
nastavite število veder.

396
00:21:11,510 --> 00:21:15,360
Kaj vam omogoča, da se prilega kot
veliko elementov, kot jih potrebujete

397
00:21:15,360 --> 00:21:19,350
je to ločen veriženje, kjer vas
so povezane sezname v posamezne segmente.

398
00:21:19,350 --> 00:21:22,850
To pomeni, da si razpršene tabele
bo točno velikost

399
00:21:22,850 --> 00:21:25,440
da jo je treba, kajne?

400
00:21:25,440 --> 00:21:27,358
To je bistvo, povezanih seznamov.

401
00:21:27,358 --> 00:21:30,850

402
00:21:30,850 --> 00:21:32,480
Cool.

403
00:21:32,480 --> 00:21:38,780
>> Tako da vsakdo tam OK?

404
00:21:38,780 --> 00:21:39,801
Vse je v redu.

405
00:21:39,801 --> 00:21:40,300
Ah.

406
00:21:40,300 --> 00:21:41,860
Kaj se je zgodilo?

407
00:21:41,860 --> 00:21:42,960
Res zdaj.

408
00:21:42,960 --> 00:21:45,250
Ugani, kdo me ubija.

409
00:21:45,250 --> 00:21:52,060
>> OK bomo šli v
poskusih, ki so malo nori.

410
00:21:52,060 --> 00:21:53,140
Všeč mi je hash tabele.

411
00:21:53,140 --> 00:21:54,460
Mislim, da so res kul.

412
00:21:54,460 --> 00:21:56,710
Poskuša so kul, preveč.

413
00:21:56,710 --> 00:21:59,590
>> Torej, ali kdo se spomnite, kaj je poskusiti?

414
00:21:59,590 --> 00:22:01,740
Moral bi šla čez
je na kratko predavanje?

415
00:22:01,740 --> 00:22:04,570

416
00:22:04,570 --> 00:22:06,377
Se spomnite vrste, kako to deluje?

417
00:22:06,377 --> 00:22:08,460
OBČINSTVO: Jaz sem samo prikimava
da nismo šel skozi njo.

418
00:22:08,460 --> 00:22:09,626
SPEAKER 1: Mi ne gredo nad njim.

419
00:22:09,626 --> 00:22:13,100
OK, smo res šli
nad njim, zdaj je tisto, kar govoriš.

420
00:22:13,100 --> 00:22:14,860
>> OBČINSTVO: To je za arhiviranje drevo.

421
00:22:14,860 --> 00:22:15,280
>> SPEAKER 1: Ja.

422
00:22:15,280 --> 00:22:16,196
To je iskanje drevo.

423
00:22:16,196 --> 00:22:16,960
Super.

424
00:22:16,960 --> 00:22:23,610
Torej, ena stvar, ki sem opazil je, da smo
iščete na posameznih znakov

425
00:22:23,610 --> 00:22:24,480
tukaj, kajne?

426
00:22:24,480 --> 00:22:29,710
>> Torej, preden se z našo hash funkcijo, smo
iskali na besede kot celote,

427
00:22:29,710 --> 00:22:32,270
in zdaj iščemo več
na znake, kajne?

428
00:22:32,270 --> 00:22:38,380
Torej imamo Maxwell sem in Mendel.

429
00:22:38,380 --> 00:22:47,840
Torej v bistvu try-- način, da razmišljajo
pri tem je, da je vsak nivo tukaj

430
00:22:47,840 --> 00:22:49,000
je niz črk.

431
00:22:49,000 --> 00:22:53,310

432
00:22:53,310 --> 00:22:55,790
Torej je to tvoj koren node tukaj, kajne?

433
00:22:55,790 --> 00:23:01,980
Ta ima vse znake
abeceda za začetek vsako besedo.

434
00:23:01,980 --> 00:23:06,480
>> In tisto, kar želite storiti, je
recimo, OK, imamo nekaj M besedo.

435
00:23:06,480 --> 00:23:10,590
Bomo iskali Maxwell, zato
gremo na M. in M ​​točke na celoten

436
00:23:10,590 --> 00:23:14,800
drugi niz, kjer je vsak
beseda, dokler obstaja

437
00:23:14,800 --> 00:23:17,044
je beseda, ki ima
kot drugo pismo,

438
00:23:17,044 --> 00:23:19,460
Dokler obstaja beseda, ki
ima B kot drugo pismo,

439
00:23:19,460 --> 00:23:24,630
da bo imela kazalec
bo za nekatere naslednjo paleto.

440
00:23:24,630 --> 00:23:29,290
>> Verjetno ne
beseda, ki MP nekaj,

441
00:23:29,290 --> 00:23:32,980
tako v P pozicijo v to
matrika, bi bilo prav, je nična.

442
00:23:32,980 --> 00:23:38,840
Bilo bi rekli, v redu, ni beseda
da je M sledi P, OK?

443
00:23:38,840 --> 00:23:43,100
Torej, če razmišljamo o tem, vsak
eden od teh manjših stvari

444
00:23:43,100 --> 00:23:47,990
je dejansko eden od teh
velike nize od A do Ž

445
00:23:47,990 --> 00:23:55,064
Torej, kaj lahko ena od stvari,
da je nekako povračila poskusiti?

446
00:23:55,064 --> 00:23:56,500
>> OBČINSTVO: veliko spomina.

447
00:23:56,500 --> 00:23:59,940
>> SPEAKER 1: To je ton spomina, kajne?

448
00:23:59,940 --> 00:24:08,750
Vsak od teh blokov tukaj
predstavlja 26 mest, 26 elementov array.

449
00:24:08,750 --> 00:24:13,680
Tako poskuša priti neverjetno prostor težka.

450
00:24:13,680 --> 00:24:17,100
>> Ampak oni so zelo hitro.

451
00:24:17,100 --> 00:24:22,540
Tako zelo hitro, vendar
res prostor neučinkovito.

452
00:24:22,540 --> 00:24:24,810
Nekako morali ugotoviti
, katero želite.

453
00:24:24,810 --> 00:24:29,470
To so res kul za vaš pset,
vendar pa traja veliko pomnilnika,

454
00:24:29,470 --> 00:24:30,290
tako da kompromis.

455
00:24:30,290 --> 00:24:31,480
Ja?

456
00:24:31,480 --> 00:24:34,300
>> OBČINSTVO: Ali bi bilo mogoče
da ustanovi poskusiti in potem

457
00:24:34,300 --> 00:24:37,967
ko imate vse
Podatki v to, da ste need--

458
00:24:37,967 --> 00:24:39,550
Ne vem, če bi bilo to smiselno.

459
00:24:39,550 --> 00:24:42,200
Sem se znebi vseh
NULL znakov, vendar se je nato

460
00:24:42,200 --> 00:24:42,910
si ne bi mogli indeks them--

461
00:24:42,910 --> 00:24:43,275
>> SPEAKER 1: Še vedno jih potrebujete.

462
00:24:43,275 --> 00:24:44,854
>> OBČINSTVO: - enak način vsak čas.

463
00:24:44,854 --> 00:24:45,520
SPEAKER 1: Ja.

464
00:24:45,520 --> 00:24:50,460
Potrebujete znaka NULL, da naj
veš, če tam ni beseda tam.

465
00:24:50,460 --> 00:24:52,040
Ben si imel kaj želite?

466
00:24:52,040 --> 00:24:52,540
OK.

467
00:24:52,540 --> 00:24:54,581
Vse je v redu, tako da bomo
iti malo bolj

468
00:24:54,581 --> 00:24:58,920
v tehnične podrobnosti izza
poskusite in delo s primerom.

469
00:24:58,920 --> 00:25:01,490
>> OK, tako da je to ista stvar.

470
00:25:01,490 --> 00:25:06,290
Ker se v povezani seznam, naša glavna
vrsta of-- kaj beseda želim? -

471
00:25:06,290 --> 00:25:08,350
kot gradnik je vozlišče.

472
00:25:08,350 --> 00:25:12,280
V poskusu, imamo tudi vozlišče,
vendar pa je to drugače opredeliti.

473
00:25:12,280 --> 00:25:17,000
>> Torej imamo nekaj bool da
predstavlja ali besede dejansko

474
00:25:17,000 --> 00:25:23,530
obstaja na tej lokaciji, in nato
imamo nekaj paleto here-- ali ne,

475
00:25:23,530 --> 00:25:27,840
To je kazalec
niz 27 znakov.

476
00:25:27,840 --> 00:25:33,339
In to je, v tem primeru je to
27-- Prepričan sem, da ste vsi podobni, počakajte,

477
00:25:33,339 --> 00:25:34,880
obstaja 26 črk v abecedi.

478
00:25:34,880 --> 00:25:36,010
Zakaj imamo 27?

479
00:25:36,010 --> 00:25:37,870
>> Torej, odvisno
način izvajati to,

480
00:25:37,870 --> 00:25:43,240
to je od pset da
dovoljeno za opuščaj.

481
00:25:43,240 --> 00:25:46,010
Torej, to je, zakaj extra ena.

482
00:25:46,010 --> 00:25:50,500
Prav tako boste imeli v nekaterih
primeri null terminator

483
00:25:50,500 --> 00:25:53,230
je kot eden od
Znaki, da je to dovoljeno,

484
00:25:53,230 --> 00:25:56,120
in to je, kako preveriti,
vidim, če je konec besedi.

485
00:25:56,120 --> 00:26:01,340
Če vas zanima, si oglejte
Video Kevinova na study.cs50,

486
00:26:01,340 --> 00:26:04,790
kakor tudi poka Wikipedija
nekaj dobrih virov tam.

487
00:26:04,790 --> 00:26:09,000
>> Vendar smo šli skozi le nekako
o tem, kako lahko sodelujete prek poskusu

488
00:26:09,000 --> 00:26:11,010
če si dal enega.

489
00:26:11,010 --> 00:26:16,230
Tako da imamo super preprosto enega tukaj, da
ima besede "kij" in "zoom" v njih.

490
00:26:16,230 --> 00:26:18,920
In kot smo videli tu gor,
ta mali prostor tukaj

491
00:26:18,920 --> 00:26:22,560
predstavlja našo bool da
pravi, ja, to je beseda.

492
00:26:22,560 --> 00:26:27,060
In potem je to naša
nizi znakov, kajne?

493
00:26:27,060 --> 00:26:33,480
>> Tako smo šli skozi
iskanje "bat" v tem poskusu.

494
00:26:33,480 --> 00:26:38,340
Torej, začeti na vrhu, kajne?

495
00:26:38,340 --> 00:26:46,290
In vemo, da b ustreza
Drugi indeks, drugi element

496
00:26:46,290 --> 00:26:47,840
v tem polju, ker in b.

497
00:26:47,840 --> 00:26:51,340
Torej približno druga.

498
00:26:51,340 --> 00:26:58,820
>> In pravi, OK, kul, upoštevajte, da v
Naslednja matrika, saj če se spomnimo,

499
00:26:58,820 --> 00:27:02,160
to ni, da je vsak od teh
dejansko vsebuje element.

500
00:27:02,160 --> 00:27:07,110
Vsak od teh nizov
vsebuje kazalec, kajne?

501
00:27:07,110 --> 00:27:10,030
To je pomembna razlika, da bi.

502
00:27:10,030 --> 00:27:13,450
>> Vem, da se to dogaja, da be-- poskusih so
res težko priti na prvo,

503
00:27:13,450 --> 00:27:15,241
tako da tudi če je to
drugič ali tretjič

504
00:27:15,241 --> 00:27:18,370
in je še vedno nekako
od zdelo težko,

505
00:27:18,370 --> 00:27:21,199
Obljubim, da če greš uro
Skratka spet jutri,

506
00:27:21,199 --> 00:27:22,740
da bomo verjetno lahko veliko bolj smiselno.

507
00:27:22,740 --> 00:27:23,890
Je potrebno veliko za prebaviti.

508
00:27:23,890 --> 00:27:27,800
Še vedno včasih sem
podobno, čakaj, kaj je poskusiti?

509
00:27:27,800 --> 00:27:29,080
Kako naj uporabljam to?

510
00:27:29,080 --> 00:27:33,880
>> Tako smo b v tem primeru,
ki je naš drugi indeks.

511
00:27:33,880 --> 00:27:40,240
Če bi imeli, recimo, c ali
d ali katera koli druga črka,

512
00:27:40,240 --> 00:27:45,810
moramo načrtovati, da se nazaj na kazalo
našega polja, ki ustreza.

513
00:27:45,810 --> 00:27:56,930
Torej bi vzamemo kot rchar in smo pravkar
odštejte off, da ga map v 0 do 25.

514
00:27:56,930 --> 00:27:58,728
Vsi so dobri, kako smo
map naše znakov?

515
00:27:58,728 --> 00:28:00,440
OK.

516
00:28:00,440 --> 00:28:05,980
>> Torej, gremo na drugo eno in mi
vidim, ja, da ne bi nič.

517
00:28:05,980 --> 00:28:07,780
Mi lahko premaknete na to naslednjo paleto.

518
00:28:07,780 --> 00:28:12,300
Torej gremo na to naslednje matrike tukaj.

519
00:28:12,300 --> 00:28:15,500
>> In smo rekli, v redu, zdaj smo
videti, če je tukaj.

520
00:28:15,500 --> 00:28:18,590
Je nična ali ne
dejansko korak naprej?

521
00:28:18,590 --> 00:28:21,880
Torej dejansko premika
naj v ta sklop.

522
00:28:21,880 --> 00:28:24,570
In smo rekli, v redu, t je naša zadnja črka.

523
00:28:24,570 --> 00:28:27,580
Torej gremo na t na indeks.

524
00:28:27,580 --> 00:28:30,120
In potem smo korak naprej
zato, ker je še eden.

525
00:28:30,120 --> 00:28:38,340
In ta pravi, da v bistvu, ja,
pa pravi, da je beseda here--

526
00:28:38,340 --> 00:28:41,750
da če boste sledili tem
Pot, ki ste prišli

527
00:28:41,750 --> 00:28:43,210
na besedo, kar vemo, je "bat".

528
00:28:43,210 --> 00:28:43,800
Ja?

529
00:28:43,800 --> 00:28:46,770
>> OBČINSTVO: Ali je standardna, da ima to
kot indeks 0 in nato še neke vrste na 1

530
00:28:46,770 --> 00:28:47,660
ali da imajo na koncu?

531
00:28:47,660 --> 00:28:48,243
>> SPEAKER 1: No.

532
00:28:48,243 --> 00:28:55,360
Torej, če se ozremo na naše
Izjava tukaj, to je bool,

533
00:28:55,360 --> 00:28:59,490
tako da je sama element v vozlišču.

534
00:28:59,490 --> 00:29:03,331
Tako da to ni del niza.

535
00:29:03,331 --> 00:29:03,830
Cool.

536
00:29:03,830 --> 00:29:08,370
Torej, ko smo končali našo besedo in smo
na tem polju, kaj želimo narediti

537
00:29:08,370 --> 00:29:12,807
je storiti, ček za to besedo.

538
00:29:12,807 --> 00:29:14,390
In v tem primeru bi se vrnil ja.

539
00:29:14,390 --> 00:29:17,220

540
00:29:17,220 --> 00:29:24,090
>> Torej na to opombo, vemo, da je "živalski vrt" -
vemo, saj ljudje, da je "zoo" beseda,

541
00:29:24,090 --> 00:29:24,820
kajne?

542
00:29:24,820 --> 00:29:28,990
Vendar poskusite tukaj bi
pravijo, ne, to ni.

543
00:29:28,990 --> 00:29:33,980
In bi rekel, da zato, ker mi
ga niso določena kot beseda tukaj.

544
00:29:33,980 --> 00:29:40,440
Čeprav smo lahko preide
skozi ta sklop,

545
00:29:40,440 --> 00:29:43,890
Ta poskus bi rekel, da ne,
zoo ni v slovarju

546
00:29:43,890 --> 00:29:47,070
saj imamo ne
jo označeni kot taki.

547
00:29:47,070 --> 00:29:52,870
>> Torej en način, da to that--
oh, oprosti, tale.

548
00:29:52,870 --> 00:29:59,450
Torej, v tem primeru, "zoo" ni
beseda, vendar je v našem poskusu.

549
00:29:59,450 --> 00:30:05,690
Toda v ta, da smo ga želeli
uvesti besedo "kopel", kaj se zgodi

550
00:30:05,690 --> 00:30:08,260
je sledimo through-- b, a, t.

551
00:30:08,260 --> 00:30:11,820
Mi smo v tem polju, in
gremo iskati h.

552
00:30:11,820 --> 00:30:15,220
>> V tem primeru, ko smo
poglej kazalec na uri,

553
00:30:15,220 --> 00:30:17,890
to je obrnjena na NULL, OK?

554
00:30:17,890 --> 00:30:20,780
Torej, če je to izrecno
kaže na drugi matriki,

555
00:30:20,780 --> 00:30:25,000
predpostavimo, da so vsi kazalci
V tem polju se kaže na null.

556
00:30:25,000 --> 00:30:28,270
Torej, v tem primeru, h se kaže
na nič, tako da ne moremo storiti ničesar,

557
00:30:28,270 --> 00:30:31,540
tako da bi bilo tudi vrniti
false, "kopel" ni tukaj.

558
00:30:31,540 --> 00:30:34,102

559
00:30:34,102 --> 00:30:35,810
Torej, zdaj smo dejansko
bo šel skozi

560
00:30:35,810 --> 00:30:39,790
kako bomo dejansko rekli,
da "zoo" je v našem poskusu.

561
00:30:39,790 --> 00:30:42,920
Kako vstaviti "živalski vrt", v našem poskusu?

562
00:30:42,920 --> 00:30:47,810
Torej, na enak način, da smo začeli z
naš povezani seznam, začnemo v korenu.

563
00:30:47,810 --> 00:30:50,600
Če ste v dvomih, začnite pri
koren od teh stvari.

564
00:30:50,600 --> 00:30:53,330
>> In bomo rekli, v redu, z.

565
00:30:53,330 --> 00:30:55,650
obstaja z, v tem, in to počne.

566
00:30:55,650 --> 00:30:58,370
Torej ste se gibljejo na
vaš naslednji niz, v redu?

567
00:30:58,370 --> 00:31:01,482
In nato na naslednjo,
smo rekli, v redu, ne o obstaja?

568
00:31:01,482 --> 00:31:03,000
To počne.

569
00:31:03,000 --> 00:31:04,330
To še enkrat.

570
00:31:04,330 --> 00:31:08,670
>> In tako na našem naslednjem enega, smo rekel,
OK, "zoo" že tu obstaja.

571
00:31:08,670 --> 00:31:12,440
Vse, kar moramo storiti, je nastaviti ta enaka
da velja, da je beseda tam.

572
00:31:12,440 --> 00:31:15,260
Če bi sledili vse
do prej navedene točke

573
00:31:15,260 --> 00:31:17,030
to je beseda, tako da samo
nastavljen je enak kot.

574
00:31:17,030 --> 00:31:17,530
Ja?

575
00:31:17,530 --> 00:31:22,550
>> OBČINSTVO: Torej ne, da
pomeni, da je "ba" beseda tudi?

576
00:31:22,550 --> 00:31:24,120
>> SPEAKER 1: No.

577
00:31:24,120 --> 00:31:28,870
Torej, v tem primeru, "ba" bomo dobili
tukaj, bi lahko rekli, je to beseda,

578
00:31:28,870 --> 00:31:31,590
in bi bilo še vedno ni.

579
00:31:31,590 --> 00:31:32,822
OK?

580
00:31:32,822 --> 00:31:33,740
Mmhmm?

581
00:31:33,740 --> 00:31:36,360
>> OBČINSTVO: Torej, ko si je
beseda in rečeš da, potem je

582
00:31:36,360 --> 00:31:38,380
vsebuje iti m?

583
00:31:38,380 --> 00:31:42,260
>> SPEAKER 1: Torej, to mora storiti
with-- ste nalaganju to.

584
00:31:42,260 --> 00:31:43,640
Rečeš "zoo" je beseda.

585
00:31:43,640 --> 00:31:47,020
Ko greš na check--
kot, da ste želeli povedati,

586
00:31:47,020 --> 00:31:49,400
pomeni "zoo" obstajajo v tem slovarju?

587
00:31:49,400 --> 00:31:54,200
Si le, da bo iskanje za "živalski vrt"
nato pa preverite, če je beseda.

588
00:31:54,200 --> 00:31:57,291
Si ne bo premaknil
do m, ker to ni

589
00:31:57,291 --> 00:31:58,290
tisto, kar iščete.

590
00:31:58,290 --> 00:32:02,690

591
00:32:02,690 --> 00:32:08,070
>> Torej, če bi dejansko želeli
dodati "kopel" v tem poskusu,

592
00:32:08,070 --> 00:32:11,390
mi bi naredil isto stvar
kot smo to storili z "živalski vrt"

593
00:32:11,390 --> 00:32:15,380
razen da bomo videli, ko bomo
poskusiti in priti do h, da ne obstaja.

594
00:32:15,380 --> 00:32:20,090
Torej si lahko zamislite, da je to težaven
dodati novo vozlišče v povezani seznam,

595
00:32:20,090 --> 00:32:27,210
zato bi morali dodati še eno
eden od teh nizi, kot tako.

596
00:32:27,210 --> 00:32:35,670
In potem, kaj mi je pravkar nastavili h
element te matrike, ki kažejo na to.

597
00:32:35,670 --> 00:32:39,430
>> In potem, kaj bi želeli narediti tukaj?

598
00:32:39,430 --> 00:32:43,110
Dodajte je enaka true
ker je beseda.

599
00:32:43,110 --> 00:32:46,350

600
00:32:46,350 --> 00:32:48,150
Cool.

601
00:32:48,150 --> 00:32:48,700
Vem.

602
00:32:48,700 --> 00:32:51,170
Poskuša niso najbolj razburljivo.

603
00:32:51,170 --> 00:32:54,250
Verjemi mi, vem.

604
00:32:54,250 --> 00:32:58,040
>> Torej, ena stvar, za uresničitev s poskusih
Rekel sem, oni so zelo učinkoviti.

605
00:32:58,040 --> 00:33:00,080
Tako smo videli
prevzamejo tono prostora.

606
00:33:00,080 --> 00:33:01,370
Oni nekako zmedeno.

607
00:33:01,370 --> 00:33:03,367
Torej, zakaj bi si kdaj uporabiti to?

608
00:33:03,367 --> 00:33:05,450
Uporabljamo jih zato, ker oni
neverjetno učinkovit.

609
00:33:05,450 --> 00:33:08,130
>> Torej, če ste že kdaj iskali
do besede, ste le

610
00:33:08,130 --> 00:33:10,450
omejena z dolžino besede.

611
00:33:10,450 --> 00:33:15,210
Torej, če iščete
Beseda, ki je dolga pet,

612
00:33:15,210 --> 00:33:20,940
ste le kdaj bodo morali
da največ petih primerjavah, OK?

613
00:33:20,940 --> 00:33:25,780
Tako da si lahko v bistvu konstantna.

614
00:33:25,780 --> 00:33:29,150
Like vstavljanja in lookup
so v bistvu konstantna čas.

615
00:33:29,150 --> 00:33:33,750
>> Torej, če lahko kdaj
nekaj v stalnem času,

616
00:33:33,750 --> 00:33:35,150
da je tako dober, kot je dobil.

617
00:33:35,150 --> 00:33:37,990
Ne morete dobiti boljše od
stalen čas za te stvari.

618
00:33:37,990 --> 00:33:43,150
Tako, da je ena izmed
ogromne pluse poskuša.

619
00:33:43,150 --> 00:33:46,780
>> Vendar je veliko prostora.

620
00:33:46,780 --> 00:33:50,380
Tako da boste nekako morali odločiti,
kaj je bolj pomembno za vas.

621
00:33:50,380 --> 00:33:54,700
In na današnjih računalnikih,
Prostor, ki je lahko poskus traja

622
00:33:54,700 --> 00:33:57,740
Mogoče ne vpliva
ste, da je veliko, ampak morda

623
00:33:57,740 --> 00:34:01,350
imate opravka z nečim
da ima veliko, veliko več stvari,

624
00:34:01,350 --> 00:34:02,810
in poskus samo ni smiselno.

625
00:34:02,810 --> 00:34:03,000
Ja?

626
00:34:03,000 --> 00:34:05,610
>> OBČINSTVO: Počakajte, da imate 26
Črke v vsak posameznik?

627
00:34:05,610 --> 00:34:07,440
>> SPEAKER 1: mmhmm.

628
00:34:07,440 --> 00:34:08,570
Ja, imate 26.

629
00:34:08,570 --> 00:34:16,984
Imate nekaj je beseda dvojno podajo, nato pa
imate 26 kazalcev v vsaki eno.

630
00:34:16,984 --> 00:34:17,775
In oni point--

631
00:34:17,775 --> 00:34:20,280
>> OBČINSTVO: In vsak 26,
pa imajo vsak 26?

632
00:34:20,280 --> 00:34:21,500
>> SPEAKER 1: Da.

633
00:34:21,500 --> 00:34:27,460
In zato, kot si lahko
glej, se širi zelo hitro.

634
00:34:27,460 --> 00:34:28,130
Vse je v redu.

635
00:34:28,130 --> 00:34:32,524
Tako bomo dobili v drevesih, ki
Počutim se, kot je lažje in bo verjetno

636
00:34:32,524 --> 00:34:36,150
biti lepo Oddih
od poskusih se.

637
00:34:36,150 --> 00:34:39,620
Zato upajmo, da večina od vas
Videl drevo prej.

638
00:34:39,620 --> 00:34:41,820
Ni všeč lepa
tisti zunaj, ki sem

639
00:34:41,820 --> 00:34:44,340
Ne vem, če je kdo
šli na prostem v zadnjem času.

640
00:34:44,340 --> 00:34:49,230
Šel sem pobiral jabolka ta vikend,
in oh moj bog, bilo je lepo.

641
00:34:49,230 --> 00:34:52,250
Nisem vedel, listje
mogoče videti, da je lepa.

642
00:34:52,250 --> 00:34:53,610
>> Torej je to samo drevo, kajne?

643
00:34:53,610 --> 00:34:56,790
To je samo nekaj vozlišč, in
opozarja na kup drugih vozlišč.

644
00:34:56,790 --> 00:34:59,570
Kot vidite tukaj, je to
nekakšna stalnica.

645
00:34:59,570 --> 00:35:03,720
Vozlišča, ki kaže, da vozlišča je nekako
Bistvo številnih podatkovnih struktur.

646
00:35:03,720 --> 00:35:06,670
To je odvisno samo od tega, kako smo
imajo jih opozarjajo na medsebojno

647
00:35:06,670 --> 00:35:08,600
in kako prečkanje
skoznje in kako smo

648
00:35:08,600 --> 00:35:14,500
vstavite stvari, ki določa,
njihove različne značilnosti.

649
00:35:14,500 --> 00:35:17,600
>> Torej samo nekaj terminologije,
ki sem jih prej.

650
00:35:17,600 --> 00:35:20,010
Torej koren je vse, kar je v samem vrhu.

651
00:35:20,010 --> 00:35:21,200
to je, kjer smo se vedno začne.

652
00:35:21,200 --> 00:35:23,610
Lahko si o njej mislijo kot vodja tudi.

653
00:35:23,610 --> 00:35:28,750
Ampak na drevesih, smo nagnjeni k
nanašajo na to kot root.

654
00:35:28,750 --> 00:35:32,820
>> Karkoli na spodnjem here--
na zelo, zelo bottom--

655
00:35:32,820 --> 00:35:34,500
so menili listi.

656
00:35:34,500 --> 00:35:37,210
Torej gre skupaj z
Celotna drevo stvar, kajne?

657
00:35:37,210 --> 00:35:39,860
Listi so na robovih drevo.

658
00:35:39,860 --> 00:35:45,820
>> In potem imamo tudi nekaj
Pogoji govoriti o vozliščih v zvezi

659
00:35:45,820 --> 00:35:46,680
seboj.

660
00:35:46,680 --> 00:35:49,700
Tako da imamo starše,
otroci, bratje in sestre.

661
00:35:49,700 --> 00:35:56,260
Torej v tem primeru 3 je
matično 5, 6 in 7.

662
00:35:56,260 --> 00:36:00,370
Tako staršev, kar je
en korak nad karkoli vas zanima

663
00:36:00,370 --> 00:36:02,940
sklicevanjem, tako da samo
kot družinsko drevo.

664
00:36:02,940 --> 00:36:07,090
Upajmo, da je to vse malo
bit bolj intuitiven kot poskusih.

665
00:36:07,090 --> 00:36:10,970
>> Bratje in sestre so vse, ki imajo
isti nadrejeni, kajne?

666
00:36:10,970 --> 00:36:13,470
Oni so na istem nivoju tukaj.

667
00:36:13,470 --> 00:36:16,960
In potem, ko sem bil
rekel, otroci so samo

668
00:36:16,960 --> 00:36:22,630
kar je en korak pod
vozlišče v vprašanju, OK?

669
00:36:22,630 --> 00:36:23,470
Cool.

670
00:36:23,470 --> 00:36:25,610
Torej, binarno drevo.

671
00:36:25,610 --> 00:36:31,450
Lahko vsakdo nevarnost ugibati na enem od
značilnosti binarnega drevesa?

672
00:36:31,450 --> 00:36:32,770
>> OBČINSTVO: Max dva lista.

673
00:36:32,770 --> 00:36:33,478
>> SPEAKER 1: Right.

674
00:36:33,478 --> 00:36:34,640
Torej max dveh listov.

675
00:36:34,640 --> 00:36:39,730
Torej, v tem enem poprej smo imeli tole
da je imel tri, ampak v binarnem drevesu

676
00:36:39,730 --> 00:36:45,000
imate max dveh
otrok na starša, kajne?

677
00:36:45,000 --> 00:36:46,970
Še en
zanimivo lastnost.

678
00:36:46,970 --> 00:36:51,550
Ali kdo ve za to?

679
00:36:51,550 --> 00:36:52,620
Dvojiško drevo.

680
00:36:52,620 --> 00:37:00,350
>> Tako da bo binarno drevo ima vse
na the-- ta ni sorted--

681
00:37:00,350 --> 00:37:05,320
vendar v sortirano binarno drevo,
vse, kar je na desni strani

682
00:37:05,320 --> 00:37:08,530
večja od staršev,
in vse na levi

683
00:37:08,530 --> 00:37:10,035
je manj od staršev.

684
00:37:10,035 --> 00:37:15,690
In da je bil kviz
Vprašanje prej, tako da dobro vedeti.

685
00:37:15,690 --> 00:37:19,500
Torej način opredeljuje,
spet imamo eno vozlišče.

686
00:37:19,500 --> 00:37:21,880
To izgleda zelo podobno kot kaj?

687
00:37:21,880 --> 00:37:28,336

688
00:37:28,336 --> 00:37:28,836
Dvakrat

689
00:37:28,836 --> 00:37:29,320
>> Publika: Povezan seznami

690
00:37:29,320 --> 00:37:31,100
>> SPEAKER 1: dvojna povezani seznam, kajne?

691
00:37:31,100 --> 00:37:33,690
Torej, če želimo zamenjati to
s prejšnjo in naslednjo,

692
00:37:33,690 --> 00:37:35,670
to bi bilo dvojno povezani seznam.

693
00:37:35,670 --> 00:37:40,125
Toda v tem primeru smo dejansko
imajo levo in desno in to je to.

694
00:37:40,125 --> 00:37:41,500
Drugače pa je popolnoma enak.

695
00:37:41,500 --> 00:37:43,374
Še vedno imamo element
iščete,

696
00:37:43,374 --> 00:37:45,988
in imate le dve kazalci
dogaja, da karkoli je naslednji.

697
00:37:45,988 --> 00:37:49,210

698
00:37:49,210 --> 00:37:51,870
Ja, tako dvojiško iskalno drevo.

699
00:37:51,870 --> 00:37:57,665
Če opazimo, vse na
tukaj je večja than--

700
00:37:57,665 --> 00:37:59,850
ali takoj vse
da tukaj

701
00:37:59,850 --> 00:38:02,840
je večja od vsega
tu je manj kot.

702
00:38:02,840 --> 00:38:06,980

703
00:38:06,980 --> 00:38:14,000
>> Torej, če bi preiskava skozi to,
bi morali videti zelo blizu binarnega iskanja

704
00:38:14,000 --> 00:38:14,910
tukaj, kajne?

705
00:38:14,910 --> 00:38:17,640
Razen namesto gledanja
na polovici matrike,

706
00:38:17,640 --> 00:38:21,720
smo samo gledaš na bodisi na levo
strani ali na desni strani drevesa.

707
00:38:21,720 --> 00:38:24,850
Tako da dobi malo enostavnejši, mislim.

708
00:38:24,850 --> 00:38:29,300
>> Torej, če je vaš korenski NULL,
Očitno je to samo false.

709
00:38:29,300 --> 00:38:33,470
In če je tam, očitno je res.

710
00:38:33,470 --> 00:38:35,320
Če je manj kot iščemo levo.

711
00:38:35,320 --> 00:38:37,070
Če je več,
iščemo pravico.

712
00:38:37,070 --> 00:38:39,890
To je natanko tako kot binarno iskanje,
samo drugačna struktura podatkov

713
00:38:39,890 --> 00:38:40,600
da smo s pomočjo.

714
00:38:40,600 --> 00:38:42,790
Namesto matrike,
to je samo binarno drevo.

715
00:38:42,790 --> 00:38:45,820

716
00:38:45,820 --> 00:38:48,090
>> OK, nizov.

717
00:38:48,090 --> 00:38:51,550
In tudi, da izgleda, kot da
Morda imajo malo časa.

718
00:38:51,550 --> 00:38:54,460
Če bomo to storili, sem vesel, da gredo
čez vse to še enkrat.

719
00:38:54,460 --> 00:38:56,856
OK, tako nizov.

720
00:38:56,856 --> 00:39:02,695
Ali kdo spomnite kaj stacks--
vse značilnosti dimnika?

721
00:39:02,695 --> 00:39:05,550

722
00:39:05,550 --> 00:39:10,400
>> OK, tako da je večina od nas, mislim,
jesti v jedilnico halls--

723
00:39:10,400 --> 00:39:13,100
toliko, kot morda ne bomo želeli.

724
00:39:13,100 --> 00:39:16,900
Ampak seveda, si lahko zamislite skladovnice
dobesedno le kot skladovnice pladnjev

725
00:39:16,900 --> 00:39:18,460
ali kup stvari.

726
00:39:18,460 --> 00:39:21,820
In kaj je pomembno
zavedati, je, da je

727
00:39:21,820 --> 00:39:26,850
something-- značilnost
da rečemo temu by-- je LIFO.

728
00:39:26,850 --> 00:39:28,450
Ali kdo ve, kaj to pomeni?

729
00:39:28,450 --> 00:39:29,070
Mmhmm?

730
00:39:29,070 --> 00:39:30,650
>> OBČINSTVO: zadnji noter, prvi ven.

731
00:39:30,650 --> 00:39:32,250
>> SPEAKER 1: Right, zadnji noter, prvi ven.

732
00:39:32,250 --> 00:39:36,585
Torej, če vemo, če bomo zlaganje stvari
up, najlažje, da zgrabite off--

733
00:39:36,585 --> 00:39:39,570
in morda edina stvar, ki jo lahko zgrabi
off, če naš dimnik je velik enough--

734
00:39:39,570 --> 00:39:40,850
je, da je zgornji del.

735
00:39:40,850 --> 00:39:43,460
Karkoli je tako dal na
last-- kot vidimo tukaj,

736
00:39:43,460 --> 00:39:46,370
karkoli je potisnilo
na najbolj recently-- je

737
00:39:46,370 --> 00:39:51,160
bo najprej
stvar, ki jo pop off, OK?

738
00:39:51,160 --> 00:39:56,324
>> Torej, kaj imamo tukaj je
drugo typedef struct.

739
00:39:56,324 --> 00:39:58,740
To je res samo všeč
crash seveda v podatkovno strukturo,

740
00:39:58,740 --> 00:40:01,650
tako da je veliko vrže na vas.

741
00:40:01,650 --> 00:40:02,540
Vem.

742
00:40:02,540 --> 00:40:04,970
Torej še en struct.

743
00:40:04,970 --> 00:40:06,740
Bravo struktur.

744
00:40:06,740 --> 00:40:16,660
>> In v tem primeru, to je nekaj pointer
na matriko, ki ima nekaj sposobnosti.

745
00:40:16,660 --> 00:40:20,830
Torej to pomeni našo skladovnico
tukaj, kot naš dejanski matriki

746
00:40:20,830 --> 00:40:22,520
da je gospodarstvo naše elemente.

747
00:40:22,520 --> 00:40:24,850
In potem tukaj imamo nekaj velikosti.

748
00:40:24,850 --> 00:40:31,170
>> In ponavadi, ki jih želite obdržati
tir, kako velik je vaš dimnik

749
00:40:31,170 --> 00:40:36,180
kajti to, kar se dogaja, da se omogoči
vi storiti je, če veš, velikost,

750
00:40:36,180 --> 00:40:39,170
vam omogoča, da reči,
OK, sem na zmogljivosti?

751
00:40:39,170 --> 00:40:40,570
Lahko dodam še kaj?

752
00:40:40,570 --> 00:40:44,650
In to vam pove tudi,
kjer je vrh vaših žetonov

753
00:40:44,650 --> 00:40:48,180
je, tako da boste vedeli, kaj vas
lahko dejansko vzlet.

754
00:40:48,180 --> 00:40:51,760
In to dejansko dogaja, da
biti malo bolj jasno tukaj.

755
00:40:51,760 --> 00:40:57,350
>> Torej Pritisni, eno stvar, če vas
bili kdaj izvajati potiskanje,

756
00:40:57,350 --> 00:41:01,330
kot sem pravkar rekel, tvoja
Sveženj ima omejeno velikost, kajne?

757
00:41:01,330 --> 00:41:03,990
Naša paleta imela nekaj zmogljivosti.

758
00:41:03,990 --> 00:41:04,910
To je niz.

759
00:41:04,910 --> 00:41:08,930
To je fiksna velikost, zato moramo
se prepričajte, da smo ne daje več

760
00:41:08,930 --> 00:41:11,950
v našo paleto, kot smo
dejansko imajo prostor.

761
00:41:11,950 --> 00:41:16,900
>> Torej, če ste ustvarjanju potiskanje
funkcija, prva stvar, kar morate storiti je reči, OK,

762
00:41:16,900 --> 00:41:18,570
imam prostor v mojem kupu?

763
00:41:18,570 --> 00:41:23,330
Ker če jaz ne, žal,
Ne morem shraniti element.

764
00:41:23,330 --> 00:41:28,980
Če bi to storili, potem želite shraniti
je na vrhu kupa, prav?

765
00:41:28,980 --> 00:41:31,325
>> In zato imamo
spremljate naše velikosti.

766
00:41:31,325 --> 00:41:35,290
Če ne bomo spremljali naše velikosti,
ne vemo, kje bi ga dal.

767
00:41:35,290 --> 00:41:39,035
Ne vemo, kako veliko stvari
v naši matriki že.

768
00:41:39,035 --> 00:41:41,410
Tako kot očitno obstajajo načini
da morda to lahko narediš.

769
00:41:41,410 --> 00:41:44,610
Lahko inicializacijo vse na NULL
in nato preverite za najnovejšo NULL,

770
00:41:44,610 --> 00:41:47,950
vendar je veliko lažje, stvar je samo
reči, OK, slediti velikosti.

771
00:41:47,950 --> 00:41:51,840
Kot sem vedel, da sem imel štiri elemente
v mojem polju, zato naslednja stvar

772
00:41:51,840 --> 00:41:55,930
da smo se na, smo
dogaja, da shranite na indeksu 4.

773
00:41:55,930 --> 00:42:00,940
In potem, seveda, to pomeni, da
ste uspešno potisnil nekaj

774
00:42:00,940 --> 00:42:03,320
na vaših žetonov, ki jih
želimo povečati velikost

775
00:42:03,320 --> 00:42:08,880
tako da boste vedeli, kje ste tako
da lahko push več stvari naprej.

776
00:42:08,880 --> 00:42:12,730
>> Torej, če se trudimo, da pop
nekaj off dimnika,

777
00:42:12,730 --> 00:42:16,072
kaj bi lahko prva stvar
da želimo preveriti?

778
00:42:16,072 --> 00:42:18,030
Ste poskušali vzeti
nekaj off vaših žetonov.

779
00:42:18,030 --> 00:42:21,710

780
00:42:21,710 --> 00:42:24,781
Ali ste prepričani, da je
nekaj v vašem kupu?

781
00:42:24,781 --> 00:42:25,280
No.

782
00:42:25,280 --> 00:42:26,894
Torej, kaj bi mi želeli preveriti?

783
00:42:26,894 --> 00:42:27,810
>> OBČINSTVO: [neslišno].

784
00:42:27,810 --> 00:42:29,880
SPEAKER 1: Preverite, ali velikost?

785
00:42:29,880 --> 00:42:31,840
Velikost.

786
00:42:31,840 --> 00:42:38,520
Zato želimo, da preverite, če je
naša velikost je večja od 0, OK?

787
00:42:38,520 --> 00:42:44,970
In če je, potem želimo zmanjšati
naša velikost z 0 in se vrniti, da.

788
00:42:44,970 --> 00:42:45,840
Zakaj?

789
00:42:45,840 --> 00:42:49,950
>> V prvem smo
potiskanje, smo ga potisnili

790
00:42:49,950 --> 00:42:52,460
na velikost in nato posodobljeno velikosti.

791
00:42:52,460 --> 00:42:57,850
V tem primeru smo pomanjšanja velikosti
in nato vzlet, je skubljenje

792
00:42:57,850 --> 00:42:58,952
iz naše paleto.

793
00:42:58,952 --> 00:42:59,826
Zakaj bi mi to naredil?

794
00:42:59,826 --> 00:43:04,800

795
00:43:04,800 --> 00:43:11,811
Torej, če imam eno stvar na mojem kupu,
kaj bi bilo moje velikosti na tej točki?

796
00:43:11,811 --> 00:43:13,140
1.

797
00:43:13,140 --> 00:43:15,180
>> In kjer je element 1 shranjeno?

798
00:43:15,180 --> 00:43:17,621
Na kaj indeks?

799
00:43:17,621 --> 00:43:18,120
OBČINSTVO: 0.

800
00:43:18,120 --> 00:43:19,060
SPEAKER 1: 0.

801
00:43:19,060 --> 00:43:22,800
Torej v tem primeru smo
vedno morali sure--

802
00:43:22,800 --> 00:43:27,630
namesto vračanja
velikost minus 1, ker smo

803
00:43:27,630 --> 00:43:31,730
vemo, da je naš element
bo shranjeno na 1. manj

804
00:43:31,730 --> 00:43:34,705
glede na naš velikost je ta
samo skrbi zanj.

805
00:43:34,705 --> 00:43:36,080
To je nekoliko bolj eleganten način.

806
00:43:36,080 --> 00:43:41,220
In smo samo pojemanje Nostra
velikosti in se nato vrne velikost.

807
00:43:41,220 --> 00:43:42,330
Mmhmm?

808
00:43:42,330 --> 00:43:45,300
>> OBČINSTVO: Mislim, da samo na splošno,
zakaj bi ta struktura podatkov

809
00:43:45,300 --> 00:43:47,800
koristna?

810
00:43:47,800 --> 00:43:50,660
>> SPEAKER 1: To je odvisno od vaše kontekstu.

811
00:43:50,660 --> 00:43:57,420
Torej za nekatere teorije,
če delate with-- OK,

812
00:43:57,420 --> 00:44:02,750
Naj vidim, če je koristno ena
da je koristno, da več kot zunaj

813
00:44:02,750 --> 00:44:05,420
za CS.

814
00:44:05,420 --> 00:44:15,780
Z dimniki, kadarkoli boste potrebovali
slediti nekaj,

815
00:44:15,780 --> 00:44:20,456
je nedavno dodano ko
boste želeli uporabiti kup.

816
00:44:20,456 --> 00:44:24,770
>> In ne morem razmišljati o dobro
Primer, ki prav zdaj.

817
00:44:24,770 --> 00:44:29,955
Ampak ko najnovejša
stvar, ki je najbolj pomembno za vas,

818
00:44:29,955 --> 00:44:31,705
da je, ko kup
se dogaja, da je koristen.

819
00:44:31,705 --> 00:44:35,797

820
00:44:35,797 --> 00:44:39,330
Poskušam razmišljati, če
tam je dobra za to.

821
00:44:39,330 --> 00:44:43,720
Če pomislim na dober primer v naslednjem
20 minut, bom zagotovo vam povem.

822
00:44:43,720 --> 00:44:49,455
>> Ampak na splošno, če je kaj,
kot sem rekel večina, kjer najnovejša

823
00:44:49,455 --> 00:44:52,470
je najbolj pomembno, da je
kjer je kup prihaja v igro.

824
00:44:52,470 --> 00:44:58,860
Ker so čakalne vrste so vrste nasprotno.

825
00:44:58,860 --> 00:44:59,870
In vsi mali psi.

826
00:44:59,870 --> 00:45:00,890
Ali ni to super, kajne?

827
00:45:00,890 --> 00:45:03,299
Počutim se, kot da bi moral
samo še zajček video

828
00:45:03,299 --> 00:45:05,090
desno v sredini
Oddelek za vas

829
00:45:05,090 --> 00:45:08,870
ker je to intenziven odsek.

830
00:45:08,870 --> 00:45:10,480
>> Tako čakalne vrste.

831
00:45:10,480 --> 00:45:12,710
V bistvu čakalna vrsta je kot črto.

832
00:45:12,710 --> 00:45:15,780
Vidva Prepričan sem, da uporaba tega vsak dan,
tako kot v naši jedilnici.

833
00:45:15,780 --> 00:45:18,160
Zato moramo iti v
in dobili naše pladnje, sem

834
00:45:18,160 --> 00:45:21,260
da boste morali čakati v vrsti
Močan in dobili hrano.

835
00:45:21,260 --> 00:45:24,650
>> Torej razlika tukaj
je, da je ta FIFO.

836
00:45:24,650 --> 00:45:30,090
Torej, če LIFO je bil nazadnje v prvi
ven, FIFO je prvi noter, prvi ven.

837
00:45:30,090 --> 00:45:33,400
Torej, to je, če karkoli si dal
na prvi je vaša najpomembnejša.

838
00:45:33,400 --> 00:45:35,540
Torej, če ste čakali
v line-- lahko vam

839
00:45:35,540 --> 00:45:39,130
si, če si šel v
pojdi novi iPhone

840
00:45:39,130 --> 00:45:42,800
in da je sveženj kadar
Zadnja oseba v skladu najprej dobil,

841
00:45:42,800 --> 00:45:44,160
bi ljudje pobijali med seboj.

842
00:45:44,160 --> 00:45:49,800
>> Torej FIFO, da smo vsi zelo dobro poznamo
z v resničnem svetu tu

843
00:45:49,800 --> 00:45:54,930
in vse to ima opraviti z dejansko
nekako poustvariti to celotno linijo

844
00:45:54,930 --> 00:45:56,900
in čekanjem strukturo.

845
00:45:56,900 --> 00:46:02,390
Torej, ker se z dimnika,
imamo potiskanje in pop.

846
00:46:02,390 --> 00:46:06,440
S čakalno vrsto, imamo
enqueue in dequeue.

847
00:46:06,440 --> 00:46:10,910
Torej enqueue v bistvu pomeni,
Povedano na hrbtu,

848
00:46:10,910 --> 00:46:13,680
in dequeue sredstva vzeti
off od spredaj.

849
00:46:13,680 --> 00:46:18,680
Torej naša podatkovna struktura je
malo bolj zapletena.

850
00:46:18,680 --> 00:46:21,060
Imamo še eno stvar za sledenje.

851
00:46:21,060 --> 00:46:25,950
>> Torej, brez glave, ta
je točno kup, kajne?

852
00:46:25,950 --> 00:46:27,900
To je enako strukturo kot dimnika.

853
00:46:27,900 --> 00:46:32,480
Edina stvar drugačna zdaj smo
imam glavo, ki je tisto, kar misliš,

854
00:46:32,480 --> 00:46:34,272
se dogaja, da spremljate?

855
00:46:34,272 --> 00:46:35,510
>> OBČINSTVO: prvi.

856
00:46:35,510 --> 00:46:38,685
>> SPEAKER 1: Right,
Prva stvar, ki smo se v.

857
00:46:38,685 --> 00:46:41,130
Vodja naše vrste.

858
00:46:41,130 --> 00:46:42,240
Kdor je prvi na vrsti.

859
00:46:42,240 --> 00:46:45,300

860
00:46:45,300 --> 00:46:49,420
Vse je v redu, tako da če bomo enqueue.

861
00:46:49,420 --> 00:46:52,720

862
00:46:52,720 --> 00:46:55,920
Spet s katerokoli
Te podatkovne strukture,

863
00:46:55,920 --> 00:46:59,760
saj imamo opravka z vrsto,
moramo preveriti, če imamo prostor.

864
00:46:59,760 --> 00:47:03,290
>> To je nekako tako kot mi pove,
fantje, če odprete datoteko,

865
00:47:03,290 --> 00:47:04,760
morate preveriti za nično.

866
00:47:04,760 --> 00:47:08,330
S katerimkoli izmed teh skladovnic
in čakalne vrste, morate

867
00:47:08,330 --> 00:47:13,420
da vidim, če je prostor, ker smo
ki se ukvarjajo z določeno velikostjo polja,

868
00:47:13,420 --> 00:47:16,030
kot smo videli here-- 0, 1 vse do 5.

869
00:47:16,030 --> 00:47:20,690
Torej, kaj bomo storili v tem primeru je prijava
da vidim, če imamo še prostor.

870
00:47:20,690 --> 00:47:23,110
Naša velikost manjša od zmogljivosti?

871
00:47:23,110 --> 00:47:28,480
>> Če je tako, moramo jo shranite na
rep in bomo posodobiti naše velikosti.

872
00:47:28,480 --> 00:47:30,250
Torej, kaj bi rep biti v tem primeru?

873
00:47:30,250 --> 00:47:32,360
Ni je izrecno napisano ven.

874
00:47:32,360 --> 00:47:33,380
Kako bi bilo shranjevanje?

875
00:47:33,380 --> 00:47:34,928
Kaj bi repa?

876
00:47:34,928 --> 00:47:38,600

877
00:47:38,600 --> 00:47:40,190
>> Tako da je sprehod skozi ta primer.

878
00:47:40,190 --> 00:47:44,590
Torej, to je matrika velikosti 6, kajne?

879
00:47:44,590 --> 00:47:49,220
In imamo zdaj, naša velikost je 5.

880
00:47:49,220 --> 00:47:55,240
In ko smo ga v, gre
da gredo v peto indeks, kajne?

881
00:47:55,240 --> 00:47:57,030
Tako shranite na repu.

882
00:47:57,030 --> 00:48:05,600
>> Drug način, da napišete rep bi samo
biti naša paleta na indeksom velikosti, kajne?

883
00:48:05,600 --> 00:48:07,560
To je velikost 5.

884
00:48:07,560 --> 00:48:11,490
Naslednja stvar, ki se dogaja, da gredo v 5.

885
00:48:11,490 --> 00:48:12,296
Cool?

886
00:48:12,296 --> 00:48:13,290
OK.

887
00:48:13,290 --> 00:48:16,350
To je nekoliko bolj zapletena postane
ko smo začeli zajebavam z glavo.

888
00:48:16,350 --> 00:48:17,060
Ja?

889
00:48:17,060 --> 00:48:20,090
>> OBČINSTVO: Ali to pomeni, da smo
bi razglasila niz, ki

890
00:48:20,090 --> 00:48:23,880
je pet elementov dolgo in
Nato smo dodali na njej?

891
00:48:23,880 --> 00:48:24,730
>> SPEAKER 1: No.

892
00:48:24,730 --> 00:48:27,560
Torej v tem primeru, to je skladovnica.

893
00:48:27,560 --> 00:48:31,760
To bi se razglasi
kot polje velikosti 6.

894
00:48:31,760 --> 00:48:37,120
In v tem primeru smo
samo še eno vesoljsko levo.

895
00:48:37,120 --> 00:48:42,720
>> OK, tako da ena stvar je v tem
primeru, če je naša glava je na 0,

896
00:48:42,720 --> 00:48:45,270
Nato smo le lahko dodate na velikost.

897
00:48:45,270 --> 00:48:51,020
Vendar pa postane malo bolj zapleteno
saj pravzaprav so

898
00:48:51,020 --> 00:48:52,840
nimajo drsnika
za to, da jaz grem

899
00:48:52,840 --> 00:48:56,670
pripraviti eno, ker to ni
tako enostavno, ko vas

900
00:48:56,670 --> 00:48:59,230
začetek znebi stvari.

901
00:48:59,230 --> 00:49:03,920
Torej, ker se z dimnika
si le kdaj

902
00:49:03,920 --> 00:49:08,920
skrbeti, kaj velikost
Ko ste dodali nekaj na,

903
00:49:08,920 --> 00:49:15,710
z vrsti boste morali narediti
Prepričajte se, da je vaša glava obračuna,

904
00:49:15,710 --> 00:49:20,760
saj kul stvar o čakalnih vrst
je, da če nisi v vlogi,

905
00:49:20,760 --> 00:49:23,040
lahko dejansko narediti, da se ovije okoli.

906
00:49:23,040 --> 00:49:28,810
>> OK, tako da ena thing-- oh,
To je grozno kreda.

907
00:49:28,810 --> 00:49:31,815
Ena stvar, da razmisli je tako.

908
00:49:31,815 --> 00:49:35,514

909
00:49:35,514 --> 00:49:37,140
Bomo pač pet.

910
00:49:37,140 --> 00:49:41,810
OK, tako da bomo
pravijo, glava je tukaj.

911
00:49:41,810 --> 00:49:46,140
To pomeni 0, 1, 2, 3, 4.

912
00:49:46,140 --> 00:49:54,210
>> Glava je tam, in
prosim, stvari v njih.

913
00:49:54,210 --> 00:49:58,340
In želimo dodati nekaj v, kajne?

914
00:49:58,340 --> 00:50:01,170
Tako stvar, da moramo
vedo, da je glava vedno

915
00:50:01,170 --> 00:50:05,620
dogaja, da se premaknete na ta način in
potem zanka nazaj okoli, OK?

916
00:50:05,620 --> 00:50:10,190
>> Tako da je ta čakalna vrsta je prostora, kajne?

917
00:50:10,190 --> 00:50:13,950
To je prostor, v samem začetku,
nekako nasprotje tega.

918
00:50:13,950 --> 00:50:17,920
Torej, kaj moramo storiti, je, da smo
moramo izračunati rep.

919
00:50:17,920 --> 00:50:20,530
Če veste, da je vaš
glava ne premakne, rep

920
00:50:20,530 --> 00:50:24,630
je samo tvoja matrika na
Indeks velikosti.

921
00:50:24,630 --> 00:50:30,000
>> Toda v resnici, če uporabljate čakalno vrsto,
tvoja glava se posodablja.

922
00:50:30,000 --> 00:50:33,890
Torej, kaj morate storiti, je,
dejansko izračunati rep.

923
00:50:33,890 --> 00:50:39,990
Torej, kaj moramo storiti, je ta formula
Tukaj, kar jaz grem, da te

924
00:50:39,990 --> 00:50:42,680
Fantje pomislite, in
potem bomo govorili o tem.

925
00:50:42,680 --> 00:50:49,567

926
00:50:49,567 --> 00:50:50,400
Torej, to je zmogljivost.

927
00:50:50,400 --> 00:50:55,890

928
00:50:55,890 --> 00:50:59,660
>> Torej, to bo dejansko
vam način, da to storite.

929
00:50:59,660 --> 00:51:03,205

930
00:51:03,205 --> 00:51:04,330
Ker v tem primeru, kaj?

931
00:51:04,330 --> 00:51:09,205
Naš vodja je na 1, naša velikost je 4.

932
00:51:09,205 --> 00:51:11,760

933
00:51:11,760 --> 00:51:18,490
Če bomo mod, ki ga 5, dobimo 0,
ki je, če bi se morali vhod je.

934
00:51:18,490 --> 00:51:23,320

935
00:51:23,320 --> 00:51:26,080
>> Torej v naslednjem primeru,
če bi to naredili,

936
00:51:26,080 --> 00:51:33,390
smo rekli, v redu, dajmo dequeue nekaj.

937
00:51:33,390 --> 00:51:34,390
Mi dequeue to.

938
00:51:34,390 --> 00:51:37,740
Mi ta element, kajne?

939
00:51:37,740 --> 00:51:47,930
>> In zdaj naša glava je obrnjena tukaj
in želimo dodati v druge stvari.

940
00:51:47,930 --> 00:51:52,470
To je v bistvu
nazaj naše linije, kajne?

941
00:51:52,470 --> 00:51:55,450
Čakalne vrste se lahko ovije okoli polja.

942
00:51:55,450 --> 00:51:57,310
To je ena od glavnih razlik.

943
00:51:57,310 --> 00:51:58,780
Stacks, si tega ne more storiti.

944
00:51:58,780 --> 00:52:01,140
>> S čakalnimi vrstami, lahko
ker vse, kar zadevah

945
00:52:01,140 --> 00:52:03,940
je, da veš, kaj
je bila nazadnje dodali.

946
00:52:03,940 --> 00:52:10,650
Ker je vse, kar se dogaja, da se doda v
ta leftward smer, v tem primeru,

947
00:52:10,650 --> 00:52:16,480
nato pa ovijte okoli, lahko
še naprej uvaja nove elemente

948
00:52:16,480 --> 00:52:18,830
na prednjem delu matrike
ker to ni res

949
00:52:18,830 --> 00:52:20,640
prednja matrike več.

950
00:52:20,640 --> 00:52:26,320
Lahko si misliš o začetku
Niz kot kje dejansko je tvoja glava.

951
00:52:26,320 --> 00:52:29,710
>> Torej, ta formula je, kako
si izračunajte svoj rep.

952
00:52:29,710 --> 00:52:32,780

953
00:52:32,780 --> 00:52:35,610
Ali je to smiselno?

954
00:52:35,610 --> 00:52:36,110
OK.

955
00:52:36,110 --> 00:52:39,400

956
00:52:39,400 --> 00:52:44,040
OK, dequeue, nato pa
vi imate 10 minut

957
00:52:44,040 --> 00:52:48,840
mi zaprosijo katerega koli vprašanja, ki pojasnjujejo
hočeš, ker vem, da je noro.

958
00:52:48,840 --> 00:52:51,980
>> Vse je v redu, tako da v istem way--
Ne vem, če se vi opazili,

959
00:52:51,980 --> 00:52:53,450
vendar CS je vse o vzorcih.

960
00:52:53,450 --> 00:52:57,370
Stvari so precej
Enako, le z drobnimi poteg.

961
00:52:57,370 --> 00:52:58,950
Torej isto stvar tukaj.

962
00:52:58,950 --> 00:53:04,040
Moramo preveriti, da vidim, če bomo dejansko
imeti nekaj v naši vrsti, kajne?

963
00:53:04,040 --> 00:53:05,960
Reči, OK, je naša velikost je večja od 0?

964
00:53:05,960 --> 00:53:06,730
Cool.

965
00:53:06,730 --> 00:53:10,690
>> Če bomo to storili, potem gremo naši glavo, ki
je tisto, kar sem dokazala tukaj.

966
00:53:10,690 --> 00:53:13,870
Mi posodobitev naše glave, da je eden več.

967
00:53:13,870 --> 00:53:18,390
In potem smo pojemanje naše
Velikost in vrne element.

968
00:53:18,390 --> 00:53:21,000

969
00:53:21,000 --> 00:53:26,250
>> Tam je veliko bolj konkreten
koda study.cs50.net,

970
00:53:26,250 --> 00:53:29,440
in sem zelo priporočam dogaja
skozi njo, če imate čas,

971
00:53:29,440 --> 00:53:30,980
tudi če je samo psevdo-kodo.

972
00:53:30,980 --> 00:53:35,980
In če hočete govoriti z
da z mano ena na ena, prosim povej mi,

973
00:53:35,980 --> 00:53:37,500
vem.

974
00:53:37,500 --> 00:53:38,770
Jaz bi z veseljem.

975
00:53:38,770 --> 00:53:42,720
Podatkovne strukture, če
vzamete CS 124, boste

976
00:53:42,720 --> 00:53:47,830
vemo, da podatkovne strukture dobili zelo
zabavno in to je šele začetek.

977
00:53:47,830 --> 00:53:50,350
>> Zato vem, da je težko.

978
00:53:50,350 --> 00:53:51,300
To je OK.

979
00:53:51,300 --> 00:53:52,410
Borimo se.

980
00:53:52,410 --> 00:53:53,630
Sem še vedno.

981
00:53:53,630 --> 00:53:56,660
Torej, ne skrbite preveč o tem.

982
00:53:56,660 --> 00:54:02,390
>> Ampak to je v bistvu Vam nadaljne
crash seveda v podatkovnih struktur.

983
00:54:02,390 --> 00:54:03,400
Vem, da je veliko.

984
00:54:03,400 --> 00:54:06,860
Ali obstaja kaj, da smo
bi rad šel še enkrat?

985
00:54:06,860 --> 00:54:09,400
Karkoli želimo govoriti skozi?

986
00:54:09,400 --> 00:54:10,060
Ja?

987
00:54:10,060 --> 00:54:16,525
>> OBČINSTVO: Za ta primer, tako
Nov rep je na 0 nad tem?

988
00:54:16,525 --> 00:54:17,150
SPEAKER 1: Da.

989
00:54:17,150 --> 00:54:18,230
OBČINSTVO: OK.

990
00:54:18,230 --> 00:54:24,220
Torej gre skozi,
boš pa 1 plus 4 or--

991
00:54:24,220 --> 00:54:27,671
>> SPEAKER 1: Torej ste rekli,
ko želimo iti to ponovi?

992
00:54:27,671 --> 00:54:28,296
OBČINSTVO: Ja.

993
00:54:28,296 --> 00:54:38,290
Torej, če ste bili kipec out--, kjer so
vam izračun rep od v tem?

994
00:54:38,290 --> 00:54:44,260
>> SPEAKER 1: Torej rep
je in-- sem to spremenila.

995
00:54:44,260 --> 00:54:52,010
Tako da v tem primeru bi bilo to
Niz smo gledaš, OK?

996
00:54:52,010 --> 00:54:54,670
Torej imamo stvari v 1, 2, 3 in 4.

997
00:54:54,670 --> 00:55:05,850
Torej imamo glava je enaka 1 pri
ta točka, in naša velikost je enaka 4

998
00:55:05,850 --> 00:55:07,050
Na tej točki, kajne?

999
00:55:07,050 --> 00:55:08,960
>> Vi vsi strinjamo, da je temu tako?

1000
00:55:08,960 --> 00:55:14,620
Torej mi glavo plus velikost, ki
nam daje 5, in potem bomo mod s 5.

1001
00:55:14,620 --> 00:55:20,690
Smo dobili 0, kar nam pove, da je 0
kjer je naša rep, kjer imamo prostor.

1002
00:55:20,690 --> 00:55:22,010
>> OBČINSTVO: Kaj je zgornja meja?

1003
00:55:22,010 --> 00:55:23,520
>> SPEAKER 1: zmogljivost.

1004
00:55:23,520 --> 00:55:24,020
Žal mi je.

1005
00:55:24,020 --> 00:55:29,640
Tako, da je velikost vašega array.

1006
00:55:29,640 --> 00:55:35,210

1007
00:55:35,210 --> 00:55:36,047
Ja?

1008
00:55:36,047 --> 00:55:39,210
>> OBČINSTVO: [neslišno] pred
vrnemo element?

1009
00:55:39,210 --> 00:55:46,270
>> SPEAKER 1: Torej gremo
glavo ali vrnitev trenutek?

1010
00:55:46,270 --> 00:55:52,680
Torej, če gremo eno, pojemanje velikost?

1011
00:55:52,680 --> 00:55:54,150
Počakaj.

1012
00:55:54,150 --> 00:55:55,770
Definitivno sem pozabil drugo.

1013
00:55:55,770 --> 00:56:00,646

1014
00:56:00,646 --> 00:56:01,990
Pozabi.

1015
00:56:01,990 --> 00:56:04,980
Ni drugega formulo.

1016
00:56:04,980 --> 00:56:09,980
Ja, bi si želeli, da se vrnete
glava in nato premakniti nazaj.

1017
00:56:09,980 --> 00:56:13,270
>> OBČINSTVO: OK, saj je na ta
točka, je glava na 0,

1018
00:56:13,270 --> 00:56:18,452
in potem se želite vrniti
indeks 0 in nato glava 1?

1019
00:56:18,452 --> 00:56:19,870
>> SPEAKER 1: Right.

1020
00:56:19,870 --> 00:56:22,820
Mislim, da obstaja še en
Formula nekako takole.

1021
00:56:22,820 --> 00:56:26,970
Ne morem imeti na vrhu moje glave kot
Ne želim, da bi vam napačnega.

1022
00:56:26,970 --> 00:56:35,470
Ampak mislim, da je popolnoma veljavna
recimo, OK, shranite to element-- karkoli

1023
00:56:35,470 --> 00:56:40,759
element glave je is-- pojemanje vaš
velikost, premaknite nad glavo, in povratek

1024
00:56:40,759 --> 00:56:41,800
ne glede na ta element.

1025
00:56:41,800 --> 00:56:44,760
To je povsem veljavna.

1026
00:56:44,760 --> 00:56:45,260
OK.

1027
00:56:45,260 --> 00:56:48,360

1028
00:56:48,360 --> 00:56:53,560
Počutim se, kot da to ni
kot most-- niste

1029
00:56:53,560 --> 00:56:55,740
dogaja, da hodi ven
podobno, ja, vem poskuša.

1030
00:56:55,740 --> 00:56:56,880
I got to vse.

1031
00:56:56,880 --> 00:56:57,670
To je v redu.

1032
00:56:57,670 --> 00:57:00,200
Obljubim.

1033
00:57:00,200 --> 00:57:05,240
Ampak podatkovne strukture so nekaj,
je potrebno veliko časa, da se privadite.

1034
00:57:05,240 --> 00:57:10,010
Verjetno ena najtežje
stvari, mislim, da je v teku.

1035
00:57:10,010 --> 00:57:15,330
>> Torej je vsekakor potrebno
ponavljanje in je videti at-- I

1036
00:57:15,330 --> 00:57:20,050
ne vem, povezane sezname
dokler sem preveč z njimi,

1037
00:57:20,050 --> 00:57:22,550
na enak način, da nisem
Res razumem kazalce

1038
00:57:22,550 --> 00:57:27,040
dokler sem moral naučiti dvoje
let in naredite svoje lastne psets z njim.

1039
00:57:27,040 --> 00:57:28,990
To traja veliko ponovitvene in časa.

1040
00:57:28,990 --> 00:57:32,600
In na koncu, da bo vrsta kliknite.

1041
00:57:32,600 --> 00:57:36,320
>> Toda v tem času, če imate neke vrste
razumevanja na visoki ravni, kar

1042
00:57:36,320 --> 00:57:39,321
to storiti, njihove prednosti
in cons--, ki je kaj

1043
00:57:39,321 --> 00:57:41,820
res navadno poudarjajo,
zlasti v intro tečaj.

1044
00:57:41,820 --> 00:57:45,511
Všeč mi je, zakaj bi uporabili
poskusite čez array?

1045
00:57:45,511 --> 00:57:48,010
Všeč mi je, kakšni so pozitivni
in negativov vsake od teh?

1046
00:57:48,010 --> 00:57:51,610
>> In razumevanje kompromise
med vsako od teh struktur

1047
00:57:51,610 --> 00:57:54,910
je tisto, kar je zdaj veliko bolj pomembno.

1048
00:57:54,910 --> 00:57:58,140
Tam lahko ena nora
Vprašanje, ali dva, da je

1049
00:57:58,140 --> 00:58:03,710
dogaja, da vas prosim, da izvaja potiskanje ali
izvajajo pop ali enqueue in dequeue.

1050
00:58:03,710 --> 00:58:07,340
Toda za večino del, ki ima
višjo raven razumevanja in več

1051
00:58:07,340 --> 00:58:09,710
o je intuitivno razumevanje
bolj pomembna kot dejansko

1052
00:58:09,710 --> 00:58:11,250
da bi mogli izvajati.

1053
00:58:11,250 --> 00:58:14,880
>> To bi bilo res super, če vas vse
lahko greš ven in pojdi izvajati poskusiti,

1054
00:58:14,880 --> 00:58:19,720
vendar smo razumeli, da to ni nujno
najbolj razumna stvar prav zdaj.

1055
00:58:19,720 --> 00:58:23,370
Ampak jih lahko v vašem pset, če želite
da, in potem boste dobili prakso,

1056
00:58:23,370 --> 00:58:27,200
in potem morda boste
Res razumem.

1057
00:58:27,200 --> 00:58:27,940
Ja?

1058
00:58:27,940 --> 00:58:30,440
>> OBČINSTVO: OK, tako da so tisti, ki
smo mišljen za uporabo v pset?

1059
00:58:30,440 --> 00:58:31,916
Ali moram uporabiti eno od njih?

1060
00:58:31,916 --> 00:58:32,540
SPEAKER 1: Da.

1061
00:58:32,540 --> 00:58:34,199
Torej imaš izbiro.

1062
00:58:34,199 --> 00:58:36,740
Mislim, da v tem primeru, ne moremo
govorimo o pset malo

1063
00:58:36,740 --> 00:58:40,480
ker sem tekel skozi to.

1064
00:58:40,480 --> 00:58:47,779
Torej v vašem pset, imate
Izbira poskusih ali hash tabel.

1065
00:58:47,779 --> 00:58:49,570
Nekateri ljudje bodo poskušali
in uporabo cvet filtrov

1066
00:58:49,570 --> 00:58:51,840
ampak tisti, tehnično ni pravilen.

1067
00:58:51,840 --> 00:58:55,804
Zaradi njihove verjetnostnega narave,
dajejo včasih napačen.

1068
00:58:55,804 --> 00:58:57,095
Oni so kul pogled v, čeprav.

1069
00:58:57,095 --> 00:58:59,030
Toplo priporočam iščejo
pri njih vsaj.

1070
00:58:59,030 --> 00:59:03,260
Vendar pa imate možnost izbire
med hash tabele in poskusu.

1071
00:59:03,260 --> 00:59:06,660
In to se dogaja, da je tam, kjer
naložite v slovarju.

1072
00:59:06,660 --> 00:59:09,230
>> In boste morali izbrati
Vaše hash funkcija,

1073
00:59:09,230 --> 00:59:13,420
boste morali izbrati, koliko
žlice, ki jo imajo, in se bo spreminjala.

1074
00:59:13,420 --> 00:59:17,440
Všeč mi je, če imate več vedra,
Mogoče bo to teči hitreje.

1075
00:59:17,440 --> 00:59:22,790
Morda pa ste zapravljaš
Veliko prostora, da je tako, čeprav.

1076
00:59:22,790 --> 00:59:26,320
Moraš ga pogruntal.

1077
00:59:26,320 --> 00:59:27,140
Mmhmm?

1078
00:59:27,140 --> 00:59:29,875
>> OBČINSTVO: Prej ste rekli, da je
moremo uporabljati drugih hash funkcije,

1079
00:59:29,875 --> 00:59:31,750
da mi ne bi bilo treba
ustvariti funkcijo razpršitve?

1080
00:59:31,750 --> 00:59:32,666
>> SPEAKER 1: Ja, prav.

1081
00:59:32,666 --> 00:59:38,150
Torej dobesedno za vaš hash funkcijo,
kot google "funkcija hash"

1082
00:59:38,150 --> 00:59:40,770
in si za nekaj kul narave.

1083
00:59:40,770 --> 00:59:43,250
Vi se ne pričakuje, da gradijo
lastne zgoščevalne funkcije.

1084
00:59:43,250 --> 00:59:46,100
Ljudje preživijo svoje
tez o teh stvareh.

1085
00:59:46,100 --> 00:59:50,250
>> Torej, ne skrbite o gradnji svoje.

1086
00:59:50,250 --> 00:59:53,350
Našli eno na spletu, da začnete z.

1087
00:59:53,350 --> 00:59:56,120
Nekatere od njih boste morali
manipulirati malo

1088
00:59:56,120 --> 00:59:59,430
Da bi se prepričali vrste povratnih ujemajo
in malenkosti, tako da v začetku,

1089
00:59:59,430 --> 01:00:02,420
Jaz bi priporočal uporabo nekaj
zelo enostavno, da morda le

1090
01:00:02,420 --> 01:00:04,680
hashes na prvo črko.

1091
01:00:04,680 --> 01:00:08,760
In potem, ko imate to delo,
vgrajen hladilnik funkcijo razpršitve.

1092
01:00:08,760 --> 01:00:09,260
Mmhmm?

1093
01:00:09,260 --> 01:00:13,020
>> OBČINSTVO: Bi poskusite biti ali
učinkovite, vendar le težje, like--

1094
01:00:13,020 --> 01:00:15,880
>> SPEAKER 1: Torej, poskusite, mislim,
je intuitivno težko izvajati

1095
01:00:15,880 --> 01:00:18,310
vendar je zelo hiter.

1096
01:00:18,310 --> 01:00:20,620
Vendar pa je več prostora.

1097
01:00:20,620 --> 01:00:25,270
Again, lahko optimizirate, tako tistih, ki v
različne načine in obstajajo načini to--

1098
01:00:25,270 --> 01:00:26,770
OBČINSTVO: Kako smo ocenjena na to?

1099
01:00:26,770 --> 01:00:27,540
Ali matter--

1100
01:00:27,540 --> 01:00:29,164
>> SPEAKER 1: Torej ste sortirani običajen način.

1101
01:00:29,164 --> 01:00:31,330
Boš razvrsti na design.

1102
01:00:31,330 --> 01:00:36,020
Kakorkoli boste to storili, boste želeli
prepričajte, da je tako eleganten kot je mogoče

1103
01:00:36,020 --> 01:00:38,610
in tako učinkovita, kot je mogoče.

1104
01:00:38,610 --> 01:00:41,950
Ampak, če se odločite poskusiti ali hašiš
miza, dokler deluje,

1105
01:00:41,950 --> 01:00:45,350
smo zadovoljni s tem.

1106
01:00:45,350 --> 01:00:48,370
In če boste uporabili nekaj, kar hashes
na prvo črko, da je v redu,

1107
01:00:48,370 --> 01:00:51,410
kot morda podobno zasnovo-modrih.

1108
01:00:51,410 --> 01:00:53,410
Mi smo tudi dosegli
točka v tem semester--

1109
01:00:53,410 --> 01:00:55,340
Ne vem, če vas
Fantje noticed-- če ste

1110
01:00:55,340 --> 01:00:58,780
pset stopnje upada malo
zaradi oblikovanja in drugih malenkosti,

1111
01:00:58,780 --> 01:00:59,900
To je popolnoma v redu.

1112
01:00:59,900 --> 01:01:02,960
To je že do točke, kjer se vaš
programi postajajo vse bolj zapletena.

1113
01:01:02,960 --> 01:01:04,830
Obstaja več krajih
lahko izboljšati.

1114
01:01:04,830 --> 01:01:06,370
>> Torej, to je povsem normalno.

1115
01:01:06,370 --> 01:01:08,810
Saj ne, da ste
tem slabše od vaše pset.

1116
01:01:08,810 --> 01:01:11,885
To je samo bomo pa težje od tebe.

1117
01:01:11,885 --> 01:01:13,732
Tako da vsi že na občutek.

1118
01:01:13,732 --> 01:01:14,940
Pravkar sem se razvrstijo vse vaše psets.

1119
01:01:14,940 --> 01:01:16,490
Vem, da vsakdo se počuti.

1120
01:01:16,490 --> 01:01:19,600
>> Zato ne bodite zaskrbljeni zaradi tega.

1121
01:01:19,600 --> 01:01:23,580
In če imate vprašanja o
predhodna psets ali načinov, kako lahko izboljšajo,

1122
01:01:23,580 --> 01:01:27,760
Trudim se in komentiraj specifična
mesta, ampak včasih je prepozno

1123
01:01:27,760 --> 01:01:30,840
in sem se naveličal.

1124
01:01:30,840 --> 01:01:34,885
Ali obstajajo še kakšne druge stvari,
o podatkovne strukture?

1125
01:01:34,885 --> 01:01:37,510
Prepričan sem, da ste vi v resnici ne
želim več govoriti o njih,

1126
01:01:37,510 --> 01:01:42,650
ampak, če obstajajo, sem vesel, da
iti nad njimi, kakor tudi karkoli

1127
01:01:42,650 --> 01:01:45,580
iz predavanja ta preteklem
teden ali prejšnji teden.

1128
01:01:45,580 --> 01:01:51,580
>> Vem, prejšnji teden je bilo vse ocene, tako da
smo lahko preskočijo nekaterih pregleda

1129
01:01:51,580 --> 01:01:54,190
iz predavanja.

1130
01:01:54,190 --> 01:01:58,230
Vsa druga vprašanja, mi lahko odgovorite?

1131
01:01:58,230 --> 01:01:59,350
OK, v redu.

1132
01:01:59,350 --> 01:02:02,400
No, fantje ven 15 minut prej.

1133
01:02:02,400 --> 01:02:08,370
>> Upam, da je to semi-koristno vsaj,
in jaz vam bomo videli fantje naslednji teden,

1134
01:02:08,370 --> 01:02:12,150
ali četrtek uradnih ur.

1135
01:02:12,150 --> 01:02:15,285
Ali obstaja zahteva za prigrizke
za naslednji teden, to je stvar?

1136
01:02:15,285 --> 01:02:17,459
Ker sem pozabil sladkarije danes.

1137
01:02:17,459 --> 01:02:19,750
In sem prinesel sladkarije zadnji
teden, vendar je bilo Columbus Day,

1138
01:02:19,750 --> 01:02:25,400
tako da je bilo tako kot šest ljudi, ki so
je imel štiri vrečke bonbonov zase.

1139
01:02:25,400 --> 01:02:28,820
Jaz lahko prinese zvezdne
še enkrat, če ti je všeč.

1140
01:02:28,820 --> 01:02:29,580
Zvezdne?

1141
01:02:29,580 --> 01:02:32,250
OK, zveni dobro.

1142
01:02:32,250 --> 01:02:35,050
Imajo velik dan, fantje.

1143
01:02:35,050 --> 01:02:39,510