1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [Semana 6, continuação]

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

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

4
00:00:08,720 --> 00:00:12,970
Este é CS50 e este é o fim da semana 6.

5
00:00:12,970 --> 00:00:17,970
Então CS50x, um dos primeiros cursos de Harvard envolvidos na iniciativa EDX

6
00:00:17,970 --> 00:00:20,590
de fato estreou esta segunda-feira passada.

7
00:00:20,590 --> 00:00:23,460
Se você gostaria de obter um vislumbre do que os outros na Internet

8
00:00:23,460 --> 00:00:27,180
estão agora acompanhando com, você pode ir para x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Que irá redirecioná-lo para o local apropriado no edx.org,

10
00:00:30,350 --> 00:00:34,160
que foi onde este e outros cursos do MIT e Berkeley vivem agora.

11
00:00:34,160 --> 00:00:38,140
Você vai ter que se inscrever para uma conta, você vai descobrir que o material é basicamente o mesmo

12
00:00:38,140 --> 00:00:42,170
como você teve neste semestre, embora algumas semanas atrasadas, como temos tudo pronto.

13
00:00:42,170 --> 00:00:46,930
Mas o que os alunos em CS50x vai ver agora é uma interface bastante como este.

14
00:00:46,930 --> 00:00:50,040
Este, por exemplo, é Zamyla levando passo a passo para conjunto de problemas 0.

15
00:00:50,040 --> 00:00:54,230
Ao fazer o login para edx.org, um estudante CS50x vê os tipos de coisas

16
00:00:54,230 --> 00:00:57,170
que seria de esperar para ver em um curso: a palestra para a segunda-feira,

17
00:00:57,170 --> 00:01:01,650
palestra para quarta-feira, shorts diversos, os conjuntos de problemas, as orientações, PDFs.

18
00:01:01,650 --> 00:01:04,459
Além disso, como você vê aqui, traduções automáticas

19
00:01:04,459 --> 00:01:08,390
transcrições de inglês para chinês, japonês, espanhol, italiano,

20
00:01:08,390 --> 00:01:12,810
e um bando inteiro de outras línguas que certamente vai ser imperfeito

21
00:01:12,810 --> 00:01:15,840
como nós rolamos-los programaticamente usando uma coisa chamada API,

22
00:01:15,840 --> 00:01:18,360
ou interface de programação de aplicativo, do Google

23
00:01:18,360 --> 00:01:21,360
que nos permite converter Inglês para essas outras línguas.

24
00:01:21,360 --> 00:01:24,100
Mas, graças ao maravilhoso espírito de alguns voluntários mais de cem,

25
00:01:24,100 --> 00:01:26,940
pessoas aleatórias na Internet que gentilmente oferecidos a se envolver

26
00:01:26,940 --> 00:01:30,180
Neste projeto, nós vamos ser gradualmente melhorar a qualidade dessas traduções

27
00:01:30,180 --> 00:01:35,790
por ter humanos corrigir os erros que nossos computadores fizeram.

28
00:01:35,790 --> 00:01:42,330
>> Assim, verifica-se que havia alguns estudantes mais aparecer na segunda-feira do que o inicialmente esperado.

29
00:01:42,330 --> 00:01:48,980
Na verdade, agora CS50x tem 100.000 pessoas que seguem junto em casa.

30
00:01:48,980 --> 00:01:54,430
Então, percebe que são todos parte dessa aula inaugural de fazer este curso de ciência da computação

31
00:01:54,430 --> 00:01:57,370
educação mais geralmente, de forma mais ampla, acessível.

32
00:01:57,370 --> 00:02:00,130
E a realidade é agora, com alguns desses cursos massivos online,

33
00:02:00,130 --> 00:02:04,070
todas elas começam com estes números muito elevados, como parece ter feito aqui.

34
00:02:04,070 --> 00:02:08,759
Mas o objetivo, em última instância, para CS50x é realmente levar as pessoas como muitos a linha de chegada quanto possível.

35
00:02:08,759 --> 00:02:12,000
Pelo projeto, CS50x vai ser oferecido a partir desta segunda-feira passada

36
00:02:12,000 --> 00:02:17,430
todo o caminho até 15 de abril de 2013, para que as pessoas que têm compromissos escolares em outros lugares,

37
00:02:17,430 --> 00:02:20,990
trabalho, a família, os conflitos outros e semelhantes, tem um pouco mais de flexibilidade

38
00:02:20,990 --> 00:02:23,640
com o qual a mergulhar neste curso, que, basta dizer,

39
00:02:23,640 --> 00:02:30,540
é bastante ambiciosa feito apenas ao longo de apenas três meses, durante um semestre de costume.

40
00:02:30,540 --> 00:02:34,190
Mas esses alunos serão enfrentar os conjuntos mesmo problema, vendo o mesmo conteúdo,

41
00:02:34,190 --> 00:02:36,350
ter acesso aos mesmos calções e semelhantes.

42
00:02:36,350 --> 00:02:38,990
Então, percebemos que todos nós somos verdadeiramente juntos nessa.

43
00:02:38,990 --> 00:02:42,360
E um dos objetivos finais de CS50x não é só para ter pessoas como muitos

44
00:02:42,360 --> 00:02:45,720
para a linha de chegada e dar-lhes essa nova compreensão da ciência da computação

45
00:02:45,720 --> 00:02:49,000
e programação, mas também para que eles têm essa experiência compartilhada.

46
00:02:49,000 --> 00:02:52,010
Uma das características definidoras de 50 no campus, esperamos,

47
00:02:52,010 --> 00:02:56,260
foi este tipo de experiência comum, para melhor ou para pior, às vezes,

48
00:02:56,260 --> 00:02:59,480
mas ter essas pessoas a voltar-se para a esquerda e para a direita,

49
00:02:59,480 --> 00:03:01,830
e as horas de expediente e Hackathon e da feira.

50
00:03:01,830 --> 00:03:04,560
É um pouco mais difícil de fazer isso pessoalmente com pessoas on-line,

51
00:03:04,560 --> 00:03:10,580
mas CS50x vai concluir em abril, com a primeira CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
que será uma adaptação online da nossa idéia da feira

53
00:03:13,630 --> 00:03:18,250
onde estes milhares de estudantes todos serão convidados a apresentar uma 1 - a 2 minutos de vídeo,

54
00:03:18,250 --> 00:03:22,480
ou um screencast de seu projeto final ou vídeo deles acenando Olá

55
00:03:22,480 --> 00:03:24,490
e falar sobre seu projeto e demos-lo,

56
00:03:24,490 --> 00:03:27,610
bem como os seus antecessores fizeram aqui no campus da feira,

57
00:03:27,610 --> 00:03:31,400
de modo que até o final do semestre, a esperança é ter uma exposição global

58
00:03:31,400 --> 00:03:37,080
de projetos dos alunos CS50x 'finais, bem como aquele que o espera em dezembro aqui no campus.

59
00:03:37,080 --> 00:03:39,680
Assim, mais do que em próximos meses.

60
00:03:39,680 --> 00:03:43,640
>> Com 100.000 estudantes, porém, vem a necessidade de uma CAs mais alguns.

61
00:03:43,640 --> 00:03:47,590
Dado que vocês estão abrindo a trilha aqui e tendo CS50

62
00:03:47,590 --> 00:03:51,630
várias semanas antes do lançamento deste material para as pessoas em EDX,

63
00:03:51,630 --> 00:03:55,330
perceber que gostaríamos de envolver como muitos de nossos próprios alunos quanto possível a esta iniciativa,

64
00:03:55,330 --> 00:03:58,720
tanto durante o semestre, assim como neste inverno e na próxima Primavera.

65
00:03:58,720 --> 00:04:01,620
Então, se você gostaria de se envolver em CS50x,

66
00:04:01,620 --> 00:04:07,450
juntando-se particularmente em CS50x discutir, a versão de EDX CS50 discutir,

67
00:04:07,450 --> 00:04:10,140
que muitos de vocês estão usando no campus, no quadro de avisos online,

68
00:04:10,140 --> 00:04:13,040
por favor, faça a cabeça para essa URL, deixe-nos saber quem você é,

69
00:04:13,040 --> 00:04:16,450
porque nós adoraríamos para construir uma equipe de alunos e funcionários e professores iguais

70
00:04:16,450 --> 00:04:19,630
no campus que estão simplesmente jogando bem e ajudando.

71
00:04:19,630 --> 00:04:21,720
E quando vêem uma questão que é familiar a eles,

72
00:04:21,720 --> 00:04:25,320
você ouve um estudante relatar algum bug em algum lugar lá fora, em algum país na Internet,

73
00:04:25,320 --> 00:04:27,450
e que toca uma campainha porque você também teve que mesmo assunto

74
00:04:27,450 --> 00:04:32,620
em seu d-hall, há algum tempo, espero, então você pode dialogar e partilhar a sua própria experiência.

75
00:04:32,620 --> 00:04:37,300
Então por favor não participar se você gostaria.

76
00:04:37,300 --> 00:04:39,360
>> Cursos de ciência da computação na Universidade de Harvard tem um pouco de uma tradição,

77
00:04:39,360 --> 00:04:44,730
CS50 entre eles, de ter algum fato, algumas roupas, que você pode usar com orgulho

78
00:04:44,730 --> 00:04:49,090
no final do semestre, dizendo com um certo orgulho que você terminou CS50

79
00:04:49,090 --> 00:04:51,830
e tomou CS50 e afins, e nós tentamos sempre envolver os alunos

80
00:04:51,830 --> 00:04:54,540
neste processo, tanto quanto possível, em que convidamos,

81
00:04:54,540 --> 00:04:56,900
nessa época do semestre, os alunos a apresentarem projetos

82
00:04:56,900 --> 00:04:59,330
usando o Photoshop, ou qualquer ferramenta de escolha que você gostaria de usar

83
00:04:59,330 --> 00:05:02,330
se você é um designer, a submeter projetos para T-shirts e camisolas

84
00:05:02,330 --> 00:05:06,100
e guarda-sóis e bandanas para cães pequenos que temos agora e similares.

85
00:05:06,100 --> 00:05:09,370
E tudo é então - os vencedores de cada ano são, então, exibiu

86
00:05:09,370 --> 00:05:12,700
no site do curso em store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Tudo é vendido ao custo de lá, mas o site só funciona sozinho

88
00:05:15,790 --> 00:05:18,330
e permite que as pessoas a escolher as cores e desenhos que eles gostam.

89
00:05:18,330 --> 00:05:20,420
Então eu pensei que tinha acabado de partilhar alguns dos projetos do ano passado

90
00:05:20,420 --> 00:05:25,130
que estavam no site além deste aqui, que é uma tradição anual.

91
00:05:25,130 --> 00:05:29,410
"Todo dia eu estou Seg Faultn" era uma das propostas do ano passado,

92
00:05:29,410 --> 00:05:32,290
que ainda está disponível lá para ex-alunos.

93
00:05:32,290 --> 00:05:35,820
Tivemos um presente ", CS50, Fundação 1989."

94
00:05:35,820 --> 00:05:39,010
Um dos nossos Bowdens, Rob, era muito popular no ano passado.

95
00:05:39,010 --> 00:05:43,480
"Team Bowden" nasceu, este projeto foi submetido, entre os mais vendidos.

96
00:05:43,480 --> 00:05:49,040
Como foi este aqui. Muitas pessoas tiveram "Fever Bowden" de acordo com os registros de vendas.

97
00:05:49,040 --> 00:05:52,650
Perceba que que poderia agora ser seu projeto lá, em cima da Internet.

98
00:05:52,650 --> 00:05:57,510
Mais detalhes sobre este problema na próxima define por vir.

99
00:05:57,510 --> 00:06:00,330
>> Mais uma ferramenta: você teve alguma exposição e espero que agora

100
00:06:00,330 --> 00:06:02,350
alguma experiência hands-on com o GDB,

101
00:06:02,350 --> 00:06:04,570
que é, naturalmente, um depurador e permite que você manipule

102
00:06:04,570 --> 00:06:09,500
o seu programa em um nível bastante baixo, fazendo o tipo de coisas?

103
00:06:09,500 --> 00:06:13,030
O que o GDB deixar você fazer?

104
00:06:13,030 --> 00:06:15,030
Sim? Dê-me alguma coisa. [Responder Estudante, ininteligível]

105
00:06:15,030 --> 00:06:18,120
Bom. Etapa em função, para que você não só tem que digitar run

106
00:06:18,120 --> 00:06:22,310
e ter o golpe programa através do seu conjunto, imprimir coisas para a saída padrão.

107
00:06:22,310 --> 00:06:25,190
Em vez disso, você pode percorrê-lo linha por linha, digitando próxima

108
00:06:25,190 --> 00:06:30,300
ir linha por linha por linha ou passo para mergulhar em uma função, normalmente aquele que você escreveu.

109
00:06:30,300 --> 00:06:35,240
O que mais faz GDB deixar você fazer? Sim? [Responder Estudante, ininteligível]

110
00:06:35,240 --> 00:06:38,100
Imprimir variáveis. Então, se você quer fazer um pouco de introspecção dentro de seu programa

111
00:06:38,100 --> 00:06:41,500
sem ter que recorrer a escrever instruções printf em todo o lugar,

112
00:06:41,500 --> 00:06:44,600
você pode apenas imprimir uma variável ou exibir uma variável.

113
00:06:44,600 --> 00:06:46,710
O que mais você pode fazer com um depurador como o GDB?

114
00:06:46,710 --> 00:06:49,170
[Responder Estudante, ininteligível]

115
00:06:49,170 --> 00:06:52,080
Exatamente. Você pode definir pontos de interrupção, você pode dizer que a execução pausa

116
00:06:52,080 --> 00:06:54,020
a função principal ou a função foo.

117
00:06:54,020 --> 00:06:56,800
Você pode dizer que a execução pausa na linha 123.

118
00:06:56,800 --> 00:06:58,950
E pontos de interrupção são uma técnica muito poderosa

119
00:06:58,950 --> 00:07:01,110
porque se você tem uma sensação geral de que o seu problema

120
00:07:01,110 --> 00:07:05,360
provavelmente é, você não precisa perder tempo percorrendo totalidade do programa.

121
00:07:05,360 --> 00:07:08,250
Você pode pular essencialmente à direita e então começar a escrever -

122
00:07:08,250 --> 00:07:10,970
percorrendo-a com passo ou próximo ou semelhante.

123
00:07:10,970 --> 00:07:14,340
Mas o problema com algo parecido com o GDB é que ele ajuda você, o humano,

124
00:07:14,340 --> 00:07:16,940
encontrar os seus problemas e encontrar seus bugs.

125
00:07:16,940 --> 00:07:19,470
Isso não significa necessariamente encontrá-los muito por você.

126
00:07:19,470 --> 00:07:23,070
>> Então, nós introduzimos o style50 outro dia, que é uma ferramenta de linha de comando curta

127
00:07:23,070 --> 00:07:27,500
que tenta estilizar seu código um pouco mais limpa do que você, o humano, poderia ter feito.

128
00:07:27,500 --> 00:07:29,530
Mas isso, também, é realmente apenas uma coisa estética.

129
00:07:29,530 --> 00:07:34,110
Mas acontece que há essa outra ferramenta chamada Valgrind que é um pouco mais misterioso de usar.

130
00:07:34,110 --> 00:07:36,860
Sua saída é atrozmente enigmática, à primeira vista.

131
00:07:36,860 --> 00:07:39,420
Mas é maravilhosamente útil, especialmente agora que estamos na parte do termo

132
00:07:39,420 --> 00:07:43,080
onde você está começando a usar malloc e alocação dinâmica de memória.

133
00:07:43,080 --> 00:07:45,420
As coisas podem dar muito, muito errado rapidamente.

134
00:07:45,420 --> 00:07:49,320
Porque se você esquecer de libertar a sua memória, ou você cancelar a referência de algum ponteiro NULL,

135
00:07:49,320 --> 00:07:55,770
ou você cancelar a referência de algum ponteiro de lixo, que normalmente é o sintoma que resultados?

136
00:07:55,770 --> 00:07:59,470
Seg culpa. E você começa este arquivo núcleo de algum número de kilobytes ou megabytes

137
00:07:59,470 --> 00:08:02,990
que representa o estado da memória do seu programa quando ele caiu,

138
00:08:02,990 --> 00:08:05,730
mas o seu programa, em última análise seg falhas, falha de segmentação,

139
00:08:05,730 --> 00:08:08,450
o que significa que algo de ruim aconteceu quase sempre relacionados

