1
00:00:00,000 --> 00:00:11,860

2
00:00:11,860 --> 00:00:13,120
>> INTERLOCUTEUR 1: Très bien, alors nous sommes de retour.

3
00:00:13,120 --> 00:00:14,480
Bienvenue à CS50.

4
00:00:14,480 --> 00:00:16,510
C'est la fin de la semaine sept ans.

5
00:00:16,510 --> 00:00:20,200
Donc, rappelons que la dernière fois, nous avons commencé
en regardant un peu plus sophistiqué

6
00:00:20,200 --> 00:00:21,100
des structures de données.

7
00:00:21,100 --> 00:00:25,110
Depuis, jusqu'à présent, nous n'avions vraiment
à notre disposition était présent, un tableau.

8
00:00:25,110 --> 00:00:29,340
>> Mais avant de nous écartons le tableau en tant que non
tout ce qui intéressant, ce qui fait qu'il

9
00:00:29,340 --> 00:00:33,570
est en réalité, ce sont quelques-uns des
avantages de ces données simples

10
00:00:33,570 --> 00:00:34,560
la structure jusqu'à présent?

11
00:00:34,560 --> 00:00:36,110
Quel est le bon?

12
00:00:36,110 --> 00:00:39,450
Pour autant que nous avons vu?

13
00:00:39,450 --> 00:00:42,540
Qu'est-ce que tu as?

14
00:00:42,540 --> 00:00:44,028
Rien.

15
00:00:44,028 --> 00:00:45,020
>> ETUDIANT: [inaudible].

16
00:00:45,020 --> 00:00:45,395
>> ENCEINTE 1: Qu'est-ce que c'est?

17
00:00:45,395 --> 00:00:46,410
>> ETUDIANT: [inaudible].

18
00:00:46,410 --> 00:00:47,000
>> INTERLOCUTEUR 1: taille fixe.

19
00:00:47,000 --> 00:00:51,260
OK, alors pourquoi est de taille fixe si bon?

20
00:00:51,260 --> 00:00:53,180
>> ETUDIANT: [inaudible].

21
00:00:53,180 --> 00:00:56,240
>> INTERLOCUTEUR 1: OK, donc c'est efficace
le sens que vous pouvez allouer une

22
00:00:56,240 --> 00:01:00,070
montant fixe de l'espace, qui nous l'espérons
C'est précisément autant

23
00:01:00,070 --> 00:01:01,180
l'espace que vous voulez.

24
00:01:01,180 --> 00:01:02,720
Il pourrait donc être absolument un plus.

25
00:01:02,720 --> 00:01:06,530
>> Ce qui est un autre aspect d'un tableau?

26
00:01:06,530 --> 00:01:07,610
Ouais?

27
00:01:07,610 --> 00:01:08,750
>> ETUDIANT: [inaudible].

28
00:01:08,750 --> 00:01:09,550
>> INTERLOCUTEUR 1: Tout le - désolé?

29
00:01:09,550 --> 00:01:11,270
>> ETUDIANT: [inaudible].

30
00:01:11,270 --> 00:01:13,620
>> INTERLOCUTEUR 1: toutes les cases de la mémoire
ou à côté de l'autre.

31
00:01:13,620 --> 00:01:15,220
Et c'est utile - pourquoi?

32
00:01:15,220 --> 00:01:15,970
C'est tout à fait vrai.

33
00:01:15,970 --> 00:01:18,611
Mais comment pouvons-nous exploiter cette vérité?

34
00:01:18,611 --> 00:01:21,500
>> ETUDIANT: [inaudible].

35
00:01:21,500 --> 00:01:24,490
>> INTERLOCUTEUR 1: Exactement, nous pouvons garder une trace de
où tout est juste en sachant

36
00:01:24,490 --> 00:01:28,560
une adresse, à savoir l'adresse de l'
premier octet de ce bloc de mémoire.

37
00:01:28,560 --> 00:01:30,420
Or, dans le cas de la chaîne,
l'adresse du premier

38
00:01:30,420 --> 00:01:31,460
chevalier dans cette chaîne.

39
00:01:31,460 --> 00:01:33,330
Et à partir de là, nous pouvons trouver
la fin de la chaîne.

40
00:01:33,330 --> 00:01:35,710
Nous pouvons trouver le deuxième élément, le
troisième élément, et ainsi de suite.

41
00:01:35,710 --> 00:01:38,740
>> Et si la fantaisie façon de décrire ce que
caractéristique est que les tableaux nous donnent

42
00:01:38,740 --> 00:01:40,020
accès aléatoire.

43
00:01:40,020 --> 00:01:44,330
Juste en utilisant le crochet
notation et un numéro, vous pouvez passer à

44
00:01:44,330 --> 00:01:48,070
un élément spécifique dans le tableau
en temps constant, grand O

45
00:01:48,070 --> 00:01:49,810
d'un seul, pour ainsi dire.

46
00:01:49,810 --> 00:01:51,080
>> Mais il ya eu quelques inconvénients.

47
00:01:51,080 --> 00:01:53,110
Qu'est-ce un tableau fait pas très facilement?

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
Quel est-il pas bon?

50
00:01:57,170 --> 00:01:58,810
>> ETUDIANT: [inaudible].

51
00:01:58,810 --> 00:01:59,860
>> ENCEINTE 1: Qu'est-ce que c'est?

52
00:01:59,860 --> 00:02:00,530
>> ETUDIANT: [inaudible].

53
00:02:00,530 --> 00:02:01,460
>> ENCEINTE 1: Développer la taille.

54
00:02:01,460 --> 00:02:04,800
Ainsi, les inconvénients du tableau sont
exactement le contraire de ce que l'

55
00:02:04,800 --> 00:02:05,540
upsides sont.

56
00:02:05,540 --> 00:02:07,610
Donc, l'un des inconvénients est
que c'est une taille fixe.

57
00:02:07,610 --> 00:02:09,400
Donc vous ne pouvez pas vraiment cultiver.

58
00:02:09,400 --> 00:02:13,510
Vous pouvez réaffecter une plus grande partie de
mémoire, puis déplacez les éléments anciens

59
00:02:13,510 --> 00:02:14,460
dans le nouveau tableau.

60
00:02:14,460 --> 00:02:18,060
Et puis libérer le vieux tableau, pour
Ainsi, en utilisant malloc ou un analogue

61
00:02:18,060 --> 00:02:21,180
fonction appelée realloc, qui
réaffecte mémoire.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, en passant, essaie de vous donner
mémoire qui est à côté de la matrice

63
00:02:25,490 --> 00:02:26,610
que vous avez déjà.

64
00:02:26,610 --> 00:02:28,740
Mais il pourrait faire bouger les choses
autour de tout.

65
00:02:28,740 --> 00:02:30,710
Mais en bref, c'est cher, non?

66
00:02:30,710 --> 00:02:33,440
Parce que si vous avez un morceau de la mémoire de
cette taille, mais vous voulez vraiment un

67
00:02:33,440 --> 00:02:36,710
de cette taille, et vous souhaitez conserver
les éléments d'origine, vous avez

68
00:02:36,710 --> 00:02:40,510
moins un processus de copie de temps linéaire
qui doit se produire à partir de

69
00:02:40,510 --> 00:02:41,900
ancien tableau à nouveau.

70
00:02:41,900 --> 00:02:44,630
Et la réalité est demande au fonctionnement
Système à plusieurs reprises et

71
00:02:44,630 --> 00:02:48,340
nouveau pour de gros morceaux de la mémoire peut commencer
vous coûter un certain temps ainsi.

72
00:02:48,340 --> 00:02:52,250
Donc, c'est à la fois une bénédiction et une malédiction
dissimuler le fait que ces tableaux

73
00:02:52,250 --> 00:02:53,860
sont de taille fixe.

74
00:02:53,860 --> 00:02:56,790
Mais si nous introduisons la place quelque chose
comme ce que nous avons appelé une alternance

75
00:02:56,790 --> 00:03:00,580
liste, nous obtenons quelques bons côtés et
quelques inconvénients ici aussi.

76
00:03:00,580 --> 00:03:05,780
>> Ainsi, une liste chaînée est tout simplement un ensemble de données
Structure composée de struct C dans cette

77
00:03:05,780 --> 00:03:09,850
cas où une structure, le rappel est juste
un récipient pour un ou plusieurs spécifique

78
00:03:09,850 --> 00:03:11,100
types de variables.

79
00:03:11,100 --> 00:03:16,110
Dans ce cas, qu'est-ce que les types de données
semblent être à l'intérieur de la structure qui

80
00:03:16,110 --> 00:03:17,600
dernière fois que nous avons appelé un nœud?

81
00:03:17,600 --> 00:03:19,380
Chacun de ces rectangles est un nœud.

82
00:03:19,380 --> 00:03:22,660
Et chacun des petits rectangles
à l'intérieur de celui-ci est un type de données.

83
00:03:22,660 --> 00:03:25,300
Quels types disions-nous
ils étaient lundi?

84
00:03:25,300 --> 00:03:26,478
Ouais?

85
00:03:26,478 --> 00:03:27,870
>> ETUDIANT: [inaudible].

86
00:03:27,870 --> 00:03:30,721
>> INTERLOCUTEUR 1: Une variable et un pointeur, ou
Plus précisément, un int, pour n,

87
00:03:30,721 --> 00:03:32,180
et un pointeur vers le bas.

88
00:03:32,180 --> 00:03:35,360
Les deux personnes se trouvent être 32 bits, à
moins sur un ordinateur comme ça CS50

89
00:03:35,360 --> 00:03:37,980
Appareil, et ils sont donc
provenant à parts égales de la taille.

90
00:03:37,980 --> 00:03:42,260
>> Alors, qu'est-ce que l'aide du pointeur
mais pour apparemment?

91
00:03:42,260 --> 00:03:47,690
Pourquoi ajouter cette flèche maintenant, quand les tableaux étaient
si belle et propre et simple?

92
00:03:47,690 --> 00:03:50,460
Quel est le pointeur fait pour
nous dans chacun de ces nœuds?

93
00:03:50,460 --> 00:03:52,160
>> ETUDIANT: [inaudible].

94
00:03:52,160 --> 00:03:52,465
>> ENCEINTE 1: Exactement.

95
00:03:52,465 --> 00:03:54,120
C'est vous dire où
le prochain est.

96
00:03:54,120 --> 00:03:57,350
Donc je sorte d'utiliser l'analogie de
l'aide d'un fil de trier des

97
00:03:57,350 --> 00:03:59,180
enfiler ces nœuds ensemble.

98
00:03:59,180 --> 00:04:01,760
Et c'est exactement ce que nous faisons avec
pointeurs parce que chacun de ces

99
00:04:01,760 --> 00:04:06,360
des morceaux de la mémoire peuvent ou non être
contiguë, dos à dos à dos

100
00:04:06,360 --> 00:04:09,500
à l'intérieur de RAM, parce que chaque fois que vous
appeler malloc dire, donnez-moi assez

101
00:04:09,500 --> 00:04:12,510
octets pour un nouveau nœud, il pourrait
soit ici ou il peut s'agir ici.

102
00:04:12,510 --> 00:04:13,120
C'est peut-être ici.

103
00:04:13,120 --> 00:04:13,730
C'est peut-être ici.

104
00:04:13,730 --> 00:04:14,640
Vous ne savez tout simplement pas.

105
00:04:14,640 --> 00:04:17,880
>> Mais l'utilisation de pointeurs dans les adresses de
ces nœuds, vous pouvez coudre les

106
00:04:17,880 --> 00:04:22,370
ensemble d'une manière qui est visuellement
comme une liste même si ces choses sont

107
00:04:22,370 --> 00:04:26,770
tout étalé tout au long de votre un ou
Vos deux ou vos quatre gigaoctets de RAM

108
00:04:26,770 --> 00:04:28,760
à l'intérieur de votre propre ordinateur.

109
00:04:28,760 --> 00:04:33,230
>> Ainsi la baisse, alors,
une liste chaînée, c'est quoi?

110
00:04:33,230 --> 00:04:34,670
Qu'est-ce qu'un prix nous sommes
apparemment payer?

111
00:04:34,670 --> 00:04:36,010
>> ETUDIANT: [inaudible].

112
00:04:36,010 --> 00:04:36,920
>> INTERLOCUTEUR 1: Plus d'espace, non?

113
00:04:36,920 --> 00:04:39,340
Nous avons, dans ce cas, a doublé le montant
de l'espace parce que nous sommes passés

114
00:04:39,340 --> 00:04:43,500
de 32 bits pour chaque noeud, pour chaque
int, alors maintenant 64 bits parce que nous devons

115
00:04:43,500 --> 00:04:45,050
maintenir un pointeur près aussi.

116
00:04:45,050 --> 00:04:48,860
Vous obtenez plus d'efficacité si votre struct
est plus grande que cette chose simple.

117
00:04:48,860 --> 00:04:52,020
Si vous avez réellement un élève à l'intérieur
qui est un couple de cordes pour

118
00:04:52,020 --> 00:04:55,430
nom et la maison, peut-être un numéro d'identification,
peut-être quelques autres domaines tout à fait.

119
00:04:55,430 --> 00:04:59,000
>> Donc si vous avez une assez grande structure,
peut-être que le coût du pointeur est

120
00:04:59,000 --> 00:05:00,010
pas une grosse affaire.

121
00:05:00,010 --> 00:05:03,570
C'est un peu un cas d'angle qui
nous stockons une telle primitive simple

122
00:05:03,570 --> 00:05:04,760
à l'intérieur de la liste liée.

123
00:05:04,760 --> 00:05:05,790
Mais le point est le même.

124
00:05:05,790 --> 00:05:08,230
Vous êtes certainement dépenser plus
mémoire, mais vous obtenez

125
00:05:08,230 --> 00:05:08,990
flexibilité.

126
00:05:08,990 --> 00:05:12,280
Parce que maintenant, si je veux ajouter un élément
au début de cette liste,

127
00:05:12,280 --> 00:05:14,340
Je dois attribuer un nouveau nœud.

128
00:05:14,340 --> 00:05:17,180
Et je dois mettre à jour seulement ceux
flèches en quelque sorte en déplaçant simplement

129
00:05:17,180 --> 00:05:17,980
quelques conseils autour.

130
00:05:17,980 --> 00:05:20,580
>> Si je veux insérer quelque chose dans l'
milieu de la liste, je n'ai pas d'

131
00:05:20,580 --> 00:05:24,410
pousser tout le monde à part, comme nous l'avons fait dans
Le passé semaines avec nos bénévoles qui

132
00:05:24,410 --> 00:05:25,700
représenté un tableau.

133
00:05:25,700 --> 00:05:29,470
Je peux attribuer un nouveau nœud et
puis il suffit de pointer les flèches

134
00:05:29,470 --> 00:05:32,290
des directions différentes, car il ne
doivent rester en situation réelle

135
00:05:32,290 --> 00:05:35,670
mémoire d'une véritable ligne comme je l'ai dessiné
ici à l'écran.

136
00:05:35,670 --> 00:05:38,400
>> Et puis enfin, si vous souhaitez insérer
quelque chose à la fin de la liste, c'est

137
00:05:38,400 --> 00:05:39,210
encore plus facile.

138
00:05:39,210 --> 00:05:43,320
C'est une sorte de notation arbitraire,
mais 34 de l'aiguille, prendre une supposition.

139
00:05:43,320 --> 00:05:46,710
Quelle est la valeur de son pointeur plus
susceptibles sorte tiré de comme un vieux

140
00:05:46,710 --> 00:05:47,700
antenne de l'école là-bas?

