1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Semana 6]

2
00:00:02,000 --> 00:00:04,000
[David J. Malan] [Harvard University]

3
00:00:04,000 --> 00:00:08,000
[Esta é CS50.] [CS50.TV]

4
00:00:08,000 --> 00:00:12,000
>> Este é CS50, e este é o início da semana 6,

5
00:00:12,000 --> 00:00:16,000
assim um par de novas ferramentas estão agora disponíveis para você aproveitar,

6
00:00:16,000 --> 00:00:19,000
o primeiro dos quais é chamado CS50 estilo.

7
00:00:19,000 --> 00:00:22,000
As probabilidades são, se você é como eu ou qualquer um dos companheiros de ensino,

8
00:00:22,000 --> 00:00:26,000
você provavelmente já viu um programa cujo estilo parece um pouco algo como isto.

9
00:00:26,000 --> 00:00:30,000
Talvez você começar a cortar alguns cantos, tarde da noite, ou você vai lidar com isso mais tarde,

10
00:00:30,000 --> 00:00:32,000
e então um TF ou CA vem mais durante o expediente.

11
00:00:32,000 --> 00:00:34,000
Então é difícil para nós ler.

12
00:00:34,000 --> 00:00:38,000
Bem, esse código é sintaticamente correta, e ele irá compilar e ele vai realmente funcionar.

13
00:00:38,000 --> 00:00:40,000
Mas definitivamente não é um 5 para o estilo.

14
00:00:40,000 --> 00:00:45,000
>> Mas agora, se vamos para este diretório aqui-

15
00:00:45,000 --> 00:00:48,000
e perceber que eu tenho conditions2.c-

16
00:00:48,000 --> 00:00:55,000
e eu corro esse novo comando, style50, nesta conditions2.c arquivo, Enter

17
00:00:55,000 --> 00:00:57,000
perceber que ele me informou que foi estilizado.

18
00:00:57,000 --> 00:01:00,000
Gedit percebeu que o arquivo foi alterado no disco,

19
00:01:00,000 --> 00:01:08,000
e se eu clicar em recarregar, todos os seus problemas estão agora automatizado.

20
00:01:08,000 --> 00:01:15,000
[Aplausos]

21
00:01:15,000 --> 00:01:17,000
Isso é uma das coisas que fizemos neste fim de semana.

22
00:01:17,000 --> 00:01:20,000
Perceber que ele é imperfeito porque há algum código

23
00:01:20,000 --> 00:01:23,000
que simplesmente não será capaz de estilizar perfeitamente,

24
00:01:23,000 --> 00:01:26,000
mas que esta é agora uma ferramenta que você pode tirar vantagem de

25
00:01:26,000 --> 00:01:33,000
se apenas para arrumar algumas das chaves mais errantly colocado cacheados e afins.

26
00:01:33,000 --> 00:01:36,000
>> Mas o mais interessante agora é CS50 Check.

27
00:01:36,000 --> 00:01:39,000
Com CS50 Check, você pode realmente realizar os testes de correção mesmos

28
00:01:39,000 --> 00:01:42,000
em seu próprio código que os companheiros de ensino são capazes de.

29
00:01:42,000 --> 00:01:44,000
Este é um utilitário de linha de comando que vem agora no aparelho

30
00:01:44,000 --> 00:01:46,000
assim que você fizer uma update50 como por

31
00:01:46,000 --> 00:01:49,000
pset quatro especificações, e usá-lo essencialmente como este.

32
00:01:49,000 --> 00:01:51,000
Você corre o check50 comando.

33
00:01:51,000 --> 00:01:56,000
Então você passa em um argumento de linha de comando, ou, mais geralmente conhecido como um interruptor ou uma bandeira.

34
00:01:56,000 --> 00:01:58,000
Geralmente, as coisas que têm hífens são chamados um interruptor

35
00:01:58,000 --> 00:02:02,000
a um programa de linha de comando, assim c especifica

36
00:02:02,000 --> 00:02:04,000
as verificações que você deseja executar.

37
00:02:04,000 --> 00:02:07,000
>> Os testes que você deseja executar são identificados individualmente por essa seqüência,

38
00:02:07,000 --> 00:02:10,000
2012/pset4/resize.

39
00:02:10,000 --> 00:02:13,000
Em outras palavras, isso é apenas uma seqüência arbitrária, mas única

40
00:02:13,000 --> 00:02:18,000
que usamos para identificar testes 4 pset de correção.

41
00:02:18,000 --> 00:02:21,000
E então você especificar uma lista separada por espaço dos arquivos que você deseja carregar

42
00:02:21,000 --> 00:02:24,000
Verifique a CS50 para análise.

43
00:02:24,000 --> 00:02:29,000
Por exemplo, se eu ir para a minha solução aqui para resize.c-

44
00:02:29,000 --> 00:02:31,000
deixe-me abrir um maior terminal de janela

45
00:02:31,000 --> 00:02:42,000
e eu ir em frente e correr digamos check50-c 2012/pset4/resize,

46
00:02:42,000 --> 00:02:46,000
e então eu ir em frente e especificar os nomes dos arquivos,

47
00:02:46,000 --> 00:02:49,000
resize.c, e pressione a tecla Enter, ele comprime,

48
00:02:49,000 --> 00:02:53,000
ele carrega, ele verifica, e eu só falhou um monte de testes.

49
00:02:53,000 --> 00:02:59,000
O de vermelho no canto superior esquerdo diz que resize.c e bmp existe.

50
00:02:59,000 --> 00:03:01,000
Esse foi o teste. Essa foi a pergunta que nós fizemos.

51
00:03:01,000 --> 00:03:04,000
E é infeliz porque a resposta era falsa.

52
00:03:04,000 --> 00:03:08,000
O texto em branco abaixo diz esperar bmp.h de existir, e isso é simplesmente culpa minha.

53
00:03:08,000 --> 00:03:11,000
Eu esqueci de enviá-lo, então eu preciso fazer upload de dois arquivos,

54
00:03:11,000 --> 00:03:14,000
resize.c e bmp.h.

55
00:03:14,000 --> 00:03:17,000
Mas agora observar todos os outros testes são em amarelo porque não correr,

56
00:03:17,000 --> 00:03:21,000
e assim o rosto sorridente é vertical, porque ele não é nem feliz nem triste,

57
00:03:21,000 --> 00:03:25,000
mas temos que corrigir esse problema no vermelho antes de essas outras verificações será executado.

58
00:03:25,000 --> 00:03:27,000
>> Deixe-me corrigir isso.

59
00:03:27,000 --> 00:03:30,000
Deixe-me afastar e executar novamente essa, desta vez com bmp.h também

60
00:03:30,000 --> 00:03:34,000
na linha de comando, Enter, e agora, se tudo correr bem,

61
00:03:34,000 --> 00:03:38,000
que vai verificar e retornar um resultado de-segure a respiração-

62
00:03:38,000 --> 00:03:42,000
tudo verde, o que significa que eu estou indo muito bem em pset 4 até agora.

63
00:03:42,000 --> 00:03:44,000
Você pode ver e inferir do texto descritivo aqui

64
00:03:44,000 --> 00:03:47,000
exatamente o que é que testamos.

65
00:03:47,000 --> 00:03:49,000
Testamos primeiro é que os arquivos existem?

66
00:03:49,000 --> 00:03:51,000
Em seguida, testamos faz compilação resize.c?

67
00:03:51,000 --> 00:03:58,000
Então nós testamos não é redimensionar uma BMP 1x1 pixel quando n, o fator de redimensionamento, é 1.

68
00:03:58,000 --> 00:04:01,000
Agora, se você não tem idéia do que n é, você vai uma vez que você mergulhar pset 4,

69
00:04:01,000 --> 00:04:04,000
mas que simplesmente é uma verificação de sanidade para se certificar de que você não é o redimensionamento

70
00:04:04,000 --> 00:04:08,000
uma imagem em todos, se o fator de redimensionamento é 1.

71
00:04:08,000 --> 00:04:14,000
Se, pelo contrário, ele redimensiona um pixel 1x1 para um 1x1 pixel BMP para 2x2 corretamente

72
00:04:14,000 --> 00:04:19,000
quando n é 2, então de forma semelhante, formas mina em conformidade.

73
00:04:19,000 --> 00:04:22,000
>> Em suma, este é significado, um, pegue a travessia dos dedos

74
00:04:22,000 --> 00:04:25,000
fora da equação direita antes de enviar seu pset.

75
00:04:25,000 --> 00:04:28,000
Você saberá exatamente o que o seu TF logo saberá

76
00:04:28,000 --> 00:04:30,000
quando você vai sobre o envio de alguns desses conjuntos de problemas,

77
00:04:30,000 --> 00:04:34,000
e também a motivação pedagógica é realmente colocar

78
00:04:34,000 --> 00:04:37,000
a oportunidade na frente de você para que, quando você sabe a priori

79
00:04:37,000 --> 00:04:39,000
que não há erros em seu código e testes que não estão sendo passados,

80
00:04:39,000 --> 00:04:43,000
você pode colocar mais eficaz do tempo na frente para resolver esses problemas

81
00:04:43,000 --> 00:04:45,000
em vez de perder pontos, obter feedback de seu TF,

82
00:04:45,000 --> 00:04:48,000
e depois ir, "Ahh," como eu deveria ter percebido isso.

83
00:04:48,000 --> 00:04:50,000
Agora, pelo menos, há uma ferramenta para ajudar a encontrar isso.

84
00:04:50,000 --> 00:04:52,000
Ele não vai apontar onde é o erro, mas ele vai dizer

85
00:04:52,000 --> 00:04:54,000
o que é um sintoma da mesma.

86
00:04:54,000 --> 00:04:57,000
>> Agora realizar os testes não são necessariamente exaustiva.

87
00:04:57,000 --> 00:04:59,000
Só porque você tem uma tela cheia de verde Smiley Faces

88
00:04:59,000 --> 00:05:02,000
não significa que seu código é perfeito, mas isso não significa

89
00:05:02,000 --> 00:05:06,000
que ele passou alguns testes prescritos pela especificação.

90
00:05:06,000 --> 00:05:08,000
Às vezes a gente não vai liberar cheques.

91
00:05:08,000 --> 00:05:10,000
Por exemplo, whodunit, um dos aspectos da pset 4,

92
00:05:10,000 --> 00:05:15,000
é tipo de decepcionante se nós lhe damos

93
00:05:15,000 --> 00:05:18,000
a resposta para o que ele é, e há uma série de maneiras para revelar

94
00:05:18,000 --> 00:05:21,000
quem é a pessoa em que o ruído vermelho.

95
00:05:21,000 --> 00:05:24,000
A especificação será sempre especificar no futuro para pset em diante 5

96
00:05:24,000 --> 00:05:26,000
o que verifica existir para você.

97
00:05:26,000 --> 00:05:28,000
Você vai perceber que há essa URL em branco no fundo.

98
00:05:28,000 --> 00:05:30,000
Por enquanto, esta é apenas a saída de diagnóstico.

99
00:05:30,000 --> 00:05:33,000
Se você visitar a URL, você vai ter um monte de loucos, mensagens enigmáticas

100
00:05:33,000 --> 00:05:36,000
que você está convidado a olhar através, mas é principalmente para o pessoal

101
00:05:36,000 --> 00:05:41,000
para que possamos diagnosticar e depurar erros em check50 si.

102
00:05:41,000 --> 00:05:46,000
>> Sem delongas, vamos seguir em frente de onde paramos.

103
00:05:46,000 --> 00:05:48,000
CS50 biblioteca tomamos para concedido por algumas semanas,

104
00:05:48,000 --> 00:05:52,000
mas, em seguida, na semana passada, começamos a descascar para trás uma das camadas do mesmo.

105
00:05:52,000 --> 00:05:55,000
Começamos colocando de lado cadeia em favor do que em vez disso?

106
00:05:55,000 --> 00:05:57,000
[Os alunos] Char.

107
00:05:57,000 --> 00:05:59,000
* Char, que tem sido um char * todo esse tempo,

108
00:05:59,000 --> 00:06:03,000
mas agora não temos que fingir que é um tipo string de dados real.

109
00:06:03,000 --> 00:06:06,000
Em vez disso, tem sido sinônimo de sorte para char *,

110
00:06:06,000 --> 00:06:09,000
e uma string é uma seqüência de caracteres,

111
00:06:09,000 --> 00:06:14,000
Então, por que será que faz sentido para representar strings como char * s?

112
00:06:14,000 --> 00:06:20,000
O que faz um char * representam no contexto desse conceito de uma string?

113
00:06:20,000 --> 00:06:23,000
Sim. >> [Estudante] O primeiro caractere.

114
00:06:23,000 --> 00:06:25,000
Bom, o primeiro caractere, mas não é bem o primeiro caractere.

115
00:06:25,000 --> 00:06:27,000
É uma [Os alunos] Endereço.

116
00:06:27,000 --> 00:06:29,000
Bom, o endereço do primeiro caractere.

117
00:06:29,000 --> 00:06:33,000
Tudo que é necessário para representar uma cadeia em memória de um computador

118
00:06:33,000 --> 00:06:36,000
é apenas o endereço exclusivo do seu byte primeiro.

119
00:06:36,000 --> 00:06:38,000
Você não tem sequer de saber quanto tempo é

120
00:06:38,000 --> 00:06:42,000
pois como você pode descobrir isso dinamicamente?

121
00:06:42,000 --> 00:06:44,000
[Estudante] comprimento String.

122
00:06:44,000 --> 00:06:48,000
Você pode chamar comprimento da corda, excelente, mas como funciona o comprimento da corda?

123
00:06:48,000 --> 00:06:50,000
O que ele faz? Sim.

124
00:06:50,000 --> 00:06:52,000
[Estudante] Continue indo até chegar o caractere nulo.

125
00:06:52,000 --> 00:06:54,000
Sim, exatamente, ele só interage com um loop for, while,

126
00:06:54,000 --> 00:06:57,000
qualquer que seja a partir de * até ao fim, e que o fim está representada

127
00:06:57,000 --> 00:07:01,000
por \ 0, o personagem chamado nulo, nulo,

128
00:07:01,000 --> 00:07:05,000
não deve ser confundida com nulo, o que é um ponteiro,

129
00:07:05,000 --> 00:07:07,000
que entrará na conversa de novo hoje.

130
00:07:07,000 --> 00:07:11,000
>> Nós descascado uma camada de GetInt, e depois demos uma olhada no GetString,

131
00:07:11,000 --> 00:07:14,000
e lembrar que essas duas funções, ou realmente,

132
00:07:14,000 --> 00:07:18,000
GetString, estava usando uma determinada função

133
00:07:18,000 --> 00:07:21,000
para realmente analisar, isto é, ler ou analisar, a entrada do usuário.

134
00:07:21,000 --> 00:07:25,000
E o que foi que nova função?

135
00:07:25,000 --> 00:07:27,000
Scanf ou sscanf. Ele realmente vem em alguns sabores diferentes.

136
00:07:27,000 --> 00:07:31,000
Há scanf, há sscanf, há fscanf.

137
00:07:31,000 --> 00:07:35,000
Por enquanto, porém, vamos focar o mais facilmente ilustrado,

138
00:07:35,000 --> 00:07:38,000
e deixe-me ir em frente e abrir no aparelho

139
00:07:38,000 --> 00:07:41,000
um arquivo como este, scanf1.c.

140
00:07:41,000 --> 00:07:43,000
Este é um programa super simples,

141
00:07:43,000 --> 00:07:46,000
mas que faz algo que nunca fizemos

