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

2
00:00:11,860 --> 00:00:13,120
>> SPEAKER 1: Olgu, me oleme tagasi.

3
00:00:13,120 --> 00:00:14,480
Tere tulemast CS50.

4
00:00:14,480 --> 00:00:16,510
See on nädala lõpuks seitse.

5
00:00:16,510 --> 00:00:20,200
Nii meelde, et viimane kord, hakkasime
vaadates veidi keerukamate

6
00:00:20,200 --> 00:00:21,100
andmestruktuurid.

7
00:00:21,100 --> 00:00:25,110
Kuna siiani on kõik meil oli tõesti
meie käsutuses, oli see massiiv.

8
00:00:25,110 --> 00:00:29,340
>> Aga enne kui me visake massiivi ei
kõik mis huvitav, mis tõepoolest

9
00:00:29,340 --> 00:00:33,570
tegelikult on, milline on mõned
plussid seda lihtsat andmed

10
00:00:33,570 --> 00:00:34,560
struktuur seni?

11
00:00:34,560 --> 00:00:36,110
Mis on see hea?

12
00:00:36,110 --> 00:00:39,450
Nii palju, kui me oleme näinud?

13
00:00:39,450 --> 00:00:42,540
Mis sul on?

14
00:00:42,540 --> 00:00:44,028
Mitte midagi.

15
00:00:44,028 --> 00:00:45,020
>> Õpilane: [kuuldamatu].

16
00:00:45,020 --> 00:00:45,395
>> SPEAKER 1: Mis see on?

17
00:00:45,395 --> 00:00:46,410
>> Õpilane: [kuuldamatu].

18
00:00:46,410 --> 00:00:47,000
>> SPEAKER 1. Fikseeritud suurusega.

19
00:00:47,000 --> 00:00:51,260
OK, nii et miks on fikseeritud suurus hea küll?

20
00:00:51,260 --> 00:00:53,180
>> Õpilane: [kuuldamatu].

21
00:00:53,180 --> 00:00:56,240
>> SPEAKER 1: OK, nii et see on tõhus
selles mõttes, et saate eraldada

22
00:00:56,240 --> 00:01:00,070
fikseeritud summa ruumi, mis loodetavasti
Just nii palju

23
00:01:00,070 --> 00:01:01,180
ruumi, kui soovite.

24
00:01:01,180 --> 00:01:02,720
Nii et võib olla absoluutselt pluss.

25
00:01:02,720 --> 00:01:06,530
>> Mis on veel kuni pool massiivi?

26
00:01:06,530 --> 00:01:07,610
Jah?

27
00:01:07,610 --> 00:01:08,750
>> Õpilane: [kuuldamatu].

28
00:01:08,750 --> 00:01:09,550
>> SPEAKER 1: All - sorry?

29
00:01:09,550 --> 00:01:11,270
>> Õpilane: [kuuldamatu].

30
00:01:11,270 --> 00:01:13,620
>> SPEAKER 1: Kõik lahtrid mälu
või üksteise kõrval.

31
00:01:13,620 --> 00:01:15,220
Ja see on kasulik - miks?

32
00:01:15,220 --> 00:01:15,970
See on täiesti tõsi.

33
00:01:15,970 --> 00:01:18,611
Aga kuidas me saame kasutada, et tõde?

34
00:01:18,611 --> 00:01:21,500
>> Õpilane: [kuuldamatu].

35
00:01:21,500 --> 00:01:24,490
>> SPEAKER 1: Täpselt, saame jälgida
kus kõik on lihtsalt teada

36
00:01:24,490 --> 00:01:28,560
üks aadress, so aadressi
Esimene bait et patakas mälu.

37
00:01:28,560 --> 00:01:30,420
Või juhul, kui string,
aadress esimese

38
00:01:30,420 --> 00:01:31,460
char selles string.

39
00:01:31,460 --> 00:01:33,330
Ja sealt leiame
stringi lõpuni.

40
00:01:33,330 --> 00:01:35,710
Me võime leida teine ​​element,
Kolmas element, ja nii edasi.

41
00:01:35,710 --> 00:01:38,740
>> Ja nii fancy viis kirjeldada, et
omadus on, et massiivid meile

42
00:01:38,740 --> 00:01:40,020
muutmälu.

43
00:01:40,020 --> 00:01:44,330
Lihtsalt abil nurksulg
märke ja number, saab hüpata

44
00:01:44,330 --> 00:01:48,070
konkreetne element massiivi
pidevas ajal suur O

45
00:01:48,070 --> 00:01:49,810
ühe, nii rääkida.

46
00:01:49,810 --> 00:01:51,080
>> Aga seal on olnud mõned varjuküljed.

47
00:01:51,080 --> 00:01:53,110
Mis array ei tee väga lihtsalt?

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
Mis see ei ole hea?

50
00:01:57,170 --> 00:01:58,810
>> Õpilane: [kuuldamatu].

51
00:01:58,810 --> 00:01:59,860
>> SPEAKER 1: Mis see on?

52
00:01:59,860 --> 00:02:00,530
>> Õpilane: [kuuldamatu].

53
00:02:00,530 --> 00:02:01,460
>> SPEAKER 1: Muutuvad suurusega.

54
00:02:01,460 --> 00:02:04,800
Nii varjuküljed massiiv on
täpselt vastupidine sellele, mida

55
00:02:04,800 --> 00:02:05,540
plussid on.

56
00:02:05,540 --> 00:02:07,610
Nii et üks varjuküljed on
et see on fikseeritud suurus.

57
00:02:07,610 --> 00:02:09,400
Nii et te ei saa tõesti kasvada.

58
00:02:09,400 --> 00:02:13,510
Võite suunata suurem patakas
mälu ja seejärel liikuda vana elemendid

59
00:02:13,510 --> 00:02:14,460
uude massiivi.

60
00:02:14,460 --> 00:02:18,060
Ja siis tasuta vana massiivi jaoks
Näiteks kasutades malloc või sarnane

61
00:02:18,060 --> 00:02:21,180
funktsiooni nimetatakse RealLOC, mis
reallocates mälu.

62
00:02:21,180 --> 00:02:25,490
>> RealLOC, nagu kõrvale, üritab anda sulle
mälu, mis on kõrval massiivi

63
00:02:25,490 --> 00:02:26,610
mis teil juba on.

64
00:02:26,610 --> 00:02:28,740
Aga see võib liigutada asju
ümber kokku.

65
00:02:28,740 --> 00:02:30,710
Aga lühidalt öeldes, et see on kallis, eks?

66
00:02:30,710 --> 00:02:33,440
Sest kui sul on patakas mälu
Selle suurus, kuid sa tõesti tahad ühe

67
00:02:33,440 --> 00:02:36,710
Selle suurus ja soovite säilitada
originaal elemente, mida

68
00:02:36,710 --> 00:02:40,510
ligikaudu lineaarne aeg kopeerimise protsess
mis vajab juhtuda

69
00:02:40,510 --> 00:02:41,900
vana massiivi uus.

70
00:02:41,900 --> 00:02:44,630
Ja reaalsus on see, paludes operatsioonisüsteemi
süsteem uuesti ja uuesti ja

71
00:02:44,630 --> 00:02:48,340
jälle suur tükkideks mälu saab alustada
teile maksma veidi aega samuti.

72
00:02:48,340 --> 00:02:52,250
Nii et see on nii õnnistus ja needus
varjata asjaolu, et need massiivid

73
00:02:52,250 --> 00:02:53,860
on fikseeritud suurus.

74
00:02:53,860 --> 00:02:56,790
Aga kui me võtame kasutusele selle asemel midagi
nagu see, mis me kutsusime seotud

75
00:02:56,790 --> 00:03:00,580
nimekirja, saame mõned plussid ja
mõned varjuküljed ka siin.

76
00:03:00,580 --> 00:03:05,780
>> Niisiis, mis on seotud nimekirja on lihtsalt andmed
struktuur, mis koosneb C structs selles

77
00:03:05,780 --> 00:03:09,850
juhul, kui struktuure, mäletate, on lihtsalt
konteinerisse ühe või mitme konkreetse

78
00:03:09,850 --> 00:03:11,100
tüüpi muutujaid.

79
00:03:11,100 --> 00:03:16,110
Sellisel juhul mida teha andmetüübid
olevat sees struct et

80
00:03:16,110 --> 00:03:17,600
Viimasel ajal oleme kutsutud sõlm?

81
00:03:17,600 --> 00:03:19,380
Kõik need ristkülikud on sõlme.

82
00:03:19,380 --> 00:03:22,660
Ja iga väike ristkülik
sees on andmetüübi.

83
00:03:22,660 --> 00:03:25,300
Millised me öelda
nad olid esmaspäeval?

84
00:03:25,300 --> 00:03:26,478
Jah?

85
00:03:26,478 --> 00:03:27,870
>> Õpilane: [kuuldamatu].

86
00:03:27,870 --> 00:03:30,721
>> SPEAKER 1: muutuv ja pointer, või
Täpsemalt int, n,

87
00:03:30,721 --> 00:03:32,180
ja osuti allosas.

88
00:03:32,180 --> 00:03:35,360
Mõlemad neist juhtub olema 32 bitti, kell
vähemalt arvuti niimoodi CS50

89
00:03:35,360 --> 00:03:37,980
Appliance ja nii nad
tõmmatud võrdselt suurusega.

90
00:03:37,980 --> 00:03:42,260
>> Niisiis, mida kasutate pointer
kuigi näiliselt?

91
00:03:42,260 --> 00:03:47,690
Miks lisada see nool nüüd kui massiivid olid
nii kena ja puhas ja lihtne?

92
00:03:47,690 --> 00:03:50,460
Mis on pointer jaoks teed
meile igas need sõlmed?

93
00:03:50,460 --> 00:03:52,160
>> Õpilane: [kuuldamatu].

94
00:03:52,160 --> 00:03:52,465
>> SPEAKER 1: Täpselt.

95
00:03:52,465 --> 00:03:54,120
Ta räägib sulle, kus
Järgmise üks on.

96
00:03:54,120 --> 00:03:57,350
Nii et ma omamoodi kasutada analoogiat
kasutades niit sortida

97
00:03:57,350 --> 00:03:59,180
niit need sõlmed kokku.

98
00:03:59,180 --> 00:04:01,760
Ja see on täpselt see, mida me teeme koos
suunanäitajaks, sest iga

99
00:04:01,760 --> 00:04:06,360
tükkideks mälu võib olla või mitte olla
terviklik, seljad tagasi

100
00:04:06,360 --> 00:04:09,500
sees RAM, sest iga kord, kui
helistada malloc öeldes mulle piisavalt

101
00:04:09,500 --> 00:04:12,510
baiti uus sõlm, võib see
siin olla või võib olla siin.

102
00:04:12,510 --> 00:04:13,120
Võib-olla on siin.

103
00:04:13,120 --> 00:04:13,730
Võib-olla on siin.

104
00:04:13,730 --> 00:04:14,640
Sa lihtsalt ei tea.

105
00:04:14,640 --> 00:04:17,880
>> Kuid kasutades lähtekohad aadressid
need sõlmed, saate õmblema neid

106
00:04:17,880 --> 00:04:22,370
kokku viisil, mis näeb visuaalselt
nagu nimekirjas, isegi kui need asjad on

107
00:04:22,370 --> 00:04:26,770
kõik laiali kogu oma ühe või
oma kaks või oma neli gigabaiti operatiivmälu

108
00:04:26,770 --> 00:04:28,760
sees oma arvutist.

109
00:04:28,760 --> 00:04:33,230
>> Nii negatiivsed, siis on
seotud nimekirja on mis?

110
00:04:33,230 --> 00:04:34,670
Mis on hind, mida me oleme
ilmselt maksavad?

111
00:04:34,670 --> 00:04:36,010
>> Õpilane: [kuuldamatu].

112
00:04:36,010 --> 00:04:36,920
>> SPEAKER 1: Rohkem ruumi, eks?

113
00:04:36,920 --> 00:04:39,340
Me oleme selles asjas kahekordistunud summa
ruumi, sest oleme läinud

114
00:04:39,340 --> 00:04:43,500
32 bitti iga sõlme iga
int, nii et nüüd 64 bitti, sest peame

115
00:04:43,500 --> 00:04:45,050
hoida umbes pointer samuti.

116
00:04:45,050 --> 00:04:48,860
Sa saad rohkem efektiivsust kui oma struktuure
on suurem kui see lihtne asi.

117
00:04:48,860 --> 00:04:52,020
Kui sa tegelikult üliõpilane sees
mis on paari stringe

118
00:04:52,020 --> 00:04:55,430
nimi ja maja, võibolla ID number,
äkki mõned muudes valdkondades kokku.

119
00:04:55,430 --> 00:04:59,000
>> Nii et kui sul on piisavalt suur, struktuure,
siis võibolla maksumus osuti on

120
00:04:59,000 --> 00:05:00,010
mitte nii suur asi.

121
00:05:00,010 --> 00:05:03,570
See on natuke nurgas puhul selles
me ladustamiseks selline lihtne primitiivne

122
00:05:03,570 --> 00:05:04,760
sisemus seotud nimekirja.

123
00:05:04,760 --> 00:05:05,790
Aga point on sama.

124
00:05:05,790 --> 00:05:08,230
Sa oled kindlasti kulutusi rohkem
mälu, kuid sa saad

125
00:05:08,230 --> 00:05:08,990
paindlikkust.

126
00:05:08,990 --> 00:05:12,280
Sest nüüd, kui ma tahan lisada element
alguses see nimekiri,

127
00:05:12,280 --> 00:05:14,340
Mul on eraldada uus sõlm.

128
00:05:14,340 --> 00:05:17,180
Ja ma pean lihtsalt ajakohastada neid
nooled millegipärast just liikuvate

129
00:05:17,180 --> 00:05:17,980
mõned näpunäited ümber.

130
00:05:17,980 --> 00:05:20,580
>> Kui ma tahan lisada midagi arvesse
Keset nimekirja, ma ei pea

131
00:05:20,580 --> 00:05:24,410
push kõik kõrvale nagu me tegime
nädalat varem meie vabatahtlikke, kes

132
00:05:24,410 --> 00:05:25,700
esindatud massiivi.

133
00:05:25,700 --> 00:05:29,470
Võin lihtsalt eraldada uus sõlm ja
siis lihtsalt juhtida nooltega

134
00:05:29,470 --> 00:05:32,290
erinevates suundades, sest see ei
peavad jääma tegelik

135
00:05:32,290 --> 00:05:35,670
mälu tõsi liin nagu ma olen juhtinud
see siin ekraanil.

136
00:05:35,670 --> 00:05:38,400
>> Ja siis lõpuks, kui soovite sisestada
midagi lõpus nimekirja, see on

137
00:05:38,400 --> 00:05:39,210
isegi lihtsam.

138
00:05:39,210 --> 00:05:43,320
See on omamoodi omavoliline märke,
kuid 34 on pointer, peaksin arvama.

139
00:05:43,320 --> 00:05:46,710
Mis on väärtus selle osuti kõige
tõenäoliselt välja omamoodi nagu vana

140
00:05:46,710 --> 00:05:47,700
kooli antenn on?

141
00:05:47,700 --> 00:05:48,920
>> Õpilane: [kuuldamatu].

142
00:05:48,920 --> 00:05:49,900
>> SPEAKER 1: See on ilmselt null.

143
00:05:49,900 --> 00:05:52,710
Ja tõepoolest see on üks autori
esindatuse null.

