1
00:00:00,000 --> 00:00:03,423
>> [Musiikkia]

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

3
00:00:05,380 --> 00:00:08,210
>> ANDI Peng: Tervetuloa viikko 6 §.

4
00:00:08,210 --> 00:00:11,620
Me poikkesi meidän vakio
kohta aikaa tiistaina

5
00:00:11,620 --> 00:00:14,130
iltapäivällä tämän ihanan sunnuntaiaamuna.

6
00:00:14,130 --> 00:00:17,330
Kiitos kaikille, että
liittyi minulle tänään, mutta vakavasti,

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

8
00:00:18,170 --> 00:00:20,600
>> Se on aika iso ponnistus.

9
00:00:20,600 --> 00:00:23,600
Melkein ei edes tee sitä
ylös ajoissa, mutta se oli OK.

10
00:00:23,600 --> 00:00:27,520
Joten tiedän, että te kaikki
juuri tehnyt sen tietovisa.

11
00:00:27,520 --> 00:00:30,370
Ensinnäkin, tervetuloa
kääntöpuoli jotka.

12
00:00:30,370 --> 00:00:32,917
>> Toiseksi, me puhumme siitä.

13
00:00:32,917 --> 00:00:34,000
Puhutaan tietokilpailu.

14
00:00:34,000 --> 00:00:35,700
Puhutaan miten
teet luokassa.

15
00:00:35,700 --> 00:00:36,550
Tulet hieno.

16
00:00:36,550 --> 00:00:39,080
Minulla on teidän tietokilpailuja
sinulle lopussa täältä,

17
00:00:39,080 --> 00:00:42,120
joten jos kaverit haluavat ottaa
katso sitä, täysin hieno.

18
00:00:42,120 --> 00:00:46,590
>> Niin nopeasti ennen kuin aloitamme,
esityslista tänään on seuraava.

19
00:00:46,590 --> 00:00:48,430
Kuten näette, olemme
pohjimmiltaan nopea ampumisen

20
00:00:48,430 --> 00:00:52,120
läpi koko joukko tietorakenteiden
todella, todella, todella nopeasti.

21
00:00:52,120 --> 00:00:54,380
Niin sellaisenaan, se ei ole
Super interaktiivinen tänään.

22
00:00:54,380 --> 00:00:59,620
Se täytyy vain olla minä sellainen huutaen
asioita, joita te, ja jos minä hämmentää sinua,

23
00:00:59,620 --> 00:01:02,680
jos aion liian nopeasti, haluaisin tietää.

24
00:01:02,680 --> 00:01:05,200
He ovat vain eri tiedot
rakenteet, ja osana

25
00:01:05,200 --> 00:01:07,070
teidän PSET tälle
tulevan viikon, luultavasti

26
00:01:07,070 --> 00:01:10,340
pyydetään toteuttamaan yksi heistä,
ehkä kaksi them-- kaksi niistä

27
00:01:10,340 --> 00:01:12,319
teidän PSET.

28
00:01:12,319 --> 00:01:14,610
OK, joten olen juuri menossa
aloittaa joitakin ilmoituksia.

29
00:01:14,610 --> 00:01:19,070
Mennään yli pinot ja jonot enemmän
syvyyttä kuin mitä teimme ennen tietokilpailu.

30
00:01:19,070 --> 00:01:20,990
Menemme yli liittyy
luetella uudestaan, jälleen kerran,

31
00:01:20,990 --> 00:01:23,899
enemmän syvyyttä kuin mitä
meillä oli ennen tietokilpailu.

32
00:01:23,899 --> 00:01:26,440
Ja sitten me puhumme hash
pöydät, puita ja yrittää, joka

33
00:01:26,440 --> 00:01:28,890
ovat kaikki melko välttämättömiä teidän PSET.

34
00:01:28,890 --> 00:01:32,925
Ja sitten me mennä yli joitakin
hyödyllisiä vinkkejä pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, joten tietokilpailu 0.

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

37
00:01:41,090 --> 00:01:45,370
Se oli hyvin alhainen, ja niin te kaikki
teki erittäin, erittäin hyvin mukaan

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

39
00:01:46,510 --> 00:01:49,970
>> Aika paljon, nyrkkisääntö on, jos olet
sisällä keskihajonta keskiarvosta

40
00:01:49,970 --> 00:01:52,990
varsinkin kun olemme vähemmän
mukava jakso, olet täysin hieno.

41
00:01:52,990 --> 00:01:54,120
Olet raiteilleen.

42
00:01:54,120 --> 00:01:55,190
Elämä on hyvää.

43
00:01:55,190 --> 00:01:58,952
>> Tiedän, että se on pelottavaa ajatella, että
Sain kuin 40% tämän tietovisan.

44
00:01:58,952 --> 00:02:00,160
Aion epäonnistua tähän luokkaan.

45
00:02:00,160 --> 00:02:02,243
Lupaan teille, et ole
menossa epäonnistua luokan.

46
00:02:02,243 --> 00:02:03,680
Olet täysin hieno.

47
00:02:03,680 --> 00:02:06,850
>> Niille teistä, jotka saivat yli
keskiarvo, vaikuttava, vaikuttava,

48
00:02:06,850 --> 00:02:08,780
kuten, vakavasti hyvin tehty.

49
00:02:08,780 --> 00:02:09,689
Minulla on ne minulle.

50
00:02:09,689 --> 00:02:11,730
Voit vapaasti tulla saada ne
lopussa osassa.

51
00:02:11,730 --> 00:02:14,520
Haluaisin tietää, jos sinulla on
kysymyksiä, kysymyksiä heidän kanssaan.

52
00:02:14,520 --> 00:02:17,204
Jos lisäämme up your pisteet
väärässä, kerro meille.

53
00:02:17,204 --> 00:02:21,240
>> OK, niin pset5, tämä on todella
outo viikko Yale siinä mielessä

54
00:02:21,240 --> 00:02:24,240
että PSET johtuu
Maanantaisin klo lukien

55
00:02:24,240 --> 00:02:27,317
myöhään päivä, joten se on todella
teoriassa johtuu tiistaina keskipäivällä.

56
00:02:27,317 --> 00:02:29,150
Luultavasti kukaan päättynyt
tiistaina keskipäivällä.

57
00:02:29,150 --> 00:02:30,830
Se on täysin hieno.

58
00:02:30,830 --> 00:02:33,700
Aiomme olla virka
tänä iltana sekä maanantai-iltana.

59
00:02:33,700 --> 00:02:36,810
Ja kaikki osat tällä viikolla
todella muuttui työpajoja,

60
00:02:36,810 --> 00:02:38,800
niin voit pop
jokin osa haluat,

61
00:02:38,800 --> 00:02:42,810
ja he ovat eräänlainen mini-PSET
työpajoja apua siitä.

62
00:02:42,810 --> 00:02:45,620
Joten sinänsä, tämä on ainoa osio
minne olemme oppimateriaalia.

63
00:02:45,620 --> 00:02:49,220
Kaikki muut osiot keskittyy
yksinomaan apua PSET.

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

65
00:02:50,146 --> 00:02:52,000
>> Yleisö: Missä virka?

66
00:02:52,000 --> 00:02:56,120
>> ANDI Peng: Aukioloajat
tonight-- Voi, hyvä kysymys.

67
00:02:56,120 --> 00:03:00,580
Mielestäni virka tänä iltana
ovat Tavi tai Commons.

68
00:03:00,580 --> 00:03:02,984
Jos tarkistaa verkossa CS50
ja menet virka,

69
00:03:02,984 --> 00:03:05,650
olisi aikataulun
kertoo missä ne kaikki ovat.

70
00:03:05,650 --> 00:03:07,954
>> Tiedän joko tänä iltana
tai huomenna on sinivihreä,

71
00:03:07,954 --> 00:03:10,120
ja mielestäni meillä voi olla
commons muiden yö.

72
00:03:10,120 --> 00:03:11,020
En ole varma.

73
00:03:11,020 --> 00:03:11,700
Hyvä kysymys.

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

75
00:03:14,430 --> 00:03:18,780
>> Viileä, kysyttävää
aikataulu seuraavan kuten kolmessa päivässä?

76
00:03:18,780 --> 00:03:21,690
Lupaan te kuten David
sanoi, tämä on mäen päälle.

77
00:03:21,690 --> 00:03:23,050
Te olette melkein perillä.

78
00:03:23,050 --> 00:03:24,644
Vain kolme päivää.

79
00:03:24,644 --> 00:03:26,310
Sinne, ja sitten me kaikki tulla alas.

80
00:03:26,310 --> 00:03:28,114
Meidän täytyy mukava CS-taukoa.

81
00:03:28,114 --> 00:03:28,780
Tervetuloa takaisin.

82
00:03:28,780 --> 00:03:30,779
Me sukeltaa web
ohjelmointi ja kehitys,

83
00:03:30,779 --> 00:03:35,150
asioita, jotka ovat erittäin hauska verrattuna
joitakin muita psets.

84
00:03:35,150 --> 00:03:37,974
Ja se tulee olemaan chill, ja
meillä on hauskaa.

85
00:03:37,974 --> 00:03:38,890
Meillä on enemmän karkkia.

86
00:03:38,890 --> 00:03:39,730
Anteeksi karkkia.

87
00:03:39,730 --> 00:03:40,945
Unohdin karkkia.

88
00:03:40,945 --> 00:03:43,310
Se oli karkea aamu.

89
00:03:43,310 --> 00:03:46,340
Joten te olette melkein perillä,
ja olen todella ylpeä sinusta kaverit.

90
00:03:46,340 --> 00:03:49,570
>> OK, niin pinot.

91
00:03:49,570 --> 00:03:53,331
Joka rakasti kysymys Jack
ja hänen vaatteita tietovisa?

92
00:03:53,331 --> 00:03:53,830
Ei kukaan?

93
00:03:53,830 --> 00:03:56,500
OK, se käy hyvin.

94
00:03:56,500 --> 00:04:00,200
>> Niin olennaisesti kuin voit
kuva Jack, tämä kaveri täällä,

95
00:04:00,200 --> 00:04:03,350
rakastaa ottaa vaatteet
pois pinon,

96
00:04:03,350 --> 00:04:05,750
ja hän laittaa sen takaisin
pino jälkeen hän on tehnyt.

97
00:04:05,750 --> 00:04:07,600
Joten tällä tavalla, hän ei koskaan
näyttää olevan saada

98
00:04:07,600 --> 00:04:10,090
pohjaan
pino hänen vaatteet.

99
00:04:10,090 --> 00:04:12,600
Joten tällainen kuvaa
perustiedot rakenne

100
00:04:12,600 --> 00:04:16,610
miten pino toteutetaan.

101
00:04:16,610 --> 00:04:20,060
>> Pohjimmiltaan ajatella
pino niin kaikki pino esineiden

102
00:04:20,060 --> 00:04:24,900
jossa voit laittaa asiat kiinni alkuun, ja
sitten pop heidät pois ylhäältä.

103
00:04:24,900 --> 00:04:28,600
Joten LIFO on lyhenne haluamme
että use-- Viime in, first out.

104
00:04:28,600 --> 00:04:32,480
Ja niin viime vuonna alkuun
pino on ensimmäinen, joka tulee ulos.

105
00:04:32,480 --> 00:04:34,260
Ja niin kaksi termiä
haluamme liittää

106
00:04:34,260 --> 00:04:36,190
kanssa, joita kutsutaan push ja pop.

107
00:04:36,190 --> 00:04:39,790
Kun painat jotain päälle
pino, ja pop se takaisin ylös.

108
00:04:39,790 --> 00:04:43,422
>> Ja niin kai tämä on tavallaan
abstrakti käsite Niille teistä

109
00:04:43,422 --> 00:04:45,630
jotka haluavat nähdä kuin
tosiasiallinen täytäntöönpano

110
00:04:45,630 --> 00:04:46,740
todellisessa maailmassa.

111
00:04:46,740 --> 00:04:50,170
Kuinka moni teistä on kirjoittanut esseen
ehkä kuten tunti ennen johtui,

112
00:04:50,170 --> 00:04:54,510
ja olet vahingossa poistanut valtava
kimpale se, kuten vahingossa?

113
00:04:54,510 --> 00:04:58,560
Ja mitä sitten ohjaus tehdä
käytämme laittaa se takaisin?

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

115
00:05:00,030 --> 00:05:03,640
Control-Z, joten määrä kertoja
että valvonta-Z on pelastanut henkeni,

116
00:05:03,640 --> 00:05:08,820
on pelastanut minun perse, joka kerta
joka on toteutetaan pinon.

117
00:05:08,820 --> 00:05:13,020
>> Pohjimmiltaan kaikki tiedot
se on Word-asiakirjaan,

118
00:05:13,020 --> 00:05:15,080
se saa työntää ja piipahti mieleisekseen.

119
00:05:15,080 --> 00:05:19,460
Ja niin olennaisesti kun
poistaa mitään, pop se takaisin ylös.

120
00:05:19,460 --> 00:05:22,820
Ja sitten jos tarvitset sitä takaisin päälle, sinun
työnnä se, joka on mitä control-C ei.

121
00:05:22,820 --> 00:05:26,770
Ja niin reaalimaailman toiminto
miten yksinkertainen tietorakenne

122
00:05:26,770 --> 00:05:28,690
voi auttaa jokapäiväistä elämää.

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

124
00:05:31,710 --> 00:05:40,150
>> Joten struct on niin, että
me itse luoda pino.

125
00:05:40,150 --> 00:05:44,720
Me Define struct, ja sitten
me kutsumme sitä pino alareunassa.

126
00:05:44,720 --> 00:05:47,440
Ja sisällä pino,
meillä on kaksi parametrit

127
00:05:47,440 --> 00:05:51,580
että voimme olennaisesti manipuloida,
joten meillä on nieriä tähden jouset kapasiteettia.

128
00:05:51,580 --> 00:05:55,150
>> Kaikki, että se tekee
luo array

129
00:05:55,150 --> 00:05:58,835
että voimme tallentaa mitä haluat
joka voimme määrittää sen kapasiteettia.

130
00:05:58,835 --> 00:06:01,990
Kapasiteetti on vain max määrä
kohteita voimme tähän array.

131
00:06:01,990 --> 00:06:05,660
int koko on laskuri, joka pitää
seuraa, kuinka monta kohdetta on tällä hetkellä

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

133
00:06:07,850 --> 00:06:11,860
Jotta voimme seurata,,
sekä kuinka suuri todellinen pino on,

134
00:06:11,860 --> 00:06:14,850
ja, B, kuinka paljon, että pino
täytimme koska emme halua

135
00:06:14,850 --> 00:06:18,800
ylivuoto, mitä meidän kapasiteetti on.

136
00:06:18,800 --> 00:06:24,340
>> Niinpä esimerkiksi, tämä ihana
kysymys oli tietokilpailun.

137
00:06:24,340 --> 00:06:28,160
Pohjimmiltaan miten me työntää
päälle pinon päälle.

138
00:06:28,160 --> 00:06:28,830
Melko yksinkertainen.

139
00:06:28,830 --> 00:06:30,621
Jos katsot sitä,
me kulkea tämän.

140
00:06:30,621 --> 00:06:32,640
Jos [äänetön] size--
muistaa, kun

141
00:06:32,640 --> 00:06:35,300
haluavat käyttää mitä tahansa
parametrin struct,

142
00:06:35,300 --> 00:06:40,320
teet nimi struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> Tällöin s on
nimi meidän pinon.

144
00:06:42,720 --> 00:06:46,230
Haluamme päästä koko
sitä, joten emme s.size.

145
00:06:46,230 --> 00:06:50,280
Niin kauan kuin koko ei ole
sama kapasiteetti tai niin kauan

146
00:06:50,280 --> 00:06:52,940
koska se on vähemmän kuin kapasiteetti,
joko toimisi täällä.

147
00:06:52,940 --> 00:06:57,180
>> Haluat käyttää sisällä
stäkistäsi, niin s.strings,

148
00:06:57,180 --> 00:07:00,790
ja aiot laittaa että uusi numero
että haluat lisätä osaksi siellä.

149
00:07:00,790 --> 00:07:05,030
Sanotaan vain me haluamme
aseta int n pinoon,

150
00:07:05,030 --> 00:07:08,905
voisimme tehdä s.strings,
suluissa, s.size vastaa n.

151
00:07:08,905 --> 00:07:11,030
Koska koko on, jos me
tällä hetkellä ovat pinossa

152
00:07:11,030 --> 00:07:14,590
jos aiomme ajaa
se, me vain käyttää

153
00:07:14,590 --> 00:07:17,370
missä koko on,
nykyinen täyteys pino,

154
00:07:17,370 --> 00:07:21,729
ja me työnnä int n päälle.

155
00:07:21,729 --> 00:07:24,770
Ja sitten me haluamme varmistaa, että
olemme myös monesko koko n,

156
00:07:24,770 --> 00:07:27,436
jotta voimme seurata olemme
lisätty ylimääräinen asia pino.

157
00:07:27,436 --> 00:07:29,660
Nyt meillä on suurempi koko.

158
00:07:29,660 --> 00:07:33,196
Onko täällä mitään järkeä
kaikki, miten loogisesti se toimii?

159
00:07:33,196 --> 00:07:34,160
Se oli eräänlainen nopeasti.

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

161
00:07:39,535 --> 00:07:42,160
Yleisö: Voitko mennä yli
s.stringss.strings [s.size] uudelleen?

162
00:07:42,160 --> 00:07:45,808
ANDI Peng: Toki, niin mitä tekee
s.size hetkellä antaa meille?

163
00:07:45,808 --> 00:07:47,440
Yleisö: Se on nykyinen koko.

164
00:07:47,440 --> 00:07:50,890
ANDI Peng: Aivan, niin
Hakemisto, että koko on,

