1
00:00:00,000 --> 00:00:02,832
>> [Jouer de la musique]

2
00:00:02,832 --> 00:00:05,670

3
00:00:05,670 --> 00:00:08,560
>> DOUG LLOYD: OK, donc au
ce point dans le cours,

4
00:00:08,560 --> 00:00:15,300
nous avons couvert un grand nombre de bases de C.
Nous savons beaucoup de choses sur les variables, les tableaux,

5
00:00:15,300 --> 00:00:17,610
pointeurs, toutes ces bonnes choses.

6
00:00:17,610 --> 00:00:21,610
Ceux-ci sont toutes sortes de bâti
pour voir que les fondamentaux,

7
00:00:21,610 --> 00:00:23,880
mais nous pouvons faire plus, non?

8
00:00:23,880 --> 00:00:27,930
Nous pouvons combiner les choses
ensemble de manière intéressante.

9
00:00:27,930 --> 00:00:31,010
>> Et nous allons donc le faire, nous allons commencer
à se ramifier de ce qui C nous donne,

10
00:00:31,010 --> 00:00:35,270
et commencer à créer nos propres données
structures utilisant ces bâtiments

11
00:00:35,270 --> 00:00:40,590
blocs ensemble pour faire quelque chose
vraiment précieuse, utile.

12
00:00:40,590 --> 00:00:43,420
Une façon nous pouvons faire est
pour parler de collections.

13
00:00:43,420 --> 00:00:48,360
Donc, jusqu'à présent, nous avons eu un type de données
Structure pour représenter collections

14
00:00:48,360 --> 00:00:51,030
d'aimer valeurs, des valeurs similaires.

15
00:00:51,030 --> 00:00:52,350
Ce serait un tableau.

16
00:00:52,350 --> 00:00:57,020
Nous avons collections d'entiers, ou
collections de caractères et ainsi de suite.

17
00:00:57,020 --> 00:01:00,890
>> Structures sont également une sorte de données
la structure de collecte d'informations,

18
00:01:00,890 --> 00:01:03,220
mais pas pour la collecte comme valeurs.

19
00:01:03,220 --> 00:01:08,090
Il mêle généralement différents types de données
ensemble à l'intérieur d'une seule boîte.

20
00:01:08,090 --> 00:01:10,750
Mais il ne se
utilisé pour enchaîner

21
00:01:10,750 --> 00:01:16,920
ou connecter ensemble similaire
articles, comme un tableau.

22
00:01:16,920 --> 00:01:20,960
Les tableaux sont grands pour
élément regarder, mais le rappel

23
00:01:20,960 --> 00:01:24,262
qu'il est très difficile
à insérer dans un tableau,

24
00:01:24,262 --> 00:01:26,470
à moins que nous insérer au
la fin de ce tableau.

25
00:01:26,470 --> 00:01:29,730
>> Et le meilleur exemple que je possède
pour ce qui est le tri par insertion.

26
00:01:29,730 --> 00:01:31,650
Si vous vous rappelez notre vidéo
le tri par insertion,

27
00:01:31,650 --> 00:01:34,110
il y avait beaucoup de
frais engagés pour avoir

28
00:01:34,110 --> 00:01:37,970
pour ramasser des éléments, et de les transférer
sur la façon de tenir quelque chose

29
00:01:37,970 --> 00:01:41,290
dans le milieu de votre tableau.

30
00:01:41,290 --> 00:01:44,690
Tableaux souffrent également d'un autre
problème, qui est l'inflexibilité.

31
00:01:44,690 --> 00:01:47,150
Lorsque nous déclarons un tableau,
nous obtenons un coup à elle.

32
00:01:47,150 --> 00:01:49,790
Nous apprenons à dire, je veux
ce nombre d'éléments.

33
00:01:49,790 --> 00:01:51,940
Peut-être 100, il pourrait
être de 1000, il pourrait

34
00:01:51,940 --> 00:01:55,930
x où x est un nombre qui est l'utilisateur
nous a donné à une invite ou à la commande

35
00:01:55,930 --> 00:01:56,630
ligne.

36
00:01:56,630 --> 00:01:59,905
>> Mais nous obtenons un seul projectile à lui, nous
ne reçois pas de dire alors Oh, en fait je

37
00:01:59,905 --> 00:02:04,360
101 nécessaire, ou je devais x plus 20.

38
00:02:04,360 --> 00:02:07,910
Trop tard, nous avons déjà déclaré la
tableau, et si nous voulons obtenir 101 ou x

39
00:02:07,910 --> 00:02:12,050
plus 20, nous avons à déclarer
un tableau tout à fait différent,

40
00:02:12,050 --> 00:02:15,540
copier tous les éléments de la matrice
plus, et ensuite nous en avons assez.

41
00:02:15,540 --> 00:02:19,880
Et si nous sommes à nouveau mal, ce qui
si nous avons réellement besoin 102, ou 40 x plus,

42
00:02:19,880 --> 00:02:21,970
nous devons le faire à nouveau.

43
00:02:21,970 --> 00:02:26,250
Donc ils sont très inflexible
pour redimensionner nos données,

44
00:02:26,250 --> 00:02:29,360
mais si nous combinons réuni certains
des bases que nous avons déjà

45
00:02:29,360 --> 00:02:33,230
appris sur les pointeurs et les structures,
en particulier en utilisant la mémoire dynamique

46
00:02:33,230 --> 00:02:36,180
répartition avec malloc, nous
peut mettre ces pièces ensemble

47
00:02:36,180 --> 00:02:40,960
pour créer une de nouvelles données
isolément liste nous pourrions say-- liée

48
00:02:40,960 --> 00:02:45,400
qui nous permet de grandir et de
réduire une collection de valeurs

49
00:02:45,400 --> 00:02:48,800
et nous ne serons pas avoir d'espace perdu.

50
00:02:48,800 --> 00:02:53,320
>> Encore une fois, nous appelons cette idée,
cette notion, une liste chaînée.

51
00:02:53,320 --> 00:02:56,320
En particulier, dans cette vidéo, nous sommes
parler de la liste chaînée,

52
00:02:56,320 --> 00:02:59,185
puis une autre vidéo nous allons parler
listes propos doublement chaînées, qui

53
00:02:59,185 --> 00:03:01,560
est juste une variation sur un thème ici.

54
00:03:01,560 --> 00:03:05,200
Mais une liste chaînée
est constitué de noeuds,

55
00:03:05,200 --> 00:03:08,559
nœuds juste être un term-- abstraite
il est juste quelque chose que je vais appeler

56
00:03:08,559 --> 00:03:10,350
qui est une sorte de
la structure, au fond, je suis?

57
00:03:10,350 --> 00:03:16,190
Tout va appeler cela un node-- et cela
noeud a deux membres, ou deux domaines.

58
00:03:16,190 --> 00:03:20,300
Il dispose de données, généralement un
entier, un flotteur de caractère,

59
00:03:20,300 --> 00:03:23,790
ou peut être un autre type de données
que vous avez défini avec un def type.