144
00:05:52,710 --> 00:05:56,310
Ja see on null, sest sa absoluutselt
vaja teada, kust lõpuks lingitud

145
00:05:56,310 --> 00:06:00,050
Nimekiri on, muidu te ei hoia järgmine ja
järel ja pärast need nooled

146
00:06:00,050 --> 00:06:01,170
mõned prügi väärtus.

147
00:06:01,170 --> 00:06:06,230
Nii null, tähendab, et seal ei ole
rohkem tippe paremal number 34,

148
00:06:06,230 --> 00:06:07,200
käesolevas asjas.

149
00:06:07,200 --> 00:06:10,270
>> Seega teeme ettepaneku, et saame rakendada
Selle sõlme kood.

150
00:06:10,270 --> 00:06:12,130
Ja me oleme näinud sedalaadi
süntaks enne.

151
00:06:12,130 --> 00:06:15,090
Typedef lihtsalt määratleb uut tüüpi kohta
meid, annab meile sünonüüm nagu

152
00:06:15,090 --> 00:06:17,100
string oli char *.

153
00:06:17,100 --> 00:06:21,030
Antud juhul see läheb meile
stenografisti märke nii et struct sõlme

154
00:06:21,030 --> 00:06:24,010
võib selle asemel lihtsalt kirjutada
sõlme, mis on palju puhtam.

155
00:06:24,010 --> 00:06:25,360
See on palju vähem verbose.

156
00:06:25,360 --> 00:06:30,080
>> Toas sõlm on ilmselt int
nimetatakse n ja seejärel struct tipp *

157
00:06:30,080 --> 00:06:34,670
mis tähendab täpselt seda, mida me tahtsime
nooli tähendab, kursor teise

158
00:06:34,670 --> 00:06:36,940
sõlme täpselt sama andmetüüp.

159
00:06:36,940 --> 00:06:40,300
Ja ma teen ettepaneku, et me võiksime rakendada
otsingu funktsiooni niimoodi, mis on

160
00:06:40,300 --> 00:06:41,890
Esmapilgul võib tunduda,
veidi keeruline.

161
00:06:41,890 --> 00:06:43,330
Aga vaatame seda konteksti.

162
00:06:43,330 --> 00:06:45,480
>> Lubage mul minna üle seadme siin.

163
00:06:45,480 --> 00:06:48,460
Lubage mul avada fail nimega
nimekiri null dot h.

164
00:06:48,460 --> 00:06:53,950
Ja see sisaldab ainult määratlus me
nägin just hetk tagasi selle andmed

165
00:06:53,950 --> 00:06:55,390
tüüp kutsus sõlme.

166
00:06:55,390 --> 00:06:57,350
Nii et me panime seda arvesse dot h faili.

167
00:06:57,350 --> 00:07:01,430
>> Ja kõrvale, kuigi see
programmi, mida parasjagu näha on

168
00:07:01,430 --> 00:07:05,410
ei ole kõik nii keeruline, et see on tõepoolest
konventsiooni kui kirjalikult programmi

169
00:07:05,410 --> 00:07:10,270
asjad nagu andmetüübid, pull
konstandid mõnikord sees oma

170
00:07:10,270 --> 00:07:13,210
päisefailist ja mitte tingimata
oma C fail, kindlasti, kui teie

171
00:07:13,210 --> 00:07:17,370
programme saada suuremaks ja suuremaks, nii et
sa tead, kust otsida nii

172
00:07:17,370 --> 00:07:20,840
dokumentatsioon mõningatel juhtudel või
jaoks põhitõdesid nagu see,

173
00:07:20,840 --> 00:07:22,360
määratlus teatud tüüpi.

174
00:07:22,360 --> 00:07:25,680
>> Kui ma nüüd avada nimekiri null dot
c, märkate mõningaid asju.

175
00:07:25,680 --> 00:07:29,090
See sisaldab vähe header faili, kõige
millest me oleme näinud.

176
00:07:29,090 --> 00:07:31,980
See hõlmab oma header fail.

177
00:07:31,980 --> 00:07:35,200
>> Ja kõrvale, miks see on topelt
tsitaadid siin, mitte nurga

178
00:07:35,200 --> 00:07:38,340
Sulgudes on joon, mis
Olen rõhutanud seal?

179
00:07:38,340 --> 00:07:39,180
>> Õpilane: [kuuldamatu].

180
00:07:39,180 --> 00:07:40,460
>> SPEAKER 1: Jah, nii see on kohalik fail.

181
00:07:40,460 --> 00:07:44,300
Nii et kui see on kohalik fail oma siin
on line 15, näiteks, saate kasutada

182
00:07:44,300 --> 00:07:46,570
jutumärkide asemel
Euroopa noolsulge.

183
00:07:46,570 --> 00:07:48,270
>> Nüüd on see omamoodi huvitav.

184
00:07:48,270 --> 00:07:51,830
Pange tähele, et ma olen kuulutanud maailma
muutuja selles programmis on line 18

185
00:07:51,830 --> 00:07:55,910
kutsutud esimene, mille idee seisneb selles on
läheb osuti esimesse

186
00:07:55,910 --> 00:07:59,190
sõlm minu ahelloend, ja ma olen
käivitub see tühjaks, sest ma olen

187
00:07:59,190 --> 00:08:02,310
ei eraldatud ühtegi tegelikku
sõlmede veel.

188
00:08:02,310 --> 00:08:07,570
>> Nii et see esindab, piltlikult, mida me
nägin hetk tagasi pilt

189
00:08:07,570 --> 00:08:10,090
et osuti palju
vasakul pool.

190
00:08:10,090 --> 00:08:12,260
Nii kohe, et pointer
ei ole noolt.

191
00:08:12,260 --> 00:08:14,590
Selle asemel on lihtsalt null.

192
00:08:14,590 --> 00:08:17,880
Aga see tähendab, milline saab olema
aadress esimesed

193
00:08:17,880 --> 00:08:19,480
sõlme selles loetelus.

194
00:08:19,480 --> 00:08:22,120
Nii et ma olen rakendanud on ülemaailmne
sest, nagu te näete, kõik see

195
00:08:22,120 --> 00:08:25,310
Programm ei elus on rakendada
seotud nimekirja minu jaoks.

196
00:08:25,310 --> 00:08:27,050
>> Nüüd on mul mõned prototüübid siin.

197
00:08:27,050 --> 00:08:31,190
Ma otsustasin, et rakendada funktsioone, nagu
kustutamine, lisamine, otsimine ja

198
00:08:31,190 --> 00:08:31,740
läbipääsusüsteemid -

199
00:08:31,740 --> 00:08:35,210
viimane lihtsalt on kõndida üle
nimekirja, prindib selle elemente.

200
00:08:35,210 --> 00:08:36,750
Ja nüüd siin on mu peamine rutiinist.

201
00:08:36,750 --> 00:08:39,890
Ja me ei veedavad liiga palju aega
Nende sest see on omamoodi loodetavasti

202
00:08:39,890 --> 00:08:41,780
vana müts nüüd.

203
00:08:41,780 --> 00:08:45,370
>> Ma lähen tegema järgmised
kui kasutaja teeb.

204
00:08:45,370 --> 00:08:47,300
Nii et üks, ma lähen välja printida
läbi selle menüü.

205
00:08:47,300 --> 00:08:49,420
Ja ma olen vormindatud see nagu
puhtalt kui suutsin.

206
00:08:49,420 --> 00:08:52,240
Kui kasutaja liigid üks, mis tähendab,
nad tahavad kustutada midagi.

207
00:08:52,240 --> 00:08:54,560
Kui kasutaja liigid kaks, mis tähendab, et
nad tahavad, et lisada midagi.

208
00:08:54,560 --> 00:08:55,930
Ja nii edasi.

209
00:08:55,930 --> 00:08:58,270
Ma lähen siis küsi
siis käsk.

210
00:08:58,270 --> 00:08:59,300
Ja siis ma lähen kasutada GetInt.

211
00:08:59,300 --> 00:09:02,790
>> Nii et see on tõesti lihtne menuing
liides, kus sa lihtsalt tüüp

212
00:09:02,790 --> 00:09:05,270
number kaardistamise üks
nende käske.

213
00:09:05,270 --> 00:09:08,730
Ja nüüd on mul kena puhas switch
kinnitus, et läheb sisse lülitada

214
00:09:08,730 --> 00:09:10,090
olenemata kasutaja sisestatud sisse

215
00:09:10,090 --> 00:09:12,180
Ja kui nad kirjutada üks, siis ma
helistada kustutada ja murda.

216
00:09:12,180 --> 00:09:14,380
Kui nad kirjutasid kaks, ma
helistada sisestada ja murda.

217
00:09:14,380 --> 00:09:16,490
>> Ja nüüd märkate Olen panna iga
Nende ühel ja samal joonel.

218
00:09:16,490 --> 00:09:18,360
See on vaid stiililine otsus.

219
00:09:18,360 --> 00:09:20,210
Tavaliselt oleme näinud midagi
niimoodi.

220
00:09:20,210 --> 00:09:23,260
Aga ma otsustasin, ausalt, minu programmi
Vaatasin veel loetav, sest

221
00:09:23,260 --> 00:09:25,980
see oli ainult neli juhtumit
lihtsalt loetleda see niimoodi.

222
00:09:25,980 --> 00:09:28,360
Täiesti õigustatud kasutamist stiilis.

223
00:09:28,360 --> 00:09:31,480
Ja ma teen seda nii kaua, kui
kasutaja ei ole kirjutatud null, mida ma

224
00:09:31,480 --> 00:09:33,910
otsustas tähendab nad soovivad loobuda.

225
00:09:33,910 --> 00:09:36,630
>> Nüüd teate, mida ma olen
teeme siin.

226
00:09:36,630 --> 00:09:38,650
Ma lähen, et vabastada nimekiri ilmselt.

227
00:09:38,650 --> 00:09:40,230
Aga rohkem sellest vaid hetk.

228
00:09:40,230 --> 00:09:41,640
Vaatame kõigepealt käivitada see programm.

229
00:09:41,640 --> 00:09:45,250
Nii et lubage mul teha suurem terminal
akna dot kaldkriipsuga nimekiri 0.

230
00:09:45,250 --> 00:09:49,510
Ma lähen edasi minna ja sisestada poolt
kirjutades kaks, number nagu 50, ja nüüd

231
00:09:49,510 --> 00:09:51,590
näete nimekiri on nüüd 50.

232
00:09:51,590 --> 00:09:53,380
Ja minu tekst lihtsalt kerida natuke.

233
00:09:53,380 --> 00:09:55,940
Nüüd teate, kui loend sisaldab
number 50.

234
00:09:55,940 --> 00:09:58,220
>> Teeme veel lisada, võttes kaks.

235
00:09:58,220 --> 00:10:01,630
Olgem kirjuta number nagu üks.

236
00:10:01,630 --> 00:10:03,940
Nimekiri on nüüd üks, millele järgneb 50.

237
00:10:03,940 --> 00:10:06,020
Nii et see on lihtsalt tekstiline esitus
nimekirja.

238
00:10:06,020 --> 00:10:10,550
Ja olgem lisada veel üks number nagu
number 42, mis on loodetavasti

239
00:10:10,550 --> 00:10:14,620
läheb lõpuks keskel, sest
see programm eriti kehvasti see

240
00:10:14,620 --> 00:10:16,320
elemente nagu ta lisab neid.

241
00:10:16,320 --> 00:10:17,220
Nii et meil on see.

242
00:10:17,220 --> 00:10:20,730
Super lihtne programm, mis võiks
absoluutselt on kasutada massiivi, aga ma

243
00:10:20,730 --> 00:10:23,280
juhtub olema, kasutades seotud nimekirja
lihtsalt, et ma saaks dünaamiliselt

244
00:10:23,280 --> 00:10:24,610
kasvab ja kahaneb see.

245
00:10:24,610 --> 00:10:28,470
>> Võtame pilk otsinguks, kui ma
käivitada käsk kolm, ma tahan, et otsida

246
00:10:28,470 --> 00:10:31,040
, ütleme, number 43.

247
00:10:31,040 --> 00:10:34,190
Ja midagi oli ilmselt leidis,
sest ma sain tagasi mingit vastust.

248
00:10:34,190 --> 00:10:35,010
Teeme seda uuesti.

249
00:10:35,010 --> 00:10:35,690
Otsing.

250
00:10:35,690 --> 00:10:39,520
Otsime 50 või pigem otsida
42, mis on kena

251
00:10:39,520 --> 00:10:40,850
veidi peenem tähendus.

252
00:10:40,850 --> 00:10:42,610
Ja ma leidsin elu mõtte seal.

253
00:10:42,610 --> 00:10:44,990
Number 42, kui te ei tea,
viide, Google seda.

254
00:10:44,990 --> 00:10:45,350
Hea küll.

255
00:10:45,350 --> 00:10:47,130
Mis siis on see programm minu heaks teinud?

256
00:10:47,130 --> 00:10:50,660
See on lihtsalt võimaldanud mul sisestada seega
kaugelt ja otsida elemente.

257
00:10:50,660 --> 00:10:53,650
>> Lähme edasi, siis, et
et funktsioon me pilgu

258
00:10:53,650 --> 00:10:55,360
Esmaspäeval nagu teaser.

259
00:10:55,360 --> 00:10:59,620
Nii et see ülesanne, ma väita, otsingud
element nimekirjas esimesel

260
00:10:59,620 --> 00:11:03,830
üks, mis sunnib kasutaja ja siis helistades
GetInt saada tegelik int

261
00:11:03,830 --> 00:11:05,060
, mida soovite otsida.

262
00:11:05,060 --> 00:11:06,460
>> Siis teate seda.

263
00:11:06,460 --> 00:11:10,690
Ma lähen luua ajutise muutuja
vastavalt 188 kutsutud pointer -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
võinuks see midagi.

266
00:11:12,440 --> 00:11:16,140
Ja see on kursor sõlme
sest ma ütlesin sõlme * seal.

267
00:11:16,140 --> 00:11:19,900
Ja ma käivitumist see olema võrdne
esimene nii et ma tegelikult olema minu

268
00:11:19,900 --> 00:11:22,860
sõrme, nii et rääkida, on väga
esimene element nimekirjas.

269
00:11:22,860 --> 00:11:27,460
Nii et kui mu parem käsi siin on PTR Ma olen
juhtides samal asi et esimene

270
00:11:27,460 --> 00:11:28,670
on osutavad.

271
00:11:28,670 --> 00:11:31,430
>> Nüüd tagasi kood,
mis juhtub järgmisena -

272
00:11:31,430 --> 00:11:35,070
see on ühine paradigma kui iterating
üle struktuur nagu

273
00:11:35,070 --> 00:11:35,970
seotud nimekirja.

274
00:11:35,970 --> 00:11:40,410
Ma lähen tegema ajal järgmisi
osuti ei ole võrdne null Niisiis, kui

275
00:11:40,410 --> 00:11:47,530
minu sõrm ei osutades mõned null
väärtus, kui osuti nool n võrdub n.

276
00:11:47,530 --> 00:11:52,290
Me märkad esimesena, et n on mis
kasutaja tipitud kohta GetInts helistada siin.

277
00:11:52,290 --> 00:11:54,280
>> Ja pointer nool n tähendab mida?

278
00:11:54,280 --> 00:11:59,020
Noh, kui me tagasi minna pilt siin
kui mul on sõrme osutavad

