1
00:00:00,000 --> 00:00:03,381
>> [Jouer de la musique]

2
00:00:03,381 --> 00:00:10,626

3
00:00:10,626 --> 00:00:11,610
>> [LECTURE VIDÉO]

4
00:00:11,610 --> 00:00:13,640
>> -Il ment.

5
00:00:13,640 --> 00:00:14,380
>> -Sur quoi?

6
00:00:14,380 --> 00:00:17,182
>> -Je ne sais pas.

7
00:00:17,182 --> 00:00:19,990
>> -Alors Que savons-nous?

8
00:00:19,990 --> 00:00:23,145
>> -Que À 9:15, Ray
Santoya était au guichet automatique.

9
00:00:23,145 --> 00:00:23,644
-Ouais.

10
00:00:23,644 --> 00:00:27,030
Donc la question est, ce qui
faisait-il à 09h16?

11
00:00:27,030 --> 00:00:29,720
>> -Shooting Millimètre 9 à quelque chose.

12
00:00:29,720 --> 00:00:31,540
Peut-être qu'il a vu le tireur d'élite.

13
00:00:31,540 --> 00:00:33,412
>> -Ou Travaillait avec lui.

14
00:00:33,412 --> 00:00:34,340
>> -Attendez.

15
00:00:34,340 --> 00:00:36,200
Retour d'un.

16
00:00:36,200 --> 00:00:36,975
>> -Que vois-tu?

17
00:00:36,975 --> 00:00:44,400

18
00:00:44,400 --> 00:00:47,805
>> -Amener Son visage jusqu'à plein écran.

19
00:00:47,805 --> 00:00:48,680
>> -Son Verres.

20
00:00:48,680 --> 00:00:50,060
>> -Il Ya une réflexion.

21
00:00:50,060 --> 00:01:00,455

22
00:01:00,455 --> 00:01:02,280
>> -C'est L'équipe de baseball Nuevitas.

23
00:01:02,280 --> 00:01:03,110
Voilà leur logo.

24
00:01:03,110 --> 00:01:05,820
>> -Et Il parle
celui qui est vêtu cette veste.

25
00:01:05,820 --> 00:01:06,670
>> [FIN LECTURE]

26
00:01:06,670 --> 00:01:07,628
>> DAVID MALAN: Très bien.

27
00:01:07,628 --> 00:01:11,210
Ceci est CS50 ce qui est un peu plus
de [inaudible] avec lequel vous êtes

28
00:01:11,210 --> 00:01:12,890
barboteurs avec le problème fixé quatre.

29
00:01:12,890 --> 00:01:16,606
Aujourd'hui, nous commençons à regarder un peu plus
profondément à ces choses appelées pointeurs,

30
00:01:16,606 --> 00:01:18,480
qui, même si elle est
un sujet très mystérieux,

31
00:01:18,480 --> 00:01:20,813
il se trouve que ça va
être les moyens par lesquels on

32
00:01:20,813 --> 00:01:24,320
peut commencer à construire et montage
programmes beaucoup plus sophistiqués.

33
00:01:24,320 --> 00:01:28,150
Mais nous l'avons fait mercredi dernier
par le biais de certains claymation premier.

34
00:01:28,150 --> 00:01:30,190
Donc cela, rappel, est
Binky et nous lui avons utilisé

35
00:01:30,190 --> 00:01:33,148
à jeter un oeil à un programme qui
n'a pas vraiment faire quelque chose d'intéressant,

36
00:01:33,148 --> 00:01:34,950
mais il a fait apparaître quelques problèmes.

37
00:01:34,950 --> 00:01:38,570
Donc, pour commencer aujourd'hui, pourquoi ne nous marchons pas
rapidement à travers quelques-uns de ces étapes,

38
00:01:38,570 --> 00:01:41,920
essayer de distiller dans les termes de droits
exactement ce qui se passe ici

39
00:01:41,920 --> 00:01:45,410
et pourquoi cela est mauvais, et puis passer
et réellement commencer à construire quelque chose

40
00:01:45,410 --> 00:01:46,309
avec cette technique?

41
00:01:46,309 --> 00:01:48,350
Voilà donc la première
deux lignes dans ce programme

42
00:01:48,350 --> 00:01:51,340
et en termes simples, ce qui
ces deux lignes sont en train de faire?

43
00:01:51,340 --> 00:01:55,600
Quelqu'un qui est assez confortable
avec ce qui est déclaré sur l'écran?

44
00:01:55,600 --> 00:01:58,340

45
00:01:58,340 --> 00:02:00,120
Quels sont ces deux lignes qui font?

46
00:02:00,120 --> 00:02:02,070
Il est pas tout à fait
différente de la première semaine,

47
00:02:02,070 --> 00:02:03,611
mais il ya un nouveau symbole spécial.

48
00:02:03,611 --> 00:02:04,152
Ouais?

49
00:02:04,152 --> 00:02:05,628
Là-bas.

50
00:02:05,628 --> 00:02:07,092
>> AUDIENCE: Déclarer pointeurs?

51
00:02:07,092 --> 00:02:08,050
DAVID MALAN: Dites à nouveau?

52
00:02:08,050 --> 00:02:08,860
AUDIENCE: Déclarer pointeurs?

53
00:02:08,860 --> 00:02:11,776
DAVID MALAN: pointeurs déclarer et
nous allons l'affiner un peu plus.

54
00:02:11,776 --> 00:02:14,050
AUDIENCE: [inaudible]
Adresse x puis y.

55
00:02:14,050 --> 00:02:15,300
DAVID MALAN: Et puis répondre.

56
00:02:15,300 --> 00:02:18,550
Donc exactement ce que nous faisons
est nous déclarons deux variables.

57
00:02:18,550 --> 00:02:21,252
Ces variables, cependant, vont
être des étoiles de type int, qui

58
00:02:21,252 --> 00:02:23,210
plus précisément des moyens
ils vont stocker

59
00:02:23,210 --> 00:02:26,450
l'adresse d'un int,
respectivement, x et y.

60
00:02:26,450 --> 00:02:27,660
Maintenant, y at-il des valeurs?

61
00:02:27,660 --> 00:02:32,621
Y at-il des adresses réelles dans ces
deux variables à ce point dans le temps?

62
00:02:32,621 --> 00:02:33,120
Non.

63
00:02:33,120 --> 00:02:35,030
Il est juste que l'on appelle des valeurs parasites.

64
00:02:35,030 --> 00:02:38,120
Si vous ne donnez pas de fait
variables, ce qui était dans la mémoire RAM

65
00:02:38,120 --> 00:02:42,224
précédemment va remplir avec des zéros
et les deux de ces variables.

66
00:02:42,224 --> 00:02:44,140
Mais nous ne savons pas encore
ce qu'ils sont et ce est

67
00:02:44,140 --> 00:02:47,060
va être la clé pour expliquer pourquoi Binky
perdu la tête la semaine dernière.

68
00:02:47,060 --> 00:02:49,980
>> Donc, ce fut la pâte à modeler
incarnation de cette

69
00:02:49,980 --> 00:02:53,580
par lequel vous avez seulement deux des variables,
petites pièces circulaires d'argile,

70
00:02:53,580 --> 00:02:57,330
qui peut stocker des variables, mais comme
les flèches enveloppées suggèrent,

71
00:02:57,330 --> 00:03:00,640
ils ne sont pas réellement pointant
partout connue en soi.

72
00:03:00,640 --> 00:03:03,670
Alors nous avons eu cette ligne, et ce
était nouveau la semaine dernière, malloc pour la mémoire

73
00:03:03,670 --> 00:03:07,130
l'allocation, qui est juste une façon élégante
de dire le système d'exploitation, Linux

74
00:03:07,130 --> 00:03:09,750
ou Mac OS ou Windows,
hey, donnez-moi un peu de mémoire,

75
00:03:09,750 --> 00:03:11,780
et tout ce que vous avez à dire
le système d'exploitation

76
00:03:11,780 --> 00:03:14,699
est ce que lorsque vous demandez pour la mémoire.

77
00:03:14,699 --> 00:03:16,990
Il ne va pas se soucier de ce
vous allez faire avec elle,

78
00:03:16,990 --> 00:03:19,786
mais vous ne devez dire à l'exploitation
ce système par le biais de malloc.

79
00:03:19,786 --> 00:03:20,286
Ouais?

80
00:03:20,286 --> 00:03:21,078
>> Public: Combien?

81
00:03:21,078 --> 00:03:21,994
DAVID MALAN: Combien?

82
00:03:21,994 --> 00:03:25,280
Combien en octets, et ainsi, cela, encore une fois,
un exemple artificiel, est en train de dire,

83
00:03:25,280 --> 00:03:27,360
me donner la taille d'un int.

84
00:03:27,360 --> 00:03:30,550
Or, la taille d'un int
est quatre octets ou 32 bits.

85
00:03:30,550 --> 00:03:32,850
Donc, cela est juste une façon de
dire, hey, système d'exploitation,

86
00:03:32,850 --> 00:03:37,290
me donner quatre octets de mémoire
que je peux utiliser à ma disposition,

87
00:03:37,290 --> 00:03:40,560
et plus précisément, qu'est-ce que
retour malloc par rapport

88
00:03:40,560 --> 00:03:41,795
à ce morceau de quatre octets?

89
00:03:41,795 --> 00:03:44,110

90
00:03:44,110 --> 00:03:44,860
AUDIENCE: adresse?

91
00:03:44,860 --> 00:03:45,901
DAVID MALAN: L'adresse.

92
00:03:45,901 --> 00:03:47,580
L'adresse de ce morceau de quatre octets.

93
00:03:47,580 --> 00:03:48,190
Exactement.

94
00:03:48,190 --> 00:03:51,430
Et voilà ce qui est stocké en fin de compte
en x et qui est pourquoi nous faisons pas vraiment

95
00:03:51,430 --> 00:03:55,240
soucier de ce que le nombre de
adresse, si elle est OX1 ou ox2

96
00:03:55,240 --> 00:03:57,110
ou une adresse hexadécimale cryptique.

97
00:03:57,110 --> 00:03:59,850
Nous nous soucions peu imagée
que cette variable x est maintenant

98
00:03:59,850 --> 00:04:01,630
pointant vers ce bloc de mémoire.

99
00:04:01,630 --> 00:04:05,570
Donc, la flèche représente un pointeur, ou
plus précisément, une adresse de mémoire.

100
00:04:05,570 --> 00:04:09,120
Mais encore une fois, nous ne nous soucions pas habituellement
ce sont les adresses réelles.

101
00:04:09,120 --> 00:04:11,780
Maintenant, cette ligne indique
ce qui en termes simples?

102
00:04:11,780 --> 00:04:14,330
Étoile obtient 42 x virgule.

103
00:04:14,330 --> 00:04:17,390
Qu'est-ce que cela signifie?

104
00:04:17,390 --> 00:04:18,200
Tu veux partir?

105
00:04:18,200 --> 00:04:20,102
Ne pas rayer votre cou.

106
00:04:20,102 --> 00:04:22,360
>> PUBLIC: L'adresse de x est au 42.

107
00:04:22,360 --> 00:04:24,300
>> DAVID MALAN: L'adresse de x est à 42.

108
00:04:24,300 --> 00:04:25,190
Pas assez.

109
00:04:25,190 --> 00:04:28,485
Si près, mais pas tout à fait, car il ya
l'étoile qui est précéder cette x.

110
00:04:28,485 --> 00:04:29,860
Nous avons donc besoin de tordre un peu.

111
00:04:29,860 --> 00:04:31,032
Ouais?

112
00:04:31,032 --> 00:04:36,044
>> PUBLIC: La valeur que le
pointeur x pointe vers est 42.

113
00:04:36,044 --> 00:04:36,710
DAVID MALAN: OK.

114
00:04:36,710 --> 00:04:40,840
La valeur que le pointeur x est
pointant vers, disons, doit être 42,

115
00:04:40,840 --> 00:04:44,165
ou, autrement dit, la star
x dit, aller à quelque adresse

116
00:04:44,165 --> 00:04:48,340
est en x, que ce soit 1 Oxford
Street ou 33 Oxford Street

117
00:04:48,340 --> 00:04:51,850
ou OX1 ou OX33, quel que soit
cette adresse numérique est,

118
00:04:51,850 --> 00:04:54,380
star du x est le déréférencement de x.

119
00:04:54,380 --> 00:04:57,297
Alors, allez à cette adresse et
puis mettre le numéro 42 il.

120
00:04:57,297 --> 00:04:59,380
Donc, ce serait une
de façon équivalente de dire que.

121
00:04:59,380 --> 00:05:01,860
Voilà donc tout va bien puis
nous représenter l'image

122
00:05:01,860 --> 00:05:05,370
comme suit où nous avons ajouté
42 à la partie de quatre que

123
00:05:05,370 --> 00:05:09,370
octets sur le côté droit, mais
cette ligne était où les choses ont mal tourné

124
00:05:09,370 --> 00:05:11,120
et la tête de Binky sauté
descendre à ce point,

125
00:05:11,120 --> 00:05:15,290
parce que de mauvaises choses arrivent quand
vous déréférencer des valeurs parasites

126
00:05:15,290 --> 00:05:18,210
ou vous déréférencer invalide
pointeurs, et je dis non valide

127
00:05:18,210 --> 00:05:21,020
car à ce stade dans le
histoire, ce qui est à l'intérieur de y?

128
00:05:21,020 --> 00:05:24,440
Quelle est la valeur de y en fonction
sur les dernières étapes?

129
00:05:24,440 --> 00:05:25,360
Ouais?

130
00:05:25,360 --> 00:05:26,115
Qu'est ce que c'est?

131
00:05:26,115 --> 00:05:26,990
>> PUBLIC: Une adresse.

132
00:05:26,990 --> 00:05:28,460
DAVID MALAN: Une adresse.

133
00:05:28,460 --> 00:05:31,910
Il devrait être une adresse
mais ai-je initialisé il?

134
00:05:31,910 --> 00:05:32,800
Je dois donc pas encore.

135
00:05:32,800 --> 00:05:35,430
Donc ce qui est connu pour être là-dedans?

136
00:05:35,430 --> 00:05:37,590
Il est juste une certaine valeur d'ordures.

137
00:05:37,590 --> 00:05:41,500
Il pourrait être une adresse de zéro à
2 milliards si vous avez deux concerts de RAM,

138
00:05:41,500 --> 00:05:44,289
ou zéro à 4 milliards d'euros si vous avez
obtenu quatre gigaoctets de RAM.

139
00:05:44,289 --> 00:05:46,080
Il est une valeur d'ordures,
mais le problème est

140
00:05:46,080 --> 00:05:48,200
que le système d'exploitation,
si elle ne vous a pas donné

141
00:05:48,200 --> 00:05:51,140
ce morceau de mémoire spécifiquement
que vous essayez d'aller à,

142
00:05:51,140 --> 00:05:54,650
il est généralement va causer ce
nous avons vu comme un défaut de segmentation.

143
00:05:54,650 --> 00:05:57,810
Donc, en fait, aucun d'entre vous qui ont
lutté à problèmes aux heures de bureau

144
00:05:57,810 --> 00:06:00,393
ou des problèmes qui est plus
généralement à essayer de comprendre

145
00:06:00,393 --> 00:06:02,150
une erreur de segmentation,
cela signifie généralement

146
00:06:02,150 --> 00:06:05,017
vous touchez un segment de
mémoire que vous ne devriez pas être.

147
00:06:05,017 --> 00:06:07,350
Vous mémoire toucher que
le système d'exploitation n'a pas

148
00:06:07,350 --> 00:06:10,450
vous a permis de toucher, que ce soit
en allant trop loin dans votre tableau

149
00:06:10,450 --> 00:06:12,870
ou à partir de maintenant, si
il est parce que vous touchez

150
00:06:12,870 --> 00:06:14,780
mémoire qui est juste une certaine valeur d'ordures.

151
00:06:14,780 --> 00:06:18,230
>> Ce faisant, star du x est ici
genre de comportement indéfini.

152
00:06:18,230 --> 00:06:22,030
Vous ne devriez jamais le faire parce que les cotes
sont, le programme va juste pour dormir,

153
00:06:22,030 --> 00:06:24,050
parce que vous dites,
aller à cette adresse

154
00:06:24,050 --> 00:06:27,000
et vous avez aucune idée où
cette adresse est réellement.

155
00:06:27,000 --> 00:06:30,300
Ainsi, le système d'exploitation est susceptible
va crasher votre programme

156
00:06:30,300 --> 00:06:33,840
à la suite et, en fait, que ce
ce qui est arrivé à Binky.

157
00:06:33,840 --> 00:06:37,210
En fin de compte, Binky fixé
ce problème avec cela.

158
00:06:37,210 --> 00:06:38,909
Alors que le programme lui-même était viciée.

159
00:06:38,909 --> 00:06:41,450
Mais si vous sorte d'aller de l'avant
et d'exécuter cette ligne à la place,

