1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> COLUNA 1: Tudo bem, então este é
CS50 Este é o fim de semana cinco.

3
00:00:15,860 --> 00:00:19,220
E lembrar que da última vez que
comecei a olhar para os dados mais chique

4
00:00:19,220 --> 00:00:22,310
estruturas que passaram a resolver
problemas, que começaram a introduzir

5
00:00:22,310 --> 00:00:25,640
novos problemas, mas a chave para este
Era o tipo de rosqueamento que nós

6
00:00:25,640 --> 00:00:27,940
começou a fazer a partir de nó a nó.

7
00:00:27,940 --> 00:00:30,085
Então, isso, claro, é
uma lista vinculada isoladamente.

8
00:00:30,085 --> 00:00:31,960
E por vinculada isoladamente,
Quer dizer, há apenas um

9
00:00:31,960 --> 00:00:33,380
enrosque entre cada um desses nós.

10
00:00:33,380 --> 00:00:35,890
Acontece que você pode fazer mais chique
coisas como listas duplamente ligadas

11
00:00:35,890 --> 00:00:38,470
em que você tem uma seta
indo em ambas as direções, o que

12
00:00:38,470 --> 00:00:40,320
pode ajudar com determinadas eficiências.

13
00:00:40,320 --> 00:00:42,000
Mas isso resolveu o problema?

14
00:00:42,000 --> 00:00:43,500
O problema é que isto resolve?

15
00:00:43,500 --> 00:00:46,620
Por que nós nos importamos na segunda-feira?

16
00:00:46,620 --> 00:00:49,820
Por que, em teoria, se nós nos importamos na segunda-feira?

17
00:00:49,820 --> 00:00:50,630
O que isso faz?

18
00:00:50,630 --> 00:00:51,950
>> AUDIÊNCIA: Nós podemos redimensioná-lo dinamicamente.

19
00:00:51,950 --> 00:00:53,740
>> COLUNA 1: OK, então nós podemos
redimensioná-lo dinamicamente.

20
00:00:53,740 --> 00:00:54,710
Bem feito tanto de você.

21
00:00:54,710 --> 00:00:57,560
Assim, você pode redimensionar dinamicamente este
estrutura de dados, enquanto que uma matriz,

22
00:00:57,560 --> 00:01:00,760
recall, você tem que saber um
priori quanto espaço você quer

23
00:01:00,760 --> 00:01:03,870
e se você precisar de um pouco mais
espaço, você é tipo de fora da sorte.

24
00:01:03,870 --> 00:01:05,560
Você tem que criar uma matriz totalmente novo.

25
00:01:05,560 --> 00:01:07,893
Você tem que mover todos os seus
dados de um para o outro,

26
00:01:07,893 --> 00:01:10,600
eventualmente, liberar o array antigo
se você puder, e depois prosseguir.

27
00:01:10,600 --> 00:01:13,891
Que só se sente muito caro e muito
ineficiente, e na verdade ele pode ser.

28
00:01:13,891 --> 00:01:14,890
Mas isso não é tudo de bom.

29
00:01:14,890 --> 00:01:18,180
Nós pagamos um preço, o que era uma
dos preços mais óbvios nós

30
00:01:18,180 --> 00:01:20,550
pagar usando uma lista ligada?

31
00:01:20,550 --> 00:01:22,825
>> AUDIÊNCIA: Nós temos que usar
espaço duplo para cada um.

32
00:01:22,825 --> 00:01:25,200
COLUNA 1: Sim, por isso precisamos
pelo menos duas vezes mais espaço.

33
00:01:25,200 --> 00:01:27,700
Na verdade, eu percebi isso de imagem
até mesmo um pouco enganador,

34
00:01:27,700 --> 00:01:32,200
porque no IDE CS50 em um monte de moderno
computadores, um ponteiro ou um endereço

35
00:01:32,200 --> 00:01:33,700
não é, de facto, quatro bytes.

36
00:01:33,700 --> 00:01:36,090
É muito frequentemente estes
dias oito bytes, os quais

37
00:01:36,090 --> 00:01:38,530
significa que a parte inferior mais
retângulos lá em realidade

38
00:01:38,530 --> 00:01:40,900
são uma espécie de duas vezes mais
grande como o que eu desenhei,

39
00:01:40,900 --> 00:01:44,409
o que significa que você está usando três vezes mais
tanto espaço quanto poderíamos ter outra forma.

40
00:01:44,409 --> 00:01:46,700
Agora, ao mesmo tempo, estamos
ainda falando bytes, certo?

41
00:01:46,700 --> 00:01:49,140
Nós não estamos necessariamente falando
megabytes ou gigabytes,

42
00:01:49,140 --> 00:01:51,000
a menos que essas estruturas de dados ficar grande.

43
00:01:51,000 --> 00:01:54,510
>> E por isso hoje nós começamos a considerar
como podemos explorar dados

44
00:01:54,510 --> 00:01:57,310
de forma mais eficiente se em
fato de os dados se torna maior.

45
00:01:57,310 --> 00:02:00,360
Mas vamos tentar canonizar
as primeiras operações

46
00:02:00,360 --> 00:02:02,460
que você pode fazer sobre estes
tipos de estruturas de dados.

47
00:02:02,460 --> 00:02:04,790
Então, algo como um ligado
lista suporta geralmente

48
00:02:04,790 --> 00:02:07,514
Operações como excluir,
inserir e pesquisar.

49
00:02:07,514 --> 00:02:08,639
E o que quero dizer com isso?

50
00:02:08,639 --> 00:02:11,222
Isso só significa que, geralmente,
se as pessoas estão usando lista encadeada,

51
00:02:11,222 --> 00:02:14,287
eles ou alguém tem implementado
funções como DELETE, INSERT,

52
00:02:14,287 --> 00:02:16,120
e busca, assim você pode
realmente fazer alguma coisa

53
00:02:16,120 --> 00:02:18,030
útil com a estrutura de dados.

54
00:02:18,030 --> 00:02:20,760
Então, vamos dar uma olhada rápida
em como podemos implementar

55
00:02:20,760 --> 00:02:24,530
algum código para uma lista ligada como se segue.

56
00:02:24,530 --> 00:02:27,885
>> Portanto, este é apenas algum código C,
nem mesmo um programa completo

57
00:02:27,885 --> 00:02:29,260
que eu realmente rapidamente empolada.

58
00:02:29,260 --> 00:02:32,300
Não é on-line na distribuição
de código, pois não irão correr.

59
00:02:32,300 --> 00:02:33,790
Mas note Acabei
com um comentário disse,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, há algo
lá, dot dot dot, alguma coisa lá.

61
00:02:36,130 --> 00:02:38,410
E vamos apenas olhar para
que as peças são suculentos.

62
00:02:38,410 --> 00:02:40,790
Assim, na linha três,
Recordamos que este é agora

63
00:02:40,790 --> 00:02:45,960
propusemos declarando um nó último
tempo, um desses objetos retangulares.

64
00:02:45,960 --> 00:02:48,790
Ele tem um int que vamos chamá-N,
mas poderíamos chamá-lo de qualquer coisa,

65
00:02:48,790 --> 00:02:51,920
e, em seguida, uma estrela nó struct chamada seguinte.

66
00:02:51,920 --> 00:02:55,520
E só para ficar claro, que segundo
linha, em linha seis, o que é isso?

67
00:02:55,520 --> 00:02:57,930
O que ele está fazendo por nós?

68
00:02:57,930 --> 00:03:01,044
Porque certamente parece mais
críptica do que nossas variáveis ​​habituais.

69
00:03:01,044 --> 00:03:02,740
>> AUDIÊNCIA: Torna-se passar um.

70
00:03:02,740 --> 00:03:04,650
>> COLUNA 1: Ele faz mover-se mais de um.

71
00:03:04,650 --> 00:03:08,580
E para ser mais preciso,
ele irá armazenar o endereço

72
00:03:08,580 --> 00:03:11,582
do nó que está destinado a ser
semanticamente próximo a ele, certo?

73
00:03:11,582 --> 00:03:13,540
Por isso, não vai
necessariamente mover qualquer coisa.

74
00:03:13,540 --> 00:03:15,290
Ele só vai
armazenar um valor, que é

75
00:03:15,290 --> 00:03:17,170
vai ser o endereço
de algum outro nó,

76
00:03:17,170 --> 00:03:20,810
e é por isso que nós dissemos struct
estrela nó, a estrela denotando

77
00:03:20,810 --> 00:03:22,370
um ponteiro ou um endereço.

78
00:03:22,370 --> 00:03:26,390
OK, então agora se você assumir que temos
N esta disponível para nós, e vamos

79
00:03:26,390 --> 00:03:29,490
supor que alguém tem
inserido um monte de números inteiros

80
00:03:29,490 --> 00:03:30,400
em uma lista ligada.

81
00:03:30,400 --> 00:03:35,640
E essa lista ligada é
apontada por algum ponto

82
00:03:35,640 --> 00:03:39,040
um chamado de lista de variáveis ​​que é
passou aqui como um parâmetro,

83
00:03:39,040 --> 00:03:43,120
como faço para ir sobre a linha
14 execução de pesquisa?

84
00:03:43,120 --> 00:03:45,990
Em outras palavras, se eu estou implementando
função cujo propósito na vida

85
00:03:45,990 --> 00:03:48,889
é tomar um int e, em seguida, o
começando de uma lista ligada,

86
00:03:48,889 --> 00:03:50,430
que é um apontador para a lista encadeada.

87
00:03:50,430 --> 00:03:52,992
Como primeiro, que eu acho que David
foi o nosso voluntário na segunda-feira,

88
00:03:52,992 --> 00:03:54,700
ele estava apontando para
toda ligada a lista,

89
00:03:54,700 --> 00:03:57,820
é como se nós estamos passando
David em como nosso argumento aqui.

90
00:03:57,820 --> 00:03:59,990
Como é que vamos atravessar esta lista?

91
00:03:59,990 --> 00:04:04,640
Bem, acontece que, apesar de
ponteiros são relativamente novo para nós agora,

92
00:04:04,640 --> 00:04:07,010
nós podemos fazer isso relativamente
diretamente.

93
00:04:07,010 --> 00:04:09,500
>> Eu estou indo para ir em frente e
declarar uma variável temporária que

94
00:04:09,500 --> 00:04:12,364
por convenção é só ir
a ser chamado de ponteiro, ou PTR,

95
00:04:12,364 --> 00:04:14,030
mas você poderia chamá-lo de qualquer coisa que você quiser.

96
00:04:14,030 --> 00:04:16,470
E eu estou indo para inicializar
-lo para o início da lista.

97
00:04:16,470 --> 00:04:20,050
Assim, você pode tipo de pensar neste
como o professor me no outro dia,

98
00:04:20,050 --> 00:04:23,580
tipo de apontando para alguém
entre nossos seres humanos como voluntários.

99
00:04:23,580 --> 00:04:26,470
Então, eu sou uma variável temporária que é
apenas apontando para a mesma coisa

100
00:04:26,470 --> 00:04:31,390
que a nossa coincidentemente chamado
voluntário David também estava apontando.

101
00:04:31,390 --> 00:04:35,440
Agora, enquanto ponteiro é
não nulo, porque recordação

102
00:04:35,440 --> 00:04:40,350
que nulo é um valor especial sentinela
o demarca o fim da lista,

103
00:04:40,350 --> 00:04:44,280
assim, enquanto eu não estou apontando para a
terra como a nossa última voluntário

104
00:04:44,280 --> 00:04:47,190
era, vamos em frente
e faça o seguinte.

105
00:04:47,190 --> 00:04:51,820
Se pointer-- e agora eu meio que quero
para fazer o que fizemos com o aluno

106
00:04:51,820 --> 00:04:57,410
structure-- se ponteiro ponto próximo
equals-- vez, se é igual a N ponteiro ponto

107
00:04:57,410 --> 00:05:02,290
é igual à variável n, a
argumento que tem sido transmitido,

108
00:05:02,290 --> 00:05:05,370
então eu quero ir em frente
e dizer return true.

109
00:05:05,370 --> 00:05:11,020
Eu encontrei o número N dentro de
um dos nós da minha lista ligada.

110
00:05:11,020 --> 00:05:13,500
Mas o ponto deixa
funciona neste contexto,

111
00:05:13,500 --> 00:05:17,260
porque ponteiro, PTR, é
na verdade, um ponteiro, um endereço,

112
00:05:17,260 --> 00:05:20,632
nós realmente podemos maravilhosamente
Finalmente usar um pedaço de sintaxe

113
00:05:20,632 --> 00:05:22,590
esse tipo de marcas
senso intuitivo e, na verdade,

114
00:05:22,590 --> 00:05:27,870
usar uma flecha aqui, o que significa ir de
esse endereço para o número inteiro lá dentro.

115
00:05:27,870 --> 00:05:30,160
Portanto, é muito semelhante em
espírito para o operador ponto,

116
00:05:30,160 --> 00:05:33,860
mas porque ponteiro não é um ponteiro
e não uma struct em si real,

117
00:05:33,860 --> 00:05:35,380
nós apenas usar a seta.

118
00:05:35,380 --> 00:05:40,620
>> Portanto, se o nó atual que eu, o
variável temporária, estou apontando para

119
00:05:40,620 --> 00:05:43,060
não é N, o que eu quero fazer?

120
00:05:43,060 --> 00:05:45,910
Bem, com os meus voluntários humanos
que tivemos aqui no outro dia,

121
00:05:45,910 --> 00:05:49,710
se o meu primeiro ser humano não é o que eu
quer, e talvez o segundo humano não é

122
00:05:49,710 --> 00:05:52,660
o que eu quero, eo terceiro, I
precisa para se manter fisicamente em movimento.

123
00:05:52,660 --> 00:05:54,690
Como como faço para percorrer uma lista?

124
00:05:54,690 --> 00:05:57,470
Quando tivemos um array você,
apenas fiz como eu plus plus.

125
00:05:57,470 --> 00:06:03,660
Mas, neste caso, basta
fazer ponteiro, fica, ponteiro, em seguida.

126
00:06:03,660 --> 00:06:07,580
Em outras palavras, o campo seguinte
é como todas as mãos esquerda

127
00:06:07,580 --> 00:06:10,880
que os nossos voluntários humanos na segunda-feira
estavam usando para apontar para algum outro nó.

128
00:06:10,880 --> 00:06:12,890
Aqueles eram seus vizinhos próximos.

129
00:06:12,890 --> 00:06:17,060
>> Então, se eu quiser passar por esta lista,
Eu não posso simplesmente fazer eu plus plus mais,

130
00:06:17,060 --> 00:06:20,120
Eu tenho que dizer, em vez
I, ponteiro, vai

131
00:06:20,120 --> 00:06:24,650
para igualar qualquer que seja o campo seguinte é,
O próximo campo, o campo seguinte é,

132
00:06:24,650 --> 00:06:28,350
seguindo todas essas mãos esquerdas
que tivemos no palco apontador

133
00:06:28,350 --> 00:06:30,000
para alguns valores subsequentes.

134
00:06:30,000 --> 00:06:32,590
E se eu passar
Toda essa iteração,

135
00:06:32,590 --> 00:06:39,330
e, finalmente, eu bati nulo não ter
N encontrado ainda, eu só retornar falso.

136
00:06:39,330 --> 00:06:44,100
Então, novamente, tudo o que estamos fazendo aqui,
de acordo com a imagem de um momento atrás,

137
00:06:44,100 --> 00:06:47,840
está começando por apontar para a
início da lista presumivelmente.

138
00:06:47,840 --> 00:06:50,970
E então eu vá, é o valor
Eu estou procurando igual a nove?

139
00:06:50,970 --> 00:06:52,650
Se assim for, volto verdade e eu sou feito.

140
00:06:52,650 --> 00:06:56,450
Se não, eu atualizo minha mão,
Ponteiro AKA, para apontar

141
00:06:56,450 --> 00:06:59,540
a localização da próxima seta e,
em seguida, a localização próxima da seta,

142
00:06:59,540 --> 00:07:00,480
e no próximo.

