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

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Així que en CS50, hem cobert
un munt de diferents estructures de dades,

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

4
00:00:09,180 --> 00:00:11,420
Hem vist les matrius, i vinculats
llistes i taules hash,

5
00:00:11,420 --> 00:00:15,210
i tries, piles i cues.

6
00:00:15,210 --> 00:00:17,579
També aprendrem una mica
sobre els arbres i munts,

7
00:00:17,579 --> 00:00:20,120
però en realitat tots aquests simplement acaben
sent fins variacions sobre un tema.

8
00:00:20,120 --> 00:00:22,840
Realment és això
tipus de quatre idees bàsiques

9
00:00:22,840 --> 00:00:25,190
que tota la resta es redueixen a.

10
00:00:25,190 --> 00:00:28,150
Arrays, llistes enllaçades,
taules hash i tries.

11
00:00:28,150 --> 00:00:30,720
I com he dit, no
són variacions sobre ells,

12
00:00:30,720 --> 00:00:32,720
però això és bastant
hi ha molt a fer per resumir

13
00:00:32,720 --> 00:00:38,140
tot el que anem a parlar
sobre aquesta classe en termes de C.

14
00:00:38,140 --> 00:00:40,140
>> Però, ¿com fan aquests de tota mesura, no?

15
00:00:40,140 --> 00:00:44,265
Hem parlat sobre els pros i els contres
de cada un en vídeos separats sobre ells,

16
00:00:44,265 --> 00:00:46,390
però hi ha un munt de nombres
sent llançat voltant.

17
00:00:46,390 --> 00:00:48,723
Hi ha una gran quantitat de generals
pensaments aconseguir llançats voltant.

18
00:00:48,723 --> 00:00:51,950
Anem a tractar de consolidar
en un sol lloc.

19
00:00:51,950 --> 00:00:55,507
Anem a sospesar els pros contra
els contres, i consideren

20
00:00:55,507 --> 00:00:57,340
que l'estructura de dades
podrien ser les dades correctes

21
00:00:57,340 --> 00:01:01,440
estructura per a la seva situació particular,
qualsevol tipus de dades que s'està emmagatzemant.

22
00:01:01,440 --> 00:01:06,625
No necessàriament sempre cal
utilitzar la inserció super ràpid, eliminació,

23
00:01:06,625 --> 00:01:10,761
i la recerca d'un trie si realment
no es preocupen per la inserció i eliminació

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

25
00:01:11,260 --> 00:01:13,968
Si vostè necessita només ràpidament a l'atzar
l'accés, pot ser que un arranjament és millor.

26
00:01:13,968 --> 00:01:15,340
Així que anem a destil·lar això.

27
00:01:15,340 --> 00:01:18,530
Anem a parlar de cada un dels quatre
principals tipus d'estructures de dades

28
00:01:18,530 --> 00:01:21,720
que hem parlat, i
simplement veure quan pot ser bo,

29
00:01:21,720 --> 00:01:23,340
i quan ells podrien no ser tan bo.

30
00:01:23,340 --> 00:01:24,610
Així que començarem amb les matrius.

31
00:01:24,610 --> 00:01:27,300
Així inserció, això és una cosa dolenta.

32
00:01:27,300 --> 00:01:31,350
>> La inserció en el final d'una matriu està bé,
si estem construint un arsenal a mesura que avancem.

33
00:01:31,350 --> 00:01:33,570
Però si hem d'inserir
elements en el medi,

34
00:01:33,570 --> 00:01:35,550
pensar de nou a la inserció
espècie, hi ha molt

35
00:01:35,550 --> 00:01:37,510
de canviar per adaptar-se a un element en aquest país.

36
00:01:37,510 --> 00:01:41,170
I pel que si anem a inserir
en qualsevol lloc, però el final d'una matriu,

37
00:01:41,170 --> 00:01:43,590
no crec que sigui tan gran.

38
00:01:43,590 --> 00:01:46,710
>> De la mateixa manera, la supressió, llevat que estiguem
esborrar des del final d'una matriu,

39
00:01:46,710 --> 00:01:49,810
és probable que també no tan gran si
no volem deixar espais buits,

40
00:01:49,810 --> 00:01:50,790
que en general no ho fem.

