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

2
00:00:00,500 --> 00:00:03,340
[Musiikki soi]

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

4
00:00:11,020 --> 00:00:14,010
>> DAVID MALAN: Tämä on CS50.

5
00:00:14,010 --> 00:00:18,090
Ja tämä on sekä alku ja
end-- kuten literally-- lähes loppuun

6
00:00:18,090 --> 00:00:18,825
viikon kuusi.

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

8
00:00:20,030 --> 00:00:22,640
>> Ajattelin jakaa
hieman hauskaa tosiasia.

9
00:00:22,640 --> 00:00:25,370
Olen vetänyt tämän ylös
viimeisen lukukauden tietoja asetettu.

10
00:00:25,370 --> 00:00:29,710
Muistatte ehkä, että pyydämme teitä jokaisessa
p set muodossa, jos olet katsonut verkossa

11
00:00:29,710 --> 00:00:31,580
tai jos olet osallistunut henkilökohtaisesti.

12
00:00:31,580 --> 00:00:33,020
Ja tässä on tiedot.

13
00:00:33,020 --> 00:00:34,710
Joten tänään oli hyvin ennustettavissa.

14
00:00:34,710 --> 00:00:37,126
Mutta halusimme viettää hieman
aikaa kanssasi kuitenkin.

15
00:00:37,126 --> 00:00:40,599
Haluaisiko kukaan arveluihin, miksi tämä
kuvaaja on niin jaggy, ylös alas, ylös alas,

16
00:00:40,599 --> 00:00:41,265
niin johdonmukaisesti?

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

18
00:00:42,980 --> 00:00:45,130
Mitä kukin huiput
ja kaukalot ovat?

19
00:00:45,130 --> 00:00:46,005
>> Yleisö: [kuulumaton]

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

21
00:00:47,002 --> 00:00:47,835
DAVID MALAN: Todellakin.

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

23
00:00:50,900 --> 00:00:55,480
Ja lisää hauskasti, Jumala varjelkoon,
pidämme yksi luento perjantaina

24
00:00:55,480 --> 00:00:58,960
alussa lukukauden,
sitähän me nähdä tapahtuvan.

25
00:00:58,960 --> 00:01:03,430
Joten tänään, me osallistumme vähän
Lisätietoa tietorakenteita.

26
00:01:03,430 --> 00:01:06,660
Ja antaa sinulle enemmän kiinteää
mielenterveyden mallin ongelmia viisi,

27
00:01:06,660 --> 00:01:07,450
joka on nyt pois.

28
00:01:07,450 --> 00:01:10,817
Kirjoitusvirheitä, jossa, me
käden tekstitiedosto noin 100000

29
00:01:10,817 --> 00:01:12,650
plus Englanti sanoja, ja
olet menossa on

30
00:01:12,650 --> 00:01:17,770
selvittää, miten taitavasti ladata niitä
muistiin, RAM, käyttäen joitakin tietoja

31
00:01:17,770 --> 00:01:19,330
rakenne valintasi.

32
00:01:19,330 --> 00:01:22,470
>> Nyt yksi tällaisten tietojen rakennetta voitaisiin
olla, mutta luultavasti ei pitäisi olla,

33
00:01:22,470 --> 00:01:25,630
melko yksinkertainen linkitetty lista,
jonka otimme käyttöön viime kerralla.

34
00:01:25,630 --> 00:01:29,220
Ja linkitetty lista oli ainakin
yksi etu verrattuna array.

35
00:01:29,220 --> 00:01:32,096
Mikä on yksi etu
linkitetty lista luultavasti?

36
00:01:32,096 --> 00:01:32,950
>> Yleisö: lisäys.

37
00:01:32,950 --> 00:01:33,908
>> DAVID MALAN: lisäys.

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

39
00:01:34,155 --> 00:01:35,196
Mitä tarkoitat?

40
00:01:35,196 --> 00:01:37,872
>> Yleisö: missä tahansa
Lista [kuultavissa].

41
00:01:37,872 --> 00:01:38,770
>> DAVID MALAN: Hyvä.

42
00:01:38,770 --> 00:01:42,090
Joten voit lisätä elementti missä
Haluatko keskellä lista

43
00:01:42,090 --> 00:01:45,490
ilman shuffle mitään,
jonka solmimme, meidän lajittelu

44
00:01:45,490 --> 00:01:47,630
keskusteluja, ei ole
välttämättä hyvä asia,

45
00:01:47,630 --> 00:01:51,200
koska se vie aikaa itse liikkumaan
kaikki nämä ihmiset vasemmalle tai oikealle.

46
00:01:51,200 --> 00:01:55,540
Ja niin on linkitetty lista, voit
vain jakaa kanssa malloc, uusi solmu,

47
00:01:55,540 --> 00:01:58,385
ja sitten päivittää pari
pointers-- kaksi, kolme toimintaa max--

48
00:01:58,385 --> 00:02:01,480
ja pystymme korttipaikkaan joku
kaikkialle listaan.

49
00:02:01,480 --> 00:02:03,550
>> Mitä muuta oli edullinen
noin linkitetyn listan?

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

51
00:02:04,980 --> 00:02:05,659
Joo?

52
00:02:05,659 --> 00:02:06,534
>> Yleisö: [kuulumaton]

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

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

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

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

57
00:02:11,090 --> 00:02:12,070
Se on todella dynaaminen.

58
00:02:12,070 --> 00:02:15,100
Ja että et ole syyllistyneet,
etukäteen, jossain määrämittaisiksi

59
00:02:15,100 --> 00:02:18,750
kimpale muistia, kuin olisit
sen kanssa array, ylösalaisin joista

60
00:02:18,750 --> 00:02:22,455
on, että voit jakaa solmut vain
kysyntä käyttäen siten vain niin paljon tilaa

61
00:02:22,455 --> 00:02:23,330
kuin todella tarvitset.

62
00:02:23,330 --> 00:02:26,830
Toisin array, saatat
vahingossa jakaa liian vähän.

63
00:02:26,830 --> 00:02:28,871
Ja sitten se vain menee
olla kipua niskassa

64
00:02:28,871 --> 00:02:32,440
kohdentaa uudelleen uuteen isompi joukko, kopioida
kaikki yli, vapaa vanha array,

65
00:02:32,440 --> 00:02:33,990
ja sitten siirtyä yrityksestäsi.

66
00:02:33,990 --> 00:02:37,479
Tai pahempaa, saatat jakaa tavalla
enemmän muistia kuin todella tarvitset,

67
00:02:37,479 --> 00:02:40,520
ja niin olet menossa on hyvin
harvaan asutuilla array, niin sanotusti.

68
00:02:40,520 --> 00:02:44,350
>> Joten liittyy luettelo, antaa sinulle nämä
edut dynaamisuus ja joustavuus

69
00:02:44,350 --> 00:02:46,080
kanssa lisäyksiä ja poistoja.

70
00:02:46,080 --> 00:02:48,000
Mutta varmasti on oltava maksettu hinta.

71
00:02:48,000 --> 00:02:50,000
Itse asiassa, yksi teemoista
tutkitaan tietokilpailu nolla

72
00:02:50,000 --> 00:02:52,430
oli pari kompromisseja
olemme nähneet tähän mennessä.

73
00:02:52,430 --> 00:02:56,161
Joten mitä maksettu hinta tai
haittapuoli linkitetyn listan?

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

75
00:02:56,660 --> 00:02:57,560
>> Yleisö: Ei random access.

76
00:02:57,560 --> 00:02:58,809
>> DAVID MALAN: o random access.

77
00:02:58,809 --> 00:02:59,540
Mutta kuka välittää?

78
00:02:59,540 --> 00:03:01,546
Random access ei kuulosta pakottavia.

79
00:03:01,546 --> 00:03:02,421
>> Yleisö: [kuulumaton]

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

81
00:03:04,865 --> 00:03:05,740
DAVID MALAN: Aivan.

82
00:03:05,740 --> 00:03:07,580
Jos haluat olla
tietty algorithm--

83
00:03:07,580 --> 00:03:10,170
ja haluaisin todella ehdottaa
Binäärihaku erityisesti, joka

84
00:03:10,170 --> 00:03:12,600
on yksi olemme käyttäneet melko bit--
Jos sinulla ei ole satunnainen pääsy,

85
00:03:12,600 --> 00:03:15,516
et voi tehdä näin yksinkertainen aritmeettinen
löytää kuin keskimmäinen elementti

86
00:03:15,516 --> 00:03:16,530
ja hyppää oikeutta siihen.

87
00:03:16,530 --> 00:03:20,239
Voit sen sijaan on aloitettava ensimmäisestä
elementti ja lineaarisesti etsi vasemmalta

88
00:03:20,239 --> 00:03:22,780
oikealle, jos haluat löytää
keski tai muita tekijöitä.

89
00:03:22,780 --> 00:03:24,410
>> Yleisö: Se varmaan vie enemmän muistia.

90
00:03:24,410 --> 00:03:25,040
>> DAVID MALAN: vaatii paljon muistia.

91
00:03:25,040 --> 00:03:27,464
Missä on täydentävä
maksaa tulevat muistiin?

92
00:03:27,464 --> 00:03:28,339
>> Yleisö: [kuulumaton]

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

94
00:03:32,566 --> 00:03:33,440
DAVID MALAN: Aivan.

95
00:03:33,440 --> 00:03:35,679
Tässä tapauksessa täällä, meillä oli
linkitetty lista kokonaislukuja,

96
00:03:35,679 --> 00:03:37,470
ja silti me kaksinkertaistaa
muistin määrä

97
00:03:37,470 --> 00:03:39,680
Tarvitsemme mukaan myös niiden tallentamista viitteitä.

98
00:03:39,680 --> 00:03:42,090
Nyt vähemmän iso juttu kuin
sinun structs saada suurempi

99
00:03:42,090 --> 00:03:45,320
ja olet ei tallenneta numero vaan
ehkä opiskelija tai jokin muu esine.

100
00:03:45,320 --> 00:03:46,880
Mutta kohta varmasti pysyy.

101
00:03:46,880 --> 00:03:49,421
Ja niin useita toimintoja
linkitettyihin luettelot kutsuttiin

102
00:03:49,421 --> 00:03:50,570
oli iso O n- lineaarinen.

103
00:03:50,570 --> 00:03:54,730
Asiat kuten asettamisen tai haku
tai poistetaan, jos elementti

104
00:03:54,730 --> 00:03:57,720
sattui olemaan aivan lopussa
lista onko se lajitellaan tai ei.

105
00:03:57,720 --> 00:04:01,167
>> Joskus saatat saada onnekas ja
niin alarajat näiden toimintojen

106
00:04:01,167 --> 00:04:04,250
voi olla vakio aikaa, jos olet
aina katsot ensimmäinen elementti,

107
00:04:04,250 --> 00:04:05,070
esimerkiksi.

108
00:04:05,070 --> 00:04:09,360
Mutta loppujen lopuksi, me lupasimme
saavuttaa Graalin

109
00:04:09,360 --> 00:04:12,630
tietorakenteita, tai
Joissakin approksimaatio,

110
00:04:12,630 --> 00:04:14,290
Poiketen vakioaikaisia.

111
00:04:14,290 --> 00:04:17,579
Voisimmeko löytää osia tai lisätä elementtejä
tai poistaa elementit listasta?

112
00:04:17,579 --> 00:04:19,059
Tulemme näkemään varsin pian.

113
00:04:19,059 --> 00:04:21,100
Ja käy ilmi, että yksi
mekanismien olemme

114
00:04:21,100 --> 00:04:23,464
aio alkaa käyttää tänään,
vuotuinen käyttö p asettaa viisi,

115
00:04:23,464 --> 00:04:24,630
on oikeastaan ​​aika tuttu.

116
00:04:24,630 --> 00:04:27,430
Esimerkiksi, jos tämä on nippu
tentti kirjoja, joista kukin

117
00:04:27,430 --> 00:04:29,660
on opiskelijan ensimmäinen
ja sukunimi sitä,

118
00:04:29,660 --> 00:04:31,820
ja minä noutaa ne
lopussa tentti,