143
00:07:00,480 --> 00:07:03,770
Eu estou simplesmente andando através desta matriz.

144
00:07:03,770 --> 00:07:06,010
>> Então, novamente, quem se importa?

145
00:07:06,010 --> 00:07:07,861
Como o que é este um ingrediente para?

146
00:07:07,861 --> 00:07:10,360
Bem, lembre-se que nós introduzimos
a noção de uma pilha, que

147
00:07:10,360 --> 00:07:15,400
é um tipo abstrato de dados na medida em que é
não é uma coisa C, não é uma coisa CS50,

148
00:07:15,400 --> 00:07:19,430
é uma idéia abstrata, essa idéia de
empilhamento coisas em cima da outra

149
00:07:19,430 --> 00:07:21,820
que pode ser implementado em
cachos de maneiras diferentes.

150
00:07:21,820 --> 00:07:25,600
E uma maneira que propusemos foi com
uma matriz, ou com uma lista ligada.

151
00:07:25,600 --> 00:07:29,570
E verifica-se que canonicamente, uma
pilha suporta, pelo menos, duas operações.

152
00:07:29,570 --> 00:07:32,320
E as palavras de zumbido são empurrão, para
empurrar algo para a pilha,

153
00:07:32,320 --> 00:07:34,770
como uma nova bandeja no
sala de jantar, ou pop,

154
00:07:34,770 --> 00:07:39,000
o que significa que para remover o mais alto
bandeja da pilha no jantar

155
00:07:39,000 --> 00:07:41,500
hall, e então talvez alguns
bem como outras operações.

156
00:07:41,500 --> 00:07:45,770
Então, como podemos definir a estrutura
que agora estamos chamando uma pilha?

157
00:07:45,770 --> 00:07:50,020
>> Bem, nós temos todo o requisite
sintaxe à nossa disposição em C. Eu digo,

158
00:07:50,020 --> 00:07:53,830
me dê uma definição de tipo de
uma estrutura dentro de uma pilha,

159
00:07:53,830 --> 00:07:58,030
Eu vou dizer é um array, de um
todo monte de números e, em seguida tamanho.

160
00:07:58,030 --> 00:08:00,930
Portanto, em outras palavras, se eu quiser
para implementar isso no código,

161
00:08:00,930 --> 00:08:03,830
Deixa-me ir apenas uma espécie de
desenhar o que se diz.

162
00:08:03,830 --> 00:08:06,317
Portanto, este está dizendo, me dê um
estrutura que tem uma matriz,

163
00:08:06,317 --> 00:08:09,400
e eu não sei o que é capacidade,
é aparentemente alguma constante que eu tenho

164
00:08:09,400 --> 00:08:10,858
definido em outro lugar, e isso é bom.

165
00:08:10,858 --> 00:08:15,260
Mas suponho que é apenas um,
dois, três, quatro, cinco.

166
00:08:15,260 --> 00:08:16,700
Assim, a capacidade é de 5.

167
00:08:16,700 --> 00:08:21,730
Este elemento dentro da minha
estrutura serão chamados números.

168
00:08:21,730 --> 00:08:24,020
E então eu preciso de um
outra variável aparentemente

169
00:08:24,020 --> 00:08:27,814
chamado tamanho que inicialmente eu vou
estipular é inicializado para zero.

170
00:08:27,814 --> 00:08:29,730
Se não há nada em
a pilha, o tamanho é zero,

171
00:08:29,730 --> 00:08:31,420
e seus valores de lixo em números.

172
00:08:31,420 --> 00:08:33,450
Eu não tenho idéia o que está lá ainda.

173
00:08:33,450 --> 00:08:36,059
>> Então, se eu quero empurrar
algo na pilha,

174
00:08:36,059 --> 00:08:40,780
suponha que eu chamo de impulso função, e
Eu digo empurrar 50, como o número 50,

175
00:08:40,780 --> 00:08:44,090
onde proporia
Eu desenhá-lo nessa matriz?

176
00:08:44,090 --> 00:08:47,124
Há cinco diferentes respostas possíveis.

177
00:08:47,124 --> 00:08:48,790
Onde você quer empurrar o número 50?

178
00:08:48,790 --> 00:08:51,899
Se o objetivo aqui, mais uma vez, chamar a
empurrão função, passa um argumento

179
00:08:51,899 --> 00:08:52,940
de 50, onde posso colocá-lo?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
Cinco possible-- 20% de chance
de adivinhar corretamente.

182
00:08:59,052 --> 00:08:59,896
Sim?

183
00:08:59,896 --> 00:09:00,740
>> AUDIÊNCIA: Extrema-direita.

184
00:09:00,740 --> 00:09:01,990
>> COLUNA 1: Extrema-direita.

185
00:09:01,990 --> 00:09:08,359
Existe agora uma chance de 25%
de adivinhar corretamente.

186
00:09:08,359 --> 00:09:09,650
De modo que seria realmente bom.

187
00:09:09,650 --> 00:09:12,770
Por convenção, eu vou dizer com uma matriz,
que seria geralmente começar à esquerda,

188
00:09:12,770 --> 00:09:14,519
mas poderíamos certamente
começa pela direita.

189
00:09:14,519 --> 00:09:17,478
Então, o spoiler aqui seria eu sou
provavelmente, vai para desenhá-lo à esquerda,

190
00:09:17,478 --> 00:09:20,060
assim como em uma matriz normal, onde
Eu começo a ir à esquerda para a direita.

191
00:09:20,060 --> 00:09:21,780
Mas se você pode virar
a aritmética, tudo bem.

192
00:09:21,780 --> 00:09:23,060
Não é apenas convencional.

193
00:09:23,060 --> 00:09:24,880
OK, eu preciso fazer uma
mais mudanças embora.

194
00:09:24,880 --> 00:09:27,710
Agora que eu empurrei algo
para a pilha, o que está próximo?

195
00:09:27,710 --> 00:09:29,400
>> Tudo bem, eu tenho que aumentar o tamanho.

196
00:09:29,400 --> 00:09:32,600
Então deixe-me ir em frente e apenas
actualizar esta, que era igual a zero.

197
00:09:32,600 --> 00:09:35,950
E, em vez agora, eu vou
para colocar no valor de um.

198
00:09:35,950 --> 00:09:39,460
E agora suponho que eu empurre outro
número na pilha, como 51.

199
00:09:39,460 --> 00:09:42,680
Bem, eu tenho que fazer mais uma
mudança, que é até o tamanho dois.

200
00:09:42,680 --> 00:09:46,100
E então suponho que eu empurrar mais uma
número na pilha como 61,

201
00:09:46,100 --> 00:09:52,530
agora eu preciso atualizar o tamanho mais uma
tempo, e obter o valor 3 como o tamanho.

202
00:09:52,530 --> 00:09:54,690
E agora suponho que eu chamo pop.

203
00:09:54,690 --> 00:09:57,250
Agora pop, por convenção,
Não é preciso um argumento.

204
00:09:57,250 --> 00:10:00,430
Com uma pilha, o conjunto
ponto da metáfora bandeja

205
00:10:00,430 --> 00:10:03,450
é que você não tem poder discricionário
para ir buscar a bandeja, tudo que você pode fazer

206
00:10:03,450 --> 00:10:06,330
é pop o mais alto de uma
pilha, apenas porque.

207
00:10:06,330 --> 00:10:08,010
Isso é o que esta estrutura de dados faz.

208
00:10:08,010 --> 00:10:12,250
>> Então, por que a lógica se eu
dizer pop, o que sai?

209
00:10:12,250 --> 00:10:13,080
Então, 61.

210
00:10:13,080 --> 00:10:15,402
Então, o que realmente é o computador
vai fazer na memória?

211
00:10:15,402 --> 00:10:16,610
O que o meu código tem que fazer?

212
00:10:16,610 --> 00:10:20,330
O que proporia
nós mudamos na tela?

213
00:10:20,330 --> 00:10:23,410
O que deve mudar?

214
00:10:23,410 --> 00:10:24,960
Desculpa?

215
00:10:24,960 --> 00:10:26,334
Por isso, se livrar de 61.

216
00:10:26,334 --> 00:10:27,500
Então eu definitivamente posso fazer isso.

217
00:10:27,500 --> 00:10:28,640
E eu posso me livrar de 61.

218
00:10:28,640 --> 00:10:30,980
E então o que os outros
mudança precisa acontecer?

219
00:10:30,980 --> 00:10:33,160
Tamanho, provavelmente, tem que voltar para dois.

220
00:10:33,160 --> 00:10:34,210
E assim tudo bem.

221
00:10:34,210 --> 00:10:36,690
Mas espere um minuto, tamanho
um momento atrás tinha três anos.

222
00:10:36,690 --> 00:10:38,240
Vamos apenas fazer uma verificação de sanidade rápida.

223
00:10:38,240 --> 00:10:41,810
Como é que nós sabemos que nós
queria se livrar de 61?

224
00:10:41,810 --> 00:10:42,760
Porque nós estamos estalando.

225
00:10:42,760 --> 00:10:46,450
E então eu tenho esta segunda tamanho da propriedade.

226
00:10:46,450 --> 00:10:48,470
>> Espere um minuto, estou
pensando de volta para a segunda semana

227
00:10:48,470 --> 00:10:51,660
quando começamos a falar sobre
arrays, onde este foi local de zero,

228
00:10:51,660 --> 00:10:55,920
este foi um local, este foi localização
dois, este é o local de três, quatro,

229
00:10:55,920 --> 00:10:58,460
parece que o
relação entre o tamanho

230
00:10:58,460 --> 00:11:02,780
e o elemento que eu quero remover
a partir da matriz parece ser apenas o que?

231
00:11:02,780 --> 00:11:05,120
Tamanho menos um.

232
00:11:05,120 --> 00:11:07,786
E foi assim que, como seres humanos
sabemos que 61 vem em primeiro lugar.

233
00:11:07,786 --> 00:11:09,160
Como está o computador vai saber?

234
00:11:09,160 --> 00:11:11,701
Quando seu código, onde você provavelmente
quer fazer o tamanho menos um,

235
00:11:11,701 --> 00:11:14,950
Assim, três menos um é dois, e que
significa que querem se livrar de 61.

236
00:11:14,950 --> 00:11:18,000
E então podemos realmente atualizar
o tamanho de modo que o tamanho agora

237
00:11:18,000 --> 00:11:20,300
vai desde três a apenas dois.

238
00:11:20,300 --> 00:11:24,520
E só para ser pedante, eu vou
a propor que eu sou feito, certo?

239
00:11:24,520 --> 00:11:27,660
Você proposto intuitivamente
corretamente eu deveria livrar-se de 61.

240
00:11:27,660 --> 00:11:30,700
Mas não tem que tipo de
tipo de livrado de 61?

241
00:11:30,700 --> 00:11:33,790
Eu efetivamente esquecido
que é realmente lá.

242
00:11:33,790 --> 00:11:37,680
E acho que volta para PSet4, se você leu
o artigo sobre forense, o PDF

243
00:11:37,680 --> 00:11:40,780
que tínhamos vocês ler, ou você
vai ler esta semana para PSet4.

244
00:11:40,780 --> 00:11:44,300
Lembre-se que este é realmente pertinente para
toda a idéia de computação forense.

245
00:11:44,300 --> 00:11:47,820
O que um computador faz é geralmente
ele simplesmente se esquece de onde algo é,

246
00:11:47,820 --> 00:11:51,300
mas não ir e como
tentar riscá-lo fora ou substituição

247
00:11:51,300 --> 00:11:54,560
esses bits com zeros e uns
ou algum outro padrão aleatório

248
00:11:54,560 --> 00:11:56,690
a menos que você mesmo fazê-lo deliberadamente.

249
00:11:56,690 --> 00:11:58,930
Assim, a sua intuição estava
bem, vamos nos livrar de 61.

250
00:11:58,930 --> 00:12:00,650
Mas, na realidade, não tem que se preocupar.

251
00:12:00,650 --> 00:12:04,040
Nós só precisamos esquecer que
ele está lá mudando nosso tamanho.

252
00:12:04,040 --> 00:12:05,662
>> Agora há um problema com esta pilha.

253
00:12:05,662 --> 00:12:07,620
Se eu continuar empurrando as coisas
para a pilha, o que é

254
00:12:07,620 --> 00:12:11,167
obviamente, vai acontecer
em apenas alguns momentos do tempo?

255
00:12:11,167 --> 00:12:12,500
Nós vamos ficar sem espaço.

256
00:12:12,500 --> 00:12:13,580
E o que vamos fazer?

257
00:12:13,580 --> 00:12:14,680
Estamos tipo de rosca.

258
00:12:14,680 --> 00:12:19,000
Esta implementação não deixa
nos redimensionar a matriz, porque usar

259
00:12:19,000 --> 00:12:21,240
esta sintaxe, se você
acho que volta para duas semanas,

260
00:12:21,240 --> 00:12:23,520
uma vez que você declarou
o tamanho de uma matriz,

261
00:12:23,520 --> 00:12:26,780
nós não vimos ainda um mecanismo onde
você pode alterar o tamanho da matriz.

262
00:12:26,780 --> 00:12:29,020
E, de fato C não tem esse recurso.

263
00:12:29,020 --> 00:12:32,524
Se você diz que me dar cinco
Nths, chamá-los de números,

264
00:12:32,524 --> 00:12:33,940
isso é tudo o que você está indo para obtê-lo.

265
00:12:33,940 --> 00:12:38,790
Então, o que fazemos agora como de segunda-feira, tem
a capacidade de expressar uma solução

266
00:12:38,790 --> 00:12:42,480
porém, só precisamos ajustar
a definição da nossa pilha

267
00:12:42,480 --> 00:12:46,840
a não ser alguns matriz codificados,
mas apenas para armazenar um endereço.

268
00:12:46,840 --> 00:12:47,890
>> Agora, por que é isso?

269
00:12:47,890 --> 00:12:51,690
Agora só temos de estar confortável com
o fato de que quando o meu programa é executado,

270
00:12:51,690 --> 00:12:53,730
Eu estou indo para presumivelmente
tem que perguntar o ser humano,

271
00:12:53,730 --> 00:12:55,110
quantos números que você deseja armazenar?

272
00:12:55,110 --> 00:12:56,776
Assim, a entrada tem que vir de algum lugar.

273
00:12:56,776 --> 00:12:59,140
Mas uma vez eu sei que
número, então eu posso apenas

274
00:12:59,140 --> 00:13:02,470
usar o que funciona para dar
me um pedaço de memória?

275
00:13:02,470 --> 00:13:03,580
Eu posso usar malloc.

276
00:13:03,580 --> 00:13:06,710
E eu posso dizer qualquer número de
bytes Eu quero voltar para estes Nths.

277
00:13:06,710 --> 00:13:10,910
E tudo o que tenho para armazenar os números
variável aqui dentro deste struct

278
00:13:10,910 --> 00:13:13,480
deve ser o que?

279
00:13:13,480 --> 00:13:18,440
O que realmente vai para o
números nesse cenário?

280
00:13:18,440 --> 00:13:21,300
É, um ponteiro para o primeiro
byte desse pedaço de memória,

281
00:13:21,300 --> 00:13:24,940
ou mais especificamente, o endereço
do primeiro desses bytes.

282
00:13:24,940 --> 00:13:27,300
Não importa se é um
bytes ou um bilhão de bytes,

283
00:13:27,300 --> 00:13:28,890
Eu só precisa se preocupar com o primeiro.

284
00:13:28,890 --> 00:13:31,530
Porque o que malloc e garantias
minhas garantias do sistema operacional,

285
00:13:31,530 --> 00:13:34,170
é que o pedaço de memória I
obter, ele vai ser contíguos.

286
00:13:34,170 --> 00:13:35,378
Não vai ser lacunas.

287
00:13:35,378 --> 00:13:38,576
Então, se eu pedi para 50
ou bytes 1.000 bytes,

288
00:13:38,576 --> 00:13:40,450
eles estão todos indo para ser
back to back to back.

