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

2
00:00:05,259 --> 00:00:08,300
DOUG Lloyd: Pra, në CS50, ne kemi mbuluar
një shumë prej strukturave të ndryshme të të dhënave,

3
00:00:08,300 --> 00:00:09,180
e drejtë?

4
00:00:09,180 --> 00:00:11,420
Ne e kemi parë vargjeve, dhe të lidhura
Listat, dhe tavolina hash,

5
00:00:11,420 --> 00:00:15,210
dhe përpiqet, oxhaqet dhe radhët e gjata.

6
00:00:15,210 --> 00:00:17,579
Ne gjithashtu do të mësojnë pak
për pemë dhe grumbujt,

7
00:00:17,579 --> 00:00:20,120
por me të vërtetë të gjitha këto vetëm në fund
duke qenë variacione mbi një temë.

8
00:00:20,120 --> 00:00:22,840
Ka të vërtetë janë këto
lloj i katër ideve themelore

9
00:00:22,840 --> 00:00:25,190
se çdo gjë tjetër mund të valoj poshtë për të.

10
00:00:25,190 --> 00:00:28,150
Vargjeve, listat lidhura,
tavolina hash, dhe të përpiqet.

11
00:00:28,150 --> 00:00:30,720
Dhe si i tha, nuk ka
dallime në to,

12
00:00:30,720 --> 00:00:32,720
por kjo është shumë e
shumë do të përmbledhë

13
00:00:32,720 --> 00:00:38,140
çdo gjë që ne jemi duke shkuar për të folur
lidhje në këtë klasë në drejtim të C.

14
00:00:38,140 --> 00:00:40,140
>> Por si do të gjitha këto masa e lart, e drejtë?

15
00:00:40,140 --> 00:00:44,265
Ne kemi biseduar për të mirat dhe të këqijat
e secilit në të veçanta video mbi ta,

16
00:00:44,265 --> 00:00:46,390
por ka një shumë të numrave
duke u hedhur rreth.

17
00:00:46,390 --> 00:00:48,723
Nuk është një shumë e përgjithshme
Mendimet e duke u hedhur rreth.

18
00:00:48,723 --> 00:00:51,950
Le të përpiqen dhe të konsolidojë
kjo në vetëm një vend.

19
00:00:51,950 --> 00:00:55,507
Le të peshojnë të mirat kundër
të këqijat, dhe të marrë parasysh

20
00:00:55,507 --> 00:00:57,340
që Struktura e të dhënave
mund të jetë e drejtë e të dhënave

21
00:00:57,340 --> 00:01:01,440
Struktura për gjendjen tuaj të veçantë,
çfarëdo lloji i të dhënave që ju jeni ruajtjen.

22
00:01:01,440 --> 00:01:06,625
Ju nuk domosdoshmërisht gjithmonë duhet të
përdorni futje super të shpejtë, fshirjen,

23
00:01:06,625 --> 00:01:10,761
dhe lookup i një Trie nëse jeni të vërtetë
nuk kujdesen për të futur dhe fshirjes

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

25
00:01:11,260 --> 00:01:13,968
Nëse keni nevojë vetëm të shpejt të rastit
qasje, ndoshta një grup është më e mirë.

26
00:01:13,968 --> 00:01:15,340
Pra, le të gjej atë.

27
00:01:15,340 --> 00:01:18,530
Le të flasim për secilin nga katër
lloje kryesore të strukturave të të dhënave

28
00:01:18,530 --> 00:01:21,720
që ne kemi biseduar rreth, dhe
vetëm shikoni kur ata mund të jenë të mira,

29
00:01:21,720 --> 00:01:23,340
dhe kur ata nuk mund të jetë aq i mirë.

30
00:01:23,340 --> 00:01:24,610
Pra, le të fillojë me vargjeve.

31
00:01:24,610 --> 00:01:27,300
Kështu futje, kjo është lloj i keq.

32
00:01:27,300 --> 00:01:31,350
>> Futje në fund të një grup është në rregull,
në qoftë se ne jemi duke ndërtuar një grup si të shkojmë.

33
00:01:31,350 --> 00:01:33,570
Por në qoftë se ne kemi nevojë për të futur
Elementet në mes,

