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

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

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

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

5
00:00:12,970 --> 00:00:17,970
Entón CS50x, un dos primeiros cursos de Harvard implicados na iniciativa EDX

6
00:00:17,970 --> 00:00:20,590
de feito estreou este luns pasado.

7
00:00:20,590 --> 00:00:23,460
Se desexa obter un vislumbre do que os outros en Internet

8
00:00:23,460 --> 00:00:27,180
agora están acompañando con, pode ir x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Que ha redireccionándoos lo para o lugar apropiado no edx.org,

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

11
00:00:34,160 --> 00:00:38,140
Vai ter que rexistrarte para unha conta, vai descubrir que o material é basicamente o mesmo

12
00:00:38,140 --> 00:00:42,170
como tivo neste semestre, aínda que algunhas semanas atrasadas, como temos todo listo.

13
00:00:42,170 --> 00:00:46,930
Pero o que os alumnos en CS50x vai ver agora unha interface bastante coma este.

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

15
00:00:50,040 --> 00:00:54,230
Ao facer o login para edx.org, un estudante CS50x ve os tipos de cousas

16
00:00:54,230 --> 00:00:57,170
que sería de esperar a ver nun curso: a palestra para o luns,

17
00:00:57,170 --> 00:01:01,650
charla para o mércores, shorts diversos, os conxuntos de problemas, as orientacións, PDFs.

18
00:01:01,650 --> 00:01:04,459
Ademais, como se ve aquí, traducións automáticas

19
00:01:04,459 --> 00:01:08,390
transcricións de inglés para chinés, xaponés, español, italiano,

20
00:01:08,390 --> 00:01:12,810
e unha banda enteiro de outras linguas que seguramente vai ser imperfecto

21
00:01:12,810 --> 00:01:15,840
coma nós rolamos-los programaticamente usando unha cousa chamada API,

22
00:01:15,840 --> 00:01:18,360
ou interface de programación de aplicación, Google

23
00:01:18,360 --> 00:01:21,360
que nos permite converter Inglés para esas outras linguas.

24
00:01:21,360 --> 00:01:24,100
Pero, grazas ao marabilloso espírito de algúns voluntarios máis de cen,

25
00:01:24,100 --> 00:01:26,940
persoas aleatorias en Internet que xentilmente ofrecidos a se involucrar

26
00:01:26,940 --> 00:01:30,180
Neste proxecto, nós imos ser gradualmente mellorar a calidade destas traducións

27
00:01:30,180 --> 00:01:35,790
por humanos corrixir os erros que os nosos ordenadores fixeron.

28
00:01:35,790 --> 00:01:42,330
>> Así, verifícase que había algúns estudantes máis aparecer o luns do inicialmente esperado.

29
00:01:42,330 --> 00:01:48,980
En realidade, agora CS50x ten 100.000 persoas que seguen xunto na casa.

30
00:01:48,980 --> 00:01:54,430
Entón, entende que son todos parte desa clase inaugural de facer este curso de ciencia da computación

31
00:01:54,430 --> 00:01:57,370
educación máis xeralmente, de forma máis ampla, accesible.

32
00:01:57,370 --> 00:02:00,130
E a realidade é agora, con algúns deses cursos masivos en liña,

33
00:02:00,130 --> 00:02:04,070
todas elas comezan con estas cifras moi elevados, como parece ter feito aquí.

34
00:02:04,070 --> 00:02:08,759
Pero o obxectivo, en última instancia, para CS50x é realmente levar a xente como moitos a liña de chegada como sexa posible.

35
00:02:08,759 --> 00:02:12,000
Polo proxecto, CS50x vai ser ofrecido dende esta pasado luns

36
00:02:12,000 --> 00:02:17,430
todo o camiño ata 15 de abril de 2013, para que as persoas que teñen compromisos escolares noutros lugares,

37
00:02:17,430 --> 00:02:20,990
traballo, a familia, os conflitos outros e semellantes, ten un pouco máis de flexibilidade

38
00:02:20,990 --> 00:02:23,640
co cal a mergullo neste curso, que basta dicir,

39
00:02:23,640 --> 00:02:30,540
é moi ambiciosa feito só ao longo de tres meses, durante un semestre de costume.

40
00:02:30,540 --> 00:02:34,190
Pero estes alumnos serán afrontar os conxuntos mesmo problema, a ver o mesmo contido,

41
00:02:34,190 --> 00:02:36,350
ter acceso aos mesmos calzóns e similares.

42
00:02:36,350 --> 00:02:38,990
Entón, entender que todos nós somos verdadeiramente xuntos nesa.

43
00:02:38,990 --> 00:02:42,360
E un dos obxectivos finais de CS50x non é só para ter xente como moitos

44
00:02:42,360 --> 00:02:45,720
para a liña de chegada e darlles esa nova comprensión da ciencia da computación

45
00:02:45,720 --> 00:02:49,000
e programación, pero tamén para que eles teñen esa experiencia compartida.

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

47
00:02:52,010 --> 00:02:56,260
Foi este tipo de experiencia común, para mellor ou para peor, ás veces,

48
00:02:56,260 --> 00:02:59,480
pero ter estas persoas a volver-se cara á esquerda e cara á dereita,

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

50
00:03:01,830 --> 00:03:04,560
É un pouco máis difícil de facer isto persoalmente con persoas en liña,

51
00:03:04,560 --> 00:03:10,580
pero CS50x vai concluír en abril, coa primeira CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
que será unha adaptación en liña da nosa idea da feira

53
00:03:13,630 --> 00:03:18,250
onde estes miles de estudantes todos serán invitados a presentar unha 1 - a 2 minutos de vídeo,

54
00:03:18,250 --> 00:03:22,480
ou un screencast do seu proxecto final ou vídeo deles aceno Ola

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

56
00:03:24,490 --> 00:03:27,610
así como os seus antecesores fixeron aquí no campus da feira,

57
00:03:27,610 --> 00:03:31,400
de xeito que ata o final do semestre, a esperanza é ter unha exposición mundial

58
00:03:31,400 --> 00:03:37,080
de proxectos dos alumnos CS50x 'finais, así como aquel que o espera en decembro aquí no campus.

59
00:03:37,080 --> 00:03:39,680
Así, máis do que en próximos meses.

60
00:03:39,680 --> 00:03:43,640
>> Con 100.000 estudantes, porén, vén a necesidade dunha CAs algúns.

61
00:03:43,640 --> 00:03:47,590
Dado que están abrindo a banda aquí e tendo CS50

62
00:03:47,590 --> 00:03:51,630
varias semanas antes do lanzamento deste material para as persoas en EDX,

63
00:03:51,630 --> 00:03:55,330
entender que queremos involucrar como moitos dos nosos propios alumnos como sexa posible a esta iniciativa,

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

65
00:03:58,720 --> 00:04:01,620
Entón, se quere se involucrar en CS50x,

66
00:04:01,620 --> 00:04:07,450
xuntándose particularmente en CS50x discutir, a versión de EDX CS50 discutir,

67
00:04:07,450 --> 00:04:10,140
que moitos de vostedes están usando no campus, no cadro de avisos en liña

68
00:04:10,140 --> 00:04:13,040
Por favor, faga a cabeza para esa URL, deixe-nos saber quen é vostede,

69
00:04:13,040 --> 00:04:16,450
porque adoraríamos para construír un equipo de alumnos e funcionarios e profesores iguais

70
00:04:16,450 --> 00:04:19,630
no campus que están simplemente xogando ben e axudando.

71
00:04:19,630 --> 00:04:21,720
E cando ven unha cuestión que é familiar a eles,

72
00:04:21,720 --> 00:04:25,320
oe un estudante informar algún erro en algún lugar aí fóra, nalgún país en Internet,

73
00:04:25,320 --> 00:04:27,450
e que toca unha campá porque tamén tivo que mesmo tema

74
00:04:27,450 --> 00:04:32,620
no seu d-hall, hai algún tempo, espero, entón podes dialogar e compartir a súa propia experiencia.

75
00:04:32,620 --> 00:04:37,300
Entón por favor non participar se desexa.

76
00:04:37,300 --> 00:04:39,360
>> Cursos de ciencia da computación na Universidade de Harvard ten un pouco de unha tradición,

77
00:04:39,360 --> 00:04:44,730
CS50 entre eles, ter algún efecto, algunhas roupas, que pode usar con orgullo

78
00:04:44,730 --> 00:04:49,090
ao final do semestre, dicindo con certa orgullo que rematou CS50

79
00:04:49,090 --> 00:04:51,830
e tomou CS50 e afíns, e nós tratamos sempre involucrar os alumnos

80
00:04:51,830 --> 00:04:54,540
neste proceso, na medida do posible, en que convidamos,

81
00:04:54,540 --> 00:04:56,900
nesa época do semestre, os alumnos presenten proxectos

82
00:04:56,900 --> 00:04:59,330
usando o Photoshop ou calquera ferramenta de selección que desexa usar

83
00:04:59,330 --> 00:05:02,330
Se vostede é un deseñador, a someterse proxectos para camisetas e camisolas

84
00:05:02,330 --> 00:05:06,100
e parasois e bandana para cans pequenos que temos agora e similares.

85
00:05:06,100 --> 00:05:09,370
E todo é entón - os vencedores de cada ano son, entón, mostrou

86
00:05:09,370 --> 00:05:12,700
na páxina web do curso en store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Todo é vendido ao custo de alí, pero o sitio só funciona só

88
00:05:15,790 --> 00:05:18,330
e permite que a xente a escoller as cores e debuxos que lle gusta.

89
00:05:18,330 --> 00:05:20,420
Entón eu penso que tiña acaba de compartir algúns dos proxectos do ano pasado

90
00:05:20,420 --> 00:05:25,130
que estaban no sitio alén deste aquí, que é unha tradición anual.

91
00:05:25,130 --> 00:05:29,410
"Todo o día eu estou L Faultn" era unha das propostas do ano pasado,

92
00:05:29,410 --> 00:05:32,290
que aínda está dispoñible alí para ex-alumnos.

93
00:05:32,290 --> 00:05:35,820
Tivemos un regalo ", CS50, Fundación 1989."

94
00:05:35,820 --> 00:05:39,010
Un dos nosos Bowdens, Rob, era moi popular o ano pasado.

95
00:05:39,010 --> 00:05:43,480
"Team Bowden" naceu, este proxecto foi sometido, entre os máis vendidos.

96
00:05:43,480 --> 00:05:49,040
Como foi este aquí. Moitas persoas tiveron "Fever Bowden" de acordo cos rexistros de vendas.

97
00:05:49,040 --> 00:05:52,650
Entenda que que podería agora ser o seu proxecto alí, enriba da Internet.

98
00:05:52,650 --> 00:05:57,510
Máis detalles sobre este problema na próxima define por vir.

99
00:05:57,510 --> 00:06:00,330
>> Unha ferramenta: tivo algunha exposición e espero que agora

100
00:06:00,330 --> 00:06:02,350
algunha experiencia hands-on co GDB,

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

102
00:06:04,570 --> 00:06:09,500
o seu programa nun nivel bastante baixo, facendo o tipo de cousas?

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

104
00:06:13,030 --> 00:06:15,030
Si? Déame algo. [Responder Estudante, inintelixible]

105
00:06:15,030 --> 00:06:18,120
Bo Etapa en función, para que non só ten que escribir run

106
00:06:18,120 --> 00:06:22,310
e ter o golpe programa a través do seu conxunto, imprimir cousas para a saída estándar.

107
00:06:22,310 --> 00:06:25,190
En vez diso, pode percorrelo-lo liña por liña, escribindo seguinte

108
00:06:25,190 --> 00:06:30,300
ir liña por liña por liña ou paso para mergullar nunha función, normalmente o que escribiu.

109
00:06:30,300 --> 00:06:35,240
O que máis fai GDB deixar facer? Si? [Responder Estudante, inintelixible]

110
00:06:35,240 --> 00:06:38,100
Imprimir variables. Entón, se quere facer un pouco de introspección dentro do seu programa

111
00:06:38,100 --> 00:06:41,500
sen ter que recorrer a escribir instrucións printf en todo o lugar,

112
00:06:41,500 --> 00:06:44,600
pode só imprimir unha variable ou mostrar unha variable.

113
00:06:44,600 --> 00:06:46,710
O que máis pode facer un depurador como o GDB?

114
00:06:46,710 --> 00:06:49,170
[Responder Estudante, inintelixible]

115
00:06:49,170 --> 00:06:52,080
Exactamente. Podes establecer puntos de interrupción, pode dicir que a execución pausa

116
00:06:52,080 --> 00:06:54,020
A función principal ou a función foo.

117
00:06:54,020 --> 00:06:56,800
Pode dicir que a execución pausa na liña 123.

118
00:06:56,800 --> 00:06:58,950
E puntos de interrupción son unha técnica moi poderosa

119
00:06:58,950 --> 00:07:01,110
porque se ten unha sensación xeral de que o seu problema

120
00:07:01,110 --> 00:07:05,360
probablemente é, non precisa perder tempo percorrendo totalidade do programa.

121
00:07:05,360 --> 00:07:08,250
Pode saltar esencialmente á dereita e entón comezar a escribir -

122
00:07:08,250 --> 00:07:10,970
percorrendo a con paso ou próximo ou semellante.

123
00:07:10,970 --> 00:07:14,340
Pero o problema con algo parecido ao GDB é que axuda, o humano,

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

125
00:07:16,940 --> 00:07:19,470
Iso non significa necesariamente atopalos moito por ti.

126
00:07:19,470 --> 00:07:23,070
>> Entón, nós introducimos o style50 outro día, que é unha ferramenta de liña de comandos curta

127
00:07:23,070 --> 00:07:27,500
que intenta estilizar o seu código un pouco máis limpa do que o humano, podería ter feito.

128
00:07:27,500 --> 00:07:29,530
Pero iso, tamén, é realmente só unha cousa estética.

129
00:07:29,530 --> 00:07:34,110
Pero acontece que hai esa outra ferramenta chamada Valgrind que é un pouco máis escuro de usar.

130
00:07:34,110 --> 00:07:36,860
A súa saída é atrozmente enigmática, a primeira vista.

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

132
00:07:39,420 --> 00:07:43,080
onde está empezando a usar malloc e distribución dinámica de memoria.

133
00:07:43,080 --> 00:07:45,420
As cousas poden dar moito mal rapidamente.

134
00:07:45,420 --> 00:07:49,320
Porque se esquecer de liberar a súa memoria, ou cancelar a referencia dalgún punteiro NULL,

135
00:07:49,320 --> 00:07:55,770
ou cancelar a referencia dalgún punteiro de lixo, que normalmente é o síntoma que resultados?

136
00:07:55,770 --> 00:07:59,470
L culpa. E comeza este ficheiro núcleo dalgún número de kilobytes ou megabytes

137
00:07:59,470 --> 00:08:02,990
que representa o estado da memoria do seu programa cando el caeu,

138
00:08:02,990 --> 00:08:05,730
pero o seu programa, en última análise seg fallos, fallo de segmento,

139
00:08:05,730 --> 00:08:08,450
o que significa que algo malo aconteceu case sempre relacionados

140
00:08:08,450 --> 00:08:11,750
a un erro relacionado coa memoria que fixo nalgún lugar.

141
00:08:11,750 --> 00:08:14,100
Entón Valgrind axuda a atopar cousas como esta.

142
00:08:14,100 --> 00:08:17,720
É unha ferramenta que executa, como GDB, despois de feita seu programa,

