1
00:00:00,000 --> 00:00:02,832
>> [MUSIC JOC]

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

3
00:00:05,670 --> 00:00:08,560
>> DOUG LLOYD: OK, deci la
acest punct în curs,

4
00:00:08,560 --> 00:00:15,300
am acoperit o mulțime de elementele de bază ale C.
Știm multe despre variabile, tablouri,

5
00:00:15,300 --> 00:00:17,610
indicii, toate lucrurile bune.

6
00:00:17,610 --> 00:00:21,610
Acestea sunt tot felul de construit
pentru a vedea cum fundamentele,

7
00:00:21,610 --> 00:00:23,880
dar putem face mai mult, nu?

8
00:00:23,880 --> 00:00:27,930
Putem combina lucruri
împreună în moduri interesante.

9
00:00:27,930 --> 00:00:31,010
>> Și așa să facem asta, să începem
a se ramifica din ceea ce ne dă C,

10
00:00:31,010 --> 00:00:35,270
și să înceapă să creeze propria noastra de date
Folosind aceste structuri de construcție

11
00:00:35,270 --> 00:00:40,590
blocuri impreuna pentru a face ceva
într-adevăr valoros, util.

12
00:00:40,590 --> 00:00:43,420
O modalitate putem face acest lucru este
pentru a vorbi despre colecții.

13
00:00:43,420 --> 00:00:48,360
Deci, până acum am avut un fel de date
structură pentru reprezentarea colecții

14
00:00:48,360 --> 00:00:51,030
de valori, ca valori similare.

15
00:00:51,030 --> 00:00:52,350
Asta ar fi o matrice.

16
00:00:52,350 --> 00:00:57,020
Avem colectii de numere întregi, sau
colecții de caractere și așa mai departe.

17
00:00:57,020 --> 00:01:00,890
>> Structuri sunt, de asemenea, un fel de date
structură pentru colectarea de informații,

18
00:01:00,890 --> 00:01:03,220
dar nu e ca și cum de colectare a valorilor.

19
00:01:03,220 --> 00:01:08,090
De obicei amesteca diferite tipuri de date
împreună în interiorul unui singur cutie.

20
00:01:08,090 --> 00:01:10,750
Dar nu e în sine
folosit pentru a lanțului de împreună

21
00:01:10,750 --> 00:01:16,920
sau conectați împreună similare
elemente, cum ar fi o serie.

22
00:01:16,920 --> 00:01:20,960
Matrice sunt foarte bune pentru
Element privi în sus, dar amintesc

23
00:01:20,960 --> 00:01:24,262
că este foarte dificil
pentru a introduce într-o matrice,

24
00:01:24,262 --> 00:01:26,470
dacă nu te introducerea la
chiar la sfârșitul acestei matrice.

25
00:01:26,470 --> 00:01:29,730
>> Și cel mai bun exemplu am
pentru că este un fel de introducere.

26
00:01:29,730 --> 00:01:31,650
Dacă vă amintiți videoclipul nostru
pe sortare prin inserție,

27
00:01:31,650 --> 00:01:34,110
a existat o mulțime de
cheltuieli implicate în a avea

28
00:01:34,110 --> 00:01:37,970
pentru a ridica elemente, și le-a schimba
din drum pentru a se potrivi ceva

29
00:01:37,970 --> 00:01:41,290
în mijlocul matrice dumneavoastră.

30
00:01:41,290 --> 00:01:44,690
Arrays, de asemenea, suferă de o altă
problemă, care este inflexibilitate.

31
00:01:44,690 --> 00:01:47,150
Când ne-am declara o matrice,
avem o șansă ea.

32
00:01:47,150 --> 00:01:49,790
Noi ne să spun, vreau
acest multe elemente.

33
00:01:49,790 --> 00:01:51,940
S-ar putea fi de 100, s-ar putea
fie 1.000, s-ar putea

34
00:01:51,940 --> 00:01:55,930
fie x unde x este un număr care utilizatorul
ne-a dat la un prompt sau la comanda

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

36
00:01:56,630 --> 00:01:59,905
>> Dar avem doar o singură lovitură de la ea, am
nu ajung apoi să spun oh, de fapt, am

37
00:01:59,905 --> 00:02:04,360
nevoie de 101, sau am nevoie de X, plus 20.

38
00:02:04,360 --> 00:02:07,910
Prea târziu, am declarat deja
matrice, și dacă doriți să obțineți 101 sau X

39
00:02:07,910 --> 00:02:12,050
plus 20, trebuie să declare
o serie complet diferit,

40
00:02:12,050 --> 00:02:15,540
copia toate elementele matricei
peste, iar apoi ne-am ajuns.

41
00:02:15,540 --> 00:02:19,880
Și ce dacă suntem din nou greșit, ceea ce
dacă, de fapt avem nevoie de 102, sau x plus 40,

42
00:02:19,880 --> 00:02:21,970
trebuie să facem acest lucru din nou.

43
00:02:21,970 --> 00:02:26,250
Astfel încât acestea sunt foarte inflexibile
pentru redimensionarea datelor noastre,

44
00:02:26,250 --> 00:02:29,360
dar dacă vom combina unele
din elementele de bază pe care le-am deja

45
00:02:29,360 --> 00:02:33,230
învățat despre indicii și structuri,
în special utilizarea de memorie dinamic

46
00:02:33,230 --> 00:02:36,180
alocare cu malloc, am
poate pune aceste piese împreună

47
00:02:36,180 --> 00:02:40,960
Pentru a crea un date structure-- o
Lista am putea say-- legate individual

48
00:02:40,960 --> 00:02:45,400
care ne permite să crească și
micsora o colecție de valori

49
00:02:45,400 --> 00:02:48,800
și nu vom avea nici un spațiu irosit.

50
00:02:48,800 --> 00:02:53,320
>> Deci, din nou, noi numim această idee,
această noțiune, o listă legată.

51
00:02:53,320 --> 00:02:56,320
În special, în acest film suntem
vorbind despre lista individual legate,

52
00:02:56,320 --> 00:02:59,185
și apoi un alt videoclip vom vorbi
liste despre legate de dublu, care

53
00:02:59,185 --> 00:03:01,560
este doar o variatie pe o temă aici.

54
00:03:01,560 --> 00:03:05,200
Dar o listă individual legat
este format din noduri,

55
00:03:05,200 --> 00:03:08,559
noduri doar fiind un term-- abstract
e doar ceva ce sun

56
00:03:08,559 --> 00:03:10,350
asta e un fel de
structura, practic, eu sunt?

57
00:03:10,350 --> 00:03:16,190
Doar de gând să-l numesc un node-- și acest
nod are doi membri, sau două domenii.

58
00:03:16,190 --> 00:03:20,300
Are date, de obicei o
întreg, un float caracter,