34
00:01:33,570 --> 00:01:35,550
mendoj se mbrapa në futje
lloj, nuk është një shumë

35
00:01:35,550 --> 00:01:37,510
e zhvendosur të përshtaten një element në atje.

36
00:01:37,510 --> 00:01:41,170
Dhe kështu që në qoftë se ne jemi duke shkuar për të futur
kudo por fundi i një grup,

37
00:01:41,170 --> 00:01:43,590
që ndoshta nuk është aq e madhe.

38
00:01:43,590 --> 00:01:46,710
>> Në mënyrë të ngjashme, fshirje, nëse ne jemi
fshirjes nga fundi i një grup,

39
00:01:46,710 --> 00:01:49,810
është ndoshta edhe jo aq e madhe nëse
ne nuk duam të lënë boshllëqe bosh,

40
00:01:49,810 --> 00:01:50,790
të cilat zakonisht ne nuk bëjmë.

41
00:01:50,790 --> 00:01:54,700
Ne duam për të hequr një element, dhe
pastaj lloj i bëjnë të rehatshëm përsëri.

42
00:01:54,700 --> 00:01:57,670
Dhe kështu fshirjes elemente nga
një grup, edhe jo aq e madhe.

43
00:01:57,670 --> 00:01:58,820
>> Lookup, megjithatë, është e madhe.

44
00:01:58,820 --> 00:02:00,920
Ne kemi qasje të rastit,
lookup kohë konstante.

45
00:02:00,920 --> 00:02:03,800
Ne vetëm themi shtatë, dhe ne do të shkojmë
të zhvendosjes array shtatë.

46
00:02:03,800 --> 00:02:05,907
Ne themi 20, me lëvizje të
array zhvendosjes 20.

47
00:02:05,907 --> 00:02:07,240
Ne nuk duhet të iterate nëpër.

48
00:02:07,240 --> 00:02:08,630
Kjo është shumë e mirë.

49
00:02:08,630 --> 00:02:11,020
>> Vargjeve janë gjithashtu relativisht e lehtë për të zgjidhur.

50
00:02:11,020 --> 00:02:14,040
Çdo herë kemi biseduar për një klasifikim
algorithm, të tilla si lloj përzgjedhjes,

51
00:02:14,040 --> 00:02:18,820
lloj futje, flluskë lloj, shkrihen
lloj, ne gjithmonë e përdorur vargjeve për të bërë atë,

52
00:02:18,820 --> 00:02:21,860
sepse vargjeve janë goxha të lehtë për të
lloj, relative te strukturave dhënave

53
00:02:21,860 --> 00:02:22,970
ne kemi parë deri tani.

54
00:02:22,970 --> 00:02:24,320
>> Ata janë gjithashtu relativisht i vogël.

55
00:02:24,320 --> 00:02:25,695
Nuk është një shumë hapësirë ​​shtesë.

56
00:02:25,695 --> 00:02:29,210
Ju vetëm të lënë mënjanë saktësisht sa më shumë
si ju duhet të mbani të dhënat tuaja,

57
00:02:29,210 --> 00:02:30,320
dhe kjo është shumë e shumë ajo.

58
00:02:30,320 --> 00:02:33,180
Pra, ata janë mjaft të vogla
dhe efikas në këtë mënyrë.

59
00:02:33,180 --> 00:02:36,000
Por një tjetër downside, edhe pse,
është se ata janë të fiksuara në madhësi.

60
00:02:36,000 --> 00:02:38,630
Ne duhet të deklarojnë me saktësi se si
i madh ne duam koleksion jonë të jetë,

61
00:02:38,630 --> 00:02:39,940
dhe ne vetëm të marrë një e shtënë në të.

62
00:02:39,940 --> 00:02:41,280
Ne nuk mund të rritet dhe tkurret atë.

63
00:02:41,280 --> 00:02:44,582
>> Në qoftë se ne kemi nevojë të rritet ose tkurret atë, ne
duhet të deklarojë një grup krejtësisht të re,

64
00:02:44,582 --> 00:02:47,750
kopje të të gjitha elementet e
array e parë në grup të dytë.

65
00:02:47,750 --> 00:02:51,410
Dhe në qoftë se ne llogariti keq se
kohë, ne duhet të bëjmë atë përsëri.