160
00:06:41,450 --> 00:06:45,580
y est égal à x signifie simplement ce que
Adresse est un x, aussi le mettre en y.

161
00:06:45,580 --> 00:06:48,740
>> Et si imagée, nous avons
cet représenté avec deux flèches

162
00:06:48,740 --> 00:06:51,570
à partir de x et de y pointage
à la même place.

163
00:06:51,570 --> 00:06:55,760
Donc, sémantiquement, x est égal
à y parce que ces deux

164
00:06:55,760 --> 00:07:00,300
sont le stockage de la même
adresse, ergo pointant à 42,

165
00:07:00,300 --> 00:07:04,910
et maintenant, quand vous dites étoiles
y, allez à l'adresse en y,

166
00:07:04,910 --> 00:07:06,790
cela a un effet secondaire intéressant.

167
00:07:06,790 --> 00:07:10,320
Donc, l'adresse dans l'est y
même chose que l'adresse en x.

168
00:07:10,320 --> 00:07:15,060
Donc, si vous dites aller à l'adresse
en y et modifiez la valeur à 13,

169
00:07:15,060 --> 00:07:17,140
Qui d'autre est concerné?

170
00:07:17,140 --> 00:07:21,100
X est, point D, pour ainsi dire,
devraient être affectés ainsi.

171
00:07:21,100 --> 00:07:24,340
>> Et en effet, comment Nick a attiré cette image
en pâte à modeler était exactement cela.

172
00:07:24,340 --> 00:07:28,665
Même si nous suivons le pointeur
y, nous avons fini à la même place,

173
00:07:28,665 --> 00:07:32,780
et si nous étions à imprimer
à x ou y de l'pointée,

174
00:07:32,780 --> 00:07:35,720
nous verrions alors la valeur de 13.

175
00:07:35,720 --> 00:07:37,927
Maintenant, je dis à être pointée
compatible avec la vidéo.

176
00:07:37,927 --> 00:07:39,760
Programmeurs, à mon
connaissance, jamais réellement

177
00:07:39,760 --> 00:07:42,460
dire le mot pointée,
ce qui est pointu

178
00:07:42,460 --> 00:07:44,650
à, mais par souci de cohérence
avec la vidéo, réaliser

179
00:07:44,650 --> 00:07:47,520
qui est tout ce qui était
signifie dans cette situation.

180
00:07:47,520 --> 00:07:54,190
Donc, des questions sur claymation
ou des pointeurs ou malloc pour l'instant?

181
00:07:54,190 --> 00:07:54,850
Non?

182
00:07:54,850 --> 00:07:55,470
Bien.

183
00:07:55,470 --> 00:07:58,560
>> Alors sans plus
tarder, nous allons jeter un coup d'oeil

184
00:07:58,560 --> 00:08:00,700
à où cela a effectivement
été utilisé pendant un certain temps.

185
00:08:00,700 --> 00:08:03,580
Donc, nous avons eu cette bibliothèque CS50
qui a obtenu toutes ces fonctions.

186
00:08:03,580 --> 00:08:06,810
Nous avons utilisé getint beaucoup, GetString,
sans doute plus tôt GetLongLong

187
00:08:06,810 --> 00:08:09,840
dans mon PSet un ou deux, mais
ce qui est réellement été en cours?

188
00:08:09,840 --> 00:08:12,920
Eh bien, nous allons jeter un coup d'œil
sous le capot à un programme qui

189
00:08:12,920 --> 00:08:17,017
inspire pourquoi nous vous donnons la CS50
bibliothèque, et même la semaine dernière,

190
00:08:17,017 --> 00:08:18,850
nous avons commencé à prendre les
roues de formation au large.

191
00:08:18,850 --> 00:08:21,080
Donc, cela est maintenant triée
d'un post-mortem de ce que

192
00:08:21,080 --> 00:08:23,690
a été en cours
intérieur de la bibliothèque CS50,

193
00:08:23,690 --> 00:08:27,250
même si nous allons maintenant commencer à bouger
loin de la plupart des programmes.

194
00:08:27,250 --> 00:08:29,460
>> Alors ceci est un programme appelé scanf 0.

195
00:08:29,460 --> 00:08:30,510
Il est super court.

196
00:08:30,510 --> 00:08:33,909
Il a juste ces lignes, mais il
introduit une fonction appelée scanf

197
00:08:33,909 --> 00:08:36,909
que nous allons vraiment voir dans
un moment à l'intérieur de la bibliothèque CS50,

198
00:08:36,909 --> 00:08:38,600
quoique sous une forme légèrement différente.

199
00:08:38,600 --> 00:08:41,330
Donc, ce programme sur la ligne 16
est une variable x déclarant.

200
00:08:41,330 --> 00:08:43,150
Donc me donner quatre octets pour un int.

201
00:08:43,150 --> 00:08:45,750
Il a été dit utilisateur,
Numéro s'il vous plaît, et ensuite

202
00:08:45,750 --> 00:08:49,010
ceci est une piste intéressante que
cravates fait ensemble la semaine dernière

203
00:08:49,010 --> 00:08:49,790
et ça.

204
00:08:49,790 --> 00:08:53,230
Scanf, puis il faut un avis
chaîne de format, tout comme printf,

205
00:08:53,230 --> 00:08:57,480
% i signifie un int, et puis il prend une
Le deuxième argument qui ressemble un peu

206
00:08:57,480 --> 00:08:58,260
funky.

207
00:08:58,260 --> 00:09:01,880
Il est esperluette x, et de rappeler,
nous ne avons vu cette semaine, une fois dernière.

208
00:09:01,880 --> 00:09:03,465
Qu'est-ce que esperluette x représente?

209
00:09:03,465 --> 00:09:06,210

210
00:09:06,210 --> 00:09:08,450
Qu'est-ce que esperluette faire en C?

211
00:09:08,450 --> 00:09:08,950
Ouais?

212
00:09:08,950 --> 00:09:10,024
>> PUBLIC: L'adresse de la.

213
00:09:10,024 --> 00:09:11,190
DAVID MALAN: L'adresse de la.

214
00:09:11,190 --> 00:09:13,190
Il est donc à l'opposé
de l'opérateur étoiles,

215
00:09:13,190 --> 00:09:17,270
tandis que l'opérateur star dit, aller à
cette adresse, l'opérateur esperluette

216
00:09:17,270 --> 00:09:20,280
dit, comprendre la
Adresse de cette variable,

217
00:09:20,280 --> 00:09:23,530
et si cela est essentiel, parce
Le but de scanf dans la vie

218
00:09:23,530 --> 00:09:26,320
est de numériser l'utilisateur de
entrée à partir du clavier,

219
00:09:26,320 --> 00:09:29,970
en fonction de ce qu'il ou elle
types, puis lisez l'entrée de cet utilisateur

220
00:09:29,970 --> 00:09:32,970
dans une variable, mais nous
vu dans les deux dernières semaines

221
00:09:32,970 --> 00:09:36,080
que cette fonction d'échange que nous
essayé effort pour mettre en œuvre

222
00:09:36,080 --> 00:09:37,110
a été juste de rompre.

223
00:09:37,110 --> 00:09:42,470
Rappelons que la fonction d'échange,
si nous vient de déclarer A et B comme ints,

224
00:09:42,470 --> 00:09:47,040
nous ne échangeons avec succès le
deux variables à l'intérieur d'échange

225
00:09:47,040 --> 00:09:50,080
Tout comme avec le lait et JO,
mais dès que swaps retourné,

226
00:09:50,080 --> 00:09:55,200
ce qui était le résultat en ce qui concerne
pour x et y, les valeurs d'origine?

227
00:09:55,200 --> 00:09:55,700
Rien.

228
00:09:55,700 --> 00:09:56,200
Ouais.

229
00:09:56,200 --> 00:09:59,754
Rien ne se passa ce moment-là, parce
swaps changent seulement ses copies locales,

230
00:09:59,754 --> 00:10:01,670
qui est-à-dire, tous les
cette fois, chaque fois que nous avons

231
00:10:01,670 --> 00:10:04,010
été en passant arguments
à des fonctions, nous sommes

232
00:10:04,010 --> 00:10:05,939
juste de passage des copies de ces arguments.

233
00:10:05,939 --> 00:10:07,980
Vous pouvez le faire avec cette
ce que vous voulez avec eux,

234
00:10:07,980 --> 00:10:10,890
mais ils vont avoir pas
effet sur les valeurs d'origine.

235
00:10:10,890 --> 00:10:13,650
Donc, ce qui est problématique si vous
veulent avoir une fonction comme scanf

236
00:10:13,650 --> 00:10:17,170
dans la vie, dont le but est de scanner
l'entrée de l'utilisateur à partir du clavier

237
00:10:17,170 --> 00:10:22,010
puis remplir les blancs, pour ainsi
parler, qui est, lui donner une variable comme x

238
00:10:22,010 --> 00:10:25,410
une valeur, parce que si je devais
juste passer x à Scanf,

239
00:10:25,410 --> 00:10:28,790
si vous considérez la logique de la dernière
semaine, scanf peut faire ce qu'il veut

240
00:10:28,790 --> 00:10:33,100
une copie de x, mais il ne pouvait pas
changer de façon permanente x moins que nous donnions

241
00:10:33,100 --> 00:10:37,120
Scanf une carte au trésor, pour ainsi dire,
où x marque l'endroit, de sorte que

242
00:10:37,120 --> 00:10:41,860
nous passons à l'adresse de x sorte que
scanf peut y aller et effectivement le changement

243
00:10:41,860 --> 00:10:42,920
la valeur de x.

244
00:10:42,920 --> 00:10:45,080
Et en effet, tous les
que ce programme ne

245
00:10:45,080 --> 00:10:53,180
si je fais scanf 0, dans ma source
Répertoire 5m, faire scanf 0,

246
00:10:53,180 --> 00:10:57,730
dot slash scanf, numéro
s'il vous plaît 50, merci pour le 50.

247
00:10:57,730 --> 00:11:01,020
>> Donc, il est pas tout à fait intéressant,
mais ce qui se passe en effet

248
00:11:01,020 --> 00:11:04,820
est que dès que je l'appelle
Scanf ici, la valeur de x

249
00:11:04,820 --> 00:11:06,410
est modifié de façon permanente.

250
00:11:06,410 --> 00:11:08,335
Maintenant, cela semble agréable et
bon, et, en fait, il

251
00:11:08,335 --> 00:11:11,200
semble que nous ne devons pas vraiment
la bibliothèque de CS50 plus du tout.

252
00:11:11,200 --> 00:11:13,960
Par exemple, on devrait courir
cette fois de plus ici.

253
00:11:13,960 --> 00:11:15,750
Permettez-moi de rouvrir pour une deuxième.

254
00:11:15,750 --> 00:11:20,600
Essayons un certain nombre et s'il vous plaît
au lieu de dire 50 comme avant,

255
00:11:20,600 --> 00:11:22,810
disons simplement pas.

256
00:11:22,810 --> 00:11:24,000
OK, qui est un peu bizarre.

257
00:11:24,000 --> 00:11:25,270
D'ACCORD.

258
00:11:25,270 --> 00:11:28,680
Et juste des bêtises ici.

259
00:11:28,680 --> 00:11:31,170
Donc, il ne semble pas
gérer des situations erronées.

260
00:11:31,170 --> 00:11:33,620
Nous devons donc minimalement début
ajoutant un peu de contrôle d'erreur

261
00:11:33,620 --> 00:11:37,460
veiller à ce que l'utilisateur a
tapé dans un nombre réel comme 50,

262
00:11:37,460 --> 00:11:40,720
parce que les mots apparemment taper
est pas détecté comme étant problématique,

263
00:11:40,720 --> 00:11:42,020
mais il devrait probablement être.

264
00:11:42,020 --> 00:11:46,450
>> Regardons cette version maintenant que ce
ma tentative de réimplémentons GetString.

265
00:11:46,450 --> 00:11:48,437
Si tout cela a scanf
fonctionnalité intégrée,

266
00:11:48,437 --> 00:11:51,270
Pourquoi avons-nous été barboteurs avec ces
roues de formation comme GetString?

267
00:11:51,270 --> 00:11:55,450
Eh bien, ici est peut-être mon propre
version simple de GetString

268
00:11:55,450 --> 00:12:00,766
dans lequel il ya une semaine, je pourrais l'ai dit,
me donner une chaîne et l'appeler tampon.

269
00:12:00,766 --> 00:12:03,390
Aujourd'hui, je vais commencer tout
disant star de char, qui, rappelons,

270
00:12:03,390 --> 00:12:04,400
il est juste aussi.

271
00:12:04,400 --> 00:12:06,629
Il semble effrayant, mais il est
exactement la même chose.

272
00:12:06,629 --> 00:12:09,420
Donc, me donner un tampon variable appelée
cela va de stocker une chaîne,

273
00:12:09,420 --> 00:12:12,780
dire la chaîne de l'utilisateur s'il vous plaît,
puis, comme avant,

274
00:12:12,780 --> 00:12:17,760
Essayons d'emprunter cette leçon scanf
% s cette fois et ensuite passer dans un tampon.

275
00:12:17,760 --> 00:12:19,310
Maintenant, un test de cohérence rapide.

276
00:12:19,310 --> 00:12:22,120
Pourquoi suis-je ne dis pas
esperluette tampon, cette fois?

277
00:12:22,120 --> 00:12:25,190

278
00:12:25,190 --> 00:12:26,625
Déduire de l'exemple précédent.

279
00:12:26,625 --> 00:12:28,000
AUDIENCE: Char étoiles est un pointeur.

280
00:12:28,000 --> 00:12:29,920
DAVID MALAN: Exactement,
parce que cette fois, char

281
00:12:29,920 --> 00:12:34,080
étoiles est déjà un pointeur, une adresse,
par définition de cette étoile d'être là.

282
00:12:34,080 --> 00:12:37,530
Et si scanf attend une adresse,
il suffit juste de passer dans un tampon.

283
00:12:37,530 --> 00:12:39,260
Je ne veux pas dire tampon de esperluette.

284
00:12:39,260 --> 00:12:42,177
Pour les curieux, vous pourriez
faire quelque chose comme ça.

285
00:12:42,177 --> 00:12:43,510
Il aurait sens différent.

286
00:12:43,510 --> 00:12:47,240
Cela vous donne un pointeur
à un pointeur, qui est en fait

287
00:12:47,240 --> 00:12:50,050
une chose valable dans C, mais pour
maintenant, nous allons garder les choses simples

288
00:12:50,050 --> 00:12:51,750
et de garder l'histoire cohérente.

289
00:12:51,750 --> 00:12:54,100
Je vais passer en
tampon et qui est exact.

290
00:12:54,100 --> 00:12:56,487
Le problème est que cela.

291
00:12:56,487 --> 00:12:58,820
Laissez-moi aller de l'avant et lance ce
programme après le compiler.

292
00:12:58,820 --> 00:13:00,902
Assurez scanf 1.

293
00:13:00,902 --> 00:13:02,610
Merde, mon compilateur de
attraper mon erreur.

294
00:13:02,610 --> 00:13:04,090
Donnez-moi une seconde.

295
00:13:04,090 --> 00:13:05,460
Clang.

296
00:13:05,460 --> 00:13:06,990
Disons scanf-1.c.

297
00:13:06,990 --> 00:13:10,880

298
00:13:10,880 --> 00:13:11,380
D'ACCORD.

299
00:13:11,380 --> 00:13:12,720
Nous y voilà.

300
00:13:12,720 --> 00:13:14,280
J'en ai besoin.

301
00:13:14,280 --> 00:13:16,750
CS50 ID a divers
les paramètres de configuration

302
00:13:16,750 --> 00:13:18,280
que vous protéger contre vous-même.

303
00:13:18,280 --> 00:13:21,300
Je devais désactiver celles de
courir clang manuellement cette fois.

304
00:13:21,300 --> 00:13:22,140
Alors s'il vous plaît chaîne.

305
00:13:22,140 --> 00:13:25,560
Je vais aller de l'avant et tapez
dans mon monde de bonjour favori.

306
00:13:25,560 --> 00:13:26,490
OK, null.

307
00:13:26,490 --> 00:13:27,700
Cela ne veut pas ce que je tapé.

308
00:13:27,700 --> 00:13:29,690
Donc, il est indicatif de
quelque chose de se tromper.

309
00:13:29,690 --> 00:13:33,920
Laissez-moi aller de l'avant et tape
dans une très longue chaîne.

310
00:13:33,920 --> 00:13:37,210
Merci pour le nul et je ne sais pas
si je vais être capable de crasher.

311
00:13:37,210 --> 00:13:40,240
Essayons un peu de copie
coller et voir si cela aide.

312
00:13:40,240 --> 00:13:43,290
Il suffit de coller beaucoup de cela.

