1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:11,137
[MUSIQUE LECTURE]

3
00:00:11,137 --> 00:00:12,220
DAVID J. Malan: Très bien.

4
00:00:12,220 --> 00:00:13,950
C'est CS50.

5
00:00:13,950 --> 00:00:18,560
C'est la semaine de cinq continué, et nous
de bonnes nouvelles et de mauvaises nouvelles.

6
00:00:18,560 --> 00:00:21,140
Donc, de bonnes nouvelles, c'est que CS50
lance ce vendredi.

7
00:00:21,140 --> 00:00:24,430
Si vous souhaitez vous joindre à nous,
la tête de l'URL d'habitude ici.

8
00:00:24,430 --> 00:00:28,670
Nouvelles encore meilleures, pas exposé
lundi prochain le 13.

9
00:00:28,670 --> 00:00:31,970
Un peu moins de meilleures nouvelles,
questionnaire zéro est mercredi prochain.

10
00:00:31,970 --> 00:00:33,840
Plus de détails peuvent être
trouvé à l'adresse ici.

11
00:00:33,840 --> 00:00:36,340
Et au cours des deux prochains jours
nous allons remplir les blancs

12
00:00:36,340 --> 00:00:39,234
en ce qui concerne les chambres
que nous avons réservé.

13
00:00:39,234 --> 00:00:41,400
De meilleures nouvelles, c'est qu'il ya aurez
une révision des cours à l'échelle

14
00:00:41,400 --> 00:00:43,570
séance prochain
Lundi dans la soirée.

15
00:00:43,570 --> 00:00:46,270
Restez à l'écoute pour le cours de
site pour l'emplacement et les détails.

16
00:00:46,270 --> 00:00:49,290
Les articles, même si elle est un
vacances, rencontrera également ainsi.

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
Meilleures nouvelles, lecture vendredi prochain.

19
00:00:52,940 --> 00:00:56,220
Il s'agit donc d'une tradition de nous
avoir, selon le programme.

20
00:00:56,220 --> 00:00:58,100
Just-- ça va être incroyable.

21
00:00:58,100 --> 00:01:02,510
Vous allez voir des choses comme
structures de données de temps constant

22
00:01:02,510 --> 00:01:04,730
des tables et des arbres et des essais hachage.

23
00:01:04,730 --> 00:01:07,150
Et nous allons parler de problèmes d'anniversaire.

24
00:01:07,150 --> 00:01:09,440
Tout un tas de choses
attend vendredi prochain.

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
Dáccord.

27
00:01:12,200 --> 00:01:13,190
Quoi qu'il en soit.

28
00:01:13,190 --> 00:01:17,080
>> Donc, rappelons que nous avons été
en se concentrant sur cette image de ce qui est

29
00:01:17,080 --> 00:01:18,980
l'intérieur de la mémoire de notre ordinateur.

30
00:01:18,980 --> 00:01:22,875
Donc, la mémoire vive ou RAM est l'endroit où les programmes
exister alors que vous êtes les exécuter.

31
00:01:22,875 --> 00:01:25,215
Si vous double-cliquez sur un
icône pour exécuter un programme

32
00:01:25,215 --> 00:01:27,520
ou double-cliquez sur un
icône pour ouvrir certains fichiers,

33
00:01:27,520 --> 00:01:30,430
il est chargé de votre disque
conduire ou lecteur à état solide

34
00:01:30,430 --> 00:01:34,190
dans la RAM, Random Access Memory, où
il vit jusqu'à ce qu'il s'éteigne,

35
00:01:34,190 --> 00:01:36,700
le couvercle se ferme pour ordinateur portable,
ou vous quittez le programme.

36
00:01:36,700 --> 00:01:38,960
>> Maintenant que la mémoire, de
qui vous avez probablement

37
00:01:38,960 --> 00:01:41,950
1 gigaoctet ces jours, 2
gigaoctets, voire beaucoup plus,

38
00:01:41,950 --> 00:01:44,420
est généralement aménagé
pour un programme donné

39
00:01:44,420 --> 00:01:47,170
dans ce genre de forme rectangulaire
modèle conceptuel

40
00:01:47,170 --> 00:01:50,860
lequel nous avons la pile au fond
et un tas d'autres choses en tête.

41
00:01:50,860 --> 00:01:53,140
La chose au sommet
nous avons vu sur cette photo

42
00:01:53,140 --> 00:01:55,670
mais jamais parlé
est le segment dit le texte.

43
00:01:55,670 --> 00:01:58,419
segment de texte est juste une façon élégante
de dire les zéros et de uns que

44
00:01:58,419 --> 00:02:01,150
composer votre programme compilé réelle.

45
00:02:01,150 --> 00:02:03,910
>> Ainsi, lorsque vous double-cliquez sur
Microsoft Word sur votre Mac ou PC,

46
00:02:03,910 --> 00:02:08,030
ou lorsque vous exécutez point slash Mario sur un
Ordinateur Linux à votre fenêtre de terminal,

47
00:02:08,030 --> 00:02:12,460
les zéros et de uns qui composent
Word ou Mario sont stockés temporairement

48
00:02:12,460 --> 00:02:16,610
dans la mémoire vive de votre ordinateur dans la soi-disant
segment de texte pour un programme particulier.

49
00:02:16,610 --> 00:02:19,080
Ci-dessous, qui va initialisé
et les données non initialisées.

50
00:02:19,080 --> 00:02:22,655
Ce sont des choses comme des variables globales,
que nous n'avons pas utilisé beaucoup de,

51
00:02:22,655 --> 00:02:24,910
mais à l'occasion, nous avons
eu des variables globales

52
00:02:24,910 --> 00:02:28,819
ou statique des chaînes définies que
est dur mots comme "bonjour" codé

53
00:02:28,819 --> 00:02:31,860
qui ne sont pas pris en de l'utilisateur
qui sont codés en dur dans votre programme.

54
00:02:31,860 --> 00:02:34,230
>> Maintenant, au bas nous
disposer la pile dite.

55
00:02:34,230 --> 00:02:37,665
Et la pile, jusqu'à présent, nous avons été
à l'aide de quels types de besoins?

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
Qu'est-ce la pile été utilisé?

58
00:02:40,997 --> 00:02:41,160
Ouais?

59
00:02:41,160 --> 00:02:42,070
>> PUBLIC: Fonctions.

60
00:02:42,070 --> 00:02:43,320
>> DAVID J. Malan: Pour les fonctions?

61
00:02:43,320 --> 00:02:44,980
Dans quel sens pour les fonctions?

62
00:02:44,980 --> 00:02:48,660
>> PUBLIC: Lorsque vous appelez une fonction, la
arguments sont copiés sur la pile.

63
00:02:48,660 --> 00:02:49,660
>> DAVID J. Malan: Exactement.

64
00:02:49,660 --> 00:02:52,650
Lorsque vous appelez une fonction, son
arguments sont copiés sur la pile.

65
00:02:52,650 --> 00:02:56,330
Ainsi, tout les X ou Y ou de A ou de B
que vous êtes de passage dans une fonction

66
00:02:56,330 --> 00:02:58,680
sont temporairement mis sur
la dite pile,

67
00:02:58,680 --> 00:03:02,000
comme l'un des Annenberg
plateaux de la salle à manger, et aussi des choses

68
00:03:02,000 --> 00:03:03,190
comme les variables locales.

69
00:03:03,190 --> 00:03:06,290
Si votre fonction foo ou votre échange
fonction des variables locales ont,

70
00:03:06,290 --> 00:03:08,602
comme température, ces deux
retrouver dans la pile.

71
00:03:08,602 --> 00:03:11,560
Maintenant, nous ne serons pas trop parler
, mais ces variables d'environnement

72
00:03:11,560 --> 00:03:15,690
en bas, nous avons vu tout à l'heure quand
Je suis futzing au clavier un jour

73
00:03:15,690 --> 00:03:20,050
et j'ai commencé à accéder à des choses
comme argv 100 ou argv 1000,

74
00:03:20,050 --> 00:03:22,320
juste elements-- j'oublie
mais que la numbers--

75
00:03:22,320 --> 00:03:24,330
n'étaient pas censés être consultée par moi.

76
00:03:24,330 --> 00:03:26,581
Nous avons commencé à voir quelques-uns
symboles funky, sur l'écran.

77
00:03:26,581 --> 00:03:28,330
C'était soi-disant
variables d'environnement

78
00:03:28,330 --> 00:03:32,390
comme paramètres globaux pour mon
programme ou pour mon ordinateur, pas

79
00:03:32,390 --> 00:03:37,090
rien à voir avec la récente
bug que nous avons discuté,

80
00:03:37,090 --> 00:03:39,670
Shellshock, que cela a été
dont souffre un très petit nombre d'ordinateurs.

81
00:03:39,670 --> 00:03:42,960
>> Maintenant, enfin, dans la mise au point d'aujourd'hui
nous allons finalement être sur le tas.

82
00:03:42,960 --> 00:03:44,864
Ceci est un autre morceau de la mémoire.

83
00:03:44,864 --> 00:03:47,030
Et tout cela fondamentalement
mémoire est la même chose.

84
00:03:47,030 --> 00:03:48,040
C'est le même matériel.

85
00:03:48,040 --> 00:03:49,956
Nous sommes juste une sorte de
le traitement de différents groupes

86
00:03:49,956 --> 00:03:51,460
d'octets à des fins différentes.

87
00:03:51,460 --> 00:03:56,540
Le tas va également être le cas
variables et la mémoire que vous demandez

88
00:03:56,540 --> 00:03:58,810
à partir du système d'exploitation
est temporairement stockée.

89
00:03:58,810 --> 00:04:01,890
>> Mais il ya une sorte de problème
ici, que l'image implique.

90
00:04:01,890 --> 00:04:05,261
Nous avons sorte de deux
navires sur le point d'entrer en collision.

91
00:04:05,261 --> 00:04:08,010
Parce que, comme vous utilisez de plus en plus
de la pile, et comme nous le voyons aujourd'hui

92
00:04:08,010 --> 00:04:11,800
avant, que vous utilisez de plus en plus de la
tas, sans doute de mauvaises choses peuvent se produire.

93
00:04:11,800 --> 00:04:15,054
Et en effet, nous pouvons induire que
intentionnellement ou non.

94
00:04:15,054 --> 00:04:16,970
Ainsi, le cliffhanger dernier
temps était de ce programme,

95
00:04:16,970 --> 00:04:20,570
qui ne sert pas tout fonctionnelle
autre but que de démontrer

96
00:04:20,570 --> 00:04:24,750
comment vous comme un mauvais gars peut effectivement prendre
avantage de bogues dans le programme de quelqu'un

97
00:04:24,750 --> 00:04:28,460
et prendre en charge un programme ou même une
Système d'ordinateur serveur ou ensemble.

98
00:04:28,460 --> 00:04:31,660
Il suffit donc de regarder brièvement, vous
remarquer que le principal en bas

99
00:04:31,660 --> 00:04:34,510
prend en ligne de commande
arguments, comme par argv.

100
00:04:34,510 --> 00:04:38,480
Et elle a un appel à une fonction f,
essentiellement une fonction anonyme appelée

101
00:04:38,480 --> 00:04:40,250
f, et c'est en passant dans argv [1].

102
00:04:40,250 --> 00:04:43,960
>> Donc, quelles que soient les mot types d'utilisateurs dans au
l'invite après le nom de ce programme,

103
00:04:43,960 --> 00:04:49,310
et alors cette fonction arbitraire jusqu'à
haut, f, prend dans une chaîne, Alias ​​char *,

104
00:04:49,310 --> 00:04:51,720
comme nous avons commencé à discuter,
et il appelle simplement qu'il «bar».

105
00:04:51,720 --> 00:04:53,310
Mais nous pourrions appeler ça.

106
00:04:53,310 --> 00:04:57,470
Et puis, il déclare, à l'intérieur
de f, un tableau de caractères

107
00:04:57,470 --> 00:04:59,930
appelé c-- ces 12 caractères.

108
00:04:59,930 --> 00:05:03,580
>> Maintenant, par l'histoire que je racontais
il ya un moment, où dans la mémoire

109
00:05:03,580 --> 00:05:06,720
c est, ou sont ces 12
Chars va finir?

110
00:05:06,720 --> 00:05:07,570
Juste pour être clair.

111
00:05:07,570 --> 00:05:08,070
Ouais?

112
00:05:08,070 --> 00:05:08,590
>> PUBLIC: Sur la pile.

113
00:05:08,590 --> 00:05:09,420
>> DAVID J. Malan: Sur la pile.

114
00:05:09,420 --> 00:05:10,720
Donc, c est une variable locale.

115
00:05:10,720 --> 00:05:14,079
Nous demandons 12 caractères ou 12 octets.

116
00:05:14,079 --> 00:05:16,120
Ceux vont finir par
sur la pile dite.

117
00:05:16,120 --> 00:05:18,530
Maintenant, enfin, est cette autre fonction
c'est en fait très utile,

118
00:05:18,530 --> 00:05:20,571
mais nous ne l'avons pas vraiment utilisé
nous-mêmes, strncopy.

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
Cela signifie copie de chaîne, mais
que n lettres, n caractères.

121
00:05:25,200 --> 00:05:31,990
Alors n caractères seront
copié de bar au c.

122
00:05:31,990 --> 00:05:32,980
Et combien?

123
00:05:32,980 --> 00:05:34,110
La longueur de la barre.

124
00:05:34,110 --> 00:05:36,330
En d'autres termes, que
une ligne, strncopy,

125
00:05:36,330 --> 00:05:39,500
va copier
bar efficacement à c.

126
00:05:39,500 --> 00:05:42,340
>> Maintenant, juste sorte de prévoir
la morale de cette histoire,

127
00:05:42,340 --> 00:05:44,750
ce qui est potentiellement problématique ici?

128
00:05:44,750 --> 00:05:49,710
Même si nous vérifions la longueur
de bar et passer dans strncopy,

129
00:05:49,710 --> 00:05:53,145
Quelle est votre intestin vous dit est
encore cassé sur ce programme?

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
Ouais?

132
00:05:55,220 --> 00:05:57,491
>> PUBLIC: Ne comprend pas
salle pour le caractère nul.

133
00:05:57,491 --> 00:05:59,990
DAVID J. Malan: Ne comprend pas
salle pour le caractère nul.

134
00:05:59,990 --> 00:06:02,073
Potentiellement, contrairement à
la pratique passée, nous n'avons pas encore

135
00:06:02,073 --> 00:06:04,810
avoir autant comme un atout 1 à
tenir compte de ce caractère nul.

136
00:06:04,810 --> 00:06:06,649
Mais c'est encore pire que cela.

137
00:06:06,649 --> 00:06:07,940
Que sommes nous n'arrivons pas à faire?

138
00:06:07,940 --> 00:06:08,432
Ouais?

139
00:06:08,432 --> 00:06:09,307
>> PUBLIC: [inaudible]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
DAVID J. Malan: Parfait.