119
00:04:31,820 --> 00:04:33,746
ja he ovat kaikki melko
paljon satunnaisessa järjestyksessä,

120
00:04:33,746 --> 00:04:36,370
ja haluamme edetä lajittelu
näitä kokeita niin, että kun arvostellaan

121
00:04:36,370 --> 00:04:38,661
se on vain paljon helpompaa ja
nopeampi luovuttamaan ne takaisin ulos

122
00:04:38,661 --> 00:04:40,030
opiskelijoille aakkosjärjestyksessä.

123
00:04:40,030 --> 00:04:42,770
Mitä vaistosi olla
varten kasa tentit näin?

124
00:04:42,770 --> 00:04:45,019
>> No, jos olet kuten minä, olet
voisi nähdä, että tämä on m,

125
00:04:45,019 --> 00:04:48,505
joten aion tavallaan toteuttaa tämä,
jos tämä on minun taulukko tai minun kerroksessa, jossa

126
00:04:48,505 --> 00:04:50,650
Olen leviää asioita
out-- tai minun array really--

127
00:04:50,650 --> 00:04:52,210
Saatan laittaa kaikki Ms siellä.

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

129
00:04:52,710 --> 00:04:55,020
Tässä A., joten saatan
laittaa Kuten täällä.

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

131
00:04:55,520 --> 00:04:57,980
Tässä toinen A. Aion
laittaa, että tänne.

132
00:04:57,980 --> 00:05:02,490
Tässä Z. Tässä on toinen M. Ja niin
Voisin alkaa tehdä kasoittain näin.

133
00:05:02,490 --> 00:05:06,620
Ja sitten ehkä menisin myöhemmin
ja tavallaan hyvin nitpicky-ly Lajittele

134
00:05:06,620 --> 00:05:07,710
yksittäiset paalut.

135
00:05:07,710 --> 00:05:11,300
Mutta kohta on haluan tarkastella
otossa, että olen kädellä

136
00:05:11,300 --> 00:05:14,016
ja haluaisin tehdä joitakin lasketaan
Päätös perustuu siihen, että tulo.

137
00:05:14,016 --> 00:05:15,640
Jos se alkaa, laita se tuonne.

138
00:05:15,640 --> 00:05:18,980
Jos se alkaa Z, laita se päälle
siellä, ja kaikkea siltä väliltä.

139
00:05:18,980 --> 00:05:22,730
>> Joten tämä on tekniikka, joka on
yleisesti tunnettu hashing-- H-A-S-H--

140
00:05:22,730 --> 00:05:26,550
mikä tarkoittaa yleensä ottaen niin
tulo ja käyttää sitä panos laskea

141
00:05:26,550 --> 00:05:30,940
arvo, yleensä määrä, ja että
numero on indeksinä varastointi

142
00:05:30,940 --> 00:05:32,260
kontti, kuten array.

143
00:05:32,260 --> 00:05:35,490
Eli toisin sanoen, voisin olla
tiivistefunktiota, kuten minä päähäni,

144
00:05:35,490 --> 00:05:37,940
että jos näen jonkun
nimi, joka alkaa,

145
00:05:37,940 --> 00:05:40,190
Aion kartan
nollaan päähäni.

146
00:05:40,190 --> 00:05:44,160
Ja jos näen jonkun kanssa Z, olen
menossa kartta, 25 päähäni

147
00:05:44,160 --> 00:05:46,220
ja sitten laittaa sen osaksi
viimeksi eniten kasaan.

148
00:05:46,220 --> 00:05:50,990
>> Nyt, jos ajattelee ei aivoni
mutta C-ohjelma, mitä numeroita voisi

149
00:05:50,990 --> 00:05:53,170
voit luottaa saavuttaa saman tuloksen?

150
00:05:53,170 --> 00:05:55,594
Toisin sanoen, jos
oli ASCII-merkki,

151
00:05:55,594 --> 00:05:57,510
miten voit määrittää
mitä ämpäri laittaa sen?

152
00:05:57,510 --> 00:05:59,801
Et luultavasti halua
laita se ämpäriin 65, joka

153
00:05:59,801 --> 00:06:01,840
olisi sama kuin tuolla
ilman hyvää syytä.

154
00:06:01,840 --> 00:06:04,320
Missä haluat laittaa
kannalta sen ASCII-arvo?

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

156
00:06:05,600 --> 00:06:08,920
Missä haluat tehdä sen ASCII
arvo keksiä älykkäämpiä ämpäri

157
00:06:08,920 --> 00:06:09,480
laittaa sen?

158
00:06:09,480 --> 00:06:10,206
>> Yleisö: Miinus A.

159
00:06:10,206 --> 00:06:10,956
>> DAVID MALAN: Joo.

160
00:06:10,956 --> 00:06:13,190
Joten miinus tai miinus
erityisesti 65, jos se on

161
00:06:13,190 --> 00:06:18,240
pääoman A. Tai 98, jos
se on pieniä.

162
00:06:18,240 --> 00:06:21,300
Ja jotta voisimme hyvin
yksinkertaisesti ja hyvin laskennallisesti,

163
00:06:21,300 --> 00:06:23,260
laittaa jotain sankoon niin.

164
00:06:23,260 --> 00:06:26,010
Joten se kääntyy pois me itse tehdä
Tämän samoin vaikka tietokilpailuja.

165
00:06:26,010 --> 00:06:29,051
>> Niin saatatte muistaa sinua ympyröity sinun
opetus kaverin nimi kannessa.

166
00:06:29,051 --> 00:06:32,270
Ja TF: n nimet järjestettiin
näihin sarakkeisiin aakkosjärjestyksessä

167
00:06:32,270 --> 00:06:34,400
hyvin, uskokaa tai älkää,
kun kaikki 80 plus meistä

168
00:06:34,400 --> 00:06:37,800
sai yhdessä muiden yö palkkaluokkaan,
viimeinen askel lajitteluun prosessi

169
00:06:37,800 --> 00:06:41,830
on hash tietokilpailuja isoon
tilaa lattian [äänetön]

170
00:06:41,830 --> 00:06:45,110
ja antaa kaikkien tietokilpailuja ulos
täsmälleen siinä järjestyksessä niiden TF: n

171
00:06:45,110 --> 00:06:47,700
nimet kannessa, koska
niin se on paljon helpompaa meille

172
00:06:47,700 --> 00:06:51,290
etsiä läpi käyttäen lineaarista
etsiä tai jonkinlainen nokkeluutta

173
00:06:51,290 --> 00:06:54,050
varten TF löytää hänen tai
oppilaidensa tietokilpailuja.

174
00:06:54,050 --> 00:06:56,060
>> Joten tämä ajatus hashing
että näet on

175
00:06:56,060 --> 00:07:00,520
melko voimakas on oikeastaan ​​aika
arkipäiväinen ja erittäin intuitiivinen,

176
00:07:00,520 --> 00:07:03,000
paljon kuin ehkä jakaa ja
Conquer oli viikolla nolla.

177
00:07:03,000 --> 00:07:05,250
I nopeasti eteenpäin hackathon
pari vuotta sitten.

178
00:07:05,250 --> 00:07:08,040
Tämä oli Zamyla ja pari
muu henkilöstö tervehdys opiskelijoita

179
00:07:08,040 --> 00:07:09,030
kuin he tulivat.

180
00:07:09,030 --> 00:07:12,680
Ja meillä oli koko joukko taitto
pöydät siellä nimilappuja.

181
00:07:12,680 --> 00:07:15,380
Ja meillä oli nimilappuja järjestäytyneen
kanssa kuten Kuten tuolla

182
00:07:15,380 --> 00:07:16,690
ja ZS tuolla.

183
00:07:16,690 --> 00:07:20,350
Ja niin yksi TF: iä erittäin taitavasti
Kirjoitin tämän, koska ohjeet

184
00:07:20,350 --> 00:07:21,030
päivä.

185
00:07:21,030 --> 00:07:24,480
Ja viikolla 12 lukukauden tämän
kaikki oli täysin järkevä ja kaikille

186
00:07:24,480 --> 00:07:25,310
tiesi, mitä tehdä.

187
00:07:25,310 --> 00:07:27,900
Mutta milloin olet
jonossa samalla tavalla,

188
00:07:27,900 --> 00:07:30,272
olet täytäntöönpanosta
Sama ajatus on hash.

189
00:07:30,272 --> 00:07:31,730
Joten virallistaa sitä vähän.

190
00:07:31,730 --> 00:07:32,890
Tässä on joukko.

191
00:07:32,890 --> 00:07:36,820
Se vetää hieman
Laaja vain kuvata, visuaalisesti,

192
00:07:36,820 --> 00:07:38,920
että voisimme laittaa jouset
jotain tällaista.

193
00:07:38,920 --> 00:07:41,970
Ja tämä joukko on
selvästi koko 26 yhteensä.

194
00:07:41,970 --> 00:07:43,935
Ja asia on nimeltään
pöytä mielivaltaisesti.

195
00:07:43,935 --> 00:07:48,930
Mutta tämä on vain taiteilijan luovutuksia
mitä hajautustaulun voisi olla.

196
00:07:48,930 --> 00:07:52,799
>> Niin hash table nyt on menossa
olla korkeampi tietorakennetta.

197
00:07:52,799 --> 00:07:54,840
Lopussa päivä
olemme tulleet, että olet

198
00:07:54,840 --> 00:07:58,700
voi toteuttaa tiiviste, joka
on paljon, kuten check-in line

199
00:07:58,700 --> 00:08:02,059
klo hackathon paljon kuin tämä
taulukko käyttää lajitteluun tenttikirjat.

200
00:08:02,059 --> 00:08:03,850
Mutta tiiviste on
tavallaan tämä korkean tason

201
00:08:03,850 --> 00:08:08,250
käsite, joka voisi käyttää array
alla huppu toteuttaa se,

202
00:08:08,250 --> 00:08:11,890
tai se voisi käyttää pituus luettelosta, tai jopa
ehkä joitakin muita tietorakenteita.

203
00:08:11,890 --> 00:08:15,590
Ja nyt se on theme-- ottaminen
jotkut näistä keskeisistä aineosista

204
00:08:15,590 --> 00:08:18,310
kuten array ja tämä rakennus
Estä nyt on pitkä lista

205
00:08:18,310 --> 00:08:21,740
ja nähdä, mitä muuta voimme rakentaa
päälle ne, kuten ainesosat

206
00:08:21,740 --> 00:08:26,550
osaksi resepti, tehdä enemmän ja enemmän
mielenkiintoista ja hyödyllistä lopulliset tulokset.

207
00:08:26,550 --> 00:08:28,680
>> Joten tiiviste
voisimme toteuttaa sen

208
00:08:28,680 --> 00:08:32,540
muistiin kuvallisesti näin, mutta
Kuinka se voisi todella olla koodattu ylös?

209
00:08:32,540 --> 00:08:33,789
No, ehkä yksinkertaisesti on tämä.

210
00:08:33,789 --> 00:08:38,270
Jos kapasiteettia kaikilla lippikset, on vain
Joissakin constant-- esimerkiksi 26,

211
00:08:38,270 --> 00:08:42,030
26 kirjainta alphabet--
Saatan soittaa minun muuttuvan pöytä,

212
00:08:42,030 --> 00:08:45,630
ja voisin väittää, että aion
laita char tähtiä siellä, tai merkkijono.

213
00:08:45,630 --> 00:08:49,880
Niin se on niin yksinkertaista kuin tämä, jos
halua toteuttaa hash table.

214
00:08:49,880 --> 00:08:51,490
Ja vielä, tämä on oikeastaan ​​vain joukko.

215
00:08:51,490 --> 00:08:53,198
Mutta jälleen kerran, hash
pöytä on nyt mitä me will

216
00:08:53,198 --> 00:08:57,470
soita abstrakti tietotyyppi, joka on juuri
eräänlainen käsitteellinen kerrospukeutuminen päälle

217
00:08:57,470 --> 00:09:00,780
jotain arkisempi
nyt haluaisin array.

218
00:09:00,780 --> 00:09:02,960
>> Nyt, miten menemme
noin ongelmien ratkaisemiseen?

