1
00:00:00,000 --> 00:00:04,074

2
00:00:04,074 --> 00:00:05,990
Doug LLOYD: All right,
tako da po tej točki ste ga

3
00:00:05,990 --> 00:00:09,020
verjetno precej pozna
z nizi in povezanih seznamov

4
00:00:09,020 --> 00:00:10,950
ki je dve primarni
podatkovne strukture, ki smo jih

5
00:00:10,950 --> 00:00:16,810
je govoril o za vodenje sklopov
podatkov o podobnih podatkovnih tipov organizirani.

6
00:00:16,810 --> 00:00:19,080
>> Zdaj bomo govorili
o nekaj sprememb

7
00:00:19,080 --> 00:00:20,330
o nizi in povezanih seznamov.

8
00:00:20,330 --> 00:00:22,362
V tem video bomo
govoriti o nizov.

9
00:00:22,362 --> 00:00:25,320
Natančneje bomo govorili
o struktura podatkov, ki se imenuje sklad.

10
00:00:25,320 --> 00:00:28,510
Odpoklic iz prejšnjih razprav
o kazalci in spominu,

11
00:00:28,510 --> 00:00:32,060
da je sklad tudi
ime za segment pomnilnika

12
00:00:32,060 --> 00:00:34,980
kjer statično razglasila
memory-- spomin, ki vas

13
00:00:34,980 --> 00:00:38,730
ime, spremenljivke, ki si ime, et
cetera in funkcija okvirji, ki smo tudi

14
00:00:38,730 --> 00:00:41,000
obstajajo klic konzoli okvirji.

15
00:00:41,000 --> 00:00:45,421
Torej, to je struktura podatkov kup
ne kup segment pomnilnika.

16
00:00:45,421 --> 00:00:45,920
V REDU.

17
00:00:45,920 --> 00:00:46,890
>> Toda kaj je kup?

18
00:00:46,890 --> 00:00:49,220
Torej, to je precej samo
posebna vrsta strukture

19
00:00:49,220 --> 00:00:51,190
da vzdržuje podatke na organiziran način.

20
00:00:51,190 --> 00:00:53,760
In tam je dva zelo
pogosti načini za izvajanje

21
00:00:53,760 --> 00:00:57,380
nizov z uporabo dveh podatkovnih struktur
da smo že poznajo,

22
00:00:57,380 --> 00:01:00,340
nizi in povezani seznam.

23
00:01:00,340 --> 00:01:04,430
Kaj naredi kup posebno je
Način, na katerega smo dal podatke

24
00:01:04,430 --> 00:01:08,200
v dimnik, in način, kako
odstrani podatke iz dimnika.

25
00:01:08,200 --> 00:01:11,600
Zlasti s skladovnice
pravilo je le najbolj

26
00:01:11,600 --> 00:01:15,830
Nedavno se doda element možno odstraniti.

27
00:01:15,830 --> 00:01:17,660
>> Torej, razmišljam o tem, kot da je to kup.

28
00:01:17,660 --> 00:01:21,170
Mi smo piling informacije
na vrhu sebi

29
00:01:21,170 --> 00:01:24,271
in samo stvar na vrhu
kupa se lahko odstrani.

30
00:01:24,271 --> 00:01:27,020
Mi stvar ne more odstraniti pod
ker vse ostalo bi

31
00:01:27,020 --> 00:01:28,020
kolaps in se prevrne.

32
00:01:28,020 --> 00:01:32,580
Torej smo res se gradi sklad, ki
bomo potem morali odstraniti kos za kosom.

33
00:01:32,580 --> 00:01:36,590
Zaradi tega smo pogosto sklicuje
na kupu kot strukturo LIFO,

34
00:01:36,590 --> 00:01:38,940
zadnji noter, prvi ven.

35
00:01:38,940 --> 00:01:42,290
LIFO, zadnji noter, prvi ven.

36
00:01:42,290 --> 00:01:45,635
>> Zato, ker te omejitve na
kako se lahko dodajajo podatki

37
00:01:45,635 --> 00:01:49,080
in odstrani iz dimnika, da je res
le dve stvari, ki jih lahko naredite z dimnika.

38
00:01:49,080 --> 00:01:52,010
Lahko potiskanje, ki je
Izraz uporabljamo za dodajanje

39
00:01:52,010 --> 00:01:55,130
nov element na vrhu
kup, ali če je sklad ne obstaja