41
00:01:50,790 --> 00:01:54,700
Volem eliminar un element, i
llavors espècie que sigui ajustat de nou.

42
00:01:54,700 --> 00:01:57,670
I així la supressió d'elements de
una matriu, també no tan gran.

43
00:01:57,670 --> 00:01:58,820
>> Operacions de recerca, però, és gran.

44
00:01:58,820 --> 00:02:00,920
Tenim accés aleatori,
recerca constant de temps.

45
00:02:00,920 --> 00:02:03,800
Acabem de dir 7, i ens anem
a la reubicació sèrie de set.

46
00:02:03,800 --> 00:02:05,907
Diem 20, a la cita de
reubicació sèrie 20.

47
00:02:05,907 --> 00:02:07,240
Nosaltres no hem de recórrer a través.

48
00:02:07,240 --> 00:02:08,630
Això és bastant bo.

49
00:02:08,630 --> 00:02:11,020
>> Les matrius també són relativament fàcils de resoldre.

50
00:02:11,020 --> 00:02:14,040
Cada vegada que parlem d'una classificació
algoritme, com la selecció de gènere,

51
00:02:14,040 --> 00:02:18,820
ordenació per inserció, ordenament de bombolla, fusionar
espècie, sempre fem servir matrius per fer-ho,

52
00:02:18,820 --> 00:02:21,860
perquè les matrius són bastant fàcils de
espècie, amb relació a les estructures de dades

53
00:02:21,860 --> 00:02:22,970
que hem vist fins ara.

54
00:02:22,970 --> 00:02:24,320
>> També són relativament petites.

55
00:02:24,320 --> 00:02:25,695
No hi ha un munt d'espai extra.

56
00:02:25,695 --> 00:02:29,210
Vostè acaba de deixar de banda la mateixa mesura
com sigui necessari per mantenir les seves dades,

57
00:02:29,210 --> 00:02:30,320
i això és pràcticament tot.

58
00:02:30,320 --> 00:02:33,180
Així que són bastant petites
i eficient d'aquesta manera.

59
00:02:33,180 --> 00:02:36,000
Però un altre aspecte negatiu, però,
és que estan fixos en grandària.

60
00:02:36,000 --> 00:02:38,630
Hem de declarar exactament com
gran Volem que la nostra matriu a ser,

61
00:02:38,630 --> 00:02:39,940
i només tenim una oportunitat.

62
00:02:39,940 --> 00:02:41,280
No podem créixer i reduir la seva grandària.

63
00:02:41,280 --> 00:02:44,582
>> Si necessitem per créixer o encongir, ens
hagi de declarar una matriu totalment nou,

64
00:02:44,582 --> 00:02:47,750
copiar tots els elements de la
primera matriu en la segona matriu.

65
00:02:47,750 --> 00:02:51,410
I si calculem malament que
temps, hem de fer-ho de nou.

66
00:02:51,410 --> 00:02:52,760
No tan fantàstic.

67
00:02:52,760 --> 00:02:58,750
Així matrius no ens donen la flexibilitat
tenir un nombre variable d'elements.

68
00:02:58,750 --> 00:03:01,320
>> Amb una llista enllaçada,
la inserció és bastant fàcil.

69
00:03:01,320 --> 00:03:03,290
Acabem de virar cap al front.

70
00:03:03,290 --> 00:03:04,892
Supressió també és bastant fàcil.

71
00:03:04,892 --> 00:03:06,100
Hem de trobar els elements.

72
00:03:06,100 --> 00:03:07,270
Que impliquen algunes recerques.

73
00:03:07,270 --> 00:03:10,270
>> Però una vegada que hagi trobat l'element
que estàs buscant, tot el que ha de fer

74
00:03:10,270 --> 00:03:12,830
és canviar un punter,
possiblement dos si té

75
00:03:12,830 --> 00:03:15,151
una de vinculada pel·lícules-- un doble
llista enllaçada, rather--

76
00:03:15,151 --> 00:03:16,650
i llavors vostè pot simplement alliberar el node.

77
00:03:16,650 --> 00:03:18,399
Vostè no ha de canviar
tot al seu voltant.

78
00:03:18,399 --> 00:03:22,090
Vostè acaba de canviar dos punters,
així que això és bastant ràpid.

79
00:03:22,090 --> 00:03:23,470
>> Operacions de recerca és dolent, oi?