219
00:09:02,960 --> 00:09:06,980
No, aikaisemmin minulla oli ylellisyyttä
ottaa tarpeeksi pöytätilaa täällä

220
00:09:06,980 --> 00:09:09,460
niin että voisin laittaa
tietokilpailuja tahansa halusin.

221
00:09:09,460 --> 00:09:10,620
Niin voisi mennä täällä.

222
00:09:10,620 --> 00:09:12,100
ZS voisi mennä täällä.

223
00:09:12,100 --> 00:09:13,230
MS voisi mennä täällä.

224
00:09:13,230 --> 00:09:14,740
Ja sitten minulla oli ylimääräistä tilaa.

225
00:09:14,740 --> 00:09:18,740
Mutta tämä on vähän huijata oikeus
nyt, koska tämä taulukko, jos olen todella

226
00:09:18,740 --> 00:09:22,720
ajatellut sitä array, on vain
tulee olemaan noin kiinteä koko.

227
00:09:22,720 --> 00:09:25,380
>> Joten teknisesti, jos vedän
jopa toisen opiskelijan tietokilpailu

228
00:09:25,380 --> 00:09:28,490
ja katso, oi, tämä henkilö
nimi alkaa myös,

229
00:09:28,490 --> 00:09:30,980
Olen sellainen halua laittaa sen sinne.

230
00:09:30,980 --> 00:09:34,740
Mutta heti kun laitoin sen sinne, jos
Tämän taulukon todellakin edustaa joukko,

231
00:09:34,740 --> 00:09:37,840
Aion olla ensisijaisia ​​tai clobbering
kuka tämä opiskelijan tietokilpailu on.

232
00:09:37,840 --> 00:09:38,340
Oikea?

233
00:09:38,340 --> 00:09:41,972
Jos tämä on joukko, vain yksi asia voi
mennä kussakin näistä soluista tai elementtejä.

234
00:09:41,972 --> 00:09:43,680
Ja niin olen sellainen on
poimia ja valita.

235
00:09:43,680 --> 00:09:45,735
>> Nyt aikaisemmin olen sellainen
huijattu ja teki tämän tai I

236
00:09:45,735 --> 00:09:47,526
vain sellainen pinottu
ne toistensa päälle.

237
00:09:47,526 --> 00:09:49,170
Mutta se ei tule lentää koodin.

238
00:09:49,170 --> 00:09:52,260
Joten jos voisin laittaa
Toinen opiskelija, jonka nimi

239
00:09:52,260 --> 00:09:54,964
on jos kaikki mitä oli on tämä
käytettävissä pöytätilaa?

240
00:09:54,964 --> 00:09:57,880
Ja olen käyttänyt kolme lähtö ja se
Näyttää siltä, ​​että on vain muutama muu.

241
00:09:57,880 --> 00:09:58,959
Mitä voisit tehdä?

242
00:09:58,959 --> 00:09:59,834
Yleisö: [kuulumaton]

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

244
00:10:00,565 --> 00:10:01,315
DAVID MALAN: Joo.

245
00:10:01,315 --> 00:10:02,370
Ehkä haluan vain pitää asiat yksinkertaisina.

246
00:10:02,370 --> 00:10:02,660
Oikea?

247
00:10:02,660 --> 00:10:04,243
Se ei sovi, jos haluan laittaa sen.

248
00:10:04,243 --> 00:10:07,450
Joten aion laittaa sen
teknisesti jossa B menisi.

249
00:10:07,450 --> 00:10:09,932
Nyt tietenkin olen alkanut
maalata itseni nurkkaan.

250
00:10:09,932 --> 00:10:11,890
Jos saan opiskelija
jonka nimi on todella B,

251
00:10:11,890 --> 00:10:14,840
Nyt B aiotaan siirtää hieman
eteenpäin, niin voisi tapahtua, juu,

252
00:10:14,840 --> 00:10:17,530
jos tämä on B, nyt se on mennä tänne.

253
00:10:17,530 --> 00:10:20,180
>> Ja niin tämä hyvin nopeasti
voisi muodostua ongelmalliseksi,

254
00:10:20,180 --> 00:10:23,850
mutta se on tekniikka, joka todella
kutsutaan lineaarinen tunnustelun

255
00:10:23,850 --> 00:10:26,650
jolloin juuri harkita
array olla pitkin linjaa.

256
00:10:26,650 --> 00:10:29,680
Ja juuri sellainen anturi tai
tarkastaa jokaisen saatavilla elementin

257
00:10:29,680 --> 00:10:31,360
etsii käytettävissä paikan päällä.

258
00:10:31,360 --> 00:10:34,010
Ja heti kun huomaat
yksi, voit pudottaa sen sinne.

259
00:10:34,010 --> 00:10:38,390
>> Nyt hinta on nyt maksettu
Tämän ratkaisu on mitä?

260
00:10:38,390 --> 00:10:41,300
Meillä on kiinteä koko array,
ja kun asetan nimet

261
00:10:41,300 --> 00:10:44,059
siihen, ainakin aluksi, mitä
käyntiaika lisäys

262
00:10:44,059 --> 00:10:46,350
laskemisesta opiskelijoiden
tietokilpailuja oikeaan kauhat?

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

264
00:10:48,710 --> 00:10:50,002
Big O mitä?

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

266
00:10:51,147 --> 00:10:52,480
DAVID MALAN: Kuulin ison O n.

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

268
00:10:53,530 --> 00:10:54,300
Ei pidä paikkaansa.

269
00:10:54,300 --> 00:10:56,490
Mutta me kiusata toisistaan
miksi vain hetken.

270
00:10:56,490 --> 00:10:57,702
Mitä muuta se voisi olla?

271
00:10:57,702 --> 00:10:58,755
>> Yleisö: [kuulumaton]

272
00:10:58,755 --> 00:11:00,380
DAVID MALAN: Ja anna minun tehdä se visuaalisesti.

273
00:11:00,380 --> 00:11:04,720
Joten Oletetaan tämä on kirjain S.

274
00:11:04,720 --> 00:11:05,604
>> Yleisö: Se on yksi.

275
00:11:05,604 --> 00:11:06,520
DAVID MALAN: Se on yksi.

276
00:11:06,520 --> 00:11:06,710
Oikea?

277
00:11:06,710 --> 00:11:08,950
Tämä on joukko, joka
tarkoittaa, että olemme random access.

278
00:11:08,950 --> 00:11:11,790
Ja jos ajattelemme tämän
nollaksi ja tämä 25,

279
00:11:11,790 --> 00:11:13,800
ja ymmärrämme, että
Voi, tässä on minun tulo S,

280
00:11:13,800 --> 00:11:16,350
Voin varmasti muuntaa
S, ASCII-merkki,

281
00:11:16,350 --> 00:11:18,540
vastaavaksi määräksi
nollan ja 25

282
00:11:18,540 --> 00:11:20,910
ja sitten heti
laita se minne se kuuluu.

283
00:11:20,910 --> 00:11:26,120
>> Mutta tietenkin, heti kun pääsen
toinen henkilö jonka nimi on A tai B tai C

284
00:11:26,120 --> 00:11:29,300
lopulta, jos olen käyttänyt
lineaarinen hyvää minun ratkaisu,

285
00:11:29,300 --> 00:11:31,360
käyntiaika
lisäys pahimmassa tapauksessa

286
00:11:31,360 --> 00:11:33,120
on todella menossa hajauttaa, mitä?

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

288
00:11:34,270 --> 00:11:36,045
Ja en kuullut sitä täällä
oikein varhain.

289
00:11:36,045 --> 00:11:36,920
Yleisö: [kuulumaton]

290
00:11:36,920 --> 00:11:41,620
DAVID MALAN: Niin se on n todellakin kerran
sinulla on riittävän suuri tietokokonaisuus.

291
00:11:41,620 --> 00:11:44,410
Niin, toisaalta, jos
matriisisi on tarpeeksi iso

292
00:11:44,410 --> 00:11:48,287
ja tietosi on niukkaa riitä,
saat tämän kauniin vakioaikaisia.

293
00:11:48,287 --> 00:11:50,620
Mutta heti kun alkaa
yhä enemmän ja enemmän elementtejä,

294
00:11:50,620 --> 00:11:53,200
ja juuri tilastollisesti saat
enemmän ihmisiä kirjaimella

295
00:11:53,200 --> 00:11:56,030
Nimensä tai kirjain
B, se olisi voinut olla

296
00:11:56,030 --> 00:11:57,900
hajauttaa joksikin lineaarinen.

297
00:11:57,900 --> 00:11:59,640
Joten ei ole aivan täydellinen.

298
00:11:59,640 --> 00:12:00,690
Joten me voisimme tehdä paremmin?

299
00:12:00,690 --> 00:12:03,210
>> No, mikä oli meidän
ratkaisu ennen kun me

300
00:12:03,210 --> 00:12:06,820
haluavat olla enemmän dynamiikkaa kuin
jotain array sallittua?

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

302
00:12:08,085 --> 00:12:08,960
Yleisö: [kuulumaton]

303
00:12:08,960 --> 00:12:10,030
DAVID MALAN: Mitä me esitellä?

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

305
00:12:10,530 --> 00:12:11,430
Joten linkitetty lista.

306
00:12:11,430 --> 00:12:14,430
No, katsotaanpa mitä liittyy
lista voisi tehdä meille sijaan.

307
00:12:14,430 --> 00:12:17,630
No, minäpä ehdotan, että
piirtää kuvaa seuraavasti.

308
00:12:17,630 --> 00:12:19,620
Nyt tämä on erilainen
kuva esimerkki

309
00:12:19,620 --> 00:12:24,750
peräisin eri tekstiä, itse asiassa, että
on todellisuudessa käyttävät taulukon koko 31.

310
00:12:24,750 --> 00:12:28,220
Ja tämä kirjailija yksinkertaisesti
päätti hash jouset

311
00:12:28,220 --> 00:12:32,430
ei perustu henkilön nimet,
vaan perustuu niiden syntymäpäiviä.

312
00:12:32,430 --> 00:12:35,680
Riippumatta kuukauden, he tajunnut
jos olet syntynyt ensimmäinen kuukausi

313
00:12:35,680 --> 00:12:39,580
tai 31. kuukausi, kirjailija
tulee hash perustuu tähän arvoon,

314
00:12:39,580 --> 00:12:44,154
levittämiseksi nimiä ulos vähän
enemmän kuin vain 26 paikkoja voisi mahdollistaa.

315
00:12:44,154 --> 00:12:47,320
Ja ehkä se on hieman yhtenäisempi
kuin menossa aakkosina,

316
00:12:47,320 --> 00:12:50,236
koska tietenkin on luultavasti
enemmän ihmisiä maailmassa nimet

317
00:12:50,236 --> 00:12:54,020
jotka alkavat kuin varmasti
joitakin muita aakkosten kirjainta.

318
00:12:54,020 --> 00:12:56,380
Joten ehkä tämä on hieman
yhtenäisempi, olettaen

319
00:12:56,380 --> 00:12:58,640
tasainen jakauma
vauvojen yli kuukausi.

320
00:12:58,640 --> 00:12:59,990
>> Mutta, tietenkin, tämä on vielä epätäydellinen.

321
00:12:59,990 --> 00:13:00,370
Oikea?

322
00:13:00,370 --> 00:13:01,370
Meillä oli törmäyksiä.

323
00:13:01,370 --> 00:13:04,680
Useita ihmisiä tässä
tietorakenne ovat edelleen

324
00:13:04,680 --> 00:13:08,432
joilla on sama syntymäaika ainakin
olet riippumatta kuukaudessa.

325
00:13:08,432 --> 00:13:09,640
Mutta mitä on kirjailija tehnyt?

326
00:13:09,640 --> 00:13:13,427
No, näyttää siltä, ​​että meillä on joukko
vasemmalla puolella piirretty pystysuunnassa,

327
00:13:13,427 --> 00:13:15,010
mutta se on vain taiteilijan luovutuksia.

328
00:13:15,010 --> 00:13:18,009
Sillä ei ole väliä mihin suuntaan
piirtää array, se on silti array.

329
00:13:18,009 --> 00:13:20,225
Mikä on tämä joukko ilmeisesti?

