1
00:00:00,000 --> 00:00:01,000
[Powered by Google Translate] [Article 6] [Plus confortable]

2
00:00:01,000 --> 00:00:04,000
[Rob Bowden] [Université de Harvard]

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

4
00:00:09,000 --> 00:00:11,000
>> Nous pouvons aller à notre section de questions.

5
00:00:11,000 --> 00:00:17,000
J'ai envoyé l'URL de l'espace avant.

6
00:00:17,000 --> 00:00:22,000
Le début de la section de questions-dire

7
00:00:22,000 --> 00:00:26,000
apparemment je ne suis pas entièrement unsick-est une question très facile

8
00:00:26,000 --> 00:00:28,000
de tout ce qui est valgrind?

9
00:00:28,000 --> 00:00:30,000
Qu'est-ce que valgrind faire?

10
00:00:30,000 --> 00:00:34,000
Quiconque veut dire quoi valgrind-ce pas?

11
00:00:34,000 --> 00:00:36,000
[Étudiant] Vérifie les fuites de mémoire.

12
00:00:36,000 --> 00:00:41,000
Ouais, valgrind est un contrôleur de mémoire générale.

13
00:00:41,000 --> 00:00:44,000
Il, à la fin, vous indique si vous avez des fuites de mémoire,

14
00:00:44,000 --> 00:00:49,000
qui est la plupart du temps ce que nous l'utilisons pour parce que si vous voulez

15
00:00:49,000 --> 00:00:54,000
bien dans l'ensemble problème ou si vous voulez

16
00:00:54,000 --> 00:00:59,000
obtenir sur le grand tableau, vous devez avoir aucune fuite de mémoire que ce soit,

17
00:00:59,000 --> 00:01:01,000
et dans le cas où vous avez une fuite de mémoire que vous ne pouvez pas trouver,

18
00:01:01,000 --> 00:01:04,000
également garder à l'esprit que chaque fois que vous ouvrez un fichier

19
00:01:04,000 --> 00:01:07,000
et si vous ne la fermez pas, c'est une fuite de mémoire.

20
00:01:07,000 --> 00:01:10,000
>> Beaucoup de gens sont à la recherche d'un nœud qu'ils ne sont pas en libérant

21
00:01:10,000 --> 00:01:15,000
alors qu'en réalité, ils n'ont pas fermé le dictionnaire dans la première étape.

22
00:01:15,000 --> 00:01:19,000
Il vous indique également si vous avez des invalides lit ou écrit,

23
00:01:19,000 --> 00:01:22,000
ce qui signifie que si vous essayez de définir une valeur

24
00:01:22,000 --> 00:01:26,000
c'est au-delà de la fin du tas et il ne se passe pas de la faute seg

25
00:01:26,000 --> 00:01:30,000
mais valgrind l'attrape, que vous ne devriez pas être fait par écrit là-bas,

26
00:01:30,000 --> 00:01:33,000
et si vous avez certainement ne devrait avoir aucun de ceux qui soit.

27
00:01:33,000 --> 00:01:38,000
Comment utilisez-vous valgrind?

28
00:01:38,000 --> 00:01:42,000
Comment utilisez-vous valgrind?

29
00:01:42,000 --> 00:01:45,000
>> C'est une question générale de

30
00:01:45,000 --> 00:01:49,000
sorte de l'exécuter et regardez la sortie.

31
00:01:49,000 --> 00:01:51,000
La sortie est accablant d'un grand nombre de fois.

32
00:01:51,000 --> 00:01:54,000
Il ya aussi des erreurs amusantes où, si vous avez quelque chose de terriblement mal

33
00:01:54,000 --> 00:01:59,000
passe dans une boucle, puis il finira par dire: «erreurs Beaucoup trop nombreux.

34
00:01:59,000 --> 00:02:03,000
Je vais arrêter de compter désormais. "

35
00:02:03,000 --> 00:02:08,000
Il s'agit essentiellement sortie textuelle que vous avez à analyser.

36
00:02:08,000 --> 00:02:13,000
En fin de compte, il vous indiquera les fuites de mémoire que vous avez,

37
00:02:13,000 --> 00:02:16,000
le nombre de blocs, ce qui peut être utile, car

38
00:02:16,000 --> 00:02:20,000
si c'est un unfreed bloc, alors il est plus facile de trouver

39
00:02:20,000 --> 00:02:23,000
de 1000 blocs unfreed.

40
00:02:23,000 --> 00:02:26,000
1000 blocs unfreed signifie probablement que vous n'êtes pas libérer

41
00:02:26,000 --> 00:02:30,000
vos listes liées de manière appropriée ou quelque chose.

42
00:02:30,000 --> 00:02:32,000
C'est valgrind.

43
00:02:32,000 --> 00:02:35,000
>> Maintenant, nous avons notre section de questions,

44
00:02:35,000 --> 00:02:38,000
dont vous n'avez pas besoin de télécharger.

45
00:02:38,000 --> 00:02:41,000
Vous pouvez cliquer sur mon nom et de les tirer vers le haut dans l'espace.

46
00:02:41,000 --> 00:02:44,000
Maintenant, cliquez sur moi.

47
00:02:44,000 --> 00:02:46,000
Révision 1 sera pile, ce qui nous faisons d'abord.

48
00:02:46,000 --> 00:02:55,000
Révision 2 sera la file d'attente, et la révision 3 sera la liste simplement chaînée.

49
00:02:55,000 --> 00:02:58,000
En partant avec notre pile.

50
00:02:58,000 --> 00:03:02,000
Comme il est dit ici, une pile est l'un des plus basique,

51
00:03:02,000 --> 00:03:07,000
structures de données fondamentales de l'informatique.

52
00:03:07,000 --> 00:03:11,000
L'exemple prototypique est très

53
00:03:11,000 --> 00:03:13,000
la pile de plateaux dans la salle à manger.

54
00:03:13,000 --> 00:03:16,000
Il s'agit en fait chaque fois que vous êtes présenté à une pile,

55
00:03:16,000 --> 00:03:20,000
quelqu'un va dire: «Oh, comme une pile de plateaux."

56
00:03:20,000 --> 00:03:22,000
Vous empilez les bacs vers le haut.

57
00:03:22,000 --> 00:03:24,000
Puis, quand vous allez tirer un plateau,

58
00:03:24,000 --> 00:03:31,000
le premier plateau qui a tiré se est le dernier qui a été mis sur la pile.

59
00:03:31,000 --> 00:03:34,000
La pile aussi, comme il est dit ci-

60
00:03:34,000 --> 00:03:37,000
nous avons le segment de mémoire appelé la pile.

61
00:03:37,000 --> 00:03:40,000
Et pourquoi est-il appelé la pile?

62
00:03:40,000 --> 00:03:42,000
>> Parce que, comme une structure de données pile,

63
00:03:42,000 --> 00:03:46,000
il apparaît des poussées et des cadres de pile sur la pile,

64
00:03:46,000 --> 00:03:53,000
où les cadres de pile sont comme un appel spécifique d'une fonction.

65
00:03:53,000 --> 00:03:57,000
Et comme une pile, vous aurez toujours de revenir

66
00:03:57,000 --> 00:04:03,000
à partir d'un appel de fonction avant de pouvoir descendre dans les cadres de pile baisse à nouveau.

67
00:04:03,000 --> 00:04:08,000
Vous ne pouvez pas avoir barre principale appel appel foo et bar retour directement principale.

68
00:04:08,000 --> 00:04:14,000
Il a toujours eu à suivre la pile en poussant correcte et popping.

69
00:04:14,000 --> 00:04:18,000
Les deux opérations, comme je l'ai dit, sont push et pop.

70
00:04:18,000 --> 00:04:20,000
Ce sont des termes universels.

71
00:04:20,000 --> 00:04:26,000
Vous devriez savoir push et pop en termes de piles, peu importe quoi.

72
00:04:26,000 --> 00:04:28,000
Nous allons voir les files d'attente sont un peu différentes.

73
00:04:28,000 --> 00:04:32,000
Il n'a pas vraiment un terme universel, mais push et pop sont universels pour les piles.

74
00:04:32,000 --> 00:04:34,000
Push est simplement placé sur la pile.

75
00:04:34,000 --> 00:04:37,000
Pop, c'est de prendre de la pile.

76
00:04:37,000 --> 00:04:43,000
Et nous voyons ici, nous avons notre pile typedef struct,

77
00:04:43,000 --> 00:04:46,000
nous avons donc chevalier cordes **.

78
00:04:46,000 --> 00:04:51,000
Ne soyez pas effrayés par tout **.

79
00:04:51,000 --> 00:04:54,000
Cela va finir par être un tableau de chaînes

80
00:04:54,000 --> 00:04:58,000
ou un tableau de pointeurs de caractères, où

81
00:04:58,000 --> 00:05:00,000
pointeurs vers les personnages ont tendance à être des chaînes.

82
00:05:00,000 --> 00:05:05,000
Il n'a pas besoin d'être des chaînes, mais ici, ils vont être des chaînes.

83
00:05:05,000 --> 00:05:08,000
>> Nous avons un tableau de chaînes.

84
00:05:08,000 --> 00:05:14,000
Nous disposons d'une taille, ce qui représente le nombre d'éléments sont actuellement dans la pile,

85
00:05:14,000 --> 00:05:19,000
et puis nous avons la capacité, qui est le nombre d'éléments peuvent être sur la pile.

86
00:05:19,000 --> 00:05:22,000
La capacité devrait commencer comme quelque chose de plus grand que 1,

87
00:05:22,000 --> 00:05:27,000
mais la taille va commencer à 0.

88
00:05:27,000 --> 00:05:36,000
Maintenant, il ya essentiellement trois façons différentes que vous pouvez penser d'une pile.

89
00:05:36,000 --> 00:05:39,000
Eh bien, il ya probablement plus, mais les deux principaux moyens sont

90
00:05:39,000 --> 00:05:43,000
vous pouvez le mettre en œuvre à l'aide d'un tableau, ou vous pouvez le mettre en œuvre en utilisant une liste chaînée.

91
00:05:43,000 --> 00:05:48,000
Listes chaînées sont un peu trivial de réaliser des empilements de.

92
00:05:48,000 --> 00:05:51,000
Il est très facile de faire une pile en utilisant les listes chaînées,

93
00:05:51,000 --> 00:05:55,000
Donc, ici, nous allons faire une pile en utilisant des tableaux,

94
00:05:55,000 --> 00:05:59,000
puis en utilisant les tableaux, il ya aussi deux façons que vous pouvez penser à ce sujet.

95
00:05:59,000 --> 00:06:01,000
Avant, quand je l'ai dit, nous avons une capacité de la pile,

96
00:06:01,000 --> 00:06:04,000
afin que nous puissions répondre à un élément de la pile.

