DOUG LLOYD: Hea küll, nii käesoleva punkti olete
ilmselt päris tuttav massiivid ja ahelloendid
mis on kaks peamist andmestruktuurid me oleme
rääkis hoida komplekti andmed sarnaste andmete tüüpi organiseeritud.
>> Nüüd me ei kavatse rääkida umbes paar variatsioonid
kohta massiivid ja ahelloendid.
Selle video me läheme rääkida korstnad.
Nimelt me ​​ei kavatse rääkida umbes andmebaasi struktuuri nimetatakse virna.
Meenuta eelmise arutelud umbes viiteid ja mälu
et stack on ka nimi for segment mälu
kus staatiliselt deklareeritud memory-- mälu, et teil
Nime, muutujaid, siis nime, et cetera ja funktsiooni raamid, mida me ka
pinu raamid olemas.
Nii et see on virnas andmestruktuur ei virna segment mälu.
OKEI.
>> Aga milline on korstna?
Nii et see on päris palju lihtsalt eriline struktuur
mis säilitab andmed organiseeritud viisil.
Ja seal on kaks väga levinumad viisid ellu
korstnad kahe andmestruktuurid et me oleme juba tuttav,
massiivid ja ahelloendid.
Mis teeb virna eriliseks kuidas me paneme info
virna ja kuidas me informatsiooni eemaldamiseks pinu.
Eelkõige korstnad reegel on ainult kõige
viimati lisatud element saab eemaldada.
>> Nii mõelda, nagu oleks see pakk.
Me tekkimise info peal ise,
ja ainult asi tipus kuhi saab eemaldada.
Me ei saa eemaldada asja all sest kõik muu oleks
variseda ja kukkuda.
Nii et me tõesti ehitame virna, et Siis pead kaotada jaokaupa.
Sellepärast me tavaliselt viidata korstnat kui LIFO struktuuri,
kesta sisse, esimesena välja.
LIFO, kesta sisse, esimesena välja.
>> Nii, sest see piirang kuidas teavet saab lisatud
ja eemaldada korstna, seal on tõesti ainult kaks asja, mida me saame teha koos virna.
Me ei lükka, mis on Mõiste, mida me kasutame, lisades
uus element tippu Kestab, või kui virna ei ole olemas
ja me luua nullist, luua pinu esimese koha
oleks surudes.
Ja siis pop, see on omamoodi CS Mõiste me kasutame eemaldada viimati
lisada elemendi riidale.
>> Nii et me läheme vaatama nii rakendusi, nii massiivi põhineb
ja ahelloendid aluseks.
Ja me ei kavatse Alustame massiivi aluseks.
Nii et siin on põhiline idee, mida massiivi põhineb stack andmestruktuur
näeks.
Meil on trükitud määratluses.
Toas, et meil on kaks liiget või väljade struktuuri.
Meil on hulgaliselt.
Ja jälle ma kasutan suvaline andmete tüübi väärtus.
>> Nii et see võib olla mis tahes tüüpi andmetena int paalia või mõne muu andmeid
kirjuta sa varem loodud.
Nii et meil on hulgaliselt suurus võimsust.
Võimsus on nael määratletud pidev, võibolla kusagil mujal meie faili.
Nii märkate juba selle konkreetse rakendamise me piiravates
end oli tavaliselt puhul massiivid,
mida me ei saa dünaamiliselt suurust, kus seal on teatud arv
elementide maksimaalne, et saame panna meie stack.
Sel juhul võime elemente.
>> Samuti jälgida top pinu.
Mis element on kõige Hiljuti lisatud korstna?
Ja nii me jälgida, et muutujale nimega top.
Ja see kõik saab tõmmati kokku uude andmete tüübi nimega virna.
Ja kui me loodud see uus andmetüüp
saame ravida nagu muid andmeid tüübist.
Me võime kuulutada stack s, nagu me võiks teha int x, või char y.
Ja kui me ütleme, korstna s, hästi, mis juhtub
on meil saada komplekt mälu kõrvale meile.
>> Sel juhul võimsusega Olen ilmselt otsustanud
10 sest mul on Ühe muutuja tüüpi korstnat
mis sisaldab kahte väljad meenutada.
Array, sel juhul läheb olema massiivi täisarvud
nagu see on enamikus minu näited.
Ja teine ​​täisarv muutuja suudavad hoida üleval,
viimati lisatud element korstnat.
Nii ühe virna, mida me lihtsalt määratletud näeb välja selline.
See on karbis massiivi 10, mida
on täisarvud sel juhul ja teine ​​täisarv muutuja seal roheline
näidata riidale.
>> Kui soovite, et tippu stack me lihtsalt öelda s.top.
See, kuidas me pääse valdkonnas struktuuri tagasivõtmist.
s.top võrdub 0 tõhusalt teeb seda meie stack.
Nii jälle on meil kaks operatsiooni et suudame täita nüüd.
Me ei lükka ja me saame pop.
Alustame push.
Jällegi, surudes lisab uue element riidale.
>> Niisiis, mida me peame tegema Selle massiivi põhinev rakendamine?
Noh üldiselt push funktsioon läheb
et pead vastu võtma kursor pinu.
Nüüd mõtle hetk ja mõelda.
Miks me tahame vastu kursor stack?
Meenuta eelmise videod Muutuja ulatust ja viiteid,
Mis juhtuks, kui me just saatis stack, s pigem parameeter?
Mida tegelikult läbinud seal?
Pea meeles, me luua koopia kui võtame seda funktsiooni
Kui me kasutame suunanäitajaks.
Ja nii see funktsioon suruda vajadustele aktsepteerima viit virna
nii et me oleme tegelikult muutmata virna me kavatseme muuta.
>> Teine asi, push ilmselt tahab nõus on andmete element tüüpi väärtuse.
Sel juhul jällegi täisarv, et me ei kavatse lisada tippu pinu.
Nii on meil meie kaks parameetrit.
Mida me saame nüüd teha sees push?
Noh, lihtsalt, me lihtsalt läheb lisada et element riidale
ja siis muutuvad kus peal stack on, et s dot top väärtus.
Nii et see on see, mida funktsioon deklaratsiooni push
tunduda mõnes massiivi põhinev rakendamine.
>> Jälle see ei ole raske ja kiire reegel et võid muuta ja on
see on väga erinevad.
Ehk s kuulutatakse kogu maailmas.
Ja nii sa ei pea isegi läbida see parameeter.
See on jällegi vaid Üldjuhul push.
Ja seal on erinevad kuidas seda rakendada.
Aga sel juhul meie push see aega võtab
kaks argumenti, kursor virna ja andmeelemendis tüüpi väärtust, täisarv
sel juhul.
>> Nii me kuulutasime s, me ütles s.top võrdub 0.
Nüüd suruge number 28 peale virna.
Noh mida see tähendab?
Noh praegu Pinu on 0.
Ja mis on põhimõtteliselt juhtub on
me ei kavatse jääda arv 28 arvesse massiivi 0.
Päris lihtne, eks, et oli üleval ja nüüd oled hea minna.
Ja siis on meil vaja muuta seda, mis tippu stack on.
Nii et järgmine kord, me push element,
me ei kavatse seda säilitada massiivi asukohta, ilmselt mitte 0.
Me ei taha kirjutada mida me just sinna pannakse.
Ja nii me lihtsalt liikuda ülevalt 1.
See ilmselt mõtet.
>> Nüüd, kui me tahame panna teise elemendi peale virna, ütleme, et me tahame, et lükata 33,
Noh nüüd me lihtsalt aega võtab 33 ja pane see on massiivi asukoha number
1 ja siis muutus tippu meie Kestab olla massiivi asukoha number kaks.
Nii et kui järgmine kord tahame push element peale virna,
see saab panna massiivi asukohta 2.
Ja teeme, et veel üks kord.
Me suruda 19 välja korstnad.
Me paneme 19 massiiv asukohta 2 ja muuta top meie stack
olema massiiv asukohast 3 nii et kui järgmine kord, kui me
on vaja teha push meil oled hea minna.
>> OK, nii et on surudes lühikokkuvõte.
Aga popping?
Nii popping on omamoodi ametivenna surudes.
See, kuidas me kustutada andmeid virna.
Ja üldiselt pop vajadustele teha järgmist.
See peab aktsepteerima kursor Kestab jälle üldises puhul.
Mõnel teisel juhul võite on deklareerinud virna maailmas,
mille puhul ei ole vaja edastada see aastal, sest see on juba juurdepääs
kui globaalne muutuja.
Aga siis mida muud me peame tegema?
Noh olime incrementing top virna push,
nii me ilmselt läheb taha ainult kahandab riidale
pop, eks?
Ja siis muidugi me ka läheb taha
tagasi väärtust, mida me eemaldada.
Kui me lisame elemente, me tahame saada elemendid välja hiljem,
me ilmselt tegelikult tahad salvestada neid nii me
ei ole lihtsalt nende kustutamiseks Kestab ja tehke midagi koos nendega.
Üldiselt, kui me oleme surudes ja popping siin
Me tahame hoida seda informatsiooni mõtestatult
ja nii see ei tee mõtet lihtsalt loobuda.
Nii et see ülesanne peaks ilmselt tagastama väärtuse meile.
>> Nii et see on see, mida deklaratsiooni pop tunduda seal üleval vasakul.
See funktsioon tagastab andmete tüüpi väärtuse.
Jällegi oleme kasutanud täisarvud kogu.
Ja ta võtab kursor virna nagu selle ainus argument või füüsilisest parameeter.
Mis on pop tegema hakkad?
Oletame, et me tahame nüüd pop element off s.
Seega pidage meeles, ma ütlesin, et korstnad on viimase aastal, esimene välja, LIFO andmestruktuurid.
Milline element läheb saab eemaldada korstna?
Kas sa vist 19?
Sest sa tahaks olla õige.
19 oli viimane element lisasime Kestab kui olime surudes elemendid,
ja nii see läheb esimene element, mis saab eemaldada.
See on sama, kui me ütlesime 28, ja siis paneme 33 peal,
ja paneme 19 peal, et.
Ainus element saame startida on 19.
>> Nüüd diagrammil siin, mida ma olen teinud on omamoodi kustutatakse 19 massiivist.
See ei ole tegelikult mida me teeme.
Me lihtsalt läheb selline on teeselda seda seal ei ole.
See on ikka seal et mälu asukoht,
aga me lihtsalt läheb seda ignoreerida muutes top meie stack
alates on 3-2.
Nii kui me nüüd lükata teise elemendi peale virna,
see üle kirjutada 19.
>> Aga ärme lähe läbi häda kustutada 19 korstnat.
Me ei teeskleme seda seal ei ole.
Eesmärgil virna see on läinud, kui muudame top olema 2 asemel 3.
Olgu, nii et oli päris palju see.
See on kõik, mida me peame tegema pop element välja.
Teeme seda uuesti.
Nii et ma olen rõhutanud seda punast siin näitavad me teeme teise kõne.
Me teeme sama asja.
>> Mis siis juhtub?
Noh, me ei kavatse hoida 33 x ja me läheme
muuta riidale 1.
Nii et kui me nüüd tõugata element virna, mis me oleme
kavatseb teha just nüüd, Mis juhtub
on meil läheb ülekirjutamise massiivi asukoha number 1.
Nii et 33, mis oli omamoodi vasakule taga, et me lihtsalt teeskles
ei ole seal enam, me lihtsalt läheb to Tellida ja panna 40 seal asemel.
Ja siis muidugi sest tegime push,
me ei kavatse juurdekasvu Pinu 1-2
nii et kui nüüd lisada teise elemendi siis see
minema massiivi asukoha number kaks.
>> Nüüd seotud nimekirjad on teise kuidas rakendada korstnad.
Ja kui see määratlus on ekraan siin tundub tuttav,
see on, sest see näeb välja peaaegu täpselt sama, tegelikult
see päris palju on täpselt Sama kui üksikult seotud nimekirja,
Kui te mäletate meie arutelu üksikult ahelloendid teise video.
Ainus piirang siin on meie jaoks nagu programmeerijad,
me ei lubata sisestada või kustutada juhuslikult
alates üksikult seotud nimekirja mida me võiksime varem teha.
Me saame alles nüüd lisada ja kustutada esi- või ülaosa seotud
nimekirja.
See on tõesti ainus Erinevus küll.
See on muidu üksikult seotud nimekirja.
See on ainult piirang asendades meist endist
nagu programmeerijad, et muudab see virna.
>> Reegel on siin alati säilitada kursor juht ahelloend.
See on muidugi üldiselt Oluline reegel esimene.
Juba üksi seotud nimekirja niikuinii vaja ainult viit juht
selleks on, et kett olema võimalik viidata
iga teine ​​element on seotud nimekirja.
Aga see on eriti oluline virna.
Ja nii üldiselt oled läheb tegelikult tahavad
osuti olla globaalne muutuja.
See on ilmselt läheb olla isegi lihtsam nii.
Millised on analoogid push ja pop?
Õigus.
Nii lükates uuesti suurendab uus element korstnat.
In ahelloend et tähendab, et me lähed on
luua uus sõlm, et me oleme läheb lisada arvesse seotud nimekirja,
ja järgige hoolikalt samme et me oleme kirjeldatud varem
in üksikult ahelloendid lisamiseks kett lõhkumata kett
ja kaotada või orvustumine tahes elemendid seotud nimekirja.
Ja see on põhimõtteliselt mida see väike kämp teksti seal kokkuvõtlikult.
Ja olgem vaatleme seda kui diagramm.
>> Nii et siin on meie ahelloendid.
See samaaegselt sisaldab nelja elemendi.
Ja täiuslikumalt siin on meie Kestab sisaldab nelja elementi.
Ja oletame, et me nüüd tahame push uus kirje peale virna.
Ja me tahame, et lükata uue esemed, mille andmed väärtus on 12.
Noh, mida me saame teha?
Noh esiteks me ei kavatse malloc ruumi, dünaamiliselt
eraldada ruumi uue sõlme.
Ja muidugi kohe pärast me helistada malloc me alati
veenduge, et kontrollida null, sest kui me saime null tagasi
seal oli mingi probleem.
Me ei taha apparent et null osuti ehk siis kannatavad seg süü.
See ei ole hea.
Nii oleme malloced sõlme.
Eeldame oleme olnud edukas siin.
Me läheme panna 12 sisse andmeväljale et sõlme.
Nüüd sa meenutada, mida meie suunanäitajaks liigub järgmise nii et me ei riku kett?
Meil on paar võimalust siin aga ainus, mis saab olema ohutu
on seatud uudis järgmine viit punkti ja vana juht nimekirja
või mida saab varsti vana juht nimekirja.
Ja nüüd, et kõik meie elemendid on aheldatud koos,
meil võimalik liigutada nimekirja punkti samas kohas, et uus teeb.
Ja meil on nüüd tõhusalt surutakse uus element peale ees virn.
>> Pop me tahame kustutada Esimene element.
Ja nii põhimõtteliselt mida me peame tegema siin,
ka meil leida teine ​​element.
Lõpuks, mis muutub uus pea pärast me kustutame esimene.
Nii et me lihtsalt vaja alustada Alguses liikuda ühe edasi.
Kui meil kätte ühel ettepoole, kus me praegu
me ei kustuta esimene ohutult ja siis saame lihtsalt liikuda juht
käsk, mis oli Teisel ametiajal siis nüüd
Esmakordne pärast seda sõlm on kustutatud.
>> Nii uuesti, võttes pilk seda kui diagramm me
tahad nüüd pop element off virna.
Mida me siis teeme?
Noh me esimest kavatse luua uus osuti, mis läheb
osutada sama kohapeal juhina.
Me läheme liigutada ühe positsiooni edasi, öeldes trav võrdsete
trav kõrval näiteks mis edendaks trav kursorit ühe
asendis edasi.
Nüüd, kui meil on hoidke esimene element
läbi pointer nimetatakse nimekirja ja Teine element läbi pointer nimetatakse
trav, saame julgelt kustutada Esimene element korstnat
kaotamata ülejäänud keti sest me
on võimalus viidata teise elemendi
edastada teel pointer nimega matk.
>> Nüüd saame tasuta, mis sõlme.
Meil saab tasuta nimekirja.
Ja siis kõik me peame tegema, on praegu liikuda nimekirja viitavad samale kohale
et matk teeb, ja me oleme justkui tagasi kust me alustasime, enne kui me tõugata 12
kohta esiteks, eks.
See on täpselt, kus me olime.
Meil oli see neli elementi pinu.
Lisasime viiendiku.
Me nõudsime viiendiku element, ja siis me
hüppasid, et viimati lisada element tagasi maha.
>> See on tõesti päris palju kõik on korstnad.
Võite rakendada neid massiive.
Võite rakendada neid ahelloendid.
On muidugi muud kuidas rakendada neid samuti.
Põhimõtteliselt põhjus, miks me ei kasuta virnade on säilitada andmetega sellisel viisil
et viimati lisatud element on esimene asi, mida me oleme
tahame seda tagasi saada.
Ma olen Doug Lloyd, see on CS50.