1
00:00:00,000 --> 00:00:03,423
>> [Música tocando]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI Peng: Bem-vindo à semana 6 da seção.

4
00:00:08,210 --> 00:00:11,620
Nós desviado o nosso padrão
tempo seção desta terça-feira

5
00:00:11,620 --> 00:00:14,130
tarde para esta linda manhã de domingo.

6
00:00:14,130 --> 00:00:17,330
Obrigado por todos que
se juntou a mim hoje, mas a sério,

7
00:00:17,330 --> 00:00:18,170
uma salva de palmas.

8
00:00:18,170 --> 00:00:20,600
>> Isso é um bem grande esforço.

9
00:00:20,600 --> 00:00:23,600
Eu quase não mesmo fazê-lo
-se no tempo, mas foi OK.

10
00:00:23,600 --> 00:00:27,520
Então eu sei que todos vocês
que acaba de fazer-lo para o quiz.

11
00:00:27,520 --> 00:00:30,370
Primeiro de tudo, bem-vindo ao
o outro lado disso.

12
00:00:30,370 --> 00:00:32,917
>> Em segundo lugar, vamos falar sobre isso.

13
00:00:32,917 --> 00:00:34,000
Vamos falar sobre o quiz.

14
00:00:34,000 --> 00:00:35,700
Vamos falar sobre como
você está fazendo na classe.

15
00:00:35,700 --> 00:00:36,550
Você vai ficar bem.

16
00:00:36,550 --> 00:00:39,080
Tenho seus testes para
você no final de aqui,

17
00:00:39,080 --> 00:00:42,120
por isso, se vocês querem tomar
um olhar para ele, totalmente bem.

18
00:00:42,120 --> 00:00:46,590
>> Então, rapidamente, antes de começar, o
agenda para hoje é o seguinte.

19
00:00:46,590 --> 00:00:48,430
Como você pode ver, estamos
queima basicamente rápida

20
00:00:48,430 --> 00:00:52,120
através de um monte de estruturas de dados
realmente, realmente, realmente rapidamente.

21
00:00:52,120 --> 00:00:54,380
Assim, como tal, não será
hoje de super interativo.

22
00:00:54,380 --> 00:00:59,620
Vai ser apenas me espécie de gritar
coisas que você, e se eu confundi-lo,

23
00:00:59,620 --> 00:01:02,680
se eu estiver indo rápido demais, deixe-me saber.

24
00:01:02,680 --> 00:01:05,200
Eles são apenas diferentes dados
estruturas, e como parte

25
00:01:05,200 --> 00:01:07,070
do seu pset para este
próxima semana, você vai

26
00:01:07,070 --> 00:01:10,340
ser solicitado para implementar um deles,
talvez duas eles-- dois deles

27
00:01:10,340 --> 00:01:12,319
em sua pset.

28
00:01:12,319 --> 00:01:14,610
OK, então eu estou indo só para
começar com alguns anúncios.

29
00:01:14,610 --> 00:01:19,070
Nós vamos passar por cima de pilhas e filas mais em
profundidade do que o que fizemos antes do quiz.

30
00:01:19,070 --> 00:01:20,990
Nós vamos passar por cima ligado
lista novamente, mais uma vez,

31
00:01:20,990 --> 00:01:23,899
mais em profundidade do que o que
tivemos antes do quiz.

32
00:01:23,899 --> 00:01:26,440
E então nós vamos falar sobre haxixe
mesas, árvores e tentativas, que

33
00:01:26,440 --> 00:01:28,890
são todos muito necessário para o seu pset.

34
00:01:28,890 --> 00:01:32,925
E então nós vamos passar por cima de alguns
dicas úteis para pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, então questionário 0.

36
00:01:37,360 --> 00:01:41,090
A média era de 58%.

37
00:01:41,090 --> 00:01:45,370
Ele foi muito baixa, e assim vocês todos
fez muito, muito bem, de acordo

38
00:01:45,370 --> 00:01:46,510
com aquilo.

39
00:01:46,510 --> 00:01:49,970
>> Muito bonito, regra de ouro é se você estiver
dentro de um desvio padrão da média

40
00:01:49,970 --> 00:01:52,990
especialmente uma vez que estamos em um a menos
seção de conforto, você está totalmente bem.

41
00:01:52,990 --> 00:01:54,120
Você está no caminho certo.

42
00:01:54,120 --> 00:01:55,190
A vida é boa.

43
00:01:55,190 --> 00:01:58,952
>> Eu sei que é assustador pensar que
Eu tenho como um 40% neste quiz.

44
00:01:58,952 --> 00:02:00,160
Vou deixar esta classe.

45
00:02:00,160 --> 00:02:02,243
Eu prometo a você, você não está
vai falhar a classe.

46
00:02:02,243 --> 00:02:03,680
Você está totalmente bem.

47
00:02:03,680 --> 00:02:06,850
>> Para aqueles de vocês que tenho mais
a média, impressionante, impressionante,

48
00:02:06,850 --> 00:02:08,780
como, a sério bem feito.

49
00:02:08,780 --> 00:02:09,689
Eu tê-los comigo.

50
00:02:09,689 --> 00:02:11,730
Sinta-se livre para vir buscá-los
no final da seção.

51
00:02:11,730 --> 00:02:14,520
Deixe-me saber se você tem qualquer
questões, perguntas com eles.

52
00:02:14,520 --> 00:02:17,204
Se somarmos a sua pontuação
errado, deixe-nos saber.

53
00:02:17,204 --> 00:02:21,240
>> OK, então pset5, este é realmente um
semana estranho para Yale no sentido

54
00:02:21,240 --> 00:02:24,240
que a nossa pset é devido
Quarta-feira ao meio-dia, incluindo

55
00:02:24,240 --> 00:02:27,317
o dia de atraso, por isso é, na verdade,
teoricamente devido terça-feira ao meio-dia.

56
00:02:27,317 --> 00:02:29,150
Provavelmente ninguém terminou
em terça-feira ao meio-dia.

57
00:02:29,150 --> 00:02:30,830
Isso é totalmente bom.

58
00:02:30,830 --> 00:02:33,700
Nós vamos ter o horário de expediente
hoje à noite, bem como na noite de ontem.

59
00:02:33,700 --> 00:02:36,810
E todas as seções desta semana vai
na verdade, ser transformado em oficinas,

60
00:02:36,810 --> 00:02:38,800
tão à vontade para pop em
qualquer seção que você quer,

61
00:02:38,800 --> 00:02:42,810
e eles vão ser uma espécie de mini-pset
oficinas para ajuda sobre isso.

62
00:02:42,810 --> 00:02:45,620
Assim, como tal, esta é a única secção
onde estamos material didático.

63
00:02:45,620 --> 00:02:49,220
Todas as outras secções será centrado
exclusivamente na ajuda para o pset.

64
00:02:49,220 --> 00:02:50,146
Sim?

65
00:02:50,146 --> 00:02:52,000
>> AUDIÊNCIA: Onde estão as horas de expediente?

66
00:02:52,000 --> 00:02:56,120
>> ANDI Peng: Horário de atendimento
tonight-- oh, boa pergunta.

67
00:02:56,120 --> 00:03:00,580
Eu acho que o horário de expediente hoje à noite
estão em Teal ou em Commons.

68
00:03:00,580 --> 00:03:02,984
Se você verificar on-line CS50
e você vai para o horário de expediente,

69
00:03:02,984 --> 00:03:05,650
deve haver um cronograma que
diz-lhe onde todos eles são.

70
00:03:05,650 --> 00:03:07,954
>> Eu sei tanto esta noite
ou amanhã é cerceta,

71
00:03:07,954 --> 00:03:10,120
e eu acho que nós podemos ter
commons para a outra noite.

72
00:03:10,120 --> 00:03:11,020
Eu não tenho certeza.

73
00:03:11,020 --> 00:03:11,700
Boa pergunta.

74
00:03:11,700 --> 00:03:14,430
Verifique em CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, qualquer dúvida sobre o
cronograma para a próxima como três dias?

76
00:03:18,780 --> 00:03:21,690
Eu prometo a vocês como David
Dito isto, este é o topo da colina.

77
00:03:21,690 --> 00:03:23,050
Vocês estão quase lá.

78
00:03:23,050 --> 00:03:24,644
Apenas três mais dias.

79
00:03:24,644 --> 00:03:26,310
Chegar lá, e então todos nós vamos descer.

80
00:03:26,310 --> 00:03:28,114
Nós vamos ter uma pausa agradável CS-free.

81
00:03:28,114 --> 00:03:28,780
Bem vindo de volta.

82
00:03:28,780 --> 00:03:30,779
Vamos mergulhar na web
programação e desenvolvimento,

83
00:03:30,779 --> 00:03:35,150
coisas que são muito divertido comparação
para alguns dos outros Série de Exercícios.

84
00:03:35,150 --> 00:03:37,974
E vai ser frio, e
vamos ter muita diversão.

85
00:03:37,974 --> 00:03:38,890
Teremos mais doces.

86
00:03:38,890 --> 00:03:39,730
Desculpem-me por doces.

87
00:03:39,730 --> 00:03:40,945
Eu esqueci de doces.

88
00:03:40,945 --> 00:03:43,310
Era uma manhã áspera.

89
00:03:43,310 --> 00:03:46,340
Então vocês estão quase lá,
e eu estou realmente orgulhoso de vocês.

90
00:03:46,340 --> 00:03:49,570
>> OK, então empilha.

91
00:03:49,570 --> 00:03:53,331
Que amava a pergunta sobre Jack
e as suas vestes no teste?

92
00:03:53,331 --> 00:03:53,830
Ninguém?

93
00:03:53,830 --> 00:03:56,500
OK, tudo bem.

94
00:03:56,500 --> 00:04:00,200
>> Então, basicamente, como você pode
imagem de Jack, esse cara aqui,

95
00:04:00,200 --> 00:04:03,350
gosta de tirar a roupa
para fora do topo da pilha,

96
00:04:03,350 --> 00:04:05,750
e ele coloca-lo de volta para
a pilha depois que ele é feito.

97
00:04:05,750 --> 00:04:07,600
Assim, deste modo, ele nunca
parece estar ficando

98
00:04:07,600 --> 00:04:10,090
para a parte inferior do
empilhar em sua roupa.

99
00:04:10,090 --> 00:04:12,600
Portanto, este tipo de descreve
a estrutura de base de dados

100
00:04:12,600 --> 00:04:16,610
de como uma pilha é implementada.

101
00:04:16,610 --> 00:04:20,060
>> Essencialmente, pense em um
pilha como qualquer pilha de objetos

102
00:04:20,060 --> 00:04:24,900
onde você colocar as coisas para o topo, e
então você pop-los para fora do topo.

103
00:04:24,900 --> 00:04:28,600
Então LIFO é a sigla que gostamos
para use-- Last In, First Out.

104
00:04:28,600 --> 00:04:32,480
E assim durar para o topo da
pilha é o primeiro que sai.

105
00:04:32,480 --> 00:04:34,260
E assim os dois termos
nós gostamos de associar

106
00:04:34,260 --> 00:04:36,190
com que são chamados push e pop.

107
00:04:36,190 --> 00:04:39,790
Quando você empurrar algo para o
pilha, e você colocá-la de volta.

108
00:04:39,790 --> 00:04:43,422
>> E então eu acho que esta é uma espécie de
conceito abstrato para aqueles de vocês

109
00:04:43,422 --> 00:04:45,630
que querem ver como um
aplicação efectiva desta

110
00:04:45,630 --> 00:04:46,740
no mundo real.

111
00:04:46,740 --> 00:04:50,170
Como muitos de vocês têm escrito um ensaio
talvez como uma hora antes do vencimento,

112
00:04:50,170 --> 00:04:54,510
e você excluiu acidentalmente um enorme
pedaço dele, como acidentalmente?

113
00:04:54,510 --> 00:04:58,560
E então o que fazer controle
que usamos para colocá-lo de volta?

114
00:04:58,560 --> 00:05:00,030
Control-Z, sim?

115
00:05:00,030 --> 00:05:03,640
Controlo-Z, de modo que a quantidade de vezes
que Control-Z salvou minha vida,

116
00:05:03,640 --> 00:05:08,820
salvou minha bunda, cada vez
que é implementado através de uma pilha.

117
00:05:08,820 --> 00:05:13,020
>> Essencialmente todas as informações
que está em seu documento do Word,

118
00:05:13,020 --> 00:05:15,080
ele é empurrado e bateu à vontade.

119
00:05:15,080 --> 00:05:19,460
E assim, essencialmente, sempre que você
excluir qualquer coisa, você colocá-la de volta.

120
00:05:19,460 --> 00:05:22,820
E então se você precisar dele novamente, você
empurrá-lo, que é o Control-C faz.

121
00:05:22,820 --> 00:05:26,770
E função mundo tão real
de estrutura de dados como simples

122
00:05:26,770 --> 00:05:28,690
pode ajudar com sua vida cotidiana.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Assim, um struct é o caminho que
nós realmente criar uma pilha.

125
00:05:40,150 --> 00:05:44,720
Nós digite definir struct, e, em seguida,
chamamos isso de pilha na parte inferior.

126
00:05:44,720 --> 00:05:47,440
E dentro da pilha,
temos dois parâmetros

127
00:05:47,440 --> 00:05:51,580
que pode, essencialmente, manipular,
por isso temos de char capacidade cordas estrela.

128
00:05:51,580 --> 00:05:55,150
>> Tudo o que está a fazer
é a criação de uma matriz

129
00:05:55,150 --> 00:05:58,835
que pode armazenar o que quiser
qual podemos determinar a sua capacidade.

130
00:05:58,835 --> 00:06:01,990
Capacidade é a quantidade máxima de
itens que podemos colocar em esta matriz.

131
00:06:01,990 --> 00:06:05,660
tamanho int é o contador que mantém
o controle de quantos itens são atualmente

132
00:06:05,660 --> 00:06:07,850
na pilha.

133
00:06:07,850 --> 00:06:11,860
Então nós pode acompanhar, A,
tanto como grande a pilha é real,

134
00:06:11,860 --> 00:06:14,850
e, B, quanto dessa pilha
enchemos porque nós não queremos

135
00:06:14,850 --> 00:06:18,800
transbordar sobre o que é a nossa capacidade.

136
00:06:18,800 --> 00:06:24,340
>> Assim, por exemplo, esta linda
pergunta era sobre seu quiz.

137
00:06:24,340 --> 00:06:28,160
Essencialmente, como vamos empurrar
sobre o topo de uma pilha.

138
00:06:28,160 --> 00:06:28,830
Muito simples.

139
00:06:28,830 --> 00:06:30,621
Se você olhar para ele,
vamos caminhar por este.

140
00:06:30,621 --> 00:06:32,640
Se [inaudível] size--
lembre-se, sempre que você

141
00:06:32,640 --> 00:06:35,300
deseja acessar qualquer
parâmetro dentro de uma estrutura,

142
00:06:35,300 --> 00:06:40,320
você faz o nome do struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> Neste caso, s é
o nome da nossa stack.

144
00:06:42,720 --> 00:06:46,230
Queremos acessar o tamanho
da mesma, por isso fazemos s.size.

145
00:06:46,230 --> 00:06:50,280
Assim, desde que o tamanho não é
igual capacidade ou desde

146
00:06:50,280 --> 00:06:52,940
já que é menos do que a capacidade,
quer iria trabalhar aqui.

147
00:06:52,940 --> 00:06:57,180
>> Você deseja acessar o interior
do seu stack, então s.strings,

148
00:06:57,180 --> 00:07:00,790
e você está indo para colocar esse novo número
que você deseja inserir lá.

149
00:07:00,790 --> 00:07:05,030
Vamos apenas dizer que vamos querer
inserir int n na pilha,

150
00:07:05,030 --> 00:07:08,905
nós poderíamos fazer s.strings,
colchetes, s.size iguala n.

151
00:07:08,905 --> 00:07:11,030
Porque o tamanho é onde nós
Estão na pilha

152
00:07:11,030 --> 00:07:14,590
se nós estamos indo para empurrar
-lo, nós apenas acessar

153
00:07:14,590 --> 00:07:17,370
onde quer que o tamanho seja, o
plenitude corrente da pilha,

154
00:07:17,370 --> 00:07:21,729
e nós empurrar o int n nele.

155
00:07:21,729 --> 00:07:24,770
E então nós queremos ter certeza de que
também estamos incrementando tamanho do n,

156
00:07:24,770 --> 00:07:27,436
para que possamos manter o controle de nós temos
adicionada uma coisa extra para a pilha.

157
00:07:27,436 --> 00:07:29,660
Agora temos um tamanho maior.

158
00:07:29,660 --> 00:07:33,196
Será que isso aqui faz sentido
todos, logicamente como ele funciona?

159
00:07:33,196 --> 00:07:34,160
Era uma espécie de rápido.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
AUDIÊNCIA: Você pode passar por cima
os s.stringss.strings [s.size] novamente?

