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

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI PENG: Bienvenue à la semaine 6 de l'article.

4
00:00:08,210 --> 00:00:11,620
Nous dévié de notre norme
section du temps du mardi

5
00:00:11,620 --> 00:00:14,130
après-midi pour ce beau dimanche matin.

6
00:00:14,130 --> 00:00:17,330
Merci pour tout le monde que
joint à moi aujourd'hui, mais sérieusement,

7
00:00:17,330 --> 00:00:18,170
une salve d'applaudissements.

8
00:00:18,170 --> 00:00:20,600
>> Voilà un joli gros effort.

9
00:00:20,600 --> 00:00:23,600
Je failli ne même pas se rendre
dans le temps, mais il a été OK.

10
00:00:23,600 --> 00:00:27,520
Donc, je sais que vous tous
ont simplement rendu au quiz.

11
00:00:27,520 --> 00:00:30,370
Tout d'abord, bienvenue à
le revers de la médaille.

12
00:00:30,370 --> 00:00:32,917
>> Deuxièmement, nous en reparlerons.

13
00:00:32,917 --> 00:00:34,000
Nous parlerons du quiz.

14
00:00:34,000 --> 00:00:35,700
Nous allons parler de la façon dont
vous faites dans la classe.

15
00:00:35,700 --> 00:00:36,550
Ça ira.

16
00:00:36,550 --> 00:00:39,080
Je dois vos quiz pour
vous à la fin d'ici,

17
00:00:39,080 --> 00:00:42,120
Donc, si vous voulez les gars à prendre
un regard sur elle, tout à fait bien.

18
00:00:42,120 --> 00:00:46,590
>> Si vite avant que nous commencions, le
l'ordre du jour d'aujourd'hui est comme suit.

19
00:00:46,590 --> 00:00:48,430
Comme vous pouvez le voir, nous sommes
tir essentiellement rapide

20
00:00:48,430 --> 00:00:52,120
grâce à tout un tas de structures de données
vraiment, vraiment, vraiment vite.

21
00:00:52,120 --> 00:00:54,380
Donc, à ce titre, il ne sera pas
aujourd'hui super-interactive.

22
00:00:54,380 --> 00:00:59,620
Il va juste être moi sorte de crier
choses que vous, et si je vous confondre,

23
00:00:59,620 --> 00:01:02,680
si je vais trop vite, faites le moi savoir.

24
00:01:02,680 --> 00:01:05,200
Ils sont juste différentes données
structures, et dans le cadre

25
00:01:05,200 --> 00:01:07,070
de votre pset pour cette
semaine prochaine, vous aurez

26
00:01:07,070 --> 00:01:10,340
être invité à mettre en œuvre l'un d'eux,
peut-être deux des eux-- deux d'entre eux

27
00:01:10,340 --> 00:01:12,319
dans votre pset.

28
00:01:12,319 --> 00:01:14,610
OK, donc je vais juste
commencer avec quelques annonces.

29
00:01:14,610 --> 00:01:19,070
Nous irons au-dessus des piles et des files d'attente plus dans
profondeur que ce que nous avons fait avant le quiz.

30
00:01:19,070 --> 00:01:20,990
Nous allons passer en revue liés
la liste de nouveau, une fois de plus,

31
00:01:20,990 --> 00:01:23,899
plus en profondeur que ce que
nous avions avant le quiz.

32
00:01:23,899 --> 00:01:26,440
Et puis nous allons parler de hachage
tables, arbres et essais, qui

33
00:01:26,440 --> 00:01:28,890
sont tous très nécessaire pour votre pset.

34
00:01:28,890 --> 00:01:32,925
Et puis nous allons passer en revue certaines
conseils utiles pour pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, donc quizz 0.

36
00:01:37,360 --> 00:01:41,090
La moyenne était de 58%.

37
00:01:41,090 --> 00:01:45,370
Il était très faible, et tout ce que vous les gars
a très, très bien en conformité

38
00:01:45,370 --> 00:01:46,510
avec ça.

39
00:01:46,510 --> 00:01:49,970
>> Pretty much, règle de base est que si vous êtes
l'intérieur d'un écart-type de la moyenne

40
00:01:49,970 --> 00:01:52,990
surtout depuis que nous sommes dans un moins
section confortable, vous êtes tout à fait bien.

41
00:01:52,990 --> 00:01:54,120
Vous êtes sur la bonne voie.

42
00:01:54,120 --> 00:01:55,190
La vie est belle.

43
00:01:55,190 --> 00:01:58,952
>> Je sais qu'il est effrayant de penser que
Je suis comme un 40% sur ce quiz.

44
00:01:58,952 --> 00:02:00,160
Je vais à l'échec cette classe.

45
00:02:00,160 --> 00:02:02,243
Je vous promets, vous n'êtes pas
aller à l'échec de la classe.

46
00:02:02,243 --> 00:02:03,680
Vous êtes tout à fait bien.

47
00:02:03,680 --> 00:02:06,850
>> Pour ceux d'entre vous qui a obtenu plus de
la moyenne, impressionnante, impressionnante,

48
00:02:06,850 --> 00:02:08,780
comme, bien fait au sérieux.

49
00:02:08,780 --> 00:02:09,689
Je les ai avec moi.

50
00:02:09,689 --> 00:02:11,730
Sentez-vous libre de venir les faire
à la fin de l'article.

51
00:02:11,730 --> 00:02:14,520
Faites-moi savoir si vous avez une
questions, des questions avec eux.

52
00:02:14,520 --> 00:02:17,204
Si nous ajoutons votre score
mal, laissez-nous savoir.

53
00:02:17,204 --> 00:02:21,240
>> OK, donc pset5, cela est vraiment
semaine bizarre pour Yale dans le sens

54
00:02:21,240 --> 00:02:24,240
que notre pset est dû
Mercredi à midi, y compris

55
00:02:24,240 --> 00:02:27,317
la fin du jour, il est donc en fait
théoriquement dû mardi à midi.

56
00:02:27,317 --> 00:02:29,150
Probablement personne ne terminé
Mardi à midi.

57
00:02:29,150 --> 00:02:30,830
Voilà tout à fait bien.

58
00:02:30,830 --> 00:02:33,700
Nous allons avoir des heures de bureau
ce soir, ainsi que lundi soir.

59
00:02:33,700 --> 00:02:36,810
Et toutes les sections cette semaine
effectivement être transformée en ateliers,

60
00:02:36,810 --> 00:02:38,800
donc sentir libre de pop
une section que vous voulez,

61
00:02:38,800 --> 00:02:42,810
et ils seront sorte de mini-pset
ateliers d'aide à ce sujet.

62
00:02:42,810 --> 00:02:45,620
Donc, en tant que telle, cette section est le seul
où nous sommes matériel pédagogique.

63
00:02:45,620 --> 00:02:49,220
Toutes les autres sections se concentreront
exclusivement sur l'aide pour le pset.

64
00:02:49,220 --> 00:02:50,146
Ouais?

65
00:02:50,146 --> 00:02:52,000
>> AUDIENCE: Où sont les heures de bureau?

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG: heures de bureau
de ce soir Oh, bonne question.

67
00:02:56,120 --> 00:03:00,580
Je pense que les heures de bureau ce soir
sont en Teal ou communes.

68
00:03:00,580 --> 00:03:02,984
Si vous cochez ligne CS50
et vous allez à des heures de bureau,

69
00:03:02,984 --> 00:03:05,650
il devrait y avoir un calendrier qui
vous où ils sont tous dit.

70
00:03:05,650 --> 00:03:07,954
>> Je sais que ce soir soit
ou demain est sarcelle d'hiver,

71
00:03:07,954 --> 00:03:10,120
et je pense que nous pouvons avoir
communes pour l'autre soir.

72
00:03:10,120 --> 00:03:11,020
Je ne suis pas sûr.

73
00:03:11,020 --> 00:03:11,700
Bonne question.

74
00:03:11,700 --> 00:03:14,430
Vérifiez sur CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, des questions concernant le
calendrier pour la prochaine comme trois jours?

76
00:03:18,780 --> 00:03:21,690
Je vous promets que des gars comme David
dit, ceci est le sommet de la colline.

77
00:03:21,690 --> 00:03:23,050
Les gars, vous y êtes presque.

78
00:03:23,050 --> 00:03:24,644
Seulement trois jours de plus.

79
00:03:24,644 --> 00:03:26,310
Allez-y, puis nous allons tous descendre.

80
00:03:26,310 --> 00:03:28,114
Nous aurons une pause agréable CS-libre.

81
00:03:28,114 --> 00:03:28,780
Nous y reviendrons.

82
00:03:28,780 --> 00:03:30,779
Nous allons plonger dans web
la programmation et le développement,

83
00:03:30,779 --> 00:03:35,150
des choses qui sont très amusant comparés
pour d'autres psets.

84
00:03:35,150 --> 00:03:37,974
Et ça va être froid, et
nous aurons beaucoup de plaisir.

85
00:03:37,974 --> 00:03:38,890
Nous aurons plus de bonbons.

86
00:03:38,890 --> 00:03:39,730
Désolé pour les bonbons.

87
00:03:39,730 --> 00:03:40,945
Je oublié bonbons.

88
00:03:40,945 --> 00:03:43,310
Ce fut une matinée difficile.

89
00:03:43,310 --> 00:03:46,340
Alors vous les gars y êtes presque,
et je suis vraiment fier de vous les gars.

90
00:03:46,340 --> 00:03:49,570
>> OK, donc piles.

91
00:03:49,570 --> 00:03:53,331
Qui aimait la question à propos de Jack
et son vêtement sur le quiz?

92
00:03:53,331 --> 00:03:53,830
Personne?

93
00:03:53,830 --> 00:03:56,500
OK, c'est bon.

94
00:03:56,500 --> 00:04:00,200
>> Donc, essentiellement, que vous le pouvez
Image Jack, ce gars-là,

95
00:04:00,200 --> 00:04:03,350
aime prendre les vêtements
sur le dessus de la pile,

96
00:04:03,350 --> 00:04:05,750
et il la remet sur
la pile après qu'il a fait.

97
00:04:05,750 --> 00:04:07,600
Donc, de cette manière, il n'a jamais
semble se

98
00:04:07,600 --> 00:04:10,090
au fond de la
empiler dans ses vêtements.

99
00:04:10,090 --> 00:04:12,600
Donc, ce genre de décrit
la structure de base de données

100
00:04:12,600 --> 00:04:16,610
de la manière dont est mis en oeuvre d'une pile.

101
00:04:16,610 --> 00:04:20,060
>> Essentiellement, penser à un
empiler comme toute pile d'objets

102
00:04:20,060 --> 00:04:24,900
où vous mettez les choses sur le dessus, et
puis vous sautez les sortir par le haut.

103
00:04:24,900 --> 00:04:28,600
Donc LIFO est l'acronyme nous aimons
à use-- Last In, First Out.

104
00:04:28,600 --> 00:04:32,480
Et ainsi de durer dans le haut de la
pile est le premier qui sort.

105
00:04:32,480 --> 00:04:34,260
Et ainsi les deux termes
nous aimons associer

106
00:04:34,260 --> 00:04:36,190
avec ce que l'on appelle poussée et pop.

107
00:04:36,190 --> 00:04:39,790
Quand vous poussez quelque chose sur le
pile, et vous sautez le sauvegarder.

108
00:04:39,790 --> 00:04:43,422
>> Et donc je suppose que cela est une sorte de
concept abstrait pour ceux d'entre vous

109
00:04:43,422 --> 00:04:45,630
qui veulent voir comme un
mise en œuvre effective de cette

110
00:04:45,630 --> 00:04:46,740
dans le monde réel.

111
00:04:46,740 --> 00:04:50,170
Combien d'entre vous ont écrit un essai
peut-être comme une heure avant l'échéance,

112
00:04:50,170 --> 00:04:54,510
et vous avez accidentellement supprimé un énorme
morceau de celui-ci, comme par hasard?

113
00:04:54,510 --> 00:04:58,560
Et puis ce contrôle ne
que nous utilisons pour le remettre?

114
00:04:58,560 --> 00:05:00,030
Ctrl-Z, ouais?

115
00:05:00,030 --> 00:05:03,640
Ctrl-Z, de sorte que le nombre de fois
que Control-Z a sauvé ma vie,

116
00:05:03,640 --> 00:05:08,820
a sauvé mon cul, à chaque fois
qui est implémenté par une cheminée.

117
00:05:08,820 --> 00:05:13,020
>> Essentiellement toutes les informations
qui est sur votre document Word,

118
00:05:13,020 --> 00:05:15,080
il est poussé et a sauté à volonté.

119
00:05:15,080 --> 00:05:19,460
Et si essentiellement chaque fois que vous
supprimer quoi que ce soit, vous sautez le sauvegarder.

120
00:05:19,460 --> 00:05:22,820
Et puis si vous avez besoin de retour, vous
pousser, ce qui est ce que Control-C fait.

121
00:05:22,820 --> 00:05:26,770
Et si la fonction du monde réel
de la structure de données comment simple

122
00:05:26,770 --> 00:05:28,690
peut vous aider avec votre vie quotidienne.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Donc, une structure est la façon dont
nous créons en fait une pile.

125
00:05:40,150 --> 00:05:44,720
Nous tapons définir struct, puis
nous l'appelons pile au fond.

126
00:05:44,720 --> 00:05:47,440
Et au sein de la pile,
nous avons deux paramètres

127
00:05:47,440 --> 00:05:51,580
que nous pouvons essentiellement manipuler,
nous avons donc omble capacité cordes étoiles.

128
00:05:51,580 --> 00:05:55,150
>> Tout ce qu'il fait
est la création d'un tableau

129
00:05:55,150 --> 00:05:58,835
que nous pouvons stocker ce que vous voulez
que nous pouvons déterminer sa capacité.

130
00:05:58,835 --> 00:06:01,990
Capacité est juste le montant maximum de
articles que nous pouvons mettre dans ce tableau.

131
00:06:01,990 --> 00:06:05,660
int size est le compteur qui maintient
la trace de la façon dont de nombreux éléments sont actuellement

132
00:06:05,660 --> 00:06:07,850
dans la pile.

133
00:06:07,850 --> 00:06:11,860
Alors nous pouvons suivre, A,
à la fois la taille de la pile est réelle,

134
00:06:11,860 --> 00:06:14,850
et, B, combien de cette pile
nous avons rempli parce que nous ne voulons pas

135
00:06:14,850 --> 00:06:18,800
à déborder sur ce que notre capacité est.

136
00:06:18,800 --> 00:06:24,340
>> Ainsi, par exemple, cette belle
question était sur votre quiz.

137
00:06:24,340 --> 00:06:28,160
Essentiellement, comment pouvons-nous poussons
sur le dessus d'une pile.

138
00:06:28,160 --> 00:06:28,830
Assez simple.

139
00:06:28,830 --> 00:06:30,621
Si vous regardez,
nous marcherons à travers cela.

140
00:06:30,621 --> 00:06:32,640
Si [inaudible] size--
rappelez-vous, chaque fois que vous

141
00:06:32,640 --> 00:06:35,300
vouloir accéder à tout
paramètre dans une structure,

142
00:06:35,300 --> 00:06:40,320
vous faites le nom de la struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> Dans ce cas, s est
le nom de notre pile.

144
00:06:42,720 --> 00:06:46,230
Nous voulons accéder à la taille
de celui-ci, de sorte que nous faisons s.size.

145
00:06:46,230 --> 00:06:50,280
Donc, tant que la taille est pas
égal à la capacité ou aussi longtemps

146
00:06:50,280 --> 00:06:52,940
comme il est inférieure à la capacité,
soit serait travailler ici.

147
00:06:52,940 --> 00:06:57,180
>> Vous voulez accéder à l'intérieur
de votre pile, donc s.strings,

148
00:06:57,180 --> 00:07:00,790
et vous allez mettre ce nouveau numéro
que vous souhaitez insérer dans il.

149
00:07:00,790 --> 00:07:05,030
Disons simplement que nous voudrons
insérer int n sur la pile,

150
00:07:05,030 --> 00:07:08,905
nous pourrions faire s.strings,
crochets, s.size équivaut n.

151
00:07:08,905 --> 00:07:11,030
Parce que la taille est où nous
sont actuellement dans la pile

152
00:07:11,030 --> 00:07:14,590
si nous allons pousser
sur, nous accédons à juste

153
00:07:14,590 --> 00:07:17,370
où la taille est, la
plénitude courant de la pile,

154
00:07:17,370 --> 00:07:21,729
et nous poussons l'int n sur elle.

155
00:07:21,729 --> 00:07:24,770
Et puis, nous voulons faire en sorte que
nous sommes également incrémenter taille de la n,

156
00:07:24,770 --> 00:07:27,436
afin que nous puissions garder une trace de nous avons
ajouté une chose supplémentaire à la pile.

157
00:07:27,436 --> 00:07:29,660
Maintenant, nous avons une plus grande taille.

158
00:07:29,660 --> 00:07:33,196
Est-ce ici de sens pour
tout le monde, comment logiquement ça marche?

159
00:07:33,196 --> 00:07:34,160
Il était une sorte de rapide.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
AUDIENCE: Pouvez-vous revenir sur
les s.stringss.strings [s.size] à nouveau?

162
00:07:42,160 --> 00:07:45,808
ANDI PENG: Bien sûr, si ce que fait
s.size actuellement nous donner?

163
00:07:45,808 --> 00:07:47,440
PUBLIC: Il est la taille actuelle.

