1
00:00:00,000 --> 00:00:11,460

2
00:00:11,460 --> 00:00:12,250
>> DAVID MALAN: Okei.

3
00:00:12,250 --> 00:00:13,860
Tervetuloa takaisin CS50.

4
00:00:13,860 --> 00:00:16,190
Tämä on alku viikolla 8.

5
00:00:16,190 --> 00:00:21,320
Ja muistaa, että ongelma asetettu 5 päättyi
kanssa hieman haastetta.

6
00:00:21,320 --> 00:00:25,210
Joten olettaen talteen kaikki
Opetuksen Fellows ja CA: n valokuvia

7
00:00:25,210 --> 00:00:30,480
vuonna card.raw tiedoston, olet oikeutettu
nyt löytää kaikki ne ihmiset, ja

8
00:00:30,480 --> 00:00:34,510
yksi onnekas voittaja kävellä kotiin yhdellä
näistä asioista, harppaus liikettä

9
00:00:34,510 --> 00:00:37,450
laite, että voit käyttää lopullisen
hankkeita, esimerkiksi.

10
00:00:37,450 --> 00:00:39,860
>> Tämä, joka vuosi, johtaa
vähän creepiness.

11
00:00:39,860 --> 00:00:43,480
Ja niin mitä ajattelin tehdä, on kertoa
teille joitakin säveliä, jotka ovat

12
00:00:43,480 --> 00:00:47,370
mennyt edestakaisin
henkilöstön luettelo myöhään.

13
00:00:47,370 --> 00:00:51,110
Esimerkiksi juuri viime yönä, lainaus
listatut, yhdestä henkilöstön

14
00:00:51,110 --> 00:00:55,000
jäsenet, "Minulla oli opiskelija knock
oveni ottaa valokuvan kanssani.

15
00:00:55,000 --> 00:00:59,020
Stalkers, minä sanon teille. "Aloitit
melko kuvaileva ja sitten muutimme

16
00:00:59,020 --> 00:01:02,830
edelleen, tunti tai niin myöhemmin, "Minulla oli
opiskelija odottaa minua jakson jälkeen

17
00:01:02,830 --> 00:01:06,080
Hän oli meidän kaikkien nimet ja kuvat
joitakin arkkia paperia. "Selvä.

18
00:01:06,080 --> 00:01:09,230
Niin järjestetty, mutta ei
kaikki kammottava vielä.

19
00:01:09,230 --> 00:01:12,520
>> Sitten, "Olin poissa kaupungista tänä viikonloppuna,
ja kun tulin takaisin, oli yksi

20
00:01:12,520 --> 00:01:12,630
minun

21
00:01:12,630 --> 00:01:16,740
makuuhuone. "[naurua]

22
00:01:16,740 --> 00:01:20,410
DAVID MALAN: Seuraava lainaus henkilöstö
jäsen ", opiskelija tuli kotiini

23
00:01:20,410 --> 00:01:25,330
Somerville kello 4 aamulla. "Seuraava
henkilökunta, "pääsin hotelli San

24
00:01:25,330 --> 00:01:30,016
Francisco ja opiskelija odotti
minua aulassa kolme DSLRs. "

25
00:01:30,016 --> 00:01:31,510
Tyyppinen kamera.

26
00:01:31,510 --> 00:01:34,980
"En ole edes henkilökuntaa tämän lukukauden,
mutta opiskelija murtautui talooni tämän

27
00:01:34,980 --> 00:01:40,480
aamu ja kirjataan koko juttu
Google Glass. "Ja sitten lopuksi,

28
00:01:40,480 --> 00:01:43,650
"Ainakin 12 ihmistä olivat innokkaasti
odottavat minua, kun sain ulos

29
00:01:43,650 --> 00:01:44,800
limusiinin, ja sitten minä

30
00:01:44,800 --> 00:01:46,970
heräsi. "Selvä.

31
00:01:46,970 --> 00:01:57,690
Joten keskuudessa valokuvia, kuten ehkä
muistaa, ovat tämän kaveri täällä, kuka olet

32
00:01:57,690 --> 00:02:01,850
voi tietää kuin Milo Banana, joka asuu
Lauren Carvalho, meidän pään

33
00:02:01,850 --> 00:02:02,905
opetus Fellow.

34
00:02:02,905 --> 00:02:05,170
Milo, Milo, tule tänne poika.

35
00:02:05,170 --> 00:02:06,320
Milo.

36
00:02:06,320 --> 00:02:08,650
Milo.

37
00:02:08,650 --> 00:02:12,230
Huomatkaa, hän on päällään Google Glass, joten
näytämme sinulle kaiken tämän jälkeen.

38
00:02:12,230 --> 00:02:16,190
Joten tämä on Milo, jos haluat
ottaa valokuvan hänestä jälkeenpäin.

39
00:02:16,190 --> 00:02:18,240
Jos haluat varoa
yleisöön siellä.

40
00:02:18,240 --> 00:02:19,430
OK.

41
00:02:19,430 --> 00:02:20,200
Se on hyvä kuvamateriaalia.

42
00:02:20,200 --> 00:02:22,556
No, Milo Banana.

43
00:02:22,556 --> 00:02:23,941
Voi, älä tee sitä.

44
00:02:23,941 --> 00:02:29,020
>> [Naurua]

45
00:02:29,020 --> 00:02:29,470
>> OK.

46
00:02:29,470 --> 00:02:34,550
Joten sana sitten mitä on edessä,
sillä kun alamme siirtyminen,

47
00:02:34,550 --> 00:02:38,410
tällä viikolla nimenomaan, alkaen C
komentoriviympäristössä PHP ja

48
00:02:38,410 --> 00:02:42,720
JavaScript ja SQL ja HTML ja CSS
web-pohjainen ympäristö, me olemme

49
00:02:42,720 --> 00:02:44,490
varustaminen sinulle kaikki
lisää tietämystä

50
00:02:44,490 --> 00:02:46,010
mahdollisten lopullisten hankkeita.

51
00:02:46,010 --> 00:02:49,240
Kohti sitä varten kurssi on
perinteisesti järjestetty seminaareja, jotka

52
00:02:49,240 --> 00:02:50,950
ovat sivuaa aiheita
sen kurssin.

53
00:02:50,950 --> 00:02:54,330
Hyvin paljon ohjelmointia ja
app kehitystä ja niin edelleen, mutta

54
00:02:54,330 --> 00:02:57,010
ei välttämättä selvittävät
Tietenkin oma oppimäärä.

55
00:02:57,010 --> 00:03:00,250
>> Joten jos saatat olla kiinnostunut yksi
tai enemmän tämän vuoden seminaareja,

56
00:03:00,250 --> 00:03:02,530
rekisteröityä cs50.net/seminar.

57
00:03:02,530 --> 00:03:06,170
On vanhempia seminaarit
klo cs50.net/seminars.

58
00:03:06,170 --> 00:03:10,620
Ja lista tähän mennessä tänä vuonna
ovat Amazing Web Apps kanssa Ruby on

59
00:03:10,620 --> 00:03:13,580
Kiskot, joka on vaihtoehtoinen
kieli PHP.

60
00:03:13,580 --> 00:03:14,900
Computational Linguistics.

61
00:03:14,900 --> 00:03:18,710
Johdatus IOS, joka on
alustan, joka käyttää iPhone ja

62
00:03:18,710 --> 00:03:19,850
iPad kehitystä.

63
00:03:19,850 --> 00:03:22,890
JavaScript Web Apps, me kattaa
että, mutta tässä seminaarissa, voit mennä

64
00:03:22,890 --> 00:03:24,070
yksityiskohtaisempi.

65
00:03:24,070 --> 00:03:27,390
>> Leap Motion, niin me todella on joitakin
meidän ystäviä Leap Motion,

66
00:03:27,390 --> 00:03:29,160
yhtiölle itselleen, liittyä meihin.

67
00:03:29,160 --> 00:03:31,800
Huomenna, itse asiassa, jotta voidaan tarjota
käytännön seminaarin, jos

68
00:03:31,800 --> 00:03:33,320
kiinnostaa sinua.

69
00:03:33,320 --> 00:03:38,770
Meteor.js, vaihtoehtoinen tekniikka
JavaScriptin avulla ei selain,

70
00:03:38,770 --> 00:03:39,970
mutta palvelimella.

71
00:03:39,970 --> 00:03:42,110
Node.js, joka on hyvin paljon
että vein samoin.

72
00:03:42,110 --> 00:03:43,650
Tyylikäs Android muotoilu.

73
00:03:43,650 --> 00:03:46,990
Android on erittäin suosittu vaihtoehto
iOS ja Windows Phone

74
00:03:46,990 --> 00:03:48,790
ja muut mobiilialustoille.

75
00:03:48,790 --> 00:03:51,180
Ja Web Security Active Defense.

76
00:03:51,180 --> 00:03:54,590
>> Joten itse asiassa, jos haluat
osallistua tähän, haluan

77
00:03:54,590 --> 00:03:55,840
muistiin tämän.

78
00:03:55,840 --> 00:03:57,790
Olemme erittäin iloinen voidessani todeta, että
ystävämme Leap

79
00:03:57,790 --> 00:03:59,140
Motion, joka on käynnistyksen -

80
00:03:59,140 --> 00:04:01,300
tämä laite todella vain tuli
muutama kuukausi sitten -

81
00:04:01,300 --> 00:04:05,960
on armollisesti lahjoitti 30 tällaisia ​​laitteita
luokkaan, niin monet opiskelijat, jos

82
00:04:05,960 --> 00:04:08,670
haluat lainata laitteisto
kohti lukukauden lopussa ja käyttää sitä

83
00:04:08,670 --> 00:04:10,390
Varsinainen opinnäytetyön.

84
00:04:10,390 --> 00:04:11,890
Ne tukevat useita kieliä.

85
00:04:11,890 --> 00:04:16,040
Mikään niistä C, mikään niistä PHP, niin
saavuttamaan yksi tai useampi näistä seminaareja

86
00:04:16,040 --> 00:04:16,899
saattaa osoittautua kohteisiin.

87
00:04:16,899 --> 00:04:19,730
Ja ne kaikki on kuvattu
Jos et pysty

88
00:04:19,730 --> 00:04:21,380
osallistua henkilökohtaisesti.

89
00:04:21,380 --> 00:04:25,000
Aikataulu julkistetaan kautta
email me jähmettyä huonetta.

90
00:04:25,000 --> 00:04:28,460
>> Ja lopuksi, jos menet
projects.cs.50.net, tämä on sivusto

91
00:04:28,460 --> 00:04:31,450
meidän pitää joka vuosi, että kutsumme
folks yhteisö, tiedekunta,

92
00:04:31,450 --> 00:04:36,420
yksiköt, henkilökunta ja molemmat
in ulkopuolella CS50 on

93
00:04:36,420 --> 00:04:37,730
ehdottaa projekti-ideoita.

94
00:04:37,730 --> 00:04:39,050
Asiat kiinnostavat opiskelijaryhmille.

95
00:04:39,050 --> 00:04:40,600
Kiinnostavia asioita osastojen.

96
00:04:40,600 --> 00:04:43,990
Joten älä käännä siellä, jos olet kamppailee
epävarmuutta siitä, mitä

97
00:04:43,990 --> 00:04:46,700
itse haluaisi puuttua.

98
00:04:46,700 --> 00:04:51,760
>> Joten viimeinen kerta toimme kiistatta
monimutkaisempi tietorakenne kuin olimme

99
00:04:51,760 --> 00:04:53,300
nähdään viikkoa aikaisemmin.

100
00:04:53,300 --> 00:04:56,550
Olimme käyttäen paneelit melko
onnellisina hyödyllistä, jos

101
00:04:56,550 --> 00:04:58,160
yksinkertainen tietorakenne.

102
00:04:58,160 --> 00:05:00,570
Sitten otimme käyttöön nämä, jotka
tietenkin liittyvät luettelot.

103
00:05:00,570 --> 00:05:05,470
Ja mikä oli yksi motiiveja
käyttöön tämän tietorakenne?

104
00:05:05,470 --> 00:05:06,930
Niin?

105
00:05:06,930 --> 00:05:07,250
Mikä tuo on?

106
00:05:07,250 --> 00:05:08,080
>> Yleisö: Dynamic koko.

107
00:05:08,080 --> 00:05:09,040
>> DAVID MALAN: Dynamic koko.

108
00:05:09,040 --> 00:05:11,890
Joten taas joukko, joudut
tietää sen koko etukäteen, kun

109
00:05:11,890 --> 00:05:12,740
voit jakaa sitä.

110
00:05:12,740 --> 00:05:14,380
Vuonna linkitetty lista, et
täytyy tietää, että.

111
00:05:14,380 --> 00:05:17,610
Voit vain malloc, tai yleisemmin
myöntää lisää

112
00:05:17,610 --> 00:05:20,720
solmu, niin sanotusti, milloin tahansa
haluat lisätä enemmän tietoa.

113
00:05:20,720 --> 00:05:22,670
Ja solmu ei ole ennalta määrättyä merkitystä.

114
00:05:22,670 --> 00:05:25,580
Se on vain yleinen termi, joka kuvaa
jonkinlainen säiliö, että olemme

115
00:05:25,580 --> 00:05:29,610
käyttämällä meidän tietorakenne tallentaa
jotkut erä kohteisiin, jotka tässä

116
00:05:29,610 --> 00:05:31,750
Jos sattuvat olemaan kokonaislukuja.

117
00:05:31,750 --> 00:05:33,160
>> Mutta on aina kompromissi.

118
00:05:33,160 --> 00:05:38,070
Joten saamme dynaaminen koot tiedot
rakenne, mutta paljonko maksaa me maksamme?

119
00:05:38,070 --> 00:05:40,040
Mitä haittapuoli linkitettyjen listojen?

120
00:05:40,040 --> 00:05:41,006
Niin?

121
00:05:41,006 --> 00:05:41,980
>> Yleisö: Vaatii enemmän muistia.

122
00:05:41,980 --> 00:05:44,240
>> DAVID MALAN: se vaatii enemmän
muisti, miten tarkalleen?

123
00:05:44,240 --> 00:05:46,440
>> Yleisö: [kuultavissa].

124
00:05:46,440 --> 00:05:47,050
>> DAVID MALAN: Aivan.

125
00:05:47,050 --> 00:05:50,460
Joten nyt meillä on viitteitä aloittamisesta
lisämuistia, että aiemmin

126
00:05:50,460 --> 00:05:53,040
ei tarvitse, koska etu
array, on tietenkin se, että

127
00:05:53,040 --> 00:05:54,860
kaikki on yhtenäinen, takaisin
takaisin takaisin, joka

128
00:05:54,860 --> 00:05:56,380
antaa random access.

129
00:05:56,380 --> 00:06:00,710
Koska vain käyttämällä hakasulkeen
merkintä, tai teknisesti osoitin

130
00:06:00,710 --> 00:06:03,580
aritmeettinen, hyvin yksinkertainen Lisäksi
Pääsetkö

131
00:06:03,580 --> 00:06:05,700
elementit jatkuvasti ajan.

132
00:06:05,700 --> 00:06:08,975
Ja itse asiassa, että on tavallaan vihjaten
toinen hinta, että maksat kanssa

133
00:06:08,975 --> 00:06:09,760
linkitetty lista.

