1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [Semaine 6, suite]

2
00:00:02,520 --> 00:00:04,160
[David J. Malan] [Université de Harvard]

3
00:00:04,160 --> 00:00:08,720
[C'est CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
C'est CS50 et c'est la fin de la semaine 6.

5
00:00:12,970 --> 00:00:17,970
Donc CS50x, l'un des premiers cours de Harvard impliqués dans l'initiative EDX

6
00:00:17,970 --> 00:00:20,590
en effet débuté lundi dernier.

7
00:00:20,590 --> 00:00:23,460
Si vous souhaitez avoir un aperçu de ce que d'autres sur l'Internet

8
00:00:23,460 --> 00:00:27,180
suivent désormais avec, vous pouvez vous diriger vers x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Cela vous redirigera vers l'endroit approprié sur edx.org,

10
00:00:30,350 --> 00:00:34,160
ce qui était le cas cela et d'autres cours du MIT et Berkeley vivons aujourd'hui.

11
00:00:34,160 --> 00:00:38,140
Vous devez vous inscrire pour un compte, vous verrez que le matériau est sensiblement le même

12
00:00:38,140 --> 00:00:42,170
que vous avez eu ce semestre, bien que quelques semaines retardés, comme nous l'avons tout préparer.

13
00:00:42,170 --> 00:00:46,930
Mais ce que les élèves CS50x allons voir maintenant est une interface tout à fait comme celui-ci.

14
00:00:46,930 --> 00:00:50,040
C'est, par exemple, est le leader Zamyla procédure pas à pas pour 0 problème posé.

15
00:00:50,040 --> 00:00:54,230
Lors de la connexion à edx.org, un étudiant CS50x voit le genre de choses

16
00:00:54,230 --> 00:00:57,170
vous vous attendez à voir dans un cours: la conférence pour le Lundi,

17
00:00:57,170 --> 00:01:01,650
conférence pour le mercredi, shorts divers, les ensembles de problèmes, les soluces, les fichiers PDF.

18
00:01:01,650 --> 00:01:04,459
En outre, comme vous le voyez ici des traductions automatiques,

19
00:01:04,459 --> 00:01:08,390
des transcriptions anglaises en chinois, japonais, espagnol, italien,

20
00:01:08,390 --> 00:01:12,810
et tout un tas d'autres langues qui sera certainement imparfaite

21
00:01:12,810 --> 00:01:15,840
comme nous les déployer par programmation en utilisant ce qu'on appelle une API,

22
00:01:15,840 --> 00:01:18,360
ou de l'interface de programmation d'application, à partir de Google

23
00:01:18,360 --> 00:01:21,360
qui nous permet de convertir l'anglais vers d'autres langues.

24
00:01:21,360 --> 00:01:24,100
Mais grâce à la formidable esprit de certains bénévoles, plus de cent,

25
00:01:24,100 --> 00:01:26,940
des gens au hasard sur l'Internet qui ont aimablement offert de s'impliquer

26
00:01:26,940 --> 00:01:30,180
dans ce projet, nous allons progressivement améliorer la qualité de ces traductions

27
00:01:30,180 --> 00:01:35,790
en ayant humains corriger les erreurs que nos ordinateurs ont fait.

28
00:01:35,790 --> 00:01:42,330
>> Ainsi, il s'avère que nous avions quelques élèves plus se présenter le lundi que nous avons prévu initialement.

29
00:01:42,330 --> 00:01:48,980
En fait, maintenant CS50x compte 100.000 personnes suivantes long à la maison.

30
00:01:48,980 --> 00:01:54,430
Alors réalisez que vous êtes tous partie de cette classe inaugurale de faire ce cours en informatique

31
00:01:54,430 --> 00:01:57,370
l'éducation en général, plus largement, accessible.

32
00:01:57,370 --> 00:02:00,130
Et la réalité est aujourd'hui, avec certains de ces cours en ligne massivement,

33
00:02:00,130 --> 00:02:04,070
ils commencent tous ces chiffres très élevés, comme il semble que nous avons fait ici.

34
00:02:04,070 --> 00:02:08,759
Mais l'objectif, à terme, pour CS50x est vraiment d'amener les gens autant à la ligne d'arrivée le plus possible.

35
00:02:08,759 --> 00:02:12,000
De par sa conception, CS50x va être offert à partir de ce lundi

36
00:02:12,000 --> 00:02:17,430
tout au long de Avril 15, 2013, de sorte que les gens qui ont pris des engagements scolaires ailleurs,

37
00:02:17,430 --> 00:02:20,990
travail, famille, d'autres conflits et autres, ont un peu plus de flexibilité

38
00:02:20,990 --> 00:02:23,640
avec laquelle se plonger dans ce cours, qui, il suffit de dire,

39
00:02:23,640 --> 00:02:30,540
est assez ambitieuse faire si ce n'est au cours des trois mois pendant un semestre d'habitude.

40
00:02:30,540 --> 00:02:34,190
Mais ces étudiants seront la lutte contre les jeux même problème, l'affichage du contenu même,

41
00:02:34,190 --> 00:02:36,350
l'accès à des courts-circuits identiques et similaires.

42
00:02:36,350 --> 00:02:38,990
Donc rendons compte que nous sommes tous dans le même bateau vraiment.

43
00:02:38,990 --> 00:02:42,360
Et l'un des objectifs ultimes de CS50x n'est pas juste pour les gens que de nombreux

44
00:02:42,360 --> 00:02:45,720
à la ligne d'arrivée et de leur donner cette nouvelle compréhension de l'informatique

45
00:02:45,720 --> 00:02:49,000
et de la programmation, mais aussi de les faire vivre cette expérience partagée.

46
00:02:49,000 --> 00:02:52,010
L'une des caractéristiques déterminantes de 50 sur le campus, nous l'espérons,

47
00:02:52,010 --> 00:02:56,260
a été ce genre d'expérience commune, pour le meilleur ou pour le pire, parfois,

48
00:02:56,260 --> 00:02:59,480
mais comportant ces personnes de se tourner vers la gauche et vers la droite,

49
00:02:59,480 --> 00:03:01,830
les heures de bureau et et le Hackathon et la foire.

50
00:03:01,830 --> 00:03:04,560
C'est un peu plus difficile à faire que les gens en personne en ligne,

51
00:03:04,560 --> 00:03:10,580
mais CS50x se terminera en Avril avec la première CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
qui sera une adaptation en ligne de notre idée de la foire

53
00:03:13,630 --> 00:03:18,250
où ces milliers d'étudiants seront tous invités à soumettre un 1 - à 2 minutes de vidéo,

54
00:03:18,250 --> 00:03:22,480
soit un screencast de leur projet final ou une vidéo d'eux en agitant bonjour

55
00:03:22,480 --> 00:03:24,490
et de parler de leur projet et faire des démonstrations,

56
00:03:24,490 --> 00:03:27,610
tout comme vos prédécesseurs l'ont fait ici sur le campus à la foire,

57
00:03:27,610 --> 00:03:31,400
de sorte qu'à la fin de semestre, l'espoir est d'avoir une exposition mondiale

58
00:03:31,400 --> 00:03:37,080
projets des étudiants CS50x »final, un peu comme ce qui vous attend en Décembre sur le campus.

59
00:03:37,080 --> 00:03:39,680
Donc plus à ce sujet dans les mois à venir.

60
00:03:39,680 --> 00:03:43,640
>> Avec 100.000 étudiants, cependant, est un besoin pour un peu plus de CA.

61
00:03:43,640 --> 00:03:47,590
Étant donné que vous les gars sont ici ouvre la voie et de prendre CS50

62
00:03:47,590 --> 00:03:51,630
plusieurs semaines à l'avance de la libération de cette matière à des gens sur EDX,

63
00:03:51,630 --> 00:03:55,330
rendons compte que nous aimerions faire participer le plus grand nombre de nos propres étudiants que possible à cette initiative,

64
00:03:55,330 --> 00:03:58,720
à la fois au cours du semestre ainsi que cet hiver et ce printemps.

65
00:03:58,720 --> 00:04:01,620
Donc, si vous souhaitez vous impliquer dans CS50x,

66
00:04:01,620 --> 00:04:07,450
notamment en joignant le CS50x Discuter, la version de EDX CS50 discuter,

67
00:04:07,450 --> 00:04:10,140
beaucoup d'entre vous ont utilisé sur le campus, le tableau d'affichage en ligne,

68
00:04:10,140 --> 00:04:13,040
s'il vous plaît ne la tête à cette URL, laissez-nous savoir qui vous êtes,

69
00:04:13,040 --> 00:04:16,450
parce que nous aimerions mettre en place une équipe d'étudiants et du personnel et du corps professoral aussi bien

70
00:04:16,450 --> 00:04:19,630
sur le campus qui sont tout simplement jouer le jeu et un coup de main.

71
00:04:19,630 --> 00:04:21,720
Et quand ils voient une question qui est familier,

72
00:04:21,720 --> 00:04:25,320
ce que vous entendiez un étudiant de rapports d'un bug quelque part là-bas dans certains pays sur l'Internet,

73
00:04:25,320 --> 00:04:27,450
et que sonne une cloche parce que vous aussi eu ce même problème

74
00:04:27,450 --> 00:04:32,620
dans votre salle d-il ya quelque temps, je l'espère, vous pouvez carillon et partager votre propre expérience.

75
00:04:32,620 --> 00:04:37,300
Alors s'il vous plaît partager si vous le souhaitez.

76
00:04:37,300 --> 00:04:39,360
>> Cours d'informatique à l'Université Harvard ont un peu une tradition,

77
00:04:39,360 --> 00:04:44,730
CS50 parmi eux, d'avoir une certaine vêtements, des vêtements, que vous pouvez porter avec fierté

78
00:04:44,730 --> 00:04:49,090
à la fin de semestre, en disant assez fièrement que vous avez terminé CS50

79
00:04:49,090 --> 00:04:51,830
et a pris CS50 et autres, et nous essayons toujours de faire participer les élèves

80
00:04:51,830 --> 00:04:54,540
dans ce processus autant que possible, par lequel nous inviter,

81
00:04:54,540 --> 00:04:56,900
à cette époque de l'semestre, les étudiants à présenter des projets

82
00:04:56,900 --> 00:04:59,330
l'aide de Photoshop, ou tout autre outil de choix que vous souhaitez utiliser

83
00:04:59,330 --> 00:05:02,330
si vous êtes un designer, à présenter des projets pour les T-shirts et sweat-shirts

84
00:05:02,330 --> 00:05:06,100
et des parasols et des bandanas pour chiens petits, nous avons maintenant et ainsi de suite.

85
00:05:06,100 --> 00:05:09,370
Et tout est alors - les lauréats chaque année sont ensuite exposées

86
00:05:09,370 --> 00:05:12,700
sur le site Web du cours à store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Tout est vendu au prix coûtant, mais le site fonctionne tout simplement lui-même

88
00:05:15,790 --> 00:05:18,330
et permet aux gens de choisir les couleurs et les dessins qu'ils aiment.

89
00:05:18,330 --> 00:05:20,420
J'ai donc pensé que nous venions de partager quelques-unes des conceptions de l'an dernier

90
00:05:20,420 --> 00:05:25,130
qui étaient sur le site en plus de celui-là, qui est une tradition annuelle.

91
00:05:25,130 --> 00:05:29,410
"Chaque jour je Seg Faultn" était l'un des soumissions année dernière,

92
00:05:29,410 --> 00:05:32,290
qui est toujours disponible là-bas pour les anciens.

93
00:05:32,290 --> 00:05:35,820
Nous avons eu celui-ci, "CS50, Established 1989».

94
00:05:35,820 --> 00:05:39,010
Un de nos Bowdens, Rob, était très populaire l'an dernier.

95
00:05:39,010 --> 00:05:43,480
"L'équipe Bowden" est né, cette conception a été présenté, parmi les meilleurs vendeurs.

96
00:05:43,480 --> 00:05:49,040
Comme ce fut celui-là. Beaucoup de gens avaient "Fever Bowden", selon les journaux de vente.

97
00:05:49,040 --> 00:05:52,650
Sachez que ce que pourrait maintenant être votre conception là-bas, sur l'Internet.

98
00:05:52,650 --> 00:05:57,510
Plus de détails à ce sujet dans le prochain problème établit à venir.

99
00:05:57,510 --> 00:06:00,330
>> Un outil de plus: vous avez eu une certaine exposition et nous espérons maintenant

100
00:06:00,330 --> 00:06:02,350
une certaine expérience pratique avec GDB,

101
00:06:02,350 --> 00:06:04,570
qui est, bien sûr, un débogueur et vous permet de manipuler

102
00:06:04,570 --> 00:06:09,500
votre programme à un niveau assez bas, en faisant ce genre de choses?

103
00:06:09,500 --> 00:06:13,030
Qu'est-ce que GDB vous laisser faire?

104
00:06:13,030 --> 00:06:15,030
Ouais? Donne-moi quelque chose. [Réponse de l'étudiant, inintelligible]

105
00:06:15,030 --> 00:06:18,120
Bon. Entrez dans la fonction, de sorte que vous n'avez pas seulement pour saisir run

106
00:06:18,120 --> 00:06:22,310
et avoir le coup programme à travers son intégralité, l'impression des choses sur la sortie standard.

107
00:06:22,310 --> 00:06:25,190
Au contraire, vous pouvez faire défiler ligne par ligne, soit en tapant prochaine

108
00:06:25,190 --> 00:06:30,300
aller ligne par ligne par ligne ou pas à plonger dans une fonction, généralement celui qui vous écrit.

109
00:06:30,300 --> 00:06:35,240
Quels sont les autres GDB vous laisser faire? Ouais? [Réponse de l'étudiant, inintelligible]

110
00:06:35,240 --> 00:06:38,100
Imprimer variables. Donc, si vous voulez faire un peu d'introspection à l'intérieur de votre programme

111
00:06:38,100 --> 00:06:41,500
sans avoir à recourir à l'écriture d'instructions printf un peu partout,

112
00:06:41,500 --> 00:06:44,600
il vous suffit d'imprimer une variable ou d'afficher une variable.

113
00:06:44,600 --> 00:06:46,710
Que pouvez-vous faire avec un débogueur GDB comme?

114
00:06:46,710 --> 00:06:49,170
[Réponse de l'étudiant, inintelligible]

115
00:06:49,170 --> 00:06:52,080
Exactement. Vous pouvez définir des points d'arrêt, vous pouvez dire l'exécution pause

116
00:06:52,080 --> 00:06:54,020
à la fonction principale ou la fonction foo.

117
00:06:54,020 --> 00:06:56,800
Vous pouvez dire que l'exécution pause à la ligne 123.

118
00:06:56,800 --> 00:06:58,950
Et les points d'arrêt sont une technique très puissante

119
00:06:58,950 --> 00:07:01,110
parce que si vous avez une idée générale de l'endroit où votre problème

120
00:07:01,110 --> 00:07:05,360
est probablement, vous n'avez pas à perdre du temps parcourant intégralité du programme.

121
00:07:05,360 --> 00:07:08,250
Vous pouvez sauter à droite essentiellement là-bas et puis commencez à taper -

122
00:07:08,250 --> 00:07:10,970
pas à pas à travers elle à l'étape suivante ou ou analogue.

123
00:07:10,970 --> 00:07:14,340
Mais le hic avec quelque chose comme GDB est qu'il vous aide, les ressources humaines,

124
00:07:14,340 --> 00:07:16,940
trouver vos problèmes et trouver des bugs.

125
00:07:16,940 --> 00:07:19,470
Elle ne trouvent pas nécessairement leur beaucoup pour vous.

126
00:07:19,470 --> 00:07:23,070
>> Donc, nous avons introduit le style50 autre jour, qui est un outil de commande en ligne à court

127
00:07:23,070 --> 00:07:27,500
qui tente de styliser votre code un peu plus propre que toi, l'être humain, pourrait avoir fait.

128
00:07:27,500 --> 00:07:29,530
Mais ça aussi, c'est vraiment juste une chose esthétique.

129
00:07:29,530 --> 00:07:34,110
Mais il s'avère qu'il ya cette autre outil appelé Valgrind qui est un peu plus obscure à utiliser.

130
00:07:34,110 --> 00:07:36,860
Sa sortie est atrocement énigmatique au premier abord.

131
00:07:36,860 --> 00:07:39,420
Mais il est merveilleusement utile, surtout maintenant que nous sommes dans la partie de l'expression

132
00:07:39,420 --> 00:07:43,080
où vous commencez à utiliser malloc et allocation dynamique de mémoire.

133
00:07:43,080 --> 00:07:45,420
Les choses peuvent aller très, très mal rapidement.

134
00:07:45,420 --> 00:07:49,320
Parce que si vous oubliez de libérer votre mémoire, ou vous déréférencez certains pointeur NULL,

135
00:07:49,320 --> 00:07:55,770
ou vous déréférencez certains pointeur de déchets, ce qui est généralement le symptôme que les résultats?

136
00:07:55,770 --> 00:07:59,470
Seg faute. Et vous obtenez ce fichier de base un certain nombre de kilo-octets ou méga-octets

137
00:07:59,470 --> 00:08:02,990
qui représente l'état de la mémoire de votre programme quand il s'est écrasé,

138
00:08:02,990 --> 00:08:05,730
mais votre programme en fin de compte seg défauts, faute de segmentation,

139
00:08:05,730 --> 00:08:08,450
ce qui signifie que quelque chose de mauvais s'est produit presque toujours liés

140
00:08:08,450 --> 00:08:11,750
d'une erreur liée à la mémoire que vous avez fait quelque part.

141
00:08:11,750 --> 00:08:14,100
Donc Valgrind vous aide à trouver des choses comme ça.

142
00:08:14,100 --> 00:08:17,720
C'est un outil que vous exécutez, comme GDB, une fois que vous avez compilé votre programme,

143
00:08:17,720 --> 00:08:20,330
mais plutôt que d'exécuter votre programme directement, vous exécutez Valgrind

144
00:08:20,330 --> 00:08:23,960
et vous lui passez votre programme, comme vous le faites avec GDB.

145
00:08:23,960 --> 00:08:26,220
Maintenant, l'utilisation, pour obtenir le meilleur type de sortie,

146
00:08:26,220 --> 00:08:30,410
est un peu long, donc là au sommet de l'écran, vous verrez Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" signifie verbose presque universellement lorsque vous utilisez des programmes sur un ordinateur Linux.

148
00:08:35,350 --> 00:08:38,770
Donc, cela signifie cracher plus de données que vous pourriez par défaut.

149
00:08:38,770 --> 00:08:45,510
»- Fuite-check = plein." Ceci est juste que chèque de toutes les fuites de mémoire possibles,

150
00:08:45,510 --> 00:08:49,430
erreurs que j'ai pu réaliser. Cela, aussi, est un paradigme commun avec des programmes Linux.

151
00:08:49,430 --> 00:08:52,710
En règle générale, si vous avez un argument de ligne de commande qui est un "switch",

152
00:08:52,710 --> 00:08:55,830
qui est censé modifier le comportement du programme, et c'est une seule lettre,

153
00:08:55,830 --> 00:09:00,310
c'est-v, mais si ça marche, tout simplement par la conception du programmeur,

154
00:09:00,310 --> 00:09:05,150
est un mot entier ou une série de mots, l'argument de ligne de commande commence par -.

155
00:09:05,150 --> 00:09:08,190
Ce ne sont que des conventions de l'homme, mais vous les verrez de plus en plus.

156
00:09:08,190 --> 00:09:12,410
Et puis, enfin, «a.out» est le nom arbitraire pour le programme dans cet exemple particulier.

157
00:09:12,410 --> 00:09:14,640
Et voici quelques sorties représentant.

158
00:09:14,640 --> 00:09:22,890
>> Avant de nous pencher sur ce que cela signifie, permettez-moi de passer à un extrait de code ici.

159
00:09:22,890 --> 00:09:26,390
Et laissez-moi passer ce hors de la voie, bientôt,

160
00:09:26,390 --> 00:09:32,120
et nous allons jeter un coup d'oeil à memory.c, qui est ce petit exemple ici.

161
00:09:32,120 --> 00:09:36,290
Donc, dans ce programme, permettez-moi de faire un zoom sur les fonctions et les questions.

162
00:09:36,290 --> 00:09:39,430
Nous avons une fonction principale qui appelle une fonction, f,

163
00:09:39,430 --> 00:09:45,590
et puis qu'est-ce que f procédez à faire, en anglais un peu technique?

164
00:09:45,590 --> 00:09:49,760
Qu'est-ce que f procéder à faire?

165
00:09:49,760 --> 00:09:53,680
Que diriez-vous, je vais commencer par la ligne 20, et l'emplacement de l'étoile n'a pas d'importance,

166
00:09:53,680 --> 00:09:56,720
mais je vais être compatible avec les dernière conférence ici.

167
00:09:56,720 --> 00:09:59,910
Quelle est la ligne 20 ne pour nous? Sur le côté gauche. Nous allons le décomposer davantage.

168
00:09:59,910 --> 00:10:02,410
Int * x: qu'est-ce que ça fait?

169
00:10:02,410 --> 00:10:04,940
D'accord. Il a déclarer un pointeur, et maintenant nous allons être encore plus technique.

170
00:10:04,940 --> 00:10:10,230
Qu'est-ce que ça veut dire, très concrètement, pour déclarer un pointeur? Quelqu'un d'autre?

171
00:10:10,230 --> 00:10:15,050
Ouais? [Réponse de l'étudiant, inintelligible] Trop loin.

172
00:10:15,050 --> 00:10:17,060
Alors que vous lisez à la droite du signe égal.

173
00:10:17,060 --> 00:10:20,290
Concentrons-nous juste sur la gauche, juste sur int * x.

174
00:10:20,290 --> 00:10:24,700
Cela ne "déclarer" un pointeur, mais maintenant, nous allons plonger plus profondément à cette définition.

175
00:10:24,700 --> 00:10:28,330
Qu'est-ce que concrètement, techniquement veut dire? Ouais?

176
00:10:28,330 --> 00:10:31,940
[Réponse de l'étudiant, inintelligible]

177
00:10:31,940 --> 00:10:35,090
D'accord. Il se prépare à enregistrer une adresse dans la mémoire.

178
00:10:35,090 --> 00:10:40,680
Bon. Et nous allons prendre un peu plus loin, c'est la déclaration d'une variable, x, c'est 32 bits.

179
00:10:40,680 --> 00:10:44,440
Et je sais que c'est parce que les 32 bits -?

180
00:10:44,440 --> 00:10:47,390
Ce n'est pas parce que c'est un int, parce que c'est un pointeur dans ce cas.

181
00:10:47,390 --> 00:10:49,650
Un hasard si c'est une seule et même chose avec un int,

182
00:10:49,650 --> 00:10:51,970
mais le fait qu'il ya l'étoile il signifie qu'il s'agit d'un pointeur

183
00:10:51,970 --> 00:10:57,300
et dans l'appareil, comme avec de nombreux ordinateurs, mais pas tous, les pointeurs sont 32 bits.

184
00:10:57,300 --> 00:11:01,850
Le matériel plus moderne comme les derniers Mac, les PC dernière génération, vous pourriez avoir des pointeurs 64 bits,

185
00:11:01,850 --> 00:11:04,160
mais dans l'appareil, ces choses sont de 32 bits.

186
00:11:04,160 --> 00:11:08,380
Donc, nous allons normaliser sur ce point. Plus concrètement, l'histoire se déroule comme suit:

187
00:11:08,380 --> 00:11:10,820
Nous "déclarer" un pointeur, ça veut dire quoi?

188
00:11:10,820 --> 00:11:12,810
Nous nous préparons à stocker une adresse mémoire.

189
00:11:12,810 --> 00:11:15,530
Qu'est-ce que ça veut dire?

190
00:11:15,530 --> 00:11:19,810
Nous créons une variable appelée x qui prend 32 bits

191
00:11:19,810 --> 00:11:23,810
qui sera bientôt stocker l'adresse d'un entier.

192
00:11:23,810 --> 00:11:26,470
Et c'est probablement à peu près aussi précis que nous pouvons obtenir.

193
00:11:26,470 --> 00:11:31,810
C'est très bien aller de l'avant afin de simplifier le monde et je dis juste déclarer un pointeur appelé x.

194
00:11:31,810 --> 00:11:35,380
Déclarer un pointeur, mais se rendre compte et de comprendre ce qui se passe réellement

195
00:11:35,380 --> 00:11:38,490
même dans ces quelques rares personnages.

196
00:11:38,490 --> 00:11:42,040
>> Maintenant, celui-ci est presque un peu plus facile, même si c'est une expression plus longue.

197
00:11:42,040 --> 00:11:48,160
Donc, ce qui est ce que ça fait, ça a souligné aujourd'hui: «malloc (10 * sizeof (int));" Ouais?

198
00:11:48,160 --> 00:11:52,350
[Réponse de l'étudiant, inintelligible]

199
00:11:52,350 --> 00:11:58,250
Bon. Et je vais le prendre là-bas. C'est allocation d'un bloc de mémoire pour dix entiers.

200
00:11:58,250 --> 00:12:02,190
Et maintenant, nous allons plonger dans un peu plus profond, c'est l'attribution d'un bloc de mémoire pour dix entiers.

201
00:12:02,190 --> 00:12:05,390
Quel est alors le retour de malloc?

202
00:12:05,390 --> 00:12:10,390
L'adresse de ce morceau, ou, plus concrètement, l'adresse du premier octet de ce morceau.

203
00:12:10,390 --> 00:12:14,080
Comment alors que je suis, le programmeur, de savoir où ce morceau de mémoire doit se terminer?

204
00:12:14,080 --> 00:12:18,340
Je sais que c'est contigus. Malloc, par définition, vous donnera un espace contigu de mémoire.

205
00:12:18,340 --> 00:12:21,240
Aucune lacune en elle. Vous avez accès à tous les octets dans ce morceau,

206
00:12:21,240 --> 00:12:26,760
dos à dos à dos, mais comment puis-je savoir où la fin de ce morceau de mémoire est?

207
00:12:26,760 --> 00:12:28,850
Lorsque vous utilisez malloc? [Réponse de l'étudiant, inintelligible] Bon.

208
00:12:28,850 --> 00:12:30,670
Vous n'avez pas. Vous devez vous rappeler.

209
00:12:30,670 --> 00:12:35,960
Je dois me rappeler que j'ai utilisé la valeur 10, et je ne semble même pas avoir fait ici.

210
00:12:35,960 --> 00:12:41,000
Mais le fardeau de la preuve repose entièrement sur moi. Strlen, que nous sommes devenus un peu tributaire des chaînes,

211
00:12:41,000 --> 00:12:45,860
fonctionne uniquement en raison de cette convention d'avoir \ 0

212
00:12:45,860 --> 00:12:48,840
ou ce caractère spécial nul, NUL, à la fin d'une chaîne.

213
00:12:48,840 --> 00:12:51,740
Cela ne tient pas seulement pour les morceaux arbitraires de la mémoire.

214
00:12:51,740 --> 00:12:58,590
C'est à vous. Ainsi, la ligne 20, puis, alloue un bloc de mémoire

215
00:12:58,590 --> 00:13:02,590
qui peut stocker des dix nombres entiers, et elle stocke l'adresse du premier octet

216
00:13:02,590 --> 00:13:05,610
de ce bloc de mémoire de la variable x appelé.

217
00:13:05,610 --> 00:13:11,140
Ergo, qui est un pointeur. Ainsi, la ligne 21, malheureusement, c'était une erreur.

218
00:13:11,140 --> 00:13:16,110
Mais tout d'abord, que fait-il? Elle dit magasin à l'emplacement 10, 0 indexées,

219
00:13:16,110 --> 00:13:19,480
du morceau de la mémoire appelée x la valeur 0.

220
00:13:19,480 --> 00:13:21,510
>> Donc remarquer un certain nombre de choses sont en cours.

221
00:13:21,510 --> 00:13:25,420
Même si x est un pointeur, rappelle il ya quelques semaines

222
00:13:25,420 --> 00:13:29,440
que vous pouvez toujours utiliser la notation de tableau de style carré support.

223
00:13:29,440 --> 00:13:36,180
Parce que c'est en fait l'abréviation main notation pour l'arithmétique des pointeurs plus cryptique l'avenir.

224
00:13:36,180 --> 00:13:40,320
où l'on ferait quelque chose comme ceci: Prenez l'adresse x, se déplacer de 10 points au-dessus de,

225
00:13:40,320 --> 00:13:44,550
puis aller à ce que l'adresse est stockée à cet emplacement.

226
00:13:44,550 --> 00:13:48,090
Mais franchement, c'est juste atroce à lire et se familiariser avec.

227
00:13:48,090 --> 00:13:52,900
Ainsi, le monde utilise généralement les crochets juste parce que c'est tellement plus humain-amical à lire.

228
00:13:52,900 --> 00:13:55,140
Mais c'est ce qui se passe vraiment sous le capot;

229
00:13:55,140 --> 00:13:58,190
x est une adresse, pas un tableau en soi.

230
00:13:58,190 --> 00:14:02,410
Donc, ce n'est stockage 0 à l'emplacement 10 dans x.

231
00:14:02,410 --> 00:14:06,120
Pourquoi est-ce mauvais? Ouais?

232
00:14:06,120 --> 00:14:17,370
[Réponse de l'étudiant, inintelligible] Exactement.

233
00:14:17,370 --> 00:14:21,100
Nous avons seulement attribuer dix entiers, mais nous comptons de 0 lors de la programmation en C,

234
00:14:21,100 --> 00:14:25,690
si vous avez accès à 0 10 1 2 3 4 5 6 7 8 9 mais non.

235
00:14:25,690 --> 00:14:30,270
Alors, soit le programme va à la faute segment ou il n'est pas.

236
00:14:30,270 --> 00:14:32,900
Mais nous ne savons pas vraiment, ce qui est une sorte de comportement non déterministe.

237
00:14:32,900 --> 00:14:35,600
Cela dépend vraiment de savoir si nous sommes chanceux.

238
00:14:35,600 --> 00:14:40,650
S'il s'avère que le système d'exploitation ne me dérange pas si je utiliser cet octet supplémentaire,

239
00:14:40,650 --> 00:14:43,360
même si elle ne l'a pas donné à moi, mon programme pourrait ne pas tomber en panne.

240
00:14:43,360 --> 00:14:46,780
Il est brut, c'est buggé, mais vous ne pourriez pas voir ce symptôme,

241
00:14:46,780 --> 00:14:48,960
ou vous pouvez le voir seulement de temps en temps.

242
00:14:48,960 --> 00:14:51,230
Mais la réalité est que le bogue est, en fait, là-bas.

243
00:14:51,230 --> 00:14:54,320
Et c'est vraiment un problème si vous avez écrit un programme qui vous voulez être correcte,

244
00:14:54,320 --> 00:14:58,840
que vous avez vendu le programme que les gens utilisent que chaque de temps en temps se bloque

245
00:14:58,840 --> 00:15:02,450
parce que, bien sûr, ce n'est pas bon. En fait, si vous avez un téléphone Android ou un iPhone

246
00:15:02,450 --> 00:15:05,550
et vous télécharger des applications de nos jours, si vous avez déjà eu une application tout simplement arrêter,

247
00:15:05,550 --> 00:15:10,040
tout d'un coup il disparaît, c'est presque toujours le résultat d'un problème lié à la mémoire,

248
00:15:10,040 --> 00:15:12,830
où le programmeur foutu et un pointeur déréférencé

249
00:15:12,830 --> 00:15:18,670
qu'il ou elle ne devrait pas avoir, et le résultat de l'iOS ou Android est juste de tuer le programme tout à fait

250
00:15:18,670 --> 00:15:23,080
plutôt que le comportement est indéterminé risque ou une sorte de compromis de sécurité.

251
00:15:23,080 --> 00:15:25,950
>> Il ya un autre bug dans ce programme en plus de celui-ci.

252
00:15:25,950 --> 00:15:30,180
Qu'ai-je raté dans ce programme?

253
00:15:30,180 --> 00:15:32,740
Je n'ai pas pratiqué ce que j'ai prêché. Ouais?

254
00:15:32,740 --> 00:15:34,760
[Réponse de l'étudiant, inintelligible] Bon.

255
00:15:34,760 --> 00:15:36,880
Je n'ai pas libéré de la mémoire. Donc, la règle d'or maintenant

256
00:15:36,880 --> 00:15:43,150
doit être à tout moment vous appeler malloc, vous devez appeler gratuitement lorsque vous avez fini d'utiliser cette mémoire.

257
00:15:43,150 --> 00:15:45,610
Maintenant, quand devrais-je libérer cette mémoire?

258
00:15:45,610 --> 00:15:49,780
Probablement, en supposant que cette première ligne était correcte, je veux le faire ici.

259
00:15:49,780 --> 00:15:55,710
Parce que je ne pouvais pas, par exemple, le faire ici-bas. Pourquoi?

260
00:15:55,710 --> 00:15:57,860
Juste hors de portée. Ainsi, même si nous parlons de pointeurs,

261
00:15:57,860 --> 00:16:04,830
c'est une semaine 2 ou 3 question, où x est seulement une portée à l'intérieur des accolades où elle a été déclarée.

262
00:16:04,830 --> 00:16:11,000
Alors vous avez certainement ne peut pas le libérer là-bas. Ma seule chance pour la libérer est à peu près après la ligne 21.

263
00:16:11,000 --> 00:16:15,170
Il s'agit d'un programme assez simple, il est assez facile une fois que vous sorte de votre esprit enveloppé

264
00:16:15,170 --> 00:16:17,870
autour de ce que le programme fasse, où les erreurs ont été.

265
00:16:17,870 --> 00:16:20,500
Et même si vous ne le voyez pas dans un premier temps, j'espère que c'est un peu évident maintenant

266
00:16:20,500 --> 00:16:23,870
que ces erreurs sont assez faciles à résoudre et facile à faire.

267
00:16:23,870 --> 00:16:28,720
Mais quand un programme est de plus de 12 lignes de long, c'est 50 lignes, 100 lignes de long,

268
00:16:28,720 --> 00:16:31,150
marche à travers votre code ligne par ligne, en pensant par là logiquement,

269
00:16:31,150 --> 00:16:35,110
est possible, mais pas particulièrement amusant à faire, sans cesse à la recherche de bugs,

270
00:16:35,110 --> 00:16:38,340
et il est aussi difficile à faire, et c'est pourquoi un outil comme Valgrind existe.

271
00:16:38,340 --> 00:16:40,900
Laissez-moi aller de l'avant et faire ceci: laissez-moi ouvrir ma fenêtre de terminal,

272
00:16:40,900 --> 00:16:45,400
et ne me laisse pas il suffit d'exécuter la mémoire, car la mémoire semble bien se passer.

273
00:16:45,400 --> 00:16:49,180
Je deviens chanceux. Qui va octet supplémentaire à la fin de la matrice

274
00:16:49,180 --> 00:16:51,060
ne semble pas y avoir trop de problèmes.

275
00:16:51,060 --> 00:16:56,370
Mais permettez-moi, tout de même, faire un test de cohérence, ce qui signifie juste pour vérifier

276
00:16:56,370 --> 00:16:58,320
si oui ou non il s'agit en fait correcte.

277
00:16:58,320 --> 00:17:04,690
>> Alors, faisons valgrind-v - Fuite-check = plein,

278
00:17:04,690 --> 00:17:07,520
puis le nom du programme dans ce cas est la mémoire, pas a.out.

279
00:17:07,520 --> 00:17:10,760
Alors laissez-moi aller de l'avant et de le faire. Appuyez sur Entrée.

280
00:17:10,760 --> 00:17:14,109
Cher Dieu. Il s'agit de sa sortie, et c'est ce que je faisais allusion tout à l'heure.

281
00:17:14,109 --> 00:17:17,550
Mais, si vous apprenez à lire toutes les bêtises ici,

282
00:17:17,550 --> 00:17:20,760
plupart de ceci est juste sortie de diagnostic, ce n'est pas très intéressant.

283
00:17:20,760 --> 00:17:24,829
Que votre œil veut vraiment être cherchez est fait mention de l'erreur ou non valide.

284
00:17:24,829 --> 00:17:26,800
Les mots qui suggèrent des problèmes.

285
00:17:26,800 --> 00:17:29,340
Et en effet, nous allons voir ce qui va mal ici-bas.

286
00:17:29,340 --> 00:17:35,230
J'ai un résumé en quelque sorte, «en usage à la sortie:. 40 octets de blocs de 1"

287
00:17:35,230 --> 00:17:38,750
Je ne suis pas vraiment sûr de ce bloc est encore, mais 40 octets

288
00:17:38,750 --> 00:17:41,260
sent réellement comme je pouvais trouver où ça vient.

289
00:17:41,260 --> 00:17:45,030
40 octets. Pourquoi sont 40 octets en usage à la sortie?

290
00:17:45,030 --> 00:17:48,780
Et plus précisément, si nous défiler vers le bas ici,

291
00:17:48,780 --> 00:17:54,520
pourquoi ai-je définitivement perdu 40 octets? Ouais?

292
00:17:54,520 --> 00:17:59,520
[Réponse de l'étudiant, inintelligible] Parfait. Oui, exactement.

293
00:17:59,520 --> 00:18:03,540
Il y avait dix entiers, et chacun d'entre eux est la taille de 4 ou 32 bits,

294
00:18:03,540 --> 00:18:08,300
donc j'ai perdu exactement 40 octets parce que, comme vous l'avez proposé, je n'ai pas dit libre.

295
00:18:08,300 --> 00:18:13,460
C'est un bug, et maintenant nous allons regarder vers le bas un peu plus loin et de voir à côté de cela,

296
00:18:13,460 --> 00:18:16,900
«Invalide écrire de taille 4." Maintenant, c'est quoi?

297
00:18:16,900 --> 00:18:21,150
Cette adresse est exprimée la notation de base ce qui, apparemment?

298
00:18:21,150 --> 00:18:23,640
C'est hexadécimal, et chaque fois que vous voyez un numéro commençant par 0x,

299
00:18:23,640 --> 00:18:29,410
cela signifie hexadécimal, que nous avons fait le chemin du retour, je pense, l'article pset 0 de questions,

300
00:18:29,410 --> 00:18:34,090
qui était juste de faire un exercice d'échauffement, la conversion de décimal en hexadécimal en binaire et ainsi de suite.

301
00:18:34,090 --> 00:18:39,220
Hexadécimal, juste par convention humaine, est généralement utilisé pour représenter des pointeurs

302
00:18:39,220 --> 00:18:41,570
ou, plus généralement, les adresses. C'est juste une convention,

303
00:18:41,570 --> 00:18:45,340
parce que c'est un peu plus facile à lire, c'est un peu plus compact que quelque chose comme décimal,

304
00:18:45,340 --> 00:18:47,720
et binaire est inutile pour la plupart des êtres humains à utiliser.

305
00:18:47,720 --> 00:18:50,840
Alors maintenant, qu'est-ce que cela signifie? Eh bien, on dirait qu'il s'agit d'une écriture non valide

306
00:18:50,840 --> 00:18:54,480
de taille 4 à la ligne 21 du memory.c.

307
00:18:54,480 --> 00:18:59,180
Donc, revenons à la ligne 21, et en effet, c'est ici que nulle écriture.

308
00:18:59,180 --> 00:19:02,640
Donc, Valgrind ne va pas tout à fait tenir ma main et me dire ce que la solution est,

309
00:19:02,640 --> 00:19:05,520
mais il détecte que je fais une écriture non valide.

310
00:19:05,520 --> 00:19:08,800
Je touche 4 octets qui je ne serais pas, et apparemment c'est parce que,

311
00:19:08,800 --> 00:19:13,960
comme vous l'avez souligné, je fais [10] au lieu de [9] au maximum

312
00:19:13,960 --> 00:19:16,660
ou [0] ou quelque chose entre les deux.

313
00:19:16,660 --> 00:19:19,690
Avec Valgrind, de réaliser n'importe quel moment vous êtes en train d'écrire un programme

314
00:19:19,690 --> 00:19:24,190
qui utilise des pointeurs et utilise de la mémoire, et malloc, plus précisément,

315
00:19:24,190 --> 00:19:27,080
certainement prendre l'habitude de courir aussi longtemps

316
00:19:27,080 --> 00:19:30,890
mais très facilement copié et collé le commandement de Valgrind

317
00:19:30,890 --> 00:19:32,650
pour voir si il ya des erreurs qui s'y trouvent.

318
00:19:32,650 --> 00:19:34,820
Et ça va être énorme à chaque fois que vous voyez la sortie,

319
00:19:34,820 --> 00:19:39,430
mais simplement analyser visuellement à travers toute la production et de voir si vous voyez des erreurs mentionne

320
00:19:39,430 --> 00:19:43,190
ou des avertissements ou invalide ou perdu.

321
00:19:43,190 --> 00:19:46,200
Tous les mots qui vous ressemble vissés quelque part.

322
00:19:46,200 --> 00:19:48,580
Alors rends compte que c'est un nouvel outil dans votre boîte à outils.

323
00:19:48,580 --> 00:19:51,270
>> Maintenant, le lundi, nous avons eu tout un tas de gens viennent ici

324
00:19:51,270 --> 00:19:53,150
et représenter la notion d'une liste chaînée.

325
00:19:53,150 --> 00:20:00,970
Et nous avons introduit la liste chaînée comme une solution à ce problème?

326
00:20:00,970 --> 00:20:04,590
Ouais? [Réponse de l'étudiant, inintelligible] Bon.

327
00:20:04,590 --> 00:20:06,530
Les tableaux ne peuvent pas avoir la mémoire ajoutée.

328
00:20:06,530 --> 00:20:09,440
Si vous allouer un tableau de taille 10, c'est tout ce que vous obtenez.

329
00:20:09,440 --> 00:20:13,690
Vous pouvez appeler une fonction comme realloc si vous avez initialement appelé malloc,

330
00:20:13,690 --> 00:20:17,580
et qui peut tenter d'augmenter le tableau si l'espace vers l'extrémité de celui-ci

331
00:20:17,580 --> 00:20:21,610
que personne d'autre utilise, et s'il n'y a pas, il va juste te trouver une plus grosse part ailleurs.

332
00:20:21,610 --> 00:20:25,040
Mais alors, il va copier tous les octets dans le nouveau tableau.

333
00:20:25,040 --> 00:20:28,310
Cela sonne comme une solution très correcte.

334
00:20:28,310 --> 00:20:34,790
Pourquoi est-ce disgracieux?

335
00:20:34,790 --> 00:20:36,940
Je veux dire que cela fonctionne, les humains ont résolu ce problème.

336
00:20:36,940 --> 00:20:40,710
Pourquoi avons-nous besoin de le résoudre, lundi, avec des listes chaînées? Ouais?

337
00:20:40,710 --> 00:20:44,060
[Réponse de l'étudiant, inintelligible] Il pourrait prendre un certain temps.

338
00:20:44,060 --> 00:20:49,260
En fait, chaque fois que vous appelez malloc ou calloc ou realloc, ce qui est encore un autre,

339
00:20:49,260 --> 00:20:52,470
chaque fois que vous, le programme, parlons du système d'exploitation,

340
00:20:52,470 --> 00:20:54,310
vous avez tendance à ralentir le programme.

341
00:20:54,310 --> 00:20:57,470
Et si vous faites ce genre de choses dans les boucles, vous êtes vraiment ralentir les choses.

342
00:20:57,470 --> 00:21:00,740
Tu ne vas pas à le remarquer pour la plus simple des programmes de "Hello World" de type,

343
00:21:00,740 --> 00:21:04,300
mais dans des programmes beaucoup plus importants, en demandant au système d'exploitation encore et encore pour la mémoire

344
00:21:04,300 --> 00:21:07,520
ou de la remettre encore et encore tendance à ne pas être une bonne chose.

345
00:21:07,520 --> 00:21:11,210
De plus, c'est juste une sorte de plan intellectuel - c'est une perte de temps totale.

346
00:21:11,210 --> 00:21:16,490
Pourquoi allouer de la mémoire de plus en plus, le risque de copier tout dans le nouveau tableau,

347
00:21:16,490 --> 00:21:21,980
si vous avez une alternative qui vous permet d'allouer de la mémoire seulement autant que vous avez réellement besoin?

348
00:21:21,980 --> 00:21:24,130
Il ya donc des avantages et des inconvénients dans ici.

349
00:21:24,130 --> 00:21:26,730
Un des avantages est que nous avons dynamisme.

350
00:21:26,730 --> 00:21:29,100
Peu importe où les segments de mémoire sont qui sont libres,

351
00:21:29,100 --> 00:21:32,070
Je peux juste une sorte de créer ces miettes de pain via les pointeurs

352
00:21:32,070 --> 00:21:34,470
d'enchaîner ma liste entière reliés entre eux.

353
00:21:34,470 --> 00:21:36,470
Mais je payer au moins un prix.

354
00:21:36,470 --> 00:21:40,060
>> Que dois-je renoncer à obtenir des listes chaînées?

355
00:21:40,060 --> 00:21:42,470
Ouais? [Réponse de l'étudiant, inintelligible] Bon.

356
00:21:42,470 --> 00:21:45,650
Vous avez besoin de plus de mémoire. Maintenant, j'ai besoin d'espace pour ces pointeurs,

357
00:21:45,650 --> 00:21:47,900
et dans le cas de cette liste liée simple, super-

358
00:21:47,900 --> 00:21:51,410
qui ne cherche qu'à stocker des entiers, qui sont 4 octets, nous disons

359
00:21:51,410 --> 00:21:54,240
De plus, un pointeur de 4 octets, alors maintenant je suis littéralement doublé

360
00:21:54,240 --> 00:21:57,290
la quantité de mémoire J'ai besoin juste pour stocker cette liste.

361
00:21:57,290 --> 00:21:59,680
Mais encore une fois, c'est un compromis constant en informatique

362
00:21:59,680 --> 00:22:03,440
entre le temps et l'espace et le développement, l'effort et d'autres ressources.

363
00:22:03,440 --> 00:22:06,630
Ce qui est un autre inconvénient de l'utilisation d'une liste chaînée? Ouais?

364
00:22:06,630 --> 00:22:10,150
[Réponse de l'étudiant, inintelligible]

365
00:22:10,150 --> 00:22:12,600
Bon. Pas aussi facile d'accès. On ne peut plus tirer parti de

366
00:22:12,600 --> 00:22:15,530
semaine 0 comme principes diviser pour régner.

367
00:22:15,530 --> 00:22:18,220
Et plus précisément, la recherche binaire. Parce que même si nous, les humains

368
00:22:18,220 --> 00:22:20,400
peut voir à peu près où le milieu de cette liste est,

369
00:22:20,400 --> 00:22:25,840
l'ordinateur ne connaît que cette liste chaînée commence à l'adresse appelée en premier.

370
00:22:25,840 --> 00:22:28,250
Et c'est 0x123 ou quelque chose comme ça.

371
00:22:28,250 --> 00:22:30,990
Et la seule façon le programme peut trouver l'élément central

372
00:22:30,990 --> 00:22:33,350
est en fait de rechercher toute la liste.

373
00:22:33,350 --> 00:22:35,500
Et même alors, il a littéralement pour rechercher toute la liste parce

374
00:22:35,500 --> 00:22:38,950
même une fois que vous atteignez l'élément central en suivant les pointeurs,

375
00:22:38,950 --> 00:22:42,380
vous, le programme, n'ont aucune idée de combien de temps cette liste est, potentiellement,

376
00:22:42,380 --> 00:22:45,250
jusqu'à ce que vous atteignez la fin de celui-ci, et comment savez-vous par programmation

377
00:22:45,250 --> 00:22:48,600
que vous êtes à la fin d'une liste chaînée?

378
00:22:48,600 --> 00:22:51,120
Il s'agit d'un pointeur NULL spéciale, à nouveau, une convention.

379
00:22:51,120 --> 00:22:53,870
Plutôt que d'utiliser ce pointeur, nous ne voulons certainement pas que ce soit une valeur ordures

380
00:22:53,870 --> 00:22:57,750
pointant hors de la scène, quelque part, nous voulons que ce soit la main vers le bas, NULL,

381
00:22:57,750 --> 00:23:01,530
afin que nous ayons ce terminus dans cette structure de données afin de savoir où elle se termine.

382
00:23:01,530 --> 00:23:03,410
>> Que faire si nous voulons manipuler ce?

383
00:23:03,410 --> 00:23:05,980
Nous avons fait plus de cela visuellement, et avec les humains,

384
00:23:05,980 --> 00:23:07,630
mais que faire si nous voulons faire une insertion?

385
00:23:07,630 --> 00:23:12,360
Ainsi, la liste initiale était de 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Et si on a ensuite voulu espace malloc pour le numéro 55, un nœud pour elle,

387
00:23:16,730 --> 00:23:20,730
puis nous voulons insérer 55 dans la liste comme nous l'avons fait le lundi?

388
00:23:20,730 --> 00:23:23,690
Comment pouvons-nous faire cela? Eh bien, Anita est arrivé et elle a essentiellement marchait dans la liste.

389
00:23:23,690 --> 00:23:27,500
Elle a commencé le premier élément, puis la suivante, l'autre, l'autre, l'autre, le lendemain.

390
00:23:27,500 --> 00:23:29,500
Enfin frappé la gauche tout en bas

391
00:23:29,500 --> 00:23:34,480
et réalisé oh, c'est la valeur NULL. Donc manipulation de pointeurs ce qui devait être fait?

392
00:23:34,480 --> 00:23:37,980
La personne qui se trouvait à la fin, numéro 34, avait besoin de sa main gauche levée

393
00:23:37,980 --> 00:23:46,220
pour pointer à 55, 55 avaient besoin de leur bras gauche vers le bas pour être le nouveau terminateur NULL. Terminé.

394
00:23:46,220 --> 00:23:49,540
Assez facile à insérer 55 dans une liste triée.

395
00:23:49,540 --> 00:23:51,800
Et comment cela pourrait-il regarder?

396
00:23:51,800 --> 00:23:55,690
>> Permettez-moi aller de l'avant et d'ouvrir quelques exemple de code ici.

397
00:23:55,690 --> 00:23:58,120
Je vais ouvrir gedit, et laissez-moi ouvrir deux fichiers en premier.

398
00:23:58,120 --> 00:24:02,050
L'un est list1.h, et laissez-moi vous rappeler que c'était le morceau de code

399
00:24:02,050 --> 00:24:04,920
que nous avons utilisé pour représenter un nœud.

400
00:24:04,920 --> 00:24:13,040
Un nœud possède à la fois un int appelé n et un pointeur appelé prochain juste des points à la chose suivante dans la liste.

401
00:24:13,040 --> 00:24:15,450
C'est désormais dans un fichier. H. Pourquoi?

402
00:24:15,450 --> 00:24:19,090
Il ya cette convention, et nous n'avons pas profité de cette énorme quantité de nous-mêmes,

403
00:24:19,090 --> 00:24:22,220
mais la personne qui a écrit fonctions printf et autres

404
00:24:22,220 --> 00:24:27,150
donné comme un cadeau pour le monde de toutes ces fonctions en écrivant un fichier appelé stdio.h.

405
00:24:27,150 --> 00:24:30,950
Et puis il ya string.h, et puis il ya map.h, et il ya tous ces fichiers h

406
00:24:30,950 --> 00:24:34,410
que vous pourriez avoir vu ou utilisé pendant la durée écrit par d'autres personnes.

407
00:24:34,410 --> 00:24:38,470
En général, dans les fichiers. H sont les seules choses comme typedefs

408
00:24:38,470 --> 00:24:42,310
ou des déclarations de types personnalisés ou des déclarations de constantes.

409
00:24:42,310 --> 00:24:47,890
Vous ne mettez pas les implémentations des fonctions »dans les fichiers d'en-tête.

410
00:24:47,890 --> 00:24:50,570
Vous avez mis, au contraire, seulement leurs prototypes.

411
00:24:50,570 --> 00:24:53,050
Vous mettez les choses que vous voulez partager avec le monde ce dont ils ont besoin

412
00:24:53,050 --> 00:24:55,640
afin de compiler leur code. Donc, juste pour entrer dans cette habitude,

413
00:24:55,640 --> 00:24:59,110
nous avons décidé de faire la même chose. Il n'ya pas beaucoup de list1.h,

414
00:24:59,110 --> 00:25:02,070
mais nous avons mis quelque chose qui pourrait être d'intérêt pour les gens dans le monde

415
00:25:02,070 --> 00:25:05,030
qui veulent utiliser notre implémentation liste chaînée.

416
00:25:05,030 --> 00:25:08,040
Maintenant, dans list1.c, je ne vais pas passer par toute cette affaire

417
00:25:08,040 --> 00:25:11,390
parce que c'est un peu long, ce programme, mais nous allons l'exécuter réel rapidement à l'invite.

418
00:25:11,390 --> 00:25:15,720
Permettez-moi de compiler list1, permettez-moi alors de fonctionner list1 et ce que vous verrez est

419
00:25:15,720 --> 00:25:18,070
nous avons simulé un programme simple peu ici

420
00:25:18,070 --> 00:25:20,990
qui va me permettre d'ajouter et de supprimer des numéros à une liste.

421
00:25:20,990 --> 00:25:24,310
Alors laissez-moi aller de l'avant et de type 3 pour les 3 options du menu.

422
00:25:24,310 --> 00:25:27,880
Je veux insérer le nombre - nous allons faire le premier numéro, qui était de 9,

423
00:25:27,880 --> 00:25:30,550
et maintenant je me dit que la liste est maintenant 9.

424
00:25:30,550 --> 00:25:33,760
Permettez-moi aller de l'avant et faire une autre insertion, alors j'ai frappé l'option 3 du menu.

425
00:25:33,760 --> 00:25:36,760
Quel numéro dois-je veux insérer? 17.

426
00:25:36,760 --> 00:25:39,220
Entrée. Et je ferai juste un plus.

427
00:25:39,220 --> 00:25:41,720
Permettez-moi d'insérer le numéro 22.

428
00:25:41,720 --> 00:25:45,850
Nous avons donc les débuts de la liste chaînée que nous avions sous forme de diaporama il ya un instant.

429
00:25:45,850 --> 00:25:48,740
Comment est cette insertion se passe réellement?

430
00:25:48,740 --> 00:25:52,000
En effet, 22 est maintenant à la fin de la liste.

431
00:25:52,000 --> 00:25:55,050
Donc, l'histoire nous dit sur scène le lundi et récapitulé tout à l'heure

432
00:25:55,050 --> 00:25:57,460
doit effectivement être le cas dans le code.

433
00:25:57,460 --> 00:25:59,700
Jetons un coup d'oeil. Permettez-moi de faire défiler vers le bas dans ce fichier.

434
00:25:59,700 --> 00:26:01,720
Nous allons passer rapidement sur certaines fonctions,

435
00:26:01,720 --> 00:26:05,630
mais nous allons descendre à, disons, la fonction d'insertion.

436
00:26:05,630 --> 00:26:11,720
>> Voyons comment nous allons sur l'insertion d'un nouveau nœud dans cette liste chaînée.

437
00:26:11,720 --> 00:26:14,550
Où est la liste déclarée? Eh bien, nous allons faire défiler tout le chemin vers le sommet,

438
00:26:14,550 --> 00:26:19,970
et remarquez que ma liste est liée essentiellement déclaré comme un pointeur unique qui est initialement NULL.

439
00:26:19,970 --> 00:26:23,180
Donc, je suis en utilisant une variable globale ici, qui en général nous avons prêché contre

440
00:26:23,180 --> 00:26:25,280
parce que cela rend votre code un peu désordonné de maintenir,

441
00:26:25,280 --> 00:26:29,080
C'est en quelque sorte de paresseux, le plus souvent, mais ce n'est pas paresseux et ce n'est pas mal et c'est pas mal

442
00:26:29,080 --> 00:26:33,660
si le seul but de votre programme dans la vie est de simuler une liste chaînée.

443
00:26:33,660 --> 00:26:35,460
Ce qui est exactement ce que nous faisons.

444
00:26:35,460 --> 00:26:39,100
Ainsi, plutôt que de déclarer cela en principal et ensuite de le transmettre à toutes les fonctions

445
00:26:39,100 --> 00:26:42,640
nous avons écrit à ce programme, nous avons plutôt réaliser oh, disons simplement la rendre globale

446
00:26:42,640 --> 00:26:47,060
parce que le but de ce programme est de démontrer une et une seule liste chaînée.

447
00:26:47,060 --> 00:26:50,700
Alors qui se sent bien. Voici mes prototypes, et nous n'allons pas passer par tout cela,

448
00:26:50,700 --> 00:26:55,800
mais j'ai écrit une fonction de suppression, une fonction de recherche, une fonction d'insertion, et une fonction transversale.

449
00:26:55,800 --> 00:26:59,080
Mais nous allons maintenant redescendre à la fonction d'insertion

450
00:26:59,080 --> 00:27:01,490
et de voir comment celui-ci fonctionne ici.

451
00:27:01,490 --> 00:27:09,940
Insérer est en ligne - ici nous allons.

452
00:27:09,940 --> 00:27:12,850
Insérez. Donc, il ne prend aucun argument, parce que nous allons demander à

453
00:27:12,850 --> 00:27:15,930
l'intérieur d'utilisateur de cette fonction pour le nombre qu'ils veulent insérer.

454
00:27:15,930 --> 00:27:19,410
Mais d'abord, nous nous préparons à leur donner un peu d'espace.

455
00:27:19,410 --> 00:27:22,050
C'est une sorte de copier-coller à partir de l'exemple des autres.

456
00:27:22,050 --> 00:27:25,110
Dans ce cas, nous avons été l'attribution d'un int, cette fois, nous allouons un nœud.

457
00:27:25,110 --> 00:27:27,910
Je ne me souviens pas vraiment combien d'octets est un nœud, mais c'est très bien.

458
00:27:27,910 --> 00:27:30,460
Sizeof peut comprendre cela pour moi.

459
00:27:30,460 --> 00:27:33,340
Et pourquoi suis-je vérifier pour NULL dans la ligne 120?

460
00:27:33,340 --> 00:27:37,530
Qu'est-ce qui pourrait mal tourner dans la ligne 119? Ouais?

461
00:27:37,530 --> 00:27:40,530
[Réponse de l'étudiant, inintelligible]

462
00:27:40,530 --> 00:27:43,440
Bon. Tout pourrait être le cas que j'ai demandé trop de mémoire

463
00:27:43,440 --> 00:27:47,020
ou quelque chose ne va pas et le système d'exploitation ne dispose pas de suffisamment d'octets à me donner,

464
00:27:47,020 --> 00:27:50,640
il signale autant en retournant NULL, et si je ne vérifie pas que

465
00:27:50,640 --> 00:27:54,710
et je aveuglément continuer à utiliser l'adresse de retour, il pourrait être NULL.

466
00:27:54,710 --> 00:27:58,400
Il pourrait y avoir une valeur inconnue, pas une bonne chose si je ne -

467
00:27:58,400 --> 00:28:00,590
fait ne sera pas une valeur inconnue. Il pourrait être NULL, alors je ne veux pas

468
00:28:00,590 --> 00:28:02,550
à en abuser et de risquer de le déréférencement.

469
00:28:02,550 --> 00:28:07,410
Si cela arrive, je viens de rentrer et nous allons faire comme si je n'avais pas récupérer toute la mémoire du tout.

470
00:28:07,410 --> 00:28:12,270
>> Sinon, je dis à l'utilisateur me donner un numéro à insérer, j'appelle notre getInt vieil ami,

471
00:28:12,270 --> 00:28:15,530
puis ce fut la nouvelle syntaxe, nous avons présenté le lundi.

472
00:28:15,530 --> 00:28:20,320
«Newptr-> n 'signifie prendre l'adresse qui vous a été donné par malloc

473
00:28:20,320 --> 00:28:23,490
qui représente le premier octet d'un objet nouveau noeud,

474
00:28:23,490 --> 00:28:26,860
puis aller sur le terrain appelé n.

475
00:28:26,860 --> 00:28:35,270
Une petite question quiz: Ceci est équivalent à ce que la ligne plus énigmatique de code?

476
00:28:35,270 --> 00:28:38,110
Comment aurais-je pu écrire ce? Vous voulez prendre un coup de poignard?

477
00:28:38,110 --> 00:28:41,480
[Réponse de l'étudiant, inintelligible]

478
00:28:41,480 --> 00:28:44,870
Bon. Utilisation de la n., Mais ce n'est pas tout à fait aussi simple que cela.

479
00:28:44,870 --> 00:28:47,090
Qu'est-ce que je dois d'abord faire? [Réponse de l'étudiant, inintelligible]

480
00:28:47,090 --> 00:28:52,730
Bon. J'ai besoin de faire newptr.n *.

481
00:28:52,730 --> 00:28:55,610
Donc, cela veut dire nouveau pointeur est évidemment une adresse. Pourquoi?

482
00:28:55,610 --> 00:28:59,520
Parce qu'elle a été renvoyée par malloc. Le newptr * disant: «y aller»,

483
00:28:59,520 --> 00:29:02,970
puis une fois que vous y êtes, vous pouvez alors utiliser le plus familier. n,

484
00:29:02,970 --> 00:29:05,730
mais cela ressemble un peu laid, surtout si nous, les humains vont

485
00:29:05,730 --> 00:29:10,360
tirer des pointeurs avec des flèches tout le temps, le monde a standardisé sur cette notation fléchée,

486
00:29:10,360 --> 00:29:12,320
qui fait exactement la même chose.

487
00:29:12,320 --> 00:29:16,070
Donc, vous utilisez uniquement le -> la notation lorsque la chose sur la gauche est un pointeur.

488
00:29:16,070 --> 00:29:18,790
Sinon, si c'est une structure réelle, utilisez le n..

489
00:29:18,790 --> 00:29:25,800
Et puis ceci: Pourquoi dois-je initialiser newptr-> suivant à NULL?

490
00:29:25,800 --> 00:29:28,610
Nous ne voulons pas d'une main gauche pend hors de la fin de la scène.

491
00:29:28,610 --> 00:29:31,630
Nous voulons qu'il pointant vers le bas, ce qui signifie la fin de cette liste

492
00:29:31,630 --> 00:29:34,980
pourrait être à ce nœud, donc nous assurez-vous qu'il est NULL.

493
00:29:34,980 --> 00:29:38,460
Et, en général, initialiser vos variables ou vos membres de données et structures

494
00:29:38,460 --> 00:29:40,470
à quelque chose est juste bonne pratique.

495
00:29:40,470 --> 00:29:45,170
Se contenter de laisser les déchets existent et continueront d'exister en général, vous obtient dans l'ennui

496
00:29:45,170 --> 00:29:48,650
si vous avez oublié de faire quelque chose plus tard.

497
00:29:48,650 --> 00:29:51,590
>> Voici quelques cas. Là encore, c'est la fonction d'insertion,

498
00:29:51,590 --> 00:29:54,930
et la première chose que je vérifie, c'est si la variable appelée en premier,

499
00:29:54,930 --> 00:29:58,240
cette variable globale est NULL, ce qui signifie qu'il n'ya pas de liste chaînée.

500
00:29:58,240 --> 00:30:02,460
Nous avons inséré aucun nombre, il est donc trivial pour insérer ce numéro actuel

501
00:30:02,460 --> 00:30:05,240
dans la liste, parce qu'il appartient seulement au début de la liste.

502
00:30:05,240 --> 00:30:08,100
Donc, ce fut quand Anita vient d'être debout ici seul, en faisant semblant

503
00:30:08,100 --> 00:30:11,390
personne d'autre était ici sur la scène jusqu'à ce que nous avons prévu un noeud,

504
00:30:11,390 --> 00:30:13,940
alors elle pourrait lever la main pour la première fois,

505
00:30:13,940 --> 00:30:17,420
si tout le monde était venu sur la scène après sa lundi.

506
00:30:17,420 --> 00:30:22,900
Or, ici, il s'agit d'un petit chèque où je dois dire que si le nouveau nœud de valeur de n

507
00:30:22,900 --> 00:30:27,370
<est la valeur de n dans le premier noeud de courant,

508
00:30:27,370 --> 00:30:29,930
cela signifie qu'il ya une liste liée qui a commencé.

509
00:30:29,930 --> 00:30:32,330
Il ya au moins un noeud dans la liste, mais ce nouveau type

510
00:30:32,330 --> 00:30:37,230
appartient avant, donc nous devons faire bouger les choses autour.

511
00:30:37,230 --> 00:30:43,450
En d'autres termes, si la liste a commencé avec seulement, disons,

512
00:30:43,450 --> 00:30:48,100
juste le numéro 17, c'est le - en fait, nous pouvons faire cela plus clairement.

513
00:30:48,100 --> 00:30:56,010
Si nous commençons notre histoire avec un pointeur ici appelé en premier,

514
00:30:56,010 --> 00:30:59,870
et d'abord il est NULL, et nous indiquer le numéro 9,

515
00:30:59,870 --> 00:31:02,510
le nombre 9 appartient clairement au début de la liste.

516
00:31:02,510 --> 00:31:07,400
Donc, supposons que nous venons de malloced l'adresse ou le numéro 9 et le mettre ici.

517
00:31:07,400 --> 00:31:13,170
Si le premier est de 9 par défaut, le premier scénario, nous avons discuté signifie simplement que le point let de ce gars ici,

518
00:31:13,170 --> 00:31:15,790
laisser ce que NULL; nous avons maintenant le numéro 9.

519
00:31:15,790 --> 00:31:18,280
Le prochain numéro nous voulons insérer est de 17.

520
00:31:18,280 --> 00:31:22,420
17 appartient ici, donc nous allons devoir faire quelques pas à pas à travers cette logique.

521
00:31:22,420 --> 00:31:26,060
Alors disons plutôt que, avant de faire cela, supposons que nous voulions insérer le numéro 8.

522
00:31:26,060 --> 00:31:28,650
>> Donc, juste pour une question de commodité, je vais faire ici.

523
00:31:28,650 --> 00:31:30,760
Mais rappelez-vous, malloc peut mettre presque n'importe où.

524
00:31:30,760 --> 00:31:33,460
Mais pour l'amour du dessin, je vais le mettre ici.

525
00:31:33,460 --> 00:31:38,440
Donc, prétendre que je viens alloué un noeud pour le numéro 8, ce qui est NULL par défaut.

526
00:31:38,440 --> 00:31:42,800
Que doit maintenant se passer? Un certain nombre de choses.

527
00:31:42,800 --> 00:31:47,090
Nous avons fait cette erreur sur scène le lundi où nous avons mis à jour un pointeur comme ça,

528
00:31:47,090 --> 00:31:51,890
puis a fait cela, et puis nous avons affirmé - nous orphelin tout le monde sur scène.

529
00:31:51,890 --> 00:31:54,350
Parce que tu ne peux pas - l'ordre des opérations est important ici,

530
00:31:54,350 --> 00:31:58,760
parce que maintenant nous avons perdu ce noeud 9 qui est juste une sorte de flotter dans l'espace.

531
00:31:58,760 --> 00:32:01,150
Ce n'était donc pas la bonne approche lundi.

532
00:32:01,150 --> 00:32:03,330
Nous devons d'abord faire quelque chose d'autre.

533
00:32:03,330 --> 00:32:06,280
L'état du monde ressemble à ceci. Au départ, 8 ont été alloués.

534
00:32:06,280 --> 00:32:10,550
Quelle serait une meilleure façon d'insérer 8?

535
00:32:10,550 --> 00:32:14,720
Au lieu de mettre à jour ce premier pointeur, juste mettre à jour celui-là à la place.

536
00:32:14,720 --> 00:32:17,720
Nous avons donc besoin d'une ligne de code qui va transformer ce caractère NULL

537
00:32:17,720 --> 00:32:22,020
dans un pointeur pointant réelle qui est au noeud 9,

538
00:32:22,020 --> 00:32:27,970
et alors nous pouvons en toute sécurité d'abord changer pour pointer vers ce gars ici.

539
00:32:27,970 --> 00:32:31,330
Maintenant, nous avons une liste, une liste chaînée, de deux éléments.

540
00:32:31,330 --> 00:32:33,580
Et qu'est ce que cela fait ressembler ici?

541
00:32:33,580 --> 00:32:36,900
Si l'on regarde le code, vous remarquerez que j'ai fait exactement cela.

542
00:32:36,900 --> 00:32:41,970
Je l'ai dit newptr, et dans cette histoire, newptr pointait à ce gars-là.

543
00:32:41,970 --> 00:32:45,520
>> Alors laissez-moi d'attirer encore une chose, et je l'aurais laissé place un peu plus pour cela.

544
00:32:45,520 --> 00:32:48,540
Alors pardonnez le dessin minuscule.

545
00:32:48,540 --> 00:32:52,140
Ce gars-là est appelé newptr.

546
00:32:52,140 --> 00:32:57,940
C'est la variable, nous avons déclaré quelques lignes plus haut, dans la ligne - juste au-dessus 25.

547
00:32:57,940 --> 00:33:03,430
Et elle pointe à 8. Donc, quand je dis newptr-> suivant, cela signifie aller à la struct

548
00:33:03,430 --> 00:33:07,910
qui est pointé par newptr, nous voici donc, allez-y.

549
00:33:07,910 --> 00:33:13,990
Ensuite, la flèche est dit obtenir le champ suivant, puis l'= est mis disant quelle valeur?

550
00:33:13,990 --> 00:33:17,280
La valeur qui était en première valeur qui était le premier?

551
00:33:17,280 --> 00:33:21,930
Première pointait sur ce nœud, ce qui signifie que cela devrait maintenant pointer vers ce nœud.

552
00:33:21,930 --> 00:33:25,660
En d'autres termes, ce qui semble bien un désordre ridicule avec mon écriture,

553
00:33:25,660 --> 00:33:28,620
ce qui est une idée simple de transférer ces flèches autour

554
00:33:28,620 --> 00:33:31,560
se traduit par le code avec juste cette ligne de commande.

555
00:33:31,560 --> 00:33:38,110
Stockez ce qui est en premier dans le champ suivant, puis mettre à jour ce premier fait.

556
00:33:38,110 --> 00:33:40,900
Allons de l'avant et avancer rapidement dans une partie de cette,

557
00:33:40,900 --> 00:33:44,220
et ne regarder que cette insertion queue pour l'instant.

558
00:33:44,220 --> 00:33:51,210
Supposons que je arriver au point où je trouve que le prochain champ de certains node est NULL.

559
00:33:51,210 --> 00:33:53,410
Et à ce moment de l'histoire, un détail qui Je passe sur

560
00:33:53,410 --> 00:33:58,170
c'est que j'ai introduit un autre pointeur vers le haut ici, à la ligne 142, pointeur prédécesseur.

561
00:33:58,170 --> 00:34:01,320
Pour l'essentiel, à ce stade de l'histoire, une fois que la liste est longue,

562
00:34:01,320 --> 00:34:04,800
J'ai en quelque sorte besoin de marcher avec deux doigts, parce que si je vais trop loin,

563
00:34:04,800 --> 00:34:08,219
retenir dans une liste unique de longueur, vous ne pouvez pas revenir en arrière.

564
00:34:08,219 --> 00:34:13,659
Donc cette idée de predptr est mon doigt vers la gauche, et newptr - pas newptr.

565
00:34:13,659 --> 00:34:17,199
Un autre pointeur qui est ici est mon autre doigt, et je suis juste un peu de marche dans la liste.

566
00:34:17,199 --> 00:34:22,179
C'est pourquoi ce qui existe. Mais nous allons seulement considérer l'un des cas plus simples ici.

567
00:34:22,179 --> 00:34:26,620
Si le champ suivant ce pointeur est NULL, ce qui est la conséquence logique?

568
00:34:26,620 --> 00:34:30,840
Si vous êtes parcourant cette liste et que vous frappez un pointeur NULL?

569
00:34:30,840 --> 00:34:35,780
Vous êtes à la fin de la liste, et ainsi le code pour ensuite ajouter à cet élément supplémentaire

570
00:34:35,780 --> 00:34:41,230
est en quelque sorte la intuitif prendra ce nœud dont la prochaine pointeur est NULL,

571
00:34:41,230 --> 00:34:46,120
c'est donc le moment NULL, et le changer, même si, comme l'adresse du nouveau noeud.

572
00:34:46,120 --> 00:34:52,260
Donc, nous ne faisons que tirer dans le code la flèche que l'on a sur scène en levant la main gauche de quelqu'un.

573
00:34:52,260 --> 00:34:54,070
>> Et le cas que je vais saluer mes mains pour le moment,

574
00:34:54,070 --> 00:34:58,020
juste parce que je pense qu'il est facile de se perdre quand nous le faisons dans ce genre d'environnement,

575
00:34:58,020 --> 00:35:00,600
est la vérification de l'insertion au milieu de la liste.

576
00:35:00,600 --> 00:35:03,220
Mais juste intuitivement, ce qui doit se passer si vous voulez comprendre

577
00:35:03,220 --> 00:35:06,600
où un certain nombre appartient au milieu, c'est que vous avez à marcher

578
00:35:06,600 --> 00:35:09,510
avec plus d'un doigt, plus d'un pointeur,

579
00:35:09,510 --> 00:35:12,920
savoir où il appartient de vérifier est l'élément <l'actuel,

580
00:35:12,920 --> 00:35:15,450
> L'actuel, et une fois que vous trouver cet endroit,

581
00:35:15,450 --> 00:35:20,400
alors vous devez faire ce genre de jeu de bonneteau où vous vous déplacez les pointeurs vers de très près.

582
00:35:20,400 --> 00:35:23,850
Et cette réponse, si vous le souhaitez à la raison grâce à cela à la maison sur votre propre,

583
00:35:23,850 --> 00:35:28,340
se résume simplement à ces deux lignes de code, mais l'ordre de ces lignes est super important.

584
00:35:28,340 --> 00:35:31,390
Parce que si vous laissez tomber la main de quelqu'un et d'élever quelqu'un d'autre dans le mauvais ordre,

585
00:35:31,390 --> 00:35:34,580
encore une fois, vous pourriez vous retrouver orphelins de la liste.

586
00:35:34,580 --> 00:35:39,500
Pour résumer conceptuellement plus, l'insertion de la queue est relativement simple.

587
00:35:39,500 --> 00:35:42,940
L'insertion à la tête est aussi relativement simple,

588
00:35:42,940 --> 00:35:45,580
mais vous avez besoin de mettre à jour un pointeur supplémentaire cette fois

589
00:35:45,580 --> 00:35:47,930
à serrer le numéro 5 dans la liste ici,

590
00:35:47,930 --> 00:35:51,560
puis insertion dans le milieu implique un effort encore plus,

591
00:35:51,560 --> 00:35:56,130
faire très attention à insérer le numéro 20 dans son emplacement correct,

592
00:35:56,130 --> 00:35:58,350
qui est comprise entre 17 et 22.

593
00:35:58,350 --> 00:36:02,700
Donc, vous avez besoin de faire quelque chose comme le nouveau nœud de 20 points à 22,

594
00:36:02,700 --> 00:36:08,470
puis, le pointeur du noeud qui doit être mis à jour dernier?

595
00:36:08,470 --> 00:36:10,630
Il a 17 ans, fait à l'insérer.

596
00:36:10,630 --> 00:36:14,080
Encore une fois, je vais reporter le code réel pour que la mise en œuvre particulière.

597
00:36:14,080 --> 00:36:17,280
>> À première vue, c'est un peu écrasante, mais c'est vraiment juste une boucle infinie

598
00:36:17,280 --> 00:36:21,770
qui est en boucle, en boucle, en boucle, en boucle, et de briser dès que vous appuyez sur le pointeur NULL,

599
00:36:21,770 --> 00:36:24,590
à quel point vous pouvez faire de l'insertion requise.

600
00:36:24,590 --> 00:36:30,960
Ce, alors, est représentatif code lié insertion liste.

601
00:36:30,960 --> 00:36:34,590
Cela faisait un peu beaucoup, et il se sent comme nous avons résolu un problème,

602
00:36:34,590 --> 00:36:36,940
mais nous avons mis en place une toute autre histoire. Franchement, nous avons passé tout ce temps

603
00:36:36,940 --> 00:36:40,540
le grand O et Ω et la gestion du temps, en essayant de résoudre les problèmes plus rapidement,

604
00:36:40,540 --> 00:36:43,270
et ici, nous faisons un grand pas en arrière, il se sent.

605
00:36:43,270 --> 00:36:45,380
Et pourtant, si l'objectif est de stocker des données,

606
00:36:45,380 --> 00:36:48,010
il se sent comme le Saint Graal, comme nous l'avons dit, le lundi serait vraiment

607
00:36:48,010 --> 00:36:50,470
pour stocker des choses instantanément.

608
00:36:50,470 --> 00:36:53,930
>> En effet, supposons que nous avons mis de côté la liste liée pour un moment

609
00:36:53,930 --> 00:36:56,000
et nous avons plutôt introduit la notion d'une table.

610
00:36:56,000 --> 00:36:59,110
Et nous allons juste penser à une table pour un moment comme un tableau.

611
00:36:59,110 --> 00:37:03,790
Ce tableau et ce cas a ici quelque 26 éléments, de 0 à 25,

612
00:37:03,790 --> 00:37:07,940
et supposons que vous aviez besoin de quelque morceau de stockage pour les noms:

613
00:37:07,940 --> 00:37:10,350
Alice et Bob et Charlie, etc.

614
00:37:10,350 --> 00:37:12,880
Et vous avez besoin d'une structure de données pour stocker ces noms.

615
00:37:12,880 --> 00:37:15,000
Eh bien, vous pouvez utiliser quelque chose comme une liste chaînée

616
00:37:15,000 --> 00:37:20,260
et on pouvait marcher sur la liste d'insérer Alice avant que Bob et Charlie après que Bob et ainsi de suite.

617
00:37:20,260 --> 00:37:23,850
Et, en fait, si vous voulez voir le code comme ça en passant,

618
00:37:23,850 --> 00:37:27,230
savons que dans list2.h, nous faisons exactement cela.

619
00:37:27,230 --> 00:37:30,610
Nous n'irons pas à travers ce code, mais il s'agit d'une variante du premier exemple

620
00:37:30,610 --> 00:37:34,640
qui introduit un autre struct nous avons vu auparavant appelé étudiant,

621
00:37:34,640 --> 00:37:40,330
et puis ce qu'il stocke en fait dans la liste chaînée est un pointeur vers une structure étudiant

622
00:37:40,330 --> 00:37:44,520
plutôt que d'un simple entier peu, n.

623
00:37:44,520 --> 00:37:46,900
Alors rends compte qu'il ya code, il implique que les chaînes réelles,

624
00:37:46,900 --> 00:37:49,940
mais si l'objectif à portée de main vraiment maintenant est de s'attaquer au problème de l'efficacité,

625
00:37:49,940 --> 00:37:53,380
ça ne serait pas bien si on nous donne un objet appelé Alice,

626
00:37:53,380 --> 00:37:56,020
nous voulons la mettre dans le bon emplacement dans une structure de données,

627
00:37:56,020 --> 00:37:58,860
il se sent comme ça serait vraiment sympa de mettre juste Alice,

628
00:37:58,860 --> 00:38:01,180
dont le nom commence par A, dans le premier emplacement.

629
00:38:01,180 --> 00:38:05,270
Et Bob, dont le nom commence par B, dans le deuxième emplacement.

630
00:38:05,270 --> 00:38:09,580
Avec un tableau, ou nous allons commencer à l'appeler une table, une table de hachage à l',

631
00:38:09,580 --> 00:38:13,650
nous pouvons faire exactement cela. Si on nous donne un nom comme Alice,

632
00:38:13,650 --> 00:38:16,700
une chaîne comme Alice, où mettez-vous A-l-i-c-e?

633
00:38:16,700 --> 00:38:20,540
Nous avons besoin d'un hueristic. Nous avons besoin d'une fonction pour prendre un peu comme Alice entrée

634
00:38:20,540 --> 00:38:24,610
et retourner une réponse: «Mettez Alice à cet endroit."

635
00:38:24,610 --> 00:38:28,720
Et cette fonction, cette boîte noire, va être appelée une fonction de hachage.

636
00:38:28,720 --> 00:38:32,330
>> Une fonction de hachage est quelque chose qui prend une entrée, comme «Alice»,

637
00:38:32,330 --> 00:38:38,080
et revient à vous, en général, l'emplacement numérique dans une structure de données où Alice appartient.

638
00:38:38,080 --> 00:38:40,830
Dans ce cas, notre fonction de hachage devrait être relativement simple.

639
00:38:40,830 --> 00:38:47,510
Notre fonction de hachage doit dire que, si on vous donne "Alice", le personnage que je dois m'en soucier?

640
00:38:47,510 --> 00:38:55,660
La première. Donc, je regarde [0], puis-je dire si [0] caractère est A, retourner le nombre 0.

641
00:38:55,660 --> 00:39:01,130
Si c'est B, renvoyer 1. Si c'est C, retourner 2, et ainsi de suite.

642
00:39:01,130 --> 00:39:05,940
Tous les index 0, et qui me permettrait d'insérer Alice et Bob, puis puis Charlie et ainsi de suite

643
00:39:05,940 --> 00:39:10,960
dans cette structure de données. Mais il ya un problème.

644
00:39:10,960 --> 00:39:13,060
Que faire si Anita arrive à nouveau?

645
00:39:13,060 --> 00:39:17,510
Où allons-nous mettre Anita? Son nom, lui aussi, commence par la lettre A,

646
00:39:17,510 --> 00:39:20,330
et il se sent comme nous avons fait un gâchis encore plus grand de ce problème.

647
00:39:20,330 --> 00:39:24,380
Nous avons maintenant insertion immédiate, insertion constante de temps, dans une structure de données

648
00:39:24,380 --> 00:39:27,100
plutôt que pire des cas linéaire,

649
00:39:27,100 --> 00:39:29,510
mais que pouvons-nous faire avec Anita dans ce cas?

650
00:39:29,510 --> 00:39:34,110
Quels sont les deux options, vraiment? Ouais?

651
00:39:34,110 --> 00:39:37,410
[Réponse de l'étudiant, inintelligible] Bon, alors nous pourrions avoir une autre dimension.

652
00:39:37,410 --> 00:39:42,320
C'est bien. Ainsi, nous pouvons construire des choses en 3D comme nous en avons parlé verbalement le lundi.

653
00:39:42,320 --> 00:39:46,700
On pourrait ajouter un autre accès ici, mais je suppose que non, je suis en train de garder ce simple.

654
00:39:46,700 --> 00:39:50,160
Le but ici est tout à avoir rapidement accès en temps constant,

655
00:39:50,160 --> 00:39:52,170
donc c'est ajouter trop de complexité.

656
00:39:52,170 --> 00:39:55,970
Quelles sont les autres options lorsque vous essayez d'insérer Anita dans cette structure de données? Ouais?

657
00:39:55,970 --> 00:39:58,610
[Réponse de l'étudiant, inintelligible] Bon. Donc, nous pourrions passer tout le monde vers le bas,

658
00:39:58,610 --> 00:40:03,040
comme Charlie coups de coude vers le bas Bob et Alice, et puis nous avons mis Anita où elle veut vraiment être.

659
00:40:03,040 --> 00:40:05,660
>> Bien sûr, maintenant, il ya un effet secondaire de cette.

660
00:40:05,660 --> 00:40:09,000
Cette structure de données est probablement utile non pas parce que nous voulons insérer les gens une fois

661
00:40:09,000 --> 00:40:11,250
mais parce que nous voulons vérifier si elles sont là plus tard

662
00:40:11,250 --> 00:40:13,600
si nous voulons imprimer tous les noms dans la structure de données.

663
00:40:13,600 --> 00:40:15,850
Nous allons faire quelque chose avec ces données par la suite.

664
00:40:15,850 --> 00:40:20,810
Alors maintenant, nous avons sorte de vissé sur Alice, qui n'est plus où elle est censée être.

665
00:40:20,810 --> 00:40:23,880
Bob n'est pas non plus, ni Charlie.

666
00:40:23,880 --> 00:40:26,060
Alors peut-être que ce n'est pas une si bonne idée.

667
00:40:26,060 --> 00:40:28,830
Mais en fait, c'est une option. Nous pourrions passer tout le monde vers le bas,

668
00:40:28,830 --> 00:40:32,240
ou diable, Anita est venu tard dans le jeu, pourquoi ne pas simplement mettre Anita

669
00:40:32,240 --> 00:40:35,870
pas ici, pas ici, pas ici, nous allons juste lui mettre un peu plus bas dans la liste.

670
00:40:35,870 --> 00:40:38,680
Mais ce problème commence à transférer à nouveau.

671
00:40:38,680 --> 00:40:41,630
Vous pourriez être en mesure de trouver instantanément Alice, sur la base de son prénom.

672
00:40:41,630 --> 00:40:44,320
Et Bob instantanément, et Charlie. Mais alors vous cherchez Anita,

673
00:40:44,320 --> 00:40:46,360
et vous voyez, hein, Alice est sur le chemin.

674
00:40:46,360 --> 00:40:48,770
Eh bien, laissez-moi vérifier ci-dessous Alice. Bob n'est pas Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie n'est pas Anita. Oh, il ya Anita.

676
00:40:51,850 --> 00:40:54,720
Et si vous continuez ce train de la logique jusqu'au bout,

677
00:40:54,720 --> 00:41:00,690
quel est le temps le pire des cas en cours d'exécution de la recherche ou de l'insertion Anita dans cette nouvelle structure de données?

678
00:41:00,690 --> 00:41:03,280
Il est O (n), pas vrai?

679
00:41:03,280 --> 00:41:06,280
Parce que dans le pire des cas, il ya Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
tout le chemin vers le bas pour quelqu'un qui s'appelle «Y», il n'y a donc qu'une seule place à gauche.

681
00:41:10,150 --> 00:41:13,950
Heureusement, nous n'avons pas de celui qui est appelé "Z", nous avons donc mis Anita tout en bas.

682
00:41:13,950 --> 00:41:16,040
>> Nous n'avons pas vraiment résolu ce problème.

683
00:41:16,040 --> 00:41:19,890
Alors peut-être nous avons besoin d'introduire cette troisième dimension.

684
00:41:19,890 --> 00:41:22,230
Et il s'avère que, si nous ne nous introduire cette troisième dimension,

685
00:41:22,230 --> 00:41:25,240
nous ne pouvons pas faire cela parfaitement, mais le Saint-Graal va devenir de

686
00:41:25,240 --> 00:41:28,370
constante de temps d'insertion et les insertions dynamiques, afin que

687
00:41:28,370 --> 00:41:30,960
nous n'avons pas coder en dur un tableau de taille 26.

688
00:41:30,960 --> 00:41:34,400
Nous pouvons insérer autant de noms que nous voulons, mais nous allons prendre notre pause de 5 minutes ici

689
00:41:34,400 --> 00:41:38,790
puis le faire correctement.

690
00:41:38,790 --> 00:41:46,020
Très bien. J'ai mis en place l'histoire assez artificiellement il

691
00:41:46,020 --> 00:41:48,670
en choisissant Alice et Bob, puis puis Charlie et Anita,

692
00:41:48,670 --> 00:41:51,000
dont le nom était évidemment entrer en collision avec Alice.

693
00:41:51,000 --> 00:41:54,120
Mais la question que nous a pris fin lundi avec c'est à quel point est-il probable

694
00:41:54,120 --> 00:41:56,370
que vous obtenez ce genre de collisions? En d'autres termes,

695
00:41:56,370 --> 00:42:00,490
si on commence à utiliser cette structure sous forme de tableau, ce qui est vraiment juste un tableau,

696
00:42:00,490 --> 00:42:02,460
dans ce cas, de 26 emplacements,

697
00:42:02,460 --> 00:42:05,740
si nos entrées sont plutôt uniformément répartie?

698
00:42:05,740 --> 00:42:09,620
Ce n'est pas artificiellement Alice et Bob et Charlie David et ainsi de suite par ordre alphabétique,

699
00:42:09,620 --> 00:42:12,380
elle est répartie uniformément sur A à Z.

700
00:42:12,380 --> 00:42:15,220
>> Peut-être que nous allons avoir de la chance et nous n'allons pas avoir deux A ou deux B

701
00:42:15,220 --> 00:42:17,640
avec une probabilité très élevée, mais comme quelqu'un l'a souligné,

702
00:42:17,640 --> 00:42:20,730
si nous généralisé ce problème et ne pas faire de 0 à 25

703
00:42:20,730 --> 00:42:26,060
mais, disons, de 0 à 364 ou de 65 ans, souvent le nombre de jours dans une année normale,

704
00:42:26,060 --> 00:42:31,170
et a posé la question: «Quelle est la probabilité que deux d'entre nous dans cette salle ont le même anniversaire?"

705
00:42:31,170 --> 00:42:34,600
En d'autres termes, quelle est la probabilité que deux d'entre nous ont un nom commençant par A?

706
00:42:34,600 --> 00:42:37,190
Le genre de question est la même, mais cet espace d'adressage,

707
00:42:37,190 --> 00:42:39,940
cet espace de recherche, est plus grand dans le cas des anniversaires,

708
00:42:39,940 --> 00:42:42,820
parce que nous avons tant de jours de plus que l'année lettres dans l'alphabet.

709
00:42:42,820 --> 00:42:44,910
Quelle est la probabilité d'une collision?

710
00:42:44,910 --> 00:42:48,410
Eh bien, nous pouvons penser de ce par déterminer le calcul en sens inverse.

711
00:42:48,410 --> 00:42:50,580
Quelle est la probabilité de collisions pas?

712
00:42:50,580 --> 00:42:53,970
Eh bien, cette expression ici dit que ce qui est la probabilité

713
00:42:53,970 --> 00:42:58,770
s'il n'y a qu'une seule personne dans cette salle, qu'ils ont un anniversaire unique?

714
00:42:58,770 --> 00:43:01,190
C'est 100%. Parce que s'il ya une seule personne dans la salle,

715
00:43:01,190 --> 00:43:03,940
son anniversaire peut être l'un des 365 jours de l'année.

716
00:43:03,940 --> 00:43:08,650
Ainsi, les options 365/365 me donne une valeur de 1.

717
00:43:08,650 --> 00:43:11,250
Donc, la probabilité en question en ce moment est à seulement 1.

718
00:43:11,250 --> 00:43:13,270
Mais s'il ya une deuxième personne dans la chambre,

719
00:43:13,270 --> 00:43:16,490
quelle est la probabilité que leur anniversaire est différent?

720
00:43:16,490 --> 00:43:20,680
Il ya seulement 364 jours possibles, en ignorant les années bissextiles,

721
00:43:20,680 --> 00:43:23,580
pour leur anniversaire de ne pas entrer en collision avec d'autres personnes.

722
00:43:23,580 --> 00:43:31,920
Donc 364/365. Si une tierce personne arrive, c'est 363/365, et ainsi de suite.

723
00:43:31,920 --> 00:43:35,790
Alors nous gardons multipliant ces fractions, qui sont de plus en plus petits,

724
00:43:35,790 --> 00:43:40,720
de comprendre quelle est la probabilité que nous avons tous des anniversaires uniques?

725
00:43:40,720 --> 00:43:43,570
Mais nous pouvons, bien sûr, il suffit de prendre cette réponse et de le retourner dans

726
00:43:43,570 --> 00:43:47,210
et faire 1 moins tout cela, une expression que nous finirons par obtenir

727
00:43:47,210 --> 00:43:51,250
si vous vous rappelez le dos de vos livres de maths, ça ressemble un petit quelque chose comme ça,

728
00:43:51,250 --> 00:43:54,590
qui est beaucoup plus facile à interpréter graphiquement.

729
00:43:54,590 --> 00:43:57,820
Et ce graphique ici est sur l'axe x le nombre d'anniversaires,

730
00:43:57,820 --> 00:44:02,030
ou le nombre de personnes qui ont leur anniversaire, et sur l'axe y est la probabilité d'un match.

731
00:44:02,030 --> 00:44:06,060
Et ce que cela veut dire, c'est que si vous avez, disons, même,

732
00:44:06,060 --> 00:44:10,860
nous allons choisir quelque chose comme 22, 23.

733
00:44:10,860 --> 00:44:13,160
S'il ya 22 ou 23 personnes dans la salle,

734
00:44:13,160 --> 00:44:17,100
la probabilité que deux de ces très peu de gens vont avoir la même date d'anniversaire

735
00:44:17,100 --> 00:44:19,560
est en fait super haute, combinatoire.

736
00:44:19,560 --> 00:44:23,450
50% de chances que dans une classe de seulement 22 personnes, un séminaire, pratiquement,

737
00:44:23,450 --> 00:44:25,790
2 de ces personnes vont avoir le même anniversaire.

738
00:44:25,790 --> 00:44:28,520
Parce qu'il ya tellement de façons dont vous pouvez avoir le même anniversaire.

739
00:44:28,520 --> 00:44:31,110
Pire encore, si vous regardez le côté droit de la carte,

740
00:44:31,110 --> 00:44:34,040
au moment où vous avez une classe avec 58 élèves en elle,

741
00:44:34,040 --> 00:44:39,270
la probabilité de 2 personnes fêtant leur anniversaire est super, super rapide, près de 100%.

742
00:44:39,270 --> 00:44:41,880
Maintenant, c'est une sorte de faits amusants sur la vie réelle.

743
00:44:41,880 --> 00:44:45,850
>> Mais les conséquences, maintenant, pour les structures de données et le stockage d'informations

744
00:44:45,850 --> 00:44:51,100
signifie que juste en supposant que vous avez une belle, propre, la distribution uniforme des données

745
00:44:51,100 --> 00:44:53,650
et vous avez un tableau assez grand pour contenir un tas de choses

746
00:44:53,650 --> 00:44:59,360
ne signifie pas que vous allez amener les gens dans des endroits uniques.

747
00:44:59,360 --> 00:45:03,810
Vous allez avoir des collisions. Donc, cette notion de hachage, comme on l'appelle,

748
00:45:03,810 --> 00:45:07,450
prenant une entrée comme "Alice" et le masser en quelque sorte

749
00:45:07,450 --> 00:45:10,190
puis reprendre une réponse comme 0 ou 1 ou 2.

750
00:45:10,190 --> 00:45:17,500
Pour en revenir une sortie de cette fonction est en proie à cette probabilité de collision.

751
00:45:17,500 --> 00:45:19,530
Alors, comment pouvons-nous gérer ces collisions?

752
00:45:19,530 --> 00:45:21,940
Eh bien, sur le premier cas, nous pouvons prendre l'idée qui a été proposée.

753
00:45:21,940 --> 00:45:25,100
Nous pouvons simplement passer tout le monde vers le bas, ou peut-être, un peu plus simplement,

754
00:45:25,100 --> 00:45:29,870
plutôt que tout le monde déménagement d'autre, nous allons simplement passer Anita au fond de la place disponible.

755
00:45:29,870 --> 00:45:32,810
Donc, si Alice est 0, Bob est en 1, Charlie est dans 2,

756
00:45:32,810 --> 00:45:35,260
nous allons simplement mettre Anita à l'emplacement 3.

757
00:45:35,260 --> 00:45:38,860
Et c'est une technique de structures de données appelées linéaire sondage.

758
00:45:38,860 --> 00:45:41,310
Linéaire parce que vous êtes juste marcher cette ligne, et que vous êtes en quelque sorte de sondage

759
00:45:41,310 --> 00:45:43,640
pour les spots de la structure de données.

760
00:45:43,640 --> 00:45:46,210
Bien sûr, cela dégénérait en O (n).

761
00:45:46,210 --> 00:45:49,590
Si la structure de données est vraiment complet, il ya 25 personnes qui y déjà,

762
00:45:49,590 --> 00:45:54,120
puis Anita arrive, elle se retrouve à ce qui serait emplacement Z, et c'est très bien.

763
00:45:54,120 --> 00:45:56,540
Elle s'inscrit toujours, et nous pouvons la retrouver plus tard.

764
00:45:56,540 --> 00:46:00,100
>> Mais cela était contraire à l'objectif d'accélérer les choses.

765
00:46:00,100 --> 00:46:02,530
Alors que faire si nous introduit à la place de cette troisième dimension?

766
00:46:02,530 --> 00:46:06,400
Cette technique est généralement appelé chaînage séparé, ou ayant des chaînes.

767
00:46:06,400 --> 00:46:10,030
Et quelle table de hachage est présent, cette structure tabulaire,

768
00:46:10,030 --> 00:46:13,450
votre table est juste un tableau de pointeurs.

769
00:46:13,450 --> 00:46:18,230
Mais ce que ces pointeurs indiquent peut deviner quoi?

770
00:46:18,230 --> 00:46:21,970
Une liste chaînée. Alors que faire si nous prenons le meilleur de ces deux mondes?

771
00:46:21,970 --> 00:46:26,500
Nous utilisons des tableaux pour les indices initiaux

772
00:46:26,500 --> 00:46:32,070
dans la structure de données afin que nous puissions vous déplacer instantanément au [0] [1], [30] ou ainsi de suite,

773
00:46:32,070 --> 00:46:36,480
mais pour que nous ayons une certaine souplesse et nous pouvons monter Anita et Alice et Adam

774
00:46:36,480 --> 00:46:38,630
et toute autre Un nom,

775
00:46:38,630 --> 00:46:43,470
nous avons au contraire laisser l'autre axe croître arbitrairement.

776
00:46:43,470 --> 00:46:47,340
Et nous avons finalement, à partir de lundi, ont cette capacité expressive avec liste chaînée.

777
00:46:47,340 --> 00:46:49,530
Nous pouvons cultiver une structure de données arbitrairement.

778
00:46:49,530 --> 00:46:52,450
Sinon, nous pourrions juste faire un énorme 2-dimensionnel,

779
00:46:52,450 --> 00:46:57,190
mais cela va être une situation terrible si l'une des lignes dans un tableau à 2 dimensions

780
00:46:57,190 --> 00:47:01,280
n'est pas assez grand pour la personne supplémentaire dont le nom se passe de commencer avec A.

781
00:47:01,280 --> 00:47:04,200
A Dieu ne plaise que nous devons réaffecter une énorme structure de 2-dimensionnelle

782
00:47:04,200 --> 00:47:06,600
simplement parce qu'il ya tant de gens nommés A,

783
00:47:06,600 --> 00:47:09,480
surtout quand il ya si peu de gens nommés Z quelque chose.

784
00:47:09,480 --> 00:47:12,170
Il va juste être une structure très clairsemée données.

785
00:47:12,170 --> 00:47:15,400
Donc, ce n'est pas parfait par tous les moyens, mais maintenant nous avons au moins la possibilité

786
00:47:15,400 --> 00:47:19,090
pour trouver instantanément où Alice ou Anita appartient,

787
00:47:19,090 --> 00:47:21,090
au moins sur le plan de l'axe vertical,

788
00:47:21,090 --> 00:47:25,850
puis nous avons juste à décider où placer Anita ou Alice dans cette liste chaînée.

789
00:47:25,850 --> 00:47:32,480
Si l'on ne se soucient pas le tri des choses, comment pourrait-on insérer rapidement Alice dans une structure comme ça?

790
00:47:32,480 --> 00:47:35,370
Il est temps constant. Nous index dans [0], et s'il n'y a pas de son,

791
00:47:35,370 --> 00:47:37,550
Alice va au début de la liste liée.

792
00:47:37,550 --> 00:47:40,000
Mais ce n'est pas une affaire énorme. Parce que si Anita vient ensuite le long de

793
00:47:40,000 --> 00:47:42,160
un certain nombre d'étapes plus tard, d'où vient Anita appartiennent?

794
00:47:42,160 --> 00:47:45,140
Eh bien, [0]. POO. Alice est déjà dans cette liste chaînée.

795
00:47:45,140 --> 00:47:47,760
>> Mais si on ne se soucie pas de trier ces noms,

796
00:47:47,760 --> 00:47:53,580
on peut juste se déplacer sur Alice, insert Anita, mais même cela est la constante de temps.

797
00:47:53,580 --> 00:47:57,010
Même s'il n'y a Alice et Adam et tous ces autres noms A,

798
00:47:57,010 --> 00:47:59,410
ce n'est pas vraiment de les déplacer physiquement. Pourquoi?

799
00:47:59,410 --> 00:48:04,090
Parce que nous venons de faire ici avec la liste chaînée, qui sait ont été ces nœuds sont de toute façon?

800
00:48:04,090 --> 00:48:06,550
Tout ce que vous avez à faire est de déplacer les miettes de pain.

801
00:48:06,550 --> 00:48:10,930
Déplacez les flèches autour, vous n'avez pas besoin de se déplacer physiquement toutes les données autour.

802
00:48:10,930 --> 00:48:14,610
Ainsi, nous pouvons insérer Anita, dans ce cas, instantanément. Constante de temps.

803
00:48:14,610 --> 00:48:20,250
Nous avons donc constante de temps de recherche, et en temps constant insertion de quelqu'un comme Anita.

804
00:48:20,250 --> 00:48:22,740
Mais un peu simpliste du monde.

805
00:48:22,740 --> 00:48:28,510
Que faire si nous voulons trouver plus tard Alice?

806
00:48:28,510 --> 00:48:31,050
Que faire si nous voulons trouver plus tard Alice?

807
00:48:31,050 --> 00:48:35,690
Combien de pas est ce que cela va prendre?

808
00:48:35,690 --> 00:48:37,850
[Réponse de l'étudiant, inintelligible]

809
00:48:37,850 --> 00:48:40,950
Exactement. Le nombre de personnes avant d'Alice dans la liste chaînée.

810
00:48:40,950 --> 00:48:45,420
Ce n'est donc pas tout à fait parfaite, parce que notre structure de données, encore une fois, a cet accès vertical

811
00:48:45,420 --> 00:48:50,240
puis il a ces listes chaînées suspendus - en fait, il ne faut pas dessiner un tableau un.

812
00:48:50,240 --> 00:48:56,020
Il a ces listes chaînées accroché à ce qui ressemble à un petit quelque chose comme ça.

813
00:48:56,020 --> 00:48:59,110
Mais le problème est que si Alice et Adam et tous ces autres noms A

814
00:48:59,110 --> 00:49:01,720
finissent de plus en plus là-bas,

815
00:49:01,720 --> 00:49:04,810
trouver quelqu'un pourrait finir par prendre un tas d'étapes,

816
00:49:04,810 --> 00:49:06,670
bcause vous devez parcourir la liste chaînée,

817
00:49:06,670 --> 00:49:08,090
qui est une opération linéaire.

818
00:49:08,090 --> 00:49:14,270
Alors, vraiment, alors, le temps d'insertion est finalement O (n), où n est le nombre d'éléments dans la liste.

819
00:49:14,270 --> 00:49:21,780
Divisé par, disons arbitrairement appeler m, où m est le nombre de listes chaînées

820
00:49:21,780 --> 00:49:24,500
que nous avons dans cet axe vertical.

821
00:49:24,500 --> 00:49:27,180
En d'autres termes, si nous voulons vraiment supposent une distribution uniforme des noms,

822
00:49:27,180 --> 00:49:30,150
totalement irréaliste. Il ya évidemment plus de quelques lettres que d'autres.

823
00:49:30,150 --> 00:49:32,580
>> Mais si nous supposons pour le moment une distribution uniforme,

824
00:49:32,580 --> 00:49:37,350
et nous avons n personnes au total, et m chaînes au total

825
00:49:37,350 --> 00:49:40,630
à notre disposition, alors la longueur de chacune de ces chaînes

826
00:49:40,630 --> 00:49:44,380
assez va simplement être le total de n divisé par le nombre de chaînes.

827
00:49:44,380 --> 00:49:48,900
Donc n / m. Mais c'est là que nous pouvons être tout mathématiquement intelligent.

828
00:49:48,900 --> 00:49:53,030
m est une constante, parce qu'il ya un nombre fixe de celles-ci.

829
00:49:53,030 --> 00:49:54,620
Vous allez déclarez votre tableau au début,

830
00:49:54,620 --> 00:49:58,450
et nous ne sommes pas le redimensionnement de l'axe vertical. Par définition, qui reste fixe.

831
00:49:58,450 --> 00:50:01,220
C'est seulement l'axe horizontal, pour ainsi dire, les choses changent.

832
00:50:01,220 --> 00:50:04,760
Donc, techniquement, c'est une constante. Alors maintenant, le temps d'insertion

833
00:50:04,760 --> 00:50:09,700
est à peu près O (n).

834
00:50:09,700 --> 00:50:12,410
Pour que ne se sent pas tout ce que beaucoup mieux.

835
00:50:12,410 --> 00:50:14,940
Mais quelle est la vérité? Eh bien, tout ce temps, pendant des semaines,

836
00:50:14,940 --> 00:50:20,640
nous avons dit O (n ²). O (n), n 2 x ², - n, divisé par 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
C'est juste ² n. Mais maintenant, dans cette partie de la session,

838
00:50:23,580 --> 00:50:25,560
nous pouvons commencer à parler du monde réel.

839
00:50:25,560 --> 00:50:31,520
Et n / m est absolument plus vite que tout seul n.

840
00:50:31,520 --> 00:50:35,170
Si vous avez un millier de noms, et vous les briser en plusieurs seaux

841
00:50:35,170 --> 00:50:37,820
de sorte que vous n'avez que dix noms dans chacune de ces chaînes,

842
00:50:37,820 --> 00:50:41,670
absolument chercher dix choses va être plus rapide que mille choses.

843
00:50:41,670 --> 00:50:43,740
Et si l'un des ensembles de problèmes à venir va vous mettre au défi

844
00:50:43,740 --> 00:50:46,100
à penser exactement que même si, ouais,

845
00:50:46,100 --> 00:50:49,520
asymptotiquement et mathématiquement, cela reste seulement linéaire,

846
00:50:49,520 --> 00:50:51,700
qui aspire en général en essayant de trouver des choses.

847
00:50:51,700 --> 00:50:54,530
En réalité, il va être plus rapide que celui

848
00:50:54,530 --> 00:50:56,520
en raison de ce diviseur.

849
00:50:56,520 --> 00:50:58,310
Et donc il ya encore va être ce compromis

850
00:50:58,310 --> 00:51:01,390
et ce conflit entre la théorie et la réalité,

851
00:51:01,390 --> 00:51:03,550
et l'un des boutons commence à tourner à ce point au cours du semestre

852
00:51:03,550 --> 00:51:07,510
est plus de la seule réalité que nous sorte de préparer pour la fin de semster,

853
00:51:07,510 --> 00:51:09,280
que l'on introduit dans le monde de la programmation web,

854
00:51:09,280 --> 00:51:11,530
où vraiment, la performance va compter parce que vos utilisateurs vont

855
00:51:11,530 --> 00:51:14,880
commencent à sentir et d'apprécier les décisions de conception pauvres.

856
00:51:14,880 --> 00:51:19,950
>> Alors, comment allez-vous mettre en œuvre une alternance - une table de hachage avec 31 éléments?

857
00:51:19,950 --> 00:51:22,600
Et l'exemple précédent a été arbitrairement sur les anniversaires.

858
00:51:22,600 --> 00:51:26,190
Si quelqu'un a un anniversaire de Janvier Février 1 ou 1, nous les mettrons dans ce seau.

859
00:51:26,190 --> 00:51:28,960
Si c'est 2 Janvier 2 Février Mars 2, nous les mettrons dans ce seau.

860
00:51:28,960 --> 00:51:32,220
C'est pourquoi il avait 31 ans. Comment pouvez-vous déclarer une table de hachage?

861
00:51:32,220 --> 00:51:37,480
Il peut être assez simple, table * noeud est mon nom arbitraire pour lui, [31].

862
00:51:37,480 --> 00:51:42,400
Cela me donne 31 pointeurs vers des noeuds,

863
00:51:42,400 --> 00:51:45,370
et cela me permet d'avoir 31 des pointeurs vers des listes chaînées

864
00:51:45,370 --> 00:51:48,800
même si ces chaînes sont initialement NULL.

865
00:51:48,800 --> 00:51:54,860
Qu'est-ce que je veux mettre si je veux conserver "Alice", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Eh bien, nous avons besoin d'envelopper ces choses dans une structure

867
00:51:57,010 --> 00:52:00,530
parce que nous devons faire remarquer Alice à Bob, pour pointer vers Charlie, et ainsi de suite.

868
00:52:00,530 --> 00:52:04,940
Nous ne pouvons pas avoir les noms seuls, pour que je puisse créer une nouvelle structure appelée nœud ici.

869
00:52:04,940 --> 00:52:08,310
>> Qu'est-ce qu'un nœud actuel? Qu'est-ce qu'un nœud dans cette nouvelle liste liée?

870
00:52:08,310 --> 00:52:11,840
La première chose, appelé mot, est le nom de la personne.

871
00:52:11,840 --> 00:52:14,340
LONGUEUR, sans doute, se rapporte à la longueur maximale du nom d'un être humain,

872
00:52:14,340 --> 00:52:18,210
quelle qu'elle soit, 20, 30, 40 caractères dans le cas d'angle fous,

873
00:52:18,210 --> 00:52:22,680
et +1 est pour quoi? C'est juste le caractère NULL supplémentaire, \ 0.

874
00:52:22,680 --> 00:52:27,410
Donc, ce nœud est enveloppant "quelque chose" à l'intérieur de lui-même,

875
00:52:27,410 --> 00:52:29,640
mais il déclare aussi appelé un pointeur prochaine

876
00:52:29,640 --> 00:52:32,580
afin que nous puissions chaîne Alice à Bob à Charlie et ainsi de suite.

877
00:52:32,580 --> 00:52:36,700
Peut être NULL, mais ne doit pas nécessairement l'être.

878
00:52:36,700 --> 00:52:40,110
Toute question relative à ces tables de hachage? Ouais?

879
00:52:40,110 --> 00:52:46,190
[Étudiant posant la question, inintelligible] Tableau - bonne question.

880
00:52:46,190 --> 00:52:50,120
Pourquoi est-ce le mot char dans un tableau plutôt que char *?

881
00:52:50,120 --> 00:52:53,830
Dans cet exemple quelque peu arbitraire, je ne voulais pas avoir à recourir

882
00:52:53,830 --> 00:52:56,190
à malloc pour chacun des noms d'origine.

883
00:52:56,190 --> 00:52:59,530
Je voulais déclarer une quantité maximale de mémoire pour la chaîne

884
00:52:59,530 --> 00:53:06,020
pour que je puisse copier dans la structure Alice \ 0 et ne pas avoir à traiter avec malloc et free, etc.

885
00:53:06,020 --> 00:53:11,710
Mais je ne pouvais le faire que si je voulais être plus conscients de l'utilisation de l'espace. Bonne question.

886
00:53:11,710 --> 00:53:14,780
Essayons donc de généraliser l'écart de cette

887
00:53:14,780 --> 00:53:18,350
et de se concentrer le reste de la journée sur les structures de données plus généralement

888
00:53:18,350 --> 00:53:21,170
et d'autres problèmes que nous pouvons résoudre en utilisant les mêmes principes

889
00:53:21,170 --> 00:53:24,590
même si les structures de données elles-mêmes peuvent différer dans le détail.

890
00:53:24,590 --> 00:53:27,910
>> Ainsi, il s'avère en informatique, les arbres sont très fréquents.

891
00:53:27,910 --> 00:53:29,760
Et vous pouvez penser à une sorte d'arbre comme un arbre de la famille,

892
00:53:29,760 --> 00:53:31,830
où il ya des racines, une matriarche ou patriarche,

893
00:53:31,830 --> 00:53:34,540
grand-mère ou grand-père ou une version antérieure de retour,

894
00:53:34,540 --> 00:53:38,880
sous lequel sont maman et papa ou frères et sœurs divers ou autres.

895
00:53:38,880 --> 00:53:42,500
Ainsi, une structure d'arborescence des nœuds et il a des enfants,

896
00:53:42,500 --> 00:53:45,260
généralement 0 ou plusieurs enfants pour chaque noeud.

897
00:53:45,260 --> 00:53:47,320
Et une partie du jargon que vous voyez sur cette photo ici

898
00:53:47,320 --> 00:53:50,630
est l'un des petits enfants ou petits-enfants sur les bords

899
00:53:50,630 --> 00:53:52,330
qui n'ont pas de flèches qui en émanent,

900
00:53:52,330 --> 00:53:55,070
ce sont les feuilles que l'on appelle, et toute personne à l'intérieur

901
00:53:55,070 --> 00:53:58,790
est un noeud interne, vous pouvez appeler ça le long de ces lignes.

902
00:53:58,790 --> 00:54:01,430
Mais cette structure est assez commun. Celui-ci est un peu arbitraire.

903
00:54:01,430 --> 00:54:04,930
Nous avons un enfant sur la gauche, nous avons trois enfants sur la droite,

904
00:54:04,930 --> 00:54:06,830
deux enfants en bas à gauche.

905
00:54:06,830 --> 00:54:10,740
Donc, nous pouvons avoir différentes tailles d'arbres, mais si nous commençons à normaliser les choses,

906
00:54:10,740 --> 00:54:15,330
et vous pouvez vous rappeler cette vidéo de Patrick sur binaire de recherche à partir d'un court précédente

907
00:54:15,330 --> 00:54:19,490
en ligne, recherche binaire ne doit pas être mis en œuvre avec un tableau

908
00:54:19,490 --> 00:54:21,410
ou des morceaux de papier sur un tableau noir.

909
00:54:21,410 --> 00:54:25,490
Supposons que vous vouliez stocker vos numéros dans une structure plus sophistiquée des données.

910
00:54:25,490 --> 00:54:27,680
Vous pouvez créer un arbre comme celui-ci.

911
00:54:27,680 --> 00:54:35,290
Vous pourriez avoir un noeud déclaré à C, et ce nœud peut avoir au moins deux éléments à l'intérieur de celui-ci.

912
00:54:35,290 --> 00:54:39,470
L'un est le numéro que vous souhaitez mémoriser, et l'autre est - bien, nous avons besoin d'une autre.

913
00:54:39,470 --> 00:54:41,540
L'autre est ses enfants.

914
00:54:41,540 --> 00:54:45,150
Alors, voici une autre structure de données. Cette fois-ci, un noeud est défini comme le stockage d'un nombre n

915
00:54:45,150 --> 00:54:49,060
puis deux pointeurs, l'enfant gauche et à droite l'enfant.

916
00:54:49,060 --> 00:54:52,100
Et ils ne sont pas arbitraires. Ce qui est intéressant à propos de cet arbre?

917
00:54:52,100 --> 00:55:00,550
>> Quelle est la tendance dans la façon dont nous avons posé cette out ou comment Patrick le mit dans sa vidéo?

918
00:55:00,550 --> 00:55:02,790
C'est un peu évident qu'il ya un tri qui se passe ici,

919
00:55:02,790 --> 00:55:04,460
mais quelle est la règle simple? Ouais?

920
00:55:04,460 --> 00:55:08,350
[Réponse de l'étudiant, inintelligible]

921
00:55:08,350 --> 00:55:12,040
Parfait. Si vous jeter un regard sur cela, vous voyez les petits chiffres sur la gauche,

922
00:55:12,040 --> 00:55:14,690
grands nombres sur la gauche, mais c'est vrai pour chaque nœud.

923
00:55:14,690 --> 00:55:20,370
Pour chaque nœud, son fils gauche inférieure à ce qu'elle et son enfant le droit supérieur à celui-ci.

924
00:55:20,370 --> 00:55:25,210
Ce que cela signifie est maintenant si je veux chercher cette structure de données pour, par exemple, le nombre 44,

925
00:55:25,210 --> 00:55:29,320
Je dois commencer à la racine, parce que l'ensemble de ces structures de données plus complexes maintenant,

926
00:55:29,320 --> 00:55:31,910
nous avons seulement un pointeur vers une chose, le commencement.

927
00:55:31,910 --> 00:55:35,010
Et dans ce cas, le début est la racine. Ce n'est pas l'extrémité gauche,

928
00:55:35,010 --> 00:55:39,530
c'est la racine de cette structure. Alors que je vois ici a 55 ans, et je suis à la recherche 44.

929
00:55:39,530 --> 00:55:41,430
Quelle direction dois-je aller?

930
00:55:41,430 --> 00:55:45,680
Eh bien, je veux aller à gauche, parce que, évidemment, vers la droite va être trop grand.

931
00:55:45,680 --> 00:55:49,050
Donc remarquer ici, vous êtes en quelque sorte le plan conceptuel couper l'arbre en deux

932
00:55:49,050 --> 00:55:51,700
parce que vous n'allez jamais jusqu'à la droite.

933
00:55:51,700 --> 00:55:55,410
Alors maintenant, je vais partir de la 55 à la 33. Elle est trop petite d'un nombre.

934
00:55:55,410 --> 00:56:01,590
Je suis à la recherche de 44 ans, mais maintenant je sais pas si 44 est dans cet arbre, je peux rendre à l'évidence vers la droite.

935
00:56:01,590 --> 00:56:04,460
Encore une fois, je suis d'élagage de l'arbre en deux.

936
00:56:04,460 --> 00:56:06,780
C'est à peu près identique, conceptuellement, à l'annuaire téléphonique.

937
00:56:06,780 --> 00:56:09,510
Elle est identique à ce que nous avons fait avec les papiers sur le tableau noir,

938
00:56:09,510 --> 00:56:13,940
mais c'est une structure plus sophistiquée qui nous permet de réellement faire

939
00:56:13,940 --> 00:56:16,880
cette diviser et conquérir par la conception de l'algorithme,

940
00:56:16,880 --> 00:56:19,420
et en fait, en traversant une structure comme celle - oups.

941
00:56:19,420 --> 00:56:22,870
Traversant une structure comme celle-ci, où il est seulement «aller de cette façon ou aller dans ce sens»,

942
00:56:22,870 --> 00:56:26,870
signifie tout ce code qui pliait votre esprit d'abord quand sa mise en œuvre dans la section

943
00:56:26,870 --> 00:56:31,270
ou en marchant à travers elle à la maison, pour la recherche binaire, en utilisant la récursivité ou itération,

944
00:56:31,270 --> 00:56:35,060
c'est une douleur dans le cou. Trouvez l'élément du milieu, puis faites votre arrondi vers le haut ou vers le bas.

945
00:56:35,060 --> 00:56:39,230
>> Il ya une beauté à ce que nous pouvons maintenant utiliser la récursivité à nouveau,

946
00:56:39,230 --> 00:56:43,760
mais beaucoup plus propre. En effet, si vous êtes au numéro 55 et que vous voulez trouver 44,

947
00:56:43,760 --> 00:56:48,450
vous allez à gauche dans ce cas, que faites-vous? Vous exécutez l'algorithme exactement la même.

948
00:56:48,450 --> 00:56:51,560
Vous vérifiez la valeur du nœud, puis vous allez à gauche ou à droite.

949
00:56:51,560 --> 00:56:53,670
Ensuite, vous vérifiez la valeur du nœud, aller à gauche ou à droite.

950
00:56:53,670 --> 00:56:56,710
Ceci est parfaitement adapté à la récursivité.

951
00:56:56,710 --> 00:57:00,920
Ainsi, même si dans le passé nous avons fait quelques exemples assez arbitraires impliquant la récursivité

952
00:57:00,920 --> 00:57:03,430
qui n'ont pas besoin d'être récursive, avec stuctures de données,

953
00:57:03,430 --> 00:57:07,820
en particulier les arbres, c'est une parfaite application de cette idée de prendre un problème,

954
00:57:07,820 --> 00:57:12,920
elle diminue, et ensuite de résoudre le même type d', mais plus petite, d'un programme.

955
00:57:12,920 --> 00:57:14,590
>> Donc, il ya une autre structure de données que l'on peut présenter.

956
00:57:14,590 --> 00:57:18,760
Celui-ci est conçu de prime abord de regarder cryptique, mais celui-ci est incroyable.

957
00:57:18,760 --> 00:57:25,090
C'est donc une structure de données appelée trie, trie, qui est héritée de la récupération des mots,

958
00:57:25,090 --> 00:57:30,210
qui ne se prononce pas re-essayer-val, mais c'est ce que le monde appelle ces choses. Tente. T-r-i-e.

959
00:57:30,210 --> 00:57:35,190
Il s'agit d'une structure arborescente d'une certaine sorte, mais chacun des nœuds dans un trie

960
00:57:35,190 --> 00:57:41,280
semble être quoi? Et c'est un peu trompeur, car c'est le genre de abrégées.

961
00:57:41,280 --> 00:57:45,960
Mais il semble que chaque nœud de la structure arborescente est en fait un tableau.

962
00:57:45,960 --> 00:57:48,840
Et même si l'auteur de ce schéma ne l'a pas montré,

963
00:57:48,840 --> 00:57:54,130
dans ce cas, cette trie est une structure de données dont le but dans la vie est de stocker des mots

964
00:57:54,130 --> 00:57:57,330
comme A-l-i-c-e ou b-O-n.

965
00:57:57,330 --> 00:58:02,480
Et la façon dont ce stocke les données Alice et Bob et Charlie et Anita et ainsi de suite

966
00:58:02,480 --> 00:58:06,970
est-il utilise un tableau de manière à stocker Alice dans une structure arborescente,

967
00:58:06,970 --> 00:58:09,820
on commence par le nœud racine qui ressemble à un tableau,

968
00:58:09,820 --> 00:58:12,080
et il a été écrit en notation abrégée.

969
00:58:12,080 --> 00:58:15,070
L'auteur omis abcdefg parce qu'il n'y avait pas de noms avec cela.

970
00:58:15,070 --> 00:58:19,150
Ils ne montrent M et P et T, mais dans ce cas,

971
00:58:19,150 --> 00:58:22,780
Passons loin de Alice et Bob et Charlie pour certains noms qui sont ici.

972
00:58:22,780 --> 00:58:25,670
Maxwell est en fait dans ce schéma.

973
00:58:25,670 --> 00:58:29,570
Alors, comment le magasin M auteur-a-x-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
Il ou elle a commencé à le nœud racine, et se rendit à [M], donc environ 13, l'emplacement 13 dans le tableau.

975
00:58:36,990 --> 00:58:40,750
Puis, à partir de là, il ya un pointeur.

976
00:58:40,750 --> 00:58:42,760
Un pointeur menant à un autre tableau.

977
00:58:42,760 --> 00:58:47,880
De là, l'auteur indexé dans ce tableau à l'emplacement A, comme le montre il ya en haut à gauche,

978
00:58:47,880 --> 00:58:52,250
et puis il ou elle a suivi ce pointeur à un autre tableau,

979
00:58:52,250 --> 00:58:55,460
et alla le pointeur à l'endroit X.

980
00:58:55,460 --> 00:58:59,840
Ensuite, dans le prochain emplacement gamme W, E, L, L, et ainsi de suite,

981
00:58:59,840 --> 00:59:03,090
et enfin, nous allons effectivement essayer de mettre une photo à cette question.

982
00:59:03,090 --> 00:59:05,380
À quoi ressemble un noeud comme dans le code?

983
00:59:05,380 --> 00:59:11,820
Un nœud dans une structure arborescente contient un tableau de pointeurs vers d'autres nœuds.

984
00:59:11,820 --> 00:59:16,090
Mais il a aussi obtenu d'être une sorte de valeur booléenne, du moins dans cette mise en œuvre.

985
00:59:16,090 --> 00:59:18,770
Il m'arrive de l'appeler is_word. Pourquoi?

986
00:59:18,770 --> 00:59:22,670
Parce que lorsque vous insérez Maxwell, vous n'êtes pas l'insertion

987
00:59:22,670 --> 00:59:25,300
rien dans cette structure de données.

988
00:59:25,300 --> 00:59:27,480
Vous n'êtes pas écrit M. Vous n'êtes pas écrire X.

989
00:59:27,480 --> 00:59:30,240
Tout ce que vous faites, c'est à la suite des pointeurs.

990
00:59:30,240 --> 00:59:33,360
Le pointeur qui représente M, alors le pointeur qui représente A,

991
00:59:33,360 --> 00:59:36,310
alors que le pointeur représente X, alors W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
mais ce que vous devez faire à la fin est une sorte de go, vérifier, je suis arrivé à cet endroit.

993
00:59:41,950 --> 00:59:45,560
Il y avait un mot qui se termine ici, dans la structure de données.

994
00:59:45,560 --> 00:59:48,190
>> Alors qu'est un trie est vraiment rempli de l'auteur a choisi de représenter

995
00:59:48,190 --> 00:59:51,880
ces terminus de petits triangles.

996
00:59:51,880 --> 00:59:56,470
Cela signifie simplement que le fait que ce triangle est ici, cette valeur booléenne true

997
00:59:56,470 --> 00:59:59,200
signifie que si vous allez vers l'arrière dans l'arborescence,

998
00:59:59,200 --> 01:00:02,420
ce qui signifie un mot nommé Maxwell est à cet égard.

999
01:00:02,420 --> 01:00:04,870
Mais le mot, foo, par exemple,

1000
01:00:04,870 --> 01:00:07,970
n'est pas dans l'arbre, parce que si je commence à le nœud racine ici en haut,

1001
01:00:07,970 --> 01:00:14,030
Il n'y a aucun pointeur f, pas de pointeur o, o pas de pointeur. Foo n'est pas un nom dans ce dictionnaire.

1002
01:00:14,030 --> 01:00:22,460
Mais par contre, la restructuration, t-u-r-i-n-g. Encore une fois, je n'ai pas stocker t ou u ou r ou i ou n ou g.

1003
01:00:22,460 --> 01:00:29,820
Mais je n'ai magasin dans cette structure de données d'une valeur de vrai chemin ici-bas dans ce nœud - dans l'arbre

1004
01:00:29,820 --> 01:00:33,030
en définissant cette valeur booléenne de is_word à true.

1005
01:00:33,030 --> 01:00:35,740
Ainsi, un trie est une sorte de méta cette structure très intéressante,

1006
01:00:35,740 --> 01:00:39,810
où vous n'êtes pas vraiment stocker les mots eux-mêmes pour ce type de dictionnaire.

1007
01:00:39,810 --> 01:00:45,100
Pour être clair, vous êtes juste stocker oui ou non, il ya un mot qui se termine ici.

1008
01:00:45,100 --> 01:00:46,430
>> Maintenant, quel est l'implication?

1009
01:00:46,430 --> 01:00:51,120
Si vous avez 150.000 mots dans un dictionnaire que vous essayez de stocker dans la mémoire

1010
01:00:51,120 --> 01:00:53,400
en utilisant quelque chose comme une liste chaînée,

1011
01:00:53,400 --> 01:00:56,870
vous allez avoir 150.000 nœuds de votre liste chaînée.

1012
01:00:56,870 --> 01:01:00,250
Et trouver un de ces mots par ordre alphabétique pourraient en O (n).

1013
01:01:00,250 --> 01:01:04,370
Le temps linéaire. Mais dans le cas présent d'une structure arborescente,

1014
01:01:04,370 --> 01:01:09,210
quelle est la durée de trouver un mot?

1015
01:01:09,210 --> 01:01:17,390
Il s'avère que la beauté ici, c'est que même si vous avez déjà 149.999 mots dans ce dictionnaire,

1016
01:01:17,390 --> 01:01:20,170
comme mis en oeuvre avec cette structure de données,

1017
01:01:20,170 --> 01:01:25,560
combien de temps faut-il pour trouver ou insérez une personne de plus dans les détails, comme Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Eh bien, ce n'est que 5, peut-être 6 étapes pour le caractère de fin.

1019
01:01:30,640 --> 01:01:32,880
Parce que le presense d'autres noms dans la structure

1020
01:01:32,880 --> 01:01:35,340
ne pas obtenir de la manière d'insérer Alice.

1021
01:01:35,340 --> 01:01:39,640
En outre, trouver Alice fois il ya 150.000 mots dans ce dictionnaire

1022
01:01:39,640 --> 01:01:41,960
ne pas mettre dans votre manière de trouver Alice à tous,

1023
01:01:41,960 --> 01:01:46,880
car Alice est. . . . . ici, parce que j'ai trouvé une valeur booléenne.

1024
01:01:46,880 --> 01:01:50,920
Et s'il n'y a pas boolean true, alors Alice n'est pas dans cette structure de données de mots.

1025
01:01:50,920 --> 01:01:56,220
En d'autres termes, le temps de fonctionnement de trouver des choses et en insérant les choses dans cette nouvelle

1026
01:01:56,220 --> 01:02:01,920
structure de données arborescente est O - il n'est pas n.

1027
01:02:01,920 --> 01:02:05,730
Parce que le presense de 150.000 personnes n'a aucun effet sur Alice, il semble.

1028
01:02:05,730 --> 01:02:11,560
Alors que nous appellerons k, où k est la longueur maximale d'un mot en anglais

1029
01:02:11,560 --> 01:02:14,050
qui est généralement pas plus de 20-quelque chose caractères.

1030
01:02:14,050 --> 01:02:17,940
Si k est une constante. Ainsi, le Saint-Graal, nous semblons avoir trouvé maintenant

1031
01:02:17,940 --> 01:02:26,000
est celle d'une structure arborescente, la constante de temps pour des inserts, pour les recherches, de délétions.

1032
01:02:26,000 --> 01:02:29,170
Parce que le nombre de choses déjà dans la structure,

1033
01:02:29,170 --> 01:02:32,600
qui ne sont pas encore physiquement. Encore une fois, ils sont juste une sorte de coché, oui ou non,

1034
01:02:32,600 --> 01:02:35,050
n'a aucun impact sur sa durée future.

1035
01:02:35,050 --> 01:02:37,940
>> Mais il doit bien y avoir un hic, sinon nous n'aurions pas perdu autant de temps

1036
01:02:37,940 --> 01:02:41,460
sur toutes ces structures de données autres que pour arriver enfin à l'un des secrets c'est incroyable.

1037
01:02:41,460 --> 01:02:46,410
Alors quel prix payons-nous pour atteindre cette grandeur ici? L'espace.

1038
01:02:46,410 --> 01:02:49,010
Cette chose est énorme. Et la raison pour laquelle l'auteur

1039
01:02:49,010 --> 01:02:52,400
n'a pas le présenter ici, notez que toutes ces choses qui ressemblent à des tableaux,

1040
01:02:52,400 --> 01:02:55,400
il n'a pas tiré le reste de l'arbre, le reste de la structure arborescente,

1041
01:02:55,400 --> 01:02:58,060
parce qu'ils sont tout simplement pas pertinents à l'histoire.

1042
01:02:58,060 --> 01:03:01,870
Mais tous ces nœuds sont super large, et chaque noeud de l'arbre prend

1043
01:03:01,870 --> 01:03:07,780
26 ou en fait, pourrait être de 27 caractères, car dans ce cas, j'ai été y compris l'espace pour l'apostrophe

1044
01:03:07,780 --> 01:03:09,980
afin que nous puissions avoir des mots apostropha.

1045
01:03:09,980 --> 01:03:14,450
Dans ce cas, ce sont des tableaux de large. Ainsi, même si elles ne sont pas picutured,

1046
01:03:14,450 --> 01:03:18,190
cela prend une énorme quantité de RAM.

1047
01:03:18,190 --> 01:03:20,670
Qui pourrait être bien, especilly dans le matériel moderne,

1048
01:03:20,670 --> 01:03:25,650
mais c'est le compromis. Nous recevons moins de temps en dépensant plus d'espace.

1049
01:03:25,650 --> 01:03:28,580
Alors, où est-ce tout va?

1050
01:03:28,580 --> 01:03:32,640
Eh bien, faisons - nous allons voir ici.

1051
01:03:32,640 --> 01:03:39,510
Faisons un saut à ce gars là.

1052
01:03:39,510 --> 01:03:43,450
>> Croyez-le ou non, autant de plaisir que C a été pendant un certain temps maintenant,

1053
01:03:43,450 --> 01:03:48,130
nous atteignons le point le semestre où il est temps de passer à des choses plus modernes.

1054
01:03:48,130 --> 01:03:50,950
Les choses à un niveau supérieur. Et même si pour les deux prochaines semaines

1055
01:03:50,950 --> 01:03:54,580
nous allons continuer à nous plonger dans le monde des pointeurs et gestion de la mémoire

1056
01:03:54,580 --> 01:03:57,210
pour obtenir que le confort avec lequel nous pouvons construire,

1057
01:03:57,210 --> 01:04:01,270
la fin du jeu est finalement d'introduire, ironiquement, pas cette langue.

1058
01:04:01,270 --> 01:04:03,330
Nous passerons, comme 10 minutes à parler de HTML.

1059
01:04:03,330 --> 01:04:05,950
Toutes HTML est un langage de balisage, et ce qui est un langage de balisage

1060
01:04:05,950 --> 01:04:10,220
est cette série de parenthèses ouvertes et fermées supports qui disent «faire de cette audacieuse»

1061
01:04:10,220 --> 01:04:12,000
«Faire ce italique» «faire ce centrée.

1062
01:04:12,000 --> 01:04:14,250
Ce n'est pas tout ce qui intellectuellement intéressant, mais c'est super utile.

1063
01:04:14,250 --> 01:04:16,650
Et ce n'est certainement omniprésente de nos jours.

1064
01:04:16,650 --> 01:04:19,450
Mais ce qui est puissant sur le monde du HTML, et la programmation web, plus généralement,

1065
01:04:19,450 --> 01:04:25,910
est de construire des choses dynamiques; écrire du code dans des langages comme PHP ou Python ou Ruby ou Java ou C #.

1066
01:04:25,910 --> 01:04:30,360
Vraiment, quelle que soit la langue de votre choix, et générer une page HTML dynamique.

1067
01:04:30,360 --> 01:04:32,960
Générer quelque chose qui s'appelle CSS dynamiquement.

1068
01:04:32,960 --> 01:04:35,810
Feuilles de style en cascade, ce qui est aussi de l'esthétique.

1069
01:04:35,810 --> 01:04:41,360
Ainsi, même si, aujourd'hui, si je vais à un certain site Web comme Google.com familier,

1070
01:04:41,360 --> 01:04:46,100
et je vais voir, développeur, voir la source, qui peut-être vous avez fait avant,

1071
01:04:46,100 --> 01:04:49,800
mais allez voir la source, ce truc ressemble probablement assez cryptique.

1072
01:04:49,800 --> 01:04:55,320
Mais c'est le code sous-jacent qui implémente Google.com.

1073
01:04:55,320 --> 01:04:57,940
Sur l'extrémité avant. Et en fait, tout cela est moelleux choses esthétique.

1074
01:04:57,940 --> 01:05:01,740
C'est CSS ici. Si je continue à défiler vers le bas nous aurons des choses à code couleur.

1075
01:05:01,740 --> 01:05:06,890
Il s'agit HTML. Code de Google ressemble à un gâchis, mais si je fait ouvrir une autre fenêtre,

1076
01:05:06,890 --> 01:05:09,380
nous pouvons voir une certaine structure à ce sujet.

1077
01:05:09,380 --> 01:05:12,640
Si j'ouvre cette place, remarquez ici, c'est un peu plus lisible.

1078
01:05:12,640 --> 01:05:16,850
Nous allons voir avant longtemps, cette balise, [mot] est une balise,

1079
01:05:16,850 --> 01:05:23,520
HTML, tête, corps, div, script, zone de texte, la durée, centré, div.

1080
01:05:23,520 --> 01:05:26,770
Et cela est également trier des cryptique l'avenir, à première vue,

1081
01:05:26,770 --> 01:05:30,890
mais tout ce gâchis suit certains schémas et des modèles reproductibles,

1082
01:05:30,890 --> 01:05:33,850
de sorte que dès que nous aurons les bases vers le bas, vous serez en mesure d'écrire du code comme ceci

1083
01:05:33,850 --> 01:05:37,550
puis de manipuler le code comme ceci utilisant un autre langage, appelé JavaScript.

1084
01:05:37,550 --> 01:05:40,440
Et JavaScript est un langage qui s'exécute à l'intérieur d'un navigateur

1085
01:05:40,440 --> 01:05:44,380
aujourd'hui que nous utilisons sur les terrains de Harvard, de l'outil de magasinage cours qui utilise google maps

1086
01:05:44,380 --> 01:05:48,660
pour vous donner un tas de dynamisme, Facebook vous donne pour montrer mises à jour d'état instantanés,

1087
01:05:48,660 --> 01:05:51,430
Twitter qu'il utilise pour vous montrer tweets instantanément.

1088
01:05:51,430 --> 01:05:53,820
Tout cela, nous allons commencer à nous plonger po

1089
01:05:53,820 --> 01:05:57,190
Mais pour y arriver, nous avons besoin de comprendre quelque chose sur l'Internet.

1090
01:05:57,190 --> 01:06:01,130
Ce clip ici est juste une minute, et supposons pour l'instant c'est, en fait,

1091
01:06:01,130 --> 01:06:08,380
comment l'Internet fonctionne comme un teaser pour ce qui est sur le point de venir. Je vous donne "Warriors of the Net".

1092
01:06:08,380 --> 01:06:14,720
>> [♫ ♫ musique chorale lente]

1093
01:06:14,720 --> 01:06:20,450
[Narrateur Homme] Il est venu avec un message.

1094
01:06:20,450 --> 01:06:23,770
Avec un protocole qui lui est propre.

1095
01:06:23,770 --> 01:06:37,270
[♫ ♫ musique électronique plus rapide]

1096
01:06:37,270 --> 01:06:41,330
Il est venu à un monde de pare-feu cool, insouciant routeurs,

1097
01:06:41,330 --> 01:06:45,690
et les dangers bien pires que la mort.

1098
01:06:45,690 --> 01:06:55,400
Il est rapide. Il est fort. Il est TCP / IP, et il a votre adresse.

1099
01:06:55,400 --> 01:06:59,250
Warriors of the net.

1100
01:06:59,250 --> 01:07:05,290
[Malan] La semaine prochaine, alors. L'Internet. Programmation Web. C'est CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]