279
00:11:59,020 --> 00:12:02,960
et esimese sõlme sisaldav üheksa,
nool tähendab sisuliselt minema, et

280
00:12:02,960 --> 00:12:08,860
sõlm ja haarata väärtus asukoha n,
sel juhul andmeväljale nimetatakse n.

281
00:12:08,860 --> 00:12:14,120
>> Nagu kõrvale - ja me nägime seda paar
nädalat tagasi, kui keegi küsis -

282
00:12:14,120 --> 00:12:18,840
Selle süntaks on uus, kuid see ei ole
annab meile volitused, et me

283
00:12:18,840 --> 00:12:20,040
ei ole veel.

284
00:12:20,040 --> 00:12:25,325
Mis oli selle fraasi kasutamisega võrdväärset
dot märke ja star paar

285
00:12:25,325 --> 00:12:29,490
nädalat tagasi, kui me kooritud tagasi
see kiht veidi enneaegselt?

286
00:12:29,490 --> 00:12:31,780
>> Õpilane: [kuuldamatu].

287
00:12:31,780 --> 00:12:38,880
>> SPEAKER 1: Just, see oli täht, ja
siis oli star dot n, kus

288
00:12:38,880 --> 00:12:41,930
sulud siia, mis näeb välja,
Ausalt, ma arvan, et palju

289
00:12:41,930 --> 00:12:43,320
rohkem segasena lugeda.

290
00:12:43,320 --> 00:12:46,270
Aga täht pointer, nagu alati,
vahendid sinna minna.

291
00:12:46,270 --> 00:12:49,090
Ja kui sa oled seal, milliseid andmeid
valdkonnas sa tahad pääseda?

292
00:12:49,090 --> 00:12:52,730
Noh te kasutate dot märke juurde
structs andmeväljale ja ma

293
00:12:52,730 --> 00:12:54,140
konkreetselt tahad n.

294
00:12:54,140 --> 00:12:56,240
>> Ausalt, ma väidan seda
on lihtsalt raskem lugeda.

295
00:12:56,240 --> 00:12:58,080
See on raskem meeles pidada, kui
ei sulgudes minna,

296
00:12:58,080 --> 00:12:59,030
täht ja kõik see.

297
00:12:59,030 --> 00:13:02,150
Nii maailma vastu mõned süntaktiline
suhkur, nii rääkida.

298
00:13:02,150 --> 00:13:04,740
Just seksikas viis öelda,
see on samaväärne, ja

299
00:13:04,740 --> 00:13:05,970
ehk rohkem intuitiivne.

300
00:13:05,970 --> 00:13:09,600
Kui osuti on tõepoolest pointer,
nool märke viisil sinna minna ja leida

301
00:13:09,600 --> 00:13:11,890
valdkonnas sel juhul nimetatakse n.

302
00:13:11,890 --> 00:13:13,660
>> Nii et kui ma leian ta, teate, mida ma teen.

303
00:13:13,660 --> 00:13:17,430
Ma lihtsalt välja printida, leidsin protsenti i,
kõrvaldamine on raha, et int.

304
00:13:17,430 --> 00:13:20,730
Kutsun magada üks teine ​​lihtsalt selline
Pauside asjad ekraanil

305
00:13:20,730 --> 00:13:22,900
anda kasutajale teine ​​absorbeerida
mis just juhtus.

306
00:13:22,900 --> 00:13:24,290
Ja siis ma murda.

307
00:13:24,290 --> 00:13:26,330
Muidu ma pean tegema?

308
00:13:26,330 --> 00:13:30,960
Ma värskendada kursor võrdne
pointer noolt.

309
00:13:30,960 --> 00:13:35,840
>> Nii lihtsalt, et oleks selge, see tähendab, minna
seal, kasutades minu vana kooli märke.

310
00:13:35,840 --> 00:13:39,580
Niisiis tähendab see lihtsalt seda, et minna ükskõik
olete osutades, mis on väga

311
00:13:39,580 --> 00:13:43,660
Esimesel juhul on Ma osutades
struct üheksa ta.

312
00:13:43,660 --> 00:13:44,510
Nii et ma olen käinud seal.

313
00:13:44,510 --> 00:13:47,880
Ja siis dot märke tähendab,
saada väärtus järgmine.

314
00:13:47,880 --> 00:13:50,470
>> Kuid raha, kuigi see on koostatud
kui kitsas, on lihtsalt number.

315
00:13:50,470 --> 00:13:51,720
See on numbriline aadress.

316
00:13:51,720 --> 00:13:55,670
Nii et see üks rida koodi, kas
kirjutatud niimoodi, rohkem segasena

317
00:13:55,670 --> 00:14:00,190
viis, või sellist, pisut rohkem
intuitiivne viis, tähendab lihtsalt liikuda mu käsi

318
00:14:00,190 --> 00:14:03,460
alates esimese sõlme kõrval üks,
ja siis järgmine ja siis

319
00:14:03,460 --> 00:14:05,320
kõrval üks, ja nii edasi.

320
00:14:05,320 --> 00:14:09,920
>> Nii et me ei tegele muu
rakendusi lisada ja kustutada

321
00:14:09,920 --> 00:14:14,030
ja läbipääsusüsteemid, kaks esimest
mis on üsna seotud.

322
00:14:14,030 --> 00:14:17,010
Ja ma arvan, et see on üsna lihtne saada
kaduma, kui teed seda suuliselt.

323
00:14:17,010 --> 00:14:19,890
Aga mida me teha saame, on siin
proovige teha kindlaks, kuidas

324
00:14:19,890 --> 00:14:21,640
parim teha seda visuaalselt.

325
00:14:21,640 --> 00:14:24,800
Kuna ma teen ettepaneku, et kui me
soovite lisada elemendid käesolevasse

326
00:14:24,800 --> 00:14:26,680
olemasolev loetelu, mis
on viis tegurit -

327
00:14:26,680 --> 00:14:29,530
9, 17, 22, 26 ja 33 -

328
00:14:29,530 --> 00:14:33,300
kui ma ei kavatse rakendada seda
kood, mul on vaja mõelda, kuidas edasi minna

329
00:14:33,300 --> 00:14:34,160
seda teed.

330
00:14:34,160 --> 00:14:37,720
>> Ja ma teen ettepaneku, võttes lapse sammud
kusjuures, sel juhul ma mõtlen, mis on

331
00:14:37,720 --> 00:14:41,090
võimalikke stsenaariume, et me
võib tekkida üldiselt?

332
00:14:41,090 --> 00:14:44,120
Rakendamisel infolehest seotud
nimekirja, see lihtsalt juhtub olema

333
00:14:44,120 --> 00:14:46,090
konkreetne näide suurus viis.

334
00:14:46,090 --> 00:14:50,420
Aga kui sa tahad sisestada number,
nagu öelda number üks, ja

335
00:14:50,420 --> 00:14:53,380
säilitades sorteeritud et vajaduse
ilmselt ei number üks pea

336
00:14:53,380 --> 00:14:55,686
mine selle konkreetse näite?

337
00:14:55,686 --> 00:14:56,840
Nagu alguses.

338
00:14:56,840 --> 00:15:00,030
>> Aga mis on huvitav on see, et
kui soovite lisada ühe sellesse

339
00:15:00,030 --> 00:15:04,100
nimekiri, mida erilist osuti peab
ajakohastada ilmselt?

340
00:15:04,100 --> 00:15:04,610
Esimene.

341
00:15:04,610 --> 00:15:07,830
Nii et ma väidan, et see on esimene juhtum
et me võiksite kaaluda,

342
00:15:07,830 --> 00:15:11,140
stsenaarium hõlmab lisades juures
loetelu alguses.

343
00:15:11,140 --> 00:15:15,400
>> Olgem sikutama off ehk kui lihtne või isegi
lihtsam juhul suhteliselt.

344
00:15:15,400 --> 00:15:18,110
Oletame, tahan lisada
number 35 in sorteeritud järjekorras.

345
00:15:18,110 --> 00:15:20,600
See ilmselt kuulub sinna.

346
00:15:20,600 --> 00:15:25,320
Mis siis osuti ilmselt läheb
tuleb ajakohastada, et stsenaarium?

347
00:15:25,320 --> 00:15:30,060
34 pointer muutub mitte null
kuid aadress struct

348
00:15:30,060 --> 00:15:31,800
sisaldavad number 35.

349
00:15:31,800 --> 00:15:32,750
Nii et juhul kaks.

350
00:15:32,750 --> 00:15:36,190
Nii juba, ma olen omamoodi Kvantimisplokk
kui palju tööd mul teha siin.

351
00:15:36,190 --> 00:15:39,880
>> Ja lõpuks, selge keskel puhul on
tõepoolest, keset, kui tahan

352
00:15:39,880 --> 00:15:45,870
sisestada midagi öelda 23, mis läheb
vahel 23 ja 26, kuid

353
00:15:45,870 --> 00:15:48,680
nüüd asju natuke rohkem
kaasatud, sest mida

354
00:15:48,680 --> 00:15:52,800
suunanäitajaks tuleb välja vahetada?

355
00:15:52,800 --> 00:15:56,680
Nii 22 ilmselt tuleb muuta
sest ta ei saa osutada 26 enam.

356
00:15:56,680 --> 00:16:00,320
Ta peab käsk uus sõlm, et
Võtan eraldada helistades

357
00:16:00,320 --> 00:16:01,770
malloc või mõnda samaväärset.

358
00:16:01,770 --> 00:16:05,990
>> Aga siis ma ka vaja, et uus sõlm, 23
Sellisel juhul on selle osuti

359
00:16:05,990 --> 00:16:07,870
osutades kellele?

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
Ja seal saab olema
tehetejärjekord siin.

362
00:16:10,380 --> 00:16:13,410
Sest kui ma teen seda rumalalt ja ma
näiteks start alguses

363
00:16:13,410 --> 00:16:16,040
nimekirja ning minu eesmärk on lisada 23.

364
00:16:16,040 --> 00:16:18,610
Ja ma saan vaadata, kas see kuulub
Siin lähedal üheksa?

365
00:16:18,610 --> 00:16:18,950
Ei.

366
00:16:18,950 --> 00:16:20,670
Kas see kuulub siin kõrval 17?

367
00:16:20,670 --> 00:16:20,940
Ei.

368
00:16:20,940 --> 00:16:22,530
Kas see kuulub siin kõrval 22?

369
00:16:22,530 --> 00:16:23,300
Jah.

370
00:16:23,300 --> 00:16:26,400
>> Nüüd, kui ma olen rumal siin, ja mitte
mõtlemine see läbi, ma võin

371
00:16:26,400 --> 00:16:28,320
eraldada minu uus sõlm 23.

372
00:16:28,320 --> 00:16:32,080
Ma võiks uuendada pointer
sõlme nimetatakse 22, juhtides

373
00:16:32,080 --> 00:16:33,080
see on uus sõlm.

374
00:16:33,080 --> 00:16:36,140
Ja mis ma siis pean uuendama
uus sõlm osuti olema?

375
00:16:36,140 --> 00:16:38,120
>> Õpilane: [kuuldamatu].

376
00:16:38,120 --> 00:16:38,385
>> SPEAKER 1: Täpselt.

377
00:16:38,385 --> 00:16:39,710
Osutades 26.

378
00:16:39,710 --> 00:16:45,590
Aga kurat võtaks, kui ma ei ole juba uuendada
22 pointer juhtida seda meest, ja

379
00:16:45,590 --> 00:16:48,260
nüüd mul on orvud, ülejäänud
nimekirja, nii rääkida.

380
00:16:48,260 --> 00:16:52,140
Nii et operatsioonide siin
saab olema oluline.

381
00:16:52,140 --> 00:16:55,100
>> Selleks võiks ma varastama
ütleme, kuus vabatahtlikku.

382
00:16:55,100 --> 00:16:57,650
Ja vaatame, kas me saame seda teha
visuaalselt asemel kood tark.

383
00:16:57,650 --> 00:16:59,330
Ja meil on mõned armas stress
pallid teile täna.

384
00:16:59,330 --> 00:17:02,510
OK, kuidas üks, kaks, on
tagasi - on lõpuks olemas.

385
00:17:02,510 --> 00:17:04,530
kolm, neli, teie mõlema
poisid lõpuks.

386
00:17:04,530 --> 00:17:05,579
Ja viis, kuus.

387
00:17:05,579 --> 00:17:05,839
Muidugi.

388
00:17:05,839 --> 00:17:06,450
Viis ja kuus.

389
00:17:06,450 --> 00:17:08,390
Olgu ja me tuleme
teiega järgmine kord.

390
00:17:08,390 --> 00:17:09,640
Olgu, tulge siia.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> Olgu, kuna sa oled siin esimene,
sa tahaksid olla üks kohmakalt

393
00:17:14,819 --> 00:17:16,119
Google Klaas here?

394
00:17:16,119 --> 00:17:19,075
Olgu nii, OK, klaas,
salvestada video.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
OK, sa oled hea minna.

397
00:17:24,589 --> 00:17:27,950
>> Olgu, kui te ei tule
siin olen eelnevalt ettevalmistatud

398
00:17:27,950 --> 00:17:30,110
mõned numbrid.

399
00:17:30,110 --> 00:17:31,240
Olgu, tule siia.

400
00:17:31,240 --> 00:17:33,440
Ja miks sa ei lähe natuke
edasi niimoodi.

401
00:17:33,440 --> 00:17:35,520
Ja vaatame, mis su nimi on,
Google Glass?

402
00:17:35,520 --> 00:17:35,910
>> Üliõpilane: Ben.

403
00:17:35,910 --> 00:17:36,230
>> SPEAKER 1: Ben?

404
00:17:36,230 --> 00:17:38,380
OK, Ben, siis esimene sõna otseses mõttes.

405
00:17:38,380 --> 00:17:40,580
Nii et me ei kavatse saata
et etapi lõpus.

406
00:17:40,580 --> 00:17:41,670
Olgu, ja teie nimi on?

407
00:17:41,670 --> 00:17:41,990
>> Üliõpilane: Jason.

408
00:17:41,990 --> 00:17:44,530
>> SPEAKER 1: Jason, OK teid
olema number üheksa.

409
00:17:44,530 --> 00:17:46,700
Nii et kui soovite jälgida Ben niimoodi.

410
00:17:46,700 --> 00:17:47,010
>> Üliõpilane: Jill.

411
00:17:47,010 --> 00:17:49,630
>> SPEAKER 1: Jill, sa lähed, et olla
17, mis siis, kui ma seda teinud veel

412
00:17:49,630 --> 00:17:51,260
arukalt, oleksin
alustas teises otsas.

413
00:17:51,260 --> 00:17:52,370
Sa minna nii.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
Ja teie olete?

416
00:17:53,670 --> 00:17:53,980
>> Üliõpilane: Mary.

417
00:17:53,980 --> 00:17:56,130
>> SPEAKER 1: Mary, on sul 22.

418
00:17:56,130 --> 00:17:58,420
Ja teie nimi on?

419
00:17:58,420 --> 00:17:58,810
>> Üliõpilane: Chris.

420
00:17:58,810 --> 00:18:00,100
>> SPEAKER 1: Chris, sa pead olema 26.

421
00:18:00,100 --> 00:18:00,740
Ja siis lõpuks.

422
00:18:00,740 --> 00:18:01,400
>> Üliõpilane: Diana.

423
00:18:01,400 --> 00:18:02,670
>> SPEAKER 1: Diana, sa pead olema 34.