97
00:06:04,000 --> 00:06:09,000
>> La manière dont on pourrait arriver, c'est que dès que vous touchez 10 éléments, puis vous avez terminé.

98
00:06:09,000 --> 00:06:13,000
Vous savez peut-être qu'il ya une limite supérieure de 10 choses dans le monde

99
00:06:13,000 --> 00:06:16,000
que vous n'aurez jamais plus de 10 choses sur votre pile,

100
00:06:16,000 --> 00:06:20,000
Dans ce cas, vous pouvez avoir une borne supérieure sur la taille de votre stack.

101
00:06:20,000 --> 00:06:23,000
Ou vous pourriez avoir votre pile sera sans bornes,

102
00:06:23,000 --> 00:06:27,000
mais si vous faites un tableau, ce qui signifie que chaque fois que vous frappez 10 éléments,

103
00:06:27,000 --> 00:06:29,000
alors vous allez devoir passer à 20 éléments, et quand vous frappez 20 éléments,

104
00:06:29,000 --> 00:06:33,000
vous allez avoir à faire croître votre tableau à 30 éléments ou 40 éléments.

105
00:06:33,000 --> 00:06:37,000
Vous allez avoir besoin d'augmenter la capacité, qui est ce que nous allons faire ici.

106
00:06:37,000 --> 00:06:40,000
Chaque fois que nous arrivons à la taille maximale de notre pile,

107
00:06:40,000 --> 00:06:46,000
quand nous pousser quelque chose d'autre, nous allons avoir besoin d'augmenter la capacité.

108
00:06:46,000 --> 00:06:50,000
Ici, nous avons bouton poussoir déclaré bool (char * str).

109
00:06:50,000 --> 00:06:54,000
Str char * est la chaîne qui nous pousse sur la pile,

110
00:06:54,000 --> 00:06:58,000
et bool dit juste si nous avons réussi ou échoué.

111
00:06:58,000 --> 00:07:00,000
>> Comment pouvons-nous échouer?

112
00:07:00,000 --> 00:07:04,000
Qu'est-ce que la seule circonstance que vous pouvez penser

113
00:07:04,000 --> 00:07:07,000
où nous aurions besoin de retourner faux?

114
00:07:07,000 --> 00:07:09,000
Ouais.

115
00:07:09,000 --> 00:07:12,000
[Étudiants] Si elle est pleine et nous utilisons une application bornée.

116
00:07:12,000 --> 00:07:17,000
Ouais, alors comment pouvons-nous définir-il répondu

117
00:07:17,000 --> 00:07:23,000
si elle est pleine et nous utilisons une application bornée.

118
00:07:23,000 --> 00:07:26,000
Ensuite, nous reviendrons assurément faux.

119
00:07:26,000 --> 00:07:31,000
Dès que nous avons atteint 10 choses dans le tableau, nous ne pouvons pas répondre à 11, donc on retourne faux.

120
00:07:31,000 --> 00:07:32,000
Et si ce n'est pas borné? Ouais.

121
00:07:32,000 --> 00:07:38,000
Si vous ne pouvez pas développer le réseau pour une raison quelconque.

122
00:07:38,000 --> 00:07:43,000
Ouais, et alors la mémoire est une ressource limitée,

123
00:07:43,000 --> 00:07:51,000
et finalement, si nous gardons les choses qui poussent sur la pile, encore et encore,

124
00:07:51,000 --> 00:07:54,000
nous allons essayer et d'allouer un tampon plus grand pour s'adapter

125
00:07:54,000 --> 00:07:59,000
la plus grande capacité, et malloc ou quoi que nous utilisons va renvoyer false.

126
00:07:59,000 --> 00:08:02,000
Eh bien, malloc retourne null.

127
00:08:02,000 --> 00:08:05,000
>> Rappelez-vous, chaque fois que vous jamais appeler malloc, vous devriez vérifier pour voir si elle

128
00:08:05,000 --> 00:08:12,000
renvoie la valeur null ou bien c'est une déduction correcte.

129
00:08:12,000 --> 00:08:17,000
Puisque nous voulons avoir une pile infinie,

130
00:08:17,000 --> 00:08:21,000
le seul cas que nous allons être de retour est faux si nous essayons de

131
00:08:21,000 --> 00:08:26,000
accroître la capacité et malloc ou quoi renvoie false.

132
00:08:26,000 --> 00:08:30,000
Puis pop ne prend aucun argument,

133
00:08:30,000 --> 00:08:37,000
et il renvoie la chaîne qui se trouve sur le dessus de la pile.

134
00:08:37,000 --> 00:08:41,000
Quels qu'aient été les plus récemment poussé sur la pile est ce que la pop est de retour,

135
00:08:41,000 --> 00:08:44,000
et il a également le retire de la pile.

136
00:08:44,000 --> 00:08:50,000
Et remarquez qu'il retourne null s'il n'y a rien sur la pile.

137
00:08:50,000 --> 00:08:53,000
Il est toujours possible que la pile est vide.

138
00:08:53,000 --> 00:08:55,000
En Java, si vous êtes habitué à cela, ou d'autres langues,

139
00:08:55,000 --> 00:09:01,000
essayent d'éclater à partir d'une pile vide peut provoquer une exception ou quelque chose.

140
00:09:01,000 --> 00:09:09,000
>> Mais en C, null est une sorte de grand nombre de cas, la façon dont nous traitons ces problèmes.

141
00:09:09,000 --> 00:09:13,000
Retournant une valeur null est de savoir comment nous allons indiquer que la pile est vide.

142
00:09:13,000 --> 00:09:16,000
Nous avons fourni un code qui permettra de tester les fonctionnalités de votre pile, le

143
00:09:16,000 --> 00:09:19,000
mettre en œuvre push et pop.

144
00:09:19,000 --> 00:09:23,000
Ce ne sera pas une grande quantité de code.

145
00:09:23,000 --> 00:09:40,000
Je le ferai-réalité, avant de faire cela, hint, hint-

146
00:09:40,000 --> 00:09:44,000
si vous ne l'avez pas vu, malloc n'est pas la seule fonction

147
00:09:44,000 --> 00:09:47,000
qui alloue la mémoire sur le tas pour vous.

148
00:09:47,000 --> 00:09:51,000
Il ya une famille de fonctions alloc.

149
00:09:51,000 --> 00:09:53,000
La première est malloc, que vous êtes habitué.

150
00:09:53,000 --> 00:09:56,000
Ensuite, il ya calloc, qui fait la même chose que malloc,

151
00:09:56,000 --> 00:09:59,000
mais il se met à zéro tout pour vous.

152
00:09:59,000 --> 00:10:04,000
Si vous avez toujours voulu tout mettre à null après allouer de quelque chose

153
00:10:04,000 --> 00:10:06,000
vous devriez venez d'utiliser calloc en premier lieu au lieu d'écrire

154
00:10:06,000 --> 00:10:09,000
une boucle for à zéro sur l'ensemble du bloc de mémoire.

155
00:10:09,000 --> 00:10:15,000
>> Realloc est comme malloc et a beaucoup de cas particuliers,

156
00:10:15,000 --> 00:10:19,000
mais, fondamentalement, ce qui ne fait que realloc

157
00:10:19,000 --> 00:10:24,000
il prend un pointeur qui avaient déjà été alloués.

158
00:10:24,000 --> 00:10:27,000
Realloc est la fonction que vous voulez prêter attention à ici.

159
00:10:27,000 --> 00:10:31,000
Il prend un pointeur qui avait déjà été renvoyé par malloc.

160
00:10:31,000 --> 00:10:35,000
Disons que vous demandez à malloc un pointeur de 10 octets.

161
00:10:35,000 --> 00:10:38,000
Puis, plus tard vous vous rendez compte que vous vouliez 20 octets,

162
00:10:38,000 --> 00:10:42,000
si vous appelez realloc sur ce pointeur de 20 octets,

163
00:10:42,000 --> 00:10:47,000
et realloc automatiquement copier tout pour vous.

164
00:10:47,000 --> 00:10:51,000
Si vous venez d'appeler malloc encore une fois, comme je l'ai un bloc de 10 octets.

165
00:10:51,000 --> 00:10:53,000
Maintenant, j'ai besoin d'un bloc de 20 octets,

166
00:10:53,000 --> 00:10:58,000
donc si je malloc 20 octets, alors je dois copier manuellement au cours des 10 octets à partir de la première chose

167
00:10:58,000 --> 00:11:01,000
dans la deuxième chose, puis la première chose gratuitement.

168
00:11:01,000 --> 00:11:04,000
Realloc se chargera pour vous.

169
00:11:04,000 --> 00:11:11,000
>> Notez la signature va être void *,

170
00:11:11,000 --> 00:11:15,000
qui est juste en renvoyant un pointeur vers le bloc de mémoire,

171
00:11:15,000 --> 00:11:17,000
puis void * ptr.

172
00:11:17,000 --> 00:11:22,000
Vous pouvez penser void * comme un pointeur générique.

173
00:11:22,000 --> 00:11:27,000
En règle générale, vous n'avez jamais traiter avec void *,

174
00:11:27,000 --> 00:11:30,000
mais malloc retourne un void *, puis il est juste utilisé comme

175
00:11:30,000 --> 00:11:34,000
ce qui se passe réellement comme un char *.

176
00:11:34,000 --> 00:11:37,000
Le void * précédent, qui avait été renvoyée par malloc

177
00:11:37,000 --> 00:11:41,000
va maintenant être transmis à realloc, puis la taille

178
00:11:41,000 --> 00:11:49,000
est le nouveau numéro d'octets que vous souhaitez allouer, de sorte que votre nouvelle capacité.

179
00:11:49,000 --> 00:11:57,000
Je vais vous donner quelques minutes, et de le faire dans notre espace.

180
00:11:57,000 --> 00:12:02,000
Commencez avec la révision 1.

181
00:12:16,000 --> 00:12:21,000
Je vous arrête, après espérons propos de suffisamment de temps pour mettre en œuvre poussoir,

182
00:12:21,000 --> 00:12:24,000
et puis je vais vous donner une autre pause pour faire pop.

183
00:12:24,000 --> 00:12:27,000
Mais ce n'est vraiment pas ce code beaucoup à tous.

184
00:12:27,000 --> 00:12:35,000
La plupart du code est sans doute le truc en expansion, expansion de la capacité.

185
00:12:35,000 --> 00:12:39,000
Ok, pas de pression pour être complètement terminé,

186
00:12:39,000 --> 00:12:47,000
mais aussi longtemps que vous vous sentez comme vous êtes sur la bonne voie, c'est bien.

187
00:12:47,000 --> 00:12:53,000
>> Quelqu'un at-il un code qu'ils se sentent à l'aise avec moi tirant vers le haut?

188
00:12:53,000 --> 00:12:59,000
Ouais, je le ferai, mais quelqu'un at-il un code que je peux tirer vers le haut?