134
00:06:09,760 --> 00:06:13,890
>> Mitä tapahtuu käyntiaika
jotain Etsi, jos haluan

135
00:06:13,890 --> 00:06:17,270
löytää arvo ja sisällä
of linkitetty lista?

136
00:06:17,270 --> 00:06:20,290
Mitä minun käyntiaika tullut?

137
00:06:20,290 --> 00:06:21,560
Big O n.

138
00:06:21,560 --> 00:06:24,060
Jos se lajitellaan?

139
00:06:24,060 --> 00:06:25,440
Mitä jos tietorakenne on järjestetty?

140
00:06:25,440 --> 00:06:28,640
Voinko tehdä paremmin kuin suuret
O n etsimiseen?

141
00:06:28,640 --> 00:06:31,700
Ei, koska pahimmassa tapauksessa se voisi
hyvin lajitellaan, mutta määrä

142
00:06:31,700 --> 00:06:32,950
etsit saattaa olla suuri.

143
00:06:32,950 --> 00:06:35,370
Se voi olla numero 100, joka
ehkä sattuvat olemaan kaikki

144
00:06:35,370 --> 00:06:36,410
Muuten lopussa.

145
00:06:36,410 --> 00:06:39,950
Ja koska voit käyttää vain linkitetyn
Luettelen tällä täytäntöönpano

146
00:06:39,950 --> 00:06:42,690
tapa sen ensimmäisen solmun, olet
vielä sellainen epäonninen.

147
00:06:42,690 --> 00:06:47,450
Sinun täytyy kulkea koko juttu
ensimmäisestä viimeiseen, jotta löydettäisiin

148
00:06:47,450 --> 00:06:49,150
että iso arvo kuin 100.

149
00:06:49,150 --> 00:06:51,350
Tai onko se
ei edes siellä.

150
00:06:51,350 --> 00:06:55,960
>> Joten emme voi tehdä mitä algoritmia datan
rakenne, joka näyttää tältä?

151
00:06:55,960 --> 00:06:59,460
Emme voi tehdä binäärihaku, koska
binäärihaku vaaditaan, että meillä oli

152
00:06:59,460 --> 00:07:00,740
random access.

153
00:07:00,740 --> 00:07:04,500
Voisimme vain harppaus sijainnista
sijainti ilman seuraa

154
00:07:04,500 --> 00:07:07,080
Näiden korppujauhoja muodossa
kaikki nämä viitteet.

155
00:07:07,080 --> 00:07:08,300
>> Nyt, miten voimme toteuttaa tämän?

156
00:07:08,300 --> 00:07:12,830
No, jos menemme näytön täällä, jos
Voimme nopeasti reimplement nämä tiedot

157
00:07:12,830 --> 00:07:13,440
rakenne -

158
00:07:13,440 --> 00:07:15,670
minun käsiala ei ole kaikki, että
hyvä täällä, mutta me yritämme.

159
00:07:15,670 --> 00:07:22,030
Joten struct, ja mitä tein
haluat soittaa tämä asia täällä?

160
00:07:22,030 --> 00:07:22,960
Solmu.

161
00:07:22,960 --> 00:07:24,580
Joten Haen alkoi.

162
00:07:24,580 --> 00:07:27,860
Ja nyt, mitä pitää sisällä
datarakenteen, että yksittäin

163
00:07:27,860 --> 00:07:28,430
linkitetty lista?

164
00:07:28,430 --> 00:07:29,950
Kuinka monilla aloilla?

165
00:07:29,950 --> 00:07:30,450
>> Joten kaksi.

166
00:07:30,450 --> 00:07:31,570
Yksi on melko helppoa.

167
00:07:31,570 --> 00:07:33,050
Joten int n.

168
00:07:33,050 --> 00:07:35,930
Ja voisimme kutsua n mitä me haluamme,
mutta sen pitäisi olla int, jos olemme

169
00:07:35,930 --> 00:07:37,660
täytäntöön linkitetty lista ints.

170
00:07:37,660 --> 00:07:41,920
Ja nyt, mitä tekee toinen
alan olla?

171
00:07:41,920 --> 00:07:43,460
Struct solmu *.

172
00:07:43,460 --> 00:07:50,570
Joten jos en struct solmu *, ja sitten minä
voi kutsua tätä myös mitä haluan,

173
00:07:50,570 --> 00:07:53,510
mutta vain olla selkeä soitan
sitä seuraava, kuten olemme tehneet.

174
00:07:53,510 --> 00:07:55,270
Ja sitten minä suljen aaltosulkeita.

175
00:07:55,270 --> 00:08:00,700
>> Ja nyt, kuin viime kerralla,
Laitoin solmun tänne.

176
00:08:00,700 --> 00:08:03,830
Mutta jos olen julistaa tämä on niin
solmu, miksi olen vaivautua on niin

177
00:08:03,830 --> 00:08:07,320
verbose täällä julistaa struct
solmu * seuraavaksi, toisin

178
00:08:07,320 --> 00:08:09,210
vain solmu * seuraavaksi?

179
00:08:09,210 --> 00:08:09,904
Niin?

180
00:08:09,904 --> 00:08:12,810
>> Yleisö: [kuultavissa].

181
00:08:12,810 --> 00:08:14,050
>> DAVID MALAN: Aivan.

182
00:08:14,050 --> 00:08:14,530
Täsmälleen.

183
00:08:14,530 --> 00:08:18,320
Koska C todella vie kirjaimellisesti ja
näkee vain määritelmän solmun

184
00:08:18,320 --> 00:08:21,230
alas täällä, et voi
viitata siihen täällä.

185
00:08:21,230 --> 00:08:24,760
Joten meillä on tällainen ennaltaehkäisevä
ilmoitus täällä, joka on tosin

186
00:08:24,760 --> 00:08:25,390
Pidempi.

187
00:08:25,390 --> 00:08:27,810
Struct solmu, joka tarkoittaa
voimme nyt käyttää sitä

188
00:08:27,810 --> 00:08:29,760
sisällä tieto-rakenteesta.

189
00:08:29,760 --> 00:08:33,370
>> Ja syrjään, koska tämä on
tulossa hieman subjektiivinen nyt

190
00:08:33,370 --> 00:08:36,230
tähti voi teknisesti mennä täällä,
se voi mennä täällä, se voi

191
00:08:36,230 --> 00:08:37,179
jopa mennä keskellä.

192
00:08:37,179 --> 00:08:39,890
Olemme hyväksytty, tyyliin opas
Tietenkin yleissopimus laskemisesta

193
00:08:39,890 --> 00:08:42,299
tähden vieressä tiedot
tyyppi, joka tässä tapauksessa

194
00:08:42,299 --> 00:08:43,460
olisi struct solmu.

195
00:08:43,460 --> 00:08:46,620
Mutta realisoida paljon oppikirjoja ja
online-viittauksia, saatat todellakin

196
00:08:46,620 --> 00:08:48,450
nähdä sen toisella puolella.

197
00:08:48,450 --> 00:08:52,200
Mutta vain ymmärtää, että molemmat todella
työtä ja sinun pitäisi vain olla

198
00:08:52,200 --> 00:08:52,970
johdonmukainen.

199
00:08:52,970 --> 00:08:53,580
>> Selvä.

200
00:08:53,580 --> 00:08:55,630
Niin, että oli meidän ilmoitus
struct solmu.

201
00:08:55,630 --> 00:08:59,430
Mutta sitten aloimme tehdä enemmän
kehittyneempiä asioita.

202
00:08:59,430 --> 00:09:03,410
Esimerkiksi päätimme ottaa käyttöön
jotain tiiviste.

203
00:09:03,410 --> 00:09:08,160
Joten tässä on hash taulukon koko on n,
indeksoitu 0 päälle vasemmalle n

204
00:09:08,160 --> 00:09:09,690
miinus 1 vasemmassa alareunassa.

205
00:09:09,690 --> 00:09:11,640
Tämä voisi olla hash
taulukossa mitään.

206
00:09:11,640 --> 00:09:15,340
Mutta millaisia ​​asioita ei puhumme
noin käyttämällä hash taulukon?

207
00:09:15,340 --> 00:09:18,370
Tallentaminen mitä?

208
00:09:18,370 --> 00:09:18,800
>> Nimet.

209
00:09:18,800 --> 00:09:20,870
Voisimme tehdä nimiä kuten
teimme viime kerralla.

210
00:09:20,870 --> 00:09:22,200
Ja oikeastaan, voit tallentaa mitään.

211
00:09:22,200 --> 00:09:24,640
Ja näemme tämän uudelleen
PHP ja JavaScript.

212
00:09:24,640 --> 00:09:28,550
Tiiviste on mukava eräänlainen Sveitsin
Armeijan veitsi, jonka avulla voit tallentaa

213
00:09:28,550 --> 00:09:33,690
aika paljon mitä haluat sisällä
se liittämällä avaimet arvot.

214
00:09:33,690 --> 00:09:34,770
Avaimet arvot.

215
00:09:34,770 --> 00:09:37,800
>> Nyt tässä yksinkertaisessa tapauksessa meidän
avaimet ovat vain numeroita.

216
00:09:37,800 --> 00:09:40,380
Olemme täytäntöönpanosta hash
taulukon array.

217
00:09:40,380 --> 00:09:43,500
Ja niin näppäimet ovat 0,
1, 2, ja niin edelleen.

218
00:09:43,500 --> 00:09:47,200
Ja niin me, ihmisinä, päätti viime
viikolla, että tiedät mitä, jos olemme

219
00:09:47,200 --> 00:09:50,410
menossa tallentaa nimiä, haluan vain
mielivaltaisesti, vaan ihan kohtuullisesti,

220
00:09:50,410 --> 00:09:54,680
olettaa, että Alice, nimi,
vain indeksoidaan 0.

221
00:09:54,680 --> 00:09:58,030
Ja Bob, B nimen, indeksoidaan
otetaan 1, ja niin edelleen.

222
00:09:58,030 --> 00:10:02,490
Joten meillä oli kartoitus tulojen välillä,
jotka ovat jouset, ja hash

223
00:10:02,490 --> 00:10:04,560
paikoissa, jotka ovat numeroita.

224
00:10:04,560 --> 00:10:07,740
>> Niin, että prosessi on yleisesti tunnettu
hash funktio, ja voit todella

225
00:10:07,740 --> 00:10:09,130
pantava se koodi.

226
00:10:09,130 --> 00:10:12,080
Jos halusin toteuttaa hajautusfunktio
joka tekee täsmälleen mitä me

227
00:10:12,080 --> 00:10:17,070
juuri kuvattu viime aikaa, voisin
julistaa funktio, joka ottaa, koska

228
00:10:17,070 --> 00:10:18,330
input esimerkiksi -

229
00:10:18,330 --> 00:10:22,190
ja tehdään tämä tästä
näytön tänne.

230
00:10:22,190 --> 00:10:26,180
Jos halusin toteuttaa hash
toiminto, voisin sanoa

231
00:10:26,180 --> 00:10:27,410
jotain tällaista.

232
00:10:27,410 --> 00:10:29,030
>> Se tulee palauttaa int.

233
00:10:29,030 --> 00:10:33,600
Se tulee kutsua hash, ja se on
aio hyväksyä väitettä

234
00:10:33,600 --> 00:10:38,920
string, tai voimme olla oikeampi nyt
ja sanoa char *, me kutsumme sitä s.

235
00:10:38,920 --> 00:10:43,840
Ja sitten kaikki tämä toiminto on tekemistä,
lopulta on palauttaa int.

236
00:10:43,840 --> 00:10:45,990
Nyt, miten se, että saattaisi
ei ole niin selvä.

237
00:10:45,990 --> 00:10:49,510
Aion toteuttaa tätä ilman
muodossa virheentarkistusta juuri nyt.

238
00:10:49,510 --> 00:10:55,740
Olen juuri menossa sokeasti sanoa, palauta
mitä on s kiinnike 0, miinus,

239
00:10:55,740 --> 00:10:58,850
sanotaanko, pääoman puolipiste.

240
00:10:58,850 --> 00:10:59,960
>> Täysin rikki.

241
00:10:59,960 --> 00:11:02,620
Se ei ole täydellinen, koska
yksi, mitä jos s on nolla?

242
00:11:02,620 --> 00:11:04,000
Pahoja asioita tapahtuu.

243
00:11:04,000 --> 00:11:07,940
Kaksi, mitä jos ensimmäinen kirjain tässä
nimi ei ole kirjain?

244
00:11:07,940 --> 00:11:09,860
Se ei tule kääntää
ulos hyvin joko.

245
00:11:09,860 --> 00:11:11,970
Se voi olla pieni kirjain
tai kirjeen ollenkaan.

246
00:11:11,970 --> 00:11:15,520
Joten täysin parantamisen varaa,
mutta tämä on perusajatus.

247
00:11:15,520 --> 00:11:19,010
>> Mitä me kuvattu viime viikolla sanallisesti
vain kartoituksesta Alice

248
00:11:19,010 --> 00:11:23,360
0 ja Bob 1 voidaan ilmaista
varmasti enemmän formulaically kuin C

249
00:11:23,360 --> 00:11:24,320
toimi täällä.

250
00:11:24,320 --> 00:11:28,630
Kutsutaan uudelleen hash, vie merkkijonon
tulo, ja sitten jotenkin tekee jotain

251
00:11:28,630 --> 00:11:31,020
kanssa tulo tuottaa tuotoksen.

252
00:11:31,020 --> 00:11:34,130
Ei toisin kuin meidän musta laatikko kuvaus
että olemme pitkään tehneet.

253
00:11:34,130 --> 00:11:36,550
En tiedä, miten tämä voisi olla
työskentelevät alla huppu.

254
00:11:36,550 --> 00:11:40,120
>> Jos ongelma asettaa 6, yksi haasteista
on sinun päättää, mitä

255
00:11:40,120 --> 00:11:41,920
tulee teidän hajautusfunktio olla?

256
00:11:41,920 --> 00:11:45,760
Mikä tulee olemaan sisällä että musta
ruutuun, ja oletettavasti se tulee olemaan

257
00:11:45,760 --> 00:11:50,380
hieman mielenkiintoisemman kuin tämä, ja
varmasti enemmän virhealtista

258
00:11:50,380 --> 00:11:53,180
tarkkailun kuin tässä
täytäntöönpanoa.

259
00:11:53,180 --> 00:11:54,580
>> Mutta ongelmia voi syntyä, eikö?

260
00:11:54,580 --> 00:11:57,760
Jos meillä on tietorakenne kuten tämän
yksi, mikä on yksi ongelmista

261
00:11:57,760 --> 00:12:01,600
voit törmätä ajan, kun asetat
enemmän ja enemmän nimiä

262
00:12:01,600 --> 00:12:02,880
tiiviste?

263
00:12:02,880 --> 00:12:04,630
Saat törmäykset, eikö?

264
00:12:04,630 --> 00:12:07,560
Mitä jos sinulla on Alice ja Aaron,
kaksi ihmistä, joiden nimet tapahtui

265
00:12:07,560 --> 00:12:08,190
aloittaa?

266
00:12:08,190 --> 00:12:11,660
Tässä herääkin kysymys, missä
laita toinen tällainen nimi?

267
00:12:11,660 --> 00:12:15,050
>> No, ehkä naiivisti laittaa sen
jossa Bob kuuluu, mutta sitten Bob on