142
00:06:16,440 --> 00:06:18,490
Nous avons codé en dur 12 assez arbitraire.

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
Ce n'est pas tant la
problème, mais le fait

145
00:06:21,330 --> 00:06:25,630
que nous ne sommes même pas vérifier si
la longueur de la barre est inférieure à 12,

146
00:06:25,630 --> 00:06:28,530
dans ce cas, il va être
sûr de le mettre dans la mémoire

147
00:06:28,530 --> 00:06:30,260
appelé c que nous avons prévu.

148
00:06:30,260 --> 00:06:32,960
En effet, si la barre est comme
20 caractères,

149
00:06:32,960 --> 00:06:39,010
cette fonction semble être la copie
20 caractères de bar en c, ce qui

150
00:06:39,010 --> 00:06:41,310
prendre au moins 8 octets
qu'il ne doit pas l'être.

151
00:06:41,310 --> 00:06:42,690
C'est l'implication ici.

152
00:06:42,690 --> 00:06:44,347
>> Donc, en résumé, le programme cassé.

153
00:06:44,347 --> 00:06:45,180
Pas une grosse affaire.

154
00:06:45,180 --> 00:06:46,360
Peut-être vous obtenez une erreur de segmentation.

155
00:06:46,360 --> 00:06:47,651
Nous avons tous eu des bugs dans les programmes.

156
00:06:47,651 --> 00:06:50,196
Nous pourrions tous avoir des bugs
dans les programmes dès maintenant.

157
00:06:50,196 --> 00:06:51,320
Mais quelle est la conséquence?

158
00:06:51,320 --> 00:06:54,390
Eh bien, voici une version zoomée de
que l'image de la mémoire de mon ordinateur.

159
00:06:54,390 --> 00:06:56,230
C'est le bas de ma pile.

160
00:06:56,230 --> 00:06:59,644
Et en effet, tout au fond est ce qui est
appelé pile routine parent, façon élégante

161
00:06:59,644 --> 00:07:00,560
de dire que c'est principale.

162
00:07:00,560 --> 00:07:03,772
Alors que celui qui appelle la fonction
f que nous parlons.

163
00:07:03,772 --> 00:07:05,230
C'est donc la partie inférieure de la pile.

164
00:07:05,230 --> 00:07:06,640
L'adresse de retour est quelque chose de nouveau.

165
00:07:06,640 --> 00:07:08,810
Il a toujours été là,
toujours été dans cette image.

166
00:07:08,810 --> 00:07:10,440
Nous n'avons jamais attiré l'attention sur elle.

167
00:07:10,440 --> 00:07:15,290
Parce qu'il s'avère que le chemin c fonctionne est
que quand une fonction appelle une autre,

168
00:07:15,290 --> 00:07:18,780
non seulement les arguments que
fonction se poussé sur la pile,

169
00:07:18,780 --> 00:07:22,470
non seulement locale de la fonction
les variables sont poussés sur la pile,

170
00:07:22,470 --> 00:07:26,820
quelque chose qui s'appelle une adresse de retour
obtient également mis sur la pile.

171
00:07:26,820 --> 00:07:33,330
Plus précisément, si les appels principaux Foo, principaux de
propre adresse dans la mémoire, bœuf quelque chose,

172
00:07:33,330 --> 00:07:38,240
efficace qui est mis sur la pile
de sorte que lorsque f est fait exécuter

173
00:07:38,240 --> 00:07:43,630
sait où pour revenir en arrière dans le texte
segment, afin de poursuivre l'exécution.

174
00:07:43,630 --> 00:07:47,760
>> Donc, si nous sommes ici sur le plan conceptuel,
en principal, alors f est appelée.

175
00:07:47,760 --> 00:07:50,200
Comment savoir qui f
au contrôle de la main en arrière?

176
00:07:50,200 --> 00:07:52,020
Eh bien, ce petit
Ariane en rouge ici,

177
00:07:52,020 --> 00:07:54,978
appelé l'adresse de retour, il suffit
contrôles, ce qui est ce que l'adresse de retour?

178
00:07:54,978 --> 00:07:57,039
Oh, laissez-moi revenir au principal ici.

179
00:07:57,039 --> 00:07:59,080
Et c'est un peu
d'une simplification,

180
00:07:59,080 --> 00:08:00,750
parce que les zéros et de uns
pour principal sont techniquement

181
00:08:00,750 --> 00:08:01,967
ici dans le segment de la technologie.

182
00:08:01,967 --> 00:08:03,800
Mais c'est l'idée. fa
a juste besoin de savoir ce que

183
00:08:03,800 --> 00:08:06,680
à l'endroit où le contrôle va finalement de retour.

184
00:08:06,680 --> 00:08:09,790
>> Mais la façon dont les ordinateurs
ont longtemps posé des choses

185
00:08:09,790 --> 00:08:12,320
comme les variables locales et
arguments est comme ça.

186
00:08:12,320 --> 00:08:17,180
Ainsi, dans le haut de cette image dans
bleu est le cadre de pile pour f, de sorte que tous

187
00:08:17,180 --> 00:08:19,630
de la mémoire que f
est précisément à l'aide.

188
00:08:19,630 --> 00:08:22,990
Ainsi donc, vous remarquerez que
bar est dans cette image.

189
00:08:22,990 --> 00:08:23,980
Bar était son argument.

190
00:08:23,980 --> 00:08:27,240
Et nous avons réclamé que les arguments de
fonctions sont poussés sur la pile.

191
00:08:27,240 --> 00:08:29,910
Et C, bien sûr, est
aussi dans cette image.

192
00:08:29,910 --> 00:08:33,520
>> Et seulement à des fins de notation,
remarquer dans le coin supérieur gauche

193
00:08:33,520 --> 00:08:37,020
est ce que serait c support 0 et
ensuite légèrement vers le bas vers la droite

194
00:08:37,020 --> 00:08:38,220
c est le support 11.

195
00:08:38,220 --> 00:08:41,240
En d'autres termes, vous pouvez l'imaginer
qu'il ya une grille d'octets

196
00:08:41,240 --> 00:08:44,380
y, qui est d'abord
en haut à gauche, en bas de laquelle

197
00:08:44,380 --> 00:08:48,360
est la dernière de ces 12 octets.

198
00:08:48,360 --> 00:08:49,930
>> Mais maintenant essayer d'avancer rapidement.

199
00:08:49,930 --> 00:08:55,580
Qu'est-ce qui va se passer si nous passons
dans un bar de chaîne qui est plus long que c?

200
00:08:55,580 --> 00:08:59,130
Et nous ne sommes pas vérifier si
il est en effet plus que 12.

201
00:08:59,130 --> 00:09:03,146
Quelle partie de cette image va
écrasés par les octets 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, puis
mauvais, 12, 13 à 19?

203
00:09:07,890 --> 00:09:11,820
Qu'est-ce qui va se passer ici,
si vous déduisez de la commande

204
00:09:11,820 --> 00:09:14,790
c 0 que le support est sur le dessus
et c support 11 est une sorte de duvet

205
00:09:14,790 --> 00:09:15,812
vers la droite?

206
00:09:15,812 --> 00:09:16,796
Ouais?

207
00:09:16,796 --> 00:09:19,260
>> PUBLIC: Eh bien, il va
pour remplacer la barre char *.

208
00:09:19,260 --> 00:09:22,260
>> DAVID J. Malan: Ouais, on dirait
vous allez écraser l'omble bar *.

209
00:09:22,260 --> 00:09:26,245
Et pire, si vous envoyez dans un très long
chaîne, vous pourriez même remplacer quoi?

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
L'adresse de retour.

212
00:09:28,570 --> 00:09:31,380
Qui encore une fois, c'est comme un
navigation pour indiquer au programme où

213
00:09:31,380 --> 00:09:34,060
pour revenir au moment où f
se fait appelé.

214
00:09:34,060 --> 00:09:37,140
>> Alors, que les méchants font généralement
est si ils viennent à travers un programme

215
00:09:37,140 --> 00:09:41,290
qu'ils sont curieux de savoir si c'est
exploitable, poussette de manière

216
00:09:41,290 --> 00:09:43,550
qu'il ou elle peut prendre
avantage de ce bug,

217
00:09:43,550 --> 00:09:45,720
en général, ils ne reçoivent pas
ce droit la première fois.

218
00:09:45,720 --> 00:09:48,590
Ils commencent juste à envoyer, par exemple,
chaînes aléatoires dans votre programme,

219
00:09:48,590 --> 00:09:50,260
soit au clavier,
ou franchement ils ont probablement

220
00:09:50,260 --> 00:09:52,740
écrire un petit programme à juste
génèrent automatiquement des chaînes,

221
00:09:52,740 --> 00:09:55,430
et commencer à taper sur votre programme par
envoi en lots de différentes entrées

222
00:09:55,430 --> 00:09:56,340
à des longueurs différentes.

223
00:09:56,340 --> 00:09:58,990
>> Dès que votre programme plante,
c'est une chose étonnante.

224
00:09:58,990 --> 00:10:01,020
Parce que cela signifie qu'il
ou elle a découvert

225
00:10:01,020 --> 00:10:02,660
ce qui est probablement en effet un bug.

226
00:10:02,660 --> 00:10:05,830
Et puis ils peuvent obtenir plus intelligent
et commencer à se concentrer plus étroitement

227
00:10:05,830 --> 00:10:07,420
sur la façon d'exploiter ce bug.

228
00:10:07,420 --> 00:10:11,480
En particulier, ce qu'il ou elle pourrait
faire est d'envoyer, dans le meilleur des cas, bonjour.

229
00:10:11,480 --> 00:10:12,210
No big deal.

230
00:10:12,210 --> 00:10:14,750
C'est une chaîne qui est suffisamment court.

231
00:10:14,750 --> 00:10:18,100
Mais que faire si il ou elle envoie,
et nous généralisons comme,

232
00:10:18,100 --> 00:10:20,890
attaque code-- si zéros
et ceux qui font des choses

233
00:10:20,890 --> 00:10:25,150
comme rm-rf, que retirer tout
depuis le disque dur ou envoyer du spam

234
00:10:25,150 --> 00:10:27,000
ou en quelque sorte attaquer la machine?

235
00:10:27,000 --> 00:10:29,570
>> Ainsi, si chacun de ces
lettres A représente juste,

236
00:10:29,570 --> 00:10:32,380
conceptuellement, attaque, attaque,
attaque, attaque, certains mauvais code

237
00:10:32,380 --> 00:10:36,410
que quelqu'un d'autre a écrit, mais
si cette personne est assez intelligent

238
00:10:36,410 --> 00:10:40,790
non seulement inclure tous
de ces RM-RFS, mais aussi

239
00:10:40,790 --> 00:10:46,100
voir ses dernières octets
un nombre qui correspond

240
00:10:46,100 --> 00:10:50,540
à l'adresse de son
ou son propre code d'attaque

241
00:10:50,540 --> 00:10:53,820
qu'il ou elle a passé en tout
en fournissant à l'invite,

242
00:10:53,820 --> 00:10:58,760
vous pouvez effectivement tromper l'ordinateur
en remarquant lorsque f est faite d'exécution,

243
00:10:58,760 --> 00:11:02,400
oh, il est temps pour moi de sauter
retourner à l'adresse de retour rouge.

244
00:11:02,400 --> 00:11:06,070
Mais parce qu'il ou elle a en quelque sorte
chevauchement que l'adresse de retour

245
00:11:06,070 --> 00:11:09,602
avec leur propre numéro,
et ils sont assez intelligents

246
00:11:09,602 --> 00:11:11,560
avoir configuré que
nombre de renvoyer, comme vous

247
00:11:11,560 --> 00:11:13,740
voir dans le super top
coin gauche là,

248
00:11:13,740 --> 00:11:18,020
l'adresse réelle de l'ordinateur de
la mémoire de certains de leur code d'attaque,

249
00:11:18,020 --> 00:11:21,740
un méchant peut tromper l'ordinateur
dans l'exécution de son propre code.

250
00:11:21,740 --> 00:11:23,700
>> Et ce code, encore une fois, peut être n'importe quoi.

251
00:11:23,700 --> 00:11:26,120
Il est généralement appelé
Code coquille, qui est juste

252
00:11:26,120 --> 00:11:29,030
une façon de dire que ce n'est pas
généralement quelque chose d'aussi simple que rm-rf.

253
00:11:29,030 --> 00:11:32,340
C'est en fait quelque chose comme Bash,
ou un programme réel qui lui donne

254
00:11:32,340 --> 00:11:37,230
ou son contrôle programmatique pour exécuter
toute autre chose qu'ils veulent.

255
00:11:37,230 --> 00:11:40,210
Donc en bref, tout cela
découle du simple fait

256
00:11:40,210 --> 00:11:44,490
que ce bug ne vérifiant pas impliqué
les limites de votre réseau.

257
00:11:44,490 --> 00:11:47,250
Et parce que la façon
les ordinateurs fonctionnent, c'est qu'ils

258
00:11:47,250 --> 00:11:49,430
utiliser la pile de
efficace, sur le plan conceptuel,

259
00:11:49,430 --> 00:11:54,830
bas sur place, mais alors les éléments
vous appuyez sur la pile croître de haut en bas,

260
00:11:54,830 --> 00:11:56,624
c'est incroyablement difficile.

261
00:11:56,624 --> 00:11:58,290
Maintenant, il ya des façons de contourner cela.

262
00:11:58,290 --> 00:12:00,800
Et franchement, il ya des langues
avec lesquelles travailler autour de cela.

263
00:12:00,800 --> 00:12:03,100
Java est à l'abri, par exemple,
à cette question.

264
00:12:03,100 --> 00:12:04,110
Parce qu'ils ne vous donnent pas des pointeurs.

265
00:12:04,110 --> 00:12:05,943
Ils ne vous donnent pas
adresses de mémoire directs.

266
00:12:05,943 --> 00:12:08,560
Donc, avec ce pouvoir que nous avons
de toucher quoi que ce soit dans la mémoire

267
00:12:08,560 --> 00:12:11,580
nous voulons vient, certes, de grands risques.

268
00:12:11,580 --> 00:12:12,430
>> Alors gardez un œil sur.

269
00:12:12,430 --> 00:12:14,596
Si, franchement, dans les mois
ou les années à venir, à tout moment

270
00:12:14,596 --> 00:12:17,740
vous découvrirez certains exploitation
d'un programme ou d'un serveur,

271
00:12:17,740 --> 00:12:22,370
si jamais vous voyez un soupçon de quelque chose
comme une attaque par débordement de tampon,

272
00:12:22,370 --> 00:12:25,390
ou débordement de pile est un autre type
d'attaque, dans le même esprit,

273
00:12:25,390 --> 00:12:28,770
inspire autant que le site Web de
nom, si vous le savez,

274
00:12:28,770 --> 00:12:33,170
il est tout simplement parler
débordant de la taille de caractère certain

275
00:12:33,170 --> 00:12:36,200
tableau ou d'un tableau plus général.