40
00:01:55,130 --> 00:01:58,550
in smo ga ustvarili iz nič,
ustvarjanje snop na prvem mestu

41
00:01:58,550 --> 00:02:00,110
bi potiska.

42
00:02:00,110 --> 00:02:04,990
In potem pop, da je nekako CS
Izraz uporabljamo za odstranitev nazadnje

43
00:02:04,990 --> 00:02:08,330
dodamo element z vrha dimnika.

44
00:02:08,330 --> 00:02:11,130
>> Torej gremo pogledati na obe
izvedb, ki temelji tako niz

45
00:02:11,130 --> 00:02:13,120
in povezani seznam, ki temelji.

46
00:02:13,120 --> 00:02:14,870
In bomo
začnete s paleto temelji.

47
00:02:14,870 --> 00:02:19,990
Torej, tukaj je osnovna ideja o tem, kaj
array temelji struktura podatkov kup

48
00:02:19,990 --> 00:02:21,140
bi izgledal.

49
00:02:21,140 --> 00:02:23,740
Imamo definicijo tipkani tukaj.

50
00:02:23,740 --> 00:02:27,790
Znotraj da imamo dva člana
ali področja strukture.

51
00:02:27,790 --> 00:02:29,880
Imamo celo paleto.

52
00:02:29,880 --> 00:02:32,400
In spet sem z uporabo
poljubna vrsta podatkov vrednost.

53
00:02:32,400 --> 00:02:35,180
>> Torej, to je lahko katera koli vrsta podatkov,
int char ali nekatere druge podatke

54
00:02:35,180 --> 00:02:37,080
tip ste prej ustvarili.

55
00:02:37,080 --> 00:02:39,861
Torej imamo paleto velikosti zmogljivosti.

56
00:02:39,861 --> 00:02:44,010
Kapaciteta se funt definirana konstanta,
morda nekje drugje v našem spisu.

57
00:02:44,010 --> 00:02:47,550
Torej opazili že s tem zlasti
Izvajanje smo se povezuje

58
00:02:47,550 --> 00:02:49,800
sami, kot je bilo običajno
na primer z nizi,

59
00:02:49,800 --> 00:02:53,170
ki je ne moremo dinamično spreminjanje velikosti,
kjer je določeno število

60
00:02:53,170 --> 00:02:55,450
za največ elementov, ki
bomo lahko v našem dimnika.

61
00:02:55,450 --> 00:02:57,930
V tem primeru je to elemente zmogljivosti.

62
00:02:57,930 --> 00:03:00,310
>> Prav tako spremljate
vrh dimnika.

63
00:03:00,310 --> 00:03:04,350
Kaj element je najbolj
Nedavno doda skladovnice?

64
00:03:04,350 --> 00:03:07,470
In tako smo spremljate da
spremenljivo imenujemo vrh.

65
00:03:07,470 --> 00:03:11,692
In vse to dobi zaokrožila skupaj
v novo vrsto podatkov, imenovano kup.

66
00:03:11,692 --> 00:03:13,400
In ko smo ustvarili
Ta nova vrsta podatkov

67
00:03:13,400 --> 00:03:15,410
jo lahko obravnavajo kot
katera koli druga vrsta podatkov.

68
00:03:15,410 --> 00:03:20,970
Mi lahko razglasi dimnika ov, prav tako kot
kar lahko storimo int x, ali char y.

69
00:03:20,970 --> 00:03:22,990
In ko rečemo kup
ov, dobro, kaj se zgodi

70
00:03:22,990 --> 00:03:26,420
se dobimo niz
pomnilnika v prahi za nas.

71
00:03:26,420 --> 00:03:28,770
>> V tem primeru zmogljivosti
Sem očitno odločil,

72
00:03:28,770 --> 00:03:33,470
10, ker sem dobil
enojna variabilna tipa skladovnice

73
00:03:33,470 --> 00:03:35,320
ki vsebuje dve polji odpokličejo.

74
00:03:35,320 --> 00:03:38,330
Matrika, v tem primeru se bo
da bo niz števil

75
00:03:38,330 --> 00:03:40,440
kot je to primer v večini mojih primerov.

76
00:03:40,440 --> 00:03:43,996
In še celo spremenljivka
lahko shrani vrha,

77
00:03:43,996 --> 00:03:45,870
Najbolj nedavno dodane
element dimnika.