60
00:03:23,790 --> 00:03:29,290
Et il contient un pointeur vers
un autre noeud du même type.

61
00:03:29,290 --> 00:03:34,710
>> Nous avons donc deux choses à l'intérieur de
ce nœud, les données et un pointeur

62
00:03:34,710 --> 00:03:36,380
à un autre noeud.

63
00:03:36,380 --> 00:03:39,370
Et si vous commencez à visualiser
cela, vous pouvez penser

64
00:03:39,370 --> 00:03:42,280
comme une chaîne de nœuds
sont reliés entre eux.

65
00:03:42,280 --> 00:03:45,070
Nous avons le premier noeud, il
contient des données, et un pointeur

66
00:03:45,070 --> 00:03:49,110
au second noeud, qui contient
données, et un pointeur vers le troisième noeud.

67
00:03:49,110 --> 00:03:52,940
Et voilà pourquoi nous l'appelons un
liste chaînée, ils sont reliés entre eux.

68
00:03:52,940 --> 00:03:56,070
>> Qu'est-ce que cette spéciale
structure de noeud ressembler?

69
00:03:56,070 --> 00:04:01,120
Eh bien, si vous vous souvenez de notre vidéo sur
la définition des types personnalisés, avec le type def,

70
00:04:01,120 --> 00:04:05,400
nous pouvons définir une structure-- et
tapez définir une structure de ce type.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, et puis je suis
en utilisant la valeur de mot ici arbitrairement

72
00:04:11,240 --> 00:04:13,891
pour indiquer quel type de données vraiment.

73
00:04:13,891 --> 00:04:16,890
Vous pourriez passer un nombre entier ou un flotteur,
vous pourriez avoir ce que vous voulez.

74
00:04:16,890 --> 00:04:19,389
Ça ne se limite pas à un peu
entiers, ou quelque chose comme ça.

75
00:04:19,389 --> 00:04:22,790
Donc, la valeur est juste un arbitraire
Type de données et puis un pointeur

76
00:04:22,790 --> 00:04:26,310
à un autre noeud du même type.

77
00:04:26,310 --> 00:04:29,690
>> Maintenant, il ya un peu de captures
ici avec une structure définissant

78
00:04:29,690 --> 00:04:33,030
quand il est une structure auto-référentielle.

79
00:04:33,030 --> 00:04:35,340
Je dois avoir un temporaire
nom pour ma structure.

80
00:04:35,340 --> 00:04:37,640
A la fin de la journée, je
veulent clairement appeler

81
00:04:37,640 --> 00:04:43,030
noeud SLL, qui est en fin de compte la nouvelle
nommer une partie de ma définition de type,

82
00:04:43,030 --> 00:04:47,450
mais je ne peux pas utiliser le noeud de SLL
au milieu de ce produit.

83
00:04:47,450 --> 00:04:51,430
La raison étant, je ne ai pas
créé un noeud de SLL de type appelé

84
00:04:51,430 --> 00:04:55,200
jusqu'à ce que je frappe ce dernier point ici.

85
00:04:55,200 --> 00:04:59,720
Jusqu'à ce point, je dois avoir
un autre moyen de se référer à ce type de données.

86
00:04:59,720 --> 00:05:02,440
>> Et cela est une auto
référentielle type de données.

87
00:05:02,440 --> 00:05:06,314
Il; s un type de données
une structure qui contient des données,

88
00:05:06,314 --> 00:05:08,480
et un pointeur vers un autre
structure du même type.

89
00:05:08,480 --> 00:05:11,750
Donc, je dois être en mesure de se référer à
ce type de données au moins temporairement,

90
00:05:11,750 --> 00:05:14,910
de sorte qu'il donne un temporaire
nom de struct sllist

91
00:05:14,910 --> 00:05:18,540
me permet de dire alors je veux un
pointeur vers une autre structure sllist,

92
00:05:18,540 --> 00:05:24,690
une étoile struct sllist, puis
après que je l'ai terminé la définition,

93
00:05:24,690 --> 00:05:27,220
Je peux maintenant appeler ce type d'un noeud de SLL.

94
00:05:27,220 --> 00:05:30,520
>> Voilà pourquoi vous voyez il ya
un nom temporaire ici,

95
00:05:30,520 --> 00:05:31,879
mais un nom permanent ici.

96
00:05:31,879 --> 00:05:33,920
Parfois, vous pourriez voir
les définitions de structure,

97
00:05:33,920 --> 00:05:36,570
par exemple, qui ne sont pas
autoréférentiel, que

98
00:05:36,570 --> 00:05:39,390
ne pas avoir un nom de spécificateur ici.

99
00:05:39,390 --> 00:05:43,040
Il serait tout simplement dire typedef struct,
ouvrir accolade, puis le définir.

100
00:05:43,040 --> 00:05:45,620
Mais si vous êtes struct est auto
référentielle, que celui-ci est,

101
00:05:45,620 --> 00:05:49,010
vous devez spécifier un
nom de type temporaire.

102
00:05:49,010 --> 00:05:51,310
Mais finalement, maintenant
que nous avons fait cela,

103
00:05:51,310 --> 00:05:53,620
nous pouvons tout simplement se référer à
ces nœuds, ces unités,

104
00:05:53,620 --> 00:05:57,900
en tant que noeuds à des fins SLL
du reste de cette vidéo.

105
00:05:57,900 --> 00:06:00,900
>> Très bien, alors nous savons comment
créer un nœud de liste chaînée.

106
00:06:00,900 --> 00:06:03,240
Nous savons comment définir
un nœud de liste chaînée.

107
00:06:03,240 --> 00:06:06,670
Maintenant, si nous allons commencer
les utiliser pour recueillir des informations,

108
00:06:06,670 --> 00:06:10,360
il ya un couple d'opérations nous
besoin de comprendre et de travailler avec.

109
00:06:10,360 --> 00:06:12,860
Nous devons savoir comment créer
une liste liée de l'air mince.

110
00:06:12,860 --> 00:06:14,901
Si il n'y a pas de liste déjà,
nous voulons commencer un.

111
00:06:14,901 --> 00:06:16,960
Donc, nous devons être en mesure
pour créer une liste chaînée,

112
00:06:16,960 --> 00:06:19,130
nous devons rechercher sans doute
à travers la liste de liens

113
00:06:19,130 --> 00:06:21,830
pour trouver un élément que nous recherchons.

114
00:06:21,830 --> 00:06:24,430
Nous devons être en mesure d'insérer
de nouvelles choses dans la liste,

115
00:06:24,430 --> 00:06:25,930
nous voulons que notre liste pour être en mesure de croître.

116
00:06:25,930 --> 00:06:28,638
Et de même, nous voulons être en mesure
de supprimer les choses de notre liste,

117
00:06:28,638 --> 00:06:30,250
nous voulons que notre liste pour être en mesure de se rétrécir.

118
00:06:30,250 --> 00:06:32,160
Et à la fin de notre
des programmes, en particulier