268
00:12:15,050 --> 00:12:17,300
Tällainen ruuvattu jos yrität
lisätä hänen nimensä vieressä ja

269
00:12:17,300 --> 00:12:18,240
Ei ole tilaa hänelle.

270
00:12:18,240 --> 00:12:21,400
Joten voit saattaa Bob missä Charlie on,
ja voitte kuvitella tämän hyvin nopeasti

271
00:12:21,400 --> 00:12:23,020
hajauttaa osaksi hieman sekaisin.

272
00:12:23,020 --> 00:12:25,600
Jotain lineaarinen lopussa, jossa
täytyy vain etsiä koko juttu

273
00:12:25,600 --> 00:12:28,190
etsivät Alice tai Bob
tai Aaron tai Charlie.

274
00:12:28,190 --> 00:12:33,230
>> Joten sen sijaan ehdotimme, eikä vain
lineaarisesti luotaa aukiot

275
00:12:33,230 --> 00:12:36,450
ja plopping nimet siellä, me
ehdotti harrastaja lähestymistapaa.

276
00:12:36,450 --> 00:12:41,740
Tiiviste toteutettu silti
joukko indeksejä, mutta tietotyyppi

277
00:12:41,740 --> 00:12:44,500
nämä indeksit olivat nyt viitteitä.

278
00:12:44,500 --> 00:12:47,360
Viitteitä mitä?

279
00:12:47,360 --> 00:12:48,730
Osoittimet liittyvät luettelot.

280
00:12:48,730 --> 00:12:53,330
>> Koska muistaa, että linkitetty lista on
oikeastaan ​​vain osoitin solmuun, ja

281
00:12:53,330 --> 00:12:57,110
solmu on seuraavaan kenttään, ja että solmu
on seuraava kenttä, ja niin edelleen.

282
00:12:57,110 --> 00:13:00,690
Joten nyt voit ajatella tätä array
vasemmalla puolella hash-taulukon

283
00:13:00,690 --> 00:13:01,820
mikä linkitetty lista.

284
00:13:01,820 --> 00:13:07,000
Etuna on, jos saat
yhteentörmäys Alice ja Aaron,

285
00:13:07,000 --> 00:13:09,300
mitä te teette
Toinen tällainen henkilö?

286
00:13:09,300 --> 00:13:14,150
Sinä vain liittää hänet
loppuun, tai jopa alussa

287
00:13:14,150 --> 00:13:15,490
Tämän linkitetty lista.

288
00:13:15,490 --> 00:13:17,340
>> Ja oikeastaan ​​haluan vain nuudeli kautta
että vain toinen.

289
00:13:17,340 --> 00:13:18,640
Jos olisi mielekästä?

290
00:13:18,640 --> 00:13:22,060
Jos asetan Alice ja hän päätyy
ensimmäinen paikka, sitten yritän

291
00:13:22,060 --> 00:13:25,310
aseta Aaronin nimi, ja siellä on
ilmeisesti törmäyksen, minun pitäisi laittaa

292
00:13:25,310 --> 00:13:27,400
hänelle alussa
on linkitetty lista?

293
00:13:27,400 --> 00:13:30,944
Se on, että ensimmäinen paikka,
tai lopussa?

294
00:13:30,944 --> 00:13:31,440
>> Yleisö: [kuultavissa].

295
00:13:31,440 --> 00:13:31,990
>> DAVID MALAN: OK.

296
00:13:31,990 --> 00:13:32,490
Kuulin alussa.

297
00:13:32,490 --> 00:13:33,903
Miksi alussa?

298
00:13:33,903 --> 00:13:34,750
>> Yleisö: [kuultavissa].

299
00:13:34,750 --> 00:13:34,940
>> DAVID MALAN: OK.

300
00:13:34,940 --> 00:13:36,520
Se on aakkosjärjestyksessä, joten on mukavaa.

301
00:13:36,520 --> 00:13:37,330
Se on hyvä ominaisuus.

302
00:13:37,330 --> 00:13:39,335
Se säästää minulle aikaa mahdollisesti.

303
00:13:39,335 --> 00:13:43,290
Se ei anna minun tehdä binäärihaku, mutta
voisi ainakin voi puhjeta

304
00:13:43,290 --> 00:13:47,340
loop-jos ymmärrän hyvin, olen niin
aiemmin olivat Aaron olisi tässä

305
00:13:47,340 --> 00:13:48,310
lajiteltu linkitetty lista.

306
00:13:48,310 --> 00:13:50,360
Minulla ei tarvitse tuhlata aikaa etsimässä
aina loppuun.

307
00:13:50,360 --> 00:13:51,530
Niin, että on kohtuullista.

308
00:13:51,530 --> 00:13:54,710
Miksi muuten ehkä haluat lisätä
törmäävän nimi on

309
00:13:54,710 --> 00:13:56,660
listan alkuun?

310
00:13:56,660 --> 00:13:57,397
Mikä tuo on?

311
00:13:57,397 --> 00:13:58,680
>> Yleisö: [kuultavissa].

312
00:13:58,680 --> 00:14:00,820
>> DAVID MALAN: Se voi kestää kauan
päästä listan loppuun.

313
00:14:00,820 --> 00:14:02,490
Ja itse asiassa, pidempään.

314
00:14:02,490 --> 00:14:04,920
Enemmän nimiä asetat, että
aloittaa, mitä kauemmin

315
00:14:04,920 --> 00:14:06,280
ketju on menossa.

316
00:14:06,280 --> 00:14:07,890
Enää, että linkitetty
lista on menossa.

317
00:14:07,890 --> 00:14:09,420
Joten olet todella vain
tuhlaa aikaa.

318
00:14:09,420 --> 00:14:14,070
Ehkä olet parempi säilyttää
jatkuva asetettiin paikoilleen, iso O 1,

319
00:14:14,070 --> 00:14:18,470
olemalla aina laittamalla törmätä nimitys
alussa linkitetty lista,

320
00:14:18,470 --> 00:14:21,230
eikä huolestuttava niin paljon
lajitteluun.

321
00:14:21,230 --> 00:14:22,600
>> Mikä on paras vastaus?

322
00:14:22,600 --> 00:14:23,320
On epäselvää.

323
00:14:23,320 --> 00:14:26,140
Se ikään kuin riippuu siitä, mitä
jakelu on, mikä malli on

324
00:14:26,140 --> 00:14:27,850
nimet asetat.

325
00:14:27,850 --> 00:14:29,430
Se ei ole välttämättä
ilmeinen vastaus.

326
00:14:29,430 --> 00:14:33,100
Mutta täällä on taas
suunnittelu tilaisuus.

327
00:14:33,100 --> 00:14:37,220
>> Niin me sitten katsoin tämä asia, joka
on todella toinen suuri mahdollisuus

328
00:14:37,220 --> 00:14:38,180
p-set 6.

329
00:14:38,180 --> 00:14:41,770
Ja ymmärtää, jos et ole jo,
Zamyla sukeltaa molempia, hash

330
00:14:41,770 --> 00:14:43,260
taulukoita ja yrittää, yksityiskohtaisemmin.

331
00:14:43,260 --> 00:14:45,630
Ja videoesityksen on
upotettu p-set spec.

332
00:14:45,630 --> 00:14:46,590
Tämä oli trie -

333
00:14:46,590 --> 00:14:51,670
T-R-I-E. Ja mikä oli mielenkiintoista
Tämä oli se, että ajoaika

334
00:14:51,670 --> 00:14:59,510
etsivät nimi, kuten Maxwell
viime kerralla, oli iso O mitä?

335
00:14:59,510 --> 00:15:01,040
Mikä tuo on?

336
00:15:01,040 --> 00:15:01,920
>> Yleisö: määrä kirjaimia.

337
00:15:01,920 --> 00:15:02,550
>> DAVID MALAN: Numero kirjeitä.

338
00:15:02,550 --> 00:15:03,210
Kuulin kaksi asiaa.

339
00:15:03,210 --> 00:15:04,630
Useita kirjeitä ja jatkuva ajan.

340
00:15:04,630 --> 00:15:05,540
Joten mennä, että ensin.

341
00:15:05,540 --> 00:15:06,410
Määrä kirjaimia.

342
00:15:06,410 --> 00:15:10,195
No, tämä tietorakenne, muistaa, on
kuten puu, sukupuu, kukin

343
00:15:10,195 --> 00:15:12,860
jonka solmut koostuvat ryhmät.

344
00:15:12,860 --> 00:15:16,300
Ja ne paneelit ovat osoittimia
muita tällaisia ​​solmuja, tai muita sellaisia

345
00:15:16,300 --> 00:15:17,670
taulukot puu.

346
00:15:17,670 --> 00:15:22,890
>> Joten jos halusimme sitten määrittää
onko Maxwell on täällä, voisin mennä

347
00:15:22,890 --> 00:15:26,890
ensimmäiseen array, aivan huipulla
puu, niin sanottu juuri, alkuun

348
00:15:26,890 --> 00:15:30,521
trie ja noudata m osoitin,
Sitten osoitin, niin x,

349
00:15:30,521 --> 00:15:31,710
w, e, l, l.

350
00:15:31,710 --> 00:15:34,910
Ja sitten kun näen joitakin erikoismerkkejä,
merkitään täällä kolmio.

351
00:15:34,910 --> 00:15:38,480
Koodin näet ehdotamme, että
toteutetaan bool, vain sanomalla kyllä

352
00:15:38,480 --> 00:15:40,540
tai no, sana loppuu tähän.

353
00:15:40,540 --> 00:15:45,270
>> No, kun olemme menneet M--X-W-E-L-L,
tuntuu seitsemän, ehkä

354
00:15:45,270 --> 00:15:48,910
kahdeksan jos menemme ohi, kahdeksan
ohjeita löytää Maxwell.

355
00:15:48,910 --> 00:15:53,050
Tai kutsutaan sitä K. Mutta muistaa viimeksi
aikaa, totesin, että jos siellä

356
00:15:53,050 --> 00:15:57,540
realistisesti maksimipituus on
sana, kuten 40-joitakin-kummallisia merkkejä,

357
00:15:57,540 --> 00:16:00,810
enimmäispituus merkitsee
vakioarvo.

358
00:16:00,810 --> 00:16:05,770
Siis todella, kyllä, se on teknisesti iso O
8 tai 7, tai oikeastaan ​​iso O K. Mutta

359
00:16:05,770 --> 00:16:09,420
jos on rajallinen korkki mitä
K voisi olla, se on vakio.

360
00:16:09,420 --> 00:16:12,080
Ja niin se on iso O 1 at
päivän päätteeksi.

361
00:16:12,080 --> 00:16:13,040
>> Ei todellisessa maailmassa.

362
00:16:13,040 --> 00:16:15,960
Ei kun todella alkaa katsella
kellon kuin ohjelman käynnissä.

363
00:16:15,960 --> 00:16:20,690
Se ehdottomasti olemaan hieman
hitaammin kuin todella jatkuvasti

364
00:16:20,690 --> 00:16:21,840
aikaa yksi askel.

365
00:16:21,840 --> 00:16:25,540
Se tulee olemaan seitsemän tai kahdeksan vaihetta,
mutta silti se on paljon, paljon parempi

366
00:16:25,540 --> 00:16:30,080
kuin algoritmi iso O n että
riippuu koosta mitä on

367
00:16:30,080 --> 00:16:31,220
tietorakenne.

368
00:16:31,220 --> 00:16:34,970
>> Huomaa ylösalaisin tässä voimme lisätä
euroa enemmän nimiä tähän

369
00:16:34,970 --> 00:16:38,170
tietorakenne, mutta kuinka paljon enemmän vaiheita
se aikoo viedä meidät löytää

370
00:16:38,170 --> 00:16:40,480
Maxwell tässä tapauksessa?

371
00:16:40,480 --> 00:16:40,780
Ei mitään.

372
00:16:40,780 --> 00:16:41,820
Hän on ennallaan.

373
00:16:41,820 --> 00:16:45,480
Ja tähän mennessä, en usko, olemme nähneet
Esimerkkinä tietojen rakenteen tai

374
00:16:45,480 --> 00:16:48,560
algoritmi, joka oli täysin
vaikuta ulkoiset

375
00:16:48,560 --> 00:16:50,040
käyttäytymistä niin.

376
00:16:50,040 --> 00:16:51,160
Mutta tämä ei voi olla hämmästyttävä.

377
00:16:51,160 --> 00:16:52,900
Tämä ei voi olla ainoa ratkaisu
ja p-set

378
00:16:52,900 --> 00:16:53,570
>> Ja se ei ole.

379
00:16:53,570 --> 00:16:55,980
Tämä ei välttämättä ole tietoa
rakenne pitäisi kallistua,

380
00:16:55,980 --> 00:16:58,220
koska kuten hash taulukoita, kompromissi.

381
00:16:58,220 --> 00:17:00,500
Mikä on hinta maksat täällä?

382
00:17:00,500 --> 00:17:00,940
Muisti.

383
00:17:00,940 --> 00:17:02,890
Tarkoitan, tämä on kamalaa
muistin määrä.

384
00:17:02,890 --> 00:17:05,569
Ja et oikein näe sitä täällä, koska
Kirjailija tämän kuvan

385
00:17:05,569 --> 00:17:09,420
ilmeisesti katkaistu kaikki paneelit
ja emme näe paljon n ja

386
00:17:09,420 --> 00:17:12,700
B: n ja C: n ja Q: n ja Y: n
ja Z: n näissä ryhmät.

387
00:17:12,700 --> 00:17:13,630
Mutta ne ovat siellä.

388
00:17:13,630 --> 00:17:17,660
>> Jokainen näistä solmuista on koko joukko
on noin 26 tavua tai useampia tavuja, ja jokainen

389
00:17:17,660 --> 00:17:19,170
mikä kirjain.

390
00:17:19,170 --> 00:17:22,920
27 meidän tapauksessamme, jotta voimme tukea
heittomerkit ongelma set.

391
00:17:22,920 --> 00:17:27,030
Joten tämä tieto rakenne on todella,
todella tiheä ja leveä.

392
00:17:27,030 --> 00:17:30,880
Ja että yksin päätyä hidastaa
asioita alas, tai ainakin maksaa sinulle

393
00:17:30,880 --> 00:17:32,240
paljon enemmän tilaa.

394
00:17:32,240 --> 00:17:34,020
Mutta jälleen kerran, voimme tehdä
vertailuja tässä.

395
00:17:34,020 --> 00:17:39,190
>> Recall taas takaisin, olemme saavuttaneet paljon
jännittävämpää käyntiaika lajittelu

396
00:17:39,190 --> 00:17:42,880
kun käytämme yhdistäminen tavallaan, mutta hinta
maksoimme saavuttaa n log n ja yhdistäminen

397
00:17:42,880 --> 00:17:46,930
sort vaaditaan, että käytämme
enemmän mitä resursseja?

398
00:17:46,930 --> 00:17:47,690
Enemmän tilaa.

399
00:17:47,690 --> 00:17:50,530
Tarvitsimme toisen array
kopioida ihmisiä, aivan kuten

400
00:17:50,530 --> 00:17:51,620
teimme täällä lavalla.

401
00:17:51,620 --> 00:17:55,880
Joten jälleen, ei ole selvää voittajaa,
mutta vain subjektiivinen suunnittelu

402
00:17:55,880 --> 00:17:57,710
päätökset tehdään.