140
00:08:08,450 --> 00:08:11,750
a um erro relacionado com a memória que você fez em algum lugar.

141
00:08:11,750 --> 00:08:14,100
Então Valgrind ajuda a encontrar coisas como esta.

142
00:08:14,100 --> 00:08:17,720
É uma ferramenta que você execute, como GDB, depois de ter compilado seu programa,

143
00:08:17,720 --> 00:08:20,330
mas em vez de executar o programa diretamente, você corre Valgrind

144
00:08:20,330 --> 00:08:23,960
e você passar para ele o seu programa, assim como você faz com o GDB.

145
00:08:23,960 --> 00:08:26,220
Agora, o uso, para obter o melhor tipo de saída,

146
00:08:26,220 --> 00:08:30,410
é um pouco longo, por isso lá no topo da tela, você verá Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" quase universalmente significa verbose quando você está usando programas em um computador Linux.

148
00:08:35,350 --> 00:08:38,770
Então isso significa cuspir mais dados do que você pode, por padrão.

149
00:08:38,770 --> 00:08:45,510
"- Leak-check = total". Este é apenas dizer seleção para todos os possíveis vazamentos de memória,

150
00:08:45,510 --> 00:08:49,430
erros que eu poderia ter feito. Isto, também, é um paradigma comum com programas Linux.

151
00:08:49,430 --> 00:08:52,710
Geralmente, se você tem um argumento de linha de comando que é um "interruptor",

152
00:08:52,710 --> 00:08:55,830
que deveria mudar o comportamento do programa, e é uma única letra,

153
00:08:55,830 --> 00:09:00,310
é-v, mas se isso está ligado, apenas pelo design do programador,

154
00:09:00,310 --> 00:09:05,150
é uma palavra completa ou série de palavras, o argumento de linha de comando começa com -.

155
00:09:05,150 --> 00:09:08,190
Estes são apenas convenções humanas, mas você vai vê-los cada vez mais.

156
00:09:08,190 --> 00:09:12,410
E, em seguida, finalmente, "a.out" é o nome arbitrário para o programa, neste exemplo particular.

157
00:09:12,410 --> 00:09:14,640
E aqui vai uma saída representativa.

158
00:09:14,640 --> 00:09:22,890
>> Antes de olharmos para o que isso significa, deixe-me ir para um trecho de código aqui.

159
00:09:22,890 --> 00:09:26,390
E deixe-me passar esta fora do caminho, em breve,

160
00:09:26,390 --> 00:09:32,120
e vamos dar uma olhada em memory.c, que é este pequeno exemplo aqui.

161
00:09:32,120 --> 00:09:36,290
Portanto, neste programa, deixe-me zoom e as funções e perguntas.

162
00:09:36,290 --> 00:09:39,430
Nós temos uma função principal que chama uma função, f,

163
00:09:39,430 --> 00:09:45,590
e então o que se f continuar a fazer, em Inglês um pouco técnico?

164
00:09:45,590 --> 00:09:49,760
O que faz f proceder para fazer?

165
00:09:49,760 --> 00:09:53,680
Que tal eu vou começar com a linha 20, e localização da estrela não importa,

166
00:09:53,680 --> 00:09:56,720
mas eu só vou ser coerente aqui com última palestra.

167
00:09:56,720 --> 00:09:59,910
Qual é a linha 20 não para nós? No lado da mão esquerda. Vamos dividi-la ainda mais.

168
00:09:59,910 --> 00:10:02,410
Int * x: o que é que faz?

169
00:10:02,410 --> 00:10:04,940
Okay. É declarar um ponteiro, e agora vamos ser ainda mais técnico.

170
00:10:04,940 --> 00:10:10,230
O que significa, muito concretamente, para declarar um ponteiro? Alguém mais?

171
00:10:10,230 --> 00:10:15,050
Sim? [Responder Estudante, ininteligível] Muito longe.

172
00:10:15,050 --> 00:10:17,060
Então você está lendo para o lado direito do sinal de igual.

173
00:10:17,060 --> 00:10:20,290
Vamos nos concentrar apenas na esquerda, apenas em int * x.

174
00:10:20,290 --> 00:10:24,700
Isso significa "declarar" um ponteiro, mas agora vamos mergulhar mais fundo para essa definição.

175
00:10:24,700 --> 00:10:28,330
O que isso concretamente, tecnicamente significa? Sim?

176
00:10:28,330 --> 00:10:31,940
[Responder Estudante, ininteligível]

177
00:10:31,940 --> 00:10:35,090
Okay. Ele está se preparando para gravar um endereço na memória.

178
00:10:35,090 --> 00:10:40,680
Bom. E vamos dar um passo adiante, que é declarar uma variável, x, que é de 32 bits.

179
00:10:40,680 --> 00:10:44,440
E eu sei que é de 32 bits porque -?

180
00:10:44,440 --> 00:10:47,390
Não é porque é um int, porque é um ponteiro neste caso.

181
00:10:47,390 --> 00:10:49,650
Coincidência que é um eo mesmo com um int,

182
00:10:49,650 --> 00:10:51,970
mas o fato de que não é a estrela que significa que este é um ponteiro

183
00:10:51,970 --> 00:10:57,300
e no interior do aparelho, como acontece com muitos computadores, mas não todas, as indicações são de 32 bits.

184
00:10:57,300 --> 00:11:01,850
Em mais hardware moderno, como os mais recentes Macs, os mais recentes PCs, você pode ter ponteiros de 64 bits,

185
00:11:01,850 --> 00:11:04,160
mas no aparelho, essas coisas são de 32 bits.

186
00:11:04,160 --> 00:11:08,380
Então, vamos padronizar isso. Mais concretamente, a história é a seguinte:

187
00:11:08,380 --> 00:11:10,820
Nós "declarar" um ponteiro, o que é que isso significa?

188
00:11:10,820 --> 00:11:12,810
Nós nos preparamos para armazenar um endereço de memória.

189
00:11:12,810 --> 00:11:15,530
O que significa isso?

190
00:11:15,530 --> 00:11:19,810
Nós criamos uma variável chamada x, que ocupa 32 bits

191
00:11:19,810 --> 00:11:23,810
que em breve armazenar o endereço de um inteiro.

192
00:11:23,810 --> 00:11:26,470
E isso é provavelmente tão preciso quanto podemos chegar.

193
00:11:26,470 --> 00:11:31,810
É bom avançar para simplificar o mundo e dizer declarar um ponteiro chamado x.

194
00:11:31,810 --> 00:11:35,380
Declare um ponteiro, mas perceber e entender o que está realmente acontecendo

195
00:11:35,380 --> 00:11:38,490
mesmo em apenas alguns desses personagens.

196
00:11:38,490 --> 00:11:42,040
>> Agora, este é quase um pouco mais fácil, mesmo que seja uma mais expressão.

197
00:11:42,040 --> 00:11:48,160
Então o que é que esta fazendo, que é destaque agora: "malloc (10 * sizeof (int));" Sim?

198
00:11:48,160 --> 00:11:52,350
[Responder Estudante, ininteligível]

199
00:11:52,350 --> 00:11:58,250
Bom. E eu vou levá-lo lá. É atribuição de um bloco de memória para 10 inteiros.

200
00:11:58,250 --> 00:12:02,190
E agora vamos mergulhar em um pouco mais profunda, que é alocar um bloco de memória para 10 inteiros.

201
00:12:02,190 --> 00:12:05,390
O que é malloc depois retornar?

202
00:12:05,390 --> 00:12:10,390
O endereço do bloco, ou, de forma mais concreta, o endereço do primeiro byte do referido pedaço.

203
00:12:10,390 --> 00:12:14,080
Como, então, sou eu, o programador, para saber onde esse pedaço de fins de memória?

204
00:12:14,080 --> 00:12:18,340
Eu sei que é contíguo. Malloc, por definição, lhe dará um pedaço contíguo de memória.

205
00:12:18,340 --> 00:12:21,240
Nenhum lacunas. Você tem acesso a todos os bytes nesse pedaço,

206
00:12:21,240 --> 00:12:26,760
de costas para trás, mas como eu sei que o fim deste pedaço de memória é?

207
00:12:26,760 --> 00:12:28,850
Quando você usa malloc? [Responder Estudante, ininteligível] Boa.

208
00:12:28,850 --> 00:12:30,670
Você não. Você tem que se lembrar.

209
00:12:30,670 --> 00:12:35,960
Eu tenho que lembrar que eu usei o valor 10, e eu não parecem mesmo ter feito isso aqui.

210
00:12:35,960 --> 00:12:41,000
Mas a responsabilidade é inteiramente em mim. Strlen, que nos tornamos um pouco dependente para cordas,

211
00:12:41,000 --> 00:12:45,860
só funciona por causa dessa convenção de ter \ 0

212
00:12:45,860 --> 00:12:48,840
ou este caráter especial nul, NUL, no final de uma string.

213
00:12:48,840 --> 00:12:51,740
Isso não vale para apenas pedaços arbitrários de memória.

214
00:12:51,740 --> 00:12:58,590
Cabe a você. Assim, a linha 20, então, aloca um bloco de memória

215
00:12:58,590 --> 00:13:02,590
que pode armazenar 10 inteiros, e armazena o endereço do primeiro byte

216
00:13:02,590 --> 00:13:05,610
desse pedaço de memória na variável x chamado.

217
00:13:05,610 --> 00:13:11,140
Logo, o que é um ponteiro. Então, linha 21, infelizmente, foi um erro.

218
00:13:11,140 --> 00:13:16,110
Mas, primeiro, o que ele está fazendo? É dizer loja no local 10, 0 indexados,

219
00:13:16,110 --> 00:13:19,480
do bloco de memória chamado x o valor 0.

220
00:13:19,480 --> 00:13:21,510
>> Então, observe algumas coisas estão acontecendo.

221
00:13:21,510 --> 00:13:25,420
Mesmo que x é um ponteiro, lembrar de algumas semanas atrás

222
00:13:25,420 --> 00:13:29,440
que você ainda pode usar a matriz estilo de notação de colchete.

223
00:13:29,440 --> 00:13:36,180
Porque isso é realmente curto-mão notação para a aritmética de ponteiro mais crítico para o futuro.

224
00:13:36,180 --> 00:13:40,320
onde iríamos fazer algo como isto: Pegue o endereço x, mover mais de 10 pontos,

225
00:13:40,320 --> 00:13:44,550
em seguida, ir para lá a qualquer endereço é armazenado no local.

226
00:13:44,550 --> 00:13:48,090
Mas, francamente, este é apenas atroz de ler e se sentir confortável com.

227
00:13:48,090 --> 00:13:52,900
Assim, o mundo geralmente usa os colchetes só porque ele é muito mais humano-amigável para ler.

228
00:13:52,900 --> 00:13:55,140
Mas isso é o que realmente está acontecendo debaixo do capô;

229
00:13:55,140 --> 00:13:58,190
x é um endereço não, uma matriz, de per si.

230
00:13:58,190 --> 00:14:02,410
Portanto, este é armazenar 0 na posição 10 em x.

231
00:14:02,410 --> 00:14:06,120
Por que isso é ruim? Sim?

232
00:14:06,120 --> 00:14:17,370
[Responder Estudante, ininteligível] Exatamente.

233
00:14:17,370 --> 00:14:21,100
Nós só alocados 10 ints, mas contar de 0 ao programar em C,

234
00:14:21,100 --> 00:14:25,690
para que você tenha acesso a 0 10 1 2 3 4 5 6 7 8 9, mas não.

235
00:14:25,690 --> 00:14:30,270
Assim, ou o programa vai culpa seg ou não é.

236
00:14:30,270 --> 00:14:32,900
Mas nós realmente não sabemos, este é um tipo de comportamento não determinístico.

237
00:14:32,900 --> 00:14:35,600
Isso realmente depende se temos sorte.

238
00:14:35,600 --> 00:14:40,650
Se se verificar que o sistema operacional não se importa se eu usar esse byte extra,

239
00:14:40,650 --> 00:14:43,360
mesmo que não tenha dado para mim, o meu programa não pode falhar.

240
00:14:43,360 --> 00:14:46,780
É cru, é buggy, mas você não pode ver esse sintoma,

241
00:14:46,780 --> 00:14:48,960
ou você pode vê-lo só de vez em quando.

242
00:14:48,960 --> 00:14:51,230
Mas a realidade é que o bug é, de fato, não há.

243
00:14:51,230 --> 00:14:54,320
E é realmente problemático se você escreveu um programa que você quer ser correto,

244
00:14:54,320 --> 00:14:58,840
que você vendeu o programa que as pessoas estão usando que de vez em quando cai

245
00:14:58,840 --> 00:15:02,450
porque, é claro, este não é boa. De fato, se você tem um celular com Android ou um iPhone

246
00:15:02,450 --> 00:15:05,550
e você baixar aplicativos nos dias de hoje, se você já teve um app abortar,

247
00:15:05,550 --> 00:15:10,040
de repente ele desaparece, que é quase sempre o resultado de algum problema relacionado à memória,

248
00:15:10,040 --> 00:15:12,830
qual o programador asneira e dereferenced um ponteiro

249
00:15:12,830 --> 00:15:18,670
que ele ou ela não deve ter, eo resultado do iOS ou Android é apenas para matar o programa completo

250
00:15:18,670 --> 00:15:23,080
em vez de comportamento indefinido risco ou algum tipo de comprometimento da segurança.

251
00:15:23,080 --> 00:15:25,950
>> Há um outro bug no programa além deste.

252
00:15:25,950 --> 00:15:30,180
O que mais eu estraguei tudo neste programa?

253
00:15:30,180 --> 00:15:32,740
Eu não pratiquei o que eu tenho pregado. Sim?

254
00:15:32,740 --> 00:15:34,760
[Responder Estudante, ininteligível] Boa.

255
00:15:34,760 --> 00:15:36,880
Eu não libertou a memória. Portanto, a regra de ouro agora

256
00:15:36,880 --> 00:15:43,150
tem que ser sempre que você chamar malloc, você deve chamar livre quando você é feito usando a memória.

257
00:15:43,150 --> 00:15:45,610
Agora, quando eu iria querer libertar esta memória?

258
00:15:45,610 --> 00:15:49,780
Provavelmente, assumindo que esta primeira linha foi correta, eu gostaria de fazê-lo aqui.

259
00:15:49,780 --> 00:15:55,710
Porque eu não poderia, por exemplo, faça-o aqui. Por quê?

260
00:15:55,710 --> 00:15:57,860
Apenas fora do escopo. Assim, mesmo que estamos falando de ponteiros,

261
00:15:57,860 --> 00:16:04,830
esta é uma semana 2 ou 3 questão, em que x é apenas um alcance dentro das chavetas onde foi declarado.

262
00:16:04,830 --> 00:16:11,000
Então você definitivamente não pode libertá-lo lá. Minha única chance de libertá-la é de aproximadamente após a linha 21.

263
00:16:11,000 --> 00:16:15,170
Este é um programa bastante simples, era bastante fácil, uma vez que o tipo de enrolado sua mente

264
00:16:15,170 --> 00:16:17,870
em torno do que o programa está fazendo, onde os erros foram.

265
00:16:17,870 --> 00:16:20,500
E mesmo se você não vê-lo em primeiro lugar, espero que seja um pouco óbvio agora

266
00:16:20,500 --> 00:16:23,870
que esses erros são muito facilmente resolvidos e facilidade.

267
00:16:23,870 --> 00:16:28,720
Mas quando um programa é mais do que 12 linhas de tempo, é 50 linhas, 100 linhas,

268
00:16:28,720 --> 00:16:31,150
andar através de seu código linha por linha, pensando por isso, logicamente,

269
00:16:31,150 --> 00:16:35,110
é possível, mas não particularmente divertido de fazer, constantemente à procura de bugs,

270
00:16:35,110 --> 00:16:38,340
e também é difícil de fazer, e é por isso que uma ferramenta como Valgrind existe.

271
00:16:38,340 --> 00:16:40,900
Deixe-me ir em frente e fazer isso: deixe-me abrir a janela de terminal,

272
00:16:40,900 --> 00:16:45,400
e deixe-me não apenas executar memória, porque a memória parece estar bem.

273
00:16:45,400 --> 00:16:49,180
Eu estou tendo sorte. Indo para o byte adicional no fim da matriz

274
00:16:49,180 --> 00:16:51,060
não parece ser muito problemático.

