1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] În programare, de multe ori am nevoie pentru a reprezenta liste de valori,

2
00:00:10,050 --> 00:00:12,840
cum ar fi numele de elevi într-o secțiune

3
00:00:12,840 --> 00:00:15,100
sau scorurile lor pe ultimul test.

4
00:00:15,100 --> 00:00:17,430
>> În limbajul C, a declarat matrice poate fi folosit

5
00:00:17,430 --> 00:00:19,160
pentru a stoca liste.

6
00:00:19,160 --> 00:00:21,200
E ușor să enumerăm elementele unei liste

7
00:00:21,200 --> 00:00:23,390
stocate într-o matrice, și în cazul în care aveți nevoie pentru a accesa

8
00:00:23,390 --> 00:00:25,050
sau de a modifica lista de elementul-lea

9
00:00:25,050 --> 00:00:27,570
pentru unele indicele arbitrare I,

10
00:00:27,570 --> 00:00:29,910
care se poate face în timp constant,

11
00:00:29,910 --> 00:00:31,660
dar tablouri au dezavantaje, de asemenea.

12
00:00:31,660 --> 00:00:33,850
>> Când ne-am le declare, suntem necesar să spunem

13
00:00:33,850 --> 00:00:35,900
în față cât de mare sunt,

14
00:00:35,900 --> 00:00:38,160
că este, cât de multe elemente care pot stoca

15
00:00:38,160 --> 00:00:40,780
și cât de mare aceste elemente sunt, care este determinat de tipul lor.

16
00:00:40,780 --> 00:00:45,450
De exemplu, int arr (10)

17
00:00:45,450 --> 00:00:48,220
poate stoca 10 articole

18
00:00:48,220 --> 00:00:50,200
care sunt de dimensiunea unei int.

19
00:00:50,200 --> 00:00:52,590
>> Noi nu putem schimba dimensiunea unei matrice, după declarația.

20
00:00:52,590 --> 00:00:55,290
Avem de a face o nouă matrice, dacă vrem să stocați mai multe elemente.

21
00:00:55,290 --> 00:00:57,410
Motivul acestei limitări este faptul că există noastră

22
00:00:57,410 --> 00:00:59,040
Programul stochează întreaga gamă

23
00:00:59,040 --> 00:01:02,310
ca o bucată de memorie contiguă.

24
00:01:02,310 --> 00:01:04,500
Spun acest lucru este în cazul în care buffer-am depozitat în gama noastră.

25
00:01:04,500 --> 00:01:06,910
S-ar putea să fie cu alte variabile

26
00:01:06,910 --> 00:01:08,310
situat chiar lângă matrice

27
00:01:08,310 --> 00:01:10,060
în memorie, astfel încât nu putem

28
00:01:10,060 --> 00:01:12,060
doar asigurați-matrice mai mare.

29
00:01:12,060 --> 00:01:15,700
>> Uneori am dori să comerțului matrice de rapid viteza de acces la date

30
00:01:15,700 --> 00:01:17,650
pentru o flexibilitate pic mai mult.

31
00:01:17,650 --> 00:01:20,380
Introduceți lista de legat, o altă structură de date de bază

32
00:01:20,380 --> 00:01:22,360
ar putea să nu fie la fel de familiarizați cu.

33
00:01:22,360 --> 00:01:24,200
La un nivel ridicat,

34
00:01:24,200 --> 00:01:26,840
o listă legată stochează datele într-o secvență de noduri

35
00:01:26,840 --> 00:01:29,280
care sunt conectate între ele cu link-uri,

36
00:01:29,280 --> 00:01:31,760
prin urmare, numele de "lista legat."

37
00:01:31,760 --> 00:01:33,840
După cum vom vedea, această diferență în proiectarea

38
00:01:33,840 --> 00:01:35,500
conduce la diferite avantaje și dezavantaje

39
00:01:35,500 --> 00:01:37,000
decât o matrice.

40
00:01:37,000 --> 00:01:39,840
>> Iată unele cod C pentru o listă foarte simplu legat de numere întregi.

41
00:01:39,840 --> 00:01:42,190
Puteti vedea ca am reprezentat fiecare nod

42
00:01:42,190 --> 00:01:45,520
în listă ca o struct care conține 2 lucruri,