119
00:06:32,160 --> 00:06:34,550
si vous vous rappelez que nous sommes
allocation dynamique de mémoire

120
00:06:34,550 --> 00:06:38,337
pour construire ces listes généralement,
nous voulons libérer tous que la mémoire

121
00:06:38,337 --> 00:06:39,670
quand nous aurons fini de travailler avec elle.

122
00:06:39,670 --> 00:06:44,627
Et donc nous devons être en mesure de supprimer une
toute liste liée à un échec coup.

123
00:06:44,627 --> 00:06:46,460
Donc, nous allons passer par
certaines de ces opérations

124
00:06:46,460 --> 00:06:51,192
et comment nous pourrions les visualiser,
parler en code pseudo spécifiquement.

125
00:06:51,192 --> 00:06:53,150
Donc, nous voulons créer un
liste chaînée, alors peut-être nous

126
00:06:53,150 --> 00:06:56,480
vouloir définir une fonction
avec ce prototype.

127
00:06:56,480 --> 00:07:01,690
SLL noeud étoiles, créer, et je suis de passage
dans un argument, certaines données arbitraires

128
00:07:01,690 --> 00:07:05,530
tapez à nouveau, d'un certain type de données arbitraires.

129
00:07:05,530 --> 00:07:10,482
Mais je dois returning-- cette fonction
revenez me voir un pointeur, à un seul

130
00:07:10,482 --> 00:07:11,190
nœud de liste chaînée.

131
00:07:11,190 --> 00:07:14,050
Encore une fois, nous essayons de créer
une liste liée de l'air mince,

132
00:07:14,050 --> 00:07:17,900
donc je besoin d'un pointeur vers
cette liste quand je suis fait.

133
00:07:17,900 --> 00:07:19,420
>> Alors, quelles sont les étapes à suivre ici?

134
00:07:19,420 --> 00:07:20,960
Eh bien, la première chose que je suis
va faire est dynamiquement

135
00:07:20,960 --> 00:07:22,550
allouer de l'espace pour un nouveau noeud.

136
00:07:22,550 --> 00:07:26,689
Encore une fois, nous créons hors de minces
l'air, nous avons donc besoin d'espace de malloc pour elle.

137
00:07:26,689 --> 00:07:28,480
Et bien sûr, immédiatement
après que nous malloc,

138
00:07:28,480 --> 00:07:31,692
nous vérifions toujours de faire en sorte que notre
pointer-- on n'a pas eu de retour nul.

139
00:07:31,692 --> 00:07:33,650
Parce que si nous essayons de
déférence un pointeur NULL,

140
00:07:33,650 --> 00:07:36,190
nous allons souffrir d'une
Segfault et nous ne voulons pas que.

141
00:07:36,190 --> 00:07:39,510
>> Ensuite, nous voulons remplir dans le domaine,
nous voulons initialiser le champ de valeur

142
00:07:39,510 --> 00:07:41,690
et initialiser le champ suivant.

143
00:07:41,690 --> 00:07:45,450
Et puis nous voulons to-- finalement que le
prototype de fonction indicates-- nous voulons

144
00:07:45,450 --> 00:07:49,940
pour retourner un pointeur vers un noeud de SLL.

145
00:07:49,940 --> 00:07:51,710
Alors, que faire cela ressemble visuellement?

146
00:07:51,710 --> 00:07:55,230
Eh bien, d'abord, nous allons dynamiquement
allouer de l'espace pour un nouveau nœud de SLL,

147
00:07:55,230 --> 00:07:58,320
donc nous voilà malloc--
une représentation visuelle

148
00:07:58,320 --> 00:08:00,020
du nœud nous venons de créer.

149
00:08:00,020 --> 00:08:02,757
Et nous vérifions pour vous assurer
ça ne null-- dans ce cas,

150
00:08:02,757 --> 00:08:04,840
l'image ne serait pas
montré jusqu'à si elle était nulle,

151
00:08:04,840 --> 00:08:07,298
nous aurions à court de mémoire,
Nous sommes donc bien d'y aller.

152
00:08:07,298 --> 00:08:10,200
Alors maintenant, nous sommes à l'étape C,
initialiser le champ de valeur nœuds.

153
00:08:10,200 --> 00:08:12,280
Eh bien, sur la base de cette fonction
Je l'appelle à l'aide ici,

154
00:08:12,280 --> 00:08:16,700
on dirait que je veux passer à 6,
Alors je vais 6 dans le champ de valeur.

155
00:08:16,700 --> 00:08:18,865
Maintenant, initialiser le champ suivant.

156
00:08:18,865 --> 00:08:21,640
Eh bien, que vais-je faire là-bas,
il n'y a rien à côté, à droite,

157
00:08:21,640 --> 00:08:23,600
ceci est la seule chose dans la liste.

158
00:08:23,600 --> 00:08:27,206
Alors, quelle est la prochaine chose dans la liste?

159
00:08:27,206 --> 00:08:29,660
>> Il ne devrait pas pointer vers quelque chose, droite.

160
00:08:29,660 --> 00:08:33,600
Il n'y a rien d'autre, si ce qui est
le concept que nous savons de qui est nothing--

161
00:08:33,600 --> 00:08:35,638
pointeurs à rien?

162
00:08:35,638 --> 00:08:37,929
Il devrait être peut-être que nous voulons
de mettre un pointeur nul là-bas,

163
00:08:37,929 --> 00:08:40,178
et je représente la null
pointeur comme juste une boîte rouge,

164
00:08:40,178 --> 00:08:41,559
nous ne pouvons pas aller plus loin.

165
00:08:41,559 --> 00:08:44,430
Comme nous le verrons un peu plus tard,
nous aurons éventuellement des chaînes

166
00:08:44,430 --> 00:08:46,330
des flèches de liaison
ces noeuds ensemble,

167
00:08:46,330 --> 00:08:48,480
mais quand vous frappez la
boîte rouge, qui est nulle,

168
00:08:48,480 --> 00:08:51,150
nous ne pouvons pas aller plus loin,
qui est la fin de la liste.

169
00:08:51,150 --> 00:08:53,960
>> Et enfin, nous voulons juste
retourner un pointeur vers ce nœud.

170
00:08:53,960 --> 00:08:56,160
Donc, nous allons appelons nouvelle,
et sera de retour nouvelle

171
00:08:56,160 --> 00:08:59,370
de sorte qu'il peut être utilisé dans
quelle que soit la fonction créée.

172
00:08:59,370 --> 00:09:03,100
Donc là, nous allons, nous avons créé un seul
nœud de liste liée de l'air mince,

173
00:09:03,100 --> 00:09:05,920
et maintenant nous avons une liste nous pouvons travailler avec.

174
00:09:05,920 --> 00:09:08,260
>> Maintenant, disons que nous avons déjà
avoir une grande chaîne,

175
00:09:08,260 --> 00:09:09,800
et nous voulons trouver quelque chose en elle.

176
00:09:09,800 --> 00:09:12,716
Et nous voulons une fonction qui va
retourner true ou false, selon

