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

2
00:00:00,500 --> 00:00:05,120
[Lecture de musique]

3
00:00:05,120 --> 00:00:12,026

4
00:00:12,026 --> 00:00:12,900
ENCEINTE 1: Très bien.

5
00:00:12,900 --> 00:00:14,600
Tout le monde souhaite un bon retour à la section.

6
00:00:14,600 --> 00:00:18,660
Je vous souhaite à tous êtes avec succès
récupéré de votre quiz

7
00:00:18,660 --> 00:00:19,510
de la semaine dernière.

8
00:00:19,510 --> 00:00:22,564
Je sais qu'il est un peu fou parfois.

9
00:00:22,564 --> 00:00:25,230
Comme je le disais avant, si vous êtes
à l'intérieur de l'écart-type,

10
00:00:25,230 --> 00:00:28,188
ne vous inquiétez pas vraiment à ce sujet, en particulier
pour une section moins à l'aise.

11
00:00:28,188 --> 00:00:30,230
Voilà à peu près où vous devriez être.

12
00:00:30,230 --> 00:00:32,850
>> Si vous avez fait une grande, alors impressionnant.

13
00:00:32,850 --> 00:00:33,650
Bravo à vous.

14
00:00:33,650 --> 00:00:36,149
Et si vous vous sentez comme vous avez besoin
un peu plus d'aide, se il vous plaît

15
00:00:36,149 --> 00:00:38,140
hésitez pas à atteindre
sur l'une quelconque des TF.

16
00:00:38,140 --> 00:00:40,030
Nous sommes tous ici pour aider.

17
00:00:40,030 --> 00:00:40,960
>> Voilà pourquoi nous enseignons.

18
00:00:40,960 --> 00:00:44,550
Voilà pourquoi je suis ici chaque lundi pour vous
les gars et à les heures de bureau le jeudi.

19
00:00:44,550 --> 00:00:48,130
Ainsi se il vous plaît sentez-vous libre pour me faire savoir
si vous êtes inquiet au sujet quoi que ce soit

20
00:00:48,130 --> 00:00:52,450
ou si il ya quelque chose sur le quiz
que vous voulez vraiment faire face.

21
00:00:52,450 --> 00:00:56,940
>> Donc, l'ordre du jour d'aujourd'hui est
tout sur les structures de données.

22
00:00:56,940 --> 00:01:01,520
Certains d'entre eux vont tout simplement être juste
pour aideront à vous familiariser avec ces derniers.

23
00:01:01,520 --> 00:01:04,870
Vous ne pouvez jamais mettre en œuvre
les dans cette classe.

24
00:01:04,870 --> 00:01:08,690
Certains d'entre eux vous voulez,
comme pour votre correcteur orthographique pset.

25
00:01:08,690 --> 00:01:11,380
>> Vous aurez le choix
entre les tables et tente hachage.

26
00:01:11,380 --> 00:01:13,680
Donc, nous allons certainement aller sur ceux-ci.

27
00:01:13,680 --> 00:01:18,690
Ça va être certainement plus de genre
d'une section de haut niveau aujourd'hui, cependant,

28
00:01:18,690 --> 00:01:22,630
car il ya beaucoup d'entre eux, et si
nous sommes allés dans les détails de mise en œuvre

29
00:01:22,630 --> 00:01:26,490
sur l'ensemble de ceux-ci, nous ne serions pas
même passer à travers les listes chaînées

30
00:01:26,490 --> 00:01:28,520
et peut-être un peu de tables de hachage.

31
00:01:28,520 --> 00:01:31,200
>> Donc garder avec moi.

32
00:01:31,200 --> 00:01:33,530
Nous ne sommes pas allez faire
autant de codage pour le moment.

33
00:01:33,530 --> 00:01:36,870
Si vous avez des questions à ce sujet
ou si vous voulez le voir mis en œuvre

34
00:01:36,870 --> 00:01:39,260
ou essayer par vous-même,
Je recommande vraiment

35
00:01:39,260 --> 00:01:44,250
aller à study.cs50.net, qui
a des exemples de tout cela.

36
00:01:44,250 --> 00:01:46,400
Il va falloir mes présentations PowerPoint
avec les notes que nous

37
00:01:46,400 --> 00:01:50,860
ont tendance à utiliser ainsi que certains programmes
exercices, en particulier pour les choses

38
00:01:50,860 --> 00:01:55,250
comme les listes chaînées et binaire
Arbres piles et les indices.

39
00:01:55,250 --> 00:01:59,590
Donc peu au plus haut niveau, qui
pourrait être agréable pour vous les gars.

40
00:01:59,590 --> 00:02:01,320
>> Donc, avec cela, nous allons commencer.

41
00:02:01,320 --> 00:02:03,060
Et aussi, des quiz yes--.

42
00:02:03,060 --> 00:02:06,550
Je pense que la plupart d'entre vous qui sont dans
ma section ont vos tests,

43
00:02:06,550 --> 00:02:12,060
mais quelqu'un vient ou une raison quelconque vous
ne sont pas, ils sont ici à l'avant.

44
00:02:12,060 --> 00:02:12,740
>> Donc lié listes.

45
00:02:12,740 --> 00:02:15,650
Je sais que ce genre de passe
à sauvegarder avant votre quiz.

46
00:02:15,650 --> 00:02:17,940
Ce fut la semaine avant
que nous avons appris à ce sujet.

47
00:02:17,940 --> 00:02:21,040
Mais dans ce cas, nous allons simplement
aller un peu plus en profondeur.

48
00:02:21,040 --> 00:02:25,900
>> Alors, pourquoi pourrions-nous choisir un
liste chaînée sur un tableau?

49
00:02:25,900 --> 00:02:27,130
Qu'est-ce qui les distingue?

50
00:02:27,130 --> 00:02:27,630
Oui?

51
00:02:27,630 --> 00:02:30,464
>> PUBLIC: Vous pouvez développer un lien
la liste par rapport à la taille fixe d'un tableau.

52
00:02:30,464 --> 00:02:31,171
ENCEINTE 1: Droit.

53
00:02:31,171 --> 00:02:33,970
Un tableau a taille fixe alors un
liste liée a une taille variable.

54
00:02:33,970 --> 00:02:36,970
Donc, si nous ne savons pas comment
beaucoup nous voulons stocker,

55
00:02:36,970 --> 00:02:39,880
une liste chaînée nous donne une grande
façon de le faire parce que nous pouvons seulement

56
00:02:39,880 --> 00:02:43,730
ajouter sur un autre nœud et ajouter sur
un autre nœud et ajouter sur un autre noeud.

57
00:02:43,730 --> 00:02:45,750
Mais ce qui pourrait être un compromis?

58
00:02:45,750 --> 00:02:49,521
Quelqu'un se souvient le compromis
entre les tableaux et les listes chaînées?

59
00:02:49,521 --> 00:02:50,020
Mmhmm?

60
00:02:50,020 --> 00:02:51,460
>> Public: Vous devez
passer par tout le chemin

61
00:02:51,460 --> 00:02:53,738
à travers la liste chaînée
trouver un élément dans une liste.

62
00:02:53,738 --> 00:02:55,570
Dans un tableau, vous pouvez
il suffit de trouver un élément.

63
00:02:55,570 --> 00:02:56,278
>> ENCEINTE 1: Droit.

64
00:02:56,278 --> 00:02:57,120
Donc, avec arrays--

65
00:02:57,120 --> 00:02:58,500
>> PUBLIC: [inaudible].

66
00:02:58,500 --> 00:03:01,090
>> ENCEINTE 1: Avec les tableaux, nous avons
ce qu'on appelle l'accès aléatoire.

67
00:03:01,090 --> 00:03:04,820
Signifie que si nous voulons ce qui est
jamais le cinquième point de la liste

68
00:03:04,820 --> 00:03:07,230
ou le cinquième point de notre
tableau, nous suffit de la saisir.

69
00:03:07,230 --> 00:03:10,440
Si il est une liste chaînée, nous avons
pour parcourir, non?

70
00:03:10,440 --> 00:03:14,020
Ainsi, l'accès à un élément en
un tableau est la constante de temps,

71
00:03:14,020 --> 00:03:19,530
alors avec une liste chaînée il serait
probablement parce que peut-être temps linéaire

72
00:03:19,530 --> 00:03:21,370
notre élément est tout le chemin à la fin.

73
00:03:21,370 --> 00:03:23,446
Nous devons chercher à travers tout.

74
00:03:23,446 --> 00:03:25,320
Donc, avec toutes ces données
structures que nous allons

75
00:03:25,320 --> 00:03:29,330
à dépenser un peu plus de temps,
quels sont les avantages et les inconvénients.

76
00:03:29,330 --> 00:03:31,480
Quand pourrions-nous vouloir
utiliser l'un sur l'autre?

77
00:03:31,480 --> 00:03:34,970
Et qui est le genre de
plus grand chose à emporter.

78
00:03:34,970 --> 00:03:40,140
>> Nous avons donc ici la
définition d'un noeud.

79
00:03:40,140 --> 00:03:43,040
Il est comme un élément
notre liste liée, non?

80
00:03:43,040 --> 00:03:46,180
Donc, nous sommes tous familiers
avec nos struct typedef,

81
00:03:46,180 --> 00:03:47,980
qui nous sommes allés en revue la dernière fois.

82
00:03:47,980 --> 00:03:53,180
Il était tout simplement de la création
un autre type de données que nous pourrions utiliser.

83
00:03:53,180 --> 00:03:57,930
>> Et dans ce cas, il est un nœud
qui tiendra un entier dans.

84
00:03:57,930 --> 00:04:00,210
Et puis ce qui est de la deuxième partie ici?

85
00:04:00,210 --> 00:04:03,192

86
00:04:03,192 --> 00:04:05,677
Tout le monde?

87
00:04:05,677 --> 00:04:06,680
>> PUBLIC: [inaudible].

88
00:04:06,680 --> 00:04:07,020
>> ENCEINTE 1: Ouais.

89
00:04:07,020 --> 00:04:08,400
Il est un pointeur vers le noeud suivant.

90
00:04:08,400 --> 00:04:12,610
Ce qui devrait être fait ici.

91
00:04:12,610 --> 00:04:18,790
Ceci est un pointeur de type
nœud à la chose suivante.

92
00:04:18,790 --> 00:04:22,410
Et qui est ce qu'ils
englobe notre nœud.

93
00:04:22,410 --> 00:04:24,060
Laisser refroidir.

94
00:04:24,060 --> 00:04:29,390
>> Très bien, alors à la recherche, comme nous étions
juste dire avant la main, si vous êtes

95
00:04:29,390 --> 00:04:31,840
en passant par de la recherche,
vous devez en fait itérer

96
00:04:31,840 --> 00:04:33,660
à travers votre liste chaînée.

97
00:04:33,660 --> 00:04:38,530
Donc, si nous sommes à la recherche pour le nombre
9, nous commencerions à notre siège

98
00:04:38,530 --> 00:04:41,520
et que nous montre au début
de notre liste liée, non?

99
00:04:41,520 --> 00:04:44,600
Et nous disons, OK, est-ce
noeud contient le numéro 9?

100
00:04:44,600 --> 00:04:45,690
Non?

101
00:04:45,690 --> 00:04:47,500
>> Tout droit, passer à la suivante.

102
00:04:47,500 --> 00:04:48,312
Suivez-le.

103
00:04:48,312 --> 00:04:49,520
Contient-il le numéro 9?

104
00:04:49,520 --> 00:04:50,570
Non.

105
00:04:50,570 --> 00:04:51,550
Suivre la suivante.

106
00:04:51,550 --> 00:04:55,490
>> Nous devons donc en fait une itération
à travers notre liste chaînée.

107
00:04:55,490 --> 00:05:00,070
Nous ne pouvons pas aller directement à l'endroit où 9 est.

108
00:05:00,070 --> 00:05:05,860
Et si vous les gars veulent vraiment
voir pseudo-code là-haut.

109
00:05:05,860 --> 00:05:10,420
Nous avons une fonction de recherche ici
qui prend in-- que faut-il en?

110
00:05:10,420 --> 00:05:13,110

111
00:05:13,110 --> 00:05:14,320
Que pensez-vous?

112
00:05:14,320 --> 00:05:15,960
Si facile un.

113
00:05:15,960 --> 00:05:17,784
Qu'est-ce que ce est?

114
00:05:17,784 --> 00:05:18,700
PUBLIC: [inaudible].

115
00:05:18,700 --> 00:05:20,366
ENCEINTE 1: Le nombre que nous recherchons.

116
00:05:20,366 --> 00:05:20,980
Droit?

117
00:05:20,980 --> 00:05:22,875
Et qu'est-ce que cela correspond à?

118
00:05:22,875 --> 00:05:25,020
Il est un pointeur vers?

119
00:05:25,020 --> 00:05:26,000
>> PUBLIC: Un noeud.

120
00:05:26,000 --> 00:05:28,980
>> ENCEINTE 1: Un nœud à la liste
que nous cherchons à, non?

121
00:05:28,980 --> 00:05:33,700
Nous avons donc des nœuds sont pointeur ici.

122
00:05:33,700 --> 00:05:37,240
Ceci est un point qui va
en fait itérer sur notre liste.

123
00:05:37,240 --> 00:05:39,630
Nous l'avons réglé égal à la liste
parce que ce juste

124
00:05:39,630 --> 00:05:44,380
sa mise en égale à la
début de notre liste chaînée.

125
00:05:44,380 --> 00:05:50,660
>> Et bien qu'il soit pas NULL, alors que
nous avons encore des choses dans notre liste,

126
00:05:50,660 --> 00:05:55,580
vérifier pour voir si ce nœud a
le nombre que nous recherchons.

127
00:05:55,580 --> 00:05:57,740
Retour vrai.

128
00:05:57,740 --> 00:06:01,070
Sinon, mettre à jour, non?

129
00:06:01,070 --> 00:06:04,870
>> Si elle est nulle, nous sortons de notre
boucle while et return false

130
00:06:04,870 --> 00:06:08,340
parce que cela signifie que nous avons pas trouvé.

131
00:06:08,340 --> 00:06:11,048
Est-ce que tout le monde se comment cela fonctionne?

132
00:06:11,048 --> 00:06:11,548
D'accord.

133
00:06:11,548 --> 00:06:14,940

134
00:06:14,940 --> 00:06:20,260
>> Donc, avec insertion, vous
faire de trois manières différentes.

135
00:06:20,260 --> 00:06:25,250
Vous pouvez faire précéder, vous pouvez ajouter
et vous pouvez insérer dans assorties.

136
00:06:25,250 --> 00:06:28,215
Dans ce cas, nous sommes
va faire un préfixe.

137
00:06:28,215 --> 00:06:33,380
Est-ce que quelqu'un sait comment ceux
trois cas peuvent différer?

138
00:06:33,380 --> 00:06:36,920
>> Donc préfixe signifie que vous mettez
il à l'avant de votre liste.

139
00:06:36,920 --> 00:06:39,770
Donc, cela voudrait dire que peu importe
ce que votre noeud est, peu importe

140
00:06:39,770 --> 00:06:43,160
quelle est la valeur, vous allez
de le mettre ici en face, OK?

141
00:06:43,160 --> 00:06:45,160
Ça va être le premier
élément dans votre liste.

142
00:06:45,160 --> 00:06:49,510
>> Si vous ajoutez, il va
pour aller à l'arrière de votre liste.

143
00:06:49,510 --> 00:06:54,010
Et l'insérer dans un assortiment signifie que vous êtes
va mettre réellement dans le lieu