43
00:01:45,520 --> 00:01:47,280
un întreg pentru a stoca numită "val"

44
00:01:47,280 --> 00:01:50,460
precum și un link la nodul următor din listă

45
00:01:50,460 --> 00:01:52,990
care ne reprezintă ca un indicator numit "viitoare."

46
00:01:54,120 --> 00:01:56,780
În acest fel, putem urmări întreaga listă

47
00:01:56,780 --> 00:01:58,790
cu doar un pointer la nodul unic prima,

48
00:01:58,790 --> 00:02:01,270
și apoi putem să urmați indicii pentru următoarele

49
00:02:01,270 --> 00:02:03,130
la nodul 2,

50
00:02:03,130 --> 00:02:05,280
la nodul 3,

51
00:02:05,280 --> 00:02:07,000
la nodul 4,

52
00:02:07,000 --> 00:02:09,889
și așa mai departe, până când vom ajunge la sfârșitul listei.

53
00:02:10,520 --> 00:02:12,210
>> S-ar putea fi capabil de a vedea un avantaj acest lucru are

54
00:02:12,210 --> 00:02:14,490
peste structura de matrice statice - cu o listă legată,

55
00:02:14,490 --> 00:02:16,450
nu avem nevoie de o bucată mare de memorie cu totul.

56
00:02:17,400 --> 00:02:20,530
Nodul prima din lista ar putea trăi în acest loc în memorie,

57
00:02:20,530 --> 00:02:23,160
și nodul două ar putea fi tot drumul până aici.

58
00:02:23,160 --> 00:02:25,780
Putem ajunge la toate nodurile, indiferent unde în memorie sunt,

59
00:02:25,780 --> 00:02:28,890
deoarece incepand de la nodul 1, indicatorul fiecare nod de pe lângă

60
00:02:28,890 --> 00:02:31,700
ne spune exact unde să mergem.

61
00:02:31,700 --> 00:02:33,670
>> În plus, nu avem de spus în față

62
00:02:33,670 --> 00:02:36,740
cât de mare o listă legată va fi modul in care facem cu matrice statice,

63
00:02:36,740 --> 00:02:39,060
deoarece putem păstra adăugarea noduri la o listă

64
00:02:39,060 --> 00:02:42,600
atât timp cât nu există spațiu de undeva în memorie pentru noduri noi.

65
00:02:42,600 --> 00:02:45,370
Prin urmare, listele legate sunt ușor pentru a redimensiona dinamic.

66
00:02:45,370 --> 00:02:47,950
Spune, mai târziu, în programul de care avem nevoie pentru a adăuga mai multe noduri

67
00:02:47,950 --> 00:02:49,350
în lista noastră.

68
00:02:49,350 --> 00:02:51,480
Pentru a insera un nou nod în lista noastră de pe zbura,

69
00:02:51,480 --> 00:02:53,740
tot ce trebuie să faceți este să aloce memorie pentru acel nod,

70
00:02:53,740 --> 00:02:55,630
plop, în valoare de date,

71
00:02:55,630 --> 00:02:59,070
și plasați-l, apoi în cazul în care ne dorim prin ajustarea corespunzătoare indicii.

72
00:02:59,070 --> 00:03:02,310
>> De exemplu, dacă am vrut să plaseze un nod între

73
00:03:02,310 --> 00:03:04,020
nodurile 2 și 3 ale listei,

74
00:03:04,020 --> 00:03:06,800
 noi nu ar trebui să se mute nodurile 2 sau 3, la toate.

75
00:03:06,800 --> 00:03:09,190
Spune-ne inserarea acestui nod rosu.

76
00:03:09,190 --> 00:03:12,890
Tot ce ar trebui să faceți este să setați indicatorul nod nou de pe lângă

77
00:03:12,890 --> 00:03:14,870
pentru a indica nodul treia

78
00:03:14,870 --> 00:03:18,580
și rewire apoi indicatorul nod doilea de pe lângă

79
00:03:18,580 --> 00:03:20,980
pentru a indica noul nostru nod.

80
00:03:22,340 --> 00:03:24,370
Deci, ne putem redimensiona listele noastre de pe zbor

81
00:03:24,370 --> 00:03:26,090
deoarece calculatorul nostru nu se bazează pe indexare,