330
00:13:20,225 --> 00:13:21,500
>> Yleisö: linkitetty lista.

331
00:13:21,500 --> 00:13:21,650
>> DAVID MALAN: Joo.

332
00:13:21,650 --> 00:13:23,490
Se näyttää siltä kuin se on
joukko linkitetty lista.

333
00:13:23,490 --> 00:13:26,490
Joten jälleen, että tässä vaiheessa järjestä
käyttää näitä tietorakenteiden nyt

334
00:13:26,490 --> 00:13:28,550
ainesosina lisää
mielenkiintoisia ratkaisuja,

335
00:13:28,550 --> 00:13:30,862
voit ehdottomasti ottaa
perusoikeuksien, kuten array,

336
00:13:30,862 --> 00:13:33,320
ja sitten ottaa jotain lisää
mielenkiintoinen kuten linkitetyn listan

337
00:13:33,320 --> 00:13:36,660
ja jopa yhdistää ne vielä
mielenkiintoisempaa tietorakenne.

338
00:13:36,660 --> 00:13:39,630
Ja todellakin, tämäkin olisi
kutsua tiiviste,

339
00:13:39,630 --> 00:13:42,610
jolloin matriisi on
todella tiiviste,

340
00:13:42,610 --> 00:13:45,600
mutta että tiiviste on
ketjut, niin sanotusti,

341
00:13:45,600 --> 00:13:50,220
joka voi kasvaa tai kutistua perusteella
alkioiden lukumäärä, jonka haluat lisätä.

342
00:13:50,220 --> 00:13:52,990
>> Nyt, vastaavasti, mikä on
käyntiaika nyt?

343
00:13:52,990 --> 00:13:58,030
Jos haluan lisätä joku
jonka syntymäpäivä on 31. lokakuuta

344
00:13:58,030 --> 00:13:59,040
mistä hän mennä?

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

346
00:14:00,530 --> 00:14:01,030
Selvä.

347
00:14:01,030 --> 00:14:02,819
Alareunaan, jossa lukee 31.

348
00:14:02,819 --> 00:14:03,610
Ja se on täydellinen.

349
00:14:03,610 --> 00:14:05,060
Se oli jatkuvaa aikaa.

350
00:14:05,060 --> 00:14:08,760
Mutta mitä jos me löytää joku muu
jonka syntymäpäivä on, katsotaanpa,

351
00:14:08,760 --> 00:14:10,950
Lokakuu, marraskuu, 31 joulukuu?

352
00:14:10,950 --> 00:14:12,790
Missä hän aikoo mennä?

353
00:14:12,790 --> 00:14:13,290
Sama juttu.

354
00:14:13,290 --> 00:14:13,970
Kaksivaiheinen kuitenkin.

355
00:14:13,970 --> 00:14:15,303
Se on jatkuvaa, vaikka ei ole sitä?

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

357
00:14:16,360 --> 00:14:16,860
Selvä.

358
00:14:16,860 --> 00:14:17,840
Tällä hetkellä se on.

359
00:14:17,840 --> 00:14:20,570
Mutta yleisessä tapauksessa,
enemmän ihmisiä lisäämme,

360
00:14:20,570 --> 00:14:23,790
toden- näköisesti, olemme menossa
saada enemmän ja enemmän törmäyksiä.

361
00:14:23,790 --> 00:14:26,820
>> Nyt tämä on vähän
parempi, koska se on teknisesti

362
00:14:26,820 --> 00:14:34,580
Nyt ketjut voisi olla
Pahimmassa tapauksessa kuinka kauan?

363
00:14:34,580 --> 00:14:38,890
Jos asetan n ihmiset tähän lisää
hienostunut tietorakenne, n ihmiset,

364
00:14:38,890 --> 00:14:41,080
pahimmassa tapauksessa se tulee olemaan n.

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

366
00:14:41,815 --> 00:14:43,332
>> Yleisö: Koska jos kaikki
on sama syntymäpäivä,

367
00:14:43,332 --> 00:14:44,545
he tulevat olemaan yksi rivi.

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

369
00:14:45,420 --> 00:14:47,480
Se saattaa olla hieman keinotekoinen,
mutta todella pahimmassa tapauksessa

370
00:14:47,480 --> 00:14:50,117
jos kaikilla on sama syntymäpäivä,
antanut tulot sinulla on,

371
00:14:50,117 --> 00:14:51,950
olet menossa on
massiivisesti pitkä ketju.

372
00:14:51,950 --> 00:14:54,241
Ja niin, voisi kutsua
tiiviste, mutta oikeastaan ​​se on

373
00:14:54,241 --> 00:14:56,810
vain massiivinen linkitetyn listan kanssa
paljon hukkaan tilaa.

374
00:14:56,810 --> 00:15:00,460
Mutta yleensä, jos oletamme, että
ainakin syntymäpäivät ovat uniform--

375
00:15:00,460 --> 00:15:01,750
ja se ei todennäköisesti ole.

376
00:15:01,750 --> 00:15:02,587
Teen että ylös.

377
00:15:02,587 --> 00:15:04,420
Mutta jos oletamme, sillä
vuoksi keskustelu

378
00:15:04,420 --> 00:15:07,717
että ne ovat, niin teoriassa, jos
tämä on pystysuora edustus

379
00:15:07,717 --> 00:15:11,050
array, hyvin sitten toivottavasti olet
menossa ketjuja, jotka ovat, tiedät,

380
00:15:11,050 --> 00:15:15,880
suunnilleen sama pituus, jossa kukin
Näiden edustaa kuukauden päivää.

381
00:15:15,880 --> 00:15:19,930
>> Nyt jos on 31 päivää kuukaudessa, kun taas
se tarkoittaa, että minun käyntiaika todella

382
00:15:19,930 --> 00:15:25,230
on iso O n yli 31, mikä
tuntuu paremmalta kuin lineaarinen.

383
00:15:25,230 --> 00:15:27,950
Mutta mikä oli yksi
sitoumukset pari viikkoa

384
00:15:27,950 --> 00:15:31,145
sitten kun se tuli ilmaisemiseen
ajoaika algoritmi?

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

386
00:15:33,450 --> 00:15:35,190
Vain vain katsoa korkean asteen termi.

387
00:15:35,190 --> 00:15:35,690
Oikea?

388
00:15:35,690 --> 00:15:37,400
31 on ehdottomasti hyödyllistä.

389
00:15:37,400 --> 00:15:39,610
Mutta tämä on silti iso O n.

390
00:15:39,610 --> 00:15:41,730
Mutta yksi teemoista
Ongelman asettaa viisi

391
00:15:41,730 --> 00:15:43,950
tulee olla
tunnustavat, että ehdottomasti,

392
00:15:43,950 --> 00:15:47,320
asymptoottisesti, teoreettisesti
tämä tietorakenne

393
00:15:47,320 --> 00:15:50,470
ei ole parempi kuin vain
yksi massiivinen linkitetty lista.

394
00:15:50,470 --> 00:15:53,550
Ja todellakin, pahimmassa tapauksessa, tämä
tiiviste voisi siirtää tuohon.

395
00:15:53,550 --> 00:15:57,620
>> Mutta todellisessa maailmassa, jossa meille ihmisille
että omat Macit tai PC tai mitä tahansa

396
00:15:57,620 --> 00:16:01,240
ja ovat käynnissä reaalimaailman
ohjelmisto reaalimaailman data,

397
00:16:01,240 --> 00:16:03,260
mikä algoritmi aiotte mieluummin?

398
00:16:03,260 --> 00:16:09,180
Joka kestää pää vaiheiden tai
joka kestää n jaettuna 31 vaiheet

399
00:16:09,180 --> 00:16:12,900
löytää joitakin osa tiedoista tai
etsiä joitakin tietoja?

400
00:16:12,900 --> 00:16:16,580
Tarkoitan, ehdottomasti 31 merkkeihin
ero todellisessa maailmassa.

401
00:16:16,580 --> 00:16:18,540
Se on 31 kertaa nopeampi.

402
00:16:18,540 --> 00:16:20,880
Ja me ihmiset olemme varmasti
menossa arvostaa sitä.

403
00:16:20,880 --> 00:16:23,004
>> Joten ymmärtää kahtiajako
siellä välillä todella

404
00:16:23,004 --> 00:16:25,920
puhumme asioista teoreettisesti
ja asymptoottisesti joka varmasti

405
00:16:25,920 --> 00:16:28,760
on arvoa olemme nähneet,
mutta todellisessa maailmassa,

406
00:16:28,760 --> 00:16:32,930
Jos välität vain tekemällä
ihmisen onnelliseksi yleisiä tuloa,

407
00:16:32,930 --> 00:16:36,010
saatat hyvinkin haluta hyväksyä
että, kyllä, tämä on lineaarinen,

408
00:16:36,010 --> 00:16:38,360
mutta se on 31 kertaa nopeampi
kuin lineaarinen voisi olla.

409
00:16:38,360 --> 00:16:41,610
Ja vielä parempaa, meillä ei vain tarvitse
tehdä jotain mielivaltaista, kuten syntymäpäivä,

410
00:16:41,610 --> 00:16:44,030
voisimme viettää hieman
enemmän aikaa ja nokkeluutta

411
00:16:44,030 --> 00:16:47,140
ja miettiä, mitä voisimme tehdä,
annetaan henkilön nimi ja ehkä

412
00:16:47,140 --> 00:16:50,130
niiden syntymäaika yhdistää nämä
ainesosat selvittää jotain

413
00:16:50,130 --> 00:16:52,720
että on todella enemmän
yhtenäinen ja vähemmän jaggy,

414
00:16:52,720 --> 00:16:56,250
niin sanotusti kuin tämä kuva
Tällä hetkellä ehdottaa, että se voisi olla.

415
00:16:56,250 --> 00:16:57,750
Miten voisimme toteuttaa tämän koodin?

416
00:16:57,750 --> 00:17:00,280
No, minäpä ehdotan, että
vain lainata syntaksin me olet

417
00:17:00,280 --> 00:17:01,799
käytetty pari kertaa näin pitkälle.

418
00:17:01,799 --> 00:17:03,590
Ja aion määritellä
solmu, joka taas

419
00:17:03,590 --> 00:17:06,812
on yleisnimi vain joitakin
kontti joidenkin tietojen rakenne.

420
00:17:06,812 --> 00:17:09,020
Aion ehdottaa, että
merkkijono on menossa sinne.

421
00:17:09,020 --> 00:17:11,369
Mutta me aiomme aloitat
ne apupyörät pois nyt.

422
00:17:11,369 --> 00:17:13,230
>> Ei enää CS50 kirjasto
todella, jos et halua

423
00:17:13,230 --> 00:17:15,230
käyttää sitä oman lopullisen
hanke, joka on hieno,

424
00:17:15,230 --> 00:17:18,569
mutta nyt olemme menossa vetämään takaisin
verho ja sanovat, että se on vain char tähti.

425
00:17:18,569 --> 00:17:22,069
Joten sana siellä tulee olemaan
henkilön nimestä.

426
00:17:22,069 --> 00:17:25,079
Ja nyt minulla on linkki
Tässä seuraavalle solmulle

427
00:17:25,079 --> 00:17:28,170
niin, että nämä ovat
kukin solmuista

428
00:17:28,170 --> 00:17:30,950
ketjussa, mahdollisesti,
linkitetyn listan.

429
00:17:30,950 --> 00:17:34,090
>> Ja nyt miten voin julistaa
tiiviste itse?

430
00:17:34,090 --> 00:17:36,660
Miten julistan koko rakenne?

431
00:17:36,660 --> 00:17:40,960
No, oikeastaan, aivan kuten käytin osoitin
vain ensimmäinen osa listasta

432
00:17:40,960 --> 00:17:44,510
ennen, samalla voin vain sanoa
Tarvitsen vain joukko osoittimia

433
00:17:44,510 --> 00:17:46,270
toteuttaa tätä koko tiiviste.

434
00:17:46,270 --> 00:17:49,484
Aion olla array
kutsutaan pöydän tiiviste.

435
00:17:49,484 --> 00:17:50,900
Se tulee olla koko kapasiteetin.