165
00:07:50,890 --> 00:07:57,780
ja niin haluamme laittaa uusi kokonaisluku
että haluamme lisätä osaksi s.size.

166
00:07:57,780 --> 00:07:58,760
Onko siinä järkeä?

167
00:07:58,760 --> 00:08:01,110
Koska s.strings, kaikki jotka
on on nimi jono.

168
00:08:01,110 --> 00:08:03,510
Kaikki se on on pääsy
array sisällä struct,

169
00:08:03,510 --> 00:08:06,030
joten jos haluamme
paikka n tuohon indeksi,

170
00:08:06,030 --> 00:08:09,651
voimme vain käyttää sitä
käyttäen suluissa s.size.

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

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

173
00:08:13,580 --> 00:08:18,916
>> Hyvä, pop, olen pseudokoodina se ulos
sinulle kaverit, mutta samanlainen käsite.

174
00:08:18,916 --> 00:08:19,790
Onko siinä järkeä?

175
00:08:19,790 --> 00:08:22,310
Jos koko on suurempi
kuin nolla, niin voit

176
00:08:22,310 --> 00:08:25,350
tietävät, että haluat ottaa jotain
pois, koska jos koko ei ole

177
00:08:25,350 --> 00:08:27,620
suurempi kuin nolla, niin voit
ei ole mitään pinossa.

178
00:08:27,620 --> 00:08:29,840
>> Joten haluat vain suorittaa
tätä koodia, se voi vain

179
00:08:29,840 --> 00:08:32,320
pop jos on jotain pop.

180
00:08:32,320 --> 00:08:35,830
Joten jos koko on suurempi
kuin 0, me miinus koko.

181
00:08:35,830 --> 00:08:40,020
Me dekrementoidaan koko ja palata sitten
mikä on sen sisällä, koska

182
00:08:40,020 --> 00:08:42,710
popping, haluamme
yhteys mitä tallennetaan

183
00:08:42,710 --> 00:08:45,694
vuonna indeksi päällimmäinen.

184
00:08:45,694 --> 00:08:46,610
Kaikki järkeä?

185
00:08:46,610 --> 00:08:49,693
Jos Tein te kirjoittaa tätä,
olisi te voi kirjoittaa sen pois?

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

187
00:08:52,029 --> 00:08:53,570
OK, te voi leikkiä sen kanssa.

188
00:08:53,570 --> 00:08:55,252
Ei hätää, jos et saa sitä.

189
00:08:55,252 --> 00:08:57,460
Meillä ei ole aikaa koodia
sitä tänään, koska olemme

190
00:08:57,460 --> 00:08:59,959
sai paljon näiden rakenteiden
käydä läpi, mutta pohjimmiltaan

191
00:08:59,959 --> 00:09:02,214
pseudokoodilla, hyvin, hyvin samankaltainen työntää.

192
00:09:02,214 --> 00:09:03,380
Vain seurata pitkin logiikkaa.

193
00:09:03,380 --> 00:09:06,092
Varmista, että olet saada kaikki
Autosi struct oikein.

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

195
00:09:06,574 --> 00:09:09,282
>> Yleisö: Will näitä dioja ja
tämä koko juttu on tänään ish?

196
00:09:09,282 --> 00:09:11,586
ANDI Peng: Aina, juu.

197
00:09:11,586 --> 00:09:13,710
Aion yrittää laittaa
tämä ylös kuin tunnin kuluttua.

198
00:09:13,710 --> 00:09:16,626
Minä sähköpostitse David, David yrittää
laita se ylös kuin tunnin kuluttua tästä.

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

200
00:09:20,040 --> 00:09:25,470
>> OK, joten sitten siirrymme tähän muut
ihana datarakenne kutsutaan jonoon.

201
00:09:25,470 --> 00:09:30,140
Kuten te voi nähdä täällä,
jono, Britannian keskuudessamme,

202
00:09:30,140 --> 00:09:32,010
kaikki se on on viiva.

203
00:09:32,010 --> 00:09:34,680
Joten toisin
luulet pino on,

204
00:09:34,680 --> 00:09:37,750
jono juuri
loogisesti luulet se on.

205
00:09:37,750 --> 00:09:41,914
Se hallussa sääntöjen FIFO,
joka on First In, First Out.

206
00:09:41,914 --> 00:09:43,705
Jos olet ensimmäinen
yksi linja, olet

207
00:09:43,705 --> 00:09:46,230
ensimmäinen, joka
tulee ulos linja.

208
00:09:46,230 --> 00:09:49,680
>> Joten mitä haluamme kutsua tätä
on dequeueing ja enqueueing.

209
00:09:49,680 --> 00:09:52,380
Jos haluamme lisätä jotain
meidän jonoon, me laittaa jonoon.

210
00:09:52,380 --> 00:09:55,690
Jos haluamme dequeue, tai ottaa
jotain pois, me dequeue.

211
00:09:55,690 --> 00:10:03,350
>> Niin sama tunne, että olemme tavallaan
luominen vakiokokoiseen elementtejä, jotka me

212
00:10:03,350 --> 00:10:06,500
voi tallentaa tiettyjä
asioita, mutta voimme myös

213
00:10:06,500 --> 00:10:10,100
muuttaa minne olemme saattamista
parametrit sisällä niitä

214
00:10:10,100 --> 00:10:13,140
perustuu minkälainen
toiminnallisuutta haluamme.

215
00:10:13,140 --> 00:10:16,700
Joten pinot, halusimme viimeinen
yksi, N olla ensimmäinen yksi.

216
00:10:16,700 --> 00:10:19,800
Jono on haluamme ensimmäinen asia
on olla ensimmäinen asia pois.

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

218
00:10:22,510 --> 00:10:26,710
>> Joten struct-tyyppinen
määritellä, kuten näette,

219
00:10:26,710 --> 00:10:29,470
se on hieman erilainen
mitä pino

220
00:10:29,470 --> 00:10:33,120
koska me emme vain täytyy pitää
Seuraa jossa koko tällä hetkellä on,

221
00:10:33,120 --> 00:10:37,420
haluamme myös seurata pään
sekä missä me tällä hetkellä olemme.

222
00:10:37,420 --> 00:10:39,580
Niin mielestäni se on helpompaa
jos piirrän tämän.

223
00:10:39,580 --> 00:10:53,270
Joten kuvitella meillä jono,
niin sanokaamme pää on täällä.

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

225
00:10:55,811 --> 00:10:58,310
Pään linja, katsotaanpa
vain sanoa, että on tällä hetkellä,

226
00:10:58,310 --> 00:11:01,809
ja haluamme lisätä
jotain jonoon.

227
00:11:01,809 --> 00:11:04,350
Aion soittaa koko olennaisesti
on sama asia kuin hännän,

228
00:11:04,350 --> 00:11:06,314
loppuun minne jono on.

229
00:11:06,314 --> 00:11:07,730
Sanotaan vain koko on täällä.

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

231
00:11:14,380 --> 00:11:18,400
>> Joten miten voidaan järkevästi
aseta jotain jonoon?

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

233
00:11:21,000 --> 00:11:24,130
Mitä indeksi haluamme sijoittaa
jossa haluamme lisätä osaksi.

234
00:11:24,130 --> 00:11:29,320
Jos tämä on alku oman
jono ja tämä on lopussa se

235
00:11:29,320 --> 00:11:31,860
tai koko se, missä me
haluavat lisätä seuraava kohde?

236
00:11:31,860 --> 00:11:32,920
>> Yleisö: [äänetön]

237
00:11:32,920 --> 00:11:35,920
ANDI Peng: Aivan, jonka haluat lisätä
se riippuu olet kirjoittanut sen.

238
00:11:35,920 --> 00:11:37,840
Joko tämä on tyhjä tai on tyhjä.

239
00:11:37,840 --> 00:11:42,630
Joten haluat lisätä sen luultavasti
tässä, koska jos koko is--

240
00:11:42,630 --> 00:11:50,540
jos nämä ovat kaikki täynnä, haluat
lisätä sen täällä, eikö?

241
00:11:50,540 --> 00:11:57,150
>> Ja niin se on, vaikka hyvin, hyvin
yksinkertainen, ei aivan aina oikein

242
00:11:57,150 --> 00:12:00,690
koska suurin ero
välillä jono ja pino

243
00:12:00,690 --> 00:12:04,350
on, että jono voi
itse asiassa voidaan käsitellä

244
00:12:04,350 --> 00:12:06,980
niin että pää muutokset
riippuen siitä, missä haluat

245
00:12:06,980 --> 00:12:08,650
alussa keppiin aloittaa.

246
00:12:08,650 --> 00:12:11,900
Ja sen seurauksena, teidän hännän
aikoo myös muuttaa.

247
00:12:11,900 --> 00:12:14,770
Ja niin vilkaise
tämä koodi juuri nyt.

248
00:12:14,770 --> 00:12:18,620
Kuten te pyydettiin myös
kirjoittaa ulos tietokilpailu, enqueue.

249
00:12:18,620 --> 00:12:22,580
Ehkä niin jutellaan läpi miksi
vastaus oli mitä se oli.

250
00:12:22,580 --> 00:12:26,790
>> En voinut oikein sovi tämän linjan yhdelle,
mutta pohjimmiltaan tämä koodinpätkä

251
00:12:26,790 --> 00:12:29,030
tulisi olla yhdellä rivillä.

252
00:12:29,030 --> 00:12:30,140
Vietä kuin 30 sekuntia.

253
00:12:30,140 --> 00:12:33,000
Katsomaan, ja miksi
tämä on niin, että se on.

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

255
00:12:50,030 --> 00:12:55,420
>> Hyvin, hyvin samankaltainen struct, hyvin, hyvin
samanlainen rakenne kuin edellinen

256
00:12:55,420 --> 00:12:58,090
pino paitsi ehkä
yhtä riviä koodia.

257
00:12:58,090 --> 00:13:01,190
Ja että yhtä riviä koodia
määrittelee toiminnot.

258
00:13:01,190 --> 00:13:03,900
Ja se todella erottelee
jono pinosta.

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

260
00:13:18,510 --> 00:13:22,010
>> Kukaan halua ottaa puukottaa
selittämään miksi olet

261
00:13:22,010 --> 00:13:24,980
sai tämän monimutkainen asia täällä?

262
00:13:24,980 --> 00:13:27,845
Näemme paluuta meidän
ihana ystävä moduuli.

263
00:13:27,845 --> 00:13:31,020
Kuten te tulevat pian
tunnistaa ohjelmoinnin,

264
00:13:31,020 --> 00:13:34,910
melkein milloin tarvitset jotain
kääri ympärille mitään,

265
00:13:34,910 --> 00:13:36,850
moduuli tulee olemaan tapa tehdä se.

266
00:13:36,850 --> 00:13:40,510
Tietäen, että ei kukaan halua
yrittää selittää että koodiriviä?

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

268
00:13:44,060 --> 00:13:47,507
Joo, kaikki vastaukset ovat
Hyväksytyt ja tervetuloa.

269
00:13:47,507 --> 00:13:48,840
Yleisö: Puhutko minulle?

270
00:13:48,840 --> 00:13:49,506
ANDI Peng: Joo.

271
00:13:49,506 --> 00:13:56,200
Yleisö: Voi ei anteeksi.

272
00:13:56,200 --> 00:14:00,250
ANDI Peng: OK, joten katsotaanpa
kävelee tämän koodin.

273
00:14:00,250 --> 00:14:03,642
Joten kun yrität
lisätä jotain päälle jono,

274
00:14:03,642 --> 00:14:08,510
ihanassa tapauksessa, että pää tapahtuu
olla täällä, se on hyvin helppoa meille

275
00:14:08,510 --> 00:14:10,960
vain mennä loppuun
lisätä jotain, eikö?

276
00:14:10,960 --> 00:14:14,690
Mutta idea jono on
että pää voi todella dynaamisesti

277
00:14:14,690 --> 00:14:17,280
muuttua riippuen missä
haluavat alku meidän Q olla,

278
00:14:17,280 --> 00:14:19,880
ja siten, hännän
aikoo myös muuttaa.

279
00:14:19,880 --> 00:14:31,100
>> Ja niin kuvitella, että tämä ei ollut
jonoon, vaan tämä oli jonossa.

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

281
00:14:37,900 --> 00:14:39,330
Sanotaan pää on täällä.

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

283
00:14:54,900 --> 00:14:56,980
Sanotaan meidän jono näytti tältä.

284
00:14:56,980 --> 00:15:00,190
Jos haluaisimme siirtää missä
rivin alussa on,

285
00:15:00,190 --> 00:15:03,400
sanokaamme muutimme pää
Näin ja kokoja täällä.

286
00:15:03,400 --> 00:15:07,100
>> Nyt haluamme lisätä jotain
tämä jono, mutta te voi nähdä,

287
00:15:07,100 --> 00:15:11,150
se ei ole niin yksinkertainen kuin vain
lisätä mitä on jälkeen koko

288
00:15:11,150 --> 00:15:13,630
koska silloin me loppuu
rajat meidän todellinen array.

289
00:15:13,630 --> 00:15:16,190
Jos haluamme todella lisätä on täällä.

290
00:15:16,190 --> 00:15:18,610
Se kauneus jonon
se meihin, visuaalisesti se

291
00:15:18,610 --> 00:15:22,380
näyttää linja menee näin,
mutta kun tallennetaan tietorakenteeseen,

292
00:15:22,380 --> 00:15:29,370
Ne antavat sille samankaltaisina sykli.

293
00:15:29,370 --> 00:15:32,360
Se ikään kuin kiertyy
eteen samalla tavalla

294
00:15:32,360 --> 00:15:34,780
että linja voi myös kääriä
noin riippuen missä tahansa

295
00:15:34,780 --> 00:15:36,279
haluavat alkuun linja on.

296
00:15:36,279 --> 00:15:38,630
Joten jos otamme
halveksua täällä, katsotaanpa

297
00:15:38,630 --> 00:15:40,880
sanoa halusimme luoda
toiminto nimeltään enqueue.

298
00:15:40,880 --> 00:15:43,980
Halusimme lisätä int n tuohon q.

299
00:15:43,980 --> 00:15:49,250
Jos q.size q-- soitamme että tietomme
structure-- jos meidän queue.size ei

300
00:15:49,250 --> 00:15:52,520
sama kapasiteetti tai jos
se on vähemmän kuin kapasiteetti,

301
00:15:52,520 --> 00:15:55,120
q.strings on joukko meidän q.

302
00:15:55,120 --> 00:15:58,380
Aiomme asettaa
että yhtä q.heads,

303
00:15:58,380 --> 00:16:02,730
joka on täällä, plus q.size
moduuli, jonka kapasiteetti, joka

304
00:16:02,730 --> 00:16:04,290
kääri meidät takaisin täällä.

305
00:16:04,290 --> 00:16:08,040
>> Joten tässä esimerkissä, indeksi
pään on 1, eikö?

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

307
00:16:11,480 --> 00:16:19,500
Joten voimme tehdä 1 plus 4 moduuli
meidän kapasiteetti, joka on 5.

308
00:16:19,500 --> 00:16:20,920
Mitä se antaa meille?

309
00:16:20,920 --> 00:16:23,270
Mikä on indeksi, joka
tulee ulos tästä?

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

311
00:16:24,080 --> 00:16:27,870
>> ANDI Peng: 0, joka
sattuu olemaan täällä,

312
00:16:27,870 --> 00:16:30,640
ja niin haluamme pystyä
lisättävän täällä.

313
00:16:30,640 --> 00:16:34,730
Ja niin tämä yhtälö täällä tällaista
vain toimii numeroita

314
00:16:34,730 --> 00:16:36,750
riippuen siitä, missä
pää ja kokosi ovat.

315
00:16:36,750 --> 00:16:38,541
Jos tiedät, mitä nämä
asiat ovat, tiedät

316
00:16:38,541 --> 00:16:43,170
tarkalleen missä haluat lisätä
mikä on sen jälkeen, kun jono.

317
00:16:43,170 --> 00:16:44,640
Tarkoittaako tämä järkevää kaikille?

318
00:16:44,640 --> 00:16:48,560
>> Tiedän eräänlainen aivojen
teaser varsinkin kun tämä

319
00:16:48,560 --> 00:16:50,512
tuli jälkimainingeissa tietokilpailun.

320
00:16:50,512 --> 00:16:52,220
Mutta toivottavasti kaikki
nyt voi ymmärtää

321
00:16:52,220 --> 00:16:57,800
miksi tämä ratkaisu tai tämä
toiminto on niin, että se on.

322
00:16:57,800 --> 00:16:59,840
Jokainen hieman epäselvä siitä?

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

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

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

326
00:17:07,109 --> 00:17:09,970
>> Ja nyt, jos
halusi dequeue, tämä

327
00:17:09,970 --> 00:17:15,240
on meidän pää olisi siirtymässä
koska jos me dequeue,

328
00:17:15,240 --> 00:17:17,030
emme ota pois loppuun q.

329
00:17:17,030 --> 00:17:19,130
Haluamme ottaa pois pään, eikö?

330
00:17:19,130 --> 00:17:24,260
Niin ollen, pää tulee muuttumaan,
ja siksi kun laittaa jonoon,

331
00:17:24,260 --> 00:17:26,800
sinulla seurata
missä päätäsi ja kokosi

332
00:17:26,800 --> 00:17:29,450
on voitava lisätä
oikeaan asentoon.

333
00:17:29,450 --> 00:17:32,740
>> Ja niin kun dequeue,
Olen myös pseudokoodilla sitä.

334
00:17:32,740 --> 00:17:35,480
Voit vapaasti, jos haluat
yrittää koodaat ulos.

335
00:17:35,480 --> 00:17:36,980
Haluat siirtää pään, eikö?