78
00:03:45,870 --> 00:03:50,290
Torej en kup, kar smo
Samo opredeljena izgleda takole.

79
00:03:50,290 --> 00:03:53,190
To je škatla, ki vsebuje
niz 10, kar

80
00:03:53,190 --> 00:03:57,280
bo cela v tem primeru in
drugo število spremenljivka je v zeleni barvi

81
00:03:57,280 --> 00:04:00,010
navesti vrh dimnika.

82
00:04:00,010 --> 00:04:02,600
>> Če želite nastaviti vrhu
Sveženj smo pravkar rekel s.top.

83
00:04:02,600 --> 00:04:04,890
To je, kako smo dostopite do
polje strukture odpoklica.

84
00:04:04,890 --> 00:04:10,460
s.top enak 0 učinkovito
pa to, da naši dimnika.

85
00:04:10,460 --> 00:04:12,960
Torej, spet imamo dve operaciji
da bomo lahko sedaj opravljam.

86
00:04:12,960 --> 00:04:14,270
Mi lahko push in bomo lahko pop.

87
00:04:14,270 --> 00:04:15,635
Začnimo s pritiskom.

88
00:04:15,635 --> 00:04:18,260
Again, potiskanje je dodal nov
element na vrhu kupa.

89
00:04:18,260 --> 00:04:21,460
>> Torej, kaj moramo storiti v
Ta matrika izvedba temelji?

90
00:04:21,460 --> 00:04:23,210
No, na splošno
funkcija Push se dogaja

91
00:04:23,210 --> 00:04:26,160
bi morali sprejeti
kazalec na sklad.

92
00:04:26,160 --> 00:04:28,610
Sedaj vzemite drugega in razmišljati o tem.

93
00:04:28,610 --> 00:04:32,840
Zakaj bi si želeli, da sprejme
kazalec na kupu?

94
00:04:32,840 --> 00:04:36,830
Odpoklic iz prejšnjih videov na
spremenljivka obseg in kazalci,

95
00:04:36,830 --> 00:04:42,350
kaj bi se zgodilo, če bomo le poslal
Sveženj, s precej v kot parameter?

96
00:04:42,350 --> 00:04:45,770
Kaj bi se dejansko prenesejo tja?

97
00:04:45,770 --> 00:04:49,430
Ne pozabite, da smo ustvarili kopijo
ko smo jo prenese na funkcijo

98
00:04:49,430 --> 00:04:51,160
če bomo uporabili kazalce.

99
00:04:51,160 --> 00:04:55,380
In tako je ta funkcija potisnite potrebe
da sprejme kazalec na kupu

100
00:04:55,380 --> 00:04:59,160
tako da smo dejansko spreminja
Sveženj nameravamo spremeniti.

101
00:04:59,160 --> 00:05:03,060
>> Druga stvar, potisni verjetno želi
sprejeti je podatkovni element tipa vrednosti.

102
00:05:03,060 --> 00:05:06,970
V tem primeru spet, celo število, ki
bomo dodali na vrhu dimnika.

103
00:05:06,970 --> 00:05:08,680
Torej imamo naše dva parametra.

104
00:05:08,680 --> 00:05:11,310
Kaj bomo
zdaj počnejo push?

105
00:05:11,310 --> 00:05:14,860
No, samo, da smo šele tekoč, da dodate
ta element na vrhu kupa

106
00:05:14,860 --> 00:05:22,860
in nato spremenite kje na vrh
Sveženj je, da S dot top vrednost.

107
00:05:22,860 --> 00:05:25,639
Torej, to je, kaj je funkcija
Izjava Pritisni

108
00:05:25,639 --> 00:05:27,680
lahko izgledal v
diod, ki temelji izvajanje.

109
00:05:27,680 --> 00:05:30,967
>> Tudi to ni težko in hitro pravilo
da bi lahko to spremenili in imajo

110
00:05:30,967 --> 00:05:32,050
se med seboj razlikujejo.

111
00:05:32,050 --> 00:05:33,840
Morda se je razglasila globalno.

112
00:05:33,840 --> 00:05:36,180
In tako sploh ne potrebujemo
da prenese je kot parameter.

113
00:05:36,180 --> 00:05:39,125
To je spet le
splošno velja za pritiskom.

114
00:05:39,125 --> 00:05:41,000
In tam so drugačni
načini za njeno izvajanje.

