1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Parfois, lors de la construction d'un
programme, vous voudrez peut-être utiliser un

3
00:00:10,890 --> 00:00:13,190
structure de données appelée un dictionnaire.

4
00:00:13,190 --> 00:00:17,960
A Plans Dictionnaire touches, qui sont
généralement des chaînes, des valeurs, ints,

5
00:00:17,960 --> 00:00:21,900
caractères, un pointeur vers un objet,
ce que nous voulons.

6
00:00:21,900 --> 00:00:26,510
C'est comme les dictionnaires ordinaires
que la carte par le biais de mots définitions.

7
00:00:26,510 --> 00:00:29,440
>> Dictionnaires nous donnent l'
capacité à stocker des informations

8
00:00:29,440 --> 00:00:32,750
associé à quelque chose
et le regarder plus tard.

9
00:00:32,750 --> 00:00:36,620
Alors, comment pouvons-nous mettre en oeuvre effectivement un
dictionnaire, disons, le code C que nous pouvons

10
00:00:36,620 --> 00:00:38,460
utiliser dans un de nos programmes?

11
00:00:38,460 --> 00:00:41,790
Eh bien, il ya beaucoup de façons que
nous pourrions mettre en œuvre un dictionnaire.

12
00:00:41,790 --> 00:00:45,930
>> D'une part, nous pourrions utiliser un tableau qui nous
redimensionner dynamiquement ou nous pourrions utiliser une

13
00:00:45,930 --> 00:00:49,150
liste chaînée, table de hachage
ou d'un arbre binaire.

14
00:00:49,150 --> 00:00:52,250
Mais ce que nous choisissons, nous devrions
être conscient de l'efficacité et

15
00:00:52,250 --> 00:00:54,300
le rendement de la mise en œuvre.

16
00:00:54,300 --> 00:00:57,930
Nous devrions penser à l'algorithme utilisé
à insérer et rechercher des éléments dans

17
00:00:57,930 --> 00:00:59,120
notre structure de données.

18
00:00:59,120 --> 00:01:03,060
>> Pour l'instant, supposons que nous
vouloir utiliser des chaînes comme clés.

19
00:01:03,060 --> 00:01:07,290
Parlons une possibilité,
une structure de données appelée un trie.

20
00:01:07,290 --> 00:01:11,210
Alors, voici une représentation visuelle
d'une structure arborescente.

21
00:01:11,210 --> 00:01:14,590
>> Comme l'image l'indique, un trie
est une structure de données d'arbre avec

22
00:01:14,590 --> 00:01:16,050
noeuds reliés entre eux.

23
00:01:16,050 --> 00:01:19,420
Nous voyons qu'il ya clairement une racine
noeud avec quelques liens s'étendant à

24
00:01:19,420 --> 00:01:20,500
d'autres noeuds.

25
00:01:20,500 --> 00:01:23,040
Mais qu'est-ce que chaque nœud consiste?

26
00:01:23,040 --> 00:01:26,700
Si nous supposons que nous sommes le stockage de clés
avec seulement des caractères alphabétiques, et

27
00:01:26,700 --> 00:01:30,150
nous ne nous soucions pas de la capitalisation,
voici une définition d'un noeud

28
00:01:30,150 --> 00:01:31,100
suffira.

29
00:01:31,100 --> 00:01:34,130
>> Un objet dont le type est struct
noeud comporte deux parties

30
00:01:34,130 --> 00:01:35,740
appelé données et des enfants.

31
00:01:35,740 --> 00:01:39,200
Nous avons laissé la partie de données comme un commentaire
pour être remplacé par un composant

32
00:01:39,200 --> 00:01:43,190
déclaration lorsque le noeud de structure est
incorporé dans un programme C.

33
00:01:43,190 --> 00:01:47,040
La partie de données d'un nœud peut être un
Valeur booléenne pour indiquer si

34
00:01:47,040 --> 00:01:51,160
pas le nœud représente l'achèvement
d'une clé de dictionnaire ou il pourrait être un

35
00:01:51,160 --> 00:01:54,240
chaîne représentant la définition
d'un mot dans le dictionnaire.

36
00:01:54,240 --> 00:01:58,870
>> Nous utiliserons un visage souriant pour indiquer
lorsque des données sont présentes dans un noeud.

37
00:01:58,870 --> 00:02:02,310
Il ya 26 éléments dans notre
tableau pour enfants, un indice

38
00:02:02,310 --> 00:02:03,690
par caractère alphabétique.

