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

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Então, em CS50, nós cobrimos
um grande número de diferentes estruturas de dados,

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

4
00:00:09,180 --> 00:00:11,420
Nós vimos arrays, e ligados
listas e tabelas de hash,

5
00:00:11,420 --> 00:00:15,210
e tenta, pilhas e filas.

6
00:00:15,210 --> 00:00:17,579
Também vamos aprender um pouco
sobre árvores e montes,

7
00:00:17,579 --> 00:00:20,120
mas realmente todos estes acabar
sendo variações sobre um tema.

8
00:00:20,120 --> 00:00:22,840
Há realmente estes
tipo de quatro idéias básicas

9
00:00:22,840 --> 00:00:25,190
que tudo o resto pode ferver para baixo.

10
00:00:25,190 --> 00:00:28,150
Arrays, listas ligadas,
tabelas de hash, e tenta.

11
00:00:28,150 --> 00:00:30,720
E como eu disse, há
são variações sobre eles,

12
00:00:30,720 --> 00:00:32,720
mas isso é muito
muito indo para resumir

13
00:00:32,720 --> 00:00:38,140
tudo o que vai falar
Sobre nesta classe em termos de C.

14
00:00:38,140 --> 00:00:40,140
>> Mas como estes todos medida, certo?

15
00:00:40,140 --> 00:00:44,265
Nós conversamos sobre os prós e contras
de cada um em vídeos separados sobre eles,

16
00:00:44,265 --> 00:00:46,390
mas há um monte de números
sendo jogado em torno.

17
00:00:46,390 --> 00:00:48,723
Há um monte de geral
pensamentos ser jogado ao redor.

18
00:00:48,723 --> 00:00:51,950
Vamos tentar e consolidar
-lo em apenas um lugar.

19
00:00:51,950 --> 00:00:55,507
Vamos pesar os prós contra
os contras, e considere

20
00:00:55,507 --> 00:00:57,340
qual a estrutura de dados
pode ser a dados direita

21
00:00:57,340 --> 00:01:01,440
estrutura para sua situação particular,
qualquer tipo de dados que você está armazenando.

22
00:01:01,440 --> 00:01:06,625
Você não necessariamente precisa sempre
usar o super rápida inserção, eliminação,

23
00:01:06,625 --> 00:01:10,761
e pesquisa de uma trie se você realmente
não se preocupam com inserir e excluir

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

25
00:01:11,260 --> 00:01:13,968
Se você precisa apenas rapidamente aleatória
acesso, talvez uma matriz é melhor.

26
00:01:13,968 --> 00:01:15,340
Então, vamos destilar isso.

27
00:01:15,340 --> 00:01:18,530
Vamos falar sobre cada um dos quatro
principais tipos de estruturas de dados

28
00:01:18,530 --> 00:01:21,720
que nós já conversamos sobre, e
basta ver quando eles pode ser bom,

29
00:01:21,720 --> 00:01:23,340
e quando eles podem não ser tão bom.

30
00:01:23,340 --> 00:01:24,610
Então vamos começar com matrizes.

31
00:01:24,610 --> 00:01:27,300
Então inserção, que é tipo de ruim.

32
00:01:27,300 --> 00:01:31,350
>> A inserção na extremidade de uma matriz é OK,
se nós estamos construindo uma matriz como vamos nós.

33
00:01:31,350 --> 00:01:33,570
Mas se nós precisarmos inserir
elementos no meio,

34
00:01:33,570 --> 00:01:35,550
acho que volta para inserção
tipo, há muito

35
00:01:35,550 --> 00:01:37,510
de deslocamento para ajustar um elemento em lá.

36
00:01:37,510 --> 00:01:41,170
E por isso, se nós estamos indo para inserir
qualquer lugar, mas no final de uma matriz,

37
00:01:41,170 --> 00:01:43,590
que provavelmente não é tão grande.

38
00:01:43,590 --> 00:01:46,710
>> Da mesma forma, a exclusão, a menos que sejamos
exclusão a partir da extremidade de uma matriz,

39
00:01:46,710 --> 00:01:49,810
é, provavelmente, também não tão grande se
nós não queremos deixar lacunas vazias,

40
00:01:49,810 --> 00:01:50,790
que normalmente nós não.

41
00:01:50,790 --> 00:01:54,700
Queremos remover um elemento, e
em seguida, tipo de torná-lo confortável novamente.