189
00:12:59,000 --> 00:13:05,000
Ok, pouvez-vous commencer, sauvegardez, quel qu'il soit?

190
00:13:05,000 --> 00:13:09,000
J'oublie toujours cette étape.

191
00:13:09,000 --> 00:13:15,000
Bon, en regardant pousser,

192
00:13:15,000 --> 00:13:18,000
voulez-vous expliquer votre code?

193
00:13:18,000 --> 00:13:24,000
[Étudiants] Tout d'abord, j'ai augmenté la taille.

194
00:13:24,000 --> 00:13:28,000
Je suppose que je devrais peut-être que, de toute façon, j'ai augmenté la taille,

195
00:13:28,000 --> 00:13:31,000
et je vois si elle est inférieure à la capacité.

196
00:13:31,000 --> 00:13:36,000
Et si elle est inférieure à la capacité, je ajouter dans le tableau que nous avons déjà.

197
00:13:36,000 --> 00:13:42,000
Et si ce n'est pas le cas, je multiplie la capacité par 2,

198
00:13:42,000 --> 00:13:50,000
et je réaffecter l'ensemble des chaînes à quelque chose avec une taille plus grande capacité actuellement.

199
00:13:50,000 --> 00:13:55,000
Et puis, s'il échoue, je dis à l'utilisateur et retourner false,

200
00:13:55,000 --> 00:14:04,000
et si tout va bien, puis j'ai mis la chaîne dans le nouveau spot.

201
00:14:04,000 --> 00:14:07,000
>> [Rob B.] Notez également que nous avons utilisé un opérateur bit à bit agréable ici

202
00:14:07,000 --> 00:14:09,000
à multiplier par 2.

203
00:14:09,000 --> 00:14:11,000
Rappelez-vous, décalage à gauche est toujours va être multiplié par 2.

204
00:14:11,000 --> 00:14:15,000
Décalage vers la droite est divisée par 2 tant que vous vous souvenez que cela signifie

205
00:14:15,000 --> 00:14:18,000
diviser par 2 comme dans un entier divisé par 2.

206
00:14:18,000 --> 00:14:20,000
Il pourrait tronquer un 1 ici ou là.

207
00:14:20,000 --> 00:14:26,000
Mais décalage à gauche de 1 est toujours va être multiplié par 2,

208
00:14:26,000 --> 00:14:32,000
à moins que vous déborder les limites de l'entier, et alors il ne sera pas.

209
00:14:32,000 --> 00:14:34,000
Une remarque.

210
00:14:34,000 --> 00:14:39,000
J'aime faire-cela ne va pas changer le codage d'une manière quelconque,

211
00:14:39,000 --> 00:14:48,000
mais je voudrais faire quelque chose comme ça.

212
00:14:48,000 --> 00:14:51,000
Il va réellement se rendre un peu plus longtemps.

213
00:15:04,000 --> 00:15:08,000
Peut-être que ce n'est pas le cas parfait pour le montrer,

214
00:15:08,000 --> 00:15:14,000
mais je tiens à le segmenter en ces blocs de-

215
00:15:14,000 --> 00:15:17,000
ok, si ce qui se passe si, alors je vais faire quelque chose,

216
00:15:17,000 --> 00:15:19,000
puis la fonction est réalisée.

217
00:15:19,000 --> 00:15:22,000
Je n'ai pas besoin de faire défiler, puis mes yeux tout le long de la fonction

218
00:15:22,000 --> 00:15:25,000
pour voir ce qui se passe après l'autre.

219
00:15:25,000 --> 00:15:27,000
C'est le cas de ce qui se passe si, alors je viens de revenir.

220
00:15:27,000 --> 00:15:30,000
Il a également l'avantage bien agréable de tout au-delà de ce

221
00:15:30,000 --> 00:15:33,000
est maintenant décalé vers la gauche une fois.

222
00:15:33,000 --> 00:15:40,000
Je n'ai plus besoin à proximité si vous avez déjà ridiculement longues files d'attente,

223
00:15:40,000 --> 00:15:45,000
alors ces 4 octets peut vous aider, ainsi que la gauche est quelque chose de plus,

224
00:15:45,000 --> 00:15:48,000
le moins accablé si vous vous sentez comme-bien, je dois me rappeler

225
00:15:48,000 --> 00:15:53,000
Je suis actuellement dans une boucle while à l'intérieur d'une autre à l'intérieur d'une boucle for.

226
00:15:53,000 --> 00:15:58,000
Partout où vous pouvez faire ce retour tout de suite, j'aime bien.

227
00:15:58,000 --> 00:16:05,000
Il est totalement facultative et ne devrait en aucune façon.

228
00:16:05,000 --> 00:16:12,000
>> [Étudiants] Faut-il une taille - dans l'état sûr?

229
00:16:12,000 --> 00:16:19,000
La condition est sûr ici nous n'avons pas réussi à realloc, alors oui.

230
00:16:19,000 --> 00:16:22,000
Remarquez comment dans l'état sûr, sans doute,

231
00:16:22,000 --> 00:16:26,000
à moins que nous des trucs gratuits plus tard, nous sommes toujours voué à l'échec

232
00:16:26,000 --> 00:16:29,000
peu importe combien de fois nous essayons de pousser quelque chose.

233
00:16:29,000 --> 00:16:32,000
Si nous continuons à pousser, nous gardons la taille d'incrémentation,

234
00:16:32,000 --> 00:16:36,000
même si nous ne mettons pas tout sur la pile.

235
00:16:36,000 --> 00:16:39,000
Habituellement, nous ne incrémenter la taille jusqu'à ce

236
00:16:39,000 --> 00:16:43,000
après nous avons réussi à le mettre sur la pile.

237
00:16:43,000 --> 00:16:50,000
Nous le ferions, par exemple, que ce soit ici et ici.

238
00:16:50,000 --> 00:16:56,000
Et puis, au lieu de dire s.size capacité ≤, c'est moins de capacité,

239
00:16:56,000 --> 00:17:01,000
seulement parce que nous nous sommes déplacés où tout était.

240
00:17:01,000 --> 00:17:07,000
>> Et rappelez-vous, le seul endroit où nous pourrions retourner faux

241
00:17:07,000 --> 00:17:14,000
C'est ici, où realloc retourné null,

242
00:17:14,000 --> 00:17:19,000
et s'il vous arrive de se rappeler d'erreur standard,

243
00:17:19,000 --> 00:17:22,000
peut-être vous pourriez envisager ce cas, un endroit où vous voulez imprimer une erreur-type,

244
00:17:22,000 --> 00:17:26,000
stderr afin fprintf au lieu de simplement imprimer directement sur la sortie standard.

245
00:17:26,000 --> 00:17:31,000
Encore une fois, ce n'est pas une attente, mais si c'est une erreur,

246
00:17:31,000 --> 00:17:41,000
tapez printf, alors vous voudrez peut-être faire imprimer sur la sortie standard au lieu de la sortie standard.

247
00:17:41,000 --> 00:17:44,000
>> Quelqu'un at-il autre chose à noter? Oui.

248
00:17:44,000 --> 00:17:47,000
[Étudiants] Pouvez-vous revenir sur la [inaudible]?

249
00:17:47,000 --> 00:17:55,000
[Rob B.] Oui, le caractère binaire réelle de celui-ci ou tout simplement ce que c'est?

250
00:17:55,000 --> 00:17:57,000
[Étudiants] Donc, vous le multipliez par 2?

251
00:17:57,000 --> 00:17:59,000
[Rob B.] Ouais, en gros.

252
00:17:59,000 --> 00:18:11,000
Dans la terre binaire, nous avons toujours notre série de chiffres.

253
00:18:11,000 --> 00:18:22,000
Le passage de cette gauche de 1 Fondamentalement, il insère ici sur le côté droit.

254
00:18:22,000 --> 00:18:25,000
Retour à cela, il suffit de se rappeler que tout en binaire

255
00:18:25,000 --> 00:18:28,000
est une puissance de 2, cela représente donc 2 au 0,

256
00:18:28,000 --> 00:18:30,000
2 à la présente 1, 2 présente au 2.

257
00:18:30,000 --> 00:18:33,000
En insérant un 0 à droite maintenant, nous venons de passer tout entier.

258
00:18:33,000 --> 00:18:38,000
Ce qui était de 2 à 0 est maintenant 2 à 1, est 2 à la 2.

259
00:18:38,000 --> 00:18:41,000
Le côté droit que nous avons inséré

260
00:18:41,000 --> 00:18:44,000
va nécessairement être égal à 0,

261
00:18:44,000 --> 00:18:46,000
ce qui est logique.

262
00:18:46,000 --> 00:18:49,000
Si jamais vous multiplier un nombre par 2, ça ne va pas finir impair,

263
00:18:49,000 --> 00:18:54,000
de sorte que le 2 à la place 0 doit être égal à 0,

264
00:18:54,000 --> 00:18:59,000
et c'est ce que j'ai mis en garde contre moitié avant est que si vous ne vous arrive de passer

265
00:18:59,000 --> 00:19:01,000
au-delà du nombre de bits dans un entier,

266
00:19:01,000 --> 00:19:04,000
alors ce 1 va finir par s'éteindre.

267
00:19:04,000 --> 00:19:10,000
C'est le seul souci s'il vous arrive d'avoir affaire avec des capacités très grandes.

268
00:19:10,000 --> 00:19:15,000
Mais à ce moment, alors vous avez affaire à un tableau de milliards de choses,

269
00:19:15,000 --> 00:19:25,000
qui pourrait ne pas tenir dans la mémoire de toute façon.

270
00:19:25,000 --> 00:19:31,000
>> Maintenant, nous pouvons arriver à la pop, ce qui est encore plus facile.

271
00:19:31,000 --> 00:19:36,000
Vous pouvez faire comme si vous arrive d'apparaître tout un tas,

272
00:19:36,000 --> 00:19:38,000
et maintenant vous êtes à la moitié de sa capacité à nouveau.

273
00:19:38,000 --> 00:19:42,000
Vous pouvez realloc pour réduire la quantité de mémoire dont vous disposez,

274
00:19:42,000 --> 00:19:47,000
mais vous n'avez pas à vous soucier de ce que, si le cas realloc ne sera

275
00:19:47,000 --> 00:19:50,000
de plus en plus de mémoire, jamais rétrécissement de la mémoire,

276
00:19:50,000 --> 00:19:59,000
qui va faire pop super-facile.

277
00:19:59,000 --> 00:20:02,000
Maintenant, les files d'attente qui vont être comme des piles,

278
00:20:02,000 --> 00:20:06,000
mais l'ordre dans lequel vous prenez les choses est inversé.

279
00:20:06,000 --> 00:20:10,000
L'exemple type d'une file d'attente est une ligne,

280
00:20:10,000 --> 00:20:12,000
donc je suppose que si vous étiez en anglais, je vous aurais dit

