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

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Dus in CS50, we hebben bedekt
veel verschillende gegevensstructuren

3
00:00:08,300 --> 00:00:09,180
toch?

4
00:00:09,180 --> 00:00:11,420
We hebben gezien arrays, en gekoppeld
lijsten en hash tabellen,

5
00:00:11,420 --> 00:00:15,210
en probeert, stacks en wachtrijen.

6
00:00:15,210 --> 00:00:17,579
We zullen ook leren een beetje
over bomen en hopen,

7
00:00:17,579 --> 00:00:20,120
maar echt deze allemaal eindigen
up zijn variaties op een thema.

8
00:00:20,120 --> 00:00:22,840
Er zijn echt deze
soort van vier basisideeën

9
00:00:22,840 --> 00:00:25,190
dat alles anders kan neerkomen op.

10
00:00:25,190 --> 00:00:28,150
Arrays, gelinkte lijsten,
hash tabellen en probeert.

11
00:00:28,150 --> 00:00:30,720
En zoals ik al zei, is er
zijn variaties daarop,

12
00:00:30,720 --> 00:00:32,720
maar dit is vrij
veel gaan samenvatten

13
00:00:32,720 --> 00:00:38,140
alles wat we gaan praten
over in deze klasse in termen van C.

14
00:00:38,140 --> 00:00:40,140
>> Maar hoe deze all maatregel, toch?

15
00:00:40,140 --> 00:00:44,265
We hebben gesproken over de voors en tegens
elk in afzonderlijke video op hen

16
00:00:44,265 --> 00:00:46,390
maar er is een heleboel nummers
getting gegooid rond.

17
00:00:46,390 --> 00:00:48,723
Er is veel van de algemene
gedachten krijgen gegooid rond.

18
00:00:48,723 --> 00:00:51,950
Laten we proberen te consolideren
het in slechts een plaats.

19
00:00:51,950 --> 00:00:55,507
Laten we wegen de voors tegen
de nadelen, en te overwegen

20
00:00:55,507 --> 00:00:57,340
welke gegevensstructuur
misschien de juiste gegevens zijn

21
00:00:57,340 --> 00:01:01,440
structuur voor uw specifieke situatie,
ongeacht de aard van de gegevens u opslaan.

22
00:01:01,440 --> 00:01:06,625
Je hoeft niet altijd nodig om
gebruik maken van de supersnelle insertie, deletie,

23
00:01:06,625 --> 00:01:10,761
en opzoeken van een trie als je echt
niet de zorg over het plaatsen en verwijderen

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

25
00:01:11,260 --> 00:01:13,968
Als je hoeft alleen maar snel willekeurige
toegang, misschien een array is beter.

26
00:01:13,968 --> 00:01:15,340
Dus laten we destilleren dat.

27
00:01:15,340 --> 00:01:18,530
Laten we praten over elk van de vier
belangrijke soorten datastructuren

28
00:01:18,530 --> 00:01:21,720
dat we hebben gesproken over, en
gewoon zien als ze goed zou kunnen zijn,

29
00:01:21,720 --> 00:01:23,340
en wanneer ze misschien niet zo goed.

30
00:01:23,340 --> 00:01:24,610
Dus laten we beginnen met arrays.

31
00:01:24,610 --> 00:01:27,300
Zo inbrengen, dat is een soort van slecht.

32
00:01:27,300 --> 00:01:31,350
>> Insertie aan het einde van een array OK,
Als we bouwen een array als we verder gaan.

33
00:01:31,350 --> 00:01:33,570
Maar als we nodig hebben om in te voegen
elementen in het midden,

34
00:01:33,570 --> 00:01:35,550
denk terug aan het inbrengen
sorteren, er is veel

35
00:01:35,550 --> 00:01:37,510
van een verschuiving naar een element passen daar.

36
00:01:37,510 --> 00:01:41,170
En dus als we gaan voegen
overal, maar het einde van een array,

37
00:01:41,170 --> 00:01:43,590
dat is waarschijnlijk niet zo groot.

38
00:01:43,590 --> 00:01:46,710
>> Ook verwijderen, tenzij we zijn
verwijderen van het einde van een array,

39
00:01:46,710 --> 00:01:49,810
is waarschijnlijk ook niet zo groot als
we willen niet lege gaten te verlaten,

40
00:01:49,810 --> 00:01:50,790
die meestal doen we niet.

41
00:01:50,790 --> 00:01:54,700
We willen een element te verwijderen, en
Vervolgens soort maken het weer knus.