177
00:09:12,716 --> 00:09:15,840
si une valeur existe dans cette liste.

178
00:09:15,840 --> 00:09:18,160
Un prototype de fonction, ou
déclaration pour cette fonction,

179
00:09:18,160 --> 00:09:23,320
pourrait ressembler this-- Bool trouver, et
alors nous voulons transmettre dans deux arguments.

180
00:09:23,320 --> 00:09:26,996
>> Le premier est un pointeur sur la
le premier élément de la liste chaînée.

181
00:09:26,996 --> 00:09:29,620
Ceci est en fait quelque chose que vous
toujours envie de garder une trace de,

182
00:09:29,620 --> 00:09:33,110
et effectivement peut-être quelque chose qui
même de mettre dans une variable globale.

183
00:09:33,110 --> 00:09:35,360
Une fois que vous créez une liste,
vous toujours, toujours

184
00:09:35,360 --> 00:09:38,990
voulez garder une trace de la très
premier élément de la liste.

185
00:09:38,990 --> 00:09:43,690
De cette façon, vous pouvez vous référer à tous les autres
éléments en suivant simplement la chaîne,

186
00:09:43,690 --> 00:09:47,300
sans avoir à garder pointeurs
intacte pour chaque élément.

187
00:09:47,300 --> 00:09:50,920
Vous avez seulement besoin de garder une trace de la première
un si ils sont tous enchaînés.

188
00:09:50,920 --> 00:09:52,460
>> Et puis la deuxième chose
nous passons à nouveau

189
00:09:52,460 --> 00:09:54,376
est some-- arbitrairement
quel que soit le type de données que nous sommes

190
00:09:54,376 --> 00:09:59,640
la recherche car il est à l'intérieur de
Heureusement, un des nœuds de la liste.

191
00:09:59,640 --> 00:10:00,980
Alors, quelles sont les étapes?

192
00:10:00,980 --> 00:10:04,250
Eh bien, la première chose que nous faisons est
nous créons un pointeur transversal

193
00:10:04,250 --> 00:10:06,015
pointant à la tête des listes.

194
00:10:06,015 --> 00:10:08,890
Eh bien, pourquoi le faisons-nous, nous avons déjà
avoir un pointeur à la tête des listes,

195
00:10:08,890 --> 00:10:10,974
pourquoi ne nous contentons pas de déplacer que personne autour?

196
00:10:10,974 --> 00:10:13,140
Eh bien, comme je viens de le dire,
il est vraiment important pour nous

197
00:10:13,140 --> 00:10:17,580
de toujours garder la trace de la
très premier élément dans la liste.

198
00:10:17,580 --> 00:10:21,270
Et il est donc fait mieux
pour créer un double de ce que,

199
00:10:21,270 --> 00:10:25,350
et l'utiliser pour se déplacer de sorte que nous ne
déplacer accidentellement loin, ou nous avons toujours

200
00:10:25,350 --> 00:10:30,430
avoir un pointeur à un point qui est
à droite sur le premier élément de la liste.

201
00:10:30,430 --> 00:10:33,290
Donc, il est préférable de créer un
seconde que nous utilisons pour se déplacer.

202
00:10:33,290 --> 00:10:35,877
>> Puis nous comparons simplement si
le champ de valeur à ce noeud

203
00:10:35,877 --> 00:10:38,960
est ce que nous recherchons, et si elle est
pas, nous passons juste pour le noeud suivant.

204
00:10:38,960 --> 00:10:41,040
Et nous continuons à faire ce que
Encore et encore et encore,

205
00:10:41,040 --> 00:10:44,811
jusqu'à ce que nous trouvons
l'élément, ou nous avons touché

206
00:10:44,811 --> 00:10:47,310
null-- nous avons atteint la fin
de la liste et il n'y est pas.

207
00:10:47,310 --> 00:10:50,540
Cela devrait nous l'espérons sonner une cloche
à vous comme simplement la recherche linéaire,

208
00:10:50,540 --> 00:10:54,430
nous ne faisons que reproduire dans
une structure de liste chaînée

209
00:10:54,430 --> 00:10:56,280
au lieu d'utiliser un tableau pour le faire.

210
00:10:56,280 --> 00:10:58,210
>> Alors, voici un exemple de
une liste chaînée.

211
00:10:58,210 --> 00:11:00,043
Celui-ci se compose de
cinq nœuds, et nous avons

212
00:11:00,043 --> 00:11:04,330
un pointeur vers la tête de la
liste, qui est appelé liste.

213
00:11:04,330 --> 00:11:07,385
La première chose que nous voulons faire est
à nouveau, créer ce parcours pointeur.

214
00:11:07,385 --> 00:11:09,760
Donc, nous avons maintenant deux pointeurs
ce point à la même chose.

215
00:11:09,760 --> 00:11:15,025
>> Maintenant, remarquez ici aussi, je ne l'ai pas
avoir à malloc tout espace pour trav.

216
00:11:15,025 --> 00:11:18,970
Je ne dis pas trav égale malloc
quelque chose, ce nœud existe déjà,

217
00:11:18,970 --> 00:11:21,160
que l'espace dans la mémoire existe déjà.

218
00:11:21,160 --> 00:11:24,290
Donc, tout ce que je suis en train de faire est
création d'un autre pointeur vers elle.

219
00:11:24,290 --> 00:11:28,210
Je ne suis pas allouer de l'supplémentaires
espace, venons de deux pointeurs

220
00:11:28,210 --> 00:11:31,370
pointant vers la même chose.

221
00:11:31,370 --> 00:11:33,710
>> Donc, est-ce que 2 je cherche?

222
00:11:33,710 --> 00:11:37,220
Eh bien, non, donc je suis à la place
passer à la suivante.

223
00:11:37,220 --> 00:11:41,740
Donc, fondamentalement, je dirais,
trav trav est égal suivante.

224
00:11:41,740 --> 00:11:43,630
Est de 3 ce que je suis à la recherche, non.

225
00:11:43,630 --> 00:11:45,780
Je continue donc à aller
à travers, jusqu'à ce que finalement

226
00:11:45,780 --> 00:11:48,690
arrive à 6, qui est ce que je suis à la recherche
pour la base de l'appel de fonction

227
00:11:48,690 --> 00:11:51,600
Je dois au sommet
là, et je suis fait.

228
00:11:51,600 --> 00:11:54,150
>> Maintenant, si l'élément que je suis
cherchez est pas dans la liste,

229
00:11:54,150 --> 00:11:55,510
est ce que ça va encore travailler?

230
00:11:55,510 --> 00:11:57,120
Eh bien, vous remarquerez que la liste
ici est subtilement différent,

231
00:11:57,120 --> 00:11:59,410
et ceci est une autre chose qui est
importante avec les listes chaînées,

232
00:11:59,410 --> 00:12:01,780
vous ne disposez pas de préserver
les dans un ordre particulier.

233
00:12:01,780 --> 00:12:05,390
Vous pouvez si vous le voulez, mais
vous avez peut-être déjà remarqué