403
00:17:57,710 --> 00:17:58,060
>> Selvä.

404
00:17:58,060 --> 00:17:59,130
Joten miten tästä?

405
00:17:59,130 --> 00:18:02,050
Jokainen tunnistaa mikä D-Hall?

406
00:18:02,050 --> 00:18:02,440
OK.

407
00:18:02,440 --> 00:18:03,170
Joten me kolme tehdä.

408
00:18:03,170 --> 00:18:03,750
Mather House.

409
00:18:03,750 --> 00:18:05,070
Tässä siis Mather ruokasalissa.

410
00:18:05,070 --> 00:18:09,650
Lyön vetoa, kaikki ruokasalia on
pinot tarjottimia näin.

411
00:18:09,650 --> 00:18:11,950
Ja tämä on todella edustava
jotain olemme

412
00:18:11,950 --> 00:18:13,050
ilmeisesti nähnyt jo.

413
00:18:13,050 --> 00:18:14,850
Kutsuimme sitä kirjaimellisesti pino.

414
00:18:14,850 --> 00:18:18,970
Ja pino, mitä teidän
tietokoneen muistiin, on, jos data menee

415
00:18:18,970 --> 00:18:20,460
kun toimintoja on kutsuttu.

416
00:18:20,460 --> 00:18:23,410
>> Esimerkiksi millaisia ​​asiat menevät
pinoon nähden

417
00:18:23,410 --> 00:18:27,420
Muistin sijoittelu olemme keskustelleet
viikkoina aikaisemmin?

418
00:18:27,420 --> 00:18:28,736
Mikä tuo on?

419
00:18:28,736 --> 00:18:29,670
>> Yleisö: Puhelut toimintoja.

420
00:18:29,670 --> 00:18:30,260
>> DAVID MALAN: Olen pahoillani.

421
00:18:30,260 --> 00:18:31,210
>> Yleisö: Puhelut toimintoja.

422
00:18:31,210 --> 00:18:33,590
>> DAVID MALAN: Puhelut toimintoja, mutta
nimenomaan, mitä sisällä kunkin

423
00:18:33,590 --> 00:18:35,340
näitä kehyksiä?

424
00:18:35,340 --> 00:18:37,220
Millaiset asiat?

425
00:18:37,220 --> 00:18:37,460
Joo.

426
00:18:37,460 --> 00:18:38,500
Niin paikallisia muuttujia.

427
00:18:38,500 --> 00:18:43,080
Aina kun tarvitaan joitakin paikallisia varastointi,
kuten väite, tai int I, tai int

428
00:18:43,080 --> 00:18:45,940
temp, tai mitä tahansa paikallisen
muuttuja, olemme olleet

429
00:18:45,940 --> 00:18:47,210
laskemisesta, että pinoon.

430
00:18:47,210 --> 00:18:49,610
Ja me kutsumme sitä pino, koska
Tämän kerrospukeutuminen idea.

431
00:18:49,610 --> 00:18:52,940
Juuri sellainen otteluita jopa todellisuuden kanssa,
käsite viipymättä.

432
00:18:52,940 --> 00:18:56,650
>> Mutta näyttää siltä, ​​että pino voi myös
pidettävä tietorakenne,

433
00:18:56,650 --> 00:19:00,110
vaihtoehto array, vaihtoehtoisen
on linkitetty lista.

434
00:19:00,110 --> 00:19:02,770
Jotain käsitteellisesti mielenkiintoisempaa
, joka voi vielä olla

435
00:19:02,770 --> 00:19:06,030
toteutetaan käyttäen joko näiden
asioita, mutta se on eri tyyppistä

436
00:19:06,030 --> 00:19:09,140
tietorakenne tukevat, todella,
vain kaksi operaatiota.

437
00:19:09,140 --> 00:19:11,000
Mutta voit lisätä harrastaja
ominaisuuksia kuin nämä.

438
00:19:11,000 --> 00:19:12,180
Mutta nämä ovat perusasiat -

439
00:19:12,180 --> 00:19:13,510
push ja pop.

440
00:19:13,510 --> 00:19:19,240
>> Ja idea pino on, että jos minä
täällä, tai ilman Annenberg

441
00:19:19,240 --> 00:19:22,880
tietäen, lokero vieressä
jossa numero 9 sitä.

442
00:19:22,880 --> 00:19:23,870
Joten int.

443
00:19:23,870 --> 00:19:26,990
Ja haluan ajaa tämän päälle tiedot
rakenne, joka tällä hetkellä on tyhjä.

444
00:19:26,990 --> 00:19:28,790
Mieti tätä pinon pohjalle.

445
00:19:28,790 --> 00:19:33,150
Haluaisin ajaa tämän numeron 9 päälle
pino, ja nyt se on tuolla.

446
00:19:33,150 --> 00:19:36,040
>> Mutta mielenkiintoinen asia pino
on, että jos en nyt halua työntää

447
00:19:36,040 --> 00:19:40,210
jokin muu arvo, kuten 17, ja painan
Tämän pinoon, aion tehdä

448
00:19:40,210 --> 00:19:43,290
vain intuitiivinen asia, olen juuri menossa
laittaa ne juuri siinä missä me ihmiset

449
00:19:43,290 --> 00:19:45,180
olisivat taipuvaisia ​​laittaa sen, päälle.

450
00:19:45,180 --> 00:19:48,850
Mutta mitä nyt mielenkiintoinen
on, miten saan klo 9?

451
00:19:48,850 --> 00:19:50,670
Tiedäthän, en ilman jonkin verran vaivaa.

452
00:19:50,670 --> 00:19:54,070
>> Niin mitä mielenkiintoista
pino on, että suunnittelu,

453
00:19:54,070 --> 00:19:56,330
se LIFO tietorakenne.

454
00:19:56,330 --> 00:19:59,680
Typerä tapa kuvata
last in, first out.

455
00:19:59,680 --> 00:20:03,280
Joten viimeinen numero
tällä kertaa oli 17.

456
00:20:03,280 --> 00:20:07,540
Joten jos haluan pop jotain pois
pinon, se voi olla vain 17.

457
00:20:07,540 --> 00:20:11,890
Joten on pakollista järjestyksessä
toimintaa täällä, missä viimeinen kohde

458
00:20:11,890 --> 00:20:14,260
siihen on oltava ensimmäinen ulos.

459
00:20:14,260 --> 00:20:16,440
Näin lyhenne, LIFO.

460
00:20:16,440 --> 00:20:19,160
>> Joten miksi tämä voisi olla hyödyllistä?

461
00:20:19,160 --> 00:20:22,690
Ovatko ne puitteet, joissa olisit
haluavat tietorakenne näin?

462
00:20:22,690 --> 00:20:24,810
No, se on varmasti ollut hyötyä
sisällä tietokoneen.

463
00:20:24,810 --> 00:20:29,050
Joten käyttöjärjestelmien selvästi käyttää tätä
Tällainen tietorakenne pinot.

464
00:20:29,050 --> 00:20:32,800
Otamme myös nähdä sama ajatus
kun se tulee web-sivuja.

465
00:20:32,800 --> 00:20:35,890
Joten tällä viikolla ja ensi viikolla ja sen jälkeen,
ja kun alkaa toteuttaa web

466
00:20:35,890 --> 00:20:39,490
sivut kieltä kutsutaan HTML, voit
itse käyttää tietorakenne kuten

467
00:20:39,490 --> 00:20:42,690
Tämä määrittää, onko sivu
on oikein muotoiltu.

468
00:20:42,690 --> 00:20:47,170
Koska näemme kaikki sivut noudattavat
eräänlainen hierarkia, syvennys

469
00:20:47,170 --> 00:20:52,030
joka, lopussa päivä, olla
puurakenne alla huppu.

470
00:20:52,030 --> 00:20:53,620
Joten lisää, että vain vähän.

471
00:20:53,620 --> 00:20:56,560
>> Mutta nyt, nyt ehdottaa
hetkellä, miten voisimme edetä

472
00:20:56,560 --> 00:20:58,830
eli mitä pino on?

473
00:20:58,830 --> 00:21:03,370
Saanen ehdottaa, että toteutamme
pino koodilla näin.

474
00:21:03,370 --> 00:21:07,990
Joten pino tulee olemaan sen sisällä
kaksi asiaa, array, nimeltään tarjottimia,

475
00:21:07,990 --> 00:21:09,510
vain oltava demo.

476
00:21:09,510 --> 00:21:12,660
Ja jokainen kohteita, että joukko
tulee olemaan tyyppiä int.

477
00:21:12,660 --> 00:21:14,740
Ja kapasiteetti on oletettavasti mitä?

478
00:21:14,740 --> 00:21:18,796
Koska en ole kirjoittanut
koko määritelmä täällä.

479
00:21:18,796 --> 00:21:21,535
>> Se on luultavasti suurin
koko joukko.

480
00:21:21,535 --> 00:21:25,150
Ja se on luultavasti ilmoitettu terävä
määritellä tiedoston alkuun, jotkut

481
00:21:25,150 --> 00:21:28,450
Tällainen jatkuva kuten ehdotetun
pelkkä arvo.

482
00:21:28,450 --> 00:21:32,250
Joten jonnekin kapasiteetti määritellään
kuin suurin mahdollinen koko.

483
00:21:32,250 --> 00:21:35,590
Samaan aikaan, sisällä tietorakenteen
tunnetaan pino siellä tulee

484
00:21:35,590 --> 00:21:38,630
olla kokonaisluku vain tiedossa
yksinkertaisesti koko.

485
00:21:38,630 --> 00:21:43,400
>> Joten jos olisin edustamaan tätä nyt
kuvallisesti Oletetaan, että tämä

486
00:21:43,400 --> 00:21:48,070
koko musta laatikko edustaa minun pino.

487
00:21:48,070 --> 00:21:50,070
Sisältä se on kaksi muuttujaa.

488
00:21:50,070 --> 00:21:54,780
Joten aion tehdä
Ensimmäinen kuin koko.

489
00:21:54,780 --> 00:21:57,420
Ja toinen aion
piirtää taulukkona.

490
00:21:57,420 --> 00:22:01,060
>> Mutta vain pitää asiat hallittu,
normaalisti Haluaisin kiinnittää array kuten

491
00:22:01,060 --> 00:22:04,910
, mutta se on tavallaan mukavaa
jos vastaa todellisuutta, tai

492
00:22:04,910 --> 00:22:06,230
ottelu mielikuvaan.

493
00:22:06,230 --> 00:22:12,880
Joten haluan sen sijaan kiinnittää array
pystysuunnassa, joka on vain, jälleen,

494
00:22:12,880 --> 00:22:13,840
taiteilijan luovuttamista.

495
00:22:13,840 --> 00:22:16,610
Ei ole oikeastaan ​​väliä, mitä se
on alla huppu.

496
00:22:16,610 --> 00:22:20,350
Ja me sanomme, että oletuksena,
kapasiteetti tulee olemaan kolme.

497
00:22:20,350 --> 00:22:23,480
Joten tämä on paikka 0, tämä
on paikalla 1, tämä

498
00:22:23,480 --> 00:22:25,740
on paikka 2.

499
00:22:25,740 --> 00:22:29,330
>> Jos minä lahjoa kanssa stressipallo, olisi
joku haluaa tulla ja ajaa

500
00:22:29,330 --> 00:22:30,870
aluksella tässä vain hetken?

501
00:22:30,870 --> 00:22:31,960
OK, näki kätesi ensin.

502
00:22:31,960 --> 00:22:33,950
Tule ylös.

503
00:22:33,950 --> 00:22:36,500
Selvä.

504
00:22:36,500 --> 00:22:38,760
Joten mielestäni on Steven.

505
00:22:38,760 --> 00:22:40,035
Tule ylös.

506
00:22:40,035 --> 00:22:40,770
Selvä.

507
00:22:40,770 --> 00:22:46,760
>> Mutta oletetaan nyt kelaa alkuperäisen
maailman tilasta, jossa I

508
00:22:46,760 --> 00:22:52,180
juuri ilmoittanut pino, ja se on
olemaan kapasiteetin kolme.

509
00:22:52,180 --> 00:22:54,470
Mutta koko ei ole vielä määritelty.

510
00:22:54,470 --> 00:22:56,100
Alustat ei ole vielä määritelty.

511
00:22:56,100 --> 00:22:57,300
Joten pari kysymystä ensin.

512
00:22:57,300 --> 00:23:01,310
Ja minä annan sinulle mikrofoni, joten voit
osallistumme aktiivisemmin tässä.

513
00:23:01,310 --> 00:23:05,190
>> Joten mitä on sisällä koko tällä hetkellä
ajoissa, jos kaikki olen tehnyt on

514
00:23:05,190 --> 00:23:09,340
julisti pino
yhtä riviä koodia?

515
00:23:09,340 --> 00:23:10,100
>> STEVEN: Ei paljon.

516
00:23:10,100 --> 00:23:12,080
>> DAVID MALAN: OK, ei paljon.

517
00:23:12,080 --> 00:23:14,410
Tiedämmekö mitä sisällä koko,
tiedämme mitä sisällä

518
00:23:14,410 --> 00:23:16,330
Tämän array täällä?

519
00:23:16,330 --> 00:23:18,630
>> STEVEN: Vain satunnainen koodi, eikö?

520
00:23:18,630 --> 00:23:20,220
Just -

521
00:23:20,220 --> 00:23:23,230
>> DAVID MALAN: Joo, aion
kutsuvat sitä koodia, mutta satunnainen -

522
00:23:23,230 --> 00:23:23,820
>> STEVEN: Things.

523
00:23:23,820 --> 00:23:28,290
>> DAVID MALAN: Asiat kuten random

524
00:23:28,290 --> 00:23:28,870
>> Steven: Bits.

525
00:23:28,870 --> 00:23:29,530
>> DAVID MALAN: Bits, eikö?

526
00:23:29,530 --> 00:23:31,190
Joten roskat arvot, eikö?

527
00:23:31,190 --> 00:23:33,470
Joten permutaatiot 0: n ja 1.

528
00:23:33,470 --> 00:23:35,920
Jäänteitä edellisen käyttötarkoituksissa
Tämän muistin.

529
00:23:35,920 --> 00:23:38,150
Ja emme todellakaan tiedä, mitä arvoja
ovat, niin me yleensä tehdä niitä

530
00:23:38,150 --> 00:23:38,930
kysymysmerkkejä.

531
00:23:38,930 --> 00:23:41,990
>> Joten ensimmäinen asia, olemme oletettavasti
menossa haluavat tehdä täällä -

532
00:23:41,990 --> 00:23:46,630
ja haluan antaa tämän alan sisällä
siellä nimi - tarjottimia.

533
00:23:46,630 --> 00:23:49,540
Mitä meidän pitäisi luultavasti alustaa
kokoa, jos haluamme

534
00:23:49,540 --> 00:23:51,040
aloitat pino?

535
00:23:51,040 --> 00:23:53,070
>> STEVEN: Alusta on osa 3.

536
00:23:53,070 --> 00:23:53,910
>> DAVID MALAN: Niin, OK.

537
00:23:53,910 --> 00:23:56,710
Olla selkeä, kapasiteetti on julistettu
muualla kuin kolme.

538
00:23:56,710 --> 00:23:58,570
Ja se mitä olen käyttänyt
jakaa array.

539
00:23:58,570 --> 00:24:03,535
Koko aikoo viitata kuinka monta
lokerot ovat tällä hetkellä pino.