141
00:05:47,700 --> 00:05:48,920
>> ETUDIANT: [inaudible].

142
00:05:48,920 --> 00:05:49,900
>> INTERLOCUTEUR 1: C'est probablement nulle.

143
00:05:49,900 --> 00:05:52,710
Et en effet, ce qui est à un auteur
représentation de nul.

144
00:05:52,710 --> 00:05:56,310
Et c'est nul parce que vous devez absolument
besoin de savoir où la fin d'une alternance

145
00:05:56,310 --> 00:06:00,050
liste, de peur que vous continuez à suivre et
la suite et la suite de ces flèches

146
00:06:00,050 --> 00:06:01,170
à une certaine valeur d'ordures.

147
00:06:01,170 --> 00:06:06,230
Donc nul signifiera qu'il n'y a pas
plus de nœuds à la droite du numéro 34,

148
00:06:06,230 --> 00:06:07,200
dans ce cas.

149
00:06:07,200 --> 00:06:10,270
>> Nous proposons donc que nous pouvons mettre en œuvre
ce nœud dans le code.

150
00:06:10,270 --> 00:06:12,130
Et nous avons vu ce genre
de syntaxe avant.

151
00:06:12,130 --> 00:06:15,090
Typedef juste définit un nouveau type de
nous, nous donne un synonyme comme

152
00:06:15,090 --> 00:06:17,100
chaîne était pour char *.

153
00:06:17,100 --> 00:06:21,030
Dans ce cas, il va nous donner
notation abrégée afin que nœud de struct

154
00:06:21,030 --> 00:06:24,010
peut au contraire être simplement écrit que
noeud, ce qui est beaucoup plus propres.

155
00:06:24,010 --> 00:06:25,360
C'est beaucoup moins verbeux.

156
00:06:25,360 --> 00:06:30,080
>> A l'intérieur d'un nœud est apparemment un int
appelé n, puis un noeud struct *

157
00:06:30,080 --> 00:06:34,670
ce qui signifie exactement ce que nous voulions le
flèches à dire, un pointeur vers un autre

158
00:06:34,670 --> 00:06:36,940
noeud du même type de données exacte.

159
00:06:36,940 --> 00:06:40,300
Et je propose que nous pourrions mettre en place un
fonction de recherche comme celui-ci, qui, à

160
00:06:40,300 --> 00:06:41,890
première vue, pourrait sembler
un peu complexe.

161
00:06:41,890 --> 00:06:43,330
Mais voyons les choses en contexte.

162
00:06:43,330 --> 00:06:45,480
>> Permettez-moi de passer à l'appareil ici.

163
00:06:45,480 --> 00:06:48,460
Permettez-moi d'ouvrir un fichier appelé
Liste zéro point h.

164
00:06:48,460 --> 00:06:53,950
Et qui ne contient que la définition que nous
juste vu il ya un instant que ces données

165
00:06:53,950 --> 00:06:55,390
Type appelée un nœud.

166
00:06:55,390 --> 00:06:57,350
Donc, nous avons mis cela dans un fichier h dot.

167
00:06:57,350 --> 00:07:01,430
>> Et en passant, même si cette
programme que vous allez voir est

168
00:07:01,430 --> 00:07:05,410
pas tout à fait complexe, il est en effet
convention lors de l'écriture d'un programme de

169
00:07:05,410 --> 00:07:10,270
mettre les choses comme les types de données, de tirer
constantes, parfois, à l'intérieur de votre

170
00:07:10,270 --> 00:07:13,210
fichier d'en-tête et pas nécessairement dans
votre fichier C, certainement lorsque votre

171
00:07:13,210 --> 00:07:17,370
programmes deviennent plus gros et plus grand, de sorte que
vous savez où regarder tant pour

172
00:07:17,370 --> 00:07:20,840
documentation dans certains cas, ou
pour bases de ce genre, les

173
00:07:20,840 --> 00:07:22,360
définition d'un certain type.

174
00:07:22,360 --> 00:07:25,680
>> Si j'ouvre maintenant la liste zéro point
c, remarqué quelques petites choses.

175
00:07:25,680 --> 00:07:29,090
Il comprend quelques fichiers d'en-tête, la plupart des
dont nous avons vu auparavant.

176
00:07:29,090 --> 00:07:31,980
Il inclut son propre fichier d'en-tête.

177
00:07:31,980 --> 00:07:35,200
>> Et en passant, pourquoi c'est à double
citations ici, contrairement à l'angle

178
00:07:35,200 --> 00:07:38,340
parenthèses sur la ligne qui
J'ai souligné il?

179
00:07:38,340 --> 00:07:39,180
>> ETUDIANT: [inaudible].

180
00:07:39,180 --> 00:07:40,460
>> INTERLOCUTEUR 1: Ouais donc c'est un fichier local.

181
00:07:40,460 --> 00:07:44,300
Donc, si c'est un fichier local de votre propre ici
sur la ligne 15, par exemple, vous utilisez

182
00:07:44,300 --> 00:07:46,570
les guillemets au lieu
des chevrons.

183
00:07:46,570 --> 00:07:48,270
>> Maintenant, c'est assez intéressant.

184
00:07:48,270 --> 00:07:51,830
Remarquez que j'ai déclaré un mondial
variable dans ce programme sur la ligne 18

185
00:07:51,830 --> 00:07:55,910
appelé en premier, l'idée étant que c'est
va être un pointeur vers le premier

186
00:07:55,910 --> 00:07:59,190
nœud dans ma liste chaînée, et j'ai
initialisée à null, parce que j'ai

187
00:07:59,190 --> 00:08:02,310
attribué aucune réelle
nœuds pour l'instant.

188
00:08:02,310 --> 00:08:07,570
>> Donc cela représente, imagé, ce que nous
vu il ya un moment dans l'image comme

189
00:08:07,570 --> 00:08:10,090
ce pointeur à l'extrême
côté gauche.

190
00:08:10,090 --> 00:08:12,260
Donc, en ce moment, ce pointeur
n'a pas encore d'une flèche.

191
00:08:12,260 --> 00:08:14,590
Il est plutôt juste nul.

192
00:08:14,590 --> 00:08:17,880
Mais il représente ce que sera l'
l'adresse du premier réelle

193
00:08:17,880 --> 00:08:19,480
noeud de cette liste.

194
00:08:19,480 --> 00:08:22,120
J'ai donc mis en œuvre un mondial
parce que, comme vous le verrez, tout cela

195
00:08:22,120 --> 00:08:25,310
programme fait dans la vie est mise en œuvre
une liste liée pour moi.

196
00:08:25,310 --> 00:08:27,050
>> Maintenant, j'ai quelques prototypes ici.

197
00:08:27,050 --> 00:08:31,190
J'ai décidé de mettre en œuvre des fonctionnalités telles que
suppression, insertion, la recherche et

198
00:08:31,190 --> 00:08:31,740
traversal -

199
00:08:31,740 --> 00:08:35,210
le dernier étant juste promenade à travers la
liste, l'impression de ses éléments.

200
00:08:35,210 --> 00:08:36,750
Et maintenant voici ma routine principale.

201
00:08:36,750 --> 00:08:39,890
Et nous n'allons pas passer trop de temps sur
ceux-ci puisque c'est en quelque sorte, nous espérons

202
00:08:39,890 --> 00:08:41,780
vieux chapeau maintenant.

203
00:08:41,780 --> 00:08:45,370
>> Je vais faire ce qui suit,
pendant que l'utilisateur coopère.

204
00:08:45,370 --> 00:08:47,300
Alors là, je vais imprimer
ce menu.

205
00:08:47,300 --> 00:08:49,420
Et j'ai formaté comme
proprement que je le pouvais.

206
00:08:49,420 --> 00:08:52,240
Si l'utilisateur saisit en un, ce qui signifie
ils veulent supprimer quelque chose.

207
00:08:52,240 --> 00:08:54,560
Si l'utilisateur tape en deux, ce qui signifie
ils veulent insérer quelque chose.

208
00:08:54,560 --> 00:08:55,930
Et ainsi de suite.

209
00:08:55,930 --> 00:08:58,270
Je vais inviter ensuite
puis d'une commande.

210
00:08:58,270 --> 00:08:59,300
Et puis je vais utiliser getInt.

211
00:08:59,300 --> 00:09:02,790
>> Donc, c'est une très simple menuing
interface où vous avez juste à taper

212
00:09:02,790 --> 00:09:05,270
un certain nombre de cartographie à une
de ces commandes.

213
00:09:05,270 --> 00:09:08,730
Et maintenant, j'ai une belle interrupteur propre
déclaration qui va allumer

214
00:09:08,730 --> 00:09:10,090
quel que soit l'utilisateur a tapé po

215
00:09:10,090 --> 00:09:12,180
Et si ils ont tapé un, je vais
appeler supprimer et se briser.

216
00:09:12,180 --> 00:09:14,380
Si ils ont tapé deux, je vais
appeler insérer et se briser.

217
00:09:14,380 --> 00:09:16,490
>> Et maintenant remarquerez que j'ai mis chaque
de ceux-ci sur la même ligne.

218
00:09:16,490 --> 00:09:18,360
C'est juste une décision stylistique.

219
00:09:18,360 --> 00:09:20,210
Typiquement, nous avons vu quelque chose
comme ça.

220
00:09:20,210 --> 00:09:23,260
Mais j'ai décidé, franchement, mon programme
regardé plus lisible car

221
00:09:23,260 --> 00:09:25,980
il n'y avait que quatre cas
se contenter d'énumérer comme ça.

222
00:09:25,980 --> 00:09:28,360
Utilisation tout à fait légitime de section.

223
00:09:28,360 --> 00:09:31,480
Et je vais le faire aussi longtemps que le
utilisateur n'a pas tapé zéro, que je

224
00:09:31,480 --> 00:09:33,910
décidé signifiera qu'ils veulent cesser de fumer.

225
00:09:33,910 --> 00:09:36,630
>> Alors maintenant, remarque ce que je suis
allons faire ici.

226
00:09:36,630 --> 00:09:38,650
Je vais libérer la liste apparemment.

227
00:09:38,650 --> 00:09:40,230
Mais plus à ce sujet dans un instant.

228
00:09:40,230 --> 00:09:41,640
Voyons d'abord exécuter ce programme.

229
00:09:41,640 --> 00:09:45,250
Alors permettez-moi de faire un terminal plus grand
fenêtre, point barre oblique liste 0.

230
00:09:45,250 --> 00:09:49,510
Je vais aller de l'avant et insérez par
taper deux, un nombre comme 50, et maintenant

231
00:09:49,510 --> 00:09:51,590
vous verrez la liste est maintenant de 50.

232
00:09:51,590 --> 00:09:53,380
Et mon texte défile juste un peu.

233
00:09:53,380 --> 00:09:55,940
Alors maintenant, notez la liste contient
le nombre 50.

234
00:09:55,940 --> 00:09:58,220
>> Faisons un autre insert en prenant deux.

235
00:09:58,220 --> 00:10:01,630
Nous allons taper le numéro comme tel.

236
00:10:01,630 --> 00:10:03,940
Liste est maintenant l'un, puis 50.

237
00:10:03,940 --> 00:10:06,020
Donc, c'est juste une représentation textuelle
de la liste.

238
00:10:06,020 --> 00:10:10,550
Et nous allons insérer un nombre plus comme
le nombre 42, qui est, espérons-

239
00:10:10,550 --> 00:10:14,620
va finir dans le milieu, parce que
ce programme en particulier trie

240
00:10:14,620 --> 00:10:16,320
éléments comme il les inserts.

241
00:10:16,320 --> 00:10:17,220
Donc, il nous l'avons.

242
00:10:17,220 --> 00:10:20,730
Programme super simple qui pourrait
absolument avoir utilisé un tableau, mais je

243
00:10:20,730 --> 00:10:23,280
arriver à être en utilisant une liste chaînée
juste pour que je puisse dynamique

244
00:10:23,280 --> 00:10:24,610
grandir et rétrécir.

245
00:10:24,610 --> 00:10:28,470
>> Donc, nous allons jeter un oeil pour la recherche, si je
trois commandes de fonctionner, je veux chercher

246
00:10:28,470 --> 00:10:31,040
pour, par exemple, le nombre 43.

247
00:10:31,040 --> 00:10:34,190
Et rien ne semble avoir été trouvé,
parce que je suis rentré sans réponse.

248
00:10:34,190 --> 00:10:35,010
Donc, nous allons le faire à nouveau.

249
00:10:35,010 --> 00:10:35,690
Rechercher.

250
00:10:35,690 --> 00:10:39,520
Cherchons à 50, ou plutôt rechercher
pour 42, qui a une belle

251
00:10:39,520 --> 00:10:40,850
peu de sens subtil.

252
00:10:40,850 --> 00:10:42,610
Et j'ai trouvé le sens de la vie là-bas.

253
00:10:42,610 --> 00:10:44,990
Numéro 42, si vous ne savez pas
la référence, Google il.

254
00:10:44,990 --> 00:10:45,350
Très bien.

255
00:10:45,350 --> 00:10:47,130
Que s'est-il ce programme fait pour moi?

256
00:10:47,130 --> 00:10:50,660
C'est juste m'a permis d'insérer ainsi
loin et rechercher des éléments.

257
00:10:50,660 --> 00:10:53,650
>> Allons de l'avant rapide, puis, à
cette fonction nous regarda

258
00:10:53,650 --> 00:10:55,360
le lundi comme un teaser.

259
00:10:55,360 --> 00:10:59,620
Donc cette fonction, je prétends, les recherches pour
un élément dans la liste en premier

260
00:10:59,620 --> 00:11:03,830
une, demandant à l'utilisateur, puis en appelant
GetInt pour obtenir une réelle int

261
00:11:03,830 --> 00:11:05,060
que vous souhaitez rechercher.

262
00:11:05,060 --> 00:11:06,460
>> Ensuite remarquer cela.

263
00:11:06,460 --> 00:11:10,690
Je vais créer une variable temporaire
en ligne 188 appelé pointeur -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
aurait appelé cela rien.

266
00:11:12,440 --> 00:11:16,140
Et c'est un pointeur vers un noeud
parce que j'ai dit il ya noeud *.

267
00:11:16,140 --> 00:11:19,900
Et je l'initialiser soit égale à
d'abord en sorte que j'ai effectivement ma

268
00:11:19,900 --> 00:11:22,860
doigt, pour ainsi dire, sur le très
premier élément de la liste.

269
00:11:22,860 --> 00:11:27,460
Donc, si ma main droite est ici PTR je suis
pointant vers la même chose que le premier

270
00:11:27,460 --> 00:11:28,670
est pointé.

271
00:11:28,670 --> 00:11:31,430
>> Donc, maintenant de retour dans le code,
ce qui arrive ensuite -

272
00:11:31,430 --> 00:11:35,070
il s'agit d'un paradigme commun lors de l'itération
sur une structure comme une

273
00:11:35,070 --> 00:11:35,970
liste chaînée.

274
00:11:35,970 --> 00:11:40,410
Je vais faire ce qui suit
pointeur n'est pas égal à null, donc tout

275
00:11:40,410 --> 00:11:47,530
mon doigt ne pointe pas à un nul
valeur, si le pointeur flèche n est égal à n.

276
00:11:47,530 --> 00:11:52,290
Nous remarquons d'abord que n est ce que l'
tapé par l'utilisateur GetInts appeler ici.

277
00:11:52,290 --> 00:11:54,280
>> Et pointeur flèche n veut dire quoi?