234
00:12:05,390 --> 00:12:09,310
que nous ne sommes pas garder la trace de
ce que l'élément numéro nous en sommes.

235
00:12:09,310 --> 00:12:13,150
>> Et qui est en quelque sorte d'un commerce que nous
avoir avec liste chaînée versets tableaux,

236
00:12:13,150 --> 00:12:15,300
est-ce nous ne disposons pas
accès aléatoire plus.

237
00:12:15,300 --> 00:12:18,150
Nous ne pouvons pas simplement dire que je veux
pour aller à l'élément 0,

238
00:12:18,150 --> 00:12:21,410
ou le sixième élément de ma matrice,
que je peux faire dans un tableau.

239
00:12:21,410 --> 00:12:25,080
Je ne peux pas dire que je veux aller à la
Élément 0, ou le 6ème élément,

240
00:12:25,080 --> 00:12:30,360
ou l'élément 25 de ma liste chaînée,
il n'y a aucun indice associé avec eux.

241
00:12:30,360 --> 00:12:33,660
Et donc il n'a pas vraiment d'importance
si nous préservons notre liste dans l'ordre.

242
00:12:33,660 --> 00:12:36,080
Si vous voulez vous
Certainement, mais il ya

243
00:12:36,080 --> 00:12:38,567
aucune raison pourquoi ils doivent
être conservé dans un ordre quelconque.

244
00:12:38,567 --> 00:12:40,400
Encore une fois, nous allons essayer de
trouver 6 dans cette liste.

245
00:12:40,400 --> 00:12:43,200
Eh bien, nous commençons à la
en commençant, nous ne trouvons pas 6,

246
00:12:43,200 --> 00:12:47,690
puis nous continuons à ne pas trouver
6, jusqu'à ce que nous obtenons ici.

247
00:12:47,690 --> 00:12:52,790
Donc points de droit maintenant trav au noeud
contenant 8, et six est pas là.

248
00:12:52,790 --> 00:12:55,250
>> Donc, la prochaine étape serait
pour aller à la prochaine pointeur,

249
00:12:55,250 --> 00:12:57,440
donc dire trav trav égale prochaine.

250
00:12:57,440 --> 00:13:00,750
Eh bien, trav côté, indiqué par
la boîte rouge, il est nul.

251
00:13:00,750 --> 00:13:03,020
Donc il n'y a nulle part ailleurs où
aller, et donc à ce stade

252
00:13:03,020 --> 00:13:06,120
nous pouvons conclure que nous avons atteint
la fin de la liste liée,

253
00:13:06,120 --> 00:13:07,190
et 6 est pas là.

254
00:13:07,190 --> 00:13:10,980
Et il serait renvoyé
faux dans ce cas.

255
00:13:10,980 --> 00:13:14,540
>> OK, comment pouvons-nous insérons un nouveau
noeud dans la liste chaînée?

256
00:13:14,540 --> 00:13:17,310
Donc, nous avons été en mesure de créer
une liste liée de nulle part,

257
00:13:17,310 --> 00:13:19,370
mais nous voulons probablement
construire une chaîne et non

258
00:13:19,370 --> 00:13:22,620
créer un tas de listes distinctes.

259
00:13:22,620 --> 00:13:25,700
Nous voulons avoir une seule liste qui
a un tas de noeuds en elle,

260
00:13:25,700 --> 00:13:28,040
pas un tas de listes avec un seul nœud.

261
00:13:28,040 --> 00:13:31,260
Donc, nous ne pouvons pas continuer à utiliser l'Créer
fonction, nous avons défini plus tôt, maintenant nous

262
00:13:31,260 --> 00:13:33,860
vouloir insérer dans un
liste qui existe déjà.

263
00:13:33,860 --> 00:13:36,499
>> Donc ce cas, nous allons
de passer en deux arguments,

264
00:13:36,499 --> 00:13:39,290
le pointeur à la tête de cette
liste que nous voulons ajouter à lié.

265
00:13:39,290 --> 00:13:40,910
Encore une fois, voilà pourquoi il est si
important que nous avons toujours

266
00:13:40,910 --> 00:13:43,400
garder une trace de celui-ci, parce
il est la seule façon vraiment

267
00:13:43,400 --> 00:13:46,690
se référer à l'ensemble de la liste est
simplement par un pointeur vers le premier élément.

268
00:13:46,690 --> 00:13:49,360
Donc, nous voulons transmettre dans un
pointeur vers ce premier élément,

269
00:13:49,360 --> 00:13:52,226
et quelle que soit la valeur que nous
vouloir ajouter à la liste.

270
00:13:52,226 --> 00:13:54,600
Et finalement, cette fonction
va retourner un pointeur

271
00:13:54,600 --> 00:13:57,980
à la nouvelle tête d'une liste chaînée.

272
00:13:57,980 --> 00:13:59,700
>> Quelles sont les étapes à suivre ici?

273
00:13:59,700 --> 00:14:02,249
Eh bien, tout comme avec créer,
nous avons besoin d'allouer dynamiquement

274
00:14:02,249 --> 00:14:05,540
espace pour un nouveau noeud, et assurez-
sûr que nous ne courons pas de mémoire, encore une fois,

275
00:14:05,540 --> 00:14:07,150
parce que nous sommes avec malloc.

276
00:14:07,150 --> 00:14:09,080
Ensuite, nous voulons remplir
et insérez le noeud,

277
00:14:09,080 --> 00:14:12,730
alors mettez le nombre, quel que soit
val est, dans le nœud.

278
00:14:12,730 --> 00:14:17,310
Nous voulons insérer le nœud à
le début de la liste chaînée.

279
00:14:17,310 --> 00:14:19,619
>> Il ya une raison que je
vouloir faire cela, et il

280
00:14:19,619 --> 00:14:21,910
pourrait être utile de prendre un second
pour mettre en pause la vidéo ici,

281
00:14:21,910 --> 00:14:25,860
et de réfléchir à la raison pour laquelle je voudrais
insérer au début d'une lié

282
00:14:25,860 --> 00:14:26,589
liste.

283
00:14:26,589 --> 00:14:28,630
Encore une fois, je l'ai mentionné plus tôt
qu'il n'a pas vraiment

284
00:14:28,630 --> 00:14:33,020
Peu importe si nous préservons dans toute
Afin, donc peut-être qui est un indice.

285
00:14:33,020 --> 00:14:36,040
Et vous avez vu ce qui se passerait si nous
voulu to-- ou d'une seconde

286
00:14:36,040 --> 00:14:37,360
Il ya quand nous allions
grâce à la recherche que vous

287
00:14:37,360 --> 00:14:39,235
pourraient voir ce qui pourrait
passerait-il si nous essayions

288
00:14:39,235 --> 00:14:41,330
à insérer à la fin de la liste.

289
00:14:41,330 --> 00:14:44,750
Parce que nous ne disposons pas d'un
pointeur vers la fin de la liste.

290
00:14:44,750 --> 00:14:47,490
>> Donc la raison pour laquelle je ne voudrais
à insérer au début,