59
00:03:20,300 --> 00:03:23,790
sau ar putea fi un alt tip de date
care le-ați definit cu un def tip.

60
00:03:23,790 --> 00:03:29,290
Și conține un pointer la
un alt nod de același tip.

61
00:03:29,290 --> 00:03:34,710
>> Deci avem două lucruri în interiorul
acest nod, date și un pointer

62
00:03:34,710 --> 00:03:36,380
la un alt nod.

63
00:03:36,380 --> 00:03:39,370
Și dacă începe să vizualizeze
aceasta, vă puteți gândi la asta

64
00:03:39,370 --> 00:03:42,280
ca un lanț de noduri care
sunt conectate împreună.

65
00:03:42,280 --> 00:03:45,070
Avem primul nod, ea
conține date, și un pointer

66
00:03:45,070 --> 00:03:49,110
la al doilea nod, care conține
date, și un pointer la nodul treia.

67
00:03:49,110 --> 00:03:52,940
Și așa de aceea l-am o numim
Lista legate, acestea sunt legate între ele.

68
00:03:52,940 --> 00:03:56,070
>> Ce face acest lucru special
Structura nod arata ca?

69
00:03:56,070 --> 00:04:01,120
Ei bine, dacă vă amintiți de la videoclipul nostru pe
definirea tipuri personalizate, cu tipul de def,

70
00:04:01,120 --> 00:04:05,400
putem defini o structure-- și
tip defini o structură de genul asta.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, și apoi eu sunt
utilizând valoarea cuvântul aici arbitrar

72
00:04:11,240 --> 00:04:13,891
pentru a indica orice tip de date într-adevăr.

73
00:04:13,891 --> 00:04:16,890
Ai putea trece pe un număr întreg sau float,
ai putea avea orice vrei.

74
00:04:16,890 --> 00:04:19,389
Nu este limitat la doar
întregi, sau ceva de genul asta.

75
00:04:19,389 --> 00:04:22,790
Deci valoare nu este doar un arbitrară
tip de date, și apoi un pointer

76
00:04:22,790 --> 00:04:26,310
la un alt nod de același tip.

77
00:04:26,310 --> 00:04:29,690
>> Acum, există un pic de captură
aici cu definirea unei structuri

78
00:04:29,690 --> 00:04:33,030
atunci când este o structură de sine referențială.

79
00:04:33,030 --> 00:04:35,340
Trebuie să am o temporar
nume pentru structura mea.

80
00:04:35,340 --> 00:04:37,640
La sfârșitul zilei I
doresc în mod clar să-l numesc

81
00:04:37,640 --> 00:04:43,030
nod SLL, asta e în cele din urmă noul
Nume componentă de definire mea tip,

82
00:04:43,030 --> 00:04:47,450
dar nu pot folosi nod SLL
în mijlocul acestei.

83
00:04:47,450 --> 00:04:51,430
Motivul fiind, nu am
a creat un nod de tip SLL numit

84
00:04:51,430 --> 00:04:55,200
până când am lovit acest ultim punct aici.

85
00:04:55,200 --> 00:04:59,720
Până în acel moment, trebuie să aibă
un alt mod de a face referire la acest tip de date.

86
00:04:59,720 --> 00:05:02,440
>> Și aceasta este o auto
tip de date referențială.

87
00:05:02,440 --> 00:05:06,314
Acesta, e un tip de date de o
structură care conține o de date,

88
00:05:06,314 --> 00:05:08,480
și un pointer la un alt
Structura de același tip.

89
00:05:08,480 --> 00:05:11,750
Așa că am nevoie pentru a putea să se refere la
acest tip de date, cel puțin temporar,

90
00:05:11,750 --> 00:05:14,910
asa ca da o temporar
Numele de struct sllist

91
00:05:14,910 --> 00:05:18,540
îmi permite să spun, atunci vreau o
pointer la un alt sllist struct,

92
00:05:18,540 --> 00:05:24,690
o stea struct sllist, și apoi
după ce am terminat definirea,

93
00:05:24,690 --> 00:05:27,220
Eu pot apela acum acest tip de un nod SLL.

94
00:05:27,220 --> 00:05:30,520
>> Deci, de aceea ai vedea acolo
un nume temporar aici,

95
00:05:30,520 --> 00:05:31,879
dar un nume permanent aici.

96
00:05:31,879 --> 00:05:33,920
Uneori s-ar putea vedea
definiții ale structurii,

97
00:05:33,920 --> 00:05:36,570
de exemplu, că nu sunt
autoreferențiale, că

98
00:05:36,570 --> 00:05:39,390
Nu au un nume specificator aici.

99
00:05:39,390 --> 00:05:43,040
S-ar spune doar typedef struct,
deschide bretele cret si apoi defini.

100
00:05:43,040 --> 00:05:45,620
Dar daca esti struct este de la sine
referențial, așa cum aceasta este,

101
00:05:45,620 --> 00:05:49,010
trebuie să specificați o
nume de tip temporar.

102
00:05:49,010 --> 00:05:51,310
Dar în cele din urmă, acum
că am făcut acest lucru,

103
00:05:51,310 --> 00:05:53,620
ne putem referi doar pentru a
aceste noduri, aceste unități,

104
00:05:53,620 --> 00:05:57,900
ca noduri SLL scopuri
de restul acestui film.

105
00:05:57,900 --> 00:06:00,900
>> În regulă, deci știm cum să
crea un nod listă legată.

106
00:06:00,900 --> 00:06:03,240
Știm cum să se definească
o listă nod conectat.

107
00:06:03,240 --> 00:06:06,670
Acum, dacă vom începe
folosindu-le pentru a colecta informații,

108
00:06:06,670 --> 00:06:10,360
există o serie de operațiuni noi
trebuie să înțeleagă și să lucreze cu.

109
00:06:10,360 --> 00:06:12,860
Trebuie să știm cum să creați
o listă legată din aer subțire.

110
00:06:12,860 --> 00:06:14,901
Dacă nu există nici o listă deja,
vrem să înceapă o.

111
00:06:14,901 --> 00:06:16,960
Deci, avem nevoie pentru a putea
pentru a crea o listă legată,

112
00:06:16,960 --> 00:06:19,130
avem nevoie pentru a căuta, probabil,
prin lista de link-ul

113
00:06:19,130 --> 00:06:21,830
pentru a găsi un element căutăm.

114
00:06:21,830 --> 00:06:24,430
Avem nevoie pentru a putea insera
lucruri noi in lista,

115
00:06:24,430 --> 00:06:25,930
vrem lista noastră să fie în măsură să crească.

116
00:06:25,930 --> 00:06:28,638
Și în mod similar, vrem să fie în măsură
pentru a șterge lucruri din lista noastră,

117
00:06:28,638 --> 00:06:30,250
vrem lista noastră să fie în măsură să se micșoreze.

118
00:06:30,250 --> 00:06:32,160
Și la sfârșitul nostru
programe, în special

