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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Allt í lagi,
svo með þessum tímapunkti sem þú ert

3
00:00:05,990 --> 00:00:09,020
líklega nokkuð kunnuglegt
með fylki og tengd listum

4
00:00:09,020 --> 00:00:10,950
sem er tvær aðal
gögn uppbygging sem við höfum

5
00:00:10,950 --> 00:00:16,810
talað um að halda setur
gögn af svipuðum gagnatög skipulögð.

6
00:00:16,810 --> 00:00:19,080
>> Nú erum við að fara að tala
um nokkra tilbrigðum

7
00:00:19,080 --> 00:00:20,330
á fylki og tengd listum.

8
00:00:20,330 --> 00:00:22,362
Í þessu myndbandi sem við erum að fara
að tala um stafla.

9
00:00:22,362 --> 00:00:25,320
Sérstaklega við erum að fara að tala
um gögn uppbygging kallast stafla.

10
00:00:25,320 --> 00:00:28,510
Muna frá fyrri umræðum
um ábendingum og minni,

11
00:00:28,510 --> 00:00:32,060
að stafla er einnig
nafn fyrir a hluti af minni

12
00:00:32,060 --> 00:00:34,980
þar statically lýst
memory-- minni sem þér

13
00:00:34,980 --> 00:00:38,730
nafn, breytur sem þú nafn, et
cetera og virka rammar sem við einnig

14
00:00:38,730 --> 00:00:41,000
kalla stafla ramma til.

15
00:00:41,000 --> 00:00:45,421
Svo er þetta stafla gögn uppbygging
ekki stafla hluti af minni.

16
00:00:45,421 --> 00:00:45,920
OK.

17
00:00:45,920 --> 00:00:46,890
>> En hvað er stafla?

18
00:00:46,890 --> 00:00:49,220
Svo það er ansi mikið bara
sérstaka tegund af uppbyggingu

19
00:00:49,220 --> 00:00:51,190
sem viðheldur gögn á skipulegan hátt.

20
00:00:51,190 --> 00:00:53,760
Og það er tveir mjög
algengar leiðir til að hrinda í framkvæmd

21
00:00:53,760 --> 00:00:57,380
stafla með tveimur gögn uppbygging
sem við erum nú þegar kunnugt,

22
00:00:57,380 --> 00:01:00,340
fylki og tengd listum.

23
00:01:00,340 --> 00:01:04,430
Hvað gerir stafla sérstakt er
Leiðin sem við setjum upplýsingar

24
00:01:04,430 --> 00:01:08,200
í stafla, og hvernig við
fjarlægja upplýsingar úr stafla.

25
00:01:08,200 --> 00:01:11,600
Einkum með stafla
reglan er aðeins mest

26
00:01:11,600 --> 00:01:15,830
bætt nýlega þáttur er hægt að fjarlægja.

27
00:01:15,830 --> 00:01:17,660
>> Svo hugsa um það eins og ef það er stakkur.

28
00:01:17,660 --> 00:01:21,170
Við erum hlóðust upplýsingar
ofan á sig,

29
00:01:21,170 --> 00:01:24,271
og aðeins eina efst
á staurnum er hægt að fjarlægja.

30
00:01:24,271 --> 00:01:27,020
Við getum ekki losnað við neitt undir
vegna þess að allt annað myndi

31
00:01:27,020 --> 00:01:28,020
hrynja og falla yfir.

32
00:01:28,020 --> 00:01:32,580
Svo við í raun ert að byggja upp stafla sem
við höfum þá að fjarlægja stykkjum.

33
00:01:32,580 --> 00:01:36,590
Vegna þessa að við vísa almennt
að stafla sem LIFO uppbyggingu,

34
00:01:36,590 --> 00:01:38,940
endast í, fyrst út.

35
00:01:38,940 --> 00:01:42,290
LIFO, endast inn, fyrst út.

36
00:01:42,290 --> 00:01:45,635
>> Svo vegna þessa takmörkun á
hvernig upplýsingar er hægt að bæta við

37
00:01:45,635 --> 00:01:49,080
og fjarlægð úr stafla, það er í raun
aðeins tveir hlutir sem við getum gert með stafla.

38
00:01:49,080 --> 00:01:52,010
Við getum ýta, sem er
tíma við notum til að bæta

39
00:01:52,010 --> 00:01:55,130
við nýju atriði til the toppur af the
stafla, eða ef stafla er ekki til