291
00:14:47,490 --> 00:14:49,380
est parce que je peux le faire immédiatement.

292
00:14:49,380 --> 00:14:52,730
Je dois un pointeur au début, et
nous verrons cela dans un visuel dans une seconde.

293
00:14:52,730 --> 00:14:55,605
Mais si je veux insérer à la fin,
Je dois commencer par le commencement,

294
00:14:55,605 --> 00:14:58,760
parcourir tout le chemin à la
fin, puis virer sur.

295
00:14:58,760 --> 00:15:01,420
Donc, cela voudrait dire que
l'insertion, à la fin de la liste

296
00:15:01,420 --> 00:15:04,140
deviendrait une des n o
opération, revenir

297
00:15:04,140 --> 00:15:06,720
à notre discussion sur
complexité de calcul.

298
00:15:06,720 --> 00:15:10,140
Il était devenu un des n o opération, où
que la liste est devenu plus grand et plus gros,

299
00:15:10,140 --> 00:15:13,310
et plus grand, il va devenir de plus en
plus difficile de virer de bord quelque chose

300
00:15:13,310 --> 00:15:14,661
sur à la fin.

301
00:15:14,661 --> 00:15:17,410
Mais il est toujours très facile à
virer quelque chose sur au début,

302
00:15:17,410 --> 00:15:19,060
vous êtes toujours au début.

303
00:15:19,060 --> 00:15:21,620
>> Et nous allons voir un visuel de ce nouveau.

304
00:15:21,620 --> 00:15:24,100
Et puis une fois que nous aurons terminé, une fois
nous avons inséré le nouveau nœud,

305
00:15:24,100 --> 00:15:26,880
nous voulons revenir à notre pointeur
la nouvelle tête d'une liste chaînée, qui

306
00:15:26,880 --> 00:15:29,213
puisque nous sommes à l'insertion
en commençant, sera effectivement

307
00:15:29,213 --> 00:15:31,060
un pointeur vers le nœud nous venons de créer.

308
00:15:31,060 --> 00:15:33,280
Disons Visualiser cette,
parce que je pense que ça va aider.

309
00:15:33,280 --> 00:15:36,661
>> Alors, voici notre liste, il se compose de
quatre éléments, contenant un noeud 15,

310
00:15:36,661 --> 00:15:38,410
qui pointe vers un noeud
contenant neuf, qui

311
00:15:38,410 --> 00:15:41,370
des points à un noeud contenant 13,
qui pointe vers un noeud contenant

312
00:15:41,370 --> 00:15:44,840
10, qui a la null
pointeur comme sa prochaine pointeur

313
00:15:44,840 --> 00:15:47,010
Voilà donc la fin de la liste.

314
00:15:47,010 --> 00:15:50,200
Donc, nous voulons insérer un
nouveau noeud avec la valeur 12

315
00:15:50,200 --> 00:15:52,720
au début de cette
liste, que faisons-nous?

316
00:15:52,720 --> 00:15:58,770
Eh bien, d'abord, nous malloc espace pour le
noeud, et puis nous avons mis 12 là-dedans.

317
00:15:58,770 --> 00:16:02,211
>> Alors maintenant, nous avons atteint un
point de décision, non?

318
00:16:02,211 --> 00:16:03,960
Nous avons un couple de
pointeurs que nous pourrions

319
00:16:03,960 --> 00:16:06,770
déplacer, ce qui devrait nous faire le premier pas?

320
00:16:06,770 --> 00:16:09,250
Devrions-nous faire 12 points à
le nouveau chef de l'films--

321
00:16:09,250 --> 00:16:13,020
ou excusez-moi, devrions-nous faire 12
signaler à l'ancien chef de la liste?

322
00:16:13,020 --> 00:16:15,319
Ou devrions-nous dire que le
liste commence maintenant à 12.

323
00:16:15,319 --> 00:16:17,110
Il ya une distinction
là, et nous regarderons

324
00:16:17,110 --> 00:16:19,870
ce qui se passe à la fois en une seconde.

325
00:16:19,870 --> 00:16:23,350
>> Mais cela conduit à une
grand sujet pour la barre latérale,

326
00:16:23,350 --> 00:16:26,280
qui est celui de la
plus délicates choses avec les listes chaînées

327
00:16:26,280 --> 00:16:30,980
est d'arranger les pointeurs
dans le bon ordre.

328
00:16:30,980 --> 00:16:34,520
Si vous déplacez les choses de l'ordre,
vous pouvez vous retrouver accidentellement

329
00:16:34,520 --> 00:16:36,050
orphelins le reste de la liste.

330
00:16:36,050 --> 00:16:37,300
Et voici un exemple de cela.

331
00:16:37,300 --> 00:16:40,540
Allons donc avec l'idée de--
Eh bien, nous venons de créer 12.

332
00:16:40,540 --> 00:16:43,180
Nous savons 12 va être
le nouveau chef de la liste,

333
00:16:43,180 --> 00:16:47,660
et alors pourquoi ne nous avançons pas seulement
le pointeur de liste pour y pointer.

334
00:16:47,660 --> 00:16:49,070
>> OK, ce qui est bien.

335
00:16:49,070 --> 00:16:51,560
Alors maintenant d'où vient 12 prochain point?

336
00:16:51,560 --> 00:16:54,580
Je veux dire, nous pouvons voir visuellement
ce qu 'il pointera à 15,

337
00:16:54,580 --> 00:16:57,250
comme les humains, il est vraiment évident pour nous.

338
00:16:57,250 --> 00:17:00,300
Comment l'ordinateur sait?

339
00:17:00,300 --> 00:17:02,720
Nous ne disposons pas quoi que ce soit
pointant à 15 plus, non?

340
00:17:02,720 --> 00:17:05,869
>> Nous avons perdu toute capacité à se référer à 15.

341
00:17:05,869 --> 00:17:11,460
Nous ne pouvons pas dire nouvelle flèche à côté égaux
quelque chose, il n'y a rien là-bas.

342
00:17:11,460 --> 00:17:13,510
En fait, nous avons orphelins
le reste de la liste

343
00:17:13,510 --> 00:17:16,465
ce faisant, nous avons
accidentellement brisé la chaîne.

344
00:17:16,465 --> 00:17:18,089
Et nous ne voulons certainement pas faire cela.

345
00:17:18,089 --> 00:17:20,000
>> Donc, nous allons revenir et essayer encore une fois.

346
00:17:20,000 --> 00:17:24,060
Peut-être la bonne chose à faire
est de fixer le pointeur suivant de 12

347
00:17:24,060 --> 00:17:28,290
à l'ancien chef de la première liste,
alors nous pouvons nous déplacer sur la liste.

348
00:17:28,290 --> 00:17:30,420
Et de fait, qui est la
bon ordre que nous

349
00:17:30,420 --> 00:17:32,836
nécessité de suivre lorsque nous sommes
travailler avec la liste chaînée.

350
00:17:32,836 --> 00:17:36,460
Nous voulons toujours connecter la
nouvel élément dans la liste,