540
00:24:03,535 --> 00:24:03,880
>> STEVEN: Zero.

541
00:24:03,880 --> 00:24:04,460
>> DAVID MALAN: Niin sen pitäisi olla nolla.

542
00:24:04,460 --> 00:24:07,760
Joten mene eteenpäin, ja kaikki sormella,
piirtää nolla kokoisia.

543
00:24:07,760 --> 00:24:08,440
Selvä.

544
00:24:08,440 --> 00:24:10,920
Joten nyt, mitä sisällä tämän
täällä, emme tiedä.

545
00:24:10,920 --> 00:24:12,160
Nämä ovat oikeastaan ​​vain roskaa arvot.

546
00:24:12,160 --> 00:24:14,800
Jotta voisimme tehdä kysymysmerkkejä, mutta
Pidetään hallituksen puhtaana nyt

547
00:24:14,800 --> 00:24:16,300
koska se ei ole väliä
mitä siellä.

548
00:24:16,300 --> 00:24:19,130
Meidän ei tarvitse alustaa array
mitään, sillä jos me tiedämme

549
00:24:19,130 --> 00:24:23,100
pinon koon on nolla, no, me
ei pitäisi tarkastella mitään

550
00:24:23,100 --> 00:24:25,590
Tämän array muutenkin at
tässä vaiheessa.

551
00:24:25,590 --> 00:24:29,970
>> Joten nyt olettaa, että painan
numero 9 pinoon.

552
00:24:29,970 --> 00:24:33,750
Miten meidän pitäisi päivittää tietorakenne
sisällä tämä musta laatikko?

553
00:24:33,750 --> 00:24:35,540
Mitä arvoja täytyy muuttaa?

554
00:24:35,540 --> 00:24:36,200
>> STEVEN: Within -

555
00:24:36,200 --> 00:24:37,400
koko?

556
00:24:37,400 --> 00:24:37,650
>> DAVID MALAN: OK.

557
00:24:37,650 --> 00:24:38,770
Koko pitäisi tulla mitä?

558
00:24:38,770 --> 00:24:39,580
>> STEVEN: Koko olisi yksi.

559
00:24:39,580 --> 00:24:39,870
>> DAVID MALAN: OK.

560
00:24:39,870 --> 00:24:41,110
Joten koko tulisi olla yksi.

561
00:24:41,110 --> 00:24:42,540
Joten voit tehdä tämän pari tapaa.

562
00:24:42,540 --> 00:24:46,920
Annan teille nyt oman
sormi on pyyhekumi.

563
00:24:46,920 --> 00:24:47,260
Selvä.

564
00:24:47,260 --> 00:24:49,960
Niin nyt sormi on harjalla.

565
00:24:49,960 --> 00:24:50,330
Selvä.

566
00:24:50,330 --> 00:24:52,820
Ja nyt, mitä muuta on muututtava,
On selvää, että tietojen rakenne?

567
00:24:52,820 --> 00:24:57,060
>> STEVEN: Menemme alkaen
alhaalta ylöspäin 9.

568
00:24:57,060 --> 00:24:57,760
>> DAVID MALAN: 9.

569
00:24:57,760 --> 00:24:58,420
OK, hyvä.

570
00:24:58,420 --> 00:25:01,550
Niin silti ei ole väliä mitä on
sijainti yksi tai kaksi, koska he

571
00:25:01,550 --> 00:25:04,520
roskat arvot, mutta meidän ei pitäisi vaivata
näköinen siellä, koska koko on

572
00:25:04,520 --> 00:25:07,540
kertovat meille, että vain ensimmäinen tekijä
on todella oikeutettua.

573
00:25:07,540 --> 00:25:10,400
Joten nyt painan 17 päälle lista.

574
00:25:10,400 --> 00:25:11,830
Mitä tapahtuu tätä kuvaa?

575
00:25:11,830 --> 00:25:14,720
>> STEVEN: Eli koko on menossa kaksi.

576
00:25:14,720 --> 00:25:15,300
>> DAVID MALAN: OK.

577
00:25:15,300 --> 00:25:16,070
Olet pyyhekumi -

578
00:25:16,070 --> 00:25:16,810
oho.

579
00:25:16,810 --> 00:25:18,026
Olet pyyhekumi.

580
00:25:18,026 --> 00:25:18,840
>> STEVEN: Eraser.

581
00:25:18,840 --> 00:25:19,720
>> DAVID MALAN: Olet harjalla.

582
00:25:19,720 --> 00:25:20,560
>> STEVEN: Brush.

583
00:25:20,560 --> 00:25:20,920
>> DAVID MALAN: OK.

584
00:25:20,920 --> 00:25:21,600
Ja mitä muuta?

585
00:25:21,600 --> 00:25:22,600
>> STEVEN: Ja sitten me -

586
00:25:22,600 --> 00:25:22,915
>> DAVID MALAN: Työnsimme 17.

587
00:25:22,915 --> 00:25:24,760
>> STEVEN: Pysymme 17 päälle, niin -

588
00:25:24,760 --> 00:25:25,710
>> DAVID MALAN: OK, hyvä.

589
00:25:25,710 --> 00:25:27,040
>> STEVEN: - pudota alas.

590
00:25:27,040 --> 00:25:27,530
>> DAVID MALAN: Okei.

591
00:25:27,530 --> 00:25:27,940
Se on tulossa helppoa.

592
00:25:27,940 --> 00:25:29,300
En aio auttaa sinua tällä kertaa.

593
00:25:29,300 --> 00:25:30,510
Push 22.

594
00:25:30,510 --> 00:25:31,720
>> STEVEN: Valmis.

595
00:25:31,720 --> 00:25:34,870
Becoming pyyhekumi.

596
00:25:34,870 --> 00:25:37,340
Olen tulossa harjalla.

597
00:25:37,340 --> 00:25:39,340
Ja sitten olen laskemisesta 22.

598
00:25:39,340 --> 00:25:40,100
>> DAVID MALAN: 22.

599
00:25:40,100 --> 00:25:40,620
Erinomainen.

600
00:25:40,620 --> 00:25:41,380
Joten vielä kerran.

601
00:25:41,380 --> 00:25:44,280
Minä lähden nyt työntää
pinoon 26.

602
00:25:44,280 --> 00:25:46,350
>> STEVEN: Ooh.

603
00:25:46,350 --> 00:25:50,278
Voi hemmetti.

604
00:25:50,278 --> 00:25:52,520
Olet todella sai minut kiinni kenet.

605
00:25:52,520 --> 00:25:53,703
>> DAVID MALAN: Et ole
näkee tällaista?

606
00:25:53,703 --> 00:25:55,930
>> Steven: En näe tätä tulossa.

607
00:25:55,930 --> 00:25:58,756
Voisimme uudelleen alkuperäisestä kapasiteetista?

608
00:25:58,756 --> 00:25:59,790
>> DAVID MALAN: Se on hyvä kysymys.

609
00:25:59,790 --> 00:26:02,360
Joten olemme sellainen maalattu itse
huoneen nurkkaan täällä.

610
00:26:02,360 --> 00:26:06,740
Ei todellakaan ole mitään hyvää ulos Steven
koska olemme myönnetty tämän taulukon

611
00:26:06,740 --> 00:26:09,130
staattisesti, niin sanotusti sisälle
tieto-rakenteesta.

612
00:26:09,130 --> 00:26:12,170
Ja olemme lähinnä kova koodattu
se on kooltaan kolme.

613
00:26:12,170 --> 00:26:14,170
Joten emme voi kohdentaa sitä.

614
00:26:14,170 --> 00:26:20,020
>> Voisimme jos menimme takaisin, me
uudelleen kaukaloiden osoitin, että

615
00:26:20,020 --> 00:26:22,300
me sitten käyttää malloc käteen muistia.

616
00:26:22,300 --> 00:26:25,050
Koska jos saimme muisti
kasaan kautta malloc, me

617
00:26:25,050 --> 00:26:26,430
voisi sitten vapauttaa sen.

618
00:26:26,430 --> 00:26:29,630
Mutta ennen vapauttaa se, voisimme
kohdentaa isompi kimpale muisti,

619
00:26:29,630 --> 00:26:31,330
päivittää osoitin, ja niin edelleen.

620
00:26:31,330 --> 00:26:33,500
Mutta nyt, tämä on todella
Parasta mitä voimme tehdä.

621
00:26:33,500 --> 00:26:36,360
Push ja pop ovat oletettavasti menossa
on viestittää jokin virhe.

622
00:26:36,360 --> 00:26:40,270
>> Niin esimerkiksi meidän täytäntöönpano
push voisi palata bool joka

623
00:26:40,270 --> 00:26:42,390
aiemmin palasi totta, totta, totta.

624
00:26:42,390 --> 00:26:48,390
Mutta neljännen kerran, se tulee olemaan
palata vääriä, esimerkiksi.

625
00:26:48,390 --> 00:26:48,540
Selvä.

626
00:26:48,540 --> 00:26:49,540
Hyvin tehty.

627
00:26:49,540 --> 00:26:50,060
Onneksi olkoon.

628
00:26:50,060 --> 00:26:52,160
Olet ansainnut stressipallo tänään.

629
00:26:52,160 --> 00:26:53,110
>> [APPLAUSE]

630
00:26:53,110 --> 00:26:54,382
>> STEVEN: Kiitos.

631
00:26:54,382 --> 00:26:55,680
>> DAVID MALAN: Kiitos.

632
00:26:55,680 --> 00:26:59,740
OK, joten tämä tuntuu olla paljon
ja askel eteenpäin, eikö?

633
00:26:59,740 --> 00:27:01,410
Me kuvataan tämän tietorakenteen.

634
00:27:01,410 --> 00:27:02,320
Se on ollut vakuuttava, eikö?

635
00:27:02,320 --> 00:27:03,200
Käyttöjärjestelmät pidä siitä.

636
00:27:03,200 --> 00:27:06,360
Ilmeisesti verkossa voi käyttää tätä,
ja muita sovelluksia edelleen.

637
00:27:06,360 --> 00:27:10,870
Mutta mitä tyhmä rajoitus, että olemme
Takaisin tavallaan viikon kahden rajan

638
00:27:10,870 --> 00:27:12,880
jossa on kiinteä koko taulukot.

639
00:27:12,880 --> 00:27:15,010
>> Joten on todellakin pari
tavalla voisimme ratkaista.

640
00:27:15,010 --> 00:27:18,750
Voisimme dynaamisesti jakaa array,
eikä kova koodaus sen olen

641
00:27:18,750 --> 00:27:22,600
täällä tehnyt, vaan uudelleen julistamisesta
Tämän vain olla selkeä, sillä

642
00:27:22,600 --> 00:27:23,830
jotain tällaista.

643
00:27:23,830 --> 00:27:29,040
Int * tarjottimia, ei päättää
tarjonnan vielä.

644
00:27:29,040 --> 00:27:35,460
Mutta kun julistaa pino muualla
minun koodi, voisin sitten soittaa malloc,

645
00:27:35,460 --> 00:27:38,250
saada osoitteen kimpale
muisti, ja voisin antaa

646
00:27:38,250 --> 00:27:39,980
että osoite tarjottimia.

647
00:27:39,980 --> 00:27:43,340
>> Ja sitten, koska se on vain kimpale
muisti, voisin edelleen käyttää neliö

648
00:27:43,340 --> 00:27:45,450
kiinnike merkintä tavalliseen tapaan.

649
00:27:45,450 --> 00:27:49,020
Koska uudelleen, siellä on tavallaan tämän
toiminnallinen vastine taulukot ja

650
00:27:49,020 --> 00:27:50,820
paloina muistia, jotka tulevat
takaisin malloc.

651
00:27:50,820 --> 00:27:53,090
Voimme kohtelevat kuin muut
käyttäen osoitin aritmeettinen tai

652
00:27:53,090 --> 00:27:54,440
hakasulkeen merkintätapa.

653
00:27:54,440 --> 00:27:55,660
Niin, että yksi lähestymistapa.

654
00:27:55,660 --> 00:28:00,120
>> Mutta miten muuten voisimme toteuttaa tämän
yhtä ja samaa rakennetta, mahdollisesti?

655
00:28:00,120 --> 00:28:00,280
Oikea?

656
00:28:00,280 --> 00:28:04,530
Tunnen me vain ratkaisi
ongelma kuin viikko sitten.

657
00:28:04,530 --> 00:28:08,860
Mikä oli ratkaisu tähän ongelmaan
että Steven törmäsi?

658
00:28:08,860 --> 00:28:10,370
Joten liittyvät luettelot, oikealle.

659
00:28:10,370 --> 00:28:13,410
>> Jos ongelma on se, että olemme maalaus
itsemme nurkkaan kohdentamalla

660
00:28:13,410 --> 00:28:17,580
etukäteen liian vähän muistia, että
sitten on jotenkin käsitellä, hyvin,

661
00:28:17,580 --> 00:28:19,880
miksi ei vain välttää
antaa kokonaan?

662
00:28:19,880 --> 00:28:26,170
Miksi ei vain julistaa kaukaloiden
osoitin solmuun, ergo linkitetty lista,

663
00:28:26,170 --> 00:28:30,740
ja sitten yksinkertaisesti jakaa uutta solmuja
joka kerta Steven tarvitaan sopivaksi

664
00:28:30,740 --> 00:28:32,400
numeron tietorakenne.

665
00:28:32,400 --> 00:28:34,200
>> Joten kuva olisi muutettava.

666
00:28:34,200 --> 00:28:38,220
Se ei tule olemaan niin puhtaita ja
yksinkertainen kuin vain joukko kolme ints.

667
00:28:38,220 --> 00:28:42,970
Nyt se tulee olemaan osoitin
struct, ja että struct on menossa

668
00:28:42,970 --> 00:28:44,830
on int ja ensi osoitin.

669
00:28:44,830 --> 00:28:47,670
Se tulee johtamaan kautta, että osoitin
toiselle tällaiselle struct on

670
00:28:47,670 --> 00:28:48,600
toinen tällainen struct.

671
00:28:48,600 --> 00:28:50,560
Joten kuva todella
saada hieman Messier.

672
00:28:50,560 --> 00:28:52,950
Ja olisimme nuolet sitominen
kaikki yhdessä.

673
00:28:52,950 --> 00:28:55,280
>> Mutta se on hieno, oikea, koska
olemme nähneet, miten tämä.

674
00:28:55,280 --> 00:28:58,180
Ja kun saat mukavan
täytäntöön jotain linkitetyn

675
00:28:58,180 --> 00:29:01,450
lista, joka sinun täytyy tehdä, jos
päättää panna hash taulukon

676
00:29:01,450 --> 00:29:05,120
erillinen ketjutus p-sarja 6, voit
käyttää sitä rakennuspalikka, tai

677
00:29:05,120 --> 00:29:08,870
ainesosa tai Scratch puhua,
menettelyä, jotain, mitä laittaa, et

678
00:29:08,870 --> 00:29:12,560
luonut oman palapelin pala
että voit käyttää uudelleen.

679
00:29:12,560 --> 00:29:17,090
Joten kompromissit, mutta mahdollisia ratkaisuja
että olemme nähneet ennen.

680
00:29:17,090 --> 00:29:20,560
>> Niin usein, näet tämän joka
vuosi tai kaksi, kun Apple julkaisee