275
00:16:51,060 --> 00:16:56,370
Mas deixe-me, no entanto, fazer uma verificação de sanidade mental, o que significa apenas para verificar

276
00:16:56,370 --> 00:16:58,320
se este é ou não realmente correto.

277
00:16:58,320 --> 00:17:04,690
>> Então vamos fazer valgrind-v - leak-check = completo,

278
00:17:04,690 --> 00:17:07,520
e, em seguida, o nome do programa, neste caso, é a memória, e não a.out.

279
00:17:07,520 --> 00:17:10,760
Então deixe-me ir em frente e fazer isso. Pressione Enter.

280
00:17:10,760 --> 00:17:14,109
Querido Deus. Esta é a sua saída, e é isso que me referi anteriormente.

281
00:17:14,109 --> 00:17:17,550
Mas, se você aprender a ler através de todos os disparates aqui,

282
00:17:17,550 --> 00:17:20,760
mais isso é apenas a saída de diagnóstico que não é tão interessante.

283
00:17:20,760 --> 00:17:24,829
O seu olho realmente quer estar procurando é qualquer menção de erro ou inválido.

284
00:17:24,829 --> 00:17:26,800
Palavras que sugerem problemas.

285
00:17:26,800 --> 00:17:29,340
E, de fato, vamos ver o que está acontecendo de errado aqui.

286
00:17:29,340 --> 00:17:35,230
Eu tenho um resumo de algum tipo, "em uso na saída:. 40 bytes em blocos de 1"

287
00:17:35,230 --> 00:17:38,750
Eu não tenho certeza do que um bloco é ainda, mas 40 bytes

288
00:17:38,750 --> 00:17:41,260
realmente se sente como se eu pudesse descobrir de onde que vem.

289
00:17:41,260 --> 00:17:45,030
40 bytes. Por que 40 bytes em uso na saída?

290
00:17:45,030 --> 00:17:48,780
E, mais especificamente, se rolar aqui,

291
00:17:48,780 --> 00:17:54,520
por que eu definitivamente perdeu 40 bytes? Sim?

292
00:17:54,520 --> 00:17:59,520
[Responder Estudante, ininteligível] Perfeito. Sim, exatamente.

293
00:17:59,520 --> 00:18:03,540
Havia dez números inteiros, e cada um destes é o tamanho de 4 ou 32 bits,

294
00:18:03,540 --> 00:18:08,300
então eu perdi exatamente 40 bytes, porque, como você propôs, eu não chamei livre.

295
00:18:08,300 --> 00:18:13,460
Isso é um erro, e agora vamos olhar para baixo um pouco mais e ver ao lado deste,

296
00:18:13,460 --> 00:18:16,900
"Inválido escrever de tamanho 4". Agora, o que é isso?

297
00:18:16,900 --> 00:18:21,150
Este endereço é expresso que a notação de base, aparentemente?

298
00:18:21,150 --> 00:18:23,640
Este é hexadecimal, ea qualquer momento você vê um número começando com 0x,

299
00:18:23,640 --> 00:18:29,410
isso significa hexadecimal, o que fizemos no caminho de volta, eu acho, seção pset 0 de perguntas,

300
00:18:29,410 --> 00:18:34,090
que era apenas para fazer um exercício de aquecimento, a conversão de decimal para hexadecimal para binário e assim por diante.

301
00:18:34,090 --> 00:18:39,220
Hexadecimal, apenas por convenção humana, é geralmente usado para representar ponteiros

302
00:18:39,220 --> 00:18:41,570
ou, de modo mais geral, aborda. É apenas uma convenção,

303
00:18:41,570 --> 00:18:45,340
porque é um pouco mais fácil de ler, é um pouco mais compacto do que algo como decimal,

304
00:18:45,340 --> 00:18:47,720
e binário é inútil para a maioria dos seres humanos de usar.

305
00:18:47,720 --> 00:18:50,840
Então agora o que isso significa? Bem, parece que há uma gravação inválido

306
00:18:50,840 --> 00:18:54,480
de tamanho 4 na linha 21 de memory.c.

307
00:18:54,480 --> 00:18:59,180
Então vamos voltar para a linha 21, e, de fato, é aqui que a gravação inválido.

308
00:18:59,180 --> 00:19:02,640
Então Valgrind não vai completamente segura minha mão e me diga o que a correção é,

309
00:19:02,640 --> 00:19:05,520
mas ele está detectando que eu estou fazendo uma gravação inválido.

310
00:19:05,520 --> 00:19:08,800
Estou tocando 4 bytes que eu não deveria ser, e, aparentemente, isso porque,

311
00:19:08,800 --> 00:19:13,960
como você apontou, eu estou fazendo [10] em vez de [9] maximamente

312
00:19:13,960 --> 00:19:16,660
ou [0] ou algo entre os dois.

313
00:19:16,660 --> 00:19:19,690
Com Valgrind, realizar qualquer momento que você está escrevendo um programa

314
00:19:19,690 --> 00:19:24,190
que usa ponteiros e utiliza a memória, e mais especificamente malloc,

315
00:19:24,190 --> 00:19:27,080
definitivamente o hábito de correr tanto tempo

316
00:19:27,080 --> 00:19:30,890
mas muito facilmente copiado e colado comando do Valgrind

317
00:19:30,890 --> 00:19:32,650
para ver se há alguns erros lá.

318
00:19:32,650 --> 00:19:34,820
E vai ser esmagadora cada vez que você ver a saída,

319
00:19:34,820 --> 00:19:39,430
mas apenas analisar visualmente através de toda a saída e veja se você ver menções de erros

320
00:19:39,430 --> 00:19:43,190
ou avisos ou inválido ou perdido.

321
00:19:43,190 --> 00:19:46,200
Quaisquer palavras que soam como você errou em algum lugar.

322
00:19:46,200 --> 00:19:48,580
Então percebe que é uma nova ferramenta em seu toolkit.

323
00:19:48,580 --> 00:19:51,270
>> Agora na segunda-feira, tivemos um monte de gente veio aqui

324
00:19:51,270 --> 00:19:53,150
e representar a noção de uma lista ligada.

325
00:19:53,150 --> 00:20:00,970
E introduzimos a lista ligada como uma solução para o problema?

326
00:20:00,970 --> 00:20:04,590
Sim? [Responder Estudante, ininteligível] Boa.

327
00:20:04,590 --> 00:20:06,530
Matrizes não podem ter memória adicionados a eles.

328
00:20:06,530 --> 00:20:09,440
Se você alocar uma matriz de tamanho 10, que é tudo que você conseguir.

329
00:20:09,440 --> 00:20:13,690
Você pode chamar uma função como realloc se inicialmente chamada malloc,

330
00:20:13,690 --> 00:20:17,580
e que pode experimentar a crescer a matriz, se houver espaço para o fim de que

331
00:20:17,580 --> 00:20:21,610
que ninguém mais está usando e, se não há, ela só vai encontrar um pedaço maior em outro lugar.

332
00:20:21,610 --> 00:20:25,040
Mas então ele vai copiar todos os bytes para a nova matriz.

333
00:20:25,040 --> 00:20:28,310
Isso soa como uma solução muito correta.

334
00:20:28,310 --> 00:20:34,790
Por que isso é pouco atraente?

335
00:20:34,790 --> 00:20:36,940
Quero dizer que funciona, os seres humanos têm resolvido este problema.

336
00:20:36,940 --> 00:20:40,710
Por que temos que resolver isso na segunda-feira com listas ligadas? Sim?

337
00:20:40,710 --> 00:20:44,060
[Responder Estudante, ininteligível] Pode levar um longo tempo.

338
00:20:44,060 --> 00:20:49,260
Na verdade, a qualquer momento que você está chamando malloc calloc ou realloc ou, o que é ainda um outro,

339
00:20:49,260 --> 00:20:52,470
qualquer momento que você, o programa, está falando com o sistema operacional,

340
00:20:52,470 --> 00:20:54,310
você tende a tornar o programa lento.

341
00:20:54,310 --> 00:20:57,470
E se você está fazendo esses tipos de coisas em loops, você está realmente abrandar as coisas.

342
00:20:57,470 --> 00:21:00,740
Você não vai perceber isso por mais simples de "Hello World" programas do tipo,

343
00:21:00,740 --> 00:21:04,300
mas em programas muito maiores, pedindo que o sistema operacional novo e de novo para a memória

344
00:21:04,300 --> 00:21:07,520
ou dando-lhe de volta uma e outra vez tende a não ser uma coisa boa.

345
00:21:07,520 --> 00:21:11,210
Além disso, é apenas uma espécie de intelectual - é um completo desperdício de tempo.

346
00:21:11,210 --> 00:21:16,490
Por que alocar mais memória e mais risco, copiar tudo para a nova matriz,

347
00:21:16,490 --> 00:21:21,980
se você tem uma alternativa que permite alocar memória apenas o quanto você realmente precisa?

348
00:21:21,980 --> 00:21:24,130
Portanto, há prós e contras aqui.

349
00:21:24,130 --> 00:21:26,730
Uma das vantagens é que agora temos dinamismo.

350
00:21:26,730 --> 00:21:29,100
Não importa de onde os pedaços de memória são de que estão livres,

351
00:21:29,100 --> 00:21:32,070
Eu só posso classificar de criar estas migalhas de pão através de ponteiros

352
00:21:32,070 --> 00:21:34,470
amarrar minha lista inteira ligados.

353
00:21:34,470 --> 00:21:36,470
Mas eu pagar pelo menos um preço.

354
00:21:36,470 --> 00:21:40,060
>> O que eu tenho a dar-se na obtenção de listas ligadas?

355
00:21:40,060 --> 00:21:42,470
Sim? [Responder Estudante, ininteligível] Boa.

356
00:21:42,470 --> 00:21:45,650
Você precisa de mais memória. Agora eu preciso de espaço para estas indicações,

357
00:21:45,650 --> 00:21:47,900
e no caso de esta lista super simples ligado

358
00:21:47,900 --> 00:21:51,410
que está apenas a tentar armazenar números inteiros, que são 4 bytes, que continua dizendo

359
00:21:51,410 --> 00:21:54,240
bem, um ponteiro é de 4 bytes, então agora eu tenho literalmente dobrou

360
00:21:54,240 --> 00:21:57,290
a quantidade de memória que eu preciso apenas para armazenar esta lista.

361
00:21:57,290 --> 00:21:59,680
Mas, novamente, esta é uma troca constante em ciência da computação

362
00:21:59,680 --> 00:22:03,440
entre tempo e espaço e esforço de desenvolvimento, e outros recursos.

363
00:22:03,440 --> 00:22:06,630
O que é outra desvantagem de usar uma lista ligada? Sim?

364
00:22:06,630 --> 00:22:10,150
[Responder Estudante, ininteligível]

365
00:22:10,150 --> 00:22:12,600
Bom. Não é tão fácil de acessar. Nós não podemos mais alavancagem

366
00:22:12,600 --> 00:22:15,530
Semana 0 princípios como dividir e conquistar.

367
00:22:15,530 --> 00:22:18,220
E, mais especificamente, a pesquisa binária. Porque mesmo que nós, seres humanos

368
00:22:18,220 --> 00:22:20,400
pode ver mais ou menos onde a meio da lista é,

369
00:22:20,400 --> 00:22:25,840
o computador só sabe que esta lista ligada começa no endereço chamado primeiro.

370
00:22:25,840 --> 00:22:28,250
E isso é 0x123 ou algo parecido.

371
00:22:28,250 --> 00:22:30,990
E a única maneira que o programa pode encontrar o elemento do meio

372
00:22:30,990 --> 00:22:33,350
é realmente procurar a lista inteira.

373
00:22:33,350 --> 00:22:35,500
E mesmo assim, ele literalmente tem que pesquisar a lista inteira porque

374
00:22:35,500 --> 00:22:38,950
mesmo quando chegar o elemento do meio, seguindo os ponteiros,

375
00:22:38,950 --> 00:22:42,380
você, o programa, não tem idéia de quanto tempo essa lista é, potencialmente,

376
00:22:42,380 --> 00:22:45,250
até chegar ao final do mesmo, e como você sabe de programação

377
00:22:45,250 --> 00:22:48,600
que está no final de uma lista ligada?

378
00:22:48,600 --> 00:22:51,120
Há um ponteiro especial NULL, portanto, novamente, uma convenção.

379
00:22:51,120 --> 00:22:53,870
Em vez de usar esse ponteiro, nós definitivamente não queremos que seja algum valor lixo

380
00:22:53,870 --> 00:22:57,750
apontando para fora do palco em algum lugar, nós queremos que seja mão para baixo, NULL,

381
00:22:57,750 --> 00:23:01,530
de modo que temos este terminal nesta estrutura de dados para sabermos onde ela termina.

382
00:23:01,530 --> 00:23:03,410
>> O que se quer manipular isso?

383
00:23:03,410 --> 00:23:05,980
Fizemos a maior parte deste visualmente, e com os seres humanos,

384
00:23:05,980 --> 00:23:07,630
mas o que se quer fazer uma inserção?

385
00:23:07,630 --> 00:23:12,360
Assim, a lista original era de 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
E se nós então queria espaço malloc para o número 55, um nó para ele,

387
00:23:16,730 --> 00:23:20,730
e então nós queremos inserir 55 na lista, assim como fizemos na segunda-feira?

388
00:23:20,730 --> 00:23:23,690
Como podemos fazer isso? Bem, Anita veio e ela caminhou essencialmente da lista.

389
00:23:23,690 --> 00:23:27,500
Ela começou no primeiro elemento, então o próximo, o próximo, o outro, o próximo, o próximo.

390
00:23:27,500 --> 00:23:29,500
Finalmente atingiu a mão esquerda todo o caminho

391
00:23:29,500 --> 00:23:34,480
e percebi oh, isso é NULL. Então, o que a manipulação de ponteiros precisava ser feito?

392
00:23:34,480 --> 00:23:37,980
A pessoa que estava no fim, número 34, precisava de sua mão esquerda levantada

393
00:23:37,980 --> 00:23:46,220
para apontar para 55, 55 precisavam de seu braço esquerdo apontando para baixo para ser o novo terminador nulo. Concluído.

394
00:23:46,220 --> 00:23:49,540
Muito fácil de inserir em uma lista de 55 classificados.

395
00:23:49,540 --> 00:23:51,800
E como isso pode olhar?

396
00:23:51,800 --> 00:23:55,690
>> Deixe-me ir em frente e abrir algum exemplo de código aqui.

397
00:23:55,690 --> 00:23:58,120
Vou abrir o gedit, e deixe-me abrir dois arquivos primeiro.

398
00:23:58,120 --> 00:24:02,050
Um é list1.h, e deixe-me lembrar que este foi o pedaço de código

399
00:24:02,050 --> 00:24:04,920
que usamos para representar um nó.

400
00:24:04,920 --> 00:24:13,040
Um nó tem tanto um int chamado n e um ponteiro chamado em seguida que apenas pontos para a próxima coisa na lista.

401
00:24:13,040 --> 00:24:15,450
Que agora está em um arquivo h.. Por quê?

402
00:24:15,450 --> 00:24:19,090
Há essa convenção, e não temos aproveitado este uma enorme quantidade de nós mesmos,

403
00:24:19,090 --> 00:24:22,220
mas a pessoa que escreveu funções printf e outros

404
00:24:22,220 --> 00:24:27,150
deu como um presente para o mundo todas essas funções por escrever um arquivo chamado stdio.h.

405
00:24:27,150 --> 00:24:30,950
E depois há string.h, e então há map.h, e há todos esses arquivos h

406
00:24:30,950 --> 00:24:34,410
que você pode ter visto ou usado durante o prazo escritos por outras pessoas.

407
00:24:34,410 --> 00:24:38,470
Normalmente nos. Arquivos h são apenas coisas como typedefs

408
00:24:38,470 --> 00:24:42,310
ou declarações de tipos personalizados ou declarações de constantes.

409
00:24:42,310 --> 00:24:47,890
Você não colocar implementações funções 'em arquivos de cabeçalho.

410
00:24:47,890 --> 00:24:50,570
Você coloca, em vez disso, apenas os seus protótipos.

411
00:24:50,570 --> 00:24:53,050
Você coloca as coisas que você deseja compartilhar com o mundo o que eles precisam

412
00:24:53,050 --> 00:24:55,640
para compilar o seu código. Então, só para chegar a este hábito,

413
00:24:55,640 --> 00:24:59,110
decidimos fazer a mesma coisa. Não há muito em list1.h,