142
00:07:46,000 --> 00:07:48,000
sem a ajuda da biblioteca CS50.

143
00:07:48,000 --> 00:07:51,000
Este recebe um int de um usuário. Como isso funciona?

144
00:07:51,000 --> 00:07:53,000
Bem, na linha 16 há,

145
00:07:53,000 --> 00:07:56,000
perceber que nós declaramos um int x chamado, e neste momento da história,

146
00:07:56,000 --> 00:07:58,000
o que é o valor de x?

147
00:07:58,000 --> 00:08:00,000
[Resposta do aluno inaudível]

148
00:08:00,000 --> 00:08:02,000
[David M.] Direito, quem sabe, algum valor lixo potencialmente, assim, em 17, nós apenas dizer que o usuário

149
00:08:02,000 --> 00:08:06,000
me dar um número, por favor, e passo 18 é onde fica interessante.

150
00:08:06,000 --> 00:08:11,000
Scanf parece emprestar uma idéia de printf em que ele usa esses códigos de formato entre aspas.

151
00:08:11,000 --> 00:08:13,000
D% é, naturalmente, um número decimal.

152
00:08:13,000 --> 00:08:21,000
Mas por que estou passando & x em vez de apenas x?

153
00:08:21,000 --> 00:08:24,000
O primeiro é correta. Sim.

154
00:08:24,000 --> 00:08:26,000
[Resposta do aluno inaudível]

155
00:08:26,000 --> 00:08:31,000
Exatamente, se o objetivo do programa, como o GetInt própria função,

156
00:08:31,000 --> 00:08:34,000
é para ter uma int do usuário que pode passar funções

157
00:08:34,000 --> 00:08:38,000
todas as variáveis ​​que eu quero, mas se eu não passá-los por referência

158
00:08:38,000 --> 00:08:41,000
ou por endereço ou por ponteiro, todos sinônimos para fins de hoje,

159
00:08:41,000 --> 00:08:46,000
em seguida, que a função não tem capacidade de alterar o conteúdo da variável.

160
00:08:46,000 --> 00:08:49,000
Isto passaria em uma cópia assim como a versão de buggy de swap

161
00:08:49,000 --> 00:08:51,000
que nós já conversamos sobre algumas vezes agora.

162
00:08:51,000 --> 00:08:54,000
>> Mas em vez disso, fazendo & x, eu estou literalmente passando o que?

163
00:08:54,000 --> 00:08:57,000
[Aluno] O endereço. >> O endereço de x.

164
00:08:57,000 --> 00:09:01,000
É como desenhar um mapa para a função chamada scanf e dizendo aqui,

165
00:09:01,000 --> 00:09:04,000
estas são as direcções para um bloco de memória no computador

166
00:09:04,000 --> 00:09:07,000
que você pode ir armazenar algum inteiro dentro

167
00:09:07,000 --> 00:09:10,000
Para que sscanf para fazer agora que

168
00:09:10,000 --> 00:09:13,000
o operador, o que parte da sintaxe é que vai ter que usar

169
00:09:13,000 --> 00:09:19,000
mesmo que não possa vê-lo porque alguém escreveu essa função?

170
00:09:19,000 --> 00:09:21,000
Em outras palavras - o que é isso?

171
00:09:21,000 --> 00:09:23,000
[Estudante] X ler.

172
00:09:23,000 --> 00:09:27,000
Não vai ser uma leitura, mas apenas em relação à x aqui.

173
00:09:27,000 --> 00:09:30,000
Se scanf está sendo passado o endereço de x,

174
00:09:30,000 --> 00:09:35,000
sintaticamente, o operador é obrigado a existir em algum lugar

175
00:09:35,000 --> 00:09:38,000
dentro de implementação, de modo que scanf scanf

176
00:09:38,000 --> 00:09:42,000
pode realmente escrever um número de 2 a esse endereço?

177
00:09:42,000 --> 00:09:44,000
Sim, então o *.

178
00:09:44,000 --> 00:09:47,000
Lembre-se de que o * é o nosso operador dereference, o que essencialmente significa ir para lá.

179
00:09:47,000 --> 00:09:50,000
>> Assim que tiver sido entregue um endereço, como é o caso aqui,

180
00:09:50,000 --> 00:09:53,000
scanf é, provavelmente, se nós realmente olhou em torno de seu código-fonte

181
00:09:53,000 --> 00:09:59,000
está fazendo * x ou o equivalente a realmente ir para esse endereço e colocar algum valor lá.

182
00:09:59,000 --> 00:10:02,000
Agora, o modo como scanf recebe a entrada do teclado,

183
00:10:02,000 --> 00:10:04,000
vamos agitar as mãos para fora para hoje.

184
00:10:04,000 --> 00:10:07,000
Basta assumir que o sistema operacional permite que sscanf para falar

185
00:10:07,000 --> 00:10:11,000
para o teclado do usuário, mas neste ponto agora na linha 19,

186
00:10:11,000 --> 00:10:14,000
quando simplesmente imprimir x, parece ser o caso

187
00:10:14,000 --> 00:10:17,000
scanf que colocou um int em x.

188
00:10:17,000 --> 00:10:19,000
Isso é exatamente como scanf funciona, e lembrar na semana passada

189
00:10:19,000 --> 00:10:25,000
é exatamente como GetString e GetInt e sua outra família de funções

190
00:10:25,000 --> 00:10:28,000
finalmente funciona, embora com ligeira variação como sscanf,

191
00:10:28,000 --> 00:10:31,000
o que significa digitalizar uma cadeia em vez do teclado.

192
00:10:31,000 --> 00:10:33,000
Mas vamos dar uma olhada em uma pequena variação desta.

193
00:10:33,000 --> 00:10:37,000
Em scanf2, eu realmente errou.

194
00:10:37,000 --> 00:10:42,000
O que está errado, e eu vou esconder o comentário que explica como muito

195
00:10:42,000 --> 00:10:47,000
o que está errado com este programa, a versão 2?

196
00:10:47,000 --> 00:10:55,000
Seja tão técnico como possível neste momento.

197
00:10:55,000 --> 00:10:57,000
Ele parece muito bom.

198
00:10:57,000 --> 00:11:03,000
É bem recuado, mas-

199
00:11:03,000 --> 00:11:07,000
Ok, que tal vamos podá-la para baixo para perguntas mais curtos?

200
00:11:07,000 --> 00:11:17,000
Linha 16. O que é linha 16 fazendo em Inglês, mas precisa técnico?

201
00:11:17,000 --> 00:11:20,000
Ficando um pouco estranho. Sim, Michael.

202
00:11:20,000 --> 00:11:25,000
[Estudante] Está apontando para a primeira letra de uma string.

203
00:11:25,000 --> 00:11:27,000
>> Ok, perto. Deixe-me ajustar isso um pouco.

204
00:11:27,000 --> 00:11:33,000
Apontando para a primeira letra de uma string, você está declarando uma variável chamada tampão

205
00:11:33,000 --> 00:11:36,000
que irá apontar para o primeiro endereço de uma string,

206
00:11:36,000 --> 00:11:39,000
ou seja, que irá apontar mais precisamente a uma char.

207
00:11:39,000 --> 00:11:42,000
Note que não é realmente apontando para qualquer lugar, porque não há operador de atribuição.

208
00:11:42,000 --> 00:11:46,000
Não há sinal de igual, então tudo o que estamos fazendo é alocação de reserva variável chamada.

209
00:11:46,000 --> 00:11:49,000
Ele passa a ser de 32 bits porque é um ponteiro,

210
00:11:49,000 --> 00:11:52,000
e o conteúdo de tampão, eventualmente, presumivelmente

211
00:11:52,000 --> 00:11:57,000
conterá um endereço de um char, mas por agora, o que tampão contém?

212
00:11:57,000 --> 00:11:59,000
Apenas alguns falso, quem sabe, algum valor de lixo,

213
00:11:59,000 --> 00:12:03,000
porque não explicitamente inicializado, então não devemos assumir nada.

214
00:12:03,000 --> 00:12:06,000
Ok, então agora é a linha 17-o que faz a linha 17 faz?

215
00:12:06,000 --> 00:12:08,000
Talvez que vai aquecer isso.

216
00:12:08,000 --> 00:12:10,000
Ela imprime uma string, certo?

217
00:12:10,000 --> 00:12:12,000
Ela imprime Cordas por favor.

218
00:12:12,000 --> 00:12:15,000
>> Linha 18 é uma espécie de familiar agora em que acabamos de ver uma variação deste

219
00:12:15,000 --> 00:12:18,000
mas com um código de formato diferente, por isso, em linha 18,

220
00:12:18,000 --> 00:12:23,000
estamos dizendo scanf aqui é o endereço de um bloco de memória.

221
00:12:23,000 --> 00:12:27,000
Eu quero que você tocar em uma corda, como implicado por% s,

222
00:12:27,000 --> 00:12:32,000
mas o problema é que não temos feito algumas coisas aqui.

223
00:12:32,000 --> 00:12:35,000
O que é um dos problemas?

224
00:12:35,000 --> 00:12:38,000
[Estudante] Está tentando dereference um ponteiro nulo.

225
00:12:38,000 --> 00:12:41,000
Bom, ponteiros nulos ou apenas outra maneira desconhecido.

226
00:12:41,000 --> 00:12:45,000
Você está entregando scanf um endereço, mas você disse há pouco

227
00:12:45,000 --> 00:12:49,000
que esse endereço é algum valor lixo porque nós realmente não atribuí-lo a nada,

228
00:12:49,000 --> 00:12:53,000
e por isso você está dizendo scanf efetivamente ir colocar uma corda aqui,

229
00:12:53,000 --> 00:12:56,000
mas não sei onde aqui ainda é,

230
00:12:56,000 --> 00:12:59,000
então nós realmente não tenho memória alocada para buffer.

231
00:12:59,000 --> 00:13:03,000
Além disso, o que você também não, mesmo dizendo scanf?

232
00:13:03,000 --> 00:13:06,000
Suponha que este era um pedaço de memória, e não era um valor de lixo,

233
00:13:06,000 --> 00:13:09,000
mas você ainda não está dizendo scanf algo importante.

234
00:13:09,000 --> 00:13:12,000
[Estudante] onde ele realmente é, o comercial.

235
00:13:12,000 --> 00:13:15,000
Ampersand, portanto, neste caso, está tudo bem.

236
00:13:15,000 --> 00:13:18,000
Porque o buffer já está declarado como um ponteiro

237
00:13:18,000 --> 00:13:22,000
com a peça * de sintaxe, nós não precisamos de usar e comercial

238
00:13:22,000 --> 00:13:25,000
porque é já um endereço, mas eu acho que ouvi-lo aqui.

239
00:13:25,000 --> 00:13:27,000
[Estudante] Como grande é?

240
00:13:27,000 --> 00:13:29,000
Bom, não estamos dizendo scanf quão grande esse buffer é,

241
00:13:29,000 --> 00:13:32,000
o que significa que, mesmo se fosse um tampão ponteiro,

242
00:13:32,000 --> 00:13:35,000
estamos dizendo scanf, colocar uma corda aqui,

243
00:13:35,000 --> 00:13:38,000
mas aqui pode ser de 2 bytes, que pode ser de 10 bytes, que poderia ser um megabyte.

244
00:13:38,000 --> 00:13:41,000
Scanf não tem idéia, e porque este é um pedaço da memória

245
00:13:41,000 --> 00:13:43,000
presumivelmente, não é uma seqüência ainda.

246
00:13:43,000 --> 00:13:48,000
É apenas uma corda uma vez que você escrever caracteres e um \ 0 para o bloco de memória.

247
00:13:48,000 --> 00:13:51,000
Agora é só algum pedaço de memória.

248
00:13:51,000 --> 00:13:55,000
Scanf não vai saber quando parar de escrever para esse endereço.

249
00:13:55,000 --> 00:13:59,000
>> Se você lembrar alguns exemplos no passado em que eu aleatoriamente digitados no teclado

250
00:13:59,000 --> 00:14:03,000
tentando estourar um buffer, e nós conversamos na sexta-feira sobre exatamente isso.

251
00:14:03,000 --> 00:14:07,000
Se um adversário de alguma forma, injeta em seu programa uma palavra muito maior

252
00:14:07,000 --> 00:14:10,000
ou frase ou então você estava esperando você pode invadida

253
00:14:10,000 --> 00:14:13,000
um pedaço de memória, que pode ter conseqüências ruins,

254
00:14:13,000 --> 00:14:15,000
como assumir todo o programa em si.

255
00:14:15,000 --> 00:14:17,000
Precisamos corrigir isso de alguma forma.

256
00:14:17,000 --> 00:14:20,000
Deixe-me afastar e ir para a versão 3 do programa.

257
00:14:20,000 --> 00:14:22,000
Isso é um pouco melhor.

258
00:14:22,000 --> 00:14:24,000
Nesta versão, notar a diferença.

259
00:14:24,000 --> 00:14:27,000
Na linha 16, estou novamente declarar uma variável chamada tampão,

260
00:14:27,000 --> 00:14:29,000
mas o que é isso agora?

261
00:14:29,000 --> 00:14:33,000
É uma matriz de 16 caracteres.

262
00:14:33,000 --> 00:14:36,000
Isso é bom, porque isso significa que eu posso agora dizer scanf

263
00:14:36,000 --> 00:14:39,000
aqui é um pedaço de memória real.

264
00:14:39,000 --> 00:14:42,000
Você quase pode pensar em matrizes como ponteiros, agora,

265
00:14:42,000 --> 00:14:44,000
mesmo que eles não são realmente equivalentes.

266
00:14:44,000 --> 00:14:47,000
Eles se comportam de maneira diferente em diferentes contextos.

267
00:14:47,000 --> 00:14:50,000
Mas é certamente o caso que o buffer é referência

268
00:14:50,000 --> 00:14:53,000
16 caracteres contíguos porque é isso que é uma matriz

269
00:14:53,000 --> 00:14:55,000
e tem sido por algumas semanas agora.

270
00:14:55,000 --> 00:14:59,000
>> Aqui, eu estou dizendo scanf aqui está um pedaço da memória.

271
00:14:59,000 --> 00:15:01,000
Desta vez, é na verdade um pedaço da memória,

272
00:15:01,000 --> 00:15:07,000
mas porque é que este programa ainda explorável?

273
00:15:07,000 --> 00:15:11,000
O que há de errado ainda?

274
00:15:11,000 --> 00:15:14,000
Eu disse me dar 16 bytes, mas-

275
00:15:14,000 --> 00:15:16,000
[Aluno] O que se eles tipo em mais de 16 anos?

276
00:15:16,000 --> 00:15:20,000
Exatamente, e se o usuário digita 17 caracteres ou caracteres 1700?

277
00:15:20,000 --> 00:15:23,000
Na verdade, vamos ver se não podemos tropeçar esse erro agora.

278
00:15:23,000 --> 00:15:25,000
É melhor, mas não perfeito.

279
00:15:25,000 --> 00:15:28,000
Deixe-me ir em frente e correr fazer scanf3 para compilar este programa.

280
00:15:28,000 --> 00:15:34,000
Deixa-me correr scanf3, String por favor: Olá, e parece que estamos bem.

281
00:15:34,000 --> 00:15:37,000
Deixe-me tentar um pouco mais, Olá lá.

282
00:15:37,000 --> 00:15:42,000
Ok, vamos fazer Olá lá como você está hoje, Enter.

283
00:15:42,000 --> 00:15:54,000
Obtendo tipo de sorte aqui, vamos dizer Olá lá como você está.