276
00:12:36,200 --> 00:12:38,822
Toutes les questions, puis, à ce sujet?

277
00:12:38,822 --> 00:12:39,780
N'essayez pas ceci à la maison.

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> Bien.

280
00:12:42,300 --> 00:12:47,270
Donc malloc a été jusqu'ici notre nouveau
ami en qui nous pouvons allouer de la mémoire

281
00:12:47,270 --> 00:12:50,540
que nous ne savons pas nécessairement dans
avance que nous voulons si nous n'avons pas

282
00:12:50,540 --> 00:12:52,920
de coder en dur dans notre
numéros de programme comme 12.

283
00:12:52,920 --> 00:12:55,550
Une fois que l'utilisateur indique dans quelle mesure
données qu'il ou elle veut à l'entrée,

284
00:12:55,550 --> 00:12:58,000
nous pouvons malloc que beaucoup de mémoire.

285
00:12:58,000 --> 00:13:01,484
>> Donc malloc il s'avère, à l'
mesure où nous l'avons utilisé,

286
00:13:01,484 --> 00:13:03,900
explicitement la dernière fois, puis
vous les gars l'ont utilisé

287
00:13:03,900 --> 00:13:08,160
pour GETSTRING inconsciemment pour
plusieurs semaines, tous de la mémoire malloc

288
00:13:08,160 --> 00:13:09,820
vient du tas dite.

289
00:13:09,820 --> 00:13:13,852
Et c'est pourquoi getString, par exemple,
peut allouer de la mémoire dynamiquement

290
00:13:13,852 --> 00:13:16,060
sans savoir ce que vous êtes
aller taper à l'avance,

291
00:13:16,060 --> 00:13:21,520
vous restituer un pointeur vers la mémoire,
et que la mémoire est toujours la vôtre à garder,

292
00:13:21,520 --> 00:13:24,080
même après GETSTRING rendements.

293
00:13:24,080 --> 00:13:27,450
Parce que d'un rappel après tout ce que l'
pile est constamment monter et descendre,

294
00:13:27,450 --> 00:13:27,950
de haut en bas.

295
00:13:27,950 --> 00:13:30,230
Et dès qu'il va
vers le bas, cela signifie que toute la mémoire

296
00:13:30,230 --> 00:13:33,030
cette fonction utilisée doit
pas être utilisé par quelqu'un d'autre.

297
00:13:33,030 --> 00:13:34,570
C'est des valeurs parasites maintenant.

298
00:13:34,570 --> 00:13:36,120
>> Mais le tas est ici.

299
00:13:36,120 --> 00:13:39,360
Et ce qui est bien, c'est que malloc
lorsque malloc alloue de la mémoire ici,

300
00:13:39,360 --> 00:13:42,070
il n'est pas affecté par la
en grande partie, par la pile.

301
00:13:42,070 --> 00:13:46,000
Et si toute fonction peut accéder
mémoire qui a été malloc'd,

302
00:13:46,000 --> 00:13:49,120
même par une fonction comme getString,
même après avoir été retourné.

303
00:13:49,120 --> 00:13:51,700
>> Maintenant, c'est l'inverse de malloc est libre.

304
00:13:51,700 --> 00:13:53,900
Et en effet, la règle que vous
doivent commencer à adopter

305
00:13:53,900 --> 00:13:58,950
est tout, tout, chaque fois que vous utilisez malloc
vous devez vous utiliser gratuitement, par la suite,

306
00:13:58,950 --> 00:14:00,280
sur ce même pointeur.

307
00:14:00,280 --> 00:14:03,289
Tout ce temps nous avons écrit
buggy, du code bogué, pour de nombreuses raisons.

308
00:14:03,289 --> 00:14:05,580
Mais dont l'un a été
en utilisant la bibliothèque CS50, qui

309
00:14:05,580 --> 00:14:09,010
lui-même est délibérément
buggy, il perd de la mémoire.

310
00:14:09,010 --> 00:14:11,410
Chaque fois que vous avez appelé getString
au cours des dernières semaines

311
00:14:11,410 --> 00:14:13,870
nous demandons au fonctionnement
système, Linux, pour mémoire.

312
00:14:13,870 --> 00:14:15,780
Et vous n'avez jamais donné une fois de retour.

313
00:14:15,780 --> 00:14:17,730
Et ce n'est pas, en
pratique, une bonne chose.

314
00:14:17,730 --> 00:14:20,330
>> Et Valgrind, l'un des
outils introduits dans Pset 4,

315
00:14:20,330 --> 00:14:22,900
est tout de vous aider
maintenant trouver des bogues comme ça.

316
00:14:22,900 --> 00:14:27,060
Mais heureusement pour Pset 4 vous n'avez pas besoin
d'utiliser la bibliothèque de CS50 ou getString.

317
00:14:27,060 --> 00:14:31,220
Donc, tous les bogues liés à la mémoire sont
en fin de compte va être votre propre.

318
00:14:31,220 --> 00:14:34,060
>> Donc malloc est plus que juste
commode à cet effet.

319
00:14:34,060 --> 00:14:37,420
Nous pouvons en fait maintenant résoudre
fondamentalement différents problèmes,

320
00:14:37,420 --> 00:14:41,640
et fondamentalement résoudre des problèmes plus
efficacement que par la promesse de la semaine zéro.

321
00:14:41,640 --> 00:14:44,720
Jusqu'à présent, c'est le plus sexy
structure de données que nous avons eu.

322
00:14:44,720 --> 00:14:47,804
Et par la structure de données que je viens de dire
une façon de conceptualiser la mémoire

323
00:14:47,804 --> 00:14:50,720
d'une manière qui va au-delà en disant:
c'est un int, c'est un car.

324
00:14:50,720 --> 00:14:52,930
Nous pouvons commencer les choses du cluster ensemble.

325
00:14:52,930 --> 00:14:54,460
>> Donc, un tableau ressemblait à ceci.

326
00:14:54,460 --> 00:14:57,270
Et ce qui était essentiel dans environ une
tableau est qu'il vous donne

327
00:14:57,270 --> 00:14:59,724
back-to-back des morceaux de
mémoire, dont chacun

328
00:14:59,724 --> 00:15:02,765
va être du même type, int,
int, int, int, ou char, char, char,

329
00:15:02,765 --> 00:15:03,330
car.

330
00:15:03,330 --> 00:15:04,496
Mais il ya quelques inconvénients.

331
00:15:04,496 --> 00:15:06,570
Ceci par exemple, est
un tableau de taille six.

332
00:15:06,570 --> 00:15:10,650
Supposons que vous remplissez ce tableau avec six
numéros et puis, pour une raison quelconque,

333
00:15:10,650 --> 00:15:13,187
votre utilisateur souhaite donner
vous un septième numéro.

334
00:15:13,187 --> 00:15:14,020
Où mettez-vous?

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> Quelle est la solution si vous avez
créer un tableau sur la pile,

337
00:15:18,990 --> 00:15:22,030
par exemple, il suffit de la semaine
deux notation que nous avons présenté,

338
00:15:22,030 --> 00:15:23,730
des crochets avec un numéro à l'intérieur?

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
Eh bien, vous avez six
le nombre de ces cases.

341
00:15:27,260 --> 00:15:28,530
Quelles seraient vos instincts être?

342
00:15:28,530 --> 00:15:29,973
Où voudriez-vous dire?

343
00:15:29,973 --> 00:15:30,860
>> PUBLIC: [inaudible]

344
00:15:30,860 --> 00:15:31,315
>> DAVID J. Malan: Désolé?

345
00:15:31,315 --> 00:15:32,380
>> PUBLIC: Mettez-le sur la fin.

346
00:15:32,380 --> 00:15:33,796
>> DAVID J. Malan: Mettez-le sur la fin.

347
00:15:33,796 --> 00:15:35,880
Donc un peu plus vers la droite,
en dehors de cette zone.

348
00:15:35,880 --> 00:15:38,710
Qui serait bien, mais il
s'avère que vous ne pouvez pas faire cela.

349
00:15:38,710 --> 00:15:41,350
Parce que si vous ne l'avez pas demandé
pour cette partie de la mémoire,

350
00:15:41,350 --> 00:15:44,490
il pourrait être par hasard que cette
est utilisé par une autre variable

351
00:15:44,490 --> 00:15:45,030
tout à fait.

352
00:15:45,030 --> 00:15:49,210
Pensez une semaine ou deux alors que nous posions
sur les noms de Zamyla et Davin et Gabe

353
00:15:49,210 --> 00:15:49,930
dans la mémoire.

354
00:15:49,930 --> 00:15:51,638
Ils étaient littéralement
dos à dos à dos.

355
00:15:51,638 --> 00:15:53,550
Donc, nous ne pouvons pas nécessairement
confiance que tout ce qui est

356
00:15:53,550 --> 00:15:55,800
ici est disponible pour moi d'utiliser.

357
00:15:55,800 --> 00:15:56,990
>> Alors quoi d'autre pourriez-vous faire?

358
00:15:56,990 --> 00:16:00,282
Eh bien, une fois que vous le sachiez
besoin d'un tableau de taille sept,

359
00:16:00,282 --> 00:16:02,490
vous pourriez créer un
tableau de taille sept, puis utilisez

360
00:16:02,490 --> 00:16:05,950
une boucle for ou une boucle while,
copier dans le nouveau tableau,

361
00:16:05,950 --> 00:16:09,680
et puis en quelque sorte simplement se débarrasser de
ce tableau arrêter ou tout simplement de l'utiliser.

362
00:16:09,680 --> 00:16:12,130
Mais ce n'est pas particulièrement efficace.

363
00:16:12,130 --> 00:16:15,340
En bref, les tableaux ne laissent pas
vous redimensionnez dynamiquement.

364
00:16:15,340 --> 00:16:17,900
>> Donc, d'une part vous obtenez
accès aléatoire, ce qui est incroyable.

365
00:16:17,900 --> 00:16:20,108
Parce qu'il nous permet de faire les choses
comme diviser pour régner,

366
00:16:20,108 --> 00:16:23,100
recherche binaire, qui nous avons
parlé sur l'écran ici.

367
00:16:23,100 --> 00:16:24,950
Mais vous vous peignez dans un coin.

368
00:16:24,950 --> 00:16:27,810
Dès que vous touchez
la fin de votre tableau,

369
00:16:27,810 --> 00:16:29,980
vous avez à faire un très
opération coûteuse

370
00:16:29,980 --> 00:16:33,910
ou écrire tout un tas de code
maintenant traiter ce problème.

371
00:16:33,910 --> 00:16:36,680
>> Alors que faire si la place nous avons eu
quelque chose qui s'appelle une liste,

372
00:16:36,680 --> 00:16:38,820
ou une liste liée en particulier?

373
00:16:38,820 --> 00:16:41,930
Et si au lieu d'avoir
rectangles dos à dos à dos,

374
00:16:41,930 --> 00:16:45,730
nous avons rectangles qui laissent un peu
peu de marge de manœuvre entre eux?

375
00:16:45,730 --> 00:16:49,670
Et même si je l'ai dessiné ce
photo ou adapté cette image

376
00:16:49,670 --> 00:16:54,696
de l'un des textes ici d'être de retour à
dos à dos très ordonnée, en réalité,

377
00:16:54,696 --> 00:16:56,820
l'un de ces rectangles
pourrait être ici en mémoire.

378
00:16:56,820 --> 00:16:58,028
L'un d'eux pourrait être ici.

379
00:16:58,028 --> 00:17:00,420
L'un d'eux pourrait être ici,
ici, et ainsi de suite.

380
00:17:00,420 --> 00:17:02,910
>> Mais que faire si nous avons tiré,
dans ce cas, des flèches

381
00:17:02,910 --> 00:17:05,650
que le lien en quelque sorte ces
rectangles ensemble?

382
00:17:05,650 --> 00:17:08,170
En effet, nous avons vu une technique
incarnation d'une flèche.

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
Qu'avons-nous utilisé au cours des dernières
jours, sous le capot,

385
00:17:13,710 --> 00:17:15,210
est représentatif d'une flèche?

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
Un pointeur, non?

388
00:17:17,349 --> 00:17:19,780
>> Alors que faire si, au lieu de
simplement stocker les numéros,

389
00:17:19,780 --> 00:17:23,130
comme 9, 17, 22, 26, 34,
si nous avons stocké pas

390
00:17:23,130 --> 00:17:27,079
seulement un numéro, mais un pointeur
à côté de chaque numéro?

391
00:17:27,079 --> 00:17:30,690
Alors que tout comme vous enfiler une
aiguille à travers tout un tas de tissu,

392
00:17:30,690 --> 00:17:32,950
les choses d'une certaine manière à lier
ensemble, de même possible

393
00:17:32,950 --> 00:17:35,550
nous avec des pointeurs, comme
incarné par des flèches ici,

394
00:17:35,550 --> 00:17:38,550
sorte de tisser
ces rectangles individuels

395
00:17:38,550 --> 00:17:41,780
en utilisant efficacement un pointeur
à côté de chaque numéro que

396
00:17:41,780 --> 00:17:46,065
souligne une certaine prochain numéro, qui
souligne à son tour, un certain nombre prochaine?

397
00:17:46,065 --> 00:17:47,940
En d'autres termes, ce
si nous voulions réellement

398
00:17:47,940 --> 00:17:49,820
de mettre en œuvre quelque chose comme ça?

399
00:17:49,820 --> 00:17:53,610
Eh bien, malheureusement, ces rectangles,
au moins l'une avec 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
et ainsi de suite, ceux-ci ne sont plus
placettes avec des chiffres simples.

401
00:17:57,040 --> 00:17:59,960
Le fond, rectangle
9 ci-dessous, par exemple,

402
00:17:59,960 --> 00:18:04,330
représente ce qui devrait
soit un pointeur, 32 bits.

403
00:18:04,330 --> 00:18:09,460
Maintenant, je ne suis pas encore au courant de tout type de données
en C qui vous donne non seulement un int

404
00:18:09,460 --> 00:18:11,630
un pointeur, mais tout à fait.

405
00:18:11,630 --> 00:18:15,020
>> Alors, quelle est la solution si nous voulons
d'inventer notre propre réponse à cela?

406
00:18:15,020 --> 00:18:15,760
Ouais?

407
00:18:15,760 --> 00:18:16,640
>> PUBLIC: [inaudible]

408
00:18:16,640 --> 00:18:17,360
>> DAVID J. Malan: Qu'est-ce que c'est?

409
00:18:17,360 --> 00:18:17,880
>> PUBLIC: Nouvelle structure.

410
00:18:17,880 --> 00:18:19,590
>> DAVID J. Malan: Ouais, alors pourquoi
ne nous créons pas une nouvelle structure,

411
00:18:19,590 --> 00:18:20,920
ou en C, une structure?

412
00:18:20,920 --> 00:18:25,990
Nous avons vu struct avant, si brièvement,
où nous avons traité avec une structure de l'étudiant