162
00:07:42,160 --> 00:07:45,808
ANDI Peng: Certo, então o que faz
s.size atualmente nos dar?

163
00:07:45,808 --> 00:07:47,440
AUDIÊNCIA: É o tamanho atual.

164
00:07:47,440 --> 00:07:50,890
ANDI Peng: Exatamente, por isso a
índice atual que nosso tamanho é em,

165
00:07:50,890 --> 00:07:57,780
e por isso queremos colocar o novo inteiro
que queremos inserir s.size.

166
00:07:57,780 --> 00:07:58,760
Isso faz sentido?

167
00:07:58,760 --> 00:08:01,110
Porque s.strings, tudo isso
é é o nome da matriz.

168
00:08:01,110 --> 00:08:03,510
Tudo o que é acessando o
matriz dentro da nossa estrutura,

169
00:08:03,510 --> 00:08:06,030
e assim, se quisermos
coloque n em que o índice,

170
00:08:06,030 --> 00:08:09,651
podemos simplesmente acessá-lo
utilizando suportes s.size.

171
00:08:09,651 --> 00:08:10,150
Legal.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Tudo bem, pop, eu Pseudocódigo para fora
para vocês, mas conceito similar.

174
00:08:18,916 --> 00:08:19,790
Isso faz sentido?

175
00:08:19,790 --> 00:08:22,310
Se o tamanho for maior
que zero, então você

176
00:08:22,310 --> 00:08:25,350
sei que você quer tomar algo
porque se o tamanho não é

177
00:08:25,350 --> 00:08:27,620
maior do que zero, então você
tem nada na pilha.

178
00:08:27,620 --> 00:08:29,840
>> Assim, você só quer executar
este código, ele só pode

179
00:08:29,840 --> 00:08:32,320
pop se há algo a estalar.

180
00:08:32,320 --> 00:08:35,830
Assim, se o tamanho é maior
do que 0, que menos o tamanho.

181
00:08:35,830 --> 00:08:40,020
Nós diminuir o tamanho e, em seguida, retornar
o que está dentro dela, porque

182
00:08:40,020 --> 00:08:42,710
estalando, queremos
acesso tudo o que está armazenado

183
00:08:42,710 --> 00:08:45,694
no índice do topo da pilha.

184
00:08:45,694 --> 00:08:46,610
Tudo faz sentido?

185
00:08:46,610 --> 00:08:49,693
Se eu fiz vocês escrever isto,
se vocês ser capaz de escrevê-lo?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
OK, vocês podem brincar com ele.

188
00:08:53,570 --> 00:08:55,252
Não se preocupe se você não obtê-lo.

189
00:08:55,252 --> 00:08:57,460
Não temos tempo para codificar
-lo hoje, porque nós temos

190
00:08:57,460 --> 00:08:59,959
tem um monte de estas estruturas
para percorrer, mas, essencialmente,

191
00:08:59,959 --> 00:09:02,214
pseudocódigo, muito, muito semelhante ao empurrar.

192
00:09:02,214 --> 00:09:03,380
Basta seguir ao longo da lógica.

193
00:09:03,380 --> 00:09:06,092
Certifique-se de que você está acessando todo o
características de sua estrutura corretamente.

194
00:09:06,092 --> 00:09:06,574
Sim?

195
00:09:06,574 --> 00:09:09,282
>> AUDIÊNCIA: Será que esses slides e
essa coisa toda ser até hoje-ish?

196
00:09:09,282 --> 00:09:11,586
ANDI Peng: Sempre, sim.

197
00:09:11,586 --> 00:09:13,710
Vou tentar colocar
isto como uma hora depois.

198
00:09:13,710 --> 00:09:16,626
Vou enviar e-mail David, David vai tentar
colocá-lo como uma hora depois disso.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> OK, então, em seguida, nos movemos para este outro
estrutura de dados adorável chamada de fila.

201
00:09:25,470 --> 00:09:30,140
Como vocês podem ver aqui, um
fila, para os britânicos entre nós,

202
00:09:30,140 --> 00:09:32,010
tudo isso é uma linha.

203
00:09:32,010 --> 00:09:34,680
Assim, ao contrário do que
Você acha que é uma pilha,

204
00:09:34,680 --> 00:09:37,750
uma fila é exatamente o que
logicamente que você pensa que é.

205
00:09:37,750 --> 00:09:41,914
É realizado pelas regras do FIFO,
que é first in, first out.

206
00:09:41,914 --> 00:09:43,705
Se você é o primeiro
um na linha, você está

207
00:09:43,705 --> 00:09:46,230
que o primeiro
sai da linha.

208
00:09:46,230 --> 00:09:49,680
>> Então, o que nós gostamos de chamar este
é dequeueing e enqueueing.

209
00:09:49,680 --> 00:09:52,380
Se queremos acrescentar algo
a nossa fila, nós enfileirar.

210
00:09:52,380 --> 00:09:55,690
Se queremos retirar da fila, ou tomar
algo longe, nós retirar da fila.

211
00:09:55,690 --> 00:10:03,350
>> Assim mesmo sentido que nós somos tipo de
a criação de elementos de tamanho fixo que

212
00:10:03,350 --> 00:10:06,500
pode armazenar certa
coisas, mas nós também podemos

213
00:10:06,500 --> 00:10:10,100
mudar para onde estamos colocando
parâmetros dentro deles

214
00:10:10,100 --> 00:10:13,140
com base no que tipo de
funcionalidade que queremos.

215
00:10:13,140 --> 00:10:16,700
Então, pilhas, queríamos a última
um, N para ser o primeiro a sair.

216
00:10:16,700 --> 00:10:19,800
Fila é que queremos a primeira coisa
para ser a primeira coisa para fora.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Assim, o tipo struct
definir, como você pode ver,

219
00:10:26,710 --> 00:10:29,470
é um pouco diferente
a partir do que foi a pilha

220
00:10:29,470 --> 00:10:33,120
porque não só temos de manter
o controle de onde o tamanho é atualmente,

221
00:10:33,120 --> 00:10:37,420
também queremos manter o controle da cabeça
bem como onde estamos atualmente.

222
00:10:37,420 --> 00:10:39,580
Então, eu acho que é mais fácil
se eu tirar isso.

223
00:10:39,580 --> 00:10:53,270
Então, vamos imaginar que temos uma fila,
então vamos dizer que a cabeça está bem aqui.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
O chefe da linha, vamos
apenas dizer que é atualmente lá,

226
00:10:58,310 --> 00:11:01,809
e queremos inserir
algo na fila.

227
00:11:01,809 --> 00:11:04,350
Eu vou ligar para o tamanho essencialmente
é a mesma coisa que a cauda,

228
00:11:04,350 --> 00:11:06,314
o fim da fila é sempre que o seu.

229
00:11:06,314 --> 00:11:07,730
Vamos apenas dizer que tamanho é aqui mesmo.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Assim como um praticàvel
inserir algo em uma fila?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
O índice queremos colocá
onde queremos inserir.

234
00:11:24,130 --> 00:11:29,320
Se este é o início de sua
fila e este é o fim de tudo

235
00:11:29,320 --> 00:11:31,860
ou o tamanho dele, onde é que vamos
deseja adicionar o próximo objeto?

236
00:11:31,860 --> 00:11:32,920
>> AUDIÊNCIA: [inaudível]

237
00:11:32,920 --> 00:11:35,920
ANDI Peng: Exatamente, você deseja adicionar
-lo, dependendo você escreveu ele.

238
00:11:35,920 --> 00:11:37,840
Ou este é em branco ou que está em branco.

239
00:11:37,840 --> 00:11:42,630
Então você deseja adicioná-lo, provavelmente,
aqui porque, se o tamanho é--

240
00:11:42,630 --> 00:11:50,540
se estes são todos completo, você quer
adicioná-lo aqui, certo?

241
00:11:50,540 --> 00:11:57,150
>> E assim que é, ao mesmo tempo muito, muito
simples, não é bem sempre correto

242
00:11:57,150 --> 00:12:00,690
porque a principal diferença
entre uma fila e uma pilha

243
00:12:00,690 --> 00:12:04,350
é que a fila pode
na verdade, ser manipulado

244
00:12:04,350 --> 00:12:06,980
de modo que as alterações de cabeça
dependendo de onde você quer

245
00:12:06,980 --> 00:12:08,650
o início de sua sugestão para começar.

246
00:12:08,650 --> 00:12:11,900
E, como resultado, sua cauda
também vai mudar.

247
00:12:11,900 --> 00:12:14,770
E então dê uma olhada
este código agora.

248
00:12:14,770 --> 00:12:18,620
Como vocês também foram convidados a
escrever sobre o quiz, enqueue.

249
00:12:18,620 --> 00:12:22,580
Talvez nós vamos falar através porquê
a resposta era o que era.

250
00:12:22,580 --> 00:12:26,790
>> Eu não conseguia encaixar esta linha em um,
mas, essencialmente, este pedaço de código

251
00:12:26,790 --> 00:12:29,030
deve estar em uma linha.

252
00:12:29,030 --> 00:12:30,140
Gastar como 30 segundos.

253
00:12:30,140 --> 00:12:33,000
Dê uma olhada, e veja por que
esta é a maneira que é.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Muito, muito semelhante struct, muito, muito
estrutura semelhante à do anterior

256
00:12:55,420 --> 00:12:58,090
empilhar exceto, talvez,
uma linha de código.

257
00:12:58,090 --> 00:13:01,190
E que uma linha de código
determina a funcionalidade.

258
00:13:01,190 --> 00:13:03,900
E isso realmente diferencia
uma fila de uma pilha.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Quem quiser tomar uma facada
para explicar por que você tem

261
00:13:22,010 --> 00:13:24,980
tem essa coisa complicada aqui?

262
00:13:24,980 --> 00:13:27,845
Nós vemos o retorno de nosso
maravilhoso módulo amigo.

263
00:13:27,845 --> 00:13:31,020
Como vocês virá logo
de reconhecer na programação,

264
00:13:31,020 --> 00:13:34,910
quase a qualquer momento você precisa de algo
para envolver qualquer coisa,

265
00:13:34,910 --> 00:13:36,850
módulo vai ser a maneira de fazê-lo.

266
00:13:36,850 --> 00:13:40,510
Então, sabendo que, alguém quer
para tentar explicar essa linha de código?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Sim, todas as respostas são
aceito e bem-vindo.

269
00:13:47,507 --> 00:13:48,840
AUDIÊNCIA: Você está falando comigo?

270
00:13:48,840 --> 00:13:49,506
ANDI Peng: Sim.

271
00:13:49,506 --> 00:13:56,200
AUDIÊNCIA: Oh, não me desculpe.

272
00:13:56,200 --> 00:14:00,250
ANDI Peng: OK, então vamos
caminhar por este código.

273
00:14:00,250 --> 00:14:03,642
Então, quando você está tentando
adicionar algo em uma fila,

274
00:14:03,642 --> 00:14:08,510
no caso adorável que a cabeça acontece
para estar aqui, é muito fácil para nós

275
00:14:08,510 --> 00:14:10,960
apenas para ir até o fim
inserir alguma coisa, certo?

276
00:14:10,960 --> 00:14:14,690
Mas o ponto inteiro de uma fila é
que a cabeça pode realmente dinamicamente

277
00:14:14,690 --> 00:14:17,280
mudar, dependendo de onde nós
quer o início da nossa q ser,

278
00:14:17,280 --> 00:14:19,880
e, como tal, a cauda
também vai mudar.

279
00:14:19,880 --> 00:14:31,100
>> E assim imaginar que este não era o
fila, mas esta foi a fila.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Vamos dizer que a cabeça está bem aqui.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Vamos dizer que nossa fila olhou como esta.

284
00:14:56,980 --> 00:15:00,190
Se quiséssemos deslocar onde
o início da linha é,

285
00:15:00,190 --> 00:15:03,400
vamos dizer que mudou cabeça
Desta forma e tamanhos aqui.

286
00:15:03,400 --> 00:15:07,100
>> Agora queremos acrescentar algo ao
essa fila, mas como vocês podem ver,

287
00:15:07,100 --> 00:15:11,150
não é tão simples como apenas
adicionar o que é após o tamanho

288
00:15:11,150 --> 00:15:13,630
porque então nós funcionamos fora do
limites da nossa matriz real.

289
00:15:13,630 --> 00:15:16,190
Onde queremos realmente é here.

290
00:15:16,190 --> 00:15:18,610
Essa é a beleza de uma fila
é que, para nós, visualmente

291
00:15:18,610 --> 00:15:22,380
Parece que a linha vai como esta,
mas quando armazenada numa estrutura de dados,

292
00:15:22,380 --> 00:15:29,370
eles dão-lo como como um ciclo.

293
00:15:29,370 --> 00:15:32,360
É o tipo de envolve
para a frente da mesma maneira

294
00:15:32,360 --> 00:15:34,780
que uma linha também pode envolvê
em torno dependendo de onde quer que você

295
00:15:34,780 --> 00:15:36,279
quer início da linha para ser.

296
00:15:36,279 --> 00:15:38,630
E por isso, se dermos uma
olhar para baixo aqui, vamos

297
00:15:38,630 --> 00:15:40,880
dizer que queria criar um
função chamada enqueue.

298
00:15:40,880 --> 00:15:43,980
Nós queríamos adicionar int n em que q.

299
00:15:43,980 --> 00:15:49,250
Se q.size nós q-- chamaremos que os nossos dados
structure-- se o nosso queue.size não

300
00:15:49,250 --> 00:15:52,520
igual capacidade ou se
é menos do que a capacidade,

301
00:15:52,520 --> 00:15:55,120
q.strings é a matriz dentro da nossa q.

302
00:15:55,120 --> 00:15:58,380
Nós estamos indo para definir
que igual a q.heads,

303
00:15:58,380 --> 00:16:02,730
que é aqui mesmo, além de q.size
módulo pela capacidade, que

304
00:16:02,730 --> 00:16:04,290
envolvê-nos de volta por aqui.

305
00:16:04,290 --> 00:16:08,040
>> Assim, neste exemplo, o índice de
de cabeça é um, certo?

306
00:16:08,040 --> 00:16:11,480
O índice de tamanho é 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Então, podemos fazer mais um módulo 4
por nossa capacidade, que é 5.

308
00:16:19,500 --> 00:16:20,920
O que isso nos dá?

309
00:16:20,920 --> 00:16:23,270
O que é que o índice
sai dessa?

310
00:16:23,270 --> 00:16:24,080
>> AUDIÊNCIA: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI Peng: 0, que
passa a ser aqui mesmo,

312
00:16:27,870 --> 00:16:30,640
e por isso queremos ser capazes
para inserir aqui.

313
00:16:30,640 --> 00:16:34,730
E assim esta equação tipo aqui
de apenas funciona com todos os números

314
00:16:34,730 --> 00:16:36,750
dependendo de onde o seu
cabeça e seu tamanho é.

315
00:16:36,750 --> 00:16:38,541
Se você sabe o que aqueles
as coisas são, você sabe

316
00:16:38,541 --> 00:16:43,170
exatamente onde você deseja inserir
tudo o que é depois de sua fila.

317
00:16:43,170 --> 00:16:44,640
Isso faz sentido para todo mundo?

318
00:16:44,640 --> 00:16:48,560
>> Eu sei que tipo de um cérebro
provocação especialmente uma vez que este

319
00:16:48,560 --> 00:16:50,512
veio na sequência do seu quiz.

320
00:16:50,512 --> 00:16:52,220
Mas espero que todos
agora pode entender

321
00:16:52,220 --> 00:16:57,800
por isso que esta solução ou este
função é a maneira que é.

322
00:16:57,800 --> 00:16:59,840
Qualquer um um pouco incerto sobre isso?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
ESTÁ BEM.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> E agora, se você
queria para retirar da fila, este

327
00:17:09,970 --> 00:17:15,240
é onde a nossa cabeça seria deslocando
porque se fôssemos para retirar da fila,

328
00:17:15,240 --> 00:17:17,030
nós não tirar a final do q.

329
00:17:17,030 --> 00:17:19,130
Queremos tirar a cabeça, certo?

330
00:17:19,130 --> 00:17:24,260
Então, como resultado, a cabeça vai mudar,
e é por isso que quando você enfileirar,

331
00:17:24,260 --> 00:17:26,800
você tem que manter o controle de
onde sua cabeça e seu tamanho

332
00:17:26,800 --> 00:17:29,450
são para ser capaz de inserir
para a posição correcta.

333
00:17:29,450 --> 00:17:32,740
>> E assim, quando você retirar da fila,
Eu também Pseudocódigo-lo.

334
00:17:32,740 --> 00:17:35,480
Sinta-se livre para se você quiser
a tentativa de codificação isso.

335
00:17:35,480 --> 00:17:36,980
Você deseja mover a cabeça, certo?

336
00:17:36,980 --> 00:17:39,320
Se eu quisesse para retirar da fila, eu
moveria a cabeça sobre.

