1
00:00:00,000 --> 00:00:11,860

2
00:00:11,860 --> 00:00:13,120
>> COLUNA 1: Tudo bem, então estamos de volta.

3
00:00:13,120 --> 00:00:14,480
Bem-vindo ao CS50.

4
00:00:14,480 --> 00:00:16,510
Isto é o fim de semana sete.

5
00:00:16,510 --> 00:00:20,200
Então, lembro que da última vez, nós começamos
olhando um pouco mais sofisticado

6
00:00:20,200 --> 00:00:21,100
estruturas de dados.

7
00:00:21,100 --> 00:00:25,110
Uma vez que, até agora, tudo o que tinha realmente
à nossa disposição era isso, um array.

8
00:00:25,110 --> 00:00:29,340
>> Mas, antes de descartar a matriz como não
tudo o que interessante, o que de fato

9
00:00:29,340 --> 00:00:33,570
realmente é, o que são alguns dos
vantagens destes dados simples

10
00:00:33,570 --> 00:00:34,560
estrutura até agora?

11
00:00:34,560 --> 00:00:36,110
O que é que é bom?

12
00:00:36,110 --> 00:00:39,450
Até agora, como vimos?

13
00:00:39,450 --> 00:00:42,540
O que você tem?

14
00:00:42,540 --> 00:00:44,028
Nada.

15
00:00:44,028 --> 00:00:45,020
>> Estudante: [inaudível].

16
00:00:45,020 --> 00:00:45,395
>> COLUNA 1: O que é isso?

17
00:00:45,395 --> 00:00:46,410
>> Estudante: [inaudível].

18
00:00:46,410 --> 00:00:47,000
>> COLUNA 1: tamanho fixo.

19
00:00:47,000 --> 00:00:51,260
OK, então por que é tamanho fixo bom embora?

20
00:00:51,260 --> 00:00:53,180
>> Estudante: [inaudível].

21
00:00:53,180 --> 00:00:56,240
>> COLUNA 1: OK, por isso é eficiente em
a sensação de que você pode alocar um

22
00:00:56,240 --> 00:01:00,070
quantidade fixa de espaço, que espero
É precisamente tanto

23
00:01:00,070 --> 00:01:01,180
espaço como você quiser.

24
00:01:01,180 --> 00:01:02,720
Assim que poderiam ser absolutamente uma vantagem.

25
00:01:02,720 --> 00:01:06,530
>> Qual é o outro lado por um conjunto?

26
00:01:06,530 --> 00:01:07,610
Sim?

27
00:01:07,610 --> 00:01:08,750
>> Estudante: [inaudível].

28
00:01:08,750 --> 00:01:09,550
>> COLUNA 1: Tudo o - sorry?

29
00:01:09,550 --> 00:01:11,270
>> Estudante: [inaudível].

30
00:01:11,270 --> 00:01:13,620
>> COLUNA 1: Todas as caixas na memória
ou ao lado do outro.

31
00:01:13,620 --> 00:01:15,220
E isso é útil - por quê?

32
00:01:15,220 --> 00:01:15,970
Isso é bem verdade.

33
00:01:15,970 --> 00:01:18,611
Mas como podemos explorar isso verdade?

34
00:01:18,611 --> 00:01:21,500
>> Estudante: [inaudível].

35
00:01:21,500 --> 00:01:24,490
>> COLUNA 1: Exatamente, podemos acompanhar
onde tudo é apenas por saber

36
00:01:24,490 --> 00:01:28,560
um endereço, ou seja, o endereço do
primeiro byte desse bloco de memória.

37
00:01:28,560 --> 00:01:30,420
Ou, no caso da cadeia,
o endereço do primeiro

38
00:01:30,420 --> 00:01:31,460
char que string.

39
00:01:31,460 --> 00:01:33,330
E a partir daí, podemos encontrar
o fim da string.

40
00:01:33,330 --> 00:01:35,710
Podemos encontrar o segundo elemento, o
terceiro elemento, e assim por diante.

41
00:01:35,710 --> 00:01:38,740
>> E assim, a maneira elegante de descrever que
característica é que as matrizes nos dar

42
00:01:38,740 --> 00:01:40,020
de acesso aleatório.

43
00:01:40,020 --> 00:01:44,330
Apenas usando o colchete
notação e um número, você pode saltar para

44
00:01:44,330 --> 00:01:48,070
um elemento específico da matriz
em tempo constante, O grande

45
00:01:48,070 --> 00:01:49,810
de uma, por assim dizer.

46
00:01:49,810 --> 00:01:51,080
>> Mas houve algumas desvantagens.

47
00:01:51,080 --> 00:01:53,110
O que uma matriz não fazer muito facilmente?

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
O que é isso não é bom?

50
00:01:57,170 --> 00:01:58,810
>> Estudante: [inaudível].

51
00:01:58,810 --> 00:01:59,860
>> COLUNA 1: O que é isso?

52
00:01:59,860 --> 00:02:00,530
>> Estudante: [inaudível].

53
00:02:00,530 --> 00:02:01,460
>> COLUNA 1: Expansão de tamanho.

54
00:02:01,460 --> 00:02:04,800
Assim, as desvantagens da matriz são
precisamente o oposto do que o

55
00:02:04,800 --> 00:02:05,540
upsides são.

56
00:02:05,540 --> 00:02:07,610
Então, uma das desvantagens é
que é um tamanho fixo.

57
00:02:07,610 --> 00:02:09,400
Então você não pode realmente crescer.

58
00:02:09,400 --> 00:02:13,510
Você pode realocar uma fatia maior do
memória e, em seguida, mover os elementos antigos

59
00:02:13,510 --> 00:02:14,460
na nova matriz.

60
00:02:14,460 --> 00:02:18,060
E, então, livre da velha matriz, para
exemplo, usando malloc ou similar

61
00:02:18,060 --> 00:02:21,180
função chamada realloc, que
realoca memória.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, como um aparte, tenta dar-lhe
de memória que é ao lado da matriz

63
00:02:25,490 --> 00:02:26,610
que você já tem.

64
00:02:26,610 --> 00:02:28,740
Mas isso pode mudar as coisas
volta completamente.

65
00:02:28,740 --> 00:02:30,710
Mas, em suma, que é caro, né?

66
00:02:30,710 --> 00:02:33,440
Porque se você tem um bloco de memória de
deste tamanho, mas você realmente quer um

67
00:02:33,440 --> 00:02:36,710
deste tamanho, e você quer preservar
os elementos originais, você tem

68
00:02:36,710 --> 00:02:40,510
cerca de um processo de cópia de tempo linear
que deve acontecer a partir de

69
00:02:40,510 --> 00:02:41,900
antiga matriz para novos.

70
00:02:41,900 --> 00:02:44,630
E a realidade está pedindo ao funcionamento
sistema novo e de novo e

71
00:02:44,630 --> 00:02:48,340
novamente para grandes pedaços de memória pode começar
lhe custar algum tempo também.

72
00:02:48,340 --> 00:02:52,250
Por isso, é tanto uma bênção e uma maldição em
dissimular o fato de que essas matrizes

73
00:02:52,250 --> 00:02:53,860
são de tamanho fixo.

74
00:02:53,860 --> 00:02:56,790
Mas se introduzir algo em vez
assim, o que nós chamamos um linked

75
00:02:56,790 --> 00:03:00,580
lista, temos alguns prós e
algumas desvantagens aqui também.

76
00:03:00,580 --> 00:03:05,780
>> Assim, uma lista ligada é simplesmente um conjunto de dados
estrutura composta de estruturas C neste

77
00:03:05,780 --> 00:03:09,850
caso, onde um struct, aviso, é apenas
um recipiente para uma ou mais específico

78
00:03:09,850 --> 00:03:11,100
tipos de variáveis.

79
00:03:11,100 --> 00:03:16,110
Neste caso, o que os tipos de dados
parecem estar dentro da estrutura que

80
00:03:16,110 --> 00:03:17,600
última vez que chamado de nó?

81
00:03:17,600 --> 00:03:19,380
Cada um destes rectângulos é um nó.

82
00:03:19,380 --> 00:03:22,660
E cada um dos retângulos menores
dentro do que é um tipo de dados.

83
00:03:22,660 --> 00:03:25,300
Quais são os tipos que dissemos
eles estavam na segunda-feira?

84
00:03:25,300 --> 00:03:26,478
Sim?

85
00:03:26,478 --> 00:03:27,870
>> Estudante: [inaudível].

86
00:03:27,870 --> 00:03:30,721
>> COLUNA 1: A variável e um ponteiro, ou
mais especificamente, um int, para n,

87
00:03:30,721 --> 00:03:32,180
e um ponteiro na parte inferior.

88
00:03:32,180 --> 00:03:35,360
Ambas aquelas que ser de 32 bits, em
menos em um computador como este CS50

89
00:03:35,360 --> 00:03:37,980
Appliance, e por isso eles são
igualmente desenhada em tamanho.

90
00:03:37,980 --> 00:03:42,260
>> Então, o que estão usando o ponteiro
apesar de aparentemente?

91
00:03:42,260 --> 00:03:47,690
Por que acrescentar esta seta agora, quando as matrizes foram
tão agradável e limpo e simples?

92
00:03:47,690 --> 00:03:50,460
O que é o ponteiro para fazer
nós em cada um desses nodos?

93
00:03:50,460 --> 00:03:52,160
>> Estudante: [inaudível].

94
00:03:52,160 --> 00:03:52,465
>> COLUNA 1: Exatamente.

95
00:03:52,465 --> 00:03:54,120
Ele está dizendo a você onde
a próxima é.

96
00:03:54,120 --> 00:03:57,350
Então, eu tipo de usar a analogia de
utilizando um fio de classificar de

97
00:03:57,350 --> 00:03:59,180
enfiar esses nós juntos.

98
00:03:59,180 --> 00:04:01,760
E isso é exatamente o que estamos fazendo com
ponteiros porque cada uma delas

99
00:04:01,760 --> 00:04:06,360
pedaços de memória pode ou não ser
contígua, de costas para trás

100
00:04:06,360 --> 00:04:09,500
dentro de RAM, porque cada vez que você
chamar malloc dizendo, dá-me o suficiente

101
00:04:09,500 --> 00:04:12,510
bytes para um novo nó, que poderia
ficar aqui ou pode ser aqui.

102
00:04:12,510 --> 00:04:13,120
Pode ser aqui.

103
00:04:13,120 --> 00:04:13,730
Pode ser aqui.

104
00:04:13,730 --> 00:04:14,640
Você simplesmente não sabe.

105
00:04:14,640 --> 00:04:17,880
>> Mas o uso de ponteiros em endereços de
desses nós, você pode uni-las

106
00:04:17,880 --> 00:04:22,370
juntos de uma forma que parece ser visualmente
como a lista, mesmo se essas coisas são

107
00:04:22,370 --> 00:04:26,770
todos espalhados por todo o seu um ou
suas duas ou seus quatro gigabytes de RAM

108
00:04:26,770 --> 00:04:28,760
dentro de seu próprio computador.

109
00:04:28,760 --> 00:04:33,230
>> Então, o lado negativo, então, de
uma lista ligada é o quê?

110
00:04:33,230 --> 00:04:34,670
O que é um preço que estamos
aparentemente pagando?

111
00:04:34,670 --> 00:04:36,010
>> Estudante: [inaudível].

112
00:04:36,010 --> 00:04:36,920
>> COLUNA 1: Mais espaço, certo?

113
00:04:36,920 --> 00:04:39,340
Temos, neste caso, duplicando a quantidade
de espaço, porque nós fomos

114
00:04:39,340 --> 00:04:43,500
a partir de 32 bits para cada nó, para cada
int, agora de 64 bits, porque temos de

115
00:04:43,500 --> 00:04:45,050
manter em torno de um ponteiro bem.

116
00:04:45,050 --> 00:04:48,860
Você ganha mais eficiência se o seu struct
é maior do que essa coisa simples.

117
00:04:48,860 --> 00:04:52,020
Se você realmente tem um aluno dentro
de que é um par de cordas para

118
00:04:52,020 --> 00:04:55,430
nome e casa, talvez um número de identificação,
talvez alguns outros campos completamente.

119
00:04:55,430 --> 00:04:59,000
>> Então, se você tem uma grande estrutura suficiente,
talvez o custo do ponteiro está

120
00:04:59,000 --> 00:05:00,010
não como um grande negócio.

121
00:05:00,010 --> 00:05:03,570
Isto é um pouco de um caso de canto em que
estamos armazenando uma simples primitivo como

122
00:05:03,570 --> 00:05:04,760
dentro da lista encadeada.

123
00:05:04,760 --> 00:05:05,790
Mas o ponto é o mesmo.

124
00:05:05,790 --> 00:05:08,230
Você está definitivamente gastar mais
memória, mas que está recebendo

125
00:05:08,230 --> 00:05:08,990
flexibilidade.

126
00:05:08,990 --> 00:05:12,280
Porque agora se eu quiser adicionar um elemento
no início da lista,

127
00:05:12,280 --> 00:05:14,340
Eu tenho que alocar um novo nó.

128
00:05:14,340 --> 00:05:17,180
E eu tenho que apenas atualizar os
flechas de alguma forma por apenas movendo

129
00:05:17,180 --> 00:05:17,980
algumas dicas redor.

130
00:05:17,980 --> 00:05:20,580
>> Se eu quiser inserir algo na
meio da lista, eu não tenho a

131
00:05:20,580 --> 00:05:24,410
empurrar todos para o lado como fizemos em
passado semanas com os nossos voluntários que

132
00:05:24,410 --> 00:05:25,700
representada uma matriz.

133
00:05:25,700 --> 00:05:29,470
Eu só posso atribuir um novo nó e
em seguida, basta apontar as setas em

134
00:05:29,470 --> 00:05:32,290
diferentes direções, porque não
tem que permanecer no real

135
00:05:32,290 --> 00:05:35,670
memória de uma linha de verdade como eu desenhei
aqui na tela.

136
00:05:35,670 --> 00:05:38,400
>> E então, finalmente, se você quiser inserir
algo que, no final da lista, é

137
00:05:38,400 --> 00:05:39,210
ainda mais fácil.

138
00:05:39,210 --> 00:05:43,320
Esta é uma espécie de notação arbitrária,
mas ponteiro de 34, dar um palpite.

139
00:05:43,320 --> 00:05:46,710
Qual é o valor de seu ponteiro mais
provável tipo elaborado de como um velho

140
00:05:46,710 --> 00:05:47,700
antena escola lá?

141
00:05:47,700 --> 00:05:48,920
>> Estudante: [inaudível].

142
00:05:48,920 --> 00:05:49,900
>> COLUNA 1: É provavelmente nulo.

143
00:05:49,900 --> 00:05:52,710
E, de fato, que é um autor
representação do nulo.