424
00:18:02,670 --> 00:18:03,920
Nii et tulge siia.

425
00:18:03,920 --> 00:18:06,360
>> Olgu, nii täiuslik järjestatud
Tellimiseks juba.

426
00:18:06,360 --> 00:18:09,600
Ja olgem minna ja teha seda
nii et me saame tegelikult -

427
00:18:09,600 --> 00:18:11,720
Ben oled lihtsalt selline vaadates
viidud kusagil seal.

428
00:18:11,720 --> 00:18:15,670
OK, nii et lähme edasi ja kujutada seda
kasutada relvi, palju nagu ma olin, täpselt,

429
00:18:15,670 --> 00:18:16,250
mis toimub.

430
00:18:16,250 --> 00:18:19,540
Nii et laske käia ja andke iseendid
suu või kaks vahel ise.

431
00:18:19,540 --> 00:18:22,900
Ja minna ja juhtida ühe käega
kes sa tuleks osutades

432
00:18:22,900 --> 00:18:23,470
põhinevad.

433
00:18:23,470 --> 00:18:25,890
Ja kui sa oled null lihtsalt juhtida
otse alla põrandale.

434
00:18:25,890 --> 00:18:27,690
OK, nii hea.

435
00:18:27,690 --> 00:18:32,290
>> Nüüd on meil seotud nimekirja, ja lase mind
ettepaneku, et ma mängida rolli

436
00:18:32,290 --> 00:18:35,110
PTR, nii et ma ei viitsinud
kes selle ümber.

437
00:18:35,110 --> 00:18:37,830
Ja siis - keegi loll leping -
võite helistada see midagi, mida soovite -

438
00:18:37,830 --> 00:18:39,800
eelkäija pointer, pred pointer -

439
00:18:39,800 --> 00:18:43,930
see on lihtsalt hüüdnimi andsime sisse
meie proovi koodi mu vasak käsi.

440
00:18:43,930 --> 00:18:47,240
Teisest küljest, mis saab olema hoida
arvet, kes on kes

441
00:18:47,240 --> 00:18:48,400
järgmised stsenaariumid.

442
00:18:48,400 --> 00:18:52,390
>> Nii oletame, esiteks tahan sikutama off
et esimene näide paigaldamisel öelda

443
00:18:52,390 --> 00:18:54,330
20. osa loetellu.

444
00:18:54,330 --> 00:18:57,160
Nii et ma vajan kedagi, kes
kehastavad number 20 juures.

445
00:18:57,160 --> 00:18:58,950
Nii et ma vaja malloc keegi
saalist.

446
00:18:58,950 --> 00:18:59,380
Tule üles.

447
00:18:59,380 --> 00:19:00,340
Mis su nimi on?

448
00:19:00,340 --> 00:19:01,300
>> Üliõpilane: Brian.

449
00:19:01,300 --> 00:19:05,270
>> SPEAKER 1: Brian, eks, et sa
on sõlm, mis sisaldab 20.

450
00:19:05,270 --> 00:19:06,810
Olgu, tule siia.

451
00:19:06,810 --> 00:19:10,025
Ja loomulikult, kui
ei Brian kuuluvad?

452
00:19:10,025 --> 00:19:12,190
Niisiis, keset - tegelikult,
oodake minut.

453
00:19:12,190 --> 00:19:13,420
Me teeme seda rikkis.

454
00:19:13,420 --> 00:19:17,170
Me teeme seda palju raskem
kui see peaks olema esimene.

455
00:19:17,170 --> 00:19:21,210
OK, me läheme tasuta Brian
ja RealLOC Brian kui viis.

456
00:19:21,210 --> 00:19:23,680
>> OK, nii et nüüd me tahame lisada
Brian kui viis.

457
00:19:23,680 --> 00:19:25,960
Nii tule siia kõrvale
Ben hetkeks.

458
00:19:25,960 --> 00:19:28,250
Ja sa võid arvatavasti öelda
kus see lugu läheb.

459
00:19:28,250 --> 00:19:30,500
Kuid olgem hoolikalt mõelda
tehetejärjekord.

460
00:19:30,500 --> 00:19:32,880
Ja see on täpselt see visuaalne
et läheb rivistama

461
00:19:32,880 --> 00:19:34,080
selle proovi kood.

462
00:19:34,080 --> 00:19:40,120
Nii et siin ma olen PTR osutades esialgu
mitte Ben iseenesest, kuid mis iganes

463
00:19:40,120 --> 00:19:43,245
Väärtustame ta sisaldab, mis antud juhul
on - mis su nimi oligi?

464
00:19:43,245 --> 00:19:43,670
>> Üliõpilane: Jason.

465
00:19:43,670 --> 00:19:47,350
>> SPEAKER 1: Jason, et nii Ben ja mina
osutades Jason praegusel hetkel.

466
00:19:47,350 --> 00:19:49,700
Nüüd mul on võimalik kindlaks teha,
kus ei Brian kuuluvad?

467
00:19:49,700 --> 00:19:53,500
Nii et ainus asi, mida ma oleks juurdepääs
Praegu on tema n andmete element.

468
00:19:53,500 --> 00:19:58,280
Ma lähen, et kontrollida, kas
Brian alla Jason?

469
00:19:58,280 --> 00:19:59,770
Vastus on tõene.

470
00:19:59,770 --> 00:20:03,680
>> Mis siis nüüd peab juhtuma,
õiges järjekorras?

471
00:20:03,680 --> 00:20:07,120
Mul on vaja uuendada, kui palju viiteid
kokku selles loos?

472
00:20:07,120 --> 00:20:10,720
Kui mu käsi on endiselt vastakuti
Jason ja käsi - kui soovite, et

473
00:20:10,720 --> 00:20:12,930
pane oma käsi nagu, justkui, I
ei tea, küsimärk.

474
00:20:12,930 --> 00:20:14,070
OK, hea.

475
00:20:14,070 --> 00:20:15,670
>> Olgu, nii et teil on
vähe kandidaate.

476
00:20:15,670 --> 00:20:20,500
Kas Ben või I või Brian või Jason
või keegi teine, kes

477
00:20:20,500 --> 00:20:21,370
suunanäitajaks vaja muuta?

478
00:20:21,370 --> 00:20:23,260
Mitu kokku?

479
00:20:23,260 --> 00:20:24,080
>> OK, nii et kaks.

480
00:20:24,080 --> 00:20:27,090
Minu kursor ei ole tegelikult küsimus enam
sest ma olen lihtsalt ajutine.

481
00:20:27,090 --> 00:20:31,370
Seega on need kaks meest, arvatavasti,
nii Ben ja Brian.

482
00:20:31,370 --> 00:20:34,410
Nii et lubage mul ettepanek, et me värskendame
Ben, sest ta on esimene.

483
00:20:34,410 --> 00:20:36,350
Esimene element selle nimekirja
nüüd saab olema Brian.

484
00:20:36,350 --> 00:20:38,070
Nii Ben punktini Brian.

485
00:20:38,070 --> 00:20:39,320
OK, mis nüüd?

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> Kes saab märkida, kellele?

488
00:20:43,460 --> 00:20:44,710
>> Õpilane: [kuuldamatu].

489
00:20:44,710 --> 00:20:46,180
>> SPEAKER 1: OK, nii Brian on
punkti juures Jason.

490
00:20:46,180 --> 00:20:48,360
Aga ma olen kaotanud jälgida, et pointer?

491
00:20:48,360 --> 00:20:49,980
Kas ma tean, kui Jason on?

492
00:20:49,980 --> 00:20:50,790
>> Õpilane: [kuuldamatu].

493
00:20:50,790 --> 00:20:52,620
>> SPEAKER 1: mina, sest ma olen
ajutine pointer.

494
00:20:52,620 --> 00:20:55,110
Ja ilmselt ma ei ole muutunud
punkti juures uus sõlm.

495
00:20:55,110 --> 00:20:58,300
Nii saame lihtsalt Brian punkt
kell iganes ma osutavad.

496
00:20:58,300 --> 00:20:59,000
Ja me oleme valmis.

497
00:20:59,000 --> 00:21:01,890
Nii kui üks, sisestamise juures
loetelu alguses.

498
00:21:01,890 --> 00:21:02,950
Seal oli kaks olulist sammu.

499
00:21:02,950 --> 00:21:06,750
Üks, peame ajakohastama Ben ja seejärel
meil on ka ajakohastada Brian.

500
00:21:06,750 --> 00:21:09,230
Ja siis ma ei pea vaeva nägema
traipsing läbi ülejäänud

501
00:21:09,230 --> 00:21:12,680
nimekirja, sest me juba leidnud oma
asukohta, sest ta kuulus

502
00:21:12,680 --> 00:21:14,080
vasakule esimene element.

503
00:21:14,080 --> 00:21:15,400
>> Olgu, päris lihtne.

504
00:21:15,400 --> 00:21:18,110
Tegelikult tundub, nagu me oleme peaaegu
muuta see liiga keeruline.

505
00:21:18,110 --> 00:21:20,240
Teeme nüüd sikutama ära lõpuks
nimekirja ja vaata, kus

506
00:21:20,240 --> 00:21:21,380
keerukus hakkab.

507
00:21:21,380 --> 00:21:24,560
Nii et kui nüüd, ma alloc saalist.

508
00:21:24,560 --> 00:21:25,540
Igaüks taha mängida 55?

509
00:21:25,540 --> 00:21:26,700
Olgu, ma nägin oma käsi esimene.

510
00:21:26,700 --> 00:21:29,620
Tule üles.

511
00:21:29,620 --> 00:21:30,030
Jah.

512
00:21:30,030 --> 00:21:31,177
Mis su nimi on?

513
00:21:31,177 --> 00:21:32,310
>> Õpilane: [kuuldamatu].

514
00:21:32,310 --> 00:21:33,240
>> SPEAKER 1: Habata.

515
00:21:33,240 --> 00:21:33,890
OK, tulge siia.

516
00:21:33,890 --> 00:21:35,730
Sul on number 55.

517
00:21:35,730 --> 00:21:37,820
Nii et loomulikult kuuluvad
lõpus nimekirja.

518
00:21:37,820 --> 00:21:41,850
Teeme kordus simulatsiooni mind
on PTR hetkeks.

519
00:21:41,850 --> 00:21:44,050
Nii et ma olen esimene läheb näpuga
mis iganes Ben osutavad.

520
00:21:44,050 --> 00:21:45,900
Me mõlemad osutavad praegu Brian.

521
00:21:45,900 --> 00:21:48,420
Nii 55 on vähemalt viis.

522
00:21:48,420 --> 00:21:52,510
Nii et ma lähen uuendada ise poolt
osutades Brian järgmise pointer, kes

523
00:21:52,510 --> 00:21:54,450
nüüd on muidugi Jason.

524
00:21:54,450 --> 00:21:57,310
55 on vähemalt üheksa, nii
Ma lähen uuendada PTR.

525
00:21:57,310 --> 00:21:58,890
Ma lähen uuendada PTR.

526
00:21:58,890 --> 00:22:02,290
Ma lähen uuendada PTR
Ma lähen uuendada PTR.

527
00:22:02,290 --> 00:22:05,060
Ja ma lähen - hmm, mis
su nimi oligi?

528
00:22:05,060 --> 00:22:05,560
>> Üliõpilane: Diana.

529
00:22:05,560 --> 00:22:09,190
>> SPEAKER 1: Diana on suunatud muidugi
kell null temaga vasaku käega.

530
00:22:09,190 --> 00:22:13,030
Nii et kui ei Habata tegelikult
kuuluvad selgelt?

531
00:22:13,030 --> 00:22:15,050
Vasakul siin.

532
00:22:15,050 --> 00:22:19,460
Niisiis, kuidas ma tean, et panna teda siin
Ma arvan, et ma olen segane.

533
00:22:19,460 --> 00:22:22,420
Sest see, mis on PTR kunst
Sel hetkel kasutab?

534
00:22:22,420 --> 00:22:23,240
Null.

535
00:22:23,240 --> 00:22:25,580
Nii et kuigi visuaalselt, saame
ilmselt näha kõiki neid

536
00:22:25,580 --> 00:22:26,610
poisid siin laval.

537
00:22:26,610 --> 00:22:29,680
Ma ei ole hoida silma peal eelmise
Isiku nimekirja.

538
00:22:29,680 --> 00:22:33,210
Mul ei ole sõrmega osutades,
sel juhul sõlme number 34.

539
00:22:33,210 --> 00:22:34,760
>> Teeme tegelikult alustada seda üle.

540
00:22:34,760 --> 00:22:37,560
Nüüd ma tegelikult ei vaja
teine ​​kohalik muutuja.

541
00:22:37,560 --> 00:22:40,980
Ja see on see, mida näete
tegeliku valimi C kood, kus, kui ma lähen,

542
00:22:40,980 --> 00:22:45,860
kui ma update minu paremal käel juhtida
Jason, jättes Brian taga, ma

543
00:22:45,860 --> 00:22:51,440
parem hakata kasutama oma vasakut kätt
ajakohastada, kus ma olin, nii et kui ma lähen

544
00:22:51,440 --> 00:22:52,700
läbi selle nimekirja -

545
00:22:52,700 --> 00:22:55,040
rohkem kohmakalt kui ma ette
nüüd siin visuaalselt -

546
00:22:55,040 --> 00:22:56,740
Ma lähen, et saada
nimekirja lõppu.

547
00:22:56,740 --> 00:23:00,020
>> See käsi on ikka null, mis on päris
kasutu, välja arvatud, et näidata

548
00:23:00,020 --> 00:23:02,980
Ma olen selgelt lõpus nimekirja
aga nüüd vähemalt on mul see

549
00:23:02,980 --> 00:23:08,270
eelkäija osuti osutab siin, nii
mis nüüd käed ja mida suunanäitajaks vaja

550
00:23:08,270 --> 00:23:10,150
tuleb ajakohastada?

551
00:23:10,150 --> 00:23:13,214
Kelle poolt sa tahad
reconfigure esimesena?

552
00:23:13,214 --> 00:23:15,190
>> Õpilane: [kuuldamatu].

553
00:23:15,190 --> 00:23:16,220
>> SPEAKER 1: OK, nii et Diana.

554
00:23:16,220 --> 00:23:21,110
Kui sa tahad, et juhtida
Diana vasakul pointer?

555
00:23:21,110 --> 00:23:23,620
Kell 55, arvatavasti, et
oleme sisestatud seal.

556
00:23:23,620 --> 00:23:25,560
Ja kui peaks 55 pointer minna?

557
00:23:25,560 --> 00:23:27,000
Alla esindava null.

558
00:23:27,000 --> 00:23:28,890
Ja minu käed, sel hetkel, ei
oluline, sest nad olid lihtsalt

559
00:23:28,890 --> 00:23:30,070
ajutised muutujad.

560
00:23:30,070 --> 00:23:31,030
Nüüd me oleme valmis.

561
00:23:31,030 --> 00:23:34,650
>> Nii keerukust seal - ja
see ei ole nii raske rakendada,

562
00:23:34,650 --> 00:23:38,660
kuid me peame teisene muutuja teha
et enne, kui ma liikuda mu õigus

563
00:23:38,660 --> 00:23:42,140
aga ma update väärtus minu vasak
küljest pred pointer sel juhul nii

564
00:23:42,140 --> 00:23:45,860
et mul tagumisel pointer
jälgida, kus ma olin.

565
00:23:45,860 --> 00:23:49,360
Nüüd kui kõrvale, kui sa mõtled seda
läbi, see tunne, et see on