351
00:17:36,460 --> 00:17:41,010
avant de prendre ce genre de
étape importante de l'évolution

352
00:17:41,010 --> 00:17:43,360
où le chef de la liste chaînée est.

353
00:17:43,360 --> 00:17:46,740
Encore une fois, que ce soit une chose fondamentale,
nous ne voulons pas perdre la trace.

354
00:17:46,740 --> 00:17:49,310
>> Donc, nous voulons faire en sorte que
tout est enchaîné ensemble,

355
00:17:49,310 --> 00:17:52,040
avant de passer ce pointeur.

356
00:17:52,040 --> 00:17:55,300
Et alors ce serait le bon ordre,
qui est de connecter 12 à la liste,

357
00:17:55,300 --> 00:17:57,630
puis dire que la liste commence un 12.

358
00:17:57,630 --> 00:18:00,860
Si nous dit que la liste commence à 12 et
alors essayé de se connecter 12 à la liste,

359
00:18:00,860 --> 00:18:02,193
nous avons déjà vu ce qui se passe.

360
00:18:02,193 --> 00:18:04,920
Nous perdons la liste par erreur.

361
00:18:04,920 --> 00:18:06,740
>> OK, donc plus qu'une chose à parler.

362
00:18:06,740 --> 00:18:09,750
Que faire si nous voulons pour se débarrasser de
toute une liste liée à la fois?

363
00:18:09,750 --> 00:18:11,750
Encore une fois, nous allons allouer de
tout cet espace, et nous

364
00:18:11,750 --> 00:18:13,351
besoin de libérer quand nous aurons fini.

365
00:18:13,351 --> 00:18:15,350
Alors maintenant, nous voulons supprimer
toute la liste chaînée.

366
00:18:15,350 --> 00:18:16,850
Eh bien, que voulons-nous faire?

367
00:18:16,850 --> 00:18:20,460
>> Si nous avons atteint le pointeur NULL, nous
vouloir arrêter, sinon, il suffit de supprimer

368
00:18:20,460 --> 00:18:23,420
le reste de la liste, puis me libérer.

369
00:18:23,420 --> 00:18:28,890
Supprimer le reste de la liste,
puis libérer le noeud courant.

370
00:18:28,890 --> 00:18:32,850
Qu'est-ce que cela ressemble,
quelle technique avons nous avons parlé

371
00:18:32,850 --> 00:18:35,440
fait précédemment à propos de ce que cela ressemble?

372
00:18:35,440 --> 00:18:39,560
Supprimer tout le monde, puis
revenir et supprimer moi.

373
00:18:39,560 --> 00:18:42,380
>> Voilà la récursivité, nous avons fait la
problème d'un peu plus petit,

374
00:18:42,380 --> 00:18:46,910
nous disons supprimer tout le monde
d'autre, alors vous pouvez me supprimer.

375
00:18:46,910 --> 00:18:50,940
Et plus loin sur la route, ce noeud
diront, supprimez tout le monde.

376
00:18:50,940 --> 00:18:53,940
Mais finalement, nous allons arriver à la
point où la liste est nulle,

377
00:18:53,940 --> 00:18:55,310
et voilà notre scénario de base.

378
00:18:55,310 --> 00:18:57,010
>> Donc, nous allons jeter un oeil à cela,
et comment cela pourrait fonctionner.

379
00:18:57,010 --> 00:18:59,759
Alors, voici notre liste, il est le même
liste que nous venons de parler,

380
00:18:59,759 --> 00:19:00,980
et il ya les étapes.

381
00:19:00,980 --> 00:19:04,200
Il ya beaucoup de texte ici, mais
Espérons que la visualisation aidera.

382
00:19:04,200 --> 00:19:08,557
>> Donc, nous have-- et je également tiré
notre cadres de pile illustration

383
00:19:08,557 --> 00:19:10,890
de notre vidéo sur des piles d'appels,
et nous espérons que tout cela

384
00:19:10,890 --> 00:19:13,260
ainsi va vous montrer ce qui se passe.

385
00:19:13,260 --> 00:19:14,510
Alors, voici notre code pseudo.

386
00:19:14,510 --> 00:19:17,830
Si nous arrivons à un null
pointeur, arrêtez, sinon,

387
00:19:17,830 --> 00:19:21,320
supprimer le reste de la liste,
puis libérer le noeud courant.

388
00:19:21,320 --> 00:19:25,700
Donc maintenant, films--
le pointeur que nous sommes

389
00:19:25,700 --> 00:19:28,410
passant de détruire des points à 12.

390
00:19:28,410 --> 00:19:33,340
12 est pas un pointeur NULL, donc nous sommes
va supprimer le reste de la liste.

391
00:19:33,340 --> 00:19:35,450
>> Ce qui est la suppression de la
reste d'entre nous impliqués?

392
00:19:35,450 --> 00:19:37,950
Eh bien, cela signifie faire un
appeler à détruire, en disant

393
00:19:37,950 --> 00:19:42,060
15 qui est le début de la
reste de la liste que nous voulons détruire.

394
00:19:42,060 --> 00:19:47,480
Et si l'appel à détruire
12 est une sorte de en attente.

395
00:19:47,480 --> 00:19:52,690
Il y est gelé, en attendant le
appeler à détruire 15, pour terminer son travail.

396
00:19:52,690 --> 00:19:56,280
>> Eh bien, 15 est pas un pointeur NULL, et
donc il va dire, tout droit,

397
00:19:56,280 --> 00:19:58,450
ainsi, supprimer le reste de la liste.

398
00:19:58,450 --> 00:20:00,760
Le reste de la liste commence
à 9, et donc nous allons simplement

399
00:20:00,760 --> 00:20:04,514
attendre jusqu'à ce que vous supprimez tout ce qui
des trucs, puis revenir et supprimer moi.

400
00:20:04,514 --> 00:20:06,680
Eh bien 9 qui va se dire, eh bien,
Je ne suis pas un pointeur NULL,

401
00:20:06,680 --> 00:20:09,020
donc supprimer le reste de la liste à partir d'ici.

402
00:20:09,020 --> 00:20:11,805
Et donc essayer de détruire 13.

403
00:20:11,805 --> 00:20:15,550
13 dit, je ne suis pas pointeur NULL,
même chose, il renvoie la balle.

404
00:20:15,550 --> 00:20:17,930
10 ne pointeur NULL, 10
contient un pointeur NULL,

405
00:20:17,930 --> 00:20:20,200
mais 10 est pas en soi une
pointeur NULL en ce moment,

406
00:20:20,200 --> 00:20:22,470
et il renvoie la balle trop.

407
00:20:22,470 --> 00:20:25,560
>> Et maintenant, la liste des points là, il
serait vraiment pointer vers some--

408
00:20:25,560 --> 00:20:28,710
si je devais plus d'espace dans l'image,
il rappelle à l'espace aléatoire

409
00:20:28,710 --> 00:20:29,960
que nous ne savons pas ce qu'il est.