144
00:05:52,710 --> 00:05:56,310
E é nulo porque é absolutamente
Precisamos saber onde o fim de um linked

145
00:05:56,310 --> 00:06:00,050
lista é, para você continuar a seguir e
seguindo e seguindo essas setas

146
00:06:00,050 --> 00:06:01,170
para um valor de lixo.

147
00:06:01,170 --> 00:06:06,230
Então nulo irá significar que não há nenhuma
mais nós à direita do número 34,

148
00:06:06,230 --> 00:06:07,200
neste caso.

149
00:06:07,200 --> 00:06:10,270
>> Assim, propomos que podemos implementar
este nó em código.

150
00:06:10,270 --> 00:06:12,130
E temos visto esse tipo
de sintaxe antes.

151
00:06:12,130 --> 00:06:15,090
Typedef apenas define um novo tipo de
nós, dá-nos um sinônimo como

152
00:06:15,090 --> 00:06:17,100
corda era para char *.

153
00:06:17,100 --> 00:06:21,030
Neste caso, ele vai nos dar
notação abreviada para que nó struct

154
00:06:21,030 --> 00:06:24,010
pode ao invés de apenas ser escrita como
nodo, o que é muito mais limpo.

155
00:06:24,010 --> 00:06:25,360
É muito menos detalhada.

156
00:06:25,360 --> 00:06:30,080
>> No interior de um nó é aparentemente um int
chamado n, e, em seguida, um nó struct *

157
00:06:30,080 --> 00:06:34,670
o que significa exatamente o que queríamos que o
setas a dizer, um ponteiro para uma outra

158
00:06:34,670 --> 00:06:36,940
nó do mesmo tipo de dados exatos.

159
00:06:36,940 --> 00:06:40,300
E eu proponho que poderia implementar um
função de pesquisa como este, que a

160
00:06:40,300 --> 00:06:41,890
primeira vista pode parecer
um pouco complexo.

161
00:06:41,890 --> 00:06:43,330
Mas vamos vê-lo no contexto.

162
00:06:43,330 --> 00:06:45,480
>> Deixe-me ir para o aparelho aqui.

163
00:06:45,480 --> 00:06:48,460
Deixe-me abrir um arquivo chamado
lista de zero ponto h.

164
00:06:48,460 --> 00:06:53,950
E isso só contém a definição de nós
só vi há pouco para esses dados

165
00:06:53,950 --> 00:06:55,390
tipo chamado um nó.

166
00:06:55,390 --> 00:06:57,350
Então nós colocamos isso em um arquivo h ponto.

167
00:06:57,350 --> 00:07:01,430
>> E como um aparte, embora esta
programa que você está prestes a ver é

168
00:07:01,430 --> 00:07:05,410
não tudo o que complexa, é de fato
convenção quando se escreve um programa para

169
00:07:05,410 --> 00:07:10,270
colocar as coisas como tipos de dados, para puxar
constantes, às vezes, dentro de seu

170
00:07:10,270 --> 00:07:13,210
arquivo de cabeçalho, e não necessariamente em
o arquivo C, certamente quando o seu

171
00:07:13,210 --> 00:07:17,370
programas ficam maiores e maiores, de modo que
você sabe onde olhar tanto para

172
00:07:17,370 --> 00:07:20,840
documentação em alguns casos, ou
para o básico como este, os

173
00:07:20,840 --> 00:07:22,360
definição de algum tipo.

174
00:07:22,360 --> 00:07:25,680
>> Se eu agora abrir lista de zero ponto
c, observe algumas coisas.

175
00:07:25,680 --> 00:07:29,090
Ele inclui alguns arquivos de cabeçalho, a maioria dos
de que nós já vimos antes.

176
00:07:29,090 --> 00:07:31,980
Ela inclui o seu próprio arquivo de cabeçalho.

177
00:07:31,980 --> 00:07:35,200
>> E como um aparte, por que é o dobro
citações aqui, em oposição ao ângulo

178
00:07:35,200 --> 00:07:38,340
suportes na linha que
Eu destacou lá?

179
00:07:38,340 --> 00:07:39,180
>> Estudante: [inaudível].

180
00:07:39,180 --> 00:07:40,460
>> COLUNA 1: Sim isso é um arquivo local.

181
00:07:40,460 --> 00:07:44,300
Então, se é um arquivo local de sua preferência aqui
na linha 15, por exemplo, você pode usar

182
00:07:44,300 --> 00:07:46,570
as aspas duplas em vez
dos suportes angulares.

183
00:07:46,570 --> 00:07:48,270
>> Agora isso é bem interessante.

184
00:07:48,270 --> 00:07:51,830
Repare que eu tenho declarado mundial
variável neste programa na linha 18

185
00:07:51,830 --> 00:07:55,910
chamado pela primeira vez, a idéia é esta é
Vai ser um ponteiro para o primeiro

186
00:07:55,910 --> 00:07:59,190
nó na minha lista ligada, e eu tenho
inicializado para nulo, porque eu tenho

187
00:07:59,190 --> 00:08:02,310
não alocado qualquer real
nós ainda.

188
00:08:02,310 --> 00:08:07,570
>> Então, isso representa, pictoricamente, o que
vi há pouco na imagem como

189
00:08:07,570 --> 00:08:10,090
esse ponteiro no canto
Lado Esquerdo.

190
00:08:10,090 --> 00:08:12,260
Então, agora, que o ponteiro
não tem uma seta.

191
00:08:12,260 --> 00:08:14,590
É ao contrário, é simplesmente nulo.

192
00:08:14,590 --> 00:08:17,880
Mas ele representa o que será o
endereço da primeira real

193
00:08:17,880 --> 00:08:19,480
nó na lista.

194
00:08:19,480 --> 00:08:22,120
Então, eu tenho implementado é uma empresa global
porque, como você vai ver, tudo isso

195
00:08:22,120 --> 00:08:25,310
programa faz na vida é implementar
uma lista ligada para mim.

196
00:08:25,310 --> 00:08:27,050
>> Agora eu tenho alguns protótipos aqui.

197
00:08:27,050 --> 00:08:31,190
Decidi implementar recursos como
deleção, inserção, pesquisa e

198
00:08:31,190 --> 00:08:31,740
travessia -

199
00:08:31,740 --> 00:08:35,210
o último sendo apenas atravessar a
lista, imprimir os seus elementos.

200
00:08:35,210 --> 00:08:36,750
E agora aqui está a minha rotina principal.

201
00:08:36,750 --> 00:08:39,890
E não vamos gastar muito tempo em
estes uma vez que esta é uma espécie de, esperemos

202
00:08:39,890 --> 00:08:41,780
chapéu velho agora.

203
00:08:41,780 --> 00:08:45,370
>> Eu vou fazer o seguinte,
enquanto o utilizador coopera.

204
00:08:45,370 --> 00:08:47,300
Então, eu estou indo para imprimir
este menu.

205
00:08:47,300 --> 00:08:49,420
E eu já formatado como
limpa que pude.

206
00:08:49,420 --> 00:08:52,240
Se o usuário digita em um, o que significa
eles querem apagar alguma coisa.

207
00:08:52,240 --> 00:08:54,560
Se o usuário digita em dois, o que significa
eles querem inserir algo.

208
00:08:54,560 --> 00:08:55,930
E assim sucessivamente.

209
00:08:55,930 --> 00:08:58,270
Vou então pedir
seguida por um comando.

210
00:08:58,270 --> 00:08:59,300
E então eu vou usar GetInt.

211
00:08:59,300 --> 00:09:02,790
>> Portanto, este é um menuing realmente simples
interface onde você só precisa digitar

212
00:09:02,790 --> 00:09:05,270
um mapeamento para um número
desses comandos.

213
00:09:05,270 --> 00:09:08,730
E agora eu tenho um interruptor limpa agradável
declaração de que vai ligar

214
00:09:08,730 --> 00:09:10,090
o que o usuário digitou dentro

215
00:09:10,090 --> 00:09:12,180
E se digitou um, eu vou
chamar apagar e quebrar.

216
00:09:12,180 --> 00:09:14,380
Se digitado duas, eu vou
chamar inserir e quebrar.

217
00:09:14,380 --> 00:09:16,490
>> E agora repare que eu coloquei cada
destes na mesma linha.

218
00:09:16,490 --> 00:09:18,360
Esta é apenas uma decisão estilística.

219
00:09:18,360 --> 00:09:20,210
Normalmente, temos visto algo
como esta.

220
00:09:20,210 --> 00:09:23,260
Mas eu decidi, francamente, meu programa
parecia mais legível porque

221
00:09:23,260 --> 00:09:25,980
ele tinha apenas quatro casos para
apenas listá-la assim.

222
00:09:25,980 --> 00:09:28,360
Uso totalmente legítimo do estilo.

223
00:09:28,360 --> 00:09:31,480
E eu vou fazer isso, desde que o
usuário não tenha digitado zero, o que eu

224
00:09:31,480 --> 00:09:33,910
decidiu significará que querem parar de fumar.

225
00:09:33,910 --> 00:09:36,630
>> Então agora perceber o que eu estou
vamos fazer aqui.

226
00:09:36,630 --> 00:09:38,650
Vou liberar a lista aparentemente.

227
00:09:38,650 --> 00:09:40,230
Mas mais sobre isso daqui a pouco.

228
00:09:40,230 --> 00:09:41,640
Vamos primeiro executar este programa.

229
00:09:41,640 --> 00:09:45,250
Então deixe-me fazer um terminal maior
janela, ponto barra lista 0.

230
00:09:45,250 --> 00:09:49,510
Eu estou indo para ir em frente e coloque por
tipagem dois, um número semelhante de 50, e agora

231
00:09:49,510 --> 00:09:51,590
você verá a lista é agora 50.

232
00:09:51,590 --> 00:09:53,380
E meu texto apenas rolou para cima um pouco.

233
00:09:53,380 --> 00:09:55,940
Então agora observe a lista contém
o número 50.

234
00:09:55,940 --> 00:09:58,220
>> Vamos fazer outra inserção, tomando duas.

235
00:09:58,220 --> 00:10:01,630
Vamos digitar o número como um.

236
00:10:01,630 --> 00:10:03,940
Lista é agora um, seguido por 50.

237
00:10:03,940 --> 00:10:06,020
Portanto, esta é apenas uma representação textual
da lista.

238
00:10:06,020 --> 00:10:10,550
E vamos inserir mais um número como
o número 42, que é esperançosamente

239
00:10:10,550 --> 00:10:14,620
vai acabar no meio, porque
este programa em particular os tipos que

240
00:10:14,620 --> 00:10:16,320
elementos, uma vez que os insere.

241
00:10:16,320 --> 00:10:17,220
Portanto, não temos.

242
00:10:17,220 --> 00:10:20,730
Super programa simples que poderia
absolutamente ter usado um array, mas eu

243
00:10:20,730 --> 00:10:23,280
acontecer de estar usando uma lista encadeada
só assim eu posso dinamicamente

244
00:10:23,280 --> 00:10:24,610
crescer e reduzi-lo.

245
00:10:24,610 --> 00:10:28,470
>> Então, vamos dar uma olhada para a pesquisa, se eu
comando de três correr, eu quero procurar

246
00:10:28,470 --> 00:10:31,040
para, por exemplo, o número 43.

247
00:10:31,040 --> 00:10:34,190
E nada foi encontrado, aparentemente,
porque voltei sem resposta.

248
00:10:34,190 --> 00:10:35,010
Então, vamos fazer isso de novo.

249
00:10:35,010 --> 00:10:35,690
Pesquisar.

250
00:10:35,690 --> 00:10:39,520
Vamos procurar para 50, ou melhor, procurar
para 42, que tem uma bela

251
00:10:39,520 --> 00:10:40,850
pouco significado sutil.

252
00:10:40,850 --> 00:10:42,610
E eu descobri o significado da vida lá.

253
00:10:42,610 --> 00:10:44,990
Número 42, se você não sabe
a referência, no Google.

254
00:10:44,990 --> 00:10:45,350
Tudo bem.

255
00:10:45,350 --> 00:10:47,130
Então, o que este programa feito por mim?

256
00:10:47,130 --> 00:10:50,660
É só me permitiu inserir assim
longe e busca de elementos.

257
00:10:50,660 --> 00:10:53,650
>> Vamos avançar, então, para
que a função que olhou

258
00:10:53,650 --> 00:10:55,360
na segunda-feira como um teaser.

259
00:10:55,360 --> 00:10:59,620
Então essa função, eu afirmo, as pesquisas para
um elemento na lista por primeiro

260
00:10:59,620 --> 00:11:03,830
um, alertando o usuário e, em seguida, chamar
GetInt para obter um int real

261
00:11:03,830 --> 00:11:05,060
que você deseja procurar.

262
00:11:05,060 --> 00:11:06,460
>> Então observe isso.

263
00:11:06,460 --> 00:11:10,690
Eu estou indo para criar uma variável temporária
na linha 188 chamado ponteiro -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
poderia tê-lo chamado qualquer coisa.

266
00:11:12,440 --> 00:11:16,140
E é um ponteiro para um nó
porque eu disse nó * lá.

267
00:11:16,140 --> 00:11:19,900
E estou inicializando a ser igual
primeiro, para que eu efetivamente tenho o meu

268
00:11:19,900 --> 00:11:22,860
dedo, por assim dizer, na mesma
primeiro elemento da lista.

269
00:11:22,860 --> 00:11:27,460
Então, se a minha mão direita é aqui PTR eu sou
apontando para a mesma coisa que o primeiro

270
00:11:27,460 --> 00:11:28,670
está apontando.

271
00:11:28,670 --> 00:11:31,430
>> Então, agora de volta no código,
o que acontece a seguir -

272
00:11:31,430 --> 00:11:35,070
este é um paradigma comum quando a iteração
ao longo de uma estrutura como uma

273
00:11:35,070 --> 00:11:35,970
lista ligada.

274
00:11:35,970 --> 00:11:40,410
Eu vou fazer o seguinte, enquanto
ponteiro não é igual a null Assim, enquanto

275
00:11:40,410 --> 00:11:47,530
meu dedo não está apontado em algum nulo
valor, se ponteiro de seta n é igual a n.

276
00:11:47,530 --> 00:11:52,290
Vamos observar primeiro que n é o que o
usuário digitou por GetInts chamar aqui.

277
00:11:52,290 --> 00:11:54,280
>> E ponteiro de seta n significa o quê?

278
00:11:54,280 --> 00:11:59,020
Bem, se nós voltar para a imagem aqui,
se eu tiver um dedo apontando para

279
00:11:59,020 --> 00:12:02,960
aquele primeiro nó contendo nove, o
seta essencialmente significa ir àquela

280
00:12:02,960 --> 00:12:08,860
nó e pegar o valor na posição n,
neste caso, o campo de dados chamado n.

281
00:12:08,860 --> 00:12:14,120
>> Como um aparte - e nós vimos isso algumas
de semanas atrás, quando alguém perguntou -