39
00:02:03,690 --> 00:02:06,570
Nous verrons l'importance
de cette bientôt.

40
00:02:06,570 --> 00:02:10,759
>> Soyons un peu plus près du noeud racine
dans notre schéma, qui n'a pas de données

41
00:02:10,759 --> 00:02:14,740
qui lui est associée, comme indiqué par l'
absence du visage souriant dans la

42
00:02:14,740 --> 00:02:16,110
partie de données.

43
00:02:16,110 --> 00:02:19,910
Les flèches s'étendant à partir des parties d'
les enfants représentent matrice non-noeud

44
00:02:19,910 --> 00:02:21,640
des pointeurs vers d'autres noeuds.

45
00:02:21,640 --> 00:02:25,500
Par exemple, la flèche s'étendant à partir de
le deuxième élément d'enfants

46
00:02:25,500 --> 00:02:28,400
représente la lettre B
dans un dictionnaire clé.

47
00:02:28,400 --> 00:02:31,920
Et dans le diagramme plus grande
nous marquer avec un B.

48
00:02:31,920 --> 00:02:35,810
>> On notera que dans le diagramme plus grande, lorsque nous
tirer un pointeur vers un autre nœud, il

49
00:02:35,810 --> 00:02:39,100
n'a pas d'importance où la flèche
répond l'autre nœud.

50
00:02:39,100 --> 00:02:43,850
Notre échantillon dictionnaire trie contient
deux mots, que et zoom.

51
00:02:43,850 --> 00:02:47,040
Passons en revue un exemple de
la recherche de données d'une clé.

52
00:02:47,040 --> 00:02:50,800
>> Supposons que nous voulions voir le
La valeur correspondante pour le bain clé.

53
00:02:50,800 --> 00:02:53,610
Nous allons commencer notre regard vers le haut
au niveau du noeud de racine.

54
00:02:53,610 --> 00:02:57,870
Ensuite, nous allons prendre la première lettre de notre
clé, B, et trouver le correspondant

55
00:02:57,870 --> 00:03:00,020
repérer dans notre tableau des enfants.

56
00:03:00,020 --> 00:03:04,490
Notez qu'il ya exactement 26 points
dans le tableau, une pour chaque lettre de

57
00:03:04,490 --> 00:03:05,330
l'alphabet.

58
00:03:05,330 --> 00:03:08,800
Et nous aurons les points représentent la
lettres de l'alphabet dans l'ordre.

59
00:03:08,800 --> 00:03:13,960
>> Nous allons examiner le second indice alors,
une indice, par B. D'une manière générale, si l'on

60
00:03:13,960 --> 00:03:17,990
avoir un caractère alphabétique C nous
pourrait déterminer l'endroit correspondant

61
00:03:17,990 --> 00:03:21,520
dans le tableau en utilisant les enfants
un calcul de ce genre.

62
00:03:21,520 --> 00:03:25,140
Nous aurions pu utiliser un plus grand enfants
tableau si nous voulions offrir regard d'

63
00:03:25,140 --> 00:03:28,380
touches avec un large éventail de personnages,
tel que l'ensemble de

64
00:03:28,380 --> 00:03:29,880
Jeu de caractères ASCII.

65
00:03:29,880 --> 00:03:32,630
>> Dans ce cas, le pointeur
dans notre tableau les enfants à

66
00:03:32,630 --> 00:03:34,320
index-ci n'est pas nulle.

67
00:03:34,320 --> 00:03:36,600
Nous continuerons donc à la recherche
le bain de clé.

68
00:03:36,600 --> 00:03:40,130
Si jamais nous avons rencontré un pointeur null
au bon endroit chez les enfants

69
00:03:40,130 --> 00:03:43,230
tableau tandis que nous traversions les nœuds,
alors nous devons dire que nous

70
00:03:43,230 --> 00:03:45,630
ne pouvait pas trouver quelque chose pour cette clé.

71
00:03:45,630 --> 00:03:49,370
>> Maintenant, nous allons prendre la seconde lettre de
notre clé, A, et continuer à suivre

72
00:03:49,370 --> 00:03:52,400
pointeurs de cette façon jusqu'à ce que nous
arriver à la fin de notre clé.

73
00:03:52,400 --> 00:03:56,530
Si nous arrivons à la fin de la clé sans
heurter les impasses, les pointeurs NULL,

74
00:03:56,530 --> 00:03:59,730
comme c'est le cas ici, alors nous ne
avoir à vérifier une chose.