413
00:18:25,990 --> 00:18:27,780
comme ça, qui avait un nom et une maison.

414
00:18:27,780 --> 00:18:31,980
Dans Pset 3 évasion vous avez utilisé un ensemble de
tas de GRECT et GOvals structs--

415
00:18:31,980 --> 00:18:34,810
Stanford créé pour que
informations se regroupent.

416
00:18:34,810 --> 00:18:38,580
Alors que faire si nous prenons cette même idée de
les mots-clés "typedef" et "struct"

417
00:18:38,580 --> 00:18:42,890
et puis des choses spécifiques, étudiant,
et d'évoluer dans ce qui suit:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- et le noeud est
juste une informatique très générique

419
00:18:46,210 --> 00:18:49,980
terme de quelque chose dans une structure de données,
un récipient dans une structure de données.

420
00:18:49,980 --> 00:18:53,900
Un noeud je prétends va avoir
un int n, tout simple,

421
00:18:53,900 --> 00:18:58,810
et puis un peu plus cryptique,
cette deuxième ligne, noeud de struct * prochaine.

422
00:18:58,810 --> 00:19:01,300
Mais en termes moins techniques,
quelle est cette deuxième ligne

423
00:19:01,300 --> 00:19:02,980
de code à l'intérieur des accolades?

424
00:19:02,980 --> 00:19:03,737
Ouais?

425
00:19:03,737 --> 00:19:04,851
>> PUBLIC: [inaudible]

426
00:19:04,851 --> 00:19:06,600
DAVID J. Malan: A
pointeur vers un autre nœud.

427
00:19:06,600 --> 00:19:09,910
Alors certes, la syntaxe un peu cryptique.

428
00:19:09,910 --> 00:19:13,250
Mais si vous lisez la lettre,
est à côté du nom d'une variable.

429
00:19:13,250 --> 00:19:14,410
Quel est son type de données?

430
00:19:14,410 --> 00:19:18,206
C'est un peu verbeux cette fois,
mais c'est de nœud de structure de type *.

431
00:19:18,206 --> 00:19:22,960
Chaque fois que nous avons vu quelque chose étoile,
signifie que c'est un pointeur sur ce type de données.

432
00:19:22,960 --> 00:19:26,810
Alors est apparemment une prochaine
pointeur vers un noeud de structure.

433
00:19:26,810 --> 00:19:28,310
>> Maintenant, ce qui est un noeud de structure?

434
00:19:28,310 --> 00:19:31,044
Eh bien, remarquez que vous voyez ces
mêmes mots en haut à droite.

435
00:19:31,044 --> 00:19:33,960
Et en effet, vous voyez aussi le mot
"Noeud" ici en bas à gauche.

436
00:19:33,960 --> 00:19:35,640
Et c'est en fait juste une commodité.

437
00:19:35,640 --> 00:19:39,930
Notez que dans notre définition de l'étudiant
il ya le mot «étudiant» qu'une seule fois.

438
00:19:39,930 --> 00:19:42,510
Et c'est parce que l'élève
Il ne s'agissait pas d'auto-référentielle.

439
00:19:42,510 --> 00:19:45,340
Il n'y a rien à l'intérieur d'un étudiant
qui doit pointer vers un autre étudiant,

440
00:19:45,340 --> 00:19:45,610
persay.

441
00:19:45,610 --> 00:19:47,630
Ce serait en quelque sorte
bizarre dans le monde réel.

442
00:19:47,630 --> 00:19:50,880
>> Mais avec un noeud dans un lié
liste, nous ne voulons d'un noeud

443
00:19:50,880 --> 00:19:53,970
être référentielle à un objet similaire.

444
00:19:53,970 --> 00:19:57,900
Et remarquez le changement n'est pas ici
juste ce qui est à l'intérieur des accolades.

445
00:19:57,900 --> 00:20:00,800
Mais nous ajoutons le mot «nœud»
dans la partie supérieure, ainsi que

446
00:20:00,800 --> 00:20:02,930
ajouter à la partie inférieure
au lieu de «étudiant».

447
00:20:02,930 --> 00:20:06,000
Et ce n'est qu'un détail technique
de sorte que, encore une fois, votre structure de données

448
00:20:06,000 --> 00:20:11,380
peut être auto-référentiel, de sorte qu'une
nœud peut pointer vers un autre tel noeud.

449
00:20:11,380 --> 00:20:13,840
>> Alors, quelle est cette fin de compte
va signifier pour nous?

450
00:20:13,840 --> 00:20:17,560
Eh bien, l'un, ce genre de choses à l'intérieur
est le contenu de notre nœud.

451
00:20:17,560 --> 00:20:19,360
Cette chose ici,
en haut à droite, est tellement

452
00:20:19,360 --> 00:20:20,860
que, encore une fois, on peut se référer à nous-mêmes.

453
00:20:20,860 --> 00:20:23,401
Et puis les choses à l'extérieur,
même si le noeud est un nouveau terme,

454
00:20:23,401 --> 00:20:25,500
peut-être, il est toujours le
même comme étudiant et ce

455
00:20:25,500 --> 00:20:27,520
était sous le capot en SPL.

456
00:20:27,520 --> 00:20:31,095
>> Donc, si nous voulions maintenant pour commencer
la mise en œuvre de cette liste chaînée,

457
00:20:31,095 --> 00:20:33,220
comment pourrions-nous traduire
quelque chose comme ça à coder?

458
00:20:33,220 --> 00:20:35,350
Eh bien, nous allons voir juste un
exemple d'un programme qui

459
00:20:35,350 --> 00:20:36,840
utilise en fait une liste chaînée.

460
00:20:36,840 --> 00:20:40,870
Parmi le code de distribution d'aujourd'hui
est un programme appelé Liste zéro.

461
00:20:40,870 --> 00:20:44,980
Et si je n'ai plus ce que j'ai créé une super-
interface graphique simple, interface utilisateur graphique,

462
00:20:44,980 --> 00:20:46,460
mais il est vraiment juste printf.

463
00:20:46,460 --> 00:20:50,930
Et maintenant, je me suis donné un peu le menu
dire les options Supprimer, Insérer, Recherche,

464
00:20:50,930 --> 00:20:51,750
et le Traverse.

465
00:20:51,750 --> 00:20:52,630
Et Quitter.

466
00:20:52,630 --> 00:20:55,970
Ce sont des opérations communes sur un juste
structure de données appelée une liste de lien.

467
00:20:55,970 --> 00:20:58,409
>> Maintenant, Supprimer va
supprimer un numéro de la liste.

468
00:20:58,409 --> 00:21:00,200
Insérer va ajouter
un numéro de la liste.

469
00:21:00,200 --> 00:21:02,181
Recherche va regarder
pour numéro dans la liste.

470
00:21:02,181 --> 00:21:04,930
Et traverse est juste une façon élégante
de dire, marcher à travers la liste,

471
00:21:04,930 --> 00:21:06,245
l'imprimer, mais c'est tout.

472
00:21:06,245 --> 00:21:07,720
Ne pas modifier en aucune façon.

473
00:21:07,720 --> 00:21:08,570
>> Essayons donc de cela.

474
00:21:08,570 --> 00:21:10,160
Allons de l'avant et de type 2.

475
00:21:10,160 --> 00:21:12,710
Et puis je vais
insérer le numéro, dire 9.

476
00:21:12,710 --> 00:21:13,620
Entrée.

477
00:21:13,620 --> 00:21:17,480
Et maintenant, mon programme est juste
programmée à-dire, la liste est maintenant 9.

478
00:21:17,480 --> 00:21:20,190
Maintenant, si je vais de l'avant et
ne Insérez à nouveau, laisser

479
00:21:20,190 --> 00:21:23,680
moi aller de l'avant et zoom arrière et tape 17.

480
00:21:23,680 --> 00:21:25,770
Ma liste est maintenant 9, puis 17.

481
00:21:25,770 --> 00:21:27,750
Si je fais insérer à nouveau, nous allons sauter un.

482
00:21:27,750 --> 00:21:32,400
Au lieu de 22, comme par l'image que nous avons
été regardant ici, permettez-moi d'intervenir avant

483
00:21:32,400 --> 00:21:34,630
et insérer 26 prochain.

484
00:21:34,630 --> 00:21:36,230
Je vais donc saisir 26.

485
00:21:36,230 --> 00:21:37,755
La liste est comme je le pense.

486
00:21:37,755 --> 00:21:40,630
Mais maintenant, juste pour voir si ce code
va être souple, laissez-moi maintenant

487
00:21:40,630 --> 00:21:43,520
Type 22, dans lequel au moins
conceptuellement, si nous sommes

488
00:21:43,520 --> 00:21:46,520
En gardant cela triée, qui est en effet
va être un autre objectif en ce moment,

489
00:21:46,520 --> 00:21:48,690
devrait passer entre 17 et 26.

490
00:21:48,690 --> 00:21:50,270
Alors j'ai frappé sur Entrée.

491
00:21:50,270 --> 00:21:51,380
En effet, cela fonctionne.

492
00:21:51,380 --> 00:21:54,950
Et maintenant laissez-moi insérer le
dernier, par l'image, 34.

493
00:21:54,950 --> 00:21:55,450
>> Bien.

494
00:21:55,450 --> 00:21:58,980
Donc pour l'instant je vais prévoir que
Supprimer et le Traverse ainsi Rechercher font,

495
00:21:58,980 --> 00:21:59,760
en fait, travailler.

496
00:21:59,760 --> 00:22:04,180
En fait, si je ne cours Recherche, nous allons
rechercher le numéro 22, Entrée.

497
00:22:04,180 --> 00:22:05,010
Il a trouvé 22.

498
00:22:05,010 --> 00:22:07,580
Donc, c'est ce que ce
Liste programme Zéro fait.

499
00:22:07,580 --> 00:22:10,230
>> Mais qu'est-ce qui se passe réellement
sur qui implémente ce?

500
00:22:10,230 --> 00:22:14,530
Eh bien, tout d'abord je pourrais avoir, et même
Je n'ai, un fichier appelé list0.h.

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
Et quelque part là-dedans est ce
ligne, typedef, noeud de structure,

503
00:22:20,690 --> 00:22:24,850
alors j'ai mes accolades, int n, et
alors struct-- quelle était la définition?

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
noeud de Struct prochaine.

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
Donc, nous avons besoin de l'étoile.

508
00:22:31,045 --> 00:22:33,420
Maintenant, techniquement, nous entrons dans
l'habitude de dessiner ici.

509
00:22:33,420 --> 00:22:35,670
Vous pouvez voir les manuels et
références en ligne le font là-bas.

510
00:22:35,670 --> 00:22:36,660
C'est fonctionnellement équivalent.

511
00:22:36,660 --> 00:22:37,980
En fait, il s'agit d'un peu plus typique.

512
00:22:37,980 --> 00:22:40,563
Mais je serai conforme à ce que
nous avons fait la dernière fois et faisons.

513
00:22:40,563 --> 00:22:42,350
Et puis enfin, je vais le faire.

514
00:22:42,350 --> 00:22:45,550
>> Ainsi, dans un fichier d'en-tête
quelque part, dans list0.h

515
00:22:45,550 --> 00:22:49,200
aujourd'hui, c'est cette définition de struct,
et peut-être d'autres choses.

516
00:22:49,200 --> 00:22:52,580
Pendant ce temps, il ya list0c
va être un certain nombre de choses.

517
00:22:52,580 --> 00:22:54,740
Mais nous allons tout simplement
commencer et ne pas finir ce.

518
00:22:54,740 --> 00:22:59,690
List0.h est un fichier que je veux
d'inclure dans mon dossier de C.

519
00:22:59,690 --> 00:23:03,910
Et puis à un moment je suis
va avoir int, principal, annuler.

520
00:23:03,910 --> 00:23:06,530
Et puis je vais
ont une certaine to-do c'est ici.

521
00:23:06,530 --> 00:23:10,620
Je vais aussi avoir un
prototype, comme vide, la recherche, int,

522
00:23:10,620 --> 00:23:13,610
n, dont le but dans la vie est
à rechercher un élément.

523
00:23:13,610 --> 00:23:18,310
Et puis ici je prétends en
le code d'aujourd'hui, nulle recherche, int, n,

524
00:23:18,310 --> 00:23:21,020
pas de point-virgule, mais accolades ouvertes.

525
00:23:21,020 --> 00:23:25,049
Et maintenant, je veux chercher quelque sorte
pour un élément dans la liste.

526
00:23:25,049 --> 00:23:27,340
Mais nous n'avons pas assez
informations à l'écran pour l'instant.

527
00:23:27,340 --> 00:23:29,800
Je n'ai pas fait
représenté la liste elle-même.

528
00:23:29,800 --> 00:23:33,070
Donc, d'une façon que nous pourrions mettre en œuvre
une liste liée à un programme

529
00:23:33,070 --> 00:23:37,520
c'est que je sorte de veux faire quelque chose
comme déclarer liste liée ici.

530
00:23:37,520 --> 00:23:40,520
Par souci de simplicité, je vais faire
ce mondial, même si en général nous

531
00:23:40,520 --> 00:23:41,645
ne devrait pas faire trop.

532
00:23:41,645 --> 00:23:43,260
Mais il va simplifier cet exemple.

533
00:23:43,260 --> 00:23:45,890
Je tiens donc à déclarer
une liste chaînée ici.

534
00:23:45,890 --> 00:23:47,010
Maintenant, comment pourrais-je faire cela?

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> Voici la photo d'une liste chaînée.

537
00:23:50,750 --> 00:23:53,030
Et je n'aime pas vraiment
savoir à l'instant comment

538
00:23:53,030 --> 00:23:56,710
Je vais aller de représenter
tant de choses avec un seul

539
00:23:56,710 --> 00:23:58,040
variable de la mémoire.

540
00:23:58,040 --> 00:23:59,160
Mais penser en arrière un instant.

541
00:23:59,160 --> 00:24:00,830
Pendant tout ce temps, nous avons eu
cordes, que nous avons ensuite

542
00:24:00,830 --> 00:24:02,913
révélé être des tableaux de
caractères, que nous avons ensuite

543
00:24:02,913 --> 00:24:05,740
révélé être juste un pointeur
pour le premier caractère

544
00:24:05,740 --> 00:24:08,890
dans un tableau de caractères
que NULL résilié.

545
00:24:08,890 --> 00:24:13,530
Donc, par cette logique, et avec ce
image type de l'ensemencement vos pensées,

546
00:24:13,530 --> 00:24:17,964
Qu'avons-nous besoin d'écrire en fait dans notre
Code pour représenter une liste chaînée?

547
00:24:17,964 --> 00:24:21,130
Combien de ces informations devons-nous
à saisir dans le code C, diriez-vous?

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
Ouais?

550
00:24:23,154 --> 00:24:24,738
>> PUBLIC: Nous avons besoin d'un pointeur vers un noeud.

551
00:24:24,738 --> 00:24:26,237
DAVID J. Malan: Un pointeur vers un noeud.