336
00:17:36,980 --> 00:17:39,320
Jos halusin dequeue, I
liikkuisi pään yli.

337
00:17:39,320 --> 00:17:40,800
Tämä olisi pää.

338
00:17:40,800 --> 00:17:45,617
>> Ja meidän nykyinen koko olisi
vähennä koska emme enää

339
00:17:45,617 --> 00:17:46,950
on neljä elementtiä jono.

340
00:17:46,950 --> 00:17:51,370
Meillä on vain kolme, ja sitten haluamme
palata mitä on tallennettu

341
00:17:51,370 --> 00:17:56,260
pään koska haluamme ottaa tämän
arvo ulos niin hyvin samanlainen kuin pino.

342
00:17:56,260 --> 00:17:58,010
Vain olet ottaen
eri paikasta,

343
00:17:58,010 --> 00:18:01,770
ja sinun täytyy siirtää osoitinta
eri paikka seurauksena.

344
00:18:01,770 --> 00:18:03,890
Loogisesti, jokainen seuraa?

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

346
00:18:05,690 --> 00:18:10,156
>> OK, joten me aiomme puhua vähän
syvemmin noin linkitettyjen listojen

347
00:18:10,156 --> 00:18:13,280
koska he ovat hyvin, hyvin arvokas
sinulle aikana tämän viikon

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

349
00:18:14,964 --> 00:18:17,130
Liittyy luettelot, kuten te
voi muistaa, kaikki ne ovat

350
00:18:17,130 --> 00:18:22,570
ovat solmuja, jotka ovat solmut tiettyjen
arvot sekä arvon ja osoitin

351
00:18:22,570 --> 00:18:26,290
jotka on linkitetty toisiinsa
näiden viitteitä.

352
00:18:26,290 --> 00:18:29,880
Ja niin struct miten
luomme solmu tässä me

353
00:18:29,880 --> 00:18:33,569
on int n, joka on mitä
arvo kaupassa tai merkkijono n

354
00:18:33,569 --> 00:18:35,610
tai mitä haluat
kutsuvat sitä, nieriä tähti n.

355
00:18:35,610 --> 00:18:41,482
Struct solmu tähti, joka on osoitin
että haluat olla kussakin solmussa,

356
00:18:41,482 --> 00:18:43,690
olet menossa on, että
osoitin kohta kohti seuraavaksi.

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

358
00:18:48,207 --> 00:18:50,040
Sinulla on pää
linkitetyn listan, joka on

359
00:18:50,040 --> 00:18:53,140
menossa kohta muualle
arvot niin edelleen ja niin edelleen

360
00:18:53,140 --> 00:18:55,290
kunnes lopulta päähän.

361
00:18:55,290 --> 00:18:58,040
Ja tämä viimeinen solmu on vain
menossa ole osoitin.

362
00:18:58,040 --> 00:18:59,952
Se tulee osoittamaan
null, ja silloin

363
00:18:59,952 --> 00:19:01,910
tiedät osuma
päättymiseen liittyvät luettelon

364
00:19:01,910 --> 00:19:04,076
on, kun viimeinen osoitin
ei osoita mitään.

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

366
00:19:06,670 --> 00:19:10,990
>> Joten aiomme mennä hieman enemmän
syvyys siitä, miten yksi olisi mahdollisesti

367
00:19:10,990 --> 00:19:12,400
etsi linkitetty lista.

368
00:19:12,400 --> 00:19:15,460
Muistakaa, mitä ovat joitakin
haitat liittyvät luettelot

369
00:19:15,460 --> 00:19:19,340
jakeet array koskien hakuja.

370
00:19:19,340 --> 00:19:22,565
Array voit binäärihaku, mutta
miksi et voi tehdä, että linkitetty lista?

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

372
00:19:26,834 --> 00:19:30,320
>> Yleisö: Koska he kaikki kytketty,
mutta et oikein tiedä missä

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

374
00:19:31,330 --> 00:19:34,600
>> ANDI Peng: Joo, juuri niin muistakaa
että loisto array

375
00:19:34,600 --> 00:19:37,190
oli se, että meillä oli
Random access memory jossa

376
00:19:37,190 --> 00:19:41,580
jos halusin arvo indeksin
kuusi, voisin vain sanoa indeksi kuusi,

377
00:19:41,580 --> 00:19:42,407
anna minulle, että arvo.

378
00:19:42,407 --> 00:19:45,240
Ja se johtuu paneelit lajitellaan
vuonna yhtenäistä tilaa muistia

379
00:19:45,240 --> 00:19:48,020
yhteen paikkaan, kun taas
Tällainen linkitettyjen listojen

380
00:19:48,020 --> 00:19:52,820
ovat satunnaisesti välissä ympäri,
ja ainoa tapa löytää yksi

381
00:19:52,820 --> 00:19:56,890
on kautta osoitin joka kertoo
osoite, jos tämä seuraava solmu on.

382
00:19:56,890 --> 00:20:00,290
>> Ja niin sen seurauksena, ainoa tapa
etsiä linkitetty lista

383
00:20:00,290 --> 00:20:01,560
on lineaarinen haku.

384
00:20:01,560 --> 00:20:05,890
Koska en tarkalleen tiedä missä
12. arvo linkitetty lista on,

385
00:20:05,890 --> 00:20:08,780
Minun täytyy kulkea kokonaisuudessaan
Tämän linkitetyn listan yhden

386
00:20:08,780 --> 00:20:12,450
yhden pään ensimmäiselle solmulle,
toiselle solmulle, kolmanteen solmuun,

387
00:20:12,450 --> 00:20:17,690
kaikki alas kunnes lopulta saada
missä että solmu etsin on.

388
00:20:17,690 --> 00:20:22,110
Ja niin tässä mielessä, haku
on linkitetty lista on aina n.

389
00:20:22,110 --> 00:20:23,040
Se on aina n.

390
00:20:23,040 --> 00:20:25,690
Se on aina lineaarisessa ajassa.

391
00:20:25,690 --> 00:20:28,470
>> Ja niin -koodi, jossa
toteutamme tätä, ja tämä

392
00:20:28,470 --> 00:20:32,620
on vähän uutta te koska te
kaverit ovat ei oikeastaan ​​puhuneet tai koskaan

393
00:20:32,620 --> 00:20:35,000
nähty viitteitä miten
etsiä viitteitä,

394
00:20:35,000 --> 00:20:37,670
niin me kulkea
tämä hyvin, hyvin hitaasti.

395
00:20:37,670 --> 00:20:40,200
Joten bool haku, oikea,
Kuvitellaan haluamme

396
00:20:40,200 --> 00:20:42,820
luoda toiminto nimeltään
haku, joka palauttaa true

397
00:20:42,820 --> 00:20:46,820
jos olet löytänyt arvo sisällä liittyvät
luettelo, ja se palauttaa false muutoin.

398
00:20:46,820 --> 00:20:50,030
Solmu tähti lista on
tällä hetkellä vain osoitin

399
00:20:50,030 --> 00:20:52,960
on ensimmäinen kohde linkitetty lista.

400
00:20:52,960 --> 00:20:56,700
int n on arvo, että olet
etsivät luetteloon.

401
00:20:56,700 --> 00:20:58,770
>> Joten solmu tähden osoitin vastaa lista.

402
00:20:58,770 --> 00:21:00,970
Tämä tarkoittaa, että me asetetaan
ja luoda osoitin

403
00:21:00,970 --> 00:21:03,592
tähän ensimmäiseen solmuun sisällä luettelon.

404
00:21:03,592 --> 00:21:04,300
Jokainen kanssani?

405
00:21:04,300 --> 00:21:06,530
Joten jos me mennä
takaisin tänne, olisin

406
00:21:06,530 --> 00:21:13,850
alustettu osoitin, joka osoittaa
johtaja mitä se lista on.

407
00:21:13,850 --> 00:21:18,600
>> Ja sitten kun saat tänne,
vaikka osoitin ei ole sama null,

408
00:21:18,600 --> 00:21:22,160
niin että on silmukka, jossa olemme
olemaan myöhemmin liikkumisesta

409
00:21:22,160 --> 00:21:25,940
loput meidän luettelosta, koska mitä
tapahtuu, kun osoitin vastaa null?

410
00:21:25,940 --> 00:21:27,550
Tiedämme, että meillä have--

411
00:21:27,550 --> 00:21:28,450
>> Yleisö: [äänetön]

412
00:21:28,450 --> 00:21:31,491
>> ANDI Peng: Aivan, niin me tiedämme, että
olemme päättynyt luettelon, eikö?

413
00:21:31,491 --> 00:21:34,470
Jos menet takaisin tänne, jokainen solmu
olisi osoittaa toiseen solmuun

414
00:21:34,470 --> 00:21:36,550
ja niin edelleen ja niin edelleen
kunnes osut lopulta

415
00:21:36,550 --> 00:21:41,589
pyrstö oman linkitetyn listan,
joka on osoitin, joka vain

416
00:21:41,589 --> 00:21:43,130
ei osoita muualla kuin ei.

417
00:21:43,130 --> 00:21:47,510
Ja niin et periaatteessa tietää, että
luettelo on vielä siellä ylös

418
00:21:47,510 --> 00:21:50,900
kunnes osoitin ei vastaa
null koska kun se vastaa null,

419
00:21:50,900 --> 00:21:53,310
tiedät, että ei ole enemmän tavaraa.

420
00:21:53,310 --> 00:21:56,930
>> Niin että on silmukka, jossa olemme
menossa on todellinen haku.

421
00:21:56,930 --> 00:22:01,690
Ja jos pointer-- näette
sellainen nuolen toiminta siellä?

422
00:22:01,690 --> 00:22:06,930
Joten jos osoitin osoittaa n, jos
osoitin n on yhtä suuri kuin n,

423
00:22:06,930 --> 00:22:09,180
niin se tarkoittaa, että jos
osoitin, että olet

424
00:22:09,180 --> 00:22:13,420
hakevat jokaisen
solmu on todella arvoa

425
00:22:13,420 --> 00:22:15,990
etsit sitten
haluat palata totta.

426
00:22:15,990 --> 00:22:19,280
Joten periaatteessa, jos olet solmu, joka
on arvo, jota etsit,

427
00:22:19,280 --> 00:22:23,550
tiedät, että olet ollut
onnistuneesti etsiä.

428
00:22:23,550 --> 00:22:27,150
>> Muuten haluat asettaa
osoitin seuraavaan solmuun.

429
00:22:27,150 --> 00:22:28,850
Sitä, että linja täällä tekee.

430
00:22:28,850 --> 00:22:31,750
Pointer vastaa osoitin seuraavaksi.

431
00:22:31,750 --> 00:22:33,360
Kaikkien nähdä, miten tämä työskentelee?

432
00:22:33,360 --> 00:22:36,580
>> Ja pohjimmiltaan aiot vain
kulkea koko luettelon,

433
00:22:36,580 --> 00:22:41,920
nollaus osoitin aina kunnes
te lopulta osuma luettelon loppuun.

434
00:22:41,920 --> 00:22:45,030
Ja te tiedätte, että ei ole olemassa
lisää solmut etsiä,

435
00:22:45,030 --> 00:22:47,999
ja sitten voit palata false
koska tiedät, että, oi, hyvin,

436
00:22:47,999 --> 00:22:50,540
jos olen voinut etsiä
kautta koko luettelon.

437
00:22:50,540 --> 00:22:54,530
Jos tässä esimerkissä, jos halusin
etsiä arvon 10,

438
00:22:54,530 --> 00:22:57,250
ja aloitan kärjessä, ja
Etsin kokonaan alas,

439
00:22:57,250 --> 00:23:00,550
ja minä lopulta sai tähän, joka
osoitin, joka osoittaa null,

440
00:23:00,550 --> 00:23:04,415
Tiedän että, paska, kai 10 ei ole
tämä lista koska en löytänyt sitä.

441
00:23:04,415 --> 00:23:06,520
Ja olen lopussa luettelosta.

442
00:23:06,520 --> 00:23:11,040
Ja jolloin tiedät
Aion return false.

443
00:23:11,040 --> 00:23:12,900
>> Anna että imeytyä vähän.

444
00:23:12,900 --> 00:23:17,350
Tämä on melko
tärkeää teidän PSET.

445
00:23:17,350 --> 00:23:21,140
Logiikka se on hyvin yksinkertainen, ehkä
syntaktisesti vain sen toteuttamisesta.

446
00:23:21,140 --> 00:23:23,365
Te halua tehdä
Varmista, että ymmärrät.

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

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

449
00:23:27,650 --> 00:23:32,560
>> OK, joten miten olisimme
lisäämällä solmuja, oikea,

450
00:23:32,560 --> 00:23:35,380
listaan, koska muistaa
mitkä ovat mitä etuja

451
00:23:35,380 --> 00:23:39,230
ottaa linkitetty lista vs.
joukko kannalta tallennustilaa?

452
00:23:39,230 --> 00:23:41,110
>> Yleisö: Se on dynaaminen,
joten se on helpompaa to--

453
00:23:41,110 --> 00:23:43,180
>> ANDI Peng: Aivan,
joten se on dynaaminen, joka

454
00:23:43,180 --> 00:23:46,880
tarkoittaa, että se voi laajentua ja kutistua
riippuen käyttäjän tarpeiden.

455
00:23:46,880 --> 00:23:56,570
Ja niin, tässä mielessä, emme tarvitse
tuhlata tarpeettomia muistin koska en

456
00:23:56,570 --> 00:24:00,850
jos en tiedä kuinka monta arvot haluan
tallentaa, se ei ole järkeä minulle

457
00:24:00,850 --> 00:24:04,310
luoda array koska
jos haluan tallentaa 10 arvoa

458
00:24:04,310 --> 00:24:08,380
ja luon joukko 1000, se
paljon hukkaan muistia, luovutetaan.

459
00:24:08,380 --> 00:24:11,180
Siksi haluamme käyttää linkitetty
luettelo voi dynaamisesti

460
00:24:11,180 --> 00:24:13,860
muuttaa tai kutistua meidän koko.

461
00:24:13,860 --> 00:24:17,040
>> Ja niin että tekee lisäys
hieman monimutkaisempi.

462
00:24:17,040 --> 00:24:20,810
Koska emme voi satunnaisesti käyttää elementtejä
että olisimme array.

463
00:24:20,810 --> 00:24:24,270
Jos haluan lisätä elementin
seitsemänteen indeksi,

464
00:24:24,270 --> 00:24:26,930
En vain voi lisätä sen
seitsemänteen indeksiin.

465
00:24:26,930 --> 00:24:30,020
On linkitetty lista, se ei
melko työtä yhtä helposti,

466
00:24:30,020 --> 00:24:34,947
joten jos halusimme lisätä
yksi täällä linkitetty lista,

467
00:24:34,947 --> 00:24:36,280
visuaalisesti, se on erittäin helppo nähdä.

468
00:24:36,280 --> 00:24:39,363
Me vain haluamme lisätä sen oikeassa,
heti alussa luettelon,

469
00:24:39,363 --> 00:24:40,840
heti pään.

470
00:24:40,840 --> 00:24:44,579
>> Mutta tapa, jolla meidän täytyy siirtää
viitteitä on hieman sekava

471
00:24:44,579 --> 00:24:47,620
tai, loogisesti, on järkevää, mutta
haluat varmistaa, että sinulla on se

472
00:24:47,620 --> 00:24:50,250
täysin alas, koska
viimeinen asia, jonka haluat

473
00:24:50,250 --> 00:24:52,990
on siirtämiseksi osoitin
siten, että teemme täällä.

474
00:24:52,990 --> 00:24:58,170
Jos dereference
osoitin päästä 1,

475
00:24:58,170 --> 00:25:01,086
sitten yhtäkkiä
loppuelämäsi linkitetty lista

476
00:25:01,086 --> 00:25:04,680
on menetetty, koska et ole itse
luotu väliaikainen mitään.

477
00:25:04,680 --> 00:25:06,220
Joka on osoitti 2.

478
00:25:06,220 --> 00:25:10,080
Jos asiakas määrittää osoitin, sitten
loput listasi on täysin menetetty.

479
00:25:10,080 --> 00:25:13,310
Joten haluat olla
hyvin, hyvin varovaisia ​​tässä

480
00:25:13,310 --> 00:25:17,010
ensin määrittää
osoittimen mitä

481
00:25:17,010 --> 00:25:20,150
haluat lisätä osaksi missä
haluat, ja sitten

482
00:25:20,150 --> 00:25:22,710
voi dereference loput listasi.

483
00:25:22,710 --> 00:25:25,250
>> Joten tämä koskee missä
yrität lisättävän.

484
00:25:25,250 --> 00:25:27,520
Jos haluat lisätä at
pää, jos haluat vastata täällä,

485
00:25:27,520 --> 00:25:29,455
jos haluat lisätä at
loppuun, hyvin, loppujen lopuksi

486
00:25:29,455 --> 00:25:30,910
kai olisi vain
ei ole osoitin, mutta sinä

487
00:25:30,910 --> 00:25:33,830
haluat varmistaa, että et
menettää loput listasi.

488
00:25:33,830 --> 00:25:36,640
Haluat aina varmistaa
uusi solmu osoittaa

489
00:25:36,640 --> 00:25:39,330
kohti mitä
haluat lisätä osaksi,

490
00:25:39,330 --> 00:25:42,170
ja voit lisätä ketjuttamalla päälle.

491
00:25:42,170 --> 00:25:43,330
Jokainen selvä?

492
00:25:43,330 --> 00:25:45,427
>> Tämä tulee olemaan
yksi todellinen kysymyksiä.

493
00:25:45,427 --> 00:25:48,010
Yksi tärkeistä kysymyksistä
olet menossa on teidän PSET