313
00:13:43,290 --> 00:13:47,310
Il est certainement un plus grand
chaîne que d'habitude.

314
00:13:47,310 --> 00:13:51,450
Disons simplement vraiment écrire.

315
00:13:51,450 --> 00:13:51,950
Non.

316
00:13:51,950 --> 00:13:52,650
Bon sang.

317
00:13:52,650 --> 00:13:53,480
Commande non trouvée.

318
00:13:53,480 --> 00:13:54,550
Voilà donc sans rapport.

319
00:13:54,550 --> 00:13:56,440
Voilà parce que je collais
quelques mauvais caractères,

320
00:13:56,440 --> 00:13:59,780
mais cela se révèle ne va pas fonctionner.

321
00:13:59,780 --> 00:14:03,510
>> Essayons une fois de plus, parce
il est plus amusant si on fait crasher.

322
00:14:03,510 --> 00:14:09,116
Disons tapez cela et maintenant, je suis
aller à copier une très longue chaîne

323
00:14:09,116 --> 00:14:10,990
et maintenant nous allons voir si nous
peut faire planter cette chose.

324
00:14:10,990 --> 00:14:14,235
Remarquez que je omis espaces et
nouvelles lignes et des points-virgules

325
00:14:14,235 --> 00:14:16,035
et tous les personnages funky.

326
00:14:16,035 --> 00:14:16,535
Entrez.

327
00:14:16,535 --> 00:14:21,090

328
00:14:21,090 --> 00:14:22,880
Et maintenant, le réseau vient d'être lent.

329
00:14:22,880 --> 00:14:27,460
Je tenais la touche Commande-V trop longtemps, clairement.

330
00:14:27,460 --> 00:14:28,190
Bon sang!

331
00:14:28,190 --> 00:14:29,260
Commande non trouvée.

332
00:14:29,260 --> 00:14:29,780
>> D'ACCORD.

333
00:14:29,780 --> 00:14:32,240
Eh bien, le point est
néanmoins la suivante.

334
00:14:32,240 --> 00:14:36,910
Alors qu'est-ce qui se passe réellement
avec cette déclaration

335
00:14:36,910 --> 00:14:39,240
de char buffer étoiles sur la ligne 16?

336
00:14:39,240 --> 00:14:41,820
Alors, que suis-je obtenir
quand je déclare un pointeur?

337
00:14:41,820 --> 00:14:47,440
Tout ce que je veux en venir est une valeur de quatre octets
appelé tampon, mais ce qui est intérieur de celui-

338
00:14:47,440 --> 00:14:49,540
en ce moment?

339
00:14:49,540 --> 00:14:50,930
Il est juste une certaine valeur d'ordures.

340
00:14:50,930 --> 00:14:54,170
Parce que chaque fois que vous déclarez une variable
en C, elle est juste une certaine valeur d'ordures,

341
00:14:54,170 --> 00:14:56,220
et nous commençons à
trébucher sur cette réalité.

342
00:14:56,220 --> 00:14:59,720
Maintenant, quand je dis scanf,
aller à cette adresse

343
00:14:59,720 --> 00:15:01,520
et mettre ce que l'utilisateur tape dans.

344
00:15:01,520 --> 00:15:06,400
Si les types d'utilisateurs dans bonjour
monde, eh bien, où dois-je le mettre?

345
00:15:06,400 --> 00:15:07,750
Est une valeur tampon d'ordures.

346
00:15:07,750 --> 00:15:11,510
>> Voilà donc un peu comme une flèche
que cela pointant qui sait où.

347
00:15:11,510 --> 00:15:13,880
Peut-être il pointant
ici dans ma mémoire.

348
00:15:13,880 --> 00:15:16,560
Et donc quand l'utilisateur
types dans Bonjour tout le monde,

349
00:15:16,560 --> 00:15:22,380
le programme tente de mettre la
Bonjour tout le monde chaîne barre oblique inverse 0

350
00:15:22,380 --> 00:15:23,910
dans ce morceau de mémoire.

351
00:15:23,910 --> 00:15:27,070
Mais avec une forte probabilité, mais
clairement pas 100% de probabilité,

352
00:15:27,070 --> 00:15:30,440
l'ordinateur va alors se bloquer
le programme parce que ce ne sont pas

353
00:15:30,440 --> 00:15:32,490
souvenir que je devrais être autorisé à toucher.

354
00:15:32,490 --> 00:15:36,330
Donc en bref, ce programme est
viciée précisément pour cette raison.

355
00:15:36,330 --> 00:15:38,070
Je fondamentalement pas faire quoi?

356
00:15:38,070 --> 00:15:42,366
Quelles sont les étapes que je omis, tout comme
nous avons omis de premier exemple de Binky?

357
00:15:42,366 --> 00:15:42,866
Ouais?

358
00:15:42,866 --> 00:15:43,710
>> AUDIENCE: allocation de mémoire?

359
00:15:43,710 --> 00:15:45,001
>> DAVID MALAN: allocation de mémoire.

360
00:15:45,001 --> 00:15:48,400
Je ne suis pas réellement alloué
toute la mémoire pour cette chaîne.

361
00:15:48,400 --> 00:15:50,270
Donc, nous pouvons résoudre ce problème dans un couple des manières.

362
00:15:50,270 --> 00:15:52,700
Un, nous pouvons garder les choses simples
et en fait, maintenant vous êtes

363
00:15:52,700 --> 00:15:55,116
va commencer à voir un flou
des lignes entre ce

364
00:15:55,116 --> 00:15:58,520
un tableau est, ce qui est une chaîne, quel
omble étoiles est, ce qu'est un tableau de caractères

365
00:15:58,520 --> 00:15:59,020
est.

366
00:15:59,020 --> 00:16:02,450
Voici un deuxième exemple
impliquant cordes et avis

367
00:16:02,450 --> 00:16:05,690
tout ce que je l'ai fait en ligne
16 est, au lieu de dire

368
00:16:05,690 --> 00:16:09,530
ce tampon va être un caractère
étoiles, un pointeur vers un bloc de mémoire,

369
00:16:09,530 --> 00:16:14,057
Je vais donner très proactive
moi un tampon pour 16 caractères,

370
00:16:14,057 --> 00:16:16,390
et en fait, si vous êtes familier
avec le tampon terme,

371
00:16:16,390 --> 00:16:20,570
probablement du monde de la vidéo,
où une vidéo est mise en mémoire tampon, en mémoire tampon,

372
00:16:20,570 --> 00:16:21,175
mise en mémoire tampon.

373
00:16:21,175 --> 00:16:22,550
Eh bien, quel est le lien ici?

374
00:16:22,550 --> 00:16:24,960
Eh bien, à l'intérieur de YouTube
et à l'intérieur des lecteurs vidéo

375
00:16:24,960 --> 00:16:27,200
est généralement un tableau
qui est plus grand que 16.

376
00:16:27,200 --> 00:16:30,340
Il pourrait être un tableau de taille un
mégaoctet, peut-être 10 mégaoctets,

377
00:16:30,340 --> 00:16:34,330
et dans ce tableau ne votre navigateur
télécharger tout un tas d'octets,

378
00:16:34,330 --> 00:16:37,500
tout un tas de mégaoctets de
vidéo et le lecteur vidéo,

379
00:16:37,500 --> 00:16:40,930
De YouTube ou quiconque est, commence
lire les octets de ce tableau,

380
00:16:40,930 --> 00:16:43,530
et chaque fois que vous voyez le
mot tampon, tampon,

381
00:16:43,530 --> 00:16:46,350
cela signifie que le joueur a
arrivé à la fin de ce tableau.

382
00:16:46,350 --> 00:16:50,430
Le réseau est si lente qu'elle n'a pas
rempli le tableau avec plusieurs octets

383
00:16:50,430 --> 00:16:55,610
et vous êtes hors de bits
à afficher pour l'utilisateur.

384
00:16:55,610 --> 00:16:59,430
>> Donc tampon est un terme approprié ici à ce que
il est juste un tableau, un morceau de la mémoire.

385
00:16:59,430 --> 00:17:02,530
Et ce sera le fixer
car il se trouve

386
00:17:02,530 --> 00:17:07,410
que vous pouvez traiter les tableaux comme si
ils sont des adresses, même si le tampon

387
00:17:07,410 --> 00:17:10,710
est juste un symbole, il est un
séquence de caractères, un tampon,

388
00:17:10,710 --> 00:17:14,760
qui est utile pour moi, le programmeur,
vous pouvez passer autour de son nom

389
00:17:14,760 --> 00:17:17,079
comme si elle était une
pointeur, comme si elle

390
00:17:17,079 --> 00:17:21,000
étaient l'adresse d'un morceau
de mémoire pour 16 caractères.

391
00:17:21,000 --> 00:17:24,530
Voilà donc à dire, je peux passer
l'scanf exactement ce mot

392
00:17:24,530 --> 00:17:30,670
et maintenant, si je fais ce programme,
faire scanf 2, point barre oblique scanf 2,

393
00:17:30,670 --> 00:17:35,386
et tapez Bonjour tout le monde,
Entrée, cela time--

394
00:17:35,386 --> 00:17:37,590
>> Hmm, ce qui est arrivé?

395
00:17:37,590 --> 00:17:39,340
Chaîne s'il vous plaît.

396
00:17:39,340 --> 00:17:41,430
Qu'ai-je fait de mal?

397
00:17:41,430 --> 00:17:43,800
Bonjour tout le monde, tampon.

398
00:17:43,800 --> 00:17:44,705
Bonjour le monde.

399
00:17:44,705 --> 00:17:48,201

400
00:17:48,201 --> 00:17:49,420
Ah, je sais ce qu'il fait.

401
00:17:49,420 --> 00:17:49,920
D'ACCORD.

402
00:17:49,920 --> 00:17:51,628
Donc, il est la lecture jusqu'à
jusqu'à ce que le premier espace.

403
00:17:51,628 --> 00:17:55,680
Donc, nous allons tricher pendant un moment et
dire que je voulais juste de taper quelque chose

404
00:17:55,680 --> 00:18:01,408
vraiment long comme ceci est une longue phrase
voilà un, deux, trois, quatre, cinq,

405
00:18:01,408 --> 00:18:04,420
six, sept, huit, neuf,
10, 11, 12, 13, 14, 15, 16.

406
00:18:04,420 --> 00:18:05,300
D'ACCORD.

407
00:18:05,300 --> 00:18:07,600
Il est en effet une longue phrase.

408
00:18:07,600 --> 00:18:10,710
Donc, cette phrase est
plus de 16 caractères

409
00:18:10,710 --> 00:18:13,670
et ainsi lorsque je tape Entrée,
ce qu'il va se passer?

410
00:18:13,670 --> 00:18:16,940
Eh bien, dans ce cas de la
tampon histoire, je l'avais déclaré

411
00:18:16,940 --> 00:18:22,190
étant en fait à une matrice
avec 16 caractères prêt à aller.

412
00:18:22,190 --> 00:18:27,426
Donc, un, deux, trois, quatre, cinq, six,
sept, huit, neuf, dix, onze, douze, treize, quatorze,

413
00:18:27,426 --> 00:18:29,440
15, 16.

414
00:18:29,440 --> 00:18:34,410
Donc 16 caractères, et maintenant, quand je
lire quelque chose comme ceci est un long

415
00:18:34,410 --> 00:18:43,950
phrase, qu'est-ce qui va se passer est
que je vais lire dans ce est un long

416
00:18:43,950 --> 00:18:49,660
S-E-N-T-E-N-C-E, phrase.

417
00:18:49,660 --> 00:18:52,270
>> Donc, cela est délibérément
une mauvaise chose que je

418
00:18:52,270 --> 00:18:55,060
continuer à écrire au-delà du
limites de mon tableau,

419
00:18:55,060 --> 00:18:56,660
au-delà des limites de mon tampon.

420
00:18:56,660 --> 00:19:00,100
Je pourrais avoir de la chance et le programme
va continuer à courir et pas de soins,

421
00:19:00,100 --> 00:19:03,450
mais en général, cette
sera en effet planter mon programme,

422
00:19:03,450 --> 00:19:06,440
et il ya un bug dans mon
coder le moment je fais un pas

423
00:19:06,440 --> 00:19:08,576
au-delà des limites
de ce tableau, parce que je

424
00:19:08,576 --> 00:19:10,450
Je ne sais pas si elle est
aller nécessairement à écraser

425
00:19:10,450 --> 00:19:12,120
ou si je vais juste avoir de la chance.

426
00:19:12,120 --> 00:19:15,750
Donc, ce qui est problématique parce que dans
ce cas, il ne semble pas fonctionner

427
00:19:15,750 --> 00:19:20,931
et nous allons tenter le sort ici, même si
l'IDE semble tolérer un peu

428
00:19:20,931 --> 00:19:21,430
de--

429
00:19:21,430 --> 00:19:22,040
>> Nous y voilà.

430
00:19:22,040 --> 00:19:23,240
Finalement.

431
00:19:23,240 --> 00:19:26,470
Donc, je suis le seul qui peut voir cela.

432
00:19:26,470 --> 00:19:29,630
Donc, je viens d'avoir beaucoup de dactylographie amusant
sur une très longue phrase réelle

433
00:19:29,630 --> 00:19:32,800
que certainement dépassé
16 octets, parce que je

434
00:19:32,800 --> 00:19:38,050
tapé dans cette longue ligne multi-fou
phrase, puis notez ce qui est arrivé.

435
00:19:38,050 --> 00:19:41,110
Le programme a tenté imprimer
et puis a obtenu une erreur de segmentation

436
00:19:41,110 --> 00:19:44,430
et des erreurs de segmentation est quand
quelque chose comme cela se produit

437
00:19:44,430 --> 00:19:47,650
et le dit système d'exploitation
Non, ne peut pas toucher cette mémoire.

438
00:19:47,650 --> 00:19:49,570
Nous allons tuer
le programme tout à fait.

439
00:19:49,570 --> 00:19:51,180
>> Donc, cela semble problématique.

440
00:19:51,180 --> 00:19:54,540
Je me suis amélioré le programme en vertu duquel
au moins avoir un peu de mémoire,

441
00:19:54,540 --> 00:19:58,000
mais cela semble confiner
la fonction pour obtenir GetString

442
00:19:58,000 --> 00:20:00,780
certaines chaînes de longueur finie 16.

443
00:20:00,780 --> 00:20:04,200
Donc, si vous voulez soutenir plus
peines de 16 caractères,

444
00:20:04,200 --> 00:20:04,880
Que faire?

445
00:20:04,880 --> 00:20:07,970
Eh bien, vous pouvez augmenter la
taille de ce tampon à 32

446
00:20:07,970 --> 00:20:09,190
ou qui semble sorte de court.

447
00:20:09,190 --> 00:20:12,260
Pourquoi ne faisons pas
il 1000 mais repousser.

448
00:20:12,260 --> 00:20:17,100
Quelle est la réponse intuitivement
seulement d'éviter ce problème en faisant

449
00:20:17,100 --> 00:20:20,660
mon buffer plus grand, comme 1000 caractères?

450
00:20:20,660 --> 00:20:23,470
En mettant en œuvre GetString cette façon.

451
00:20:23,470 --> 00:20:27,130
Ce qui est bon ou mauvais ici?

452
00:20:27,130 --> 00:20:28,033
Ouais?

453
00:20:28,033 --> 00:20:30,574
Public: Si vous liez un lot
de l'espace et vous ne l'utilisez pas,

454
00:20:30,574 --> 00:20:33,500
alors vous ne pouvez pas réaffecter cet espace.

455
00:20:33,500 --> 00:20:34,500
DAVID MALAN: Absolument.

456
00:20:34,500 --> 00:20:38,480
Il est inutile dans la mesure où si vous ne le faites pas
réellement besoin de ces 900 octets

457
00:20:38,480 --> 00:20:41,057
et pourtant vous demandez
1000 au total de toute façon,

458
00:20:41,057 --> 00:20:44,140
vous êtes juste de consommer plus de mémoire sur
l'ordinateur de l'utilisateur que vous avez besoin,

459
00:20:44,140 --> 00:20:45,740
et après tout, certains de
vous avez déjà rencontré

460
00:20:45,740 --> 00:20:47,620
dans la vie que lorsque vous êtes
courir beaucoup de programmes

461
00:20:47,620 --> 00:20:50,470
et qu'ils mangent trop de mémoire,
cela peut effectivement affecter les performances

462
00:20:50,470 --> 00:20:52,220
et l'expérience de l'utilisateur
sur l'ordinateur.

463
00:20:52,220 --> 00:20:56,090
Voilà donc une sorte de solution paresseuse,
pour sûr, et inversement,

464
00:20:56,090 --> 00:21:00,140
il est non seulement inutile, ce problème
demeure, même si je fais mon mémoire tampon

465
00:21:00,140 --> 00:21:02,100
1000?

466
00:21:02,100 --> 00:21:02,600
Ouais?

