1
00:00:00,000 --> 00:00:05,259

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Nii CS50, oleme kaetud
palju erinevaid andmestruktuurid

3
00:00:08,300 --> 00:00:09,180
õige?

4
00:00:09,180 --> 00:00:11,420
Me oleme näinud massiivid ning seotud
nimekirjad ja hash tabeleid,

5
00:00:11,420 --> 00:00:15,210
ja proovib, korstnad ja järjekorrad.

6
00:00:15,210 --> 00:00:17,579
Me ka õppida veidi
umbes puud ja hunnikutes,

7
00:00:17,579 --> 00:00:20,120
kuid tõesti neid kõiki lihtsalt lõpuks
up on variatsioone teema.

8
00:00:20,120 --> 00:00:22,840
Seal tõesti on need
Selline neli põhiideed

9
00:00:22,840 --> 00:00:25,190
et kõik muu võib taanduvad.

10
00:00:25,190 --> 00:00:28,150
Massiivid, ahelloendid,
hash tabeleid ja proovib.

11
00:00:28,150 --> 00:00:30,720
Ja nagu ma ütlesin,
On erinevusi nende,

12
00:00:30,720 --> 00:00:32,720
aga see on päris
palju läheb kokku

13
00:00:32,720 --> 00:00:38,140
kõik me kavatseme rääkida
umbes selles klassis poolest C.

14
00:00:38,140 --> 00:00:40,140
>> Aga kuidas need kõik küündima, eks?

15
00:00:40,140 --> 00:00:44,265
Me rääkisime plusse ja miinuseid
Iga eraldi videos neile,

16
00:00:44,265 --> 00:00:46,390
kuid seal on palju numbreid
saada visatakse ümber.

17
00:00:46,390 --> 00:00:48,723
Seal on palju üldist
mõtteid saada visatakse ümber.

18
00:00:48,723 --> 00:00:51,950
Proovime ja tugevdada
see vaid üks koht.

19
00:00:51,950 --> 00:00:55,507
Olgem kaaluda plusse vastu
miinuseid, ja kaaluda

20
00:00:55,507 --> 00:00:57,340
mis andmestruktuur
võiks olla õigus andmeid

21
00:00:57,340 --> 00:01:01,440
struktuuri oma konkreetsele olukorrale,
olenemata sellest, millist andmete olete ladustamiseks.

22
00:01:01,440 --> 00:01:06,625
Sa ei pruugi alati vaja
kasutada super kiire lisamise, kustutamise

23
00:01:06,625 --> 00:01:10,761
ja lookup on Prefiksipuu kui sa tõesti
ei hooli lisada ja kustutada

24
00:01:10,761 --> 00:01:11,260
liiga palju.

25
00:01:11,260 --> 00:01:13,968
Kui teil on vaja lihtsalt kiiresti juhuslik
juurdepääsu, võibolla hulga parem.

26
00:01:13,968 --> 00:01:15,340
Nii oletame ajama seda.

27
00:01:15,340 --> 00:01:18,530
Räägime iga nelja
suuremate liiki andmestruktuuride

28
00:01:18,530 --> 00:01:21,720
et me rääkisime, ja
lihtsalt näha, kui nad võiksid olla hea,

29
00:01:21,720 --> 00:01:23,340
ja kui nad ei pruugi olla nii hea.

30
00:01:23,340 --> 00:01:24,610
Nii alustame massiivid.

31
00:01:24,610 --> 00:01:27,300
Nii sisestamise, et on selline halb.

32
00:01:27,300 --> 00:01:31,350
>> Insertion lõpus massiivi on OK,
Kui me ehitame massiivi läheme.

33
00:01:31,350 --> 00:01:33,570
Aga kui meil on vaja sisestada
elemendid keskele,

34
00:01:33,570 --> 00:01:35,550
arvan, et tagasi sisestamise
sorteerida, seal on palju

35
00:01:35,550 --> 00:01:37,510
minnes sobib element olemas.

36
00:01:37,510 --> 00:01:41,170
Ja kui me läheme sisestada
kõikjal, kuid lõpuks massiiv,

37
00:01:41,170 --> 00:01:43,590
et ilmselt ei ole nii suur.

38
00:01:43,590 --> 00:01:46,710
>> Samuti kustutamist, kui me oleme
kustutada lõpust massiivi,

39
00:01:46,710 --> 00:01:49,810
on ilmselt ka mitte nii suur kui
me ei taha lahkuda tühjade lüngad,

40
00:01:49,810 --> 00:01:50,790
mis tavaliselt me ​​seda ei tee.