494
00:25:48,010 --> 00:25:51,340
on, että aiot yrittää luoda
linkitetty lista ja insertti asiat

495
00:25:51,340 --> 00:25:53,340
mutta sitten vain menettää
loppuelämäsi linkitetyn listan.

496
00:25:53,340 --> 00:25:54,900
Ja aiot olla, minä
en tiedä miksi näin tapahtuu?

497
00:25:54,900 --> 00:25:58,040
Ja se on kipu mennä läpi
ja etsiä kaikki osoittimia.

498
00:25:58,040 --> 00:26:02,100
>> Ja voin taata teille tässä PSET,
kirjoittaminen ja piirtäminen näiden solmujen ulos

499
00:26:02,100 --> 00:26:03,344
on erittäin, erittäin hyödyllistä.

500
00:26:03,344 --> 00:26:06,010
Joten voit täysin seurata
missä kaikki osoittimet ovat,

501
00:26:06,010 --> 00:26:08,540
mikä on vialla,
jossa kaikki solmut ovat,

502
00:26:08,540 --> 00:26:12,660
mitä sinun tarvitsee tehdä käyttää tai
lisätä tai poistaa tai jokin niistä.

503
00:26:12,660 --> 00:26:14,550
Jokainen hyvä, että?

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

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

506
00:26:19,300 --> 00:26:22,600
>> Joten jos halusimme katsoa koodi?

507
00:26:22,600 --> 00:26:24,470
Voi, en tiedä, jos me
voi nähdä the-- OK, niin

508
00:26:24,470 --> 00:26:27,940
huipulla kaikki se on on funktio
nimeltään insertti jossa haluamme

509
00:26:27,940 --> 00:26:31,365
lisätä int n osaksi linkitetty lista.

510
00:26:31,365 --> 00:26:32,740
Me aiomme kulkea tämän.

511
00:26:32,740 --> 00:26:34,770
Se on paljon koodia, paljon uusia syntaksin.

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

513
00:26:36,220 --> 00:26:39,120
>> Joten ylös huipulla, kun
haluamme luoda mitään

514
00:26:39,120 --> 00:26:42,380
mitä meidän täytyy tehdä, varsinkin jos
haluavat sen ei tallenneta pino

515
00:26:42,380 --> 00:26:43,920
mutta kasaan?

516
00:26:43,920 --> 00:26:45,460
Käymme malloc, eikö?

517
00:26:45,460 --> 00:26:48,240
Joten aiomme luoda osoitin.

518
00:26:48,240 --> 00:26:52,074
Solmu, osoitin, uusi tasavertaisten
malloc koko solmun

519
00:26:52,074 --> 00:26:53,740
koska haluamme, että solmu luotava.

520
00:26:53,740 --> 00:26:56,720
Haluamme määrä
muisti että solmu vie

521
00:26:56,720 --> 00:26:59,300
aiotaan luovuttaa varten
luominen uusi solmu.

522
00:26:59,300 --> 00:27:02,270
>> Ja sitten me aiomme tarkistaa
onko uusia tasavertaisten vastaa null.

523
00:27:02,270 --> 00:27:03,370
Muistakaa mitä sanoimme?

524
00:27:03,370 --> 00:27:06,470
Mitä ikinä malloc,
mitä on aina teet?

525
00:27:06,470 --> 00:27:09,490
Sinun täytyy aina tarkistaa,
onko se on nolla.

526
00:27:09,490 --> 00:27:13,620
>> Esimerkiksi, jos käyttöjärjestelmä
järjestelmä oli aivan täynnä,

527
00:27:13,620 --> 00:27:17,060
jos sinulla ei ollut enemmän muistia
kaikki ja yrität malloc,

528
00:27:17,060 --> 00:27:18,410
se palaisi null sinulle.

529
00:27:18,410 --> 00:27:21,094
Joten jos yrität käyttää sitä
kun se osoittaa null,

530
00:27:21,094 --> 00:27:23,260
et aio pysty
käyttää näitä tietoja.

531
00:27:23,260 --> 00:27:27,010
Ja niin sellaisenaan, halusimme tehdä
Varmista, että kun olet mallocing,

532
00:27:27,010 --> 00:27:30,500
olet aina tarkistaa, jos
että muisti annettu sinulle on null.

533
00:27:30,500 --> 00:27:33,670
Ja jos se ei ole, niin voimme siirtyä
kanssa loput meidän koodi.

534
00:27:33,670 --> 00:27:36,140
>> Joten aiomme
alustaa uusi solmu.

535
00:27:36,140 --> 00:27:39,050
Aiomme tehdä uusi n on n.

536
00:27:39,050 --> 00:27:42,390
Ja sitten me aiomme tehdä
asettaa uusia osoitin uusi

537
00:27:42,390 --> 00:27:46,900
null koska nyt emme
halua mitään sen osoittamaan.

538
00:27:46,900 --> 00:27:48,755
Meillä ei ole aavistustakaan missä
se tulee laittaa sinut,

539
00:27:48,755 --> 00:27:50,630
ja sitten jos haluamme
aseta se kärjessä,

540
00:27:50,630 --> 00:27:53,820
voimme siirtää
osoitin päähän.

541
00:27:53,820 --> 00:27:58,530
Onko jokainen seuraa logiikkaa
missä se tapahtuu?

542
00:27:58,530 --> 00:28:02,502
>> Kaikki me teemme on luomassa uutta
solmu, jossa osoitin null,

543
00:28:02,502 --> 00:28:04,210
ja sitten uudelleen kohdentamisesta
se päähän, jos me

544
00:28:04,210 --> 00:28:06,320
tietää haluamme lisätä sen kärjessä.

545
00:28:06,320 --> 00:28:09,420
Ja sitten pää on menossa
kohta kohti että uusi solmu.

546
00:28:09,420 --> 00:28:11,060
Jokainen OK kanssa?

547
00:28:11,060 --> 00:28:12,380
>> Joten se on kaksivaiheinen prosessi.

548
00:28:12,380 --> 00:28:14,760
Sinun täytyy ensin assign
mitä luot.

549
00:28:14,760 --> 00:28:18,260
Aseta että osoitin
viite, ja sitten

550
00:28:18,260 --> 00:28:21,400
voi sellaista dereference
ensimmäinen osoitin

551
00:28:21,400 --> 00:28:22,972
ja kohta se kohti uusi solmu.

552
00:28:22,972 --> 00:28:25,680
Minne haluat lisätä sen,
että logiikka on menossa pitävät paikkansa.

553
00:28:25,680 --> 00:28:27,530
>> Se on ikään kuin osoitetaan
väliaikainen muuttujat.

554
00:28:27,530 --> 00:28:28,700
Muista, sinulla
varmista, että olet

555
00:28:28,700 --> 00:28:30,346
älä katoaa jos olet vaihtamalla.

556
00:28:30,346 --> 00:28:33,470
Haluat varmistaa, että sinulla on
väliaikainen muuttuja sellainen pitää

557
00:28:33,470 --> 00:28:35,620
kirjaa kun tämä asia
on säilytettävä niin, että voit

558
00:28:35,620 --> 00:28:41,190
eivät menetä mitään arvoa kurssin
samankaltaisten kikkailunsa sen.

559
00:28:41,190 --> 00:28:42,710
>> OK, joten koodi on täällä.

560
00:28:42,710 --> 00:28:45,020
Te katsomaan jakson jälkeen.

561
00:28:45,020 --> 00:28:48,060
Se on siellä.

562
00:28:48,060 --> 00:28:50,280
>> Joten kai miten
tämä eroaa jos haluaisimme

563
00:28:50,280 --> 00:28:52,300
lisätä keskelle tai loppuun?

564
00:28:52,300 --> 00:28:57,892
Onko kellään aavistustakaan siitä, mitä on
pseudokoodia loogisena viite

565
00:28:57,892 --> 00:29:00,350
että ryhtyisimme jos haluaisimme
lisätä sen keskellä?

566
00:29:00,350 --> 00:29:03,391
Joten jos halusimme aseta se
pää, kaikki mitä teemme on luoda uusi solmu.

567
00:29:03,391 --> 00:29:06,311
Asetimme osoitin kyseisen
uusi solmu mihin tahansa päähän,

568
00:29:06,311 --> 00:29:08,310
ja sitten asetamme pää
uuteen solmuun, eikö?

569
00:29:08,310 --> 00:29:11,560
Jos halusimme lisätä sen keskellä
luettelon, mitä meidän on tehtävä?

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

571
00:29:14,108 --> 00:29:16,110
>> Yleisö: se silti
olla samanlainen prosessi

572
00:29:16,110 --> 00:29:19,114
samankaltaisten määrittämällä osoittimen ja
sitten antaa tämä osoitin,

573
00:29:19,114 --> 00:29:20,530
mutta meidän olisi paikantaa siellä.

574
00:29:20,530 --> 00:29:23,560
>> ANDI Peng: Aivan, niin täsmälleen
sama prosessi paitsi sinä

575
00:29:23,560 --> 00:29:27,820
täytyy etsiä missä tarkalleen olet
haluavat, että uuden osoittimen mennä,

576
00:29:27,820 --> 00:29:44,790
joten jos haluan lisätä osaksi
keskellä liittyvät list-- OK,

577
00:29:44,790 --> 00:29:46,370
sanotaan, että on meidän linkitetty lista.

578
00:29:46,370 --> 00:29:49,500
Jos haluamme lisätä sen täällä,
aiomme luoda uusi solmu.

579
00:29:49,500 --> 00:29:50,520
Aiomme malloc.

580
00:29:50,520 --> 00:29:52,220
Aiomme luoda uusi solmu.

581
00:29:52,220 --> 00:29:55,940
Aiomme antaa
osoitin tämän solmun täällä.

582
00:29:55,940 --> 00:29:58,335
>> Mutta ongelma, joka poikkeaa
josta pää on

583
00:29:58,335 --> 00:30:00,490
on, että me tiesimme tarkalleen
jossa pää on.

584
00:30:00,490 --> 00:30:01,930
Se oli aivan ensimmäinen, eikö?

585
00:30:01,930 --> 00:30:04,870
Mutta tässä meidän täytyy seurata
missä olemme sen laittamista.

586
00:30:04,870 --> 00:30:07,930
Jos me asetat meidän
solmu täällä, meillä

587
00:30:07,930 --> 00:30:12,270
varmistaa, että
yksi aiempi tähän solmuun

588
00:30:12,270 --> 00:30:14,172
on yksi että reassigns osoitin.

589
00:30:14,172 --> 00:30:16,380
Joten sitten on sellainen
seurata kaksi asiaa.

590
00:30:16,380 --> 00:30:19,420
Jos seurata missä tämän
solmu tällä hetkellä on laitat ne.

591
00:30:19,420 --> 00:30:23,280
Sinun on myös seurata, missä
edellinen solmu että etsit

592
00:30:23,280 --> 00:30:24,340
oli myös siellä.

593
00:30:24,340 --> 00:30:25,830
Jokainen hyvä, että?

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

595
00:30:26,500 --> 00:30:28,000
>> Entä lisäämällä osaksi loppuun?

596
00:30:28,000 --> 00:30:34,220
Jos halusin lisätä sen here-- jos halusin
lisätä uusi solmu loppuun luettelon,

597
00:30:34,220 --> 00:30:37,009
miten voisin mennä noin tekee, että?

598
00:30:37,009 --> 00:30:39,300
Yleisö: Eli tällä hetkellä,
viime yksi osoitti null.

599
00:30:39,300 --> 00:30:40,960
ANDI Peng: Joo.

600
00:30:40,960 --> 00:30:43,560
Tarkalleen, niin tämä yksi
tällä hetkellä on suunnattu tietää,

601
00:30:43,560 --> 00:30:46,720
ja niin kai, tässä mielessä se on
erittäin helppo lisätä luettelon loppuun.

602
00:30:46,720 --> 00:30:51,810
Kaikki mitä sinun tarvitsee tehdä on asettaa se
yhtä null ja sitten boom.

603
00:30:51,810 --> 00:30:53,070
Oikeassa, erittäin helppo.

604
00:30:53,070 --> 00:30:53,960
Hyvin yksinkertainen.

605
00:30:53,960 --> 00:30:56,430
>> Hyvin samankaltainen kuin
pää, mutta loogisesti sinä

606
00:30:56,430 --> 00:30:59,690
haluat varmistaa, että vaiheet
otat kohti teet mitään tällaista,

607
00:30:59,690 --> 00:31:01,500
olet seuraava pitkin.

608
00:31:01,500 --> 00:31:04,420
Se on erittäin helppo, keskellä
koodistasi, saada kiinni,

609
00:31:04,420 --> 00:31:05,671
Voi, minulla niin paljon viitteitä.

610
00:31:05,671 --> 00:31:07,461
En tiedä missä
jotain on osoittaa.

611
00:31:07,461 --> 00:31:09,170
En edes tiedä mikä solmu olen.

612
00:31:09,170 --> 00:31:11,490
Mitä on meneillään?

613
00:31:11,490 --> 00:31:13,620
>> Rentoudu, rauhoitu, vetäkää syvään henkeä.

614
00:31:13,620 --> 00:31:15,530
Vetää ulos linkitetyn listan.

615
00:31:15,530 --> 00:31:18,800
Jos sanot, tiedän missä tarkalleen
Minun täytyy lisätä tämän huomioon

616
00:31:18,800 --> 00:31:22,970
ja tiedän tarkalleen, miten siirtää minun
osoittimia, paljon, paljon helpompi kuva

617
00:31:22,970 --> 00:31:27,200
out-- paljon, paljon helpompaa ei
eksyä vikoja koodistasi.

618
00:31:27,200 --> 00:31:29,410
Jokainen OK kanssa?

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

620
00:31:31,380 --> 00:31:35,120
>> Joten kai käsite, meillä ei
todella puhui ennen nyt,

621
00:31:35,120 --> 00:31:38,131
ja kai luultavasti
ei kohdata paljon yet--

622
00:31:38,131 --> 00:31:40,880
se on tavallaan kehittynyt concept--
on, että meillä on todellakin tiedot

623
00:31:40,880 --> 00:31:43,900
rakenne kutsutaan kaksin verroin linkitetty lista.

624
00:31:43,900 --> 00:31:46,390
Niin te voi nähdä,
kaikki teemme on luoda

625
00:31:46,390 --> 00:31:50,400
todellinen arvo, ylimääräinen
osoitin jokaisen meidän solmujen

626
00:31:50,400 --> 00:31:52,660
että myös viittaa edelliseen solmuun.

627
00:31:52,660 --> 00:31:58,170
Joten ei vain meillä on meidän
solmut viittaavat seuraavaan.

628
00:31:58,170 --> 00:32:01,430
Ne viittaavat myös edelliseen.

629
00:32:01,430 --> 00:32:04,310
Aion jättää nämä kaksi nyt.

630
00:32:04,310 --> 00:32:06,740
>> Joten sitten on ketju
jotka voivat liikkua molempiin suuntiin,

631
00:32:06,740 --> 00:32:09,630
ja sitten se on hieman helpompaa
loogisesti seurata pitkin.

632
00:32:09,630 --> 00:32:11,896
Kuten täällä, sen sijaan
pitää seurata, oi, minä

633
00:32:11,896 --> 00:32:14,520
täytyy tietää, että tämä solmu on
joka minun täytyy siirtää,

634
00:32:14,520 --> 00:32:17,532
Voin vain mennä täällä ja
vain vetää edellinen.

635
00:32:17,532 --> 00:32:19,490
Silloin tiedän tarkalleen missä
että on, ja sitten

636
00:32:19,490 --> 00:32:21,130
ei tarvitse kulkea
kokonaisuudessaan linkitetyn listan.

637
00:32:21,130 --> 00:32:22,180
Se on hieman helpompaa.

638
00:32:22,180 --> 00:32:24,960
>> Mutta sinänsä, sinulla on kaksin verroin
määrän osoittimia,

639
00:32:24,960 --> 00:32:26,960
se kaksinkertainen määrä muistia.

640
00:32:26,960 --> 00:32:28,950
Se on paljon viitteitä seurata.

641
00:32:28,950 --> 00:32:32,140
Se on hieman monimutkaisempi, mutta se on
hieman käyttäjäystävällisempi riippuen

642
00:32:32,140 --> 00:32:34,080
mitä yrität saavuttaa.

643
00:32:34,080 --> 00:32:36,910
>> Joten tämäntyyppisiä tietoja
rakenne täysin olemassa,

644
00:32:36,910 --> 00:32:40,280
ja rakenne on hyvin, hyvin
yksinkertainen paitsi kaikki sinulla on on,

645
00:32:40,280 --> 00:32:43,850
eikä vain osoitin seuraavaan,
sinulla on myös osoittimen edelliseen.

646
00:32:43,850 --> 00:32:45,940
Siinä kaikki ero oli.

647
00:32:45,940 --> 00:32:47,740
Jokainen hyvä, että?

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

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

650
00:32:50,940 --> 00:32:53,280
>> Hyvä on, joten nyt olen
todella viettää luultavasti

651
00:32:53,280 --> 00:32:56,870
kuten 15-20 minuuttia tai irtotavarana
muun ajan jaksossa

652
00:32:56,870 --> 00:32:58,360
puhumme hash taulukoita.

653
00:32:58,360 --> 00:33:02,590
Kuinka moni teistä kaverit
lukenut pset5 spec?

654
00:33:02,590 --> 00:33:03,620
Hyvä, hyvä.

655
00:33:03,620 --> 00:33:06,160
Se on suurempi kuin 50% normaalisti.

656
00:33:06,160 --> 00:33:07,560
Se on ok.

657
00:33:07,560 --> 00:33:10,345
>> Niin te näet,
olet haaste pset5

658
00:33:10,345 --> 00:33:16,790
on toteuttaa sanakirja
jossa lataat yli 140000 sanoja