681
00:29:20,560 --> 00:29:23,060
jotain uutta, ja kaikki hulluja ihmisiä
riviin ulkopuolella Apple

682
00:29:23,060 --> 00:29:27,050
ostamaan marginaali
päivittää laitteisto.

683
00:29:27,050 --> 00:29:30,420
Sanon tämän, se on OK, koska
Olen yksi niistä ihmisistä.

684
00:29:30,420 --> 00:29:35,140
Millainen tietorakenne
voisi edustaa tätä todellisuutta?

685
00:29:35,140 --> 00:29:36,980
>> No, kutsutaan sitä jono, rivi.

686
00:29:36,980 --> 00:29:40,270
Joten British kutsuisi sitä tyypillisesti
jono joka tapauksessa, joten se on kiva nimi.

687
00:29:40,270 --> 00:29:44,960
Ja kaksi operaatiota, että jono
tuetaan me kutsumme enqueue

688
00:29:44,960 --> 00:29:48,900
toiminta ja dequeue toimintaa,
, jotka ovat samanlaisia

689
00:29:48,900 --> 00:29:50,120
henki työntää ja pop.

690
00:29:50,120 --> 00:29:54,060
Se on vain eräänlainen erilainen
yleissopimus, mitä me soittaa näitä.

691
00:29:54,060 --> 00:29:57,680
Mutta laittaa jonoon jotain tarkoittaa lisätä
tai aseta se tietorakennetta.

692
00:29:57,680 --> 00:29:59,570
Voit dequeue keino poistaa se.

693
00:29:59,570 --> 00:30:05,170
Mutta taas pino oli LIFO tiedot
rakenne, jono on ensimmäinen,

694
00:30:05,170 --> 00:30:06,740
first out tietorakenne.

695
00:30:06,740 --> 00:30:10,050
>> Jos olet ensimmäinen henkilö linjassa,
olet ensimmäinen henkilö saada

696
00:30:10,050 --> 00:30:12,420
ulos linja ja ostaa uusi laite.

697
00:30:12,420 --> 00:30:18,070
Kuvittele kuinka järkyttynyt nämä ihmiset olisivat
jos Apple sen sijaan käytetään pino varten

698
00:30:18,070 --> 00:30:21,250
Esimerkiksi toteuttaa poiminta
jopa oman uuden lelun.

699
00:30:21,250 --> 00:30:24,310
Joten jonot järkeä, varmasti ja
voimme ajatella kaikenlaisia

700
00:30:24,310 --> 00:30:27,480
sovelluksia, oletettavasti, jonot,
varsinkin kun haluat oikeudenmukaisuutta.

701
00:30:27,480 --> 00:30:30,040
Joten miten voisimme toteuttaa nämä
sillä tietorakenne?

702
00:30:30,040 --> 00:30:33,680
>> No, ehdotan, että voisimme
täytyy tehdä se tällä tavalla.

703
00:30:33,680 --> 00:30:35,225
Joten aion nyt numeroita.

704
00:30:35,225 --> 00:30:38,190
Joten me pitää se yksinkertainen ja ei
välttämättä puhutaan lokeroihin.

705
00:30:38,190 --> 00:30:40,220
Vain numeroita että ihmiset mennyt.

706
00:30:40,220 --> 00:30:43,760
Kapasiteetti on menossa jälleen korjata
henkilöiden määrä, jotka voivat olla

707
00:30:43,760 --> 00:30:46,900
tätä linjaa, sillä kolme tai
mitä muita arvo.

708
00:30:46,900 --> 00:30:50,760
>> Mutta ehdotan, että minun täytyy seurata
ei ainoastaan ​​koosta

709
00:30:50,760 --> 00:30:52,370
jono, kuinka monet asiat ovat siinä.

710
00:30:52,370 --> 00:30:56,310
Joten koko on nykyinen koko, kapasiteetti
on enimmäiskoko.

711
00:30:56,310 --> 00:30:58,540
Vain kerran, nimikkeistö
sopimuksen mukaan.

712
00:30:58,540 --> 00:31:03,680
Miksi tarvitsen lisää int sisällä
jonon seurata kuka on

713
00:31:03,680 --> 00:31:05,365
rivin?

714
00:31:05,365 --> 00:31:07,930

715
00:31:07,930 --> 00:31:10,910
Miksi minun pitää tehdä, että tässä tapauksessa?

716
00:31:10,910 --> 00:31:14,750

717
00:31:14,750 --> 00:31:16,190
>> No, miten tämä kuva
tulee muuttumaan?

718
00:31:16,190 --> 00:31:19,280
Voin ehkä uudelleen useimmat
Kuvan.

719
00:31:19,280 --> 00:31:21,480
Anna minun mennä eteenpäin ja poistaa mitä on täällä.

720
00:31:21,480 --> 00:31:24,580
Annamme tässä hieman
eri nimellä täällä.

721
00:31:24,580 --> 00:31:28,930
Mennään eroon 17 Mennään eroon
ja 9, nyt päästä eroon 3.

722
00:31:28,930 --> 00:31:30,410
Ja antaa vielä yhden asian.

723
00:31:30,410 --> 00:31:34,710
Ehdotan, että minun täytyy seurata
edessä lista, joka on vain

724
00:31:34,710 --> 00:31:35,570
olemaan int samoin.

725
00:31:35,570 --> 00:31:36,550
Ja me aiomme pitää asiat yksinkertaisina.

726
00:31:36,550 --> 00:31:37,740
Ei linkitetty lista nyt.

727
00:31:37,740 --> 00:31:40,900
>> Me myönnettävä, että aiomme
kolahtaa vastaan ​​tämän rajan.

728
00:31:40,900 --> 00:31:43,720
Mutta mitä haluan nähdä
tapahtuu tällä kertaa?

729
00:31:43,720 --> 00:31:47,240
Joten kai mennä eteenpäin ja ensimmäinen
henkilö keksii linjassa, ja

730
00:31:47,240 --> 00:31:48,560
se on numero 9.

731
00:31:48,560 --> 00:31:49,680
Meillä on stressi pallot.

732
00:31:49,680 --> 00:31:51,330
Voinko varastaa, eli kaksi tai kolme ihmistä?

733
00:31:51,330 --> 00:31:52,690
Yksi, kaksi, kolme?

734
00:31:52,690 --> 00:31:53,120
Tule ylös.

735
00:31:53,120 --> 00:31:56,022
Oikea edestä, koska
Tästä tehdään yksi nopea.

736
00:31:56,022 --> 00:31:59,415
>> Jokainen teistä on nyt olemaan
tuuletin poika jonossa Apple.

737
00:31:59,415 --> 00:32:03,970

738
00:32:03,970 --> 00:32:06,210
Et ehkä saa Applen laitteet
lopussa tämän kuitenkin.

739
00:32:06,210 --> 00:32:06,500
Selvä.

740
00:32:06,500 --> 00:32:09,430
Joten olet numero 9, olet
numero 17, numero 22.

741
00:32:09,430 --> 00:32:12,130
Nämä ovat mielivaltaisia ​​numeroita, kuten
Opiskelija tunnukset tai vaikka mitä.

742
00:32:12,130 --> 00:32:14,550
Ja vain hetken, aloitetaan
aloittaa lisäämällä asioita.

743
00:32:14,550 --> 00:32:16,000
Ja minä ajaa aluksella tässä tällä kertaa.

744
00:32:16,000 --> 00:32:19,570
>> Joten tässä tapauksessa, olen alustettu
edessä on -

745
00:32:19,570 --> 00:32:22,380
Olen itse ei välitä, mitä
edessä on, koska koko on nolla.

746
00:32:22,380 --> 00:32:24,480
Joten tämä saattoi aivan hyvin
olla kysymysmerkki.

747
00:32:24,480 --> 00:32:26,170
Nämä kaikki ovat kysymysmerkkejä.

748
00:32:26,170 --> 00:32:29,880
Joten nyt alamme todella nähdä
ihmiset riviin myymälässä.

749
00:32:29,880 --> 00:32:33,320
>> Joten jos numero 9, olet ensimmäinen
siellä 5 AM, mennä eteenpäin ja riviin,

750
00:32:33,320 --> 00:32:34,210
tai iltana.

751
00:32:34,210 --> 00:32:34,580
OK.

752
00:32:34,580 --> 00:32:35,940
Joten nyt 9 on täällä.

753
00:32:35,940 --> 00:32:37,940
Joten 9 on edessä luettelosta.

754
00:32:37,940 --> 00:32:41,440
Joten aion mennä eteenpäin ja päivittää
koko nykyisten tietojen

755
00:32:41,440 --> 00:32:44,740
rakennetta ei ole 0 enää,
vaan olla 1.

756
00:32:44,740 --> 00:32:47,630
Aion laittaa 9 at
edessä luettelosta.

757
00:32:47,630 --> 00:32:51,020
Anna minun mennä eteenpäin ja vaihtaa näytön
jotta voimme nähdä ohitsemme täällä.

758
00:32:51,020 --> 00:32:53,220
>> Ja nyt, mitä haluan
laittaa edessä?

759
00:32:53,220 --> 00:32:56,240
Aion seurata, että
jonon nyt

760
00:32:56,240 --> 00:32:58,570
on paikalla 0.

761
00:32:58,570 --> 00:33:00,510
Sillä se, mitä seuraavaksi tapahtuu?

762
00:33:00,510 --> 00:33:03,000
No, kai nyt laittaa jonoon
17 samoin.

763
00:33:03,000 --> 00:33:04,510
Joten hop linjassa siellä.

764
00:33:04,510 --> 00:33:07,060
Ja vielä, eräänlainen oven
myymälä tulee olemaan täällä.

765
00:33:07,060 --> 00:33:08,700
Joten nyt olen lisätty 17.

766
00:33:08,700 --> 00:33:10,810
Ja vaikka nämä kaverit ovat estämässä
näyttö, se on OK,

767
00:33:10,810 --> 00:33:12,300
koska voimme nähdä sen täällä.

768
00:33:12,300 --> 00:33:12,910
Anteeksi.

769
00:33:12,910 --> 00:33:13,810
>> Yleisö: Voimme liikkua -

770
00:33:13,810 --> 00:33:14,660
>> DAVID MALAN: Ei, se on OK.

771
00:33:14,660 --> 00:33:16,000
Se on valtava siellä.

772
00:33:16,000 --> 00:33:18,580
Joten 17 on nyt sisä-jonon.

773
00:33:18,580 --> 00:33:21,332
Minun täytyy päivittää joka
kentät nyt vaikka?

774
00:33:21,332 --> 00:33:23,210
OK, varmasti koko.

775
00:33:23,210 --> 00:33:26,430
Ja miten edessä?

776
00:33:26,430 --> 00:33:27,040
OK, no.

777
00:33:27,040 --> 00:33:30,200
Edessä ei pitäisi muuttaa, koska
toisin kuin pinon, me

778
00:33:30,200 --> 00:33:31,370
haluavat säilyttää oikeudenmukaisuutta.

779
00:33:31,370 --> 00:33:35,150
Joten jos 9 tuli ensin, haluamme 9
olla ensimmäinen ulos linja

780
00:33:35,150 --> 00:33:36,420
ja myymälä.

781
00:33:36,420 --> 00:33:37,220
>> Itse asiassa, nyt nähdä, että.

782
00:33:37,220 --> 00:33:42,235
Ennen kuin voimme lisätä 22, nyt
mennä eteenpäin ja dequeue 9.

783
00:33:42,235 --> 00:33:42,970
Mikä sinun nimesi olikaan?

784
00:33:42,970 --> 00:33:43,680
>> Yleisö: Jake.

785
00:33:43,680 --> 00:33:45,440
>> DAVID MALAN: Jake on menossa
voidaan dequeued nyt.

786
00:33:45,440 --> 00:33:48,050
Joten saat kävellä kauppaan.

787
00:33:48,050 --> 00:33:49,880
Ja teeskennellä, että myymälä
on tuolla.

788
00:33:49,880 --> 00:33:51,970
Joten nyt mitä tarvitsee - dit-dit-dit!

789
00:33:51,970 --> 00:33:53,400
Mitä täytyy tapahtua nyt?

790
00:33:53,400 --> 00:33:54,490
Suunnittelu päätös.

791
00:33:54,490 --> 00:33:56,825
Joten ei paha vaisto, mutta -
Mikä sinun nimesi olikaan?

792
00:33:56,825 --> 00:33:57,090
>> Yleisö: David.

793
00:33:57,090 --> 00:33:57,500
>> DAVID MALAN: David.

794
00:33:57,500 --> 00:33:58,810
Mitäs David tehdä?

795
00:33:58,810 --> 00:34:02,590
Hän yritti tavallaan vahvistaa tiedot
rakenne ja siirtyä hänen sijainnistaan

796
00:34:02,590 --> 00:34:04,100
osaksi Jake entinen sijainti.

797
00:34:04,100 --> 00:34:06,740
Ja se on hienoa, jos olemme valmiita
hyväksyä, että

798
00:34:06,740 --> 00:34:08,199
täytäntöönpanon yksityiskohtia.

799
00:34:08,199 --> 00:34:11,100
Mutta ensin on päivittää tiedot
rakenne ennen kuin teemme sen.

800
00:34:11,100 --> 00:34:14,139
Koska en ole mieltynyt ajatukseen kaikkien
ihmiset siirtymässä tätä linjaa.

801
00:34:14,139 --> 00:34:17,360
>> Se ei ole iso juttu, jos David tekee sen
yksi askel, mutta jälleen kerran, muistelen

802
00:34:17,360 --> 00:34:20,360
kun meillä on ollut kahdeksan vapaaehtoisille
vaiheessa ja olemme tehneet kuten paikoilleen

803
00:34:20,360 --> 00:34:22,600
lajitella, jossa meidän piti aloittaa
liikkuvat kaikki ympärillä.

804
00:34:22,600 --> 00:34:23,790
Se sai kallista, eikö?

805
00:34:23,790 --> 00:34:28,330
Se saa minut punastumaan noin iso O
n, iso O n potenssiin uudelleen.

806
00:34:28,330 --> 00:34:30,650
Se ei ole tunne kuin
Paras lopputulos.

807
00:34:30,650 --> 00:34:32,080
>> Joten haluan vain päivittää.

808
00:34:32,080 --> 00:34:35,120
Joten koko jonon
ei ole enää 2.

809
00:34:35,120 --> 00:34:37,090
Nyt on yksinkertaisesti 1.

810
00:34:37,090 --> 00:34:40,360
Mutta voin nyt päivittää jotain
En päivittänyt ennen,

811
00:34:40,360 --> 00:34:41,130
edessä luettelosta.

812
00:34:41,130 --> 00:34:45,420
Voisin sanoa, että paikka 1?

813
00:34:45,420 --> 00:34:49,770
Joten nyt meillä on roskaa arvo tähän,
roskat arvo täällä, ja David

814
00:34:49,770 --> 00:34:51,469
Keskellä tätä roskaa.

815
00:34:51,469 --> 00:34:54,980
Mutta tietorakenne
on ehjä.

816
00:34:54,980 --> 00:34:58,540
>> Ja itse asiassa, en edes tarvitse
muuttaa Jaken entisen numeron

817
00:34:58,540 --> 00:35:00,460
9, koska who cares.

818
00:35:00,460 --> 00:35:04,470
Minulla on tarpeeksi tietoa nyt
koko, että tiedän siellä on yksi henkilö