467
00:21:02,600 --> 00:21:04,475
>> PUBLIC: La chaîne est de longueur 1001.

468
00:21:04,475 --> 00:21:05,350
DAVID MALAN: Exactement.

469
00:21:05,350 --> 00:21:08,280
Si votre chaîne est de longueur 1001,
vous avez exactement le même problème,

470
00:21:08,280 --> 00:21:10,705
et par mon argumentation, je le ferais
vient ensuite rendre 2000,

471
00:21:10,705 --> 00:21:12,830
mais vous ne savez pas dans
avancer la taille qu'elle devrait être,

472
00:21:12,830 --> 00:21:16,890
et pourtant, je dois compiler mon programme
avant de laisser les gens utilisent et téléchargement

473
00:21:16,890 --> 00:21:17,390
ce.

474
00:21:17,390 --> 00:21:21,490
Donc, cela est exactement le genre de
choses que la bibliothèque essais CS50

475
00:21:21,490 --> 00:21:24,750
pour nous aider avec et nous allons seulement regard
à la mise en œuvre de certaines sous-jacent

476
00:21:24,750 --> 00:21:29,790
ici, mais cela est CS50 point C. Cette
est le fichier qui a été sur CS50 IDE

477
00:21:29,790 --> 00:21:31,420
toutes ces semaines que vous avez déjà utilisé.

478
00:21:31,420 --> 00:21:34,280
Il est pré-compilé et vous avez
été en utilisant automatiquement

479
00:21:34,280 --> 00:21:38,780
par la nature de l'comportant
dash L CS50 indicateurs avec fracas,

480
00:21:38,780 --> 00:21:42,300
mais si je faire défiler tous
ces fonctions, voici GetString,

481
00:21:42,300 --> 00:21:44,636
et juste pour vous donner une
goût de ce qui se passe,

482
00:21:44,636 --> 00:21:46,760
nous allons jeter un coup d'oeil sur
la relative complexité.

483
00:21:46,760 --> 00:21:48,870
Il est pas un super long
fonction, mais on n'a pas

484
00:21:48,870 --> 00:21:52,530
avoir à réfléchir sérieusement à tous les
comment s'y prendre pour obtenir des chaînes.

485
00:21:52,530 --> 00:21:55,660
>> Alors, voici ma mémoire tampon et je
apparemment l'initialiser à NULL.

486
00:21:55,660 --> 00:21:57,990
Ceci, bien sûr, est le
même chose en tant que char étoiles,

487
00:21:57,990 --> 00:22:00,585
mais je décidai de
l'application de la bibliothèque CS50

488
00:22:00,585 --> 00:22:02,460
que si nous allons
être totalement dynamique,

489
00:22:02,460 --> 00:22:05,770
Je ne sais pas à l'avance la taille d'un
les utilisateurs de chaîne vont vouloir obtenir.

490
00:22:05,770 --> 00:22:08,140
Donc, je vais commencer
avec juste une chaîne vide

491
00:22:08,140 --> 00:22:11,507
et je vais construire autant
mémoire que je dois adapter à la chaîne de l'utilisateur

492
00:22:11,507 --> 00:22:13,340
et si je ne ai pas
assez, je vais demander à

493
00:22:13,340 --> 00:22:15,010
le système d'exploitation pour plus de mémoire.

494
00:22:15,010 --> 00:22:17,510
Je vais passer leur chaîne
dans un plus gros morceau de la mémoire

495
00:22:17,510 --> 00:22:21,847
et je vais libérer ou libérer la
insuffisamment grande partie de la mémoire

496
00:22:21,847 --> 00:22:23,680
et nous allons juste
pour ce faire de manière itérative.

497
00:22:23,680 --> 00:22:25,570
>> Ainsi, un rapide coup d'œil,
voici juste une variable

498
00:22:25,570 --> 00:22:28,780
avec laquelle je vais garder la trace
de la capacité du tampon ma.

499
00:22:28,780 --> 00:22:30,071
Combien d'octets que je peux adapter?

500
00:22:30,071 --> 00:22:32,070
Voici une variable n avec
que je vais continuer à

501
00:22:32,070 --> 00:22:36,200
trace de combien d'octets sont réellement dans
le tampon ou que l'utilisateur a saisi.

502
00:22:36,200 --> 00:22:39,900
Si vous avez pas vu cela avant, vous
peut spécifier qu'une variable comme un int

503
00:22:39,900 --> 00:22:46,370
est non signé, qui, comme son nom l'indique,
signifie qu'il est non-négatif, et pourquoi

504
00:22:46,370 --> 00:22:50,590
Je veux plus jamais à se soucier spécifiant
qu'un int est non seulement un int,

505
00:22:50,590 --> 00:22:52,540
mais il est un unsigned int?

506
00:22:52,540 --> 00:22:55,064
Il est un int non-négative.

507
00:22:55,064 --> 00:22:56,355
Qu'est-ce que le [inaudible] signifie?

508
00:22:56,355 --> 00:22:58,910
>> PUBLIC: Il est décrit une quantité
de mémoire qui peut être [inaudible].

509
00:22:58,910 --> 00:22:59,660
>> DAVID MALAN: Ouais.

510
00:22:59,660 --> 00:23:03,710
Donc, si je dis non signé, cela est effectivement
vous donnant un peu de mémoire supplémentaire

511
00:23:03,710 --> 00:23:07,440
et il semble un peu ridicule, mais si vous
avoir un peu de mémoire supplémentaire, que

512
00:23:07,440 --> 00:23:09,940
signifie que vous avez deux fois plus nombreux
valeurs que vous pouvez représenter,

513
00:23:09,940 --> 00:23:11,570
car il peut être un 0 ou un 1.

514
00:23:11,570 --> 00:23:14,660
Donc, par défaut, un int peut être à peu près
négative de 2 milliards de tout le chemin

515
00:23:14,660 --> 00:23:16,030
jusqu'à 2 milliards de positif.

516
00:23:16,030 --> 00:23:18,540
Ce sont de grandes plages, mais
il est encore un peu de gaspillage

517
00:23:18,540 --> 00:23:21,280
si vous vous souciez seulement
tailles, qui vient intuitivement

518
00:23:21,280 --> 00:23:24,620
devrait être non-négative ou
positif ou 0, eh bien,

519
00:23:24,620 --> 00:23:28,884
pourquoi êtes-vous perdez 2 milliards
valeurs possibles pour les nombres négatifs

520
00:23:28,884 --> 00:23:30,300
si vous allez jamais à les utiliser?

521
00:23:30,300 --> 00:23:35,350
Donc, en disant non signé, maintenant mon int peut
être entre 0 et environ 4 milliards.

522
00:23:35,350 --> 00:23:39,280
>> Alors, voici juste un int C pour des raisons
nous ne serons pas entrer dans ce moment que

523
00:23:39,280 --> 00:23:42,280
pourquoi il est un int place
d'un char, mais voici

524
00:23:42,280 --> 00:23:44,630
l'essentiel de ce qui se passe
sur, et certains d'entre vous

525
00:23:44,630 --> 00:23:48,340
on pourrait en utilisant, par exemple, la
fonction fgetc même dans quatre PSet

526
00:23:48,340 --> 00:23:51,580
ou par la suite, nous verrons ce
nouveau en problème posé cinq,

527
00:23:51,580 --> 00:23:55,410
fgetc est agréable parce que le nom
en quelque sorte, suggère sorte de arcanely,

528
00:23:55,410 --> 00:23:57,940
il est une fonction qui
obtient un caractère et ainsi,

529
00:23:57,940 --> 00:24:00,690
ce qui est fondamentalement différent
à propos de ce que nous faisons dans GetString

530
00:24:00,690 --> 00:24:03,110
est que nous ne sommes pas à l'aide
scanf de la même façon.

531
00:24:03,110 --> 00:24:07,550
Nous sommes juste rampant étape par étape
sur ce que l'utilisateur a tapé dans,

532
00:24:07,550 --> 00:24:10,970
parce que nous pouvons toujours allouer un
char, et ainsi nous pouvons toujours en toute sécurité

533
00:24:10,970 --> 00:24:15,599
regarder un omble à la fois, et
la magie commence à se produire ici.

534
00:24:15,599 --> 00:24:17,890
Je vais faire défiler vers le bas pour
Au milieu de cette fonction

535
00:24:17,890 --> 00:24:20,360
juste pour présenter brièvement cette fonction.

536
00:24:20,360 --> 00:24:22,670
Tout comme il ya une
fonction malloc, il est

537
00:24:22,670 --> 00:24:27,740
une fonction de realloc où realloc
vous permet de réaffecter une partie de la mémoire

538
00:24:27,740 --> 00:24:29,570
et le rendre plus grand ou plus petit.

539
00:24:29,570 --> 00:24:33,060
Tant histoire courte et
une vague de ma main pour aujourd'hui,

540
00:24:33,060 --> 00:24:35,620
savoir que ce GetString
fait est qu'il est en quelque sorte

541
00:24:35,620 --> 00:24:39,720
de magie croissance ou
retrait du tampon en tant qu'utilisateur

542
00:24:39,720 --> 00:24:41,440
types dans sa chaîne.

543
00:24:41,440 --> 00:24:43,962
>> Donc, si l'utilisateur tape une
courte chaîne, ce code

544
00:24:43,962 --> 00:24:45,920
seulement alloue assez
mémoire pour adapter la chaîne.

545
00:24:45,920 --> 00:24:48,086
Si l'utilisateur maintient le typage
comme je l'ai fait encore et encore

546
00:24:48,086 --> 00:24:50,330
et encore, eh bien, si le
tampon de ce grand départ

547
00:24:50,330 --> 00:24:53,310
et le programme réalise, à
attendez une minute, je suis hors de l'espace,

548
00:24:53,310 --> 00:24:55,410
il va doubler
la taille de la mémoire tampon

549
00:24:55,410 --> 00:24:59,110
puis doubler la taille de la mémoire tampon
et le code qui fait le doublement,

550
00:24:59,110 --> 00:25:03,170
si nous regardons ici, il est
juste cette habile one-liner.

551
00:25:03,170 --> 00:25:06,830
Vous pourriez ne pas avoir vu cette syntaxe
avant, mais si vous dites étoiles égale,

552
00:25:06,830 --> 00:25:10,470
cela est la même chose que
disant fois de capacité 2.

553
00:25:10,470 --> 00:25:13,390
Donc, il ne cesse de doubler
la capacité de la mémoire tampon

554
00:25:13,390 --> 00:25:17,480
puis dire realloc pour donner
lui-même que beaucoup plus de mémoire.

555
00:25:17,480 --> 00:25:19,720
>> Maintenant, en aparté, il
sont d'autres fonctions dans ici

556
00:25:19,720 --> 00:25:23,680
que nous ne regarderons pas dans les détails
autre que de montrer dans getint,

557
00:25:23,680 --> 00:25:26,150
nous utilisons GetString dans getint.

558
00:25:26,150 --> 00:25:28,192
Nous vérifions qu'il est pas
null, qui, rappelons,

559
00:25:28,192 --> 00:25:30,400
est la valeur spéciale qui
signifie quelque chose a mal tourné.

560
00:25:30,400 --> 00:25:31,233
Nous sommes sortis de la mémoire.

561
00:25:31,233 --> 00:25:32,310
Mieux vérifier cela.

562
00:25:32,310 --> 00:25:33,710
Et nous revenons une valeur sentinelle.

563
00:25:33,710 --> 00:25:37,850
Mais je vais laisser les commentaires quant à
pourquoi et puis nous utilisons ce cousin de scanf

564
00:25:37,850 --> 00:25:42,100
sscanf appelé et il se trouve
que sscanf, ou une chaîne scanf,

565
00:25:42,100 --> 00:25:45,310
vous permet de jeter un oeil à la ligne
l'utilisateur a tapé dans et vous laisser

566
00:25:45,310 --> 00:25:49,610
analyser essentiellement et ce que je suis
fais ici est que je dis sscanf,

567
00:25:49,610 --> 00:25:54,440
analyser quel que soit l'utilisateur
tapé dans et assurez-vous% i,

568
00:25:54,440 --> 00:25:59,250
il est un entier, et nous ne serons pas
entrer aujourd'hui exactement pourquoi il ya aussi

569
00:25:59,250 --> 00:26:03,760
un c%, mais que, dans un mot permet
de détecter si l'utilisateur a tapé

570
00:26:03,760 --> 00:26:06,050
dans quelque chose de faux après le numéro.

571
00:26:06,050 --> 00:26:11,766
Donc la raison pour laquelle getint et GetString
vous dire à réessayer, réessayer, réessayez

572
00:26:11,766 --> 00:26:13,640
est cause de tous
que le code que nous avons écrit,

573
00:26:13,640 --> 00:26:17,900
il est une sorte de regarder l'entrée de l'utilisateur
en veillant à ce qu'il est entièrement numérique

574
00:26:17,900 --> 00:26:21,700
ou il est un flottant réelle
valeur du point ou similaire,

575
00:26:21,700 --> 00:26:24,233
en fonction de ce que la valeur
fonctionnez vous utilisez.

576
00:26:24,233 --> 00:26:25,060
>> Ouf.

577
00:26:25,060 --> 00:26:25,710
D'ACCORD.

578
00:26:25,710 --> 00:26:27,592
Ce fut une bouchée
mais le point est ici

579
00:26:27,592 --> 00:26:29,550
que la raison pour laquelle nous avions
ces roues de formation sur

580
00:26:29,550 --> 00:26:32,880
est parce que, au niveau le plus bas,
Il ya tellement de choses qui

581
00:26:32,880 --> 00:26:35,674
peut aller mal que nous voulions
pour traiter préventivement

582
00:26:35,674 --> 00:26:38,090
ces choses certainement dans le
premières semaines de la classe,

583
00:26:38,090 --> 00:26:42,230
mais maintenant, avec PSet quatre et cinq et PSet
au-delà de vous verrez qu'il est plus vers

584
00:26:42,230 --> 00:26:45,570
vous, mais aussi que vous êtes plus capable
de résoudre ce genre de problèmes

585
00:26:45,570 --> 00:26:47,180
vous-même.

586
00:26:47,180 --> 00:26:51,770
Des questions sur GetString ou getint?

587
00:26:51,770 --> 00:26:52,630
Ouais?

588
00:26:52,630 --> 00:26:55,130
>> Public: Pourquoi voudriez-vous doubler
la capacité de la mémoire tampon

589
00:26:55,130 --> 00:26:57,630
plutôt que de simplement augmenter
par le montant exact?

590
00:26:57,630 --> 00:26:58,100
>> DAVID MALAN: Bonne question.

591
00:26:58,100 --> 00:27:00,474
Pourquoi voudrions-nous doubler la capacité
du tampon plutôt que

592
00:27:00,474 --> 00:27:02,800
juste à l'aggraver
par une certaine valeur constante?

593
00:27:02,800 --> 00:27:03,900
Il était une décision de conception.

594
00:27:03,900 --> 00:27:08,590
Nous avons juste décidé que parce qu'elle tend à
être un peu cher temps-sage de demander

595
00:27:08,590 --> 00:27:10,440
le système d'exploitation
pour mémoire, nous ne l'avons pas

596
00:27:10,440 --> 00:27:13,210
vouloir finir par entrer dans
une situation pour les grandes chaînes

597
00:27:13,210 --> 00:27:14,960
que nous demandions
l'OS encore et encore

598
00:27:14,960 --> 00:27:17,500
et encore et encore dans
succession rapide pour la mémoire.

599
00:27:17,500 --> 00:27:20,387
Donc nous avons juste décidé, un peu
arbitrairement, mais nous espérons raisonnablement,

600
00:27:20,387 --> 00:27:22,720
que, vous savez quoi, nous allons
essayer de prendre de l'avance de nous-mêmes

601
00:27:22,720 --> 00:27:25,520
et juste continuer à doubler en sorte que
nous minimisons la quantité de fois

602
00:27:25,520 --> 00:27:29,010
nous devons appeler malloc ou
realloc, mais un jugement totale

603
00:27:29,010 --> 00:27:31,820
appeler en l'absence de savoir
ce que les utilisateurs pourraient vouloir saisir.

604
00:27:31,820 --> 00:27:33,600
Les deux méthodes pourraient être défendable.

605
00:27:33,600 --> 00:27:35,430
Sans doute bonne.

606
00:27:35,430 --> 00:27:39,240
>> Donc, nous allons jeter un oeil à un couple
d'autres effets secondaires de la mémoire,

607
00:27:39,240 --> 00:27:41,610
choses qui peuvent mal se passer
et des outils que vous pouvez

608
00:27:41,610 --> 00:27:43,880
utiliser pour attraper ces types d'erreurs.

609
00:27:43,880 --> 00:27:47,800
Il se trouve tout de vous, même si
check50 ne vous a pas dit autant,

610
00:27:47,800 --> 00:27:50,050
ont écrit poussette
Code depuis la première semaine,