659
00:33:16,790 --> 00:33:20,610
että annamme sinulle ja oikeinkirjoituksen tarkistus
se vastaan ​​koko tekstin.

660
00:33:20,610 --> 00:33:22,580
Annamme sinulle satunnainen
kappaletta kirjallisuuden.

661
00:33:22,580 --> 00:33:23,520
Annamme sinulle Odyssey.

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

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

664
00:33:26,350 --> 00:33:28,220
>> Ja teidän haaste
on oikeinkirjoituksen tarkistus

665
00:33:28,220 --> 00:33:31,760
jokainen sana kaikissa
näistä sanakirjoja

666
00:33:31,760 --> 00:33:34,960
olennaisesti meidän oikeinkirjoituksen tarkistus.

667
00:33:34,960 --> 00:33:38,620
Ja niin siellä on muutamia osia
luoda tämän PSET,

668
00:33:38,620 --> 00:33:41,970
ensimmäinen haluat olla
pystyy todella ladata

669
00:33:41,970 --> 00:33:43,970
kaikki sanat omalle
sanakirja, ja sitten

670
00:33:43,970 --> 00:33:45,530
haluavat pystyä
oikeinkirjoituksen tarkistus ne kaikki.

671
00:33:45,530 --> 00:33:48,780
Ja niin sellaisenaan, olet menossa vaatia
tietorakenne, joka voi tehdä tämän nopeasti

672
00:33:48,780 --> 00:33:50,790
ja tehokkaasti ja dynaamisesti.

673
00:33:50,790 --> 00:33:52,900
>> Joten kai helpoin
tapa tehdä tämä, te

674
00:33:52,900 --> 00:33:55,010
todennäköisesti luo runsaasti, eikö?

675
00:33:55,010 --> 00:33:58,910
Helpoin tapa tallennustilaa on sinua
voi luoda joukko 140000 sanoja

676
00:33:58,910 --> 00:34:03,400
ja juuri laita ne kaikki siellä ja
sitten kulkea ne binäärihaku

677
00:34:03,400 --> 00:34:06,780
tai valintoja tai not--
pahoillani, että on lajittelua.

678
00:34:06,780 --> 00:34:10,729
Ne voidaan järjestää ja sitten kulkea niitä
binäärilisäyksellä haku tai vain lineaarinen haku

679
00:34:10,729 --> 00:34:13,730
ja vain lopullinen sanoja, mutta että
vie valtavasti muistia,

680
00:34:13,730 --> 00:34:15,190
ja se ei ole kovin tehokas.

681
00:34:15,190 --> 00:34:18,350
>> Ja niin aiomme aloittaa
puhumme tapoja

682
00:34:18,350 --> 00:34:20,110
meidän käyntiaika tehokkaampi.

683
00:34:20,110 --> 00:34:23,190
Ja tavoitteenamme on saada
vakio aika missä

684
00:34:23,190 --> 00:34:25,810
se on melkein kuin paneelit, jossa
sinulla on hetkellinen pääsy.

685
00:34:25,810 --> 00:34:28,560
Jos halusin etsiä mitään,
Haluan pystyä vain,

686
00:34:28,560 --> 00:34:30,810
puomi, löytää se tarkalleen, ja vedä se ulos.

687
00:34:30,810 --> 00:34:34,100
Ja niin rakenne, jossa
me voidaan tulossa erittäin lähellä

688
00:34:34,100 --> 00:34:37,569
pystyä käyttämään vakio
aika, tämä pyhä Graal

689
00:34:37,569 --> 00:34:41,370
ohjelmointiin jatkuvasti
aikaa kutsutaan hajautustaulua.

690
00:34:41,370 --> 00:34:45,370
Ja niin David aiemmin mainittu
[Äänetön] vähän luento,

691
00:34:45,370 --> 00:34:49,100
mutta aiomme todella
sukeltaa syvälle tällä viikolla

692
00:34:49,100 --> 00:34:51,780
pala, joka on koskevat
miten hash table toimii.

693
00:34:51,780 --> 00:34:53,949
>> Niin että hajautus
pöytä teoksia, esimerkiksi,

694
00:34:53,949 --> 00:35:00,230
jos halusin tallentaa joukko sanoja,
nippu sanoja Englanti kielellä,

695
00:35:00,230 --> 00:35:02,940
Voisin teoriassa laittaa
banaani, omena, kiivi, mango, pari,

696
00:35:02,940 --> 00:35:04,980
ja cantaloupe kaikki vain array.

697
00:35:04,980 --> 00:35:07,044
Ne voisivat kaikki mahtuvat ja voidaan löytää.

698
00:35:07,044 --> 00:35:09,210
Se olisi eräänlainen kipua
etsiä ja pääsy,

699
00:35:09,210 --> 00:35:12,920
mutta helpompi tapa tehdä tämä on
että voimme luoda todella rakenne

700
00:35:12,920 --> 00:35:15,680
kutsutaan hash table jossa hash.

701
00:35:15,680 --> 00:35:19,880
Otamme kaikki meidän avaimet kautta
hajautusfunktio, yhtälö,

702
00:35:19,880 --> 00:35:22,600
joka muuttaa ne kaikki
jonkinlainen arvo

703
00:35:22,600 --> 00:35:28,740
että voimme tallenna
olennaisesti erilaisia ​​linkitetyn listan.

704
00:35:28,740 --> 00:35:32,570
>> Ja niin tässä, jos haluaisimme
tallentaa Englanti sanat,

705
00:35:32,570 --> 00:35:37,250
voisimme mahdollisesti vain, en
tietää, käännä kaikki ensimmäiset kirjaimet

706
00:35:37,250 --> 00:35:39,630
jonkinlainen numeron.

707
00:35:39,630 --> 00:35:43,140
Ja niin, esimerkiksi, jos halusin
Olla synonyymi apple--

708
00:35:43,140 --> 00:35:47,460
tai indeksi 0, ja
B olla synonyymi 1,

709
00:35:47,460 --> 00:35:51,030
voimme olla 26 merkinnät
että voi vain tallentaa

710
00:35:51,030 --> 00:35:53,610
kaikki kirjaimet
aakkoset että aloitamme kanssa.

711
00:35:53,610 --> 00:35:56,130
Ja sitten voimme olla
omena on indeksi 0.

712
00:35:56,130 --> 00:35:59,160
Meillä voi olla banaani on indeksi
1, fenkoli on indeksi 2,

713
00:35:59,160 --> 00:36:00,540
ja niin edelleen ja niin edelleen.

714
00:36:00,540 --> 00:36:04,460
Ja näin jos halusin etsiä
minun tiiviste ja pääsy omena,

715
00:36:04,460 --> 00:36:07,560
Tiedän Apple alkaa
, ja tiedän tarkalleen

716
00:36:07,560 --> 00:36:10,860
että sen on oltava, ja hash
pöytä indeksi 0, koska

717
00:36:10,860 --> 00:36:13,620
Toiminnon aiemmin määritetty.

718
00:36:13,620 --> 00:36:16,572
>> Joten en tiedä, olemme
käyttäjäkohtaisia ​​jossa

719
00:36:16,572 --> 00:36:18,780
sinulta veloitetaan kanssa
arbitrarily-- ei mielivaltaisesti,

720
00:36:18,780 --> 00:36:22,530
kanssa yrittää mietteliäänä
ajatella hyvä yhtälöt

721
00:36:22,530 --> 00:36:25,460
pystyä levittämään
pois kaikki arvot

722
00:36:25,460 --> 00:36:29,370
siten he voivat helposti
se myöhemmin kanssa kuin yhtälön

723
00:36:29,370 --> 00:36:31,130
että te itse, tietää.

724
00:36:31,130 --> 00:36:35,210
Joten siinä mielessä, jos halusin mennä
mango, tiedän, oi, se alkaa m.

725
00:36:35,210 --> 00:36:37,134
Sen on oltava indeksi 12.

726
00:36:37,134 --> 00:36:38,800
Minulla ei tarvitse etsiä mitään.

727
00:36:38,800 --> 00:36:42,080
Tiedän exactly-- voisin vain mennä
indeksi 12 ja vedä se ulos.

728
00:36:42,080 --> 00:36:45,520
>> Jokainen selvää miten
tiiviste n toiminto toimii?

729
00:36:45,520 --> 00:36:48,380
Se on tavallaan vain monimutkaisempi array.

730
00:36:48,380 --> 00:36:50,010
Siinä kaikki se on.

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

732
00:36:51,630 --> 00:36:57,690
>> Joten kai me törmätä
tämä kysymys mitä

733
00:36:57,690 --> 00:37:06,390
tapahtuu, jos sinulla on useita asioita
jotka antavat sinulle sama indeksi?

734
00:37:06,390 --> 00:37:10,570
Joten sanoa meidän tehtävämme, kaikki se
teki oli ottaa tämän ensimmäisen kirjeen

735
00:37:10,570 --> 00:37:14,490
ja kääntää sen osaksi
vastaaviin 0 kautta 25 indeksi.

736
00:37:14,490 --> 00:37:17,137
Se on täysin hienoa, jos
sinulla on vain yksi kutakin.

737
00:37:17,137 --> 00:37:18,970
Mutta toinen aloitat
on enemmän, olet

738
00:37:18,970 --> 00:37:20,910
menossa on mitä kutsutaan törmäys.

739
00:37:20,910 --> 00:37:25,580
>> Joten jos yritän lisätä haudata osaksi hash
taulukko, joka jo on banaani sitä,

740
00:37:25,580 --> 00:37:27,870
mitä tulee tapahtumaan, kun
yrität lisätä, että?

741
00:37:27,870 --> 00:37:30,930
Bad Things koska banaani
jo tallennettu indeksi

742
00:37:30,930 --> 00:37:33,800
että haluat tallentaa sen.

743
00:37:33,800 --> 00:37:35,560
Berry sellainen on kuin, ah, mitä teen?

744
00:37:35,560 --> 00:37:37,080
En tiedä minne mennä.

745
00:37:37,080 --> 00:37:38,410
Miten ratkaista tämän?

746
00:37:38,410 --> 00:37:41,150
>> Ja niin te tulee eräänlainen
katso teemme tätä hankala asia

747
00:37:41,150 --> 00:37:44,810
missä voimme tavallaan todella
luoda linkitetyn listan meidän paneelit.

748
00:37:44,810 --> 00:37:46,840
Ja niin helpoin tapa
ajatella tätä,

749
00:37:46,840 --> 00:37:50,830
kaikki tiiviste on
joukko linkitettyjen listojen.

750
00:37:50,830 --> 00:37:55,670
Ja niin, siinä mielessä, sinulla on
tämä kaunis joukko osoittimia,

751
00:37:55,670 --> 00:37:58,740
ja sitten kukin osoitinta
että arvo, että indeksi,

752
00:37:58,740 --> 00:38:00,740
voi todella korostavat muita asioita.

753
00:38:00,740 --> 00:38:05,720
Ja niin sinulla on kaikki nämä erilliset
ketjut tulossa pois yhden ison array.

754
00:38:05,720 --> 00:38:07,960
>> Ja niin tässä, jos en
halusi lisätä marja,

755
00:38:07,960 --> 00:38:11,220
Tiedän, OK, aion tuloon
se läpi minun hajautusfunktio.

756
00:38:11,220 --> 00:38:15,070
Aion päätyä indeksi
1, ja sitten aion voida olla

757
00:38:15,070 --> 00:38:20,410
vain pienempi osajoukko tämän
jättiläinen 140000-sanan sanakirja.

758
00:38:20,410 --> 00:38:24,220
Ja sitten voin vain katsoa
kautta 1/26 siitä.

759
00:38:24,220 --> 00:38:27,910
>> Ja niin sitten voin vain lisätä
marja joko ennen tai jälkeen banaani

760
00:38:27,910 --> 00:38:28,820
tässä tapauksessa?

761
00:38:28,820 --> 00:38:29,700
Jälkeen, eikö?

762
00:38:29,700 --> 00:38:33,920
Ja niin olet menossa haluavat
aseta tämä solmu jälkeen banaani,

763
00:38:33,920 --> 00:38:36,667
ja niin aiot lisätä
klo pyrstö että linkitetyn listan.

764
00:38:36,667 --> 00:38:38,500
Aion mennä takaisin
Tämän Edellinen dia,

765
00:38:38,500 --> 00:38:40,680
joten te voi nähdä, miten
tiivistefunktio toimii.

766
00:38:40,680 --> 00:38:43,980
>> Joten tiivistefunktio on tämä yhtälö
että käytät sellaista syöte

767
00:38:43,980 --> 00:38:46,940
kautta saada mitä indeksi
haluat antaa etenemään kohti.

768
00:38:46,940 --> 00:38:51,130
Ja niin, tässä esimerkissä, kaikki halusimme
tehdä oli ottaa ensimmäinen kirjain,

769
00:38:51,130 --> 00:38:55,890
kääntää sen osaksi indeksi, niin me
voi tallentaa että meidän hajautusfunktio.

770
00:38:55,890 --> 00:39:00,160
Kaikki me teemme tässä olemme
muuntaa ensimmäinen kirjain.

771
00:39:00,160 --> 00:39:04,770
Joten KeyKey [0] on vain ensimmäinen kirjain
riippumatta merkkijono meillä oli,

772
00:39:04,770 --> 00:39:05,720
olemme ohimennen.

773
00:39:05,720 --> 00:39:09,740
Olemme muuntaa että ylä-, ja
olemme vähentämällä mukaan isoja,

774
00:39:09,740 --> 00:39:11,740
niin kaikki mitä tekee
antaa meille numero

775
00:39:11,740 --> 00:39:13,670
jossa voimme hash arvojamme päälle.

776
00:39:13,670 --> 00:39:16,550
>> Ja sitten me aiomme
palata hash moduuli KOKO.

777
00:39:16,550 --> 00:39:19,340
Ole hyvin, hyvin varovainen
sillä, teoriassa, tässä

778
00:39:19,340 --> 00:39:21,870
sinun hash arvo voi olla ääretön.

779
00:39:21,870 --> 00:39:23,660
Se voisi vain mennä ja ja.

780
00:39:23,660 --> 00:39:26,080
Se voisi olla joitakin todella,
todella suuri arvo,

781
00:39:26,080 --> 00:39:29,849
mutta koska tiiviste että
olet luonut vain 26 indeksit,

782
00:39:29,849 --> 00:39:31,890
haluat varmistaa, että
modulusing jotta voit

783
00:39:31,890 --> 00:39:33,848
älä run-- se on sama
asia kuin queue--

784
00:39:33,848 --> 00:39:36,320
niin että et suorita pois
pohjassa hajautusfunktion.

785
00:39:36,320 --> 00:39:39,210
>> Haluat kääri se takaisin noin
samalla tavalla [äänetön], kun

786
00:39:39,210 --> 00:39:41,750
sinulla oli kuin hyvin,
erittäin suuri kirjain, sinua

787
00:39:41,750 --> 00:39:43,740
ei halua, että
vain ajaa pois loppuun.

788
00:39:43,740 --> 00:39:46,948
Sama juttu täällä, haluat varmistaa,
se ei suorita pois lopussa käärimällä

789
00:39:46,948 --> 00:39:48,330
noin taulukon yläosassa.

790
00:39:48,330 --> 00:39:50,530
Joten tämä on vain hyvin
yksinkertainen tiivistefunktio.

791
00:39:50,530 --> 00:39:56,570
Kaikki tämä teki, oli ottaa ensimmäinen
kirjeellä mitä meidän panos oli

792
00:39:56,570 --> 00:40:01,660
ja kääntää sen osaksi indeksi, joka
voisimme ottaa meidän tiiviste.

793
00:40:01,660 --> 00:40:05,450
>> Joo, ja niin kuten aiemmin sanoin,
siten, että ratkaisemme törmäykset

794
00:40:05,450 --> 00:40:09,330
meidän hash taulukot ottaa,
mitä me kutsumme, ketjutus.

795
00:40:09,330 --> 00:40:13,860
Joten jos yrität lisätä useita
sanoja, jotka alkavat sama asia,

796
00:40:13,860 --> 00:40:16,145
aiot olla yksi hash-arvo.

797
00:40:16,145 --> 00:40:18,770
Avokadot ja omena, jos olet
ajaa se läpi meidän hajautusfunktio,

798
00:40:18,770 --> 00:40:21,450
aiomme antaa teille
sama numero, numero 0.

799
00:40:21,450 --> 00:40:24,550
Ja niin tapaamme ratkaista että on
että voimme todella sellaista linkittää niitä

800
00:40:24,550 --> 00:40:27,010
yhdessä kautta linkitettyjen listojen.

801
00:40:27,010 --> 00:40:29,600
>> Ja niin tässä mielessä,
te voi nähdä sellaista

802
00:40:29,600 --> 00:40:32,640
siitä, miten tietorakenteet
olemme asettamalla aiemmin

803
00:40:32,640 --> 00:40:35,870
kuten rusina linkitetty lista laji
ja voi tulla yhdeksi.

804
00:40:35,870 --> 00:40:38,860
Ja sitten voit luoda pitkälle
tehokkaampi tietorakenteita

805
00:40:38,860 --> 00:40:43,350
jotka voivat käsitellä suurempia määriä
tiedot, että dynaamisesti muuttaa riippuen

806
00:40:43,350 --> 00:40:44,870
tarpeisiin.

807
00:40:44,870 --> 00:40:45,620
Jokainen selvä?

808
00:40:45,620 --> 00:40:47,580
Jokainen sellainen selkeä
mitä tapahtuu täällä?

809
00:40:47,580 --> 00:40:52,110
>> Jos halusin insert-- mitä
hedelmä, joka alkaa, en tiedä,