144
00:06:54,010 --> 00:06:57,700
où il maintient votre liste chaînée triée.

145
00:06:57,700 --> 00:07:00,810
Encore une fois, la façon dont vous utilisez
ceux et lorsque vous utilisez

146
00:07:00,810 --> 00:07:02,530
les varieront en fonction de votre cas.

147
00:07:02,530 --> 00:07:05,834

148
00:07:05,834 --> 00:07:07,750
Si elle n'a pas besoin de
être triés, préfixe tend

149
00:07:07,750 --> 00:07:10,460
être ce que la plupart des gens
utiliser parce que vous ne

150
00:07:10,460 --> 00:07:15,680
avoir à passer par la liste complète
pour trouver la fin de l'ajouter, non?

151
00:07:15,680 --> 00:07:17,720
Vous pouvez simplement coller en plein.

152
00:07:17,720 --> 00:07:21,930
>> Nous allons donc passer par une
insertion 1 en ce moment.

153
00:07:21,930 --> 00:07:26,360
Donc, une chose que je vais
recommande fortement sur cette pset

154
00:07:26,360 --> 00:07:29,820
est de tirer les choses, comme toujours.

155
00:07:29,820 --> 00:07:35,130
Il est très important que vous mettez à jour
vos pointeurs dans le bon ordre

156
00:07:35,130 --> 00:07:38,620
parce que si vous mettez à jour les
un peu hors de l'ordre,

157
00:07:38,620 --> 00:07:42,210
vous allez finir par
perdre des parties de votre liste.

158
00:07:42,210 --> 00:07:49,680
>> Ainsi, par exemple, dans ce cas, nous sommes
dire la tête à tout moment à 1.

159
00:07:49,680 --> 00:07:56,070
Si nous faisons tout ce que
sans enregistrer cette 1,

160
00:07:56,070 --> 00:07:58,570
nous ne savons pas ce que
1 doit pointer maintenant

161
00:07:58,570 --> 00:08:02,490
parce que nous avons perdu ce que
la tête souligné.

162
00:08:02,490 --> 00:08:05,530
Donc, une chose à retenir
lorsque vous faites un préfixe

163
00:08:05,530 --> 00:08:09,630
est de sauver ce qui le
points de la tête à la première,

164
00:08:09,630 --> 00:08:15,210
puis le réaffecter, puis mettre à jour
ce que votre nouveau nœud doit pointer vers.

165
00:08:15,210 --> 00:08:20,870

166
00:08:20,870 --> 00:08:22,560
Dans ce cas, cela est une façon de le faire.

167
00:08:22,560 --> 00:08:25,440
>> Donc, si nous avions fait de cette façon
où nous venons de redéploiement de la tête,

168
00:08:25,440 --> 00:08:30,320
nous perdons notre fondamentalement
liste entière, non?

169
00:08:30,320 --> 00:08:38,000
Une façon de le faire est d'avoir 1 point à
prochaine, et alors point de tête à 1.

170
00:08:38,000 --> 00:08:42,650
Ou vous pouvez faire un peu comme le
stockage temporaire, dont je parlais.

171
00:08:42,650 --> 00:08:45,670
>> Mais réaffectation votre
pointeurs dans le bon ordre

172
00:08:45,670 --> 00:08:48,750
va être très, très
important pour ce jeu de processeurs.

173
00:08:48,750 --> 00:08:53,140
Sinon, vous allez avoir une table de hachage
table ou un essai qui vient va être

174
00:08:53,140 --> 00:08:56,014
une partie seulement des mots que vous
veulent et puis you're-- mmhmm?

175
00:08:56,014 --> 00:08:58,930
Public: Quel a été le temporaire
chose de stockage dont vous parliez?

176
00:08:58,930 --> 00:09:00,305
ENCEINTE 1: Le stockage temporaire.

177
00:09:00,305 --> 00:09:02,760
Donc, fondamentalement, un autre
comme vous pouvez le faire

178
00:09:02,760 --> 00:09:07,650
est stocker la tête de quelque chose, comme
stocker la variable temporaire.

179
00:09:07,650 --> 00:09:11,250
Assigner à 1 et
puis mettre à jour 1 au point

180
00:09:11,250 --> 00:09:13,830
à ce que la tête utilisé pour pointer.

181
00:09:13,830 --> 00:09:16,920
De cette manière, est évidemment
plus élégant parce que vous

182
00:09:16,920 --> 00:09:20,770
ne pas avoir besoin d'une valeur temporaire, mais
tout simplement d'offrir une autre façon de le faire.

183
00:09:20,770 --> 00:09:23,999

184
00:09:23,999 --> 00:09:25,790
Et nous avons effectivement
un code pour cela.

185
00:09:25,790 --> 00:09:28,080
Donc, pour la liste chaînée, nous
avoir fait un peu de code.

186
00:09:28,080 --> 00:09:31,930
Donc insérer ici, ce sont précéder.

187
00:09:31,930 --> 00:09:34,290
Donc cette entrée à la tête.

188
00:09:34,290 --> 00:09:38,820
>> Donc, première chose, vous devez
créer votre nouveau nœud, bien sûr,

189
00:09:38,820 --> 00:09:40,790
et vérifier la valeur NULL.

190
00:09:40,790 --> 00:09:43,250
Toujours bon.

191
00:09:43,250 --> 00:09:47,840
Et puis, vous devez affecter les valeurs.

192
00:09:47,840 --> 00:09:51,260
Chaque fois que vous créez un nouveau nœud, vous
ne sait pas ce qu'il pointe vers la prochaine,

193
00:09:51,260 --> 00:09:54,560
si vous voulez initialiser à NULL.

194
00:09:54,560 --> 00:09:58,760
Si elle ne finissent pointant vers quelque chose
autre, il se réaffecté et il est très bien.

195
00:09:58,760 --> 00:10:00,740
Si elle est la première chose
dans la liste, il faut

196
00:10:00,740 --> 00:10:04,270
au point sur null
qui est la fin de la liste.

197
00:10:04,270 --> 00:10:12,410
>> Alors pour l'insérer, nous voyons ici nous
affectez la valeur suivante de notre nœud

198
00:10:12,410 --> 00:10:17,380
à être ce que la tête est,
qui est ce que nous avions ici.

199
00:10:17,380 --> 00:10:19,930
Voilà ce que nous venons de faire.

200
00:10:19,930 --> 00:10:25,820
Et puis nous sommes tête à un point attribuant
à notre nouveau nœud, car rappelez-vous,

201
00:10:25,820 --> 00:10:31,090
nouveau est quelque pointeur vers un noeud,
et qui est exactement ce que la tête est.

202
00:10:31,090 --> 00:10:34,370
Voilà exactement pourquoi nous
avoir cette flèche accesseur.

203
00:10:34,370 --> 00:10:37,030

204
00:10:37,030 --> 00:10:37,530
Cool?

205
00:10:37,530 --> 00:10:38,130
Mmhmm?

206
00:10:38,130 --> 00:10:41,100
>> PUBLIC: Devons-nous
initialiser un nouveau à côté de la valeur NULL première,

207
00:10:41,100 --> 00:10:44,240
ou pouvons-nous simplement initialiser à la tête?

208
00:10:44,240 --> 00:10:48,210
>> ENCEINTE 1: New prochaine
doit être NULL pour commencer

209
00:10:48,210 --> 00:10:53,760
parce que vous ne savez pas
où il va être.

210
00:10:53,760 --> 00:10:56,100
En outre, ce type est de
Tout comme un paradigme.

211
00:10:56,100 --> 00:10:59,900
Vous définissez égale à NULL juste pour faire
assurer que toutes vos bases sont couvertes

212
00:10:59,900 --> 00:11:04,070
avant de faire toute réaffectation de sorte que
vous êtes toujours garanti que le

213
00:11:04,070 --> 00:11:08,880
pointer sur une valeur spécifique
par rapport à une valeur comme des ordures.

214
00:11:08,880 --> 00:11:12,210
Parce que, oui, nous attribuons
NOUVEAU automatiquement,

215
00:11:12,210 --> 00:11:15,420
mais il est plus juste comme un
bonnes pratiques pour l'initialiser

216
00:11:15,420 --> 00:11:19,270
de cette façon et puis réaffecter.

217
00:11:19,270 --> 00:11:23,420
>> OK, donc doublement lié listes maintenant.

218
00:11:23,420 --> 00:11:24,601
Que pensons-nous?

219
00:11:24,601 --> 00:11:26,350
Ce qui est différent avec
doublement des listes chaînées?

220
00:11:26,350 --> 00:11:30,750

221
00:11:30,750 --> 00:11:34,300
>> Ainsi, dans nos listes chaînées, nous pouvons
seulement se déplacer dans une direction, non?

222
00:11:34,300 --> 00:11:35,270
Nous avons seulement à côté.

223
00:11:35,270 --> 00:11:36,760
Nous ne pouvons aller de l'avant.

224
00:11:36,760 --> 00:11:40,300
>> Avec une liste doublement chaînée,
nous pouvons également revenir en arrière.

225
00:11:40,300 --> 00:11:44,810
Donc, nous avons non seulement la
nombre que nous voulons stocker,

226
00:11:44,810 --> 00:11:50,110
nous avons où il pointe prochaine
et où nous venons de.

227
00:11:50,110 --> 00:11:52,865
Donc, ce qui permet de
certains mieux traversée.

228
00:11:52,865 --> 00:11:56,620

229
00:11:56,620 --> 00:12:01,240
>> Nœuds donc doublement chaînées,
très similaire, non?

230
00:12:01,240 --> 00:12:05,000
La seule différence est maintenant que nous
avoir un côté et un précédent.

231
00:12:05,000 --> 00:12:06,235
Il est la seule différence.

232
00:12:06,235 --> 00:12:09,570

233
00:12:09,570 --> 00:12:14,790
>> Donc, si nous étions à précéder ou append-- nous
ne pas avoir de code de cette place ici--

234
00:12:14,790 --> 00:12:17,830
mais si vous deviez essayer et
insérer, l'important

235
00:12:17,830 --> 00:12:19,980
est que vous devez faire
que vous affectez

236
00:12:19,980 --> 00:12:23,360
à la fois votre précédente et votre
pointeur suivant correctement.

237
00:12:23,360 --> 00:12:29,010
Donc dans ce cas, vous feriez
non seulement l'initialisation suivante,

238
00:12:29,010 --> 00:12:31,820
l'initialisation précédente.

239
00:12:31,820 --> 00:12:36,960
Si nous sommes à la tête de la liste, nous
non seulement tenir tête égale nouvelle,

240
00:12:36,960 --> 00:12:41,750
mais si notre nouvelle précédente
pointer vers la tête, non?

241
00:12:41,750 --> 00:12:43,380
>> Voilà la seule différence.

242
00:12:43,380 --> 00:12:47,200
Et si vous voulez plus pratique avec
ceux-ci avec les listes chaînées, avec insertion,

243
00:12:47,200 --> 00:12:49,900
avec la suppression, avec insert
dans une liste assortis,

244
00:12:49,900 --> 00:12:52,670
se il vous plaît vérifier study.cs50.net.

245
00:12:52,670 --> 00:12:54,870
Il ya un tas de grands exercices.

246
00:12:54,870 --> 00:12:55,870
Je les recommande fortement.

247
00:12:55,870 --> 00:12:59,210
Je souhaite que nous ayons le temps de les parcourir
mais il ya beaucoup de structures de données

248
00:12:59,210 --> 00:13:01,530
pour passer à travers.

249
00:13:01,530 --> 00:13:02,650
>> OK, donc les tables de hachage.

250
00:13:02,650 --> 00:13:07,070
Ceci est probablement la plus
peu utile pour votre pset

251
00:13:07,070 --> 00:13:11,090
ici parce que vous allez être
mise en œuvre de l'un d'eux, ou un essai.

252
00:13:11,090 --> 00:13:12,200
Je l'aime vraiment les tables de hachage.

253
00:13:12,200 --> 00:13:13,110
Ils sont plutôt sympas.

254
00:13:13,110 --> 00:13:17,080
>> Donc, fondamentalement, ce
qui se passe est une table de hachage

255
00:13:17,080 --> 00:13:22,050
est quand nous avons vraiment besoin rapide
insertion, délétion, et recherche.

256
00:13:22,050 --> 00:13:25,010
Ce sont les choses que nous sommes
priorité à une table de hachage.

257
00:13:25,010 --> 00:13:29,500
Ils peuvent devenir assez grand,
mais comme nous le verrons avec essais,

258
00:13:29,500 --> 00:13:33,040
il ya des choses qui sont beaucoup plus gros.

259
00:13:33,040 --> 00:13:38,330
>> Mais fondamentalement, tout un hachage
table est une fonction de hachage

260
00:13:38,330 --> 00:13:47,215
qui vous dit qui seau de mettre chaque
de vos données, chacun de vos éléments.

261
00:13:47,215 --> 00:13:51,140
Une façon simple de penser à une table de hachage
est qu'il est seulement seaux de choses,

262
00:13:51,140 --> 00:13:51,770
droit?

263
00:13:51,770 --> 00:13:59,720
Ainsi, lorsque vous triez les choses par
comme la première lettre de leur nom,

264
00:13:59,720 --> 00:14:01,820
qui est un peu comme une table de hachage.

265
00:14:01,820 --> 00:14:06,180
>> Alors vous les gars si je devais groupe est
en groupes de quiconque son nom commence

266
00:14:06,180 --> 00:14:11,670
avec un cours ici, ou celui qui est l'anniversaire
est en Janvier, Février, Mars,

267
00:14:11,670 --> 00:14:15,220
que ce soit, qui est efficace
la création d'une table de hachage.

268
00:14:15,220 --> 00:14:18,120
Il est juste que la création de seaux
vous triez vos éléments en

269
00:14:18,120 --> 00:14:19,520
de sorte que vous pouvez les trouver plus facilement.

270
00:14:19,520 --> 00:14:22,300
Ainsi de cette façon quand je dois
pour trouver l'un de vous,

271
00:14:22,300 --> 00:14:24,680
Je ne dois pas chercher
par chacun de vos noms.

272
00:14:24,680 --> 00:14:29,490
Je peux être comme, oh, je sais que
L'anniversaire de Danielle est in--

273
00:14:29,490 --> 00:14:30,240
PUBLIC: --April.

274
00:14:30,240 --> 00:14:30,948
ENCEINTE 1: Avril.

275
00:14:30,948 --> 00:14:33,120
Donc, je regarde dans ma Avril
seau, et avec un peu de chance,

276
00:14:33,120 --> 00:14:38,270
elle sera le seul là-bas et
mon temps est constante en ce sens,

277
00:14:38,270 --> 00:14:41,230
alors que si je dois regarder
par tout un tas de gens,

278
00:14:41,230 --> 00:14:43,090
ça va prendre beaucoup plus de temps.

279
00:14:43,090 --> 00:14:45,830
Donc, tables de hachage ne sont réellement que des seaux.

280
00:14:45,830 --> 00:14:48,630
Un moyen facile de penser à eux.

281
00:14:48,630 --> 00:14:52,930
>> Donc, une chose très importante à propos
une table de hachage est une fonction de hachage.

282
00:14:52,930 --> 00:14:58,140
Donc, les choses que je viens de parler, comme
votre première lettre de votre prénom

283
00:14:58,140 --> 00:15:01,450
ou mois de votre anniversaire,
ce sont des idées que

284
00:15:01,450 --> 00:15:03,070
vraiment en corrélation avec une fonction de hachage.