40
00:01:55,130 --> 00:01:58,550
og við erum að skapa það frá grunni,
skapa stafla í fyrsta sæti

41
00:01:58,550 --> 00:02:00,110
væri að þrýsta.

42
00:02:00,110 --> 00:02:04,990
Og þá skjóta, sem er tegund af CS
Hugtakið við notum til að fjarlægja nýlega

43
00:02:04,990 --> 00:02:08,330
bætt frumefni úr efsta hluta stafla.

44
00:02:08,330 --> 00:02:11,130
>> Þannig að við erum að fara að líta á bæði
gerð, bæði array byggir

45
00:02:11,130 --> 00:02:13,120
og tengda listanum byggt.

46
00:02:13,120 --> 00:02:14,870
Og við erum að fara að
byrja með array byggir.

47
00:02:14,870 --> 00:02:19,990
Svo hér er grunn hugmynd um hvað
array byggir stafla gögn uppbygging

48
00:02:19,990 --> 00:02:21,140
myndi líta út.

49
00:02:21,140 --> 00:02:23,740
Við höfum vélritað skilgreiningu hér.

50
00:02:23,740 --> 00:02:27,790
Inni að við höfum tvo menn
eða sviðum uppbyggingu.

51
00:02:27,790 --> 00:02:29,880
Við höfum fylki.

52
00:02:29,880 --> 00:02:32,400
Og aftur ég er að nota er
handahófskennt gögn tegund gildi.

53
00:02:32,400 --> 00:02:35,180
>> Þannig að þetta gæti verið hvaða gögn tegund,
INT bleikju eða einhver önnur gögn

54
00:02:35,180 --> 00:02:37,080
tegund þú áður búið.

55
00:02:37,080 --> 00:02:39,861
Þannig að við höfum fjölda stærð getu.

56
00:02:39,861 --> 00:02:44,010
Getu verið pund skilgreind stöðug,
kannski annars staðar í skrá okkar.

57
00:02:44,010 --> 00:02:47,550
Svo eftir þegar við þetta tiltekna
framkvæmd við erum afmarka

58
00:02:47,550 --> 00:02:49,800
okkur sem var yfirleitt
málið með fylki,

59
00:02:49,800 --> 00:02:53,170
sem við getum ekki virk búa,
þar er ákveðin tala

60
00:02:53,170 --> 00:02:55,450
staka hámarki sem
við getum sett í stafla okkar.

61
00:02:55,450 --> 00:02:57,930
Í þessu tilfelli er það þætti getu.

62
00:02:57,930 --> 00:03:00,310
>> Við stöndum einnig utan um
efst á stafla.

63
00:03:00,310 --> 00:03:04,350
Hvað þáttur er mest
nýlega bætt við stafla?

64
00:03:04,350 --> 00:03:07,470
Og svo við að halda utan um það
í breytu sem heitir ofan.

65
00:03:07,470 --> 00:03:11,692
Og allt þetta fær pakkað upp saman
í nýja tegund gagna kallast stakkur.

66
00:03:11,692 --> 00:03:13,400
Og þegar við erum búin
þetta nýja gögn gerð

67
00:03:13,400 --> 00:03:15,410
við getum meðhöndla það eins og
önnur gögn tegund.

68
00:03:15,410 --> 00:03:20,970
Við getum lýst stafla s, rétt eins og
við gætum gert int x, eða bleikju y.

69
00:03:20,970 --> 00:03:22,990
Og þegar við segjum stafla
s, vel hvað gerist

70
00:03:22,990 --> 00:03:26,420
er að við fá a setja af
minni til hliðar fyrir okkur.

71
00:03:26,420 --> 00:03:28,770
>> Í þessu tilfelli getu
Ég hef greinilega ákveðið

72
00:03:28,770 --> 00:03:33,470
er 10 vegna þess að ég hef fengið
einn af taginu stafla

73
00:03:33,470 --> 00:03:35,320
sem inniheldur tvær sviðum muna.

74
00:03:35,320 --> 00:03:38,330
An array, í þessu tilfelli er að fara
að vera array af heiltölur

75
00:03:38,330 --> 00:03:40,440
eins og raunin er í flestum dæmum mínum.

76
00:03:40,440 --> 00:03:43,996
Og annar heiltölubreytu
fær um að geyma á toppinn,

77
00:03:43,996 --> 00:03:45,870
The nýlega bætt
þáttur í stafla.