337
00:17:39,320 --> 00:17:40,800
Esta seria a cabeça.

338
00:17:40,800 --> 00:17:45,617
>> E o nosso tamanho atual faria
subtrair porque já não

339
00:17:45,617 --> 00:17:46,950
temos quatro elementos na matriz.

340
00:17:46,950 --> 00:17:51,370
Nós só temos três, e então nós queremos
para retornar o que estava armazenado dentro

341
00:17:51,370 --> 00:17:56,260
da cabeça porque queremos aproveitar esta
valor para fora de modo muito semelhante ao da pilha.

342
00:17:56,260 --> 00:17:58,010
Assim você está tomando
de um lugar diferente,

343
00:17:58,010 --> 00:18:01,770
e você tem que voltar a atribuir o ponteiro
para lugar diferente como resultado.

344
00:18:01,770 --> 00:18:03,890
Logicamente, todos sigam?

345
00:18:03,890 --> 00:18:05,690
Ótimo.

346
00:18:05,690 --> 00:18:10,156
>> OK, então vamos falar um pouco
mais em profundidade sobre listas ligadas

347
00:18:10,156 --> 00:18:13,280
porque vai ser muito, muito valioso
para você no decorrer desta semana

348
00:18:13,280 --> 00:18:14,964
Série de Exercícios.

349
00:18:14,964 --> 00:18:17,130
Listas ligadas, como vocês
lembro, todos eles são

350
00:18:17,130 --> 00:18:22,570
são os nós que são nós de certa
valores de ambos um valor e um ponteiro

351
00:18:22,570 --> 00:18:26,290
que estão ligados entre si
por esses ponteiros.

352
00:18:26,290 --> 00:18:29,880
E assim, a estrutura de como
criamos um nó aqui é nós

353
00:18:29,880 --> 00:18:33,569
tem int n, que é o que quer
o valor em uma loja ou cadeia de n

354
00:18:33,569 --> 00:18:35,610
ou o que você quiser
chamá-lo, o caractere estrela n.

355
00:18:35,610 --> 00:18:41,482
Struct estrela nó, que é o ponteiro
que você quer ter em cada nó,

356
00:18:41,482 --> 00:18:43,690
você vai ter que
ponteiro ponto em direção ao lado.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Você vai ter a cabeça
de uma lista ligada que é

359
00:18:50,040 --> 00:18:53,140
indo para apontar para o resto
os valores assim por diante e assim por diante

360
00:18:53,140 --> 00:18:55,290
até que você finalmente chegar ao fim.

361
00:18:55,290 --> 00:18:58,040
E este último nó é apenas
indo para não ter um ponteiro.

362
00:18:58,040 --> 00:18:59,952
Vai para apontar para
null, e que, quando

363
00:18:59,952 --> 00:19:01,910
você sabe que você bateu o
final da sua lista ligada

364
00:19:01,910 --> 00:19:04,076
é quando o último ponteiro
não aponta para qualquer coisa.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Então, nós estamos indo para ir um pouco mais em
profundidade a respeito de como se faria possivelmente

367
00:19:10,990 --> 00:19:12,400
procurar uma lista ligada.

368
00:19:12,400 --> 00:19:15,460
Lembre-se o que são alguns dos
inconvenientes das listas ligadas

369
00:19:15,460 --> 00:19:19,340
versículos uma matriz sobre pesquisas.

370
00:19:19,340 --> 00:19:22,565
Uma matriz que puder busca binária, mas
por que você não pode fazer isso em uma lista vinculada?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> AUDIÊNCIA: Porque eles estão todos conectados,
mas não sei bem onde

373
00:19:30,320 --> 00:19:31,330
[INAUDÍVEL].

374
00:19:31,330 --> 00:19:34,600
>> ANDI Peng: Sim, exatamente por isso lembre-
que o brilho de uma matriz

375
00:19:34,600 --> 00:19:37,190
foi o fato de que tínhamos
memória de acesso aleatório onde

376
00:19:37,190 --> 00:19:41,580
se eu queria o valor do índice
seis, eu poderia apenas dizer índice seis,

377
00:19:41,580 --> 00:19:42,407
dá-me esse valor.

378
00:19:42,407 --> 00:19:45,240
E isso é porque as matrizes são classificadas
num espaço contíguo de memória

379
00:19:45,240 --> 00:19:48,020
em um só lugar, ao passo que
tipo de listas ligadas

380
00:19:48,020 --> 00:19:52,820
são intercaladas aleatoriamente por toda parte,
ea única maneira que você pode encontrar um

381
00:19:52,820 --> 00:19:56,890
é através de um ponteiro que lhe diz
o endereço de onde o próximo nó é.

382
00:19:56,890 --> 00:20:00,290
>> E assim, como resultado, a única maneira
para pesquisar uma lista ligada

383
00:20:00,290 --> 00:20:01,560
é a busca linear.

384
00:20:01,560 --> 00:20:05,890
Porque eu não sei exatamente onde
o valor 12º na lista ligada é,

385
00:20:05,890 --> 00:20:08,780
Eu tenho que atravessar a totalidade
dessa lista um ligado

386
00:20:08,780 --> 00:20:12,450
a um, da cabeça para o primeiro nó,
para o segundo nó, para o terceiro nó,

387
00:20:12,450 --> 00:20:17,690
todo o caminho até que eu finalmente chegar
para onde esse nó eu estou procurando é.

388
00:20:17,690 --> 00:20:22,110
E assim, neste sentido, busca
em uma lista ligada é sempre n.

389
00:20:22,110 --> 00:20:23,040
É sempre n.

390
00:20:23,040 --> 00:20:25,690
É sempre em tempo linear.

391
00:20:25,690 --> 00:20:28,470
>> E assim o código em que
vamos implementar isto, e isto

392
00:20:28,470 --> 00:20:32,620
é um pouco novo para vocês desde que você
caras realmente não tenho falado ou nunca

393
00:20:32,620 --> 00:20:35,000
ponteiros visto em como
pesquisar através de ponteiros,

394
00:20:35,000 --> 00:20:37,670
então vamos percorrer
esta muito, muito lentamente.

395
00:20:37,670 --> 00:20:40,200
Assim, busca bool, direito,
vamos imaginar que queremos

396
00:20:40,200 --> 00:20:42,820
para criar uma função chamada
pesquisa que retorna verdadeiro

397
00:20:42,820 --> 00:20:46,820
Se você encontrou um valor dentro do ligada
lista, e retorna false de outra forma.

398
00:20:46,820 --> 00:20:50,030
Lista estrela nó é
Atualmente apenas o ponteiro

399
00:20:50,030 --> 00:20:52,960
para o primeiro item em sua lista ligada.

400
00:20:52,960 --> 00:20:56,700
int n é o valor que você está
procurando na lista.

401
00:20:56,700 --> 00:20:58,770
>> Então ponteiro estrela nó lista é igual.

402
00:20:58,770 --> 00:21:00,970
Isso significa que nós estamos estabelecendo
e criando um ponteiro

403
00:21:00,970 --> 00:21:03,592
para que o primeiro nó dentro da lista.

404
00:21:03,592 --> 00:21:04,300
Todo mundo comigo?

405
00:21:04,300 --> 00:21:06,530
Então, se tivéssemos de ir
voltar aqui, eu teria

406
00:21:06,530 --> 00:21:13,850
inicializado um ponteiro que indica
o cabeça de tudo o que é lista.

407
00:21:13,850 --> 00:21:18,600
>> E, em seguida, uma vez que você chegar aqui,
enquanto ponteiro não é igual a null,

408
00:21:18,600 --> 00:21:22,160
de modo que é o ciclo em que estamos
vai ser, subsequentemente, atravessando

409
00:21:22,160 --> 00:21:25,940
o resto da nossa lista, porque o que
acontece quando o ponteiro é igual a null?

410
00:21:25,940 --> 00:21:27,550
Sabemos que have--

411
00:21:27,550 --> 00:21:28,450
>> AUDIÊNCIA: [inaudível]

412
00:21:28,450 --> 00:21:31,491
>> ANDI Peng: Exatamente, por isso sabemos que
chegamos ao fim da lista, certo?

413
00:21:31,491 --> 00:21:34,470
Se você voltar aqui, cada nó
deve estar apontando para outro nó

414
00:21:34,470 --> 00:21:36,550
e assim por diante
até chegar, eventualmente,

415
00:21:36,550 --> 00:21:41,589
a cauda da sua lista ligada,
que tem um ponteiro que apenas

416
00:21:41,589 --> 00:21:43,130
não aponta qualquer lugar que não.

417
00:21:43,130 --> 00:21:47,510
E para que você saiba que, basicamente,
sua lista ainda está lá em cima

418
00:21:47,510 --> 00:21:50,900
até ponteiro não é igual
nula porque uma vez que ele é igual a null,

419
00:21:50,900 --> 00:21:53,310
você sabe que não há mais coisas.

420
00:21:53,310 --> 00:21:56,930
>> Então esse é o ciclo em que estamos
vai ter a pesquisa real.

421
00:21:56,930 --> 00:22:01,690
E se os pointer-- você vê
esse tipo de função seta lá?

422
00:22:01,690 --> 00:22:06,930
Portanto, se o ponteiro aponta n, se
o ponteiro em que n é igual é igual a N,

423
00:22:06,930 --> 00:22:09,180
de modo que significa que se
o ponteiro que você é

424
00:22:09,180 --> 00:22:13,420
procurando na extremidade de cada
nó é efectivamente igual ao valor

425
00:22:13,420 --> 00:22:15,990
você está procurando, em seguida,
você quer retornar verdadeiro.

426
00:22:15,990 --> 00:22:19,280
Então, basicamente, se você estiver em um nó que
tem o valor que você está procurando,

427
00:22:19,280 --> 00:22:23,550
você sabe que você esteve
capaz de pesquisa com êxito.

428
00:22:23,550 --> 00:22:27,150
>> Caso contrário, você deseja definir
o ponteiro para o próximo nó.

429
00:22:27,150 --> 00:22:28,850
Isso é o que essa linha está fazendo aqui.

430
00:22:28,850 --> 00:22:31,750
Ponteiro é igual ponteiro próximo.

431
00:22:31,750 --> 00:22:33,360
Todo mundo ver como é que está trabalhando?

432
00:22:33,360 --> 00:22:36,580
>> E, essencialmente, você vai apenas
atravessam a totalidade da lista,

433
00:22:36,580 --> 00:22:41,920
redefinir o ponteiro de cada vez até
você finalmente bateu o final da lista.

434
00:22:41,920 --> 00:22:45,030
E você sabe que não há
mais nós para pesquisar,

435
00:22:45,030 --> 00:22:47,999
e então você pode retornar false
porque você sabe que, oh, bem,

436
00:22:47,999 --> 00:22:50,540
se eu fui capaz de pesquisar
através da totalidade da lista.

437
00:22:50,540 --> 00:22:54,530
Se neste exemplo, se eu quisesse
a olhar para o valor de 10,

438
00:22:54,530 --> 00:22:57,250
e eu começo na cabeça, e
Eu procuro todo o caminho,

439
00:22:57,250 --> 00:23:00,550
e eu finalmente cheguei a esta, que
um ponteiro que aponta para null,

440
00:23:00,550 --> 00:23:04,415
Eu sei que, uma porcaria, eu acho que 10 não está na
esta lista porque eu não poderia encontrá-lo.

441
00:23:04,415 --> 00:23:06,520
E eu estou no fim da lista.

442
00:23:06,520 --> 00:23:11,040
E no caso de que você sabe
Eu estou indo para retornar falso.

443
00:23:11,040 --> 00:23:12,900
>> Deixe que molho em um pouco.

444
00:23:12,900 --> 00:23:17,350
Isso vai ser muito
importante para o seu pset.

445
00:23:17,350 --> 00:23:21,140
A lógica dele é muito simples, talvez
sintaticamente apenas implementá-lo.

446
00:23:21,140 --> 00:23:23,365
Vocês querem fazer
Certifique-se de que você entenda.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Legal.

449
00:23:27,650 --> 00:23:32,560
>> OK, então como nós ficaríamos
inserção de nós, certo,

450
00:23:32,560 --> 00:23:35,380
em uma lista de lembrar, porque
o que são o que os benefícios

451
00:23:35,380 --> 00:23:39,230
de ter uma lista vinculada contra
uma matriz em termos de armazenamento?

452
00:23:39,230 --> 00:23:41,110
>> AUDIÊNCIA: É dinâmico,
por isso é mais fácil a--

453
00:23:41,110 --> 00:23:43,180
>> ANDI Peng: Exatamente,
por isso é dinâmica, o que

454
00:23:43,180 --> 00:23:46,880
significa que pode expandir-se e encolher
dependendo das necessidades do usuário.

455
00:23:46,880 --> 00:23:56,570
E assim, neste sentido, nós não precisamos
desperdiçar memória desnecessária porque eu

456
00:23:56,570 --> 00:24:00,850
se eu não sei quantos valores que eu quero
a loja, não faz sentido para mim

457
00:24:00,850 --> 00:24:04,310
para criar uma matriz porque
se eu quiser armazenar 10 valores

458
00:24:04,310 --> 00:24:08,380
e eu criar uma matriz de 1000, que é
uma grande quantidade de memória desperdiçada, atribuído.

459
00:24:08,380 --> 00:24:11,180
É por isso que nós queremos usar um ligado
lista para ser capaz de dinamicamente

460
00:24:11,180 --> 00:24:13,860
alterar ou diminuir o tamanho da nossa.

461
00:24:13,860 --> 00:24:17,040
>> E assim que faz a inserção
um pouco mais complicado.

462
00:24:17,040 --> 00:24:20,810
Já que não podemos acessar aleatoriamente elementos
da maneira que gostaríamos de uma matriz.

463
00:24:20,810 --> 00:24:24,270
Se eu quiser inserir um elemento
na sétima índice,

464
00:24:24,270 --> 00:24:26,930
Eu só pode inseri-lo
na sétima índice.

465
00:24:26,930 --> 00:24:30,020
Em uma lista ligada, isso não acontece
bastante trabalhar tão facilmente,

466
00:24:30,020 --> 00:24:34,947
e por isso, se queríamos para inserir
o aqui na lista ligada,

467
00:24:34,947 --> 00:24:36,280
visualmente, é muito fácil de ver.

468
00:24:36,280 --> 00:24:39,363
Nós apenas queremos inseri-lo ali mesmo,
logo no início da lista,

469
00:24:39,363 --> 00:24:40,840
logo após a cabeça.

470
00:24:40,840 --> 00:24:44,579
>> Mas a maneira em que nós temos que voltar a atribuir
os ponteiros é um pouco complicado

471
00:24:44,579 --> 00:24:47,620
ou, logicamente, faz sentido, mas
você quer ter certeza de que você tem-

472
00:24:47,620 --> 00:24:50,250
completamente para baixo, porque
a última coisa que você quer

473
00:24:50,250 --> 00:24:52,990
é reatribuir um ponteiro a
maneira que nós estamos fazendo aqui.

474
00:24:52,990 --> 00:24:58,170
Se você excluir a referência o
ponteiro da cabeça aos 1,

475
00:24:58,170 --> 00:25:01,086
então, de repente, o
resto de sua lista ligada

476
00:25:01,086 --> 00:25:04,680
está perdido, porque você não tem, na verdade,
criado um nada temporária.

477
00:25:04,680 --> 00:25:06,220
Isso apontou para o 2.

478
00:25:06,220 --> 00:25:10,080
Se transferir o ponteiro, então o
resto de sua lista está totalmente perdido.

479
00:25:10,080 --> 00:25:13,310
Então você quer ser
muito, muito cuidado aqui

480
00:25:13,310 --> 00:25:17,010
para atribuir o primeiro
ponteiro de tudo o que você

481
00:25:17,010 --> 00:25:20,150
deseja inserir em qualquer lugar
você quer, e então você

482
00:25:20,150 --> 00:25:22,710
pode cancelar o resto de sua lista.

483
00:25:22,710 --> 00:25:25,250
>> Então, isso se aplica para onde quer
você está tentando inserir.

484
00:25:25,250 --> 00:25:27,520
Se você deseja inserir no
cabeça, se você quiser responder aqui,

485
00:25:27,520 --> 00:25:29,455
se você deseja inserir no
Ao final, bem, o fim I

486
00:25:29,455 --> 00:25:30,910
acho que você faria apenas
não tem um ponteiro, mas você

487
00:25:30,910 --> 00:25:33,830
quer ter a certeza de que você não fazer
perder o resto de sua lista.

488
00:25:33,830 --> 00:25:36,640
Você sempre quer ter a certeza
o novo nó está apontando

489
00:25:36,640 --> 00:25:39,330
no sentido de tudo o que você
deseja inserir,

490
00:25:39,330 --> 00:25:42,170
e então você pode adicionar o encadeamento diante.

491
00:25:42,170 --> 00:25:43,330
Todo mundo é clara?

