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

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Så i CS50, har vi dækket
en masse forskellige datastrukturer,

3
00:00:08,300 --> 00:00:09,180
højre?

4
00:00:09,180 --> 00:00:11,420
Vi har set arrays, og forbundet
lister og hash tabeller,

5
00:00:11,420 --> 00:00:15,210
og forsøger, stakke og køer.

6
00:00:15,210 --> 00:00:17,579
Vi vil også lære lidt
om træer og dynger,

7
00:00:17,579 --> 00:00:20,120
men virkelig disse alle bare ende
at blive variationer over et tema.

8
00:00:20,120 --> 00:00:22,840
Der er virkelig disse
slags fire grundlæggende ideer

9
00:00:22,840 --> 00:00:25,190
at alt andet kan koges ned til.

10
00:00:25,190 --> 00:00:28,150
Arrays, hægtede lister,
hash tabeller og forsøger.

11
00:00:28,150 --> 00:00:30,720
Og som jeg sagde, er der
er variationer over dem,

12
00:00:30,720 --> 00:00:32,720
men dette er temmelig
meget kommer til at opsummere

13
00:00:32,720 --> 00:00:38,140
alt, hvad vi kommer til at tale
om i denne klasse i form af C.

14
00:00:38,140 --> 00:00:40,140
>> Men hvordan gør disse alle måle op, ikke?

15
00:00:40,140 --> 00:00:44,265
Vi har talt om fordele og ulemper
af hver i separate videoer på dem,

16
00:00:44,265 --> 00:00:46,390
men der er en masse tal
at blive kastet rundt.

17
00:00:46,390 --> 00:00:48,723
Der er en masse generel
tanker blive kastet rundt.

18
00:00:48,723 --> 00:00:51,950
Lad os prøve og konsolidere
det i ét sted.

19
00:00:51,950 --> 00:00:55,507
Lad os afveje fordele mod
ulemperne, og overveje

20
00:00:55,507 --> 00:00:57,340
som datastruktur
kunne være det rigtige data

21
00:00:57,340 --> 00:01:01,440
struktur for netop din situation,
uanset hvilken type data, du opbevaring.

22
00:01:01,440 --> 00:01:06,625
Du behøver ikke nødvendigvis altid behøver at
bruge super hurtig indsættelse, sletning,

23
00:01:06,625 --> 00:01:10,761
og opslag af en trie, hvis du virkelig
er ligeglad indsættelse og sletning

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

25
00:01:11,260 --> 00:01:13,968
Hvis du har brug for lige hurtigt tilfældig
adgang, måske et array er bedre.

26
00:01:13,968 --> 00:01:15,340
Så lad os destillere det.

27
00:01:15,340 --> 00:01:18,530
Lad os tale om hver af de fire
store typer af datastrukturer

28
00:01:18,530 --> 00:01:21,720
at vi har talt om, og
bare se, når de kunne være gode,

29
00:01:21,720 --> 00:01:23,340
og når de måske ikke være så god.

30
00:01:23,340 --> 00:01:24,610
Så lad os starte med arrays.

31
00:01:24,610 --> 00:01:27,300
Så indsættelse, der er slags dårlig.

32
00:01:27,300 --> 00:01:31,350
>> Insertion i slutningen af ​​et array er OK,
hvis vi bygger et array, som vi går.

33
00:01:31,350 --> 00:01:33,570
Men hvis vi har brug for at indsætte
elementer i midten,

34
00:01:33,570 --> 00:01:35,550
tænker tilbage på indsættelse
sortere, der er en masse

35
00:01:35,550 --> 00:01:37,510
at flytte til at passe et element derinde.

36
00:01:37,510 --> 00:01:41,170
Og så hvis vi kommer til at indsætte
overalt, men i slutningen af ​​et array,

37
00:01:41,170 --> 00:01:43,590
det er nok ikke så stor.

38
00:01:43,590 --> 00:01:46,710
>> Tilsvarende sletning, medmindre vi er
sletning fra enden af ​​et array,

39
00:01:46,710 --> 00:01:49,810
er nok heller ikke så stor, hvis
Vi ønsker ikke at efterlade tomme huller,

40
00:01:49,810 --> 00:01:50,790
som normalt gør vi ikke.

41
00:01:50,790 --> 00:01:54,700
Vi ønsker at fjerne et element, og
så slags gør det lunt igen.