115
00:05:41,000 --> 00:05:42,810
Toda v tem primeru naše
Pritisni in bo trajalo

116
00:05:42,810 --> 00:05:48,540
dva argumenta, kazalec na kup in
podatkovni element tipa vrednosti, integer

117
00:05:48,540 --> 00:05:49,840
v tem primeru.

118
00:05:49,840 --> 00:05:52,100
>> Tako smo razglasila ov smo
dejal s.top enak 0.

119
00:05:52,100 --> 00:05:55,969
Zdaj pa potisnite
Številka 28 na kupu.

120
00:05:55,969 --> 00:05:57,010
No, kaj to pomeni?

121
00:05:57,010 --> 00:05:59,600
No, trenutno
Vrh dimnika je 0.

122
00:05:59,600 --> 00:06:01,350
In kaj je v bistvu
se bo zgodilo, je

123
00:06:01,350 --> 00:06:05,820
bomo držijo številko
28 v matrično mestu 0.

124
00:06:05,820 --> 00:06:09,540
Precej enostavno, kajne, da
je bil najboljši in zdaj smo na dobri poti.

125
00:06:09,540 --> 00:06:12,910
In potem moramo spremeniti, kaj
vrh dimnika bo.

126
00:06:12,910 --> 00:06:15,130
Tako da naslednjič, ko
smo potiskanje element,

127
00:06:15,130 --> 00:06:18,017
bomo, da jo shranite v
lokacija matrika, verjetno ni 0.

128
00:06:18,017 --> 00:06:20,100
Mi ne želimo prepisati
kaj smo pravkar dal tam.

129
00:06:20,100 --> 00:06:23,510
In tako bomo samo premaknete vrha do 1.

130
00:06:23,510 --> 00:06:24,890
To je verjetno smiselna.

131
00:06:24,890 --> 00:06:28,940
>> Zdaj, če želimo postaviti še en element
na kupu, recimo želimo potiskanje 33,

132
00:06:28,940 --> 00:06:33,190
tudi zdaj smo šele bo trajalo 33
in jo dal na matrično lokaciji številko

133
00:06:33,190 --> 00:06:37,580
1, in nato spremenite vrhu našega
kup da je matrika lokacija številka dve.

134
00:06:37,580 --> 00:06:40,650
Torej, če naslednjič, ko želimo
potisni element na stack,

135
00:06:40,650 --> 00:06:43,087
ga bom dal v matrično mestu 2.

136
00:06:43,087 --> 00:06:44,420
In kaj je to naredil še enkrat.

137
00:06:44,420 --> 00:06:45,753
Bomo potisnite 19 off od nizov.

138
00:06:45,753 --> 00:06:48,940
Bomo dal 19 v matriki mestu 2
in spremenite vrh našega dimnika

139
00:06:48,940 --> 00:06:51,220
da je matrika mesto 3
tako da, če v naslednjem času smo

140
00:06:51,220 --> 00:06:54,780
morali narediti Pritisni smo na dobri poti.

141
00:06:54,780 --> 00:06:56,980
>> OK, tako da se potiska na kratko.

142
00:06:56,980 --> 00:06:57,830
Kaj popping?

143
00:06:57,830 --> 00:07:00,240
Tako živahen je neke vrste
kolegom za potiskanje.

144
00:07:00,240 --> 00:07:02,720
To je, kako odstraniti podatke iz dimnika.

145
00:07:02,720 --> 00:07:04,610
In splošne potrebe pop
storiti naslednje.

146
00:07:04,610 --> 00:07:07,600
Potrebuje, da sprejme kazalec na
kup, spet v splošnem primeru.

147
00:07:07,600 --> 00:07:10,480
V nekem drugem primeru boste morda
so izjavili, da sklad v svetovnem merilu,

148
00:07:10,480 --> 00:07:13,910
V tem primeru vam ni treba dajati
V saj že ima dostop do njega

149
00:07:13,910 --> 00:07:15,541
kot globalne spremenljivke.

150
00:07:15,541 --> 00:07:17,040
Ampak potem, kaj storiti moramo storiti?

151
00:07:17,040 --> 00:07:21,000
Pa smo povečevanje
na vrhu kupa v pritiskom,

152
00:07:21,000 --> 00:07:24,050
tako da bomo verjetno želeli
da pojemanje vrh dimnika