282
00:12:14,120 --> 00:12:18,840
esta sintaxe é novo, mas não
dar-nos poderes que

283
00:12:18,840 --> 00:12:20,040
já não tem.

284
00:12:20,040 --> 00:12:25,325
Qual foi esta frase equivalente a usar
notação de ponto e estrela de um casal

285
00:12:25,325 --> 00:12:29,490
de semanas atrás, quando puxada para trás
esta camada um pouco prematuramente?

286
00:12:29,490 --> 00:12:31,780
>> Estudante: [inaudível].

287
00:12:31,780 --> 00:12:38,880
>> COLUNA 1: Exatamente, foi estrela, e
em seguida, foi estrela ponto n, com

288
00:12:38,880 --> 00:12:41,930
parênteses aqui, o que parece,
francamente, eu acho que um monte

289
00:12:41,930 --> 00:12:43,320
mais enigmática de ler.

290
00:12:43,320 --> 00:12:46,270
Mas a estrela do ponteiro, como sempre,
meios para lá.

291
00:12:46,270 --> 00:12:49,090
E uma vez que você está lá, que dados
campo que você deseja acessar?

292
00:12:49,090 --> 00:12:52,730
Bem, você usar a notação de ponto para acessar
um campo de dados estruturas, e eu

293
00:12:52,730 --> 00:12:54,140
quer especificamente n.

294
00:12:54,140 --> 00:12:56,240
>> Francamente, eu diria que este
é apenas mais difícil de ler.

295
00:12:56,240 --> 00:12:58,080
É mais difícil se lembrar de onde
que os parênteses ir, o

296
00:12:58,080 --> 00:12:59,030
estrela e tudo isso.

297
00:12:59,030 --> 00:13:02,150
Assim, o mundo adotaram algum sintática
açúcar, por assim dizer.

298
00:13:02,150 --> 00:13:04,740
Apenas uma maneira sexy de dizer:
isto é equivalente, e

299
00:13:04,740 --> 00:13:05,970
talvez mais intuitiva.

300
00:13:05,970 --> 00:13:09,600
Se o ponteiro é de fato um ponteiro, o
seta significa notação ir lá e encontrar

301
00:13:09,600 --> 00:13:11,890
o campo neste caso chamado n.

302
00:13:11,890 --> 00:13:13,660
>> Então, se eu encontrá-lo, perceber o que eu faço.

303
00:13:13,660 --> 00:13:17,430
Eu simplesmente imprimir, achei por cento i,
ligar o valor para que int.

304
00:13:17,430 --> 00:13:20,730
Eu chamo de dormir por um segundo apenas para tipo
de pausa coisas na tela para

305
00:13:20,730 --> 00:13:22,900
dar ao utilizador um segundo para absorver
o que aconteceu.

306
00:13:22,900 --> 00:13:24,290
E então eu quebro.

307
00:13:24,290 --> 00:13:26,330
Caso contrário, o que eu faço?

308
00:13:26,330 --> 00:13:30,960
Eu atualizar ponteiro para igual
seta de ponteiro próximo.

309
00:13:30,960 --> 00:13:35,840
>> Então, só para deixar claro, isso significa ir
lá, usando o meu notação old-school.

310
00:13:35,840 --> 00:13:39,580
Então, isso significa apenas ir para qualquer
você está apontando para que, no muito

311
00:13:39,580 --> 00:13:43,660
primeiro caso é que eu estou apontando para
a estrutura com nove nele.

312
00:13:43,660 --> 00:13:44,510
Então eu fui lá.

313
00:13:44,510 --> 00:13:47,880
E então a notação de ponto significa,
obter o valor na próxima.

314
00:13:47,880 --> 00:13:50,470
>> Mas o valor, mesmo que seja elaborado
como um estreito, é apenas um número.

315
00:13:50,470 --> 00:13:51,720
É um endereço numérico.

316
00:13:51,720 --> 00:13:55,670
Assim, esta linha de código, se
escrito como este, o mais enigmático

317
00:13:55,670 --> 00:14:00,190
forma, ou assim, a pouco mais
forma intuitiva, significa apenas mover a minha mão

318
00:14:00,190 --> 00:14:03,460
a partir do primeiro nó para o próximo,
e, em seguida, o próximo, e então a

319
00:14:03,460 --> 00:14:05,320
seguinte, e assim por diante.

320
00:14:05,320 --> 00:14:09,920
>> Portanto, não vou me debruçar sobre o outro
implementações de inserção e exclusão

321
00:14:09,920 --> 00:14:14,030
e transversal, os dois primeiros
que são bastante envolvido.

322
00:14:14,030 --> 00:14:17,010
E eu acho que é muito fácil obter
perdido quando fazê-lo verbalmente.

323
00:14:17,010 --> 00:14:19,890
Mas o que podemos fazer aqui é
tentar determinar como

324
00:14:19,890 --> 00:14:21,640
melhor forma de fazer isso visualmente.

325
00:14:21,640 --> 00:14:24,800
Porque eu iria propor que se
deseja inserir elementos para essa

326
00:14:24,800 --> 00:14:26,680
lista existente, o que
tem cinco elementos -

327
00:14:26,680 --> 00:14:29,530
9, 17, 22, 26 e 33 -

328
00:14:29,530 --> 00:14:33,300
se eu estivesse indo para implementar isso em
código, eu preciso considerar como ir

329
00:14:33,300 --> 00:14:34,160
sobre como fazer isso.

330
00:14:34,160 --> 00:14:37,720
>> E eu gostaria de propor a dar passos de bebê
segundo a qual, neste caso, quer dizer, quais são

331
00:14:37,720 --> 00:14:41,090
os cenários possíveis que
pode encontrar em geral?

332
00:14:41,090 --> 00:14:44,120
Ao implementar inserção de um linked
lista, isso só acontece de ser um

333
00:14:44,120 --> 00:14:46,090
exemplo específico de tamanho cinco.

334
00:14:46,090 --> 00:14:50,420
Bem, se você quiser inserir um número,
como diria o número um, e

335
00:14:50,420 --> 00:14:53,380
manutenção da ordem classificada, onde
Obviamente acontece com o número um precisa

336
00:14:53,380 --> 00:14:55,686
ir neste exemplo específico?

337
00:14:55,686 --> 00:14:56,840
Tal como no início.

338
00:14:56,840 --> 00:15:00,030
>> Mas o que é interessante lá é que
Se você deseja inserir um nessa

339
00:15:00,030 --> 00:15:04,100
lista, o ponteiro necessidades especiais
ser atualizado aparentemente?

340
00:15:04,100 --> 00:15:04,610
First.

341
00:15:04,610 --> 00:15:07,830
Então, eu diria, este é o primeiro caso
que pode querer considerar um

342
00:15:07,830 --> 00:15:11,140
cenário que envolve a inserção no
o início da lista.

343
00:15:11,140 --> 00:15:15,400
>> Vamos arrancar fora talvez uma tão fácil ou mesmo
caso mais fácil, relativamente falando.

344
00:15:15,400 --> 00:15:18,110
Suponha que eu queira inserir o
número 35 em ordem de classificação.

345
00:15:18,110 --> 00:15:20,600
É, obviamente, pertence lá.

346
00:15:20,600 --> 00:15:25,320
Então, o ponteiro obviamente vai
tem que ser atualizado nesse cenário?

347
00:15:25,320 --> 00:15:30,060
Ponteiro de 34 tornando-se não nulo
mas o endereço da estrutura

348
00:15:30,060 --> 00:15:31,800
contendo o número 35.

349
00:15:31,800 --> 00:15:32,750
Então, isso é caso dois.

350
00:15:32,750 --> 00:15:36,190
Então, já, eu sou uma espécie de quantização
a quantidade de trabalho que tenho que fazer aqui.

351
00:15:36,190 --> 00:15:39,880
>> E, finalmente, no caso do meio é óbvio
de fato, no meio, se eu quiser

352
00:15:39,880 --> 00:15:45,870
inserir algo como dizer 23, que vai
entre os 23 e os 26, mas

353
00:15:45,870 --> 00:15:48,680
Agora as coisas ficam um pouco mais
envolvido, porque o que

354
00:15:48,680 --> 00:15:52,800
ponteiros precisa ser mudado?

355
00:15:52,800 --> 00:15:56,680
Então, 22 obviamente precisa ser mudado
porque ele não pode apontar mais de 26.

356
00:15:56,680 --> 00:16:00,320
Ele precisa apontar para o novo nó
Eu vou ter que alocar chamando

357
00:16:00,320 --> 00:16:01,770
malloc ou algum equivalente.

358
00:16:01,770 --> 00:16:05,990
>> Mas, então, eu também preciso que o novo nó, 23
neste caso, que a sua ponteiro

359
00:16:05,990 --> 00:16:07,870
apontando para quem?

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
E aí, vai ser uma
ordem das operações aqui.

362
00:16:10,380 --> 00:16:13,410
Porque se eu fizer isso loucamente, e eu
por exemplo, no início do começo

363
00:16:13,410 --> 00:16:16,040
da lista, e meu objetivo é inserir 23.

364
00:16:16,040 --> 00:16:18,610
E eu verificar, ele pertence
aqui, perto de nove?

365
00:16:18,610 --> 00:16:18,950
Não.

366
00:16:18,950 --> 00:16:20,670
Será que é aqui, ao lado de 17?

367
00:16:20,670 --> 00:16:20,940
Não.

368
00:16:20,940 --> 00:16:22,530
Será que ela pertence aqui ao lado de 22?

369
00:16:22,530 --> 00:16:23,300
Sim.

370
00:16:23,300 --> 00:16:26,400
>> Agora, se eu sou tolo aqui, e não
pensando sobre isso, eu poderia

371
00:16:26,400 --> 00:16:28,320
alocar meu novo nó para 23.

372
00:16:28,320 --> 00:16:32,080
Posso atualizar o ponteiro da
o nó chamado 22, apontando

373
00:16:32,080 --> 00:16:33,080
em que o novo nó.

374
00:16:33,080 --> 00:16:36,140
E então o que eu tenho que atualizar
ponteiro do novo nó a ser?

375
00:16:36,140 --> 00:16:38,120
>> Estudante: [inaudível].

376
00:16:38,120 --> 00:16:38,385
>> COLUNA 1: Exatamente.

377
00:16:38,385 --> 00:16:39,710
Apontando para 26.

378
00:16:39,710 --> 00:16:45,590
Mas caramba, se eu já não atualizar
Ponteiro de 22 para apontar para esse cara, e

379
00:16:45,590 --> 00:16:48,260
agora eu tenho órfãos, o resto
da lista, por assim dizer.

380
00:16:48,260 --> 00:16:52,140
Assim, a ordem das operações aqui
vai ser importante.

381
00:16:52,140 --> 00:16:55,100
>> Para fazer isso eu poderia roubar,
digamos, seis voluntários.

382
00:16:55,100 --> 00:16:57,650
E vamos ver se a gente não pode fazer isso
visualmente em vez de código-wise.

383
00:16:57,650 --> 00:16:59,330
E temos alguns adorável estresse
bolas para você hoje.

384
00:16:59,330 --> 00:17:02,510
OK, como sobre um, dois, no
de volta - no final lá.

385
00:17:02,510 --> 00:17:04,530
três, quatro, tanto de você
caras no final.

386
00:17:04,530 --> 00:17:05,579
E, cinco, seis.

387
00:17:05,579 --> 00:17:05,839
Claro.

388
00:17:05,839 --> 00:17:06,450
Cinco e seis.

389
00:17:06,450 --> 00:17:08,390
Tudo bem e nós viremos
para vocês da próxima vez.

390
00:17:08,390 --> 00:17:09,640
Tudo bem, vamos lá para cima.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> Tudo bem, desde que você está aqui em primeiro lugar,
gostaria de ser o único jeito

393
00:17:14,819 --> 00:17:16,119
no vidro Google aqui?

394
00:17:16,119 --> 00:17:19,075
Tudo bem, então, OK, Vidro,
gravar um vídeo.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
OK, você está pronto para ir.

397
00:17:24,589 --> 00:17:27,950
>> Tudo bem, então se vocês podem vir
aqui, eu preparei com antecedência

398
00:17:27,950 --> 00:17:30,110
alguns números.

399
00:17:30,110 --> 00:17:31,240
Tudo bem, venha até aqui.

400
00:17:31,240 --> 00:17:33,440
E por que não ir um pouco
ainda mais dessa forma.

401
00:17:33,440 --> 00:17:35,520
E vamos ver, qual é o seu nome,
com o vidro Google?

402
00:17:35,520 --> 00:17:35,910
>> ALUNO: Ben.

403
00:17:35,910 --> 00:17:36,230
>> COLUNA 1: Ben?

404
00:17:36,230 --> 00:17:38,380
OK, Ben, você vai ser o primeiro, literalmente.

405
00:17:38,380 --> 00:17:40,580
Por isso, vamos enviar-lhe
para o final da etapa.

406
00:17:40,580 --> 00:17:41,670
Tudo bem, e seu nome?

407
00:17:41,670 --> 00:17:41,990
>> ALUNO: Jason.

408
00:17:41,990 --> 00:17:44,530
>> COLUNA 1: Jason, OK você vai
ser o número nove.

409
00:17:44,530 --> 00:17:46,700
Então, se você quer seguir Ben dessa forma.

410
00:17:46,700 --> 00:17:47,010
>> ALUNO: Jill.

411
00:17:47,010 --> 00:17:49,630
>> COLUNA 1: Jill, você está indo para ser
17, que se eu tivesse feito isso mais

412
00:17:49,630 --> 00:17:51,260
inteligente, eu teria
iniciada na outra extremidade.

413
00:17:51,260 --> 00:17:52,370
Você ir por esse caminho.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
E você é?

416
00:17:53,670 --> 00:17:53,980
>> ALUNO: Mary.

417
00:17:53,980 --> 00:17:56,130
>> COLUNA 1: Mary, você vai ser 22.

418
00:17:56,130 --> 00:17:58,420
E o seu nome é?

419
00:17:58,420 --> 00:17:58,810
>> ALUNO: Chris.

420
00:17:58,810 --> 00:18:00,100
>> COLUNA 1: Chris, você vai ser 26.

421
00:18:00,100 --> 00:18:00,740
E então, finalmente.

422
00:18:00,740 --> 00:18:01,400
>> ALUNO: Diana.

423
00:18:01,400 --> 00:18:02,670
>> COLUNA 1: Diana, você vai ser 34.

424
00:18:02,670 --> 00:18:03,920
Então você vem aqui.

425
00:18:03,920 --> 00:18:06,360
>> Tudo bem, tão perfeito classificadas
encomendar já.

426
00:18:06,360 --> 00:18:09,600
E vamos em frente e fazer isso
para que possamos realmente -

427
00:18:09,600 --> 00:18:11,720
Ben você é apenas o tipo de procura
fora em nada lá.