278
00:11:54,280 --> 00:11:59,020
Eh bien, si nous revenons à l'image ici,
si j'ai un doigt pointé vers

279
00:11:59,020 --> 00:12:02,960
que le premier nœud contenant neuf, le
flèche signifie essentiellement aller à ce

280
00:12:02,960 --> 00:12:08,860
nœud et saisir la valeur à l'emplacement n,
Dans ce cas, le champ de données appelée n.

281
00:12:08,860 --> 00:12:14,120
>> Soit dit en passant - et nous avons vu ce couple
il ya quelques semaines lorsque quelqu'un a demandé -

282
00:12:14,120 --> 00:12:18,840
cette syntaxe est nouveau, mais il ne
nous donner des pouvoirs que nous

283
00:12:18,840 --> 00:12:20,040
ne pas avoir déjà.

284
00:12:20,040 --> 00:12:25,325
Quelle était cette phrase équivaut à utiliser
dot notation et la star d'un couple

285
00:12:25,325 --> 00:12:29,490
Il ya quelques semaines, lorsque nous décollée
cette couche un peu prématurée?

286
00:12:29,490 --> 00:12:31,780
>> ETUDIANT: [inaudible].

287
00:12:31,780 --> 00:12:38,880
>> INTERLOCUTEUR 1: Exactement, c'était étoiles, et
puis ce fut étoile point n, avec

288
00:12:38,880 --> 00:12:41,930
parenthèses ici, qui ressemble,
Franchement, je pense que beaucoup

289
00:12:41,930 --> 00:12:43,320
plus énigmatique à lire.

290
00:12:43,320 --> 00:12:46,270
Mais Star Pointer, comme toujours,
moyens y aller.

291
00:12:46,270 --> 00:12:49,090
Et une fois que vous y êtes, quelles données
domaine voulez-vous accéder?

292
00:12:49,090 --> 00:12:52,730
Eh bien, vous utilisez la notation par point d'accès
un champ de données de structures, et je

293
00:12:52,730 --> 00:12:54,140
veulent spécifiquement n.

294
00:12:54,140 --> 00:12:56,240
>> Franchement, je dirais cette
est juste plus difficile à lire.

295
00:12:56,240 --> 00:12:58,080
Il est plus difficile de se rappeler où
ne les parenthèses vont, l'

296
00:12:58,080 --> 00:12:59,030
étoiles et tout ça.

297
00:12:59,030 --> 00:13:02,150
Ainsi, le monde a adopté un certain syntaxique
sucre, pour ainsi dire.

298
00:13:02,150 --> 00:13:04,740
Juste une façon sexy de dire,
c'est l'équivalent, et

299
00:13:04,740 --> 00:13:05,970
peut-être plus intuitive.

300
00:13:05,970 --> 00:13:09,600
Si le pointeur est en effet un pointeur, l'
moyens de notation fléchées y aller et trouver

301
00:13:09,600 --> 00:13:11,890
le terrain dans ce cas appelé n.

302
00:13:11,890 --> 00:13:13,660
>> Donc, si je trouve, notez ce que je fais.

303
00:13:13,660 --> 00:13:17,430
Je suffit d'imprimer, j'ai trouvé pour cent i,
brancher la valeur de cette int.

304
00:13:17,430 --> 00:13:20,730
J'appelle dormir pendant une seconde juste genre
de pause choses à l'écran pour

305
00:13:20,730 --> 00:13:22,900
donner à l'utilisateur une seconde pour absorber
ce qui vient de se passer.

306
00:13:22,900 --> 00:13:24,290
Et puis, je me casse.

307
00:13:24,290 --> 00:13:26,330
Sinon, je fais quoi?

308
00:13:26,330 --> 00:13:30,960
Je mets à jour le pointeur à l'égalité
la flèche du pointeur prochaine.

309
00:13:30,960 --> 00:13:35,840
>> Donc, juste pour être clair, cela signifie aller
là-bas, en utilisant ma notation de la vieille école.

310
00:13:35,840 --> 00:13:39,580
Donc, cela signifie simplement aller à n'importe quel
que vous pointez, qui dans la très

311
00:13:39,580 --> 00:13:43,660
premier cas, c'est que je fais remarquer à
la structure à neuf en elle.

312
00:13:43,660 --> 00:13:44,510
Donc, je suis allé là-bas.

313
00:13:44,510 --> 00:13:47,880
Et puis, signifie la notation par point,
obtenir la valeur lors de la prochaine.

314
00:13:47,880 --> 00:13:50,470
>> Mais la valeur, même si elle est dessinée
comme étroite, est juste un nombre.

315
00:13:50,470 --> 00:13:51,720
Il s'agit d'une adresse numérique.

316
00:13:51,720 --> 00:13:55,670
Donc cette seule ligne de code, si
écrit comme ça, le plus énigmatique

317
00:13:55,670 --> 00:14:00,190
Ainsi, ou comme ça, le peu plus
manière intuitive, signifie simplement déplacer ma main

318
00:14:00,190 --> 00:14:03,460
à partir du premier noeud à la suivante,
puis la suivante, puis le

319
00:14:03,460 --> 00:14:05,320
suivant, et ainsi de suite.

320
00:14:05,320 --> 00:14:09,920
>> Donc, nous ne nous attarderons pas sur l'autre
implémentations d'insérer et de supprimer

321
00:14:09,920 --> 00:14:14,030
et la traversée, dont les deux premières
qui sont assez impliqués.

322
00:14:14,030 --> 00:14:17,010
Et je pense que c'est assez facile à obtenir
perdu quand il le faire verbalement.

323
00:14:17,010 --> 00:14:19,890
Mais ce que nous pouvons faire ici est
essayer de déterminer comment

324
00:14:19,890 --> 00:14:21,640
mieux de le faire visuellement.

325
00:14:21,640 --> 00:14:24,800
Parce que je voudrais proposer que si nous
insérer les éléments dans cette

326
00:14:24,800 --> 00:14:26,680
liste existante, qui
comporte cinq éléments -

327
00:14:26,680 --> 00:14:29,530
9, 17, 22, 26, et 33 -

328
00:14:29,530 --> 00:14:33,300
si je devais mettre en œuvre ce dans
code, j'ai besoin de considérer comment s'y prendre

329
00:14:33,300 --> 00:14:34,160
prendre.

330
00:14:34,160 --> 00:14:37,720
>> Et je vous propose de prendre des mesures de bébé
de sorte que, dans ce cas, je veux dire, quels sont

331
00:14:37,720 --> 00:14:41,090
les scénarios possibles que nous
pourraient rencontrer en général?

332
00:14:41,090 --> 00:14:44,120
Lorsque la mise en œuvre d'un insert lié
liste, cela arrive juste à être un

333
00:14:44,120 --> 00:14:46,090
exemple précis de la taille de cinq ans.

334
00:14:46,090 --> 00:14:50,420
Eh bien, si vous voulez insérer un numéro,
comme, disons, le numéro un, et

335
00:14:50,420 --> 00:14:53,380
le maintien de l'ordre de tri, où
fait évidemment le numéro un besoin d'

336
00:14:53,380 --> 00:14:55,686
aller dans cet exemple précis?

337
00:14:55,686 --> 00:14:56,840
Comme au début.

338
00:14:56,840 --> 00:15:00,030
>> Mais ce qui est intéressant, c'est que là
si vous voulez insérer un dans cette

339
00:15:00,030 --> 00:15:04,100
liste, ce pointeur particulière doit
être mis à jour apparemment?

340
00:15:04,100 --> 00:15:04,610
Première.

341
00:15:04,610 --> 00:15:07,830
Je dirais donc, c'est le premier cas
que nous pourrions envisager, une

342
00:15:07,830 --> 00:15:11,140
scénario impliquant l'insertion d'au
le début de la liste.

343
00:15:11,140 --> 00:15:15,400
>> Allons arrachez peut-être un aussi facile ou même
cas plus facile, relativement parlant.

344
00:15:15,400 --> 00:15:18,110
Supposons que je veux insérer l'
Numéro 35 dans l'ordre.

345
00:15:18,110 --> 00:15:20,600
Il appartient évidemment là-bas.

346
00:15:20,600 --> 00:15:25,320
Alors qu'est-ce pointeur évidemment va
être mis à jour dans ce scénario?

347
00:15:25,320 --> 00:15:30,060
34 de la pointeur de devenir non nulle
mais l'adresse de la structure

348
00:15:30,060 --> 00:15:31,800
contenant le numéro 35.

349
00:15:31,800 --> 00:15:32,750
C'est donc deux cas.

350
00:15:32,750 --> 00:15:36,190
Donc, déjà, je suis une sorte de quantification
la quantité de travail que j'ai à faire ici.

351
00:15:36,190 --> 00:15:39,880
>> Et enfin, le cas du milieu est évident
En effet, dans le milieu, si je veux

352
00:15:39,880 --> 00:15:45,870
insérer quelque chose comme, disons 23, qui va
entre le 23 et le 26, mais

353
00:15:45,870 --> 00:15:48,680
maintenant les choses deviennent un peu plus
impliqué parce que ce

354
00:15:48,680 --> 00:15:52,800
pointeurs doivent être changées?

355
00:15:52,800 --> 00:15:56,680
Donc 22 doit évidemment être changé
parce qu'il ne peut pas pointer vers 26 plus.

356
00:15:56,680 --> 00:16:00,320
Il doit pointer vers le nouveau nœud
Je vais devoir répartir en appelant

357
00:16:00,320 --> 00:16:01,770
malloc ou quelque chose d'équivalent.

358
00:16:01,770 --> 00:16:05,990
>> Mais ensuite, j'ai aussi besoin que le nouveau nœud, 23
dans ce cas, d'avoir son pointeur

359
00:16:05,990 --> 00:16:07,870
pointant à qui?

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
Et il va y avoir une
ordre des opérations ici.

362
00:16:10,380 --> 00:16:13,410
Parce que si je fais ça bêtement, et je
par exemple début au début de

363
00:16:13,410 --> 00:16:16,040
la liste, et mon but est d'insérer 23.

364
00:16:16,040 --> 00:16:18,610
Et je vérifie, appartient-il
ici, près de neuf?

365
00:16:18,610 --> 00:16:18,950
No.

366
00:16:18,950 --> 00:16:20,670
Appartient-elle ici, à côté de 17?

367
00:16:20,670 --> 00:16:20,940
No.

368
00:16:20,940 --> 00:16:22,530
Est-ce qu'il appartient ici à côté de 22?

369
00:16:22,530 --> 00:16:23,300
Oui.

370
00:16:23,300 --> 00:16:26,400
>> Maintenant, si je suis fou ici, et pas
pensant que cela à travers, je pourrais

371
00:16:26,400 --> 00:16:28,320
allouer mon nouveau nœud pour 23.

372
00:16:28,320 --> 00:16:32,080
Je pourrais mettre à jour le pointeur de
le nœud appelé 22, pointant

373
00:16:32,080 --> 00:16:33,080
il au nouveau nœud.

374
00:16:33,080 --> 00:16:36,140
Et puis qu'est-ce que je dois mettre à jour
le pointeur du nouveau nœud de l'être?

375
00:16:36,140 --> 00:16:38,120
>> ETUDIANT: [inaudible].

376
00:16:38,120 --> 00:16:38,385
>> ENCEINTE 1: Exactement.

377
00:16:38,385 --> 00:16:39,710
Pointant à 26.

378
00:16:39,710 --> 00:16:45,590
Mais dammit si je n'avais pas déjà mettre à jour
Le pointeur de 22 pour pointer vers ce type, et

379
00:16:45,590 --> 00:16:48,260
maintenant j'ai orphelins, le reste
de la liste, pour ainsi dire.

380
00:16:48,260 --> 00:16:52,140
Donc, l'ordre des opérations ici
va être importante.

381
00:16:52,140 --> 00:16:55,100
>> Pour ce faire, je pourrais voler,
disons, six bénévoles.

382
00:16:55,100 --> 00:16:57,650
Et nous allons voir si nous ne pouvons pas le faire
visuellement au lieu du code-sage.

383
00:16:57,650 --> 00:16:59,330
Et nous avons une belle contrainte
boules pour vous aujourd'hui.

384
00:16:59,330 --> 00:17:02,510
OK, que diriez-vous un, deux, dans le
arrière - sur la fin il.

385
00:17:02,510 --> 00:17:04,530
trois, quatre, deux d'entre vous
les gars sur la fin.

386
00:17:04,530 --> 00:17:05,579
Et cinq, six.

387
00:17:05,579 --> 00:17:05,839
Bien sûr.

388
00:17:05,839 --> 00:17:06,450
Cinq et six ans.

389
00:17:06,450 --> 00:17:08,390
Tous droits et nous viendrons
à vous les gars la prochaine fois.

390
00:17:08,390 --> 00:17:09,640
Très bien, allez vers le haut.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> Très bien, puisque vous êtes ici en premier,
aimeriez-vous être celui maladroitement

393
00:17:14,819 --> 00:17:16,119
Google en verre ici?

394
00:17:16,119 --> 00:17:19,075
D'accord, donc, OK, verre,
enregistrer une vidéo.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
OK, vous êtes bon pour aller.

397
00:17:24,589 --> 00:17:27,950
>> D'accord, donc si vous les gars peut venir
ici, j'ai préparé à l'avance

398
00:17:27,950 --> 00:17:30,110
quelques chiffres.

399
00:17:30,110 --> 00:17:31,240
Très bien, venez par ici.

400
00:17:31,240 --> 00:17:33,440
Et pourquoi ne vas-tu pas un peu
en outre cette façon.

401
00:17:33,440 --> 00:17:35,520
Et Voyons, quel est votre nom,
avec le verre de Google?

402
00:17:35,520 --> 00:17:35,910
>> ETUDIANT: Ben.

403
00:17:35,910 --> 00:17:36,230
>> INTERLOCUTEUR 1: Ben?

404
00:17:36,230 --> 00:17:38,380
OK, Ben, vous serez d'abord, littéralement.

405
00:17:38,380 --> 00:17:40,580
Donc, nous allons vous envoyer
à la fin de l'étape.

406
00:17:40,580 --> 00:17:41,670
Bon, et ton nom?

407
00:17:41,670 --> 00:17:41,990
>> ETUDIANT: Jason.

408
00:17:41,990 --> 00:17:44,530
>> INTERLOCUTEUR 1: Jason, OK vous aurez
être le numéro neuf.

409
00:17:44,530 --> 00:17:46,700
Donc, si vous voulez suivre Ben ça.

410
00:17:46,700 --> 00:17:47,010
>> ETUDIANT: Jill.

411
00:17:47,010 --> 00:17:49,630
>> INTERLOCUTEUR 1: Jill, vous allez être
17, qui, si j'avais fait ce plus

412
00:17:49,630 --> 00:17:51,260
intelligemment, je n'aurais
commencé à l'autre extrémité.

413
00:17:51,260 --> 00:17:52,370
Vous allez de cette façon.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
Et vous êtes?

416
00:17:53,670 --> 00:17:53,980
>> ETUDIANT: Marie.

417
00:17:53,980 --> 00:17:56,130
>> INTERLOCUTEUR 1: Marie, vous serez 22.

418
00:17:56,130 --> 00:17:58,420
Et votre nom?

419
00:17:58,420 --> 00:17:58,810
>> ETUDIANT: Chris.

420
00:17:58,810 --> 00:18:00,100
>> INTERLOCUTEUR 1: Chris, vous serez 26.

421
00:18:00,100 --> 00:18:00,740
Et puis enfin.

422
00:18:00,740 --> 00:18:01,400
>> ETUDIANT: Diana.

