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

2
00:00:10,900 --> 00:00:15,860
>> COLUMNA 1: Todo ben, entón que é
CS50 Este é o fin de semana cinco.

3
00:00:15,860 --> 00:00:19,220
E lembrar que a última vez que
comecei a ollar os datos máis chic

4
00:00:19,220 --> 00:00:22,310
estruturas que pasaron a resolver
problemas, que comezaron a introducir

5
00:00:22,310 --> 00:00:25,640
novos problemas, pero a clave para este
Era o tipo de rosqueamento que

6
00:00:25,640 --> 00:00:27,940
comezou a facer a partir de nó a nó.

7
00:00:27,940 --> 00:00:30,085
Entón, iso, por suposto, é
unha lista vinculada illadamente.

8
00:00:30,085 --> 00:00:31,960
E por vinculada illadamente,
É dicir, hai só un

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

10
00:00:33,380 --> 00:00:35,890
Acontece que pode facer máis chic
cousas como listas dobremente ligadas

11
00:00:35,890 --> 00:00:38,470
en que ten unha frecha
indo en ambas as direccións, o que

12
00:00:38,470 --> 00:00:40,320
pode axudar con determinadas eficiencias.

13
00:00:40,320 --> 00:00:42,000
Pero iso resolveu o problema?

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

15
00:00:43,500 --> 00:00:46,620
Por que nós nos importa o luns?

16
00:00:46,620 --> 00:00:49,820
Por que, en teoría, se nós nos importa o luns?

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

18
00:00:50,630 --> 00:00:51,950
>> Audiencia: Podemos redimensionar-lo dinamicamente.

19
00:00:51,950 --> 00:00:53,740
>> COLUMNA 1: OK, entón podemos
redimensiona-lo dinamicamente.

20
00:00:53,740 --> 00:00:54,710
Ben feito tanto de ti.

21
00:00:54,710 --> 00:00:57,560
Así, pode cambiar o tamaño dinamicamente este
estrutura de datos, mentres que unha matriz,

22
00:00:57,560 --> 00:01:00,760
recall, ten que saber un
priori como espazo quere

23
00:01:00,760 --> 00:01:03,870
e se precisa de algo máis
espazo, é tipo de fóra da sorte.

24
00:01:03,870 --> 00:01:05,560
Ten que crear unha matriz totalmente novo.

25
00:01:05,560 --> 00:01:07,893
Ten que mover os seus
datos de un para o outro,

26
00:01:07,893 --> 00:01:10,600
finalmente, liberar o array antigo
se pode, e despois continuar.

27
00:01:10,600 --> 00:01:13,891
Que só se sente moi caro e moi
ineficiente, e en realidade pode ser.

28
00:01:13,891 --> 00:01:14,890
Pero iso non é todo de bo.

29
00:01:14,890 --> 00:01:18,180
Nós pagamos un prezo, o que era unha
dos prezos máis obvios nós

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

31
00:01:20,550 --> 00:01:22,825
>> Audiencia: Temos que usar
dobre espazo para cada un.

32
00:01:22,825 --> 00:01:25,200
COLUMNA 1: Si, por iso necesitamos
polo menos dúas veces máis espazo.

33
00:01:25,200 --> 00:01:27,700
En realidade, eu entender iso de imaxe
incluso un pouco erro,

34
00:01:27,700 --> 00:01:32,200
porque no IDE CS50 en unha morea de moderno
ordenadores, un punteiro ou un enderezo

35
00:01:32,200 --> 00:01:33,700
non é, de feito, catro bytes.

36
00:01:33,700 --> 00:01:36,090
É moi frecuentemente estes
días oito bytes, os cales

37
00:01:36,090 --> 00:01:38,530
significa que a parte inferior máis
rectángulos alí en realidade

38
00:01:38,530 --> 00:01:40,900
son unha especie de dúas veces máis
grande como o que eu deseño,

39
00:01:40,900 --> 00:01:44,409
o que significa que está a usar tres veces máis
tanto espazo como poderiamos ter outra forma.

40
00:01:44,409 --> 00:01:46,700
Agora, ao mesmo tempo, estamos
aínda falando bytes, non?

41
00:01:46,700 --> 00:01:49,140
Non estamos necesariamente falando
megabytes ou gigabytes,

42
00:01:49,140 --> 00:01:51,000
a non ser que esas estruturas de datos quedar grande.

43
00:01:51,000 --> 00:01:54,510
>> E por iso hoxe comezan a considerar
como podemos explotar datos

44
00:01:54,510 --> 00:01:57,310
de forma máis eficiente en
traxe dos datos se fai maior.

45
00:01:57,310 --> 00:02:00,360
Pero imos tratar canonizar
as primeiras operacións

46
00:02:00,360 --> 00:02:02,460
que podes facer sobre estes
tipos de estruturas de datos.

47
00:02:02,460 --> 00:02:04,790
Entón, algo así como un conectado
lista soporta xeralmente

48
00:02:04,790 --> 00:02:07,514
Operacións como eliminar,
introducir e buscar.

49
00:02:07,514 --> 00:02:08,639
E o que quero dicir con iso?

50
00:02:08,639 --> 00:02:11,222
Isto só significa que, xeralmente,
se a xente está usando lista encadeada,

51
00:02:11,222 --> 00:02:14,287
eles ou alguén ten aplicado
funcións como DELETE, INSERT,

52
00:02:14,287 --> 00:02:16,120
e busca, para que poida
realmente facer algo

53
00:02:16,120 --> 00:02:18,030
útil coa estrutura de datos.

54
00:02:18,030 --> 00:02:20,760
Entón, imos dar un ollo rápida
en como podemos aplicar

55
00:02:20,760 --> 00:02:24,530
algún código para unha lista ligada deste xeito.

56
00:02:24,530 --> 00:02:27,885
>> Polo tanto, este é só un código C,
nin sequera un programa completo

57
00:02:27,885 --> 00:02:29,260
que realmente rápido empolada.

58
00:02:29,260 --> 00:02:32,300
Non é en liña na distribución
de código, pois non han funcionar.

59
00:02:32,300 --> 00:02:33,790
Pero teña en conta Acaba
cun comentario dixo,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, hai algo
alí, dot dot dot, algo alí.

61
00:02:36,130 --> 00:02:38,410
E imos só ollar para
que as pezas son suculentos.

62
00:02:38,410 --> 00:02:40,790
Así, na liña tres,
Recordamos que este é agora

63
00:02:40,790 --> 00:02:45,960
propuxemos declarando un nó último
tempo, un destes obxectos rectangulares.

64
00:02:45,960 --> 00:02:48,790
Ten un int que imos chamar N,
pero poderiamos chamalo de calquera cousa,

65
00:02:48,790 --> 00:02:51,920
e, a continuación, unha estrela nó struct chamada seguinte.

66
00:02:51,920 --> 00:02:55,520
E só para quedar claro, que segundo
liña, en liña seis, o que é iso?

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

68
00:02:57,930 --> 00:03:01,044
Porque certamente parece máis
críptica do que as nosas variables habituais.

69
00:03:01,044 --> 00:03:02,740
>> Audiencia: Faise pasar un.

70
00:03:02,740 --> 00:03:04,650
>> COLUMNA 1: Fai moverse máis dun.

71
00:03:04,650 --> 00:03:08,580
E para ser máis preciso,
ha almacenar o enderezo

72
00:03:08,580 --> 00:03:11,582
do nodo que está destinado a ser
semanticamente próximo a el, non?

73
00:03:11,582 --> 00:03:13,540
Por iso, non vai
necesariamente mover calquera cousa.

74
00:03:13,540 --> 00:03:15,290
El só vai
almacenar un valor que é

75
00:03:15,290 --> 00:03:17,170
será a dirección
dalgún outro no,

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

77
00:03:20,810 --> 00:03:22,370
un punteiro ou un enderezo.

78
00:03:22,370 --> 00:03:26,390
OK, entón agora se asumir que temos
N esta dispoñible para nós, e imos

79
00:03:26,390 --> 00:03:29,490
supoñer que alguén ten
insire unha morea de números enteiros

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

81
00:03:30,400 --> 00:03:35,640
E esa lista ligada é
apuntada por algún punto

82
00:03:35,640 --> 00:03:39,040
un chamado lista de variables que se
pasou aquí como un parámetro,

83
00:03:39,040 --> 00:03:43,120
como fago para ir sobre a liña
14 execución de investigación?

84
00:03:43,120 --> 00:03:45,990
Noutras palabras, se eu estou aplicando
función cuxo propósito na vida

85
00:03:45,990 --> 00:03:48,889
é tomar un int e, a continuación, o
comezando dunha lista ligada,

86
00:03:48,889 --> 00:03:50,430
que é un enlace á lista encadeada.

87
00:03:50,430 --> 00:03:52,992
Como primeiro, que eu creo que David
foi o noso voluntario o luns,

88
00:03:52,992 --> 00:03:54,700
estaba a apuntar cara
toda ligada a lista,

89
00:03:54,700 --> 00:03:57,820
é coma se nós estamos pasando
David en como o noso argumento aquí.

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

91
00:03:59,990 --> 00:04:04,640
Ben, resulta que, a pesar de
punteiros son relativamente novo para nós agora,

92
00:04:04,640 --> 00:04:07,010
podemos facelo relativamente
directamente.

93
00:04:07,010 --> 00:04:09,500
>> Eu estou indo a ir adiante e
declarar unha variable temporal que

94
00:04:09,500 --> 00:04:12,364
por convención é só ir
a ser chamado de punteiro, ou PTR,

95
00:04:12,364 --> 00:04:14,030
pero podería chamalo de calquera cousa que sexa.

96
00:04:14,030 --> 00:04:16,470
E eu estou indo a iniciar
Lo para o inicio da lista.

97
00:04:16,470 --> 00:04:20,050
Así, pode tipo de pensar neste
como o profesor me o outro día,

98
00:04:20,050 --> 00:04:23,580
tipo de apuntando para alguén
entre os nosos seres humanos como voluntarios.

99
00:04:23,580 --> 00:04:26,470
Entón, eu son unha variable temporal que é
só apuntando para o mesmo

100
00:04:26,470 --> 00:04:31,390
que a nosa coincidentemente chamado
voluntario David tamén estaba apuntando.

101
00:04:31,390 --> 00:04:35,440
Agora, mentres punteiro é
non nulo, porque recordo

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

103
00:04:40,350 --> 00:04:44,280
así, mentres eu non estou a apuntar cara a
terra como a nosa última voluntario

104
00:04:44,280 --> 00:04:47,190
era, imos adiante
e faga o seguinte.

105
00:04:47,190 --> 00:04:51,820
Se pointer-- e agora eu medio que quero
para facer o que fixemos co alumno

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

107
00:04:57,410 --> 00:05:02,290
é igual á variable n, a
argumento que foi transmitido,

108
00:05:02,290 --> 00:05:05,370
entón eu quero ir adiante
e dicir return true.

109
00:05:05,370 --> 00:05:11,020
Eu atopei o número N dentro
un dos nós da miña lista ligada.

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

111
00:05:13,500 --> 00:05:17,260
porque punteiro, PTR, é
de feito, un punteiro, un enderezo,

112
00:05:17,260 --> 00:05:20,632
realmente podemos marabillosas
Finalmente usar unha peza de sintaxe

113
00:05:20,632 --> 00:05:22,590
este tipo de marcas
sentido intuitivo e, de feito,

114
00:05:22,590 --> 00:05:27,870
usar unha frecha aquí, o que significa ir de
este enderezo ao número enteiro alí dentro.

115
00:05:27,870 --> 00:05:30,160
Polo tanto, é moi semellante en
espírito ao operador punto,

116
00:05:30,160 --> 00:05:33,860
senón porque punteiro non é un punteiro
e non unha struct en si real,

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

118
00:05:35,380 --> 00:05:40,620
>> Polo tanto, se o nodo actual que eu, o
variable temporal, estou apuntando para

119
00:05:40,620 --> 00:05:43,060
non é N, o que quero facer?

120
00:05:43,060 --> 00:05:45,910
Ben, cos meus voluntarios humanos
que tivemos aquí o outro día,

121
00:05:45,910 --> 00:05:49,710
o meu primeiro ser humano non é o que eu
quere, e quizais o segundo humano non é

122
00:05:49,710 --> 00:05:52,660
o que quero, eo terceiro, I
precisa para manterse fisicamente en movemento.

123
00:05:52,660 --> 00:05:54,690
Como como fago para percorrer unha lista?

124
00:05:54,690 --> 00:05:57,470
Cando tivemos un array ti,
só fixen como eu plus plus.

125
00:05:57,470 --> 00:06:03,660
Pero, neste caso, pode
facer punteiro, queda, punteiro, a continuación.

126
00:06:03,660 --> 00:06:07,580
Noutras palabras, o campo seguinte
é como todas as mans esquerda

127
00:06:07,580 --> 00:06:10,880
que os nosos voluntarios humanos o luns
estaban a usar para ligar a algún outro nodo.

128
00:06:10,880 --> 00:06:12,890
Aqueles eran os seus veciños próximos.

129
00:06:12,890 --> 00:06:17,060
>> Entón, se eu queira pasar por esta lista,
Non podo simplemente facer eu plus plus máis,

130
00:06:17,060 --> 00:06:20,120
Eu teño que dicir, en vez
I, punteiro, vai

131
00:06:20,120 --> 00:06:24,650
para igualar calquera que sexa o campo seguinte é,
O seguinte campo, o campo seguinte é,

132
00:06:24,650 --> 00:06:28,350
seguindo todas esas mans esquerdas
que tivemos no escenario ligazón

133
00:06:28,350 --> 00:06:30,000
para algúns valores seguintes.

134
00:06:30,000 --> 00:06:32,590
E se eu pasar
Toda esa iteración,

135
00:06:32,590 --> 00:06:39,330
e, finalmente, eu bati nulo non
N atopou aínda, eu só retornar falso.

136
00:06:39,330 --> 00:06:44,100
Entón, de novo, todo o que estamos facendo aquí,
segundo a imaxe dun momento atrás,

137
00:06:44,100 --> 00:06:47,840
comeza por apuntar á
inicio da lista presuntamente.

138
00:06:47,840 --> 00:06:50,970
E entón eu vaia, é o valor
Estou buscando igual a nove?

139
00:06:50,970 --> 00:06:52,650
Se é así, volvo verdade e eu son feito.

140
00:06:52,650 --> 00:06:56,450
Se non, eu actualizar miña man,
Punteiro AKA, para apuntar

141
00:06:56,450 --> 00:06:59,540
a localización da próxima frecha e,
a continuación, a localización próxima da frecha,

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

143
00:07:00,480 --> 00:07:03,770
Estou simplemente camiñando a través desta matriz.

144
00:07:03,770 --> 00:07:06,010
>> Entón, de novo, quen lle importa?

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

146
00:07:07,861 --> 00:07:10,360
Ben, lembre que introducimos
a noción de unha pila, que

147
00:07:10,360 --> 00:07:15,400
é un tipo abstracto de datos na medida en que é
non é unha cousa C, non é unha cousa CS50,