428
00:18:11,720 --> 00:18:15,670
OK, então vamos seguir em frente e descrever esta
usando armas, bem como eu era, exatamente,

429
00:18:15,670 --> 00:18:16,250
o que está acontecendo.

430
00:18:16,250 --> 00:18:19,540
Então vá em frente e dar-vos um
pé ou dois entre vós.

431
00:18:19,540 --> 00:18:22,900
E vá em frente e apontar com uma mão para
quem você deve estar apontando para

432
00:18:22,900 --> 00:18:23,470
com base nesta.

433
00:18:23,470 --> 00:18:25,890
E se você é nula apenas apontar
direto para o chão.

434
00:18:25,890 --> 00:18:27,690
OK, tudo bem.

435
00:18:27,690 --> 00:18:32,290
>> Portanto, agora temos uma lista ligada, e deixe-me
propor que eu vou desempenhar o papel de

436
00:18:32,290 --> 00:18:35,110
PTR, então eu não vou incomodar
levando esta ao redor.

437
00:18:35,110 --> 00:18:37,830
E então - alguém convenção estúpida -
você pode chamar isso de qualquer coisa que você quiser -

438
00:18:37,830 --> 00:18:39,800
ponteiro predecessor, ponteiro pred -

439
00:18:39,800 --> 00:18:43,930
é apenas o apelido que demos em
nosso código de exemplo para minha mão esquerda.

440
00:18:43,930 --> 00:18:47,240
O outro lado, que vai ser manter
o controle de quem é quem no

441
00:18:47,240 --> 00:18:48,400
seguintes cenários.

442
00:18:48,400 --> 00:18:52,390
>> Então suponho que, em primeiro lugar, quero arrancar fora
aquele primeiro exemplo de inserção de, digamos

443
00:18:52,390 --> 00:18:54,330
20, na lista.

444
00:18:54,330 --> 00:18:57,160
Então, eu vou precisar de alguém para
encarnam o número 20 para nós.

445
00:18:57,160 --> 00:18:58,950
Então eu preciso de alguém para malloc
da platéia.

446
00:18:58,950 --> 00:18:59,380
Vamos para cima.

447
00:18:59,380 --> 00:19:00,340
Qual é o seu nome?

448
00:19:00,340 --> 00:19:01,300
>> ALUNO: Brian.

449
00:19:01,300 --> 00:19:05,270
>> COLUNA 1: Brian tudo bem, então você
deve ser o nó que contém 20.

450
00:19:05,270 --> 00:19:06,810
Tudo bem, venha até aqui.

451
00:19:06,810 --> 00:19:10,025
E, obviamente, onde
Brian não pertence?

452
00:19:10,025 --> 00:19:12,190
Assim, no meio de - na verdade,
espere um minuto.

453
00:19:12,190 --> 00:19:13,420
Estamos fazendo isso para fora de ordem.

454
00:19:13,420 --> 00:19:17,170
Nós estamos fazendo isso muito mais difícil
do que ele precisa estar em primeiro lugar.

455
00:19:17,170 --> 00:19:21,210
OK, vamos livre Brian
e realloc Brian cinco.

456
00:19:21,210 --> 00:19:23,680
>> OK, então agora queremos inserir
Brian como cinco.

457
00:19:23,680 --> 00:19:25,960
Então venha aqui ao lado
Ben só por um momento.

458
00:19:25,960 --> 00:19:28,250
E você pode dizer presumivelmente
onde essa história vai dar.

459
00:19:28,250 --> 00:19:30,500
Mas vamos pensar cuidadosamente sobre
a ordem das operações.

460
00:19:30,500 --> 00:19:32,880
E é precisamente esta visuais
que vai alinhar

461
00:19:32,880 --> 00:19:34,080
com esse código de amostra.

462
00:19:34,080 --> 00:19:40,120
Então, aqui eu PTR apontando inicialmente
não em Ben, por si só, mas em qualquer

463
00:19:40,120 --> 00:19:43,245
valor que ele contém, o que neste caso
é - qual é o seu nome?

464
00:19:43,245 --> 00:19:43,670
>> ALUNO: Jason.

465
00:19:43,670 --> 00:19:47,350
>> COLUNA 1: Jason, então Ben e eu somos
apontando para Jason neste momento.

466
00:19:47,350 --> 00:19:49,700
Então agora eu tenho de determinar,
onde é que Brian pertence?

467
00:19:49,700 --> 00:19:53,500
Então a única coisa que eu tenho acesso a
agora é o item de dados n.

468
00:19:53,500 --> 00:19:58,280
Então eu vou dar uma olhada, é
Brian menos de Jason?

469
00:19:58,280 --> 00:19:59,770
A resposta é verdadeira.

470
00:19:59,770 --> 00:20:03,680
>> Então, o que precisa agora de acontecer,
na ordem correta?

471
00:20:03,680 --> 00:20:07,120
Eu preciso atualizar quantos ponteiros
no total nesta história?

472
00:20:07,120 --> 00:20:10,720
Onde minha mão ainda está apontando para
Jason, e sua mão - se você quiser

473
00:20:10,720 --> 00:20:12,930
colocar a mão como, de alguma forma, eu
Não sei, um ponto de interrogação.

474
00:20:12,930 --> 00:20:14,070
OK, bom.

475
00:20:14,070 --> 00:20:15,670
>> Tudo bem, então você tem
alguns candidatos.

476
00:20:15,670 --> 00:20:20,500
Ou Ben ou eu ou Brian ou Jason
ou qualquer outra pessoa, que

477
00:20:20,500 --> 00:20:21,370
ponteiros precisa mudar?

478
00:20:21,370 --> 00:20:23,260
Quantos ao todo?

479
00:20:23,260 --> 00:20:24,080
>> OK, então dois.

480
00:20:24,080 --> 00:20:27,090
Meu ponteiro realmente não importa mais
porque eu sou apenas temporária.

481
00:20:27,090 --> 00:20:31,370
Por isso, é esses dois caras, presumivelmente,
Ben e Brian.

482
00:20:31,370 --> 00:20:34,410
Então deixe-me propor que nós atualizamos
Ben, já que ele está em primeiro lugar.

483
00:20:34,410 --> 00:20:36,350
O primeiro elemento da lista
agora vai ser Brian.

484
00:20:36,350 --> 00:20:38,070
Assim ponto Ben em Brian.

485
00:20:38,070 --> 00:20:39,320
OK, e agora?

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> Quem fica apontada para quem?

488
00:20:43,460 --> 00:20:44,710
>> Estudante: [inaudível].

489
00:20:44,710 --> 00:20:46,180
>> COLUNA 1: OK, então Brian tem
para apontar para Jason.

490
00:20:46,180 --> 00:20:48,360
Mas o que eu perdi a noção do que ponteiro?

491
00:20:48,360 --> 00:20:49,980
Não sei onde Jason é?

492
00:20:49,980 --> 00:20:50,790
>> Estudante: [inaudível].

493
00:20:50,790 --> 00:20:52,620
>> COLUNA 1: eu faço, desde que eu sou
o ponteiro temporária.

494
00:20:52,620 --> 00:20:55,110
E, presumivelmente, não mudei
para apontar para o novo nó.

495
00:20:55,110 --> 00:20:58,300
Assim, podemos simplesmente ter ponto de Brian
em quem eu estou apontando.

496
00:20:58,300 --> 00:20:59,000
E estamos a fazer.

497
00:20:59,000 --> 00:21:01,890
Assim, um caso, a inserção na
início da lista.

498
00:21:01,890 --> 00:21:02,950
Havia dois passos fundamentais.

499
00:21:02,950 --> 00:21:06,750
Um deles, temos que atualizar Ben, e, em seguida,
nós também temos que atualizar Brian.

500
00:21:06,750 --> 00:21:09,230
E então eu não tem que se preocupar
perambulando pelo resto da

501
00:21:09,230 --> 00:21:12,680
lista, porque já encontrou o seu
localização, porque ele pertencia ao

502
00:21:12,680 --> 00:21:14,080
esquerda do primeiro elemento.

503
00:21:14,080 --> 00:21:15,400
>> Tudo bem, então bastante simples.

504
00:21:15,400 --> 00:21:18,110
Na verdade, parece que estamos quase
fazendo isso muito complicado.

505
00:21:18,110 --> 00:21:20,240
Então, vamos agora arrancar fora da final
da lista, e ver onde

506
00:21:20,240 --> 00:21:21,380
a complexidade começa.

507
00:21:21,380 --> 00:21:24,560
Então, se agora eu alocação da platéia.

508
00:21:24,560 --> 00:21:25,540
Qualquer um quer jogar 55?

509
00:21:25,540 --> 00:21:26,700
Tudo bem, eu vi o seu em primeira mão.

510
00:21:26,700 --> 00:21:29,620
Venha.

511
00:21:29,620 --> 00:21:30,030
Sim.

512
00:21:30,030 --> 00:21:31,177
Qual é o seu nome?

513
00:21:31,177 --> 00:21:32,310
>> Estudante: [inaudível].

514
00:21:32,310 --> 00:21:33,240
>> COLUNA 1: Habata.

515
00:21:33,240 --> 00:21:33,890
OK, vamos lá para cima.

516
00:21:33,890 --> 00:21:35,730
Você vai ser o número 55.

517
00:21:35,730 --> 00:21:37,820
Então, você, naturalmente, pertencem
no fim da lista.

518
00:21:37,820 --> 00:21:41,850
Então, vamos repetir a simulação comigo
sendo o PTR só por um momento.

519
00:21:41,850 --> 00:21:44,050
Então, eu estou indo primeiro para apontar
o que Ben está apontando.

520
00:21:44,050 --> 00:21:45,900
Nós dois estamos apontando agora em Brian.

521
00:21:45,900 --> 00:21:48,420
Assim, 55 não é menos do que cinco.

522
00:21:48,420 --> 00:21:52,510
Então eu vou me atualizar por
apontando para o próximo ponteiro de Brian, que

523
00:21:52,510 --> 00:21:54,450
agora é, naturalmente, Jason.

524
00:21:54,450 --> 00:21:57,310
55 não seja inferior a nove, de modo
Vou atualizar PTR.

525
00:21:57,310 --> 00:21:58,890
Vou atualizar PTR.

526
00:21:58,890 --> 00:22:02,290
Vou atualizar PTR
Eu vou atualizar PTR.

527
00:22:02,290 --> 00:22:05,060
E eu vou to - Hum, o que é
o seu nome?

528
00:22:05,060 --> 00:22:05,560
>> ALUNO: Diana.

529
00:22:05,560 --> 00:22:09,190
>> COLUNA 1: Diana está apontando, é claro,
no nulo com a mão esquerda.

530
00:22:09,190 --> 00:22:13,030
Então onde é que realmente Habata
pertencem claramente?

531
00:22:13,030 --> 00:22:15,050
Para o lado esquerdo, aqui.

532
00:22:15,050 --> 00:22:19,460
Então, como é que eu sei para colocá-la aqui
Eu acho que eu estraguei tudo.

533
00:22:19,460 --> 00:22:22,420
Porque o que é PTR arte
neste momento?

534
00:22:22,420 --> 00:22:23,240
Nulo.

535
00:22:23,240 --> 00:22:25,580
Assim, mesmo que, visualmente, o que pudermos
ver, obviamente, tudo isso

536
00:22:25,580 --> 00:22:26,610
caras aqui no palco.

537
00:22:26,610 --> 00:22:29,680
Eu não tenho mantido a par do anterior
pessoa na lista.

538
00:22:29,680 --> 00:22:33,210
Eu não tenho um dedo apontando para fora,
neste caso, o número de nó 34.

539
00:22:33,210 --> 00:22:34,760
>> Então, vamos começar esta acabado.

540
00:22:34,760 --> 00:22:37,560
Então, agora eu realmente preciso
uma segunda variável local.

541
00:22:37,560 --> 00:22:40,980
E isso é o que você verá no
código C amostra real, onde, como eu vou,

542
00:22:40,980 --> 00:22:45,860
quando eu atualizar a minha mão direita para apontar
Jason, deixando, assim, Brian atrás, eu

543
00:22:45,860 --> 00:22:51,440
melhor começar a usar a mão esquerda para
atualizar onde eu estava, para que, como eu vou

544
00:22:51,440 --> 00:22:52,700
através desta lista -

545
00:22:52,700 --> 00:22:55,040
mais sem jeito do que eu pretendia
agora aqui visualmente -

546
00:22:55,040 --> 00:22:56,740
Vou chegar ao
fim da lista.

547
00:22:56,740 --> 00:23:00,020
>> Esta mão ainda é nulo, o que é bastante
inútil, excepto para indicar

548
00:23:00,020 --> 00:23:02,980
Sou claramente no final da lista
mas agora pelo menos eu tenho essa

549
00:23:02,980 --> 00:23:08,270
ponteiro predecessor apontando aqui, então
agora que as mãos e os ponteiros que precisa

550
00:23:08,270 --> 00:23:10,150
para ser atualizado?

551
00:23:10,150 --> 00:23:13,214
Cuja mão que você quer
reconfigurar primeiro?

552
00:23:13,214 --> 00:23:15,190
>> Estudante: [inaudível].

553
00:23:15,190 --> 00:23:16,220
>> COLUNA 1: OK, então Diana.

554
00:23:16,220 --> 00:23:21,110
Onde você quer apontar
Ponteiro para a esquerda de Diana at?

555
00:23:21,110 --> 00:23:23,620
Aos 55 anos, presume-se, de modo que
temos inserido lá.

556
00:23:23,620 --> 00:23:25,560
E onde deve 55 ponteiro ir?

557
00:23:25,560 --> 00:23:27,000
Para baixo, representando nulo.

558
00:23:27,000 --> 00:23:28,890
E minhas mãos, neste momento, não
importa, porque eles eram apenas

559
00:23:28,890 --> 00:23:30,070
variáveis ​​temporárias.

560
00:23:30,070 --> 00:23:31,030
Portanto, agora estamos a fazer.

561
00:23:31,030 --> 00:23:34,650
>> Assim, a complexidade adicional ali - e
não é assim tão difícil de implementar,

562
00:23:34,650 --> 00:23:38,660
mas precisamos de uma variável secundária para fazer
certeza de que antes de eu mudar a minha direita

563
00:23:38,660 --> 00:23:42,140
lado, eu atualizar o valor do meu lado esquerdo
lado, o ponteiro de pred, neste caso, de modo

564
00:23:42,140 --> 00:23:45,860
que eu tenho um ponteiro de arrasto
manter o controle de onde eu estava.

565
00:23:45,860 --> 00:23:49,360
Agora, como um aparte, se você está pensando que isso
passar, isso se sente como se fosse um

566
00:23:49,360 --> 00:23:51,490
pouco chato ter que manter
acompanhar desta mão esquerda.