153
00:07:24,050 --> 00:07:25,009
v pop, kajne?

154
00:07:25,009 --> 00:07:26,800
In potem seveda
smo tudi dogaja, da želijo

155
00:07:26,800 --> 00:07:29,240
vrne vrednost, ki smo odstraniti.

156
00:07:29,240 --> 00:07:32,125
Če smo dodajanjem elementov, želimo
dobiti elemente ven kasneje,

157
00:07:32,125 --> 00:07:34,000
bomo verjetno dejansko
jih želite shraniti, zato smo

158
00:07:34,000 --> 00:07:36,490
jih ne šele izbrisati iz
kup in potem ni z njimi.

159
00:07:36,490 --> 00:07:38,500
Na splošno, če smo
potiskanje in popping tukaj

160
00:07:38,500 --> 00:07:41,250
želimo, da shranite to
informacije na razumljiv način

161
00:07:41,250 --> 00:07:43,250
in zato tudi ne
občutek, da samo ga zavrzite.

162
00:07:43,250 --> 00:07:46,380
Torej ta funkcija bi morala
Verjetno vrne vrednost k nam.

163
00:07:46,380 --> 00:07:51,040
>> Torej, to je, kaj deklaracijo za pop
morda videti, kot da v zgornjem levem kotu.

164
00:07:51,040 --> 00:07:53,870
Ta funkcija vrne
Podatki o vrsti vrednosti.

165
00:07:53,870 --> 00:07:56,320
Spet smo bili z uporabo
cela števila v celotnem besedilu.

166
00:07:56,320 --> 00:08:01,916
In to sprejme kazalec na kupu, kot
njen edini argument ali edini parameter.

167
00:08:01,916 --> 00:08:03,040
Torej, kaj je pop boš naredil?

168
00:08:03,040 --> 00:08:07,990
Recimo, da želimo zdaj
pop element off s.

169
00:08:07,990 --> 00:08:14,000
Torej, ne pozabite, sem rekel, da so nizov zadnji
noter, prvi ven, LIFO podatkovnih struktur.

170
00:08:14,000 --> 00:08:17,855
Kateri element se dogaja, da
odstrani iz skladovnice?

171
00:08:17,855 --> 00:08:21,780

172
00:08:21,780 --> 00:08:24,150
Ali uganete, 19?

173
00:08:24,150 --> 00:08:25,290
Ker bi morali biti v redu.

174
00:08:25,290 --> 00:08:28,836
19 je bil zadnji element smo dodali k
kup, ko smo bili potiska elementov na,

175
00:08:28,836 --> 00:08:31,210
in tako se dogaja, da je prvi
element, da postane odstraniti.

176
00:08:31,210 --> 00:08:34,780
To je, kot če bi rekli, 28, in
potem smo dal 33 na vrhu je,

177
00:08:34,780 --> 00:08:36,659
in mi dal 19 na vrhu, da.

178
00:08:36,659 --> 00:08:40,650
Edini element moremo vzleteti, je 19.

179
00:08:40,650 --> 00:08:45,019
>> Zdaj v diagramu tukaj kaj sem naredil
je nekako črta 19 iz matrike.

180
00:08:45,019 --> 00:08:46,810
To dejansko ni
kaj bomo storili.

181
00:08:46,810 --> 00:08:48,934
Mi smo le, da bo vrste
od pretvarjati, da ni tam.

182
00:08:48,934 --> 00:08:51,441
To je še vedno tam v
da spominsko lokacijo,

183
00:08:51,441 --> 00:08:54,190
vendar smo šele tekoč, da ga ignorirati
s spreminjanjem vrh našim skladovnice

184
00:08:54,190 --> 00:08:56,080
od tega 3 na 2.

185
00:08:56,080 --> 00:08:58,720
Torej, če smo bili do zdaj potiskanje
en element na stack,

186
00:08:58,720 --> 00:09:00,720
da bi čez pisati 19.

187
00:09:00,720 --> 00:09:03,990
>> Ampak ne gredo skozi težave
izbrišete 19 iz dimnika.

188
00:09:03,990 --> 00:09:05,830
Mi lahko samo pretvarjamo, da je ni tam.

189
00:09:05,830 --> 00:09:11,107
Za namene dimnika je to šlo, če
spremenimo zgornji znaša 2 namesto 3.