42
00:01:54,700 --> 00:01:57,670
En zo het verwijderen van elementen uit
een array, ook niet zo groot.

43
00:01:57,670 --> 00:01:58,820
>> Opzoeken, is echter groot.

44
00:01:58,820 --> 00:02:00,920
We hebben random access,
constante tijd opzoeken.

45
00:02:00,920 --> 00:02:03,800
Wij zeggen slechts zeven, en we gaan
array verhuizing zeven.

46
00:02:03,800 --> 00:02:05,907
Wij zeggen 20, met go aan
scala verhuizing 20.

47
00:02:05,907 --> 00:02:07,240
We hoeven niet over herhalen.

48
00:02:07,240 --> 00:02:08,630
Dat is vrij goed.

49
00:02:08,630 --> 00:02:11,020
>> Arrays zijn ook relatief gemakkelijk te sorteren.

50
00:02:11,020 --> 00:02:14,040
Elke keer als we gesproken over een sorteer-
algoritme, zoals de selectie sorteren,

51
00:02:14,040 --> 00:02:18,820
insertion sort, bubble sort, samenvoegen
sorteren, we altijd gebruikt arrays om het te doen,

52
00:02:18,820 --> 00:02:21,860
omdat arrays zijn vrij gemakkelijk te
sorteren opzichte van de datastructuren

53
00:02:21,860 --> 00:02:22,970
we tot nu toe gezien.

54
00:02:22,970 --> 00:02:24,320
>> Ze zijn ook relatief klein.

55
00:02:24,320 --> 00:02:25,695
Er is niet veel extra ruimte.

56
00:02:25,695 --> 00:02:29,210
Je zet gewoon opzij precies evenveel
als je nodig hebt om uw gegevens te houden,

57
00:02:29,210 --> 00:02:30,320
en dat is vrij veel.

58
00:02:30,320 --> 00:02:33,180
Dus ze zijn vrij klein
en efficiënt op die manier.

59
00:02:33,180 --> 00:02:36,000
Maar een ander nadeel, hoewel,
is dat ze vast formaat.

60
00:02:36,000 --> 00:02:38,630
We moeten precies aangeven hoe
groot willen we ons aanbod te zijn,

61
00:02:38,630 --> 00:02:39,940
en we krijgen slechts één schot op het.

62
00:02:39,940 --> 00:02:41,280
We kunnen niet groeien en krimpen.

63
00:02:41,280 --> 00:02:44,582
>> Als we nodig hebben om te groeien of krimpen, we
moet een geheel nieuwe array te verklaren,

64
00:02:44,582 --> 00:02:47,750
kopieer alle elementen van de
eerste array in de tweede reeks.

65
00:02:47,750 --> 00:02:51,410
En als we dat misrekend
tijd moeten we het opnieuw doen.

66
00:02:51,410 --> 00:02:52,760
Niet zo groot.

67
00:02:52,760 --> 00:02:58,750
Dus arrays niet geven ons de flexibiliteit
variabele aantallen elementen.

68
00:02:58,750 --> 00:03:01,320
>> Met een gekoppelde lijst,
inbrengen is vrij eenvoudig.

69
00:03:01,320 --> 00:03:03,290
We overstag net op de voorkant.

70
00:03:03,290 --> 00:03:04,892
Verwijdering is ook vrij eenvoudig.

71
00:03:04,892 --> 00:03:06,100
We moeten de elementen vinden.

72
00:03:06,100 --> 00:03:07,270
Dat betrekken wat zoeken.

73
00:03:07,270 --> 00:03:10,270
>> Maar als je eenmaal het element hebt gevonden
je zoekt, alles wat je hoeft te doen

74
00:03:10,270 --> 00:03:12,830
is verandering een pointer,
misschien twee als je

75
00:03:12,830 --> 00:03:15,151
een gekoppelde list-- een dubbel
gelinkte lijst, rather--

76
00:03:15,151 --> 00:03:16,650
en dan kun je gewoon gratis de node.

77
00:03:16,650 --> 00:03:18,399
Je hoeft niet te verschuiven
alles rond.

78
00:03:18,399 --> 00:03:22,090
Je verandert slechts twee pointers,
dus dat is vrij snel.

79
00:03:22,090 --> 00:03:23,470
>> Lookup is slecht maar, toch?

80
00:03:23,470 --> 00:03:26,280
Om ons te vinden een
element in een gekoppelde lijst,