78
00:03:45,870 --> 00:03:50,290
Svo eitt stafla af því sem við
bara skilgreint lítur svona út.

79
00:03:50,290 --> 00:03:53,190
Það er kassi sem inniheldur
fylki af 10 hvað

80
00:03:53,190 --> 00:03:57,280
verður heiltölur í þessu tilfelli og
annar heiltölubreytu það í grænu

81
00:03:57,280 --> 00:04:00,010
að tilgreina efst á stafla.

82
00:04:00,010 --> 00:04:02,600
>> Til að stilla the toppur af the
stafla við segjum bara s.top.

83
00:04:02,600 --> 00:04:04,890
Það er hvernig við aðgang að
reit af uppbyggingu muna.

84
00:04:04,890 --> 00:04:10,460
s.top jafngildir 0 raun
er þetta að stafla okkar.

85
00:04:10,460 --> 00:04:12,960
Svo aftur að við höfum tvær aðgerðir
sem við getum gert núna.

86
00:04:12,960 --> 00:04:14,270
Við getum ýta og við getum skjóta.

87
00:04:14,270 --> 00:04:15,635
Við skulum byrja með ýta.

88
00:04:15,635 --> 00:04:18,260
Aftur, þrýsta er að bæta við nýjum
þáttur til the toppur á stafla.

89
00:04:18,260 --> 00:04:21,460
>> Svo hvað þurfum við að gera í
þetta array undirstaða framkvæmd?

90
00:04:21,460 --> 00:04:23,210
Jæja í Almennt
ýta virka er að fara

91
00:04:23,210 --> 00:04:26,160
að þurfa að sætta sig við
bendi á mánudaginn.

92
00:04:26,160 --> 00:04:28,610
Nú taka annað og hugsa um það.

93
00:04:28,610 --> 00:04:32,840
Hvers vegna viljum við taka
bendi á mánudaginn?

94
00:04:32,840 --> 00:04:36,830
Muna frá fyrri vídeó á
Variable Gildissvið og ábendingum,

95
00:04:36,830 --> 00:04:42,350
hvað myndi gerast ef við sendum bara
stafla, s frekar inn sem stiki?

96
00:04:42,350 --> 00:04:45,770
Hvað myndi reyndar vera liðin í það?

97
00:04:45,770 --> 00:04:49,430
Mundu að við erum að búa til afrit
þegar við gefa það til aðgerð

98
00:04:49,430 --> 00:04:51,160
nema við notum ábendingum.

99
00:04:51,160 --> 00:04:55,380
Og svo þessi aðgerð ýta þörfum
að samþykkja bendi á mánudaginn

100
00:04:55,380 --> 00:04:59,160
þannig að við erum í raun að breyta
stafla sem við ætlum að breyta.

101
00:04:59,160 --> 00:05:03,060
>> The annar hlutur ýta vill sennilega að
taka er gögn þáttur tegund gildi.

102
00:05:03,060 --> 00:05:06,970
Í þessu tilviki, aftur, heil tala sem
við erum að fara að bæta við efst á stafla.

103
00:05:06,970 --> 00:05:08,680
Þannig að við höfum fengið tvær breytur okkar.

104
00:05:08,680 --> 00:05:11,310
Hvað erum við að fara að
nú gera inni ýta?

105
00:05:11,310 --> 00:05:14,860
Jæja, einfaldlega, við erum bara að fara að bæta við
þessi þáttur til the toppur á stafla

106
00:05:14,860 --> 00:05:22,860
og þá breyta þar efst á
stafla er, að er punktur efst gildi.

107
00:05:22,860 --> 00:05:25,639
Svo er þetta það fall
yfirlýsing um að ýta

108
00:05:25,639 --> 00:05:27,680
getur litið eins og í
array byggir framkvæmd.

109
00:05:27,680 --> 00:05:30,967
>> Aftur er þetta ekki föst regla
sem þú gætir breyta þessu og hafa

110
00:05:30,967 --> 00:05:32,050
það verið á mismunandi vegu.

111
00:05:32,050 --> 00:05:33,840
Kannski s er lýst á heimsvísu.

112
00:05:33,840 --> 00:05:36,180
Og svo þú þarft ekki einu sinni
að gefa það er sem viðfang.

113
00:05:36,180 --> 00:05:39,125
Þetta er aftur bara
almenn mál fyrir ýta.