436
00:17:50,900 --> 00:17:52,525
Se, miten monta elementtiä mahtuu siihen.

437
00:17:52,525 --> 00:17:56,180
Ja jokainen niistä tässä
array tulee olemaan solmu tähti.

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

439
00:17:56,810 --> 00:18:00,160
No, kohti tätä kuvaa, mitä olen
täytäntöönpanosta tiiviste kuin

440
00:18:00,160 --> 00:18:04,330
tehokkaasti alussa on vain
Tämän array että olemme vetää pystysuoraan,

441
00:18:04,330 --> 00:18:06,820
jokainen jonka neliöt
edustaa osoitin.

442
00:18:06,820 --> 00:18:09,170
Että ne, jotka ovat viiltää
niiden kautta ovat vain null.

443
00:18:09,170 --> 00:18:11,410
Ja ne, jotka ovat
nuolet menossa oikeaan

444
00:18:11,410 --> 00:18:16,140
ovat todellisia viitteitä todellinen solmuja,
ergo alku liittyy luettelo.

445
00:18:16,140 --> 00:18:19,050
>> Joten tässä sitten on, kuinka voisimme
toteuttaa tiiviste, joka

446
00:18:19,050 --> 00:18:21,580
toteuttaa erillinen ketjutus.

447
00:18:21,580 --> 00:18:22,840
Nyt me voisimme tehdä paremmin?

448
00:18:22,840 --> 00:18:25,632
Okei Lupasin viime kerralla, että
voisimme saavuttaa vakioaikaisia.

449
00:18:25,632 --> 00:18:27,381
Ja olen sellainen annoin sinulle
vakio aikaa täällä,

450
00:18:27,381 --> 00:18:29,850
mutta sanoi sitten ei oikeastaan
vakio aikaa, koska se on edelleen

451
00:18:29,850 --> 00:18:31,890
riippuvainen koko
useita tekijöitä

452
00:18:31,890 --> 00:18:34,500
olet kautta ne
tietorakenteen.

453
00:18:34,500 --> 00:18:35,980
Mutta kai me teimme tämän.

454
00:18:35,980 --> 00:18:39,550
Anna minun mennä takaisin ruudun tänne.

455
00:18:39,550 --> 00:18:44,520
Saanen myös heijastaa tätä täällä, kirkas
näyttö, ja kai tein tämän.

456
00:18:44,520 --> 00:18:49,300
Kai halusin lisätä nimen
Daven on minun tietorakenne.

457
00:18:49,300 --> 00:18:52,100
>> Joten haluan lisätä merkkijono
Daven osaksi tietorakennetta.

458
00:18:52,100 --> 00:18:54,370
Mitä jos en käytä
tiiviste, mutta käytän

459
00:18:54,370 --> 00:18:56,980
jotain, joka on enemmän puumainen
kuten sukupuu, jossa

460
00:18:56,980 --> 00:18:59,670
sinulla on root
top ja sitten solmut ja lehdet

461
00:18:59,670 --> 00:19:01,440
jotka menevät alaspäin ja ulospäin.

462
00:19:01,440 --> 00:19:04,450
Oletetaan sitten, että minä
haluat lisätä Daven n

463
00:19:04,450 --> 00:19:06,430
siitä, mitä on tällä hetkellä tyhjä lista.

464
00:19:06,430 --> 00:19:09,780
Aion tehdä seuraavaa: olen
luomassa solmuun tässä perheessä

465
00:19:09,780 --> 00:19:15,170
puumainen tietorakenne, joka näyttää
vähän kuin tämä, joista kukin

466
00:19:15,170 --> 00:19:19,640
suorakaide on, sanokaamme,
nyt 26 elementtiä sitä.

467
00:19:19,640 --> 00:19:21,650
Ja kukin soluista
Tässä joukko on menossa

468
00:19:21,650 --> 00:19:23,470
edustamaan kirjeen aakkoset.

469
00:19:23,470 --> 00:19:28,190
>> Erityisesti aion kohdella
tämä on, sitten B, sitten C, sitten D,

470
00:19:28,190 --> 00:19:29,310
tämä yksi täällä.

471
00:19:29,310 --> 00:19:32,940
Joten tämä tulee tehokkaasti
edustaa kirjain D.

472
00:19:32,940 --> 00:19:36,040
Vaan lisätä kaikki Daven n
nimeä en täytyy tehdä hieman enemmän.

473
00:19:36,040 --> 00:19:37,840
Joten olen ensin menossa hash, niin sanotusti.

474
00:19:37,840 --> 00:19:41,049
Olen menossa katsomaan ensimmäinen kirjain
vuonna Daven n, joka on ilmeisesti D,

475
00:19:41,049 --> 00:19:42,840
ja aion jakaa
solmu, joka näyttää

476
00:19:42,840 --> 00:19:45,570
kuten this-- iso suorakulmio iso
mahtuakseen koko aakkoset.

477
00:19:45,570 --> 00:19:47,140
>> Nyt D on tehty.

478
00:19:47,140 --> 00:19:49,720
Nyt A. D-A-V-E-N on tavoite.

479
00:19:49,720 --> 00:19:51,220
Joten nyt, mitä aion tehdä, on tämä.

480
00:19:51,220 --> 00:19:54,027
Heti kun aloin D huomautus
ei ole osoitin siellä.

481
00:19:54,027 --> 00:19:56,860
Se on roskaa arvot tällä hetkellä,
tai voisin alustaa sen nollaamaan.

482
00:19:56,860 --> 00:19:59,630
Mutta haluan pysyä menossa
tämä ajatus rakentaa puun.

483
00:19:59,630 --> 00:20:04,260
Sallikaa minun jakaa toinen näistä
solmuja, jotka on 26 elementtejä sitä.

484
00:20:04,260 --> 00:20:05,150
>> Ja tiedätkö mitä?

485
00:20:05,150 --> 00:20:09,130
Jos tämä on vain solmu muistiin, että
Olen luotu malloc käyttäen struct

486
00:20:09,130 --> 00:20:11,240
kuten tulemme pian nähdä,
Aion tehdä this--

487
00:20:11,240 --> 00:20:14,450
Aion piirretään nuoli
asia, joka edusti D alas

488
00:20:14,450 --> 00:20:15,860
tähän uuteen solmuun.

489
00:20:15,860 --> 00:20:19,240
Ja nyt, ensimmäistä seuraavaksi
kirje Daven nimi,

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V-- aion mennä eteenpäin
ja vetää toisen solmun näin,

491
00:20:24,150 --> 00:20:30,150
jolloin, V-elementit tässä, joka
me piirtää instance-- oho.

492
00:20:30,150 --> 00:20:31,020
Emme vetää siellä.

493
00:20:31,020 --> 00:20:31,936
Se tulee menemään täällä.

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

495
00:20:32,890 --> 00:20:35,712
>> Sitten me aiomme
pitävät tätä V.

496
00:20:35,712 --> 00:20:44,920
Ja sitten täällä aiomme indeksi
alas V mitä me harkitsemme E.

497
00:20:44,920 --> 00:20:50,100
Ja sitten täältä me tulemme
go on yksi näistä solmuista täällä.

498
00:20:50,100 --> 00:20:52,930
Ja nyt meillä on kysymys vastata.

499
00:20:52,930 --> 00:20:57,840
Minun täytyy jotenkin osoittaa, että
olemme lopussa merkkijonon Daven.

500
00:20:57,840 --> 00:20:59,490
Joten voisin vain jättää sitä null.

501
00:20:59,490 --> 00:21:02,670
>> Mutta mitä jos meillä on Daven n
Koko nimi myös, mikä

502
00:21:02,670 --> 00:21:04,280
on, kuten olemme sanoneet, Davenport?

503
00:21:04,280 --> 00:21:06,970
Joten mitä jos Daven on
todella alimerkkijono,

504
00:21:06,970 --> 00:21:08,960
etuliite paljon pidempi jono?

505
00:21:08,960 --> 00:21:11,450
Emme voi vain pysyvästi
sano mitään ei tapahdu

506
00:21:11,450 --> 00:21:14,410
mennä sinne, koska emme voineet
älä laita sana kuten Davenport

507
00:21:14,410 --> 00:21:15,840
tähän tietorakenne

508
00:21:15,840 --> 00:21:19,560
>> Joten mitä voisimme tehdä sen sijaan on
rinnastaa nämä elementit

509
00:21:19,560 --> 00:21:22,170
niin ehkä on kaksi
Sisällä niistä.

510
00:21:22,170 --> 00:21:24,810
Yksi on osoitin, todellakin,
kuten olen tehnyt.

511
00:21:24,810 --> 00:21:27,100
Joten jokainen näistä laatikoista
ei ole vain yksi solu.

512
00:21:27,100 --> 00:21:29,855
Mutta mitä jos alkuun
one-- pohja oman

513
00:21:29,855 --> 00:21:32,230
olemaan nolla, koska
ei ole Davenport vielä.

514
00:21:32,230 --> 00:21:34,197
Mitä jos ylin
On joitakin erityisiä arvoa?

515
00:21:34,197 --> 00:21:36,530
Ja se tulee olemaan hieman
vaikea tehdä se tämän koon.

516
00:21:36,530 --> 00:21:38,130
Mutta kai se on vain valintamerkki.

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

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-N on merkkijono
Tässä tietorakenne.

519
00:21:44,230 --> 00:21:48,350
>> Samaan aikaan, jos minulla olisi enemmän tilaa
täällä, voisin tehdä P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
ja voisin laittaa Mistä solmun
että on T-kirjain aivan lopussa.

521
00:21:52,650 --> 00:21:55,460
Joten tämä on massiivisesti
monimutkainen näköinen tietorakenne.

522
00:21:55,460 --> 00:21:57,210
Ja minun käsiala
ei tietenkään auta.

523
00:21:57,210 --> 00:22:00,043
Mutta jos halusin lisätä jotain
muu, miettiä, mitä tekisimme.

524
00:22:00,043 --> 00:22:03,370
Jos haluaisimme asetti Daavidin,
olimme noudattaa samaa logiikkaa, D-A-V,

525
00:22:03,370 --> 00:22:08,802
mutta nyt haluaisin huomauttaa seuraavassa
elementti ei E, vaan I D.

526
00:22:08,802 --> 00:22:10,760
Joten siellä tulee olemaan
lisää solmuja tässä puussa.

527
00:22:10,760 --> 00:22:12,325
Aiomme olla puhelu malloc enemmän.

528
00:22:12,325 --> 00:22:14,700
Mutta en halua tehdä
täydellinen sotku tätä kuvaa.

529
00:22:14,700 --> 00:22:17,710
Joten sen sijaan tarkastellaan yhdessä
joka on ollut esiformuloituja

530
00:22:17,710 --> 00:22:21,810
Nytkin ei piste, piste,
pisteitä, mutta vain lyhennettynä paneelit.

531
00:22:21,810 --> 00:22:23,950
Mutta kukin solmuista
tässä puussa täällä

532
00:22:23,950 --> 00:22:26,700
edustaa samaa thing--
array Ray koosta 26.

533
00:22:26,700 --> 00:22:28,860
>> Tai jos haluamme olla
todella oikea nyt, mitä

534
00:22:28,860 --> 00:22:30,790
Jos jonkun nimi
heittomerkki, katsotaanpa

535
00:22:30,790 --> 00:22:35,560
olettaa, että jokainen solmu todella on
kuten 27 indeksit se, ei vain 26.

536
00:22:35,560 --> 00:22:42,020
Joten tämä nyt tulee olemaan data
rakennetta kutsutaan trie-- T-R-I-E.

537
00:22:42,020 --> 00:22:46,120
Trien, joka on oletettavasti
historiallisesti nokkela nimi puu

538
00:22:46,120 --> 00:22:49,040
optimoituna
haku, joka tietenkin,

539
00:22:49,040 --> 00:22:50,870
kirjoitetaan I-E, joten se on trie.

540
00:22:50,870 --> 00:22:52,710
Mutta se on historiaa trien.

541
00:22:52,710 --> 00:22:55,860
>> Joten trie on tämä puumainen tiedot
rakenne kuten sukupuu

542
00:22:55,860 --> 00:22:57,510
että lopulta käyttäytyy niin.