819
00:35:04,470 --> 00:35:05,030
tähän jonoon.

820
00:35:05,030 --> 00:35:08,340
Ja tiedän, että kyseinen henkilö
on paikassa 1, ei 0.

821
00:35:08,340 --> 00:35:09,760
En laskenta.

822
00:35:09,760 --> 00:35:11,300
Joten 1 samoin.

823
00:35:11,300 --> 00:35:13,410
Joten tietorakenne on vielä OK.

824
00:35:13,410 --> 00:35:14,330
>> No, mitä tapahtuu seuraavaksi?

825
00:35:14,330 --> 00:35:15,010
Katsotaanpa enqueue -

826
00:35:15,010 --> 00:35:15,370
Mikä sinun nimesi on?

827
00:35:15,370 --> 00:35:16,160
>> Yleisö: Callen.

828
00:35:16,160 --> 00:35:16,580
>> DAVID MALAN: Callen.

829
00:35:16,580 --> 00:35:20,770
Katsotaanpa laittaa jonoon Callen, ja
22 on nyt jonossa.

830
00:35:20,770 --> 00:35:22,300
Mitä nyt on muututtava täällä?

831
00:35:22,300 --> 00:35:24,380
Etu ei tule
muuttaa, tietenkin.

832
00:35:24,380 --> 00:35:27,160
Koko on muuttumassa olla 2 uudelleen.

833
00:35:27,160 --> 00:35:31,590
Ja 22 päätyy tänne, 9 on edelleen läsnä,
mutta se on tehokkaasti

834
00:35:31,590 --> 00:35:32,600
roskat arvo nyt.

835
00:35:32,600 --> 00:35:35,910
Se on vain jäänne Jake ohi.

836
00:35:35,910 --> 00:35:39,200
>> Joten nyt mitä tapahtuu, jos
Olen dequeue David?

837
00:35:39,200 --> 00:35:41,560
Viimeinen toiminta, dequeue David.

838
00:35:41,560 --> 00:35:46,070
Voisimme siirtää, mutta ehdotan, katsotaanpa
tehdä niin vähän työtä kuin mahdollista.

839
00:35:46,070 --> 00:35:50,280
Nyt tietoni rakenne menee
takaisin kooltaan 2-1.

840
00:35:50,280 --> 00:35:53,730
Mutta jonon
nyt tulee 2.

841
00:35:53,730 --> 00:35:56,640
Minun ei tarvitse muuttaa näitä numeroita
vielä, koska he

842
00:35:56,640 --> 00:35:58,230
vain roskat arvot.

843
00:35:58,230 --> 00:35:59,720
>> Mutta mitä nyt tapahtuu?

844
00:35:59,720 --> 00:36:03,280
Kai laittaa jonoon itse, 26?

845
00:36:03,280 --> 00:36:05,890
Tunnen kuulun tänne.

846
00:36:05,890 --> 00:36:06,890
Joten Minua enqueued.

847
00:36:06,890 --> 00:36:08,760
Joten olen sellainen kuulu tänne.

848
00:36:08,760 --> 00:36:11,300
Ja vaikka et ole aivan
Arvostan tätä visuaalisesti vaiheessa

849
00:36:11,300 --> 00:36:15,075
koska meillä on runsaasti tilaa, haluan
ei seison tässä, miksi?

850
00:36:15,075 --> 00:36:16,290
>> Yleisö: Olet out of bounds.

851
00:36:16,290 --> 00:36:16,370
>> DAVID MALAN: Oikea.

852
00:36:16,370 --> 00:36:16,940
Olen out of bounds.

853
00:36:16,940 --> 00:36:19,330
Olen indeksoitu yli
bounds tämän taulukon.

854
00:36:19,330 --> 00:36:23,420
En todellakaan pitäisi olla yksi
kolme mahdollisia paikkoja.

855
00:36:23,420 --> 00:36:25,150
Nyt, missä on kaikkein luonnollisin mennä?

856
00:36:25,150 --> 00:36:27,760
Ehdotan velkarahalla
viikolla yksi temppu.

857
00:36:27,760 --> 00:36:30,150
Mod operaattori prosenttiyksikköä.

858
00:36:30,150 --> 00:36:36,850
Koska olen teknisesti seisoo
sijainti 3, mutta en 3 mod kapasiteettia,

859
00:36:36,850 --> 00:36:40,250
niin 3, prosenttimerkki, 3 -

860
00:36:40,250 --> 00:36:40,970
kapasiteetti on 3.

861
00:36:40,970 --> 00:36:41,720
Mikä tuo on?

862
00:36:41,720 --> 00:36:43,700
Mikä on jakojäännös, kun
jaat 3 noin 3?

863
00:36:43,700 --> 00:36:44,070
0.

864
00:36:44,070 --> 00:36:48,140
>> Niin että saa minut oli Jake oli,
joka on todella hyvä.

865
00:36:48,140 --> 00:36:50,370
Joten nyt täytäntöönpanoa
tämä asia tulee

866
00:36:50,370 --> 00:36:51,250
olla hieman päänsärkyä.

867
00:36:51,250 --> 00:36:53,740
Se on oikeastaan ​​vain yksi rivi
päänsärky, koodia.

868
00:36:53,740 --> 00:36:56,580
Mutta ainakin nyt on roskaa
arvo täällä, mutta siellä on kaksi

869
00:36:56,580 --> 00:36:57,910
laillista ints täällä.

870
00:36:57,910 --> 00:37:04,160
Ja väitän, että nyt olemme tehneet
mitä meidän täytyy tehdä niin kauan kuin

871
00:37:04,160 --> 00:37:08,600
muutamme mitä Jaken
arvo oli 26 jäsentä.

872
00:37:08,600 --> 00:37:12,110
>> Meillä on nyt tarpeeksi tietoa edelleen
luotettavuuden säilyttämiseksi

873
00:37:12,110 --> 00:37:13,060
Tämän tietorakenteen.

874
00:37:13,060 --> 00:37:17,160
Olemme vielä sellainen pois onnea, kun olemme
haluat lisätä vähintään neljä yhteensä

875
00:37:17,160 --> 00:37:20,740
elementtejä, mutta ainakin voin tehdä melko
tehokas käyttö tämän jatkuvan

876
00:37:20,740 --> 00:37:21,740
aikaa, itse asiassa.

877
00:37:21,740 --> 00:37:27,150
En tarvitse murehtia siirtymässä
kaikille, sillä Davidin kaltevuus oli.

878
00:37:27,150 --> 00:37:30,816
>> Kysyttävää pinoja,
tai tähän jonoon?

879
00:37:30,816 --> 00:37:32,184
>> AUDIENCE: Onko miksi
tarvitset kokoa niin tiedät

880
00:37:32,184 --> 00:37:34,010
missä on ihminen?

881
00:37:34,010 --> 00:37:34,770
>> DAVID MALAN: Aivan.

882
00:37:34,770 --> 00:37:38,230
Minun täytyy tietää koko joukko
koska minun täytyy tietää tarkalleen, kuinka

883
00:37:38,230 --> 00:37:41,940
Monet näistä arvoista ovat oikeutettuja,
ja niin, että voin löytää mihin

884
00:37:41,940 --> 00:37:42,800
seuraava henkilö.

885
00:37:42,800 --> 00:37:43,300
Täsmälleen.

886
00:37:43,300 --> 00:37:44,580
Koko on -

887
00:37:44,580 --> 00:37:46,360
Oikeastaan ​​emme päivittää tätä vielä.

888
00:37:46,360 --> 00:37:48,380
Lisäsin itseni 26.

889
00:37:48,380 --> 00:37:51,760
Koko on nyt, ei 1, mutta 2.

890
00:37:51,760 --> 00:37:57,780
Joten nyt tämä todellakin auttaa minua löytämään
johtaja luettelon, joka ei ole 0, ei

891
00:37:57,780 --> 00:37:59,250
1, mutta on 2.

892
00:37:59,250 --> 00:38:01,665
Edessä lista
on todellakin numero 22.

893
00:38:01,665 --> 00:38:05,120
Koska hän tuli ensin, niin hän olisi
päästetä varastoida ennen minua,

894
00:38:05,120 --> 00:38:08,780
vaikka visuaalisesti Seison
lähempänä myymälän.

895
00:38:08,780 --> 00:38:09,220
>> Kaikki hyvin?

896
00:38:09,220 --> 00:38:12,410
Aplodit nämä kaverit
ja annamme ne pois sieltä.

897
00:38:12,410 --> 00:38:17,090
>> [APPLAUSE]

898
00:38:17,090 --> 00:38:18,150
>> DAVID MALAN: antaisin
pidät lokeroon.

899
00:38:18,150 --> 00:38:20,760
Voisimme nähdä, mitä tapahtuu, jos
haluat, mutta ehkä ei.

900
00:38:20,760 --> 00:38:21,590
Selvä.

901
00:38:21,590 --> 00:38:25,380
Joten mitä nyt se jättää meidät?

902
00:38:25,380 --> 00:38:28,900
No, minäpä ehdottaa, että on olemassa
muutamia muita tietorakenteita voisimme

903
00:38:28,900 --> 00:38:33,810
aloittaa lisäämällä meidän työkalusarja joka tulee
itse asiassa olla melko, melko osuvia

904
00:38:33,810 --> 00:38:35,270
me sukeltaa web kamaa.

905
00:38:35,270 --> 00:38:38,150
Joka taas on jonkinlainen yhteys
puita muodossa

906
00:38:38,150 --> 00:38:40,550
jotain kutsutaan DOM, asiakirja
objektimalli.

907
00:38:40,550 --> 00:38:42,370
Mutta näemme enemmän
että ennen pitkää.

908
00:38:42,370 --> 00:38:46,260
>> Sallikaa minun määritelmällisesti että
kutsupuu mitä nyt ehkä tiedätte kuin

909
00:38:46,260 --> 00:38:48,820
enemmän sukupuun, jossa
joitakin kantaisä on

910
00:38:48,820 --> 00:38:49,790
juuret puu.

911
00:38:49,790 --> 00:38:54,480
Patriarkaalinen tai matriarkka at
hyvin puun latvaan.

912
00:38:54,480 --> 00:38:56,700
Ilman heidän puolisonsa, tässä tapauksessa.

913
00:38:56,700 --> 00:39:00,940
Mutta meillä on nyt, mitä me kutsumme
lapset, jotka ovat solmuja, jotka roikkuvat

914
00:39:00,940 --> 00:39:05,480
pois vasen lapsi tai oikea lapsi,
nuolet kuten kuvattu täällä.

915
00:39:05,480 --> 00:39:10,490
>> Toisin sanoen, kun puu tietorakenne
tietokoneen, puu on nolla

916
00:39:10,490 --> 00:39:11,480
tai useampi solmu.

917
00:39:11,480 --> 00:39:13,500
Jos se on ainakin yksi solmu,
sitä kutsutaan root.

918
00:39:13,500 --> 00:39:15,700
Se on asioita visuaalisesti että
vedämme huipulla.

919
00:39:15,700 --> 00:39:20,280
Ja että solmu, kuten mikä tahansa muu solmu, voi
on nolla, yksi tai kaksi tai kolme,

920
00:39:20,280 --> 00:39:23,600
tai miten monta lasta
tietorakenne tukee.

921
00:39:23,600 --> 00:39:29,150
Tässä tapauksessa juuri, varastointi
arvo yksi, on kaksi lasta, 2 ja 3,

922
00:39:29,150 --> 00:39:33,020
niin me yleensä soittaa 2 vasen
lapsi ja 3 oikea lapsi.

923
00:39:33,020 --> 00:39:36,940
>> Ja sitten kun pääsemme 5, 6, ja
7, 6 voisi kutsua keskimmäinen lapsi.

924
00:39:36,940 --> 00:39:38,940
Jos sinulla on neljä lasta,
se saa hämmentävä.

925
00:39:38,940 --> 00:39:42,260
Joten lopeta tuollainen
pikakuvake sanallisesti.

926
00:39:42,260 --> 00:39:44,580
Mutta se on oikeastaan ​​vain sukupuun.

927
00:39:44,580 --> 00:39:48,880
Ja lehdet tässä ovat solmuja, jotka
itse ei ole lapsia.

928
00:39:48,880 --> 00:39:52,540
Ne roikkuvat pois puun alaosaa.

929
00:39:52,540 --> 00:39:56,940
>> Joten miten voisimme toteuttaa puu, joka
on vain kaksi lasta maksimaalisesti?

930
00:39:56,940 --> 00:39:58,410
Me kutsumme sitä binääripuu.

931
00:39:58,410 --> 00:40:00,960
Bi taas tarkoittaa kahta tässä
tapauksessa, kuten binary.

932
00:40:00,960 --> 00:40:04,830
Ja niin se voi olla nolla, yksi,
tai kaksi lasta maksimaalisesti.

933
00:40:04,830 --> 00:40:08,650
>> Minä ehdotan, että toteutamme solmu
että rakenne int n,

934
00:40:08,650 --> 00:40:11,910
ja sitten kaksi osoitinta, yksi nimeltään
vasemmalle, yksi nimeltään oikea.

935
00:40:11,910 --> 00:40:14,830
Mutta ne ovat vain mukavia
mielivaltainen yleissopimukset.

936
00:40:14,830 --> 00:40:18,170
Ja mitä mukavaa nyt, varsinkin jos
Tällainen kamppaillut käsitteellisesti

937
00:40:18,170 --> 00:40:21,300
rekursio, tai ajatellut, että se ei ollut
todella ratkaisu mihinkään,

938
00:40:21,300 --> 00:40:23,120
varsinkin jos voisit
muisti loppuu.

939
00:40:23,120 --> 00:40:26,600
Nyt puhumme tiedot
rakenteita ja algoritmeja, jotka mahdollistavat

940
00:40:26,600 --> 00:40:31,030
meitä kulkemaan ja manipuloida niitä,
Osoittautuu, että rekursiivisista tulee takaisin

941
00:40:31,030 --> 00:40:34,240
paljon pakottavia
jos ei kauniilla tavalla.

942
00:40:34,240 --> 00:40:38,670
>> Joten tämä Ehdotan täytäntöönpano
ja hakutoiminto.

943
00:40:38,670 --> 00:40:39,870
Koska kaksi tuloa -

944
00:40:39,870 --> 00:40:41,570
niin ajattele tätä musta laatikko.

945
00:40:41,570 --> 00:40:46,560
Koska kaksi tuloa, n, int, ja
osoitin puu, osoitin

946
00:40:46,560 --> 00:40:50,020
solmu, tai oikeastaan ​​juuri puu, I
väittävät, että tämä toiminto voi palauttaa

947
00:40:50,020 --> 00:40:53,530
totta vai tarua, että arvo n
on sisällä tämän puun.

948
00:40:53,530 --> 00:40:55,210
>> Mitä sisällä tämä musta laatikko?

949
00:40:55,210 --> 00:40:57,440
No, neljä oksat.

950
00:40:57,440 --> 00:40:58,385
Ensimmäinen vain tarkistaa.

951
00:40:58,385 --> 00:41:00,490
Jos puu on null, vain palauttaa false.

952
00:41:00,490 --> 00:41:04,580
Jos ei ole solmu, ei ole n,
ei ole numero, vain palauttaa false.