42
00:01:54,700 --> 00:01:57,670
Og så sletter elementer fra
et array, heller ikke så stor.

43
00:01:57,670 --> 00:01:58,820
>> Opslag, er dog stor.

44
00:01:58,820 --> 00:02:00,920
Vi har random access,
konstant tid opslag.

45
00:02:00,920 --> 00:02:03,800
Vi bare sige syv, og vi går
til matrix udflytning syv.

46
00:02:03,800 --> 00:02:05,907
Vi siger 20, med gå til
vifte udflytning 20.

47
00:02:05,907 --> 00:02:07,240
Vi behøver ikke at gentage hele.

48
00:02:07,240 --> 00:02:08,630
Det er temmelig godt.

49
00:02:08,630 --> 00:02:11,020
>> Arrays er også forholdsvis let at sortere.

50
00:02:11,020 --> 00:02:14,040
Hver gang vi talte om en sortering
algoritme, såsom udvælgelse sortere,

51
00:02:14,040 --> 00:02:18,820
indsættelse sortere, boble sortere, fusionere
sortere, vi altid brugt arrays til at gøre det,

52
00:02:18,820 --> 00:02:21,860
fordi arrays er temmelig let at
Sorter forhold til de datastrukturer

53
00:02:21,860 --> 00:02:22,970
vi hidtil har set.

54
00:02:22,970 --> 00:02:24,320
>> De er også relativt lille.

55
00:02:24,320 --> 00:02:25,695
Der er ikke en masse ekstra plads.

56
00:02:25,695 --> 00:02:29,210
Du skal bare afsat nøjagtig lige så meget
som du har brug for at holde dine data,

57
00:02:29,210 --> 00:02:30,320
og det er temmelig meget det.

58
00:02:30,320 --> 00:02:33,180
Så de er temmelig lille
og effektivt på denne måde.

59
00:02:33,180 --> 00:02:36,000
Men en anden ulempe, selv om,
er, at de er fastsat i størrelse.

60
00:02:36,000 --> 00:02:38,630
Vi er nødt til at erklære, præcis hvordan
store vi ønsker, at vores array til at være,

61
00:02:38,630 --> 00:02:39,940
og vi får kun ét skud på det.

62
00:02:39,940 --> 00:02:41,280
Vi kan ikke vokse og skrumpe det.

63
00:02:41,280 --> 00:02:44,582
>> Hvis vi har brug for at vokse eller skrumpe det, vi
nødt til at erklære en helt ny array,

64
00:02:44,582 --> 00:02:47,750
kopiere alle elementer i
første opstilling i den anden matrix.

65
00:02:47,750 --> 00:02:51,410
Og hvis vi fejlberegnet, at
tid, er vi nødt til at gøre det igen.

66
00:02:51,410 --> 00:02:52,760
Ikke så stor.

67
00:02:52,760 --> 00:02:58,750
Så arrays ikke giver os den fleksibilitet
at have variabelt antal elementer.

68
00:02:58,750 --> 00:03:01,320
>> Med en sammenkædet liste,
indsættelse er temmelig let.

69
00:03:01,320 --> 00:03:03,290
Vi har lige tack på forsiden.

70
00:03:03,290 --> 00:03:04,892
Sletning er også temmelig let.

71
00:03:04,892 --> 00:03:06,100
Vi er nødt til at finde elementerne.

72
00:03:06,100 --> 00:03:07,270
Det indebærer nogle søger.

73
00:03:07,270 --> 00:03:10,270
>> Men når du har fundet elementet
du leder efter, alt hvad du behøver at gøre

74
00:03:10,270 --> 00:03:12,830
er at ændre en pegepind,
eventuelt to, hvis du har

75
00:03:12,830 --> 00:03:15,151
en sammenkædet list-- en dobbelt
sammenkædet liste, rather--

76
00:03:15,151 --> 00:03:16,650
og så kan du bare frigøre node.

77
00:03:16,650 --> 00:03:18,399
Du behøver ikke at flytte
alt omkring.

78
00:03:18,399 --> 00:03:22,090
Du skal bare ændre to pointere,
så det er temmelig hurtig.

79
00:03:22,090 --> 00:03:23,470
>> Opslag er dårlig selv, ikke?