80
00:03:23,470 --> 00:03:26,280
Per tal per a nosaltres trobar un
element d'una llista enllaçada,

81
00:03:26,280 --> 00:03:29,154
ja sigui individualment o doblement enllaçada,
hem de buscar-la en el lineal.

82
00:03:29,154 --> 00:03:32,320
Hem de començar pel principi i
moure l'extrem, o començar pel moviment final

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

84
00:03:33,860 --> 00:03:35,474
No tenim accés aleatori més.

85
00:03:35,474 --> 00:03:37,265
Així que si estem fent un
munt de recerca, potser

86
00:03:37,265 --> 00:03:39,830
una llista enllaçada no és
tan bo per a nosaltres.

87
00:03:39,830 --> 00:03:43,750
>> També són molt
difícil de resoldre, oi?

88
00:03:43,750 --> 00:03:45,666
L'única manera que pugui
realment ordenar una llista enllaçada

89
00:03:45,666 --> 00:03:47,870
és per solucionar el problema a mesura que construeixes ell.

90
00:03:47,870 --> 00:03:50,497
Però si ordena com vostè
construir-lo, ja no estàs

91
00:03:50,497 --> 00:03:51,830
fent insercions ràpides més.

92
00:03:51,830 --> 00:03:53,746
No està sol virades
coses a la part frontal.

93
00:03:53,746 --> 00:03:55,710
Has de trobar la
lloc adequat per dir-ho,

94
00:03:55,710 --> 00:03:57,820
i després la seva inserció
es torna gairebé tan dolent

95
00:03:57,820 --> 00:03:59,390
com la inserció en una matriu.

96
00:03:59,390 --> 00:04:03,130
Així llistes enllaçades no són
tan gran per a la classificació de dades.

97
00:04:03,130 --> 00:04:05,830
>> També són bastant petites, de mida convenient.

98
00:04:05,830 --> 00:04:08,496
Llista doblement enllaçada lleugerament
més gran que les llistes per separat enllaçats,

99
00:04:08,496 --> 00:04:10,620
que són lleugerament més grans
de matrius, però no és

100
00:04:10,620 --> 00:04:13,330
una enorme quantitat d'espai desaprofitat.

101
00:04:13,330 --> 00:04:18,730
Així que si l'espai és un bé escàs, però
no una prima molt intens,

102
00:04:18,730 --> 00:04:22,180
aquest podria ser el camí correcte a seguir.

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

104
00:04:23,330 --> 00:04:25,850
La inserció en una taula hash
és bastant senzill.

105
00:04:25,850 --> 00:04:26,980
És un procés de dos passos.

106
00:04:26,980 --> 00:04:30,700
En primer lloc hem de córrer a través dels nostres dades
una funció hash per obtenir un codi hash,

107
00:04:30,700 --> 00:04:37,550
i després inserim l'element en el
taula hash en aquesta ubicació codi hash.

108
00:04:37,550 --> 00:04:40,879
>> Supressió, similar a la llista enllaçada,
és fàcil una vegada que trobi l'element.

109
00:04:40,879 --> 00:04:43,170
Has de trobar-primer,
però després, quan ho elimina,

110
00:04:43,170 --> 00:04:45,128
només ha d'intercanviar
un parell de punters,

111
00:04:45,128 --> 00:04:47,250
si vostè està utilitzant encadenament separat.

112
00:04:47,250 --> 00:04:49,942
Si utilitzeu el sondeig,
o si no estàs

113
00:04:49,942 --> 00:04:51,650
utilitzant l'encadenament en absolut
en la seva taula hash,

114
00:04:51,650 --> 00:04:53,040
eliminació és realment molt fàcil.

115
00:04:53,040 --> 00:04:57,134
Tot el que necessites fer és hash de la
de dades i, a continuació, anar a aquest lloc.

116
00:04:57,134 --> 00:04:58,925
I suposant que no ho fa
tenir col·lisions,

117
00:04:58,925 --> 00:05:01,650
podràs eliminar ràpidament.

118
00:05:01,650 --> 00:05:04,930
>> Ara, la recerca és on les coses
ser una mica més complicat.

119
00:05:04,930 --> 00:05:06,910
Està enmig d'una millor
de llistes enllaçades.