41
00:01:50,790 --> 00:01:54,700
Me tahame, et eemaldada element, ja
siis omamoodi teha kallistama uuesti.

42
00:01:54,700 --> 00:01:57,670
Ja nii kustutamine elemendid
massiivi, ka mitte nii suur.

43
00:01:57,670 --> 00:01:58,820
>> Otsing, kuigi on suur.

44
00:01:58,820 --> 00:02:00,920
Meil on muutmälu,
konstantse ajaga otsing.

45
00:02:00,920 --> 00:02:03,800
Me lihtsalt öelda, seitse, ja me läheme
kuni massiivi ümberpaigutamine seitse.

46
00:02:03,800 --> 00:02:05,907
Me ütleme, 20, koos Mine
massiivi ümberpaigutamine 20.

47
00:02:05,907 --> 00:02:07,240
Me ei pea korrata üle.

48
00:02:07,240 --> 00:02:08,630
See on päris hea.

49
00:02:08,630 --> 00:02:11,020
>> Massiivid on ka suhteliselt lihtne sorteerida.

50
00:02:11,020 --> 00:02:14,040
Iga kord, kui me rääkisime sorteerimine
algoritm, nagu valimise omamoodi,

51
00:02:14,040 --> 00:02:18,820
sisestamise sorteerida, mull sorteerida, ühendada
Sorteeri me alati kasutada massiive seda teha,

52
00:02:18,820 --> 00:02:21,860
sest massiivid on päris lihtne
sorteerida, võrreldes andmestruktuuride

53
00:02:21,860 --> 00:02:22,970
oleme näinud siiani.

54
00:02:22,970 --> 00:02:24,320
>> Nad on ka suhteliselt väike.

55
00:02:24,320 --> 00:02:25,695
Seal ei ole palju lisaruumi.

56
00:02:25,695 --> 00:02:29,210
Sa lihtsalt kõrvale täpselt nii palju
kui teil on vaja hoida oma andmeid,

57
00:02:29,210 --> 00:02:30,320
ja see on päris palju see.

58
00:02:30,320 --> 00:02:33,180
Nii nad on üsna väike
ja tõhus nii.

59
00:02:33,180 --> 00:02:36,000
Aga teine ​​negatiivne külg, kuigi
on see, et nad on fikseeritud suurus.

60
00:02:36,000 --> 00:02:38,630
Meil on kuulutada, kuidas täpselt
big me tahame, et meie massiivi olla,

61
00:02:38,630 --> 00:02:39,940
ja et me saame ainult üks lask seda.

62
00:02:39,940 --> 00:02:41,280
Me ei saa kasvada ja kahaneb see.

63
00:02:41,280 --> 00:02:44,582
>> Kui meil on vaja kasvada või väheneda, siis me
vaja kuulutada täiesti uue massiivi,

64
00:02:44,582 --> 00:02:47,750
kopeerida kõik elemendid
Esimene massiivi teine ​​rida.

65
00:02:47,750 --> 00:02:51,410
Ja kui me valesti, et
aega, me peame seda uuesti teha.

66
00:02:51,410 --> 00:02:52,760
Ei ole nii suur.

67
00:02:52,760 --> 00:02:58,750
Nii massiivid ei anna meile paindlikkuse
omada muutuva arvu elemente.

68
00:02:58,750 --> 00:03:01,320
>> Mis ahelloend,
sisestamise on üsna lihtne.

69
00:03:01,320 --> 00:03:03,290
Me lihtsalt pühitakse peale ees.

70
00:03:03,290 --> 00:03:04,892
Kustutamine on ka üsna lihtne.

71
00:03:04,892 --> 00:03:06,100
Me peame leidma elemente.

72
00:03:06,100 --> 00:03:07,270
See kaasata mõned otsivad.

73
00:03:07,270 --> 00:03:10,270
>> Aga kui olete leidnud element
otsite, kõik mida sa pead tegema

74
00:03:10,270 --> 00:03:12,830
on muuta kursorit,
võib-olla kaks, kui teil on

75
00:03:12,830 --> 00:03:15,151
lingitud list-- kahekordselt
seotud nimekirja, rather--

76
00:03:15,151 --> 00:03:16,650
ja siis saate lihtsalt vaba sõlme.

77
00:03:16,650 --> 00:03:18,399
Sa ei pea minema
kõike enda ümber.

78
00:03:18,399 --> 00:03:22,090
Sa lihtsalt muuta kahe suunanäitajaks,
nii see on päris kiire.

79
00:03:22,090 --> 00:03:23,470
>> Otsing on halb küll, eks?