114
00:05:39,125 --> 00:05:41,000
Og það eru mismunandi
leiðir til að framkvæma það.

115
00:05:41,000 --> 00:05:42,810
En í þessu tilfelli okkar
ýta er að fara að taka

116
00:05:42,810 --> 00:05:48,540
tvær breytur, bendi á stafla og
a gögn þátturinn af gerðinni verðmæti, heiltala

117
00:05:48,540 --> 00:05:49,840
í þessu tilfelli.

118
00:05:49,840 --> 00:05:52,100
>> Þannig að við lýst s, við
sagði s.top jafngildir 0.

119
00:05:52,100 --> 00:05:55,969
Nú skulum ýta
númer 28 á mánudaginn.

120
00:05:55,969 --> 00:05:57,010
Jæja hvað þýðir það?

121
00:05:57,010 --> 00:05:59,600
Jæja nú
Efst á stafla er 0.

122
00:05:59,600 --> 00:06:01,350
Og svo er það í grundvallaratriðum
að fara að gerast er

123
00:06:01,350 --> 00:06:05,820
við erum að fara að halda fjölda
28 í array stað 0.

124
00:06:05,820 --> 00:06:09,540
Mjög einfalt, ekki satt, að
var efst og nú erum við gott að fara.

125
00:06:09,540 --> 00:06:12,910
Og þá þurfum við að breyta því sem
efst á stafla verður.

126
00:06:12,910 --> 00:06:15,130
Þannig að næst þegar
við ýta stak í,

127
00:06:15,130 --> 00:06:18,017
við erum að fara að geyma það í
array staðsetningu, sennilega ekki 0.

128
00:06:18,017 --> 00:06:20,100
Við viljum ekki að skrifa
hvað við setjum bara þarna.

129
00:06:20,100 --> 00:06:23,510
Og svo við verðum bara að fara á toppinn á 1.

130
00:06:23,510 --> 00:06:24,890
Það gerir líklega vit.

131
00:06:24,890 --> 00:06:28,940
>> Nú ef við viljum setja annar þáttur
á mánudaginn, segja að við viljum að ýta 33,

132
00:06:28,940 --> 00:06:33,190
Jæja núna erum við bara að fara að taka 33
og setja það á array staðsetningu númer

133
00:06:33,190 --> 00:06:37,580
1, og þá breyta efst okkar
stafla vera array staðsetningu númer tvö.

134
00:06:37,580 --> 00:06:40,650
Svo ef næsta skipti sem við viljum
ýta stak á mánudaginn,

135
00:06:40,650 --> 00:06:43,087
það verður sett í array stað 2.

136
00:06:43,087 --> 00:06:44,420
Og við skulum gera það einu sinni enn.

137
00:06:44,420 --> 00:06:45,753
Við munum ýta 19 burt af stafla.

138
00:06:45,753 --> 00:06:48,940
Við munum setja 19 í array stað 2
og breyta efst stafla okkar

139
00:06:48,940 --> 00:06:51,220
að vera array staðsetningu 3
þannig að ef við næstu

140
00:06:51,220 --> 00:06:54,780
þarf að gera ýta við erum gott að fara.

141
00:06:54,780 --> 00:06:56,980
>> OK, svo það er að þrýsta í hnotskurn.

142
00:06:56,980 --> 00:06:57,830
Hvað um pabbi?

143
00:06:57,830 --> 00:07:00,240
Svo er pabbi konar
hliðstæðu til að þrýsta.

144
00:07:00,240 --> 00:07:02,720
Það er hvernig við að fjarlægja gögn úr stafla.

145
00:07:02,720 --> 00:07:04,610
Og í almennar þarfir pop
að gera eftirfarandi.

146
00:07:04,610 --> 00:07:07,600
Það þarf að taka bendi á
stafla, aftur í almennu máli.

147
00:07:07,600 --> 00:07:10,480
Í sumum öðrum tilvikum gætir þú
hafa lýst stafla heimsvísu,

148
00:07:10,480 --> 00:07:13,910
í því tilviki að þú þarft ekki að gefa það
í því að hún hefur nú þegar aðgang að henni

149
00:07:13,910 --> 00:07:15,541
sem alþjóðlegt breytu.

150
00:07:15,541 --> 00:07:17,040
En hvað þá annað þurfum við að gera?

151
00:07:17,040 --> 00:07:21,000
Jæja við vorum incrementing
efst á stafla í ýta,

