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

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Quindi, in CS50, abbiamo coperto
un sacco di strutture di dati diversi,

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

4
00:00:09,180 --> 00:00:11,420
Abbiamo visto gli array, e legati
elenchi e tabelle hash,

5
00:00:11,420 --> 00:00:15,210
e cerca, pile e code.

6
00:00:15,210 --> 00:00:17,579
Impareremo anche un po '
su alberi e mucchi,

7
00:00:17,579 --> 00:00:20,120
ma in realtà tutti questi solo fine
per essere variazioni sul tema.

8
00:00:20,120 --> 00:00:22,840
Ci sono davvero questi
tipo di quattro idee di base

9
00:00:22,840 --> 00:00:25,190
che tutto il resto può ridursi a.

10
00:00:25,190 --> 00:00:28,150
Array, liste concatenate,
tabelle hash, e cerca.

11
00:00:28,150 --> 00:00:30,720
E come ho detto, ci
sono variazioni su di loro,

12
00:00:30,720 --> 00:00:32,720
ma questo è abbastanza
tanto andare a riassumere

13
00:00:32,720 --> 00:00:38,140
tutto quello che stiamo andando a parlare
circa in questa classe, in termini di C.

14
00:00:38,140 --> 00:00:40,140
>> Ma come fanno questi ogni misura, giusto?

15
00:00:40,140 --> 00:00:44,265
Abbiamo parlato i pro ei contro
di ciascuno in video separati su di loro,

16
00:00:44,265 --> 00:00:46,390
ma c'è un sacco di numeri
ottenere gettato intorno.

17
00:00:46,390 --> 00:00:48,723
C'è un sacco di generale
pensieri sempre gettati in giro.

18
00:00:48,723 --> 00:00:51,950
Cerchiamo di consolidare
in un solo posto.

19
00:00:51,950 --> 00:00:55,507
Facciamo pesare i pro contro
i contro, e prendere in considerazione

20
00:00:55,507 --> 00:00:57,340
quale struttura dati
potrebbe essere il giusto dati

21
00:00:57,340 --> 00:01:01,440
Struttura per la vostra situazione particolare,
qualunque tipo di dati si sta memorizzazione.

22
00:01:01,440 --> 00:01:06,625
Non è necessariamente sempre bisogno di
utilizzare l'inserimento super veloce, la cancellazione,

23
00:01:06,625 --> 00:01:10,761
e ricerca di un trie se davvero
non si preoccupano di inserimento e cancellazione

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

25
00:01:11,260 --> 00:01:13,968
Se avete bisogno di appena rapidamente casuale
accesso, forse un array è meglio.

26
00:01:13,968 --> 00:01:15,340
Quindi cerchiamo di distillare tale.

27
00:01:15,340 --> 00:01:18,530
Parliamo di ciascuno dei quattro
principali tipi di strutture di dati

28
00:01:18,530 --> 00:01:21,720
che abbiamo parlato, e
basta vedere quando potrebbe essere buono,

29
00:01:21,720 --> 00:01:23,340
e quando potrebbero non essere così buono.

30
00:01:23,340 --> 00:01:24,610
Quindi partiamo con gli array.

31
00:01:24,610 --> 00:01:27,300
Così l'inserimento, che una specie di male.

32
00:01:27,300 --> 00:01:31,350
>> Inserimento alla fine di un array è OK,
se stiamo costruendo una matrice come andiamo.

33
00:01:31,350 --> 00:01:33,570
Ma se abbiamo bisogno di inserire
elementi nel mezzo,

34
00:01:33,570 --> 00:01:35,550
ripensare a inserimento
tipo, c'è un sacco

35
00:01:35,550 --> 00:01:37,510
di spostare a montare un elemento in là.

36
00:01:37,510 --> 00:01:41,170
E così, se abbiamo intenzione di inserire
ovunque ma la fine di una matrice,

37
00:01:41,170 --> 00:01:43,590
che probabilmente non è così grande.

38
00:01:43,590 --> 00:01:46,710
>> Allo stesso modo, la cancellazione, a meno che non siamo
eliminazione dalla fine di una matrice,

39
00:01:46,710 --> 00:01:49,810
è probabilmente non è così grande, se
non vogliamo lasciare fessure vuote,

40
00:01:49,810 --> 00:01:50,790
che di solito non lo facciamo.

41
00:01:50,790 --> 00:01:54,700
Vogliamo rimuovere un elemento, e
poi sorta di renderlo aderente di nuovo.