567
00:23:51,490 --> 00:23:54,015
>> Qual seria outra solução
para este problema têm sido?

568
00:23:54,015 --> 00:23:56,500
Se você tem que redesenhar os dados
estrutura que estamos falando

569
00:23:56,500 --> 00:23:59,630
por agora?

570
00:23:59,630 --> 00:24:02,690
Se este tipo de apenas se sente um pouco
chato ter, tipo, dois ponteiros

571
00:24:02,690 --> 00:24:08,430
passando a lista, quem mais poderia
ter, em um mundo ideal, mantido

572
00:24:08,430 --> 00:24:10,160
informações de que precisamos?

573
00:24:10,160 --> 00:24:11,360
Sim?

574
00:24:11,360 --> 00:24:12,610
>> Estudante: [inaudível].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> COLUNA 1: Exatamente.

577
00:24:16,150 --> 00:24:19,130
Direito então não há realmente uma interessante
germe de uma idéia.

578
00:24:19,130 --> 00:24:22,470
E essa idéia de um ponteiro anterior,
apontando para o elemento anterior.

579
00:24:22,470 --> 00:24:25,580
E se eu apenas incorporada que
dentro da própria lista?

580
00:24:25,580 --> 00:24:27,810
E isso vai ser difícil de visualizar
isso sem todo o papel

581
00:24:27,810 --> 00:24:28,830
caindo no chão.

582
00:24:28,830 --> 00:24:31,860
Mas suponha que esses caras usado tanto
das suas mãos para uma prévia

583
00:24:31,860 --> 00:24:35,950
ponteiro, e um ponteiro próximo, assim
implementar o que vamos chamar um duplamente

584
00:24:35,950 --> 00:24:36,830
lista ligada.

585
00:24:36,830 --> 00:24:41,090
Isso me permitiria classificar de rewind,
muito mais facilmente, sem mim, o

586
00:24:41,090 --> 00:24:43,800
programador, ter de manter
controlar manualmente -

587
00:24:43,800 --> 00:24:44,980
verdadeiramente manualmente -

588
00:24:44,980 --> 00:24:47,280
de onde eu tinha sido anteriormente
na lista.

589
00:24:47,280 --> 00:24:48,110
Portanto, não vamos fazer isso.

590
00:24:48,110 --> 00:24:50,950
Vamos mantê-lo simples, porque isso é
vai ter um preço, duas vezes mais

591
00:24:50,950 --> 00:24:53,450
muito mais espaço para os ponteiros,
se você quiser um segundo.

592
00:24:53,450 --> 00:24:55,760
Mas isso é de fato um comum
estrutura de dados conhecida como um

593
00:24:55,760 --> 00:24:57,410
lista duplamente ligada.

594
00:24:57,410 --> 00:25:01,310
>> Vamos fazer o último exemplo aqui e colocar
esses caras fora de sua miséria.

595
00:25:01,310 --> 00:25:03,270
Então malloc 20.

596
00:25:03,270 --> 00:25:05,320
Vamos para cima do corredor lá.

597
00:25:05,320 --> 00:25:06,280
Tudo bem, qual é o seu nome?

598
00:25:06,280 --> 00:25:07,440
>> Estudante: [inaudível].

599
00:25:07,440 --> 00:25:07,855
>> COLUNA 1: Desculpe?

600
00:25:07,855 --> 00:25:08,480
>> Estudante: [inaudível].

601
00:25:08,480 --> 00:25:09,410
>> COLUNA 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
OK vamos lá para cima.

603
00:25:10,230 --> 00:25:11,910
Você deve ser 20.

604
00:25:11,910 --> 00:25:14,720
Você, obviamente, vai
pertencer entre 17 e 22.

605
00:25:14,720 --> 00:25:16,150
Então deixe-me aprender a lição.

606
00:25:16,150 --> 00:25:18,150
Eu vou começar ponteiro
apontando para Brian.

607
00:25:18,150 --> 00:25:21,190
E eu vou ter a minha mão esquerda
apenas atualizar a Brian como eu passar para

608
00:25:21,190 --> 00:25:23,600
Jason, verificação faz 20 a menos do que nove?

609
00:25:23,600 --> 00:25:24,060
Não.

610
00:25:24,060 --> 00:25:25,430
É de 20 a menos de 17 anos?

611
00:25:25,430 --> 00:25:25,880
Não.

612
00:25:25,880 --> 00:25:27,450
É de 20 a menos de 22?

613
00:25:27,450 --> 00:25:28,440
Sim.

614
00:25:28,440 --> 00:25:34,070
Então, o que os ponteiros ou mãos precisa mudar
onde eles estão apontando agora?

615
00:25:34,070 --> 00:25:37,070
>> Assim, podemos fazer 17 apontando para 20.

616
00:25:37,070 --> 00:25:37,860
Então, isso é bom.

617
00:25:37,860 --> 00:25:40,080
Onde queremos apontar
o ponteiro agora?

618
00:25:40,080 --> 00:25:41,330
Aos 22 anos.

619
00:25:41,330 --> 00:25:45,410
E nós sabemos que 22 é, mais uma vez, graças
ao meu ponteiro temporário.

620
00:25:45,410 --> 00:25:46,760
Então, nós estamos OK lá.

621
00:25:46,760 --> 00:25:49,440
Assim, devido a esta armazenagem temporária
Eu mantive o controle de onde toda a gente é.

622
00:25:49,440 --> 00:25:55,055
E agora você pode ir para onde visualmente
você pertence, e agora precisamos de 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 bolas de stress,
e uma salva de palmas para

624
00:25:58,410 --> 00:25:59,770
esses caras, se pudéssemos.

625
00:25:59,770 --> 00:26:00,410
Bem feito.

626
00:26:00,410 --> 00:26:05,320
>> [Aplausos]

627
00:26:05,320 --> 00:26:06,330
>> COLUNA 1: Tudo bem.

628
00:26:06,330 --> 00:26:09,860
E você pode manter as peças
de papel como lembranças.

629
00:26:09,860 --> 00:26:15,930
>> Tudo bem, então, confie em mim é muito
mais fácil entrar por aquela com

630
00:26:15,930 --> 00:26:17,680
os seres humanos do que com código real.

631
00:26:17,680 --> 00:26:22,690
Mas o que você vai encontrar em um momento
agora, é o mesmo - oh, muito obrigado.

632
00:26:22,690 --> 00:26:23,630
Obrigado -

633
00:26:23,630 --> 00:26:29,360
é que você vai descobrir que os mesmos dados
estrutura, uma lista ligada, pode realmente

634
00:26:29,360 --> 00:26:33,200
ser utilizado como um bloco de construção de ainda mais
estruturas de dados sofisticadas.

635
00:26:33,200 --> 00:26:37,620
>> E perceber também o tema aqui é que
temos absolutamente introduziu mais

636
00:26:37,620 --> 00:26:40,060
complexidade na implementação
deste algoritmo.

637
00:26:40,060 --> 00:26:43,940
Inserção, e se passou por isso,
exclusão e consulta, é um pouco

638
00:26:43,940 --> 00:26:46,660
mais complicado do que
Foi com uma matriz.

639
00:26:46,660 --> 00:26:48,040
Mas ganhar algum dinamismo.

640
00:26:48,040 --> 00:26:50,180
Nós temos uma estrutura de dados adaptativa.

641
00:26:50,180 --> 00:26:54,010
>> Mas, novamente, nós pagamos um preço de ter algum
complexidade adicional, tanto em

642
00:26:54,010 --> 00:26:54,910
implementá-lo.

643
00:26:54,910 --> 00:26:56,750
E estamos desistido de acesso aleatório.

644
00:26:56,750 --> 00:27:00,450
E para ser honesto, não há um bom
limpar slides posso dar-lhe que

645
00:27:00,450 --> 00:27:03,120
Diz aqui que é por isso que uma lista ligada
é melhor do que uma matriz.

646
00:27:03,120 --> 00:27:04,100
E deixar por isso mesmo.

647
00:27:04,100 --> 00:27:07,520
Porque o tema recorrente agora, mesmo
mais ainda nas próximas semanas, é

648
00:27:07,520 --> 00:27:10,200
que não há necessariamente
uma resposta correta.

649
00:27:10,200 --> 00:27:13,830
>> É por isso que temos o eixo separado
do projeto para conjuntos de problemas.

650
00:27:13,830 --> 00:27:17,700
Vai ser muito sensível ao contexto
se você quiser usar esses dados

651
00:27:17,700 --> 00:27:21,750
estrutura ou aquele, e vai
depende do que é importante para você em termos

652
00:27:21,750 --> 00:27:24,620
de recursos e complexidade.

653
00:27:24,620 --> 00:27:28,830
>> Mas deixe-me propor que os dados ideais
estrutura, o santo graal, seria

654
00:27:28,830 --> 00:27:32,200
algo que é constante de tempo,
independentemente da quantidade de material é

655
00:27:32,200 --> 00:27:36,940
dentro dele, não seria surpreendente se um
estrutura de dados retornou respostas

656
00:27:36,940 --> 00:27:37,920
tempo constante.

657
00:27:37,920 --> 00:27:38,330
Sim.

658
00:27:38,330 --> 00:27:40,110
Esta palavra está na sua enorme dicionário.

659
00:27:40,110 --> 00:27:41,550
Ou não, esta palavra não é.

660
00:27:41,550 --> 00:27:43,270
Ou qualquer problema desse tipo lá.

661
00:27:43,270 --> 00:27:46,360
Bem, vamos ver se a gente não pode, pelo menos
dar um passo em direção a isso.

662
00:27:46,360 --> 00:27:50,190
>> Deixe-me propor uma nova estrutura de dados que
pode ser usado para diferentes coisas,

663
00:27:50,190 --> 00:27:52,260
neste caso denominada tabela hash.

664
00:27:52,260 --> 00:27:55,590
E por isso estamos realmente olhando para trás
em uma matriz, no caso em apreço, e

665
00:27:55,590 --> 00:28:00,550
arbitrariamente, eu desenhei esta
tabela hash como uma matriz com uma espécie de

666
00:28:00,550 --> 00:28:02,810
matriz bidimensional -

667
00:28:02,810 --> 00:28:05,410
ou melhor, ele é descrito aqui como um dois
matriz dimensional - mas este é apenas

668
00:28:05,410 --> 00:28:10,770
uma matriz de tamanho 26, de tal modo que se
chamar a tabela da matriz, suporte de mesa

669
00:28:10,770 --> 00:28:12,440
zero é o rectângulo no topo.

670
00:28:12,440 --> 00:28:15,090
Tabela suporte 25 é o retângulo
na parte inferior.

671
00:28:15,090 --> 00:28:18,620
E é assim que eu poderia chamar um conjunto de dados
estrutura em que deseja armazenar

672
00:28:18,620 --> 00:28:19,790
nomes de pessoas.

673
00:28:19,790 --> 00:28:24,370
>> Assim, por exemplo, e eu não vou chamar a
coisa toda aqui no alto, se eu

674
00:28:24,370 --> 00:28:29,160
tinha essa matriz, que eu estou indo agora para
chamar uma tabela hash, e este é novamente

675
00:28:29,160 --> 00:28:31,360
Local de zero.

676
00:28:31,360 --> 00:28:34,840
Esta aqui é a localização
um, e assim por diante.

677
00:28:34,840 --> 00:28:37,880
Eu afirmo que eu quero usar esses dados
estrutura, por causa da discussão,

678
00:28:37,880 --> 00:28:42,600
para armazenar os nomes das pessoas, Alice e Bob
e Charlie e outros nomes.

679
00:28:42,600 --> 00:28:46,110
Então, pense nisso agora, como o início
de, digamos, um dicionário

680
00:28:46,110 --> 00:28:47,520
com muitas palavras.

681
00:28:47,520 --> 00:28:49,435
Elas acontecem para ser nomes
No nosso exemplo aqui.

682
00:28:49,435 --> 00:28:52,560
E tudo isso é muito pertinente, talvez, para
implementação de um corretor ortográfico, como

683
00:28:52,560 --> 00:28:54,400
talvez para o problema de definir seis.

684
00:28:54,400 --> 00:28:59,300
>> Então, se temos uma matriz de tamanho total 26
de modo que este é o local 25

685
00:28:59,300 --> 00:29:03,390
na parte inferior, e eu afirmo que Alice é
a primeira palavra no dicionário de

686
00:29:03,390 --> 00:29:07,260
nomes que eu quero inserir na RAM,
para essa estrutura de dados, onde estão

687
00:29:07,260 --> 00:29:12,480
instintos dizendo que Alice
nome deve ir neste array?

688
00:29:12,480 --> 00:29:13,510
>> Temos 26 opções.

689
00:29:13,510 --> 00:29:14,990
Onde queremos colocá-la?

690
00:29:14,990 --> 00:29:16,200
Queremos que ela no suporte zero, certo?

691
00:29:16,200 --> 00:29:18,280
Um para Alice, vamos chamar isso de zero.

692
00:29:18,280 --> 00:29:20,110
E B será um, e C será de dois.

693
00:29:20,110 --> 00:29:22,600
Então, vamos escrever
Nome aqui em cima de Alice.

694
00:29:22,600 --> 00:29:24,890
Se, então, inserir Bob, seu
nome vai aqui.

695
00:29:24,890 --> 00:29:27,280
Charlie vai passar aqui.

696
00:29:27,280 --> 00:29:30,500
E assim por diante ao longo
esta estrutura de dados.

697
00:29:30,500 --> 00:29:32,090
>> Esta é uma estrutura de dados maravilhoso.

698
00:29:32,090 --> 00:29:32,730
Por quê?

699
00:29:32,730 --> 00:29:37,460
Bem, o que é o tempo de execução
inserir o nome de um humano para esta

700
00:29:37,460 --> 00:29:39,850
estrutura de dados agora?

701
00:29:39,850 --> 00:29:43,702
Dado que esta tabela é implementado,
verdadeiramente, como uma matriz.

702
00:29:43,702 --> 00:29:44,940
Bem, é tempo constante.

703
00:29:44,940 --> 00:29:45,800
É fim de um.

704
00:29:45,800 --> 00:29:46,360
Por quê?

705
00:29:46,360 --> 00:29:48,630
>> Bem, como você determina
onde Alice pertence?

706
00:29:48,630 --> 00:29:51,000
Você olha para qual letra do seu nome?

707
00:29:51,000 --> 00:29:51,490
O primeiro.

708
00:29:51,490 --> 00:29:54,350
E você pode chegar lá, se é uma string,
apenas olhando para cadeia

709
00:29:54,350 --> 00:29:55,200
Suporte de zero.

710
00:29:55,200 --> 00:29:57,110
Assim, o caráter zeroth da cadeia.

711
00:29:57,110 --> 00:29:57,610
Isso é fácil.

712
00:29:57,610 --> 00:30:00,350
Fizemos isso no crypto
semanas de atribuição atrás.