289
00:13:40,450 --> 00:13:44,500
E desde que eu me lembro como grande, como
Eu pedi muito, tudo o que precisa de saber

290
00:13:44,500 --> 00:13:46,230
é o primeiro tal endereço.

291
00:13:46,230 --> 00:13:48,660
>> Portanto, agora temos a capacidade de código.

292
00:13:48,660 --> 00:13:51,280
Embora, isso vai nos levar
mais tempo para escrever isto,

293
00:13:51,280 --> 00:13:55,900
poderíamos agora realocar que a memória por
apenas armazenar um endereço diferente lá

294
00:13:55,900 --> 00:13:59,060
se queremos uma maior ou mesmo
um pedaço menor de memória.

295
00:13:59,060 --> 00:14:00,170
Então aqui para encontrar um compromisso.

296
00:14:00,170 --> 00:14:01,360
Agora temos dinamismo.

297
00:14:01,360 --> 00:14:03,350
Nós ainda temos
contiguidade estou afirmando.

298
00:14:03,350 --> 00:14:05,881
Porque malloc nos dará
um pedaço contíguo de memória.

299
00:14:05,881 --> 00:14:08,630
Mas isso vai ser uma dor no
o pescoço para nós, o programador,

300
00:14:08,630 --> 00:14:09,770
para realmente codificar.

301
00:14:09,770 --> 00:14:10,730
É apenas mais trabalho.

302
00:14:10,730 --> 00:14:13,930
Precisamos de código semelhante ao que eu era
batendo para fora apenas um momento atrás.

303
00:14:13,930 --> 00:14:16,120
Muito factível, mas adiciona complexidade.

304
00:14:16,120 --> 00:14:19,520
E assim desenvolvedor tempo, programador
o tempo é ainda um outro recurso

305
00:14:19,520 --> 00:14:22,520
para que pudéssemos precisa gastar
algum tempo para obter novos recursos.

306
00:14:22,520 --> 00:14:24,020
E depois, claro, há uma fila.

307
00:14:24,020 --> 00:14:26,227
Nós não vamos entrar nesse
um em muito detalhe.

308
00:14:26,227 --> 00:14:27,560
Mas é muito semelhante em espírito.

309
00:14:27,560 --> 00:14:31,220
Eu poderia implementar uma fila, e
suas operações correspondentes,

310
00:14:31,220 --> 00:14:35,660
enqueue ou dequeue, como adicionar ou remover,
é apenas uma maneira de dizê-lo mais chique,

311
00:14:35,660 --> 00:14:38,100
enfileiramento ou desenfileirar, como se segue.

312
00:14:38,100 --> 00:14:41,170
Eu só posso me dar um struct
que novamente tem matriz de um número,

313
00:14:41,170 --> 00:14:44,000
que de novo tem um tamanho,
Mas por que eu preciso agora

314
00:14:44,000 --> 00:14:46,940
para manter o controle da frente de uma fila?

315
00:14:46,940 --> 00:14:50,630
Eu não preciso saber
a frente da minha stack.

316
00:14:50,630 --> 00:14:53,570
Bem, se eu novamente para uma
queue-- vamos duro

317
00:14:53,570 --> 00:14:57,870
codificá-lo como tendo como cinco
inteiros em aqui potencialmente.

318
00:14:57,870 --> 00:15:00,940
Portanto, este é zero, um, dois, três, quatro.

319
00:15:00,940 --> 00:15:03,430
Este vai ser
números chamados novamente.

320
00:15:03,430 --> 00:15:06,940
E isso vai ser chamado de tamanho.

321
00:15:06,940 --> 00:15:10,056
>> Por que não é suficiente
ter apenas o tamanho?

322
00:15:10,056 --> 00:15:11,680
Bem, vamos empurrar os mesmos números por diante.

323
00:15:11,680 --> 00:15:14,220
Então eu pushed-- I enfileirado, ou empurrado.

324
00:15:14,220 --> 00:15:20,150
Agora eu vou enfileirar 50, e, em seguida,
51, e depois 61, e Dot Dot Dot.

325
00:15:20,150 --> 00:15:21,070
Então, isso é enqueue.

326
00:15:21,070 --> 00:15:23,176
I enfileirados 50, depois 51, depois 61.

327
00:15:23,176 --> 00:15:25,050
E isso parece idêntico
para uma pilha até agora,

328
00:15:25,050 --> 00:15:27,190
só que eu preciso fazer uma mudança.

329
00:15:27,190 --> 00:15:33,680
Eu preciso atualizar esse tamanho, então eu ir
de zero a um de dois a três agora.

330
00:15:33,680 --> 00:15:35,760
Como faço para retirar da fila?

331
00:15:35,760 --> 00:15:36,890
O que acontece com dequeue?

332
00:15:36,890 --> 00:15:41,950
Quem deve sair esta lista primeiro
se é a linha na loja da Apple?

333
00:15:41,950 --> 00:15:42,780
Então, 50.

334
00:15:42,780 --> 00:15:44,700
Então é meio complicado desta vez.

335
00:15:44,700 --> 00:15:47,880
Considerando última vez que ele foi super
fácil simplesmente fazer o tamanho menos um,

336
00:15:47,880 --> 00:15:51,440
Eu chegar ao final da minha matriz efetivamente
onde os números são, ele remove 61.

337
00:15:51,440 --> 00:15:52,920
Mas eu não quero remover 61.

338
00:15:52,920 --> 00:15:55,030
Eu quero ter 50 anos, que
estava lá na 5:00

339
00:15:55,030 --> 00:15:56,790
para a linha para o
novo iPhone ou outros enfeites.

340
00:15:56,790 --> 00:16:01,200
E assim se livrar de 50, I
não pode simplesmente fazer isso, certo?

341
00:16:01,200 --> 00:16:02,547
Eu posso atravessar a 50.

342
00:16:02,547 --> 00:16:04,380
Mas nós apenas disse que
não tem que ser tão anal

343
00:16:04,380 --> 00:16:06,330
como a riscar ou ocultar os dados.

344
00:16:06,330 --> 00:16:08,090
Nós podemos simplesmente esquecer onde está.

345
00:16:08,090 --> 00:16:12,330
>> Mas se eu mudar o meu tamanho agora
dois, é esta informação suficiente

346
00:16:12,330 --> 00:16:15,711
para saber o que está acontecendo na minha fila?

347
00:16:15,711 --> 00:16:16,680
Na verdade, não.

348
00:16:16,680 --> 00:16:19,830
Tal como o meu tamanho é dois, mas
onde é que a fila de começar,

349
00:16:19,830 --> 00:16:22,980
especialmente se eu ainda tenho
esses mesmos números na memória.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Então, eu preciso lembrar
Agora, onde a frente é.

352
00:16:27,090 --> 00:16:29,630
E assim como eu propus-se
lá, nós vamos ter chamado apenas

353
00:16:29,630 --> 00:16:33,729
Frente Nth, cuja inicial
valor deve ter sido o que?

354
00:16:33,729 --> 00:16:35,270
Zero, apenas o começo da lista.

355
00:16:35,270 --> 00:16:40,876
Mas agora, além de decrementing
o tamanho, nós apenas incrementar a frente.

356
00:16:40,876 --> 00:16:42,000
Ora aqui está um outro problema.

357
00:16:42,000 --> 00:16:43,030
Então, quando eu continuo indo.

358
00:16:43,030 --> 00:16:47,520
Suponhamos que este é o número de
como 121, 124, e, em seguida, caramba,

359
00:16:47,520 --> 00:16:48,610
Estou fora do espaço.

360
00:16:48,610 --> 00:16:50,390
Mas espere um minuto, eu não sou.

361
00:16:50,390 --> 00:16:55,630
Então, neste ponto da história,
suponhamos que o tamanho é um, dois,

362
00:16:55,630 --> 00:17:00,370
três, quatro, de modo que o supor
tamanho é quatro, a frente é um,

363
00:17:00,370 --> 00:17:01,621
de modo 51 é a parte da frente.

364
00:17:01,621 --> 00:17:04,329
Eu quero colocar outro número aqui,
mas, caramba, eu estou fora do espaço.

365
00:17:04,329 --> 00:17:06,710
Mas eu não sou realmente, certo?

366
00:17:06,710 --> 00:17:11,192
Onde eu poderia colocar algum
valor adicional, como 171?

367
00:17:11,192 --> 00:17:13,400
Sim, eu poderia apenas uma espécie de
voltar para lá, certo?

368
00:17:13,400 --> 00:17:18,161
E, em seguida, atravessar a 50, ou
apenas substituí-lo com 171.

369
00:17:18,161 --> 00:17:20,410
E se você está se perguntando por
nossos números ficou tão aleatório,

370
00:17:20,410 --> 00:17:24,150
estes são normalmente tomadas computador
cursos de ciências em Harvard após CS50.

371
00:17:24,150 --> 00:17:27,510
Mas isso foi uma boa otimização,
porque agora eu não estou desperdiçando espaço.

372
00:17:27,510 --> 00:17:30,750
Eu ainda tenho que lembrar
quão grande essa coisa é total.

373
00:17:30,750 --> 00:17:31,500
É cinco totais.

374
00:17:31,500 --> 00:17:33,375
Porque eu não quero
começar a substituir 51.

375
00:17:33,375 --> 00:17:36,260
Então agora eu ainda estou sem espaço,
de modo que o mesmo problema de antes.

376
00:17:36,260 --> 00:17:39,140
Mas você pode ver como agora
em seu código, você provavelmente

377
00:17:39,140 --> 00:17:41,910
tem que escrever um pouco mais
complexidade para que isso aconteça.

378
00:17:41,910 --> 00:17:44,510
E, de fato, o operador
em C provavelmente permite

379
00:17:44,510 --> 00:17:48,110
você magicamente fazer isso a circularidade?

380
00:17:48,110 --> 00:17:50,160
Sim, o operador módulo,
o sinal de porcentagem.

381
00:17:50,160 --> 00:17:53,160
Então, o que é legal sobre uma fila,
embora nós manter matrizes desenho

382
00:17:53,160 --> 00:17:56,520
como essas linhas retas como, se você
tipo de pensar sobre isso como encurvamento

383
00:17:56,520 --> 00:18:00,341
em torno de como um círculo, em seguida, basta
intuitivamente que tipo de obras mentalmente

384
00:18:00,341 --> 00:18:01,590
Eu acho que um pouco mais limpa.

385
00:18:01,590 --> 00:18:05,190
Você ainda teria que implementar
que modelo mental no código.

386
00:18:05,190 --> 00:18:07,550
Então, não é difícil,
em última análise, para implementar,

387
00:18:07,550 --> 00:18:12,430
mas ainda perder o size-- vez, o
capacidade de redimensionar, a menos que façamos isso.

388
00:18:12,430 --> 00:18:15,310
>> Temos de livrar-se da matriz, nós
substituí-lo por um único ponteiro,

389
00:18:15,310 --> 00:18:20,010
e, em seguida, em algum lugar no meu código que eu tenho
a chamar o que funcionar para realmente criar

390
00:18:20,010 --> 00:18:23,720
a matriz de números chamados?

391
00:18:23,720 --> 00:18:26,190
Malloc, ou alguma semelhante
função, exatamente.

392
00:18:26,190 --> 00:18:30,481
Quaisquer perguntas sobre pilhas ou filas.

393
00:18:30,481 --> 00:18:30,980
Sim?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Boa pergunta.

396
00:18:34,240 --> 00:18:35,830
Qual módulo você usaria aqui.

397
00:18:35,830 --> 00:18:38,520
Assim, em geral, quando se utiliza
mod, você faria isso

398
00:18:38,520 --> 00:18:40,620
com o tamanho do
estrutura inteira de dados.

399
00:18:40,620 --> 00:18:44,120
Então, algo como cinco ou capacidade, se
é constante, está provavelmente envolvido.

400
00:18:44,120 --> 00:18:47,100
Mas apenas fazendo modulo cinco
provavelmente não é suficiente,

401
00:18:47,100 --> 00:18:51,380
porque nós precisamos saber é que nós
envolver em torno de aqui ou aqui ou aqui.

402
00:18:51,380 --> 00:18:54,160
Então você provavelmente está também
vai querer envolver

403
00:18:54,160 --> 00:18:57,220
o tamanho da coisa, ou
a variável frente também.

404
00:18:57,220 --> 00:19:00,140
Então é só isso relativamente
expressão aritmética simples,

405
00:19:00,140 --> 00:19:02,000
mas módulo seria o ingrediente chave.

406
00:19:02,000 --> 00:19:03,330
>> Então, curta-metragem se você quiser.

407
00:19:03,330 --> 00:19:05,780
Uma animação que alguns
povos em outra universidade

408
00:19:05,780 --> 00:19:08,060
juntos que nós temos
adaptado para esta discussão.

409
00:19:08,060 --> 00:19:12,630
Trata-se de aprender a Jack
fatos sobre filas e estatísticas.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> FILME: Era uma vez,
havia um cara chamado Jack.

412
00:19:21,890 --> 00:19:25,330
Quando ele veio para fazer amigos,
Jack não tem um talento especial.

413
00:19:25,330 --> 00:19:28,220
Então Jack foi conversar com o
mais cara popular que ele conhecia.

414
00:19:28,220 --> 00:19:30,920
Ele foi para Lou e perguntou: O que eu faço?

415
00:19:30,920 --> 00:19:33,400
Lou viu que seu amigo
foi muito angustiado.

416
00:19:33,400 --> 00:19:36,050
Bem, ele começou, apenas
olha como você está vestida.

417
00:19:36,050 --> 00:19:38,680
Você não tem nenhuma roupa
com um olhar diferente?

418
00:19:38,680 --> 00:19:39,660
Sim, disse Jack.

419
00:19:39,660 --> 00:19:40,840
Eu com certeza faço.

420
00:19:40,840 --> 00:19:43,320
Venha à minha casa e
Eu vou mostrar a você.

421
00:19:43,320 --> 00:19:44,550
Então, eles foram para Jack.

422
00:19:44,550 --> 00:19:47,520
Jack e Lou mostrou a caixa
onde guardava todas as suas camisas,

423
00:19:47,520 --> 00:19:49,260
e as calças e as meias.

424
00:19:49,260 --> 00:19:52,290
Lou disse, eu vejo que você tem
todas as suas roupas em uma pilha.

425
00:19:52,290 --> 00:19:54,870
Por que você não usar algum
outros de vez em quando?

426
00:19:54,870 --> 00:19:58,020
>> Jack disse, bem, quando eu
remover roupas e meias,

427
00:19:58,020 --> 00:20:00,780
Eu lavá-los e colocá-
-los na caixa.

428
00:20:00,780 --> 00:20:03,210
Em seguida, vem o próximo
manhã, e se eu pulo.

429
00:20:03,210 --> 00:20:06,380
Eu ir para a caixa e obter
minhas roupas fora do topo.

430
00:20:06,380 --> 00:20:09,070
Lou percebeu rapidamente
O problema com Jack.

431
00:20:09,070 --> 00:20:12,080
Ele manteve roupas, CDs,
e livros na pilha.

432
00:20:12,080 --> 00:20:14,420
Quando chegou para
algo para ler ou para vestir,

433
00:20:14,420 --> 00:20:17,100
ele escolheria o topo livro ou roupa interior.

434
00:20:17,100 --> 00:20:19,500
Então, quando ele foi feito, ele
iria colocá-lo de volta.

435
00:20:19,500 --> 00:20:21,970
Voltar seria ir, no topo da pilha.

436
00:20:21,970 --> 00:20:24,460
Eu sei a solução,
disse um alto triunfante.

437
00:20:24,460 --> 00:20:27,090
Você precisa aprender a
começar a usar uma fila.

438
00:20:27,090 --> 00:20:29,870
Lou pegou roupas de Jack e
pendurou-os no armário.

439
00:20:29,870 --> 00:20:32,710
E quando ele tinha esvaziado
a caixa, ele simplesmente jogou-a.

440
00:20:32,710 --> 00:20:36,500
>> Então ele disse, agora Jack, no final de
o dia, colocar suas roupas no lado esquerdo