164
00:07:47,440 --> 00:07:50,890
ANDI PENG: Exactement, de sorte que le
index courant que notre taille est à,

165
00:07:50,890 --> 00:07:57,780
et donc nous voulons mettre le nouvel entier
que nous voulons insérer dans s.size.

166
00:07:57,780 --> 00:07:58,760
Cela a-t-il du sens?

167
00:07:58,760 --> 00:08:01,110
Parce s.strings, tout ce qui
est est le nom du tableau.

168
00:08:01,110 --> 00:08:03,510
Tout ce qu'il est est l'accès à la
réseau au sein de notre structure,

169
00:08:03,510 --> 00:08:06,030
et si nous voulons
n placer dans cet indice,

170
00:08:06,030 --> 00:08:09,651
nous ne pouvons y accéder
à l'aide de crochets s.size.

171
00:08:09,651 --> 00:08:10,150
Frais.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Tout droit, pop, je Pseudocode it out
pour vous les gars, mais concept similaire.

174
00:08:18,916 --> 00:08:19,790
Cela a-t-il du sens?

175
00:08:19,790 --> 00:08:22,310
Si la taille est supérieure
à zéro, alors vous

176
00:08:22,310 --> 00:08:25,350
savez que vous voulez prendre quelque chose
parce que si la taille est pas

177
00:08:25,350 --> 00:08:27,620
supérieur à zéro, alors vous
rien avoir dans la pile.

178
00:08:27,620 --> 00:08:29,840
>> Donc, vous voulez seulement exécuter
ce code, il ne peut

179
00:08:29,840 --> 00:08:32,320
pop si il ya quelque chose à la musique pop.

180
00:08:32,320 --> 00:08:35,830
Donc, si la taille est plus grande
à 0, nous moins la taille.

181
00:08:35,830 --> 00:08:40,020
Nous décrémentons la taille et ensuite revenir
tout ce qui est à l'intérieur de celui-ci, car

182
00:08:40,020 --> 00:08:42,710
en faisant éclater, nous voulons
accès tout ce qui est stocké

183
00:08:42,710 --> 00:08:45,694
l'indice du sommet de la pile.

184
00:08:45,694 --> 00:08:46,610
Tout a un sens?

185
00:08:46,610 --> 00:08:49,693
Si je vous ai fait les gars écrivez ceci,
feriez-vous les gars être capable de l'écrire?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
OK, les gars vous pouvez jouer avec elle.

188
00:08:53,570 --> 00:08:55,252
Pas de soucis si vous ne l'obtiennent pas.

189
00:08:55,252 --> 00:08:57,460
Nous ne disposons pas des temps de coder
il aujourd'hui parce que nous avons

190
00:08:57,460 --> 00:08:59,959
a obtenu un grand nombre de ces structures
à passer, mais essentiellement

191
00:08:59,959 --> 00:09:02,214
pseudo, très, très semblable à pousser.

192
00:09:02,214 --> 00:09:03,380
Il suffit de suivre le long de la logique.

193
00:09:03,380 --> 00:09:06,092
Assurez-vous d'accéder à toutes les
caractéristiques de votre struct correctement.

194
00:09:06,092 --> 00:09:06,574
Ouais?

195
00:09:06,574 --> 00:09:09,282
>> AUDIENCE: Will ces diapositives et
tout cela soit aujourd'hui à la rigueur?

196
00:09:09,282 --> 00:09:11,586
ANDI PENG: Toujours, oui.

197
00:09:11,586 --> 00:09:13,710
Je vais essayer de mettre
cette place comme une heure après.

198
00:09:13,710 --> 00:09:16,626
Je vais écrivez-David, David va essayer de
mettre en place comme une heure après cela.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> OK, alors nous entrons dans cette autre
belle structure de données appelée une file d'attente.

201
00:09:25,470 --> 00:09:30,140
Comme vous les gars pouvez le voir ici, un
file d'attente, pour les Britanniques parmi nous,

202
00:09:30,140 --> 00:09:32,010
tout ce qu'il est est une ligne.

203
00:09:32,010 --> 00:09:34,680
Donc, contrairement à ce que
vous pensez est une pile,

204
00:09:34,680 --> 00:09:37,750
une file d'attente est exactement ce que
logiquement vous pensez qu'il est.

205
00:09:37,750 --> 00:09:41,914
Il est tenu par les règles de FIFO,
qui est First In, First Out.

206
00:09:41,914 --> 00:09:43,705
Si vous êtes le premier
l'un dans la ligne, vous êtes

207
00:09:43,705 --> 00:09:46,230
le premier qui
qui sort de la ligne.

208
00:09:46,230 --> 00:09:49,680
>> Donc, ce que nous aimons appeler cette
est dequeueing et enqueueing.

209
00:09:49,680 --> 00:09:52,380
Si nous voulons ajouter quelque chose
à notre attente, nous ENQUEUE.

210
00:09:52,380 --> 00:09:55,690
Si nous voulons dequeue, ou de prendre
quelque chose, nous DEQUEUE.

211
00:09:55,690 --> 00:10:03,350
>> Alors même sens que nous sommes en quelque sorte
la création d'éléments de taille fixe que nous

212
00:10:03,350 --> 00:10:06,500
peut stocker certaines
les choses, mais nous pouvons aussi

213
00:10:06,500 --> 00:10:10,100
changer l'endroit où nous allons placer
les paramètres à l'intérieur de

214
00:10:10,100 --> 00:10:13,140
sur la base de ce type de
fonctionnalité que nous voulons.

215
00:10:13,140 --> 00:10:16,700
Donc, piles, nous voulions le dernier
l'un, N pour être le premier à sortir.

216
00:10:16,700 --> 00:10:19,800
File d'attente est que nous voulons la première chose
pour être la première chose sur.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Ainsi, le type de structure
définir, comme vous pouvez le voir,

219
00:10:26,710 --> 00:10:29,470
il est un peu différent
de ce que la pile était

220
00:10:29,470 --> 00:10:33,120
parce que non seulement nous avons à garder
trace d'où la taille est actuellement,

221
00:10:33,120 --> 00:10:37,420
nous voulons aussi garder une trace de la tête
ainsi que là où nous sommes actuellement.

222
00:10:37,420 --> 00:10:39,580
Donc, je pense qu'il est plus facile
si je tire cette place.

223
00:10:39,580 --> 00:10:53,270
Donc, imaginons que nous avons une file d'attente,
alors disons la tête est ici.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
La tête de la ligne, nous allons
juste dire que ce moment là,

226
00:10:58,310 --> 00:11:01,809
et nous voulons insérer
quelque chose dans la file d'attente.

227
00:11:01,809 --> 00:11:04,350
Je vais appeler la taille essentiellement
est la même chose que la queue,

228
00:11:04,350 --> 00:11:06,314
la fin de la mesure de votre file d'attente est.

229
00:11:06,314 --> 00:11:07,730
Disons simplement que la taille est juste ici.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Alors, comment peut-on réalistement
insérer quelque chose dans une file d'attente?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
Qu'est-ce que l'indice voulons-nous placer
où nous voulons insérer dans.

234
00:11:24,130 --> 00:11:29,320
Si tel est le début de votre
la file d'attente, ce qui est la fin de celui-

235
00:11:29,320 --> 00:11:31,860
ou de la taille de celui-ci, où allons-nous
vouloir ajouter l'objet suivant?

236
00:11:31,860 --> 00:11:32,920
>> AUDIENCE: [inaudible]

237
00:11:32,920 --> 00:11:35,920
ANDI PENG: Exactement, vous voulez ajouter
il selon vous ai écrit il.

238
00:11:35,920 --> 00:11:37,840
Soit ce est vide ou qui est vide.

239
00:11:37,840 --> 00:11:42,630
Donc, vous voulez probablement ajouter
ici parce que si la taille est--

240
00:11:42,630 --> 00:11:50,540
si ceux-ci sont tous pleins, vous voulez
pour l'ajouter ici, non?

241
00:11:50,540 --> 00:11:57,150
>> Et donc voilà, alors que très, très
simple, pas tout à fait toujours correct

242
00:11:57,150 --> 00:12:00,690
parce que la différence principale
entre une file d'attente et une pile

243
00:12:00,690 --> 00:12:04,350
est ce que la file d'attente peut
en fait être manipulé

244
00:12:04,350 --> 00:12:06,980
de sorte que les changements de tête
selon l'endroit où vous voulez

245
00:12:06,980 --> 00:12:08,650
le début de votre signal pour commencer.

246
00:12:08,650 --> 00:12:11,900
Et en conséquence, votre queue
va également changer.

247
00:12:11,900 --> 00:12:14,770
Et ainsi de jeter un oeil à
ce code en ce moment.

248
00:12:14,770 --> 00:12:18,620
Comme vous les gars ont également été invités à
écrire sur le quiz, enqueue.

249
00:12:18,620 --> 00:12:22,580
Peut-être nous parler à travers pourquoi
la réponse était ce qu'elle était.

250
00:12:22,580 --> 00:12:26,790
>> Je ne pouvais pas tout à fait correspondre à cette ligne sur l'une,
mais essentiellement ce morceau de code

251
00:12:26,790 --> 00:12:29,030
devrait être sur une seule ligne.

252
00:12:29,030 --> 00:12:30,140
Dépenser comme 30 secondes.

253
00:12:30,140 --> 00:12:33,000
Jetez un oeil et voir pourquoi
ceci est la façon dont il est.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Très, très similaire struct, très, très
la structure est semblable au précédent

256
00:12:55,420 --> 00:12:58,090
empiler sauf peut-être
une ligne de code.

257
00:12:58,090 --> 00:13:01,190
Et que une ligne de code
détermine la fonctionnalité.

258
00:13:01,190 --> 00:13:03,900
Et ce qui différencie vraiment
une file d'attente à partir d'une pile.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Tout le monde veut prendre un coup de couteau
à expliquer pourquoi vous avez

261
00:13:22,010 --> 00:13:24,980
obtenu cette chose compliquée ici?

262
00:13:24,980 --> 00:13:27,845
Nous voyons le retour de notre
ami merveilleux module.

263
00:13:27,845 --> 00:13:31,020
Comme vous les gars viendra bientôt
de reconnaître dans la programmation,

264
00:13:31,020 --> 00:13:34,910
presque chaque fois que vous besoin de quelque chose
à enrouler autour de quoi que ce soit,

265
00:13:34,910 --> 00:13:36,850
module va être la façon de le faire.

266
00:13:36,850 --> 00:13:40,510
Donc, sachant que, personne ne veut
pour tenter d'expliquer cette ligne de code?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Oui, toutes les réponses sont
acceptée et bienvenue.

269
00:13:47,507 --> 00:13:48,840
Public: Êtes-vous en train de me parler?

270
00:13:48,840 --> 00:13:49,506
ANDI PENG: Ouais.

271
00:13:49,506 --> 00:13:56,200
AUDIENCE: Oh, non désolé.

272
00:13:56,200 --> 00:14:00,250
ANDI PENG: OK, nous allons donc
marcher à travers ce code.

273
00:14:00,250 --> 00:14:03,642
Ainsi, lorsque vous essayez de
ajouter quelque chose sur une file d'attente,

274
00:14:03,642 --> 00:14:08,510
dans le cas de beau que la tête arrive
à être ici, il est très facile pour nous

275
00:14:08,510 --> 00:14:10,960
juste aller à la fin
insérer quelque chose, non?

276
00:14:10,960 --> 00:14:14,690
Mais tout l'intérêt d'une file d'attente est
que la tête peut réellement dynamique

277
00:14:14,690 --> 00:14:17,280
changer en fonction de l'endroit où nous
veulent le début de notre q soit,

278
00:14:17,280 --> 00:14:19,880
et en tant que tel, la queue
va également changer.

279
00:14:19,880 --> 00:14:31,100
>> Et alors, imaginez que ce ne fut pas le
la file d'attente, mais plutôt ce fut la file d'attente.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Disons que la tête est ici.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Disons que notre file d'attente ressemblait à ceci.

284
00:14:56,980 --> 00:15:00,190
Si nous voulions déplacer où
le début de la ligne est,

285
00:15:00,190 --> 00:15:03,400
disons que nous sommes passés la tête
de cette façon et tailles ici.

286
00:15:03,400 --> 00:15:07,100
>> Maintenant, nous voulons ajouter quelque chose à
cette file d'attente, mais comme vous les gars pouvez le voir,

287
00:15:07,100 --> 00:15:11,150
il est pas aussi simple que de simplement
ajouter tout ce qui est après la taille

288
00:15:11,150 --> 00:15:13,630
parce que nous manquons de
limites de notre tableau réel.

289
00:15:13,630 --> 00:15:16,190
Où nous voulons vraiment ajouter est ici.

290
00:15:16,190 --> 00:15:18,610
Voilà la beauté de la file d'attente
est que pour nous, visuellement

291
00:15:18,610 --> 00:15:22,380
ressemble à la ligne va comme ceci,
mais lorsqu'il est stocké dans une structure de données,

292
00:15:22,380 --> 00:15:29,370
ils donnent comme comme un cycle.

293
00:15:29,370 --> 00:15:32,360
Ce type de enroule autour
à l'avant de la même façon

294
00:15:32,360 --> 00:15:34,780
qu'une ligne peut également envelopper
autour fonction de là où vous

295
00:15:34,780 --> 00:15:36,279
vouloir début de la ligne de l'être.

296
00:15:36,279 --> 00:15:38,630
Et si nous prenons un
regarder vers le bas ici, nous allons

297
00:15:38,630 --> 00:15:40,880
disons que nous voulions créer un
fonction appelée enqueue.

298
00:15:40,880 --> 00:15:43,980
Nous voulions ajouter int n dans ce q.

299
00:15:43,980 --> 00:15:49,250
Si q.size q-- nous appellerons que nos données
structure-- si notre queue.size ne

300
00:15:49,250 --> 00:15:52,520
égal à la capacité ou si
il est inférieure à la capacité,

301
00:15:52,520 --> 00:15:55,120
q.strings est la matrice au sein de notre q.

302
00:15:55,120 --> 00:15:58,380
Nous allons mettre en
qui égale à q.heads,

303
00:15:58,380 --> 00:16:02,730
qui est ici, plus q.size
module par la capacité, ce qui

304
00:16:02,730 --> 00:16:04,290
enveloppez-nous revenir ici.

305
00:16:04,290 --> 00:16:08,040
>> Donc, dans cet exemple, l'indice
de la tête est une, non?

306
00:16:08,040 --> 00:16:11,480
L'indice de taille est égal à 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Donc, nous pouvons faire une plus 4 module
par notre capacité qui est de 5.

308
00:16:19,500 --> 00:16:20,920
Qu'est-ce que nous donner?

309
00:16:20,920 --> 00:16:23,270
Quel est l'indice que
sort de cette situation?

310
00:16:23,270 --> 00:16:24,080
>> AUDIENCE: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI PENG: 0, ce qui
arrive à être ici,

312
00:16:27,870 --> 00:16:30,640
et nous voulons être en mesure
à insérer dans ici.

313
00:16:30,640 --> 00:16:34,730
Et si cette équation ici genre
des travaux juste avec tous les numéros

314
00:16:34,730 --> 00:16:36,750
selon l'endroit où votre
tête et votre taille sont.

315
00:16:36,750 --> 00:16:38,541
Si vous savez ce que ceux
les choses sont, vous le savez

316
00:16:38,541 --> 00:16:43,170
exactement où vous voulez insérer
tout ce qui est après votre file d'attente.

317
00:16:43,170 --> 00:16:44,640
Est-ce que de sens pour tout le monde?

318
00:16:44,640 --> 00:16:48,560
>> Je sais une sorte de cerveau
Teaser surtout depuis cette

319
00:16:48,560 --> 00:16:50,512
est venu à la suite de votre quiz.

320
00:16:50,512 --> 00:16:52,220
Mais nous espérons que tout le monde
maintenant peut comprendre

321
00:16:52,220 --> 00:16:57,800
pourquoi cette solution ou cette
fonction est la façon dont il est.

322
00:16:57,800 --> 00:16:59,840
Toute personne un peu clair à ce sujet?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
D'ACCORD.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> Et maintenant, si vous
voulu dequeue, ce

327
00:17:09,970 --> 00:17:15,240
est où notre tête serait décalage
parce que si nous devions dequeue,

328
00:17:15,240 --> 00:17:17,030
nous ne prenons pas au large de la fin de la q.

329
00:17:17,030 --> 00:17:19,130
Nous voulons enlever la tête, non?

330
00:17:19,130 --> 00:17:24,260
Donc, par conséquent, la tête va changer,
et voilà pourquoi lorsque vous ENQUEUE,

331
00:17:24,260 --> 00:17:26,800
vous avez à garder une trace de
où votre tête et votre taille

332
00:17:26,800 --> 00:17:29,450
doivent être en mesure d'insérer
dans la position correcte.

333
00:17:29,450 --> 00:17:32,740
>> Et donc quand vous DEQUEUE,
Je également pseudo-it out.

334
00:17:32,740 --> 00:17:35,480
Sentez-vous libre de si vous voulez
à tenter de codage ceci.

335
00:17:35,480 --> 00:17:36,980
Vous souhaitez déplacer la tête, non?

336
00:17:36,980 --> 00:17:39,320
Si je voulais dequeue, je
serait déplacer la tête au-dessus.

337
00:17:39,320 --> 00:17:40,800
Ce serait la tête.