42
00:01:54,700 --> 00:01:57,670
E assim a exclusão de elementos
uma matriz, também não tão grande.

43
00:01:57,670 --> 00:01:58,820
>> Lookup, porém, é grande.

44
00:01:58,820 --> 00:02:00,920
Temos de acesso aleatório,
pesquisa de tempo constante.

45
00:02:00,920 --> 00:02:03,800
Nós apenas dizer sete, e nós vamos
a matriz deslocalização sete.

46
00:02:03,800 --> 00:02:05,907
Dizemos 20, com a go
matriz deslocalização 20.

47
00:02:05,907 --> 00:02:07,240
Não temos para percorrer transversalmente.

48
00:02:07,240 --> 00:02:08,630
Isso é muito bom.

49
00:02:08,630 --> 00:02:11,020
>> Arrays também são relativamente fáceis de classificar.

50
00:02:11,020 --> 00:02:14,040
Cada vez que falamos sobre uma triagem
algoritmo, tais como seleção de tipo,

51
00:02:14,040 --> 00:02:18,820
tipo de inserção, bubble sort, merge
tipo, nós sempre utilizado matrizes para fazê-lo,

52
00:02:18,820 --> 00:02:21,860
porque as matrizes são bastante fáceis de
tipo, em relação às estruturas de dados

53
00:02:21,860 --> 00:02:22,970
temos visto até agora.

54
00:02:22,970 --> 00:02:24,320
>> Eles também são relativamente pequeno.

55
00:02:24,320 --> 00:02:25,695
Não há um monte de espaço extra.

56
00:02:25,695 --> 00:02:29,210
Você só anular exatamente tanto
como você precisa para armazenar seus dados,

57
00:02:29,210 --> 00:02:30,320
e isso é muito bonito isso.

58
00:02:30,320 --> 00:02:33,180
Então eles são muito pequenos
e eficiente desta maneira.

59
00:02:33,180 --> 00:02:36,000
Mas uma outra desvantagem, no entanto,
é que eles são de tamanho fixo.

60
00:02:36,000 --> 00:02:38,630
Temos de declarar exatamente como
grande queremos que a nossa matriz para ser,

61
00:02:38,630 --> 00:02:39,940
e nós só temos uma chance.

62
00:02:39,940 --> 00:02:41,280
Nós não podemos crescer e reduzi-lo.

63
00:02:41,280 --> 00:02:44,582
>> Se precisamos crescer ou encolher-lo, nós
precisa declarar uma matriz inteiramente novo,

64
00:02:44,582 --> 00:02:47,750
copiar todos os elementos do
primeira matriz para a segunda matriz.

65
00:02:47,750 --> 00:02:51,410
E se calculou mal que
tempo, temos de fazê-lo novamente.

66
00:02:51,410 --> 00:02:52,760
Não é tão boa.

67
00:02:52,760 --> 00:02:58,750
Então matrizes não nos dão a flexibilidade
ter número variável de elementos.

68
00:02:58,750 --> 00:03:01,320
>> Com uma lista ligada,
inserção é muito fácil.

69
00:03:01,320 --> 00:03:03,290
Nós apenas alinhavar para a frente.

70
00:03:03,290 --> 00:03:04,892
Eliminação também é muito fácil.

71
00:03:04,892 --> 00:03:06,100
Temos que encontrar os elementos.

72
00:03:06,100 --> 00:03:07,270
Que envolvem alguma pesquisa.

73
00:03:07,270 --> 00:03:10,270
>> Mas uma vez que você tenha encontrado o elemento
você está procurando, tudo que você precisa fazer

74
00:03:10,270 --> 00:03:12,830
é alterar um ponteiro,
possivelmente dois, se você tem

75
00:03:12,830 --> 00:03:15,151
uma ligada lista-- um duplamente
lista ligada, rather--

76
00:03:15,151 --> 00:03:16,650
e então você pode apenas liberar o nó.

77
00:03:16,650 --> 00:03:18,399
Você não tem que mudar
tudo ao seu redor.

78
00:03:18,399 --> 00:03:22,090
Você acabou de mudar dois ponteiros,
de modo que é muito rápido.

79
00:03:22,090 --> 00:03:23,470
>> Lookup é ruim, certo?

80
00:03:23,470 --> 00:03:26,280
A fim para nós encontrar um
elemento em uma lista ligada,