190
00:09:11,107 --> 00:09:12,690
Vse je v redu, tako da je bilo precej bilo.

191
00:09:12,690 --> 00:09:15,080
To je vse, kar moramo storiti
pop element off.

192
00:09:15,080 --> 00:09:16,090
Dajmo še enkrat.

193
00:09:16,090 --> 00:09:18,610
Tako sem ga v rdeči barvi tukaj
kažejo, da smo kar en klic.

194
00:09:18,610 --> 00:09:19,720
Bomo narediti isto stvar.

195
00:09:19,720 --> 00:09:20,803
>> Torej, kaj se bo zgodilo?

196
00:09:20,803 --> 00:09:23,670
No, bomo za shranjevanje
33 vx in gremo

197
00:09:23,670 --> 00:09:26,217
spremeniti vrhu kupa 1.

198
00:09:26,217 --> 00:09:29,050
Tako da če smo bili zdaj potiskanje
element v plasteh, ki sva

199
00:09:29,050 --> 00:09:31,610
storili zdaj,
kaj se bo zgodilo

200
00:09:31,610 --> 00:09:36,367
se greva Prepiši
matrika lokacija številka 1.

201
00:09:36,367 --> 00:09:38,950
Tako da je 33, ki je bil nekako levo
zadaj, da smo samo pretvarjal

202
00:09:38,950 --> 00:09:44,390
ni več tam, da smo le, da bo
da jo clobber in namesto tega dal 40 tam.

203
00:09:44,390 --> 00:09:46,290
In potem seveda,
saj smo naredili potiskanje,

204
00:09:46,290 --> 00:09:48,780
bomo prirastek
vrh dimnika od 1 do 2

205
00:09:48,780 --> 00:09:50,950
tako da če smo zdaj dodali
še en element, da bomo

206
00:09:50,950 --> 00:09:54,700
iti v matrično lokaciji številka dve.

207
00:09:54,700 --> 00:09:57,590
>> Zdaj povezani seznami so še en
način za izvajanje nizov.

208
00:09:57,590 --> 00:10:01,210
In če te opredelitve na
Zaslon tukaj izgleda znano za vas,

209
00:10:01,210 --> 00:10:04,260
to je zato, ker je videti skoraj
popolnoma enako, v bistvu,

210
00:10:04,260 --> 00:10:07,790
je precej, je natanko
Enako kot posamezno povezani seznam,

211
00:10:07,790 --> 00:10:11,990
če se spomnimo iz naše razprave
posamezno povezana sezname v drugem videu.

212
00:10:11,990 --> 00:10:15,510
Edina omejitev tukaj
je za nas kot programerji,

213
00:10:15,510 --> 00:10:17,900
smo ni dovoljeno
vstavite ali izbrišete naključno

214
00:10:17,900 --> 00:10:20,620
od enkrat povezani seznam
ki bi lahko že prej storiti.

215
00:10:20,620 --> 00:10:25,820
Mi lahko šele zdaj vstaviti in izbrisati iz
sprednji ali na vrhu povezana

216
00:10:25,820 --> 00:10:26,320
seznam.

217
00:10:26,320 --> 00:10:28,028
To je res edina
Razlika čeprav.

218
00:10:28,028 --> 00:10:29,700
To je sicer za enkrat povezani seznam.

219
00:10:29,700 --> 00:10:32,060
To je edina omejitev
zamenjava na nas

220
00:10:32,060 --> 00:10:35,770
kot programerjev, ki
ga spremeni v kup.

221
00:10:35,770 --> 00:10:39,280
>> Pravilo tukaj je, da vedno vzdržuje
kazalec na čelu povezani seznam.

222
00:10:39,280 --> 00:10:41,520
To je seveda splošno
Pomembno pravilo prvič.

223
00:10:41,520 --> 00:10:44,260
Za posamezno povezani seznam nekako vam
potrebujete le kazalec na glavo

224
00:10:44,260 --> 00:10:46,160
z namenom, da ima to
veriga lahko nanašajo

225
00:10:46,160 --> 00:10:48,596
za vsakega drugega elementa
v povezanem seznamu.

226
00:10:48,596 --> 00:10:50,470
Ampak to je še posebej
pomembna z dimnika.

227
00:10:50,470 --> 00:10:52,386
In tako na splošno, da ste
bo dejansko želijo

228
00:10:52,386 --> 00:10:54,090
Ta kazalec bi lahko globalna spremenljivka.