414
00:24:59,110 --> 00:25:02,070
mas nós colocamos algo que pode ser do interesse de pessoas no mundo

415
00:25:02,070 --> 00:25:05,030
que querem usar a nossa implementação lista encadeada.

416
00:25:05,030 --> 00:25:08,040
Agora, em list1.c, eu não vou passar por essa coisa toda

417
00:25:08,040 --> 00:25:11,390
porque é um pouco longo, este programa, mas vamos executá-lo real rapidamente no prompt.

418
00:25:11,390 --> 00:25:15,720
Deixe-me compilar list1, deixe-me em seguida, executar list1, eo que você vai ver é

419
00:25:15,720 --> 00:25:18,070
temos um programa de simulação simples pouco aqui

420
00:25:18,070 --> 00:25:20,990
que vai me permite adicionar e remover números a uma lista.

421
00:25:20,990 --> 00:25:24,310
Então deixe-me ir em frente e digite 3 para a 3 opção de menu.

422
00:25:24,310 --> 00:25:27,880
Quero inserir o número - vamos fazer o primeiro número, que foi de 9,

423
00:25:27,880 --> 00:25:30,550
e agora eu sou informado a lista é agora 9.

424
00:25:30,550 --> 00:25:33,760
Deixe-me ir em frente e fazer outra inserção, então eu bati opção de menu 3.

425
00:25:33,760 --> 00:25:36,760
Qual o número que eu quero inserir? 17.

426
00:25:36,760 --> 00:25:39,220
Enter. E eu vou fazer só mais um.

427
00:25:39,220 --> 00:25:41,720
Deixe-me inserir o número 22.

428
00:25:41,720 --> 00:25:45,850
Portanto, temos o início da lista encadeada que tínhamos em forma de slides um momento atrás.

429
00:25:45,850 --> 00:25:48,740
Como é que esta inserção realmente acontecendo?

430
00:25:48,740 --> 00:25:52,000
De facto, 22 é agora no fim da lista.

431
00:25:52,000 --> 00:25:55,050
Assim, a história que contou no palco na segunda-feira e só agora recapitulou

432
00:25:55,050 --> 00:25:57,460
deve realmente estar acontecendo no código.

433
00:25:57,460 --> 00:25:59,700
Vamos dar uma olhada. Deixe-me rolar neste arquivo.

434
00:25:59,700 --> 00:26:01,720
Nós vamos passar por cima algumas das funções,

435
00:26:01,720 --> 00:26:05,630
mas nós vamos descer para, digamos, a função de inserção.

436
00:26:05,630 --> 00:26:11,720
>> Vamos ver como nós vamos sobre a inserção de um novo nó para esta lista ligada.

437
00:26:11,720 --> 00:26:14,550
Onde está a lista declarada? Bem, vamos percorrer todo o caminho até ao topo,

438
00:26:14,550 --> 00:26:19,970
e perceber que a minha lista ligada essencialmente declarado como um ponteiro único que é inicialmente NULL.

439
00:26:19,970 --> 00:26:23,180
Então, eu estou usando uma variável global aqui, que em geral temos pregado contra

440
00:26:23,180 --> 00:26:25,280
porque faz com que o seu código um pouco confuso para manter,

441
00:26:25,280 --> 00:26:29,080
é uma espécie de preguiça, normalmente, mas não é preguiçoso e não é errado e não é ruim

442
00:26:29,080 --> 00:26:33,660
se o propósito único de seu programa na vida é para simular uma lista ligada.

443
00:26:33,660 --> 00:26:35,460
Que é exatamente o que estamos fazendo.

444
00:26:35,460 --> 00:26:39,100
Então ao invés de declarar isso em principal e depois ter de passá-lo para cada função

445
00:26:39,100 --> 00:26:42,640
temos escrito neste programa, em vez perceber oh, vamos torná-lo global

446
00:26:42,640 --> 00:26:47,060
porque todo o propósito deste programa é demonstrar uma e apenas uma lista ligada.

447
00:26:47,060 --> 00:26:50,700
Então, que se sente bem. Aqui estão os meus protótipos, e não vamos passar por tudo isso,

448
00:26:50,700 --> 00:26:55,800
mas eu escrevi uma função de exclusão, uma função de encontrar, uma função de inserção, e uma função de travessia.

449
00:26:55,800 --> 00:26:59,080
Mas vamos agora voltar-se para a função de inserção

450
00:26:59,080 --> 00:27:01,490
e ver como este funciona aqui.

451
00:27:01,490 --> 00:27:09,940
Inserção é on line - aqui vamos nós.

452
00:27:09,940 --> 00:27:12,850
Inserir. Então, não é preciso nenhum argumento, porque nós vamos pedir

453
00:27:12,850 --> 00:27:15,930
o interior usuário desta função para o número que deseja inserir.

454
00:27:15,930 --> 00:27:19,410
Mas, primeiro, nos preparamos para dar-lhes um pouco de espaço.

455
00:27:19,410 --> 00:27:22,050
Esta é uma espécie de copiar e colar do outro exemplo.

456
00:27:22,050 --> 00:27:25,110
Nesse caso, fomos atribuição de um int, desta vez estamos alocando um nó.

457
00:27:25,110 --> 00:27:27,910
Eu realmente não me lembro quantos bytes um nó é, mas isso é bom.

458
00:27:27,910 --> 00:27:30,460
Sizeof pode descobrir isso para mim.

459
00:27:30,460 --> 00:27:33,340
E por que estou verificando NULL na linha 120?

460
00:27:33,340 --> 00:27:37,530
O que poderia dar errado na linha 119? Sim?

461
00:27:37,530 --> 00:27:40,530
[Responder Estudante, ininteligível]

462
00:27:40,530 --> 00:27:43,440
Bom. Só poderia ser o caso que eu pedi muita memória

463
00:27:43,440 --> 00:27:47,020
ou algo está errado eo sistema operacional não tem bytes suficiente para me dar,

464
00:27:47,020 --> 00:27:50,640
por isso sinaliza tanto por retornar nulo, e se eu não verificar que

465
00:27:50,640 --> 00:27:54,710
e eu apenas cega continuar a usar o endereço retornado, pode ser NULL.

466
00:27:54,710 --> 00:27:58,400
Poderia ser algum valor desconhecido, não é uma boa coisa a menos que eu -

467
00:27:58,400 --> 00:28:00,590
na verdade, não será um valor desconhecido. Pode ser NULL, então eu não quero

468
00:28:00,590 --> 00:28:02,550
a abusar dela e arriscar dereferencing-lo.

469
00:28:02,550 --> 00:28:07,410
Se isso acontecer, eu só voltar e vamos fingir que eu não voltar qualquer memória de todos.

470
00:28:07,410 --> 00:28:12,270
>> Caso contrário, eu digo o usuário me dar um número para inserir, eu chamo a nossa GetInt velho amigo,

471
00:28:12,270 --> 00:28:15,530
e então esta foi a nova sintaxe que introduziu na segunda-feira.

472
00:28:15,530 --> 00:28:20,320
'Newptr-> n' significa ter o endereço que lhe foi fornecido por malloc

473
00:28:20,320 --> 00:28:23,490
que representa o primeiro byte de um objecto novo nó,

474
00:28:23,490 --> 00:28:26,860
e depois ir para o campo chamado n.

475
00:28:26,860 --> 00:28:35,270
Uma questão pouco trivial: Este é equivalente ao que linha mais enigmática do código?

476
00:28:35,270 --> 00:28:38,110
Como poderia eu ter escrito isso? Quer dar uma facada?

477
00:28:38,110 --> 00:28:41,480
[Responder Estudante, ininteligível]

478
00:28:41,480 --> 00:28:44,870
Bom. Usando o n., Mas não é tão simples como isso.

479
00:28:44,870 --> 00:28:47,090
O que eu primeiro preciso fazer? [Responder Estudante, ininteligível]

480
00:28:47,090 --> 00:28:52,730
Bom. Eu preciso fazer newptr.n *.

481
00:28:52,730 --> 00:28:55,610
Portanto, este novo ponteiro está dizendo é, obviamente, um endereço. Por quê?

482
00:28:55,610 --> 00:28:59,520
Porque ele foi devolvido por malloc. O newptr * dizendo "vá lá",

483
00:28:59,520 --> 00:29:02,970
e, em seguida, uma vez que você estiver lá, então você pode usar o mais familiar. n,

484
00:29:02,970 --> 00:29:05,730
mas isso só parece um pouco feio, especialmente se nós, seres humanos vão

485
00:29:05,730 --> 00:29:10,360
desenhar os ponteiros com as setas todo o tempo, o mundo tem padronizado nesta notação de seta,

486
00:29:10,360 --> 00:29:12,320
que faz exatamente a mesma coisa.

487
00:29:12,320 --> 00:29:16,070
Assim, você só usar o - notação> quando a coisa da esquerda é um ponteiro.

488
00:29:16,070 --> 00:29:18,790
Caso contrário, se é uma estrutura real, use o n..

489
00:29:18,790 --> 00:29:25,800
E depois este: Por que eu inicializar newptr-> ao lado nulo?

490
00:29:25,800 --> 00:29:28,610
Nós não queremos uma mão pendurada esquerda fora da final da etapa.

491
00:29:28,610 --> 00:29:31,630
Queremos que ele apontando diretamente para baixo, o que significa o fim desta lista

492
00:29:31,630 --> 00:29:34,980
poderia ser neste nó, então é melhor ter certeza que é NULL.

493
00:29:34,980 --> 00:29:38,460
E, em geral, inicializar suas variáveis ​​ou membros de dados e estruturas

494
00:29:38,460 --> 00:29:40,470
a algo é apenas uma boa prática.

495
00:29:40,470 --> 00:29:45,170
Apenas deixar lixo existem e continuarão a existir, geralmente você fica em apuros

496
00:29:45,170 --> 00:29:48,650
se você se esquecer de fazer alguma coisa mais tarde.

497
00:29:48,650 --> 00:29:51,590
>> Aqui está alguns casos. Isso, novamente, é a função de inserção,

498
00:29:51,590 --> 00:29:54,930
ea primeira coisa que eu verificar é se a variável chamada primeiro,

499
00:29:54,930 --> 00:29:58,240
essa variável global é NULL, que significa que não há lista ligada.

500
00:29:58,240 --> 00:30:02,460
Nós não inseriu nenhum número, por isso é trivial para inserir este número atual

501
00:30:02,460 --> 00:30:05,240
na lista, porque apenas pertence no início da lista.

502
00:30:05,240 --> 00:30:08,100
Então, isso foi quando Anita estava em pé aqui sozinho, fingindo

503
00:30:08,100 --> 00:30:11,390
não havia mais ninguém aqui no palco até alocamos um nó,

504
00:30:11,390 --> 00:30:13,940
então ela poderia levantar a mão pela primeira vez,

505
00:30:13,940 --> 00:30:17,420
se todo mundo tivesse vindo no palco depois de sua segunda-feira.

506
00:30:17,420 --> 00:30:22,900
Agora, aqui, este é um cheque pequeno onde eu tenho que dizer se o valor do novo nó de n

507
00:30:22,900 --> 00:30:27,370
é <o valor de n no nó atual primeiro,

508
00:30:27,370 --> 00:30:29,930
isso significa que há uma lista encadeada que começou.

509
00:30:29,930 --> 00:30:32,330
Há pelo menos um nó na lista, mas esse cara nova

510
00:30:32,330 --> 00:30:37,230
pertence, antes disso, por isso temos de mudar as coisas ao redor.

511
00:30:37,230 --> 00:30:43,450
Em outras palavras, se a lista começou com apenas, vamos dizer,

512
00:30:43,450 --> 00:30:48,100
apenas o número 17, que é a - na verdade, o que podemos fazer isso mais claramente.

513
00:30:48,100 --> 00:30:56,010
Se começarmos a nossa história com um ponteiro aqui chamado em primeiro lugar,

514
00:30:56,010 --> 00:30:59,870
e, inicialmente, é nulo, e inserir o número 9,

515
00:30:59,870 --> 00:31:02,510
o número 9 pertence claramente no início da lista.

516
00:31:02,510 --> 00:31:07,400
Então vamos fingir que apenas malloced o endereço ou o número 9 e colocá-lo aqui.

517
00:31:07,400 --> 00:31:13,170
Se o primeiro é de 9 por padrão, o primeiro cenário discutimos apenas significa ponto vamos esse cara aqui,

518
00:31:13,170 --> 00:31:15,790
deixar isso como NULL, agora temos o número 9.

519
00:31:15,790 --> 00:31:18,280
O próximo número que deseja inserir é 17.

520
00:31:18,280 --> 00:31:22,420
17 pertence aqui, então nós vamos ter que fazer alguma revisão lógica por isso.

521
00:31:22,420 --> 00:31:26,060
Então, vamos em vez disso, antes de fazer isso, vamos fingir que queria inserir o número 8.

522
00:31:26,060 --> 00:31:28,650
>> Então, só por conveniência, eu vou desenhar aqui.

523
00:31:28,650 --> 00:31:30,760
Mas lembre-se, malloc pode colocá-lo em qualquer lugar.

524
00:31:30,760 --> 00:31:33,460
Mas, pelo amor de desenho, vou colocá-lo aqui.

525
00:31:33,460 --> 00:31:38,440
Então, fingir que acabou atribuído um nó para o número 8, que é NULL por padrão.

526
00:31:38,440 --> 00:31:42,800
O que tem que acontecer agora? Um par de coisas.

527
00:31:42,800 --> 00:31:47,090
Fizemos esse erro no palco na segunda-feira, onde atualizamos um ponteiro como este,

528
00:31:47,090 --> 00:31:51,890
em seguida, fez isso, e então alegou - nós órfãos todos os outros no palco.

529
00:31:51,890 --> 00:31:54,350
Porque você não pode - a ordem das operações aqui é importante,

530
00:31:54,350 --> 00:31:58,760
porque agora nós perdemos esta 9 nó que é exatamente o tipo de flutuar no espaço.

531
00:31:58,760 --> 00:32:01,150
Portanto, este não era o caminho certo na segunda-feira.

532
00:32:01,150 --> 00:32:03,330
Primeiro temos de fazer outra coisa.

533
00:32:03,330 --> 00:32:06,280
O estado do mundo é assim. Inicialmente, 8 foi alocado.

534
00:32:06,280 --> 00:32:10,550
Qual seria a melhor maneira de inserir 8?

535
00:32:10,550 --> 00:32:14,720
Em vez de atualizar este primeiro ponteiro, apenas atualizar este aqui em seu lugar.

536
00:32:14,720 --> 00:32:17,720
Então, precisamos de uma linha de código que vai virar personagem NULL

537
00:32:17,720 --> 00:32:22,020
em um ponteiro real que está apontando para o nó 9,

538
00:32:22,020 --> 00:32:27,970
e então podemos seguramente mudar primeiro a apontar para esse cara aqui.

539
00:32:27,970 --> 00:32:31,330
Agora temos uma lista, uma lista ligada, de dois elementos.

540
00:32:31,330 --> 00:32:33,580
E o que isso realmente parecido com aqui?

541
00:32:33,580 --> 00:32:36,900
Se olharmos para o código, observe que eu fiz exatamente isso.

542
00:32:36,900 --> 00:32:41,970
Eu já disse newptr, e nesta história, newptr estava apontando para esse cara.

543
00:32:41,970 --> 00:32:45,520
>> Então deixe-me tirar mais uma coisa, e eu deveria ter deixado quarto um pouco mais por isso.

544
00:32:45,520 --> 00:32:48,540
Então, perdoe o desenho pequeno.

545
00:32:48,540 --> 00:32:52,140
Esse cara é chamado newptr.

546
00:32:52,140 --> 00:32:57,940
Essa é a variável que declarou algumas linhas antes, em linha - só acima de 25.

547
00:32:57,940 --> 00:33:03,430
E está apontando para 8. Portanto, quando digo newptr-> seguinte, o que significa ir para a estrutura

548
00:33:03,430 --> 00:33:07,910
que está sendo apontado por newptr, então aqui estamos nós, vá lá.

549
00:33:07,910 --> 00:33:13,990
Em seguida, a seta está dizendo obter o próximo campo, e então a = está dizendo colocar o valor lá?

550
00:33:13,990 --> 00:33:17,280
O valor que estava em primeiro, qual o valor que estava em primeiro lugar?

551
00:33:17,280 --> 00:33:21,930
Primeiro foi apontando para esse nó, o que significa que este deve agora apontar para este nó.