953
00:41:04,580 --> 00:41:12,330
Jos kuitenkin, n, arvo etsit
varten, on pienempi kuin puu nuoli n ja

954
00:41:12,330 --> 00:41:15,180
vain olla selvää, mitä se tarkoittaa, kun
Kirjoitan puu ja sitten nuoli

955
00:41:15,180 --> 00:41:18,150
merkintätapa, n?

956
00:41:18,150 --> 00:41:18,690
Täsmälleen.

957
00:41:18,690 --> 00:41:21,970
Se tarkoittaa dereference että
osoitin kutsutaan puu.

958
00:41:21,970 --> 00:41:26,750
Mene sinne, ja sitten päästä sisälle, että
solmu ja saada alansa Kutsutaan.

959
00:41:26,750 --> 00:41:30,810
Ja sitten verrata todellisia n, joka oli
johdetaan Haku sitä vastaan.

960
00:41:30,810 --> 00:41:35,390
>> Joten jos n on pienempi kuin n-arvo
puussa solmun itse, hyvin,

961
00:41:35,390 --> 00:41:36,720
mitä se tarkoittaa?

962
00:41:36,720 --> 00:41:40,690
Tämä tarkoittaa mitään ensi silmäyksellä.

963
00:41:40,690 --> 00:41:40,900
Oikea?

964
00:41:40,900 --> 00:41:45,560
Aivan kuten silloin, kun on joukko
arvot, haluat ehkä soveltaa binary

965
00:41:45,560 --> 00:41:48,290
etsiä muotona kahtiajaon
ja valloittaa.

966
00:41:48,290 --> 00:41:51,790
Mutta mitä oletus ei meidän tehdä
binary haku toimi lainkaan

967
00:41:51,790 --> 00:41:54,510
puhelinluettelosta, ja
Aiempia esimerkkejä?

968
00:41:54,510 --> 00:41:55,530
>> Miten voidaan lajitella.

969
00:41:55,530 --> 00:41:59,490
Joten tarkentaa määritelmää puu
täällä ei olla vain puu, joka voi

970
00:41:59,490 --> 00:42:00,880
mitään määrän lapsia.

971
00:42:00,880 --> 00:42:04,700
Ei vain binääripuu, joka voi
on 0, 1 tai 2 maksimaalisesti.

972
00:42:04,700 --> 00:42:09,700
Mutta binäärihakupuu tai BST,
joka on vain hieno tapa sanoa

973
00:42:09,700 --> 00:42:15,430
binääripuussa siten, että jokaisen solmun
vasen lapsi, jos on läsnä, on

974
00:42:15,430 --> 00:42:16,830
vähemmän kuin solmu.

975
00:42:16,830 --> 00:42:20,170
Ja jokainen solmun oikea lapsi,
jos läsnä on suurempi

976
00:42:20,170 --> 00:42:21,740
kuin solmu itse.

977
00:42:21,740 --> 00:42:25,200
>> Eli toisin sanoen, jos olisit tehdä
puu pois, kaikki numerot ovat

978
00:42:25,200 --> 00:42:30,620
tasapainoisia näin niin, että jos
sinulla on 55 root, 33 voi mennä

979
00:42:30,620 --> 00:42:33,090
sen vasemmalla puolella, koska se on vähemmän kuin 55.

980
00:42:33,090 --> 00:42:36,430
77 voi mennä sen oikein, koska
se on suurempi kuin 55.

981
00:42:36,430 --> 00:42:40,750
Mutta nyt huomaa, samaa määritelmää,
se on rekursiivinen määritelmä sanallisesti,

982
00:42:40,750 --> 00:42:42,600
on haettava 33.

983
00:42:42,600 --> 00:42:47,610
33 vasemman Lapsen tulee olla alle sen,
ja 33: n oikea lapsi, 44, on oltava

984
00:42:47,610 --> 00:42:48,580
suurempi kuin se.

985
00:42:48,580 --> 00:42:51,670
>> Joten tämä on binäärihakupuu, ja
Ehdotan, käyttäen hieman

986
00:42:51,670 --> 00:42:53,910
rekursio, voimme nyt löytää n.

987
00:42:53,910 --> 00:42:59,160
Joten jos n on pienempi kuin arvo n, joka on
nykyinen solmu, aion mennä

988
00:42:59,160 --> 00:43:04,090
eteenpäin ja ruuhi, niin sanotusti, ja vain
palata riippumatta vastaus on

989
00:43:04,090 --> 00:43:08,470
etsivät n päälle
puun vasen lapsi.

990
00:43:08,470 --> 00:43:11,370
Huomaa jälleen, tämä toiminto vain
odottaa solmu tähden,

991
00:43:11,370 --> 00:43:12,780
osoitin solmuun.

992
00:43:12,780 --> 00:43:17,360
Niin varmasti voin vain tehdä puiden
nuoli vasemmalle, mikä johtaa

993
00:43:17,360 --> 00:43:18,400
minut toiseen solmuun.

994
00:43:18,400 --> 00:43:19,480
Mutta mikä on se solmu?

995
00:43:19,480 --> 00:43:22,820
>> No, tämän julistuksen,
vasemmalla on vain osoitin, niin että vain

996
00:43:22,820 --> 00:43:27,090
tarkoittaa olen ohimennen hakutoiminto
eri osoitin, eli

997
00:43:27,090 --> 00:43:30,750
yksi, joka edustaa
minun vasen lapsen puu.

998
00:43:30,750 --> 00:43:36,040
Joten tässä tapauksessa osoitin 33, jos
Tämä on meidän näyte tulo Samaan aikaan, jos

999
00:43:36,040 --> 00:43:40,740
n on suurempi kuin arvo n on
nykyinen solmu puussa, niin olen

1000
00:43:40,740 --> 00:43:43,370
mene eteenpäin ja punt muiden
suuntaan ja vain sanoa, en

1001
00:43:43,370 --> 00:43:47,280
tietää, jos tämä arvo n on puu,
mutta en tiedä, jos se on, se on alas minun

1002
00:43:47,280 --> 00:43:49,090
oikea haara, niin sanoakseni.

1003
00:43:49,090 --> 00:43:53,120
Joten Soitan rekursiivisesti etsiä,
kulkee n uudelleen, mutta ohimennen

1004
00:43:53,120 --> 00:43:54,580
osoitin minun oikea lapsi.

1005
00:43:54,580 --> 00:44:00,020
>> Toisin sanoen, jos olen tällä hetkellä 55
ja etsin 99, tiedän, että 99

1006
00:44:00,020 --> 00:44:04,270
on suurempi kuin 55, joten aivan kuten Revin
puhelinluettelosta viikkoa sitten ja me

1007
00:44:04,270 --> 00:44:07,140
meni oikein, samoin me olemme
menossa täällä.

1008
00:44:07,140 --> 00:44:11,960
Ja en tiedä onko se minun oikealle
lapsi, ja se ei ole, 77 on olemassa, mutta

1009
00:44:11,960 --> 00:44:13,210
Tiedän, että se siihen suuntaan.

1010
00:44:13,210 --> 00:44:18,770
Joten pyydän haku minun oikea lapsi,
77, ja anna hakuun luku ulos

1011
00:44:18,770 --> 00:44:24,950
siellä jos 99 tämä mielivaltainen
Esimerkiksi on todella olemassa.

1012
00:44:24,950 --> 00:44:26,900
>> Muu, mikä on viimeinen asia?

1013
00:44:26,900 --> 00:44:28,620
Jos puu on nolla on yksi tapaus.

1014
00:44:28,620 --> 00:44:31,890
Jos n on pienempi kuin nykyisen solmun
arvo on toinen asia.

1015
00:44:31,890 --> 00:44:35,120
Jos n on suurempi kuin nykyinen
solmun arvo on kolmas tapaus.

1016
00:44:35,120 --> 00:44:38,250
Mikä on neljäs ja viimeinen asia?

1017
00:44:38,250 --> 00:44:39,480
Luulen, että olemme pois tapauksissa, eikö?

1018
00:44:39,480 --> 00:44:44,690
Sen täytyy olla, että n on
nykyinen solmu, joka olen.

1019
00:44:44,690 --> 00:44:49,640
>> Joten jos Etsin 55 tässä vaiheessa
tarina, että haara

1020
00:44:49,640 --> 00:44:51,780
puu palaisi totta.

1021
00:44:51,780 --> 00:44:55,380
Niin mitä mielenkiintoista tässä on se, että me
itse, toisin kuin viikkoa aiemmin, olemme eräänlainen

1022
00:44:55,380 --> 00:44:56,740
ja kaksi pohja tapauksissa.

1023
00:44:56,740 --> 00:44:58,300
Ja he eivät tarvitse
olla kaikki huipulla.

1024
00:44:58,300 --> 00:45:01,390
Alkuun on pohja tapauksessa, koska jos
puu on null, ei ole mitään tekemistä.

1025
00:45:01,390 --> 00:45:03,410
Vain palata kovakoodattu
arvo false.

1026
00:45:03,410 --> 00:45:07,400
>> Alahaaran on eräänlainen
oletus, jonka mukaan jos olemme tarkastetaan

1027
00:45:07,400 --> 00:45:11,550
null, olemme tarkastetaan, jos se olisi
vasemmalle, mutta sen ei pitäisi olla, olemme

1028
00:45:11,550 --> 00:45:14,640
tarkistetaan, jos se olisi oikea, mutta se
ei pitäisi olla selvästi sen on oltava

1029
00:45:14,640 --> 00:45:15,870
juuri siellä missä olemme.

1030
00:45:15,870 --> 00:45:16,780
Se on pohja tapauksessa.

1031
00:45:16,780 --> 00:45:19,920
Joten siellä kaksi rekursiivinen tapauksissa
alumiinifoliota siellä keskellä.

1032
00:45:19,920 --> 00:45:21,630
Mutta en voinut kirjoittaa
Tässä missä tahansa järjestyksessä.

1033
00:45:21,630 --> 00:45:24,520
Ajattelin vain se sellainen tuntui luontevalta
ensin tarkistaa mahdollisen virheen,

1034
00:45:24,520 --> 00:45:28,340
tarkista sitten vasemmalle, sitten tarkistaa oikealle, sitten
olettaa, että olet solmussa

1035
00:45:28,340 --> 00:45:30,630
olet todella etsivät.

1036
00:45:30,630 --> 00:45:36,240
>> Joten miksi tämä voisi olla hyödyllistä?

1037
00:45:36,240 --> 00:45:37,910
Joten se kääntyy pois -

1038
00:45:37,910 --> 00:45:42,110
ja haluan hypätä teaser
täällä se on verkossa.

1039
00:45:42,110 --> 00:45:44,920
Aiomme alkaa käyttää ei
ohjelmointikieli aluksi, mutta

1040
00:45:44,920 --> 00:45:46,030
kuvauskieli.

1041
00:45:46,030 --> 00:45:48,740
Kuvauskieli on yksi, joka on
hengeltään samanlainen ohjelma

1042
00:45:48,740 --> 00:45:51,715
kieli, mutta se ei anna
kyky ilmaista itseäsi loogisesti.

1043
00:45:51,715 --> 00:45:55,070
Se vain antaa sinulle mahdollisuuden
ilmaista itseäsi rakenteellisesti.

1044
00:45:55,070 --> 00:45:57,960
>> Minne haluat laittaa jotain
sivulla, sivun?

1045
00:45:57,960 --> 00:45:59,200
Mitä väriä haluat tehdä?

1046
00:45:59,200 --> 00:46:00,950
Mitä fontin kokoa haluat tehdä?

1047
00:46:00,950 --> 00:46:02,970
Mitä sanoja sinä itse
haluavat www-sivulla?

1048
00:46:02,970 --> 00:46:04,060
Niin, että kuvauskieli.

1049
00:46:04,060 --> 00:46:07,690
Mutta sitten me nopeasti käyttöön
JavaScript, joka on täysimittainen

1050
00:46:07,690 --> 00:46:08,560
ohjelmointikieli.

1051
00:46:08,560 --> 00:46:12,530
Hyvin samanlainen rakenteeltaan ulkonäöltään
C, mutta se tulee olla

1052
00:46:12,530 --> 00:46:15,200
kiva, tehokkaampia ja
käyttäjäystävällisiä ominaisuuksia.

1053
00:46:15,200 --> 00:46:18,050
>> Ja yksi turhautumisen tässä
kohta lukukausi on, että me

1054
00:46:18,050 --> 00:46:22,065
pian täytäntöön aapinen vuonna huomattavasti vähemmän
riviä koodia muilla kielillä

1055
00:46:22,065 --> 00:46:25,580
kuin C puolestaan ​​sallitaan, mutta syystä: n
me pian ymmärtää.

1056
00:46:25,580 --> 00:46:27,750
Tämä on ensimmäinen tällainen web-sivun.

1057
00:46:27,750 --> 00:46:30,120
Se on täysin underwhelming,
ensimmäinen teemme.

1058
00:46:30,120 --> 00:46:31,400
Se yksinkertaisesti sanoa, hello world.

1059
00:46:31,400 --> 00:46:34,010
Mutta jos et ole koskaan nähnyt
ennen kuin tämä on HTML,

1060
00:46:34,010 --> 00:46:35,670
Hypertext Markup Language.

1061
00:46:35,670 --> 00:46:39,310
>> Jos menet tiettyjä valikon vaihtoehto
Useimmissa tahansa selaimella, millä tahansa web-sivu

1062
00:46:39,310 --> 00:46:43,160
Internetissä voit nähdä HTML
että jotkut ihmiset kirjoitti

1063
00:46:43,160 --> 00:46:44,400
luoda kyseisen sivun.

1064
00:46:44,400 --> 00:46:47,850
Ja se luultavasti ei näytä yhtä
lyhyt tai siisti kuin tämä.

1065
00:46:47,850 --> 00:46:51,400
Mutta se seuraa mallia näistä
avoin suluissa ja viiltää ja

1066
00:46:51,400 --> 00:46:53,660
kirjaimia ja mahdollisesti numeroita.

1067
00:46:53,660 --> 00:46:56,770
>> Ajattelin antaa teille teaser
mitä voit tehdä

1068
00:46:56,770 --> 00:46:57,950
ottamisen jälkeen CS50.

1069
00:46:57,950 --> 00:47:02,620
Anna minun mennä cs.harvard.edu / ryöstää,
oman Rob Bowden kotisivulla.

1070
00:47:02,620 --> 00:47:06,080
Hän teki tämän meille.

1071
00:47:06,080 --> 00:47:07,490
Joten voit pian olla mahdollisuus tehdä niin.

1072
00:47:07,490 --> 00:47:10,660
Ja myös, mitä kuulit
tänä aamuna -

1073
00:47:10,660 --> 00:47:12,480
mitä tänä aamuna -

1074
00:47:12,480 --> 00:47:13,780
>> [HAMSTER DANCE MUSIC]

1075
00:47:13,780 --> 00:47:15,702
>> - You'll voi tehdä tätä.

1076
00:47:15,702 --> 00:47:16,790
Joka meitä odottaa keskiviikkona.

1077
00:47:16,790 --> 00:47:17,791
Me nähdään sitten.

1078
00:47:17,791 --> 00:47:22,950
>> [HAMSTER DANCE MUSIC]

1079
00:47:22,950 --> 00:47:24,300
DAVID MALAN: Seuraavassa CS50 -

1080
00:47:24,300 --> 00:47:31,670