284
00:15:54,000 --> 00:15:56,000
Droga.

285
00:15:56,000 --> 00:16:03,000
Ok, então tivemos sorte. Vamos ver se não podemos consertar isso.

286
00:16:03,000 --> 00:16:06,000
Não, isso não vai me deixar copiar.

287
00:16:06,000 --> 00:16:09,000
Vamos tentar de novo.

288
00:16:09,000 --> 00:16:12,000
Tudo bem, preparem-se.

289
00:16:12,000 --> 00:16:20,000
Vamos ver quanto tempo eu posso fingir foco enquanto ainda está fazendo isso.

290
00:16:20,000 --> 00:16:23,000
Droga. Isso é bastante apropriado, na verdade.

291
00:16:23,000 --> 00:16:26,000
Lá vamos nós.

292
00:16:26,000 --> 00:16:30,000
Ponto feito.

293
00:16:30,000 --> 00:16:34,000
>> Isto, embaraçando embora também seja, é também uma das fontes de grande confusão

294
00:16:34,000 --> 00:16:38,000
ao escrever programas que têm bugs, porque eles se manifestam

295
00:16:38,000 --> 00:16:40,000
só de vez em quando, às vezes.

296
00:16:40,000 --> 00:16:43,000
A realidade é que, mesmo se o código está completamente quebrado,

297
00:16:43,000 --> 00:16:46,000
ele só poderia ser completamente quebrado de vez em quando

298
00:16:46,000 --> 00:16:49,000
porque às vezes, essencialmente, o que acontece é o sistema operacional aloca

299
00:16:49,000 --> 00:16:52,000
um pouco mais de memória do que você realmente precisa, por qualquer razão,

300
00:16:52,000 --> 00:16:57,000
e para que ninguém mais está usando a memória logo após o seu pedaço de 16 caracteres,

301
00:16:57,000 --> 00:17:01,000
por isso, se você vai para 17, 18, 19, qualquer que seja, não é um negócio tão grande.

302
00:17:01,000 --> 00:17:04,000
Agora, o computador, mesmo que não falha nesse ponto,

303
00:17:04,000 --> 00:17:09,000
pode, eventualmente, usar o número de bytes de 17 ou 18 ou 19 para outra coisa,

304
00:17:09,000 --> 00:17:14,000
altura em que os dados que você colocar ali, ainda que excessivamente longo,

305
00:17:14,000 --> 00:17:18,000
vai ser substituídas potencialmente por alguma outra função.

306
00:17:18,000 --> 00:17:21,000
Não é necessariamente vai permanecer intacta,

307
00:17:21,000 --> 00:17:23,000
mas não vai necessariamente provocar uma falha seg.

308
00:17:23,000 --> 00:17:26,000
Mas, neste caso, eu finalmente desde caracteres suficientes

309
00:17:26,000 --> 00:17:29,000
que eu essencialmente ultrapassado meu segmento de memória, e pronto,

310
00:17:29,000 --> 00:17:33,000
o sistema operacional, disse: "Desculpe, isso não é falha de segmentação de boa qualidade."

311
00:17:33,000 --> 00:17:38,000
>> E vamos ver agora se o que permanece aqui no meu diretório

312
00:17:38,000 --> 00:17:40,000
perceber que eu tenho esse arquivo aqui, o núcleo.

313
00:17:40,000 --> 00:17:42,000
Note-se que esta é mais uma vez chamado de core dump.

314
00:17:42,000 --> 00:17:46,000
É essencialmente um arquivo que contém o conteúdo da memória de seu programa

315
00:17:46,000 --> 00:17:48,000
no ponto em que deixou de funcionar,

316
00:17:48,000 --> 00:17:51,000
e apenas para tentar um pequeno exemplo aqui, deixe-me entrar aqui

317
00:17:51,000 --> 00:17:57,000
e executar o gdb no scanf3 e especifique um terceiro argumento chamado de núcleo,

318
00:17:57,000 --> 00:18:01,000
e notar aqui que se eu listar o código,

319
00:18:01,000 --> 00:18:06,000
nós vamos ser capazes, como de costume com o gdb para começar a caminhar através deste programa,

320
00:18:06,000 --> 00:18:10,000
e eu possa executá-lo e assim que eu bater-como com o comando passo na gdb-

321
00:18:10,000 --> 00:18:13,000
assim que atingiu a linha de buggy potencialmente depois de digitar uma seqüência enorme,

322
00:18:13,000 --> 00:18:16,000
Eu vou ser capaz de realmente identificá-lo aqui.

323
00:18:16,000 --> 00:18:19,000
Mais sobre isso, no entanto, na seção em termos de core dumps

324
00:18:19,000 --> 00:18:22,000
e assim por diante, de modo que você pode realmente bisbilhotar dentro do core dump

325
00:18:22,000 --> 00:18:27,000
e ver em que linha o programa não você.

326
00:18:27,000 --> 00:18:32,000
Quaisquer perguntas, então em ponteiros e endereços?

327
00:18:32,000 --> 00:18:36,000
Porque hoje, nós vamos começar a tomar por certo que essas coisas existem

328
00:18:36,000 --> 00:18:40,000
e sabemos exatamente o que eles são.

329
00:18:40,000 --> 00:18:42,000
Sim.

330
00:18:42,000 --> 00:18:46,000
>> [Estudante] Como é que você não tem que colocar um comercial ao lado da parte-

331
00:18:46,000 --> 00:18:48,000
Boa pergunta.

332
00:18:48,000 --> 00:18:51,000
Como é que eu não tenho que colocar um comercial ao lado da matriz de caracteres como eu fiz anteriormente

333
00:18:51,000 --> 00:18:53,000
com a maioria dos nossos exemplos?

334
00:18:53,000 --> 00:18:55,000
A resposta curta é matrizes são um pouco especial.

335
00:18:55,000 --> 00:18:59,000
Você quase pode pensar um tampão como sendo realmente um endereço,

336
00:18:59,000 --> 00:19:03,000
e isso só acontece de ser o caso de que a notação de colchete

337
00:19:03,000 --> 00:19:06,000
é uma conveniência para que possamos entrar em suporte 0, faixa 1,

338
00:19:06,000 --> 00:19:10,000
faixa 2, sem ter de utilizar a notação *.

339
00:19:10,000 --> 00:19:13,000
Isso é um pouco de uma mentira porque as matrizes e ponteiros

340
00:19:13,000 --> 00:19:17,000
são, na verdade, um pouco diferente, mas que muitas vezes pode, mas nem sempre ser usados ​​indistintamente.

341
00:19:17,000 --> 00:19:21,000
Em suma, quando a função está esperando um ponteiro para um bloco de memória,

342
00:19:21,000 --> 00:19:24,000
você pode passar um endereço que foi retornado por malloc,

343
00:19:24,000 --> 00:19:29,000
e vamos ver malloc novamente antes de tempo, ou você pode passar-lhe o nome de uma matriz.

344
00:19:29,000 --> 00:19:32,000
Você não tem de fazer comercial com matrizes porque eles já estão

345
00:19:32,000 --> 00:19:34,000
essencialmente, como endereços.

346
00:19:34,000 --> 00:19:36,000
Essa é a única exceção.

347
00:19:36,000 --> 00:19:39,000
Os colchetes tornam especiais.

348
00:19:39,000 --> 00:19:41,000
>> Você poderia colocar um comercial ao lado do tampão?

349
00:19:41,000 --> 00:19:43,000
Não neste caso.

350
00:19:43,000 --> 00:19:46,000
Isso não iria funcionar porque, novamente, desta canto caso

351
00:19:46,000 --> 00:19:49,000
onde matrizes não são muito realmente endereços.

352
00:19:49,000 --> 00:19:54,000
Mas vamos talvez volte para que em pouco tempo com outros exemplos.

353
00:19:54,000 --> 00:19:56,000
Vamos tentar resolver um problema aqui.

354
00:19:56,000 --> 00:20:00,000
Temos uma estrutura de dados que temos vindo a utilizar durante algum tempo conhecida como uma matriz.

355
00:20:00,000 --> 00:20:02,000
O caso em questão, é o que acabamos de ter.

356
00:20:02,000 --> 00:20:04,000
Mas matrizes têm algum upsides e desvantagens.

357
00:20:04,000 --> 00:20:06,000
Matrizes são agradáveis ​​porque?

358
00:20:06,000 --> 00:20:11,000
O que é uma coisa que você gosta, na medida em que você gosta matrizes-sobre matrizes?

359
00:20:11,000 --> 00:20:13,000
O que é conveniente sobre eles? O que é interessante?

360
00:20:13,000 --> 00:20:18,000
Por que nós apresentá-los em primeiro lugar?

361
00:20:18,000 --> 00:20:20,000
Sim.

362
00:20:20,000 --> 00:20:27,000
[Estudante] Eles podem armazenar uma grande quantidade de dados, e você não tem que usar uma coisa toda.

363
00:20:27,000 --> 00:20:29,000
Você pode usar uma seção.

364
00:20:29,000 --> 00:20:32,000
Bom, com uma matriz você pode armazenar uma grande quantidade de dados,

365
00:20:32,000 --> 00:20:35,000
e você não necessariamente tem que usar tudo isso, para que você possa overallocate,

366
00:20:35,000 --> 00:20:39,000
o que pode ser conveniente se você não sabe de antemão quantos de algo que esperar.

367
00:20:39,000 --> 00:20:41,000
>> GetString é um exemplo perfeito.

368
00:20:41,000 --> 00:20:44,000
GetString, escrito por nós, não tem idéia de quantos chars que esperar,

369
00:20:44,000 --> 00:20:48,000
de modo que o fato de que podemos alocar blocos de memória contígua é bom.

370
00:20:48,000 --> 00:20:51,000
Matrizes também resolver um problema que vimos há algumas semanas agora

371
00:20:51,000 --> 00:20:54,000
onde o código começa a transformar-se em algo muito mal projetado.

372
00:20:54,000 --> 00:20:57,000
Lembre-se que eu criei uma estrutura estudante chamado David,

373
00:20:57,000 --> 00:21:00,000
e depois que foi realmente uma alternativa, porém,

374
00:21:00,000 --> 00:21:04,000
a ter uma variável chamada nome e outra variável chamada, eu acho, casa,

375
00:21:04,000 --> 00:21:08,000
e outra variável chamada ID, porque nessa história então eu queria introduzir algo mais

376
00:21:08,000 --> 00:21:11,000
Rob gosta no programa, então eu decidi esperar um minuto,

377
00:21:11,000 --> 00:21:13,000
Eu preciso mudar o nome destas variáveis.

378
00:21:13,000 --> 00:21:16,000
Vamos chamar de meu nome1, ID1, house1.

379
00:21:16,000 --> 00:21:20,000
Vamos chamar de Rob nome2, house2, ID2.

380
00:21:20,000 --> 00:21:22,000
Mas, então, espere um minuto, o que dizer de Tommy?

381
00:21:22,000 --> 00:21:24,000
Então nós tivemos três variáveis ​​mais.

382
00:21:24,000 --> 00:21:27,000
Nós introduzimos alguém, quatro conjuntos de variáveis.

383
00:21:27,000 --> 00:21:30,000
O mundo começou a ficar confuso muito rapidamente,

384
00:21:30,000 --> 00:21:33,000
para que introduziu estruturas, eo que é interessante sobre uma estrutura?

385
00:21:33,000 --> 00:21:39,000
O que faz um struct C permitem que você faça?

386
00:21:39,000 --> 00:21:42,000
É realmente estranho hoje.

387
00:21:42,000 --> 00:21:44,000
O quê? >> [Resposta do aluno inaudível]

388
00:21:44,000 --> 00:21:47,000
Sim, especificamente, typedef permite criar um novo tipo de dados,

389
00:21:47,000 --> 00:21:51,000
e estrutura, a palavra-chave struct, permite encapsular

390
00:21:51,000 --> 00:21:54,000
peças conceitualmente relacionados de dados juntamente

391
00:21:54,000 --> 00:21:56,000
e, posteriormente, chamá-los de algo como um estudante.

392
00:21:56,000 --> 00:21:58,000
>> Isso foi bom, porque agora podemos modelar

393
00:21:58,000 --> 00:22:03,000
espécie muito mais consistente conceitualmente a noção de um estudante em uma variável

394
00:22:03,000 --> 00:22:07,000
em vez de ter uma forma arbitrária para uma cadeia, um para um ID, e assim por diante.

395
00:22:07,000 --> 00:22:10,000
Matrizes são bons porque eles nos permitem começar a limpar o nosso código.

396
00:22:10,000 --> 00:22:13,000
Mas o que é uma desvantagem agora de uma matriz?

397
00:22:13,000 --> 00:22:15,000
O que você não pode fazer? Sim.

398
00:22:15,000 --> 00:22:17,000
[Estudante] Você tem que saber o quão grande ela é.

399
00:22:17,000 --> 00:22:19,000
Você tem que saber como é grande, por isso é um tipo de dor.

400
00:22:19,000 --> 00:22:21,000
Aqueles de vocês com experiência anterior em programação sabe que em um monte de línguas,

401
00:22:21,000 --> 00:22:24,000
como Java, você pode pedir um pedaço de memória, especificamente uma matriz,

402
00:22:24,000 --> 00:22:28,000
quão grande é você, com um comprimento de, propriedade, por assim dizer, e isso é realmente conveniente.

403
00:22:28,000 --> 00:22:32,000
Em C, você não pode sequer chamar strlen em uma matriz genérica

404
00:22:32,000 --> 00:22:35,000
porque strlen, como a palavra indica, é apenas para cordas,

405
00:22:35,000 --> 00:22:39,000
e você pode descobrir o comprimento de uma cadeia por causa deste convenção humana

406
00:22:39,000 --> 00:22:43,000
de ter um \ 0, mas um conjunto, mais genericamente, é apenas um pedaço de memória.

407
00:22:43,000 --> 00:22:46,000
Se é uma matriz de inteiros, não vai ser algum caractere especial

408
00:22:46,000 --> 00:22:48,000
no final esperando por você.

409
00:22:48,000 --> 00:22:50,000
Você tem que lembrar o comprimento de uma matriz.

410
00:22:50,000 --> 00:22:54,000
Outro ponto negativo de uma matriz elevou sua cabeça em GetString si.

411
00:22:54,000 --> 00:22:59,000
O que é outra desvantagem de uma matriz?

412
00:22:59,000 --> 00:23:01,000
Senhor, só eu e você hoje.

413
00:23:01,000 --> 00:23:04,000
[Resposta do aluno inaudível] >> É o quê?

414
00:23:04,000 --> 00:23:06,000
Ele é declarado na pilha.

415
00:23:06,000 --> 00:23:09,000
Ok, declarou na pilha. Por que você não gosta?

416
00:23:09,000 --> 00:23:13,000
[Estudante], porque ela é reutilizada.

417
00:23:13,000 --> 00:23:15,000
Ele fica reutilizados.

418
00:23:15,000 --> 00:23:18,000
Ok, se você usar uma matriz para alocar memória,

419
00:23:18,000 --> 00:23:21,000
você não pode, por exemplo, devolvê-lo, porque é na pilha.

420
00:23:21,000 --> 00:23:23,000
Ok, isso é uma desvantagem.

421
00:23:23,000 --> 00:23:25,000
E quanto a um outro com uma matriz?

422
00:23:25,000 --> 00:23:28,000
Uma vez que você afectá-lo, você é do tipo parafusado, se você precisar de mais espaço

423
00:23:28,000 --> 00:23:30,000
do que a matriz tem.