441
00:20:36,500 --> 00:20:37,990
quando você colocá-los fora.

442
00:20:37,990 --> 00:20:41,300
Então, amanhã de manhã quando você
ver a luz do sol, pegar suas roupas

443
00:20:41,300 --> 00:20:43,440
à direita, a partir da extremidade da linha.

444
00:20:43,440 --> 00:20:44,880
Você não vê? disse Lou.

445
00:20:44,880 --> 00:20:46,370
Ele vai ser tão bom.

446
00:20:46,370 --> 00:20:49,770
Você vai usar tudo uma vez
antes de usar algo duas vezes.

447
00:20:49,770 --> 00:20:52,670
E com tudo em filas
em seu armário e prateleira,

448
00:20:52,670 --> 00:20:55,160
Jack começou a se sentir
muito seguro de si.

449
00:20:55,160 --> 00:20:59,720
Tudo graças a Lou e
sua maravilhosa fila.

450
00:20:59,720 --> 00:21:01,220
COLUNA 1: Tudo bem, é adorável.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Então, o que foi realmente acontecendo
por baixo do capuz agora?

453
00:21:10,080 --> 00:21:12,370
Que temos ponteiros,
que temos malloc,

454
00:21:12,370 --> 00:21:15,680
que temos a capacidade de criar
pedaços de memória para nós mesmos

455
00:21:15,680 --> 00:21:16,344
dinamicamente.

456
00:21:16,344 --> 00:21:18,510
Portanto, esta é uma imagem que
vislumbrada apenas no outro dia.

457
00:21:18,510 --> 00:21:21,180
Nós realmente não habitará
sobre ele, mas esta imagem

458
00:21:21,180 --> 00:21:24,180
tem sido acontecendo por baixo
o capô há semanas.

459
00:21:24,180 --> 00:21:27,050
E assim isso representa, apenas
um retângulo que temos desenhado,

460
00:21:27,050 --> 00:21:28,180
a memória do seu computador.

461
00:21:28,180 --> 00:21:31,850
E talvez o seu computador, ou CS50
ID, tem um gigabyte de memória RAM ou

462
00:21:31,850 --> 00:21:33,050
ou dois gigabytes ou quatro.

463
00:21:33,050 --> 00:21:34,450
Realmente não importa.

464
00:21:34,450 --> 00:21:37,240
Seu sistema operacional
Windows ou Mac OS ou Linux,

465
00:21:37,240 --> 00:21:41,120
essencialmente permite que o programa
a pensar que ele tem acesso

466
00:21:41,120 --> 00:21:42,982
para a totalidade do
a memória do seu computador,

467
00:21:42,982 --> 00:21:45,440
mesmo que você pode estar executando
vários programas ao mesmo tempo.

468
00:21:45,440 --> 00:21:46,990
Então, na realidade, que realmente não funciona.

469
00:21:46,990 --> 00:21:49,448
Mas é tipo de uma ilusão
dado a todos os seus programas.

470
00:21:49,448 --> 00:21:53,110
Então se você tivesse dois gigas de RAM, este
É assim que o computador pode pensar nisso.

471
00:21:53,110 --> 00:21:57,110
>> Agora coincidentemente, um deles
coisas, um desses segmentos de memória,

472
00:21:57,110 --> 00:21:58,350
é chamado uma pilha.

473
00:21:58,350 --> 00:22:01,680
E, de fato qualquer momento
até agora em escrever código

474
00:22:01,680 --> 00:22:05,900
que você tem chamado a
função, por exemplo principal.

475
00:22:05,900 --> 00:22:08,410
Lembre-se que a qualquer momento eu tenho
memória tirada do computador,

476
00:22:08,410 --> 00:22:10,640
Eu sempre desenhar tipo de
metade de um retângulo aqui

477
00:22:10,640 --> 00:22:12,520
e não se incomode de falar
sobre o que está acima.

478
00:22:12,520 --> 00:22:15,980
Porque quando principal é chamado, eu reivindico
que você começa este pedaço de memória

479
00:22:15,980 --> 00:22:16,970
que vai para baixo aqui.

480
00:22:16,970 --> 00:22:20,650
E se uma função principal chamada
como swap, bem troca vai aqui.

481
00:22:20,650 --> 00:22:23,720
E ao que parece, isso é
onde ele está terminando.

482
00:22:23,720 --> 00:22:26,277
Em algo chamado uma pilha
dentro da memória do seu computador.

483
00:22:26,277 --> 00:22:28,360
Agora, no final do dia,
este é apenas aborda.

484
00:22:28,360 --> 00:22:30,680
É como byte zero,
byte um, byte 2 bilhões.

485
00:22:30,680 --> 00:22:33,130
Mas se você pensar sobre isso
como este objecto rectangular,

486
00:22:33,130 --> 00:22:35,130
tudo o que estamos fazendo a cada
vez que chamar uma função é

487
00:22:35,130 --> 00:22:37,180
estratificação uma nova fatia de memória.

488
00:22:37,180 --> 00:22:41,700
Estamos dando essa função uma fatia
da sua própria memória para trabalhar.

489
00:22:41,700 --> 00:22:44,490
>> E lembro agora que isso é importante.

490
00:22:44,490 --> 00:22:46,400
Porque se nós temos
algo como troca

491
00:22:46,400 --> 00:22:51,610
e duas variáveis ​​locais como A e B e
podemos mudar esses valores a partir de um e dois

492
00:22:51,610 --> 00:22:55,130
para dois e um, lembre-
que quando retorna permuta,

493
00:22:55,130 --> 00:22:58,330
é como se essa fatia
de memória é apenas ido.

494
00:22:58,330 --> 00:23:00,080
Na realidade, ainda é
há forense.

495
00:23:00,080 --> 00:23:01,940
E algo ainda está realmente lá.

496
00:23:01,940 --> 00:23:05,410
Mas conceitualmente, é como
embora é completamente desaparecido.

497
00:23:05,410 --> 00:23:10,910
E assim principal não sabe qualquer um dos trabalhos
que foi feito nessa função swap,

498
00:23:10,910 --> 00:23:14,890
a menos que seja realmente passou naqueles
argumentos de ponteiro ou por referência.

499
00:23:14,890 --> 00:23:17,790
Agora, a solução fundamental
para esse problema com permuta

500
00:23:17,790 --> 00:23:19,970
está passando por coisas no endereço.

501
00:23:19,970 --> 00:23:23,250
Mas ao que parece, também, o que é
vem acontecendo acima que parte

502
00:23:23,250 --> 00:23:26,330
do retângulo de todo esse tempo é
Ainda há mais memória lá em cima.

503
00:23:26,330 --> 00:23:28,790
E quando você dinamicamente
alocar a memória,

504
00:23:28,790 --> 00:23:32,020
se é dentro de GetString, que
temos vindo a fazer para você no CS50

505
00:23:32,020 --> 00:23:34,710
biblioteca, ou se vocês
chamar malloc e pedir

506
00:23:34,710 --> 00:23:37,950
o sistema operacional para um pedaço de
memória, ele não vem da pilha.

507
00:23:37,950 --> 00:23:40,960
Ele vem de outro lugar
na memória do seu computador

508
00:23:40,960 --> 00:23:42,220
que é chamado de heap.

509
00:23:42,220 --> 00:23:43,430
E isso não é diferente.

510
00:23:43,430 --> 00:23:44,285
É a mesma RAM.

511
00:23:44,285 --> 00:23:45,160
É a mesma memória.

512
00:23:45,160 --> 00:23:49,080
É apenas a memória RAM que está acima
lá em vez de descer aqui.

513
00:23:49,080 --> 00:23:50,750
>> E então o que é que isso significa?

514
00:23:50,750 --> 00:23:53,650
Bem, se o computador tiver
uma quantidade finita de memória

515
00:23:53,650 --> 00:23:57,450
ea pilha está crescendo, então
para falar, ea pilha, de acordo

516
00:23:57,450 --> 00:23:59,349
para esta seta, está crescendo para baixo.

517
00:23:59,349 --> 00:24:01,140
Em outras palavras, cada
vez que você chamar malloc,

518
00:24:01,140 --> 00:24:03,430
você está sendo dada uma fatia
de memória a partir de cima,

519
00:24:03,430 --> 00:24:06,630
em seguida, talvez um pouco mais baixo, então um pouco
inferior, cada vez que você chamar malloc,

520
00:24:06,630 --> 00:24:10,100
a pilha, é o uso,
é uma espécie de crescimento,

521
00:24:10,100 --> 00:24:11,950
crescendo cada vez mais perto para o que?

522
00:24:11,950 --> 00:24:13,382
A pilha.

523
00:24:13,382 --> 00:24:14,840
Então, isso parece ser uma boa idéia?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
Quero dizer, onde não é muito claro
o que mais você pode fazer se você só

526
00:24:22,140 --> 00:24:23,910
tem uma quantidade finita de memória.

527
00:24:23,910 --> 00:24:25,200
Mas este é certamente ruim.

528
00:24:25,200 --> 00:24:27,920
Essas duas setas estão em um
Crash Course um pelo outro.

529
00:24:27,920 --> 00:24:31,930
>> E verifica-se que cara mau, pessoas que
são particularmente bons com a programação,

530
00:24:31,930 --> 00:24:36,140
e tentando invadir computadores,
pode explorar essa realidade.

531
00:24:36,140 --> 00:24:38,290
Na verdade, vamos considerar
um pequeno trecho.

532
00:24:38,290 --> 00:24:41,350
Portanto, este é um exemplo que você pode ler
com mais detalhes na Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Nós vamos apontá-lo no
artigo se curioso.

534
00:24:43,100 --> 00:24:45,650
Mas há um ataque geral
conhecido como buffer overflow que

535
00:24:45,650 --> 00:24:49,570
tem existido durante o tempo que os seres humanos
ter tido a capacidade de manipular

536
00:24:49,570 --> 00:24:53,120
a memória do computador, especialmente em C.
Portanto, este é um programa muito arbitrária,

537
00:24:53,120 --> 00:24:55,130
mas vamos lê-lo de baixo para cima.

538
00:24:55,130 --> 00:24:57,650
Principal em ARGC carvão estrela argv.

539
00:24:57,650 --> 00:24:59,830
Portanto, é um programa que tira
argumentos de linha de comando.

540
00:24:59,830 --> 00:25:03,620
E tudo principal é que, aparentemente, é chamada
uma função, chamá-lo de F pela simplicidade.

541
00:25:03,620 --> 00:25:04,610
E ele passa em quê?

542
00:25:04,610 --> 00:25:05,490
ArGV de um.

543
00:25:05,490 --> 00:25:09,320
Então, ele passa para o que quer que F
a palavra é que o usuário digitou

544
00:25:09,320 --> 00:25:11,500
no prompt após a
nome do programa em tudo.

545
00:25:11,500 --> 00:25:15,730
Tanto como César ou Vigenere, que
você pode se lembrar fazendo com argv.

546
00:25:15,730 --> 00:25:16,680
>> Então, o que é F?

547
00:25:16,680 --> 00:25:19,760
F leva em uma string
como seu único argumento,

548
00:25:19,760 --> 00:25:22,100
AKA uma estrela char, mesmo
coisa, como uma string.

549
00:25:22,100 --> 00:25:24,920
E ele é chamado arbitrariamente
bar no presente exemplo.

550
00:25:24,920 --> 00:25:27,710
E depois de char c 12,
apenas em termos leigos,

551
00:25:27,710 --> 00:25:31,750
o que é char c suporte de 12 fazendo por nós?

552
00:25:31,750 --> 00:25:33,440
O que ele faz?

553
00:25:33,440 --> 00:25:36,490
A alocação de memória, especificamente
12 bytes para 12 caracteres.

554
00:25:36,490 --> 00:25:36,990
Exatamente.

555
00:25:36,990 --> 00:25:40,000
E então a última linha, mexa e
cópia, você provavelmente não vi.

556
00:25:40,000 --> 00:25:43,360
Esta é uma cópia cadeia
função cujo propósito na vida

557
00:25:43,360 --> 00:25:48,160
é copiar seu segundo argumento
em seu primeiro argumento,

558
00:25:48,160 --> 00:25:51,190
mas apenas até um
certo número de bytes.

559
00:25:51,190 --> 00:25:53,860
Assim, o terceiro argumento diz,
quantos bytes você deve copiar?

560
00:25:53,860 --> 00:25:56,720
O comprimento da barra,
tudo o que o usuário digitou.

561
00:25:56,720 --> 00:25:59,320
E os conteúdos de
Bar, essa seqüência, são

562
00:25:59,320 --> 00:26:02,330
copiada para a memória apontada para a C.

563
00:26:02,330 --> 00:26:04,060
>> Então, isso parece meio idiota, e é.

564
00:26:04,060 --> 00:26:06,300
É um exemplo artificial,
mas é representante

565
00:26:06,300 --> 00:26:10,100
de uma classe de vectores de ataque,
uma forma de atacar um programa.

566
00:26:10,100 --> 00:26:15,050
Tudo está bem e bom se o usuário
tipos em uma palavra que é 11 caracteres

567
00:26:15,050 --> 00:26:18,040
ou menos, mais a barra invertida zero.

568
00:26:18,040 --> 00:26:22,830
E se o usuário digita em mais de
11 ou 12 ou 20 ou 50 caracteres?

569
00:26:22,830 --> 00:26:25,090
O que é este programa vai fazer?

570
00:26:25,090 --> 00:26:29,360
Falha potencialmente seg. Vai
para copiar cegamente tudo no bar-se

571
00:26:29,360 --> 00:26:31,750
ao seu comprimento, que é
literalmente tudo no bar,

572
00:26:31,750 --> 00:26:36,307
para o endereço apontado pelo C. Mas C
só preventivamente dada como 12 bytes.

573
00:26:36,307 --> 00:26:37,640
Mas não há nenhuma verificação adicional.

574
00:26:37,640 --> 00:26:38,700
Não há nenhum caso as condições.

575
00:26:38,700 --> 00:26:40,580
Não há nenhuma verificação de erros aqui.

576
00:26:40,580 --> 00:26:43,270
>> E então o que este programa é
vai fazer é apenas cega

577
00:26:43,270 --> 00:26:45,750
copiar uma coisa à outra.

578
00:26:45,750 --> 00:26:47,880
E assim se desenhar esse
como uma imagem, é aqui

579
00:26:47,880 --> 00:26:49,860
apenas uma pequena parte do espaço de memória.

580
00:26:49,860 --> 00:26:53,470
Então, observe na parte inferior, nós
têm o bar variável local.

581
00:26:53,470 --> 00:26:57,330
Então, esse ponteiro que vai store--
vez que o argumento local que é

582
00:26:57,330 --> 00:26:58,672
indo para armazenar a barra de string.

583
00:26:58,672 --> 00:27:00,380
Em seguida, observe apenas
acima dela numa pilha,

584
00:27:00,380 --> 00:27:02,505
porque cada vez que você perguntar
para memória na pilha,

585
00:27:02,505 --> 00:27:04,310
ele vai um pouco
acima, pictorially,

586
00:27:04,310 --> 00:27:06,270
aviso de que temos 12 bytes lá.

587
00:27:06,270 --> 00:27:10,690
A de cima esquerda é zero e suporte C
o certo é inferior C suporte 11.

588
00:27:10,690 --> 00:27:12,870
Isso é apenas a forma como os computadores
indo para colocá-lo fora.

589
00:27:12,870 --> 00:27:18,300
Então, só intuitivamente, se bar tem mais
de 12 caracteres no total, incluindo

590
00:27:18,300 --> 00:27:25,790
a barra invertida zero, onde está o
12 ou o suporte de C 12 indo para ir?

591
00:27:25,790 --> 00:27:28,440
Ou melhor, onde é o 12º
personagem ou o personagem 13th,

592
00:27:28,440 --> 00:27:30,900
o personagem vai centésimo
para acabar na foto?

593
00:27:30,900 --> 00:27:33,400
Acima ou abaixo?