66
00:02:51,410 --> 00:02:52,760
Jo aq e madhe.

67
00:02:52,760 --> 00:02:58,750
Pra vargjeve nuk na jep fleksibilitetin
që të ketë një numër të ndryshueshme të elementeve.

68
00:02:58,750 --> 00:03:01,320
>> Me një listë të lidhura,
futje është shumë e lehtë.

69
00:03:01,320 --> 00:03:03,290
Ne vetëm litar mbi pjesën e përparme.

70
00:03:03,290 --> 00:03:04,892
Fshirje është gjithashtu shumë e lehtë.

71
00:03:04,892 --> 00:03:06,100
Ne duhet të gjejmë elementet.

72
00:03:06,100 --> 00:03:07,270
Që përfshijnë disa kërkim.

73
00:03:07,270 --> 00:03:10,270
>> Por një herë ju keni gjetur elementin
ju jeni duke kërkuar për të, të gjithë ju duhet të bëni

74
00:03:10,270 --> 00:03:12,830
është të ndryshojë një akrep,
ndoshta dy në qoftë se ju keni

75
00:03:12,830 --> 00:03:15,151
një i lidhur list-- një dyfish
listë e lidhur, rather--

76
00:03:15,151 --> 00:03:16,650
dhe atëherë ju vetëm mund të lirë nyjen.

77
00:03:16,650 --> 00:03:18,399
Ju nuk duhet të zhvendoset
çdo gjë përreth.

78
00:03:18,399 --> 00:03:22,090
Ju vetëm të ndryshojë dy pointers,
kështu që është mjaft i shpejtë.

79
00:03:22,090 --> 00:03:23,470
>> Lookup është e keqe edhe pse, e drejtë?

80
00:03:23,470 --> 00:03:26,280
Në mënyrë që ne për të gjetur një
element në një listë të lidhura,

81
00:03:26,280 --> 00:03:29,154
qoftë në formë individuale apo dyfish i lidhur,
ne duhet ta lineare të kërkuar atë.

82
00:03:29,154 --> 00:03:32,320
Ne duhet të fillojë në fillim dhe
lëvizur fund, ose të fillojnë në lëvizje fund

83
00:03:32,320 --> 00:03:33,860
në fillim.

84
00:03:33,860 --> 00:03:35,474
Ne nuk kemi qasje të rastit më.

85
00:03:35,474 --> 00:03:37,265
Pra, nëse ne jemi duke bërë një
Shumë kërkim, ndoshta

86
00:03:37,265 --> 00:03:39,830
një listë e lidhur nuk është
krejt në mënyrë të mirë për ne.

87
00:03:39,830 --> 00:03:43,750
>> Ata janë gjithashtu të vërtetë
e vështirë për të zgjidhur, e drejtë?

88
00:03:43,750 --> 00:03:45,666
E vetmja mënyrë që ju mund të
të vërtetë të zgjidhur një listë e lidhur

89
00:03:45,666 --> 00:03:47,870
është për të zgjidhur atë si ju të ndërtuar atë.

90
00:03:47,870 --> 00:03:50,497
Por nëse ju zgjidhur atë si ju
ndërtuar atë, ju nuk jeni

91
00:03:50,497 --> 00:03:51,830
duke e bërë insertions shpejtë më.

92
00:03:51,830 --> 00:03:53,746
Ju nuk jeni vetëm tacking
gjëra onto përpara.

93
00:03:53,746 --> 00:03:55,710
Ju keni për të gjetur të
vendin e duhur për ta vënë atë,

94
00:03:55,710 --> 00:03:57,820
dhe pastaj futje tuaj
bëhet vetëm për aq e keqe

95
00:03:57,820 --> 00:03:59,390
si futur në një grup.

96
00:03:59,390 --> 00:04:03,130
Pra, listat e lidhura nuk janë
aq e madhe për klasifikim të dhënave.

97
00:04:03,130 --> 00:04:05,830
>> Ata janë gjithashtu mjaft të vogla, madhësia e-mençur.

98
00:04:05,830 --> 00:04:08,496
Dyfish i lidhur listën pak
më të mëdha se listat e lidhura në formë individuale,

