1
00:00:00,000 --> 00:00:05,259

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Donc, en CS50, nous avons couvert
un grand nombre de différentes structures de données,

3
00:00:08,300 --> 00:00:09,180
droit?

4
00:00:09,180 --> 00:00:11,420
Nous avons vu des tableaux, et Linked
les listes et les tables de hachage,

5
00:00:11,420 --> 00:00:15,210
et tente, piles et files d'attente.

6
00:00:15,210 --> 00:00:17,579
On y apprend aussi un peu
des arbres et des tas,

7
00:00:17,579 --> 00:00:20,120
mais vraiment ces tout simplement finir
par être variations sur un thème.

8
00:00:20,120 --> 00:00:22,840
Il ya vraiment ces
type de quatre idées de base

9
00:00:22,840 --> 00:00:25,190
que tout le monde peut se résumer à.

10
00:00:25,190 --> 00:00:28,150
Tableaux, listes chaînées,
Les tables de hachage, et tente.

11
00:00:28,150 --> 00:00:30,720
Et comme je l'ai dit, il y
sont des variations sur eux,

12
00:00:30,720 --> 00:00:32,720
mais cela est assez
de choses pour résumer

13
00:00:32,720 --> 00:00:38,140
tout ce que nous allons parler
dans cette catégorie en termes de C.

14
00:00:38,140 --> 00:00:40,140
>> Mais comment ces toutes les mesures en place, non?

15
00:00:40,140 --> 00:00:44,265
Nous avons parlé des avantages et des inconvénients
de chaque dans les vidéos distinctes sur eux,

16
00:00:44,265 --> 00:00:46,390
mais il ya beaucoup de chiffres
se jeter autour.

17
00:00:46,390 --> 00:00:48,723
Il ya beaucoup de général
pensées se jeter autour.

18
00:00:48,723 --> 00:00:51,950
Essayons et consolider
en un seul endroit.

19
00:00:51,950 --> 00:00:55,507
Disons peser les avantages contre
les inconvénients, et considèrent

20
00:00:55,507 --> 00:00:57,340
laquelle structure de données
pourrait être le droit des données

21
00:00:57,340 --> 00:01:01,440
la structure de votre situation particulière,
quel que soit le type de données que vous stockez.

22
00:01:01,440 --> 00:01:06,625
Vous n'êtes pas nécessairement toujours besoin de
utiliser l'insertion super rapide, la suppression,

23
00:01:06,625 --> 00:01:10,761
et recherche d'un trie si vous avez vraiment
ne se soucient pas insertion et de suppression

24
00:01:10,761 --> 00:01:11,260
trop.

25
00:01:11,260 --> 00:01:13,968
Si vous avez juste besoin rapidement aléatoire
l'accès, peut-être un tableau est mieux.

26
00:01:13,968 --> 00:01:15,340
Alors disons que distiller.

27
00:01:15,340 --> 00:01:18,530
Parlons de chacun des quatre
grands types de structures de données

28
00:01:18,530 --> 00:01:21,720
que nous avons parlé, et
voir juste au moment où ils pourraient être bon,

29
00:01:21,720 --> 00:01:23,340
et quand ils pourraient ne pas être si bon.

30
00:01:23,340 --> 00:01:24,610
Commençons donc avec les tableaux.

31
00:01:24,610 --> 00:01:27,300
Donc, l'insertion, que ce genre de mauvais.

32
00:01:27,300 --> 00:01:31,350
>> Insertion à la fin d'un tableau est OK,
si nous construisons un tableau que nous allons.

33
00:01:31,350 --> 00:01:33,570
Mais si nous avons besoin d'insérer
éléments dans le milieu,

34
00:01:33,570 --> 00:01:35,550
penser à l'insertion
Trier, il ya beaucoup

35
00:01:35,550 --> 00:01:37,510
de passage à adapter un élément là-dedans.

36
00:01:37,510 --> 00:01:41,170
Et donc si nous allons insérer
partout, mais la fin d'un tableau,

37
00:01:41,170 --> 00:01:43,590
qui est sans doute pas si grand.

38
00:01:43,590 --> 00:01:46,710
>> De même, la suppression, à moins que nous sommes
la suppression à partir de la fin d'un tableau,

39
00:01:46,710 --> 00:01:49,810
est probablement aussi pas si grand, si
nous ne voulons pas laisser des espaces vides à,

40
00:01:49,810 --> 00:01:50,790
qui habituellement nous ne faisons pas.