338
00:17:40,800 --> 00:17:45,617
>> Et notre taille actuelle serait
soustraire parce que nous ne

339
00:17:45,617 --> 00:17:46,950
avoir quatre éléments dans le tableau.

340
00:17:46,950 --> 00:17:51,370
Nous avons seulement trois, et ensuite nous voulons
pour retourner tout ce qui était stocké à l'intérieur

341
00:17:51,370 --> 00:17:56,260
de la tête parce que nous voulons profiter de cette
valeur de manière très similaire à la pile.

342
00:17:56,260 --> 00:17:58,010
Juste vous prenez
d'un endroit différent,

343
00:17:58,010 --> 00:18:01,770
et vous avez à réattribuer votre pointeur
au lieu différent en conséquence.

344
00:18:01,770 --> 00:18:03,890
Logiquement, tout le monde suit?

345
00:18:03,890 --> 00:18:05,690
Génial.

346
00:18:05,690 --> 00:18:10,156
>> OK, alors nous allons parler un peu
plus en profondeur sur les listes chaînées

347
00:18:10,156 --> 00:18:13,280
car ils vont être très, très précieux
pour vous au cours de cette semaine de

348
00:18:13,280 --> 00:18:14,964
psets.

349
00:18:14,964 --> 00:18:17,130
Les listes chaînées, comme vous les gars
peuvent se souvenir, tout ce qu'ils sont

350
00:18:17,130 --> 00:18:22,570
sont des nœuds qui sont des noeuds de certains
Les valeurs à la fois une valeur et un pointeur

351
00:18:22,570 --> 00:18:26,290
qui sont reliés entre eux
par les pointeurs.

352
00:18:26,290 --> 00:18:29,880
Et donc la structure sur la façon
nous créons un noeud ici est que nous

353
00:18:29,880 --> 00:18:33,569
avoir int n, ce qui est tout ce que
la valeur dans un magasin ou une chaîne n

354
00:18:33,569 --> 00:18:35,610
ou ce que vous voulez
appeler, l'omble étoiles n.

355
00:18:35,610 --> 00:18:41,482
Star noeud de structure, qui est le pointeur
que vous voulez avoir dans chaque nœud,

356
00:18:41,482 --> 00:18:43,690
vous allez avoir ce
point de pointeur vers la prochaine.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Vous aurez la tête
d'une liste liée qui est

359
00:18:50,040 --> 00:18:53,140
va pointer vers le reste de
les valeurs ainsi de suite et ainsi de suite

360
00:18:53,140 --> 00:18:55,290
jusqu'à ce que vous atteindrez la fin.

361
00:18:55,290 --> 00:18:58,040
Et ce dernier noeud est juste
aller de ne pas avoir un pointeur.

362
00:18:58,040 --> 00:18:59,952
Il va pointer vers
null, et que lorsqu'il est

363
00:18:59,952 --> 00:19:01,910
vous savez que vous avez touché le
fin de votre liste chaînée

364
00:19:01,910 --> 00:19:04,076
est lorsque votre dernière pointeur
ne pointe pas sur quoi que ce soit.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Donc, nous allons aller un peu plus dans
profondeur sur la façon dont on le ferait peut-

367
00:19:10,990 --> 00:19:12,400
rechercher une liste chaînée.

368
00:19:12,400 --> 00:19:15,460
Rappelez-vous ce que sont certains de la
inconvénients des listes chaînées

369
00:19:15,460 --> 00:19:19,340
versets un tableau concernant les recherches.

370
00:19:19,340 --> 00:19:22,565
Un tableau vous pouvez recherche binaire, mais
pourquoi ne pouvez-vous faire cela dans une liste chaînée?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> AUDIENCE: Parce qu'ils sont tous connectés,
mais vous ne savez pas très bien où

373
00:19:30,320 --> 00:19:31,330
[INAUDIBLE].

374
00:19:31,330 --> 00:19:34,600
>> ANDI PENG: Ouais, exactement ainsi souvenir
que la brillance d'un tableau

375
00:19:34,600 --> 00:19:37,190
était le fait que nous avions
mémoire à accès aléatoire où

376
00:19:37,190 --> 00:19:41,580
si je voulais la valeur de l'indice
six, je pourrais juste dire indice de six,

377
00:19:41,580 --> 00:19:42,407
me donner cette valeur.

378
00:19:42,407 --> 00:19:45,240
Et voilà car les tableaux sont classés
dans un espace contigu de mémoire

379
00:19:45,240 --> 00:19:48,020
en un seul endroit, alors que
type de listes chaînées

380
00:19:48,020 --> 00:19:52,820
sont entrecoupées de façon aléatoire tout autour,
et la seule façon que vous pouvez en trouver un

381
00:19:52,820 --> 00:19:56,890
est grâce à un pointeur qui vous dit
l'adresse de l'endroit où ce nœud suivant est.

382
00:19:56,890 --> 00:20:00,290
>> Et donc, par conséquent, la seule façon
de recherche à travers une liste chaînée

383
00:20:00,290 --> 00:20:01,560
est la recherche linéaire.

384
00:20:01,560 --> 00:20:05,890
Parce que je ne sais pas exactement où
la valeur 12 dans la liste chaînée est,

385
00:20:05,890 --> 00:20:08,780
Je dois parcourir l'intégralité
de cette liste chaînée un

386
00:20:08,780 --> 00:20:12,450
par une tête à partir du premier noeud,
au second noeud, au troisième noeud,

387
00:20:12,450 --> 00:20:17,690
tout le chemin jusqu'à ce que je reçois enfin
à l'endroit où ce nœud que je cherche est.

388
00:20:17,690 --> 00:20:22,110
Et dans ce sens, la recherche
sur une liste chaînée est toujours n.

389
00:20:22,110 --> 00:20:23,040
Il est toujours n.

390
00:20:23,040 --> 00:20:25,690
Il est toujours dans le temps linéaire.

391
00:20:25,690 --> 00:20:28,470
>> Et donc le code dans lequel
nous mettons en œuvre cela, et cela

392
00:20:28,470 --> 00:20:32,620
est un peu nouveau pour vous les gars, puisque vous
les gars ont pas vraiment parlé ou jamais

393
00:20:32,620 --> 00:20:35,000
pointeurs vu dans la façon de
recherche à travers des pointeurs,

394
00:20:35,000 --> 00:20:37,670
donc nous allons marcher à travers
cette très, très lentement.

395
00:20:37,670 --> 00:20:40,200
Donc, la recherche booléenne, à droite,
Imaginons que nous voulons

396
00:20:40,200 --> 00:20:42,820
pour créer une fonction appelée
recherche qui renvoie true

397
00:20:42,820 --> 00:20:46,820
si vous avez trouvé une valeur liée à l'intérieur du
liste, et il retourne false sinon.

398
00:20:46,820 --> 00:20:50,030
Node étoiles est
actuellement un peu le pointeur

399
00:20:50,030 --> 00:20:52,960
le premier élément de votre liste chaînée.

400
00:20:52,960 --> 00:20:56,700
int n est la valeur que vous êtes
chercher dans cette liste.

401
00:20:56,700 --> 00:20:58,770
>> Donc pointeur noeud étoiles liste est égal.

402
00:20:58,770 --> 00:21:00,970
Cela signifie que nous mettons en place
et la création d'un pointeur

403
00:21:00,970 --> 00:21:03,592
à ce premier noeud à l'intérieur de la liste.

404
00:21:03,592 --> 00:21:04,300
Tout le monde avec moi?

405
00:21:04,300 --> 00:21:06,530
Donc, si nous devions aller
de retour ici, je devrais

406
00:21:06,530 --> 00:21:13,850
initialiser un pointeur qui pointe vers
la tête de tout ce que la liste est.

407
00:21:13,850 --> 00:21:18,600
>> Et puis une fois que vous obtenez ici,
tandis pointeur ne correspond pas à null,

408
00:21:18,600 --> 00:21:22,160
de sorte que soit la boucle dans laquelle nous sommes
va être la suite traversant

409
00:21:22,160 --> 00:21:25,940
le reste de notre liste parce que ce
qui se passe lorsque le pointeur est égal nulle?

410
00:21:25,940 --> 00:21:27,550
Nous savons que nous have--

411
00:21:27,550 --> 00:21:28,450
>> AUDIENCE: [inaudible]

412
00:21:28,450 --> 00:21:31,491
>> ANDI PENG: Exactement, donc nous savons que
nous avons atteint la fin de la liste, à droite?

413
00:21:31,491 --> 00:21:34,470
Si vous revenez ici, chaque noeud
doit être dirigée vers un autre nœud

414
00:21:34,470 --> 00:21:36,550
et ainsi de suite
jusqu'à ce que vous atteignez finalement

415
00:21:36,550 --> 00:21:41,589
la queue de votre liste chaînée,
qui a un pointeur qui vient

416
00:21:41,589 --> 00:21:43,130
ne pointe pas ailleurs que non.

417
00:21:43,130 --> 00:21:47,510
Et si vous savez fondamentalement que
votre liste, il est toujours en place

418
00:21:47,510 --> 00:21:50,900
jusqu'à ce pointeur ne correspond pas à
null car une fois qu'il est égal à null,

419
00:21:50,900 --> 00:21:53,310
vous savez qu'il n'y a pas plus de choses.

420
00:21:53,310 --> 00:21:56,930
>> Voilà donc la boucle dans laquelle nous sommes
allez avoir la recherche proprement dite.

421
00:21:56,930 --> 00:22:01,690
Et si les pointer-- voyez-vous
ce genre de fonction de flèche il?

422
00:22:01,690 --> 00:22:06,930
Donc, si pointeur à n, si
le pointeur au n est égal à égal n,

423
00:22:06,930 --> 00:22:09,180
ce qui signifie que si
le pointeur que vous êtes

424
00:22:09,180 --> 00:22:13,420
chercher à l'extrémité de chaque
nœud est en fait égale à la valeur

425
00:22:13,420 --> 00:22:15,990
vous cherchez, puis
vous voulez retourner vrai.

426
00:22:15,990 --> 00:22:19,280
Donc, fondamentalement, si vous êtes à un nœud qui
a la valeur que vous cherchez,

427
00:22:19,280 --> 00:22:23,550
vous savez que vous avez été
capable de rechercher avec succès.

428
00:22:23,550 --> 00:22:27,150
>> Sinon, vous souhaitez définir
votre pointeur vers le nœud suivant.

429
00:22:27,150 --> 00:22:28,850
Voilà ce que cette ligne ici est fait.

430
00:22:28,850 --> 00:22:31,750
Pointeur est égal pointeur à côté.

431
00:22:31,750 --> 00:22:33,360
Tout le monde voir comment que ça marche?

432
00:22:33,360 --> 00:22:36,580
>> Et essentiellement, vous allez tout simplement
parcourir l'intégralité de la liste,

433
00:22:36,580 --> 00:22:41,920
réinitialiser votre pointeur à chaque fois jusqu'à
vous a finalement atteint la fin de la liste.

434
00:22:41,920 --> 00:22:45,030
Et vous savez qu'il ya ne sont pas
plusieurs noeuds de recherche à travers,

435
00:22:45,030 --> 00:22:47,999
et puis vous pouvez retourner false
parce que vous savez que, oh, eh bien,

436
00:22:47,999 --> 00:22:50,540
si je suis en mesure de rechercher
à travers la totalité de la liste.

437
00:22:50,540 --> 00:22:54,530
Si dans cet exemple, si je voulais
pour trouver la valeur de 10,

438
00:22:54,530 --> 00:22:57,250
et je commence à la tête, et
Je cherche tout le chemin vers le bas,

439
00:22:57,250 --> 00:23:00,550
et je suis finalement devenu à ce qui
un pointeur qui pointe à null,

440
00:23:00,550 --> 00:23:04,415
Je sais que, merde, je suppose que 10 est pas
cette liste parce que je ne pouvais pas trouver.

441
00:23:04,415 --> 00:23:06,520
Et je suis à la fin de la liste.

442
00:23:06,520 --> 00:23:11,040
Et dans ce cas, vous savez
Je vais retourner faux.

443
00:23:11,040 --> 00:23:12,900
>> Disons que tremper dans un peu.

444
00:23:12,900 --> 00:23:17,350
Ce sera assez
important pour votre pset.

445
00:23:17,350 --> 00:23:21,140
La logique de cela est très simple, peut-être
syntaxiquement tout mettre en œuvre.

446
00:23:21,140 --> 00:23:23,365
Les gars, vous voulez faire
vous que vous comprenez.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Frais.

449
00:23:27,650 --> 00:23:32,560
>> OK, alors comment nous serions
l'insertion des nœuds, à droite,

450
00:23:32,560 --> 00:23:35,380
dans une liste retenir, car
quels sont les avantages de ce

451
00:23:35,380 --> 00:23:39,230
d'avoir une liste liée par rapport
un tableau en termes de stockage?

452
00:23:39,230 --> 00:23:41,110
>> PUBLIC: Il est dynamique,
il est donc plus facile to--

453
00:23:41,110 --> 00:23:43,180
>> ANDI PENG: Exactement,
il est si dynamique, qui

454
00:23:43,180 --> 00:23:46,880
signifie qu'il peut gonfler et se rétrécir
en fonction des besoins de l'utilisateur.

455
00:23:46,880 --> 00:23:56,570
Et donc, dans ce sens, nous ne devons pas
à perdre la mémoire inutile parce que je

456
00:23:56,570 --> 00:24:00,850
si je ne sais pas combien de valeurs que je veux
au magasin, il n'a pas de sens pour moi

457
00:24:00,850 --> 00:24:04,310
pour créer un tableau parce
si je veux stocker 10 valeurs

458
00:24:04,310 --> 00:24:08,380
et je crée un tableau de 1000, qui est
beaucoup de mémoire gaspillée, alloué.

459
00:24:08,380 --> 00:24:11,180
Voilà pourquoi nous voulons utiliser un lien
Liste de pouvoir dynamiquement

460
00:24:11,180 --> 00:24:13,860
modifier ou réduire notre taille.

461
00:24:13,860 --> 00:24:17,040
>> Et pour que rend l'insertion
un peu plus compliqué.

462
00:24:17,040 --> 00:24:20,810
Puisque nous ne pouvons pas accéder au hasard éléments
la façon dont nous aurions d'un tableau.

463
00:24:20,810 --> 00:24:24,270
Si je veux insérer un élément
dans la septième indice,

464
00:24:24,270 --> 00:24:26,930
Je peux juste insérer
dans la septième indice.

465
00:24:26,930 --> 00:24:30,020
Sur une liste chaînée, il ne fait pas
tout à fait travailler aussi facilement,

466
00:24:30,020 --> 00:24:34,947
et donc si nous voulions insérer
celui qui est ici dans la liste chaînée,

467
00:24:34,947 --> 00:24:36,280
Visuellement, il est très facile à voir.

468
00:24:36,280 --> 00:24:39,363
Nous voulons juste pour l'insérer là,
dès le début de la liste,

469
00:24:39,363 --> 00:24:40,840
juste après la tête.

470
00:24:40,840 --> 00:24:44,579
>> Mais la façon dont nous devons réaffecter
les pointeurs est un peu alambiquées

471
00:24:44,579 --> 00:24:47,620
ou, logiquement, il est logique, mais
vous voulez vous assurer que vous avez

472
00:24:47,620 --> 00:24:50,250
complètement à cause
la dernière chose que vous voulez

473
00:24:50,250 --> 00:24:52,990
est de réaffecter un pointeur du
façon que nous faisons ici.

474
00:24:52,990 --> 00:24:58,170
Si vous déréférencer la
pointeur de la tête aux 1,

475
00:24:58,170 --> 00:25:01,086
puis tout d'un coup la
reste de votre liste chaînée

476
00:25:01,086 --> 00:25:04,680
est perdu parce que vous avez pas réellement
un temporaire créé rien.

477
00:25:04,680 --> 00:25:06,220
Qui est dirigée à l'2.

478
00:25:06,220 --> 00:25:10,080
Si vous réattribuez le pointeur, puis le
reste de votre liste est totalement perdu.

479
00:25:10,080 --> 00:25:13,310
Donc, vous voulez être
très, très prudent ici

480
00:25:13,310 --> 00:25:17,010
d'abord attribuer le
pointeur de tout ce que vous

481
00:25:17,010 --> 00:25:20,150
à insérer dans la mesure du
vous voulez, puis vous

482
00:25:20,150 --> 00:25:22,710
peut déréférencer le reste de votre liste.

483
00:25:22,710 --> 00:25:25,250
>> Donc, cela vaut pour la mesure
vous essayez de l'insérer dans.

484
00:25:25,250 --> 00:25:27,520
Si vous souhaitez insérer à la
tête, si vous voulez répondre ici,

485
00:25:27,520 --> 00:25:29,455
si vous souhaitez insérer au
la fin, ainsi, à la fin, je

486
00:25:29,455 --> 00:25:30,910
suppose que vous feriez tout
avoir aucun pointeur, mais vous

487
00:25:30,910 --> 00:25:33,830
voulez vous assurer que vous ne le faites pas
perdre le reste de votre liste.

488
00:25:33,830 --> 00:25:36,640
Vous voulez toujours vous assurer
votre nouveau noeud pointe

489
00:25:36,640 --> 00:25:39,330
vers ce que vous
à insérer dans,

490
00:25:39,330 --> 00:25:42,170
et puis vous pouvez ajouter le chaînage.

491
00:25:42,170 --> 00:25:43,330
Tout le monde est clair?