82
00:03:26,090 --> 00:03:28,990
ci mai degrabă pe corelarea folosind indicii pentru a le stoca.

83
00:03:29,120 --> 00:03:31,600
>> Lista de preturi cu toate acestea, un dezavantaj al legate de

84
00:03:31,600 --> 00:03:33,370
este faptul că, spre deosebire de o matrice statice,

85
00:03:33,370 --> 00:03:36,690
calculatorul nu poate sari doar la mijlocul listei.

86
00:03:38,040 --> 00:03:40,780
Din moment ce computerul are de a vizita fiecare nod în listă legată

87
00:03:40,780 --> 00:03:42,330
pentru a ajunge la următoarea,

88
00:03:42,330 --> 00:03:44,770
se va lua mai mult timp pentru a găsi un anumit nod

89
00:03:44,770 --> 00:03:46,400
decât ar fi într-o matrice.

90
00:03:46,400 --> 00:03:48,660
Pentru a traversa întreaga listă nevoie de timp proporțională

91
00:03:48,660 --> 00:03:50,580
la lungimea listei,

92
00:03:50,580 --> 00:03:54,630
sau O (n) în notație asimptotică.

93
00:03:54,630 --> 00:03:56,510
În medie, ajungând la orice nod

94
00:03:56,510 --> 00:03:58,800
De asemenea, are nevoie de timp proporțională cu nr.

95
00:03:58,800 --> 00:04:00,700
>> Acum, hai să scrie de fapt un cod

96
00:04:00,700 --> 00:04:02,000
care funcționează cu liste legate.

97
00:04:02,000 --> 00:04:04,220
Să spunem că doriți o listă legată de întregi.

98
00:04:04,220 --> 00:04:06,140
Ne poate reprezenta un nod în lista noastră din nou

99
00:04:06,140 --> 00:04:08,340
ca o struct cu 2 campuri,

100
00:04:08,340 --> 00:04:10,750
o valoare întreagă numită "val"

101
00:04:10,750 --> 00:04:13,490
și un pointer lângă urmatorul nod al listei.

102
00:04:13,490 --> 00:04:15,660
Ei bine, se pare destul de simplu.

103
00:04:15,660 --> 00:04:17,220
>> Să presupunem că vrem să scrie o funcție

104
00:04:17,220 --> 00:04:19,329
care traversează lista și imprimă

105
00:04:19,329 --> 00:04:22,150
valoarea stocată în ultimul nod al listei.

106
00:04:22,150 --> 00:04:24,850
Ei bine, asta înseamnă că va trebui să traverseze toate nodurile din lista

107
00:04:24,850 --> 00:04:27,310
pentru a găsi ultima, dar din moment ce nu suntem adăugarea de

108
00:04:27,310 --> 00:04:29,250
sau ștergerea nimic, nu vrem să se schimbe

109
00:04:29,250 --> 00:04:32,210
structura internă a pointerilor următoare în listă.

110
00:04:32,210 --> 00:04:34,790
>> Deci, vom avea nevoie de un pointer special pentru traversarea

111
00:04:34,790 --> 00:04:36,940
pe care o vom numi "pe șenile."

112
00:04:36,940 --> 00:04:38,870
Acesta va accesa cu crawlere prin toate elementele listei

113
00:04:38,870 --> 00:04:41,190
urmând lanțul de pointeri pentru următoarele.

114
00:04:41,190 --> 00:04:43,750
Tot ce-am stocat este un pointer la nodul 1,

115
00:04:43,750 --> 00:04:45,730
sau "capul" listei.

116
00:04:45,730 --> 00:04:47,370
Puncte de cap la nodul primul.

117
00:04:47,370 --> 00:04:49,120
Este de tip pointer-la-nod.

118
00:04:49,120 --> 00:04:51,280
>> Pentru a obține efectiv primul nod în listă,

119
00:04:51,280 --> 00:04:53,250
trebuie să dereference acest indicator,

120
00:04:53,250 --> 00:04:55,100
dar înainte de a putem dereference, avem nevoie pentru a verifica

121
00:04:55,100 --> 00:04:57,180
dacă indicatorul este nul primul.

122
00:04:57,180 --> 00:04:59,190
Dacă e nul, lista este goală,