143
00:08:17,720 --> 00:08:20,330
pero en vez de executar o programa directamente, vostede corre Valgrind

144
00:08:20,330 --> 00:08:23,960
e pasar a el o seu programa, así como fai o GDB.

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

146
00:08:26,220 --> 00:08:30,410
é un pouco longo, por iso alí na parte superior da pantalla, podes ver Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" case universalmente significa verbose cando está usando programas nun ordenador Linux.

148
00:08:35,350 --> 00:08:38,770
Entón iso significa cuspir máis datos do que pode, por defecto.

149
00:08:38,770 --> 00:08:45,510
"- Leak-check = total". Este é só dicir selección para todos os posibles derrames de memoria,

150
00:08:45,510 --> 00:08:49,430
erros que eu podería ter feito. Isto, tamén, é un paradigma común con programas Linux.

151
00:08:49,430 --> 00:08:52,710
Xeralmente, se ten un argumento de liña de comandos que é un "interruptor",

152
00:08:52,710 --> 00:08:55,830
que debería cambiar o comportamento do programa, e unha única letra,

153
00:08:55,830 --> 00:09:00,310
é-v, pero iso está conectado, só polo deseño do programador,

154
00:09:00,310 --> 00:09:05,150
é unha palabra completa ou serie de palabras, o argumento de liña de comandos comeza con -.

155
00:09:05,150 --> 00:09:08,190
Estes son só convencións humanas, pero vai ve-los cada vez máis.

156
00:09:08,190 --> 00:09:12,410
E, a continuación, finalmente, "a.out" é o nome arbitrario para o programa, neste exemplo particular.

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

158
00:09:14,640 --> 00:09:22,890
>> Antes de olharmos para o que iso significa, deixe-me ir a un fragmento de código aquí.

159
00:09:22,890 --> 00:09:26,390
E deixe-me pasar esta fora do camiño, en breve,

160
00:09:26,390 --> 00:09:32,120
e imos dar un ollo a memory.c, que é este pequeno exemplo aquí.

161
00:09:32,120 --> 00:09:36,290
Polo tanto, neste programa, deixe-me zoom e as funcións e preguntas.

162
00:09:36,290 --> 00:09:39,430
Temos unha función principal que chama unha función, f,

163
00:09:39,430 --> 00:09:45,590
e entón o que se f continuar a facer, en inglés un pouco técnico?

164
00:09:45,590 --> 00:09:49,760
O que fai f proceder a facer?

165
00:09:49,760 --> 00:09:53,680
Que tal eu vou comezar coa liña 20, e localización da estrela non importa,

166
00:09:53,680 --> 00:09:56,720
pero eu só vou ser coherente aquí con última charla.

167
00:09:56,720 --> 00:09:59,910
Cal é a liña 20 non para nós? No lado da man esquerda. Imos división la aínda máis.

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

169
00:10:02,410 --> 00:10:04,940
Okay. É declarar un punteiro, e agora imos ser aínda máis técnico.

170
00:10:04,940 --> 00:10:10,230
O que significa, moi concretamente, para declarar un punteiro? Alguén máis?

171
00:10:10,230 --> 00:10:15,050
Si? [Responder Estudante, inintelixible] Moi lonxe.

172
00:10:15,050 --> 00:10:17,060
Entón está lendo o lado dereito do signo igual.

173
00:10:17,060 --> 00:10:20,290
Imos nos centrarse só na esquerda, só int * x.

174
00:10:20,290 --> 00:10:24,700
Isto significa "declarar" un punteiro, pero agora imos mergullar máis fondo para esa definición.

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

176
00:10:28,330 --> 00:10:31,940
[Responder Estudante, inintelixible]

177
00:10:31,940 --> 00:10:35,090
Okay. Está preparado para gravar un enderezo na memoria.

178
00:10:35,090 --> 00:10:40,680
Bo E imos dar un paso adiante, que é declarar unha variable, x, que é de 32 bits.

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

180
00:10:44,440 --> 00:10:47,390
Non é porque é un int, porque é un punteiro neste caso.

181
00:10:47,390 --> 00:10:49,650
Coincidencia que é un eo mesmo con un int,

182
00:10:49,650 --> 00:10:51,970
pero o feito de que non é a estrela que significa que este é un punteiro

183
00:10:51,970 --> 00:10:57,300
e no interior do aparello, como acontece con moitos ordenadores, pero non todas, as indicacións son de 32 bits.

184
00:10:57,300 --> 00:11:01,850
En máis hardware moderno, como os máis recentes Macs, os máis recentes PCs, pode ter punteiros de 64 bits,

185
00:11:01,850 --> 00:11:04,160
pero no aparello, esas cousas son de 32 bits.

186
00:11:04,160 --> 00:11:08,380
Entón, imos padronizar iso. Máis concretamente, a historia é a seguinte:

187
00:11:08,380 --> 00:11:10,820
Nós "declarar" un punteiro, que é o que significa isto?

188
00:11:10,820 --> 00:11:12,810
Nós nos preparamos para almacenar un enderezo de memoria.

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

190
00:11:15,530 --> 00:11:19,810
Creamos unha variable chamada x, que ocupa 32 bits

191
00:11:19,810 --> 00:11:23,810
que en breve almacenar o enderezo de un número enteiro.

192
00:11:23,810 --> 00:11:26,470
E iso pode ser tan preciso como podemos chegar.

193
00:11:26,470 --> 00:11:31,810
É bo avanzar para simplificar o mundo e dicir declarar un punteiro chamado x.

194
00:11:31,810 --> 00:11:35,380
Declare un punteiro, pero entender e comprender o que está realmente a suceder

195
00:11:35,380 --> 00:11:38,490
mesmo en só algúns deses personaxes.

196
00:11:38,490 --> 00:11:42,040
>> Agora, este é case un pouco máis fácil, aínda que sexa unha máis expresión.

197
00:11:42,040 --> 00:11:48,160
Entón que é o que está facendo, que é destacado agora: "malloc (10 * sizeof (int));" Si?

198
00:11:48,160 --> 00:11:52,350
[Responder Estudante, inintelixible]

199
00:11:52,350 --> 00:11:58,250
Bo E eu vou leva-lo alí. É atribución dun bloque de memoria para 10 enteiros.

200
00:11:58,250 --> 00:12:02,190
E agora imos mergullar un pouco máis profunda, que é reservar un bloque de memoria para 10 enteiros.

201
00:12:02,190 --> 00:12:05,390
¿Que é malloc despois volver?

202
00:12:05,390 --> 00:12:10,390
O enderezo do bloque, ou, de forma máis concreta, o enderezo do primeiro byte do referido peza.

203
00:12:10,390 --> 00:12:14,080
Como, entón, son eu, o programador, para saber onde ese pedazo de fins de memoria?

204
00:12:14,080 --> 00:12:18,340
Sei que é contiguo. Malloc, por definición, lle dará un anaco contiguo de memoria.

205
00:12:18,340 --> 00:12:21,240
Ningún lagoas. Ten acceso a todos os bytes nese anaco,

206
00:12:21,240 --> 00:12:26,760
de costas cara atrás, pero como sei que o fin deste pedazo de memoria é?

207
00:12:26,760 --> 00:12:28,850
Cando usa malloc? [Responder Estudante, inintelixible] Boa.

208
00:12:28,850 --> 00:12:30,670
Non. Ten que se lembrar.

209
00:12:30,670 --> 00:12:35,960
Eu teño que lembrar que eu usei o valor 10, e eu non parecen mesmo ter feito isto aquí.

210
00:12:35,960 --> 00:12:41,000
Pero a responsabilidade é enteiramente en min. Strlen, que nos facemos un pouco dependente para cordas,

211
00:12:41,000 --> 00:12:45,860
só funciona por mor desa convención de \ 0

212
00:12:45,860 --> 00:12:48,840
ou este carácter especial nul, NUL, ao final dunha cadea.

213
00:12:48,840 --> 00:12:51,740
Isto non val para só anacos arbitrarios de memoria.

214
00:12:51,740 --> 00:12:58,590
Correspóndelle a vostede. Así, a liña 20, entón, aloca un bloque de memoria

215
00:12:58,590 --> 00:13:02,590
que pode almacenar 10 enteiros, e almacena o enderezo do primeiro byte

216
00:13:02,590 --> 00:13:05,610
dese anaco de memoria na variable x chamado.

217
00:13:05,610 --> 00:13:11,140
Logo, o que é un punteiro. Entón, liña 21, desgraciadamente, foi un erro.

218
00:13:11,140 --> 00:13:16,110
Pero, primeiro, o que está facendo? É dicir tenda no lugar 10, 0 indexados,

219
00:13:16,110 --> 00:13:19,480
do bloque de memoria chamado X o valor 0.

220
00:13:19,480 --> 00:13:21,510
>> Entón, observe algunhas cousas están a ocorrer.

221
00:13:21,510 --> 00:13:25,420
Aínda que x é un punteiro, lembrar de algunhas semanas atrás

222
00:13:25,420 --> 00:13:29,440
que aínda pode usar a matriz estilo de notación de colchete.

223
00:13:29,440 --> 00:13:36,180
Porque iso é realmente curto man notación para a aritmética de punteiro máis crítico para o futuro.

224
00:13:36,180 --> 00:13:40,320
onde iríamos facer algo como isto: Colla o enderezo x, mover máis de 10 puntos,

225
00:13:40,320 --> 00:13:44,550
a continuación, ir para alí a calquera enderezo é almacenado no lugar.

226
00:13:44,550 --> 00:13:48,090
Pero, francamente, este é só atroz de ler e sentirse cómodo con.

227
00:13:48,090 --> 00:13:52,900
Así, o mundo normalmente usa os corchetes só porque é moito máis humano-agradable para ler.

228
00:13:52,900 --> 00:13:55,140
Pero iso é o que realmente está a suceder debaixo do capó;

229
00:13:55,140 --> 00:13:58,190
x é un enderezo non, unha matriz, de per si.

230
00:13:58,190 --> 00:14:02,410
Polo tanto, este é almacenar 0 na posición 10 en x.

231
00:14:02,410 --> 00:14:06,120
Por que iso é malo? Si?

232
00:14:06,120 --> 00:14:17,370
[Responder Estudante, inintelixible] Exactamente.

233
00:14:17,370 --> 00:14:21,100
Nós só alocados 10 ints, pero contar de 0 a programar en C,

234
00:14:21,100 --> 00:14:25,690
para que teña acceso a 0 10 1 2 3 4 5 6 7 8 9 pero non.

235
00:14:25,690 --> 00:14:30,270
Así, ou o programa vai culpa seg ou non é.

236
00:14:30,270 --> 00:14:32,900
Pero nós realmente non sabemos, este é un tipo de comportamento non determinístico.

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

238
00:14:35,600 --> 00:14:40,650
Se se comprobar que o sistema operativo non se importa se eu usar este byte extra,

239
00:14:40,650 --> 00:14:43,360
aínda que non lle deses ningunha para min, o meu programa non pode fallar.

240
00:14:43,360 --> 00:14:46,780
É cru, é buggy, pero non pode ver este síntoma,

241
00:14:46,780 --> 00:14:48,960
ou pode velo só de cando en vez.

242
00:14:48,960 --> 00:14:51,230
Pero a realidade é que o erro é, de feito, non hai.

243
00:14:51,230 --> 00:14:54,320
E é realmente problemático se escribiu nun programa que quere ser correcto,

244
00:14:54,320 --> 00:14:58,840
que vendeu o programa que a xente está a usar que de cando en cando cae

245
00:14:58,840 --> 00:15:02,450
porque, por suposto, este non é boa. De feito, se ten un móbil con Android ou un iPhone

246
00:15:02,450 --> 00:15:05,550
e baixar aplicacións nos días de hoxe, se xa tivo un app abortar,

247
00:15:05,550 --> 00:15:10,040
de súpeto el desaparece, que é case sempre o resultado algún problema relacionado coa memoria,

248
00:15:10,040 --> 00:15:12,830
cal o desenvolvedor asneira e dereferenced un punteiro

249
00:15:12,830 --> 00:15:18,670
que el ou ela non debe ter, eo resultado do IOS ou Android é só para matar o programa completo

250
00:15:18,670 --> 00:15:23,080
en vez de comportamento indefinido risco ou algún tipo de compromiso da seguridade.

251
00:15:23,080 --> 00:15:25,950
>> Hai outro erro no programa alén deste.

252
00:15:25,950 --> 00:15:30,180
O que máis me estraguei todo neste programa?

253
00:15:30,180 --> 00:15:32,740
Eu non practiquei o que eu teño cravado. Si?

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

255
00:15:34,760 --> 00:15:36,880
Eu non liberou a memoria. Polo tanto, a regra de ouro agora

256
00:15:36,880 --> 00:15:43,150
ten que ser sempre que chamar malloc, ten que chamar libre cando está feito usando a memoria.

257
00:15:43,150 --> 00:15:45,610
Agora, cando eu ía querer liberar esta memoria?

258
00:15:45,610 --> 00:15:49,780
Probablemente, asumindo que esta primeira liña foi correcta, gustaríame facelo aquí.

259
00:15:49,780 --> 00:15:55,710
Porque eu non podería, por exemplo, fai-o aquí. Por que?

260
00:15:55,710 --> 00:15:57,860
Só fóra do alcance. Así, aínda que estamos falando de punteiros,

261
00:15:57,860 --> 00:16:04,830
Esta é unha semana 2 ou 3 cuestión, no que x é só un alcance dentro das bosquexo onde foi declarado.

262
00:16:04,830 --> 00:16:11,000
Entón vostede definitivamente non pode liberar-lo alí. A miña única oportunidade de liberar-la é de aproximadamente tras a liña 21.

263
00:16:11,000 --> 00:16:15,170
Este é un programa moi sinxelo, era bastante fácil, xa que o tipo de enrolado súa mente

264
00:16:15,170 --> 00:16:17,870
en torno ao que o programa está facendo, onde os erros foron.

265
00:16:17,870 --> 00:16:20,500
E mesmo se non velo en primeiro lugar, espero que sexa un pouco obvio agora

266
00:16:20,500 --> 00:16:23,870
que estes erros son moi facilmente resoltos e facilidade.

267
00:16:23,870 --> 00:16:28,720
Pero cando un programa é máis que 12 liñas de tempo, é 50 liñas, 100 liñas,

268
00:16:28,720 --> 00:16:31,150
andar a través do seu código liña por liña, pensando por iso, loxicamente,

269
00:16:31,150 --> 00:16:35,110
é posible, pero non particularmente divertido de facer, sempre á procura de erros,

270
00:16:35,110 --> 00:16:38,340
e tamén é difícil de facer, e é por iso que unha ferramenta como Valgrind existe.

271
00:16:38,340 --> 00:16:40,900
Deixe-me ir adiante e facelo: déixeme abrir a xanela de terminal,

272
00:16:40,900 --> 00:16:45,400
e deixe-me non só realizar memoria, porque a memoria parece estar ben.

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

274
00:16:49,180 --> 00:16:51,060
non parece ser moi problemático.

275
00:16:51,060 --> 00:16:56,370
Pero deixe-me, con todo, facer unha comprobación de sanidade mental, o que significa só para comprobar

276
00:16:56,370 --> 00:16:58,320
este é ou non realmente correcto.

277
00:16:58,320 --> 00:17:04,690
>> Entón imos facer valgrind-v - Leak-check = completo,