611
00:27:50,050 --> 00:27:53,630
même si tous les tests sont check50
passé, et même si vous et votre TF

612
00:27:53,630 --> 00:27:56,010
sont convaincus que super-
votre code fonctionne comme prévu.

613
00:27:56,010 --> 00:27:59,190
Votre code a été buggy ou
viciée en ce que chacun d'entre vous,

614
00:27:59,190 --> 00:28:02,540
en utilisant la bibliothèque CS50,
ont été fuite mémoire.

615
00:28:02,540 --> 00:28:06,040
Vous avez demandé le système d'exploitation
pour la mémoire dans la plupart des programmes

616
00:28:06,040 --> 00:28:08,850
vous avez écrit, mais vous avez
jamais réellement redonné.

617
00:28:08,850 --> 00:28:12,110
Vous avez appelé GetString
et getint et GetFloat,

618
00:28:12,110 --> 00:28:15,270
mais avec GetString, vous avez
jamais appelé unGetString ou donner

619
00:28:15,270 --> 00:28:19,890
String ou similaire, mais nous avons vu
que GetString fait allouer de la mémoire

620
00:28:19,890 --> 00:28:22,810
par voie de malloc ou cette
fonction realloc, qui est juste

621
00:28:22,810 --> 00:28:25,670
très similaire dans l'esprit,
et pourtant, nous avons été

622
00:28:25,670 --> 00:28:28,629
demandant au système d'exploitation pour
mémoire et la mémoire encore et encore

623
00:28:28,629 --> 00:28:29,670
mais jamais lui redonner.

624
00:28:29,670 --> 00:28:33,550
>> Maintenant, en aparté, il se trouve que
quand un programme se ferme, la totalité de la mémoire

625
00:28:33,550 --> 00:28:34,870
est automatiquement libéré.

626
00:28:34,870 --> 00:28:36,150
Donc, cela n'a pas été une affaire énorme.

627
00:28:36,150 --> 00:28:38,590
Il ne va pas se casser la
IDE ou ralentir les choses,

628
00:28:38,590 --> 00:28:40,670
Mais lorsque les programmes font
généralement fuite de mémoire

629
00:28:40,670 --> 00:28:42,170
et ils sont en cours d'exécution pendant une longue période.

630
00:28:42,170 --> 00:28:45,640
Si vous avez déjà vu la petite bête
ballon de plage dans Mac OS ou le sablier

631
00:28:45,640 --> 00:28:51,160
sur Windows où il est une sorte de
ralentir ou de penser ou de penser

632
00:28:51,160 --> 00:28:53,770
ou commence vraiment
de ralentir à une exploration,

633
00:28:53,770 --> 00:28:56,960
il pourrait être très probablement
le résultat d'une fuite de mémoire.

634
00:28:56,960 --> 00:28:59,970
Les programmeurs qui ont écrit
le logiciel que vous utilisez

635
00:28:59,970 --> 00:29:03,570
demander au système d'exploitation pour la mémoire
toutes les quelques minutes, toutes les heures.

636
00:29:03,570 --> 00:29:05,570
Mais si vous utilisez la
logiciel, même si elle est

637
00:29:05,570 --> 00:29:08,680
minimisé dans votre ordinateur
pendant des heures ou des jours,

638
00:29:08,680 --> 00:29:11,980
vous demandez peut-être pour de plus en plus
la mémoire et l'utiliser en fait jamais

639
00:29:11,980 --> 00:29:15,180
et ainsi votre code pourrait être, ou
programmes pourraient être une fuite de mémoire,

640
00:29:15,180 --> 00:29:18,350
et si vous commencez à perdre la mémoire,
il ya moins de mémoire pour les autres programmes,

641
00:29:18,350 --> 00:29:21,220
et l'effet est de
tout ralentir.

642
00:29:21,220 --> 00:29:23,600
>> Maintenant, cela est de loin l'un des
les programmes les plus atroces

643
00:29:23,600 --> 00:29:26,350
vous aurez l'occasion
à fonctionner dans la mesure où CS50

644
00:29:26,350 --> 00:29:31,650
que sa sortie est encore plus ésotérique que
clang de faire ou de toute ou de la commande

645
00:29:31,650 --> 00:29:35,930
programmes en ligne que nous avons exécuté avant mais
heureusement, noyé dans sa sortie

646
00:29:35,930 --> 00:29:39,810
est quelques conseils utiles que super-
sera utile soit pour PSet quatre

647
00:29:39,810 --> 00:29:41,510
ou certainement PSEt cinq.

648
00:29:41,510 --> 00:29:44,250
Donc valgrind est un outil
qui peut être utilisé pour comparer

649
00:29:44,250 --> 00:29:46,930
pour les fuites de mémoire dans votre programme.

650
00:29:46,930 --> 00:29:48,570
Il est relativement simple à exécuter.

651
00:29:48,570 --> 00:29:51,420
Vous exécutez valgrind puis, même
si elle est un peu verbeux,

652
00:29:51,420 --> 00:29:54,440
dash chèque tableau de bord de fuite
est égal à plein, puis dot

653
00:29:54,440 --> 00:29:56,320
slash et le nom de votre programme.

654
00:29:56,320 --> 00:30:00,010
Donc valgrind sera ensuite exécuter votre programme
et à la fin de votre programme

655
00:30:00,010 --> 00:30:02,240
courir avant qu'il quitte et
vous donne une autre invite,

656
00:30:02,240 --> 00:30:04,980
il va analyser votre
programme alors qu'il avait couru

657
00:30:04,980 --> 00:30:07,740
et dites que vous avez-vous des fuites
toute la mémoire et, mieux encore,

658
00:30:07,740 --> 00:30:10,610
avez-vous touchez mémoire
ne vous appartiennent?

659
00:30:10,610 --> 00:30:13,700
Il ne peut pas attraper tout, mais il est
assez bon à attraper la plupart des choses.

660
00:30:13,700 --> 00:30:19,700
>> Alors, voici un exemple de mon avoir couru
ce programme, ayant couru valgrind,

661
00:30:19,700 --> 00:30:21,470
sur un programme appelé
la mémoire, et je vais

662
00:30:21,470 --> 00:30:24,730
de mettre en évidence les lignes qui sont
en fin de compte de l'intérêt pour nous.

663
00:30:24,730 --> 00:30:27,690
Donc, il ya encore plus de distractions
que je l'ai supprimé de la diapositive.

664
00:30:27,690 --> 00:30:30,930
Mais voyons ce que cette
programme est capable de nous dire.

665
00:30:30,930 --> 00:30:34,800
Il est capable de nous dire les choses
comme écriture invalide de taille 4.

666
00:30:34,800 --> 00:30:38,020
En d'autres termes, si vous touchez la mémoire,
en particulier 4 octets de mémoire

667
00:30:38,020 --> 00:30:40,350
que vous ne devriez pas avoir,
valgrind peut vous le dire.

668
00:30:40,350 --> 00:30:41,660
Écriture invalide de taille 4.

669
00:30:41,660 --> 00:30:43,640
Vous avez abordé quatre octets
que vous ne devriez pas avoir.

670
00:30:43,640 --> 00:30:44,840
Où avez-vous fait cela?

671
00:30:44,840 --> 00:30:45,900
Ceci est la beauté.

672
00:30:45,900 --> 00:30:50,000
Mémoire dot ligne de 21 c est là que vous
foiré et voilà pourquoi il est utile.

673
00:30:50,000 --> 00:30:53,410
Tout comme GDB, il peut aider
vous indiquer à l'erreur réelle.

674
00:30:53,410 --> 00:30:57,170
>> Maintenant, celui-ci est un peu plus
verbose, sinon confus.

675
00:30:57,170 --> 00:31:01,307
40 octets dans 1 blocs sont certainement
perdu dans le dossier de la perte de 1 1.

676
00:31:01,307 --> 00:31:02,140
Qu'est-ce que cela veut dire?

677
00:31:02,140 --> 00:31:05,920
Eh bien, cela signifie simplement que vous avez demandé
40 octets et que vous ne lui avez donné dos.

678
00:31:05,920 --> 00:31:08,930
Vous avez appelé malloc ou vous avez appelé
GetString et le système d'exploitation

679
00:31:08,930 --> 00:31:12,450
vous 40 octets, mais vous jamais donné
libérés ou libérés que la mémoire,

680
00:31:12,450 --> 00:31:15,400
et pour être honnête, nous ne l'avons jamais montrons
vous comment redonner la mémoire.

681
00:31:15,400 --> 00:31:17,910
Avère qu'il ya un Super
simple fonction dite libre.

682
00:31:17,910 --> 00:31:21,170
Prend un argument, la chose
vous voulez libérer ou donner en retour,

683
00:31:21,170 --> 00:31:23,430
mais 40 octets, apparemment,
dans ce programme

684
00:31:23,430 --> 00:31:27,300
ont été perdus à la ligne
20 de la mémoire dot c.

685
00:31:27,300 --> 00:31:28,650
>> Voyons donc ce programme.

686
00:31:28,650 --> 00:31:31,020
Il est super inutile.

687
00:31:31,020 --> 00:31:33,980
Il démontre seulement
cette erreur particulière.

688
00:31:33,980 --> 00:31:34,920
Donc, nous allons jeter un coup d'oeil.

689
00:31:34,920 --> 00:31:39,920
Voici principales et principaux, avis, les appels
une fonction appelée rendements F puis.

690
00:31:39,920 --> 00:31:41,550
Donc, pas tout à fait intéressant.

691
00:31:41,550 --> 00:31:42,664
Qu'est-ce que f faire?

692
00:31:42,664 --> 00:31:44,330
Remarquez que je ne vous embêtez pas avec un prototype.

693
00:31:44,330 --> 00:31:46,520
Je voulais garder le code
aussi minime que possible.

694
00:31:46,520 --> 00:31:49,530
Donc, je mets principal et f ci-dessus
ça va, certainement,

695
00:31:49,530 --> 00:31:51,500
pour les programmes courts comme celui-ci.

696
00:31:51,500 --> 00:31:56,910
Donc f ne renvoie rien et fait
rien prendre, mais il ne le faire.

697
00:31:56,910 --> 00:31:59,620
Il déclare, tout comme
dans l'exemple Binky,

698
00:31:59,620 --> 00:32:02,682
un pointeur appelé x qui va
pour stocker l'adresse d'un int.

699
00:32:02,682 --> 00:32:03,890
Voilà donc le côté gauche.

700
00:32:03,890 --> 00:32:07,230
En anglais, ce qui est le
côté droit de faire?

701
00:32:07,230 --> 00:32:09,770
Toute personne?

702
00:32:09,770 --> 00:32:13,665
Quel est ce fait pour nous?

703
00:32:13,665 --> 00:32:14,651
Ouais?

704
00:32:14,651 --> 00:32:16,623
>> AUDIENCE: [inaudible]
fois la taille d'un int

705
00:32:16,623 --> 00:32:19,175
qui est 10 fois que [inaudible]

706
00:32:19,175 --> 00:32:20,800
DAVID MALAN: Bon et permettez-moi de résumer.

707
00:32:20,800 --> 00:32:25,480
Donc allouer suffisamment d'espace pour 10 entiers
ou 10, ce qui est de la taille d'un int,

708
00:32:25,480 --> 00:32:29,340
il est quatre octets, de sorte que 10 fois 4 est
40, de sorte que droite que je l'ai

709
00:32:29,340 --> 00:32:33,930
surbrillance est me donner 40 octets et
stocker l'adresse du premier octet

710
00:32:33,930 --> 00:32:34,940
en x.

711
00:32:34,940 --> 00:32:38,380
Et maintenant, enfin, et voici où
ce programme est bogué, ce qui est

712
00:32:38,380 --> 00:32:41,540
mal avec la ligne 21 basée sur cette logique?

713
00:32:41,540 --> 00:32:45,197

714
00:32:45,197 --> 00:32:46,280
Quel est le problème avec la ligne 21?

715
00:32:46,280 --> 00:32:46,780
Ouais?

716
00:32:46,780 --> 00:32:49,550
AUDIENCE: Vous ne pouvez pas
index dans x [inaudible].

717
00:32:49,550 --> 00:32:50,300
DAVID MALAN: Ouais.

718
00:32:50,300 --> 00:32:52,270
Je ne devrais pas index dans x comme ça.

719
00:32:52,270 --> 00:32:53,850
Donc, syntaxiquement, qui est OK.

720
00:32:53,850 --> 00:32:56,990
Ce qui est bien est, un peu comme vous
peut traiter le nom d'un tableau

721
00:32:56,990 --> 00:33:01,080
comme si elle est un pointeur, de façon similaire
pouvez-vous traiter un pointeur comme si elle est

722
00:33:01,080 --> 00:33:06,425
un tableau, et je ne peux donc syntaxiquement
dire x support de quelque chose, x support i,

723
00:33:06,425 --> 00:33:07,800
mais la figure 10 est problématique.

724
00:33:07,800 --> 00:33:09,096
Pourquoi?

725
00:33:09,096 --> 00:33:10,910
>> AUDIENCE: Parce qu'il est pas à l'intérieur.

726
00:33:10,910 --> 00:33:12,390
>> DAVID MALAN: Il est pas
à l'intérieur de ce morceau de mémoire.

727
00:33:12,390 --> 00:33:15,306
Quelle est la plus grande valeur que je devrait
être mise en ces crochets?

728
00:33:15,306 --> 00:33:16,870
9, 0 à 9.

729
00:33:16,870 --> 00:33:18,160
Du fait de l'indexation zéro.

730
00:33:18,160 --> 00:33:20,190
Ainsi de 0 à 9 serait bien.

731
00:33:20,190 --> 00:33:23,960
Support 10 est pas bon et
mais, rappeler que, chaque fois

732
00:33:23,960 --> 00:33:27,017
Il me semble essayer de faire CS50 IDE
accident en tapant des valeurs fausses,

733
00:33:27,017 --> 00:33:29,100
il ne collabore pas toujours,
et en effet, vous avez souvent

734
00:33:29,100 --> 00:33:31,460
avoir de la chance juste parce que le
système d'exploitation ne fait pas

735
00:33:31,460 --> 00:33:35,467
vous remarquerez que très légèrement
passer quelque morceau de la mémoire,

736
00:33:35,467 --> 00:33:38,300
parce que vous êtes resté au sein techniquement
votre segment, mais plus sur ce

737
00:33:38,300 --> 00:33:40,940
dans une classe de systèmes d'exploitation,
et ainsi de quelque chose comme ça

738
00:33:40,940 --> 00:33:43,000
pourrait très facilement passer inaperçue.

739
00:33:43,000 --> 00:33:48,120
Votre programme ne va jamais à planter
systématiquement mais peut-être de temps en temps.

740
00:33:48,120 --> 00:33:50,610
>> Et donc nous allons essayer valgrind
sur ce point, et voici

741
00:33:50,610 --> 00:33:52,870
où nous aurons dépassé
par la sortie momentanément.

742
00:33:52,870 --> 00:34:00,810
Donc, assurez-mémoire chèque valgrind de fuite
est égal à la mémoire pleine dot slash.

743
00:34:00,810 --> 00:34:03,040
Et voici pourquoi je promets
ce serait submerger.

744
00:34:03,040 --> 00:34:05,700
Voici ce que valgrind, voici ce que
un programmeur, certains ans-

745
00:34:05,700 --> 00:34:08,469
décidé que ce serait une bonne idée
pour la sortie de ressembler.

746
00:34:08,469 --> 00:34:09,750
Faisons donc le sens de cette.

747
00:34:09,750 --> 00:34:13,120
Donc, tout le chemin à la main gauche
côté sans raison valable

748
00:34:13,120 --> 00:34:16,620
est l'ID de processus du programme
nous venons de courir, l'identifiant unique

749
00:34:16,620 --> 00:34:18,030
pour le programme que nous avons manqué.

750
00:34:18,030 --> 00:34:19,738
Nous avons supprimé qu'à partir de
la diapositive, mais il

751
00:34:19,738 --> 00:34:22,190
quelques informations utiles ici.

752
00:34:22,190 --> 00:34:24,684
>> Disons défiler jusqu'à sommet.

753
00:34:24,684 --> 00:34:25,600
Voici où nous avons commencé.

754
00:34:25,600 --> 00:34:27,040
Donc, il est pas tant que ça sortie.

755
00:34:27,040 --> 00:34:30,429
Voici ce que écriture invalide
de la taille 4 à la ligne 21.

756
00:34:30,429 --> 00:34:31,760
Eh bien, ce qui était la ligne 21?

757
00:34:31,760 --> 00:34:34,500
Ligne 21 était exactement
cela et il est logique

758
00:34:34,500 --> 00:34:37,290
que je suis dans valablement
écrire 4 octets parce que je suis

759
00:34:37,290 --> 00:34:40,389
essayer de mettre cet entier,
qui pourrait être quelque chose,