148
00:07:15,400 --> 00:07:19,430
é unha idea abstracta, esa idea de
empilhado cousas enriba da outra

149
00:07:19,430 --> 00:07:21,820
que pode ser aplicado en
acios de xeitos diferentes.

150
00:07:21,820 --> 00:07:25,600
E un xeito que propuxemos foi con
unha matriz, ou cunha lista ligada.

151
00:07:25,600 --> 00:07:29,570
E parece que canonicamente, unha
pila soporta, polo menos, dúas operacións.

152
00:07:29,570 --> 00:07:32,320
E as palabras de zumbido son pulo, para
empurrar algo para a pila,

153
00:07:32,320 --> 00:07:34,770
como unha nova bandexa no
comedor, ou pop,

154
00:07:34,770 --> 00:07:39,000
o que significa que para eliminar o máis alto
bandexa do conxunto na cea

155
00:07:39,000 --> 00:07:41,500
hall, e entón pode que algúns
así como outras operacións.

156
00:07:41,500 --> 00:07:45,770
Entón, como podemos definir a estrutura
que agora estamos chamando unha pila?

157
00:07:45,770 --> 00:07:50,020
>> Ben, temos todo o requisite
sintaxe á nosa disposición en C. Eu digo,

158
00:07:50,020 --> 00:07:53,830
me dea unha definición de tipo de
unha estrutura dentro dunha pila,

159
00:07:53,830 --> 00:07:58,030
Eu vou dicir é un array, dun
todo morea de números e logo tamaño.

160
00:07:58,030 --> 00:08:00,930
Polo tanto, noutras palabras, se eu queira
para aplicar tanto no código,

161
00:08:00,930 --> 00:08:03,830
Déixame ir só unha especie de
deseñar o que se di.

162
00:08:03,830 --> 00:08:06,317
Polo tanto, este está dicindo, me dea un
estrutura que ten unha matriz,

163
00:08:06,317 --> 00:08:09,400
e eu non sei o que é capacidade,
é aparentemente algunha constante que eu teño

164
00:08:09,400 --> 00:08:10,858
definido noutro lugar, e iso é bo.

165
00:08:10,858 --> 00:08:15,260
Pero supoño que non é máis que un,
dous, tres, catro, cinco.

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

167
00:08:16,700 --> 00:08:21,730
Este elemento dentro da miña
estrutura serán chamados números.

168
00:08:21,730 --> 00:08:24,020
E entón eu teño un
outra variable aparentemente

169
00:08:24,020 --> 00:08:27,814
chamado tamaño que inicialmente eu vou
estipular é inicializar a cero.

170
00:08:27,814 --> 00:08:29,730
Se non hai nada en
a pila, o tamaño é cero,

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

172
00:08:31,420 --> 00:08:33,450
Eu non teño idea o que está aí aínda.

173
00:08:33,450 --> 00:08:36,059
>> Entón, se eu quero empurrar
algo na pila,

174
00:08:36,059 --> 00:08:40,780
supoñamos que eu chamo de impulso función, e
Digo empurrar 50, como o número 50,

175
00:08:40,780 --> 00:08:44,090
onde proporía
Eu deseña-lo nesa matriz?

176
00:08:44,090 --> 00:08:47,124
Hai cinco diferentes respostas posibles.

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

178
00:08:48,790 --> 00:08:51,899
O obxectivo aquí, unha vez máis, chamar a
pulo función, pasa un argumento

179
00:08:51,899 --> 00:08:52,940
de 50, onde podo poñelas?

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

181
00:08:55,680 --> 00:08:59,052
Cinco possible-- 20% de posibilidades
de adiviñar correctamente.

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

183
00:08:59,896 --> 00:09:00,740
>> Audiencia: Extrema-dereita.

184
00:09:00,740 --> 00:09:01,990
>> COLUMNA 1: Extrema-dereita.

185
00:09:01,990 --> 00:09:08,359
Existe agora unha oportunidade de 25%
de adiviñar correctamente.

186
00:09:08,359 --> 00:09:09,650
De xeito que sería realmente bo.

187
00:09:09,650 --> 00:09:12,770
Por convención, eu vou dicir cunha matriz,
que sería normalmente comezar á esquerda,

188
00:09:12,770 --> 00:09:14,519
pero poderiamos certamente
comeza pola dereita.

189
00:09:14,519 --> 00:09:17,478
Entón, o alerón aquí sería eu son
probablemente, vai deseña-lo á esquerda,

190
00:09:17,478 --> 00:09:20,060
así como nunha matriz normal, onde
Eu comezo a ir á esquerda cara á dereita.

191
00:09:20,060 --> 00:09:21,780
Pero se pode virar
aritmética, todo ben.

192
00:09:21,780 --> 00:09:23,060
Non é só convencional.

193
00:09:23,060 --> 00:09:24,880
OK, eu teño que facer unha
máis cambios aínda.

194
00:09:24,880 --> 00:09:27,710
Agora que eu empurre algo
para a pila, o que está preto?

195
00:09:27,710 --> 00:09:29,400
>> Todo ben, eu teño que aumentar o tamaño.

196
00:09:29,400 --> 00:09:32,600
Entón deixe-me ir adiante e só
actualizar esta, que era igual a cero.

197
00:09:32,600 --> 00:09:35,950
E, no canto agora, eu vou
para poñer por valor de un.

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

199
00:09:39,460 --> 00:09:42,680
Ben, eu teño que facer unha
cambio, que é ata o tamaño dous.

200
00:09:42,680 --> 00:09:46,100
E entón supoño que empurrar unha
número na pila como 61,

201
00:09:46,100 --> 00:09:52,530
agora eu teño actualizar o tamaño unha
tempo, e obter o valor 3 como o tamaño.

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

203
00:09:54,690 --> 00:09:57,250
Agora pop, por convención,
Non é preciso un argumento.

204
00:09:57,250 --> 00:10:00,430
Cunha pila, o conxunto
punto da metáfora bandexa

205
00:10:00,430 --> 00:10:03,450
é que non ten poder discreccionario
para ir buscar a bandexa, todo o que pode facer

206
00:10:03,450 --> 00:10:06,330
é pop o máis alto dunha
pila, só porque.

207
00:10:06,330 --> 00:10:08,010
Iso é o que esta estrutura de datos fai.

208
00:10:08,010 --> 00:10:12,250
>> Entón, por que a lóxica si
dicir pop, o que sae?

209
00:10:12,250 --> 00:10:13,080
Entón, 61.

210
00:10:13,080 --> 00:10:15,402
Entón, o que realmente é o ordenador
vai facer na memoria?

211
00:10:15,402 --> 00:10:16,610
Que o meu código ten que facer?

212
00:10:16,610 --> 00:10:20,330
Que proporía
nós cambiamos a pantalla?

213
00:10:20,330 --> 00:10:23,410
O que debe cambiar?

214
00:10:23,410 --> 00:10:24,960
Sentímolo?

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

216
00:10:26,334 --> 00:10:27,500
Entón eu sempre podo facelo.

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

218
00:10:28,640 --> 00:10:30,980
E entón o que os outros
cambio ten que ocorrer?

219
00:10:30,980 --> 00:10:33,160
Tamaño, probablemente, ten que volver para dous.

220
00:10:33,160 --> 00:10:34,210
E así todo ben.

221
00:10:34,210 --> 00:10:36,690
Pero agarde un minuto, tamaño
un momento atrás tiña tres anos.

222
00:10:36,690 --> 00:10:38,240
Nós só facer unha verificación de sanidade rápida.

223
00:10:38,240 --> 00:10:41,810
Como é que sabemos que nos
quería desfacerse de 61?

224
00:10:41,810 --> 00:10:42,760
Porque estamos estalado.

225
00:10:42,760 --> 00:10:46,450
E entón eu teño esta segunda tamaño da propiedade.

226
00:10:46,450 --> 00:10:48,470
>> Agarde un minuto, estou
pensar de volta para a segunda semana

227
00:10:48,470 --> 00:10:51,660
cando comezamos a falar
arrays, onde este foi lugar de cero,

228
00:10:51,660 --> 00:10:55,920
este foi un lugar, este foi localización
dous, este é o lugar de tres, catro,

229
00:10:55,920 --> 00:10:58,460
parece que o
relación entre o tamaño

230
00:10:58,460 --> 00:11:02,780
eo elemento que quero eliminar
desde a matriz parece ser só o que?

231
00:11:02,780 --> 00:11:05,120
Tamaño menos un.

232
00:11:05,120 --> 00:11:07,786
E foi así que, como seres humanos
sabemos que 61 ven en primeiro lugar.

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

234
00:11:09,160 --> 00:11:11,701
Cando o seu código, onde probablemente
quere facer o tamaño menos un,

235
00:11:11,701 --> 00:11:14,950
Así, tres menos un é dous, e que
significa que queren se librar de 61.

236
00:11:14,950 --> 00:11:18,000
E entón podemos realmente actualizar
o tamaño de xeito que o tamaño agora

237
00:11:18,000 --> 00:11:20,300
vai desde tres a só dous.

238
00:11:20,300 --> 00:11:24,520
E só para ser pedante, eu vou
a propoñer que eu son feito, non?

239
00:11:24,520 --> 00:11:27,660
Vostede proposto intuitivamente
correctamente debería librarse de 61.

240
00:11:27,660 --> 00:11:30,700
Pero non ten que tipo de
tipo de libro de 61?

241
00:11:30,700 --> 00:11:33,790
Eu efectivamente esquecido
que é realmente alí.

242
00:11:33,790 --> 00:11:37,680
E creo que volta a PSet4, se leu
o artigo sobre forense, o PDF

243
00:11:37,680 --> 00:11:40,780
que tiñamos vostedes ler, ou
vai ler esta semana para PSet4.

244
00:11:40,780 --> 00:11:44,300
Lembre que este é realmente pertinente para
toda a idea de computación forense.

245
00:11:44,300 --> 00:11:47,820
O que un ordenador fai é xeralmente
simplemente se esquece de onde algo é,

246
00:11:47,820 --> 00:11:51,300
pero non ir e como
tentar risco-lo fóra ou substitución

247
00:11:51,300 --> 00:11:54,560
eses bits con ceros e uns
ou algún outro estándar chou

248
00:11:54,560 --> 00:11:56,690
a non ser que mesmo facelo deliberadamente.

249
00:11:56,690 --> 00:11:58,930
Así, a súa intuición estaba
ben, imos nos librar de 61.

250
00:11:58,930 --> 00:12:00,650
Pero, en realidade, non ten que se preocupar.

251
00:12:00,650 --> 00:12:04,040
Nós só necesitamos esquecer que
está alí cambiando noso tamaño.

252
00:12:04,040 --> 00:12:05,662
>> Agora hai un problema con esta pila.

253
00:12:05,662 --> 00:12:07,620
Se eu continuar presionando as cousas
para a pila, o que é

254
00:12:07,620 --> 00:12:11,167
obviamente, vai pasar
en só algúns momentos do tempo?

255
00:12:11,167 --> 00:12:12,500
Nós imos quedar sen espazo.

256
00:12:12,500 --> 00:12:13,580
E o que imos facer?

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

258
00:12:14,680 --> 00:12:19,000
Esta aplicación non deixa
nos redimensionar a matriz, porque usar

259
00:12:19,000 --> 00:12:21,240
esta sintaxe, se
creo que volta a dúas semanas,

260
00:12:21,240 --> 00:12:23,520
xa que declarou
o tamaño dunha matriz,

261
00:12:23,520 --> 00:12:26,780
nós non vimos aínda un mecanismo onde
pode cambiar o tamaño da matriz.

262
00:12:26,780 --> 00:12:29,020
E, de feito C non ten este recurso.

263
00:12:29,020 --> 00:12:32,524
Se di que me dar cinco
Nths, chamalos de números,

264
00:12:32,524 --> 00:12:33,940
iso é todo o que está indo para obtelo.

265
00:12:33,940 --> 00:12:38,790
Entón, o que facemos agora como de luns ten
a capacidade de expresar unha solución

266
00:12:38,790 --> 00:12:42,480
porén, só necesitamos axustar
a definición da nosa pila

267
00:12:42,480 --> 00:12:46,840
a menos algúns matriz codificados,
pero só para almacenar un enderezo.

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

269
00:12:47,890 --> 00:12:51,690
Agora só temos que estar cómodo con
o feito de que cando o meu programa é executado,

270
00:12:51,690 --> 00:12:53,730
Eu estou indo a presuntamente
ten que preguntar o ser humano,

271
00:12:53,730 --> 00:12:55,110
cantos números que quere almacenar?

272
00:12:55,110 --> 00:12:56,776
Así, a entrada ten que vir de algures.

273
00:12:56,776 --> 00:12:59,140
Pero xa sei que
número, entón podo só

274
00:12:59,140 --> 00:13:02,470
usar o que traballa para dar
me unha peza de memoria?

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

276
00:13:03,580 --> 00:13:06,710
E podo dicir calquera número de
bytes Quero voltar estes Nths.

277
00:13:06,710 --> 00:13:10,910
E todo o que teño para almacenar os números
variable aquí dentro deste struct

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

279
00:13:13,480 --> 00:13:18,440
O que realmente vai ao
números nese escenario?

280
00:13:18,440 --> 00:13:21,300
É un punteiro para o primeiro
byte dese anaco de memoria,

281
00:13:21,300 --> 00:13:24,940
ou máis especificamente, a dirección
do primeiro destes bytes.

282
00:13:24,940 --> 00:13:27,300
Non importa se é un
bytes ou mil millóns de bytes,

283
00:13:27,300 --> 00:13:28,890
Só se preocupe co primeiro.

284
00:13:28,890 --> 00:13:31,530
Porque o que malloc e garantías
miñas garantías do sistema operativo,

285
00:13:31,530 --> 00:13:34,170
é que o anaco de memoria I
obter, que vai ser contiguos.

286
00:13:34,170 --> 00:13:35,378
Non vai ser lagoas.

287
00:13:35,378 --> 00:13:38,576
Entón, se eu pedín a 50
ou bytes 1.000 bytes,

288
00:13:38,576 --> 00:13:40,450
están todos indo a ser
back to back to back.

289
00:13:40,450 --> 00:13:44,500
E desde que eu recordo como gran, como
Eu pedín moito, todo o que precisa saber

290
00:13:44,500 --> 00:13:46,230
é o primeiro tal dirección.

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

292
00:13:48,660 --> 00:13:51,280
Aínda que, iso vai levar
máis tempo para escribir isto,

293
00:13:51,280 --> 00:13:55,900
poderiamos agora recolocar que a memoria por
só almacenar un enderezo diferente alí

294
00:13:55,900 --> 00:13:59,060
se queremos unha maior ou mesmo
unha peza menor de memoria.

295
00:13:59,060 --> 00:14:00,170
Entón aquí para atopar un compromiso.

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

297
00:14:01,360 --> 00:14:03,350
Aínda temos
contiguidade estou afirmando.

298
00:14:03,350 --> 00:14:05,881
Porque malloc daranos
unha peza contiguo de memoria.

