DOUG LLOYD: zote haki, hivyo kwa hatua hii uko
pengine pretty ukoo na arrays na orodha wanaohusishwa
ambayo ni ya msingi mbili miundo data tumekuwa
kuongelea kwa ajili ya kuweka seti ya data ya aina hiyo data kupangwa.
>> Sasa sisi ni kwenda kuzungumza juu ya wanandoa wa tofauti
juu ya arrays na orodha wanaohusishwa.
Katika video hii tunakwenda kuzungumzia mwingi.
Hasa sisi ni kwenda kuzungumza kuhusu muundo data kuitwa stack.
Kumbuka kutoka mijadala iliyopita kuhusu kuyatumia na kumbukumbu,
kuwa stack pia ni jina kwa sehemu ya kumbukumbu
ambapo statically alitangaza memory-- kumbukumbu kwamba wewe
jina, vigezo kwamba wewe jina, et kadhalika na kazi muafaka na sisi pia
muafaka wito mkusanyiko kuwepo.
Hivyo hii ni muundo wa mkusanyiko data si stack sehemu ya kumbukumbu.
SAWA.
>> Lakini ni nini stack?
Hivyo ni pretty much tu aina maalum ya muundo wa
kwamba inao data katika njia kupangwa.
Na kuna mawili sana njia ya kawaida ya kutekeleza
mwingi kwa kutumia miundo mbili data kuwa tuko tayari ukoo na,
arrays na orodha wanaohusishwa.
Kinachofanya mkusanyiko maalum ni njia ambayo sisi kuweka taarifa
kwenye mkusanyiko, na njia ya sisi kuondoa habari kutoka stack.
Hasa na mwingi utawala ni tu zaidi
hivi karibuni aliongeza kipengele inaweza kuondolewa.
>> Hivyo kufikiri juu yake kana kwamba ni stack.
Sisi ni piling taarifa juu ya yenyewe,
na tu kitu juu ya rundo inaweza kuondolewa.
Hatuwezi kuondoa kitu chini kwa sababu kila kitu kingine ingekuwa
kuanguka na kuanguka juu.
Hivyo sisi kweli ni kujenga stack kwamba sisi kisha una kuondoa kipande kwa kipande.
Kwa sababu hiyo sisi kawaida rejea kwa stack kama muundo LIFO,
mwisho katika, nje ya kwanza.
LIFO, mwisho katika, kwanza nje.
>> Hivyo kwa sababu ya kizuizi juu ya hii jinsi habari unaweza kuongezwa kwa
na kuondolewa kutoka stack, kuna kweli mambo mawili tu tunaweza kufanya na stack.
Tunaweza kushinikiza, ambayo ni mrefu sisi kutumia kwa ajili ya kuongeza
kipengele mpya juu ya stack, au kama stack haipo
na sisi ni kujenga ni kutoka mwanzo, kujenga stack katika nafasi ya kwanza
itakuwa kusukuma.
Na kisha pop, hiyo ni aina ya CS mrefu sisi kutumia ili kuondoa hivi karibuni
aliongeza kipengele kutoka juu ya stack.
>> Hivyo sisi ni kwenda kuangalia wote utekelezaji, wote safu msingi
na orodha wanaohusishwa msingi.
Na tunakwenda kuanza na safu ya msingi.
Hivyo hapa ni wazo la msingi la nini safu msingi muundo stack data
bila kuangalia kama.
Tuna typed ufafanuzi hapa.
Ndani ya kwamba tuna wanachama wawili au mashamba ya muundo.
Tuna safu.
Na tena mimi nina kutumia holela aina data thamani.
>> Hivyo hii inaweza kuwa aina yoyote data, int char au baadhi ya data mengine
aina wewe hapo awali kuundwa.
Hivyo tuna safu ya ukubwa uwezo.
Uwezo kuwa pauni inavyoelezwa mara kwa mara, labda mahali pengine katika faili wetu.
Hivyo taarifa tayari kwa hii hasa utekelezaji sisi ni bounding
wenyewe kama alikuwa kawaida kesi na arrays,
ambayo hatuwezi dynamically resize, ambapo kuna idadi fulani
ya mambo ya kiwango cha juu kwamba tunaweza kuweka katika stack yetu.
Katika kesi hiyo ni mambo uwezo.
>> Sisi pia kuweka wimbo wa juu ya stack.
Nini kipengele ni zaidi hivi karibuni aliongeza kwa stack?
Na hivyo sisi kuweka wimbo wa kwamba katika variable kuitwa juu.
Na hii yote anapata ilimalizika pamoja ndani ya mwezi aina data aitwaye stack.
Na mara moja sisi ni umba hii aina mpya data
tunaweza kutibu kama Aina ya data nyingine yoyote.
Tunaweza kutangaza stack s, kama vile tunaweza kufanya int x, au char y.
Na wakati sisi kusema stack s, pamoja kile kinachotokea
ni sisi kupata seti ya kumbukumbu zilizotengwa kwa ajili yetu.
>> Katika uwezo huu kesi Nimekuwa inaonekana aliamua
ni 10 kwa sababu mimi nimepata kutofautiana moja ya aina stack
ambayo ina mashamba mawili kukumbuka.
Safu, katika kesi hii ni kwenda kuwa safu ya integers
kama ilivyo katika maeneo mengi ya mifano yangu.
Na mwingine kutofautiana integer uwezo wa kuhifadhi juu,
hivi karibuni aliongeza kipengele kwa stack.
Hivyo moja mkusanyiko wa kile sisi tu kuelezwa inaonekana kama hii.
Ni sanduku zenye safu ya 10 nini
itakuwa integers katika kesi hii na mwingine kutofautiana integer huko katika kijani
zinaonyesha juu ya stack.
>> Kuweka juu ya stack sisi tu kusema s.top.
Hiyo ni jinsi sisi kupata uwanja wa muundo kukumbuka.
s.top sawa na 0 ufanisi gani hii kwa stack yetu.
Hivyo tena tuna shughuli mbili tuweze kufanya sasa.
Tunaweza kushinikiza na tunaweza pop.
Hebu kuanza na kushinikiza.
Tena, kusukuma ni kuongeza mpya kipengele juu ya stack.
>> Basi je, tunahitaji kufanya katika hii safu ya utekelezaji msingi?
Vizuri kwa ujumla the kushinikiza kazi ni kwenda
haja ya kukubali pointer kwa stack.
Sasa kuchukua pili na kufikiri juu yake.
Kwa nini tunataka kukubali pointer stack?
Kumbuka kutoka video ya awali juu ya wigo kutofautiana na kuyatumia,
nini kitatokea kama sisi tu alimtuma stack, s badala katika kama parameter?
Nini ingekuwa kweli kuwa kupita katika huko?
Kumbuka sisi ni kujenga nakala wakati sisi kupita kwa kazi
isipokuwa sisi kutumia kuyatumia.
Na hivyo kazi hii kushinikiza mahitaji kukubali pointer mkusanyiko
ili sisi ni kweli kubadilisha stack sisi nia ya kubadilika.
>> Wengine jambo kushinikiza pengine anataka kukubali ni data kipengele cha aina thamani.
Katika kesi hiyo, tena, integer kwamba tunakwenda kuongeza hadi juu ya stack.
Hivyo sisi tumepewa vigezo zetu mbili.
Je, ni sisi kwenda sasa kufanya ndani ya kushinikiza?
Naam, tu, sisi ni kwenda tu kuongeza kwamba kipengele juu ya stack
na kisha kubadili ambapo juu ya stack ni, kwamba s dot thamani ya juu.
Hivyo hii ni nini kazi Tamko kwa kushinikiza
ili kuangalia kama katika safu makao utekelezaji.
>> Tena hii si utawala ngumu na ya haraka kwamba unaweza kubadili hali hii na kuwa na
ni kutofautiana katika njia tofauti.
Labda s ni alitangaza kimataifa.
Na hivyo huna hata haja kupita ni kama parameter.
Hii ni mara ya pili tu ujumla kesi kwa kushinikiza.
Na kuna tofauti njia za kutekeleza.
Lakini katika kesi hii yetu kushinikiza ni kwenda kuchukua
hoja mbili, pointer mkusanyiko na data kipengele cha aina thamani, integer
kwa kesi hii.
>> Hivyo sisi alitangaza s, sisi Alisema s.top sawa na 0.
Sasa hebu kushinikiza idadi 28 kwenye stack.
Vizuri nini maana gani?
Naam sasa juu ya stack ni 0.
Na hivyo kile kimsingi kinaenda kutokea ni
tunakwenda fimbo idadi 28 katika safu eneo 0.
Pretty moja kwa moja, kulia, na hivyo Ilikuwa juu na sasa sisi ni vizuri kwenda.
Na kisha sisi haja ya kubadili kile juu ya stack itakuwa.
Hivyo kwamba wakati mwingine sisi kushinikiza kipengele katika,
tunakwenda kuhifadhi katika safu eneo, pengine si 0.
Hatutaki overwrite nini sisi tu ya kuweka huko.
Na hivyo tutaweza tu hoja juu ya 1.
Kwamba pengine hufanya akili.
>> Sasa kama tunataka kuweka kipengele mwingine kwenye stack, wanasema tunataka kushinikiza 33,
vizuri sasa sisi ni kwenda tu kuchukua 33 na kuiweka katika safu eneo idadi
1, na kisha kubadili juu ya yetu stack kuwa safu eneo namba mbili.
Hivyo kama wakati mwingine tunataka kushinikiza kipengele kwenye stack,
kutakuwa na kuwekwa katika safu eneo 2.
Na hebu kufanya hivyo mara moja zaidi.
Tutaweza kushinikiza 19 mbali ya mwingi.
Tutaweza kuweka 19 katika safu eneo 2 na mabadiliko juu ya stack yetu
kuwa safu eneo 3 hivyo kama ijayo wakati sisi
haja ya kufanya kushinikiza sisi ni vizuri kwenda.
>> OK, hivyo hiyo ni kusukuma kwa kifupi.
Je kuhusu yanajitokeza?
Hivyo popping ni aina ya mwenzake kwa kusukuma.
Ni jinsi gani sisi kuondoa data kutoka stack.
Na katika mahitaji ujumla pop kufanya yafuatayo.
Inahitaji kukubali pointer stack, tena katika kesi ujumla.
Katika baadhi ya kesi nyingine waweza wametangaza stack kimataifa,
katika kesi ambayo huna haja ya kupita katika sababu tayari ina huduma hiyo
kama variable kimataifa.
Lakini basi kile kingine tunahitaji kufanya nini?
Vizuri tulikuwa incrementing juu ya stack katika kushinikiza,
hivyo sisi ni pengine atataka kwa pungufu juu ya stack
katika pop, sawa?
Na kisha bila shaka sisi ni pia atataka
kurudi thamani kwamba sisi kuondoa.
Kama sisi ni kuongeza vipengele, tunataka kupata mambo nje baadaye,
sisi pengine kwa kweli unataka kuhifadhi yao ili sisi
si tu kufuta yao kutoka stack na kisha kufanya chochote pamoja nao.
Kwa ujumla kama tuko kusukuma na popping hapa
tunataka kuhifadhi hii Maelezo kwa njia ya maana
na hivyo hana kufanya maana tu kuondokana na hilo.
Hivyo kazi hii lazima pengine kurudi thamani kwetu.
>> Hivyo hii ni nini tamko kwa pop ili kuangalia kama kuna juu kushoto.
Hii anarudi kazi data ya aina thamani.
Tena tumekuwa kutumia integers hela.
Na anapokea pointer mkusanyiko kama pekee hoja yake au vigezo pekee.
Kwa hiyo kile ni pop kwenda kufanya?
Hebu sema tunataka sasa pop kipengele mbali ya s.
Basi kumbuka mimi alisema kuwa mwingi ni mwisho katika, kwanza nje, LIFO data miundo.
Ambayo kipengele ni kwenda kuondolewa kutoka mkusanyiko?
Je, nadhani 19?
Kwa sababu wewe d kuwa na haki.
19 Ilikuwa kipengele mwisho sisi aliongeza kwa stack tulipokuwa kusukuma mambo juu,
na hivyo ni kwenda kwanza kipengele kwamba anapata kuondolewa.
Ni kama tulivyosema 28, na kisha sisi kuweka 33 juu yake,
na sisi kuweka 19 juu ya kwamba.
Kipengele tu tunaweza kuchukua mbali ni 19.
>> Sasa katika mchoro hapa kile nimepata kufanyika ni aina ya kufutwa 19 kutoka safu.
Hiyo ni kweli nini tunakwenda kufanya.
Tunakwenda tu aina ya kujifanya si huko.
Bado kuna katika kwamba kumbukumbu eneo,
lakini sisi ni kwenda tu kupuuza kwa kubadilisha juu ya stack yetu
asiwe 3-2.
Hivyo kama tulikuwa sasa kushinikiza kipengele kingine kwenye stack,
ingekuwa juu ya kuandika 19.
>> Lakini hebu kwenda kwa njia ya shida ya kufuta 19 kutoka stack.
Tunaweza kujifanya tu siyo huko.
Kwa madhumuni ya mkusanyiko ni gone ikiwa sisi kubadili juu ya kuwa 2 badala ya 3.
Haki wote, ili kwamba ilikuwa pretty kiasi.
Hayo ni yote tunahitaji kufanya pop kipengele mbali.
Hebu kufanya hivyo tena.
Hivyo nimekuwa yalionyesha katika nyekundu hapa zinaonyesha sisi ni kufanya wito mwingine.
Tunakwenda kufanya kitu kimoja.
>> Basi nini kitatokea?
Naam, sisi ni kwenda kuhifadhi 33 katika x na tunakwenda
kubadili juu ya stack kwa 1.
Hivyo kwamba kama tulikuwa sasa kushinikiza kipengele kwenye mkusanyiko ambayo tuko
kwenda kufanya hivi sasa, nini kitatokea
ni tunakwenda overwrite safu eneo namba 1.
Hivyo kwamba 33 ni aina ya kushoto nyuma ya kwamba sisi tu akadai
si huko tena, tunakwenda tu kwa clobber yake na kuweka 40 huko badala yake.
Na kisha bila shaka, tangu tukiwa kushinikiza,
tunakwenda increment juu ya stack 1-2
ili kwamba kama sisi sasa kuongeza kipengele mwingine ni itabidi
kwenda katika safu eneo namba mbili.
>> Sasa orodha wanaohusishwa ni mwingine njia ya kutekeleza mwingi.
Na kama ufafanuzi juu ya hii screen hapa inaonekana ukoo na wewe,
ni kwa sababu inaonekana karibu sawa, kwa kweli,
ni pretty much ni hasa sawa na orodha moja moja wanaohusishwa,
kama unakumbuka kutoka mjadala wetu wa moja moja wanaohusishwa orodha katika video nyingine.
Kizuizi tu hapa ni kwa ajili yetu kama programmers,
sisi ni haruhusiwi kuingiza au kufuta nasibu
kutoka orodha moja moja wanaohusishwa ambayo tunaweza awali kufanya.
Tunaweza tu sasa kuingiza na kufuta kutoka mbele au juu ya wanaohusishwa
orodha.
Hiyo ni kweli tu tofauti ingawa.
Hii ni vinginevyo orodha moja moja wanaohusishwa.
Ni tu kizuizi kuchukua nafasi ya juu ya sisi wenyewe
kama programmers kwamba mabadiliko hayo kwenye mkusanyiko.
>> Utawala hapa ni daima kudumisha pointer na mkuu wa orodha wanaohusishwa.
Bila shaka hii ni kwa ujumla utawala muhimu kwanza.
Kwa moja moja wanaohusishwa orodha anyway wewe tu haja pointer kichwa
ili kuwa na kwamba mlolongo kuwa na uwezo wa kutaja
kwa kila kipengele nyingine katika orodha wanaohusishwa.
Lakini ni hasa muhimu kwa stack.
Na hivyo kwa ujumla uko kwenda kwa kweli wanataka
pointer hii kuwa kutofautiana kimataifa.
Ni pengine kwenda kuwa hata rahisi kwa njia hiyo.
Hivyo milinganisho ya kushinikiza na pop ni nini?
Kulia.
Hivyo kusukuma tena ni kuongeza kipengele mpya ya stack.
Katika orodha wanaohusishwa kwamba ina maana tunakwenda na
kujenga nodi mpya kwamba sisi ni kwenda kuongeza katika orodha wanaohusishwa,
na kisha kufuata hatua makini kwamba tumekuwa ilivyoainishwa hapo awali
katika orodha moja moja wanaohusishwa na kuongeza kuwa kwa mlolongo bila kuvunja mlolongo
na kupoteza au orphaning yoyote mambo ya orodha wanaohusishwa.
Na kwamba kimsingi nini kwamba Blob kidogo ya maandishi huko muhtasari.
Na hebu tuangalie saa hiyo kama kielelezo.
>> Hivyo hapa ni orodha yetu wanaohusishwa.
Ni Sanjari ina mambo manne.
Na kwa usahihi zaidi hapa ni wetu stack zenye mambo manne.
Na hebu sema sisi sasa wanataka kushinikiza bidhaa mpya kwenye stack hii.
Na tunataka kushinikiza mpya bidhaa ambazo data thamani ya 12.
Vizuri nini sisi kwenda kufanya?
Vizuri kwanza tunakwenda malloc nafasi, dynamically
kutenga nafasi kwa nodi mpya.
Na bila shaka mara baada ya sisi kufanya wito malloc sisi daima
kuhakikisha kuangalia kwa null, kwa sababu kama tulipata null nyuma
kulikuwa na aina fulani ya tatizo.
Hatutaki dereference kwamba null pointer au utakuwa kuteseka seg kosa.
Hiyo si nzuri.
Hivyo tumekuwa malloced ya nodi.
Tutaweza kudhani tumekuwa na mafanikio hapa.
Sisi ni kwenda kuweka katika 12 uwanja wa nodi data.
Sasa je, unakumbuka ambayo ya kuyatumia yetu hatua ijayo hivyo hatuna kuvunja minyororo?
Sisi kuwa wanandoa wa chaguzi hapa lakini moja tu kwamba kinaendelea kuwa salama
ni kuweka habari ijayo pointer hatua kwa kichwa wa zamani wa orodha
au nini hivi karibuni kuwa umri wa mkuu wa orodha.
Na sasa kwamba wote wa wetu mambo ni minyororo pamoja,
tunaweza tu hoja orodha kwa uhakika kwenye sehemu moja kwamba mwezi gani.
Na sisi sasa kwa ufanisi kusukuma kipengele mpya kwenye mbele ya stack.
>> Pop sisi nataka tu kufuta kwamba kipengele kwanza.
Na hivyo kimsingi nini tuna kufanya hapa,
vizuri inabidi kutafuta kipengele cha pili.
Hatimaye ambayo yamekuwa mapya kichwa baada ya sisi kufuta moja ya kwanza.
Hivyo sisi tu haja ya kuanza kutoka mwanzo, kusonga mbele moja.
Mara sisi tumepewa uwezo juu moja mbele ya ambapo sisi sasa
ni tunaweza kufuta moja kwanza salama na kisha tunaweza tu hoja kichwa
kwa uhakika na kile ilikuwa awamu ya pili na kisha sasa
ni ya kwanza baada ya kuwa nodi umefutwa.
>> Hivyo tena, kuchukua kuangalia saa hiyo kama mchoro sisi
wanataka sasa pop kipengele mbali ya stack hii.
Hivyo tunafanya nini?
Naam sisi ni kwanza kwenda kujenga pointer mpya ambayo inaenda
kwa uhakika na doa sawa na kichwa.
Tunakwenda hoja hiyo nafasi moja mbele kwa kusema trav sawa
Trav ijayo kwa mfano, ambayo ingekuwa mapema trav pointer moja
nafasi mbele.
Sasa kwa kuwa sisi tumepewa kushikilia kitu cha kwanza
kupitia pointer iitwayo orodha, na kipengele cha pili kupitia pointer iitwayo
trav, tunaweza kwa usalama kufuta kwamba kitu cha kwanza kutoka mkusanyiko
bila ya kupoteza wengine ya mlolongo sababu sisi
kuwa na njia kwa kutaja kwa kipengele cha pili
mbele kwa njia ya pointer iitwayo trav.
>> Hivyo sasa tunaweza bure kwamba nodi.
Tunaweza bure orodha.
Na kisha wote tunahitaji kufanya sasa ni hoja ya orodha kwa uhakika kwenye sehemu moja
kwamba trav gani, na tuko aina ya nyuma ambapo sisi kuanza kabla ya sisi kusukuma 12
juu ya katika nafasi ya kwanza, haki.
Hii ni hasa ambapo tulikuwa.
Tulikuwa na hii stack nne kipengele.
Sisi aliongeza tano.
Sisi kusukuma tano kipengele juu, na kisha sisi
popped kwamba hivi karibuni aliongeza kipengele nyuma mbali.
>> Hiyo ni kweli pretty much yote kuna mwingi.
Unaweza kutekeleza yao kama arrays.
Unaweza kutekeleza yao kama orodha wanaohusishwa.
Kuna, bila shaka, wengine njia za kutekeleza yao pia.
Kimsingi sababu tunataka kutumia mwingi ni kudumisha data kwa namna
kwamba hivi karibuni aliongeza kipengele ni jambo la kwanza tuko
atataka kupata nyuma.
Mimi nina Doug Lloyd, hii ni cs50.