281
00:20:12,000 --> 00:20:17,000
un exemple type d'une file d'attente est une file d'attente.

282
00:20:17,000 --> 00:20:22,000
Donc, comme une ligne, si vous êtes la première personne en ligne,

283
00:20:22,000 --> 00:20:24,000
vous vous attendez à être la première personne hors de la ligne.

284
00:20:24,000 --> 00:20:31,000
Si vous êtes la dernière personne en ligne, vous allez être la dernière personne desservie.

285
00:20:31,000 --> 00:20:35,000
Nous appelons ce modèle FIFO, alors que la pile LIFO est tendance.

286
00:20:35,000 --> 00:20:40,000
Ces mots sont assez universel.

287
00:20:40,000 --> 00:20:46,000
>> Comme les piles et au contraire des tableaux, des files d'attente, généralement, ne permettent pas l'accès aux éléments du milieu.

288
00:20:46,000 --> 00:20:50,000
Ici, une pile, nous avons push et pop.

289
00:20:50,000 --> 00:20:54,000
Ici, il nous arrive d'avoir appelé les enqueue et dequeue.

290
00:20:54,000 --> 00:20:58,000
J'ai aussi entendu les appelait changement et unshift.

291
00:20:58,000 --> 00:21:02,000
J'ai entendu des gens dire push et pop pour s'appliquer également aux files d'attente.

292
00:21:02,000 --> 00:21:05,000
J'ai entendu insérer, supprimer,

293
00:21:05,000 --> 00:21:11,000
de sorte push et pop, si vous parlez des piles, vous poussez et popping.

294
00:21:11,000 --> 00:21:16,000
Si vous parlez de files d'attente, vous pouvez choisir les mots que vous souhaitez utiliser

295
00:21:16,000 --> 00:21:23,000
pour l'insertion et le retrait, et il n'y a pas de consensus sur ce que devrait être appelé.

296
00:21:23,000 --> 00:21:27,000
Mais ici, nous avons enqueue et dequeue.

297
00:21:27,000 --> 00:21:37,000
Maintenant, la structure est presque identique à la structure de la pile.

298
00:21:37,000 --> 00:21:40,000
Mais nous devons garder la trace de la tête.

299
00:21:40,000 --> 00:21:44,000
Je suppose que c'est dit ici, mais pourquoi avons-nous besoin de la tête?

300
00:21:53,000 --> 00:21:57,000
Les prototypes sont fondamentalement identiques à pousser et pop.

301
00:21:57,000 --> 00:21:59,000
Vous pouvez penser que c'est push et pop.

302
00:21:59,000 --> 00:22:08,000
La seule différence est la pop est de retour au lieu de la dernière, il est le premier retour.

303
00:22:08,000 --> 00:22:12,000
2, 1, 3, 4, ou quelque chose.

304
00:22:12,000 --> 00:22:14,000
Et voici le début.

305
00:22:14,000 --> 00:22:17,000
Notre file d'attente est pleine, il ya donc quatre éléments qu'il contient.

306
00:22:17,000 --> 00:22:21,000
La fin de notre file d'attente est actuellement de 2,

307
00:22:21,000 --> 00:22:24,000
et maintenant nous allons insérer quelque chose d'autre.

308
00:22:24,000 --> 00:22:29,000
>> Quand on veut insérer cette autre chose, ce que nous avons fait pour la version pile

309
00:22:29,000 --> 00:22:36,000
est nous avons étendu notre bloc de mémoire.

310
00:22:36,000 --> 00:22:40,000
Quel est le problème avec ça?

311
00:22:40,000 --> 00:22:45,000
[Étudiants] Vous déplacez le 2.

312
00:22:45,000 --> 00:22:51,000
Ce que j'ai dit avant sur la fin de la file d'attente,

313
00:22:51,000 --> 00:22:57,000
ce n'est pas logique que nous commencions à 1,

314
00:22:57,000 --> 00:23:01,000
alors nous voulons dequeue 1, puis dequeue 3, puis dequeue 4,

315
00:23:01,000 --> 00:23:05,000
puis dequeue 2, puis dequeue celui-ci.

316
00:23:05,000 --> 00:23:08,000
Nous ne pouvons pas utiliser realloc maintenant,

317
00:23:08,000 --> 00:23:11,000
ou à tout le moins, vous devez utiliser realloc d'une manière différente.

318
00:23:11,000 --> 00:23:15,000
Mais vous ne devriez pas simplement utiliser realloc.

319
00:23:15,000 --> 00:23:18,000
Vous allez avoir à copier manuellement votre mémoire.

320
00:23:18,000 --> 00:23:21,000
>> Il ya deux fonctions pour copier la mémoire.

321
00:23:21,000 --> 00:23:25,000
Il ya memcopy et memmove.

322
00:23:25,000 --> 00:23:29,000
Je suis en train de lire les pages de manuel pour trouver celui qui vous allez avoir à utiliser.

323
00:23:29,000 --> 00:23:35,000
Bon, memcopy, la différence est

324
00:23:35,000 --> 00:23:38,000
que memcopy et memmove, on manipule correctement le cas

325
00:23:38,000 --> 00:23:41,000
où vous voulez copier dans une région qui se trouve à chevaucher la région

326
00:23:41,000 --> 00:23:46,000
vous copiez à partir.

327
00:23:46,000 --> 00:23:50,000
Memcopy ne pas y faire face. Memmove fait.

328
00:23:50,000 --> 00:23:59,000
Vous pouvez penser que le problème-

329
00:23:59,000 --> 00:24:09,000
disons que je veux copier ce gars-là,

330
00:24:09,000 --> 00:24:13,000
ces quatre à ce gars-dessus.

331
00:24:13,000 --> 00:24:16,000
En fin de compte, ce que le tableau devrait ressembler à

332
00:24:16,000 --> 00:24:26,000
une fois la copie 2, 1, 2, 1, 3, 4, puis des trucs à la fin.

333
00:24:26,000 --> 00:24:29,000
Mais cela dépend de l'ordre dans lequel nous avons fait copier,

334
00:24:29,000 --> 00:24:32,000
car si nous ne considérons pas le fait que la région nous copier dans

335
00:24:32,000 --> 00:24:35,000
chevauche celui que nous la copie de son

336
00:24:35,000 --> 00:24:46,000
alors nous pourrions faire comme début ici, copier les 2 dans l'endroit où nous voulons aller,

337
00:24:46,000 --> 00:24:52,000
puis déplacez les pointeurs vers l'avant.

338
00:24:52,000 --> 00:24:56,000
>> Maintenant, nous allons être ici et ici, et maintenant nous voulons copier

339
00:24:56,000 --> 00:25:04,000
ce mec sur ce gars et faire avancer nos pointeurs vers l'avant.

340
00:25:04,000 --> 00:25:07,000
Ce que nous allons finir par avoir est de 2, 1, 2, 1, 2, 1

341
00:25:07,000 --> 00:25:10,000
au lieu de la 2 appropriée, 1, 2, 1, 3, 4, car

342
00:25:10,000 --> 00:25:15,000
2, 1 emportait sur l'original 3, 4.

343
00:25:15,000 --> 00:25:19,000
Memmove gère cela correctement.

344
00:25:19,000 --> 00:25:23,000
Dans ce cas, fondamentalement juste toujours utiliser memmove

345
00:25:23,000 --> 00:25:26,000
parce qu'il le gère correctement.

346
00:25:26,000 --> 00:25:29,000
Il n'est généralement pas effectuer de pire.

347
00:25:29,000 --> 00:25:32,000
L'idée est plutôt de partir de début et la copie de cette façon

348
00:25:32,000 --> 00:25:35,000
comme nous venons de faire ici, il commence à partir de la fin et copie dans,

349
00:25:35,000 --> 00:25:38,000
et dans ce cas, vous ne pouvez jamais avoir un problème.

350
00:25:38,000 --> 00:25:40,000
Il n'existe pas de perte de performance.

351
00:25:40,000 --> 00:25:47,000
Toujours utiliser memmove. Ne vous souciez plus memcopy.

352
00:25:47,000 --> 00:25:51,000
Et c'est là que vous allez devoir séparément Memmove

353
00:25:51,000 --> 00:26:01,000
la portion enroulée autour de votre-file d'attente.

354
00:26:01,000 --> 00:26:04,000
Pas de soucis si elle n'est pas complètement terminé.

355
00:26:04,000 --> 00:26:10,000
C'est plus difficile que pile, push et pop.

356
00:26:10,000 --> 00:26:15,000
>> N'importe qui ont n'importe quel code on pouvait travailler avec?

357
00:26:15,000 --> 00:26:21,000
Même si complètement incomplète?

358
00:26:21,000 --> 00:26:23,000
[Étudiants] Oui, c'est tout à fait incomplète, cependant.

359
00:26:23,000 --> 00:26:27,000
Complètement incomplet est très bien tant que nous, on peut économiser de la révision?

360
00:26:27,000 --> 00:26:32,000
J'ai oublier que chaque fois unique.

361
00:26:32,000 --> 00:26:39,000
Bon, ignorant ce qui se passe quand nous avons besoin de redimensionner les choses.

362
00:26:39,000 --> 00:26:42,000
Ignorer complètement redimensionnement.

363
00:26:42,000 --> 00:26:49,000
Expliquez ce code.

364
00:26:49,000 --> 00:26:54,000
Je vérifie tout d'abord si la taille est inférieure à la première copie de tous les

365
00:26:54,000 --> 00:27:01,000
et puis après ça, je insérez-je prendre la tête + taille,

366
00:27:01,000 --> 00:27:05,000
et je m'assure qu'il s'enroule autour de la capacité de la matrice,

367
00:27:05,000 --> 00:27:08,000
et je insérer la nouvelle chaîne à cette position.

368
00:27:08,000 --> 00:27:12,000
Puis-je augmenter la taille et renvoie true.

369
00:27:12,000 --> 00:27:22,000
>> [Rob B.] C'est certainement l'un de ces cas où vous allez vouloir utiliser mod.

370
00:27:22,000 --> 00:27:25,000
Tout type de cas où vous avez enroulant autour, si vous pensez enroulant autour,

371
00:27:25,000 --> 00:27:29,000
la pensée immédiate devrait être mod.

372
00:27:29,000 --> 00:27:36,000
Comme une optimisation rapide / rendre votre code une ligne plus courte,

373
00:27:36,000 --> 00:27:42,000
vous remarquerez que la ligne qui suit immédiatement celui-ci

374
00:27:42,000 --> 00:27:53,000
est juste la taille + +, donc vous fusionnez que dans cette ligne, la taille + +.

375
00:27:53,000 --> 00:27:58,000
Maintenant, ici-bas, nous avons le cas

376
00:27:58,000 --> 00:28:01,000
où nous n'avons pas assez de mémoire,

377
00:28:01,000 --> 00:28:05,000
si nous augmentons notre capacité de 2.