278
00:17:04,690 --> 00:17:07,520
e, a continuación, o nome do programa, neste caso, é a memoria, e non a.out.

279
00:17:07,520 --> 00:17:10,760
Entón deixe-me ir adiante e facelo. Prema Intro.

280
00:17:10,760 --> 00:17:14,109
Querido Deus. Esta é a súa saída, e iso é o que me refire anteriormente.

281
00:17:14,109 --> 00:17:17,550
Pero, se aprender a ler a través de todos os disparates aquí,

282
00:17:17,550 --> 00:17:20,760
máis iso é só a saída de diagnóstico que non é tan interesante.

283
00:17:20,760 --> 00:17:24,829
O seu ollo realmente quere estar buscando é calquera mención de erro ou non é válido.

284
00:17:24,829 --> 00:17:26,800
Palabras que suxiren problemas.

285
00:17:26,800 --> 00:17:29,340
E, de feito, imos ver o que está a suceder de malo aquí.

286
00:17:29,340 --> 00:17:35,230
Eu teño un resumo de calquera tipo, "en uso na saída:. 40 bytes en bloques de 1"

287
00:17:35,230 --> 00:17:38,750
Eu non estou seguro do que un bloque é aínda, pero 40 máis

288
00:17:38,750 --> 00:17:41,260
realmente se sente como se eu puidese descubrir de onde que vén.

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

290
00:17:45,030 --> 00:17:48,780
E, máis concretamente, se rolar aquí,

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

292
00:17:54,520 --> 00:17:59,520
[Responder Estudante, inintelixible] Perfecto. Si, exactamente.

293
00:17:59,520 --> 00:18:03,540
Había dez números enteiros, e cada un destes é o tamaño de 4 ou 32 bits,

294
00:18:03,540 --> 00:18:08,300
entón eu perdín exactamente 40 bytes, porque, como propuxo, non chamei libre.

295
00:18:08,300 --> 00:18:13,460
Isto é un erro, e agora imos ollar para abaixo un pouco máis e ver ao lado deste,

296
00:18:13,460 --> 00:18:16,900
"Válido escribir de tamaño 4". Agora, o que é iso?

297
00:18:16,900 --> 00:18:21,150
Este enderezo é expresado que a notación de base, ao parecer?

298
00:18:21,150 --> 00:18:23,640
Este é hexadecimal, ea calquera momento ve un número comezando con 0x,

299
00:18:23,640 --> 00:18:29,410
isto significa hexadecimal, o que fixemos no camiño de volta, eu creo, sección pset 0 de preguntas,

300
00:18:29,410 --> 00:18:34,090
que era só para facer un exercicio de calefacción, a conversión de decimal para hexadecimal para binario e así por diante.

301
00:18:34,090 --> 00:18:39,220
Hexadecimal, só por convención humana, é xeralmente usado para representar punteiros

302
00:18:39,220 --> 00:18:41,570
ou, de xeito máis xeral, aborda. É só unha convención,

303
00:18:41,570 --> 00:18:45,340
porque é un pouco máis fácil de ler, é un pouco máis compacto do que algo así como decimal,

304
00:18:45,340 --> 00:18:47,720
e binario é inútil para a maioría dos seres humanos de usar.

305
00:18:47,720 --> 00:18:50,840
Entón agora o que significa isto? Ben, parece que hai unha gravación válido

306
00:18:50,840 --> 00:18:54,480
de tamaño 4 na liña 21 de memory.c.

307
00:18:54,480 --> 00:18:59,180
Entón imos voltar á liña 21 e, de feito, é aquí que a gravación non válido.

308
00:18:59,180 --> 00:19:02,640
Entón Valgrind non completamente segura miña man e me diga o que a corrección é,

309
00:19:02,640 --> 00:19:05,520
pero está detectando que eu estou facendo unha gravación válido.

310
00:19:05,520 --> 00:19:08,800
Estou tocando 4 bytes que eu non debería ser, e, ao parecer, iso porque,

311
00:19:08,800 --> 00:19:13,960
como apuntou, eu estou facendo [10] no canto de [9] maximamente

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

313
00:19:16,660 --> 00:19:19,690
Con Valgrind, realizar calquera momento que está escribindo un programa

314
00:19:19,690 --> 00:19:24,190
que usa punteiros e utiliza a memoria, e máis especificamente malloc,

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

316
00:19:27,080 --> 00:19:30,890
pero moi facilmente copiado e pegado mando do Valgrind

317
00:19:30,890 --> 00:19:32,650
a ver se hai algúns erros alí.

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

319
00:19:34,820 --> 00:19:39,430
pero só analizar visualmente a través de toda a saída e ver se ves mencións de erros

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

321
00:19:43,190 --> 00:19:46,200
Todas as palabras que soan como errou en algún lugar.

322
00:19:46,200 --> 00:19:48,580
Entón entender que é unha nova ferramenta no seu toolkit.

323
00:19:48,580 --> 00:19:51,270
>> Agora o luns, tivemos unha morea de xente veu aquí

324
00:19:51,270 --> 00:19:53,150
e representar a noción de unha lista ligada.

325
00:19:53,150 --> 00:20:00,970
E introducimos a lista ligada como unha solución para o problema?

326
00:20:00,970 --> 00:20:04,590
Si? [Responder Estudante, inintelixible] Boa.

327
00:20:04,590 --> 00:20:06,530
Matrices non poden ter memoria engadidos a eles.

328
00:20:06,530 --> 00:20:09,440
Se reservar unha matriz de tamaño 10, que é todo o que pode.

329
00:20:09,440 --> 00:20:13,690
Pode chamar unha función como realloc inicialmente chamada malloc,

330
00:20:13,690 --> 00:20:17,580
e que pode probar a crecer a matriz, se hai espazo para o fin de que

331
00:20:17,580 --> 00:20:21,610
que ninguén máis está a usar e, se non hai, ela só vai atopar unha peza maior noutro lugar.

332
00:20:21,610 --> 00:20:25,040
Pero entón vai copiar todos os bytes para a nova matriz.

333
00:20:25,040 --> 00:20:28,310
Isto soa como unha solución moi correcta.

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

335
00:20:34,790 --> 00:20:36,940
Quero dicir que funciona, os seres humanos teñen resolto este problema.

336
00:20:36,940 --> 00:20:40,710
Por que temos que resolver iso o luns con listas ligadas? Si?

337
00:20:40,710 --> 00:20:44,060
[Responder Estudante, inintelixible] Pode levar un longo tempo.

338
00:20:44,060 --> 00:20:49,260
En realidade, en calquera momento que está chamando malloc calloc ou realloc ou, o que é aínda un outro,

339
00:20:49,260 --> 00:20:52,470
calquera momento que o programa está falando co sistema operativo,

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

341
00:20:54,310 --> 00:20:57,470
E se está facendo eses tipos de cousas en loops, está realmente abrandar as cousas.

342
00:20:57,470 --> 00:21:00,740
Non vai entender iso por máis sinxelo de "Hello World" programas do tipo,

343
00:21:00,740 --> 00:21:04,300
pero en programas moi grandes, pedindo que o sistema operativo novo e de novo para a memoria

344
00:21:04,300 --> 00:21:07,520
ou dándolle de volta unha e outra vez tende a non ser unha cousa boa.

345
00:21:07,520 --> 00:21:11,210
Ademais, é só unha especie de intelectual - é un completo pérdida de tempo.

346
00:21:11,210 --> 00:21:16,490
Por que reservar máis memoria e máis risco, copiar todo para a nova matriz,

347
00:21:16,490 --> 00:21:21,980
Se vostede ten unha alternativa que permite reservar memoria só o que realmente precisa?

348
00:21:21,980 --> 00:21:24,130
Polo tanto, hai pros e contras aquí.

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

350
00:21:26,730 --> 00:21:29,100
Non importa de onde os anacos de memoria son de que están libres,

351
00:21:29,100 --> 00:21:32,070
Eu só podo clasificar de crear estas migas de pan a través de punteiros

352
00:21:32,070 --> 00:21:34,470
amarre miña lista enteira conectados.

353
00:21:34,470 --> 00:21:36,470
Pero eu pagar polo menos un prezo.

354
00:21:36,470 --> 00:21:40,060
>> O que eu teño a dar-se na obtención de listas ligadas?

355
00:21:40,060 --> 00:21:42,470
Si? [Responder Estudante, inintelixible] Boa.

356
00:21:42,470 --> 00:21:45,650
Precisa máis memoria. Agora eu teño espazo para estas indicacións,

357
00:21:45,650 --> 00:21:47,900
e no caso de este super sinxelo conectado

358
00:21:47,900 --> 00:21:51,410
que só a tentar gardar números enteiros, que son 4 bytes, que segue dicindo

359
00:21:51,410 --> 00:21:54,240
ben, un punteiro é de 4 bytes, entón agora eu teño literalmente dobrou

360
00:21:54,240 --> 00:21:57,290
a cantidade de memoria que eu teño só para gardar esta lista.

361
00:21:57,290 --> 00:21:59,680
Pero, de novo, esta é unha cambio constante en ciencia da computación

362
00:21:59,680 --> 00:22:03,440
entre tempo e espazo e esforzo de desenvolvemento, e outros recursos.

363
00:22:03,440 --> 00:22:06,630
O que é outra desvantaxe de usar unha lista ligada? Si?

364
00:22:06,630 --> 00:22:10,150
[Responder Estudante, inintelixible]

365
00:22:10,150 --> 00:22:12,600
Bo Non é tan fácil de acceder. Non podemos máis alavancagem

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

367
00:22:15,530 --> 00:22:18,220
E, máis concretamente, a investigación binaria. Porque aínda que nós, seres humanos

368
00:22:18,220 --> 00:22:20,400
pode ver máis ou menos onde a metade da lista,

369
00:22:20,400 --> 00:22:25,840
o ordenador só sabe que este ligada comeza no enderezo chamado primeiro.

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

371
00:22:28,250 --> 00:22:30,990
E a única forma de que o programa pode atopar o elemento do medio

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

373
00:22:33,350 --> 00:22:35,500
E aínda así, el literalmente ten que buscar a lista enteira porque

374
00:22:35,500 --> 00:22:38,950
mesmo cando chegue o elemento do medio, seguindo os punteiros,

375
00:22:38,950 --> 00:22:42,380
ti, o programa, non ten idea de canto tempo esa lista é, potencialmente,

376
00:22:42,380 --> 00:22:45,250
ata chegar ao final do mesmo, e como vostede sabe de programación

377
00:22:45,250 --> 00:22:48,600
que está ao final dunha lista ligada?

378
00:22:48,600 --> 00:22:51,120
Hai un punteiro especial NULL, polo tanto, de novo, unha convención.

379
00:22:51,120 --> 00:22:53,870
En vez de usar este punteiro, nós definitivamente non queremos que sexa un valor lixo

380
00:22:53,870 --> 00:22:57,750
apuntando para fóra do escenario en algún lugar, queremos que sexa man para abaixo, NULL,

381
00:22:57,750 --> 00:23:01,530
de xeito que temos este terminal nesta estrutura de datos para sabermos onde remata.

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

383
00:23:03,410 --> 00:23:05,980
Fixemos a maior parte deste visualmente, e cos seres humanos,

384
00:23:05,980 --> 00:23:07,630
pero o que se quere facer unha inserción?

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

386
00:23:12,360 --> 00:23:16,730
E se nós entón quería espazo malloc para o número 55, un nó para el,

387
00:23:16,730 --> 00:23:20,730
e entón queremos introducir 55 na lista, así como fixemos o luns?

388
00:23:20,730 --> 00:23:23,690
Como podemos facer iso? Ben, Anita veu e ela camiñou esencialmente da lista.

389
00:23:23,690 --> 00:23:27,500
Comezou o primeiro elemento, entón o próximo, o próximo, o outro, o próximo, o seguinte.

390
00:23:27,500 --> 00:23:29,500
Finalmente chegou a man esquerda todo o camiño

391
00:23:29,500 --> 00:23:34,480
e entender oh, iso é NULL. Entón, o que a manipulación de agullas precisaba ser feito?

392
00:23:34,480 --> 00:23:37,980
A persoa que estaba no fin, número 34, precisaba da súa man esquerda levantada

393
00:23:37,980 --> 00:23:46,220
para apuntar para 55, 55 precisaban do seu brazo esquerdo apuntando cara abaixo para o novo terminador nulo. Feito.

394
00:23:46,220 --> 00:23:49,540
Moi doado de inserir unha lista de 55 clasificados.

395
00:23:49,540 --> 00:23:51,800
E como isto pode ollar?

396
00:23:51,800 --> 00:23:55,690
>> Deixe-me ir adiante e abrir un exemplo de código aquí.

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

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

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

400
00:24:04,920 --> 00:24:13,040
Un nó ten tanto un int chamado n e un punteiro chamado a continuación que só puntos para a próxima cousa na lista.

401
00:24:13,040 --> 00:24:15,450
Que agora está nun arquivo h .. Por que?

402
00:24:15,450 --> 00:24:19,090
Hai esa convención, e non temos aproveitado este unha enorme cantidade de nós mesmos,

403
00:24:19,090 --> 00:24:22,220
pero a persoa que escribiu funcións printf e outros

404
00:24:22,220 --> 00:24:27,150
deu como agasallo para o mundo todas esas funcións por escribir un ficheiro chamado stdio.h.

405
00:24:27,150 --> 00:24:30,950
E despois hai string.h, e entón hai map.h, e hai todos estes arquivos h

406
00:24:30,950 --> 00:24:34,410
que pode ver ou usar durante o prazo escritos por outras persoas.

407
00:24:34,410 --> 00:24:38,470
Normalmente nos. Arquivos h son só cousas como typedefs

408
00:24:38,470 --> 00:24:42,310
ou declaracións de tipos personalizados ou declaracións de constantes.

409
00:24:42,310 --> 00:24:47,890
Non poñer implementacións funcións 'en arquivos de cabeceira.

410
00:24:47,890 --> 00:24:50,570
Vostede pon, en vez diso, só os seus prototipos.

411
00:24:50,570 --> 00:24:53,050
Vostede pon as cousas que quere compartir co mundo o que eles precisan

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

413
00:24:55,640 --> 00:24:59,110
decidimos facer a mesma cousa. Non hai moito en list1.h,

414
00:24:59,110 --> 00:25:02,070
pero poñemos algo que pode ser do interese de persoas no mundo

415
00:25:02,070 --> 00:25:05,030
que queren usar a nosa implantación lista encadeada.

416
00:25:05,030 --> 00:25:08,040
Agora, en list1.c, eu non vou pasar por esa cousa toda

417
00:25:08,040 --> 00:25:11,390
porque é un pouco longo, este programa, pero imos executa-lo real rapidamente no prompt.

418
00:25:11,390 --> 00:25:15,720
Deixe-me compilar Lista1, deixe-me a continuación, realizar Lista1, eo que vai ver é

419
00:25:15,720 --> 00:25:18,070
temos un programa de simulación simple pouco aquí

420
00:25:18,070 --> 00:25:20,990
que vai me permite engadir e eliminar números a unha lista.

421
00:25:20,990 --> 00:25:24,310
Entón deixe-me ir adiante e escriba 3 a 3 opción de menú.

422
00:25:24,310 --> 00:25:27,880
Quero introducir o número - imos facer o primeiro número, que foi de 9,

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

424
00:25:30,550 --> 00:25:33,760
Deixe-me ir adiante e facer outra inserción, entón eu bati opción de menú 3.