423
00:18:01,400 --> 00:18:02,670
>> INTERLOCUTEUR 1: Diana, vous serez 34.

424
00:18:02,670 --> 00:18:03,920
Donc, vous venez par ici.

425
00:18:03,920 --> 00:18:06,360
>> Très bien, si parfait triés
commander déjà.

426
00:18:06,360 --> 00:18:09,600
Et nous allons aller de l'avant et faire ce
afin que nous puissions vraiment -

427
00:18:09,600 --> 00:18:11,720
Ben vous êtes juste un peu de recherche
out dans le néant là.

428
00:18:11,720 --> 00:18:15,670
OK, nous allons donc aller de l'avant et illustrent cette
en utilisant des armes, tout comme je l'étais, exactement,

429
00:18:15,670 --> 00:18:16,250
ce qui se passe.

430
00:18:16,250 --> 00:18:19,540
Alors allez-y et donnez-vous un
pied ou deux entre vous.

431
00:18:19,540 --> 00:18:22,900
Et aller de l'avant et pointer d'une main pour
celui qui vous doit être dirigée à

432
00:18:22,900 --> 00:18:23,470
sur cette base.

433
00:18:23,470 --> 00:18:25,890
Et si vous êtes nul suffit de pointer
tout droit vers le sol.

434
00:18:25,890 --> 00:18:27,690
OK, tout va bien.

435
00:18:27,690 --> 00:18:32,290
>> Alors maintenant, nous avons une liste chaînée, et laissez-moi
propose que je vais jouer le rôle de

436
00:18:32,290 --> 00:18:35,110
PTR, donc je ne vais pas
porter ce autour.

437
00:18:35,110 --> 00:18:37,830
Et puis - quelqu'un convention stupide -
vous pouvez appeler ce que vous voulez -

438
00:18:37,830 --> 00:18:39,800
pointeur prédécesseur, pointeur pred -

439
00:18:39,800 --> 00:18:43,930
c'est juste le surnom que nous avons donné à
notre exemple de code pour la main gauche.

440
00:18:43,930 --> 00:18:47,240
L'autre main qui va être maintenant
trace de qui est qui dans le

441
00:18:47,240 --> 00:18:48,400
suivant les scénarios.

442
00:18:48,400 --> 00:18:52,390
>> Alors suppose, d'abord, je tiens à arrachez
ce premier exemple d'insertion, par exemple

443
00:18:52,390 --> 00:18:54,330
20, dans la liste.

444
00:18:54,330 --> 00:18:57,160
Donc, je vais avoir besoin de quelqu'un pour
incarner le numéro 20 pour nous.

445
00:18:57,160 --> 00:18:58,950
J'ai donc besoin de quelqu'un malloc
de l'auditoire.

446
00:18:58,950 --> 00:18:59,380
Venez sur place.

447
00:18:59,380 --> 00:19:00,340
Quel est votre nom?

448
00:19:00,340 --> 00:19:01,300
>> ETUDIANT: Brian.

449
00:19:01,300 --> 00:19:05,270
>> INTERLOCUTEUR 1: Brian, tout droit, de sorte que vous
est le noeud contenant 20.

450
00:19:05,270 --> 00:19:06,810
Très bien, venez par ici.

451
00:19:06,810 --> 00:19:10,025
Et évidemment, où
ne Brian appartient-il?

452
00:19:10,025 --> 00:19:12,190
Ainsi, au milieu de - en fait,
Attendez une minute.

453
00:19:12,190 --> 00:19:13,420
Nous faisons cela en panne.

454
00:19:13,420 --> 00:19:17,170
Nous faisons cela beaucoup plus difficile
qu'elle doit être au premier abord.

455
00:19:17,170 --> 00:19:21,210
OK, nous allons libre Brian
et realloc Brian en cinq ans.

456
00:19:21,210 --> 00:19:23,680
>> OK, maintenant nous voulons insérer
Brian que cinq.

457
00:19:23,680 --> 00:19:25,960
Alors venez ici à côté de
Ben pour un instant.

458
00:19:25,960 --> 00:19:28,250
Et vous pouvez sans doute dire
où cette histoire va.

459
00:19:28,250 --> 00:19:30,500
Mais nous devons penser soigneusement à
l'ordre des opérations.

460
00:19:30,500 --> 00:19:32,880
Et c'est justement ce visuel
qui va s'aligner

461
00:19:32,880 --> 00:19:34,080
avec ce code échantillon.

462
00:19:34,080 --> 00:19:40,120
Donc ici, je n'ai PTR pointant initialement
pas à Ben, en soi, mais quel que soit le

463
00:19:40,120 --> 00:19:43,245
valeur qu'il contient, qui dans ce cas
est - quel est votre nom?

464
00:19:43,245 --> 00:19:43,670
>> ETUDIANT: Jason.

465
00:19:43,670 --> 00:19:47,350
>> INTERLOCUTEUR 1: Jason, donc Ben et moi sommes
montrant Jason en ce moment.

466
00:19:47,350 --> 00:19:49,700
Alors maintenant, je dois déterminer,
où est Brian appartient-il?

467
00:19:49,700 --> 00:19:53,500
Donc la seule chose que j'ai accès à
en ce moment, c'est son élément de données n.

468
00:19:53,500 --> 00:19:58,280
Donc, je vais vérifier, n'est-
Brian moins de Jason?

469
00:19:58,280 --> 00:19:59,770
La réponse est vrai.

470
00:19:59,770 --> 00:20:03,680
>> Que faut-il maintenant se passer,
dans le bon ordre?

471
00:20:03,680 --> 00:20:07,120
J'ai besoin de mettre à jour le nombre de pointeurs
Au total dans cette histoire?

472
00:20:07,120 --> 00:20:10,720
Lorsque ma main est toujours pointée vers
Jason, et votre main - si vous voulez

473
00:20:10,720 --> 00:20:12,930
mettez votre main comme, en quelque sorte, je
Je ne sais pas, un point d'interrogation.

474
00:20:12,930 --> 00:20:14,070
OK, c'est bon.

475
00:20:14,070 --> 00:20:15,670
>> Très bien, alors vous avez
quelques candidats.

476
00:20:15,670 --> 00:20:20,500
Soit Ben, moi ou Brian ou Jason
ou tout le monde, qui

477
00:20:20,500 --> 00:20:21,370
pointeurs doivent changer?

478
00:20:21,370 --> 00:20:23,260
Combien au total?

479
00:20:23,260 --> 00:20:24,080
>> OK, donc deux.

480
00:20:24,080 --> 00:20:27,090
Mon pointeur ne compte pas vraiment plus
parce que je suis juste temporaire.

481
00:20:27,090 --> 00:20:31,370
Donc, ce sont ces deux gars, sans doute,
Ben et Brian.

482
00:20:31,370 --> 00:20:34,410
Alors permettez-moi de proposer que nous mettons à jour
Ben, depuis qu'il est premier.

483
00:20:34,410 --> 00:20:36,350
Le premier élément de cette liste
va maintenant être Brian.

484
00:20:36,350 --> 00:20:38,070
Donc, point de Ben à Brian.

485
00:20:38,070 --> 00:20:39,320
OK, et maintenant?

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> Qui se fait à qui?

488
00:20:43,460 --> 00:20:44,710
>> ETUDIANT: [inaudible].

489
00:20:44,710 --> 00:20:46,180
>> INTERLOCUTEUR 1: OK si Brian a
pour pointer vers Jason.

490
00:20:46,180 --> 00:20:48,360
Mais ai-je perdu la trace de ce pointeur?

491
00:20:48,360 --> 00:20:49,980
Est-ce que je sais où Jason est?

492
00:20:49,980 --> 00:20:50,790
>> ETUDIANT: [inaudible].

493
00:20:50,790 --> 00:20:52,620
>> INTERLOCUTEUR 1: je le fais, car je suis
le pointeur temporaire.

494
00:20:52,620 --> 00:20:55,110
Et sans doute, je n'ai pas changé
pour pointer vers le nouveau nœud.

495
00:20:55,110 --> 00:20:58,300
Donc, nous ne pouvons tout simplement avoir point de Brian
à qui je suis pointé.

496
00:20:58,300 --> 00:20:59,000
Et nous avons terminé.

497
00:20:59,000 --> 00:21:01,890
Donc un cas, l'insertion à l'
au début de la liste.

498
00:21:01,890 --> 00:21:02,950
Il y avait deux étapes principales.

499
00:21:02,950 --> 00:21:06,750
D'abord, nous devons mettre à jour Ben, puis
nous devons également mettre à jour Brian.

500
00:21:06,750 --> 00:21:09,230
Et puis je n'ai pas besoin de s'embêter
se promènent à travers le reste de l'

501
00:21:09,230 --> 00:21:12,680
liste, car nous avons déjà trouvé son
lieu, parce qu'il appartenait à l'

502
00:21:12,680 --> 00:21:14,080
à gauche du premier élément.

503
00:21:14,080 --> 00:21:15,400
>> D'accord, donc assez simple.

504
00:21:15,400 --> 00:21:18,110
En fait, se sent comme nous sommes presque
ce qui en fait trop compliqué.

505
00:21:18,110 --> 00:21:20,240
Donc, nous allons maintenant arrachez la fin
de la liste, et de voir où

506
00:21:20,240 --> 00:21:21,380
la complexité commence.

507
00:21:21,380 --> 00:21:24,560
Donc, si aujourd'hui, je alloc de l'auditoire.

508
00:21:24,560 --> 00:21:25,540
Tout le monde veut jouer 55?

509
00:21:25,540 --> 00:21:26,700
Bon, j'ai vu votre première main.

510
00:21:26,700 --> 00:21:29,620
Venez sur place.

511
00:21:29,620 --> 00:21:30,030
Ouais.

512
00:21:30,030 --> 00:21:31,177
Quel est votre nom?

513
00:21:31,177 --> 00:21:32,310
>> ETUDIANT: [inaudible].

514
00:21:32,310 --> 00:21:33,240
>> INTERLOCUTEUR 1: Habata.

515
00:21:33,240 --> 00:21:33,890
OK, venez sur place.

516
00:21:33,890 --> 00:21:35,730
Vous serez le numéro 55.

517
00:21:35,730 --> 00:21:37,820
Donc, vous, bien sûr, appartenez
à la fin de la liste.

518
00:21:37,820 --> 00:21:41,850
Donc, nous allons rejouer la simulation avec moi
étant le PTR pour un instant.

519
00:21:41,850 --> 00:21:44,050
Donc, je vais d'abord faire remarquer à
Ben tout est pointé.

520
00:21:44,050 --> 00:21:45,900
Nous sommes tous les deux pointant désormais à Brian.

521
00:21:45,900 --> 00:21:48,420
Donc 55 n'est pas inférieur à cinq.

522
00:21:48,420 --> 00:21:52,510
Donc, je vais me mettre à jour par
pointant vers la prochaine pointeur de Brian, qui

523
00:21:52,510 --> 00:21:54,450
maintenant, c'est bien sûr Jason.

524
00:21:54,450 --> 00:21:57,310
55 n'est pas moins de neuf, donc
Je vais mettre à jour PTR.

525
00:21:57,310 --> 00:21:58,890
Je vais mettre à jour PTR.

526
00:21:58,890 --> 00:22:02,290
Je vais mettre à jour PTR
Je vais mettre à jour PTR.

527
00:22:02,290 --> 00:22:05,060
Et je vais - hmm, ce qui est
votre nom?

528
00:22:05,060 --> 00:22:05,560
>> ETUDIANT: Diana.

529
00:22:05,560 --> 00:22:09,190
>> INTERLOCUTEUR 1: Diana pointe, bien sûr,
à nulle avec sa main gauche.

530
00:22:09,190 --> 00:22:13,030
Alors d'où vient réellement Habata
appartiennent clairement?

531
00:22:13,030 --> 00:22:15,050
Pour la gauche, ici.

532
00:22:15,050 --> 00:22:19,460
Alors, comment puis-je savoir la mettre ici
Je crois que j'ai merdé.

533
00:22:19,460 --> 00:22:22,420
Parce que ce qui est PTR art
ce moment-là?

534
00:22:22,420 --> 00:22:23,240
NULL.

535
00:22:23,240 --> 00:22:25,580
Ainsi, même si, visuellement, nous pouvons
évidemment voir tous ces

536
00:22:25,580 --> 00:22:26,610
gars ici sur scène.

537
00:22:26,610 --> 00:22:29,680
Je n'ai pas gardé la trace de la précédente
personne dans la liste.

538
00:22:29,680 --> 00:22:33,210
Je n'ai pas un doigt pointé sur,
Dans ce cas, le numéro de noeud 34.

539
00:22:33,210 --> 00:22:34,760
>> Donc, nous allons réellement commencer ce cours.

540
00:22:34,760 --> 00:22:37,560
Alors maintenant, je n'ai réellement besoin
une seconde variable locale.

541
00:22:37,560 --> 00:22:40,980
Et c'est ce que vous verrez dans le
échantillon réel du code C, alors que je vais,

542
00:22:40,980 --> 00:22:45,860
quand je mets à jour ma main droite pour pointer
Jason, laissant ainsi derrière Brian, je

543
00:22:45,860 --> 00:22:51,440
mieux commencer à utiliser ma main gauche pour
jour où j'étais, de sorte que je vais

544
00:22:51,440 --> 00:22:52,700
grâce à cette liste -

545
00:22:52,700 --> 00:22:55,040
plus maladroitement que je comptais
maintenant ici visuellement -

546
00:22:55,040 --> 00:22:56,740
Je vais aller à l'
fin de la liste.

547
00:22:56,740 --> 00:23:00,020
>> Cette main est encore nul, ce qui est assez
inutile, sauf pour indiquer

548
00:23:00,020 --> 00:23:02,980
Je suis clairement à la fin de la liste,
mais maintenant, au moins, j'ai cette

549
00:23:02,980 --> 00:23:08,270
pointeur prédécesseur pointant ici,
maintenant ce que les mains et les pointeurs doivent

550
00:23:08,270 --> 00:23:10,150
être mis à jour?

551
00:23:10,150 --> 00:23:13,214
Dont la main que vous voulez
pour reconfigurer le premier?

552
00:23:13,214 --> 00:23:15,190
>> ETUDIANT: [inaudible].

553
00:23:15,190 --> 00:23:16,220
>> INTERLOCUTEUR 1: OK, donc Diana.

554
00:23:16,220 --> 00:23:21,110
Où voulez-vous faire remarquer
Pointeur vers la gauche de Diana à?

555
00:23:21,110 --> 00:23:23,620
À 55 ans, vraisemblablement, de sorte que
nous avons inséré là.

556
00:23:23,620 --> 00:23:25,560
Et où doit-55 pointeur aller?

557
00:23:25,560 --> 00:23:27,000
Vers le bas, soit nulle.

558
00:23:27,000 --> 00:23:28,890
Et mes mains, à ce stade, ne le font pas
importance car ils étaient juste

559
00:23:28,890 --> 00:23:30,070
variables temporaires.

560
00:23:30,070 --> 00:23:31,030
Alors maintenant, nous avons terminé.

561
00:23:31,030 --> 00:23:34,650
>> Ainsi, la complexité supplémentaire là-bas - et
ce n'est pas si difficile à mettre en œuvre,

562
00:23:34,650 --> 00:23:38,660
mais nous avons besoin d'une variable secondaire à faire
vous que avant que je passe mon droit

563
00:23:38,660 --> 00:23:42,140
Par contre, je mets à jour la valeur de ma gauche
main, pointeur pred dans ce cas, si

