1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Semaine 6]

2
00:00:02,000 --> 00:00:04,000
[David J. Malan] [Université de Harvard]

3
00:00:04,000 --> 00:00:08,000
[C'est CS50.] [CS50.TV]

4
00:00:08,000 --> 00:00:12,000
>> C'est CS50, et c'est le début de la semaine 6,

5
00:00:12,000 --> 00:00:16,000
si un couple de nouveaux outils sont maintenant disponibles pour vous permettre de profiter,

6
00:00:16,000 --> 00:00:19,000
dont le premier est appelé CS50 style.

7
00:00:19,000 --> 00:00:22,000
Les chances sont, si vous êtes comme moi ou l'un des compagnons d'enseignement,

8
00:00:22,000 --> 00:00:26,000
vous avez probablement vu un programme dont le style ressemble un petit quelque chose comme ça.

9
00:00:26,000 --> 00:00:30,000
Peut-être que vous commencer à couper quelques virages tard dans la nuit, ou vous allez traiter avec elle plus tard,

10
00:00:30,000 --> 00:00:32,000
puis un TF ou CA sont plus durant les heures de bureau.

11
00:00:32,000 --> 00:00:34,000
Ensuite, il est difficile pour nous de lire.

12
00:00:34,000 --> 00:00:38,000
Eh bien, ce code est syntaxiquement correct, et il faudra compiler, et il va vraiment fonctionner.

13
00:00:38,000 --> 00:00:40,000
Mais ce n'est certainement pas un 5 pour le style.

14
00:00:40,000 --> 00:00:45,000
>> Mais maintenant, si nous allons dans ce répertoire ci-

15
00:00:45,000 --> 00:00:48,000
et remarquez que je n'ai conditions2.c-

16
00:00:48,000 --> 00:00:55,000
et je lance cette nouvelle commande, style50, sur ce conditions2.c fichier, Entrée,

17
00:00:55,000 --> 00:00:57,000
remarquez que ce n'est m'a informé qu'il a été stylisée.

18
00:00:57,000 --> 00:01:00,000
Gedit remarqué que le fichier a été modifié sur le disque,

19
00:01:00,000 --> 00:01:08,000
et si je clique sur recharger, tous vos problèmes sont maintenant automatisées.

20
00:01:08,000 --> 00:01:15,000
[Applaudissements]

21
00:01:15,000 --> 00:01:17,000
C'est l'une des choses que nous avons ce week-end.

22
00:01:17,000 --> 00:01:20,000
Sachez qu'il est imparfait, car il ya peu de code

23
00:01:20,000 --> 00:01:23,000
qu'il suffit de ne pas être en mesure de styliser parfaitement,

24
00:01:23,000 --> 00:01:26,000
mais rends compte que c'est maintenant un outil, vous pouvez profiter de

25
00:01:26,000 --> 00:01:33,000
si ce n'est que pour ranger quelques-uns des accolades plus errantly placé bouclés, etc.

26
00:01:33,000 --> 00:01:36,000
>> Mais plus convaincant est maintenant CS50 Check.

27
00:01:36,000 --> 00:01:39,000
Avec CS50 Check, vous pouvez réellement effectuer les tests exactitude mêmes

28
00:01:39,000 --> 00:01:42,000
sur votre propre code que les boursiers d'enseignement sont capables.

29
00:01:42,000 --> 00:01:44,000
Il s'agit d'un utilitaire de ligne de commande qui est maintenant dans l'appareil

30
00:01:44,000 --> 00:01:46,000
dès que vous faites un update50 selon

31
00:01:46,000 --> 00:01:49,000
pset 4 des spécifications, et vous l'utiliser essentiellement comme ça.

32
00:01:49,000 --> 00:01:51,000
Vous exécutez la commande check50.

33
00:01:51,000 --> 00:01:56,000
Puis vous passez un argument de ligne de commande, ou plus généralement connu comme un interrupteur ou un drapeau.

34
00:01:56,000 --> 00:01:58,000
En général, les choses qui ont traits d'union sont appelé un commutateur

35
00:01:58,000 --> 00:02:02,000
à un programme de ligne de commande,-c spécifie

36
00:02:02,000 --> 00:02:04,000
les contrôles que vous souhaitez exécuter.

37
00:02:04,000 --> 00:02:07,000
>> Les tests que vous souhaitez exécuter sont identifiés individuellement par cette chaîne,

38
00:02:07,000 --> 00:02:10,000
2012/pset4/resize.

39
00:02:10,000 --> 00:02:13,000
En d'autres termes, c'est juste une chaîne arbitraire mais unique

40
00:02:13,000 --> 00:02:18,000
que nous utilisons pour identifier de manière unique les tests exactitude de 4 pset.

41
00:02:18,000 --> 00:02:21,000
Et puis vous spécifiez une liste séparée par des espaces des fichiers que vous souhaitez télécharger

42
00:02:21,000 --> 00:02:24,000
pour CS50 Vérifier fins d'analyse.

43
00:02:24,000 --> 00:02:29,000
Par exemple, si je vais dans ma solution ici pour resize.c-

44
00:02:29,000 --> 00:02:31,000
Permettez-moi d'ouvrir une fenêtre de terminal plus grand-

45
00:02:31,000 --> 00:02:42,000
et je vais de l'avant et de fonctionner disons check50-c 2012/pset4/resize,

46
00:02:42,000 --> 00:02:46,000
et puis je aller de l'avant et de préciser les noms des fichiers,

47
00:02:46,000 --> 00:02:49,000
resize.c, puis appuyez sur Entrée, il compresse,

48
00:02:49,000 --> 00:02:53,000
il télécharge, il vérifie, et je vient d'échouer tout un tas de tests.

49
00:02:53,000 --> 00:02:59,000
L'une en rouge en haut à gauche indique que resize.c et bmp exister.

50
00:02:59,000 --> 00:03:01,000
C'était le test. Telle était la question que nous posions.

51
00:03:01,000 --> 00:03:04,000
Et c'est malheureux parce que la réponse était fausse.

52
00:03:04,000 --> 00:03:08,000
Le texte blanc en dessous il est dit s'attendre bmp.h d'exister, et c'est tout simplement ma faute.

53
00:03:08,000 --> 00:03:11,000
J'ai oublié de le charger, donc j'ai besoin de télécharger les deux fichiers,

54
00:03:11,000 --> 00:03:14,000
resize.c et bmp.h.

55
00:03:14,000 --> 00:03:17,000
Mais remarquez maintenant tous les autres tests sont en jaune parce qu'ils n'ont pas exécuté,

56
00:03:17,000 --> 00:03:21,000
et si le smiley est verticale, car il n'est ni heureux ni triste,

57
00:03:21,000 --> 00:03:25,000
mais nous devons remédier à ce problème en rouge avant les autres contrôles seront exécutés.

58
00:03:25,000 --> 00:03:27,000
>> Permettez-moi de résoudre ce problème.

59
00:03:27,000 --> 00:03:30,000
Permettez-moi de faire un zoom arrière et refaire cette, cette fois avec bmp.h aussi

60
00:03:30,000 --> 00:03:34,000
sur la ligne de commande, entrez, et maintenant, si tout va bien,

61
00:03:34,000 --> 00:03:38,000
il va vérifier et retourner un résultat des-retenez votre souffle-

62
00:03:38,000 --> 00:03:42,000
tout en vert, ce qui signifie que je fais vraiment bien sur pset 4 pour autant.

63
00:03:42,000 --> 00:03:44,000
Vous pouvez voir et en déduire le texte descriptif ici

64
00:03:44,000 --> 00:03:47,000
exactement ce que c'est que nous avons testé.

65
00:03:47,000 --> 00:03:49,000
Nous avons testé un premier temps ne les fichiers existent?

66
00:03:49,000 --> 00:03:51,000
Nous avons ensuite testé de la compilation resize.c?

67
00:03:51,000 --> 00:03:58,000
Puis nous avons testé n'est-il pas redimensionner une BMP 1x1 pixel lorsque n, le facteur de redimensionnement, est 1.

68
00:03:58,000 --> 00:04:01,000
Maintenant, si vous n'avez aucune idée de ce qui n est, vous une fois que vous plonger dans pset 4,

69
00:04:01,000 --> 00:04:04,000
mais c'est tout simplement une vérification de cohérence pour s'assurer que vous n'êtes pas le redimensionnement

70
00:04:04,000 --> 00:04:08,000
une image du tout si le facteur de redimensionnement est 1.

71
00:04:08,000 --> 00:04:14,000
Si, en revanche, il redimensionne un pixel 1x1 à un 1x1 à 2x2 pixel BMP correctement

72
00:04:14,000 --> 00:04:19,000
lorsque n est 2, alors même, le mien fait en conséquence.

73
00:04:19,000 --> 00:04:22,000
>> En bref, cela signifie, premièrement, prendre les croisant les doigts

74
00:04:22,000 --> 00:04:25,000
de l'équation à droite avant de soumettre votre pset.

75
00:04:25,000 --> 00:04:28,000
Vous saurez exactement ce que vous saurez bientôt TF

76
00:04:28,000 --> 00:04:30,000
quand vous allez sur la soumission de certains de ces ensembles de problèmes,

77
00:04:30,000 --> 00:04:34,000
ainsi que la motivation pédagogique est vraiment à mettre

78
00:04:34,000 --> 00:04:37,000
l'occasion en face de vous de sorte que lorsque vous savez a priori

79
00:04:37,000 --> 00:04:39,000
qu'il ya des bugs dans votre code et des essais qui ne sont pas passés,

80
00:04:39,000 --> 00:04:43,000
vous pouvez mettre dans le temps plus efficace à l'avant pour résoudre ces problèmes

81
00:04:43,000 --> 00:04:45,000
plutôt que de perdre des points, obtenir la rétroaction de votre carte de TF,

82
00:04:45,000 --> 00:04:48,000
et puis aller, "Ahh", comme je l'aurais compris cela.

83
00:04:48,000 --> 00:04:50,000
Maintenant, au moins il ya un outil pour vous aider à trouver ça.

84
00:04:50,000 --> 00:04:52,000
Il ne va pas à signaler le bug, mais il vous dira

85
00:04:52,000 --> 00:04:54,000
ce qui est symptomatique d'elle.

86
00:04:54,000 --> 00:04:57,000
>> Maintenant, réaliser les tests ne sont pas nécessairement exhaustive.

87
00:04:57,000 --> 00:04:59,000
Juste parce que vous obtenez un écran de verdure binettes

88
00:04:59,000 --> 00:05:02,000
ne signifie pas que votre code est parfait, mais cela ne signifie

89
00:05:02,000 --> 00:05:06,000
qu'il a adopté certains critères prescrits par la spécification.

90
00:05:06,000 --> 00:05:08,000
Parfois, nous ne divulguerons pas les chèques.

91
00:05:08,000 --> 00:05:10,000
Par exemple, polar, l'un des aspects de la pset 4,

92
00:05:10,000 --> 00:05:15,000
est un peu décevant si nous vous donnons

93
00:05:15,000 --> 00:05:18,000
la réponse à ce qu'il est, et il ya un certain nombre de façons de révéler

94
00:05:18,000 --> 00:05:21,000
qui est la personne à qui le bruit rouge.

95
00:05:21,000 --> 00:05:24,000
La spécification sera toujours préciser à l'avenir pour pset 5 Onward

96
00:05:24,000 --> 00:05:26,000
ce qui vérifie existent pour vous.

97
00:05:26,000 --> 00:05:28,000
Vous remarquerez qu'il ya cette URL blanc au fond.

98
00:05:28,000 --> 00:05:30,000
Pour l'instant, ce n'est qu'une sortie de diagnostic.

99
00:05:30,000 --> 00:05:33,000
Si vous visitez cette URL, vous aurez tout un tas de fous, messages cryptiques

100
00:05:33,000 --> 00:05:36,000
que vous êtes les bienvenus pour regarder à travers, mais c'est surtout pour le personnel

101
00:05:36,000 --> 00:05:41,000
afin que nous puissions diagnostiquer et déboguer des bugs dans check50 lui-même.

102
00:05:41,000 --> 00:05:46,000
>> Sans tarder, nous allons passer à l'endroit où nous nous sommes quittés.

103
00:05:46,000 --> 00:05:48,000
CS50 bibliothèque, nous avons pris pour acquis depuis quelques semaines,

104
00:05:48,000 --> 00:05:52,000
mais la semaine dernière, nous avons commencé à éplucher une des couches de celui-ci.

105
00:05:52,000 --> 00:05:55,000
Nous avons commencé à mettre de côté corde en faveur de ce lieu?

106
00:05:55,000 --> 00:05:57,000
[Les élèves] Char.

107
00:05:57,000 --> 00:05:59,000
Char *, qui a été un char * tout ce temps,

108
00:05:59,000 --> 00:06:03,000
mais maintenant, nous n'avons pas de prétendre que c'est une chaîne de type de données réel.

109
00:06:03,000 --> 00:06:06,000
Au contraire, il a été un synonyme de sortes de char *,

110
00:06:06,000 --> 00:06:09,000
et une chaîne de caractères est une séquence de caractères,

111
00:06:09,000 --> 00:06:14,000
alors pourquoi est-il sensé pour représenter des chaînes comme char * s?

112
00:06:14,000 --> 00:06:20,000
Qu'est-ce qu'un char * représenter dans le cadre de ce concept d'une chaîne?

113
00:06:20,000 --> 00:06:23,000
Ouais. >> [Étudiants] Le premier caractère.

114
00:06:23,000 --> 00:06:25,000
Bon, le premier caractère, mais pas tout à fait le premier caractère.

115
00:06:25,000 --> 00:06:27,000
Ce sont les étudiants-[] Adresse.

116
00:06:27,000 --> 00:06:29,000
Bonne, l'adresse du premier caractère.

117
00:06:29,000 --> 00:06:33,000
Tout ce qui est nécessaire pour représenter une chaîne en mémoire d'un ordinateur

118
00:06:33,000 --> 00:06:36,000
est tout simplement l'adresse unique de sa première octet.

119
00:06:36,000 --> 00:06:38,000
Vous n'avez même pas besoin de savoir combien de temps il est

120
00:06:38,000 --> 00:06:42,000
parce que comment pouvez-vous comprendre cela de manière dynamique?

121
00:06:42,000 --> 00:06:44,000
[Étudiants] longueur de la chaîne.

122
00:06:44,000 --> 00:06:48,000
Vous pouvez appeler longueur de la chaîne, excellent, mais comment fonctionne-t-longueur de la chaîne?

123
00:06:48,000 --> 00:06:50,000
Que faut-il faire? Ouais.

124
00:06:50,000 --> 00:06:52,000
[Étudiants] Continuez jusqu'à ce que vous obtenez le caractère nul.

125
00:06:52,000 --> 00:06:54,000
Oui, exactement, il parcourt seulement avec une boucle for, while,

126
00:06:54,000 --> 00:06:57,000
que ce soit de * jusqu'à la fin, et la fin est représentée

127
00:06:57,000 --> 00:07:01,000
par \ 0, le caractère soi-disant nul, nul,

128
00:07:01,000 --> 00:07:05,000
à ne pas confondre avec nulle, ce qui est un pointeur,

129
00:07:05,000 --> 00:07:07,000
qui entrera dans la conversation encore aujourd'hui.

130
00:07:07,000 --> 00:07:11,000
>> Nous épluché une couche de getInt, puis nous avons pris un coup d'oeil à GetString,

131
00:07:11,000 --> 00:07:14,000
et de rappeler que ces deux fonctions, ou bien,

132
00:07:14,000 --> 00:07:18,000
GetString, utilisait une certaine fonction

133
00:07:18,000 --> 00:07:21,000
à analyser en fait, qui est, de lire ou d'analyser, d'entrée de l'utilisateur.

134
00:07:21,000 --> 00:07:25,000
Et quelle est cette nouvelle fonction?

135
00:07:25,000 --> 00:07:27,000
Scanf ou sscanf. Il s'agit en fait de quelques saveurs différentes.

136
00:07:27,000 --> 00:07:31,000
Il ya scanf, il ya sscanf, il ya fscanf.

137
00:07:31,000 --> 00:07:35,000
Pour le moment, cependant, concentrons-nous sur le plus facile à illustrer,

138
00:07:35,000 --> 00:07:38,000
et laissez-moi aller de l'avant et d'ouvrir dans l'appareil

139
00:07:38,000 --> 00:07:41,000
un fichier comme celui-ci, scanf1.c.

140
00:07:41,000 --> 00:07:43,000
Il s'agit d'un programme super simple,

141
00:07:43,000 --> 00:07:46,000
mais qui fait quelque chose que nous n'avons jamais fait

142
00:07:46,000 --> 00:07:48,000
sans l'aide de la bibliothèque CS50.

143
00:07:48,000 --> 00:07:51,000
Cela devient un int à partir d'un utilisateur. Comment ça marche?

144
00:07:51,000 --> 00:07:53,000
Eh bien, à la ligne 16 là-bas,

145
00:07:53,000 --> 00:07:56,000
remarquerez que nous déclarons un int x appelés, et à ce moment de l'histoire,

146
00:07:56,000 --> 00:07:58,000
quelle est la valeur de x?

147
00:07:58,000 --> 00:08:00,000
[Réponse de l'élève inaudible]

148
00:08:00,000 --> 00:08:02,000
[David M.] Droite, qui sait, une valeur des déchets potentiellement, donc en 17, que nous venons de dire à l'utilisateur

149
00:08:02,000 --> 00:08:06,000
me donner un numéro, s'il vous plaît, et l'étape 18 est là que ça devient intéressant.

150
00:08:06,000 --> 00:08:11,000
Scanf semble emprunter une idée de printf en ce qu'il utilise ces codes de format entre guillemets.

151
00:08:11,000 --> 00:08:13,000
% D est bien sûr un nombre décimal.

152
00:08:13,000 --> 00:08:21,000
Mais pourquoi suis-je en passant et x au lieu de seulement x?

153
00:08:21,000 --> 00:08:24,000
Le premier est correcte. Ouais.

154
00:08:24,000 --> 00:08:26,000
[Réponse de l'élève inaudible]

155
00:08:26,000 --> 00:08:31,000
Justement, si l'objectif de ce programme, comme le getInt fonction elle-même,

156
00:08:31,000 --> 00:08:34,000
est d'obtenir un int de l'utilisateur je peux passer des fonctions

157
00:08:34,000 --> 00:08:38,000
toutes les variables que je veux, mais si je ne les passer par référence

158
00:08:38,000 --> 00:08:41,000
ou par adresse ou par pointeur, tous synonymes à des fins d'aujourd'hui,

159
00:08:41,000 --> 00:08:46,000
alors que la fonction n'a pas la possibilité de modifier le contenu de cette variable.

160
00:08:46,000 --> 00:08:49,000
Cela passerait dans une copie tout comme la version buggy de swap de

161
00:08:49,000 --> 00:08:51,000
que nous avons parlé quelques fois maintenant.

162
00:08:51,000 --> 00:08:54,000
>> Mais à la place, et en faisant x, je suis littéralement en passant quoi?

163
00:08:54,000 --> 00:08:57,000
[Étudiants] L'adresse. >> L'adresse de x.

164
00:08:57,000 --> 00:09:01,000
C'est comme dessiner une carte pour la fonction scanf appelé et dit ici,

165
00:09:01,000 --> 00:09:04,000
ce sont des indications pour un morceau de la mémoire de l'ordinateur

166
00:09:04,000 --> 00:09:07,000
que vous pouvez aller stocker un entier po

167
00:09:07,000 --> 00:09:10,000
Pour sscanf maintenant faire

168
00:09:10,000 --> 00:09:13,000
quel opérateur, ce morceau de syntaxe est ce que ça va avoir à utiliser

169
00:09:13,000 --> 00:09:19,000
même si nous ne pouvons pas le voir parce que quelqu'un d'autre a écrit cette fonction?

170
00:09:19,000 --> 00:09:21,000
En d'autres termes - ce que c'est?

171
00:09:21,000 --> 00:09:23,000
[Étudiants] X lire.

172
00:09:23,000 --> 00:09:27,000
Il va y avoir un peu de lecture, mais seulement par rapport à x ici.

173
00:09:27,000 --> 00:09:30,000
Si scanf est passé l'adresse de x,

174
00:09:30,000 --> 00:09:35,000
syntaxiquement, ce exploitant est tenu d'exister quelque part

175
00:09:35,000 --> 00:09:38,000
à l'intérieur de la mise en œuvre de sorte que scanf scanf

176
00:09:38,000 --> 00:09:42,000
peut écrire un nombre à 2 à cette adresse?

177
00:09:42,000 --> 00:09:44,000
Ouais, et alors le fichier *.

178
00:09:44,000 --> 00:09:47,000
Rappelons que le * est notre opérateur de déréférencement, ce qui signifie essentiellement y aller.

179
00:09:47,000 --> 00:09:50,000
>> Une fois que vous avez été remis une adresse, comme c'est le cas ici,

180
00:09:50,000 --> 00:09:53,000
scanf est sans doute, si nous effectivement regardé autour de son code source,

181
00:09:53,000 --> 00:09:59,000
fait * x ou l'équivalent d'aller effectivement à cette adresse et mettre un peu de valeur là-bas.

182
00:09:59,000 --> 00:10:02,000
Maintenant, quant à la façon dont scanf prend son entrée à partir du clavier,

183
00:10:02,000 --> 00:10:04,000
Nous allons saluer nos mains pour aujourd'hui.

184
00:10:04,000 --> 00:10:07,000
Simplement supposer que le système d'exploitation permet de parler sscanf

185
00:10:07,000 --> 00:10:11,000
au clavier de l'utilisateur, mais à ce point maintenant à la ligne 19,

186
00:10:11,000 --> 00:10:14,000
quand nous suffit d'imprimer x, il semble être le cas

187
00:10:14,000 --> 00:10:17,000
que scanf a mis en int x.

188
00:10:17,000 --> 00:10:19,000
C'est exactement la façon dont fonctionne scanf, et de rappeler la semaine dernière

189
00:10:19,000 --> 00:10:25,000
c'est exactement ce que GetString et getInt et son autre famille de fonctions

190
00:10:25,000 --> 00:10:28,000
fonctionne en fin de compte, mais avec de légères différences comme sscanf,

191
00:10:28,000 --> 00:10:31,000
ce qui signifie analyser une chaîne au lieu du clavier.

192
00:10:31,000 --> 00:10:33,000
Mais nous allons jeter un oeil à un peu de variance de cela.

193
00:10:33,000 --> 00:10:37,000
En scanf2, j'ai vraiment merdé.

194
00:10:37,000 --> 00:10:42,000
Quel est le problème et je vais cacher le commentaire qui explique que très

195
00:10:42,000 --> 00:10:47,000
ce qui ne va pas avec ce programme, la version 2?

196
00:10:47,000 --> 00:10:55,000
Soyez aussi technique que possible cette fois.

197
00:10:55,000 --> 00:10:57,000
Il semble assez bon.

198
00:10:57,000 --> 00:11:03,000
C'est très joliment indenté, mais-

199
00:11:03,000 --> 00:11:07,000
ok, que diriez-vous il faut bien tailler jusqu'à plus courtes questions?

200
00:11:07,000 --> 00:11:17,000
Ligne 16. Quelle est la ligne 16 fait en anglais, mais précise technique?

201
00:11:17,000 --> 00:11:20,000
Obtenir un peu maladroit. Oui, Michael.

202
00:11:20,000 --> 00:11:25,000
[Étudiants] Il pointe vers la première lettre d'une chaîne.

203
00:11:25,000 --> 00:11:27,000
>> Bon, à proximité. Permettez-moi de peaufiner un petit peu.

204
00:11:27,000 --> 00:11:33,000
Attirant l'attention sur la première lettre d'une chaîne, vous déclarez une variable appelée tampon

205
00:11:33,000 --> 00:11:36,000
qui pointe vers la première adresse d'une chaîne,

206
00:11:36,000 --> 00:11:39,000
ou plutôt, qui pointera plus particulièrement à un char.

207
00:11:39,000 --> 00:11:42,000
Remarquez que ce n'est pas réellement pointant nulle part parce qu'il n'y a pas d'opérateur d'affectation.

208
00:11:42,000 --> 00:11:46,000
Il n'ya pas de signe égal, tout ce que nous faisons est l'allocation du tampon variable appelée.

209
00:11:46,000 --> 00:11:49,000
Il se trouve que 32 bits parce que c'est un pointeur,

210
00:11:49,000 --> 00:11:52,000
et le contenu du tampon sans doute finalement

211
00:11:52,000 --> 00:11:57,000
contiendra l'adresse d'un char, mais pour l'instant, ce qui ne contiennent tampon?

212
00:11:57,000 --> 00:11:59,000
Juste un peu faux, qui sait, une valeur ordures,

213
00:11:59,000 --> 00:12:03,000
parce que nous n'avons pas explicitement initialisée, donc nous ne devrions pas présumer de rien.

214
00:12:03,000 --> 00:12:06,000
Bon, alors maintenant la ligne 17 est-ce que la ligne 17 ne faire?

215
00:12:06,000 --> 00:12:08,000
Peut-être que vous réchauffera jusqu'à présent.

216
00:12:08,000 --> 00:12:10,000
Il imprime une chaîne, pas vrai?

217
00:12:10,000 --> 00:12:12,000
Elle imprime à cordes s'il vous plaît.

218
00:12:12,000 --> 00:12:15,000
>> La ligne 18 est une sorte de familier maintenant que nous venons de voir une variance de cette

219
00:12:15,000 --> 00:12:18,000
mais avec un code de format différent, à la ligne 18,

220
00:12:18,000 --> 00:12:23,000
nous disons ici scanf est l'adresse d'un bloc de mémoire.

221
00:12:23,000 --> 00:12:27,000
Je veux que tu sonner dans une chaîne, comme le laisse entendre par% s,

222
00:12:27,000 --> 00:12:32,000
mais le problème est que nous n'avons pas fait un certain nombre de choses ici.

223
00:12:32,000 --> 00:12:35,000
Quel est l'un des problèmes?

224
00:12:35,000 --> 00:12:38,000
[Étudiants] Il essaie de déréférencer un pointeur NULL.

225
00:12:38,000 --> 00:12:41,000
Bon, pointeurs nuls ou tout simplement ailleurs inconnu.

226
00:12:41,000 --> 00:12:45,000
Vous n'êtes remise scanf une adresse, mais vous venez de dire il ya un instant

227
00:12:45,000 --> 00:12:49,000
que cette adresse est une valeur ordures parce que nous n'avons pas réellement l'attribuer à quelque chose,

228
00:12:49,000 --> 00:12:53,000
et si vous dites scanf effectivement aller mettre une chaîne ici,

229
00:12:53,000 --> 00:12:56,000
mais nous ne savons pas où est ici encore,

230
00:12:56,000 --> 00:12:59,000
donc nous n'avons pas réellement la mémoire allouée pour le tampon.

231
00:12:59,000 --> 00:13:03,000
Par ailleurs, ce que vous êtes aussi même pas dire scanf?

232
00:13:03,000 --> 00:13:06,000
Supposons que ce fut un morceau de mémoire, et ce n'était pas une valeur ordures,

233
00:13:06,000 --> 00:13:09,000
mais vous n'êtes pas encore dire quelque chose d'important scanf.

234
00:13:09,000 --> 00:13:12,000
[Étudiants] Lorsqu'il est fait, l'esperluette.

235
00:13:12,000 --> 00:13:15,000
Ampersand, dans ce cas, ce n'est pas grave.

236
00:13:15,000 --> 00:13:18,000
Parce tampon est déjà déclaré comme un pointeur

237
00:13:18,000 --> 00:13:22,000
avec la pièce * de la syntaxe, nous n'avons pas besoin d'utiliser esperluette

238
00:13:22,000 --> 00:13:25,000
parce que c'est déjà une adresse, mais je pense que je l'ai entendu ici.

239
00:13:25,000 --> 00:13:27,000
[Étudiants] Quelle est sa taille?

240
00:13:27,000 --> 00:13:29,000
Bon, nous ne disons pas scanf l'ampleur de ce tampon est,

241
00:13:29,000 --> 00:13:32,000
ce qui signifie que même si le tampon était un pointeur,

242
00:13:32,000 --> 00:13:35,000
nous disons scanf, mettre une chaîne ici,

243
00:13:35,000 --> 00:13:38,000
mais ici pourrait être de 2 octets, il pourrait être de 10 octets, ce pourrait être un méga-octet.

244
00:13:38,000 --> 00:13:41,000
Scanf n'a aucune idée, et parce que c'est un morceau de mémoire

245
00:13:41,000 --> 00:13:43,000
sans doute, ce n'est pas une chaîne pour le moment.

246
00:13:43,000 --> 00:13:48,000
C'est seulement une fois que vous écrivez chaîne de caractères et un 0 \ à ce morceau de mémoire.

247
00:13:48,000 --> 00:13:51,000
Maintenant, c'est juste une portion de mémoire.

248
00:13:51,000 --> 00:13:55,000
Scanf ne saurez pas quand arrêter d'écrire à cette adresse.

249
00:13:55,000 --> 00:13:59,000
>> Si vous vous rappelez quelques exemples dans le passé où je aléatoirement tapés sur le clavier

250
00:13:59,000 --> 00:14:03,000
en essayant de déborder un tampon, et nous avons parlé vendredi au sujet exactement cela.

251
00:14:03,000 --> 00:14:07,000
Si un adversaire injecte quelque sorte dans votre programme un mot beaucoup plus grand

252
00:14:07,000 --> 00:14:10,000
ou phrase ou alors vous vous attendiez, vous pouvez dépassement

253
00:14:10,000 --> 00:14:13,000
un morceau de mémoire, ce qui peut avoir des conséquences néfastes,

254
00:14:13,000 --> 00:14:15,000
comme la prise en charge de l'ensemble du programme lui-même.

255
00:14:15,000 --> 00:14:17,000
Nous avons besoin de résoudre ce problème en quelque sorte.

256
00:14:17,000 --> 00:14:20,000
Permettez-moi de faire un zoom arrière et aller dans la version 3 de ce programme.

257
00:14:20,000 --> 00:14:22,000
C'est un peu mieux.

258
00:14:22,000 --> 00:14:24,000
Dans cette version, notez la différence.

259
00:14:24,000 --> 00:14:27,000
A la ligne 16, je suis à nouveau déclarer une variable appelée tampon,

260
00:14:27,000 --> 00:14:29,000
mais qu'est-ce maintenant?

261
00:14:29,000 --> 00:14:33,000
C'est un tableau de 16 caractères.

262
00:14:33,000 --> 00:14:36,000
C'est une bonne chose parce que cela signifie que je peux maintenant dire scanf

263
00:14:36,000 --> 00:14:39,000
voici un morceau de mémoire réelle.

264
00:14:39,000 --> 00:14:42,000
Vous pouvez presque penser à des tableaux comme étant des pointeurs maintenant,

265
00:14:42,000 --> 00:14:44,000
même si elles ne sont pas réellement équivalente.

266
00:14:44,000 --> 00:14:47,000
Ils vont se comporter différemment dans des contextes différents.

267
00:14:47,000 --> 00:14:50,000
Mais c'est certainement le cas que le tampon est le référencement

268
00:14:50,000 --> 00:14:53,000
16 caractères contigus parce que c'est ce tableau est un

269
00:14:53,000 --> 00:14:55,000
et depuis quelques semaines maintenant.

270
00:14:55,000 --> 00:14:59,000
>> Ici, je dis scanf voici un morceau de mémoire.

271
00:14:59,000 --> 00:15:01,000
Cette fois-ci, c'est en fait un morceau de mémoire,

272
00:15:01,000 --> 00:15:07,000
mais pourquoi est ce programme encore exploitable?

273
00:15:07,000 --> 00:15:11,000
Qu'est-ce qui ne va pas encore?

274
00:15:11,000 --> 00:15:14,000
Je l'ai dit de me donner 16 octets, mais-

275
00:15:14,000 --> 00:15:16,000
[Étudiants] Que faire si ils tapent dans plus de 16?

276
00:15:16,000 --> 00:15:20,000
Justement, si l'utilisateur tape 17 caractères ou 1700 caractères?

277
00:15:20,000 --> 00:15:23,000
En fait, nous allons voir si nous ne pouvons pas trébucher sur cette erreur maintenant.

278
00:15:23,000 --> 00:15:25,000
C'est mieux mais pas parfait.

279
00:15:25,000 --> 00:15:28,000
Permettez-moi aller de l'avant et exécutez make scanf3 pour compiler ce programme.

280
00:15:28,000 --> 00:15:34,000
Permettez-moi de lancer scanf3, String s'il vous plaît: bonjour, et il semble bien se passer.

281
00:15:34,000 --> 00:15:37,000
Je vais essayer un peu plus long, bonjour.

282
00:15:37,000 --> 00:15:42,000
Bon, on ne bonjour là-bas comment allez-vous aujourd'hui, Entrée.

283
00:15:42,000 --> 00:15:54,000
Mise en sorte de chance ici, nous allons dire bonjour comment allez-vous y.

284
00:15:54,000 --> 00:15:56,000
Merde.

285
00:15:56,000 --> 00:16:03,000
Ok, donc nous avons été chanceux. Voyons voir si nous ne pouvons pas résoudre ce problème.

286
00:16:03,000 --> 00:16:06,000
Non, ça ne va pas me laisser copier.

287
00:16:06,000 --> 00:16:09,000
Essayons encore une fois.

288
00:16:09,000 --> 00:16:12,000
Tout droit, stand by.

289
00:16:12,000 --> 00:16:20,000
Nous allons voir combien de temps je peux faire semblant de se concentrer tout en faisant cela.

290
00:16:20,000 --> 00:16:23,000
Merde. C'est plutôt le cas, effectivement.

291
00:16:23,000 --> 00:16:26,000
Nous y voilà.

292
00:16:26,000 --> 00:16:30,000
Point de fait.

293
00:16:30,000 --> 00:16:34,000
>> Ceci, gênant mais il est aussi, il est également l'une des sources de grande confusion

294
00:16:34,000 --> 00:16:38,000
lors de l'écriture des programmes qui ont des bugs parce qu'ils se manifestent

295
00:16:38,000 --> 00:16:40,000
seulement de temps en temps, parfois.

296
00:16:40,000 --> 00:16:43,000
La réalité est que même si votre code est complètement rompu,

297
00:16:43,000 --> 00:16:46,000
elle ne peut être complètement rompu de temps en temps

298
00:16:46,000 --> 00:16:49,000
parce que parfois, essentiellement ce qui se passe est le système d'exploitation alloue

299
00:16:49,000 --> 00:16:52,000
un peu plus de mémoire que vous avez réellement besoin pour une raison quelconque,

300
00:16:52,000 --> 00:16:57,000
et que personne d'autre utilise la mémoire juste après votre morceau de 16 caractères,

301
00:16:57,000 --> 00:17:01,000
donc si vous allez à 17, 18, 19, peu importe, ce n'est pas une grosse affaire.

302
00:17:01,000 --> 00:17:04,000
Maintenant, l'ordinateur, même si elle ne tombe pas en panne à ce moment-là,

303
00:17:04,000 --> 00:17:09,000
pourrait éventuellement utiliser le numéro d'octet 17 ou 18 ou 19 pour autre chose,

304
00:17:09,000 --> 00:17:14,000
au cours de laquelle pointer vos données que vous mettez là-bas, mais excessivement longue,

305
00:17:14,000 --> 00:17:18,000
va se faire écraser éventuellement par une autre fonction.

306
00:17:18,000 --> 00:17:21,000
Il ne va pas nécessairement de rester intact,

307
00:17:21,000 --> 00:17:23,000
mais il ne sera pas nécessairement la cause d'un défaut seg.

308
00:17:23,000 --> 00:17:26,000
Mais dans ce cas, je me suis finalement fourni suffisamment de caractères

309
00:17:26,000 --> 00:17:29,000
essentiellement que je dépassé mon segment de mémoire, et bam,

310
00:17:29,000 --> 00:17:33,000
le système d'exploitation a dit: «Désolé, ce n'est pas une erreur de segmentation bon."

311
00:17:33,000 --> 00:17:38,000
>> Et nous allons voir maintenant si ce qui reste ici dans mon répertoire-

312
00:17:38,000 --> 00:17:40,000
remarquerez que j'ai ce fichier ici, le noyau.

313
00:17:40,000 --> 00:17:42,000
Notez que ceci est encore appelé un core dump.

314
00:17:42,000 --> 00:17:46,000
Il s'agit essentiellement d'un fichier qui contient le contenu de la mémoire de votre programme

315
00:17:46,000 --> 00:17:48,000
à l'endroit où il s'est écrasé,

316
00:17:48,000 --> 00:17:51,000
et juste pour essayer un petit exemple ici me laisser aller ici

317
00:17:51,000 --> 00:17:57,000
et exécuter gdb sur scanf3 puis spécifiez un troisième argument appelé core,

318
00:17:57,000 --> 00:18:01,000
et noter ici que si je liste le code,

319
00:18:01,000 --> 00:18:06,000
nous serons en mesure, comme d'habitude avec gdb pour commencer à marcher à travers ce programme,

320
00:18:06,000 --> 00:18:10,000
et je peux le faire fonctionner et dès que j'ai touché, comme avec la commande étape dans gdb-

321
00:18:10,000 --> 00:18:13,000
dès que j'ai touché la ligne potentiellement buggé après avoir tapé dans une chaîne énorme,

322
00:18:13,000 --> 00:18:16,000
Je vais être en mesure de réellement identifier ici.

323
00:18:16,000 --> 00:18:19,000
Plus à ce sujet, même si, dans la section en termes de core dump

324
00:18:19,000 --> 00:18:22,000
et ainsi de suite de sorte que vous pouvez réellement fouiller à l'intérieur de la core dump

325
00:18:22,000 --> 00:18:27,000
et de voir sur quelle ligne du programme que vous n'avez pas.

326
00:18:27,000 --> 00:18:32,000
Toutes les questions, puis sur des pointeurs et des adresses?

327
00:18:32,000 --> 00:18:36,000
Parce que, aujourd'hui, nous allons commencer en prenant pour acquis que ces choses existent

328
00:18:36,000 --> 00:18:40,000
et nous savons exactement ce qu'ils sont.

329
00:18:40,000 --> 00:18:42,000
Oui.

330
00:18:42,000 --> 00:18:46,000
>> [Étudiants] Comment se fait que vous n'avez pas à mettre une esperluette à côté de la partie-

331
00:18:46,000 --> 00:18:48,000
Bonne question.

332
00:18:48,000 --> 00:18:51,000
Comment se fait je n'ai pas besoin de mettre une esperluette à côté du tableau de caractères comme je le faisais auparavant

333
00:18:51,000 --> 00:18:53,000
avec la plupart de nos exemples?

334
00:18:53,000 --> 00:18:55,000
La réponse courte est des tableaux sont un peu spéciale.

335
00:18:55,000 --> 00:18:59,000
Vous pouvez presque penser un tampon comme étant réellement une adresse,

336
00:18:59,000 --> 00:19:03,000
et il se trouve être le cas que la notation crochet

337
00:19:03,000 --> 00:19:06,000
est une commodité afin que nous puissions aller dans le support 0, tranche 1,

338
00:19:06,000 --> 00:19:10,000
tranche 2, sans avoir à utiliser la notation *.

339
00:19:10,000 --> 00:19:13,000
C'est un peu un mensonge car les tableaux et les pointeurs

340
00:19:13,000 --> 00:19:17,000
sont, en fait, un peu différent, mais ils peuvent souvent, mais pas toujours être utilisés de façon interchangeable.

341
00:19:17,000 --> 00:19:21,000
En bref, quand une fonction attend un pointeur vers un bloc de mémoire,

342
00:19:21,000 --> 00:19:24,000
vous pouvez passer soit une adresse qui a été renvoyée par malloc,

343
00:19:24,000 --> 00:19:29,000
et nous verrons malloc nouveau avant longtemps, ou vous pouvez lui passer le nom d'un tableau.

344
00:19:29,000 --> 00:19:32,000
Vous n'avez pas à le faire et commercial avec des tableaux parce qu'ils sont déjà

345
00:19:32,000 --> 00:19:34,000
essentiellement comme des adresses.

346
00:19:34,000 --> 00:19:36,000
C'est la seule exception.

347
00:19:36,000 --> 00:19:39,000
Les crochets rendre spécial.

348
00:19:39,000 --> 00:19:41,000
>> Pouvez-vous mettre une esperluette à côté du tampon?

349
00:19:41,000 --> 00:19:43,000
Pas dans ce cas.

350
00:19:43,000 --> 00:19:46,000
Cela ne marcherait pas parce que, encore une fois, de cette affaire coin

351
00:19:46,000 --> 00:19:49,000
où les tableaux ne sont pas tout à fait en réalité adresses.

352
00:19:49,000 --> 00:19:54,000
Mais nous allons peut-être revenir à ce que d'ici peu d'autres exemples.

353
00:19:54,000 --> 00:19:56,000
Essayons de résoudre un problème ici.

354
00:19:56,000 --> 00:20:00,000
Nous avons une structure de données que nous avons utilisé pendant un certain temps connu sous le nom d'un tableau.

355
00:20:00,000 --> 00:20:02,000
Affaire au point, c'est ce que nous venons d'avoir.

356
00:20:02,000 --> 00:20:04,000
Mais les tableaux ont une certaine aspects positifs et négatifs.

357
00:20:04,000 --> 00:20:06,000
Les tableaux sont beaux pourquoi?

358
00:20:06,000 --> 00:20:11,000
Qu'est-ce une chose que vous aimez, dans la mesure où vous aimez les tableaux-sur les tableaux?

359
00:20:11,000 --> 00:20:13,000
Ce qui est pratique à leur sujet? Quel est-il intéressant?

360
00:20:13,000 --> 00:20:18,000
Pourquoi avons-nous les présenter en premier lieu?

361
00:20:18,000 --> 00:20:20,000
Ouais.

362
00:20:20,000 --> 00:20:27,000
[Étudiants] Ils peuvent stocker beaucoup de données, et vous n'avez pas à utiliser un ensemble de chose.

363
00:20:27,000 --> 00:20:29,000
Vous pouvez utiliser une section.

364
00:20:29,000 --> 00:20:32,000
Bon, avec un tableau, vous pouvez stocker beaucoup de données,

365
00:20:32,000 --> 00:20:35,000
et vous n'avez pas forcément besoin d'utiliser tout cela, afin que vous puissiez overallocate,

366
00:20:35,000 --> 00:20:39,000
ce qui peut être pratique si vous ne savez pas à l'avance combien de quelque chose à attendre.

367
00:20:39,000 --> 00:20:41,000
>> GetString est un parfait exemple.

368
00:20:41,000 --> 00:20:44,000
GetString, écrit par nous, n'a aucune idée de combien de caractères à attendre,

369
00:20:44,000 --> 00:20:48,000
donc le fait que nous pouvons allouer des blocs de mémoire contigus est bon.

370
00:20:48,000 --> 00:20:51,000
Les tableaux aussi résoudre un problème que nous avons vu il ya quelques semaines maintenant

371
00:20:51,000 --> 00:20:54,000
où votre code commence à se transformer en quelque chose de très mal conçu.

372
00:20:54,000 --> 00:20:57,000
Rappelez-vous que j'ai créé une structure étudiant du nom de David,

373
00:20:57,000 --> 00:21:00,000
puis qui était en fait une alternative, cependant,

374
00:21:00,000 --> 00:21:04,000
d'avoir un nom de variable et une autre variable appelée s'appelait, je crois, maison,

375
00:21:04,000 --> 00:21:08,000
et une autre variable appelée ID parce que dans cette histoire que j'ai ensuite voulu introduire quelque chose d'autre

376
00:21:08,000 --> 00:21:11,000
comme Rob dans le programme, alors j'ai décidé d'attendre une minute,

377
00:21:11,000 --> 00:21:13,000
J'ai besoin de renommer ces variables.

378
00:21:13,000 --> 00:21:16,000
Appelons le mien nom1, ID1, house1.

379
00:21:16,000 --> 00:21:20,000
Appelons Rob nom2, casa2, ID2.

380
00:21:20,000 --> 00:21:22,000
Mais attendez une minute, ce à propos de Tommy?

381
00:21:22,000 --> 00:21:24,000
Ensuite, nous avons eu trois autres variables.

382
00:21:24,000 --> 00:21:27,000
Nous avons introduit quelqu'un d'autre, quatre ensembles de variables.

383
00:21:27,000 --> 00:21:30,000
Le monde a commencé à déraper très rapidement,

384
00:21:30,000 --> 00:21:33,000
donc nous avons introduit les structures, et ce qui est convaincant sur une structure?

385
00:21:33,000 --> 00:21:39,000
Qu'est-ce qu'un struct C te laisser faire?

386
00:21:39,000 --> 00:21:42,000
C'est vraiment bizarre aujourd'hui.

387
00:21:42,000 --> 00:21:44,000
Quoi? >> [Réponse de l'élève inaudible]

388
00:21:44,000 --> 00:21:47,000
Oui, précisément, typedef vous permet de créer un nouveau type de données,

389
00:21:47,000 --> 00:21:51,000
et structure, le mot-clé struct, vous permet d'encapsuler

390
00:21:51,000 --> 00:21:54,000
pièces conceptuellement liés ensemble de données

391
00:21:54,000 --> 00:21:56,000
et ensuite les appeler quelque chose comme un étudiant.

392
00:21:56,000 --> 00:21:58,000
>> C'était bien parce que maintenant nous pouvons modéliser

393
00:21:58,000 --> 00:22:03,000
tri beaucoup plus de cohérence conceptuelle de la notion d'un étudiant dans une variable

394
00:22:03,000 --> 00:22:07,000
plutôt que de manière arbitraire comportant une pour une chaîne, une pour une identification, et ainsi de suite.

395
00:22:07,000 --> 00:22:10,000
Les tableaux sont bien car ils nous permettent de commencer à nettoyer notre code.

396
00:22:10,000 --> 00:22:13,000
Mais ce qui est un inconvénient désormais d'un tableau?

397
00:22:13,000 --> 00:22:15,000
Que pouvez-vous pas faire? Ouais.

398
00:22:15,000 --> 00:22:17,000
[Étudiants] Vous devez savoir comment elle est grande.

399
00:22:17,000 --> 00:22:19,000
Vous devez savoir comment elle est grande, il est donc une sorte de douleur.

400
00:22:19,000 --> 00:22:21,000
Ceux d'entre vous ayant une expérience préalable de la programmation savons que dans beaucoup de langues,

401
00:22:21,000 --> 00:22:24,000
comme Java, vous pouvez demander un morceau de mémoire, en particulier un tableau,

402
00:22:24,000 --> 00:22:28,000
quelle est la taille que vous, avec une longueur, la propriété, pour ainsi dire, et c'est vraiment pratique.

403
00:22:28,000 --> 00:22:32,000
En C, vous ne pouvez plus appeler strlen sur un tableau générique

404
00:22:32,000 --> 00:22:35,000
car strlen, comme le mot l'indique, est que pour les chaînes,

405
00:22:35,000 --> 00:22:39,000
et vous pouvez trouver la longueur d'une chaîne à cause de cette convention humaine

406
00:22:39,000 --> 00:22:43,000
d'avoir un 0 \, mais un tableau, de manière plus générique, c'est juste un morceau de mémoire.

407
00:22:43,000 --> 00:22:46,000
Si c'est un tableau d'entiers, il ne va pas être un caractère spécial

408
00:22:46,000 --> 00:22:48,000
à la fin vous attend.

409
00:22:48,000 --> 00:22:50,000
Vous devez vous rappeler de la longueur d'un tableau.

410
00:22:50,000 --> 00:22:54,000
Un autre inconvénient d'un tableau élevé sa tête en lui-même GetString.

411
00:22:54,000 --> 00:22:59,000
Ce qui est un autre inconvénient d'un tableau?

412
00:22:59,000 --> 00:23:01,000
Monsieur, que vous et moi aujourd'hui.

413
00:23:01,000 --> 00:23:04,000
[Réponse de l'élève inaudible] >> C'est quoi?

414
00:23:04,000 --> 00:23:06,000
Il a déclaré sur la pile.

415
00:23:06,000 --> 00:23:09,000
Okay, a déclaré sur la pile. Pourquoi tu n'aimes pas ça?

416
00:23:09,000 --> 00:23:13,000
[Étudiants] Parce qu'il se réutilisé.

417
00:23:13,000 --> 00:23:15,000
Il se réutilisé.

418
00:23:15,000 --> 00:23:18,000
Bon, si vous utilisez un tableau à allouer de la mémoire,

419
00:23:18,000 --> 00:23:21,000
vous ne pouvez pas, par exemple, le retourner parce que c'est sur la pile.

420
00:23:21,000 --> 00:23:23,000
D'accord, c'est un désavantage.

421
00:23:23,000 --> 00:23:25,000
Et que diriez-vous une autre avec un tableau?

422
00:23:25,000 --> 00:23:28,000
Une fois que vous l'affecter, vous êtes un peu vissé si vous avez besoin de plus d'espace

423
00:23:28,000 --> 00:23:30,000
que cette matrice a.

424
00:23:30,000 --> 00:23:34,000
>> Ensuite, nous avons introduit, rappel, malloc, qui nous a donné la possibilité d'allouer dynamiquement de la mémoire.

425
00:23:34,000 --> 00:23:37,000
Mais que faire si nous avons essayé un monde tout à fait différent?

426
00:23:37,000 --> 00:23:40,000
Que faire si nous voulions résoudre quelques problèmes ces

427
00:23:40,000 --> 00:23:45,000
donc nous avons au lieu-ma plume s'est endormi ici-

428
00:23:45,000 --> 00:23:51,000
si on plutôt voulu essentiellement créer un monde qui n'est plus comme ça?

429
00:23:51,000 --> 00:23:56,000
Il s'agit d'un tableau, et, bien sûr, ce genre de détériore une fois nous avons atteint la fin du tableau,

430
00:23:56,000 --> 00:24:00,000
et maintenant je n'ai plus d'espace pour un autre entier ou un autre personnage.

431
00:24:00,000 --> 00:24:03,000
Que si l'on sorte de manière préventive dites bien, pourquoi ne pas se détendre

432
00:24:03,000 --> 00:24:07,000
cette condition que tous ces blocs de mémoire contigus être dos à dos,

433
00:24:07,000 --> 00:24:10,000
et pourquoi pas, quand j'ai besoin d'un int ou un char,

434
00:24:10,000 --> 00:24:12,000
donnez-moi de l'espace pour l'un d'eux?

435
00:24:12,000 --> 00:24:14,000
Et quand j'ai besoin d'une autre, donne-moi un autre espace,

436
00:24:14,000 --> 00:24:16,000
et quand j'ai besoin d'une autre, donne-moi un autre espace.

437
00:24:16,000 --> 00:24:19,000
L'avantage de ce qui est maintenant que si quelqu'un d'autre

438
00:24:19,000 --> 00:24:21,000
prend la mémoire ici, pas une grosse affaire.

439
00:24:21,000 --> 00:24:25,000
Je vais prendre ce morceau de mémoire supplémentaire ici et puis celle-ci.

440
00:24:25,000 --> 00:24:28,000
>> Maintenant, le seul hic, c'est que cela se sent presque comme je l'ai

441
00:24:28,000 --> 00:24:30,000
tout un tas de différentes variables.

442
00:24:30,000 --> 00:24:33,000
Cela ressemble à cinq variables différentes potentiellement.

443
00:24:33,000 --> 00:24:36,000
Mais que faire si nous voler une idée à partir de chaînes

444
00:24:36,000 --> 00:24:41,000
par lequel nous en quelque sorte le lien entre ces choses ensemble conceptuellement, et si je fait cela?

445
00:24:41,000 --> 00:24:44,000
C'est ma flèche très mal rédigé.

446
00:24:44,000 --> 00:24:46,000
Mais supposons que chacun de ces segments de mémoire

447
00:24:46,000 --> 00:24:52,000
souligné à l'autre, et ce mec, qui n'a pas de frère ou sœur à sa droite,

448
00:24:52,000 --> 00:24:54,000
n'a pas de flèche par exemple.

449
00:24:54,000 --> 00:24:56,000
C'est en fait ce qu'on appelle une liste chaînée.

450
00:24:56,000 --> 00:25:00,000
Il s'agit d'une nouvelle structure de données qui nous permet d'allouer un bloc de mémoire,

451
00:25:00,000 --> 00:25:03,000
puis un autre, puis un autre, puis un autre, chaque fois que nous voulons

452
00:25:03,000 --> 00:25:07,000
au cours d'un programme, et nous nous rappelons qu'ils sont tous en quelque sorte liée à

453
00:25:07,000 --> 00:25:11,000
par littéralement les enchaîner ensemble, et nous l'avons fait de façon imagée ici avec une flèche.

454
00:25:11,000 --> 00:25:15,000
Mais dans le code, ce qui serait le mécanisme par lequel vous pouviez vous connecter,

455
00:25:15,000 --> 00:25:20,000
presque comme Scratch, un morceau à un autre morceau?

456
00:25:20,000 --> 00:25:22,000
Nous pourrions utiliser un pointeur, pas vrai?

457
00:25:22,000 --> 00:25:25,000
Parce que vraiment la flèche qui va de la place en haut à gauche,

458
00:25:25,000 --> 00:25:31,000
ce gars-là à celui-ci, pourrait contenir à l'intérieur de ce carré

459
00:25:31,000 --> 00:25:34,000
pas seulement certains entiers, et pas seulement quelques-uns char, mais que faire si j'ai effectivement alloué

460
00:25:34,000 --> 00:25:37,000
un peu plus d'espace de sorte que maintenant,

461
00:25:37,000 --> 00:25:41,000
chacun de mes morceaux de la mémoire, même si cela va me coûter,

462
00:25:41,000 --> 00:25:45,000
regarde maintenant un peu plus rectangulaire dont l'un des blocs de mémoire

463
00:25:45,000 --> 00:25:47,000
est utilisée pour un certain nombre, comme nombre 1,

464
00:25:47,000 --> 00:25:50,000
et puis si ce gars stocke le numéro 2,

465
00:25:50,000 --> 00:25:52,000
ce bloc de mémoire autre est utilisé pour une flèche,

466
00:25:52,000 --> 00:25:54,000
ou, plus concrètement, un pointeur.

467
00:25:54,000 --> 00:25:59,000
Et si je stocker le numéro 3 par ici pendant que je l'utiliser pour pointer vers ce type,

468
00:25:59,000 --> 00:26:02,000
et maintenant ce mec, supposons que je ne veux trois morceaux tels de mémoire.

469
00:26:02,000 --> 00:26:05,000
Je vais tracer une ligne à travers elle, indiquant nulle.

470
00:26:05,000 --> 00:26:07,000
Il n'ya pas de personnage supplémentaire.

471
00:26:07,000 --> 00:26:10,000
>> En effet, c'est ainsi que nous pouvons prendre pour la mise en œuvre

472
00:26:10,000 --> 00:26:12,000
quelque chose qui s'appelle une liste chaînée.

473
00:26:12,000 --> 00:26:18,000
Une liste chaînée est une nouvelle structure de données, et c'est un tremplin vers

474
00:26:18,000 --> 00:26:21,000
structures de données beaucoup plus fantaisistes qui commencent à résoudre des problèmes

475
00:26:21,000 --> 00:26:23,000
le long des lignes de type Facebook et Google problèmes de type problèmes

476
00:26:23,000 --> 00:26:26,000
où vous avez d'énormes ensembles de données, et il ne le coupe

477
00:26:26,000 --> 00:26:29,000
pour tout ranger côte à côte et utiliser quelque chose comme recherche linéaire

478
00:26:29,000 --> 00:26:31,000
ou même quelque chose comme binaire de recherche.

479
00:26:31,000 --> 00:26:33,000
Vous en voulez encore meilleurs temps de fonctionnement.

480
00:26:33,000 --> 00:26:37,000
En fait, l'un des Saint Graal nous parlerons plus tard cette semaine ou la suivante

481
00:26:37,000 --> 00:26:41,000
est un algorithme dont le temps d'exécution est constant.

482
00:26:41,000 --> 00:26:44,000
En d'autres termes, il faut toujours la même quantité de temps, peu importe

483
00:26:44,000 --> 00:26:47,000
la taille de l'entrée est, et ce serait effectivement convaincants,

484
00:26:47,000 --> 00:26:49,000
plus encore que quelque chose logarithmique.

485
00:26:49,000 --> 00:26:51,000
Quel est ce sur l'écran ici?

486
00:26:51,000 --> 00:26:55,000
Chacun des rectangles est exactement ce que je viens a la main.

487
00:26:55,000 --> 00:26:59,000
Mais la chose tout le chemin sur la gauche est une variable spéciale.

488
00:26:59,000 --> 00:27:02,000
Ça va être un pointeur unique parce que le gotcha une

489
00:27:02,000 --> 00:27:04,000
avec une liste chaînée, car ces choses sont dites,

490
00:27:04,000 --> 00:27:09,000
c'est que vous avez à accrocher sur une extrémité de la liste chaînée.

491
00:27:09,000 --> 00:27:13,000
>> Tout comme avec une chaîne, vous devez connaître l'adresse du premier caractère.

492
00:27:13,000 --> 00:27:15,000
Beaucoup même pour les listes chaînées.

493
00:27:15,000 --> 00:27:19,000
Vous devez connaître l'adresse du premier bloc de mémoire

494
00:27:19,000 --> 00:27:25,000
parce que de là, vous pouvez atteindre tous les autres.

495
00:27:25,000 --> 00:27:27,000
Baisse.

496
00:27:27,000 --> 00:27:30,000
Quel prix payons-nous pour cette polyvalence d'avoir une dynamique

497
00:27:30,000 --> 00:27:34,000
importante structure de données que si jamais nous avons besoin de plus de mémoire, très bien,

498
00:27:34,000 --> 00:27:37,000
juste allouer un plus gros morceau et d'en tirer un pointeur de

499
00:27:37,000 --> 00:27:39,000
l'ancienne à la nouvelle queue de la liste?

500
00:27:39,000 --> 00:27:41,000
Ouais.

501
00:27:41,000 --> 00:27:43,000
[Étudiants] Il occupe un espace deux fois plus cher.

502
00:27:43,000 --> 00:27:45,000
Il occupe un espace deux fois plus, donc c'est vraiment un inconvénient, et nous avons vu ce

503
00:27:45,000 --> 00:27:48,000
compromis avant entre temps et l'espace et la flexibilité

504
00:27:48,000 --> 00:27:51,000
où maintenant, nous n'avons pas besoin de 32 bits pour chacun de ces nombres.

505
00:27:51,000 --> 00:27:57,000
Nous avons vraiment besoin de 64, 32 pour le nombre et 32 ​​pour le pointeur.

506
00:27:57,000 --> 00:27:59,000
Mais bon, j'ai 2 Go de RAM.

507
00:27:59,000 --> 00:28:02,000
En ajoutant un autre 32 bits ici et là ne semble pas que les grandes d'un accord.

508
00:28:02,000 --> 00:28:05,000
Mais pour les ensembles de données volumineux, il ajoute certainement à littéralement deux fois plus.

509
00:28:05,000 --> 00:28:09,000
Ce qui est un autre inconvénient maintenant, ou ce qui est la particularité que nous abandonnons,

510
00:28:09,000 --> 00:28:12,000
si l'on représente des listes de choses avec une liste chaînée et non un tableau?

511
00:28:12,000 --> 00:28:14,000
[Étudiants] Vous ne pouvez pas traverser vers l'arrière.

512
00:28:14,000 --> 00:28:16,000
Vous ne pouvez pas traverser vers l'arrière, de sorte que vous êtes un peu vissé si vous êtes à pied

513
00:28:16,000 --> 00:28:19,000
de gauche à droite à l'aide d'une boucle ou d'une boucle tandis que

514
00:28:19,000 --> 00:28:21,000
et puis vous vous rendez compte, "Oh, je veux revenir au début de la liste."

515
00:28:21,000 --> 00:28:26,000
Vous ne pouvez pas parce que ces pointeurs aller de gauche à droite, comme les flèches indiquent.

516
00:28:26,000 --> 00:28:29,000
>> Maintenant, vous pouvez rappeler le début de la liste avec une autre variable,

517
00:28:29,000 --> 00:28:31,000
mais c'est une complexité à garder à l'esprit.

518
00:28:31,000 --> 00:28:35,000
Un tableau, peu importe à quel point vous allez, vous pouvez toujours faire moins, moins, moins, moins

519
00:28:35,000 --> 00:28:37,000
et retournez d'où vous venez.

520
00:28:37,000 --> 00:28:40,000
Ce qui est un autre inconvénient ici? Ouais.

521
00:28:40,000 --> 00:28:43,000
[Question étudiant inaudible]

522
00:28:43,000 --> 00:28:47,000
Vous pourriez, si vous avez réellement vient de proposer une structure de données appelée une liste doublement chaînée,

523
00:28:47,000 --> 00:28:50,000
et en effet, il faut ajouter un autre pointeur vers chacun de ces rectangles

524
00:28:50,000 --> 00:28:53,000
qui va l'autre direction, la tête de laquelle

525
00:28:53,000 --> 00:28:55,000
est maintenant que vous pouvez parcourir dans les deux sens,

526
00:28:55,000 --> 00:28:59,000
l'inconvénient de ce qui est maintenant vous utilisez trois fois plus de mémoire que nous avons utilisé pour

527
00:28:59,000 --> 00:29:04,000
et aussi ajouter de complexité en termes de code que vous devez écrire pour y arriver.

528
00:29:04,000 --> 00:29:08,000
Mais ce sont peut-être tout compromis très raisonnables, si la reprise est plus important.

529
00:29:08,000 --> 00:29:10,000
Ouais.

530
00:29:10,000 --> 00:29:12,000
[Étudiants] Vous pouvez également avoir une liste 2D lié.

531
00:29:12,000 --> 00:29:16,000
Bon, vous ne pouvez pas vraiment avoir une liste liée 2D.

532
00:29:16,000 --> 00:29:18,000
Vous pourriez. Ce n'est pas aussi facile que d'un tableau.

533
00:29:18,000 --> 00:29:21,000
Comme un tableau, vous ouvre la parenthèse, le support fermé, le support ouvert, fermé support,

534
00:29:21,000 --> 00:29:23,000
et vous aurez une structure 2-dimensionnelle.

535
00:29:23,000 --> 00:29:26,000
Vous pouvez implémenter une liste 2-dimensionnelle liée

536
00:29:26,000 --> 00:29:29,000
si vous faites module que vous proposé-un pointeur troisième chacune de ces choses,

537
00:29:29,000 --> 00:29:34,000
et si vous pensez à une autre liste venant à vous de style 3D

538
00:29:34,000 --> 00:29:40,000
à partir de l'écran pour nous tous, qui est juste une autre chaîne en quelque sorte.

539
00:29:40,000 --> 00:29:45,000
On pourrait le faire, mais ce n'est pas aussi simple que de taper crochet ouvrant, crochet. Ouais.

540
00:29:45,000 --> 00:29:48,000
[Question étudiant inaudible]

541
00:29:48,000 --> 00:29:50,000
Bon, c'est donc un kicker réel.

542
00:29:50,000 --> 00:29:54,000
>> Ces algorithmes que nous avons langui plus, comme oh, recherche binaire,

543
00:29:54,000 --> 00:29:57,000
vous pouvez rechercher un tableau de nombres sur la carte

544
00:29:57,000 --> 00:30:01,000
ou un annuaire téléphonique beaucoup plus rapidement si vous utilisez diviser pour mieux régner

545
00:30:01,000 --> 00:30:05,000
et un algorithme de recherche binaire, binaire de recherche, mais nécessitait deux hypothèses.

546
00:30:05,000 --> 00:30:09,000
Un, que les données ont été classées.

547
00:30:09,000 --> 00:30:11,000
Maintenant, nous pouvons sans doute garder cette triées,

548
00:30:11,000 --> 00:30:14,000
alors peut-être que ce n'est pas un problème, mais également supposé recherche binaire

549
00:30:14,000 --> 00:30:18,000
que vous avez eu accès aléatoire à la liste des numéros,

550
00:30:18,000 --> 00:30:21,000
et un tableau vous permet d'avoir accès aléatoire, et par l'accès aléatoire,

551
00:30:21,000 --> 00:30:24,000
Je veux dire si on vous donne un tableau, combien de temps vous faut-il

552
00:30:24,000 --> 00:30:26,000
pour se rendre à tranche 0?

553
00:30:26,000 --> 00:30:29,000
Une opération, il suffit d'utiliser [0] et que vous êtes là.

554
00:30:29,000 --> 00:30:33,000
Combien d'étapes faut-il pour se rendre à l'emplacement 10?

555
00:30:33,000 --> 00:30:36,000
Une étape, vous allez simplement dans [10] et vous y êtes.

556
00:30:36,000 --> 00:30:40,000
En revanche, comment obtenez-vous à l'entier le 10ème d'une liste chaînée?

557
00:30:40,000 --> 00:30:42,000
Vous devez commencer au début parce que vous souvenant seulement

558
00:30:42,000 --> 00:30:45,000
le début d'une liste chaînée, tout comme une chaîne on se souvient

559
00:30:45,000 --> 00:30:48,000
par l'adresse de son premier caractère, et de constater que 10th Int

560
00:30:48,000 --> 00:30:53,000
ou que 10ème caractère dans une chaîne, vous devez rechercher le tout foutu.

561
00:30:53,000 --> 00:30:55,000
>> Encore une fois, nous ne sommes pas résoudre tous nos problèmes.

562
00:30:55,000 --> 00:31:00,000
Nous introduisons de nouvelles, mais cela dépend vraiment de ce que vous essayez de concevoir pour.

563
00:31:00,000 --> 00:31:04,000
En termes de mise en œuvre, nous pouvons emprunter une idée de cette structure étudiant.

564
00:31:04,000 --> 00:31:07,000
La syntaxe est très similaire, sauf que maintenant, l'idée est un peu plus abstrait

565
00:31:07,000 --> 00:31:09,000
que la maison et le nom et l'ID.

566
00:31:09,000 --> 00:31:13,000
Mais je vous propose que nous pourrions avoir une structure de données en C

567
00:31:13,000 --> 00:31:17,000
qui est appelé nœud, comme le dernier mot sur la diapositive indique,

568
00:31:17,000 --> 00:31:21,000
à l'intérieur d'un nœud et un nœud est juste un conteneur générique en informatique.

569
00:31:21,000 --> 00:31:25,000
Il est généralement représenté comme un cercle ou un carré ou un rectangle comme nous l'avons fait.

570
00:31:25,000 --> 00:31:27,000
Et dans cette structure de données, nous avons un int, n,

571
00:31:27,000 --> 00:31:29,000
de sorte que c'est le nombre que je veux pour stocker.

572
00:31:29,000 --> 00:31:36,000
Mais quelle est cette seconde ligne, struct noeud * suivant?

573
00:31:36,000 --> 00:31:40,000
Pourquoi est-ce exact, ou le rôle que joue cette chose,

574
00:31:40,000 --> 00:31:42,000
même si c'est un peu obscur à première vue?

575
00:31:42,000 --> 00:31:44,000
Ouais.

576
00:31:44,000 --> 00:31:46,000
[Réponse de l'élève inaudible]

577
00:31:46,000 --> 00:31:50,000
Exactement, le genre * de butin que c'est un pointeur de quelque sorte.

578
00:31:50,000 --> 00:31:53,000
Le nom de ce pointeur est arbitrairement prochaine,

579
00:31:53,000 --> 00:32:00,000
mais nous aurions pu l'appelait tout ce qu'on veut, mais qu'est-ce que ce point pointeur?

580
00:32:00,000 --> 00:32:03,000
[Étudiants] Un autre noeud. >> Exactement, il pointe vers un autre nœud tel.

581
00:32:03,000 --> 00:32:05,000
>> Maintenant, c'est une sorte de curiosité de C.

582
00:32:05,000 --> 00:32:09,000
Rappelons que C est lu par un compilateur haut en bas, de gauche à droite,

583
00:32:09,000 --> 00:32:13,000
ce qui signifie que si-c'est un peu différent de ce que nous avons fait avec l'étudiant.

584
00:32:13,000 --> 00:32:16,000
Lorsque nous avons défini un étudiant, nous avons fait n'a pas mis un mot là-bas.

585
00:32:16,000 --> 00:32:18,000
Il vient d'être dit typedef.

586
00:32:18,000 --> 00:32:20,000
Puis nous avons eu int id string name,, string maison,

587
00:32:20,000 --> 00:32:23,000
puis élève au bas de la structure.

588
00:32:23,000 --> 00:32:26,000
Cette déclaration est un peu différent parce que,

589
00:32:26,000 --> 00:32:28,000
à nouveau, le compilateur C est un peu stupide.

590
00:32:28,000 --> 00:32:30,000
Il va seulement à lire de haut en bas,

591
00:32:30,000 --> 00:32:33,000
si elle atteint la 2ème ligne ici

592
00:32:33,000 --> 00:32:37,000
où à côté est déclaré et il voit, oh, voici une variable appelée prochaine.

593
00:32:37,000 --> 00:32:39,000
Il s'agit d'un pointeur vers un noeud de structure.

594
00:32:39,000 --> 00:32:42,000
Le compilateur va réaliser ce qui est un nœud de structure?

595
00:32:42,000 --> 00:32:44,000
Je n'ai jamais entendu parler de cette chose avant,

596
00:32:44,000 --> 00:32:47,000
parce que le mot node pourraient autrement ne pas apparaître

597
00:32:47,000 --> 00:32:49,000
jusqu'à ce que le fond, il ya donc cette redondance.

598
00:32:49,000 --> 00:32:53,000
Vous avez à dire struct noeud ici, que vous pouvez ensuite raccourcir plus tard

599
00:32:53,000 --> 00:32:56,000
grâce à typedef ici-bas, mais ce n'est parce

600
00:32:56,000 --> 00:33:02,000
on référençant la structure elle-même à l'intérieur de la structure.

601
00:33:02,000 --> 00:33:05,000
C'est la chasse aux sorcières celui-là.

602
00:33:05,000 --> 00:33:07,000
>> Quelques problèmes intéressants vont se poser.

603
00:33:07,000 --> 00:33:09,000
Nous avons une liste de nombres. Comment pouvons-nous insérer dans tout cela?

604
00:33:09,000 --> 00:33:11,000
Comment pouvons-nous chercher? Comment peut-on supprimer de lui?

605
00:33:11,000 --> 00:33:13,000
Surtout maintenant que nous devons gérer l'ensemble de ces pointeurs.

606
00:33:13,000 --> 00:33:15,000
Vous pensiez que les pointeurs étaient en quelque sorte hallucinante

607
00:33:15,000 --> 00:33:17,000
quand vous avez eu l'un d'eux essaie juste de lire un int à elle.

608
00:33:17,000 --> 00:33:20,000
Maintenant, nous devons manipuler vaut une liste entière.

609
00:33:20,000 --> 00:33:22,000
Pourquoi ne pas prendre notre pause de 5 minutes ici, et ensuite nous allons apporter

610
00:33:22,000 --> 00:33:34,000
certaines personnes sur scène pour faire exactement cela.

611
00:33:34,000 --> 00:33:36,000
>> C est beaucoup plus amusant quand il est mis en scène.

612
00:33:36,000 --> 00:33:39,000
Qui aurait littéralement tiens à être le premier?

613
00:33:39,000 --> 00:33:41,000
Bon, allez vers le haut. Vous êtes le premier.

614
00:33:41,000 --> 00:33:44,000
Qui voudrait être de 9? Ok, 9.

615
00:33:44,000 --> 00:33:46,000
Que diriez-9? 17?

616
00:33:46,000 --> 00:33:51,000
Une petite clique ici. 22 et 26 de la rangée avant.

617
00:33:51,000 --> 00:33:53,000
Et puis, que diriez-vous à quelqu'un là-bas pointé.

618
00:33:53,000 --> 00:33:57,000
Vous êtes 34. Okay, 34, allez vers le haut.

619
00:33:57,000 --> 00:33:59,000
La première est là-bas. Bon, tous les quatre d'entre vous.

620
00:33:59,000 --> 00:34:01,000
Et qui sommes-nous dire pour 9?

621
00:34:01,000 --> 00:34:04,000
Qui est notre 9?

622
00:34:04,000 --> 00:34:07,000
Qui veut vraiment être de 9? Bon, allez, soit 9.

623
00:34:07,000 --> 00:34:10,000
Nous y voilà.

624
00:34:10,000 --> 00:34:13,000
34, nous allons vous rencontrer là-bas.

625
00:34:13,000 --> 00:34:17,000
La première partie est de faire vous-même ressembler à ça.

626
00:34:17,000 --> 00:34:21,000
26, 22, 17, bon.

627
00:34:21,000 --> 00:34:25,000
Si vous pouvez supporter sur le côté, parce que nous allons vous malloc dans un instant.

628
00:34:25,000 --> 00:34:29,000
>> Bien, bien.

629
00:34:29,000 --> 00:34:32,000
Bon, excellent, nous allons donc poser quelques questions ici.

630
00:34:32,000 --> 00:34:34,000
Et en fait, c'est quoi ton nom? >> Anita.

631
00:34:34,000 --> 00:34:37,000
Anita, d'accord, viens par ici.

632
00:34:37,000 --> 00:34:41,000
Anita va nous aider à résoudre sorte d'une question assez simple en premier,

633
00:34:41,000 --> 00:34:44,000
qui est comment trouvez-vous si oui ou non une valeur est dans la liste?

634
00:34:44,000 --> 00:34:48,000
Maintenant, remarquez que le premier, représenté ici par Lucas,

635
00:34:48,000 --> 00:34:52,000
est un peu différent, et donc son morceau de papier est volontairement de côté

636
00:34:52,000 --> 00:34:55,000
car ce n'est pas tout à fait aussi grand et ne prend pas autant de bits,

637
00:34:55,000 --> 00:34:58,000
même si, techniquement, il a le même format de papier juste tourné.

638
00:34:58,000 --> 00:35:01,000
Mais il est un peu différent en ce sens qu'il n'est que de 32 bits pour un pointeur,

639
00:35:01,000 --> 00:35:05,000
et tous ces gars-là sont 64 bits, dont la moitié est du nombre, la moitié de ce qui est un pointeur.

640
00:35:05,000 --> 00:35:08,000
Mais le pointeur n'est pas représenté, donc si vous pouviez un peu maladroitement

641
00:35:08,000 --> 00:35:12,000
utiliser la main gauche pour pointer vers la personne à côté de vous.

642
00:35:12,000 --> 00:35:14,000
Et vous êtes le numéro 34. Quel est ton nom?

643
00:35:14,000 --> 00:35:16,000
Ari.

644
00:35:16,000 --> 00:35:19,000
Ari, donc en fait, tenir le papier dans la main droite et la main gauche va vers le bas.

645
00:35:19,000 --> 00:35:21,000
Vous déclarez nul sur la gauche.

646
00:35:21,000 --> 00:35:24,000
>> Maintenant, notre image humaine est très cohérent.

647
00:35:24,000 --> 00:35:26,000
C'est en fait la façon dont fonctionne pointeurs.

648
00:35:26,000 --> 00:35:29,000
Et si vous pouvez froisser un peu de cette façon que je ne suis pas dans votre chemin.

649
00:35:29,000 --> 00:35:34,000
Anita ici, trouvez-moi le numéro 22,

650
00:35:34,000 --> 00:35:40,000
mais supposent une contrainte de ne pas les humains brandissant des bouts de papier,

651
00:35:40,000 --> 00:35:43,000
mais il s'agit d'une liste, et vous avez seulement Lucas pour commencer

652
00:35:43,000 --> 00:35:46,000
parce qu'il est littéralement le premier pointeur.

653
00:35:46,000 --> 00:35:51,000
Supposons que vous êtes vous-même un pointeur, et si vous aussi vous avez la possibilité de pointer vers quelque chose.

654
00:35:51,000 --> 00:35:56,000
Pourquoi ne pas commencer en pointant exactement ce que Lucas est dirigée vers?

655
00:35:56,000 --> 00:35:58,000
Bon, et permettez-moi de mettre en oeuvre cette sur ici.

656
00:35:58,000 --> 00:36:04,000
Juste pour le plaisir de la discussion, permettez-moi de tirer vers le haut d'une page blanche ici.

657
00:36:04,000 --> 00:36:06,000
Comment pouvez-vous épeler votre nom? >> Anita.

658
00:36:06,000 --> 00:36:08,000
Bon, Anita.

659
00:36:08,000 --> 00:36:18,000
Disons noeud * anita = lucas.

660
00:36:18,000 --> 00:36:22,000
Eh bien, il ne faut pas vous appeler lucas. On devrait appeler en premier.

661
00:36:22,000 --> 00:36:25,000
Pourquoi est-ce, en fait, conformes à la réalité ici?

662
00:36:25,000 --> 00:36:27,000
Un, premier existe déjà.

663
00:36:27,000 --> 00:36:30,000
Première a été attribué sans doute quelque part ici.

664
00:36:30,000 --> 00:36:35,000
* Noeud d'abord, et il a été alloué une liste quelque part.

665
00:36:35,000 --> 00:36:37,000
Je ne sais pas comment c'est arrivé. Cela se passait avant la classe a commencé.

666
00:36:37,000 --> 00:36:40,000
Cette liste chaînée de l'homme a été créé.

667
00:36:40,000 --> 00:36:44,000
Et maintenant, à ce moment de l'histoire, tout cela va apparemment plus tard sur Facebook-

668
00:36:44,000 --> 00:36:49,000
à ce stade de l'histoire, Anita a été initialisé pour être égale à la première,

669
00:36:49,000 --> 00:36:51,000
ce qui ne veut pas dire que les points de Anita à Lucas.

670
00:36:51,000 --> 00:36:53,000
Au contraire, elle montre ce qu'il fait à

671
00:36:53,000 --> 00:36:57,000
parce que la même adresse que c'est à l'intérieur de Lucas 32 bits - 1, 2, 3 -

672
00:36:57,000 --> 00:37:01,000
est maintenant aussi à l'intérieur de Anita 32 bits - 1, 2, 3.

673
00:37:01,000 --> 00:37:05,000
>> Maintenant, trouver 22. Comment feriez-vous pour cela?

674
00:37:05,000 --> 00:37:07,000
Qu'est-ce que Point? >> Pour que ce soit.

675
00:37:07,000 --> 00:37:11,000
Pointez sur que ce soit, alors allez-y et agir du mieux que vous le pouvez ici.

676
00:37:11,000 --> 00:37:15,000
Bon, bon, et maintenant vous pointez-quel est ton nom avec 22?

677
00:37:15,000 --> 00:37:18,000
Ramon. >> Ramon, si Ramon est maintenant de 22.

678
00:37:18,000 --> 00:37:20,000
Vous avez maintenant fait un chèque.

679
00:37:20,000 --> 00:37:24,000
Est-ce que Ramon == 22, et si c'est le cas, par exemple, on peut retourner true.

680
00:37:24,000 --> 00:37:26,000
Laissez-moi-tout ces gars-là rester ici un peu maladroitement-

681
00:37:26,000 --> 00:37:32,000
laissez-moi faire quelque chose rapidement comme bool trouver.

682
00:37:32,000 --> 00:37:37,000
Je vais aller de l'avant et de dire (nœud de la liste *, int n).

683
00:37:37,000 --> 00:37:39,000
Je reviens tout de suite avec vous les gars. Je viens d'écrire un peu de code.

684
00:37:39,000 --> 00:37:45,000
Et maintenant, je vais aller de l'avant et de faire, noeud * = anita liste.

685
00:37:45,000 --> 00:37:51,000
Et je vais aller de l'avant et de dire tout (anita! = NULL).

686
00:37:51,000 --> 00:37:57,000
>> La métaphore ici devient un peu tendu, mais tout (anita! = NULL), qu'est-ce que je veux faire?

687
00:37:57,000 --> 00:38:03,000
J'ai besoin de faire référence aux

688
00:38:03,000 --> 00:38:05,000
l'entier Anita est pointé.

689
00:38:05,000 --> 00:38:08,000
Dans le passé, lorsque nous avons eu des structures, ce qui est un nœud,

690
00:38:08,000 --> 00:38:11,000
nous avons utilisé la notation par point, et nous dire quelque chose comme

691
00:38:11,000 --> 00:38:15,000
anita.n, mais le problème ici est que Anita n'est pas une structure en soi.

692
00:38:15,000 --> 00:38:17,000
Quelle est-elle?

693
00:38:17,000 --> 00:38:21,000
Elle est un pointeur, donc vraiment, si nous voulons utiliser cette notation pointée-

694
00:38:21,000 --> 00:38:23,000
et cela va se pencher volontairement un peu obscur-

695
00:38:23,000 --> 00:38:28,000
nous devons faire quelque chose comme aller à gauche tout ce Anita est dirigée vers

696
00:38:28,000 --> 00:38:31,000
et ensuite obtenir le champ appelé n.

697
00:38:31,000 --> 00:38:35,000
Anita est un pointeur, mais ce qui est anita *?

698
00:38:35,000 --> 00:38:38,000
Que trouvez-vous quand vous allez à ce Anita est dirigée vers?

699
00:38:38,000 --> 00:38:42,000
Une structure, un nœud et un nœud, le rappel, a un champ nommé n

700
00:38:42,000 --> 00:38:47,000
car il a, rappel, ces 2 champs, à côté et n,

701
00:38:47,000 --> 00:38:50,000
que nous avons vu il ya un instant ici.

702
00:38:50,000 --> 00:38:53,000
>> Pour imiter cette réalité dans le code,

703
00:38:53,000 --> 00:39:02,000
nous pourrions faire cela et dire if ((* anita). n == n), n que je suis à la recherche.

704
00:39:02,000 --> 00:39:04,000
Notez que la fonction a été adoptée dans le nombre je me soucie.

705
00:39:04,000 --> 00:39:10,000
Ensuite, je peux aller de l'avant et faire quelque chose comme vrai retour.

706
00:39:10,000 --> 00:39:12,000
Sinon, si ce n'est pas le cas, qu'est-ce que je veux faire?

707
00:39:12,000 --> 00:39:19,000
Comment puis-je traduire pour coder ce Anita l'a fait de manière intuitive en se promenant dans la liste?

708
00:39:19,000 --> 00:39:26,000
Que dois-je faire ici pour simuler Anita prendre cette mesure à la gauche, c'est pas à gauche?

709
00:39:26,000 --> 00:39:28,000
[Réponse de l'élève inaudible] >> Qu'est-ce que c'est?

710
00:39:28,000 --> 00:39:30,000
[Réponse de l'élève inaudible]

711
00:39:30,000 --> 00:39:34,000
Bon, pas une mauvaise idée, mais dans le passé, lorsque nous avons fait cela, nous avons fait anita + +

712
00:39:34,000 --> 00:39:37,000
parce que ce serait ajouter le numéro 1, Anita,

713
00:39:37,000 --> 00:39:40,000
qui seraient normalement pointer vers la prochaine personne, comme Ramon,

714
00:39:40,000 --> 00:39:44,000
ou la personne à côté de lui, ou de la personne à côté de lui sur toute la ligne.

715
00:39:44,000 --> 00:39:49,000
Mais ce n'est pas tout à fait bon ici, car qu'est-ce que cette chose ressemble à la mémoire?

716
00:39:49,000 --> 00:39:54,000
Non pas que. Nous devons désactivez cette option.

717
00:39:54,000 --> 00:40:00,000
Elle ressemble à ceci en mémoire, et même si j'ai dessiné 1 et 2 et 3 près de l'autre,

718
00:40:00,000 --> 00:40:03,000
si nous avons vraiment simuler ce-pouvez-vous les gars, tout en montrant les mêmes personnes,

719
00:40:03,000 --> 00:40:07,000
certains d'entre vous peut prendre un peu de recul aléatoire, certains d'entre vous une étape aléatoire de l'avant?

720
00:40:07,000 --> 00:40:10,000
>> Ce désordre est encore une liste chaînée,

721
00:40:10,000 --> 00:40:13,000
mais ces gars-là pourrait être n'importe où dans la mémoire,

722
00:40:13,000 --> 00:40:15,000
de sorte anita + + ne va pas travailler pourquoi?

723
00:40:15,000 --> 00:40:19,000
Quel est l'emplacement anita + +?

724
00:40:19,000 --> 00:40:21,000
Qui sait.

725
00:40:21,000 --> 00:40:24,000
C'est une autre valeur que se trouve juste à être interposé

726
00:40:24,000 --> 00:40:28,000
parmi tous ces nœuds par hasard parce que nous ne sommes pas en utilisant un tableau.

727
00:40:28,000 --> 00:40:30,000
Nous avons affecté chacun de ces nœuds individuellement.

728
00:40:30,000 --> 00:40:32,000
Bon, si vous les gars vous pouvez nettoyer vers le haut.

729
00:40:32,000 --> 00:40:37,000
Permettez-moi de proposer qu'au lieu de anita + +, nous avons plutôt faire anita se-

730
00:40:37,000 --> 00:40:42,000
Eh bien, pourquoi ne pas aller à tout ce qui est dirigée vers Anita puis faire. prochaine?

731
00:40:42,000 --> 00:40:45,000
En d'autres termes, nous allons à Ramon, qui est maintenant le numéro 22,

732
00:40:45,000 --> 00:40:51,000
puis. prochaine comme si Anita serait copier son pointeur main gauche.

733
00:40:51,000 --> 00:40:54,000
Mais elle ne voulait pas aller plus loin que Ramon car nous avons trouvé 22.

734
00:40:54,000 --> 00:40:56,000
Mais ce serait l'idée. Maintenant, c'est un gâchis terrible dieu.

735
00:40:56,000 --> 00:40:59,000
Honnêtement, personne ne pourra jamais se rappeler cette syntaxe, et, heureusement,

736
00:40:59,000 --> 00:41:04,000
c'est en fait un peu délibéré-oh, vous n'avez pas vraiment vu ce que j'ai écrit.

737
00:41:04,000 --> 00:41:08,000
Ce serait plus convaincant si vous le pouviez. Voila!

738
00:41:08,000 --> 00:41:10,000
>> Dans les coulisses, j'ai été de résoudre le problème de cette façon.

739
00:41:10,000 --> 00:41:14,000
Anita, à franchir le pas vers la gauche,

740
00:41:14,000 --> 00:41:18,000
première fois, nous y allons à l'adresse que Anita est dirigée vers

741
00:41:18,000 --> 00:41:23,000
et où elle se trouve, non seulement n, ce qui nous viens de vérifier pour fins de comparaison,

742
00:41:23,000 --> 00:41:25,000
mais vous trouverez également à côté - dans ce cas,

743
00:41:25,000 --> 00:41:28,000
Main gauche Ramon pointant vers le nœud suivant dans la liste.

744
00:41:28,000 --> 00:41:32,000
Mais c'est le bordel de dieu terrible à laquelle j'ai fait allusion plus tôt,

745
00:41:32,000 --> 00:41:34,000
mais il s'avère C nous permet de simplifier cette.

746
00:41:34,000 --> 00:41:40,000
Au lieu d'écrire (* anita), on peut simplement écrire au lieu anita-> n,

747
00:41:40,000 --> 00:41:45,000
et c'est exactement la même chose fonctionnellement, mais il est beaucoup plus intuitive,

748
00:41:45,000 --> 00:41:48,000
et il est beaucoup plus conforme à l'image que nous avons attiré

749
00:41:48,000 --> 00:41:50,000
tout ce temps à l'aide des flèches.

750
00:41:50,000 --> 00:41:57,000
>> Enfin, qu'est-ce que nous devons faire à la fin de ce programme?

751
00:41:57,000 --> 00:42:00,000
Il ya une ligne de code restant.

752
00:42:00,000 --> 00:42:02,000
Retour quoi?

753
00:42:02,000 --> 00:42:05,000
Faux, parce que si nous recevons à travers toute la boucle while

754
00:42:05,000 --> 00:42:10,000
et Anita est, en fait, null, ce qui signifie qu'elle a fait tout le chemin jusqu'à la fin de la liste

755
00:42:10,000 --> 00:42:12,000
où elle pointait au-quel est votre nom?

756
00:42:12,000 --> 00:42:15,000
Ari main gauche. >> Ari, qui est nulle.

757
00:42:15,000 --> 00:42:18,000
Anita est maintenant nul, et je me rends compte que vous êtes debout juste ici maladroitement dans les limbes

758
00:42:18,000 --> 00:42:21,000
parce que je pars sur un monologue ici,

759
00:42:21,000 --> 00:42:23,000
mais nous vous impliquer à nouveau dans quelques instants.

760
00:42:23,000 --> 00:42:27,000
Anita est nulle à ce moment de l'histoire, de sorte que la boucle while se termine,

761
00:42:27,000 --> 00:42:30,000
et nous devons retourner faux parce que si elle a eu tout le chemin vers un pointeur nul Ari

762
00:42:30,000 --> 00:42:34,000
alors il n'y avait pas de numéro qu'elle cherchait dans la liste.

763
00:42:34,000 --> 00:42:39,000
Nous pouvons nettoyer ça aussi, mais c'est une très bonne mise en œuvre, puis

764
00:42:39,000 --> 00:42:43,000
une fonction de traversée, une fonction de recherche pour une liste chaînée.

765
00:42:43,000 --> 00:42:48,000
C'est encore la recherche linéaire, mais ce n'est pas aussi simple que + + un pointeur

766
00:42:48,000 --> 00:42:52,000
+ + ou une variable i, parce que maintenant nous ne pouvons pas deviner

767
00:42:52,000 --> 00:42:54,000
où chacun de ces noeuds sont en mémoire.

768
00:42:54,000 --> 00:42:57,000
Nous devons littéralement suivre les traces de chapelure ou, plus précisément,

769
00:42:57,000 --> 00:43:00,000
pointeurs, pour aller d'un nœud à l'autre.

770
00:43:00,000 --> 00:43:02,000
>> Maintenant, nous allons essayer un autre. Anita, tu veux revenir ici?

771
00:43:02,000 --> 00:43:06,000
Pourquoi ne pas aller de l'avant et d'attribuer une autre personne de l'auditoire?

772
00:43:06,000 --> 00:43:08,000
Malloc-quel est ton nom? >> Rebecca.

773
00:43:08,000 --> 00:43:10,000
Rebecca. Rebecca a été malloced de l'auditoire,

774
00:43:10,000 --> 00:43:13,000
et elle est désormais stocker le numéro 55.

775
00:43:13,000 --> 00:43:17,000
Et l'objectif à portée de main est maintenant à Anita pour insérer

776
00:43:17,000 --> 00:43:22,000
Rebecca dans la liste liée ici à sa place appropriée.

777
00:43:22,000 --> 00:43:24,000
Venez par ici pour un moment.

778
00:43:24,000 --> 00:43:28,000
J'ai fait quelque chose comme ça.

779
00:43:28,000 --> 00:43:32,000
Je l'ai fait * noeud. Et quel est votre nom?

780
00:43:32,000 --> 00:43:34,000
Rebecca. >> Rebecca, d'accord.

781
00:43:34,000 --> 00:43:41,000
Rebecca se malloc (sizeof (noeud)).

782
00:43:41,000 --> 00:43:44,000
Tout comme nous avons alloué des choses comme les étudiants et autres joyeusetés dans le passé,

783
00:43:44,000 --> 00:43:46,000
nous avons besoin de la taille du noeud, alors maintenant Rebecca

784
00:43:46,000 --> 00:43:49,000
est dirigée vers quoi?

785
00:43:49,000 --> 00:43:52,000
Rebecca a deux champs à l'intérieur d'elle, dont l'une est 55.

786
00:43:52,000 --> 00:43:55,000
Faisons ce que, rebecca-> = 55.

787
00:43:55,000 --> 00:44:00,000
Mais alors rebecca-> suivant doit être-comme en ce moment, sa main est une sorte de qui sait?

788
00:44:00,000 --> 00:44:03,000
C'est en montrant une certaine valeur ordures, alors pourquoi ne pas pour faire bonne mesure

789
00:44:03,000 --> 00:44:07,000
nous avons au moins le faire pour que la main gauche est maintenant à ses côtés.

790
00:44:07,000 --> 00:44:09,000
Maintenant, Anita, le prendre d'ici.

791
00:44:09,000 --> 00:44:11,000
Vous avez Rebecca ayant été attribués.

792
00:44:11,000 --> 00:44:20,000
Allez-y et trouver l'endroit où nous devrions mettre Rebecca.

793
00:44:20,000 --> 00:44:25,000
Bien, très bien.

794
00:44:25,000 --> 00:44:28,000
Bon, très bien, et maintenant nous avons besoin de vous donner un peu de sens,

795
00:44:28,000 --> 00:44:30,000
si vous avez atteint Ari.

796
00:44:30,000 --> 00:44:33,000
Sa main gauche est nulle, mais Rebecca appartient clairement à la droite,

797
00:44:33,000 --> 00:44:36,000
Alors, comment avons-nous pour modifier cette liste chaînée

798
00:44:36,000 --> 00:44:38,000
afin d'insérer Rebecca dans l'endroit approprié?

799
00:44:38,000 --> 00:44:42,000
Si vous pouviez littéralement déplacer les mains des gens autour gauche, au besoin,

800
00:44:42,000 --> 00:44:48,000
nous allons résoudre le problème de cette façon.

801
00:44:48,000 --> 00:44:52,000
Bon, très bien, et en même temps, la main gauche de Rebecca est maintenant à côté d'elle.

802
00:44:52,000 --> 00:44:54,000
>> C'était trop facile.

803
00:44:54,000 --> 00:44:57,000
Essayons-nous sommes allouer presque fini, 20.

804
00:44:57,000 --> 00:44:59,000
Bon, allez vers le haut.

805
00:44:59,000 --> 00:45:04,000
20 a été alloué, alors laissez-moi aller de l'avant et je le répète ici

806
00:45:04,000 --> 00:45:07,000
nous venons de faire saad * noeud.

807
00:45:07,000 --> 00:45:11,000
Nous avons malloc (sizeof (noeud)).

808
00:45:11,000 --> 00:45:16,000
Nous procédons alors à la même syntaxe exacte comme nous le faisions avant pour 20,

809
00:45:16,000 --> 00:45:20,000
et je ferai la prochaine = NULL, et maintenant c'est à Anita

810
00:45:20,000 --> 00:45:23,000
à vous d'ajouter dans la liste liée, si vous pouviez jouer ce rôle exactement la même.

811
00:45:23,000 --> 00:45:30,000
Execute.

812
00:45:30,000 --> 00:45:32,000
Bon, très bien.

813
00:45:32,000 --> 00:45:38,000
Maintenant, réfléchissez bien avant de commencer à bouger la main gauche autour.

814
00:45:38,000 --> 00:45:46,000
Vous, de loin, a obtenu le rôle le plus délicat aujourd'hui.

815
00:45:46,000 --> 00:45:59,000
Dont la main doit être déplacé en premier?

816
00:45:59,000 --> 00:46:02,000
Bon, attends, je viens d'entendre quelques-uns de pas.

817
00:46:02,000 --> 00:46:07,000
Si certaines personnes poliment tiens à vous aider à résoudre une situation délicate ici.

818
00:46:07,000 --> 00:46:11,000
Dont la main gauche doit être mis à jour premier peut-être? Ouais.

819
00:46:11,000 --> 00:46:13,000
[Étudiants] de Saad.

820
00:46:13,000 --> 00:46:15,000
Bon, Saad, pourquoi, si?

821
00:46:15,000 --> 00:46:17,000
[Réponse de l'élève inaudible]

822
00:46:17,000 --> 00:46:19,000
Bon, parce que si nous nous déplaçons-quel est ton nom? >> Marshall.

823
00:46:19,000 --> 00:46:22,000
Marshall, si l'on bouge sa main d'abord vers null,

824
00:46:22,000 --> 00:46:25,000
maintenant, nous avons littéralement orphelins quatre personnes dans cette liste

825
00:46:25,000 --> 00:46:29,000
parce qu'il était le seul dirigeant à Ramon et tout le monde vers la gauche,

826
00:46:29,000 --> 00:46:31,000
de sorte que la mise à jour du premier pointeur était mauvaise.

827
00:46:31,000 --> 00:46:33,000
Nous allons annuler cela.

828
00:46:33,000 --> 00:46:37,000
Bon, et maintenant aller de l'avant et de déplacer la main gauche tendue appropriée à Ramon.

829
00:46:37,000 --> 00:46:39,000
Cela se sent un peu redondant.

830
00:46:39,000 --> 00:46:41,000
Maintenant, il ya deux personnes pointant à Ramon, mais c'est très bien

831
00:46:41,000 --> 00:46:43,000
parce que maintenant de quelle autre façon peut-on mettre à jour la liste?

832
00:46:43,000 --> 00:46:48,000
Qu'est-ce d'autre part doit se déplacer?

833
00:46:48,000 --> 00:46:53,000
Excellent, maintenant nous avons perdu toute la mémoire?

834
00:46:53,000 --> 00:46:57,000
Non, tout va bien, nous allons voir si nous ne pouvons pas briser ce une fois de plus.

835
00:46:57,000 --> 00:47:00,000
>> Allouer de la dernière fois, le numéro 5.

836
00:47:00,000 --> 00:47:04,000
Tout le chemin à l'arrière, allez vers le bas.

837
00:47:04,000 --> 00:47:08,000
C'est très excitant.

838
00:47:08,000 --> 00:47:15,000
[Applaudissements]

839
00:47:15,000 --> 00:47:17,000
Quel est ton nom? >> Ron.

840
00:47:17,000 --> 00:47:19,000
Ron, d'accord, vous êtes malloced que le numéro 5.

841
00:47:19,000 --> 00:47:23,000
Nous venons d'exécuter du code qui est presque identique à ceux-ci

842
00:47:23,000 --> 00:47:26,000
avec juste un nom différent.

843
00:47:26,000 --> 00:47:28,000
Excellent.

844
00:47:28,000 --> 00:47:38,000
Maintenant, Anita, bonne chance insérer le numéro 5 dans la liste maintenant.

845
00:47:38,000 --> 00:47:43,000
Bon, et?

846
00:47:43,000 --> 00:47:47,000
Excellent, donc c'est vraiment le troisième de trois cas au total.

847
00:47:47,000 --> 00:47:49,000
Nous avons d'abord eu quelqu'un au bout du compte, Rebecca.

848
00:47:49,000 --> 00:47:51,000
Nous avons ensuite eu quelqu'un dans le milieu.

849
00:47:51,000 --> 00:47:53,000
Maintenant, nous avons quelqu'un au début, et dans cet exemple,

850
00:47:53,000 --> 00:47:56,000
nous avions maintenant de mettre à jour Lucas pour la première fois

851
00:47:56,000 --> 00:48:00,000
parce que le premier élément de la liste doit maintenant pointer vers un nouveau nœud,

852
00:48:00,000 --> 00:48:03,000
qui, à son tour, est dirigée vers le numéro de station 9.

853
00:48:03,000 --> 00:48:06,000
>> Ce fut une démonstration extrêmement maladroit, j'en suis sûr,

854
00:48:06,000 --> 00:48:08,000
si une salve d'applaudissements pour ces gars-là si vous le pouviez.

855
00:48:08,000 --> 00:48:11,000
Bien joué.

856
00:48:11,000 --> 00:48:17,000
Voilà tout. Vous pouvez garder vos morceaux de papier comme un peu de mémoire.

857
00:48:17,000 --> 00:48:22,000
Il s'avère que le faire dans le code

858
00:48:22,000 --> 00:48:26,000
n'est pas aussi simple que de passer les mains autour de

859
00:48:26,000 --> 00:48:28,000
et pointant pointeurs à des choses différentes.

860
00:48:28,000 --> 00:48:31,000
Mais se rendre compte que lorsque vient le temps de mettre en place quelque chose comme

861
00:48:31,000 --> 00:48:34,000
une liste chaînée ou une variante de celui-ci si vous vous concentrez sur la réalité

862
00:48:34,000 --> 00:48:38,000
ces principes fondamentaux, les problèmes bouchées que je dois comprendre,

863
00:48:38,000 --> 00:48:43,000
est-ce cela la main ou cette main, se rendent compte que ce qui est par ailleurs un programme assez complexe

864
00:48:43,000 --> 00:48:47,000
peut, en effet, être réduit à des blocs de construction relativement simples comme celui-ci.

865
00:48:47,000 --> 00:48:51,000
>> Prenons les choses dans un sens encore plus sophistiquée.

866
00:48:51,000 --> 00:48:53,000
Nous avons maintenant la notion de liste chaînée.

867
00:48:53,000 --> 00:48:57,000
Nous avons aussi, grâce à la suggestion retourner là-bas, une liste doublement chaînée,

868
00:48:57,000 --> 00:49:01,000
qui ressemble presque le même, mais maintenant nous avons deux pointeurs à l'intérieur de la structure

869
00:49:01,000 --> 00:49:05,000
au lieu d'un, et nous pourrions probablement appeler ces pointeurs précédent et suivant

870
00:49:05,000 --> 00:49:08,000
ou vers la gauche ou vers la droite, mais nous faisons, en effet, besoin de deux d'entre eux.

871
00:49:08,000 --> 00:49:10,000
Le code serait un peu plus compliqué.

872
00:49:10,000 --> 00:49:12,000
Anita aurait dû faire plus de travail ici sur la scène.

873
00:49:12,000 --> 00:49:15,000
Mais nous pourrions certainement mettre en œuvre ce type de structure.

874
00:49:15,000 --> 00:49:19,000
En termes de durée, cependant, quelle serait la durée de fonctionnement

875
00:49:19,000 --> 00:49:24,000
pour Anita de trouver un nombre n dans une liste, maintenant?

876
00:49:24,000 --> 00:49:27,000
Toujours grand O de n, donc ce n'est pas mieux que la recherche linéaire.

877
00:49:27,000 --> 00:49:29,000
Nous ne pouvons pas faire de recherche binaire, même si, encore une fois.

878
00:49:29,000 --> 00:49:34,000
Pourquoi était-ce le cas? Vous ne pouvez pas sauter partout.

879
00:49:34,000 --> 00:49:36,000
Même si nous avons évidemment voir tous les humains sur la scène,

880
00:49:36,000 --> 00:49:39,000
et Anita aurait pu eyeballed et dit: «Voici le milieu de la liste,"

881
00:49:39,000 --> 00:49:42,000
elle ne voulait pas savoir que si elle était le programme informatique

882
00:49:42,000 --> 00:49:47,000
parce que la seule chose qu'elle a dû s'accrocher à au début du scénario

883
00:49:47,000 --> 00:49:50,000
était Lucas, qui était le premier pointeur.

884
00:49:50,000 --> 00:49:53,000
Elle devra nécessairement suivre ces liens,

885
00:49:53,000 --> 00:49:56,000
compter son chemin jusqu'à ce qu'elle trouve à peu près au milieu,

886
00:49:56,000 --> 00:49:58,000
et même alors, elle ne va pas savoir quand elle atteint le milieu

887
00:49:58,000 --> 00:50:01,000
à moins qu'elle ne va tout le chemin jusqu'à la fin pour comprendre combien ils sont,

888
00:50:01,000 --> 00:50:05,000
puis fait marche arrière, et cela serait difficile à moins d'avoir

889
00:50:05,000 --> 00:50:07,000
une liste doublement liée de quelque sorte.

890
00:50:07,000 --> 00:50:10,000
>> La résolution de certains problèmes aujourd'hui, mais en introduisant d'autres.

891
00:50:10,000 --> 00:50:12,000
Qu'en est-il une structure de données tout à fait différent?

892
00:50:12,000 --> 00:50:15,000
C'est une photographie des plateaux de Mather House,

893
00:50:15,000 --> 00:50:19,000
et dans ce cas, nous avons une structure de données que nous avons aussi un peu déjà parlé.

894
00:50:19,000 --> 00:50:22,000
Nous avons parlé d'une pile dans le contexte de la mémoire,

895
00:50:22,000 --> 00:50:26,000
et qui est en quelque sorte délibérément nommé parce que une pile dans les termes de mémoire

896
00:50:26,000 --> 00:50:31,000
est en fait une structure de données qui a des trucs de plus en plus couches sur le dessus de celui-ci.

897
00:50:31,000 --> 00:50:35,000
Mais la chose intéressante à propos d'une pile, comme c'est le cas dans la réalité,

898
00:50:35,000 --> 00:50:38,000
c'est que c'est un type particulier de structure de données.

899
00:50:38,000 --> 00:50:42,000
C'est une structure de données de sorte que le premier élément

900
00:50:42,000 --> 00:50:46,000
est le dernier élément sur.

901
00:50:46,000 --> 00:50:50,000
Si vous êtes le premier plateau à mettre sur la pile,

902
00:50:50,000 --> 00:50:53,000
vous allez être malheureusement le dernier plateau à prendre de la pile,

903
00:50:53,000 --> 00:50:55,000
et ce n'est pas nécessairement une bonne chose.

904
00:50:55,000 --> 00:50:58,000
Inversement, vous pouvez penser dans l'autre sens,

905
00:50:58,000 --> 00:51:02,000
le dernier est le premier sorti.

906
00:51:02,000 --> 00:51:05,000
>> Maintenant, ne les scénarios viennent à l'esprit où avoir une pile

907
00:51:05,000 --> 00:51:08,000
structure de données où vous avez cette propriété

908
00:51:08,000 --> 00:51:13,000
du dernier entré, premier sorti, est en fait convaincante?

909
00:51:13,000 --> 00:51:16,000
Est-ce une bonne chose? Est-ce une mauvaise chose?

910
00:51:16,000 --> 00:51:19,000
C'est certainement une mauvaise chose si les plateaux ne sont pas tous identiques

911
00:51:19,000 --> 00:51:21,000
et ils étaient tous différents coloris spéciaux ou autres joyeusetés,

912
00:51:21,000 --> 00:51:24,000
et la couleur que vous voulez, c'est tout le chemin vers le bas.

913
00:51:24,000 --> 00:51:26,000
Bien sûr, vous ne pouvez pas obtenir cela sans grand effort.

914
00:51:26,000 --> 00:51:28,000
Vous devez commencer par le haut et de travailler votre chemin vers le bas.

915
00:51:28,000 --> 00:51:31,000
De même, si vous étiez l'un de ces garçons ventilateur

916
00:51:31,000 --> 00:51:34,000
qui attend toute la nuit essayant d'obtenir un iPhone et s'aligne

917
00:51:34,000 --> 00:51:36,000
dans un endroit comme celui-ci?

918
00:51:36,000 --> 00:51:40,000
Serait-il pas agréable si l'Apple Store

919
00:51:40,000 --> 00:51:42,000
étaient une structure de données de la pile?

920
00:51:42,000 --> 00:51:44,000
Yay? Nay?

921
00:51:44,000 --> 00:51:47,000
Il est seulement bon pour les gens qui se présentent à la dernière minute

922
00:51:47,000 --> 00:51:50,000
et puis obtenir arraché la file d'attente.

923
00:51:50,000 --> 00:51:52,000
Et en effet, le fait que j'ai été tellement enclin à dire la file d'attente

924
00:51:52,000 --> 00:51:56,000
est en fait conforme à ce que nous pourrions appeler ce type de structure de données,

925
00:51:56,000 --> 00:51:59,000
un dans la réalité où l'ordre a son importance,

926
00:51:59,000 --> 00:52:02,000
et que vous voulez le premier à être le premier à sortir

927
00:52:02,000 --> 00:52:04,000
si ce n'est que pour des raisons d'équité humaine.

928
00:52:04,000 --> 00:52:07,000
Nous appelons généralement qu'une structure de données file d'attente.

929
00:52:07,000 --> 00:52:11,000
>> Il s'avère en outre des listes chaînées, nous pouvons commencer à utiliser ces mêmes idées de base

930
00:52:11,000 --> 00:52:15,000
et commencer à créer de nouveaux types et différentes solutions aux problèmes.

931
00:52:15,000 --> 00:52:19,000
Par exemple, dans le cas d'une pile, on pourrait représenter une pile

932
00:52:19,000 --> 00:52:22,000
en utilisant une structure de données comme celui-ci, je vous propose.

933
00:52:22,000 --> 00:52:26,000
Dans ce cas, j'ai déclaré une structure, et j'ai dit à l'intérieur de cette structure

934
00:52:26,000 --> 00:52:30,000
est un tableau de nombres et une taille variable appelée,

935
00:52:30,000 --> 00:52:33,000
et je vais appeler cette chose une pile.

936
00:52:33,000 --> 00:52:35,000
Maintenant, pourquoi est-ce vraiment efficace?

937
00:52:35,000 --> 00:52:43,000
Dans le cas d'une pile, je pouvais dessiner de façon efficace à l'écran sous forme de tableau.

938
00:52:43,000 --> 00:52:47,000
Voici mon tapis. Ce sont mes numéros.

939
00:52:47,000 --> 00:52:50,000
Et nous allons les tirer comme ça, ça, ça, ça, ça.

940
00:52:50,000 --> 00:52:53,000
Et puis j'ai une autre membre de données ici,

941
00:52:53,000 --> 00:52:58,000
qui est appelé la taille, si ce n'est la taille, et c'est le nombre,

942
00:52:58,000 --> 00:53:02,000
et collectivement, l'iPad représente ici toute une structure de pile.

943
00:53:02,000 --> 00:53:07,000
Maintenant, par défaut, la taille est sans doute arrivé à être initialisée à 0,

944
00:53:07,000 --> 00:53:11,000
et ce qui est à l'intérieur de la matrice de nombres initialement

945
00:53:11,000 --> 00:53:14,000
quand j'ai allouer un tableau?

946
00:53:14,000 --> 00:53:16,000
Garbage. Qui sait? Et il n'a pas vraiment d'importance.

947
00:53:16,000 --> 00:53:20,000
Ce n'est pas grave si c'est 1, 2, 3, 4, 5, complètement aléatoire

948
00:53:20,000 --> 00:53:25,000
par la malchance stocké dans ma structure, car tant que je sais que la taille de la pile

949
00:53:25,000 --> 00:53:29,000
est 0, alors je sais programme, ne regardez pas à l'un des éléments dans le tableau.

950
00:53:29,000 --> 00:53:31,000
Ce n'est pas grave ce qui est là.

951
00:53:31,000 --> 00:53:34,000
Ne les regardez pas, comme ce serait l'implication d'une taille de 0.

952
00:53:34,000 --> 00:53:38,000
>> Mais supposons maintenant je vais de l'avant et insérer quelque chose dans la pile.

953
00:53:38,000 --> 00:53:42,000
Je veux insérer le numéro 5, alors j'ai mis le numéro 5 ici,

954
00:53:42,000 --> 00:53:45,000
et puis qu'est-ce que je mets ici?

955
00:53:45,000 --> 00:53:48,000
Maintenant, je voudrais effectivement mis en baisse de 1 pour la taille,

956
00:53:48,000 --> 00:53:50,000
et maintenant la pile est de taille 1.

957
00:53:50,000 --> 00:53:53,000
Que faire si je aller de l'avant et insérez le nombre, disons, 7 next?

958
00:53:53,000 --> 00:53:57,000
Cela devient alors mis à jour à 2, puis nous ferons 9,

959
00:53:57,000 --> 00:54:02,000
et puis ce sera mise à jour à 3.

960
00:54:02,000 --> 00:54:05,000
Mais la caractéristique intéressante de cette pile maintenant, c'est que

961
00:54:05,000 --> 00:54:09,000
Je suis censé supprimer cet élément si je veux faire un saut

962
00:54:09,000 --> 00:54:12,000
quelque chose hors de la pile, pour ainsi dire?

963
00:54:12,000 --> 00:54:14,000
9 serait la première chose à faire.

964
00:54:14,000 --> 00:54:18,000
Comment devrais changer l'image, si je veux faire apparaître un élément de la pile,

965
00:54:18,000 --> 00:54:20,000
un peu comme un bac à Mather?

966
00:54:20,000 --> 00:54:22,000
Ouais. >> [Étudiants] Régler la taille à 2.

967
00:54:22,000 --> 00:54:27,000
Exactement, tout ce que je faire est de définir la taille à 2, et que dois-je faire avec le tableau?

968
00:54:27,000 --> 00:54:29,000
Je n'ai pas à faire quoi que ce soit.

969
00:54:29,000 --> 00:54:32,000
Je pourrais, juste pour être anal, mettre un 0 ou -1 il ou quelque chose pour signifier

970
00:54:32,000 --> 00:54:34,000
que ce n'est pas une valeur légitime, mais ce n'est pas grave parce que

971
00:54:34,000 --> 00:54:37,000
Je peux enregistrer à l'extérieur de la matrice elle-même combien de temps il est

972
00:54:37,000 --> 00:54:41,000
de sorte que je sais qu'à regarder les deux premiers éléments de ce tableau.

973
00:54:41,000 --> 00:54:47,000
Maintenant, si je vais ajouter le numéro 8 du présent tableau, comment changer l'image suivante?

974
00:54:47,000 --> 00:54:50,000
Cela devient 8, et cela devient 3.

975
00:54:50,000 --> 00:54:52,000
Je coupe quelques virages ici.

976
00:54:52,000 --> 00:54:56,000
Maintenant, nous avons 5, 7, 8, et nous sommes de retour à une taille de 3.

977
00:54:56,000 --> 00:54:58,000
C'est assez simple à mettre en œuvre,

978
00:54:58,000 --> 00:55:06,000
mais quand allons-nous regrettons cette décision de conception?

979
00:55:06,000 --> 00:55:09,000
Quand est-ce les choses commencent à aller mal, très mal? Ouais.

980
00:55:09,000 --> 00:55:11,000
[Réponse de l'élève inaudible]

981
00:55:11,000 --> 00:55:13,000
Lorsque vous voulez revenir en arrière et obtenir le premier élément que vous mettez dedans

982
00:55:13,000 --> 00:55:18,000
>> Il s'avère ici, même si une pile est un tableau sous le capot,

983
00:55:18,000 --> 00:55:21,000
ces structures de données que nous avons commencé à parler sont aussi généralement connu sous le nom

984
00:55:21,000 --> 00:55:25,000
structures de données abstraites où comment ils mis en œuvre

985
00:55:25,000 --> 00:55:27,000
est complètement hors de propos.

986
00:55:27,000 --> 00:55:31,000
Une structure de données comme une pile est censé ajouter le support

987
00:55:31,000 --> 00:55:35,000
opérations comme poussoir, qui pousse un plateau dans la pile,

988
00:55:35,000 --> 00:55:39,000
et de la pop, ce qui supprime un élément de la pile, et c'est tout.

989
00:55:39,000 --> 00:55:43,000
Si vous deviez télécharger le code de quelqu'un d'autre qui a déjà mis en œuvre

990
00:55:43,000 --> 00:55:46,000
cette chose appelée une pile, cette personne aurait écrit

991
00:55:46,000 --> 00:55:49,000
seulement deux fonctions pour vous, poussez et pop, dont le seul but dans la vie

992
00:55:49,000 --> 00:55:51,000
serait de faire exactement cela.

993
00:55:51,000 --> 00:55:54,000
Vous ou lui qui a appliqué ce programme

994
00:55:54,000 --> 00:55:58,000
aurait été tout à fait le seul à décider comment mettre en œuvre

995
00:55:58,000 --> 00:56:00,000
la sémantique de pousser et sauter sous le capot

996
00:56:00,000 --> 00:56:03,000
ou la fonctionnalité de pousser et popping.

997
00:56:03,000 --> 00:56:07,000
Et j'ai pris une décision un peu myope ici

998
00:56:07,000 --> 00:56:10,000
en mettant en place ma pile avec cette structure de données simple pourquoi?

999
00:56:10,000 --> 00:56:12,000
Quand est-ce cette pause structure de données?

1000
00:56:12,000 --> 00:56:18,000
À quel moment dois-je retourner une erreur lorsque l'utilisateur appelle push, par exemple?

1001
00:56:18,000 --> 00:56:20,000
[Étudiant] S'il n'y a pas plus de place.

1002
00:56:20,000 --> 00:56:23,000
Justement, s'il ya un espace pas plus, si j'ai dépassé la capacité,

1003
00:56:23,000 --> 00:56:27,000
ce qui est tout en majuscules, car il suggère que c'est une sorte de constante globale.

1004
00:56:27,000 --> 00:56:30,000
Eh bien, alors je vais juste avoir à dire: «Désolé, je ne peux pas pousser une autre valeur

1005
00:56:30,000 --> 00:56:32,000
sur la pile », un peu comme dans Mather.

1006
00:56:32,000 --> 00:56:36,000
>> À un certain moment, ils vont frapper la partie supérieure de ce petit cabinet.

1007
00:56:36,000 --> 00:56:39,000
Il n'y a plus d'espace ou de capacité de la pile, à quel point il ya une sorte d'erreur.

1008
00:56:39,000 --> 00:56:42,000
Ils doivent mettre l'élément ailleurs, le plateau ailleurs,

1009
00:56:42,000 --> 00:56:44,000
ou nulle part.

1010
00:56:44,000 --> 00:56:47,000
Maintenant, avec une file d'attente, nous avons pu mettre en œuvre un peu différemment.

1011
00:56:47,000 --> 00:56:50,000
Une file d'attente est un peu différent en ce que sous le capot, il peut être mis en œuvre

1012
00:56:50,000 --> 00:56:54,000
comme un tableau, mais pourquoi, dans ce cas, je propose

1013
00:56:54,000 --> 00:56:59,000
d'avoir aussi un élément de tête représentant la tête de la liste,

1014
00:56:59,000 --> 00:57:06,000
le début de la liste, la première personne en ligne sur l'Apple Store, en plus de la taille?

1015
00:57:06,000 --> 00:57:14,000
Pourquoi ai-je besoin d'une pièce supplémentaire de données ici?

1016
00:57:14,000 --> 00:57:16,000
Pensez à ce que le nombre est

1017
00:57:16,000 --> 00:57:18,000
si j'ai dessiné comme suit.

1018
00:57:18,000 --> 00:57:21,000
Supposons que c'est maintenant une file d'attente au lieu d'une pile,

1019
00:57:21,000 --> 00:57:24,000
la différence étant, tout comme l'Apple Store en file d'attente est juste.

1020
00:57:24,000 --> 00:57:27,000
La première personne en ligne au début de la liste, le numéro 5 dans ce cas,

1021
00:57:27,000 --> 00:57:30,000
il ou elle va être laissé dans le premier magasin.

1022
00:57:30,000 --> 00:57:32,000
Faisons-le.

1023
00:57:32,000 --> 00:57:35,000
Supposons que c'est l'état de ma file d'attente en ce moment dans le temps, et maintenant sur l'Apple Store

1024
00:57:35,000 --> 00:57:39,000
et ouvre la première personne, le numéro 5, est introduit dans le magasin.

1025
00:57:39,000 --> 00:57:43,000
Comment puis-je changer l'image, maintenant que j'ai dé-file d'attente la première personne

1026
00:57:43,000 --> 00:57:47,000
à l'avant de la ligne?

1027
00:57:47,000 --> 00:57:50,000
Qu'est-ce que c'est? >> [Étudiants] Changer la file d'attente.

1028
00:57:50,000 --> 00:57:52,000
Changer la tête, donc 5 disparaît.

1029
00:57:52,000 --> 00:57:56,000
En réalité, c'est comme si-la meilleure façon de faire cela?

1030
00:57:56,000 --> 00:58:00,000
En réalité, c'est comme si ce gars disparaît.

1031
00:58:00,000 --> 00:58:03,000
Qu'est-ce que le numéro 7 faire dans un magasin réel?

1032
00:58:03,000 --> 00:58:05,000
Ils prendraient un grand pas en avant.

1033
00:58:05,000 --> 00:58:08,000
>> Mais qu'avons-nous appris à apprécier quand il s'agit de tableaux

1034
00:58:08,000 --> 00:58:10,000
et déplacer des choses?

1035
00:58:10,000 --> 00:58:12,000
C'est une sorte de gaspillage de votre temps, pas vrai?

1036
00:58:12,000 --> 00:58:16,000
Pourquoi avez-vous besoin d'être aussi anale pour avoir la première personne

1037
00:58:16,000 --> 00:58:21,000
au début de la ligne à physiquement le début de la portion de mémoire?

1038
00:58:21,000 --> 00:58:23,000
C'est complètement inutile. Pourquoi?

1039
00:58:23,000 --> 00:58:26,000
Que pouvais-je me souviens à la place? >> [Réponse de l'élève inaudible]

1040
00:58:26,000 --> 00:58:30,000
Exactement, je ne pouvais me souviens de cette tête de l'élément de données supplémentaire

1041
00:58:30,000 --> 00:58:34,000
que maintenant à la tête de la liste n'est plus 0, ce qui était il ya un instant.

1042
00:58:34,000 --> 00:58:39,000
Maintenant, il est en fait le numéro 1. De cette façon, j'obtiens une optimisation légère.

1043
00:58:39,000 --> 00:58:44,000
Juste parce que je suis quelqu'un de-file d'attente à partir de la ligne au début de la ligne sur l'Apple Store

1044
00:58:44,000 --> 00:58:47,000
ne signifie pas que tout le monde doit passer, ce qui rappel est une opération linéaire.

1045
00:58:47,000 --> 00:58:50,000
Je peux passer du temps au lieu seule constante

1046
00:58:50,000 --> 00:58:53,000
et de réaliser ensuite une réponse beaucoup plus rapide.

1047
00:58:53,000 --> 00:58:56,000
Mais le prix que je paie ce qu'il faut gagner cette performance supplémentaire

1048
00:58:56,000 --> 00:58:58,000
et ne pas avoir à changer le monde?

1049
00:58:58,000 --> 00:59:01,000
Ouais. >> [Réponse de l'élève inaudible]

1050
00:59:01,000 --> 00:59:04,000
Pouvez ajouter d'autres personnes, eh bien, ce problème est orthogonal

1051
00:59:04,000 --> 00:59:07,000
au fait que nous ne sommes pas déplacer les gens autour.

1052
00:59:07,000 --> 00:59:11,000
C'est toujours un tableau, donc si oui ou non nous changeons tout le monde ou pas-

1053
00:59:11,000 --> 00:59:13,000
oh, je vois ce que tu veux dire, d'accord.

1054
00:59:13,000 --> 00:59:16,000
En fait, je suis d'accord avec ce que vous dites en ce qu'elle est presque comme si

1055
00:59:16,000 --> 00:59:19,000
nous sommes maintenant ne va jamais utiliser le début de ce tableau plus

1056
00:59:19,000 --> 00:59:22,000
parce que si je retire 5, puis-je supprimer 7.

1057
00:59:22,000 --> 00:59:24,000
Mais je ne mettre les gens vers la droite.

1058
00:59:24,000 --> 00:59:28,000
>> C'est comme si je perds mon espace, et finalement ma file d'attente se désintègre en rien du tout,

1059
00:59:28,000 --> 00:59:31,000
si nous pouvions avoir enveloppant les gens,

1060
00:59:31,000 --> 00:59:35,000
et l'on pourrait penser de ce tableau vraiment comme une sorte de structure circulaire,

1061
00:59:35,000 --> 00:59:38,000
mais nous utilisons ce que l'opérateur en C pour faire ce genre de bouclage?

1062
00:59:38,000 --> 00:59:40,000
[Réponse de l'élève inaudible] >> L'opérateur modulo.

1063
00:59:40,000 --> 00:59:43,000
Il serait un peu ennuyeux de penser à la façon dont tu fais l'enveloppant,

1064
00:59:43,000 --> 00:59:46,000
mais nous pourrions le faire, et nous avons pu commencer à mettre les gens à ce qui était à l'avant de la ligne,

1065
00:59:46,000 --> 00:59:52,000
mais nous venons de rappeler à cette variable la tête qui est le chef réel de la ligne est en réalité.

1066
00:59:52,000 --> 00:59:57,000
Que faire si, au contraire, notre but en fin de compte, cependant,

1067
00:59:57,000 --> 01:00:00,000
était de chercher des numéros, comme nous l'avons fait ici sur scène avec Anita,

1068
01:00:00,000 --> 01:00:02,000
mais nous voulons vraiment le meilleur de tous les mondes?

1069
01:00:02,000 --> 01:00:05,000
Nous voulons toujours plus sophistiquée tableau permet

1070
01:00:05,000 --> 01:00:09,000
parce que nous voulons que la capacité à se développer de manière dynamique la structure de données.

1071
01:00:09,000 --> 01:00:12,000
Mais nous ne voulons pas avoir à recourir à quelque chose que nous avons fait remarquer

1072
01:00:12,000 --> 01:00:15,000
dans la première conférence n'était pas un algorithme optimal,

1073
01:00:15,000 --> 01:00:17,000
que la recherche linéaire.

1074
01:00:17,000 --> 01:00:21,000
Il s'avère que vous pouvez, en effet, d'atteindre

1075
01:00:21,000 --> 01:00:24,000
ou au moins proche de la constante de temps, lequel quelqu'un comme Anita,

1076
01:00:24,000 --> 01:00:27,000
si elle configure sa structure de données ne soit pas une liste chaînée,

1077
01:00:27,000 --> 01:00:30,000
de ne pas être une pile, ne pas être une file d'attente, pourrait, en fait,

1078
01:00:30,000 --> 01:00:33,000
proposer une structure de données qui lui permet de regarder les choses,

1079
01:00:33,000 --> 01:00:37,000
même des mots, et pas seulement des chiffres, dans ce que nous appellerons la constante de temps.

1080
01:00:37,000 --> 01:00:40,000
>> Et en fait, l'avenir, l'un des psets dans cette classe est presque toujours

1081
01:00:40,000 --> 01:00:43,000
une mise en œuvre d'un correcteur orthographique, lequel

1082
01:00:43,000 --> 01:00:46,000
nous vous donnons encore quelques mots 150.000 anglais et le but est de

1083
01:00:46,000 --> 01:00:51,000
charger dans la mémoire de ceux et rapidement être en mesure de répondre aux questions de la forme

1084
01:00:51,000 --> 01:00:54,000
ce mot est correctement orthographié?

1085
01:00:54,000 --> 01:00:58,000
Et il serait vraiment sucer si vous deviez parcourir tous les 150.000 mots pour répondre.

1086
01:00:58,000 --> 01:01:02,000
Mais, en fait, nous allons voir ce que nous pouvons le faire en un temps très, très rapide.

1087
01:01:02,000 --> 01:01:06,000
Et cela va impliquer quelque chose appelé la mise en œuvre d'une table de hachage,

1088
01:01:06,000 --> 01:01:09,000
et même si à première vue, cette chose qu'on appelle une table de hachage va

1089
01:01:09,000 --> 01:01:12,000
laissez-nous atteindre ces superbes moments d'intervention rapide,

1090
01:01:12,000 --> 01:01:18,000
il s'avère qu'il ya en fait un problème.

1091
01:01:18,000 --> 01:01:23,000
Quand vient le temps de mettre en œuvre cette chose appelée de nouveau, je le fais à nouveau.

1092
01:01:23,000 --> 01:01:25,000
Je suis le seul ici.

1093
01:01:25,000 --> 01:01:28,000
Quand vient le temps de mettre en œuvre ce qu'on appelle une table de hachage,

1094
01:01:28,000 --> 01:01:30,000
nous allons devoir prendre une décision.

1095
01:01:30,000 --> 01:01:32,000
Quelle devrait être cette chose en réalité?

1096
01:01:32,000 --> 01:01:36,000
Et quand on commence à insérer des numéros dans cette table de hachage,

1097
01:01:36,000 --> 01:01:38,000
comment allons-nous à les stocker de manière

1098
01:01:38,000 --> 01:01:42,000
que nous pouvons les récupérer aussi vite que nous les avons en?

1099
01:01:42,000 --> 01:01:45,000
Mais nous verrons bientôt que cette question de

1100
01:01:45,000 --> 01:01:48,000
lorsque anniversaire de tout le monde est dans la classe sera tout à fait pertinent.

1101
01:01:48,000 --> 01:01:51,000
Il s'avère que dans cette salle, nous avons quelques centaines de personnes,

1102
01:01:51,000 --> 01:01:56,000
alors les chances que deux d'entre nous ont le même anniversaire est probablement assez élevé.

1103
01:01:56,000 --> 01:01:58,000
Que faire si il n'y avait que 40 d'entre nous dans cette salle?

1104
01:01:58,000 --> 01:02:02,000
Quelles sont les chances de deux personnes ayant la même date d'anniversaire?

1105
01:02:02,000 --> 01:02:04,000
[Les élèves] Plus de 50%.

1106
01:02:04,000 --> 01:02:06,000
Oui, plus de 50%. En fait, j'ai même apporté un graphique.

1107
01:02:06,000 --> 01:02:08,000
Il s'avère, et c'est vraiment juste un sneak preview-

1108
01:02:08,000 --> 01:02:12,000
s'il ya seulement 58 d'entre nous dans cette salle, la probabilité de 2 d'entre nous

1109
01:02:12,000 --> 01:02:16,000
ayant la même date d'anniversaire est extrêmement élevé, de près de 100%,

1110
01:02:16,000 --> 01:02:20,000
et que va causer tout un tas de mal pour nous le mercredi.

1111
01:02:20,000 --> 01:02:24,000
>> Cela dit, nous allons ajourner ici. Nous allons vous voir mercredi.

1112
01:02:24,000 --> 01:02:28,000
[Applaudissements]

1113
01:02:28,000 --> 01:02:30,000
[CS50.TV]