80
00:03:23,470 --> 00:03:26,280
Et saaksime leida
element ahelloend,

81
00:03:26,280 --> 00:03:29,154
kas eraldi või kahekordselt seotud,
meil lineaarne otsida seda.

82
00:03:29,154 --> 00:03:32,320
Me peame hakkama alguses ja
liigutage end, või alustada lõpus liikuda

83
00:03:32,320 --> 00:03:33,860
algusesse.

84
00:03:33,860 --> 00:03:35,474
Meil ei ole random access enam.

85
00:03:35,474 --> 00:03:37,265
Nii et kui me teeme
palju otsinguid, võib-olla

86
00:03:37,265 --> 00:03:39,830
ahelloend ei ole
päris nii hea.

87
00:03:39,830 --> 00:03:43,750
>> Nad on ka väga
raske sorteerida, eks?

88
00:03:43,750 --> 00:03:45,666
Ainult nii saab
tõesti sorteeri ahelloend

89
00:03:45,666 --> 00:03:47,870
on sortida kui ehitada see.

90
00:03:47,870 --> 00:03:50,497
Aga kui sa sorteeri seda nagu
ehitada see, et sa oled enam

91
00:03:50,497 --> 00:03:51,830
teha kiireid vahelekirjutuste enam.

92
00:03:51,830 --> 00:03:53,746
Sa mitte ainult laveerimine
asju peale ees.

93
00:03:53,746 --> 00:03:55,710
Sa pead leidma
õigesse kohta panna,

94
00:03:55,710 --> 00:03:57,820
ja siis oma sisestamist
muutub peaaegu sama halb

95
00:03:57,820 --> 00:03:59,390
sisestades massiivi.

96
00:03:59,390 --> 00:04:03,130
Nii ahelloendid ei ole
nii suur sorteerimine andmeid.

97
00:04:03,130 --> 00:04:05,830
>> Nad on ka üsna väike, suurus tark.

98
00:04:05,830 --> 00:04:08,496
Kahekordselt seotud nimekirja veidi
suurem kui üksikult ahelloendid,

99
00:04:08,496 --> 00:04:10,620
mis on veidi suuremad
kui massiivid, kuid see ei ole

100
00:04:10,620 --> 00:04:13,330
tohutult raisatud ruumi.

101
00:04:13,330 --> 00:04:18,730
Nii et kui ruumi on lisatasu, kuid
ei ole tõesti tihe premium,

102
00:04:18,730 --> 00:04:22,180
see võib olla õige tee.

103
00:04:22,180 --> 00:04:23,330
>> Räsitabeli.

104
00:04:23,330 --> 00:04:25,850
Sisestamist hash tabelis
on üsna lihtne.

105
00:04:25,850 --> 00:04:26,980
See on kaheastmeline protsess.

106
00:04:26,980 --> 00:04:30,700
Esiteks peame kulgema meie kaudu andmeid
räsi funktsiooni saada räsikoodiga,

107
00:04:30,700 --> 00:04:37,550
ja siis me lisada element sisse
hash tabelit, et räsikoodiga asukohta.

108
00:04:37,550 --> 00:04:40,879
>> Kustutamine, sarnaselt seotud nimekirja,
on lihtne, kui leiad element.

109
00:04:40,879 --> 00:04:43,170
Sa pead leidma kõigepealt,
aga siis, kui sa seda kustutada,

110
00:04:43,170 --> 00:04:45,128
sa lihtsalt vaja vahetada
paar suunanäitajaks,

111
00:04:45,128 --> 00:04:47,250
kui te kasutate eraldi ühendamine.

112
00:04:47,250 --> 00:04:49,942
Kui te kasutate katsetamine,
või kui sa ei ole

113
00:04:49,942 --> 00:04:51,650
kasutades aheldamine üldse
Teie hash tabelit,

114
00:04:51,650 --> 00:04:53,040
kustutamise on tegelikult väga lihtne.

115
00:04:53,040 --> 00:04:57,134
Kõik, mida pead tegema, on hash
andmed ja siis minge selles kohas.

116
00:04:57,134 --> 00:04:58,925
Ja eeldades, et sa seda ei tee
mingeid kokkupõrkeid,

117
00:04:58,925 --> 00:05:01,650
Teil on võimalik kustutada väga kiiresti.

118
00:05:01,650 --> 00:05:04,930
>> Nüüd, lookup on, kus asjad
natuke keerulisem.

119
00:05:04,930 --> 00:05:06,910
See on keskmiselt paremad
kui ahelloendid.