425
00:25:33,760 --> 00:25:36,760
Cal é o número que quero introducir? 17.

426
00:25:36,760 --> 00:25:39,220
Intro. E eu vou facer só un.

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

428
00:25:41,720 --> 00:25:45,850
Polo tanto, temos o inicio da lista encadeada que tiñamos en forma de diapositivas nun momento atrás.

429
00:25:45,850 --> 00:25:48,740
Como é que esta inserción realmente a suceder?

430
00:25:48,740 --> 00:25:52,000
De feito, 22 e agora no fin da lista.

431
00:25:52,000 --> 00:25:55,050
Así, a historia que contou no escenario o luns e só agora recapitulou

432
00:25:55,050 --> 00:25:57,460
debe realmente estar a suceder no código.

433
00:25:57,460 --> 00:25:59,700
Imos dar un ollo. Deixe-me rolar neste arquivo.

434
00:25:59,700 --> 00:26:01,720
Nós imos pasar por riba algunhas das funcións,

435
00:26:01,720 --> 00:26:05,630
pero nós imos descender para, digamos, a función de inserción.

436
00:26:05,630 --> 00:26:11,720
>> Imos ver como nós imos sobre a inserción dun novo nodo a esta lista ligada.

437
00:26:11,720 --> 00:26:14,550
Onde está a lista declarada? Ben, imos percorrer todo o camiño ata o cumio,

438
00:26:14,550 --> 00:26:19,970
e entender que a miña lista ligada esencialmente declarado como un punteiro único que é inicialmente NULL.

439
00:26:19,970 --> 00:26:23,180
Entón, eu estou usando unha variable global aquí, que en xeral temos predicado contra

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

441
00:26:25,280 --> 00:26:29,080
é unha especie de preguiza, normalmente, pero non é preguiceiro e non é malo e non é malo

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

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

444
00:26:35,460 --> 00:26:39,100
Entón en vez de declarar isto principal e logo ter que pasalo para cada función

445
00:26:39,100 --> 00:26:42,640
temos escrito neste programa, en vez entender oh, imos facelo global

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

447
00:26:47,060 --> 00:26:50,700
Entón, que se sente ben. Aquí están os meus prototipos, e non imos pasar por todo iso,

448
00:26:50,700 --> 00:26:55,800
pero eu escribín unha función de exclusión, unha función de atopar, unha función de inserción, e unha función de travesía.

449
00:26:55,800 --> 00:26:59,080
Pero imos agora volverse para a función de inserción

450
00:26:59,080 --> 00:27:01,490
para ver como este funciona aquí.

451
00:27:01,490 --> 00:27:09,940
Inserción e on line - aquí imos nós.

452
00:27:09,940 --> 00:27:12,850
Inserir. Entón, non é preciso ningún argumento, porque nós imos pedir

453
00:27:12,850 --> 00:27:15,930
o interior usuario desta función ao número que desexa introducir.

454
00:27:15,930 --> 00:27:19,410
Pero, primeiro, nos preparamos para darlles un pouco de espazo.

455
00:27:19,410 --> 00:27:22,050
Esta é unha especie de copiar e pegar do outro exemplo.

456
00:27:22,050 --> 00:27:25,110
Neste caso, fomos asignación dun int, esta vez estamos alocando un nó.

457
00:27:25,110 --> 00:27:27,910
Eu realmente non me lembro cantos bytes un nó é, pero iso é bo.

458
00:27:27,910 --> 00:27:30,460
Sizeof pode descubrir iso para min.

459
00:27:30,460 --> 00:27:33,340
E por que estou comprobando NULL na liña 120?

460
00:27:33,340 --> 00:27:37,530
O que podería dar mal na liña 119? Si?

461
00:27:37,530 --> 00:27:40,530
[Responder Estudante, inintelixible]

462
00:27:40,530 --> 00:27:43,440
Bo Só podería ser o caso de que eu pedín moita memoria

463
00:27:43,440 --> 00:27:47,020
ou algo está mal eo sistema operativo non ten máis suficiente para me dar,

464
00:27:47,020 --> 00:27:50,640
por iso sinala tanto por volver nulo, e eu non comprobar que

465
00:27:50,640 --> 00:27:54,710
e eu só cega continuar a utilizar o enderezo de retorno, pode ser NULL.

466
00:27:54,710 --> 00:27:58,400
Podería ser algún valor descoñecido, non é unha boa cousa a non ser que eu -

467
00:27:58,400 --> 00:28:00,590
en realidade, non será un valor descoñecido. Pode ser NULL, entón eu non quero

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

469
00:28:02,550 --> 00:28:07,410
Se isto acontecer, eu só volver e imos finxir que eu non volver calquera memoria de todos.

470
00:28:07,410 --> 00:28:12,270
>> Se non, eu digo que o usuario me dar un número para introducir, eu chamo a nosa GetInt vello amigo,

471
00:28:12,270 --> 00:28:15,530
e entón esta foi a nova sintaxe que introduciu o luns.

472
00:28:15,530 --> 00:28:20,320
'Newptr-> n' significa ter o enderezo que lle foi subministrado por malloc

473
00:28:20,320 --> 00:28:23,490
que representa o primeiro byte dun obxecto novo nodo,

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

475
00:28:26,860 --> 00:28:35,270
Unha cuestión pouco trivial: Este é equivalente ao que liña máis enigmática do código?

476
00:28:35,270 --> 00:28:38,110
Como podería eu escribir isto? Quere dar unha facada?

477
00:28:38,110 --> 00:28:41,480
[Responder Estudante, inintelixible]

478
00:28:41,480 --> 00:28:44,870
Bo Usando o n., Pero non é tan sinxelo coma iso.

479
00:28:44,870 --> 00:28:47,090
O que eu primeiro teño que facer? [Responder Estudante, inintelixible]

480
00:28:47,090 --> 00:28:52,730
Bo Eu teño que facer newptr.n *.

481
00:28:52,730 --> 00:28:55,610
Polo tanto, este novo punteiro está dicindo é, obviamente, un enderezo. Por que?

482
00:28:55,610 --> 00:28:59,520
Porque foi devolto por malloc. O newptr * dicindo "vaia alí",

483
00:28:59,520 --> 00:29:02,970
e, a continuación, unha vez que está alí, entón podes usar o máis familiar. n,

484
00:29:02,970 --> 00:29:05,730
pero iso só parece un pouco feo, especialmente se nós, seres humanos van

485
00:29:05,730 --> 00:29:10,360
deseñar os punteiros coas frechas todo o tempo, o mundo ten estándar nesta notación de frecha,

486
00:29:10,360 --> 00:29:12,320
que fai exactamente a mesma cousa.

487
00:29:12,320 --> 00:29:16,070
Así, só usar - notación> cando a cousa da esquerda é un punteiro.

488
00:29:16,070 --> 00:29:18,790
En caso contrario, se é unha estrutura real, use o n ..

489
00:29:18,790 --> 00:29:25,800
E despois este: Por qué me arrincar newptr-> ao lado nulo?

490
00:29:25,800 --> 00:29:28,610
Nós non queremos unha man pendurada esquerda fóra da final da etapa.

491
00:29:28,610 --> 00:29:31,630
Queremos que apuntar directamente cara abaixo, o que significa o fin desta lista

492
00:29:31,630 --> 00:29:34,980
podería ser neste nodo, entón é mellor que seguro que é NULL.

493
00:29:34,980 --> 00:29:38,460
E, en xeral, arrincar súas variables ou membros de datos e estruturas

494
00:29:38,460 --> 00:29:40,470
a algo é só unha boa práctica.

495
00:29:40,470 --> 00:29:45,170
Só deixar lixo existen e seguirán a existir, xeralmente queda en apuros

496
00:29:45,170 --> 00:29:48,650
Se se esquecer de facer algo máis tarde.

497
00:29:48,650 --> 00:29:51,590
>> Aquí está algúns casos. Isto, de novo, é a función de inserción,

498
00:29:51,590 --> 00:29:54,930
ea primeira cousa que eu comprobar se a variable chamada primeiro,

499
00:29:54,930 --> 00:29:58,240
esa variable global é NULL, o que significa que non hai lista ligada.

500
00:29:58,240 --> 00:30:02,460
Non inseriu ningún número, por iso é trivial para introducir este número actual

501
00:30:02,460 --> 00:30:05,240
na lista, porque só pertence ao comezo da lista.

502
00:30:05,240 --> 00:30:08,100
Entón, iso foi cando Anita estaba en pé aquí só, finxindo

503
00:30:08,100 --> 00:30:11,390
non había máis ninguén aquí no escenario ata alocamos un nó,

504
00:30:11,390 --> 00:30:13,940
entón ela podería levantar a man por primeira vez,

505
00:30:13,940 --> 00:30:17,420
se todo o mundo tivese benvida no escenario despois da súa luns.

506
00:30:17,420 --> 00:30:22,900
Agora, aquí, este é un cheque pequeno onde eu teño que dicir que o valor do novo nodo n

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

508
00:30:27,370 --> 00:30:29,930
Isto significa que hai unha lista encadeada que comezou.

509
00:30:29,930 --> 00:30:32,330
Hai polo menos un nodo na lista, pero este cara nova

510
00:30:32,330 --> 00:30:37,230
pertence, antes diso, polo que temos que cambiar as cousas arredor.

511
00:30:37,230 --> 00:30:43,450
Noutras palabras, a lista comezou con só, imos dicir,

512
00:30:43,450 --> 00:30:48,100
só o número 17, que é a - en realidade, o que podemos facer isto máis claro.

513
00:30:48,100 --> 00:30:56,010
Se comezar a nosa historia con un punteiro aquí chamado en primeiro lugar,

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

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

516
00:31:02,510 --> 00:31:07,400
Entón imos finxir que só malloced o enderezo ou o número 9 e poñelas aquí.

517
00:31:07,400 --> 00:31:13,170
O primeiro é de 9 por defecto, o primeiro escenario discutir só significa punto imos este cara aquí,

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

519
00:31:15,790 --> 00:31:18,280
O seguinte número que desexa introducir é 17.

520
00:31:18,280 --> 00:31:22,420
17 pertence aquí, entón nós imos ter que facer algunha revisión lóxica por iso.

521
00:31:22,420 --> 00:31:26,060
Entón, imos en vez diso, antes de facer iso, imos finxir que quería introducir o número 8.

522
00:31:26,060 --> 00:31:28,650
>> Entón, só por conveniencia, eu vou deseñar aquí.

523
00:31:28,650 --> 00:31:30,760
Pero lembre, malloc pode poñelas en calquera lugar.

524
00:31:30,760 --> 00:31:33,460
Pero polo amor de deseño, vou poñelas aquí.

525
00:31:33,460 --> 00:31:38,440
Entón, finxir que acabou asignado un nó ao número 8, que é NULL por defecto.

526
00:31:38,440 --> 00:31:42,800
O que ten que ocorrer agora? Un par de cousas.

527
00:31:42,800 --> 00:31:47,090
Fixemos este erro no escenario o luns, onde actualizamos un punteiro como este,

528
00:31:47,090 --> 00:31:51,890
a continuación, fixo iso, e entón dixo - nos orfos todos os outros no escenario.

529
00:31:51,890 --> 00:31:54,350
Porque non pode - a orde das operacións aquí é importante,

530
00:31:54,350 --> 00:31:58,760
porque agora nós perdemos esta 9 no que é exactamente o tipo de flotar no espazo.

531
00:31:58,760 --> 00:32:01,150
Polo tanto, este non era o camiño certo o luns.

532
00:32:01,150 --> 00:32:03,330
Primeiro temos que facer outra cousa.

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

534
00:32:06,280 --> 00:32:10,550
Cal sería a mellor forma de introducir 8?

535
00:32:10,550 --> 00:32:14,720
En vez de actualizar este primeiro punteiro, só actualizar este aquí no seu lugar.

536
00:32:14,720 --> 00:32:17,720
Entón, necesitamos unha liña de código que vai virar personaxe NULL

537
00:32:17,720 --> 00:32:22,020
nun punteiro real que está apuntando para o nodo 9,

538
00:32:22,020 --> 00:32:27,970
e entón podemos seguramente cambiar primeiro a apuntar para este cara aquí.

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

540
00:32:31,330 --> 00:32:33,580
E o que iso realmente coma aquí?

541
00:32:33,580 --> 00:32:36,900
Se olharmos para o código, observe que eu fixen exactamente iso.

542
00:32:36,900 --> 00:32:41,970
Eu xa dixen newptr, e nesta historia, newptr estaba apuntando cara este cara.

543
00:32:41,970 --> 00:32:45,520
>> Entón deixe-me tirar unha cousa, e eu debería deixar cuarto un pouco máis por iso.

544
00:32:45,520 --> 00:32:48,540
Entón, perdoe o deseño pequeno.

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

546
00:32:52,140 --> 00:32:57,940
Esa é a variable que declarou algunhas liñas antes, en liña - só por riba de 25.

547
00:32:57,940 --> 00:33:03,430
E está a apuntar cara 8. Polo tanto, cando digo newptr-> seguinte, o que significa ir a estrutura

548
00:33:03,430 --> 00:33:07,910
que está a ser apuntado por newptr, entón aquí estamos nós, vai alí.

549
00:33:07,910 --> 00:33:13,990
A continuación, a frecha está dicindo obter o seguinte campo, e entón a = está dicindo poñer o valor alí?

550
00:33:13,990 --> 00:33:17,280
O valor que estaba en primeiro, que o valor que estaba en primeiro lugar?

551
00:33:17,280 --> 00:33:21,930
Primeiro foi apuntando para este nodo, o que significa que este debe agora apuntar a este nodo.

552
00:33:21,930 --> 00:33:25,660
Noutras palabras, o que parece aínda unha desorde ridículo coa miña letra,

553
00:33:25,660 --> 00:33:28,620
o que é unha idea simple de só mover esas frechas ao redor

554
00:33:28,620 --> 00:33:31,560
traduce código con só forro este.

555
00:33:31,560 --> 00:33:38,110
Almacenar o que está en primeiro no campo ao lado e entón actualizar o primeiro realmente é.

556
00:33:38,110 --> 00:33:40,900
Imos adiante e avanzar rapidamente un pouco diso,

557
00:33:40,900 --> 00:33:44,220
e mirar só para esa inserción do rabo por agora.

558
00:33:44,220 --> 00:33:51,210
Supoña que chegar ao punto no que eu considerar que o seguinte campo de algún no é NULL.

559
00:33:51,210 --> 00:33:53,410
E neste punto da historia, un detalle que eu estou pasando por riba

560
00:33:53,410 --> 00:33:58,170
é que eu introducín outro punteiro se aquí na liña 142, punteiro antecesor.

561
00:33:58,170 --> 00:34:01,320
Esencialmente, neste punto da historia, unha vez que a lista é longa,

562
00:34:01,320 --> 00:34:04,800
Eu medio que teño piso con dous dedos, porque se eu for moi lonxe,

563
00:34:04,800 --> 00:34:08,219
Teña en conta que nunha única lista de longo, non pode ir cara atrás.

564
00:34:08,219 --> 00:34:13,659
Entón esa idea de predptr é o meu dedo cara á esquerda, e newptr - non newptr.

565
00:34:13,659 --> 00:34:17,199
Outro indicador que está aquí é o meu outro dedo, e eu son só un tipo de andar a lista.

566
00:34:17,199 --> 00:34:22,179
É por iso que existe. Pero imos considerar só un dos casos máis simple aquí.