424
00:23:30,000 --> 00:23:34,000
>> Então, nós introduzimos, malloc recall, que nos deu a capacidade de alocar dinamicamente a memória.

425
00:23:34,000 --> 00:23:37,000
Mas o que se tentou um mundo completamente diferente?

426
00:23:37,000 --> 00:23:40,000
O que se queria resolver alguns desses problemas

427
00:23:40,000 --> 00:23:45,000
por isso, em vez minha caneta-dorme aqui-

428
00:23:45,000 --> 00:23:51,000
o que se queria essencialmente em vez de criar um mundo que já não é assim?

429
00:23:51,000 --> 00:23:56,000
Trata-se de uma matriz, e, é claro, este tipo de deterioração, uma vez que atingiu o fim da matriz,

430
00:23:56,000 --> 00:24:00,000
e agora não tem mais espaço para outro inteiro ou outro personagem.

431
00:24:00,000 --> 00:24:03,000
E se nós meio que preventivamente dizer bem, por que não vamos relaxar

432
00:24:03,000 --> 00:24:07,000
esta exigência de que todos esses pedaços de memória ser contíguo volta para trás,

433
00:24:07,000 --> 00:24:10,000
e por que não, quando eu preciso de um int ou um char,

434
00:24:10,000 --> 00:24:12,000
me dê espaço para um deles?

435
00:24:12,000 --> 00:24:14,000
E quando eu precisar de outro, dá-me um outro espaço,

436
00:24:14,000 --> 00:24:16,000
e quando eu precisar de outro, dá-me um outro espaço.

437
00:24:16,000 --> 00:24:19,000
A vantagem de que agora é que, se alguém

438
00:24:19,000 --> 00:24:21,000
leva a memória por aqui, não é grande coisa.

439
00:24:21,000 --> 00:24:25,000
Vou levar este pedaço adicional de memória aqui e depois este.

440
00:24:25,000 --> 00:24:28,000
>> Agora, o único problema aqui é que esta quase se sente como eu tenho

441
00:24:28,000 --> 00:24:30,000
todo um conjunto de variáveis ​​diferentes.

442
00:24:30,000 --> 00:24:33,000
Isso sente-se como cinco diferentes variáveis ​​potencialmente.

443
00:24:33,000 --> 00:24:36,000
Mas o que se roubar uma idéia de cordas

444
00:24:36,000 --> 00:24:41,000
em que, de alguma maneira vincular essas coisas juntas conceitualmente, e que se eu fizesse isso?

445
00:24:41,000 --> 00:24:44,000
Esta é a minha flecha muito mal desenhado.

446
00:24:44,000 --> 00:24:46,000
Mas suponha que cada um desses pedaços de memória

447
00:24:46,000 --> 00:24:52,000
apontou para o outro, e esse cara, que não tem nenhum irmão à sua direita,

448
00:24:52,000 --> 00:24:54,000
não tem nenhuma seta tal.

449
00:24:54,000 --> 00:24:56,000
Este é de fato o que é chamado de uma lista ligada.

450
00:24:56,000 --> 00:25:00,000
Esta é uma nova estrutura de dados que nos permite alocar um bloco de memória,

451
00:25:00,000 --> 00:25:03,000
depois outra, depois outra, depois outra, a qualquer hora que queremos

452
00:25:03,000 --> 00:25:07,000
durante um programa, e lembre-se que todos eles são de alguma forma relacionados

453
00:25:07,000 --> 00:25:11,000
por, literalmente, encadeando-os, e nós fizemos isso pictoricamente aqui com uma seta.

454
00:25:11,000 --> 00:25:15,000
Mas no código, o que seria o mecanismo através do qual você pudesse de alguma forma se conectar,

455
00:25:15,000 --> 00:25:20,000
quase como Scratch, um pedaço de um outro pedaço?

456
00:25:20,000 --> 00:25:22,000
Nós poderíamos usar um ponteiro, certo?

457
00:25:22,000 --> 00:25:25,000
Porque realmente a seta que vai da praça superior esquerdo,

458
00:25:25,000 --> 00:25:31,000
esse cara aqui a esta, poderia conter dentro da praça

459
00:25:31,000 --> 00:25:34,000
não apenas alguns ints, não apenas alguns char, mas o que se eu realmente alocada

460
00:25:34,000 --> 00:25:37,000
um pouco de espaço extra para que agora,

461
00:25:37,000 --> 00:25:41,000
cada um dos meus pedaços de memória, mesmo que isso vai me custar,

462
00:25:41,000 --> 00:25:45,000
agora parece um pouco mais rectangular em que um dos blocos de memória

463
00:25:45,000 --> 00:25:47,000
é utilizado para um número, assim como o número 1,

464
00:25:47,000 --> 00:25:50,000
e, em seguida, se este tipo armazena o número 2,

465
00:25:50,000 --> 00:25:52,000
este pedaço de outra memória é usada para uma seta,

466
00:25:52,000 --> 00:25:54,000
ou mais concretamente, um ponteiro.

467
00:25:54,000 --> 00:25:59,000
E suponha que eu armazenar o número 3 por aqui, enquanto eu uso isso para apontar para esse cara,

468
00:25:59,000 --> 00:26:02,000
e agora esse cara, vamos supor que eu só quero esses três pedaços de memória.

469
00:26:02,000 --> 00:26:05,000
Eu vou desenhar uma linha por isso, indicando nulo.

470
00:26:05,000 --> 00:26:07,000
Não há personagem adicional.

471
00:26:07,000 --> 00:26:10,000
>> Na verdade, esta é a forma como nós podemos ir sobre a implementação de

472
00:26:10,000 --> 00:26:12,000
algo que é chamado de uma lista ligada.

473
00:26:12,000 --> 00:26:18,000
Uma lista ligada é uma nova estrutura de dados, e é um trampolim para a

474
00:26:18,000 --> 00:26:21,000
muito amador estruturas de dados que começam a resolver problemas

475
00:26:21,000 --> 00:26:23,000
ao longo das linhas de Facebook tipo de problemas e problemas do tipo Google

476
00:26:23,000 --> 00:26:26,000
onde você tem enormes conjuntos de dados, e já não corta

477
00:26:26,000 --> 00:26:29,000
para armazenar tudo de forma contígua e usar algo como busca linear

478
00:26:29,000 --> 00:26:31,000
ou mesmo algo como pesquisa binária.

479
00:26:31,000 --> 00:26:33,000
Você quer mesmo melhores tempos de execução.

480
00:26:33,000 --> 00:26:37,000
De fato, um dos objetivos primordiais vamos falar mais tarde esta semana ou na próxima

481
00:26:37,000 --> 00:26:41,000
é um algoritmo cujo tempo de corrida é constante.

482
00:26:41,000 --> 00:26:44,000
Em outras palavras, tem sempre a mesma quantidade de tempo, não importa

483
00:26:44,000 --> 00:26:47,000
como é grande a entrada, e que seria de fato interessante,

484
00:26:47,000 --> 00:26:49,000
até mais do que algo logarítmica.

485
00:26:49,000 --> 00:26:51,000
O que é isso na tela aqui?

486
00:26:51,000 --> 00:26:55,000
Cada um dos retângulos é exatamente o que eu desenhei a mão.

487
00:26:55,000 --> 00:26:59,000
Mas a coisa toda a maneira à esquerda é uma variável especial.

488
00:26:59,000 --> 00:27:02,000
Vai ser um ponteiro único porque a única pegadinha

489
00:27:02,000 --> 00:27:04,000
com uma lista ligada, como essas coisas são chamados,

490
00:27:04,000 --> 00:27:09,000
é que você tem para se agarrar a uma final da lista de relacionados.

491
00:27:09,000 --> 00:27:13,000
>> Assim como com uma corda, você tem que saber o endereço do primeiro caractere.

492
00:27:13,000 --> 00:27:15,000
Mesma coisa para listas ligadas.

493
00:27:15,000 --> 00:27:19,000
Você tem que saber o endereço do primeiro pedaço de memória

494
00:27:19,000 --> 00:27:25,000
porque de lá, você pode chegar a qualquer um outro.

495
00:27:25,000 --> 00:27:27,000
Desvantagem.

496
00:27:27,000 --> 00:27:30,000
Qual o preço que estamos pagando por essa versatilidade de ter um dinamicamente

497
00:27:30,000 --> 00:27:34,000
estrutura de dados de tamanho considerável que se alguma vez precisar de mais memória, tudo bem,

498
00:27:34,000 --> 00:27:37,000
simplesmente alocar mais um pedaço e desenhar um ponteiro de

499
00:27:37,000 --> 00:27:39,000
da antiga para a nova cauda da lista?

500
00:27:39,000 --> 00:27:41,000
Sim.

501
00:27:41,000 --> 00:27:43,000
[Estudante] É preciso espaço de cerca de duas vezes mais.

502
00:27:43,000 --> 00:27:45,000
Ele ocupa um espaço duas vezes maior, de modo que é definitivamente uma desvantagem, e temos visto isso

503
00:27:45,000 --> 00:27:48,000
troca antes entre tempo e espaço e flexibilidade

504
00:27:48,000 --> 00:27:51,000
onde por agora, não precisamos de 32 bits para cada um desses números.

505
00:27:51,000 --> 00:27:57,000
Nós realmente precisamos de 64, 32 para o número e 32 para o ponteiro.

506
00:27:57,000 --> 00:27:59,000
Mas, ei, eu tenho 2 gigabytes de memória RAM.

507
00:27:59,000 --> 00:28:02,000
Adicionando mais 32 bits aqui e aqui não parece que de um grande negócio.

508
00:28:02,000 --> 00:28:05,000
Mas para grandes conjuntos de dados, definitivamente acrescenta-se, literalmente, o dobro.

509
00:28:05,000 --> 00:28:09,000
O que é outra desvantagem agora, ou o que é que vamos característica desistir,

510
00:28:09,000 --> 00:28:12,000
se representar listas de coisas com uma lista ligada e não uma matriz?

511
00:28:12,000 --> 00:28:14,000
[Estudante] Você não pode atravessá-lo para trás.

512
00:28:14,000 --> 00:28:16,000
Você não pode atravessá-lo para trás, então você é do tipo parafusado, se você está andando

513
00:28:16,000 --> 00:28:19,000
da esquerda para a direita, com um loop ou um loop while

514
00:28:19,000 --> 00:28:21,000
e então você percebe, "Oh, eu quero voltar para o início da lista."

515
00:28:21,000 --> 00:28:26,000
Você não pode porque estes ponteiros só ir da esquerda para a direita, como as setas indicam.

516
00:28:26,000 --> 00:28:29,000
>> Agora, você poderia lembrar o início da lista, com uma outra variável,

517
00:28:29,000 --> 00:28:31,000
mas isso é uma complexidade para manter em mente.

518
00:28:31,000 --> 00:28:35,000
Uma matriz, não importa o quão longe você vá, você sempre pode fazer menos, menos, menos, menos

519
00:28:35,000 --> 00:28:37,000
e voltar de onde você veio.

520
00:28:37,000 --> 00:28:40,000
O que é outra desvantagem aqui? Sim.

521
00:28:40,000 --> 00:28:43,000
[Pergunta estudante inaudível]

522
00:28:43,000 --> 00:28:47,000
Você poderia, então você realmente acabou de propor uma estrutura de dados chamado de lista duplamente ligada,

523
00:28:47,000 --> 00:28:50,000
e, na verdade, você gostaria de acrescentar outro ponteiro para cada um desses rectângulos

524
00:28:50,000 --> 00:28:53,000
que vai outra direcção, ao contrário do que

525
00:28:53,000 --> 00:28:55,000
é que agora você pode atravessar para o outro,

526
00:28:55,000 --> 00:28:59,000
a desvantagem de que agora você está usando três vezes mais memória do que costumávamos

527
00:28:59,000 --> 00:29:04,000
e também aumentar a complexidade em termos de código que você tem que escrever para acertar.

528
00:29:04,000 --> 00:29:08,000
Mas todos estes são talvez compensações razoáveis, se a reversão é mais importante.

529
00:29:08,000 --> 00:29:10,000
Sim.

530
00:29:10,000 --> 00:29:12,000
[Estudante] Você também não pode ter uma lista 2D vinculado.

531
00:29:12,000 --> 00:29:16,000
Bom, você não pode realmente ter uma lista 2D ligados.

532
00:29:16,000 --> 00:29:18,000
Você poderia. Não é tão fácil como uma matriz.

533
00:29:18,000 --> 00:29:21,000
Como um array, você faz suporte aberto, suporte fechada, suporte aberto, fechado suporte,

534
00:29:21,000 --> 00:29:23,000
e você terá uma estrutura 2-dimensional.

535
00:29:23,000 --> 00:29:26,000
Você poderia implementar uma lista de 2-dimensional ligados

536
00:29:26,000 --> 00:29:29,000
Se você adicionar, como você propôs-um ponteiro terceiro a cada uma dessas coisas,

537
00:29:29,000 --> 00:29:34,000
e se você pensar em uma outra lista que vem em você estilo 3D

538
00:29:34,000 --> 00:29:40,000
da tela para todos nós, que é apenas uma outra corrente de algum tipo.

539
00:29:40,000 --> 00:29:45,000
Nós poderíamos fazer isso, mas não é tão simples como escrever suporte aberto, colchete. Sim.

540
00:29:45,000 --> 00:29:48,000
[Pergunta estudante inaudível]

541
00:29:48,000 --> 00:29:50,000
Bom, então isso é um retrocesso real.

542
00:29:50,000 --> 00:29:54,000
>> Esses algoritmos que temos pined mais, como oh, busca binária,

543
00:29:54,000 --> 00:29:57,000
você pode pesquisar uma matriz de números na placa

544
00:29:57,000 --> 00:30:01,000
ou um livro de telefone muito mais rapidamente se utilizar dividir e conquistar

545
00:30:01,000 --> 00:30:05,000
e um algoritmo de busca binária, mas busca binária necessários dois pressupostos.

546
00:30:05,000 --> 00:30:09,000
Um, que os dados foram classificados.

547
00:30:09,000 --> 00:30:11,000
Agora, nós podemos manter este presumivelmente classificados,

548
00:30:11,000 --> 00:30:14,000
talvez por isso não é uma preocupação, mas de busca binária também assumiu

549
00:30:14,000 --> 00:30:18,000
que você teve acesso aleatório à lista de números,

550
00:30:18,000 --> 00:30:21,000
e uma matriz permite que você tenha acesso aleatório, e de acesso aleatório,

551
00:30:21,000 --> 00:30:24,000
Quero dizer, se você está dado uma matriz, quanto tempo leva para você

552
00:30:24,000 --> 00:30:26,000
para chegar ao suporte de 0?

553
00:30:26,000 --> 00:30:29,000
Uma operação, basta usar [0] e você está aí.

554
00:30:29,000 --> 00:30:33,000
Quantos passos que é preciso para chegar ao local 10?

555
00:30:33,000 --> 00:30:36,000
Um passo, é só ir para [10] e você está lá.

556
00:30:36,000 --> 00:30:40,000
Por outro lado, como você começa para o número inteiro 10 em uma lista ligada?

557
00:30:40,000 --> 00:30:42,000
Você tem que começar no início, porque você só está lembrando

558
00:30:42,000 --> 00:30:45,000
o início de uma lista ligada, como uma string está sendo lembrado

559
00:30:45,000 --> 00:30:48,000
pelo endereço de seu primeiro char, e ao descobrir que int 10