285
00:15:03,070 --> 00:15:08,900
Il est juste une façon de décider qui
vous êtes la seau élément va dans, OK?

286
00:15:08,900 --> 00:15:14,850
Donc, pour ce jeu de processeurs, vous pouvez rechercher
à peu près toutes les fonctions de hachage que vous voulez.

287
00:15:14,850 --> 00:15:16,030
>> Ne pas avoir à être votre propre.

288
00:15:16,030 --> 00:15:21,140
Il y en a de vraiment cool sur
il que font toutes sortes de mathématiques fou.

289
00:15:21,140 --> 00:15:25,170
Et si vous voulez faire de votre
correcteur orthographique super rapide,

290
00:15:25,170 --> 00:15:27,620
I would definitely
se pencher sur l'un de ceux.

291
00:15:27,620 --> 00:15:32,390
>> Mais il ya aussi la
les plus simples, comme calcul

292
00:15:32,390 --> 00:15:39,010
la somme des mots, comme
chaque lettre a un certain nombre.

293
00:15:39,010 --> 00:15:39,940
Calculer la somme.

294
00:15:39,940 --> 00:15:42,230
Qui détermine le godet.

295
00:15:42,230 --> 00:15:45,430
Ils ont aussi les plus faciles que
sont comme tous les A ici,

296
00:15:45,430 --> 00:15:47,050
tous les B est ici.

297
00:15:47,050 --> 00:15:48,920
L'un de ceux.

298
00:15:48,920 --> 00:15:55,770
>> Fondamentalement, il vous indique juste que
index de tableau de votre élément devrait aller en.

299
00:15:55,770 --> 00:15:58,690
Il suffit de décider de la bucket--
tout est une fonction de hachage est.

300
00:15:58,690 --> 00:16:04,180
Nous avons donc ici un exemple qui est
que la première lettre de la chaîne

301
00:16:04,180 --> 00:16:05,900
que je viens de parler.

302
00:16:05,900 --> 00:16:11,900
>> Donc, vous avez une table de hachage qui est juste la
première lettre de votre chaîne moins un,

303
00:16:11,900 --> 00:16:16,090
qui vous donnera une
nombre entre 0 et 25.

304
00:16:16,090 --> 00:16:20,790
Et ce que vous voulez faire est
veiller à ce que cela représente

305
00:16:20,790 --> 00:16:24,110
la taille de votre hachage table--
combien il ya des godets.

306
00:16:24,110 --> 00:16:25,860
Avec un grand nombre de ceux-ci
Les fonctions de hachage, ils sont

307
00:16:25,860 --> 00:16:31,630
va être le retour des valeurs qui pourraient
être bien au-dessus du nombre de seaux

308
00:16:31,630 --> 00:16:33,610
que vous avez fait
dans votre table de hachage,

309
00:16:33,610 --> 00:16:37,240
si vous avez besoin de faire
sûr et mod par ceux-ci.

310
00:16:37,240 --> 00:16:42,190
Sinon, il va dire,
oh, il devrait être dans un seau 5000

311
00:16:42,190 --> 00:16:46,040
mais vous avez seulement 30
seaux à votre table de hachage.

312
00:16:46,040 --> 00:16:49,360
Et bien sûr, nous savons tous que ce
va donner lieu à des erreurs folles.

313
00:16:49,360 --> 00:16:52,870
Donc, assurez-vous de mod par la
taille de votre table de hachage.

314
00:16:52,870 --> 00:16:58,430

315
00:16:58,430 --> 00:16:58,930
Laisser refroidir.

316
00:16:58,930 --> 00:17:00,506
Donc collisions.

317
00:17:00,506 --> 00:17:02,620
Tout le monde est bon à ce jour?

318
00:17:02,620 --> 00:17:03,120
Mmhmm?

319
00:17:03,120 --> 00:17:05,900
>> Public: Pourquoi ne serait-il
retourner cette valeur massif?

320
00:17:05,900 --> 00:17:09,210
>> ENCEINTE 1: Selon l'algorithme
que votre fonction de hachage utilise.

321
00:17:09,210 --> 00:17:12,270
Certains d'entre eux faire
multiplication fou.

322
00:17:12,270 --> 00:17:16,270
Et il est tout à obtenir
une répartition,

323
00:17:16,270 --> 00:17:18,490
de sorte qu'ils ne vraiment quelque
parfois des choses folles.

324
00:17:18,490 --> 00:17:20,960
Ce est tout.

325
00:17:20,960 --> 00:17:22,140
Rien d'autre?

326
00:17:22,140 --> 00:17:22,829
D'accord.

327
00:17:22,829 --> 00:17:24,480
>> Donc collisions.

328
00:17:24,480 --> 00:17:29,270
Au fond, comme je l'ai dit plus tôt,
dans le meilleur des cas,

329
00:17:29,270 --> 00:17:32,040
tout seau je regarde dans est
va avoir une chose,

330
00:17:32,040 --> 00:17:34,160
donc je ne dois pas regarder du tout, non?

331
00:17:34,160 --> 00:17:37,040
Je sais que ce soit est là ou ce est
pas, et que ce que nous voulons vraiment.

332
00:17:37,040 --> 00:17:43,960
Mais si nous avons des dizaines de milliers de
points de données et de moins de ce nombre

333
00:17:43,960 --> 00:17:48,700
des seaux, nous allons avoir
collisions où finalement quelque chose

334
00:17:48,700 --> 00:17:54,210
va avoir à se retrouver dans un
seau qui a déjà un élément.

335
00:17:54,210 --> 00:17:57,390
>> Donc la question est, qu'est-ce
faisons-nous dans ce cas?

336
00:17:57,390 --> 00:17:58,480
Que faisons-nous?

337
00:17:58,480 --> 00:17:59,300
Nous avons déjà quelque chose?

338
00:17:59,300 --> 00:18:00,060
Devons-nous juste le jeter?

339
00:18:00,060 --> 00:18:00,700
>> Non.

340
00:18:00,700 --> 00:18:01,980
Nous devons garder les deux.

341
00:18:01,980 --> 00:18:06,400
Ainsi, la manière que nous
typiquement le faire est ce?

342
00:18:06,400 --> 00:18:08,400
Quelle est la structure de données
nous venons de parler?

343
00:18:08,400 --> 00:18:09,316
PUBLIC: liste chaînée.

344
00:18:09,316 --> 00:18:10,500
ENCEINTE 1: Une liste chaînée.

345
00:18:10,500 --> 00:18:16,640
Donc, maintenant, à la place de chacun de ceux-ci
seaux avoir un seul élément,

346
00:18:16,640 --> 00:18:24,020
il va contenir une liste chaînée de
les éléments qui ont été hachés en elle.

347
00:18:24,020 --> 00:18:27,588
OK, tout le monde ne sorte de rendre cette idée?

348
00:18:27,588 --> 00:18:30,546
Parce que nous ne pouvions pas avoir un tableau
parce que nous ne savons pas combien de choses

349
00:18:30,546 --> 00:18:31,730
vont être là.

350
00:18:31,730 --> 00:18:36,540
Une liste chaînée nous permet de
avoir juste le nombre exact que

351
00:18:36,540 --> 00:18:38,465
sont hachés dans le seau, non?

352
00:18:38,465 --> 00:18:42,260

353
00:18:42,260 --> 00:18:50,500
>> Donc linéaire palpage
essentiellement ce idea--

354
00:18:50,500 --> 00:18:52,300
il est une façon de faire face à une collision.

355
00:18:52,300 --> 00:18:58,010
Ce que vous pouvez faire est de savoir si, dans ce
cas, Berry a été haché dans 1

356
00:18:58,010 --> 00:19:01,130
et nous avons déjà
quelque chose, que vous venez de

357
00:19:01,130 --> 00:19:04,840
continuer jusqu'à ce que
vous trouverez un emplacement vide.

358
00:19:04,840 --> 00:19:06,370
Voilà une façon de le gérer.

359
00:19:06,370 --> 00:19:09,020
L'autre façon de gérer
il est avec ce que nous venons

360
00:19:09,020 --> 00:19:12,280
called-- le lien
liste est appelée chaînage.

361
00:19:12,280 --> 00:19:20,510
>> Donc, cette idée fonctionne si
votre table de hachage vous pensez

362
00:19:20,510 --> 00:19:24,150
est beaucoup plus grande que
vos données définies ou si vous

363
00:19:24,150 --> 00:19:28,870
vouloir tenter de minimiser le chaînage
jusqu'à ce qu'il soit absolument nécessaire.

364
00:19:28,870 --> 00:19:34,050
Donc, une chose est linéaire
sondage signifie évidemment

365
00:19:34,050 --> 00:19:37,290
que votre fonction de hachage
est pas tout à fait comme utile

366
00:19:37,290 --> 00:19:42,200
parce que vous allez finir par utiliser
votre fonction de hachage, se rendre à un point,

367
00:19:42,200 --> 00:19:46,400
vous sondez linéaire jusqu'à
un endroit qui est disponible.

368
00:19:46,400 --> 00:19:49,670
Mais maintenant, bien sûr, rien
d'autre qui se termine là-haut,

369
00:19:49,670 --> 00:19:52,050
vous allez avoir à
recherche encore plus loin.

370
00:19:52,050 --> 00:19:55,650
>> Et il ya beaucoup plus
Recherche frais que

371
00:19:55,650 --> 00:19:59,820
va entrer dans un élément
dans votre table de hachage maintenant, non?

372
00:19:59,820 --> 00:20:05,640
Et maintenant quand vous allez essayer de trouver
Berry à nouveau, vous allez hacher,

373
00:20:05,640 --> 00:20:07,742
et il va dire,
oh, regardez dans le seau 1,

374
00:20:07,742 --> 00:20:09,700
et il ne va pas être
dans le seau 1, de sorte que vous êtes

375
00:20:09,700 --> 00:20:11,970
allez avoir à traverser
sur le reste de ceux-ci.

376
00:20:11,970 --> 00:20:17,720
Donc, il est parfois utile,
mais dans la plupart des cas,

377
00:20:17,720 --> 00:20:22,660
nous allons dire que
chaînage est ce que vous voulez faire.

378
00:20:22,660 --> 00:20:25,520
>> Donc nous en avons parlé plus tôt.

379
00:20:25,520 --> 00:20:27,812
Je suis un peu en avance sur moi-même.

380
00:20:27,812 --> 00:20:33,560
Mais chaînage est essentiellement que
chaque seau dans votre table de hachage

381
00:20:33,560 --> 00:20:36,120
est juste une liste chaînée.

382
00:20:36,120 --> 00:20:39,660
>> Un autre moyen, plus ou technique
Ainsi, de penser à une table de hachage

383
00:20:39,660 --> 00:20:44,490
est qu'il est juste un tableau
des listes chaînées, qui

384
00:20:44,490 --> 00:20:49,330
quand vous écrivez votre dictionnaire
et vous essayez de le charger,

385
00:20:49,330 --> 00:20:52,070
penser comme un
tableau de listes chaînées

386
00:20:52,070 --> 00:20:54,390
il sera beaucoup plus facile
pour vous d'initialiser.

387
00:20:54,390 --> 00:20:57,680
>> Auditoire: Alors table de hachage
a une taille prédéterminée,

388
00:20:57,680 --> 00:20:58,980
comme un [inaudible] de seaux?

389
00:20:58,980 --> 00:20:59,220
>> ENCEINTE 1: Droit.

390
00:20:59,220 --> 00:21:01,655
Ainsi, il a un certain nombre de
seaux que vous determine--

391
00:21:01,655 --> 00:21:03,530
qui vous les gars devraient
hésitez pas à jouer avec.

392
00:21:03,530 --> 00:21:05,269
Il peut être assez cool
pour voir ce qui se passe

393
00:21:05,269 --> 00:21:06,810
que vous changez votre numéro de seaux.

394
00:21:06,810 --> 00:21:09,410

395
00:21:09,410 --> 00:21:11,510
Mais oui, il a une
définir le nombre de seaux.

396
00:21:11,510 --> 00:21:15,360
Qu'est-ce que vous permet d'ajuster comme
autant d'éléments que vous avez besoin

397
00:21:15,360 --> 00:21:19,350
est ce chaînage séparé où vous
ont lié les listes dans chaque seau.

398
00:21:19,350 --> 00:21:22,850
Cela signifie que votre table de hachage
sera exactement la taille

399
00:21:22,850 --> 00:21:25,440
que vous en avez besoin pour être, non?

400
00:21:25,440 --> 00:21:27,358
Voilà tout l'intérêt de listes chaînées.

401
00:21:27,358 --> 00:21:30,850

402
00:21:30,850 --> 00:21:32,480
Laisser refroidir.

403
00:21:32,480 --> 00:21:38,780
>> Donc, tout le monde il OK?

404
00:21:38,780 --> 00:21:39,801
Bien.

405
00:21:39,801 --> 00:21:40,300
Ah.

406
00:21:40,300 --> 00:21:41,860
Qu'est-ce que vient de se passer?

407
00:21:41,860 --> 00:21:42,960
Vraiment maintenant.

408
00:21:42,960 --> 00:21:45,250
Devinez quelqu'un me tue.

409
00:21:45,250 --> 00:21:52,060
>> OK, nous allons entrer dans
essais, qui sont un peu fou.

410
00:21:52,060 --> 00:21:53,140
Je l'aime tables de hachage.

411
00:21:53,140 --> 00:21:54,460
Je pense qu'ils sont vraiment cool.

412
00:21:54,460 --> 00:21:56,710
Essais sont cool, trop.

413
00:21:56,710 --> 00:21:59,590
>> Donc ce que quelqu'un se rappeler ce un essai est?

414
00:21:59,590 --> 00:22:01,740
Vous devriez avoir dépassé
brièvement dans la leçon?

415
00:22:01,740 --> 00:22:04,570

416
00:22:04,570 --> 00:22:06,377
Vous souvenez-vous de sorte comment cela fonctionne?

417
00:22:06,377 --> 00:22:08,460
PUBLIC: Je suis juste un signe de tête
que nous sommes allés au-dessus.

418
00:22:08,460 --> 00:22:09,626
ENCEINTE 1: On ne va dessus.

419
00:22:09,626 --> 00:22:13,100
OK, nous allons vraiment aller
plus il est maintenant ce que nous disons.

420
00:22:13,100 --> 00:22:14,860
>> PUBLIC: Voilà pour un arbre de recherche.

421
00:22:14,860 --> 00:22:15,280
>> ENCEINTE 1: Ouais.

422
00:22:15,280 --> 00:22:16,196
Il est un arbre de recherche.

423
00:22:16,196 --> 00:22:16,960
Impressionnant.

424
00:22:16,960 --> 00:22:23,610
Donc, une chose à noter ici est que nous
sont à la recherche à des caractères individuels

425
00:22:23,610 --> 00:22:24,480
ici, non?

426
00:22:24,480 --> 00:22:29,710
>> Alors avant avec notre fonction de hachage, nous
étaient à la recherche sur les mots dans son ensemble,

427
00:22:29,710 --> 00:22:32,270
et maintenant nous sommes à la recherche de plus
les personnages, non?

428
00:22:32,270 --> 00:22:38,380
Nous avons donc ici Maxwell et Mendel.

429
00:22:38,380 --> 00:22:47,840
Donc, fondamentalement, un try-- une façon de penser
à ce sujet est que chaque niveau ici

430
00:22:47,840 --> 00:22:49,000
est une série de lettres.

431
00:22:49,000 --> 00:22:53,310