760
00:34:40,389 --> 00:34:42,370
il arrive juste pour être
zéro, mais je suis en train

761
00:34:42,370 --> 00:34:44,940
pour le mettre à un endroit
qui ne fait pas de moi.

762
00:34:44,940 --> 00:34:50,900
De plus, ici-bas, 40 octets dans un
blocs sont définitivement perdus dans fiche 1.

763
00:34:50,900 --> 00:34:56,500
Cela est parce que quand je l'appelle malloc
ici, je jamais réellement libérer la mémoire.

764
00:34:56,500 --> 00:34:58,140
>> Alors, comment pouvons-nous résoudre ce problème?

765
00:34:58,140 --> 00:35:02,970
Permettez-moi aller de l'avant et être un peu plus sûr
et faire 9 là et laissez-moi ici gratuitement x.

766
00:35:02,970 --> 00:35:04,820
Ceci est la nouvelle fonction pour aujourd'hui.

767
00:35:04,820 --> 00:35:11,520
Si je ReRun maintenant faire mémoire de points slash,
exécutons valgrind sur elle à nouveau,

768
00:35:11,520 --> 00:35:14,990
maximiser ma fenêtre et appuyez sur Entrée.

769
00:35:14,990 --> 00:35:16,900
Maintenant, il est bon.

770
00:35:16,900 --> 00:35:19,590
Ils enterrent les bonnes nouvelles
dans l'ensemble de cette sortie.

771
00:35:19,590 --> 00:35:20,810
Tous les blocs de tas étaient libres.

772
00:35:20,810 --> 00:35:23,604
Nous allons revenir à ce que le tas
est, mais pas de fuites sont possibles.

773
00:35:23,604 --> 00:35:25,520
Donc, ceci est juste un autre
outil pour votre trousse à outils

774
00:35:25,520 --> 00:35:30,220
avec lequel vous pouvez commencer à
maintenant trouver des erreurs comme ça.

775
00:35:30,220 --> 00:35:34,532
>> Mais voyons ce que
plus peut aller mal ici.

776
00:35:34,532 --> 00:35:38,890
Laissez de transition maintenant
résoudre réellement un problème.

777
00:35:38,890 --> 00:35:42,440
En aparté, si cela va soulager
peu de confusion ou de tension,

778
00:35:42,440 --> 00:35:43,430
cela est maintenant drôle.

779
00:35:43,430 --> 00:35:46,400

780
00:35:46,400 --> 00:35:46,900
Ouais.

781
00:35:46,900 --> 00:35:49,040
Cela est assez bon.

782
00:35:49,040 --> 00:35:50,890
Parce que les pointeurs sont
des adresses et des adresses

783
00:35:50,890 --> 00:35:53,098
ayant généralement par convention
écrit avec hexadécimal.

784
00:35:53,098 --> 00:35:54,650
Ha, ha, ça drôle maintenant.

785
00:35:54,650 --> 00:35:58,390
Quoi qu'il en soit, nous allons donc maintenant
effectivement résoudre un problème.

786
00:35:58,390 --> 00:36:00,840
Cela a été super,
super bas niveau à ce jour,

787
00:36:00,840 --> 00:36:03,950
et nous pouvons réellement faire utiles
choses avec ces détails de bas niveau.

788
00:36:03,950 --> 00:36:06,710
>> Donc, nous avons introduit quelques semaines
il ya la notion d'un tableau.

789
00:36:06,710 --> 00:36:09,177
Un tableau était bien car
il est difficile de nettoyer notre code

790
00:36:09,177 --> 00:36:11,760
parce que si nous voulions écrire un
programme avec plusieurs étudiants

791
00:36:11,760 --> 00:36:15,270
ou plusieurs noms et les maisons et
dortoirs et des collèges et tout cela,

792
00:36:15,270 --> 00:36:19,430
nous pourrions tout stocker plus
proprement à l'intérieur d'un tableau.

793
00:36:19,430 --> 00:36:23,039
Mais proposer un inconvénient
d'un tableau jusqu'ici.

794
00:36:23,039 --> 00:36:26,080
Même si vous avez pas souffert soi-même
dans un programme, juste instinctivement,

795
00:36:26,080 --> 00:36:30,870
ce qui est une mauvaise chose
à propos d'un tableau, peut-être?

796
00:36:30,870 --> 00:36:32,337
Je entends quelques murmures.

797
00:36:32,337 --> 00:36:34,170
PUBLIC: Il est difficile
pour modifier la taille.

798
00:36:34,170 --> 00:36:36,128
DAVID MALAN: Il est difficile
pour modifier la taille.

799
00:36:36,128 --> 00:36:38,660
Vous ne pouvez pas modifier la taille
d'un tableau, en fait, en soi,

800
00:36:38,660 --> 00:36:43,040
en C. Vous pouvez attribuer un autre tableau,
déplacer tout de l'ancien

801
00:36:43,040 --> 00:36:45,380
dans le nouveau, et maintenant
avoir un peu d'espace supplémentaire,

802
00:36:45,380 --> 00:36:47,469
mais il est pas comme un
langage comme Java ou Python

803
00:36:47,469 --> 00:36:49,760
ou un nombre quelconque d'autres
langues avec lesquelles certains d'entre vous

804
00:36:49,760 --> 00:36:52,070
connaissez peut-être où vous
peut simplement continuer à ajouter des choses

805
00:36:52,070 --> 00:36:53,930
ad nauseam à la fin d'un tableau.

806
00:36:53,930 --> 00:36:57,880
Lorsque vous avez un tableau de
taille 6, qui est sa taille,

807
00:36:57,880 --> 00:37:01,970
et ainsi de beaucoup l'idée plus tôt
ayant une mémoire tampon d'une certaine taille,

808
00:37:01,970 --> 00:37:05,940
vous devez deviner hors de la porte
quelle taille voulez-vous qu'il soit?

809
00:37:05,940 --> 00:37:07,880
Si vous devinez trop grand,
vous perdez l'espace.

810
00:37:07,880 --> 00:37:10,950
Si vous devinez trop petite, vous
ne peut pas stocker les données, au moins

811
00:37:10,950 --> 00:37:12,940
sans beaucoup plus de travail.

812
00:37:12,940 --> 00:37:18,180
>> Donc, aujourd'hui, grâce à des pointeurs, nous pouvons
commencer assemblant notre propre personnalisé

813
00:37:18,180 --> 00:37:20,989
des structures de données, et
fait, voici quelque chose

814
00:37:20,989 --> 00:37:23,030
qui ressemble un peu plus
cryptique au premier coup d'œil,

815
00:37:23,030 --> 00:37:26,440
mais cela est ce que nous appellerons un lien
liste, et son nom de genre résume

816
00:37:26,440 --> 00:37:26,940
ce.

817
00:37:26,940 --> 00:37:29,550
Il est une liste de numéros, ou
ce cas, une liste de numéros,

818
00:37:29,550 --> 00:37:33,480
mais il pourrait être une liste de quelque chose, mais
il est lié à l'autre par des flèches,

819
00:37:33,480 --> 00:37:36,380
et juste prendre une proposition
avec quelle technique

820
00:37:36,380 --> 00:37:38,310
allons-nous être en mesure
à assembler,

821
00:37:38,310 --> 00:37:42,540
un peu comme du pop-corn avec un fil,
une liée listes rectangles ici?

822
00:37:42,540 --> 00:37:43,936
Ses numéros?

823
00:37:43,936 --> 00:37:45,560
Quelle est la fonction de la langue sous-jacente?

824
00:37:45,560 --> 00:37:46,350
>> PUBLIC: Un pointeur.

825
00:37:46,350 --> 00:37:47,308
>> DAVID MALAN: Un pointeur.

826
00:37:47,308 --> 00:37:51,700
Donc, chacun de ces flèches représente ici
un pointeur ou tout simplement une adresse.

827
00:37:51,700 --> 00:37:54,590
Donc, en d'autres termes, si je veux
pour stocker une liste de numéros,

828
00:37:54,590 --> 00:37:59,040
Je ne peux pas stocker si je veux
la capacité à croître et à se rétrécir

829
00:37:59,040 --> 00:38:00,990
la structure de mon données dans un tableau.

830
00:38:00,990 --> 00:38:03,000
Donc, je dois avoir un peu
plus de sophistication,

831
00:38:03,000 --> 00:38:05,720
mais remarquez que cette
image type de suggère

832
00:38:05,720 --> 00:38:08,650
que si vous avez juste petits fils
connectant tout ensemble,

833
00:38:08,650 --> 00:38:13,100
est probablement pas si difficile à faire de l'espace
entre deux de ces rectangles

834
00:38:13,100 --> 00:38:16,750
ou deux de ces nœuds, comme nous allons commencer
les appelant, mettre dans un nouveau nœud,

835
00:38:16,750 --> 00:38:19,547
et ensuite avec un nouveau fil, tout simplement
abandonner les trois nœuds ensemble,

836
00:38:19,547 --> 00:38:22,880
la première, la dernière, et la une
que vous venez d'insérer dans le milieu.

837
00:38:22,880 --> 00:38:26,000
>> Et en effet, une liste chaînée,
contrairement à un tableau, est dynamique.

838
00:38:26,000 --> 00:38:27,840
Il peut se développer et il peut
réduisez et vous ne le faites pas

839
00:38:27,840 --> 00:38:32,434
avoir à connaître ou de soins à l'avance comment
beaucoup de données vous allez être stocker,

840
00:38:32,434 --> 00:38:35,600
mais il se trouve que nous devons être un peu
attention à la façon de mettre en œuvre.

841
00:38:35,600 --> 00:38:39,070
Donc, d'abord nous allons examiner comment nous mettons en œuvre
un de ces petits rectangles.

842
00:38:39,070 --> 00:38:40,690
Il est facile à mettre en œuvre un int.

843
00:38:40,690 --> 00:38:44,000
Vous dites simplement int n, puis
vous obtenez 4 octets pour un int,

844
00:38:44,000 --> 00:38:49,089
mais comment puis-je obtenir un int, appelez ça n,
puis un pointeur, appelons-le suivant.

845
00:38:49,089 --> 00:38:50,880
Nous pourrions appeler ces
les choses ce que nous voulons

846
00:38:50,880 --> 00:38:53,590
mais je besoin d'une structure de données personnalisé.

847
00:38:53,590 --> 00:38:54,257
Ouais?

848
00:38:54,257 --> 00:38:57,020
>> AUDIENCE: Ampersand [inaudible].

849
00:38:57,020 --> 00:39:00,940
>> DAVID MALAN: Donc esperluette nous allons utiliser pour
obtenir l'adresse d'un noeud potentiellement.

850
00:39:00,940 --> 00:39:02,740
Mais nous avons besoin d'une autre
caractéristique de C dans l'ordre

851
00:39:02,740 --> 00:39:06,700
de me donner la possibilité de créer
ce rectangle de coutume, cette coutume

852
00:39:06,700 --> 00:39:08,919
variable si vous voulez, dans la mémoire.

853
00:39:08,919 --> 00:39:09,710
PUBLIC: Une struct.

854
00:39:09,710 --> 00:39:10,626
DAVID MALAN: Une struct.

855
00:39:10,626 --> 00:39:14,310
Rappelons que la semaine dernière, nous avons lancé
struct, cette relativement simple mot-clé

856
00:39:14,310 --> 00:39:16,254
qui nous permet de faire des choses comme ça.

857
00:39:16,254 --> 00:39:18,420
C ne vient pas avec un ensemble de données
structure appelée étudiant.

858
00:39:18,420 --> 00:39:22,190
Il est livré avec int et float et l'omble chevalier et
tel, mais il ne vient pas avec l'élève,

859
00:39:22,190 --> 00:39:26,750
mais nous pouvons créer un type de données de l'étudiant,
une structure d'étudiant, avec cette syntaxe

860
00:39:26,750 --> 00:39:27,250
Ici.

861
00:39:27,250 --> 00:39:28,350
Et vous verrez encore et encore.

862
00:39:28,350 --> 00:39:30,426
Donc, ne vous inquiétez pas
mémoriser les mots-clés,

863
00:39:30,426 --> 00:39:33,300
mais le mot-clé qui est important est
juste le fait que nous avons dit struct

864
00:39:33,300 --> 00:39:37,590
puis nous l'avons appelé étudiant et à l'intérieur
de l'étudiant était un nom et une maison

865
00:39:37,590 --> 00:39:39,390
ou un dortoir ou similaire.

866
00:39:39,390 --> 00:39:41,980
>> Et maintenant aujourd'hui, nous allons proposer cette.

867
00:39:41,980 --> 00:39:45,240
Je ai ajouté quelques mots, mais si je veux
de mettre en œuvre ce rectangle qui est

868
00:39:45,240 --> 00:39:48,440
a obtenu à la fois un int et un
pointeur, vous savez quoi, je suis

869
00:39:48,440 --> 00:39:51,540
aller à déclarer une struct appelé noeud.

870
00:39:51,540 --> 00:39:55,630
Je suis aussi, à l'intérieur de celui-ci, va dire
qu'un noeud, ce rectangle, a une int

871
00:39:55,630 --> 00:39:59,730
et nous appelons n et
il dispose d'un pointeur à côté.

872
00:39:59,730 --> 00:40:02,540
Et cela est un peu verbeux,
mais si vous pensez cela,

873
00:40:02,540 --> 00:40:07,300
les flèches qui étaient dans l'image
il ya un moment sont de ce type de données?

874
00:40:07,300 --> 00:40:12,330
Où chacun de ces flèches est pointée
à ce type de structure de données?

875
00:40:12,330 --> 00:40:14,332
Ça ne pointe pas juste pour un int en soi.

876
00:40:14,332 --> 00:40:16,165
Il est pointant vers le
rectangulaire toute chose

877
00:40:16,165 --> 00:40:18,720
et cette chose rectangulaire,
nous l'avons dit, est appelé un nœud.

878
00:40:18,720 --> 00:40:21,720
Et donc nous avons une sorte de à
définir de manière récursive cette tels

879
00:40:21,720 --> 00:40:26,270
qu'un nœud, nous dirons,
contiendra un int appelé n

880
00:40:26,270 --> 00:40:31,070
et un pointeur appelé prochaine et la
type de structure de données dans laquelle

881
00:40:31,070 --> 00:40:35,770
que les points de pointeur est apparemment
va être struct noeud.

882
00:40:35,770 --> 00:40:41,550
>> Donc, cela est fâcheusement verbose
et juste pour être pédant,

883
00:40:41,550 --> 00:40:44,100
la raison pour laquelle nous ne pouvons pas
juste dire ce qui franchement

884
00:40:44,100 --> 00:40:46,860
ressemble beaucoup plus lisible,
est parce que c lire le rappel

885
00:40:46,860 --> 00:40:48,710
les choses de haut en bas, de gauche à droite.

886
00:40:48,710 --> 00:40:54,120
Il est pas jusqu'à ce que nous obtenons le point-virgule
que le noeud mot-clé existe réellement.

887
00:40:54,120 --> 00:40:57,980
Donc, si nous voulons avoir ce genre de
référence cyclique à l'intérieur des données

888
00:40:57,980 --> 00:41:02,120
la structure, nous avons à faire, où
nous disons noeud struct au sommet, qui

889
00:41:02,120 --> 00:41:06,770
nous donne une façon de décrire ce plus
chose, puis à l'intérieur nous disons noeud de struct,

890
00:41:06,770 --> 00:41:09,560
puis à la dernière ligne
nous disons, tout droit, C, par la manière,

891
00:41:09,560 --> 00:41:12,060
il suffit d'appeler toute cette foutue
chose et d'arrêter un noeud

892
00:41:12,060 --> 00:41:14,360
en utilisant tout à fait le mot-clé struct.

893
00:41:14,360 --> 00:41:18,030
Donc, cela est juste une sorte de syntaxique
astuce qui permet en fin de compte nous créons

894
00:41:18,030 --> 00:41:21,370
quelque chose qui ressemble exactement à cela.

895
00:41:21,370 --> 00:41:25,010
>> Donc, si nous supposons maintenant que nous pouvons
mettre en œuvre cette chose en C,

896
00:41:25,010 --> 00:41:28,040
comment pouvons-nous réellement
commencer traversant ce?

897
00:41:28,040 --> 00:41:32,360
Eh bien, en fait, tout ce que nous avons à faire est
itérer de gauche à droite et juste

898
00:41:32,360 --> 00:41:35,960
genre d'insérer ou de supprimer des noeuds noeuds
ou chercher des choses là où nous voulons,

899
00:41:35,960 --> 00:41:39,560
mais pour ce faire, nous allons aller de l'avant et de faire
les choses un peu plus réelle parce que cette

900
00:41:39,560 --> 00:41:42,560
a été faible niveau super jusqu'ici.

901
00:41:42,560 --> 00:41:45,700
Quelqu'un voudrait littéralement être le premier?