567
00:34:22,179 --> 00:34:26,620
Se o campo seguinte que punteiro é NULL, o que é a implicación lóxica?

568
00:34:26,620 --> 00:34:30,840
Se está atravesando este e bater un punteiro NULL?

569
00:34:30,840 --> 00:34:35,780
Está no fin da lista, e así o código para entón engadir este elemento adicional

570
00:34:35,780 --> 00:34:41,230
é unha especie de intuitiva terá que no cuxa próxima punteiro é NULL,

571
00:34:41,230 --> 00:34:46,120
por iso este é actualmente NULL, e cambia-lo, aínda que, de ser o enderezo do novo nodo.

572
00:34:46,120 --> 00:34:52,260
Entón, estamos só debuxando no código da frecha que trazamos no escenario, levantando a man esquerda de alguén.

573
00:34:52,260 --> 00:34:54,070
>> É o caso que eu vou acenar as mans menos por agora,

574
00:34:54,070 --> 00:34:58,020
só porque eu creo que é fácil perderse cando o facemos neste tipo de ambiente,

575
00:34:58,020 --> 00:35:00,600
é a comprobación de inserción no medio da lista.

576
00:35:00,600 --> 00:35:03,220
Pero só de forma intuitiva, o que debe ocorrer se queres descubrir

577
00:35:03,220 --> 00:35:06,600
onde un número pertence no medio é que ten que camiñar

578
00:35:06,600 --> 00:35:09,510
con máis de un dedo, máis dun punteiro,

579
00:35:09,510 --> 00:35:12,920
descubrir onde el pertence, a verificación é o elemento <actual,

580
00:35:12,920 --> 00:35:15,450
> O actual, e unha vez que atopar ese lugar,

581
00:35:15,450 --> 00:35:20,400
entón tes que facer este tipo de xogo de cunchas onde move os punteiros en torno de moito coidado.

582
00:35:20,400 --> 00:35:23,850
E esa resposta, se desexa razón por este na casa no seu propio país,

583
00:35:23,850 --> 00:35:28,340
se reduce só a estas dúas liñas de código, pero a orde das liñas é super importante.

584
00:35:28,340 --> 00:35:31,390
Porque se soltar a man de alguén e levantar outra persoa na orde errada,

585
00:35:31,390 --> 00:35:34,580
de novo, pode acabar orfandade da lista.

586
00:35:34,580 --> 00:35:39,500
Para resumir máis conceptualmente, a inserción na cola é relativamente sinxelo.

587
00:35:39,500 --> 00:35:42,940
A inserción na cabeza tamén é relativamente simple,

588
00:35:42,940 --> 00:35:45,580
pero precisa actualizar un punteiro adicional neste momento

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

590
00:35:47,930 --> 00:35:51,560
e, a continuación, a inserción no medio implica un esforzo aínda maior,

591
00:35:51,560 --> 00:35:56,130
Para inserir coidadosamente o número 20 na súa posición correcta,

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

593
00:35:58,350 --> 00:36:02,700
Entón, ten que facer algo como ter o novo nó de punto de 20 a 22,

594
00:36:02,700 --> 00:36:08,470
e, a continuación, o punteiro que no debe ser actualizado pasado?

595
00:36:08,470 --> 00:36:10,630
E 17, de verdade inserir-lo.

596
00:36:10,630 --> 00:36:14,080
Entón, de novo, eu vou retrasar o código real para que a implementación particular.

597
00:36:14,080 --> 00:36:17,280
>> A primeira vista, é un pouco asustado, pero é realmente só un ciclo infinito

598
00:36:17,280 --> 00:36:21,770
que é looping, looping, looping, looping, e rompendo así que bateu o punteiro NULL,

599
00:36:21,770 --> 00:36:24,590
en que punto pode facer a inserción necesaria.

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

601
00:36:30,960 --> 00:36:34,590
Que era unha especie de un lote, e parece que resolvemos un problema,

602
00:36:34,590 --> 00:36:36,940
pero nós introducimos un totalmente diferente. Francamente, nós pasamos todo ese tempo

603
00:36:36,940 --> 00:36:40,540
en grande e Ω e correndo o tempo, intentando resolver os problemas máis rapidamente,

604
00:36:40,540 --> 00:36:43,270
e aquí estamos dando un gran paso cara atrás, el se sente.

605
00:36:43,270 --> 00:36:45,380
E, no entanto, se o obxectivo é almacenar datos,

606
00:36:45,380 --> 00:36:48,010
parece que o Santo Graal, como dixemos o luns, sería realmente

607
00:36:48,010 --> 00:36:50,470
para gardar cousas instantaneamente.

608
00:36:50,470 --> 00:36:53,930
>> En realidade, creo que fixemos poñer lista de banda conectado por un momento

609
00:36:53,930 --> 00:36:56,000
e nós, en vez introduciu a noción dunha mesa.

610
00:36:56,000 --> 00:36:59,110
E imos pensar nunha mesa por un momento como unha matriz.

611
00:36:59,110 --> 00:37:03,790
Esta matriz e neste caso aquí ten preto de 26 elementos, de 0 a 25,

612
00:37:03,790 --> 00:37:07,940
e supoña que precisaba dalgún anaco de almacenamento de nomes:

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

614
00:37:10,350 --> 00:37:12,880
E precisa algunha estrutura de datos para almacenar eses nomes.

615
00:37:12,880 --> 00:37:15,000
Ben, vostede podería usar algo como unha lista ligada

616
00:37:15,000 --> 00:37:20,260
e pode percorrer a lista de introducir Alicia antes de Bob e Charlie despois de Bob e así por diante.

617
00:37:20,260 --> 00:37:23,850
E, de feito, se queres ver o código así como un aparte,

618
00:37:23,850 --> 00:37:27,230
sei que en list2.h, facemos exactamente isto.

619
00:37:27,230 --> 00:37:30,610
Non vai pasar por este código, pero esta é unha variante do primeiro exemplo

620
00:37:30,610 --> 00:37:34,640
que introduce outra struct que xa vimos antes estudante chamado,

621
00:37:34,640 --> 00:37:40,330
e entón o que realmente almacena na lista vinculada é un punteiro para unha estrutura de estudante

622
00:37:40,330 --> 00:37:44,520
en vez de enteiro un pouco simple, n.

623
00:37:44,520 --> 00:37:46,900
Entón, entendo que hai código alí que implica cordas reais,

624
00:37:46,900 --> 00:37:49,940
Pero se o obxectivo en mans realmente agora é resolver o problema da eficiencia,

625
00:37:49,940 --> 00:37:53,380
Non sería bo se nós estamos dando un obxecto chamado Alice,

626
00:37:53,380 --> 00:37:56,020
queremos poñer-la no lugar correcto, nunha estrutura de datos,

627
00:37:56,020 --> 00:37:58,860
parece que sería moi bo para só poñer Alicia,

628
00:37:58,860 --> 00:38:01,180
cuxo nome comeza con A, no primeiro lugar.

629
00:38:01,180 --> 00:38:05,270
E Bob, cuxo nome comeza con B, na segunda posición.

630
00:38:05,270 --> 00:38:09,580
Con unha matriz, ou imos comezar chamándoo de unha táboa, a táboa hash en que,

631
00:38:09,580 --> 00:38:13,650
podemos facer exactamente isto. Se nos é dado un nome como Alicia,

632
00:38:13,650 --> 00:38:16,700
unha secuencia como Alicia, onde pon a-l-i-c-e?

633
00:38:16,700 --> 00:38:20,540
Necesitamos un hueristic. Necesitamos dunha función para sacar algunha entrada como Alicia

634
00:38:20,540 --> 00:38:24,610
e voltar unha resposta, "Alicia Pon este lugar."

635
00:38:24,610 --> 00:38:28,720
E esta función, esta caixa negra, vai ser chamado de función hash.

636
00:38:28,720 --> 00:38:32,330
>> Unha función hash é algo que ten unha entrada, como "Alicia",

637
00:38:32,330 --> 00:38:38,080
e volta para ti, normalmente, a localización numérica nalgunha estrutura de datos onde Alicia pertence.

638
00:38:38,080 --> 00:38:40,830
Neste caso, a función hash debe ser relativamente sinxela.

639
00:38:40,830 --> 00:38:47,510
A nosa función hash debe dicir, se está dado "Alicia", que o personaxe debería me importar?

640
00:38:47,510 --> 00:38:55,660
O primeiro. Entón eu ollo para [0], e entón eu digo si [0] carácter é A, voltar o número 0.

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

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

643
00:39:05,940 --> 00:39:10,960
para esa estrutura de datos. Pero hai un problema.

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

645
00:39:13,060 --> 00:39:17,510
Onde poñemos Anita? O seu nome tamén comeza coa letra A,

646
00:39:17,510 --> 00:39:20,330
e parece que fixemos unha confusión aínda maior do problema.

647
00:39:20,330 --> 00:39:24,380
Temos agora a inserción inmediata, inserción constante de tempo, para unha estrutura de datos

648
00:39:24,380 --> 00:39:27,100
en vez de peor caso lineal,

649
00:39:27,100 --> 00:39:29,510
pero o que podemos facer con Anita neste caso?

650
00:39:29,510 --> 00:39:34,110
Cales son as dúas opcións, realmente? Si?

651
00:39:34,110 --> 00:39:37,410
[Responder Estudante, inintelixible] Ok, entón nós poderíamos ter outra dimensión.

652
00:39:37,410 --> 00:39:42,320
Isto é bo. Así, podemos construír cousas en 3D como falamos verbalmente o luns.

653
00:39:42,320 --> 00:39:46,700
Poderiamos engadir outro acceso aquí, pero creo que non, eu estou tentando manter isto simple.

654
00:39:46,700 --> 00:39:50,160
O obxectivo xeral aquí é ter acceso constante de tempo inmediato,

655
00:39:50,160 --> 00:39:52,170
de xeito que é a adición de moita complexidade.

656
00:39:52,170 --> 00:39:55,970
Cales son as outras opcións ao tentar inserir Anita para esta estrutura de datos? Si?

657
00:39:55,970 --> 00:39:58,610
[Responder Estudante, inintelixible] Boa. Entón, nós poderíamos pasar todo o mundo para abaixo,

658
00:39:58,610 --> 00:40:03,040
como Charlie cutuca baixo Bob e Alicia, e entón poñemos Anita onde realmente quere ser.

659
00:40:03,040 --> 00:40:05,660
>> Está claro que, agora, hai un efecto colateral desta.

660
00:40:05,660 --> 00:40:09,000
Esta estrutura de datos é probablemente útil non porque queremos introducir a xente xa

661
00:40:09,000 --> 00:40:11,250
senón porque queremos comprobar se eles están alí máis tarde

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

663
00:40:13,600 --> 00:40:15,850
Nós imos facer algo con eses datos, eventualmente.

664
00:40:15,850 --> 00:40:20,810
Entón agora nós medio que parafuso sobre Alicia, que non é máis onde debería estar.

665
00:40:20,810 --> 00:40:23,880
Non é Bob, nin é Charlie.

666
00:40:23,880 --> 00:40:26,060
Entón quizais iso non é unha boa idea.

667
00:40:26,060 --> 00:40:28,830
Pero, en realidade, esta é unha opción. Nós poderiamos cambiar todos para abaixo,

668
00:40:28,830 --> 00:40:32,240
ou diaños, Anita chegou atrasado para o xogo, por que non imos só poñer Anita

669
00:40:32,240 --> 00:40:35,870
aquí non, aquí non, aquí non, imos poñer-la un pouco máis abaixo da lista.

670
00:40:35,870 --> 00:40:38,680
Pero, entón, este problema comeza a devolver de novo.

671
00:40:38,680 --> 00:40:41,630
Pode ser capaz de atopar Alicia instantaneamente, con base no seu nome.

672
00:40:41,630 --> 00:40:44,320
E Bob instantaneamente, e Charlie. Pero entón mira para Anita,

673
00:40:44,320 --> 00:40:46,360
e ve, hein, Alice está no camiño.

674
00:40:46,360 --> 00:40:48,770
Ben, deixe-me ver abaixo Alicia. Bob non é Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie non é Anita. Oh, hai Anita.

676
00:40:51,850 --> 00:40:54,720
E se seguir ese tren da lóxica toda a maneira,

677
00:40:54,720 --> 00:41:00,690
o que é o tempo de execución do peor caso de atopar ou inserción de Anita para esta nova estrutura de datos?

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

679
00:41:03,280 --> 00:41:06,280
Porque, no peor dos casos, hai Alicia, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
todo o camiño para alguén chamado "Y", polo que hai só un punto á esquerda.

681
00:41:10,150 --> 00:41:13,950
Afortunadamente, non temos un chamado "Z", entón poñemos Anita na parte inferior.

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

683
00:41:16,040 --> 00:41:19,890
Entón quizais necesitamos introducir esta terceira dimensión.

684
00:41:19,890 --> 00:41:22,230
E non é que se non introducir esta terceira dimensión,

685
00:41:22,230 --> 00:41:25,240
non podemos facelo perfectamente, pero o Santo Graal vai estar recibindo

686
00:41:25,240 --> 00:41:28,370
constante de tempo de inserción e dinámicos para que as insercións

687
00:41:28,370 --> 00:41:30,960
non temos a hard-código dunha matriz de tamaño 26.

688
00:41:30,960 --> 00:41:34,400
Podemos introducir tantos nomes como queremos, pero imos dar o noso intervalo de 5 minutos aquí

689
00:41:34,400 --> 00:41:38,790
e despois facelo correctamente.

690
00:41:38,790 --> 00:41:46,020
Todo ben. Eu define a historia ata moi artificialmente hai

691
00:41:46,020 --> 00:41:48,670
escollendo Alicia e Bob e Charlie e Anita,

692
00:41:48,670 --> 00:41:51,000
cuxo nome foi, obviamente, vai chocar con Alice.

693
00:41:51,000 --> 00:41:54,120
Pero a pregunta que terminou o luns con só quão probable é

694
00:41:54,120 --> 00:41:56,370
que quere obter eses tipos de colisións? Noutras palabras,

695
00:41:56,370 --> 00:42:00,490
se comezar a usar esa estrutura de táboa, que é realmente só unha matriz,

696
00:42:00,490 --> 00:42:02,460
neste caso, de 26 posicións,

697
00:42:02,460 --> 00:42:05,740
E se os nosos insumos son distribuídos uniformemente en vez?

698
00:42:05,740 --> 00:42:09,620
Non é artificialmente Alicia e Bob e Charlie e David e así por diante en orde alfabética,

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

700
00:42:12,380 --> 00:42:15,220
>> Quizais nós imos ter sorte e non imos ter dous un ou dous de B

701
00:42:15,220 --> 00:42:17,640
con probabilidade moi alta, pero como alguén apuntou,

702
00:42:17,640 --> 00:42:20,730
este problema xeneralizado e non 0-25

703
00:42:20,730 --> 00:42:26,060
pero, digamos, de 0 a 364 ou 65, moitas veces, o número de días nun ano típico,

704
00:42:26,060 --> 00:42:31,170
e fixo a pregunta: "Cal é a probabilidade de que dous de nós nesta sala ten a mesma data de aniversario?"

705
00:42:31,170 --> 00:42:34,600
Dito doutra forma, cal é a probabilidade de que dous de nós ten un nome que comeza coa?

706
00:42:34,600 --> 00:42:37,190
O tipo de pregunta é a mesma, pero este espazo de enderezos,

707
00:42:37,190 --> 00:42:39,940
este espazo de procura, é maior no caso de aniversarios,