564
00:23:42,140 --> 00:23:45,860
que j'ai un pointeur de fuite
de garder une trace de l'endroit où je me trouvais.

565
00:23:45,860 --> 00:23:49,360
Maintenant, en passant, si vous songez à ce
à travers, cela se sent comme c'est un

566
00:23:49,360 --> 00:23:51,490
peu ennuyeux d'avoir à garder
la trace de cette main gauche.

567
00:23:51,490 --> 00:23:54,015
>> Que serait une autre solution
à ce problème ont été?

568
00:23:54,015 --> 00:23:56,500
Si vous avez à remodeler les données
structure que nous parlons

569
00:23:56,500 --> 00:23:59,630
traverse en ce moment?

570
00:23:59,630 --> 00:24:02,690
Si ce genre de juste se sent un peu
ennuyeux d'avoir, comme, deux pointeurs

571
00:24:02,690 --> 00:24:08,430
en passant par la liste, qui d'autre pourrait
ont, dans un monde idéal, maintenu

572
00:24:08,430 --> 00:24:10,160
l'information dont nous avons besoin?

573
00:24:10,160 --> 00:24:11,360
Ouais?

574
00:24:11,360 --> 00:24:12,610
>> ETUDIANT: [inaudible].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> ENCEINTE 1: Exactement.

577
00:24:16,150 --> 00:24:19,130
Droit si il ya en fait un intéressant
germe d'une idée.

578
00:24:19,130 --> 00:24:22,470
Et cette idée d'un pointeur précédent,
pointant vers l'élément précédent.

579
00:24:22,470 --> 00:24:25,580
Que faire si je viens incarné qui
à l'intérieur de lui-même la liste?

580
00:24:25,580 --> 00:24:27,810
Et il va être difficile de visualiser
ceci sans tout le papier

581
00:24:27,810 --> 00:24:28,830
tomber au sol.

582
00:24:28,830 --> 00:24:31,860
Mais supposons que ces gars-là utilisés à la fois
de leurs mains pour avoir un précédent

583
00:24:31,860 --> 00:24:35,950
pointeur, et un pointeur suivant, ainsi
mise en œuvre de ce que nous appellerons un doublement

584
00:24:35,950 --> 00:24:36,830
liste chaînée.

585
00:24:36,830 --> 00:24:41,090
Cela me permettra sorte de retour en arrière,
beaucoup plus facilement sans moi, l'

586
00:24:41,090 --> 00:24:43,800
programmeur, d'avoir à garder
suivre manuellement -

587
00:24:43,800 --> 00:24:44,980
vraiment manuellement -

588
00:24:44,980 --> 00:24:47,280
de l'endroit où j'avais été précédemment
dans la liste.

589
00:24:47,280 --> 00:24:48,110
Donc, nous ne le ferons pas.

590
00:24:48,110 --> 00:24:50,950
Nous allons garder les choses simples parce que c'est
va venir à un prix deux fois plus

591
00:24:50,950 --> 00:24:53,450
beaucoup d'espace pour les pointeurs,
si vous voulez une deuxième.

592
00:24:53,450 --> 00:24:55,760
Mais c'est effectivement un commun
Structure de données connu en tant que

593
00:24:55,760 --> 00:24:57,410
doublement liste chaînée.

594
00:24:57,410 --> 00:25:01,310
>> Faisons le dernier exemple ici et mettre
ces gars sortir de leur misère.

595
00:25:01,310 --> 00:25:03,270
Alors malloc 20.

596
00:25:03,270 --> 00:25:05,320
Venez sur place à partir de l'allée là-bas.

597
00:25:05,320 --> 00:25:06,280
Bon, quel est votre nom?

598
00:25:06,280 --> 00:25:07,440
>> ETUDIANT: [inaudible].

599
00:25:07,440 --> 00:25:07,855
>> ENCEINTE 1: Pardon?

600
00:25:07,855 --> 00:25:08,480
>> ETUDIANT: [inaudible].

601
00:25:08,480 --> 00:25:09,410
>> INTERLOCUTEUR 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
OK venir sur place.

603
00:25:10,230 --> 00:25:11,910
Vous serez 20.

604
00:25:11,910 --> 00:25:14,720
Vous allez évidemment
appartiennent entre 17 et 22.

605
00:25:14,720 --> 00:25:16,150
Alors permettez-moi d'apprendre ma leçon.

606
00:25:16,150 --> 00:25:18,150
Je vais commencer à pointer
pointant à Brian.

607
00:25:18,150 --> 00:25:21,190
Et je vais avoir ma main gauche
seulement mettre à jour à Brian que je passe à

608
00:25:21,190 --> 00:25:23,600
Jason, le contrôle fait 20 moins de neuf?

609
00:25:23,600 --> 00:25:24,060
No.

610
00:25:24,060 --> 00:25:25,430
Est de 20 à moins de 17?

611
00:25:25,430 --> 00:25:25,880
No.

612
00:25:25,880 --> 00:25:27,450
Est de 20 à moins de 22?

613
00:25:27,450 --> 00:25:28,440
Oui.

614
00:25:28,440 --> 00:25:34,070
Alors qu'est-ce pointeurs ou les mains doivent changer
où ils pointant maintenant?

615
00:25:34,070 --> 00:25:37,070
>> Ainsi, nous pouvons faire 17 pointant à 20.

616
00:25:37,070 --> 00:25:37,860
Donc, c'est très bien.

617
00:25:37,860 --> 00:25:40,080
Où voulons-nous faire remarquer
votre pointeur maintenant?

618
00:25:40,080 --> 00:25:41,330
A 22 ans.

619
00:25:41,330 --> 00:25:45,410
Et nous savons où 22 est, encore une fois merci
à mon pointeur temporaire.

620
00:25:45,410 --> 00:25:46,760
Donc, nous sommes OK là.

621
00:25:46,760 --> 00:25:49,440
Donc à cause de ce stockage temporaire
J'ai gardé la trace de l'endroit où tout le monde est.

622
00:25:49,440 --> 00:25:55,055
Et maintenant, vous pouvez vous rendre visuellement dans laquelle
vous appartenez, et maintenant nous avons besoin de 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 boules d'effort,
et une salve d'applaudissements pour

624
00:25:58,410 --> 00:25:59,770
ces gars-là, si nous le pouvions.

625
00:25:59,770 --> 00:26:00,410
Bien fait.

626
00:26:00,410 --> 00:26:05,320
>> [Applaudissements]

627
00:26:05,320 --> 00:26:06,330
>> INTERLOCUTEUR 1: Très bien.

628
00:26:06,330 --> 00:26:09,860
Et vous pouvez garder les morceaux
de papier comme souvenirs.

629
00:26:09,860 --> 00:26:15,930
>> Très bien, alors, croyez-moi, c'est beaucoup
plus facile de marcher à travers ce avec

630
00:26:15,930 --> 00:26:17,680
l'homme qu'elle ne l'est avec le code réel.

631
00:26:17,680 --> 00:26:22,690
Mais ce que vous trouverez dans un instant
Maintenant, est-ce même - oh, merci.

632
00:26:22,690 --> 00:26:23,630
Merci -

633
00:26:23,630 --> 00:26:29,360
c'est que vous verrez que les mêmes données
la structure, une liste chaînée, peut effectivement

634
00:26:29,360 --> 00:26:33,200
être utilisée comme un bloc de construction à encore plus
des structures de données complexes.

635
00:26:33,200 --> 00:26:37,620
>> Et de réaliser aussi le thème ici est que
nous avons absolument introduit plus

636
00:26:37,620 --> 00:26:40,060
complexité dans la mise en œuvre
de cet algorithme.

637
00:26:40,060 --> 00:26:43,940
Insertion, et si nous sommes allés à travers elle,
suppression et la recherche, est un peu

638
00:26:43,940 --> 00:26:46,660
plus compliqué que cela
était avec un tableau.

639
00:26:46,660 --> 00:26:48,040
Mais nous gagnons un certain dynamisme.

640
00:26:48,040 --> 00:26:50,180
Nous obtenons une structure de données d'adaptation.

641
00:26:50,180 --> 00:26:54,010
>> Mais encore une fois, nous payons un prix d'avoir une certaine
complexité supplémentaire, à la fois dans

642
00:26:54,010 --> 00:26:54,910
sa mise en œuvre.

643
00:26:54,910 --> 00:26:56,750
Et on nous donne l'accès aléatoire.

644
00:26:56,750 --> 00:27:00,450
Et pour être honnête, il n'y a pas de belles
lame propre, je peux vous donner que

645
00:27:00,450 --> 00:27:03,120
dit ici, c'est pourquoi une liste chaînée
c'est mieux que un tableau.

646
00:27:03,120 --> 00:27:04,100
Et en rester là.

647
00:27:04,100 --> 00:27:07,520
Parce que le thème récurrent maintenant, même
d'autant plus dans les semaines à venir, est

648
00:27:07,520 --> 00:27:10,200
qu'il n'y a pas nécessairement
une réponse correcte.

649
00:27:10,200 --> 00:27:13,830
>> C'est pourquoi nous avons séparé l'axe
de la conception de séries de problèmes.

650
00:27:13,830 --> 00:27:17,700
Il sera très sensible au contexte
si vous souhaitez utiliser ces données

651
00:27:17,700 --> 00:27:21,750
structure ou de celui-là, et il sera
dépendra de ce qui compte pour vous en termes

652
00:27:21,750 --> 00:27:24,620
des ressources et de la complexité.

653
00:27:24,620 --> 00:27:28,830
>> Mais permettez-moi de proposer que les données idéales
la structure, le saint graal, serait

654
00:27:28,830 --> 00:27:32,200
quelque chose qui est constante de temps,
indépendamment de la quantité de choses est

655
00:27:32,200 --> 00:27:36,940
à l'intérieur, il ne serait pas étonnant si une
Structure de données renvoyé en réponse

656
00:27:36,940 --> 00:27:37,920
constante de temps.

657
00:27:37,920 --> 00:27:38,330
Oui.

658
00:27:38,330 --> 00:27:40,110
Ce mot est dans votre énorme dictionnaire.

659
00:27:40,110 --> 00:27:41,550
Ou non, ce mot n'est pas.

660
00:27:41,550 --> 00:27:43,270
Or un tel problème.

661
00:27:43,270 --> 00:27:46,360
Eh bien nous allons voir si nous ne pouvons pas au moins
faire un pas dans cette direction.

662
00:27:46,360 --> 00:27:50,190
>> Permettez-moi de proposer une nouvelle structure de données qui
peut être utilisé pour différentes choses,

663
00:27:50,190 --> 00:27:52,260
dans ce cas appelé une table de hachage.

664
00:27:52,260 --> 00:27:55,590
Et donc nous sommes en fait à en regardant
à une rangée, dans ce cas, et

665
00:27:55,590 --> 00:28:00,550
un peu arbitrairement, j'ai dessiné cette
table de hachage comme un tableau avec une sorte de

666
00:28:00,550 --> 00:28:02,810
tableau à deux dimensions -

667
00:28:02,810 --> 00:28:05,410
ou plutôt il est dépeint ici comme deux
matrice bidimensionnelle - mais c'est juste

668
00:28:05,410 --> 00:28:10,770
un tableau de taille 26, de sorte que si nous
appeler le tableau de tableau, le support de table

669
00:28:10,770 --> 00:28:12,440
zéro est le rectangle en haut.

670
00:28:12,440 --> 00:28:15,090
Support tableau 25 est le rectangle
au fond.

671
00:28:15,090 --> 00:28:18,620
Et voilà comment je pourrais tirer des données
structure dans laquelle je veux stocker

672
00:28:18,620 --> 00:28:19,790
noms des personnes.

673
00:28:19,790 --> 00:28:24,370
>> Ainsi, par exemple, et je ne vais pas attirer l'
Tout ça ici sur la tête, si je

674
00:28:24,370 --> 00:28:29,160
eu ce tableau, que je vais maintenant
appeler une table de hachage, ce qui est nouveau

675
00:28:29,160 --> 00:28:31,360
emplacement zéro.

676
00:28:31,360 --> 00:28:34,840
Cet emplacement est ici
une, et ainsi de suite.

677
00:28:34,840 --> 00:28:37,880
Je prétends que je veux utiliser ces données
la structure, pour les besoins du débat,

678
00:28:37,880 --> 00:28:42,600
pour stocker les noms des personnes, Alice et Bob
et Charlie et d'autres noms.

679
00:28:42,600 --> 00:28:46,110
Alors, pensez à ce moment que les débuts
de, disons, un dictionnaire

680
00:28:46,110 --> 00:28:47,520
avec beaucoup de mots.

681
00:28:47,520 --> 00:28:49,435
Ils ressemblent à des noms
dans notre exemple.

682
00:28:49,435 --> 00:28:52,560
Et c'est tout aussi pertinente, peut-être,
la mise en œuvre d'un correcteur orthographique, comme nous l'

683
00:28:52,560 --> 00:28:54,400
pourrait par problème posé six.

684
00:28:54,400 --> 00:28:59,300
>> Donc, si nous avons un tableau de taille total de 26
de sorte que c'est l'endroit 25e

685
00:28:59,300 --> 00:29:03,390
au fond, et je prétends que Alice est
le premier mot dans le dictionnaire d'

686
00:29:03,390 --> 00:29:07,260
Les noms que je veux insérer dans la RAM,
dans cette structure de données, où sont

687
00:29:07,260 --> 00:29:12,480
instincts vous disent que c'est Alice
nom devrait aller dans ce tableau?

688
00:29:12,480 --> 00:29:13,510
>> Nous avons 26 options.

689
00:29:13,510 --> 00:29:14,990
Lorsque nous voulons la mettre?

690
00:29:14,990 --> 00:29:16,200
Nous voulons qu'elle en support zéro, non?

691
00:29:16,200 --> 00:29:18,280
A pour Alice, appelons ça nul.

692
00:29:18,280 --> 00:29:20,110
Et B seront un, et C sera deux.

693
00:29:20,110 --> 00:29:22,600
Nous allons donc écrire
Le nom d'Alice ici.

694
00:29:22,600 --> 00:29:24,890
Si nous insérons Bob, son
nom sera ici.

695
00:29:24,890 --> 00:29:27,280
Charlie va aller ici.

696
00:29:27,280 --> 00:29:30,500
Et ainsi de suite à travers
cette structure de données.

697
00:29:30,500 --> 00:29:32,090
>> Il s'agit d'une structure de données merveilleux.

698
00:29:32,090 --> 00:29:32,730
Pourquoi?

699
00:29:32,730 --> 00:29:37,460
Eh bien, quelle est la durée de
insérer le nom d'un homme dans cette

700
00:29:37,460 --> 00:29:39,850
structure de données en ce moment?

701
00:29:39,850 --> 00:29:43,702
Étant donné que ce tableau est mis en œuvre,
vraiment, comme un tableau.

702
00:29:43,702 --> 00:29:44,940
Eh bien il est temps constant.

703
00:29:44,940 --> 00:29:45,800
C'est l'ordre d'un.

704
00:29:45,800 --> 00:29:46,360
Pourquoi?

705
00:29:46,360 --> 00:29:48,630
>> Eh bien, comment déterminez-vous
où Alice appartient?

706
00:29:48,630 --> 00:29:51,000
Vous regardez quelle lettre de son nom?

707
00:29:51,000 --> 00:29:51,490
La première.

708
00:29:51,490 --> 00:29:54,350
Et vous pouvez y arriver, si c'est une chaîne,
simplement en regardant chaîne

709
00:29:54,350 --> 00:29:55,200
Support zéro.