123
00:04:59,190 --> 00:05:01,320
și ar trebui să imprima un mesaj care, pentru că lista este goală,

124
00:05:01,320 --> 00:05:03,250
nu există nici un nod ultima.

125
00:05:03,250 --> 00:05:05,190
Dar, hai să spunem lista nu este goală.

126
00:05:05,190 --> 00:05:08,340
Dacă nu e, atunci ar trebui să se târască prin intreaga lista

127
00:05:08,340 --> 00:05:10,440
până când vom ajunge la ultimul nod din lista,

128
00:05:10,440 --> 00:05:13,030
și cum putem spune dacă ne uităm la ultimul nod din listă?

129
00:05:13,670 --> 00:05:16,660
>> Ei bine, în cazul în care indicatorul de pe lângă un nod este nulă,

130
00:05:16,660 --> 00:05:18,320
știm că suntem la sfârșitul

131
00:05:18,320 --> 00:05:22,390
deoarece indicatorul ultima următoare ar avea nici un nod următor din lista de la punctul la.

132
00:05:22,390 --> 00:05:26,590
E bună practică de a păstra întotdeauna indicatorul ultimul nod de pe lângă inițializat la nul

133
00:05:26,590 --> 00:05:30,800
pentru a avea o proprietate standardizat care ne avertizează atunci când am ajuns la sfârșitul listei.

134
00:05:30,800 --> 00:05:33,510
>> Deci, în cazul în care pe șenile → următoare este nulă,

135
00:05:34,120 --> 00:05:38,270
amintiți-vă că săgeata de sintaxa este o comandă rapidă pentru dereferencing

136
00:05:38,270 --> 00:05:40,010
un pointer la o structura, atunci accesarea

137
00:05:40,010 --> 00:05:42,510
sa câmpul de lângă echivalentă cu incomode:

138
00:05:42,510 --> 00:05:48,750
(* Pe șenile). Următor.

139
00:05:49,820 --> 00:05:51,260
Odată ce am găsit ultimul nod,

140
00:05:51,260 --> 00:05:53,830
vrem să le imprimați pe șenile → val,

141
00:05:53,830 --> 00:05:55,000
valoarea din nodul curent

142
00:05:55,000 --> 00:05:57,130
care știm că este ultima.

143
00:05:57,130 --> 00:05:59,740
În caz contrar, dacă nu suntem încă la ultimul nod din lista,

144
00:05:59,740 --> 00:06:02,340
avem pentru a trece la urmatorul nod din lista

145
00:06:02,340 --> 00:06:04,750
și verificați dacă asta e ultima.

146
00:06:04,750 --> 00:06:07,010
Pentru a face acest lucru, am stabilit doar indicatorul nostru pe șenile

147
00:06:07,010 --> 00:06:09,840
să indice valoarea nodul curent de pe lângă,

148
00:06:09,840 --> 00:06:11,680
că este, nodul următor din listă.

149
00:06:11,680 --> 00:06:13,030
Acest lucru se face prin setarea

150
00:06:13,030 --> 00:06:15,280
pe șenile crawler = → viitoare.

151
00:06:16,050 --> 00:06:18,960
Apoi ne-am repeta acest proces, cu o buclă, de exemplu,

152
00:06:18,960 --> 00:06:20,960
până când vom găsi ultimul nod.

153
00:06:20,960 --> 00:06:23,150
Deci, de exemplu, în cazul în care a fost pe șenile îndreptat spre cap,

154
00:06:24,050 --> 00:06:27,710
am setat pe șenile pentru a indica pe șenile → următoare,

155
00:06:27,710 --> 00:06:30,960
care este aceeași ca și în câmpul următor al nodului primul.

156
00:06:30,960 --> 00:06:33,620
Deci, acum crawlerul nostru este îndreptat la nodul 2,

157
00:06:33,620 --> 00:06:35,480
și, din nou, vom repeta acest lucru cu o buclă,

158
00:06:37,220 --> 00:06:40,610
până când am găsit ultimul nod, care este,

159
00:06:40,610 --> 00:06:43,640
în cazul în care indicatorul de pe lângă nod este indică spre zero.

160
00:06:43,640 --> 00:06:45,070
Și acolo îl avem,