708
00:42:39,940 --> 00:42:42,820
porque temos tantos días de máis o ano que letras no alfabeto.

709
00:42:42,820 --> 00:42:44,910
Cal é a probabilidade dunha colisión?

710
00:42:44,910 --> 00:42:48,410
Ben, podemos pensar niso por descubrir as matemáticas de forma oposta.

711
00:42:48,410 --> 00:42:50,580
Cal é a probabilidade de colisións non?

712
00:42:50,580 --> 00:42:53,970
Ben, esa expresión aquí di que o que é a probabilidade

713
00:42:53,970 --> 00:42:58,770
hai só unha persoa neste cuarto, que ten un aniversario?

714
00:42:58,770 --> 00:43:01,190
É 100%. Porque se hai só unha persoa na sala,

715
00:43:01,190 --> 00:43:03,940
seu aniversario pode ser calquera dos 365 días fóra do ano.

716
00:43:03,940 --> 00:43:08,650
Logo, as opcións 365/365 me dá un valor de 1.

717
00:43:08,650 --> 00:43:11,250
Así, a probabilidade en cuestión no momento é só 1.

718
00:43:11,250 --> 00:43:13,270
Pero se hai unha segunda persoa no cuarto,

719
00:43:13,270 --> 00:43:16,490
cal é a probabilidade de que o seu aniversario é diferente?

720
00:43:16,490 --> 00:43:20,680
Hai só 364 días posibles, anos bisestos, ignorando

721
00:43:20,680 --> 00:43:23,580
para o seu aniversario para non chocar con outras persoas.

722
00:43:23,580 --> 00:43:31,920
Así, 364/365. Unha terceira persoa entra, é 363/365, e así por diante.

723
00:43:31,920 --> 00:43:35,790
Así, continúan multiplicando xunto destas fraccións, que están ficando cada vez menores,

724
00:43:35,790 --> 00:43:40,720
para descubrir cal é a probabilidade de que todos temos aniversarios orixinais?

725
00:43:40,720 --> 00:43:43,570
Pero, entón, podemos, por suposto, pode ter esa resposta e lanzalo ao redor de

726
00:43:43,570 --> 00:43:47,210
e facer 1 menos de todo isto, unha expresión que vai finalmente chegar

727
00:43:47,210 --> 00:43:51,250
se recorda a parte de atrás dos seus libros de matemáticas, que parece un pouco algo como isto,

728
00:43:51,250 --> 00:43:54,590
que é moito máis facilmente interpretado graficamente.

729
00:43:54,590 --> 00:43:57,820
E este gráfico aquí ten no eixe x o número de aniversarios,

730
00:43:57,820 --> 00:44:02,030
ou o número de persoas con aniversarios, e no eixe y é a probabilidade dunha saída.

731
00:44:02,030 --> 00:44:06,060
E o que iso está dicindo é que se ten, digamos, ata,

732
00:44:06,060 --> 00:44:10,860
imos escoller algo así como 22, 23.

733
00:44:10,860 --> 00:44:13,160
Se hai 22 ou 23 persoas na sala,

734
00:44:13,160 --> 00:44:17,100
a probabilidade de que dúas desas poucas persoas van ter o mesmo aniversario

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

736
00:44:19,560 --> 00:44:23,450
50% as probabilidades de que unha clase de só 22 persoas, dun seminario, practicamente,

737
00:44:23,450 --> 00:44:25,790
2 de esas persoas van ter o mesmo aniversario.

738
00:44:25,790 --> 00:44:28,520
Porque hai moitas maneiras en que pode ter o mesmo aniversario.

739
00:44:28,520 --> 00:44:31,110
Peor aínda, se ollar para o lado dereito da gráfica,

740
00:44:31,110 --> 00:44:34,040
no momento en que ten unha clase con 58 alumnos en que,

741
00:44:34,040 --> 00:44:39,270
a probabilidade de dúas persoas que teñan un aniversario é alta, super super, preto do 100%.

742
00:44:39,270 --> 00:44:41,880
Agora, iso é unha especie de traxe divertido sobre a vida real.

743
00:44:41,880 --> 00:44:45,850
>> Pero as implicacións, agora, para estruturas de datos e almacenamento de información

744
00:44:45,850 --> 00:44:51,100
significa que só supoñendo que ten un bo, distribución, limpa e uniforme de datos

745
00:44:51,100 --> 00:44:53,650
e ten unha matriz grande abondo para caber unha morea de cousas

746
00:44:53,650 --> 00:44:59,360
non significa que está indo para obter as persoas en lugares exclusivos.

747
00:44:59,360 --> 00:45:03,810
Vai ter colisións. Polo tanto, esta noción de hash, como se chama,

748
00:45:03,810 --> 00:45:07,450
tomando unha entrada como "Alicia" e Masaxes-o de algunha maneira

749
00:45:07,450 --> 00:45:10,190
e despois volver unha resposta como 0 ou 1 ou 2.

750
00:45:10,190 --> 00:45:17,500
Voltar algunha saída desa función é atormentado por esa probabilidade de colisión.

751
00:45:17,500 --> 00:45:19,530
Entón, como podemos tratar con esas colisións?

752
00:45:19,530 --> 00:45:21,940
Ben, en ningún caso, podemos ter a idea de que foi suxerido.

753
00:45:21,940 --> 00:45:25,100
Podemos só cambiar todos para abaixo, ou quizais, un pouco máis simple,

754
00:45:25,100 --> 00:45:29,870
en vez de todos os outros movemento, imos mover Anita para o fondo do local dispoñible.

755
00:45:29,870 --> 00:45:32,810
Entón, se Alice está en 0, Bob está en 1, Charlie está en 2,

756
00:45:32,810 --> 00:45:35,260
imos poñer Anita na localización 3.

757
00:45:35,260 --> 00:45:38,860
E esta é unha técnica en estruturas de datos chamado lineal enquisa.

758
00:45:38,860 --> 00:45:41,310
Lineal porque está só camiñando nesa liña, e é unha especie de sondaxe

759
00:45:41,310 --> 00:45:43,640
para os lugares dispoñibles na estrutura de datos.

760
00:45:43,640 --> 00:45:46,210
Por suposto, este transfórmase en O (n).

761
00:45:46,210 --> 00:45:49,590
A estrutura de datos é realmente completo, hai 25 persoas que xa,

762
00:45:49,590 --> 00:45:54,120
e Anita vén, ela acaba co que sería localización Z, e iso é bo.

763
00:45:54,120 --> 00:45:56,540
Ela aínda encaixa, e podemos atopala máis tarde.

764
00:45:56,540 --> 00:46:00,100
>> Pero iso era contrario ao obxectivo de acelerar as cousas.

765
00:46:00,100 --> 00:46:02,530
Entón, o que se creou, esa terceira dimensión?

766
00:46:02,530 --> 00:46:06,400
Esta técnica é xeralmente chamado encadeamento separado, ou que posúan cadeas.

767
00:46:06,400 --> 00:46:10,030
E o que unha táboa hash é agora, esta estrutura tabular,

768
00:46:10,030 --> 00:46:13,450
súa táboa é só unha matriz de punteiros.

769
00:46:13,450 --> 00:46:18,230
Pero o que os punteiros apuntan para adiviñar o que é?

770
00:46:18,230 --> 00:46:21,970
Unha lista ligada. Entón, o que se aproveitar o mellor de ambos os mundos?

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

772
00:46:26,500 --> 00:46:32,070
na estrutura de datos, de xeito que pode inmediatamente ir a [0] [1], [30], ou así por diante,

773
00:46:32,070 --> 00:46:36,480
pero para que poidamos ter algunha flexibilidade e podemos encaixar Anita e Alice e Adam

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

775
00:46:38,630 --> 00:46:43,470
nós pero deixar que o outro eixe crecer de forma arbitraria.

776
00:46:43,470 --> 00:46:47,340
E finalmente, a partir do luns, ten esa capacidade expresiva con lista encadeada.

777
00:46:47,340 --> 00:46:49,530
Podemos crecer unha estrutura de datos de forma arbitraria.

778
00:46:49,530 --> 00:46:52,450
Alternativamente, podemos só facer unha matriz de 2 dimensións enormes,

779
00:46:52,450 --> 00:46:57,190
pero que vai ser unha situación terrible unha das liñas dunha matriz de 2 dimensións

780
00:46:57,190 --> 00:47:01,280
non é suficientemente grande para a persoa cuxo nome adicional acontece a comezar con A.

781
00:47:01,280 --> 00:47:04,200
Deus nos libre de ter que recolocar unha estrutura 2-dimensional enorme

782
00:47:04,200 --> 00:47:06,600
só porque hai tantas persoas denominados A,

783
00:47:06,600 --> 00:47:09,480
especialmente cando hai tan poucas persoas nomeadas algo Z.

784
00:47:09,480 --> 00:47:12,170
El só vai ser unha moi escasa estrutura de datos.

785
00:47:12,170 --> 00:47:15,400
Polo tanto, non é perfecto, por calquera medio, pero agora polo menos temos a capacidade

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

787
00:47:19,090 --> 00:47:21,090
polo menos en termos de eixe vertical,

788
00:47:21,090 --> 00:47:25,850
e despois só temos que decidir onde poñer Anita ou Alice nesta lista ligada.

789
00:47:25,850 --> 00:47:32,480
Se non nos importa con clasificando as cousas, que rapidez podemos inserir Alicia nunha estrutura como esta?

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

791
00:47:35,370 --> 00:47:37,550
Alicia vai no inicio desta lista ligada.

792
00:47:37,550 --> 00:47:40,000
Pero isto non é un gran negocio. Porque se Anita entón vén

793
00:47:40,000 --> 00:47:42,160
un número de pasos despois, onde é que Anita pertence?

794
00:47:42,160 --> 00:47:45,140
Ben, [0]. POO. Alicia xa está na lista ligada.

795
00:47:45,140 --> 00:47:47,760
>> Pero, se non lle importan a clasificación destes nomes,

796
00:47:47,760 --> 00:47:53,580
podemos só pasar máis de Alicia, inserción Anita, pero iso é tempo constante.

797
00:47:53,580 --> 00:47:57,010
Mesmo se hai Alicia e Adán e todos eses outros nomes A,

798
00:47:57,010 --> 00:47:59,410
non está realmente cambiando-los fisicamente. Por que?

799
00:47:59,410 --> 00:48:04,090
Porque nós fixemos aquí con lista encadeada, quen sabe se estes nós son ao final?

800
00:48:04,090 --> 00:48:06,550
Todo o que tes que facer é mover as migas de pan.

801
00:48:06,550 --> 00:48:10,930
Move as frechas ao redor, non ten que mover fisicamente todos os datos ao redor.

802
00:48:10,930 --> 00:48:14,610
Así, podemos introducir Anita, nese caso, instantaneamente. Tempo constante.

803
00:48:14,610 --> 00:48:20,250
Polo tanto, temos de tempo constante de investigación e de tempo constante inserción de alguén como Anita.

804
00:48:20,250 --> 00:48:22,740
Pero tipo de simplificar o mundo.

805
00:48:22,740 --> 00:48:28,510
O que máis tarde quere atopar Alicia?

806
00:48:28,510 --> 00:48:31,050
O que máis tarde quere atopar Alicia?

807
00:48:31,050 --> 00:48:35,690
Cantos pasos que vai levar?

808
00:48:35,690 --> 00:48:37,850
[Responder Estudante, inintelixible]

809
00:48:37,850 --> 00:48:40,950
Exactamente. O número de persoas antes de Alicia na lista ligada.

810
00:48:40,950 --> 00:48:45,420
Polo tanto, non é perfecta, porque a nosa estrutura de datos, unha vez máis, ten este acceso vertical

811
00:48:45,420 --> 00:48:50,240
e el ten esas listas ligadas de suspensión - na verdade, non imos deseñar unha matriz.

812
00:48:50,240 --> 00:48:56,020
Ten estas listas ligadas colgado fóra del que se parece un pouco algo como isto.

813
00:48:56,020 --> 00:48:59,110
Pero o problema é se Alicia e Adán e todos eses outros nomes A

814
00:48:59,110 --> 00:49:01,720
acabar máis e máis para alí,

815
00:49:01,720 --> 00:49:04,810
atopar alguén pode acabar levando unha morea de pasos,

816
00:49:04,810 --> 00:49:06,670
bcause ten que atravesar a lista ligada,

817
00:49:06,670 --> 00:49:08,090
que é unha operación lineal.

818
00:49:08,090 --> 00:49:14,270
Entón, realmente, a continuación, o tempo de inserción, en última análise é O (n), onde n é o número de elementos na lista.

819
00:49:14,270 --> 00:49:21,780
Dividido por, imos chamalo arbitrariamente m, onde m é o número de listas ligadas

820
00:49:21,780 --> 00:49:24,500
que temos neste eixe vertical.

821
00:49:24,500 --> 00:49:27,180
Noutras palabras, se realmente asumir unha distribución uniforme de nomes,

822
00:49:27,180 --> 00:49:30,150
totalmente irrealista. Hai, obviamente, máis de algunhas letras que outros.

823
00:49:30,150 --> 00:49:32,580
>> Pero se nós asumimos para o momento dunha distribución uniforme,

824
00:49:32,580 --> 00:49:37,350
e temos n total de persoas, e m correntes totais

825
00:49:37,350 --> 00:49:40,630
á nosa disposición, a continuación, a lonxitude de cada unha destas cadeas

826
00:49:40,630 --> 00:49:44,380
forma moi simple, será o total, n, dividido polo número de cadeas.

827
00:49:44,380 --> 00:49:48,900
Así, n / m. Pero aquí é onde podemos ser todo matematicamente intelixente.

828
00:49:48,900 --> 00:49:53,030
m é unha constante, porque non hai un número fixo de estes.

829
00:49:53,030 --> 00:49:54,620
Está indo para declarar a matriz en principio,

830
00:49:54,620 --> 00:49:58,450
e non estamos redimensionando o eixe vertical. Por definición, que permanece fixo.

831
00:49:58,450 --> 00:50:01,220
É só o eixe horizontal, por así dicir, iso está cambiando.

832
00:50:01,220 --> 00:50:04,760
Entón, tecnicamente, é unha constante. Entón, agora, o tempo de inserción

833
00:50:04,760 --> 00:50:09,700
é moi fermoso o (n).

834
00:50:09,700 --> 00:50:12,410
De xeito que non se sente todo o que moito mellor.

835
00:50:12,410 --> 00:50:14,940
Pero o que hai de certo niso? Ben, todo este tempo, por semanas,

836
00:50:14,940 --> 00:50:20,640
estamos dicindo o (n ²). O (n), 2 x n ², - n, dividido por 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
É só ² n. Pero agora, nesta parte do semestre,

838
00:50:23,580 --> 00:50:25,560
podemos empezar a falar sobre o mundo real novo.

839
00:50:25,560 --> 00:50:31,520
E n / m é absolutamente máis rápido que só n soa.

840
00:50:31,520 --> 00:50:35,170
Se ten mil nomes, e división las en varios baldes

841
00:50:35,170 --> 00:50:37,820
para que teña só 10 nomes en cada unha destas cadeas,

842
00:50:37,820 --> 00:50:41,670
absolutamente buscar 10 cousas vai ser máis rápido que mil cousas.

843
00:50:41,670 --> 00:50:43,740
E así un dos conxuntos de problemas futuros vai desafia-lo