75
00:03:59,730 --> 00:04:02,110
Est-ce réellement la clé
dans le dictionnaire?

76
00:04:02,110 --> 00:04:07,660
>> Si c'est le cas, nous devrions trouver une valeur, ainsi un
smiley icône de visage dans notre schéma où

77
00:04:07,660 --> 00:04:08,750
le mot se termine.

78
00:04:08,750 --> 00:04:12,270
Si il ya quelque chose d'autre stockée avec
les données, alors nous pouvons retourner.

79
00:04:12,270 --> 00:04:16,500
Par exemple, le zoo clé n'est pas dans la
dictionnaire, même si nous aurions pu

80
00:04:16,500 --> 00:04:19,810
atteint la fin de cette touche, sans jamais
frapper un pointeur NULL, alors que nous

81
00:04:19,810 --> 00:04:21,089
parcourir la trie.

82
00:04:21,089 --> 00:04:25,436
>> Si nous avons essayé de voir la salle de bain clé, la
deuxième à l'indice de tableau de dernier nœud,

83
00:04:25,436 --> 00:04:28,750
correspondant à la lettre H, serait
ont tenu un pointeur NULL.

84
00:04:28,750 --> 00:04:31,120
Ainsi, le bain n'est pas dans le dictionnaire.

85
00:04:31,120 --> 00:04:34,800
Et si un trie est unique en ce que les touches
ne sont jamais explicitement stockés dans

86
00:04:34,800 --> 00:04:36,650
la structure de données.

87
00:04:36,650 --> 00:04:38,810
Alors, comment pouvons-nous insérer quelque chose
dans un trie?

88
00:04:38,810 --> 00:04:41,780
>> Insérons la touche
zoo dans notre trie.

89
00:04:41,780 --> 00:04:46,120
Rappelez-vous que un visage souriant à un noeud
pourrait correspondre dans le code à une simple

90
00:04:46,120 --> 00:04:50,170
Valeur booléenne pour indiquer que zoo
est dans le dictionnaire ou il pourrait

91
00:04:50,170 --> 00:04:53,710
correspondent à plus d'informations que nous
souhaitez associer à la touche zoo,

92
00:04:53,710 --> 00:04:56,860
comme la définition de l'
mot ou quelque chose d'autre.

93
00:04:56,860 --> 00:05:00,350
À certains égards, le processus pour insérer
quelque chose dans un trie est similaire à

94
00:05:00,350 --> 00:05:02,060
regardant quelque chose dans un trie.

95
00:05:02,060 --> 00:05:05,720
>> Nous allons commencer avec le nœud racine de nouveau,
pointeurs suivants correspondant à

96
00:05:05,720 --> 00:05:07,990
les lettres de notre clé.

97
00:05:07,990 --> 00:05:11,310
Heureusement, nous avons pu suivre les pointeurs
tout le chemin jusqu'à ce que nous ayons atteint

98
00:05:11,310 --> 00:05:12,770
l'extrémité de la clé.

99
00:05:12,770 --> 00:05:16,480
Depuis zoo est un préfixe du mot
zoom, qui est un membre de l'

100
00:05:16,480 --> 00:05:19,440
dictionnaire, nous n'avons pas besoin de
allouer de nouveaux nœuds.

101
00:05:19,440 --> 00:05:23,140
>> Nous pouvons modifier le nœud pour indiquer que
le chemin de personnages principaux à

102
00:05:23,140 --> 00:05:25,360
il représente un élément clé dans notre dictionnaire.

103
00:05:25,360 --> 00:05:28,630
Maintenant, nous allons essayer d'insérer le
BAIN clé dans la structure arborescente.

104
00:05:28,630 --> 00:05:32,260
Nous allons commencer à le nœud racine
et suivre à nouveau les pointeurs.

105
00:05:32,260 --> 00:05:35,620
Mais dans cette situation, nous avons touché un mort
fin avant que nous soyons en mesure d'obtenir à l'

106
00:05:35,620 --> 00:05:36,940
extrémité de la clé.

107
00:05:36,940 --> 00:05:40,980
Maintenant, nous avons besoin d'allouer une nouvelle
nœuds devront allouer un nouveau

108
00:05:40,980 --> 00:05:43,660
pour chaque nœud restant
lettre de notre clé.

109
00:05:43,660 --> 00:05:46,740
>> Dans ce cas, nous avons juste besoin
d'allouer un nouveau nœud.

110
00:05:46,740 --> 00:05:50,590
Ensuite, nous devons faire l'indice de H
référence à ce nouveau nœud.