42
00:01:54,700 --> 00:01:57,670
E così l'eliminazione di elementi da
un array, anche non così grande.

43
00:01:57,670 --> 00:01:58,820
>> Consultazione, tuttavia, è grande.

44
00:01:58,820 --> 00:02:00,920
Abbiamo accesso casuale,
ricerca costante di tempo.

45
00:02:00,920 --> 00:02:03,800
Diciamo solo sette, e andiamo
a matrice di delocalizzazione sette.

46
00:02:03,800 --> 00:02:05,907
Diciamo 20, all'appuntamento per
array di trasferimento 20.

47
00:02:05,907 --> 00:02:07,240
Non abbiamo per scorrere attraverso.

48
00:02:07,240 --> 00:02:08,630
Questo è abbastanza buono.

49
00:02:08,630 --> 00:02:11,020
>> Gli array sono anche relativamente facile da ordinare.

50
00:02:11,020 --> 00:02:14,040
Ogni volta che abbiamo parlato di un ordinamento
algoritmo, come la selezione tipo,

51
00:02:14,040 --> 00:02:18,820
insertion sort, bubble sort, merge
specie, abbiamo sempre usato le matrici di farlo,

52
00:02:18,820 --> 00:02:21,860
perché gli array sono abbastanza facili da
tipo, rispetto alle strutture di dati

53
00:02:21,860 --> 00:02:22,970
che abbiamo visto finora.

54
00:02:22,970 --> 00:02:24,320
>> Sono anche relativamente piccolo.

55
00:02:24,320 --> 00:02:25,695
Non c'è un sacco di spazio in più.

56
00:02:25,695 --> 00:02:29,210
Devi solo mettere da parte esattamente quanto
come è necessario per tenere i vostri dati,

57
00:02:29,210 --> 00:02:30,320
e che è praticamente.

58
00:02:30,320 --> 00:02:33,180
Quindi sono piuttosto piccole
ed efficiente in questo modo.

59
00:02:33,180 --> 00:02:36,000
Ma un altro aspetto negativo, però,
è che essi hanno una dimensione fissa.

60
00:02:36,000 --> 00:02:38,630
Dobbiamo dichiarare esattamente come
grande vogliamo la nostra gamma di essere,

61
00:02:38,630 --> 00:02:39,940
e abbiamo solo un colpo a questo.

62
00:02:39,940 --> 00:02:41,280
Non possiamo crescere e ridurla.

63
00:02:41,280 --> 00:02:44,582
>> Se abbiamo bisogno di crescere o restringersi, noi
hanno bisogno di dichiarare un nuovo array,

64
00:02:44,582 --> 00:02:47,750
copiare tutti gli elementi del
primo array nella seconda matrice.

65
00:02:47,750 --> 00:02:51,410
E se noi calcolato male che
tempo, abbiamo bisogno di farlo di nuovo.

66
00:02:51,410 --> 00:02:52,760
Non così grande.

67
00:02:52,760 --> 00:02:58,750
Quindi gli array non ci danno la flessibilità
di avere un numero variabile di elementi.

68
00:02:58,750 --> 00:03:01,320
>> Con una lista collegata,
inserimento è abbastanza facile.

69
00:03:01,320 --> 00:03:03,290
Siamo appiccicare semplicemente le anteriore.

70
00:03:03,290 --> 00:03:04,892
La cancellazione è anche abbastanza facile.

71
00:03:04,892 --> 00:03:06,100
Dobbiamo trovare gli elementi.

72
00:03:06,100 --> 00:03:07,270
Che coinvolgono qualche ricerca.

73
00:03:07,270 --> 00:03:10,270
>> Ma una volta che hai trovato l'elemento
che stai cercando, tutto quello che dovete fare

74
00:03:10,270 --> 00:03:12,830
è cambiare un puntatore,
forse due se avete

75
00:03:12,830 --> 00:03:15,151
un legato list-- un doppiamente
lista collegata, rather--

76
00:03:15,151 --> 00:03:16,650
e allora si può solo liberare il nodo.

77
00:03:16,650 --> 00:03:18,399
Non è necessario spostare
tutto intorno.

78
00:03:18,399 --> 00:03:22,090
Basta cambiare due puntatori,
così che è piuttosto veloce.

79
00:03:22,090 --> 00:03:23,470
>> Ricerca è male però, no?