378
00:28:05,000 --> 00:28:09,000
Je suppose que vous pourriez avoir le même problème ici, mais nous pouvons l'ignorer maintenant,

379
00:28:09,000 --> 00:28:13,000
où si vous n'avez pas d'augmenter votre capacité,

380
00:28:13,000 --> 00:28:18,000
alors vous allez avoir à diminuer votre capacité de 2 à nouveau.

381
00:28:18,000 --> 00:28:24,000
Une autre brève note est juste comme vous pouvez le faire + =,

382
00:28:24,000 --> 00:28:30,000
vous pouvez également faire << =.

383
00:28:30,000 --> 00:28:43,000
Presque tout peut aller devant égaux, + =, | =, & =, << =.

384
00:28:43,000 --> 00:28:52,000
Char * nouveau, c'est notre nouveau bloc de mémoire.

385
00:28:52,000 --> 00:28:55,000
Oh, là-bas.

386
00:28:55,000 --> 00:29:02,000
>> Qu'est-ce que les gens pensent au sujet du type de notre nouveau bloc de mémoire?

387
00:29:02,000 --> 00:29:06,000
[Étudiants] Il devrait être char **.

388
00:29:06,000 --> 00:29:12,000
En repensant à notre structure ici,

389
00:29:12,000 --> 00:29:14,000
cordes est ce que nous réaffectation.

390
00:29:14,000 --> 00:29:21,000
Nous faisons un ensemble de stockage nouvelle dynamique pour les éléments dans la file d'attente.

391
00:29:21,000 --> 00:29:25,000
Ce que nous allons attribuer à vos chaînes est ce que nous allouer de ce moment,

392
00:29:25,000 --> 00:29:30,000
et si nouvelle va être de type char **.

393
00:29:30,000 --> 00:29:34,000
Il va y avoir un tableau de chaînes.

394
00:29:34,000 --> 00:29:38,000
Alors quel est le cas en vertu de laquelle nous allons revenir faux?

395
00:29:38,000 --> 00:29:41,000
[Étudiants] Devrions-nous faire la char *?

396
00:29:41,000 --> 00:29:44,000
[Rob B.] Oui, bonne idée.

397
00:29:44,000 --> 00:29:46,000
[Étudiants] Qu'est-ce que c'était?

398
00:29:46,000 --> 00:29:49,000
[Rob B.] Nous voulions faire la taille de char *, car nous ne sommes plus-

399
00:29:49,000 --> 00:29:53,000
ce serait en fait un très gros problème parce que sizeof (char) serait de 1.

400
00:29:53,000 --> 00:29:55,000
Char * sizeof va être de 4,

401
00:29:55,000 --> 00:29:58,000
de sorte que beaucoup de fois quand vous faites affaire avec des entiers,

402
00:29:58,000 --> 00:30:01,000
vous avez tendance à sortir avec elle parce que la taille de int et la taille de int *

403
00:30:01,000 --> 00:30:04,000
sur un système 32-bit va être la même chose.

404
00:30:04,000 --> 00:30:09,000
Mais ici, sizeof (char) et sizeof (char *) sont désormais va être la même chose.

405
00:30:09,000 --> 00:30:15,000
>> Quelle est la situation où l'on retourne faux?

406
00:30:15,000 --> 00:30:17,000
[Étudiants] Nouveau est nulle.

407
00:30:17,000 --> 00:30:23,000
Oui, si le nouveau est nul, on retourne faux,

408
00:30:23,000 --> 00:30:34,000
et je vais jeter ici-

409
00:30:34,000 --> 00:30:37,000
[Étudiants] [inaudible]

410
00:30:37,000 --> 00:30:39,000
[Rob B.] Oui, c'est très bien.

411
00:30:39,000 --> 00:30:46,000
Vous pouvez soit le faire 2 fois la capacité ou 1 quart capacité et ensuite seulement le mettre ici-bas ou ailleurs.

412
00:30:46,000 --> 00:30:52,000
Nous allons le faire comme nous l'avions.

413
00:30:52,000 --> 00:30:56,000
Capacité >> = 1.

414
00:30:56,000 --> 00:31:08,000
Et vous n'allez jamais avoir à vous inquiéter de perdre sa place le 1

415
00:31:08,000 --> 00:31:12,000
parce que vous avez quitté décalée de 1, donc les 1 endroit est nécessairement un 0,

416
00:31:12,000 --> 00:31:16,000
donc décaler à droite par 1, vous allez toujours bien.

417
00:31:16,000 --> 00:31:19,000
[Étudiants] Avez-vous besoin de le faire avant le retour?

418
00:31:19,000 --> 00:31:29,000
[Rob B.] Oui, cela n'a absolument aucun sens.

419
00:31:29,000 --> 00:31:36,000
>> Supposons maintenant que nous allons finir par retourner true à la fin.

420
00:31:36,000 --> 00:31:39,000
La façon dont nous allons faire ces memmoves,

421
00:31:39,000 --> 00:31:45,000
nous devons faire attention à la façon dont nous le faisons.

422
00:31:45,000 --> 00:31:50,000
Est-ce que quelqu'un a des suggestions sur la façon dont nous le faisons?

423
00:32:17,000 --> 00:32:21,000
Voici notre départ.

424
00:32:21,000 --> 00:32:28,000
Inévitablement, nous voulons commencer au début de nouveau

425
00:32:28,000 --> 00:32:35,000
copie et les choses à partir de là, 1, 3, 4, 2.

426
00:32:35,000 --> 00:32:41,000
Comment faites-vous cela?

427
00:32:41,000 --> 00:32:52,000
Tout d'abord, je dois regarder à la page de manuel de memmove nouveau.

428
00:32:52,000 --> 00:32:57,000
Memmove, l'ordre des arguments est toujours important.

429
00:32:57,000 --> 00:33:01,000
Nous voulons que notre destination première, deuxième source d', troisième dimension.

430
00:33:01,000 --> 00:33:06,000
Il ya beaucoup de fonctions qui inversent source et la destination.

431
00:33:06,000 --> 00:33:11,000
Destination, d'origine a tendance à être un peu cohérente.

432
00:33:17,000 --> 00:33:21,000
Déplacer, quel est-il de retour?

433
00:33:21,000 --> 00:33:27,000
Elle renvoie un pointeur vers la destination, quelle qu'en soit la raison, vous voudrez peut-être cela.

434
00:33:27,000 --> 00:33:32,000
Je peux le lire image, mais nous voulons aller dans notre destination.

435
00:33:32,000 --> 00:33:35,000
>> Quelle est notre destination va être?

436
00:33:35,000 --> 00:33:37,000
[Étudiants] Nouveau.

437
00:33:37,000 --> 00:33:39,000
[Rob B.] Oui, et où allons-nous à partir de la copie?

438
00:33:39,000 --> 00:33:43,000
La première chose que nous la copie est-ce 1, 3, 4.

439
00:33:43,000 --> 00:33:50,000
Qu'est-ce que la mention-cette 1, 3, 4.

440
00:33:50,000 --> 00:33:55,000
Quelle est l'adresse de ce 1?

441
00:33:55,000 --> 00:33:58,000
Quelle est l'adresse de ce 1?

442
00:33:58,000 --> 00:34:01,000
[Étudiants] [inaudible]

443
00:34:01,000 --> 00:34:03,000
[Rob B.] Tête + l'adresse du premier élément.

444
00:34:03,000 --> 00:34:05,000
Comment pouvons-nous obtenir le premier élément dans le tableau?

445
00:34:05,000 --> 00:34:10,000
[Étudiants] file d'attente.

446
00:34:10,000 --> 00:34:15,000
[Rob B.] Oui, q.strings.

447
00:34:15,000 --> 00:34:20,000
Rappelez-vous, ici, notre tête est de 1.

448
00:34:20,000 --> 00:34:24,000
Bon sang. Je pense que c'est juste magique-

449
00:34:24,000 --> 00:34:29,000
Ici, notre tête est de 1. Je vais changer ma couleur aussi.

450
00:34:29,000 --> 00:34:36,000
Et voici cordes.

451
00:34:36,000 --> 00:34:41,000
Cela, nous pouvons soit l'écrire comme nous l'avons fait ici

452
00:34:41,000 --> 00:34:43,000
avec des têtes + q.strings.

453
00:34:43,000 --> 00:34:51,000
Beaucoup de gens aussi écrire et q.strings [la tête].

454
00:34:51,000 --> 00:34:55,000
Ce n'est pas vraiment moins efficace.

455
00:34:55,000 --> 00:34:58,000
Vous pourriez penser que c'est vous le déréférencement, puis obtenir l'adresse d',

456
00:34:58,000 --> 00:35:04,000
mais le compilateur va traduire ce que nous avions avant de toute façon, q.strings + tête.

457
00:35:04,000 --> 00:35:06,000
De toute façon vous voulez penser.

458
00:35:06,000 --> 00:35:11,000
>> Et combien d'octets que nous voulons copier?

459
00:35:11,000 --> 00:35:15,000
[Étudiants] Capacité - tête.

460
00:35:15,000 --> 00:35:18,000
Capacité - tête.

461
00:35:18,000 --> 00:35:21,000
Et puis, vous pouvez toujours écrire sur un exemple

462
00:35:21,000 --> 00:35:23,000
de voir si c'est vrai.

463
00:35:23,000 --> 00:35:26,000
[Étudiants] Il doit être divisé par 2, alors.

464
00:35:26,000 --> 00:35:30,000
Ouais, donc je suppose que nous pourrions utiliser la taille.

465
00:35:30,000 --> 00:35:35,000
Nous avons encore la taille étant-

466
00:35:35,000 --> 00:35:39,000
en utilisant la taille, on a une taille égale à 4.

467
00:35:39,000 --> 00:35:42,000
Notre taille est de 4. Notre tête est 1.

468
00:35:42,000 --> 00:35:46,000
Nous voulons copier ces 3 éléments.

469
00:35:46,000 --> 00:35:54,000
C'est la vérification que cette taille - tête est correctement 3.

470
00:35:54,000 --> 00:35:58,000
Et revenir ici, comme nous l'avons déjà dit,

471
00:35:58,000 --> 00:36:00,000
si nous avons utilisé la capacité, alors nous aurions à diviser par 2

472
00:36:00,000 --> 00:36:04,000
parce que nous avons déjà augmenté notre capacité, donc au lieu, nous allons utiliser la taille.

473
00:36:11,000 --> 00:36:13,000
Que des copies de cette partie.

474
00:36:13,000 --> 00:36:18,000
Maintenant, nous avons besoin de copier l'autre partie, la partie qui est à gauche du début.

475
00:36:18,000 --> 00:36:28,000
>> Cela va Memmove dans quelle position?

476
00:36:28,000 --> 00:36:32,000
[Étudiants] Taille Plus - tête.