902
00:41:45,700 --> 00:41:46,200
D'ACCORD.

903
00:41:46,200 --> 00:41:47,092
Allez vers le haut.

904
00:41:47,092 --> 00:41:47,800
Comment t'appelles tu?

905
00:41:47,800 --> 00:41:48,499
>> DAVID: David.

906
00:41:48,499 --> 00:41:49,290
DAVID MALAN: David.

907
00:41:49,290 --> 00:41:49,998
Enchanté de faire votre connaissance.

908
00:41:49,998 --> 00:41:50,960
Moi aussi.

909
00:41:50,960 --> 00:41:52,450
Bien.

910
00:41:52,450 --> 00:41:53,990
Et nous avons besoin d'un numéro 9.

911
00:41:53,990 --> 00:41:55,240
Pas aussi bon que la première, peut-être.

912
00:41:55,240 --> 00:41:56,430
OK, le numéro 9.

913
00:41:56,430 --> 00:41:59,667
Un certain nombre 17, s'il vous plaît.

914
00:41:59,667 --> 00:42:01,000
Permettez-moi de revenir un peu plus loin.

915
00:42:01,000 --> 00:42:03,980
Nombre 22, s'il vous plaît, et
que diriez-vous plus loin

916
00:42:03,980 --> 00:42:06,344
si je peux voir toutes les mains
avec toute la lumière ou pas.

917
00:42:06,344 --> 00:42:08,010
Quelqu'un étant volontaire là.

918
00:42:08,010 --> 00:42:08,968
Voulez-vous venir?

919
00:42:08,968 --> 00:42:10,450
Votre avant-bras est de force à la hausse.

920
00:42:10,450 --> 00:42:12,340
OK, 17.

921
00:42:12,340 --> 00:42:13,690
22.

922
00:42:13,690 --> 00:42:15,120
26 descend.

923
00:42:15,120 --> 00:42:18,450
Quiconque voudrait
forcefully-- Allez jusqu'à.

924
00:42:18,450 --> 00:42:21,030
Un volontaire réelle.

925
00:42:21,030 --> 00:42:23,330
>> Donc, très rapidement, si
vous les gars pourraient organiser

926
00:42:23,330 --> 00:42:26,550
vous voulez juste
les noeuds sur l'écran.

927
00:42:26,550 --> 00:42:27,510
Merci.

928
00:42:27,510 --> 00:42:29,234
Et vous serez 26.

929
00:42:29,234 --> 00:42:30,650
Toutes les bonnes introductions et rapide.

930
00:42:30,650 --> 00:42:32,139
Donc, je suis David et vous êtes aussi?

931
00:42:32,139 --> 00:42:32,680
DAVID: David.

932
00:42:32,680 --> 00:42:33,721
DAVID MALAN: Et vous êtes?

933
00:42:33,721 --> 00:42:34,229
JAKE: Jake.

934
00:42:34,229 --> 00:42:34,729
SUE: Sue.

935
00:42:34,729 --> 00:42:35,229
ALEX: Alex.

936
00:42:35,229 --> 00:42:36,475
RAPHAEL: Raphael.

937
00:42:36,475 --> 00:42:37,100
TAYLOR: Taylor.

938
00:42:37,100 --> 00:42:37,466
DAVID MALAN: Taylor.

939
00:42:37,466 --> 00:42:37,590
Excellente.

940
00:42:37,590 --> 00:42:39,810
Donc, ce sont nos bénévoles
pour aujourd'hui et aller de l'avant

941
00:42:39,810 --> 00:42:43,090
et de passer un peu de cette façon,
et juste aller de l'avant et de garder

942
00:42:43,090 --> 00:42:47,024
la tenue de vos numéros que vous êtes ou votre
premier signe et l'aide de votre main gauche,

943
00:42:47,024 --> 00:42:48,940
aller de l'avant et juste mettre en œuvre
ces flèches, tout simplement

944
00:42:48,940 --> 00:42:51,360
de sorte que votre main gauche est littéralement
montrant tout ce que vous devez mentionner

945
00:42:51,360 --> 00:42:54,610
à, et vous donner une certaine marge de telle sorte que
nous pouvons voir visuellement vos bras effectivement

946
00:42:54,610 --> 00:42:58,120
pointage, et vous pouvez simplement pointer
sorte de au rez-est très bien.

947
00:42:58,120 --> 00:43:03,040
>> Nous avons donc ici une liste liée de l'une,
deux, trois, quatre, cinq noeuds initialement,

948
00:43:03,040 --> 00:43:05,860
et remarquez que nous avons cette spéciale
pointeur au début qui est

949
00:43:05,860 --> 00:43:09,770
clé parce que nous devons garder la trace
de l'ensemble de la liste de la longueur d'une certaine manière.

950
00:43:09,770 --> 00:43:13,590
Ces gars-là, même si elles sont laissées
à droite, dos à dos dans la mémoire,

951
00:43:13,590 --> 00:43:15,950
ils peuvent effectivement être partout
dans la mémoire de l'ordinateur.

952
00:43:15,950 --> 00:43:18,240
Donc, ces gars-là pourraient être
debout partout sur la scène

953
00:43:18,240 --> 00:43:20,960
et ça va, tant qu'ils sont
effectivement pointant à l'autre,

954
00:43:20,960 --> 00:43:22,770
mais de garder les choses
propre et simple, nous allons

955
00:43:22,770 --> 00:43:25,728
juste les dessiner à droite comme à gauche
, mais il pourrait y avoir des lacunes massives

956
00:43:25,728 --> 00:43:26,790
entre ces noeuds.

957
00:43:26,790 --> 00:43:30,710
>> Maintenant, si je veux réellement insérer des
nouvelle valeur, nous allons aller de l'avant et le faire.

958
00:43:30,710 --> 00:43:33,720
Nous avons maintenant l'occasion
de choisir un autre nœud.

959
00:43:33,720 --> 00:43:39,820
Dites nous allons commencer avec les allouer de 55.

960
00:43:39,820 --> 00:43:41,320
Quelqu'un aurait l'esprit étant malloc?

961
00:43:41,320 --> 00:43:42,280
OK, venez sur place.

962
00:43:42,280 --> 00:43:42,992
Comment t'appelles tu?

963
00:43:42,992 --> 00:43:43,700
RAINBOW: arc en ciel.

964
00:43:43,700 --> 00:43:44,050
DAVID MALAN: Rainbow?

965
00:43:44,050 --> 00:43:44,810
Bien.

966
00:43:44,810 --> 00:43:46,600
Malloc arc.

967
00:43:46,600 --> 00:43:47,450
Allez vers le haut.

968
00:43:47,450 --> 00:43:51,610
Alors maintenant, nous devons nous demander
algorithmique où nous pouvons mettre 55.

969
00:43:51,610 --> 00:43:53,610
Donc, nous le savons tous,
évidemment, où elle a probablement

970
00:43:53,610 --> 00:43:55,401
appartient si nous essayons
de garder cette triée

971
00:43:55,401 --> 00:43:58,299
Et si vous les gars pourrait prendre une
du recul afin de ne pas tomber

972
00:43:58,299 --> 00:43:59,590
la scène, ce serait formidable.

973
00:43:59,590 --> 00:44:01,420
Donc en fait, Rainbow,
recommencer ici avec moi,

974
00:44:01,420 --> 00:44:04,200
parce que nous, l'ordinateur peut maintenant
ne verrez qu'une seule variable à la fois.

975
00:44:04,200 --> 00:44:05,190
Donc, si tel est le premier noeud.

976
00:44:05,190 --> 00:44:07,160
Notez qu'il est pas un nœud,
il est juste un pointeur,

977
00:44:07,160 --> 00:44:10,270
et voilà pourquoi il a dessiné pour être
seulement la taille d'un pointeur, pas

978
00:44:10,270 --> 00:44:11,780
un de ces rectangles pleins.

979
00:44:11,780 --> 00:44:16,650
Donc, nous allons vérifier à chaque
itération est inférieure à 55 9?

980
00:44:16,650 --> 00:44:17,150
Non.

981
00:44:17,150 --> 00:44:19,060
Is 55, moins de 17?

982
00:44:19,060 --> 00:44:19,720
Non.

983
00:44:19,720 --> 00:44:20,800
Moins de 22?

984
00:44:20,800 --> 00:44:22,020
Moins de 26?

985
00:44:22,020 --> 00:44:23,390
Moins de 34?

986
00:44:23,390 --> 00:44:25,890
Et maintenant, évidemment
Arc en ciel appartient à la fin.

987
00:44:25,890 --> 00:44:27,270
Donc, pour être clair, et ce
était votre nom, Taylor?

988
00:44:27,270 --> 00:44:27,895
>> TAYLOR: Taylor.

989
00:44:27,895 --> 00:44:32,510
DAVID MALAN: Donc parmi Taylor
main gauche et les mains de l'arc ici,

990
00:44:32,510 --> 00:44:38,324
dont la main a besoin de pointer ce qui, dans
Afin d'insérer 55 dans cette liste?

991
00:44:38,324 --> 00:44:39,240
Que devons-nous faire?

992
00:44:39,240 --> 00:44:39,700
Ouais?

993
00:44:39,700 --> 00:44:41,140
>> AUDIENCE: la main de Taylor
doit pointer gauche.

994
00:44:41,140 --> 00:44:41,680
>> DAVID MALAN: Exactement.

995
00:44:41,680 --> 00:44:43,800
Ainsi, l'insertion d'un nœud
dans la fin de la liste

996
00:44:43,800 --> 00:44:47,140
est assez simple parce que Taylor simplement
a signaler, au lieu de la terre

997
00:44:47,140 --> 00:44:49,640
ou nous l'appellerons null,
null est en quelque sorte l'absence

998
00:44:49,640 --> 00:44:51,640
d'un pointeur ou un spécial
pointeur zéro, vous êtes

999
00:44:51,640 --> 00:44:53,740
va pointer avec votre gauche
main à Rainbow et Rainbow

1000
00:44:53,740 --> 00:44:55,910
où si votre gauche
main probablement Point?

1001
00:44:55,910 --> 00:44:56,570
Vers le bas.

1002
00:44:56,570 --> 00:45:00,140
Il est pas bon si sa main est en quelque sorte
de pointer au large ici ou toute sorte de

1003
00:45:00,140 --> 00:45:00,640
Quelle direction.

1004
00:45:00,640 --> 00:45:02,407
Ce serait considéré comme
une valeur d'ordures,

1005
00:45:02,407 --> 00:45:04,240
mais si elle montre
une certaine valeur connue, nous allons

1006
00:45:04,240 --> 00:45:07,360
appeler zéro ou nulle, qui est OK
parce que nous avons un terme dans ce

1007
00:45:07,360 --> 00:45:09,390
et nous savons la liste est maintenant terminée.

1008
00:45:09,390 --> 00:45:11,550
>> Alors, quel est l'autre
cas relativement simple?

1009
00:45:11,550 --> 00:45:13,125
Pourrions-nous malloc 5?

1010
00:45:13,125 --> 00:45:14,010
Allez vers le haut.

1011
00:45:14,010 --> 00:45:14,782
Comment t'appelles tu?

1012
00:45:14,782 --> 00:45:15,490
TIFFANY: Tiffany.

1013
00:45:15,490 --> 00:45:16,000
DAVID MALAN: Je suis désolé?

1014
00:45:16,000 --> 00:45:16,470
TIFFANY: Tiffany.

1015
00:45:16,470 --> 00:45:16,880
DAVID MALAN: Tiffany.

1016
00:45:16,880 --> 00:45:17,110
Bien.

1017
00:45:17,110 --> 00:45:19,071
Tiffany a été malloced
avec la valeur 5.

1018
00:45:19,071 --> 00:45:19,570
Allez vers le haut.

1019
00:45:19,570 --> 00:45:23,820
Celui-ci est relativement facile aussi, mais
nous allons examiner maintenant l'ordre des opérations.

1020
00:45:23,820 --> 00:45:25,820
Il était assez facile
avec Taylor à la fin.

1021
00:45:25,820 --> 00:45:30,302
Nombre 5 est bien sûr moins de 9,
et nous avons donc David, nous avons Tiffany,

1022
00:45:30,302 --> 00:45:31,260
et quel était votre nom?

1023
00:45:31,260 --> 00:45:31,680
>> JAKE: Jake.

1024
00:45:31,680 --> 00:45:32,470
>> DAVID MALAN: Jake.

1025
00:45:32,470 --> 00:45:34,300
Tiffany, Jake, et David.

1026
00:45:34,300 --> 00:45:36,580
Dont la main devrait être mis à jour en premier?

1027
00:45:36,580 --> 00:45:39,260

1028
00:45:39,260 --> 00:45:40,590
Que voulez-vous faire ici?

1029
00:45:40,590 --> 00:45:45,244
Il ya quelques façons possibles, mais
il ya aussi un ou des moyens plus mauvaises.

1030
00:45:45,244 --> 00:45:46,620
>> AUDIENCE: Commencez par la plus à gauche.

1031
00:45:46,620 --> 00:45:47,800
>> DAVID MALAN: Commencez par le plus à gauche.

1032
00:45:47,800 --> 00:45:49,008
Qui est le plus à gauche ici, alors?

1033
00:45:49,008 --> 00:45:49,700
AUDIENCE: Première.

1034
00:45:49,700 --> 00:45:50,366
>> DAVID MALAN: OK.

1035
00:45:50,366 --> 00:45:53,781
Donc, commencer par la première et où avez-vous
vouloir mettre à jour les mains de David d'être?

1036
00:45:53,781 --> 00:45:54,780
AUDIENCE: Vers la 5.

1037
00:45:54,780 --> 00:45:55,446
DAVID MALAN: OK.

1038
00:45:55,446 --> 00:45:59,026
Alors David, le point à cinq
ou Tiffany ici, et maintenant?

1039
00:45:59,026 --> 00:46:01,072
>> AUDIENCE: Tiffany pointe vers le 9?

1040
00:46:01,072 --> 00:46:04,030
DAVID MALAN: Parfait, sauf de Binky
la tête juste un peu tombé, non?

1041
00:46:04,030 --> 00:46:06,820
Parce que ce qui ne va pas avec
cette image littéralement?

1042
00:46:06,820 --> 00:46:08,070
AUDIENCE: Rien pointe.

1043
00:46:08,070 --> 00:46:09,945
DAVID MALAN: Rien
pointant vers Jake maintenant.

1044
00:46:09,945 --> 00:46:13,360
Nous avons littéralement orphelins 9
et 17, et nous avons littéralement

1045
00:46:13,360 --> 00:46:18,450
fuyait de cette mémoire, parce que, par
mise à jour de la main de David d'abord, que ce

1046
00:46:18,450 --> 00:46:21,660
bien dans la mesure où il est correctement
pointant à Tiffany maintenant,

1047
00:46:21,660 --> 00:46:25,410
mais si personne ne l'avait
prévoyance pour pointer vers Jake,

1048
00:46:25,410 --> 00:46:27,490
alors nous avons perdu la
totalité de cette liste.

1049
00:46:27,490 --> 00:46:28,200
Donc, nous allons défaire.

1050
00:46:28,200 --> 00:46:30,950
Donc, ce fut une bonne chose
trébucher mais nous allons corriger maintenant.

1051
00:46:30,950 --> 00:46:33,624
Que devrions-nous faire en premier lieu?

1052
00:46:33,624 --> 00:46:34,124
Ouais?

1053
00:46:34,124 --> 00:46:35,791
>> AUDIENCE: Tiffany doit pointer au 9?

1054
00:46:35,791 --> 00:46:37,582
DAVID MALAN: je ne peux pas
obtenir que près de vous.

1055
00:46:37,582 --> 00:46:38,720
Qui devrait pointer le 9?

1056
00:46:38,720 --> 00:46:39,220
>> AUDIENCE: Tiffany.

1057
00:46:39,220 --> 00:46:39,390
>> DAVID MALAN: Très bien.

1058
00:46:39,390 --> 00:46:41,200
Donc Tiffany devrait premier point à la 9.

1059
00:46:41,200 --> 00:46:43,550
Donc Tiffany devrait prendre
sur une valeur identique

1060
00:46:43,550 --> 00:46:45,820
à David, qui semble
redondant pour un moment,

1061
00:46:45,820 --> 00:46:48,820
mais cela est très bien, parce que maintenant, deuxième
étape, nous pouvons mettre à jour la main de David

1062
00:46:48,820 --> 00:46:52,680
à signaler, et puis si à Tiffany
Nous venons genre de nettoyer les choses

1063
00:46:52,680 --> 00:46:55,740
comme si cela est une sorte de printanier,
voilà une bonne insertion.

1064
00:46:55,740 --> 00:46:56,700
Donc excellente.

1065
00:46:56,700 --> 00:46:57,970
Alors maintenant, nous y sommes presque.