594
00:27:33,400 --> 00:27:36,300
>> Certo, porque embora
a própria pilha cresce para cima,

595
00:27:36,300 --> 00:27:39,590
uma vez que você colocar as coisas em
ele, por razões de concepção,

596
00:27:39,590 --> 00:27:41,294
coloca a memória de cima para baixo.

597
00:27:41,294 --> 00:27:44,460
Então, se você tem mais de 12 bytes,
você vai começar a substituir bar.

598
00:27:44,460 --> 00:27:47,280
Agora que é um erro, mas é
não é realmente um grande negócio.

599
00:27:47,280 --> 00:27:51,130
Mas é um grande negócio, porque há
mais coisas acontecendo na memória.

600
00:27:51,130 --> 00:27:53,074
Então aqui está como nós pudemos
colocar Olá, para ser claro.

601
00:27:53,074 --> 00:27:54,490
Se eu digitei Olá no prompt.

602
00:27:54,490 --> 00:27:59,330
Barra invertida zero, H-E-L-L-O, acaba por dentro
esses 12 bytes, e estamos super seguro.

603
00:27:59,330 --> 00:28:00,330
Tudo está bem.

604
00:28:00,330 --> 00:28:03,020
Mas se eu digitar algo
mais longo, que é potencialmente

605
00:28:03,020 --> 00:28:05,860
vai rastejar para o espaço bar.

606
00:28:05,860 --> 00:28:08,405
Mas, pior ainda, verifica-se
fora todo esse tempo,

607
00:28:08,405 --> 00:28:11,530
embora nós nunca conversamos sobre
que, a pilha é usada para outras coisas.

608
00:28:11,530 --> 00:28:13,560
Não são apenas as variáveis ​​locais.

609
00:28:13,560 --> 00:28:15,100
>> C é uma linguagem de nível muito baixo.

610
00:28:15,100 --> 00:28:17,810
E que tipo de segredo
utiliza também a pilha

611
00:28:17,810 --> 00:28:21,260
para recordar quando um
função é chamada, o que

612
00:28:21,260 --> 00:28:26,040
é o endereço da função anterior,
assim que pode saltar de volta para essa função.

613
00:28:26,040 --> 00:28:29,980
Então, quando as chamadas principais trocar, entre
as coisas empurrado para a pilha

614
00:28:29,980 --> 00:28:34,380
não são apenas troca variáveis ​​locais,
ou seus argumentos, também empurrou secretamente

615
00:28:34,380 --> 00:28:37,510
para a pilha como representado
pela fatia vermelho aqui,

616
00:28:37,510 --> 00:28:40,520
é o endereço do principal fisicamente
na memória do seu computador,

617
00:28:40,520 --> 00:28:44,180
de modo que quando é feito de permuta, o computador
sabe que eu preciso para voltar ao principal

618
00:28:44,180 --> 00:28:46,760
e terminar de executar a função principal.

619
00:28:46,760 --> 00:28:51,960
Então, isso é perigoso agora, porque se
o usuário digita bem mais do que Olá,

620
00:28:51,960 --> 00:28:57,030
de tal modo que a entrada do usuário clobbers
ou substitui essa seção vermelho,

621
00:28:57,030 --> 00:28:59,820
logicamente, se do computador
só vai assumir cegamente

622
00:28:59,820 --> 00:29:03,830
em que os bytes que são fatia vermelho
o endereço para o qual ele deve retornar,

623
00:29:03,830 --> 00:29:09,020
e se o adversário é inteligente o suficiente ou
sorte o suficiente para colocar uma seqüência de bytes

624
00:29:09,020 --> 00:29:13,450
há que se parece com um endereço,
mas é o endereço de código

625
00:29:13,450 --> 00:29:18,730
que ele ou ela quer o computador
para executar em vez de principal?

626
00:29:18,730 --> 00:29:21,670
>> Em outras palavras, se o que o
usuário está digitando no prompt,

627
00:29:21,670 --> 00:29:23,850
não é apenas algo
como inócuo Olá,

628
00:29:23,850 --> 00:29:28,210
mas na verdade é um código que é equivalente
apagar todos os arquivos desse usuário?

629
00:29:28,210 --> 00:29:30,060
Ou enviar e-mail a senha para mim?

630
00:29:30,060 --> 00:29:31,940
Ou começar a registrar sua
teclas digitadas, certo?

631
00:29:31,940 --> 00:29:34,920
Há um caminho, vamos estipular hoje,
que eles poderiam escrever não apenas Olá

632
00:29:34,920 --> 00:29:36,711
mundo ou seu nome,
que podiam essencialmente

633
00:29:36,711 --> 00:29:39,570
passar em código, e zeros
aqueles, que o computador

634
00:29:39,570 --> 00:29:43,450
erros de código e um endereço.

635
00:29:43,450 --> 00:29:48,950
Assim, embora um pouco abstrata, se o
usuário digita o código contraditório suficiente

636
00:29:48,950 --> 00:29:52,330
que vamos generalizar aqui como
A. Uma é o ataque ou adversários.

637
00:29:52,330 --> 00:29:53,140
Então, só coisas ruins.

638
00:29:53,140 --> 00:29:55,306
Nós não nos importamos sobre a
números ou os zeros ou aqueles

639
00:29:55,306 --> 00:29:59,470
hoje, de tal forma que você acaba
sobrescrevendo essa seção vermelho,

640
00:29:59,470 --> 00:30:01,580
notar que seqüência de bytes.

641
00:30:01,580 --> 00:30:05,020
O 835 C de zero oito zero.

642
00:30:05,020 --> 00:30:08,960
E agora, como artigo de Wikipedia aqui
propôs, se você realmente começar agora

643
00:30:08,960 --> 00:30:12,460
rotular os bytes em seu computador de
memória, o que o artigo é Wikipedia

644
00:30:12,460 --> 00:30:19,060
propondo é que, o que se o endereço
de que byte superior esquerdo é de 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Em outras palavras, se o cara é ruim
inteligente o suficiente com o seu código

646
00:30:22,200 --> 00:30:26,650
para realmente colocar um número aqui que
corresponde ao endereço do código

647
00:30:26,650 --> 00:30:29,180
ele ou ela injectado
no computador, você

648
00:30:29,180 --> 00:30:31,050
pode enganar o computador
a fazer qualquer coisa.

649
00:30:31,050 --> 00:30:34,140
A remoção de arquivos, e-mail
coisas, farejando o seu tráfego,

650
00:30:34,140 --> 00:30:36,710
literalmente qualquer coisa poderia ser
injectado no computador.

651
00:30:36,710 --> 00:30:39,220
E assim por um estouro de buffer
ataque em seu núcleo

652
00:30:39,220 --> 00:30:43,530
é apenas um estúpido, estúpido
imperiosa de uma matriz que

653
00:30:43,530 --> 00:30:45,840
não têm seus limites marcada.

654
00:30:45,840 --> 00:30:48,850
E é isso que é super perigoso
e ao mesmo tempo poderoso super

655
00:30:48,850 --> 00:30:52,560
em C é que nós realmente têm
acesso a qualquer lugar da memória.

656
00:30:52,560 --> 00:30:55,320
Cabe a nós, os programadores,
que escrevem o código original

657
00:30:55,320 --> 00:30:59,330
para verificar o comprimento danado de qualquer
matrizes que nós estamos manipulando.

658
00:30:59,330 --> 00:31:00,750
Então, para ser claro, o que é a correção?

659
00:31:00,750 --> 00:31:03,190
Se reverter para esta
código, eu não deveria apenas

660
00:31:03,190 --> 00:31:08,000
alterar o comprimento da barra, o que
mais eu deveria estar verificando?

661
00:31:08,000 --> 00:31:10,620
O que mais eu deveria estar fazendo para
evitar este ataque inteiramente?

662
00:31:10,620 --> 00:31:14,110
Eu não quero dizer apenas cega
que você deve copiar como muitos bytes

663
00:31:14,110 --> 00:31:16,140
como é o comprimento da barra.

664
00:31:16,140 --> 00:31:18,910
Eu quero dizer, como copiar
muitos bytes como estão em bar

665
00:31:18,910 --> 00:31:24,090
até o alocado
memória, ou 12 no máximo.

666
00:31:24,090 --> 00:31:27,450
Então eu preciso de algum tipo de condição if
que faz verificar o comprimento da barra,

667
00:31:27,450 --> 00:31:32,800
mas se for superior a 12, nós código apenas difícil
12 como a distância máxima possível.

668
00:31:32,800 --> 00:31:35,910
Caso contrário, o chamado tampão
ataque de estouro pode acontecer.

669
00:31:35,910 --> 00:31:38,451
Na parte inferior das referidas lâminas,
Se você está curioso para ler mais

670
00:31:38,451 --> 00:31:41,200
é o artigo original real
se você gostaria de dar uma olhada.

671
00:31:41,200 --> 00:31:44,550
>> Mas agora, entre os preços
pago aqui foi ineficiências.

672
00:31:44,550 --> 00:31:46,680
Então isso foi um rápido
olhar baixo nível em que

673
00:31:46,680 --> 00:31:49,709
podem surgir problemas agora que nós
têm acesso a memória do computador.

674
00:31:49,709 --> 00:31:51,750
Mas um outro problema que
já tropeçou nesta segunda-feira

675
00:31:51,750 --> 00:31:53,800
era apenas a ineficiência
de uma lista ligada.

676
00:31:53,800 --> 00:31:56,019
Estamos de volta ao tempo linear.

677
00:31:56,019 --> 00:31:57,560
Nós já não temos uma matriz contígua.

678
00:31:57,560 --> 00:31:58,980
Não temos acesso aleatório.

679
00:31:58,980 --> 00:32:00,710
Nós não podemos usar a notação de colchete.

680
00:32:00,710 --> 00:32:04,590
Nós, literalmente, tem que usar um loop while
como a que eu escrevi há pouco.

681
00:32:04,590 --> 00:32:09,740
Mas na segunda-feira, que alegou que pudermos
rastejar de volta para o reino da eficiência

682
00:32:09,740 --> 00:32:13,040
alcançar algo que é
logarítmica talvez, ou melhor ainda,

683
00:32:13,040 --> 00:32:16,120
talvez até mesmo algo que é
o chamado tempo constante.

684
00:32:16,120 --> 00:32:19,840
Então, como podemos fazer isso usando estes novos
ferramentas, esses endereços, esses ponteiros,

685
00:32:19,840 --> 00:32:22,210
e enfiar coisas da nossa própria?

686
00:32:22,210 --> 00:32:23,960
Bem, suponha que
aqui, estes são um bando

687
00:32:23,960 --> 00:32:27,170
de números que queremos armazenar em um
estrutura de dados de forma eficiente e de busca.

688
00:32:27,170 --> 00:32:30,960
Podemos absolutamente rebobinar a semana
dois, jogá-los em uma matriz,

689
00:32:30,960 --> 00:32:33,150
e pesquisá-los usando pesquisa binária.

690
00:32:33,150 --> 00:32:34,040
Dividir e conquistar.

691
00:32:34,040 --> 00:32:37,720
E, de fato você escreveu
busca binária em PSET3,

692
00:32:37,720 --> 00:32:40,100
onde você implementou o programa find.

693
00:32:40,100 --> 00:32:40,890
Mas você sabe o quê.

694
00:32:40,890 --> 00:32:45,060
Há uma espécie de mais
maneira inteligente de fazer isso.

695
00:32:45,060 --> 00:32:47,390
É um pouco mais
sofisticado e talvez

696
00:32:47,390 --> 00:32:50,830
permite-nos ver porque binário
busca é muito mais rápido.

697
00:32:50,830 --> 00:32:52,980
Primeiro, vamos introduzir
a noção de uma árvore.

698
00:32:52,980 --> 00:32:54,730
Que, embora em
realidade tipo de árvores

699
00:32:54,730 --> 00:32:57,730
crescer como este, no mundo de computador
ciência que tipo de crescer para baixo

700
00:32:57,730 --> 00:33:00,830
como uma árvore de família, onde você tem
seus avós ou bisavós

701
00:33:00,830 --> 00:33:04,580
ou outros enfeites no topo, o patriarca e
a matriarca da família, apenas um

702
00:33:04,580 --> 00:33:07,930
chamada raiz, nó, abaixo
que são as suas crianças,

703
00:33:07,930 --> 00:33:11,442
abaixo da qual estão os seus filhos, ou
seus descendentes em geral.

704
00:33:11,442 --> 00:33:13,400
E qualquer um que pendura fora
a parte inferior da família

705
00:33:13,400 --> 00:33:16,070
árvore, além de ser a
caçula da família,

706
00:33:16,070 --> 00:33:19,520
também pode ser apenas genericamente
chamado as folhas da árvore.

707
00:33:19,520 --> 00:33:21,800
>> Portanto, este é apenas um bando
de palavras e definições

708
00:33:21,800 --> 00:33:25,790
para algo chamado de uma árvore no computador
ciência, bem como uma árvore genealógica.

709
00:33:25,790 --> 00:33:28,770
Mas há encarnações mais extravagantes
de árvores, uma das quais

710
00:33:28,770 --> 00:33:30,780
é chamada uma árvore de busca binária.

711
00:33:30,780 --> 00:33:34,380
E você pode tipo de provocação
além o que essa coisa faz.

712
00:33:34,380 --> 00:33:37,180
Bem, é binário em que sentido?

713
00:33:37,180 --> 00:33:41,455
Onde é que o binário vem daqui?

714
00:33:41,455 --> 00:33:41,955
Desculpa?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
Não é tanto um ou.

717
00:33:47,210 --> 00:33:52,000
É mais que cada um de nós não tem
mais de dois filhos, como podemos ver aqui.

718
00:33:52,000 --> 00:33:54,990
Em geral, um e tree--
seus pais e avós

719
00:33:54,990 --> 00:33:57,640
pode ter tantos filhos ou
netos como eles realmente querem,

720
00:33:57,640 --> 00:34:00,820
e assim, por exemplo, aí temos três
crianças fora desse nó mão direita,

721
00:34:00,820 --> 00:34:05,480
mas de uma árvore binária, um nó possui
zero, um ou dois filhos maximamente.

722
00:34:05,480 --> 00:34:08,496
E isso é uma propriedade agradável,
Porque se é tampado por dois,

723
00:34:08,496 --> 00:34:10,620
nós vamos ser capazes de
ficar um pouco log base dois

724
00:34:10,620 --> 00:34:11,975
ação acontecendo aqui, em última instância.

725
00:34:11,975 --> 00:34:13,350
Portanto, temos algo logarítmica.

726
00:34:13,350 --> 00:34:14,558
Mas mais sobre isso em um momento.

727
00:34:14,558 --> 00:34:19,810
Pesquisa árvore significa que os números são
disposto de tal modo que a criança esquerda do

728
00:34:19,810 --> 00:34:22,429
valor é maior do que a raiz.

729
00:34:22,429 --> 00:34:26,010
E seu filho direito é
maior do que a raiz.

730
00:34:26,010 --> 00:34:29,290
Em outras palavras, se você pegar qualquer um dos
nós, os círculos nesta imagem,

731
00:34:29,290 --> 00:34:31,840
e olha para sua esquerda
criança e seu filho direito,

732
00:34:31,840 --> 00:34:34,739
o primeiro deve ser inferior a,
o segundo deve ser maior do que.

733
00:34:34,739 --> 00:34:36,159
Então verificação de sanidade 55.

734
00:34:36,159 --> 00:34:37,780
É criança deixada é de 33.

735
00:34:37,780 --> 00:34:38,620
É menos do que.

736
00:34:38,620 --> 00:34:40,929
55, seu filho da direita é de 77.

737
00:34:40,929 --> 00:34:41,783
É maior que.

738
00:34:41,783 --> 00:34:43,199
E isso é uma definição recursiva.

739
00:34:43,199 --> 00:34:46,480
Poderíamos verificar cada um desses
nós e o mesmo padrão iria realizar.

740
00:34:46,480 --> 00:34:49,389
>> Então, o que é bom em um
árvore de busca binária, é

