DOUG LLOYD: Ceart go leor, mar sin ag an bpointe seo tá tú
is dócha ar an eolas go leor le arrays agus liostaí nasctha
a bhfuil an dá bunscoile struchtúir sonraí tá muid
Labhair faoi do thacair de a choinneáil sonraí de chineálacha sonraí den chineál céanna eagraithe.
>> Anois, tá muid ag dul chun labhairt faoi ​​cúpla athruithe
ar arrays agus liostaí nasctha.
Sa físeán seo, táimid ag dul chun labhairt faoi stoic.
Go sonrach táimid ag dul chun labhairt faoi ​​struchtúr sonraí dtugtar Stack.
Athghairm ó phlé roimhe seo faoi ​​threo agus cuimhne,
go bhfuil an chairn freisin an ainm le haghaidh deighleog de chuimhne
i gcás ina ndearbhaítear statically cuimhne memory-- go bhfuil tú
ainm, athróga a ainm duit, et frámaí cetera agus feidhm a againn chomh maith
frámaí Stack glaoch ann.
Mar sin, tá sé seo le struchtúr sonraí Stack Ní le teascán Stack de chuimhne.
OK.
>> Ach cad é Stack?
Mar sin tá sé go leor i bhfad ach cineál speisialta an déanmhais
go gcoimeádann sonraí ar bhealach eagraithe.
Agus níl dhá an- bealaí a chur chun feidhme
cruacha ag baint úsáide as dhá struchtúr sonraí go bhfuil muid eolas maidir leis cheana féin,
arrays agus liostaí nasctha.
Cad a dhéanann é speisialta Stack an tslí ina chuir muid eolas
isteach an chairn, agus ar an mbealach ina ndéanaimid eolas ó an chairn a bhaint.
Go háirithe le stoic is é an riail ach amháin an chuid is mó
le déanaí Is féidir an ghné seo a leanas a chur as oifig.
>> Mar sin, smaoineamh ar é mar má tá sé ina chairn.
Táimid ag piling faisnéis ar bharr féin,
agus gan ach an rud ag an mbarr Is féidir an carn a chur as oifig.
Ní féidir linn a bhaint as an rud thíos toisc go mbeadh gach rud eile
collapse agus titim os a chionn.
Mar sin, táimid i ndáiríre ag tógáil Stack go ní mór dúinn ansin píosa a bhaint de phíosa.
Mar gheall ar seo táimid ag tagairt go coitianta go Stack mar struchtúr LIFO,
go deireanach i, an chéad amach.
LIFO, go deireanach i, an chéad amach.
>> Mar sin, mar gheall ar seo srian le conas is féidir faisnéis a chur leis
agus a chur as Stack, níl i ndáiríre ach dhá rud is féidir linn a dhéanamh le Stack.
Is féidir linn a bhrú, a bhfuil an téarma a úsáidimid le cur le coinníollacha
gné nua chun an barr an Stack, nó más rud é nach bhfuil an chairn ann
agus táimid ag a chruthú sé ó thús, ag cruthú an chairn ar an gcéad dul
bheadh ​​ag brú.
Agus ansin pop, go bhfuil an saghas CS téarma linn a úsáid a bhaint as an chuid is mó le déanaí
eilimint chur leis ó bharr an chairn.
>> Mar sin, táimid ag dul chun breathnú ar an dá implementations, idir eagar atá bunaithe
agus liosta a nasctha bunaithe.
Agus táimid ag dul chun tús a chur le sraith bunaithe.
Mar sin, tá anseo an smaoineamh bunúsach ar cad a an struchtúr sonraí Stack eagar bunaithe
Bheadh ​​cuma mhaith.
Ní mór dúinn a shainmhíniú clóscríofa anseo.
Taobh istigh de go bhfuil muid dhá chomhalta nó réimsí an struchtúir.
Ní mór dúinn le sraith.
Agus arís mé ag baint úsáide as an luach cineál sonraí treallach.
>> Mar sin d'fhéadfadh sé seo a bheith de chineál ar bith sonraí, Char slánuimhir nó sonraí éigin eile
cineál chruthaigh tú cheana.
Mar sin, ní mór dúinn le sraith de acmhainn méid.
Cumas a bheith punt sainithe tairiseach, b'fhéidir áit éigin eile in ár gcomhad.
Mar sin, faoi deara cheana féin leis seo go háirithe cur i bhfeidhm táimid theorainn
dúinn féin mar a bhí de ghnáth an cás le arrays,
nach féidir linn a Athraigh dinimiciúil, i gcás ina níl líon áirithe
na n-eilimintí uasmhéid is Is féidir linn a chur in ár chairn.
Sa chás seo, tá sé gnéithe acmhainne.
>> Coinneoimid freisin súil a choinneáil ar barr an chairn.
Cad eilimint é an chuid is mó leis le déanaí leis an chairn?
Agus mar sin a choinneáil orainn súil a choinneáil ar a i athróg ar a dtugtar barr.
Agus seo ar fad faigheann fillte suas le chéile i ndáil le cineál sonraí nua ar a dtugtar Stack.
Agus nuair a bhíonn muid a cruthaíodh an cineál nua sonraí
is féidir linn a chóireáil sé cosúil aon chineál sonraí eile.
Is féidir linn a dhearbhú Stack s, díreach cosúil féidir linn a dhéanamh slánuimhir x, y nó Char.
Agus nuair a rá linn a Stack s, go maith cad a tharlaíonn
Tá fháil againn sraith de cuimhne ar leataobh dúinn.
>> Sa cháil cás Tá mé cinneadh déanta cosúil
Is 10 mar tá fuair mé athróg amháin de chineál chairn
ina bhfuil dhá réimsí cuimhne.
Tá sraith, sa chás seo ag dul a bheith le sraith de slánuimhreacha
mar is amhlaidh sa chuid is mó de mo samplaí.
Agus athróg slánuimhir eile in ann a stóráil an barr,
an chur leis an chuid is mó le déanaí eilimint leis an chairn.
Mar sin, aon Stack amháin de cad againn díreach sainithe Breathnaíonn mar seo.
Tá sé bosca ina bhfuil le sraith de 10 cad
Beidh slánuimhreacha sa chás seo agus athróg slánuimhir eile ann i glas
a chur in iúl ar an barr an chairn.
>> A shocrú ar an barr an Stack linn a rá ach s.top.
Sin é an chaoi a chuirimid ar rochtain a fháil ar réimse dtagann aisghlaoch struchtúr.
s.top cothrom le 0 héifeachtach mbaineann sé seo chun ár chairn.
Mar sin, arís tá dhá oibríochtaí gur féidir linn a dhéanamh anois.
Is féidir linn a bhrú agus is féidir linn pop.
A ligean ar tús a chur le bhrú.
Arís, ag brú go bhfuil cur nua eilimint go barr an chairn.
>> Mar sin, cad a dhéanann gá dúinn a dhéanamh i an eagar a chur i bhfeidhm atá bunaithe ar?
Go maith sa gcoitinne Tá feidhm bhrú ag dul
go mór chun glacadh le pointeoir chuig an chairn.
Anois a ghlacadh an dara agus smaoineamh air.
Cén fáth go mbeadh muid ag iarraidh a glacadh pointeoir chuig an chairn?
Athghairm ó físeáin roimhe seo ar raon feidhme athraitheach agus leideanna,
cad a tharlódh má sheoltar muid díreach Stack s, in áit i mar pharaiméadar?
Cad é a chur ar aghaidh i ndáiríre i ann?
Cuimhnigh táimid ag cruthú cóip nuair a théann muid é le feidhm
ach amháin má úsáidimid leideanna.
Agus mar sin an fheidhm seo riachtanais a bhrú glacadh le pointeoir chuig an chairn
ionas go mbeidh muid ag athrú go hiarbhír an chairn ar intinn againn a athrú.
>> An rud bhrú eile ba mhaith leis is dócha go Is gné sonraí de luach chineál glacadh leis.
Sa chás seo, arís, slánuimhir go táimid ag dul a chur leis an barr an chairn.
Mar sin, tá muid fuair ár dhá paraiméadair.
Cad tá muid ag dul go dtí anois a dhéanamh taobh istigh de bhrú?
Bhuel, go simplí, táimid ag dul díreach a chur an ghné go dtí an barr an chairn
agus ansin a athrú i gcás an barr is é an chairn, go s luach is fearr ponc.
Mar sin, is é seo cad feidhm dearbhú bhrú
D'fhéadfadh cuma mhaith ar sraith-bhunaithe a chur chun feidhme.
>> Arís nach bhfuil an riail crua agus go tapa go bhféadfaí tú a athrú seo agus tá
Athraíonn sé ar bhealaí éagsúla.
B'fhéidir go bhfuil s dhearbhú ar fud an domhain.
Agus mar sin ní gá duit fiú chun pas a fháil go bhfuil sé mar pharaiméadar.
Tá sé seo arís ach cás ginearálta le haghaidh bhrú.
Agus tá go difriúil bealaí a chur i bhfeidhm.
Ach sa chás seo ár Tá bhrú ag dul a ghlacadh
dhá argóint, pointeoir chuig Stack agus eilimint sonraí a bhfuil luach de chineál, slánuimhir
sa chás seo.
>> Mar sin, a dhearbhú linn a s, táimid ag Dúirt ionann s.top 0.
Anois, a ligean ar a bhrú ar an uimhir 28 ar an chairn.
Bhuel cad a chiallaíonn?
Bhuel faoi láthair ar an Is barr an chairn 0.
Agus mar sin cad atá go bunúsach ag dul le tarlú go bhfuil
táimid ag dul chun bata leis an uimhir 28 i suíomh eagar 0.
Pretty simplí, ceart, go ba é an barr agus anois tá muid go maith chun dul.
Agus ansin is gá dúinn a athrú ar cad Beidh an barr an chairn a bheith.
Ionas go mbeidh an chéad uair eile a bhrú linn a gné i,
táimid ag dul chun é a stóráil i suíomh eagar, is dócha nach bhfuil 0.
Nílimid ag iarraidh a fhorscríobh cad a chuir muid díreach ann.
Agus mar sin beidh muid ag bogadh ach an barr a 1.
Sin a dhéanann ciall dócha.
>> Anois, más mian linn a chur ar gné eile isteach ar an chairn, a rá ba mhaith linn a bhrú 33,
go maith anois táimid ag dul ach a ghlacadh 33 agus é a chur ag uimhir suíomh eagar
1, agus ansin a athrú an barr ár Stack a bheith eagar dhá uimhir suíomh.
Mar sin, más rud é an chéad uair eile ba mhaith linn a eilimint a bhrú isteach ar an chairn,
beidh sé a chur i suíomh eagar 2.
Agus a ligean ar é sin a dhéanamh níos mó ama amháin.
Beidh muid a bhrú 19 uaire an stacks.
Beidh muid a chur ar 19 i suíomh eagar 2 agus athrú ar an bharr ár chairn
a bheith suíomh eagar 3 mar sin más rud é an chéad uair eile a chuirimid ar
Ní mór a dhéanamh a bhrú táimid go maith chun dul.
>> OK, mar sin go bhfuil ag brú i nutshell.
Cad mar gheall ar popping?
Dá bhrí sin tá popping an saghas mhacasamhail a brú.
Tá sé conas a sonraí a bhaint as an chairn.
Agus riachtanais pop gcoitinne a dhéanamh ar an méid seo a leanas.
Caithfidh sé a glacadh le pointeoir chuig an Stack, arís sa chás go ginearálta.
I gcás eile, d'fhéadfadh tú roinnt dhearbhú an chairn ar fud an domhain,
agus sa chás sin ní gá duit a pas a fháil sé i toisc go bhfuil sé cheana rochtain air
mar athróg domhanda.
Ach ansin cad eile a dhéanamh is gá dúinn a dhéanamh?
Bhuel bhí muid ag incriminteach barr an chairn i bhrú,
mar sin táimid ag dul is dócha a iarraidh chun decrement an barr an chairn
i pop, ceart?
Agus ansin ar ndóigh táimid ag dul freisin chun iarraidh
a thabhairt ar ais ar an luach a bhaint againn.
Má tá muid ag cur gnéithe, ba mhaith linn chun eilimintí fháil amach níos déanaí,
táimid ag is dócha i ndáiríre ag iarraidh chun iad a stóráil mar sin againn
ná scrios ach iad as an Stack agus ansin a dhéanamh rud ar bith leo.
Go ginearálta má tá muid ag brú agus a popping anseo
ba mhaith linn a stóráil seo faisnéis ar bhealach bríoch
agus mar sin ní dhéanann sé a dhéanamh ciall a scriosadh ach é.
Mar sin, ba chóir an fheidhm seo is dócha go bhfuil luach ar ais chugainn.
>> Mar sin, is é seo cad dearbhú do pop D'fhéadfadh cuma mhaith ann ag an mbarr clé.
Seo tuairisceáin fheidhm sonraí de luach chineál.
Arís tá muid ag baint úsáide as slánuimhreacha ar fud.
Agus glacann sé pointeoir a Stack mar a argóint aonair nó paraiméadar amháin.
Mar sin, cad é pop ag dul a dhéanamh?
Ligean le rá ba mhaith linn a anois pop gné uaire de s.
Mar sin, cuimhnigh a dúirt mé go bhfuil stoic caite i, amach ar dtús, LIFO struchtúir sonraí.
Cé acu eilimint ag dul chun a chur as an chairn?
An raibh tú buille faoi thuairim 19?
Toisc gur mhaith leat a bheith ceart.
Bhí an ghné dheireanach chuir muid go dtí an 19 Stack nuair a bhí na heilimintí brú dúinn ar,
agus mar sin tá sé ag dul go dtí an chéad eilimint go bhfaigheann bhaint astu.
Tá sé mar má dúirt muid 28, agus ansin chuir muid 33 ar a bharr,
agus chuir muid 19 ar a bharr sin.
Is é an ghné amháin is féidir linn a éirí de thalamh 19.
>> Anois sa léaráid anseo cad atá déanta agam Tá saghas a scriosadh 19 ó na eagar.
Ní sin i ndáiríre cad tá muid ag dul a dhéanamh.
Táimid ag dul díreach a chineál de ligean nach bhfuil sé ann.
Tá sé fós ann i go suíomh chuimhne,
ach táimid ag dul díreach chun neamhaird a dhéanamh air ag athrú an bharr ár chairn
ó bheith 3-2.
Mar sin má bhí muid a bhrú anois eilimint eile isteach ar an chairn,
bheadh ​​sé ag scríobh níos mó ná 19.
>> Ach a ligean ar nach dul tríd an deacracht de a scriosadh 19 as an chairn.
Is féidir linn a ligean ach nach bhfuil sé ann.
Chun críocha an chairn tá sé imithe más rud é athraíonn muid an barr a bheith 2 in ionad 3.
Ceart go leor, mar sin go raibh go leor i bhfad é.
Sin go léir is gá dúinn a dhéanamh a pop gné amach.
A ligean ar é a dhéanamh arís.
Mar sin, tá mé béim air i dearg anseo Léiríonn táimid ag déanamh glao eile.
Táimid ag dul a dhéanamh ar an rud céanna.
>> Mar sin, cad atá ar siúl le tarlú?
Bhuel, táimid ag dul a stóráil 33 in x agus táimid ag dul
a athrú ar an barr an chairn go 1.
Ionas go má bhí muid anois a bhrú ar eilimint isteach an chairn a bhfuil muid
ag dul a dhéanamh ceart anois, cad atá ar siúl le tarlú
Tá táimid ag dul forscríobh eagar uimhir suíomh 1.
Mar sin, go 33 gur saghas chlé taobh thiar de sin lig againn ach
nach bhfuil ann níos mó, táimid ag dul díreach a clobber é agus chuir 40 ann ina ionad.
Agus ansin ar ndóigh, ós rud é a rinne muid a bhrú,
táimid ag dul chun incrimint an barr an chairn 1-2
ionas go má táimid a chur anois eilimint eile Feicfidh sé
dul i sraith dhá uimhir suíomh.
>> Anois tá liostaí nasctha eile bhealach chun stoic a chur i bhfeidhm.
Agus má sainmhíniú seo ar an Breathnaíonn an scáileán anseo eolas a thabhairt duit,
tá sé mar tá sé beagnach díreach mar an gcéanna, i ndáiríre,
tá sé go leor i bhfad go díreach ar an mar liosta nasctha ina n-aonar céanna,
má tá tú chun cuimhne as ár plé ar ina n-aonar liostaí nasctha i físeán eile.
An srian amháin anseo Is le haghaidh dúinn mar ríomhchláraitheoirí,
ní táimid cead chur isteach nó a scriosadh randamach
ón liosta nasctha ina n-aonar a d'fhéadfadh muid a dhéanamh roimhe seo.
Is féidir linn a chur isteach ach amháin anois agus scrios ó an tosaigh nó barr an nasctha
liosta.
Sin i ndáiríre an t-aon difríocht cé.
Tá sé seo ar shlí eile liosta nasctha ina n-aonar.
Tá sé ach an srian in áit ar dúinn féin
mar ríomhchláraitheoirí go athruithe sé isteach Stack.
>> Is é an riail anseo a choimeád ar bun i gcónaí pointeoir chuig ceann liosta nasctha.
Tá sé seo ar ndóigh go ginearálta riail chéad tábhachtach.
Le haghaidh nasctha ina n-aonar liosta mar sin féin agat gá ach pointeoir chun an ceann
d'fhonn go mbeadh go slabhra a bheith in ann a tharchur
gach gné eile ar an liosta nasctha.
Ach tá sé go háirithe tábhachtach le Stack.
Agus mar sin go ginearálta go bhfuil tú ag dul go dtí mhaith iarbhír
an pointeoir a bheith ina domhanda athraitheach.
Tá sé ag dul is dócha go a bheith níos éasca go bhealach.
Mar sin, cad iad na analogs de bhrú agus pop?
Ceart.
Mar sin, ag brú arís ag cur gné nua chun an chairn.
I liosta nasctha go ciallaíonn táimid ag dul go bhfuil
a chruthú nód nua go mbeimid dul a chur isteach ar an liosta nasctha,
agus ansin lean na céimeanna go cúramach go atá leagtha amach againn roimhe
i liostaí nasctha ina n-aonar chun é a chur le an slabhra gan briseadh an slabhra
agus a chailliúint nó a orphaning aon gnéithe den liosta nasctha.
Agus sin go bunúsach cad a Blob beag de théacs achoimre ann.
Agus a ligean ar ghlacadh le breathnú ar sé mar léaráid.
>> Mar sin, tá anseo ar ár liosta nasctha.
Tá sé i gcomhthráth ceithre ghné.
Agus níos foirfe anseo ar ár Stack ina bhfuil ceithre ghné.
Agus a ligean le rá ba mhaith linn anois a bhrú mír nua isteach ar an chairn.
Agus ba mhaith linn a bhrú nua Tá mír a bhfuil a luach shonraí 12.
Bhuel cad tá muid ag dul a dhéanamh?
Bhuel ar dtús táimid ag dul chun spás malloc, dinimiciúil
spás a leithdháileadh le haghaidh nód nua.
Agus ar ndóigh díreach tar éis a théimid ar glaoch a malloc againn i gcónaí
a dhéanamh cinnte a sheiceáil le haghaidh null, mar má fuair muid ar ais null
bhí de chineál éigin fhadhb.
Ní chuirimid iarraidh a téigh i sin null Beidh pointeoir nó tú ag fulaingt locht seg.
Ní Sin maith.
Mar sin, tá muid malloced an nód.
Beidh muid glacadh leis a bhí againn rath anseo.
Táimid ag dul a chur i 12 an réimse sonraí an nód.
Anois a dhéanann tú a thabhairt chun cuimhne a bhfuil ár n-leideanna bogann ar aghaidh mar sin ní féidir linn a bhriseadh an slabhra?
Ní mór dúinn cúpla roghanna anseo ach an ceann amháin go bhfuil dul a bheith sábháilte
Tá nuacht chugainn pointeoir go a shocrú pointe ar an ceann d'aois ar an liosta
nó cad a bheidh go luath ar an ceann d'aois ar an liosta.
Agus anois go bhfuil gach ceann dár heilimintí atá chained le chéile,
Is féidir linn bogadh go díreach liosta a chur in iúl go dtí an áit chéanna go ndéanann nua.
Agus ní mór dúinn anois bhrú héifeachtach eilimint nua isteach ar an os comhair an chairn.
>> A pop muid ach ag iarraidh a scrios go chéad eilimint.
Agus mar sin go bunúsach cad ní mór dúinn a dhéanamh anseo,
go maith ní mór dúinn a fháil ar an dara gné.
Faoi dheireadh beidh a bheith ar an nua ceann i ndiaidh a scriosadh muid a an chéad cheann.
Mar sin, ní mór dúinn ach chun tús a chur as an tús, dul ar aghaidh amháin.
Chomh luath agus tá muid fuair a shealbhú ar cheann amháin ar aghaidh ar an áit ina againn faoi láthair
Tá féidir linn a scriosadh an chéad cheann go sábháilte agus ansin is féidir linn bogadh ach an ceann
a chur in iúl leis an méid a bhí an dara téarma agus ansin anois
Is é an chéad uair tar éis sin Tá nód Scriosadh.
>> Mar sin arís, ag cur le breathnú ar sé mar léaráid linn a
ag iarraidh a pop anois eilimint uaire den chairn.
Mar sin, cad a dhéanaimid?
Bhuel táimid ag dul ar dtús a chruthú pointeoir nua go bhfuil dul
a chur in iúl ar an láthair céanna leis an ceann.
Táimid ag dul a bhogadh suíomh amháin ar aghaidh ag rá ionann trav
Trav romhainn mar shampla, a Bheadh ​​cinn an ceann pointeoir trav
seasamh ar aghaidh.
Anois go atá againn fuair shealbhú ar an chéad eilimint
tríd an liosta pointeoir ar a dtugtar, agus an dara gné trí pointeoir ar a dtugtar
trav, is féidir linn a scriosadh go sábháilte go chéad eilimint as an chairn
gan chailliúint an chuid eile an slabhra mar gheall orainn
bheith ar bhealach a tharchur leis an dara gné
ar aghaidh trí na pointeoir ar a dtugtar trav.
>> Mar sin, anois is féidir linn saor in aisce go nód.
Is féidir linn a saor in aisce liosta.
Agus ansin go léir is gá dúinn a dhéanamh anois bogadh an liosta go dtí pointe go dtí an áit chéanna
ndéanann trav, agus táimid saghas ais nuair a thosaigh muid roimh bhrú orainn 12
ar an gcéad dul, ceart.
Tá sé seo díreach nuair a raibh muid.
Bhí orainn seo ceithre eilimint chairn.
Chuir muid an cúigiú.
Bhrú orainn an cúigiú eilimint ar, agus ansin dúinn
popped an chuid is mó le déanaí eilimint chuirtear ar ais as.
>> Sin i ndáiríre go leor i bhfad léir go bhfuil a cruacha.
Is féidir leat iad a chur i bhfeidhm mar arrays.
Is féidir leat iad a chur i bhfeidhm le liostaí nasctha.
Tá, ar ndóigh, eile bealaí chun iad a chur i bhfeidhm chomh maith.
Go bunúsach ar an gcúis ba mhaith linn a úsáid Tá stoic sonraí sa chaoi a chothabháil
go bhfuil an bhreisluacha is déanaí Is é an ghné an chéad rud táimid
dul go dtí mhaith a fháil ar ais.
Tá mé Doug Lloyd, is é seo CS50.