81
00:03:26,280 --> 00:03:29,154
of enkelvoudig of dubbel gebonden,
we moeten lineair doorzoeken.

82
00:03:29,154 --> 00:03:32,320
We moeten beginnen bij het begin en
bewegen het einde of begin aan het einde verhuizing

83
00:03:32,320 --> 00:03:33,860
aan het begin.

84
00:03:33,860 --> 00:03:35,474
We hebben geen random access meer.

85
00:03:35,474 --> 00:03:37,265
Dus als we een doen
veel zoeken, misschien

86
00:03:37,265 --> 00:03:39,830
een gekoppelde lijst is niet
helemaal zo goed voor ons.

87
00:03:39,830 --> 00:03:43,750
>> Ze zijn ook erg
moeilijk om te sorteren, toch?

88
00:03:43,750 --> 00:03:45,666
De enige manier waarop je kunt
echt afstand een gelinkte lijst

89
00:03:45,666 --> 00:03:47,870
is om het te sorteren zoals u het construeren.

90
00:03:47,870 --> 00:03:50,497
Maar als je het te sorteren zoals u
construeren, u niet meer bent

91
00:03:50,497 --> 00:03:51,830
het maken van snelle inserties meer.

92
00:03:51,830 --> 00:03:53,746
Je bent niet zomaar overstag
dingen op de voorkant.

93
00:03:53,746 --> 00:03:55,710
Je moet het vinden
juiste plek om het te zetten,

94
00:03:55,710 --> 00:03:57,820
en dan uw inlassing
wordt ongeveer net zo slecht

95
00:03:57,820 --> 00:03:59,390
het invoegen in een array.

96
00:03:59,390 --> 00:04:03,130
Dus gelinkte lijsten zijn niet
zo geweldig voor het sorteren van data.

97
00:04:03,130 --> 00:04:05,830
>> Ze zijn ook vrij klein, size-wise.

98
00:04:05,830 --> 00:04:08,496
Dubbel gelinkte lijst lichtjes
groter dan afzonderlijk gelinkte lijsten,

99
00:04:08,496 --> 00:04:10,620
die iets groter zijn
dan arrays, maar het is niet

100
00:04:10,620 --> 00:04:13,330
een enorme hoeveelheid verspilde ruimte.

101
00:04:13,330 --> 00:04:18,730
Dus als de ruimte is op een premie, maar
niet echt een intense premie,

102
00:04:18,730 --> 00:04:22,180
dit zou de juiste weg te gaan.

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

104
00:04:23,330 --> 00:04:25,850
Inbrengen in een hash table
is vrij eenvoudig.

105
00:04:25,850 --> 00:04:26,980
Het is een proces van twee stappen.

106
00:04:26,980 --> 00:04:30,700
Eerst moeten we onze data lopen door
een hash-functie om een ​​hash-code te krijgen,

107
00:04:30,700 --> 00:04:37,550
en steek we het element in de
hash table op die hash-code locatie.

108
00:04:37,550 --> 00:04:40,879
>> Deletie, vergelijkbaar met gekoppelde lijst,
is makkelijk als je eenmaal het element te vinden.

109
00:04:40,879 --> 00:04:43,170
Je moet het eerst vinden,
maar dan als je het verwijdert,

110
00:04:43,170 --> 00:04:45,128
je hoeft alleen maar uit te wisselen
een paar pointers,

111
00:04:45,128 --> 00:04:47,250
als je met behulp aparte chaining.

112
00:04:47,250 --> 00:04:49,942
Als u gebruik maakt indringende,
of als je niet

113
00:04:49,942 --> 00:04:51,650
gebruik chaining helemaal
in de hash tabel,

114
00:04:51,650 --> 00:04:53,040
verwijdering is eigenlijk heel eenvoudig.

115
00:04:53,040 --> 00:04:57,134
Het enige wat u hoeft te doen is de hash
data, en ga vervolgens naar die locatie.

116
00:04:57,134 --> 00:04:58,925
En ervan uitgaande dat je niet
nog botsingen,

117
00:04:58,925 --> 00:05:01,650
zult u in staat om zeer snel te verwijderen.

118
00:05:01,650 --> 00:05:04,930
>> Nu, lookup is waar dingen
een beetje ingewikkelder.

119
00:05:04,930 --> 00:05:06,910
Het is gemiddeld beter
dan gelinkte lijsten.

120
00:05:06,910 --> 00:05:09,560
Als u gebruik maakt chaining,
je nog steeds een gelinkte lijst,