80
00:03:23,470 --> 00:03:26,280
Al fine per noi trovare un
elemento in una lista collegata,

81
00:03:26,280 --> 00:03:29,154
se singolarmente o doppiamente collegata,
dobbiamo lineare cercarlo.

82
00:03:29,154 --> 00:03:32,320
Dobbiamo cominciare all'inizio e
spostare l'estremità, o iniziare alla fine mossa

83
00:03:32,320 --> 00:03:33,860
all'inizio.

84
00:03:33,860 --> 00:03:35,474
Noi non abbiamo più accesso casuale.

85
00:03:35,474 --> 00:03:37,265
Quindi, se stiamo facendo un
sacco di ricerca, forse

86
00:03:37,265 --> 00:03:39,830
una lista collegata non è
abbastanza così buono per noi.

87
00:03:39,830 --> 00:03:43,750
>> Sono anche molto
difficile da risolvere, giusto?

88
00:03:43,750 --> 00:03:45,666
L'unico modo è possibile
davvero ordinare una lista concatenata

89
00:03:45,666 --> 00:03:47,870
è quello di ordinare come si costruisce esso.

90
00:03:47,870 --> 00:03:50,497
Ma se si ordina come si
costruirlo, non sei più

91
00:03:50,497 --> 00:03:51,830
rendendo più inserimenti rapidi.

92
00:03:51,830 --> 00:03:53,746
Tu non sei solo virata
le cose sulla parte anteriore.

93
00:03:53,746 --> 00:03:55,710
Devi trovare il
posto giusto per metterlo,

94
00:03:55,710 --> 00:03:57,820
e poi la vostra inserzione
diventa quasi come cattivo

95
00:03:57,820 --> 00:03:59,390
come l'inserimento in una matrice.

96
00:03:59,390 --> 00:04:03,130
Quindi liste concatenate non sono
così grande per ordinare i dati.

97
00:04:03,130 --> 00:04:05,830
>> Sono anche piuttosto piccolo, formato-saggio.

98
00:04:05,830 --> 00:04:08,496
Doppiamente concatenata po 'elenco
più grande di liste concatenate semplici,

99
00:04:08,496 --> 00:04:10,620
che sono leggermente più grandi
di array, ma non è

100
00:04:10,620 --> 00:04:13,330
una grande quantità di spazio sprecato.

101
00:04:13,330 --> 00:04:18,730
Quindi, se lo spazio è ad un premio, ma
Non un premio davvero intenso,

102
00:04:18,730 --> 00:04:22,180
questa potrebbe essere la strada giusta da percorrere.

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

104
00:04:23,330 --> 00:04:25,850
Inserimento in una tabella hash
è abbastanza semplice.

105
00:04:25,850 --> 00:04:26,980
Si tratta di un processo in due fasi.

106
00:04:26,980 --> 00:04:30,700
In primo luogo abbiamo bisogno di eseguire i nostri dati attraverso
una funzione di hash per ottenere un codice hash,

107
00:04:30,700 --> 00:04:37,550
e poi inseriamo l'elemento nella
tabella hash in quella posizione codice hash.

108
00:04:37,550 --> 00:04:40,879
>> La cancellazione, simile alla lista collegata,
è facile una volta trovato l'elemento.

109
00:04:40,879 --> 00:04:43,170
Devi trovare per primo,
ma poi quando lo si elimina,

110
00:04:43,170 --> 00:04:45,128
basta scambiare
una coppia di puntatori,

111
00:04:45,128 --> 00:04:47,250
se si sta utilizzando concatenazioni separate.

112
00:04:47,250 --> 00:04:49,942
Se stai usando sondare,
o se non siete

113
00:04:49,942 --> 00:04:51,650
utilizzando concatenamento a tutti
nella tabella di hash,

114
00:04:51,650 --> 00:04:53,040
l'eliminazione è in realtà molto semplice.

115
00:04:53,040 --> 00:04:57,134
Tutto quello che dovete fare è il hash
i dati, e poi andare a quella posizione.

116
00:04:57,134 --> 00:04:58,925
E a patto che non lo fai
avere collisioni,

117
00:04:58,925 --> 00:05:01,650
sarete in grado di eliminare rapidamente.

118
00:05:01,650 --> 00:05:04,930
>> Ora, di ricerca è dove le cose
ottenere un po 'più complicato.

119
00:05:04,930 --> 00:05:06,910
E 'in media meglio
di liste concatenate.