477
00:36:32,000 --> 00:36:38,000
Oui, nous avons déjà copié en taille - octets tête,

478
00:36:38,000 --> 00:36:43,000
et donc où nous voulons copier les octets restants est nouveau

479
00:36:43,000 --> 00:36:48,000
puis la taille minus-même, le nombre d'octets que nous avons déjà copié po

480
00:36:48,000 --> 00:36:52,000
Et puis, où allons-nous à partir de la copie?

481
00:36:52,000 --> 00:36:54,000
[Étudiants] Q.strings [0].

482
00:36:54,000 --> 00:36:56,000
[Rob B.] Oui, q.strings.

483
00:36:56,000 --> 00:37:02,000
On pourrait soit faire et q.strings [0].

484
00:37:02,000 --> 00:37:05,000
Ce chiffre est nettement moins fréquent que cela.

485
00:37:05,000 --> 00:37:14,000
Si ça va juste être 0, alors vous aurez tendance à voir q.strings.

486
00:37:14,000 --> 00:37:16,000
C'est là que nous copiant à partir.

487
00:37:16,000 --> 00:37:18,000
Combien d'octets ne nous reste à copier? >> [Étudiants] 10.

488
00:37:18,000 --> 00:37:20,000
Droite.

489
00:37:20,000 --> 00:37:25,000
[Étudiants] Faut-il multiplier 5 à 10 fois la taille des octets ou quelque chose?

490
00:37:25,000 --> 00:37:30,000
Ouais, donc c'est de là qu'est-ce exactement que nous la copie?

491
00:37:30,000 --> 00:37:32,000
[Étudiants] [inaudible]

492
00:37:32,000 --> 00:37:34,000
Quel est le type de chose que nous la copie?

493
00:37:34,000 --> 00:37:36,000
[Étudiants] [inaudible]

494
00:37:36,000 --> 00:37:41,000
Ouais, donc le char * s que nous vous copiez, nous ne savons pas où ceux-ci sont en venir.

495
00:37:41,000 --> 00:37:47,000
Eh bien, là où ils sont pointant vers, comme les cordes, on finit par le pousser vers la file d'attente

496
00:37:47,000 --> 00:37:49,000
ou mise en file sur la file d'attente.

497
00:37:49,000 --> 00:37:51,000
Lorsque les personnes viennent, nous n'avons aucune idée.

498
00:37:51,000 --> 00:37:56,000
Nous avons juste besoin de garder une trace de la char * s eux-mêmes.

499
00:37:56,000 --> 00:38:00,000
Nous ne voulons pas copier taille - octets tête.

500
00:38:00,000 --> 00:38:03,000
Nous voulons copier taille - tête char * s,

501
00:38:03,000 --> 00:38:11,000
donc nous allons multiplier par sizeof (char *).

502
00:38:11,000 --> 00:38:17,000
Même ici-bas, la tête * sizeof (char *).

503
00:38:17,000 --> 00:38:24,000
>> [Étudiants] Qu'en est-il [inaudible]?

504
00:38:24,000 --> 00:38:26,000
Ce droit ici?

505
00:38:26,000 --> 00:38:28,000
[Étudiants] Non, en dessous, la taille - tête.

506
00:38:28,000 --> 00:38:30,000
[Rob B.] Ce droit ici?

507
00:38:30,000 --> 00:38:32,000
L'arithmétique des pointeurs.

508
00:38:32,000 --> 00:38:35,000
Comment l'arithmétique des pointeurs est d'aller travailler est

509
00:38:35,000 --> 00:38:40,000
il se multiplie automatiquement par la taille du type que nous avons affaire.

510
00:38:40,000 --> 00:38:46,000
Tout comme ici, nouvelle + (taille - tête)

511
00:38:46,000 --> 00:38:56,000
est exactement équivalente à & [size - tête] nouveau

512
00:38:56,000 --> 00:39:00,000
jusqu'à ce que nous nous attendons à ce que pour fonctionner correctement,

513
00:39:00,000 --> 00:39:04,000
car si nous avons affaire à un tableau int, alors nous n'avons pas d'index par int-

514
00:39:04,000 --> 00:39:07,000
ou si elle est de taille 5 et que vous voulez le 4ème élément, puis nous index dans la

515
00:39:07,000 --> 00:39:10,000
int tableau [4].

516
00:39:10,000 --> 00:39:14,000
Vous ne-[4] * taille de int.

517
00:39:14,000 --> 00:39:21,000
Qu'il gère automatiquement, et dans ce cas

518
00:39:21,000 --> 00:39:29,000
est littéralement équivalent, de sorte que le support de la syntaxe

519
00:39:29,000 --> 00:39:34,000
va juste être converties à ce que dès que vous compilez.

520
00:39:34,000 --> 00:39:38,000
C'est quelque chose que vous devez faire attention à ce que

521
00:39:38,000 --> 00:39:42,000
lorsque vous ajoutez taille - tête

522
00:39:42,000 --> 00:39:45,000
vous ajoutez pas un octet.

523
00:39:45,000 --> 00:39:53,000
Vous n'êtes ajoutant un char *, qui peut être un octets ou quoi que ce soit.

524
00:39:53,000 --> 00:39:56,000
>> D'autres questions?

525
00:39:56,000 --> 00:40:04,000
Bon, dequeue va être plus facile.

526
00:40:04,000 --> 00:40:11,000
Je vais vous donner une minute pour mettre en œuvre.

527
00:40:11,000 --> 00:40:18,000
Oh, et je suppose que c'est la même situation

528
00:40:18,000 --> 00:40:21,000
ce le cas enqueue, si nous sommes mise en file nulle,

529
00:40:21,000 --> 00:40:24,000
peut-être que nous voulons y faire face, peut-être nous n'avons pas.

530
00:40:24,000 --> 00:40:27,000
Nous n'allons pas refaire ici, mais même notre cas pile.

531
00:40:27,000 --> 00:40:34,000
Si nous en file d'attente nulle, nous pourrions en faire abstraction.

532
00:40:34,000 --> 00:40:40,000
N'importe qui ont un peu de code que je peux tirer vers le haut?

533
00:40:40,000 --> 00:40:45,000
[Étudiants] J'ai juste dequeue.

534
00:40:45,000 --> 00:40:56,000
La version 2 est que-bien.

535
00:40:56,000 --> 00:40:59,000
Vous cherchez à faire?

536
00:40:59,000 --> 00:41:01,000
[Étudiants] Tout d'abord, vous assurez-vous qu'il ya quelque chose dans la file d'attente

537
00:41:01,000 --> 00:41:07,000
et que la taille est en baisse de 1.

538
00:41:07,000 --> 00:41:11,000
Vous avez besoin de faire ça, et puis vous revenez la tête

539
00:41:11,000 --> 00:41:13,000
et puis déplacez la tête jusqu'à 1.

540
00:41:13,000 --> 00:41:19,000
Ok, donc il ya un cas coin, nous avons à considérer. Ouais.

541
00:41:19,000 --> 00:41:24,000
[Étudiants] Si votre tête est au dernier élément,

542
00:41:24,000 --> 00:41:26,000
alors vous ne voulez pas la tête pour pointer en dehors du tableau.

543
00:41:26,000 --> 00:41:29,000
>> Oui, dès que la tête arrive à la fin de notre tableau,

544
00:41:29,000 --> 00:41:35,000
quand nous dequeue, notre tête doit être modded à 0.

545
00:41:35,000 --> 00:41:40,000
Malheureusement, nous ne pouvons pas le faire en une seule étape.

546
00:41:40,000 --> 00:41:44,000
Je pense que la façon dont je serais probablement fixer, il est

547
00:41:44,000 --> 00:41:52,000
cela va être un char *, ce que nous retournant,

548
00:41:52,000 --> 00:41:55,000
quel que soit votre nom de variable veut être.

549
00:41:55,000 --> 00:42:02,000
Ensuite, nous voulons mod tête par notre capacité

550
00:42:02,000 --> 00:42:10,000
puis revenir ret.

551
00:42:10,000 --> 00:42:14,000
Beaucoup de gens ici, ils pourraient faire-

552
00:42:14,000 --> 00:42:19,000
c'est le cas de-vous verrez les gens faire si la tête

553
00:42:19,000 --> 00:42:29,000
est supérieure à la capacité, faire la tête - la capacité.

554
00:42:29,000 --> 00:42:36,000
Et qui vient travailler autour de ce mod est.

555
00:42:36,000 --> 00:42:41,000
Chef mod = capacité est beaucoup plus propre

556
00:42:41,000 --> 00:42:51,000
d'un emballage autour de la tête, si supérieure à la capacité de la tête - la capacité.

557
00:42:51,000 --> 00:42:56,000
>> Des questions?

558
00:42:56,000 --> 00:43:02,000
Ok, la dernière chose que nous avons laissé notre liste chaînée.

559
00:43:02,000 --> 00:43:07,000
Vous pourriez être utilisé pour une partie du comportement liste chaînée si vous avez fait

560
00:43:07,000 --> 00:43:11,000
des listes liées dans vos tables de hachage, si vous avez une table de hachage.

561
00:43:11,000 --> 00:43:15,000
Je recommande fortement de faire une table de hachage.

562
00:43:15,000 --> 00:43:17,000
Vous avez sans doute déjà fait un trie,

563
00:43:17,000 --> 00:43:23,000
mais essais sont plus difficiles.

564
00:43:23,000 --> 00:43:27,000
En théorie, ils sont asymptotiquement meilleur.

565
00:43:27,000 --> 00:43:30,000
Mais il suffit de regarder le grand tableau,

566
00:43:30,000 --> 00:43:35,000
et tente jamais faire mieux, et ils prennent plus de mémoire.

567
00:43:35,000 --> 00:43:43,000
Tout à propos de tente finit par être pire pour les plus de travail.

568
00:43:43,000 --> 00:43:49,000
C'est ce que David Malan solution est toujours

569
00:43:49,000 --> 00:43:56,000
est-il toujours sa solution trie les messages, et voyons où il est actuellement.

570
00:43:56,000 --> 00:44:00,000
Quel était-il sous, David J?

571
00:44:00,000 --> 00:44:06,000
Il est n ° 18, si ce n'est pas terriblement mauvais,

572
00:44:06,000 --> 00:44:09,000
et que ça va être l'un des meilleurs essais, vous pouvez penser

573
00:44:09,000 --> 00:44:17,000
ou l'un des meilleurs essaie d'une structure arborescente.

574
00:44:17,000 --> 00:44:23,000
N'est-il pas même sa solution originale?

575
00:44:23,000 --> 00:44:29,000
Je me sens comme solutions de structure arborescente ont tendance à être plus dans cette gamme de utilisation de la RAM.

576
00:44:29,000 --> 00:44:33,000
>> Aller en bas à en haut, et l'utilisation de la RAM est à un seul chiffre.

577
00:44:33,000 --> 00:44:36,000
Descendez vers le bas, puis vous commencez à voir essaie