121
00:05:09,560 --> 00:05:13,170
wat betekent dat u nog steeds de
search nadele van een gekoppelde lijst.

122
00:05:13,170 --> 00:05:18,390
Maar omdat je het nemen van uw gekoppelde
lijst en het splitsen van het over 100 of 1000

123
00:05:18,390 --> 00:05:25,380
of n elementen in uw hash tafel, je bent
gelinkte lijsten zijn allen één n de grootte.

124
00:05:25,380 --> 00:05:27,650
Ze zijn allemaal aanzienlijk kleiner.

125
00:05:27,650 --> 00:05:32,080
Je hebt n gelinkte lijsten plaats
van een gelinkte lijst van grootte n.

126
00:05:32,080 --> 00:05:34,960
>> En dus is deze real-world constante
factor, die over het algemeen we

127
00:05:34,960 --> 00:05:39,730
praat niet over in de tijd complexiteit, is het
doet eigenlijk een verschil maken hier.

128
00:05:39,730 --> 00:05:43,020
Dus lookup is nog steeds lineair
zoeken als je gebruik chaining,

129
00:05:43,020 --> 00:05:46,780
maar de lengte van de lijst
Je zoekt

130
00:05:46,780 --> 00:05:50,080
is zeer, zeer korte vergelijking.

131
00:05:50,080 --> 00:05:52,995
Nogmaals, als sortering uw
doel hier, hash tafel

132
00:05:52,995 --> 00:05:54,370
waarschijnlijk niet de juiste manier om te gaan.

133
00:05:54,370 --> 00:05:56,830
Gewoon gebruik maken van een array als sorteren
is echt belangrijk voor je.

134
00:05:56,830 --> 00:05:58,590
>> En ze kunnen het gamma van grootte uit te voeren.

135
00:05:58,590 --> 00:06:01,640
Het is moeilijk te zeggen of een
hash table is klein of groot,

136
00:06:01,640 --> 00:06:04,110
want het is echt afhankelijk van
hoe groot uw hash tafel is.

137
00:06:04,110 --> 00:06:07,340
Als je alleen gaat worden opslaan
vijf elementen in de hash-tabel,

138
00:06:07,340 --> 00:06:10,620
en je hebt een hash table
met 10.000 elementen erin,

139
00:06:10,620 --> 00:06:12,614
bent u waarschijnlijk verspilt veel ruimte.

140
00:06:12,614 --> 00:06:15,030
Contrast dat u kunt ook
hebben zeer compact hash tabellen,

141
00:06:15,030 --> 00:06:18,720
maar de kleinere uw hash tafel krijgt,
hoe langer elk van deze verbonden lijsten

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

143
00:06:19,220 --> 00:06:22,607
En dus er is echt geen manier om te bepalen
precies grootte van een hash-tabel,

144
00:06:22,607 --> 00:06:24,440
maar het is waarschijnlijk veilig
te zeggen dat het over het algemeen

145
00:06:24,440 --> 00:06:27,990
naar groter dan gekoppeld worden
lijst opslaan van dezelfde gegevens,

146
00:06:27,990 --> 00:06:30,400
maar kleiner dan een trie.

147
00:06:30,400 --> 00:06:32,720
>> En probeert de vierde
Deze structuren

148
00:06:32,720 --> 00:06:34,070
dat we het over.

149
00:06:34,070 --> 00:06:36,450
Invoegen in een trie is complex.

150
00:06:36,450 --> 00:06:38,400
Er is veel van dynamische
toewijzing van het geheugen,

151
00:06:38,400 --> 00:06:40,780
vooral in het begin,
als je begint te bouwen.

152
00:06:40,780 --> 00:06:43,700
Maar het is een constante tijd.

153
00:06:43,700 --> 00:06:47,690
Het is alleen de menselijke factor
hier, dat maakt het lastig.

154
00:06:47,690 --> 00:06:53,250
Hoeven null pointer tegenkomen, malloc
ruimte, er naartoe te gaan, misschien malloc ruimte

155
00:06:53,250 --> 00:06:54,490
vanaf daar opnieuw.

156
00:06:54,490 --> 00:06:58,880
Het soort intimidatie factor
wijzers in dynamisch geheugen toewijzing

157
00:06:58,880 --> 00:07:00,130
is de hindernis te ontruimen.

158
00:07:00,130 --> 00:07:04,550
Maar als je eenmaal hebt gewist, insertie
komt eigenlijk heel simpel,