119
00:06:32,160 --> 00:06:34,550
dacă vă reamintesc că suntem
alocarea dinamică de memorie

120
00:06:34,550 --> 00:06:38,337
pentru a construi aceste liste de obicei,
vrem pentru a elibera toate că memoria

121
00:06:38,337 --> 00:06:39,670
când am terminat de lucru cu ea.

122
00:06:39,670 --> 00:06:44,627
Și așa trebuie să fie în măsură pentru a șterge o
întreaga listă legate într-o singură lovitură nu.

123
00:06:44,627 --> 00:06:46,460
Deci, haideți să mergem prin
unele dintre aceste operațiuni

124
00:06:46,460 --> 00:06:51,192
si cum am putea le vizualiza,
vorbind în codul pseudocod specific.

125
00:06:51,192 --> 00:06:53,150
Deci, ne-o dorim pentru a crea un
Lista legate, asa ca poate ne

126
00:06:53,150 --> 00:06:56,480
doriți să definiți o funcție
cu acest prototip.

127
00:06:56,480 --> 00:07:01,690
SLL stele nod, de a crea, și eu care trece
într-un singur argument, unele date arbitrare

128
00:07:01,690 --> 00:07:05,530
introduceți din nou, de un anumit tip de date arbitrare.

129
00:07:05,530 --> 00:07:10,482
Dar eu sunt returning-- această funcție ar trebui să
întoarcă la mine un pointer, pentru un individual

130
00:07:10,482 --> 00:07:11,190
Lista legate nod.

131
00:07:11,190 --> 00:07:14,050
Din nou, noi încercăm să creeze
o listă legată din aer subțire,

132
00:07:14,050 --> 00:07:17,900
asa ca am nevoie de un pointer la
această listă, atunci când am terminat.

133
00:07:17,900 --> 00:07:19,420
>> Deci, ce sunt etapele implicate aici?

134
00:07:19,420 --> 00:07:20,960
Ei bine, primul lucru sunt
de gând să faci este dinamic

135
00:07:20,960 --> 00:07:22,550
aloca spațiu pentru un nou nod.

136
00:07:22,550 --> 00:07:26,689
Din nou, suntem o crearea de subțire
aer, așa că trebuie să spațiu malloc pentru ea.

137
00:07:26,689 --> 00:07:28,480
Și, desigur, imediat
după ce am malloc,

138
00:07:28,480 --> 00:07:31,692
vom verifica întotdeauna să ne asigurăm că ne
pointer-- nu am reveni nul.

139
00:07:31,692 --> 00:07:33,650
Pentru că dacă vom încerca și
deferență un pointer nul,

140
00:07:33,650 --> 00:07:36,190
vom suferi o
segfault si nu vrem asta.

141
00:07:36,190 --> 00:07:39,510
>> Apoi ne-am dori să completați câmpul,
dorim pentru a inițializa câmpul valoric

142
00:07:39,510 --> 00:07:41,690
și inițializa câmpul următor.

143
00:07:41,690 --> 00:07:45,450
Și apoi ne-o dorim în cele din urmă ca sa--
Funcția prototip indicates-- vrem

144
00:07:45,450 --> 00:07:49,940
pentru a reveni un pointer la un nod SLL.

145
00:07:49,940 --> 00:07:51,710
Deci, ce face acest arata vizual?

146
00:07:51,710 --> 00:07:55,230
Ei bine, în primul rând vom dinamic
aloca spațiu pentru un nou nod SLL,

147
00:07:55,230 --> 00:07:58,320
asa ca am malloc-- asta e
o reprezentare vizuală

148
00:07:58,320 --> 00:08:00,020
din nodul tocmai am creat.

149
00:08:00,020 --> 00:08:02,757
Si vom verifica pentru a vă asigura
nu este null-- în acest caz,

150
00:08:02,757 --> 00:08:04,840
imaginea nu ar avea
apărut în cazul în care a fost nul,

151
00:08:04,840 --> 00:08:07,298
ne-ar fi rămas fără memorie,
asa ca suntem bine să plec acolo.

152
00:08:07,298 --> 00:08:10,200
Deci, acum suntem la pasul C,
inițializa câmpul valoare noduri.

153
00:08:10,200 --> 00:08:12,280
Ei bine, pe baza această funcție
apel Sunt folosind aici,

154
00:08:12,280 --> 00:08:16,700
arata ca vreau sa trec la 6,
așa că vom 6 în câmpul valoric.

155
00:08:16,700 --> 00:08:18,865
Acum, inițializa câmpul următor.

156
00:08:18,865 --> 00:08:21,640
Ei bine, ce am de gând să fac acolo,
nu este nimic următoare, dreapta,

157
00:08:21,640 --> 00:08:23,600
acesta este singurul lucru pe listă.

158
00:08:23,600 --> 00:08:27,206
Deci, ce e următorul lucru pe lista?

159
00:08:27,206 --> 00:08:29,660
>> Nu ar trebui să punct la nimic, chiar.

160
00:08:29,660 --> 00:08:33,600
Nu e nimic altceva acolo, astfel încât ceea ce este
conceptul știm de care este nothing--

161
00:08:33,600 --> 00:08:35,638
indicii la nimic?

162
00:08:35,638 --> 00:08:37,929
Ar trebui să fie, poate, ne-o dorim
pentru a pune un pointer nul acolo,

163
00:08:37,929 --> 00:08:40,178
și voi reprezintă nul
pointer ca doar o cutie roșie,

164
00:08:40,178 --> 00:08:41,559
nu putem merge mai departe.

165
00:08:41,559 --> 00:08:44,430
După cum vom vedea un pic mai târziu,
vom avea în cele din urmă lanturi

166
00:08:44,430 --> 00:08:46,330
de săgeți de conectare
aceste noduri împreună,

167
00:08:46,330 --> 00:08:48,480
dar atunci când a lovit
casetă roșie, care este nul,

168
00:08:48,480 --> 00:08:51,150
nu putem merge mai departe,
asta e sfârșitul listei.

169
00:08:51,150 --> 00:08:53,960
>> Și, în fine, vrem doar să
reveni un pointer la acest nod.

170
00:08:53,960 --> 00:08:56,160
Deci, vom numi noi,
și va reveni noi

171
00:08:56,160 --> 00:08:59,370
astfel încât să poată fi utilizate în
indiferent de funcția a creat.

172
00:08:59,370 --> 00:09:03,100
Deci nu vom merge, Am creat un individual
Lista nod legat din aer subțire,

173
00:09:03,100 --> 00:09:05,920
iar acum avem o listă, putem lucra cu.

174
00:09:05,920 --> 00:09:08,260
>> Acum, să spunem că am deja
au un lanț mare,

175
00:09:08,260 --> 00:09:09,800
și vrem să găsim ceva în ea.