578
00:44:36,000 --> 00:44:41,000
où vous aurez utilisation de la RAM absolument gigantesque,

579
00:44:41,000 --> 00:44:45,000
et essais sont plus difficiles.

580
00:44:45,000 --> 00:44:53,000
Pas tout à fait la peine, mais une expérience éducative si vous avez un.

581
00:44:53,000 --> 00:44:56,000
La dernière chose est de notre liste chaînée,

582
00:44:56,000 --> 00:45:04,000
et ces trois choses, piles, files et listes chaînées,

583
00:45:04,000 --> 00:45:09,000
quelque chose de l'avenir vous jamais faire en informatique

584
00:45:09,000 --> 00:45:12,000
supposerons que vous avez connaissance de ces choses.

585
00:45:12,000 --> 00:45:19,000
Ils sont tellement fondamentale pour tout.

586
00:45:19,000 --> 00:45:25,000
>> Listes chaînées, et ici nous avons une liste simplement chaînée va être notre mise en œuvre.

587
00:45:25,000 --> 00:45:34,000
Qu'est-ce que signifie simplement chaînée par opposition aux doublement chaînée? Oui.

588
00:45:34,000 --> 00:45:37,000
[Étudiants] Il souligne que pour que le pointeur suivant plutôt que de les pointeurs,

589
00:45:37,000 --> 00:45:39,000
comme celui qui le précède et celle d'après.

590
00:45:39,000 --> 00:45:44,000
Ouais, donc au format image, qu'est-ce que je viens de faire?

591
00:45:44,000 --> 00:45:48,000
J'ai deux choses. J'ai image et l'image.

592
00:45:48,000 --> 00:45:51,000
Dans le format d'image, nos individuellement listes chaînées,

593
00:45:51,000 --> 00:45:57,000
inévitablement, nous avons une sorte de pointeur à la tête de notre liste,

594
00:45:57,000 --> 00:46:02,000
puis au sein de notre liste, nous avons juste des pointeurs,

595
00:46:02,000 --> 00:46:05,000
et peut-être cela indique une valeur nulle.

596
00:46:05,000 --> 00:46:08,000
Ça va être votre dessin typique d'une liste simplement chaînée.

597
00:46:08,000 --> 00:46:14,000
Une liste doublement chaînée, vous pouvez revenir en arrière.

598
00:46:14,000 --> 00:46:19,000
Si je vous donne un nœud dans la liste, vous pouvez alors nécessairement se rendre à

599
00:46:19,000 --> 00:46:23,000
un autre noeud dans la liste si elle est une liste doublement chaînée.

600
00:46:23,000 --> 00:46:27,000
Mais si je te le troisième noeud dans la liste et c'est une liste simplement chaînée,

601
00:46:27,000 --> 00:46:30,000
aucun moyen que vous allez jamais à obtenir les premier et second noeuds.

602
00:46:30,000 --> 00:46:34,000
Et il ya des avantages et des inconvénients, et un plus évident

603
00:46:34,000 --> 00:46:42,000
est vous prendre plus de taille, et vous devez garder une trace de l'endroit où ces choses sont pointant maintenant.

604
00:46:42,000 --> 00:46:49,000
Mais nous ne se soucient simplement chaînée.

605
00:46:49,000 --> 00:46:53,000
>> A peu de choses que nous allons devoir mettre en œuvre.

606
00:46:53,000 --> 00:47:00,000
Votre typedef struct noeud, int i: struct noeud * suivant; nœud.

607
00:47:00,000 --> 00:47:09,000
C'est typedef devrait être gravée dans votre esprit.

608
00:47:09,000 --> 00:47:14,000
Quiz 1 doit être comme donner un typedef d'un nœud de liste chaînée,

609
00:47:14,000 --> 00:47:18,000
et vous devriez être en mesure de mettre immédiatement griffonner que vers le bas

610
00:47:18,000 --> 00:47:22,000
sans même y penser.

611
00:47:22,000 --> 00:47:27,000
Je suppose que quelques questions, pourquoi avons-nous besoin struct ici?

612
00:47:27,000 --> 00:47:32,000
Pourquoi ne peut-on pas dire noeud *?

613
00:47:32,000 --> 00:47:35,000
[Étudiants] [inaudible]

614
00:47:35,000 --> 00:47:38,000
Ouais.

615
00:47:38,000 --> 00:47:44,000
La seule chose qui définit un noeud comme une chose

616
00:47:44,000 --> 00:47:47,000
typedef est la même.

617
00:47:47,000 --> 00:47:55,000
Mais à partir de ce point, lorsque nous sommes en quelque sorte l'analyse par cette définition struct noeud,

618
00:47:55,000 --> 00:48:01,000
nous n'avons pas fini notre typedef encore, donc depuis le typedef n'est pas terminée,

619
00:48:01,000 --> 00:48:05,000
noeud n'existe pas.

620
00:48:05,000 --> 00:48:12,000
Mais struct noeud fait, et ce noeud ici,

621
00:48:12,000 --> 00:48:14,000
cela pourrait aussi être appelé n'importe quoi d'autre.

622
00:48:14,000 --> 00:48:16,000
Cela pourrait être appelé n.

623
00:48:16,000 --> 00:48:19,000
Il pourrait être appelé nœud de liste chaînée.

624
00:48:19,000 --> 00:48:21,000
Il pourrait être appelé n'importe quoi.

625
00:48:21,000 --> 00:48:26,000
Mais ce noeud struct doit être appelé la même chose que ce noeud struct.

626
00:48:26,000 --> 00:48:29,000
Ce que vous appelez cela doit aussi être ici,

627
00:48:29,000 --> 00:48:32,000
et de telle sorte que répond également au second point de la question

628
00:48:32,000 --> 00:48:37,000
C'est pourquoi, beaucoup de fois quand vous voyez structs et typedefs de structures,

629
00:48:37,000 --> 00:48:42,000
vous verrez les structures anonymes où vous ne verrez typedef struct,

630
00:48:42,000 --> 00:48:47,000
mise en œuvre de la structure, un dictionnaire, ou autre chose.

631
00:48:47,000 --> 00:48:51,000
>> Pourquoi avons-nous besoin ici de dire nœud?

632
00:48:51,000 --> 00:48:54,000
Pourquoi ne peut-il pas être une struct anonyme?

633
00:48:54,000 --> 00:48:56,000
C'est presque la même réponse.

634
00:48:56,000 --> 00:48:58,000
[Étudiants] Vous avez besoin de s'y référer dans la structure.

635
00:48:58,000 --> 00:49:04,000
Oui, au sein de la structure, vous devez vous référer à la structure elle-même.

636
00:49:04,000 --> 00:49:10,000
Si vous ne donnez pas la structure d'un nom, si c'est une struct anonyme, vous ne pouvez pas faire référence.

637
00:49:10,000 --> 00:49:17,000
Et enfin et surtout, celles-ci ne devraient tous être un peu simple,

638
00:49:17,000 --> 00:49:20,000
et ils devraient vous aider à réaliser si vous écrivez cela sur

639
00:49:20,000 --> 00:49:24,000
que vous faites quelque chose de mal, si ce genre de choses n'ont pas de sens.

640
00:49:24,000 --> 00:49:28,000
Last but not least, pourquoi cela at-il pour être struct noeud *?

641
00:49:28,000 --> 00:49:34,000
Pourquoi ne pas simplement être struct noeud suivant?

642
00:49:34,000 --> 00:49:37,000
[Étudiants] Pointeur vers la structure suivante.

643
00:49:37,000 --> 00:49:39,000
C'est forcément ce que nous voulons.

644
00:49:39,000 --> 00:49:42,000
Pourquoi ne pourrait-il jamais être struct noeud prochaine?

645
00:49:42,000 --> 00:49:50,000
Pourquoi faut-il que le noeud de struct * à côté? Ouais.

646
00:49:50,000 --> 00:49:53,000
[Étudiants] C'est comme une boucle infinie.

647
00:49:53,000 --> 00:49:55,000
Ouais.

648
00:49:55,000 --> 00:49:57,000
[Étudiants] Tout serait à la fois.

649
00:49:57,000 --> 00:50:02,000
Oui, il suffit de penser comment nous ferions taille ou quelque chose.

650
00:50:02,000 --> 00:50:08,000
Taille d'une structure est fondamentalement + ou - une tendance ici ou là.

651
00:50:08,000 --> 00:50:15,000
C'est fondamentalement va être la somme des tailles des choses dans la structure.

652
00:50:15,000 --> 00:50:18,000
Ce droit ici, sans rien changer, la taille va pas être facile.

653
00:50:18,000 --> 00:50:24,000
Taille de noeud struct va être la taille de i + taille de la prochaine.

654
00:50:24,000 --> 00:50:27,000
Taille de i va être 4. Taille de la prochaine va être 4.

655
00:50:27,000 --> 00:50:30,000
Taille de noeud struct va être 8.

656
00:50:30,000 --> 00:50:34,000
Si nous n'avons pas l'*, en pensant à sizeof,

657
00:50:34,000 --> 00:50:37,000
puis sizeof (i) va être 4.

658
00:50:37,000 --> 00:50:43,000
Taille de noeud struct est la prochaine va être la taille de i + taille du noeud struct prochaine

659
00:50:43,000 --> 00:50:46,000
Taille + taille + i du nœud de structure suivante.

660
00:50:46,000 --> 00:50:55,000
Ce serait une récursion infinie de nœuds.

661
00:50:55,000 --> 00:51:00,000
C'est pourquoi c'est comme ça que les choses doivent être.

662
00:51:00,000 --> 00:51:03,000
>> Encore une fois, c'est sûr que mémoriser,

663
00:51:03,000 --> 00:51:06,000
ou au moins le comprendre assez que vous pouvez être en mesure de

664
00:51:06,000 --> 00:51:12,000
la raison par la quelle il devrait ressembler.

665
00:51:12,000 --> 00:51:14,000
Les choses que nous allons vouloir mettre en œuvre.

666
00:51:14,000 --> 00:51:18,000
Si la longueur de la liste,

667
00:51:18,000 --> 00:51:21,000
vous pouvez tricher et garder autour d'un

668
00:51:21,000 --> 00:51:24,000
durée globale ou quelque chose, mais nous n'allons pas le faire.

669
00:51:24,000 --> 00:51:28,000
Nous allons compter la longueur de la liste.

670
00:51:28,000 --> 00:51:34,000
Nous avons contient, de sorte que c'est fondamentalement comme une recherche,

671
00:51:34,000 --> 00:51:41,000
nous avons donc une liste chaînée d'entiers pour voir si cet entier est dans la liste chaînée.

672
00:51:41,000 --> 00:51:44,000
Préfixe va insérer au début de la liste.

673
00:51:44,000 --> 00:51:46,000
Append va insérer à la fin.