111
00:05:50,590 --> 00:05:54,070
Une fois de plus, nous pouvons modifier le nœud de
indiquer que la trajectoire de caractères

112
00:05:54,070 --> 00:05:57,120
menant à elle représente un
clé dans notre dictionnaire.

113
00:05:57,120 --> 00:06:00,730
Disons raisonner sur l'asymptotique
complexité de nos procédures pour les

114
00:06:00,730 --> 00:06:02,110
deux opérations.

115
00:06:02,110 --> 00:06:06,420
>> Nous remarquons que dans les deux cas, le nombre
des étapes de notre algorithme a pris a été

116
00:06:06,420 --> 00:06:09,470
proportionnel au nombre de
lettres dans le mot-clé.

117
00:06:09,470 --> 00:06:10,220
C'est vrai.

118
00:06:10,220 --> 00:06:13,470
Si vous souhaitez rechercher un mot dans un
trie vous suffit pour parcourir

119
00:06:13,470 --> 00:06:17,100
les lettres une par une jusqu'à ce que vous
arriver à la fin du mot ou

120
00:06:17,100 --> 00:06:19,060
dans une impasse dans le trie.

121
00:06:19,060 --> 00:06:22,470
>> Et lorsque vous souhaitez insérer une clé
valeur paire dans un trie à l'aide du

122
00:06:22,470 --> 00:06:26,250
procédure, nous avons discuté, le pire des cas
vous fera l'attribution d'un nouveau noeud

123
00:06:26,250 --> 00:06:27,550
pour chaque lettre.

124
00:06:27,550 --> 00:06:31,290
Et nous supposons que la répartition
est une constante de temps de fonctionnement.

125
00:06:31,290 --> 00:06:35,850
Donc, si nous supposons que la longueur de la clé est
délimitée par une constante fixe, à la fois

126
00:06:35,850 --> 00:06:39,400
insertion et voir sont constants
opérations de temps pour un trie.

127
00:06:39,400 --> 00:06:42,930
>> Si nous ne faisons pas cette hypothèse que
la longueur de la clé est délimitée par une partie fixe

128
00:06:42,930 --> 00:06:46,650
constante, insertion et regarder en haut,
dans le pire des cas, sont linéaires dans la

129
00:06:46,650 --> 00:06:48,240
longueur de la clé.

130
00:06:48,240 --> 00:06:51,800
Notez que le nombre d'éléments stockés
dans le trie ne pas affecter l'apparence des

131
00:06:51,800 --> 00:06:52,820
ou le temps d'insertion.

132
00:06:52,820 --> 00:06:55,360
Il est seulement affecté par la
longueur de la clé.

133
00:06:55,360 --> 00:06:59,300
>> En revanche, l'ajout d'entrées à, disons,
une table de hachage tend à faire

134
00:06:59,300 --> 00:07:01,250
perspectives d'avenir plus lentement.

135
00:07:01,250 --> 00:07:04,520
Même si cela peut paraître séduisante au premier abord,
nous devrions garder à l'esprit que

136
00:07:04,520 --> 00:07:08,740
complexité asymptotique favorable ne
dire que dans la pratique les données

137
00:07:08,740 --> 00:07:11,410
structure est nécessairement
au-delà de tout reproche.

138
00:07:11,410 --> 00:07:15,860
Nous devons aussi considérer que pour stocker une
mot dans un trie, nous devons, dans le pire des

139
00:07:15,860 --> 00:07:19,700
cas, un certain nombre de noeuds proportionnel
à la longueur du mot lui-même.

140
00:07:19,700 --> 00:07:21,880
>> Essais ont tendance à utiliser beaucoup d'espace.

141
00:07:21,880 --> 00:07:25,620
C'est en revanche à une table de hachage,
où nous avons seulement besoin d'un nouveau nœud à

142
00:07:25,620 --> 00:07:27,940
stocker des paires de valeur de la clé.

143
00:07:27,940 --> 00:07:31,370
Maintenant, toujours en théorie, un grand espace
la consommation ne semble pas être un grand

144
00:07:31,370 --> 00:07:34,620
traiter, d'autant plus que moderne
ordinateurs ont gigaoctets et

145
00:07:34,620 --> 00:07:36,180
gigaoctets de mémoire.

146
00:07:36,180 --> 00:07:39,200
Mais il s'avère que nous avons encore
à vous soucier de l'utilisation de la mémoire et