741
00:34:49,389 --> 00:34:52,204
esse, podemos implementá-lo
com uma estrutura, tal como este.

742
00:34:52,204 --> 00:34:54,620
E mesmo que nós estamos jogando
lotes de estruturas na sua,

743
00:34:54,620 --> 00:34:56,560
eles são um pouco
intuitiva agora esperançoso.

744
00:34:56,560 --> 00:35:00,570
A sintaxe é ainda misterioso, com certeza,
mas o conteúdo de um nó nesta

745
00:35:00,570 --> 00:35:02,786
context-- e continuamos
utilizando o nó palavra,

746
00:35:02,786 --> 00:35:04,910
se é um retângulo
na tela ou um círculo,

747
00:35:04,910 --> 00:35:08,970
é apenas alguns contêiner genérico,
Neste caso de uma árvore, como o

748
00:35:08,970 --> 00:35:11,780
vimos, precisamos de um número inteiro
em cada um dos nós

749
00:35:11,780 --> 00:35:15,460
e então eu preciso de dois ponteiros apontando
para o filho esquerdo e direito da criança,

750
00:35:15,460 --> 00:35:16,590
respectivamente.

751
00:35:16,590 --> 00:35:20,730
Então é assim que nós pudemos
implementar isso em um struct.

752
00:35:20,730 --> 00:35:22,315
E como eu poderia implementá-lo em código?

753
00:35:22,315 --> 00:35:26,730
Bem, vamos dar uma rápida
olhar para este pequeno exemplo.

754
00:35:26,730 --> 00:35:29,820
Não é funcional, mas eu tenho
copiado e colado essa estrutura.

755
00:35:29,820 --> 00:35:33,510
E se a minha função para um binário
árvore de busca é chamado de busca,

756
00:35:33,510 --> 00:35:36,980
e isso leva dois argumentos,
um N de número inteiro e um ponteiro

757
00:35:36,980 --> 00:35:41,400
para um nó, de modo que um ponteiro para a árvore
ou um ponteiro para a raiz de uma árvore,

758
00:35:41,400 --> 00:35:43,482
como faço para ir sobre como procurar N?

759
00:35:43,482 --> 00:35:45,440
Bem, em primeiro lugar, porque eu sou
lidar com ponteiros,

760
00:35:45,440 --> 00:35:46,750
Eu vou fazer um teste de sanidade.

761
00:35:46,750 --> 00:35:54,279
Se iguais árvore é igual a zero, é N
nesta árvore ou não nesta árvore?

762
00:35:54,279 --> 00:35:55,070
Não pode ser, certo?

763
00:35:55,070 --> 00:35:56,870
Se eu sou passado null,
não há nada lá.

764
00:35:56,870 --> 00:35:59,230
Eu poderia muito bem apenas
cegamente dizer return false.

765
00:35:59,230 --> 00:36:04,050
Se você me der nada, eu certamente não posso
encontrar qualquer número N. Então, o que mais eu poderia

766
00:36:04,050 --> 00:36:04,750
verifique agora?

767
00:36:04,750 --> 00:36:12,830
Eu vou dizer bem else if N é
menos do que o que está no nó de árvore

768
00:36:12,830 --> 00:36:16,300
que eu tenho valor N entregou.

769
00:36:16,300 --> 00:36:20,270
Em outras palavras, se o número eu sou
procurando, n, for menor do que o nó

770
00:36:20,270 --> 00:36:21,340
que eu estou olhando.

771
00:36:21,340 --> 00:36:23,190
E o nó que estou procurando
a árvore é chamado,

772
00:36:23,190 --> 00:36:26,370
e lembrar do exemplo anterior
para obter o valor em um ponteiro,

773
00:36:26,370 --> 00:36:28,310
Eu uso a notação de seta.

774
00:36:28,310 --> 00:36:35,960
Portanto, se N é inferior a seta árvore
N, eu quero ir conceitualmente esquerda.

775
00:36:35,960 --> 00:36:38,590
Como posso expressar searching esquerda?

776
00:36:38,590 --> 00:36:41,560
Para ser claro, se este for
a imagem em questão,

777
00:36:41,560 --> 00:36:44,612
e eu tenho que passou de nível superior
arrow que está apontando para baixo.

778
00:36:44,612 --> 00:36:45,570
Esse é o meu ponteiro árvore.

779
00:36:45,570 --> 00:36:48,060
Eu estou apontando para a raiz da árvore.

780
00:36:48,060 --> 00:36:52,100
E eu estou olhando por exemplo, para
o número 44, de forma arbitrária.

781
00:36:52,100 --> 00:36:55,300
44 é inferior ou
superior a 55, obviamente,?

782
00:36:55,300 --> 00:36:56,360
Por isso é menos do que.

783
00:36:56,360 --> 00:36:58,760
E assim este se condição se aplica.

784
00:36:58,760 --> 00:37:03,981
Assim, conceitualmente, o que eu quero
procurar seguinte se eu estou procurando 44?

785
00:37:03,981 --> 00:37:04,480
Sim?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Exatamente, eu quero
procurar o filho esquerdo,

788
00:37:11,100 --> 00:37:12,789
ou a sub-árvore à esquerda da imagem.

789
00:37:12,789 --> 00:37:14,830
E, na verdade, deixe-me através de
a foto aqui

790
00:37:14,830 --> 00:37:17,770
por apenas um momento, uma vez que
Eu não posso arranhar isso.

791
00:37:17,770 --> 00:37:21,150
Se eu começar aqui em 55, e
Eu sei que o valor 44

792
00:37:21,150 --> 00:37:23,180
Eu estou procurando é a
à esquerda, é uma espécie

793
00:37:23,180 --> 00:37:26,010
de como rasgar o livro de telefone em
metade ou rasgar a árvore no meio.

794
00:37:26,010 --> 00:37:29,660
Eu já não precisa se preocupar com
toda esta metade da árvore.

795
00:37:29,660 --> 00:37:33,270
E, no entanto, curiosamente, em termos de
estrutura, esta coisa aqui que

796
00:37:33,270 --> 00:37:36,682
inicia-se com 33, que se
é uma árvore de busca binária.

797
00:37:36,682 --> 00:37:39,890
Eu disse a palavra recursiva antes porque
Na verdade, esta é uma estrutura de dados que

798
00:37:39,890 --> 00:37:41,707
por definição é recursiva.

799
00:37:41,707 --> 00:37:44,540
Você pode ter uma árvore que é isso
grande, mas cada um de seus filhos

800
00:37:44,540 --> 00:37:46,870
representa uma árvore apenas um pouco menor.

801
00:37:46,870 --> 00:37:50,910
Ao invés de ser vovô
ou a avó, agora é só mãe

802
00:37:50,910 --> 00:37:54,300
ou-- Eu não posso não dizer-- mãe
ou pai, que seria estranho.

803
00:37:54,300 --> 00:37:59,000
Em vez das duas crianças lá
seria como irmão e irmã.

804
00:37:59,000 --> 00:38:01,120
A nova geração da árvore genealógica.

805
00:38:01,120 --> 00:38:02,900
Mas estruturalmente, é a mesma idéia.

806
00:38:02,900 --> 00:38:06,790
E acontece que eu tenho uma função
com o qual eu posso procurar uma pesquisa binária

807
00:38:06,790 --> 00:38:07,290
árvore.

808
00:38:07,290 --> 00:38:08,680
Ele é chamado de busca.

809
00:38:08,680 --> 00:38:17,870
I procurar N na árvore seta para a esquerda
outro se n for maior do que o valor

810
00:38:17,870 --> 00:38:18,870
que eu sou atualmente.

811
00:38:18,870 --> 00:38:20,800
55 na história um momento atrás.

812
00:38:20,800 --> 00:38:23,780
Eu tenho uma função chamada
pesquisa que eu posso apenas

813
00:38:23,780 --> 00:38:29,660
N passar isso e procurar de forma recursiva
a sub-árvore e apenas retorno

814
00:38:29,660 --> 00:38:30,620
qualquer que seja a resposta.

815
00:38:30,620 --> 00:38:33,530
Outra coisa que eu tenho algum caso base final aqui.

816
00:38:33,530 --> 00:38:35,310
>> O que é o caso final?

817
00:38:35,310 --> 00:38:36,570
Árvore ou é nulo.

818
00:38:36,570 --> 00:38:39,980
O valor que eu tanto estou procurando é
menos do que ou maior do que aquela

819
00:38:39,980 --> 00:38:42,610
ou igual ao mesmo.

820
00:38:42,610 --> 00:38:44,750
E eu poderia dizer igual
igual, mas logicamente é

821
00:38:44,750 --> 00:38:46,500
equivalente a apenas dizendo outra coisa aqui.

822
00:38:46,500 --> 00:38:49,150
Tanto é verdade como eu encontrar alguma coisa.

823
00:38:49,150 --> 00:38:51,710
Portanto, esperamos que esta é uma
mesmo exemplo mais atraente

824
00:38:51,710 --> 00:38:54,900
do que a função sigma estúpido
fizemos algumas palestras para trás,

825
00:38:54,900 --> 00:38:58,360
onde era tão fácil de usar um loop
para contar todos os números de um

826
00:38:58,360 --> 00:39:02,390
a N. aqui com uma estrutura de dados
que em si é recursivamente

827
00:39:02,390 --> 00:39:07,050
definido e de forma recursiva desenhada, agora nós
têm a capacidade de nos expressarmos

828
00:39:07,050 --> 00:39:09,780
no código que em si é recursiva.

829
00:39:09,780 --> 00:39:12,580
Portanto, este é exatamente o mesmo código aqui.

830
00:39:12,580 --> 00:39:14,400
>> Então, o que os outros problemas que podemos resolver?

831
00:39:14,400 --> 00:39:18,160
Então, um passo rápido longe de
árvores para apenas um momento.

832
00:39:18,160 --> 00:39:20,130
Aqui é, digamos, a bandeira alemã.

833
00:39:20,130 --> 00:39:22,020
E há claramente um
padrão para esta bandeira.

834
00:39:22,020 --> 00:39:23,811
E há muita
bandeiras do mundo que

835
00:39:23,811 --> 00:39:27,560
são tão simples como isso em termos
das suas cores e padrões.

836
00:39:27,560 --> 00:39:31,930
Mas suponhamos que esta é armazenada como um
.GIF, Ou um JPEG ou bitmap, ou um ping,

837
00:39:31,930 --> 00:39:34,240
qualquer formato de arquivo gráfico
com o qual você está familiarizado,

838
00:39:34,240 --> 00:39:36,460
alguns dos quais nós somos
brincando com em PSet4.

839
00:39:36,460 --> 00:39:41,550
Isso não parece valer a pena para armazenar
pixel preto, pixel preto, pixel preto,

840
00:39:41,550 --> 00:39:44,790
ponto, ponto, ponto, um monte de
pixels pretos para a primeira linha de varredura,

841
00:39:44,790 --> 00:39:47,430
ou linha, em seguida, um grupo inteiro de
a mesma, em seguida, um grupo inteiro

842
00:39:47,430 --> 00:39:49,530
do mesmo, e, em seguida, uma
todo grupo de pixels vermelhos,

843
00:39:49,530 --> 00:39:53,020
pixels vermelhos, pixels vermelhos, em seguida, um todo
punhado de pixels amarelo, amarelo, certo?

844
00:39:53,020 --> 00:39:55,050
>> Não há tal ineficiência aqui.

845
00:39:55,050 --> 00:39:59,040
Como é que você intuitivamente
comprimir a bandeira alemã

846
00:39:59,040 --> 00:40:01,320
se implementá-lo como um arquivo?

847
00:40:01,320 --> 00:40:04,940
Como o que informação pode não
incomodar o armazenamento em disco em ordem

848
00:40:04,940 --> 00:40:08,040
para diminuir o nosso tamanho do arquivo de como
um megabyte de um kilobyte, algo

849
00:40:08,040 --> 00:40:09,430
menor?

850
00:40:09,430 --> 00:40:13,130
Onde reside a redundância
aqui para ser claro?

851
00:40:13,130 --> 00:40:13,880
O que você poderia fazer?

852
00:40:13,880 --> 00:40:14,380
Sim?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Exatamente.

855
00:40:21,970 --> 00:40:24,550
Por que não, em vez de se lembrar
a cor de cada pixel danado

856
00:40:24,550 --> 00:40:28,200
assim como você está fazendo em PSet4
com o formato de arquivo de bitmap,

857
00:40:28,200 --> 00:40:32,060
por que você não apenas representar a
coluna mais à esquerda de pixels, por exemplo

858
00:40:32,060 --> 00:40:35,370
um monte de pixels pretos, um grupo
de vermelho, e um monte de amarelo,

859
00:40:35,370 --> 00:40:39,210
e depois é só alguma forma codificar o
idéia de repetir este 100 vezes

860
00:40:39,210 --> 00:40:41,020
ou repetir isto 1.000 vezes?

861
00:40:41,020 --> 00:40:43,430
Onde é 100 ou 1000
apenas um número inteiro, para que

862
00:40:43,430 --> 00:40:47,290
pode começar afastado com apenas um único número
em vez de centenas ou milhares

863
00:40:47,290 --> 00:40:48,270
pixels de adicionais.

864
00:40:48,270 --> 00:40:50,990
E, de fato, é assim que
poderia comprimir a bandeira alemã.

865
00:40:50,990 --> 00:40:51,490
E

866
00:40:51,490 --> 00:40:53,470
Agora o que acontece com a bandeira francesa?

867
00:40:53,470 --> 00:40:58,930
E um pouco de algum tipo de
exercício mental, que flag

868
00:40:58,930 --> 00:41:01,040
pode ser comprimida mais no disco?

869
00:41:01,040 --> 00:41:05,720
A bandeira alemão ou francês
bandeira, se levarmos essa abordagem?

870
00:41:05,720 --> 00:41:08,490
A bandeira alemão, porque não há
mais redundância horizontal.

871
00:41:08,490 --> 00:41:12,190
E pelo design, muitos arquivos gráfico
formatos de fato trabalhar como linhas de varredura

872
00:41:12,190 --> 00:41:12,830
horizontalmente.

873
00:41:12,830 --> 00:41:14,674
Eles poderiam trabalhar
verticalmente, basta humanidade

874
00:41:14,674 --> 00:41:17,090
anos atrás decidiu que vamos
Geralmente pensamos em coisas fileira

875
00:41:17,090 --> 00:41:18,880
por linha em vez de coluna por coluna.

876
00:41:18,880 --> 00:41:20,820
Então, na verdade, se você fosse
olhar para o arquivo

877
00:41:20,820 --> 00:41:24,670
tamanho de uma bandeira alemã e uma francesa
bandeira, desde que a resolução é

878
00:41:24,670 --> 00:41:27,530
a mesma, a mesma largura
e altura, este

879
00:41:27,530 --> 00:41:31,580
aqui vai ser maior, porque você
tem que repetir-se três vezes.

880
00:41:31,580 --> 00:41:35,570
Você tem que especificar azul, repita
-se, branco, repita-se, vermelho,

881
00:41:35,570 --> 00:41:36,740
repetir-se.

882
00:41:36,740 --> 00:41:39,000
Você não pode simplesmente ir tudo
o caminho para a direita.

883
00:41:39,000 --> 00:41:41,200
E como um lado, para fazer
desmarque a compressão

884
00:41:41,200 --> 00:41:43,910
está em toda parte, se estas são
quatro quadros de uma video-- você

885
00:41:43,910 --> 00:41:45,890
deve se lembrar que um filme
ou de vídeo é geralmente

886
00:41:45,890 --> 00:41:47,286
como 29 ou 30 quadros por segundo.

887
00:41:47,286 --> 00:41:50,410
É como um pouco flip book, onde
basta ver imagem, imagem, imagem, imagem,

888
00:41:50,410 --> 00:41:54,410
imagem apenas super rápido assim que olha como
os atores na tela estão se movendo.

889
00:41:54,410 --> 00:41:57,130
Aqui está uma abelha do bumble em
cima de um ramo de flores.