566
00:23:49,360 --> 00:23:51,490
natuke tüütu on, et hoida
jälgida seda vasaku käega.

567
00:23:51,490 --> 00:23:54,015
>> Mis oleks teine ​​lahendus
see probleem on?

568
00:23:54,015 --> 00:23:56,500
Kui sul ümber kujundada andmed
struktuur me räägime

569
00:23:56,500 --> 00:23:59,630
läbi kohe?

570
00:23:59,630 --> 00:24:02,690
Kui see lihtsalt omamoodi tunneb vähe
tüütud on, nagu, kaks viiteid

571
00:24:02,690 --> 00:24:08,430
läbimas nimekiri, kes veel võiks
on, Ideaalses maailmas, säilitada

572
00:24:08,430 --> 00:24:10,160
informatsiooni, mida me vajame?

573
00:24:10,160 --> 00:24:11,360
Jah?

574
00:24:11,360 --> 00:24:12,610
>> Õpilane: [kuuldamatu].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> SPEAKER 1: Täpselt.

577
00:24:16,150 --> 00:24:19,130
Just nii seal on tegelikult huvitav
idud idee.

578
00:24:19,130 --> 00:24:22,470
Ja see idee eelmine pointer,
osutades eelmine element.

579
00:24:22,470 --> 00:24:25,580
Mis siis, kui ma lihtsalt kehastab et
sisemus nimekirjaga?

580
00:24:25,580 --> 00:24:27,810
Ja see saab olema raske visualiseerida
see ilma kogu paber

581
00:24:27,810 --> 00:24:28,830
kukkumist põrandale.

582
00:24:28,830 --> 00:24:31,860
Aga oletame, et need kutid kasutada nii
nende käed on eelmise

583
00:24:31,860 --> 00:24:35,950
pointer, ja järgmise pointer, mis
rakendamisel, mida me kutsume kahekordselt

584
00:24:35,950 --> 00:24:36,830
seotud nimekirja.

585
00:24:36,830 --> 00:24:41,090
See võimaldaks mind omamoodi tagasikerimiseks
palju kergem ilma minuta,

586
00:24:41,090 --> 00:24:43,800
programmeerija, võttes hoida
jälitada käsitsi -

587
00:24:43,800 --> 00:24:44,980
tõesti käsitsi -

588
00:24:44,980 --> 00:24:47,280
kus ma ei olnud varem
nimekirjas.

589
00:24:47,280 --> 00:24:48,110
Nii et me ei tee seda.

590
00:24:48,110 --> 00:24:50,950
Hoiame seda lihtsalt sellepärast, et see on
tulemas hinnaga, kaks korda

591
00:24:50,950 --> 00:24:53,450
palju ruumi suunanäitajaks,
kui sa tahad teist.

592
00:24:53,450 --> 00:24:55,760
Aga see on tõesti ühine
andmete struktuuri, mida

593
00:24:55,760 --> 00:24:57,410
kahekordselt seotud nimekirja.

594
00:24:57,410 --> 00:25:01,310
>> Teeme lõplik näiteks siin ja pane
need poisid välja oma viletsuses.

595
00:25:01,310 --> 00:25:03,270
Nii malloc 20.

596
00:25:03,270 --> 00:25:05,320
Tule üles vahekäiku seal.

597
00:25:05,320 --> 00:25:06,280
Olgu, mis su nimi on?

598
00:25:06,280 --> 00:25:07,440
>> Õpilane: [kuuldamatu].

599
00:25:07,440 --> 00:25:07,855
>> SPEAKER 1: Vabandust?

600
00:25:07,855 --> 00:25:08,480
>> Õpilane: [kuuldamatu].

601
00:25:08,480 --> 00:25:09,410
>> SPEAKER 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
OK tulge siia.

603
00:25:10,230 --> 00:25:11,910
Sul peab olema 20.

604
00:25:11,910 --> 00:25:14,720
Sa ilmselt ei kavatse
kuuluvad 17-22.

605
00:25:14,720 --> 00:25:16,150
Nii et lubage mul õppida oma õppetund.

606
00:25:16,150 --> 00:25:18,150
Ma hakkan pointer
osutades Brian.

607
00:25:18,150 --> 00:25:21,190
Ja ma lähen on minu vasak käsi
ainult värskendada Brian nagu ma liikuda

608
00:25:21,190 --> 00:25:23,600
Jason, kontrolli kas 20 alla üheksa?

609
00:25:23,600 --> 00:25:24,060
Ei.

610
00:25:24,060 --> 00:25:25,430
Kas 20 on alla 17?

611
00:25:25,430 --> 00:25:25,880
Ei.

612
00:25:25,880 --> 00:25:27,450
Kas 20 on alla 22?

613
00:25:27,450 --> 00:25:28,440
Jah.

614
00:25:28,440 --> 00:25:34,070
Mis siis osuti või käsi vaja muuta
kus nad osutavad nüüd?

615
00:25:34,070 --> 00:25:37,070
>> Nii et me saame teha 17 osutades 20.

616
00:25:37,070 --> 00:25:37,860
Nii et pole midagi.

617
00:25:37,860 --> 00:25:40,080
Kui me tahame juhtida
kursor nüüd?

618
00:25:40,080 --> 00:25:41,330
Kell 22.

619
00:25:41,330 --> 00:25:45,410
Ja me teame, kus 22 on jällegi tänu
minu ajutine pointer.

620
00:25:45,410 --> 00:25:46,760
Nii et me oleme OK seal.

621
00:25:46,760 --> 00:25:49,440
Niisiis, kuna see ajutine ladustamine
Olen hoida silma peal, kus kõik on.

622
00:25:49,440 --> 00:25:55,055
Ja nüüd saab visuaalselt minna kus
te kuulute, ja nüüd on meil vaja 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 stress pallid,
ning aplaus

624
00:25:58,410 --> 00:25:59,770
need kutid, kui saime.

625
00:25:59,770 --> 00:26:00,410
Ilusti tehtud.

626
00:26:00,410 --> 00:26:05,320
>> [APLAUS]

627
00:26:05,320 --> 00:26:06,330
>> SPEAKER 1: Olgu.

628
00:26:06,330 --> 00:26:09,860
Ja te võite hoida tükki
paber nagu mälestusesemete.

629
00:26:09,860 --> 00:26:15,930
>> Olgu nii, usalda mind see on palju
lihtsam kõndida läbi, et koos

630
00:26:15,930 --> 00:26:17,680
inimesele, kui see on tegelike kood.

631
00:26:17,680 --> 00:26:22,690
Aga mida sa leiad vaid hetk
nüüd on see, et sama - oh, aitäh.

632
00:26:22,690 --> 00:26:23,630
Aitäh -

633
00:26:23,630 --> 00:26:29,360
on see, et sa leiad, et samu andmeid
struktuur, mis on seotud nimekirja, võib tegelikult

634
00:26:29,360 --> 00:26:33,200
kasutada alustalana veelgi
keerukamaid andmestruktuurid.

635
00:26:33,200 --> 00:26:37,620
>> Ja realiseerida liiga teema on see, et
oleme absoluutselt kasutusele rohkem

636
00:26:37,620 --> 00:26:40,060
keerukamaks rakendamine
Selle algoritmi.

637
00:26:40,060 --> 00:26:43,940
Sisestamisel ja kui me läksime läbi see,
kustutamine ja otsimine, on vähe

638
00:26:43,940 --> 00:26:46,660
keerulisem kui
oli massiivi.

639
00:26:46,660 --> 00:26:48,040
Aga me saame mõned dünaamilisus.

640
00:26:48,040 --> 00:26:50,180
Me saame adaptiivne andmestruktuur.

641
00:26:50,180 --> 00:26:54,010
>> Aga jälle, me maksame hind teatav
täiendavat keerukust nii

642
00:26:54,010 --> 00:26:54,910
rakendamisel.

643
00:26:54,910 --> 00:26:56,750
Ja me loobunud muutmälu.

644
00:26:56,750 --> 00:27:00,450
Ja kui aus olla, siis ei ole mõne kena
puhas slide võin teile anda, et

645
00:27:00,450 --> 00:27:03,120
ütleb siin ongi seotud nimekirja
on parem kui massiivi.

646
00:27:03,120 --> 00:27:04,100
Ja jätke see seda.

647
00:27:04,100 --> 00:27:07,520
Kuna teema reoccurring nüüd, isegi
seda enam, et lähinädalatel on

648
00:27:07,520 --> 00:27:10,200
et seal ei ole tingimata
õige vastus.

649
00:27:10,200 --> 00:27:13,830
>> See on põhjus, miks meil on eraldi telg
projekteerimise jaoks probleem komplekti.

650
00:27:13,830 --> 00:27:17,700
See saab olema väga konteksti
kas soovite kasutada neid andmeid

651
00:27:17,700 --> 00:27:21,750
struktuur või et üks, ja see tahe
sõltub sellest, mida teie jaoks tähtis nii

652
00:27:21,750 --> 00:27:24,620
ressursside ja keerukust.

653
00:27:24,620 --> 00:27:28,830
>> Aga lubage mul ettepanek, et ideaalne andmed
struktuur, Püha Graal, oleks

654
00:27:28,830 --> 00:27:32,200
midagi, mis on pidevas ajal
olenemata sellest, kui palju asju on

655
00:27:32,200 --> 00:27:36,940
sees, kas ei oleks hämmastav, kui
andmestruktuur tagastatakse vastuseid

656
00:27:36,940 --> 00:27:37,920
konstantse ajaga.

657
00:27:37,920 --> 00:27:38,330
Jah.

658
00:27:38,330 --> 00:27:40,110
See sõna on oma tohutu sõnastik.

659
00:27:40,110 --> 00:27:41,550
Või ei ole see sõna ei ole.

660
00:27:41,550 --> 00:27:43,270
Või mõni selline probleem olemas.

661
00:27:43,270 --> 00:27:46,360
Noh vaatame, kui me ei saa vähemalt
astuda samm lähemale sellele.

662
00:27:46,360 --> 00:27:50,190
>> Lubage mul esitada uus andmestruktuur
võib kasutada erinevaid asju,

663
00:27:50,190 --> 00:27:52,260
sel juhul nimetatakse hash tabelis.

664
00:27:52,260 --> 00:27:55,590
Ja nii me tegelikult tagasi põrkav
kell massiivi, antud juhul, ja

665
00:27:55,590 --> 00:28:00,550
mõnevõrra meelevaldselt, olen juhtinud seda
hash tabelit massiivi omamoodi

666
00:28:00,550 --> 00:28:02,810
kahemõõtmeline massiiv -

667
00:28:02,810 --> 00:28:05,410
või pigem see siin on kujutatud kui kaks
mõõtmeline massiiv - kuid see on lihtsalt

668
00:28:05,410 --> 00:28:10,770
massiivi suurus 26, nii et kui me
helistada massiivi, laud sulg

669
00:28:10,770 --> 00:28:12,440
null on ristküliku tipus.

670
00:28:12,440 --> 00:28:15,090
Tabel sulg 25 on ristküliku
allosas.

671
00:28:15,090 --> 00:28:18,620
Ja see on, kuidas ma võiks teha andmebaasi
konstruktsioon, kus ma tahan salvestada

672
00:28:18,620 --> 00:28:19,790
inimeste nimesid.

673
00:28:19,790 --> 00:28:24,370
>> Nii näiteks, ja ma ei tarbi
kogu see asi siin on õhuliinid, kui ma

674
00:28:24,370 --> 00:28:29,160
oli see massiiv, mis ma nüüd lähen
helistada hash tabel ja see on jälle

675
00:28:29,160 --> 00:28:31,360
Asukoht null.

676
00:28:31,360 --> 00:28:34,840
See siin on asukoht
üks, ja nii edasi.

677
00:28:34,840 --> 00:28:37,880
Väidan, et ma tahan kasutada neid andmeid
struktuuri huvides arutelu,

678
00:28:37,880 --> 00:28:42,600
salvestada inimeste nimesid, Alice ja Bob
ja Charlie ja muud sellised nimed.

679
00:28:42,600 --> 00:28:46,110
Nii et mõtle selle nüüd algused
, ütleme, sõnastik

680
00:28:46,110 --> 00:28:47,520
kus on palju sõnu.

681
00:28:47,520 --> 00:28:49,435
Nad juhtub olema nimed
Meie näites siin.

682
00:28:49,435 --> 00:28:52,560
Ja see on kõik liiga Sobiv võib-olla ka
rakendamisel õigekirjakontrolli, nagu me

683
00:28:52,560 --> 00:28:54,400
võib jaoks probleem määrata kuus.

684
00:28:54,400 --> 00:28:59,300
>> Nii et kui meil on massiivi kogupindalaga 26
nii, et see on 25. asukoht

685
00:28:59,300 --> 00:29:03,390
allosas, ja ma väita, et Alice on
esimene sõna sõnaraamatus

686
00:29:03,390 --> 00:29:07,260
nimed, et ma tahan lisada RAM,
sellesse andmestruktuur, kus on

687
00:29:07,260 --> 00:29:12,480
instinktid ütlen teile, et Alice'i
nimi peaks minema selle massiivi?

688
00:29:12,480 --> 00:29:13,510
>> Meil on 26 võimalusi.

689
00:29:13,510 --> 00:29:14,990
Kui me tahame, et panna teda?

690
00:29:14,990 --> 00:29:16,200
Me tahame teda sulg null, eks?

691
00:29:16,200 --> 00:29:18,280
Alice, kutsume seda null.

692
00:29:18,280 --> 00:29:20,110
Ja B on üks, ja C on kaks.

693
00:29:20,110 --> 00:29:22,600
Nii et me ei kavatse kirjutada
Alice'i nimi siia.

694
00:29:22,600 --> 00:29:24,890
Kui me siis sisesta Bob, tema
nimi läheb siin.

695
00:29:24,890 --> 00:29:27,280
Charlie läheb siin.

696
00:29:27,280 --> 00:29:30,500
Ja nii edasi ette läbi
see andmestruktuur.

697
00:29:30,500 --> 00:29:32,090
>> See on suurepärane andmestruktuur.

698
00:29:32,090 --> 00:29:32,730
Miks?

699
00:29:32,730 --> 00:29:37,460
Noh, mis on töötamise aeg
sisestades inimese nime sellesse

700
00:29:37,460 --> 00:29:39,850
andmestruktuur kohe?

701
00:29:39,850 --> 00:29:43,702
Arvestades, et see tabel on rakendatud,
tõesti, kui massiiv.

702
00:29:43,702 --> 00:29:44,940
Noh see on pidev aja.

703
00:29:44,940 --> 00:29:45,800
See, et üks.

704
00:29:45,800 --> 00:29:46,360
Miks?

705
00:29:46,360 --> 00:29:48,630
>> Noh, kuidas sa kindlaks
kus Alice kuulub?

706
00:29:48,630 --> 00:29:51,000
Sa vaata, mis kirjas tema nimi?

707
00:29:51,000 --> 00:29:51,490
Esimene.

708
00:29:51,490 --> 00:29:54,350
Ja saad seal, kui see on string,
lihtsalt vaadata string

709
00:29:54,350 --> 00:29:55,200
sulg null.

710
00:29:55,200 --> 00:29:57,110
Nii nullis iseloomu string.

711
00:29:57,110 --> 00:29:57,610
See on lihtne.

712
00:29:57,610 --> 00:30:00,350
Me tegime seda krüpto
loovutamise nädalat tagasi.