492
00:25:43,330 --> 00:25:45,427
>> Cela va être
l'un des vrais problèmes.

493
00:25:45,427 --> 00:25:48,010
Une des plus grandes questions
vous allez avoir sur votre pset

494
00:25:48,010 --> 00:25:51,340
est-ce que vous allez essayer de créer
une liste liée et les choses insertion

495
00:25:51,340 --> 00:25:53,340
mais alors juste de perdre le
reste de votre liste chaînée.

496
00:25:53,340 --> 00:25:54,900
Et vous allez être comme, je
ne sais pas pourquoi ce qui se passe?

497
00:25:54,900 --> 00:25:58,040
Et il est une douleur pour passer
et rechercher tous vos pointeurs.

498
00:25:58,040 --> 00:26:02,100
>> Et je vous garantis sur ce pset,
écrire et dessiner sur ces nœuds

499
00:26:02,100 --> 00:26:03,344
sera très, très utile.

500
00:26:03,344 --> 00:26:06,010
Ainsi, vous pouvez complètement suivre
d'où tous vos pointeurs sont,

501
00:26:06,010 --> 00:26:08,540
ce qui va mal,
où tous vos nœuds sont,

502
00:26:08,540 --> 00:26:12,660
ce que vous devez faire pour accéder ou
insérer ou de supprimer ou de l'un d'eux.

503
00:26:12,660 --> 00:26:14,550
Tout le monde bien avec qui?

504
00:26:14,550 --> 00:26:15,050
Frais.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Donc, si nous voulions regarder le code?

507
00:26:22,600 --> 00:26:24,470
Oh, je ne sais pas si nous
peut voir the-- OK, donc

508
00:26:24,470 --> 00:26:27,940
en haut tout ce qu'il est est une fonction
insert nommé où nous voulons

509
00:26:27,940 --> 00:26:31,365
insérer int n dans la liste chaînée.

510
00:26:31,365 --> 00:26:32,740
Nous allons marcher à travers cela.

511
00:26:32,740 --> 00:26:34,770
Il ya beaucoup de code, un lot de la nouvelle syntaxe.

512
00:26:34,770 --> 00:26:36,220
Nous serons OK.

513
00:26:36,220 --> 00:26:39,120
>> Alors au sommet, à chaque fois
nous voulons créer quelque chose

514
00:26:39,120 --> 00:26:42,380
qu'est-ce que nous devons faire, surtout si vous
voulez qu'il ne sera pas stockée sur la pile

515
00:26:42,380 --> 00:26:43,920
mais dans le tas?

516
00:26:43,920 --> 00:26:45,460
Nous allons à un malloc, non?

517
00:26:45,460 --> 00:26:48,240
Donc, nous allons créer un pointeur.

518
00:26:48,240 --> 00:26:52,074
Noeud, pointeur, de nouvelles égaux
malloc la taille d'un noeud

519
00:26:52,074 --> 00:26:53,740
parce que nous voulons que le noeud à créer.

520
00:26:53,740 --> 00:26:56,720
Nous voulons que le montant de
mémoire qui prend un noeud

521
00:26:56,720 --> 00:26:59,300
être alloué pour la
création d'un nouveau noeud.

522
00:26:59,300 --> 00:27:02,270
>> Et puis nous allons vérifier
voir si de nouveaux égaux égal nulle.

523
00:27:02,270 --> 00:27:03,370
Rappelez-vous ce que nous disions?

524
00:27:03,370 --> 00:27:06,470
Quoi que vous malloc,
que devez-vous toujours le faire?

525
00:27:06,470 --> 00:27:09,490
Vous devez toujours vérifier pour voir
si oui ou non qui est nulle.

526
00:27:09,490 --> 00:27:13,620
>> Par exemple, si votre exploitation
système était complètement plein,

527
00:27:13,620 --> 00:27:17,060
si vous aviez pas plus de mémoire au
tous et vous essayez de malloc,

528
00:27:17,060 --> 00:27:18,410
il serait retourner null pour vous.

529
00:27:18,410 --> 00:27:21,094
Et si vous essayez de l'utiliser
quand il pointait à null,

530
00:27:21,094 --> 00:27:23,260
tu ne vas pas à la mesure
pour accéder à cette information.

531
00:27:23,260 --> 00:27:27,010
Et en tant que telle, nous voulions faire
vous que chaque fois que vous allouer de,

532
00:27:27,010 --> 00:27:30,500
vous êtes toujours vérifier pour voir si
que la mémoire qui vous est donné est nulle.

533
00:27:30,500 --> 00:27:33,670
Et si elle est non, alors nous pouvons nous déplacer
avec le reste de notre code.

534
00:27:33,670 --> 00:27:36,140
>> Nous allons donc
initialiser le nouveau nœud.

535
00:27:36,140 --> 00:27:39,050
Nous allons faire une nouvelle n est égal à n.

536
00:27:39,050 --> 00:27:42,390
Et puis nous allons faire
mettre le pointeur sur la nouvelle nouvelle

537
00:27:42,390 --> 00:27:46,900
null parce que nous faisons en ce moment pas
vouloir quelque chose pour elle pour pointer vers.

538
00:27:46,900 --> 00:27:48,755
Nous ne savons pas où
il va vous mettre,

539
00:27:48,755 --> 00:27:50,630
et puis si nous voulons
insérer à la tête,

540
00:27:50,630 --> 00:27:53,820
alors nous pouvons réaffecter
le pointeur de la tête.

541
00:27:53,820 --> 00:27:58,530
Est-ce que tout le monde suit la logique
d'où ça se passe?

542
00:27:58,530 --> 00:28:02,502
>> Tout ce que nous faisons est de créer une nouvelle
noeud, le réglage du pointeur à null,

543
00:28:02,502 --> 00:28:04,210
puis la réaffectation
à la tête si nous

544
00:28:04,210 --> 00:28:06,320
savons que nous voulons pour l'insérer à la tête.

545
00:28:06,320 --> 00:28:09,420
Et puis, la tête va
pointer vers ce nouveau nœud.

546
00:28:09,420 --> 00:28:11,060
Tout le monde OK avec ça?

547
00:28:11,060 --> 00:28:12,380
>> Donc, il est un processus en deux étapes.

548
00:28:12,380 --> 00:28:14,760
Vous devez d'abord affecter
tout ce que vous créez.

549
00:28:14,760 --> 00:28:18,260
Réglez ce pointeur à la
référence, et ensuite vous

550
00:28:18,260 --> 00:28:21,400
peut sorte de déréférencer
le premier pointeur

551
00:28:21,400 --> 00:28:22,972
et pointer vers le nouveau nœud.

552
00:28:22,972 --> 00:28:25,680
Partout où vous voulez l'insérer,
que la logique va être vrai.

553
00:28:25,680 --> 00:28:27,530
>> Il est un peu comme l'attribution
variables temporaires.

554
00:28:27,530 --> 00:28:28,700
Rappelez-vous, vous avez
pour vous assurer que vous

555
00:28:28,700 --> 00:28:30,346
ne pas perdre de si vous échanger.

556
00:28:30,346 --> 00:28:33,470
Vous voulez vous assurer que vous avez une
variable temporaire qui maintient type de

557
00:28:33,470 --> 00:28:35,620
trace d'où cette chose
est stockée afin que vous

558
00:28:35,620 --> 00:28:41,190
ne pas perdre toute valeur au cours
comme de déconner avec elle.

559
00:28:41,190 --> 00:28:42,710
>> OK, donc le code sera ici.

560
00:28:42,710 --> 00:28:45,020
Les gars, vous jetez un oeil après l'article.

561
00:28:45,020 --> 00:28:48,060
Il sera là.

562
00:28:48,060 --> 00:28:50,280
>> Donc je suppose que la façon dont le fait
cela diffère si nous voulions

563
00:28:50,280 --> 00:28:52,300
à insérer dans le milieu ou la fin?

564
00:28:52,300 --> 00:28:57,892
Quelqu'un at-il une idée de ce qui est la
pseudo que la référence logique

565
00:28:57,892 --> 00:29:00,350
que nous prendrions si nous voulions
pour l'insérer dans le milieu?

566
00:29:00,350 --> 00:29:03,391
Donc, si nous voulions pour l'insérer à la
tête, tout ce que nous faisons est de créer un nouveau nœud.

567
00:29:03,391 --> 00:29:06,311
Nous avons mis le pointeur de ce
nouveau nœud à ce que la tête,

568
00:29:06,311 --> 00:29:08,310
puis nous avons mis la tête
vers le nouveau nœud, non?

569
00:29:08,310 --> 00:29:11,560
Si nous voulions de l'insérer dans le milieu
de la liste, qu'aurions-nous faire?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> Auditoire: ce serait encore
être un processus similaire

572
00:29:16,110 --> 00:29:19,114
de l'attribution comme pointeur et
puis en attribuant ce pointeur,

573
00:29:19,114 --> 00:29:20,530
mais nous aurions à s'y implanter.

574
00:29:20,530 --> 00:29:23,560
>> ANDI PENG: Exactement, si exactement
le même processus, sauf vous

575
00:29:23,560 --> 00:29:27,820
avoir pour localiser exactement où vous
veulent que le nouveau pointeur d'aller dans,

576
00:29:27,820 --> 00:29:44,790
donc si je veux insérer dans
le milieu de films-- liée OK,

577
00:29:44,790 --> 00:29:46,370
disons que notre liste est lié.

578
00:29:46,370 --> 00:29:49,500
Si nous voulons insérer ici,
nous allons créer un nouveau noeud.

579
00:29:49,500 --> 00:29:50,520
Nous allons malloc.

580
00:29:50,520 --> 00:29:52,220
Nous allons créer un nouveau nœud.

581
00:29:52,220 --> 00:29:55,940
Nous allons assigner le
pointeur de ce noeud.

582
00:29:55,940 --> 00:29:58,335
>> Mais le problème qui diffère
d'où la tête est

583
00:29:58,335 --> 00:30:00,490
est que nous savions exactement
où la tête est.

584
00:30:00,490 --> 00:30:01,930
Il était à droite au premier, non?

585
00:30:01,930 --> 00:30:04,870
Mais ici nous avons à suivre
d'où nous insérant dans.

586
00:30:04,870 --> 00:30:07,930
Si nous insérons notre
noeud ici, nous avons

587
00:30:07,930 --> 00:30:12,270
pour vous assurer que le
un précédent de ce noeud

588
00:30:12,270 --> 00:30:14,172
est celle qui réaffecte le pointeur.

589
00:30:14,172 --> 00:30:16,380
Alors vous devez sorte de
garder la trace de deux choses.

590
00:30:16,380 --> 00:30:19,420
Si vous gardez une trace de l'endroit où cette
noeud est actuellement insérer dans.

591
00:30:19,420 --> 00:30:23,280
Vous avez également de garder une trace de l'endroit où
le nœud précédent que vous êtes à la recherche au

592
00:30:23,280 --> 00:30:24,340
était également là.

593
00:30:24,340 --> 00:30:25,830
Tout le monde bien avec qui?

594
00:30:25,830 --> 00:30:26,500
D'ACCORD.

595
00:30:26,500 --> 00:30:28,000
>> Comment sur l'insertion dans l'extrémité?

596
00:30:28,000 --> 00:30:34,220
Si je voulais ajouter ici-- si je voulais
à ajouter un nouveau noeud à la fin de la liste,

597
00:30:34,220 --> 00:30:37,009
Comment pourrais-je m'y prendre?

598
00:30:37,009 --> 00:30:39,300
Auditoire: Alors, pour le moment, la
dernière de celui pointé nulle.

599
00:30:39,300 --> 00:30:40,960
ANDI PENG: Ouais.

600
00:30:40,960 --> 00:30:43,560
Exactement, si celui-
actuellement est fait de savoir,

601
00:30:43,560 --> 00:30:46,720
et donc je suppose que, dans ce sens, il est
très facile d'ajouter à la fin de la liste.

602
00:30:46,720 --> 00:30:51,810
Tout ce que vous avez à faire est de définir ce
égale à null puis essor.

603
00:30:51,810 --> 00:30:53,070
Juste là, très facile.

604
00:30:53,070 --> 00:30:53,960
Très simple.

605
00:30:53,960 --> 00:30:56,430
>> Très similaire à la
tête, mais logiquement vous

606
00:30:56,430 --> 00:30:59,690
voulez vous assurer que les étapes
vous prenez en direction de faire tout cela,

607
00:30:59,690 --> 00:31:01,500
vous suivez.

608
00:31:01,500 --> 00:31:04,420
Il est très facile de, au milieu
de votre code, se laisser prendre sur,

609
00:31:04,420 --> 00:31:05,671
oh, je ai tellement de pointeurs.

610
00:31:05,671 --> 00:31:07,461
Je ne sais pas où
rien pointe.

611
00:31:07,461 --> 00:31:09,170
Je ne sais même pas qui je suis sur le noeud.

612
00:31:09,170 --> 00:31:11,490
Ce qui se passe?

613
00:31:11,490 --> 00:31:13,620
>> Détendez-vous, calmez-vous, prenez une profonde respiration.

614
00:31:13,620 --> 00:31:15,530
Dessinez votre liste chaînée.

615
00:31:15,530 --> 00:31:18,800
Si vous le dites, je sais exactement où
Je dois insérer cela dans

616
00:31:18,800 --> 00:31:22,970
et je sais exactement comment réaffecter mon
pointeurs, beaucoup, beaucoup plus facile d'imaginer

617
00:31:22,970 --> 00:31:27,200
out-- beaucoup, beaucoup plus facile à pas
se perdre dans les bugs de votre code.

618
00:31:27,200 --> 00:31:29,410
Tout le monde OK avec ça?

619
00:31:29,410 --> 00:31:31,380
D'ACCORD.

620
00:31:31,380 --> 00:31:35,120
>> Donc je suppose un concept que nous avons pas
vraiment parlé avant aujourd'hui,

621
00:31:35,120 --> 00:31:38,131
et je suppose que vous probablement
ne rencontrera beaucoup yet--

622
00:31:38,131 --> 00:31:40,880
il est une sorte d'concept-- avancée
est que nous avons fait un données

623
00:31:40,880 --> 00:31:43,900
structure appelée une liste doublement chaînée.

624
00:31:43,900 --> 00:31:46,390
Donc, comme vous les gars pouvez le voir,
tout ce que nous faisons est la création

625
00:31:46,390 --> 00:31:50,400
une valeur réelle, un supplément de
pointeur sur chacun de nos nœuds

626
00:31:50,400 --> 00:31:52,660
qui souligne également le noeud précédent.

627
00:31:52,660 --> 00:31:58,170
Ainsi, non seulement nous avons notre
nœuds point à la suivante.

628
00:31:58,170 --> 00:32:01,430
Ils soulignent également à la précédente.

629
00:32:01,430 --> 00:32:04,310
Je vais ignorer ces deux maintenant.

630
00:32:04,310 --> 00:32:06,740
>> Alors vous avez une chaîne
qui peut se déplacer dans les deux sens,

631
00:32:06,740 --> 00:32:09,630
et alors il est un peu plus facile
à suivre logiquement long.

632
00:32:09,630 --> 00:32:11,896
Comme ici, au lieu de
garder la trace de, oh, je

633
00:32:11,896 --> 00:32:14,520
faut savoir que ce noeud est
celui que je dois réaffecter,

634
00:32:14,520 --> 00:32:17,532
Je peux juste aller ici et
il suffit de tirer la précédente.

635
00:32:17,532 --> 00:32:19,490
Alors je sais exactement où
qui est, et puis vous

636
00:32:19,490 --> 00:32:21,130
ne pas avoir à traverser le
intégralité de la liste chaînée.

637
00:32:21,130 --> 00:32:22,180
Il est un peu plus facile.

638
00:32:22,180 --> 00:32:24,960
>> Mais en tant que telle, vous avez doublement
la quantité de pointeurs,

639
00:32:24,960 --> 00:32:26,960
qui est le double de la quantité de mémoire.

640
00:32:26,960 --> 00:32:28,950
Il ya beaucoup de pointeurs à garder la trace.

641
00:32:28,950 --> 00:32:32,140
Il est un peu plus complexe, mais il est
un peu plus convivial en fonction

642
00:32:32,140 --> 00:32:34,080
sur ce que vous essayez d'accomplir.

643
00:32:34,080 --> 00:32:36,910
>> Donc, ce type de données
structure existe totalement,

644
00:32:36,910 --> 00:32:40,280
et la structure pour est très, très
simple, sauf tout ce que vous rencontrez est,

645
00:32:40,280 --> 00:32:43,850
au lieu de simplement un pointeur vers la prochaine,
vous avez également un pointeur vers précédente.

646
00:32:43,850 --> 00:32:45,940
Voilà toute la différence était.

647
00:32:45,940 --> 00:32:47,740
Tout le monde bien avec qui?

648
00:32:47,740 --> 00:32:48,240
Frais.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Très bien, alors maintenant je suis
pour vraiment passer probablement

651
00:32:53,280 --> 00:32:56,870
comme 15 à 20 minutes ou le vrac
le reste du temps dans la section

652
00:32:56,870 --> 00:32:58,360
parler de tables de hachage.

653
00:32:58,360 --> 00:33:02,590
Combien d'entre vous les gars
ont lu pset5 spec?

654
00:33:02,590 --> 00:33:03,620
Très bien, bon.

655
00:33:03,620 --> 00:33:06,160
Voilà plus élevé que les 50% de normalement.