80
00:03:23,470 --> 00:03:26,280
For os at finde en
element i en sammenkædet liste,

81
00:03:26,280 --> 00:03:29,154
om enkeltvis eller dobbelt forbundet,
vi er nødt til lineær søge den.

82
00:03:29,154 --> 00:03:32,320
Vi er nødt til at starte ved begyndelsen og
flytte enden, eller starte i slutningen farten

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

84
00:03:33,860 --> 00:03:35,474
Vi har ikke random access længere.

85
00:03:35,474 --> 00:03:37,265
Så hvis vi laver en
masse søgning, måske

86
00:03:37,265 --> 00:03:39,830
en sammenkædet liste er ikke
helt så godt for os.

87
00:03:39,830 --> 00:03:43,750
>> De er også virkelig
vanskeligt at sortere, ikke?

88
00:03:43,750 --> 00:03:45,666
Den eneste måde du kan
virkelig sortere en sammenkædet liste

89
00:03:45,666 --> 00:03:47,870
er at sortere det, som du konstruere den.

90
00:03:47,870 --> 00:03:50,497
Men hvis du sortere det som du
konstruere det, er du ikke længere

91
00:03:50,497 --> 00:03:51,830
lave hurtige indrykninger længere.

92
00:03:51,830 --> 00:03:53,746
Du er ikke bare krydse
ting på forsiden.

93
00:03:53,746 --> 00:03:55,710
Du er nødt til at finde den
rigtige sted at sætte det,

94
00:03:55,710 --> 00:03:57,820
og så vil din indsættelse
bliver omtrent lige så slemt

95
00:03:57,820 --> 00:03:59,390
som indsætning i et array.

96
00:03:59,390 --> 00:04:03,130
Så forbundne lister er ikke
så stor for sortering af data.

97
00:04:03,130 --> 00:04:05,830
>> De er også temmelig lille, størrelse-wise.

98
00:04:05,830 --> 00:04:08,496
Dobbelt knyttet liste lidt
større end enkeltvis hægtede lister,

99
00:04:08,496 --> 00:04:10,620
som er lidt større
end arrays, men det er ikke

100
00:04:10,620 --> 00:04:13,330
en enorm mængde spildplads.

101
00:04:13,330 --> 00:04:18,730
Så hvis pladsen er på en præmie, men
ikke en rigtig intens præmie,

102
00:04:18,730 --> 00:04:22,180
dette kan være den rigtige vej at gå.

103
00:04:22,180 --> 00:04:23,330
>> Hash tabeller.

104
00:04:23,330 --> 00:04:25,850
Indføring i en hashtabel
er forholdsvis ligetil.

105
00:04:25,850 --> 00:04:26,980
Det er en to-trins proces.

106
00:04:26,980 --> 00:04:30,700
Først skal vi køre vores data gennem
en hash-funktion for at få en hash-kode,

107
00:04:30,700 --> 00:04:37,550
og så vi indsætter elementet ind i
hash tabellen på det hashkode placering.

108
00:04:37,550 --> 00:04:40,879
>> Deletion, der svarer til sammenkædet liste,
er nemt, når du finder det element.

109
00:04:40,879 --> 00:04:43,170
Du er nødt til at finde det første,
men så når du sletter den,

110
00:04:43,170 --> 00:04:45,128
du bare brug for at udveksle
et par pointere,

111
00:04:45,128 --> 00:04:47,250
hvis du bruger separat kæde.

112
00:04:47,250 --> 00:04:49,942
Hvis du bruger sondering,
eller hvis du ikke er

113
00:04:49,942 --> 00:04:51,650
ved hjælp af kæde overhovedet
i dit hash tabel,

114
00:04:51,650 --> 00:04:53,040
sletning er faktisk virkelig nemt.

115
00:04:53,040 --> 00:04:57,134
Alt du skal gøre er at hash det
data, og derefter gå til denne placering.

116
00:04:57,134 --> 00:04:58,925
Og forudsat du ikke gør
har nogen kollisioner,

117
00:04:58,925 --> 00:05:01,650
vil du være i stand til at slette meget hurtigt.

118
00:05:01,650 --> 00:05:04,930
>> Nu opslag er, hvor tingene
få lidt mere kompliceret.

119
00:05:04,930 --> 00:05:06,910
Det er i gennemsnit bedre
end hægtede lister.