120
00:05:06,910 --> 00:05:09,560
Kui te kasutate ühendamine,
sul on veel seotud nimekirja,

121
00:05:09,560 --> 00:05:13,170
mis tähendab, sul on veel
Otsing kahjustamises ahelloend.

122
00:05:13,170 --> 00:05:18,390
Aga kuna te võtate oma seotud
nimekirja ja jagades selle üle 100 või 1000

123
00:05:18,390 --> 00:05:25,380
või n elementi oma hash tabelit, sa oled
ahelloendid on kõik üks nda suurus.

124
00:05:25,380 --> 00:05:27,650
Nad kõik on oluliselt väiksem.

125
00:05:27,650 --> 00:05:32,080
Olete n ahelloendid asemel
Ühe seotud nimekiri suuruse n.

126
00:05:32,080 --> 00:05:34,960
>> Ja nii see reaalse maailma pidev
tegur, mis meil üldiselt

127
00:05:34,960 --> 00:05:39,730
ei räägi ajas keerukus, see
ei tegelikult midagi muuta siin.

128
00:05:39,730 --> 00:05:43,020
Nii lookup on ikka lineaarne
otsida, kui te kasutate ühendamine,

129
00:05:43,020 --> 00:05:46,780
kuid pikkus nimekirja
sa läbi otsida

130
00:05:46,780 --> 00:05:50,080
on väga lühike võrreldes.

131
00:05:50,080 --> 00:05:52,995
Jällegi, kui sorteerimine on teie
eesmärk siin hash tabeli

132
00:05:52,995 --> 00:05:54,370
Ilmselt ei ole õige tee.

133
00:05:54,370 --> 00:05:56,830
Lihtsalt kasutada massiivi kui sortimine
On väga oluline, et teil.

134
00:05:56,830 --> 00:05:58,590
>> Ja nad saavad kulgema varieeruvad suurusest.

135
00:05:58,590 --> 00:06:01,640
On raske öelda, kas
hash tabelis on väike või suur,

136
00:06:01,640 --> 00:06:04,110
sest see tõesti sõltub
kui suur on teie hash tabelis on.

137
00:06:04,110 --> 00:06:07,340
Kui oled ainus kavatse salvestamiseks
viis elementi oma hash tabelit,

138
00:06:07,340 --> 00:06:10,620
ja teil on hash tabelis
10000 elementide seda,

139
00:06:10,620 --> 00:06:12,614
oled ilmselt raiskab palju ruumi.

140
00:06:12,614 --> 00:06:15,030
Kontrast, võid ka
on väga kompaktne hash tabeleid,

141
00:06:15,030 --> 00:06:18,720
kuid väiksematel oma hash tabelit saab,
Pikemas iga nimetatud ahelloendid

142
00:06:18,720 --> 00:06:19,220
saab.

143
00:06:19,220 --> 00:06:22,607
Ja nii seal on tõesti kuidagi määratleda
täpselt sama suur hash tabelit,

144
00:06:22,607 --> 00:06:24,440
aga see on ilmselt ohutu
öelda, et see on üldiselt

145
00:06:24,440 --> 00:06:27,990
saab olema suurem kui seotud
nimekirja salvestamiseks samu andmeid,

146
00:06:27,990 --> 00:06:30,400
kuid väiksem kui Prefiksipuu.

147
00:06:30,400 --> 00:06:32,720
>> Ja üritab on neljas
Nende struktuuride

148
00:06:32,720 --> 00:06:34,070
et me oleme rääkinud.

149
00:06:34,070 --> 00:06:36,450
Sisestamine sisse Prefiksipuu on keeruline.

150
00:06:36,450 --> 00:06:38,400
Seal on palju dünaamilisem
mälu eraldamise,

151
00:06:38,400 --> 00:06:40,780
eriti alguses,
kui sa oled hakanud ehitama.

152
00:06:40,780 --> 00:06:43,700
Aga see on pidev aega.

153
00:06:43,700 --> 00:06:47,690
See on ainult inimese element
siin, mis muudab ta keeruline.

154
00:06:47,690 --> 00:06:53,250
Võttes silmitsi nullviida, malloc
ruumi, sinna minna, võib-olla malloc ruumi

155
00:06:53,250 --> 00:06:54,490
sealt uuesti.

156
00:06:54,490 --> 00:06:58,880
Omamoodi hirmutamise tegur
viiteid dünaamiline mälu eraldamise

157
00:06:58,880 --> 00:07:00,130
on takistuseks selge.

158
00:07:00,130 --> 00:07:04,550
Aga kui olete läbinud seda, sisestamise
tegelikult on üsna lihtne,