492
00:25:43,330 --> 00:25:45,427
>> Este vai ser
uma das questões reais.

493
00:25:45,427 --> 00:25:48,010
Uma das mais importantes questões
você vai ter no seu pset

494
00:25:48,010 --> 00:25:51,340
é que você está indo para tentar criar
uma lista encadeada e as coisas de inserção

495
00:25:51,340 --> 00:25:53,340
mas depois é só perder o
resto de sua lista ligada.

496
00:25:53,340 --> 00:25:54,900
E você vai ser como eu
Não sei por que isso está acontecendo?

497
00:25:54,900 --> 00:25:58,040
E é uma dor de passar por
e pesquisar todos os seus ponteiros.

498
00:25:58,040 --> 00:26:02,100
>> E eu garanto que nesta pset,
escrever e desenhar esses nós fora

499
00:26:02,100 --> 00:26:03,344
vai ser muito, muito útil.

500
00:26:03,344 --> 00:26:06,010
Assim você pode manter completamente a noção
de onde todos os seus ponteiros são,

501
00:26:06,010 --> 00:26:08,540
o que está acontecendo de errado,
onde todos os seus nodos são,

502
00:26:08,540 --> 00:26:12,660
o que você precisa fazer para acessar ou
inserir ou excluir ou nenhum deles.

503
00:26:12,660 --> 00:26:14,550
Todo mundo bem com isso?

504
00:26:14,550 --> 00:26:15,050
Legal.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Então, se nós queria olhar para o código?

507
00:26:22,600 --> 00:26:24,470
Oh, eu não sei se nós
pode ver as-- OK, então

508
00:26:24,470 --> 00:26:27,940
no topo de tudo, é uma função
inserção nomeado onde queremos

509
00:26:27,940 --> 00:26:31,365
para inserir int n na lista ligada.

510
00:26:31,365 --> 00:26:32,740
Nós vamos caminhar por este.

511
00:26:32,740 --> 00:26:34,770
É um monte de código, um monte de nova sintaxe.

512
00:26:34,770 --> 00:26:36,220
Nós vamos ficar bem.

513
00:26:36,220 --> 00:26:39,120
>> Assim, no topo, sempre que
queremos criar nada

514
00:26:39,120 --> 00:26:42,380
o que precisamos de fazer, especialmente se você
deseja que ele não deve ser armazenado na pilha

515
00:26:42,380 --> 00:26:43,920
mas na pilha?

516
00:26:43,920 --> 00:26:45,460
Nós vamos para um malloc, certo?

517
00:26:45,460 --> 00:26:48,240
Então vamos criar um ponteiro.

518
00:26:48,240 --> 00:26:52,074
Nó, ponteiro, novas equals
malloc o tamanho de um nó

519
00:26:52,074 --> 00:26:53,740
porque queremos que nó a ser criado.

520
00:26:53,740 --> 00:26:56,720
Queremos que a quantidade de
memória que um nó ocupa

521
00:26:56,720 --> 00:26:59,300
a ser alocado para o
criação do novo nó.

522
00:26:59,300 --> 00:27:02,270
>> E então nós vamos verificar para
ver se é igual a novos iguais nulo.

523
00:27:02,270 --> 00:27:03,370
Lembre-se do que dissemos?

524
00:27:03,370 --> 00:27:06,470
Tudo o que você malloc,
o que você deve sempre fazer?

525
00:27:06,470 --> 00:27:09,490
Você deve sempre verificar para ver
se isso é ou não nulo.

526
00:27:09,490 --> 00:27:13,620
>> Por exemplo, se seu funcionamento
sistema foi completamente cheio,

527
00:27:13,620 --> 00:27:17,060
se você não tinha mais memória em
tudo e tentar malloc,

528
00:27:17,060 --> 00:27:18,410
ele iria retornar nulo para você.

529
00:27:18,410 --> 00:27:21,094
E por isso, se você tentar usá-lo
quando ele estava apontando para null,

530
00:27:21,094 --> 00:27:23,260
você não vai poder
para acessar essa informação.

531
00:27:23,260 --> 00:27:27,010
E assim, como tal, nós queríamos fazer
Certifique-se de que sempre que você está mallocing,

532
00:27:27,010 --> 00:27:30,500
você está sempre verificando se
que a memória dado a você é nulo.

533
00:27:30,500 --> 00:27:33,670
E se não é, então podemos passar
com o resto do nosso código.

534
00:27:33,670 --> 00:27:36,140
>> Então, nós estamos indo para
inicializar o novo nó.

535
00:27:36,140 --> 00:27:39,050
Nós vamos fazer nova n é igual a n.

536
00:27:39,050 --> 00:27:42,390
E então nós vamos fazer
definir novo o ponteiro na nova

537
00:27:42,390 --> 00:27:46,900
como nulo porque agora nós não
quer nada para ele para apontar para.

538
00:27:46,900 --> 00:27:48,755
Nós não temos nenhuma idéia de onde
ele vai colocá-lo,

539
00:27:48,755 --> 00:27:50,630
e, em seguida, se quisermos
inseri-lo na cabeça,

540
00:27:50,630 --> 00:27:53,820
então podemos atribuir novamente
o ponteiro para a cabeça.

541
00:27:53,820 --> 00:27:58,530
Será que todo mundo seguir a lógica
de onde isso está acontecendo?

542
00:27:58,530 --> 00:28:02,502
>> Tudo o que estamos fazendo é criar uma nova
nó, definir o ponteiro para null,

543
00:28:02,502 --> 00:28:04,210
e, em seguida, a reafectação
-lo para a cabeça se

544
00:28:04,210 --> 00:28:06,320
sabemos que queremos para inseri-lo na cabeça.

545
00:28:06,320 --> 00:28:09,420
E, em seguida, a cabeça vai
apontam para que o novo nó.

546
00:28:09,420 --> 00:28:11,060
Todo mundo bem com isso?

547
00:28:11,060 --> 00:28:12,380
>> Portanto, é um processo de duas etapas.

548
00:28:12,380 --> 00:28:14,760
Você tem que primeiro atribuir
o que quer que você está criando.

549
00:28:14,760 --> 00:28:18,260
Definir que ponteiro para o
referência, e então você

550
00:28:18,260 --> 00:28:21,400
pode tipo de dereference
o primeiro ponteiro

551
00:28:21,400 --> 00:28:22,972
e apontá-lo para o novo nó.

552
00:28:22,972 --> 00:28:25,680
Onde quer que você deseja inseri-lo,
que a lógica vai realizar verdadeiro.

553
00:28:25,680 --> 00:28:27,530
>> É uma espécie de como atribuir
variáveis ​​temporárias.

554
00:28:27,530 --> 00:28:28,700
Lembre-se, você tem
para se certificar de que você

555
00:28:28,700 --> 00:28:30,346
não perder de vista se você está trocando.

556
00:28:30,346 --> 00:28:33,470
Você quer ter certeza de que você tem um
variável temporária esse tipo de guarda

557
00:28:33,470 --> 00:28:35,620
o controle de onde essa coisa
é armazenada de modo que você

558
00:28:35,620 --> 00:28:41,190
não perdem qualquer valor no curso
de como mexer com ele.

559
00:28:41,190 --> 00:28:42,710
>> OK, então o código será aqui.

560
00:28:42,710 --> 00:28:45,020
Vocês vejam após a secção.

561
00:28:45,020 --> 00:28:48,060
Ele vai estar lá.

562
00:28:48,060 --> 00:28:50,280
>> Então eu acho que como é que
isso difere se quiséssemos

563
00:28:50,280 --> 00:28:52,300
inserir no meio ou no fim?

564
00:28:52,300 --> 00:28:57,892
Alguém tem uma idéia de qual é o
pseudocódigo como referência lógica

565
00:28:57,892 --> 00:29:00,350
que levaria se quiséssemos
para inseri-lo no meio?

566
00:29:00,350 --> 00:29:03,391
Então, se nós queria para inseri-lo no
cabeça, tudo o que fazemos é criar um novo nó.

567
00:29:03,391 --> 00:29:06,311
Nós definir o ponteiro de que
novo nó a tudo o que a cabeça,

568
00:29:06,311 --> 00:29:08,310
e, em seguida, vamos definir o cabeça
para o novo nó, certo?

569
00:29:08,310 --> 00:29:11,560
Se quiséssemos para inseri-lo no meio
da lista, o que teria que fazer?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> AUDIÊNCIA: É ainda faria
ser um processo semelhante

572
00:29:16,110 --> 00:29:19,114
de como a atribuição de ponteiro e
em seguida, atribuindo esse ponteiro,

573
00:29:19,114 --> 00:29:20,530
mas teríamos de encontrar lá.

574
00:29:20,530 --> 00:29:23,560
>> ANDI Peng: Exatamente, exatamente por isso
o mesmo processo, exceto você

575
00:29:23,560 --> 00:29:27,820
tem que localizar onde exatamente você
deseja que o novo ponteiro para entrar,

576
00:29:27,820 --> 00:29:44,790
por isso, se eu quero inserir em
no meio de ligado lista-- OK,

577
00:29:44,790 --> 00:29:46,370
vamos dizer que essa é a nossa lista ligada.

578
00:29:46,370 --> 00:29:49,500
Se queremos inseri-lo aqui,
vamos criar um novo nó.

579
00:29:49,500 --> 00:29:50,520
Nós estamos indo para malloc.

580
00:29:50,520 --> 00:29:52,220
Nós vamos criar um novo nó.

581
00:29:52,220 --> 00:29:55,940
Nós vamos atribuir o
ponteiro deste nó aqui.

582
00:29:55,940 --> 00:29:58,335
>> Mas o problema que difere
de onde a cabeça é

583
00:29:58,335 --> 00:30:00,490
é que nós sabíamos exatamente
onde está a cabeça.

584
00:30:00,490 --> 00:30:01,930
Foi à direita no primeiro, certo?

585
00:30:01,930 --> 00:30:04,870
Mas aqui nós temos que manter o controle
de onde estamos inserindo-o.

586
00:30:04,870 --> 00:30:07,930
Se estamos inserindo nosso
nó aqui, nós temos

587
00:30:07,930 --> 00:30:12,270
para se certificar de que o
anterior a este nó

588
00:30:12,270 --> 00:30:14,172
é aquele que atribui novamente o ponteiro.

589
00:30:14,172 --> 00:30:16,380
Então você tem que tipo de
manter o controle de duas coisas.

590
00:30:16,380 --> 00:30:19,420
Se você manter o controle de onde esta
nó atualmente está inserindo.

591
00:30:19,420 --> 00:30:23,280
Você também tem que manter o controle de onde
o nó anterior que você está olhando

592
00:30:23,280 --> 00:30:24,340
também estava lá.

593
00:30:24,340 --> 00:30:25,830
Todo mundo bem com isso?

594
00:30:25,830 --> 00:30:26,500
ESTÁ BEM.

595
00:30:26,500 --> 00:30:28,000
>> Como cerca de inserir no final?

596
00:30:28,000 --> 00:30:34,220
Se eu queria adicioná-lo aqui-- se eu queria
para adicionar um novo nó ao fim de uma lista,

597
00:30:34,220 --> 00:30:37,009
como eu poderia ir sobre como fazer isso?

598
00:30:37,009 --> 00:30:39,300
AUDIÊNCIA: Então, atualmente, a
do último apontado como nulo.

599
00:30:39,300 --> 00:30:40,960
ANDI Peng: Sim.

600
00:30:40,960 --> 00:30:43,560
Exatamente, por isso este
Atualmente é apontado saber,

601
00:30:43,560 --> 00:30:46,720
e então eu acho que, nesse sentido, é
muito fácil de adicionar ao fim de uma lista.

602
00:30:46,720 --> 00:30:51,810
Tudo que você tem a fazer é configurá-lo
igual a nulo e depois crescer.

603
00:30:51,810 --> 00:30:53,070
Bem ali, muito fácil.

604
00:30:53,070 --> 00:30:53,960
Muito simples.

605
00:30:53,960 --> 00:30:56,430
>> Muito semelhante ao
cabeça, mas logicamente você

606
00:30:56,430 --> 00:30:59,690
quer ter a certeza que os passos
você tomar para fazer nada disso,

607
00:30:59,690 --> 00:31:01,500
você está acompanhando.

608
00:31:01,500 --> 00:31:04,420
É muito fácil, no meio
do seu código, pego em,

609
00:31:04,420 --> 00:31:05,671
oh, eu tenho tantos ponteiros.

610
00:31:05,671 --> 00:31:07,461
Eu não sei onde
nada está apontando.

611
00:31:07,461 --> 00:31:09,170
Eu nem sei qual o nó em que estou.

612
00:31:09,170 --> 00:31:11,490
O que está acontecendo?

613
00:31:11,490 --> 00:31:13,620
>> Relaxe, acalme-se, tomar uma respiração profunda.

614
00:31:13,620 --> 00:31:15,530
Desenhe a sua lista ligada.

615
00:31:15,530 --> 00:31:18,800
Se você disser, eu sei onde exatamente
Eu preciso inserir isto em

616
00:31:18,800 --> 00:31:22,970
e eu sei exatamente como realocar o meu
ponteiros, muito, muito mais fácil de imaginar

617
00:31:22,970 --> 00:31:27,200
out-- muito, muito mais fácil de não
se perder nos erros do seu código.

618
00:31:27,200 --> 00:31:29,410
Todo mundo bem com isso?

619
00:31:29,410 --> 00:31:31,380
ESTÁ BEM.

620
00:31:31,380 --> 00:31:35,120
>> Então eu acho que um conceito que não tem
realmente falamos antes agora,

621
00:31:35,120 --> 00:31:38,131
e eu acho que você provavelmente
não vai encontrar muito yet--

622
00:31:38,131 --> 00:31:40,880
é uma espécie de um concept-- avançada
é que nós realmente temos um conjunto de dados

623
00:31:40,880 --> 00:31:43,900
estrutura chamada uma lista duplamente ligada.

624
00:31:43,900 --> 00:31:46,390
Então, como vocês podem ver,
tudo o que estamos fazendo é criar

625
00:31:46,390 --> 00:31:50,400
um valor real, um extra
ponteiro em cada uma de nossas nós

626
00:31:50,400 --> 00:31:52,660
que também aponta para o nó anterior.

627
00:31:52,660 --> 00:31:58,170
Portanto, não só temos o nosso
nodos apontar para a próxima.

628
00:31:58,170 --> 00:32:01,430
Eles também apontam para o anterior.

629
00:32:01,430 --> 00:32:04,310
Eu vou ignorar esses dois agora.

630
00:32:04,310 --> 00:32:06,740
>> Então você tem uma cadeia
que pode mover-se em ambos os sentidos,

631
00:32:06,740 --> 00:32:09,630
e então é um pouco mais fácil
a seguir logicamente junto.

632
00:32:09,630 --> 00:32:11,896
Como aqui, em vez de
manter o controle de, oh, I

633
00:32:11,896 --> 00:32:14,520
tem que saber que esse nó é
o que eu tenho que voltar a atribuir,

634
00:32:14,520 --> 00:32:17,532
Eu só posso ir aqui e
basta puxar o anterior.

635
00:32:17,532 --> 00:32:19,490
Então eu sei exatamente onde
que é, e então você

636
00:32:19,490 --> 00:32:21,130
não tem que atravessar a
totalidade da lista ligada.

637
00:32:21,130 --> 00:32:22,180
É um pouco mais fácil.

638
00:32:22,180 --> 00:32:24,960
>> Mas, como tal, você tem duplamente
a quantidade de ponteiros,

639
00:32:24,960 --> 00:32:26,960
que é o dobro da quantidade de memória.

640
00:32:26,960 --> 00:32:28,950
É um monte de ponteiros para acompanhar.

641
00:32:28,950 --> 00:32:32,140
É um pouco mais complexo, mas é
um pouco mais amigável, dependendo

642
00:32:32,140 --> 00:32:34,080
o que você está tentando realizar.

643
00:32:34,080 --> 00:32:36,910
>> Portanto, este tipo de dados
estrutura existe totalmente,

644
00:32:36,910 --> 00:32:40,280
ea estrutura para é muito, muito
simples, exceto tudo que você está tendo é,

645
00:32:40,280 --> 00:32:43,850
em vez de apenas um ponteiro para o próximo,
você também tem um ponteiro para anterior.

646
00:32:43,850 --> 00:32:45,940
Isso é tudo que a diferença era.

647
00:32:45,940 --> 00:32:47,740
Todo mundo bem com isso?

648
00:32:47,740 --> 00:32:48,240
Legal.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Tudo bem, então agora eu sou
para realmente passar, provavelmente,

651
00:32:53,280 --> 00:32:56,870
como 15 a 20 minutos ou a granel
do resto do tempo na secção

652
00:32:56,870 --> 00:32:58,360
falando de tabelas de hash.

653
00:32:58,360 --> 00:33:02,590
Como muitos de vocês
li pset5 especificação?