120
00:05:06,910 --> 00:05:09,560
Si utilitzeu l'encadenament,
encara té una llista enllaçada,

121
00:05:09,560 --> 00:05:13,170
el que significa que encara té la
Cerca causi un perjudici una llista enllaçada.

122
00:05:13,170 --> 00:05:18,390
Però com que vostè està prenent el seu lligats
llista i la seva divisió de més de 100 o 1000

123
00:05:18,390 --> 00:05:25,380
o n elements en la seva taula hash, ets
llistes enllaçades són tots u enèsim la mida.

124
00:05:25,380 --> 00:05:27,650
Tots són substancialment menor.

125
00:05:27,650 --> 00:05:32,080
Has n vinculats llistes vegada
d'una sola llista enllaçada de mida n.

126
00:05:32,080 --> 00:05:34,960
>> I pel que aquest món real constant
factor, que en general,

127
00:05:34,960 --> 00:05:39,730
no es parla de la complexitat temps,
no realment fer una diferència aquí.

128
00:05:39,730 --> 00:05:43,020
Així de recerca segueix sent lineal
buscar si vostè està utilitzant l'encadenament,

129
00:05:43,020 --> 00:05:46,780
però la longitud de la llista
Ets a la

130
00:05:46,780 --> 00:05:50,080
és molt, molt curt en comparació.

131
00:05:50,080 --> 00:05:52,995
De nou, si la classificació és la seva
objectiu aquí, taula hash de

132
00:05:52,995 --> 00:05:54,370
probablement no és el camí correcte a seguir.

133
00:05:54,370 --> 00:05:56,830
Només ha d'utilitzar una matriu si la classificació
és realment important per a vostè.

134
00:05:56,830 --> 00:05:58,590
>> I poden funcionar la gamma de mida.

135
00:05:58,590 --> 00:06:01,640
És difícil dir si un
taula hash és petit o gran,

136
00:06:01,640 --> 00:06:04,110
perquè realment depèn de
la mida de la seva taula hash és.

137
00:06:04,110 --> 00:06:07,340
Si només vas a emmagatzemar
cinc elements en la seva taula hash,

138
00:06:07,340 --> 00:06:10,620
i vostè té una taula hash
amb 10.000 elements en els mateixos,

139
00:06:10,620 --> 00:06:12,614
t'estàs perdent un munt d'espai.

140
00:06:12,614 --> 00:06:15,030
Contrast ser que també pots
té taules hash molt compactes,

141
00:06:15,030 --> 00:06:18,720
però el més petit de la seva taula hash es posa,
com més temps cadascuna d'aquestes llistes enllaçades

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

143
00:06:19,220 --> 00:06:22,607
I així, no hi ha realment cap manera de definir
exactament la mida d'una taula hash,

144
00:06:22,607 --> 00:06:24,440
però és probablement segur
dir que és en general

145
00:06:24,440 --> 00:06:27,990
serà més gran que una vinculada
Llista d'emmagatzematge de les mateixes dades,

146
00:06:27,990 --> 00:06:30,400
però més petit que un trie.

147
00:06:30,400 --> 00:06:32,720
>> I intents són la quarta
d'aquestes estructures

148
00:06:32,720 --> 00:06:34,070
que hem estat parlant.

149
00:06:34,070 --> 00:06:36,450
Inserció en un trie és complexa.

150
00:06:36,450 --> 00:06:38,400
Hi ha un munt de dinàmica
assignació de memòria,

151
00:06:38,400 --> 00:06:40,780
sobretot al principi,
com vas a començar a construir.

152
00:06:40,780 --> 00:06:43,700
Però és temps constant.

153
00:06:43,700 --> 00:06:47,690
No és més que l'element humà
aquí que fa que sigui difícil.

154
00:06:47,690 --> 00:06:53,250
Haver de trobar punter nul, malloc
espai, anar-hi, l'espai, possiblement malloc

155
00:06:53,250 --> 00:06:54,490
des d'allà de nou.

156
00:06:54,490 --> 00:06:58,880
El tipus de factor d'intimidació de
punters en l'assignació de memòria dinàmica

157
00:06:58,880 --> 00:07:00,130
és l'obstacle per esborrar.

158
00:07:00,130 --> 00:07:04,550
Però una vegada que hagi netejat ella, la inserció
en realitat ve molt simple,