713
00:30:00,350 --> 00:30:05,310
E então quando você sabe que Alice
A carta é a capital, podemos subtrair

714
00:30:05,310 --> 00:30:08,160
off 65 ou maiúsculo si,
que nos dá zero.

715
00:30:08,160 --> 00:30:10,940
Portanto, sabemos agora que Alice pertence
na posição zero.

716
00:30:10,940 --> 00:30:14,240
>> E dado um ponteiro a estes dados
estrutura, de alguma sorte, o tempo faz

717
00:30:14,240 --> 00:30:18,840
ele me levar para encontrar a localização
zero em um array?

718
00:30:18,840 --> 00:30:22,080
Apenas um passo, certo É hora constante
devido a que o acesso aleatório

719
00:30:22,080 --> 00:30:23,780
proposta era uma característica de uma matriz.

720
00:30:23,780 --> 00:30:28,570
Assim, em breve, descobrir o que o índice
do nome de Alice é, que é, em

721
00:30:28,570 --> 00:30:32,610
Neste caso, é A, ou vamos apenas resolver
que a zero, em que B é um C e é

722
00:30:32,610 --> 00:30:34,900
dois, imaginando que fora
É tempo constante.

723
00:30:34,900 --> 00:30:38,510
Eu só tenho que olhar para a sua primeira carta,
descobrir onde zero é um

724
00:30:38,510 --> 00:30:40,460
matriz também é de tempo constante.

725
00:30:40,460 --> 00:30:42,140
Então, tecnicamente isso é
como dois passos agora.

726
00:30:42,140 --> 00:30:43,330
Mas isso ainda é constante.

727
00:30:43,330 --> 00:30:46,880
Então, nós chamamos isso de um grande O, então nós
Alice inserido nesta tabela em

728
00:30:46,880 --> 00:30:48,440
tempo constante.

729
00:30:48,440 --> 00:30:50,960
>> Mas, claro, eu estou sendo
ingênuo aqui, certo?

730
00:30:50,960 --> 00:30:53,240
E se há uma Aaron na classe?

731
00:30:53,240 --> 00:30:53,990
Ou Alicia?

732
00:30:53,990 --> 00:30:57,230
Ou quaisquer outros nomes começando com
A. Onde vamos colocar

733
00:30:57,230 --> 00:31:00,800
essa pessoa, certo?

734
00:31:00,800 --> 00:31:03,420
Quero dizer, agora há apenas três
pessoas sobre a mesa, então talvez nós

735
00:31:03,420 --> 00:31:07,490
deve colocar Aaron no local
zero um, dois, três.

736
00:31:07,490 --> 00:31:09,480
>> Certo, eu poderia colocar um aqui.

737
00:31:09,480 --> 00:31:13,350
Mas então, se tentarmos inserir David em
Nesta lista, onde é que David vai?

738
00:31:13,350 --> 00:31:15,170
Agora o nosso sistema começa a quebrar
para baixo, certo?

739
00:31:15,170 --> 00:31:19,210
Porque agora David acaba aqui
Aaron se é realmente aqui.

740
00:31:19,210 --> 00:31:23,060
E agora toda essa idéia de ter um
estrutura de dados limpo que nos dá

741
00:31:23,060 --> 00:31:28,010
inserções de tempo constantes, não está mais
constante de tempo, porque eu tenho que

742
00:31:28,010 --> 00:31:31,240
verificar, oh, droga, alguém já está
no local de Alice.

743
00:31:31,240 --> 00:31:35,320
>> Deixe-me investigar o resto dos dados
estrutura, procurando um local para colocar

744
00:31:35,320 --> 00:31:37,130
alguém como o nome de Aaron.

745
00:31:37,130 --> 00:31:39,390
E assim que também está começando
ter tempo linear.

746
00:31:39,390 --> 00:31:42,710
Além disso, se você agora quer encontrar o
Aaron nesta estrutura de dados, e você

747
00:31:42,710 --> 00:31:45,430
verifique, eo nome de Aaron não está aqui.

748
00:31:45,430 --> 00:31:47,960
Idealmente, você teria apenas que dizer Arão
não na estrutura de dados.

749
00:31:47,960 --> 00:31:51,530
Mas se você começar a fazer sala para
Aaron onde deveria ter havido um D

750
00:31:51,530 --> 00:31:55,600
ou um E, você, o pior caso, tem que verificar
Toda a estrutura de dados, em

751
00:31:55,600 --> 00:31:59,480
caso em que se transforma em algo
linear no tamanho da tabela.

752
00:31:59,480 --> 00:32:00,920
>> Então tudo bem, eu vou corrigir isso.

753
00:32:00,920 --> 00:32:04,200
O problema aqui é que eu tinha
26 elementos nesta matriz.

754
00:32:04,200 --> 00:32:05,000
Deixe-me mudar isso.

755
00:32:05,000 --> 00:32:06,010
Gritos.

756
00:32:06,010 --> 00:32:10,600
Deixe-me mudar isso para que, em vez de ser
tamanho 26 no total, observe o fundo

757
00:32:10,600 --> 00:32:12,720
índice vai mudar de n menos 1.

758
00:32:12,720 --> 00:32:16,610
Se 26 é claramente demasiado pequeno para os seres humanos '
nomes, porque há milhares de

759
00:32:16,610 --> 00:32:20,830
nomes do mundo, vamos fazer
em 100 ou 1000 ou 10000.

760
00:32:20,830 --> 00:32:22,960
Vamos apenas alocar muito mais espaço.

761
00:32:22,960 --> 00:32:27,230
>> Bem, isso não significa necessariamente diminuir
a probabilidade de que não terá dois

762
00:32:27,230 --> 00:32:31,510
pessoas com nomes que começam com A, e
assim, você estava indo para tentar colocar um

763
00:32:31,510 --> 00:32:33,120
nomes em local ainda a zero.

764
00:32:33,120 --> 00:32:36,850
Eles ainda vão colidir, o que
significa que ainda precisa de uma solução para colocar

765
00:32:36,850 --> 00:32:41,020
Alice e Arão e Alicia e outros
nomes que começam com A em outro lugar.

766
00:32:41,020 --> 00:32:43,460
Mas como um grande problema é esse?

767
00:32:43,460 --> 00:32:46,870
Qual é a probabilidade de que você
tem colisões em uma base de dados

768
00:32:46,870 --> 00:32:48,240
estrutura como esta?

769
00:32:48,240 --> 00:32:52,570
>> Bem, deixe-me - nós vamos voltar
a essa pergunta aqui.

770
00:32:52,570 --> 00:32:55,530
E olha como poderíamos
resolvê-lo pela primeira vez.

771
00:32:55,530 --> 00:32:58,480
Deixa-me tirar esta proposta aqui.

772
00:32:58,480 --> 00:33:02,020
O que acabamos de descrever é um algoritmo,
uma heurística chamado linear

773
00:33:02,020 --> 00:33:05,030
sondagem segundo a qual, se você tentou inserir
algo aqui nestes dados

774
00:33:05,030 --> 00:33:08,920
estrutura, o que é denominado tabela hash
e não há espaço lá, você

775
00:33:08,920 --> 00:33:12,000
verdadeiramente sondar a estrutura de dados
verificação, é esta disponível?

776
00:33:12,000 --> 00:33:13,430
É esta disponível é esta disponível?

777
00:33:13,430 --> 00:33:13,980
É esta disponível?

778
00:33:13,980 --> 00:33:17,550
E quando ele finalmente seja, inserir o
nome que originalmente planejado

779
00:33:17,550 --> 00:33:19,370
em outro lugar naquele local.

780
00:33:19,370 --> 00:33:23,360
Mas, no pior dos casos, o único ponto
pode ser a parte inferior dos dados

781
00:33:23,360 --> 00:33:25,090
estrutura, o fim do array.

782
00:33:25,090 --> 00:33:30,130
>> Então linear sondagem, no pior caso,
transforma em um algoritmo linear em que

783
00:33:30,130 --> 00:33:34,500
Aaron, se ele passa a ser inserido última
neste tipo de estrutura de dados, ele pode

784
00:33:34,500 --> 00:33:39,540
colidir com esta primeira posição, mas
depois acabam por má sorte no final.

785
00:33:39,540 --> 00:33:43,940
Portanto, esta não é uma constante
tempo santo graal para nós.

786
00:33:43,940 --> 00:33:47,650
Esta abordagem para a inserção de elementos
uma estrutura de dados, chamado de hash

787
00:33:47,650 --> 00:33:52,050
tabela não parecem ser de tempo constante
pelo menos, no caso geral.

788
00:33:52,050 --> 00:33:54,000
Ele pode transformar-se em algo linear.

789
00:33:54,000 --> 00:33:56,970
>> Então, o que se resolver conflitos
um pouco diferente?

790
00:33:56,970 --> 00:34:00,740
Então aqui vai um mais sofisticado
abordagem para o que é ainda

791
00:34:00,740 --> 00:34:02,800
chamada de tabela de hash.

792
00:34:02,800 --> 00:34:05,890
E, de hash, como um aparte, o que
Quero dizer, é o índice que

793
00:34:05,890 --> 00:34:07,070
Me referi anteriormente.

794
00:34:07,070 --> 00:34:09,810
Para hash de alguma coisa pode ser
pensada como um verbo.

795
00:34:09,810 --> 00:34:13,690
>> Então, se você haxixe Alice é um nome,
uma função de hash, por assim dizer,

796
00:34:13,690 --> 00:34:14,710
deve retornar um número.

797
00:34:14,710 --> 00:34:18,199
Neste caso será zero se a ela pertence
localização zero, um, se ela pertence a

798
00:34:18,199 --> 00:34:20,000
um local, e assim por diante.

799
00:34:20,000 --> 00:34:24,360
Assim, a minha função de hash, até agora, tem sido
super simples, apenas olhando para o

800
00:34:24,360 --> 00:34:26,159
primeira letra do nome de alguém.

801
00:34:26,159 --> 00:34:29,090
Mas uma função de hash recebe como
entrada de algum pedaço de dados, um

802
00:34:29,090 --> 00:34:30,210
string, um inteiro, qualquer que seja.

803
00:34:30,210 --> 00:34:32,239
E ele cospe tipicamente um número.

804
00:34:32,239 --> 00:34:35,739
E esse número é o local onde os dados
elemento pertence a uma estrutura de dados

805
00:34:35,739 --> 00:34:37,800
conhecido aqui como uma tabela hash.

806
00:34:37,800 --> 00:34:41,400
>> Então, só intuitivamente, esta é uma
contexto ligeiramente diferente.

807
00:34:41,400 --> 00:34:44,170
Isso, na verdade está se referindo a um exemplo
envolvendo aniversários, quando

808
00:34:44,170 --> 00:34:46,850
pode haver tantos como
31 dias no mês.

809
00:34:46,850 --> 00:34:52,239
Mas o que essa pessoa decidir
fazer em caso de uma colisão?

810
00:34:52,239 --> 00:34:55,304
Contexto agora a ser, não uma colisão de
nomes, mas uma colisão de aniversários,

811
00:34:55,304 --> 00:35:00,760
se duas pessoas têm a mesma data de aniversário no
o 2 º de outubro, por exemplo.

812
00:35:00,760 --> 00:35:02,120
>> Estudante: [inaudível].

813
00:35:02,120 --> 00:35:05,010
>> COLUNA 1: Sim, então aqui nós temos
a alavancagem de listas ligadas.

814
00:35:05,010 --> 00:35:07,830
Portanto, parece um pouco diferente
do que chamou mais cedo.

815
00:35:07,830 --> 00:35:10,790
Mas parece que uma matriz
no lado esquerdo.

816
00:35:10,790 --> 00:35:13,230
Esse é um índice, pois nenhuma
razão particular.

817
00:35:13,230 --> 00:35:14,630
Mas ainda é um array.

818
00:35:14,630 --> 00:35:16,160
É uma matriz de ponteiros.

819
00:35:16,160 --> 00:35:20,670
E cada um desses elementos, cada um de
esses círculos ou barras - a barra

820
00:35:20,670 --> 00:35:23,970
representando nula - cada uma delas
ponteiros é, aparentemente, apontando para

821
00:35:23,970 --> 00:35:25,730
que a estrutura de dados?

822
00:35:25,730 --> 00:35:26,890
Uma lista ligada.

823
00:35:26,890 --> 00:35:30,530
>> Portanto, agora temos a capacidade de
codificar em nosso programa

824
00:35:30,530 --> 00:35:32,010
o tamanho da tabela.

825
00:35:32,010 --> 00:35:35,360
Neste caso, sabemos que nunca há
mais de 31 dias em um mês.

826
00:35:35,360 --> 00:35:38,480
Tão difícil codificação de um valor como 31 é
razoável nesse contexto.

827
00:35:38,480 --> 00:35:42,700
No contexto de nomes, codificação dura
26 não é razoável que as pessoas

828
00:35:42,700 --> 00:35:46,340
nomes começam apenas com, por exemplo,
o alfabeto de A a Z. envolvendo

829
00:35:46,340 --> 00:35:50,180
>> Podemos meter-los todos em que os dados
estrutura, desde que, quando temos um

830
00:35:50,180 --> 00:35:55,330
colisão, não colocar os nomes aqui,
que em vez de pensar essas células

831
00:35:55,330 --> 00:36:00,270
como não próprias cordas, mas como
ponteiros para, por exemplo, Alice.

832
00:36:00,270 --> 00:36:03,660
E então Alice pode ter outro ponteiro
para outro nome começando com

833
00:36:03,660 --> 00:36:06,150
A. e Bob realmente passa por aqui.

834
00:36:06,150 --> 00:36:10,850
>> E se há outro nome que começa
com B, ele acaba por aqui.

835
00:36:10,850 --> 00:36:15,070
E assim, cada um dos elementos do presente
mesa de dois, se nós projetamos este um

836
00:36:15,070 --> 00:36:17,350
pouco mais inteligente -

837
00:36:17,350 --> 00:36:18,125
Vamos lá -

838
00:36:18,125 --> 00:36:22,950
se nós projetamos este um pouco mais
inteligentemente, torna-se agora um conjunto de dados de adaptação

839
00:36:22,950 --> 00:36:27,720
estrutura, onde não há limite rígido
em quantos elementos você pode inserir

840
00:36:27,720 --> 00:36:30,700
nele porque se você tem
uma colisão, isso é bom.

841
00:36:30,700 --> 00:36:34,690
Basta ir em frente e anexá-lo ao
o que vimos um pouco atrás era

842
00:36:34,690 --> 00:36:38,290
conhecido como uma lista ligada.

843
00:36:38,290 --> 00:36:39,690
>> Bem, vamos fazer uma pausa por um momento.

844
00:36:39,690 --> 00:36:42,570
O que é que a probabilidade de uma colisão
em primeiro lugar?

845
00:36:42,570 --> 00:36:45,480
Certo, talvez eu estou mais pensando, talvez
Eu estou sobre engenharia este problema,