713
00:30:00,350 --> 00:30:05,310
Ja siis, kui sa tead, et Alice'i
kirjas on kapitali, saame lahutama

714
00:30:05,310 --> 00:30:08,160
välja 65 või kapitali ise,
mis annab meile null.

715
00:30:08,160 --> 00:30:10,940
Nii et me teame nüüd, et Alice kuulub
Kohapeal null.

716
00:30:10,940 --> 00:30:14,240
>> Ja arvestades osuti sellele andmed
struktuur, mingisugune, kui kaua

717
00:30:14,240 --> 00:30:18,840
see mind leida asukoht
nulli massiivi?

718
00:30:18,840 --> 00:30:22,080
Lihtsalt üks samm, eks see on konstantne aeg
sest muutmälu me

719
00:30:22,080 --> 00:30:23,780
Kavandatud oli funktsioon massiivi.

720
00:30:23,780 --> 00:30:28,570
Nii lühike, figuring mida indeks
Alice'i nimi on, mis on

721
00:30:28,570 --> 00:30:32,610
Sel juhul ei või olgem lihtsalt lahendada
et nulliga, kus B on üks ja C on

722
00:30:32,610 --> 00:30:34,900
kaks, selgitades, et välja
on konstantne aeg.

723
00:30:34,900 --> 00:30:38,510
Ma pean vaatama oma esimese kirja,
figuring kus null on

724
00:30:38,510 --> 00:30:40,460
massiiv on ka pidevalt aega.

725
00:30:40,460 --> 00:30:42,140
Nii tehniliselt see on
nagu kaks sammu nüüd.

726
00:30:42,140 --> 00:30:43,330
Aga see on ikka samaks.

727
00:30:43,330 --> 00:30:46,880
Nii me nimetame et suur O ühe, nii et me oleme
sisestatud Alice sellesse tabelisse

728
00:30:46,880 --> 00:30:48,440
konstantse ajaga.

729
00:30:48,440 --> 00:30:50,960
>> Aga muidugi, ma oleks
naiivne siin, eks?

730
00:30:50,960 --> 00:30:53,240
Mis siis, kui seal on Aaron klassis?

731
00:30:53,240 --> 00:30:53,990
Või Alicia?

732
00:30:53,990 --> 00:30:57,230
Või muud nimed algavad
A. Kuhu me läheme üles

733
00:30:57,230 --> 00:31:00,800
et inimene, eks ole?

734
00:31:00,800 --> 00:31:03,420
Ma mõtlen, et praegu on ainult kolm
inimesed lauale, nii et võib-olla me

735
00:31:03,420 --> 00:31:07,490
tuleks panna Aaron saabus
null üks kaks kolm.

736
00:31:07,490 --> 00:31:09,480
>> Just, ma võiksin panna siia.

737
00:31:09,480 --> 00:31:13,350
Aga siis, kui me püüame lisada Taaveti
see nimekiri, kus Taavet minna?

738
00:31:13,350 --> 00:31:15,170
Nüüd meie süsteem hakkab purustamine
maha, eks?

739
00:31:15,170 --> 00:31:19,210
Sest nüüd David jõuab siia
Kui Aaron on tegelikult siin.

740
00:31:19,210 --> 00:31:23,060
Ja nüüd kogu see idee, millel
puhas andmestruktuur, mis annab meile

741
00:31:23,060 --> 00:31:28,010
pidev aja sisestamisel ei ole enam
pidev ajal sest ma pean

742
00:31:28,010 --> 00:31:31,240
vaadake, oh, damnit, keegi on juba
Alice asukohast.

743
00:31:31,240 --> 00:31:35,320
>> Lubage mul sondi ülejäänud seda andmed
struktuur, otsin kohapeal üles

744
00:31:35,320 --> 00:31:37,130
keegi nagu Aaroni nimi.

745
00:31:37,130 --> 00:31:39,390
Ja nii, et liiga on hakanud
võtta lineaarne aeg.

746
00:31:39,390 --> 00:31:42,710
Pealegi, kui sa nüüd tahad leida
Aaron selles andmestruktuur, ja sa

747
00:31:42,710 --> 00:31:45,430
vaadake, ja Aaroni nimi ei ole siin.

748
00:31:45,430 --> 00:31:47,960
Ideaalis oleks lihtsalt öelda Aaroni
ei andmestruktuur.

749
00:31:47,960 --> 00:31:51,530
Aga kui sa hakata ruumi
Aaron, kus oleks pidanud olema D

750
00:31:51,530 --> 00:31:55,600
või E, teid, halvimal juhul pead kontrollima
Kogu info konstruktsioon

751
00:31:55,600 --> 00:31:59,480
mille puhul devolves midagi
lineaarne suurus tabelis.

752
00:31:59,480 --> 00:32:00,920
>> Nii et kõik õige, ma ajan asja korda.

753
00:32:00,920 --> 00:32:04,200
Probleem on selles, et mul oli
26 elementi see massiiv.

754
00:32:04,200 --> 00:32:05,000
Lubage mul seda muuta.

755
00:32:05,000 --> 00:32:06,010
Oih.

756
00:32:06,010 --> 00:32:10,600
Lubage mul seda muuta nii, et pigem heaolu
suurus 26 kokku märka alt

757
00:32:10,600 --> 00:32:12,720
indeks on muutu kuni n miinus 1.

758
00:32:12,720 --> 00:32:16,610
Kui 26 on selgelt liiga väike inimesele "
nimesid, sest seal on tuhandeid

759
00:32:16,610 --> 00:32:20,830
nimed maailmas, lähme lihtsalt
100 või 1000 või 10000.

760
00:32:20,830 --> 00:32:22,960
Olgem lihtsalt eraldada palju rohkem ruumi.

761
00:32:22,960 --> 00:32:27,230
>> Noh, et ei pruugi väheneda
tõenäosus, et me ei pea kaks

762
00:32:27,230 --> 00:32:31,510
inimeste nimed algavad ja
Niisiis, te ei kavatse proovida panna

763
00:32:31,510 --> 00:32:33,120
nimede asukohta null ikka.

764
00:32:33,120 --> 00:32:36,850
Nad ikka läheb kokku põrkavad, mis
tähendab, et meil on vaja veel lahendus panna

765
00:32:36,850 --> 00:32:41,020
Alice ja Aaron ja Alicia ja muu
nimed algavad mujal.

766
00:32:41,020 --> 00:32:43,460
Aga kuidas suur probleem see on?

767
00:32:43,460 --> 00:32:46,870
Milline on tõenäosus, et sa
on kokkupõrked andmed

768
00:32:46,870 --> 00:32:48,240
struktuuri nagu see on?

769
00:32:48,240 --> 00:32:52,570
>> Noh, las ma - me tuleme tagasi
Sellele küsimusele siin.

770
00:32:52,570 --> 00:32:55,530
Ja vaadata, kuidas me võiksime
lahendada see esimene.

771
00:32:55,530 --> 00:32:58,480
Lase ma tõmban seda ettepanekut siin.

772
00:32:58,480 --> 00:33:02,020
Mida me just kirjeldatud on algoritm,
heuristiline nimetatakse lineaarse

773
00:33:02,020 --> 00:33:05,030
katsetamine, mille kohaselt juhul, kui sa püüdsid lisada
midagi siin andmed

774
00:33:05,030 --> 00:33:08,920
struktuur, mida nimetatakse hash tabel,
ja seal pole ruumi seal, siis

775
00:33:08,920 --> 00:33:12,000
tõeliselt sondi andmestruktuur
kontrollimine, kas see on võimalik?

776
00:33:12,000 --> 00:33:13,430
Kas see Saadaval on see võimalik?

777
00:33:13,430 --> 00:33:13,980
Kas see olemas?

778
00:33:13,980 --> 00:33:17,550
Ja kui see lõpuks on, siis sisesta
nimi, mida algselt kavandatud

779
00:33:17,550 --> 00:33:19,370
mujal selles kohas.

780
00:33:19,370 --> 00:33:23,360
Kuid halvimal juhul ainult kohapeal
võib olla väga põhjas andmed

781
00:33:23,360 --> 00:33:25,090
struktuur, päris lõpus massiivi.

782
00:33:25,090 --> 00:33:30,130
>> Nii lineaarne katsetamine, halvimal juhul,
devolves lineaarne algoritm, kus

783
00:33:30,130 --> 00:33:34,500
Aaron, kui ta juhtub olema sisestatud viimane
Selles andmestruktuur, võib ta

784
00:33:34,500 --> 00:33:39,540
põrkuvad see esimene asukoht, kuid
siis lõpetuseks ebaõnn päris lõpus.

785
00:33:39,540 --> 00:33:43,940
Nii et see ei ole konstantne
aeg Püha Graal meile.

786
00:33:43,940 --> 00:33:47,650
Selline lähenemine, mille puhul lisatakse elemendid
andmete struktuuri nimetatakse räsi

787
00:33:47,650 --> 00:33:52,050
Tabel ei tundu olevat pidev aeg
vähemalt mitte üldiselt juhul.

788
00:33:52,050 --> 00:33:54,000
See võib vaimule midagi lineaarne.

789
00:33:54,000 --> 00:33:56,970
>> Mis siis, kui me lahendada kokkupõrkeid
mõnevõrra teisiti?

790
00:33:56,970 --> 00:34:00,740
Nii et siin on keerukam
lähenemine, mis on ikka veel

791
00:34:00,740 --> 00:34:02,800
nimetatakse hash tabelis.

792
00:34:02,800 --> 00:34:05,890
Ja hash, nagu kõrvale, mida
Ma mõtlen on indeks, mis

793
00:34:05,890 --> 00:34:07,070
Mainisin.

794
00:34:07,070 --> 00:34:09,810
Hash midagi saab
mõelnud kui verb.

795
00:34:09,810 --> 00:34:13,690
>> Nii et kui te hash Alice'i nimi,
räsifunktsiooni, niiöelda,

796
00:34:13,690 --> 00:34:14,710
peaks tagasi number.

797
00:34:14,710 --> 00:34:18,199
Antud juhul on null, kui ta kuulub juures
Asukoht null, üks, kui ta kuulub juures

798
00:34:18,199 --> 00:34:20,000
Asukoht üks, ja nii edasi.

799
00:34:20,000 --> 00:34:24,360
Nii et minu räsifunktsiooni Seni on
super lihtne, vaid vaadates

800
00:34:24,360 --> 00:34:26,159
esitäht kellegi nimi.

801
00:34:26,159 --> 00:34:29,090
Aga räsifunktsiooni võtab nii
sisend mõned tükk andmed,

802
00:34:29,090 --> 00:34:30,210
string, int, mida iganes.

803
00:34:30,210 --> 00:34:32,239
Ja ta sülitab välja tavaliselt number.

804
00:34:32,239 --> 00:34:35,739
Ja see number on, kui need andmed
element kuulub andmestruktuur

805
00:34:35,739 --> 00:34:37,800
mida tuntakse hash tabelis.

806
00:34:37,800 --> 00:34:41,400
>> Nii lihtsalt vaistlikult, et see on
veidi erinevas kontekstis.

807
00:34:41,400 --> 00:34:44,170
See tegelikult viitab näiteks
kaasates sünnipäevad, kus

808
00:34:44,170 --> 00:34:46,850
siis võib olla sama palju kui
31 päeva kuus.

809
00:34:46,850 --> 00:34:52,239
Aga mis see inimene otsustada
teha kokkupõrke korral?

810
00:34:52,239 --> 00:34:55,304
Kontekst nüüd on, ei ole kokkupõrge
nimesid, kuid kokkupõrge sünnipäevad,

811
00:34:55,304 --> 00:35:00,760
Kui kaks inimest on sama sünnipäeva
2. oktoober, näiteks.

812
00:35:00,760 --> 00:35:02,120
>> Õpilane: [kuuldamatu].

813
00:35:02,120 --> 00:35:05,010
>> SPEAKER 1: Jah, siin on meil
võimendades seotud nimekirju.

814
00:35:05,010 --> 00:35:07,830
Nii tundub natuke teistmoodi
kui me juhtis ta varem.

815
00:35:07,830 --> 00:35:10,790
Aga me ilmselt array
vasakul servas.

816
00:35:10,790 --> 00:35:13,230
See on üks indeks, mitte
erilist põhjust.

817
00:35:13,230 --> 00:35:14,630
Aga see on ikka massiivi.

818
00:35:14,630 --> 00:35:16,160
See on massiivi osuti.

819
00:35:16,160 --> 00:35:20,670
Ja kõik need elemendid, igaüks
need ringid või jooned - kaldkriips

820
00:35:20,670 --> 00:35:23,970
esindavad null - kõik need
osuti on ilmselt osutades

821
00:35:23,970 --> 00:35:25,730
milliseid andmeid struktuur?

822
00:35:25,730 --> 00:35:26,890
Seotud nimekirja.

823
00:35:26,890 --> 00:35:30,530
>> Nüüd on meil võimalus
kõva kood meie programm

824
00:35:30,530 --> 00:35:32,010
Laua suurus.

825
00:35:32,010 --> 00:35:35,360
Sel juhul me teame, pole kunagi
rohkem kui 31 päeva kuus.

826
00:35:35,360 --> 00:35:38,480
Nii raske kodeerimine väärtus nagu 31
mõistlik selles kontekstis.

827
00:35:38,480 --> 00:35:42,700
Kontekstis nimed, kõva kodeerimine
26 ei ole mõistlik see inimeste

828
00:35:42,700 --> 00:35:46,340
nimed alles algavad, näiteks
tähestiku kaasates läbi Z.

829
00:35:46,340 --> 00:35:50,180
>> Saame tuupima neid kõiki arvesse, et andmed
struktuuri nii kaua, kui me

830
00:35:50,180 --> 00:35:55,330
kokkupõrge, me ei pane nimesid siin
me selle asemel mõtlema nende rakkude

831
00:35:55,330 --> 00:36:00,270
mitte nagu stringid ise, kuid kui
vihjeid, näiteks, Alice.

832
00:36:00,270 --> 00:36:03,660
Ja siis Alice võib olla teise osuti
teise nime alustades

833
00:36:03,660 --> 00:36:06,150
A. Ja Bob tegelikult läheb siia.

834
00:36:06,150 --> 00:36:10,850
>> Ja kui seal on teine ​​nimi algab
B-ga, ta jõuab siia.

835
00:36:10,850 --> 00:36:15,070
Ja nii iga osa käesoleva
tabelis kaks, kui me loodud see

836
00:36:15,070 --> 00:36:17,350
veidi rohkem nutikalt -

837
00:36:17,350 --> 00:36:18,125
tule -

838
00:36:18,125 --> 00:36:22,950
kui me loodud see veidi rohkem
nutikalt, nüüd muutub adaptiivne andmed

839
00:36:22,950 --> 00:36:27,720
struktuur, kus pole raske piiri
kui palju elemente saate sisestada

840
00:36:27,720 --> 00:36:30,700
arvesse seda, sest kui sul on
kokkupõrge, see on hea.

841
00:36:30,700 --> 00:36:34,690
Lihtsalt minna ja lisada see
mida nägime natuke tagasi oli

842
00:36:34,690 --> 00:36:38,290
tuntud seotud nimekirja.

843
00:36:38,290 --> 00:36:39,690
>> Noh olgem pausi hetkeks.

844
00:36:39,690 --> 00:36:42,570
Milline on tõenäosus kokkupõrke
esiteks?