81
00:03:26,280 --> 00:03:29,154
isoladamente ou duplamente ligado,
temos a linear busca-lo.

82
00:03:29,154 --> 00:03:32,320
Temos que começar no início e
mova o fim, ou começar no final do movimento

83
00:03:32,320 --> 00:03:33,860
para o início.

84
00:03:33,860 --> 00:03:35,474
Não temos acesso aleatório mais.

85
00:03:35,474 --> 00:03:37,265
Então, se estamos fazendo um
muita pesquisa, talvez

86
00:03:37,265 --> 00:03:39,830
uma lista ligada não é
tão bom para nós.

87
00:03:39,830 --> 00:03:43,750
>> Eles também são realmente
difícil de resolver, certo?

88
00:03:43,750 --> 00:03:45,666
A única maneira que você puder
realmente classificar uma lista ligada

89
00:03:45,666 --> 00:03:47,870
é para classificá-lo como você construí-lo.

90
00:03:47,870 --> 00:03:50,497
Mas se você classificá-lo como você
construí-lo, você não é mais

91
00:03:50,497 --> 00:03:51,830
fazendo inserções rápidas anymore.

92
00:03:51,830 --> 00:03:53,746
Você não está apenas alinhavando
as coisas para a frente.

93
00:03:53,746 --> 00:03:55,710
Você tem que encontrar o
ponto certo para colocá-lo,

94
00:03:55,710 --> 00:03:57,820
e, em seguida, a sua inserção
torna-se quase tão ruim

95
00:03:57,820 --> 00:03:59,390
como a inserção em uma matriz.

96
00:03:59,390 --> 00:04:03,130
Então listas ligadas não são
tão grande para classificar os dados.

97
00:04:03,130 --> 00:04:05,830
>> Eles também são bastante pequeno, tamanho-wise.

98
00:04:05,830 --> 00:04:08,496
Duplamente lista ligada ligeiramente
maior do que isoladamente listas ligadas,

99
00:04:08,496 --> 00:04:10,620
que são ligeiramente maiores
de matrizes, mas não é

100
00:04:10,620 --> 00:04:13,330
uma enorme quantidade de espaço desperdiçado.

101
00:04:13,330 --> 00:04:18,730
Portanto, se o espaço é um prêmio, mas
não um prêmio muito intenso,

102
00:04:18,730 --> 00:04:22,180
este pode ser o caminho certo a seguir.

103
00:04:22,180 --> 00:04:23,330
>> As tabelas de hash.

104
00:04:23,330 --> 00:04:25,850
Inserção em uma tabela hash
é bastante simples.

105
00:04:25,850 --> 00:04:26,980
É um processo de duas etapas.

106
00:04:26,980 --> 00:04:30,700
Primeiro, precisamos executar nossas informações através
uma função hash para obter um código de hash,

107
00:04:30,700 --> 00:04:37,550
e, depois, insira o elemento para o
tabela hash naquele local do código hash.

108
00:04:37,550 --> 00:04:40,879
>> Eliminação, semelhante a lista ligada,
é fácil uma vez que você encontrar o elemento.

109
00:04:40,879 --> 00:04:43,170
Você tem que encontrá-lo primeiro,
mas, em seguida, quando você excluí-lo,

110
00:04:43,170 --> 00:04:45,128
você só precisa trocar
um par de ponteiros,

111
00:04:45,128 --> 00:04:47,250
se você estiver usando o encadeamento separado.

112
00:04:47,250 --> 00:04:49,942
Se você estiver usando sondagem,
ou se você não estiver

113
00:04:49,942 --> 00:04:51,650
usando encadeamento em tudo
em sua tabela de hash,

114
00:04:51,650 --> 00:04:53,040
eliminação é realmente muito fácil.

115
00:04:53,040 --> 00:04:57,134
Tudo que você precisa fazer é botar o
dados, e em seguida, ir para esse local.

116
00:04:57,134 --> 00:04:58,925
E supondo que você não fazer
tem nenhum colisões,

117
00:04:58,925 --> 00:05:01,650
você vai ser capaz de apagar muito rapidamente.

118
00:05:01,650 --> 00:05:04,930
>> Agora, a pesquisa é onde as coisas
ficar um pouco mais complicado.

119
00:05:04,930 --> 00:05:06,910
Está na melhor média
de listas ligadas.