152
00:07:21,000 --> 00:07:24,050
þannig að við erum líklega að fara að vilja
að lækka efst á stafla

153
00:07:24,050 --> 00:07:25,009
í popp, ekki satt?

154
00:07:25,009 --> 00:07:26,800
Og svo auðvitað
við erum líka að fara til að vilja

155
00:07:26,800 --> 00:07:29,240
að skila gildi sem við fjarlægja.

156
00:07:29,240 --> 00:07:32,125
Ef við erum að bæta þætti, við viljum
að fá þætti út síðar,

157
00:07:32,125 --> 00:07:34,000
við líklega í raun
vilt geyma þá svo við

158
00:07:34,000 --> 00:07:36,490
ekki bara eyða þeim úr
stafla og þá gera ekkert með þeim.

159
00:07:36,490 --> 00:07:38,500
Almennt ef við erum
ýta og pabbi hér

160
00:07:38,500 --> 00:07:41,250
við viljum geyma þetta
upplýsingar á markvissan hátt

161
00:07:41,250 --> 00:07:43,250
og svo það þýðir ekki að gera
vit í að bara henda því.

162
00:07:43,250 --> 00:07:46,380
Svo þessi aðgerð ætti
líklega skila gildi til okkar.

163
00:07:46,380 --> 00:07:51,040
>> Svo er þetta það yfirlýsingu um pop
gæti litið út eins og það efst til vinstri.

164
00:07:51,040 --> 00:07:53,870
Þetta fall skilar
gögn af gerðinni gildi.

165
00:07:53,870 --> 00:07:56,320
Aftur höfum við verið að nota
heiltölur í gegn.

166
00:07:56,320 --> 00:08:01,916
Og það tekur bendi á mánudaginn og
il rök hennar eða eini breytu.

167
00:08:01,916 --> 00:08:03,040
Svo hvað er pop að fara að gera?

168
00:08:03,040 --> 00:08:07,990
Segjum að við viljum nú
skjóta stak burt af s.

169
00:08:07,990 --> 00:08:14,000
Svo man ég sagði að stafla eru síðustu
í, fyrst út, LIFO gögn uppbygging.

170
00:08:14,000 --> 00:08:17,855
Hvaða þáttur er fara að
fjarlægður úr stafla?

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

172
00:08:21,780 --> 00:08:24,150
Vissir þú giska 19?

173
00:08:24,150 --> 00:08:25,290
Þar sem þú vilt vera rétt.

174
00:08:25,290 --> 00:08:28,836
19 var síðasta þáttur við bætt við
stafla þegar við vorum að ýta þætti á,

175
00:08:28,836 --> 00:08:31,210
og svo það er að fara að fyrsta
þáttur sem fær eytt.

176
00:08:31,210 --> 00:08:34,780
Það er eins og ef við sögðum 28, og
þá erum við að setja 33 ofan á það,

177
00:08:34,780 --> 00:08:36,659
og við setjum 19 ofan á það.

178
00:08:36,659 --> 00:08:40,650
Eina þáttur sem við getum tekið burt er 19.

179
00:08:40,650 --> 00:08:45,019
>> Nú á myndinni hér það sem ég hef gert
er tegund af eytt 19 frá array.

180
00:08:45,019 --> 00:08:46,810
Það er í raun ekki
það sem við erum að fara að gera.

181
00:08:46,810 --> 00:08:48,934
Við erum bara að fara að eins konar
af þykjast það er ekki þar.

182
00:08:48,934 --> 00:08:51,441
Það er enn í
að minni staðsetningu,

183
00:08:51,441 --> 00:08:54,190
en við erum bara að fara að hunsa það
með því að breyta efst staflans okkar

184
00:08:54,190 --> 00:08:56,080
frá því að vera 3 til 2.

185
00:08:56,080 --> 00:08:58,720
Svo ef við vorum að nú ýta
annar þáttur á mánudaginn,

186
00:08:58,720 --> 00:09:00,720
það myndi yfir skrifa 19.

187
00:09:00,720 --> 00:09:03,990
>> En við skulum ekki fara í gegnum vandræði
um að eyða 19 úr stafla.

188
00:09:03,990 --> 00:09:05,830
Við getum bara láta það er ekki þar.

189
00:09:05,830 --> 00:09:11,107
Í þeim tilgangi að stafla það er farið ef
við að breyta efst til að vera 2 í stað 3.

190
00:09:11,107 --> 00:09:12,690
Allt í lagi, svo það var ansi mikið það.