432
00:22:53,310 --> 00:22:55,790
Donc ceci est votre noeud racine ici, non?

433
00:22:55,790 --> 00:23:01,980
Ceci présente tous les caractères de la
alphabet pour le début de chaque mot.

434
00:23:01,980 --> 00:23:06,480
>> Et ce que vous voulez faire est
par exemple, OK, nous avons un mot M.

435
00:23:06,480 --> 00:23:10,590
Nous allons chercher Maxwell, si
nous allons à M. et M des points à un ensemble

436
00:23:10,590 --> 00:23:14,800
autre un tableau où chaque
mot, tant qu'il n'y

437
00:23:14,800 --> 00:23:17,044
est un mot qui a une
que la seconde lettre,

438
00:23:17,044 --> 00:23:19,460
aussi longtemps que il ya un mot qui
B a la deuxième lettre,

439
00:23:19,460 --> 00:23:24,630
elle aura un pointeur
aller d'un tableau à côté.

440
00:23:24,630 --> 00:23:29,290
>> Il n'y a probablement pas un
mot que MP quelque chose,

441
00:23:29,290 --> 00:23:32,980
si à la position P en ce
tableau, il serait tout simplement NULL.

442
00:23:32,980 --> 00:23:38,840
Il dit, OK, il n'y a pas de mot
qui a M suivie par un P, OK?

443
00:23:38,840 --> 00:23:43,100
Donc, si nous pensons à ce sujet, chaque
l'un de ces petits choses

444
00:23:43,100 --> 00:23:47,990
est en fait un de ces
grands tableaux de A à Z.

445
00:23:47,990 --> 00:23:55,064
Donc, ce qui pourrait être l'une des choses
qui est une sorte de inconvénient d'un essai?

446
00:23:55,064 --> 00:23:56,500
>> PUBLIC: A beaucoup de mémoire.

447
00:23:56,500 --> 00:23:59,940
>> ENCEINTE 1: Il ya une tonne de mémoire, non?

448
00:23:59,940 --> 00:24:08,750
Chacun de ces blocs ici
représente 26 places, 26 élément tableau.

449
00:24:08,750 --> 00:24:13,680
Donc essais se incroyablement espace lourd.

450
00:24:13,680 --> 00:24:17,100
>> Mais ils sont très rapides.

451
00:24:17,100 --> 00:24:22,540
Incroyablement rapide mais
vraiment espace inefficace.

452
00:24:22,540 --> 00:24:24,810
Type d'avoir à comprendre
celle que vous voulez.

453
00:24:24,810 --> 00:24:29,470
Ce sont vraiment cool pour votre pset,
mais ils prennent beaucoup de mémoire,

454
00:24:29,470 --> 00:24:30,290
si vous négociez off.

455
00:24:30,290 --> 00:24:31,480
Ouais?

456
00:24:31,480 --> 00:24:34,300
>> PUBLIC: Serait-il possible
de mettre en place un essai et ensuite

457
00:24:34,300 --> 00:24:37,967
une fois que vous avez toutes les
données dans ce que vous need--

458
00:24:37,967 --> 00:24:39,550
Je ne sais pas si ce serait logique.

459
00:24:39,550 --> 00:24:42,200
Je commençais à me débarrasser de toutes les
Caractères NULL, mais

460
00:24:42,200 --> 00:24:42,910
vous ne seriez pas en mesure d'indexer eux--

461
00:24:42,910 --> 00:24:43,275
>> ENCEINTE 1: Vous devez toujours leur.

462
00:24:43,275 --> 00:24:44,854
>> PUBLIC: - de la même façon à chaque fois.

463
00:24:44,854 --> 00:24:45,520
ENCEINTE 1: Ouais.

464
00:24:45,520 --> 00:24:50,460
Vous avez besoin des caractères NULL à laisser
vous savez si il n'y a pas un mot là.

465
00:24:50,460 --> 00:24:52,040
Ben ne vous avez quelque chose que vous voulez?

466
00:24:52,040 --> 00:24:52,540
D'accord.

467
00:24:52,540 --> 00:24:54,581
Très bien, nous allons donc
d'aller un peu plus

468
00:24:54,581 --> 00:24:58,920
dans le détail technique derrière
essayer et travailler à travers un exemple.

469
00:24:58,920 --> 00:25:01,490
>> OK, si cela est la même chose.

470
00:25:01,490 --> 00:25:06,290
Alors que dans une liste chaînée, notre principal
genre de-- quel est le mot que je veux? -

471
00:25:06,290 --> 00:25:08,350
comme bloc de construction était un nœud.

472
00:25:08,350 --> 00:25:12,280
Dans un essai, nous avons aussi un nœud,
mais il est défini différemment.

473
00:25:12,280 --> 00:25:17,000
>> Nous avons donc une certaine bool que
représente en fait si un mot

474
00:25:17,000 --> 00:25:23,530
existe à cet endroit, et puis
nous avons une gamme ici-- ou plutôt,

475
00:25:23,530 --> 00:25:27,840
ceci est un pointeur sur un
tableau de 27 caractères.

476
00:25:27,840 --> 00:25:33,339
Et ceci est pour, dans ce cas, cette
27-- Je suis sûr que vous êtes tous comme, attends,

477
00:25:33,339 --> 00:25:34,880
il ya 26 lettres dans l'alphabet.

478
00:25:34,880 --> 00:25:36,010
Pourquoi avons-nous 27?

479
00:25:36,010 --> 00:25:37,870
>> Ainsi, en fonction de la
comme vous le mettre en œuvre,

480
00:25:37,870 --> 00:25:43,240
cela est d'un ensemble de processeurs que
permis pour apostrophes.

481
00:25:43,240 --> 00:25:46,010
Voilà pourquoi l'un de plus.

482
00:25:46,010 --> 00:25:50,500
Vous aurez également à certains
cas, le terminateur null

483
00:25:50,500 --> 00:25:53,230
est inclus comme l'un des
caractères qu'il est autorisé à être,

484
00:25:53,230 --> 00:25:56,120
et voilà comment ils vérifient
voir si elle est la fin du mot.

485
00:25:56,120 --> 00:26:01,340
Si vous êtes intéressé, consultez
La vidéo de Kevin sur study.cs50,

486
00:26:01,340 --> 00:26:04,790
ainsi que Wikipedia a
quelques bonnes ressources là-bas.

487
00:26:04,790 --> 00:26:09,000
>> Mais nous allons passer par tout genre
de la façon dont vous pouvez travailler à travers un essai

488
00:26:09,000 --> 00:26:11,010
si on vous donne un.

489
00:26:11,010 --> 00:26:16,230
Donc, nous avons un super-simple ici que
a les mots "chauve-souris" et "zoom" en eux.

490
00:26:16,230 --> 00:26:18,920
Et comme nous le voyons ici,
ce petit espace ici

491
00:26:18,920 --> 00:26:22,560
représente notre bool que
dit, oui, cela est un mot.

492
00:26:22,560 --> 00:26:27,060
Et puis cela a notre
des tableaux de caractères, non?

493
00:26:27,060 --> 00:26:33,480
>> Donc, nous allons passer par
trouver "chauve-souris" dans cette tentative.

494
00:26:33,480 --> 00:26:38,340
Donc, commencer par le haut, à droite?

495
00:26:38,340 --> 00:26:46,290
Et nous savons que b correspond à
le second index, le deuxième élément

496
00:26:46,290 --> 00:26:47,840
dans ce tableau, parce que a et b.

497
00:26:47,840 --> 00:26:51,340
Ainsi, approximativement la seconde.

498
00:26:51,340 --> 00:26:58,820
>> Et il dit, OK, cool, suivre que dans
le tableau suivant, parce que si nous nous souvenons,

499
00:26:58,820 --> 00:27:02,160
il est pas que chacun de ceux-ci
contient en fait l'élément.

500
00:27:02,160 --> 00:27:07,110
Chacun de ces tableaux
contient un pointeur, non?

501
00:27:07,110 --> 00:27:10,030
Il est une distinction importante à faire.

502
00:27:10,030 --> 00:27:13,450
>> Je sais que cela va être-- essais sont
vraiment difficile d'obtenir sur la première fois,

503
00:27:13,450 --> 00:27:15,241
même si cela est le
deuxième ou troisième fois

504
00:27:15,241 --> 00:27:18,370
et il est encore un peu
de paraître difficile,

505
00:27:18,370 --> 00:27:21,199
Je promets si vous allez montre
court à nouveau demain,

506
00:27:21,199 --> 00:27:22,740
il va probablement faire beaucoup plus de sens.

507
00:27:22,740 --> 00:27:23,890
Il en faut beaucoup pour digérer.

508
00:27:23,890 --> 00:27:27,800
Je suis encore parfois
comme, attendez, ce qui est un essai?

509
00:27:27,800 --> 00:27:29,080
Comment puis-je l'utiliser?

510
00:27:29,080 --> 00:27:33,880
>> Nous avons donc b Dans ce cas,
qui est notre deuxième indice.

511
00:27:33,880 --> 00:27:40,240
Si nous avions, par exemple, ou c
d ou toute autre lettre,

512
00:27:40,240 --> 00:27:45,810
nous avons besoin de la carte que revenir à l'index
de notre gamme que cela correspond à.

513
00:27:45,810 --> 00:27:56,930
Nous serions donc prendre comme rchar et nous avons
soustraire de un à map dans 0 à 25.

514
00:27:56,930 --> 00:27:58,728
Tout le monde bien comment nous
la carte de nos personnages?

515
00:27:58,728 --> 00:28:00,440
D'accord.

516
00:28:00,440 --> 00:28:05,980
>> Donc, nous allons à la seconde et nous
voir que, oui, il est pas à NULL.

517
00:28:05,980 --> 00:28:07,780
Nous pouvons passer à la prochaine série.

518
00:28:07,780 --> 00:28:12,300
Donc, nous passons à la prochaine série ici.

519
00:28:12,300 --> 00:28:15,500
>> Et nous disons, OK, maintenant nous
besoin de voir si un est ici.

520
00:28:15,500 --> 00:28:18,590
Une valeur NULL ou est-ce
en fait aller de l'avant?

521
00:28:18,590 --> 00:28:21,880
Ainsi, une se déplace effectivement
transmettre dans ce tableau.

522
00:28:21,880 --> 00:28:24,570
Et nous disons, OK, t est notre dernière lettre.

523
00:28:24,570 --> 00:28:27,580
Donc, nous allons à la t à l'index.

524
00:28:27,580 --> 00:28:30,120
Et puis nous allons de l'avant
parce qu'il ya une autre.

525
00:28:30,120 --> 00:28:38,340
Et celui-ci dit essentiellement que, oui,
il dit qu'il ya un mot ici--

526
00:28:38,340 --> 00:28:41,750
que si vous suivez cette
chemin, vous êtes arrivés

527
00:28:41,750 --> 00:28:43,210
à un mot, que nous connaissons est «chauve-souris».

528
00:28:43,210 --> 00:28:43,800
Oui?

529
00:28:43,800 --> 00:28:46,770
>> Public: Est-ce que la norme d'avoir
comme l'indice 0 et alors une sorte à 1

530
00:28:46,770 --> 00:28:47,660
ou d'avoir à la fin?

531
00:28:47,660 --> 00:28:48,243
>> ENCEINTE 1: Non

532
00:28:48,243 --> 00:28:55,360
Donc, si nous regardons en arrière à notre
déclaration ici, il est un booléen,

533
00:28:55,360 --> 00:28:59,490
il est donc son propre élément dans votre nœud.

534
00:28:59,490 --> 00:29:03,331
Donc, il ne fait pas partie du tableau.

535
00:29:03,331 --> 00:29:03,830
Laisser refroidir.

536
00:29:03,830 --> 00:29:08,370
Donc, lorsque nous aurons terminé notre parole et nous sommes
à ce tableau, ce que nous voulons faire

537
00:29:08,370 --> 00:29:12,807
est faire un chèque de est-ce un mot.

538
00:29:12,807 --> 00:29:14,390
Et dans ce cas, il reviendrait oui.

539
00:29:14,390 --> 00:29:17,220

540
00:29:17,220 --> 00:29:24,090
>> Donc, sur cette note, nous savons que "zoo" -
nous savons que les humains qui "zoo" est un mot,

541
00:29:24,090 --> 00:29:24,820
droit?

542
00:29:24,820 --> 00:29:28,990
Mais sont essayer ici serait
dire, non, il est pas.

543
00:29:28,990 --> 00:29:33,980
Et ce serait dire que parce que nous
ne pas avoir désigné comme un mot ici.

544
00:29:33,980 --> 00:29:40,440
Même si nous pouvons traverser
grâce à cette matrice,

545
00:29:40,440 --> 00:29:43,890
cette tentative serait dire que, non,
zoo est pas dans votre dictionnaire

546
00:29:43,890 --> 00:29:47,070
parce que nous avons pas
désigné comme tel.

547
00:29:47,070 --> 00:29:52,870
>> Donc, une façon de faire that--
Oh, désolé, celui-ci.

548
00:29:52,870 --> 00:29:59,450
Donc dans ce cas, "zoo" est pas
un mot, mais il est dans notre essai.

549
00:29:59,450 --> 00:30:05,690
Mais dans celui-ci, disons que nous voulons
introduire le mot «bain», ce qui se passe

550
00:30:05,690 --> 00:30:08,260
nous suivons est through-- b, a, t.

551
00:30:08,260 --> 00:30:11,820
Nous sommes dans ce tableau, et
nous allons à la recherche de h.

552
00:30:11,820 --> 00:30:15,220
>> Dans ce cas, quand on
regarder le pointeur à h,

553
00:30:15,220 --> 00:30:17,890
il pointe vers NULL, OK?

554
00:30:17,890 --> 00:30:20,780
Donc, sauf si elle est explicitement
pointant vers un autre tableau,

555
00:30:20,780 --> 00:30:25,000
vous supposez que tous les pointeurs
dans ce tableau sont pointant vers null.

556
00:30:25,000 --> 00:30:28,270
Donc dans ce cas, h pointe
null si nous ne pouvons rien faire,

557
00:30:28,270 --> 00:30:31,540
de sorte qu'il serait aussi revenir
faux, "bain" est pas ici.

558
00:30:31,540 --> 00:30:34,102

559
00:30:34,102 --> 00:30:35,810
Alors maintenant, nous sommes en fait
va passer par

560
00:30:35,810 --> 00:30:39,790
comment pourrions-nous réellement dire
que "zoo" est dans notre essai.

561
00:30:39,790 --> 00:30:42,920
Comment pouvons-nous insérons "zoo" dans notre essai?

562
00:30:42,920 --> 00:30:47,810
Donc, de la même façon que nous avons commencé avec
notre liste chaînée, on commence à la racine.

563
00:30:47,810 --> 00:30:50,600
En cas de doute, commencer à
l'origine de ces choses.

564
00:30:50,600 --> 00:30:53,330
>> Et nous disons, OK, z.

565
00:30:53,330 --> 00:30:55,650
z existe dans ce domaine, et il le fait.

566
00:30:55,650 --> 00:30:58,370
Donc, vous vous déplacez à
votre prochain tableau, OK?

567
00:30:58,370 --> 00:31:01,482
Et puis sur la suivante,
nous disons, OK, ne o existe?

568
00:31:01,482 --> 00:31:03,000
Il ne.

569
00:31:03,000 --> 00:31:04,330
Ce nouveau.

570
00:31:04,330 --> 00:31:08,670
>> Et ainsi de suite notre prochain, nous l'avons dit,
OK, "zoo" existe déjà ici.