299
00:14:05,881 --> 00:14:08,630
Pero iso vai ser unha dor no
o pescozo para nós, o programador,

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

301
00:14:09,770 --> 00:14:10,730
É só máis traballo.

302
00:14:10,730 --> 00:14:13,930
Necesitamos código semellante ao que eu era
batendo fóra só un momento atrás.

303
00:14:13,930 --> 00:14:16,120
Moi factible, senón que engade complexidade.

304
00:14:16,120 --> 00:14:19,520
E así creador tempo, programador
o tempo é aínda outro recurso

305
00:14:19,520 --> 00:14:22,520
para que puidésemos necesita gastar
moito tempo para obter novas características.

306
00:14:22,520 --> 00:14:24,020
E despois, claro, hai unha fila.

307
00:14:24,020 --> 00:14:26,227
Non imos entrar nese
un en moi detalle.

308
00:14:26,227 --> 00:14:27,560
Pero é moi semellante en espírito.

309
00:14:27,560 --> 00:14:31,220
Podería aplicar unha cola, e
súas operacións correspondentes,

310
00:14:31,220 --> 00:14:35,660
enqueue ou dequeue, como engadir ou eliminar,
é só unha forma de dicilo máis chique,

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

312
00:14:38,100 --> 00:14:41,170
Só podo darme un struct
que de novo ten matriz dun número,

313
00:14:41,170 --> 00:14:44,000
que de novo ten un tamaño,
Pero por que eu teño agora

314
00:14:44,000 --> 00:14:46,940
para manter o control da cabeza dunha fila?

315
00:14:46,940 --> 00:14:50,630
Non teño que saber
a cabeza da miña stack.

316
00:14:50,630 --> 00:14:53,570
Ben, se eu volver á
queue-- imos duro

317
00:14:53,570 --> 00:14:57,870
codifica-lo como tendo como cinco
enteiros en aquí potencialmente.

318
00:14:57,870 --> 00:15:00,940
Polo tanto, este é cero, un, dous, tres, catro.

319
00:15:00,940 --> 00:15:03,430
Este será
números chamados de novo.

320
00:15:03,430 --> 00:15:06,940
E iso vai ser chamado de tamaño.

321
00:15:06,940 --> 00:15:10,056
>> Por que non é suficiente
ter só o tamaño?

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

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

324
00:15:14,220 --> 00:15:20,150
Agora eu vou enfileirar 50, e, a continuación,
51, e despois 61, e Dot Dot Dot.

325
00:15:20,150 --> 00:15:21,070
Entón, iso é enqueue.

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

327
00:15:23,176 --> 00:15:25,050
E iso parece idéntico
para unha pila de momento,

328
00:15:25,050 --> 00:15:27,190
só que eu teño que facer un cambio.

329
00:15:27,190 --> 00:15:33,680
Necesito actualizar ese tamaño, entón eu ir
de cero a un de dous a tres agora.

330
00:15:33,680 --> 00:15:35,760
¿Como retirar da cola?

331
00:15:35,760 --> 00:15:36,890
Que pasa con dequeue?

332
00:15:36,890 --> 00:15:41,950
Quen debe saír esta lista primeiro
se é a liña na tenda de Apple?

333
00:15:41,950 --> 00:15:42,780
Entón, 50.

334
00:15:42,780 --> 00:15:44,700
Entón é medio complicado desta vez.

335
00:15:44,700 --> 00:15:47,880
Considerando última vez que foi super
doado simplemente facer o tamaño menos un,

336
00:15:47,880 --> 00:15:51,440
Chegar ao final da miña matriz efectivamente
onde as cifras son, el elimina 61.

337
00:15:51,440 --> 00:15:52,920
Pero eu non quero eliminar 61.

338
00:15:52,920 --> 00:15:55,030
Quero ter 50 anos, que
estaba alí na 5:00

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

340
00:15:56,790 --> 00:16:01,200
E así se librar de 50, I
Non pode simplemente facelo, non?

341
00:16:01,200 --> 00:16:02,547
Podo atravesar a 50.

342
00:16:02,547 --> 00:16:04,380
Pero nós só dixo que
Non ten que ser tan anal

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

344
00:16:06,330 --> 00:16:08,090
Podemos simplemente esquecer onde está.

345
00:16:08,090 --> 00:16:12,330
>> Pero se eu cambiar o meu tamaño agora
dous, é esta información suficiente

346
00:16:12,330 --> 00:16:15,711
para saber o que está a suceder na miña cola?

347
00:16:15,711 --> 00:16:16,680
En realidade non.

348
00:16:16,680 --> 00:16:19,830
Así como o meu tamaño é dous, pero
onde é que a cola de comezar,

349
00:16:19,830 --> 00:16:22,980
especialmente se eu teño
eses mesmos números na memoria.

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

351
00:16:24,260 --> 00:16:27,090
Entón, eu teño lembrar
Agora, onde a cabeza é.

352
00:16:27,090 --> 00:16:29,630
E así como eu propuxen a
alí, nós imos ter chamado só

353
00:16:29,630 --> 00:16:33,729
Fronte nth, cuxa inicial
valor debe ser o que?

354
00:16:33,729 --> 00:16:35,270
Cero, só o comezo da lista.

355
00:16:35,270 --> 00:16:40,876
Pero agora, ademais de decrementing
o tamaño, nós só incrementar a fronte.

356
00:16:40,876 --> 00:16:42,000
Aquí está outro problema.

357
00:16:42,000 --> 00:16:43,030
Entón, cando eu sigo indo.

358
00:16:43,030 --> 00:16:47,520
Supoñamos que este é o número de
como 121, 124, e, a continuación, caramba,

359
00:16:47,520 --> 00:16:48,610
Estou fóra do espazo.

360
00:16:48,610 --> 00:16:50,390
Pero agarde un minuto, eu non son.

361
00:16:50,390 --> 00:16:55,630
Entón, neste punto da historia,
supoñamos que o tamaño é un, dous,

362
00:16:55,630 --> 00:17:00,370
tres, catro, de forma que o supor
tamaño é catro, a fronte é un,

363
00:17:00,370 --> 00:17:01,621
para 51 é a parte da fronte.

364
00:17:01,621 --> 00:17:04,329
Quero poñer outro número aquí,
pero, caramba, eu estou fóra do espazo.

365
00:17:04,329 --> 00:17:06,710
Pero eu non son realmente, non?

366
00:17:06,710 --> 00:17:11,192
Onde eu podería poñer algún
valor adicional, como 171?

367
00:17:11,192 --> 00:17:13,400
Si, eu podería só unha especie de
volver para alí, non?

368
00:17:13,400 --> 00:17:18,161
E, a continuación, atravesar a 50, ou
só substituílo con 171.

369
00:17:18,161 --> 00:17:20,410
E se está a se pregunta por
nosos números quedou tan aleatorio,

370
00:17:20,410 --> 00:17:24,150
estes adoitan ser tomadas ordenador
cursos de ciencias en Harvard tras CS50.

371
00:17:24,150 --> 00:17:27,510
Pero iso foi unha boa optimización,
porque agora eu non estou perdendo espazo.

372
00:17:27,510 --> 00:17:30,750
Eu aínda teño que lembrar
o grande esa cousa é total.

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

374
00:17:31,500 --> 00:17:33,375
Porque eu non quero
comezar a substituír 51.

375
00:17:33,375 --> 00:17:36,260
Entón agora eu estou sen espazo,
de xeito que o mesmo problema de antes.

376
00:17:36,260 --> 00:17:39,140
Pero se pode ver como agora
no seu código, probablemente

377
00:17:39,140 --> 00:17:41,910
ten que escribir un pouco máis
complexidade para que isto ocorre.

378
00:17:41,910 --> 00:17:44,510
E, de feito, o operador
en C probablemente permite

379
00:17:44,510 --> 00:17:48,110
vostede Magic facelo a circularidade?

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

381
00:17:50,160 --> 00:17:53,160
Entón, o que é legal sobre unha fila,
aínda que manter matrices deseño

382
00:17:53,160 --> 00:17:56,520
como estas liñas rectas como, se
tipo de pensar sobre iso como encurvamento

383
00:17:56,520 --> 00:18:00,341
en torno a como un círculo, a continuación, pode
intuitivamente que tipo de obras mental

384
00:18:00,341 --> 00:18:01,590
Eu creo que un pouco máis limpa.

385
00:18:01,590 --> 00:18:05,190
Aínda tería que aplicar
que modelo mental no código.

386
00:18:05,190 --> 00:18:07,550
Entón, non é difícil,
en definitiva, para aplicar,

387
00:18:07,550 --> 00:18:12,430
pero aínda perder o size-- vez, o
capacidade de cambiar o tamaño, a menos que fagamos isto.

388
00:18:12,430 --> 00:18:15,310
>> Debemos librar-se da matriz, nós
substituílo por un único punteiro,

389
00:18:15,310 --> 00:18:20,010
e, a continuación, en algún lugar no meu código que teño
a chamar o que funciona para realmente crear

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

391
00:18:23,720 --> 00:18:26,190
Malloc, ou algunha similar
función, exactamente.

392
00:18:26,190 --> 00:18:30,481
Calquera preguntas sobre pilas ou filas.

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

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

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

396
00:18:34,240 --> 00:18:35,830
Cal módulo usaría aquí.

397
00:18:35,830 --> 00:18:38,520
Así, en xeral, cando se utiliza
mod, faría iso

398
00:18:38,520 --> 00:18:40,620
co tamaño do
estrutura enteira de datos.

399
00:18:40,620 --> 00:18:44,120
Entón, algo así como cinco ou capacidade, se
é constante, está probablemente parte.

400
00:18:44,120 --> 00:18:47,100
Pero só facendo modulo cinco
probablemente non é suficiente,

401
00:18:47,100 --> 00:18:51,380
porque necesitamos saber é que nós
participa en torno de aquí ou aquí ou aquí.

402
00:18:51,380 --> 00:18:54,160
Entón probablemente está tamén
Vai querer involucrarse

403
00:18:54,160 --> 00:18:57,220
o tamaño da cousa, ou
a variable fronte tamén.

404
00:18:57,220 --> 00:19:00,140
Entón é só iso relativamente
expresión aritmética simple,

405
00:19:00,140 --> 00:19:02,000
pero módulo sería ingrediente clave.

406
00:19:02,000 --> 00:19:03,330
>> Entón, curtametraxe se quere.

407
00:19:03,330 --> 00:19:05,780
Unha animación que algúns
pobos noutra universidade

408
00:19:05,780 --> 00:19:08,060
xuntos que temos
adaptado para este fío.

409
00:19:08,060 --> 00:19:12,630
Trátase de aprender a Jack
feitos sobre filas e estatísticas.

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

411
00:19:19,010 --> 00:19:21,890
>> PELÍCULA: Había unha vez,
había un cara chamado Jack.

412
00:19:21,890 --> 00:19:25,330
Cando el veu para facer amigos,
Jack non ten un talento especial.

413
00:19:25,330 --> 00:19:28,220
Entón Jack foi falar co
máis cara popular que coñecía.

414
00:19:28,220 --> 00:19:30,920
Foi para Lou e preguntou: O que fago?

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

416
00:19:33,400 --> 00:19:36,050
Ben, el comezou, só
mira como está vestida.

417
00:19:36,050 --> 00:19:38,680
Non ten ningunha roupa
cunha mirada diferente?

418
00:19:38,680 --> 00:19:39,660
Si, dixo Jack.

419
00:19:39,660 --> 00:19:40,840
Eu seguramente facer.

420
00:19:40,840 --> 00:19:43,320
Veña á miña casa e
Eu vou amosar a vostede.

421
00:19:43,320 --> 00:19:44,550
Entón, eles foron para Jack.

422
00:19:44,550 --> 00:19:47,520
Jack e Lou mostrou a caixa
onde gardaba as súas camisas,

423
00:19:47,520 --> 00:19:49,260
e os pantalóns e as medias.

424
00:19:49,260 --> 00:19:52,290
Lou dixo, eu vexo que ten
todas as súas roupas nunha pila.

425
00:19:52,290 --> 00:19:54,870
Por que non usar algún
outros de cando en vez?

426
00:19:54,870 --> 00:19:58,020
>> Jack dixo, ben, cando
eliminar roupa e medias,

427
00:19:58,020 --> 00:20:00,780
Eu lava-los e colocá-
Los no cadro.

428
00:20:00,780 --> 00:20:03,210
A continuación, vén o seguinte
mañá, e se eu pulo.

429
00:20:03,210 --> 00:20:06,380
Ir á caixa e obter
miñas roupas fóra do cumio.

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

431
00:20:09,070 --> 00:20:12,080
El mantivo roupa, CDs,
e libros na pila.

432
00:20:12,080 --> 00:20:14,420
Cando chegou a
algo para ler ou para levar,

433
00:20:14,420 --> 00:20:17,100
el escollería o cumio libro ou roupa interior.

434
00:20:17,100 --> 00:20:19,500
Entón, cando se fixo, el
ía poñer-lo de volta.

435
00:20:19,500 --> 00:20:21,970
Volver sería ir, na parte superior do conxunto.

436
00:20:21,970 --> 00:20:24,460
Sei a solución,
dixo un alto triunfante.

437
00:20:24,460 --> 00:20:27,090
Debe aprender a
comezar a usar unha cola.

438
00:20:27,090 --> 00:20:29,870
Lou colleu roupa de Jack e
colgou os no armario.

439
00:20:29,870 --> 00:20:32,710
E cando baleirara
a caixa, simplemente xogouse a.

440
00:20:32,710 --> 00:20:36,500
>> Entón el dixo, agora Jack, a finais de
o día, poñer a roupa na parte esquerda

441
00:20:36,500 --> 00:20:37,990
cando poñer-los fóra.

442
00:20:37,990 --> 00:20:41,300
Entón, mañá pola mañá cando
ver a luz do sol, incorporarse a roupa

443
00:20:41,300 --> 00:20:43,440
á dereita, a partir da extremidade da liña.

444
00:20:43,440 --> 00:20:44,880
Non ve? dixo Lou.

445
00:20:44,880 --> 00:20:46,370
Que vai ser tan bo.

446
00:20:46,370 --> 00:20:49,770
Vai empregar todo xa
antes de usar algo dúas veces.

447
00:20:49,770 --> 00:20:52,670
E con todo en filas
no seu armario e andel,

448
00:20:52,670 --> 00:20:55,160
Jack comezou a sentirse
moi seguro de si.

449
00:20:55,160 --> 00:20:59,720
Todo grazas a Lou e
súa marabillosa cola.

450
00:20:59,720 --> 00:21:01,220
COLUMNA 1: Todo ben, é encantador.

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

452
00:21:05,920 --> 00:21:10,080
Entón, o que foi realmente a suceder
por baixo do capuz agora?

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

454
00:21:12,370 --> 00:21:15,680
que temos a capacidade de crear
anacos de memoria para nós mesmos

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

456
00:21:16,344 --> 00:21:18,510
Polo tanto, esta é unha imaxe que
vislumbrada só o outro día.