654
00:33:02,590 --> 00:33:03,620
Tudo bem, bom.

655
00:33:03,620 --> 00:33:06,160
Isso é mais elevado do que os 50% do normalmente.

656
00:33:06,160 --> 00:33:07,560
Está certo.

657
00:33:07,560 --> 00:33:10,345
>> Então, como vocês vão ver,
você é desafio em pset5

658
00:33:10,345 --> 00:33:16,790
será a implementação de um dicionário
onde você carregar mais de 140.000 palavras

659
00:33:16,790 --> 00:33:20,610
que nós damos-lhe e verificação ortográfica
contra todo o texto.

660
00:33:20,610 --> 00:33:22,580
Nós vamos dar-lhe aleatória
peças de literatura.

661
00:33:22,580 --> 00:33:23,520
Nós vamos dar-lhe The Odyssey.

662
00:33:23,520 --> 00:33:24,561
Nós vamos dar-lhe a Ilíada.

663
00:33:24,561 --> 00:33:26,350
Nós vamos dar-lhe Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> E seu desafio
será a de verificação ortográfica

665
00:33:28,220 --> 00:33:31,760
cada palavra em tudo
desses dicionários

666
00:33:31,760 --> 00:33:34,960
essencialmente com nosso corretor ortográfico.

667
00:33:34,960 --> 00:33:38,620
E por isso há poucas partes
de criar este pset,

668
00:33:38,620 --> 00:33:41,970
primeiro você quer ser
capaz de carregar, na verdade,

669
00:33:41,970 --> 00:33:43,970
todas as palavras em seu
dicionário, e então você

670
00:33:43,970 --> 00:33:45,530
quer ser capaz de
verificação ortográfica todos eles.

671
00:33:45,530 --> 00:33:48,780
E assim, como tal, você está indo para exigir
uma estrutura de dados que pode fazer isso rápido

672
00:33:48,780 --> 00:33:50,790
e eficientemente e de forma dinâmica.

673
00:33:50,790 --> 00:33:52,900
>> Então, eu suponho que o mais fácil
maneira de fazer isso, você

674
00:33:52,900 --> 00:33:55,010
provavelmente criar uma matriz, certo?

675
00:33:55,010 --> 00:33:58,910
A maneira mais fácil de armazenamento é você
pode criar uma matriz de 140.000 palavras

676
00:33:58,910 --> 00:34:03,400
e apenas colocá-los todos lá e
então atravessá-los por busca binária

677
00:34:03,400 --> 00:34:06,780
ou pelas selecções ou não--
Lamentamos que é a classificação.

678
00:34:06,780 --> 00:34:10,729
Você pode classificá-los e depois atravessá-los
por busca binária ou busca apenas linear

679
00:34:10,729 --> 00:34:13,730
e apenas as palavras finais, mas que
leva uma grande quantidade de memória,

680
00:34:13,730 --> 00:34:15,190
e não é muito eficiente.

681
00:34:15,190 --> 00:34:18,350
>> E assim nós vamos começar
falando sobre maneiras de fazer

682
00:34:18,350 --> 00:34:20,110
nosso tempo de funcionamento mais eficiente.

683
00:34:20,110 --> 00:34:23,190
E nosso objetivo é fazer com que
constante de tempo onde

684
00:34:23,190 --> 00:34:25,810
é quase como matrizes, onde
você tem acesso instantâneo.

685
00:34:25,810 --> 00:34:28,560
Se eu quisesse procurar qualquer coisa,
Eu quero ser capaz de apenas,

686
00:34:28,560 --> 00:34:30,810
crescimento, encontrá-lo exatamente, e puxe-o para fora.

687
00:34:30,810 --> 00:34:34,100
E assim uma estrutura na qual
nós vamos estar a tornar-se muito perto

688
00:34:34,100 --> 00:34:37,569
para acessar a constante
tempo, esse santo graal

689
00:34:37,569 --> 00:34:41,370
na programação da constante
tempo é chamado de tabela de hash.

690
00:34:41,370 --> 00:34:45,370
E assim por David mencionado anteriormente o
[Inaudível] um pouco na palestra,

691
00:34:45,370 --> 00:34:49,100
mas nós vamos realmente
mergulho em profundidade esta semana

692
00:34:49,100 --> 00:34:51,780
em um pedaço que está sobre
como uma tabela hash funciona.

693
00:34:51,780 --> 00:34:53,949
>> Assim, a maneira que um hash
obras de mesa, por exemplo,

694
00:34:53,949 --> 00:35:00,230
se eu queria guardar um monte de palavras, um
monte de palavras no idioma Inglês,

695
00:35:00,230 --> 00:35:02,940
Eu poderia, teoricamente, colocar
banana, maçã, kiwi, manga, par,

696
00:35:02,940 --> 00:35:04,980
e melão tudo em apenas uma matriz.

697
00:35:04,980 --> 00:35:07,044
Todos eles poderiam se encaixar e ser encontrar.

698
00:35:07,044 --> 00:35:09,210
Seria uma espécie de dor para
pesquisar e acesso,

699
00:35:09,210 --> 00:35:12,920
mas a maneira mais fácil de fazer isto é
que pode criar efectivamente uma estrutura

700
00:35:12,920 --> 00:35:15,680
chamado uma tabela hash onde nós hash.

701
00:35:15,680 --> 00:35:19,880
Corremos todos os nossos chaves através
uma função hash, uma equação,

702
00:35:19,880 --> 00:35:22,600
que transforma-los todos em
algum tipo de valor

703
00:35:22,600 --> 00:35:28,740
que então podemos armazenar em
essencialmente um array de lista ligada.

704
00:35:28,740 --> 00:35:32,570
>> E aqui, se quiséssemos
para armazenar palavras em inglês,

705
00:35:32,570 --> 00:35:37,250
Podemos potencialmente apenas, eu não
sabe, transformar todas as primeiras letras

706
00:35:37,250 --> 00:35:39,630
em algum tipo de um número.

707
00:35:39,630 --> 00:35:43,140
E assim, por exemplo, se eu quisesse
Um a ser sinônimo de apple--

708
00:35:43,140 --> 00:35:47,460
ou com o índice de 0, e
B a ser sinônimo de 1,

709
00:35:47,460 --> 00:35:51,030
nós podemos ter 26 entradas
que podem apenas armazenar

710
00:35:51,030 --> 00:35:53,610
todas as letras do
alfabeto que vamos começar.

711
00:35:53,610 --> 00:35:56,130
E então nós podemos ter
maçã no índice de 0.

712
00:35:56,130 --> 00:35:59,160
Podemos ter de banana no índice de
1, melão no índice de 2,

713
00:35:59,160 --> 00:36:00,540
e assim por diante.

714
00:36:00,540 --> 00:36:04,460
E, assim, se eu quisesse pesquisar
meu hash de mesa e acesso maçã,

715
00:36:04,460 --> 00:36:07,560
Eu sei que a Apple começa com
um A, e eu sei exatamente

716
00:36:07,560 --> 00:36:10,860
que deve ser eo hash
tabela no índice 0, pois

717
00:36:10,860 --> 00:36:13,620
da função atribuído anteriormente.

718
00:36:13,620 --> 00:36:16,572
>> Então, eu não sei, nós somos
um programa de usuário, onde

719
00:36:16,572 --> 00:36:18,780
você vai ser cobrado com
não arbitrarily-- arbitrariamente,

720
00:36:18,780 --> 00:36:22,530
com a tentativa de pensativamente
pensar em boas equações

721
00:36:22,530 --> 00:36:25,460
para ser capaz de se espalhar
fora todos os seus valores

722
00:36:25,460 --> 00:36:29,370
de uma maneira que eles podem acessar facilmente
-lo mais tarde com como uma equação

723
00:36:29,370 --> 00:36:31,130
que você, você mesmo, sabe.

724
00:36:31,130 --> 00:36:35,210
Assim, no sentido de se eu queria ir para
manga, eu sei, oh, ele começa com m.

725
00:36:35,210 --> 00:36:37,134
Deve ser no índice de 12.

726
00:36:37,134 --> 00:36:38,800
Eu não tenho a busca através de qualquer coisa.

727
00:36:38,800 --> 00:36:42,080
Eu sei exactly-- eu poderia apenas ir para
o índice de 12 e puxar isso.

728
00:36:42,080 --> 00:36:45,520
>> Todos clara sobre como um
A função da tabela hash funciona?

729
00:36:45,520 --> 00:36:48,380
É uma espécie de apenas uma matriz mais complexa.

730
00:36:48,380 --> 00:36:50,010
Isso é tudo o que é.

731
00:36:50,010 --> 00:36:51,630
ESTÁ BEM.

732
00:36:51,630 --> 00:36:57,690
>> Então eu acho que correr em
esta questão do que

733
00:36:57,690 --> 00:37:06,390
acontece se você tiver várias coisas
que dar-lhe o mesmo índice?

734
00:37:06,390 --> 00:37:10,570
Então, dizer que a nossa função, tudo o que
fez foi tomar essa primeira letra

735
00:37:10,570 --> 00:37:14,490
e transformar isso em um
respectivo índice 0 a 25.

736
00:37:14,490 --> 00:37:17,137
Isso é totalmente bem se
você só tem um de cada.

737
00:37:17,137 --> 00:37:18,970
Mas a segunda você começa
ter mais, você é

738
00:37:18,970 --> 00:37:20,910
vai ter o que é chamado uma colisão.

739
00:37:20,910 --> 00:37:25,580
>> Então, se eu tentar inserir enterrar em um hash
tabela que já tenha banana nele,

740
00:37:25,580 --> 00:37:27,870
o que vai acontecer quando
tentar inserir isso?

741
00:37:27,870 --> 00:37:30,930
Coisas ruins por causa da banana
já existe dentro do índice

742
00:37:30,930 --> 00:37:33,800
que você deseja armazená-lo em.

743
00:37:33,800 --> 00:37:35,560
Berry tipo de é como, ah, o que eu faço?

744
00:37:35,560 --> 00:37:37,080
Eu não sei para onde ir.

745
00:37:37,080 --> 00:37:38,410
Como posso resolver isso?

746
00:37:38,410 --> 00:37:41,150
>> E assim vocês vão tipo de
ver o que fazemos esta coisa complicada

747
00:37:41,150 --> 00:37:44,810
onde podemos tipo de verdade
criar lista ligada em nossas matrizes.

748
00:37:44,810 --> 00:37:46,840
E assim, a maneira mais fácil
para pensar sobre isso,

749
00:37:46,840 --> 00:37:50,830
tudo é uma tabela hash
matriz de listas ligadas.

750
00:37:50,830 --> 00:37:55,670
E assim, nesse sentido, você tem
esta bela matriz de ponteiros,

751
00:37:55,670 --> 00:37:58,740
e, em seguida, em cada ponteiro
esse valor, em que o índice,

752
00:37:58,740 --> 00:38:00,740
pode realmente apontar para outras coisas.

753
00:38:00,740 --> 00:38:05,720
E então você tem todos esses separado
cadeias saindo de uma grande matriz.

754
00:38:05,720 --> 00:38:07,960
>> E aqui, se eu
queria inserir baga,

755
00:38:07,960 --> 00:38:11,220
Eu sei, OK, eu estou indo para introduzir
-lo através de minha função hash.

756
00:38:11,220 --> 00:38:15,070
Eu vou acabar com o índice de
1, e então eu vou ser capaz de ter

757
00:38:15,070 --> 00:38:20,410
apenas um subconjunto menor da presente
gigante dicionário de 140.000 palavras.

758
00:38:20,410 --> 00:38:24,220
E então eu posso apenas olhar
através de 1/26 do que isso.

759
00:38:24,220 --> 00:38:27,910
>> E então eu só posso inserir
baga, quer antes ou depois da banana

760
00:38:27,910 --> 00:38:28,820
nesse caso?

761
00:38:28,820 --> 00:38:29,700
Depois, certo?

762
00:38:29,700 --> 00:38:33,920
E então você vai querer
inserir esse nó depois de banana,

763
00:38:33,920 --> 00:38:36,667
e então você vai para inserir
em que a cauda de lista ligada.

764
00:38:36,667 --> 00:38:38,500
Eu vou voltar
a este slide anterior,

765
00:38:38,500 --> 00:38:40,680
para que vocês possam ver como
função hash funciona.

766
00:38:40,680 --> 00:38:43,980
>> Então função hash é esta equação
que você está executando o seu tipo de entrada

767
00:38:43,980 --> 00:38:46,940
através de obter o que quer índice
pretende atribuir-lo para.

768
00:38:46,940 --> 00:38:51,130
E assim, neste exemplo, tudo o que queríamos
a fazer era tomar a primeira letra,

769
00:38:51,130 --> 00:38:55,890
transformar isso em um índice, então nós
pode armazenar que em nossa função hash.

770
00:38:55,890 --> 00:39:00,160
Tudo o que estamos fazendo aqui é que estamos
converter a primeira letra.

771
00:39:00,160 --> 00:39:04,770
Então KeyKey [0] é apenas a primeira letra
de qualquer seqüência que estamos tendo,

772
00:39:04,770 --> 00:39:05,720
estamos passando.

773
00:39:05,720 --> 00:39:09,740
Estamos convertendo que a superior, e
estamos subtraindo por letras maiúsculas A,

774
00:39:09,740 --> 00:39:11,740
assim tudo que está fazendo
está nos dando um número

775
00:39:11,740 --> 00:39:13,670
em que podemos botar nossos valores para.

776
00:39:13,670 --> 00:39:16,550
>> E então nós vamos
retornar de hash TAMANHO módulo.

777
00:39:16,550 --> 00:39:19,340
Seja muito, muito cuidado
porque, teoricamente, aqui

778
00:39:19,340 --> 00:39:21,870
o seu valor de hash pode ser infinita.

779
00:39:21,870 --> 00:39:23,660
Ele poderia simplesmente ir sobre e sobre e sobre.

780
00:39:23,660 --> 00:39:26,080
Pode haver alguma verdade,
realmente grande valor,

781
00:39:26,080 --> 00:39:29,849
mas porque sua tabela hash que
que você criou possui apenas 26 índices,

782
00:39:29,849 --> 00:39:31,890
você quer ter certeza de seu
modulusing para que você

783
00:39:31,890 --> 00:39:33,848
não run-- é o mesmo
coisa como seu queue--

784
00:39:33,848 --> 00:39:36,320
para que você não corra fora da
inferior de sua função hash.

785
00:39:36,320 --> 00:39:39,210
>> Você quer envolvê-la de volta ao redor
da mesma forma em [inaudível] quando

786
00:39:39,210 --> 00:39:41,750
você teve como um muito,
muito grande carta, você

787
00:39:41,750 --> 00:39:43,740
Não queria que isso
basta executar fora da final.

788
00:39:43,740 --> 00:39:46,948
Mesma coisa aqui, você quer certificar-se
ele não é executado fora da final por envolvimento

789
00:39:46,948 --> 00:39:48,330
em torno ao topo da mesa.

790
00:39:48,330 --> 00:39:50,530
Portanto, esta é apenas uma muito
função hash simples.

791
00:39:50,530 --> 00:39:56,570
Tudo o que fiz foi dar o primeiro
carta de tudo o que o nosso contributo foi

792
00:39:56,570 --> 00:40:01,660
e transformar isso em um índice que
poderíamos colocar em nossa tabela de hash.

793
00:40:01,660 --> 00:40:05,450
>> Sim, e assim como eu disse antes,
a maneira que nós resolver colisões

794
00:40:05,450 --> 00:40:09,330
em nosso hash de tabelas estão tendo,
o que chamamos de encadeamento.

795
00:40:09,330 --> 00:40:13,860
Então, se você tentar inserir múltiplo
palavras que começam com a mesma coisa,

796
00:40:13,860 --> 00:40:16,145
você vai ter um valor de hash.

797
00:40:16,145 --> 00:40:18,770
Abacate e maçã, se você tiver
executá-lo através de nossa função hash,

798
00:40:18,770 --> 00:40:21,450
vai dar-lhe a
mesmo número, o número de 0.

799
00:40:21,450 --> 00:40:24,550
E assim a nossa forma de resolver isso é
que podemos realmente tipo de vinculá-los

800
00:40:24,550 --> 00:40:27,010
juntos via listas ligadas.

801
00:40:27,010 --> 00:40:29,600
>> E assim, neste sentido,
vocês podem ver espécie

802
00:40:29,600 --> 00:40:32,640
de forma que as estruturas de dados
temos vindo a criação anteriormente

803
00:40:32,640 --> 00:40:35,870
como uma uva passa ligada lista espécie
de podem se unir em um só.

804
00:40:35,870 --> 00:40:38,860
E então você pode criar muito
estruturas de dados mais eficientes

805
00:40:38,860 --> 00:40:43,350
que pode lidar com grandes quantidades de
dados, que redimensionar dinamicamente dependendo

806
00:40:43,350 --> 00:40:44,870
de suas necessidades.

807
00:40:44,870 --> 00:40:45,620
Todo mundo é clara?