159
00:07:04,550 --> 00:07:06,810
ja see on kindlasti pidevat aega.

160
00:07:06,810 --> 00:07:07,680
>> Kustutamine on lihtne.

161
00:07:07,680 --> 00:07:11,330
Kõik, mida pead tegema, on liikuda alla
Paar viiteid ja vaba sõlme,

162
00:07:11,330 --> 00:07:12,420
nii, et on päris hea.

163
00:07:12,420 --> 00:07:13,930
Otsing on ka päris kiire.

164
00:07:13,930 --> 00:07:16,780
See on ainus, mis põhineb
pikkus oma andmeid.

165
00:07:16,780 --> 00:07:19,924
Nii et kui kõik andmed on
viie tähemärke,

166
00:07:19,924 --> 00:07:22,590
Näiteks, sa hoidmiseks viis
tähemärgistringides oma Prefiksipuu,

167
00:07:22,590 --> 00:07:25,439
see võtab vaid viis sammu
leida, mida te otsite.

168
00:07:25,439 --> 00:07:28,480
Viis on lihtsalt konstandiks, nii
jälle lisamise, kustutamise ja otsimise

169
00:07:28,480 --> 00:07:31,670
siin on kõik pidevas ajal tõhusalt.

170
00:07:31,670 --> 00:07:34,880
>> Teine asi on see, et teie Prefiksipuu on
tegelikult omamoodi juba sorteeritud, eks?

171
00:07:34,880 --> 00:07:36,800
Tänu kuidas me
sisestades elemente,

172
00:07:36,800 --> 00:07:40,060
minnes kirja kirja teel
klahvi või numbrite kaupa võti,

173
00:07:40,060 --> 00:07:45,084
Tavaliselt oma Prefiksipuu jõuab on
Selline järjestatud nagu te ehitada seda.

174
00:07:45,084 --> 00:07:47,250
See ei ole tegelikult teeb
mõtet mõelda sorteerimine

175
00:07:47,250 --> 00:07:49,874
samamoodi mõtleme
see massiivid või ahelloendid,

176
00:07:49,874 --> 00:07:51,070
või hash tabeleid.

177
00:07:51,070 --> 00:07:54,780
Kuid mõnes mõttes oma
Prefiksipuu on järjestatud lähete.

178
00:07:54,780 --> 00:07:58,630
>> Puuduseks on muidugi see, et
Prefiksipuu kiiresti muutub tohutu.

179
00:07:58,630 --> 00:08:02,970
Igast ristmikul punkti, võite
have-- kui oma võti seisneb numbrit,

180
00:08:02,970 --> 00:08:04,880
teil on 10 muud
kohti võid minna, mis

181
00:08:04,880 --> 00:08:07,490
tähendab, et iga sõlme
sisaldab teavet

182
00:08:07,490 --> 00:08:11,440
umbes andmed, mida soovite salvestada
sel sõlme, pluss 10 suunanäitajaks.

183
00:08:11,440 --> 00:08:14,430
Mille kohta on CS50 IDE, on 80 baiti.

184
00:08:14,430 --> 00:08:17,220
Nii et see on vähemalt 80 baiti
Iga sõlme, et te luua,

185
00:08:17,220 --> 00:08:19,240
ja see pole isegi lugedes andmeid.

186
00:08:19,240 --> 00:08:24,950
Ja kui teie sõlmed
Tähtede asemel numbrit,

187
00:08:24,950 --> 00:08:27,825
nüüd on 26 suunanäitajaks
igast asukohast.

188
00:08:27,825 --> 00:08:32,007
Ja 26 korda 8 on ilmselt 200
baiti, või midagi sellist.

189
00:08:32,007 --> 00:08:33,840
Ja sul on kapitali
ja lowercase-- võite

190
00:08:33,840 --> 00:08:35,381
näha, kus ma lähen seda, eks?

191
00:08:35,381 --> 00:08:37,500
Sinu sõlmed saavad tõesti
suur, ja nii Prefiksipuu

192
00:08:37,500 --> 00:08:40,470
ise üldiselt ei
saada tõesti suur, liiga.

193
00:08:40,470 --> 00:08:42,630
Nii et kui ruumi on kõrge
premium oma süsteemis,

194
00:08:42,630 --> 00:08:45,830
Prefiksipuu ei pruugi olla õige tee
minna, kuigi tema muid hüvesid

195
00:08:45,830 --> 00:08:47,780
tulevad mängu.

196
00:08:47,780 --> 00:08:48,710
Ma olen Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
See on CS50.

198
00:08:50,740 --> 00:08:52,316