229
00:10:54,090 --> 00:10:56,574
To je verjetno, da bo
še lažje na ta način.

230
00:10:56,574 --> 00:10:58,240
Torej, kaj so analogi Pritisni in popa?

231
00:10:58,240 --> 00:10:58,740
Prav.

232
00:10:58,740 --> 00:11:01,812
Torej, spet potiska je dodal
nov element dimnika.

233
00:11:01,812 --> 00:11:03,770
V povezanem seznamu
pomeni, da bomo imeli

234
00:11:03,770 --> 00:11:07,770
ustvariti novo vozlišče, da smo
bom dodal v povezanem seznamu

235
00:11:07,770 --> 00:11:10,500
in sledite skrbno korakom
da smo že prej opisali

236
00:11:10,500 --> 00:11:16,050
v posamezno povezanih seznamov, da jo dodate
veriga ne da bi poškodovali verigo

237
00:11:16,050 --> 00:11:18,900
in izgube ali orphaning koli
elementi povezani seznam.

238
00:11:18,900 --> 00:11:21,820
In to je v bistvu tisto, ki
Malo blob besedila tam povzema.

239
00:11:21,820 --> 00:11:23,740
In dajmo si oglejte
na to kot diagram.

240
00:11:23,740 --> 00:11:24,823
>> Torej, tukaj je naša povezani seznam.

241
00:11:24,823 --> 00:11:26,620
To hkrati vsebuje štiri elemente.

242
00:11:26,620 --> 00:11:30,420
In še več popolnoma Tukaj je naš
kup, ki vsebuje štiri elemente.

243
00:11:30,420 --> 00:11:36,030
In recimo, da hočemo sedaj
potisnite nov element na tem kupu.

244
00:11:36,030 --> 00:11:39,792
In želimo, da potisnite nov
postavka, katere podatki vrednost je 12.

245
00:11:39,792 --> 00:11:41,000
No, kaj bomo storili?

246
00:11:41,000 --> 00:11:43,420
No, najprej se bomo
malloc prostor, dinamično

247
00:11:43,420 --> 00:11:45,411
dodeli prostor za novo vozlišče.

248
00:11:45,411 --> 00:11:48,160
In seveda takoj
smo klic, da smo malloc vedno

249
00:11:48,160 --> 00:11:52,989
se prepričajte, da preverite, ali null,
ker če imamo null nazaj

250
00:11:52,989 --> 00:11:54,280
je bil neke vrste problem.

251
00:11:54,280 --> 00:11:57,570
Nočemo, da dereference tem null
kazalec ali pa boste trpeli napako SEG.

252
00:11:57,570 --> 00:11:58,510
To ni dobro.

253
00:11:58,510 --> 00:11:59,760
Torej smo malloced vozlišča.

254
00:11:59,760 --> 00:12:01,260
Bomo domnevati, da smo imeli uspeh tukaj.

255
00:12:01,260 --> 00:12:06,090
Bomo dal 12 v
podatkovno polje vozlišča.

256
00:12:06,090 --> 00:12:11,570
Zdaj pa se spomnite, kateri od naših nasvetov
premika zraven tako ne bomo prekinili verigo?

257
00:12:11,570 --> 00:12:15,100
Imamo nekaj možnosti tukaj, ampak
edini, ki se dogaja, da je varna

258
00:12:15,100 --> 00:12:19,330
je določiti novice naslednji kazalec na
točka na stari glavo seznama

259
00:12:19,330 --> 00:12:21,360
ali kaj bo kmalu bo
stari vodja seznama.

260
00:12:21,360 --> 00:12:23,610
In zdaj, da so vsi naši
Elementi so priklenjen skupaj,

261
00:12:23,610 --> 00:12:27,370
bomo lahko samo premaknete seznam za točko
na istem mestu, da nova ne.

262
00:12:27,370 --> 00:12:33,550
In zdaj smo dejansko potisne
Novost na sprednji strani skladovnice.

263
00:12:33,550 --> 00:12:36,420
>> Pop Pravkar smo želeli
izbrisati to prvi element.

264
00:12:36,420 --> 00:12:38,150
In tako v bistvu tisto,
moramo narediti tukaj,

265
00:12:38,150 --> 00:12:40,050
dobro se bomo morali najti drugega elementa.