674
00:51:46,000 --> 00:51:53,000
Insert_sorted va insérer dans la position dans la liste triée.

675
00:51:53,000 --> 00:52:01,000
Type de Insert_sorted suppose que vous n'avez jamais utilisé prepend ou ajouter dans de mauvaises manières.

676
00:52:01,000 --> 00:52:09,000
>> Insert_sorted lorsque vous implémentez insert_sorted-

677
00:52:09,000 --> 00:52:13,000
disons que nous avons notre liste chaînée.

678
00:52:13,000 --> 00:52:18,000
C'est ce que cela ressemble actuellement, 2, 4, 5.

679
00:52:18,000 --> 00:52:24,000
Je veux insérer 3, tant et aussi longtemps que la liste elle-même est déjà trié,

680
00:52:24,000 --> 00:52:27,000
il est facile de trouver où 3 appartient.

681
00:52:27,000 --> 00:52:29,000
Je commence à 2.

682
00:52:29,000 --> 00:52:32,000
Okay, 3 est supérieur à 2, alors je veux continuer.

683
00:52:32,000 --> 00:52:35,000
Oh, 4 est trop grand, donc je sais pas 3 va passer entre 2 et 4,

684
00:52:35,000 --> 00:52:39,000
et je dois fixer des pointeurs et tous ces trucs.

685
00:52:39,000 --> 00:52:43,000
Mais si nous n'avons pas strictement d'utiliser insert_sorted,

686
00:52:43,000 --> 00:52:50,000
comme nous allons simplement dire que je préfixer 6,

687
00:52:50,000 --> 00:52:55,000
puis ma liste chaînée va devenir cela.

688
00:52:55,000 --> 00:53:01,000
Il fait maintenant aucun sens, donc pour insert_sorted, vous pouvez simplement supposer

689
00:53:01,000 --> 00:53:04,000
que la liste est triée, même si les opérations existent

690
00:53:04,000 --> 00:53:09,000
qui peut l'amener à ne pas être triés, et c'est tout.

691
00:53:09,000 --> 00:53:20,000
Trouver un insert utiles afin que ceux-sont les principales choses que vous allez avoir à mettre en œuvre.

692
00:53:20,000 --> 00:53:24,000
>> Pour l'instant, prenez une minute pour faire la longueur et contient,

693
00:53:24,000 --> 00:53:30,000
et ceux-ci devraient être relativement rapide.

694
00:53:41,000 --> 00:53:48,000
Presque l'heure de fermeture, si quelqu'un a quelque chose pour la longueur ou contient?

695
00:53:48,000 --> 00:53:50,000
Ils vont être à peu près identique.

696
00:53:50,000 --> 00:53:57,000
[Étudiants] Longueur.

697
00:53:57,000 --> 00:54:01,000
Voyons, révision.

698
00:54:01,000 --> 00:54:04,000
D'accord.

699
00:54:12,000 --> 00:54:15,000
Vous cherchez à faire?

700
00:54:15,000 --> 00:54:21,000
[Étudiants] Je viens de créer un nœud de pointeur et l'initialiser d'abord, qui est notre variable globale,

701
00:54:21,000 --> 00:54:27,000
puis-je vérifier pour voir si elle est nulle si je ne reçois pas un défaut segments et renvoient 0 si c'est le cas.

702
00:54:27,000 --> 00:54:34,000
Sinon, je boucle, garder une trace de l'intérieur entier

703
00:54:34,000 --> 00:54:38,000
combien de fois j'ai accédé à l'élément suivant de la liste

704
00:54:38,000 --> 00:54:43,000
et dans la même opération d'incrémentation également accéder à cet élément réel,

705
00:54:43,000 --> 00:54:47,000
et puis je continue faire la vérification pour voir si elle est nulle,

706
00:54:47,000 --> 00:54:56,000
et si elle est nulle, alors il abandonne et retourne simplement le nombre d'éléments que j'ai consultés.

707
00:54:56,000 --> 00:55:01,000
>> [Rob B.] Est-ce que quelqu'un a des commentaires sur quelque chose?

708
00:55:01,000 --> 00:55:06,000
Cela semble correct bien sage.

709
00:55:06,000 --> 00:55:10,000
[Étudiants] Je ne pense pas que vous devez le noeud == null.

710
00:55:10,000 --> 00:55:13,000
Ouais, donc si le noeud == 0 return null.

711
00:55:13,000 --> 00:55:18,000
Mais si le noeud == null alors ce-oh, il ya un problème de justesse.

712
00:55:18,000 --> 00:55:23,000
C'était juste vous i retour, mais ce n'est pas dans la portée en ce moment.

713
00:55:23,000 --> 00:55:30,000
Vous avez juste besoin int i, si i = 0.

714
00:55:30,000 --> 00:55:34,000
Mais si le noeud est nulle, alors je continue toujours à 0,

715
00:55:34,000 --> 00:55:39,000
et nous allons retourner 0, si ce cas est identique.

716
00:55:39,000 --> 00:55:48,000
Un autre point commun est de conserver la déclaration

717
00:55:48,000 --> 00:55:51,000
du noeud à l'intérieur de la boucle for.

718
00:55:51,000 --> 00:55:54,000
Vous pourriez dire: oh, non.

719
00:55:54,000 --> 00:55:56,000
Restons comme ça.

720
00:55:56,000 --> 00:55:59,000
Je serais probablement mis int i = 0 ici,

721
00:55:59,000 --> 00:56:05,000
alors noeud noeud * = première ici.

722
00:56:05,000 --> 00:56:11,000
Et c'est sans doute comment-se débarrasser de cela maintenant.

723
00:56:11,000 --> 00:56:14,000
C'est probablement la façon dont je l'ai écrit.

724
00:56:14,000 --> 00:56:21,000
Vous pouvez aussi regarder-comme celui-ci.

725
00:56:21,000 --> 00:56:25,000
Cette structure de boucle pour ici

726
00:56:25,000 --> 00:56:30,000
devrait être presque aussi naturel pour vous que pour int i = 0

727
00:56:30,000 --> 00:56:33,000
i est inférieure à la longueur de la rangée i + +.

728
00:56:33,000 --> 00:56:38,000
Si c'est comme ça que vous itérer sur un tableau, c'est la façon dont vous itérer sur une liste chaînée.

729
00:56:38,000 --> 00:56:45,000
>> Cela devrait être une seconde nature à un moment donné.

730
00:56:45,000 --> 00:56:50,000
Avec cela à l'esprit, ce sera presque la même chose.

731
00:56:50,000 --> 00:56:57,000
Vous allez avoir à parcourir une liste chaînée.

732
00:56:57,000 --> 00:57:02,000
Si le nœud-Je n'ai aucune idée de ce que la valeur est appelée.

733
00:57:02,000 --> 00:57:04,000
I nœud.

734
00:57:04,000 --> 00:57:15,000
Si la valeur de ce noeud = i return true, et c'est tout.

735
00:57:15,000 --> 00:57:18,000
Notez que la seule façon que nous ayons jamais retourner faux

736
00:57:18,000 --> 00:57:23,000
si nous parcourir la liste entière liée et ne jamais revenir vrai,

737
00:57:23,000 --> 00:57:29,000
si c'est ce que cela fait.

738
00:57:29,000 --> 00:57:36,000
Comme un côté la note, nous n'obtiendrez probablement pas d'ajouter ou de précéder.

739
00:57:36,000 --> 00:57:39,000
>> Rapide dernière note.

740
00:57:39,000 --> 00:57:52,000
Si vous voyez le mot-clé static, alors disons statique int count = 0,

741
00:57:52,000 --> 00:57:56,000
puis nous faisons count + +, vous pouvez tout simplement penser que c'est une variable globale,

742
00:57:56,000 --> 00:58:00,000
même si je viens de le dire, ce n'est pas comment nous allons mettre en œuvre longueur.

743
00:58:00,000 --> 00:58:06,000
Je le fais ici, et puis compter + +.

744
00:58:06,000 --> 00:58:11,000
De toute façon, nous pouvons entrer un nœud dans notre liste chaînée nous incrémentation notre compte.

745
00:58:11,000 --> 00:58:15,000
Le but de cela est ce que signifie le mot clé static.

746
00:58:15,000 --> 00:58:20,000
Si je devais int count = 0 ce serait un habitué ancienne variable globale.

747
00:58:20,000 --> 00:58:25,000
Que statique moyens int count, c'est qu'il est une variable globale pour ce fichier.

748
00:58:25,000 --> 00:58:28,000
Il est impossible pour un autre fichier,

749
00:58:28,000 --> 00:58:34,000
comme penser pset 5, si vous avez commencé.

750
00:58:34,000 --> 00:58:39,000
Vous avez les deux speller.c, et vous avez dictionary.c,

751
00:58:39,000 --> 00:58:42,000
et si vous venez de déclarer une chose globale, puis quelque chose dans speller.c

752
00:58:42,000 --> 00:58:45,000
est accessible en dictionary.c et vice versa.

753
00:58:45,000 --> 00:58:48,000
Les variables globales sont accessibles par n'importe quel fichier. C,

754
00:58:48,000 --> 00:58:54,000
mais les variables statiques sont accessibles uniquement depuis le fichier lui-même,

755
00:58:54,000 --> 00:59:01,000
donc à l'intérieur du vérificateur d'orthographe ou à l'intérieur de dictionary.c,

756
00:59:01,000 --> 00:59:06,000
c'est un peu de la façon dont je déclarer ma variable pour la taille de mon tableau

757
00:59:06,000 --> 00:59:10,000
ou la taille de mon nombre de mots dans le dictionnaire.

758
00:59:10,000 --> 00:59:15,000
Comme je ne veux pas déclarer une variable globale que l'on ait accès à

759
00:59:15,000 --> 00:59:18,000
J'ai vraiment ne se soucient que pour mes propres fins.

760
00:59:18,000 --> 00:59:21,000
>> La bonne chose à ce sujet est aussi le nom de l'ensemble des choses collision.

761
00:59:21,000 --> 00:59:27,000
Si un autre fichier tente d'utiliser une variable globale appelée comte, les choses vont mal, très mal,

762
00:59:27,000 --> 00:59:33,000
si ça continue bien sûr les choses, et vous seul pouvez y accéder,

763
00:59:33,000 --> 00:59:38,000
et nul autre ne peut, et si quelqu'un d'autre déclare une variable globale appelée comte,

764
00:59:38,000 --> 00:59:43,000
il ne sera pas interférer avec votre variable statique appelée comptage.

765
00:59:43,000 --> 00:59:47,000
C'est ce qui est statique. C'est une variable fichier global.

766
00:59:47,000 --> 00:59:52,000
>> Questions sur quoi que ce soit?

767
00:59:52,000 --> 00:59:59,000
Tous ensemble. Bye.

768
00:59:59,000 --> 01:00:03,000
[CS50.TV]