656
00:33:06,160 --> 00:33:07,560
C'est bon.

657
00:33:07,560 --> 00:33:10,345
>> Donc, comme vous pourrez voir les gars,
vous êtes défi dans pset5

658
00:33:10,345 --> 00:33:16,790
sera de mettre en oeuvre un dictionnaire
où vous chargez plus de 140.000 mots

659
00:33:16,790 --> 00:33:20,610
que nous vous donnons et vérification orthographique
contre l'ensemble du texte.

660
00:33:20,610 --> 00:33:22,580
Nous vous donnerons aléatoire
morceaux de la littérature.

661
00:33:22,580 --> 00:33:23,520
Nous vous donnerons L'Odyssée.

662
00:33:23,520 --> 00:33:24,561
Nous allons vous donner l'Iliade.

663
00:33:24,561 --> 00:33:26,350
Nous vous donnerons Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> Et votre défi
sera de vérification orthographique

665
00:33:28,220 --> 00:33:31,760
chaque mot dans tous les
de ces dictionnaires

666
00:33:31,760 --> 00:33:34,960
essentiellement avec notre correcteur orthographique.

667
00:33:34,960 --> 00:33:38,620
Et donc il ya quelques parties
de la création de ce jeu de processeurs,

668
00:33:38,620 --> 00:33:41,970
D'abord, vous voulez être
en mesure de réellement charger

669
00:33:41,970 --> 00:33:43,970
tous les mots dans votre
dictionnaire, et puis vous

670
00:33:43,970 --> 00:33:45,530
veulent être en mesure de
vérifier l'orthographe de chacun d'eux.

671
00:33:45,530 --> 00:33:48,780
Et en tant que tel, vous allez exiger
une structure de données qui peut faire ce jeûne

672
00:33:48,780 --> 00:33:50,790
et de manière efficace et dynamique.

673
00:33:50,790 --> 00:33:52,900
>> Donc je suppose que le plus facile
façon de le faire, vous

674
00:33:52,900 --> 00:33:55,010
serait probablement créer un tableau, non?

675
00:33:55,010 --> 00:33:58,910
La meilleure façon de stockage est vous
peut créer un tableau de 140.000 mots

676
00:33:58,910 --> 00:34:03,400
et juste les placer tous là et
puis traverser les par recherche binaire

677
00:34:03,400 --> 00:34:06,780
ou par des sélections ou pas--
Désolé que ça tri.

678
00:34:06,780 --> 00:34:10,729
Vous pouvez les trier et parcourir les
par recherche binaire ou linéaire recherche juste

679
00:34:10,729 --> 00:34:13,730
et juste finales les mots, mais que
prend une énorme quantité de mémoire,

680
00:34:13,730 --> 00:34:15,190
et il est pas très efficace.

681
00:34:15,190 --> 00:34:18,350
>> Et donc nous allons commencer
parler de façons de faire

682
00:34:18,350 --> 00:34:20,110
notre temps de fonctionnement plus efficace.

683
00:34:20,110 --> 00:34:23,190
Et notre objectif est d'obtenir
constante de temps où

684
00:34:23,190 --> 00:34:25,810
il est presque comme les tableaux, où
vous avez un accès instantané.

685
00:34:25,810 --> 00:34:28,560
Si je voulais chercher quoi que ce soit,
Je veux être capable de tout,

686
00:34:28,560 --> 00:34:30,810
perche, trouver exactement, et le sortir.

687
00:34:30,810 --> 00:34:34,100
Et ainsi une structure dans laquelle
nous serons en train de devenir très proche

688
00:34:34,100 --> 00:34:37,569
pour être en mesure d'accéder constante
temps, ce saint Graal

689
00:34:37,569 --> 00:34:41,370
la programmation de la constante
le temps est appelée une table de hachage.

690
00:34:41,370 --> 00:34:45,370
Et si David mentionné précédemment, les
[Inaudible] un peu de lecture,

691
00:34:45,370 --> 00:34:49,100
mais nous allons vraiment
plongée dans une profonde cette semaine

692
00:34:49,100 --> 00:34:51,780
sur un morceau qui est en ce qui concerne
comment une table de hachage fonctionne.

693
00:34:51,780 --> 00:34:53,949
>> Donc, la façon dont un hachage
ouvrages de table, par exemple,

694
00:34:53,949 --> 00:35:00,230
si je voulais enregistrer un tas de mots, un
tas de mots dans la langue anglaise,

695
00:35:00,230 --> 00:35:02,940
Je pourrais théoriquement mettre
banane, pomme, kiwi, mangue, paire,

696
00:35:02,940 --> 00:35:04,980
et le cantaloup tout simplement sur un tableau.

697
00:35:04,980 --> 00:35:07,044
Ils pourraient tous intégrer et être trouver.

698
00:35:07,044 --> 00:35:09,210
Ce serait une sorte de douleur à
parcourir et l'accès,

699
00:35:09,210 --> 00:35:12,920
mais le plus simple de le faire est
que nous pouvons réellement créer une structure

700
00:35:12,920 --> 00:35:15,680
appelé une table de hachage où nous hachage.

701
00:35:15,680 --> 00:35:19,880
Nous courons tous nos clés à travers
une fonction de hachage, une équation,

702
00:35:19,880 --> 00:35:22,600
que tous les tours en
une sorte de valeur

703
00:35:22,600 --> 00:35:28,740
que nous pouvons stocker sur
essentiellement un tableau de liste chaînée.

704
00:35:28,740 --> 00:35:32,570
>> Et ici, si nous voulions
pour stocker des mots anglais,

705
00:35:32,570 --> 00:35:37,250
nous pourrions potentiellement juste, je ne fais pas
savoir, mettez toutes les premières lettres

706
00:35:37,250 --> 00:35:39,630
en quelque sorte d'un certain nombre.

707
00:35:39,630 --> 00:35:43,140
Et ainsi, par exemple, si je voulais
Un synonyme de apple--

708
00:35:43,140 --> 00:35:47,460
ou avec l'indice de 0, et
B soit synonyme de 1,

709
00:35:47,460 --> 00:35:51,030
nous pouvons avoir 26 entrées
qui peut simplement stocker

710
00:35:51,030 --> 00:35:53,610
toutes les lettres de l'
alphabet que nous allons commencer avec.

711
00:35:53,610 --> 00:35:56,130
Et alors nous pouvons avoir
pomme à l'index de 0.

712
00:35:56,130 --> 00:35:59,160
Nous pouvons avoir la banane à l'index des
1, le cantaloup à l'index de 2,

713
00:35:59,160 --> 00:36:00,540
et ainsi de suite.

714
00:36:00,540 --> 00:36:04,460
Et donc si je voulais chercher
ma table de hachage et l'accès pomme,

715
00:36:04,460 --> 00:36:07,560
Je sais que la pomme commence par
un A, et je sais exactement

716
00:36:07,560 --> 00:36:10,860
qu'il doit être et le hachage
tableau à l'index 0 parce

717
00:36:10,860 --> 00:36:13,620
de la fonction précédemment attribuée.

718
00:36:13,620 --> 00:36:16,572
>> Donc, je ne sais pas, nous sommes
un programme utilisateur où

719
00:36:16,572 --> 00:36:18,780
vous serez facturé avec
arbitrarily-- pas arbitrairement,

720
00:36:18,780 --> 00:36:22,530
à essayer de pensivement
penser de bonnes équations

721
00:36:22,530 --> 00:36:25,460
pour être en mesure de se propager
l'ensemble de vos valeurs

722
00:36:25,460 --> 00:36:29,370
d'une manière qu'ils peuvent facilement accéder
il plus tard avec comme une équation

723
00:36:29,370 --> 00:36:31,130
que vous, vous-même, savent.

724
00:36:31,130 --> 00:36:35,210
Ainsi, dans le sens que si je voulais aller à
mangue, je sais, oh, il commence par m.

725
00:36:35,210 --> 00:36:37,134
Il doit être à l'index des 12.

726
00:36:37,134 --> 00:36:38,800
Je ne dois pas chercher dans quoi que ce soit.

727
00:36:38,800 --> 00:36:42,080
Je sais exactly-- je pouvais aller à
l'indice des 12 et tirez cela.

728
00:36:42,080 --> 00:36:45,520
>> Tout le monde sur la façon dont un clair
La fonction de table de hachage des fonctionne?

729
00:36:45,520 --> 00:36:48,380
Il est un peu juste un tableau plus complexe.

730
00:36:48,380 --> 00:36:50,010
Voilà tout ce qu'il est.

731
00:36:50,010 --> 00:36:51,630
D'ACCORD.

732
00:36:51,630 --> 00:36:57,690
>> Donc je suppose que nous nous heurtons à
cette question de ce que

733
00:36:57,690 --> 00:37:06,390
qui se passe si vous avez plusieurs choses
qui vous donnent le même indice?

734
00:37:06,390 --> 00:37:10,570
Donc, dire que notre fonction, tout ce qu'il
n'a fait que prendre cette première lettre

735
00:37:10,570 --> 00:37:14,490
et le transformer en un
respective de 0 à 25 index.

736
00:37:14,490 --> 00:37:17,137
Cela est tout à fait bien si
vous avez seulement un de chaque.

737
00:37:17,137 --> 00:37:18,970
Mais la deuxième vous commencez
avoir plus, vous êtes

738
00:37:18,970 --> 00:37:20,910
va avoir ce qu'on appelle une collision.

739
00:37:20,910 --> 00:37:25,580
>> Donc, si je tente d'insérer l'enterrer dans un hachage
table qui a déjà la banane sur elle,

740
00:37:25,580 --> 00:37:27,870
qu'est-ce qui va se passer quand
vous essayez d'insérer cela?

741
00:37:27,870 --> 00:37:30,930
Les mauvaises choses parce que la banane
existe déjà au sein de l'indice

742
00:37:30,930 --> 00:37:33,800
que vous souhaitez stocker dans.

743
00:37:33,800 --> 00:37:35,560
Berry genre de est comme, ah, je fais quoi?

744
00:37:35,560 --> 00:37:37,080
Je ne sais pas où aller.

745
00:37:37,080 --> 00:37:38,410
Comment puis-je résoudre ce problème?

746
00:37:38,410 --> 00:37:41,150
>> Et si vous les gars seront sorte de
voyons que nous faisons cette chose délicate

747
00:37:41,150 --> 00:37:44,810
où nous pouvons sorte de réalité
créer une liste liée dans nos tableaux.

748
00:37:44,810 --> 00:37:46,840
Et la meilleure façon
de penser à ce sujet,

749
00:37:46,840 --> 00:37:50,830
tous table de hachage est une
tableau de listes liées.

750
00:37:50,830 --> 00:37:55,670
Et donc, dans ce sens, vous avez
ce beau tableau de pointeurs,

751
00:37:55,670 --> 00:37:58,740
puis chaque pointeur dans
cette valeur, dans cet indice,

752
00:37:58,740 --> 00:38:00,740
peut effectivement pointer vers d'autres choses.

753
00:38:00,740 --> 00:38:05,720
Et si vous avez tous ces séparée
les chaînes qui sortent d'un grand tableau.

754
00:38:05,720 --> 00:38:07,960
>> Et donc là, si je
voulu insérer Berry,

755
00:38:07,960 --> 00:38:11,220
Je sais, OK, je vais à l'entrée
à travers ma fonction de hachage.

756
00:38:11,220 --> 00:38:15,070
Je vais finir avec l'indice de
1, et puis je vais être en mesure d'avoir

757
00:38:15,070 --> 00:38:20,410
juste un petit sous-ensemble de cette
140.000 mots géant dictionnaire.

758
00:38:20,410 --> 00:38:24,220
Et puis, je peux simplement regarder
26.1 travers de cela.

759
00:38:24,220 --> 00:38:27,910
>> Et alors je peux juste insérer
Berry soit avant ou après la banane

760
00:38:27,910 --> 00:38:28,820
dans ce cas?

761
00:38:28,820 --> 00:38:29,700
Après, non?

762
00:38:29,700 --> 00:38:33,920
Et si vous allez vouloir
insérer ce noeud après la banane,

763
00:38:33,920 --> 00:38:36,667
et donc vous allez insérer
à la queue de la liste liée.

764
00:38:36,667 --> 00:38:38,500
Je vais revenir
à cette diapositive précédente,

765
00:38:38,500 --> 00:38:40,680
de sorte que vous pouvez voir comment les gars
fonction de hachage fonctionne.

766
00:38:40,680 --> 00:38:43,980
>> Donc fonction de hachage est cette équation
que vous sorte de votre entrée en cours d'exécution

767
00:38:43,980 --> 00:38:46,940
jusqu'à obtenir ce que l'index
vous voulez affecter vers.

768
00:38:46,940 --> 00:38:51,130
Et donc, dans cet exemple, tout ce qu'on voulait
à faire était de prendre la première lettre,

769
00:38:51,130 --> 00:38:55,890
le transformer en un indice, alors nous
peut stocker que dans notre fonction de hachage.

770
00:38:55,890 --> 00:39:00,160
Tout ce que nous faisons ici est que nous sommes
convertir la première lettre.

771
00:39:00,160 --> 00:39:04,770
Donc KeyKey [0] est tout simplement la première lettre
de quelque chaîne que nous allons avoir,

772
00:39:04,770 --> 00:39:05,720
nous passons en.

773
00:39:05,720 --> 00:39:09,740
Nous convertir ce à supérieure, et
nous soustrayant par majuscule,

774
00:39:09,740 --> 00:39:11,740
donc tout ce qui est fait
nous donne un certain nombre

775
00:39:11,740 --> 00:39:13,670
dans lequel nous pouvons hachage sur nos valeurs.

776
00:39:13,670 --> 00:39:16,550
>> Et puis nous allons
retourner hachage taille de module.

777
00:39:16,550 --> 00:39:19,340
Soyez très, très prudent
parce que, théoriquement, ici

778
00:39:19,340 --> 00:39:21,870
votre valeur de hachage pourrait être infinie.

779
00:39:21,870 --> 00:39:23,660
Il pourrait simplement aller sur et sur et sur.

780
00:39:23,660 --> 00:39:26,080
Il pourrait être une vraiment,
très grande valeur,

781
00:39:26,080 --> 00:39:29,849
mais parce que votre table de hachage
vous avez créé a seulement 26 indices,

782
00:39:29,849 --> 00:39:31,890
vous voulez vous assurer que votre
modulusing afin que vous

783
00:39:31,890 --> 00:39:33,848
ne run-- il est le même
chose que votre queue--

784
00:39:33,848 --> 00:39:36,320
de sorte que vous ne courez pas au large de la
bas de votre fonction de hachage.

785
00:39:36,320 --> 00:39:39,210
>> Vous voulez de l'envelopper de retour autour
de la même manière dans [inaudible] lorsque

786
00:39:39,210 --> 00:39:41,750
vous aviez comme un très,
très grande lettre, vous

787
00:39:41,750 --> 00:39:43,740
je ne voulais pas que cela se
il suffit d'exécuter l'extrémité.

788
00:39:43,740 --> 00:39:46,948
Même chose ici, vous voulez vous assurer que
il ne coule pas la fin en enveloppant

789
00:39:46,948 --> 00:39:48,330
autour de la partie supérieure de la table.

790
00:39:48,330 --> 00:39:50,530
Donc, ceci est juste un très
fonction de hachage simple.

791
00:39:50,530 --> 00:39:56,570
Tout ce qui n'a fait que prendre la première
lettre quelle que soit notre entrée était

792
00:39:56,570 --> 00:40:01,660
et le transformer en un indice qui
nous pourrions mettre dans notre table de hachage.

793
00:40:01,660 --> 00:40:05,450
>> Ouais, et ainsi que je l'ai dit avant,
la manière dont nous résolvons les collisions

794
00:40:05,450 --> 00:40:09,330
dans notre hash tables éprouvent,
ce que nous appelons, chaînage.

795
00:40:09,330 --> 00:40:13,860
Donc, si vous essayez d'insérer multiples
mots qui commencent par la même chose,

796
00:40:13,860 --> 00:40:16,145
vous allez avoir une valeur de hachage.

797
00:40:16,145 --> 00:40:18,770
Les avocats et les pommes, si vous avez
le lancer à travers notre fonction de hachage,

798
00:40:18,770 --> 00:40:21,450
vont vous donner la
même nombre, le nombre de 0.

799
00:40:21,450 --> 00:40:24,550
Et la façon dont nous résoudre qui est
que nous pouvons réellement sorte de lien entre eux

800
00:40:24,550 --> 00:40:27,010
ensemble via des listes chaînées.

801
00:40:27,010 --> 00:40:29,600
>> Et dans ce sens,
vous les gars peuvent voir genre

802
00:40:29,600 --> 00:40:32,640
de la façon dont des structures de données
nous avons précédemment fixons

803
00:40:32,640 --> 00:40:35,870
comme une liste liée raisin genre
de peuvent se réunir en un seul.

804
00:40:35,870 --> 00:40:38,860
Et puis, vous pouvez créer autant
structures de données plus efficaces

805
00:40:38,860 --> 00:40:43,350
qui peut gérer de grandes quantités de
données, ce redimensionner dynamiquement en fonction

806
00:40:43,350 --> 00:40:44,870
sur vos besoins.

807
00:40:44,870 --> 00:40:45,620
Tout le monde est clair?

808
00:40:45,620 --> 00:40:47,580
Tout le monde sorte de clair
sur ce qui se passe ici?