571
00:31:08,670 --> 00:31:12,440
Tout ce que nous devons faire est de définir cette égalité
à vrai qu'il ya un mot là.

572
00:31:12,440 --> 00:31:15,260
Si vous aviez suivi tout
jusqu'à avant ce moment,

573
00:31:15,260 --> 00:31:17,030
il est un mot, si juste
Le mettre à tel.

574
00:31:17,030 --> 00:31:17,530
Oui?

575
00:31:17,530 --> 00:31:22,550
>> AUDIENCE: le fait alors que
signifie que «ba» est un mot aussi?

576
00:31:22,550 --> 00:31:24,120
>> ENCEINTE 1: Non

577
00:31:24,120 --> 00:31:28,870
Donc dans ce cas, "ba" nous aurions
ici, nous dirions qu'il est un mot,

578
00:31:28,870 --> 00:31:31,590
et il serait toujours pas.

579
00:31:31,590 --> 00:31:32,822
D'accord?

580
00:31:32,822 --> 00:31:33,740
Mmhmm?

581
00:31:33,740 --> 00:31:36,360
>> Auditoire: Alors, une fois que vous est-il un
mot et vous dites oui, alors il

582
00:31:36,360 --> 00:31:38,380
contiendra d'aller à m?

583
00:31:38,380 --> 00:31:42,260
>> ENCEINTE 1: Donc cela a à voir
with-- vous chargez ce dans.

584
00:31:42,260 --> 00:31:43,640
Vous dites "zoo" est un mot.

585
00:31:43,640 --> 00:31:47,020
Quand vous allez à check--
comme, disons que vous voulez dire,

586
00:31:47,020 --> 00:31:49,400
existe "zoo" dans ce dictionnaire?

587
00:31:49,400 --> 00:31:54,200
Vous allez seulement à la recherche de "zoo"
et puis vérifier pour voir si elle est un mot.

588
00:31:54,200 --> 00:31:57,291
Vous ne réussirez jamais à se déplacer
jusqu'à m parce que ce ne

589
00:31:57,291 --> 00:31:58,290
ce que vous cherchez.

590
00:31:58,290 --> 00:32:02,690

591
00:32:02,690 --> 00:32:08,070
>> Donc, si nous voulions vraiment
ajouter «bain» dans cette tentative,

592
00:32:08,070 --> 00:32:11,390
nous ferions la même chose
comme nous l'avons fait avec "zoo"

593
00:32:11,390 --> 00:32:15,380
sauf que nous verrions que lorsque nous
essayer d'obtenir à h, il ne existe pas.

594
00:32:15,380 --> 00:32:20,090
Ainsi, vous pouvez penser à ce que d'essayer
d'ajouter un nouveau nœud dans une liste chaînée,

595
00:32:20,090 --> 00:32:27,210
de sorte que nous aurions besoin d'ajouter un autre
l'un de ces tableaux, comme si.

596
00:32:27,210 --> 00:32:35,670
Et puis ce que nous faisons est que nous venons de mettre la h
élément de ce tableau montrant ce.

597
00:32:35,670 --> 00:32:39,430
>> Et puis quoi voudrions-nous faire ici?

598
00:32:39,430 --> 00:32:43,110
Ajoutez égale à vrai
car il est un mot.

599
00:32:43,110 --> 00:32:46,350

600
00:32:46,350 --> 00:32:48,150
Laisser refroidir.

601
00:32:48,150 --> 00:32:48,700
Je sais.

602
00:32:48,700 --> 00:32:51,170
Essais ne sont pas le plus excitant.

603
00:32:51,170 --> 00:32:54,250
Croyez-moi, je sais.

604
00:32:54,250 --> 00:32:58,040
>> Donc, une chose à réaliser avec essais,
Je l'ai dit, ils sont très efficaces.

605
00:32:58,040 --> 00:33:00,080
Donc, nous avons vu qu'ils
prendre une tonne d'espace.

606
00:33:00,080 --> 00:33:01,370
Ils genre de confusion.

607
00:33:01,370 --> 00:33:03,367
Alors, pourquoi aurions-nous jamais les utiliser?

608
00:33:03,367 --> 00:33:05,450
Nous utilisons ces parce qu'ils sont
incroyablement efficace.

609
00:33:05,450 --> 00:33:08,130
>> Donc, si jamais vous êtes à la recherche
un mot, vous êtes seulement

610
00:33:08,130 --> 00:33:10,450
limitée par la longueur du mot.

611
00:33:10,450 --> 00:33:15,210
Donc, si vous êtes à la recherche d'un
mot qui est d'une longueur de cinq ans,

612
00:33:15,210 --> 00:33:20,940
vous ne jamais devoir
faire dans la plupart des cinq comparaisons, OK?

613
00:33:20,940 --> 00:33:25,780
Et il est donc essentiellement une constante.

614
00:33:25,780 --> 00:33:29,150
Comme insertion et lookup
sont essentiellement constante de temps.

615
00:33:29,150 --> 00:33:33,750
>> Donc, si vous pouvez toujours obtenir
quelque chose en temps constant,

616
00:33:33,750 --> 00:33:35,150
qui est aussi bon qu'il obtient.

617
00:33:35,150 --> 00:33:37,990
Vous ne pouvez pas faire mieux que
constante de temps pour ces choses.

618
00:33:37,990 --> 00:33:43,150
Voilà donc l'un des
d'énormes avantages d'essais.

619
00:33:43,150 --> 00:33:46,780
>> Mais il ya beaucoup d'espace.

620
00:33:46,780 --> 00:33:50,380
Donc, vous avez genre de décider
ce qui est plus important pour vous.

621
00:33:50,380 --> 00:33:54,700
Et sur les ordinateurs d'aujourd'hui, la
espace que d'essayer peut prendre jusqu'à

622
00:33:54,700 --> 00:33:57,740
peut-être ne pas affecter
vous tant que ça, mais peut-être

623
00:33:57,740 --> 00:34:01,350
vous avez affaire à quelque chose
qui a beaucoup, beaucoup plus de choses,

624
00:34:01,350 --> 00:34:02,810
et un essai est tout simplement pas raisonnable.

625
00:34:02,810 --> 00:34:03,000
Oui?

626
00:34:03,000 --> 00:34:05,610
>> PUBLIC: Attendez, si vous avez 26
lettres à chacun?

627
00:34:05,610 --> 00:34:07,440
>> ENCEINTE 1: Mmhmm.

628
00:34:07,440 --> 00:34:08,570
Ouais, vous avez 26.

629
00:34:08,570 --> 00:34:16,984
Vous avez quelque soit mot marqueur et puis
vous avez 26 pointeurs de chacun.

630
00:34:16,984 --> 00:34:17,775
Et ils point--

631
00:34:17,775 --> 00:34:20,280
>> Public: Et tous les 26,
ne ils ont chacun 26?

632
00:34:20,280 --> 00:34:21,500
>> ENCEINTE 1: Oui.

633
00:34:21,500 --> 00:34:27,460
Et voilà pourquoi, comme vous pouvez
voir, il se dilate très rapidement.

634
00:34:27,460 --> 00:34:28,130
Bien.

635
00:34:28,130 --> 00:34:32,524
Donc, nous allons entrer dans les arbres, ce qui
Je me sens comme il est plus facile et sera probablement

636
00:34:32,524 --> 00:34:36,150
être un petit sursis
à partir de là essais.

637
00:34:36,150 --> 00:34:39,620
Donc, je l'espère plus de vous
ont vu un arbre avant.

638
00:34:39,620 --> 00:34:41,820
Pas comme la jolie
ceux à l'extérieur, que je

639
00:34:41,820 --> 00:34:44,340
Je ne sais pas si quelqu'un
est allé à l'extérieur récemment.

640
00:34:44,340 --> 00:34:49,230
Je suis allé cueillir des pommes ce week-end,
et oh mon dieu, elle était très belle.

641
00:34:49,230 --> 00:34:52,250
Je ne savais pas feuilles
pourrait regarder cette jolie.

642
00:34:52,250 --> 00:34:53,610
>> Donc, ceci est juste un arbre, non?

643
00:34:53,610 --> 00:34:56,790
Il est juste un noeud, et il
des points à un tas d'autres nœuds.

644
00:34:56,790 --> 00:34:59,570
Comme vous le voyez ici, ce sont
une sorte de thème récurrent.

645
00:34:59,570 --> 00:35:03,720
Nœuds pointant vers des nœuds est une sorte de
l'essence de plusieurs structures de données.

646
00:35:03,720 --> 00:35:06,670
Tout dépend de la façon dont nous
ont eux pointent à l'autre

647
00:35:06,670 --> 00:35:08,600
et la façon dont nous traversons
à travers eux et comment nous

648
00:35:08,600 --> 00:35:14,500
insérer choses qui détermine
leurs différentes caractéristiques.

649
00:35:14,500 --> 00:35:17,600
>> Il suffit donc de la terminologie,
que je l'ai utilisé avant.

650
00:35:17,600 --> 00:35:20,010
Alors racine est tout ce qui est en haut.

651
00:35:20,010 --> 00:35:21,200
il est où nous commençons toujours.

652
00:35:21,200 --> 00:35:23,610
Vous pouvez penser que la tête aussi.

653
00:35:23,610 --> 00:35:28,750
Mais pour les arbres, nous avons tendance à
reportez-vous à ce que la racine.

654
00:35:28,750 --> 00:35:32,820
>> Tout au fond ici--
à la très, très bottom--

655
00:35:32,820 --> 00:35:34,500
sont considérés comme les feuilles.

656
00:35:34,500 --> 00:35:37,210
Donc, il va de pair avec la
chose d'arbres entiers, non?

657
00:35:37,210 --> 00:35:39,860
Les feuilles sont sur les bords de votre arbre.

658
00:35:39,860 --> 00:35:45,820
>> Et puis nous avons aussi un couple de
termes pour parler de nœuds en relation

659
00:35:45,820 --> 00:35:46,680
à l'autre.

660
00:35:46,680 --> 00:35:49,700
Donc, nous avons des parents,
enfants, frères et sœurs.

661
00:35:49,700 --> 00:35:56,260
Donc dans ce cas, 3 est le
mère de 5, 6, et 7.

662
00:35:56,260 --> 00:36:00,370
Ainsi, le parent est tout ce qui est
un cran au dessus que vous êtes

663
00:36:00,370 --> 00:36:02,940
référence, si juste
comme un arbre généalogique.

664
00:36:02,940 --> 00:36:07,090
Heureusement, tout cela est un peu
peu plus intuitive que les essais.

665
00:36:07,090 --> 00:36:10,970
>> Les frères et sœurs sont celles qui ont
le même parent, non?

666
00:36:10,970 --> 00:36:13,470
Ils sont sur le même niveau ici.

667
00:36:13,470 --> 00:36:16,960
Et puis, comme je l'étais
dire, les enfants sont tout simplement

668
00:36:16,960 --> 00:36:22,630
ce qui est un cran en dessous
le nœud en question, OK?

669
00:36:22,630 --> 00:36:23,470
Laisser refroidir.

670
00:36:23,470 --> 00:36:25,610
Ainsi, un arbre binaire.

671
00:36:25,610 --> 00:36:31,450
Quelqu'un peut hasarder une hypothèse sur l'un des
les caractéristiques de l'arbre binaire?

672
00:36:31,450 --> 00:36:32,770
>> PUBLIC: Max deux feuilles.

673
00:36:32,770 --> 00:36:33,478
>> ENCEINTE 1: Droit.

674
00:36:33,478 --> 00:36:34,640
Ainsi, deux feuilles de max.

675
00:36:34,640 --> 00:36:39,730
Ainsi, dans celui-ci avant, nous avions celui-ci
qui avait trois, mais dans un arbre binaire,

676
00:36:39,730 --> 00:36:45,000
vous avez un maximum de deux
enfants par mère, non?

677
00:36:45,000 --> 00:36:46,970
Il ya un autre
caractéristique intéressante.

678
00:36:46,970 --> 00:36:51,550
Est-ce que quelqu'un sait qui?

679
00:36:51,550 --> 00:36:52,620
Arbre binaire.

680
00:36:52,620 --> 00:37:00,350
>> Ainsi, un arbre binaire aura tout
sur the-- celui-ci est pas sorted--

681
00:37:00,350 --> 00:37:05,320
mais dans un arbre binaire triés,
tout à droite

682
00:37:05,320 --> 00:37:08,530
est plus grand que le parent,
et tout à gauche

683
00:37:08,530 --> 00:37:10,035
est inférieure à la mère.

684
00:37:10,035 --> 00:37:15,690
Et cela a été un quiz
question avant, si bon à savoir.

685
00:37:15,690 --> 00:37:19,500
Donc, la façon dont nous définissons ce,
de plus, nous avons un autre nœud.

686
00:37:19,500 --> 00:37:21,880
Cela semble très similaire à ce que?

687
00:37:21,880 --> 00:37:28,336

688
00:37:28,336 --> 00:37:28,836
Deux fois plus

689
00:37:28,836 --> 00:37:29,320
>> PUBLIC: Lié listes

690
00:37:29,320 --> 00:37:31,100
>> ENCEINTE 1: Un double liste liée, non?

691
00:37:31,100 --> 00:37:33,690
Donc, si nous remplaçons cette
avec précédente et suivante,

692
00:37:33,690 --> 00:37:35,670
ce serait une liste doublement chaînée.

693
00:37:35,670 --> 00:37:40,125
Mais dans ce cas, nous avons effectivement
avoir gauche et à droite et voilà.

694
00:37:40,125 --> 00:37:41,500
Sinon, il est exactement le même.

695
00:37:41,500 --> 00:37:43,374
Nous avons toujours l'élément
vous cherchez,

696
00:37:43,374 --> 00:37:45,988
et vous avez juste deux pointeurs
aller à tout ce qui est à côté.

697
00:37:45,988 --> 00:37:49,210

698
00:37:49,210 --> 00:37:51,870
Ouais, donc arbre binaire de recherche.

699
00:37:51,870 --> 00:37:57,665
Si nous remarquons, tout sur le
ici est plus than--

700
00:37:57,665 --> 00:37:59,850
ou tout de suite
à droite ici

701
00:37:59,850 --> 00:38:02,840
est plus grande que, tout
ici est moins.

702
00:38:02,840 --> 00:38:06,980

703
00:38:06,980 --> 00:38:14,000
>> Donc, si nous étions à la recherche à travers, il
devrait être très proche de recherche binaire

704
00:38:14,000 --> 00:38:14,910
ici, non?

705
00:38:14,910 --> 00:38:17,640
Sauf qu'au lieu de regarder
à la moitié du tableau,

706
00:38:17,640 --> 00:38:21,720
nous cherchons simplement à soit la gauche
côté ou le côté droit de l'arbre.

707
00:38:21,720 --> 00:38:24,850
Ainsi, il devient un peu plus simple, je pense.

708
00:38:24,850 --> 00:38:29,300
>> Donc, si votre racine est NULL,
Évidemment, il est juste faux.

709
00:38:29,300 --> 00:38:33,470
Et si elle est là, évidemment, il est vrai.

710
00:38:33,470 --> 00:38:35,320
Si elle est inférieure, nous cherchons la gauche.

711
00:38:35,320 --> 00:38:37,070
Si elle est supérieure à,
nous cherchons la droite.

712
00:38:37,070 --> 00:38:39,890
Il est exactement comme la recherche binaire,
seulement une structure de données différente

713
00:38:39,890 --> 00:38:40,600
que nous utilisons.