560
00:30:48,000 --> 00:30:53,000
ou que o caráter 10 em uma seqüência, você tem que procurar a coisa toda.

561
00:30:53,000 --> 00:30:55,000
>> Novamente, não estamos resolvendo todos os nossos problemas.

562
00:30:55,000 --> 00:31:00,000
Estamos introduzindo novos, mas realmente depende do que você está tentando projetar para.

563
00:31:00,000 --> 00:31:04,000
Em termos de aplicação do presente, podemos pedir uma idéia de que a estrutura do aluno.

564
00:31:04,000 --> 00:31:07,000
A sintaxe é muito semelhante, só que agora, a idéia é um pouco mais abstrato

565
00:31:07,000 --> 00:31:09,000
de casa e nome e ID.

566
00:31:09,000 --> 00:31:13,000
Mas proponho que nós poderíamos ter uma estrutura de dados em C

567
00:31:13,000 --> 00:31:17,000
que é chamado de nó, como a última palavra sobre o slide sugere,

568
00:31:17,000 --> 00:31:21,000
dentro de um nó, e um nó é apenas um contêiner genérico em ciência da computação.

569
00:31:21,000 --> 00:31:25,000
Geralmente é desenhada como um círculo ou um quadrado ou retângulo, como temos feito.

570
00:31:25,000 --> 00:31:27,000
E nesta estrutura de dados, que tem um int, n,

571
00:31:27,000 --> 00:31:29,000
de modo que é o número que eu quiser armazenar.

572
00:31:29,000 --> 00:31:36,000
Mas o que é essa segunda linha, struct node * próximo?

573
00:31:36,000 --> 00:31:40,000
Por que isso é correto, ou qual o papel que este jogo coisa,

574
00:31:40,000 --> 00:31:42,000
mesmo que seja um pouco enigmática, à primeira vista?

575
00:31:42,000 --> 00:31:44,000
Sim.

576
00:31:44,000 --> 00:31:46,000
[Resposta do aluno inaudível]

577
00:31:46,000 --> 00:31:50,000
Exatamente, por isso o tipo * do espólio que é um ponteiro de algum tipo.

578
00:31:50,000 --> 00:31:53,000
O nome deste ponteiro é arbitrariamente seguinte,

579
00:31:53,000 --> 00:32:00,000
mas poderíamos ter chamado qualquer coisa que queremos, mas o que faz este ponto ponteiro para?

580
00:32:00,000 --> 00:32:03,000
[Estudante] Outro nó. >> Exatamente, ele aponta para outro nó tal.

581
00:32:03,000 --> 00:32:05,000
>> Agora, isso é uma espécie de curiosidade de C.

582
00:32:05,000 --> 00:32:09,000
Lembre-se que C é lido por um top compilador para baixo, da esquerda para a direita,

583
00:32:09,000 --> 00:32:13,000
que significa que se-isso é um pouco diferente do que fizemos com o aluno.

584
00:32:13,000 --> 00:32:16,000
Quando definimos um estudante, que se não colocar uma palavra lá.

585
00:32:16,000 --> 00:32:18,000
Ele apenas disse typedef.

586
00:32:18,000 --> 00:32:20,000
Então nós tivemos int id nome, corda, corda casa,

587
00:32:20,000 --> 00:32:23,000
e, em seguida, na parte inferior do estudante da estrutura.

588
00:32:23,000 --> 00:32:26,000
Esta declaração é um pouco diferente, porque,

589
00:32:26,000 --> 00:32:28,000
novamente, o compilador C é um pouco idiota.

590
00:32:28,000 --> 00:32:30,000
Ele só vai ler de cima para baixo,

591
00:32:30,000 --> 00:32:33,000
assim que se atinge a linha 2 aqui

592
00:32:33,000 --> 00:32:37,000
onde próxima está declarada e vê Oh, aqui está uma variável chamada seguinte.

593
00:32:37,000 --> 00:32:39,000
É um ponteiro para um nó de estrutura.

594
00:32:39,000 --> 00:32:42,000
O compilador vai perceber o que é um nó de estrutura?

595
00:32:42,000 --> 00:32:44,000
Eu nunca ouvi falar dessa coisa antes,

596
00:32:44,000 --> 00:32:47,000
porque o nó palavra não poderiam aparecer

597
00:32:47,000 --> 00:32:49,000
até o fundo, para que haja esta redundância.

598
00:32:49,000 --> 00:32:53,000
Você tem que dizer nó struct aqui, o que você pode encurtar mais tarde

599
00:32:53,000 --> 00:32:56,000
graças a typedef aqui, mas isso é porque

600
00:32:56,000 --> 00:33:02,000
estamos referenciando a estrutura em si no interior da estrutura.

601
00:33:02,000 --> 00:33:05,000
Essa é a única pegadinha aí.

602
00:33:05,000 --> 00:33:07,000
>> Alguns problemas interessantes vão surgir.

603
00:33:07,000 --> 00:33:09,000
Temos uma lista de números. Como vamos inserir nele?

604
00:33:09,000 --> 00:33:11,000
Como é que vamos busca-lo? Como podemos excluir isso?

605
00:33:11,000 --> 00:33:13,000
Especialmente agora que temos de gerir todos esses ponteiros.

606
00:33:13,000 --> 00:33:15,000
Você pensou ponteiros eram uma espécie de alucinante

607
00:33:15,000 --> 00:33:17,000
quando você tinha um deles apenas tentando ler um int para ele.

608
00:33:17,000 --> 00:33:20,000
Agora, temos de manipular o valor de uma lista inteira.

609
00:33:20,000 --> 00:33:22,000
Por que não vamos tomar o nosso intervalo de 5 minutos aqui, e então nós vamos trazer

610
00:33:22,000 --> 00:33:34,000
algumas pessoas até ao palco para fazer exatamente isso.

611
00:33:34,000 --> 00:33:36,000
>> C é muito mais divertido quando é encenado.

612
00:33:36,000 --> 00:33:39,000
Quem iria literalmente gostaria de ser o primeiro?

613
00:33:39,000 --> 00:33:41,000
Ok, vamos lá para cima. Você está em primeiro lugar.

614
00:33:41,000 --> 00:33:44,000
Quem gostaria de ser o 9? Ok, 9.

615
00:33:44,000 --> 00:33:46,000
Como cerca de 9? 17?

616
00:33:46,000 --> 00:33:51,000
A panelinha aqui. 22 e 26 em que a linha da frente.

617
00:33:51,000 --> 00:33:53,000
E então, que tal alguém ali sendo apontada.

618
00:33:53,000 --> 00:33:57,000
Está 34. Ok, de 34 anos, vem para cima.

619
00:33:57,000 --> 00:33:59,000
Primeiro está ali. Ok, todos os quatro de vocês.

620
00:33:59,000 --> 00:34:01,000
E quem foi que disse para 9?

621
00:34:01,000 --> 00:34:04,000
Quem é o nosso 9?

622
00:34:04,000 --> 00:34:07,000
Quem realmente quer ser 9? Tudo bem, vamos lá, ser 9.

623
00:34:07,000 --> 00:34:10,000
Aqui vamos nós.

624
00:34:10,000 --> 00:34:13,000
34, nós vamos encontrá-lo por lá.

625
00:34:13,000 --> 00:34:17,000
A primeira parte é fazer-vos olhar como aquele.

626
00:34:17,000 --> 00:34:21,000
26, 22, 17, bom.

627
00:34:21,000 --> 00:34:25,000
Se você pode estar ao lado, porque estamos indo para malloc você em um momento.

628
00:34:25,000 --> 00:34:29,000
>> Bom, muito bom.

629
00:34:29,000 --> 00:34:32,000
Ok, excelente, por isso vamos pedir um par de perguntas aqui.

630
00:34:32,000 --> 00:34:34,000
E, na verdade, qual é o seu nome? >> Anita.

631
00:34:34,000 --> 00:34:37,000
Anita, tudo bem, venha até aqui.

632
00:34:37,000 --> 00:34:41,000
Anita vai nos ajudar a resolver um tipo de pergunta bastante simples, em primeiro lugar,

633
00:34:41,000 --> 00:34:44,000
que é como você encontrar ou não um valor está na lista?

634
00:34:44,000 --> 00:34:48,000
Agora, observe que o primeiro, representado aqui por Lucas,

635
00:34:48,000 --> 00:34:52,000
é um pouco diferente, e por isso seu pedaço de papel é deliberadamente de lado

636
00:34:52,000 --> 00:34:55,000
porque não é tão alto e não toma-se como muitos bits,

637
00:34:55,000 --> 00:34:58,000
embora tecnicamente ele tem o mesmo tamanho de papel apenas rodado.

638
00:34:58,000 --> 00:35:01,000
Mas ele é um pouco diferente, já que ele tem apenas 32 bits para um ponteiro,

639
00:35:01,000 --> 00:35:05,000
e todos esses caras são de 64 bits, metade dos quais é o número, metade dos quais é um ponteiro.

640
00:35:05,000 --> 00:35:08,000
Mas o ponteiro não é retratado, por isso, se vocês pudessem um pouco sem jeito

641
00:35:08,000 --> 00:35:12,000
use a mão esquerda para apontar para a pessoa ao seu lado.

642
00:35:12,000 --> 00:35:14,000
E você é o número 34. Qual é o seu nome?

643
00:35:14,000 --> 00:35:16,000
Ari.

644
00:35:16,000 --> 00:35:19,000
Ari, portanto, na verdade, manter o papel em sua mão direita, ea mão esquerda vai direto para baixo.

645
00:35:19,000 --> 00:35:21,000
Você declara nulo à esquerda.

646
00:35:21,000 --> 00:35:24,000
>> Agora o nosso retrato humano é muito consistente.

647
00:35:24,000 --> 00:35:26,000
Isto é, na verdade, como os ponteiros trabalhar.

648
00:35:26,000 --> 00:35:29,000
E se você pode amassar um pouco dessa forma que eu não estou no seu caminho.

649
00:35:29,000 --> 00:35:34,000
Anita aqui, encontrar-me o número 22,

650
00:35:34,000 --> 00:35:40,000
mas assumir uma restrição de não seres humanos segurando pedaços de papel,

651
00:35:40,000 --> 00:35:43,000
mas esta é uma lista, e você só tem Lucas para começar

652
00:35:43,000 --> 00:35:46,000
porque ele é, literalmente, o primeiro ponteiro.

653
00:35:46,000 --> 00:35:51,000
Suponha que você mesmo é um ponteiro, e para que você também tem a capacidade de apontar algo.

654
00:35:51,000 --> 00:35:56,000
Por que você não começar por apontar exatamente o que Lucas está apontando?

655
00:35:56,000 --> 00:35:58,000
Bom, deixe-me e aprovar isso aqui.

656
00:35:58,000 --> 00:36:04,000
Apenas por uma questão de discussão, deixe-me puxar para cima uma página em branco aqui.

657
00:36:04,000 --> 00:36:06,000
Como se escreve o seu nome? >> Anita.

658
00:36:06,000 --> 00:36:08,000
Ok, Anita.

659
00:36:08,000 --> 00:36:18,000
Digamos nó * anita = lucas.

660
00:36:18,000 --> 00:36:22,000
Bem, não devemos chamá-lo de Lucas. Devemos chamá-lo primeiro.

661
00:36:22,000 --> 00:36:25,000
Por que isso é de fato consistente com a realidade aqui?

662
00:36:25,000 --> 00:36:27,000
Um, primeiro já existe.

663
00:36:27,000 --> 00:36:30,000
Primeiro foi alocado em algum lugar, presumivelmente, aqui em cima.

664
00:36:30,000 --> 00:36:35,000
* Primeiro nó, e que tem sido atribuída uma lista de alguma forma.

665
00:36:35,000 --> 00:36:37,000
Eu não sei como isso aconteceu. Isso aconteceu antes da aula começar.

666
00:36:37,000 --> 00:36:40,000
Esta lista ligada de seres humanos foi criado.

667
00:36:40,000 --> 00:36:44,000
E agora, neste momento da história, tudo isso é ir no Facebook, aparentemente, mais tarde,

668
00:36:44,000 --> 00:36:49,000
neste ponto da história, Anita foi inicializada para ser igual ao primeiro,

669
00:36:49,000 --> 00:36:51,000
o que não significa que os pontos de Anita em Lucas.

670
00:36:51,000 --> 00:36:53,000
Em vez disso, ela aponta para o que ele aponta para

671
00:36:53,000 --> 00:36:57,000
pois o mesmo endereço que está dentro de 32 bits - Lucas 1, 2, 3 -

672
00:36:57,000 --> 00:37:01,000
é agora também dentro de 32 Anita bits - 1, 2, 3.

673
00:37:01,000 --> 00:37:05,000
>> Agora, encontrar 22. Como você vai fazer sobre isso?

674
00:37:05,000 --> 00:37:07,000
O que é que o ponto? >> Para o que for.

675
00:37:07,000 --> 00:37:11,000
Aponte para o que quer, então vá em frente e agir para fora o melhor que puder aqui.

676
00:37:11,000 --> 00:37:15,000
Bom, bom, e agora você está apontando-o que é o seu nome, com 22?

677
00:37:15,000 --> 00:37:18,000
Ramon. >> Ramon, então Ramon está segurando 22.

678
00:37:18,000 --> 00:37:20,000
Você já fez um cheque.

679
00:37:20,000 --> 00:37:24,000
O Ramon == 22, e se assim for, por exemplo, podemos voltar verdade.

680
00:37:24,000 --> 00:37:26,000
Deixe-me, enquanto esses caras ficar aqui um pouco sem jeito,

681
00:37:26,000 --> 00:37:32,000
deixe-me fazer algo rapidamente, como bool encontrar.

682
00:37:32,000 --> 00:37:37,000
Eu estou indo para ir em frente e dizer (lista * nó, int n).

683
00:37:37,000 --> 00:37:39,000
Eu estarei de volta com vocês. Eu só tenho que escrever algum código.

684
00:37:39,000 --> 00:37:45,000
E agora eu estou indo para ir em frente e fazer isso, nó * anita = lista.

685
00:37:45,000 --> 00:37:51,000
E eu estou indo para ir em frente e dizer ao mesmo tempo (Anita! = NULL).

686
00:37:51,000 --> 00:37:57,000
>> A metáfora aqui está ficando um pouco esticado, mas enquanto (Anita! = NULL), o que eu quero fazer?

687
00:37:57,000 --> 00:38:03,000
Eu preciso de alguma forma de referenciar

688
00:38:03,000 --> 00:38:05,000
o inteiro que Anita está apontando.

689
00:38:05,000 --> 00:38:08,000
No passado, quando se tinham estruturas, o que é um nó,

690
00:38:08,000 --> 00:38:11,000
usamos a notação de ponto, e gostaríamos de dizer algo como

691
00:38:11,000 --> 00:38:15,000
anita.n, mas o problema aqui é que Anita não é uma estrutura em si.

692
00:38:15,000 --> 00:38:17,000
O que ela é?

693
00:38:17,000 --> 00:38:21,000
Ela é um ponteiro, por isso mesmo, se quisermos usar esta notação de ponto

694
00:38:21,000 --> 00:38:23,000
e este vai olhar deliberadamente um pouco enigmática-

695
00:38:23,000 --> 00:38:28,000
temos que fazer alguma coisa, como ir para a mão esquerda o que Anita está apontando para

696
00:38:28,000 --> 00:38:31,000
e em seguida, obter o campo chamado n.

697
00:38:31,000 --> 00:38:35,000
Anita é um ponteiro, mas o que é * Anita?