809
00:40:47,580 --> 00:40:52,110
>> Si je voulais insert-- ce qui est un
fruit qui commence par, je ne sais pas,

810
00:40:52,110 --> 00:40:54,726
B, autres que les baies, les bananes.

811
00:40:54,726 --> 00:40:55,710
>> AUDIENCE: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI PENG: Blackberry, Blackberry.

813
00:40:57,910 --> 00:41:00,530
Où BlackBerry aller ici?

814
00:41:00,530 --> 00:41:04,251
Eh bien, nous avons fait pas trié
encore, mais en théorie

815
00:41:04,251 --> 00:41:06,250
Si nous voulions avoir cette
dans l'ordre alphabétique,

816
00:41:06,250 --> 00:41:07,944
où la mûre devrait aller?

817
00:41:07,944 --> 00:41:09,210
>> AUDIENCE: [inaudible]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG: Exactement, après ici, non?

819
00:41:11,100 --> 00:41:14,950
Mais depuis il est très difficile de
reorder-- Je suppose que cela est à vous les gars.

820
00:41:14,950 --> 00:41:17,920
Les gars, vous pouvez tout à fait
mettre en œuvre tout ce que vous voulez.

821
00:41:17,920 --> 00:41:20,730
La façon la plus efficace
de le faire peut-être

822
00:41:20,730 --> 00:41:24,570
serait de trier vos liée
liste dans l'ordre alphabétique,

823
00:41:24,570 --> 00:41:26,520
et donc quand vous êtes
l'insertion des choses, que vous voulez

824
00:41:26,520 --> 00:41:28,632
pour être sûr de les insérer
dans l'ordre alphabétique

825
00:41:28,632 --> 00:41:30,590
de sorte que lorsque vous êtes alors
en essayant de les rechercher,

826
00:41:30,590 --> 00:41:32,410
vous ne disposez pas de traverser tout.

827
00:41:32,410 --> 00:41:35,290
Vous savez exactement où
il est, et il est plus facile.

828
00:41:35,290 --> 00:41:39,100
>> Mais si vous avez sorte de
entrecoupées de choses au hasard,

829
00:41:39,100 --> 00:41:41,420
vous allez encore avoir
pour traverser toute façon.

830
00:41:41,420 --> 00:41:44,990
Et si je voulais juste
BlackBerry insérer ici

831
00:41:44,990 --> 00:41:47,470
et je voulais chercher
il, je sais, oh, BlackBerry

832
00:41:47,470 --> 00:41:52,012
doit commencer par l'indice de 1, donc je
connaître instantanément suffit de chercher à 1.

833
00:41:52,012 --> 00:41:53,970
Et puis je peux type de
parcourir la liste chaînée

834
00:41:53,970 --> 00:41:56,120
jusqu'à ce que je reçois de BlackBerry,
et alors-- ouais?

835
00:41:56,120 --> 00:41:59,550
>> Public: Si vous essayez de create--
Je suppose que ce genre est un hachage très simple

836
00:41:59,550 --> 00:42:00,050
fonction.

837
00:42:00,050 --> 00:42:02,835
Et si nous voulions faire
de multiples couches de que, comme,

838
00:42:02,835 --> 00:42:05,870
OK, nous voulons séparer en
comme toutes les lettres de l'alphabet

839
00:42:05,870 --> 00:42:09,040
et puis de nouveau à aimer un autre jeu
de lettres alphabétiques dans ce cadre,

840
00:42:09,040 --> 00:42:11,715
mettons-nous comme un hachage
tableau dans un tableau de hachage,

841
00:42:11,715 --> 00:42:13,256
ou comme une fonction au sein d'une fonction?

842
00:42:13,256 --> 00:42:14,880
Ou est that--

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG: Donc, votre hachage
function-- votre table de hachage

844
00:42:17,510 --> 00:42:19,360
peut être aussi grand que vous le souhaitez.

845
00:42:19,360 --> 00:42:21,930
Donc, dans ce sens, je pensais
il était très facile, très

846
00:42:21,930 --> 00:42:25,320
simple pour moi de repose juste une sorte
sur les lettres du premier mot.

847
00:42:25,320 --> 00:42:28,690
Et donc il ya seulement 26 options.

848
00:42:28,690 --> 00:42:32,650
Je ne peux obtenir 26 options de
0 à 25 car ils ne peuvent

849
00:42:32,650 --> 00:42:36,510
commencer de A à Z. Mais si vous voulez
d'ajouter, peut-être, plus de complexité

850
00:42:36,510 --> 00:42:39,260
ou plus courir de temps à votre
table de hachage des, vous avez absolument

851
00:42:39,260 --> 00:42:40,760
peut faire toutes sortes de choses.

852
00:42:40,760 --> 00:42:43,330
Vous pouvez faire votre propre
équation qui vous donne

853
00:42:43,330 --> 00:42:48,000
plus la distribution dans votre
mots, puis lorsque vous recherchez,

854
00:42:48,000 --> 00:42:49,300
ça va être plus rapide.

855
00:42:49,300 --> 00:42:52,100
>> Il est totalement à vous les gars
comment vous voulez mettre en oeuvre.

856
00:42:52,100 --> 00:42:55,140
Pensez-y comme seulement seaux.

857
00:42:55,140 --> 00:42:57,376
Si je voulais avoir
26 seaux, je vais

858
00:42:57,376 --> 00:42:59,420
pour arranger les choses dans ces seaux.

859
00:42:59,420 --> 00:43:02,980
Mais je vais avoir un tas
de choses dans chaque seau,

860
00:43:02,980 --> 00:43:05,890
donc si vous voulez faire
plus rapide et plus efficace,

861
00:43:05,890 --> 00:43:07,190
laissez-moi avoir une centaine de seaux.

862
00:43:07,190 --> 00:43:09,290
>> Mais alors vous devez trouver un
façon de régler les choses de sorte qu'ils sont

863
00:43:09,290 --> 00:43:11,040
dans le seau correcte ils devraient être dans.

864
00:43:11,040 --> 00:43:13,331
Mais alors, quand vous avez réellement
vouloir regarder ce seau,

865
00:43:13,331 --> 00:43:16,410
il est beaucoup plus rapide car il ya
moins de choses dans chaque seau.

866
00:43:16,410 --> 00:43:20,250
Et donc, oui, qui est en fait
le truc pour vous les gars dans pset5

867
00:43:20,250 --> 00:43:22,360
est que vous serez
défié de créer simplement

868
00:43:22,360 --> 00:43:26,170
ce qui est le plus efficace
fonction que vous pouvez penser à être

869
00:43:26,170 --> 00:43:28,520
capable de stocker et de vérifier ces valeurs.

870
00:43:28,520 --> 00:43:30,840
>> Totalement à vous les gars
mais vous voulez le faire,

871
00:43:30,840 --> 00:43:32,229
mais qui est un très bon point.

872
00:43:32,229 --> 00:43:34,520
Que le genre de logique vous
vouloir commencer à penser à

873
00:43:34,520 --> 00:43:37,236
est, bien, pourquoi dois-je pas faire plus seaux.

874
00:43:37,236 --> 00:43:39,527
Et puis je dois rechercher
moins de choses, et alors peut-être que je

875
00:43:39,527 --> 00:43:41,640
avoir une fonction de hachage différent.

876
00:43:41,640 --> 00:43:45,500
>> Oui, il ya beaucoup de façons de le faire
pset, certains sont plus rapides que d'autres.

877
00:43:45,500 --> 00:43:50,630
Je suis totalement d'aller voir à quel point
était rapide les plus rapides vous les gars

878
00:43:50,630 --> 00:43:55,170
être en mesure d'obtenir vos fonctions à travailler.

879
00:43:55,170 --> 00:43:58,176
OK, tout le monde sur la bonne
chaînage et de hachage tables?

880
00:43:58,176 --> 00:44:00,800
Il est en fait très simple comme un
notion si vous pensez à ce sujet.

881
00:44:00,800 --> 00:44:05,160
Tout ce qu'il est est ce que la séparation
vos entrées sont dans des seaux,

882
00:44:05,160 --> 00:44:10,670
les trier, puis en recherchant la
énumère qu'il y est associé.

883
00:44:10,670 --> 00:44:11,852
>> Frais.

884
00:44:11,852 --> 00:44:18,160
Très bien, maintenant, nous avons une sorte différente
de structure de données que l'on appelle un arbre.

885
00:44:18,160 --> 00:44:20,850
Allons et parlent essais
qui sont nettement différentes,

886
00:44:20,850 --> 00:44:22,330
mais dans la même catégorie.

887
00:44:22,330 --> 00:44:29,010
Essentiellement, tout est un arbre à la place
organiser les données de manière linéaire dans la

888
00:44:29,010 --> 00:44:32,560
qu'une table de hachage vous does--
le savez, il a un haut et un bas

889
00:44:32,560 --> 00:44:37,900
et puis vous type de lien hors de it-- une
arbre a un top que vous appelez la racine,

890
00:44:37,900 --> 00:44:40,220
et puis il a des feuilles tout autour de lui.

891
00:44:40,220 --> 00:44:42,390
>> Et tout ce que vous avez ici
est tout simplement le nœud supérieur

892
00:44:42,390 --> 00:44:45,980
que les points à d'autres noeuds, que les points
à plusieurs noeuds, et ainsi de suite et ainsi de suite.

893
00:44:45,980 --> 00:44:48,130
Et donc vous avez juste branches fractionnement.

894
00:44:48,130 --> 00:44:53,255
Il est juste une façon différente d'organiser
données, et parce que nous appelons un arbre,

895
00:44:53,255 --> 00:44:56,270
vous les gars just-- il est juste
modélisé pour ressembler à un arbre.

896
00:44:56,270 --> 00:44:57,670
Voilà pourquoi nous appelons les arbres.

897
00:44:57,670 --> 00:44:59,370
>> Table de hachage ressemble à une table.

898
00:44:59,370 --> 00:45:01,310
Un arbre ressemble à un arbre.

899
00:45:01,310 --> 00:45:03,300
Tout ce qu'il est est un séparée
façon d'organiser les nœuds

900
00:45:03,300 --> 00:45:06,020
en fonction de ce que sont vos besoins.

901
00:45:06,020 --> 00:45:11,810
>> Donc, vous avez une racine et
alors vous avez des feuilles.

902
00:45:11,810 --> 00:45:15,380
La façon dont nous pouvons particulier
penser est un arbre binaire,

903
00:45:15,380 --> 00:45:18,150
un arbre binaire est juste un
type spécifique d'un arbre

904
00:45:18,150 --> 00:45:22,450
où chaque noeud seuls points
à, au maximum, deux autres noeuds.

905
00:45:22,450 --> 00:45:25,434
Et là, vous avez distincte
symétrie dans votre arbre

906
00:45:25,434 --> 00:45:28,600
qui le rend plus facile à genre de look
à ce que les valeurs que vous êtes parce que vous

907
00:45:28,600 --> 00:45:30,150
toujours avoir une gauche ou un droit.

908
00:45:30,150 --> 00:45:33,150
Il n'y a jamais comme un tiers gauche de
ou le quart gauche depuis le côté gauche.

909
00:45:33,150 --> 00:45:36,358
Il est juste que vous avez une gauche et une droite
et vous pouvez rechercher soit des deux.

910
00:45:36,358 --> 00:45:38,980
Et pourquoi est-ce utile?

911
00:45:38,980 --> 00:45:40,980
La façon dont cela est
est utile si vous êtes à la recherche

912
00:45:40,980 --> 00:45:42,890
de recherche à travers des valeurs, non?

913
00:45:42,890 --> 00:45:45,640
Plutôt que de mettre en œuvre binaire
recherche dans un tableau d'erreur,

914
00:45:45,640 --> 00:45:49,260
si vous voulez être en mesure d'insérer noeuds
et enlever les nœuds à volonté et aussi

915
00:45:49,260 --> 00:45:52,185
préserver la recherche
capacités de recherche binaire.

916
00:45:52,185 --> 00:45:54,560
Donc, de cette manière, nous sommes en quelque sorte
tricking-- souvenir lorsque nous

917
00:45:54,560 --> 00:45:56,530
ladite listes chaînées ne pouvez pas rechercher binaire?

918
00:45:56,530 --> 00:46:01,700
Nous sommes en quelque sorte de créer une structure de données
que des astuces qui en travaillant.

919
00:46:01,700 --> 00:46:05,034
>> Et parce que les listes liées sont linéaires,
elles sont liées seulement l'une après l'autre.

920
00:46:05,034 --> 00:46:06,950
Nous pouvons avoir de genre
autre type de pointeurs

921
00:46:06,950 --> 00:46:09,408
ce point à différents noeuds
qui peut nous aider à la recherche.

922
00:46:09,408 --> 00:46:12,590
Et ici, si je voulais
avoir un arbre binaire de recherche,

923
00:46:12,590 --> 00:46:14,090
Je sais que mon milieu, si 55.

924
00:46:14,090 --> 00:46:18,280
Je vais juste pour créer ce que
comme mon milieu, comme ma racine,

925
00:46:18,280 --> 00:46:20,770
et puis je vais devoir
valeurs spin off de celui-ci.

926
00:46:20,770 --> 00:46:25,610
>> Donc, ici, si je vais à la recherche de
la valeur de 66, je peux commencer à 55.

927
00:46:25,610 --> 00:46:27,310
Il est 66 supérieure à 55?

928
00:46:27,310 --> 00:46:30,970
Oui, il est, donc je sais que je cherche mus
i n le droit pointeur de cet arbre.

929
00:46:30,970 --> 00:46:32,440
Je vais à 77.

930
00:46:32,440 --> 00:46:35,367
OK, est inférieur à 66 ou supérieur à 77?

931
00:46:35,367 --> 00:46:37,950
Il est moins, donc vous savez, oh,
ce doit être le nœud gauche.

932
00:46:37,950 --> 00:46:41,410
>> Et ici nous sommes en quelque sorte de préserver
toutes les grandes choses au sujet des tableaux,

933
00:46:41,410 --> 00:46:44,420
ainsi comme le redimensionnement dynamique
des objets, étant

934
00:46:44,420 --> 00:46:49,530
capable d'insérer et de supprimer à volonté,
sans avoir à se soucier du fixe

935
00:46:49,530 --> 00:46:50,370
quantité d'espace.

936
00:46:50,370 --> 00:46:52,820
Nous conservons encore tous
ces choses merveilleuses

937
00:46:52,820 --> 00:46:57,140
tout en étant capable de conserver la
log et le temps de recherche de recherche binaire

938
00:46:57,140 --> 00:47:00,450
que nous étions seulement auparavant
en mesure d'obtenir une phrase.

939
00:47:00,450 --> 00:47:06,310
>> Structure de données Cool, sorte de
complexe à implémenter, le nœud.

940
00:47:06,310 --> 00:47:08,311
Comme vous pouvez le voir, tout ce qu'il
est la structure du noeud

941
00:47:08,311 --> 00:47:10,143
est que vous avez une gauche
et un pointeur à droite.

942
00:47:10,143 --> 00:47:11,044
Voilà tout ce qu'il est.

943
00:47:11,044 --> 00:47:12,960
Donc, plutôt que de simplement
ayant un X ou un précédent.

944
00:47:12,960 --> 00:47:15,920
Vous disposez d'un gauche ou droit, puis
vous pouvez sorte de les relier entre eux

945
00:47:15,920 --> 00:47:16,836
Cependant vous le souhaitez.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, nous allons en fait
il suffit de prendre quelques minutes.

948
00:47:24,270 --> 00:47:25,790
Donc, nous allons revenir ici.

949
00:47:25,790 --> 00:47:28,270
Comme je le disais précédemment,
Je sorte de expliquai

950
00:47:28,270 --> 00:47:31,520
la logique derrière la façon dont nous
chercherait par ce biais.

951
00:47:31,520 --> 00:47:33,860
Nous allons essayer
pseudocoding ceci à voir

952
00:47:33,860 --> 00:47:38,000
si nous pouvons appliquer le genre de
même logique de recherche binaire

953
00:47:38,000 --> 00:47:40,055
à un type de structure de données différent.

954
00:47:40,055 --> 00:47:45,049
Si vous voulez les gars à prendre comme un couple
minutes pour penser juste à ce sujet.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
D'ACCORD.

957
00:48:46,925 --> 00:48:51,407
Très bien, je vais
en fait juste vous donner the-- pas,

958
00:48:51,407 --> 00:48:52,990
nous allons parler de la pseudo-première.

959
00:48:52,990 --> 00:48:56,580
Donc Quelqu'un veut-
pour donner un coup de couteau à ce

960
00:48:56,580 --> 00:49:02,100
la première chose que vous voulez faire quand
vous commencez la recherche est?

961
00:49:02,100 --> 00:49:04,460
Si nous sommes à la recherche
la valeur de 66, ce qui est

962
00:49:04,460 --> 00:49:07,940
la première chose que nous voulons faire si
nous voulons binaires de recherche cet arbre?

963
00:49:07,940 --> 00:49:10,760
>> AUDIENCE: Vous voulez regarder à droite
et de regarder à gauche et voir [inaudible]

964
00:49:10,760 --> 00:49:11,230
plus grand nombre.

965
00:49:11,230 --> 00:49:12,271
>> ANDI PENG: Oui, exactement.

966
00:49:12,271 --> 00:49:15,350
Donc, vous allez regarder votre racine.

967
00:49:15,350 --> 00:49:18,180
Il ya beaucoup de façons que vous pouvez appeler
, vos gens nœud parent dire.