714
00:38:40,600 --> 00:38:42,790
Au lieu d'un tableau,
il est juste un arbre binaire.

715
00:38:42,790 --> 00:38:45,820

716
00:38:45,820 --> 00:38:48,090
>> OK, piles.

717
00:38:48,090 --> 00:38:51,550
Et aussi, il semble que nous
pourrait avoir un peu de temps.

718
00:38:51,550 --> 00:38:54,460
Si nous le faisons, je suis heureux d'y aller
sur tout cela de nouveau.

719
00:38:54,460 --> 00:38:56,856
OK, donc piles.

720
00:38:56,856 --> 00:39:02,695
Est-ce que quelqu'un se souvient de ce stacks--
des caractéristiques d'une pile?

721
00:39:02,695 --> 00:39:05,550

722
00:39:05,550 --> 00:39:10,400
>> OK, donc la plupart d'entre nous, je pense,
manger dans la salle halls--

723
00:39:10,400 --> 00:39:13,100
autant que nous pouvons ne pas aimer à.

724
00:39:13,100 --> 00:39:16,900
Mais évidemment, vous pouvez penser à une pile
littéralement comme une pile de plateaux

725
00:39:16,900 --> 00:39:18,460
ou une pile de choses.

726
00:39:18,460 --> 00:39:21,820
Et ce qui est important
à réaliser est qu'il est

727
00:39:21,820 --> 00:39:26,850
la caractéristique quelque chose--
que nous appelons by-- est LIFO.

728
00:39:26,850 --> 00:39:28,450
Est-ce que quelqu'un sait ce qui représente?

729
00:39:28,450 --> 00:39:29,070
Mmhmm?

730
00:39:29,070 --> 00:39:30,650
>> PUBLIC: dernier entré, premier sorti.

731
00:39:30,650 --> 00:39:32,250
>> ENCEINTE 1: Droit, dernier entré, premier sorti.

732
00:39:32,250 --> 00:39:36,585
Donc, si nous le savons, si nous empiler les choses
jusqu'à, la chose la plus facile à saisir off--

733
00:39:36,585 --> 00:39:39,570
et peut-être la seule chose que nous pouvons saisir
hors si notre pile est grand enough--

734
00:39:39,570 --> 00:39:40,850
est que l'élément supérieur.

735
00:39:40,850 --> 00:39:43,460
Donc tout ce que a été mis sur
last-- comme nous le voyons ici,

736
00:39:43,460 --> 00:39:46,370
tout ce qui était poussé
sur plus recently-- est

737
00:39:46,370 --> 00:39:51,160
va être le premier
chose que nous crever, OK?

738
00:39:51,160 --> 00:39:56,324
>> Donc, ce que nous avons ici est
une autre structure typedef.

739
00:39:56,324 --> 00:39:58,740
Ceci est vraiment comme un
Crash Course dans la structure de données,

740
00:39:58,740 --> 00:40:01,650
donc il ya beaucoup jeté à vous les gars.

741
00:40:01,650 --> 00:40:02,540
Je sais.

742
00:40:02,540 --> 00:40:04,970
Donc, encore une autre structure.

743
00:40:04,970 --> 00:40:06,740
Yay pour les structures.

744
00:40:06,740 --> 00:40:16,660
>> Et dans ce cas, il est certain pointeur
à un tableau qui a une certaine capacité.

745
00:40:16,660 --> 00:40:20,830
Donc, ce qui représente notre pile
ici, comme notre tableau réel

746
00:40:20,830 --> 00:40:22,520
qui est maintenant nos éléments.

747
00:40:22,520 --> 00:40:24,850
Et puis ici nous avons une certaine taille.

748
00:40:24,850 --> 00:40:31,170
>> Et généralement, vous voulez garder
piste de la taille de votre pile est

749
00:40:31,170 --> 00:40:36,180
parce que ça va permettre
que vous fassiez est si vous connaissez la taille,

750
00:40:36,180 --> 00:40:39,170
il vous permet de dire,
OK, je suis à la capacité?

751
00:40:39,170 --> 00:40:40,570
Puis-je ajouter quelque chose de plus?

752
00:40:40,570 --> 00:40:44,650
Et il vous dit aussi
où le haut de votre pile

753
00:40:44,650 --> 00:40:48,180
est si vous savez ce que vous
peut réellement décoller.

754
00:40:48,180 --> 00:40:51,760
Et ce qui se passe réellement à
être un peu plus clair.

755
00:40:51,760 --> 00:40:57,350
>> Donc, pour pousser, une chose, si vous
étaient toujours à mettre en œuvre poussée,

756
00:40:57,350 --> 00:41:01,330
comme je viens de le dire, votre
pile a une taille limitée, non?

757
00:41:01,330 --> 00:41:03,990
Notre gamme avait une certaine capacité.

758
00:41:03,990 --> 00:41:04,910
Il est un tableau.

759
00:41:04,910 --> 00:41:08,930
Il est de taille fixe, donc nous avons besoin de
faire en sorte que nous ne mettons pas plus

760
00:41:08,930 --> 00:41:11,950
dans notre tableau de nous
pour avoir effectivement espace.

761
00:41:11,950 --> 00:41:16,900
>> Ainsi, lorsque vous créez un bouton
fonction, la première chose que vous faites est de dire, OK,

762
00:41:16,900 --> 00:41:18,570
je dois espace dans ma pile?

763
00:41:18,570 --> 00:41:23,330
Parce que si je ne le fais pas, désolé,
Je ne peux pas enregistrer votre élément.

764
00:41:23,330 --> 00:41:28,980
Si je le fais, alors vous voulez stocker
au sommet de la pile, non?

765
00:41:28,980 --> 00:41:31,325
>> Et c'est pourquoi nous avons
de garder une trace de notre taille.

766
00:41:31,325 --> 00:41:35,290
Si nous ne gardons pas trace de notre taille,
nous ne savons pas où le mettre.

767
00:41:35,290 --> 00:41:39,035
Nous ne savons pas combien de choses
sont dans notre gamme déjà.

768
00:41:39,035 --> 00:41:41,410
Comme de toute évidence il existe des moyens
peut-être que vous pourriez le faire.

769
00:41:41,410 --> 00:41:44,610
Vous pouvez initialiser tout à NULL
et puis vérifier la dernière NULL,

770
00:41:44,610 --> 00:41:47,950
mais une chose beaucoup plus facile est juste
à-dire, OK, garder une trace de taille.

771
00:41:47,950 --> 00:41:51,840
Comme je sais que je dois quatre éléments
dans mon tableau, donc la chose suivante

772
00:41:51,840 --> 00:41:55,930
que nous mettons sur, nous sommes
allez stocker à l'indice 4.

773
00:41:55,930 --> 00:42:00,940
Et puis, bien sûr, cela signifie que
vous avez réussi à pousser quelque chose

774
00:42:00,940 --> 00:42:03,320
sur votre pile, vous
vouloir augmenter la taille

775
00:42:03,320 --> 00:42:08,880
de sorte que vous savez où vous êtes si
que vous pouvez pousser plus de choses sur.

776
00:42:08,880 --> 00:42:12,730
>> Donc, si nous essayons de pop
quelque chose de la pile,

777
00:42:12,730 --> 00:42:16,072
ce qui pourrait être la première chose
que nous voulons vérifier?

778
00:42:16,072 --> 00:42:18,030
Vous essayez de prendre
quelque chose de votre pile.

779
00:42:18,030 --> 00:42:21,710

780
00:42:21,710 --> 00:42:24,781
Êtes-vous sûr qu'il ya
quelque chose dans votre pile?

781
00:42:24,781 --> 00:42:25,280
Non.

782
00:42:25,280 --> 00:42:26,894
Alors que peut-on vouloir vérifier?

783
00:42:26,894 --> 00:42:27,810
>> PUBLIC: [inaudible].

784
00:42:27,810 --> 00:42:29,880
ENCEINTE 1: Vérifier la taille?

785
00:42:29,880 --> 00:42:31,840
Taille.

786
00:42:31,840 --> 00:42:38,520
Donc, nous voulons vérifier si
notre taille est supérieur à 0, OK?

787
00:42:38,520 --> 00:42:44,970
Et si elle l'est, nous voulons diminuer
notre taille par 0 et le retourner.

788
00:42:44,970 --> 00:42:45,840
Pourquoi?

789
00:42:45,840 --> 00:42:49,950
>> Dans la première, nous étions
pousser, nous avons poussé le

790
00:42:49,950 --> 00:42:52,460
sur la taille et la taille puis mis à jour.

791
00:42:52,460 --> 00:42:57,850
Dans ce cas, nous décrémentation taille
et puis l'enlever, arracher ce

792
00:42:57,850 --> 00:42:58,952
de notre tableau.

793
00:42:58,952 --> 00:42:59,826
Pourquoi pouvons-nous faire cela?

794
00:42:59,826 --> 00:43:04,800

795
00:43:04,800 --> 00:43:11,811
Donc, si je dois une chose sur ma pile,
ce qui serait ma taille à ce point?

796
00:43:11,811 --> 00:43:13,140
1.

797
00:43:13,140 --> 00:43:15,180
>> Et où est stocké l'élément 1?

798
00:43:15,180 --> 00:43:17,621
A quel indice?

799
00:43:17,621 --> 00:43:18,120
PUBLIC: 0.

800
00:43:18,120 --> 00:43:19,060
ENCEINTE 1: 0.

801
00:43:19,060 --> 00:43:22,800
Donc dans ce cas, nous
toujours besoin de faire sure--

802
00:43:22,800 --> 00:43:27,630
au lieu de retourner
taille moins 1, parce que nous

803
00:43:27,630 --> 00:43:31,730
Sachez que notre élément est
va être stocké à une moins

804
00:43:31,730 --> 00:43:34,705
quelle que soit notre taille est, cette
prend juste soin d'elle.

805
00:43:34,705 --> 00:43:36,080
Il est une façon un peu plus élégant.

806
00:43:36,080 --> 00:43:41,220
Et nous décrémentons juste notre
taille et ensuite revenir taille.

807
00:43:41,220 --> 00:43:42,330
Mmhmm?

808
00:43:42,330 --> 00:43:45,300
>> PUBLIC: Je pense juste en général,
Pourquoi serait-ce la structure de données

809
00:43:45,300 --> 00:43:47,800
être bénéfique?

810
00:43:47,800 --> 00:43:50,660
>> ENCEINTE 1: Cela dépend de votre contexte.

811
00:43:50,660 --> 00:43:57,420
Donc, pour une partie de la théorie,
si vous travaillez with-- OK,

812
00:43:57,420 --> 00:44:02,750
laissez-moi voir si il est un bénéfique
qui est avantageux à plus d'extérieur

813
00:44:02,750 --> 00:44:05,420
de CS.

814
00:44:05,420 --> 00:44:15,780
Avec des piles, à tout moment vous avez besoin
de garder une trace de quelque chose qui

815
00:44:15,780 --> 00:44:20,456
est le plus récemment ajouté est quand
vous allez avoir à utiliser une pile.

816
00:44:20,456 --> 00:44:24,770
>> Et je ne peux pas penser à une bonne
exemple de ce droit maintenant.

817
00:44:24,770 --> 00:44:29,955
Mais chaque fois que le plus récent
chose est plus important pour vous,

818
00:44:29,955 --> 00:44:31,705
qui est alors une pile
va être utile.

819
00:44:31,705 --> 00:44:35,797

820
00:44:35,797 --> 00:44:39,330
Je suis en train de penser si
il ya un bon pour cela.

821
00:44:39,330 --> 00:44:43,720
Si je pense à un bon exemple dans la prochaine
20 minutes, je vais certainement vous dire.

822
00:44:43,720 --> 00:44:49,455
>> Mais dans l'ensemble, si il ya quelque chose,
comme je l'ai dit plus, où la plus récente

823
00:44:49,455 --> 00:44:52,470
est le plus important, qui est
où une pile entre en jeu.

824
00:44:52,470 --> 00:44:58,860
Alors que les files d'attente sont un peu le contraire.

825
00:44:58,860 --> 00:44:59,870
Et tous les petits chiens.

826
00:44:59,870 --> 00:45:00,890
Est pas génial, non?

827
00:45:00,890 --> 00:45:03,299
Je me sens comme je le devrais
juste avoir une vidéo de lapin

828
00:45:03,299 --> 00:45:05,090
en plein milieu de
section pour vous les gars

829
00:45:05,090 --> 00:45:08,870
parce que cela est une section intense.

830
00:45:08,870 --> 00:45:10,480
>> Donc, une file d'attente.

831
00:45:10,480 --> 00:45:12,710
Fondamentalement, une file d'attente est comme une ligne.

832
00:45:12,710 --> 00:45:15,780
Vous les gars, je suis sûr que cette utilisation de tous les jours,
tout comme dans nos salles à manger.

833
00:45:15,780 --> 00:45:18,160
Nous devons donc aller dans
et obtenir nos plateaux, je suis

834
00:45:18,160 --> 00:45:21,260
que vous avez à attendre en ligne
de glisser ou obtenir votre nourriture.

835
00:45:21,260 --> 00:45:24,650
>> Donc, la différence ici
est l'existence de ce type FIFO.

836
00:45:24,650 --> 00:45:30,090
Donc, si LIFO était dernier entré, premier
out, FIFO est premier entré, premier sorti.

837
00:45:30,090 --> 00:45:33,400
Ce est donc là que vous avez mis
la première est votre plus importante.

838
00:45:33,400 --> 00:45:35,540
Donc, si vous attendiez
dans un line-- vous pouvez

839
00:45:35,540 --> 00:45:39,130
Imaginez si vous êtes allé à
aller chercher le nouvel iPhone

840
00:45:39,130 --> 00:45:42,800
et il avait une pile où le
dernière personne en ligne a obtenu le premier,

841
00:45:42,800 --> 00:45:44,160
les gens tuer les uns les autres.

842
00:45:44,160 --> 00:45:49,800
>> Donc FIFO, nous sommes tous très familiers
avec dans le monde réel ici,

843
00:45:49,800 --> 00:45:54,930
et il a tout à voir avec effectivement
sorte de recréer toute cette ligne

844
00:45:54,930 --> 00:45:56,900
et la structure de file d'attente.

845
00:45:56,900 --> 00:46:02,390
Ainsi, alors que la pile,
nous avons poussée et pop.

846
00:46:02,390 --> 00:46:06,440
Avec une file d'attente, nous avons
en file d'attente et dequeue.

847
00:46:06,440 --> 00:46:10,910
Donc en file d'attente signifie essentiellement
mettre sur le dos,

848
00:46:10,910 --> 00:46:13,680
et des moyens dequeue prennent
hors de l'avant.

849
00:46:13,680 --> 00:46:18,680
Donc, notre structure de données est un
peu plus compliqué.

850
00:46:18,680 --> 00:46:21,060
Nous avons un deuxième chose à garder la trace.

851
00:46:21,060 --> 00:46:25,950
>> Donc, sans la tête, cette
est exactement une pile, non?

852
00:46:25,950 --> 00:46:27,900
Ceci est la même structure que celle d'une pile.

853
00:46:27,900 --> 00:46:32,480
La seule chose différente est maintenant nous
avoir cette tête, qui que pensez-vous

854
00:46:32,480 --> 00:46:34,272
va suivre?

855
00:46:34,272 --> 00:46:35,510
>> AUDIENCE: Le premier.

856
00:46:35,510 --> 00:46:38,685
>> ENCEINTE 1: Droit, la
première chose que nous avons mis en.