99
00:04:08,496 --> 00:04:10,620
të cilat janë pak më të madhe
se vargjeve, por kjo nuk është

100
00:04:10,620 --> 00:04:13,330
një sasi të madhe të hapësirës tretur.

101
00:04:13,330 --> 00:04:18,730
Pra, nëse hapësira është shumë i kërkuar, por
jo një premium të vërtetë intensive,

102
00:04:18,730 --> 00:04:22,180
kjo mund të jetë mënyra e drejtë për të shkuar.

103
00:04:22,180 --> 00:04:23,330
>> Tavolina hash.

104
00:04:23,330 --> 00:04:25,850
Futje në një tabelë hash
është mjaft i hapur.

105
00:04:25,850 --> 00:04:26,980
Është një proces me dy faza.

106
00:04:26,980 --> 00:04:30,700
Së pari ne kemi nevojë për të drejtuar të dhënat tona përmes
një funksion hash për të marrë një kod të hash,

107
00:04:30,700 --> 00:04:37,550
dhe pastaj ne të futur elementin NË
Tabela hash në atë lokacion kodin hash.

108
00:04:37,550 --> 00:04:40,879
>> Fshirje, të ngjashme me listë të lidhura,
është e lehtë sapo ju të gjeni elementin.

109
00:04:40,879 --> 00:04:43,170
Ju keni për të gjetur atë më parë,
por pastaj kur ju fshini atë,

110
00:04:43,170 --> 00:04:45,128
ju vetëm duhet për të shkëmbyer
një çift i pointers,

111
00:04:45,128 --> 00:04:47,250
në qoftë se ju jeni duke përdorur chaining veçantë.

112
00:04:47,250 --> 00:04:49,942
Nëse jeni duke përdorur probing,
ose në qoftë se ju nuk jeni

113
00:04:49,942 --> 00:04:51,650
duke përdorur chaining në të gjitha
në tryezën tuaj hash,

114
00:04:51,650 --> 00:04:53,040
fshirje është në fakt të vërtetë e lehtë.

115
00:04:53,040 --> 00:04:57,134
Të gjithë ju duhet të bëni është të hash
të dhënave, dhe pastaj të shkoni në atë vend.

116
00:04:57,134 --> 00:04:58,925
Dhe duke supozuar që ju nuk e bëni
keni ndonjë goditjet,

117
00:04:58,925 --> 00:05:01,650
ju do të jetë në gjendje për të fshirë shumë shpejt.

118
00:05:01,650 --> 00:05:04,930
>> Tani, lookup është ajo që gjërat
merrni pak më e komplikuar.

119
00:05:04,930 --> 00:05:06,910
Është mesatarisht më të mirë
se listat e lidhura.

120
00:05:06,910 --> 00:05:09,560
Nëse jeni duke përdorur chaining,
ju ende keni një listë e lidhur,

121
00:05:09,560 --> 00:05:13,170
që do të thotë ju ende keni
Kërkimi dëm një listë e lidhur.

122
00:05:13,170 --> 00:05:18,390
Por për shkak se ju jeni duke marrë lidhur tuaj
Lista e ndarë atë mbi 100 apo 1000

123
00:05:18,390 --> 00:05:25,380
ose n elemente në tryezën tuaj hash, ju jeni
Listat e lidhura janë të gjithë një n-madhësia.

124
00:05:25,380 --> 00:05:27,650
Ata janë të gjithë në thelb më të vogla.

125
00:05:27,650 --> 00:05:32,080
Ju keni lidhur n listat vend
e një listë të lidhura me madhësi n.

126
00:05:32,080 --> 00:05:34,960
>> Dhe kështu kjo botës reale konstante
faktor, që ne në përgjithësi

127
00:05:34,960 --> 00:05:39,730
mos flasim për në kompleksitetin kohë,
ka të vërtetë të bëjë një ndryshim këtu.

128
00:05:39,730 --> 00:05:43,020
Pra lookup është ende lineare
kërko në qoftë se ju jeni duke përdorur chaining,

129
00:05:43,020 --> 00:05:46,780
por gjatësia e listës
ju jeni në kërkim përmes

130
00:05:46,780 --> 00:05:50,080
është shumë, shumë e shkurtër nga krahasimi.