159
00:07:04,550 --> 00:07:06,810
en het is zeker constante tijd.

160
00:07:06,810 --> 00:07:07,680
>> Verwijdering is eenvoudig.

161
00:07:07,680 --> 00:07:11,330
Het enige wat u hoeft te doen is te navigeren in een
paar pointers en gratis het knooppunt,

162
00:07:11,330 --> 00:07:12,420
dus dat is vrij goed.

163
00:07:12,420 --> 00:07:13,930
Lookup is ook vrij snel.

164
00:07:13,930 --> 00:07:16,780
Het is alleen op basis van de
lengte van uw gegevens.

165
00:07:16,780 --> 00:07:19,924
Dus als al uw gegevens
vijf tekenreeksen,

166
00:07:19,924 --> 00:07:22,590
bijvoorbeeld, je bent het opslaan van vijf
tekenreeksen in uw trie,

167
00:07:22,590 --> 00:07:25,439
het duurt slechts vijf stappen
vinden wat je zoekt.

168
00:07:25,439 --> 00:07:28,480
Vijf is gewoon een constante factor, dus
weer, insertie, deletie en lookup

169
00:07:28,480 --> 00:07:31,670
hier zijn alle constante tijd, effectief.

170
00:07:31,670 --> 00:07:34,880
>> Een ander ding is dat uw trie is
eigenlijk wel al naargelang, toch?

171
00:07:34,880 --> 00:07:36,800
Op grond van de manier waarop we
invoegen van elementen,

172
00:07:36,800 --> 00:07:40,060
door te gaan letter voor letter van de
toets of cijfer voor cijfer van de sleutel,

173
00:07:40,060 --> 00:07:45,084
typisch, uw trie eindigt in
soort naargelang als je bouwen.

174
00:07:45,084 --> 00:07:47,250
Het maakt eigenlijk niet maakt
zin om na te denken over het sorteren

175
00:07:47,250 --> 00:07:49,874
op dezelfde manier waarop we denken over
met arrays of gelinkte lijsten,

176
00:07:49,874 --> 00:07:51,070
of hash tabellen.

177
00:07:51,070 --> 00:07:54,780
Maar in zekere zin, je
trie wordt gesorteerd als je gaat.

178
00:07:54,780 --> 00:07:58,630
>> Het nadeel is natuurlijk dat
een trie snel wordt enorm.

179
00:07:58,630 --> 00:08:02,970
Vanuit elk knooppunt, zou je
have-- als uw sleutel bestaat uit cijfers,

180
00:08:02,970 --> 00:08:04,880
heb je 10 andere
plekken waar je kunt gaan, wat

181
00:08:04,880 --> 00:08:07,490
betekent dat elk knooppunt
bevat informatie

182
00:08:07,490 --> 00:08:11,440
over de gegevens die u wilt opslaan
op dat knooppunt, plus 10 pointers.

183
00:08:11,440 --> 00:08:14,430
Die op CS50 IDE, is 80 bytes.

184
00:08:14,430 --> 00:08:17,220
Dus is ten minste 80 bytes
elk knooppunt die u maakt,

185
00:08:17,220 --> 00:08:19,240
en dat is niet eens tellen data.

186
00:08:19,240 --> 00:08:24,950
En als je knooppunten
letters in plaats van cijfers,

187
00:08:24,950 --> 00:08:27,825
nu heb je 26 pointers
vanaf elke locatie.

188
00:08:27,825 --> 00:08:32,007
En 26 tijden 8 waarschijnlijk 200
bytes, of iets dergelijks.

189
00:08:32,007 --> 00:08:33,840
En je hebt het kapitaal
en lowercase-- u kunt

190
00:08:33,840 --> 00:08:35,381
zien waar ik ga met deze, toch?

191
00:08:35,381 --> 00:08:37,500
Uw knooppunten kan echt
groot, en zo de Trie

192
00:08:37,500 --> 00:08:40,470
zelf, algemeen, kan
krijgen heel groot, ook.

193
00:08:40,470 --> 00:08:42,630
Als de ruimte is op een hoog
premie op uw systeem,

194
00:08:42,630 --> 00:08:45,830
een trie zou de juiste manier om niet
gaan, ook al zijn andere voordelen

195
00:08:45,830 --> 00:08:47,780
in het spel komen.

196
00:08:47,780 --> 00:08:48,710
Ik ben Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
Dit is CS50.

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