857
00:46:38,685 --> 00:46:41,130
La tête de notre file d'attente.

858
00:46:41,130 --> 00:46:42,240
Celui qui est en première ligne.

859
00:46:42,240 --> 00:46:45,300

860
00:46:45,300 --> 00:46:49,420
Très bien, si nous faisons en file d'attente.

861
00:46:49,420 --> 00:46:52,720

862
00:46:52,720 --> 00:46:55,920
Encore une fois, avec l'un des
ces structures de données,

863
00:46:55,920 --> 00:46:59,760
puisque nous avons affaire à un tableau,
nous devons vérifier si nous avons de l'espace.

864
00:46:59,760 --> 00:47:03,290
>> Ceci est un peu comme me dire
vous les gars, si vous ouvrez un fichier,

865
00:47:03,290 --> 00:47:04,760
vous devez vérifier pour nulle.

866
00:47:04,760 --> 00:47:08,330
Avec l'une de ces piles
et les files d'attente, vous devez

867
00:47:08,330 --> 00:47:13,420
pour voir si il ya de l'espace parce que nous sommes
traiter avec une matrice de taille fixe,

868
00:47:13,420 --> 00:47:16,030
comme nous le voyons ici-- 0, 1 tout à 5.

869
00:47:16,030 --> 00:47:20,690
Donc, ce que nous faisons dans ce cas est de vérifier
pour voir si nous avons encore de la place.

870
00:47:20,690 --> 00:47:23,110
Est notre taille inférieure à la capacité?

871
00:47:23,110 --> 00:47:28,480
>> Si oui, nous avons besoin de les stocker à
la queue et nous mettons à jour notre taille.

872
00:47:28,480 --> 00:47:30,250
Alors, que peut-être la queue dans ce cas?

873
00:47:30,250 --> 00:47:32,360
Il est pas explicitement écrit sur.

874
00:47:32,360 --> 00:47:33,380
Comment pourrions-nous stocker?

875
00:47:33,380 --> 00:47:34,928
Qu'est-ce que la queue être?

876
00:47:34,928 --> 00:47:38,600

877
00:47:38,600 --> 00:47:40,190
>> Donc, nous allons marcher à travers cet exemple.

878
00:47:40,190 --> 00:47:44,590
Donc ceci est un tableau de taille 6, à droite?

879
00:47:44,590 --> 00:47:49,220
Et nous avons en ce moment, notre taille est 5.

880
00:47:49,220 --> 00:47:55,240
Et quand on le met dans, ça va
pour aller dans le cinquième indice, non?

881
00:47:55,240 --> 00:47:57,030
Donc stocker à queue.

882
00:47:57,030 --> 00:48:05,600
>> Une autre façon d'écrire la queue serait juste
être notre tableau à indice de la taille, non?

883
00:48:05,600 --> 00:48:07,560
Cette taille est 5.

884
00:48:07,560 --> 00:48:11,490
La prochaine chose va aller en 5.

885
00:48:11,490 --> 00:48:12,296
Cool?

886
00:48:12,296 --> 00:48:13,290
D'accord.

887
00:48:13,290 --> 00:48:16,350
Il devient un peu plus compliqué
quand nous commençons à jouer avec la tête.

888
00:48:16,350 --> 00:48:17,060
Oui?

889
00:48:17,060 --> 00:48:20,090
>> Public: Est-ce à dire que nous
aurait déclaré un tableau

890
00:48:20,090 --> 00:48:23,880
cinq éléments est longue et
puis nous ajoutons sur elle?

891
00:48:23,880 --> 00:48:24,730
>> ENCEINTE 1: Non

892
00:48:24,730 --> 00:48:27,560
Donc dans ce cas, cela est une pile.

893
00:48:27,560 --> 00:48:31,760
Ce serait déclarée
comme un tableau de taille 6.

894
00:48:31,760 --> 00:48:37,120
Et dans ce cas, nous
juste avoir une gauche de l'espace.

895
00:48:37,120 --> 00:48:42,720
>> OK, si une chose est dans ce
cas, si notre tête est à 0,

896
00:48:42,720 --> 00:48:45,270
alors nous ne pouvons l'ajouter à la taille.

897
00:48:45,270 --> 00:48:51,020
Mais il ya un peu plus délicat
parce qu'en fait, ils

898
00:48:51,020 --> 00:48:52,840
ne pas avoir une diapositive
pour cela, donc je vais

899
00:48:52,840 --> 00:48:56,670
de tirer un parce qu'il est pas
tout à fait aussi simple que cela une fois que vous

900
00:48:56,670 --> 00:48:59,230
commencer à se débarrasser de choses.

901
00:48:59,230 --> 00:49:03,920
Ainsi, alors que avec une pile
vous ne devez jamais

902
00:49:03,920 --> 00:49:08,920
à vous soucier de ce que la taille est
lorsque vous ajoutez quelque chose sur,

903
00:49:08,920 --> 00:49:15,710
avec une file d'attente, vous devez également faire
vous que votre tête est représenté,

904
00:49:15,710 --> 00:49:20,760
parce que quelque chose de cool à propos de files d'attente
est que si vous n'êtes pas à pleine capacité,

905
00:49:20,760 --> 00:49:23,040
vous pouvez réellement faire enrouler autour.

906
00:49:23,040 --> 00:49:28,810
>> OK, donc on chose-- oh,
cette craie est terrible.

907
00:49:28,810 --> 00:49:31,815
Une chose à considérer est le cas.

908
00:49:31,815 --> 00:49:35,514

909
00:49:35,514 --> 00:49:37,140
Nous allons juste faire cinq.

910
00:49:37,140 --> 00:49:41,810
OK, donc nous allons
dire la tête est ici.

911
00:49:41,810 --> 00:49:46,140
Ceci est égal à 0, 1, 2, 3, 4.

912
00:49:46,140 --> 00:49:54,210
>> La tête est là, et
se il vous plaît avoir des choses en eux.

913
00:49:54,210 --> 00:49:58,340
Et nous voulons ajouter quelque chose à, non?

914
00:49:58,340 --> 00:50:01,170
Donc, la chose que nous devons
savoir est que la tête est toujours

915
00:50:01,170 --> 00:50:05,620
va se déplacer de cette façon et
ensuite bouclé autour, OK?

916
00:50:05,620 --> 00:50:10,190
>> Donc, cette file d'attente possède un espace dédié, non?

917
00:50:10,190 --> 00:50:13,950
Il possède un espace dédié au tout début,
type de l'opposé de cela.

918
00:50:13,950 --> 00:50:17,920
Donc, ce que nous devons faire est nous
besoin de calculer la queue.

919
00:50:17,920 --> 00:50:20,530
Si vous savez que votre
tête n'a pas bougé, la queue

920
00:50:20,530 --> 00:50:24,630
est juste à votre tableau
l'indice de la taille.

921
00:50:24,630 --> 00:50:30,000
>> Mais en réalité, si vous utilisez une file d'attente,
votre tête est probablement mis à jour.

922
00:50:30,000 --> 00:50:33,890
Donc ce que vous devez faire est
en fait calculer la queue.

923
00:50:33,890 --> 00:50:39,990
Donc, ce que nous faisons est cette formule
ici, que je vais vous laisser

924
00:50:39,990 --> 00:50:42,680
les gars pensent, et
puis nous en reparlerons.

925
00:50:42,680 --> 00:50:49,567

926
00:50:49,567 --> 00:50:50,400
Donc, cette capacité est.

927
00:50:50,400 --> 00:50:55,890

928
00:50:55,890 --> 00:50:59,660
>> Donc, ce sera effectivement
vous donner un moyen de le faire.

929
00:50:59,660 --> 00:51:03,205

930
00:51:03,205 --> 00:51:04,330
Parce que dans ce cas, quoi?

931
00:51:04,330 --> 00:51:09,205
Notre siège est à 1, notre taille est 4.

932
00:51:09,205 --> 00:51:11,760

933
00:51:11,760 --> 00:51:18,490
Si nous mod que par 5, on obtient 0,
qui est l'endroit où nous devrions elle entrée.

934
00:51:18,490 --> 00:51:23,320

935
00:51:23,320 --> 00:51:26,080
>> Alors dans le cas suivant,
si nous devions le faire,

936
00:51:26,080 --> 00:51:33,390
nous disons, OK, nous allons DEQUEUE quelque chose.

937
00:51:33,390 --> 00:51:34,390
Nous DEQUEUE cela.

938
00:51:34,390 --> 00:51:37,740
Nous prenons à cet élément, non?

939
00:51:37,740 --> 00:51:47,930
>> Et maintenant, notre tête est pointé ici,
et nous voulons ajouter une autre chose.

940
00:51:47,930 --> 00:51:52,470
Ceci est essentiellement le
arrière de notre ligne, non?

941
00:51:52,470 --> 00:51:55,450
Les files d'attente peuvent enrouler autour du tableau.

942
00:51:55,450 --> 00:51:57,310
Voilà l'une des principales différences.

943
00:51:57,310 --> 00:51:58,780
Piles, vous ne pouvez pas faire cela.

944
00:51:58,780 --> 00:52:01,140
>> Avec les files d'attente, vous pouvez
parce que tout ce qui compte

945
00:52:01,140 --> 00:52:03,940
est que vous savez ce que
a été le plus récemment ajouté.

946
00:52:03,940 --> 00:52:10,650
Puisque tout va être ajoutée dans
cette direction vers la gauche, dans ce cas,

947
00:52:10,650 --> 00:52:16,480
et puis envelopper, vous pouvez
continuer à mettre de nouveaux éléments

948
00:52:16,480 --> 00:52:18,830
à l'avant de la matrice
car il est pas vraiment

949
00:52:18,830 --> 00:52:20,640
l'avant de la rangée plus.

950
00:52:20,640 --> 00:52:26,320
Vous pouvez penser le début de la
tableau comme lorsque votre tête est en réalité.

951
00:52:26,320 --> 00:52:29,710
>> Donc, cette formule est de savoir comment
vous calculez votre queue.

952
00:52:29,710 --> 00:52:32,780

953
00:52:32,780 --> 00:52:35,610
Est-ce que cela a un sens?

954
00:52:35,610 --> 00:52:36,110
D'accord.

955
00:52:36,110 --> 00:52:39,400

956
00:52:39,400 --> 00:52:44,040
OK, dequeue, puis
vous les gars avez 10 minutes

957
00:52:44,040 --> 00:52:48,840
à me poser des questions de clarification
vous voulez, parce que je sais qu'il est fou.

958
00:52:48,840 --> 00:52:51,980
>> Très bien, alors dans le même way--
Je ne sais pas si vous remarqué,

959
00:52:51,980 --> 00:52:53,450
mais CS est tout au sujet des motifs.

960
00:52:53,450 --> 00:52:57,370
Les choses sont à peu près la
même, juste de petits réglages.

961
00:52:57,370 --> 00:52:58,950
Donc même chose ici.

962
00:52:58,950 --> 00:53:04,040
Nous avons besoin de vérifier pour voir si nous avons effectivement
avoir quelque chose dans notre file d'attente, non?

963
00:53:04,040 --> 00:53:05,960
Dire, OK, est notre taille supérieure à 0?

964
00:53:05,960 --> 00:53:06,730
Laisser refroidir.

965
00:53:06,730 --> 00:53:10,690
>> Si nous le faisons, alors nous passons notre tête, qui
est ce que je viens de le démontrer ici.

966
00:53:10,690 --> 00:53:13,870
Nous mettons à jour notre tête à être un plus.

967
00:53:13,870 --> 00:53:18,390
Et puis nous avons notre décrémentons
taille et retourner l'élément.

968
00:53:18,390 --> 00:53:21,000

969
00:53:21,000 --> 00:53:26,250
>> Il est beaucoup plus concret
code sur study.cs50.net,

970
00:53:26,250 --> 00:53:29,440
et je vous recommande vivement d'y aller
à travers elle, si vous avez le temps,

971
00:53:29,440 --> 00:53:30,980
même si elle est juste un pseudo-code.

972
00:53:30,980 --> 00:53:35,980
Et si vous voulez les gars de parler à travers
qui avec moi sur une base individuelle, se il vous plaît laissez-moi

973
00:53:35,980 --> 00:53:37,500
savoir.

974
00:53:37,500 --> 00:53:38,770
Je serais heureux de le faire.

975
00:53:38,770 --> 00:53:42,720
Les structures de données, si
vous prenez CS 124, vous aurez

976
00:53:42,720 --> 00:53:47,830
savent que les structures de données deviennent très
amusant et ce ne fait que commencer.

977
00:53:47,830 --> 00:53:50,350
>> Donc, je sais qu'il est difficile.

978
00:53:50,350 --> 00:53:51,300
Ce est OK.

979
00:53:51,300 --> 00:53:52,410
Nous luttons.

980
00:53:52,410 --> 00:53:53,630
Je le fais toujours.

981
00:53:53,630 --> 00:53:56,660
Donc ne vous inquiétez pas trop à ce sujet.

982
00:53:56,660 --> 00:54:02,390
>> Mais qui est fondamentalement votre
Crash Course dans les structures de données.

983
00:54:02,390 --> 00:54:03,400
Je sais qu'il est beaucoup.

984
00:54:03,400 --> 00:54:06,860
Y at-il quelque chose que nous
voudrait aller encore?

985
00:54:06,860 --> 00:54:09,400
Tout ce que nous voulons parler à travers?

986
00:54:09,400 --> 00:54:10,060
Oui?

987
00:54:10,060 --> 00:54:16,525
>> Public: Pour cet exemple, si
la nouvelle queue est à 0 sur cela?

988
00:54:16,525 --> 00:54:17,150
ENCEINTE 1: Oui.

989
00:54:17,150 --> 00:54:18,230
PUBLIC: OK.

990
00:54:18,230 --> 00:54:24,220
Alors en passant par,
vous auriez 1 plus 4 ou--

991
00:54:24,220 --> 00:54:27,671
>> ENCEINTE 1: Donc vous disiez,
quand nous voulons aller le faire à nouveau?

992
00:54:27,671 --> 00:54:28,296
PUBLIC: Ouais.

993
00:54:28,296 --> 00:54:38,290
Donc, si vous déterminez out-- où sont
vous le calcul de la queue de dans tout cela?

994
00:54:38,290 --> 00:54:44,260
>> ENCEINTE 1: Donc la queue
Je suis in-- changé la donne.

995
00:54:44,260 --> 00:54:52,010
Ainsi, dans cet exemple ici, ce fut
le tableau que nous cherchons à, OK?

996
00:54:52,010 --> 00:54:54,670
Donc, nous avons des choses en 1, 2, 3, et 4.

997
00:54:54,670 --> 00:55:05,850
Donc, nous avons notre tête est égal à 1 à
ce point, et notre taille est égale à 4

998
00:55:05,850 --> 00:55:07,050
à ce moment, non?

999
00:55:07,050 --> 00:55:08,960
>> Vous conviendrez que ce soit le cas?

1000
00:55:08,960 --> 00:55:14,620
Nous faisons donc la tête, plus la taille, qui
nous donne 5, puis nous Mod par 5.

1001
00:55:14,620 --> 00:55:20,690
Nous obtenons 0, qui nous dit que 0 est
où est notre queue, où nous avons de l'espace.

1002
00:55:20,690 --> 00:55:22,010
>> Public: Qu'est-ce qu'un bouchon?

1003
00:55:22,010 --> 00:55:23,520
>> ENCEINTE 1: La capacité.

1004
00:55:23,520 --> 00:55:24,020
Désolé.