968
00:49:18,180 --> 00:49:21,317
Je tiens à dire, car la racine
qui est comme la racine de l'arbre.

969
00:49:21,317 --> 00:49:23,400
Vous allez regarder
votre nœud racine, et vous êtes

970
00:49:23,400 --> 00:49:26,940
allez voir est 66 supérieure
ou inférieur à 55.

971
00:49:26,940 --> 00:49:30,360
Et si elle est supérieure à, eh bien, il est
supérieure, où voulons-nous chercher?

972
00:49:30,360 --> 00:49:32,000
Où voulons-nous pour chercher maintenant, non?

973
00:49:32,000 --> 00:49:34,340
Nous voulons rechercher la
la moitié droite de cet arbre.

974
00:49:34,340 --> 00:49:38,390
>> Nous avons donc, idéalement, un
pointeur qui pointe vers la droite.

975
00:49:38,390 --> 00:49:44,325
Et alors nous pouvons mettre en
notre nouvelle racine soit 77.

976
00:49:44,325 --> 00:49:46,450
Nous pouvons simplement aller là où
Positionnez le pointeur.

977
00:49:46,450 --> 00:49:49,100
Eh bien, oh, ici nous commençons
à 77, et nous ne pouvons tout simplement

978
00:49:49,100 --> 00:49:51,172
le faire de manière récursive encore et encore.

979
00:49:51,172 --> 00:49:52,880
De cette façon, vous genre
d'avoir une fonction.

980
00:49:52,880 --> 00:49:57,430
Vous avez une façon de chercher que vous
peut simplement répéter encore et encore et encore,

981
00:49:57,430 --> 00:50:02,720
selon l'endroit où vous voulez regarder
jusqu'à ce que vous obtenez finalement à la valeur

982
00:50:02,720 --> 00:50:04,730
que vous êtes à la recherche pour.

983
00:50:04,730 --> 00:50:05,230
Donner un sens?

984
00:50:05,230 --> 00:50:07,800
>> Je suis sur le point de vous montrer la réelle
code, et il ya beaucoup de code.

985
00:50:07,800 --> 00:50:08,674
Pas besoin de paniquer.

986
00:50:08,674 --> 00:50:09,910
Nous parlerons à travers elle.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> En fait non.

989
00:50:14,020 --> 00:50:15,061
Ce était juste pseudo.

990
00:50:15,061 --> 00:50:17,860
OK, qui était juste le pseudo-code,
qui est un peu complexe,

991
00:50:17,860 --> 00:50:19,751
mais il est tout à fait bien.

992
00:50:19,751 --> 00:50:21,000
Tout le monde suit le long ici?

993
00:50:21,000 --> 00:50:24,260
Si la racine est null, le retour
faux parce que les moyens

994
00:50:24,260 --> 00:50:26,850
vous ne même pas quelque chose là-bas.

995
00:50:26,850 --> 00:50:31,376
>> Si la racine n est la valeur, de sorte que si elle
se trouve être celui que vous cherchez à,

996
00:50:31,376 --> 00:50:34,000
alors vous allez retourner vrai
parce que vous savez vous l'avez trouvé.

997
00:50:34,000 --> 00:50:36,250
Mais si la valeur est inférieure
de racine de n, vous êtes

998
00:50:36,250 --> 00:50:38,332
aller chercher la gauche
enfant ou la feuille de gauche,

999
00:50:38,332 --> 00:50:39,540
tout ce que vous voulez l'appeler.

1000
00:50:39,540 --> 00:50:41,750
Et si la valeur est supérieure à la racine,
vous allez chercher le bon arbre,

1001
00:50:41,750 --> 00:50:44,610
puis il suffit d'exécuter la fonction
grâce à la recherche à nouveau.

1002
00:50:44,610 --> 00:50:48,037
>> Et si la racine est nulle, ce qui
signifie que vous avez atteint la fin?

1003
00:50:48,037 --> 00:50:50,120
Cela signifie que vous avez pas
plus plus part à la recherche,

1004
00:50:50,120 --> 00:50:52,230
alors vous savez, oh, je
suppose qu'il est pas ici

1005
00:50:52,230 --> 00:50:55,063
parce que, après, je l'ai regardé à travers
toute chose et il est pas là,

1006
00:50:55,063 --> 00:50:56,930
ça pourrait ne pas être ici.

1007
00:50:56,930 --> 00:50:58,350
>> Est-ce que de sens pour tout le monde?

1008
00:50:58,350 --> 00:51:03,230
Donc, il est comme la préservation de recherche binaire
les capacités de listes chaînées.

1009
00:51:03,230 --> 00:51:09,200
, Et de sorte que le deuxième type cool
de la structure de données que vous les gars

1010
00:51:09,200 --> 00:51:13,180
peut essayer de mettre en œuvre sur votre pset,
il suffit de choisir une méthode.

1011
00:51:13,180 --> 00:51:19,430
Mais peut-être une méthode alternative pour
la table de hachage est ce que nous appelons un trie.

1012
00:51:19,430 --> 00:51:24,080
>> Tout un trie est est un
type spécifique de arbre

1013
00:51:24,080 --> 00:51:28,600
a des valeurs qui vont à d'autres valeurs.

1014
00:51:28,600 --> 00:51:31,450
Ainsi, au lieu d'avoir un binaire
arbre dans le sens où seulement une

1015
00:51:31,450 --> 00:51:35,940
chose peut pointer à deux, vous pouvez avoir
Point à beaucoup, beaucoup de choses une chose.

1016
00:51:35,940 --> 00:51:39,450
Vous avez essentiellement tableaux
l'intérieur de laquelle vous stockez

1017
00:51:39,450 --> 00:51:41,790
pointeurs qui pointent vers d'autres réseaux.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Donc, le nœud de la façon dont nous
définirait un trie

1020
00:51:49,460 --> 00:51:52,590
est que nous voulons avoir une
Boolean, c mot, non?

1021
00:51:52,590 --> 00:51:54,920
Ainsi, le noeud est booléenne
comme vrai ou faux,

1022
00:51:54,920 --> 00:51:58,490
tout d'abord à la tête de
ce tableau, est-ce un mot?

1023
00:51:58,490 --> 00:52:03,620
Deuxièmement, vous voulez avoir des pointeurs
à tout ce que le reste d'entre eux sont.

1024
00:52:03,620 --> 00:52:07,470
Un peu complexe, un peu abstrait, mais
Je vais vous expliquer ce que tous les moyens.

1025
00:52:07,470 --> 00:52:13,800
>> Donc, ici, au sommet, si vous
ont un tableau déclaré déjà,

1026
00:52:13,800 --> 00:52:17,040
un noeud où vous avez un booléen
valeur stockée à l'avant

1027
00:52:17,040 --> 00:52:19,490
qui vous dit est-ce un mot?

1028
00:52:19,490 --> 00:52:20,520
Est-ce pas un mot?

1029
00:52:20,520 --> 00:52:23,240
Et puis vous avez la
reste de votre tableau qui

1030
00:52:23,240 --> 00:52:26,040
stocke en fait tout le
possibilités de ce qu'il pourrait être.

1031
00:52:26,040 --> 00:52:28,660
Ainsi, par exemple, comme
au sommet, vous avez

1032
00:52:28,660 --> 00:52:32,140
la première chose qui dit vrai ou
faux, oui ou non, cela est un mot.

1033
00:52:32,140 --> 00:52:38,130
>> Et puis vous avez de 0 à 26
les lettres que vous pouvez stocker.

1034
00:52:38,130 --> 00:52:42,790
Si je voulais chercher ici
pour les chauve-souris, je vais vers le haut

1035
00:52:42,790 --> 00:52:49,200
et je regarde pour B. je trouve dans mon B
tableau, et ainsi je sais, OK, est B un mot?

1036
00:52:49,200 --> 00:52:53,010
B est pas un mot, donc ainsi
Je dois continuer à chercher.

1037
00:52:53,010 --> 00:52:56,410
Je vais de B, et je me réjouis à la
pointeur qui pointe vers B

1038
00:52:56,410 --> 00:53:00,900
et je vois un autre tableau de l'information,
la même structure que nous avions avant.

1039
00:53:00,900 --> 00:53:05,240
>> Et ici-- oh, la prochaine
lettre de [inaudible] est A.

1040
00:53:05,240 --> 00:53:07,210
Donc, nous regardons dans ce tableau.

1041
00:53:07,210 --> 00:53:10,860
Nous trouvons la huitième valeur,
puis nous attendons à voir, oh,

1042
00:53:10,860 --> 00:53:12,840
Hey, est-ce un mot, est B-A un mot?

1043
00:53:12,840 --> 00:53:13,807
Il est pas un mot.

1044
00:53:13,807 --> 00:53:14,890
Nous devons continuer à chercher.

1045
00:53:14,890 --> 00:53:17,850
>> Et alors nous nous tournons vers où
le pointeur d'un point,

1046
00:53:17,850 --> 00:53:21,130
et il pointe vers une autre façon
que nous avons plus de valeur stockée.

1047
00:53:21,130 --> 00:53:24,150
Et finalement, nous arrivons à
B-A-T, qui est un mot.

1048
00:53:24,150 --> 00:53:25,970
Et donc la prochaine fois
vous regardez, vous allez

1049
00:53:25,970 --> 00:53:30,850
d'avoir ce chèque de, oui,
cette fonction booléenne est vraie.

1050
00:53:30,850 --> 00:53:35,450
Et donc, en ce sens que nous sommes en quelque sorte
d'avoir un arbre avec des tableaux.

1051
00:53:35,450 --> 00:53:39,890
>> Alors vous pouvez type de recherche vers le bas.

1052
00:53:39,890 --> 00:53:43,650
Plutôt que de hachage une fonction et
attribuer des valeurs par liste chaînée,

1053
00:53:43,650 --> 00:53:49,190
vous pouvez simplement mettre en œuvre une
Trie qui recherche Oréal qu.

1054
00:53:49,190 --> 00:53:50,850
Vraiment, vraiment compliqué choses.

1055
00:53:50,850 --> 00:53:54,060
Pas facile de penser parce que je suis comme
cracher autant de structures de données sur

1056
00:53:54,060 --> 00:53:58,710
à vous, mais que tout le monde sorte de
comprendre comment la logique de ce qui fonctionne?

1057
00:53:58,710 --> 00:54:01,920
>> OK cool.

1058
00:54:01,920 --> 00:54:05,600
Donc B-A-T, puis
vous allez chercher.

1059
00:54:05,600 --> 00:54:07,940
La prochaine fois que vous allez
pour voir, oh, hé, il est vrai,

1060
00:54:07,940 --> 00:54:09,273
donc je sais que ce doit être un mot.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Même chose pour le zoo.

1063
00:54:13,770 --> 00:54:17,960
Alors, voici la chose en ce moment, si nous
voulu chercher zoo, en ce moment,

1064
00:54:17,960 --> 00:54:20,780
actuellement zoo est pas un
mot dans notre dictionnaire

1065
00:54:20,780 --> 00:54:25,300
parce que, comme vous les gars peut le voir, le
la première place que nous avons un booléen

1066
00:54:25,300 --> 00:54:28,590
return true est à la fin de zoom.

1067
00:54:28,590 --> 00:54:30,430
Nous avons Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> Et alors voici, nous ne disposons pas fait
le mot, zoo, dans notre dictionnaire

1069
00:54:33,900 --> 00:54:36,070
parce que cette case est décochée.

1070
00:54:36,070 --> 00:54:39,540
Ainsi, l'ordinateur n'a pas
sachez que le zoo est un mot

1071
00:54:39,540 --> 00:54:42,430
parce que la façon que nous avons
stocké, seulement un zoom ici

1072
00:54:42,430 --> 00:54:44,920
a effectivement une valeur booléenne
ce qui a été tourné vrai.

1073
00:54:44,920 --> 00:54:49,380
Donc, si nous voulons insérer le
mot, zoo, dans notre dictionnaire,

1074
00:54:49,380 --> 00:54:51,770
comment pourrions-nous le faire de cela?

1075
00:54:51,770 --> 00:54:55,960
Que devons-nous faire pour nous assurer que notre
ordinateur sait que Z-O-O est un mot

1076
00:54:55,960 --> 00:54:58,130
et pas le premier mot est Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> AUDIENCE: [inaudible]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI PENG: Exactement, nous
voulez vous assurer que cette

1079
00:55:01,450 --> 00:55:07,890
ici, cette valeur booléenne est
coché qu'il est vrai.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, puis nous allons vérifier que,
nous savons donc exactement, hey, zoo est un mot.

1081
00:55:13,297 --> 00:55:15,380
Je vais dire à la
ordinateur qu'il est un mot si

1082
00:55:15,380 --> 00:55:18,000
que, lorsque les contrôles de l'ordinateur,
il sait que le zoo est un mot.

1083
00:55:18,000 --> 00:55:21,269
>> Car rappelez-vous toutes ces données
structures, il est très facile pour nous

1084
00:55:21,269 --> 00:55:22,310
à-dire, oh, chauve-souris est un mot.

1085
00:55:22,310 --> 00:55:22,851
Zoo est un mot.

1086
00:55:22,851 --> 00:55:23,611
Zoom est un mot.

1087
00:55:23,611 --> 00:55:25,860
Mais quand vous construire,
l'ordinateur n'a aucune idée.

1088
00:55:25,860 --> 00:55:28,619
>> Donc, vous avez à dire exactement
à quel moment est-ce un mot?

1089
00:55:28,619 --> 00:55:29,910
À quel moment est-il pas un mot?

1090
00:55:29,910 --> 00:55:31,784
Et à quel moment dois-je
besoin de chercher des choses,

1091
00:55:31,784 --> 00:55:34,000
et à quel moment dois-je aller?

1092
00:55:34,000 --> 00:55:37,010
Chacun claire de cela?

1093
00:55:37,010 --> 00:55:39,540
Frais.

1094
00:55:39,540 --> 00:55:42,530
>> Et puis vient le
problème de comment pourrions-nous

1095
00:55:42,530 --> 00:55:45,560
aller sur l'insertion de quelque chose
qui est en fait pas là?

1096
00:55:45,560 --> 00:55:49,090
Donc disons que nous voulons insérer
le mot, salle de bain, dans notre trie.

1097
00:55:49,090 --> 00:55:53,589
Comme vous les gars peuvent voir comme actuellement
tout ce que nous avons maintenant est B-A-T,

1098
00:55:53,589 --> 00:55:55,630
et cette nouvelle structure de données
il y avait une pinte qui

1099
00:55:55,630 --> 00:55:59,740
pointé nulle parce que nous supposons
que, oh, il n'y a pas de mots après B-A-T,

1100
00:55:59,740 --> 00:56:02,530
Pourquoi avons-nous besoin de garder
avoir des choses après que T.

1101
00:56:02,530 --> 00:56:06,581
>> Mais le problème se pose si nous faisons vous
veulent avoir un mot qui vient après

1102
00:56:06,581 --> 00:56:07,080
T de la.

1103
00:56:07,080 --> 00:56:09,500
Si vous avez de bain, vous êtes
allez vouloir un droit d'H.

1104
00:56:09,500 --> 00:56:13,290
Et la façon dont nous allons faire est
nous allons créer un noeud distinct.

1105
00:56:13,290 --> 00:56:16,840
Nous ne sommes pas attribuons quelque quantité
de mémoire pour cette nouvelle gamme,

1106
00:56:16,840 --> 00:56:20,720
et nous allons réaffecter des pointeurs.

1107
00:56:20,720 --> 00:56:22,947
>> Nous allons assigner le
H, Tout d'abord, ce nul,

1108
00:56:22,947 --> 00:56:24,030
nous allons débarrasser.

1109
00:56:24,030 --> 00:56:26,590
Nous allons avoir
les vers le bas du point H.

1110
00:56:26,590 --> 00:56:30,600
Si nous voyons un H, nous voulons
pour aller à un autre endroit.

1111
00:56:30,600 --> 00:56:33,910
>> Ici, nous pouvons alors cocher oui.

1112
00:56:33,910 --> 00:56:38,170
Si nous avons atteint un H après la T, oh,
alors nous savons que cela est un mot.

1113
00:56:38,170 --> 00:56:41,110
Le booléenne va revenir vrai.

1114
00:56:41,110 --> 00:56:42,950
Tout le monde clair sur comment cela est arrivé?

1115
00:56:42,950 --> 00:56:45,110
D'ACCORD.

1116
00:56:45,110 --> 00:56:47,214
>> Donc, essentiellement, tous
ces structures de données

1117
00:56:47,214 --> 00:56:50,130
que nous avons dépassé aujourd'hui, je l'ai
allé sur eux vraiment, vraiment vite

1118
00:56:50,130 --> 00:56:52,192
et pas dans beaucoup de
détail, et qui est OK.

1119
00:56:52,192 --> 00:56:53,900
Une fois que vous commencez à déconner
avec elle, vous serez

1120
00:56:53,900 --> 00:56:55,733
garder la trace de l'endroit où
tous les pointeurs sont,

1121
00:56:55,733 --> 00:56:58,060
ce qui se passe dans votre
structures de données, et cetera.

1122
00:56:58,060 --> 00:56:59,810
Ils vont être très utile,
et il est à vous

1123
00:56:59,810 --> 00:57:03,890
les gars de figurer totalement comment
vous voulez mettre en œuvre les choses.

1124
00:57:03,890 --> 00:57:07,650
>> Et donc pset4, de 5-- oh, cela est faux.