410
00:20:29,960 --> 00:20:34,680
Il est le pointeur NULL si, la liste
est littéralement maintenant réglée, il est des valeurs nulles.

411
00:20:34,680 --> 00:20:36,820
Il est pointant vers la droite dans cette boîte rouge.

412
00:20:36,820 --> 00:20:39,960
Nous avons atteint un pointeur NULL, donc
nous pouvons nous arrêter, et nous allons faire.

413
00:20:39,960 --> 00:20:46,230
>> Et pour que purple frame est maintenant-- au
haut de stack-- qui est du cadre actif,

414
00:20:46,230 --> 00:20:47,017
mais il l'a fait.

415
00:20:47,017 --> 00:20:48,600
Si nous avons atteint un pointeur NULL, arrêter.

416
00:20:48,600 --> 00:20:51,290
Nous ne faisons rien, nous
ne peut pas libérer un pointeur NULL,

417
00:20:51,290 --> 00:20:55,070
nous ne sommes pas tout malloc
espace, et donc nous avons fini.

418
00:20:55,070 --> 00:20:57,590
Alors que cadre de fonction
est détruit, et nous

419
00:20:57,590 --> 00:21:00,930
resume-- nous ramassons où nous avons laissé
off avec le plus élevé suivant une, qui

420
00:21:00,930 --> 00:21:02,807
est ce cadre bleu foncé ici.

421
00:21:02,807 --> 00:21:04,390
Donc, nous ramassons là où nous nous sommes quittés.

422
00:21:04,390 --> 00:21:06,598
Nous avons supprimé le reste de la
liste déjà, alors maintenant nous sommes

423
00:21:06,598 --> 00:21:08,000
va libérer les noeuds de courant.

424
00:21:08,000 --> 00:21:12,920
Alors maintenant, nous pouvons libérer ce noeud, et maintenant
nous avons atteint la fin de la fonction.

425
00:21:12,920 --> 00:21:16,810
Et pour que cadre de fonction est détruite,
et nous chercher à le bleu clair.

426
00:21:16,810 --> 00:21:20,650
>> Donc, il says-- Je l'ai déjà done--
de supprimer le reste de la liste, de sorte

427
00:21:20,650 --> 00:21:23,140
libérer le noeud courant.

428
00:21:23,140 --> 00:21:26,520
Et maintenant le cadre jaune est
retour au sommet de la pile.

429
00:21:26,520 --> 00:21:29,655
Et comme vous le voyez, nous sommes maintenant
détruire la liste de droite à gauche.

430
00:21:29,655 --> 00:21:33,710

431
00:21:33,710 --> 00:21:37,280
>> Que serait-il arrivé, si,
si nous avions fait les choses dans le mauvais sens?

432
00:21:37,280 --> 00:21:39,410
Tout comme quand nous avons essayé
à ajouter un élément.

433
00:21:39,410 --> 00:21:41,909
Si nous foiré la chaîne, si
nous ne relions pas les pointeurs

434
00:21:41,909 --> 00:21:44,690
dans le bon ordre, si nous
juste libéré du premier élément,

435
00:21:44,690 --> 00:21:47,420
si nous avons juste libéré les
tête de la liste, maintenant nous

436
00:21:47,420 --> 00:21:49,642
aurait aucun moyen de se référer à
le reste de la liste.

437
00:21:49,642 --> 00:21:51,350
Et si nous aurions
tout orphelins,

438
00:21:51,350 --> 00:21:53,880
nous aurions eu ce qui est
appelé une fuite de mémoire.

439
00:21:53,880 --> 00:21:56,800
Si vous vous souvenez de notre vidéo
sur l'allocation dynamique de la mémoire,

440
00:21:56,800 --> 00:21:58,650
ce ne est pas très bonne chose.

441
00:21:58,650 --> 00:22:00,810
>> Donc, comme je le disais, il
Plusieurs opérations

442
00:22:00,810 --> 00:22:04,010
que nous devons utiliser pour travailler
avec liste liée de manière efficace.

443
00:22:04,010 --> 00:22:08,430
Et vous avez peut-être remarqué que je omis un,
la suppression d'un élément unique à partir d'un lien

444
00:22:08,430 --> 00:22:09,064
liste.

445
00:22:09,064 --> 00:22:10,980
La raison pour laquelle je l'ai fait
est il est en fait assez

446
00:22:10,980 --> 00:22:14,360
difficile de penser à la façon de supprimer
un seul élément à partir d'un seul

447
00:22:14,360 --> 00:22:15,600
liste chaînée.

448
00:22:15,600 --> 00:22:19,950
Nous devons être en mesure de sauter
quelque chose dans la liste, qui

449
00:22:19,950 --> 00:22:22,975
signifie que nous arrivons à un nous point--
vouloir supprimer ce node--

450
00:22:22,975 --> 00:22:25,350
mais dans le but de faire en sorte que nous
ne perdez aucune information,

451
00:22:25,350 --> 00:22:30,530
nous avons besoin de connecter ce
noeud plus ici, ici.

452
00:22:30,530 --> 00:22:33,390
>> Donc, je l'ai fait de mal sans doute
à partir d'un point de vue visuel.

453
00:22:33,390 --> 00:22:36,830
Donc, nous sommes au début de notre
liste, nous allons procéder par le biais,

454
00:22:36,830 --> 00:22:40,510
nous voulons supprimer ce noeud.

455
00:22:40,510 --> 00:22:43,440
Si nous venons de supprimer,
nous avons brisé la chaîne.

456
00:22:43,440 --> 00:22:45,950
Ce nœud ici
se réfère à tout le reste,

457
00:22:45,950 --> 00:22:48,260
il contient la chaîne à partir de maintenant.

458
00:22:48,260 --> 00:22:51,190
>> Donc, ce que nous devons faire effectivement
après nous arrivons à ce point,

459
00:22:51,190 --> 00:22:56,670
est que nous devons prendre du recul un, et
connecter ce noeud plus à ce nœud,

460
00:22:56,670 --> 00:22:58,590
afin que nous puissions ensuite supprimer
l'une au milieu.

461
00:22:58,590 --> 00:23:02,120
Mais les listes simplement liés ne le font pas
nous fournir un moyen de revenir en arrière.

462
00:23:02,120 --> 00:23:05,160
Nous devons donc soit conserver
deux pointeurs, et les déplacer

463
00:23:05,160 --> 00:23:09,527
sorte d'étape au large, les uns derrière les
d'autres que nous allons, ou arrivez à un point

464
00:23:09,527 --> 00:23:11,110
puis envoyer un autre pointeur à travers.

465
00:23:11,110 --> 00:23:13,150
Et comme vous pouvez le voir, il
peut obtenir un peu désordonné.

466
00:23:13,150 --> 00:23:15,360
Heureusement, nous avons
une autre façon de résoudre cela,

467
00:23:15,360 --> 00:23:17,810
lorsque nous parlons de listes doublement chaînées.

468
00:23:17,810 --> 00:23:20,720
>> Je suis Doug Lloyd, cela est CS50.

469
00:23:20,720 --> 00:23:22,298