41
00:01:50,790 --> 00:01:54,700
Nous voulons supprimer un élément, et
puis sorte de rendre à nouveau serré.

42
00:01:54,700 --> 00:01:57,670
Et donc des éléments de suppression
un tableau, aussi pas si grande.

43
00:01:57,670 --> 00:01:58,820
>> Lookup, cependant, est grande.

44
00:01:58,820 --> 00:02:00,920
Nous avons accès aléatoire,
recherche constante de temps.

45
00:02:00,920 --> 00:02:03,800
Nous disons seulement sept, et nous allons
au tableau relocalisation sept.

46
00:02:03,800 --> 00:02:05,907
Nous disons 20, au rendez-vous à
tableau réinstallation 20.

47
00:02:05,907 --> 00:02:07,240
Nous ne disposons pas d'itérer à travers.

48
00:02:07,240 --> 00:02:08,630
Cela est assez bon.

49
00:02:08,630 --> 00:02:11,020
>> Les tableaux sont aussi relativement facile à trier.

50
00:02:11,020 --> 00:02:14,040
Chaque fois que nous avons parlé d'un tri
algorithme, comme la sélection sorte,

51
00:02:14,040 --> 00:02:18,820
tri par insertion, bulle tri, de fusion
Trier, nous avons toujours utilisé des tableaux de le faire,

52
00:02:18,820 --> 00:02:21,860
car les tableaux sont assez faciles à
trier, par rapport aux structures de données

53
00:02:21,860 --> 00:02:22,970
nous avons vu jusqu'à présent.

54
00:02:22,970 --> 00:02:24,320
>> Ils sont aussi relativement faible.

55
00:02:24,320 --> 00:02:25,695
Il n'y a pas beaucoup d'espace supplémentaire.

56
00:02:25,695 --> 00:02:29,210
Vous venez de mettre de côté exactement autant
que vous avez besoin pour stocker vos données,

57
00:02:29,210 --> 00:02:30,320
et voilà à peu près tout.

58
00:02:30,320 --> 00:02:33,180
Donc, ils sont assez petite
et efficace en ce sens.

59
00:02:33,180 --> 00:02:36,000
Mais un autre inconvénient, cependant,
est qu'ils sont fixés à la taille.

60
00:02:36,000 --> 00:02:38,630
Nous devons déclarer exactement comment
Nous voulons que notre grand tableau à être,

61
00:02:38,630 --> 00:02:39,940
et nous obtenons un seul coup à elle.

62
00:02:39,940 --> 00:02:41,280
Nous ne pouvons pas grandir et rétrécir.

63
00:02:41,280 --> 00:02:44,582
>> Si nous avons besoin de grandir ou rétrécir, nous
besoin de déclarer un tableau tout à fait nouveau,

64
00:02:44,582 --> 00:02:47,750
copier tous les éléments de la
premier tableau dans la deuxième rangée.

65
00:02:47,750 --> 00:02:51,410
Et si nous mal calculé que
temps, nous avons besoin de le faire à nouveau.

66
00:02:51,410 --> 00:02:52,760
Pas si bien.

67
00:02:52,760 --> 00:02:58,750
Donc tableaux ne nous donnent pas la flexibilité
d'avoir un nombre variable d'éléments.

68
00:02:58,750 --> 00:03:01,320
>> Avec une liste chaînée,
insertion est assez facile.

69
00:03:01,320 --> 00:03:03,290
Nous louvoyons juste sur le devant.

70
00:03:03,290 --> 00:03:04,892
La suppression est également assez facile.

71
00:03:04,892 --> 00:03:06,100
Nous devons trouver les éléments.

72
00:03:06,100 --> 00:03:07,270
Qui impliquent quelques recherches.

73
00:03:07,270 --> 00:03:10,270
>> Mais une fois que vous avez trouvé l'élément
vous cherchez, tout ce que vous devez faire

74
00:03:10,270 --> 00:03:12,830
est de changer un pointeur,
peut-être deux si vous avez

75
00:03:12,830 --> 00:03:15,151
un lié films-- un doublement
liste chaînée, rather--

76
00:03:15,151 --> 00:03:16,650
et puis vous pouvez simplement libérer le noeud.

77
00:03:16,650 --> 00:03:18,399
Vous ne devez pas passer
tout autour.

78
00:03:18,399 --> 00:03:22,090
Vous venez de changer deux pointeurs,
de sorte que est assez rapide.

79
00:03:22,090 --> 00:03:23,470
>> Lookup est mauvais, non?