120
00:05:06,910 --> 00:05:09,560
Se você estiver usando o encadeamento,
você ainda tem uma lista ligada,

121
00:05:09,560 --> 00:05:13,170
o que significa que você ainda tem a
Pesquisa detrimento uma lista ligada.

122
00:05:13,170 --> 00:05:18,390
Mas porque você está tomando seu ligada
lista e dividi-lo mais de 100 ou 1000

123
00:05:18,390 --> 00:05:25,380
ou n elementos em sua tabela de hash, você é
listas ligadas são todos um enésimo o tamanho.

124
00:05:25,380 --> 00:05:27,650
Eles são todos substancialmente menor.

125
00:05:27,650 --> 00:05:32,080
Você listas n ligada ao invés
de uma lista ligada de tamanho n.

126
00:05:32,080 --> 00:05:34,960
>> E assim, este mundo real constante
fator, que geralmente

127
00:05:34,960 --> 00:05:39,730
não falar sobre a complexidade em tempo,
faz realmente fazer a diferença aqui.

128
00:05:39,730 --> 00:05:43,020
Assim pesquisa ainda é linear
procurar se você estiver usando o encadeamento,

129
00:05:43,020 --> 00:05:46,780
mas o comprimento da lista
Você está vendo a

130
00:05:46,780 --> 00:05:50,080
é muito, muito curto, por comparação.

131
00:05:50,080 --> 00:05:52,995
Novamente, se a classificação é a sua
objetivo aqui, hash de tabela de

132
00:05:52,995 --> 00:05:54,370
provavelmente não é o caminho certo a seguir.

133
00:05:54,370 --> 00:05:56,830
Basta usar uma matriz se classificar
é realmente importante para você.

134
00:05:56,830 --> 00:05:58,590
>> E eles podem executar a gama de tamanho.

135
00:05:58,590 --> 00:06:01,640
É difícil dizer se uma
tabela hash é pequeno ou grande,

136
00:06:01,640 --> 00:06:04,110
porque ele realmente depende de
como grande sua tabela hash é.

137
00:06:04,110 --> 00:06:07,340
Se você está indo só para estar armazenando
cinco elementos em sua tabela hash,

138
00:06:07,340 --> 00:06:10,620
e você tem uma tabela hash
com 10.000 elementos nele,

139
00:06:10,620 --> 00:06:12,614
provavelmente você está desperdiçando uma grande quantidade de espaço.

140
00:06:12,614 --> 00:06:15,030
Contraste sendo você também pode
tem tabelas de hash muito compactas,

141
00:06:15,030 --> 00:06:18,720
mas o menor sua tabela hash fica,
quanto mais cada uma dessas listas ligadas

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

143
00:06:19,220 --> 00:06:22,607
E assim não há realmente nenhuma maneira de definir
exactamente o tamanho de uma tabela hash,

144
00:06:22,607 --> 00:06:24,440
mas é provavelmente seguro
dizer que é geralmente

145
00:06:24,440 --> 00:06:27,990
vai ser maior do que um ligado
lista armazenar os mesmos dados,

146
00:06:27,990 --> 00:06:30,400
mas menor do que um trie.

147
00:06:30,400 --> 00:06:32,720
>> E tentativas são a quarta
destas estruturas

148
00:06:32,720 --> 00:06:34,070
que temos vindo a falar.

149
00:06:34,070 --> 00:06:36,450
A inserção numa trie é complexo.

150
00:06:36,450 --> 00:06:38,400
Há um monte de dinâmica
alocação de memória,

151
00:06:38,400 --> 00:06:40,780
especialmente no início,
como você está começando a construir.

152
00:06:40,780 --> 00:06:43,700
Mas é tempo constante.

153
00:06:43,700 --> 00:06:47,690
É apenas o elemento humano
aqui que faz com que seja complicado.

154
00:06:47,690 --> 00:06:53,250
Ter de encontrar ponteiro nulo, malloc
espaço, ir lá, o espaço possivelmente malloc

155
00:06:53,250 --> 00:06:54,490
a partir daí de novo.

156
00:06:54,490 --> 00:06:58,880
O tipo de fator de intimidação de
ponteiros em alocação dinâmica de memória

157
00:06:58,880 --> 00:07:00,130
é o obstáculo para limpar.