810
00:40:52,110 --> 00:40:54,726
B, muut kuin marja, banaani.

811
00:40:54,726 --> 00:40:55,710
>> Yleisö: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI Peng: Blackberry, karhunvatukka.

813
00:40:57,910 --> 00:41:00,530
Jos ei karhunvatukka mennä täällä?

814
00:41:00,530 --> 00:41:04,251
No, emme oikeastaan ​​ole lajiteltu
tätä vielä, mutta teoreettisesti

815
00:41:04,251 --> 00:41:06,250
jos halusimme saada tämän
aakkosjärjestyksessä

816
00:41:06,250 --> 00:41:07,944
jossa pitäisi karhunvatukka mennä?

817
00:41:07,944 --> 00:41:09,210
>> Yleisö: [äänetön]

818
00:41:09,210 --> 00:41:11,100
>> ANDI Peng: Aivan, kun täällä, eikö?

819
00:41:11,100 --> 00:41:14,950
Mutta koska se on hyvin vaikeaa
reorder-- Kai se on jopa teitä.

820
00:41:14,950 --> 00:41:17,920
Te voi täysin
toteuttaa mitä haluat.

821
00:41:17,920 --> 00:41:20,730
Tehokkaamman
tehdä tämä ehkä

822
00:41:20,730 --> 00:41:24,570
olisi lajitella sidoksissa
luettelo aakkosjärjestykseen,

823
00:41:24,570 --> 00:41:26,520
ja niin kun olet
lisäämällä asioita, haluat

824
00:41:26,520 --> 00:41:28,632
olla varma lisätä niitä
aakkosjärjestykseen

825
00:41:28,632 --> 00:41:30,590
niin että sitten kun olet
yrittää etsiä niitä,

826
00:41:30,590 --> 00:41:32,410
sinun ei tarvitse kulkea kaikki.

827
00:41:32,410 --> 00:41:35,290
Tiedät tarkalleen missä
se on, ja se on helpompaa.

828
00:41:35,290 --> 00:41:39,100
>> Mutta jos sellainen on
asiat välissä satunnaisesti,

829
00:41:39,100 --> 00:41:41,420
olet vielä menossa on
kulkemaan sitä anyways.

830
00:41:41,420 --> 00:41:44,990
Joten jos halusin vain
aseta karhunvatukka täällä

831
00:41:44,990 --> 00:41:47,470
ja halusin etsiä
se, tiedän, OH, karhunvatukka

832
00:41:47,470 --> 00:41:52,012
on aloitettava indeksi 1, joten en
tietää välittömästi vain etsiä 1.

833
00:41:52,012 --> 00:41:53,970
Ja sitten voin sellainen
kulkea linkitetty lista

834
00:41:53,970 --> 00:41:56,120
kunnes saan Blackberry,
ja then-- joo?

835
00:41:56,120 --> 00:41:59,550
>> Yleisö: Jos yrität create--
Oletan näin on hyvin yksinkertainen hash

836
00:41:59,550 --> 00:42:00,050
toiminto.

837
00:42:00,050 --> 00:42:02,835
Ja jos halusimme tehdä
useita kerroksia, että kuten,

838
00:42:02,835 --> 00:42:05,870
OK, haluamme erotella
kuten kaikki aakkosina

839
00:42:05,870 --> 00:42:09,040
ja sitten taas kuin toinen joukko
aakkosellinen kirjeitä kyseisessä,

840
00:42:09,040 --> 00:42:11,715
olemme laskemisesta kuin hash
pöytä sisällä tiiviste,

841
00:42:11,715 --> 00:42:13,256
tai kuten toimintoa funktio?

842
00:42:13,256 --> 00:42:14,880
Vai onko that--

843
00:42:14,880 --> 00:42:17,510
>> ANDI Peng: Joten hash
function-- sinun tiiviste

844
00:42:17,510 --> 00:42:19,360
voi olla niin suuri kuin haluat sen.

845
00:42:19,360 --> 00:42:21,930
Joten tässä mielessä, ajattelin
se oli hyvin helppo, hyvin

846
00:42:21,930 --> 00:42:25,320
yksinkertainen minulle vain eräänlainen perustuu
kirjeistä ensimmäisen sanan.

847
00:42:25,320 --> 00:42:28,690
Ja niin on vain 26 vaihtoehtoja.

848
00:42:28,690 --> 00:42:32,650
Voin vain saada 26 vaihtoehtoja
0-25 koska ne voivat vain

849
00:42:32,650 --> 00:42:36,510
alkaa A: sta Z Mutta Jos halusi
lisätä, ehkä enemmän monimutkaisuus

850
00:42:36,510 --> 00:42:39,260
tai nopeampi ajaa aikaa teidän
tiiviste, ehdottomasti

851
00:42:39,260 --> 00:42:40,760
voi tehdä kaikenlaisia ​​asioita.

852
00:42:40,760 --> 00:42:43,330
Voit tehdä oman
yhtälö, joka antaa sinulle

853
00:42:43,330 --> 00:42:48,000
lisää jakelu teidän
sanoja, sitten kun haet,

854
00:42:48,000 --> 00:42:49,300
se tulee olemaan nopeampi.

855
00:42:49,300 --> 00:42:52,100
>> Se on täysin jopa te
miten haluat toteuttaa sitä.

856
00:42:52,100 --> 00:42:55,140
Ajattele sitä vain kauhat.

857
00:42:55,140 --> 00:42:57,376
Jos halusin
26 kauhat, aion

858
00:42:57,376 --> 00:42:59,420
lajitella asiat noihin kauhat.

859
00:42:59,420 --> 00:43:02,980
Mutta aion olla nippu
tavaraa kussakin ämpäri,

860
00:43:02,980 --> 00:43:05,890
joten jos haluat tehdä
nopeampi ja tehokkaampi,

861
00:43:05,890 --> 00:43:07,190
antaa minulle sata kauhat.

862
00:43:07,190 --> 00:43:09,290
>> Mutta sitten sinun täytyy selvittää
tapa järjestää asiat niin, että ne ovat

863
00:43:09,290 --> 00:43:11,040
oikeassa ämpäri niiden pitäisi olla.

864
00:43:11,040 --> 00:43:13,331
Mutta sitten kun itse
halua katsoa että ämpäri,

865
00:43:13,331 --> 00:43:16,410
se on paljon nopeammin, koska siellä
vähemmän tavaraa kussakin ämpäri.

866
00:43:16,410 --> 00:43:20,250
Ja niin, joo, se on todella
temppu sinulle kaverit pset5

867
00:43:20,250 --> 00:43:22,360
on, että voit olla
haastetaan vain luoda

868
00:43:22,360 --> 00:43:26,170
mikä on tehokkain
toiminnolla voit ajatella olevan

869
00:43:26,170 --> 00:43:28,520
voi tallentaa ja tarkistaa näitä arvoja.

870
00:43:28,520 --> 00:43:30,840
>> Täysin jopa te
mutta haluat tehdä sen,

871
00:43:30,840 --> 00:43:32,229
mutta se on todella hyvä pointti.

872
00:43:32,229 --> 00:43:34,520
Että logiikkaa sinua
haluavat alkaa miettiä

873
00:43:34,520 --> 00:43:37,236
on, hyvin, miksi en tee enemmän kauhat.

874
00:43:37,236 --> 00:43:39,527
Ja sitten minun täytyy etsiä
vähemmän asioita, ja sitten ehkä

875
00:43:39,527 --> 00:43:41,640
on eri hajautusfunktio.

876
00:43:41,640 --> 00:43:45,500
>> Joo, siellä on paljon tapoja tehdä tämä
PSET, jotkut ovat nopeampia kuin toiset.

877
00:43:45,500 --> 00:43:50,630
Olen täysin menossa vain nähdä miten
nopea oli nopein te kaverit

878
00:43:50,630 --> 00:43:55,170
voi saada toiminnot toimimaan.

879
00:43:55,170 --> 00:43:58,176
OK, kaikki hyvältä
ketjuuntuminen ja hash taulukoita?

880
00:43:58,176 --> 00:44:00,800
Se on oikeastaan ​​kuin hyvin yksinkertainen
käsite jos ajattelee sitä.

881
00:44:00,800 --> 00:44:05,160
Kaikki se on on erottamalla riippumatta
teidän tulot ovat osaksi kauhat,

882
00:44:05,160 --> 00:44:10,670
lajittelu, ja sitten etsimällä
luettelee että siellä liittyy.

883
00:44:10,670 --> 00:44:11,852
>> Viileä.

884
00:44:11,852 --> 00:44:18,160
Okei, nyt meillä on erilainen eräänlainen
Tietojen rakenne, joka kutsutaan puu.

885
00:44:18,160 --> 00:44:20,850
Jatketaan ja puhua yrittää
jotka ovat selvästi erilaisia,

886
00:44:20,850 --> 00:44:22,330
mutta samaan luokkaan.

887
00:44:22,330 --> 00:44:29,010
Pohjimmiltaan kaikki puu on sen sijaan
järjestää tietojen lineaarisesti

888
00:44:29,010 --> 00:44:32,560
että tiiviste does-- sinua
tietää, se sai ylä- ja alaosassa

889
00:44:32,560 --> 00:44:37,900
ja sitten tavallaan linkittää pois it--
puu on ylhäältä joka soitat juuri,

890
00:44:37,900 --> 00:44:40,220
ja sitten se on lähtee kaikki sen ympärillä.

891
00:44:40,220 --> 00:44:42,390
>> Ja niin sinun ei täällä
on vain yläsolmun

892
00:44:42,390 --> 00:44:45,980
joka viittaa muihin solmuihin, että pistettä
enemmän solmuja, ja niin edelleen, ja niin edelleen.

893
00:44:45,980 --> 00:44:48,130
Ja niin sinun täytyy vain jakohaaroja.

894
00:44:48,130 --> 00:44:53,255
Se on vain erilainen tapa organisoida
tiedot, ja koska me kutsumme sitä puu,

895
00:44:53,255 --> 00:44:56,270
te just-- se on vain
mallinnettu ulos näyttämään puu.

896
00:44:56,270 --> 00:44:57,670
Siksi me kutsumme sitä puita.

897
00:44:57,670 --> 00:44:59,370
>> Tiiviste näyttää pöytä.

898
00:44:59,370 --> 00:45:01,310
Puu vain näyttää puu.

899
00:45:01,310 --> 00:45:03,300
Kaikki se on on erillinen
tapa järjestää solmujen

900
00:45:03,300 --> 00:45:06,020
riippuen mitkä tarpeet ovat.

901
00:45:06,020 --> 00:45:11,810
>> Joten sinulla on juuri ja
sitten on lehdet.

902
00:45:11,810 --> 00:45:15,380
Tapa, jolla voimme erityisen
ajattele sitä on binääripuu,

903
00:45:15,380 --> 00:45:18,150
binääripuu on vain
tietyntyyppistä puu

904
00:45:18,150 --> 00:45:22,450
jossa kukin solmu vain pistettä
to, max, kaksi muuta solmut.

905
00:45:22,450 --> 00:45:25,434
Ja niin täällä on selvä
symmetria teidän puu

906
00:45:25,434 --> 00:45:28,600
että helpottaa sellaista näyttää
mitä arvoja olet koska silloin

907
00:45:28,600 --> 00:45:30,150
on aina vasemmalle tai oikealle.

908
00:45:30,150 --> 00:45:33,150
Ei koskaan kuin vasemman kolmanneksen
vasemmalle tai neljäsosa vasemmalta.

909
00:45:33,150 --> 00:45:36,358
Se on vain sinulla on vasen ja oikea
ja voit hakea joko näistä kahdesta.

910
00:45:36,358 --> 00:45:38,980
Ja niin miksi tämä hyödyllinen?

911
00:45:38,980 --> 00:45:40,980
Siten, että tämä on
hyödyllinen on jos etsit

912
00:45:40,980 --> 00:45:42,890
etsiä arvoja, eikö?

913
00:45:42,890 --> 00:45:45,640
Sijasta, binary
etsiä virheen array,

914
00:45:45,640 --> 00:45:49,260
jos halusi pystyä lisätä solmuja
ja ottaa pois solmut tahtoa ja myös

915
00:45:49,260 --> 00:45:52,185
säilyttää haku
kapasiteetin binäärihakupuu.

916
00:45:52,185 --> 00:45:54,560
Joten tällä tavalla, olemme eräänlainen
tricking-- muistan kun me

917
00:45:54,560 --> 00:45:56,530
sanoi liittyy luetteloita ei binäärihaku?

918
00:45:56,530 --> 00:46:01,700
Olemme tavallaan luoda tietorakenteen
että temppuja että työskentelyasentoon.

919
00:46:01,700 --> 00:46:05,034
>> Ja siksi sidoksissa luettelot ovat lineaarisia,
ne yhdistävät vain yksi toisensa jälkeen.

920
00:46:05,034 --> 00:46:06,950
Voimme sellaista olla
toisenlaisen osoittimia

921
00:46:06,950 --> 00:46:09,408
Siinä vaiheessa eri solmut
jotka voivat auttaa meitä haku.

922
00:46:09,408 --> 00:46:12,590
Ja niin tässä, jos halusin
on binäärihakupuu,

923
00:46:12,590 --> 00:46:14,090
Tiedän, että minun keskimmäinen jos 55.

924
00:46:14,090 --> 00:46:18,280
Olen juuri menossa luoda että
minun keskimmäinen, kuten minun root,

925
00:46:18,280 --> 00:46:20,770
ja sitten aion olla
arvot spin off sitä.

926
00:46:20,770 --> 00:46:25,610
>> Joten tässä, jos aion etsiä
arvo 66, voin aloittaa 55.

927
00:46:25,610 --> 00:46:27,310
Se on 66 suurempi kuin 55?

928
00:46:27,310 --> 00:46:30,970
Kyllä se on, niin tiedän mus etsi
I n oikea osoitin tämän puun.

929
00:46:30,970 --> 00:46:32,440
Menen 77.

930
00:46:32,440 --> 00:46:35,367
OK, on ​​66 pienempi tai suurempi kuin 77?

931
00:46:35,367 --> 00:46:37,950
Se on vähemmän kuin, niin tiedät, oi,
jonka on oltava vasemmalle solmu.

932
00:46:37,950 --> 00:46:41,410
>> Ja joten tässä olemme eräänlainen säilyttämiseen
kaikki suuria asioita paneelit,

933
00:46:41,410 --> 00:46:44,420
joten kuten dynaaminen koon
esineitä, että

934
00:46:44,420 --> 00:46:49,530
voi lisätä ja poistaa mieleisekseen,
ilman huolta siitä kiinteä

935
00:46:49,530 --> 00:46:50,370
paljon tilaa.

936
00:46:50,370 --> 00:46:52,820
Meillä on vielä säilyttää kaikki
niitä ihania asioita

937
00:46:52,820 --> 00:46:57,140
samalla myös mahdollisuus säilyttää
log ja etsiä aikaa binary haku

938
00:46:57,140 --> 00:47:00,450
että olimme vain aiemmin
saada lause.

939
00:47:00,450 --> 00:47:06,310
>> Cool tietorakenne, eräänlainen
hankala toteuttaa, solmu.

940
00:47:06,310 --> 00:47:08,311
Kuten näette, kaikki se
on struct solmun

941
00:47:08,311 --> 00:47:10,143
on, että sinulla on vasemmalle
ja oikea osoitin.

942
00:47:10,143 --> 00:47:11,044
Siinä kaikki se on.

943
00:47:11,044 --> 00:47:12,960
Joten sen sijaan vain
ottaa X tai edellinen.

944
00:47:12,960 --> 00:47:15,920
Sinulla vasemmalle tai oikealle, ja sitten
voit sellaista liittää ne yhteen

945
00:47:15,920 --> 00:47:16,836
kuitenkin niin haluat.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, olemme todella menossa
vain kestää muutaman minuutin.

948
00:47:24,270 --> 00:47:25,790
Joten aiomme palata tänne.

949
00:47:25,790 --> 00:47:28,270
Kuten sanoin aiemmin,
Olen sellainen selittänyt

950
00:47:28,270 --> 00:47:31,520
logiikka miten me
olisi etsiä tätä.

951
00:47:31,520 --> 00:47:33,860
Aiomme yrittää
pseudocoding tätä nähdä

952
00:47:33,860 --> 00:47:38,000
jos voimme sellaista soveltaa
Sama logiikka binäärihaku

953
00:47:38,000 --> 00:47:40,055
eri tyyppisiä tietoja rakenteen.

954
00:47:40,055 --> 00:47:45,049
Jos kaverit haluavat ottaa kuin pari
minuuttia vain ajatella tätä.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
OK.

957
00:48:46,925 --> 00:48:51,407
Hyvä, aion
oikeastaan ​​vain antaa sinulle the-- ei,

958
00:48:51,407 --> 00:48:52,990
me puhumme pseudokoodina ensin.

959
00:48:52,990 --> 00:48:56,580
Joten ei kukaan halua
antaa puukottaa mitä

960
00:48:56,580 --> 00:49:02,100
ensimmäinen asia, jonka haluat tehdä, kun
olet aloittamassa haku on?

961
00:49:02,100 --> 00:49:04,460
Jos etsimme
arvo 66, mikä on

962
00:49:04,460 --> 00:49:07,940
ensimmäinen asia haluamme tehdä, jos
haluamme binäärihakupuu tämän puun?

963
00:49:07,940 --> 00:49:10,760
>> Yleisö: Haluat katsoa oikealle
ja näyttävät vasemmalle ja nähdä [äänetön]

964
00:49:10,760 --> 00:49:11,230
suurempi määrä.

965
00:49:11,230 --> 00:49:12,271
>> ANDI Peng: Joo, täsmälleen.

966
00:49:12,271 --> 00:49:15,350
Joten olet menossa katsomaan pääkäyttäjän.

