1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Section 6: Moins confortable]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Université de Harvard]

3
00:00:05,040 --> 00:00:07,320
[C'est CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Très bien. Bienvenue à la section 6.

5
00:00:11,840 --> 00:00:14,690
Cette semaine, nous allons parler de structures de données en coupe,

6
00:00:14,690 --> 00:00:19,780
principalement parce que le problème de cette semaine mis sur spellr

7
00:00:19,780 --> 00:00:24,410
fait un tas d'exploration structure différente des données.

8
00:00:24,410 --> 00:00:26,520
Il ya un tas de façons différentes que vous pouvez aller avec le problème posé,

9
00:00:26,520 --> 00:00:31,570
et les structures de données plus vous en savez, plus les choses cool que vous pouvez faire.

10
00:00:31,570 --> 00:00:34,990
>> Donc, nous allons commencer. D'abord nous allons parler de piles,

11
00:00:34,990 --> 00:00:37,530
les données de pile et la file d'attente des structures que nous allons parler.

12
00:00:37,530 --> 00:00:40,560
Les piles et les files d'attente sont vraiment utiles quand on commence à parler de graphiques,

13
00:00:40,560 --> 00:00:44,390
que nous n'allons pas faire beaucoup en ce moment.

14
00:00:44,390 --> 00:00:52,820
Mais ils sont vraiment bons pour comprendre l'une des grandes structures de données fondamentales du CS.

15
00:00:52,820 --> 00:00:54,880
La description de la spécification du jeu de problème,

16
00:00:54,880 --> 00:00:59,260
si vous tirez dessus jusqu'à, parle de piles comme s'apparente à

17
00:00:59,260 --> 00:01:05,239
la pile de plateaux repas que vous avez dans la cafétéria de salles à manger

18
00:01:05,239 --> 00:01:09,680
où manger quand le personnel arrive et met les plateaux repas après qu'ils les ont nettoyés,

19
00:01:09,680 --> 00:01:12,000
ils empiler les uns sur les autres.

20
00:01:12,000 --> 00:01:15,050
Et puis, quand les enfants viennent pour obtenir de la nourriture,

21
00:01:15,050 --> 00:01:19,490
ils tirent les plateaux off, d'abord celui du haut, puis celui ci-dessous, alors que celui ci-dessous.

22
00:01:19,490 --> 00:01:25,190
Donc, en effet, le premier plateau que le personnel de salle à manger poser est la dernière qui obtient enlevé.

23
00:01:25,190 --> 00:01:32,330
Le dernier repas que le personnel mis en est le premier qui obtient enlevé pour le dîner.

24
00:01:32,330 --> 00:01:38,100
Dans l'ensemble spec problème, que vous pouvez télécharger si vous n'avez pas déjà,

25
00:01:38,100 --> 00:01:46,730
nous parlons de la modélisation d'une stucture de données pile en utilisant ce type de structure.

26
00:01:46,730 --> 00:01:51,070
>> Donc, ce que nous avons ici, ce qui est similaire à ce qui a été présenté en conférence,

27
00:01:51,070 --> 00:01:58,120
sauf dans la conférence, nous avons présenté cela avec ints plutôt que char * s.

28
00:01:58,120 --> 00:02:06,250
Cela va être une pile qui stocke quoi?

29
00:02:06,250 --> 00:02:09,009
Daniel? Qu'est-ce qu'on stocker dans cette pile?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? Nous sommes >> stocker des chaînes dans cette pile, exactement.

31
00:02:15,260 --> 00:02:20,950
Tout ce que vous devez avoir afin de créer une pile est un tableau

32
00:02:20,950 --> 00:02:23,920
d'une capacité particulière, qui, dans ce cas,

33
00:02:23,920 --> 00:02:28,020
la capacité va être en majuscules parce que c'est une constante.

34
00:02:28,020 --> 00:02:36,340
Et puis, en plus du tableau, tout ce que nous devons suivre est la taille actuelle de la matrice.

35
00:02:36,340 --> 00:02:38,980
Une chose à noter ici c'est plutôt cool

36
00:02:38,980 --> 00:02:47,060
c'est qu'on création de la structure de données empilées l'une sur l'autre structure de données, la matrice.

37
00:02:47,060 --> 00:02:50,110
Il ya différentes façons de mettre en œuvre des piles.

38
00:02:50,110 --> 00:02:54,250
Nous ne le ferons pas tout à fait encore, mais nous espérons que, après avoir fait les problèmes de listes liées,

39
00:02:54,250 --> 00:03:00,520
vous verrez comment vous pouvez facilement mettre en œuvre une pile au-dessus d'une liste chaînée ainsi.

40
00:03:00,520 --> 00:03:02,640
Mais pour l'instant, nous nous en tiendrons aux tableaux.

41
00:03:02,640 --> 00:03:06,350
Encore une fois, tout ce qu'il faut est un tableau et nous avons juste besoin de suivre la taille du tableau.

42
00:03:06,350 --> 00:03:09,850
[Sam] Désolé, pourquoi est-ce que vous avez dit la pile est au-dessus des cordes?

43
00:03:09,850 --> 00:03:13,440
Pour moi, il semble que les chaînes sont dans la pile.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Ouais. Nous créons, nous prenons notre tableau structure de données -

45
00:03:16,790 --> 00:03:22,130
c'est une très bonne question. Donc la question est pourquoi, pour les gens qui regardent cette ligne,

46
00:03:22,130 --> 00:03:24,140
pourquoi disons-nous que la pile est au-dessus des cordes,

47
00:03:24,140 --> 00:03:27,990
car ici, il semble que les chaînes sont à l'intérieur de la pile?

48
00:03:27,990 --> 00:03:31,050
Ce qui est totalement le cas.

49
00:03:31,050 --> 00:03:34,660
Ce que je faisais allusion à ce que nous avons une structure de données de tableau.

50
00:03:34,660 --> 00:03:39,290
Nous avons un tableau de char * s, ce tableau de chaînes,

51
00:03:39,290 --> 00:03:45,300
et nous allons ajouter à cela afin de créer la structure de données empilées.

52
00:03:45,300 --> 00:03:48,620
>> Ainsi, une pile est un peu plus complexe qu'un tableau.

53
00:03:48,620 --> 00:03:51,890
On peut utiliser un tableau pour construire une pile.

54
00:03:51,890 --> 00:03:55,810
C'est donc là que nous disons que la pile est construite au-dessus d'un tableau.

55
00:03:55,810 --> 00:04:02,510
De même, comme je l'ai dit plus tôt, nous pouvons construire une pile au-dessus d'une liste chaînée.

56
00:04:02,510 --> 00:04:04,960
Au lieu d'utiliser un tableau pour stocker nos éléments,

57
00:04:04,960 --> 00:04:10,070
nous pourrions utiliser une liste chaînée de tenir nos éléments et de construire la pile autour de cela.

58
00:04:10,070 --> 00:04:12,420
Passons en revue quelques exemples, en regardant un peu de code,

59
00:04:12,420 --> 00:04:14,960
pour voir ce qui se passe réellement ici.

60
00:04:14,960 --> 00:04:23,400
Sur la gauche, j'ai jeté ce que struct pile pourrait ressembler dans la mémoire

61
00:04:23,400 --> 00:04:28,330
si la capacité a été défini # au nombre de quatre.

62
00:04:28,330 --> 00:04:33,490
Nous avons nos quatre-élément de tableau char *.

63
00:04:33,490 --> 00:04:38,110
Nous avons cordes [0], strings [1], les chaînes [2], strings [3],

64
00:04:38,110 --> 00:04:43,800
et puis ce dernier espace entier de notre taille.

65
00:04:43,800 --> 00:04:46,270
Est-ce logique? D'accord.

66
00:04:46,270 --> 00:04:48,790
C'est ce qui arrive si ce que je fais sur la droite,

67
00:04:48,790 --> 00:04:55,790
qui sera mon code, est de simplement déclarer une structure, une structure empilée appelé s.

68
00:04:55,790 --> 00:05:01,270
C'est ce que nous obtenons. Il établit cette empreinte dans la mémoire.

69
00:05:01,270 --> 00:05:05,590
La première question ici est quel est le contenu de cette struct pile?

70
00:05:05,590 --> 00:05:09,250
En ce moment ils ne sont rien, mais ils ne sont pas tout à fait rien.

71
00:05:09,250 --> 00:05:13,300
Ils sont ce genre de déchets. Nous n'avons aucune idée de ce qu'il ya dedans.

72
00:05:13,300 --> 00:05:17,000
Lorsque nous déclarons s de la pile, nous ne faisons que jeter que sur le dessus de la mémoire.

73
00:05:17,000 --> 00:05:19,840
C'est un peu comme déclarer int i et pas l'initialiser.

74
00:05:19,840 --> 00:05:21,730
Vous ne savez pas ce qu'il ya dedans. Vous pouvez lire ce qu'il ya dedans,

75
00:05:21,730 --> 00:05:27,690
mais il ne serait pas super utile.

76
00:05:27,690 --> 00:05:32,680
Une chose que vous voulez toujours vous rappeler de le faire est d'initialiser tout ce qui doit être initialisé.

77
00:05:32,680 --> 00:05:35,820
Dans ce cas, nous allons initialiser la taille à zéro,

78
00:05:35,820 --> 00:05:39,960
parce que cela va se révéler très important pour nous.

79
00:05:39,960 --> 00:05:43,450
Nous pourrions aller de l'avant et d'initialiser tous les pointeurs, tous les s char *,

80
00:05:43,450 --> 00:05:49,670
avoir une certaine valeur compréhensible, probablement nulle.

81
00:05:49,670 --> 00:05:58,270
Mais ce n'est pas absolument nécessaire que nous le fassions.

82
00:05:58,270 --> 00:06:04,200
>> Maintenant, les deux principales opérations sur les piles sont?

83
00:06:04,200 --> 00:06:07,610
Quelqu'un se souvient de ce que vous faites conférence avec des piles? Oui?

84
00:06:07,610 --> 00:06:09,700
[Stella] poussage et de sauter? >> Exactement.

85
00:06:09,700 --> 00:06:13,810
Pousser et popping sont les deux principales opérations sur les piles.

86
00:06:13,810 --> 00:06:17,060
Et qu'est-ce poussoir faire? Il met quelque chose >> sur le dessus

87
00:06:17,060 --> 00:06:19,300
de la pile, et ensuite il enlève éclatement.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Exactement. Si poussée pousse quelque chose sur le dessus de la pile.

89
00:06:23,150 --> 00:06:27,700
C'est comme mettre du personnel à manger un plateau repas sur le comptoir.

90
00:06:27,700 --> 00:06:33,630
Et éclatée prend un plateau repas hors de la pile.

91
00:06:33,630 --> 00:06:36,460
Passons en revue quelques exemples de ce qui se passe

92
00:06:36,460 --> 00:06:39,720
lorsque l'on pousse les choses dans la pile.

93
00:06:39,720 --> 00:06:45,110
Si nous devions pousser la chaîne 'Bonjour' sur notre pile,

94
00:06:45,110 --> 00:06:49,760
c'est ce que notre diagramme sera semblable à aujourd'hui.

95
00:06:49,760 --> 00:06:53,410
Voir ce qui se passe?

96
00:06:53,410 --> 00:06:56,530
Nous avons poussé dans le premier élément de notre tableau de chaînes

97
00:06:56,530 --> 00:07:01,420
et nous avons augmenté notre nombre de la taille à 1.

98
00:07:01,420 --> 00:07:05,340
Donc, si on regarde la différence entre les deux lames, ici était de 0, voici avant la poussée.

99
00:07:05,340 --> 00:07:08,690
Voici après la poussée.

100
00:07:08,690 --> 00:07:13,460
Avant la poussée, après la poussée.

101
00:07:13,460 --> 00:07:16,860
Et maintenant nous avons un élément dans notre pile.

102
00:07:16,860 --> 00:07:20,970
C'est la chaîne "bonjour", et c'est tout.

103
00:07:20,970 --> 00:07:24,440
Tout le reste du tableau, dans notre tableau de chaînes, est encore ordures.

104
00:07:24,440 --> 00:07:27,070
Nous n'avons pas initialisé.

105
00:07:27,070 --> 00:07:29,410
Disons que l'on pousse une autre chaîne sur notre pile.

106
00:07:29,410 --> 00:07:32,210
Nous allons pousser "monde" sur cette période.

107
00:07:32,210 --> 00:07:35,160
Ainsi, vous pouvez voir "monde" va ici au-dessus de «bonjour»,

108
00:07:35,160 --> 00:07:40,040
et le nombre de la taille va jusqu'à 2.

109
00:07:40,040 --> 00:07:44,520
Maintenant, nous pouvons pousser "CS50", et que vous allez sur le dessus à nouveau.

110
00:07:44,520 --> 00:07:51,110
Si nous revenons, vous pouvez voir comment nous poussons les choses sur le dessus de la pile.

111
00:07:51,110 --> 00:07:53,320
Et maintenant, nous arrivons à la pop.

112
00:07:53,320 --> 00:07:58,910
Lorsque nous sommes passés quelque chose hors de la pile, ce qui s'est passé?

113
00:07:58,910 --> 00:08:01,540
Quelqu'un a vu la différence? Il est assez subtile.

114
00:08:01,540 --> 00:08:05,810
[Étudiants] La taille. >> Oui, la taille a changé.

115
00:08:05,810 --> 00:08:09,040
>> Que voulez-vous pu s'attendre à changer?

116
00:08:09,040 --> 00:08:14,280
[] Les étudiants cordes, aussi. Droit >>. Les cordes aussi.

117
00:08:14,280 --> 00:08:17,110
Il s'avère que lorsque vous faites de cette façon,

118
00:08:17,110 --> 00:08:21,960
parce que nous ne sommes pas copier les éléments dans notre pile,

119
00:08:21,960 --> 00:08:24,670
nous avons en fait ne pas avoir à faire quoi que ce soit, nous pouvons simplement utiliser la taille

120
00:08:24,670 --> 00:08:28,630
de garder une trace du nombre de choses dans notre tableau

121
00:08:28,630 --> 00:08:33,780
de sorte que lorsque nous retirons encore, encore que nous venons de diminuer notre taille en-dessous de 1.

122
00:08:33,780 --> 00:08:39,440
Il n'est pas nécessaire d'aller effectivement dans et écrasera tout.

123
00:08:39,440 --> 00:08:41,710
Sorte de funky.

124
00:08:41,710 --> 00:08:46,520
Il s'avère que nous avons généralement juste laisser faire parce que c'est moins de travail à faire pour nous.

125
00:08:46,520 --> 00:08:50,060
Si nous n'avons pas à revenir en arrière et remplacer quelque chose, alors pourquoi le faire?

126
00:08:50,060 --> 00:08:54,150
Ainsi, lorsque nous apparaître deux fois hors de la pile, qui ne fait que diminuer la taille d'une couple de fois.

127
00:08:54,150 --> 00:08:59,120
Et encore, c'est seulement parce que nous ne sommes pas copier des choses dans notre pile.

128
00:08:59,120 --> 00:09:01,320
Oui? Allez-y.

129
00:09:01,320 --> 00:09:04,460
[Étudiant, inintelligible] >> Et alors qu'est-ce qui se passe lorsque vous appuyez de nouveau quelque chose?

130
00:09:04,460 --> 00:09:08,570
Lorsque vous appuyez de nouveau quelque chose, où faut-il aller?

131
00:09:08,570 --> 00:09:12,390
Où faut-il aller, Basil? Dans cordes >> [1]? Droit >>.

132
00:09:12,390 --> 00:09:14,530
Pourquoi ne pas aller dans les chaînes [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Parce qu'il a oublié qu'il y avait quoi que ce soit dans les chaînes [1] et [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Exactement. Notre pile, pour l'essentiel, a "oublié" qu'elle tenait à rien

135
00:09:24,040 --> 00:09:29,480
dans les chaînes [1] ou chaînes [2], alors quand nous pousser "woot",

136
00:09:29,480 --> 00:09:36,670
il met juste que dans l'élément à cordes [1].

137
00:09:36,670 --> 00:09:41,590
Y at-il des questions sur la façon dont cela fonctionne, à un niveau de base?

138
00:09:41,590 --> 00:09:45,160
[Sam] Ce n'est donc pas en aucune façon dynamique, en termes de quantité

139
00:09:45,160 --> 00:09:47,620
ou en fonction de la taille de la pile?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Exactement. C'est - le fait est que ce n'était pas une pile dynamiquement growning.

141
00:09:56,750 --> 00:10:02,850
Il s'agit d'une pile qui peut contenir, au plus, quatre char * s, au plus quatre choses.

142
00:10:02,850 --> 00:10:07,580
Si nous devions essayer de pousser un cinquième chose, que pensez-vous devrait se passer?

143
00:10:07,580 --> 00:10:11,870
[Etudiants, inintelligibles]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Exactement. Il ya un certain nombre de choses qui pourraient arriver.

145
00:10:14,600 --> 00:10:19,330
Il pourrait éventuellement seg défaut, en fonction de ce que nous avons -

146
00:10:19,330 --> 00:10:22,530
comment exactement nous mettions en œuvre le back-end.

147
00:10:22,530 --> 00:10:31,740
Il pourrait écraser. Il pourrait avoir ce type buffer overflow dont nous avons parlé en classe.

148
00:10:31,740 --> 00:10:35,240
Quelle serait la chose la plus évidente qui pourrait être écrasé

149
00:10:35,240 --> 00:10:42,370
si nous avons essayé de pousser une chose supplémentaire sur notre pile?

150
00:10:42,370 --> 00:10:44,550
Donc, vous avez mentionné un buffer overflow.

151
00:10:44,550 --> 00:10:47,870
Quelle pourrait être la chose qui serait-il écrasé ou piétiné

152
00:10:47,870 --> 00:10:52,320
si nous débordé accidentellement en essayant de pousser une chose en plus?

153
00:10:52,320 --> 00:10:54,730
[Daniel, inintelligible] possible >>.

154
00:10:54,730 --> 00:10:58,440
Mais d'abord, qu'est-ce qui pourrait arriver? Que faire si nous avons essayé de pousser un quatrième chose?

155
00:10:58,440 --> 00:11:06,220
Il peut écraser la taille, du moins en ce diagramme mémoire que nous avons.

156
00:11:06,220 --> 00:11:10,880
>> Dans la spécification du jeu de problème, c'est ce que nous allons mettre en œuvre aujourd'hui,

157
00:11:10,880 --> 00:11:16,030
ce que nous voulons faire est de simplement renvoyer false.

158
00:11:16,030 --> 00:11:20,030
Notre méthode push va retourner une valeur booléenne,

159
00:11:20,030 --> 00:11:22,920
et que la valeur booléenne sera vrai si la poussée réussit

160
00:11:22,920 --> 00:11:29,730
et faux si l'on ne peut pas pousser plus rien parce que la pile est pleine.

161
00:11:29,730 --> 00:11:33,620
Parcourons un peu de ce code en ce moment.

162
00:11:33,620 --> 00:11:36,400
Voici notre fonction Push.

163
00:11:36,400 --> 00:11:40,380
Notre fonction Push pour une pile va prendre dans la chaîne à mettre sur la pile.

164
00:11:40,380 --> 00:11:45,820
Il va retourner true si la chaîne a réussi à pousser

165
00:11:45,820 --> 00:11:51,820
sur l'autre pile et faux.

166
00:11:51,820 --> 00:11:59,740
Toutes les suggestions sur ce qui pourrait être une bonne chose premier à faire ici?

167
00:11:59,740 --> 00:12:20,630
[Sam] Si la taille est égale à la capacité alors retourner faux?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Nice job.

169
00:12:23,320 --> 00:12:26,310
Si la taille est la capacité, nous allons retourner false.

170
00:12:26,310 --> 00:12:29,270
Nous ne pouvons pas mettre quelque chose de plus dans notre pile.

171
00:12:29,270 --> 00:12:36,900
Dans le cas contraire, nous voulons mettre quelque chose sur le dessus de la pile.

172
00:12:36,900 --> 00:12:41,670
Qu'est-ce que «le sommet de la pile», d'abord?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Taille 0? >> Taille 0.

174
00:12:43,650 --> 00:12:49,990
Quel est le sommet de la pile après il ya une chose dans la pile? Missy, savez-vous?

175
00:12:49,990 --> 00:12:52,720
[Missy] One. Des tailles >> en est un, exactement. Vous continuez à ajouter à la taille,

176
00:12:52,720 --> 00:13:01,690
et chaque fois que vous mettez dans le nouvel élément à la taille de l'index dans le tableau.

177
00:13:01,690 --> 00:13:05,470
Nous pouvons le faire avec ce genre de one-liner, si cela fait sens.

178
00:13:05,470 --> 00:13:11,910
Donc, nous avons notre tableau de chaînes, nous allons y accéder à l'index taille,

179
00:13:11,910 --> 00:13:14,780
et nous allons juste pour stocker notre char * là-dedans.

180
00:13:14,780 --> 00:13:19,340
Remarquez comment il ya pas de copie de chaîne qui se passe ici,

181
00:13:19,340 --> 00:13:29,680
pas d'allocation dynamique de la mémoire?

182
00:13:29,680 --> 00:13:34,440
Et puis Missy élevé ce que nous devons faire maintenant,

183
00:13:34,440 --> 00:13:40,570
parce que nous avons stocké la chaîne à l'endroit approprié dans le tableau,

184
00:13:40,570 --> 00:13:49,230
et elle a dit que nous devions augmenter la taille par une afin que nous sommes prêts pour la prochaine poussée.

185
00:13:49,230 --> 00:13:53,950
Ainsi, nous pouvons le faire avec s.size + +.

186
00:13:53,950 --> 00:13:59,330
À ce stade, nous avons poussé dans notre tableau. Quelle est la dernière chose que nous devons faire?

187
00:13:59,330 --> 00:14:10,110
[Étudiants] Retourne true. >> Retour vrai.

188
00:14:10,110 --> 00:14:14,690
Donc, c'est assez simple, un code assez simple. Pas trop.

189
00:14:14,690 --> 00:14:17,070
Une fois que vous avez enveloppé autour de votre tête la façon dont la pile fonctionne,

190
00:14:17,070 --> 00:14:21,910
c'est assez simple à mettre en œuvre.

191
00:14:21,910 --> 00:14:26,390
>> Maintenant, la prochaine partie de cet éclatement est une chaîne hors de la pile.

192
00:14:26,390 --> 00:14:29,410
Je vais vous donner les gars un peu de temps pour travailler sur ce morceau un peu.

193
00:14:29,410 --> 00:14:34,320
C'est presque essentiellement l'inverse de ce que nous avons fait ici en push.

194
00:14:34,320 --> 00:14:38,510
Qu'est-ce que j'ai fait est fait - oups.

195
00:14:38,510 --> 00:14:48,160
J'ai démarré un appareil ici, et dans l'appareil,

196
00:14:48,160 --> 00:14:53,600
J'ai remonté le problème set 5 spécification.

197
00:14:53,600 --> 00:15:02,560
Si l'on zoom avant ici, nous pouvons voir que je suis à cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Avez-vous les gars téléchargé ce code qui est situé ici, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Très bien. Si vous n'avez pas fait cela, le faire dès maintenant, très rapidement.

200
00:15:15,030 --> 00:15:22,130
Je le ferai dans ma fenêtre de terminal.

201
00:15:22,130 --> 00:15:25,090
En fait, je l'ai fait ici. Ouais.

202
00:15:25,090 --> 00:15:34,730
Oui, Sam? >> J'ai une question à propos de pourquoi tu as dit entre parenthèses s.string 's de taille = str?

203
00:15:34,730 --> 00:15:42,910
Qu'est-ce que str? Est celle qui est définie quelque part, ou - oh, dans le char * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Oui, exactement. C'est l'argument. >> Oh, d'accord. Désolé.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Nous sommes en spécifiant la chaîne de pousser po

206
00:15:49,470 --> 00:15:55,220
L'autre question qui pourrait arriver que nous n'avons pas vraiment parler ici était

207
00:15:55,220 --> 00:15:58,810
nous avons pris pour acquis que nous avons eu cette variable appelée s

208
00:15:58,810 --> 00:16:02,710
qui était dans la portée et accessible pour nous.

209
00:16:02,710 --> 00:16:06,960
Nous avons pris pour acquis que s était cette structure de pile.

210
00:16:06,960 --> 00:16:08,930
Donc, en regardant en arrière à ce code poussée,

211
00:16:08,930 --> 00:16:13,450
vous pouvez voir que nous faisons des choses avec cette chaîne qui s'est passé dans

212
00:16:13,450 --> 00:16:19,210
mais tout d'un coup, nous accédons à s.size, comme, où avez-s vient-il?

213
00:16:19,210 --> 00:16:23,020
Dans le code que nous allons examiner dans la section archives

214
00:16:23,020 --> 00:16:27,100
et puis le truc que vous allez faire dans votre problème fixe,

215
00:16:27,100 --> 00:16:32,440
nous avons fait notre pile struct une variable globale

216
00:16:32,440 --> 00:16:36,380
afin que nous puissions avoir accès à toutes nos fonctions différentes

217
00:16:36,380 --> 00:16:40,630
sans avoir à entrer manuellement le faire circuler et de le passer par référence,

218
00:16:40,630 --> 00:16:44,870
faire tout ce genre de trucs à elle.

219
00:16:44,870 --> 00:16:52,280
Nous sommes juste triche un peu, si vous voulez, pour rendre les choses plus agréables.

220
00:16:52,280 --> 00:16:57,430
Et c'est quelque chose que nous faisons ici, car c'est pour le plaisir, c'est plus facile.

221
00:16:57,430 --> 00:17:02,800
Souvent, vous verrez des gens le faire si ils ont une grande structure de données

222
00:17:02,800 --> 00:17:07,750
qui a été opéré au sein de leur programme.

223
00:17:07,750 --> 00:17:09,560
>> Revenons sur l'appareil.

224
00:17:09,560 --> 00:17:15,240
Tout le monde a réussi à obtenir le section6.zip?

225
00:17:15,240 --> 00:17:20,440
Tout le monde le décompresser à l'aide section6.zip décompresser?

226
00:17:20,440 --> 00:17:27,200
Si vous allez dans le répertoire de l'article 6 -

227
00:17:27,200 --> 00:17:29,220
aah, dans tous les sens -

228
00:17:29,220 --> 00:17:32,840
et vous énumérer ce qui est ici, vous voyez que vous avez trois fichiers différents. c.

229
00:17:32,840 --> 00:17:38,350
Vous avez une file d'attente, un sll, qui est simplement chaînée liste, et une pile.

230
00:17:38,350 --> 00:17:44,600
Si vous ouvrez pile.c,

231
00:17:44,600 --> 00:17:47,330
vous pouvez voir que nous avons cette structure définie pour nous,

232
00:17:47,330 --> 00:17:51,330
la structure exacte que nous en avons parlé dans les diapositives.

233
00:17:51,330 --> 00:17:56,340
Nous avons notre variable globale pour la pile,

234
00:17:56,340 --> 00:18:00,110
nous avons notre fonction Push,

235
00:18:00,110 --> 00:18:04,230
et puis nous avons eu notre fonction de pop.

236
00:18:04,230 --> 00:18:08,320
Je vais mettre le code pour repousser sur la diapositive ici,

237
00:18:08,320 --> 00:18:10,660
mais ce que je voudrais vous les gars à faire est, au mieux de vos capacités,

238
00:18:10,660 --> 00:18:13,790
aller et mettre en œuvre la fonction de pop.

239
00:18:13,790 --> 00:18:18,480
Une fois que vous avez mis en place, vous pouvez compiler avec make cette pile,

240
00:18:18,480 --> 00:18:22,540
puis exécutez le fichier exécutable pile résultante,

241
00:18:22,540 --> 00:18:28,390
et qui se déroulera tout ce code de test ici-bas qui est en principale.

242
00:18:28,390 --> 00:18:31,060
Et principal prend soin de faire réellement le push et pop appels

243
00:18:31,060 --> 00:18:33,220
et faire en sorte que tout se passe à travers tous les droits.

244
00:18:33,220 --> 00:18:36,820
Il initialise également la taille de la pile ici

245
00:18:36,820 --> 00:18:39,780
de sorte que vous n'avez pas à vous soucier de ce que l'initialisation.

246
00:18:39,780 --> 00:18:42,310
On peut supposer qu'il a été correctement initialisé

247
00:18:42,310 --> 00:18:48,000
par le temps que vous y accédez à la fonction de pop.

248
00:18:48,000 --> 00:18:53,530
Est-ce logique?

249
00:18:53,530 --> 00:19:00,100
Alors on y va. Il s'agit du code poussoir.

250
00:19:00,100 --> 00:19:13,210
Je vais vous donner les gars 5 ou 10 minutes.

251
00:19:13,210 --> 00:19:15,690
Et si vous avez des questions dans l'intervalle pendant que vous êtes de codage,

252
00:19:15,690 --> 00:19:17,710
s'il vous plaît demandez-leur à haute voix.

253
00:19:17,710 --> 00:19:23,080
Donc, si vous arrivez à un point d'achoppement, il suffit de demander.

254
00:19:23,080 --> 00:19:26,030
Faites-moi savoir, je sais tout le monde.

255
00:19:26,030 --> 00:19:28,160
Travaillez avec votre voisin aussi.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Nous ne faisons que mettre en œuvre pop en ce moment? >> Just pop.

257
00:19:30,360 --> 00:19:34,200
Bien que vous pouvez copier la mise en œuvre de la poussée, si vous souhaitez

258
00:19:34,200 --> 00:19:37,780
de sorte que le test fonctionne.

259
00:19:37,780 --> 00:19:41,940
Parce qu'il est difficile de tester des choses en obtenant -

260
00:19:41,940 --> 00:19:49,030
ou, il est difficile de tester des choses sautant hors d'une pile si il n'y a rien dans la pile pour commencer.

261
00:19:49,030 --> 00:19:55,250
>> Quelle est pop censé être de retour? L'élément à partir du haut de la pile.

262
00:19:55,250 --> 00:20:01,260
Il est censé récupérer l'élément hors du dessus de la pile

263
00:20:01,260 --> 00:20:05,780
puis diminuer la taille de la pile,

264
00:20:05,780 --> 00:20:07,810
et maintenant vous avez perdu l'élément sur le dessus.

265
00:20:07,810 --> 00:20:11,420
Et puis vous retournez l'élément sur le dessus.

266
00:20:11,420 --> 00:20:20,080
[Étudiant, inintelligible]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Donc ce qui arrive si vous faites cela? [Étudiant, inintelligible]

268
00:20:28,810 --> 00:20:34,000
Ce qui finit par se produire, c'est que vous êtes probablement l'accès soit

269
00:20:34,000 --> 00:20:37,350
un élément qui n'a pas encore été initialisé, de sorte que votre calcul

270
00:20:37,350 --> 00:20:39,990
où le dernier élément est éteint.

271
00:20:39,990 --> 00:20:46,260
Donc ici, si vous remarquez, en push, nous accédons à cordes à l'élément s.size

272
00:20:46,260 --> 00:20:48,560
parce que c'est un nouvel indice.

273
00:20:48,560 --> 00:20:51,460
C'est le nouveau haut de la pile.

274
00:20:51,460 --> 00:21:01,100
Alors que dans la pop, s.size va être le prochain espace,

275
00:21:01,100 --> 00:21:05,210
l'espace qui est au-dessus de tous les éléments de votre pile.

276
00:21:05,210 --> 00:21:10,050
Ainsi, l'élément supérieur plus n'est pas s.size,

277
00:21:10,050 --> 00:21:14,930
mais plutôt, c'est en dessous.

278
00:21:14,930 --> 00:21:19,640
>> L'autre chose à faire quand vous - dans la pop,

279
00:21:19,640 --> 00:21:22,030
est que vous ne devez diminuer la taille.

280
00:21:22,030 --> 00:21:28,750
Si vous vous souvenez de notre petit diagramme ici,

281
00:21:28,750 --> 00:21:30,980
vraiment, la seule chose que nous avons vu se passe quand nous avons appelé pop

282
00:21:30,980 --> 00:21:36,150
est que cette taille baissé, premier à 2, puis à 1.

283
00:21:36,150 --> 00:21:42,620
Puis, quand nous avons poussé un nouvel élément sur, il irait à l'endroit approprié.

284
00:21:42,620 --> 00:21:49,610
[Basil] Si le s.size est 2, alors il ne serait pas aller à l'élément 2,

285
00:21:49,610 --> 00:21:54,400
puis que vous voudriez faire apparaître cet élément off?

286
00:21:54,400 --> 00:21:59,510
Donc, si nous sommes allés à - >> Donc, regardons encore une fois.

287
00:21:59,510 --> 00:22:07,730
Si telle est notre pile à ce moment-

288
00:22:07,730 --> 00:22:12,130
et nous appelons pop,

289
00:22:12,130 --> 00:22:16,150
au cours de laquelle l'indice est l'élément le plus?

290
00:22:16,150 --> 00:22:19,300
[Basil] A 2, mais il va pop 3. Droit >>.

291
00:22:19,300 --> 00:22:24,220
C'est donc là que notre taille est de 3, mais nous voulons faire apparaître l'élément à l'index 2.

292
00:22:24,220 --> 00:22:29,900
C'est ce genre typique de large par celui que vous avez avec le zéro-indexation des tableaux.

293
00:22:29,900 --> 00:22:36,430
Donc, vous voulez faire apparaître le troisième élément, mais le troisième élément n'est pas à l'index 3.

294
00:22:36,430 --> 00:22:39,430
Et la raison pour laquelle nous n'avons pas à le faire 1 moins quand nous poussons

295
00:22:39,430 --> 00:22:44,120
est parce qu'en ce moment, vous remarquez que l'élément de plus haut niveau,

296
00:22:44,120 --> 00:22:47,600
si nous devions pousser quelque chose d'autre sur la pile à ce moment-là,

297
00:22:47,600 --> 00:22:50,360
nous voulons pousser à l'index 3.

298
00:22:50,360 --> 00:23:03,550
Et il se trouve que la taille et les indices de s'aligner quand vous poussez.

299
00:23:03,550 --> 00:23:06,960
>> Qui a une implémentation de la pile de travail?

300
00:23:06,960 --> 00:23:09,690
Vous avez une pile de travail un. Avez-vous pop fonctionne pas encore?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Oui. Je crois.

302
00:23:11,890 --> 00:23:14,610
Programme en cours d'exécution >> et non seg failles, c'est l'impression de sortir?

303
00:23:14,610 --> 00:23:17,520
Est-ce que l'imprimer "succès" lorsque vous l'exécutez?

304
00:23:17,520 --> 00:23:22,630
Ouais. Assurez-pile, l'exécuter, si elle imprime sur le «succès» et ne fait boum,

305
00:23:22,630 --> 00:23:26,000
alors tout est bon.

306
00:23:26,000 --> 00:23:34,070
Très bien. Passons en revue à l'appareil très rapidement,

307
00:23:34,070 --> 00:23:46,100
et nous marcherons à travers cela.

308
00:23:46,100 --> 00:23:51,110
Si nous regardons ce qui se passe ici avec la pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, ce qui était la première chose que vous avez fait?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Si s.size est supérieur à 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] D'accord. Et pourquoi as-tu fait cela?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Pour s'assurer qu'il y avait quelque chose à l'intérieur de la pile.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Droit. Vous voulez tester pour s'assurer que s.size est supérieur à 0;

314
00:24:10,950 --> 00:24:13,280
autrement, que voulez-vous qu'il se passe?

315
00:24:13,280 --> 00:24:16,630
[Daniel] null retour? Null Retour >>, exactement.

316
00:24:16,630 --> 00:24:20,740
Donc, si s.size est supérieur à 0. Alors qu'allons-nous faire?

317
00:24:20,740 --> 00:24:25,890
Que faisons-nous si la pile n'est pas vide?

318
00:24:25,890 --> 00:24:31,210
[Stella] Vous décrémenter la taille? Vous >> diminuer la taille, d'accord.

319
00:24:31,210 --> 00:24:34,440
Alors, comment avez-vous fait? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Grande. Et puis qu'est-ce que tu fais?

321
00:24:37,030 --> 00:24:44,140
[Stella] Et puis je l'ai dit retour s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Grande.

323
00:24:48,560 --> 00:24:51,940
Sinon, vous retourner null. Oui, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Pourquoi faut-il pas besoin d'être s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? Ouais >>. >> Compris.

326
00:24:58,430 --> 00:25:00,980
[Sam] Je pensais que parce que vous prenez 1 sortie,

327
00:25:00,980 --> 00:25:04,290
alors vous allez être de retour n'est pas celui qu'ils ont demandé.

328
00:25:04,290 --> 00:25:09,400
[Hardison] Et c'était exactement ce dont nous parlions avec toute cette question des indices de 0.

329
00:25:09,400 --> 00:25:11,380
Donc, si nous faire un zoom avant ici.

330
00:25:11,380 --> 00:25:15,650
Si l'on regarde ce gars ici, vous pouvez voir que lorsque nous pop,

331
00:25:15,650 --> 00:25:19,340
nous éclater l'élément à l'index 2.

332
00:25:19,340 --> 00:25:25,200
>> Donc, nous diminuons notre première taille, notre taille correspond à notre index.

333
00:25:25,200 --> 00:25:39,650
Si nous ne diminue pas la taille d'abord, puis nous avons à faire taille -1 puis décrémentation.

334
00:25:39,650 --> 00:25:45,270
Grande. Tout va bien?

335
00:25:45,270 --> 00:25:47,530
Vous avez des questions à ce sujet?

336
00:25:47,530 --> 00:25:54,050
Il ya un certain nombre de façons différentes d'écrire aussi.

337
00:25:54,050 --> 00:26:03,290
En fait, nous pouvons faire quelque chose d'encore - que nous pouvons faire un one-liner.

338
00:26:03,290 --> 00:26:05,770
Nous pouvons faire un retour sur une ligne.

339
00:26:05,770 --> 00:26:12,980
Nous pouvons donc diminuer avant de retourner en faisant cela.

340
00:26:12,980 --> 00:26:18,320
Donc, mettre le - avant le s.size.

341
00:26:18,320 --> 00:26:22,060
C'est pourquoi cette gamme très dense.

342
00:26:22,060 --> 00:26:30,940
Lorsque la différence entre la -. Taille et la s.size--

343
00:26:30,940 --> 00:26:40,130
est que cette postfix - ils l'appellent postfix parce que le - vient après le s.size--

344
00:26:40,130 --> 00:26:47,430
signifie que s.size est évaluée aux fins de la constatation de l'indice

345
00:26:47,430 --> 00:26:50,410
tel qu'il est actuellement lorsque cette ligne est exécutée,

346
00:26:50,410 --> 00:26:54,290
et puis ce - qui se produit après la ligne est exécuté.

347
00:26:54,290 --> 00:27:00,340
Après l'élément à s.size indice est accessible.

348
00:27:00,340 --> 00:27:07,260
Et ce n'est pas ce que nous voulons, parce que nous voulons le décrément arriver premier.

349
00:27:07,260 --> 00:27:10,990
Othewise, nous allons accéder au tableau, de manière efficace, en dehors des limites.

350
00:27:10,990 --> 00:27:16,850
Nous allons accéder à l'élément ci-dessus celui que nous voulons effectivement accès.

351
00:27:16,850 --> 00:27:23,840
Ouais, Sam? Est-il plus rapide >> ou utiliser moins de mémoire vive pour faire une ligne ou pas?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Honnêtement, cela dépend vraiment.

353
00:27:29,620 --> 00:27:34,220
[Sam, inintelligible] >> Ouais, ça dépend. Vous pouvez faire des tours de compilation

354
00:27:34,220 --> 00:27:41,580
pour obtenir le compilateur de reconnaître que, généralement, j'imagine.

355
00:27:41,580 --> 00:27:44,840
>> Alors nous l'avons mentionné un peu plus sur ce genre de choses optimisation du compilateur

356
00:27:44,840 --> 00:27:47,400
que vous pouvez faire à la compilation,

357
00:27:47,400 --> 00:27:50,580
et c'est le genre de chose qu'un compilateur pourrait être en mesure de comprendre,

358
00:27:50,580 --> 00:27:54,710
comme oh, hé, peut-être que je peux faire tout cela en une seule opération,

359
00:27:54,710 --> 00:27:59,420
au lieu de chargement dans la variable de taille de la mémoire vive,

360
00:27:59,420 --> 00:28:03,770
le décrémenter, le stocker revenir en arrière, puis de le charger de retour à nouveau

361
00:28:03,770 --> 00:28:08,000
à traiter le reste de cette opération.

362
00:28:08,000 --> 00:28:10,710
Mais en général, non, ce n'est pas le genre de chose

363
00:28:10,710 --> 00:28:20,770
qui va rendre votre programme beaucoup plus rapide.

364
00:28:20,770 --> 00:28:26,000
D'autres questions sur les piles?

365
00:28:26,000 --> 00:28:31,360
>> Donc, en poussant et popping. Si vous voulez les gars d'essayer l'édition pirate,

366
00:28:31,360 --> 00:28:33,660
ce que nous avons fait dans l'édition pirate est en fait augmenté

367
00:28:33,660 --> 00:28:37,670
et fait de cette pile croissance dynamique.

368
00:28:37,670 --> 00:28:43,190
Le défi consiste surtout ici dans la fonction Push,

369
00:28:43,190 --> 00:28:48,820
de comprendre comment faire grandir ce tableau

370
00:28:48,820 --> 00:28:52,450
que vous continuer à pousser les éléments de plus en plus sur la pile.

371
00:28:52,450 --> 00:28:56,000
Il s'agit en fait pas trop de code supplémentaire.

372
00:28:56,000 --> 00:29:00,080
Juste un appel à - vous avez à retenir pour obtenir les appels à malloc là correctement,

373
00:29:00,080 --> 00:29:03,310
et puis savoir quand vous allez appeler realloc.

374
00:29:03,310 --> 00:29:06,090
C'est un défi amusant si vous êtes intéressés.

375
00:29:06,090 --> 00:29:11,550
>> Mais pour le moment, nous allons passer à autre chose, et nous allons parler de files d'attente.

376
00:29:11,550 --> 00:29:15,680
Faites défiler ici.

377
00:29:15,680 --> 00:29:19,340
La file d'attente est un frère près de la pile.

378
00:29:19,340 --> 00:29:25,380
Ainsi, dans la pile, les choses qui ont été mis en dernière

379
00:29:25,380 --> 00:29:28,810
sont les premières choses à être récupérées.

380
00:29:28,810 --> 00:29:33,600
Nous avons ce dernier entré, premier sorti, ou LIFO, de la commande.

381
00:29:33,600 --> 00:29:38,390
Alors que dans la file d'attente, comme vous le souhaitiez partir du moment où vous êtes debout en ligne,

382
00:29:38,390 --> 00:29:41,980
la première personne à faire la queue, la première chose à faire dans la file d'attente,

383
00:29:41,980 --> 00:29:47,630
est la première chose qui se extraites de la file d'attente.

384
00:29:47,630 --> 00:29:51,490
Les files d'attente sont également souvent utilisés lorsque nous traitons avec des graphiques,

385
00:29:51,490 --> 00:29:55,560
comme nous en avons parlé brièvement avec des piles,

386
00:29:55,560 --> 00:30:00,260
et les files d'attente sont également à portée de main pour un tas d'autres choses.

387
00:30:00,260 --> 00:30:06,180
Une chose qui revient souvent est d'essayer de maintenir, par exemple,

388
00:30:06,180 --> 00:30:12,310
une liste triée des éléments.

389
00:30:12,310 --> 00:30:17,650
Et vous pouvez le faire avec un tableau. Vous pouvez gérer une liste triée des choses dans un tableau,

390
00:30:17,650 --> 00:30:20,650
mais lorsque cela devient délicat est alors, vous avez toujours de trouver

391
00:30:20,650 --> 00:30:26,160
l'endroit approprié pour insérer la chose suivante.

392
00:30:26,160 --> 00:30:28,250
Donc si vous avez un tableau de nombres, de 1 à 10,

393
00:30:28,250 --> 00:30:31,630
et puis vous voulez étendre cela à tous les chiffres de 1 à 100,

394
00:30:31,630 --> 00:30:33,670
et vous obtenez ces numéros dans un ordre aléatoire et en essayant de garder tout

395
00:30:33,670 --> 00:30:40,650
triées comme vous le passer, vous finissez par avoir à faire beaucoup de changement.

396
00:30:40,650 --> 00:30:43,910
Avec certains types de files d'attente et certains types de structures de données sous-jacentes,

397
00:30:43,910 --> 00:30:46,670
vous pouvez effectivement garder assez simple.

398
00:30:46,670 --> 00:30:50,640
Vous n'avez pas besoin d'ajouter quelque chose, puis remélanger le tout à chaque fois.

399
00:30:50,640 --> 00:30:56,770
Pas plus que vous avez à faire beaucoup de déplacement des éléments internes autour.

400
00:30:56,770 --> 00:31:02,990
Lorsque nous regardons une file d'attente, vous voyez que - même dans queue.c dans le code de section -

401
00:31:02,990 --> 00:31:10,950
la structure que nous vous avons donnée est vraiment similaire à la structure que nous vous avons toute une pile.

402
00:31:10,950 --> 00:31:13,770
>> Il ya une exception à cette règle, et que seule exception

403
00:31:13,770 --> 00:31:21,700
est que nous avons cet entier supplémentaire appelé la tête,

404
00:31:21,700 --> 00:31:28,120
et la tête ici, c'est pour garder la trace de la tête de la file d'attente,

405
00:31:28,120 --> 00:31:32,160
ou le premier élément dans la file d'attente.

406
00:31:32,160 --> 00:31:37,470
Avec une pile, nous avons réussi à garder la trace de l'élément que nous étions sur le point de récupérer,

407
00:31:37,470 --> 00:31:40,800
ou le haut de la pile, en utilisant simplement la taille,

408
00:31:40,800 --> 00:31:44,220
tandis que dans une file d'attente, nous allons avoir à faire face à des extrémités opposées.

409
00:31:44,220 --> 00:31:49,000
Nous essayons de virer de bord sur les choses à la fin, mais de remettre les choses à partir de l'avant.

410
00:31:49,000 --> 00:31:54,640
Donc, en réalité, avec la tête, nous avons l'indice du début de la file d'attente,

411
00:31:54,640 --> 00:31:58,920
et la taille nous donne l'indice de la fin de la file d'attente

412
00:31:58,920 --> 00:32:03,730
afin que nous puissions récupérer les choses de la tête et ajouter des choses à la queue.

413
00:32:03,730 --> 00:32:06,890
Alors qu'avec la pile, nous n'avons jamais traiter avec le haut de la pile.

414
00:32:06,890 --> 00:32:08,900
Nous n'avons jamais eu d'accéder au bas de la pile.

415
00:32:08,900 --> 00:32:12,220
Nous avons seulement ajouté des choses vers le haut et a pris les choses hors de la partie supérieure

416
00:32:12,220 --> 00:32:17,470
nous n'avons donc pas besoin de ce champ supplémentaire à l'intérieur de notre structure.

417
00:32:17,470 --> 00:32:20,590
Est-ce que généralement un sens?

418
00:32:20,590 --> 00:32:27,670
Très bien. Oui, Charlotte? [Charlotte, inintelligible]

419
00:32:27,670 --> 00:32:32,660
[Hardison] C'est une très bonne question, et c'est celui qui est venu en conférence.

420
00:32:32,660 --> 00:32:36,290
Peut-être la marche à travers quelques exemples vont illustrer pourquoi

421
00:32:36,290 --> 00:32:41,400
nous ne voulons pas d'utiliser des chaînes [0] à la tête de la file d'attente.

422
00:32:41,400 --> 00:32:46,770
>> Alors, imaginez ce que nous avons notre file d'attente, nous allons l'appeler file d'attente.

423
00:32:46,770 --> 00:32:49,210
Au début, quand nous avons tout juste instancié,

424
00:32:49,210 --> 00:32:53,330
quand nous venons-il déclaré, nous n'avons pas initialisé quoi que ce soit.

425
00:32:53,330 --> 00:32:56,790
C'est tous les déchets. Alors bien sûr, nous voulons faire en sorte que nous initialisons

426
00:32:56,790 --> 00:33:00,950
la taille et les domaines tête à 0, quelque chose de raisonnable.

427
00:33:00,950 --> 00:33:05,770
Nous pourrions aussi aller de l'avant et nulle sur les éléments dans notre file d'attente.

428
00:33:05,770 --> 00:33:09,930
Et pour rendre ce bon schéma, vous remarquerez que maintenant notre file d'attente ne peut contenir trois éléments;

429
00:33:09,930 --> 00:33:13,150
alors que notre pile peut tenir quatre, notre file d'attente ne peut contenir que trois.

430
00:33:13,150 --> 00:33:18,680
Et c'est juste pour faire le bon schéma.

431
00:33:18,680 --> 00:33:26,150
La première chose qui se passe ici, c'est que nous en file d'attente la chaîne "salut".

432
00:33:26,150 --> 00:33:30,380
Et tout comme nous l'avons fait avec la pile, rien de très différent ici,

433
00:33:30,380 --> 00:33:39,230
nous jetons sur la chaîne à cordes [0] et augmenter notre taille de 1.

434
00:33:39,230 --> 00:33:42,720
Nous en file d'attente "au revoir", il se fait mettre.

435
00:33:42,720 --> 00:33:45,870
Donc, cela ressemble à une pile pour la plupart.

436
00:33:45,870 --> 00:33:53,230
Nous avons commencé ici, nouvel élément, élément nouveau, la taille ne cesse d'augmenter.

437
00:33:53,230 --> 00:33:56,330
Qu'est-ce qui se passe à ce point quand nous voulons dequeue quelque chose?

438
00:33:56,330 --> 00:34:01,280
Quand nous voulons dequeue, qui est l'élément que nous voulons dequeue?

439
00:34:01,280 --> 00:34:04,110
[Basil] Strings [0]. >> Zéro. Exactement, Basil.

440
00:34:04,110 --> 00:34:10,960
Nous voulons nous débarrasser de la première chaîne, celui-ci, «salut».

441
00:34:10,960 --> 00:34:13,170
Alors quelle est l'autre chose qui a changé?

442
00:34:13,170 --> 00:34:17,010
Remarquez quand nous sommes passés quelque chose hors de la pile, nous avons juste changé les dimensions,

443
00:34:17,010 --> 00:34:22,080
mais ici, nous avons un certain nombre de choses qui changent.

444
00:34:22,080 --> 00:34:27,440
Non seulement le changement de taille, mais les changements à la tête.

445
00:34:27,440 --> 00:34:31,020
Cela va revenir au point de Charlotte tôt:

446
00:34:31,020 --> 00:34:38,699
pourquoi avons-nous cette tête aussi?

447
00:34:38,699 --> 00:34:42,110
Est-il judicieux aujourd'hui, Charlotte? Type d'>>.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Type de? Donc ce qui s'est passé lorsque nous dequeued?

449
00:34:47,500 --> 00:34:54,340
Qu'est-ce que la tête faire maintenant est intéressant?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Oh, parce qu'il a changé - d'accord. Je vois.

451
00:34:56,449 --> 00:35:02,090
Parce que la tête - où la tête est orientée à l'évolution des termes de l'emplacement.

452
00:35:02,090 --> 00:35:07,200
Ce n'est plus toujours le seul indice zéro. >> Oui, exactement.

453
00:35:07,200 --> 00:35:17,660
Qu'est-ce qui s'est passé, si dequeueing l'élément haut

454
00:35:17,660 --> 00:35:20,590
a été fait et nous n'avons pas eu ce champ tête

455
00:35:20,590 --> 00:35:26,880
parce que nous avons toujours été d'appeler cette chaîne à 0 indexer la tête de notre file d'attente,

456
00:35:26,880 --> 00:35:30,170
alors nous aurions à passer le reste de la file d'attente vers le bas.

457
00:35:30,170 --> 00:35:36,010
Nous serions obligés de passer «au revoir» à partir de chaînes de caractères [1] pour les cordes [0].

458
00:35:36,010 --> 00:35:38,760
Et strings [2] vers le bas pour cordes [1].

459
00:35:38,760 --> 00:35:43,050
Et nous aurions dû le faire pour la liste complète des éléments,

460
00:35:43,050 --> 00:35:45,110
l'ensemble du réseau d'éléments.

461
00:35:45,110 --> 00:35:50,490
Et quand nous faisons cela avec un tableau, qui devient vraiment cher.

462
00:35:50,490 --> 00:35:53,340
Donc, ici, ce n'est pas une grosse affaire. Nous venons d'avoir trois éléments dans notre tableau.

463
00:35:53,340 --> 00:35:57,230
Mais si nous avions une file d'attente d'un millier d'éléments ou un million éléments,

464
00:35:57,230 --> 00:36:00,060
et puis tout d'un coup, nous commençons à faire un tas de dequeue appelle tous dans une boucle,

465
00:36:00,060 --> 00:36:03,930
les choses vont vraiment à ralentir car il se déplace tout vers le bas en permanence.

466
00:36:03,930 --> 00:36:07,320
Vous savez, passer par 1, passage de 1, passage de 1, passage de 1.

467
00:36:07,320 --> 00:36:13,650
Au lieu de cela, nous utilisons cette tête, on appelle cela un «pointeur», même si ce n'est pas vraiment un pointeur

468
00:36:13,650 --> 00:36:16,430
au sens strict, ce n'est pas un type pointeur.

469
00:36:16,430 --> 00:36:19,410
Ce n'est pas un int * ou char * ou quelque chose comme ça.

470
00:36:19,410 --> 00:36:28,930
Mais elle pointe ou indiquant la tête de notre file d'attente. Ouais?

471
00:36:28,930 --> 00:36:38,800
>> [Étudiants] Comment dequeue sais juste pop off tout ce qui est à la tête?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Comment dequeue sais pas comment pour faire sauter tout ce qui est à la tête? Droit >>, ouais.

473
00:36:43,620 --> 00:36:49,050
>> Qu'est-ce qu'il regarde est juste quelque soit le domaine social est fixé à.

474
00:36:49,050 --> 00:36:52,710
Ainsi, dans ce premier cas, si l'on regarde ici,

475
00:36:52,710 --> 00:36:55,690
notre tête est 0, 0 index. Droit >>.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Donc, il dit juste correct, eh bien, l'élément à l'index 0, la chaîne "salut",

477
00:37:00,500 --> 00:37:03,050
est l'élément à la tête de notre file d'attente.

478
00:37:03,050 --> 00:37:05,570
Donc, nous allons dequeue ce type.

479
00:37:05,570 --> 00:37:09,800
Et ce sera l'élément qui est retourné à l'appelant.

480
00:37:09,800 --> 00:37:14,540
Oui, Saad? Alors >> la tête définit essentiellement la - où vous allez l'index?

481
00:37:14,540 --> 00:37:17,750
C'est le début de celui-ci? Ouais >>. Ok >>.

482
00:37:17,750 --> 00:37:22,900
[Hardison] C'est de devenir le nouveau départ pour notre tableau.

483
00:37:22,900 --> 00:37:28,930
Ainsi, lorsque vous dequeue quelque chose, tout ce que vous avez à faire est accéder à l'élément à l'index q.head,

484
00:37:28,930 --> 00:37:32,240
et ce sera l'élément que vous voulez dequeue.

485
00:37:32,240 --> 00:37:34,930
Vous avez également à diminuer la taille.

486
00:37:34,930 --> 00:37:39,430
Nous verrons dans un instant où les choses deviennent un peu délicat avec cela.

487
00:37:39,430 --> 00:37:46,520
Nous dequeue, et maintenant, si nous en file d'attente à nouveau,

488
00:37:46,520 --> 00:37:51,300
où allons-nous en file d'attente?

489
00:37:51,300 --> 00:37:55,000
D'où vient l'élément suivant aller dans notre file d'attente?

490
00:37:55,000 --> 00:37:57,980
Disons que nous voulons en file d'attente la chaîne "CS".

491
00:37:57,980 --> 00:38:02,240
Dans laquelle index-il aller? [Les élèves] Strings [2]. Deux >>.

492
00:38:02,240 --> 00:38:04,980
Pourquoi 2 et pas 0?

493
00:38:04,980 --> 00:38:13,570
[Basil] Parce que maintenant, la tête est de 1, de sorte que c'est comme le début de la liste?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Droit. Et ce qui indique la fin de la liste?

495
00:38:21,220 --> 00:38:23,290
Qu'est-ce qu'on utilise pour désigner la fin de notre file d'attente?

496
00:38:23,290 --> 00:38:25,970
La tête est la tête de notre file d'attente, le début de notre file d'attente.

497
00:38:25,970 --> 00:38:29,530
Quelle est la fin de notre file d'attente? [Etudiants] Taille. Taille >>, exactement.

498
00:38:29,530 --> 00:38:36,360
Ainsi, nos nouveaux éléments vont à sa taille, et les éléments que nous décoller sortir à la tête.

499
00:38:36,360 --> 00:38:45,390
Quand nous en file d'attente l'élément suivant, nous allons le mettre à sa taille.

500
00:38:45,390 --> 00:38:48,530
[Étudiants] Avant de mettre les choses en bien, la taille était de 1, non?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Droit. Donc, pas tout à fait au format. + Taille, pas une, mais la tête +.

502
00:38:55,690 --> 00:38:59,990
Parce que nous sommes passés tout par la quantité tête.

503
00:38:59,990 --> 00:39:14,270
Donc, ici, maintenant nous avons une file d'attente de taille 1 qui commence à l'index 1.

504
00:39:14,270 --> 00:39:20,730
La queue est l'indice 2. Oui?

505
00:39:20,730 --> 00:39:25,780
>> [Étudiants] Qu'est-ce qui se passe quand vous dequeue cordes [0], ainsi que les chaînes «fentes de mémoire

506
00:39:25,780 --> 00:39:29,420
juste me vider, au fond, ou tout simplement oublié?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Ouais. En ce sens, nous ne faisons que de les oublier.

508
00:39:34,700 --> 00:39:42,640
Si nous étions stocker des copies de -

509
00:39:42,640 --> 00:39:46,310
plusieurs structures de données enregistrerez souvent de leurs propres copies des éléments

510
00:39:46,310 --> 00:39:51,760
de sorte que la personne qui gère la structure de données n'a pas à se soucier

511
00:39:51,760 --> 00:39:53,650
d'où tous ces pointeurs sont en cours.

512
00:39:53,650 --> 00:39:56,000
La structure de données s'accroche à tout, s'accroche à toutes les copies,

513
00:39:56,000 --> 00:39:59,580
afin de s'assurer que tout subsiste en conséquence.

514
00:39:59,580 --> 00:40:03,140
Toutefois, dans ce cas, ces structures de données juste, pour plus de simplicité,

515
00:40:03,140 --> 00:40:05,580
ne sont pas de faire des copies de tout ce que nous vous stockez en eux.

516
00:40:05,580 --> 00:40:08,630
[Étudiants] Donc est-ce un réseau continu de -? Oui >>.

517
00:40:08,630 --> 00:40:14,350
Si nous regardons en arrière à ce que la définition était de cette structure, il est.

518
00:40:14,350 --> 00:40:19,110
C'est juste un tableau standard, comme vous avez vu,

519
00:40:19,110 --> 00:40:24,280
un tableau de char * s.

520
00:40:24,280 --> 00:40:26,340
Est-ce que -? >> Ouais, je me demandais

521
00:40:26,340 --> 00:40:29,130
si vous finirez par manquer de mémoire, dans une certaine mesure,

522
00:40:29,130 --> 00:40:32,330
si vous avez tous ces espaces vides dans votre tableau?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Oui, c'est un bon point.

524
00:40:36,390 --> 00:40:41,530
>> Si l'on regarde ce qui s'est passé aujourd'hui à ce point,

525
00:40:41,530 --> 00:40:46,350
nous avons rempli notre file d'attente, elle ressemble.

526
00:40:46,350 --> 00:40:50,390
Mais nous n'avons pas vraiment rempli notre file d'attente

527
00:40:50,390 --> 00:40:57,710
parce que nous avons une file d'attente qui est de taille 2, mais il commence à l'index 1,

528
00:40:57,710 --> 00:41:02,160
parce que c'est là notre pointeur de tête est.

529
00:41:02,160 --> 00:41:08,400
Comme vous le disiez, cet élément à cordes [0], à l'indice 0, n'est pas vraiment là.

530
00:41:08,400 --> 00:41:10,450
Il n'est pas dans notre file d'attente plus.

531
00:41:10,450 --> 00:41:16,460
Nous n'avions tout simplement pas la peine d'y aller et l'écraser lorsque nous sortir de la file.

532
00:41:16,460 --> 00:41:18,700
Ainsi, même si on dirait que nous sommes à court de mémoire, nous n'avons pas vraiment.

533
00:41:18,700 --> 00:41:23,270
Cette tache est disponible pour nous à utiliser.

534
00:41:23,270 --> 00:41:29,310
Le comportement approprié, si nous devions essayer quelque chose et le premier dequeue

535
00:41:29,310 --> 00:41:34,420
comme "au revoir", qui apparaîtra au revoir au large.

536
00:41:34,420 --> 00:41:38,460
Maintenant, notre file d'attente commence à l'index 2 et est de taille 1.

537
00:41:38,460 --> 00:41:42,240
Et maintenant, si nous essayons quelque chose de nouveau en file d'attente et, disons 50,

538
00:41:42,240 --> 00:41:47,880
50 doit aller dans cet endroit à l'index 0

539
00:41:47,880 --> 00:41:51,270
parce qu'il est toujours disponible pour nous. Oui, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Est-ce que se faire automatiquement?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Il ne se passe pas tout à fait automatiquement. Vous devez faire le calcul

542
00:41:56,150 --> 00:42:00,380
pour le faire fonctionner, mais essentiellement ce que nous avons fait, c'est que nous venons de enroulé autour.

543
00:42:00,380 --> 00:42:04,070
[Saad] Et est-ce correct si cela a un trou au milieu de celui-ci?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Il est si on peut faire le calcul fonctionne de façon appropriée.

545
00:42:08,720 --> 00:42:15,470
>> Et il s'avère que ce n'est en fait pas si difficile à faire avec l'opérateur mod.

546
00:42:15,470 --> 00:42:20,040
Ainsi, tout comme nous l'avons fait avec César et les choses crypto,

547
00:42:20,040 --> 00:42:25,190
en utilisant mod, nous pouvons faire avancer les choses pour envelopper et continuer

548
00:42:25,190 --> 00:42:28,090
autour et autour et autour de notre file d'attente,

549
00:42:28,090 --> 00:42:32,180
garder ce pointeur de tête à se déplacer.

550
00:42:32,180 --> 00:42:38,840
Notez que la taille est toujours en respectant le nombre d'éléments réellement dans la file d'attente.

551
00:42:38,840 --> 00:42:43,110
Et c'est juste le pointeur de tête qui maintient le vélo à travers.

552
00:42:43,110 --> 00:42:49,660
Si l'on regarde ce qui s'est passé ici, si nous revenons au début,

553
00:42:49,660 --> 00:42:55,020
et vous venez de regarder ce qui se passe à la tête

554
00:42:55,020 --> 00:42:58,240
quand nous en file d'attente quelque chose, rien ne s'est passé dans la tête.

555
00:42:58,240 --> 00:43:00,970
Quand nous en file d'attente d'autre chose, rien ne s'est passé dans la tête.

556
00:43:00,970 --> 00:43:04,130
Dès que nous dequeued quelque chose, la tête monte par un.

557
00:43:04,130 --> 00:43:06,600
Nous en file d'attente quelque chose, rien ne se passe dans la tête.

558
00:43:06,600 --> 00:43:11,060
Quand nous dequeue quelque chose, tout d'un coup la tête est incrémenté.

559
00:43:11,060 --> 00:43:14,660
Quand nous avons quelque chose en file d'attente, rien ne se passe dans la tête.

560
00:43:14,660 --> 00:43:20,240
>> Que se passerait-il à ce point si nous devions dequeue quelque chose de nouveau?

561
00:43:20,240 --> 00:43:23,240
Toute pensée? Qu'arriverait-il à la tête?

562
00:43:23,240 --> 00:43:27,190
Que faut-il à la tête

563
00:43:27,190 --> 00:43:32,990
si nous devions dequeue quelque chose d'autre?

564
00:43:32,990 --> 00:43:35,400
La tête en ce moment est à l'indice 2,

565
00:43:35,400 --> 00:43:38,920
ce qui signifie que la tête de la file d'attente est strings [2].

566
00:43:38,920 --> 00:43:44,280
[Étudiants] Qui retourne 0? >> Elle doit retourner à 0. Il faut envelopper retourna, exactement.

567
00:43:44,280 --> 00:43:48,440
Jusqu'à présent, chaque fois que nous avons appelé dequeue, nous avons ajouté un à la tête,

568
00:43:48,440 --> 00:43:50,960
ajouter une à la tête, ajouter une à la tête, ajouter une à la tête.

569
00:43:50,960 --> 00:43:58,400
Dès que le pointeur de tête arrive au dernier indice dans notre tableau,

570
00:43:58,400 --> 00:44:05,650
alors nous devons conclure retour vers le début, revenir à 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Qu'est ce qui détermine la capacité de la file d'attente dans une pile?

572
00:44:09,900 --> 00:44:13,120
[Hardison] Dans ce cas, nous venons avec une constante # défini. Ok >>.

573
00:44:13,120 --> 00:44:19,590
[Hardison] Dans le fichier réel. C, vous pouvez aller dans et dans la boue avec elle un peu

574
00:44:19,590 --> 00:44:21,710
et de le rendre aussi grand ou aussi peu que vous voulez.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Ainsi, lorsque vous faites une file d'attente, comment voulez-vous que l'ordinateur sait

576
00:44:25,310 --> 00:44:29,120
la taille que vous voulez que la pile de l'être?

577
00:44:29,120 --> 00:44:31,700
[Hardison] C'est une très bonne question.

578
00:44:31,700 --> 00:44:34,800
Il existe deux façons. La première est de simplement définir à l'avance

579
00:44:34,800 --> 00:44:42,050
et dire que cela va être une file d'attente qui possède 4 éléments ou 50 éléments ou 10.000.

580
00:44:42,050 --> 00:44:45,430
L'autre façon est de faire ce que les gens édition pirates font

581
00:44:45,430 --> 00:44:52,310
et créer des fonctions pour que votre file d'attente croissance dynamique en plus de choses sont ajoutés po

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Donc, pour aller avec la première option, quelle syntaxe que vous utilisez

583
00:44:54,740 --> 00:44:57,830
pour indiquer au programme quelle est la taille de la file d'attente?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Donc, nous allons sortir de cette.

585
00:45:04,780 --> 00:45:12,650
Je suis toujours dans pile.c ici, donc je vais juste pour faire défiler vers le haut ici.

586
00:45:12,650 --> 00:45:17,920
Pouvez-vous voir juste là? Il s'agit de la capacité de 10 # define.

587
00:45:17,920 --> 00:45:24,600
Et c'est presque la même syntaxe exacte que nous avons pour la file d'attente.

588
00:45:24,600 --> 00:45:28,390
Sauf dans la file d'attente, nous avons ce champ struct supplémentaire ici.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, je pensais que la capacité signifie la capacité de la chaîne.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Ca y est la longueur maximale d'un mot. >> Compris.

591
00:45:36,770 --> 00:45:41,180
Ouais. La capacité ici - c'est un excellent point.

592
00:45:41,180 --> 00:45:44,000
Et c'est quelque chose qui est difficile

593
00:45:44,000 --> 00:45:49,480
parce que ce que nous avons déclaré ici est un tableau de char * s.

594
00:45:49,480 --> 00:45:52,770
Un tableau de pointeurs.

595
00:45:52,770 --> 00:45:56,690
Il s'agit d'un tableau de caractères.

596
00:45:56,690 --> 00:46:01,690
C'est probablement ce que vous avez vu quand vous avez été la déclaration de vos tampons pour le fichier I / O,

597
00:46:01,690 --> 00:46:06,840
quand vous avez été la création de chaînes manuellement sur la pile.

598
00:46:06,840 --> 00:46:09,090
Cependant, ce que nous avons ici, c'est un tableau de char * s.

599
00:46:09,090 --> 00:46:13,400
Donc, c'est un tableau de pointeurs.

600
00:46:13,400 --> 00:46:18,350
En fait, si l'on zoom arrière et on regarde ce qui se passe ici

601
00:46:18,350 --> 00:46:23,140
dans la présentation, vous voyez que les éléments réels, les données de caractères

602
00:46:23,140 --> 00:46:26,180
ne sont pas stockées dans le tableau lui-même.

603
00:46:26,180 --> 00:46:42,690
Ce qui est stocké au sein de notre réseau ici sont des pointeurs vers les données de caractères.

604
00:46:42,690 --> 00:46:52,560
D'accord. Donc, nous avons vu comment la taille de la file d'attente est juste comme avec la pile,

605
00:46:52,560 --> 00:46:58,670
la taille respecte toujours le nombre d'éléments actuellement dans la file d'attente.

606
00:46:58,670 --> 00:47:02,720
Après avoir fait deux enqueues, la taille est 2.

607
00:47:02,720 --> 00:47:07,110
Après avoir fait une dequeue la taille est maintenant 1.

608
00:47:07,110 --> 00:47:09,330
Après avoir fait une autre enqueue la taille est remonté à 2.

609
00:47:09,330 --> 00:47:12,340
Ainsi, la taille respecte certainement le nombre d'éléments dans la file d'attente,

610
00:47:12,340 --> 00:47:15,580
puis la tête ne cesse de cyclisme.

611
00:47:15,580 --> 00:47:20,210
Il va de 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
Et chaque fois que nous appelons dequeue, le pointeur de tête est incrémenté à l'index suivant.

613
00:47:25,620 --> 00:47:29,930
Et si la tête est sur le point de passer en revue, il reboucle autour de 0.

614
00:47:29,930 --> 00:47:34,870
Donc, avec cela, nous pouvons écrire la fonction dequeue.

615
00:47:34,870 --> 00:47:40,200
Et nous allons quitter la fonction enqueue pour vous les gars pour mettre en œuvre la place.

616
00:47:40,200 --> 00:47:45,880
>> Quand nous dequeue un élément de notre file d'attente,

617
00:47:45,880 --> 00:47:55,490
ce qui était la première chose que Daniel fait lorsque nous avons commencé à écrire la fonction pop pour les piles?

618
00:47:55,490 --> 00:48:00,490
Permettez-moi entendre parler de quelqu'un qui n'a pas encore parlé.

619
00:48:00,490 --> 00:48:06,710
Voyons, Saad, vous rappelez-vous ce que Daniel a fait que la première chose quand il a écrit la pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Il y avait, c'était - >> Il a testé pour quelque chose.

621
00:48:08,860 --> 00:48:12,140
[Saad] Si la taille est supérieure à 0. >> Exactement.

622
00:48:12,140 --> 00:48:14,390
Et quel était ce test pour?

623
00:48:14,390 --> 00:48:19,090
[Saad] Cela a été tester pour voir s'il ya quelque chose à l'intérieur du tableau.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Ouais. Exactement. Donc, vous ne pouvez pas récupérer quelque chose hors de la pile si elle est vide.

625
00:48:23,210 --> 00:48:26,510
De même, vous ne pouvez pas dequeue quoi que ce soit à partir d'une file d'attente si elle est vide.

626
00:48:26,510 --> 00:48:30,420
Quelle est la première chose que nous devons faire dans notre fonction dequeue ici, pensez-vous?

627
00:48:30,420 --> 00:48:33,860
[Saad] Si la taille est supérieure à 0? Ouais >>.

628
00:48:33,860 --> 00:48:37,710
Dans ce cas, je l'ai fait juste testé pour voir si elle est de 0.

629
00:48:37,710 --> 00:48:42,240
Si c'est 0, on peut retourner null.

630
00:48:42,240 --> 00:48:45,280
Mais la logique exactement la même.

631
00:48:45,280 --> 00:48:49,110
Et nous allons continuer avec cela.

632
00:48:49,110 --> 00:48:54,600
Si la taille n'est pas 0, où est l'élément que nous voulons dequeue?

633
00:48:54,600 --> 00:48:58,550
[Saad] A la tête? >> Exactement.

634
00:48:58,550 --> 00:49:01,720
Nous ne pouvons tout simplement retirer le premier élément dans notre file d'attente

635
00:49:01,720 --> 00:49:07,040
en accédant à l'élément de la tête.

636
00:49:07,040 --> 00:49:14,630
Rien de fou.

637
00:49:14,630 --> 00:49:19,620
Après cela, que devons-nous faire? Ce qui doit arriver?

638
00:49:19,620 --> 00:49:23,740
Quelle est la chose d'autre dont nous avons parlé dans dequeue?

639
00:49:23,740 --> 00:49:28,130
Deux choses doivent se produire, parce que notre file d'attente a changé.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Réduire la taille. >> Nous devons réduire la taille et d'accroître la tête? Exactement.

641
00:49:35,640 --> 00:49:40,600
Pour accroître la tête, nous ne pouvons pas aveuglément augmenter la hauteur, souvenez-vous.

642
00:49:40,600 --> 00:49:45,080
Nous ne pouvons pas faire queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Nous devons également comprendre ce mod par la capacité.

644
00:49:51,630 --> 00:49:54,740
Et pourquoi avons-nous la capacité de mod, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Parce qu'il a à enrouler autour. >> Exactement.

646
00:49:58,680 --> 00:50:04,750
Nous mod par la capacité, car il doit envelopper arrière autour de 0.

647
00:50:04,750 --> 00:50:07,400
Alors maintenant, à ce stade, nous pouvons faire ce que Daniel dit.

648
00:50:07,400 --> 00:50:12,700
Nous pouvons diminuer la taille.

649
00:50:12,700 --> 00:50:29,170
Et puis on peut simplement retourner l'élément qui était à la tête de la file d'attente.

650
00:50:29,170 --> 00:50:34,000
Il a l'air assez gnarly au premier abord. Vous pouvez poser une question. Désolé?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Pourquoi le premier en haut de la file d'attente? Où ça va?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Il s'agit de la quatrième ligne du bas.

653
00:50:42,480 --> 00:50:46,060
Après nous tester pour s'assurer que notre file d'attente n'est pas vide,

654
00:50:46,060 --> 00:50:54,100
nous nous retirons char * d'abord, nous nous retirons l'élément qui est assis à la tête de l'indice

655
00:50:54,100 --> 00:50:58,680
de notre gamme, notre gamme de chaînes, >> et que le premier appel?

656
00:50:58,680 --> 00:51:04,500
[Hardison] Et nous appelons en premier. Ouais.

657
00:51:04,500 --> 00:51:09,850
Pour faire suite à ce sujet, pourquoi pensez-vous que nous devions faire cela?

658
00:51:09,850 --> 00:51:18,270
[Sam] Chaque premier revient tout juste q.strings [q.head]? Ouais >>.

659
00:51:18,270 --> 00:51:23,830
Parce que >> nous faisons cette évolution de la q.head avec la fonction mod,

660
00:51:23,830 --> 00:51:27,810
et il n'y a aucun moyen de le faire dans la conduite de retour également.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Exactement. Vous êtes sur place. Sam est totalement justes.

662
00:51:31,640 --> 00:51:36,800
La raison pour laquelle nous avons dû retirer le premier élément dans notre file d'attente et le stocker dans une variable

663
00:51:36,800 --> 00:51:43,030
C'est parce que cette ligne où nous venions q.head,

664
00:51:43,030 --> 00:51:47,030
il ya l'opérateur mod là n'est pas quelque chose que nous pouvons faire

665
00:51:47,030 --> 00:51:51,230
et le faire entrer en vigueur sur la tête sans - sur une seule ligne.

666
00:51:51,230 --> 00:51:54,480
Donc, nous avons à tirer le premier élément, puis réglez la tête,

667
00:51:54,480 --> 00:52:00,430
ajuster la taille, puis retourner l'élément qui nous nous sommes retirés.

668
00:52:00,430 --> 00:52:02,680
Et c'est quelque chose que nous allons voir arriver plus tard avec

669
00:52:02,680 --> 00:52:04,920
listes chaînées, comme on joue avec eux.

670
00:52:04,920 --> 00:52:08,410
Souvent, quand vous libérer ou de l'élimination des listes chaînées

671
00:52:08,410 --> 00:52:13,500
vous devez vous rappeler l'élément suivant, le pointeur suivant d'une liste chaînée

672
00:52:13,500 --> 00:52:16,330
avant de disposer de l'actuel.

673
00:52:16,330 --> 00:52:23,580
Parce que sinon, vous jetez les informations de ce qui reste dans la liste.

674
00:52:23,580 --> 00:52:34,160
Maintenant, si vous allez à votre appareil, vous ouvrez queue.c-x-dehors de ça.

675
00:52:34,160 --> 00:52:39,390
Donc, si j'ouvre queue.c, laissez-moi un zoom avant ici,

676
00:52:39,390 --> 00:52:44,970
vous verrez que vous avez un fichier d'aspect semblable.

677
00:52:44,970 --> 00:52:49,200
D'aspect semblable fichier à ce que nous avions auparavant avec pile.c.

678
00:52:49,200 --> 00:52:54,690
Nous avons notre structure de file d'attente définie comme nous l'avons vu dans les diapositives.

679
00:52:54,690 --> 00:52:59,870
>> Nous avons notre fonction enqueue qui est à faire pour vous.

680
00:52:59,870 --> 00:53:04,340
Et nous avons la fonction dequeue ici.

681
00:53:04,340 --> 00:53:06,870
La fonction dequeue dans le fichier n'est pas implémenté,

682
00:53:06,870 --> 00:53:13,230
mais je vais le remettre en place sur le PowerPoint de sorte que vous puissiez le saisir, si vous le souhaitez.

683
00:53:13,230 --> 00:53:16,690
Donc, pour les 5 prochaines minutes, vous les gars travailler sur enqueue

684
00:53:16,690 --> 00:53:22,570
qui est presque à l'opposé de dequeue.

685
00:53:22,570 --> 00:53:29,560
Vous n'avez pas besoin d'ajuster la tête lorsque vous enqueueing, mais qu'est-ce que vous avez à régler?

686
00:53:29,560 --> 00:53:38,920
Taille. Ainsi, lorsque vous enqueue, la tête reste intacte, la taille est changée.

687
00:53:38,920 --> 00:53:46,920
Mais cela prend un peu de - vous aurez à jouer avec ce mod

688
00:53:46,920 --> 00:53:57,560
de comprendre exactement ce que l'indice le nouvel élément doit être inséré à.

689
00:53:57,560 --> 00:54:03,080
Alors je vais vous donner les gars un peu, mettez dequeue remonter sur la diapositive,

690
00:54:03,080 --> 00:54:05,200
et que vous les gars avez des questions, leur crier afin que nous puissions

691
00:54:05,200 --> 00:54:09,220
tout le monde parle d'eux comme un groupe.

692
00:54:09,220 --> 00:54:13,960
En outre, avec la taille que vous ne - lorsque vous réglez la taille, vous pouvez toujours juste -

693
00:54:13,960 --> 00:54:18,720
avez-vous de mod la taille sans cesse? [Daniel] No. >> Vous n'avez pas de mod de la taille, à droite.

694
00:54:18,720 --> 00:54:24,260
Parce que la taille sera toujours, si Tu es - en supposant que vous gérez les choses correctement,

695
00:54:24,260 --> 00:54:30,840
la taille sera toujours compris entre 0 et 3.

696
00:54:30,840 --> 00:54:38,680
Où avez-vous de mod quand vous faites enqueue?

697
00:54:38,680 --> 00:54:41,060
[Étudiants] Uniquement pour la tête. Seuls >> pour la tête, exactement.

698
00:54:41,060 --> 00:54:44,620
Et pourquoi avez-vous de mod du tout dans enqueue?

699
00:54:44,620 --> 00:54:48,830
Quand une situation dans laquelle vous auriez à mod?

700
00:54:48,830 --> 00:54:53,630
[Étudiants] Si vous avez des trucs à des espaces, comme à des espaces 1 et 2,

701
00:54:53,630 --> 00:54:55,950
et puis vous avez besoin d'ajouter quelque chose à 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Oui, exactement. Donc, si le pointeur de votre tête est tout à la fin,

703
00:55:02,570 --> 00:55:14,210
ou si votre taille ainsi que votre tête est plus grand, ou plutôt, va s'enrouler autour de la file d'attente.

704
00:55:14,210 --> 00:55:17,830
>> Donc, dans cette situation que nous avons ici sur la diapositive en ce moment,

705
00:55:17,830 --> 00:55:24,370
si je veux quelque chose en file d'attente en ce moment,

706
00:55:24,370 --> 00:55:31,110
nous voulons quelque chose en file d'attente à l'index 0.

707
00:55:31,110 --> 00:55:35,450
Donc, si vous regardez où va le 50, et je l'appelle enqueue 50,

708
00:55:35,450 --> 00:55:40,840
il y descend en bas. Il va en index 0.

709
00:55:40,840 --> 00:55:44,160
Il remplace le «salut» qui a déjà été dequeued.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Ne vous prenez soin de cela dans dequeue déjà?

711
00:55:46,210 --> 00:55:50,550
Pourquoi faut-il faire quelque chose avec la tête dans enqueue?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Oh, si vous n'êtes pas modifier la tête, désolé.

713
00:55:55,770 --> 00:56:02,310
Mais vous devez utiliser l'opérateur mod lorsque vous accédez

714
00:56:02,310 --> 00:56:04,250
l'élément que vous voulez en file d'attente lorsque vous accédez

715
00:56:04,250 --> 00:56:06,960
l'élément suivant dans la file d'attente.

716
00:56:06,960 --> 00:56:10,960
[Basil] Je n'ai pas fait cela, et j'ai eu le «succès» de l'existence.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, je comprends ce que vous dites.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Donc, vous didn't - vous venez de faire à q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Ouais. Je viens de changer d'autre, je n'ai rien fait avec la tête.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Vous n'avez pas réellement besoin de réinitialiser la tête d'être quoi que ce soit,

721
00:56:24,300 --> 00:56:31,650
mais quand vous indice dans le tableau de chaînes,

722
00:56:31,650 --> 00:56:39,500
vous avez réellement à aller de l'avant et de calculer l'endroit où l'élément suivant est,

723
00:56:39,500 --> 00:56:44,230
parce withe la pile, l'élément suivant dans votre pile était toujours

724
00:56:44,230 --> 00:56:48,740
à l'indice correspondant à la taille.

725
00:56:48,740 --> 00:56:55,850
Si nous regardons en arrière jusqu'à notre fonction push pile,

726
00:56:55,850 --> 00:57:03,100
on peut toujours débarquez dans notre élément nouveau à droite à la taille des index.

727
00:57:03,100 --> 00:57:06,710
Alors qu'avec la file d'attente, nous ne pouvons pas le faire

728
00:57:06,710 --> 00:57:10,340
parce que si nous sommes à cette situation,

729
00:57:10,340 --> 00:57:18,130
si nous en file d'attente 50 Notre nouvelle chaîne irait droit à cordes [1]

730
00:57:18,130 --> 00:57:20,540
que nous ne voulons pas faire.

731
00:57:20,540 --> 00:57:41,200
Nous voulons avoir la nouvelle chaîne aller à l'index 0.

732
00:57:41,200 --> 00:57:44,320
>> Est-ce que tout le monde - oui? [Étudiants] J'ai une question, mais ce n'est pas vraiment lié.

733
00:57:44,320 --> 00:57:48,160
Qu'est-ce que cela signifie quand quelqu'un appelle simplement quelque chose comme pointeur pred?

734
00:57:48,160 --> 00:57:51,260
Qu'est-ce que le nom court pour? Je sais que c'est juste un nom.

735
00:57:51,260 --> 00:57:59,110
[Hardison] pointeur Pred? Voyons voir. Dans quel contexte?

736
00:57:59,110 --> 00:58:01,790
[Étudiants] C'était pour l'insert. Je peux vous demander plus tard si vous voulez

737
00:58:01,790 --> 00:58:03,920
car ce n'est pas vraiment lié, mais je viens de -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Du code d'insertion de David de conférence?

739
00:58:07,300 --> 00:58:10,860
Nous ne pouvons tirer que vous et parler.

740
00:58:10,860 --> 00:58:15,550
Nous en parlerons la prochaine, une fois que nous arrivons à des listes chaînées.

741
00:58:15,550 --> 00:58:21,440
>> Donc, nous allons très vite voir ce que la fonction enqueue ressemble.

742
00:58:21,440 --> 00:58:26,530
Quelle est la première chose que les gens ont essayé de le faire dans votre ligne de enqueue? Dans cette file d'attente?

743
00:58:26,530 --> 00:58:29,960
Semblable à ce que vous avez fait pour pousser la pile.

744
00:58:29,960 --> 00:58:32,080
Qu'avez-vous fait, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, inintelligible]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Exactement. Si (q.size CAPACITÉ ==) -

747
00:58:45,700 --> 00:58:54,720
J'ai besoin de mettre mon appareil au bon endroit - return false.

748
00:58:54,720 --> 00:59:01,370
Zoom dans un peu. D'accord.

749
00:59:01,370 --> 00:59:03,800
Maintenant, quelle est la prochaine chose que nous devions faire?

750
00:59:03,800 --> 00:59:11,370
Tout comme avec la pile, et inséré au bon endroit.

751
00:59:11,370 --> 00:59:16,010
Et quel était le bon endroit pour insérer ce?

752
00:59:16,010 --> 00:59:23,170
Avec la pile c'était taille de l'index, avec cela, il n'est pas tout à fait cela.

753
00:59:23,170 --> 00:59:30,210
[Daniel] J'ai q.head--ou - q.strings >>? >> Ouais.

754
00:59:30,210 --> 00:59:40,470
q.strings [+ q.head q.size mod CAPACITÉ]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Nous voudrez probablement mettre des parenthèses autour de cette

756
00:59:42,740 --> 00:59:48,830
de sorte que nous obtenons la priorité appropriée et si c'est cleart à tout le monde.

757
00:59:48,830 --> 00:59:55,800
Et définir ce que l'égalité? >> Pour str? >> Pour str. Grande.

758
00:59:55,800 --> 01:00:00,160
Et maintenant, quelle est la dernière chose que nous devons faire?

759
01:00:00,160 --> 01:00:06,780
Tout comme nous l'avons fait dans la pile. >> Incrémentation de la taille? >> Incrémentation de la taille.

760
01:00:06,780 --> 01:00:13,830
Boom. Et puis, depuis le code de démarrage juste retourné false par défaut,

761
01:00:13,830 --> 01:00:27,460
nous voulons changer cette option à true si tout se passe à travers et tout va bien.

762
01:00:27,460 --> 01:00:33,050
Très bien. C'est beaucoup d'informations pour la section.

763
01:00:33,050 --> 01:00:39,480
Nous ne sommes pas tout à fait terminée. Nous voulons parler très rapidement sur des liaisons simples listes liées.

764
01:00:39,480 --> 01:00:44,010
Je vais mettre cette place afin que nous puissions y revenir plus tard.

765
01:00:44,010 --> 01:00:50,850
Mais revenons à notre présentation pour juste un peu plus transparents.

766
01:00:50,850 --> 01:00:53,790
Donc enqueue est TODO, maintenant que nous avons fait.

767
01:00:53,790 --> 01:00:57,430
>> Maintenant, nous allons jeter un oeil à des liaisons simples listes liées.

768
01:00:57,430 --> 01:01:00,040
Nous avons parlé de ces un peu plus dans la conférence.

769
01:01:00,040 --> 01:01:02,540
Combien d'entre vous les gars vu la démo où nous avions des gens

770
01:01:02,540 --> 01:01:08,220
maladroitement pointant vers chacun des nombres et d'autres organisation? >> J'étais dans cette.

771
01:01:08,220 --> 01:01:16,620
>> Qu'est-ce que vous en pensez? Ai fait, je l'espère démystifier ces bits un peu?

772
01:01:16,620 --> 01:01:25,990
Avec une liste, il s'avère que nous avons affaire avec ce type que nous allons appeler un nœud.

773
01:01:25,990 --> 01:01:32,520
Alors que la file d'attente et la pile nous avions structures qui nous avions appellent file d'attente dans la pile,

774
01:01:32,520 --> 01:01:34,860
nous avions ces nouvelle file d'attente dans les types de pile,

775
01:01:34,860 --> 01:01:39,240
voici une liste est vraiment juste constituée d'un groupe de nœuds.

776
01:01:39,240 --> 01:01:45,920
De la même manière que les chaînes sont juste un tas de caractères tous alignés les uns à côté des autres.

777
01:01:45,920 --> 01:01:50,650
Une liste chaînée est juste un noeud et un autre noeud et un autre noeud et un autre noeud.

778
01:01:50,650 --> 01:01:55,080
Et plutôt que de casser tous les noeuds entre eux et de les stocker de manière contiguë

779
01:01:55,080 --> 01:01:58,090
tout juste à côté de l'autre dans la mémoire,

780
01:01:58,090 --> 01:02:04,470
avoir ce pointeur suivant nous permet de stocker les nœuds partout où, au hasard.

781
01:02:04,470 --> 01:02:10,500
Et puis, sorte de fil tous ensemble au point de l'un à l'autre.

782
01:02:10,500 --> 01:02:15,850
>> Et quel était le gros avantage que cela a eu sur un tableau?

783
01:02:15,850 --> 01:02:21,680
Sur tout stockage contiguë juste coincé à côté de l'autre?

784
01:02:21,680 --> 01:02:24,190
Vous vous souvenez? Ouais? L'allocation dynamique de la mémoire >>?

785
01:02:24,190 --> 01:02:27,220
>> Allocation de mémoire dynamique dans quel sens?

786
01:02:27,220 --> 01:02:31,780
[Étudiants] Dans ce que vous pouvez continuer à faire plus grand et vous n'avez pas à déplacer votre tableau entier?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Exactement. Donc, avec un tableau, lorsque vous voulez mettre un élément nouveau dans le milieu,

788
01:02:40,940 --> 01:02:45,320
vous devez changer tout pour faire de la place.

789
01:02:45,320 --> 01:02:47,880
Et comme nous en avons parlé avec la file d'attente,

790
01:02:47,880 --> 01:02:50,080
c'est pourquoi nous gardons cela pointeur de tête,

791
01:02:50,080 --> 01:02:52,050
de sorte que nous ne sommes pas les choses changent constamment.

792
01:02:52,050 --> 01:02:54,520
Parce que devient cher si vous avez un grand tableau

793
01:02:54,520 --> 01:02:57,130
et vous êtes constamment à faire ces insertions aléatoires.

794
01:02:57,130 --> 01:03:00,820
Alors qu'avec une liste, tout ce que vous avez à faire est de le jeter sur un nouveau nœud,

795
01:03:00,820 --> 01:03:06,330
ajuster les pointeurs, et vous avez terminé.

796
01:03:06,330 --> 01:03:10,940
Ce qui craint à ce sujet?

797
01:03:10,940 --> 01:03:16,830
Mis à part le fait que ce n'est pas aussi facile de travailler avec comme un tableau? Ouais?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Eh bien, je suppose que c'est beaucoup plus difficile d'accéder à un élément spécifique dans la liste chaînée?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Vous ne pouvez pas accéder à un élément d'arbitraire dans le milieu de votre liste chaînée.

800
01:03:30,470 --> 01:03:33,800
Comment avez-vous de le faire à la place? >> Vous devez passer en revue l'ensemble de chose.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Ouais. Vous devez passer par un à la fois, un à la fois.

802
01:03:35,660 --> 01:03:38,480
C'est un énorme - c'est une douleur.

803
01:03:38,480 --> 01:03:41,550
Quel est l'autre - il ya une autre chute à cela.

804
01:03:41,550 --> 01:03:45,340
[Basil] Vous ne pouvez pas aller de l'avant et vers l'arrière? Il faut y aller une seule direction?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Ouais. Alors, comment pouvons-nous résoudre que, parfois?

806
01:03:48,570 --> 01:03:53,370
[Basil] doublement listes chaînées? >> Exactement. Il existe des listes doublement liés.

807
01:03:53,370 --> 01:03:55,540
Il ya aussi - excusez-moi?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Est-ce la même fonction que la chose que pred -

809
01:03:57,620 --> 01:04:01,090
Je viens de me rappeler, n'est-ce pas ce que la chose est pour pred?

810
01:04:01,090 --> 01:04:05,850
N'est-ce pas dans l'intervalle doublement et individuellement?

811
01:04:05,850 --> 01:04:10,020
[Hardison] Regardons exactement ce qu'il faisait.

812
01:04:10,020 --> 01:04:15,760
Alors on y va. Voici le code liste.

813
01:04:15,760 --> 01:04:25,620
Ici, nous avons predptr, ici. Est-ce que vous parlez?

814
01:04:25,620 --> 01:04:30,750
Donc, ce fut - il libère une liste et qu'il essaie de stocker un pointeur vers elle.

815
01:04:30,750 --> 01:04:35,000
Ce n'est pas le doublement, individuellement liés listes.

816
01:04:35,000 --> 01:04:40,090
Nous pouvons parler plus à ce sujet plus tard, car il est question ici de libérer la liste

817
01:04:40,090 --> 01:04:42,900
et je veux vous montrer quelques autres trucs d'abord.

818
01:04:42,900 --> 01:04:51,480
mais c'est juste - c'est se rappeler la valeur de ptr

819
01:04:51,480 --> 01:04:54,170
[Étudiants] Oh, c'est pointeur précédent? Ouais >>.

820
01:04:54,170 --> 01:05:04,070
Afin que nous puissions ensuite incrémenter ptr lui-même avant nous alors libre ce qui est predptr.

821
01:05:04,070 --> 01:05:09,130
Parce que nous ne pouvons pas libre ptr puis appelez ptr = ptr prochaine, non?

822
01:05:09,130 --> 01:05:11,260
Ce serait mauvais.

823
01:05:11,260 --> 01:05:20,940
Voyons donc, revenons à ce gars-là.

824
01:05:20,940 --> 01:05:23,900
>> L'autre point négatif est que sur les listes alors qu'avec un tableau

825
01:05:23,900 --> 01:05:26,520
il suffit de tous les éléments eux-mêmes empilés à côté de l'autre,

826
01:05:26,520 --> 01:05:29,050
ici nous avons également introduit ce pointeur.

827
01:05:29,050 --> 01:05:34,060
Il ya donc un morceau de mémoire supplémentaire que nous allons avoir à utiliser

828
01:05:34,060 --> 01:05:37,910
pour chaque élément que nous stockons dans notre liste.

829
01:05:37,910 --> 01:05:40,030
Nous obtenons la flexibilité, mais elle a un coût.

830
01:05:40,030 --> 01:05:42,230
Il est livré avec ce coût en temps,

831
01:05:42,230 --> 01:05:45,270
et il est livré avec ce coût trop de mémoire.

832
01:05:45,270 --> 01:05:47,800
Temps dans le sens que nous avons maintenant à passer en revue chaque élément dans le tableau

833
01:05:47,800 --> 01:05:58,670
pour trouver celui à l'indice 10, ou qui aurait été indice 10 dans un tableau.

834
01:05:58,670 --> 01:06:01,230
>> Juste très rapidement, quand on diagramme sur ces listes,

835
01:06:01,230 --> 01:06:05,980
généralement nous nous accrochons à la tête de la liste ou le premier pointeur de la liste

836
01:06:05,980 --> 01:06:08,010
et notez qu'il s'agit d'un pointeur vrai.

837
01:06:08,010 --> 01:06:11,100
C'est juste 4 octets. Ce n'est pas un nœud lui-même.

838
01:06:11,100 --> 01:06:17,120
Donc, vous voyez qu'il n'a pas de valeur int en elle, aucun pointeur à côté de lui.

839
01:06:17,120 --> 01:06:20,790
Il est littéralement juste un pointeur.

840
01:06:20,790 --> 01:06:23,550
Il va pointer vers quelque chose qui est une struct noeud réelle.

841
01:06:23,550 --> 01:06:28,480
[Sam] Un pointeur appelé nœud? Il s'agit d'>> - no. Il s'agit d'un pointeur vers quelque chose de noeud de type.

842
01:06:28,480 --> 01:06:32,540
Il s'agit d'un pointeur sur une struct noeud. >> Oh, d'accord.

843
01:06:32,540 --> 01:06:36,870
Schéma sur la gauche, le code sur la droite.

844
01:06:36,870 --> 01:06:42,190
On peut le mettre à null, ce qui est une bonne façon de commencer.

845
01:06:42,190 --> 01:06:49,850
Quand vous le diagramme, vous pouvez soit écrire comme nulle ou que vous mettez une ligne en travers comme ça.

846
01:06:49,850 --> 01:06:53,910
>> Une des façons les plus faciles de travailler avec des listes,

847
01:06:53,910 --> 01:06:57,430
et nous vous demandons de faire les deux prepend et ajouter de voir les différences entre les deux,

848
01:06:57,430 --> 01:07:01,320
mais préfixant est certainement plus facile.

849
01:07:01,320 --> 01:07:05,790
Lorsque vous faites précéder, c'est là que vous - lorsque vous prepend (7),

850
01:07:05,790 --> 01:07:10,050
vous allez créer la structure noeud

851
01:07:10,050 --> 01:07:13,870
et que vous définissez premier à pointer vers elle, parce que maintenant, depuis que nous avons préfixé,

852
01:07:13,870 --> 01:07:17,240
ça va être au début de la liste.

853
01:07:17,240 --> 01:07:22,540
Si nous prepend (3), qui crée un autre nœud, mais maintenant 3 sort avant le 7.

854
01:07:22,540 --> 01:07:31,130
Nous sommes donc essentiellement pousser les choses sur notre liste.

855
01:07:31,130 --> 01:07:34,720
Maintenant, vous pouvez voir que prepend, parfois, les gens l'appellent pousser,

856
01:07:34,720 --> 01:07:39,600
parce que vous poussez un nouvel élément sur votre liste.

857
01:07:39,600 --> 01:07:43,270
Il est également facile de supprimer à l'avant d'une liste.

858
01:07:43,270 --> 01:07:45,650
Alors, les gens appellent souvent que pop.

859
01:07:45,650 --> 01:07:52,200
Et de cette façon, vous pouvez émuler une pile en utilisant une liste chaînée.

860
01:07:52,200 --> 01:07:57,880
Oups. Désolé, maintenant nous entrons dans append. Nous voilà donc préfixé (7), maintenant nous prepend (3).

861
01:07:57,880 --> 01:08:02,600
Si nous préfixé quelque chose d'autre sur cette liste, si nous préfixé (4),

862
01:08:02,600 --> 01:08:06,540
alors nous aurions 4, puis 3 puis 7.

863
01:08:06,540 --> 01:08:14,220
Alors, on pourrait éclater et enlever 4, supprimer 3, supprimer 7.

864
01:08:14,220 --> 01:08:16,500
Souvent le moyen le plus intuitif de penser à ce sujet est en append.

865
01:08:16,500 --> 01:08:20,310
J'ai donc schématisé sur ce qu'il pourrait ressembler à ajouter ici.

866
01:08:20,310 --> 01:08:23,380
Ici, annexé (7) n'a pas l'air différent

867
01:08:23,380 --> 01:08:25,160
parce qu'il n'y a qu'un seul élément dans la liste.

868
01:08:25,160 --> 01:08:28,620
Et en ajoutant (3) qu'elle met à la fin.

869
01:08:28,620 --> 01:08:31,020
Peut-être que vous pouvez voir en ce moment le tour avec append

870
01:08:31,020 --> 01:08:36,600
est que, puisque nous ne savons où le début de la liste est,

871
01:08:36,600 --> 01:08:39,450
à ajouter à une liste que vous avez à marcher tout le chemin à travers la liste

872
01:08:39,450 --> 01:08:46,500
pour arriver à la fin, arrêtez, puis construire votre noeud et tout plunk vers le bas.

873
01:08:46,500 --> 01:08:50,590
Câblez toutes les choses en place.

874
01:08:50,590 --> 01:08:55,170
Donc, avec préfixe, comme nous venons déchiré par ce très rapidement,

875
01:08:55,170 --> 01:08:58,170
lorsque vous faites précéder d'une liste, il est assez simple.

876
01:08:58,170 --> 01:09:02,960
>> Vous faites votre noeud nouvelle, qu'elle implique une allocation dynamique de mémoire.

877
01:09:02,960 --> 01:09:09,830
Donc, ici, nous faisons une struct noeud en utilisant malloc.

878
01:09:09,830 --> 01:09:14,710
Donc malloc nous utilisons parce que vous mis de côté la mémoire pour nous pour plus tard

879
01:09:14,710 --> 01:09:20,350
parce que nous ne voulons pas cela - nous voulons que cette mémoire se perpétue pendant un long moment.

880
01:09:20,350 --> 01:09:25,350
Et nous obtenons un pointeur vers l'espace dans la mémoire que nous venons alloué.

881
01:09:25,350 --> 01:09:29,260
Nous utilisons la taille du noeud, nous n'avons pas la somme des champs.

882
01:09:29,260 --> 01:09:31,899
Nous n'avons pas générer manuellement le nombre d'octets,

883
01:09:31,899 --> 01:09:39,750
au lieu que nous utilisons sizeof afin que nous sachions que nous obtenons le nombre approprié d'octets.

884
01:09:39,750 --> 01:09:43,660
Nous nous assurons de tester que notre appel malloc réussi.

885
01:09:43,660 --> 01:09:47,939
C'est quelque chose que vous voulez faire en général.

886
01:09:47,939 --> 01:09:52,590
Sur les machines modernes, à court de mémoire n'est pas quelque chose qui est facile

887
01:09:52,590 --> 01:09:56,610
à moins que vous allouons une tonne de trucs et de faire une liste énorme,

888
01:09:56,610 --> 01:10:02,220
mais si vous construire des choses pour, disons, comme un iPhone ou un Android,

889
01:10:02,220 --> 01:10:05,230
vous ne disposer de ressources mémoire limitées, surtout si vous faites quelque chose d'intense.

890
01:10:05,230 --> 01:10:08,300
Donc, il est bon d'obtenir en pratique.

891
01:10:08,300 --> 01:10:10,510
>> Remarquez que j'ai utilisé un couple de différentes fonctions ici

892
01:10:10,510 --> 01:10:12,880
que vous avez vu ce sont des sortes de nouvelles.

893
01:10:12,880 --> 01:10:15,870
Donc fprintf est juste comme printf

894
01:10:15,870 --> 01:10:21,320
l'exception de son premier argument est le flux auquel vous souhaitez imprimer.

895
01:10:21,320 --> 01:10:23,900
Dans ce cas, nous voulons imprimer à la chaîne d'erreur standard

896
01:10:23,900 --> 01:10:29,410
qui est différente de la norme outstream.

897
01:10:29,410 --> 01:10:31,620
Par défaut, il se présente au même endroit.

898
01:10:31,620 --> 01:10:34,600
Il imprime aussi au terminal, mais vous pouvez -

899
01:10:34,600 --> 01:10:38,790
en utilisant les commandes que vous avez appris sur les techniques de redirection,

900
01:10:38,790 --> 01:10:42,290
vous avez appris à propos de la vidéo de Tommy pour 4 ensemble de problèmes, vous pouvez le diriger

901
01:10:42,290 --> 01:10:47,900
à différents domaines, puis quitter, ici, les sorties de votre programme.

902
01:10:47,900 --> 01:10:50,440
Il s'agit essentiellement comme un retour de principal,

903
01:10:50,440 --> 01:10:53,600
sauf que nous utilisons ici la sortie, car le retour ne fera rien.

904
01:10:53,600 --> 01:10:57,140
Nous ne sommes pas en principal, de sorte scrutin ne quitter le programme comme nous le voulons.

905
01:10:57,140 --> 01:11:03,020
Donc, nous utilisons la fonction de sortie et de lui donner un code d'erreur.

906
01:11:03,020 --> 01:11:11,890
Alors voilà nous avons mis en valeur le terrain du nouveau nœud, son champ i soit égale à i, puis on le câbler.

907
01:11:11,890 --> 01:11:15,530
Nous avons mis en pointeur à côté du nouveau nœud de souligner tout d'abord,

908
01:11:15,530 --> 01:11:20,460
et puis la première va maintenant pointer vers le nouveau nœud.

909
01:11:20,460 --> 01:11:25,120
Ces premières lignes de code, nous sommes en train de construire le nouveau nœud.

910
01:11:25,120 --> 01:11:27,280
Pas les deux dernières lignes de cette fonction, mais les premiers.

911
01:11:27,280 --> 01:11:30,290
Vous pouvez effectivement sortir dans une fonction, dans une fonction d'assistance.

912
01:11:30,290 --> 01:11:32,560
C'est souvent ce que je fais, c'est que je le sortir dans une fonction,

913
01:11:32,560 --> 01:11:36,040
Je l'appelle quelque chose comme noeud de construction,

914
01:11:36,040 --> 01:11:40,410
et qui maintient la fonction prepend assez petit, il est à seulement 3 lignes-là.

915
01:11:40,410 --> 01:11:48,710
Je fais un appel à ma fonction de noeud de construction, et puis tout fils je vers le haut.

916
01:11:48,710 --> 01:11:51,970
>> La dernière chose que je veux vous montrer,

917
01:11:51,970 --> 01:11:54,030
et je vous laisse faire append et tout ce que vous-même,

918
01:11:54,030 --> 01:11:57,500
est de savoir comment itérer sur une liste.

919
01:11:57,500 --> 01:12:00,780
Il ya un tas de façons différentes pour itérer sur une liste.

920
01:12:00,780 --> 01:12:03,140
Dans ce cas, nous allons trouver la longueur d'une liste.

921
01:12:03,140 --> 01:12:06,570
Nous commençons donc avec une longueur = 0.

922
01:12:06,570 --> 01:12:11,580
Ceci est très similaire à l'écriture strlen pour une chaîne.

923
01:12:11,580 --> 01:12:17,780
C'est ce que je veux vous montrer, cette boucle for ici.

924
01:12:17,780 --> 01:12:23,530
Il ressemble un peu branché, ce n'est pas l'habitude int i = 0, i <que ce soit, i + +.

925
01:12:23,530 --> 01:12:34,920
Au lieu de cela il est l'initialisation de notre variable n comme le début de la liste.

926
01:12:34,920 --> 01:12:40,620
Et puis, alors que notre variable d'itération n'est pas nul, nous continuons.

927
01:12:40,620 --> 01:12:46,340
C'est parce que, par convention, la fin de notre liste sera considérée comme nulle.

928
01:12:46,340 --> 01:12:48,770
Et puis, pour incrémenter, plutôt que de faire + +,

929
01:12:48,770 --> 01:12:57,010
l'équivalent de liste chaînée + + est N = N-> suivante.

930
01:12:57,010 --> 01:13:00,410
>> Je vous laisse combler les lacunes ici parce que nous manquons de temps.

931
01:13:00,410 --> 01:13:09,300
Mais gardez cela à l'esprit lorsque vous travaillez sur vos psets spellr.

932
01:13:09,300 --> 01:13:11,650
Listes chaînées, si vous implémentez une table de hachage,

933
01:13:11,650 --> 01:13:14,010
va certainement se révéler très utiles.

934
01:13:14,010 --> 01:13:21,780
Et ayant cet idiome pour boucler sur les choses vont rendre la vie beaucoup plus facile, je l'espère.

935
01:13:21,780 --> 01:13:25,910
Pour toute question, rapidement?

936
01:13:25,910 --> 01:13:28,920
[Sam] Est-ce que vous envoyez le rempli sll et sc?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Ouais. Je vais envoyer des diapositives réalisées et pile sll rempli et queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]