159
00:07:04,550 --> 00:07:06,810
i sens dubte és la constant de temps.

160
00:07:06,810 --> 00:07:07,680
>> Supressió és fàcil.

161
00:07:07,680 --> 00:07:11,330
Tot el que necessites fer és navegar per una
parell de punters i connexió al node,

162
00:07:11,330 --> 00:07:12,420
així que això és bastant bo.

163
00:07:12,420 --> 00:07:13,930
Operacions de cerca també és bastant ràpid.

164
00:07:13,930 --> 00:07:16,780
Només es basa en la
longitud de les seves dades.

165
00:07:16,780 --> 00:07:19,924
Així que si totes les seves dades és
cinc cadenes de caràcters,

166
00:07:19,924 --> 00:07:22,590
per exemple, vostè està emmagatzemant de cinc
cadenes de caràcters en el trie,

167
00:07:22,590 --> 00:07:25,439
només es triga cinc passos per
trobar el que estàs buscant.

168
00:07:25,439 --> 00:07:28,480
El cinc és només un factor constant, de manera que
de nou, la inserció, eliminació i recerca

169
00:07:28,480 --> 00:07:31,670
aquí estan tots els temps constant, eficaç.

170
00:07:31,670 --> 00:07:34,880
>> Una altra cosa és que la seva trie és
en realitat una mica ja ordenats, oi?

171
00:07:34,880 --> 00:07:36,800
En virtut del que som
elements d'inserció,

172
00:07:36,800 --> 00:07:40,060
anant lletra per lletra del
clau, o dígit a dígit de la clau,

173
00:07:40,060 --> 00:07:45,084
normalment, la seva trie acaba sent
tipus de ordenats com el construeixes.

174
00:07:45,084 --> 00:07:47,250
En realitat no fa
sentit de pensar en la classificació

175
00:07:47,250 --> 00:07:49,874
de la mateixa manera en què pensem sobre
amb matrius o llistes enllaçades,

176
00:07:49,874 --> 00:07:51,070
o taules hash.

177
00:07:51,070 --> 00:07:54,780
Però en cert sentit, la seva
trie està ordenada a mesura que avança.

178
00:07:54,780 --> 00:07:58,630
>> El desavantatge, és clar, és que
1 trie es converteix ràpidament en enormes.

179
00:07:58,630 --> 00:08:02,970
Des de tots els punts d'unió, és possible que
tener-- si la seva clau consisteix en dígits,

180
00:08:02,970 --> 00:08:04,880
vostè té 10 una altra
llocs als quals poden anar, que

181
00:08:04,880 --> 00:08:07,490
vol dir que cada node
conté informació

182
00:08:07,490 --> 00:08:11,440
sobre les dades que desitja emmagatzemar
en aquest node, més 10 punts.

183
00:08:11,440 --> 00:08:14,430
La qual cosa, en CS50 IDE, és de 80 bytes.

184
00:08:14,430 --> 00:08:17,220
Així que és almenys 80 bytes per
cada node que es crea,

185
00:08:17,220 --> 00:08:19,240
i això sense comptar les dades.

186
00:08:19,240 --> 00:08:24,950
I si els seus nodes són
lletres en comptes de nombres,

187
00:08:24,950 --> 00:08:27,825
ara tens 26 punters
de cada lloc.

188
00:08:27,825 --> 00:08:32,007
I 26 vegades 8 és probablement 200
bytes, o alguna cosa així.

189
00:08:32,007 --> 00:08:33,840
I vostè té el capital
i vostè pot lowercase--

190
00:08:33,840 --> 00:08:35,381
veure on vaig amb això, oi?

191
00:08:35,381 --> 00:08:37,500
Els seus nodes poden aconseguir realment
gran, i pel que el trie

192
00:08:37,500 --> 00:08:40,470
sí, en general, pot
aconseguir realment gran, massa.

193
00:08:40,470 --> 00:08:42,630
Així que si l'espai és molt alta
prima en el sistema,

194
00:08:42,630 --> 00:08:45,830
1 trie vegada no sigui la manera correcta de
vagi, tot i que els seus altres beneficis

195
00:08:45,830 --> 00:08:47,780
entrar en joc.

196
00:08:47,780 --> 00:08:48,710
Sóc Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
Això és CS50.

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