967
00:49:15,350 --> 00:49:18,180
On paljon tapoja, joilla voit soittaa
se, vanhempasi solmu ihmiset sanovat.

968
00:49:18,180 --> 00:49:21,317
Haluan sanoa juuri koska
se on kuin puun juuri.

969
00:49:21,317 --> 00:49:23,400
Olet menossa katsomaan
sinun juurisolmu, ja olet

970
00:49:23,400 --> 00:49:26,940
näkemään on 66 suurempi
kuin tai vähemmän kuin 55.

971
00:49:26,940 --> 00:49:30,360
Ja jos se on suurempi kuin, no, se on
suurempi kuin, jos haluamme näyttää?

972
00:49:30,360 --> 00:49:32,000
Missä haluamme etsiä nyt, eikö?

973
00:49:32,000 --> 00:49:34,340
Haluamme etsiä
oikea puoli tämän puun.

974
00:49:34,340 --> 00:49:38,390
>> Joten meillä on, sopivasti,
osoitin, joka osoittaa oikealle.

975
00:49:38,390 --> 00:49:44,325
Ja niin sitten voimme asettaa
uusi pääkäyttäjän 77.

976
00:49:44,325 --> 00:49:46,450
Voimme vain mennä minne
osoitin osoittaa.

977
00:49:46,450 --> 00:49:49,100
No, oh, tässä alamme
77, ja voimme vain

978
00:49:49,100 --> 00:49:51,172
Tätä rekursiivisesti uudestaan ​​ja uudestaan.

979
00:49:51,172 --> 00:49:52,880
Näin voit laji
on on toiminto.

980
00:49:52,880 --> 00:49:57,430
Sinulla on tapa etsiä että te
voi vain toistaa uudestaan ​​ja uudestaan ​​ja uudestaan,

981
00:49:57,430 --> 00:50:02,720
riippuen siitä, missä haluat katsoa
kunnes lopulta saada arvoa

982
00:50:02,720 --> 00:50:04,730
että etsit.

983
00:50:04,730 --> 00:50:05,230
Käydä järkeen?

984
00:50:05,230 --> 00:50:07,800
>> Olen aikeissa näyttää todellinen
koodi, ja se on paljon koodia.

985
00:50:07,800 --> 00:50:08,674
Ei tarvitse älyttömästi.

986
00:50:08,674 --> 00:50:09,910
Puhutaan sen läpi.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Itse asiassa, ole.

989
00:50:14,020 --> 00:50:15,061
Se oli vain pseudokoodilla.

990
00:50:15,061 --> 00:50:17,860
OK, että oli vain pseudokoodina,
joka on vähän monimutkainen,

991
00:50:17,860 --> 00:50:19,751
mutta se on täysin hieno.

992
00:50:19,751 --> 00:50:21,000
Jokainen seuraava pitkin täällä?

993
00:50:21,000 --> 00:50:24,260
Jos juuri on null, paluu
väärä, koska se tarkoittaa

994
00:50:24,260 --> 00:50:26,850
sinun ei edes ole mitään siellä.

995
00:50:26,850 --> 00:50:31,376
>> Jos juuri n on arvo, joten jos se
sattuu olemaan yksi etsit,

996
00:50:31,376 --> 00:50:34,000
sitten olet menossa return true
koska tiedät löysit sen.

997
00:50:34,000 --> 00:50:36,250
Mutta jos arvo on pienempi
kuin juuri n, olet

998
00:50:36,250 --> 00:50:38,332
menossa etsiä vasemmalle
lapsi tai vasemmalle lehtiä,

999
00:50:38,332 --> 00:50:39,540
mitä haluat kutsua sitä.

1000
00:50:39,540 --> 00:50:41,750
Ja jos arvo on suurempi kuin juuri,
aiot etsiä oikea puu,

1001
00:50:41,750 --> 00:50:44,610
sitten vain ajaa toiminto
haun kautta uudelleen.

1002
00:50:44,610 --> 00:50:48,037
>> Ja jos juuri on null, että
tarkoittaa olet saavuttanut loppuun?

1003
00:50:48,037 --> 00:50:50,120
Tämä tarkoittaa sinulla ei ole
lisää lisää lehtiä etsiä,

1004
00:50:50,120 --> 00:50:52,230
niin tiedät, oi, minä
kai se ei ole täällä

1005
00:50:52,230 --> 00:50:55,063
koska kun olen käynyt läpi
koko juttu ja se ei ole täällä,

1006
00:50:55,063 --> 00:50:56,930
se vain voi olla täällä.

1007
00:50:56,930 --> 00:50:58,350
>> Tarkoittaako tämä järkevää kaikille?

1008
00:50:58,350 --> 00:51:03,230
Joten se on kuin binäärihaku säilöntä
ominaisuuksia linkitettyjen listojen.

1009
00:51:03,230 --> 00:51:09,200
Jäähtyä, ja siten toisen tyypin
Tietojen rakenne te

1010
00:51:09,200 --> 00:51:13,180
voi kokeilla täytäntöönpanosta teidän PSET,
sinulla on vain valita yksi menetelmä.

1011
00:51:13,180 --> 00:51:19,430
Mutta ehkä vaihtoehtoinen menetelmä
hash table me kutsumme trie.

1012
00:51:19,430 --> 00:51:24,080
>> Kaikki trie on on
tietyntyyppisen puun, joka

1013
00:51:24,080 --> 00:51:28,600
on arvoja, jotka menevät muita arvoja.

1014
00:51:28,600 --> 00:51:31,450
Joten sen sijaan, että binary
puu siinä mielessä, että vain yksi

1015
00:51:31,450 --> 00:51:35,940
asia voi viitata kaksi, voit olla
yksi asia kohta monia, monia asioita.

1016
00:51:35,940 --> 00:51:39,450
Voit olennaisesti on taulukot
jonka sisällä tallennat

1017
00:51:39,450 --> 00:51:41,790
osoittimia, jotka viittaavat muihin paneelit.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Joten solmu miten
määriteltäisiin trie

1020
00:51:49,460 --> 00:51:52,590
on haluamme
Boolean, C sana, eikö?

1021
00:51:52,590 --> 00:51:54,920
Joten solmu on Boolen
kuten totta vai tarua,

1022
00:51:54,920 --> 00:51:58,490
ensinnäkin kärjessä
että matriisi, on tämä sana?

1023
00:51:58,490 --> 00:52:03,620
Toiseksi, haluat olla viitteitä
mihin tahansa loput niistä ovat.

1024
00:52:03,620 --> 00:52:07,470
Hieman monimutkainen, hieman abstrakti, mutta
Selitän, mitä se kaikki keinot.

1025
00:52:07,470 --> 00:52:13,800
>> Joten tässä, huipulla, jos
on joukko julisti jo,

1026
00:52:13,800 --> 00:52:17,040
solmu, jossa sinulla on Boolen
tallennettu arvo edessä

1027
00:52:17,040 --> 00:52:19,490
joka kertoo on tämä sana?

1028
00:52:19,490 --> 00:52:20,520
Eikö tämä ole sana?

1029
00:52:20,520 --> 00:52:23,240
Ja sitten on
loppuelämäsi array, joka

1030
00:52:23,240 --> 00:52:26,040
todella tallentaa kaikki
mahdollisuuksia mitä se voisi olla.

1031
00:52:26,040 --> 00:52:28,660
Niinpä esimerkiksi, kuten
huipulla olet

1032
00:52:28,660 --> 00:52:32,140
ensimmäinen asia, joka sanoo totta tai
väärä, kyllä ​​tai ei, tämä on sana.

1033
00:52:32,140 --> 00:52:38,130
>> Ja sitten on 0 kautta 26
kirjaimet, jotka voit tallentaa.

1034
00:52:38,130 --> 00:52:42,790
Jos halusin etsiä täällä
BAT, menen alkuun

1035
00:52:42,790 --> 00:52:49,200
ja odotan B löydän B minun
array, ja niin tiedän, OK, on ​​B sana?

1036
00:52:49,200 --> 00:52:53,010
B ei ole sana, niin näin
Minun täytyy pitää etsimistä.

1037
00:52:53,010 --> 00:52:56,410
Menen B, ja katson
osoitin, että B osoittaa kohti

1038
00:52:56,410 --> 00:53:00,900
ja minä näen toisen joukko tietoja,
sama rakenne, että meillä oli ennen.

1039
00:53:00,900 --> 00:53:05,240
>> Ja here-- oh, seuraava
kirje [äänetön] on A.

1040
00:53:05,240 --> 00:53:07,210
Joten katsomme, että jono.

1041
00:53:07,210 --> 00:53:10,860
Löydämme kahdeksas arvo,
ja sitten me katsomme, OH,

1042
00:53:10,860 --> 00:53:12,840
hei, on että sana, on B-sana?

1043
00:53:12,840 --> 00:53:13,807
Se ei ole sana.

1044
00:53:13,807 --> 00:53:14,890
Meidän täytyy pitää näköinen.

1045
00:53:14,890 --> 00:53:17,850
>> Ja niin sitten katsomme missä
osoittimen pistettä,

1046
00:53:17,850 --> 00:53:21,130
ja se osoittaa muulla tavalla
joka meillä on enemmän arvoa tallennetaan.

1047
00:53:21,130 --> 00:53:24,150
Ja lopulta, saamme
B--T-, joka on sana.

1048
00:53:24,150 --> 00:53:25,970
Ja niin seuraavan kerran
näytät, olet menossa

1049
00:53:25,970 --> 00:53:30,850
on, että tarkastus, kyllä,
tämä Boolen toiminto on totta.

1050
00:53:30,850 --> 00:53:35,450
Ja niin siinä mielessä olemme eräänlainen
ottaa puu paneelit.

1051
00:53:35,450 --> 00:53:39,890
>> Joten voit eräänlainen haku alaspäin.

1052
00:53:39,890 --> 00:53:43,650
Sen sijaan, hajautus funktio ja
osoitetaan arvoja linkitetty lista,

1053
00:53:43,650 --> 00:53:49,190
voit vain toteuttaa
trien, joka etsii downwords.

1054
00:53:49,190 --> 00:53:50,850
Todella, todella monimutkainen kamaa.

1055
00:53:50,850 --> 00:53:54,060
Ei helppo ajatella, koska olen kuin
sylkeminen niin paljon tietorakenteita ulos

1056
00:53:54,060 --> 00:53:58,710
sinulle, mutta ei jokainen sellainen
ymmärtää, miten logiikkaa tämä toimii?

1057
00:53:58,710 --> 00:54:01,920
>> OK, viileä.

1058
00:54:01,920 --> 00:54:05,600
Joten B--T, ja sitten
aiot etsiä.

1059
00:54:05,600 --> 00:54:07,940
Seuraavan kerran olet menossa
nähdä, OH, hei, se on totta,

1060
00:54:07,940 --> 00:54:09,273
Näin Tiedän, että tämä on sana.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Sama asia eläintarha.

1063
00:54:13,770 --> 00:54:17,960
Joten tässä on asia juuri nyt, jos me
halusi etsiä eläintarhaan, juuri nyt,

1064
00:54:17,960 --> 00:54:20,780
tällä hetkellä eläintarha ei ole
sana sanakirjastamme

1065
00:54:20,780 --> 00:54:25,300
koska, kuten te voi nähdä,
ensinnäkin, että meillä on Boolen

1066
00:54:25,300 --> 00:54:28,590
return true on lopussa zoom.

1067
00:54:28,590 --> 00:54:30,430
Meillä on Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> Ja niin tässä, meillä ei oikeastaan
sana, eläintarha, meidän sanakirja

1069
00:54:33,900 --> 00:54:36,070
koska tämä valintaruutu ei ole valittuna.

1070
00:54:36,070 --> 00:54:39,540
Joten tietokone ei
tietävät, että eläintarha on sana

1071
00:54:39,540 --> 00:54:42,430
koska siten, että olemme
se on tallennettu vain zoom täällä

1072
00:54:42,430 --> 00:54:44,920
itse asiassa on totuusarvon
joka on kytketty totta.

1073
00:54:44,920 --> 00:54:49,380
Joten jos haluamme lisätä
sana, eläintarha, meidän sanakirja,

1074
00:54:49,380 --> 00:54:51,770
kuinka voisimme edetä tee sitä?

1075
00:54:51,770 --> 00:54:55,960
Mitä meidän on tehtävä, jotta voimme varmistaa
tietokone tietää, että Z-O-O on sana

1076
00:54:55,960 --> 00:54:58,130
ja ole ensimmäinen sana on Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> Yleisö: [äänetön]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI Peng: Aivan, me
haluat varmistaa, että tästä

1079
00:55:01,450 --> 00:55:07,890
täällä, että Boolen arvo on
tarkistanut pois, että se on totta.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, niin aiomme tarkistaa, että
joten tiedämme tarkalleen, hei, eläintarha on sana.

1081
00:55:13,297 --> 00:55:15,380
Aion kertoa
tietokoneeseen, se on sana niin

1082
00:55:15,380 --> 00:55:18,000
että kun tietokone tarkistaa,
se tietää, että eläintarha on sana.

1083
00:55:18,000 --> 00:55:21,269
>> Koska muistaa kaikki nämä tiedot
rakenteet, se on hyvin helppoa meille

1084
00:55:21,269 --> 00:55:22,310
sanoa, oh, lepakko on sana.

1085
00:55:22,310 --> 00:55:22,851
Zoo on sana.

1086
00:55:22,851 --> 00:55:23,611
Zoom on sana.

1087
00:55:23,611 --> 00:55:25,860
Mutta kun olet rakentamassa sitä,
tietokone ei ole aavistustakaan.

1088
00:55:25,860 --> 00:55:28,619
>> Joten sinun täytyy kertoa se tarkalleen
missä vaiheessa on tämä sana?

1089
00:55:28,619 --> 00:55:29,910
Missä vaiheessa se ole sana?

1090
00:55:29,910 --> 00:55:31,784
Ja missä vaiheessa minun
täytyy etsiä asioita,

1091
00:55:31,784 --> 00:55:34,000
ja missä vaiheessa minun täytyy mennä seuraavaksi?

1092
00:55:34,000 --> 00:55:37,010
Jokainen selvää siitä?

1093
00:55:37,010 --> 00:55:39,540
Viileä.

1094
00:55:39,540 --> 00:55:42,530
>> Ja niin sitten tulee
ongelma, miten voisimme

1095
00:55:42,530 --> 00:55:45,560
edetä lisäämällä jotain
se oikeastaan ​​ole siellä?

1096
00:55:45,560 --> 00:55:49,090
Joten vain sanoa haluamme lisätä
sana, kylpyamme, meidän trie.

1097
00:55:49,090 --> 00:55:53,589
Kuten te voi nähdä, kuten tällä hetkellä
meidän täytyy nyt on B--T,

1098
00:55:53,589 --> 00:55:55,630
ja tämä uusi tietorakenne
siellä oli pint että

1099
00:55:55,630 --> 00:55:59,740
viittasivat null koska oletamme
että, oi, ei ole sanoja jälkeen B--T,

1100
00:55:59,740 --> 00:56:02,530
miksi meidän täytyy pitää
ottaa asioita jälkeen T.

1101
00:56:02,530 --> 00:56:06,581
>> Mutta ongelma syntyy, jos teemme sinulle
haluavat sana joka tulee jälkeen

1102
00:56:06,581 --> 00:56:07,080
T: n.

1103
00:56:07,080 --> 00:56:09,500
Jos sinulla on kylpyamme, olet
menossa halua H oikealla.

1104
00:56:09,500 --> 00:56:13,290
Ja niin miten aiomme tehdä niin on
aiomme luoda erillinen solmu.

1105
00:56:13,290 --> 00:56:16,840
Emme jakaa summaksi
muistia tämän uuden taulukon,

1106
00:56:16,840 --> 00:56:20,720
ja aiomme siirtää osoittimia.

1107
00:56:20,720 --> 00:56:22,947
>> Aiomme antaa
H, Ensinnäkin, tämä null,

1108
00:56:22,947 --> 00:56:24,030
aiomme päästä eroon.

1109
00:56:24,030 --> 00:56:26,590
Aiomme olla
H-pisteen alaspäin.

1110
00:56:26,590 --> 00:56:30,600
Jos näemme H, haluamme sen
mennä jonnekin muualle.

1111
00:56:30,600 --> 00:56:33,910
>> Täällä voimme sitten ruksata kyllä.

1112
00:56:33,910 --> 00:56:38,170
Jos me osuma H jälkeen T, OH,
me tiedämme, että tämä on sana.

1113
00:56:38,170 --> 00:56:41,110
Boolean aikoo palata totta.

1114
00:56:41,110 --> 00:56:42,950
Jokainen selvää, miten se tapahtui?

1115
00:56:42,950 --> 00:56:45,110
OK.

1116
00:56:45,110 --> 00:56:47,214
>> Niin olennaisesti, kaikki
nämä tietorakenteita

1117
00:56:47,214 --> 00:56:50,130
että olemme ylittäneet tänään, olen
menneet heitä todella, todella nopeasti

1118
00:56:50,130 --> 00:56:52,192
eikä paljon
yksityiskohtaisesti, ja se on OK.

1119
00:56:52,192 --> 00:56:53,900
Kun aloitat Messing
sen kanssa, voit olla

1120
00:56:53,900 --> 00:56:55,733
pitää kirjaa siitä, missä
kaikki osoittimet ovat,

1121
00:56:55,733 --> 00:56:58,060
mitä tapahtuu omassa
tietorakenteita, jne.

1122
00:56:58,060 --> 00:56:59,810
He ovat erittäin hyödyllisiä,
ja se on sinun

1123
00:56:59,810 --> 00:57:03,890
kaverit täysin selvittää, miten
haluat toteuttaa asioita.