161
00:06:45,070 --> 00:06:47,620
am gasit ultimul nod din lista, pentru a imprima și valoarea sa,

162
00:06:47,620 --> 00:06:50,800
vom folosi doar pe șenile → val.

163
00:06:50,800 --> 00:06:53,130
>> Traversarea nu este așa de rău, dar ce despre introducerea?

164
00:06:53,130 --> 00:06:56,290
Să spun că vrem să inserați un întreg în locul 4

165
00:06:56,290 --> 00:06:58,040
într-o listă întreagă.

166
00:06:58,040 --> 00:07:01,280
Aceasta este între nodurile curente 3 si 4.

167
00:07:01,280 --> 00:07:03,760
Din nou, trebuie să traverseze lista doar pentru a

168
00:07:03,760 --> 00:07:06,520
ajunge la elementul treia, cea pe care o ai dupa inserarea.

169
00:07:06,520 --> 00:07:09,300
Deci, vom crea un pointer pe șenile din nou pentru a traversa pe lista,

170
00:07:09,300 --> 00:07:11,400
verificați dacă indicatorul nostru central este nul,

171
00:07:11,400 --> 00:07:14,810
si daca nu e, punctul nostru de indicatorul pe șenile de la nodul capului.

172
00:07:16,880 --> 00:07:18,060
Deci, suntem la primul element.

173
00:07:18,060 --> 00:07:21,020
Trebuie să mergem mai departe 2 mai multe elemente înainte de a putea insera,

174
00:07:21,020 --> 00:07:23,390
astfel încât să putem folosi o buclă pentru

175
00:07:23,390 --> 00:07:26,430
int i = 1; i <3; i + +

176
00:07:26,430 --> 00:07:28,590
și în fiecare iterație a buclei,

177
00:07:28,590 --> 00:07:31,540
avansa indicatorul nostru pe șenile înainte de 1 nod

178
00:07:31,540 --> 00:07:34,570
prin verificarea dacă câmpul nodul curent de pe lângă este nul,

179
00:07:34,570 --> 00:07:37,550
si daca nu e, mutați indicatorul crawlerului nostru la urmatorul nod

180
00:07:37,550 --> 00:07:41,810
prin fixarea egală cu indicatorul de pe lângă nodul curent.

181
00:07:41,810 --> 00:07:45,210
Deci, din moment bucla noastră pentru a face acest lucru spune

182
00:07:45,210 --> 00:07:47,550
de două ori,

183
00:07:49,610 --> 00:07:51,190
am ajuns la nodul 3,

184
00:07:51,190 --> 00:07:53,110
și o dată indicatorul crawlerului nostru a ajuns la nodul după

185
00:07:53,110 --> 00:07:55,270
pe care dorim să inserați noul nostru întreg,

186
00:07:55,270 --> 00:07:57,050
cum facem de fapt introducerea?

187
00:07:57,050 --> 00:07:59,440
>> Ei bine, întreg noul nostru trebuie să fie introdus în lista de

188
00:07:59,440 --> 00:08:01,250
ca parte dintr-o structura de nod proprie,

189
00:08:01,250 --> 00:08:03,140
deoarece aceasta este într-adevăr o secvență de noduri.

190
00:08:03,140 --> 00:08:05,690
Deci, hai să facem un pointer la nodul nou

191
00:08:05,690 --> 00:08:08,910
numit "new_node,"

192
00:08:08,910 --> 00:08:11,800
și a stabilit la punctul în memorie pe care le aloca acum

193
00:08:11,800 --> 00:08:14,270
pe heap pentru nodul în sine,

194
00:08:14,270 --> 00:08:16,000
și cât de mult de memorie avem nevoie de a aloca?

195
00:08:16,000 --> 00:08:18,250
Ei bine, de marimea unui nod,

196
00:08:20,450 --> 00:08:23,410
și vrem să setați domeniul său la Val întreg care ne-o dorim pentru a insera.

197
00:08:23,410 --> 00:08:25,590
Să spunem, 6.

198
00:08:25,590 --> 00:08:27,710
Acum, nodul conține valoarea noastră întreagă.

199
00:08:27,710 --> 00:08:30,650
Este, de asemenea, bune practici pentru a inițializa câmp noul nod de pe lângă