131
00:05:50,080 --> 00:05:52,995
Përsëri, në qoftë se zgjidhja është tuaj
Qëllimi këtu, tabela hash-së

132
00:05:52,995 --> 00:05:54,370
ndoshta nuk është mënyra e drejtë për të shkuar.

133
00:05:54,370 --> 00:05:56,830
Vetëm të përdorni një rrjet nëse sorting
është me të vërtetë e rëndësishme për ju.

134
00:05:56,830 --> 00:05:58,590
>> Dhe ata mund të drejtuar gamë e madhësisë.

135
00:05:58,590 --> 00:06:01,640
Është e vështirë të thuhet nëse një
tabelë hash është i vogël apo i madh,

136
00:06:01,640 --> 00:06:04,110
sepse me të vërtetë varet nga
sa i madh tabelë hash juaj është.

137
00:06:04,110 --> 00:06:07,340
Nëse ju jeni vetëm do të jetë ruajtjen
pesë elemente në tryezën tuaj hash,

138
00:06:07,340 --> 00:06:10,620
dhe ju keni një tabelë hash
me 10.000 elementëve në të,

139
00:06:10,620 --> 00:06:12,614
ndoshta ju jeni të humbur një shumë hapësirë.

140
00:06:12,614 --> 00:06:15,030
Kontrasti qenë ju gjithashtu mund të
kanë tavolina shumë kompakt hash,

141
00:06:15,030 --> 00:06:18,720
por më të vogla tryezë juaj hash merr,
Sa më gjatë që secili prej këtyre listave të lidhura

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

143
00:06:19,220 --> 00:06:22,607
Dhe kështu që nuk ka të vërtetë nuk ka mënyrë për të përcaktuar
pikërisht madhësia e një tabelë hash,

144
00:06:22,607 --> 00:06:24,440
por kjo është ndoshta i sigurt
për të thënë se është në përgjithësi

145
00:06:24,440 --> 00:06:27,990
do të jetë më e madhe se një i lidhur
Lista ruajtjen të njëjtat të dhëna,

146
00:06:27,990 --> 00:06:30,400
por më i vogël se një Trie.

147
00:06:30,400 --> 00:06:32,720
>> Dhe mundohet janë katërt
e ketyre strukturave

148
00:06:32,720 --> 00:06:34,070
që ne kemi qenë duke folur rreth.

149
00:06:34,070 --> 00:06:36,450
Futur në një Trie është komplekse.

150
00:06:36,450 --> 00:06:38,400
Nuk është një shumë e dinamik
kujtese,

151
00:06:38,400 --> 00:06:40,780
veçanërisht në fillim,
si ju jeni duke filluar për të ndërtuar.

152
00:06:40,780 --> 00:06:43,700
Por është koha konstante.

153
00:06:43,700 --> 00:06:47,690
Është vetëm element njerëzor
këtu që e bën të ndërlikuar.

154
00:06:47,690 --> 00:06:53,250
Duke pasur të ndeshen treguesin null, malloc
hapësirë, shko atje, hapësirë ​​ndoshta malloc

155
00:06:53,250 --> 00:06:54,490
nga atje përsëri.

156
00:06:54,490 --> 00:06:58,880
Lloj i faktorit frikësimit të
pointers në shpërndarjen e kujtesës dinamike

157
00:06:58,880 --> 00:07:00,130
është pengesë për të pastruar.

158
00:07:00,130 --> 00:07:04,550
Por një herë ju keni pastruar atë, futje
në fakt vjen mjaft e thjeshtë,

159
00:07:04,550 --> 00:07:06,810
dhe kjo sigurisht është koha konstante.

160
00:07:06,810 --> 00:07:07,680
>> Fshirje është e lehtë.

161
00:07:07,680 --> 00:07:11,330
Të gjithë ju duhet të bëni është të lundruar poshtë një
çift ​​i pointers dhe pa nyje,

162
00:07:11,330 --> 00:07:12,420
kështu që kjo është shumë e mirë.

163
00:07:12,420 --> 00:07:13,930
Lookup është gjithashtu mjaft i shpejtë.

164
00:07:13,930 --> 00:07:16,780
Është e bazuar vetëm në
gjatësia e të dhënave tuaja.