698
00:38:35,000 --> 00:38:38,000
O que você acha quando você vai para o que Anita está apontando?

699
00:38:38,000 --> 00:38:42,000
A estrutura, um nó, e um nó de recordação, tem um campo chamado n

700
00:38:42,000 --> 00:38:47,000
porque tem, lembre-se, estes dois campos, próximos e n,

701
00:38:47,000 --> 00:38:50,000
que vimos há pouco aqui.

702
00:38:50,000 --> 00:38:53,000
>> Para realmente imitar isso no código,

703
00:38:53,000 --> 00:39:02,000
nós poderíamos fazer isso e dizer se ((* anita). n == n), o n que eu estou procurando.

704
00:39:02,000 --> 00:39:04,000
Observe que a função foi aprovada no número que me interessa.

705
00:39:04,000 --> 00:39:10,000
Então eu posso ir em frente e fazer algo como verdadeiro retorno.

706
00:39:10,000 --> 00:39:12,000
Outra coisa, se esse não é o caso, o que eu quero fazer?

707
00:39:12,000 --> 00:39:19,000
Como eu traduzo para codificar o que Anita fez intuitivamente andando através da lista?

708
00:39:19,000 --> 00:39:26,000
O que devo fazer aqui para simular Anita dar esse passo para a esquerda, que passo para a esquerda?

709
00:39:26,000 --> 00:39:28,000
[Resposta do aluno inaudível] >> O que é isso?

710
00:39:28,000 --> 00:39:30,000
[Resposta do aluno inaudível]

711
00:39:30,000 --> 00:39:34,000
Bom, não é uma idéia ruim, mas no passado, quando fizemos isso, fizemos anita + +

712
00:39:34,000 --> 00:39:37,000
porque que gostaria de acrescentar o número 1 para Anita,

713
00:39:37,000 --> 00:39:40,000
que normalmente apontar para a próxima pessoa, como Ramon,

714
00:39:40,000 --> 00:39:44,000
ou a pessoa próxima a ele, ou a pessoa próxima a ele para baixo da linha.

715
00:39:44,000 --> 00:39:49,000
Mas isso não é muito bom aqui, porque o que essa coisa parece na memória?

716
00:39:49,000 --> 00:39:54,000
Não é isso. Nós temos que desativar isso.

717
00:39:54,000 --> 00:40:00,000
Parece que este na memória, e mesmo que eu tenha desenhado 1 e 2 e 3 próximos um do outro,

718
00:40:00,000 --> 00:40:03,000
se realmente simular este-Vocês podem, ainda apontando para as mesmas pessoas,

719
00:40:03,000 --> 00:40:07,000
alguns de vocês podem dar um passo atrás aleatória, alguns de vocês um passo aleatório para a frente?

720
00:40:07,000 --> 00:40:10,000
>> Esta confusão é ainda uma lista ligada,

721
00:40:10,000 --> 00:40:13,000
mas esses caras poderiam estar em qualquer lugar na memória,

722
00:40:13,000 --> 00:40:15,000
assim anita + + não vai funcionar por que?

723
00:40:15,000 --> 00:40:19,000
O que está em local anita + +?

724
00:40:19,000 --> 00:40:21,000
Quem sabe.

725
00:40:21,000 --> 00:40:24,000
É algum outro valor que só acontece a ser interposta

726
00:40:24,000 --> 00:40:28,000
entre todos esses nós por acaso, porque não estamos usando uma matriz.

727
00:40:28,000 --> 00:40:30,000
Nós alocado a cada um destes nós individualmente.

728
00:40:30,000 --> 00:40:32,000
Ok, se vocês podem limpar-se de volta.

729
00:40:32,000 --> 00:40:37,000
Deixe-me propor que, em vez de anita + +, que em vez fazer anita fica-

730
00:40:37,000 --> 00:40:42,000
bem, por que não vamos para o que quer que Anita está apontando e depois fazer. próximo?

731
00:40:42,000 --> 00:40:45,000
Em outras palavras, vamos para Ramon, que está segurando o número 22,

732
00:40:45,000 --> 00:40:51,000
e depois. seguinte é como se Anita seria copiar o seu ponteiro mão esquerda.

733
00:40:51,000 --> 00:40:54,000
Mas ela não quis ir mais longe do que Ramon porque encontramos 22.

734
00:40:54,000 --> 00:40:56,000
Mas isso seria a idéia. Agora, isso é uma bagunça horrível.

735
00:40:56,000 --> 00:40:59,000
Honestamente, ninguém vai lembrar esta sintaxe, e assim, felizmente,

736
00:40:59,000 --> 00:41:04,000
na verdade é um pouco deliberada-oh, você não realmente ver o que eu escrevi.

737
00:41:04,000 --> 00:41:08,000
Isso seria mais convincente se pudesse. Voila!

738
00:41:08,000 --> 00:41:10,000
>> Por trás das cenas, eu estava resolvendo o problema dessa forma.

739
00:41:10,000 --> 00:41:14,000
Anita, para dar esse passo para a esquerda,

740
00:41:14,000 --> 00:41:18,000
em primeiro lugar, nós ir para o endereço que Anita está apontando para

741
00:41:18,000 --> 00:41:23,000
e onde ela vai encontrar não só n, que verifiquei apenas para efeitos de comparação,

742
00:41:23,000 --> 00:41:25,000
mas você também vai encontrar próximo - neste caso,

743
00:41:25,000 --> 00:41:28,000
Mão esquerda Ramon, apontando para o próximo nó na lista.

744
00:41:28,000 --> 00:41:32,000
Mas esta é a bagunça horrível a que me referi anteriormente,

745
00:41:32,000 --> 00:41:34,000
mas acontece C nos permite simplificar isso.

746
00:41:34,000 --> 00:41:40,000
Em vez de escrever (* anita), podemos ao invés de apenas escrever anita-> n,

747
00:41:40,000 --> 00:41:45,000
e é exatamente a mesma coisa funcionalmente, mas é muito mais intuitivo,

748
00:41:45,000 --> 00:41:48,000
e é muito mais consistente com a imagem que temos vindo a desenhar

749
00:41:48,000 --> 00:41:50,000
todo esse tempo usando as setas.

750
00:41:50,000 --> 00:41:57,000
>> Por fim, o que nós precisamos fazer no final deste programa?

751
00:41:57,000 --> 00:42:00,000
Há uma linha de código restante.

752
00:42:00,000 --> 00:42:02,000
Devolver o que?

753
00:42:02,000 --> 00:42:05,000
Falso, porque se passar todo o loop while

754
00:42:05,000 --> 00:42:10,000
e Anita é, de fato, nulo, isso significa que ela percorreu todo o caminho para o fim da lista

755
00:42:10,000 --> 00:42:12,000
onde ela estava apontando-o que é o seu nome?

756
00:42:12,000 --> 00:42:15,000
Ari mão esquerda. >> Ari, que é nulo.

757
00:42:15,000 --> 00:42:18,000
Anita agora é nulo, e eu perceber que você está de pé aqui sem jeito no limbo

758
00:42:18,000 --> 00:42:21,000
porque eu estou saindo em um monólogo aqui,

759
00:42:21,000 --> 00:42:23,000
mas vamos envolvê-lo novamente em apenas um momento.

760
00:42:23,000 --> 00:42:27,000
Anita é nulo nesse ponto da história, de modo que o loop while termina,

761
00:42:27,000 --> 00:42:30,000
e nós temos que retornar falso, porque se ela tem todo o caminho para ponteiro nulo de Ari

762
00:42:30,000 --> 00:42:34,000
então não havia número que ela procurou na lista.

763
00:42:34,000 --> 00:42:39,000
Podemos limpar isso também, mas essa é uma implementação muito boa, então

764
00:42:39,000 --> 00:42:43,000
de uma função de passagem, uma função para encontrar uma lista ligada.

765
00:42:43,000 --> 00:42:48,000
É ainda busca linear, mas não é tão simples como um ponteiro + +

766
00:42:48,000 --> 00:42:52,000
ou + + uma variável i porque agora não podemos adivinhar

767
00:42:52,000 --> 00:42:54,000
em que cada um destes nós se encontram na memória.

768
00:42:54,000 --> 00:42:57,000
Temos que, literalmente, seguir a trilha de migalhas de pão ou, mais especificamente,

769
00:42:57,000 --> 00:43:00,000
ponteiros, para começar a partir de um nó para outro.

770
00:43:00,000 --> 00:43:02,000
>> Agora vamos tentar outro. Anita, você quer voltar para cá?

771
00:43:02,000 --> 00:43:06,000
Por que não vamos em frente e alocar uma outra pessoa da platéia?

772
00:43:06,000 --> 00:43:08,000
Malloc qual é o seu nome? >> Rebecca.

773
00:43:08,000 --> 00:43:10,000
Rebecca. Rebecca foi malloced da platéia,

774
00:43:10,000 --> 00:43:13,000
e ela é agora armazenar o número 55.

775
00:43:13,000 --> 00:43:17,000
E o objetivo em mãos agora é para Anita para inserir

776
00:43:17,000 --> 00:43:22,000
Rebecca na lista ligada aqui em seu lugar apropriado.

777
00:43:22,000 --> 00:43:24,000
Venha aqui por um momento.

778
00:43:24,000 --> 00:43:28,000
Eu tenho feito algo assim.

779
00:43:28,000 --> 00:43:32,000
Eu fiz * nó. E qual é o seu nome?

780
00:43:32,000 --> 00:43:34,000
Rebecca. >> Rebecca, tudo bem.

781
00:43:34,000 --> 00:43:41,000
Rebecca fica malloc (sizeof (nó)).

782
00:43:41,000 --> 00:43:44,000
Assim como nós alocamos coisas como estudantes e outros enfeites no passado,

783
00:43:44,000 --> 00:43:46,000
temos o tamanho do nó, de modo agora Rebecca

784
00:43:46,000 --> 00:43:49,000
está apontando para o que?

785
00:43:49,000 --> 00:43:52,000
Rebecca tem dois campos dentro dela, um dos quais é 55.

786
00:43:52,000 --> 00:43:55,000
Vamos fazer o que, rebecca-> = 55.

787
00:43:55,000 --> 00:44:00,000
Mas, então, rebecca-> seguinte deve ser-como agora, a mão dela é uma espécie de, quem sabe?

788
00:44:00,000 --> 00:44:03,000
Ele está apontando para algum valor de lixo, então por que não fazer para uma boa medida

789
00:44:03,000 --> 00:44:07,000
que pelo menos fazer isso para que a mão esquerda está agora ao seu lado.

790
00:44:07,000 --> 00:44:09,000
Agora Anita, levá-lo a partir daqui.

791
00:44:09,000 --> 00:44:11,000
Você tem Rebecca tendo sido atribuídos.

792
00:44:11,000 --> 00:44:20,000
Vá em frente e descobrir onde devemos colocar Rebecca.

793
00:44:20,000 --> 00:44:25,000
Bom, muito bom.

794
00:44:25,000 --> 00:44:28,000
Ok, bom, e agora nós precisamos de você para fornecer um pouco de direção,

795
00:44:28,000 --> 00:44:30,000
de modo que você alcançou Ari.

796
00:44:30,000 --> 00:44:33,000
Sua mão esquerda é nulo, mas Rebecca pertence claramente à direita,

797
00:44:33,000 --> 00:44:36,000
então como é que nós temos que alterar esta lista ligada

798
00:44:36,000 --> 00:44:38,000
a fim de inserir Rebecca no local apropriado?

799
00:44:38,000 --> 00:44:42,000
Se você pode, literalmente, mover as mãos das pessoas de esquerda em torno de como necessário,

800
00:44:42,000 --> 00:44:48,000
nós vamos resolver o problema dessa forma.

801
00:44:48,000 --> 00:44:52,000
Ok, bom, e, entretanto, a mão esquerda de Rebecca já está ao seu lado.

802
00:44:52,000 --> 00:44:54,000
>> Isso foi muito fácil.

803
00:44:54,000 --> 00:44:57,000
Vamos tentar alocar-estamos quase pronto, 20.

804
00:44:57,000 --> 00:44:59,000
Ok, vamos lá para cima.

805
00:44:59,000 --> 00:45:04,000
20 foi atribuído, então deixe-me ir em frente e dizer novamente aqui

806
00:45:04,000 --> 00:45:07,000
nós acabamos de fazer saad * nó.

807
00:45:07,000 --> 00:45:11,000
Temos malloc (sizeof (nó)).

808
00:45:11,000 --> 00:45:16,000
Em seguida, fazer a mesma sintaxe exata como fizemos antes de 20,

809
00:45:16,000 --> 00:45:20,000
e eu vou fazer = NULL seguinte, e agora cabe a Anita

810
00:45:20,000 --> 00:45:23,000
você inserir na lista ligada, se você poderia desempenhar esse papel exato.

811
00:45:23,000 --> 00:45:30,000
Executar.

812
00:45:30,000 --> 00:45:32,000
Ok, bom.

813
00:45:32,000 --> 00:45:38,000
Agora pense com cuidado antes de você começar a se mover a mão esquerda ao redor.

814
00:45:38,000 --> 00:45:46,000
Você tem, de longe, o papel mais difícil hoje.

815
00:45:46,000 --> 00:45:59,000
Cuja mão deve ser movido em primeiro lugar?

816
00:45:59,000 --> 00:46:02,000
Ok, espere, eu estou ouvindo algumas n º.

817
00:46:02,000 --> 00:46:07,000
Se algumas pessoas se educadamente gostaria de ajudar a resolver uma situação embaraçosa aqui.

818
00:46:07,000 --> 00:46:11,000
Cuja mão esquerda deve ser atualizado primeiro, talvez? Sim.

819
00:46:11,000 --> 00:46:13,000
[Estudante] Saad.

820
00:46:13,000 --> 00:46:15,000
Ok, Saad, por que, então?

821
00:46:15,000 --> 00:46:17,000
[Resposta do aluno inaudível]

822
00:46:17,000 --> 00:46:19,000
Bom, porque se mover-qual é o seu nome? >> Marshall.

823
00:46:19,000 --> 00:46:22,000
Marshall, se mover sua mão primeiro para baixo a nulo,

824
00:46:22,000 --> 00:46:25,000
agora temos literalmente órfãos quatro pessoas na lista

825
00:46:25,000 --> 00:46:29,000
porque ele era a única coisa apontando para Ramon e todos para a esquerda,

826
00:46:29,000 --> 00:46:31,000
de modo que a atualização primeiro ponteiro era ruim.

827
00:46:31,000 --> 00:46:33,000
Vamos desfazer isso.

828
00:46:33,000 --> 00:46:37,000
Bom, e agora vá em frente e passar a mão apropriado esquerda apontando para Ramon.

829
00:46:37,000 --> 00:46:39,000
Isso sente-se um pouco redundante.

830
00:46:39,000 --> 00:46:41,000
Agora há duas pessoas apontando para Ramon, mas isso é bom

831
00:46:41,000 --> 00:46:43,000
porque agora que outra forma é que vamos atualizar a lista?

832
00:46:43,000 --> 00:46:48,000
O que por outro lado tem de se mover?

833
00:46:48,000 --> 00:46:53,000
Excelente, agora temos perdido a memória?

834
00:46:53,000 --> 00:46:57,000
Não, tudo bem, vamos ver se não podemos quebrar esta mais uma vez.

835
00:46:57,000 --> 00:47:00,000
>> Mallocing uma última vez, o número 5.

836
00:47:00,000 --> 00:47:04,000
Em todo o caminho de volta, venha para baixo.