176
00:09:09,800 --> 00:09:12,716
Și dorim o functie care va
pentru a reveni adevărat sau fals, în funcție

177
00:09:12,716 --> 00:09:15,840
dacă o valoare există în această listă.

178
00:09:15,840 --> 00:09:18,160
Un prototip funcție, sau
declarație pentru această funcție,

179
00:09:18,160 --> 00:09:23,320
ar putea arata ca astea-- bool găsi, și
apoi ne-o dorim pentru a trece în două argumente.

180
00:09:23,320 --> 00:09:26,996
>> Primul, este un pointer la
primul element al listei de legătura.

181
00:09:26,996 --> 00:09:29,620
Aceasta este de fapt ceva ce vei
dori întotdeauna pentru a urmări,

182
00:09:29,620 --> 00:09:33,110
și de fapt ar putea fi ceva care
tine chiar pus într-o variabilă globală.

183
00:09:33,110 --> 00:09:35,360
După ce ați creat o listă,
tu mereu, mereu

184
00:09:35,360 --> 00:09:38,990
doresc pentru a urmări de foarte
Primul element al listei.

185
00:09:38,990 --> 00:09:43,690
În acest fel puteți face referire la toate celelalte
Elemente de doar după lanțul,

186
00:09:43,690 --> 00:09:47,300
fără a fi nevoie de a păstra pointeri
intact la fiecare singur element.

187
00:09:47,300 --> 00:09:50,920
Trebuie doar pentru a ține evidența primul
o în cazul în care acestea sunt toate legate împreună.

188
00:09:50,920 --> 00:09:52,460
>> Și apoi al doilea lucru
suntem trece din nou

189
00:09:52,460 --> 00:09:54,376
este some-- arbitrar
indiferent de tipul de date suntem

190
00:09:54,376 --> 00:09:59,640
cauta există în interiorul
sperăm unul dintre nodurile din lista.

191
00:09:59,640 --> 00:10:00,980
Deci, care sunt pașii?

192
00:10:00,980 --> 00:10:04,250
Ei bine, primul lucru pe care îl facem este
vom crea un pointer transversal

193
00:10:04,250 --> 00:10:06,015
arătând spre capul liste.

194
00:10:06,015 --> 00:10:08,890
Ei bine, de ce facem asta, deja
au un pointer la cap liste,

195
00:10:08,890 --> 00:10:10,974
de ce nu ne mișcăm doar că unul pe aici?

196
00:10:10,974 --> 00:10:13,140
Ei bine, cum am spus doar,
este foarte important pentru noi

197
00:10:13,140 --> 00:10:17,580
pentru a ține întotdeauna evidența
foarte primul element din listă.

198
00:10:17,580 --> 00:10:21,270
Și așa e de fapt mai bine
pentru a crea un duplicat de care,

199
00:10:21,270 --> 00:10:25,350
și de a folosi că pentru a muta în jurul valorii de așa că nu
muta accidental departe, sau ne-am mereu

200
00:10:25,350 --> 00:10:30,430
au un pointer la un moment dat, care este
chiar pe primul element al listei.

201
00:10:30,430 --> 00:10:33,290
Deci, este mai bine pentru a crea un
al doilea pe care le folosim pentru a muta.

202
00:10:33,290 --> 00:10:35,877
>> Apoi, ne-am compara dacă
câmpul valoare la acel nod

203
00:10:35,877 --> 00:10:38,960
este ceea ce căutați, și, dacă este
nu, vom trece doar la nodul următor.

204
00:10:38,960 --> 00:10:41,040
Și noi continuăm să facem asta
peste și peste și peste,

205
00:10:41,040 --> 00:10:44,811
până când vom găsi fie
elementul, sau am lovit

206
00:10:44,811 --> 00:10:47,310
null-- am ajuns la sfârșitul
listei și nu este acolo.

207
00:10:47,310 --> 00:10:50,540
Acest lucru ar trebui să sperăm sune un clopot
pentru tine, ca doar de căutare liniară,

208
00:10:50,540 --> 00:10:54,430
suntem doar replicare în
o structură listă individual legat

209
00:10:54,430 --> 00:10:56,280
loc de a folosi o matrice a face acest lucru.

210
00:10:56,280 --> 00:10:58,210
>> Deci, aici e un exemplu de
o listă individual legat.

211
00:10:58,210 --> 00:11:00,043
Acesta este format din
cinci noduri, și ne-am

212
00:11:00,043 --> 00:11:04,330
un pointer la șefului
Lista, care se numește listă.

213
00:11:04,330 --> 00:11:07,385
Primul lucru pe care doriți să faceți este
din nou, a crea acel pointer traversarea.

214
00:11:07,385 --> 00:11:09,760
Deci, acum avem două indicii
acest punct de același lucru.

215
00:11:09,760 --> 00:11:15,025
>> Acum, observați aici, de asemenea,, nu am
Trebuie să malloc orice spațiu pentru Trav.

216
00:11:15,025 --> 00:11:18,970
Nu am spus trav egal malloc
ceva, acel nod există deja,

217
00:11:18,970 --> 00:11:21,160
acest spațiu în memorie există deja.

218
00:11:21,160 --> 00:11:24,290
Deci, tot eu sunt de fapt face este
crearea de un alt pointer la ea.

219
00:11:24,290 --> 00:11:28,210
Nu mă mallocing o suplimentare
spațiu, trebuie doar acum două indicii

220
00:11:28,210 --> 00:11:31,370
arătând spre același lucru.

221
00:11:31,370 --> 00:11:33,710
>> Deci, este de 2 ceea ce caut?

222
00:11:33,710 --> 00:11:37,220
Ei bine, nu, astfel încât în ​​loc eu sunt
va trece la următorul.

223
00:11:37,220 --> 00:11:41,740
Deci, practic, aș spune,
trav Trav egal următor.

224
00:11:41,740 --> 00:11:43,630
Este de 3 ceea ce caut, nr.

225
00:11:43,630 --> 00:11:45,780
Așa că am continua să meargă
prin, în cele din urmă până la

226
00:11:45,780 --> 00:11:48,690
ajunge la 6, care este ceea ce caut
pentru bazate pe apelul funcției

227
00:11:48,690 --> 00:11:51,600
Am la partea de sus
acolo, și așa am terminat.

228
00:11:51,600 --> 00:11:54,150
>> Acum, ce se întâmplă dacă elementul sunt
căutați nu este în listă,

229
00:11:54,150 --> 00:11:55,510
este încă de gând să lucreze?

230
00:11:55,510 --> 00:11:57,120
Ei bine, observați că lista
aici este subtil diferit,

231
00:11:57,120 --> 00:11:59,410
și acest lucru este un alt lucru care este
important, cu liste legate,

232
00:11:59,410 --> 00:12:01,780
nu trebuie să păstreze
le în orice ordine special.