845
00:36:42,570 --> 00:36:45,480
Õigus, võibolla ma olen üle mõelnud, äkki
Ma olen üle insener Selle probleemi

846
00:36:45,480 --> 00:36:46,370
sest sa tead, mis?

847
00:36:46,370 --> 00:36:49,070
Jah, ma ei saa tulla suvalise
näited välja ülalt mu peas nagu

848
00:36:49,070 --> 00:36:52,870
Allison ja Aaron, kuid tegelikkuses
antud ühtlase jaotuse

849
00:36:52,870 --> 00:36:56,990
sisendeid, mis on mõne juhusliku sisestamise
arvesse andmete struktuuri, mis tegelikult on

850
00:36:56,990 --> 00:36:58,580
kokkupõrke tõenäosus?

851
00:36:58,580 --> 00:37:01,670
Noh selgub, et see on tegelikult
super suur.

852
00:37:01,670 --> 00:37:03,850
Las ma üldistada seda
Probleem on selles.

853
00:37:03,850 --> 00:37:08,890
>> Nii et ruumi n CS50 õpilast, mis on
on tõenäosus, et vähemalt

854
00:37:08,890 --> 00:37:11,010
kaks õpilast ruumis
on sama sünnipäev?

855
00:37:11,010 --> 00:37:13,346
Nii et seal on mis. mõni Hund -

856
00:37:13,346 --> 00:37:16,790
200 300 inimest siin ja mitmel
sada inimest kodus täna.

857
00:37:16,790 --> 00:37:20,670
Nii et kui sa tahad küsida, mis on
tõenäosus kaks inimest

858
00:37:20,670 --> 00:37:23,930
selles ruumis, millel on sama sünnipäev,
me leiame vastuse.

859
00:37:23,930 --> 00:37:26,250
Ja ma väita, tegelikult on kaks
inimesed sama sünnipäev.

860
00:37:26,250 --> 00:37:29,560
>> Näiteks, kas keegi
on täna sünnipäev?

861
00:37:29,560 --> 00:37:31,340
Täna?

862
00:37:31,340 --> 00:37:32,590
Homme?

863
00:37:32,590 --> 00:37:35,980
Olgu, tundub, nagu ma
et pean seda tegema 363 või nii rohkem

864
00:37:35,980 --> 00:37:39,500
korda tegelikult aru saada,
kui meil on kokkupõrke.

865
00:37:39,500 --> 00:37:42,350
Või me võiks lihtsalt teha seda matemaatiliselt
mitte tüütult

866
00:37:42,350 --> 00:37:43,200
seda tegema.

867
00:37:43,200 --> 00:37:44,500
Ja järgmine ettepanek.

868
00:37:44,500 --> 00:37:48,740
>> Seega teen ettepaneku, et me võiks modelleerida
tõenäosus kaks inimest, kellel on

869
00:37:48,740 --> 00:37:55,320
sama sünnipäev on tõenäosus 1
miinus tõenäosus keegi, kellel

870
00:37:55,320 --> 00:37:56,290
sama sünnipäev.

871
00:37:56,290 --> 00:37:59,960
Nii, et saada seda, ja see on alles
fancy viis kirjutamise jaoks

872
00:37:59,960 --> 00:38:03,090
esimene inimene toas, ta
võib olla mõni võimalik

873
00:38:03,090 --> 00:38:07,370
sünnipäevad eeldades 365 päeva aastas,
koos vabandused isikutele

874
00:38:07,370 --> 00:38:08,760
29. veebruar sünnipäev.

875
00:38:08,760 --> 00:38:13,470
>> Nii et esimene inimene selles toas on tasuta
mingit arvu sünnipäevad

876
00:38:13,470 --> 00:38:18,280
välja 365 võimalusi, et
me teeme seda 365 jagatud 365,

877
00:38:18,280 --> 00:38:18,990
mis on üks.

878
00:38:18,990 --> 00:38:22,700
Järgmine inimene toas, kui eesmärgiks
on kokkupõrke vältimiseks, saab ainult

879
00:38:22,700 --> 00:38:26,460
on tema sünnipäev, kuidas
palju erinevaid võimalikke päeva?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Nii teise ametiaja see väljend on
sisuliselt seda, et matemaatikat meile

882
00:38:31,430 --> 00:38:33,460
lahutatakse maha üks võimalik päev.

883
00:38:33,460 --> 00:38:36,390
Ja siis järgmisel päeval, järgmisel päeval,
Järgmisel päeval alla koguarv

884
00:38:36,390 --> 00:38:38,100
inimesi ruumis.

885
00:38:38,100 --> 00:38:41,290
>> Ja kui me siis leian ka, siis on
tõenäosus mitte igaüks, kellel

886
00:38:41,290 --> 00:38:45,265
ainulaadne sünnipäevad, aga jälle 1 miinus
et see, mida me saada on väljend

887
00:38:45,265 --> 00:38:47,810
mida saab väga luulelennuliselt
näeb välja selline.

888
00:38:47,810 --> 00:38:50,330
Aga see on rohkem huvitav
vaadata visuaalselt.

889
00:38:50,330 --> 00:38:55,120
See on skeem, kus on x-telg on
inimeste arvu ruumis,

890
00:38:55,120 --> 00:38:56,180
arvu sünnipäevad.

891
00:38:56,180 --> 00:38:59,840
Y-telg on tõenäosus
Kokkupõrke kaks inimest

892
00:38:59,840 --> 00:39:01,230
millel on sama sünnipäev.

893
00:39:01,230 --> 00:39:05,020
>> Ja Buffee alates nimetatud kõver on
et niipea, kui saad nagu 40

894
00:39:05,020 --> 00:39:11,110
õpilased, sa oled üles 90% tõenäosusega
combinatorically kahe

895
00:39:11,110 --> 00:39:13,550
inimesed või rohkem, millel
sama sünnipäev.

896
00:39:13,550 --> 00:39:18,600
Ja kui sa saad nagu 58 inimesed on
peaaegu 100% võimalus kaks

897
00:39:18,600 --> 00:39:21,310
inimesed ruumis on plaanis
sama sünnipäev, kuigi seal on

898
00:39:21,310 --> 00:39:26,650
365 või 366 võimalik ämbrid ja
ainult 58 inimest toas.

899
00:39:26,650 --> 00:39:29,900
Just statistiliselt oled tõenäoliselt
saada kokkupõrked, mis lühidalt

900
00:39:29,900 --> 00:39:31,810
motiveerib see arutelu.

901
00:39:31,810 --> 00:39:35,890
Et isegi kui me fancy siin, ja
alustate võttes need ketid, me oleme ikka

902
00:39:35,890 --> 00:39:36,950
läheb on kokkupõrkeid.

903
00:39:36,950 --> 00:39:42,710
>> Nii et tekib küsimus, mis on
kulud on talutavad Lisatud ja kustutatud

904
00:39:42,710 --> 00:39:44,850
arvesse andmete struktuuri nagu see on?

905
00:39:44,850 --> 00:39:46,630
Noh andke mulle ettepaneku -

906
00:39:46,630 --> 00:39:51,570
ja lubage mul minna tagasi ekraanil üle
siin - kui me oleme n elementi

907
00:39:51,570 --> 00:39:56,330
nimekirja, nii et kui me üritame lisada
n elementi, ja meil on

908
00:39:56,330 --> 00:39:58,050
kui palju kokku ämbrid?

909
00:39:58,050 --> 00:40:03,450
Oletame, et 31 kokku ämbrid
puhul sünnipäevad.

910
00:40:03,450 --> 00:40:09,240
Mis on maksimaalne pikkus on
Nende kettide potentsiaalselt?

911
00:40:09,240 --> 00:40:12,670
>> Kui jälle seal 31 võimalik
sünnipäevad antud kuul.

912
00:40:12,670 --> 00:40:14,580
Ja me lihtsalt kokkukleepumist kõigile -

913
00:40:14,580 --> 00:40:15,580
tegelikult see on loll näide.

914
00:40:15,580 --> 00:40:16,960
Teeme 26 asemel.

915
00:40:16,960 --> 00:40:20,890
Seega, kui tegelikult on inimesed, kelle nimed
Alustame läbi Z, andes

916
00:40:20,890 --> 00:40:22,780
meile 26 võimalusi.

917
00:40:22,780 --> 00:40:25,920
Ja me kasutame andmestruktuuri nagu
üks me just nägime, kusjuures meil on

918
00:40:25,920 --> 00:40:30,210
massiivi osuti, millest igaüks
osutab seotud nimekirja, kus

919
00:40:30,210 --> 00:40:32,360
Esimene nimekiri on igaühe
nimega Alice.

920
00:40:32,360 --> 00:40:35,770
Teine nimekiri on igal koos
algavat nime, mis algab

921
00:40:35,770 --> 00:40:36,980
B-ga, ja nii edasi.

922
00:40:36,980 --> 00:40:41,020
>> Mis on tõenäoline pikkus iga
need nimekirjad, kui me eeldame, kena puhas

923
00:40:41,020 --> 00:40:45,410
jaotus nimede kaudu Z
kogu andmestruktuuri?

924
00:40:45,410 --> 00:40:50,210
Seal on n inimest andmestruktuur
jagatud 26, kui nad kenasti

925
00:40:50,210 --> 00:40:52,110
laiali üle kogu
andmestruktuur.

926
00:40:52,110 --> 00:40:54,970
Nii pikkuse iga
ketid on n jagatud 26.

927
00:40:54,970 --> 00:40:57,380
Aga suur O märke, mis see on?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Mis see on tõesti?

930
00:41:02,440 --> 00:41:04,150
Nii et see on tõesti lihtsalt n, eks?

931
00:41:04,150 --> 00:41:06,620
Kuna me oleme varem öelnud,
et vuih sa jagad 26.

932
00:41:06,620 --> 00:41:08,710
Jah, tegelikult on see kiirem.

933
00:41:08,710 --> 00:41:12,720
Aga teoreetiliselt, see ei ole põhimõtteliselt
kõik, et kiiremini.

934
00:41:12,720 --> 00:41:16,040
>> Nii et me ei tundu olevat kõik, et palju
lähemale see Püha Graal.

935
00:41:16,040 --> 00:41:17,750
Tegelikult, see on lihtsalt lineaarne aeg.

936
00:41:17,750 --> 00:41:20,790
Heck, sel hetkel, siis miks me ei
lihtsalt kasutada üks tohutu seotud nimekirja?

937
00:41:20,790 --> 00:41:23,510
Miks me ei võiks lihtsalt kasutada üks suur
array salvestada nimed

938
00:41:23,510 --> 00:41:25,010
kõik ruumis?

939
00:41:25,010 --> 00:41:28,280
Noh, kas on veel midagi
kaalukaid umbes hash tabel?

940
00:41:28,280 --> 00:41:30,810
Kas on veel midagi kaalukat
kohta andmete struktuuri

941
00:41:30,810 --> 00:41:33,940
, mis näeb välja nagu see on?

942
00:41:33,940 --> 00:41:35,182
See.

943
00:41:35,182 --> 00:41:37,050
>> Õpilane: [kuuldamatu].

944
00:41:37,050 --> 00:41:39,840
>> SPEAKER 1: õige ja uuesti, kui see on lihtsalt
lineaarne algoritm, ja

945
00:41:39,840 --> 00:41:42,780
lineaarne aeg andmestruktuur, miks ma ei
lihtsalt hoida igaühe nime suur

946
00:41:42,780 --> 00:41:44,210
massiiv või suur seotud nimekirja?

947
00:41:44,210 --> 00:41:47,010
Ja lõpetage tehes CS nii palju raskem
kui see peaks olema?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Mis on kaalukaid sellest, isegi
kuigi ma kriimustatud välja?

950
00:41:53,190 --> 00:41:54,930
>> Õpilane: [kuuldamatu].

951
00:41:54,930 --> 00:41:57,040
>> SPEAKER 1: Insertsioonid ei ole?

952
00:41:57,040 --> 00:41:58,140
Kallimad enam.

953
00:41:58,140 --> 00:42:03,390
Nii sisestamisel potentsiaalselt võiks ikka
olema pidev, isegi kui ta oma andmed

954
00:42:03,390 --> 00:42:07,910
struktuur näeb välja selline, array
suunanäitajaks, millest igaüks on vastakuti

955
00:42:07,910 --> 00:42:09,550
potentsiaalselt seotud nimekirja.

956
00:42:09,550 --> 00:42:15,220
Kuidas sa saavutada püsiv
aeg sisestamise nimed?

957
00:42:15,220 --> 00:42:16,280
Pista see ees, eks?

958
00:42:16,280 --> 00:42:19,290
>> Kui me ohverdama disaini eesmärk alates
varem, kui me tahtsime hoida

959
00:42:19,290 --> 00:42:22,650
igaühe nimi, näiteks, sorteeritud,
või kõik numbrid laval sorteeritud,

960
00:42:22,650 --> 00:42:25,020
oletame, et meil on
sortimata seotud nimekirja.

961
00:42:25,020 --> 00:42:29,960
See ainult maksab meile ühe või kaks sammu,
meeldib puhul Ben ja Brian

962
00:42:29,960 --> 00:42:32,750
varem, et lisada element
loetelu alguses.

963
00:42:32,750 --> 00:42:36,090
Nii et kui me ei hooli sorteerimine kõik
nimed algavad või kõik

964
00:42:36,090 --> 00:42:39,660
nimed algavad B, saame ikka
saavutada püsiv aja sisestamist.

965
00:42:39,660 --> 00:42:43,900
Nüüd soojaks Alice või Bob või nimi
üldiselt on ikka see, mida?

966
00:42:43,900 --> 00:42:48,100
See on suur O n jagatud 26, et
Ideaalne juhul, kui kõik on ühtlaselt

967
00:42:48,100 --> 00:42:51,190
jaotatud, kus on nii palju oma
kui on Z, mis on ilmselt

968
00:42:51,190 --> 00:42:52,220
ebareaalne.

969
00:42:52,220 --> 00:42:53,880
Aga see on ikka lineaarne.

970
00:42:53,880 --> 00:42:57,120
>> Aga siin me tuleme tagasi punkti
asümptootilisest märge on

971
00:42:57,120 --> 00:42:58,600
teoreetiliselt õige.

972
00:42:58,600 --> 00:43:02,960
Kuid reaalses maailmas, kui ma väita, et
Minu programm ei tee midagi 26 korda

973
00:43:02,960 --> 00:43:06,210
kiiremini kui sinu oma, kelle programm
sa lähed eelistavad kasutada?

974
00:43:06,210 --> 00:43:09,660
Sinu või minu, mis
on 26 korda kiiremini?

975
00:43:09,660 --> 00:43:14,320
Reaalselt kelle on 26
korda kiiremini, isegi kui teoreetiliselt

976
00:43:14,320 --> 00:43:18,790
meie algoritmid töötavad samal
asümptootiliseks sõiduaega.

977
00:43:18,790 --> 00:43:20,940
>> Lubage mul välja teistsuguse
lahendus üldse.

978
00:43:20,940 --> 00:43:24,380
Ja kui see ei ole löök meelt,
oleme välja andmestruktuurid.

979
00:43:24,380 --> 00:43:27,420
Nii et see on see Prefiksipuu -

980
00:43:27,420 --> 00:43:28,520
mingi loll nimi.

981
00:43:28,520 --> 00:43:32,880
Ta on pärit väljavõtete ja sõna
on kirjutatud Prefiksipuu, t-r-i-e, sest

982
00:43:32,880 --> 00:43:34,450
Muidugi ülekanne kõlab Prefiksipuu.