1005
00:55:24,020 --> 00:55:29,640
Voilà donc la taille de votre tableau.

1006
00:55:29,640 --> 00:55:35,210

1007
00:55:35,210 --> 00:55:36,047
Oui?

1008
00:55:36,047 --> 00:55:39,210
>> PUBLIC: [Inaudible] avant
nous revenons de l'élément?

1009
00:55:39,210 --> 00:55:46,270
>> ENCEINTE 1: Nous passons donc la
la tête ou retourner le moment?

1010
00:55:46,270 --> 00:55:52,680
Donc, si nous passons un, diminuer la taille?

1011
00:55:52,680 --> 00:55:54,150
Attendez.

1012
00:55:54,150 --> 00:55:55,770
Je certainement oublié un autre.

1013
00:55:55,770 --> 00:56:00,646

1014
00:56:00,646 --> 00:56:01,990
Ça ne fait rien.

1015
00:56:01,990 --> 00:56:04,980
Il n'y a pas une autre formule.

1016
00:56:04,980 --> 00:56:09,980
Ouais, vous voulez retourner
la tête, puis le reculer.

1017
00:56:09,980 --> 00:56:13,270
>> PUBLIC: OK, car à ce
stade, la tête était à 0,

1018
00:56:13,270 --> 00:56:18,452
et puis vous voulez retourner
index 0 et ensuite faire la tête 1?

1019
00:56:18,452 --> 00:56:19,870
>> ENCEINTE 1: Droit.

1020
00:56:19,870 --> 00:56:22,820
Je pense qu'il ya un autre
formule un peu comme cela.

1021
00:56:22,820 --> 00:56:26,970
Je ne l'ai pas sur le dessus de ma tête comme
Je ne veux pas vous donner le mauvais.

1022
00:56:26,970 --> 00:56:35,470
Mais je pense qu'il est tout à fait valable pour
par exemple, OK, entreposer ce quel que soit element--

1023
00:56:35,470 --> 00:56:40,759
l'élément de tête est-- décrémenter votre
taille, déplacez votre tête au-dessus, et retour

1024
00:56:40,759 --> 00:56:41,800
tout ce qui est élément.

1025
00:56:41,800 --> 00:56:44,760
Voilà tout à fait valable.

1026
00:56:44,760 --> 00:56:45,260
D'accord.

1027
00:56:45,260 --> 00:56:48,360

1028
00:56:48,360 --> 00:56:53,560
Je me sens comme ce ne sont pas
comme le most-- vous n'êtes pas

1029
00:56:53,560 --> 00:56:55,740
va sortir d'ici
comme, oui, je sais essais.

1030
00:56:55,740 --> 00:56:56,880
Je l'ai eu tout.

1031
00:56:56,880 --> 00:56:57,670
Ce est OK.

1032
00:56:57,670 --> 00:57:00,200
Je promets.

1033
00:57:00,200 --> 00:57:05,240
Mais les structures de données sont quelque chose que
il faut beaucoup de temps pour s'y habituer.

1034
00:57:05,240 --> 00:57:10,010
Probablement l'un des plus difficiles
choses, je pense que, dans le cours.

1035
00:57:10,010 --> 00:57:15,330
>> Donc, il faut certainement
répétition et la recherche at-- je

1036
00:57:15,330 --> 00:57:20,050
ne savait pas vraiment les listes chaînées
jusqu'à ce que je l'ai fait beaucoup trop avec eux,

1037
00:57:20,050 --> 00:57:22,550
de la même manière que je ne l'ai pas
vraiment comprendre pointeurs

1038
00:57:22,550 --> 00:57:27,040
jusqu'à ce que je l'ai eu à enseigner pour deux
ans et faire ma propre psets avec elle.

1039
00:57:27,040 --> 00:57:28,990
Il faut beaucoup de répétition et du temps.

1040
00:57:28,990 --> 00:57:32,600
Et finalement, il sorte de cliquer.

1041
00:57:32,600 --> 00:57:36,320
>> Mais en attendant, si vous avez genre
une compréhension de haut niveau de ce que

1042
00:57:36,320 --> 00:57:39,321
ceux-ci ne, leurs avantages
et qui est ce qui cons--

1043
00:57:39,321 --> 00:57:41,820
nous avons tendance vraiment à souligner,
en particulier dans le cadre de l'intro.

1044
00:57:41,820 --> 00:57:45,511
Comme, pourquoi devrions-nous utiliser
un essai sur un tableau?

1045
00:57:45,511 --> 00:57:48,010
Comme, ce sont les points positifs
et négatifs de chacune des personnes?

1046
00:57:48,010 --> 00:57:51,610
>> Et de comprendre les compromis
entre chacune de ces structures

1047
00:57:51,610 --> 00:57:54,910
est ce qui est beaucoup plus important en ce moment.

1048
00:57:54,910 --> 00:57:58,140
Il peut y avoir un fou
question ou deux qui est

1049
00:57:58,140 --> 00:58:03,710
vais vous demander de mettre en œuvre poussée ou
mettre en œuvre pop ou en file d'attente et dequeue.

1050
00:58:03,710 --> 00:58:07,340
Mais la plupart du temps, compte que
compréhension supérieure de niveau et plus

1051
00:58:07,340 --> 00:58:09,710
d'une compréhension intuitive est
en fait plus importante que

1052
00:58:09,710 --> 00:58:11,250
être en mesure de mettre en œuvre.

1053
00:58:11,250 --> 00:58:14,880
>> Ce serait vraiment génial si vous tous
pourrait sortir et aller mettre en œuvre un essai,

1054
00:58:14,880 --> 00:58:19,720
mais nous comprenons qu'il est pas nécessairement
la chose la plus raisonnable à l'heure actuelle.

1055
00:58:19,720 --> 00:58:23,370
Mais vous pouvez dans votre pset, si vous voulez
à, et puis vous aurez la pratique,

1056
00:58:23,370 --> 00:58:27,200
et puis peut-être vous
vraiment comprendre.

1057
00:58:27,200 --> 00:58:27,940
Oui?

1058
00:58:27,940 --> 00:58:30,440
>> PUBLIC: OK, donc ceux qui sont
nous voulions dire à utiliser dans le jeu de processeurs?

1059
00:58:30,440 --> 00:58:31,916
Dois-je utiliser l'un d'eux?

1060
00:58:31,916 --> 00:58:32,540
ENCEINTE 1: Oui.

1061
00:58:32,540 --> 00:58:34,199
Donc, vous avez le choix.

1062
00:58:34,199 --> 00:58:36,740
Je suppose que dans ce cas, nous pouvons
parler de l'ensemble de processeurs un peu

1063
00:58:36,740 --> 00:58:40,480
parce que je courais à travers ces.

1064
00:58:40,480 --> 00:58:47,779
Donc, à votre pset, vous avez votre
choix d'essais ou tables de hachage.

1065
00:58:47,779 --> 00:58:49,570
Certaines personnes vont essayer
et utiliser des filtres de floraison,

1066
00:58:49,570 --> 00:58:51,840
mais ceux-ci sont techniquement pas correct.

1067
00:58:51,840 --> 00:58:55,804
En raison de leur nature probabiliste,
ils donnent parfois des faux positifs.

1068
00:58:55,804 --> 00:58:57,095
Ils sont en look cool, cependant.

1069
00:58:57,095 --> 00:58:59,030
Je le recommande vivement à la recherche
à eux au moins.

1070
00:58:59,030 --> 00:59:03,260
Mais vous avez le choix
entre une table de hachage et un essai.

1071
00:59:03,260 --> 00:59:06,660
Et cela va être le cas
vous chargez dans votre dictionnaire.

1072
00:59:06,660 --> 00:59:09,230
>> Et vous aurez besoin de choisir
votre fonction de hachage,

1073
00:59:09,230 --> 00:59:13,420
vous aurez besoin de choisir combien de
seaux que vous avez, et il peut varier.

1074
00:59:13,420 --> 00:59:17,440
Comme si vous avez plus de seaux,
ce sera peut courir plus vite.

1075
00:59:17,440 --> 00:59:22,790
Mais peut-être vous perdez un
beaucoup d'espace de cette façon, si.

1076
00:59:22,790 --> 00:59:26,320
Vous devez comprendre.

1077
00:59:26,320 --> 00:59:27,140
Mmhmm?

1078
00:59:27,140 --> 00:59:29,875
>> Public: Vous avez dit avant que
nous pouvons utiliser d'autres fonctions de hachage,

1079
00:59:29,875 --> 00:59:31,750
que nous ne devons pas
créer une fonction de hachage?

1080
00:59:31,750 --> 00:59:32,666
>> ENCEINTE 1: Oui, à droite.

1081
00:59:32,666 --> 00:59:38,150
Donc littéralement pour votre fonction de hachage,
comme google "fonction de hachage"

1082
00:59:38,150 --> 00:59:40,770
et chercher des étés frais.

1083
00:59:40,770 --> 00:59:43,250
Vous n'êtes pas censé construire
vos propres fonctions de hachage.

1084
00:59:43,250 --> 00:59:46,100
Les gens passent leur
thèses sur ces choses.

1085
00:59:46,100 --> 00:59:50,250
>> Ne vous inquiétez donc pas de construire votre propre.

1086
00:59:50,250 --> 00:59:53,350
Trouver une à commencer par ligne.

1087
00:59:53,350 --> 00:59:56,120
Certains d'entre eux vous devez
manipuler un peu

1088
00:59:56,120 --> 00:59:59,430
à veiller à ce que les types de retour correspondent
et ainsi de suite, si au début,

1089
00:59:59,430 --> 01:00:02,420
Je vous conseille d'utiliser quelque chose
vraiment facile que peut-être juste

1090
01:00:02,420 --> 01:00:04,680
hache sur la première lettre.

1091
01:00:04,680 --> 01:00:08,760
Et puis une fois que vous avez ce travail,
intégrant une fonction de hachage refroidisseur.

1092
01:00:08,760 --> 01:00:09,260
Mmhmm?

1093
01:00:09,260 --> 01:00:13,020
>> PUBLIC: Serait un essai ou être
efficace, mais juste plus difficile à, like--

1094
01:00:13,020 --> 01:00:15,880
>> ENCEINTE 1: Donc un essai, je pense,
est intuitivement difficile à mettre en œuvre

1095
01:00:15,880 --> 01:00:18,310
mais est très rapide.

1096
01:00:18,310 --> 01:00:20,620
Cependant, prend plus de place.

1097
01:00:20,620 --> 01:00:25,270
Encore une fois, vous pouvez optimiser à la fois de ceux qui en
différentes façons et il existe des moyens to--

1098
01:00:25,270 --> 01:00:26,770
Public: Comment sommes-nous classés sur ce?

1099
01:00:26,770 --> 01:00:27,540
Est-ce matter--

1100
01:00:27,540 --> 01:00:29,164
>> ENCEINTE 1: Vous êtes donc classés de façon normale.

1101
01:00:29,164 --> 01:00:31,330
Vous allez être classé sur la conception.

1102
01:00:31,330 --> 01:00:36,020
Quelle que soit la façon dont vous le faites, vous voulez
assurez-vous qu'il est aussi élégant que peut être

1103
01:00:36,020 --> 01:00:38,610
et aussi efficace que possible.

1104
01:00:38,610 --> 01:00:41,950
Mais si vous choisissez un essai ou hachage
table, tant que cela fonctionne,

1105
01:00:41,950 --> 01:00:45,350
nous sommes heureux.

1106
01:00:45,350 --> 01:00:48,370
Et si vous utilisez quelque chose qui hachages
sur la première lettre, qui est très bien,

1107
01:00:48,370 --> 01:00:51,410
comme peut-être comme du design.

1108
01:00:51,410 --> 01:00:53,410
Nous sommes également d'atteindre le
point de cette semester--

1109
01:00:53,410 --> 01:00:55,340
Je ne sais pas si vous
noticed-- gars si vous êtes

1110
01:00:55,340 --> 01:00:58,780
grades pset diminuent un peu
en raison de la conception et ainsi de suite,

1111
01:00:58,780 --> 01:00:59,900
qui est parfaitement bien.

1112
01:00:59,900 --> 01:01:02,960
Il se fait à un point où votre
programmes sont de plus compliqué.

1113
01:01:02,960 --> 01:01:04,830
Il ya plus de places
vous pouvez améliorer.

1114
01:01:04,830 --> 01:01:06,370
>> Ainsi, il est parfaitement normal.

1115
01:01:06,370 --> 01:01:08,810
Il est pas que vous êtes
faire pire sur votre pset.

1116
01:01:08,810 --> 01:01:11,885
Il est juste que nous allons être plus difficile sur vous maintenant.

1117
01:01:11,885 --> 01:01:13,732
Donc tout le monde se sent elle.

1118
01:01:13,732 --> 01:01:14,940
Je viens graduée tous vos psets.

1119
01:01:14,940 --> 01:01:16,490
Je sais que tout le monde se sent elle.

1120
01:01:16,490 --> 01:01:19,600
>> Alors ne soyez pas inquiet à ce sujet.

1121
01:01:19,600 --> 01:01:23,580
Et si vous avez des questions au sujet
psets antérieures ou des façons dont vous pouvez améliorer,

1122
01:01:23,580 --> 01:01:27,760
Je tente de commenter le spécifique
endroits, mais parfois il est tard

1123
01:01:27,760 --> 01:01:30,840
et je suis fatigué.

1124
01:01:30,840 --> 01:01:34,885
Y at-il d'autres choses
sur les structures de données?

1125
01:01:34,885 --> 01:01:37,510
Je suis sûr que vous les gars ne le faites pas vraiment
vouloir en parler plus,

1126
01:01:37,510 --> 01:01:42,650
mais si il ya, je suis heureux de
passer en revue, ainsi que tout

1127
01:01:42,650 --> 01:01:45,580
de conférence dernier
semaine ou la semaine dernière.

1128
01:01:45,580 --> 01:01:51,580
>> Je sais que la semaine dernière était tout contrôle, si
nous avons peut-être sauté quelques examen

1129
01:01:51,580 --> 01:01:54,190
de conférence.

1130
01:01:54,190 --> 01:01:58,230
Toutes les autres questions auxquelles je peux répondre?

1131
01:01:58,230 --> 01:01:59,350
OK, d'accord.

1132
01:01:59,350 --> 01:02:02,400
Eh bien, les gars sortir 15 minutes plus tôt.

1133
01:02:02,400 --> 01:02:08,370
>> Je espère que cette était semi-utile au moins,
et je vais vous voir les gars la semaine prochaine,

1134
01:02:08,370 --> 01:02:12,150
ou jeudi les heures de bureau.

1135
01:02:12,150 --> 01:02:15,285
Existe-t-il des demandes pour les collations
pour la semaine prochaine, il est la chose?

1136
01:02:15,285 --> 01:02:17,459
Parce que je oublié bonbons aujourd'hui.

1137
01:02:17,459 --> 01:02:19,750
Je fis bonbons dernier
semaine, mais il était Columbus Day,

1138
01:02:19,750 --> 01:02:25,400
donc il y avait comme six personnes
avait quatre sacs de bonbons pour eux-mêmes.

1139
01:02:25,400 --> 01:02:28,820
Je peux apporter Starbursts
nouveau si vous le souhaitez.

1140
01:02:28,820 --> 01:02:29,580
Starbursts?

1141
01:02:29,580 --> 01:02:32,250
OK, sonne bien.

1142
01:02:32,250 --> 01:02:35,050
Avoir un grand jour, les gars.

1143
01:02:35,050 --> 01:02:39,510