552
00:33:21,930 --> 00:33:25,660
Em outras palavras, o que parece ainda uma bagunça ridículo com a minha letra,

553
00:33:25,660 --> 00:33:28,620
o que é uma idéia simples de apenas mover essas setas ao redor

554
00:33:28,620 --> 00:33:31,560
traduz em código com apenas forro este.

555
00:33:31,560 --> 00:33:38,110
Armazenar o que está em primeiro no campo ao lado e então atualizar o primeiro realmente é.

556
00:33:38,110 --> 00:33:40,900
Vamos em frente e avançar rapidamente um pouco disso,

557
00:33:40,900 --> 00:33:44,220
e olhar apenas para essa inserção da cauda para agora.

558
00:33:44,220 --> 00:33:51,210
Suponha que eu chegar ao ponto em que eu achar que o próximo campo de algum nó é NULL.

559
00:33:51,210 --> 00:33:53,410
E neste ponto da história, um detalhe que eu estou passando por cima

560
00:33:53,410 --> 00:33:58,170
é que eu introduzi outro ponteiro-se aqui na linha 142, ponteiro antecessor.

561
00:33:58,170 --> 00:34:01,320
Essencialmente, neste ponto da história, uma vez que a lista é longa,

562
00:34:01,320 --> 00:34:04,800
Eu meio que preciso andar com dois dedos, porque se eu for muito longe,

563
00:34:04,800 --> 00:34:08,219
lembre-se em uma única lista de comprimento, você não pode ir para trás.

564
00:34:08,219 --> 00:34:13,659
Então essa idéia de predptr é o meu dedo para a esquerda, e newptr - não newptr.

565
00:34:13,659 --> 00:34:17,199
Outro indicador que está aqui é o meu outro dedo, e eu sou apenas um tipo de andar a lista.

566
00:34:17,199 --> 00:34:22,179
É por isso que existe. Mas vamos considerar apenas um dos casos mais simples aqui.

567
00:34:22,179 --> 00:34:26,620
Se o campo seguinte que ponteiro é NULL, o que é a implicação lógica?

568
00:34:26,620 --> 00:34:30,840
Se você está atravessando esta lista e você bater um ponteiro NULL?

569
00:34:30,840 --> 00:34:35,780
Você está no fim da lista, e assim o código para então acrescentar este elemento adicional

570
00:34:35,780 --> 00:34:41,230
é uma espécie de intuitiva terá que nó cuja próxima ponteiro é NULL,

571
00:34:41,230 --> 00:34:46,120
por isso este é atualmente NULL, e alterá-lo, embora, para ser o endereço do novo nó.

572
00:34:46,120 --> 00:34:52,260
Então, estamos apenas desenhando no código da seta que traçamos no palco, levantando a mão esquerda de alguém.

573
00:34:52,260 --> 00:34:54,070
>> E o caso que eu vou acenar as mãos menos por enquanto,

574
00:34:54,070 --> 00:34:58,020
só porque eu acho que é fácil se perder quando o fazemos neste tipo de ambiente,

575
00:34:58,020 --> 00:35:00,600
é a verificação de inserção no meio da lista.

576
00:35:00,600 --> 00:35:03,220
Mas apenas de forma intuitiva, o que deve acontecer se você quiser descobrir

577
00:35:03,220 --> 00:35:06,600
onde um número pertence no meio é que você tem que caminhar

578
00:35:06,600 --> 00:35:09,510
com mais de um dedo, mais de um ponteiro,

579
00:35:09,510 --> 00:35:12,920
descobrir onde ele pertence, a verificação é o elemento <o atual,

580
00:35:12,920 --> 00:35:15,450
> O atual, e uma vez que você encontrar esse lugar,

581
00:35:15,450 --> 00:35:20,400
então você tem que fazer esse tipo de jogo de conchas onde você move os ponteiros em torno de muito cuidado.

582
00:35:20,400 --> 00:35:23,850
E essa resposta, se você gostaria de razão por este em casa no seu próprio país,

583
00:35:23,850 --> 00:35:28,340
se resume apenas a essas duas linhas de código, mas a ordem das linhas é super importante.

584
00:35:28,340 --> 00:35:31,390
Porque se você soltar a mão de alguém e levantar outra pessoa na ordem errada,

585
00:35:31,390 --> 00:35:34,580
novamente, você pode acabar orfandade da lista.

586
00:35:34,580 --> 00:35:39,500
Para resumir mais conceitualmente, a inserção na cauda é relativamente simples.

587
00:35:39,500 --> 00:35:42,940
A inserção na cabeça também é relativamente simples,

588
00:35:42,940 --> 00:35:45,580
mas você precisa atualizar um ponteiro adicional neste momento

589
00:35:45,580 --> 00:35:47,930
para espremer o número 5 na lista aqui,

590
00:35:47,930 --> 00:35:51,560
e, em seguida, a inserção no meio envolve um esforço ainda maior,

591
00:35:51,560 --> 00:35:56,130
para inserir cuidadosamente o número 20 na sua posição correcta,

592
00:35:56,130 --> 00:35:58,350
que é entre 17 e 22.

593
00:35:58,350 --> 00:36:02,700
Então, você precisa fazer algo como ter o novo nó de ponto de 20 a 22,

594
00:36:02,700 --> 00:36:08,470
e, em seguida, o ponteiro que nó precisa ser atualizado passado?

595
00:36:08,470 --> 00:36:10,630
É 17, de realmente inseri-lo.

596
00:36:10,630 --> 00:36:14,080
Então, novamente, eu vou adiar o código real para que a implementação particular.

597
00:36:14,080 --> 00:36:17,280
>> À primeira vista, é um pouco assustador, mas é realmente apenas um ciclo infinito

598
00:36:17,280 --> 00:36:21,770
que é looping, looping, looping, looping, e quebrando assim que bateu o ponteiro NULL,

599
00:36:21,770 --> 00:36:24,590
em que ponto você pode fazer a inserção necessária.

600
00:36:24,590 --> 00:36:30,960
Este, então, é o código de inserção representante lista ligada.

601
00:36:30,960 --> 00:36:34,590
Que era uma espécie de um lote, e parece que nós resolvemos um problema,

602
00:36:34,590 --> 00:36:36,940
mas nós introduzimos um totalmente diferente. Francamente, nós passamos todo esse tempo

603
00:36:36,940 --> 00:36:40,540
em grande O e Ω e correndo o tempo, tentando resolver problemas mais rapidamente,

604
00:36:40,540 --> 00:36:43,270
e aqui estamos dando um grande passo para trás, ele se sente.

605
00:36:43,270 --> 00:36:45,380
E, no entanto, se o objetivo é armazenar dados,

606
00:36:45,380 --> 00:36:48,010
parece que o Santo Graal, como dissemos na segunda-feira, seria realmente

607
00:36:48,010 --> 00:36:50,470
para guardar coisas instantaneamente.

608
00:36:50,470 --> 00:36:53,930
>> Na verdade, acho que fizemos colocar lista de lado ligado por um momento

609
00:36:53,930 --> 00:36:56,000
e nós, em vez introduziu a noção de uma mesa.

610
00:36:56,000 --> 00:36:59,110
E vamos pensar em uma mesa por um momento como uma matriz.

611
00:36:59,110 --> 00:37:03,790
Esta matriz e neste caso aqui tem cerca de 26 elementos, de 0 a 25,

612
00:37:03,790 --> 00:37:07,940
e suponha que você precisava de algum pedaço de armazenamento de nomes:

613
00:37:07,940 --> 00:37:10,350
Alice e Bob e Charlie e similares.

614
00:37:10,350 --> 00:37:12,880
E você precisa de alguma estrutura de dados para armazenar esses nomes.

615
00:37:12,880 --> 00:37:15,000
Bem, você poderia usar algo como uma lista ligada

616
00:37:15,000 --> 00:37:20,260
e você pode percorrer a lista de inserir Alice antes de Bob e Charlie depois de Bob e assim por diante.

617
00:37:20,260 --> 00:37:23,850
E, de fato, se você quiser ver o código assim como um aparte,

618
00:37:23,850 --> 00:37:27,230
sei que em list2.h, fazemos exatamente isso.

619
00:37:27,230 --> 00:37:30,610
Nós não vai passar por esse código, mas esta é uma variante do primeiro exemplo

620
00:37:30,610 --> 00:37:34,640
que introduz uma outra struct que já vimos antes estudante chamado,

621
00:37:34,640 --> 00:37:40,330
e então o que realmente armazena na lista vinculada é um ponteiro para uma estrutura de estudante

622
00:37:40,330 --> 00:37:44,520
em vez de inteiro um pouco simples, n.

623
00:37:44,520 --> 00:37:46,900
Então, percebo que há código lá que envolve cordas reais,

624
00:37:46,900 --> 00:37:49,940
Mas se o objetivo em mãos realmente agora é resolver o problema da eficiência,

625
00:37:49,940 --> 00:37:53,380
Não seria bom se nós estamos dando um objeto chamado Alice,

626
00:37:53,380 --> 00:37:56,020
queremos colocá-la no local certo, em uma estrutura de dados,

627
00:37:56,020 --> 00:37:58,860
parece que seria muito bom para apenas colocar Alice,

628
00:37:58,860 --> 00:38:01,180
cujo nome começa com A, no primeiro local.

629
00:38:01,180 --> 00:38:05,270
E Bob, cujo nome começa com B, na segunda posição.

630
00:38:05,270 --> 00:38:09,580
Com uma matriz, ou vamos começar chamando-o de uma tabela, uma tabela hash em que,

631
00:38:09,580 --> 00:38:13,650
nós podemos fazer exatamente isso. Se nos é dado um nome como Alice,

632
00:38:13,650 --> 00:38:16,700
uma seqüência como Alice, onde você põe A-l-i-c-e?

633
00:38:16,700 --> 00:38:20,540
Precisamos de um hueristic. Precisamos de uma função para tirar alguma entrada como Alice

634
00:38:20,540 --> 00:38:24,610
e retornar uma resposta, "Alice Coloque neste local."

635
00:38:24,610 --> 00:38:28,720
E esta função, esta caixa preta, vai ser chamado de função hash.

636
00:38:28,720 --> 00:38:32,330
>> Uma função hash é algo que tem uma entrada, como "Alice",

637
00:38:32,330 --> 00:38:38,080
e volta para você, normalmente, a localização numérica em alguma estrutura de dados onde Alice pertence.

638
00:38:38,080 --> 00:38:40,830
Neste caso, a função hash deve ser relativamente simples.

639
00:38:40,830 --> 00:38:47,510
Nossa função hash deve dizer, se você está dado "Alice", que a personagem deveria me importar com?

640
00:38:47,510 --> 00:38:55,660
O primeiro. Então eu olho para [0], e então eu digo se [0] o caráter é A, retornar o número 0.

641
00:38:55,660 --> 00:39:01,130
Se for B, retornar 1. Se é C, o retorno 2, e assim por diante.

642
00:39:01,130 --> 00:39:05,940
Todos índice 0, e que me permita inserir Alice e Bob e Charlie e assim por diante

643
00:39:05,940 --> 00:39:10,960
para essa estrutura de dados. Mas há um problema.

644
00:39:10,960 --> 00:39:13,060
O que se Anita vem de novo?

645
00:39:13,060 --> 00:39:17,510
Onde colocamos Anita? Seu nome também começa com a letra A,

646
00:39:17,510 --> 00:39:20,330
e parece que fizemos uma confusão ainda maior do problema.

647
00:39:20,330 --> 00:39:24,380
Nós temos agora a inserção imediata, inserção constante de tempo, para uma estrutura de dados

648
00:39:24,380 --> 00:39:27,100
em vez de pior caso linear,

649
00:39:27,100 --> 00:39:29,510
mas o que podemos fazer com Anita neste caso?

650
00:39:29,510 --> 00:39:34,110
Quais são as duas opções, realmente? Sim?

651
00:39:34,110 --> 00:39:37,410
[Responder Estudante, ininteligível] Ok, então nós poderíamos ter outra dimensão.

652
00:39:37,410 --> 00:39:42,320
Isso é bom. Assim, podemos construir coisas em 3D como falamos verbalmente na segunda-feira.

653
00:39:42,320 --> 00:39:46,700
Poderíamos acrescentar um outro acesso aqui, mas acho que não, eu estou tentando manter isso simples.

654
00:39:46,700 --> 00:39:50,160
O objetivo geral aqui é ter acesso constante de tempo imediato,

655
00:39:50,160 --> 00:39:52,170
de modo que é a adição de muita complexidade.

656
00:39:52,170 --> 00:39:55,970
Quais são as outras opções ao tentar inserir Anita para esta estrutura de dados? Sim?

657
00:39:55,970 --> 00:39:58,610
[Responder Estudante, ininteligível] Boa. Então, nós poderíamos passar todo mundo para baixo,

658
00:39:58,610 --> 00:40:03,040
como Charlie cutuca baixo Bob e Alice, e então colocamos Anita onde ela realmente quer ser.

659
00:40:03,040 --> 00:40:05,660
>> É claro que, agora, há um efeito colateral dessa.

660
00:40:05,660 --> 00:40:09,000
Esta estrutura de dados é provavelmente útil não porque queremos inserir as pessoas uma vez

661
00:40:09,000 --> 00:40:11,250
mas porque queremos verificar se eles estão lá mais tarde

662
00:40:11,250 --> 00:40:13,600
se queremos imprimir todos os nomes na estrutura de dados.

663
00:40:13,600 --> 00:40:15,850
Nós vamos fazer alguma coisa com esses dados, eventualmente.

664
00:40:15,850 --> 00:40:20,810
Então agora nós meio que parafusado sobre Alice, que não é mais onde ela deveria estar.

665
00:40:20,810 --> 00:40:23,880
Nem é Bob, nem é Charlie.

666
00:40:23,880 --> 00:40:26,060
Então talvez isso não é uma boa idéia.

667
00:40:26,060 --> 00:40:28,830
Mas, na verdade, esta é uma opção. Nós poderíamos mudar todos para baixo,

668
00:40:28,830 --> 00:40:32,240
ou diabos, Anita chegou atrasado para o jogo, por que não vamos apenas colocar Anita

669
00:40:32,240 --> 00:40:35,870
aqui não, aqui não, aqui não, vamos colocá-la um pouco mais abaixo na lista.

670
00:40:35,870 --> 00:40:38,680
Mas, então, este problema começa a devolver novamente.

671
00:40:38,680 --> 00:40:41,630
Você pode ser capaz de encontrar Alice instantaneamente, com base em seu primeiro nome.

672
00:40:41,630 --> 00:40:44,320
E Bob instantaneamente, e Charlie. Mas então você olha para Anita,

673
00:40:44,320 --> 00:40:46,360
e você vê, hein, Alice está no caminho.

674
00:40:46,360 --> 00:40:48,770
Bem, deixe-me ver abaixo Alice. Bob não é Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie não é Anita. Oh, há Anita.

676
00:40:51,850 --> 00:40:54,720
E se você continuar nesse trem da lógica toda a maneira,

677
00:40:54,720 --> 00:41:00,690
o que é o tempo de execução do pior caso de encontrar ou inserção de Anita para esta nova estrutura de dados?

678
00:41:00,690 --> 00:41:03,280
É O (n), certo?

679
00:41:03,280 --> 00:41:06,280
Porque, na pior das hipóteses, há Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
todo o caminho para alguém chamado "Y", por isso há apenas um ponto à esquerda.

681
00:41:10,150 --> 00:41:13,950
Felizmente, não temos um chamado de "Z", então colocamos Anita na parte inferior.

682
00:41:13,950 --> 00:41:16,040
>> Nós realmente não resolveu o problema.

683
00:41:16,040 --> 00:41:19,890
Então talvez nós precisamos introduzir esta terceira dimensão.

684
00:41:19,890 --> 00:41:22,230
E não é que, se nós não introduzir esta terceira dimensão,

685
00:41:22,230 --> 00:41:25,240
nós não podemos fazer isso perfeitamente, mas o Santo Graal vai estar recebendo

686
00:41:25,240 --> 00:41:28,370
constante de tempo de inserção e dinâmicos de modo a que as inserções

687
00:41:28,370 --> 00:41:30,960
não temos a hard-código uma matriz de tamanho 26.

688
00:41:30,960 --> 00:41:34,400
Podemos inserir tantos nomes como queremos, mas vamos dar o nosso intervalo de 5 minutos aqui