846
00:36:45,480 --> 00:36:46,370
porque você sabe o quê?

847
00:36:46,370 --> 00:36:49,070
Sim, eu posso chegar a arbitrária
exemplos em cima da minha cabeça, como

848
00:36:49,070 --> 00:36:52,870
Allison e Aaron, mas, na realidade,
dada uma distribuição uniforme do

849
00:36:52,870 --> 00:36:56,990
insumos, ou seja algumas inserções aleatórias
numa estrutura de dados, o que é realmente

850
00:36:56,990 --> 00:36:58,580
a probabilidade de uma colisão?

851
00:36:58,580 --> 00:37:01,670
Bem vê, é realmente
super alta.

852
00:37:01,670 --> 00:37:03,850
Deixe-me generalizar este
este problema é como.

853
00:37:03,850 --> 00:37:08,890
>> Assim, em uma sala de n CS50 estudantes, o que é
a probabilidade de que pelo menos

854
00:37:08,890 --> 00:37:11,010
dois alunos na sala
têm a mesma data de aniversário?

855
00:37:11,010 --> 00:37:13,346
Portanto, não há o quê. alguns hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 pessoas aqui e vários
centenas de pessoas em casa hoje.

857
00:37:16,790 --> 00:37:20,670
Então, se você queria perguntar a nós mesmos o que é
a probabilidade de duas pessoas

858
00:37:20,670 --> 00:37:23,930
nesta sala que tem o mesmo aniversário,
podemos descobrir isso.

859
00:37:23,930 --> 00:37:26,250
E eu afirmo na verdade, existem dois
pessoas com o mesmo aniversário.

860
00:37:26,250 --> 00:37:29,560
>> Por exemplo, alguém
tem aniversário hoje?

861
00:37:29,560 --> 00:37:31,340
Ontem?

862
00:37:31,340 --> 00:37:32,590
Amanhã?

863
00:37:32,590 --> 00:37:35,980
Tudo bem, então parece que eu vou
ter que fazer isso mais ou menos 363

864
00:37:35,980 --> 00:37:39,500
vezes para realmente descobrir
se temos uma colisão.

865
00:37:39,500 --> 00:37:42,350
Ou podemos fazer isso matematicamente
ao invés de tediosamente

866
00:37:42,350 --> 00:37:43,200
fazer isso.

867
00:37:43,200 --> 00:37:44,500
E propor o seguinte.

868
00:37:44,500 --> 00:37:48,740
>> Assim, proponho que poderia modelar o
probabilidade de duas pessoas que têm a

869
00:37:48,740 --> 00:37:55,320
mesma data de aniversário como a probabilidade de um
menos a probabilidade de não ter um

870
00:37:55,320 --> 00:37:56,290
aniversário no mesmo dia.

871
00:37:56,290 --> 00:37:59,960
Então, para conseguir isso, e este é apenas o
fantasia maneira de escrever isso, pois o

872
00:37:59,960 --> 00:38:03,090
primeira pessoa na sala, ele ou ela
pode ter qualquer um dos possíveis

873
00:38:03,090 --> 00:38:07,370
aniversários assumindo 365 dias no ano,
com desculpas às pessoas com

874
00:38:07,370 --> 00:38:08,760
o 29 º aniversário de fevereiro.

875
00:38:08,760 --> 00:38:13,470
>> Assim, a primeira pessoa nesta sala é livre
ter qualquer número de aniversários

876
00:38:13,470 --> 00:38:18,280
fora das 365 possibilidades para que
vamos fazer que 365 dividido por 365,

877
00:38:18,280 --> 00:38:18,990
, que é um.

878
00:38:18,990 --> 00:38:22,700
A próxima pessoa na sala, se o objetivo
é evitar uma colisão, só pode

879
00:38:22,700 --> 00:38:26,460
ter seu aniversário em como
diversos dias possíveis?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Assim, o segundo termo da expressão é esta
essencialmente, fazendo que a matemática para nós

882
00:38:31,430 --> 00:38:33,460
subtraindo-se fora de um dia possível.

883
00:38:33,460 --> 00:38:36,390
E, em seguida, no dia seguinte, no dia seguinte, o
dia seguinte até ao número total

884
00:38:36,390 --> 00:38:38,100
de pessoas na sala.

885
00:38:38,100 --> 00:38:41,290
>> E se então considerar, qual é então
a probabilidade de não ter todos

886
00:38:41,290 --> 00:38:45,265
aniversários únicas, mas novamente um menos
que, o que temos é uma expressão

887
00:38:45,265 --> 00:38:47,810
que pode muito fantasiosamente
semelhante a este.

888
00:38:47,810 --> 00:38:50,330
Mas é mais interessante
olhar visualmente.

889
00:38:50,330 --> 00:38:55,120
Este é um gráfico em que no eixo dos x é
o número de pessoas na sala, o

890
00:38:55,120 --> 00:38:56,180
número de aniversários.

891
00:38:56,180 --> 00:38:59,840
No eixo y representa a probabilidade
de uma colisão, duas pessoas

892
00:38:59,840 --> 00:39:01,230
tendo o mesmo aniversário.

893
00:39:01,230 --> 00:39:05,020
>> E o takeaway partir desta curva é
que, assim que você começa a gostar 40

894
00:39:05,020 --> 00:39:11,110
estudantes, está-se a uma probabilidade de 90%
combinatorically de dois

895
00:39:11,110 --> 00:39:13,550
ou mais pessoas que têm
aniversário no mesmo dia.

896
00:39:13,550 --> 00:39:18,600
E uma vez que você começa a gostar de 58 pessoas é
cerca de 100% de uma possibilidade os dois

897
00:39:18,600 --> 00:39:21,310
pessoas na sala vai ter o
mesma data de aniversário, mesmo que não haja

898
00:39:21,310 --> 00:39:26,650
365 ou 366 possíveis baldes e
apenas 58 pessoas na sala.

899
00:39:26,650 --> 00:39:29,900
Apenas estatisticamente é provável que você
obter colisões, o que em suma

900
00:39:29,900 --> 00:39:31,810
motiva esta discussão.

901
00:39:31,810 --> 00:39:35,890
Que, mesmo que começar a fantasia aqui, e
começar a ter essas cadeias, ainda estamos

902
00:39:35,890 --> 00:39:36,950
vai ter colisões.

903
00:39:36,950 --> 00:39:42,710
>> Assim que levanta a questão: o que é o
custo de fazer inserções e deleções

904
00:39:42,710 --> 00:39:44,850
em uma estrutura de dados como este?

905
00:39:44,850 --> 00:39:46,630
Bem, deixe-me propor -

906
00:39:46,630 --> 00:39:51,570
e deixe-me voltar para a tela sobre
aqui - se temos n elementos no

907
00:39:51,570 --> 00:39:56,330
lista, por isso, se estamos tentando inserir
n elementos, e nós temos

908
00:39:56,330 --> 00:39:58,050
quantos total de baldes?

909
00:39:58,050 --> 00:40:03,450
Digamos que 31 baldes totais
no caso de aniversário.

910
00:40:03,450 --> 00:40:09,240
Qual é o comprimento máximo de um
destas cadeias potencialmente?

911
00:40:09,240 --> 00:40:12,670
>> Se novamente não é possível 31
aniversários em um determinado mês.

912
00:40:12,670 --> 00:40:14,580
E estamos apenas a aglutinação todos -

913
00:40:14,580 --> 00:40:15,580
na verdade, isso é um exemplo estúpido.

914
00:40:15,580 --> 00:40:16,960
Vamos fazer 26 em vez.

915
00:40:16,960 --> 00:40:20,890
Então, se realmente tem pessoas cujos nomes
começar com A a Z, dando assim

916
00:40:20,890 --> 00:40:22,780
nos 26 possibilidades.

917
00:40:22,780 --> 00:40:25,920
E nós estamos usando uma estrutura de dados como
o que acabamos de ver, em que temos

918
00:40:25,920 --> 00:40:30,210
uma matriz de pontos, cada um dos quais
aponta para uma lista ligada, onde o

919
00:40:30,210 --> 00:40:32,360
primeira lista é de todos
com o nome de Alice.

920
00:40:32,360 --> 00:40:35,770
A segunda lista é cada um com o
nome começar com A, começando

921
00:40:35,770 --> 00:40:36,980
com B, e assim por diante.

922
00:40:36,980 --> 00:40:41,020
>> Qual é a duração provável de cada um dos
essas listas se assumirmos um bom limpo

923
00:40:41,020 --> 00:40:45,410
distribuição de nomes de A a Z
através da estrutura de dados inteiro?

924
00:40:45,410 --> 00:40:50,210
Há n pessoas na estrutura de dados
dividido por 26, se forem bem

925
00:40:50,210 --> 00:40:52,110
espalhados por todo o
estrutura de dados.

926
00:40:52,110 --> 00:40:54,970
Assim, o comprimento de cada um desses
cadeias é n dividido por 26.

927
00:40:54,970 --> 00:40:57,380
Mas na notação O grande, o que é isso?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
O que é isso mesmo?

930
00:41:02,440 --> 00:41:04,150
Então, é realmente apenas n, certo?

931
00:41:04,150 --> 00:41:06,620
Porque nós já disse no passado,
ugh que você dividir por 26.

932
00:41:06,620 --> 00:41:08,710
Sim, na realidade, ela é mais rápida.

933
00:41:08,710 --> 00:41:12,720
Mas, em teoria, não é fundamentalmente
tudo o que mais rapidamente.

934
00:41:12,720 --> 00:41:16,040
>> Portanto, não parece ser tudo o que muito
mais próximo a este santo graal.

935
00:41:16,040 --> 00:41:17,750
Na verdade, este é apenas o tempo linear.

936
00:41:17,750 --> 00:41:20,790
Heck, neste ponto, por que não nós
basta usar uma lista ligada enorme?

937
00:41:20,790 --> 00:41:23,510
Por que não usar apenas um enorme
matriz para armazenar os nomes das

938
00:41:23,510 --> 00:41:25,010
todos na sala?

939
00:41:25,010 --> 00:41:28,280
Bem, ainda há algo
convincente sobre uma tabela hash?

940
00:41:28,280 --> 00:41:30,810
Existe ainda algo atraente
sobre uma estrutura de dados

941
00:41:30,810 --> 00:41:33,940
que se parece com isso?

942
00:41:33,940 --> 00:41:35,182
Este.

943
00:41:35,182 --> 00:41:37,050
>> Estudante: [inaudível].

944
00:41:37,050 --> 00:41:39,840
>> COLUNA 1: Certo, e, novamente, se é apenas
um algoritmo de tempo linear, e um

945
00:41:39,840 --> 00:41:42,780
estrutura de dados em tempo linear, por que não eu
apenas armazenar o nome de todos em um grande

946
00:41:42,780 --> 00:41:44,210
matriz, ou em uma lista vinculada grande?

947
00:41:44,210 --> 00:41:47,010
E parar de fazer CS muito mais difícil
do que precisa ser?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
O que é interessante sobre isso, mesmo
embora eu arranhou-lo?

950
00:41:53,190 --> 00:41:54,930
>> Estudante: [inaudível].

951
00:41:54,930 --> 00:41:57,040
>> COLUNA 1: As inserções não são?

952
00:41:57,040 --> 00:41:58,140
Expensive mais.

953
00:41:58,140 --> 00:42:03,390
Então inserções potencialmente poderia ainda
ser de tempo constante, mesmo se os seus dados

954
00:42:03,390 --> 00:42:07,910
estrutura se parece com isso, uma série de
apontadores, cada um dos quais está a apontar

955
00:42:07,910 --> 00:42:09,550
potencialmente uma lista encadeada.

956
00:42:09,550 --> 00:42:15,220
Como você poderia conseguir constante
inserção vez de nomes de?

957
00:42:15,220 --> 00:42:16,280
Cole-o no frontal, certo?

958
00:42:16,280 --> 00:42:19,290
>> Se sacrificar um objetivo do projeto de
anteriormente, onde queríamos manter

959
00:42:19,290 --> 00:42:22,650
o nome de todos, por exemplo, classificadas
ou todos os números em fase classificados,

960
00:42:22,650 --> 00:42:25,020
supor que nós temos um
lista ligada indiferenciados.

961
00:42:25,020 --> 00:42:29,960
Ele só nos custa um ou dois passos,
como no caso de Ben e Brian

962
00:42:29,960 --> 00:42:32,750
anteriormente, para inserir um elemento em
o início da lista.

963
00:42:32,750 --> 00:42:36,090
Então, se nós não nos importamos sobre a classificação todos
dos nomes começam com um ou todos

964
00:42:36,090 --> 00:42:39,660
os nomes que começam com B, ainda podemos
alcançar inserção constante de tempo.

965
00:42:39,660 --> 00:42:43,900
Agora, olhando para Alice ou Bob ou qualquer nome
mais geral ainda o que é?

966
00:42:43,900 --> 00:42:48,100
É grande O de n dividido por 26, no
caso ideal, onde todos estão uniformemente

967
00:42:48,100 --> 00:42:51,190
distribuído, onde há o maior número de um
uma vez que existem de Z, o qual é provavelmente

968
00:42:51,190 --> 00:42:52,220
irrealista.

969
00:42:52,220 --> 00:42:53,880
Mas isso ainda é linear.

970
00:42:53,880 --> 00:42:57,120
>> Mas aqui, voltamos ao ponto
de notação assintótica ser

971
00:42:57,120 --> 00:42:58,600
teoricamente verdade.

972
00:42:58,600 --> 00:43:02,960
Mas, no mundo real, se eu afirmar que
meu programa pode fazer algo 26 vezes

973
00:43:02,960 --> 00:43:06,210
mais rápido do que o seu, cujo programa
você vai preferir usar?

974
00:43:06,210 --> 00:43:09,660
Seu ou meu, que
é 26 vezes mais rápido?

975
00:43:09,660 --> 00:43:14,320
Realisticamente, a pessoa de quem é 26
vezes mais rápida, ainda que teoricamente

976
00:43:14,320 --> 00:43:18,790
nossos algoritmos são executados na mesma
assintótica tempo de corrida.

977
00:43:18,790 --> 00:43:20,940
>> Deixe-me propor uma diferente
solução completamente.

978
00:43:20,940 --> 00:43:24,380
E se isso não explodir sua mente,
estamos fora de estruturas de dados.

979
00:43:24,380 --> 00:43:27,420
Portanto, esta é uma trie -

980
00:43:27,420 --> 00:43:28,520
tipo de um nome estúpido.

981
00:43:28,520 --> 00:43:32,880
Ela vem de recuperações, ea palavra
está escrito trie, t-r-i-e, por causa de

982
00:43:32,880 --> 00:43:34,450
recuperação curso soa como trie.

983
00:43:34,450 --> 00:43:36,580
Mas essa é a história
da palavra trie.