457
00:21:18,510 --> 00:21:21,180
Nós realmente non habitará
sobre el, pero esta imaxe

458
00:21:21,180 --> 00:21:24,180
foi pasando por baixo
o capó hai semanas.

459
00:21:24,180 --> 00:21:27,050
E así que representa, só
un rectángulo que temos deseñado,

460
00:21:27,050 --> 00:21:28,180
a memoria do seu ordenador.

461
00:21:28,180 --> 00:21:31,850
E quizais o seu ordenador, ou CS50
ID, ten un gigabyte de memoria RAM ou

462
00:21:31,850 --> 00:21:33,050
ou dous gigabytes ou catro.

463
00:21:33,050 --> 00:21:34,450
Realmente non importa.

464
00:21:34,450 --> 00:21:37,240
O seu sistema operativo
Windows ou Mac OS ou Linux,

465
00:21:37,240 --> 00:21:41,120
esencialmente permite que o programa
pensando que ten acceso

466
00:21:41,120 --> 00:21:42,982
para o conxunto do
a memoria do seu ordenador,

467
00:21:42,982 --> 00:21:45,440
aínda que pode estar executando
varios programas á vez.

468
00:21:45,440 --> 00:21:46,990
Entón, en realidade, que realmente non funciona.

469
00:21:46,990 --> 00:21:49,448
Pero é tipo de unha ilusión
dado a todos os seus programas.

470
00:21:49,448 --> 00:21:53,110
Entón se tivese dous gigas de memoria RAM, este
É así que o ordenador pode pensar niso.

471
00:21:53,110 --> 00:21:57,110
>> Agora coincidentemente, un deles
cousas, un deses segmentos de memoria,

472
00:21:57,110 --> 00:21:58,350
chámase unha pila.

473
00:21:58,350 --> 00:22:01,680
E, de feito calquera momento
ata agora en escribir código

474
00:22:01,680 --> 00:22:05,900
que ten chamado a
función, por exemplo principal.

475
00:22:05,900 --> 00:22:08,410
Lembre que en calquera momento eu teño
memoria tirada do ordenador,

476
00:22:08,410 --> 00:22:10,640
Sempre deseñar tipo de
metade dun rectángulo aquí

477
00:22:10,640 --> 00:22:12,520
e non se incomoda de falar
sobre o que está enriba.

478
00:22:12,520 --> 00:22:15,980
Porque cando principal chámase, eu reivindico
que comeza este anaco de memoria

479
00:22:15,980 --> 00:22:16,970
que vai para abaixo aquí.

480
00:22:16,970 --> 00:22:20,650
E se unha función principal chamada
como intercambio, así cambio vai aquí.

481
00:22:20,650 --> 00:22:23,720
E ao parecer, iso é
onde acaba.

482
00:22:23,720 --> 00:22:26,277
En algo chamado unha pila
dentro da memoria do seu ordenador.

483
00:22:26,277 --> 00:22:28,360
Agora, ao final do día,
este é só aborda.

484
00:22:28,360 --> 00:22:30,680
É como byte cero,
byte un, byte 2 millóns.

485
00:22:30,680 --> 00:22:33,130
Pero se pensar sobre iso
como este obxecto rectangular,

486
00:22:33,130 --> 00:22:35,130
todo o que estamos facendo cada
xa que chamar a unha función é

487
00:22:35,130 --> 00:22:37,180
estratificación unha nova porción de memoria.

488
00:22:37,180 --> 00:22:41,700
Estamos dando esa función dunha porción
da súa propia memoria para traballar.

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

490
00:22:44,490 --> 00:22:46,400
Porque se temos
algo así como intercambio

491
00:22:46,400 --> 00:22:51,610
e dúas variables locais como A e B e
podemos cambiar estes valores a partir de un e dous

492
00:22:51,610 --> 00:22:55,130
para dous e un, Lembre
que cando retorna permuta,

493
00:22:55,130 --> 00:22:58,330
é coma se esa porción
de memoria é só ir.

494
00:22:58,330 --> 00:23:00,080
En realidade, aínda é
hai forense.

495
00:23:00,080 --> 00:23:01,940
E algo aínda está realmente alí.

496
00:23:01,940 --> 00:23:05,410
Pero conceptualmente, é como
aínda é completamente desaparecido.

497
00:23:05,410 --> 00:23:10,910
E así principal non sabe calquera dos traballos
que se fixo nesa función de intercambio,

498
00:23:10,910 --> 00:23:14,890
a non ser que sexa realmente pasou naqueles
argumentos de punteiro ou por referencia.

499
00:23:14,890 --> 00:23:17,790
Agora, a solución fundamental
para este problema con permuta

500
00:23:17,790 --> 00:23:19,970
está pasando por cousas no enderezo.

501
00:23:19,970 --> 00:23:23,250
Pero ao parecer, tamén, o que é
vén acontecendo enriba que parte

502
00:23:23,250 --> 00:23:26,330
do rectángulo de todo este tempo é
Aínda hai máis memoria alí enriba.

503
00:23:26,330 --> 00:23:28,790
E cando dinamicamente
reservar a memoria,

504
00:23:28,790 --> 00:23:32,020
se é dentro GetString, que
temos está a facer para ti no CS50

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

506
00:23:34,710 --> 00:23:37,950
o sistema operativo para unha peza de
memoria, non vén do conxunto.

507
00:23:37,950 --> 00:23:40,960
Vén doutro lugar
na memoria do seu ordenador

508
00:23:40,960 --> 00:23:42,220
que se chama de datos dinámicos.

509
00:23:42,220 --> 00:23:43,430
E iso non é diferente.

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

511
00:23:44,285 --> 00:23:45,160
É a mesma memoria.

512
00:23:45,160 --> 00:23:49,080
É só a memoria RAM que está por riba
alí en vez de baixar aquí.

513
00:23:49,080 --> 00:23:50,750
>> E entón o que é que iso significa?

514
00:23:50,750 --> 00:23:53,650
Ben, se o ordenador ten
unha cantidade finita de memoria

515
00:23:53,650 --> 00:23:57,450
ea pila é evidente, entón
para falar, ea pila, segundo

516
00:23:57,450 --> 00:23:59,349
para esta frecha, é evidente para abaixo.

517
00:23:59,349 --> 00:24:01,140
Noutras palabras, cada
vez que chamar malloc,

518
00:24:01,140 --> 00:24:03,430
está a ser dada unha porción
de memoria dende arriba,

519
00:24:03,430 --> 00:24:06,630
a continuación, se cadra un pouco máis abaixo, entón un pouco
inferior, cada vez que chamar malloc,

520
00:24:06,630 --> 00:24:10,100
a pila, é o uso,
é unha especie de crecemento,

521
00:24:10,100 --> 00:24:11,950
crecendo cada vez máis preto para o que?

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

523
00:24:13,382 --> 00:24:14,840
Entón, iso parece ser unha boa idea?

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

525
00:24:18,420 --> 00:24:22,140
Quero dicir, onde non é moi claro
o que máis pode facer se só

526
00:24:22,140 --> 00:24:23,910
ten unha cantidade finita de memoria.

527
00:24:23,910 --> 00:24:25,200
Pero este é certamente mal.

528
00:24:25,200 --> 00:24:27,920
Esas dúas frechas están nun
Crash Course un polo outro.

529
00:24:27,920 --> 00:24:31,930
>> E parece que cara mal, persoas que
son particularmente bos coa programación,

530
00:24:31,930 --> 00:24:36,140
e tentando invadir ordenadores,
Pode explotar esa realidade.

531
00:24:36,140 --> 00:24:38,290
De feito, imos considerar
un pequeno fragmento.

532
00:24:38,290 --> 00:24:41,350
Polo tanto, este é un exemplo que pode ler
con máis detalle na Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Nós imos sinala-lo no
artigo curioso.

534
00:24:43,100 --> 00:24:45,650
Pero hai un ataque xeral
coñecido como buffer overflow que

535
00:24:45,650 --> 00:24:49,570
existiu durante o tempo que o ser humano
ter a capacidade de manipular

536
00:24:49,570 --> 00:24:53,120
a memoria do ordenador, especialmente en C.
Polo tanto, este é un programa moi arbitraria,

537
00:24:53,120 --> 00:24:55,130
pero imos lelo desde abaixo.

538
00:24:55,130 --> 00:24:57,650
Principal en ARGC carbón estrela argv.

539
00:24:57,650 --> 00:24:59,830
Polo tanto, é un programa que tira
argumentos de liña de comandos.

540
00:24:59,830 --> 00:25:03,620
E todo principal é que, ao parecer, é chamada
unha función, chamalo F pola simplicidade.

541
00:25:03,620 --> 00:25:04,610
E pasa que?

542
00:25:04,610 --> 00:25:05,490
Argv dun.

543
00:25:05,490 --> 00:25:09,320
Entón, el pasa a que quere que F
a palabra é que o usuario introduciu

544
00:25:09,320 --> 00:25:11,500
no poder tras a
nome do programa en todo.

545
00:25:11,500 --> 00:25:15,730
Tanto como César ou Vigenère, que
pode lembrar facendo argv.

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

547
00:25:16,680 --> 00:25:19,760
F leva nunha cadea
como o seu único argumento,

548
00:25:19,760 --> 00:25:22,100
AKA unha estrela char, mesmo
cousa, como unha cadea.

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

550
00:25:24,920 --> 00:25:27,710
E despois de char c 12,
só en termos leigos,

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

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

553
00:25:33,440 --> 00:25:36,490
A distribución de memoria, especialmente
12 bytes para 12 caracteres.

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

555
00:25:36,990 --> 00:25:40,000
E entón a última liña, mexa e
copia, probablemente non vin.

556
00:25:40,000 --> 00:25:43,360
Esta é unha copia cadea
función cuxo propósito na vida

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

558
00:25:48,160 --> 00:25:51,190
pero só ata un
número de bytes.

559
00:25:51,190 --> 00:25:53,860
Así, o terceiro argumento di,
cantos bytes ten que copiar?

560
00:25:53,860 --> 00:25:56,720
A lonxitude da barra,
todo o que o usuario escribiu.

561
00:25:56,720 --> 00:25:59,320
E os contidos de
Bar, esa secuencia, son

562
00:25:59,320 --> 00:26:02,330
copiada á memoria apuntada para a C.

563
00:26:02,330 --> 00:26:04,060
>> Entón, iso parece medio idiota, e é.

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

565
00:26:06,300 --> 00:26:10,100
dunha clase de vectores de ataque,
unha forma de atacar un programa.

566
00:26:10,100 --> 00:26:15,050
Todo está ben e bo se o usuario
tipo nunha palabra que é 11 caracteres

567
00:26:15,050 --> 00:26:18,040
ou menos, máis a barra invertida cero.

568
00:26:18,040 --> 00:26:22,830
E se o usuario escribe en máis de
11 ou 12 ou 20 ou 50 caracteres?

569
00:26:22,830 --> 00:26:25,090
¿Que é este programa vai facer?

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

571
00:26:29,360 --> 00:26:31,750
á súa lonxitude, que é
literalmente todo o bar,

572
00:26:31,750 --> 00:26:36,307
ao enderezo sinalado polo C. Pero C
só cautelarmente dada como 12 bytes.

573
00:26:36,307 --> 00:26:37,640
Pero non hai ningunha verificación adicional.

574
00:26:37,640 --> 00:26:38,700
Non hai ningún caso as condicións.

575
00:26:38,700 --> 00:26:40,580
Non hai ningunha verificación de erros aquí.

576
00:26:40,580 --> 00:26:43,270
>> E entón o que este programa é
vai facer é só cega

577
00:26:43,270 --> 00:26:45,750
copiar algo á outra.

578
00:26:45,750 --> 00:26:47,880
E así se deseñar ese
como unha imaxe, é aquí

579
00:26:47,880 --> 00:26:49,860
só unha pequena parte do espazo de memoria.

580
00:26:49,860 --> 00:26:53,470
Entón, observe no fondo, nós
teñen o bar variable local.

581
00:26:53,470 --> 00:26:57,330
Entón, ese punteiro que store--
xa que o argumento local que é

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

583
00:26:58,672 --> 00:27:00,380
A continuación, teña en conta só
enriba dela nunha pila,

584
00:27:00,380 --> 00:27:02,505
porque cada vez que preguntar
para memoria na pila,

585
00:27:02,505 --> 00:27:04,310
vai un pouco
anterior, pictorially,

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

587
00:27:06,270 --> 00:27:10,690
A de arriba esquerda é cero e soporte C
o certo é inferior C soporte 11.

588
00:27:10,690 --> 00:27:12,870
Isto é só a forma como os ordenadores
indo para poñelas fóra.

589
00:27:12,870 --> 00:27:18,300
Entón, só intuitivamente, se bar ten máis
de 12 caracteres en total, incluíndo

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

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

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

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

594
00:27:33,400 --> 00:27:36,300
>> Seguro, porque aínda
a propia pila crece cara arriba,

595
00:27:36,300 --> 00:27:39,590
unha vez que poñer as cousas en
el, por razóns de deseño,

596
00:27:39,590 --> 00:27:41,294
pon a memoria de arriba abaixo.

597
00:27:41,294 --> 00:27:44,460
Entón, se ten máis de 12 bytes,
vai comezar a substituír bar.

598
00:27:44,460 --> 00:27:47,280
Agora que é un erro, pero é
non é realmente un gran negocio.

599
00:27:47,280 --> 00:27:51,130
Pero é un gran negocio, porque hai
máis cousas a suceder na memoria.

600
00:27:51,130 --> 00:27:53,074
Entón aquí está como nós puidemos
poñer Ola, para ser claro.

601
00:27:53,074 --> 00:27:54,490
Se eu escriba Ola no poder.

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

603
00:27:59,330 --> 00:28:00,330
Todo está ben.

604
00:28:00,330 --> 00:28:03,020
Pero se eu escribir algo
máis longo, que é potencialmente

605
00:28:03,020 --> 00:28:05,860
vai rastexaren para o espazo bar.

606
00:28:05,860 --> 00:28:08,405
Pero peor aínda, parece se
fóra todo este tempo,

607
00:28:08,405 --> 00:28:11,530
aínda que nunca falamos sobre
que, a pila é usada para outras cousas.

608
00:28:11,530 --> 00:28:13,560
Non son só as variables locais.

609
00:28:13,560 --> 00:28:15,100
>> C é unha linguaxe de nivel moi baixo.

610
00:28:15,100 --> 00:28:17,810
E que tipo de segredo
utiliza tamén a pila

611
00:28:17,810 --> 00:28:21,260
para recordar cando un
función é chamada, o que

612
00:28:21,260 --> 00:28:26,040
é a dirección da función anterior,
así que pode ir de volta para esa función.

613
00:28:26,040 --> 00:28:29,980
Entón, cando as chamadas principais intercambiar entre
as cousas empurrado para a pila

614
00:28:29,980 --> 00:28:34,380
non só cambio variables locais,
ou os seus argumentos, tamén empurrou secretaría

615
00:28:34,380 --> 00:28:37,510
para a pila como representado
pola porción vermello aquí,