191
00:09:12,690 --> 00:09:15,080
Það er allt sem við þurfum að gera
að skjóta stak af.

192
00:09:15,080 --> 00:09:16,090
Við skulum gera það aftur.

193
00:09:16,090 --> 00:09:18,610
Þannig að ég hef bent henni í rauðu hér að
benda að við erum að gera annað símtal.

194
00:09:18,610 --> 00:09:19,720
Við erum að fara að gera það sama.

195
00:09:19,720 --> 00:09:20,803
>> Svo hvað er að fara að gerast?

196
00:09:20,803 --> 00:09:23,670
Jæja, við erum að fara að geyma
33 í x og við erum að fara

197
00:09:23,670 --> 00:09:26,217
til að breyta efst á stafla til 1.

198
00:09:26,217 --> 00:09:29,050
Þannig að ef við vorum nú að ýta að
þáttur í stafla sem við erum

199
00:09:29,050 --> 00:09:31,610
að fara að gera núna,
hvað er að fara að gerast

200
00:09:31,610 --> 00:09:36,367
er að við erum að fara Skrifa yfir
array staðsetningu númer 1.

201
00:09:36,367 --> 00:09:38,950
Þannig að 33 voru eins konar vinstri
bak sem við lést bara

202
00:09:38,950 --> 00:09:44,390
er ekki þar lengur, við erum bara að fara
að clobber það og setja 40 þar í staðinn.

203
00:09:44,390 --> 00:09:46,290
Og svo auðvitað
þar sem við gert ýta,

204
00:09:46,290 --> 00:09:48,780
við erum að fara að hækka í
Efst á stafla frá: 1 til að 2

205
00:09:48,780 --> 00:09:50,950
þannig að ef við bætum nú
annar þáttur það verður

206
00:09:50,950 --> 00:09:54,700
fara í array staðsetningu númer tvö.

207
00:09:54,700 --> 00:09:57,590
>> Nú tengd listum eru önnur
leiðin til að innleiða stafla.

208
00:09:57,590 --> 00:10:01,210
Og ef þessari skilgreiningu hins
skjár lítur hér þekki þig,

209
00:10:01,210 --> 00:10:04,260
það er vegna þess að það lítur næstum
nákvæmlega það sama, í raun,

210
00:10:04,260 --> 00:10:07,790
það nokkuð mikið er einmitt
sama og eintengdan lista,

211
00:10:07,790 --> 00:10:11,990
ef þú manst frá umræðu okkar
ein tengd listum í öðru vídeó.

212
00:10:11,990 --> 00:10:15,510
Eina takmörkun hér
er fyrir okkur sem forritari,

213
00:10:15,510 --> 00:10:17,900
við erum ekki leyft að
setja inn eða eyða af handahófi

214
00:10:17,900 --> 00:10:20,620
frá eintengdan lista
sem við gætum áður gert.

215
00:10:20,620 --> 00:10:25,820
Við getum aðeins núna að setja inn og eyða úr
framan eða ofan á tengd

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

217
00:10:26,320 --> 00:10:28,028
Það er í raun eina
Munurinn þó.

218
00:10:28,028 --> 00:10:29,700
Þetta er annars eintengdan lista.

219
00:10:29,700 --> 00:10:32,060
Það er aðeins takmörkun
skipta á okkur

220
00:10:32,060 --> 00:10:35,770
sem forritari að
breytist það í stafla.

221
00:10:35,770 --> 00:10:39,280
>> Reglan hér er að alltaf að halda a
bendi á höfuð tengda listanum.

222
00:10:39,280 --> 00:10:41,520
Þetta er auðvitað almennt
mikilvægur regla fyrst.

223
00:10:41,520 --> 00:10:44,260
Fyrir eintengdan lista samt þér
þarf aðeins bendi á höfði

224
00:10:44,260 --> 00:10:46,160
í því skyni að hafa sem
keðja vera fær um að vísa

225
00:10:46,160 --> 00:10:48,596
að sérhver önnur frumefni
í tengda listanum.

226
00:10:48,596 --> 00:10:50,470
En það er sérstaklega
mikilvægt með stafla.

227
00:10:50,470 --> 00:10:52,386
Og svo almennt að þú ert
fara til raunverulega vilja

228
00:10:52,386 --> 00:10:54,090
þetta bendi til að vera alþjóðlegt breytu.