808
00:40:45,620 --> 00:40:47,580
Todos tipo de clara
sobre o que acontece aqui?

809
00:40:47,580 --> 00:40:52,110
>> Se eu quisesse insert-- o que é um
fruta que começa com, eu não sei,

810
00:40:52,110 --> 00:40:54,726
B, com excepção baga, banana.

811
00:40:54,726 --> 00:40:55,710
>> AUDIÊNCIA: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI Peng: Blackberry, amora.

813
00:40:57,910 --> 00:41:00,530
Onde é que blackberry aqui?

814
00:41:00,530 --> 00:41:04,251
Bem, nós realmente não ter resolvido
isso ainda, mas, teoricamente,

815
00:41:04,251 --> 00:41:06,250
se quiséssemos ter este
em ordem alfabética,

816
00:41:06,250 --> 00:41:07,944
onde deve ir blackberry?

817
00:41:07,944 --> 00:41:09,210
>> AUDIÊNCIA: [inaudível]

818
00:41:09,210 --> 00:41:11,100
>> ANDI Peng: Exatamente, após aqui, certo?

819
00:41:11,100 --> 00:41:14,950
Mas já que é muito difícil
reorder-- Eu acho que cabe a vocês.

820
00:41:14,950 --> 00:41:17,920
Vocês podem totalmente
implementar o que quiser.

821
00:41:17,920 --> 00:41:20,730
A maneira mais eficiente
de fazer isso, talvez,

822
00:41:20,730 --> 00:41:24,570
seria a de classificar sua ligado
lista em ordem alfabética,

823
00:41:24,570 --> 00:41:26,520
e então quando você está
inserção de coisas, você quer

824
00:41:26,520 --> 00:41:28,632
ter a certeza de inseri-los
em ordem alfabética

825
00:41:28,632 --> 00:41:30,590
para que, em seguida, quando você está
tentando procurá-los,

826
00:41:30,590 --> 00:41:32,410
você não tem que atravessar tudo.

827
00:41:32,410 --> 00:41:35,290
Você sabe exatamente onde
que é, e é mais fácil.

828
00:41:35,290 --> 00:41:39,100
>> Mas se você tipo de ter
coisas intercalado aleatoriamente,

829
00:41:39,100 --> 00:41:41,420
você ainda vai ter
para atravessá-lo de qualquer maneira.

830
00:41:41,420 --> 00:41:44,990
E então se eu queria apenas
inserir blackberry aqui

831
00:41:44,990 --> 00:41:47,470
e eu queria procurar
isso, eu sei, oh, blackberry

832
00:41:47,470 --> 00:41:52,012
deve começar com o índice de 1, então eu
saber instantaneamente basta pesquisar a 1.

833
00:41:52,012 --> 00:41:53,970
E então eu posso tipo de
atravessar a lista vinculada

834
00:41:53,970 --> 00:41:56,120
até eu chegar para o BlackBerry,
e entăo-- sim?

835
00:41:56,120 --> 00:41:59,550
>> Audiência: Se você está tentando create--
Eu acho que como este é um hash muito simples

836
00:41:59,550 --> 00:42:00,050
função.

837
00:42:00,050 --> 00:42:02,835
E se o que queríamos fazer
várias camadas de que, como o

838
00:42:02,835 --> 00:42:05,870
OK, nós queremos separar em
como todas as letras do alfabeto

839
00:42:05,870 --> 00:42:09,040
e depois novamente a gostar de outro conjunto
de letras do alfabeto em que,

840
00:42:09,040 --> 00:42:11,715
que estamos colocando como um hash
tabela dentro de uma tabela hash,

841
00:42:11,715 --> 00:42:13,256
ou como uma função dentro de uma função?

842
00:42:13,256 --> 00:42:14,880
Ou é isso--

843
00:42:14,880 --> 00:42:17,510
>> ANDI Peng: Então seu haxixe
function-- sua tabela hash

844
00:42:17,510 --> 00:42:19,360
pode ser tão grande quanto você quer que ele.

845
00:42:19,360 --> 00:42:21,930
Portanto, nesse sentido, pensei
era muito fácil, muito

846
00:42:21,930 --> 00:42:25,320
simples para mim com base apenas sorte
em cartas de a primeira palavra.

847
00:42:25,320 --> 00:42:28,690
E por isso há apenas 26 opções.

848
00:42:28,690 --> 00:42:32,650
Eu só pode obter 26 opções de
0-25 porque eles só podem

849
00:42:32,650 --> 00:42:36,510
começar de A a Z. Mas Se você queria
a acrescentar, talvez, mais complexidade

850
00:42:36,510 --> 00:42:39,260
ou mais rápido tempo de execução para o seu
tabela de hash, é absolutamente

851
00:42:39,260 --> 00:42:40,760
pode fazer todo tipo de coisas.

852
00:42:40,760 --> 00:42:43,330
Você pode fazer o seu próprio
equação que dá a você

853
00:42:43,330 --> 00:42:48,000
mais em sua distribuição
palavras, então quando você procura,

854
00:42:48,000 --> 00:42:49,300
ele vai ser mais rápido.

855
00:42:49,300 --> 00:42:52,100
>> É totalmente até vocês
como você deseja implementar isso.

856
00:42:52,100 --> 00:42:55,140
Pense nisso como apenas baldes.

857
00:42:55,140 --> 00:42:57,376
Se eu queria ter
26 baldes, eu vou

858
00:42:57,376 --> 00:42:59,420
para resolver as coisas para aqueles baldes.

859
00:42:59,420 --> 00:43:02,980
Mas eu vou ter um monte
de material em cada balde,

860
00:43:02,980 --> 00:43:05,890
por isso, se você quiser torná-lo
mais rápido e mais eficiente,

861
00:43:05,890 --> 00:43:07,190
deixe-me ter uma centena de baldes.

862
00:43:07,190 --> 00:43:09,290
>> Mas então você tem que descobrir uma
maneira de resolver as coisas para que eles sejam

863
00:43:09,290 --> 00:43:11,040
no balde adequada eles devem estar em.

864
00:43:11,040 --> 00:43:13,331
Mas então quando você realmente
quero olhar para esse balde,

865
00:43:13,331 --> 00:43:16,410
é muito mais rápido porque não há
menos coisas em cada balde.

866
00:43:16,410 --> 00:43:20,250
E então, sim, isso é verdade,
o truque para vocês em pset5

867
00:43:20,250 --> 00:43:22,360
é que você vai ser
desafiados a criar apenas

868
00:43:22,360 --> 00:43:26,170
qualquer que seja o mais eficiente
função que você pode pensar de ser

869
00:43:26,170 --> 00:43:28,520
capaz de armazenar e verificar esses valores.

870
00:43:28,520 --> 00:43:30,840
>> Totalmente até vocês
no entanto, você quer fazê-lo,

871
00:43:30,840 --> 00:43:32,229
mas isso é um ponto muito bom.

872
00:43:32,229 --> 00:43:34,520
Que o tipo de lógica você
quer começar a pensar em

873
00:43:34,520 --> 00:43:37,236
é, bem, por que não posso fazer mais baldes.

874
00:43:37,236 --> 00:43:39,527
E então eu tenho que procurar
menos coisas, e então talvez eu

875
00:43:39,527 --> 00:43:41,640
tem uma função hash diferente.

876
00:43:41,640 --> 00:43:45,500
>> Sim, há um monte de maneiras de fazer isso
pset, alguns são mais rápidos do que outros.

877
00:43:45,500 --> 00:43:50,630
Estou totalmente vai apenas ver como
rápido foi o mais rápido que vocês vão

878
00:43:50,630 --> 00:43:55,170
ser capaz de obter suas funções para trabalhar.

879
00:43:55,170 --> 00:43:58,176
OK, todos em bom
encadeamento e hash tabelas?

880
00:43:58,176 --> 00:44:00,800
É realmente como uma forma muito simples
conceito, se você pensar sobre isso.

881
00:44:00,800 --> 00:44:05,160
Tudo o que é separar o que quer
suas entradas estão em baldes,

882
00:44:05,160 --> 00:44:10,670
classificando-os, em seguida, procura o
lista que não está associado.

883
00:44:10,670 --> 00:44:11,852
>> Legal.

884
00:44:11,852 --> 00:44:18,160
Tudo bem, agora nós temos um tipo diferente
de estrutura de dados que é chamado de uma árvore.

885
00:44:18,160 --> 00:44:20,850
Vamos seguir em frente e falar sobre tentativas
que são distintamente diferentes,

886
00:44:20,850 --> 00:44:22,330
mas na mesma categoria.

887
00:44:22,330 --> 00:44:29,010
Essencialmente, toda a árvore é uma vez
de organização de dados na forma linear

888
00:44:29,010 --> 00:44:32,560
que uma tabela hash does-- você
sabe, ele tem um superior e um inferior

889
00:44:32,560 --> 00:44:37,900
e, em seguida, você tipo de ligação fora de um ele--
árvore tem um top que você chamar a raiz,

890
00:44:37,900 --> 00:44:40,220
e em seguida, ele tem as folhas toda em torno dele.

891
00:44:40,220 --> 00:44:42,390
>> E assim tudo que você tem aqui
é apenas o nó superior

892
00:44:42,390 --> 00:44:45,980
que aponta para outros nós, que pontos
para mais nós, e assim por diante e assim por diante.

893
00:44:45,980 --> 00:44:48,130
E assim você só tem ramos de divisão.

894
00:44:48,130 --> 00:44:53,255
É apenas uma maneira diferente de organizar
dados, e porque nós o chamamos de uma árvore,

895
00:44:53,255 --> 00:44:56,270
vocês só-- é apenas
modelado para se parecer com uma árvore.

896
00:44:56,270 --> 00:44:57,670
É por isso que nós o chamamos de árvores.

897
00:44:57,670 --> 00:44:59,370
>> Tabela de hash parece uma tabela.

898
00:44:59,370 --> 00:45:01,310
Uma árvore apenas se parece com uma árvore.

899
00:45:01,310 --> 00:45:03,300
Tudo o que é um separado
forma de organizar os nós

900
00:45:03,300 --> 00:45:06,020
dependendo de quais são suas necessidades.

901
00:45:06,020 --> 00:45:11,810
>> Então você tem uma raiz e
então você tem folhas.

902
00:45:11,810 --> 00:45:15,380
A maneira que nós podemos particularmente
pensar sobre isso é uma árvore binária,

903
00:45:15,380 --> 00:45:18,150
uma árvore binária é apenas um
tipo específico de uma árvore

904
00:45:18,150 --> 00:45:22,450
onde cada nó únicos pontos
a, no máximo, dois outros nós.

905
00:45:22,450 --> 00:45:25,434
E por isso aqui você tem distintas
simetria em sua árvore

906
00:45:25,434 --> 00:45:28,600
que torna mais fácil tipo de olhar
em que os valores que são, porque então você

907
00:45:28,600 --> 00:45:30,150
ter sempre um esquerdo ou direito.

908
00:45:30,150 --> 00:45:33,150
Nunca há como uma terceira esquerda de
a esquerda ou um quarto da esquerda.

909
00:45:33,150 --> 00:45:36,358
É só você tem uma esquerda e uma direita
e você pode procurar qualquer um dos dois.

910
00:45:36,358 --> 00:45:38,980
E assim por que isso é útil?

911
00:45:38,980 --> 00:45:40,980
A maneira que este é
é útil se você está procurando

912
00:45:40,980 --> 00:45:42,890
a busca através de valores, certo?

913
00:45:42,890 --> 00:45:45,640
Em vez de implementar binário
pesquisar em uma matriz de erro,

914
00:45:45,640 --> 00:45:49,260
se você queria ser capaz de inserir os nós
e tirar os nós à vontade e também

915
00:45:49,260 --> 00:45:52,185
preservar a pesquisa
capacidades de busca binária.

916
00:45:52,185 --> 00:45:54,560
Assim, deste modo, nós somos tipo de
tricking-- lembro quando nós

917
00:45:54,560 --> 00:45:56,530
disse listas ligadas não posso busca binária?

918
00:45:56,530 --> 00:46:01,700
Estamos tipo de criação de uma estrutura de dados
que truques que em trabalhar.

919
00:46:01,700 --> 00:46:05,034
>> E isso porque listas ligadas são lineares,
eles só ligar um após o outro.

920
00:46:05,034 --> 00:46:06,950
Podemos tipo de ter
diferente tipo de ponteiros

921
00:46:06,950 --> 00:46:09,408
que apontam para diferentes nós
que pode nos ajudar com a pesquisa.

922
00:46:09,408 --> 00:46:12,590
E aqui, se eu quisesse
ter uma árvore de busca binária,

923
00:46:12,590 --> 00:46:14,090
Eu sei que o meu meio se 55.

924
00:46:14,090 --> 00:46:18,280
Eu só vou criar esse
como meu meio, como a minha raiz,

925
00:46:18,280 --> 00:46:20,770
e então eu vou ter
valores girar fora dele.

926
00:46:20,770 --> 00:46:25,610
>> Então, aqui, se eu vou procurar
o valor de 66, eu posso começar a 55.

927
00:46:25,610 --> 00:46:27,310
É 66 maior do que 55?

928
00:46:27,310 --> 00:46:30,970
Sim, é, então eu sei que mus pesquisa
i n o ponteiro direita da árvore.

929
00:46:30,970 --> 00:46:32,440
Eu vou para 77.

930
00:46:32,440 --> 00:46:35,367
OK, é menos do que 66 ou maior do que 77?

931
00:46:35,367 --> 00:46:37,950
É menos do que, por isso, você sabe, oh,
que tem de ser o nó à esquerda.

932
00:46:37,950 --> 00:46:41,410
>> E então aqui estamos tipo de preservação
todas as grandes coisas sobre arrays,

933
00:46:41,410 --> 00:46:44,420
assim como redimensionamento dinâmico
de objetos, sendo

934
00:46:44,420 --> 00:46:49,530
capaz de inserir e excluir à vontade,
sem ter que se preocupar com o fixo

935
00:46:49,530 --> 00:46:50,370
quantidade de espaço.

936
00:46:50,370 --> 00:46:52,820
Nós ainda preservar todos
aquelas coisas maravilhosas

937
00:46:52,820 --> 00:46:57,140
enquanto também é capaz de preservar a
log e tempo de busca binária pesquisa

938
00:46:57,140 --> 00:47:00,450
que nós só anteriormente
capaz de obter uma frase.

939
00:47:00,450 --> 00:47:06,310
>> Estrutura de dados legal, tipo de
complexo de implementar, o nó.

940
00:47:06,310 --> 00:47:08,311
Como você pode ver, tudo o que
representa a estrutura do nó

941
00:47:08,311 --> 00:47:10,143
é que você tem uma esquerda
e um ponteiro direito.

942
00:47:10,143 --> 00:47:11,044
Isso é tudo o que é.

943
00:47:11,044 --> 00:47:12,960
Então, ao invés de apenas
Tendo um X ou uma anterior.

944
00:47:12,960 --> 00:47:15,920
Você tem uma esquerda ou a direita, e, em seguida,
você pode tipo de ligá-los juntos

945
00:47:15,920 --> 00:47:16,836
no entanto você escolhe assim.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, nós estamos indo realmente
basta tirar alguns minutos.

948
00:47:24,270 --> 00:47:25,790
Então vamos voltar aqui.

949
00:47:25,790 --> 00:47:28,270
Como eu disse anteriormente,
Eu meio que explicou

950
00:47:28,270 --> 00:47:31,520
a lógica por trás de como nós
iria procurar por isso.

951
00:47:31,520 --> 00:47:33,860
Nós estamos indo para tentar
pseudocoding este para fora para ver

952
00:47:33,860 --> 00:47:38,000
se podemos aplicar o tipo de
mesma lógica de busca binária

953
00:47:38,000 --> 00:47:40,055
a um tipo diferente de estrutura de dados.

954
00:47:40,055 --> 00:47:45,049
Se vocês querem tomar como um casal
minutos para apenas pensar sobre isso.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
ESTÁ BEM.

957
00:48:46,925 --> 00:48:51,407
Tudo bem, eu vou
na verdade, apenas dar-lhe as-- não,

958
00:48:51,407 --> 00:48:52,990
vamos falar sobre o pseudocódigo primeiro.

959
00:48:52,990 --> 00:48:56,580
Então, alguém quer
para dar uma facada em que

960
00:48:56,580 --> 00:49:02,100
a primeira coisa que você quer fazer quando
você está começando a pesquisa é?

961
00:49:02,100 --> 00:49:04,460
Se nós estamos procurando
o valor de 66, o que é

962
00:49:04,460 --> 00:49:07,940
a primeira coisa que queremos fazer, se
queremos Pesquisa Binária esta árvore?

963
00:49:07,940 --> 00:49:10,760
>> AUDIÊNCIA: Você quer olhar direito
e olhar esquerda e ver [inaudível]

964
00:49:10,760 --> 00:49:11,230
maior número.