543
00:22:57,510 --> 00:23:00,890
Ja tässä on vain yksi esimerkki
koko joukko muita ihmisten nimet.

544
00:23:00,890 --> 00:23:03,540
Mutta kysymys nyt
käsillä on mitä on

545
00:23:03,540 --> 00:23:08,070
saimme ottamalla käyttöön luultavasti enemmän
monimutkainen tietorakenne, ja yksi,

546
00:23:08,070 --> 00:23:09,870
rehellisesti, joka käyttää paljon muistia.

547
00:23:09,870 --> 00:23:11,703
>> Sillä vaikka,
Tällä hetkellä olen vain

548
00:23:11,703 --> 00:23:15,050
käyttäen D's osoitin ja
Ja V ja Es: n ja NS,

549
00:23:15,050 --> 00:23:16,700
En tuhlaa pahus paljon muistia.

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

551
00:23:18,030 --> 00:23:22,660
Mutta missä vietän yhden resurssin,
Minulla on tapana tehdä saada takaisin toiseen.

552
00:23:22,660 --> 00:23:26,020
Joten jos vietän enemmän tilaa,
mikä on luultavasti toivoa?

553
00:23:26,020 --> 00:23:27,407
Että vietän vähemmän mitä?

554
00:23:27,407 --> 00:23:28,240
Yleisö: Vähemmän aikaa.

555
00:23:28,240 --> 00:23:28,990
DAVID MALAN: Time.

556
00:23:28,990 --> 00:23:30,320
Nyt miksi se mahtaa olla?

557
00:23:30,320 --> 00:23:33,880
No, mikä on lisäys
ajan, mitattuna iso O nyt

558
00:23:33,880 --> 00:23:37,660
nimen, kuten Daven
tai Davenport tai David?

559
00:23:37,660 --> 00:23:39,340
No, Daven oli viisi vaihetta.

560
00:23:39,340 --> 00:23:42,350
Davenport olisi yhdeksän vaiheet,
niin se olisi muutaman askeleen.

561
00:23:42,350 --> 00:23:44,250
David olisi viisi askelta samoin.

562
00:23:44,250 --> 00:23:47,230
Joten ne ovat konkreettisia
numeroita, mutta varmasti siellä on

563
00:23:47,230 --> 00:23:49,550
yläraja
pituus jonkun nimi.

564
00:23:49,550 --> 00:23:52,240
Ja todellakin, että ongelma
sarjaa viiden erittely,

565
00:23:52,240 --> 00:23:54,050
aiomme ehdottaa
että se on jotain

566
00:23:54,050 --> 00:23:55,470
joka on 40-joidenkin outoa merkkiä.

567
00:23:55,470 --> 00:23:58,180
>> Realistisesti, kukaan ei ole
äärettömän pitkä nimi,

568
00:23:58,180 --> 00:24:01,542
joka on sanoa, että pituus
nimi tai merkkijonon pituuden voisimme

569
00:24:01,542 --> 00:24:03,750
on tietty tila
rakenne on luultavasti mitä?

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

571
00:24:05,550 --> 00:24:06,250
Se on vakio.

572
00:24:06,250 --> 00:24:06,430
Oikea?

573
00:24:06,430 --> 00:24:09,310
Se voi olla iso vakio kuten
40-jotain, mutta se on vakio.

574
00:24:09,310 --> 00:24:13,752
Ja se ei ole riippuvuutta, kuinka monta
muut nimet ovat tässä tietorakenne.

575
00:24:13,752 --> 00:24:15,460
Toisin sanoen, jos I
halusi nyt lisätä

576
00:24:15,460 --> 00:24:20,540
Colton tai Gabriel tai Rob tai Zamyla tai
Alison tai Belinda tai muita nimiä

577
00:24:20,540 --> 00:24:23,940
Sen henkilöstön tähän tiedot
rakenne, on käyntiaika

578
00:24:23,940 --> 00:24:26,750
lisäämällä muita nimiä
olemaan ollenkaan vaikuttanut

579
00:24:26,750 --> 00:24:30,220
kuinka monet muut tekijät ovat
datarakenteessa jo?

580
00:24:30,220 --> 00:24:31,040
Se ei ole.

581
00:24:31,040 --> 00:24:31,540
Oikea?

582
00:24:31,540 --> 00:24:36,150
Koska olemme tehokkaasti käyttäen
Tämän monikerroksinen tiiviste.

583
00:24:36,150 --> 00:24:38,280
Ja ajoaika
Jonkin näistä toimista

584
00:24:38,280 --> 00:24:41,510
ei ole riippuvainen siitä lukumäärästä
elementtejä, jotka ovat tietorakenteen

585
00:24:41,510 --> 00:24:43,090
tai jotka ovat lopulta menossa
olla tietorakenteen,

586
00:24:43,090 --> 00:24:44,714
mutta pituudesta, mitä erityisesti?

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

588
00:24:46,500 --> 00:24:49,200
>> Merkkijono on
Lisätään, joka ei tee

589
00:24:49,200 --> 00:24:52,580
Tämän asymptoottisesti vakio
time-- iso O yhden.

590
00:24:52,580 --> 00:24:54,720
Ja rehellisesti, juuri
reaalimaailmassa, tämä

591
00:24:54,720 --> 00:24:58,380
tarkoittaa lisäämällä Daven nimi vie
kuten viisi askelta, tai Davenport yhdeksän

592
00:24:58,380 --> 00:25:00,100
vaiheet, tai David viisi vaihetta.

593
00:25:00,100 --> 00:25:03,071
Se on tosi pieni käynnissä kertaa.

594
00:25:03,071 --> 00:25:05,320
Ja todellakin, se on hyvin
hyvä asia, varsinkin kun

595
00:25:05,320 --> 00:25:08,126
se ei ole riippuvainen koko
elementtien määrä siellä.

596
00:25:08,126 --> 00:25:10,500
Joten miten voisimme toteuttaa tämän
Tällainen rakenne koodin?

597
00:25:10,500 --> 00:25:12,900
Se on hieman enemmän
monimutkainen, mutta silti se on

598
00:25:12,900 --> 00:25:15,050
vain soveltaminen
perusrakenneosia.

599
00:25:15,050 --> 00:25:17,830
Aion uudelleen
meille solmu seuraavasti:

600
00:25:17,830 --> 00:25:21,100
bool kutsui word-- ja tämän
voisi kutsua mitään.

601
00:25:21,100 --> 00:25:23,970
Mutta bool edustaa
mitä piirsin niin valintamerkki.

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

603
00:25:24,490 --> 00:25:26,720
Tämä on loppuun merkkijonon
Tässä tietorakenne.

604
00:25:26,720 --> 00:25:30,702
>> Ja, tietenkin, solmu tähti
siellä viittaa lapsiin.

605
00:25:30,702 --> 00:25:32,410
Ja todellakin, aivan kuten
sukupuu, voit

606
00:25:32,410 --> 00:25:34,370
harkitsisi solmut
joita roikkui

607
00:25:34,370 --> 00:25:36,920
pohjan joidenkin vanhemman
elementti olla lapsia.

608
00:25:36,920 --> 00:25:40,510
Ja niin lapset on menossa
olla joukko 27, 27 yksi

609
00:25:40,510 --> 00:25:41,680
vain vointia heittomerkki.

610
00:25:41,680 --> 00:25:43,390
Aiomme järjestää
on erikoistapaus, joka.

611
00:25:43,390 --> 00:25:45,400
Joten voit olla tiettyjä
nimet heittomerkit.

612
00:25:45,400 --> 00:25:47,399
Ehkä jopa Yhdysviivalla
mennä sinne, mutta sinun

613
00:25:47,399 --> 00:25:50,330
nähdä p set 5 me vain välitä
kirjeistä ja heittomerkit.

614
00:25:50,330 --> 00:25:52,990
>> Ja sitten miten te edustatte
tietorakenne itse?

615
00:25:52,990 --> 00:25:56,454
Miten te edustatte root
Tämän trie, niin sanoakseni?

616
00:25:56,454 --> 00:25:59,620
No, aivan kuten linkitetyn listan, voit
täytyy osoitin ensimmäiseen elementtiin.

617
00:25:59,620 --> 00:26:04,270
Kanssa trie sinun tarvitsee vain yhden
osoitin juuri tämän trie.

618
00:26:04,270 --> 00:26:07,290
Ja sieltä voit hash
tiesi alas syvemmälle ja syvemmälle

619
00:26:07,290 --> 00:26:10,460
joka toinen solmun rakenteessa.

620
00:26:10,460 --> 00:26:13,440
Joten yksinkertaisesti tämän voi
me edustamme, että struct.

621
00:26:13,440 --> 00:26:15,877
>> Nyt Meanwhile-- Voi kysymys.

622
00:26:15,877 --> 00:26:17,220
>> Yleisö: Mikä bool sana?

623
00:26:17,220 --> 00:26:20,490
>> DAVID MALAN: Bool sana on
juuri tämä C inkarnaatio

624
00:26:20,490 --> 00:26:22,920
mitä kuvasin
tähän kohtaan täällä, kun

625
00:26:22,920 --> 00:26:26,000
Aloitin jakamalla kunkin
array elementtejä kahteen osaan.

626
00:26:26,000 --> 00:26:27,600
Yksi on osoitin seuraavaan solmuun.

627
00:26:27,600 --> 00:26:30,280
Muiden on oltava
jotain valintaruutu

628
00:26:30,280 --> 00:26:33,770
sanoa kyllä, siellä
Sana Daven että loppuu tähän,

629
00:26:33,770 --> 00:26:35,610
koska emme halua,
tällä hetkellä, Dave.

630
00:26:35,610 --> 00:26:39,320
>> Vaikka Dave tulee olemaan
oikeutettu sana, hän ei ole trie

631
00:26:39,320 --> 00:26:39,830
vielä.

632
00:26:39,830 --> 00:26:40,950
Ja D ei ole sana.

633
00:26:40,950 --> 00:26:42,770
Ja D-ei ole sana tai nimi.

634
00:26:42,770 --> 00:26:45,020
Joten valintamerkki
osoittaa vain, kun olet

635
00:26:45,020 --> 00:26:48,190
osuma tämä solmu on
edellinen polku merkkiä

636
00:26:48,190 --> 00:26:50,700
todella merkkijono, joka olet lisännyt.

637
00:26:50,700 --> 00:26:53,660
Niin, että kaikki bool
siellä tekee meille.

638
00:26:53,660 --> 00:26:55,500
>> Muita kysymyksiä yrittää?

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

640
00:26:56,215 --> 00:26:58,035
>> Yleisö: Mikä on päällekkäisyyttä?

641
00:26:58,035 --> 00:26:59,945
Mitä jos sinulla on Dave ja Daven?

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

643
00:27:00,820 --> 00:27:02,580
Mitä jos sinulla on Dave ja Daven?

644
00:27:02,580 --> 00:27:06,240
Jos siis lisätä, sanovat lempinimi,
varten David-- Dave-- D-V-E?

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

646
00:27:07,370 --> 00:27:08,700
Tämä on oikeastaan ​​erittäin yksinkertainen.

647
00:27:08,700 --> 00:27:10,325
Joten me vain vie neljä vaihetta.

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

649
00:27:11,042 --> 00:27:15,847
D-A-V-E. Ja mitä minun täytyy
tehdä, kun osuin että neljäs solmu?

650
00:27:15,847 --> 00:27:16,680
Juuri menossa tarkistaa.

651
00:27:16,680 --> 00:27:18,000
Olemme jo hyvä mennä.

652
00:27:18,000 --> 00:27:18,840
Tehty.

653
00:27:18,840 --> 00:27:19,750
Neljä vaihetta.

654
00:27:19,750 --> 00:27:21,590
Vakioaikaisia ​​asymptoottisesti.

655
00:27:21,590 --> 00:27:26,300
Ja nyt olemme ilmoittaneet, että molemmat Dave
ja Daven ovat merkkijonoja rakenteen.

656
00:27:26,300 --> 00:27:27,710
Joten ei ole ongelma.

657
00:27:27,710 --> 00:27:30,200
Ja huomaa, miten läsnäolo
on Daven ei selvinnyt