890
00:41:57,130 --> 00:41:59,790
E embora possa ser uma espécie de
difícil de ver à primeira vista,

891
00:41:59,790 --> 00:42:04,020
a única coisa que se deslocam em
este filme é a abelha.

892
00:42:04,020 --> 00:42:06,880
>> O que é mudo sobre o armazenamento
vídeo não comprimido?

893
00:42:06,880 --> 00:42:11,420
É uma espécie de um desperdício para armazenar vídeo
como quatro imagens que quase idênticos

894
00:42:11,420 --> 00:42:13,670
diferem apenas na medida em que a abelha é.

895
00:42:13,670 --> 00:42:16,280
Você pode jogar fora mais
de que as informações

896
00:42:16,280 --> 00:42:20,190
e lembre-se somente, por exemplo,
o primeiro quadro eo último quadro,

897
00:42:20,190 --> 00:42:22,180
quadros-chave se você
já ouviu a palavra,

898
00:42:22,180 --> 00:42:24,337
e apenas armazenar no
meio, onde a abelha é.

899
00:42:24,337 --> 00:42:26,170
E você não tem que
armazenar todo o rosa,

900
00:42:26,170 --> 00:42:28,330
eo azul, ea
valores verdes também.

901
00:42:28,330 --> 00:42:31,200
Portanto, esta é apenas a dizer que
compressão está em toda parte.

902
00:42:31,200 --> 00:42:34,900
É uma técnica muitas vezes usamos
ou exame para concedido nestes dias.

903
00:42:34,900 --> 00:42:38,750
>> Mas como você comprimir texto?

904
00:42:38,750 --> 00:42:40,450
Como você vai fazer sobre a compressão de texto?

905
00:42:40,450 --> 00:42:45,410
Bem, cada um dos personagens em
Ascii é um byte, ou oito bits.

906
00:42:45,410 --> 00:42:47,360
E isso é meio idiota, certo?

907
00:42:47,360 --> 00:42:51,160
Porque você provavelmente tipo A
e E e I e O e U muito

908
00:42:51,160 --> 00:42:55,270
mais frequentemente do que como W ou Q ou Z,
dependendo do idioma em que

909
00:42:55,270 --> 00:42:56,610
você está escrevendo certamente.

910
00:42:56,610 --> 00:42:59,600
E então por que estamos usando
oito bits para cada letra,

911
00:42:59,600 --> 00:43:02,040
incluindo a menos
letras populares, certo?

912
00:43:02,040 --> 00:43:05,300
Por que não usar menos bits para
as letras super popular,

913
00:43:05,300 --> 00:43:07,760
E como, as coisas que você adivinhar
pela primeira vez em Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
e usar mais bits para
as letras menos populares?

915
00:43:10,450 --> 00:43:10,950
Por quê?

916
00:43:10,950 --> 00:43:13,130
Porque nós apenas estamos indo para
usá-los com menos freqüência.

917
00:43:13,130 --> 00:43:15,838
>> Bem, acontece que não têm
tentativas de fazer isso sido.

918
00:43:15,838 --> 00:43:18,630
E se você se lembra de grau
escola ou colégio, código Morse.

919
00:43:18,630 --> 00:43:20,400
Código Morse tem pontos
e traços que pode ser

920
00:43:20,400 --> 00:43:24,270
transmitido ao longo de um fio conforme
sons ou sinais de algum tipo.

921
00:43:24,270 --> 00:43:25,930
Mas o código Morse é um super limpo.

922
00:43:25,930 --> 00:43:29,010
É uma espécie de um sistema binário em
que você tem pontos ou traços.

923
00:43:29,010 --> 00:43:30,977
Mas se você ver, por exemplo, dois pontos.

924
00:43:30,977 --> 00:43:33,810
Ou se você acha que volta para o operador
que vai como bip, bip, bip,

925
00:43:33,810 --> 00:43:36,760
beep, atingindo um pouco gatilho
que transmite um sinal,

926
00:43:36,760 --> 00:43:40,360
se você, o destinatário, recebe dois
pontos, qual a mensagem que você recebeu?

927
00:43:40,360 --> 00:43:43,490
Completamente arbitrária.

928
00:43:43,490 --> 00:43:44,450
>> EU?

929
00:43:44,450 --> 00:43:45,060
EU?

930
00:43:45,060 --> 00:43:47,500
Ou o que about-- ou eu?

931
00:43:47,500 --> 00:43:49,570
Talvez fosse apenas dois à direita de E?

932
00:43:49,570 --> 00:43:52,480
Portanto, não há esse problema
de Decodificação com Morse

933
00:43:52,480 --> 00:43:54,890
código, por meio de que a menos que o
pessoa que enviou a mensagem

934
00:43:54,890 --> 00:43:59,510
na verdade, faz uma pausa para que você possa classificar de
ver ou ouvir as lacunas entre as letras,

935
00:43:59,510 --> 00:44:02,990
não é suficiente apenas para
enviar um fluxo de zeros e uns,

936
00:44:02,990 --> 00:44:05,610
ou pontos e traços,
porque não há ambigüidade.

937
00:44:05,610 --> 00:44:08,640
E é um único ponto, por isso, se você
ver dois pontos ou ouvir dois pontos,

938
00:44:08,640 --> 00:44:11,254
talvez seja dois e de ou talvez seja uma I.

939
00:44:11,254 --> 00:44:13,670
Então, precisamos de um sistema que é um
pouco mais inteligente do que isso.

940
00:44:13,670 --> 00:44:16,851
Então um homem chamado Huffman anos
atrás veio com exatamente isso.

941
00:44:16,851 --> 00:44:18,600
Então, nós apenas estamos indo
para tomar um rápido olhar

942
00:44:18,600 --> 00:44:20,114
a forma como as árvores são pertinentes a esta.

943
00:44:20,114 --> 00:44:22,530
Suponha que esta é uma
estúpido mensagem que deseja enviar,

944
00:44:22,530 --> 00:44:26,342
composto por apenas A, B, C de D's e E do,
mas há um monte de redundância aqui.

945
00:44:26,342 --> 00:44:27,550
Isso não deveria ser Inglês.

946
00:44:27,550 --> 00:44:28,341
Não é criptografado.

947
00:44:28,341 --> 00:44:30,540
É apenas uma mensagem estúpida
com muita repetição.

948
00:44:30,540 --> 00:44:34,010
Então, se você realmente contar para fora toda a
A, B de, C de, D's, e E de, aqui está

949
00:44:34,010 --> 00:44:34,890
a frequência.

950
00:44:34,890 --> 00:44:37,800
20% do que as letras sejam
Um, 45% das cartas

951
00:44:37,800 --> 00:44:39,660
E são de, e outros três freqüências.

952
00:44:39,660 --> 00:44:41,960
Contamos lá em cima manualmente
e apenas fez as contas.

953
00:44:41,960 --> 00:44:44,579
>> Assim, verifica-se que
Huffman, há algum tempo,

954
00:44:44,579 --> 00:44:46,620
percebi que, você sabe
o que, se eu começar a construir

955
00:44:46,620 --> 00:44:51,172
uma árvore ou floresta de árvores, se quiserem,
da seguinte forma, eu posso fazer o seguinte.

956
00:44:51,172 --> 00:44:53,880
Eu vou dar um nó para cada
das cartas que me interessa

957
00:44:53,880 --> 00:44:55,530
e eu estou indo para armazenar
dentro desse nó

958
00:44:55,530 --> 00:44:58,610
as freqüências como um ponto flutuante
valor, ou você pode usá-lo uma N, também,

959
00:44:58,610 --> 00:45:00,210
mas vamos apenas usar um flutuador aqui.

960
00:45:00,210 --> 00:45:03,100
E que o algoritmo
ele propôs é que você

961
00:45:03,100 --> 00:45:07,210
aproveitar esta floresta de nó único
árvores, árvores tão super curtas,

962
00:45:07,210 --> 00:45:11,920
e você começar a conectar-los com
novos grupos, pais novos, se você quiser.

963
00:45:11,920 --> 00:45:16,150
E você fazer isso escolhendo o
dois menores freqüências de cada vez.

964
00:45:16,150 --> 00:45:18,110
Então, eu levei 10% e 10%.

965
00:45:18,110 --> 00:45:19,090
Eu criar um novo nó.

966
00:45:19,090 --> 00:45:20,910
E eu chamo o novo nó de 20%.

967
00:45:20,910 --> 00:45:22,750
>> Que dois nós Eu combino o próximo?

968
00:45:22,750 --> 00:45:23,810
É um pouco ambígua.

969
00:45:23,810 --> 00:45:26,643
Portanto, há alguns casos canto para
considerar, mas para manter as coisas bem,

970
00:45:26,643 --> 00:45:29,300
Eu vou escolher 20% -
Eu agora ignorar as crianças.

971
00:45:29,300 --> 00:45:33,640
Eu vou escolher 20% e
15% e desenhar duas novas arestas.

972
00:45:33,640 --> 00:45:35,624
E agora que dois nós
eu logicamente combinar?

973
00:45:35,624 --> 00:45:38,540
Ignorar todas as crianças, todos os
netos, basta olhar para as raízes

974
00:45:38,540 --> 00:45:39,070
agora.

975
00:45:39,070 --> 00:45:42,220
Que dois nós posso amarrar juntos?

976
00:45:42,220 --> 00:45:44,530
Ponto dois e 0,35.

977
00:45:44,530 --> 00:45:45,890
Então deixe-me desenhar duas novas arestas.

978
00:45:45,890 --> 00:45:47,570
E então eu tenho apenas um à esquerda.

979
00:45:47,570 --> 00:45:48,650
Então aqui está uma árvore.

980
00:45:48,650 --> 00:45:51,160
E foi desenhada deliberadamente
olhar tipo de bonito,

981
00:45:51,160 --> 00:45:55,870
de notar que as arestas têm
Também foi marcado zero e um.

982
00:45:55,870 --> 00:45:59,510
Assim, todas as bordas esquerdas são zero
arbitrariamente, mas de forma consistente.

983
00:45:59,510 --> 00:46:01,170
Todas as bordas direitas são queridos.

984
00:46:01,170 --> 00:46:05,070
>> E então o que Hoffman proposta é,
se você quiser representar um B,

985
00:46:05,070 --> 00:46:10,080
em vez de representar o número 66 como
um Ascii que é oito bits inteiros,

986
00:46:10,080 --> 00:46:13,360
Você sabe o que, exatamente loja
o padrão zero, zero, zero,

987
00:46:13,360 --> 00:46:17,030
zero, porque esse é o caminho
da minha árvore, árvore do Sr. Huffman,

988
00:46:17,030 --> 00:46:18,600
para a folha a partir da raiz.

989
00:46:18,600 --> 00:46:20,970
Se você deseja armazenar uma
E, por outro lado, não fazer

990
00:46:20,970 --> 00:46:26,290
enviar oito bits que representam um E.
Em vez disso, enviar o padrão de bits?

991
00:46:26,290 --> 00:46:26,890
Uma.

992
00:46:26,890 --> 00:46:30,410
E o que é agradável sobre esta é
que E é a letra mais popular,

993
00:46:30,410 --> 00:46:32,340
e você está usando o
código mais curto para ele.

994
00:46:32,340 --> 00:46:34,090
O próximo mais popular
carta parece que

995
00:46:34,090 --> 00:46:37,380
era A. E assim quantos bits
ele propor usando para isso?

996
00:46:37,380 --> 00:46:38,270
Zero um.

997
00:46:38,270 --> 00:46:41,060
>> E porque ele é implementado
como esta árvore, por enquanto

998
00:46:41,060 --> 00:46:43,350
deixe-me estipular há
qualquer ambiguidade em Morse

999
00:46:43,350 --> 00:46:46,090
código, porque todo o
letras que se preocupam

1000
00:46:46,090 --> 00:46:48,780
são no final destes bordos.

1001
00:46:48,780 --> 00:46:50,580
Então, isso é apenas um
aplicação de uma árvore.

1002
00:46:50,580 --> 00:46:52,538
Isso é-- e eu vou acenar
minha mão neste como você

1003
00:46:52,538 --> 00:46:55,570
pode implementar isso como uma estrutura C.

1004
00:46:55,570 --> 00:46:58,260
Nós apenas precisamos de combinar
um símbolo, como um char,

1005
00:46:58,260 --> 00:46:59,910
ea freqüência em esquerda e direita.

1006
00:46:59,910 --> 00:47:02,510
Mas vamos olhar para dois
exemplos finais que você vai

1007
00:47:02,510 --> 00:47:06,070
se bastante familiarizado com depois
questionário zero no conjunto de problemas cinco.

1008
00:47:06,070 --> 00:47:09,210
>> Portanto, há a estrutura de dados
conhecida como uma tabela de hash.

1009
00:47:09,210 --> 00:47:12,247
E uma tabela hash é uma espécie de
arrefecer na medida em que tem baldes.

1010
00:47:12,247 --> 00:47:14,830
E suponha que há quatro baldes
aqui, apenas quatro espaços em branco.

1011
00:47:14,830 --> 00:47:20,830
Aqui está um baralho de cartas, e aqui está
clube, pá, clube, diamantes, clube,

1012
00:47:20,830 --> 00:47:25,960
diamantes, clubes, diamantes,
clubs-- então este é o acaso.

1013
00:47:25,960 --> 00:47:30,330
Corações, então estou hearts--
bucketizing todas as entradas aqui.

1014
00:47:30,330 --> 00:47:32,430
E uma tabela de hash necessidades
a olhar para a sua entrada,

1015
00:47:32,430 --> 00:47:34,850
e, em seguida, colocá-lo em um determinado
colocar com base no que você vê.

1016
00:47:34,850 --> 00:47:35,600
É um algoritmo.

1017
00:47:35,600 --> 00:47:37,980
E eu estava usando um super-
algoritmo visual simples.

1018
00:47:37,980 --> 00:47:40,030
A parte mais difícil do que foi
lembrando-se de que as imagens foram.

1019
00:47:40,030 --> 00:47:41,590
E depois há quatro coisas totais.

1020
00:47:41,590 --> 00:47:45,440
>> Agora, as pilhas estavam crescendo, o que
é uma coisa deliberada projeto aqui.

1021
00:47:45,440 --> 00:47:46,540
Mas o que mais eu poderia fazer?

1022
00:47:46,540 --> 00:47:49,080
Então, na verdade, temos aqui um
bando de velhos livros de exame escolar.

1023
00:47:49,080 --> 00:47:51,240
Suponha que um grupo de
nomes alunos estão aqui.

1024
00:47:51,240 --> 00:47:52,570
Aqui está uma tabela hash maior.

1025
00:47:52,570 --> 00:47:54,867
Em vez de quatro baldes,
Tenho, digamos 26.

1026
00:47:54,867 --> 00:47:57,950
E nós não queremos ir pedir emprestado 26
coisas de fora [? Annenberg?], Assim

1027
00:47:57,950 --> 00:48:00,289
aqui está cinco que representam
A a Z. E se eu

1028
00:48:00,289 --> 00:48:03,580
ver um aluno cujo nome começa com A,
Eu vou colocar o seu questionário lá.

1029
00:48:03,580 --> 00:48:08,850
Se alguém começa com C, até lá,
A--, na verdade, não queria fazer isso.

1030
00:48:08,850 --> 00:48:10,060
B passa por aqui.

1031
00:48:10,060 --> 00:48:13,390
Então eu tenho A e B e C. E
Agora, aqui está outro estudante A.

1032
00:48:13,390 --> 00:48:16,212
Mas, se esta tabela hash é
implementado com uma matriz,

1033
00:48:16,212 --> 00:48:17,920
Eu sou do tipo aparafusado
neste momento, certo?

1034
00:48:17,920 --> 00:48:19,510
Eu meio que precisa colocar isso em algum lugar.

1035
00:48:19,510 --> 00:48:24,380
>> Assim, uma maneira que eu posso resolver isto é, todos
direito, A é ocupado, B estiver ocupado, C está ocupado.