965
00:49:11,230 --> 00:49:12,271
>> ANDI Peng: Sim, exatamente.

966
00:49:12,271 --> 00:49:15,350
Então, você vai olhar para a sua raiz.

967
00:49:15,350 --> 00:49:18,180
Há muitas maneiras que você pode chamar
ele, seu nó pai pessoas dizem.

968
00:49:18,180 --> 00:49:21,317
Eu gosto de dizer porque raiz
que é como a raiz da árvore.

969
00:49:21,317 --> 00:49:23,400
Você vai olhar para
o nó raiz, e você está

970
00:49:23,400 --> 00:49:26,940
vai ver é 66 maior
que ou menor do que 55.

971
00:49:26,940 --> 00:49:30,360
E se é maior do que, bem, é
superior, onde é que vamos querer olhar?

972
00:49:30,360 --> 00:49:32,000
Aonde queremos procurar agora, certo?

973
00:49:32,000 --> 00:49:34,340
Queremos procurar o
metade direita da árvore.

974
00:49:34,340 --> 00:49:38,390
>> Portanto, temos, convenientemente, um
ponteiro que aponta para a direita.

975
00:49:38,390 --> 00:49:44,325
E então podemos definir
nossa nova raiz para ser 77.

976
00:49:44,325 --> 00:49:46,450
Nós podemos apenas ir para onde quer
o ponteiro está apontando.

977
00:49:46,450 --> 00:49:49,100
Bem, oh, aqui estamos começando
aos 77 anos, e nós podemos apenas

978
00:49:49,100 --> 00:49:51,172
fazer isso de forma recursiva novamente e novamente.

979
00:49:51,172 --> 00:49:52,880
Desta forma, você meio
de ter uma função.

980
00:49:52,880 --> 00:49:57,430
Você tem uma maneira de pesquisar que você
pode apenas repetir mais e mais e mais,

981
00:49:57,430 --> 00:50:02,720
dependendo de onde você quer olhar
até finalmente chegar ao valor

982
00:50:02,720 --> 00:50:04,730
que você está procurando.

983
00:50:04,730 --> 00:50:05,230
Faz sentido?

984
00:50:05,230 --> 00:50:07,800
>> Estou prestes a mostrar-lhe o real
código, e é um monte de código.

985
00:50:07,800 --> 00:50:08,674
Não há necessidade de assustar.

986
00:50:08,674 --> 00:50:09,910
Vamos falar com ele.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Na verdade não.

989
00:50:14,020 --> 00:50:15,061
Isso foi apenas pseudocódigo.

990
00:50:15,061 --> 00:50:17,860
OK, isso foi apenas o pseudocódigo,
que é um pouco complexo,

991
00:50:17,860 --> 00:50:19,751
mas é totalmente bom.

992
00:50:19,751 --> 00:50:21,000
Todo mundo seguindo ao longo aqui?

993
00:50:21,000 --> 00:50:24,260
Se a raiz é nulo, o retorno
falso, porque isso significa

994
00:50:24,260 --> 00:50:26,850
você não tem sequer qualquer coisa lá.

995
00:50:26,850 --> 00:50:31,376
>> Se raiz n é o valor, assim que se
acontece a ser o que você está olhando,

996
00:50:31,376 --> 00:50:34,000
então você está indo para retornar true
porque você sabe que você encontrou.

997
00:50:34,000 --> 00:50:36,250
Mas, se o valor for inferior
de raiz n, você é

998
00:50:36,250 --> 00:50:38,332
vai procurar a esquerda
criança ou a folha esquerda,

999
00:50:38,332 --> 00:50:39,540
tudo o que você quiser chamá-lo.

1000
00:50:39,540 --> 00:50:41,750
E se o valor for superior a raiz,
você está indo para procurar a árvore direita,

1001
00:50:41,750 --> 00:50:44,610
em seguida, basta executar a função
através de pesquisa novamente.

1002
00:50:44,610 --> 00:50:48,037
>> E se a raiz é nulo, para que aquele
Significa que você chegou ao fim?

1003
00:50:48,037 --> 00:50:50,120
Isso significa que você não tem nenhuma
mais mais folhas de pesquisa,

1004
00:50:50,120 --> 00:50:52,230
então você sabe, oh, I
acho que não é aqui

1005
00:50:52,230 --> 00:50:55,063
porque depois que eu olhei através
a coisa toda e não é aqui,

1006
00:50:55,063 --> 00:50:56,930
ele só poderia não estar aqui.

1007
00:50:56,930 --> 00:50:58,350
>> Isso faz sentido para todo mundo?

1008
00:50:58,350 --> 00:51:03,230
Então, é como busca binária preservação
as capacidades de listas ligadas.

1009
00:51:03,230 --> 00:51:09,200
Arrefecer, e de modo que o segundo tipo
de estrutura de dados que vocês

1010
00:51:09,200 --> 00:51:13,180
pode tentar implementar em seu pset,
você só tem que escolher um método.

1011
00:51:13,180 --> 00:51:19,430
Mas talvez um método alternativo para
a tabela hash é o que chamamos um trie.

1012
00:51:19,430 --> 00:51:24,080
>> Tudo é um trie é um
tipo específico de árvore que

1013
00:51:24,080 --> 00:51:28,600
tem valores que vão para outros valores.

1014
00:51:28,600 --> 00:51:31,450
Então, ao invés de ter um binário
árvore no sentido de que apenas um

1015
00:51:31,450 --> 00:51:35,940
coisa pode apontar para dois, você pode ter
uma coisa aponte para muitas, muitas coisas.

1016
00:51:35,940 --> 00:51:39,450
Você tem basicamente matrizes
dentro do qual você armazena

1017
00:51:39,450 --> 00:51:41,790
ponteiros que apontam para outras matrizes.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Assim, o nó de como nós
definiria um trie

1020
00:51:49,460 --> 00:51:52,590
é que nós queremos ter um
Booleano, palavra de c, certo?

1021
00:51:52,590 --> 00:51:54,920
Assim, o nó é booleano
como verdadeira ou falsa,

1022
00:51:54,920 --> 00:51:58,490
em primeiro lugar, à frente de
essa matriz, isso é uma palavra?

1023
00:51:58,490 --> 00:52:03,620
Em segundo lugar, você quer ter ponteiros
a tudo o que o resto deles são.

1024
00:52:03,620 --> 00:52:07,470
Um pouco complexo, um pouco abstrato, mas
Vou explicar o que tudo isso significa.

1025
00:52:07,470 --> 00:52:13,800
>> Então, aqui, no topo, se você
tenho uma matriz já declarou,

1026
00:52:13,800 --> 00:52:17,040
um nó onde você tem um valor booleano
valor armazenado na frente

1027
00:52:17,040 --> 00:52:19,490
que lhe diz é esta uma palavra?

1028
00:52:19,490 --> 00:52:20,520
Não é esta uma palavra?

1029
00:52:20,520 --> 00:52:23,240
E então você tem o
resto de sua matriz que

1030
00:52:23,240 --> 00:52:26,040
na verdade, armazena todas as
possibilidades do que poderia ser.

1031
00:52:26,040 --> 00:52:28,660
Assim, por exemplo, como
no topo você tem

1032
00:52:28,660 --> 00:52:32,140
a primeira coisa que diz verdadeira ou
falso, sim ou não, esta é uma palavra.

1033
00:52:32,140 --> 00:52:38,130
>> E então você tem de 0 a 26 de
as cartas que você pode armazenar.

1034
00:52:38,130 --> 00:52:42,790
Se eu quisesse pesquisar aqui
para morcego, eu ir para o topo

1035
00:52:42,790 --> 00:52:49,200
e eu olho para B. Acho B na minha
array, e então eu sei, OK, é uma palavra B?

1036
00:52:49,200 --> 00:52:53,010
B não é uma palavra, de modo que assim
Devo continuar pesquisando.

1037
00:52:53,010 --> 00:52:56,410
Eu vou de B, e eu olho para o
ponteiro que aponta para B

1038
00:52:56,410 --> 00:53:00,900
e eu vejo outro conjunto de informações,
a mesma estrutura que tínhamos antes.

1039
00:53:00,900 --> 00:53:05,240
>> E aqui-- oh, o próximo
carta em [inaudível] é A.

1040
00:53:05,240 --> 00:53:07,210
Então, nós olhamos nesse array.

1041
00:53:07,210 --> 00:53:10,860
Nós encontramos o oitavo valor,
e, depois, olhar para ver, oh,

1042
00:53:10,860 --> 00:53:12,840
hey, que é uma palavra, é B-A uma palavra?

1043
00:53:12,840 --> 00:53:13,807
Não é uma palavra.

1044
00:53:13,807 --> 00:53:14,890
Nós temos que continuar procurando.

1045
00:53:14,890 --> 00:53:17,850
>> E então olhamos para onde
o ponteiro de pontos A,

1046
00:53:17,850 --> 00:53:21,130
e aponta para uma outra maneira em
que temos mais valor armazenado.

1047
00:53:21,130 --> 00:53:24,150
E, eventualmente, temos de
B-A-T, o que é uma palavra.

1048
00:53:24,150 --> 00:53:25,970
E assim na próxima vez
você olha, você está indo

1049
00:53:25,970 --> 00:53:30,850
para ter esse cheque de, sim,
esta função booleana é verdadeira.

1050
00:53:30,850 --> 00:53:35,450
E assim, no sentido de que estamos espécie
de ter uma árvore com matrizes.

1051
00:53:35,450 --> 00:53:39,890
>> Então você pode tipo de busca para baixo.

1052
00:53:39,890 --> 00:53:43,650
Ao invés de uma função hash e
atribuindo valores de lista ligada,

1053
00:53:43,650 --> 00:53:49,190
você pode simplesmente implementar um
trie que procura downwords.

1054
00:53:49,190 --> 00:53:50,850
Realmente, realmente complicado coisas.

1055
00:53:50,850 --> 00:53:54,060
Não é fácil pensar, porque eu sou como
cuspindo tantas estruturas de dados para fora

1056
00:53:54,060 --> 00:53:58,710
em você, mas como todo tipo de
entender como a lógica de tudo isto funciona?

1057
00:53:58,710 --> 00:54:01,920
>> OK legal.

1058
00:54:01,920 --> 00:54:05,600
Assim B-A-T e, em seguida
você vai procurar.

1059
00:54:05,600 --> 00:54:07,940
A próxima vez que você está indo
para ver, oh, hey, é verdade,

1060
00:54:07,940 --> 00:54:09,273
assim, eu sei que isso deve ser uma palavra.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Mesma coisa para jardim zoológico.

1063
00:54:13,770 --> 00:54:17,960
Então aqui é a coisa certa agora, se nós
queria procurar jardim zoológico, agora,

1064
00:54:17,960 --> 00:54:20,780
Atualmente não é um jardim zoológico
palavra em nosso dicionário

1065
00:54:20,780 --> 00:54:25,300
porque, como vocês podem ver, o
o primeiro lugar que temos um booleano

1066
00:54:25,300 --> 00:54:28,590
return true é no final de zoom.

1067
00:54:28,590 --> 00:54:30,430
Temos Z-O-O-H.

1068
00:54:30,430 --> 00:54:33,900
>> E aqui, nós não realmente ter
a palavra, jardim zoológico, no nosso dicionário

1069
00:54:33,900 --> 00:54:36,070
porque esta caixa de seleção não está marcada.

1070
00:54:36,070 --> 00:54:39,540
Assim, o computador não faz
sei que zoo é uma palavra

1071
00:54:39,540 --> 00:54:42,430
porque a maneira que nós temos
armazenados, só um zoom aqui

1072
00:54:42,430 --> 00:54:44,920
na verdade tem um valor booleano
que tem sido virou verdade.

1073
00:54:44,920 --> 00:54:49,380
Portanto, se queremos inserir o
palavra, jardim zoológico, em nosso dicionário,

1074
00:54:49,380 --> 00:54:51,770
como é que nós vamos fazer sobre isso?

1075
00:54:51,770 --> 00:54:55,960
O que temos que fazer para garantir que a nossa
computador sabe que Z-O-O é uma palavra

1076
00:54:55,960 --> 00:54:58,130
e não a primeira palavra é Z-O-O-H?

1077
00:54:58,130 --> 00:54:59,360
>> AUDIÊNCIA: [inaudível]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI Peng: Exatamente, nós
quer ter a certeza de que este

1079
00:55:01,450 --> 00:55:07,890
aqui, que é valor booleano
verificado fora que é verdade.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, em seguida, vamos verificar que,
por isso sabemos exatamente, hey, jardim zoológico é uma palavra.

1081
00:55:13,297 --> 00:55:15,380
Eu vou dizer a
computador que é uma palavra tão

1082
00:55:15,380 --> 00:55:18,000
que quando o computador verifica,
ele sabe que zoo é uma palavra.

1083
00:55:18,000 --> 00:55:21,269
>> Porque lembre-se todos estes dados
estruturas, é muito fácil para nós

1084
00:55:21,269 --> 00:55:22,310
quer dizer, oh, morcego é uma palavra.

1085
00:55:22,310 --> 00:55:22,851
Zoo é uma palavra.

1086
00:55:22,851 --> 00:55:23,611
Zoom é uma palavra.

1087
00:55:23,611 --> 00:55:25,860
Mas quando você está construindo,
o computador não tem idéia.

1088
00:55:25,860 --> 00:55:28,619
>> Então você tem que dizer a ele exatamente
em que ponto é esta uma palavra?

1089
00:55:28,619 --> 00:55:29,910
Em que ponto é que nem uma palavra?

1090
00:55:29,910 --> 00:55:31,784
E em que ponto I
precisa procurar coisas,

1091
00:55:31,784 --> 00:55:34,000
e em que ponto eu preciso ir em seguida?

1092
00:55:34,000 --> 00:55:37,010
Todos clara de que?

1093
00:55:37,010 --> 00:55:39,540
Legal.

1094
00:55:39,540 --> 00:55:42,530
>> E então vem o
problema de como seria de nós

1095
00:55:42,530 --> 00:55:45,560
ir sobre como inserir algo
que, na verdade, não está lá?

1096
00:55:45,560 --> 00:55:49,090
Então vamos dizer que queremos inserir
a palavra, banho, em nossa trie.

1097
00:55:49,090 --> 00:55:53,589
Como vocês podem ver como actualmente
tudo o que temos agora é B-A-T,

1098
00:55:53,589 --> 00:55:55,630
e esta nova estrutura de dados
lá tinha uma caneca que

1099
00:55:55,630 --> 00:55:59,740
apontou para nula porque assumimos
que, oh, não há palavras após B-A-T,

1100
00:55:59,740 --> 00:56:02,530
por que precisamos para manter
ter as coisas depois que T.

1101
00:56:02,530 --> 00:56:06,581
>> Mas o problema surge se você
quero ter uma palavra que vem depois

1102
00:56:06,581 --> 00:56:07,080
a T.

1103
00:56:07,080 --> 00:56:09,500
Se você tiver banheira, você está
vai querer um direito H.

1104
00:56:09,500 --> 00:56:13,290
E assim, a maneira que nós estamos indo para fazer isso é
vamos criar um nó separado.

1105
00:56:13,290 --> 00:56:16,840
Nós não vamos colocar qualquer quantidade
de memória para esta nova matriz,

1106
00:56:16,840 --> 00:56:20,720
e vamos voltar a atribuir ponteiros.

1107
00:56:20,720 --> 00:56:22,947
>> Nós vamos atribuir o
H, Primeiro de tudo, este nulo,

1108
00:56:22,947 --> 00:56:24,030
nós estamos indo para se livrar.

1109
00:56:24,030 --> 00:56:26,590
Nós vamos ter
os para baixo ponto H.

1110
00:56:26,590 --> 00:56:30,600
Se vemos um H, queremos que
para ir para outro lugar.

1111
00:56:30,600 --> 00:56:33,910
>> Em aqui, então podemos marcar sim.

1112
00:56:33,910 --> 00:56:38,170
Se nós batemos um H após o T, oh,
então sabemos que esta é uma palavra.

1113
00:56:38,170 --> 00:56:41,110
O booleano vai retornar true.

1114
00:56:41,110 --> 00:56:42,950
Todos clara sobre como isso aconteceu?

1115
00:56:42,950 --> 00:56:45,110
ESTÁ BEM.

1116
00:56:45,110 --> 00:56:47,214
>> Assim, essencialmente, todos
estas estruturas de dados

1117
00:56:47,214 --> 00:56:50,130
que temos ido mais hoje, eu tenho
ido sobre eles muito, muito rapidamente

1118
00:56:50,130 --> 00:56:52,192
e em que não mais
detalhe, e isso é OK.

1119
00:56:52,192 --> 00:56:53,900
Uma vez que você começar a brincar
com ele, você poderá

1120
00:56:53,900 --> 00:56:55,733
manter o controle de onde
Todos os ponteiros são,

