DOUG Lloyd: Të gjithë të drejtë, kështu që me këtë pikë ju jeni
ndoshta goxha i njohur me vargjeve dhe listat lidhura
që është dy primar strukturat e të dhënave ne kemi
foli për për mbajtjen grupe të të dhënat e llojeve të ngjashme të të dhënave të organizuar.
>> Tani ne jemi duke shkuar për të folur në lidhje me një çift të variacioneve
në vargjeve dhe listat e lidhura.
Në këtë video ne jemi duke shkuar për të folur për oxhaqet.
Në mënyrë të veçantë ne do të flasim rreth një strukturë e të dhënave të quajtur një pirg.
Kujtoni nga diskutimet e mëparshme për pointers dhe kujtesës,
se rafte është edhe të përmendur për një segment të kujtesës
ku deklaroi statike kujtim memory-- që ju
emrin, variablat që emri, et cetera dhe funksion korniza të cilat ne gjithashtu
korniza thirrje rafte ekzistojnë.
Pra, kjo është një strukturë e të dhënave pirg jo një segment rafte e kujtesës.
NE RREGULL.
>> Por çfarë është një pirg?
Pra, kjo është shumë e shumë vetëm një lloj të veçantë të strukturës së
që ruan të dhënat në mënyrë të organizuar.
Dhe nuk ka dy shumë Mënyra e zakonshme për të zbatuar
oxhaqet duke përdorur dy strukturat e të dhënave se ne jemi tashmë të njohur me,
vargjeve dhe listat lidhura.
Çfarë e bën një të veçantë pirg është Mënyra në të cilën ne kemi vënë informacion
në rafte, dhe mënyrën se si ne hiqni informacion nga rafte.
Në mënyrë të veçantë me oxhaqet rregulli është vetëm më
Kohët e fundit shtuar element mund të hiqet.
>> Pra, mendoni për atë si në qoftë se kjo është një pirg.
Ne jemi grumbullonin informacion në krye të vetë,
dhe vetëm gjëja në krye i grumbullit mund të hiqet.
Ne nuk mund të hiqni gjë nën sepse çdo gjë tjetër do të
shembet dhe bien mbi.
Pra, ne me të vërtetë jemi duke ndërtuar një pirg që ne pastaj kemi për të hequr copë me copë.
Për shkak të kësaj, ne zakonisht i referohemi në një pirg, si një strukturë LIFO,
zgjasë në, nga e para.
LIFO, të zgjasë në, së pari jashtë.
>> Pra, për shkak të këtij kufizimi në si informacion mund të shtohet në
dhe të hiqen nga një pirg, nuk ka të vërtetë vetëm dy gjëra që mund të bëjmë me një pirg.
Ne mund shtytje, i cili është Termi ne përdorim për të shtuar
një element i ri në majën e rafte, ose në qoftë se rafte nuk ekziston
dhe ne jemi duke krijuar atë nga e para, duke krijuar rafte në vendin e parë
do të jetë e shtyrë.
Dhe pastaj pop, kjo është lloj i CS Termi ne i përdorim për të hequr më të fundit
shtimit element nga maja e pirg.
>> Pra, ne do të shikojmë në të dyja Implementimi, si grup i bazuar
dhe listë e lidhur në bazë.
Dhe ne jemi duke shkuar për të fillojë me grup bazë.
Kështu që këtu është ideja themelore e asaj që Struktura e të dhënave rafte grup i bazuar
do të duken si.
Ne kemi një përkufizim e shtypur këtu.
Brenda se ne kemi dy anëtarë apo fusha të strukturës.
Ne kemi një rrjet.
Dhe përsëri unë jam duke përdorur arbitrar Vlera e tipit të të dhënave.
>> Pra, kjo mund të jetë çdo lloj të dhënave, Char int ose disa të dhëna të tjera
shkruani ju krijuar më parë.
Pra, ne kemi një rrjet të kapaciteteve të madhësisë.
Kapaciteti qenë një kile përcaktuar konstante, ndoshta diku tjetër në dosjen tonë.
Pra, vini re tashmë me këtë të veçantë Zbatimi ne jemi bounding
veten si ishte tipike rasti me vargjeve,
të cilat ne nuk mund dinamike resize, ku ka një numër të caktuar
e elementeve maksimale që ne mund të vënë në rafte tonë.
Në këtë rast është e elementet e kapaciteteve.
>> Ne gjithashtu mbajnë gjurmët e në krye të rafte.
Çfarë element është më e shtuar kohët e fundit në rafte?
Dhe kështu që ne mbajnë gjurmët e që në një ndryshore të quajtur top.
Dhe e gjithë kjo merr përfundoi së bashku në një lloj të ri të dhënave të quajtur një pirg.
Dhe një herë ne jemi krijuar ky lloj i ri të dhëna
ne mund ta trajtojmë atë si çdo lloj tjetër të të dhënave.
Ne mund të deklarojë rafte s, ashtu si ne mund të bëjmë int x, apo y char.
Dhe kur themi rafte s, dhe çfarë ndodh
po ne kemi marrë një sërë kujtesës vendosur mënjanë për ne.
>> Në këtë kapacitet rast Unë kam vendosur me sa duket
është 10 sepse unë kam marrë një variable të vetme të tipit rafte
e cila përmban dy fusha kujtojnë.
Një grup, në këtë rast po ndodh të jetë një grup i numrave të plotë
siç është rasti në shumicën e shembujve të mia.
Dhe një tjetër variabël integer i aftë për ruajtjen në krye,
shtoi më të fundit element të pirg.
Pra, një turrë e vetme e asaj që ne përkufizohet vetëm duket si ky.
Kjo është një kuti që përmban një grup i 10 çfarë
do të jetë e integers në këtë rast dhe një tjetër variabël integer atje në gjelbër
për të treguar në krye të rafte.
>> Për të vendosur në krye të rafte ne vetëm themi s.top.
Kjo është se si ne të hyrë në një Fusha e një strukture kujtojnë.
s.top barabartë 0 efektivisht e bën këtë për të rafte tonë.
Pra, përsëri ne kemi dy operacione që ne mund të kryejnë tani.
Ne mund të shtyjë dhe ne mund të pop.
Le të fillojmë me shtytje.
Përsëri, duke i shtyre është shtuar një të ri element në majë të pirg.
>> Pra, çfarë ne duhet të bëjmë në ky grup zbatimi i bazuar?
E pra në përgjithësi Funksioni shtytje po shkon
të duhet të pranojë një treguesin në rafte.
Tani ndalo një sekondë dhe mendoni për atë.
Pse do të duam të pranojmë një tregues për rafte?
Kujtoni nga e kaluara videos në Shtrirja ndryshueshme dhe pointers,
çfarë do të ndodhte nëse ne vetëm të dërguar rafte, s dhe jo në si një parametër?
Çfarë në të vërtetë do të kalojë në atje?
Mos harroni ne jemi duke krijuar një kopje kur ne të kalojë atë në një funksion
nëse ne përdorim pointers.
Dhe kështu që ky funksion të shtyjë nevojat të pranojë një tregues për rafte
kështu që ne jemi të vërtetë ndryshuar rafte ne synojmë për të ndryshuar.
>> Gjëja Push tjetër ndoshta dëshiron të të pranojë është një element i të dhënave të vlerës së tipit.
Në këtë rast, një herë, një numër i plotë që ne jemi duke shkuar për të shtuar në krye të rafte.
Pra, ne kemi marrë dy parametra tona.
Çfarë do të shkojmë për tani bëjë brenda shtytje?
E pra, thjesht, ne jemi vetëm duke shkuar për të shtuar që element në majë të pirg
dhe pastaj të ndryshojë ku në krye të rafte është, që s dot vlerë të lartë.
Pra, kjo është ajo që një funksion Deklarata për shtytje
mund të duket si në një array-bazuar zbatimi.
>> Përsëri kjo nuk është një rregull e vështirë dhe të shpejtë që ju mund të ndryshojë këtë dhe të ketë
ajo ndryshojnë në mënyra të ndryshme.
S Ndoshta është deklaruar në nivel global.
Dhe kështu që ju nuk duhet edhe për të kaluar ajo është si një parametër.
Kjo është përsëri vetëm një Rasti i përgjithshëm për shtytje.
Dhe atje janë të ndryshme mënyra për ta zbatuar atë.
Por në këtë rast tonë shtytje do të marrë
dy argumente, një tregues për një pirg dhe një element të dhëna me vlerë të tipit, integer
në këtë rast.
>> Pra, ne shpallëm s, ne tha s.top barabartë me 0.
Tani le të shtyjë numrin 28 mbi rafte.
E pra çfarë do të thotë?
Well aktualisht krye të rafte është 0.
Dhe kështu që ajo që është në thelb do të ndodhë është
ne jemi duke shkuar për të rrinë numrin 28 në array lokacion 0.
Shumë i thjeshtë, i drejtë, që ishte e lartë dhe tani ne jemi të mirë për të shkuar.
Dhe pastaj ne kemi nevojë për të ndryshuar çfarë në krye të rafte do të jetë.
Kështu që herën tjetër ne shtytje një element në,
ne jemi duke shkuar për të ruajtur atë në Vendndodhja grup, ndoshta jo 0.
Ne nuk duam të prishësh atë që ne vetëm vënë atje.
Dhe kështu që ne do të lëvizin vetëm maja deri 1.
Kjo ndoshta ka kuptim.
>> Tani në qoftë se ne duam të vënë një tjetër element mbi rafte, thonë se ne duam të shtyjë 33,
edhe tani ne jemi vetëm duke shkuar për të marrë 33 dhe e vënë atë në array numrin e lokacionit
1, dhe pastaj të ndryshojë në krye të tonë rafte të jetë array vend numri dy.
Pra, nëse herën tjetër ne duam të të shtyjë një element mbi rafte,
ajo do të vihet në vend array 2.
Dhe le ta bëjmë atë një më shumë kohë.
Ne do të shtyjë 19 off e oxhaqet.
Ne do të vënë 19 në array vend 2 dhe për të ndryshuar në krye të rafte tonë
të jetë array vend 3 kështu që në qoftë se kohë kemi ardhshëm
nevojë për të bërë një shtytje ne jemi të mirë për të shkuar.
>> OK, kështu që është shtyrë në një fjalë.
Po në lidhje me popping?
Pra Popping është lloj i Homologu të shtyrë.
Kjo është se si ne të hequr të dhënat nga rafte.
Dhe në nevojat e përgjithshme pop të bëjë të mëposhtme.
Ajo duhet të pranojë një tregues për rafte, përsëri në rastin e përgjithshëm.
Në disa raste tjera që ju mund kanë deklaruar rafte globalisht,
në të cilin rast ju nuk keni nevojë për të kaluar atë në sepse ajo tashmë ka qasje në të
si një ndryshore globale.
Por atëherë çfarë tjetër nuk kemi nevojë të bëjmë?
E pra ne u bën rritjen në krye të rafte në shtytje,
kështu që ne jemi me siguri do të duan për pakësim në krye të rafte
në pop, e drejtë?
Dhe pastaj sigurisht ne jemi gjithashtu do të duan
për t'u kthyer vlerën që kemi hequr.
Nëse ne jemi duke shtuar elemente, ne duam për të marrë elemente nga më vonë,
ne ndoshta në fakt duan për të ruajtur ato në mënyrë që ne
nuk i vetëm fshini ato nga rafte dhe pastaj të bëjë asgjë me ta.
Në përgjithësi në qoftë se ne jemi duke i shtyre dhe popping këtu
ne duam të ruajtur këtë informacion në një mënyrë kuptimplote
dhe kështu që nuk ka të bëjë kuptim të vetëm hidhni atë.
Pra, ky funksion duhet të ndoshta kthehen një vlerë për ne.
>> Pra, kjo është ajo që një deklaratë për pop mund të duket si atje në të majtë të lartë.
Ky funksion të kthimit të dhënat e vlerës së tipit.
Përsëri ne kemi qenë duke përdorur integers të gjithë.
Dhe ajo pranon një tregues për një pirg si Argumenti i saj i vetëm apo parametër i vetëm.
Pra, çfarë po pop do të bëni?
Le të themi se duam të tani pop një element jashtë e s.
Pra, mos harroni kam thënë se oxhaqet janë të fundit në, e parë jashtë, LIFO dhënave strukturave.
Cili element do të të hiqet nga pirg?
A ju me mend 19?
Sepse ju do të jetë e drejtë.
19 ishte elementi i fundit kemi shtuar të rafte kur ishim shtyjnë elemente në,
dhe kështu ajo do të të parë element që merr hequr.
Është sikur tha ne 28, dhe pastaj ne kemi vënë 33 në krye të saj,
dhe ne kemi vënë 19 në krye të kësaj.
I vetmi element që ne mund të marrë jashtë është 19.
>> Tani në diagramin këtu atë që kam bërë është lloj i fshirë 19 nga array.
Kjo nuk është në fakt ajo që ne jemi duke shkuar për të bërë.
Ne jemi vetëm duke shkuar për të llojit të pretendojë se nuk është atje.
Është ende atje në se vendndodhja e kujtesës,
por ne jemi vetëm duke shkuar për të injorojë atë duke ndryshuar në krye të rafte tonë
nga të qenit 3 në 2.
Pra, nëse ne do të shtyjë tani Një tjetër element mbi rafte,
kjo do të shkruaj mbi 19.
>> Por le të mos shkojnë nëpër telashe e fshirjes 19 nga rafte.
Ne vetëm mund të pretendojë se nuk është atje.
Për qëllime të rafte ato zhduken nëse ne ndryshojë lartë të jetë 2 në vend të 3.
Të gjithë të drejtë, kështu që ishte shumë e shumë atë.
Kjo është e gjitha ne duhet të bëjmë të pop një element off.
Le ta bëjmë atë përsëri.
Kështu që unë e kam theksuar atë në të kuqe këtu për tregojnë ne jemi duke e bërë një telefonatë tjetër.
Ne jemi duke shkuar për të bërë të njëjtën gjë.
>> Pra, çfarë do të ndodhë?
E pra, ne jemi duke shkuar për të ruajtur 33 në x dhe ne jemi duke shkuar
për të ndryshuar në krye të rafte në 1.
Kështu që në qoftë se ne ishim tani për të nxitur një Elementi në rafte që ne jemi
do të bëjë të drejtë tani, çfarë do të ndodhë
po ne jemi duke shkuar prishësh Grup vend numri 1.
Kështu që 33 që u la lloj prapa se ne vetëm pretenduar
nuk është më aty, ne jemi vetëm duke shkuar për plaçkë dhe vënë 40 atje në vend.
Dhe pastaj sigurisht, pasi kemi bërë një shtytje,
ne jemi duke shkuar për të rrisim maja e pirg nga 1 deri 2
kështu që në qoftë se ne tani shtoni një element tjetër ajo do të
shkoni në array lokacionit numrin dy.
>> Tani Listat e lidhura janë një tjetër mënyrë për të zbatuar oxhaqet.
Dhe në qoftë se ky përkufizim për Ekran këtu duket të njohura për ju,
kjo është për shkak se ajo duket pothuajse saktësisht të njëjtë, në fakt,
kjo shumë e shumë është pikërisht njëjtë si një listë e lidhur në formë individuale,
nëse ju kujtohet nga diskutimit tonë të lidhur veçmas listat në një tjetër video.
I vetmi kufizim këtu është për ne si programuesit,
ne nuk jemi të lejuar të futur apo fshij rastësisht
nga lista e lidhur veçmas që ne mund të bëjmë më parë.
Ne vetëm tani mund të futni dhe të fshini nga front apo në krye të lidhur
lista.
Kjo është me të vërtetë e vetmja Dallimi pse.
Kjo është ndryshe një listë e lidhur në formë individuale.
Është vetëm kufizimi duke zëvendësuar në veten tonë
si programuesit që ndryshon atë në një pirg.
>> Rregulli këtu është që gjithmonë të mbajë një treguesin në krye të listës lidhur.
Kjo është sigurisht një përgjithësi Rregulli i parë i rëndësishëm.
Për lidhur veçmas listë gjithsesi ju duhet vetëm një tregues për kokë
në mënyrë të ketë se zinxhir të jetë në gjendje për t'iu referuar
për çdo element tjetër në lista e lidhur.
Por kjo është veçanërisht e i rëndësishëm me një pirg.
Dhe kështu në përgjithësi ju jeni duke shkuar për të vërtetë duan
ky tregues të jetë një ndryshore globale.
Kjo ndoshta do të të jetë edhe më e lehtë në këtë mënyrë.
Pra cilat janë analoge e shtytje dhe pop?
E drejtë.
Pra, duke i shtyre përsëri është shtuar një element i ri në rafte.
Në një listë të lidhura që do të thotë që ne do të kemi
për të krijuar një nyje të re që ne jemi duke shkuar për të shtuar në listën e lidhur,
dhe pastaj ndiqni hapat të kujdesshëm që ne i kemi përshkruar më parë
në listat e lidhura veçmas për të shtuar se zinxhiri pa thyer zinxhirin
dhe humbjes ose orphaning ndonjë elementet e listës lidhura.
Dhe kjo është në thelb ajo që pak pikë e tekstit atje përmbledh.
Dhe le të marrin një vështrim në atë si një diagram.
>> Kështu që këtu është lista jonë e lidhur.
Ai njëkohësisht përmban katër elemente.
Dhe më të përsosur këtu është tonë rafte përmban katër elemente.
Dhe le të thonë se ne tani duam të të shtyjë një artikull të ri mbi këtë rafte.
Dhe ne duam që të shtyjë një të ri Pika dhënat e të cilit vlerë është 12.
Mirë se çfarë do të shkojmë të bëjmë?
E pra së pari ne jemi duke shkuar për hapësirë ​​malloc, dinamike
ndajë hapësirë ​​për një nyje të re.
Dhe sigurisht menjëherë pas kemi bërë një thirrje për malloc ne gjithmonë
sigurohuni që të kontrolloni për null, sepse në qoftë se ne u null përsëri
ka pasur një lloj të problemit.
Ne nuk duam të dereference atë null pointer ose ju do të vuajnë një defekt seg.
Kjo nuk është e mirë.
Pra, ne kemi malloced e nyjeve.
Ne do të supozojmë që kemi pasur sukses këtu.
Ne jemi duke shkuar për të vënë 12 në fusha e të dhënave të kësaj nyje.
Tani ju kujtojnë se cili prej pointers tona lëviz tjetër kështu që ne nuk e thyejnë zinxhirin?
Ne kemi disa opcione këtu, por i vetmi që do të jetë i sigurt
është për të vendosur lajme akrep ardhshëm të Pika në kokë e vjetër të listës
apo atë që së shpejti do të jetë kreu i vjetër i listës.
Dhe tani që të gjithë e tona elemente janë të lidhur me zinxhirë së bashku,
ne vetëm mund të lëvizin listën në pikën në të njëjtin vend që bën të reja.
Dhe ne tani kemi shtyrë në mënyrë efektive një element i ri në pjesën e përparme të rafte.
>> Të pop ne vetëm duam të fshini se elementi i parë.
Dhe kështu në thelb ajo ne duhet të bëjmë këtu,
edhe ne duhet të gjejmë elementin e dytë.
Përfundimisht se do të bëhet i ri kokë pasi ne fshini një të parë.
Pra, ne vetëm duhet të fillojë nga fillimi, të lëvizë një sulmues.
Pasi ne kemi marrë një të mbajë në një përpara e ku ne aktualisht
janë ne mund të fshini një të parë në mënyrë të sigurtë dhe pastaj ne vetëm mund të lëvizin kokën
të tregojnë për çfarë ishte Termi i dytë dhe pastaj tani
është e para pas që Nyja është fshirë.
>> Pra, përsëri, duke marrë një vështrim atë si një diagram ne
duan të tani pop një Elementi off e këtij rafte.
Pra, çfarë bëjmë ne?
E pra ne jemi së pari do të krijojmë një tregues i ri që po ndodh
për pikë në të njëjtin vend si kokës.
Ne jemi duke shkuar për të lëvizur atë një pozicion përpara duke thënë është e barabartë Trav
Trav tjetër për shembull, të cilat do të avancojë atë trav akrep
pozicion përpara.
Tani që ne kemi marrë një mbajtur në elementin e parë
përmes treguesin e quajtur listë, dhe Elementi i dytë përmes një tregues të quajtur
Trav, ne mund të sigurtë të fshini atë Elementi i parë nga rafte
pa humbur pjesën tjetër e zinxhirit sepse ne
kanë një mënyrë për të referuar me elementin e dytë
përpara me anë të të akrep quajtur trav.
>> Deri tani ne mund të lirë atë nyje.
Ne mund të lirë listë.
Dhe pastaj të gjithë ne duhet të bëjmë tani është lëvizin listën e pikës në të njëjtin vend
që Trav bën, dhe ne jemi lloj prapa ku kemi filluar para se të shtyrë 12
në në radhë të parë, e drejtë.
Kjo është saktësisht ku ishim.
Ne kishim këtë katër element rafte.
Ne kemi shtuar një të pestën.
Ne shtyrë një të pestën element në, dhe pastaj ne
popped që më të fundit shtoi element mbrapa off.
>> Kjo është me të vërtetë shumë e shumë gjitha nuk është për oxhaqet.
Ju mund të zbatojë ato si vargjeve.
Ju mund të zbatojë ato si listat e lidhura.
Ka, natyrisht, të tjera mënyra për zbatimin e tyre si edhe.
Në thelb arsyeja që ne do të përdorim oxhaqet është për të ruajtur të dhënat në një mënyrë të tillë
që shtoi më të fundit element është gjëja e parë që ne jemi
do të dëshironi të merrni përsëri.
Unë jam Doug Lloyd, kjo është CS50.