552
00:24:26,237 --> 00:24:29,320
En particulier, le nœud qui serait votre
instincts de garder un pointeur vers?

553
00:24:29,320 --> 00:24:30,026
>> AUDIENCE: Le premier nœud.

554
00:24:30,026 --> 00:24:31,942
>> DAVID J. Malan: Ouais,
probablement que la première.

555
00:24:31,942 --> 00:24:34,030
Et remarquez, la première
le noeud est de forme différente.

556
00:24:34,030 --> 00:24:37,690
C'est seulement la moitié de la taille de la structure,
parce que c'est en effet seulement un pointeur.

557
00:24:37,690 --> 00:24:44,650
Donc, ce que vous pouvez en effet faire est de déclarer
une liste chaînée à être de type noeud *.

558
00:24:44,650 --> 00:24:47,780
Et nous allons simplement appeler la première
et l'initialiser à NULL.

559
00:24:47,780 --> 00:24:49,910
Donc nul, encore une fois, est venue
dans l'image ici.

560
00:24:49,910 --> 00:24:53,620
Non seulement est nulle utilisé comme comme un spécial
valeur de retour pour des choses comme getString

561
00:24:53,620 --> 00:24:57,770
et malloc, null est aussi le zéro
pointeur, l'absence d'un pointeur,

562
00:24:57,770 --> 00:24:58,430
si vous voulez.

563
00:24:58,430 --> 00:25:00,309
Cela signifie simplement que rien n'est encore ici.

564
00:25:00,309 --> 00:25:02,100
Maintenant, la première, j'aurais pu
appelé cette chose.

565
00:25:02,100 --> 00:25:04,200
J'aurais pu appelé "liste"
ou n'importe quel nombre d'autres choses.

566
00:25:04,200 --> 00:25:06,960
Mais je l'appeler «première» de sorte que
qu'il s'aligne avec cette image.

567
00:25:06,960 --> 00:25:10,280
Ainsi, tout comme une chaîne peut être représenté
avec l'adresse de son premier octet,

568
00:25:10,280 --> 00:25:11,280
si possible une liste chaînée.

569
00:25:11,280 --> 00:25:13,480
Et nous verrons d'autres données
structures sont représentées

570
00:25:13,480 --> 00:25:16,700
avec un seul pointeur,
une flèche de 32 bits, pointant

571
00:25:16,700 --> 00:25:18,740
au premier noeud dans la structure.

572
00:25:18,740 --> 00:25:20,340
>> Mais maintenant, nous allons anticiper un problème.

573
00:25:20,340 --> 00:25:23,230
Si je suis seulement se souvenir
dans mon programme l'adresse

574
00:25:23,230 --> 00:25:27,220
du premier noeud, le premier
rectangle dans cette structure de données,

575
00:25:27,220 --> 00:25:31,760
ce qui avait mieux être le cas à propos de la
mise en œuvre du reste de ma liste?

576
00:25:31,760 --> 00:25:35,820
Qu'est-ce que c'est un détail clé qui va
de veiller à ce que cela fonctionne réellement?

577
00:25:35,820 --> 00:25:39,250
Et par "fonctionne réellement" je
moyenne, un peu comme une chaîne,

578
00:25:39,250 --> 00:25:42,180
nous laisse partir du premier caractère
au nom de Davin à la seconde,

579
00:25:42,180 --> 00:25:44,755
à la troisième, à la
quatrième, à la fin,

580
00:25:44,755 --> 00:25:47,880
comment savons-nous quand nous sommes à la fin
d'une liste chaînée qui ressemble à ceci?

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
Quand il est nul.

583
00:25:50,660 --> 00:25:53,640
Et j'ai représenté cette sorte de
comme un ingénieur puissance électrique,

584
00:25:53,640 --> 00:25:56,420
avec la petite mise à la terre
symbole, en quelque sorte.

585
00:25:56,420 --> 00:25:58,246
Mais cela signifie simplement nulle dans ce cas.

586
00:25:58,246 --> 00:26:00,370
Vous pouvez dessiner n'importe quel nombre
des moyens, mais cet auteur

587
00:26:00,370 --> 00:26:02,800
arrivé à utiliser ce symbole ici.

588
00:26:02,800 --> 00:26:06,260
>> Tant que nous sommes cordage
tous ces noeuds ensemble,

589
00:26:06,260 --> 00:26:08,600
seulement à se rappeler où
la première est, aussi longtemps

590
00:26:08,600 --> 00:26:11,760
que nous mettons un symbole spécial à
le dernier noeud de la liste,

591
00:26:11,760 --> 00:26:15,130
et nous utiliserons nulle, parce que c'est
ce que nous avons à notre disposition,

592
00:26:15,130 --> 00:26:16,480
cette liste est complète.

593
00:26:16,480 --> 00:26:20,190
Et même si je ne vous donne un pointeur vers
le premier élément, vous, le programmeur,

594
00:26:20,190 --> 00:26:22,486
peut certainement accéder au reste de celui-ci.

595
00:26:22,486 --> 00:26:24,360
Mais laissons vos esprits
se promener un peu,

596
00:26:24,360 --> 00:26:26,140
s'ils ne sont pas déjà
tout ce qui est wandered--

597
00:26:26,140 --> 00:26:28,723
va être le temps d'exécution de
rien trouver dans cette liste?

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
Merde, il est grand O de n,
qui n'est pas mauvais, en toute équité.

600
00:26:33,470 --> 00:26:34,800
Mais il est linéaire.

601
00:26:34,800 --> 00:26:37,980
Nous avons renoncé à ce dispositif
de tableaux en déplaçant plus

602
00:26:37,980 --> 00:26:43,130
vers cette image de façon dynamique
tissés ensemble ou liés noeuds?

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
Nous avons renoncé à accès aléatoire.

605
00:26:46,687 --> 00:26:48,770
Un tableau est agréable parce que
tout mathématiquement

606
00:26:48,770 --> 00:26:50,340
est de retour à dos à dos à dos.

607
00:26:50,340 --> 00:26:52,370
Même si cette image
semble assez, et même

608
00:26:52,370 --> 00:26:55,830
si elle ressemble à ces nœuds
sont bien espacées, dans la réalité

609
00:26:55,830 --> 00:26:56,830
ils pourraient être n'importe où.

610
00:26:56,830 --> 00:27:01,590
Ox1, OX50, Ox123, Ox99, ces
noeuds pourraient être n'importe où.

611
00:27:01,590 --> 00:27:05,960
Parce que malloc fait allouer de la mémoire
dans le tas, mais partout dans le tas.

612
00:27:05,960 --> 00:27:09,080
Vous ne savez pas nécessairement que c'est
va être dos à dos à dos.

613
00:27:09,080 --> 00:27:12,460
Et si cette image dans la réalité d'
ne va pas être tout à fait cette jolie.

614
00:27:12,460 --> 00:27:16,140
>> Donc, il va prendre un peu de
travailler à mettre en œuvre cette fonction.

615
00:27:16,140 --> 00:27:17,880
Donc, nous allons mettre en œuvre la recherche maintenant.

616
00:27:17,880 --> 00:27:20,250
Et nous allons voir une sorte de
façon intelligente de le faire.

617
00:27:20,250 --> 00:27:24,660
Donc, si je suis une fonction de recherche et
Je me donne une variable, entier n

618
00:27:24,660 --> 00:27:28,490
à chercher, j'ai besoin de savoir l'
nouvelle syntaxe pour regarder à l'intérieur

619
00:27:28,490 --> 00:27:32,400
d'une structure qui est
souligné, de trouver n.

620
00:27:32,400 --> 00:27:33,210
Donc, nous allons le faire.

621
00:27:33,210 --> 00:27:36,030
>> Alors d'abord je vais aller
avant et déclarer un noeud *.

622
00:27:36,030 --> 00:27:39,400
Et je vais l'appeler
pointeur, juste par convention.

623
00:27:39,400 --> 00:27:41,710
Et je vais de l'initialiser à la première.

624
00:27:41,710 --> 00:27:43,770
Et maintenant, je peux le faire
dans un certain nombre de façons.

625
00:27:43,770 --> 00:27:45,436
Mais je vais prendre une approche commune.

626
00:27:45,436 --> 00:27:50,180
Alors que le pointeur n'est pas égal à
nul, et c'est la syntaxe correcte.

627
00:27:50,180 --> 00:27:54,550
Et cela signifie juste faire ce qui suit, de sorte
Tant que vous n'êtes pas en montrant rien.

628
00:27:54,550 --> 00:27:55,800
Qu'est-ce que je veux faire?

629
00:27:55,800 --> 00:28:01,939
>> Si pointeur point n, permettez-moi de revenir
pour que, equals-- égal quoi?

630
00:28:01,939 --> 00:28:03,105
Quelle est la valeur que je cherche?

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
Le n réel qui a été transmise.

633
00:28:06,590 --> 00:28:09,020
Alors, voici une autre caractéristique
de C et de nombreuses langues.

634
00:28:09,020 --> 00:28:13,705
Même si le noeud de structure appelée
a une valeur n, tout à fait légitime

635
00:28:13,705 --> 00:28:17,530
d'avoir aussi un argument locale
ou variable appelé n.

636
00:28:17,530 --> 00:28:20,085
Parce que même nous, avec
yeux de l'homme, peuvent distinguer

637
00:28:20,085 --> 00:28:22,087
ce que n est probablement
différent de ce n.

638
00:28:22,087 --> 00:28:23,420
Parce que la syntaxe est différente.

639
00:28:23,420 --> 00:28:26,211
Vous avez un point et un pointeur,
alors que celui-ci n'a pas une telle chose.

640
00:28:26,211 --> 00:28:27,290
Donc, c'est OK.

641
00:28:27,290 --> 00:28:29,120
C'est OK pour les appeler les mêmes choses.

642
00:28:29,120 --> 00:28:32,380
>> Si je trouve ne vous cela, je suis
va vouloir faire quelque chose

643
00:28:32,380 --> 00:28:35,000
comme vous annonçons que nous avons trouvé n.

644
00:28:35,000 --> 00:28:37,930
Et nous allons laisser cela comme un
commenter ou code pseudo.

645
00:28:37,930 --> 00:28:40,190
Sinon, et voici la
partie intéressante, ce

646
00:28:40,190 --> 00:28:47,320
ce que je veux faire si le noeud courant
est pas n contenant que je me soucie?

647
00:28:47,320 --> 00:28:50,700
Comment puis-je obtenir les résultats suivants?

648
00:28:50,700 --> 00:28:53,710
Si mon doigt à l'
moment est PTR, et c'est

649
00:28:53,710 --> 00:28:55,920
pointant à quelque
la première est dirigée vers,

650
00:28:55,920 --> 00:28:59,290
comment puis-je passer mon doigt
au noeud suivant dans le code?

651
00:28:59,290 --> 00:29:01,915
Eh bien, ce qui est le fil d'Ariane que nous sommes
va suivre dans ce cas?

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
PUBLIC: [inaudible].

654
00:29:04,380 --> 00:29:05,630
DAVID J. Malan: Ouais, donc la prochaine.

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
Donc, si je reviens à ma
code ici, en effet, je suis

657
00:29:09,824 --> 00:29:12,990
aller de l'avant et dire pointeur, qui
est juste un variable-- temporaire c'est

658
00:29:12,990 --> 00:29:15,320
un nom bizarre, ptr, mais
c'est comme temp--

659
00:29:15,320 --> 00:29:19,234
Je vais mettre pointeur
égal à tout ce pointeur is--

660
00:29:19,234 --> 00:29:22,150
et encore une fois, cela va être un
peu buggé pour un point moment-- prochaine.

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
En d'autres termes, je vais prendre mon
doigt qui est en montrant ce noeud

663
00:29:26,550 --> 00:29:31,247
ici et je vais vous dire, vous savez
ce, jetez un oeil à la zone suivante

664
00:29:31,247 --> 00:29:33,330
et déplacez votre doigt pour
quel que soit son pointé.

665
00:29:33,330 --> 00:29:35,163
Et cela va
répéter, répéter, répéter.

666
00:29:35,163 --> 00:29:37,630
Mais quand est-ce mon doigt
arrêter de faire quoi que ce soit?

667
00:29:37,630 --> 00:29:40,095
Dès que quelle ligne de coups de pied de code dans?

668
00:29:40,095 --> 00:29:40,970
PUBLIC: [inaudible]

669
00:29:40,970 --> 00:29:43,060
DAVID J. Malan: Si le point en
pointeur n'est pas égale à null.

670
00:29:43,060 --> 00:29:44,900
À un certain moment de mon doigt
va être montrant null

671
00:29:44,900 --> 00:29:47,070
et je vais réaliser
c'est la fin de cette liste.

672
00:29:47,070 --> 00:29:48,910
Maintenant, c'est un peu
mensonge pour plus de simplicité.

673
00:29:48,910 --> 00:29:51,580
Il s'avère que même si nous
vient d'apprendre cette notation point

674
00:29:51,580 --> 00:29:55,220
pour les structures, pointeur n'est pas une structure.

675
00:29:55,220 --> 00:29:56,580
ptr, c'est quoi?

676
00:29:56,580 --> 00:29:58,350
Juste pour être plus tatillon.

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
Il s'agit d'un pointeur vers un noeud.

679
00:30:01,360 --> 00:30:03,120
Ce n'est pas un noeud lui-même.

680
00:30:03,120 --> 00:30:06,650
Si je n'avais pas étoiles ici, pointeur
absolutely-- c'est un nœud.

681
00:30:06,650 --> 00:30:08,650
C'est comme la première semaine
déclaration d'une variable,

682
00:30:08,650 --> 00:30:10,120
même si le mot «nœud» est nouvelle.

683
00:30:10,120 --> 00:30:13,860
>> Mais dès que nous introduisons une
étoiles, c'est maintenant un pointeur vers un noeud.

684
00:30:13,860 --> 00:30:17,960
Et malheureusement, vous ne pouvez pas utiliser
la notation par points pour un pointeur.

685
00:30:17,960 --> 00:30:21,070
Vous devez utiliser la flèche
notation, qui, étonnamment,

686
00:30:21,070 --> 00:30:23,470
C'est la première fois qu'un morceau
de la syntaxe semble intuitive.

687
00:30:23,470 --> 00:30:25,245
Cela ressemble littéralement comme une flèche.

688
00:30:25,245 --> 00:30:26,370
Et donc c'est une bonne chose.

689
00:30:26,370 --> 00:30:28,995
Et ici littéralement
ressemble à une flèche.

690
00:30:28,995 --> 00:30:31,870
Donc, je pense que c'est la la-- je ne fais pas
pense que je suis trop commettre ici-- je

691
00:30:31,870 --> 00:30:34,120
pense que c'est la dernière nouvelle pièce
de la syntaxe que nous allons voir.

692
00:30:34,120 --> 00:30:36,500
Et heureusement, il est en effet
un peu plus intuitive.