689
00:41:34,400 --> 00:41:38,790
e depois fazer isso corretamente.

690
00:41:38,790 --> 00:41:46,020
Tudo bem. Eu defini a história até muito artificialmente há

691
00:41:46,020 --> 00:41:48,670
escolhendo Alice e Bob e Charlie e Anita,

692
00:41:48,670 --> 00:41:51,000
cujo nome foi, obviamente, vai colidir com Alice.

693
00:41:51,000 --> 00:41:54,120
Mas a pergunta que terminou na segunda-feira com é apenas quão provável é

694
00:41:54,120 --> 00:41:56,370
que você deseja obter esses tipos de colisões? Em outras palavras,

695
00:41:56,370 --> 00:42:00,490
se começarmos a usar essa estrutura de tabela, que é realmente apenas uma matriz,

696
00:42:00,490 --> 00:42:02,460
neste caso, de 26 posições,

697
00:42:02,460 --> 00:42:05,740
E se nossos insumos são distribuídos uniformemente em vez?

698
00:42:05,740 --> 00:42:09,620
Não é artificialmente Alice e Bob e Charlie e David e assim por diante em ordem alfabética,

699
00:42:09,620 --> 00:42:12,380
é uniformemente distribuída ao longo de A a Z.

700
00:42:12,380 --> 00:42:15,220
>> Talvez nós vamos ter sorte e nós não vamos ter dois Um ou dois de B

701
00:42:15,220 --> 00:42:17,640
com probabilidade muito alta, mas como alguém apontou,

702
00:42:17,640 --> 00:42:20,730
se este problema generalizado e não 0-25

703
00:42:20,730 --> 00:42:26,060
mas, digamos, de 0 a 364 ou 65, muitas vezes, o número de dias em um ano típico,

704
00:42:26,060 --> 00:42:31,170
e fez a pergunta: "Qual é a probabilidade de que dois de nós nesta sala tem a mesma data de aniversário?"

705
00:42:31,170 --> 00:42:34,600
Dito de outra forma, qual é a probabilidade de que dois de nós tem um nome que começa com A?

706
00:42:34,600 --> 00:42:37,190
O tipo de pergunta é a mesma, mas este espaço de endereços,

707
00:42:37,190 --> 00:42:39,940
este espaço de busca, é maior no caso de aniversários,

708
00:42:39,940 --> 00:42:42,820
porque temos tantos dias a mais no ano do que letras no alfabeto.

709
00:42:42,820 --> 00:42:44,910
Qual é a probabilidade de uma colisão?

710
00:42:44,910 --> 00:42:48,410
Bem, podemos pensar nisso por descobrir a matemática de forma oposta.

711
00:42:48,410 --> 00:42:50,580
Qual é a probabilidade de colisões não?

712
00:42:50,580 --> 00:42:53,970
Bem, essa expressão aqui diz que o que é a probabilidade

713
00:42:53,970 --> 00:42:58,770
se há apenas uma pessoa neste quarto, que tem um aniversário?

714
00:42:58,770 --> 00:43:01,190
É 100%. Porque se há apenas uma pessoa na sala,

715
00:43:01,190 --> 00:43:03,940
seu aniversário pode ser qualquer um dos 365 dias fora do ano.

716
00:43:03,940 --> 00:43:08,650
Logo, as opções 365/365 me dá um valor de 1.

717
00:43:08,650 --> 00:43:11,250
Assim, a probabilidade em questão no momento é apenas 1.

718
00:43:11,250 --> 00:43:13,270
Mas se há uma segunda pessoa no quarto,

719
00:43:13,270 --> 00:43:16,490
qual é a probabilidade de que seu aniversário é diferente?

720
00:43:16,490 --> 00:43:20,680
Há apenas 364 dias possíveis, anos bissextos, ignorando

721
00:43:20,680 --> 00:43:23,580
para seu aniversário para não colidir com as outras pessoas.

722
00:43:23,580 --> 00:43:31,920
Assim, 364/365. Se uma terceira pessoa entra, é 363/365, e assim por diante.

723
00:43:31,920 --> 00:43:35,790
Assim, continuam se multiplicando junto destas frações, que estão ficando cada vez menores,

724
00:43:35,790 --> 00:43:40,720
para descobrir qual é a probabilidade de que todos nós temos aniversários originais?

725
00:43:40,720 --> 00:43:43,570
Mas, então, nós podemos, é claro, basta ter essa resposta e lançá-lo em torno de

726
00:43:43,570 --> 00:43:47,210
e fazer 1 menos de tudo isso, uma expressão que vai finalmente chegar

727
00:43:47,210 --> 00:43:51,250
se você se lembra a parte de trás de seus livros de matemática, que parece um pouco algo como isto,

728
00:43:51,250 --> 00:43:54,590
que é muito mais facilmente interpretada graficamente.

729
00:43:54,590 --> 00:43:57,820
E este gráfico aqui tem no eixo x o número de aniversários,

730
00:43:57,820 --> 00:44:02,030
ou o número de pessoas com aniversários, e no eixo y é a probabilidade de uma partida.

731
00:44:02,030 --> 00:44:06,060
E o que isso está dizendo é que se você tem, digamos, até mesmo,

732
00:44:06,060 --> 00:44:10,860
vamos escolher algo como 22, 23.

733
00:44:10,860 --> 00:44:13,160
Se há 22 ou 23 pessoas na sala,

734
00:44:13,160 --> 00:44:17,100
a probabilidade de que duas dessas poucas pessoas vão ter o mesmo aniversário

735
00:44:17,100 --> 00:44:19,560
é realmente super alta, combinatoriamente.

736
00:44:19,560 --> 00:44:23,450
50% as probabilidades de que em uma classe de apenas 22 pessoas, de um seminário, praticamente,

737
00:44:23,450 --> 00:44:25,790
2 de essas pessoas vão ter o mesmo aniversário.

738
00:44:25,790 --> 00:44:28,520
Porque há muitas maneiras em que você pode ter o mesmo aniversário.

739
00:44:28,520 --> 00:44:31,110
Pior ainda, se você olhar para o lado direito do gráfico,

740
00:44:31,110 --> 00:44:34,040
no momento em que você tem uma classe com 58 alunos em que,

741
00:44:34,040 --> 00:44:39,270
a probabilidade de duas pessoas que tenham um aniversário é alta, super super, cerca de 100%.

742
00:44:39,270 --> 00:44:41,880
Agora, isso é uma espécie de fato divertido sobre a vida real.

743
00:44:41,880 --> 00:44:45,850
>> Mas as implicações, agora, para estruturas de dados e armazenamento de informações

744
00:44:45,850 --> 00:44:51,100
significa que apenas supondo que você tem um bom, distribuição, limpa e uniforme de dados

745
00:44:51,100 --> 00:44:53,650
e você tem uma matriz grande o suficiente para caber um monte de coisas

746
00:44:53,650 --> 00:44:59,360
não significa que você está indo para obter as pessoas em locais exclusivos.

747
00:44:59,360 --> 00:45:03,810
Você vai ter colisões. Portanto, esta noção de hash, como é chamado,

748
00:45:03,810 --> 00:45:07,450
tomando uma entrada como "Alice" e massageando-o de alguma forma

749
00:45:07,450 --> 00:45:10,190
e depois voltar uma resposta como 0 ou 1 ou 2.

750
00:45:10,190 --> 00:45:17,500
Voltando alguma saída dessa função é atormentado por essa probabilidade de colisão.

751
00:45:17,500 --> 00:45:19,530
Então, como podemos lidar com essas colisões?

752
00:45:19,530 --> 00:45:21,940
Bem, em um caso, podemos ter a idéia de que foi sugerido.

753
00:45:21,940 --> 00:45:25,100
Nós podemos apenas mudar todos para baixo, ou talvez, um pouco mais simples,

754
00:45:25,100 --> 00:45:29,870
em vez de todos os outros movimento, vamos mover Anita para o fundo do local disponível.

755
00:45:29,870 --> 00:45:32,810
Então, se Alice está em 0, Bob está em 1, Charlie está em 2,

756
00:45:32,810 --> 00:45:35,260
vamos colocar Anita na localização 3.

757
00:45:35,260 --> 00:45:38,860
E esta é uma técnica em estruturas de dados chamado linear sondagem.

758
00:45:38,860 --> 00:45:41,310
Linear porque você está apenas caminhando nessa linha, e você é uma espécie de sondagem

759
00:45:41,310 --> 00:45:43,640
para os locais disponíveis na estrutura de dados.

760
00:45:43,640 --> 00:45:46,210
Naturalmente, este transforma em O (n).

761
00:45:46,210 --> 00:45:49,590
Se a estrutura de dados é realmente completo, há 25 pessoas que já,

762
00:45:49,590 --> 00:45:54,120
e Anita vem, ela acaba com o que seria localização Z, e isso é bom.

763
00:45:54,120 --> 00:45:56,540
Ela ainda se encaixa, e podemos encontrá-la mais tarde.

764
00:45:56,540 --> 00:46:00,100
>> Mas isso era contrário ao objetivo de acelerar as coisas.

765
00:46:00,100 --> 00:46:02,530
Então, o que se criou, essa terceira dimensão?

766
00:46:02,530 --> 00:46:06,400
Essa técnica é geralmente chamado encadeamento separado, ou que possuam cadeias.

767
00:46:06,400 --> 00:46:10,030
E o que uma tabela hash é agora, esta estrutura tabular,

768
00:46:10,030 --> 00:46:13,450
sua tabela é apenas uma matriz de ponteiros.

769
00:46:13,450 --> 00:46:18,230
Mas o que os ponteiros apontam para adivinhar o que é?

770
00:46:18,230 --> 00:46:21,970
Uma lista ligada. Então, o que se tirar o melhor de ambos os mundos?

771
00:46:21,970 --> 00:46:26,500
Usamos matrizes para os índices iniciais

772
00:46:26,500 --> 00:46:32,070
na estrutura de dados, de modo que pode imediatamente ir para [0] [1], [30], ou assim por diante,

773
00:46:32,070 --> 00:46:36,480
mas para que possamos ter alguma flexibilidade e podemos encaixar Anita e Alice e Adam

774
00:46:36,480 --> 00:46:38,630
e qualquer nome de um outro,

775
00:46:38,630 --> 00:46:43,470
nós mas deixar que o outro eixo crescer de forma arbitrária.

776
00:46:43,470 --> 00:46:47,340
E finalmente, a partir de segunda-feira, tem essa capacidade expressiva com lista encadeada.

777
00:46:47,340 --> 00:46:49,530
Podemos crescer uma estrutura de dados de forma arbitrária.

778
00:46:49,530 --> 00:46:52,450
Alternativamente, podemos apenas fazer uma matriz de 2 dimensões enormes,

779
00:46:52,450 --> 00:46:57,190
mas que vai ser uma situação terrível se uma das linhas de uma matriz de 2 dimensões

780
00:46:57,190 --> 00:47:01,280
não é suficientemente grande para a pessoa cujo nome adicional acontece a começar com A.

781
00:47:01,280 --> 00:47:04,200
Deus nos livre de ter que realocar uma estrutura 2-dimensional enorme

782
00:47:04,200 --> 00:47:06,600
apenas porque há tantas pessoas denominados A,

783
00:47:06,600 --> 00:47:09,480
especialmente quando há tão poucas pessoas nomeadas algo Z.

784
00:47:09,480 --> 00:47:12,170
Ele só vai ser uma muito escassa estrutura de dados.

785
00:47:12,170 --> 00:47:15,400
Portanto, não é perfeito, por qualquer meio, mas agora pelo menos temos a capacidade

786
00:47:15,400 --> 00:47:19,090
Para encontrar onde Alice ou Anita pertence,

787
00:47:19,090 --> 00:47:21,090
pelo menos em termos do eixo vertical,

788
00:47:21,090 --> 00:47:25,850
e depois só temos de decidir onde colocar Anita ou Alice nesta lista ligada.

789
00:47:25,850 --> 00:47:32,480
Se nós não nos importamos com classificando as coisas, com que rapidez podemos inserir Alice em uma estrutura como esta?

790
00:47:32,480 --> 00:47:35,370
É tempo constante. Nós índice para [0], e se não houver ninguém,

791
00:47:35,370 --> 00:47:37,550
Alice vai no início dessa lista ligada.

792
00:47:37,550 --> 00:47:40,000
Mas isso não é um grande negócio. Porque se Anita então vem

793
00:47:40,000 --> 00:47:42,160
um número de passos depois, onde é que Anita pertence?

794
00:47:42,160 --> 00:47:45,140
Bem, [0]. POO. Alice já está na lista ligada.

795
00:47:45,140 --> 00:47:47,760
>> Mas, se não se importam com a classificação desses nomes,

796
00:47:47,760 --> 00:47:53,580
podemos apenas passar mais de Alice, inserção Anita, mas mesmo isso é tempo constante.

797
00:47:53,580 --> 00:47:57,010
Mesmo se houver Alice e Adão e todos esses outros nomes A,

798
00:47:57,010 --> 00:47:59,410
ele não está realmente mudando-los fisicamente. Por quê?

799
00:47:59,410 --> 00:48:04,090
Porque nós fizemos aqui com lista encadeada, quem sabe se esses nós são afinal?

800
00:48:04,090 --> 00:48:06,550
Tudo que você tem a fazer é mover as migalhas de pão.

801
00:48:06,550 --> 00:48:10,930
Mova as setas ao redor, você não tem que mover fisicamente todos os dados ao redor.

802
00:48:10,930 --> 00:48:14,610
Assim, podemos inserir Anita, nesse caso, instantaneamente. Tempo constante.

803
00:48:14,610 --> 00:48:20,250
Portanto, temos de tempo constante de pesquisa e de tempo constante inserção de alguém como Anita.

804
00:48:20,250 --> 00:48:22,740
Mas tipo de simplificar o mundo.

805
00:48:22,740 --> 00:48:28,510
O que se mais tarde quiser encontrar Alice?

806
00:48:28,510 --> 00:48:31,050
O que se mais tarde quiser encontrar Alice?

807
00:48:31,050 --> 00:48:35,690
Quantos passos é que vai levar?

808
00:48:35,690 --> 00:48:37,850
[Responder Estudante, ininteligível]

809
00:48:37,850 --> 00:48:40,950
Exatamente. O número de pessoas antes de Alice na lista ligada.

810
00:48:40,950 --> 00:48:45,420
Portanto, não é perfeita, porque a nossa estrutura de dados, mais uma vez, tem este acesso vertical

811
00:48:45,420 --> 00:48:50,240
e então ele tem essas listas ligadas de suspensão - na verdade, não vamos desenhar uma matriz.

812
00:48:50,240 --> 00:48:56,020
Tem essas listas ligadas pendurado fora dele que se parece um pouco algo como isto.

813
00:48:56,020 --> 00:48:59,110
Mas o problema é se Alice e Adão e todos esses outros nomes A

814
00:48:59,110 --> 00:49:01,720
acabar mais e mais para lá,

815
00:49:01,720 --> 00:49:04,810
encontrar alguém pode acabar levando um monte de etapas,

816
00:49:04,810 --> 00:49:06,670
bcause você tem que atravessar a lista ligada,

817
00:49:06,670 --> 00:49:08,090
que é uma operação linear.

818
00:49:08,090 --> 00:49:14,270
Então, realmente, em seguida, o tempo de inserção, em última análise é O (n), onde n é o número de elementos na lista.

819
00:49:14,270 --> 00:49:21,780
Dividido por, vamos chamá-lo arbitrariamente m, onde m é o número de listas ligadas

820
00:49:21,780 --> 00:49:24,500
que temos neste eixo vertical.

821
00:49:24,500 --> 00:49:27,180
Em outras palavras, se realmente assumir uma distribuição uniforme de nomes,

822
00:49:27,180 --> 00:49:30,150
totalmente irrealista. Há, obviamente, mais de algumas letras do que outros.

823
00:49:30,150 --> 00:49:32,580
>> Mas se nós assumimos para o momento de uma distribuição uniforme,

824
00:49:32,580 --> 00:49:37,350
e temos n total de pessoas, e m correntes totais

825
00:49:37,350 --> 00:49:40,630
à nossa disposição, em seguida, o comprimento de cada uma destas cadeias

826
00:49:40,630 --> 00:49:44,380
forma muito simples, vai ser o total, n, dividido pelo número de correntes.

827
00:49:44,380 --> 00:49:48,900
Assim, n / m. Mas aqui é onde podemos ser tudo matematicamente inteligente.