229
00:10:54,090 --> 00:10:56,574
Það er líklega að fara að
enn auðveldara þannig.

230
00:10:56,574 --> 00:10:58,240
Svo það eru hliðstæður ýta og popp?

231
00:10:58,240 --> 00:10:58,740
Hægri.

232
00:10:58,740 --> 00:11:01,812
Svo ýta aftur er að bæta
a nýr þáttur á mánudaginn.

233
00:11:01,812 --> 00:11:03,770
Í tengda listanum sem
þýðir að við erum að fara að hafa

234
00:11:03,770 --> 00:11:07,770
til að búa til nýjan hnút sem við erum
að fara að bæta inn í tengda listanum,

235
00:11:07,770 --> 00:11:10,500
og þá fylgja varfærin skref
sem við höfum lýst áður

236
00:11:10,500 --> 00:11:16,050
í ein tengd listum að bæta því við
keðja án þess að brjóta keðju

237
00:11:16,050 --> 00:11:18,900
og tapa eða orphaning eitthvað
þættir í tengda listanum.

238
00:11:18,900 --> 00:11:21,820
Og það er í rauninni það sem að
lítið Blob texta þar samantekt.

239
00:11:21,820 --> 00:11:23,740
Og við skulum taka a líta
á það sem skýringarmynd.

240
00:11:23,740 --> 00:11:24,823
>> Svo er hér tengd listi okkar.

241
00:11:24,823 --> 00:11:26,620
Það inniheldur samtímis fjóra þætti.

242
00:11:26,620 --> 00:11:30,420
Og meira fullkomlega Hér er okkar
stafla sem inniheldur fjóra þætti.

243
00:11:30,420 --> 00:11:36,030
Og við skulum segja að við viljum nú að
ýta nýtt atriði á þessa stafla.

244
00:11:36,030 --> 00:11:39,792
Og við viljum að ýta nýtt
atriði sem gildi gagnanna er 12.

245
00:11:39,792 --> 00:11:41,000
Jæja hvað erum við að fara að gera?

246
00:11:41,000 --> 00:11:43,420
Jæja fyrst við erum að fara að
malloc pláss, virk

247
00:11:43,420 --> 00:11:45,411
úthluta pláss fyrir nýja hnút.

248
00:11:45,411 --> 00:11:48,160
Og auðvitað strax eftir
við að hringja að malloc við alltaf

249
00:11:48,160 --> 00:11:52,989
ganga úr skugga um að athuga fyrir null,
því ef við fengum null aftur

250
00:11:52,989 --> 00:11:54,280
það var einhvers konar vandamál.

251
00:11:54,280 --> 00:11:57,570
Við viljum ekki að dereference þess null
bendillinn eða þú munt þjást seg kenna.

252
00:11:57,570 --> 00:11:58,510
Það er ekki gott.

253
00:11:58,510 --> 00:11:59,760
Þannig að við höfum malloced hnútarins.

254
00:11:59,760 --> 00:12:01,260
Við munum gera ráð sem við höfum haft árangur hér.

255
00:12:01,260 --> 00:12:06,090
Við erum að fara að setja 12 í
gögn sviði hnút.

256
00:12:06,090 --> 00:12:11,570
Nú þú manst hvaða ábendingum okkar
færist næsta þannig að við brjóta ekki keðju?

257
00:12:11,570 --> 00:12:15,100
Við hafa a par af valkostur hér en
sú eina sem er að fara til að vera örugg

258
00:12:15,100 --> 00:12:19,330
er að setja fréttir næsta músina til
benda á gamla höfuð á listanum

259
00:12:19,330 --> 00:12:21,360
eða hvað mun brátt vera
gamall yfirmaður lista.

260
00:12:21,360 --> 00:12:23,610
Og nú að allt okkar
þættir eru handjárnaða saman,

261
00:12:23,610 --> 00:12:27,370
við getum bara flutt lista til að benda
á sama stað sem nýtt gerir.

262
00:12:27,370 --> 00:12:33,550
Og við höfum nú í raun ýtt a
Ný þáttur framan á mánudaginn.

263
00:12:33,550 --> 00:12:36,420
>> Að skjóta Við bara vilja til að
eyða sem fyrst þáttur.

264
00:12:36,420 --> 00:12:38,150
Og svo í rauninni það
við þurfum að gera hér,

265
00:12:38,150 --> 00:12:40,050
vel við verðum að finna annað frumefni.