147
00:07:39,200 --> 00:07:42,540
organisation pour le bien de
performance, puisque les ordinateurs modernes

148
00:07:42,540 --> 00:07:46,960
avoir des mécanismes en place dans le cadre du
capot pour accélérer l'accès mémoire.

149
00:07:46,960 --> 00:07:51,180
>> Mais ces mécanismes fonctionnent mieux lorsque
accès à la mémoire sont expédiées dans les compact

150
00:07:51,180 --> 00:07:52,810
régions ou zones.

151
00:07:52,810 --> 00:07:55,910
Et les noeuds d'un trie pourraient résider
n'importe où dans ce tas.

152
00:07:55,910 --> 00:07:58,390
Mais ce sont des compromis
que nous devons considérer.

153
00:07:58,390 --> 00:08:01,440
>> Rappelez-vous que, lorsque vous choisissez une des données
la structure pour une certaine tâche, nous

154
00:08:01,440 --> 00:08:04,420
devraient penser à ce genre de
opérations de la structure de données doit

155
00:08:04,420 --> 00:08:07,140
support et quel rendement
de chacun de ces

156
00:08:07,140 --> 00:08:09,080
opérations des questions à nous.

157
00:08:09,080 --> 00:08:11,300
Ces opérations peuvent même
étendre au-delà de

158
00:08:11,300 --> 00:08:13,430
base regard et l'insertion.

159
00:08:13,430 --> 00:08:17,010
Supposons que nous voulions mettre en place une sorte
de la fonctionnalité de saisie semi-automatique, beaucoup

160
00:08:17,010 --> 00:08:18,890
comme moteur de recherche Google ne.

161
00:08:18,890 --> 00:08:22,210
C'est, retournez toutes les clés et
potentiellement valeurs qui

162
00:08:22,210 --> 00:08:24,130
avoir un préfixe donné.

163
00:08:24,130 --> 00:08:27,050
>> Un trie est particulièrement utile
pour cette opération.

164
00:08:27,050 --> 00:08:29,890
C'est simple pour parcourir
le trie pour chaque caractère de

165
00:08:29,890 --> 00:08:30,950
le préfixe.

166
00:08:30,950 --> 00:08:33,559
Tout comme une opération rechercher,
nous pourrions suivre des pointeurs

167
00:08:33,559 --> 00:08:35,400
caractère par caractère.

168
00:08:35,400 --> 00:08:38,659
Puis, quand nous arrivons à la fin de la
préfixe, nous pourrions parcourir la

169
00:08:38,659 --> 00:08:42,049
la partie restante de la structure de données
étant donné que l'une des touches au-delà de

170
00:08:42,049 --> 00:08:43,980
ce point ont le préfixe.

171
00:08:43,980 --> 00:08:47,670
>> Il est également facile d'obtenir cette annonce
dans l'ordre alphabétique depuis le

172
00:08:47,670 --> 00:08:50,970
éléments de la matrice pour enfants
sont classées par ordre alphabétique.

173
00:08:50,970 --> 00:08:54,420
Donc, j'espère que vous envisagerez
dons tente un essai.

174
00:08:54,420 --> 00:08:56,085
Je suis Kevin Schmid, et c'est CS50.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> Ah, c'est le début
de la baisse.

177
00:09:00,790 --> 00:09:01,350
Je suis désolé.

178
00:09:01,350 --> 00:09:01,870
Désolé.

179
00:09:01,870 --> 00:09:02,480
Désolé.

180
00:09:02,480 --> 00:09:03,130
Désolé.

181
00:09:03,130 --> 00:09:03,950
>> Frappez quatre.

182
00:09:03,950 --> 00:09:04,360
Je suis sorti.

183
00:09:04,360 --> 00:09:05,280
Désolé.

184
00:09:05,280 --> 00:09:06,500
Désolé.

185
00:09:06,500 --> 00:09:07,490
Désolé.

186
00:09:07,490 --> 00:09:12,352
Désolé pour la fabrication de la personne qui
doit modifier ce fou.

187
00:09:12,352 --> 00:09:13,280
>> Désolé.

188
00:09:13,280 --> 00:09:13,880
Désolé.

189
00:09:13,880 --> 00:09:15,080
Désolé.

190
00:09:15,080 --> 00:09:15,680
Désolé.

191
00:09:15,680 --> 00:09:16,280
>> INTERLOCUTEUR 1: Bravo.

192
00:09:16,280 --> 00:09:17,530
Cela a été très bien fait.

193
00:09:17,530 --> 00:09:18,430