1121
00:56:55,733 --> 00:56:58,060
o que está acontecendo em sua
estruturas de dados, et cetera.

1122
00:56:58,060 --> 00:56:59,810
Eles vão ser muito útil,
e cabe a você

1123
00:56:59,810 --> 00:57:03,890
caras para descobrir como totalmente fora
você deseja implementar coisas.

1124
00:57:03,890 --> 00:57:07,650
>> E assim PSet4, de 5-- oh, isso é errado.

1125
00:57:07,650 --> 00:57:10,140
Pset5 é erros de ortografia.

1126
00:57:10,140 --> 00:57:13,710
Como eu disse antes, você vai, uma vez
novamente, baixar o código fonte de nós.

1127
00:57:13,710 --> 00:57:16,210
Não vai ser de três principal
coisas que você vai ser o download.

1128
00:57:16,210 --> 00:57:18,470
Você vai baixar dicionários,
kers e textos.

1129
00:57:18,470 --> 00:57:21,660
>> Todas essas coisas são são
quer dicionários de palavras

1130
00:57:21,660 --> 00:57:25,190
que nós queremos que você vá
ou teste de informações

1131
00:57:25,190 --> 00:57:26,930
que nós queremos que você verificação ortográfica.

1132
00:57:26,930 --> 00:57:29,670
E assim os dicionários
nós damos-lhe vão

1133
00:57:29,670 --> 00:57:34,870
para dar-lhe palavras reais que queremos
você armazene alguma forma em uma forma que é

1134
00:57:34,870 --> 00:57:36,530
mais eficiente do que uma matriz.

1135
00:57:36,530 --> 00:57:38,470
E, em seguida, os textos são
vai ser o que nós somos

1136
00:57:38,470 --> 00:57:43,900
pedindo-lhe para soletrar verifique se
todas as palavras são palavras reais lá.

1137
00:57:43,900 --> 00:57:47,970
>> E assim os três blocos de
programas que nós vamos dar-lhe

1138
00:57:47,970 --> 00:57:51,130
são chamados dictionary.c,
dictionary.h, e speller.c.

1139
00:57:51,130 --> 00:57:56,500
E assim todo o dictionary.c faz é
o que você está convidado a implementar.

1140
00:57:56,500 --> 00:57:57,880
Ele carrega palavras.

1141
00:57:57,880 --> 00:58:02,000
Ele ortográfico verifica-los, e isso torna-se de
que tudo está inserido corretamente.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h é apenas um arquivo de biblioteca
que declara todas essas funções.

1143
00:58:05,180 --> 00:58:07,650
E speller.c, nós vamos dar-lhe.

1144
00:58:07,650 --> 00:58:09,290
Você não precisa modificar nada disso.

1145
00:58:09,290 --> 00:58:14,290
Todos speller.c faz é tomar que,
carrega-lo, verifica a velocidade do mesmo,

1146
00:58:14,290 --> 00:58:19,190
testa o valor de referência de como como
rapidamente você é capaz de fazer as coisas.

1147
00:58:19,190 --> 00:58:20,410
>> É um verificador ortográfico.

1148
00:58:20,410 --> 00:58:23,920
Apenas não mexer com isso, mas fazer
certeza que você entende o que está fazendo.

1149
00:58:23,920 --> 00:58:28,090
Nós usamos uma função chamada getrusage que
testa o desempenho do seu feitiço

1150
00:58:28,090 --> 00:58:28,590
verificador.

1151
00:58:28,590 --> 00:58:32,200
Tudo que faz é basicamente testar a
tempo de tudo em seu dicionário,

1152
00:58:32,200 --> 00:58:33,680
por isso certifique-se de compreendê-lo.

1153
00:58:33,680 --> 00:58:36,660
Tenha cuidado para não mexer com ele ou
as outras coisas não funcionará corretamente.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> E a maior parte desse desafio é para
vocês para realmente modificar dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Nós vamos dar-lhe
140.000 palavras em um dicionário.

1157
00:58:48,526 --> 00:58:50,900
Nós vamos dar-lhe um texto
arquivo que tenha essas palavras,

1158
00:58:50,900 --> 00:58:54,840
e nós queremos que você seja capaz de organizar
-los em uma tabela hash ou um trie

1159
00:58:54,840 --> 00:58:58,140
porque quando pedimos-lhe para soletrar
check-- imagine se você é mágica

1160
00:58:58,140 --> 00:59:00,690
verificar como a Odisséia de Homero.

1161
00:59:00,690 --> 00:59:03,010
É como esta enorme teste enorme,.

1162
00:59:03,010 --> 00:59:05,190
>> Imagine se cada
palavra que você tinha que olhar

1163
00:59:05,190 --> 00:59:08,100
através de uma matriz de valores de 140.000.

1164
00:59:08,100 --> 00:59:10,350
Isso levaria para sempre
para a sua máquina para funcionar.

1165
00:59:10,350 --> 00:59:14,490
É por isso que queremos organizar a nossa
dados em estruturas de dados mais eficientes

1166
00:59:14,490 --> 00:59:17,270
tais como uma tabela de hash ou um trie.

1167
00:59:17,270 --> 00:59:20,700
E então vocês podem tipo
de quando você procura acesso

1168
00:59:20,700 --> 00:59:22,570
coisas com mais facilidade e mais rapidamente.

1169
00:59:22,570 --> 00:59:24,934
>> E por isso tome cuidado para resolver colisões.

1170
00:59:24,934 --> 00:59:27,350
Você está indo para obter um bando
de palavras de que começo com A.

1171
00:59:27,350 --> 00:59:29,957
Você vai ter um monte palavras
que começam com B. Até você

1172
00:59:29,957 --> 00:59:31,290
caras como você deseja resolver.

1173
00:59:31,290 --> 00:59:34,144
Talvez haja mais
função hash eficiente

1174
00:59:34,144 --> 00:59:36,810
que apenas a primeira letra
alguma coisa, e por isso é até você

1175
00:59:36,810 --> 00:59:38,190
caras para tipo de fazer o que quiser.

1176
00:59:38,190 --> 00:59:40,148
>> Talvez você deseja adicionar
todas as letras juntas.

1177
00:59:40,148 --> 00:59:43,410
Talvez você deseja como fazer coisas estranhas
para contabilizar o número de letras,

1178
00:59:43,410 --> 00:59:43,970
tanto faz.

1179
00:59:43,970 --> 00:59:45,386
Até vocês como você quer fazer.

1180
00:59:45,386 --> 00:59:49,262
Se você quer fazer uma tabela hash, se você
quer tentar uma trie, totalmente até você.

1181
00:59:49,262 --> 00:59:52,470
Vou avisá-lo antes do tempo que o
trie é normalmente um pouco mais difícil

1182
00:59:52,470 --> 00:59:54,520
apenas porque há um monte
mais ponteiros para acompanhar.

1183
00:59:54,520 --> 00:59:55,645
Mas totalmente até vocês.

1184
00:59:55,645 --> 00:59:58,742
É muito mais eficiente
na maioria dos casos.

1185
00:59:58,742 --> 01:00:01,450
Você quer realmente ser capaz de manter
a par de todos os seus ponteiros.

1186
01:00:01,450 --> 01:00:03,850
Como fazer a mesma coisa
que eu estava fazendo aqui.

1187
01:00:03,850 --> 01:00:06,871
Quando você está tentando inserir
valores em uma tabela hash ou excluir,

1188
01:00:06,871 --> 01:00:08,620
certifique-se que você é
realmente manter o controle

1189
01:00:08,620 --> 01:00:11,860
de onde tudo é porque
é realmente fácil para se estou

1190
01:00:11,860 --> 01:00:14,727
tentando inserir como a palavra, andy.

1191
01:00:14,727 --> 01:00:16,810
Vamos apenas dizer que é um
palavra verdadeira, a palavra, andy,

1192
01:00:16,810 --> 01:00:19,640
em uma lista gigante de um palavras.

1193
01:00:19,640 --> 01:00:22,450
>> Se eu só acontecerá a reafectação
um ponteiro errado, oops,

1194
01:00:22,450 --> 01:00:24,940
lá se vai a totalidade do
o resto da minha lista ligada.

1195
01:00:24,940 --> 01:00:26,897
Agora, a única palavra que eu
tem é Andy, e agora

1196
01:00:26,897 --> 01:00:29,230
todas as outras palavras do
dicionário ter sido perdida.

1197
01:00:29,230 --> 01:00:31,370
E assim que você quer certificar-se de que você
manter o controle de todos os seus ponteiros

1198
01:00:31,370 --> 01:00:33,661
ou então você está indo para obter
enormes problemas em seu código.

1199
01:00:33,661 --> 01:00:35,840
Desenhe as coisas cuidadosamente, passo a passo.

1200
01:00:35,840 --> 01:00:37,870
Isso torna muito mais fácil de pensar.

1201
01:00:37,870 --> 01:00:40,910
>> E, finalmente, você quer ser capaz de
testar o seu desempenho do seu programa

1202
01:00:40,910 --> 01:00:41,618
no grande tabuleiro.

1203
01:00:41,618 --> 01:00:43,710
Se vocês tomar uma
olhar para CS50 agora,

1204
01:00:43,710 --> 01:00:45,210
nós temos o que é chamado o grande quadro.

1205
01:00:45,210 --> 01:00:50,200
É a súmula dos mais rápidos
soletrar tempos de aferição, em todos CS50

1206
01:00:50,200 --> 01:00:55,720
agora, eu acho que o top 10 como
vezes eu acho que oito deles são funcionários.

1207
01:00:55,720 --> 01:00:57,960
Nós realmente queremos que vocês nos vencer.

1208
01:00:57,960 --> 01:01:00,870
>> Todos nós estávamos tentando implementar
o código mais rápido possível.

1209
01:01:00,870 --> 01:01:04,880
Queremos que vocês tentar desafiar
nós e implementar mais rapidamente do que todos nós

1210
01:01:04,880 --> 01:01:05,550
podem.

1211
01:01:05,550 --> 01:01:07,970
E assim, este é realmente
a primeira vez que nós somos

1212
01:01:07,970 --> 01:01:12,680
pedindo a vocês para fazer um pset que
você realmente pode fazer em qualquer método

1213
01:01:12,680 --> 01:01:13,760
tu queres.

1214
01:01:13,760 --> 01:01:17,730
>> Eu sempre digo, este é mais parecido
a uma solução da vida real, certo?

1215
01:01:17,730 --> 01:01:19,550
Eu digo, hey, eu preciso de você para fazer isso.

1216
01:01:19,550 --> 01:01:21,380
Construir um programa que faz isso para mim.

1217
01:01:21,380 --> 01:01:22,630
Fazê-lo como quiser.

1218
01:01:22,630 --> 01:01:24,271
Eu só sei que eu quero jejuar.

1219
01:01:24,271 --> 01:01:25,770
Esse é o seu desafio para esta semana.

1220
01:01:25,770 --> 01:01:27,531
Vocês, vamos
para dar-lhe uma tarefa.

1221
01:01:27,531 --> 01:01:29,030
Nós vamos dar-lhe um desafio.

1222
01:01:29,030 --> 01:01:31,559
E então cabe a vocês
completamente apenas descobrir

1223
01:01:31,559 --> 01:01:34,100
qual é a mais rápida e mais
maneira eficiente de implementar isso.

1224
01:01:34,100 --> 01:01:34,600
Sim?

1225
01:01:34,600 --> 01:01:37,476
>> AUDIÊNCIA: É permitido se
queria pesquisar maneiras mais rápidas

1226
01:01:37,476 --> 01:01:40,821
para fazer tabelas de hash on-line, podemos fazer
que e citar código de outra pessoa?

1227
01:01:40,821 --> 01:01:42,070
ANDI Peng: Sim, totalmente bem.

1228
01:01:42,070 --> 01:01:44,320
Então, se vocês a ler
spec, há uma linha

1229
01:01:44,320 --> 01:01:48,310
na especificação que diz que vocês
são totalmente livres para pesquisar de hash

1230
01:01:48,310 --> 01:01:51,070
funções em que são alguns
das funções hash mais rápidos

1231
01:01:51,070 --> 01:01:54,720
para executar as coisas através como
Contanto que você citar esse código.

1232
01:01:54,720 --> 01:01:57,220
Por isso, algumas pessoas já têm
descobri maneiras rápidas

1233
01:01:57,220 --> 01:02:00,250
de fazer corretores ortográficos, de rápida
formas de armazenar informações.

1234
01:02:00,250 --> 01:02:02,750
Totalmente até que vocês se
quero tomar apenas isso, certo?

1235
01:02:02,750 --> 01:02:04,045
Certifique-se de que você está citando.

1236
01:02:04,045 --> 01:02:06,170
O desafio aqui é realmente
que estamos tentando testar

1237
01:02:06,170 --> 01:02:09,750
é ter certeza que você sabe
o caminho de volta ponteiros.

1238
01:02:09,750 --> 01:02:12,700
Tanto quanto você implementar
a função hash real

1239
01:02:12,700 --> 01:02:15,070
e chegando com como
a matemática para fazer isso,

1240
01:02:15,070 --> 01:02:17,570
vocês podem pesquisar o que quer
métodos on-line que vocês querem.

1241
01:02:17,570 --> 01:02:17,996
Sim?

1242
01:02:17,996 --> 01:02:19,700
>> AUDIÊNCIA: Podemos citar apenas
usando o [inaudível]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI Peng: Sim.

1244
01:02:20,120 --> 01:02:22,328
Você pode apenas, em seu comentário,
você pode citar como, oh,

1245
01:02:22,328 --> 01:02:26,127
tomado de yada, yada,
yada, a função hash.

1246
01:02:26,127 --> 01:02:27,210
Alguém tem alguma pergunta?

1247
01:02:27,210 --> 01:02:29,694
Nós, na verdade breezed
a seção de hoje.

1248
01:02:29,694 --> 01:02:31,610
Eu vou estar aqui a
responder a perguntas bem.

1249
01:02:31,610 --> 01:02:36,570
>> Além disso, como eu disse, escritório
horas esta noite e amanhã.

1250
01:02:36,570 --> 01:02:40,307
A especificação desta semana é, na verdade,
super fácil e super rápido de ler.

1251
01:02:40,307 --> 01:02:43,140
Eu gostaria de sugerir tendo um olhar, apenas
ler através da totalidade do mesmo.

1252
01:02:43,140 --> 01:02:45,730
>> E Zamyla realmente anda você
através de cada uma das funções

1253
01:02:45,730 --> 01:02:49,796
você precisa para implementar, e por isso é
muito, muito claro como fazer tudo.

1254
01:02:49,796 --> 01:02:51,920
Só para ter certeza que você é
manter o controle dos ponteiros.

1255
01:02:51,920 --> 01:02:53,650
Este é um pset muito desafiador.

1256
01:02:53,650 --> 01:02:56,744
>> Não é um desafio porque, como,
oh, os conceitos são muito mais

1257
01:02:56,744 --> 01:02:59,160
difícil, ou você tem que aprender
muito nova sintaxe do caminho

1258
01:02:59,160 --> 01:03:00,650
que você fez para a última pset.

1259
01:03:00,650 --> 01:03:03,320
Isto é difícil porque pset
há muitos pontos,

1260
01:03:03,320 --> 01:03:06,980
e então é muito, muito fácil de uma vez
você tem um bug em seu código não ser capaz

1261
01:03:06,980 --> 01:03:08,315
para descobrir onde é que o bug.

1262
01:03:08,315 --> 01:03:13,200
>> E assim completa e absoluta fé em você
caras para ser capaz de bater o nosso [inaudível]

1263
01:03:13,200 --> 01:03:13,700
grafias.

1264
01:03:13,700 --> 01:03:16,640
Na verdade, eu não tenho qualquer mina escrito
Ainda não, mas estou prestes a escrever o meu.

1265
01:03:16,640 --> 01:03:19,070
Então, enquanto você está escrevendo
seu, eu vou estar escrevendo meu.

1266
01:03:19,070 --> 01:03:21,070
Vou tentar fazer
mina mais rápido do que o seu.

1267
01:03:21,070 --> 01:03:23,940
Vamos ver quem tem o mais rápido.

1268
01:03:23,940 --> 01:03:27,340
>> E sim, vou ver todos
vocês aqui na terça-feira.

1269
01:03:27,340 --> 01:03:29,510
Vou correr um tipo como uma oficina pset.

1270
01:03:29,510 --> 01:03:32,640
Todas as secções este
semana são oficinas PSet,

1271
01:03:32,640 --> 01:03:36,690
então vocês têm muitas oportunidades
por ajuda, o horário de expediente, como sempre,

1272
01:03:36,690 --> 01:03:41,330
e eu realmente ansioso para
ler todo o código dos seus rapazes.

1273
01:03:41,330 --> 01:03:44,160
Eu tenho quizzes-se aqui se você
caras querem vir buscar aqueles.

1274
01:03:44,160 --> 01:03:45,880
Isso é tudo.

1275
01:03:45,880 --> 01:03:48,180