233
00:12:01,780 --> 00:12:05,390
Puteți, dacă doriți, dar
este posibil să fi observat deja

234
00:12:05,390 --> 00:12:09,310
că nu suntem urmărirea
ce element de numărul suntem la.

235
00:12:09,310 --> 00:12:13,150
>> Și asta e un fel de un comerț pe care le
au cu lista legate versuri tablouri,

236
00:12:13,150 --> 00:12:15,300
este că nu avem
mai cu acces aleator.

237
00:12:15,300 --> 00:12:18,150
Nu putem spune doar, vreau
pentru a merge la elementul 0th,

238
00:12:18,150 --> 00:12:21,410
sau elementul de matrice a 6-mea,
care pot face într-o matrice.

239
00:12:21,410 --> 00:12:25,080
Nu pot să spun că vreau să merg la
Element 0th, sau 6a elementul,

240
00:12:25,080 --> 00:12:30,360
sau elementul 25 lista mea legată,
nu exista nici index asociate cu acestea.

241
00:12:30,360 --> 00:12:33,660
Și așa nu contează cu adevărat
dacă ne-am păstra lista noastră în ordine.

242
00:12:33,660 --> 00:12:36,080
Dacă doriți să vă
cu siguranță pot, dar nu e

243
00:12:36,080 --> 00:12:38,567
nici un motiv pentru care au nevoie pentru a
fi păstrate în orice ordine.

244
00:12:38,567 --> 00:12:40,400
Deci, din nou, să încercăm și
găsi 6 în această listă.

245
00:12:40,400 --> 00:12:43,200
Ei bine, vom începe de la
începând, nu găsim 6,

246
00:12:43,200 --> 00:12:47,690
si atunci nu continua găsirea
6, până când vom ajunge în cele din urmă aici.

247
00:12:47,690 --> 00:12:52,790
Deci, chiar de puncte acum trav la nodul
conținând 8, iar șase nu este acolo.

248
00:12:52,790 --> 00:12:55,250
>> Deci, urmatorul pas ar fi
pentru a merge la indicatorul următor,

249
00:12:55,250 --> 00:12:57,440
așa spun trav Trav egal următor.

250
00:12:57,440 --> 00:13:00,750
Ei bine, trav viitoare, indicat de
caseta de culoare roșie nu, este nul.

251
00:13:00,750 --> 00:13:03,020
Deci nu e nicăieri în altă parte a
du-te, și așa mai departe în acest moment

252
00:13:03,020 --> 00:13:06,120
putem concluziona că am ajuns
sfârșitul listei de legătura,

253
00:13:06,120 --> 00:13:07,190
și 6 nu este acolo.

254
00:13:07,190 --> 00:13:10,980
Și ar fi returnat
fals în acest caz.

255
00:13:10,980 --> 00:13:14,540
>> OK, cum putem introduce o nouă
nod în lista legat?

256
00:13:14,540 --> 00:13:17,310
Deci am fost capabili de a crea
o listă legată de nicăieri,

257
00:13:17,310 --> 00:13:19,370
dar, probabil, vrem să
construi un lanț și nu

258
00:13:19,370 --> 00:13:22,620
a crea o grămadă de liste distincte.

259
00:13:22,620 --> 00:13:25,700
Vrem să avem o listă care
are o grămadă de noduri în ea,

260
00:13:25,700 --> 00:13:28,040
nu o grămadă de liste cu un singur nod.

261
00:13:28,040 --> 00:13:31,260
Deci, nu putem ține folosind Creare
Funcția am definit mai devreme, acum ne

262
00:13:31,260 --> 00:13:33,860
doriți să inserați într-un
Lista care există deja.

263
00:13:33,860 --> 00:13:36,499
>> Deci acest caz, vom
pentru a trece în două argumente,

264
00:13:36,499 --> 00:13:39,290
indicatorul la cap de care
Lista pe care ne-o dorim pentru a adăuga la legat.

265
00:13:39,290 --> 00:13:40,910
Din nou, de aceea este atât de
important ca noi mereu

266
00:13:40,910 --> 00:13:43,400
urmări, pentru că
e singurul mod cu adevarat

267
00:13:43,400 --> 00:13:46,690
trebuie să se refere la întreaga listă este
doar de un pointer la primul element.

268
00:13:46,690 --> 00:13:49,360
Deci, vrem să treacă într-o
pointer la care prim element,

269
00:13:49,360 --> 00:13:52,226
si indiferent de valoarea am
doriți să adăugați la lista.

270
00:13:52,226 --> 00:13:54,600
Și, eventual, această funcție
este de gând să se întoarcă un pointer

271
00:13:54,600 --> 00:13:57,980
la noul șef al unei liste legate.

272
00:13:57,980 --> 00:13:59,700
>> Care sunt etapele implicate aici?

273
00:13:59,700 --> 00:14:02,249
Ei bine, la fel ca și cu crearea,
avem nevoie pentru a aloca dinamic

274
00:14:02,249 --> 00:14:05,540
spațiu pentru un nou nod, și verificați pentru a face
sigur că nu a alerga afară de memorie, din nou,

275
00:14:05,540 --> 00:14:07,150
pentru că suntem folosind malloc.

276
00:14:07,150 --> 00:14:09,080
Apoi, ne-o dorim pentru a popula
și introduceți nodul,

277
00:14:09,080 --> 00:14:12,730
asa ca pune numărul, indiferent de
val este, în nodul.

278
00:14:12,730 --> 00:14:17,310
Vrem să introduceți nodul la
începutul listei de legătura.

279
00:14:17,310 --> 00:14:19,619
>> Exista un motiv pentru care am
vreau să fac asta, și

280
00:14:19,619 --> 00:14:21,910
ar putea fi în valoare de a lua un al doilea
pentru a întrerupe videoclipul aici,

281
00:14:21,910 --> 00:14:25,860
și cred că de ce aș vrea să
introduce la începutul unui legat

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

283
00:14:26,589 --> 00:14:28,630
Din nou, am menționat mai devreme
că aceasta nu prea

284
00:14:28,630 --> 00:14:33,020
contează dacă am păstra în orice
ordine, astfel poate că e un indiciu.

285
00:14:33,020 --> 00:14:36,040
Și ai văzut ce se va întâmpla dacă am
a vrut sa-- sau de la doar o secundă

286
00:14:36,040 --> 00:14:37,360
Acum, când am fost de gând
prin căutare vă

287
00:14:37,360 --> 00:14:39,235
ar putea vedea ce s-ar putea
întâmpla dacă am încercat

288
00:14:39,235 --> 00:14:41,330
pentru a insera la sfârșitul listei.

289
00:14:41,330 --> 00:14:44,750
Pentru ca nu avem o
pointer la sfârșitul listei.

290
00:14:44,750 --> 00:14:47,490
>> Deci motivul pentru care mi-aș dori
pentru a insera la început,