80
00:03:23,470 --> 00:03:26,280
Pour que nous puissions trouver une
élément dans une liste chaînée,

81
00:03:26,280 --> 00:03:29,154
si une ou deux fois lié,
nous devons linéaire fouiller.

82
00:03:29,154 --> 00:03:32,320
Nous devons commencer au début et
déplacer la fin, ou commencer à l'initiative de la fin

83
00:03:32,320 --> 00:03:33,860
au début.

84
00:03:33,860 --> 00:03:35,474
Nous ne avons plus accès aléatoire.

85
00:03:35,474 --> 00:03:37,265
Donc, si nous faisons un
beaucoup de recherche, peut-être

86
00:03:37,265 --> 00:03:39,830
une liste chaînée est pas
tout à fait aussi bon pour nous.

87
00:03:39,830 --> 00:03:43,750
>> Ils sont également très
difficiles à trier, à droite?

88
00:03:43,750 --> 00:03:45,666
La seule façon que vous pouvez
vraiment trier une liste chaînée

89
00:03:45,666 --> 00:03:47,870
est de faire le tri comme vous le construire.

90
00:03:47,870 --> 00:03:50,497
Mais si vous triez comme vous
construire, vous n'êtes plus

91
00:03:50,497 --> 00:03:51,830
des insertions rapides plus.

92
00:03:51,830 --> 00:03:53,746
Vous n'êtes pas seulement vireur
les choses sur le devant.

93
00:03:53,746 --> 00:03:55,710
Vous devez trouver le
place juste pour la mettre,

94
00:03:55,710 --> 00:03:57,820
puis votre insertion
devient à peu près aussi mauvais

95
00:03:57,820 --> 00:03:59,390
que l'insertion dans un tableau.

96
00:03:59,390 --> 00:04:03,130
Donc, les listes chaînées ne sont pas
si grand pour le tri des données.

97
00:04:03,130 --> 00:04:05,830
>> Ils sont aussi assez petit, de la taille d'une montre.

98
00:04:05,830 --> 00:04:08,496
Doublement liste chaînée légèrement
plus grand que les listes simplement liées,

99
00:04:08,496 --> 00:04:10,620
qui sont légèrement plus grand
que les tableaux, mais il est pas

100
00:04:10,620 --> 00:04:13,330
une énorme quantité d'espace perdu.

101
00:04:13,330 --> 00:04:18,730
Donc, si l'espace est à une prime, mais
pas une prime vraiment intense,

102
00:04:18,730 --> 00:04:22,180
ce pourrait être la bonne façon de faire.

103
00:04:22,180 --> 00:04:23,330
>> Les tables de hachage.

104
00:04:23,330 --> 00:04:25,850
Insertion dans une table de hachage
est assez simple.

105
00:04:25,850 --> 00:04:26,980
Il est un processus en deux étapes.

106
00:04:26,980 --> 00:04:30,700
Premièrement, nous devons exécuter nos données à travers
une fonction de hachage pour obtenir un code de hachage,

107
00:04:30,700 --> 00:04:37,550
puis on insère l'élément dans le
table de hachage des à cet endroit de code de hachage.

108
00:04:37,550 --> 00:04:40,879
>> Suppression, semblable à la liste chaînée,
est facile une fois que vous trouvez l'élément.

109
00:04:40,879 --> 00:04:43,170
Vous devez trouver le premier,
mais alors quand vous le supprimez,

110
00:04:43,170 --> 00:04:45,128
vous avez juste besoin d'échanger
un couple de pointeurs,

111
00:04:45,128 --> 00:04:47,250
si vous utilisez le chaînage séparé.

112
00:04:47,250 --> 00:04:49,942
Si vous utilisez de sondage,
ou si vous n'êtes pas

113
00:04:49,942 --> 00:04:51,650
utilisant chaînage du tout
dans votre table de hachage,

114
00:04:51,650 --> 00:04:53,040
suppression est effectivement très facile.

115
00:04:53,040 --> 00:04:57,134
Tout ce que vous devez faire est de hacher la
données, puis aller à cet endroit.

116
00:04:57,134 --> 00:04:58,925
Et en supposant que vous ne faites pas
Pour toute collision,

117
00:04:58,925 --> 00:05:01,650
vous serez en mesure de supprimer très rapidement.

118
00:05:01,650 --> 00:05:04,930
>> Maintenant, consultation est où les choses
obtenir un peu plus compliqué.

119
00:05:04,930 --> 00:05:06,910
Il est en moyenne meilleure
que les listes chaînées.