693
00:30:36,500 --> 00:30:40,090
>> Maintenant, pour ceux d'entre vous qui
pourraient préférer l'ancienne,

694
00:30:40,090 --> 00:30:42,550
vous pouvez toujours utiliser la notation par points.

695
00:30:42,550 --> 00:30:45,380
Mais selon de lundi
la conversation, nous avons d'abord

696
00:30:45,380 --> 00:30:50,530
besoin d'y aller, aller à cette
répondre, puis accéder au champ.

697
00:30:50,530 --> 00:30:51,897
Donc, c'est aussi correct.

698
00:30:51,897 --> 00:30:53,730
Et franchement, c'est un
peu plus pédant.

699
00:30:53,730 --> 00:30:56,530
Vous êtes littéralement dire, déréférencer
le pointeur et y aller.

700
00:30:56,530 --> 00:30:59,320
Puis saisir .n, le champ appelé n.

701
00:30:59,320 --> 00:31:01,370
Mais franchement, personne ne veut
taper ou lire.

702
00:31:01,370 --> 00:31:03,620
Et si le monde inventé
la notation de la flèche, qui

703
00:31:03,620 --> 00:31:06,980
est équivalent, identique,
c'est juste du sucre syntaxique.

704
00:31:06,980 --> 00:31:10,570
Ainsi, une façon élégante de dire ce
semble meilleure, ou semble plus simple.

705
00:31:10,570 --> 00:31:12,296
>> Alors maintenant, je vais faire autre chose.

706
00:31:12,296 --> 00:31:15,420
Je vais dire "casser" une fois que je n'ai
trouvé si je ne garde pas le chercher.

707
00:31:15,420 --> 00:31:17,620
Mais ce n'est l'essentiel
d'une fonction de recherche.

708
00:31:17,620 --> 00:31:21,710
Mais il est beaucoup plus facile, dans le
fin, de ne pas marcher dans le code.

709
00:31:21,710 --> 00:31:25,570
C'est en effet la mise en œuvre formelle
de la recherche dans le code de distribution d'aujourd'hui.

710
00:31:25,570 --> 00:31:30,530
J'ose dire que insert n'est pas
particulièrement amusant à parcourir

711
00:31:30,530 --> 00:31:33,180
visuellement, n'est pas non plus supprimer, même
si à la fin de la journée

712
00:31:33,180 --> 00:31:35,460
ils se résument à assez
heuristiques simples.

713
00:31:35,460 --> 00:31:36,330
>> Donc, nous allons le faire.

714
00:31:36,330 --> 00:31:39,250
Si vous aurez l'humour moi ici, je l'ai fait
apporter un tas de balles anti-stress.

715
00:31:39,250 --> 00:31:40,620
J'ai apporté un tas de chiffres.

716
00:31:40,620 --> 00:31:46,562
Et pourrions-nous obtenir quelques bénévoles
à représenter 9, 17, 20, 22, 29, et 34?

717
00:31:46,562 --> 00:31:48,270
Donc, essentiellement, tout le monde
qui est ici aujourd'hui.

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
C'était un, deux, trois,
quatre, cinq, six personnes.

720
00:31:52,760 --> 00:31:55,740
Et j'ai demandé à go-- voir, pas
un dans le dos soulève leurs mains.

721
00:31:55,740 --> 00:32:01,910
OK, un, deux, trois, quatre,
five-- permettez-moi de charger balance-- six.

722
00:32:01,910 --> 00:32:03,051
OK, vous venez sur place six.

723
00:32:03,051 --> 00:32:04,050
Nous aurons besoin d'autres personnes.

724
00:32:04,050 --> 00:32:05,460
Nous avons apporté des boules de stress supplémentaires.

725
00:32:05,460 --> 00:32:08,200
Et si vous pouviez, pour
un instant, ligne

726
00:32:08,200 --> 00:32:10,490
vous place juste
comme cette image ici.

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> Bien.

729
00:32:15,959 --> 00:32:17,125
Voyons, quel est votre nom?

730
00:32:17,125 --> 00:32:17,550
>> PUBLIC: Andrew.

731
00:32:17,550 --> 00:32:18,800
>> DAVID J. Malan: Andrew,
vous êtes le numéro 9.

732
00:32:18,800 --> 00:32:19,540
Ravi de vous rencontrer.

733
00:32:19,540 --> 00:32:20,400
Voici.

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
PUBLIC: Jen.

736
00:32:22,176 --> 00:32:22,662
DAVID J. Malan: Jen.

737
00:32:22,662 --> 00:32:23,162
David.

738
00:32:23,162 --> 00:32:23,765
Numéro 17.

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
Oui?

741
00:32:25,450 --> 00:32:26,400
>> PUBLIC: Je suis Julia.

742
00:32:26,400 --> 00:32:26,980
>> DAVID J. Malan: Julia, David.

743
00:32:26,980 --> 00:32:27,545
Nombre 20.

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
PUBLIC: Christian.

746
00:32:29,340 --> 00:32:30,715
DAVID J. Malan: Christian, David.

747
00:32:30,715 --> 00:32:31,541
Numéro 22.

748
00:32:31,541 --> 00:32:32,040
Et?

749
00:32:32,040 --> 00:32:32,649
>> PUBLIC: JP.

750
00:32:32,649 --> 00:32:33,440
DAVID J. Malan: JP.

751
00:32:33,440 --> 00:32:34,880
Numéro 29.

752
00:32:34,880 --> 00:32:37,080
Donc, aller de l'avant et obtenir in-- Uh oh.

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
Uh oh.

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
Veille.

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20.

759
00:32:42,390 --> 00:32:43,682
Quelqu'un at-il un marqueur?

760
00:32:43,682 --> 00:32:44,890
PUBLIC: J'ai un Sharpie.

761
00:32:44,890 --> 00:32:45,660
DAVID J. Malan: Vous avez un Sharpie?

762
00:32:45,660 --> 00:32:46,159
Dáccord.

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
Et quelqu'un at-il un morceau de papier?

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
Enregistrer la conférence.

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
Allons.

769
00:32:55,362 --> 00:32:56,320
PUBLIC: Nous avons obtenu.

770
00:32:56,320 --> 00:32:57,600
DAVID J. Malan: nous surprendre?

771
00:32:57,600 --> 00:32:58,577
Très bien, merci.

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
Et c'est parti.

774
00:33:02,520 --> 00:33:03,582
Était-ce de vous?

775
00:33:03,582 --> 00:33:04,540
Vous venez d'enregistrer le jour.

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
Donc 29.

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
Bien.

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
Je écorché 29, mais OK.

782
00:33:14,890 --> 00:33:15,720
Aller de l'avant.

783
00:33:15,720 --> 00:33:18,114
Très bien, je vais vous donner
votre stylo momentanément.

784
00:33:18,114 --> 00:33:19,280
Nous avons donc ces gens ici.

785
00:33:19,280 --> 00:33:20,330
Ayons un autre.

786
00:33:20,330 --> 00:33:23,750
Gabe, voulez-vous jouer
le premier élément ici?

787
00:33:23,750 --> 00:33:25,705
Nous aurons besoin de vous faire remarquer
à ces bons gens.

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
Donc, 9, 17, 20, 22, sorte
de 29, puis 34.

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
Avons-nous perdu quelqu'un?

792
00:33:33,325 --> 00:33:33,950
J'ai un 34.

793
00:33:33,950 --> 00:33:36,730
Où did-- OK, qui veut être 34?

794
00:33:36,730 --> 00:33:37,605
OK, venez sur place, 34.

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
Très bien, ce sera
vaut bien le point culminant.

797
00:33:41,220 --> 00:33:41,550
Quel est votre nom?

798
00:33:41,550 --> 00:33:42,040
>> PUBLIC: Peter.

799
00:33:42,040 --> 00:33:43,456
>> DAVID J. Malan: Peter, venez sur place.

800
00:33:43,456 --> 00:33:46,810
Bon, alors voici une
tas ensemble de nœuds.

801
00:33:46,810 --> 00:33:49,060
Chacun de vous les gars représente
l'un de ces rectangles.

802
00:33:49,060 --> 00:33:51,930
Et Gabe, le peu étrange
Man Out, représente la première.

803
00:33:51,930 --> 00:33:54,850
Ainsi, son pointeur est un peu plus petit
sur l'écran de tout le monde.

804
00:33:54,850 --> 00:33:58,120
Et dans ce cas, chacun de vos gauche
mains va soit orienté vers le bas,

805
00:33:58,120 --> 00:34:01,085
représentant de ce fait nulle, de sorte que
juste l'absence d'un pointeur,

806
00:34:01,085 --> 00:34:03,210
ou il va être dirigée
à un nœud à côté de vous.

807
00:34:03,210 --> 00:34:05,440
>> Donc maintenant si vous ornez
vous comme l'image

808
00:34:05,440 --> 00:34:07,585
ici, aller de l'avant et le point
à l'autre, avec Gabe

809
00:34:07,585 --> 00:34:11,030
en particulier pointage à
numéro 9 pour représenter la liste.

810
00:34:11,030 --> 00:34:14,050
OK, et le numéro 34, de la main gauche
devrait seulement être dirigée vers le sol.

811
00:34:14,050 --> 00:34:15,750
>> OK, donc c'est la liste chaînée.

812
00:34:15,750 --> 00:34:17,580
Donc, c'est le scénario en question.

813
00:34:17,580 --> 00:34:20,210
Et en effet, c'est représentatif
d'une classe de problèmes

814
00:34:20,210 --> 00:34:21,929
que vous pourriez essayer de résoudre avec le code.

815
00:34:21,929 --> 00:34:25,020
Vous souhaitez insérer en fin de compte
un nouvel élément dans la liste.

816
00:34:25,020 --> 00:34:27,494
Dans ce cas, nous allons
essayez d'insérer le numéro 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Mais il y aura
différents cas à considérer.

819
00:34:30,860 --> 00:34:34,409
Et en effet, cela va être un
de l'ensemble de la situation des plats à emporter ici, est,

820
00:34:34,409 --> 00:34:35,659
quels sont les différents cas.

821
00:34:35,659 --> 00:34:39,120
Quels sont les différents si les conditions ou
branches que votre programme pourrait avoir?

822
00:34:39,120 --> 00:34:42,024
>> Eh bien, le nombre que vous essayez de
insert, dont nous savons maintenant à 55,

823
00:34:42,024 --> 00:34:44,650
mais si vous ne saviez pas
à l'avance, si j'ose dire

824
00:34:44,650 --> 00:34:47,840
tombe dans au moins trois
les situations possibles.

825
00:34:47,840 --> 00:34:49,717
Où peut-être un nouvel élément?

826
00:34:49,717 --> 00:34:51,050
PUBLIC: Et la fin ou au milieu.

827
00:34:51,050 --> 00:34:54,150
DAVID J. Malan: A la fin, dans
au milieu, ou au début.

828
00:34:54,150 --> 00:34:56,650
Donc, je prétends qu'il ya au moins
trois problèmes que nous avons besoin de résoudre.

829
00:34:56,650 --> 00:34:58,691
Choisissons ce qui est peut-être
sans doute le plus simple

830
00:34:58,691 --> 00:35:01,090
un, où le nouvel élément
appartient au début.

831
00:35:01,090 --> 00:35:04,040
Donc, je vais avoir le code tout à fait
comme la recherche, que je viens d'écrire.

832
00:35:04,040 --> 00:35:07,670
Et je vais devoir ptr, qui
Je représente ici avec mon doigt,

833
00:35:07,670 --> 00:35:08,370
comme d'habitude.

834
00:35:08,370 --> 00:35:12,430
>> Et rappelez-vous, quelle est la valeur
avons-nous initialisons ptr?

835
00:35:12,430 --> 00:35:15,300
Donc, nous avons initialisé à null initialement.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Mais alors qu'est-ce que nous faisons lorsque nous
trouvaient à l'intérieur de notre fonction de recherche?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Nous avons mis en elle égale à la première,
qui ne signifie pas le faire.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Si je mets ptr égale à la première, ce qui
devrait être vraiment ma main pointant?

842
00:35:30,570 --> 00:35:31,070
Droite.

843
00:35:31,070 --> 00:35:33,290
Donc, si Gabe et moi allons
être des valeurs égales ici,

844
00:35:33,290 --> 00:35:34,760
nous devons à la fois point numéro 9.

845
00:35:34,760 --> 00:35:36,420
>> Donc, ce fut le début de notre histoire.

846
00:35:36,420 --> 00:35:38,700
Et maintenant, c'est juste simple,
même si la syntaxe est nouveau.

847
00:35:38,700 --> 00:35:40,580
Conceptuellement, cela est tout simplement la recherche linéaire.

848
00:35:40,580 --> 00:35:42,750
Is 55, égale à 9?

849
00:35:42,750 --> 00:35:45,559
Ou plutôt, disons moins de 9.

850
00:35:45,559 --> 00:35:47,600
Parce que je suis en train de
savoir où mettre 55.

851
00:35:47,600 --> 00:35:51,270
Moins de 9, à moins de 17, moins
de 20, moins de 22, moins de 29,

852
00:35:51,270 --> 00:35:52,510
moins de 34, no.

853
00:35:52,510 --> 00:35:55,080
Alors maintenant, nous sommes dans le cas
l'un des au moins trois.

854
00:35:55,080 --> 00:35:59,910
>> Si je veux insérer 55 ici, ce
lignes de code nécessaire pour se exécutés?

855
00:35:59,910 --> 00:36:01,890
Comment cette image de
les humains ont besoin de changer?

856
00:36:01,890 --> 00:36:03,181
Que dois-je faire avec ma main gauche?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Cela devrait être nulle au départ,
parce que je suis à la fin de la liste.

859
00:36:07,360 --> 00:36:09,318
Et ce qui devrait arriver
ici avec Peter, était-ce?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Il va évidemment à pointer vers moi.

862
00:36:12,430 --> 00:36:15,580
Donc, je prétends qu'il ya au moins deux lignes
de code dans le code à partir d'aujourd'hui de l'échantillon

863
00:36:15,580 --> 00:36:18,570
qui va mettre en œuvre cette
scénario d'ajouter 55 à la queue.

864
00:36:18,570 --> 00:36:20,950
Et pourrais-je avoir quelqu'un hop
et juste représenter 55?

865
00:36:20,950 --> 00:36:22,200
Très bien, vous êtes le nouveau 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Alors maintenant, que faire si la prochaine
scénario se présente,

868
00:36:27,054 --> 00:36:29,720
et nous voulons ajouter à la
début ou à la tête de cette liste?

869
00:36:29,720 --> 00:36:31,100
Et quel est votre nom, le numéro 55?

870
00:36:31,100 --> 00:36:31,420
>> PUBLIC: Jack.

871
00:36:31,420 --> 00:36:32,295
>> DAVID J. Malan: Jack?

872
00:36:32,295 --> 00:36:33,585
OK, nice to meet you.

873
00:36:33,585 --> 00:36:34,210
Bienvenue à bord.