291
00:14:47,490 --> 00:14:49,380
este pentru că eu pot face imediat.

292
00:14:49,380 --> 00:14:52,730
Am un pointer la început, și
vom vedea acest lucru într-un vizual într-o secundă.

293
00:14:52,730 --> 00:14:55,605
Dar dacă vreau să insera la sfârșitul anului,
Trebuie să începem cu începutul,

294
00:14:55,605 --> 00:14:58,760
traversa tot drumul la
scop, și apoi tac pe.

295
00:14:58,760 --> 00:15:01,420
Deci aceasta ar însemna că
inserarea la sfârșitul listei

296
00:15:01,420 --> 00:15:04,140
ar deveni un o de n
funcționare, merge înapoi

297
00:15:04,140 --> 00:15:06,720
la discuția noastră de
complexitate de calcul.

298
00:15:06,720 --> 00:15:10,140
Ar deveni un o operație de n, în cazul în care
ca lista sa mărit, și mai mare,

299
00:15:10,140 --> 00:15:13,310
și mai mare, acesta va deveni mai mult și
mai dificil de tac ceva

300
00:15:13,310 --> 00:15:14,661
pe la sfârșitul anului.

301
00:15:14,661 --> 00:15:17,410
Dar este întotdeauna foarte ușor de
tac ceva pe la început,

302
00:15:17,410 --> 00:15:19,060
esti mereu la început.

303
00:15:19,060 --> 00:15:21,620
>> Și vom vedea o vizuală a acestui nou.

304
00:15:21,620 --> 00:15:24,100
Și apoi o dată am terminat, o dată
am introdus noul nod,

305
00:15:24,100 --> 00:15:26,880
vrem să se întoarcă la indicatorul nostru
noul șef al unei liste legate, care

306
00:15:26,880 --> 00:15:29,213
deoarece suntem introducerea la
incepand, va fi de fapt

307
00:15:29,213 --> 00:15:31,060
un pointer la nodul ne-am creat.

308
00:15:31,060 --> 00:15:33,280
Să vizualiza acest lucru,
pentru că eu cred că va ajuta.

309
00:15:33,280 --> 00:15:36,661
>> Deci, aici e lista noastra, este alcătuită din
patru elemente, un nod care conține 15,

310
00:15:36,661 --> 00:15:38,410
ceea ce indică un nod
conținând 9, care

311
00:15:38,410 --> 00:15:41,370
indică un nod conține 13,
ceea ce indică un nod care conține

312
00:15:41,370 --> 00:15:44,840
10, care are nulul
pointer ca următoarea pointer

313
00:15:44,840 --> 00:15:47,010
astfel că la scos din lista.

314
00:15:47,010 --> 00:15:50,200
Deci, vrem să inserați un
nod nou cu valoarea de 12

315
00:15:50,200 --> 00:15:52,720
la începutul acestui
Lista, ce facem?

316
00:15:52,720 --> 00:15:58,770
Ei bine, în primul rând ne-am malloc spațiu pentru
nod, și apoi am pus 12 acolo.

317
00:15:58,770 --> 00:16:02,211
>> Deci, acum am ajuns la un ne-
punctul de decizie, nu?

318
00:16:02,211 --> 00:16:03,960
Avem un cuplu de
indicii care am putea

319
00:16:03,960 --> 00:16:06,770
muta, care ar trebui să ne mutăm mai întâi?

320
00:16:06,770 --> 00:16:09,250
Ar trebui să facem 12 puncte la
noul șef al list--

321
00:16:09,250 --> 00:16:13,020
sau scuză-mă, trebuie să facem 12
punctul la cap vechi listei?

322
00:16:13,020 --> 00:16:15,319
Sau ar trebui să spunem că
Lista acum începe la 12.

323
00:16:15,319 --> 00:16:17,110
Există o distincție
acolo, si ne vom uita

324
00:16:17,110 --> 00:16:19,870
la ce se întâmplă cu atât într-o secundă.

325
00:16:19,870 --> 00:16:23,350
>> Dar aceasta duce la o
mare subiect de bara laterală,

326
00:16:23,350 --> 00:16:26,280
care este faptul că una dintre cele
dificile lucruri cu liste legate

327
00:16:26,280 --> 00:16:30,980
este de a asigura indicii
în ordinea corectă.

328
00:16:30,980 --> 00:16:34,520
Dacă mutați lucrurile de ordine,
puteți ajunge accidental

329
00:16:34,520 --> 00:16:36,050
orphaning restul listei.

330
00:16:36,050 --> 00:16:37,300
Și aici este un exemplu de acest lucru.

331
00:16:37,300 --> 00:16:40,540
Deci, să mergem cu ideea de--
Ei bine, tocmai am creat 12.

332
00:16:40,540 --> 00:16:43,180
Știm 12 va fi
noul șef al listei,

333
00:16:43,180 --> 00:16:47,660
și așa că de ce să nu ne-am muta
Lista indicatorul la punctul acolo.

334
00:16:47,660 --> 00:16:49,070
>> OK, așa că e bine.

335
00:16:49,070 --> 00:16:51,560
Deci, acum cazul în care nu 12 Următorul punct?

336
00:16:51,560 --> 00:16:54,580
Adică, vizual putem vedea
că va indica 15,

337
00:16:54,580 --> 00:16:57,250
ca oameni este foarte evident pentru noi.

338
00:16:57,250 --> 00:17:00,300
Cum știe computer?

339
00:17:00,300 --> 00:17:02,720
Noi nu avem nimic
mai indică spre 15, nu?

340
00:17:02,720 --> 00:17:05,869
>> Am pierdut orice capacitate de a se referă la 15.

341
00:17:05,869 --> 00:17:11,460
Nu putem spune noi săgeata de lângă egali
ceva, nu e nimic acolo.

342
00:17:11,460 --> 00:17:13,510
De fapt, ne-am orfani
restul listei

343
00:17:13,510 --> 00:17:16,465
de a face acest lucru, ne-am
rupt accidental lanțul.

344
00:17:16,465 --> 00:17:18,089
Și cu siguranță nu vreau să fac asta.

345
00:17:18,089 --> 00:17:20,000
>> Deci, să ne întoarcem și să încercați din nou.

346
00:17:20,000 --> 00:17:24,060
Poate că ceea ce trebuie să facă
este de a stabili 12 de pe lângă indicatorul

347
00:17:24,060 --> 00:17:28,290
la vechiul cap al listei prima,
atunci ne putem muta în lista de peste.

348
00:17:28,290 --> 00:17:30,420
Și, de fapt, că este
ordinea corectă pe care le

349
00:17:30,420 --> 00:17:32,836
trebuie să urmați atunci când suntem
de lucru cu lista individual legat.

350
00:17:32,836 --> 00:17:36,460
Noi mereu doriți să conectați
element nou în listă,