828
00:49:48,900 --> 00:49:53,030
m é uma constante, porque não há um número fixo de estes.

829
00:49:53,030 --> 00:49:54,620
Você está indo para declarar a matriz no início,

830
00:49:54,620 --> 00:49:58,450
e não estamos redimensionando o eixo vertical. Por definição, que permanece fixo.

831
00:49:58,450 --> 00:50:01,220
É apenas o eixo horizontal, por assim dizer, isso está mudando.

832
00:50:01,220 --> 00:50:04,760
Então, tecnicamente, é uma constante. Então, agora, o tempo de inserção

833
00:50:04,760 --> 00:50:09,700
é muito bonito O (n).

834
00:50:09,700 --> 00:50:12,410
De modo que não se sente tudo o que muito melhor.

835
00:50:12,410 --> 00:50:14,940
Mas o que há de verdade nisso? Bem, todo esse tempo, por semanas,

836
00:50:14,940 --> 00:50:20,640
estamos dizendo O (n ²). O (n), 2 x n ², - n, dividido por 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
É apenas ² n. Mas agora, nesta parte do semestre,

838
00:50:23,580 --> 00:50:25,560
podemos começar a falar sobre o mundo real novamente.

839
00:50:25,560 --> 00:50:31,520
E n / m é absolutamente mais rápido do que apenas n sozinha.

840
00:50:31,520 --> 00:50:35,170
Se você tem mil nomes, e dividi-las em vários baldes

841
00:50:35,170 --> 00:50:37,820
para que você tenha apenas 10 nomes em cada uma dessas cadeias,

842
00:50:37,820 --> 00:50:41,670
absolutamente buscar 10 coisas vai ser mais rápido do que mil coisas.

843
00:50:41,670 --> 00:50:43,740
E assim um dos conjuntos de problemas futuros vai desafiá-lo

844
00:50:43,740 --> 00:50:46,100
para pensar sobre exatamente que, apesar de, sim,

845
00:50:46,100 --> 00:50:49,520
assintoticamente e matematicamente, isso ainda é apenas linear,

846
00:50:49,520 --> 00:50:51,700
que suga, em geral, ao tentar encontrar as coisas.

847
00:50:51,700 --> 00:50:54,530
Na realidade, o que vai ser mais rápido do que

848
00:50:54,530 --> 00:50:56,520
devido a este divisor.

849
00:50:56,520 --> 00:50:58,310
E assim, lá está de novo vai ser este trade-off

850
00:50:58,310 --> 00:51:01,390
e este conflito entre a teoria ea realidade,

851
00:51:01,390 --> 00:51:03,550
e um dos botões vai começar a girar neste ponto no semestre

852
00:51:03,550 --> 00:51:07,510
é mais a realidade como um tipo de preparar para o final de semster,

853
00:51:07,510 --> 00:51:09,280
como vamos introduzir no mundo da programação web,

854
00:51:09,280 --> 00:51:11,530
onde realmente, o desempenho vai contar porque seus usuários estão indo para

855
00:51:11,530 --> 00:51:14,880
começar a sentir e apreciar as decisões de design pobre.

856
00:51:14,880 --> 00:51:19,950
>> Então, como você vai fazer sobre a implementação de um ligado - uma tabela hash com 31 elementos?

857
00:51:19,950 --> 00:51:22,600
E o exemplo anterior foi arbitrariamente sobre aniversários.

858
00:51:22,600 --> 00:51:26,190
Se alguém tem um aniversário de 01 de janeiro ou 01 de fevereiro, vamos colocá-los neste balde.

859
00:51:26,190 --> 00:51:28,960
Se é 02 de janeiro, 02 de fevereiro, 2 de março, nós vamos colocá-los neste balde.

860
00:51:28,960 --> 00:51:32,220
É por isso que foi de 31. Como você declarar uma tabela hash?

861
00:51:32,220 --> 00:51:37,480
Ele pode ser bastante simples, mesa * nó é o meu nome arbitrário para ele, [31].

862
00:51:37,480 --> 00:51:42,400
Isso me dá 31 dicas para nós,

863
00:51:42,400 --> 00:51:45,370
e que me permite ter 31 ponteiros para listas ligadas

864
00:51:45,370 --> 00:51:48,800
mesmo que essas correntes são inicialmente NULL.

865
00:51:48,800 --> 00:51:54,860
O que eu quero colocar, se eu quiser armazenar "Alice", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Bem, é preciso envolver essas coisas em uma estrutura

867
00:51:57,010 --> 00:52:00,530
porque precisamos de Alice para apontar para Bob, para apontar para Charlie, e assim por diante.

868
00:52:00,530 --> 00:52:04,940
Nós não podemos apenas ter os nomes só, então eu poderia criar uma nova estrutura chamada nó aqui.

869
00:52:04,940 --> 00:52:08,310
>> O que é um nó real? O que é um nó nesta nova lista ligada?

870
00:52:08,310 --> 00:52:11,840
O primeiro, chamado palavra, é para o nome da pessoa.

871
00:52:11,840 --> 00:52:14,340
COMPRIMENTO, presumivelmente, refere-se ao comprimento máximo do nome de um ser humano,

872
00:52:14,340 --> 00:52:18,210
seja o que for, 20, 30, 40 personagens em casos de canto louco,

873
00:52:18,210 --> 00:52:22,680
e um é para o que? É apenas o caractere NULL extra, \ 0.

874
00:52:22,680 --> 00:52:27,410
Portanto, este nó é embrulho "algo" dentro de si,

875
00:52:27,410 --> 00:52:29,640
mas também declara um ponteiro chamado próxima

876
00:52:29,640 --> 00:52:32,580
para que possamos cadeia de Alice para Bob para Charlie e assim por diante.

877
00:52:32,580 --> 00:52:36,700
Pode ser NULL, mas não necessariamente tem que ser.

878
00:52:36,700 --> 00:52:40,110
Qualquer dúvida sobre estas tabelas de hash? Sim?

879
00:52:40,110 --> 00:52:46,190
[Estudante pedindo questão, ininteligível] Uma matriz - boa pergunta.

880
00:52:46,190 --> 00:52:50,120
Porque é que esta palavra char em uma matriz em vez de apenas char *?

881
00:52:50,120 --> 00:52:53,830
Neste exemplo um tanto arbitrária, eu não queria ter que recorrer

882
00:52:53,830 --> 00:52:56,190
para malloc para cada um dos nomes originais.

883
00:52:56,190 --> 00:52:59,530
Eu queria declarar uma quantidade máxima de memória para a cadeia

884
00:52:59,530 --> 00:53:06,020
para que eu pudesse copiar para a estrutura de Alice \ 0 e não ter de lidar com malloc e free e similares.

885
00:53:06,020 --> 00:53:11,710
Mas eu poderia fazer isso se eu queria ser mais consciente do uso do espaço. Boa pergunta.

886
00:53:11,710 --> 00:53:14,780
Então, vamos tentar generalizar longe deste

887
00:53:14,780 --> 00:53:18,350
e focar o restante de hoje em estruturas de dados mais geral

888
00:53:18,350 --> 00:53:21,170
e outros problemas que podemos resolver usando os mesmos fundamentos

889
00:53:21,170 --> 00:53:24,590
mesmo que as estruturas de dados elas mesmas podem diferir nos seus pormenores.

890
00:53:24,590 --> 00:53:27,910
>> Assim, verifica-se em ciência da computação, as árvores são muito comuns.

891
00:53:27,910 --> 00:53:29,760
E você pode pensar em uma espécie de árvore como uma árvore genealógica,

892
00:53:29,760 --> 00:53:31,830
onde há algumas raízes, alguns matriarca ou patriarca,

893
00:53:31,830 --> 00:53:34,540
avô ou avó ou mais cedo de volta,

894
00:53:34,540 --> 00:53:38,880
sob o qual estão a mãe eo pai ou irmãos diversas ou similares.

895
00:53:38,880 --> 00:53:42,500
Assim, uma estrutura de árvore tem nós e tem filhos,

896
00:53:42,500 --> 00:53:45,260
geralmente 0 ou mais crianças para cada nó.

897
00:53:45,260 --> 00:53:47,320
E alguns dos jargões que você vê nesta foto aqui

898
00:53:47,320 --> 00:53:50,630
é qualquer uma das crianças pequenas ou netos nas bordas

899
00:53:50,630 --> 00:53:52,330
que não têm setas que emanam a partir deles,

900
00:53:52,330 --> 00:53:55,070
essas são as folhas chamados, e qualquer pessoa no interior

901
00:53:55,070 --> 00:53:58,790
é um nó interno, você pode chamá-lo de qualquer coisa nesse sentido.

902
00:53:58,790 --> 00:54:01,430
Mas essa estrutura é muito comum. Este aqui é um pouco arbitrária.

903
00:54:01,430 --> 00:54:04,930
Nós temos um filho à esquerda, temos três filhos, à direita,

904
00:54:04,930 --> 00:54:06,830
duas crianças no canto inferior esquerdo.

905
00:54:06,830 --> 00:54:10,740
Assim podemos ter diferentes tamanhos de árvores, mas se começarmos a padronizar as coisas,

906
00:54:10,740 --> 00:54:15,330
e você pode chamar este de vídeo Patrick em busca binária de um curta anterior

907
00:54:15,330 --> 00:54:19,490
pesquisa, online binário não tem que ser implementado com uma matriz

908
00:54:19,490 --> 00:54:21,410
ou pedaços de papel em um quadro negro.

909
00:54:21,410 --> 00:54:25,490
Suponha que você queria para armazenar seus números em uma estrutura de dados mais sofisticados.

910
00:54:25,490 --> 00:54:27,680
Você poderia criar uma árvore como esta.

911
00:54:27,680 --> 00:54:35,290
Pode ter um nó declarado em C, e que o nó pode ter, pelo menos, dois elementos no interior do mesmo.

912
00:54:35,290 --> 00:54:39,470
Um deles é o número que deseja armazenar, eo outro é - bem, nós precisamos de mais um.

913
00:54:39,470 --> 00:54:41,540
A outra é seus filhos.

914
00:54:41,540 --> 00:54:45,150
Então, aqui está uma outra estrutura de dados. Desta vez, o nó é definido como o armazenamento de um número n

915
00:54:45,150 --> 00:54:49,060
e, em seguida, dois ponteiros, criança esquerdo e direito da criança.

916
00:54:49,060 --> 00:54:52,100
E eles não são arbitrárias. O que é interessante sobre esta árvore?

917
00:54:52,100 --> 00:55:00,550
>> Qual é o padrão na forma como temos colocado isso ou como Patrick colocou-o em seu vídeo?

918
00:55:00,550 --> 00:55:02,790
É meio óbvio que há alguma ordenação acontecendo aqui,

919
00:55:02,790 --> 00:55:04,460
mas o que é a regra simples? Sim?

920
00:55:04,460 --> 00:55:08,350
[Responder Estudante, ininteligível]

921
00:55:08,350 --> 00:55:12,040
Perfeito. Se você olhar para isso, você vê os números pequenos de esquerda,

922
00:55:12,040 --> 00:55:14,690
grandes números do lado esquerdo, mas isso é verdade para cada nó.

923
00:55:14,690 --> 00:55:20,370
Para cada nó, o seu filho esquerdo inferior, e a sua criança direita maior do que.

924
00:55:20,370 --> 00:55:25,210
O que isto significa que agora é que se eu quiser procurar esta estrutura de dados para, por exemplo, o número 44,

925
00:55:25,210 --> 00:55:29,320
Eu tenho que começar na raiz, porque, como com todas essas estruturas mais complexas de dados, agora,

926
00:55:29,320 --> 00:55:31,910
temos apenas um ponteiro para uma coisa, o início.

927
00:55:31,910 --> 00:55:35,010
E, neste caso, o início é a raiz. Não é o lado esquerdo,

928
00:55:35,010 --> 00:55:39,530
é a raiz desta estrutura. Então eu vejo aqui é 55, e eu estou procurando 44.

929
00:55:39,530 --> 00:55:41,430
Qual direção que eu quero ir?

930
00:55:41,430 --> 00:55:45,680
Bem, eu quero ir para a esquerda, porque, obviamente, para a direita vai ser muito grande.

931
00:55:45,680 --> 00:55:49,050
Então, observe aqui, você é uma espécie de conceitualmente cortar a árvore em meia

932
00:55:49,050 --> 00:55:51,700
porque você nunca está indo para o lado direito.

933
00:55:51,700 --> 00:55:55,410
Então agora eu ir do 55 ao 33. É muito pequeno de um número.

934
00:55:55,410 --> 00:56:01,590
Estou à procura de 44, mas agora eu sei, se 44 é nesta árvore, eu posso ir, obviamente, para a direita.

935
00:56:01,590 --> 00:56:04,460
Então, novamente, eu sou a poda da árvore no meio.

936
00:56:04,460 --> 00:56:06,780
É praticamente idêntico conceitualmente para o livro de telefone.

937
00:56:06,780 --> 00:56:09,510
É idêntico ao que fizemos com os papéis no quadro negro,

938
00:56:09,510 --> 00:56:13,940
mas é uma estrutura mais sofisticada, que nos permite realmente fazer

939
00:56:13,940 --> 00:56:16,880
este dividir e conquistar, pelo design do algoritmo,

940
00:56:16,880 --> 00:56:19,420
e, de fato, atravessando uma estrutura como esta - gritos.

941
00:56:19,420 --> 00:56:22,870
Atravessando uma estrutura como esta, onde é apenas "ir por este caminho ou ir por esse caminho",

942
00:56:22,870 --> 00:56:26,870
significa todo o código que que dobrado sua mente em primeiro lugar quando implementá-lo na seção

943
00:56:26,870 --> 00:56:31,270
ou andar com ele em casa, por busca binária, usando recursão ou iteração,

944
00:56:31,270 --> 00:56:35,060
é uma dor no pescoço. Encontre o elemento do meio, em seguida, fazer o seu arredondamento para cima ou para baixo.

945
00:56:35,060 --> 00:56:39,230
>> Há uma beleza a este, porque agora podemos usar recursão novamente,

946
00:56:39,230 --> 00:56:43,760
mas muito mais limpa. Na verdade, se você está no número 55 e você quer encontrar 44,

947
00:56:43,760 --> 00:56:48,450
você vá para a esquerda, neste caso, então o que você faz? Você corre o algoritmo exato.

948
00:56:48,450 --> 00:56:51,560
Você verifica o valor do nó, então você vá para a esquerda ou direita.

949
00:56:51,560 --> 00:56:53,670
Então você verificar o valor do nó, vá para a esquerda ou direita.

950
00:56:53,670 --> 00:56:56,710
Isto é perfeitamente adequado para a recursividade.

951
00:56:56,710 --> 00:57:00,920
Assim, mesmo que no passado fizemos alguns exemplos bastante arbitrárias que envolvem recursão

952
00:57:00,920 --> 00:57:03,430
que não precisa ser recursiva, com stuctures de dados,

953
00:57:03,430 --> 00:57:07,820
especialmente árvores, é uma perfeita aplicação desta idéia de levar um problema,

954
00:57:07,820 --> 00:57:12,920
reduzindo-a, e em seguida a solução do mesmo tipo de, mas menor do programa.

955
00:57:12,920 --> 00:57:14,590
>> Portanto, há uma outra estrutura de dados que podemos apresentar.

956
00:57:14,590 --> 00:57:18,760
Este é projetada à primeira vista olhar enigmático, mas este é incrível.

957
00:57:18,760 --> 00:57:25,090
Portanto, esta é uma estrutura de dados chamada trie, trie, que é herdado da recuperação de palavra,

958
00:57:25,090 --> 00:57:30,210
que não é pronunciado re-try-val, mas é o que o mundo chama essas coisas. Tenta. T-r-i-e.

959
00:57:30,210 --> 00:57:35,190
É uma estrutura de árvore de algum tipo, mas cada um de nós em um trie

960
00:57:35,190 --> 00:57:41,280
parece ser o que? E isso é um pouco enganoso, porque é uma espécie de abreviado.

961
00:57:41,280 --> 00:57:45,960
Mas parece que cada nó neste trie é na verdade uma matriz.

962
00:57:45,960 --> 00:57:48,840
E mesmo que o autor deste diagrama não tem mostrado que,

963
00:57:48,840 --> 00:57:54,130
neste caso, este trie é uma estrutura de dados cujo propósito na vida é armazenar palavras

964
00:57:54,130 --> 00:57:57,330
como A-l-i-c-e ou B-o-b.