120
00:05:06,910 --> 00:05:09,560
Si vous utilisez le chaînage,
vous avez encore une liste chaînée,

121
00:05:09,560 --> 00:05:13,170
ce qui signifie que vous avez toujours la
recherche désavantage du une liste chaînée.

122
00:05:13,170 --> 00:05:18,390
Mais parce que vous prenez votre liés
liste et le diviser plus de 100 ou 1000

123
00:05:18,390 --> 00:05:25,380
ou n éléments dans votre table de hachage, vous êtes
listes chaînées sont tous un nième la taille.

124
00:05:25,380 --> 00:05:27,650
Ils sont tous sensiblement plus petite.

125
00:05:27,650 --> 00:05:32,080
Vous avez n liée listes place
d'une liste liée de taille n.

126
00:05:32,080 --> 00:05:34,960
>> Et donc ce monde réel constant
facteur, que nous avons généralement

127
00:05:34,960 --> 00:05:39,730
ne pas parler de la complexité du temps, il
ne fait effectivement une différence ici.

128
00:05:39,730 --> 00:05:43,020
Donc recherche est toujours linéaire
rechercher si vous utilisez le chaînage,

129
00:05:43,020 --> 00:05:46,780
mais la longueur de la liste
vous êtes à la recherche par le biais

130
00:05:46,780 --> 00:05:50,080
est très, très courte en comparaison.

131
00:05:50,080 --> 00:05:52,995
Encore une fois, si le tri est votre
but ici, la table de hachage

132
00:05:52,995 --> 00:05:54,370
probablement pas la bonne voie à suivre.

133
00:05:54,370 --> 00:05:56,830
Il suffit d'utiliser un tableau si le tri
est vraiment important pour vous.

134
00:05:56,830 --> 00:05:58,590
>> Et ils peuvent exécuter toute la gamme de la taille.

135
00:05:58,590 --> 00:06:01,640
Il est difficile de dire si une
Table hachage est petite ou grande,

136
00:06:01,640 --> 00:06:04,110
parce que cela dépend vraiment de
la taille de votre table de hachage est.

137
00:06:04,110 --> 00:06:07,340
Si vous allez seulement à stocker
cinq éléments dans votre table de hachage,

138
00:06:07,340 --> 00:06:10,620
et vous avez une table de hachage
avec 10.000 éléments en elle,

139
00:06:10,620 --> 00:06:12,614
vous êtes probablement perdre beaucoup d'espace.

140
00:06:12,614 --> 00:06:15,030
Contraste Vous être peut également
avoir des tables de hachage très compactes,

141
00:06:15,030 --> 00:06:18,720
mais le plus petit de votre table de hachage obtient,
le plus chacune de ces listes chaînées

142
00:06:18,720 --> 00:06:19,220
Gets.

143
00:06:19,220 --> 00:06:22,607
Et donc il n'y a vraiment aucun moyen de définir
exactement de la taille d'une table de hachage,

144
00:06:22,607 --> 00:06:24,440
mais il est probablement sûr
à-dire il est généralement

145
00:06:24,440 --> 00:06:27,990
va être plus grand qu'un liée
Liste stocker les mêmes données,

146
00:06:27,990 --> 00:06:30,400
mais inférieure à une trie.

147
00:06:30,400 --> 00:06:32,720
>> Et tente sont la quatrième
de ces structures

148
00:06:32,720 --> 00:06:34,070
que nous avons parlé.

149
00:06:34,070 --> 00:06:36,450
Insertion dans un trie est complexe.

150
00:06:36,450 --> 00:06:38,400
Il ya beaucoup de dynamique
allocation de mémoire,

151
00:06:38,400 --> 00:06:40,780
en particulier au début,
que vous commencez à construire.

152
00:06:40,780 --> 00:06:43,700
Mais il est temps constant.

153
00:06:43,700 --> 00:06:47,690
Il est seulement l'élément humain
ici qui le rend délicat.

154
00:06:47,690 --> 00:06:53,250
Avoir à rencontrer pointeur NULL, malloc
espace, allez-y, l'espace éventuellement malloc

155
00:06:53,250 --> 00:06:54,490
à partir de là à nouveau.

156
00:06:54,490 --> 00:06:58,880
Le genre de facteur d'intimidation de
pointeurs dans allocation dynamique de mémoire

157
00:06:58,880 --> 00:07:00,130
est l'obstacle à franchir.

158
00:07:00,130 --> 00:07:04,550
Mais une fois que vous avez terminé il, insertion
vient en fait assez simple,