351
00:17:36,460 --> 00:17:41,010
înainte vom lua acest tip de
pas important de schimbare

352
00:17:41,010 --> 00:17:43,360
în cazul în care capul listei legat este.

353
00:17:43,360 --> 00:17:46,740
Din nou, asta e un lucru fundamental,
nu vrem să-și piardă urmări de ea.

354
00:17:46,740 --> 00:17:49,310
>> Deci, vrem să ne asigurăm că
totul este legat împreună,

355
00:17:49,310 --> 00:17:52,040
înainte de a ne muta ca pointer.

356
00:17:52,040 --> 00:17:55,300
Și așa ar fi ordinea corectă,
care urmează să se conecteze 12 la lista,

357
00:17:55,300 --> 00:17:57,630
apoi spune că lista începe un 12.

358
00:17:57,630 --> 00:18:00,860
Dacă am declarat că lista incepe de la 12 si
apoi a încercat să se conecteze 12 la lista,

359
00:18:00,860 --> 00:18:02,193
am văzut deja ce se întâmplă.

360
00:18:02,193 --> 00:18:04,920
Pierdem lista din greșeală.

361
00:18:04,920 --> 00:18:06,740
>> OK, cu atât mai mult un lucru pentru a vorbi despre.

362
00:18:06,740 --> 00:18:09,750
Ce se întâmplă dacă vrem să scăpăm de
un întreg listă de legat la o dată?

363
00:18:09,750 --> 00:18:11,750
Din nou, suntem mallocing
toate acest spațiu, și așa ne-am

364
00:18:11,750 --> 00:18:13,351
Trebuie să-l elibereze, atunci când am terminat.

365
00:18:13,351 --> 00:18:15,350
Deci, acum vrem să ștergeți
întreaga listă legată.

366
00:18:15,350 --> 00:18:16,850
Ei bine, ce vrem sa facem?

367
00:18:16,850 --> 00:18:20,460
>> Dacă am ajuns la indicatorul nul, am
vrea să se oprească, în caz contrar, ștergeți doar

368
00:18:20,460 --> 00:18:23,420
restul de listă și apoi mă eliberezi.

369
00:18:23,420 --> 00:18:28,890
Ștergeți restul listei,
și apoi elibera nodul curent.

370
00:18:28,890 --> 00:18:32,850
Ce face asta suna ca,
ce tehnica au am vorbit

371
00:18:32,850 --> 00:18:35,440
nu despre anterior ca suna ca?

372
00:18:35,440 --> 00:18:39,560
Șterge toată lumea, atunci
întoarce și șterge-mă.

373
00:18:39,560 --> 00:18:42,380
>> Asta e recursivitate, am facut
problemă un pic mai mic,

374
00:18:42,380 --> 00:18:46,910
ce spunem șterge toată lumea
altceva, atunci poți să-mi șterge.

375
00:18:46,910 --> 00:18:50,940
Și mai departe pe drum, acel nod
va spune, șterge toată lumea.

376
00:18:50,940 --> 00:18:53,940
Dar în cele din urmă vom ajunge la
punct în care lista este nul,

377
00:18:53,940 --> 00:18:55,310
și asta e cazul nostru de bază.

378
00:18:55,310 --> 00:18:57,010
>> Deci, haideți să aruncăm o privire la acest lucru,
și modul în care acest lucru ar putea să funcționeze.

379
00:18:57,010 --> 00:18:59,759
Deci, aici e lista noastra, e la fel
lista vorbeam despre,

380
00:18:59,759 --> 00:19:00,980
și nu există trepte.

381
00:19:00,980 --> 00:19:04,200
Există o mulțime de text aici, dar
sperăm vizualizarea va ajuta.

382
00:19:04,200 --> 00:19:08,557
>> Asa ca am have-- și, de asemenea, am tras
up cadre stiva nostru ilustrare

383
00:19:08,557 --> 00:19:10,890
din videoclipul nostru pe stive de apel,
și sperăm că toate acestea

384
00:19:10,890 --> 00:19:13,260
împreună vă va arăta ceea ce se întâmplă.

385
00:19:13,260 --> 00:19:14,510
Deci, aici e codul nostru pseudocod.

386
00:19:14,510 --> 00:19:17,830
Dacă vom ajunge la un nul
pointer, opri, în caz contrar,

387
00:19:17,830 --> 00:19:21,320
șterge restul listei,
apoi elibera nodul curent.

388
00:19:21,320 --> 00:19:25,700
Deci, chiar acum, list--
indicatorul care suntem

389
00:19:25,700 --> 00:19:28,410
trecând în a distruge puncte pentru a 12.

390
00:19:28,410 --> 00:19:33,340
12 nu este un pointer nul, deci suntem
merge pentru a șterge restul listei.

391
00:19:33,340 --> 00:19:35,450
>> Ce este ștergerea
restul dintre noi implicat?

392
00:19:35,450 --> 00:19:37,950
Ei bine, aceasta înseamnă a face o
apel pentru a distruge, spunând

393
00:19:37,950 --> 00:19:42,060
că 15 este începutul
restul listei vrem să distrugă.

394
00:19:42,060 --> 00:19:47,480
Și astfel chemarea de a distruge
12 este un fel de în așteptare.

395
00:19:47,480 --> 00:19:52,690
E înghețat acolo, de așteptare pentru
apel pentru a distruge 15, pentru a termina treaba.

396
00:19:52,690 --> 00:19:56,280
>> Ei bine, 15 nu este un pointer nul, și
așa că o să spun, bine,

397
00:19:56,280 --> 00:19:58,450
bine, șterge restul listei.

398
00:19:58,450 --> 00:20:00,760
Restul listei începe
la 9, si asa ca vom doar

399
00:20:00,760 --> 00:20:04,514
așteptați până când ștergeți toate că
chestii, apoi te întorci și șterge-mă.

400
00:20:04,514 --> 00:20:06,680
Ei bine, 9 va spune, bine,
Eu nu sunt un pointer nul,

401
00:20:06,680 --> 00:20:09,020
astfel încât să ștergeți restul lista de aici.

402
00:20:09,020 --> 00:20:11,805
Și așa că încercați și de a distruge 13.

403
00:20:11,805 --> 00:20:15,550
13 spune, eu nu sunt pointer null,
același lucru, trece dolar.

404
00:20:15,550 --> 00:20:17,930
10 nu este pointer nul, 10
conține un pointer nul,

405
00:20:17,930 --> 00:20:20,200
dar 10 nu este un este
null pointer chiar acum,

406
00:20:20,200 --> 00:20:22,470
și așa trece dolar prea.

407
00:20:22,470 --> 00:20:25,560
>> Și acum lista puncte acolo, ea
într-adevăr ar indica some--

408
00:20:25,560 --> 00:20:28,710
dacă am avut mai mult spațiu în imagine,
ar indica un spațiu aleatoare