1124
00:57:03,890 --> 00:57:07,650
>> Ja niin pset4, on 5-- Voi, että on väärä.

1125
00:57:07,650 --> 00:57:10,140
Pset5 on kirjoitusvirheet.

1126
00:57:10,140 --> 00:57:13,710
Kuten aiemmin sanoin, olet menossa, kun
uudelleen, lataa lähdekoodin meiltä.

1127
00:57:13,710 --> 00:57:16,210
Siellä tulee olemaan kolme
asiat sinua lataamista.

1128
00:57:16,210 --> 00:57:18,470
Sinun ladata sanakirjoja,
KERS, ja tekstejä.

1129
00:57:18,470 --> 00:57:21,660
>> Kaikki nämä asiat ovat ovat
joko sanakirjoja sanoja

1130
00:57:21,660 --> 00:57:25,190
että haluamme tarkistaa
tai testi tiedot

1131
00:57:25,190 --> 00:57:26,930
että me haluamme teidän oikeinkirjoituksen tarkistus.

1132
00:57:26,930 --> 00:57:29,670
Ja niin sanakirjat
annamme aiot

1133
00:57:29,670 --> 00:57:34,870
antaa sinulle todellinen sanoja että haluamme
voit tallentaa jotenkin tavalla, joka on

1134
00:57:34,870 --> 00:57:36,530
tehokkaampi kuin jono.

1135
00:57:36,530 --> 00:57:38,470
Ja sitten tekstit ovat
olemaan mitä olemme

1136
00:57:38,470 --> 00:57:43,900
pyytää teitä oikeinkirjoituksen varmista
kaikilla sanoilla olemassa todellisia sanoja.

1137
00:57:43,900 --> 00:57:47,970
>> Ja niin kolme korttelin
ohjelmia, jotka annamme sinulle

1138
00:57:47,970 --> 00:57:51,130
kutsutaan dictionary.c,
dictionary.h, ja speller.c.

1139
00:57:51,130 --> 00:57:56,500
Ja niin kaikki dictionary.c tekee on
mitä sinua pyydetään toteuttamaan.

1140
00:57:56,500 --> 00:57:57,880
Se lataa sanoja.

1141
00:57:57,880 --> 00:58:02,000
Se oikeinkirjoituksen tarkistaa niitä, ja se varmistaa,
että kaikki on asetettu oikein.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h on vain kirjastotiedosto
että ilmoittaa kaikki toiminnot.

1143
00:58:05,180 --> 00:58:07,650
Ja speller.c, me aiomme antaa teille.

1144
00:58:07,650 --> 00:58:09,290
Sinun ei tarvitse muuttaa mitään siitä.

1145
00:58:09,290 --> 00:58:14,290
Kaikki speller.c ei on ottaa sen,
lataa sen, tarkistaa nopeus se,

1146
00:58:14,290 --> 00:58:19,190
testaa vertailukohtana kuten miten
nopeasti pystyt tekemään asioita.

1147
00:58:19,190 --> 00:58:20,410
>> Se on speller.

1148
00:58:20,410 --> 00:58:23,920
Eivät vain sotkea sitä, mutta varmista,
että ymmärrät mitä se tekee.

1149
00:58:23,920 --> 00:58:28,090
Käytämme toiminto nimeltään getrusage että
testaa suorituskykyä loitsu

1150
00:58:28,090 --> 00:58:28,590
Checker.

1151
00:58:28,590 --> 00:58:32,200
Kaikki se on periaatteessa testata
aika kaiken teidän sanakirjasta,

1152
00:58:32,200 --> 00:58:33,680
joten varmista, että ymmärrät sen.

1153
00:58:33,680 --> 00:58:36,660
Varo sotkea sitä tai
muuten asiat eivät toimi kunnolla.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> Ja suurin osa tähän haasteeseen on
te todella muuttaa dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Aiomme antaa teille
140.000 sanat sanakirjasta.

1157
00:58:48,526 --> 00:58:50,900
Aiomme antaa sinulle tekstiviestin
tiedoston, nämä sanat,

1158
00:58:50,900 --> 00:58:54,840
ja haluamme pystyä järjestämään
ne hajautustaulun tai trie

1159
00:58:54,840 --> 00:58:58,140
koska kun pyydämme teitä oikeinkirjoituksen
check-- kuvitella, jos olet loitsu

1160
00:58:58,140 --> 00:59:00,690
tarkkailun kuten Homeroksen Odysseia.

1161
00:59:00,690 --> 00:59:03,010
Se on kuin tämä valtava, valtava testi.

1162
00:59:03,010 --> 00:59:05,190
>> Kuvittele, jos joka ikinen
sana oli etsiä

1163
00:59:05,190 --> 00:59:08,100
läpi joukko 140000 arvoja.

1164
00:59:08,100 --> 00:59:10,350
Se kestää ikuisesti
oman koneen käydä.

1165
00:59:10,350 --> 00:59:14,490
Siksi haluamme organisoida
data tehokkaampi tietorakenteiden

1166
00:59:14,490 --> 00:59:17,270
kuten hajautustaulun tai trie.

1167
00:59:17,270 --> 00:59:20,700
Ja sitten te voi kind
ja kun haet pääsy

1168
00:59:20,700 --> 00:59:22,570
asioita helpommin ja nopeammin.

1169
00:59:22,570 --> 00:59:24,934
>> Ja joten ole varovainen ratkaista törmäyksiä.

1170
00:59:24,934 --> 00:59:27,350
Olet menossa saada nippu
sanoja, jotka alkavat A.

1171
00:59:27,350 --> 00:59:29,957
Olet menossa saada nippu sanoja
jotka alkavat B. Jopa sinua

1172
00:59:29,957 --> 00:59:31,290
kaverit, miten haluat sen ratkaisemiseksi.

1173
00:59:31,290 --> 00:59:34,144
Ehkä siellä on enemmän
tehokas tiivistefunktio

1174
00:59:34,144 --> 00:59:36,810
kuin vain ensimmäinen kirjain
jotain, ja niin se on sinun

1175
00:59:36,810 --> 00:59:38,190
kaverit sellaista tehdä mitä haluat.

1176
00:59:38,190 --> 00:59:40,148
>> Ehkä haluat lisätä
kaikki kirjaimet yhteen.

1177
00:59:40,148 --> 00:59:43,410
Ehkä haluat pidät tehdä outoja asioita
tilille kirjeiden määrä,

1178
00:59:43,410 --> 00:59:43,970
aivan sama.

1179
00:59:43,970 --> 00:59:45,386
Jopa te miten haluat tehdä.

1180
00:59:45,386 --> 00:59:49,262
Jos haluat tehdä hajautustaulun, jos
kannattaa kokeilla trie, täysin vain haluat.

1181
00:59:49,262 --> 00:59:52,470
Minä varoitan teitä etukäteen, että
trie on tyypillisesti hieman vaikeaa

1182
00:59:52,470 --> 00:59:54,520
vain koska siellä on paljon
lisää viitteitä seurata.

1183
00:59:54,520 --> 00:59:55,645
Mutta täysin jopa teitä.

1184
00:59:55,645 --> 00:59:58,742
Se on paljon tehokkaampaa
useimmissa tapauksissa.

1185
00:59:58,742 --> 01:00:01,450
Haluat todella pystyä pitämään
kirjaa kaikki osoittimia.

1186
01:00:01,450 --> 01:00:03,850
Kuten tehdä sama asia
että tein täällä.

1187
01:00:03,850 --> 01:00:06,871
Kun yrität lisätä
arvot hajautustaulun tai poistaa,

1188
01:00:06,871 --> 01:00:08,620
varmista, että olet
todella pitää kirjaa

1189
01:00:08,620 --> 01:00:11,860
missä kaikki on, koska
se on todella helppoa jos olen

1190
01:00:11,860 --> 01:00:14,727
yrittää lisätä kuten sana, Andy.

1191
01:00:14,727 --> 01:00:16,810
Sanotaan vain, että on
oikea sana, sana, Andy,

1192
01:00:16,810 --> 01:00:19,640
jättimäisen luettelon sanoista.

1193
01:00:19,640 --> 01:00:22,450
>> Jos minä vain sattuvat siirtää
osoitin väärä, oho,

1194
01:00:22,450 --> 01:00:24,940
siellä menee kokonaisuudessaan
loppuelämäni linkitetyn listan.

1195
01:00:24,940 --> 01:00:26,897
Nyt vain sana I
on on Andy, ja nyt

1196
01:00:26,897 --> 01:00:29,230
kaikki muut sanat
Sanakirja on menetetty.

1197
01:00:29,230 --> 01:00:31,370
Ja niin haluat varmistaa, että sinulla
seurata kaikki osoittimet

1198
01:00:31,370 --> 01:00:33,661
tai muuten olet menossa saada
valtavia ongelmia koodissa.

1199
01:00:33,661 --> 01:00:35,840
Piirrä asioita huolellisesti askel askeleelta.

1200
01:00:35,840 --> 01:00:37,870
Se tekee siitä paljon helpompi ajatella.

1201
01:00:37,870 --> 01:00:40,910
>> Ja lopuksi, haluat pystyä
testata suorituskykyä ohjelman

1202
01:00:40,910 --> 01:00:41,618
iso aluksella.

1203
01:00:41,618 --> 01:00:43,710
Jos te ottaa
katsokaa CS50 juuri nyt,

1204
01:00:43,710 --> 01:00:45,210
meillä on mitä kutsutaan iso board.

1205
01:00:45,210 --> 01:00:50,200
Se on arvostelukaavakkeen nopeimmin
oikoluvun kertaa kaikilla on CS50

1206
01:00:50,200 --> 01:00:55,720
juuri nyt, mielestäni top kuin 10
kertaa Luulen kahdeksan heistä ovat henkilökunnan.

1207
01:00:55,720 --> 01:00:57,960
Haluamme todella te lyödä meitä.

1208
01:00:57,960 --> 01:01:00,870
>> Kaikki meistä yrittivät toteuttaa
nopein koodi kuin mahdollista.

1209
01:01:00,870 --> 01:01:04,880
Haluamme te yrittää haastaa
meille ja toteuttaa nopeammin kuin me kaikki

1210
01:01:04,880 --> 01:01:05,550
voi.

1211
01:01:05,550 --> 01:01:07,970
Ja niin tämä on todella
ensimmäisen kerran, että olemme

1212
01:01:07,970 --> 01:01:12,680
pyytää te tehdä PSET joka
voit todella tehdä missä tahansa menetelmässä

1213
01:01:12,680 --> 01:01:13,760
haluat.

1214
01:01:13,760 --> 01:01:17,730
>> Sanon aina, tämä on enemmän sukua
ja tosielämän ratkaisu, eikö?

1215
01:01:17,730 --> 01:01:19,550
Sanon, hei, tarvitsen sinua tekemään tämän.

1216
01:01:19,550 --> 01:01:21,380
Rakenna ohjelma, joka tekee tämän minulle.

1217
01:01:21,380 --> 01:01:22,630
Tee se kuitenkin haluat.

1218
01:01:22,630 --> 01:01:24,271
Tiedän vain, että haluan nopeasti.

1219
01:01:24,271 --> 01:01:25,770
Se on sinun haaste tällä viikolla.

1220
01:01:25,770 --> 01:01:27,531
Kaverit, aiomme
antaa sinulle tehtävän.

1221
01:01:27,531 --> 01:01:29,030
Aiomme antaa teille haasteen.

1222
01:01:29,030 --> 01:01:31,559
Ja sitten se on sinun kaverit
täysin vain selvittää

1223
01:01:31,559 --> 01:01:34,100
mikä on nopein ja
tehokas tapa toteuttaa tätä.

1224
01:01:34,100 --> 01:01:34,600
Joo?

1225
01:01:34,600 --> 01:01:37,476
>> Yleisö: Olemmeko saa jos
halusi tutkia nopeammin tapoja

1226
01:01:37,476 --> 01:01:40,821
tehdä hash taulukoita verkossa, voimme tehdä
että ja mainitsevat jonkun toisen koodia?

1227
01:01:40,821 --> 01:01:42,070
ANDI Peng: Joo, täysin hieno.

1228
01:01:42,070 --> 01:01:44,320
Joten jos te lukea
spec, siellä linja

1229
01:01:44,320 --> 01:01:48,310
spec joka sanoo te
ovat täysin vapaasti tutkimukseen hash

1230
01:01:48,310 --> 01:01:51,070
toimintoja mitkä ovat joitakin
ja nopeammin hash toimintoja

1231
01:01:51,070 --> 01:01:54,720
ajaa asioita läpi kuin
kunhan mainita, että koodin.

1232
01:01:54,720 --> 01:01:57,220
Joten jotkut ihmiset ovat jo
tajunnut nopeasti tapoja

1233
01:01:57,220 --> 01:02:00,250
tehdä oikolukuohjelmia, nopeasti
tapoja tallentaa tietoa.

1234
01:02:00,250 --> 01:02:02,750
Täysin vain te, jos
haluavat vain ottaa sen?

1235
01:02:02,750 --> 01:02:04,045
Varmista, että olet vedoten.

1236
01:02:04,045 --> 01:02:06,170
Haasteena todella
että yritämme testata

1237
01:02:06,170 --> 01:02:09,750
on varmistaa, että tiedät
päin osoittimia.

1238
01:02:09,750 --> 01:02:12,700
Niin pitkälle kuin täytäntöönpanosta
todellinen tiivistefunktio

1239
01:02:12,700 --> 01:02:15,070
ja keksiä kuten
matematiikka tehdä niin,

1240
01:02:15,070 --> 01:02:17,570
te voi tutkia mitä tahansa
menetelmiä online-kaverit haluavat.

1241
01:02:17,570 --> 01:02:17,996
Joo?

1242
01:02:17,996 --> 01:02:19,700
>> Yleisö: Voimmeko mainita vain
käyttämällä [äänetön]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI Peng: Joo.

1244
01:02:20,120 --> 01:02:22,328
Voit vain, sinun kommentti,
voit mainita kuten, oh,

1245
01:02:22,328 --> 01:02:26,127
otettu yada, Yada,
Yada, tiivistefunktio.

1246
01:02:26,127 --> 01:02:27,210
Kellään mitään kysyttävää?

1247
01:02:27,210 --> 01:02:29,694
Me itse asiassa breezed
kautta jakso tänään.

1248
01:02:29,694 --> 01:02:31,610
Aion olla jopa täällä
vastata kysymyksiin samoin.

1249
01:02:31,610 --> 01:02:36,570
>> Myös, kuten sanoin, toimisto
tuntia tänään ja huomenna.

1250
01:02:36,570 --> 01:02:40,307
Spec tällä viikolla on oikeastaan
erittäin helppo ja erittäin lyhyt lukea.

1251
01:02:40,307 --> 01:02:43,140
Ehdotan ottaa tarkastella, vain
lukea läpi kokonaisuudessaan se.

1252
01:02:43,140 --> 01:02:45,730
>> Ja Zamyla todella kävelee sinua
kullakin toimintojen

1253
01:02:45,730 --> 01:02:49,796
sinun täytyy toteuttaa, ja niin se on
hyvin, hyvin selvää, kuinka tehdä kaikkea.

1254
01:02:49,796 --> 01:02:51,920
Vain varmista, että olet
pitää kirjaa osoittimia.

1255
01:02:51,920 --> 01:02:53,650
Tämä on erittäin haastava PSET.

1256
01:02:53,650 --> 01:02:56,744
>> Se ei ole haastavaa, koska kuten,
oh, käsitteet ovat niin paljon enemmän

1257
01:02:56,744 --> 01:02:59,160
vaikea, tai sinun täytyy oppia
niin paljon uusia syntaksi tavalla

1258
01:02:59,160 --> 01:03:00,650
että teit viime PSET.

1259
01:03:00,650 --> 01:03:03,320
Tämä PSET on vaikeaa, koska
on niin paljon viitteitä,

1260
01:03:03,320 --> 01:03:06,980
ja sitten se on hyvin, hyvin helppo kerran
sinulla vian koodi ei voi

1261
01:03:06,980 --> 01:03:08,315
löytää missä se vika on.

1262
01:03:08,315 --> 01:03:13,200
>> Ja niin täydellisestä uskon sinua
kaverit pystyä voittamaan meidän [äänetön]

1263
01:03:13,200 --> 01:03:13,700
kirjoitusasuja.

1264
01:03:13,700 --> 01:03:16,640
Minulla on oikeastaan ​​ole mitään kirjallista minun
vielä, mutta olen aikeissa kirjoittaa minun.

1265
01:03:16,640 --> 01:03:19,070
Joten kun olet kirjoittamassa
sinun, otan kirjallisesti minun.

1266
01:03:19,070 --> 01:03:21,070
Aion yrittää tehdä
minun nopeammin kuin sinun.

1267
01:03:21,070 --> 01:03:23,940
Näemme kuka on nopein.

1268
01:03:23,940 --> 01:03:27,340
>> Ja joo, minä näen kaikki
te täällä tiistaina.

1269
01:03:27,340 --> 01:03:29,510
Käyn sellaista kuin PSET työpaja.

1270
01:03:29,510 --> 01:03:32,640
Kaikki osat tämän
viikko ovat PSET työpajoja,

1271
01:03:32,640 --> 01:03:36,690
joten teillä paljon mahdollisuuksia
apua, virka kuten aina,

1272
01:03:36,690 --> 01:03:41,330
ja minä todella odotan
lukeminen kaikki kaverit "koodi.

1273
01:03:41,330 --> 01:03:44,160
Minulla on tietokilpailuja tänne jos
kaverit haluavat tulla saada näitä.

1274
01:03:44,160 --> 01:03:45,880
Siinä kaikki.

1275
01:03:45,880 --> 01:03:48,180