158
00:07:00,130 --> 00:07:04,550
Mas uma vez que você limpou-o, inserção
na verdade vem bastante simples,

159
00:07:04,550 --> 00:07:06,810
e é certamente tempo constante.

160
00:07:06,810 --> 00:07:07,680
>> A exclusão é fácil.

161
00:07:07,680 --> 00:07:11,330
Tudo que você precisa fazer é navegar para baixo a
par de ponteiros e livre o nó,

162
00:07:11,330 --> 00:07:12,420
de modo que é muito bom.

163
00:07:12,420 --> 00:07:13,930
Lookup também é bastante rápido.

164
00:07:13,930 --> 00:07:16,780
É só com base na
comprimento de seus dados.

165
00:07:16,780 --> 00:07:19,924
Portanto, se todos os seus dados é
cinco cadeias de caracteres,

166
00:07:19,924 --> 00:07:22,590
por exemplo, você está armazenando cinco
cadeias de caracteres em seu trie,

167
00:07:22,590 --> 00:07:25,439
ele só tem cinco passos para
encontrar o que você está procurando.

168
00:07:25,439 --> 00:07:28,480
Cinco é apenas um fator constante, por isso,
novamente, inserção, exclusão e pesquisa

169
00:07:28,480 --> 00:07:31,670
aqui estão todos os tempos constante, de forma eficaz.

170
00:07:31,670 --> 00:07:34,880
>> Outra coisa é que seu trie é
na verdade, meio que já classificadas, certo?

171
00:07:34,880 --> 00:07:36,800
Em virtude de como estamos
elementos Inserir,

172
00:07:36,800 --> 00:07:40,060
indo letra por letra do
chave, ou dígito por dígito da chave,

173
00:07:40,060 --> 00:07:45,084
normalmente, o trie acaba sendo
tipo de classificadas como você construí-lo.

174
00:07:45,084 --> 00:07:47,250
Realmente não faz
sentido pensar em classificação

175
00:07:47,250 --> 00:07:49,874
da mesma forma que pensamos sobre
com matrizes ou listas ligadas,

176
00:07:49,874 --> 00:07:51,070
ou tabelas de hash.

177
00:07:51,070 --> 00:07:54,780
Mas, em certo sentido, o seu
trie é classificada como você vai.

178
00:07:54,780 --> 00:07:58,630
>> A desvantagem, claro, é que
um trie rapidamente torna-se enorme.

179
00:07:58,630 --> 00:08:02,970
De todos os pontos de junção, você pode
have-- se sua chave é composta de dígitos,

180
00:08:02,970 --> 00:08:04,880
você tem 10 outros
lugares que você pode ir, o que

181
00:08:04,880 --> 00:08:07,490
significa que cada nó
contém informações

182
00:08:07,490 --> 00:08:11,440
sobre os dados que você deseja armazenar
no nó que, além de 10 ponteiros.

183
00:08:11,440 --> 00:08:14,430
Que, em CS50 IDE, é de 80 bytes.

184
00:08:14,430 --> 00:08:17,220
Então, é, pelo menos, 80 bytes para
cada nó que você criar,

185
00:08:17,220 --> 00:08:19,240
e isso não é mesmo contando dados.

186
00:08:19,240 --> 00:08:24,950
E se os seus nodos são
letras em vez de dígitos,

187
00:08:24,950 --> 00:08:27,825
agora você tem 26 ponteiros
de todos os locais.

188
00:08:27,825 --> 00:08:32,007
E 26 vezes 8 é provavelmente 200
bytes, ou algo parecido.

189
00:08:32,007 --> 00:08:33,840
E você tem o capital
e você pode lowercase--

190
00:08:33,840 --> 00:08:35,381
ver onde eu estou indo com isso, certo?

191
00:08:35,381 --> 00:08:37,500
Seus nós pode ficar muito
grande, e assim a trie

192
00:08:37,500 --> 00:08:40,470
-se, em geral, pode
ficar realmente grande, demasiado.

193
00:08:40,470 --> 00:08:42,630
Portanto, se o espaço é alta
prêmio em seu sistema,

194
00:08:42,630 --> 00:08:45,830
um trie pode não ser o caminho certo para
ir, apesar de seus outros benefícios

195
00:08:45,830 --> 00:08:47,780
entre no jogo.

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

197
00:08:48,710 --> 00:08:50,740
Este é CS50.

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