874
00:36:34,210 --> 00:36:36,640
Alors maintenant, nous allons
insérer, par exemple, le nombre 5.

875
00:36:36,640 --> 00:36:39,840
Voici le deuxième cas de la
trois, nous est venu avec avant.

876
00:36:39,840 --> 00:36:43,050
Ainsi, si 5 appartient au début,
nous allons voir comment nous trouvons cela.

877
00:36:43,050 --> 00:36:46,310
Je initialiser mon ptr
pointeur vers le numéro 9 de nouveau.

878
00:36:46,310 --> 00:36:49,140
Et j'ai réalisé, oh, 5 est inférieur à 9.

879
00:36:49,140 --> 00:36:50,880
Donc, fixer cette image pour nous.

880
00:36:50,880 --> 00:36:54,820
Dont les mains, Gabe ou David
ou-- quel est le nom de numéro 9?

881
00:36:54,820 --> 00:36:55,740
>> PUBLIC: Jen.

882
00:36:55,740 --> 00:36:58,406
>> DAVID J. Malan: la hands-- de Jen
qui de nos mains il changer?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, donc Gabe souligne à quel moment?

885
00:37:00,970 --> 00:37:01,640
Chez moi.

886
00:37:01,640 --> 00:37:02,750
Je suis le nouveau nœud.

887
00:37:02,750 --> 00:37:04,870
Donc, je vais juste sorte de mouvement
ici pour voir visuellement.

888
00:37:04,870 --> 00:37:06,435
Et pendant ce temps qu'est-ce que je tiens à signaler que?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Encore où je pointe.

891
00:37:09,020 --> 00:37:10,000
Alors, c'est ça.

892
00:37:10,000 --> 00:37:13,717
Donc vraiment une ligne de correctifs de code
cette question, il semblerait.

893
00:37:13,717 --> 00:37:14,800
Très bien, alors c'est une bonne chose.

894
00:37:14,800 --> 00:37:17,580
Et quelqu'un peut-il être un espace réservé pour 5?

895
00:37:17,580 --> 00:37:18,080
Venez sur place.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Nous vous aiderons à reprendre la prochaine fois.

898
00:37:21,320 --> 00:37:24,280
>> Très bien, alors maintenant-- et
En aparté, les noms

899
00:37:24,280 --> 00:37:28,510
Je ne fais pas mention explicite de droit
maintenant, pointeur pred, prédécesseur pointeur

900
00:37:28,510 --> 00:37:31,260
et nouveau pointeur, c'est
seulement les prénoms

901
00:37:31,260 --> 00:37:35,280
dans l'exemple de code pour les pointeurs ou
mes mains c'est le genre de pointage autour.

902
00:37:35,280 --> 00:37:36,060
Quel est votre nom?

903
00:37:36,060 --> 00:37:36,700
>> PUBLIC: Christine.

904
00:37:36,700 --> 00:37:37,100
>> DAVID J. Malan: Christine.

905
00:37:37,100 --> 00:37:38,090
Bienvenue à bord.

906
00:37:38,090 --> 00:37:42,180
Très bien, alors nous allons examiner maintenant
un scénario un peu plus ennuyeux,

907
00:37:42,180 --> 00:37:46,350
par lequel je veux insérer
quelque chose comme 26 dans cette.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Quoi?

910
00:37:47,590 --> 00:37:50,510
Ceux-ci soient: une bonne chose que nous ayons ce stylo.

911
00:37:50,510 --> 00:37:51,955
Très bien, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Si quelqu'un pouvait obtenir un autre morceau de
papier prêt, juste à case-- tout droit.

914
00:37:57,570 --> 00:37:58,370
Oh, intéressant.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Eh bien c'est un exemple
d'un bug de conférence.

917
00:38:02,390 --> 00:38:03,894
OK alors quel est votre nom?

918
00:38:03,894 --> 00:38:04,560
PUBLIC: Julia.

919
00:38:04,560 --> 00:38:07,559
DAVID J. Malan: Julia, pouvez-vous pop
sur et prétendre que vous étiez jamais là?

920
00:38:07,559 --> 00:38:09,040
OK, ce n'est jamais arrivé.

921
00:38:09,040 --> 00:38:09,680
Merci.

922
00:38:09,680 --> 00:38:12,180
Donc, supposons que nous voulons insérer
Julia dans cette liste chaînée.

923
00:38:12,180 --> 00:38:13,780
Elle est le numéro 20.

924
00:38:13,780 --> 00:38:15,530
Et bien sûr, elle est
va appartenir à la

925
00:38:15,530 --> 00:38:17,521
begin-- ne pointent pas à quoi que ce soit encore.

926
00:38:17,521 --> 00:38:20,020
Ainsi, votre main peut être genre de
bas nulle ou une valeur à ordures.

927
00:38:20,020 --> 00:38:21,210
Disons l'histoire rapide.

928
00:38:21,210 --> 00:38:22,980
Je fais remarquer au numéro 5 cette fois.

929
00:38:22,980 --> 00:38:23,880
Ensuite, je vérifie 9.

930
00:38:23,880 --> 00:38:25,130
Ensuite, je vérifie 17.

931
00:38:25,130 --> 00:38:26,247
Ensuite, je vérifie 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
Et je me rends compte, ooh, Julia
doit aller avant le 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Alors, que faut-il faire?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Dont les mains ont besoin de changer?

938
00:38:36,910 --> 00:38:38,360
Julia, la mienne, ou--
quel est votre nom?

939
00:38:38,360 --> 00:38:39,230
>> PUBLIC: Christian.

940
00:38:39,230 --> 00:38:40,060
>> DAVID J. Malan: Christian ou?

941
00:38:40,060 --> 00:38:40,560
>> PUBLIC: Andy.

942
00:38:40,560 --> 00:38:40,905
>> DAVID J. Malan: Andy.

943
00:38:40,905 --> 00:38:41,654
Christian ou Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy doit pointer à?

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
Julia.

948
00:38:47,341 --> 00:38:47,840
Bien.

949
00:38:47,840 --> 00:38:48,960
Alors Andy, voulez-vous montrer à Julia?

950
00:38:48,960 --> 00:38:50,120
Mais attendez une minute.

951
00:38:50,120 --> 00:38:53,260
Dans l'histoire jusqu'à présent,
Je suis le genre de l'un

952
00:38:53,260 --> 00:38:56,800
en charge, dans le sens où
pointeur est la chose qui est

953
00:38:56,800 --> 00:38:57,850
déplacer dans la liste.

954
00:38:57,850 --> 00:39:00,800
Nous pourrions avoir un nom pour Andy, mais
il n'y a pas variable appelée Andy.

955
00:39:00,800 --> 00:39:04,320
La seule autre variable que nous avons est
la première, qui est représenté par Gabe.

956
00:39:04,320 --> 00:39:07,690
>> C'est en fait pourquoi donc
Jusqu'à présent, nous n'avons pas besoin de cela.

957
00:39:07,690 --> 00:39:10,846
Mais maintenant, sur l'écran, il est
parler à nouveau de pointeur pred.

958
00:39:10,846 --> 00:39:11,970
Alors permettez-moi d'être plus explicite.

959
00:39:11,970 --> 00:39:14,820
Si ce n'est pointeur, je ferais mieux de
obtenir un peu plus intelligent

960
00:39:14,820 --> 00:39:15,950
sur mon itération.

961
00:39:15,950 --> 00:39:19,580
Si cela ne vous dérange pas ma passant par ici
nouveau, pointant ici, pointant ici.

962
00:39:19,580 --> 00:39:22,500
Mais laissez-moi un pointeur pred,
prédécesseur pointeur, c'est

963
00:39:22,500 --> 00:39:24,740
type de pointage à l'
élément J'étais juste à.

964
00:39:24,740 --> 00:39:27,330
Donc, quand je vais ici, maintenant
mes mises à jour de la main gauche.

965
00:39:27,330 --> 00:39:29,370
Quand je vais ici mes mises à jour de la main gauche.

966
00:39:29,370 --> 00:39:33,090
Et maintenant, j'ai non seulement un pointeur vers
l'élément qui va après Julia,

967
00:39:33,090 --> 00:39:36,300
J'ai encore un pointeur vers
Andy, l'élément avant.

968
00:39:36,300 --> 00:39:39,430
Donc, vous avez accès, en substance,
chapelure, si vous voulez,

969
00:39:39,430 --> 00:39:41,500
pour tous les pointeurs nécessaires.

970
00:39:41,500 --> 00:39:43,710
>> Donc, si je montre
Andy et je suis aussi pointer

971
00:39:43,710 --> 00:39:47,105
à Christian, dont les mains
devrait maintenant être fait ailleurs?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Donc Andy peuvent maintenant signaler à Julia.

974
00:39:51,960 --> 00:39:54,460
Julia peut maintenant indiquer à Christian.

975
00:39:54,460 --> 00:39:56,950
Parce qu'elle peut copier mon
le pointeur de la main droite.

976
00:39:56,950 --> 00:40:00,044
Et qui vous met efficacement
retour dans ce lieu ici.

977
00:40:00,044 --> 00:40:02,460
Donc en bref, même si ce
est nous prendre sorte de toujours

978
00:40:02,460 --> 00:40:04,510
à mettre à jour une réalité
liste chaînée, réaliser

979
00:40:04,510 --> 00:40:06,580
que les opérations de
sont relativement simples.

980
00:40:06,580 --> 00:40:10,030
Il s'agit d'un, deux, trois
lignes de code en fin de compte.

981
00:40:10,030 --> 00:40:12,780
Mais enroulé autour de ceux
lignes de code vraisemblablement

982
00:40:12,780 --> 00:40:16,350
C'est un peu logique que efficace
pose la question, où en sommes-nous?

983
00:40:16,350 --> 00:40:18,970
Sommes-nous au début,
le milieu ou la fin?

984
00:40:18,970 --> 00:40:21,890
>> Maintenant, il ya certainement une autre
opérations que nous pourrions mettre en œuvre.

985
00:40:21,890 --> 00:40:24,880
Et ces photos ici représentent seulement
ce que nous venons de faire avec les humains.

986
00:40:24,880 --> 00:40:26,080
Qu'en est-il l'enlèvement?

987
00:40:26,080 --> 00:40:30,650
Si je veux, par exemple,
supprimer le numéro 34 ou 55,

988
00:40:30,650 --> 00:40:34,680
Je pourrais avoir le même genre de code,
mais je vais avoir besoin d'une ou deux étapes.

989
00:40:34,680 --> 00:40:36,110
Parce que ce qui est nouveau?

990
00:40:36,110 --> 00:40:40,460
Si je retire quelqu'un à la fin,
comme le nombre de 55, puis 34,

991
00:40:40,460 --> 00:40:42,995
ce qui a aussi de changer ce que je fais cela?

992
00:40:42,995 --> 00:40:44,870
Je dois pas evict--
quel est votre nom?

993
00:40:44,870 --> 00:40:45,380
>> PUBLIC: Jack.

994
00:40:45,380 --> 00:40:46,255
>> DAVID J. Malan: Jack.

995
00:40:46,255 --> 00:40:49,770
Je dois non seulement evict-- libre Jack,
si littéralement appeler sans Jack, ou au moins

996
00:40:49,770 --> 00:40:53,530
le pointeur là aussi, mais maintenant
ce qui doit changer avec Peter?

997
00:40:53,530 --> 00:40:55,510
Sa main meilleur départ vers le bas.

998
00:40:55,510 --> 00:40:59,300
Parce que dès que j'appelle gratuitement sur
Jack, si Peter pointant toujours à Jack

999
00:40:59,300 --> 00:41:02,530
et je garde donc traverser
la liste et l'accès de ce pointeur,

1000
00:41:02,530 --> 00:41:05,650
c'est là que notre vieil ami segmentation
la faute pourrait en fait botter.

1001
00:41:05,650 --> 00:41:07,860
Parce que nous avons donné l'
sauvegarde de la mémoire de Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Vous pouvez y rester
maladroitement pendant un moment.

1003
00:41:10,760 --> 00:41:13,410
Parce que nous avons juste un couple
opérations finales à prendre en compte.

1004
00:41:13,410 --> 00:41:15,600
Démontage de la tête de la liste,
ou la beginning-- et celui de

1005
00:41:15,600 --> 00:41:16,349
un peu ennuyeux.

1006
00:41:16,349 --> 00:41:19,640
Parce que nous devons savoir que Gabe
est une sorte de spécial dans ce programme.

1007
00:41:19,640 --> 00:41:21,440
Car en effet, il a son propre pointeur.

1008
00:41:21,440 --> 00:41:24,860
Il ne s'agit pas seulement d'être pointé,
comme presque tout le monde ici.

1009
00:41:24,860 --> 00:41:28,112
>> Ainsi, lorsque la tête de la liste est
enlevé, dont les mains ont besoin de changer maintenant?

1010
00:41:28,112 --> 00:41:29,070
Quel est votre nom?

1011
00:41:29,070 --> 00:41:29,450
>> PUBLIC: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> DAVID J. Malan: Je suis terrible
au nom, apparemment.

1013
00:41:31,408 --> 00:41:34,011
Donc, Christine et Gabe,
dont les mains ont besoin de changer

1014
00:41:34,011 --> 00:41:36,510
quand nous essayons de retirer Christine,
numéro 5, à partir de l'image?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, donc faisons Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe va pointer,
sans doute, au numéro 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Mais qu'est-ce qui doit se passer à côté?

1020
00:41:44,642 --> 00:41:46,600
PUBLIC: Christine devrait
nulle [inaudible].

1021
00:41:46,600 --> 00:41:50,244
DAVID J. Malan: OK, nous devrions probablement
make-- j'ai entendu "null" quelque part.

1022
00:41:50,244 --> 00:41:51,410
PUBLIC: Null et sa libre.

1023
00:41:51,410 --> 00:41:51,855
DAVID J. Malan: Null quoi?

1024
00:41:51,855 --> 00:41:53,074
PUBLIC: Null et sa libre.

1025
00:41:53,074 --> 00:41:54,490
DAVID J. Malan: Null et sa libre.

1026
00:41:54,490 --> 00:41:55,422
Donc, c'est très facile.

1027
00:41:55,422 --> 00:41:58,380
Et c'est parfait que vous êtes maintenant sorte
de se tenir là, ne faisant pas partie.

1028
00:41:58,380 --> 00:42:00,430
Parce que vous avez été
découplé de la liste.

1029
00:42:00,430 --> 00:42:02,820
Vous avez effectivement été
orphelins de la liste.

1030
00:42:02,820 --> 00:42:07,770
Et si nous avions mieux appeler gratuitement dès maintenant sur
Christine donner que la mémoire de retour.

1031
00:42:07,770 --> 00:42:10,240
Sinon chaque fois que nous
supprimer un noeud dans la liste

1032
00:42:10,240 --> 00:42:14,230
nous pourrions faisons la liste
plus courte, mais pas réellement décroissant

1033
00:42:14,230 --> 00:42:15,096
la taille de la mémoire.