658
00:27:30,200 --> 00:27:34,750
ottaa enempää aikaa tai vähemmän
aikaa Dave ja päinvastoin.

659
00:27:34,750 --> 00:27:36,000
>> Joten mitä muuta voimme nyt tehdä?

660
00:27:36,000 --> 00:27:40,680
Olemme käyttäneet tätä metafora ennen
tarjottimia edustaa jotain.

661
00:27:40,680 --> 00:27:43,380
Mutta näyttää siltä, ​​että
pino tarjottimet on oikeastaan

662
00:27:43,380 --> 00:27:47,187
demonstratiivinen toisen abstraktien tietojen
type-- korkeamman tason datarakenteen

663
00:27:47,187 --> 00:27:49,770
että lopussa päivä on juuri
kuten array tai linkitetty lista

664
00:27:49,770 --> 00:27:50,970
tai jotain arkisempi.

665
00:27:50,970 --> 00:27:53,270
Mutta se on enemmän mielenkiintoista
käsitteellinen käsite.

666
00:27:53,270 --> 00:27:56,440
Pino, kuten nämä
Lokeroiden täällä Mather,

667
00:27:56,440 --> 00:27:58,750
kutsutaan yleensä
vain that-- pino.

668
00:27:58,750 --> 00:28:02,540
>> Ja tämän tyyppisen tietorakenteen
sinulla on kaksi operations--

669
00:28:02,540 --> 00:28:05,880
sinulla on yksi nimeltään push
lisäämällä jotain pino,

670
00:28:05,880 --> 00:28:08,320
kuin laittaisi toiseen lokeroon
takaisin pinon päälle.

671
00:28:08,320 --> 00:28:11,350
Ja sitten pop, mikä tarkoittaa,
ottaa päällimmäinen lokero pois.

672
00:28:11,350 --> 00:28:16,210
Mutta mitä näppäintä noin pino on, että
se sai tämän utelias ominaisuus.

673
00:28:16,210 --> 00:28:19,560
Kuten ruokasali henkilökunta
järjestämällä tarjottimet seuraavan aterian,

674
00:28:19,560 --> 00:28:21,380
mitä tulee olemaan
totta, miten opiskelijat

675
00:28:21,380 --> 00:28:22,856
vuorovaikutuksessa tämän datan rakenne?

676
00:28:22,856 --> 00:28:24,480
Yleisö: He aikovat pop kertaluonteinen.

677
00:28:24,480 --> 00:28:26,550
DAVID MALAN: He aikovat
pop kertaluonteinen, toivottavasti alkuun.

678
00:28:26,550 --> 00:28:28,910
Muuten se on vain typerää
mennä pohjaan.

679
00:28:28,910 --> 00:28:29,070
Oikea?

680
00:28:29,070 --> 00:28:31,620
Tietorakenne ei oikeastaan ​​salli
voit napata pohjalevy ainakin

681
00:28:31,620 --> 00:28:32,520
helposti.

682
00:28:32,520 --> 00:28:35,040
Joten on tämä kummallinen
omaisuutta pino

683
00:28:35,040 --> 00:28:39,730
että viimeinen erä on
olemaan ensimmäinen ulos.

684
00:28:39,730 --> 00:28:43,400
Ja tietotekniikan tutkijoita soittaa
Tämän LIFO-- last in, first out.

685
00:28:43,400 --> 00:28:45,540
Ja se todella ei ole
mielenkiintoisia sovelluksia.

686
00:28:45,540 --> 00:28:50,090
Se ei ole välttämättä yhtä selvää kuin jotkut
toiset, mutta se voi todellakin olla hyödyllistä,

687
00:28:50,090 --> 00:28:54,040
ja se voi todellakin toteuttaa
pari eri tavoin.

688
00:28:54,040 --> 00:28:58,550
>> Niin yksi, ja itse asiassa, anna
minua ei sukeltaa tuohon.

689
00:28:58,550 --> 00:28:59,860
Tehdään tämä sijaan.

690
00:28:59,860 --> 00:29:03,700
Katsotaanpa yksi, joka on melkein
Sama idea, mutta se on vähän oikeudenmukaisempaa.

691
00:29:03,700 --> 00:29:04,200
Oikea?

692
00:29:04,200 --> 00:29:07,560
Jos olet yksi näistä fani poikia tai
tytöt, jotka todella tykkää Applen tuotteita

693
00:29:07,560 --> 00:29:10,130
ja heräsin klo 03:00
riviin jossain myymälässä

694
00:29:10,130 --> 00:29:14,150
saada uusinta iPhone, sinun
ehkä jonottivat näin.

695
00:29:14,150 --> 00:29:15,800
>> Nyt jonossa on erittäin tarkoituksella nimetty.

696
00:29:15,800 --> 00:29:18,190
Se on linja, koska siellä
Joissakin oikeudenmukaisuus sitä.

697
00:29:18,190 --> 00:29:18,690
Oikea?

698
00:29:18,690 --> 00:29:21,690
Se olisi eräänlainen imi, jos olet
sai siellä ensin Apple Storessa

699
00:29:21,690 --> 00:29:25,700
mutta olet tehokkaasti alimmainen
lokero koska Applen työntekijöille sitten

700
00:29:25,700 --> 00:29:28,189
pop viimeinen henkilö, joka
itse saanut linjassa.

701
00:29:28,189 --> 00:29:31,230
Niin pinot ja jonot, vaikka
toiminnallisesti ne ovat eräänlainen same--

702
00:29:31,230 --> 00:29:33,105
se on vain tämä kokoelma
resursseja, jotka on

703
00:29:33,105 --> 00:29:36,210
tulee kasvamaan ja shrink-- siellä
Tämän oikeudenmukaisuuden näkökulma siihen,

704
00:29:36,210 --> 00:29:39,634
ainakin todellisessa maailmassa,
jossa toiminnot liikut

705
00:29:39,634 --> 00:29:40,800
ovat täysin erilaiset.

706
00:29:40,800 --> 00:29:43,360
Stack-- jono
rather-- sanotaan

707
00:29:43,360 --> 00:29:45,320
kaksi operaatiota: n jono ja d jono.

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

709
00:29:46,341 --> 00:29:48,090
Tai voit soittaa heille
mikä tahansa joukko asioita.

710
00:29:48,090 --> 00:29:50,770
Mutta haluat vain kaapata
ajatus, että yksi on lisännyt

711
00:29:50,770 --> 00:29:53,230
ja yksi on lopulta vähentämällä.

712
00:29:53,230 --> 00:29:58,840
>> Nyt alla huppu, sekä pino
ja jono voitaisiin toteuttaa miten?

713
00:29:58,840 --> 00:30:01,390
Emme aio mennä koodi
sitä, koska korkeamman tason

714
00:30:01,390 --> 00:30:03,387
Ajatus on tavallaan selvempi.

715
00:30:03,387 --> 00:30:04,470
Tarkoitan, mitä ihmiset tekevät?

716
00:30:04,470 --> 00:30:07,030
Jos minä olen ensimmäinen henkilö Apple
Tallentaa ja tämä on etuovi,

717
00:30:07,030 --> 00:30:08,130
Tiedätkö, aion seistä täällä.

718
00:30:08,130 --> 00:30:09,750
Ja seuraavan henkilön
menossa seistä täällä.

719
00:30:09,750 --> 00:30:11,500
Ja seuraavan henkilön
menossa seistä täällä.

720
00:30:11,500 --> 00:30:13,792
Niin mitä tietorakenne
otollisia jonossa?

721
00:30:13,792 --> 00:30:14,542
>> Yleisö: jono.

722
00:30:14,542 --> 00:30:15,667
DAVID MALAN: No, jono.

723
00:30:15,667 --> 00:30:16,390
Toki.

724
00:30:16,390 --> 00:30:16,920
Mitä muuta?

725
00:30:16,920 --> 00:30:17,600
>> Yleisö: linkitetty lista.

726
00:30:17,600 --> 00:30:18,990
>> DAVID MALAN: liittyy
Listassa voisi toteuttaa.

727
00:30:18,990 --> 00:30:22,500
Ja linkitetty lista on mukavaa, koska silloin
se voi kasvaa mielivaltaisesti pitkiä verrattuna

728
00:30:22,500 --> 00:30:24,880
että on joitakin kiinteitä numero
ihmisiä myymälässä.

729
00:30:24,880 --> 00:30:27,030
Mutta ehkä kiinteä määrä
paikkoja on oikeutettua.

730
00:30:27,030 --> 00:30:30,350
Koska jos ne vain ovat, kuten 20
iPhonet ensimmäisenä päivänä, ehkä

731
00:30:30,350 --> 00:30:33,930
ne tarvitsee vain taulukon koko
20 edustaa jonoa, joka

732
00:30:33,930 --> 00:30:37,070
on vain sanoa nyt, kun alamme keskustella
näistä että suurempia ongelmia,

733
00:30:37,070 --> 00:30:38,890
voit toteuttaa sen
vuonna monin tavoin.

734
00:30:38,890 --> 00:30:42,030
Ja on luultavasti juuri menossa
olla kaupan pois ja ajallisesti

735
00:30:42,030 --> 00:30:43,950
tai vain oman koodin monimutkaisuutta.

736
00:30:43,950 --> 00:30:45,380
>> Entä pino?

737
00:30:45,380 --> 00:30:48,190
No, pino, olemme nähneet liian
voisi vain olla näitä lokeroita.

738
00:30:48,190 --> 00:30:50,007
Ja voisitte toteuttaa tämän array.

739
00:30:50,007 --> 00:30:53,090
Mutta jossain vaiheessa jos käytät array,
mitä tulee tapahtumaan lokerot

740
00:30:53,090 --> 00:30:54,173
yrität laittaa alas?

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

742
00:30:55,170 --> 00:30:55,670
Selvä.

743
00:30:55,670 --> 00:30:57,490
Olet vain menossa
voi mennä niin korkea.

744
00:30:57,490 --> 00:31:00,156
Ja mielestäni Mather he
todella upotettu että aukko.

745
00:31:00,156 --> 00:31:01,950
Niin tosiaan, se on melkein
kuten Mather käyttää

746
00:31:01,950 --> 00:31:03,783
joukko kiinteitä koko,
koska voit vain

747
00:31:03,783 --> 00:31:08,302
sovittaa niin monta lokeroa että aukko
seinä alhaalla ihmisten polvet.

748
00:31:08,302 --> 00:31:10,010
Ja jotta voisi olla
sanotaan olevan taulukon,

749
00:31:10,010 --> 00:31:14,300
mutta voisimme varmasti toteuttaa että
yleisemmin linkitetty lista.

750
00:31:14,300 --> 00:31:16,390
>> No, entä toinen tietorakenne?

751
00:31:16,390 --> 00:31:18,760
Saanen vetää yksi muu visuaalinen täällä.

752
00:31:18,760 --> 00:31:24,710
Jotain Entäs tämä yksi täällä?

753
00:31:24,710 --> 00:31:28,920
Miksi se voisi olla hyödyllistä ole
jotain niin hieno kuin trie, joka

754
00:31:28,920 --> 00:31:32,370
näimme oli näitä hyvin laaja solmuja,
joista kukin on joukko?

755
00:31:32,370 --> 00:31:35,740
Mutta mitä jos teemme jotain enemmän
yksinkertaisesti, kuten vanha koulu sukupuu,

756
00:31:35,740 --> 00:31:38,110
joiden kunkin solmun täällä
on vain numeron tallentamisesta.

757
00:31:38,110 --> 00:31:42,180
Sen sijaan, että nimi tai jälkeläinen
on vain numeron tallentamisesta näin.

758
00:31:42,180 --> 00:31:45,250
>> No, slangia, jota käytämme
tietorakenteita on sekä yrittää

759
00:31:45,250 --> 00:31:49,510
ja puita, missä trien, jälleen, on
vain yksi, jonka solmut ovat paneelit,

760
00:31:49,510 --> 00:31:51,680
on silti mitä voisi
käyttää vuodesta alakoulussa

761
00:31:51,680 --> 00:31:53,860
kun olet tehnyt perhe
tree-- lehdet ja juuren