1036
00:48:24,380 --> 00:48:28,880
Vou colocá-lo em D. Então,
em primeiro lugar, eu tenho acesso instantâneo aleatório

1037
00:48:28,880 --> 00:48:31,064
para cada um dos baldes para os alunos.

1038
00:48:31,064 --> 00:48:33,230
Mas agora é uma espécie de delegada
em algo linear,

1039
00:48:33,230 --> 00:48:36,750
porque se eu quiser procurar alguém
cujo nome começa com A, eu verifico aqui.

1040
00:48:36,750 --> 00:48:38,854
Mas, se esta não é a um
estudante que eu estou procurando,

1041
00:48:38,854 --> 00:48:41,520
Eu meio que tenho que começar a verificar
os baldes, porque o que eu fiz

1042
00:48:41,520 --> 00:48:44,530
era uma espécie de linearmente
sondar a estrutura de dados.

1043
00:48:44,530 --> 00:48:47,710
Um jeito estúpido de dizer basta olhar
para a primeira abertura disponível,

1044
00:48:47,710 --> 00:48:51,850
e colocar como um plano B, por assim dizer,
ou plano D neste caso, o valor

1045
00:48:51,850 --> 00:48:53,340
nesse local.

1046
00:48:53,340 --> 00:48:56,470
Este é apenas para que se você tiver
tem 26 locais e nenhum aluno

1047
00:48:56,470 --> 00:49:00,600
com o nome Q ou Z, ou algo parecido
que, pelo menos você está usando o espaço.

1048
00:49:00,600 --> 00:49:03,140
>> Mas já vimos mais
soluções inteligentes aqui, certo?

1049
00:49:03,140 --> 00:49:04,870
O que você faria em vez
se você tiver uma colisão?

1050
00:49:04,870 --> 00:49:06,670
Se duas pessoas têm
o nome A, o que seria

1051
00:49:06,670 --> 00:49:09,160
ter sido um mais esperto ou
solução intuitiva do que apenas

1052
00:49:09,160 --> 00:49:12,840
colocando um D, onde é suposto ser?

1053
00:49:12,840 --> 00:49:14,810
Por que não posso simplesmente ir
lado de fora [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
como malloc, outro nó, coloque-
aqui, e em seguida, colocar que um estudante aqui.

1055
00:49:19,960 --> 00:49:22,120
Assim que eu tiver essencialmente
algum tipo de uma matriz,

1056
00:49:22,120 --> 00:49:25,590
ou talvez mais elegantemente como estamos
começando a ver uma lista ligada.

1057
00:49:25,590 --> 00:49:29,520
>> E assim uma tabela hash é uma estrutura
que poderia olhar apenas como este,

1058
00:49:29,520 --> 00:49:33,900
mas mais inteligente, você algo chamado
encadeamento separado, em que uma tabela hash

1059
00:49:33,900 --> 00:49:38,340
muito simplesmente é uma matriz, cada um dos
cujos elementos não é um número,

1060
00:49:38,340 --> 00:49:40,470
é em si uma lista ligada.

1061
00:49:40,470 --> 00:49:45,080
Para que você tenha acesso super rápido
decidir onde botar o seu valor para.

1062
00:49:45,080 --> 00:49:48,059
Muito parecido com o exemplo cartões,
Eu fiz decisões super rápido.

1063
00:49:48,059 --> 00:49:49,600
Corações vai aqui, diamantes vai aqui.

1064
00:49:49,600 --> 00:49:52,180
Mesmo aqui, A vai aqui,
D vai aqui, B vai aqui.

1065
00:49:52,180 --> 00:49:55,740
Então super rápido look-ups, e se
acontecer de você correr em um caso

1066
00:49:55,740 --> 00:49:59,429
colisões, onde você tem dois,
pessoas com o mesmo nome, bem, então

1067
00:49:59,429 --> 00:50:00,970
você acabou de começar ligando-os juntos.

1068
00:50:00,970 --> 00:50:03,900
E talvez você mantê-los classificadas
em ordem alfabética, talvez você não.

1069
00:50:03,900 --> 00:50:05,900
Mas pelo menos agora temos o dinamismo.

1070
00:50:05,900 --> 00:50:10,250
Assim, por um lado, temos super rápido
constante de tempo e tipo de tempo linear

1071
00:50:10,250 --> 00:50:14,110
envolvidos se essas listas ligadas
começam a ficar um pouco longo.

1072
00:50:14,110 --> 00:50:16,880
>> Portanto, este tipo de um bobo,
gracejo geeky anos atrás.

1073
00:50:16,880 --> 00:50:19,590
No CS50 Hack-a-thon,
quando os alunos check-in,

1074
00:50:19,590 --> 00:50:22,040
alguns TF ou CA a cada ano
acha que é engraçado para colocar-se

1075
00:50:22,040 --> 00:50:27,772
um sinal como este, onde ele só
significa que se seu nome começa com um A,

1076
00:50:27,772 --> 00:50:28,870
ir por este caminho.

1077
00:50:28,870 --> 00:50:31,110
Se seu nome começa
com um B, ir isto-- OK,

1078
00:50:31,110 --> 00:50:33,290
é engraçado talvez mais tarde no semestre.

1079
00:50:33,290 --> 00:50:36,420
Mas há outra
maneira de fazer isso também.

1080
00:50:36,420 --> 00:50:37,410
Vamos voltar a isso.

1081
00:50:37,410 --> 00:50:38,600
>> Portanto, há essa estrutura.

1082
00:50:38,600 --> 00:50:40,420
E esta é a nossa última
estrutura para hoje,

1083
00:50:40,420 --> 00:50:42,400
que é algo chamado trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, que, por algum motivo é curto
para recuperação, mas ele é chamado trie.

1085
00:50:47,140 --> 00:50:51,389
Assim, um outro interessante é trie
amálgama de muitas dessas idéias.

1086
00:50:51,389 --> 00:50:52,930
É uma árvore, o que temos visto antes.

1087
00:50:52,930 --> 00:50:54,180
Não é uma árvore de busca binária.

1088
00:50:54,180 --> 00:50:58,410
É uma árvore com qualquer número de filhos,
mas cada uma das crianças em um trie

1089
00:50:58,410 --> 00:51:00,090
é uma matriz.

1090
00:51:00,090 --> 00:51:04,790
Uma matriz de tamanho, dizem, 26 ou talvez 27
se você quiser apoiar hifenizado nomes

1091
00:51:04,790 --> 00:51:06,790
ou apóstrofos em nomes de pessoas.

1092
00:51:06,790 --> 00:51:08,280
>> E por isso esta é uma estrutura de dados.

1093
00:51:08,280 --> 00:51:10,290
E se você olhar de cima
para baixo, como se você

1094
00:51:10,290 --> 00:51:13,710
olhar para o nó superior lá, M, é
apontando para a coisa mais à esquerda lá,

1095
00:51:13,710 --> 00:51:17,665
que é, em seguida, A, X, W, E, L, L. Isto é
apenas uma estrutura de dados que arbitrariamente

1096
00:51:17,665 --> 00:51:19,120
é o armazenamento de nomes de pessoas.

1097
00:51:19,120 --> 00:51:25,720
E Maxwell é armazenado por apenas seguindo
um caminho de matriz para matriz para matriz.

1098
00:51:25,720 --> 00:51:30,050
Mas o que é surpreendente sobre um trie é
que, ao passo que uma lista ligada e até mesmo

1099
00:51:30,050 --> 00:51:34,520
uma matriz, o melhor que eu já cheguei é
tempo linear ou logarítmica tempo à procura

1100
00:51:34,520 --> 00:51:35,600
alguém.

1101
00:51:35,600 --> 00:51:40,530
Nesta estrutura de dados de um trie, se
minha estrutura de dados tem um nome nele

1102
00:51:40,530 --> 00:51:43,720
e eu estou procurando Maxwell, eu sou
vai encontrá-lo muito rapidamente.

1103
00:51:43,720 --> 00:51:47,910
Acabei de olhar para M-A-X-W-E-L-L. E se
esta estrutura de dados, em contraste,

1104
00:51:47,910 --> 00:51:51,830
Se N é um milhão, se há uma
milhão de nomes nesta estrutura de dados,

1105
00:51:51,830 --> 00:51:57,100
Maxwell ainda vai ser
detectável depois de apenas M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
degraus.

1107
00:51:58,090 --> 00:52:01,276
E passos David-- D-A-V-I-D.

1108
00:52:01,276 --> 00:52:03,400
Em outras palavras, através da construção de
uma estrutura de dados que é

1109
00:52:03,400 --> 00:52:07,240
tem todas essas matrizes, todos os quais
se sustentar de acesso aleatório,

1110
00:52:07,240 --> 00:52:11,090
Eu posso começar a olhar para cima de pessoas
nome usando uma quantidade de tempo que é

1111
00:52:11,090 --> 00:52:14,340
proporcional à não o número
de coisas na estrutura de dados,

1112
00:52:14,340 --> 00:52:16,330
como um milhão de nomes existentes.

1113
00:52:16,330 --> 00:52:20,135
A quantidade de tempo que leva-me a encontrar
H-A-X-W-E-G-G na estrutura de dados é este

1114
00:52:20,135 --> 00:52:22,260
não proporcional ao
o tamanho da estrutura de dados,

1115
00:52:22,260 --> 00:52:25,930
mas com o comprimento do nome.

1116
00:52:25,930 --> 00:52:28,440
E realisticamente a
nomes que nós estamos olhando para cima

1117
00:52:28,440 --> 00:52:29,970
nunca vai ser louco por muito tempo.

1118
00:52:29,970 --> 00:52:32,600
Talvez alguém tem um caráter 10
nomear, 20 nome do personagem.

1119
00:52:32,600 --> 00:52:33,900
É certamente finito, certo?

1120
00:52:33,900 --> 00:52:37,110
Não é um ser humano em que a Terra
tem o nome mais longo possível,

1121
00:52:37,110 --> 00:52:39,920
mas esse nome é uma constante
comprimento valor, certo?

1122
00:52:39,920 --> 00:52:41,980
Ele não varia em qualquer sentido.

1123
00:52:41,980 --> 00:52:45,090
Assim, deste modo, nós temos
conseguida uma estrutura de dados

1124
00:52:45,090 --> 00:52:47,800
que é tempo constante look-up.

1125
00:52:47,800 --> 00:52:50,670
Ele faz ter um número de passos
dependendo do comprimento da entrada,

1126
00:52:50,670 --> 00:52:54,250
mas não o número de nome
na estrutura de dados.

1127
00:52:54,250 --> 00:52:58,700
Então, se nós dobrar o número de nomes
no próximo ano de um bilhão a dois bilhões,

1128
00:52:58,700 --> 00:53:03,720
constatação Maxwell vai levar
o mesmo número de sete passos

1129
00:53:03,720 --> 00:53:04,650
para encontrá-lo.

1130
00:53:04,650 --> 00:53:08,810
E, assim, parecem ter conseguido
nosso Santo Graal do tempo de execução.

1131
00:53:08,810 --> 00:53:10,860
>> Assim, um par de anúncios rápidos.

1132
00:53:10,860 --> 00:53:11,850
Questionário de zero está chegando.

1133
00:53:11,850 --> 00:53:14,600
Mais sobre isso no site do curso
durante o próximo par de dias.

1134
00:53:14,600 --> 00:53:17,120
Segunda-feira de lecture-- É um feriado
aqui em Harvard na segunda-feira.

1135
00:53:17,120 --> 00:53:18,850
Não é em New Haven,
assim que nós estamos tomando a classe

1136
00:53:18,850 --> 00:53:20,310
a New Haven para palestra na segunda-feira.

1137
00:53:20,310 --> 00:53:22,550
Tudo será filmado
e transmitido ao vivo, como de costume,

1138
00:53:22,550 --> 00:53:24,900
mas vamos terminar hoje
com um segundo clipe 30

1139
00:53:24,900 --> 00:53:26,910
chamados de "Pensamentos Profundos"
Daven por Farnham, que

1140
00:53:26,910 --> 00:53:30,850
foi inspirado no ano passado até sábado
"Pensamentos Profundos" de Night Live

1141
00:53:30,850 --> 00:53:35,700
por Jack Handy, que
agora deve fazer sentido.

1142
00:53:35,700 --> 00:53:38,810
>> FILME: E agora, "Deep
Pensamentos "por Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Mesa de confecção.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> COLUNA 1: Tudo bem, isso é tudo por agora.

1147
00:53:47,660 --> 00:53:48,805
Vamos vê-lo na próxima semana.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Para vê-lo em ação.

1150
00:53:56,680 --> 00:53:58,304
Então, vamos dar uma olhada nisso agora.

1151
00:53:58,304 --> 00:53:59,890
Então, aqui, temos um conjunto indiferenciado.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, você pode ir em frente e reinício
isso por apenas um segundo, por favor.

1153
00:54:04,860 --> 00:54:08,562
Tudo bem, as câmeras estão rolando, então
ação sempre que você estiver pronto, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Tudo bem, então o que nós
temos aqui é um conjunto indiferenciado.

1155
00:54:11,020 --> 00:54:13,960
E eu tenho colorido todos os elementos
vermelho para indicar que ele é, na verdade,

1156
00:54:13,960 --> 00:54:14,460
indiferenciados.

1157
00:54:14,460 --> 00:54:17,960
Então recordar que a primeira coisa que fazemos
é que classificar a metade esquerda da matriz.

1158
00:54:17,960 --> 00:54:20,630
Em seguida, classificar a direita
metade da matriz.

1159
00:54:20,630 --> 00:54:22,830
E ya-da, ya-da, ya-da,
que fundi-las.

1160
00:54:22,830 --> 00:54:24,520
E nós temos uma matriz completamente ordenada.

1161
00:54:24,520 --> 00:54:25,360
Então é assim que funciona merge sort.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Ei, ei, ei,
corta, corta, corta, corta.

1163
00:54:27,109 --> 00:54:30,130
Doug, você não pode apenas ya-da, ya-da,
ya-da, o seu caminho através merge sort.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Eu apenas fiz.

1165
00:54:31,970 --> 00:54:32,832
Está bem.

1166
00:54:32,832 --> 00:54:33,540
Nós somos bons de ir.

1167
00:54:33,540 --> 00:54:34,760
Vamos apenas continuar jogando.

1168
00:54:34,760 --> 00:54:35,380
Então, de qualquer maneira,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Você tem que explicar
Ele mais plenamente do que isso.

1170
00:54:37,800 --> 00:54:39,999
Isso não é apenas o suficiente.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, nós não
precisamos voltar a um.

1172
00:54:41,790 --> 00:54:42,350
Está bem.

1173
00:54:42,350 --> 00:54:45,690
De qualquer forma, se continuarmos com merge--
Ian, nós estamos no meio das filmagens.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Eu sei.

1175
00:54:46,612 --> 00:54:49,320
E nós não podemos apenas ya-da, ya-da,
ya-da, através de todo o processo.

1176
00:54:49,320 --> 00:54:52,200
Você tem que explicar como o
dois lados se fundiram juntos.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Mas nós já
explicou como os dois sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Você acabou mostrado
-lhes uma variedade de mesclagem.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Eles sabem o processo.

1180
00:54:56,486 --> 00:54:57,172
Eles estão bem.

1181
00:54:57,172 --> 00:54:58,380
Temos ido sobre ele dez vezes.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Você acabou de pular direito sobre ele.

1183
00:55:00,330 --> 00:55:03,360
Vamos voltar para um, você
você não pode ya-da, ya-da sobre ele.

1184
00:55:03,360 --> 00:55:05,480
Tudo bem, de volta a um.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Eu tenho que voltar
através de todos os slides?

1186
00:55:07,833 --> 00:55:08,332
Meu Deus.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
É como o sexto tempo, Ian.

1189
00:55:13,004 --> 00:55:13,940
Está bem.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Tudo bem.

1191
00:55:15,200 --> 00:55:16,590
Esta pronto?

1192
00:55:16,590 --> 00:55:17,400
Ótimo.

1193
00:55:17,400 --> 00:55:18,950
Açao.