165
00:07:16,780 --> 00:07:19,924
Pra, nëse të gjitha të dhënat tuaja është
pesë vargjet karakter,

166
00:07:19,924 --> 00:07:22,590
për shembull, ju jeni ruajtjen pesë
strings karakter në Trie tuaj,

167
00:07:22,590 --> 00:07:25,439
ajo merr vetëm pesë hapa për të
gjeni atë që ju po kërkoni.

168
00:07:25,439 --> 00:07:28,480
Pesë është vetëm një faktor konstant, kështu që
përsëri, futje, fshirje, dhe lookup

169
00:07:28,480 --> 00:07:31,670
këtu janë të gjithë kohë konstante, në mënyrë efektive.

170
00:07:31,670 --> 00:07:34,880
>> Një tjetër gjë është se Trie juaj është
në fakt renditura lloj tashmë, e drejtë?

171
00:07:34,880 --> 00:07:36,800
Duke u mbështetur në sa ne jemi
Elementet e futni

172
00:07:36,800 --> 00:07:40,060
duke shkuar letrën me letër e
kyç, ose shifra me shifra të çelësit,

173
00:07:40,060 --> 00:07:45,084
në mënyrë tipike, Trie juaj përfundon duke u
lloj i të renditura si ju të ndërtuar atë.

174
00:07:45,084 --> 00:07:47,250
Ajo nuk ka të vërtetë e bën
kuptim për të menduar për klasifikim

175
00:07:47,250 --> 00:07:49,874
në të njëjtën mënyrë që ne mendojmë për
ajo me vargjeve, ose listat e lidhura,

176
00:07:49,874 --> 00:07:51,070
ose tabelat hash.

177
00:07:51,070 --> 00:07:54,780
Por, në një kuptim, tuaj
Trie është renditur si ju shkoni.

178
00:07:54,780 --> 00:07:58,630
>> Dobësitë, natyrisht, është se
një Trie shpejt të bëhet i madh.

179
00:07:58,630 --> 00:08:02,970
Nga çdo pikë kryqëzim, ju mund të
have-- nëse çelësi yt përbëhet nga shifra,

180
00:08:02,970 --> 00:08:04,880
ju keni 10 Tjetër
vende ju mund të shkoni, që

181
00:08:04,880 --> 00:08:07,490
do të thotë se çdo nyje
përmban informacion

182
00:08:07,490 --> 00:08:11,440
për të dhënat që ju doni të ruajtur
në atë nyje, plus 10 pointers.

183
00:08:11,440 --> 00:08:14,430
I cili, në CS50 IDE, është 80 bytes.

184
00:08:14,430 --> 00:08:17,220
Pra, kjo është të paktën 80 bytes për
çdo nyje që keni krijuar,

185
00:08:17,220 --> 00:08:19,240
dhe kjo nuk është edhe numëruar të dhënat.

186
00:08:19,240 --> 00:08:24,950
Dhe nëse nyjet tuaja janë
letra në vend të shifrave,

187
00:08:24,950 --> 00:08:27,825
tani ju keni 26 pointers
nga çdo vend.

188
00:08:27,825 --> 00:08:32,007
Dhe 26 herë 8 është ndoshta 200
bytes, ose diçka të tillë.

189
00:08:32,007 --> 00:08:33,840
Dhe ju keni kapital
dhe ju mund të lowercase--

190
00:08:33,840 --> 00:08:35,381
shihni se ku unë jam duke shkuar me këtë, apo jo?

191
00:08:35,381 --> 00:08:37,500
Nyjet e juaj mund të merrni të vërtetë
i madh, dhe kështu Trie

192
00:08:37,500 --> 00:08:40,470
vetë, në përgjithësi, mund të
merrni të vërtetë e madhe, too.

193
00:08:40,470 --> 00:08:42,630
Pra, nëse hapësira është në një të lartë
premium në sistemin tuaj,

194
00:08:42,630 --> 00:08:45,830
një Trie mund të mos jetë mënyra e drejtë për
shko, edhe pse përfitimet e saj të tjera

195
00:08:45,830 --> 00:08:47,780
të hyjë në lojë.

196
00:08:47,780 --> 00:08:48,710
Unë jam Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
Kjo është CS50.

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