409
00:20:28,710 --> 00:20:29,960
care nu știm ce este.

410
00:20:29,960 --> 00:20:34,680
Este indicatorul nul, deși, lista
este literalmente acum setat e valori nule.

411
00:20:34,680 --> 00:20:36,820
Este arătând chiar în interiorul cutie roșie.

412
00:20:36,820 --> 00:20:39,960
Am ajuns la un pointer nul, astfel încât
putem opri, și am terminat.

413
00:20:39,960 --> 00:20:46,230
>> Și astfel încât cadru violet este now-- la
Partea de sus a stack-- care este cadrul activ,

414
00:20:46,230 --> 00:20:47,017
dar se face.

415
00:20:47,017 --> 00:20:48,600
Dacă am ajuns un pointer nul, opri.

416
00:20:48,600 --> 00:20:51,290
Noi nu facem nimic, ne-am
nu poate elibera un pointer nul,

417
00:20:51,290 --> 00:20:55,070
nu am nici o malloc
spațiu, și așa am terminat.

418
00:20:55,070 --> 00:20:57,590
Astfel încât cadru funcție
este distrus, iar noi

419
00:20:57,590 --> 00:21:00,930
resume-- ne ridica unde am plecat
off cu următoarea cea mai mare cel care

420
00:21:00,930 --> 00:21:02,807
este acest cadru albastru închis aici.

421
00:21:02,807 --> 00:21:04,390
Așa că am ridica dreapta unde am rămas.

422
00:21:04,390 --> 00:21:06,598
Am eliminat restul
Lista deja, asa ca acum suntem

423
00:21:06,598 --> 00:21:08,000
merge pentru a elibera nodurile curente.

424
00:21:08,000 --> 00:21:12,920
Deci, acum putem elibera acest nod, iar acum
am ajuns la sfârșitul funcției.

425
00:21:12,920 --> 00:21:16,810
Și astfel încât cadru functie este distrus,
si ne-am ridica la cel albastru deschis.

426
00:21:16,810 --> 00:21:20,650
>> Deci, says-- am deja done--
ștergerea restul listei, așa

427
00:21:20,650 --> 00:21:23,140
elibera nodul curent.

428
00:21:23,140 --> 00:21:26,520
Și acum cadrul galben este
din nou pe partea de sus a stivei.

429
00:21:26,520 --> 00:21:29,655
Și așa după cum vedeți, suntem acum
distruge lista de la dreapta la stânga.

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

431
00:21:33,710 --> 00:21:37,280
>> Ce s-ar fi întâmplat, însă,
dacă am fi făcut lucruri în mod greșit?

432
00:21:37,280 --> 00:21:39,410
La fel ca atunci când am încercat
adăugarea unui element.

433
00:21:39,410 --> 00:21:41,909
Dacă ne-am dat peste cap lanț, în cazul în care
nu am conecta indicii

434
00:21:41,909 --> 00:21:44,690
în ordinea corectă, dacă
doar eliberat primul element,

435
00:21:44,690 --> 00:21:47,420
dacă ne-am eliberat
cap de listă, acum ne

436
00:21:47,420 --> 00:21:49,642
au nici o modalitate de a face referire la
restul listei.

437
00:21:49,642 --> 00:21:51,350
Și așa ne-am fi
totul orfani,

438
00:21:51,350 --> 00:21:53,880
am fi avut ce-i
numit o scurgere de memorie.

439
00:21:53,880 --> 00:21:56,800
Dacă vă amintiți de la videoclipul nostru
privind alocarea dinamică a memoriei,

440
00:21:56,800 --> 00:21:58,650
asta nu e lucru foarte bun.

441
00:21:58,650 --> 00:22:00,810
>> Deci, după cum am spus, nu
sunt mai multe operațiuni

442
00:22:00,810 --> 00:22:04,010
de care avem nevoie pentru a utiliza pentru a lucra
cu lista legate în mod eficient.

443
00:22:04,010 --> 00:22:08,430
Și este posibil să fi observat că omis unul,
ștergerea un singur element dintr-o legătură

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

445
00:22:09,064 --> 00:22:10,980
Motivul pentru care am făcut asta
este de fapt un fel de

446
00:22:10,980 --> 00:22:14,360
dificil să se gândească la cum să ștergeți
un singur element dintr-o individual

447
00:22:14,360 --> 00:22:15,600
Lista legate.

448
00:22:15,600 --> 00:22:19,950
Trebuie să fim capabili să săriți peste
ceva în listă, care

449
00:22:19,950 --> 00:22:22,975
înseamnă ajungem la o vom point--
doriți să ștergeți acest node--

450
00:22:22,975 --> 00:22:25,350
dar în scopul de a face astfel încât să
nu pierde nici o informație,

451
00:22:25,350 --> 00:22:30,530
avem nevoie pentru a conecta acest
nod aici, aici.

452
00:22:30,530 --> 00:22:33,390
>> Deci, probabil, am făcut-o greșit
din punct de vedere vizual.

453
00:22:33,390 --> 00:22:36,830
Deci suntem la începutul nostru
Lista, suntem procedând prin,

454
00:22:36,830 --> 00:22:40,510
vrem să ștergeți acest nod.

455
00:22:40,510 --> 00:22:43,440
Dacă ne-am șterge,
am rupt lanțul.

456
00:22:43,440 --> 00:22:45,950
Acest nod aici
se referă la orice altceva,

457
00:22:45,950 --> 00:22:48,260
conține lanțul de acum înainte.

458
00:22:48,260 --> 00:22:51,190
>> Deci, ceea ce avem nevoie pentru a face de fapt
după ce vom ajunge la acest punct,

459
00:22:51,190 --> 00:22:56,670
este că trebuie să pas înapoi, și
conecta acest nod pe la acest nod,

460
00:22:56,670 --> 00:22:58,590
astfel încât să putem șterge apoi
cel din mijloc.

461
00:22:58,590 --> 00:23:02,120
Dar listele individual legate nu
ne oferă o modalitate de a merge înapoi.

462
00:23:02,120 --> 00:23:05,160
Așa că trebuie să fie păstrați
două indicii, și a le muta

463
00:23:05,160 --> 00:23:09,527
un fel de pas off, una în spatele
altul ca mergem, sau ajunge la un punct

464
00:23:09,527 --> 00:23:11,110
și apoi trimite un alt pointer prin.

465
00:23:11,110 --> 00:23:13,150
Și, după cum se poate vedea,
poate obține un pic murdar.

466
00:23:13,150 --> 00:23:15,360
Din fericire, ne-am
un alt mod de a rezolva asta,

467
00:23:15,360 --> 00:23:17,810
atunci când vorbim despre liste de două ori legate.

468
00:23:17,810 --> 00:23:20,720
>> Sunt Doug Lloyd, aceasta este CS50.

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