616
00:28:37,510 --> 00:28:40,520
é a dirección do principal fisicamente
na memoria do seu ordenador,

617
00:28:40,520 --> 00:28:44,180
de xeito que cando está feito de permuta, o ordenador
sabe que eu teño para volver ao inicio

618
00:28:44,180 --> 00:28:46,760
e rematar de realizar a función principal.

619
00:28:46,760 --> 00:28:51,960
Entón, iso é perigoso agora, porque se
o usuario escribe moito máis do que Ola,

620
00:28:51,960 --> 00:28:57,030
de tal xeito que a entrada do usuario clobbers
ou substitúe esa sección vermello,

621
00:28:57,030 --> 00:28:59,820
loxicamente, se o ordenador
só vai asumir cegamente

622
00:28:59,820 --> 00:29:03,830
en que os bytes que son porción vermello
a dirección para o que debe retornar,

623
00:29:03,830 --> 00:29:09,020
e se o adversario é intelixente dabondo ou
sorte o suficiente para poñer unha secuencia de bytes

624
00:29:09,020 --> 00:29:13,450
hai que se parece un enderezo,
pero é a dirección de código

625
00:29:13,450 --> 00:29:18,730
que el ou ela quere o ordenador
para realizar no canto de principal?

626
00:29:18,730 --> 00:29:21,670
>> Noutras palabras, se o que o
usuario está escribindo no prompt,

627
00:29:21,670 --> 00:29:23,850
non é só algo
como inocuo Ola,

628
00:29:23,850 --> 00:29:28,210
pero en realidade é un código que equivale
borrar todos os ficheiros dese usuario?

629
00:29:28,210 --> 00:29:30,060
Ou enviar correo-e o contrasinal para min?

630
00:29:30,060 --> 00:29:31,940
Ou comezar a rexistrar a súa
teclas escritas, non?

631
00:29:31,940 --> 00:29:34,920
Hai un camiño, imos estipular hoxe,
que poderían escribir non só Ola

632
00:29:34,920 --> 00:29:36,711
mundo ou o seu nome,
que podían esencialmente

633
00:29:36,711 --> 00:29:39,570
pasar en código, e ceros
aqueles que o ordenador

634
00:29:39,570 --> 00:29:43,450
erros de código e un enderezo.

635
00:29:43,450 --> 00:29:48,950
Así, aínda que un pouco abstracto, o
usuario escribe o código contraditorio suficiente

636
00:29:48,950 --> 00:29:52,330
que imos xeneralizar aquí como
A. Unha é o ataque ou adversarios.

637
00:29:52,330 --> 00:29:53,140
Entón, só cousas malas.

638
00:29:53,140 --> 00:29:55,306
Non nos importa sobre a
números ou os ceros ou aqueles

639
00:29:55,306 --> 00:29:59,470
hoxe, de tal forma que acaba
sobrescrevendo esa sección vermello,

640
00:29:59,470 --> 00:30:01,580
notar que secuencia de bytes.

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

642
00:30:05,020 --> 00:30:08,960
E agora, como artigo de Wikipedia aquí
propuxo, se realmente comezar agora

643
00:30:08,960 --> 00:30:12,460
rotular os bytes no seu ordenador de
memoria, o que o artigo é Wikipedia

644
00:30:12,460 --> 00:30:19,060
propoñendo é que o que se a dirección
de que byte superior esquerda é de 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Noutras palabras, se a cara é malo
intelixente dabondo co seu código

646
00:30:22,200 --> 00:30:26,650
para realmente poñer un número aquí que
corresponde ao enderezo do código

647
00:30:26,650 --> 00:30:29,180
el ou ela inxectado
no ordenador,

648
00:30:29,180 --> 00:30:31,050
pode enganar o ordenador
a facer calquera cousa.

649
00:30:31,050 --> 00:30:34,140
A eliminación de arquivos, correo electrónico
cousas, rastrexando o seu tráfico,

650
00:30:34,140 --> 00:30:36,710
literalmente nada podería ser
inxectado no ordenador.

651
00:30:36,710 --> 00:30:39,220
E así por un estourido de buffer
ataque no seu núcleo

652
00:30:39,220 --> 00:30:43,530
é só un estúpido, estúpido
imperiosa dunha matriz que

653
00:30:43,530 --> 00:30:45,840
non teñen os seus límites marcada.

654
00:30:45,840 --> 00:30:48,850
E iso é o que é super perigoso
e á vez poderoso super

655
00:30:48,850 --> 00:30:52,560
en C é que realmente teñen
acceso a calquera lugar da memoria.

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

657
00:30:55,320 --> 00:30:59,330
para comprobar a lonxitude danado de calquera
matrices que estamos manipulando.

658
00:30:59,330 --> 00:31:00,750
Entón, para ser claro, o que é a corrección?

659
00:31:00,750 --> 00:31:03,190
Se voltar a esta
código, non debería só

660
00:31:03,190 --> 00:31:08,000
cambiar a lonxitude da barra, o que
máis eu debería estar comprobando?

661
00:31:08,000 --> 00:31:10,620
O que máis debería estar facendo para
evitar este ataque enteiramente?

662
00:31:10,620 --> 00:31:14,110
Non quero dicir só cega
que ten que copiar como moitos bytes

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

664
00:31:16,140 --> 00:31:18,910
Quero dicir, como copiar
moitos bytes como están en bar

665
00:31:18,910 --> 00:31:24,090
ata o asignado
memoria, ou 12 como máximo.

666
00:31:24,090 --> 00:31:27,450
Entón eu teño algún tipo de condición if
que fai comprobar a lonxitude da barra,

667
00:31:27,450 --> 00:31:32,800
pero se é superior a 12, nos código só difícil
12 como a distancia máxima posible.

668
00:31:32,800 --> 00:31:35,910
Se non, o chamado tapón
ataque de estourido pode pasar.

669
00:31:35,910 --> 00:31:38,451
Na parte inferior das referidas láminas,
Se está curioso para saber máis

670
00:31:38,451 --> 00:31:41,200
é a páxina orixinal real
se quere dar un ollo.

671
00:31:41,200 --> 00:31:44,550
>> Pero agora, entre os prezos
pago aquí foi ineficiencia.

672
00:31:44,550 --> 00:31:46,680
Así, foi un rápido
ollar baixo nivel en que

673
00:31:46,680 --> 00:31:49,709
poden xurdir problemas agora que
teñen acceso a memoria do ordenador.

674
00:31:49,709 --> 00:31:51,750
Pero outro problema que
xa tropezou hoxe

675
00:31:51,750 --> 00:31:53,800
era só a ineficiencia
dunha lista ligada.

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

677
00:31:56,019 --> 00:31:57,560
Xa non temos unha matriz contigua.

678
00:31:57,560 --> 00:31:58,980
Non temos acceso aleatorio.

679
00:31:58,980 --> 00:32:00,710
Non podemos usar a notación de paréntese.

680
00:32:00,710 --> 00:32:04,590
Nós, literalmente, ten que usar un loop while
como a que escribín hai pouco.

681
00:32:04,590 --> 00:32:09,740
Pero o luns, que alegou que pudermos
rastexaren ao seu reino de eficiencia

682
00:32:09,740 --> 00:32:13,040
alcanzar algo que é
logarítmica quizais, ou mellor aínda,

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

684
00:32:16,120 --> 00:32:19,840
Entón, como podemos facelo cos seus novos
ferramentas, estes enderezos, estes punteiros,

685
00:32:19,840 --> 00:32:22,210
e enfiar cousas da nosa propia?

686
00:32:22,210 --> 00:32:23,960
Ben, supoñamos que
aquí, estes son unha banda

687
00:32:23,960 --> 00:32:27,170
de números que queremos almacenar nun
estrutura de datos de forma eficaz e de procura.

688
00:32:27,170 --> 00:32:30,960
Podemos absolutamente rebobinar a semana
dous, xoga-los nunha matriz,

689
00:32:30,960 --> 00:32:33,150
e procura-los usando investigación binaria.

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

691
00:32:34,040 --> 00:32:37,720
E, de feito escribiu
busca binaria en PSET3,

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

693
00:32:40,100 --> 00:32:40,890
Pero vostede sabe o que.

694
00:32:40,890 --> 00:32:45,060
Hai unha especie de máis
xeito intelixente de facelo.

695
00:32:45,060 --> 00:32:47,390
É un pouco máis
sofisticado e quizais

696
00:32:47,390 --> 00:32:50,830
permítenos ver por binario
busca é moito máis rápido.

697
00:32:50,830 --> 00:32:52,980
En primeiro lugar, imos introducir
a noción dunha árbore.

698
00:32:52,980 --> 00:32:54,730
Que, aínda que en
realidade tipo de árbores

699
00:32:54,730 --> 00:32:57,730
crecer como este, no mundo informático
ciencia que tipo de crecer para abaixo

700
00:32:57,730 --> 00:33:00,830
como unha árbore de familia, onde ten
seus avós ou bisavós

701
00:33:00,830 --> 00:33:04,580
ou outros adornos na parte superior, o patriarca e
a matriarca da familia, só un

702
00:33:04,580 --> 00:33:07,930
chamada raíz, no, a continuación
que son os seus nenos,

703
00:33:07,930 --> 00:33:11,442
debaixo da cal están os seus fillos, ou
seus descendentes en xeral.

704
00:33:11,442 --> 00:33:13,400
E calquera que colga fóra
a parte inferior da familia

705
00:33:13,400 --> 00:33:16,070
árbore, ademais de ser a
caçula da familia,

706
00:33:16,070 --> 00:33:19,520
Tamén pode ser só xenericamente
chamado as follas da árbore.

707
00:33:19,520 --> 00:33:21,800
>> Polo tanto, este é só unha banda
de palabras e definicións

708
00:33:21,800 --> 00:33:25,790
para algo chamado dunha árbore no ordenador
ciencia, así como unha árbore xenealóxica.

709
00:33:25,790 --> 00:33:28,770
Pero hai encarnações máis extravagantes
de árbores, unha das cales

710
00:33:28,770 --> 00:33:30,780
é chamada unha árbore de busca binaria.

711
00:33:30,780 --> 00:33:34,380
E pode tipo de provocación
ademais o que esa cousa fai.

712
00:33:34,380 --> 00:33:37,180
Ben, é binario en que sentido?

713
00:33:37,180 --> 00:33:41,455
Onde é que o binario vén aquí?

714
00:33:41,455 --> 00:33:41,955
Sentímolo?

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

716
00:33:45,961 --> 00:33:47,210
Non é tanto un ou.

717
00:33:47,210 --> 00:33:52,000
É máis que cada un de nós non ten
máis de dous fillos, como vemos aquí.

718
00:33:52,000 --> 00:33:54,990
En xeral, unha tree--
seus pais e avós

719
00:33:54,990 --> 00:33:57,640
pode ter tantos fillos ou
netos como realmente queren,

720
00:33:57,640 --> 00:34:00,820
e así, por exemplo, aí temos tres
nenos fóra dese nodo man dereita,

721
00:34:00,820 --> 00:34:05,480
mais dunha árbore binaria, un nó posúe
cero, un ou dous fillos maxima.

722
00:34:05,480 --> 00:34:08,496
E iso é unha propiedade agradable,
Porque si é tapado por dous,

723
00:34:08,496 --> 00:34:10,620
nós imos ser capaces de
estar un pouco rexistro base dous

724
00:34:10,620 --> 00:34:11,975
acción suceder aquí, en última instancia.

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

726
00:34:13,350 --> 00:34:14,558
Pero máis sobre iso nun momento.

727
00:34:14,558 --> 00:34:19,810
Busca árbore significa que as cifras son
disposto de tal xeito que o neno esquerda do

728
00:34:19,810 --> 00:34:22,429
valor é maior que a raíz.

729
00:34:22,429 --> 00:34:26,010
E o seu fillo dereito é
maior que a raíz.

730
00:34:26,010 --> 00:34:29,290
Noutras palabras, se incorporarse calquera dos
nós, os círculos nesta imaxe,

731
00:34:29,290 --> 00:34:31,840
e mira para a súa esquerda
neno eo seu fillo dereito,

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

733
00:34:34,739 --> 00:34:36,159
Entón verificación de sanidade 55.

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

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

736
00:34:38,620 --> 00:34:40,929
55, o seu fillo da dereita é de 77.

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

738
00:34:41,783 --> 00:34:43,199
E iso é unha definición recursiva.

739
00:34:43,199 --> 00:34:46,480
Poderiamos comprobar cada un destes
nós eo mesmo patrón ía realizar.

740
00:34:46,480 --> 00:34:49,389
>> Entón, o que é bo en un
árbore de busca binaria, é

741
00:34:49,389 --> 00:34:52,204
este, podemos implementar lo
cunha estrutura, como este.

742
00:34:52,204 --> 00:34:54,620
E aínda que estamos xogando
lotes de estruturas na súa,

743
00:34:54,620 --> 00:34:56,560
son un pouco
intuitiva agora esperanzas.

744
00:34:56,560 --> 00:35:00,570
A sintaxe é aínda misterioso, con certeza,
pero o contido dun nodo nesta

745
00:35:00,570 --> 00:35:02,786
context-- e seguimos
utilizando o no palabra,

746
00:35:02,786 --> 00:35:04,910
se é un rectángulo
na pantalla ou un círculo,

747
00:35:04,910 --> 00:35:08,970
é só algúns contedores xenérico,
Neste caso dunha árbore, como o

748
00:35:08,970 --> 00:35:11,780
vimos, necesitamos un número enteiro
en cada un dos nós

749
00:35:11,780 --> 00:35:15,460
e entón eu teño dous punteiros apuntando
para o fillo esquerdo e dereito do neno,

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

751
00:35:16,590 --> 00:35:20,730
Entón é así que nós puidemos
aplicar isto nun struct.

752
00:35:20,730 --> 00:35:22,315
E como eu podería implementar lo en código?

753
00:35:22,315 --> 00:35:26,730
Ben, imos dar unha rápida
mirar para este pequeno exemplo.

754
00:35:26,730 --> 00:35:29,820
Non é funcional, pero eu teño
copiado e pegado esa estrutura.

755
00:35:29,820 --> 00:35:33,510
E se a miña función para un par
árbore de busca é chamado de busca,

756
00:35:33,510 --> 00:35:36,980
e iso leva dous argumentos,
un N de número enteiro e un punteiro

757
00:35:36,980 --> 00:35:41,400
para un nó, de xeito que un punteiro para a árbore
ou un punteiro para a raíz dunha árbore,

758
00:35:41,400 --> 00:35:43,482
como fago para ir sobre como buscar N?

759
00:35:43,482 --> 00:35:45,440
Ben, en primeiro lugar, porque son
xestionar punteiros,

760
00:35:45,440 --> 00:35:46,750
Vou facer unha proba de sanidade.

761
00:35:46,750 --> 00:35:54,279
Iguais árbore é igual a cero, é N
nesta árbore ou non nesta árbore?

762
00:35:54,279 --> 00:35:55,070
Non pode ser, non?