120
00:05:06,910 --> 00:05:09,560
Se stai usando concatenazioni,
avete ancora una lista collegata,

121
00:05:09,560 --> 00:05:13,170
il che significa che avete ancora la
Ricerca detrimento una lista collegata.

122
00:05:13,170 --> 00:05:18,390
Ma perché si sta prendendo la tua collegati
lista e dividendolo oltre 100 o 1000

123
00:05:18,390 --> 00:05:25,380
o n elementi nella vostra tabella di hash, sei
liste collegate sono tutte ennesimo le dimensioni.

124
00:05:25,380 --> 00:05:27,650
Sono tutti sostanzialmente più piccolo.

125
00:05:27,650 --> 00:05:32,080
Hai n collegato liste invece
di una lista collegata di dimensione n.

126
00:05:32,080 --> 00:05:34,960
>> E così questo mondo reale costante
fattore, che generalmente

127
00:05:34,960 --> 00:05:39,730
non si parla di complessità tempo,
realtà non fare la differenza qui.

128
00:05:39,730 --> 00:05:43,020
Quindi ricerca è ancora lineare
cercare se si sta usando concatenazioni,

129
00:05:43,020 --> 00:05:46,780
ma la lunghezza della lista
si sta cercando attraverso

130
00:05:46,780 --> 00:05:50,080
è molto, molto breve in confronto.

131
00:05:50,080 --> 00:05:52,995
Anche in questo caso, se l'ordinamento è il vostro
obiettivo qui, hash tabella di

132
00:05:52,995 --> 00:05:54,370
probabilmente non è il modo giusto per andare.

133
00:05:54,370 --> 00:05:56,830
Basta usare un array se l'ordinamento
è veramente importante per voi.

134
00:05:56,830 --> 00:05:58,590
>> E possono eseguire la gamma di dimensioni.

135
00:05:58,590 --> 00:06:01,640
E 'difficile dire se un
tabella hash è piccolo o grande,

136
00:06:01,640 --> 00:06:04,110
perché in realtà dipende
quanto è grande la vostra tabella di hash è.

137
00:06:04,110 --> 00:06:07,340
Se avete intenzione solo di essere l'archiviazione
cinque elementi nella vostra tabella hash,

138
00:06:07,340 --> 00:06:10,620
e si dispone di una tabella di hash
con 10.000 elementi in esso,

139
00:06:10,620 --> 00:06:12,614
probabilmente stai sprecando un sacco di spazio.

140
00:06:12,614 --> 00:06:15,030
Contrasto si possono anche essere
avere tabelle hash molto compatte,

141
00:06:15,030 --> 00:06:18,720
ma il più piccolo la tua tabella hash ottiene,
il più lungo ciascuna di tali liste collegate

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

143
00:06:19,220 --> 00:06:22,607
E così non c'è davvero nessun modo per definire
esattamente la dimensione di una tabella hash,

144
00:06:22,607 --> 00:06:24,440
ma è probabilmente sicuro
dire che è generalmente

145
00:06:24,440 --> 00:06:27,990
sta per essere più grande di un collegato
Lista memorizzare gli stessi dati,

146
00:06:27,990 --> 00:06:30,400
ma più piccolo di un trie.

147
00:06:30,400 --> 00:06:32,720
>> E tentativi sono la quarta
di queste strutture

148
00:06:32,720 --> 00:06:34,070
che stiamo parlando.

149
00:06:34,070 --> 00:06:36,450
Inserimento in un trie è complessa.

150
00:06:36,450 --> 00:06:38,400
C'è un sacco di dinamica
allocazione della memoria,

151
00:06:38,400 --> 00:06:40,780
soprattutto all'inizio,
come si sta iniziando a costruire.

152
00:06:40,780 --> 00:06:43,700
Ma è tempo costante.

153
00:06:43,700 --> 00:06:47,690
E 'solo l'elemento umano
qui che lo rende difficile.

154
00:06:47,690 --> 00:06:53,250
Dover incontrare puntatore nullo, malloc
spazio, andare lì, lo spazio forse malloc

155
00:06:53,250 --> 00:06:54,490
da lì di nuovo.

156
00:06:54,490 --> 00:06:58,880
Il tipo di fattore di intimidazione di
puntatori in allocazione dinamica della memoria

157
00:06:58,880 --> 00:07:00,130
è l'ostacolo per cancellare.