120
00:05:06,910 --> 00:05:09,560
Hvis du bruger kæde,
du stadig har en linket liste,

121
00:05:09,560 --> 00:05:13,170
hvilket betyder, at du stadig har den
søgning skade en sammenkædet liste.

122
00:05:13,170 --> 00:05:18,390
Men fordi du tager dit forbundet
listen og opdele den over 100 eller 1.000

123
00:05:18,390 --> 00:05:25,380
eller n elementer i dit hash tabel, er du
hægtede lister er alle én n'te størrelsen.

124
00:05:25,380 --> 00:05:27,650
De er alle væsentligt mindre.

125
00:05:27,650 --> 00:05:32,080
Du har n forbundet lister i stedet
af en sammenkædet liste af størrelse n.

126
00:05:32,080 --> 00:05:34,960
>> Og så dette virkelige verden konstant
faktor, som vi generelt

127
00:05:34,960 --> 00:05:39,730
taler ikke om i tide kompleksitet, det
rent faktisk gør en forskel her.

128
00:05:39,730 --> 00:05:43,020
Så opslag er stadig lineær
søge, hvis du bruger kæde,

129
00:05:43,020 --> 00:05:46,780
men længden af ​​listen
du søger gennem

130
00:05:46,780 --> 00:05:50,080
er meget, meget kort ved sammenligning.

131
00:05:50,080 --> 00:05:52,995
Igen, hvis sortering er din
mål her, hash tabellens

132
00:05:52,995 --> 00:05:54,370
sandsynligvis ikke den rigtige vej at gå.

133
00:05:54,370 --> 00:05:56,830
Bare bruge et array hvis sortering
er virkelig vigtigt for dig.

134
00:05:56,830 --> 00:05:58,590
>> Og de kan køre farveskala af størrelse.

135
00:05:58,590 --> 00:06:01,640
Det er svært at sige, om en
hash bordet er lille eller stor,

136
00:06:01,640 --> 00:06:04,110
fordi det virkelig afhænger af
hvor stor din hash bordet er.

137
00:06:04,110 --> 00:06:07,340
Hvis du kun vil være at lagre
fem elementer i din hash tabellen,

138
00:06:07,340 --> 00:06:10,620
og du har en hash tabel
med 10.000 elementer i det,

139
00:06:10,620 --> 00:06:12,614
du sandsynligvis spilde en masse plads.

140
00:06:12,614 --> 00:06:15,030
Kontrast være du også
har meget kompakte hash tabeller,

141
00:06:15,030 --> 00:06:18,720
men mindre din hash tabel får,
jo længere hver af disse forbundne lister

142
00:06:18,720 --> 00:06:19,220
får.

143
00:06:19,220 --> 00:06:22,607
Og så der er virkelig ingen måde at definere
nøjagtigt størrelsen af ​​en hash tabel,

144
00:06:22,607 --> 00:06:24,440
men det er nok sikkert
at sige, det er generelt

145
00:06:24,440 --> 00:06:27,990
vil være større end en sammenkædet
liste lagring af samme data,

146
00:06:27,990 --> 00:06:30,400
men mindre end en trie.

147
00:06:30,400 --> 00:06:32,720
>> Og kunne er den fjerde
af disse strukturer

148
00:06:32,720 --> 00:06:34,070
at vi har talt om.

149
00:06:34,070 --> 00:06:36,450
Indsættelse i en trie er kompleks.

150
00:06:36,450 --> 00:06:38,400
Der er en masse dynamisk
hukommelse tildeling,

151
00:06:38,400 --> 00:06:40,780
især i begyndelsen,
som du begynder at bygge.

152
00:06:40,780 --> 00:06:43,700
Men det er konstant tid.

153
00:06:43,700 --> 00:06:47,690
Det er kun det menneskelige element
her, der gør det vanskeligt.

154
00:06:47,690 --> 00:06:53,250
At skulle støde null-pointer, malloc
plads, gå der, eventuelt malloc plads

155
00:06:53,250 --> 00:06:54,490
derfra igen.

156
00:06:54,490 --> 00:06:58,880
Den slags intimidering faktor
pejlemærker i dynamisk allokering af hukommelse

157
00:06:58,880 --> 00:07:00,130
er den hurdle at rydde.