844
00:50:43,740 --> 00:50:46,100
para pensar sobre exactamente que, a pesar de si,

845
00:50:46,100 --> 00:50:49,520
assintoticamente e matematicamente, iso aínda é só lineal,

846
00:50:49,520 --> 00:50:51,700
que suga, en xeral, ao tentar atopar as cousas.

847
00:50:51,700 --> 00:50:54,530
En realidade, o que vai ser máis rápido que

848
00:50:54,530 --> 00:50:56,520
debido a este divisor.

849
00:50:56,520 --> 00:50:58,310
E así, alí está de novo vai ser este trade-off

850
00:50:58,310 --> 00:51:01,390
e este conflito entre a teoría ea realidade,

851
00:51:01,390 --> 00:51:03,550
e un dos botóns vai comezar a xirar neste punto no semestre

852
00:51:03,550 --> 00:51:07,510
é máis a realidade como un tipo de preparar para o final de semster,

853
00:51:07,510 --> 00:51:09,280
como imos introducir no mundo da programación web,

854
00:51:09,280 --> 00:51:11,530
onde realmente, o rendemento vai contar porque os seus usuarios están indo para

855
00:51:11,530 --> 00:51:14,880
comezar a sentir e apreciar as decisións de deseño pobre.

856
00:51:14,880 --> 00:51:19,950
>> Entón, como vai facer sobre a implementación dun conectado - dunha táboa hash con 31 elementos?

857
00:51:19,950 --> 00:51:22,600
E o exemplo anterior foi arbitrariamente sobre aniversarios.

858
00:51:22,600 --> 00:51:26,190
Se alguén ten un aniversario de 01 de xaneiro ou 01 de febreiro, imos poñer-los neste balde.

859
00:51:26,190 --> 00:51:28,960
Se é 02 de xaneiro, 02 de febreiro, 2 de marzo, nós imos poñer-los neste balde.

860
00:51:28,960 --> 00:51:32,220
É por iso que foi de 31. Como declarar unha táboa hash?

861
00:51:32,220 --> 00:51:37,480
Pode ser moi sinxelo, mesa * ó é o meu nome arbitrario para el, [31].

862
00:51:37,480 --> 00:51:42,400
Tanto me dá 31 consellos para nós,

863
00:51:42,400 --> 00:51:45,370
e que me permite ter 31 punteiros para listas ligadas

864
00:51:45,370 --> 00:51:48,800
aínda que estas correntes son inicialmente NULL.

865
00:51:48,800 --> 00:51:54,860
O que quero poñer, se eu queira gardar "Alicia", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Ben, é preciso involucrar esas cousas nunha estrutura

867
00:51:57,010 --> 00:52:00,530
porque necesitamos Alicia para apuntar para Bob, para apuntar para Charlie, e así por diante.

868
00:52:00,530 --> 00:52:04,940
Non podemos só ter os nomes só, entón eu podería crear unha nova estrutura chamada no aquí.

869
00:52:04,940 --> 00:52:08,310
>> ¿Que é un nodo real? ¿Que é un nodo nesta nova lista ligada?

870
00:52:08,310 --> 00:52:11,840
O primeiro, chamado palabra, é o nome da persoa.

871
00:52:11,840 --> 00:52:14,340
Lonxitude, presuntamente, refírese ao lonxitude máxima do nome dun ser humano,

872
00:52:14,340 --> 00:52:18,210
sexa o que sexa, 20, 30, 40 personaxes en casos de canto tolo,

873
00:52:18,210 --> 00:52:22,680
e un é para o que? É só o carácter NULL extra, \ 0.

874
00:52:22,680 --> 00:52:27,410
Polo tanto, este nodo é embrulho "algo" dentro de si,

875
00:52:27,410 --> 00:52:29,640
pero tamén declara un punteiro chamado seguinte

876
00:52:29,640 --> 00:52:32,580
para que poidamos cadea de Alicia para Bob para Charlie e así por diante.

877
00:52:32,580 --> 00:52:36,700
Pode ser NULL, pero non necesariamente ten que ser.

878
00:52:36,700 --> 00:52:40,110
Calquera dúbida sobre estas táboas de hash? Si?

879
00:52:40,110 --> 00:52:46,190
[Estudante pedindo cuestión, inintelixible] Unha matriz - boa pregunta.

880
00:52:46,190 --> 00:52:50,120
¿Por que esta palabra char nunha matriz en vez de só char *?

881
00:52:50,120 --> 00:52:53,830
Neste exemplo un tanto arbitraria, eu non quería ter que recorrer

882
00:52:53,830 --> 00:52:56,190
para malloc para cada un dos nomes orixinais.

883
00:52:56,190 --> 00:52:59,530
Eu quería declarar unha cantidade máxima de memoria para a cadea

884
00:52:59,530 --> 00:53:06,020
para que eu puidese copiar a estrutura de Alicia \ 0 e non ter que tratar con malloc e free e similares.

885
00:53:06,020 --> 00:53:11,710
Pero eu podería facelo se eu quería ser máis consciente do uso do espazo. Boa pregunta.

886
00:53:11,710 --> 00:53:14,780
Entón, imos tratar de xeneralizar lonxe deste

887
00:53:14,780 --> 00:53:18,350
e centrar o resto de hoxe en estruturas de datos máis xeral

888
00:53:18,350 --> 00:53:21,170
e outros problemas que pode resolver empregando os mesmos fundamentos

889
00:53:21,170 --> 00:53:24,590
aínda que as estruturas de datos elas mesmas poden diferir nos seus detalles.

890
00:53:24,590 --> 00:53:27,910
>> Así, verifícase en ciencia da computación, as árbores son moi comúns.

891
00:53:27,910 --> 00:53:29,760
E pode pensar nunha especie de árbore como unha árbore xenealóxica,

892
00:53:29,760 --> 00:53:31,830
onde hai algunhas raíces, algúns matriarca ou patriarca,

893
00:53:31,830 --> 00:53:34,540
avó ou avoa ou máis cedo de volta,

894
00:53:34,540 --> 00:53:38,880
baixo o cal están a nai eo pai ou irmáns diversas ou similares.

895
00:53:38,880 --> 00:53:42,500
Así, unha estrutura de árbore ten nós e ten fillos,

896
00:53:42,500 --> 00:53:45,260
xeralmente 0 ou máis nenos para cada nó.

897
00:53:45,260 --> 00:53:47,320
E algúns dos xerga que ve nesta foto aquí

898
00:53:47,320 --> 00:53:50,630
é calquera das nenos pequenos ou netos nas beiras

899
00:53:50,630 --> 00:53:52,330
que non teñen frechas que emanan a partir deles,

900
00:53:52,330 --> 00:53:55,070
estas son as follas chamados, e calquera persoa no interior

901
00:53:55,070 --> 00:53:58,790
é un nó interior, pode chamalo de calquera cousa nese sentido.

902
00:53:58,790 --> 00:54:01,430
Pero esa estrutura é moi común. Este aquí é un pouco arbitraria.

903
00:54:01,430 --> 00:54:04,930
Temos un fillo á esquerda, temos tres fillos, á dereita,

904
00:54:04,930 --> 00:54:06,830
dous nenos no ángulo inferior esquerdo.

905
00:54:06,830 --> 00:54:10,740
Así podemos ter diferentes tamaños de árbores, pero se comezar a estandarizar as cousas,

906
00:54:10,740 --> 00:54:15,330
e pode chamar este vídeo Patrick en busca binaria dun curto anterior

907
00:54:15,330 --> 00:54:19,490
investigación, en liña binario non ten que ser aplicado con unha matriz

908
00:54:19,490 --> 00:54:21,410
ou anacos de papel en un cadro negro.

909
00:54:21,410 --> 00:54:25,490
Supoña que vostede quería para almacenar os seus números nunha estrutura de datos máis sofisticados.

910
00:54:25,490 --> 00:54:27,680
Vostede podería crear unha árbore coma esta.

911
00:54:27,680 --> 00:54:35,290
Pode ter un nó declarado en C, e que o nodo pode ter, polo menos, dous elementos no interior do mesmo.

912
00:54:35,290 --> 00:54:39,470
Un deles é o número que desexa almacenar, eo outro é - ben, necesitamos máis.

913
00:54:39,470 --> 00:54:41,540
A outra é os seus fillos.

914
00:54:41,540 --> 00:54:45,150
Entón, aquí está outra estrutura de datos. Desta vez, o nó defínese como o almacenamento dun número n

915
00:54:45,150 --> 00:54:49,060
e, a continuación, dous punteiros, neno esquerdo e dereito do neno.

916
00:54:49,060 --> 00:54:52,100
E eles non son arbitrarias. O que é interesante sobre esta árbore?

917
00:54:52,100 --> 00:55:00,550
>> Cal é o estándar en forma como temos colocado iso ou como Patrick colocouse no seu vídeo?

918
00:55:00,550 --> 00:55:02,790
É medio obvio que hai algunha ordenación suceder aquí,

919
00:55:02,790 --> 00:55:04,460
pero o que é a regra simple? Si?

920
00:55:04,460 --> 00:55:08,350
[Responder Estudante, inintelixible]

921
00:55:08,350 --> 00:55:12,040
Perfecto. Se ollar para iso, ve os números pequenos de esquerda,

922
00:55:12,040 --> 00:55:14,690
grandes números do lado esquerdo, pero iso é certo para cada nó.

923
00:55:14,690 --> 00:55:20,370
Para cada nodo, o seu fillo esquerdo inferior, e á súa neno dereita máis grande que.

924
00:55:20,370 --> 00:55:25,210
O que isto significa que agora é que se eu queira buscar esta estrutura de datos, por exemplo, o número 44,

925
00:55:25,210 --> 00:55:29,320
Eu teño que comezar na raíz, porque, como con todas estas estruturas máis complexas de datos, agora,

926
00:55:29,320 --> 00:55:31,910
Temos só un punteiro para unha cousa, o inicio.

927
00:55:31,910 --> 00:55:35,010
E, neste caso, o inicio é a raíz. Non é o lado esquerdo,

928
00:55:35,010 --> 00:55:39,530
é a raíz desta estrutura. Entón eu vexo aquí é 55, e eu estou buscando 44.

929
00:55:39,530 --> 00:55:41,430
Cal dirección que quero ir?

930
00:55:41,430 --> 00:55:45,680
Ben, eu quero ir á esquerda, porque, obviamente, á dereita vai ser moi grande.

931
00:55:45,680 --> 00:55:49,050
Entón, observe aquí, é unha especie de conceptualmente cortar a árbore en media

932
00:55:49,050 --> 00:55:51,700
porque nunca está indo para o lado dereito.

933
00:55:51,700 --> 00:55:55,410
Entón agora eu ir do 55 ao 33. É moi pequeno de un número.

934
00:55:55,410 --> 00:56:01,590
Estou na procura de 44, pero agora sei se 44 é nesta árbore, podo ir, por suposto, á dereita.

935
00:56:01,590 --> 00:56:04,460
Entón, de novo, eu son a poda da árbore no medio.

936
00:56:04,460 --> 00:56:06,780
É practicamente idéntico conceptualmente para o libro de teléfono.

937
00:56:06,780 --> 00:56:09,510
É idéntico ao que fixemos cos papeis no cadro negro,

938
00:56:09,510 --> 00:56:13,940
pero é unha estrutura máis sofisticada, que nos permite realmente facer

939
00:56:13,940 --> 00:56:16,880
este dividir e conquistar, polo deseño do algoritmo,

940
00:56:16,880 --> 00:56:19,420
e, de feito, atravesando unha estrutura como esta - berros.

941
00:56:19,420 --> 00:56:22,870
Atravesando unha estrutura como esta, onde é só "ir por este camiño ou ir por ese camiño",

942
00:56:22,870 --> 00:56:26,870
significa todo o código que que dobrado a súa mente en primeiro lugar cando implementar lo na sección

943
00:56:26,870 --> 00:56:31,270
ou andar con el na casa, por busca binaria, usando recursão ou iteração,

944
00:56:31,270 --> 00:56:35,060
é unha dor no pescozo. Atopar o elemento do medio, a continuación, facer o seu redondeo cara arriba ou cara abaixo.

945
00:56:35,060 --> 00:56:39,230
>> Hai unha beleza a este, porque agora podemos utilizar recursão novo,

946
00:56:39,230 --> 00:56:43,760
pero moito máis limpa. En realidade, se está no número 55 e quere atopar 44,

947
00:56:43,760 --> 00:56:48,450
vaia á esquerda, neste caso, entón o que fai? Vostede corre o algoritmo exacto.

948
00:56:48,450 --> 00:56:51,560
Vostede verifica o valor do nodo, entón vai cara á esquerda ou á dereita.

949
00:56:51,560 --> 00:56:53,670
Entón comprobar o valor do nodo, vai cara á esquerda ou á dereita.

950
00:56:53,670 --> 00:56:56,710
Isto é perfectamente adecuado para a recursividade.

951
00:56:56,710 --> 00:57:00,920
Así, aínda que no pasado fixemos algúns exemplos bastante arbitrarias que implica recursão

952
00:57:00,920 --> 00:57:03,430
que non debe ser recursiva, con stuctures de datos,

953
00:57:03,430 --> 00:57:07,820
especialmente árbores, é unha perfecta aplicación desta idea de levar un problema,

954
00:57:07,820 --> 00:57:12,920
reducindo-a, e logo a solución do mesmo tipo de, pero menor do programa.

955
00:57:12,920 --> 00:57:14,590
>> Polo tanto, hai outra estrutura de datos que podemos presentar.

956
00:57:14,590 --> 00:57:18,760
Este é proxectada a primeira vista ollar enigmático, pero este é incrible.

957
00:57:18,760 --> 00:57:25,090
Polo tanto, esta é unha estrutura de datos chamada trie, trie, que é herdado da recuperación de palabra,

958
00:57:25,090 --> 00:57:30,210
que non é pronunciado re-try-val, pero é o que o mundo chámase esas cousas. Intenta. T-r-i-e.

959
00:57:30,210 --> 00:57:35,190
É unha estrutura de árbore de calquera tipo, pero cada un de nós nun trie

960
00:57:35,190 --> 00:57:41,280
parece ser o que? E iso é un pouco erro, porque é unha especie de abreviado.

961
00:57:41,280 --> 00:57:45,960
Pero parece que cada nodo neste trie é na verdade unha matriz.

962
00:57:45,960 --> 00:57:48,840
E aínda que o autor deste diagrama non demostrou que,

963
00:57:48,840 --> 00:57:54,130
neste caso, este trie é unha estrutura de datos cuxo propósito na vida é almacenar palabras

964
00:57:54,130 --> 00:57:57,330
como A-l-i-c-e ou B-o-b.

965
00:57:57,330 --> 00:58:02,480
E a maneira pola cal os datos tendas Alicia e Bob e Charlie e Anita e así por diante

966
00:58:02,480 --> 00:58:06,970
é que usa unha matriz para almacenar que Alicia nunha trie,

967
00:58:06,970 --> 00:58:09,820
comezamos o nodo raíz que se parece unha matriz,

968
00:58:09,820 --> 00:58:12,080
e que foi escrito en notación abreviada.

969
00:58:12,080 --> 00:58:15,070
O autor omitido abcdefg porque non había nomes con iso.

970
00:58:15,070 --> 00:58:19,150
Eles só mostrou M e P e T, pero neste caso,

971
00:58:19,150 --> 00:58:22,780
imos pasar lonxe de Alicia e Bob e Charlie para algúns nomes que están aquí.