763
00:35:55,070 --> 00:35:56,870
Se eu son pasado null,
non hai nada alí.

764
00:35:56,870 --> 00:35:59,230
Podería moi ben só
cegamente dicir return false.

765
00:35:59,230 --> 00:36:04,050
Se me der nada, eu certamente non podo
atopar calquera número N. Entón, o que máis podería

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

767
00:36:04,750 --> 00:36:12,830
Eu vou dicir ben else if N é
menos que o que está no nó de árbore

768
00:36:12,830 --> 00:36:16,300
que teño valor N entregou.

769
00:36:16,300 --> 00:36:20,270
Noutras palabras, se o número son
buscar, n, sexa menor que o nó

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

771
00:36:21,340 --> 00:36:23,190
E o no que estou a buscar
a árbore é chamado,

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

773
00:36:26,370 --> 00:36:28,310
Eu uso a notación de frecha.

774
00:36:28,310 --> 00:36:35,960
Polo tanto, se n é inferior a frecha árbore
N, quero ir conceptualmente esquerda.

775
00:36:35,960 --> 00:36:38,590
Como podo expresar searching esquerda?

776
00:36:38,590 --> 00:36:41,560
Para ser claro, se este é
a imaxe en cuestión,

777
00:36:41,560 --> 00:36:44,612
e eu teño que pasou de nivel superior
arrow que está a apuntar cara a abaixo.

778
00:36:44,612 --> 00:36:45,570
Ese é o meu punteiro árbore.

779
00:36:45,570 --> 00:36:48,060
Estou a apuntar cara a raíz da árbore.

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

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

782
00:36:55,300 --> 00:36:56,360
Polo que é menos que.

783
00:36:56,360 --> 00:36:58,760
E así este condición é aplicable.

784
00:36:58,760 --> 00:37:03,981
Así, conceptualmente, o que quero
buscar seguinte se eu estou buscando 44?

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

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

787
00:37:08,310 --> 00:37:11,100
>> Exactamente, quero
buscar o fillo esquerdo,

788
00:37:11,100 --> 00:37:12,789
ou a sub-árbore á esquerda da imaxe.

789
00:37:12,789 --> 00:37:14,830
E, de feito, deixe-me a través de
a foto aquí

790
00:37:14,830 --> 00:37:17,770
por só un momento, xa que
Non podo rabuñar iso.

791
00:37:17,770 --> 00:37:21,150
Se eu comezar en 55, e
Sei que o valor 44

792
00:37:21,150 --> 00:37:23,180
Estou buscando é a
á esquerda, é unha especie

793
00:37:23,180 --> 00:37:26,010
de como rasgar o libro de teléfono en
metade ou rasgar a árbore no medio.

794
00:37:26,010 --> 00:37:29,660
Eu xa non se preocupe
toda esta metade da árbore.

795
00:37:29,660 --> 00:37:33,270
E, con todo, curiosamente, en termos de
estrutura, esta cousa aquí que

796
00:37:33,270 --> 00:37:36,682
iníciase coa 33, que se
é unha árbore de busca binaria.

797
00:37:36,682 --> 00:37:39,890
Eu dixen a palabra recursiva antes porque
De feito, esta é unha estrutura de datos que

798
00:37:39,890 --> 00:37:41,707
por definición é recursiva.

799
00:37:41,707 --> 00:37:44,540
Pode que unha árbore que é iso
grande, pero cada un dos seus fillos

800
00:37:44,540 --> 00:37:46,870
representa unha árbore só un pouco menor.

801
00:37:46,870 --> 00:37:50,910
En vez de ser vovô
ou a avoa, agora é só nai

802
00:37:50,910 --> 00:37:54,300
ou-- Non podo non dizer-- nai
ou pai, que sería estraño.

803
00:37:54,300 --> 00:37:59,000
No canto das dúas nenos alí
sería como irmán e irmá.

804
00:37:59,000 --> 00:38:01,120
A nova xeración de árbore xenealóxica.

805
00:38:01,120 --> 00:38:02,900
Pero estruturalmente, é a mesma idea.

806
00:38:02,900 --> 00:38:06,790
E resulta que eu teño unha función
co cal podo buscar unha busca binaria

807
00:38:06,790 --> 00:38:07,290
árbore.

808
00:38:07,290 --> 00:38:08,680
El é chamado de busca.

809
00:38:08,680 --> 00:38:17,870
I buscar N na árbore frecha para a esquerda
outro se n é maior que o valor

810
00:38:17,870 --> 00:38:18,870
que eu son actualmente.

811
00:38:18,870 --> 00:38:20,800
55 na historia un momento atrás.

812
00:38:20,800 --> 00:38:23,780
Eu teño unha función chamada
investigación que podo só

813
00:38:23,780 --> 00:38:29,660
N pasar iso e buscar de forma recursiva
a sub-árbore e só retorno

814
00:38:29,660 --> 00:38:30,620
calquera que sexa a resposta.

815
00:38:30,620 --> 00:38:33,530
Outra cousa que eu teño algún caso base final aquí.

816
00:38:33,530 --> 00:38:35,310
>> ¿Que é o caso final?

817
00:38:35,310 --> 00:38:36,570
Árbore ou é nulo.

818
00:38:36,570 --> 00:38:39,980
O valor que tanto estou buscando é
menos que ou maior que aquela

819
00:38:39,980 --> 00:38:42,610
ou mesmo que o mesmo.

820
00:38:42,610 --> 00:38:44,750
E eu podería dicir igual
igual, pero loxicamente é

821
00:38:44,750 --> 00:38:46,500
equivalente a só dicindo outra cousa aquí.

822
00:38:46,500 --> 00:38:49,150
Tanto é así como eu atopar algo.

823
00:38:49,150 --> 00:38:51,710
Polo tanto, esperamos que esta é unha
mesmo exemplo máis atractivo

824
00:38:51,710 --> 00:38:54,900
que a función sigma estúpido
fixemos algunhas conferencias atrás,

825
00:38:54,900 --> 00:38:58,360
onde era tan fácil de usar un loop
para contar todos os números dun

826
00:38:58,360 --> 00:39:02,390
a N. aquí cunha estrutura de datos
que en si é recursivamente

827
00:39:02,390 --> 00:39:07,050
definido e de forma recursiva deseñada, agora nós
teñen a capacidade de nos expresarmos

828
00:39:07,050 --> 00:39:09,780
no código que en si é recursiva.

829
00:39:09,780 --> 00:39:12,580
Polo tanto, este é o mesmo código aquí.

830
00:39:12,580 --> 00:39:14,400
>> Entón, o que os outros problemas que podemos resolver?

831
00:39:14,400 --> 00:39:18,160
Entón, un paso rápido lonxe de
árbores para só un momento.

832
00:39:18,160 --> 00:39:20,130
Aquí é, digamos, a bandeira alemá.

833
00:39:20,130 --> 00:39:22,020
E hai claramente un
estándar para esta bandeira.

834
00:39:22,020 --> 00:39:23,811
E hai moita
bandeiras do mundo que

835
00:39:23,811 --> 00:39:27,560
son tan sinxelo coma iso en termos
das súas cores e patróns.

836
00:39:27,560 --> 00:39:31,930
Pero supoñamos que esta se garda como un
.gif, Ou un JPEG ou bitmap, ou un ping,

837
00:39:31,930 --> 00:39:34,240
calquera formato de arquivo gráfico
co que está familiarizado,

838
00:39:34,240 --> 00:39:36,460
algúns dos cales somos
xogar con en PSet4.

839
00:39:36,460 --> 00:39:41,550
Isto non parece valer a pena para almacenar
pixel negro, pixel negro, pixel negro,

840
00:39:41,550 --> 00:39:44,790
punto, punto, punto, unha morea de
píxeles negros para a primeira liña de varrido,

841
00:39:44,790 --> 00:39:47,430
ou liña, a continuación, un grupo enteiro de
a mesma, a continuación, un grupo enteiro

842
00:39:47,430 --> 00:39:49,530
do mesmo, e, a continuación, unha
todo grupo de píxeles vermellos,

843
00:39:49,530 --> 00:39:53,020
píxeles vermellos, píxeles vermellos, a continuación, un todo
puñado de píxeles amarelo, amarelo, non?

844
00:39:53,020 --> 00:39:55,050
>> Non hai tal ineficiencia aquí.

845
00:39:55,050 --> 00:39:59,040
Como é que intuitivamente
comprimir a bandeira alemá

846
00:39:59,040 --> 00:40:01,320
se implementar lo como un arquivo?

847
00:40:01,320 --> 00:40:04,940
Como o que información pode non
incomodar o almacenamento en disco en orde

848
00:40:04,940 --> 00:40:08,040
para diminuír o noso tamaño do arquivo de como
un megabyte dun kilobyte, algo

849
00:40:08,040 --> 00:40:09,430
menor?

850
00:40:09,430 --> 00:40:13,130
Onde reside a redundancia
aquí para ser claro?

851
00:40:13,130 --> 00:40:13,880
O que podería facer?

852
00:40:13,880 --> 00:40:14,380
Si?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Exactamente.

855
00:40:21,970 --> 00:40:24,550
Por que non, no canto de se lembrar
a cor de cada píxel danado

856
00:40:24,550 --> 00:40:28,200
así como está facendo en PSet4
co formato de arquivo de mapa de bits,

857
00:40:28,200 --> 00:40:32,060
por que non só representar a
columna máis á esquerda de píxeles, por exemplo

858
00:40:32,060 --> 00:40:35,370
unha morea de píxeles negros, un grupo
de vermello, e unha morea de amarelo,

859
00:40:35,370 --> 00:40:39,210
e despois é só algunha maneira codificar o
idea de repetir este 100 veces

860
00:40:39,210 --> 00:40:41,020
ou repetir isto 1.000 veces?

861
00:40:41,020 --> 00:40:43,430
Onde é 100 ou 1000
só un número enteiro, para que

862
00:40:43,430 --> 00:40:47,290
pode comezar afastado con só un único número
en vez de centos ou miles

863
00:40:47,290 --> 00:40:48,270
píxeles de adicionais.

864
00:40:48,270 --> 00:40:50,990
E, de feito, é así que
podería comprimir a bandeira alemá.

865
00:40:50,990 --> 00:40:51,490
E

866
00:40:51,490 --> 00:40:53,470
Agora o que pasa coa bandeira francesa?

867
00:40:53,470 --> 00:40:58,930
E un pouco de calquera tipo de
exercicio mental, que flag

868
00:40:58,930 --> 00:41:01,040
pode ser comprimida máis no disco?

869
00:41:01,040 --> 00:41:05,720
A bandeira alemán ou francés
bandeira, se temos esa visión?

870
00:41:05,720 --> 00:41:08,490
A bandeira alemán, porque non hai
máis redundancia horizontal.

871
00:41:08,490 --> 00:41:12,190
E polo deseño, moitos arquivos gráfico
formatos de feito traballar como liñas de varrido

872
00:41:12,190 --> 00:41:12,830
horizontalmente.

873
00:41:12,830 --> 00:41:14,674
Poderían traballar
vertical, basta humanidade

874
00:41:14,674 --> 00:41:17,090
anos decidiu que imos
Xeralmente pensamos en cousas fileira

875
00:41:17,090 --> 00:41:18,880
por liña en vez de columna por columna.

876
00:41:18,880 --> 00:41:20,820
Entón, en realidade, se fose
mirar para o ficheiro

877
00:41:20,820 --> 00:41:24,670
tamaño dunha bandeira alemá e unha francesa
bandeira, sempre que a resolución é

878
00:41:24,670 --> 00:41:27,530
o mesmo, o mesmo ancho
e altura, este

879
00:41:27,530 --> 00:41:31,580
aquí vai ser maior, porque
ten que repetir-se tres veces.

880
00:41:31,580 --> 00:41:35,570
Ten que especificar azul, repita
Se, branco, repita a, vermello,

881
00:41:35,570 --> 00:41:36,740
repetirse.

882
00:41:36,740 --> 00:41:39,000
Non pode simplemente ir todo
o camiño para a dereita.

883
00:41:39,000 --> 00:41:41,200
E como unha banda, para facer
desmarque a compresión

884
00:41:41,200 --> 00:41:43,910
está en todas partes, se estas son
catro cadros dunha video-- vostede

885
00:41:43,910 --> 00:41:45,890
que lembrar que unha película
ou de vídeo é xeralmente

886
00:41:45,890 --> 00:41:47,286
como 29 ou 30 cadros por segundo.

887
00:41:47,286 --> 00:41:50,410
É como un pouco flip book, onde
basta ver imaxe, imaxe, imaxe, imaxe,

888
00:41:50,410 --> 00:41:54,410
imaxe só super rápido así que mira como
os actores na pantalla están movendo.

889
00:41:54,410 --> 00:41:57,130
Aquí está unha abella do bumble en
encima dun ramo de flores.

890
00:41:57,130 --> 00:41:59,790
E aínda que poida ser unha especie de
difícil de ver a primeira vista,

891
00:41:59,790 --> 00:42:04,020
o único que se desprazan en
esta película é a abella.

892
00:42:04,020 --> 00:42:06,880
>> ¿Que é mudo sobre o almacenamento
vídeo sen comprimir?

893
00:42:06,880 --> 00:42:11,420
É unha especie de un desperdicio para almacenar vídeo
como catro imaxes que case idénticos

894
00:42:11,420 --> 00:42:13,670
difiren só na medida en que a abella é.

895
00:42:13,670 --> 00:42:16,280
Pode xogar fóra máis
de que a información

896
00:42:16,280 --> 00:42:20,190
e lembre-se só, por exemplo,
o primeiro cadro eo último cadro,

897
00:42:20,190 --> 00:42:22,180
cadros clave se
Xa escoitou a palabra,

898
00:42:22,180 --> 00:42:24,337
e só almacenar no
medio, onde a abella é.

899
00:42:24,337 --> 00:42:26,170
E non ten que
almacenar todo o rosa,

900
00:42:26,170 --> 00:42:28,330
eo azul, ea
valores verdes tamén.

901
00:42:28,330 --> 00:42:31,200
Polo tanto, esta é só a dicir que
compresión está en todas partes.

902
00:42:31,200 --> 00:42:34,900
É unha técnica miúdo usan
ou exame para concedida nestes días.

903
00:42:34,900 --> 00:42:38,750
>> Pero como comprimir texto?

904
00:42:38,750 --> 00:42:40,450
Como vai facer sobre a compresión de texto?

905
00:42:40,450 --> 00:42:45,410
Ben, cada un dos personaxes en
Ascii é un byte, ou oito bits.

906
00:42:45,410 --> 00:42:47,360
E iso é medio idiota, non?

907
00:42:47,360 --> 00:42:51,160
Porque probablemente tipo A
e E e I e O e U moi

908
00:42:51,160 --> 00:42:55,270
máis veces que como W ou Q ou Z,
dependendo do idioma en que

909
00:42:55,270 --> 00:42:56,610
está escribindo certamente.

910
00:42:56,610 --> 00:42:59,600
E entón por que estamos usando
oito bits para cada letra,

911
00:42:59,600 --> 00:43:02,040
incluíndo a menos
letras populares, non?