710
00:29:55,200 --> 00:29:57,110
Ainsi, le caractère zéro de la chaîne.

711
00:29:57,110 --> 00:29:57,610
C'est facile.

712
00:29:57,610 --> 00:30:00,350
Nous l'avons fait dans la crypto
il ya des semaines d'affectation.

713
00:30:00,350 --> 00:30:05,310
Et puis une fois que vous savez que Alice
lettre majuscule A, nous pouvons soustraire

714
00:30:05,310 --> 00:30:08,160
off 65 ou au capital A lui-même,
qui nous donne zéro.

715
00:30:08,160 --> 00:30:10,940
Donc, nous savons maintenant que Alice appartient
au lieu de zéro.

716
00:30:10,940 --> 00:30:14,240
>> Et d'un pointeur sur ces données
la structure, en quelque sorte, combien de temps

717
00:30:14,240 --> 00:30:18,840
faut-il pour trouver l'emplacement
zéro dans un tableau?

718
00:30:18,840 --> 00:30:22,080
Juste une seule étape, à droite Il est temps constant
en raison de la vive nous

719
00:30:22,080 --> 00:30:23,780
proposée était une caractéristique d'un tableau.

720
00:30:23,780 --> 00:30:28,570
Donc en bref, comprendre ce que l'indice
du nom d'Alice, qui est, en

721
00:30:28,570 --> 00:30:32,610
ce cas est A, ou disons simplement résoudre
que à zéro, où B est un et C est

722
00:30:32,610 --> 00:30:34,900
deux, pensant que les
est la constante de temps.

723
00:30:34,900 --> 00:30:38,510
J'ai juste à regarder sa première lettre,
déterminer où zéro est une

724
00:30:38,510 --> 00:30:40,460
tableau est également constante de temps.

725
00:30:40,460 --> 00:30:42,140
Donc, techniquement c'est
comme deux mesures dès maintenant.

726
00:30:42,140 --> 00:30:43,330
Mais c'est toujours constant.

727
00:30:43,330 --> 00:30:46,880
Nous appelons donc ce grand O d'un seul, c'est pourquoi nous avons
Alice inséré dans ce tableau en

728
00:30:46,880 --> 00:30:48,440
constante de temps.

729
00:30:48,440 --> 00:30:50,960
>> Mais bien sûr, je vais être
naïf ici, non?

730
00:30:50,960 --> 00:30:53,240
Que faire si il ya une Aaron dans la classe?

731
00:30:53,240 --> 00:30:53,990
Ou Alicia?

732
00:30:53,990 --> 00:30:57,230
Ou tous les autres noms commençant par
A. Où allons-nous mettre

733
00:30:57,230 --> 00:31:00,800
que personne, pas vrai?

734
00:31:00,800 --> 00:31:03,420
Je veux dire, en ce moment il ya seulement trois
les gens sur la table, alors peut-être nous

735
00:31:03,420 --> 00:31:07,490
devrait mettre Aaron au lieu
zéro un deux trois.

736
00:31:07,490 --> 00:31:09,480
>> Bon, je pourrais mettre un ici.

737
00:31:09,480 --> 00:31:13,350
Mais alors, si on cherche à insérer dans David
cette liste, où ne vont David?

738
00:31:13,350 --> 00:31:15,170
Maintenant, notre système commence à casser
en bas, à droite?

739
00:31:15,170 --> 00:31:19,210
Parce que maintenant, David finit ici
si Aaron est en fait ici.

740
00:31:19,210 --> 00:31:23,060
Et maintenant cette idée d'avoir un
structure de données propre qui nous donne

741
00:31:23,060 --> 00:31:28,010
insertions de temps constants n'est plus
constante de temps, parce que je dois

742
00:31:28,010 --> 00:31:31,240
vérifier, oh, merde, quelqu'un est déjà
à l'emplacement d'Alice.

743
00:31:31,240 --> 00:31:35,320
>> Permettez-moi de sonder le reste de ces données
la structure, à la recherche d'un endroit pour mettre

744
00:31:35,320 --> 00:31:37,130
quelqu'un comme le nom d'Aaron.

745
00:31:37,130 --> 00:31:39,390
Et cela aussi est en train
prendre le temps linéaire.

746
00:31:39,390 --> 00:31:42,710
En outre, si vous voulez maintenant de trouver le
Aaron dans cette structure de données, et on

747
00:31:42,710 --> 00:31:45,430
vérifier, et le nom d'Aaron n'est pas ici.

748
00:31:45,430 --> 00:31:47,960
Idéalement, vous voulez juste dire Aaron
pas dans la structure de données.

749
00:31:47,960 --> 00:31:51,530
Mais si vous ne commencez à faire de la place pour
Aaron où il aurait dû être un D

750
00:31:51,530 --> 00:31:55,600
ou un E, vous, le pire des cas, vérifiez
la structure de données tout en

751
00:31:55,600 --> 00:31:59,480
auquel cas il incombe en quelque chose
linéaire dans la taille de la table.

752
00:31:59,480 --> 00:32:00,920
>> Alors bon, je vais arranger ça.

753
00:32:00,920 --> 00:32:04,200
Le problème ici, c'est que j'avais
26 éléments dans ce tableau.

754
00:32:04,200 --> 00:32:05,000
Permettez-moi de le changer.

755
00:32:05,000 --> 00:32:06,010
Oups.

756
00:32:06,010 --> 00:32:10,600
Permettez-moi de le modifier de sorte que, au lieu d'être des
taille 26 au total, notez le fond

757
00:32:10,600 --> 00:32:12,720
index va changer à n moins 1.

758
00:32:12,720 --> 00:32:16,610
Si 26 est clairement trop petit pour l'homme »
noms, parce qu'il ya des milliers d'

759
00:32:16,610 --> 00:32:20,830
noms du monde, nous allons juste faire
en 100 ou 1000 ou 10000.

760
00:32:20,830 --> 00:32:22,960
Disons simplement allouer beaucoup plus d'espace.

761
00:32:22,960 --> 00:32:27,230
>> Bien que ne diminue pas nécessairement
la probabilité que nous n'aurons pas deux

762
00:32:27,230 --> 00:32:31,510
personnes avec des noms commençant par A, et
Ainsi, vous alliez essayer de mettre un

763
00:32:31,510 --> 00:32:33,120
noms au lieu de zéro encore.

764
00:32:33,120 --> 00:32:36,850
Ils vont quand même entrer en collision, ce qui
signifie que nous avons encore besoin d'une solution pour mettre

765
00:32:36,850 --> 00:32:41,020
Alice et Aaron et Alicia et autres
des noms commençant par A d'ailleurs.

766
00:32:41,020 --> 00:32:43,460
Mais combien d'un problème est le suivant?

767
00:32:43,460 --> 00:32:46,870
Quelle est la probabilité que vous
avoir des collisions dans un ensemble de données

768
00:32:46,870 --> 00:32:48,240
structure de ce type?

769
00:32:48,240 --> 00:32:52,570
>> Eh bien, permettez-moi - nous reviendrons
à cette question ici.

770
00:32:52,570 --> 00:32:55,530
Et regardez comment nous pourrions
résoudre en premier.

771
00:32:55,530 --> 00:32:58,480
Laisse-moi ôter cette proposition ici.

772
00:32:58,480 --> 00:33:02,020
Ce que nous venons de décrire est un algorithme,
une heuristique appelée linéaire

773
00:33:02,020 --> 00:33:05,030
sondage dans lequel, si vous avez essayé d'insérer
quelque chose dans ces données

774
00:33:05,030 --> 00:33:08,920
la structure, qui est appelé une table de hachage,
et il n'y a pas de place là-bas, vous

775
00:33:08,920 --> 00:33:12,000
véritablement sonder la structure de données
vérification, est-ce disponible?

776
00:33:12,000 --> 00:33:13,430
Est-ce disponible est cette disposition?

777
00:33:13,430 --> 00:33:13,980
Est-ce disponible?

778
00:33:13,980 --> 00:33:17,550
Et quand il est enfin, vous insérez le
nom que vous avez initialement prévu

779
00:33:17,550 --> 00:33:19,370
d'ailleurs à cet endroit.

780
00:33:19,370 --> 00:33:23,360
Mais dans le pire des cas, le seul endroit
pourrait être le fond même des données

781
00:33:23,360 --> 00:33:25,090
la structure, la fin du tableau.

782
00:33:25,090 --> 00:33:30,130
>> Alors linéaire sondage, dans le pire des cas,
dégénérait en un algorithme linéaire où

783
00:33:30,130 --> 00:33:34,500
Aaron, s'il arrive à être inséré dernier
dans cette structure de données, il pourrait

784
00:33:34,500 --> 00:33:39,540
entrer en collision avec ce premier emplacement, mais
puis terminer par la malchance à la toute fin.

785
00:33:39,540 --> 00:33:43,940
Ce n'est donc pas une constante
temps graal pour nous.

786
00:33:43,940 --> 00:33:47,650
Cette approche de l'insertion des éléments dans
une structure de données appelée un hachage

787
00:33:47,650 --> 00:33:52,050
tableau ne semble pas être la constante de temps
du moins pas dans le cas général.

788
00:33:52,050 --> 00:33:54,000
Il peut dégénérer en quelque chose de linéaire.

789
00:33:54,000 --> 00:33:56,970
>> Alors que faire si nous résolvons collisions
un peu différemment?

790
00:33:56,970 --> 00:34:00,740
Alors, voici un plus sophistiqué
approcher de ce qui est encore

791
00:34:00,740 --> 00:34:02,800
appelée une table de hachage.

792
00:34:02,800 --> 00:34:05,890
Et par hachage, en aparté, que
Je veux dire, c'est l'indice que

793
00:34:05,890 --> 00:34:07,070
J'ai parlé plus tôt.

794
00:34:07,070 --> 00:34:09,810
Pour quelque chose de hachage peut être
considéré comme un verbe.

795
00:34:09,810 --> 00:34:13,690
>> Donc, si vous hachage Alice c'est un nom,
une fonction de hachage, pour ainsi dire,

796
00:34:13,690 --> 00:34:14,710
doit retourner un nombre.

797
00:34:14,710 --> 00:34:18,199
Dans ce cas, est nulle si elle appartient à
emplacement zéro, un, si elle appartient à

798
00:34:18,199 --> 00:34:20,000
une localisation, et ainsi de suite.

799
00:34:20,000 --> 00:34:24,360
Donc, ma fonction de hachage a été jusqu'ici
super simple, uniquement en regardant le

800
00:34:24,360 --> 00:34:26,159
première lettre du nom de quelqu'un.

801
00:34:26,159 --> 00:34:29,090
Mais une fonction de hachage prend comme
entrée un morceau de données, un

802
00:34:29,090 --> 00:34:30,210
chaîne, un int, peu importe.

803
00:34:30,210 --> 00:34:32,239
Et il crache généralement un certain nombre.

804
00:34:32,239 --> 00:34:35,739
Et ce nombre est l'endroit où ces données
élément appartient à une structure de données

805
00:34:35,739 --> 00:34:37,800
connu ici comme une table de hachage.

806
00:34:37,800 --> 00:34:41,400
>> Il suffit donc de manière intuitive, c'est un
contexte légèrement différent.

807
00:34:41,400 --> 00:34:44,170
Cette réalité se réfère à un exemple
impliquant des anniversaires, le cas

808
00:34:44,170 --> 00:34:46,850
il pourrait y avoir le plus grand nombre
31 jours dans le mois.

809
00:34:46,850 --> 00:34:52,239
Mais qu'est-ce que cette personne décide d'
faire dans le cas d'une collision?

810
00:34:52,239 --> 00:34:55,304
Contexte être maintenant, pas une collision
noms, mais une collision anniversaires,

811
00:34:55,304 --> 00:35:00,760
Si deux personnes ont le même anniversaire sur
Le 2 Octobre, par exemple.

812
00:35:00,760 --> 00:35:02,120
>> ETUDIANT: [inaudible].

813
00:35:02,120 --> 00:35:05,010
>> INTERLOCUTEUR 1: Ouais, donc nous avons ici
la mise à profit des listes chaînées.

814
00:35:05,010 --> 00:35:07,830
Ainsi, il semble un peu différemment
que nous avons tiré plus tôt.

815
00:35:07,830 --> 00:35:10,790
Mais nous semblons avoir à un tableau
sur le côté gauche.

816
00:35:10,790 --> 00:35:13,230
C'est un indice, sans
raison particulière.

817
00:35:13,230 --> 00:35:14,630
Mais c'est toujours un tableau.

818
00:35:14,630 --> 00:35:16,160
C'est un tableau de pointeurs.

819
00:35:16,160 --> 00:35:20,670
Et chacun de ces éléments, chacun de
ces cercles ou des barres obliques - La barre oblique

820
00:35:20,670 --> 00:35:23,970
soit nulle - chacune de ces
pointeurs est apparemment pointant vers

821
00:35:23,970 --> 00:35:25,730
quelle structure de données?

822
00:35:25,730 --> 00:35:26,890
Une liste chaînée.

823
00:35:26,890 --> 00:35:30,530
>> Alors maintenant, nous avons la capacité de
coder en dur dans notre programme

824
00:35:30,530 --> 00:35:32,010
la taille de la table.

825
00:35:32,010 --> 00:35:35,360
Dans ce cas, nous savons qu'il ya jamais
plus de 31 jours à un mois.

826
00:35:35,360 --> 00:35:38,480
Donc, le codage en dur une valeur comme 31 est
raisonnable dans ce contexte.

827
00:35:38,480 --> 00:35:42,700
Dans le cadre de noms, le codage en dur
26 n'est pas déraisonnable Ce sont des gens

828
00:35:42,700 --> 00:35:46,340
Les noms ne commencent avec, par exemple,
l'alphabet impliquant de A à Z.

829
00:35:46,340 --> 00:35:50,180
>> Nous pouvons entasser tous dans ces données
Structure tant que, lorsque nous aurons une

830
00:35:50,180 --> 00:35:55,330
collision, nous ne mettons pas les noms ici,
nous pensons que la place de ces cellules

831
00:35:55,330 --> 00:36:00,270
pas comme des chaînes elles-mêmes, mais aussi
pointeurs vers, par exemple, Alice.

832
00:36:00,270 --> 00:36:03,660
Et puis Alice peut avoir un autre pointeur
à un autre nom commençant par

833
00:36:03,660 --> 00:36:06,150
A. Et Bob va réellement ici.

834
00:36:06,150 --> 00:36:10,850
>> Et si il ya un autre nom commence
avec B, il se retrouve ici.

835
00:36:10,850 --> 00:36:15,070
Et ainsi de chacun des éléments de cette
tableau à deux, si nous avons conçu ce une

836
00:36:15,070 --> 00:36:17,350
peu plus intelligemment -

837
00:36:17,350 --> 00:36:18,125
s'allumer -

838
00:36:18,125 --> 00:36:22,950
si nous avons conçu ce un peu plus
habilement, devient maintenant une donnée adaptatifs

839
00:36:22,950 --> 00:36:27,720
la structure, où il n'ya pas de limite stricte
sur le nombre d'éléments que vous pouvez insérer

840
00:36:27,720 --> 00:36:30,700
en elle, parce que si vous n'avez
une collision, c'est très bien.

841
00:36:30,700 --> 00:36:34,690
Il suffit d'aller de l'avant et l'annexer au
ce que nous avons vu il ya un peu était

842
00:36:34,690 --> 00:36:38,290
connue sous le nom d'une liste liée.

843
00:36:38,290 --> 00:36:39,690
>> Eh bien nous allons mettre en pause pendant un moment.