972
00:58:22,780 --> 00:58:25,670
Maxwell é realmente neste diagrama.

973
00:58:25,670 --> 00:58:29,570
Entón, como o almacenamento de autor M-a-x-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
El ou ela comezou no nodo raíz, e foi para [M], de xeito máis ou menos 13, o lugar 13 na matriz.

975
00:58:36,990 --> 00:58:40,750
Entón, a partir de aí, hai un punteiro.

976
00:58:40,750 --> 00:58:42,760
Un punteiro levando a outro array.

977
00:58:42,760 --> 00:58:47,880
A partir de aí o autor indexados en que a matriz na posición A, como se mostra alí enriba, á esquerda,

978
00:58:47,880 --> 00:58:52,250
e despois que el ou ela seguiu ese punteiro a outra matriz,

979
00:58:52,250 --> 00:58:55,460
e foi para o punteiro no lugar X.

980
00:58:55,460 --> 00:58:59,840
A continuación, na seguinte localización matriz W, E, L, L, e así por diante,

981
00:58:59,840 --> 00:59:03,090
e, finalmente, imos realmente tentar poñer unha imaxe para iso.

982
00:59:03,090 --> 00:59:05,380
O que fai un nó como no código?

983
00:59:05,380 --> 00:59:11,820
Un nó nunha trie contén unha matriz de punteiros para nós máis.

984
00:59:11,820 --> 00:59:16,090
Pero hai tamén debe haber algún tipo de valor booleano, polo menos nesta aplicación.

985
00:59:16,090 --> 00:59:18,770
Acontece que eu chamalo is_word. Por que?

986
00:59:18,770 --> 00:59:22,670
Porque cando está inserindo Maxwell, non está inserindo

987
00:59:22,670 --> 00:59:25,300
nada a esta estrutura de datos.

988
00:59:25,300 --> 00:59:27,480
Non está escribindo M. Non está escribindo X.

989
00:59:27,480 --> 00:59:30,240
Todo o que está facendo é seguir punteiros.

990
00:59:30,240 --> 00:59:33,360
O punteiro que representa M, entón o punteiro que representa a,

991
00:59:33,360 --> 00:59:36,310
a continuación, o punteiro que representa X, a continuación, W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
pero o que ten que facer ao final é unha especie de balde, comprobar, cheguei a este sitio.

993
00:59:41,950 --> 00:59:45,560
Había unha palabra que termina aquí na estrutura de datos.

994
00:59:45,560 --> 00:59:48,190
>> Entón, o que unha trie é realmente cheo e co autor escolleu para representar

995
00:59:48,190 --> 00:59:51,880
Estes terminuses con pequenos triángulos.

996
00:59:51,880 --> 00:59:56,470
Isto só significa que o feito de este triángulo está aquí, este valor booleano verdadeiro

997
00:59:56,470 --> 00:59:59,200
significa que se ir cara atrás na árbore,

998
00:59:59,200 --> 01:00:02,420
significa que unha palabra é chamado Maxwell neste.

999
01:00:02,420 --> 01:00:04,870
Pero a palabra foo, por exemplo,

1000
01:00:04,870 --> 01:00:07,970
non está na árbore, porque se eu comezar no nodo raíz aquí enriba,

1001
01:00:07,970 --> 01:00:14,030
Non hai punteiro f, ningún punteiro o, non o punteiro. Foo non é un nome neste dicionario.

1002
01:00:14,030 --> 01:00:22,460
Pero por outro lado, turação, t-u-r-i-n-g. Unha vez máis, eu non almacenar t ou u ou r ou i ou n ou g.

1003
01:00:22,460 --> 01:00:29,820
Pero eu fixen na tenda esta estrutura de datos dun valor verdadeiro camiño ata aquí neste nó - na árbore

1004
01:00:29,820 --> 01:00:33,030
definindo ese valor booleano de is_word a verdade.

1005
01:00:33,030 --> 01:00:35,740
Así, un trie é unha especie de esta estrutura meta moi interesante,

1006
01:00:35,740 --> 01:00:39,810
onde non está realmente gardar as propias palabras para este tipo de dicionario.

1007
01:00:39,810 --> 01:00:45,100
Para ser claro, só está almacenando si ou non, non é unha palabra que termina aquí.

1008
01:00:45,100 --> 01:00:46,430
>> Agora, cal é a implicación?

1009
01:00:46,430 --> 01:00:51,120
Se ten 150 mil palabras nun dicionario que estás almacenar na memoria

1010
01:00:51,120 --> 01:00:53,400
usar algo como unha lista ligada,

1011
01:00:53,400 --> 01:00:56,870
vai ter 150 mil nós na súa lista ligada.

1012
01:00:56,870 --> 01:01:00,250
E atopar unha desas palabras en orde alfabética pode levar tempo O (n).

1013
01:01:00,250 --> 01:01:04,370
Tempo lineal. Pero no caso aquí dunha trie,

1014
01:01:04,370 --> 01:01:09,210
o que é o tempo de execución de atopar unha palabra?

1015
01:01:09,210 --> 01:01:17,390
Acontece que a beleza aquí é que, mesmo se ten 149.999 palabras xa neste dicionario,

1016
01:01:17,390 --> 01:01:20,170
como aplicado con esta estrutura de datos,

1017
01:01:20,170 --> 01:01:25,560
canto tempo leva para atopar ou inserir unha persoa que, como Alicia, Alicia?

1018
01:01:25,560 --> 01:01:30,640
Ben, é só 5, quizais 6 pasos para o personaxe de fuga.

1019
01:01:30,640 --> 01:01:32,880
Porque o presense doutros nomes na estrutura

1020
01:01:32,880 --> 01:01:35,340
non estar no camiño de entrada de Alicia.

1021
01:01:35,340 --> 01:01:39,640
Ademais, atopar Alicia xa que hai 150.000 palabras neste dicionario

1022
01:01:39,640 --> 01:01:41,960
non entrar no seu camiño de atopar Alicia en todo,

1023
01:01:41,960 --> 01:01:46,880
porque Alicia é. . . . . aquí, porque eu atope un valor booleano.

1024
01:01:46,880 --> 01:01:50,920
E se non hai booleano verdadeiro, entón Alicia non está na esta estrutura de datos de palabras.

1025
01:01:50,920 --> 01:01:56,220
Noutras palabras, o tempo de execución de atopar as cousas e inserindo as cousas para este novo

1026
01:01:56,220 --> 01:02:01,920
estrutura de datos de trie é o de - non é n.

1027
01:02:01,920 --> 01:02:05,730
Porque o presense de 150.000 persoas non ten efecto sobre Alicia, que parece.

1028
01:02:05,730 --> 01:02:11,560
Entón, imos chamalo de k, onde k é o lonxitude máxima dunha palabra en inglés

1029
01:02:11,560 --> 01:02:14,050
que é, tipicamente, non máis que 20 e poucos caracteres.

1030
01:02:14,050 --> 01:02:17,940
Así, k é unha constante. Así, o Santo Graal que parecen ter atopado agora

1031
01:02:17,940 --> 01:02:26,000
é o dunha vez, trie constante para pastillas para investigacións, por eliminacións.

1032
01:02:26,000 --> 01:02:29,170
Como o número de cousas xa na estrutura,

1033
01:02:29,170 --> 01:02:32,600
que non son nin mesmo físicamente alí. Unha vez máis, eles están só unha especie de DESestablecido, si ou non,

1034
01:02:32,600 --> 01:02:35,050
non ten impacto no seu tempo futuro en execución.

1035
01:02:35,050 --> 01:02:37,940
>> Pero ten que ser un problema, se non, non tería perdido tanto tempo

1036
01:02:37,940 --> 01:02:41,460
en todas estas estruturas de datos outros só para finalmente chegar ao un segredo que é incrible.

1037
01:02:41,460 --> 01:02:46,410
Entón, cal é o prezo que estamos pagando para alcanzar esa grandeza aquí? Espazo.

1038
01:02:46,410 --> 01:02:49,010
Esa cousa é enorme. E a razón que o autor

1039
01:02:49,010 --> 01:02:52,400
non presenta-lo aquí, destacar que todas esas cousas que se parecen con matrices,

1040
01:02:52,400 --> 01:02:55,400
non debuxar o resto da árbore, o resto do trie,

1041
01:02:55,400 --> 01:02:58,060
porque son non só relevantes para a historia.

1042
01:02:58,060 --> 01:03:01,870
Pero todos estes nós son super grande, e cada nodo na árbore ocupa

1043
01:03:01,870 --> 01:03:07,780
26 ou, en realidade, podería ser de 27 carácteres, porque neste caso eu estaba incluído espazo para o apóstrofo

1044
01:03:07,780 --> 01:03:09,980
para que pudéssemos ter palabras apostrofado.

1045
01:03:09,980 --> 01:03:14,450
Neste caso, trátase se matrices de ancho. Así, aínda que eles non están picutured,

1046
01:03:14,450 --> 01:03:18,190
iso leva a unha enorme cantidade de RAM.

1047
01:03:18,190 --> 01:03:20,670
O que pode ser bo, especilly en hardware moderno,

1048
01:03:20,670 --> 01:03:25,650
pero esa é a cambio. Temos menos tempo, gastan máis espazo.

1049
01:03:25,650 --> 01:03:28,580
Entón, onde é que isto vai?

1050
01:03:28,580 --> 01:03:32,640
Ben, imos facer - imos ver aquí.

1051
01:03:32,640 --> 01:03:39,510
Imos facer un salto este cara aquí.

1052
01:03:39,510 --> 01:03:43,450
>> Acreditar ou non, divertido como C foi xa hai algún tempo,

1053
01:03:43,450 --> 01:03:48,130
estamos chegando ao punto en que, no semestre é hora de transición para as cousas máis modernas.

1054
01:03:48,130 --> 01:03:50,950
Cousas nun nivel superior. E aínda que para o próximo par de semanas

1055
01:03:50,950 --> 01:03:54,580
imos continuar a mergullo no mundo de punteiros e xestión de memoria

1056
01:03:54,580 --> 01:03:57,210
para ese confort coa que podemos entón construír,

1057
01:03:57,210 --> 01:04:01,270
O xogo final é, finalmente, para introducir, ironicamente, non esta linguaxe.

1058
01:04:01,270 --> 01:04:03,330
Nós imos gastar, como 10 minutos falando HTML.

1059
01:04:03,330 --> 01:04:05,950
Todo o HTML é unha linguaxe de marcación, e que é unha linguaxe de marcación é

1060
01:04:05,950 --> 01:04:10,220
é esta serie de soportes abertos e pechados soportes que din "facer este bold '

1061
01:04:10,220 --> 01:04:12,000
"Facer esta cursiva" "facer esta centrada."

1062
01:04:12,000 --> 01:04:14,250
Non é todo o que intelectualmente interesante, pero é super útil.

1063
01:04:14,250 --> 01:04:16,650
E é certamente omnipresente nos días de hoxe.

1064
01:04:16,650 --> 01:04:19,450
Pero o que é poderoso sobre o mundo do HTML e programación web en xeral,

1065
01:04:19,450 --> 01:04:25,910
constrúe cousas dinámicas; escribir código en linguaxes como PHP ou Python ou Ruby ou Java ou C #.

1066
01:04:25,910 --> 01:04:30,360
Realmente, calquera que sexa o idioma da súa elección, e xerar HTML dinamicamente.

1067
01:04:30,360 --> 01:04:32,960
Xerando unha cousa chamada CSS dinamicamente.

1068
01:04:32,960 --> 01:04:35,810
Follas de estilo en cascada, o que é tamén sobre a estética.

1069
01:04:35,810 --> 01:04:41,360
E por iso mesmo que, hoxe, se eu for a algún sitio como o Google.com familiar,

1070
01:04:41,360 --> 01:04:46,100
e vou ver, creador, fonte de visión, que talvez teña feito antes,

1071
01:04:46,100 --> 01:04:49,800
pero vai ver o código fonte, este material probablemente parece moi enigmática.

1072
01:04:49,800 --> 01:04:55,320
Pero este é o código subxacente que aplica Google.com.

1073
01:04:55,320 --> 01:04:57,940
No extremo dianteira. E, de feito, todo isto é cousa de estética gordo.

1074
01:04:57,940 --> 01:05:01,740
Este é CSS aquí. Se eu continuar a rolagem para abaixo imos incorporarse algunhas cousas con código de cores.

1075
01:05:01,740 --> 01:05:06,890
Este é HTML. Código de Google parece unha desorde, pero realmente abrir unha xanela distinta,

1076
01:05:06,890 --> 01:05:09,380
podemos ver algunha estrutura para iso.

1077
01:05:09,380 --> 01:05:12,640
Se eu abrir isto, observe aquí, é un pouco máis lexible.

1078
01:05:12,640 --> 01:05:16,850
Nós imos ver en pouco tempo esa marca, [palabra] é unha etiqueta,

1079
01:05:16,850 --> 01:05:23,520
HTML, cabeza, corpo, div, guión, área de texto, extensión, centrado, div.

1080
01:05:23,520 --> 01:05:26,770
E esta é tamén clasificar de aparencia enigmática, a primeira vista,

1081
01:05:26,770 --> 01:05:30,890
pero toda esta confusión segue certos patróns e normas repetitivos,

1082
01:05:30,890 --> 01:05:33,850
de modo que unha vez que temos o básico para abaixo, vai ser capaz de escribir un código coma este

1083
01:05:33,850 --> 01:05:37,550
e, entón, manipular o código como esta usando outra linguaxe, chamada de JavaScript.

1084
01:05:37,550 --> 01:05:40,440
E JavaScript é unha linguaxe que roda dentro dun navegador

1085
01:05:40,440 --> 01:05:44,380
hoxe, que usan en Harvard cursos, a ferramenta de compras curso que usa mapas de Google

1086
01:05:44,380 --> 01:05:48,660
para darlle unha morea de dinamismo, Facebook ofrece a vostede para amosar actualizacións de estado instantánea,

1087
01:05:48,660 --> 01:05:51,430
Twitter usa para amosar o tweets instantaneamente.

1088
01:05:51,430 --> 01:05:53,820
Todo iso, imos comezar a mergullo dentro

1089
01:05:53,820 --> 01:05:57,190
Pero para chegar alí, necesitamos entender un pouco sobre a Internet.

1090
01:05:57,190 --> 01:06:01,130
Este clip aquí é só un minuto de duración, e imos asumir por agora este é, de feito,

1091
01:06:01,130 --> 01:06:08,380
como a Internet funciona como un teaser para o que está por vir. Eu darlle "Guerreiros do líquido."

1092
01:06:08,380 --> 01:06:14,720
>> [♫ ♫ música lenta coro]

1093
01:06:14,720 --> 01:06:20,450
[Narrador Masculino] El veu con unha mensaxe.

1094
01:06:20,450 --> 01:06:23,770
Con un protocolo de todo o seu.

1095
01:06:23,770 --> 01:06:37,270
[♫ ♫ música Faster electrónico]

1096
01:06:37,270 --> 01:06:41,330
El veu para un mundo de firewalls frías, insensibles routers,

1097
01:06:41,330 --> 01:06:45,690
e perigos moito peores que a morte.

1098
01:06:45,690 --> 01:06:55,400
El é rápido. El é forte. El é o TCP / IP, e ten o seu enderezo.

1099
01:06:55,400 --> 01:06:59,250
Guerreiros da rede.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Na próxima semana, entón. Internet. Programación web. Este é CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]