837
00:47:04,000 --> 00:47:08,000
É muito emocionante.

838
00:47:08,000 --> 00:47:15,000
[Aplausos]

839
00:47:15,000 --> 00:47:17,000
Qual é o seu nome? >> Ron.

840
00:47:17,000 --> 00:47:19,000
Ron, ok, você está malloced como número 5.

841
00:47:19,000 --> 00:47:23,000
Acabamos de executado o código que é quase idêntico a estes

842
00:47:23,000 --> 00:47:26,000
com apenas um nome diferente.

843
00:47:26,000 --> 00:47:28,000
Excelente.

844
00:47:28,000 --> 00:47:38,000
Agora, Anita, boa sorte inserir o número 5 na lista agora.

845
00:47:38,000 --> 00:47:43,000
Bom, e?

846
00:47:43,000 --> 00:47:47,000
Excelente, de modo que este é realmente o terceiro de três casos no total.

847
00:47:47,000 --> 00:47:49,000
Primeiro tivemos alguém no final, Rebecca.

848
00:47:49,000 --> 00:47:51,000
Então, teve alguém no meio.

849
00:47:51,000 --> 00:47:53,000
Agora temos alguém no início, e, neste exemplo,

850
00:47:53,000 --> 00:47:56,000
agora teve que atualizar Lucas pela primeira vez

851
00:47:56,000 --> 00:48:00,000
porque o primeiro elemento na lista agora tem que apontar para um novo nó,

852
00:48:00,000 --> 00:48:03,000
que, por sua vez, está a apontar no número de nó 9.

853
00:48:03,000 --> 00:48:06,000
>> Esta foi uma demonstração extremamente estranho, eu tenho certeza,

854
00:48:06,000 --> 00:48:08,000
assim um grande aplauso para esses caras se pudesse.

855
00:48:08,000 --> 00:48:11,000
Bem feito.

856
00:48:11,000 --> 00:48:17,000
Isto é tudo. Você pode manter seus pedaços de papel como um pouco de memória.

857
00:48:17,000 --> 00:48:22,000
Acontece que fazer isso no código

858
00:48:22,000 --> 00:48:26,000
não é tão simples como mover as mãos em torno de

859
00:48:26,000 --> 00:48:28,000
e apontando ponteiros em coisas diferentes.

860
00:48:28,000 --> 00:48:31,000
Mas perceber que quando chega a hora de implementar algo como

861
00:48:31,000 --> 00:48:34,000
uma lista ligada ou uma variante do que se você se concentrar em realmente

862
00:48:34,000 --> 00:48:38,000
esses fundamentos básicos, os problemas de mordida de tamanho que eu tenho que descobrir,

863
00:48:38,000 --> 00:48:43,000
é esta mão ou este lado, perceber que o que é outra forma de um programa bastante complexo

864
00:48:43,000 --> 00:48:47,000
pode, de fato, ser reduzida a blocos de construção bastante simples como este.

865
00:48:47,000 --> 00:48:51,000
>> Vamos levar as coisas para uma direção mais sofisticado ainda.

866
00:48:51,000 --> 00:48:53,000
Temos agora a noção de lista ligada.

867
00:48:53,000 --> 00:48:57,000
Temos também, graças à sugestão lá atrás-uma lista duplamente ligada,

868
00:48:57,000 --> 00:49:01,000
que parece ser quase a mesma, mas agora temos dois ponteiros dentro da estrutura

869
00:49:01,000 --> 00:49:05,000
em vez de uma, e provavelmente poderíamos chamar os ponteiros anterior e próximo

870
00:49:05,000 --> 00:49:08,000
ou para a esquerda ou para a direita, mas nós, de fato, precisa de dois deles.

871
00:49:08,000 --> 00:49:10,000
O código seria um pouco mais complicado.

872
00:49:10,000 --> 00:49:12,000
Anita teria que fazer mais trabalho aqui no palco.

873
00:49:12,000 --> 00:49:15,000
Mas certamente poderíamos implementar esse tipo de estrutura.

874
00:49:15,000 --> 00:49:19,000
Em termos de tempo de funcionamento, no entanto, o que seria o tempo de execução

875
00:49:19,000 --> 00:49:24,000
por Anita de encontrar um n número em uma lista ligada agora?

876
00:49:24,000 --> 00:49:27,000
O ainda grande de n, então não é melhor do que a busca linear.

877
00:49:27,000 --> 00:49:29,000
Nós não podemos fazer busca binária, embora, mais uma vez.

878
00:49:29,000 --> 00:49:34,000
Por que isso acontece? Você não pode pular.

879
00:49:34,000 --> 00:49:36,000
Mesmo que ver, obviamente, todos os seres humanos no palco,

880
00:49:36,000 --> 00:49:39,000
e Anita poderia ter eyeballed e disse: "Aqui está a meio da lista",

881
00:49:39,000 --> 00:49:42,000
ela não saberia que, se fosse um programa de computador

882
00:49:42,000 --> 00:49:47,000
porque a única coisa que tinha de agarrar-se no início do cenário

883
00:49:47,000 --> 00:49:50,000
era Lucas, que foi o primeiro ponteiro.

884
00:49:50,000 --> 00:49:53,000
Ela teria necessariamente que seguir estes links,

885
00:49:53,000 --> 00:49:56,000
contando o seu caminho até que encontrou cerca de meio a,

886
00:49:56,000 --> 00:49:58,000
e mesmo assim, ela não vai saber quando ela atingiu o meio

887
00:49:58,000 --> 00:50:01,000
a menos que ela vai todo o caminho até o fim para descobrir quantos são,

888
00:50:01,000 --> 00:50:05,000
depois volta atrás, e que também seria difícil, a menos que você teve

889
00:50:05,000 --> 00:50:07,000
uma lista duplamente ligada de algum tipo.

890
00:50:07,000 --> 00:50:10,000
>> Resolução de alguns problemas hoje, mas a introdução de outros.

891
00:50:10,000 --> 00:50:12,000
E sobre uma estrutura de dados completamente diferente?

892
00:50:12,000 --> 00:50:15,000
Esta é uma fotografia das bandejas em Mather House,

893
00:50:15,000 --> 00:50:19,000
e, neste caso, temos uma estrutura de dados que temos também uma espécie de já falando.

894
00:50:19,000 --> 00:50:22,000
Nós conversamos sobre uma pilha no contexto da memória,

895
00:50:22,000 --> 00:50:26,000
e que é uma espécie de deliberadamente chamado porque uma pilha nos termos de memória

896
00:50:26,000 --> 00:50:31,000
é efetivamente uma estrutura de dados que tem mais e mais coisas em camadas em cima dele.

897
00:50:31,000 --> 00:50:35,000
Mas o mais interessante sobre uma pilha, como é o caso na realidade,

898
00:50:35,000 --> 00:50:38,000
é que ele é um tipo especial de estrutura de dados.

899
00:50:38,000 --> 00:50:42,000
É uma estrutura de dados em que o primeiro elemento

900
00:50:42,000 --> 00:50:46,000
é o último elemento para fora.

901
00:50:46,000 --> 00:50:50,000
Se você é a primeira bandeja para ser colocado na pilha,

902
00:50:50,000 --> 00:50:53,000
você vai ser, infelizmente, a bandeja último a ser retirado da pilha,

903
00:50:53,000 --> 00:50:55,000
e isso não é necessariamente uma coisa boa.

904
00:50:55,000 --> 00:50:58,000
Por outro lado, você pode pensar sobre ele o caminho inverso,

905
00:50:58,000 --> 00:51:02,000
o último é o primeiro a sair.

906
00:51:02,000 --> 00:51:05,000
>> Agora, se os cenários vêm à mente que ter uma pilha

907
00:51:05,000 --> 00:51:08,000
estrutura de dados, onde você tem que a propriedade

908
00:51:08,000 --> 00:51:13,000
do último, em primeiro lugar, é realmente atraente?

909
00:51:13,000 --> 00:51:16,000
Isso é uma coisa boa? É que uma coisa ruim?

910
00:51:16,000 --> 00:51:19,000
É definitivamente uma coisa ruim se as bandejas não eram todos iguais

911
00:51:19,000 --> 00:51:21,000
e todos eles eram diferentes cores especiais ou outros enfeites,

912
00:51:21,000 --> 00:51:24,000
ea cor que você quer é todo o caminho na parte inferior.

913
00:51:24,000 --> 00:51:26,000
É claro, você não pode conseguir que sem grande esforço.

914
00:51:26,000 --> 00:51:28,000
Você tem que começar a partir do topo e trabalhar sua maneira para baixo.

915
00:51:28,000 --> 00:51:31,000
Da mesma forma, se você fosse um desses meninos de fãs

916
00:51:31,000 --> 00:51:34,000
que espera a noite toda tentando obter um iPhone e alinha

917
00:51:34,000 --> 00:51:36,000
em um lugar como este?

918
00:51:36,000 --> 00:51:40,000
Não seria bom se a loja da Apple

919
00:51:40,000 --> 00:51:42,000
foram uma estrutura de dados de pilha?

920
00:51:42,000 --> 00:51:44,000
Yay? Não?

921
00:51:44,000 --> 00:51:47,000
Só é bom para as pessoas que aparecem no último minuto possível

922
00:51:47,000 --> 00:51:50,000
e depois se arranquei a fila.

923
00:51:50,000 --> 00:51:52,000
E, na verdade, o fato de que eu estava tão inclinado a dizer fila

924
00:51:52,000 --> 00:51:56,000
é realmente consistente com o que nós chamaríamos este tipo de estrutura de dados,

925
00:51:56,000 --> 00:51:59,000
um na realidade onde a ordem não importa,

926
00:51:59,000 --> 00:52:02,000
e deseja que o primeiro em ser o primeiro a sair

927
00:52:02,000 --> 00:52:04,000
mesmo que apenas por uma questão de equidade humana.

928
00:52:04,000 --> 00:52:07,000
Vamos chamar geral de que uma estrutura de dados fila.

929
00:52:07,000 --> 00:52:11,000
>> Acontece que além de listas ligadas, podemos começar a usar essas mesmas idéias básicas

930
00:52:11,000 --> 00:52:15,000
e começar a criar novos tipos e diferentes de soluções para os problemas.

931
00:52:15,000 --> 00:52:19,000
Por exemplo, no caso de uma pilha, que pode representar uma pilha

932
00:52:19,000 --> 00:52:22,000
usando uma estrutura de dados como este, eu gostaria de propor.

933
00:52:22,000 --> 00:52:26,000
Neste caso, eu tenho declarado um struct, e eu já disse dentro desta estrutura

934
00:52:26,000 --> 00:52:30,000
é uma matriz de números e, em seguida, um tamanho variável chamada,

935
00:52:30,000 --> 00:52:33,000
e eu vou chamar essa coisa de uma pilha.

936
00:52:33,000 --> 00:52:35,000
Agora, por que isso realmente funciona?

937
00:52:35,000 --> 00:52:43,000
No caso de uma pilha, poderia desenhar essa eficácia no ecrã como uma matriz.

938
00:52:43,000 --> 00:52:47,000
Aqui é a minha pilha. Esses são os meus números.

939
00:52:47,000 --> 00:52:50,000
E nós vamos chamar-lhes como este, este, este, este, este.

940
00:52:50,000 --> 00:52:53,000
E então eu tenho algum membro de outros dados aqui,

941
00:52:53,000 --> 00:52:58,000
que é chamado de tamanho, de modo que este é o tamanho, e isto é números,

942
00:52:58,000 --> 00:53:02,000
e coletivamente, o iPad todo aqui representa uma estrutura de pilha.

943
00:53:02,000 --> 00:53:07,000
Agora, por padrão, o tamanho presumivelmente tem que ser inicializado a 0,

944
00:53:07,000 --> 00:53:11,000
e que está dentro da matriz de números inicialmente

945
00:53:11,000 --> 00:53:14,000
quando eu alocar uma matriz?

946
00:53:14,000 --> 00:53:16,000
Lixo. Quem sabe? E isso realmente não importa.

947
00:53:16,000 --> 00:53:20,000
Não importa se é 1, 2, 3, 4, 5, de forma completamente aleatória

948
00:53:20,000 --> 00:53:25,000
pela má sorte armazenados em minha estrutura, porque desde que eu sei que o tamanho da pilha

949
00:53:25,000 --> 00:53:29,000
é 0, então eu sei que programaticamente, não olhe para qualquer um dos elementos do array.

950
00:53:29,000 --> 00:53:31,000
Não importa o que está lá.

951
00:53:31,000 --> 00:53:34,000
Não olhe para eles, como seria a implicação de um tamanho de 0.

952
00:53:34,000 --> 00:53:38,000
>> Mas suponha que agora eu vá em frente e inserir algo na pilha.

953
00:53:38,000 --> 00:53:42,000
Quero inserir o número 5, então eu coloquei o número 5 aqui,

954
00:53:42,000 --> 00:53:45,000
e então o que eu coloco aqui?

955
00:53:45,000 --> 00:53:48,000
Agora eu realmente colocar para baixo 1 para o tamanho,

956
00:53:48,000 --> 00:53:50,000
e agora, a pilha é de tamanho 1.

957
00:53:50,000 --> 00:53:53,000
E se eu ir em frente e inserir o número, digamos, 7 próximo?

958
00:53:53,000 --> 00:53:57,000
Isso, então, é atualizado a 2, e depois vamos fazer 9,

959
00:53:57,000 --> 00:54:02,000
e então esta é atualizado a 3.

960
00:54:02,000 --> 00:54:05,000
Mas a característica interessante agora desta pilha é que

961
00:54:05,000 --> 00:54:09,000
Eu tenho que remover elemento que se eu quiser pop

962
00:54:09,000 --> 00:54:12,000
algo fora da pilha, por assim dizer?

963
00:54:12,000 --> 00:54:14,000
9 seria a primeira coisa a ir.

964
00:54:14,000 --> 00:54:18,000
Como a imagem deve mudar se eu quiser aparecer um elemento da pilha,

965
00:54:18,000 --> 00:54:20,000
Muito parecido com uma bandeja na Mather?

966
00:54:20,000 --> 00:54:22,000
Sim. >> [Estudante] tamanho definido para 2.

967
00:54:22,000 --> 00:54:27,000
Exatamente, tudo que eu faço é definir o tamanho para 2, eo que eu faço com a matriz?

968
00:54:27,000 --> 00:54:29,000
Eu não tenho que fazer nada.

969
00:54:29,000 --> 00:54:32,000
Eu poderia, apenas para ser anal, coloque um 0 lá ou a -1 ou algo para significar

970
00:54:32,000 --> 00:54:34,000
que este não é um valor legal, mas não importa porque

971
00:54:34,000 --> 00:54:37,000
Eu posso gravar fora do conjunto em si quanto tempo é

972
00:54:37,000 --> 00:54:41,000
para que eu saiba só olhar para os dois primeiros elementos desta matriz.

973
00:54:41,000 --> 00:54:47,000
Agora, se eu for e adicionar o número de 8 a essa matriz, como é que o quadro mude em seguida?

974
00:54:47,000 --> 00:54:50,000
Isto torna-se 8, e isto torna-se 3.

975
00:54:50,000 --> 00:54:52,000
Estou cortando alguns cantos aqui.

976
00:54:52,000 --> 00:54:56,000
Agora temos 5, 7, 8, e estamos de volta a um tamanho de 3.

977
00:54:56,000 --> 00:54:58,000
Isso é muito simples de implementar,

978
00:54:58,000 --> 00:55:06,000
mas quando é que vamos lamentar esta decisão design?