200
00:08:30,650 --> 00:08:33,690
să indice null,

201
00:08:33,690 --> 00:08:35,080
dar acum ce?

202
00:08:35,080 --> 00:08:37,179
>> Avem de a schimba structura internă a listei

203
00:08:37,179 --> 00:08:40,409
și indicii pentru următoarele cuprinse în lista existentă de

204
00:08:40,409 --> 00:08:42,950
Nodurile 3 și 4.

205
00:08:42,950 --> 00:08:46,560
Având în vedere că indicii următoarele determina ordinea listei,

206
00:08:46,560 --> 00:08:48,650
și din moment ce ne introduce noul nostru nod

207
00:08:48,650 --> 00:08:50,510
chiar în mijlocul listei,

208
00:08:50,510 --> 00:08:52,010
acesta poate fi un pic dificil.

209
00:08:52,010 --> 00:08:54,250
Acest lucru se datorează faptului că, amintiți-vă, calculatorul nostru

210
00:08:54,250 --> 00:08:56,250
cunoaște doar amplasarea de noduri în listă

211
00:08:56,250 --> 00:09:00,400
din cauza indicii următoarele stocate în nodurile precedente.

212
00:09:00,400 --> 00:09:03,940
Deci, dacă ne-am pierdut vreodată cale de oricare dintre aceste locații,

213
00:09:03,940 --> 00:09:06,860
spun prin schimbarea uneia dintre următoarele indicii din lista noastră,

214
00:09:06,860 --> 00:09:09,880
de exemplu, să spunem ne-am schimbat

215
00:09:09,880 --> 00:09:12,920
nod treilea domeniu de pe lângă

216
00:09:12,920 --> 00:09:15,610
să indice o nod aici.

217
00:09:15,610 --> 00:09:17,920
Ne-ar fi de noroc, pentru că nu ne-am

218
00:09:17,920 --> 00:09:20,940
au nici o idee în cazul în care pentru a găsi restul listei,

219
00:09:20,940 --> 00:09:23,070
și că este, evident, foarte rău.

220
00:09:23,070 --> 00:09:25,080
Deci, trebuie să fim foarte atenți cu privire la comanda

221
00:09:25,080 --> 00:09:28,360
în care ne manipula pointeri noastre pentru următoarele timpul inserției.

222
00:09:28,360 --> 00:09:30,540
>> Deci, pentru a simplifica acest lucru, să spunem că

223
00:09:30,540 --> 00:09:32,220
primele noastre 4 noduri

224
00:09:32,220 --> 00:09:36,200
sunt numite A, B,, C, și D, cu săgeți care reprezintă lanțul de pointeri

225
00:09:36,200 --> 00:09:38,070
care conectează nodurile.

226
00:09:38,070 --> 00:09:40,050
Deci, avem nevoie de a introduce noul nostru nod

227
00:09:40,050 --> 00:09:42,070
între nodurile C și D.

228
00:09:42,070 --> 00:09:45,060
Este important să-l facă în ordinea corectă, și vă voi arăta de ce.

229
00:09:45,060 --> 00:09:47,500
>> Să ne uităm la modul greșit de a face acest lucru mai întâi.

230
00:09:47,500 --> 00:09:49,490
Hei, știm noul nod trebuie să vină imediat dupa C,

231
00:09:49,490 --> 00:09:51,910
așa că hai să setați indicatorul următor lui C

232
00:09:51,910 --> 00:09:54,700
să indice new_node.

233
00:09:56,530 --> 00:09:59,180
În regulă, pare ok, trebuie doar să termin până acum de către

234
00:09:59,180 --> 00:10:01,580
punct de luare nod nou indicatorul de lângă D,

235
00:10:01,580 --> 00:10:03,250
dar așteptați, cum putem face asta?

236
00:10:03,250 --> 00:10:05,170
Singurul lucru care ne-ar putea spune unde D a fost,

237
00:10:05,170 --> 00:10:07,630
a fost următoarea indicatorul anterior stocate în C,

238
00:10:07,630 --> 00:10:09,870
dar am rescris doar că indicatorul

239
00:10:09,870 --> 00:10:11,170
pentru a indica nou nod,

240
00:10:11,170 --> 00:10:14,230
astfel încât nu mai avem nici o idee unde D este în memorie,