912
00:43:02,040 --> 00:43:05,300
Por que non usar menos bits para
as letras super popular,

913
00:43:05,300 --> 00:43:07,760
E como, as cousas que adiviñar
por primeira vez en Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
e utilizar máis bits para
as letras menos populares?

915
00:43:10,450 --> 00:43:10,950
Por que?

916
00:43:10,950 --> 00:43:13,130
Porque só estamos indo a
usalos con menos frecuencia.

917
00:43:13,130 --> 00:43:15,838
>> Ben, resulta que non teñen
intentos de facelo foi.

918
00:43:15,838 --> 00:43:18,630
E se se lembra de grao
escola ou colexio, código Morse.

919
00:43:18,630 --> 00:43:20,400
Código Morse ten puntos
e trazos que se pode

920
00:43:20,400 --> 00:43:24,270
transmitido ao longo dun fío conforme
sons ou signos de calquera tipo.

921
00:43:24,270 --> 00:43:25,930
Pero o código Morse é un super limpo.

922
00:43:25,930 --> 00:43:29,010
É unha especie de un sistema binario en
que ten puntos ou trazos.

923
00:43:29,010 --> 00:43:30,977
Pero se ver, por exemplo, dous puntos.

924
00:43:30,977 --> 00:43:33,810
Ou se pensas que ao seu operador
que vai como bip, bip, bip,

925
00:43:33,810 --> 00:43:36,760
Campá, acadando un pouco gatillo
que transmite un sinal,

926
00:43:36,760 --> 00:43:40,360
se, o destinatario recibe dous
puntos, que a mensaxe que recibiu?

927
00:43:40,360 --> 00:43:43,490
Completamente arbitraria.

928
00:43:43,490 --> 00:43:44,450
>> I?

929
00:43:44,450 --> 00:43:45,060
I?

930
00:43:45,060 --> 00:43:47,500
Ou o que about-- ou eu?

931
00:43:47,500 --> 00:43:49,570
Quizais fose só dous á dereita de E?

932
00:43:49,570 --> 00:43:52,480
Polo tanto, non hai ese problema
de Desencriptación con Morse

933
00:43:52,480 --> 00:43:54,890
código, por medio de que a non ser que o
persoa que enviou a mensaxe

934
00:43:54,890 --> 00:43:59,510
de feito, fai unha pausa para que poida clasificar de
ver ou escoitar as lagoas entre as letras,

935
00:43:59,510 --> 00:44:02,990
non é suficiente só para
enviar un fluxo de ceros e uns,

936
00:44:02,990 --> 00:44:05,610
ou puntos e trazos,
porque non hai ambigüidade.

937
00:44:05,610 --> 00:44:08,640
E é un único punto, polo que, se
ver dous puntos ou escoitar dous puntos,

938
00:44:08,640 --> 00:44:11,254
quizais sexa dous e de ou que sexa unha I.

939
00:44:11,254 --> 00:44:13,670
Entón, necesitamos un sistema que é un
pouco máis intelixente do que iso.

940
00:44:13,670 --> 00:44:16,851
Entón un home chamado Huffman anos
atrás veu con exactamente isto.

941
00:44:16,851 --> 00:44:18,600
Entón, nós só estamos indo
para tomar un rápido ollar

942
00:44:18,600 --> 00:44:20,114
o xeito no que as árbores son pertinentes a esta.

943
00:44:20,114 --> 00:44:22,530
Supoña que esta é unha
estúpido mensaxe que desexe enviar,

944
00:44:22,530 --> 00:44:26,342
composto por só A, B, C de D's e E do,
pero hai unha morea de redundancia aquí.

945
00:44:26,342 --> 00:44:27,550
Isto non debería ser inglés.

946
00:44:27,550 --> 00:44:28,341
Non e criptografía.

947
00:44:28,341 --> 00:44:30,540
É só unha mensaxe estúpida
con moita repetición.

948
00:44:30,540 --> 00:44:34,010
Entón, se realmente contar para fóra toda a
A, B de, C de, D's, e E de aquí está

949
00:44:34,010 --> 00:44:34,890
a frecuencia.

950
00:44:34,890 --> 00:44:37,800
20% do que as letras son
Un, 45% das cartas

951
00:44:37,800 --> 00:44:39,660
E son de, e outros tres frecuencias.

952
00:44:39,660 --> 00:44:41,960
Contamos alí enriba manualmente
e só fixo as contas.

953
00:44:41,960 --> 00:44:44,579
>> Así, verifícase que
Huffman, hai algún tempo,

954
00:44:44,579 --> 00:44:46,620
entender que, vostede sabe
o que, se eu comezar a construír

955
00:44:46,620 --> 00:44:51,172
unha árbore ou bosque de árbores, se quixeren,
do seguinte xeito, eu podo facer o seguinte.

956
00:44:51,172 --> 00:44:53,880
Vou dar un nó para cada
das cartas que me interesa

957
00:44:53,880 --> 00:44:55,530
e eu estou indo para almacenar
dentro dese nodo

958
00:44:55,530 --> 00:44:58,610
as frecuencias como un punto flotante
valor, ou pode usalo unha N, tamén,

959
00:44:58,610 --> 00:45:00,210
pero imos só usar un flotador aquí.

960
00:45:00,210 --> 00:45:03,100
E que o algoritmo
el propuxo é que

961
00:45:03,100 --> 00:45:07,210
aproveitar esta bosque de nó único
árbores, árbores tan super curtas,

962
00:45:07,210 --> 00:45:11,920
e comezar a conectar-los con
novos grupos, pais novos, se quere.

963
00:45:11,920 --> 00:45:16,150
E facelo escollendo o
dous menores frecuencias á vez.

964
00:45:16,150 --> 00:45:18,110
Entón, eu levei o 10% e 10%.

965
00:45:18,110 --> 00:45:19,090
Eu crear un novo nodo.

966
00:45:19,090 --> 00:45:20,910
E eu chamo o novo nó de 20%.

967
00:45:20,910 --> 00:45:22,750
>> Que dous nós Eu combino o próximo?

968
00:45:22,750 --> 00:45:23,810
É un pouco ambigua.

969
00:45:23,810 --> 00:45:26,643
Polo tanto, hai algúns casos canto para
considerar, pero para manter as cousas ben,

970
00:45:26,643 --> 00:45:29,300
Vou escoller 20% -
Eu agora ignorar os nenos.

971
00:45:29,300 --> 00:45:33,640
Vou escoller un 20% e
15% e deseñar dúas novas arestas.

972
00:45:33,640 --> 00:45:35,624
E agora que dous nós
eu loxicamente combinar?

973
00:45:35,624 --> 00:45:38,540
Ignorar todos os nenos, as
netos, basta ollar para as raíces

974
00:45:38,540 --> 00:45:39,070
agora.

975
00:45:39,070 --> 00:45:42,220
Que dous nós podo amarre xuntos?

976
00:45:42,220 --> 00:45:44,530
Punto dous e 0,35.

977
00:45:44,530 --> 00:45:45,890
Entón deixe-me deseñar dúas novas arestas.

978
00:45:45,890 --> 00:45:47,570
E entón eu teño só un á esquerda.

979
00:45:47,570 --> 00:45:48,650
Entón aquí está unha árbore.

980
00:45:48,650 --> 00:45:51,160
E deseñada deliberadamente
ollar tipo de bonito,

981
00:45:51,160 --> 00:45:55,870
de ter en conta que as arestas teñen
Tamén foi marcado cero e un.

982
00:45:55,870 --> 00:45:59,510
Así, todas as beiras esquerdas son cero
arbitrariamente, senón de forma consistente.

983
00:45:59,510 --> 00:46:01,170
Todas as beiras dereitas son queridos.

984
00:46:01,170 --> 00:46:05,070
>> E entón o que Hoffman proposta é,
se quere representar un B,

985
00:46:05,070 --> 00:46:10,080
en vez de representar o número 66 como
un ASCII que é oito bits enteiros,

986
00:46:10,080 --> 00:46:13,360
Vostede sabe o que, exactamente tenda
o estándar cero, cero, cero,

987
00:46:13,360 --> 00:46:17,030
cero, porque ese é o camiño
da miña árbore, árbore do Sr Huffman,

988
00:46:17,030 --> 00:46:18,600
para a folla a partir da raíz.

989
00:46:18,600 --> 00:46:20,970
Se desexa almacenar unha
E, por outra banda, non facer

990
00:46:20,970 --> 00:46:26,290
enviar oito bits que representan un E.
Pola contra, enviar o estándar de bits?

991
00:46:26,290 --> 00:46:26,890
Unha.

992
00:46:26,890 --> 00:46:30,410
E o que é agradable sobre esta é
que e é a letra máis popular,

993
00:46:30,410 --> 00:46:32,340
e está a executar o
código máis curto para el.

994
00:46:32,340 --> 00:46:34,090
O seguinte máis popular
carta parece que

995
00:46:34,090 --> 00:46:37,380
era A. E así cantos bits
el propoñer usando para iso?

996
00:46:37,380 --> 00:46:38,270
Cero, un.

997
00:46:38,270 --> 00:46:41,060
>> E porque é aplicado
como esta árbore, polo de agora

998
00:46:41,060 --> 00:46:43,350
déixeme estipular hai
calquera ambigüidade en Morse

999
00:46:43,350 --> 00:46:46,090
código, porque todo o
letras que se preocupan

1000
00:46:46,090 --> 00:46:48,780
son a finais destes cantos.

1001
00:46:48,780 --> 00:46:50,580
Entón, iso é só un
aplicación dunha árbore.

1002
00:46:50,580 --> 00:46:52,538
Isto é-- e eu vou acenar
miña man neste como

1003
00:46:52,538 --> 00:46:55,570
pode aplicar isto como unha estrutura C.

1004
00:46:55,570 --> 00:46:58,260
Nós só necesitamos combinar
un símbolo, como un char,

1005
00:46:58,260 --> 00:46:59,910
ea miúdo en esquerda e dereita.

1006
00:46:59,910 --> 00:47:02,510
Pero imos ollar para dous
exemplos finais que vai

1007
00:47:02,510 --> 00:47:06,070
bastante familiarizado con logo
cuestionario cero no conxunto de problemas cinco.

1008
00:47:06,070 --> 00:47:09,210
>> Polo tanto, hai a estrutura de datos
coñecida como unha táboa de hash.

1009
00:47:09,210 --> 00:47:12,247
E unha táboa hash é unha especie de
arrefecer na medida en que ten baldes.

1010
00:47:12,247 --> 00:47:14,830
E supoña que hai catro baldes
aquí, só catro espazos en branco.

1011
00:47:14,830 --> 00:47:20,830
Aquí está un baralla de cartas, e aquí está
club, pa, club, diamantes, club,

1012
00:47:20,830 --> 00:47:25,960
diamantes, clubs, diamantes,
clubs-- entón que é o azar.

1013
00:47:25,960 --> 00:47:30,330
Corazóns, entón estou hearts--
bucketizing todas as entradas aquí.

1014
00:47:30,330 --> 00:47:32,430
E unha táboa de hash necesidades
a ollar para a súa entrada,

1015
00:47:32,430 --> 00:47:34,850
e, a continuación, colocar-lo en un
poñer a base do que ve.

1016
00:47:34,850 --> 00:47:35,600
É un algoritmo.

1017
00:47:35,600 --> 00:47:37,980
E eu estaba a usar un super-
algoritmo visual simple.

1018
00:47:37,980 --> 00:47:40,030
A parte máis difícil do que foi
lembrando-se de que as imaxes foron.

1019
00:47:40,030 --> 00:47:41,590
E despois hai catro cousas totais.

1020
00:47:41,590 --> 00:47:45,440
>> Agora, as pilas estaban crecendo, o que
é unha cousa deliberada proxecto aquí.

1021
00:47:45,440 --> 00:47:46,540
Pero o que máis podería facer?

1022
00:47:46,540 --> 00:47:49,080
Entón, en realidade, temos aquí un
banda de vellos libros de exame escolar.

1023
00:47:49,080 --> 00:47:51,240
Supoña que un grupo de
nomes alumnos están aquí.

1024
00:47:51,240 --> 00:47:52,570
Aquí está unha táboa hash maior.

1025
00:47:52,570 --> 00:47:54,867
No canto de catro baldes,
Teño, digamos 26.

1026
00:47:54,867 --> 00:47:57,950
E nós non queremos ir pedir prestado 26
cousas de fóra [? Annenberg?] Así

1027
00:47:57,950 --> 00:48:00,289
aquí está cinco que representan
A a Z. E se eu

1028
00:48:00,289 --> 00:48:03,580
ver un alumno cuxo nome comeza con A,
Vou poñer o seu cuestionario alí.

1029
00:48:03,580 --> 00:48:08,850
Se alguén comeza con C, ata alí,
A--, en realidade, non quería facelo.

1030
00:48:08,850 --> 00:48:10,060
B pasa por aquí.

1031
00:48:10,060 --> 00:48:13,390
Entón eu teño A e B e C. E
Agora, aquí está outro estudante A.

1032
00:48:13,390 --> 00:48:16,212
Pero, se esta táboa hash é
aplicado con unha matriz,

1033
00:48:16,212 --> 00:48:17,920
Eu son do tipo aparafusado
Actualmente, non?

1034
00:48:17,920 --> 00:48:19,510
Eu medio que cómpre poñer isto en algún lugar.

1035
00:48:19,510 --> 00:48:24,380
>> Así, un xeito que podo resolver isto é, todo
dereito, A é ocupado, B está ocupado, C está ocupado.

1036
00:48:24,380 --> 00:48:28,880
Vou poñelas D. Entón,
en primeiro lugar, eu teño acceso instantáneo chou

1037
00:48:28,880 --> 00:48:31,064
para cada un dos baldes para os alumnos.

1038
00:48:31,064 --> 00:48:33,230
Pero agora é unha especie de delegada
en algo lineal,

1039
00:48:33,230 --> 00:48:36,750
porque se eu queira buscar alguén
cuxo nome comeza con A, eu verifico aquí.

1040
00:48:36,750 --> 00:48:38,854
Pero, se esta non é a dun
estudante que eu estou a buscar,

1041
00:48:38,854 --> 00:48:41,520
Eu medio que teño que comezar a comprobar
os baldes, xa que o que eu fixen

1042
00:48:41,520 --> 00:48:44,530
era unha especie de linearmente
sondar a estrutura de datos.

1043
00:48:44,530 --> 00:48:47,710
Un xeito estúpido dicir basta ollar
para a primeira apertura dispoñible,

1044
00:48:47,710 --> 00:48:51,850
e poñer no seu plan B, por así dicir,
ou plan D neste caso, o valor

1045
00:48:51,850 --> 00:48:53,340
nese lugar.

1046
00:48:53,340 --> 00:48:56,470
Este é só para que se ten
ten 26 locais e ningún alumno

1047
00:48:56,470 --> 00:49:00,600
co nome Q ou Z, ou algo así
que, polo menos está a usar o espazo.