1066
00:46:57,970 --> 00:47:01,075
Insérons une dernière
valeur comme la valeur 20.

1067
00:47:01,075 --> 00:47:03,010
Si nous pouvions malloc un bénévole finale?

1068
00:47:03,010 --> 00:47:04,140
Allez vers le haut.

1069
00:47:04,140 --> 00:47:06,224
Alors celui-ci est un peu plus délicat.

1070
00:47:06,224 --> 00:47:08,390
Mais vraiment, le code que nous sommes
l'écriture, mais verbalement,

1071
00:47:08,390 --> 00:47:10,610
est juste comme avoir un tas
si les conditions de l'entreprise, non?

1072
00:47:10,610 --> 00:47:12,318
Nous avions une condition
vérifier si elle appartient

1073
00:47:12,318 --> 00:47:13,840
à la fin, peut-être le début.

1074
00:47:13,840 --> 00:47:15,940
Nous avons besoin d'une sorte de boucle
trouver l'endroit dans le milieu.

1075
00:47:15,940 --> 00:47:17,400
Donc, nous allons faire avec ce qui est votre nom?

1076
00:47:17,400 --> 00:47:17,700
>> ERIC: Eric.

1077
00:47:17,700 --> 00:47:18,340
>> DAVID MALAN: Eric?

1078
00:47:18,340 --> 00:47:18,660
Eric.

1079
00:47:18,660 --> 00:47:19,368
Enchanté de faire votre connaissance.

1080
00:47:19,368 --> 00:47:20,490
Nous avons donc 20.

1081
00:47:20,490 --> 00:47:21,220
Moins de cinq ans?

1082
00:47:21,220 --> 00:47:21,530
Non.

1083
00:47:21,530 --> 00:47:22,160
Moins de neuf?

1084
00:47:22,160 --> 00:47:22,410
Non.

1085
00:47:22,410 --> 00:47:23,050
Moins de 17?

1086
00:47:23,050 --> 00:47:23,550
Non.

1087
00:47:23,550 --> 00:47:23,740
D'ACCORD.

1088
00:47:23,740 --> 00:47:25,701
Il appartient ici et
vos noms sont à nouveau?

1089
00:47:25,701 --> 00:47:26,200
SUE: Sue.

1090
00:47:26,200 --> 00:47:26,880
DAVID MALAN: Sue.

1091
00:47:26,880 --> 00:47:27,379
ALEX: Alex.

1092
00:47:27,379 --> 00:47:28,790
DAVID MALAN: Sue, Alex, et?

1093
00:47:28,790 --> 00:47:29,290
ERIC: Eric.

1094
00:47:29,290 --> 00:47:30,120
DAVID MALAN: Eric.

1095
00:47:30,120 --> 00:47:32,140
Dont les mains ont besoin de se mettre à jour en premier?

1096
00:47:32,140 --> 00:47:32,930
>> AUDIENCE: Eric.

1097
00:47:32,930 --> 00:47:33,429
D'ACCORD.

1098
00:47:33,429 --> 00:47:35,200
Donc, d'Eric devrait pointer où?

1099
00:47:35,200 --> 00:47:35,930
A 22 ans.

1100
00:47:35,930 --> 00:47:36,430
Bien.

1101
00:47:36,430 --> 00:47:38,180
Et maintenant, quelle est la prochaine?

1102
00:47:38,180 --> 00:47:40,800
Sue peut alors pointer Eric
et maintenant, si vous les gars juste

1103
00:47:40,800 --> 00:47:44,077
faire de la place, ce qui est bien
visuellement, maintenant que nous avons fait de l'insertion.

1104
00:47:44,077 --> 00:47:47,160
Donc, nous allons maintenant examiner une question, mais
je vous remercie beaucoup pour nos bénévoles.

1105
00:47:47,160 --> 00:47:48,090
Très bien fait.

1106
00:47:48,090 --> 00:47:50,831
Vous pouvez garder ceux-ci, si vous le souhaitez.

1107
00:47:50,831 --> 00:47:54,140
Et nous avons un beau cadeau d'adieu si
vous seriez chaque aimez prendre une boule de stress.

1108
00:47:54,140 --> 00:47:56,030
Permettez-moi de passer cette baisse.

1109
00:47:56,030 --> 00:47:58,430
Alors quelle est la livraison de ce?

1110
00:47:58,430 --> 00:48:02,430
Cela semble être incroyable
dans la mesure où nous avons maintenant

1111
00:48:02,430 --> 00:48:06,360
introduit une alternative à un
tableau qui ne s'y limite pas

1112
00:48:06,360 --> 00:48:07,780
à un tableau d'une certaine taille fixe.

1113
00:48:07,780 --> 00:48:09,380
Ils peuvent se développer dynamiquement.

1114
00:48:09,380 --> 00:48:13,220
>> Mais tout comme nous l'avons vu dans les semaines
passé, nous ne sommes jamais rien pour rien,

1115
00:48:13,220 --> 00:48:15,740
comme il ya sûrement un compromis ici.

1116
00:48:15,740 --> 00:48:18,890
Donc, avec une tête d'un lien
liste, est ce dynamisme?

1117
00:48:18,890 --> 00:48:21,590
Cette capacité à croître et franchement,
nous aurions pu faire de suppression

1118
00:48:21,590 --> 00:48:23,570
et nous pouvions réduire si nécessaire.

1119
00:48:23,570 --> 00:48:24,710
Quel prix payons-nous?

1120
00:48:24,710 --> 00:48:28,510

1121
00:48:28,510 --> 00:48:30,340
Deux fois autant d'espace, tout d'abord.

1122
00:48:30,340 --> 00:48:34,010
Si vous regardez l'image, pas plus
suis-je stocker une liste d'entiers.

1123
00:48:34,010 --> 00:48:36,740
Je stocker une liste des
entiers ainsi que des pointeurs.

1124
00:48:36,740 --> 00:48:38,240
Donc, je suis doublement de la quantité d'espace.

1125
00:48:38,240 --> 00:48:40,740
Maintenant, peut-être que ce pas de nature
une grosse affaire de 4 octets, 8 octets,

1126
00:48:40,740 --> 00:48:43,160
mais il pourrait certainement ajouter
pour de grands ensembles de données.

1127
00:48:43,160 --> 00:48:45,570
Quel est un autre inconvénient?

1128
00:48:45,570 --> 00:48:46,070
Ouais?

1129
00:48:46,070 --> 00:48:48,010
>> PUBLIC: Nous devons
traverser les une par une.

1130
00:48:48,010 --> 00:48:48,760
DAVID MALAN: Ouais.

1131
00:48:48,760 --> 00:48:50,260
Nous devons les traverser un par un.

1132
00:48:50,260 --> 00:48:53,860
Vous savez quoi, nous avons renoncé à ce super
fonction pratique du crochet

1133
00:48:53,860 --> 00:48:57,240
notation, plus correctement
connu comme l'accès aléatoire,

1134
00:48:57,240 --> 00:48:59,280
où nous pouvons simplement sauter
à un élément individuel

1135
00:48:59,280 --> 00:49:01,470
mais maintenant, si je devais encore
mes bénévoles ici,

1136
00:49:01,470 --> 00:49:04,660
si je voulais trouver le
numéro 22, je ne peux pas

1137
00:49:04,660 --> 00:49:06,620
passer à quelque chose de support de quelque chose.

1138
00:49:06,620 --> 00:49:10,530
Je dois regarder par-dessus la liste, beaucoup
comme nos exemples DE LA RECHERCHE linéairement,

1139
00:49:10,530 --> 00:49:12,260
pour trouver le numéro 22.

1140
00:49:12,260 --> 00:49:14,340
Donc, nous semblons avoir payé un prix là-bas.

1141
00:49:14,340 --> 00:49:16,430
Mais nous pouvons tout de même
résoudre d'autres problèmes.

1142
00:49:16,430 --> 00:49:18,587
>> En fait, permettez-moi de vous présenter
juste un couple de visuels.

1143
00:49:18,587 --> 00:49:20,920
Donc, si vous avez été jusqu'à
Dining Hall Mather récemment,

1144
00:49:20,920 --> 00:49:23,320
Vous vous souviendrez que leur
piles de plateaux comme celui-ci,

1145
00:49:23,320 --> 00:49:26,300
nous avons emprunté ces partir
Annenberg avant la classe.

1146
00:49:26,300 --> 00:49:28,930
Donc, cette pile de plateaux, même si,
est représentatif effectivement

1147
00:49:28,930 --> 00:49:30,860
d'une structure de données de la science informatique.

1148
00:49:30,860 --> 00:49:32,910
Il y a une structure de données
en informatique

1149
00:49:32,910 --> 00:49:38,010
connu comme une pile qui très bien
se prête à exactement ce visuel.

1150
00:49:38,010 --> 00:49:41,380
Donc, si chacun de ces plateaux est pas un
bac mais comme un certain nombre et je voulais

1151
00:49:41,380 --> 00:49:45,010
à stocker des numéros, je
pourrait mettre un ici-bas,

1152
00:49:45,010 --> 00:49:48,320
et je pourrais mettre une autre ici-bas,
et continuer l'empilage des numéros

1153
00:49:48,320 --> 00:49:53,180
sur le dessus les uns des autres, et ce qui est
potentiellement utiles à ce sujet

1154
00:49:53,180 --> 00:49:55,450
est que ce qui est de l'implication
de cette structure de données?

1155
00:49:55,450 --> 00:49:58,045
Quel numéro puis-je sortir
première la plus commode?

1156
00:49:58,045 --> 00:50:00,640

1157
00:50:00,640 --> 00:50:03,030
Le plus récemment, on a mis là-bas.

1158
00:50:03,030 --> 00:50:06,430
>> Voilà donc ce que nous appellerions en
informatique, une structure de données LIFO.

1159
00:50:06,430 --> 00:50:08,070
Dernier entré, premier sorti.

1160
00:50:08,070 --> 00:50:10,800
Et nous verrons avant longtemps pourquoi
qui pourraient être utiles, mais pour l'instant,

1161
00:50:10,800 --> 00:50:12,200
il suffit de considérer la propriété.

1162
00:50:12,200 --> 00:50:15,158
Et il est un peu stupide si vous pensez
sur la façon dont la salle à manger fait.

1163
00:50:15,158 --> 00:50:17,910
Chaque fois qu'ils plateaux propres et
mettre la fraîcheur ceux sur le dessus,

1164
00:50:17,910 --> 00:50:22,160
vous pourriez avoir un précédemment propre
mais finalement très sale et poussiéreux

1165
00:50:22,160 --> 00:50:24,360
le plateau tout en bas
si vous jamais réellement

1166
00:50:24,360 --> 00:50:26,820
aller au fond de cette
pile, parce que vous venez

1167
00:50:26,820 --> 00:50:29,380
continuer à mettre la nouvelle et
celles propres sur le dessus.

1168
00:50:29,380 --> 00:50:31,840
La même chose pourrait se produire
dans un supermarché trop.

1169
00:50:31,840 --> 00:50:35,450
Si vous avez une vitrine
de lait et de tous les temps de CVS

1170
00:50:35,450 --> 00:50:37,610
ou celui qui obtient plus de lait,
vous venez de fourrer les laits

1171
00:50:37,610 --> 00:50:39,880
vous avez déjà à l'arrière et
vous mettez les nouveaux à l'avant,

1172
00:50:39,880 --> 00:50:43,088
vous allez avoir un peu assez méchant
lait à la fin de la structure de données,

1173
00:50:43,088 --> 00:50:46,390
car il est toujours au fond ou
équivalente il est toujours à l'arrière.

1174
00:50:46,390 --> 00:50:50,407
>> Mais il ya une autre façon de penser
alignant données et par exemple, cela.

1175
00:50:50,407 --> 00:50:53,490
Si vous êtes une de ces personnes qui aime
d'aligner à l'extérieur de magasins Apple

1176
00:50:53,490 --> 00:50:55,610
quand un nouveau produit est livré
, vous êtes probablement

1177
00:50:55,610 --> 00:50:58,780
ne pas utiliser une pile de données
la structure parce que vous

1178
00:50:58,780 --> 00:51:03,070
aliénerait tout le monde qui est
la queue pour acheter un nouveau jouet.

1179
00:51:03,070 --> 00:51:06,610
Au contraire, vous êtes probablement à l'aide
quel type de structure de données

1180
00:51:06,610 --> 00:51:10,050
ou ce genre de système
dans le monde réel?

1181
00:51:10,050 --> 00:51:13,493
Espérons que cela est une ligne, ou plus
correctement ou plus Colombie-like, une file d'attente.

1182
00:51:13,493 --> 00:51:17,700
Et il se trouve une file d'attente est également un
structure de données en informatique,

1183
00:51:17,700 --> 00:51:19,700
mais une file d'attente a une très
propriété différente.

1184
00:51:19,700 --> 00:51:20,820
Il est pas LIFO.

1185
00:51:20,820 --> 00:51:21,990
Dernier entré, premier sorti.

1186
00:51:21,990 --> 00:51:22,800
Dieu pardonne.

1187
00:51:22,800 --> 00:51:24,280
Il est à la place FIFO.

1188
00:51:24,280 --> 00:51:26,110
Premier entré, premier sorti.

1189
00:51:26,110 --> 00:51:27,970
Et cela est une bonne chose
pour l'équité 'amour

1190
00:51:27,970 --> 00:51:30,428
certainement lorsque vous doublure
jusqu'à super tôt dans la matinée.

1191
00:51:30,428 --> 00:51:33,400
Si vous y arrivez d'abord, vous
vouloir sortir premier ainsi.

1192
00:51:33,400 --> 00:51:35,880
>> Et si toutes ces données
les structures, les files d'attente et des piles

1193
00:51:35,880 --> 00:51:39,220
et grappes d'autrui, se révèle vous
peut considérer cela comme un simple tableau.

1194
00:51:39,220 --> 00:51:41,820
Ceci est un tableau, peut-être
une taille fixe 4, mais ce serait

1195
00:51:41,820 --> 00:51:44,990
être une sorte de bien si nous pouvions juste empiler
plateaux presque infiniment grand si nous

1196
00:51:44,990 --> 00:51:46,780
avoir autant de plateaux ou des numéros.

1197
00:51:46,780 --> 00:51:48,840
Alors peut-être que nous voulons
utiliser une liste liée ici,

1198
00:51:48,840 --> 00:51:51,800
mais le compromis va être
potentiellement que nous avons besoin de plus de mémoire,

1199
00:51:51,800 --> 00:51:55,930
prend un peu plus de temps, mais nous
ne limitent pas la hauteur de la pile,

1200
00:51:55,930 --> 00:51:59,550
un peu comme la vitrine de Mather
peut limiter la taille de la pile,

1201
00:51:59,550 --> 00:52:03,117
et ce sont donc des décisions de conception ou
options disponibles pour nous en fin de compte.

1202
00:52:03,117 --> 00:52:04,950
Donc, avec ces données
structures, nous avons commencé

1203
00:52:04,950 --> 00:52:09,360
voir de nouvelles limites supérieures potentiellement
sur ce qui était auparavant super rapide

1204
00:52:09,360 --> 00:52:11,260
et où nous partirons
off aujourd'hui et où

1205
00:52:11,260 --> 00:52:13,200
nous espérons obtenir à
est le mercredi, nous allons

1206
00:52:13,200 --> 00:52:15,740
commencer à regarder une donnée
structure qui nous permet de chercher

1207
00:52:15,740 --> 00:52:18,260
grâce à des données dans le journal l'heure de fin de nouveau.

1208
00:52:18,260 --> 00:52:21,470
Et nous avons vu que, rappelons-le, à la semaine zéro
et l'autre avec la recherche binaire ou fracture

1209
00:52:21,470 --> 00:52:22,180
et conquérir.

1210
00:52:22,180 --> 00:52:26,240
Il va revenir et, mieux encore,
le Saint-Graal pour ce mercredi

1211
00:52:26,240 --> 00:52:29,510
sera à venir avec la
structure de données qui fonctionne réellement

1212
00:52:29,510 --> 00:52:32,070
ou théoriquement
constante de temps, de sorte que

1213
00:52:32,070 --> 00:52:34,760
il n'a pas d'importance combien de
millions ou des milliards de choses

1214
00:52:34,760 --> 00:52:38,470
nous avons dans la structure de données, il sera
nous prendre constante de temps, peut-être une étape

1215
00:52:38,470 --> 00:52:41,387
ou deux étapes ou 10 étapes,
mais un nombre constant d'étapes

1216
00:52:41,387 --> 00:52:42,970
de recherche à travers cette structure de données.

1217
00:52:42,970 --> 00:52:46,300
Ce sera en effet le Saint Graal
mais plus sur que le mercredi.

1218
00:52:46,300 --> 00:52:49,045
See ya ensuite.

1219
00:52:49,045 --> 00:52:53,704
>> [Jouer de la musique]

1220
00:52:53,704 --> 00:56:08,448