241
00:10:14,230 --> 00:10:17,020
și am pierdut restul listei.

242
00:10:17,020 --> 00:10:19,000
Nu e bine deloc.

243
00:10:19,000 --> 00:10:21,090
>> Deci, cum facem acest drept?

244
00:10:22,360 --> 00:10:25,090
În primul rând, punctul indicatorul noul nod de pe lângă la D.

245
00:10:26,170 --> 00:10:28,990
Acum, atât noul nod lui și a lui C pentru următoarele indicii

246
00:10:28,990 --> 00:10:30,660
sunt orientate către același nod, D,

247
00:10:30,660 --> 00:10:32,290
dar asta e bine.

248
00:10:32,290 --> 00:10:35,680
Acum putem indica indicatorul următor C, la nod nou.

249
00:10:37,450 --> 00:10:39,670
Deci, am făcut acest lucru fără a pierde date.

250
00:10:39,670 --> 00:10:42,280
În cod, C este nodul curent

251
00:10:42,280 --> 00:10:45,540
că indicatorul traversare pe șenile este orientată spre,

252
00:10:45,540 --> 00:10:50,400
și D este reprezentat de nodul indicat de către câmpul nodul curent de pe lângă,

253
00:10:50,400 --> 00:10:52,600
sau pe șenile → următoare.

254
00:10:52,600 --> 00:10:55,460
Deci, ne-am stabilit prima indicatorul nod nou de pe lângă

255
00:10:55,460 --> 00:10:57,370
să indice pe șenile → următoare,

256
00:10:57,370 --> 00:11:00,880
fel cum am spus indicatorul următor new_node ar trebui să

257
00:11:00,880 --> 00:11:02,780
indică D în ilustrație.

258
00:11:02,780 --> 00:11:04,540
Apoi, putem seta indicatorul nodul curent de pe lângă

259
00:11:04,540 --> 00:11:06,330
la nodul noul nostru,

260
00:11:06,330 --> 00:11:10,980
la fel cum am fost nevoiți să așteptăm de la punctul C la new_node în desen.

261
00:11:10,980 --> 00:11:12,250
Acum totul e în ordine, și nu ne-am pierdut

262
00:11:12,250 --> 00:11:14,490
evidența tuturor datelor, și noi am fost capabil să pur și simplu

263
00:11:14,490 --> 00:11:16,200
lipi nod noul nostru în mijlocul listei

264
00:11:16,200 --> 00:11:19,330
fără reconstrucția totul sau schimbarea chiar orice elemente

265
00:11:19,330 --> 00:11:22,490
modul în care ne-ar fi trebuit să o matrice de lungime fixă.

266
00:11:22,490 --> 00:11:26,020
>> Deci, listele sunt legate de o bază, dar importantă, dinamică structură de date

267
00:11:26,020 --> 00:11:29,080
care au atât avantaje, cât și dezavantaje

268
00:11:29,080 --> 00:11:31,260
comparativ cu matrice și alte structuri de date,

269
00:11:31,260 --> 00:11:33,350
și așa cum este adesea cazul în informatică,

270
00:11:33,350 --> 00:11:35,640
este important să știi când să utilizeze fiecare instrument,

271
00:11:35,640 --> 00:11:37,960
astfel încât să puteți alege instrumentul potrivit pentru postul potrivit.

272
00:11:37,960 --> 00:11:40,060
>> Pentru mai multă practică, încearcă să scrii funcțiile pentru a

273
00:11:40,060 --> 00:11:42,080
șterge nodurile dintr-o listă legată -

274
00:11:42,080 --> 00:11:44,050
amintiți-vă să fie atent cu privire ordinea în care ați rearanja

275
00:11:44,050 --> 00:11:47,430
de indicii pentru următoarele pentru a se asigura că nu pierdeți o bucată din lista ta -

276
00:11:47,430 --> 00:11:50,200
sau o funcție pentru a număra nodurile dintr-o listă legată,

277
00:11:50,200 --> 00:11:53,280
sau o distracție, de a inversa ordinea de toate nodurile dintr-o listă legată.

278
00:11:53,280 --> 00:11:56,090
>> Numele meu este Michael Jackson Steinkamp, ​​acest lucru este CS50.