1048
00:49:00,600 --> 00:49:03,140
>> Pero xa vimos máis
solucións intelixentes aquí, non?

1049
00:49:03,140 --> 00:49:04,870
O que faría no canto
se ten unha colisión?

1050
00:49:04,870 --> 00:49:06,670
Se dúas persoas teñen
o nome A, o que sería

1051
00:49:06,670 --> 00:49:09,160
ser un máis intelixente ou
solución intuitiva que

1052
00:49:09,160 --> 00:49:12,840
poñendo un D, ​​onde se quere que sexa?

1053
00:49:12,840 --> 00:49:14,810
Por que non podo simplemente ir
[fóra? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
como malloc, outro no, coloque-
aquí, e logo poñer que un estudante aquí.

1055
00:49:19,960 --> 00:49:22,120
Así que eu tivera esencialmente
algún tipo de unha matriz,

1056
00:49:22,120 --> 00:49:25,590
ou quizais máis elegante como estamos
empezando a ver unha lista ligada.

1057
00:49:25,590 --> 00:49:29,520
>> E así unha táboa hash é unha estrutura
que podería ollar só como este,

1058
00:49:29,520 --> 00:49:33,900
pero máis intelixente, algo chamado
fío separado, en que unha táboa hash

1059
00:49:33,900 --> 00:49:38,340
moi simplemente é unha matriz, cada un dos
cuxos elementos non é un número,

1060
00:49:38,340 --> 00:49:40,470
é en si unha lista ligada.

1061
00:49:40,470 --> 00:49:45,080
Para que teña acceso super rápido
decidir onde botar o seu valor para.

1062
00:49:45,080 --> 00:49:48,059
Moi parecido ao exemplo tarxetas,
Eu fixen decisións super rápido.

1063
00:49:48,059 --> 00:49:49,600
Corazóns vai aquí, diamantes vai aquí.

1064
00:49:49,600 --> 00:49:52,180
Mesmo aquí, A vai aquí,
D vai aquí, B vai aquí.

1065
00:49:52,180 --> 00:49:55,740
Entón super rápido look emerxentes, e se
pasar de correr nun caso

1066
00:49:55,740 --> 00:49:59,429
colisións, onde ten dous,
persoas co mesmo nome, así, entón

1067
00:49:59,429 --> 00:50:00,970
acaba de comezar ligando-os xuntos.

1068
00:50:00,970 --> 00:50:03,900
E quizais mantelos clasificadas
por orde alfabética, quizais non.

1069
00:50:03,900 --> 00:50:05,900
Pero polo menos agora temos o dinamismo.

1070
00:50:05,900 --> 00:50:10,250
Así, por unha banda, temos super rápido
constante de tempo e tipo de tempo lineal

1071
00:50:10,250 --> 00:50:14,110
implicados se esas listas ligadas
comezan a estar un pouco longo.

1072
00:50:14,110 --> 00:50:16,880
>> Polo tanto, este tipo de un parvo,
gracejo geeky anos.

1073
00:50:16,880 --> 00:50:19,590
No CS50 Hack a Thon,
cando os alumnos facturación,

1074
00:50:19,590 --> 00:50:22,040
algúns TF ou CA cada ano
Pensas que é divertido para poñer-se

1075
00:50:22,040 --> 00:50:27,772
un sinal como este, onde só
significa que o seu nome comeza cun A,

1076
00:50:27,772 --> 00:50:28,870
ir por este camiño.

1077
00:50:28,870 --> 00:50:31,110
Se o seu nome comeza
cun B, ir isto-- OK,

1078
00:50:31,110 --> 00:50:33,290
é divertido quizais máis tarde no semestre.

1079
00:50:33,290 --> 00:50:36,420
Pero hai outra
forma de facelo tamén.

1080
00:50:36,420 --> 00:50:37,410
Imos volver a iso.

1081
00:50:37,410 --> 00:50:38,600
>> Polo tanto, hai esa estrutura.

1082
00:50:38,600 --> 00:50:40,420
E esta é a nosa última
estrutura para hoxe,

1083
00:50:40,420 --> 00:50:42,400
que é algo chamado trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, que, por algunha razón é curto
para recuperación, pero é chamado trie.

1085
00:50:47,140 --> 00:50:51,389
Así, outro interesante é trie
amálgama de moitas desas ideas.

1086
00:50:51,389 --> 00:50:52,930
É unha árbore, o que vimos antes.

1087
00:50:52,930 --> 00:50:54,180
Non é unha árbore de busca binaria.

1088
00:50:54,180 --> 00:50:58,410
É unha árbore con calquera número de fillos,
pero cada un dos nenos nun trie

1089
00:50:58,410 --> 00:51:00,090
é unha matriz.

1090
00:51:00,090 --> 00:51:04,790
Unha matriz de tamaño, din, 26 ou que 27
se quere apoiar hifenizado nomes

1091
00:51:04,790 --> 00:51:06,790
ou apóstrofos en nomes de persoas.

1092
00:51:06,790 --> 00:51:08,280
>> E polo que esta é unha estrutura de datos.

1093
00:51:08,280 --> 00:51:10,290
E se ollar arriba
abaixo, como se

1094
00:51:10,290 --> 00:51:13,710
mirar para o no superior alí, M, é
apuntando para o máis á esquerda alí,

1095
00:51:13,710 --> 00:51:17,665
que é, a continuación, A, X, W, E, L, L. Isto é
só unha estrutura de datos que arbitrariamente

1096
00:51:17,665 --> 00:51:19,120
é o almacenamento de nomes de persoas.

1097
00:51:19,120 --> 00:51:25,720
E Maxwell é almacenado por só seguindo
un camiño de matriz para matriz para matriz.

1098
00:51:25,720 --> 00:51:30,050
Pero o que é sorprendente sobre un trie é
que, mentres que a lista ligada e mesmo

1099
00:51:30,050 --> 00:51:34,520
unha matriz, o mellor que eu xa cheguei é
tempo lineal ou logarítmica tempo buscando

1100
00:51:34,520 --> 00:51:35,600
alguén.

1101
00:51:35,600 --> 00:51:40,530
Nesta estrutura de datos dun trie, se
miña estrutura de datos ten un nome nel

1102
00:51:40,530 --> 00:51:43,720
e eu estou buscando Maxwell, eu son
Vai atopalo moi rapidamente.

1103
00:51:43,720 --> 00:51:47,910
Acaba de ollar para M-A-X-W-E-L-L. Se
esta estrutura de datos, en contraste,

1104
00:51:47,910 --> 00:51:51,830
Se N é un millón, se hai unha
millón de nomes nesta estrutura de datos,

1105
00:51:51,830 --> 00:51:57,100
Maxwell aínda vai ser
detectábel tras só M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
pasos.

1107
00:51:58,090 --> 00:52:01,276
E pasos David-- D-A-V-I-D.

1108
00:52:01,276 --> 00:52:03,400
Noutras palabras, a través da construción de
unha estrutura de datos que é

1109
00:52:03,400 --> 00:52:07,240
ten todas esas matrices, as cales
sosterse de acceso aleatorio,

1110
00:52:07,240 --> 00:52:11,090
Podo comezar a ollar para arriba de persoas
nome usando unha cantidade de tempo que é

1111
00:52:11,090 --> 00:52:14,340
proporcional á non o número
de cousas na estrutura de datos,

1112
00:52:14,340 --> 00:52:16,330
como un millón de nomes existentes.

1113
00:52:16,330 --> 00:52:20,135
A cantidade de tempo que leva-me a atopar
H-A-X-W-E-G-G na estrutura de datos é este

1114
00:52:20,135 --> 00:52:22,260
non proporcional ao
o tamaño da estrutura de datos,

1115
00:52:22,260 --> 00:52:25,930
pero coa lonxitude do nome.

1116
00:52:25,930 --> 00:52:28,440
E realista a
nomes que nós estamos mirando para arriba

1117
00:52:28,440 --> 00:52:29,970
non vai ser tolo por moito tempo.

1118
00:52:29,970 --> 00:52:32,600
Quizais alguén ten un carácter 10
nomear, 20 nome do personaxe.

1119
00:52:32,600 --> 00:52:33,900
É certamente finito, non?

1120
00:52:33,900 --> 00:52:37,110
Non é un ser humano en que a Terra
ten o nome máis longo posible,

1121
00:52:37,110 --> 00:52:39,920
pero ese nome é unha constante
lonxitude valor, non?

1122
00:52:39,920 --> 00:52:41,980
Non varía en calquera sentido.

1123
00:52:41,980 --> 00:52:45,090
Así, deste xeito, temos
conseguida unha estrutura de datos

1124
00:52:45,090 --> 00:52:47,800
que é tempo constante look-up.

1125
00:52:47,800 --> 00:52:50,670
Fai ter un número de pasos
dependendo da lonxitude da entrada,

1126
00:52:50,670 --> 00:52:54,250
pero non o número de nome
na estrutura de datos.

1127
00:52:54,250 --> 00:52:58,700
Entón, se nós dobrar o número de nomes
o ano que de mil millóns a dous millóns,

1128
00:52:58,700 --> 00:53:03,720
constatación Maxwell levará
o mesmo número de sete pasos

1129
00:53:03,720 --> 00:53:04,650
para atopalo.

1130
00:53:04,650 --> 00:53:08,810
E, así, parece ter conseguido
noso Santo Graal do tempo de execución.

1131
00:53:08,810 --> 00:53:10,860
>> Así, un par de anuncios rápidos.

1132
00:53:10,860 --> 00:53:11,850
Cuestionario de cero está chegando.

1133
00:53:11,850 --> 00:53:14,600
Máis sobre o tema na páxina web do curso
durante o próximo par de días.

1134
00:53:14,600 --> 00:53:17,120
Luns de lecture-- É unha festa
aquí en Harvard o luns.

1135
00:53:17,120 --> 00:53:18,850
Non é en New Haven,
así que estamos tomando a clase

1136
00:53:18,850 --> 00:53:20,310
a New Haven para charla o luns.

1137
00:53:20,310 --> 00:53:22,550
Todo será filmado
e transmitido en directo, como de costume,

1138
00:53:22,550 --> 00:53:24,900
pero imos rematar hoxe
cun segundo clip 30

1139
00:53:24,900 --> 00:53:26,910
chamados "Pensamentos Profundos"
Daven por Farnham, que

1140
00:53:26,910 --> 00:53:30,850
foi inspirado o ano pasado ata sábado
"Pensamentos Profundos" de Night Live

1141
00:53:30,850 --> 00:53:35,700
por Jack Handy, que
agora debe ter sentido.

1142
00:53:35,700 --> 00:53:38,810
>> PELÍCULA: E agora, "Deep
Pensamentos "por Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Táboa de hash.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> COLUMNA 1: Todo ben, iso é todo por agora.

1147
00:53:47,660 --> 00:53:48,805
Imos velo a próxima semana.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> Doug: Para velo en acción.

1150
00:53:56,680 --> 00:53:58,304
Entón, imos dar un ollo niso agora.

1151
00:53:58,304 --> 00:53:59,890
Entón, aquí temos un conxunto indiferenciado.

1152
00:53:59,890 --> 00:54:04,860
>> Ian: Doug, pode ir adiante e reinicio
iso por só un segundo, por favor.

1153
00:54:04,860 --> 00:54:08,562
Todo ben, as cámaras están rolando, entón
acción sempre que estea listo, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
Doug: Todo ben, entón o que
temos aquí é un conxunto indiferenciado.

1155
00:54:11,020 --> 00:54:13,960
E eu teño colorido todos os elementos
vermello para indicar que é, en realidade,

1156
00:54:13,960 --> 00:54:14,460
indiferenciados.

1157
00:54:14,460 --> 00:54:17,960
Entón recordar que o primeiro que facemos
é que clasificar a metade esquerda da matriz.

1158
00:54:17,960 --> 00:54:20,630
Logo clasificar a dereita
metade da matriz.

1159
00:54:20,630 --> 00:54:22,830
E ya-da, ya-da, ya-da,
que fundín-las.

1160
00:54:22,830 --> 00:54:24,520
E nós temos unha matriz completamente ordenada.

1161
00:54:24,520 --> 00:54:25,360
Entón é así que funciona merge sort.

1162
00:54:25,360 --> 00:54:27,109
>> Ian: Ei, ei, ei,
corta, corta, corta, corta.

1163
00:54:27,109 --> 00:54:30,130
Doug, non pode só ya-da, ya-da,
ya-da, o seu camiño a través merge sort.

1164
00:54:30,130 --> 00:54:31,970
>> Doug: Eu só fixen.

1165
00:54:31,970 --> 00:54:32,832
É moi ben.

1166
00:54:32,832 --> 00:54:33,540
Somos bos de ir.

1167
00:54:33,540 --> 00:54:34,760
Nós só seguir xogando.

1168
00:54:34,760 --> 00:54:35,380
Entón, de calquera xeito,

1169
00:54:35,380 --> 00:54:37,800
>> Ian: Ten que explicar
El máis plenamente do que iso.

1170
00:54:37,800 --> 00:54:39,999
Isto non é só o suficiente.

1171
00:54:39,999 --> 00:54:41,790
Doug: Ian, non
necesitamos volver a un.

1172
00:54:41,790 --> 00:54:42,350
É moi ben.

1173
00:54:42,350 --> 00:54:45,690
En calquera caso, se seguimos con merge--
Ian, estamos no medio da rodaxe.

1174
00:54:45,690 --> 00:54:46,612
>> Ian: Eu sei.

1175
00:54:46,612 --> 00:54:49,320
E nós non podemos só ya-da, ya-da,
ya-da, a través de todo o proceso.

1176
00:54:49,320 --> 00:54:52,200
Ten que explicar como o
dous lados se fundiron xuntos.

1177
00:54:52,200 --> 00:54:53,570
>> Doug: Pero nós xa
explicou como os dous sides--

1178
00:54:53,570 --> 00:54:55,321
>> Ian: Acaba mostra
-lhes unha variedade de mesclagem.

1179
00:54:55,321 --> 00:54:56,486
Doug: Saben o proceso.

1180
00:54:56,486 --> 00:54:57,172
Están ben.

1181
00:54:57,172 --> 00:54:58,380
Temos ido sobre el dez veces.

1182
00:54:58,380 --> 00:55:00,330
>> Ian: Acaba de saltar dereito sobre el.

1183
00:55:00,330 --> 00:55:03,360
Imos voltar a un,
non pode ya-da, ya-da sobre el.

1184
00:55:03,360 --> 00:55:05,480
Todo ben, de volta a un.

1185
00:55:05,480 --> 00:55:07,833
>> Doug: Teño que volver
a través de todos os diapositivas?

1186
00:55:07,833 --> 00:55:08,332
Meu Deus.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
É como o sexto tempo, Ian.

1189
00:55:13,004 --> 00:55:13,940
É moi ben.

1190
00:55:13,940 --> 00:55:15,200
>> Ian: Todo ben.

1191
00:55:15,200 --> 00:55:16,590
Está preparado?

1192
00:55:16,590 --> 00:55:17,400
Gran.

1193
00:55:17,400 --> 00:55:18,950
Acción.