266
00:12:40,050 --> 00:12:43,540
Loksins að verða að nýjum
höfuð eftir að við eyða fyrsta.

267
00:12:43,540 --> 00:12:47,300
Þannig að við þurfum bara að byrja frá
upphaf, færa einn framherja.

268
00:12:47,300 --> 00:12:50,340
Þegar við höfum fengið að halda á einn
áfram þar sem við nú

269
00:12:50,340 --> 00:12:53,850
við erum getur eytt fyrsti örugglega
og þá getum við bara færa höfuðið

270
00:12:53,850 --> 00:12:57,150
til að benda á hvað var
Seinni tíma og þá nú

271
00:12:57,150 --> 00:12:59,170
er fyrsta eftir að
hnút hefur verið eytt.

272
00:12:59,170 --> 00:13:01,160
>> Svo aftur, taka a líta
á það sem skýringarmynd við

273
00:13:01,160 --> 00:13:05,022
viljum nú skjóta að
þáttur burt af þessum stafla.

274
00:13:05,022 --> 00:13:05,730
Svo hvað eigum við að gera?

275
00:13:05,730 --> 00:13:08,188
Jæja við erum fyrst að fara að búa til
ný músina sem er að fara

276
00:13:08,188 --> 00:13:10,940
til að benda á sama stað og höfuðið.

277
00:13:10,940 --> 00:13:13,790
Við erum að fara að flytja það eina stöðu
áfram með því að segja Trav jafn

278
00:13:13,790 --> 00:13:17,510
Trav næst til dæmis, þar sem
myndi fara á Trav músina einn

279
00:13:17,510 --> 00:13:19,324
stöðu áfram.

280
00:13:19,324 --> 00:13:21,240
Nú þegar við höfum fengið
halda á fyrstu frumefni

281
00:13:21,240 --> 00:13:24,573
gegnum músina heitir listanum og er
Annað þáttur gegnum bendi heitir

282
00:13:24,573 --> 00:13:28,692
Trav, getum við örugglega eyða að
Fyrsti þátturinn úr stafla

283
00:13:28,692 --> 00:13:30,650
án þess að missa restina
keðjunni vegna þess að við

284
00:13:30,650 --> 00:13:32,358
hafa a vegur til að vísa
við annað frumefni

285
00:13:32,358 --> 00:13:34,780
senda með því að í
bendi heitir Trav.

286
00:13:34,780 --> 00:13:37,100
>> Svo nú getum við frjáls hnút.

287
00:13:37,100 --> 00:13:38,404
Við getum frjáls lista.

288
00:13:38,404 --> 00:13:41,320
Og þá er allt sem við þurfum að gera núna
færa lista til að benda á sama stað

289
00:13:41,320 --> 00:13:44,482
sem trav gerir, og við erum svona aftur
þar sem við byrjuðum áður en við ýtt 12

290
00:13:44,482 --> 00:13:45,690
á í fyrsta sæti, ekki satt.

291
00:13:45,690 --> 00:13:46,940
Þetta er einmitt þar sem við vorum.

292
00:13:46,940 --> 00:13:48,840
Við áttum fjóra þátturinn stafla.

293
00:13:48,840 --> 00:13:49,690
Við bætt við fimmta.

294
00:13:49,690 --> 00:13:51,910
Við ýtt fimmtungur
þáttur á, og þá erum við

295
00:13:51,910 --> 00:13:55,980
smella sem nýlega
bætt þáttur aftur burt.

296
00:13:55,980 --> 00:13:58,816
>> Það er í raun ansi mikið
allt sem er til stafla.

297
00:13:58,816 --> 00:14:00,190
Þú getur innleiða þá sem fylki.

298
00:14:00,190 --> 00:14:01,815
Þú getur innleiða þá sem tengd listum.

299
00:14:01,815 --> 00:14:04,810
Það eru, Að sjálfsögðu henta önnur
leiðir til að framkvæma þær eins og heilbrigður.

300
00:14:04,810 --> 00:14:09,060
Í grundvallaratriðum er ástæða þess að við myndum nota
stafla er að halda gögnum á þann hátt

301
00:14:09,060 --> 00:14:12,090
að nýlega bætt
þáttur er það fyrsta sem við erum

302
00:14:12,090 --> 00:14:14,980
fara til að vilja fá til baka.

303
00:14:14,980 --> 00:14:17,900
Ég er Doug Lloyd, þetta er CS50.

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