1125
00:57:07,650 --> 00:57:10,140
Pset5 est fautes d'orthographe.

1126
00:57:10,140 --> 00:57:13,710
Comme je l'ai dit avant, vous allez, une fois
à nouveau, télécharger le code source de nous.

1127
00:57:13,710 --> 00:57:16,210
Il va y avoir trois principaux
choses que vous allez télécharger.

1128
00:57:16,210 --> 00:57:18,470
Vous télécharger les dictionnaires,
KERS, et des textes.

1129
00:57:18,470 --> 00:57:21,660
>> Toutes ces choses sont sont
soit dictionnaires de mots

1130
00:57:21,660 --> 00:57:25,190
que nous voulons que vous vérifiez
ou l'essai de l'information

1131
00:57:25,190 --> 00:57:26,930
que nous voulons que vous Vérifier l'orthographe.

1132
00:57:26,930 --> 00:57:29,670
Et ainsi les dictionnaires
nous donnons vous allez

1133
00:57:29,670 --> 00:57:34,870
pour vous donner des mots réels que nous voulons
de stocker en quelque sorte d'une manière qui est

1134
00:57:34,870 --> 00:57:36,530
plus efficace qu'un tableau.

1135
00:57:36,530 --> 00:57:38,470
Et puis les textes sont
va être ce que nous sommes

1136
00:57:38,470 --> 00:57:43,900
vous demandant de vérifier l'orthographe pour vous assurer
tous les mots, il n'y a de vrais mots.

1137
00:57:43,900 --> 00:57:47,970
>> Et ainsi les trois blocs de
les programmes que nous vous donnerons

1138
00:57:47,970 --> 00:57:51,130
dictionary.c sont appelés,
dictionary.h, et speller.c.

1139
00:57:51,130 --> 00:57:56,500
Et ainsi tout dictionary.c fait est
ce que vous êtes invité à mettre en œuvre.

1140
00:57:56,500 --> 00:57:57,880
Il charge mots.

1141
00:57:57,880 --> 00:58:02,000
Il sort contrôles eux, et il fait en sorte
que tout est correctement insérée.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h est juste un fichier de bibliothèque
qui déclare toutes ces fonctions.

1143
00:58:05,180 --> 00:58:07,650
Et speller.c, nous allons vous donner.

1144
00:58:07,650 --> 00:58:09,290
Vous ne devez pas modifier quoi que ce soit.

1145
00:58:09,290 --> 00:58:14,290
Tout est speller.c ne prendre que,
le charge, vérifie la vitesse de celui-ci,

1146
00:58:14,290 --> 00:58:19,190
teste l'indice de référence comme la façon dont
rapidement, vous êtes en mesure de faire des choses.

1147
00:58:19,190 --> 00:58:20,410
>> Il est un correcteur orthographique.

1148
00:58:20,410 --> 00:58:23,920
Juste ne plaisante pas avec elle, mais assurez-
sûr que vous comprenez ce qu'il fait.

1149
00:58:23,920 --> 00:58:28,090
Nous utilisons une fonction appelée getrusage que
teste les performances de votre sort

1150
00:58:28,090 --> 00:58:28,590
vérificateur.

1151
00:58:28,590 --> 00:58:32,200
Tout ce qu'il fait est essentiellement tester la
le temps de tout dans votre dictionnaire,

1152
00:58:32,200 --> 00:58:33,680
alors assurez-vous que vous le comprenez.

1153
00:58:33,680 --> 00:58:36,660
Veillez à ne pas salir avec elle ou
les autres choses ne seront pas fonctionner correctement.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> Et la majeure partie de ce défi est pour
vous les gars de modifier vraiment dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Nous allons vous donner
140.000 mots dans un dictionnaire.

1157
00:58:48,526 --> 00:58:50,900
Nous allons vous donner un texte
fichier qui a ces mots,

1158
00:58:50,900 --> 00:58:54,840
et nous voulons que vous soyez en mesure d'organiser
les dans une table de hachage ou un trie

1159
00:58:54,840 --> 00:58:58,140
parce que quand nous vous demandons de préciser
check-- imaginez si vous êtes sort

1160
00:58:58,140 --> 00:59:00,690
la vérification comme l'Odyssée d'Homère.

1161
00:59:00,690 --> 00:59:03,010
Il est comme ça énorme, énorme test.

1162
00:59:03,010 --> 00:59:05,190
>> Imaginez si chaque simple
mot que vous aviez à regarder

1163
00:59:05,190 --> 00:59:08,100
à travers un réseau de 140.000 valeurs.

1164
00:59:08,100 --> 00:59:10,350
Ce serait prendre une éternité
pour votre machine de fonctionner.

1165
00:59:10,350 --> 00:59:14,490
Voilà pourquoi nous voulons organiser notre
données dans des structures de données plus efficaces

1166
00:59:14,490 --> 00:59:17,270
comme une table de hachage ou un trie.

1167
00:59:17,270 --> 00:59:20,700
Et puis vous les gars peuvent genre
de l'accès lorsque vous recherchez

1168
00:59:20,700 --> 00:59:22,570
les choses plus facilement et plus rapidement.

1169
00:59:22,570 --> 00:59:24,934
>> Et soyez donc prudent de résoudre les collisions.

1170
00:59:24,934 --> 00:59:27,350
Vous allez obtenir un tas
des paroles de ce départ avec A.

1171
00:59:27,350 --> 00:59:29,957
Vous allez obtenir un tas mots
qui commencent par B. Jusqu'à vous

1172
00:59:29,957 --> 00:59:31,290
les gars comment vous voulez le résoudre.

1173
00:59:31,290 --> 00:59:34,144
Peut-être il ya plus
fonction de hachage efficace

1174
00:59:34,144 --> 00:59:36,810
que seulement la première lettre
quelque chose, et que est à vous

1175
00:59:36,810 --> 00:59:38,190
les gars de sorte de faire ce que vous voulez.

1176
00:59:38,190 --> 00:59:40,148
>> Peut-être que vous voulez ajouter
toutes les lettres ensemble.

1177
00:59:40,148 --> 00:59:43,410
Peut-être que vous voulez voulez faire des choses bizarres
pour tenir compte du nombre de lettres,

1178
00:59:43,410 --> 00:59:43,970
peu importe.

1179
00:59:43,970 --> 00:59:45,386
À vous les gars comment vous voulez faire.

1180
00:59:45,386 --> 00:59:49,262
Si vous voulez faire une table de hachage, si vous
vouloir essayer un trie, totalement à vous.

1181
00:59:49,262 --> 00:59:52,470
Je vais vous avertir à l'avance que le
Trie est généralement un peu plus difficile

1182
00:59:52,470 --> 00:59:54,520
juste parce que il ya beaucoup
plusieurs pointeurs de garder la trace.

1183
00:59:54,520 --> 00:59:55,645
Mais totalement à vous les gars.

1184
00:59:55,645 --> 00:59:58,742
Il est beaucoup plus efficace
dans la plupart des cas.

1185
00:59:58,742 --> 01:00:01,450
Vous voulez vraiment être en mesure de garder
une trace de tous vos pointeurs.

1186
01:00:01,450 --> 01:00:03,850
Comme faire la même chose
que je faisais là.

1187
01:00:03,850 --> 01:00:06,871
Lorsque vous essayez d'insérer
des valeurs dans une table de hachage ou supprimer,

1188
01:00:06,871 --> 01:00:08,620
assurez-vous que vous êtes
vraiment garder la trace

1189
01:00:08,620 --> 01:00:11,860
d'où tout est parce que
il est vraiment facile car si je suis

1190
01:00:11,860 --> 01:00:14,727
essayer d'insérer comme le mot, Andy.

1191
01:00:14,727 --> 01:00:16,810
Disons simplement que ce est un
vrai mot, le mot, andy,

1192
01:00:16,810 --> 01:00:19,640
dans une liste géante de A mots.

1193
01:00:19,640 --> 01:00:22,450
>> Si je viens d'arriver à réaffecter
un mauvais pointeur, oops,

1194
01:00:22,450 --> 01:00:24,940
il y va de l'intégralité des
le reste de ma liste chaînée.

1195
01:00:24,940 --> 01:00:26,897
Maintenant, le seul mot que je
ont est Andy, et maintenant

1196
01:00:26,897 --> 01:00:29,230
tous les autres mots du
dictionnaire ont été perdus.

1197
01:00:29,230 --> 01:00:31,370
Et si vous voulez vous assurer que vous
garder une trace de tous vos pointeurs

1198
01:00:31,370 --> 01:00:33,661
ou bien vous allez obtenir
d'énormes problèmes dans votre code.

1199
01:00:33,661 --> 01:00:35,840
Dessiner les choses avec soin, étape par étape.

1200
01:00:35,840 --> 01:00:37,870
Il rend beaucoup plus facile de penser.

1201
01:00:37,870 --> 01:00:40,910
>> Et enfin, vous voulez être en mesure de
tester vos performances de votre programme

1202
01:00:40,910 --> 01:00:41,618
sur le grand tableau.

1203
01:00:41,618 --> 01:00:43,710
Si vous les gars prendre un
regarder CS50 dès maintenant,

1204
01:00:43,710 --> 01:00:45,210
nous avons ce qu'on appelle le grand tableau.

1205
01:00:45,210 --> 01:00:50,200
Il est la feuille de pointage de la plus rapide
épeler fois de contrôle dans l'ensemble de CS50

1206
01:00:50,200 --> 01:00:55,720
maintenant, je pense que le sommet comme 10
fois je pense que huit d'entre eux sont employés.

1207
01:00:55,720 --> 01:00:57,960
Nous voulons vraiment que vous les gars à nous battre.

1208
01:00:57,960 --> 01:01:00,870
>> Chacun d'entre nous ont essayé de mettre en œuvre
le code le plus rapide possible.

1209
01:01:00,870 --> 01:01:04,880
Nous voulons que vous les gars pour essayer de contester
nous et mettre en œuvre plus rapidement que nous tous

1210
01:01:04,880 --> 01:01:05,550
pouvoir.

1211
01:01:05,550 --> 01:01:07,970
Et si cela est vraiment
la première fois que nous sommes

1212
01:01:07,970 --> 01:01:12,680
vous demandant de faire un gars qui pset
vous pouvez vraiment faire quelle que soit la méthode

1213
01:01:12,680 --> 01:01:13,760
tu veux.

1214
01:01:13,760 --> 01:01:17,730
>> Je dis toujours, ce qui est plus apparenté
à une solution de la vie réelle, non?

1215
01:01:17,730 --> 01:01:19,550
Je dis, hey, je veux que vous faites cela.

1216
01:01:19,550 --> 01:01:21,380
Construire un programme qui fait ça pour moi.

1217
01:01:21,380 --> 01:01:22,630
Faites-le comme vous le voulez.

1218
01:01:22,630 --> 01:01:24,271
Je sais juste que je veux jeûner.

1219
01:01:24,271 --> 01:01:25,770
Voilà votre défi pour cette semaine.

1220
01:01:25,770 --> 01:01:27,531
Vous les gars, nous allons
pour vous donner une tâche.

1221
01:01:27,531 --> 01:01:29,030
Nous allons vous donner un défi.

1222
01:01:29,030 --> 01:01:31,559
Et puis, il est à vous les gars
complètement juste comprendre

1223
01:01:31,559 --> 01:01:34,100
ce qui est le plus rapide et le plus
moyen efficace de mettre en œuvre cette.

1224
01:01:34,100 --> 01:01:34,600
Ouais?

1225
01:01:34,600 --> 01:01:37,476
>> AUDIENCE: Sommes-nous autorisés à se
voulait la recherche des moyens plus rapides

1226
01:01:37,476 --> 01:01:40,821
à faire des tables de hachage en ligne, nous pouvons faire
que et de citer le code de quelqu'un d'autre?

1227
01:01:40,821 --> 01:01:42,070
ANDI PENG: Oui, tout à fait bien.

1228
01:01:42,070 --> 01:01:44,320
Donc, si vous les gars lire les
spec, il ya une ligne

1229
01:01:44,320 --> 01:01:48,310
dans la spécification qui dit que vous les gars
sont totalement libre à la recherche hachage

1230
01:01:48,310 --> 01:01:51,070
fonctions sur ce que sont certains
des fonctions de hachage rapides

1231
01:01:51,070 --> 01:01:54,720
faire tourner les choses à travers comme
Tant que vous citez ce code.

1232
01:01:54,720 --> 01:01:57,220
Ainsi, certaines personnes ont déjà
compris des moyens rapides

1233
01:01:57,220 --> 01:02:00,250
de faire des correcteurs d'orthographe, de la restauration rapide
des moyens de stockage d'informations.

1234
01:02:00,250 --> 01:02:02,750
Totalement à vous les gars si vous
vouloir prendre tout ça, non?

1235
01:02:02,750 --> 01:02:04,045
Assurez-vous que vous citez.

1236
01:02:04,045 --> 01:02:06,170
Le défi ici vraiment
que nous essayons de tester

1237
01:02:06,170 --> 01:02:09,750
est de faire en sorte que vous savez
votre chemin autour de pointeurs.

1238
01:02:09,750 --> 01:02:12,700
Pour autant que vous la mise en œuvre
la fonction réelle de hachage

1239
01:02:12,700 --> 01:02:15,070
et à venir avec comme
le calcul pour le faire,

1240
01:02:15,070 --> 01:02:17,570
vous les gars peuvent faire des recherches quelle que soit
méthodes en ligne vous les gars veulent.

1241
01:02:17,570 --> 01:02:17,996
Ouais?

1242
01:02:17,996 --> 01:02:19,700
>> AUDIENCE: Pouvons-nous citer que
en utilisant le [inaudible]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI PENG: Ouais.

1244
01:02:20,120 --> 01:02:22,328
Vous pouvez tout simplement, dans votre commentaire,
vous pouvez citer comme, oh,

1245
01:02:22,328 --> 01:02:26,127
prise de bla, bla,
yada, fonction de hachage.

1246
01:02:26,127 --> 01:02:27,210
Quelqu'un at-il des questions?

1247
01:02:27,210 --> 01:02:29,694
Nous avons en fait en coup de vent
à travers la section aujourd'hui.

1248
01:02:29,694 --> 01:02:31,610
Je serai ici à
répondre à des questions aussi.

1249
01:02:31,610 --> 01:02:36,570
>> Aussi, comme je le disais, bureau
heures ce soir et demain.

1250
01:02:36,570 --> 01:02:40,307
La spécification de cette semaine est en fait
super facile et super court à lire.

1251
01:02:40,307 --> 01:02:43,140
Je vous conseillerais de prendre un coup d'oeil, juste
lire l'intégralité de celui-ci.

1252
01:02:43,140 --> 01:02:45,730
>> Et Zamyla vous guide fait
à travers chacune des fonctions

1253
01:02:45,730 --> 01:02:49,796
vous avez besoin de mettre en œuvre, et il est donc
très, très clair tout faire.

1254
01:02:49,796 --> 01:02:51,920
Juste pour vous assurer que vous êtes
garder la trace des pointeurs.

1255
01:02:51,920 --> 01:02:53,650
Ceci est un jeu de processeurs très difficile.

1256
01:02:53,650 --> 01:02:56,744
>> Ça ne conteste pas parce que, comme,
oh, les concepts sont tellement plus

1257
01:02:56,744 --> 01:02:59,160
difficile, ou que vous avez à apprendre
tellement nouvelle syntaxe la manière

1258
01:02:59,160 --> 01:03:00,650
que vous avez fait pour la dernière pset.

1259
01:03:00,650 --> 01:03:03,320
Cette pset est difficile parce que
il ya tellement de pointeurs,

1260
01:03:03,320 --> 01:03:06,980
puis il est très, très facile à la fois
vous avez un bogue dans votre code ne pourra pas

1261
01:03:06,980 --> 01:03:08,315
pour trouver où est ce bug.

1262
01:03:08,315 --> 01:03:13,200
>> Et si complète et la foi absolue en vous
les gars pour être en mesure de battre notre [inaudible]

1263
01:03:13,200 --> 01:03:13,700
orthographes.

1264
01:03:13,700 --> 01:03:16,640
Je dois en fait pas une mine écrite
encore, mais je suis en train d'écrire le mien.

1265
01:03:16,640 --> 01:03:19,070
Ainsi, alors que vous écrivez
vôtre, je vais écrire le mien.

1266
01:03:19,070 --> 01:03:21,070
Je vais essayer de faire
la mine plus rapide que le vôtre.

1267
01:03:21,070 --> 01:03:23,940
Nous allons voir qui a le plus rapide d'un.

1268
01:03:23,940 --> 01:03:27,340
>> Et ouais, je vais voir tout
vous les gars ici mardi.

1269
01:03:27,340 --> 01:03:29,510
Je vais lancer un type comme un atelier de pset.

1270
01:03:29,510 --> 01:03:32,640
Toutes les sections ce
semaine sont des ateliers de pset,

1271
01:03:32,640 --> 01:03:36,690
de sorte que vous les gars avez beaucoup de possibilités
de l'aide, les heures de bureau, comme toujours,

1272
01:03:36,690 --> 01:03:41,330
et je vraiment hâte de
lire tous le code de vos gars.

1273
01:03:41,330 --> 01:03:44,160
Je dois quiz ici si vous
les gars veulent venir obtenir ces.

1274
01:03:44,160 --> 01:03:45,880
C'est tout.

1275
01:03:45,880 --> 01:03:48,180