1034
00:42:15,096 --> 00:42:17,720
Et si nous continuons d'ajouter et
ajoutant, ajouter des choses à la liste,

1035
00:42:17,720 --> 00:42:19,280
mon ordinateur pourrait devenir plus lent
et plus lent et plus lent,

1036
00:42:19,280 --> 00:42:21,740
parce que je suis à court de
mémoire, même si je ne suis pas fait

1037
00:42:21,740 --> 00:42:25,580
à l'aide de bytes de Christine
de mémoire plus.

1038
00:42:25,580 --> 00:42:28,500
>> Donc à la fin il ya d'autres
scénarios d'enlèvement course--

1039
00:42:28,500 --> 00:42:30,640
dans le milieu, l'élimination
à la fin, comme nous l'avons vu.

1040
00:42:30,640 --> 00:42:32,348
Mais le plus intéressant
défi est maintenant

1041
00:42:32,348 --> 00:42:34,770
va être de considérer exactement
ce que le temps d'exécution est.

1042
00:42:34,770 --> 00:42:36,640
Donc, non seulement vous pouvez garder votre
morceaux de papier, si, Gabe,

1043
00:42:36,640 --> 00:42:38,640
vous ne me dérangerait pas de donner
chacun une balle anti-stress.

1044
00:42:38,640 --> 00:42:42,100
Merci beaucoup à notre liste chaînée
de bénévoles ici, s'il vous plaît.

1045
00:42:42,100 --> 00:42:45,320
>> [Applaudissements]

1046
00:42:45,320 --> 00:42:46,700
>> DAVID J. Malan: Très bien.

1047
00:42:46,700 --> 00:42:51,110
Alors quelques analytique
des questions puis, si je pouvais.

1048
00:42:51,110 --> 00:42:59,670
Nous avons vu cette notation avant,
grand O et l'oméga, les limites supérieures

1049
00:42:59,670 --> 00:43:02,520
et des bornes inférieures sur le
temps d'un algorithme en cours d'exécution.

1050
00:43:02,520 --> 00:43:04,950
Donc, nous allons examiner tout
quelques questions.

1051
00:43:04,950 --> 00:43:07,090
>> Un, et nous l'avons dit
avant, ce qui est le fonctionnement

1052
00:43:07,090 --> 00:43:10,647
temps de recherche d'un
liste en termes de grand O?

1053
00:43:10,647 --> 00:43:13,480
Qu'est-ce que c'est une limite supérieure sur le fonctionnement
temps de recherche d'une liste chaînée

1054
00:43:13,480 --> 00:43:16,340
mis en œuvre par nos bénévoles ici?

1055
00:43:16,340 --> 00:43:17,820
Il est grand O de n, linéaire.

1056
00:43:17,820 --> 00:43:20,630
Parce que dans le pire des cas,
l'élément, comme 55,

1057
00:43:20,630 --> 00:43:23,830
nous pourrions être à la recherche d'pourrions être là où
Jack était, tout le chemin à la fin.

1058
00:43:23,830 --> 00:43:28,250
Et malheureusement, contrairement à un tableau
nous ne pouvons pas obtenir la fantaisie cette fois.

1059
00:43:28,250 --> 00:43:31,820
Même si tous nos humains étaient
triés à partir de petits éléments, 5,

1060
00:43:31,820 --> 00:43:35,900
sur toute la hauteur de l'élément plus grand,
55, c'est généralement une bonne chose.

1061
00:43:35,900 --> 00:43:38,815
Mais qu'est-ce que cette hypothèse
ne nous permet de faire?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
PUBLIC: [inaudible]

1064
00:43:40,650 --> 00:43:40,920
DAVID J. Malan: Dites à nouveau?

1065
00:43:40,920 --> 00:43:41,800
PUBLIC: accès aléatoire.

1066
00:43:41,800 --> 00:43:43,049
DAVID J. Malan: accès aléatoire.

1067
00:43:43,049 --> 00:43:46,330
Et à son tour, cela signifie que nous ne pouvons
plus utiliser zéros faible, l'intuition,

1068
00:43:46,330 --> 00:43:49,365
et l'évidence de l'utilisation binaire
recherche et de diviser et conquérir.

1069
00:43:49,365 --> 00:43:51,240
Parce que même si nous
l'homme ne pouvait évidemment

1070
00:43:51,240 --> 00:43:54,610
voir que Andy ou chrétienne étaient
à peu près au milieu de la liste,

1071
00:43:54,610 --> 00:43:57,670
nous savons seulement que comme un
ordinateur en parcourant la liste

1072
00:43:57,670 --> 00:43:59,029
dès le début.

1073
00:43:59,029 --> 00:44:00,570
Nous avons donc renoncé à ce que l'accès aléatoire.

1074
00:44:00,570 --> 00:44:04,380
>> Donc grand O n est maintenant la partie supérieure
lié à notre temps de recherche.

1075
00:44:04,380 --> 00:44:07,920
Qu'en est-il oméga de notre recherche?

1076
00:44:07,920 --> 00:44:11,535
Quelle est la limite inférieure sur la recherche
pour un nombre dans cette liste?

1077
00:44:11,535 --> 00:44:12,410
PUBLIC: [inaudible]

1078
00:44:12,410 --> 00:44:13,040
DAVID J. Malan: Dites à nouveau?

1079
00:44:13,040 --> 00:44:13,420
PUBLIC: Un.

1080
00:44:13,420 --> 00:44:13,800
DAVID J. Malan: One.

1081
00:44:13,800 --> 00:44:14,760
Temps si constant.

1082
00:44:14,760 --> 00:44:17,020
Dans le meilleur des cas, Christine est
en effet, au début de la liste.

1083
00:44:17,020 --> 00:44:19,020
Et nous sommes à la recherche
numéro 5, alors nous l'avons trouvé.

1084
00:44:19,020 --> 00:44:19,787
Donc, pas grand-chose.

1085
00:44:19,787 --> 00:44:22,370
Mais elle a obtenu d'être à la
au début de la liste dans ce cas.

1086
00:44:22,370 --> 00:44:23,745
Qu'en est-il quelque chose comme Delete?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Que faire si vous voulez supprimer un élément?

1089
00:44:26,300 --> 00:44:29,200
Quelle est la limite supérieure et la limite inférieure
sur la suppression de quelque chose d'un lien

1090
00:44:29,200 --> 00:44:29,699
la liste?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
PUBLIC: [inaudible]

1093
00:44:36,070 --> 00:44:36,420
DAVID J. Malan: Dites à nouveau?

1094
00:44:36,420 --> 00:44:37,067
PUBLIC: n.

1095
00:44:37,067 --> 00:44:38,900
DAVID J. Malan: n est
en effet la borne supérieure.

1096
00:44:38,900 --> 00:44:41,700
Parce que dans le pire des cas, nous essayons
supprimer Jack, comme nous venons de le faire.

1097
00:44:41,700 --> 00:44:43,050
Il est tout le chemin à la fin.

1098
00:44:43,050 --> 00:44:45,419
Nous prend une éternité, ou
n des mesures pour lui trouver.

1099
00:44:45,419 --> 00:44:46,460
C'est donc une limite supérieure.

1100
00:44:46,460 --> 00:44:47,430
C'est linéaire, bien sûr.

1101
00:44:47,430 --> 00:44:50,970
Et le meilleur des cas durée, ou
les limites inférieures dans le meilleur des cas

1102
00:44:50,970 --> 00:44:51,975
serait temps constant.

1103
00:44:51,975 --> 00:44:54,600
Peut-être parce que nous essayons de supprimer
Christine, et nous obtenons juste de la chance

1104
00:44:54,600 --> 00:44:55,558
elle est au début.

1105
00:44:55,558 --> 00:44:56,350
Maintenant, attendez une minute.

1106
00:44:56,350 --> 00:44:59,370
Gabe était aussi au début,
et nous avons également de mettre à jour Gabe.

1107
00:44:59,370 --> 00:45:01,150
Donc, ce n'était pas juste une étape.

1108
00:45:01,150 --> 00:45:04,210
Ainsi est-il en effet constant
temps, dans le meilleur des cas,

1109
00:45:04,210 --> 00:45:06,345
à enlever l'élément le plus petit?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Il est, même si cela peut être deux,
trois, ou même 100 lignes de code,

1112
00:45:10,960 --> 00:45:14,000
si c'est le même nombre de
lignes, et non dans une certaine boucle,

1113
00:45:14,000 --> 00:45:16,577
et indépendant de la taille
de la liste, absolument.

1114
00:45:16,577 --> 00:45:18,660
Suppression de l'élément à
le début de la liste,

1115
00:45:18,660 --> 00:45:21,940
même si nous devons faire face à
Gabe, est encore temps constant.

1116
00:45:21,940 --> 00:45:24,220
>> Donc, cela semble être un
énorme pas en arrière.

1117
00:45:24,220 --> 00:45:27,000
Et qu'est-ce une perte de temps
si, dans la première semaine et la semaine

1118
00:45:27,000 --> 00:45:30,250
zéro, nous avons eu non seulement
code pseudo mais le code réel

1119
00:45:30,250 --> 00:45:35,780
de mettre en œuvre quelque chose qui est journal
de base n, ou connectez-vous plutôt de n, base 2,

1120
00:45:35,780 --> 00:45:37,150
en fonction de sa durée de fonctionnement.

1121
00:45:37,150 --> 00:45:40,710
Alors pourquoi diable aurions-nous envie de commencer
en utilisant quelque chose comme une liste chaînée?

1122
00:45:40,710 --> 00:45:41,517
Ouais.

1123
00:45:41,517 --> 00:45:44,022
>> PUBLIC: Donc, vous pouvez ajouter
éléments au tableau.

1124
00:45:44,022 --> 00:45:46,230
DAVID J. Malan: Ainsi, vous pouvez
ajouter des éléments au tableau.

1125
00:45:46,230 --> 00:45:47,550
Et cela aussi est thématique.

1126
00:45:47,550 --> 00:45:49,740
Et nous allons continuer à voir
ce, ce compromis, beaucoup

1127
00:45:49,740 --> 00:45:51,573
comme nous l'avons vu un
compromis avec le tri par fusion.

1128
00:45:51,573 --> 00:45:54,606
Nous ne pouvions accélérer
recherche ou de tri, plutôt,

1129
00:45:54,606 --> 00:45:57,480
si nous passons un peu plus d'espace et
avoir un morceau supplémentaire d'un mémoire

1130
00:45:57,480 --> 00:45:58,760
ou un tableau pour le tri par fusion.

1131
00:45:58,760 --> 00:46:01,270
Mais nous passons plus de
espace, mais nous gagnons du temps.

1132
00:46:01,270 --> 00:46:04,820
Dans ce cas, nous sommes
donner du temps, mais nous sommes

1133
00:46:04,820 --> 00:46:08,170
gagner en flexibilité,
dynamisme si vous voulez,

1134
00:46:08,170 --> 00:46:10,280
qui est sans doute un élément positif.

1135
00:46:10,280 --> 00:46:11,520
>> Nous sommes également passer espace.

1136
00:46:11,520 --> 00:46:13,710
Dans quel sens est un lien
liste plus cher

1137
00:46:13,710 --> 00:46:15,700
en termes d'espace qu'un tableau?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Où est l'espace supplémentaire vient?

1140
00:46:19,920 --> 00:46:20,460
Ouais?

1141
00:46:20,460 --> 00:46:21,800
>> PUBLIC: [inaudible] pointeur.

1142
00:46:21,800 --> 00:46:23,310
>> DAVID J. Malan: Oui, nous
ont également le pointeur.

1143
00:46:23,310 --> 00:46:25,560
Donc, c'est gênant minorly
en ce que je ne suis plus

1144
00:46:25,560 --> 00:46:27,780
Je stocker juste un int
pour représenter un int.

1145
00:46:27,780 --> 00:46:30,990
Je stocker un int et un
pointeur, qui est également 32 bits.

1146
00:46:30,990 --> 00:46:33,470
Donc, je suis littéralement doubler
la quantité d'espace impliqué.

1147
00:46:33,470 --> 00:46:36,040
Donc, c'est un compromis, mais
c'est dans le cas d'int.

1148
00:46:36,040 --> 00:46:39,580
Supposons que vous n'êtes pas stocker int,
mais supposons chacun de ces rectangles

1149
00:46:39,580 --> 00:46:43,290
ou chacun de ces êtres humains représentait
un mot, un mot anglais qui

1150
00:46:43,290 --> 00:46:46,430
peut-être cinq caractères, 10
personnages, peut-être même plus.

1151
00:46:46,430 --> 00:46:49,940
Puis en ajoutant seulement 32 plus de bits
peut-être moins d'une grosse affaire.

1152
00:46:49,940 --> 00:46:52,160
>> Et si chacun des élèves
à la manifestation

1153
00:46:52,160 --> 00:46:55,107
étaient littéralement struct étudiants qui
ont des noms et des maisons et peut-être

1154
00:46:55,107 --> 00:46:57,065
les numéros de téléphone et Twitter
poignées et autres.

1155
00:46:57,065 --> 00:46:59,564
Donc, tous les domaines, nous avons commencé
parler l'autre jour,

1156
00:46:59,564 --> 00:47:02,410
beaucoup moins d'un gros problème,
nos nœuds deviennent plus intéressantes

1157
00:47:02,410 --> 00:47:05,972
et gros pour passer, hein, un montant supplémentaire de
pointeur juste pour les relier.

1158
00:47:05,972 --> 00:47:07,180
Mais en fait, c'est un compromis.

1159
00:47:07,180 --> 00:47:09,560
Et en effet, le code est
plus complexe, car vous aurez

1160
00:47:09,560 --> 00:47:11,770
voir en parcourant
cet exemple particulier.

1161
00:47:11,770 --> 00:47:14,302
Mais s'il y avait
un texte sacré ici.

1162
00:47:14,302 --> 00:47:17,010
Et si nous ne prenons pas une étape
en arrière, mais un énorme pas en avant

1163
00:47:17,010 --> 00:47:19,180
et mettre en œuvre un ensemble de données
la structure par laquelle nous

1164
00:47:19,180 --> 00:47:22,870
peut trouver des éléments comme Jack ou
Christine ou tout autre élément

1165
00:47:22,870 --> 00:47:25,870
dans ce tableau en vrai constante de temps?

1166
00:47:25,870 --> 00:47:26,920
Recherche est constante.

1167
00:47:26,920 --> 00:47:28,320
Supprimer est constante.

1168
00:47:28,320 --> 00:47:29,570
Insérer est constante.

1169
00:47:29,570 --> 00:47:32,260
Toutes ces opérations sont constants.

1170
00:47:32,260 --> 00:47:33,750
Ce serait notre saint Graal.

1171
00:47:33,750 --> 00:47:36,690
Et c'est là que nous
va chercher la prochaine fois.

1172
00:47:36,690 --> 00:47:38,600
Rendez-vous donc.

1173
00:47:38,600 --> 00:47:39,371