844
00:36:39,690 --> 00:36:42,570
Quelle est la probabilité d'une collision
en premier lieu?

845
00:36:42,570 --> 00:36:45,480
A droite, je suis peut plus penser, peut-être
Je suis sur les directions techniques à ce problème,

846
00:36:45,480 --> 00:36:46,370
parce que vous savez quoi?

847
00:36:46,370 --> 00:36:49,070
Oui, je peux venir avec arbitraire
exemples sur le dessus de ma tête comme

848
00:36:49,070 --> 00:36:52,870
Allison et Aaron, mais en réalité,
compte tenu d'une distribution uniforme de

849
00:36:52,870 --> 00:36:56,990
entrées, soit des insertions aléatoires
dans une structure de données, ce qui est vraiment

850
00:36:56,990 --> 00:36:58,580
la probabilité d'une collision?

851
00:36:58,580 --> 00:37:01,670
Bien s'avère, il s'agit en fait
très élevé.

852
00:37:01,670 --> 00:37:03,850
Permettez-moi de généraliser cette
problème, c'est que cela.

853
00:37:03,850 --> 00:37:08,890
>> Donc, dans une chambre de n CS50 étudiants, ce qui est
la probabilité qu'au moins

854
00:37:08,890 --> 00:37:11,010
deux élèves dans la salle
avoir la même date d'anniversaire?

855
00:37:11,010 --> 00:37:13,346
Donc, il ya quoi. quelques Hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 gens d'ici et plusieurs
centaine de personnes à la maison aujourd'hui.

857
00:37:16,790 --> 00:37:20,670
Donc, si vous vouliez nous demander ce que c'est
la probabilité que deux personnes

858
00:37:20,670 --> 00:37:23,930
dans cette pièce ayant la même date d'anniversaire,
nous pouvons comprendre cela.

859
00:37:23,930 --> 00:37:26,250
Et je prétends fait il ya deux
les personnes ayant la même date d'anniversaire.

860
00:37:26,250 --> 00:37:29,560
>> Par exemple, personne ne
avoir anniversaire aujourd'hui?

861
00:37:29,560 --> 00:37:31,340
Hier?

862
00:37:31,340 --> 00:37:32,590
Demain?

863
00:37:32,590 --> 00:37:35,980
D'accord, donc il se sent comme je vais
d'avoir à faire ce 363 ou plus si

864
00:37:35,980 --> 00:37:39,500
fois pour réellement comprendre
Si nous avons une collision.

865
00:37:39,500 --> 00:37:42,350
Ou on pourrait faire cela mathématiquement
plutôt que péniblement

866
00:37:42,350 --> 00:37:43,200
faire.

867
00:37:43,200 --> 00:37:44,500
Et proposer ce qui suit.

868
00:37:44,500 --> 00:37:48,740
>> Je propose donc que nous pourrions modéliser l'
probabilité de deux personnes ayant le

869
00:37:48,740 --> 00:37:55,320
même jour que la probabilité de 1
moins la probabilité de personne ayant

870
00:37:55,320 --> 00:37:56,290
le même anniversaire.

871
00:37:56,290 --> 00:37:59,960
Donc, pour obtenir cela, et ce n'est que le
façon élégante de la rédaction du présent, pour l'

872
00:37:59,960 --> 00:38:03,090
première personne dans la chambre, il ou elle
peut avoir l'une quelconque de la possible

873
00:38:03,090 --> 00:38:07,370
anniversaires supposant 365 jours de l'année,
avec mes excuses aux personnes atteintes

874
00:38:07,370 --> 00:38:08,760
le 29e anniversaire Février.

875
00:38:08,760 --> 00:38:13,470
>> Donc, la première personne dans cette salle est libre
d'avoir un certain nombre de anniversaires

876
00:38:13,470 --> 00:38:18,280
sur les 365 possibilités afin que
nous ferons ce que 365 divisé par 365,

877
00:38:18,280 --> 00:38:18,990
qui est une.

878
00:38:18,990 --> 00:38:22,700
La prochaine personne dans la salle, si l'objectif
est d'éviter une collision, ne peut

879
00:38:22,700 --> 00:38:26,460
avoir son anniversaire sur la façon
plusieurs jours possibles?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Donc, le deuxième terme de cette expression est
faisant essentiellement que les maths pour nous

882
00:38:31,430 --> 00:38:33,460
en soustrayant off un jour possible.

883
00:38:33,460 --> 00:38:36,390
Et puis, le lendemain, le lendemain, l'
lendemain vers le bas pour le nombre total

884
00:38:36,390 --> 00:38:38,100
de personnes dans la salle.

885
00:38:38,100 --> 00:38:41,290
>> Et si l'on considère alors, quel est alors
la probabilité de ne pas avoir tout le monde

886
00:38:41,290 --> 00:38:45,265
anniversaires uniques, mais encore une fois 1 moins
que, ce que nous obtenons est une expression

887
00:38:45,265 --> 00:38:47,810
qui peut très fantaisiste
ressembler à ceci.

888
00:38:47,810 --> 00:38:50,330
Mais il est plus intéressant
d'examiner visuellement.

889
00:38:50,330 --> 00:38:55,120
Il s'agit d'un tableau où sur l'axe des x est
le nombre de personnes dans la salle, l'

890
00:38:55,120 --> 00:38:56,180
nombre d'anniversaires.

891
00:38:56,180 --> 00:38:59,840
Sur l'axe des y est la probabilité
d'une collision, deux personnes

892
00:38:59,840 --> 00:39:01,230
ayant la même date d'anniversaire.

893
00:39:01,230 --> 00:39:05,020
>> Et les plats à emporter à partir de cette courbe est
que, dès que vous arrivez à comme 40

894
00:39:05,020 --> 00:39:11,110
étudiants, vous êtes-vous à une probabilité de 90%
combinatorically des deux

895
00:39:11,110 --> 00:39:13,550
personnes ou plus ayant
le même anniversaire.

896
00:39:13,550 --> 00:39:18,600
Et une fois que vous arrivez à 58 personnes comme il est
près de 100% de chance les deux

897
00:39:18,600 --> 00:39:21,310
personnes dans la salle vont avoir la
même anniversaire, même si il ya

898
00:39:21,310 --> 00:39:26,650
365 ou 366 seaux possibles, et
seulement 58 personnes dans la salle.

899
00:39:26,650 --> 00:39:29,900
Juste statistiquement vous êtes susceptible d'
obtenir collisions, qui en bref

900
00:39:29,900 --> 00:39:31,810
motive cette discussion.

901
00:39:31,810 --> 00:39:35,890
Que même si nous obtenons de fantaisie ici, et
commencez à avoir ces chaînes, nous sommes encore

902
00:39:35,890 --> 00:39:36,950
va avoir collisions.

903
00:39:36,950 --> 00:39:42,710
>> Alors que se poser la question, quel est le
coût de faire des insertions et des suppressions

904
00:39:42,710 --> 00:39:44,850
dans une structure de données comme ça?

905
00:39:44,850 --> 00:39:46,630
Eh bien laissez-moi vous proposer -

906
00:39:46,630 --> 00:39:51,570
et permettez-moi de revenir à l'écran sur
ici - si nous avons des éléments N dans le

907
00:39:51,570 --> 00:39:56,330
liste, donc si nous essayons d'insérer
n éléments, et nous avons

908
00:39:56,330 --> 00:39:58,050
combien au total seaux?

909
00:39:58,050 --> 00:40:03,450
Disons total de 31 seaux
dans le cas des anniversaires.

910
00:40:03,450 --> 00:40:09,240
Quelle est la longueur maximale d'un
de ces chaînes potentiellement?

911
00:40:09,240 --> 00:40:12,670
>> Si encore il ya 31 possible
anniversaires dans un mois donné.

912
00:40:12,670 --> 00:40:14,580
Et nous sommes en train de s'agglutiner tout le monde -

913
00:40:14,580 --> 00:40:15,580
En fait, c'est un exemple stupide.

914
00:40:15,580 --> 00:40:16,960
Faisons 26 place.

915
00:40:16,960 --> 00:40:20,890
Donc, si effectivement avoir des personnes dont les noms
commencer par A à Z, donnant ainsi

916
00:40:20,890 --> 00:40:22,780
nous 26 possibilités.

917
00:40:22,780 --> 00:40:25,920
Et nous utilisons une structure de données comme
celle que nous venons de voir, par lequel nous avons

918
00:40:25,920 --> 00:40:30,210
un tableau de pointeurs, dont chacun
pointe vers une liste liée, où l'

919
00:40:30,210 --> 00:40:32,360
première liste est tout le monde
avec le nom Alice.

920
00:40:32,360 --> 00:40:35,770
La deuxième liste est tout à l'
le nom commence par A, à partir

921
00:40:35,770 --> 00:40:36,980
avec B, et ainsi de suite.

922
00:40:36,980 --> 00:40:41,020
>> Quelle est la durée probable de chacune des
ces listes si l'on suppose un bien propre

923
00:40:41,020 --> 00:40:45,410
Répartition des noms de A à Z
à travers la structure de données entier?

924
00:40:45,410 --> 00:40:50,210
Il ya n personnes dans la structure de données
divisé par 26, si elles sont bien

925
00:40:50,210 --> 00:40:52,110
étaler sur toute
la structure de données.

926
00:40:52,110 --> 00:40:54,970
Ainsi, la longueur de chacun de ceux-ci
chaînes est n divisé par 26.

927
00:40:54,970 --> 00:40:57,380
Mais en gros notation O, c'est quoi?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Qu'est ce que c'est vraiment?

930
00:41:02,440 --> 00:41:04,150
Donc, c'est vraiment juste n, non?

931
00:41:04,150 --> 00:41:06,620
Parce que nous avons dit dans le passé,
ugh que vous divisez par 26.

932
00:41:06,620 --> 00:41:08,710
Oui, en réalité, il est plus rapide.

933
00:41:08,710 --> 00:41:12,720
Mais en théorie, il n'est pas fondamentalement
tout cela rapidement.

934
00:41:12,720 --> 00:41:16,040
>> Donc, nous ne semblons pas être tant que ça
rapprocher de ce Saint-Graal.

935
00:41:16,040 --> 00:41:17,750
En fait, c'est juste le temps linéaire.

936
00:41:17,750 --> 00:41:20,790
Heck, à ce point, pourquoi ne pas nous
il suffit d'utiliser une énorme liste chaînée?

937
00:41:20,790 --> 00:41:23,510
Pourquoi ne pas simplement utiliser un énorme
tableau pour stocker les noms des

938
00:41:23,510 --> 00:41:25,010
tout le monde dans la salle?

939
00:41:25,010 --> 00:41:28,280
Eh bien, est-il encore quelque chose
convaincant sur une table de hachage?

940
00:41:28,280 --> 00:41:30,810
Est-il encore quelque chose de convaincant
sur une structure de données

941
00:41:30,810 --> 00:41:33,940
qui ressemble à ceci?

942
00:41:33,940 --> 00:41:35,182
Cette.

943
00:41:35,182 --> 00:41:37,050
>> ETUDIANT: [inaudible].

944
00:41:37,050 --> 00:41:39,840
>> ENCEINTE 1: Oui, et encore si c'est juste
un algorithme en temps linéaire, et un

945
00:41:39,840 --> 00:41:42,780
la structure de données en temps linéaire, pourquoi ne pas
simplement stocker le nom de tout le monde dans une grande

946
00:41:42,780 --> 00:41:44,210
tableau ou dans une grande liste chaînée?

947
00:41:44,210 --> 00:41:47,010
Et cesser de faire des CS d'autant plus difficile
qu'elle doit être?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Ce qui est convaincant à ce sujet, même
si j'ai gratté it out?

950
00:41:53,190 --> 00:41:54,930
>> ETUDIANT: [inaudible].

951
00:41:54,930 --> 00:41:57,040
>> INTERLOCUTEUR 1: insertions ne sont pas?

952
00:41:57,040 --> 00:41:58,140
Plus cher.

953
00:41:58,140 --> 00:42:03,390
Alors insertions potentiellement pourrait encore
être constante de temps, même si vos données

954
00:42:03,390 --> 00:42:07,910
la structure ressemble à ceci, un tableau de
pointeurs, dont chacun est dirigé vers

955
00:42:07,910 --> 00:42:09,550
éventuellement une liste chaînée.

956
00:42:09,550 --> 00:42:15,220
Comment pourriez-vous réaliser constant
insertion de temps de noms?

957
00:42:15,220 --> 00:42:16,280
Collez-le sur le devant, à droite?

958
00:42:16,280 --> 00:42:19,290
>> Si nous sacrifions un objectif de conception de
plus tôt, là où nous voulions garder

959
00:42:19,290 --> 00:42:22,650
Le nom de tout le monde, par exemple, triée,
ou tous les numéros sur scène triés,

960
00:42:22,650 --> 00:42:25,020
Supposons que nous avons une
non triés liste chaînée.

961
00:42:25,020 --> 00:42:29,960
Il ne nous coûte une ou deux étapes,
comme dans le cas de Ben et Brian

962
00:42:29,960 --> 00:42:32,750
précédemment, à insérer un élément à
le début de la liste.

963
00:42:32,750 --> 00:42:36,090
Donc, si nous ne nous préoccupons pas de tri tous
des noms commençant par A ou tout

964
00:42:36,090 --> 00:42:39,660
les noms commençant par B, nous pouvons encore
atteindre insertion de temps constant.

965
00:42:39,660 --> 00:42:43,900
Maintenant regardant Alice ou Bob ou tout autre nom
plus généralement est encore quoi?

966
00:42:43,900 --> 00:42:48,100
Il est grand O de n divisé par 26, dans le
cas idéal où tout le monde est uniformément

967
00:42:48,100 --> 00:42:51,190
distribué, où il ya le plus grand nombre de A
car il ya de Z, qui est probablement

968
00:42:51,190 --> 00:42:52,220
irréaliste.

969
00:42:52,220 --> 00:42:53,880
Mais c'est toujours linéaire.

970
00:42:53,880 --> 00:42:57,120
>> Mais ici, nous revenons au point
de notation asymptotique être

971
00:42:57,120 --> 00:42:58,600
théoriquement vrai.

972
00:42:58,600 --> 00:43:02,960
Mais dans le monde réel, si je prétends que
mon programme peut faire quelque chose 26 fois

973
00:43:02,960 --> 00:43:06,210
plus rapide que le vôtre, dont le programme
allez-vous préférer utiliser?

974
00:43:06,210 --> 00:43:09,660
La vôtre ou la mienne, qui
est 26 fois plus rapide?

975
00:43:09,660 --> 00:43:14,320
De façon réaliste, la personne dont est 26
fois plus rapide, même si théoriquement

976
00:43:14,320 --> 00:43:18,790
nos algorithmes fonctionnent de la même
asymptotique temps d'exécution.

977
00:43:18,790 --> 00:43:20,940
>> Permettez-moi de proposer un autre
solution tout à fait.

978
00:43:20,940 --> 00:43:24,380
Et si cela ne veut pas souffler votre esprit,
nous sommes hors des structures de données.

979
00:43:24,380 --> 00:43:27,420
Alors c'est un trie -

980
00:43:27,420 --> 00:43:28,520
genre d'un nom stupide.

981
00:43:28,520 --> 00:43:32,880
Il vient de récupérations, et le mot
est orthographié trie, t-r-i-e, en raison de

982
00:43:32,880 --> 00:43:34,450
récupération de cours ressemble à Trie.

983
00:43:34,450 --> 00:43:36,580
Mais c'est l'histoire
du mot trie.