979
00:55:06,000 --> 00:55:09,000
Quando as coisas começam a ir muito, muito errado? Sim.

980
00:55:09,000 --> 00:55:11,000
[Resposta do aluno inaudível]

981
00:55:11,000 --> 00:55:13,000
Quando você quiser voltar e pegar o primeiro elemento que você colocar dentro

982
00:55:13,000 --> 00:55:18,000
>> Acontece aqui, mesmo que uma pilha é uma matriz debaixo do capô,

983
00:55:18,000 --> 00:55:21,000
essas estruturas de dados que já começou a falar sobre geralmente também são conhecidos como

984
00:55:21,000 --> 00:55:25,000
abstratos estruturas de dados pelo qual como elas são implementadas

985
00:55:25,000 --> 00:55:27,000
é completamente fora de questão.

986
00:55:27,000 --> 00:55:31,000
Uma estrutura de dados como uma pilha é suposto adicionar suporte

987
00:55:31,000 --> 00:55:35,000
operações como impulso, que empurra uma bandeja para a pilha,

988
00:55:35,000 --> 00:55:39,000
e pop, que remove um elemento da pilha, e é isso.

989
00:55:39,000 --> 00:55:43,000
Se você tivesse que baixar código de outra pessoa que já implementadas

990
00:55:43,000 --> 00:55:46,000
esta coisa chamada uma pilha, essa pessoa teria escrito

991
00:55:46,000 --> 00:55:49,000
apenas duas funções para você, push e pop, cujo único propósito na vida

992
00:55:49,000 --> 00:55:51,000
seria fazer exatamente isso.

993
00:55:51,000 --> 00:55:54,000
Você ou ele ou a ela que implementou o programa

994
00:55:54,000 --> 00:55:58,000
teria sido inteiramente um para decidir como implementar

995
00:55:58,000 --> 00:56:00,000
a semântica de empurrar e aparecendo debaixo do capô

996
00:56:00,000 --> 00:56:03,000
ou a funcionalidade de empurrar e popping.

997
00:56:03,000 --> 00:56:07,000
E eu fiz uma decisão um tanto míope aqui

998
00:56:07,000 --> 00:56:10,000
através da implementação de minha pilha com esta estrutura de dados simples por quê?

999
00:56:10,000 --> 00:56:12,000
Quando é que esta pausa estrutura de dados?

1000
00:56:12,000 --> 00:56:18,000
Em que ponto eu tenho que retornar um erro quando o usuário chama push, por exemplo?

1001
00:56:18,000 --> 00:56:20,000
[Estudante] Se não há mais espaço.

1002
00:56:20,000 --> 00:56:23,000
Exatamente, se há não mais espaço, se eu excedeu a capacidade,

1003
00:56:23,000 --> 00:56:27,000
que é todo em maiúsculas, porque sugere que é algum tipo de constante global.

1004
00:56:27,000 --> 00:56:30,000
Bem, então eu só vou ter que dizer: "Desculpe, eu não posso empurrar um outro valor

1005
00:56:30,000 --> 00:56:32,000
na pilha ", bem como em Mather.

1006
00:56:32,000 --> 00:56:36,000
>> Em algum momento, eles vão bater a parte de cima do gabinete que pouco.

1007
00:56:36,000 --> 00:56:39,000
Não há mais espaço ou capacidade da pilha, altura em que há algum tipo de erro.

1008
00:56:39,000 --> 00:56:42,000
Eles têm que colocar o elemento em outro lugar, a bandeja em outro lugar,

1009
00:56:42,000 --> 00:56:44,000
ou em lugar nenhum.

1010
00:56:44,000 --> 00:56:47,000
Agora, com uma fila, podemos implementá-lo um pouco diferente.

1011
00:56:47,000 --> 00:56:50,000
Uma fila é um pouco diferente, em que, sob o capô, ele pode ser implementado

1012
00:56:50,000 --> 00:56:54,000
como uma matriz, mas por que, neste caso, estou propondo

1013
00:56:54,000 --> 00:56:59,000
ter também um elemento de cabeça que representa a cabeça de lista,

1014
00:56:59,000 --> 00:57:06,000
a frente da lista, a primeira pessoa da fila na loja da Apple, além de tamanho?

1015
00:57:06,000 --> 00:57:14,000
Por que eu preciso de uma peça adicional de dados aqui?

1016
00:57:14,000 --> 00:57:16,000
Pense de volta para o que os números é

1017
00:57:16,000 --> 00:57:18,000
se eu desenhei como se segue.

1018
00:57:18,000 --> 00:57:21,000
Suponhamos que esta é agora uma fila, em vez de uma pilha,

1019
00:57:21,000 --> 00:57:24,000
a diferença ser-assim como a fila de armazenamento da Apple é justo.

1020
00:57:24,000 --> 00:57:27,000
A primeira pessoa na linha no início da lista, o número 5, neste caso,

1021
00:57:27,000 --> 00:57:30,000
ele ou ela vai ser deixado na primeira loja.

1022
00:57:30,000 --> 00:57:32,000
Vamos fazer isso.

1023
00:57:32,000 --> 00:57:35,000
Suponha-se que este é o estado da minha fila neste momento no tempo, e agora a loja da Apple

1024
00:57:35,000 --> 00:57:39,000
abre ea primeira pessoa, número 5, é conduzido para a loja.

1025
00:57:39,000 --> 00:57:43,000
Como faço para mudar o quadro, agora que eu de-fila a primeira pessoa

1026
00:57:43,000 --> 00:57:47,000
na parte da frente da linha?

1027
00:57:47,000 --> 00:57:50,000
O que é isso? >> [Estudante] Alterar a fila.

1028
00:57:50,000 --> 00:57:52,000
Mudar a cabeça, de modo 5 desaparece.

1029
00:57:52,000 --> 00:57:56,000
Na realidade, é como se, a melhor forma de fazer isso?

1030
00:57:56,000 --> 00:58:00,000
Na realidade, é como se esse cara desaparece.

1031
00:58:00,000 --> 00:58:03,000
Qual seria o número 7 fazer em uma loja real?

1032
00:58:03,000 --> 00:58:05,000
Eles iriam dar um grande passo para a frente.

1033
00:58:05,000 --> 00:58:08,000
>> Mas o que temos vindo a apreciar quando se trata de matrizes

1034
00:58:08,000 --> 00:58:10,000
e mover as coisas?

1035
00:58:10,000 --> 00:58:12,000
Isso é um desperdício do seu tempo, certo?

1036
00:58:12,000 --> 00:58:16,000
Por que você tem que ser tão anal como ter a primeira pessoa

1037
00:58:16,000 --> 00:58:21,000
no início da linha de fisicamente o início do bloco de memória?

1038
00:58:21,000 --> 00:58:23,000
Isso é completamente desnecessário. Por quê?

1039
00:58:23,000 --> 00:58:26,000
O que eu poderia apenas lembrar em vez disso? >> [Resposta do aluno inaudível]

1040
00:58:26,000 --> 00:58:30,000
Exatamente, eu poderia apenas lembrar com esta cabeça adicional membro de dados

1041
00:58:30,000 --> 00:58:34,000
que agora o cabeça da lista já não é 0, o que foi um momento atrás.

1042
00:58:34,000 --> 00:58:39,000
Agora é realmente o número 1. Desta forma, recebo uma otimização leve.

1043
00:58:39,000 --> 00:58:44,000
Só porque eu tenho de-fila alguém de linha no início da linha na loja da Apple

1044
00:58:44,000 --> 00:58:47,000
não significa que todo mundo tem que mudar, que recall é uma operação linear.

1045
00:58:47,000 --> 00:58:50,000
Eu posso passar o tempo ao invés única constante

1046
00:58:50,000 --> 00:58:53,000
e, em seguida, obter uma resposta muito mais rápida.

1047
00:58:53,000 --> 00:58:56,000
Mas o preço que eu estou pagando é o que ganhar esse adicional de desempenho

1048
00:58:56,000 --> 00:58:58,000
e não ter que mudar todos?

1049
00:58:58,000 --> 00:59:01,000
Sim. >> [Resposta do aluno inaudível]

1050
00:59:01,000 --> 00:59:04,000
Pode adicionar mais pessoas, bem, o problema é ortogonal

1051
00:59:04,000 --> 00:59:07,000
ao fato de que nós não estamos mudando as pessoas ao redor.

1052
00:59:07,000 --> 00:59:11,000
É ainda uma matriz, para se vamos ou não mudar todos ou não-

1053
00:59:11,000 --> 00:59:13,000
oh, eu vejo o que você quer dizer, tudo bem.

1054
00:59:13,000 --> 00:59:16,000
Na verdade, eu concordo com o que você está dizendo em que é quase como se

1055
00:59:16,000 --> 00:59:19,000
nós nunca estamos indo agora para usar o início desta matriz mais

1056
00:59:19,000 --> 00:59:22,000
porque se eu remover 5, então eu remover 7.

1057
00:59:22,000 --> 00:59:24,000
Mas eu só colocar as pessoas para a direita.

1058
00:59:24,000 --> 00:59:28,000
>> Parece que eu estou perdendo espaço e, finalmente, minha fila se desintegra em nada,

1059
00:59:28,000 --> 00:59:31,000
portanto, pode apenas ter envolvente pessoas,

1060
00:59:31,000 --> 00:59:35,000
e podemos pensar dessa matriz realmente como uma espécie de estrutura circular,

1061
00:59:35,000 --> 00:59:38,000
mas usamos o operador em C para fazer esse tipo de envolvente?

1062
00:59:38,000 --> 00:59:40,000
[Resposta do aluno inaudível] >> O operador módulo.

1063
00:59:40,000 --> 00:59:43,000
Seria um pouco chato para pensar em como você faz a envolvente,

1064
00:59:43,000 --> 00:59:46,000
mas poderia fazê-lo, e nós poderíamos começar a colocar as pessoas no que costumava ser a frente da linha,

1065
00:59:46,000 --> 00:59:52,000
mas lembre-se com esta variável cabeça que a cabeça de uma linha realmente é.

1066
00:59:52,000 --> 00:59:57,000
E se, em vez disso, nosso objetivo, em última análise, no entanto,

1067
00:59:57,000 --> 01:00:00,000
era para procurar números, como fizemos aqui no palco com Anita,

1068
01:00:00,000 --> 01:00:02,000
mas nós realmente queremos o melhor de todos os mundos?

1069
01:00:02,000 --> 01:00:05,000
Nós queremos mais do que sofisticação matriz permite que

1070
01:00:05,000 --> 01:00:09,000
porque queremos que a capacidade de crescer de forma dinâmica a estrutura de dados.

1071
01:00:09,000 --> 01:00:12,000
Mas nós não queremos ter que recorrer a algo que nós indicamos

1072
01:00:12,000 --> 01:00:15,000
na primeira conferência não era um algoritmo ótimo,

1073
01:00:15,000 --> 01:00:17,000
o de busca linear.

1074
01:00:17,000 --> 01:00:21,000
Acontece que você pode, de fato, alcançar

1075
01:00:21,000 --> 01:00:24,000
ou pelo menos perto de tempo constante, em que alguém como Anita,

1076
01:00:24,000 --> 01:00:27,000
se ela configura a estrutura de dados não ser uma lista ligada,

1077
01:00:27,000 --> 01:00:30,000
a não ser uma pilha, a não ser uma fila, pode, na verdade,

1078
01:00:30,000 --> 01:00:33,000
chegar a uma estrutura de dados que lhe permite olhar para as coisas,

1079
01:00:33,000 --> 01:00:37,000
mesmo palavras, não apenas em números, o que nós chamamos de tempo constante.

1080
01:00:37,000 --> 01:00:40,000
>> E, de fato, olhando para frente, uma das Série de Exercícios nesta classe é quase sempre

1081
01:00:40,000 --> 01:00:43,000
a implementação de um corretor ortográfico, em que

1082
01:00:43,000 --> 01:00:46,000
nós damos-lhe algumas palavras novamente 150.000 ingleses eo objetivo é

1083
01:00:46,000 --> 01:00:51,000
carregar os para a memória e rapidamente ser capaz de responder às perguntas do formulário

1084
01:00:51,000 --> 01:00:54,000
é esta palavra soletrada corretamente?

1085
01:00:54,000 --> 01:00:58,000
E seria realmente chupar se você tivesse que percorrer todos os 150 mil palavras para responder a isso.

1086
01:00:58,000 --> 01:01:02,000
Mas, na verdade, nós vamos ver que nós podemos fazê-lo em tempo muito, muito rápido.

1087
01:01:02,000 --> 01:01:06,000
E vai envolver algo implementação chamada tabela hash,

1088
01:01:06,000 --> 01:01:09,000
e mesmo que à primeira vista essa coisa chamada uma tabela hash vai

1089
01:01:09,000 --> 01:01:12,000
vamos alcançar esses super-rápidos tempos de resposta,

1090
01:01:12,000 --> 01:01:18,000
verifica-se que há, de facto, um problema.

1091
01:01:18,000 --> 01:01:23,000
Quando chega a hora de implementar esta coisa chamada de novo, eu estou fazendo isso de novo.

1092
01:01:23,000 --> 01:01:25,000
Eu sou o único aqui.

1093
01:01:25,000 --> 01:01:28,000
Quando chega a hora de implementar essa coisa chamada uma tabela hash,

1094
01:01:28,000 --> 01:01:30,000
nós vamos ter que tomar uma decisão.

1095
01:01:30,000 --> 01:01:32,000
Qual deve ser essa coisa realmente ser?

1096
01:01:32,000 --> 01:01:36,000
E quando começamos a inserção de números para esta tabela hash,

1097
01:01:36,000 --> 01:01:38,000
como é que vamos para armazená-los de tal forma

1098
01:01:38,000 --> 01:01:42,000
que pode levá-los de volta o mais rápido que chegamos los?

1099
01:01:42,000 --> 01:01:45,000
Mas vamos ver antes de tempo que esta questão de

1100
01:01:45,000 --> 01:01:48,000
Quando o aniversário de todos está na classe será bastante pertinente.

1101
01:01:48,000 --> 01:01:51,000
Acontece que nesta sala, temos algumas centenas de pessoas,

1102
01:01:51,000 --> 01:01:56,000
assim as chances de que dois de nós têm a mesma data de aniversário é provavelmente bastante elevado.

1103
01:01:56,000 --> 01:01:58,000
E se houvesse apenas 40 de nós nesta sala?

1104
01:01:58,000 --> 01:02:02,000
Quais são as chances de duas pessoas que têm a mesma data de aniversário?

1105
01:02:02,000 --> 01:02:04,000
[Os alunos] Mais de 50%.

1106
01:02:04,000 --> 01:02:06,000
Sim, mais de 50%. Na verdade, eu ainda trouxe um gráfico.

1107
01:02:06,000 --> 01:02:08,000
Acontece, e isso é realmente apenas um sneak preview-

1108
01:02:08,000 --> 01:02:12,000
se há apenas 58 de nós nesta sala, a probabilidade de dois de nós

1109
01:02:12,000 --> 01:02:16,000
ter a mesma data de aniversário é extremamente alta, quase 100%,

1110
01:02:16,000 --> 01:02:20,000
e que vai causar um monte de dor para nós na quarta-feira.

1111
01:02:20,000 --> 01:02:24,000
>> Com isso dito, vamos adiar aqui. Vemo-nos na quarta-feira.

1112
01:02:24,000 --> 01:02:28,000
[Aplausos]

1113
01:02:28,000 --> 01:02:30,000
[CS50.TV]