158
00:07:00,130 --> 00:07:04,550
Men når du har ryddet det, indsættelse
faktisk kommer ganske enkel,

159
00:07:04,550 --> 00:07:06,810
og det er bestemt konstant tid.

160
00:07:06,810 --> 00:07:07,680
>> Sletning er nemt.

161
00:07:07,680 --> 00:07:11,330
Alt du skal gøre er at navigere ned en
par pointere og fri knudepunktet,

162
00:07:11,330 --> 00:07:12,420
så det er temmelig godt.

163
00:07:12,420 --> 00:07:13,930
Opslag er også temmelig hurtigt.

164
00:07:13,930 --> 00:07:16,780
Det er kun baseret på
længden af ​​dine data.

165
00:07:16,780 --> 00:07:19,924
Så hvis alle dine data er
fem tegnstrenge,

166
00:07:19,924 --> 00:07:22,590
for eksempel, er du lagre fem
tegnstrenge i din trie,

167
00:07:22,590 --> 00:07:25,439
det tager kun fem trin til
finde det, du leder efter.

168
00:07:25,439 --> 00:07:28,480
Fem er bare en konstant faktor, så
igen, insertion, deletion og opslag

169
00:07:28,480 --> 00:07:31,670
her er alle konstant tid, effektivt.

170
00:07:31,670 --> 00:07:34,880
>> En anden ting er, at din trie er
faktisk slags allerede sorteres, ikke?

171
00:07:34,880 --> 00:07:36,800
I kraft af, hvordan vi er
indsætte elementer,

172
00:07:36,800 --> 00:07:40,060
ved at gå bogstav for bogstav af det
nøgle, eller ciffer for ciffer af nøglen,

173
00:07:40,060 --> 00:07:45,084
typisk din Trie ender med at blive
slags sorteres som du bygger det.

174
00:07:45,084 --> 00:07:47,250
Det betyder ikke virkelig gør
mening at tænke på sortering

175
00:07:47,250 --> 00:07:49,874
på samme måde, vi tænker
det med arrays eller hægtede lister,

176
00:07:49,874 --> 00:07:51,070
eller hash tabeller.

177
00:07:51,070 --> 00:07:54,780
Men i en vis forstand, din
Trie sorteres som du går.

178
00:07:54,780 --> 00:07:58,630
>> Ulempen er naturligvis, at
en trie hurtigt bliver stort.

179
00:07:58,630 --> 00:08:02,970
Fra hvert knudepunkt punkt, kan du
have-- hvis din nøgle består af cifre,

180
00:08:02,970 --> 00:08:04,880
du har 10 andre
steder, du kan gå, hvilket

181
00:08:04,880 --> 00:08:07,490
betyder, at hver node
indeholder oplysninger

182
00:08:07,490 --> 00:08:11,440
om de data, du vil gemme
ved dette knudepunkt, plus 10 pointere.

183
00:08:11,440 --> 00:08:14,430
Som på CS50 IDE, er 80 bytes.

184
00:08:14,430 --> 00:08:17,220
Så det er mindst 80 bytes for
hver node, du opretter,

185
00:08:17,220 --> 00:08:19,240
Og det er ikke engang tælle data.

186
00:08:19,240 --> 00:08:24,950
Og hvis dine noder er
bogstaver i stedet for tal,

187
00:08:24,950 --> 00:08:27,825
nu har du 26 pejlemærker
fra hvert sted.

188
00:08:27,825 --> 00:08:32,007
Og 26 gange 8 er formentlig 200
byte, eller noget lignende.

189
00:08:32,007 --> 00:08:33,840
Og du har kapital
og lowercase-- du kan

190
00:08:33,840 --> 00:08:35,381
se, hvor jeg har tænkt mig med dette, ikke?

191
00:08:35,381 --> 00:08:37,500
Dine noder kan få virkelig
store og så trie

192
00:08:37,500 --> 00:08:40,470
selv, samlet, kan
få virkelig store, også.

193
00:08:40,470 --> 00:08:42,630
Så hvis pladsen er på et højt
præmie på dit system,

194
00:08:42,630 --> 00:08:45,830
en trie måske ikke den rigtige måde at
gå, selvom dens andre fordele

195
00:08:45,830 --> 00:08:47,780
komme i spil.

196
00:08:47,780 --> 00:08:48,710
Jeg er Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
Det er CS50.

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