762
00:31:53,860 --> 00:31:57,250
puun ja lapset
vanhemman ja sisarukset sen.

763
00:31:57,250 --> 00:32:03,670
Ja voisimme toteuttaa puu,
esimerkiksi, niin yksinkertaisesti kuin tämä.

764
00:32:03,670 --> 00:32:07,420
Puu, jos se solmu, yksi
Näissä piireissä että on useita,

765
00:32:07,420 --> 00:32:09,947
se ei tule olla
yksi osoitin, mutta kaksi.

766
00:32:09,947 --> 00:32:11,780
Ja heti kun lisäät
toinen osoitin, sinun

767
00:32:11,780 --> 00:32:13,905
voi itse nyt tehdä sort
kaksiulotteisten tietojen

768
00:32:13,905 --> 00:32:14,780
rakenteet muistissa.

769
00:32:14,780 --> 00:32:16,660
Paljon kuin kaksiulotteinen
array, voit

770
00:32:16,660 --> 00:32:18,904
on eräänlainen kaksiulotteinen
liittyvät luettelot mutta niitä

771
00:32:18,904 --> 00:32:20,820
jotka noudattavat kaavaa
jossa ei ole sykliä.

772
00:32:20,820 --> 00:32:24,487
Se on todella puu yhdellä
isovanhempi tapa tänne ja sitten

773
00:32:24,487 --> 00:32:27,320
jotkut vanhemmat ja lapset ja
lapsenlapset ja lastenlastenlapset.

774
00:32:27,320 --> 00:32:28,370
ja niin edelleen.

775
00:32:28,370 --> 00:32:32,390
>> Mutta mitä todella siisti tästä liikaa,
vain kiusaa sinua vähän koodia,

776
00:32:32,390 --> 00:32:35,370
Recall rekursio alkaen
jonkin aikaa takaisin, jolloin

777
00:32:35,370 --> 00:32:38,220
voit kirjoittaa funktio, joka kutsuu itseään.

778
00:32:38,220 --> 00:32:41,140
Tämä on kaunis tilaisuus
toteuttaa jotain

779
00:32:41,140 --> 00:32:42,920
kuten rekursio, koska pitävät tätä.

780
00:32:42,920 --> 00:32:43,860
>> Tämä on puu.

781
00:32:43,860 --> 00:32:48,040
Ja olen ollut vähän anaali miten
Laitoin kokonaislukuja kadulle.

782
00:32:48,040 --> 00:32:51,020
Niin paljon, että sillä on erityinen
name-- binäärihakupuu.

783
00:32:51,020 --> 00:32:53,460
Nyt olemme kuulleet binary
etsiä, mutta voit

784
00:32:53,460 --> 00:32:55,180
työskennellä taaksepäin tämä asia nimi?

785
00:32:55,180 --> 00:32:59,280
Mikä on malli miten
Lisätään kokonaisluvut tähän puuhun?

786
00:32:59,280 --> 00:33:00,696
Se ei ole mielivaltaista.

787
00:33:00,696 --> 00:33:01,570
Siellä on joitakin kuvio.

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

789
00:33:02,090 --> 00:33:03,370
>> Yleisö: Pienempiä vasemmalla.

790
00:33:03,370 --> 00:33:03,690
>> DAVID MALAN: Joo.

791
00:33:03,690 --> 00:33:05,062
Pienempiä ovat vasemmalla.

792
00:33:05,062 --> 00:33:06,270
Isompiakin ovat oikealla.

793
00:33:06,270 --> 00:33:12,940
Niin että totena on
vanhempi on suurempi kuin sen vasen lapsi,

794
00:33:12,940 --> 00:33:14,850
mutta vähemmän kuin sen oikea lapsi.

795
00:33:14,850 --> 00:33:17,750
Ja että yksin on jopa
rekursiivinen sanallinen määritelmä

796
00:33:17,750 --> 00:33:20,500
koska voit hakea että
Samaa logiikkaa jokaiseen solmuun

797
00:33:20,500 --> 00:33:23,080
ja se vain pohjat
ulos, pohja tapauksessa, jos

798
00:33:23,080 --> 00:33:25,740
tulee, kun osut yksi
lehtiä, niin sanotusti,

799
00:33:25,740 --> 00:33:28,580
jos lomaa ei ole lapsia vielä.

800
00:33:28,580 --> 00:33:30,614
>> Nyt miten voisit löytää numeron 44?

801
00:33:30,614 --> 00:33:32,280
Voisitte aloittaa juuresta ja sanoa, hm.

802
00:33:32,280 --> 00:33:35,690
55 ei ole 44 Niin haluan mennä
oikealle tai haluanko mennä vasemmalle?

803
00:33:35,690 --> 00:33:37,190
No, ilmeisesti haluat mennä vasemmalle.

804
00:33:37,190 --> 00:33:40,060
Ja niin se on aivan kuin puhelin
Varaa esimerkiksi binäärihaku

805
00:33:40,060 --> 00:33:41,099
yleisemmin.

806
00:33:41,099 --> 00:33:43,390
Mutta me sen täytäntöönpanosta
nyt hieman enemmän dynaamisesti

807
00:33:43,390 --> 00:33:45,339
kuin array voisi sallia.

808
00:33:45,339 --> 00:33:48,130
Ja itse asiassa, jos haluat katsoa
klo koodi, ensi silmäyksellä varma.

809
00:33:48,130 --> 00:33:49,671
Se näyttää koko joukko viivoja.

810
00:33:49,671 --> 00:33:51,220
Mutta se on todella helppo käyttää.

811
00:33:51,220 --> 00:33:54,490
Jos haluat toteuttaa toiminnon
nimeltään Hae joiden tarkoitus elämässä

812
00:33:54,490 --> 00:33:57,290
on etsiä arvon
kuten N, kokonaisluku,

813
00:33:57,290 --> 00:34:01,756
ja olet läpäissyt yhden pointer--
osoitin solmuun juuret,

814
00:34:01,756 --> 00:34:04,380
Pikemminkin tuon puun, josta
voit käyttää kaikkea muuta,

815
00:34:04,380 --> 00:34:08,850
huomaa, miten suoraviivaisesti
voit toteuttaa logiikkaa.

816
00:34:08,850 --> 00:34:10,880
Jos puu on null,
ilmeisesti se ei ole siellä.

817
00:34:10,880 --> 00:34:11,880
Toivotaan vain return false.

818
00:34:11,880 --> 00:34:12,000
Oikea?

819
00:34:12,000 --> 00:34:14,040
Jos toisaalta se mitään,
siellä ole mitään.

820
00:34:14,040 --> 00:34:17,900
>> Muuten, jos n on pienempi kuin
puu nuoli n- nyt nuoli n,

821
00:34:17,900 --> 00:34:20,670
muistaa esittelimme Super
lyhyesti toinen päivä,

822
00:34:20,670 --> 00:34:25,100
ja että vain sitä de-viite
osoitin ja katsoa kentän kutsutaan n.

823
00:34:25,100 --> 00:34:27,690
Niin se tarkoittaa mennä sinne ja
katsokaa kenttä kutsutaan n.

824
00:34:27,690 --> 00:34:33,810
Joten jos n, arvo olet antanut, on vähemmän
kuin arvo puissa kokonaisluku,

825
00:34:33,810 --> 00:34:35,449
Minne haluat mennä?

826
00:34:35,449 --> 00:34:36,389
Vasemmalle.

827
00:34:36,389 --> 00:34:37,780
>> Niin huomaa rekursio.

828
00:34:37,780 --> 00:34:39,860
En returning-- ole totta.

829
00:34:39,860 --> 00:34:40,989
Ei vääriä.

830
00:34:40,989 --> 00:34:45,670
Olen palaamassa riippumatta vastaus
on peräisin kutsu itseäni, kulkee

831
00:34:45,670 --> 00:34:50,100
n uudelleen, joka on tarpeeton,
mutta mitä hieman erilainen nyt?

832
00:34:50,100 --> 00:34:51,989
Miten minä tehdä ongelman pienempiä?

833
00:34:51,989 --> 00:34:54,920
Olen ohimennen toisena
argumentti, ei puun juurta,

834
00:34:54,920 --> 00:34:59,616
mutta vasen lapsi tässä tapauksessa.

835
00:34:59,616 --> 00:35:00,990
Joten olen ohimennen vasen lapsi.

836
00:35:00,990 --> 00:35:04,720
>> Samaan aikaan, jos n on suurempi kuin
solmu Olen tällä hetkellä katsot,

837
00:35:04,720 --> 00:35:06,690
Etsin oikealla puolella.

838
00:35:06,690 --> 00:35:10,880
Else, jos puu ei ole nolla, ja
Jos elementti ei vasemmalle

839
00:35:10,880 --> 00:35:13,240
ja se ei ole oikea,
mikä on ihanan tapauksessa?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
Olemme todella löytyy solmun
kysymys, ja niin palaamme totta.

842
00:35:18,440 --> 00:35:21,490
>> Joten olemme juuri naarmuja pintaan
nyt joitakin näistä tietorakenteita.

843
00:35:21,490 --> 00:35:24,370
Ongelmatilanteissa asettaa viisi sinua will
tutkia näitä vielä entisestään,

844
00:35:24,370 --> 00:35:27,250
ja sinulle annetaan suunnittelua
valinta, miten edetä tästä.

845
00:35:27,250 --> 00:35:30,250
Mitä haluaisin tehdä päätelmiä
on vain 30 sekunnin teaser

846
00:35:30,250 --> 00:35:32,080
mitä odottaa ensi viikolla ja sen jälkeen.

847
00:35:32,080 --> 00:35:35,390
>> Kuten me begin-- onneksi saatat
think-- meidän siirtyminen hitaasti

848
00:35:35,390 --> 00:35:38,680
maailmasta C ja alempi
tason toteutuksen yksityiskohdat,

849
00:35:38,680 --> 00:35:42,090
maailmaan, jossa voimme ottaa varten
myöntää, että joku muu on vihdoin

850
00:35:42,090 --> 00:35:44,010
täytäntöön nämä tiedot
rakenteet meille,

851
00:35:44,010 --> 00:35:47,570
ja alamme ymmärtää
reaalimaailman täytäntöönpanosäädöksillä

852
00:35:47,570 --> 00:35:50,560
Web-pohjaisten ohjelmien ja
sivustot yleisemmin

853
00:35:50,560 --> 00:35:52,910
ja myös erittäin turvallisuus
vaikutuksia, että olemme vain

854
00:35:52,910 --> 00:35:54,850
alkanut raapia pintaa.

855
00:35:54,850 --> 00:35:57,320
Tässä on mitä odottaa meitä
vuonna lähipäivinä.

856
00:35:57,320 --> 00:36:00,480
>> [VIDEOTOISTOSTA]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -Hän Tuli viestin kanssa,
protokollan kaikkia omia.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
Hän tuli maailmaan julma
palomuurit, piittaamaton reitittimet,

861
00:36:30,894 --> 00:36:33,368
ja vaaroista paljon pahempi kuin kuolema.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
Hän on nopea.

864
00:36:36,236 --> 00:36:37,980
Hän on vahva.

865
00:36:37,980 --> 00:36:42,830
Hän on TCP / IP, ja hänellä on osoitteesi.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"Warriors of the Net".

868
00:36:48,074 --> 00:36:49,660
[END VIDEOTOISTOSTA]

869
00:36:49,660 --> 00:36:50,910
DAVID MALAN: Tulossa ensi viikolla.

870
00:36:50,910 --> 00:36:51,880
Nähdään sitten.

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[VIDEOTOISTOSTA]

873
00:36:56,060 --> 00:36:59,240
-Ja Nyt, "Deep Thoughts"
by Daven Farnham.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-David Aina alkaa
luentoja, "Okei."

876
00:37:05,820 --> 00:37:08,750
Miksi ei, "Tässä on ratkaisu
Tämän viikon Harjoitus "

877
00:37:08,750 --> 00:37:12,180
tai "Annamme kaikille teille?"

878
00:37:12,180 --> 00:37:13,380
[Nauraa]

879
00:37:13,380 --> 00:37:15,530
[END VIDEOTOISTOSTA]