965
00:57:57,330 --> 00:58:02,480
E a maneira pela qual os dados lojas Alice e Bob e Charlie e Anita e assim por diante

966
00:58:02,480 --> 00:58:06,970
é que ele usa uma matriz para armazenar qual Alice em uma trie,

967
00:58:06,970 --> 00:58:09,820
começamos no nó raiz que se parece com uma matriz,

968
00:58:09,820 --> 00:58:12,080
e que ele foi escrito em notação abreviada.

969
00:58:12,080 --> 00:58:15,070
O autor omitido abcdefg porque não havia nomes com isso.

970
00:58:15,070 --> 00:58:19,150
Eles só mostrou M e P e T, mas neste caso,

971
00:58:19,150 --> 00:58:22,780
vamos passar longe de Alice e Bob e Charlie para alguns nomes que estão aqui.

972
00:58:22,780 --> 00:58:25,670
Maxwell é realmente neste diagrama.

973
00:58:25,670 --> 00:58:29,570
Então, como o armazenamento de autor M-a-x-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
Ele ou ela começou no nó raiz, e foi para [M], de modo mais ou menos 13, o local 13 na matriz.

975
00:58:36,990 --> 00:58:40,750
Então, a partir daí, há um ponteiro.

976
00:58:40,750 --> 00:58:42,760
Um ponteiro levando para outro array.

977
00:58:42,760 --> 00:58:47,880
A partir daí o autor indexados em que a matriz na posição A, como mostrado lá em cima, à esquerda,

978
00:58:47,880 --> 00:58:52,250
e depois que ele ou ela seguiu esse ponteiro para outra matriz,

979
00:58:52,250 --> 00:58:55,460
e foi para o ponteiro no local X.

980
00:58:55,460 --> 00:58:59,840
Em seguida, na próxima localização matriz W, E, L, L, e assim por diante,

981
00:58:59,840 --> 00:59:03,090
e, finalmente, vamos realmente tentar colocar uma imagem para isso.

982
00:59:03,090 --> 00:59:05,380
O que faz um nó como no código?

983
00:59:05,380 --> 00:59:11,820
Um nó em uma trie contém uma matriz de ponteiros para nós mais.

984
00:59:11,820 --> 00:59:16,090
Mas há também tem de haver algum tipo de valor booleano, pelo menos nesta implementação.

985
00:59:16,090 --> 00:59:18,770
Acontece que eu chamá-lo is_word. Por quê?

986
00:59:18,770 --> 00:59:22,670
Porque quando você está inserindo Maxwell, você não está inserindo

987
00:59:22,670 --> 00:59:25,300
nada para esta estrutura de dados.

988
00:59:25,300 --> 00:59:27,480
Você não está escrevendo M. Você não está escrevendo X.

989
00:59:27,480 --> 00:59:30,240
Tudo o que você está fazendo é seguir ponteiros.

990
00:59:30,240 --> 00:59:33,360
O ponteiro que representa M, então o ponteiro que representa A,

991
00:59:33,360 --> 00:59:36,310
em seguida, o ponteiro que representa X, em seguida, W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
mas o que você precisa fazer no final é uma espécie de vão, verificar, cheguei a este local.

993
00:59:41,950 --> 00:59:45,560
Havia uma palavra que termina aqui na estrutura de dados.

994
00:59:45,560 --> 00:59:48,190
>> Então, o que uma trie é realmente cheio e com o autor escolheu para representar

995
00:59:48,190 --> 00:59:51,880
estes terminuses com pequenos triângulos.

996
00:59:51,880 --> 00:59:56,470
Isto apenas significa que o fato de esse triângulo está aqui, este valor booleano verdadeiro

997
00:59:56,470 --> 00:59:59,200
significa que se você ir para trás na árvore,

998
00:59:59,200 --> 01:00:02,420
significa que uma palavra é chamado Maxwell neste.

999
01:00:02,420 --> 01:00:04,870
Mas a palavra foo, por exemplo,

1000
01:00:04,870 --> 01:00:07,970
não está na árvore, porque se eu começar no nó raiz aqui em cima,

1001
01:00:07,970 --> 01:00:14,030
Não há ponteiro f, nenhum ponteiro o, não o ponteiro. Foo não é um nome neste dicionário.

1002
01:00:14,030 --> 01:00:22,460
Mas por outro lado, turação, t-u-r-i-n-g. Mais uma vez, eu não armazenar t ou u ou r ou i ou n ou g.

1003
01:00:22,460 --> 01:00:29,820
Mas eu fiz na loja esta estrutura de dados um valor de verdadeiro caminho até aqui neste nó - na árvore

1004
01:00:29,820 --> 01:00:33,030
definindo esse valor booleano de is_word a verdade.

1005
01:00:33,030 --> 01:00:35,740
Assim, um trie é uma espécie de esta estrutura meta muito interessante,

1006
01:00:35,740 --> 01:00:39,810
onde você não está realmente armazenar as próprias palavras para este tipo de dicionário.

1007
01:00:39,810 --> 01:00:45,100
Para ser claro, você está apenas armazenando sim ou não, não é uma palavra que termina aqui.

1008
01:00:45,100 --> 01:00:46,430
>> Agora, qual é a implicação?

1009
01:00:46,430 --> 01:00:51,120
Se você tem 150 mil palavras em um dicionário que você está tentando armazenar na memória

1010
01:00:51,120 --> 01:00:53,400
usando algo como uma lista ligada,

1011
01:00:53,400 --> 01:00:56,870
você vai ter 150 mil nós em sua lista ligada.

1012
01:00:56,870 --> 01:01:00,250
E encontrar uma dessas palavras em ordem alfabética pode levar tempo O (n).

1013
01:01:00,250 --> 01:01:04,370
Tempo linear. Mas no caso aqui de uma trie,

1014
01:01:04,370 --> 01:01:09,210
o que é o tempo de execução de encontrar uma palavra?

1015
01:01:09,210 --> 01:01:17,390
Acontece que a beleza aqui é que mesmo se você tem 149.999 palavras já neste dicionário,

1016
01:01:17,390 --> 01:01:20,170
como implementado com esta estrutura de dados,

1017
01:01:20,170 --> 01:01:25,560
quanto tempo leva para encontrar ou inserir mais uma pessoa em que, como Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Bem, é apenas 5, talvez 6 passos para o personagem de fuga.

1019
01:01:30,640 --> 01:01:32,880
Porque o presense de outros nomes na estrutura

1020
01:01:32,880 --> 01:01:35,340
não ficar no caminho de inserção de Alice.

1021
01:01:35,340 --> 01:01:39,640
Além disso, encontrar Alice uma vez que existem 150.000 palavras neste dicionário

1022
01:01:39,640 --> 01:01:41,960
não entrar em seu caminho de encontrar Alice em tudo,

1023
01:01:41,960 --> 01:01:46,880
porque Alice é. . . . . aqui, porque eu encontrei um valor booleano.

1024
01:01:46,880 --> 01:01:50,920
E se não houver booleano verdadeiro, então Alice não está na esta estrutura de dados de palavras.

1025
01:01:50,920 --> 01:01:56,220
Em outras palavras, o tempo de execução de encontrar as coisas e inserindo as coisas para este novo

1026
01:01:56,220 --> 01:02:01,920
estrutura de dados de trie é O de - não é n.

1027
01:02:01,920 --> 01:02:05,730
Porque o presense de 150.000 pessoas não tem efeito sobre Alice, que parece.

1028
01:02:05,730 --> 01:02:11,560
Então, vamos chamá-lo de k, onde k é o comprimento máximo de uma palavra em Inglês

1029
01:02:11,560 --> 01:02:14,050
que é, tipicamente, não mais do que 20 e poucos caracteres.

1030
01:02:14,050 --> 01:02:17,940
Assim, k é uma constante. Assim, o Santo Graal que parecem ter encontrado agora

1031
01:02:17,940 --> 01:02:26,000
é o de uma vez, trie constante para pastilhas, para pesquisas, por eliminações.

1032
01:02:26,000 --> 01:02:29,170
Como o número de coisas já na estrutura,

1033
01:02:29,170 --> 01:02:32,600
que não são nem mesmo fisicamente lá. Mais uma vez, eles estão apenas uma espécie de desmarcado, sim ou não,

1034
01:02:32,600 --> 01:02:35,050
não tem impacto no seu tempo futuro em execução.

1035
01:02:35,050 --> 01:02:37,940
>> Mas tem de ser um problema, caso contrário, não teria perdido tanto tempo

1036
01:02:37,940 --> 01:02:41,460
em todas essas estruturas de dados outros apenas para finalmente chegar ao um segredo que é incrível.

1037
01:02:41,460 --> 01:02:46,410
Então, qual o preço que estamos pagando para alcançar essa grandeza aqui? Espaço.

1038
01:02:46,410 --> 01:02:49,010
Essa coisa é enorme. E a razão que o autor

1039
01:02:49,010 --> 01:02:52,400
não apresentá-lo aqui, notar que todas essas coisas que se parecem com matrizes,

1040
01:02:52,400 --> 01:02:55,400
ele não desenhar o restante da árvore, o resto do trie,

1041
01:02:55,400 --> 01:02:58,060
porque eles são não apenas relevantes para a história.

1042
01:02:58,060 --> 01:03:01,870
Mas todos esses nós são super grande, e cada nó na árvore ocupa

1043
01:03:01,870 --> 01:03:07,780
26 ou, na verdade, poderia ser de 27 caracteres, porque neste caso eu estava incluindo espaço para o apóstrofo

1044
01:03:07,780 --> 01:03:09,980
para que pudéssemos ter palavras apostrofado.

1045
01:03:09,980 --> 01:03:14,450
Neste caso, trata-se matrizes de largura. Assim, mesmo que eles não estão picutured,

1046
01:03:14,450 --> 01:03:18,190
isso leva-se uma enorme quantidade de RAM.

1047
01:03:18,190 --> 01:03:20,670
O que pode ser bom, especilly em hardware moderno,

1048
01:03:20,670 --> 01:03:25,650
mas essa é a troca. Nós temos menos tempo, gastando mais espaço.

1049
01:03:25,650 --> 01:03:28,580
Então, onde é que isto tudo vai?

1050
01:03:28,580 --> 01:03:32,640
Bem, vamos fazer - vamos ver aqui.

1051
01:03:32,640 --> 01:03:39,510
Vamos fazer um salto para esse cara aqui.

1052
01:03:39,510 --> 01:03:43,450
>> Acredite ou não, divertido como C tem sido já há algum tempo,

1053
01:03:43,450 --> 01:03:48,130
estamos chegando ao ponto em que, no semestre é hora de transição para as coisas mais modernas.

1054
01:03:48,130 --> 01:03:50,950
Coisas em um nível superior. E mesmo que para o próximo par de semanas

1055
01:03:50,950 --> 01:03:54,580
vamos continuar a mergulhar no mundo de ponteiros e gerenciamento de memória

1056
01:03:54,580 --> 01:03:57,210
para obter esse conforto com a qual podemos então construir,

1057
01:03:57,210 --> 01:04:01,270
O jogo final é, finalmente, para introduzir, ironicamente, não esta linguagem.

1058
01:04:01,270 --> 01:04:03,330
Nós vamos gastar, como 10 minutos falando sobre HTML.

1059
01:04:03,330 --> 01:04:05,950
Todo o HTML é uma linguagem de marcação, e que é uma linguagem de marcação é

1060
01:04:05,950 --> 01:04:10,220
é esta série de suportes abertos e fechados suportes que dizem "fazer este bold '

1061
01:04:10,220 --> 01:04:12,000
"Tornar esta itálico" "fazer esta centrada."

1062
01:04:12,000 --> 01:04:14,250
Não é tudo o que intelectualmente interessante, mas é super útil.

1063
01:04:14,250 --> 01:04:16,650
E é certamente onipresente nos dias de hoje.

1064
01:04:16,650 --> 01:04:19,450
Mas o que é poderoso sobre o mundo do HTML e programação web em geral,

1065
01:04:19,450 --> 01:04:25,910
está construindo coisas dinâmicas; escrever código em linguagens como PHP ou Python ou Ruby ou Java ou C #.

1066
01:04:25,910 --> 01:04:30,360
Realmente, qualquer que seja o idioma de sua escolha, e gerar HTML dinamicamente.

1067
01:04:30,360 --> 01:04:32,960
Gerando uma coisa chamada CSS dinamicamente.

1068
01:04:32,960 --> 01:04:35,810
Folhas de estilo em cascata, o que é também sobre a estética.

1069
01:04:35,810 --> 01:04:41,360
E por isso mesmo que, hoje, se eu for para algum site como o Google.com familiar,

1070
01:04:41,360 --> 01:04:46,100
e vou ver, desenvolvedor, fonte de visão, que talvez você tenha feito antes,

1071
01:04:46,100 --> 01:04:49,800
mas vai ver o código fonte, este material provavelmente parece muito enigmática.

1072
01:04:49,800 --> 01:04:55,320
Mas este é o código subjacente que implementa Google.com.

1073
01:04:55,320 --> 01:04:57,940
Na extremidade dianteira. E, na verdade, tudo isso é coisa de estética fofo.

1074
01:04:57,940 --> 01:05:01,740
Este é CSS aqui. Se eu continuar a rolagem para baixo nós vamos pegar algumas coisas com código de cores.

1075
01:05:01,740 --> 01:05:06,890
Este é HTML. Código do Google parece uma bagunça, mas se eu realmente abrir uma janela diferente,

1076
01:05:06,890 --> 01:05:09,380
podemos ver alguma estrutura para isso.

1077
01:05:09,380 --> 01:05:12,640
Se eu abrir isto, observe aqui, é um pouco mais legível.

1078
01:05:12,640 --> 01:05:16,850
Nós vamos ver em pouco tempo essa marca, [palavra] é uma tag,

1079
01:05:16,850 --> 01:05:23,520
HTML, cabeça, corpo, div, roteiro, área de texto, extensão, centrado, div.

1080
01:05:23,520 --> 01:05:26,770
E esta é também classificar de aparência enigmática, à primeira vista,

1081
01:05:26,770 --> 01:05:30,890
mas toda esta confusão segue certos padrões, e padrões repetitivos,

1082
01:05:30,890 --> 01:05:33,850
de modo que uma vez que temos o básico para baixo, você vai ser capaz de escrever um código como este

1083
01:05:33,850 --> 01:05:37,550
e, então, manipular o código como esta usando outra linguagem, chamada de JavaScript.

1084
01:05:37,550 --> 01:05:40,440
E JavaScript é uma linguagem que roda dentro de um browser

1085
01:05:40,440 --> 01:05:44,380
hoje, que usamos em Harvard cursos, para a ferramenta de compras curso que usa mapas do Google

1086
01:05:44,380 --> 01:05:48,660
para dar-lhe um monte de dinamismo, o Facebook dá a você para mostrar atualizações de status instantâneas,

1087
01:05:48,660 --> 01:05:51,430
Twitter usa para mostrar o tweets instantaneamente.

1088
01:05:51,430 --> 01:05:53,820
Tudo isso, vamos começar a mergulhar dentro

1089
01:05:53,820 --> 01:05:57,190
Mas para chegar lá, precisamos entender um pouco sobre a Internet.

1090
01:05:57,190 --> 01:06:01,130
Este clip aqui é apenas um minuto de duração, e vamos assumir por agora este é, de fato,

1091
01:06:01,130 --> 01:06:08,380
como a Internet funciona como um teaser para o que está por vir. Eu dar-lhe "Guerreiros do líquido."

1092
01:06:08,380 --> 01:06:14,720
>> [♫ ♫ música lenta coro]

1093
01:06:14,720 --> 01:06:20,450
[Narrador Masculino] Ele veio com uma mensagem.

1094
01:06:20,450 --> 01:06:23,770
Com um protocolo de todo seu.

1095
01:06:23,770 --> 01:06:37,270
[♫ ♫ música Faster eletrônico]

1096
01:06:37,270 --> 01:06:41,330
Ele veio para um mundo de firewalls frias, insensíveis roteadores,

1097
01:06:41,330 --> 01:06:45,690
e perigos muito piores do que a morte.

1098
01:06:45,690 --> 01:06:55,400
Ele é rápido. Ele é forte. Ele é o TCP / IP, e ele tem o seu endereço.

1099
01:06:55,400 --> 01:06:59,250
Guerreiros da rede.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Na próxima semana, então. A Internet. Programação web. Este é CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]