984
00:43:36,580 --> 00:43:40,980
>> Assim, uma trie é de fato uma espécie de árvore,
e também é uma brincadeira com a palavra.

985
00:43:40,980 --> 00:43:46,330
E mesmo que você não consegue vê-lo
com esta visualização, um trie é um

986
00:43:46,330 --> 00:43:50,790
árvore estruturada, como uma árvore genealógica com
um antepassado no topo e muito

987
00:43:50,790 --> 00:43:54,530
de netos e bisnetos
como folhas na parte inferior.

988
00:43:54,530 --> 00:43:58,100
Mas cada nó em uma trie é uma matriz.

989
00:43:58,100 --> 00:44:00,680
E é em uma matriz - e vamos
simplificar por um momento - é uma

990
00:44:00,680 --> 00:44:04,600
matriz, neste caso, de tamanho 26, onde
cada nó é novamente uma matriz de tamanho

991
00:44:04,600 --> 00:44:09,000
26, onde o elemento de ordem zero, em que
Uma matriz representa, ea última

992
00:44:09,000 --> 00:44:11,810
em cada elemento de tal
array representa Z.

993
00:44:11,810 --> 00:44:15,520
>> Assim, proponho, então, que esses dados
estrutura, conhecida como uma trie, pode ser

994
00:44:15,520 --> 00:44:17,600
também utilizada para armazenar palavras.

995
00:44:17,600 --> 00:44:21,740
Vimos há pouco como poderíamos armazenar
palavras, ou neste caso os nomes, e nós

996
00:44:21,740 --> 00:44:25,440
viu anteriormente como podemos armazenar números,
mas se concentrar em nomes ou seqüências

997
00:44:25,440 --> 00:44:27,460
aqui, perceber o que é interessante.

998
00:44:27,460 --> 00:44:32,210
Eu afirmo que o nome é Maxwell
dentro desta estrutura de dados.

999
00:44:32,210 --> 00:44:33,730
Onde você vê Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> Estudante: [inaudível].

1001
00:44:35,140 --> 00:44:36,240
>> COLUNA 1: À esquerda.

1002
00:44:36,240 --> 00:44:39,910
Então, o que é interessante com estes dados
estrutura é, em vez de armazenar o

1003
00:44:39,910 --> 00:44:46,200
corda M-A-X-W-E-L-L invertida zero, tudo
contígua, o que fazer em vez

1004
00:44:46,200 --> 00:44:46,890
está seguindo.

1005
00:44:46,890 --> 00:44:50,510
Se esta é uma estrutura de dados como trie,
cada um dos nós cujas é novamente uma matriz,

1006
00:44:50,510 --> 00:44:54,650
e você quer armazenar Maxwell, primeiro você
índice e assim nó da raiz, de modo

1007
00:44:54,650 --> 00:44:57,810
dizer, o nó de nível superior,
na posição M, certo, então

1008
00:44:57,810 --> 00:44:59,160
aproximadamente no meio.

1009
00:44:59,160 --> 00:45:03,740
E, em seguida, a partir daí, você seguir uma
Ponteiro para uma criança nós, por assim dizer.

1010
00:45:03,740 --> 00:45:06,150
Assim, no sentido de árvore genealógica,
você segui-lo para baixo.

1011
00:45:06,150 --> 00:45:09,030
E que levá-lo para outro nó
À esquerda, que é

1012
00:45:09,030 --> 00:45:10,540
apenas uma outra matriz.

1013
00:45:10,540 --> 00:45:14,710
>> E então se você deseja armazenar Maxwell,
encontrar o ponteiro que representa

1014
00:45:14,710 --> 00:45:16,430
A, que é este aqui.

1015
00:45:16,430 --> 00:45:17,840
Então você vai para o próximo nó.

1016
00:45:17,840 --> 00:45:20,100
E note - é por isso que a imagem do
um pouco enganador -

1017
00:45:20,100 --> 00:45:21,990
este nó olhar super pequena.

1018
00:45:21,990 --> 00:45:26,050
Mas para a direita deste é Y e Z.
É só o autor tem truncado o

1019
00:45:26,050 --> 00:45:27,630
imagem de modo que você realmente
ver as coisas.

1020
00:45:27,630 --> 00:45:30,400
Caso contrário, esta imagem
seria muito grande.

1021
00:45:30,400 --> 00:45:36,180
Então, agora você indexar localização X, então
W, E E, em seguida, L, em seguida, L. Então qual é

1022
00:45:36,180 --> 00:45:37,380
essa curiosidade?

1023
00:45:37,380 --> 00:45:41,250
>> Bem, se estamos usando esse tipo de novo
assumir a forma de armazenar uma string em um

1024
00:45:41,250 --> 00:45:44,500
estrutura de dados, você ainda precisa
essencialmente marcar nos dados

1025
00:45:44,500 --> 00:45:47,250
estrutura que uma palavra termina aqui.

1026
00:45:47,250 --> 00:45:50,830
Em outras palavras, cada um desses nós
de alguma forma tem que se lembrar que

1027
00:45:50,830 --> 00:45:53,500
na verdade, seguido todos estes ponteiros
e estão deixando um pouco

1028
00:45:53,500 --> 00:45:58,370
migalha de pão no fundo aqui deste
estrutura para indicar M-A-X-W-E-L-L é

1029
00:45:58,370 --> 00:46:00,230
de facto nesta estrutura de dados.

1030
00:46:00,230 --> 00:46:02,040
>> Assim, poderíamos fazer isso da seguinte forma.

1031
00:46:02,040 --> 00:46:06,810
Cada um dos nós na imagem que acabamos de
tem uma serra, uma matriz de tamanho 27.

1032
00:46:06,810 --> 00:46:10,550
E agora é 27 porque, p definir seis anos,
vamos realmente dar-lhe uma apóstrofe,

1033
00:46:10,550 --> 00:46:13,590
para que possamos ter nomes como O'Reilly
e outros com apóstrofos.

1034
00:46:13,590 --> 00:46:14,820
Mas a mesma idéia.

1035
00:46:14,820 --> 00:46:17,710
Cada um desses elementos no
pontos de matriz para uma struct

1036
00:46:17,710 --> 00:46:19,320
nó, então apenas um nó.

1037
00:46:19,320 --> 00:46:21,430
Então isso é muito reminiscente
da nossa lista encadeada.

1038
00:46:21,430 --> 00:46:24,550
>> E então eu tenho um valor booleano, que eu vou
chamar palavra, que só vai ser

1039
00:46:24,550 --> 00:46:29,120
verdadeiro se uma palavra termina neste
nó da árvore.

1040
00:46:29,120 --> 00:46:32,870
Ele representa efetivamente a pouco
triângulo que vimos há pouco.

1041
00:46:32,870 --> 00:46:37,190
Assim, se uma palavra que termina no nó no
árvore, aquele campo palavra será verdadeira,

1042
00:46:37,190 --> 00:46:41,990
que é conceitualmente a verificação off, ou
estamos desenhando esse triângulo, sim, há

1043
00:46:41,990 --> 00:46:44,080
é uma palavra aqui.

1044
00:46:44,080 --> 00:46:45,120
>> Portanto, esta é uma trie.

1045
00:46:45,120 --> 00:46:48,540
E agora a pergunta é, o que
é seu tempo de execução?

1046
00:46:48,540 --> 00:46:49,930
É grande O de n?

1047
00:46:49,930 --> 00:46:51,410
É algo mais?

1048
00:46:51,410 --> 00:46:57,330
Bem, se você tem n nomes nestes dados
estrutura, Maxwell sendo apenas um

1049
00:46:57,330 --> 00:47:02,330
eles, o que é o tempo de execução
inserção ou encontrar Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Qual é o tempo de execução
inserção de Maxwell?

1052
00:47:09,050 --> 00:47:11,740
Se há n outros nomes
já em cima da mesa?

1053
00:47:11,740 --> 00:47:12,507
Sim?

1054
00:47:12,507 --> 00:47:15,429
>> Estudante: [inaudível].

1055
00:47:15,429 --> 00:47:17,550
>> COLUNA 1: Sim, é o comprimento
do nome, certo?

1056
00:47:17,550 --> 00:47:24,420
Então M-a-x-w-e-l-l por isso se sente assim
O algoritmo é grande de sete.

1057
00:47:24,420 --> 00:47:26,580
Agora, obviamente, o nome
irá variar em comprimento.

1058
00:47:26,580 --> 00:47:27,380
Talvez seja um nome curto.

1059
00:47:27,380 --> 00:47:28,600
Talvez seja um nome mais longo.

1060
00:47:28,600 --> 00:47:33,390
Mas o que é importante aqui é que
é um número constante.

1061
00:47:33,390 --> 00:47:36,810
E talvez não seja realmente constante,
Mas Deus, se realisticamente, em um

1062
00:47:36,810 --> 00:47:41,570
dicionário, provavelmente há algum limite
sobre o número de letras de uma

1063
00:47:41,570 --> 00:47:43,820
o nome da pessoa em um determinado país.

1064
00:47:43,820 --> 00:47:46,940
>> E assim, podemos supor que
é um valor constante.

1065
00:47:46,940 --> 00:47:47,750
Eu não sei o que é.

1066
00:47:47,750 --> 00:47:50,440
É, provavelmente, maior do que
pensamos que é.

1067
00:47:50,440 --> 00:47:52,720
Porque há sempre algum canto
caso com um nome muito louco.

1068
00:47:52,720 --> 00:47:56,360
Então, vamos chamá-lo de k, mas é ainda um
constante, presumivelmente, porque cada

1069
00:47:56,360 --> 00:48:00,190
nome no mundo, pelo menos em um
determinado país, é que o comprimento ou

1070
00:48:00,190 --> 00:48:01,780
mais curto, por isso é constante.

1071
00:48:01,780 --> 00:48:04,490
Mas quando dissemos algo é grande
O de um valor constante, o que é isso

1072
00:48:04,490 --> 00:48:07,760
realmente equivalente a?

1073
00:48:07,760 --> 00:48:10,420
Essa é realmente a mesma coisa
que dizer de tempo constante.

1074
00:48:10,420 --> 00:48:11,530
>> Agora nós somos o tipo de fazer batota, certo?

1075
00:48:11,530 --> 00:48:15,340
Estamos meio de alavancar alguma teoria
aqui para dizer que o bem, a fim de k é

1076
00:48:15,340 --> 00:48:17,450
realmente só encomendar de um,
e é tempo constante.

1077
00:48:17,450 --> 00:48:18,200
Mas ele realmente é.

1078
00:48:18,200 --> 00:48:22,550
Porque o insight chave aqui é que
se temos n nomes já neste

1079
00:48:22,550 --> 00:48:26,010
estrutura de dados, e inserção Maxwell
é a quantidade de tempo que nos leva a

1080
00:48:26,010 --> 00:48:29,530
inserir Maxwell em todos os afetados
por quantas outras pessoas

1081
00:48:29,530 --> 00:48:31,100
estão dentro da estrutura de dados?

1082
00:48:31,100 --> 00:48:31,670
Não parece ser.

1083
00:48:31,670 --> 00:48:36,280
Se eu tivesse um bilhão de mais elementos para esta
trie, e então insira Maxwell, é

1084
00:48:36,280 --> 00:48:38,650
ele em todos os afetados?

1085
00:48:38,650 --> 00:48:39,050
Não.

1086
00:48:39,050 --> 00:48:42,950
E isso é diferente de qualquer um dos dados do dia
estruturas que temos visto até agora, onde

1087
00:48:42,950 --> 00:48:46,820
o tempo de execução do seu algoritmo é
completamente independente de quanto

1088
00:48:46,820 --> 00:48:51,430
material é ou não é já
em que a estrutura de dados.

1089
00:48:51,430 --> 00:48:54,650
>> E assim, com esta lhe proporciona agora é um
oportunidade para p conjunto de seis, que será

1090
00:48:54,650 --> 00:48:58,310
novamente envolver implementar seu próprio
corretor ortográfico, a leitura em 150 mil

1091
00:48:58,310 --> 00:49:01,050
palavras, a melhor forma de armazenar esse
não é necessariamente evidente.

1092
00:49:01,050 --> 00:49:04,030
E embora eu aspirava a encontrar
o santo graal, eu não

1093
00:49:04,030 --> 00:49:05,330
afirmam que uma trie é.

1094
00:49:05,330 --> 00:49:09,810
Na verdade, uma tabela hash pode muito bem
provar ser muito mais eficiente.

1095
00:49:09,810 --> 00:49:10,830
Mas esses são apenas -

1096
00:49:10,830 --> 00:49:14,620
isso é apenas uma das decisões de projeto
você terá que fazer.

1097
00:49:14,620 --> 00:49:18,920
>> Mas no encerramento vamos ter 50 ou mais
segundos para dar uma olhada no que está

1098
00:49:18,920 --> 00:49:22,190
frente na próxima semana e que a transição para além
a partir desta linha de comando

1099
00:49:22,190 --> 00:49:26,220
mundo, se programas em C para as coisas web
base e linguagens como PHP e

1100
00:49:26,220 --> 00:49:30,350
JavaScript e da própria internet,
protocolos como HTTP, o que você

1101
00:49:30,350 --> 00:49:32,870
tida como certa por muitos anos
agora, e digitou a maioria cada

1102
00:49:32,870 --> 00:49:34,440
dia, talvez, ou visto.

1103
00:49:34,440 --> 00:49:37,420
E vamos começar a descascar a
camadas de qual é a Internet.

1104
00:49:37,420 --> 00:49:40,650
E qual é o código que
subjacente ferramentas de hoje.

1105
00:49:40,650 --> 00:49:43,230
Então 50 segundos este teaser aqui.

1106
00:49:43,230 --> 00:49:46,570
Eu dar-lhe guerreiros da rede.

1107
00:49:46,570 --> 00:49:51,370
>> [REPRODUÇÃO]

1108
00:49:51,370 --> 00:49:56,764
>> -Ele veio com uma mensagem.

1109
00:49:56,764 --> 00:50:00,687
Com um protocolo de todos os seus próprios.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Ele veio para um mundo de firewalls cruéis
routers indiferente, e os perigos longe

1112
00:50:19,780 --> 00:50:22,600
pior que a morte.

1113
00:50:22,600 --> 00:50:23,590
Ele é rápido.

1114
00:50:23,590 --> 00:50:25,300
Ele é forte.

1115
00:50:25,300 --> 00:50:27,700
Ele é TCPIP.

1116
00:50:27,700 --> 00:50:30,420
E ele tem o seu endereço.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Guerreiros da rede.

1119
00:50:34,590 --> 00:50:35,290
>> [FIM REPRODUÇÃO DE VÍDEO]

1120
00:50:35,290 --> 00:50:38,070
>> COLUNA 1: É assim que a internet
deve trabalhar a partir da próxima semana.

1121
00:50:38,070 --> 00:50:40,406