983
00:43:34,450 --> 00:43:36,580
Aga see on ajalugu
Sõna Prefiksipuu.

984
00:43:36,580 --> 00:43:40,980
>> Nii Prefiksipuu on tõepoolest mingi puu,
ja see on ka mängida, et sõna.

985
00:43:40,980 --> 00:43:46,330
Ja kuigi sa ei saa päris näha
Selle visualiseerimine, Prefiksipuu on

986
00:43:46,330 --> 00:43:50,790
puu struktuuri, nagu sugupuu koos
üks esivanem tipus ja palju

987
00:43:50,790 --> 00:43:54,530
ja lapselapsed ja lapselapsed
kui jätab põhjale.

988
00:43:54,530 --> 00:43:58,100
Aga iga sõlme Prefiksipuu on massiiv.

989
00:43:58,100 --> 00:44:00,680
Ja see on massiiv - ja olgem
lihtsustavad hetkeks - see on

990
00:44:00,680 --> 00:44:04,600
massiiv, sel juhul on suurus 26, kus
Iga sõlme uuesti ei massiivi suurus

991
00:44:04,600 --> 00:44:09,000
26, kui nullis element kõnealuses
massiivi esindab ja viimane

992
00:44:09,000 --> 00:44:11,810
element iga sellise
massiivi esindab Z.

993
00:44:11,810 --> 00:44:15,520
>> Seega teen ettepaneku, et seejärel need andmed
struktuur, mida nimetatakse Prefiksipuu, võib olla

994
00:44:15,520 --> 00:44:17,600
kasutada ka salvestada sõnu.

995
00:44:17,600 --> 00:44:21,740
Nägime hetk tagasi, kuidas saaksime säilitada
sõnad, või antud juhul nimed ja me

996
00:44:21,740 --> 00:44:25,440
nägime, kuidas meil on võimalik salvestada numbreid,
aga kui me keskendume nimed või stringid

997
00:44:25,440 --> 00:44:27,460
siin, teate, mis on huvitav.

998
00:44:27,460 --> 00:44:32,210
Väidan, et nimi Maxwell on
sees see andmestruktuur.

999
00:44:32,210 --> 00:44:33,730
Kus sa näed Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> Õpilane: [kuuldamatu].

1001
00:44:35,140 --> 00:44:36,240
>> SPEAKER 1: vasakul.

1002
00:44:36,240 --> 00:44:39,910
Niisiis, mida on huvitav selle andmed
struktuur on pigem poest

1003
00:44:39,910 --> 00:44:46,200
string M--X-W-E-L-L Kenoviiva null, kõik
contiguously, mida mitte teha

1004
00:44:46,200 --> 00:44:46,890
jälgib.

1005
00:44:46,890 --> 00:44:50,510
Kui see on Prefiksipuu nagu andmestruktuur,
iga, mille tipud on jälle massiiv,

1006
00:44:50,510 --> 00:44:54,650
ja soovite salvestada Maxwell, siis esimene
indeks ja nii root sõlmes, nii

1007
00:44:54,650 --> 00:44:57,810
rääkida, tipmine sõlme,
Kohapeal M, paremale, nii

1008
00:44:57,810 --> 00:44:59,160
umbes keskele.

1009
00:44:59,160 --> 00:45:03,740
Ja siis sealt sa järgima
kursor tütartippu nii rääkida.

1010
00:45:03,740 --> 00:45:06,150
Nii sugupuu mõttes
te järgite seda allapoole.

1011
00:45:06,150 --> 00:45:09,030
Ja see viib sind teise sõlme
vasakul seal, mis on

1012
00:45:09,030 --> 00:45:10,540
lihtsalt üks massiiv.

1013
00:45:10,540 --> 00:45:14,710
>> Ja siis, kui soovite salvestada Maxwell,
leida pointer, mis tähistab

1014
00:45:14,710 --> 00:45:16,430
, Mis on see siin.

1015
00:45:16,430 --> 00:45:17,840
Siis minge järgmise sõlme.

1016
00:45:17,840 --> 00:45:20,100
Ja teate - see on põhjus, miks pildi
veidi petlik -

1017
00:45:20,100 --> 00:45:21,990
See sõlm vaadata super pisike.

1018
00:45:21,990 --> 00:45:26,050
Aga õige on see, Y ja Z.
See on lihtsalt autor on kärbitud

1019
00:45:26,050 --> 00:45:27,630
pilt, et sa tegelikult
vaata asju.

1020
00:45:27,630 --> 00:45:30,400
Muidu see pilt
oleks väga lai.

1021
00:45:30,400 --> 00:45:36,180
Nüüd sa indeks asukoha X, siis
W, siis E, siis L, seejärel L. Milles siis

1022
00:45:36,180 --> 00:45:37,380
see uudishimu?

1023
00:45:37,380 --> 00:45:41,250
>> Noh, kui me kasutame seda tüüpi uus
võtta, kuidas hoida stringi

1024
00:45:41,250 --> 00:45:44,500
andmete struktuuri, siis on vaja veel
sisuliselt kontrollima off andmete

1025
00:45:44,500 --> 00:45:47,250
struktuur, mis sõna lõppeb siin.

1026
00:45:47,250 --> 00:45:50,830
Teisisõnu, kõik need sõlmed
millegipärast on meeles pidada, et me

1027
00:45:50,830 --> 00:45:53,500
tegelikult järgida kõiki neid viiteid
ja lahkute vähe

1028
00:45:53,500 --> 00:45:58,370
riivsaiaga allosas siin selle
struktuur, mis näitab M--X-W-E-L-L on

1029
00:45:58,370 --> 00:46:00,230
tõepoolest selles andmestruktuur.

1030
00:46:00,230 --> 00:46:02,040
>> Nii et me võiks seda teha järgmiselt.

1031
00:46:02,040 --> 00:46:06,810
Iga tippe pilt me ​​lihtsalt
Saag on üks, massiivi suurus 27.

1032
00:46:06,810 --> 00:46:10,550
Ja see on nüüd 27, sest p seatud kuus,
me tegelikult sulle ülakoma,

1033
00:46:10,550 --> 00:46:13,590
et saaksime nimed nagu O'Reilly
ja teised ülakoma.

1034
00:46:13,590 --> 00:46:14,820
Aga sama mõte.

1035
00:46:14,820 --> 00:46:17,710
Kõik need elemendid
massiiv punktid struct

1036
00:46:17,710 --> 00:46:19,320
sõlm, nii lihtsalt sõlme.

1037
00:46:19,320 --> 00:46:21,430
Nii et see on väga meenutab
Meie seotud nimekirja.

1038
00:46:21,430 --> 00:46:24,550
>> Ja siis on mul Loogiline, kus ma
helistada sõna, mis on lihtsalt saab olema

1039
00:46:24,550 --> 00:46:29,120
tõsi, kui sõna lõpeb see
sõlme puu.

1040
00:46:29,120 --> 00:46:32,870
See tõhusalt tähistab vähe
kolmnurk nägime hetkeks tagasi.

1041
00:46:32,870 --> 00:46:37,190
Nii et kui sõna lõpeb, et sõlme
puu, mis sõna valdkonnas on tõsi,

1042
00:46:37,190 --> 00:46:41,990
mis on põhimõtteliselt kontrollida lülitatud või
me joonistus see kolmnurk, jah seal

1043
00:46:41,990 --> 00:46:44,080
on sõna siin.

1044
00:46:44,080 --> 00:46:45,120
>> Nii et see on Prefiksipuu.

1045
00:46:45,120 --> 00:46:48,540
Ja nüüd on küsimus selles, mida
on oma sõiduaega?

1046
00:46:48,540 --> 00:46:49,930
Kas see suur O n?

1047
00:46:49,930 --> 00:46:51,410
Kas see midagi muud?

1048
00:46:51,410 --> 00:46:57,330
Noh, kui sa oled n nimed selles andmed
struktuur, Maxwell on vaid üks

1049
00:46:57,330 --> 00:47:02,330
neid, mis on töötamise aeg
sisestamist või leida Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Mis sõiduaega
sisestades Maxwell?

1052
00:47:09,050 --> 00:47:11,740
Kui seal on n muud nimed
juba tabelis?

1053
00:47:11,740 --> 00:47:12,507
Jah?

1054
00:47:12,507 --> 00:47:15,429
>> Õpilane: [kuuldamatu].

1055
00:47:15,429 --> 00:47:17,550
>> SPEAKER 1: Jah, see on pikkus
nime, eks?

1056
00:47:17,550 --> 00:47:24,420
Nii M--x-w-e-l-l, nii tundub, nagu see
algoritm on suur O seitse.

1057
00:47:24,420 --> 00:47:26,580
Nüüd, muidugi, nimi
on erineva pikkusega.

1058
00:47:26,580 --> 00:47:27,380
Võibolla on see nimetus.

1059
00:47:27,380 --> 00:47:28,600
Võib-olla on pikk nimi.

1060
00:47:28,600 --> 00:47:33,390
Aga mis peamine on see, et
see on pidev number.

1061
00:47:33,390 --> 00:47:36,810
Ja võib-olla see ei ole tegelikult pidevalt,
aga jumal, kui realistlikult lähenedes

1062
00:47:36,810 --> 00:47:41,570
sõnastik, seal on ilmselt mingi piir
arvu tähed

1063
00:47:41,570 --> 00:47:43,820
isiku nimi konkreetses riigis.

1064
00:47:43,820 --> 00:47:46,940
>> Ja nii me võime eeldada, et
väärtus on konstantne.

1065
00:47:46,940 --> 00:47:47,750
Ma ei tea, mis see on.

1066
00:47:47,750 --> 00:47:50,440
See on ilmselt suurem kui
me arvame, et on.

1067
00:47:50,440 --> 00:47:52,720
Sest seal on alati mõned nurgas
puhul hull pikk nimi.

1068
00:47:52,720 --> 00:47:56,360
Nii ütleme k, aga see on veel
pidev arvatavasti, sest igal

1069
00:47:56,360 --> 00:48:00,190
nimi maailmas, vähemalt
riigis, on see, et pikkus või

1070
00:48:00,190 --> 00:48:01,780
lühem, nii et see on pidev.

1071
00:48:01,780 --> 00:48:04,490
Aga kui me oleme öelnud midagi on suur
O püsiv väärtus, mis see on

1072
00:48:04,490 --> 00:48:07,760
tegelikult võrdne?

1073
00:48:07,760 --> 00:48:10,420
See on tegelikult sama asi
öeldes pidevalt aega.

1074
00:48:10,420 --> 00:48:11,530
>> Nüüd oleme omamoodi petmine, eks?

1075
00:48:11,530 --> 00:48:15,340
Oleme omamoodi võimendades mõned teooria
siin öelda, et hästi, et k on

1076
00:48:15,340 --> 00:48:17,450
tõesti lihtsalt, et üks,
ja see on pidevalt aega.

1077
00:48:17,450 --> 00:48:18,200
Aga see on tõesti.

1078
00:48:18,200 --> 00:48:22,550
Sest Võtmeküsimuseks on see, et
kui meil on n nimed juba selles

1079
00:48:22,550 --> 00:48:26,010
andmete struktuuri ja me sisestada Maxwell,
on, kui palju aega kulub, et me

1080
00:48:26,010 --> 00:48:29,530
sisestada Maxwell üldse mõjutatud
kui palju teisi inimesi

1081
00:48:29,530 --> 00:48:31,100
on andmestruktuur?

1082
00:48:31,100 --> 00:48:31,670
Kas ei tundu olevat.

1083
00:48:31,670 --> 00:48:36,280
Kui mul oleks miljard rohkem elemente seda
Prefiksipuu ning seejärel sisestada Maxwell, on

1084
00:48:36,280 --> 00:48:38,650
ta üldse mõjutab?

1085
00:48:38,650 --> 00:48:39,050
Ei.

1086
00:48:39,050 --> 00:48:42,950
Ja see, et erinevalt mõne päeva andmed
struktuuride oleme näinud siiani, kus

1087
00:48:42,950 --> 00:48:46,820
sõiduaega oma algoritmi
täiesti sõltumatu, kui palju

1088
00:48:46,820 --> 00:48:51,430
asjad on või ei ole juba
selles andmestruktuur.

1089
00:48:51,430 --> 00:48:54,650
>> Ja nii seda annab teile nüüd on
võimaluse p set kuus, mis kestab

1090
00:48:54,650 --> 00:48:58,310
uuesti kaasata rakendamisel oma
Õigekirja, lugemine 150000

1091
00:48:58,310 --> 00:49:01,050
sõnadega, kuidas salvestada et
ei ole tingimata selge.

1092
00:49:01,050 --> 00:49:04,030
Ja kuigi ma olen püüdnud leida
Püha Graal, ma ei

1093
00:49:04,030 --> 00:49:05,330
väidavad, et Prefiksipuu on.

1094
00:49:05,330 --> 00:49:09,810
Tegelikult hash tabel võib väga hästi
osutuda palju tõhusamaks.

1095
00:49:09,810 --> 00:49:10,830
Aga need on vaid -

1096
00:49:10,830 --> 00:49:14,620
see on lihtsalt üks disaini otsuseid
sa pead tegema.

1097
00:49:14,620 --> 00:49:18,920
>> Aga sulgemine võtame 50 või nii
sekundit kurkistaa mis peitub

1098
00:49:18,920 --> 00:49:22,190
edasi järgmisel nädalal ja pärast me üleminek
selle käsurea

1099
00:49:22,190 --> 00:49:26,220
maailmas kui C programme asjad web
aluseks ja keeltes nagu PHP ja

1100
00:49:26,220 --> 00:49:30,350
JavaScript ja internet ise
protokolle nagu HTTP, mille olete

1101
00:49:30,350 --> 00:49:32,870
enesestmõistetavaks aastaid
nüüd, ja trükitud rohkem kui kord

1102
00:49:32,870 --> 00:49:34,440
päev, ehk või näinud.

1103
00:49:34,440 --> 00:49:37,420
Ja hakkame koorida tagasi
kihist, mis on internet.

1104
00:49:37,420 --> 00:49:40,650
Ja mis on kood, mis
aluseks tänapäeva tööriistu.

1105
00:49:40,650 --> 00:49:43,230
Nii 50 sekundit selle teaser siin.

1106
00:49:43,230 --> 00:49:46,570
Ma annan sulle Warriors of the Net.

1107
00:49:46,570 --> 00:49:51,370
>> [VIDEO PLAYBACK]

1108
00:49:51,370 --> 00:49:56,764
>> -Ta tuli sõnum.

1109
00:49:56,764 --> 00:50:00,687
Koos protokolliga kõik omal.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Ta tuli maailma julm tulemüürid
uncaring ruuterid, ja ohud kaugele

1112
00:50:19,780 --> 00:50:22,600
hullem kui surm.

1113
00:50:22,600 --> 00:50:23,590
Ta on kiire.

1114
00:50:23,590 --> 00:50:25,300
Ta on tugev.

1115
00:50:25,300 --> 00:50:27,700
Ta TCPIP.

1116
00:50:27,700 --> 00:50:30,420
Ja tal on oma aadress.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Warriors of the Net.

1119
00:50:34,590 --> 00:50:35,290
>> [END VIDEO PLAYBACK]

1120
00:50:35,290 --> 00:50:38,070
>> SPEAKER 1: See, kuidas internet
teeb tööd järgmisel nädalal.

1121
00:50:38,070 --> 00:50:40,406