158
00:07:00,130 --> 00:07:04,550
Ma una volta che hai eliminato esso, l'inserimento
in realtà arriva abbastanza semplice,

159
00:07:04,550 --> 00:07:06,810
e certamente è un tempo costante.

160
00:07:06,810 --> 00:07:07,680
>> La cancellazione è facile.

161
00:07:07,680 --> 00:07:11,330
Tutto quello che dovete fare è navigare lungo una
paio di puntatori e la connessione al nodo,

162
00:07:11,330 --> 00:07:12,420
così che è abbastanza buono.

163
00:07:12,420 --> 00:07:13,930
Lookup è anche abbastanza veloce.

164
00:07:13,930 --> 00:07:16,780
Si basa unicamente sulla
lunghezza dei vostri dati.

165
00:07:16,780 --> 00:07:19,924
Quindi, se tutti i dati sono
cinque stringhe di caratteri,

166
00:07:19,924 --> 00:07:22,590
per esempio, si sta memorizzare cinque
stringhe di caratteri nel trie,

167
00:07:22,590 --> 00:07:25,439
ci vogliono solo cinque passi per
trovare quello che stai cercando.

168
00:07:25,439 --> 00:07:28,480
Cinque è solo un fattore costante, così
ancora una volta, l'inserimento, la cancellazione, e ricerca

169
00:07:28,480 --> 00:07:31,670
qui ci sono tutti i tempi costanti, in modo efficace.

170
00:07:31,670 --> 00:07:34,880
>> Un'altra cosa è che il vostro è trie
in realtà tipo di già ordinato, giusto?

171
00:07:34,880 --> 00:07:36,800
In virtù di quanto siamo
inserire elementi,

172
00:07:36,800 --> 00:07:40,060
andando lettera per lettera del
chiave, o cifra per cifra della chiave,

173
00:07:40,060 --> 00:07:45,084
In genere, il trie finisce per essere
tipo di ordinati come si costruisce.

174
00:07:45,084 --> 00:07:47,250
Non fa davvero
senso di pensare di smistamento

175
00:07:47,250 --> 00:07:49,874
nello stesso modo in cui pensiamo
con gli array, o liste collegate,

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

177
00:07:51,070 --> 00:07:54,780
Ma in un certo senso, il vostro
trie è ordinato, come si va.

178
00:07:54,780 --> 00:07:58,630
>> Il rovescio della medaglia, naturalmente, è che
un trie diventa rapidamente enorme.

179
00:07:58,630 --> 00:08:02,970
Da ogni punto di congiunzione, si potrebbe
have-- se la tua chiave è costituito da cifre,

180
00:08:02,970 --> 00:08:04,880
avete altri 10
luoghi che si può andare, che

181
00:08:04,880 --> 00:08:07,490
significa che ogni nodo
contiene informazioni

182
00:08:07,490 --> 00:08:11,440
sui dati che si desidera memorizzare
a quel nodo, più 10 puntatori.

183
00:08:11,440 --> 00:08:14,430
Il che, in CS50 IDE, è di 80 byte.

184
00:08:14,430 --> 00:08:17,220
Quindi è di almeno 80 byte per
ogni nodo che si crea,

185
00:08:17,220 --> 00:08:19,240
e che non è nemmeno contare i dati.

186
00:08:19,240 --> 00:08:24,950
E se i nodi sono
lettere invece di cifre,

187
00:08:24,950 --> 00:08:27,825
ora avete 26 puntatori
da ogni posizione.

188
00:08:27,825 --> 00:08:32,007
E 26 volte 8 è probabilmente 200
byte, o qualcosa del genere.

189
00:08:32,007 --> 00:08:33,840
E tu hai capitale
e si può lowercase--

190
00:08:33,840 --> 00:08:35,381
vedere dove sto andando con questo, giusto?

191
00:08:35,381 --> 00:08:37,500
I nodi possono ottenere davvero
grande, e così il trie

192
00:08:37,500 --> 00:08:40,470
stesso, nel complesso, può
ottenere veramente grande, troppo.

193
00:08:40,470 --> 00:08:42,630
Quindi, se lo spazio è molto elevata
premio sul proprio sistema,

194
00:08:42,630 --> 00:08:45,830
un trie potrebbe non essere il modo giusto per
andare, anche se i suoi altri benefici

195
00:08:45,830 --> 00:08:47,780
entrare in gioco.

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

197
00:08:48,710 --> 00:08:50,740
Questo è CS50.

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