984
00:43:36,580 --> 00:43:40,980
>> Donc un trie est en effet un certain type d'arbre,
et c'est aussi un jeu de ce mot.

985
00:43:40,980 --> 00:43:46,330
Et même si vous ne pouvez pas tout voir
avec cette visualisation, une trie est un

986
00:43:46,330 --> 00:43:50,790
arbre structuré comme un arbre généalogique avec
un ancêtre dans la partie supérieure et beaucoup

987
00:43:50,790 --> 00:43:54,530
des petits-enfants et arrière-petits-
Comme les feuilles sur le fond.

988
00:43:54,530 --> 00:43:58,100
Mais chaque noeud dans un trie est un tableau.

989
00:43:58,100 --> 00:44:00,680
Et c'est dans un tableau - et LET'S
simplifier à l'extrême pour un moment - c'est un

990
00:44:00,680 --> 00:44:04,600
tableau, dans ce cas, de taille 26, où
chaque nœud est à nouveau un tableau de taille

991
00:44:04,600 --> 00:44:09,000
26, où l'élément de rang zéro en ce que
matrice représente A, et le dernier

992
00:44:09,000 --> 00:44:11,810
élément dans chacun de ces
tableau représente Z.

993
00:44:11,810 --> 00:44:15,520
>> Je propose donc que ces données
la structure, connue comme une structure arborescente, peut être

994
00:44:15,520 --> 00:44:17,600
utilisé également pour stocker les mots.

995
00:44:17,600 --> 00:44:21,740
Nous avons vu il ya un instant comment nous pourrions stocker
mots, ou dans ce cas les noms, et nous

996
00:44:21,740 --> 00:44:25,440
vu plus haut comment nous pouvons stocker des nombres,
mais si nous nous concentrons sur des noms ou des chaînes

997
00:44:25,440 --> 00:44:27,460
ici, notez ce qui est intéressant.

998
00:44:27,460 --> 00:44:32,210
Je prétends que le nom Maxwell est
à l'intérieur de cette structure de données.

999
00:44:32,210 --> 00:44:33,730
Où voyez-vous Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> ETUDIANT: [inaudible].

1001
00:44:35,140 --> 00:44:36,240
>> INTERLOCUTEUR 1: Sur la gauche.

1002
00:44:36,240 --> 00:44:39,910
Donc ce qui est intéressant avec ces données
structure est plutôt que de stocker l'

1003
00:44:39,910 --> 00:44:46,200
chaîne M-A-X-W-E-L-L oblique zéro, tout
contiguë, ce que vous faites place

1004
00:44:46,200 --> 00:44:46,890
est la suite.

1005
00:44:46,890 --> 00:44:50,510
Si c'est un trie comme structure de données,
chacun des nœuds dont est encore un tableau,

1006
00:44:50,510 --> 00:44:54,650
et vous voulez stocker Maxwell, vous devez d'abord
index et ainsi de noeud de la racine, de sorte

1007
00:44:54,650 --> 00:44:57,810
parler, le nœud le plus haut,
à l'emplacement M, à droite, de sorte

1008
00:44:57,810 --> 00:44:59,160
à peu près dans la moyenne.

1009
00:44:59,160 --> 00:45:03,740
Et puis à partir de là, vous suivez un
pointeur à un enfant nœuds, pour ainsi dire.

1010
00:45:03,740 --> 00:45:06,150
Ainsi, dans le sens de l'arbre généalogique,
vous suivez le bas.

1011
00:45:06,150 --> 00:45:09,030
Et qui vous mènera vers un autre nœud
sur la gauche, il ya, ce qui est

1012
00:45:09,030 --> 00:45:10,540
juste un autre tableau.

1013
00:45:10,540 --> 00:45:14,710
>> Et puis si vous voulez stocker Maxwell,
vous trouverez le pointeur qui représente

1014
00:45:14,710 --> 00:45:16,430
A, qui est celui-là.

1015
00:45:16,430 --> 00:45:17,840
Ensuite, vous passez au nœud suivant.

1016
00:45:17,840 --> 00:45:20,100
Et remarquez - c'est pourquoi le tableau de
un peu décevant -

1017
00:45:20,100 --> 00:45:21,990
ce nœud super look minuscule.

1018
00:45:21,990 --> 00:45:26,050
Mais à droite de cette est Y et Z.
C'est juste l'auteur a tronqué

1019
00:45:26,050 --> 00:45:27,630
image de sorte que vous avez réellement
voir les choses.

1020
00:45:27,630 --> 00:45:30,400
Sinon cette image
serait extrêmement large.

1021
00:45:30,400 --> 00:45:36,180
Alors maintenant, vous indice dans l'emplacement X, puis
W, E, puis L, puis L. Ensuite, ce qui est

1022
00:45:36,180 --> 00:45:37,380
cette curiosité?

1023
00:45:37,380 --> 00:45:41,250
>> Eh bien, si nous utilisons ce genre de nouvelle
prendre sur la façon de stocker une chaîne dans un

1024
00:45:41,250 --> 00:45:44,500
structure de données, vous avez encore besoin d'
essentiellement cocher dans les données

1025
00:45:44,500 --> 00:45:47,250
Structure qu'un mot se termine ici.

1026
00:45:47,250 --> 00:45:50,830
En d'autres termes, chacun de ces nœuds
en quelque sorte a se rappeler que nous

1027
00:45:50,830 --> 00:45:53,500
effectivement suivi toutes ces pointeurs
et sont en laissant un peu

1028
00:45:53,500 --> 00:45:58,370
mie de pain au fond ici de cette
Structure pour indiquer M-A-X-W-E-L-L est

1029
00:45:58,370 --> 00:46:00,230
En effet, dans cette structure de données.

1030
00:46:00,230 --> 00:46:02,040
>> Donc, nous pourrions procéder comme suit.

1031
00:46:02,040 --> 00:46:06,810
Chacun des noeuds dans l'image que nous venons de
scie a un, un tableau de la taille 27.

1032
00:46:06,810 --> 00:46:10,550
Et il est maintenant 27, car en p fixé six,
nous allons vous donner réellement une apostrophe,

1033
00:46:10,550 --> 00:46:13,590
afin que nous puissions avoir des noms comme O'Reilly
et d'autres avec des apostrophes.

1034
00:46:13,590 --> 00:46:14,820
Mais même idée.

1035
00:46:14,820 --> 00:46:17,710
Chacun de ces éléments dans l'
tableau pointe vers une structure

1036
00:46:17,710 --> 00:46:19,320
noeud, donc juste un nœud.

1037
00:46:19,320 --> 00:46:21,430
Donc, ce n'est pas sans rappeler
de notre liste chaînée.

1038
00:46:21,430 --> 00:46:24,550
>> Et puis j'ai un booléen, que je vais
appelez mot, qui va juste être

1039
00:46:24,550 --> 00:46:29,120
vrai si un mot se termine à cette
noeud de l'arbre.

1040
00:46:29,120 --> 00:46:32,870
Il représente effectivement la petite
triangle, nous avons vu il ya un instant.

1041
00:46:32,870 --> 00:46:37,190
Donc, si un mot se termine à ce nœud dans le
arbre, ce champ de texte sera vrai,

1042
00:46:37,190 --> 00:46:41,990
qui est conceptuellement cochant ou
nous nous appuyons ce triangle, oui, il

1043
00:46:41,990 --> 00:46:44,080
est un mot ici.

1044
00:46:44,080 --> 00:46:45,120
>> Il s'agit donc d'un trie.

1045
00:46:45,120 --> 00:46:48,540
Et maintenant, la question est, qu'est-ce
est sa durée?

1046
00:46:48,540 --> 00:46:49,930
Est-il grand O de n?

1047
00:46:49,930 --> 00:46:51,410
Est-ce autre chose?

1048
00:46:51,410 --> 00:46:57,330
Eh bien, si vous avez n noms de ces données
la structure, Maxwell étant juste un des

1049
00:46:57,330 --> 00:47:02,330
eux, quelle est la durée de
d'insérer ou de trouver Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Quelle est la durée de fonctionnement
l'insertion de Maxwell?

1052
00:47:09,050 --> 00:47:11,740
S'il ya d'autres noms n
déjà dans le tableau?

1053
00:47:11,740 --> 00:47:12,507
Ouais?

1054
00:47:12,507 --> 00:47:15,429
>> ETUDIANT: [inaudible].

1055
00:47:15,429 --> 00:47:17,550
>> INTERLOCUTEUR 1: Ouais, c'est la longueur
du nom, non?

1056
00:47:17,550 --> 00:47:24,420
Alors M-a-x-w-e-l-l il se sent comme ce
algorithme est grand O de sept ans.

1057
00:47:24,420 --> 00:47:26,580
Maintenant, bien sûr, le nom
variera en longueur.

1058
00:47:26,580 --> 00:47:27,380
Peut-être que c'est un nom court.

1059
00:47:27,380 --> 00:47:28,600
C'est peut-être un nom plus long.

1060
00:47:28,600 --> 00:47:33,390
Mais ce qui est important ici, c'est que
c'est un nombre constant.

1061
00:47:33,390 --> 00:47:36,810
Et c'est peut-être pas vraiment constant,
Mais Dieu, si réaliste, dans un

1062
00:47:36,810 --> 00:47:41,570
dictionnaire, il ya probablement une certaine limite
le nombre de lettres dans un

1063
00:47:41,570 --> 00:47:43,820
Le nom de la personne dans un pays donné.

1064
00:47:43,820 --> 00:47:46,940
>> Et si nous pouvons supposer que
valeur est une constante.

1065
00:47:46,940 --> 00:47:47,750
Je ne sais pas ce que c'est.

1066
00:47:47,750 --> 00:47:50,440
Il est probablement plus grand que
nous pensons qu'il est.

1067
00:47:50,440 --> 00:47:52,720
Parce qu'il ya toujours un coin
cas avec un nom fou longtemps.

1068
00:47:52,720 --> 00:47:56,360
Alors, appelons-k, mais il ya toujours un
constant sans doute, parce que chaque

1069
00:47:56,360 --> 00:48:00,190
nom dans le monde, au moins dans un
pays en particulier, est que la longueur ou

1070
00:48:00,190 --> 00:48:01,780
plus courte, il est donc constant.

1071
00:48:01,780 --> 00:48:04,490
Mais quand nous avons dit que quelque chose est grand
O d'une valeur constante, qu'est-ce que

1072
00:48:04,490 --> 00:48:07,760
vraiment équivalent à?

1073
00:48:07,760 --> 00:48:10,420
C'est vraiment la même chose
comme disant constante de temps.

1074
00:48:10,420 --> 00:48:11,530
>> Maintenant, nous sommes en quelque sorte de tricherie, pas vrai?

1075
00:48:11,530 --> 00:48:15,340
Nous sommes en quelque sorte l'effet de levier un peu de théorie
ici pour dire que bien, de l'ordre de k est

1076
00:48:15,340 --> 00:48:17,450
vraiment il suffit de commander d'un seul,
et il est temps constant.

1077
00:48:17,450 --> 00:48:18,200
Mais il est vraiment.

1078
00:48:18,200 --> 00:48:22,550
Parce que l'idée fondamentale ici est que
si nous avons n noms déjà dans cette

1079
00:48:22,550 --> 00:48:26,010
structure de données, et nous insert Maxwell,
est la quantité de temps qu'il nous faut pour

1080
00:48:26,010 --> 00:48:29,530
insérer Maxwell à toutes les personnes touchées
par combien d'autres personnes

1081
00:48:29,530 --> 00:48:31,100
sont dans la structure de données?

1082
00:48:31,100 --> 00:48:31,670
Ne semble pas l'être.

1083
00:48:31,670 --> 00:48:36,280
Si j'avais un milliard de plus d'éléments à ce
trie, puis insérez Maxwell, est

1084
00:48:36,280 --> 00:48:38,650
il du tout affecté?

1085
00:48:38,650 --> 00:48:39,050
No.

1086
00:48:39,050 --> 00:48:42,950
Et ce n'est pas comme des données jour
structures que nous avons vu jusqu'à présent, où

1087
00:48:42,950 --> 00:48:46,820
le temps d'exécution de votre algorithme est
complètement indépendante de la quantité d'

1088
00:48:46,820 --> 00:48:51,430
substance est ou n'est pas déjà
en ce que la structure de données.

1089
00:48:51,430 --> 00:48:54,650
>> Et ainsi, avec cette offre vous est désormais un
occasion pour p fixé six, qui sera

1090
00:48:54,650 --> 00:48:58,310
de nouveau impliquer la mise en œuvre de votre propre
correcteur orthographique, la lecture en 150.000

1091
00:48:58,310 --> 00:49:01,050
termes, la meilleure façon de stocker cette
n'est pas nécessairement évident.

1092
00:49:01,050 --> 00:49:04,030
Et si j'ai aspiré à trouver
le Saint-Graal, je n'ai pas

1093
00:49:04,030 --> 00:49:05,330
prétendre qu'il est un trie.

1094
00:49:05,330 --> 00:49:09,810
En fait, une table de hachage peut très bien
s'avérer beaucoup plus efficace.

1095
00:49:09,810 --> 00:49:10,830
Mais ce ne sont là -

1096
00:49:10,830 --> 00:49:14,620
ce n'est que l'une des décisions de conception
vous aurez à faire.

1097
00:49:14,620 --> 00:49:18,920
>> Mais en fermant prenons 50 ou plus
secondes pour jeter un œil à ce qui se trouve

1098
00:49:18,920 --> 00:49:22,190
prochaine semaine à venir et au-delà, nous transition
à partir de cette ligne de commande

1099
00:49:22,190 --> 00:49:26,220
monde si les programmes C à des choses web
fondé et langages comme PHP et

1100
00:49:26,220 --> 00:49:30,350
JavaScript et de l'Internet lui-même,
protocoles comme HTTP, que vous avez

1101
00:49:30,350 --> 00:49:32,870
pris pour acquis pendant des années
maintenant, et j'ai tapé plus chaque

1102
00:49:32,870 --> 00:49:34,440
jour, peut-être, ou vu.

1103
00:49:34,440 --> 00:49:37,420
Et nous allons commencer à peler la
des couches de ce qui est l'Internet.

1104
00:49:37,420 --> 00:49:40,650
Et quel est le code qui
sous-tend les outils d'aujourd'hui.

1105
00:49:40,650 --> 00:49:43,230
Donc 50 secondes de ce teaser ici.

1106
00:49:43,230 --> 00:49:46,570
Je vous donne guerriers du Net.

1107
00:49:46,570 --> 00:49:51,370
>> [LECTURE VIDEO]

1108
00:49:51,370 --> 00:49:56,764
>> -Il est venu avec un message.

1109
00:49:56,764 --> 00:50:00,687
Avec un protocole qui lui est propre.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Il est venu à un monde de pare-feu cruels,
routeurs insensible, et les dangers loin

1112
00:50:19,780 --> 00:50:22,600
pire que la mort.

1113
00:50:22,600 --> 00:50:23,590
Il est rapide.

1114
00:50:23,590 --> 00:50:25,300
Il est fort.

1115
00:50:25,300 --> 00:50:27,700
Il est TCPIP.

1116
00:50:27,700 --> 00:50:30,420
Et il a votre adresse.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Guerriers du filet.

1119
00:50:34,590 --> 00:50:35,290
>> [FIN LECTURE VIDÉO]

1120
00:50:35,290 --> 00:50:38,070
>> INTERLOCUTEUR 1: C'est ainsi que l'internet
doit travailler dès la semaine prochaine.

1121
00:50:38,070 --> 00:50:40,406