266
00:12:40,050 --> 00:12:43,540
Sčasoma, da bo postala nova
glavo, ko smo izbrisati prvo.

267
00:12:43,540 --> 00:12:47,300
Zato smo morali začeti iz
začetek, premakniti eno naprej.

268
00:12:47,300 --> 00:12:50,340
Ko bomo dobili držite na enem
naprej, kje smo trenutno

269
00:12:50,340 --> 00:12:53,850
smo lahko varno izbrisati prvo
in potem bomo lahko samo premaknete glavo

270
00:12:53,850 --> 00:12:57,150
opozoriti na to, kar je bilo
Drugi mandat in nato zdaj

271
00:12:57,150 --> 00:12:59,170
je prva po tem
vozlišče je bil izbrisan.

272
00:12:59,170 --> 00:13:01,160
>> Torej še enkrat, ob poglej
na njej kot diagram smo

273
00:13:01,160 --> 00:13:05,022
želijo zdaj pop
element off tega dimnika.

274
00:13:05,022 --> 00:13:05,730
Torej, kaj naj naredimo?

275
00:13:05,730 --> 00:13:08,188
Pa smo prvič dogaja, da ustvarite
nov kazalec, ki se dogaja

276
00:13:08,188 --> 00:13:10,940
da kaže na istem mestu kot konica.

277
00:13:10,940 --> 00:13:13,790
Bomo, da ga premaknete za eno mesto
naprej z besedami trav enaka

278
00:13:13,790 --> 00:13:17,510
trav Naslednji primer, ki
bi vnaprej trav kazalec eno na

279
00:13:17,510 --> 00:13:19,324
položaj naprej.

280
00:13:19,324 --> 00:13:21,240
Zdaj, ko imamo
imajo na prvem elementu

281
00:13:21,240 --> 00:13:24,573
s kazalcem imenuje seznamu, in
drugi element s kazalcem imenuje

282
00:13:24,573 --> 00:13:28,692
trav, bomo lahko varno izbrisati, da
Prvi element iz skladovnice

283
00:13:28,692 --> 00:13:30,650
brez izgube ostalo
verige, ker mi

284
00:13:30,650 --> 00:13:32,358
so način, da se sklicujem
na drugi element

285
00:13:32,358 --> 00:13:34,780
posreduje preko izmed
Kazalec se imenuje trav.

286
00:13:34,780 --> 00:13:37,100
>> Torej, zdaj smo lahko osvobodi tega vozlišča.

287
00:13:37,100 --> 00:13:38,404
Mi lahko osvobodi seznam.

288
00:13:38,404 --> 00:13:41,320
In potem vse, kar morate storiti, je zdaj
premakniti seznam točke na istem mestu

289
00:13:41,320 --> 00:13:44,482
da trav počne, in smo nekako nazaj
kjer smo začeli, preden smo potisnilo 12

290
00:13:44,482 --> 00:13:45,690
na na prvem mestu, desno.

291
00:13:45,690 --> 00:13:46,940
To je točno tam, kjer smo bili.

292
00:13:46,940 --> 00:13:48,840
Imela sva štiri element dimnika.

293
00:13:48,840 --> 00:13:49,690
Dodali smo petino.

294
00:13:49,690 --> 00:13:51,910
Zavzeli smo petino
element na, nato pa smo

295
00:13:51,910 --> 00:13:55,980
izstrelil da v zadnjem času
Dodana element nazaj off.

296
00:13:55,980 --> 00:13:58,816
>> To je res precej
vse, kar je nizov.

297
00:13:58,816 --> 00:14:00,190
Lahko jih izvajajo kot nizi.

298
00:14:00,190 --> 00:14:01,815
Lahko jih izvajajo kot povezanih seznamov.

299
00:14:01,815 --> 00:14:04,810
Obstajajo seveda druge
načine za njihovo izvajanje, kot tudi.

300
00:14:04,810 --> 00:14:09,060
V bistvu razlog, da bi uporabili
skladovnic je ohranjanje podatkov na tak način,

301
00:14:09,060 --> 00:14:12,090
da je nedavno dodane
element je prva stvar, ki smo

302
00:14:12,090 --> 00:14:14,980
dogaja, da želijo, da bi dobili nazaj.

303
00:14:14,980 --> 00:14:17,900
Sem Doug Lloyd, to je CS50.

304
00:14:17,900 --> 00:14:19,926