159
00:07:04,550 --> 00:07:06,810
et il est certainement temps constant.

160
00:07:06,810 --> 00:07:07,680
>> La suppression est facile.

161
00:07:07,680 --> 00:07:11,330
Tout ce que vous devez faire est de descendre d'un
couple de pointeurs et gratuitement le noeud,

162
00:07:11,330 --> 00:07:12,420
de sorte que est assez bon.

163
00:07:12,420 --> 00:07:13,930
Lookup est également assez rapide.

164
00:07:13,930 --> 00:07:16,780
Il est seulement basé sur la
longueur de vos données.

165
00:07:16,780 --> 00:07:19,924
Donc, si toutes vos données est
cinq chaînes de caractères,

166
00:07:19,924 --> 00:07:22,590
par exemple, que vous stockez de cinq
chaînes de caractères dans votre trie,

167
00:07:22,590 --> 00:07:25,439
il ne faut que cinq étapes
à trouver ce que vous cherchez.

168
00:07:25,439 --> 00:07:28,480
Cinq est juste un facteur constant, de sorte
de plus, l'insertion, la suppression et recherche

169
00:07:28,480 --> 00:07:31,670
Voici les temps constant, efficace.

170
00:07:31,670 --> 00:07:34,880
>> Une autre chose est que votre Trie est
fait assez déjà trié, non?

171
00:07:34,880 --> 00:07:36,800
En vertu de la façon dont nous sommes
insérer des éléments,

172
00:07:36,800 --> 00:07:40,060
par lettre allant par lettre du
clé, chiffre par chiffre ou de la clé,

173
00:07:40,060 --> 00:07:45,084
habituellement, votre trie finit par être
sorte de tri que vous construisez.

174
00:07:45,084 --> 00:07:47,250
Il n'a pas fait vraiment
sens de penser sur le tri

175
00:07:47,250 --> 00:07:49,874
de la même manière que nous pensons à propos
avec des tableaux ou des listes liées,

176
00:07:49,874 --> 00:07:51,070
ou tables de hachage.

177
00:07:51,070 --> 00:07:54,780
Mais dans un certain sens, votre
Trie est triée comme vous allez.

178
00:07:54,780 --> 00:07:58,630
>> L'inconvénient, bien sûr, est que
un trie devient rapidement énorme.

179
00:07:58,630 --> 00:08:02,970
De tous les points de jonction, vous pourriez
have-- si votre clé est constitué de chiffres,

180
00:08:02,970 --> 00:08:04,880
vous avez 10 autres
endroits où vous pouvez aller, qui

181
00:08:04,880 --> 00:08:07,490
signifie que chaque nœud
contient des informations

182
00:08:07,490 --> 00:08:11,440
sur les données que vous souhaitez stocker
à ce noeud, plus 10 pointeurs.

183
00:08:11,440 --> 00:08:14,430
Qui, sur CS50 IDE, est de 80 octets.

184
00:08:14,430 --> 00:08:17,220
Donc, il est au moins 80 octets pour
chaque nœud que vous créez,

185
00:08:17,220 --> 00:08:19,240
et cela est même pas des données de comptage.

186
00:08:19,240 --> 00:08:24,950
Et si vos nœuds sont
lettres au lieu de chiffres,

187
00:08:24,950 --> 00:08:27,825
maintenant vous avez 26 pointeurs
de chaque emplacement.

188
00:08:27,825 --> 00:08:32,007
Et 26 fois 8 est probablement 200
octets, ou quelque chose comme ça.

189
00:08:32,007 --> 00:08:33,840
Et vous avez des capitaux
et vous peut lowercase--

190
00:08:33,840 --> 00:08:35,381
voir où je vais avec cela, non?

191
00:08:35,381 --> 00:08:37,500
Vos nœuds peuvent être vraiment
grande, et donc le trie

192
00:08:37,500 --> 00:08:40,470
lui-même, dans l'ensemble, peut
devenir vraiment grand, trop.

193
00:08:40,470 --> 00:08:42,630
Donc, si l'espace est à un niveau élevé
prime sur votre système,

194
00:08:42,630 --> 00:08:45,830
un trie pourrait ne pas être la bonne façon de
aller, même si ses autres avantages

195
00:08:45,830 --> 00:08:47,780
entrer en jeu.

196
00:08:47,780 --> 00:08:48,710
Je suis Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
Ceci est CS50.

198
00:08:50,740 --> 00:08:52,316